home *** CD-ROM | disk | FTP | other *** search
/ Fractal Frenzy 1 / WalnutCreekFractalFrenzy-1.iso / pc / viewers / x11 / xv221.tz / xv221 / xv-2.21 / fsQuick.c < prev    next >
C/C++ Source or Header  |  1992-03-17  |  13KB  |  310 lines
  1. /* fsQuick.c 
  2. *
  3. * Quick and reasonably general halftoning code for taking grayscale-mapped
  4. * inputs to bit-packed bitmap output.  Uses a variation on Floyd-Steinberg
  5. * error diffusion that is much faster: propagate error to only two neighbors,
  6. * half to next row and half to next column (processing in serpentine raster
  7. * order).  Starts with some blue noise at the top edge.  Acts as if the top
  8. * row were repeated a number of times above the picture to avoid edge
  9. * effects at the top of the picture. At the end of each row, all error
  10. * is propagated to first pixel processed in the next row (none is lost).
  11. * Result is not much worse than standard F-S for most images I've tried,
  12. * and is several times faster than popular implementations of F-S.
  13. * Can be used for either possible black-white bit representation and either
  14. * possible bit order in output bitmap.
  15. *
  16. * BUGS:
  17. * o May be somewhat more prone to systematic artifacts in resulting bitmap than
  18. *    standard Floyd-Steinberg.
  19. * o Relies heavily on macros to avoid redundant code and runtime overhead; 
  20. *    produces fast but not compact code; may not work if your C doesn't like 
  21. *    very long lines of code after macro substitution.
  22. *
  23. * OTHER POSSIBLE IMPROVEMENTS:
  24. * o The macro dorows() should really be a function.
  25. * o Further optimization idea: remove postinc and predec of pointers and
  26. *    shifting of outword in dither1pix. Instead supply specific offsets and
  27. *    image pen mask as arguments to dither1pix. Will have to do this
  28. *    separately for the two raster directions. Should save another 10-20%?
  29. * o Should allow processing of one row per call, rather than whole image.
  30. * o Should be made to work for non-packed bitmap output.
  31. * o fsQTablesT should be made public so caller can have more flexibility to
  32. *    to set this instead of calling fsQInit?  Hmmm...  maybe not.
  33. *
  34. *             -David B Rosen (currently rosen@cns.bu.edu) Jan-Feb 1991
  35. */
  36.  
  37. /* fsQuick Copyright (C) 1991 by David B. Rosen.  All Rights Reserved.  This
  38. *  copyright notice applies only to fsQuick, not necessarily to the entire
  39. *  work it is distributed with or used in.  See also accompanying license.
  40. */
  41.  
  42. #include <stdio.h>
  43.  
  44. #define fsQTablesTYPE /* this is the private type definition */ \
  45. struct {  \
  46.   /* bit lookup tables going up and down columns in row: */ \
  47.   fsQBitmapT up[1<<fsQ_BITMAP_BITS], down[1<<fsQ_BITMAP_BITS]; \
  48. }
  49.  
  50. #include "fsQuick.h"
  51.  
  52. void FatalError fsQ_proto((char *message));
  53.  
  54. fsQ_RANDOM_DECL;
  55.  
  56. #ifndef NULL
  57. #define NULL ((void *)0)
  58. #endif /* NULL */
  59.  
  60. #ifndef TRUE
  61. #define TRUE 1
  62. #endif /* TRUE */
  63.  
  64. #define fsQ_MAXVAL (fsQ_PIC_VALS-1)
  65.  
  66. fsQTablesT *fsQInit(black, IsLSBFirst)
  67.      int black;
  68.      int IsLSBFirst;
  69. {
  70.   register int flipbits= -(black&0x1);
  71.   fsQBitmapT *bitTableLSBFirst=NULL, *bitTableMSBFirst=NULL;
  72.  
  73.   fsQTablesT *fsQTablesP;
  74.   if (!(fsQTablesP = (void *)malloc(sizeof(fsQTablesT))))
  75.     FatalError("not enough memory to fsQInit");
  76.  
  77.   if ((unsigned long)(fsQPicT)(fsQ_PIC_VALS-1) 
  78.       != (unsigned long)(fsQ_PIC_VALS-1))
  79.     FatalError("fsQInit: fsQ_PIC_VALS too large for type");
  80.  
  81.   if ((unsigned long)(fsQBitmapT)((((unsigned long)1)<<(fsQ_BITMAP_BITS))-1)
  82.       != ((((unsigned long)1)<<(fsQ_BITMAP_BITS))-1))
  83.     FatalError("fsQInit: fsQ_BITMAP_BITS too large for type");
  84.  
  85. #if fsQ_DEBUG
  86.   fprintf(stderr, 
  87.       "fsQInit: black=%d, flipbits=%x\n", (int)black, (int)flipbits);
  88. #endif /* fsQ_DEBUG */
  89.  
  90.   if (IsLSBFirst) {
  91.     bitTableMSBFirst=fsQTablesP->up;
  92.     bitTableLSBFirst=fsQTablesP->down;
  93.   } else {
  94.     bitTableLSBFirst=fsQTablesP->up;
  95.     bitTableMSBFirst=fsQTablesP->down;
  96.   }
  97.   { register int i;
  98.     for ( i=1<<fsQ_BITMAP_BITS; --i>=0; ) bitTableLSBFirst[i]= i^flipbits;
  99.   }
  100.  
  101.   { register int i;
  102.     for (i=(1<<fsQ_BITMAP_BITS); --i>=0; ){
  103.       register int entry=0, ibit;
  104.       for (ibit=fsQ_BITMAP_BITS; --ibit>=0; ) {
  105.     /* set bit ((fsQ_BITMAP_BITS-1)-ibit) to bit ibit: */
  106.     entry |= ( ((i>>ibit)&0x1) << ((fsQ_BITMAP_BITS-1)-ibit) );
  107.       }
  108.       bitTableMSBFirst[i] = entry^flipbits;
  109.     }
  110.   }
  111.   return fsQTablesP;
  112. }
  113.  
  114. void fsQuick(picture, gamma, nRows, nCols,
  115.            bitmap, bitTables, wordsPerRow)
  116.      const fsQPicT *picture;
  117.      const fsQPicT *gamma;
  118.      int nRows;
  119.      int nCols;
  120.      fsQBitmapT *bitmap;
  121.      const fsQTablesT *bitTables;
  122.      int wordsPerRow;
  123. {
  124.   int *errRow;
  125.   /* output words having all bits in image */
  126.   int nWholeWords=nCols/fsQ_BITMAP_BITS; 
  127.   
  128.   /* having bits in image < fsQ_BITMAP_BITS*/
  129.   int nExtraWords=wordsPerRow-nWholeWords; 
  130.  
  131.   register int err=0;
  132.  
  133.   /*These go up the cols of one row, down the next:*/
  134.   register fsQBitmapT *bitP = bitmap;
  135.  
  136.   register const fsQPicT *picP = picture;
  137.   /*This is just 1 row so it just goes up and back down again: */
  138.  
  139.   register int *errP;
  140.   register const fsQBitmapT *bitTable;
  141.  
  142. /* MACROS: */
  143. #define dither1pix(condition, predec, postinc)                            \
  144.   if (condition) { /* if-else optimized away with constant condition*/    \
  145.     /* Now err is residual error from previous pixel processed,       \
  146.            and * predec errP is resid. error from pixel above this one.*/ \
  147.                                                                       \
  148.     if (fsQ_DEBUG>2) {                                                    \
  149.       int * errPtmp = errP;                                              \
  150.       fprintf(stderr,                                                     \
  151.                 "dither1pix: rowsleft=%d, err=%d, * predec errP=%d",      \
  152.                 (int)rowsleft, (int)err, (int) * predec errPtmp);         \
  153.     }                                                                     \
  154.                                                                           \
  155.     err += * predec errP;                                                 \
  156.     /* Now err is the total error coming into this pixel */               \
  157.                                                                           \
  158.     { register int val = * predec picP postinc; /*intersperse loads*/     \
  159.       outword<<=1; /* shift the output image word */                      \
  160.       if (fsQ_DEBUG>2) {                                                  \
  161.         fprintf(stderr, ", pix val=%d", (int)gamma[val]);                 \
  162.       }                                                                   \
  163.       err += gamma[val];                                                  \
  164.     }                                                                     \
  165.                                                                           \
  166.     /* Now err stores net value for this pixel (not the error) */         \
  167.                                                                           \
  168.     if (fsQ_DEBUG>2) {                                                    \
  169.       fprintf(stderr, ", net val=%d\n", (int)err);                        \
  170.     }                                                                     \
  171.                                                                           \
  172.     if (err >= fsQ_THRESH_VAL) { /* compare net value to thresh */        \
  173.       /* this pixel will be white */                                      \
  174.       err -= fsQ_MAXVAL;                                                  \
  175.       outword |= 1;                                                       \
  176.     }                                                                     \
  177.                                                                           \
  178.     /* Now err is total residual error sent out from this pixel. */       \
  179.                                                                           \
  180.     *errP postinc = (err>>=1); /* half over, half down */                 \
  181.       /* Now * predec errP is resid. error sent to pixel below this one   \
  182.      and err is residual error sent to next pixel processed */        \
  183.   } else {                                                                \
  184.     predec errP postinc; /* just keep track of column this way */         \
  185.     outword<<=1; /* shift the output image word */                        \
  186.   }
  187.  
  188.  
  189.     /* The following macro performs the halftoning for fsQ_BITMAP_BITS pixels 
  190.        for each of nWords words in output bitmap. It propagates half of the 
  191.        error over to the next column (in err) and the rest down to the next 
  192.        row (in *errP).
  193.        This is much faster than using the Floyd-Steinberg coefficients and
  194.        propagating to four neighbors as is customary. It proceeds in
  195.        serpentine fashion (left-right, right-left, etc....) and at the end of
  196.        each row, _all_ of the error is propagated to the first pixel
  197.        processed in the next row, instead of throwing away the half that
  198.        would go off the edge. The innermost loop is fairly well optimized
  199.        when condition is constant, which it will be for almost all pixels.
  200.        
  201.        This macro references: 
  202.        gamma, err, errP, picP, bitP, bitTable, fsQ_MAXVAL, fsQ_THRESH_VAL
  203.        */
  204.  
  205. #define ditherword(nWords, condition, predec, postinc)                   \
  206. { register int iword;                                                    \
  207.   for (iword=nWords; --iword>=0; ) {                                     \
  208.     register int outword=0; /* output image word (offset in bitTable) */ \
  209.       /* Loop over fsQ_BITMAP_BITS columns, postincrementing or          \
  210.          predecrementing the input                                       \
  211.          pointer picP and error pointer errP and shifting outword: */    \
  212.                                                                          \
  213.     if (fsQ_BITMAP_BITS == 8) {                                          \
  214.       dither1pix(condition, predec, postinc);                            \
  215.       dither1pix(condition, predec, postinc);                            \
  216.       dither1pix(condition, predec, postinc);                            \
  217.       dither1pix(condition, predec, postinc);                            \
  218.       dither1pix(condition, predec, postinc);                            \
  219.       dither1pix(condition, predec, postinc);                            \
  220.       dither1pix(condition, predec, postinc);                            \
  221.       dither1pix(condition, predec, postinc);                            \
  222.     } else {                                                             \
  223.       { register int ibit;                                               \
  224.         for (ibit=fsQ_BITMAP_BITS; --ibit>=0; )                          \
  225.           dither1pix(condition, predec, postinc);                        \
  226.       }                                                                  \
  227.     }                                                                    \
  228.                                                                          \
  229.   * predec bitP postinc = bitTable[outword];   /* convert output word */ \
  230.   }                                                                      \
  231. }
  232.  
  233.  
  234. /* row loop macro: */
  235. #define dorows(nRows, nextRow) \
  236. { \
  237.     int rowsleft = nRows; \
  238.     while (TRUE) { \
  239.       if (--rowsleft<0) break; \
  240.       if ((rowsleft&63) == 0) WaitCursor();    /* JHB */ \
  241.       /* left to right with postincrement: */ \
  242. \
  243.       bitTable=bitTables->up; \
  244.       /* ditherword() with TRUE so if (condition)... is optimized away: */ \
  245.       ditherword(nWholeWords,               TRUE,   , ++); \
  246.       ditherword(nExtraWords,  errP<errRow+nCols,   , ++); \
  247.       /* now err + *--errP is residual error sent to highest col of next row*/\
  248. \
  249.       nextRow; \
  250. \
  251.       if (--rowsleft<0) break; \
  252.       /* right to left with predecrement: */ \
  253. \
  254.       bitTable=bitTables->down; \
  255.       ditherword(nExtraWords, errP<=errRow+nCols, --,   ); \
  256.       /* ditherword() with TRUE so if (condition)... is optimized away: */ \
  257.       ditherword(nWholeWords,               TRUE, --,   ); \
  258.       /* now err + *errP is residual error sent to lowest col of next row */ \
  259. \
  260.       nextRow; \
  261.     } \
  262. }
  263.  
  264. /* END OF MACROS.  BEGIN: */
  265.  
  266.   /* allocate vector of errors for columns in row: */
  267.   errRow = (int *) malloc(nCols * sizeof(int));
  268.   if (! errRow) FatalError("out of memory in fsQuick");
  269.  
  270.   errP= errRow; /* initialize pointer */
  271.  
  272.   { register int col;
  273.     for (col=nCols; --col>=0; ) {
  274.       if (fsQ_DEBUG>2) {
  275.     errRow[col]= 0;
  276.       } else {
  277.     /*Start w/ small random errors to avoid some weird systematic effects.*/
  278.     errRow[col]= (fsQ_RANDOM % (fsQ_MAXVAL+1) - fsQ_THRESH_VAL) /8;
  279.       }
  280.     }
  281.   }
  282.  
  283. #ifdef fsQ_NOSHORTCUT
  284.     /* This is a reality check that does the condition test for every pixel
  285.      as if we weren't sure that pixels in nWholeWords are all in the image. */
  286.     nWholeWords=0;
  287.     nExtraWords=wordsPerRow;
  288. #endif
  289.  
  290. /* To avoid edge effects at the top of the picture, extend the picture upwards
  291.    by replicating the top row several times.
  292.    Implement this by simply processing the top row several times: */
  293. dorows(fsQ_FIRST_ROW_EXTRAS, );
  294.  
  295. /* now process the whole actual image: */
  296. dorows(nRows,  bitP += wordsPerRow;  picP += nCols; );
  297.  
  298. #undef dorows
  299. #undef ditherword
  300. #undef dither1pix
  301.  
  302.   free(errRow);
  303. }
  304.  
  305. void fsQFree(fsQTablesP)
  306.      fsQTablesT *fsQTablesP;
  307. {
  308.   free(fsQTablesP);
  309. }
  310.