/* pgmtopbm.c - read a portable graymap and write a portable bitmap ** ** Copyright (C) 1989 by Jef Poskanzer. ** ** Permission to use, copy, modify, and distribute this software and its ** documentation for any purpose and without fee is hereby granted, provided ** that the above copyright notice appear in all copies and that both that ** copyright notice and this permission notice appear in supporting ** documentation. This software is provided "as is" without express or ** implied warranty. */ #include #include "pm_c_util.h" #include "shhopt.h" #include "pgm.h" #include "dithers.h" #include "mallocvar.h" #include "rand.h" enum halftone {QT_FS, QT_THRESH, QT_DITHER8, QT_CLUSTER, QT_HILBERT}; struct CmdlineInfo { /* All the information the user supplied in the command line, in a form easy for the program to use. */ const char * inputFilespec; enum halftone halftone; unsigned int clumpSize; unsigned int clusterRadius; /* Defined only for halftone == QT_CLUSTER */ unsigned int randomSeed; unsigned int randomSeedSpec; /* Defined only for halftone == QT_FS */ float threshval; }; static void parseCommandLine(int argc, const char ** argv, struct CmdlineInfo *cmdlineP) { /*---------------------------------------------------------------------------- Note that the file spec array we return is stored in the storage that was passed to us as the argv array. -----------------------------------------------------------------------------*/ optEntry * option_def; /* Used by OPTENT3 */ optStruct3 opt; unsigned int option_def_index; unsigned int floydOpt, hilbertOpt, thresholdOpt, dither8Opt, cluster3Opt, cluster4Opt, cluster8Opt; unsigned int valueSpec, clumpSpec; MALLOCARRAY_NOFAIL(option_def, 100); option_def_index = 0; /* incremented by OPTENTRY */ OPTENT3(0, "floyd", OPT_FLAG, NULL, &floydOpt, 0); OPTENT3(0, "fs", OPT_FLAG, NULL, &floydOpt, 0); OPTENT3(0, "threshold", OPT_FLAG, NULL, &thresholdOpt, 0); OPTENT3(0, "hilbert", OPT_FLAG, NULL, &hilbertOpt, 0); OPTENT3(0, "dither8", OPT_FLAG, NULL, &dither8Opt, 0); OPTENT3(0, "d8", OPT_FLAG, NULL, &dither8Opt, 0); OPTENT3(0, "cluster3", OPT_FLAG, NULL, &cluster3Opt, 0); OPTENT3(0, "c3", OPT_FLAG, NULL, &cluster3Opt, 0); OPTENT3(0, "cluster4", OPT_FLAG, NULL, &cluster4Opt, 0); OPTENT3(0, "c4", OPT_FLAG, NULL, &cluster4Opt, 0); OPTENT3(0, "cluster8", OPT_FLAG, NULL, &cluster8Opt, 0); OPTENT3(0, "c8", OPT_FLAG, NULL, &cluster8Opt, 0); OPTENT3(0, "value", OPT_FLOAT, &cmdlineP->threshval, &valueSpec, 0); OPTENT3(0, "clump", OPT_UINT, &cmdlineP->clumpSize, &clumpSpec, 0); OPTENT3(0, "randomseed", OPT_UINT, &cmdlineP->randomSeed, &cmdlineP->randomSeedSpec, 0); opt.opt_table = option_def; opt.short_allowed = FALSE; /* We have no short (old-fashioned) options */ opt.allowNegNum = FALSE; /* We may have parms that are negative numbers */ pm_optParseOptions4(&argc, argv, opt, sizeof(opt), 0); /* Uses and sets argc, argv, and some of *cmdlineP and others. */ if (floydOpt + thresholdOpt + hilbertOpt + dither8Opt + cluster3Opt + cluster4Opt + cluster8Opt == 0) cmdlineP->halftone = QT_FS; else if (floydOpt + thresholdOpt + dither8Opt + cluster3Opt + cluster4Opt + cluster8Opt > 1) pm_error("No cannot specify more than one halftoning type"); else { if (floydOpt) cmdlineP->halftone = QT_FS; else if (thresholdOpt) cmdlineP->halftone = QT_THRESH; else if (hilbertOpt) cmdlineP->halftone = QT_HILBERT; else if (dither8Opt) cmdlineP->halftone = QT_DITHER8; else if (cluster3Opt) { cmdlineP->halftone = QT_CLUSTER; cmdlineP->clusterRadius = 3; } else if (cluster4Opt) { cmdlineP->halftone = QT_CLUSTER; cmdlineP->clusterRadius = 4; } else if (cluster8Opt) { cmdlineP->halftone = QT_CLUSTER; cmdlineP->clusterRadius = 8; } else pm_error("INTERNAL ERROR. No halftone option"); } if (!valueSpec) cmdlineP->threshval = 0.5; else { if (cmdlineP->threshval < 0.0) pm_error("-value cannot be negative. You specified %f", cmdlineP->threshval); if (cmdlineP->threshval > 1.0) pm_error("-value cannot be greater than one. You specified %f", cmdlineP->threshval); } if (!clumpSpec) cmdlineP->clumpSize = 5; else { if (cmdlineP->clumpSize < 2) pm_error("-clump must be at least 2. You specified %u", cmdlineP->clumpSize); } if (cmdlineP->halftone != QT_FS && cmdlineP->randomSeedSpec) pm_message ("Ignoring -randomseed value " "(meaningful only with Floyd-Steinberg)"); if (argc-1 > 1) pm_error("Too many arguments (%d). There is at most one " "non-option argument: the file name", argc-1); else if (argc-1 == 1) cmdlineP->inputFilespec = argv[1]; else cmdlineP->inputFilespec = "-"; } /* Hilbert curve tracer */ #define MAXORD 18 static int hil_order,hil_ord; static int hil_turn; static int hil_dx,hil_dy; static int hil_x,hil_y; static int hil_stage[MAXORD]; static int hil_width,hil_height; static void init_hilbert(int const w, int const h) { /*---------------------------------------------------------------------------- Initialize the Hilbert curve tracer -----------------------------------------------------------------------------*/ int big,ber; hil_width = w; hil_height = h; big = w > h ? w : h; for (ber = 2, hil_order = 1; ber < big; ber <<= 1, hil_order++); if (hil_order > MAXORD) pm_error("Sorry, hilbert order is too large"); hil_ord = hil_order; hil_order--; } static int hilbert(int * const px, int * const py) { /*---------------------------------------------------------------------------- Return non-zero if got another point -----------------------------------------------------------------------------*/ int temp; if (hil_ord > hil_order) { /* have to do first point */ hil_ord--; hil_stage[hil_ord] = 0; hil_turn = -1; hil_dy = 1; hil_dx = hil_x = hil_y = 0; *px = *py = 0; return 1; } /* Operate the state machine */ for(;;) { switch (hil_stage[hil_ord]) { case 0: hil_turn = -hil_turn; temp = hil_dy; hil_dy = -hil_turn * hil_dx; hil_dx = hil_turn * temp; if (hil_ord > 0) { hil_stage[hil_ord] = 1; hil_ord--; hil_stage[hil_ord]=0; continue; } case 1: hil_x += hil_dx; hil_y += hil_dy; if (hil_x < hil_width && hil_y < hil_height) { hil_stage[hil_ord] = 2; *px = hil_x; *py = hil_y; return 1; } case 2: hil_turn = -hil_turn; temp = hil_dy; hil_dy = -hil_turn * hil_dx; hil_dx = hil_turn * temp; if (hil_ord > 0) { /* recurse */ hil_stage[hil_ord] = 3; hil_ord--; hil_stage[hil_ord]=0; continue; } case 3: hil_x += hil_dx; hil_y += hil_dy; if (hil_x < hil_width && hil_y < hil_height) { hil_stage[hil_ord] = 4; *px = hil_x; *py = hil_y; return 1; } case 4: if (hil_ord > 0) { /* recurse */ hil_stage[hil_ord] = 5; hil_ord--; hil_stage[hil_ord]=0; continue; } case 5: temp = hil_dy; hil_dy = -hil_turn * hil_dx; hil_dx = hil_turn * temp; hil_turn = -hil_turn; hil_x += hil_dx; hil_y += hil_dy; if (hil_x < hil_width && hil_y < hil_height) { hil_stage[hil_ord] = 6; *px = hil_x; *py = hil_y; return 1; } case 6: if (hil_ord > 0) { /* recurse */ hil_stage[hil_ord] = 7; hil_ord--; hil_stage[hil_ord]=0; continue; } case 7: temp = hil_dy; hil_dy = -hil_turn * hil_dx; hil_dx = hil_turn * temp; hil_turn = -hil_turn; /* Return from a recursion */ if (hil_ord < hil_order) hil_ord++; else return 0; } } } static void doHilbert(FILE * const ifP, unsigned int const clump_size) { /*---------------------------------------------------------------------------- Use hilbert space filling curve dithering -----------------------------------------------------------------------------*/ /* * This is taken from the article "Digital Halftoning with * Space Filling Curves" by Luiz Velho, proceedings of * SIGRAPH '91, page 81. * * This is not a terribly efficient or quick version of * this algorithm, but it seems to work. - Graeme Gill. * graeme@labtam.labtam.OZ.AU * */ int cols, rows; gray maxval; gray **grays; bit **bits; int end; int *x,*y; int sum = 0; grays = pgm_readpgm(ifP, &cols,&rows, &maxval); bits = pbm_allocarray(cols,rows); MALLOCARRAY(x, clump_size); MALLOCARRAY(y, clump_size); if (x == NULL || y == NULL) pm_error("out of memory"); init_hilbert(cols,rows); end = clump_size; while (end == clump_size) { int i; /* compute the next clust co-ordinates along hilbert path */ for (i = 0; i < end; i++) { if (hilbert(&x[i],&y[i])==0) end = i; /* we reached the end */ } /* sum levels */ for (i = 0; i < end; i++) sum += grays[y[i]][x[i]]; /* dither half and half along path */ for (i = 0; i < end; i++) { if (sum >= maxval) { bits[y[i]][x[i]] = PBM_WHITE; sum -= maxval; } else bits[y[i]][x[i]] = PBM_BLACK; } } pbm_writepbm(stdout, bits, cols, rows, 0); } struct converter { void (*convertRow)(struct converter * const converterP, unsigned int const row, gray grayrow[], bit bitrow[]); void (*destroy)(struct converter * const converterP); unsigned int cols; gray maxval; void * stateP; }; /*============================================================================= Converter: fs =============================================================================*/ unsigned int const fs_scale = 1024; unsigned int const half_fs_scale = 512; struct fsState { long* thiserr; long* nexterr; bool fs_forward; long threshval; /* Threshold gray value, scaled by FS_SCALE */ }; static void fsConvertRow(struct converter * const converterP, unsigned int const row, gray grayrow[], bit bitrow[]) { struct fsState * const stateP = converterP->stateP; long * const thiserr = stateP->thiserr; long * const nexterr = stateP->nexterr; bit* bP; gray* gP; unsigned int limitcol; unsigned int col; for (col = 0; col < converterP->cols + 2; ++col) nexterr[col] = 0; if (stateP->fs_forward) { col = 0; limitcol = converterP->cols; gP = grayrow; bP = bitrow; } else { col = converterP->cols - 1; limitcol = -1; gP = &(grayrow[col]); bP = &(bitrow[col]); } do { long sum; sum = ((long) *gP * fs_scale) / converterP->maxval + thiserr[col + 1]; if (sum >= stateP->threshval) { *bP = PBM_WHITE; sum = sum - stateP->threshval - half_fs_scale; } else *bP = PBM_BLACK; if (stateP->fs_forward) { thiserr[col + 2] += (sum * 7) / 16; nexterr[col ] += (sum * 3) / 16; nexterr[col + 1] += (sum * 5) / 16; nexterr[col + 2] += (sum ) / 16; ++col; ++gP; ++bP; } else { thiserr[col ] += (sum * 7) / 16; nexterr[col + 2] += (sum * 3) / 16; nexterr[col + 1] += (sum * 5) / 16; nexterr[col ] += (sum ) / 16; --col; --gP; --bP; } } while (col != limitcol); stateP->thiserr = nexterr; stateP->nexterr = thiserr; stateP->fs_forward = ! stateP->fs_forward; } static void fsDestroy(struct converter * const converterP) { free(converterP->stateP); } static struct converter createFsConverter(unsigned int const cols, gray const maxval, float const threshFraction, unsigned int const randomSeedSpec, unsigned int const randomSeed) { struct fsState * stateP; struct converter converter; MALLOCVAR_NOFAIL(stateP); /* Initialize Floyd-Steinberg error vectors. */ MALLOCARRAY_NOFAIL(stateP->thiserr, cols + 2); MALLOCARRAY_NOFAIL(stateP->nexterr, cols + 2); { /* (random errors in [-fs_scale/8 .. fs_scale/8]) */ unsigned int col; struct pm_randSt randSt; pm_randinit(&randSt); pm_srand2(&randSt, randomSeedSpec, randomSeed); for (col = 0; col < cols + 2; ++col) stateP->thiserr[col] = (long)(pm_rand(&randSt) % fs_scale - half_fs_scale) / 4; pm_randterm(&randSt); } stateP->fs_forward = TRUE; stateP->threshval = threshFraction * fs_scale; converter.stateP = stateP; converter.cols = cols; converter.maxval = maxval; converter.convertRow = &fsConvertRow; converter.destroy = &fsDestroy; return converter; } /*============================================================================= Converter: thresh =============================================================================*/ struct threshState { gray threshval; }; static void threshConvertRow(struct converter * const converterP, unsigned int const row, gray grayrow[], bit bitrow[]) { struct threshState * const stateP = converterP->stateP; unsigned int col; for (col = 0; col < converterP->cols; ++col) if (grayrow[col] >= stateP->threshval) bitrow[col] = PBM_WHITE; else bitrow[col] = PBM_BLACK; } static void threshDestroy(struct converter * const converterP) { free(converterP->stateP); } static struct converter createThreshConverter(unsigned int const cols, gray const maxval, float const threshFraction) { struct threshState * stateP; struct converter converter; MALLOCVAR_NOFAIL(stateP); converter.cols = cols; converter.maxval = maxval; converter.convertRow = &threshConvertRow; converter.destroy = &threshDestroy; stateP->threshval = ROUNDU(maxval * threshFraction); converter.stateP = stateP; return converter; } /*============================================================================= Converter: dither8 =============================================================================*/ struct dither8State { int dither8[16][16]; }; static void dither8ConvertRow(struct converter * const converterP, unsigned int const row, gray grayrow[], bit bitrow[]) { struct dither8State * const stateP = converterP->stateP; unsigned int col; for (col = 0; col < converterP->cols; ++col) if (grayrow[col] > stateP->dither8[row % 16][col % 16]) bitrow[col] = PBM_WHITE; else bitrow[col] = PBM_BLACK; } static void dither8Destroy(struct converter * const converterP) { struct dither8State * const stateP = converterP->stateP; free(stateP); } static struct converter createDither8Converter(unsigned int const cols, gray const maxval) { struct converter converter; struct dither8State * stateP; unsigned int row; MALLOCVAR_NOFAIL(stateP); converter.cols = cols; converter.convertRow = &dither8ConvertRow; converter.destroy = dither8Destroy; converter.stateP = stateP; converter.maxval = maxval; /* Scale dither matrix. */ for (row = 0; row < 16; ++row) { unsigned int col; for (col = 0; col < 16; ++col) stateP->dither8[row][col] = dither8[row][col] * maxval / 256; } return converter; } /*============================================================================= Converter: cluster =============================================================================*/ struct clusterState { unsigned int radius; int ** clusterMatrix; }; static void clusterConvertRow(struct converter * const converterP, unsigned int const row, gray grayrow[], bit bitrow[]) { struct clusterState * const stateP = converterP->stateP; unsigned int const diameter = 2 * stateP->radius; unsigned int col; for (col = 0; col < converterP->cols; ++col) if (grayrow[col] > stateP->clusterMatrix[row % diameter][col % diameter]) bitrow[col] = PBM_WHITE; else bitrow[col] = PBM_BLACK; } static void clusterDestroy(struct converter * const converterP) { struct clusterState * const stateP = converterP->stateP; unsigned int const diameter = 2 * stateP->radius; unsigned int row; for (row = 0; row < diameter; ++row) free(stateP->clusterMatrix[row]); free(stateP->clusterMatrix); free(stateP); } static struct converter createClusterConverter(unsigned int const radius, unsigned int const cols, gray const maxval) { int const clusterNormalizer = radius * radius * 2; unsigned int const diameter = 2 * radius; struct converter converter; struct clusterState * stateP; unsigned int row; converter.cols = cols; converter.maxval = maxval; converter.convertRow = &clusterConvertRow; converter.destroy = &clusterDestroy; MALLOCVAR_NOFAIL(stateP); stateP->radius = radius; MALLOCARRAY_NOFAIL(stateP->clusterMatrix, diameter); for (row = 0; row < diameter; ++row) { unsigned int col; MALLOCARRAY_NOFAIL(stateP->clusterMatrix[row], diameter); for (col = 0; col < diameter; ++col) { int val; switch (radius) { case 3: val = cluster3[row][col]; break; case 4: val = cluster4[row][col]; break; case 8: val = cluster8[row][col]; break; default: pm_error("INTERNAL ERROR: invalid radius"); } stateP->clusterMatrix[row][col] = val * maxval / clusterNormalizer; } } converter.stateP = stateP; return converter; } int main(int argc, const char *argv[]) { struct CmdlineInfo cmdline; FILE * ifP; gray * grayrow; bit * bitrow; pm_proginit(&argc, argv); parseCommandLine(argc, argv, &cmdline); ifP = pm_openr(cmdline.inputFilespec); if (cmdline.halftone == QT_HILBERT) doHilbert(ifP, cmdline.clumpSize); else { struct converter converter; int cols, rows; gray maxval; int format; int row; pgm_readpgminit(ifP, &cols, &rows, &maxval, &format); pbm_writepbminit(stdout, cols, rows, 0); switch (cmdline.halftone) { case QT_FS: converter = createFsConverter(cols, maxval, cmdline.threshval, cmdline.randomSeedSpec, cmdline.randomSeed); break; case QT_THRESH: converter = createThreshConverter(cols, maxval, cmdline.threshval); break; case QT_DITHER8: converter = createDither8Converter(cols, maxval); break; case QT_CLUSTER: converter = createClusterConverter(cmdline.clusterRadius, cols, maxval); break; case QT_HILBERT: pm_error("INTERNAL ERROR: halftone is QT_HILBERT where it " "shouldn't be."); break; } grayrow = pgm_allocrow(cols); bitrow = pbm_allocrow(cols); for (row = 0; row < rows; ++row) { pgm_readpgmrow(ifP, grayrow, cols, maxval, format); converter.convertRow(&converter, row, grayrow, bitrow); pbm_writepbmrow(stdout, bitrow, cols, 0); } pbm_freerow(bitrow); pgm_freerow(grayrow); if (converter.destroy) converter.destroy(&converter); } pm_close(ifP); return 0; }