tools/aapt2/compile/NinePatch.cpp

/*
 * Copyright (C) 2016 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "compile/Image.h"
#include "util/StringPiece.h"
#include "util/Util.h"

#include <androidfw/ResourceTypes.h>
#include <sstream>
#include <string>
#include <vector>

namespace aapt {

// Colors in the format 0xAARRGGBB (the way 9-patch expects it).
constexpr static const uint32_t kColorOpaqueWhite = 0xffffffffu;
constexpr static const uint32_t kColorOpaqueBlack = 0xff000000u;
constexpr static const uint32_t kColorOpaqueRed   = 0xffff0000u;

constexpr static const uint32_t kPrimaryColor = kColorOpaqueBlack;
constexpr static const uint32_t kSecondaryColor = kColorOpaqueRed;

/**
 * Returns the alpha value encoded in the 0xAARRGBB encoded pixel.
 */
static uint32_t getAlpha(uint32_t color);

/**
 * Determines whether a color on an ImageLine is valid.
 * A 9patch image may use a transparent color as neutral,
 * or a fully opaque white color as neutral, based on the
 * pixel color at (0,0) of the image. One or the other is fine,
 * but we need to ensure consistency throughout the image.
 */
class ColorValidator {
public:
    virtual ~ColorValidator() = default;

    /**
     * Returns true if the color specified is a neutral color
     * (no padding, stretching, or optical bounds).
     */
    virtual bool isNeutralColor(uint32_t color) const = 0;

    /**
     * Returns true if the color is either a neutral color
     * or one denoting padding, stretching, or optical bounds.
     */
    bool isValidColor(uint32_t color) const {
        switch (color) {
        case kPrimaryColor:
        case kSecondaryColor:
            return true;
        }
        return isNeutralColor(color);
    }
};

// Walks an ImageLine and records Ranges of primary and secondary colors.
// The primary color is black and is used to denote a padding or stretching range,
// depending on which border we're iterating over.
// The secondary color is red and is used to denote optical bounds.
//
// An ImageLine is a templated-interface that would look something like this if it
// were polymorphic:
//
// class ImageLine {
// public:
//      virtual int32_t getLength() const = 0;
//      virtual uint32_t getColor(int32_t idx) const = 0;
// };
//
template <typename ImageLine>
static bool fillRanges(const ImageLine* imageLine,
                       const ColorValidator* colorValidator,
                       std::vector<Range>* primaryRanges,
                       std::vector<Range>* secondaryRanges,
                       std::string* err) {
    const int32_t length = imageLine->getLength();

    uint32_t lastColor = 0xffffffffu;
    for (int32_t idx = 1; idx < length - 1; idx++) {
        const uint32_t color = imageLine->getColor(idx);
        if (!colorValidator->isValidColor(color)) {
            *err = "found an invalid color";
            return false;
        }

        if (color != lastColor) {
            // We are ending a range. Which range?
            // note: encode the x offset without the final 1 pixel border.
            if (lastColor == kPrimaryColor) {
                primaryRanges->back().end = idx - 1;
            } else if (lastColor == kSecondaryColor) {
                secondaryRanges->back().end = idx - 1;
            }

            // We are starting a range. Which range?
            // note: encode the x offset without the final 1 pixel border.
            if (color == kPrimaryColor) {
                primaryRanges->push_back(Range(idx - 1, length - 2));
            } else if (color == kSecondaryColor) {
                secondaryRanges->push_back(Range(idx - 1, length - 2));
            }
            lastColor = color;
        }
    }
    return true;
}

/**
 * Iterates over a row in an image. Implements the templated ImageLine interface.
 */
class HorizontalImageLine {
public:
    explicit HorizontalImageLine(uint8_t** rows, int32_t xOffset, int32_t yOffset,
                                 int32_t length) :
            mRows(rows), mXOffset(xOffset), mYOffset(yOffset), mLength(length) {
    }

    inline int32_t getLength() const {
        return mLength;
    }

    inline uint32_t getColor(int32_t idx) const {
        return NinePatch::packRGBA(mRows[mYOffset] + (idx + mXOffset) * 4);
    }

private:
    uint8_t** mRows;
    int32_t mXOffset, mYOffset, mLength;

    DISALLOW_COPY_AND_ASSIGN(HorizontalImageLine);
};

/**
 * Iterates over a column in an image. Implements the templated ImageLine interface.
 */
class VerticalImageLine {
public:
    explicit VerticalImageLine(uint8_t** rows, int32_t xOffset, int32_t yOffset,
                               int32_t length) :
            mRows(rows), mXOffset(xOffset), mYOffset(yOffset), mLength(length) {
    }

    inline int32_t getLength() const {
        return mLength;
    }

    inline uint32_t getColor(int32_t idx) const {
        return NinePatch::packRGBA(mRows[mYOffset + idx] + (mXOffset * 4));
    }

private:
    uint8_t** mRows;
    int32_t mXOffset, mYOffset, mLength;

    DISALLOW_COPY_AND_ASSIGN(VerticalImageLine);
};

class DiagonalImageLine {
public:
    explicit DiagonalImageLine(uint8_t** rows, int32_t xOffset, int32_t yOffset,
                               int32_t xStep, int32_t yStep, int32_t length) :
            mRows(rows), mXOffset(xOffset), mYOffset(yOffset), mXStep(xStep), mYStep(yStep),
            mLength(length) {
    }

    inline int32_t getLength() const {
        return mLength;
    }

    inline uint32_t getColor(int32_t idx) const {
        return NinePatch::packRGBA(
                mRows[mYOffset + (idx * mYStep)] + ((idx + mXOffset) * mXStep) * 4);
    }

private:
    uint8_t** mRows;
    int32_t mXOffset, mYOffset, mXStep, mYStep, mLength;

    DISALLOW_COPY_AND_ASSIGN(DiagonalImageLine);
};

class TransparentNeutralColorValidator : public ColorValidator {
public:
    bool isNeutralColor(uint32_t color) const override {
        return getAlpha(color) == 0;
    }
};

class WhiteNeutralColorValidator : public ColorValidator {
public:
    bool isNeutralColor(uint32_t color) const override {
        return color == kColorOpaqueWhite;
    }
};

inline static uint32_t getAlpha(uint32_t color) {
    return (color & 0xff000000u) >> 24;
}

static bool populateBounds(const std::vector<Range>& padding,
                           const std::vector<Range>& layoutBounds,
                           const std::vector<Range>& stretchRegions,
                           const int32_t length,
                           int32_t* paddingStart, int32_t* paddingEnd,
                           int32_t* layoutStart, int32_t* layoutEnd,
                           const StringPiece& edgeName,
                           std::string* err) {
    if (padding.size() > 1) {
        std::stringstream errStream;
        errStream << "too many padding sections on " << edgeName << " border";
        *err = errStream.str();
        return false;
    }

    *paddingStart = 0;
    *paddingEnd = 0;
    if (!padding.empty()) {
        const Range& range = padding.front();
        *paddingStart = range.start;
        *paddingEnd = length - range.end;
    } else if (!stretchRegions.empty()) {
        // No padding was defined. Compute the padding from the first and last
        // stretch regions.
        *paddingStart = stretchRegions.front().start;
        *paddingEnd = length - stretchRegions.back().end;
    }

    if (layoutBounds.size() > 2) {
        std::stringstream errStream;
        errStream << "too many layout bounds sections on " << edgeName << " border";
        *err = errStream.str();
        return false;
    }

    *layoutStart = 0;
    *layoutEnd = 0;
    if (layoutBounds.size() >= 1) {
        const Range& range = layoutBounds.front();
        // If there is only one layout bound segment, it might not start at 0, but then it should
        // end at length.
        if (range.start != 0 && range.end != length) {
            std::stringstream errStream;
            errStream << "layout bounds on " << edgeName << " border must start at edge";
            *err = errStream.str();
            return false;
        }
        *layoutStart = range.end;

        if (layoutBounds.size() >= 2) {
            const Range& range = layoutBounds.back();
            if (range.end != length) {
                std::stringstream errStream;
                errStream << "layout bounds on " << edgeName << " border must start at edge";
                *err = errStream.str();
                return false;
            }
            *layoutEnd = length - range.start;
        }
    }
    return true;
}

static int32_t calculateSegmentCount(const std::vector<Range>& stretchRegions, int32_t length) {
    if (stretchRegions.size() == 0) {
        return 0;
    }

    const bool startIsFixed = stretchRegions.front().start != 0;
    const bool endIsFixed = stretchRegions.back().end != length;
    int32_t modifier = 0;
    if (startIsFixed && endIsFixed) {
        modifier = 1;
    } else if (!startIsFixed && !endIsFixed) {
        modifier = -1;
    }
    return static_cast<int32_t>(stretchRegions.size()) * 2 + modifier;
}

static uint32_t getRegionColor(uint8_t** rows, const Bounds& region) {
    // Sample the first pixel to compare against.
    const uint32_t expectedColor = NinePatch::packRGBA(rows[region.top] + region.left * 4);
    for (int32_t y = region.top; y < region.bottom; y++) {
        const uint8_t* row = rows[y];
        for (int32_t x = region.left; x < region.right; x++) {
            const uint32_t color = NinePatch::packRGBA(row + x * 4);
            if (getAlpha(color) == 0) {
                // The color is transparent.
                // If the expectedColor is not transparent, NO_COLOR.
                if (getAlpha(expectedColor) != 0) {
                    return android::Res_png_9patch::NO_COLOR;
                }
            } else if (color != expectedColor) {
                return android::Res_png_9patch::NO_COLOR;
            }
        }
    }

    if (getAlpha(expectedColor) == 0) {
        return android::Res_png_9patch::TRANSPARENT_COLOR;
    }
    return expectedColor;
}

// Fills outColors with each 9-patch section's colour. If the whole section is transparent,
// it gets the special TRANSPARENT colour. If the whole section is the same colour, it is assigned
// that colour. Otherwise it gets the special NO_COLOR colour.
//
// Note that the rows contain the 9-patch 1px border, and the indices in the stretch regions are
// already offset to exclude the border. This means that each time the rows are accessed,
// the indices must be offset by 1.
//
// width and height also include the 9-patch 1px border.
static void calculateRegionColors(uint8_t** rows,
                                  const std::vector<Range>& horizontalStretchRegions,
                                  const std::vector<Range>& verticalStretchRegions,
                                  const int32_t width, const int32_t height,
                                  std::vector<uint32_t>* outColors) {
    int32_t nextTop = 0;
    Bounds bounds;
    auto rowIter = verticalStretchRegions.begin();
    while (nextTop != height) {
        if (rowIter != verticalStretchRegions.end()) {
            if (nextTop != rowIter->start) {
                // This is a fixed segment.
                // Offset the bounds by 1 to accommodate the border.
                bounds.top = nextTop + 1;
                bounds.bottom = rowIter->start + 1;
                nextTop = rowIter->start;
            } else {
                // This is a stretchy segment.
                // Offset the bounds by 1 to accommodate the border.
                bounds.top = rowIter->start + 1;
                bounds.bottom = rowIter->end + 1;
                nextTop = rowIter->end;
                ++rowIter;
            }
        } else {
            // This is the end, fixed section.
            // Offset the bounds by 1 to accommodate the border.
            bounds.top = nextTop + 1;
            bounds.bottom = height + 1;
            nextTop = height;
         }

        int32_t nextLeft = 0;
        auto colIter = horizontalStretchRegions.begin();
        while (nextLeft != width) {
            if (colIter != horizontalStretchRegions.end()) {
                if (nextLeft != colIter->start) {
                    // This is a fixed segment.
                    // Offset the bounds by 1 to accommodate the border.
                    bounds.left = nextLeft + 1;
                    bounds.right = colIter->start + 1;
                    nextLeft = colIter->start;
                } else {
                    // This is a stretchy segment.
                    // Offset the bounds by 1 to accommodate the border.
                    bounds.left = colIter->start + 1;
                    bounds.right = colIter->end + 1;
                    nextLeft = colIter->end;
                    ++colIter;
                }
            } else {
                // This is the end, fixed section.
                // Offset the bounds by 1 to accommodate the border.
                bounds.left = nextLeft + 1;
                bounds.right = width + 1;
                nextLeft = width;
            }
            outColors->push_back(getRegionColor(rows, bounds));
        }
    }
}

// Calculates the insets of a row/column of pixels based on where the largest alpha value begins
// (on both sides).
template <typename ImageLine>
static void findOutlineInsets(const ImageLine* imageLine, int32_t* outStart, int32_t* outEnd) {
    *outStart = 0;
    *outEnd = 0;

    const int32_t length = imageLine->getLength();
    if (length < 3) {
        return;
    }

    // If the length is odd, we want both sides to process the center pixel,
    // so we use two different midpoints (to account for < and <= in the different loops).
    const int32_t mid2 = length / 2;
    const int32_t mid1 = mid2 + (length % 2);

    uint32_t maxAlpha = 0;
    for (int32_t i = 0; i < mid1 && maxAlpha != 0xff; i++) {
        uint32_t alpha = getAlpha(imageLine->getColor(i));
        if (alpha > maxAlpha) {
            maxAlpha = alpha;
            *outStart = i;
        }
    }

    maxAlpha = 0;
    for (int32_t i = length - 1; i >= mid2 && maxAlpha != 0xff; i--) {
        uint32_t alpha = getAlpha(imageLine->getColor(i));
        if (alpha > maxAlpha) {
            maxAlpha = alpha;
            *outEnd = length - (i + 1);
        }
    }
    return;
}

template <typename ImageLine>
static uint32_t findMaxAlpha(const ImageLine* imageLine) {
    const int32_t length = imageLine->getLength();
    uint32_t maxAlpha = 0;
    for (int32_t idx = 0; idx < length && maxAlpha != 0xff; idx++) {
        uint32_t alpha = getAlpha(imageLine->getColor(idx));
        if (alpha > maxAlpha) {
            maxAlpha = alpha;
        }
    }
    return maxAlpha;
}

// Pack the pixels in as 0xAARRGGBB (as 9-patch expects it).
uint32_t NinePatch::packRGBA(const uint8_t* pixel) {
    return (pixel[3] << 24) | (pixel[0] << 16) | (pixel[1] << 8) | pixel[2];
}

std::unique_ptr<NinePatch> NinePatch::create(uint8_t** rows,
                                             const int32_t width, const int32_t height,
                                             std::string* err) {
    if (width < 3 || height < 3) {
        *err = "image must be at least 3x3 (1x1 image with 1 pixel border)";
        return {};
    }

    std::vector<Range> horizontalPadding;
    std::vector<Range> horizontalOpticalBounds;
    std::vector<Range> verticalPadding;
    std::vector<Range> verticalOpticalBounds;
    std::vector<Range> unexpectedRanges;
    std::unique_ptr<ColorValidator> colorValidator;

    if (rows[0][3] == 0) {
        colorValidator = util::make_unique<TransparentNeutralColorValidator>();
    } else if (packRGBA(rows[0]) == kColorOpaqueWhite) {
        colorValidator = util::make_unique<WhiteNeutralColorValidator>();
    } else {
        *err = "top-left corner pixel must be either opaque white or transparent";
        return {};
    }

    // Private constructor, can't use make_unique.
    auto ninePatch = std::unique_ptr<NinePatch>(new NinePatch());

    HorizontalImageLine topRow(rows, 0, 0, width);
    if (!fillRanges(&topRow, colorValidator.get(), &ninePatch->horizontalStretchRegions,
                    &unexpectedRanges, err)) {
        return {};
    }

    if (!unexpectedRanges.empty()) {
        const Range& range = unexpectedRanges[0];
        std::stringstream errStream;
        errStream << "found unexpected optical bounds (red pixel) on top border "
                << "at x=" << range.start + 1;
        *err = errStream.str();
        return {};
    }

    VerticalImageLine leftCol(rows, 0, 0, height);
    if (!fillRanges(&leftCol, colorValidator.get(), &ninePatch->verticalStretchRegions,
                    &unexpectedRanges, err)) {
        return {};
    }

    if (!unexpectedRanges.empty()) {
        const Range& range = unexpectedRanges[0];
        std::stringstream errStream;
        errStream << "found unexpected optical bounds (red pixel) on left border "
                << "at y=" << range.start + 1;
        return {};
    }

    HorizontalImageLine bottomRow(rows, 0, height - 1, width);
    if (!fillRanges(&bottomRow, colorValidator.get(), &horizontalPadding,
                    &horizontalOpticalBounds, err)) {
        return {};
    }

    if (!populateBounds(horizontalPadding, horizontalOpticalBounds,
                        ninePatch->horizontalStretchRegions, width - 2,
                        &ninePatch->padding.left, &ninePatch->padding.right,
                        &ninePatch->layoutBounds.left, &ninePatch->layoutBounds.right,
                        "bottom", err)) {
        return {};
    }

    VerticalImageLine rightCol(rows, width - 1, 0, height);
    if (!fillRanges(&rightCol, colorValidator.get(), &verticalPadding,
                    &verticalOpticalBounds, err)) {
        return {};
    }

    if (!populateBounds(verticalPadding, verticalOpticalBounds,
                        ninePatch->verticalStretchRegions, height - 2,
                        &ninePatch->padding.top, &ninePatch->padding.bottom,
                        &ninePatch->layoutBounds.top, &ninePatch->layoutBounds.bottom,
                        "right", err)) {
        return {};
    }

    // Fill the region colors of the 9-patch.
    const int32_t numRows = calculateSegmentCount(ninePatch->horizontalStretchRegions, width - 2);
    const int32_t numCols = calculateSegmentCount(ninePatch->verticalStretchRegions, height - 2);
    if ((int64_t) numRows * (int64_t) numCols > 0x7f) {
        *err = "too many regions in 9-patch";
        return {};
    }

    ninePatch->regionColors.reserve(numRows * numCols);
    calculateRegionColors(rows, ninePatch->horizontalStretchRegions,
                          ninePatch->verticalStretchRegions,
                          width - 2, height - 2,
                          &ninePatch->regionColors);

    // Compute the outline based on opacity.

    // Find left and right extent of 9-patch content on center row.
    HorizontalImageLine midRow(rows, 1, height / 2, width - 2);
    findOutlineInsets(&midRow, &ninePatch->outline.left, &ninePatch->outline.right);

    // Find top and bottom extent of 9-patch content on center column.
    VerticalImageLine midCol(rows, width / 2, 1, height - 2);
    findOutlineInsets(&midCol, &ninePatch->outline.top, &ninePatch->outline.bottom);

    const int32_t outlineWidth = (width - 2) - ninePatch->outline.left - ninePatch->outline.right;
    const int32_t outlineHeight = (height - 2) - ninePatch->outline.top - ninePatch->outline.bottom;

    // Find the largest alpha value within the outline area.
    HorizontalImageLine outlineMidRow(rows,
                                      1 + ninePatch->outline.left,
                                      1 + ninePatch->outline.top + (outlineHeight / 2),
                                      outlineWidth);
    VerticalImageLine outlineMidCol(rows,
                                    1 + ninePatch->outline.left + (outlineWidth / 2),
                                    1 + ninePatch->outline.top,
                                    outlineHeight);
    ninePatch->outlineAlpha = std::max(findMaxAlpha(&outlineMidRow), findMaxAlpha(&outlineMidCol));

    // Assuming the image is a round rect, compute the radius by marching
    // diagonally from the top left corner towards the center.
    DiagonalImageLine diagonal(rows, 1 + ninePatch->outline.left, 1 + ninePatch->outline.top,
                               1, 1, std::min(outlineWidth, outlineHeight));
    int32_t topLeft, bottomRight;
    findOutlineInsets(&diagonal, &topLeft, &bottomRight);

    /* Determine source radius based upon inset:
     *     sqrt(r^2 + r^2) = sqrt(i^2 + i^2) + r
     *     sqrt(2) * r = sqrt(2) * i + r
     *     (sqrt(2) - 1) * r = sqrt(2) * i
     *     r = sqrt(2) / (sqrt(2) - 1) * i
     */
    ninePatch->outlineRadius = 3.4142f * topLeft;
    return ninePatch;
}

std::unique_ptr<uint8_t[]> NinePatch::serializeBase(size_t* outLen) const {
    android::Res_png_9patch data;
    data.numXDivs = static_cast<uint8_t>(horizontalStretchRegions.size()) * 2;
    data.numYDivs = static_cast<uint8_t>(verticalStretchRegions.size()) * 2;
    data.numColors = static_cast<uint8_t>(regionColors.size());
    data.paddingLeft = padding.left;
    data.paddingRight = padding.right;
    data.paddingTop = padding.top;
    data.paddingBottom = padding.bottom;

    auto buffer = std::unique_ptr<uint8_t[]>(new uint8_t[data.serializedSize()]);
    android::Res_png_9patch::serialize(data,
                                       (const int32_t*) horizontalStretchRegions.data(),
                                       (const int32_t*) verticalStretchRegions.data(),
                                       regionColors.data(),
                                       buffer.get());
    // Convert to file endianness.
    reinterpret_cast<android::Res_png_9patch*>(buffer.get())->deviceToFile();

    *outLen = data.serializedSize();
    return buffer;
}

std::unique_ptr<uint8_t[]> NinePatch::serializeLayoutBounds(size_t* outLen) const {
    size_t chunkLen = sizeof(uint32_t) * 4;
    auto buffer = std::unique_ptr<uint8_t[]>(new uint8_t[chunkLen]);
    uint8_t* cursor = buffer.get();

    memcpy(cursor, &layoutBounds.left, sizeof(layoutBounds.left));
    cursor += sizeof(layoutBounds.left);

    memcpy(cursor, &layoutBounds.top, sizeof(layoutBounds.top));
    cursor += sizeof(layoutBounds.top);

    memcpy(cursor, &layoutBounds.right, sizeof(layoutBounds.right));
    cursor += sizeof(layoutBounds.right);

    memcpy(cursor, &layoutBounds.bottom, sizeof(layoutBounds.bottom));
    cursor += sizeof(layoutBounds.bottom);

    *outLen = chunkLen;
    return buffer;
}

std::unique_ptr<uint8_t[]> NinePatch::serializeRoundedRectOutline(size_t* outLen) const {
    size_t chunkLen = sizeof(uint32_t) * 6;
    auto buffer = std::unique_ptr<uint8_t[]>(new uint8_t[chunkLen]);
    uint8_t* cursor = buffer.get();

    memcpy(cursor, &outline.left, sizeof(outline.left));
    cursor += sizeof(outline.left);

    memcpy(cursor, &outline.top, sizeof(outline.top));
    cursor += sizeof(outline.top);

    memcpy(cursor, &outline.right, sizeof(outline.right));
    cursor += sizeof(outline.right);

    memcpy(cursor, &outline.bottom, sizeof(outline.bottom));
    cursor += sizeof(outline.bottom);

    *((float*) cursor) = outlineRadius;
    cursor += sizeof(outlineRadius);

    *((uint32_t*) cursor) = outlineAlpha;

    *outLen = chunkLen;
    return buffer;
}

::std::ostream& operator<<(::std::ostream& out, const Range& range) {
    return out << "[" << range.start << ", " << range.end << ")";
}

::std::ostream& operator<<(::std::ostream& out, const Bounds& bounds) {
    return out << "l=" << bounds.left
            << " t=" << bounds.top
            << " r=" << bounds.right
            << " b=" << bounds.bottom;
}

::std::ostream& operator<<(::std::ostream& out, const NinePatch& ninePatch) {
    return out << "horizontalStretch:" << util::joiner(ninePatch.horizontalStretchRegions, " ")
            << " verticalStretch:" << util::joiner(ninePatch.verticalStretchRegions, " ")
            << " padding: " << ninePatch.padding
            << ", bounds: " << ninePatch.layoutBounds
            << ", outline: " << ninePatch.outline
            << " rad=" << ninePatch.outlineRadius
            << " alpha=" << ninePatch.outlineAlpha;
}

} // namespace aapt