Add a mipmap-like divide-by-two image scaling algorithm. I am going to use this

for on-the-fly generated thumbnails.
Review URL: http://codereview.chromium.org/118341

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@17957 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 214 insertions, 7 deletions

diff --git a/skia/ext/image_operations.cc b/skia/ext/image_operations.cc
index c0ee3e0..1924369 100644
--- a/skia/ext/image_operations.cc
+++ b/skia/ext/image_operations.cc
@@ -624,5 +624,86 @@ SkBitmap ImageOperations::CreateTiledBitmap(const SkBitmap& source,
   return cropped;
 }
 
+// static
+SkBitmap ImageOperations::DownsampleByTwo(const SkBitmap& bitmap) {
+  DCHECK(bitmap.getConfig() == SkBitmap::kARGB_8888_Config);
+
+  // Handle the nop case.
+  if (bitmap.width() <= 1 || bitmap.height() <= 1)
+    return bitmap;
+
+  SkBitmap result;
+  result.setConfig(SkBitmap::kARGB_8888_Config,
+                   (bitmap.width() + 1) / 2,
+                   (bitmap.height() + 1) / 2);
+  result.allocPixels();
+
+  SkAutoLockPixels lock(bitmap);
+  for (int dest_y = 0; dest_y < result.height(); dest_y++) {
+    for (int dest_x = 0; dest_x < result.width(); dest_x++ ) {
+      // This code is based on downsampleby2_proc32 in SkBitmap.cpp. It is very
+      // clever in that it does two channels at once: alpha and green ("ag")
+      // and red and blue ("rb"). Each channel gets averaged across 4 pixels
+      // to get the result.
+      int src_x = dest_x << 1;
+      int src_y = dest_y << 1;
+      const SkPMColor* cur_src = bitmap.getAddr32(src_x, src_y);
+      SkPMColor tmp, ag, rb;
+
+      // Top left pixel of the 2x2 block.
+      tmp = *cur_src;
+      ag = (tmp >> 8) & 0xFF00FF;
+      rb = tmp & 0xFF00FF;
+      if (src_x < bitmap.width() - 1)
+        cur_src += 1;
+
+      // Top right pixel of the 2x2 block.
+      tmp = *cur_src;
+      ag += (tmp >> 8) & 0xFF00FF;
+      rb += tmp & 0xFF00FF;
+      if (src_y < bitmap.height() - 1)
+        cur_src = bitmap.getAddr32(src_x, src_y + 1);
+      else
+        cur_src = bitmap.getAddr32(src_x, src_y);  // Move back to the first.
+
+      // Bottom left pixel of the 2x2 block.
+      tmp = *cur_src;
+      ag += (tmp >> 8) & 0xFF00FF;
+      rb += tmp & 0xFF00FF;
+      if (src_x < bitmap.width() - 1)
+        cur_src += 1;
+
+      // Bottom right pixel of the 2x2 block.
+      tmp = *cur_src;
+      ag += (tmp >> 8) & 0xFF00FF;
+      rb += tmp & 0xFF00FF;
+
+      // PUt the channels back together, dividing each by 4 to get the average.
+      // |ag| has the alpha and green channels shifted right by 8 bits from
+      // there they should end up, so shifting left by 6 gives them in the
+      // correct position divided by 4.
+      *result.getAddr32(dest_x, dest_y) =
+          ((rb >> 2) & 0xFF00FF) | ((ag << 6) & 0xFF00FF00);
+    }
+  }
+
+  return result;
+}
+
+// static
+SkBitmap ImageOperations::DownsampleByTwoUntilSize(const SkBitmap& bitmap,
+                                                   int min_w, int min_h) {
+  if (bitmap.width() <= min_w || bitmap.height() <= min_h ||
+      min_w < 0 || min_h < 0)
+    return bitmap;
+
+  // Since bitmaps are refcounted, this copy will be fast.
+  SkBitmap current = bitmap;
+  while (current.width() >= min_w * 2 && current.height() >= min_h * 2 &&
+         current.width() > 1 && current.height() > 1)
+    current = DownsampleByTwo(current);
+  return current;
+}
+
 }  // namespace skia
 
diff --git a/skia/ext/image_operations.h b/skia/ext/image_operations.h
index 4e3c93e..3b172c8 100644
--- a/skia/ext/image_operations.h
+++ b/skia/ext/image_operations.h
@@ -61,9 +61,9 @@ class ImageOperations {
   static SkBitmap CreateMaskedBitmap(const SkBitmap& first,
                                      const SkBitmap& alpha);
 
-  // We create a button background image by compositing the color and image 
-  // together, then applying the mask. This is a highly specialized composite 
-  // operation that is the equivalent of drawing a background in |color|, 
+  // We create a button background image by compositing the color and image
+  // together, then applying the mask. This is a highly specialized composite
+  // operation that is the equivalent of drawing a background in |color|,
   // tiling |image| over the top, and then masking the result out with |mask|.
   // The images must use kARGB_8888_Config config.
   static SkBitmap CreateButtonBackground(SkColor color,
@@ -74,17 +74,17 @@ class ImageOperations {
   // by |blur_amount|. The blur will wrap around image edges.
   static SkBitmap CreateBlurredBitmap(const SkBitmap& bitmap, int blur_amount);
 
-  // Shift a bitmap's HSL values. The shift values are in the range of 0-1, 
-  // with the option to specify -1 for 'no change'. The shift values are 
+  // Shift a bitmap's HSL values. The shift values are in the range of 0-1,
+  // with the option to specify -1 for 'no change'. The shift values are
   // defined as:
   // hsl_shift[0] (hue): The absolute hue value for the image - 0 and 1 map
   //    to 0 and 360 on the hue color wheel (red).
-  // hsl_shift[1] (saturation): A saturation shift for the image, with the 
+  // hsl_shift[1] (saturation): A saturation shift for the image, with the
   //    following key values:
   //    0 = remove all color.
   //    0.5 = leave unchanged.
   //    1 = fully saturate the image.
-  // hsl_shift[2] (lightness): A lightness shift for the image, with the 
+  // hsl_shift[2] (lightness): A lightness shift for the image, with the
   //    following key values:
   //    0 = remove all lightness (make all pixels black).
   //    0.5 = leave unchanged.
@@ -98,6 +98,19 @@ class ImageOperations {
   static SkBitmap CreateTiledBitmap(const SkBitmap& bitmap,
                                     int src_x, int src_y,
                                     int dst_w, int dst_h);
+
+  // Makes a bitmap half has large in each direction by averaging groups of
+  // 4 pixels. This is one step in generating a mipmap.
+  static SkBitmap DownsampleByTwo(const SkBitmap& bitmap);
+
+  // Iteratively downsamples by 2 until the bitmap is no smaller than the
+  // input size. The normal use of this is to downsample the bitmap "close" to
+  // the final size, and then use traditional resampling on the result.
+  // Because the bitmap will be closer to the final size, it will be faster,
+  // and linear interpolation will generally work well as a second step.
+  static SkBitmap DownsampleByTwoUntilSize(const SkBitmap& bitmap,
+                                           int min_w, int min_h);
+
  private:
   ImageOperations();  // Class for scoping only.
 };
diff --git a/skia/ext/image_operations_unittest.cc b/skia/ext/image_operations_unittest.cc
index 06bd4fc..3699685 100644
--- a/skia/ext/image_operations_unittest.cc
+++ b/skia/ext/image_operations_unittest.cc
@@ -399,3 +399,116 @@ TEST(ImageOperations, CreateCroppedBitmapWrapping) {
   }
 }
 
+TEST(ImageOperations, DownsampleByTwo) {
+  // Use an odd-sized bitmap to make sure the edge cases where there isn't a
+  // 2x2 block of pixels is handled correctly.
+  // Here's the ARGB example
+  //
+  //    50% transparent green             opaque 50% blue           white
+  //        80008000                         FF000080              FFFFFFFF
+  //
+  //    50% transparent red               opaque 50% gray           black
+  //        80800000                         80808080              FF000000
+  //
+  //         black                            white                50% gray
+  //        FF000000                         FFFFFFFF              FF808080
+  //
+  // The result of this computation should be:
+  //        A0404040  FF808080
+  //        FF808080  FF808080
+  SkBitmap input;
+  input.setConfig(SkBitmap::kARGB_8888_Config, 3, 3);
+  input.allocPixels();
+
+  // The color order may be different, but we don't care (the channels are
+  // trated the same).
+  *input.getAddr32(0, 0) = 0x80008000;
+  *input.getAddr32(1, 0) = 0xFF000080;
+  *input.getAddr32(2, 0) = 0xFFFFFFFF;
+  *input.getAddr32(0, 1) = 0x80800000;
+  *input.getAddr32(1, 1) = 0x80808080;
+  *input.getAddr32(2, 1) = 0xFF000000;
+  *input.getAddr32(0, 2) = 0xFF000000;
+  *input.getAddr32(1, 2) = 0xFFFFFFFF;
+  *input.getAddr32(2, 2) = 0xFF808080;
+
+  SkBitmap result = skia::ImageOperations::DownsampleByTwo(input);
+  EXPECT_EQ(2, result.width());
+  EXPECT_EQ(2, result.height());
+
+  // Some of the values are off-by-one due to rounding.
+  SkAutoLockPixels lock(result);
+  EXPECT_EQ(0x9f404040, *result.getAddr32(0, 0));
+  EXPECT_EQ(0xFF7f7f7f, *result.getAddr32(1, 0));
+  EXPECT_EQ(0xFF7f7f7f, *result.getAddr32(0, 1));
+  EXPECT_EQ(0xFF808080, *result.getAddr32(1, 1));
+}
+
+// Test edge cases for DownsampleByTwo.
+TEST(ImageOperations, DownsampleByTwoSmall) {
+  SkPMColor reference = 0xFF4080FF;
+
+  // Test a 1x1 bitmap.
+  SkBitmap one_by_one;
+  one_by_one.setConfig(SkBitmap::kARGB_8888_Config, 1, 1);
+  one_by_one.allocPixels();
+  *one_by_one.getAddr32(0, 0) = reference;
+  SkBitmap result = skia::ImageOperations::DownsampleByTwo(one_by_one);
+  SkAutoLockPixels lock1(result);
+  EXPECT_EQ(1, result.width());
+  EXPECT_EQ(1, result.height());
+  EXPECT_EQ(reference, *result.getAddr32(0, 0));
+
+  // Test an n by 1 bitmap.
+  SkBitmap one_by_n;
+  one_by_n.setConfig(SkBitmap::kARGB_8888_Config, 300, 1);
+  one_by_n.allocPixels();
+  result = skia::ImageOperations::DownsampleByTwo(one_by_n);
+  SkAutoLockPixels lock2(result);
+  EXPECT_EQ(300, result.width());
+  EXPECT_EQ(1, result.height());
+
+  // Test a 1 by n bitmap.
+  SkBitmap n_by_one;
+  n_by_one.setConfig(SkBitmap::kARGB_8888_Config, 1, 300);
+  n_by_one.allocPixels();
+  result = skia::ImageOperations::DownsampleByTwo(n_by_one);
+  SkAutoLockPixels lock3(result);
+  EXPECT_EQ(1, result.width());
+  EXPECT_EQ(300, result.height());
+
+  // Test an empty bitmap
+  SkBitmap empty;
+  result = skia::ImageOperations::DownsampleByTwo(empty);
+  EXPECT_TRUE(result.isNull());
+  EXPECT_EQ(0, result.width());
+  EXPECT_EQ(0, result.height());
+}
+
+// Here we assume DownsampleByTwo works correctly (it's tested above) and
+// just make sure that the 
+TEST(ImageOperations, DownsampleByTwoUntilSize) {
+  // First make sure a "too small" bitmap doesn't get modified at all.
+  SkBitmap too_small;
+  too_small.setConfig(SkBitmap::kARGB_8888_Config, 10, 10);
+  too_small.allocPixels();
+  SkBitmap result = skia::ImageOperations::DownsampleByTwoUntilSize(
+      too_small, 16, 16);
+  EXPECT_EQ(10, result.width());
+  EXPECT_EQ(10, result.height());
+
+  // Now make sure giving it a 0x0 target returns something reasonable.
+  result = skia::ImageOperations::DownsampleByTwoUntilSize(too_small, 0, 0);
+  EXPECT_EQ(1, result.width());
+  EXPECT_EQ(1, result.height());
+
+  // Test multiple steps of downsampling.
+  SkBitmap large;
+  large.setConfig(SkBitmap::kARGB_8888_Config, 100, 43);
+  large.allocPixels();
+  result = skia::ImageOperations::DownsampleByTwoUntilSize(large, 6, 6);
+
+  // The result should be divided in half 100x43 -> 50x22 -> 25x11
+  EXPECT_EQ(25, result.width());
+  EXPECT_EQ(11, result.height());
+}
\ No newline at end of file