From 4303fbdc450e651900e0a3cd856c0e56a4392dce Mon Sep 17 00:00:00 2001 From: giraffedata Date: Wed, 10 Mar 2010 16:25:17 +0000 Subject: speedup by afu git-svn-id: http://svn.code.sf.net/p/netpbm/code/trunk@1145 9d0c8265-081b-0410-96cb-a4ca84ce46f8 --- editor/pbmclean.c | 342 +++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 247 insertions(+), 95 deletions(-) (limited to 'editor/pbmclean.c') diff --git a/editor/pbmclean.c b/editor/pbmclean.c index 65b53e1c..e0ef1445 100644 --- a/editor/pbmclean.c +++ b/editor/pbmclean.c @@ -22,27 +22,6 @@ struct cmdlineInfo { unsigned int verbose; }; -#define PBM_INVERT(p) ((p) == PBM_WHITE ? PBM_BLACK : PBM_WHITE) - -/* input bitmap size and storage */ -static bit *inrow[3] ; - -#define THISROW (1) - -enum compass_heading { - WEST=0, - NORTHWEST=1, - NORTH=2, - NORTHEAST=3, - EAST=4, - SOUTHEAST=5, - SOUTH=6, - SOUTHWEST=7 -}; -/* compass directions from west clockwise. Indexed by enum compass_heading */ -int const xd[] = { -1, -1, 0, 1, 1, 1, 0, -1 } ; -int const yd[] = { 0, -1, -1, -1, 0, 1, 1, 1 } ; - static void parseCommandLine(int argc, char ** argv, struct cmdlineInfo *cmdlineP) { @@ -71,6 +50,8 @@ parseCommandLine(int argc, char ** argv, optParseOptions3(&argc, argv, opt, sizeof(opt), 0); /* Uses and sets argc, argv, and some of *cmdlineP and others. */ + free(option_def); + if (!black && !white) { cmdlineP->flipBlack = TRUE; cmdlineP->flipWhite = TRUE; @@ -79,7 +60,6 @@ parseCommandLine(int argc, char ** argv, cmdlineP->flipWhite = !!white; } - if (!minneighborsSpec) { /* Now we do a sleazy tour through the parameters to see if one is -N where N is a positive integer. That's for @@ -121,84 +101,219 @@ parseCommandLine(int argc, char ** argv, } +static unsigned int +bitpop8(unsigned char const x) { +/*---------------------------------------------------------------------------- + Return the number of 1 bits in 'x' +-----------------------------------------------------------------------------*/ +static unsigned int const p[256] = { + 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 }; + + return p[x]; +} +static unsigned int +bitpop24(uint32_t const w){ +/*---------------------------------------------------------------------------- + Return the number of 1 bits in the lower 24 bits of 'w' + A GCC builtin, __builtin_popcountl(), is available, but it + emits a call to an external function instead of inlining (GCC 4.4.3). + This table lookup method is faster. +-----------------------------------------------------------------------------*/ + return ( bitpop8((w>>16) & 0xff) + + bitpop8((w>>8) & 0xff) + + bitpop8(w & 0xff) ); +} -static void -nextrow(FILE * const ifd, - int const row, - int const cols, - int const rows, - int const format) { /*---------------------------------------------------------------------------- - Advance one row in the input. +Fast algorithm for counting friendly neighbor pixels + +In this program both input and output rows are in raw (packed) PBM format. + +We handle input rows in groups of three, named "prevrow", "thisrow", +"nextrow" and scan from left to right. At every byte boundary, 10 bits +are read from each of the three rows and placed into a temporary storage +we call "sample". + +prevrow: ... ... _______M NNNNNNNN O_______ ... +thisrow: ... ... _______W cCCCCCCC E_______ ... +nextrow: ... ... _______R SSSSSSSS T_______ ... + +sample : xxMNNNNNNNNOWcCCCCCCCERSSSSSSST - 'row' is the row number that will be the current row. +We count bits by taking the logical and of "sample" and a bit-mask called +"selection", and feeding the result to a table-based bit-population counter. + +For example, the bits around the leftmost bit of the byte ("c") are selected +like this: + +sample : xxMNNNNNNNNOWcCCCCCCCERSSSSSSST +selection: & | __111_______1_1_______111______ + +(In the actual process, "sample" is shifted right and anded against a + constant "selection" mask.) + +The above reports one bits. For the zero (white) bits we replace "sample" +with its inverse. + +If the friendly neighbor count is below a threshold (default 1), we record +that as a one bit in "flipmask". Bits are flipped in units of eight +and written to outrow at the byte boundary. -----------------------------------------------------------------------------*/ - bit * shuffle; - /* First, get the "next" row in inrow[2] if this is the very first - call to nextrow(). - */ - if (inrow[2] == NULL && row < rows) { - inrow[2] = pbm_allocrow(cols); - pbm_readpbmrow(ifd, inrow[2], cols, format); - } - /* Now advance the inrow[] window, rotating the buffer that now holds - the "previous" row to use it for the new "next" row. - */ - shuffle = inrow[0]; - - inrow[0] = inrow[1]; - inrow[1] = inrow[2]; - inrow[2] = shuffle ; - if (row+1 < rows) { - /* Read the "next" row in from the file. Allocate buffer if needed */ - if (inrow[2] == NULL) - inrow[2] = pbm_allocrow(cols); - pbm_readpbmrow(ifd, inrow[2], cols, format); - } else { - /* There is no next row */ - if (inrow[2]) { - pbm_freerow(inrow[2]); - inrow[2] = NULL; - } - } +static unsigned int +likeNeighbors(uint32_t const blackSample, + unsigned int const offset) { + + bool const thispoint = ( blackSample >> (18-offset) ) & 0x01; + uint32_t const sample = (thispoint == PBM_BLACK ) + ? blackSample + : ~ blackSample ; + uint32_t const selection = 0x701407; + + return ( bitpop24( ( sample >> (7-offset) ) & selection ) ); + } +static uint32_t +setSample(const bit * const prevrow, + const bit * const thisrow, + const bit * const nextrow, + unsigned int const col){ + uint32_t sample; + int col8 = col/8; -static unsigned int -likeNeighbors(bit * const inrow[3], - unsigned int const col, - unsigned int const cols) { - - int const point = inrow[THISROW][col]; - enum compass_heading heading; - int joined; - - joined = 0; /* initial value */ - for (heading = WEST; heading <= SOUTHWEST; ++heading) { - int x = col + xd[heading] ; - int y = THISROW + yd[heading] ; - if (x < 0 || x >= cols || !inrow[y]) { - if (point == PBM_WHITE) joined++; - } else if (inrow[y][x] == point) joined++ ; + sample = ( ( prevrow[col8 -1] ) << 29 ) + | ( ( prevrow[col8] ) << 21 ) + | ( ( prevrow[col8 +1] & 0x80 ) << 13 ) + | ( ( thisrow[col8 -1] & 0x01 ) << 19 ) + | ( ( thisrow[col8] ) << 11 ) + | ( ( thisrow[col8 +1] & 0x80 ) << 3 ) + | ( ( nextrow[col8 -1] & 0x01 ) << 9 ) + | ( ( nextrow[col8] ) << 1 ) + | ( ( nextrow[col8 +1] & 0x80 ) >> 7 ); + + return (sample); + +} + + +static unsigned char +setTestmask(unsigned char const whiteTestmask, + bool const testWhite, + bool const testBlack) { +/* ----------------------------------------------------------------------- + Make a byte pattern of what bits should be tested within a given "thisrow" + (current inrow) byte. 0 means test, 1 means skip. + -------------------------------------------------------------------------- */ + + if (testWhite == testBlack) /* Both are TRUE */ + return ( 0x00 ); + else if (testWhite == TRUE) /* testBlack is FALSE */ + return whiteTestmask; + else + return ~ whiteTestmask; +} + + +static int +cleanrow(const bit * const prevrow, + const bit * const thisrow, + const bit * const nextrow, + bit * const outrow, + int const cols, + unsigned int const threshold, + bool const flipWhite, + bool const flipBlack) { + /* ---------------------------------------------------------------------- + Work through row, scanning for bits that require flipping, and write + the results to outrow. + + Returns the number of bits flipped within this one row. + ------------------------------------------------------------------------- */ + + uint32_t sample; + unsigned char testmask; + unsigned char flipmask=0x00; + unsigned int col; + unsigned int nFlipped =0; + + for ( col=0 ; col < cols ; ++col) { + int const col8 = col/8; + unsigned int const offset = col%8; + + if(offset == 0) { + + if(flipmask != 0x00) { /* Some bits have to be flipped */ + outrow[col8 -1] = thisrow [col8 -1] ^ flipmask; + nFlipped += bitpop8(flipmask); + flipmask = 0x00; + } + else if ( col8 > 0) + outrow[col8 -1] = thisrow [col8 -1]; + + sample = setSample(prevrow, thisrow, nextrow, col); + testmask = setTestmask(thisrow[col8], flipWhite, flipBlack); } - return joined; + + if ( ( ( testmask << offset ) & 0x80 ) ==0 ){ + if ( likeNeighbors(sample, offset ) < threshold ) + flipmask |= (0x80 >> offset); + } + } + + /* Write out last byte */ + { + unsigned int col8Last = pbm_packed_bytes(cols) -1; + if(flipmask != 0x00) { + outrow[col8Last] = thisrow [col8Last] ^ flipmask; + nFlipped += bitpop8(flipmask); + } + else + outrow[col8Last] = thisrow [col8Last]; + } + + return nFlipped; + } + + int main(int argc, char *argv[]) { struct cmdlineInfo cmdline; FILE *ifp; - bit *outrow; + bit ** buffer; + bit * prevrow; + bit * thisrow; + bit * nextrow; + bit * outrow; + bit * edgerow; int cols, rows, format; unsigned int row; - unsigned int nFlipped; /* Number of pixels we have flipped so far */ + + double nFlipped = 0; /* Number of pixels we have flipped so far. + Use type double to prevent overflow. */ pbm_init( &argc, argv ); @@ -206,36 +321,73 @@ main(int argc, char *argv[]) { ifp = pm_openr(cmdline.inputFilespec); - inrow[0] = inrow[1] = inrow[2] = NULL; pbm_readpbminit(ifp, &cols, &rows, &format); + /* Initialize input buffers. + We add a margin of 8 bits each on the left and right of the rows. + + On the top and bottom of the image we place an imaginary blank row + ("edgerow") to facilitate the process. + */ + { + unsigned int i; + buffer = pbm_allocarray_packed(cols+16, 3); + edgerow = pbm_allocrow_packed(cols+16); + + for(i=0; i < pbm_packed_bytes(cols+16); ++i) + edgerow[i] = 0x00; + + for(i=0; i < 3; ++i) /* Add blank (all white) bytes beside the edges */ + buffer[i][0] = buffer[i][ pbm_packed_bytes( cols +16 ) -1 ] = 0x00; + + thisrow = &edgerow[1]; + nextrow = &buffer[0][1]; + + /* Read the top line into nextrow and clean the right end. */ + + pbm_readpbmrow_packed(ifp, nextrow, cols, format); + if (cols%8>0){ + nextrow[pbm_packed_bytes(cols) -1 ] >>= (8 - cols%8); + nextrow[pbm_packed_bytes(cols) -1 ] <<= (8 - cols%8); + } + } + outrow = pbm_allocrow(cols); pbm_writepbminit(stdout, cols, rows, 0) ; - nFlipped = 0; /* No pixels flipped yet */ for (row = 0; row < rows; ++row) { - unsigned int col; - nextrow(ifp, row, cols, rows, format); - for (col = 0; col < cols; ++col) { - bit const thispoint = inrow[THISROW][col]; - if ((cmdline.flipWhite && thispoint == PBM_WHITE) || - (cmdline.flipBlack && thispoint == PBM_BLACK)) { - if (likeNeighbors(inrow, col, cols) < cmdline.connect) { - outrow[col] = PBM_INVERT(thispoint); - ++nFlipped; - } else - outrow[col] = thispoint; - } else - outrow[col] = thispoint; - } - pbm_writepbmrow(stdout, outrow, cols, 0) ; + prevrow = thisrow; /* Slide up the input row window */ + thisrow = nextrow; + if( row < rows -1){ + nextrow = &buffer[(row+1)%3][1]; + /* We take the address directly instead of shuffling the rows + with the help of a temporary. This provision is for proper + handling of the initial edgerow. */ + + pbm_readpbmrow_packed(ifp, nextrow, cols, format); + if (cols%8>0){ + nextrow[pbm_packed_bytes(cols) -1 ] >>= (8 - cols%8); + nextrow[pbm_packed_bytes(cols) -1 ] <<= (8 - cols%8); + } } + else /* Bottom of image. */ + nextrow = & edgerow[1]; + + nFlipped += + cleanrow ( prevrow, thisrow, nextrow, outrow, cols, cmdline.connect, + cmdline.flipWhite, cmdline.flipBlack ); + + pbm_writepbmrow_packed(stdout, outrow, cols, 0) ; + } + + pbm_freearray(buffer,3); + pbm_freerow(edgerow); pbm_freerow(outrow); pm_close(ifp); if (cmdline.verbose) - pm_message("%d pixels flipped", nFlipped); + pm_message("%f pixels flipped", nFlipped); return 0; } -- cgit 1.4.1