Use faster search algorithm for optimum arrangement

git-svn-id: http://svn.code.sf.net/p/netpbm/code/trunk@454 9d0c8265-081b-0410-96cb-a4ca84ce46f8

1 files changed, 301 insertions, 157 deletions

diff --git a/editor/pnmmontage.c b/editor/pnmmontage.c
index 9eb2d7be..e992dab3 100644
--- a/editor/pnmmontage.c
+++ b/editor/pnmmontage.c
@@ -10,18 +10,20 @@
  * implied warranty.
  */
 
+#include <assert.h>
 #include <limits.h>
 #include <string.h>
 
-#include "pam.h"
-#include "shhopt.h"
-#include "nstring.h"
+#include "pm_c_util.h"
 #include "mallocvar.h"
+#include "nstring.h"
+#include "shhopt.h"
+#include "pam.h"
 
 typedef struct { int f[sizeof(int) * 8 + 1]; } factorset;
 typedef struct { int x; int y; } coord;
 
-static int qfactor = 200;
+static int qfactor;
 static int quality = 5;
 
 static factorset 
@@ -63,62 +65,79 @@ gcd(int n, int m)
   return (g);
 }
 
-static __inline__ int imax(int n, int m) { return (n > m ? n : m); }
 
-static int 
-checkcollision(coord *locs, coord *szs, coord *cloc, coord *csz, int n)
-{
-  int i;
-  for (i = 0; i < n; ++i)
-  {
-    if ((locs[i].x < cloc->x + csz->x) &&
-        (locs[i].y < cloc->y + csz->y) &&
-        (locs[i].x + szs[i].x > cloc->x) &&
-        (locs[i].y + szs[i].y > cloc->y))
-      return (1);
-  }
-  return (0);
+
+static bool
+collides(const coord * const locs,
+         const coord * const szs,
+         const coord * const cloc,
+         const coord * const csz,
+         unsigned int  const n) {
+
+    unsigned int i;
+
+    for (i = 0; i < n; ++i) {
+        if ((locs[i].x < cloc->x + csz->x) &&
+            (locs[i].y < cloc->y + csz->y) &&
+            (locs[i].x + szs[i].x > cloc->x) &&
+            (locs[i].y + szs[i].y > cloc->y))
+            return true;
+    }
+    return false;
 }
 
+
+
 static void 
-recursefindpack(coord *current, coord currentsz, coord *set, 
-                coord *best, int minarea, int *maxarea, 
-                int depth, int n, int xinc, int yinc)
-{
-  coord c;
-  if (depth == n)
-  {
-    if (currentsz.x * currentsz.y < *maxarea)
-    {
-      memcpy(best, current, sizeof(coord) * n);
-      *maxarea = currentsz.x * currentsz.y;
-    }
-    return;
-  }
+recursefindpack(coord *        const current,
+                coord          const currentsz,
+                coord *        const set, 
+                coord *        const best,
+                unsigned int   const minarea,
+                unsigned int * const maxareaP, 
+                unsigned int   const depth,
+                unsigned int   const n,
+                unsigned int   const xinc,
+                unsigned int   const yinc) {
+
+    if (depth == n) {
+        if (currentsz.x * currentsz.y < *maxareaP) {
+            unsigned int i;
+            for (i = 0; i < n; ++i)
+                best[i] = current[i];
+            *maxareaP = currentsz.x * currentsz.y;
+        }
+    } else {
+        unsigned int i;
 
-  for (current[depth].x = 0; 
-       imax(current[depth].x + set[depth].x, currentsz.x) * 
-           imax(currentsz.y, set[depth].y) < *maxarea; 
-       current[depth].x += xinc)
-  {
-    for (current[depth].y = 0; 
-         imax(current[depth].x + set[depth].x, currentsz.x) * 
-             imax(currentsz.y, current[depth].y + set[depth].y) < *maxarea; 
-         current[depth].y += yinc)
-    {
-      c.x = imax(current[depth].x + set[depth].x, currentsz.x);
-      c.y = imax(current[depth].y + set[depth].y, currentsz.y);
-      if (!checkcollision(current, set, &current[depth], &set[depth], depth))
-      {
-        recursefindpack(current, c, set, best, minarea, maxarea, 
-                        depth + 1, n, xinc, yinc);
-        if (*maxarea <= minarea)
-          return;
-      }
+        for (i = 0; ; ++i) {
+            for (current[depth].x = 0, current[depth].y = i * yinc;
+                 current[depth].y <= i * yinc;) {
+
+                coord c;
+
+                c.x = MAX(current[depth].x + set[depth].x, currentsz.x);
+                c.y = MAX(current[depth].y + set[depth].y, currentsz.y);
+                if (!collides(current, set, &current[depth],
+                              &set[depth], depth)) {
+                    recursefindpack(current, c, set, best, minarea, maxareaP,
+                                    depth + 1, n, xinc, yinc);
+                    if (*maxareaP <= minarea)
+                        return;
+                }
+                if (current[depth].x == (i - 1) * xinc)
+                    current[depth].y = 0;
+                if (current[depth].x < i * xinc)
+                    current[depth].x += xinc;
+                else
+                    current[depth].y += yinc;
+            }
+        }
     }
-  }
 }
 
+
+
 static void 
 findpack(struct pam *imgs, int n, coord *coords)
 {
@@ -130,15 +149,15 @@ findpack(struct pam *imgs, int n, coord *coords)
   int miny = -1;
   coord *current;
   coord *set;
-  int z = INT_MAX;
+  unsigned int z = UINT_MAX;
   coord c = { 0, 0 };
 
   if (quality > 1)
   {
     for (minarea = i = 0; i < n; ++i)
       minarea += imgs[i].height * imgs[i].width,
-      minx = imax(minx, imgs[i].width),
-      miny = imax(miny, imgs[i].height);
+      minx = MAX(minx, imgs[i].width),
+      miny = MAX(miny, imgs[i].height);
 
     minarea = minarea * qfactor / 100;
   }
@@ -237,65 +256,241 @@ writePam(struct pam *       const outpamP,
 
 
 
+static void
+writeData(FILE *             const dataFileP,
+          unsigned int       const width,
+          unsigned int       const height,
+          unsigned int       const nfiles,
+          const char **      const names,
+          const coord *      const coords,
+          const struct pam * const imgs) {
+
+    unsigned int i;
+
+    fprintf(dataFileP, ":0:0:%u:%u\n", width, height);
+
+    for (i = 0; i < nfiles; ++i) {
+        fprintf(dataFileP, "%s:%u:%u:%u:%u\n", names[i], coords[i].x,
+                coords[i].y, imgs[i].width, imgs[i].height);
+    }
+}
+
+
+
+static void
+writeHeader(FILE * const headerFileP,
+            const char * const prefix,
+            unsigned int const width,
+            unsigned int const height,
+            unsigned int const nfiles,
+            const char ** const names,
+            const coord * const coords,
+            const struct pam * imgs) {
+
+    unsigned int i;
+
+    fprintf(headerFileP, "#define %sOVERALLX %u\n", prefix, width);
+
+    fprintf(headerFileP, "#define %sOVERALLY %u\n", prefix, height);
+
+    fprintf(headerFileP, "\n");
+
+    for (i = 0; i < nfiles; ++i) {
+        char * const buffer = strdup(names[i]);
+        coord const coord = coords[i];
+        struct pam const img = imgs[i];
+
+        unsigned int j;
+        
+        *strchr(buffer, '.') = 0;
+        for (j = 0; buffer[j]; ++j) {
+            if (ISLOWER(buffer[j]))
+                buffer[j] = TOUPPER(buffer[j]);
+        }
+        fprintf(headerFileP, "#define %s%sX %u\n", 
+                prefix, buffer, coord.x);
+
+        fprintf(headerFileP, "#define %s%sY %u\n",
+                prefix, buffer, coord.y);
+
+        fprintf(headerFileP, "#define %s%sSZX %u\n",
+                prefix, buffer, img.width);
+
+        fprintf(headerFileP, "#define %s%sSZY %u\n",
+                prefix, buffer, img.height);
+
+        fprintf(headerFileP, "\n");
+    }
+}
+
+
+
+static void
+sortImagesByArea(unsigned int  const nfiles,
+                 struct pam *  const imgs,
+                 const char ** const names) {
+/*----------------------------------------------------------------------------
+   Sort the images described by 'imgs' and 'names' in place, from largest
+   area to smallest.
+-----------------------------------------------------------------------------*/
+    /* Bubble sort */
+
+    unsigned int i;
+
+    for (i = 0; i < nfiles - 1; ++i) {
+        unsigned int j;
+        for (j = i + 1; j < nfiles; ++j) {
+            if (imgs[j].width * imgs[j].height >
+                imgs[i].width * imgs[i].height) {
+
+                struct pam p;
+                const char * c;
+                
+                p = imgs[i]; imgs[i] = imgs[j]; imgs[j] = p;
+                c = names[i]; names[i] = names[j]; names[j] = c;
+            }
+        }
+    }
+}
+
+
+
+static void
+computeOutputType(sample *           const maxvalP,
+                  int *              const formatP,
+                  char *             const tupleTypeP,
+                  unsigned int *     const depthP,
+                  unsigned int       const nfiles,
+                  const struct pam * const imgs) {
+
+    unsigned int i;
+
+    sample maxval;
+    int format;
+    const char * tupleType;
+    unsigned int depth;
+
+    assert(nfiles > 0);
+
+    /* initial guesses */
+    maxval    = imgs[0].maxval;
+    format    = imgs[0].format;
+    depth     = imgs[0].depth;
+    tupleType = imgs[0].tuple_type;
+
+    for (i = 1; i < nfiles; ++i) {
+        if (PAM_FORMAT_TYPE(imgs[i].format) > PAM_FORMAT_TYPE(format)) {
+            format    = imgs[i].format;
+            tupleType = imgs[i].tuple_type;
+        }
+        maxval = MAX(maxval, imgs[i].maxval);
+        depth  = MAX(depth,  imgs[i].depth);
+    }
+
+    *maxvalP = maxval;
+    *formatP = format;
+    *depthP  = depth;
+    memcpy(tupleTypeP, tupleType, sizeof(imgs[0].tuple_type));
+}
+
+
+
+static void
+computeOutputDimensions(int * const widthP,
+                        int * const heightP,
+                        unsigned int const nfiles,
+                        const struct pam * const imgs,
+                        const coord * const coords) {
+
+    unsigned int widthGuess, heightGuess;
+    unsigned int i;
+
+    widthGuess  = 0;  /* initial value */
+    heightGuess = 0;  /* initial value */
+    
+    for (i = 0; i < nfiles; ++i) {
+        widthGuess  = MAX(widthGuess,  imgs[i].width  + coords[i].x);
+        heightGuess = MAX(heightGuess, imgs[i].height + coords[i].y);
+    }
+
+    *widthP  = widthGuess;
+    *heightP = heightGuess;
+}
+
+
+
+struct cmdlineInfo {
+    const char * header;
+    const char * data;
+    const char * prefix;
+    unsigned int quality;
+    unsigned int q[10];
+};
+
+
+
 int 
-main(int argc, char **argv)
-{
+main(int argc, char **argv) {
+  struct cmdlineInfo cmdline;
   struct pam *imgs;
   struct pam outimg;
-  struct pam p;
   int nfiles;
-  int i, j;
-  unsigned int q[10];
   coord *coords;
-  const char *headfname = NULL;
-  const char *datafname = NULL;
-  const char *prefix = "";
   FILE *header;
   FILE *data;
-  char **names;
-  char *c;
+  const char **names;
+  unsigned int i;
 
-  optEntry *option_def = malloc(100*sizeof(optEntry));
+  optEntry * option_def;
       /* Instructions to OptParseOptions3 on how to parse our options.
        */
   optStruct3 opt;
-
+  unsigned int dataSpec, headerSpec, prefixSpec, qualitySpec;
   unsigned int option_def_index;
 
+  pm_proginit(&argc, argv);
+
+  MALLOCARRAY_NOFAIL(option_def, 100);
+  
   option_def_index = 0;   /* incremented by OPTENTRY */
-  OPTENT3( 0,  "data",    OPT_STRING, &datafname, NULL, 0);
-  OPTENT3( 0,  "header",  OPT_STRING, &headfname, NULL, 0);
-  OPTENT3('q', "quality", OPT_UINT,   &qfactor,   NULL, 0);
-  OPTENT3('p', "prefix",  OPT_STRING, &prefix,    NULL, 0);
-  OPTENT3('0', "0",       OPT_FLAG,   NULL, &q[0],      0);
-  OPTENT3('1', "1",       OPT_FLAG,   NULL, &q[1],      0);
-  OPTENT3('2', "2",       OPT_FLAG,   NULL, &q[2],      0);
-  OPTENT3('3', "3",       OPT_FLAG,   NULL, &q[3],      0);
-  OPTENT3('4', "4",       OPT_FLAG,   NULL, &q[4],      0);
-  OPTENT3('5', "5",       OPT_FLAG,   NULL, &q[5],      0);
-  OPTENT3('6', "6",       OPT_FLAG,   NULL, &q[6],      0);
-  OPTENT3('7', "7",       OPT_FLAG,   NULL, &q[7],      0);
-  OPTENT3('8', "8",       OPT_FLAG,   NULL, &q[8],      0);
-  OPTENT3('9', "9",       OPT_FLAG,   NULL, &q[9],      0);
+  OPTENT3( 0,  "data",    OPT_STRING, &cmdline.data, &dataSpec, 0);
+  OPTENT3( 0,  "header",  OPT_STRING, &cmdline.header, &headerSpec, 0);
+  OPTENT3('q', "quality", OPT_UINT,   &cmdline.quality,   &qualitySpec, 0);
+  OPTENT3('p', "prefix",  OPT_STRING, &cmdline.prefix,    &prefixSpec, 0);
+  OPTENT3('0', "0",       OPT_FLAG,   NULL, &cmdline.q[0],      0);
+  OPTENT3('1', "1",       OPT_FLAG,   NULL, &cmdline.q[1],      0);
+  OPTENT3('2', "2",       OPT_FLAG,   NULL, &cmdline.q[2],      0);
+  OPTENT3('3', "3",       OPT_FLAG,   NULL, &cmdline.q[3],      0);
+  OPTENT3('4', "4",       OPT_FLAG,   NULL, &cmdline.q[4],      0);
+  OPTENT3('5', "5",       OPT_FLAG,   NULL, &cmdline.q[5],      0);
+  OPTENT3('6', "6",       OPT_FLAG,   NULL, &cmdline.q[6],      0);
+  OPTENT3('7', "7",       OPT_FLAG,   NULL, &cmdline.q[7],      0);
+  OPTENT3('8', "8",       OPT_FLAG,   NULL, &cmdline.q[8],      0);
+  OPTENT3('9', "9",       OPT_FLAG,   NULL, &cmdline.q[9],      0);
 
   opt.opt_table = option_def;
   opt.short_allowed = FALSE;
   opt.allowNegNum = FALSE;
 
-  pnm_init(&argc, argv);
-
   /* Check for flags. */
   optParseOptions3(&argc, argv, opt, sizeof(opt), 0);
 
-  if (headfname)
-    header = pm_openw(headfname);
+  if (!dataSpec)
+      cmdline.data = NULL;
+  if (!headerSpec)
+      cmdline.header = NULL;
+  if (!prefixSpec)
+      cmdline.prefix = "";
+  if (!qualitySpec)
+      cmdline.quality = 200;
 
-  if (datafname)
-    data = pm_openw(datafname);
+  header = cmdline.header ? pm_openw(cmdline.header) : NULL;
+  data = cmdline.data ? pm_openw(cmdline.data) : NULL;
+  qfactor = cmdline.quality;
 
   for (i = 0; i < 10; ++i)
   {
-    if (q[i])
+    if (cmdline.q[i])
     {
       quality = i;
       switch (quality)
@@ -345,37 +540,19 @@ main(int argc, char **argv)
     imgs[0].file = stdin;
   }
 
-  pnm_readpaminit(imgs[0].file, &imgs[0], PAM_STRUCT_SIZE(tuple_type));
-  outimg.maxval = imgs[0].maxval;
-  outimg.format = imgs[0].format;
-  memcpy(outimg.tuple_type, imgs[0].tuple_type, sizeof(imgs[0].tuple_type));
-  outimg.depth = imgs[0].depth;
-
-  for (i = 1; i < nfiles; ++i)
-  {
-    pnm_readpaminit(imgs[i].file, &imgs[i], PAM_STRUCT_SIZE(tuple_type));
-    if (PAM_FORMAT_TYPE(imgs[i].format) > PAM_FORMAT_TYPE(outimg.format))
-      outimg.format = imgs[i].format,
-      memcpy(outimg.tuple_type, imgs[i].tuple_type, 
-             sizeof(imgs[i].tuple_type));
-    outimg.maxval = imax(imgs[i].maxval, outimg.maxval);
-    outimg.depth = imax(imgs[i].depth, outimg.depth);
-  }
+  for (i = 0; i < nfiles; ++i)
+      pnm_readpaminit(imgs[i].file, &imgs[i], PAM_STRUCT_SIZE(tuple_type));
 
-  for (i = 0; i < nfiles - 1; ++i)
-    for (j = i + 1; j < nfiles; ++j)
-      if (imgs[j].width * imgs[j].height > imgs[i].width * imgs[i].height)
-        p = imgs[i], imgs[i] = imgs[j], imgs[j] = p,
-        c = names[i], names[i] = names[j], names[j] = c;
+  sortImagesByArea(nfiles, imgs, names);
 
   findpack(imgs, nfiles, coords);
 
-  outimg.height = outimg.width = 0;
-  for (i = 0; i < nfiles; ++i)
-  {
-    outimg.width = imax(outimg.width, imgs[i].width + coords[i].x);
-    outimg.height = imax(outimg.height, imgs[i].height + coords[i].y);
-  }
+  computeOutputType(&outimg.maxval, &outimg.format, outimg.tuple_type,
+                    &outimg.depth, nfiles, imgs);
+
+  computeOutputDimensions(&outimg.width, &outimg.height, nfiles, imgs, coords);
+
+  pnm_setminallocationdepth(&outimg, outimg.depth);
 
   outimg.size = sizeof(outimg);
   outimg.len = sizeof(outimg);
@@ -383,56 +560,23 @@ main(int argc, char **argv)
   outimg.bytes_per_sample = 0;
   for (i = outimg.maxval; i; i >>= 8)
     ++outimg.bytes_per_sample;
-
+ 
   writePam(&outimg, nfiles, coords, imgs);
 
-  if (datafname)
-  {
-    fprintf(data, ":0:0:%u:%u\n", outimg.width, outimg.height);
-
-    for (i = 0; i < nfiles; ++i)
-    {
-      fprintf(data, "%s:%u:%u:%u:%u\n", names[i], coords[i].x,
-          coords[i].y, imgs[i].width, imgs[i].height);
-    }
-  }
+  if (data)
+      writeData(data, outimg.width, outimg.height,
+                nfiles, names, coords, imgs);
 
-  if (headfname)
-  {
-    fprintf(header, "#define %sOVERALLX %u\n"
-                    "#define %sOVERALLY %u\n"
-                    "\n",
-                    prefix, outimg.width,
-                    prefix, outimg.height);
-
-    for (i = 0; i < nfiles; ++i)
-    {
-      *strchr(names[i], '.') = 0;
-      for (j = 0; names[i][j]; ++j)
-      {
-        if (ISLOWER(names[i][j]))
-          names[i][j] = TOUPPER(names[i][j]);
-      }
-      fprintf(header, "#define %s%sX %u\n"
-                      "#define %s%sY %u\n"
-                      "#define %s%sSZX %u\n"
-                      "#define %s%sSZY %u\n"
-                      "\n",
-                      prefix, names[i], coords[i].x,
-                      prefix, names[i], coords[i].y,
-                      prefix, names[i], imgs[i].width,
-                      prefix, names[i], imgs[i].height);
-    }
-  }
+  if (header)
+      writeHeader(header, cmdline.prefix, outimg.width, outimg.height,
+                  nfiles, names, coords, imgs);
 
   for (i = 0; i < nfiles; ++i)
     pm_close(imgs[i].file);
   pm_close(stdout);
-
-  if (headfname)
+  if (header)
     pm_close(header);
-
-  if (datafname)
+  if (data)
     pm_close(data);
 
   return 0;