[gimp] app: add GimpChunkIterator

[Ell <ell src gnome org>]

commit ba9ce34e1009f6abb4c2762fe482b86ae225163c
Author: Ell <ell_se yahoo com>
Date:   Sat Jan 12 03:12:13 2019 -0500

    app: add GimpChunkIterator
    
    Factor out the region-chunking logic of GimpProjection into a new
    GimpChunkIterator type, providing a generic mechanism for iterating
    over a cairo region in discrete chunks.  The iterator doesn't
    perform any processing itself, but rather dispenses rectangular
    chunks, which the user then processes.
    
    Iteration is broken into intervals, the duration of which is
    configurable.  Each iteration begins with a call to
    gimp_chunk_iterator_next(), after which
    gimp_chunk_iterator_get_rect() should be called in succession to
    fetch a rectangle to process, until it returns FALSE, which marks
    the end of the iteration.  Updates to the UI should take place in
    the interval between iterations, but not during an iteration.  The
    iterator dynamically adjusts the chunk size according to processing
    speed, in order to match the target iteration interval.
    
    The iterator can be given a priority rectangle, which is processed
    before the rest of the region.  It can also be given a
    representative tile rectangle, defining a regular tile grid;
    dispensed chunks are aligned to the tile grid as much as possible.

 app/core/Makefile.am         |   2 +
 app/core/core-types.h        |   1 +
 app/core/gimpchunkiterator.c | 473 +++++++++++++++++++++++++++++++++++++++++++
 app/core/gimpchunkiterator.h |  44 ++++
 4 files changed, 520 insertions(+)
---
diff --git a/app/core/Makefile.am b/app/core/Makefile.am
index 585b8057e4..2cf3699bf2 100644
--- a/app/core/Makefile.am
+++ b/app/core/Makefile.am
@@ -143,6 +143,8 @@ libappcore_a_sources = \
        gimpchannelpropundo.h                   \
        gimpchannelundo.c                       \
        gimpchannelundo.h                       \
+       gimpchunkiterator.c                     \
+       gimpchunkiterator.h                     \
        gimpcontainer.c                         \
        gimpcontainer.h                         \
        gimpcontainer-filter.c                  \
diff --git a/app/core/core-types.h b/app/core/core-types.h
index ad1565fbac..afb27e8211 100644
--- a/app/core/core-types.h
+++ b/app/core/core-types.h
@@ -223,6 +223,7 @@ typedef struct _GimpWaitable                    GimpWaitable;    /* dummy typede
 
 typedef struct _GimpBacktrace                   GimpBacktrace;
 typedef struct _GimpBoundSeg                    GimpBoundSeg;
+typedef struct _GimpChunkIterator               GimpChunkIterator;
 typedef struct _GimpCoords                      GimpCoords;
 typedef struct _GimpGradientSegment             GimpGradientSegment;
 typedef struct _GimpPaletteEntry                GimpPaletteEntry;
diff --git a/app/core/gimpchunkiterator.c b/app/core/gimpchunkiterator.c
new file mode 100644
index 0000000000..1cf7da1459
--- /dev/null
+++ b/app/core/gimpchunkiterator.c
@@ -0,0 +1,473 @@
+/* GIMP - The GNU Image Manipulation Program
+ * Copyright (C) 1995-1999 Spencer Kimball and Peter Mattis
+ *
+ * gimpchunkiterator.c
+ * Copyright (C) 2019 Ell
+ *
+ * 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 3 of the License, or
+ * (at your option) any later version.
+ *
+ * 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 General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+
+#include "config.h"
+
+#include <cairo.h>
+#include <gdk-pixbuf/gdk-pixbuf.h>
+#include <gegl.h>
+
+#include "libgimpmath/gimpmath.h"
+
+#include "core-types.h"
+
+#include "gimpchunkiterator.h"
+
+
+/* the maximal chunk size */
+#define MAX_CHUNK_WIDTH          4096
+#define MAX_CHUNK_HEIGHT         4096
+
+/* the default iteration interval */
+#define DEFAULT_INTERVAL         (1.0 / 15.0) /* seconds */
+
+/* the minimal processed area on the current iteration, above which we
+ * calculate a new target area to render on the next iteration
+ */
+#define MIN_AREA_PER_UPDATE      1024
+
+/* the width of the target-area sliding window */
+#define TARGET_AREA_HISTORY_SIZE 5
+
+
+struct _GimpChunkIterator
+{
+  cairo_region_t *region;
+  cairo_region_t *priority_region;
+
+  GeglRectangle   tile_rect;
+  GeglRectangle   priority_rect;
+
+  gdouble         interval;
+
+  cairo_region_t *current_region;
+  GeglRectangle   current_rect;
+
+  gint            current_x;
+  gint            current_y;
+  gint            current_height;
+
+  gint64          iteration_time;
+
+  gdouble         current_area;
+  gdouble         target_area;
+
+  gdouble         target_area_history[TARGET_AREA_HISTORY_SIZE];
+  gint            target_area_history_i;
+};
+
+
+/*  local function prototypes  */
+
+static void       gimp_chunk_iterator_set_current_rect   (GimpChunkIterator   *iter,
+                                                          const GeglRectangle *rect);
+static void       gimp_chunk_iterator_merge_current_rect (GimpChunkIterator   *iter);
+
+static void       gimp_chunk_iterator_merge              (GimpChunkIterator   *iter);
+
+static gboolean   gimp_chunk_iterator_prepare            (GimpChunkIterator   *iter);
+
+
+/*  private functions  */
+
+static void
+gimp_chunk_iterator_set_current_rect (GimpChunkIterator   *iter,
+                                      const GeglRectangle *rect)
+{
+  cairo_region_subtract_rectangle (iter->current_region,
+                                   (const cairo_rectangle_int_t *) rect);
+
+  iter->current_rect = *rect;
+
+  iter->current_x    = rect->x;
+  iter->current_y    = rect->y;
+}
+
+static void
+gimp_chunk_iterator_merge_current_rect (GimpChunkIterator *iter)
+{
+  GeglRectangle rect;
+  gint          current_height = 0;
+
+  if (gegl_rectangle_is_empty (&iter->current_rect))
+    return;
+
+  /* merge the remainder of the current row */
+  if (iter->current_x != iter->current_rect.x)
+    {
+      current_height = iter->current_height;
+
+      rect.x      = iter->current_x;
+      rect.y      = iter->current_y;
+      rect.width  = iter->current_rect.x + iter->current_rect.width -
+                    iter->current_x;
+      rect.height = current_height;
+
+      cairo_region_union_rectangle (iter->current_region,
+                                    (const cairo_rectangle_int_t *) &rect);
+    }
+
+  /* merge the remainder of the current rect */
+  rect.x      = iter->current_rect.x;
+  rect.y      = iter->current_y + current_height;
+  rect.width  = iter->current_rect.width;
+  rect.height = iter->current_rect.y + iter->current_rect.height - rect.y;
+
+  cairo_region_union_rectangle (iter->current_region,
+                                (const cairo_rectangle_int_t *) &rect);
+
+  /* reset the current rect and coordinates */
+  iter->current_rect.x      = 0;
+  iter->current_rect.y      = 0;
+  iter->current_rect.width  = 0;
+  iter->current_rect.height = 0;
+
+  iter->current_x           = 0;
+  iter->current_y           = 0;
+}
+
+static void
+gimp_chunk_iterator_merge (GimpChunkIterator *iter)
+{
+  /* merge the current rect back to the current region */
+  gimp_chunk_iterator_merge_current_rect (iter);
+
+  /* merge the priority region back to the global region */
+  if (iter->priority_region)
+    {
+      cairo_region_union (iter->region, iter->priority_region);
+
+      g_clear_pointer (&iter->priority_region, cairo_region_destroy);
+    }
+}
+
+static gboolean
+gimp_chunk_iterator_prepare (GimpChunkIterator *iter)
+{
+  if (iter->current_x >= iter->current_rect.x + iter->current_rect.width)
+    {
+      iter->current_x  = iter->current_rect.x;
+      iter->current_y += iter->current_height;
+
+      if (iter->current_y >= iter->current_rect.y + iter->current_rect.height)
+        {
+          GeglRectangle rect;
+
+          if (! iter->priority_region &&
+              ! gegl_rectangle_is_empty (&iter->priority_rect))
+            {
+              iter->priority_region = cairo_region_copy (iter->region);
+
+              cairo_region_intersect_rectangle (
+                iter->priority_region,
+                (const cairo_rectangle_int_t *) &iter->priority_rect);
+
+              cairo_region_subtract_rectangle (
+                iter->region,
+                (const cairo_rectangle_int_t *) &iter->priority_rect);
+            }
+
+          if (! iter->priority_region ||
+              cairo_region_is_empty (iter->priority_region))
+            {
+              iter->current_region = iter->region;
+            }
+          else
+            {
+              iter->current_region = iter->priority_region;
+            }
+
+          if (cairo_region_is_empty (iter->current_region))
+            {
+              iter->current_rect.x      = 0;
+              iter->current_rect.y      = 0;
+              iter->current_rect.width  = 0;
+              iter->current_rect.height = 0;
+
+              iter->current_x           = 0;
+              iter->current_y           = 0;
+
+              return FALSE;
+            }
+
+          cairo_region_get_rectangle (iter->current_region, 0,
+                                      (cairo_rectangle_int_t *) &rect);
+
+          gimp_chunk_iterator_set_current_rect (iter, &rect);
+        }
+    }
+
+  return TRUE;
+}
+
+
+/*  public functions  */
+
+GimpChunkIterator *
+gimp_chunk_iterator_new (cairo_region_t *region)
+{
+  GimpChunkIterator *iter;
+
+  g_return_val_if_fail (region != NULL, NULL);
+
+  iter = g_slice_new0 (GimpChunkIterator);
+
+  iter->region = region;
+
+  g_object_get (gegl_config (),
+                "tile-width",  &iter->tile_rect.width,
+                "tile-height", &iter->tile_rect.height,
+                NULL);
+
+  iter->interval = DEFAULT_INTERVAL;
+
+  return iter;
+}
+
+void
+gimp_chunk_iterator_set_tile_rect (GimpChunkIterator   *iter,
+                                   const GeglRectangle *rect)
+{
+  g_return_if_fail (iter != NULL);
+  g_return_if_fail (rect != NULL);
+  g_return_if_fail (! gegl_rectangle_is_empty (rect));
+
+  iter->tile_rect = *rect;
+}
+
+void
+gimp_chunk_iterator_set_priority_rect (GimpChunkIterator   *iter,
+                                       const GeglRectangle *rect)
+{
+  const GeglRectangle empty_rect = {};
+
+  g_return_if_fail (iter != NULL);
+
+  if (! rect)
+    rect = &empty_rect;
+
+  if (! gegl_rectangle_equal (rect, &iter->priority_rect))
+    {
+      iter->priority_rect = *rect;
+
+      gimp_chunk_iterator_merge (iter);
+    }
+}
+
+void
+gimp_chunk_iterator_set_interval (GimpChunkIterator *iter,
+                                  gdouble            interval)
+{
+  g_return_if_fail (iter != NULL);
+
+  interval = MAX (interval, 0.0);
+
+  if (interval != iter->interval)
+    {
+      if (iter->interval)
+        {
+          gdouble ratio = interval / iter->interval;
+          gint    i;
+
+          iter->target_area *= ratio;
+
+          for (i = 0; i < TARGET_AREA_HISTORY_SIZE; i++)
+            iter->target_area_history[i] *= ratio;
+        }
+
+      iter->interval = interval;
+    }
+}
+
+gboolean
+gimp_chunk_iterator_next (GimpChunkIterator *iter)
+{
+  g_return_val_if_fail (iter != NULL, FALSE);
+
+  if (! gimp_chunk_iterator_prepare (iter))
+    {
+      gimp_chunk_iterator_stop (iter, TRUE);
+
+      return FALSE;
+    }
+
+  iter->iteration_time = g_get_monotonic_time ();
+
+  iter->current_area = 0;
+
+  return TRUE;
+}
+
+static gint
+compare_double (const gdouble *x,
+                const gdouble *y)
+{
+  return (*y < *x) - (*x < *y);
+}
+
+gboolean
+gimp_chunk_iterator_get_rect (GimpChunkIterator *iter,
+                              GeglRectangle     *rect)
+{
+  gdouble interval;
+  gdouble aspect_ratio;
+  gint    offset_x;
+  gint    offset_y;
+
+  g_return_val_if_fail (iter != NULL, FALSE);
+  g_return_val_if_fail (rect != NULL, FALSE);
+
+  if (! gimp_chunk_iterator_prepare (iter))
+    return FALSE;
+
+  interval = (gdouble) (g_get_monotonic_time () - iter->iteration_time) /
+             G_TIME_SPAN_SECOND;
+
+  if (iter->current_area > 0 && interval > iter->interval)
+    {
+      /* adjust the target area to be processed on the next iteration,
+       * according to the area processed during this iteration and the elapsed
+       * time, in order to match the desired interval.
+       */
+      if (iter->current_area >= MIN_AREA_PER_UPDATE)
+        {
+          gdouble target_area_history[TARGET_AREA_HISTORY_SIZE];
+
+          iter->target_area_history[iter->target_area_history_i] =
+            iter->current_area * iter->interval / interval;
+
+          /* calculate the median target area of the last
+           * TARGET_AREA_HISTORY_SIZE iterations
+           */
+          memcpy (target_area_history, iter->target_area_history,
+                  sizeof (target_area_history));
+
+          qsort (target_area_history, TARGET_AREA_HISTORY_SIZE,
+                 sizeof (gdouble), (gpointer) compare_double);
+
+          iter->target_area = target_area_history[TARGET_AREA_HISTORY_SIZE / 2];
+
+          iter->target_area_history_i++;
+          iter->target_area_history_i %= TARGET_AREA_HISTORY_SIZE;
+        }
+
+      return FALSE;
+    }
+
+  if (! iter->target_area)
+    {
+      gint i;
+
+      iter->target_area = iter->tile_rect.width * iter->tile_rect.height;
+
+      for (i = 0; i < TARGET_AREA_HISTORY_SIZE; i++)
+        iter->target_area_history[i] = iter->target_area;
+
+      iter->target_area_history_i = 0;
+    }
+
+  aspect_ratio = (gdouble) iter->tile_rect.width /
+                 (gdouble) iter->tile_rect.height;
+
+  rect->x = iter->current_x;
+  rect->y = iter->current_y;
+
+  offset_x = rect->x - iter->tile_rect.x;
+  offset_y = rect->y - iter->tile_rect.y;
+
+  rect->width = ceil ((offset_x + sqrt (iter->target_area * aspect_ratio)) /
+                      iter->tile_rect.width)                               *
+                iter->tile_rect.width                                      -
+                offset_x;
+
+  rect->height = ceil ((offset_y + (gdouble) iter->target_area /
+                                   (gdouble) rect->width)      /
+                       iter->tile_rect.height)                 *
+                 iter->tile_rect.height                        -
+                 offset_y;
+
+  rect->width = MIN (rect->width,
+                     iter->current_rect.x + iter->current_rect.width -
+                     rect->x);
+  rect->width = MIN (rect->width, MAX_CHUNK_WIDTH);
+
+  rect->height = MIN (rect->height,
+                      iter->current_rect.y + iter->current_rect.height -
+                      rect->y);
+  rect->height = MIN (rect->height, MAX_CHUNK_HEIGHT);
+
+  if (rect->height != iter->current_height)
+    {
+      /* if the chunk height changed in the middle of a row, merge the
+       * remaining area back into the current region, and reset the current
+       * area to the remainder of the row, using the new chunk height
+       */
+      if (rect->x != iter->current_rect.x)
+        {
+          GeglRectangle rem;
+
+          rem.x      = rect->x;
+          rem.y      = rect->y;
+          rem.width  = iter->current_rect.x + iter->current_rect.width -
+                       rect->x;
+          rem.height = rect->height;
+
+          gimp_chunk_iterator_merge_current_rect (iter);
+
+          gimp_chunk_iterator_set_current_rect (iter, &rem);
+        }
+
+      iter->current_height = rect->height;
+    }
+
+  iter->current_x += rect->width;
+
+  iter->current_area += rect->width * rect->height;
+
+  return TRUE;
+}
+
+cairo_region_t *
+gimp_chunk_iterator_stop (GimpChunkIterator *iter,
+                          gboolean           free_region)
+{
+  cairo_region_t *result = NULL;
+
+  g_return_val_if_fail (iter != NULL, NULL);
+
+  if (free_region)
+    {
+      cairo_region_destroy (iter->region);
+    }
+  else
+    {
+      if (gimp_chunk_iterator_prepare (iter))
+        gimp_chunk_iterator_merge (iter);
+
+      result = iter->region;
+    }
+
+  g_clear_pointer (&iter->priority_region, cairo_region_destroy);
+
+  g_slice_free (GimpChunkIterator, iter);
+
+  return result;
+}
diff --git a/app/core/gimpchunkiterator.h b/app/core/gimpchunkiterator.h
new file mode 100644
index 0000000000..e1756f3629
--- /dev/null
+++ b/app/core/gimpchunkiterator.h
@@ -0,0 +1,44 @@
+/* GIMP - The GNU Image Manipulation Program
+ * Copyright (C) 1995 Spencer Kimball and Peter Mattis
+ *
+ * gimpchunkiterator.h
+ * Copyright (C) 2019 Ell
+ *
+ * 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 3 of the License, or
+ * (at your option) any later version.
+ *
+ * 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 General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+#ifndef __GIMP_CHUNK_ITEARTOR_H__
+#define __GIMP_CHUNK_ITEARTOR_H__
+
+
+GimpChunkIterator * gimp_chunk_iterator_new               (cairo_region_t      *region);
+
+void                gimp_chunk_iterator_set_tile_rect     (GimpChunkIterator   *iter,
+                                                           const GeglRectangle *rect);
+
+void                gimp_chunk_iterator_set_priority_rect (GimpChunkIterator   *iter,
+                                                           const GeglRectangle *rect);
+
+void                gimp_chunk_iterator_set_interval      (GimpChunkIterator   *iter,
+                                                           gdouble              interval);
+
+gboolean            gimp_chunk_iterator_next              (GimpChunkIterator   *iter);
+gboolean            gimp_chunk_iterator_get_rect          (GimpChunkIterator   *iter,
+                                                           GeglRectangle       *rect);
+
+cairo_region_t    * gimp_chunk_iterator_stop              (GimpChunkIterator   *iter,
+                                                           gboolean             free_region);
+
+
+#endif  /*  __GIMP_CHUNK_ITEARTOR_H__  */