diff options
-rw-r--r-- | doc/HISTORY | 3 | ||||
-rw-r--r-- | editor/pnmmontage.c | 458 |
2 files changed, 304 insertions, 157 deletions
diff --git a/doc/HISTORY b/doc/HISTORY index e91f0960..92933b19 100644 --- a/doc/HISTORY +++ b/doc/HISTORY @@ -6,6 +6,9 @@ CHANGE HISTORY not yet BJH Release 10.41.00 + pnmmontage: new search algorithm to choose square + output quickly. Thanks "Nic Roets" <nroets@gmail.com>. + bmptopnm: fix crash with 16 bit images. pamlcolor8.map: Make it a 256 color map sorted by index, 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, ¤t[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, ¤t[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; |