[gtk+] gtkcairoblur: Replace our exponential blur with the box blur from mutter

[Matthias Clasen <matthiasc src gnome org>]

commit f5d8f75c0fcc73420393ee3ebe401d8b8a03298b
Author: Jasper St. Pierre <jstpierre mecheye net>
Date:   Wed Jul 30 12:26:08 2014 +0200

    gtkcairoblur: Replace our exponential blur with the box blur from mutter
    
    https://bugzilla.gnome.org/show_bug.cgi?id=734053

 gtk/gtkcairoblur.c |  299 ++++++++++++++++++++++++++--------------------------
 1 files changed, 149 insertions(+), 150 deletions(-)
---
diff --git a/gtk/gtkcairoblur.c b/gtk/gtkcairoblur.c
index 7b1fa18..b4473ec 100644
--- a/gtk/gtkcairoblur.c
+++ b/gtk/gtkcairoblur.c
@@ -1,171 +1,172 @@
 /*
- * Copyright (C) 2012 Canonical Ltd
+ * Copyright (C) 2014 Red Hat
  *
- * This  library is free  software; you can  redistribute it and/or
- * modify it  under  the terms  of the  GNU Lesser  General  Public
- * License  as published  by the Free  Software  Foundation; either
- * version 2 of the License, or (at your option) any later version.
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
  *
- * This library is distributed  in the hope that it will be useful,
- * but  WITHOUT ANY WARRANTY; without even  the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * Lesser General Public License for more details.
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
  *
- * You should have received a copy of the GNU Lesser General Public
- * License  along  with  this library;  if not,  write to  the Free
- * Software Foundation, Inc., 51  Franklin St, Fifth Floor, Boston,
- * MA 02110-1301, USA.
- *
- * Authored by Andrea Cimitan <andrea cimitan canonical com>
- * Original code from Mirco Mueller <mirco mueller canonical com>
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ * 02111-1307, USA.
  *
+ * Written by:
+ *     Jasper St. Pierre <jstpierre mecheye net>
+ *     Owen Taylor <otaylor redhat com>
  */
 
 #include "gtkcairoblurprivate.h"
 
 #include <math.h>
+#include <string.h>
 
-/*
- * Notes:
- *   based on exponential-blur algorithm by Jani Huhtanen
+/* This applies a single box blur pass to a horizontal range of pixels;
+ * since the box blur has the same weight for all pixels, we can
+ * implement an efficient sliding window algorithm where we add
+ * in pixels coming into the window from the right and remove
+ * them when they leave the windw to the left.
+ *
+ * d is the filter width; for even d shift indicates how the blurred
+ * result is aligned with the original - does ' x ' go to ' yy' (shift=1)
+ * or 'yy ' (shift=-1)
  */
-static inline void
-_blurinner (guchar* pixel,
-            gint   *zA,
-            gint    alpha,
-            gint    aprec,
-            gint    zprec)
+static void
+blur_xspan (guchar *row,
+            guchar *tmp_buffer,
+            int     row_width,
+            int     d,
+            int     shift)
+{
+  int offset;
+  int sum = 0;
+  int i;
+
+  if (d % 2 == 1)
+    offset = d / 2;
+  else
+    offset = (d - shift) / 2;
+
+  /* All the conditionals in here look slow, but the branches will
+   * be well predicted and there are enough different possibilities
+   * that trying to write this as a series of unconditional loops
+   * is hard and not an obvious win. The main slow down here seems
+   * to be the integer division for pixel; one possible optimization
+   * would be to accumulate into two 16-bit integer buffers and
+   * only divide down after all three passes. (SSE parallel implementation
+   * of the divide step is possible.)
+   */
+  for (i = -d + offset; i < row_width + offset; i++)
+    {
+      if (i >= 0 && i < row_width)
+        sum += row[i];
+
+      if (i >= offset)
+        {
+          if (i >= d)
+            sum -= row[i - d];
+
+          tmp_buffer[i - offset] = (sum + d / 2) / d;
+        }
+    }
+
+  memcpy (row, tmp_buffer, row_width);
+}
+
+static void
+blur_rows (guchar *dst_buffer,
+           guchar *tmp_buffer,
+           int     buffer_width,
+           int     buffer_height,
+           int     d)
 {
-  guchar A;
-
-  A = *pixel;
-  *zA += (alpha * ((A << zprec) - *zA)) >> aprec;
-  *pixel = *zA >> zprec;
-} 
-
-static inline void
-_blurrow (guchar* pixels,
-          gint    width,
-          gint    height,
-          gint    rowstride,
-          gint    line,
-          gint    alpha,
-          gint    aprec,
-          gint    zprec)
+  int i;
+
+  for (i = 0; i < buffer_height; i++)
+    {
+      guchar *row = dst_buffer + i * buffer_width;
+
+      /* We want to produce a symmetric blur that spreads a pixel
+       * equally far to the left and right. If d is odd that happens
+       * naturally, but for d even, we approximate by using a blur
+       * on either side and then a centered blur of size d + 1.
+       * (techique also from the SVG specification)
+       */
+      if (d % 2 == 1)
+        {
+          blur_xspan (row, tmp_buffer, buffer_width, d, 0);
+          blur_xspan (row, tmp_buffer, buffer_width, d, 0);
+          blur_xspan (row, tmp_buffer, buffer_width, d, 0);
+        }
+      else
+        {
+          blur_xspan (row, tmp_buffer, buffer_width, d, 1);
+          blur_xspan (row, tmp_buffer, buffer_width, d, -1);
+          blur_xspan (row, tmp_buffer, buffer_width, d + 1, 0);
+        }
+    }
+}
+
+/* Swaps width and height. Either swaps in-place and returns the original
+ * buffer or allocates a new buffer, frees the original buffer and returns
+ * the new buffer.
+ */
+static void
+flip_buffer (guchar *dst_buffer,
+             guchar *src_buffer,
+             int     width,
+             int     height)
 {
-  gint    zA;
-  gint    index;
-  guchar* scanline;
-
-  scanline = &pixels[line * rowstride];
-
-  zA = *scanline << zprec;
-
-  for (index = 0; index < width; index ++)
-    _blurinner (&scanline[index],
-                &zA,
-                alpha,
-                aprec,
-                zprec);
-
-  for (index = width - 2; index >= 0; index--)
-    _blurinner (&scanline[index],
-                &zA,
-                alpha,
-                aprec,
-                zprec);
+  /* Working in blocks increases cache efficiency, compared to reading
+   * or writing an entire column at once */
+#define BLOCK_SIZE 16
+
+  int i0, j0;
+
+  for (i0 = 0; i0 < width; i0 += BLOCK_SIZE)
+    for (j0 = 0; j0 < height; j0 += BLOCK_SIZE)
+      {
+        int max_j = MIN(j0 + BLOCK_SIZE, height);
+        int max_i = MIN(i0 + BLOCK_SIZE, width);
+        int i, j;
+
+        for (i = i0; i < max_i; i++)
+          for (j = j0; j < max_j; j++)
+            dst_buffer[i * height + j] = src_buffer[j * width + i];
+      }
+#undef BLOCK_SIZE
 }
 
-static inline void
-_blurcol (guchar* pixels,
-          gint    width,
-          gint    height,
-          gint    rowstride,
-          gint    x,
-          gint    alpha,
-          gint    aprec,
-          gint    zprec)
+static void
+_boxblur (guchar  *buffer,
+          int      width,
+          int      height,
+          int      radius)
 {
-  gint zA;
-  gint index;
-  guchar* ptr;
+  guchar *flipped_buffer;
 
-  ptr = pixels;
+  flipped_buffer = g_malloc (width * height);
 
-  ptr += x;
+  /* Step 1: swap rows and columns */
+  flip_buffer (flipped_buffer, buffer, width, height);
 
-  zA = *ptr << zprec;
+  /* Step 2: blur rows (really columns) */
+  blur_rows (flipped_buffer, buffer, height, width, radius);
 
-  for (index = 0; index < height; index++)
-    _blurinner (&ptr[index * rowstride],
-                &zA,
-                alpha,
-                aprec,
-                zprec);
+  /* Step 3: swap rows and columns */
+  flip_buffer (buffer, flipped_buffer, height, width);
 
-  for (index = height - 2; index >= 0; index--)
-    _blurinner (&ptr[index * rowstride],
-                &zA,
-                alpha,
-                aprec,
-                zprec);
-}
+  /* Step 4: blur rows */
+  blur_rows (buffer, flipped_buffer, width, height, radius);
 
-/*
- * _expblur:
- * @pixels: image data
- * @width: image width
- * @height: image height
- * @rowstride: image rowstride
- * @radius: kernel radius
- * @aprec: precision of alpha parameter in fixed-point format 0.aprec
- * @zprec: precision of state parameters zR,zG,zB and zA in fp format 8.zprec
- *
- * Performs an in-place blur of image data “pixels”
- * with kernel of approximate radius “radius”.
- *
- * Blurs with two sided exponential impulse response.
- *
- */
-static void
-_expblur (guchar* pixels,
-          gint    width,
-          gint    height,
-          gint    rowstride,
-          double  radius,
-          gint    aprec,
-          gint    zprec)
-{
-  gint alpha;
-  int row, col;
-
-  /* Calculate the alpha such that 90% of 
-   * the kernel is within the radius.
-   * (Kernel extends to infinity) */
-  alpha = (gint) ((1 << aprec) * (1.0f - expf (-2.3f / (radius + 1.f))));
-
-  for (row = 0; row < height; row++)
-    _blurrow (pixels,
-              width,
-              height,
-              rowstride,
-              row,
-              alpha,
-              aprec,
-              zprec);
-
-  for(col = 0; col < width; col++)
-    _blurcol (pixels,
-              width,
-              height,
-              rowstride,
-              col,
-              alpha,
-              aprec,
-              zprec);
+  g_free (flipped_buffer);
 }
 
-
 /*
  * _gtk_cairo_blur_surface:
  * @surface: a cairo image surface.
@@ -175,9 +176,10 @@ _expblur (guchar* pixels,
  */
 void
 _gtk_cairo_blur_surface (cairo_surface_t* surface,
-                         double           radius)
+                         double           radius_d)
 {
   cairo_format_t format;
+  int radius = radius_d;
 
   g_return_if_fail (surface != NULL);
   g_return_if_fail (cairo_surface_get_type (surface) == CAIRO_SURFACE_TYPE_IMAGE);
@@ -191,13 +193,10 @@ _gtk_cairo_blur_surface (cairo_surface_t* surface,
   /* Before we mess with the surface execute any pending drawing. */
   cairo_surface_flush (surface);
 
-  _expblur (cairo_image_surface_get_data (surface),
-            cairo_image_surface_get_width (surface),
-            cairo_image_surface_get_height (surface),
+  _boxblur (cairo_image_surface_get_data (surface),
             cairo_image_surface_get_stride (surface),
-            radius,
-            16,
-            7);
+            cairo_image_surface_get_height (surface),
+            radius);
 
   /* Inform cairo we altered the surfaces contents. */
   cairo_surface_mark_dirty (surface);