/* pamflip.c - perform one or more flip operations on a Netpbm image ** ** 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. */ /* There is some fancy virtual memory management in this program to avoid page thrashing when you flip a large image in a columns-for-rows way (e.g. -transpose). The page thrashing we're trying to avoid could happen because the output of the transformation is stored in an array of xels in virtual memory. An xel array is stored in column-first order, meaning that all the columns of particular row are contiguous, the next row is next to that, etc. If you fill up that array by filling in Column 0 sequentially in every row from top to bottom, you will touch a lot of different virtual memory pages, and every one has to be paged in as you touch it. If the number of virtual memory pages you touch exceeds the amount of real memory the process can get, then by the time you hit the bottom of the xel array, the pages that hold the top are already paged out. So if you go back and do Column 1 from top to bottom, you will again touch lots of pages and have to page in every one of them. Do this for 100 columns, and you might page in every page in the array 100 times each, putting a few bytes in the page each time. That is very expensive. Instead, you'd like to keep the same pages in real memory as long as possible and fill them up as much as you can before paging them out and working on a new set of pages. You can do that by doing Column 0 from top to say Row 10, then Column 1 from top to Row 10, etc. all the way across the image. Assuming 10 rows fits in real memory, you will keep the virtual memory for the first 10 rows of the xel array in real memory until you've filled them in completely. Now you go back and do Column 0 from Row 11 to Row 20, then Column 1 from Row 11 to Row 20, and so on. So why are we even trying to fill in column by column instead of just filling in row by row? Because we're reading an input image row by row and transforming it in such a way that a row of the input becomes a column of the output. In order to fill in a whole row of the output, we'd have to read a whole column of the input, and then we have the same page thrashing problem in the input. So the optimal procedure is to do N output rows in each pass, where N is the largest number of rows we can fit in real memory. In each pass, we read certain columns of every row of the input and output every column of certain rows of the output. The output area for the rows in the pass gets paged in once during the pass and then never again. Note that some pages of every row of the input get paged in once in each pass too. As each input page is referenced only in one burst, input pages do not compete with output pages for real memory -- the working set is the output pages, which get referenced cyclically. */ #include #include #include "pam.h" #include "shhopt.h" #include "nstring.h" enum xformType {LEFTRIGHT, TOPBOTTOM, TRANSPOSE}; struct cmdlineInfo { /* All the information the user supplied in the command line, in a form easy for the program to use. */ const char *inputFilespec; /* Filespec of input file */ unsigned int xformCount; /* Number of transforms in the 'xformType' array */ enum xformType xformList[10]; /* Array of transforms to be applied, in order */ unsigned int availableMemory; unsigned int pageSize; unsigned int verbose; }; static void parseXformOpt(const char * const xformOpt, unsigned int * const xformCountP, enum xformType * const xformList) { /*---------------------------------------------------------------------------- Translate the -xform option string into an array of transform types. Return the array as xformList[], which is preallocated for at least 10 elements. -----------------------------------------------------------------------------*/ unsigned int xformCount; char * xformOptWork; char * cursor; bool eol; xformOptWork = strdup(xformOpt); cursor = &xformOptWork[0]; eol = FALSE; /* initial value */ xformCount = 0; /* initial value */ while (!eol && xformCount < 10) { const char * token; token = strsepN(&cursor, ","); if (token) { if (strcmp(token, "leftright") == 0) xformList[xformCount++] = LEFTRIGHT; else if (strcmp(token, "topbottom") == 0) xformList[xformCount++] = TOPBOTTOM; else if (strcmp(token, "transpose") == 0) xformList[xformCount++] = TRANSPOSE; else if (strcmp(token, "") == 0) { /* ignore it */} else pm_error("Invalid transform type in -xform option: '%s'", token ); } else eol = TRUE; } free(xformOptWork); *xformCountP = xformCount; } static void parseCommandLine(int argc, char ** const argv, struct cmdlineInfo * const 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 = malloc(100*sizeof(optEntry)); /* Instructions to OptParseOptions3 on how to parse our options. */ optStruct3 opt; unsigned int option_def_index; unsigned int lr, tb, xy, r90, r270, r180, null; unsigned int memsizeSpec, pagesizeSpec, xformSpec; unsigned int memsizeOpt; const char *xformOpt; option_def_index = 0; /* incremented by OPTENTRY */ OPTENT3(0, "lr", OPT_FLAG, NULL, &lr, 0); OPTENT3(0, "leftright", OPT_FLAG, NULL, &lr, 0); OPTENT3(0, "tb", OPT_FLAG, NULL, &tb, 0); OPTENT3(0, "topbottom", OPT_FLAG, NULL, &tb, 0); OPTENT3(0, "xy", OPT_FLAG, NULL, &xy, 0); OPTENT3(0, "transpose", OPT_FLAG, NULL, &xy, 0); OPTENT3(0, "r90", OPT_FLAG, NULL, &r90, 0); OPTENT3(0, "rotate90", OPT_FLAG, NULL, &r90, 0); OPTENT3(0, "ccw", OPT_FLAG, NULL, &r90, 0); OPTENT3(0, "r180", OPT_FLAG, NULL, &r180, 0); OPTENT3(0, "rotate180", OPT_FLAG, NULL, &r180, 0); OPTENT3(0, "r270", OPT_FLAG, NULL, &r270, 0); OPTENT3(0, "rotate270", OPT_FLAG, NULL, &r270, 0); OPTENT3(0, "cw", OPT_FLAG, NULL, &r270, 0); OPTENT3(0, "null", OPT_FLAG, NULL, &null, 0); OPTENT3(0, "verbose", OPT_FLAG, NULL, &cmdlineP->verbose, 0); OPTENT3(0, "memsize", OPT_UINT, &memsizeOpt, &memsizeSpec, 0); OPTENT3(0, "pagesize", OPT_UINT, &cmdlineP->pageSize, &pagesizeSpec, 0); OPTENT3(0, "xform", OPT_STRING, &xformOpt, &xformSpec, 0); opt.opt_table = option_def; opt.short_allowed = FALSE; /* We have no short (old-fashioned) options */ opt.allowNegNum = FALSE; /* We don't parms that are negative numbers */ optParseOptions3(&argc, argv, opt, sizeof(opt), 0); /* Uses and sets argc, argv, and some of *cmdlineP and others. */ if (lr + tb + xy + r90 + r180 + r270 + null > 1) pm_error("You may specify only one type of flip."); if (lr + tb + xy + r90 + r180 + r270 + null == 1) { if (lr) { cmdlineP->xformCount = 1; cmdlineP->xformList[0] = LEFTRIGHT; } else if (tb) { cmdlineP->xformCount = 1; cmdlineP->xformList[0] = TOPBOTTOM; } else if (xy) { cmdlineP->xformCount = 1; cmdlineP->xformList[0] = TRANSPOSE; } else if (r90) { cmdlineP->xformCount = 2; cmdlineP->xformList[0] = TRANSPOSE; cmdlineP->xformList[1] = TOPBOTTOM; } else if (r180) { cmdlineP->xformCount = 2; cmdlineP->xformList[0] = LEFTRIGHT; cmdlineP->xformList[1] = TOPBOTTOM; } else if (r270) { cmdlineP->xformCount = 2; cmdlineP->xformList[0] = TRANSPOSE; cmdlineP->xformList[1] = LEFTRIGHT; } else if (null) { cmdlineP->xformCount = 0; } } else if (xformSpec) parseXformOpt(xformOpt, &cmdlineP->xformCount, cmdlineP->xformList); else pm_error("You must specify an option such as -topbottom to indicate " "what kind of flip you want."); if (memsizeSpec) { if (memsizeOpt > UINT_MAX / 1024 / 1024) pm_error("-memsize value too large: %u MiB. Maximum this program " "can handle is %u MiB", memsizeOpt, UINT_MAX / 1024 / 1024); cmdlineP->availableMemory = memsizeOpt * 1024 *1024; } else cmdlineP->availableMemory = UINT_MAX; if (!pagesizeSpec) cmdlineP->pageSize = 4*1024; if (argc-1 == 0) cmdlineP->inputFilespec = "-"; else if (argc-1 != 1) pm_error("Program takes zero or one argument (filename). You " "specified %d", argc-1); else cmdlineP->inputFilespec = argv[1]; } struct xformMatrix { int a; int b; int c; int d; int e; int f; }; static void leftright(struct xformMatrix * const xformP) { xformP->a = - xformP->a; xformP->c = - xformP->c; xformP->e = - xformP->e + 1; } static void topbottom(struct xformMatrix * const xformP) { xformP->b = - xformP->b; xformP->d = - xformP->d; xformP->f = - xformP->f + 1; } static void swap(int * const xP, int * const yP) { int const t = *xP; *xP = *yP; *yP = t; } static void transpose(struct xformMatrix * const xformP) { swap(&xformP->a, &xformP->b); swap(&xformP->c, &xformP->d); swap(&xformP->e, &xformP->f); } static void computeXformMatrix(struct xformMatrix * const xformP, unsigned int const xformCount, enum xformType xformType[]) { struct xformMatrix const nullTransform = {1, 0, 0, 1, 0, 0}; unsigned int i; *xformP = nullTransform; /* initial value */ for (i = 0; i < xformCount; ++i) { switch (xformType[i]) { case LEFTRIGHT: leftright(xformP); break; case TOPBOTTOM: topbottom(xformP); break; case TRANSPOSE: transpose(xformP); break; } } } static void transformRowByRow(struct pam * const inpamP, struct pam * const outpamP, struct xformMatrix const xform) { tuple* tuplerow; tuple* newtuplerow; int row; tuplerow = pnm_allocpamrow(inpamP); newtuplerow = pnm_allocpamrow(outpamP); pnm_writepaminit(outpamP); for (row = 0; row < inpamP->height; ++row) { int col; pnm_readpamrow(inpamP, tuplerow); for (col = 0; col < inpamP->width; ++col) { /* Transform a point: ** ** [ a b 0 ] ** [ x y 1 ] [ c d 0 ] = [ x2 y2 1 ] ** [ e f 1 ] */ int const newcol = xform.a * col + xform.c * row + xform.e * (outpamP->width - 1); pnm_assigntuple(inpamP, newtuplerow[newcol], tuplerow[col]); } pnm_writepamrow(outpamP, newtuplerow); } pnm_freepamrow(tuplerow); pnm_freepamrow(newtuplerow); } static void __inline__ transformPoint( int const col, int const newcols, int const row, int const newrows, struct xformMatrix const xform, int * const newcolP, int * const newrowP ) { /* Transform a point: ** ** [ a b 0 ] ** [ x y 1 ] [ c d 0 ] = [ x2 y2 1 ] ** [ e f 1 ] */ *newcolP = xform.a * col + xform.c * row + xform.e * ( newcols - 1 ); *newrowP = xform.b * col + xform.d * row + xform.f * ( newrows - 1 ); } static unsigned int optimalSegmentSize(struct xformMatrix const xform, struct pam const pam, unsigned int const availableMemory, unsigned int const pageSize) { /*---------------------------------------------------------------------------- Compute the maximum number of columns that can be transformed, one row at a time, without causing page thrashing. See comments at the top of this file for an explanation of the kind of page thrashing using segments avoids. 'availableMemory' is the amount of real memory in bytes that this process should expect to be able to use. 'pageSize' is the size of a page in bytes. A page means the unit that is paged in or out. 'outputCols' is the number of columns in each row of the output array. 'format' is the format of the output array (PPM, etc.). -----------------------------------------------------------------------------*/ unsigned int segmentSize; if (xform.b == 0) segmentSize = pam.width; else { unsigned int const otherNeeds = 200*1024; /* A wild guess at how much real memory is needed by the program for purposes other than the output xel array. */ if (otherNeeds > availableMemory) segmentSize = pam.width; /* Can't prevent thrashing */ else { unsigned int const availablePages = (availableMemory - otherNeeds) / pageSize; if (availablePages <= 1) segmentSize = pam.width; /* Can't prevent thrashing */ else { unsigned int const bytesPerRow = pam.width * pam.depth * pam.bytes_per_sample; unsigned int rowsPerPage = MAX(1, (pageSize + (pageSize/2)) / bytesPerRow); /* This is how many consecutive rows we can touch on average while staying within the same page. */ segmentSize = availablePages * rowsPerPage; } } } return segmentSize; } static void transformNonPbm(struct pam * const inpamP, struct pam * const outpamP, struct xformMatrix const xform, unsigned int const segmentSize, bool const verbose) { /*---------------------------------------------------------------------------- Do the transform using "pam" library functions, as opposed to "pbm" ones. Assume input file is positioned to the raster (just after the header). 'segmentSize' is the number of columns we are to process in each pass. We do each segment going from left to right. For each segment, we do each row, going from top to bottom. For each row of the segment, we do each column, going from left to right. (The reason Caller wants it done by segments is to improve virtual memory reference locality. See comments at the top of this file). if 'segmentSize' is less than the whole image, ifP must be a seekable file. -----------------------------------------------------------------------------*/ pm_filepos imagepos; /* The input file position of the raster. But defined only if segment size is less than whole image. */ tuple* tuplerow; tuple** newtuples; unsigned int startCol; tuplerow = pnm_allocpamrow(inpamP); newtuples = pnm_allocpamarray(outpamP); if (segmentSize < inpamP->width) pm_tell2(inpamP->file, &imagepos, sizeof(imagepos)); for (startCol = 0; startCol < inpamP->width; startCol += segmentSize) { /* Do one set of columns which is small enough not to cause page thrashing. */ unsigned int const endCol = MIN(inpamP->width, startCol + segmentSize); unsigned int row; if (verbose) pm_message("Transforming Columns %u up to %u", startCol, endCol); if (startCol > 0) /* Go back to read from Row 0 again */ pm_seek2(inpamP->file, &imagepos, sizeof(imagepos)); for (row = 0; row < inpamP->height; ++row) { unsigned int col; pnm_readpamrow(inpamP, tuplerow); for (col = startCol; col < endCol; ++col) { int newcol, newrow; transformPoint(col, outpamP->width, row, outpamP->height, xform, &newcol, &newrow); pnm_assigntuple(inpamP, newtuples[newrow][newcol], tuplerow[col]); } } } pnm_writepam(outpamP, newtuples); pnm_freepamarray(newtuples, outpamP); pnm_freepamrow(tuplerow); } static void transformPbm(struct pam * const inpamP, struct pam * const outpamP, struct xformMatrix const xform) { /*---------------------------------------------------------------------------- This is the same as transformNonPbm, except that it uses less memory, since the PBM buffer format uses one bit per pixel instead of twelve bytes -----------------------------------------------------------------------------*/ bit* bitrow; bit** newbits; int row; bitrow = pbm_allocrow(inpamP->width); newbits = pbm_allocarray(pbm_packed_bytes(outpamP->width), outpamP->height); /* Initialize entire array to zeroes. One bits will be or'ed in later */ for (row = 0; row < outpamP->height; ++row) { int col; for (col = 0; col < pbm_packed_bytes(outpamP->width); ++col) newbits[row][col] = 0; } for (row = 0; row < inpamP->height; ++row) { int col; pbm_readpbmrow(inpamP->file, bitrow, inpamP->width, inpamP->format); for (col = 0; col < inpamP->width; ++col) { int newcol, newrow; transformPoint(col, outpamP->width, row, outpamP->height, xform, &newcol, &newrow); newbits[newrow][newcol/8] |= bitrow[col] << (7 - newcol % 8); /* Use of "|=" patterned after pbm_readpbmrow_packed. */ } } pbm_writepbminit(outpamP->file, outpamP->width, outpamP->height, outpamP->plainformat); for (row = 0; row < outpamP->height; ++row) pbm_writepbmrow_packed(outpamP->file, newbits[row], outpamP->width, outpamP->plainformat); pbm_freearray(newbits, outpamP->height); pbm_freerow(bitrow); } int main(int argc, char * argv[]) { struct cmdlineInfo cmdline; struct pam inpam; struct pam outpam; FILE* ifP; struct xformMatrix xform; pnm_init(&argc, argv); parseCommandLine(argc, argv, &cmdline); if (cmdline.availableMemory < UINT_MAX) ifP = pm_openr_seekable(cmdline.inputFilespec); else ifP = pm_openr(cmdline.inputFilespec); pnm_readpaminit(ifP, &inpam, sizeof(inpam)); computeXformMatrix(&xform, cmdline.xformCount, cmdline.xformList); outpam = inpam; /* initial value */ outpam.file = stdout; outpam.width = abs(xform.a) * inpam.width + abs(xform.c) * inpam.height; outpam.height = abs(xform.b) * inpam.width + abs(xform.d) * inpam.height; if (xform.b == 0 && xform.d == 1 && xform.f == 0) { /* In this case newrow is always equal to row, so we can do the transform line by line and avoid in-memory buffering altogether. */ if (cmdline.verbose) pm_message("Transforming row by row"); transformRowByRow(&inpam, &outpam, xform); } else { unsigned int const segmentSize = optimalSegmentSize(xform, outpam, cmdline.availableMemory, cmdline.pageSize); if (cmdline.verbose) { if (segmentSize < outpam.width) pm_message("Transforming %u columns of %u total at a time", segmentSize, outpam.width); else pm_message("Transforming entire image at once"); } /* Generic case. Read in the anymap a line at a time and transform it into an in-memory array. */ switch (PNM_FORMAT_TYPE(inpam.format)) { case PBM_TYPE: transformPbm(&inpam, &outpam, xform); break; default: transformNonPbm(&inpam, &outpam, xform, segmentSize, cmdline.verbose); break; } } pm_close(inpam.file); pm_close(outpam.file); exit(0); }