home *** CD-ROM | disk | FTP | other *** search
/ vsiftp.vmssoftware.com / VSIPUBLIC@vsiftp.vmssoftware.com.tar / FREEWARE / FREEWARE40.ZIP / xv310a / xv24to8.c < prev    next >
C/C++ Source or Header  |  1995-06-12  |  51KB  |  1,755 lines
  1. /*
  2.  * xv24to8.c  -  contains the 24-to-8-bit Conv24to8() procedure
  3.  *               and the 8-to-24-bit Conv8to24() procedure
  4.  *
  5.  * The Conv24to8 procedure takes a pointer to a 24-bit image (loaded
  6.  * previously).  The image will be a w * h * 3 byte array of
  7.  * bytes.  The image will be arranged with 3 bytes per pixel (in order
  8.  * R, G, and B), pixel 0 at the top left corner.  (As normal.)
  9.  * The procedure also takes a maximum number of colors to use (numcols)
  10.  * and pointers to three 256-long arrays of bytes (to hold the returned
  11.  * colormap)
  12.  *
  13.  * Note that Conv24to8() does NOT free the pic24 image under any circumstances
  14.  *
  15.  * The Conv24to8 procedure will set up the following:  it will allocate, make
  16.  * & return 'pic8', a 'w' by 'h' (passed in values) 8-bit picture.
  17.  * it will load up the rmap, gmap and bmap colormap arrays.  it will NOT 
  18.  * calculate numcols, since the cmap sort procedure has to be called anyway
  19.  *
  20.  * Conv24to8 returns 'pic8' if successful, 'NULL' on failure (presumably on a 
  21.  * malloc())
  22.  *
  23.  * The 'slow' code, while still based on Heckbert's Median Cut algorithm, 
  24.  * has been shamelessly lifted from the Independent JPEG Group's software
  25.  * (jquant2.c), as (for a variety of reasons) theirs was far better than 
  26.  * the version I was previously using.  Thanks guys!
  27.  *
  28.  * Also, as is my way, I've stripped out most of the IJG's well-written
  29.  * comments regarding their algorithm.  Folks interested in learning how it
  30.  * works are encouraged to look at the original source.  (jpeg/jquant2.c)
  31.  *
  32.  * contains:
  33.  *   Cont24to8()
  34.  *   Init24to8()
  35.  */
  36.  
  37. #include "copyright.h"
  38.  
  39. /*
  40.  * Portions Copyright (C) 1989, 1991 by Jef Poskanzer.  See copyright notice
  41.  * below, at the beginning of the relevant code.
  42.  */
  43.  
  44. #include "xv.h"
  45.  
  46. static int    quick_check PARM((byte*, int,int, byte*, byte*,byte*,byte*,int));
  47. static int    quick_quant PARM((byte*, int,int, byte*, byte*,byte*,byte*,int));
  48. static int    ppm_quant   PARM((byte *,int,int, byte*, byte*,byte*,byte*,int));
  49.  
  50. static int    slow_quant  PARM((byte*, int,int, byte*, byte*,byte*,byte*,int));
  51.  
  52. /****************************/
  53. void Init24to8()
  54. {
  55.   /* doesn't do anything anymore... */
  56. }
  57.  
  58.  
  59.  
  60. /****************************/
  61. byte *Conv24to8(pic24,w,h,nc,rm,gm,bm)
  62.      byte *pic24;
  63.      byte *rm, *gm, *bm;
  64.      int   w,h,nc;
  65. {
  66.   /* returns pointer to new 8-bit-per-pixel image (w*h) if successful, or
  67.      NULL if unsuccessful */
  68.   
  69.   int   i;
  70.   byte *pic8;
  71.   
  72.   if (!pic24) return NULL;
  73.  
  74.   pic8 = (byte *) malloc((size_t) (w * h));
  75.   if (!pic8) {
  76.     fprintf(stderr,"%s: Conv24to8() - failed to allocate 'pic8'\n",cmd);
  77.     return pic8;
  78.   }
  79.  
  80.   if (nc<=0) nc = 255;  /* 'nc == 0' breaks code */
  81.  
  82.   if (!noqcheck && quick_check(pic24, w,h, pic8, rm,gm,bm, nc)) { 
  83.     SetISTR(ISTR_INFO,"No color compression was necessary.\n");
  84.     return pic8;   
  85.   }
  86.  
  87.   switch (conv24) {
  88.   case CONV24_FAST:
  89.     SetISTR(ISTR_INFO,"Doing 'quick' 24-bit to 8-bit conversion.");
  90.     i = quick_quant(pic24, w, h, pic8, rm, gm, bm, nc);
  91.     break;
  92.     
  93.   case CONV24_BEST:
  94.     SetISTR(ISTR_INFO,"Doing 'best' 24-bit to 8-bit conversion.");
  95.     i = ppm_quant(pic24, w, h, pic8, rm, gm, bm, nc);
  96.     break;
  97.     
  98.   case CONV24_SLOW:
  99.   default:
  100.     SetISTR(ISTR_INFO,"Doing 'slow' 24-bit to 8-bit conversion.");
  101.     i = slow_quant(pic24, w, h, pic8, rm, gm, bm, nc);
  102.     break;
  103.   }
  104.   
  105.   if (i) { free(pic8);  pic8 = NULL; }
  106.   return pic8;
  107. }
  108.  
  109.  
  110. /***************************************************************/
  111. byte *Conv8to24(pic8, w, h, rmap,gmap,bmap)
  112.      byte *pic8, *rmap, *gmap, *bmap;
  113.      int   w, h;
  114. {
  115.   /* converts an w*h 8-bit image (with colormap rmap,gmap,bmap) into a
  116.    * 24-bit image.  Note, 'pic8' could be NULL
  117.    *
  118.    * returns pointer to new 24-bits-per-pixel image (w*h) if successful,
  119.    * or NULL if unsuccessful
  120.    */
  121.  
  122.   int   i;
  123.   byte *pic24, *sp, *dp;
  124.  
  125.   pic24 = (byte *) malloc((size_t) (w * h * 3));
  126.   if (!pic24) return pic24;
  127.  
  128.   for (i=w*h, sp=pic8, dp=pic24; i; i--, sp++) {
  129.     if ((i&0x1ffff)==0) WaitCursor();
  130.     *dp++ = rmap[*sp];
  131.     *dp++ = gmap[*sp];
  132.     *dp++ = bmap[*sp];
  133.   }
  134.  
  135.   return pic24;
  136. }
  137.   
  138.  
  139. /****************************/
  140. static int quick_check(pic24, w,h, pic8, rmap,gmap,bmap, maxcol)
  141.      byte *pic24, *pic8, *rmap, *gmap, *bmap;
  142.      int   w,h,maxcol;
  143. {
  144.   /* scans picture until it finds more than 'maxcol' different colors.  If it
  145.      finds more than 'maxcol' colors, it returns '0'.  If it DOESN'T, it does
  146.      the 24-to-8 conversion by simply sticking the colors it found into
  147.      a colormap, and changing instances of a color in pic24 into colormap
  148.      indicies (in pic8) */
  149.  
  150.   unsigned long colors[256],col;
  151.   int           i, nc, low, high, mid;
  152.   byte         *p, *pix;
  153.  
  154.   if (maxcol>256) maxcol = 256;
  155.  
  156.   /* put the first color in the table by hand */
  157.   nc = 0;  mid = 0;  
  158.  
  159.   for (i=w*h,p=pic24; i; i--) {
  160.     col  = (((u_long) *p++) << 16);  
  161.     col += (((u_long) *p++) << 8);
  162.     col +=  *p++;
  163.  
  164.     /* binary search the 'colors' array to see if it's in there */
  165.     low = 0;  high = nc-1;
  166.     while (low <= high) {
  167.       mid = (low+high)/2;
  168.       if      (col < colors[mid]) high = mid - 1;
  169.       else if (col > colors[mid]) low  = mid + 1;
  170.       else break;
  171.     }
  172.  
  173.     if (high < low) { /* didn't find color in list, add it. */
  174.       if (nc>=maxcol) return 0;
  175.       xvbcopy((char *) &colors[low], (char *) &colors[low+1],
  176.           (nc - low) * sizeof(u_long));
  177.       colors[low] = col;
  178.       nc++;
  179.     }
  180.   }
  181.  
  182.  
  183.   /* run through the data a second time, this time mapping pixel values in
  184.      pic24 into colormap offsets into 'colors' */
  185.  
  186.   for (i=w*h,p=pic24, pix=pic8; i; i--,pix++) {
  187.     col  = (((u_long) *p++) << 16);  
  188.     col += (((u_long) *p++) << 8);
  189.     col +=  *p++;
  190.  
  191.     /* binary search the 'colors' array.  It *IS* in there */
  192.     low = 0;  high = nc-1;
  193.     while (low <= high) {
  194.       mid = (low+high)/2;
  195.       if      (col < colors[mid]) high = mid - 1;
  196.       else if (col > colors[mid]) low  = mid + 1;
  197.       else break;
  198.     }
  199.  
  200.     if (high < low) {
  201.       fprintf(stderr,"quick_check:  impossible situation!\n");
  202.       exit(1);
  203.     }
  204.     *pix = mid;
  205.   }
  206.  
  207.   /* and load up the 'desired colormap' */
  208.   for (i=0; i<nc; i++) {
  209.     rmap[i] =  colors[i]>>16;  
  210.     gmap[i] = (colors[i]>>8) & 0xff;
  211.     bmap[i] =  colors[i]     & 0xff;
  212.   }
  213.  
  214.   return 1;
  215. }
  216.  
  217.  
  218.  
  219.  
  220. /************************************/
  221. static int quick_quant(p24,w,h, p8, rmap,gmap,bmap, nc)
  222.      byte *p24, *p8, *rmap, *gmap, *bmap;
  223.      int   w,h,nc;
  224. {
  225.   /* called after 'pic8' has been alloced, pWIDE,pHIGH set up, mono/1-bit
  226.      checked already */
  227.   
  228. /* up to 256 colors:     3 bits R, 3 bits G, 2 bits B  (RRRGGGBB) */
  229. #define RMASK      0xe0
  230. #define RSHIFT        0
  231. #define GMASK      0xe0
  232. #define GSHIFT        3
  233. #define BMASK      0xc0
  234. #define BSHIFT        6
  235.  
  236.   byte *pp;
  237.   int  r1, g1, b1;
  238.   int  *thisline, *nextline, *thisptr, *nextptr, *tmpptr;
  239.   int  i, j, val, pwide3;
  240.   int  imax, jmax;
  241.  
  242.   pp = p8;  pwide3 = w * 3;  imax = h-1;  jmax = w-1;
  243.  
  244.  
  245.   /* load up colormap:
  246.    *   note that 0 and 255 of each color are always in the map;
  247.    *   intermediate values are evenly spaced.
  248.    */
  249.  
  250.   for (i=0; i<256; i++) {
  251.     rmap[i] = (((i<<RSHIFT) & RMASK) * 255 + RMASK/2) / RMASK;
  252.     gmap[i] = (((i<<GSHIFT) & GMASK) * 255 + GMASK/2) / GMASK;
  253.     bmap[i] = (((i<<BSHIFT) & BMASK) * 255 + BMASK/2) / BMASK;
  254.   }
  255.   
  256.  
  257.   thisline = (int *) malloc(pwide3 * sizeof(int));
  258.   nextline = (int *) malloc(pwide3 * sizeof(int));
  259.   if (!thisline || !nextline) {
  260.     if (thisline) free(thisline);
  261.     if (nextline) free(nextline);
  262.     fprintf(stderr,"%s: unable to allocate memory in quick_quant()\n", cmd);
  263.     return(1);
  264.   }
  265.   
  266.   /* get first line of picture */
  267.   for (j=pwide3, tmpptr=nextline; j; j--) *tmpptr++ = (int) *p24++;
  268.   
  269.   for (i=0; i<h; i++) {
  270.     tmpptr = thisline;  thisline = nextline;  nextline = tmpptr;   /* swap */
  271.     
  272.     if ((i&0x3f) == 0) WaitCursor();
  273.  
  274.     if (i!=imax)   /* get next line */
  275.       for (j=pwide3, tmpptr=nextline; j; j--)
  276.     *tmpptr++ = (int) *p24++;
  277.     
  278.     for (j=0, thisptr=thisline, nextptr=nextline; j<w; j++,pp++) {
  279.       r1 = *thisptr++;  g1 = *thisptr++;  b1 = *thisptr++;
  280.       RANGE(r1,0,255);  RANGE(g1,0,255);  RANGE(b1,0,255);  
  281.       
  282.       /* choose actual pixel value */
  283.       val = (((r1&RMASK)>>RSHIFT) | ((g1&GMASK)>>GSHIFT) | 
  284.          ((b1&BMASK)>>BSHIFT));
  285.       *pp = val;
  286.       
  287.       /* compute color errors */
  288.       r1 -= rmap[val];
  289.       g1 -= gmap[val];
  290.       b1 -= bmap[val];
  291.       
  292.       /* Add fractions of errors to adjacent pixels */
  293.       if (j!=jmax) {  /* adjust RIGHT pixel */
  294.     thisptr[0] += (r1*7) / 16;
  295.     thisptr[1] += (g1*7) / 16;
  296.     thisptr[2] += (b1*7) / 16;
  297.       }
  298.       
  299.       if (i!=imax) {    /* do BOTTOM pixel */
  300.     nextptr[0] += (r1*5) / 16;
  301.     nextptr[1] += (g1*5) / 16;
  302.     nextptr[2] += (b1*5) / 16;
  303.  
  304.     if (j>0) {  /* do BOTTOM LEFT pixel */
  305.       nextptr[-3] += (r1*3) / 16;
  306.       nextptr[-2] += (g1*3) / 16;
  307.       nextptr[-1] += (b1*3) / 16;
  308.     }
  309.  
  310.     if (j!=jmax) {  /* do BOTTOM RIGHT pixel */
  311.       nextptr[3] += (r1)/16;
  312.       nextptr[4] += (g1)/16;
  313.       nextptr[5] += (b1)/16;
  314.     }
  315.     nextptr += 3;
  316.       }
  317.     }
  318.   }
  319.   
  320.   free(thisline);
  321.   free(nextline);
  322.   return 0;
  323.  
  324.  
  325. #undef RMASK
  326. #undef RSHIFT
  327. #undef GMASK
  328. #undef GSHIFT
  329. #undef BMASK
  330. #undef BSHIFT
  331. }
  332.       
  333.  
  334.  
  335.  
  336.  
  337.  
  338.  
  339. /***************************************************************/
  340. /* The following code based on code from the 'pbmplus' package */
  341. /* written by Jef Poskanzer                                    */
  342. /***************************************************************/
  343.  
  344.  
  345. /* ppmquant.c - quantize the colors in a pixmap down to a specified number
  346. **
  347. ** Copyright (C) 1989, 1991 by Jef Poskanzer.
  348. **
  349. ** Permission to use, copy, modify, and distribute this software and its
  350. ** documentation for any purpose and without fee is hereby granted, provided
  351. ** that the above copyright notice appear in all copies and that both that
  352. ** copyright notice and this permission notice appear in supporting
  353. ** documentation.  This software is provided "as is" without express or
  354. ** implied warranty.
  355. */
  356.  
  357.  
  358. typedef unsigned char pixval;
  359.  
  360. #define PPM_MAXMAXVAL 255
  361. typedef struct { pixval r, g, b; } pixel;
  362.  
  363. #define PPM_GETR(p) ((p).r)
  364. #define PPM_GETG(p) ((p).g)
  365. #define PPM_GETB(p) ((p).b)
  366.  
  367. #define PPM_ASSIGN(p,red,grn,blu) \
  368.   { (p).r = (red); (p).g = (grn); (p).b = (blu); }
  369.  
  370. #define PPM_EQUAL(p,q) ( (p).r == (q).r && (p).g == (q).g && (p).b == (q).b )
  371.  
  372.  
  373. /* Color scaling macro -- to make writing ppmtowhatever easier. */
  374.  
  375. #define PPM_DEPTH(newp,p,oldmaxval,newmaxval) \
  376.     PPM_ASSIGN( (newp), \
  377.             ((int) PPM_GETR(p)) * ((int)newmaxval) / ((int)oldmaxval), \
  378.             ((int) PPM_GETG(p)) * ((int)newmaxval) / ((int)oldmaxval), \
  379.             ((int) PPM_GETB(p)) * ((int)newmaxval) / ((int)oldmaxval) )
  380.  
  381.  
  382. /* Luminance macro. */
  383.  
  384. /* 
  385.  * #define PPM_LUMIN(p) \
  386.  *   ( 0.299 * PPM_GETR(p) + 0.587 * PPM_GETG(p) + 0.114 * PPM_GETB(p) )
  387.  */
  388.  
  389. /* Luminance macro, using only integer ops.  Returns an int (*256)  JHB */
  390. #define PPM_LUMIN(p) \
  391.   ( 77 * PPM_GETR(p) + 150 * PPM_GETG(p) + 29 * PPM_GETB(p) )
  392.  
  393. /* Color histogram stuff. */
  394.  
  395. typedef struct chist_item* chist_vec;
  396. struct chist_item { pixel color;
  397.             int value;
  398.               };
  399.  
  400. typedef struct chist_list_item* chist_list;
  401. struct chist_list_item { struct chist_item ch;
  402.                  chist_list next;
  403.                };
  404.  
  405. typedef chist_list* chash_table;
  406.  
  407. typedef struct box* box_vector;
  408. struct box {
  409.   int index;
  410.   int colors;
  411.   int sum;
  412. };
  413.  
  414.  
  415. #define MAXCOLORS 32767
  416. #define CLUSTER_MAXVAL 63
  417.  
  418. #define LARGE_LUM
  419. #define REP_AVERAGE_PIXELS
  420.  
  421. #define FS_SCALE 1024
  422.  
  423. #define HASH_SIZE 6553
  424.  
  425. #define ppm_hashpixel(p) ((((int) PPM_GETR(p) * 33023 +    \
  426.                 (int) PPM_GETG(p) * 30013 +    \
  427.                 (int) PPM_GETB(p) * 27011) & 0x7fffffff)   \
  428.               % HASH_SIZE)
  429.  
  430.  
  431.  
  432. /*** function defs ***/
  433.  
  434. static chist_vec   mediancut        PARM((chist_vec, int, int, int, int));
  435. static int         redcompare       PARM((const void *, const void *));
  436. static int         greencompare     PARM((const void *, const void *));
  437. static int         bluecompare      PARM((const void *, const void *));
  438. static int         sumcompare       PARM((const void *, const void *));
  439. static chist_vec   ppm_computechist PARM((pixel **, int,int,int,int *));
  440. static chash_table ppm_computechash PARM((pixel **, int,int,int,int *));
  441. static chist_vec   ppm_chashtochist PARM((chash_table, int));
  442. static chash_table ppm_allocchash   PARM((void));
  443. static void        ppm_freechist    PARM((chist_vec));
  444. static void        ppm_freechash    PARM((chash_table));
  445.  
  446.  
  447. /****************************************************************************/
  448. static int ppm_quant(pic24, cols, rows, pic8, rmap, gmap, bmap, newcolors)
  449.      byte *pic24, *pic8, *rmap, *gmap, *bmap;
  450.      int  cols, rows, newcolors;
  451. {
  452.   pixel**          pixels;
  453.   register pixel*  pP;
  454.   int              row;
  455.   register int     col, limitcol;
  456.   pixval           maxval, newmaxval;
  457.   int              colors;
  458.   register int     index;
  459.   chist_vec chv, colormap;
  460.   chash_table  cht;
  461.   int              i;
  462.   unsigned char    *picptr;
  463.   static char      *fn = "ppmquant()";
  464.  
  465.   index = 0;
  466.   maxval = 255;
  467.  
  468.   /*
  469.    *  reformat 24-bit pic24 image (3 bytes per pixel) into 2-dimensional
  470.    *  array of pixel structures
  471.    */
  472.  
  473.   if (DEBUG) fprintf(stderr,"%s: remapping to ppm-style internal fmt\n", fn);
  474.   WaitCursor();
  475.   
  476.   pixels = (pixel **) malloc(rows * sizeof(pixel *));
  477.   if (!pixels) FatalError("couldn't allocate 'pixels' array");
  478.   for (row=0; row<rows; row++) {
  479.     pixels[row] = (pixel *) malloc(cols * sizeof(pixel));
  480.     if (!pixels[row]) FatalError("couldn't allocate a row of pixels array");
  481.  
  482.     for (col=0, pP=pixels[row]; col<cols; col++, pP++) {
  483.       pP->r = *pic24++;
  484.       pP->g = *pic24++;
  485.       pP->b = *pic24++;
  486.     }
  487.   }
  488.   if (DEBUG) fprintf(stderr,"%s: done format remapping\n", fn);
  489.  
  490.  
  491.     
  492.  
  493.   /*
  494.    *  attempt to make a histogram of the colors, unclustered.
  495.    *  If at first we don't succeed, lower maxval to increase color
  496.    *  coherence and try again.  This will eventually terminate, with
  497.    *  maxval at worst 15, since 32^3 is approximately MAXCOLORS.
  498.    */
  499.  
  500.   WaitCursor();
  501.   for ( ; ; ) {
  502.     if (DEBUG) fprintf(stderr, "%s:  making histogram\n", fn);
  503.  
  504.     chv = ppm_computechist(pixels, cols, rows, MAXCOLORS, &colors);
  505.     if (chv != (chist_vec) 0) break;
  506.     
  507.     if (DEBUG) fprintf(stderr, "%s: too many colors!\n", fn);
  508.     newmaxval = maxval / 2;
  509.     if (DEBUG) fprintf(stderr, "%s: rescaling colors (maxval=%d) %s\n",
  510.                fn, newmaxval, "to improve clustering");
  511.  
  512.     for (row=0; row<rows; ++row)
  513.       for (col=0, pP=pixels[row]; col<cols; ++col, ++pP)
  514.     PPM_DEPTH( *pP, *pP, maxval, newmaxval );
  515.     maxval = newmaxval;
  516.   }
  517.  
  518.   if (DEBUG) fprintf(stderr,"%s: %d colors found\n", fn, colors);
  519.  
  520.  
  521.  
  522.   /*
  523.    * Step 3: apply median-cut to histogram, making the new colormap.
  524.    */
  525.  
  526.   WaitCursor();
  527.   if (DEBUG) fprintf(stderr, "%s: choosing %d colors\n", fn, newcolors);
  528.   colormap = mediancut(chv, colors, rows * cols, maxval, newcolors);
  529.   ppm_freechist(chv);
  530.  
  531.  
  532.  
  533.   /*
  534.    *  Step 4: map the colors in the image to their closest match in the
  535.    *  new colormap, and write 'em out.
  536.    */
  537.  
  538.   if (DEBUG) fprintf(stderr,"%s: mapping image to new colors\n", fn);
  539.   cht = ppm_allocchash();
  540.  
  541.   picptr = pic8;
  542.   for (row = 0;  row < rows;  ++row) {
  543.     col = 0;  limitcol = cols;  pP = pixels[row];
  544.  
  545.     ProgressMeter(0, rows-1, row, "24 -> 8");
  546.  
  547.     if ((row & 0x1f) == 0) WaitCursor();
  548.     do {
  549.       int hash;
  550.       chist_list chl;
  551.  
  552.       /* Check hash table to see if we have already matched this color. */
  553.  
  554.       hash = ppm_hashpixel(*pP);
  555.       for (chl = cht[hash];  chl;  chl = chl->next)
  556.     if (PPM_EQUAL(chl->ch.color, *pP)) {index = chl->ch.value; break;}
  557.  
  558.       if (!chl /*index = -1*/) {/* No; search colormap for closest match. */
  559.     register int i, r1, g1, b1, r2, g2, b2;
  560.     register long dist, newdist;
  561.  
  562.     r1 = PPM_GETR( *pP );
  563.     g1 = PPM_GETG( *pP );
  564.     b1 = PPM_GETB( *pP );
  565.     dist = 2000000000;
  566.  
  567.     for (i=0; i<newcolors; i++) {
  568.       r2 = PPM_GETR( colormap[i].color );
  569.       g2 = PPM_GETG( colormap[i].color );
  570.       b2 = PPM_GETB( colormap[i].color );
  571.  
  572.       newdist = ( r1 - r2 ) * ( r1 - r2 ) +
  573.                 ( g1 - g2 ) * ( g1 - g2 ) +
  574.                 ( b1 - b2 ) * ( b1 - b2 );
  575.  
  576.       if (newdist<dist) { index = i;  dist = newdist; }
  577.     }
  578.  
  579.     hash = ppm_hashpixel(*pP);
  580.     chl = (chist_list) malloc(sizeof(struct chist_list_item));
  581.     if (!chl) FatalError("ran out of memory adding to hash table");
  582.  
  583.     chl->ch.color = *pP;
  584.     chl->ch.value = index;
  585.     chl->next = cht[hash];
  586.     cht[hash] = chl;
  587.       }
  588.  
  589.       *picptr++ = index;
  590.  
  591.       ++col;
  592.       ++pP;
  593.     }
  594.     while (col != limitcol);
  595.   }
  596.  
  597.   /* rescale the colormap and load the XV colormap */
  598.   for (i=0; i<newcolors; i++) {
  599.     PPM_DEPTH(colormap[i].color, colormap[i].color, maxval, 255);
  600.     rmap[i] = PPM_GETR( colormap[i].color );
  601.     gmap[i] = PPM_GETG( colormap[i].color );
  602.     bmap[i] = PPM_GETB( colormap[i].color );
  603.   }
  604.  
  605.   /* free the pixels array */
  606.   for (i=0; i<rows; i++) free(pixels[i]);
  607.   free(pixels);
  608.  
  609.   /* free cht and colormap */
  610.   ppm_freechist(colormap);
  611.   ppm_freechash(cht);
  612.  
  613.   return 0;
  614. }
  615.  
  616.  
  617.  
  618. /*
  619. ** Here is the fun part, the median-cut colormap generator.  This is based
  620. ** on Paul Heckbert's paper "Color Image Quantization for Frame Buffer
  621. ** Display", SIGGRAPH '82 Proceedings, page 297.
  622. */
  623.  
  624.  
  625.  
  626. /****************************************************************************/
  627. static chist_vec mediancut( chv, colors, sum, maxval, newcolors )
  628.      chist_vec chv;
  629.      int colors, sum, newcolors;
  630.      int maxval;
  631. {
  632.   chist_vec colormap;
  633.   box_vector bv;
  634.   register int bi, i;
  635.   int boxes;
  636.  
  637.   bv = (box_vector) malloc(sizeof(struct box) * newcolors);
  638.   colormap = (chist_vec) 
  639.              malloc(sizeof(struct chist_item) * newcolors );
  640.  
  641.   if (!bv || !colormap) FatalError("unable to malloc in mediancut()");
  642.  
  643.   for (i=0; i<newcolors; i++)
  644.     PPM_ASSIGN(colormap[i].color, 0, 0, 0);
  645.  
  646.   /*
  647.    *  Set up the initial box.
  648.    */
  649.   bv[0].index = 0;
  650.   bv[0].colors = colors;
  651.   bv[0].sum = sum;
  652.   boxes = 1;
  653.  
  654.  
  655.   /*
  656.    ** Main loop: split boxes until we have enough.
  657.    */
  658.  
  659.   while ( boxes < newcolors ) {
  660.     register int indx, clrs;
  661.     int sm;
  662.     register int minr, maxr, ming, maxg, minb, maxb, v;
  663.     int halfsum, lowersum;
  664.  
  665.     /*
  666.      ** Find the first splittable box.
  667.      */
  668.     for (bi=0; bv[bi].colors<2 && bi<boxes; bi++) ;
  669.     if (bi == boxes) break;    /* ran out of colors! */
  670.  
  671.     indx = bv[bi].index;
  672.     clrs = bv[bi].colors;
  673.     sm = bv[bi].sum;
  674.  
  675.     /*
  676.      ** Go through the box finding the minimum and maximum of each
  677.      ** component - the boundaries of the box.
  678.      */
  679.     minr = maxr = PPM_GETR( chv[indx].color );
  680.     ming = maxg = PPM_GETG( chv[indx].color );
  681.     minb = maxb = PPM_GETB( chv[indx].color );
  682.  
  683.     for (i=1; i<clrs; i++) {
  684.       v = PPM_GETR( chv[indx + i].color );
  685.       if (v < minr) minr = v;
  686.       if (v > maxr) maxr = v;
  687.  
  688.       v = PPM_GETG( chv[indx + i].color );
  689.       if (v < ming) ming = v;
  690.       if (v > maxg) maxg = v;
  691.  
  692.       v = PPM_GETB( chv[indx + i].color );
  693.       if (v < minb) minb = v;
  694.       if (v > maxb) maxb = v;
  695.     }
  696.  
  697.     /*
  698.      ** Find the largest dimension, and sort by that component.  I have
  699.      ** included two methods for determining the "largest" dimension;
  700.      ** first by simply comparing the range in RGB space, and second
  701.      ** by transforming into luminosities before the comparison.  You
  702.      ** can switch which method is used by switching the commenting on
  703.      ** the LARGE_ defines at the beginning of this source file.
  704.      */
  705.     {
  706.       /* LARGE_LUM version */
  707.  
  708.       pixel p;
  709.       int rl, gl, bl;
  710.  
  711.       PPM_ASSIGN(p, maxr - minr, 0, 0);
  712.       rl = PPM_LUMIN(p);
  713.  
  714.       PPM_ASSIGN(p, 0, maxg - ming, 0);
  715.       gl = PPM_LUMIN(p);
  716.  
  717.       PPM_ASSIGN(p, 0, 0, maxb - minb);
  718.       bl = PPM_LUMIN(p);
  719.  
  720.       if (rl >= gl && rl >= bl)
  721.     qsort((char*) &(chv[indx]), (size_t) clrs, sizeof(struct chist_item),
  722.           redcompare );
  723.       else if (gl >= bl)
  724.     qsort((char*) &(chv[indx]), (size_t) clrs, sizeof(struct chist_item),
  725.           greencompare );
  726.       else 
  727.     qsort((char*) &(chv[indx]), (size_t) clrs, sizeof(struct chist_item),
  728.           bluecompare );
  729.     }
  730.  
  731.     /*
  732.      ** Now find the median based on the counts, so that about half the
  733.      ** pixels (not colors, pixels) are in each subdivision.
  734.      */
  735.     lowersum = chv[indx].value;
  736.     halfsum = sm / 2;
  737.     for (i=1; i<clrs-1; i++) {
  738.       if (lowersum >= halfsum) break;
  739.       lowersum += chv[indx + i].value;
  740.     }
  741.  
  742.     /*
  743.      ** Split the box, and sort to bring the biggest boxes to the top.
  744.      */
  745.     bv[bi].colors = i;
  746.     bv[bi].sum = lowersum;
  747.     bv[boxes].index = indx + i;
  748.     bv[boxes].colors = clrs - i;
  749.     bv[boxes].sum = sm - lowersum;
  750.     ++boxes;
  751.     qsort((char*) bv, (size_t) boxes, sizeof(struct box), sumcompare);
  752.   }  /* while (boxes ... */
  753.   
  754.   /*
  755.    ** Ok, we've got enough boxes.  Now choose a representative color for
  756.    ** each box.  There are a number of possible ways to make this choice.
  757.    ** One would be to choose the center of the box; this ignores any structure
  758.    ** within the boxes.  Another method would be to average all the colors in
  759.    ** the box - this is the method specified in Heckbert's paper.  A third
  760.    ** method is to average all the pixels in the box.  You can switch which
  761.    ** method is used by switching the commenting on the REP_ defines at
  762.    ** the beginning of this source file.
  763.    */
  764.   
  765.   for (bi=0; bi<boxes; bi++) {
  766.     /* REP_AVERAGE_PIXELS version */
  767.     register int indx = bv[bi].index;
  768.     register int clrs = bv[bi].colors;
  769.     register long r = 0, g = 0, b = 0, sum = 0;
  770.  
  771.     for (i=0; i<clrs; i++) {
  772.       r += PPM_GETR( chv[indx + i].color ) * chv[indx + i].value;
  773.       g += PPM_GETG( chv[indx + i].color ) * chv[indx + i].value;
  774.       b += PPM_GETB( chv[indx + i].color ) * chv[indx + i].value;
  775.       sum += chv[indx + i].value;
  776.     }
  777.  
  778.     r = r / sum;  if (r>maxval) r = maxval;    /* avoid math errors */
  779.     g = g / sum;  if (g>maxval) g = maxval;
  780.     b = b / sum;  if (b>maxval) b = maxval;
  781.  
  782.     PPM_ASSIGN( colormap[bi].color, r, g, b );
  783.   }
  784.  
  785.   free(bv);
  786.   return colormap;
  787. }
  788.  
  789.  
  790. /**********************************/
  791. static int redcompare(p1, p2)
  792.      const void *p1, *p2;
  793. {
  794.   return (int) PPM_GETR( ((chist_vec)p1)->color ) - 
  795.          (int) PPM_GETR( ((chist_vec)p2)->color );
  796. }
  797.  
  798. /**********************************/
  799. static int greencompare(p1, p2)
  800.      const void *p1, *p2;
  801. {
  802.   return (int) PPM_GETG( ((chist_vec)p1)->color ) - 
  803.          (int) PPM_GETG( ((chist_vec)p2)->color );
  804. }
  805.  
  806. /**********************************/
  807. static int bluecompare(p1, p2)
  808.      const void *p1, *p2;
  809. {
  810.   return (int) PPM_GETB( ((chist_vec)p1)->color ) - 
  811.          (int) PPM_GETB( ((chist_vec)p2)->color );
  812. }
  813.  
  814. /**********************************/
  815. static int sumcompare(p1, p2)
  816.      const void *p1, *p2;
  817. {
  818.   return ((box_vector) p2)->sum - ((box_vector) p1)->sum;
  819. }
  820.  
  821.  
  822.  
  823. /****************************************************************************/
  824. static chist_vec 
  825.   ppm_computechist(pixels, cols, rows, maxcolors, colorsP)
  826.      pixel** pixels;
  827.      int cols, rows, maxcolors;
  828.      int* colorsP;
  829. {
  830.   chash_table cht;
  831.   chist_vec chv;
  832.  
  833.   cht = ppm_computechash(pixels, cols, rows, maxcolors, colorsP);
  834.   if (!cht) return (chist_vec) 0;
  835.  
  836.   chv = ppm_chashtochist(cht, maxcolors);
  837.   ppm_freechash(cht);
  838.   return chv;
  839. }
  840.  
  841.  
  842. /****************************************************************************/
  843. static chash_table ppm_computechash(pixels, cols, rows, 
  844.                         maxcolors, colorsP )
  845.      pixel** pixels;
  846.      int cols, rows, maxcolors;
  847.      int* colorsP;
  848. {
  849.   chash_table cht;
  850.   register pixel* pP;
  851.   chist_list chl;
  852.   int col, row, hash;
  853.  
  854.   cht = ppm_allocchash( );
  855.   *colorsP = 0;
  856.  
  857.   /* Go through the entire image, building a hash table of colors. */
  858.   for (row=0; row<rows; row++)
  859.     for (col=0, pP=pixels[row];  col<cols;  col++, pP++) {
  860.       hash = ppm_hashpixel(*pP);
  861.  
  862.       for (chl = cht[hash]; chl != (chist_list) 0; chl = chl->next)
  863.     if (PPM_EQUAL(chl->ch.color, *pP)) break;
  864.       
  865.       if (chl != (chist_list) 0) ++(chl->ch.value);
  866.       else {
  867.     if ((*colorsP)++ > maxcolors) {
  868.       ppm_freechash(cht);
  869.       return (chash_table) 0;
  870.     }
  871.     
  872.     chl = (chist_list) malloc(sizeof(struct chist_list_item));
  873.     if (!chl) FatalError("ran out of memory computing hash table");
  874.  
  875.     chl->ch.color = *pP;
  876.     chl->ch.value = 1;
  877.     chl->next = cht[hash];
  878.     cht[hash] = chl;
  879.       }
  880.     }
  881.   
  882.   return cht;
  883. }
  884.  
  885.  
  886. /****************************************************************************/
  887. static chash_table ppm_allocchash()
  888. {
  889.   chash_table cht;
  890.   int i;
  891.  
  892.   cht = (chash_table) malloc( HASH_SIZE * sizeof(chist_list) );
  893.   if (!cht) FatalError("ran out of memory allocating hash table");
  894.  
  895.   for (i=0; i<HASH_SIZE; i++ )
  896.     cht[i] = (chist_list) 0;
  897.  
  898.   return cht;
  899. }
  900.  
  901.  
  902. /****************************************************************************/
  903. static chist_vec ppm_chashtochist( cht, maxcolors )
  904.      chash_table cht;
  905.      int maxcolors;
  906. {
  907.   chist_vec chv;
  908.   chist_list chl;
  909.   int i, j;
  910.  
  911.   /* Now collate the hash table into a simple chist array. */
  912.   chv = (chist_vec) malloc( maxcolors * sizeof(struct chist_item) );
  913.  
  914.   /* (Leave room for expansion by caller.) */
  915.   if (!chv) FatalError("ran out of memory generating histogram");
  916.  
  917.   /* Loop through the hash table. */
  918.   j = 0;
  919.   for (i=0; i<HASH_SIZE; i++)
  920.     for (chl = cht[i];  chl != (chist_list) 0;  chl = chl->next) {
  921.       /* Add the new entry. */
  922.       chv[j] = chl->ch;
  923.       ++j;
  924.     }
  925.  
  926.   return chv;
  927. }
  928.  
  929.  
  930. /****************************************************************************/
  931. static void ppm_freechist( chv )
  932.      chist_vec chv;
  933. {
  934.   free( (char*) chv );
  935. }
  936.  
  937.  
  938. /****************************************************************************/
  939. static void ppm_freechash( cht )
  940.      chash_table cht;
  941. {
  942.   int i;
  943.   chist_list chl, chlnext;
  944.  
  945.   for (i=0; i<HASH_SIZE; i++)
  946.     for (chl = cht[i];  chl != (chist_list) 0; chl = chlnext) {
  947.       chlnext = chl->next;
  948.       free( (char*) chl );
  949.     }
  950.  
  951.   free( (char*) cht );
  952. }
  953.  
  954.  
  955.  
  956.  
  957.  
  958. /***************************************************************/
  959. /* The following is based on jquant2.c from version 5          */
  960. /* of the IJG JPEG software, which is                          */
  961. /* Copyright (C) 1991-1994, Thomas G. Lane.                    */
  962. /***************************************************************/
  963.  
  964. #define MAXNUMCOLORS  256    /* maximum size of colormap */
  965.  
  966. #define C0_SCALE 2        /* scale R distances by this much */
  967. #define C1_SCALE 3        /* scale G distances by this much */
  968. #define C2_SCALE 1        /* and B by this much */
  969.  
  970. #define HIST_C0_BITS  5        /* bits of precision in R histogram */
  971. #define HIST_C1_BITS  6        /* bits of precision in G histogram */
  972. #define HIST_C2_BITS  5        /* bits of precision in B histogram */
  973.  
  974. /* Number of elements along histogram axes. */
  975. #define HIST_C0_ELEMS  (1<<HIST_C0_BITS)
  976. #define HIST_C1_ELEMS  (1<<HIST_C1_BITS)
  977. #define HIST_C2_ELEMS  (1<<HIST_C2_BITS)
  978.  
  979. /* These are the amounts to shift an input value to get a histogram index. */
  980. #define C0_SHIFT  (8-HIST_C0_BITS)
  981. #define C1_SHIFT  (8-HIST_C1_BITS)
  982. #define C2_SHIFT  (8-HIST_C2_BITS)
  983.  
  984.  
  985. typedef unsigned char JSAMPLE;
  986. typedef JSAMPLE * JSAMPROW;
  987.  
  988. typedef u_short histcell;    /* histogram cell; prefer an unsigned type */
  989.  
  990. typedef histcell * histptr;    /* for pointers to histogram cells */
  991.  
  992. typedef histcell hist1d[HIST_C2_ELEMS]; /* typedefs for the histogram array */
  993. typedef hist1d hist2d[HIST_C1_ELEMS];
  994. typedef hist2d hist3d[HIST_C0_ELEMS];
  995.  
  996. typedef short FSERROR;        /* 16 bits should be enough */
  997. typedef int LOCFSERROR;        /* use 'int' for calculation temps */
  998.  
  999. typedef FSERROR *FSERRPTR;    /* pointer to error array */
  1000.  
  1001. typedef struct {
  1002.   /* The bounds of the box (inclusive); expressed as histogram indexes */
  1003.   int c0min, c0max;
  1004.   int c1min, c1max;
  1005.   int c2min, c2max;
  1006.   /* The volume (actually 2-norm) of the box */
  1007.   INT32 volume;
  1008.   /* The number of nonzero histogram cells within this box */
  1009.   long colorcount;
  1010. } box;
  1011. typedef box * boxptr;
  1012.  
  1013. /* Local state for the IJG quantizer */
  1014.  
  1015. static hist2d * sl_histogram;    /* pointer to the 3D histogram array */
  1016. static FSERRPTR sl_fserrors;    /* accumulated-errors array */
  1017. static int * sl_error_limiter;    /* table for clamping the applied error */
  1018. static int sl_on_odd_row;    /* flag to remember which row we are on */
  1019. static JSAMPROW sl_colormap[3];    /* selected colormap */
  1020. static int sl_num_colors;    /* number of selected colors */
  1021.  
  1022.  
  1023. static void   slow_fill_histogram PARM((byte*, int));
  1024. static boxptr find_biggest_color_pop PARM((boxptr, int));
  1025. static boxptr find_biggest_volume PARM((boxptr, int));
  1026. static void   update_box PARM((boxptr));
  1027. static int    median_cut PARM((boxptr, int, int));
  1028. static void   compute_color PARM((boxptr, int));
  1029. static void   slow_select_colors PARM((int));
  1030. static int    find_nearby_colors PARM((int, int, int, JSAMPLE []));
  1031. static void   find_best_colors PARM((int,int,int,int, JSAMPLE [], JSAMPLE []));
  1032. static void   fill_inverse_cmap PARM((int, int, int));
  1033. static void   slow_map_pixels PARM((byte*, int, int, byte*));
  1034. static void   init_error_limit PARM((void));
  1035.  
  1036.  
  1037. /* Master control for slow quantizer. */
  1038. static int slow_quant(pic24, w, h, pic8, rm,gm,bm, descols)
  1039.      byte *pic24, *pic8, *rm, *gm, *bm;
  1040.      int   w, h, descols;
  1041. {
  1042.   size_t fs_arraysize = (w + 2) * (3 * sizeof(FSERROR));
  1043.  
  1044.   /* Allocate all the temporary storage needed */
  1045.   if (sl_error_limiter == NULL)
  1046.     init_error_limit();
  1047.   sl_histogram = (hist2d *) malloc(sizeof(hist3d));
  1048.   sl_fserrors = (FSERRPTR) malloc(fs_arraysize);
  1049.  
  1050.   if (! sl_error_limiter || ! sl_histogram || ! sl_fserrors) {
  1051.     /* we never free sl_error_limiter once acquired */
  1052.     if (sl_histogram) free(sl_histogram);
  1053.     if (sl_fserrors) free(sl_fserrors);
  1054.     fprintf(stderr,"%s: slow_quant() - failed to allocate workspace\n",cmd);
  1055.     return 1;
  1056.   }
  1057.  
  1058.   sl_colormap[0] = (JSAMPROW) rm;
  1059.   sl_colormap[1] = (JSAMPROW) gm;
  1060.   sl_colormap[2] = (JSAMPROW) bm;
  1061.  
  1062.   /* Compute the color histogram */
  1063.   slow_fill_histogram(pic24, w*h);
  1064.  
  1065.   /* Select the colormap */
  1066.   slow_select_colors(descols);
  1067.  
  1068.   /* Zero the histogram: now to be used as inverse color map */
  1069.   xvbzero((char *) sl_histogram, sizeof(hist3d));
  1070.  
  1071.   /* Initialize the propagated errors to zero. */
  1072.   xvbzero((char *) sl_fserrors, fs_arraysize);
  1073.   sl_on_odd_row = FALSE;
  1074.  
  1075.   /* Map the image. */
  1076.   slow_map_pixels(pic24, w, h, pic8);
  1077.  
  1078.   /* Release working memory. */
  1079.   /* we never free sl_error_limiter once acquired */
  1080.   free(sl_histogram);
  1081.   free(sl_fserrors);
  1082.  
  1083.   return 0;
  1084. }
  1085.  
  1086.  
  1087. static void slow_fill_histogram (pic24, numpixels)
  1088.      register byte *pic24;
  1089.      register int   numpixels;
  1090. {
  1091.   register histptr histp;
  1092.   register hist2d * histogram = sl_histogram;
  1093.  
  1094.   xvbzero((char *) histogram, sizeof(hist3d));
  1095.  
  1096.   while (numpixels-- > 0) {
  1097.     /* get pixel value and index into the histogram */
  1098.     histp = & histogram[pic24[0] >> C0_SHIFT]
  1099.                [pic24[1] >> C1_SHIFT]
  1100.                [pic24[2] >> C2_SHIFT];
  1101.     /* increment, check for overflow and undo increment if so. */
  1102.     if (++(*histp) <= 0)
  1103.       (*histp)--;
  1104.     pic24 += 3;
  1105.   }
  1106. }
  1107.  
  1108.  
  1109. static boxptr find_biggest_color_pop (boxlist, numboxes)
  1110.      boxptr boxlist;
  1111.      int numboxes;
  1112. {
  1113.   register boxptr boxp;
  1114.   register int i;
  1115.   register long maxc = 0;
  1116.   boxptr which = NULL;
  1117.   
  1118.   for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) {
  1119.     if (boxp->colorcount > maxc && boxp->volume > 0) {
  1120.       which = boxp;
  1121.       maxc = boxp->colorcount;
  1122.     }
  1123.   }
  1124.   return which;
  1125. }
  1126.  
  1127.  
  1128. static boxptr find_biggest_volume (boxlist, numboxes)
  1129.      boxptr boxlist;
  1130.      int numboxes;
  1131. {
  1132.   register boxptr boxp;
  1133.   register int i;
  1134.   register INT32 maxv = 0;
  1135.   boxptr which = NULL;
  1136.   
  1137.   for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) {
  1138.     if (boxp->volume > maxv) {
  1139.       which = boxp;
  1140.       maxv = boxp->volume;
  1141.     }
  1142.   }
  1143.   return which;
  1144. }
  1145.  
  1146.  
  1147. static void update_box (boxp)
  1148.      boxptr boxp;
  1149. {
  1150.   hist2d * histogram = sl_histogram;
  1151.   histptr histp;
  1152.   int c0,c1,c2;
  1153.   int c0min,c0max,c1min,c1max,c2min,c2max;
  1154.   INT32 dist0,dist1,dist2;
  1155.   long ccount;
  1156.   
  1157.   c0min = boxp->c0min;  c0max = boxp->c0max;
  1158.   c1min = boxp->c1min;  c1max = boxp->c1max;
  1159.   c2min = boxp->c2min;  c2max = boxp->c2max;
  1160.   
  1161.   if (c0max > c0min)
  1162.     for (c0 = c0min; c0 <= c0max; c0++)
  1163.       for (c1 = c1min; c1 <= c1max; c1++) {
  1164.     histp = & histogram[c0][c1][c2min];
  1165.     for (c2 = c2min; c2 <= c2max; c2++)
  1166.       if (*histp++ != 0) {
  1167.         boxp->c0min = c0min = c0;
  1168.         goto have_c0min;
  1169.       }
  1170.       }
  1171.  have_c0min:
  1172.   if (c0max > c0min)
  1173.     for (c0 = c0max; c0 >= c0min; c0--)
  1174.       for (c1 = c1min; c1 <= c1max; c1++) {
  1175.     histp = & histogram[c0][c1][c2min];
  1176.     for (c2 = c2min; c2 <= c2max; c2++)
  1177.       if (*histp++ != 0) {
  1178.         boxp->c0max = c0max = c0;
  1179.         goto have_c0max;
  1180.       }
  1181.       }
  1182.  have_c0max:
  1183.   if (c1max > c1min)
  1184.     for (c1 = c1min; c1 <= c1max; c1++)
  1185.       for (c0 = c0min; c0 <= c0max; c0++) {
  1186.     histp = & histogram[c0][c1][c2min];
  1187.     for (c2 = c2min; c2 <= c2max; c2++)
  1188.       if (*histp++ != 0) {
  1189.         boxp->c1min = c1min = c1;
  1190.         goto have_c1min;
  1191.       }
  1192.       }
  1193.  have_c1min:
  1194.   if (c1max > c1min)
  1195.     for (c1 = c1max; c1 >= c1min; c1--)
  1196.       for (c0 = c0min; c0 <= c0max; c0++) {
  1197.     histp = & histogram[c0][c1][c2min];
  1198.     for (c2 = c2min; c2 <= c2max; c2++)
  1199.       if (*histp++ != 0) {
  1200.         boxp->c1max = c1max = c1;
  1201.         goto have_c1max;
  1202.       }
  1203.       }
  1204.  have_c1max:
  1205.   if (c2max > c2min)
  1206.     for (c2 = c2min; c2 <= c2max; c2++)
  1207.       for (c0 = c0min; c0 <= c0max; c0++) {
  1208.     histp = & histogram[c0][c1min][c2];
  1209.     for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
  1210.       if (*histp != 0) {
  1211.         boxp->c2min = c2min = c2;
  1212.         goto have_c2min;
  1213.       }
  1214.       }
  1215.  have_c2min:
  1216.   if (c2max > c2min)
  1217.     for (c2 = c2max; c2 >= c2min; c2--)
  1218.       for (c0 = c0min; c0 <= c0max; c0++) {
  1219.     histp = & histogram[c0][c1min][c2];
  1220.     for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
  1221.       if (*histp != 0) {
  1222.         boxp->c2max = c2max = c2;
  1223.         goto have_c2max;
  1224.       }
  1225.       }
  1226.  have_c2max:
  1227.  
  1228.   dist0 = ((c0max - c0min) << C0_SHIFT) * C0_SCALE;
  1229.   dist1 = ((c1max - c1min) << C1_SHIFT) * C1_SCALE;
  1230.   dist2 = ((c2max - c2min) << C2_SHIFT) * C2_SCALE;
  1231.   boxp->volume = dist0*dist0 + dist1*dist1 + dist2*dist2;
  1232.   
  1233.   ccount = 0;
  1234.   for (c0 = c0min; c0 <= c0max; c0++)
  1235.     for (c1 = c1min; c1 <= c1max; c1++) {
  1236.       histp = & histogram[c0][c1][c2min];
  1237.       for (c2 = c2min; c2 <= c2max; c2++, histp++)
  1238.     if (*histp != 0) {
  1239.       ccount++;
  1240.     }
  1241.     }
  1242.   boxp->colorcount = ccount;
  1243. }
  1244.  
  1245.  
  1246. static int median_cut (boxlist, numboxes, desired_colors)
  1247.      boxptr boxlist;
  1248.      int numboxes, desired_colors;
  1249. {
  1250.   int n,lb;
  1251.   int c0,c1,c2,cmax;
  1252.   register boxptr b1,b2;
  1253.  
  1254.   while (numboxes < desired_colors) {
  1255.     /* Select box to split.
  1256.      * Current algorithm: by population for first half, then by volume.
  1257.      */
  1258.     if (numboxes*2 <= desired_colors) {
  1259.       b1 = find_biggest_color_pop(boxlist, numboxes);
  1260.     } else {
  1261.       b1 = find_biggest_volume(boxlist, numboxes);
  1262.     }
  1263.     if (b1 == NULL)        /* no splittable boxes left! */
  1264.       break;
  1265.     b2 = &boxlist[numboxes];    /* where new box will go */
  1266.     /* Copy the color bounds to the new box. */
  1267.     b2->c0max = b1->c0max; b2->c1max = b1->c1max; b2->c2max = b1->c2max;
  1268.     b2->c0min = b1->c0min; b2->c1min = b1->c1min; b2->c2min = b1->c2min;
  1269.     /* Choose which axis to split the box on.
  1270.      */
  1271.     c0 = ((b1->c0max - b1->c0min) << C0_SHIFT) * C0_SCALE;
  1272.     c1 = ((b1->c1max - b1->c1min) << C1_SHIFT) * C1_SCALE;
  1273.     c2 = ((b1->c2max - b1->c2min) << C2_SHIFT) * C2_SCALE;
  1274.     cmax = c1; n = 1;
  1275.     if (c0 > cmax) { cmax = c0; n = 0; }
  1276.     if (c2 > cmax) { n = 2; }
  1277.     switch (n) {
  1278.     case 0:
  1279.       lb = (b1->c0max + b1->c0min) / 2;
  1280.       b1->c0max = lb;
  1281.       b2->c0min = lb+1;
  1282.       break;
  1283.     case 1:
  1284.       lb = (b1->c1max + b1->c1min) / 2;
  1285.       b1->c1max = lb;
  1286.       b2->c1min = lb+1;
  1287.       break;
  1288.     case 2:
  1289.       lb = (b1->c2max + b1->c2min) / 2;
  1290.       b1->c2max = lb;
  1291.       b2->c2min = lb+1;
  1292.       break;
  1293.     }
  1294.     /* Update stats for boxes */
  1295.     update_box(b1);
  1296.     update_box(b2);
  1297.     numboxes++;
  1298.   }
  1299.   return numboxes;
  1300. }
  1301.  
  1302.  
  1303. static void compute_color (boxp, icolor)
  1304.      boxptr boxp;
  1305.      int icolor;
  1306. {
  1307.   /* Current algorithm: mean weighted by pixels (not colors) */
  1308.   /* Note it is important to get the rounding correct! */
  1309.   hist2d * histogram = sl_histogram;
  1310.   histptr histp;
  1311.   int c0,c1,c2;
  1312.   int c0min,c0max,c1min,c1max,c2min,c2max;
  1313.   long count;
  1314.   long total = 0;
  1315.   long c0total = 0;
  1316.   long c1total = 0;
  1317.   long c2total = 0;
  1318.   
  1319.   c0min = boxp->c0min;  c0max = boxp->c0max;
  1320.   c1min = boxp->c1min;  c1max = boxp->c1max;
  1321.   c2min = boxp->c2min;  c2max = boxp->c2max;
  1322.   
  1323.   for (c0 = c0min; c0 <= c0max; c0++)
  1324.     for (c1 = c1min; c1 <= c1max; c1++) {
  1325.       histp = & histogram[c0][c1][c2min];
  1326.       for (c2 = c2min; c2 <= c2max; c2++) {
  1327.     if ((count = *histp++) != 0) {
  1328.       total += count;
  1329.       c0total += ((c0 << C0_SHIFT) + ((1<<C0_SHIFT)>>1)) * count;
  1330.       c1total += ((c1 << C1_SHIFT) + ((1<<C1_SHIFT)>>1)) * count;
  1331.       c2total += ((c2 << C2_SHIFT) + ((1<<C2_SHIFT)>>1)) * count;
  1332.     }
  1333.       }
  1334.     }
  1335.   
  1336.   sl_colormap[0][icolor] = (JSAMPLE) ((c0total + (total>>1)) / total);
  1337.   sl_colormap[1][icolor] = (JSAMPLE) ((c1total + (total>>1)) / total);
  1338.   sl_colormap[2][icolor] = (JSAMPLE) ((c2total + (total>>1)) / total);
  1339. }
  1340.  
  1341.  
  1342. static void slow_select_colors (descolors)
  1343.      int descolors;
  1344. /* Master routine for color selection */
  1345. {
  1346.   box boxlist[MAXNUMCOLORS];
  1347.   int numboxes;
  1348.   int i;
  1349.  
  1350.   /* Initialize one box containing whole space */
  1351.   numboxes = 1;
  1352.   boxlist[0].c0min = 0;
  1353.   boxlist[0].c0max = 255 >> C0_SHIFT;
  1354.   boxlist[0].c1min = 0;
  1355.   boxlist[0].c1max = 255 >> C1_SHIFT;
  1356.   boxlist[0].c2min = 0;
  1357.   boxlist[0].c2max = 255 >> C2_SHIFT;
  1358.   /* Shrink it to actually-used volume and set its statistics */
  1359.   update_box(& boxlist[0]);
  1360.   /* Perform median-cut to produce final box list */
  1361.   numboxes = median_cut(boxlist, numboxes, descolors);
  1362.   /* Compute the representative color for each box, fill colormap */
  1363.   for (i = 0; i < numboxes; i++)
  1364.     compute_color(& boxlist[i], i);
  1365.   sl_num_colors = numboxes;
  1366. }
  1367.  
  1368.  
  1369. /* log2(histogram cells in update box) for each axis; this can be adjusted */
  1370. #define BOX_C0_LOG  (HIST_C0_BITS-3)
  1371. #define BOX_C1_LOG  (HIST_C1_BITS-3)
  1372. #define BOX_C2_LOG  (HIST_C2_BITS-3)
  1373.  
  1374. #define BOX_C0_ELEMS  (1<<BOX_C0_LOG) /* # of hist cells in update box */
  1375. #define BOX_C1_ELEMS  (1<<BOX_C1_LOG)
  1376. #define BOX_C2_ELEMS  (1<<BOX_C2_LOG)
  1377.  
  1378. #define BOX_C0_SHIFT  (C0_SHIFT + BOX_C0_LOG)
  1379. #define BOX_C1_SHIFT  (C1_SHIFT + BOX_C1_LOG)
  1380. #define BOX_C2_SHIFT  (C2_SHIFT + BOX_C2_LOG)
  1381.  
  1382.  
  1383. static int find_nearby_colors (minc0, minc1, minc2, colorlist)
  1384.      int minc0, minc1, minc2;
  1385.      JSAMPLE colorlist[];
  1386. {
  1387.   int numcolors = sl_num_colors;
  1388.   int maxc0, maxc1, maxc2;
  1389.   int centerc0, centerc1, centerc2;
  1390.   int i, x, ncolors;
  1391.   INT32 minmaxdist, min_dist, max_dist, tdist;
  1392.   INT32 mindist[MAXNUMCOLORS];    /* min distance to colormap entry i */
  1393.  
  1394.   maxc0 = minc0 + ((1 << BOX_C0_SHIFT) - (1 << C0_SHIFT));
  1395.   centerc0 = (minc0 + maxc0) >> 1;
  1396.   maxc1 = minc1 + ((1 << BOX_C1_SHIFT) - (1 << C1_SHIFT));
  1397.   centerc1 = (minc1 + maxc1) >> 1;
  1398.   maxc2 = minc2 + ((1 << BOX_C2_SHIFT) - (1 << C2_SHIFT));
  1399.   centerc2 = (minc2 + maxc2) >> 1;
  1400.  
  1401.   minmaxdist = 0x7FFFFFFFL;
  1402.  
  1403.   for (i = 0; i < numcolors; i++) {
  1404.     /* We compute the squared-c0-distance term, then add in the other two. */
  1405.     x = sl_colormap[0][i];
  1406.     if (x < minc0) {
  1407.       tdist = (x - minc0) * C0_SCALE;
  1408.       min_dist = tdist*tdist;
  1409.       tdist = (x - maxc0) * C0_SCALE;
  1410.       max_dist = tdist*tdist;
  1411.     } else if (x > maxc0) {
  1412.       tdist = (x - maxc0) * C0_SCALE;
  1413.       min_dist = tdist*tdist;
  1414.       tdist = (x - minc0) * C0_SCALE;
  1415.       max_dist = tdist*tdist;
  1416.     } else {
  1417.       /* within cell range so no contribution to min_dist */
  1418.       min_dist = 0;
  1419.       if (x <= centerc0) {
  1420.     tdist = (x - maxc0) * C0_SCALE;
  1421.     max_dist = tdist*tdist;
  1422.       } else {
  1423.     tdist = (x - minc0) * C0_SCALE;
  1424.     max_dist = tdist*tdist;
  1425.       }
  1426.     }
  1427.  
  1428.     x = sl_colormap[1][i];
  1429.     if (x < minc1) {
  1430.       tdist = (x - minc1) * C1_SCALE;
  1431.       min_dist += tdist*tdist;
  1432.       tdist = (x - maxc1) * C1_SCALE;
  1433.       max_dist += tdist*tdist;
  1434.     } else if (x > maxc1) {
  1435.       tdist = (x - maxc1) * C1_SCALE;
  1436.       min_dist += tdist*tdist;
  1437.       tdist = (x - minc1) * C1_SCALE;
  1438.       max_dist += tdist*tdist;
  1439.     } else {
  1440.       /* within cell range so no contribution to min_dist */
  1441.       if (x <= centerc1) {
  1442.     tdist = (x - maxc1) * C1_SCALE;
  1443.     max_dist += tdist*tdist;
  1444.       } else {
  1445.     tdist = (x - minc1) * C1_SCALE;
  1446.     max_dist += tdist*tdist;
  1447.       }
  1448.     }
  1449.  
  1450.     x = sl_colormap[2][i];
  1451.     if (x < minc2) {
  1452.       tdist = (x - minc2) * C2_SCALE;
  1453.       min_dist += tdist*tdist;
  1454.       tdist = (x - maxc2) * C2_SCALE;
  1455.       max_dist += tdist*tdist;
  1456.     } else if (x > maxc2) {
  1457.       tdist = (x - maxc2) * C2_SCALE;
  1458.       min_dist += tdist*tdist;
  1459.       tdist = (x - minc2) * C2_SCALE;
  1460.       max_dist += tdist*tdist;
  1461.     } else {
  1462.       /* within cell range so no contribution to min_dist */
  1463.       if (x <= centerc2) {
  1464.     tdist = (x - maxc2) * C2_SCALE;
  1465.     max_dist += tdist*tdist;
  1466.       } else {
  1467.     tdist = (x - minc2) * C2_SCALE;
  1468.     max_dist += tdist*tdist;
  1469.       }
  1470.     }
  1471.  
  1472.     mindist[i] = min_dist;    /* save away the results */
  1473.     if (max_dist < minmaxdist)
  1474.       minmaxdist = max_dist;
  1475.   }
  1476.  
  1477.   ncolors = 0;
  1478.   for (i = 0; i < numcolors; i++) {
  1479.     if (mindist[i] <= minmaxdist)
  1480.       colorlist[ncolors++] = (JSAMPLE) i;
  1481.   }
  1482.   return ncolors;
  1483. }
  1484.  
  1485.  
  1486. static void find_best_colors (minc0, minc1, minc2, numcolors,
  1487.                   colorlist, bestcolor)
  1488.      int minc0, minc1, minc2, numcolors;
  1489.      JSAMPLE colorlist[];
  1490.      JSAMPLE bestcolor[];
  1491. {
  1492.   int ic0, ic1, ic2;
  1493.   int i, icolor;
  1494.   register INT32 * bptr;    /* pointer into bestdist[] array */
  1495.   JSAMPLE * cptr;        /* pointer into bestcolor[] array */
  1496.   INT32 dist0, dist1;        /* initial distance values */
  1497.   register INT32 dist2;        /* current distance in inner loop */
  1498.   INT32 xx0, xx1;        /* distance increments */
  1499.   register INT32 xx2;
  1500.   INT32 inc0, inc1, inc2;    /* initial values for increments */
  1501.   /* This array holds the distance to the nearest-so-far color for each cell */
  1502.   INT32 bestdist[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];
  1503.  
  1504.   /* Initialize best-distance for each cell of the update box */
  1505.   bptr = bestdist;
  1506.   for (i = BOX_C0_ELEMS*BOX_C1_ELEMS*BOX_C2_ELEMS-1; i >= 0; i--)
  1507.     *bptr++ = 0x7FFFFFFFL;
  1508.   
  1509.   /* Nominal steps between cell centers ("x" in Thomas article) */
  1510. #define STEP_C0  ((1 << C0_SHIFT) * C0_SCALE)
  1511. #define STEP_C1  ((1 << C1_SHIFT) * C1_SCALE)
  1512. #define STEP_C2  ((1 << C2_SHIFT) * C2_SCALE)
  1513.   
  1514.   for (i = 0; i < numcolors; i++) {
  1515.     icolor = colorlist[i];
  1516.     /* Compute (square of) distance from minc0/c1/c2 to this color */
  1517.     inc0 = (minc0 - (int) sl_colormap[0][icolor]) * C0_SCALE;
  1518.     dist0 = inc0*inc0;
  1519.     inc1 = (minc1 - (int) sl_colormap[1][icolor]) * C1_SCALE;
  1520.     dist0 += inc1*inc1;
  1521.     inc2 = (minc2 - (int) sl_colormap[2][icolor]) * C2_SCALE;
  1522.     dist0 += inc2*inc2;
  1523.     /* Form the initial difference increments */
  1524.     inc0 = inc0 * (2 * STEP_C0) + STEP_C0 * STEP_C0;
  1525.     inc1 = inc1 * (2 * STEP_C1) + STEP_C1 * STEP_C1;
  1526.     inc2 = inc2 * (2 * STEP_C2) + STEP_C2 * STEP_C2;
  1527.     /* Now loop over all cells in box, updating distance per Thomas method */
  1528.     bptr = bestdist;
  1529.     cptr = bestcolor;
  1530.     xx0 = inc0;
  1531.     for (ic0 = BOX_C0_ELEMS-1; ic0 >= 0; ic0--) {
  1532.       dist1 = dist0;
  1533.       xx1 = inc1;
  1534.       for (ic1 = BOX_C1_ELEMS-1; ic1 >= 0; ic1--) {
  1535.     dist2 = dist1;
  1536.     xx2 = inc2;
  1537.     for (ic2 = BOX_C2_ELEMS-1; ic2 >= 0; ic2--) {
  1538.       if (dist2 < *bptr) {
  1539.         *bptr = dist2;
  1540.         *cptr = (JSAMPLE) icolor;
  1541.       }
  1542.       dist2 += xx2;
  1543.       xx2 += 2 * STEP_C2 * STEP_C2;
  1544.       bptr++;
  1545.       cptr++;
  1546.     }
  1547.     dist1 += xx1;
  1548.     xx1 += 2 * STEP_C1 * STEP_C1;
  1549.       }
  1550.       dist0 += xx0;
  1551.       xx0 += 2 * STEP_C0 * STEP_C0;
  1552.     }
  1553.   }
  1554. }
  1555.  
  1556.  
  1557. static void fill_inverse_cmap (c0, c1, c2)
  1558.      int c0, c1, c2;
  1559. {
  1560.   hist2d * histogram = sl_histogram;
  1561.   int minc0, minc1, minc2;    /* lower left corner of update box */
  1562.   int ic0, ic1, ic2;
  1563.   register JSAMPLE * cptr;    /* pointer into bestcolor[] array */
  1564.   register histptr cachep;    /* pointer into main cache array */
  1565.   /* This array lists the candidate colormap indexes. */
  1566.   JSAMPLE colorlist[MAXNUMCOLORS];
  1567.   int numcolors;        /* number of candidate colors */
  1568.   /* This array holds the actually closest colormap index for each cell. */
  1569.   JSAMPLE bestcolor[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];
  1570.  
  1571.   /* Convert cell coordinates to update box ID */
  1572.   c0 >>= BOX_C0_LOG;
  1573.   c1 >>= BOX_C1_LOG;
  1574.   c2 >>= BOX_C2_LOG;
  1575.  
  1576.   minc0 = (c0 << BOX_C0_SHIFT) + ((1 << C0_SHIFT) >> 1);
  1577.   minc1 = (c1 << BOX_C1_SHIFT) + ((1 << C1_SHIFT) >> 1);
  1578.   minc2 = (c2 << BOX_C2_SHIFT) + ((1 << C2_SHIFT) >> 1);
  1579.   
  1580.   numcolors = find_nearby_colors(minc0, minc1, minc2, colorlist);
  1581.  
  1582.   /* Determine the actually nearest colors. */
  1583.   find_best_colors(minc0, minc1, minc2, numcolors, colorlist, bestcolor);
  1584.  
  1585.   /* Save the best color numbers (plus 1) in the main cache array */
  1586.   c0 <<= BOX_C0_LOG;        /* convert ID back to base cell indexes */
  1587.   c1 <<= BOX_C1_LOG;
  1588.   c2 <<= BOX_C2_LOG;
  1589.   cptr = bestcolor;
  1590.   for (ic0 = 0; ic0 < BOX_C0_ELEMS; ic0++) {
  1591.     for (ic1 = 0; ic1 < BOX_C1_ELEMS; ic1++) {
  1592.       cachep = & histogram[c0+ic0][c1+ic1][c2];
  1593.       for (ic2 = 0; ic2 < BOX_C2_ELEMS; ic2++) {
  1594.     *cachep++ = (histcell) (*cptr++ + 1);
  1595.       }
  1596.     }
  1597.   }
  1598. }
  1599.  
  1600.  
  1601. static void slow_map_pixels (pic24, width, height, pic8)
  1602.      byte *pic24, *pic8;
  1603.      int   width, height;
  1604. {
  1605.   register LOCFSERROR cur0, cur1, cur2;    /* current error or pixel value */
  1606.   LOCFSERROR belowerr0, belowerr1, belowerr2; /* error for pixel below cur */
  1607.   LOCFSERROR bpreverr0, bpreverr1, bpreverr2; /* error for below/prev col */
  1608.   register FSERRPTR errorptr;    /* => fserrors[] at column before current */
  1609.   JSAMPROW inptr;        /* => current input pixel */
  1610.   JSAMPROW outptr;        /* => current output pixel */
  1611.   histptr cachep;
  1612.   int dir;            /* +1 or -1 depending on direction */
  1613.   int dir3;            /* 3*dir, for advancing inptr & errorptr */
  1614.   int row, col;
  1615.   int *error_limit = sl_error_limiter;
  1616.   JSAMPROW colormap0 = sl_colormap[0];
  1617.   JSAMPROW colormap1 = sl_colormap[1];
  1618.   JSAMPROW colormap2 = sl_colormap[2];
  1619.   hist2d * histogram = sl_histogram;
  1620.  
  1621.   for (row = 0; row < height; row++) {
  1622.  
  1623.     if ((row&0x3f) == 0) WaitCursor();
  1624.     ProgressMeter(0, height-1, row, "Dither");
  1625.  
  1626.     inptr = & pic24[row * width * 3];
  1627.     outptr = & pic8[row * width];
  1628.     if (sl_on_odd_row) {
  1629.       /* work right to left in this row */
  1630.       inptr += (width-1) * 3;    /* so point to rightmost pixel */
  1631.       outptr += width-1;
  1632.       dir = -1;
  1633.       dir3 = -3;
  1634.       errorptr = sl_fserrors + (width+1)*3; /* => entry after last column */
  1635.       sl_on_odd_row = FALSE;    /* flip for next time */
  1636.     } else {
  1637.       /* work left to right in this row */
  1638.       dir = 1;
  1639.       dir3 = 3;
  1640.       errorptr = sl_fserrors;    /* => entry before first real column */
  1641.       sl_on_odd_row = TRUE;    /* flip for next time */
  1642.     }
  1643.     /* Preset error values: no error propagated to first pixel from left */
  1644.     cur0 = cur1 = cur2 = 0;
  1645.     /* and no error propagated to row below yet */
  1646.     belowerr0 = belowerr1 = belowerr2 = 0;
  1647.     bpreverr0 = bpreverr1 = bpreverr2 = 0;
  1648.  
  1649.     for (col = width; col > 0; col--) {
  1650.       cur0 = (cur0 + errorptr[dir3+0] + 8) >> 4;
  1651.       cur1 = (cur1 + errorptr[dir3+1] + 8) >> 4;
  1652.       cur2 = (cur2 + errorptr[dir3+2] + 8) >> 4;
  1653.       cur0 = error_limit[cur0];
  1654.       cur1 = error_limit[cur1];
  1655.       cur2 = error_limit[cur2];
  1656.       cur0 += inptr[0];
  1657.       cur1 += inptr[1];
  1658.       cur2 += inptr[2];
  1659.       RANGE(cur0, 0, 255);
  1660.       RANGE(cur1, 0, 255);
  1661.       RANGE(cur2, 0, 255);
  1662.       /* Index into the cache with adjusted pixel value */
  1663.       cachep = & histogram[cur0>>C0_SHIFT][cur1>>C1_SHIFT][cur2>>C2_SHIFT];
  1664.       /* If we have not seen this color before, find nearest colormap */
  1665.       /* entry and update the cache */
  1666.       if (*cachep == 0)
  1667.     fill_inverse_cmap(cur0>>C0_SHIFT, cur1>>C1_SHIFT, cur2>>C2_SHIFT);
  1668.       /* Now emit the colormap index for this cell */
  1669.       { register int pixcode = *cachep - 1;
  1670.     *outptr = (JSAMPLE) pixcode;
  1671.     /* Compute representation error for this pixel */
  1672.     cur0 -= (int) colormap0[pixcode];
  1673.     cur1 -= (int) colormap1[pixcode];
  1674.     cur2 -= (int) colormap2[pixcode];
  1675.       }
  1676.       /* Compute error fractions to be propagated to adjacent pixels.
  1677.        * Add these into the running sums, and simultaneously shift the
  1678.        * next-line error sums left by 1 column.
  1679.        */
  1680.       { register LOCFSERROR bnexterr, delta;
  1681.  
  1682.     bnexterr = cur0;    /* Process component 0 */
  1683.     delta = cur0 * 2;
  1684.     cur0 += delta;        /* form error * 3 */
  1685.     errorptr[0] = (FSERROR) (bpreverr0 + cur0);
  1686.     cur0 += delta;        /* form error * 5 */
  1687.     bpreverr0 = belowerr0 + cur0;
  1688.     belowerr0 = bnexterr;
  1689.     cur0 += delta;        /* form error * 7 */
  1690.     bnexterr = cur1;    /* Process component 1 */
  1691.     delta = cur1 * 2;
  1692.     cur1 += delta;        /* form error * 3 */
  1693.     errorptr[1] = (FSERROR) (bpreverr1 + cur1);
  1694.     cur1 += delta;        /* form error * 5 */
  1695.     bpreverr1 = belowerr1 + cur1;
  1696.     belowerr1 = bnexterr;
  1697.     cur1 += delta;        /* form error * 7 */
  1698.     bnexterr = cur2;    /* Process component 2 */
  1699.     delta = cur2 * 2;
  1700.     cur2 += delta;        /* form error * 3 */
  1701.     errorptr[2] = (FSERROR) (bpreverr2 + cur2);
  1702.     cur2 += delta;        /* form error * 5 */
  1703.     bpreverr2 = belowerr2 + cur2;
  1704.     belowerr2 = bnexterr;
  1705.     cur2 += delta;        /* form error * 7 */
  1706.       }
  1707.       /* At this point curN contains the 7/16 error value to be propagated
  1708.        * to the next pixel on the current line, and all the errors for the
  1709.        * next line have been shifted over.  We are therefore ready to move on.
  1710.        */
  1711.       inptr += dir3;        /* Advance pixel pointers to next column */
  1712.       outptr += dir;
  1713.       errorptr += dir3;        /* advance errorptr to current column */
  1714.     }
  1715.     /* Post-loop cleanup: we must unload the final error values into the
  1716.      * final fserrors[] entry.  Note we need not unload belowerrN because
  1717.      * it is for the dummy column before or after the actual array.
  1718.      */
  1719.     errorptr[0] = (FSERROR) bpreverr0; /* unload prev errs into array */
  1720.     errorptr[1] = (FSERROR) bpreverr1;
  1721.     errorptr[2] = (FSERROR) bpreverr2;
  1722.   }
  1723. }
  1724.  
  1725.  
  1726. static void init_error_limit ()
  1727. /* Allocate and fill in the error_limiter table */
  1728. /* Note this should be done only once. */
  1729. {
  1730.   int * table;
  1731.   int in, out;
  1732.  
  1733.   table = (int *) malloc((size_t) ((255*2+1) * sizeof(int)));
  1734.   if (! table) return;
  1735.  
  1736.   table += 255;        /* so can index -255 .. +255 */
  1737.   sl_error_limiter = table;
  1738.  
  1739. #define STEPSIZE ((255+1)/16)
  1740.   /* Map errors 1:1 up to +- 255/16 */
  1741.   out = 0;
  1742.   for (in = 0; in < STEPSIZE; in++, out++) {
  1743.     table[in] = out; table[-in] = -out;
  1744.   }
  1745.   /* Map errors 1:2 up to +- 3*255/16 */
  1746.   for (; in < STEPSIZE*3; in++, out += (in&1) ? 0 : 1) {
  1747.     table[in] = out; table[-in] = -out;
  1748.   }
  1749.   /* Clamp the rest to final out value (which is (255+1)/8) */
  1750.   for (; in <= 255; in++) {
  1751.     table[in] = out; table[-in] = -out;
  1752.   }
  1753. #undef STEPSIZE
  1754. }
  1755.