Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Michael S <already5chosen@yahoo.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety - worst memory size
Date: Wed, 5 Jun 2024 17:45:45 +0300
Organization: A noiseless patient Spider
Lines: 347
Message-ID: <20240605174545.00002c4e@yahoo.com>
References: <ut3669$21eur$1@i2pn2.org>
	<86h6h3nvyz.fsf@linuxsc.com>
	<865xxiok09.fsf@linuxsc.com>
	<20240319131842.00002138@yahoo.com>
	<86o7b9ms7d.fsf@linuxsc.com>
	<20240320115416.00001ab5@yahoo.com>
	<86zfusltwp.fsf@linuxsc.com>
	<20240324193352.000062e9@yahoo.com>
	<86jzlrk0f6.fsf@linuxsc.com>
	<20240405173033.00006145@yahoo.com>
	<868r1k1uq8.fsf@linuxsc.com>
	<20240411152033.00007173@yahoo.com>
	<86bk6ez9te.fsf@linuxsc.com>
	<20240417004609.000010aa@yahoo.com>
	<86plunyj82.fsf@linuxsc.com>
	<20240417224126.0000727a@yahoo.com>
	<86a5lpxbd3.fsf@linuxsc.com>
	<20240420211023.000067cc@yahoo.com>
	<20240425175606.000059d5@yahoo.com>
	<20240503183305.000079e0@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 05 Jun 2024 16:45:33 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="af421c1bf631e23d6a62a4e576399d10";
	logging-data="966879"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19N/XGTyVBsddVaNJcfwObG1MQM3Co0SDc="
Cancel-Lock: sha1:lYFDy6w9n2pvv0GirE0pkZNZaTA=
X-Newsreader: Claws Mail 3.19.1 (GTK+ 2.24.33; x86_64-w64-mingw32)
Bytes: 12939

On Fri, 3 May 2024 18:33:05 +0300
Michael S <already5chosen@yahoo.com> wrote:

> On Thu, 25 Apr 2024 17:56:06 +0300
> Michael S <already5chosen@yahoo.com> wrote:
> 
> 
> A solution (sort of) is in line with the famous quite of David Wheeler
> - to turn todo lists from bit maps into arrays of
> abscesses-or-ordinates of contact points.
> 
> The cost is a memory footprint - 4x bigger than the previous version,
> 32 times bigger than above-mentioned "packed" variant of the previous
> version. But in BigO sense it's the same.
> 
> In my tests it reduced the worst case time from O(max(A,B)**3) to
> O(A*B*log(max(A,B)). Which is non-ideal, but probably acceptable,
> because the bad cases should be very rare in practice.
> 
> The real trouble is different - I don't know if my "worst case" is
> really the worst.
> 
> The code below is for presentation of algorithm in both clear and
> compact manner, with emphasis on symmetry between x and y directions.
> It is not optimal in any sense and can be made no-trivially faster
> both by algorithm enhancements an by specialization of critical loops.
> 
>

Following code improves on ideas from the previous post.
Unlike the previous one, it is purely iterative, with no recursion.
The algorithm is simpler and access storage in more compact manner, i.e.
all accessed memory area starts from beginning and grows according to
need. Previous attempt did not have this property.
It's still longer and less simple than I would like.

// try+split algorithm with flat storage
// - horizontal intervals
// - two stacks: main stack for intervals,
//   auxiliary stack of areas of interest (AoI)
// - both stacks implemented as arrays
#include <stddef.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#define NDEBUG
#include <assert.h>
#include <stdio.h>

typedef unsigned char Color;

typedef struct {
  size_t n_intervals;
  size_t n_splits;
} stack_sizes_t;

static
stack_sizes_t floodfill4_calc_stack_size(int width, int height)
{
  stack_sizes_t sz = { .n_intervals = 1, .n_splits = 1 };
  for (;;) {
    ptrdiff_t len;
    if (width > height) { // split vertically
      len = height;
      width = (width + 1)/2;
    } else { // split horizontally
      len = width;
      height = (height + 1)/2;
    }
    if (len <= 1)
      break;
    sz.n_intervals += len*2 + 4;
    sz.n_splits += 1;
  }
  return sz;
}

int floodfill4(
  Color* image,
  int width, int height,
  int x,     int y,
  Color old_color, Color new_color)
{
  if (width <= 0 || height <= 0)
    return 0;

  if (x < 0 || x >= width || y < 0 || y >= height)
    return 0;

  size_t w = width;
  Color* row = &image[w*y];
  if (row[x] != old_color)
    return 0;

  enum coordinate_axes {
    x_i = 0, y_i, // index of pos[] MS bit of index of limits[][]
  };
  #define X2Y(axis) ((axis) ^ 1)
  enum beg_or_end {
    beg_i = 0, end_i // LS bit of index of limits[],
                     // I use 0 and 1 more commonly
  };
  enum limits_idx { // index of limits[]
    x0_i = x_i*2+beg_i,
    x1_i = x_i*2+end_i,
    y0_i = y_i*2+beg_i,
    y1_i = y_i*2+end_i,
  };

  typedef struct {
    int x0, x1, y;
    int from; // 0 => from y-1, 1 => from y+1
  } interval_t;
  typedef struct {
    interval_t* parent_todo;
    int         saved_limit_val;
    uint8_t     saved_limit_idx; // axis*2+beg_or_end
    int         frame_capacity_deficit;
  } parent_info_t;

  stack_sizes_t stacks_len = floodfill4_calc_stack_size(width, height);
  const size_t parent_info_sz = stacks_len.n_splits *
  sizeof(parent_info_t); const size_t todo_sz = stacks_len.n_intervals
  * sizeof(interval_t); void* stacks = malloc(parent_info_sz + todo_sz);
  if (!stacks)
    return -1;

  parent_info_t* parents_stack = stacks;
  parent_info_t* parents_stack_end =
  &parents_stack[stacks_len.n_splits]; interval_t* todo_stack =
  (interval_t*)parents_stack_end; interval_t* todo = todo_stack;
  #ifndef NDEBUG
  interval_t* todo_stack_end = &todo[stacks_len.n_intervals];
  #endif

  int limits[2*2] = { 0, width-1, 0, height-1}; // {x0, x1, y0, y1};

  // recolor initial horizontal interval
  row[x] = new_color;
  // look backward
  int x00;
  for (x00 = x-1; x00 >= 0 && row[x00]==old_color; --x00)
    row[x00] = new_color;
  x00 += 1;
  // look forward
  int x01;
  for (x01 = x+1; x01 < width && row[x01]==old_color; ++x01)
    row[x01] = new_color;
  x01 -= 1;
  // push neighbors of initial interval on todo stack
  for (enum beg_or_end from = beg_i; from <= end_i; ++from) {
    unsigned next_y = y+1-from*2;
    if (next_y < (unsigned)height) {
      todo->x0 = x00;
      todo->x1 = x01;
      todo->y  = next_y;
      todo->from = from;
      ++todo;
    }
  }

  parent_info_t* parent_aoi = parents_stack;
========== REMAINDER OF ARTICLE TRUNCATED ==========