The Tor Browser / file revision

 // Copyright (c) 2006-2012 The Chromium Authors. All rights reserved.

 //

 // Redistribution and use in source and binary forms, with or without

 // modification, are permitted provided that the following conditions

 // are met:

 //  * Redistributions of source code must retain the above copyright

 //    notice, this list of conditions and the following disclaimer.

 //  * Redistributions in binary form must reproduce the above copyright

 //    notice, this list of conditions and the following disclaimer in

 //    the documentation and/or other materials provided with the

 //    distribution.

 //  * Neither the name of Google, Inc. nor the names of its contributors

 //    may be used to endorse or promote products derived from this

 //    software without specific prior written permission.

 //

 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS

 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE

 // COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,

 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,

 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS

 // OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED

 // AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,

 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT

 // OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF

 // SUCH DAMAGE.

 #include "base/basictypes.h"

 #define _USE_MATH_DEFINES

 #include <algorithm>

 #include <cmath>

 #include <limits>

 #include "image_operations.h"

 #include "base/stack_container.h"

 #include "convolver.h"

 #include "skia/SkColorPriv.h"

 #include "skia/SkBitmap.h"

 #include "skia/SkRect.h"

 #include "skia/SkFontHost.h"

 namespace skia {

 namespace {

 // Returns the ceiling/floor as an integer.

 inline int CeilInt(float val) {

   return static_cast<int>(ceil(val));

 }

 inline int FloorInt(float val) {

   return static_cast<int>(floor(val));

 }

 // Filter function computation -------------------------------------------------

 // Evaluates the box filter, which goes from -0.5 to +0.5.

 float EvalBox(float x) {

   return (x >= -0.5f && x < 0.5f) ? 1.0f : 0.0f;

 }

 // Evaluates the Lanczos filter of the given filter size window for the given

 // position.

 //

 // |filter_size| is the width of the filter (the "window"), outside of which

 // the value of the function is 0. Inside of the window, the value is the

 // normalized sinc function:

 //   lanczos(x) = sinc(x) * sinc(x / filter_size);

 // where

 //   sinc(x) = sin(pi*x) / (pi*x);

 float EvalLanczos(int filter_size, float x) {

   if (x <= -filter_size || x >= filter_size)

     return 0.0f;  // Outside of the window.

   if (x > -std::numeric_limits<float>::epsilon() &&

       x < std::numeric_limits<float>::epsilon())

     return 1.0f;  // Special case the discontinuity at the origin.

   float xpi = x * static_cast<float>(M_PI);

   return (sin(xpi) / xpi) *  // sinc(x)

           sin(xpi / filter_size) / (xpi / filter_size);  // sinc(x/filter_size)

 }

 // Evaluates the Hamming filter of the given filter size window for the given

 // position.

 //

 // The filter covers [-filter_size, +filter_size]. Outside of this window

 // the value of the function is 0. Inside of the window, the value is sinus

 // cardinal multiplied by a recentered Hamming function. The traditional

 // Hamming formula for a window of size N and n ranging in [0, N-1] is:

 //   hamming(n) = 0.54 - 0.46 * cos(2 * pi * n / (N-1)))

 // In our case we want the function centered for x == 0 and at its minimum

 // on both ends of the window (x == +/- filter_size), hence the adjusted

 // formula:

 //   hamming(x) = (0.54 -

 //                 0.46 * cos(2 * pi * (x - filter_size)/ (2 * filter_size)))

 //              = 0.54 - 0.46 * cos(pi * x / filter_size - pi)

 //              = 0.54 + 0.46 * cos(pi * x / filter_size)

 float EvalHamming(int filter_size, float x) {

   if (x <= -filter_size || x >= filter_size)

     return 0.0f;  // Outside of the window.

   if (x > -std::numeric_limits<float>::epsilon() &&

       x < std::numeric_limits<float>::epsilon())

     return 1.0f;  // Special case the sinc discontinuity at the origin.

   const float xpi = x * static_cast<float>(M_PI);

   return ((sin(xpi) / xpi) *  // sinc(x)

           (0.54f + 0.46f * cos(xpi / filter_size)));  // hamming(x)

 }

 // ResizeFilter ----------------------------------------------------------------

 // Encapsulates computation and storage of the filters required for one complete

 // resize operation.

 class ResizeFilter {

  public:

   ResizeFilter(ImageOperations::ResizeMethod method,

                int src_full_width, int src_full_height,

                int dest_width, int dest_height,

                const SkIRect& dest_subset);

   // Returns the filled filter values.

   const ConvolutionFilter1D& x_filter() { return x_filter_; }

   const ConvolutionFilter1D& y_filter() { return y_filter_; }

  private:

   // Returns the number of pixels that the filer spans, in filter space (the

   // destination image).

   float GetFilterSupport(float scale) {

     switch (method_) {

       case ImageOperations::RESIZE_BOX:

         // The box filter just scales with the image scaling.

         return 0.5f;  // Only want one side of the filter = /2.

       case ImageOperations::RESIZE_HAMMING1:

         // The Hamming filter takes as much space in the source image in

         // each direction as the size of the window = 1 for Hamming1.

         return 1.0f;

       case ImageOperations::RESIZE_LANCZOS2:

         // The Lanczos filter takes as much space in the source image in

         // each direction as the size of the window = 2 for Lanczos2.

         return 2.0f;

       case ImageOperations::RESIZE_LANCZOS3:

         // The Lanczos filter takes as much space in the source image in

         // each direction as the size of the window = 3 for Lanczos3.

         return 3.0f;

       default:

         return 1.0f;

     }

   }

   // Computes one set of filters either horizontally or vertically. The caller

   // will specify the "min" and "max" rather than the bottom/top and

   // right/bottom so that the same code can be re-used in each dimension.

   //

   // |src_depend_lo| and |src_depend_size| gives the range for the source

   // depend rectangle (horizontally or vertically at the caller's discretion

   // -- see above for what this means).

   //

   // Likewise, the range of destination values to compute and the scale factor

   // for the transform is also specified.

   void ComputeFilters(int src_size,

                       int dest_subset_lo, int dest_subset_size,

                       float scale, float src_support,

                       ConvolutionFilter1D* output);

   // Computes the filter value given the coordinate in filter space.

   inline float ComputeFilter(float pos) {

     switch (method_) {

       case ImageOperations::RESIZE_BOX:

         return EvalBox(pos);

       case ImageOperations::RESIZE_HAMMING1:

         return EvalHamming(1, pos);

       case ImageOperations::RESIZE_LANCZOS2:

         return EvalLanczos(2, pos);

       case ImageOperations::RESIZE_LANCZOS3:

         return EvalLanczos(3, pos);

       default:

         return 0;

     }

   }

   ImageOperations::ResizeMethod method_;

   // Size of the filter support on one side only in the destination space.

   // See GetFilterSupport.

   float x_filter_support_;

   float y_filter_support_;

   // Subset of scaled destination bitmap to compute.

   SkIRect out_bounds_;

   ConvolutionFilter1D x_filter_;

   ConvolutionFilter1D y_filter_;

   DISALLOW_COPY_AND_ASSIGN(ResizeFilter);

 };

 ResizeFilter::ResizeFilter(ImageOperations::ResizeMethod method,

                            int src_full_width, int src_full_height,

                            int dest_width, int dest_height,

                            const SkIRect& dest_subset)

     : method_(method),

       out_bounds_(dest_subset) {

   // method_ will only ever refer to an "algorithm method".

   SkASSERT((ImageOperations::RESIZE_FIRST_ALGORITHM_METHOD <= method) &&

            (method <= ImageOperations::RESIZE_LAST_ALGORITHM_METHOD));

   float scale_x = static_cast<float>(dest_width) /

                   static_cast<float>(src_full_width);

   float scale_y = static_cast<float>(dest_height) /

                   static_cast<float>(src_full_height);

   x_filter_support_ = GetFilterSupport(scale_x);

   y_filter_support_ = GetFilterSupport(scale_y);

   // Support of the filter in source space.

   float src_x_support = x_filter_support_ / scale_x;

   float src_y_support = y_filter_support_ / scale_y;

   ComputeFilters(src_full_width, dest_subset.fLeft, dest_subset.width(),

                  scale_x, src_x_support, &x_filter_);

   ComputeFilters(src_full_height, dest_subset.fTop, dest_subset.height(),

                  scale_y, src_y_support, &y_filter_);

 }

 // TODO(egouriou): Take advantage of periods in the convolution.

 // Practical resizing filters are periodic outside of the border area.

 // For Lanczos, a scaling by a (reduced) factor of p/q (q pixels in the

 // source become p pixels in the destination) will have a period of p.

 // A nice consequence is a period of 1 when downscaling by an integral

 // factor. Downscaling from typical display resolutions is also bound

 // to produce interesting periods as those are chosen to have multiple

 // small factors.

 // Small periods reduce computational load and improve cache usage if

 // the coefficients can be shared. For periods of 1 we can consider

 // loading the factors only once outside the borders.

 void ResizeFilter::ComputeFilters(int src_size,

                                   int dest_subset_lo, int dest_subset_size,

                                   float scale, float src_support,

                                   ConvolutionFilter1D* output) {

   int dest_subset_hi = dest_subset_lo + dest_subset_size;  // [lo, hi)

   // When we're doing a magnification, the scale will be larger than one. This

   // means the destination pixels are much smaller than the source pixels, and

   // that the range covered by the filter won't necessarily cover any source

   // pixel boundaries. Therefore, we use these clamped values (max of 1) for

   // some computations.

   float clamped_scale = std::min(1.0f, scale);

   // Speed up the divisions below by turning them into multiplies.

   float inv_scale = 1.0f / scale;

   StackVector<float, 64> filter_values;

   StackVector<int16_t, 64> fixed_filter_values;

   // Loop over all pixels in the output range. We will generate one set of

   // filter values for each one. Those values will tell us how to blend the

   // source pixels to compute the destination pixel.

   for (int dest_subset_i = dest_subset_lo; dest_subset_i < dest_subset_hi;

        dest_subset_i++) {

     // Reset the arrays. We don't declare them inside so they can re-use the

     // same malloc-ed buffer.

     filter_values->clear();

     fixed_filter_values->clear();

     // This is the pixel in the source directly under the pixel in the dest.

     // Note that we base computations on the "center" of the pixels. To see

     // why, observe that the destination pixel at coordinates (0, 0) in a 5.0x

     // downscale should "cover" the pixels around the pixel with *its center*

     // at coordinates (2.5, 2.5) in the source, not those around (0, 0).

     // Hence we need to scale coordinates (0.5, 0.5), not (0, 0).

     float src_pixel = (static_cast<float>(dest_subset_i) + 0.5f) * inv_scale;

     // Compute the (inclusive) range of source pixels the filter covers.

     int src_begin = std::max(0, FloorInt(src_pixel - src_support));

     int src_end = std::min(src_size - 1, CeilInt(src_pixel + src_support));

     // Compute the unnormalized filter value at each location of the source

     // it covers.

     float filter_sum = 0.0f;  // Sub of the filter values for normalizing.

     for (int cur_filter_pixel = src_begin; cur_filter_pixel <= src_end;

          cur_filter_pixel++) {

       // Distance from the center of the filter, this is the filter coordinate

       // in source space. We also need to consider the center of the pixel

       // when comparing distance against 'src_pixel'. In the 5x downscale

       // example used above the distance from the center of the filter to

       // the pixel with coordinates (2, 2) should be 0, because its center

       // is at (2.5, 2.5).

       float src_filter_dist =

            ((static_cast<float>(cur_filter_pixel) + 0.5f) - src_pixel);

       // Since the filter really exists in dest space, map it there.

       float dest_filter_dist = src_filter_dist * clamped_scale;

       // Compute the filter value at that location.

       float filter_value = ComputeFilter(dest_filter_dist);

       filter_values->push_back(filter_value);

       filter_sum += filter_value;

     }

     // The filter must be normalized so that we don't affect the brightness of

     // the image. Convert to normalized fixed point.

     int16_t fixed_sum = 0;

     for (size_t i = 0; i < filter_values->size(); i++) {

       int16_t cur_fixed = output->FloatToFixed(filter_values[i] / filter_sum);

       fixed_sum += cur_fixed;

       fixed_filter_values->push_back(cur_fixed);

     }

     // The conversion to fixed point will leave some rounding errors, which

     // we add back in to avoid affecting the brightness of the image. We

     // arbitrarily add this to the center of the filter array (this won't always

     // be the center of the filter function since it could get clipped on the

     // edges, but it doesn't matter enough to worry about that case).

     int16_t leftovers = output->FloatToFixed(1.0f) - fixed_sum;

     fixed_filter_values[fixed_filter_values->size() / 2] += leftovers;

     // Now it's ready to go.

     output->AddFilter(src_begin, &fixed_filter_values[0],

                       static_cast<int>(fixed_filter_values->size()));

   }

   output->PaddingForSIMD(8);

 }

 ImageOperations::ResizeMethod ResizeMethodToAlgorithmMethod(

     ImageOperations::ResizeMethod method) {

   // Convert any "Quality Method" into an "Algorithm Method"

   if (method >= ImageOperations::RESIZE_FIRST_ALGORITHM_METHOD &&

       method <= ImageOperations::RESIZE_LAST_ALGORITHM_METHOD) {

     return method;

   }

   // The call to ImageOperationsGtv::Resize() above took care of

   // GPU-acceleration in the cases where it is possible. So now we just

   // pick the appropriate software method for each resize quality.

   switch (method) {

     // Users of RESIZE_GOOD are willing to trade a lot of quality to

     // get speed, allowing the use of linear resampling to get hardware

     // acceleration (SRB). Hence any of our "good" software filters

     // will be acceptable, and we use the fastest one, Hamming-1.

     case ImageOperations::RESIZE_GOOD:

       // Users of RESIZE_BETTER are willing to trade some quality in order

       // to improve performance, but are guaranteed not to devolve to a linear

       // resampling. In visual tests we see that Hamming-1 is not as good as

       // Lanczos-2, however it is about 40% faster and Lanczos-2 itself is

       // about 30% faster than Lanczos-3. The use of Hamming-1 has been deemed

       // an acceptable trade-off between quality and speed.

     case ImageOperations::RESIZE_BETTER:

       return ImageOperations::RESIZE_HAMMING1;

     default:

       return ImageOperations::RESIZE_LANCZOS3;

   }

 }

 }  // namespace

 // Resize ----------------------------------------------------------------------

 // static

 SkBitmap ImageOperations::Resize(const SkBitmap& source,

                                  ResizeMethod method,

                                  int dest_width, int dest_height,

                                  const SkIRect& dest_subset,

                                  void* dest_pixels /* = nullptr */) {

   if (method == ImageOperations::RESIZE_SUBPIXEL)

     return ResizeSubpixel(source, dest_width, dest_height, dest_subset);

   else

     return ResizeBasic(source, method, dest_width, dest_height, dest_subset,

                        dest_pixels);

 }

 // static

 SkBitmap ImageOperations::ResizeSubpixel(const SkBitmap& source,

                                          int dest_width, int dest_height,

                                          const SkIRect& dest_subset) {

   // Currently only works on Linux/BSD because these are the only platforms

   // where SkFontHost::GetSubpixelOrder is defined.

 #if defined(XP_UNIX)

   // Understand the display.

   const SkFontHost::LCDOrder order = SkFontHost::GetSubpixelOrder();

   const SkFontHost::LCDOrientation orientation =

       SkFontHost::GetSubpixelOrientation();

   // Decide on which dimension, if any, to deploy subpixel rendering.

   int w = 1;

   int h = 1;

   switch (orientation) {

     case SkFontHost::kHorizontal_LCDOrientation:

       w = dest_width < source.width() ? 3 : 1;

       break;

     case SkFontHost::kVertical_LCDOrientation:

       h = dest_height < source.height() ? 3 : 1;

       break;

   }

   // Resize the image.

   const int width = dest_width * w;

   const int height = dest_height * h;

   SkIRect subset = { dest_subset.fLeft, dest_subset.fTop,

                      dest_subset.fLeft + dest_subset.width() * w,

                      dest_subset.fTop + dest_subset.height() * h };

   SkBitmap img = ResizeBasic(source, ImageOperations::RESIZE_LANCZOS3, width,

                              height, subset);

   const int row_words = img.rowBytes() / 4;

   if (w == 1 && h == 1)

     return img;

   // Render into subpixels.

   SkBitmap result;

   result.setConfig(SkBitmap::kARGB_8888_Config, dest_subset.width(),

                    dest_subset.height());

   result.allocPixels();

   if (!result.readyToDraw())

     return img;

   SkAutoLockPixels locker(img);

   if (!img.readyToDraw())

     return img;

   uint32_t* src_row = img.getAddr32(0, 0);

   uint32_t* dst_row = result.getAddr32(0, 0);

   for (int y = 0; y < dest_subset.height(); y++) {

     uint32_t* src = src_row;

     uint32_t* dst = dst_row;

     for (int x = 0; x < dest_subset.width(); x++, src += w, dst++) {

       uint8_t r = 0, g = 0, b = 0, a = 0;

       switch (order) {

         case SkFontHost::kRGB_LCDOrder:

           switch (orientation) {

             case SkFontHost::kHorizontal_LCDOrientation:

               r = SkGetPackedR32(src[0]);

               g = SkGetPackedG32(src[1]);

               b = SkGetPackedB32(src[2]);

               a = SkGetPackedA32(src[1]);

               break;

             case SkFontHost::kVertical_LCDOrientation:

               r = SkGetPackedR32(src[0 * row_words]);

               g = SkGetPackedG32(src[1 * row_words]);

               b = SkGetPackedB32(src[2 * row_words]);

               a = SkGetPackedA32(src[1 * row_words]);

               break;

           }

           break;

         case SkFontHost::kBGR_LCDOrder:

           switch (orientation) {

             case SkFontHost::kHorizontal_LCDOrientation:

               b = SkGetPackedB32(src[0]);

               g = SkGetPackedG32(src[1]);

               r = SkGetPackedR32(src[2]);

               a = SkGetPackedA32(src[1]);

               break;

             case SkFontHost::kVertical_LCDOrientation:

               b = SkGetPackedB32(src[0 * row_words]);

               g = SkGetPackedG32(src[1 * row_words]);

               r = SkGetPackedR32(src[2 * row_words]);

               a = SkGetPackedA32(src[1 * row_words]);

               break;

           }

           break;

         case SkFontHost::kNONE_LCDOrder:

           break;

       }

       // Premultiplied alpha is very fragile.

       a = a > r ? a : r;

       a = a > g ? a : g;

       a = a > b ? a : b;

       *dst = SkPackARGB32(a, r, g, b);

     }

     src_row += h * row_words;

     dst_row += result.rowBytes() / 4;

   }

   result.setAlphaType(img.alphaType());

   return result;

 #else

   return SkBitmap();

 #endif  // OS_POSIX && !OS_MACOSX && !defined(OS_ANDROID)

 }

 // static

 SkBitmap ImageOperations::ResizeBasic(const SkBitmap& source,

                                       ResizeMethod method,

                                       int dest_width, int dest_height,

                                       const SkIRect& dest_subset,

                                       void* dest_pixels /* = nullptr */) {

   // Ensure that the ResizeMethod enumeration is sound.

   SkASSERT(((RESIZE_FIRST_QUALITY_METHOD <= method) &&

             (method <= RESIZE_LAST_QUALITY_METHOD)) ||

            ((RESIZE_FIRST_ALGORITHM_METHOD <= method) &&

             (method <= RESIZE_LAST_ALGORITHM_METHOD)));

   // If the size of source or destination is 0, i.e. 0x0, 0xN or Nx0, just

   // return empty.

   if (source.width() < 1 || source.height() < 1 ||

       dest_width < 1 || dest_height < 1)

     return SkBitmap();

   method = ResizeMethodToAlgorithmMethod(method);

   // Check that we deal with an "algorithm methods" from this point onward.

   SkASSERT((ImageOperations::RESIZE_FIRST_ALGORITHM_METHOD <= method) &&

            (method <= ImageOperations::RESIZE_LAST_ALGORITHM_METHOD));

   SkAutoLockPixels locker(source);

   if (!source.readyToDraw())

       return SkBitmap();

   ResizeFilter filter(method, source.width(), source.height(),

                       dest_width, dest_height, dest_subset);

   // Get a source bitmap encompassing this touched area. We construct the

   // offsets and row strides such that it looks like a new bitmap, while

   // referring to the old data.

   const uint8_t* source_subset =

       reinterpret_cast<const uint8_t*>(source.getPixels());

   // Convolve into the result.

   SkBitmap result;

   result.setConfig(SkBitmap::kARGB_8888_Config,

                    dest_subset.width(), dest_subset.height());

   if (dest_pixels) {

     result.setPixels(dest_pixels);

   } else {

     result.allocPixels();

   }

   if (!result.readyToDraw())

     return SkBitmap();

   BGRAConvolve2D(source_subset, static_cast<int>(source.rowBytes()),

                  !source.isOpaque(), filter.x_filter(), filter.y_filter(),

                  static_cast<int>(result.rowBytes()),

                  static_cast<unsigned char*>(result.getPixels()),

                  /* sse = */ false);

   // Preserve the "opaque" flag for use as an optimization later.

   result.setAlphaType(source.alphaType());

   return result;

 }

 // static

 SkBitmap ImageOperations::Resize(const SkBitmap& source,

                                  ResizeMethod method,

                                  int dest_width, int dest_height,

                                  void* dest_pixels /* = nullptr */) {

   SkIRect dest_subset = { 0, 0, dest_width, dest_height };

   return Resize(source, method, dest_width, dest_height, dest_subset,

                 dest_pixels);

 }

 }  // namespace skia