tools/aapt2/compile/NinePatch.cpp - SHIFTPHONES/android_frameworks_base - Gitiles

 /*
  * 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
	/*
	* 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