speedup by afu

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

1 files changed, 247 insertions, 95 deletions

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;
 }