Back to index

plt-scheme  4.2.1
wx_24to8.cc
Go to the documentation of this file.
00001 /*
00002  * xv24to8.c  -  contains the 24-to-8-bit Conv24to8 procedure
00003  *
00004  * The Conv24to8 procedure takes a pointer to a 24-bit image (loaded
00005  * previously).  The image will be a w * h * 3 byte array of
00006  * bytes.  The image will be arranged with 3 bytes per pixel (in order
00007  * R, G, and B), pixel 0 at the top left corner.  (As normal.)
00008  * The procedure also takes a maximum number of colors to use (numcols)
00009  *
00010  * The Conv24to8 procedure will set up the following:  it will allocate and
00011  * create 'pic', a pWIDE*pHIGH 8-bit picture.  it will set up pWIDE and pHIGH.
00012  * it will load up the r[], g[], and b[] colormap arrays.  it will NOT 
00013  * calculate numcols, since the cmap sort procedure has to be called anyway
00014  *
00015  * Conv24to8 returns '0' if successful, '1' if it failed (presumably on a 
00016  * malloc())
00017  *
00018  * contains:
00019  *   Cont24to8()
00020  *   InitFSDTables()
00021  */
00022 
00023 /*
00024  * Copyright 1989, 1990 by the University of Pennsylvania
00025  *
00026  * Permission to use, copy, and distribute for non-commercial purposes,
00027  * is hereby granted without fee, providing that the above copyright
00028  * notice appear in all copies and that both the copyright notice and this
00029  * permission notice appear in supporting documentation.
00030  *
00031  * The software may be modified for your own purposes, but modified versions
00032  * may not be distributed.
00033  *
00034  * This software is provided "as is" without any express or implied warranty.
00035  */
00036 
00037 #include <stdlib.h>
00038 #include "wx_image.h"
00039 
00040 #ifdef MZ_PRECISE_GC
00041 END_XFORM_ARITH;
00042 #endif
00043 
00044 static int   num_colors, WIDE, HIGH;
00045 static int   histogram[B_LEN][B_LEN][B_LEN];
00046 
00047 CBOX   *freeboxes, *usedboxes;
00048 CCELL **ColorCells;
00049 
00050 static void assign_color(CBOX *ptr,byte *rp,byte *gp, byte *bp);
00051 static CCELL *create_colorcell(int r1, int g1, int b1,
00052                             byte *r, byte *g, byte *b);
00053 static void   map_colortable(byte *r, byte *g, byte *b);
00054 
00055 static byte   tbl1[256],     /* tables used in F-S Dithering */
00056               tbl3[256],     /* contain i/16, 3i/16, 5i/16, 7i/16, */
00057               tbl5[256],     /* (i=0-255) respectively */
00058               tbl7[256];
00059 
00060 
00061 /****************************/
00062 int wxImage::Conv24to8(byte *p, int w, int h, int nc)
00063 /****************************/
00064 {
00065   int   i;
00066   CBOX *box_list, *ptr;
00067 
00068   /* copy arguments to local-global variables */
00069   pic24 = p;  pWIDE = WIDE = w;  pHIGH = HIGH = h;  num_colors = nc;
00070 
00071 
00072   /* allocate pic immediately, so that if we can't allocate it, we don't
00073      waste time running this algorithm */
00074 
00075   {
00076     byte *ba;
00077     ba = (byte *) malloc(WIDE * HIGH);
00078     pic = ba;
00079   }
00080   if (pic == NULL) {
00081     fprintf(stderr,"Conv24to8() - failed to allocate picture\n");
00082     return(1);
00083   }
00084 
00085 
00086   /* quick check:  if we're going to display a greyscale or 1-bit image,
00087      DON'T run this annoyingly time-consuming code.  Just convert the 24-bit
00088      color image to an 8-bit greyscale.  This takes virtually no time, by
00089      comparision, and it has the same effect. */
00090 
00091   if (mono || nc==0) {
00092     byte *pp, *p24;
00093 
00094     for (i=0; i<256; i++) {
00095       r[i]=g[i]=b[i]=i;   /* greyscale colormap */
00096     }
00097     pp = pic;  p24 = pic24;
00098     for (i=WIDE*HIGH; i>0; i--, pp++, p24+=3) {
00099       *pp = (p24[0]*11 + p24[1]*16 + p24[2]*5) >> 5;  /* pp=.33R+.5G+.17B */
00100     }
00101 
00102     return(0);
00103   }
00104 
00105   if (!noqcheck && QuickCheck(pic24,w,h,nc)) { 
00106     /* see if it's a <256 color RGB pic */
00107     return 0;   
00108   }
00109   else if (!slow24) {
00110     return(Quick24to8(pic24,w,h));
00111   }
00112 
00113   /**** STEP 1:  create empty boxes ****/
00114 
00115   usedboxes = NULL;
00116   freeboxes = (CBOX *) malloc(num_colors * sizeof(CBOX));
00117   box_list = freeboxes;
00118 
00119   if (box_list == NULL) {
00120     return(1);
00121   }
00122 
00123   for (i=0; i<num_colors; i++) {
00124     freeboxes[i].next = &freeboxes[i+1];
00125     freeboxes[i].prev = &freeboxes[i-1];
00126   }
00127   freeboxes[0].prev = NULL;
00128   freeboxes[num_colors-1].next = NULL;
00129 
00130 
00131   /**** STEP 2: get histogram, initialize first box ****/
00132 
00133   ptr = freeboxes;
00134   freeboxes = ptr->next;
00135   if (freeboxes) freeboxes->prev = NULL;
00136 
00137   ptr->next = usedboxes;
00138   usedboxes = ptr;
00139   if (ptr->next) ptr->next->prev = ptr;
00140        
00141   get_histogram(ptr);
00142 
00143 
00144   /**** STEP 3: continually subdivide boxes until no more free boxes remain */
00145 
00146   while (freeboxes) {
00147     ptr = largest_box();
00148     if (ptr) splitbox(ptr);
00149     else break;
00150   }
00151 
00152   
00153   /**** STEP 4: assign colors to all boxes ****/
00154 
00155   for (i=0, ptr=usedboxes; i<num_colors && ptr; i++, ptr=ptr->next) {
00156     assign_color(ptr, &r[i], &g[i], &b[i]);
00157   }
00158 
00159   /* We're done with the boxes now */
00160   num_colors = i;
00161   free(box_list);
00162   box_list = freeboxes = usedboxes = NULL;
00163  
00164 
00165   /**** STEP 5: scan histogram and map all values to closest color */
00166 
00167   /* 5a: create cell list as described in Heckbert[2] */
00168 
00169   ColorCells = (CCELL **) calloc(C_LEN*C_LEN*C_LEN, sizeof(CCELL *));
00170 
00171 
00172   /* 5b: create mapping from truncated pixel space to color table entries */
00173 
00174   map_colortable(r, g, b);
00175 
00176 
00177   /**** STEP 6: scan image, match input values to table entries */
00178 
00179   i=quant_fsdither();
00180 
00181   /* free everything that can be freed */
00182   free(ColorCells);
00183 
00184   return i;
00185 }
00186 
00187 
00188 /****************************/
00189 void wxImage::get_histogram(CBOX *box)
00190 /****************************/
00191 {
00192   int   i,j,rC,gC,bC,*ptr;
00193   byte *p;
00194 
00195   box->rmin = box->gmin = box->bmin = 999;
00196   box->rmax = box->gmax = box->bmax = -1;
00197   box->total = WIDE * HIGH;
00198 
00199   /* zero out histogram */
00200   ptr = &histogram[0][0][0];
00201   for (i=B_LEN*B_LEN*B_LEN; i>0; i-- ) { *ptr++ = 0; }
00202 
00203   /* calculate histogram */
00204   p = pic24;
00205   for (i=0; i<HIGH; i++) {
00206     for (j=0; j<WIDE; j++) {
00207       rC = (*p++) >> (COLOR_DEPTH-B_DEPTH);
00208       gC = (*p++) >> (COLOR_DEPTH-B_DEPTH);
00209       bC = (*p++) >> (COLOR_DEPTH-B_DEPTH);
00210 
00211       if (rC < box->rmin) box->rmin = rC;
00212       if (rC > box->rmax) box->rmax = rC;
00213 
00214       if (gC < box->gmin) box->gmin = gC;
00215       if (gC > box->gmax) box->gmax = gC;
00216 
00217       if (bC < box->bmin) box->bmin = bC;
00218       if (bC > box->bmax) box->bmax = bC;
00219       histogram[rC][gC][bC]++;
00220     }
00221   }
00222 }
00223 
00224 
00225 
00226 /******************************/
00227 CBOX *wxImage::largest_box()
00228 /******************************/
00229 {
00230   CBOX *tmp, *ptr;
00231   int   size = -1;
00232 
00233   tmp = usedboxes;
00234   ptr = NULL;
00235 
00236   while (tmp) {
00237     if ( (tmp->rmax > tmp->rmin  ||
00238          tmp->gmax > tmp->gmin  ||
00239          tmp->bmax > tmp->bmin)  &&  tmp->total > size ) {
00240       ptr = tmp;
00241       size = tmp->total;
00242     }
00243     tmp = tmp->next;
00244   }
00245   return(ptr);
00246 }
00247 
00248 
00249 
00250 /******************************/
00251 void wxImage::splitbox(CBOX *ptr)
00252 /******************************/
00253 {
00254   int   hist2[B_LEN], first, last, i, rdel, gdel, bdel;
00255   CBOX *new_cbox;
00256   int  *iptr, *histp, ir, ig, ib;
00257   int  rmin,rmax,gmin,gmax,bmin,bmax;
00258   enum {RED,GREEN,BLUE} which;
00259 
00260   /*
00261    * see which axis is the largest, do a histogram along that
00262    * axis.  Split at median point.  Contract both new boxes to
00263    * fit points and return
00264    */
00265 
00266   first = last = 0;   /* shut RT hcc compiler up */
00267 
00268   rmin = ptr->rmin;  rmax = ptr->rmax;
00269   gmin = ptr->gmin;  gmax = ptr->gmax;
00270   bmin = ptr->bmin;  bmax = ptr->bmax;
00271 
00272   rdel = rmax - rmin;
00273   gdel = gmax - gmin;
00274   bdel = bmax - bmin;
00275 
00276   if      (rdel>=gdel && rdel>=bdel) which = RED;
00277   else if (gdel>=bdel)               which = GREEN;
00278   else                               which = BLUE;
00279 
00280   /* get histogram along longest axis */
00281   switch (which) {
00282 
00283   case RED:
00284     histp = &hist2[rmin];
00285     for (ir=rmin; ir<=rmax; ir++) {
00286       *histp = 0;
00287       for (ig=gmin; ig<=gmax; ig++) {
00288        iptr = &histogram[ir][ig][bmin];
00289        for (ib=bmin; ib<=bmax; ib++) {
00290          *histp += *iptr;
00291          ++iptr;
00292        }
00293       }
00294       ++histp;
00295     }
00296     first = rmin;  last = rmax;
00297     break;
00298 
00299   case GREEN:
00300     histp = &hist2[gmin];
00301     for (ig=gmin; ig<=gmax; ig++) {
00302       *histp = 0;
00303       for (ir=rmin; ir<=rmax; ir++) {
00304        iptr = &histogram[ir][ig][bmin];
00305        for (ib=bmin; ib<=bmax; ib++) {
00306          *histp += *iptr;
00307          ++iptr;
00308        }
00309       }
00310       ++histp;
00311     }
00312     first = gmin;  last = gmax;
00313     break;
00314 
00315   case BLUE:
00316     histp = &hist2[bmin];
00317     for (ib=bmin; ib<=bmax; ib++) {
00318       *histp = 0;
00319       for (ir=rmin; ir<=rmax; ir++) {
00320        iptr = &histogram[ir][gmin][ib];
00321        for (ig=gmin; ig<=gmax; ig++) {
00322          *histp += *iptr;
00323          iptr += B_LEN;
00324        }
00325       }
00326       ++histp;
00327     }
00328     first = bmin;  last = bmax;
00329     break;
00330   }
00331 
00332 
00333   /* find median point */
00334   {
00335     int sum, sum2;
00336 
00337     histp = &hist2[first];
00338 
00339     sum2 = ptr->total/2;
00340     histp = &hist2[first];
00341     sum = 0;
00342         
00343     for (i=first; i<=last && (sum += *histp++)<sum2; i++) {
00344     }
00345     if (i==first) i++;
00346   }
00347 
00348 
00349   /* Create new box, re-allocate points */
00350   
00351   new_cbox = freeboxes;
00352   freeboxes = new_cbox->next;
00353   if (freeboxes) freeboxes->prev = NULL;
00354 
00355   if (usedboxes) usedboxes->prev = new_cbox;
00356   new_cbox->next = usedboxes;
00357   usedboxes = new_cbox;
00358 
00359   {
00360     int sum1,sum2,j;
00361     
00362     histp = &hist2[first];
00363     sum1 = 0;
00364     for (j = first; j < i; ++j) { sum1 += *histp++; }
00365     sum2 = 0;
00366     for (j = i; j <= last; ++j) { sum2 += *histp++; }
00367     new_cbox->total = sum1;
00368     ptr->total = sum2;
00369   }
00370 
00371 
00372   new_cbox->rmin = rmin;  new_cbox->rmax = rmax;
00373   new_cbox->gmin = gmin;  new_cbox->gmax = gmax;
00374   new_cbox->bmin = bmin;  new_cbox->bmax = bmax;
00375 
00376   switch (which) {
00377   case RED:    new_cbox->rmax = i-1;  ptr->rmin = i;  break;
00378   case GREEN:  new_cbox->gmax = i-1;  ptr->gmin = i;  break;
00379   case BLUE:   new_cbox->bmax = i-1;  ptr->bmin = i;  break;
00380   }
00381 
00382   shrinkbox(new_cbox);
00383   shrinkbox(ptr);
00384 }
00385 
00386 
00387 /****************************/
00388 void wxImage::shrinkbox(CBOX *box)
00389 /****************************/
00390 {
00391   int *histp,ir,ig,ib;
00392   int  rmin,rmax,gmin,gmax,bmin,bmax;
00393 
00394   rmin = box->rmin;  rmax = box->rmax;
00395   gmin = box->gmin;  gmax = box->gmax;
00396   bmin = box->bmin;  bmax = box->bmax;
00397 
00398   if (rmax>rmin) {
00399     for (ir=rmin; ir<=rmax; ir++) {
00400       for (ig=gmin; ig<=gmax; ig++) {
00401        histp = &histogram[ir][ig][bmin];
00402        for (ib=bmin; ib<=bmax; ib++) {
00403          if (*histp++ != 0) {
00404            box->rmin = rmin = ir;
00405            goto have_rmin;
00406          }
00407        }
00408       }
00409     }
00410 
00411   have_rmin:
00412     if (rmax>rmin)
00413       for (ir=rmax; ir>=rmin; --ir) {
00414        for (ig=gmin; ig<=gmax; ig++) {
00415          histp = &histogram[ir][ig][bmin];
00416          for (ib=bmin; ib<=bmax; ib++) {
00417            if (*histp++ != 0) {
00418              box->rmax = rmax = ir;
00419              goto have_rmax;
00420            }
00421          }
00422        }
00423       }
00424   }
00425 
00426 
00427  have_rmax:
00428 
00429   if (gmax>gmin) {
00430     for (ig=gmin; ig<=gmax; ig++) {
00431       for (ir=rmin; ir<=rmax; ir++) {
00432        histp = &histogram[ir][ig][bmin];
00433        for (ib=bmin; ib<=bmax; ib++) {
00434          if (*histp++ != 0) {
00435            box->gmin = gmin = ig;
00436            goto have_gmin;
00437          }
00438        }
00439       }
00440     }
00441 
00442   have_gmin:
00443     if (gmax>gmin)
00444       for (ig=gmax; ig>=gmin; --ig) {
00445        for (ir=rmin; ir<=rmax; ir++) {
00446          histp = &histogram[ir][ig][bmin];
00447          for (ib=bmin; ib<=bmax; ib++) {
00448            if (*histp++ != 0) {
00449              box->gmax = gmax = ig;
00450              goto have_gmax;
00451            }
00452          }
00453        }
00454       }
00455   }
00456 
00457 
00458  have_gmax:
00459 
00460   if (bmax>bmin) {
00461     for (ib=bmin; ib<=bmax; ib++) {
00462       for (ir=rmin; ir<=rmax; ir++) {
00463        histp = &histogram[ir][gmin][ib];
00464        for (ig=gmin; ig<=gmax; ig++) {
00465          if (*histp != 0) {
00466            box->bmin = bmin = ib;
00467            goto have_bmin;
00468          }
00469          histp += B_LEN;
00470        }
00471       }
00472     }
00473 
00474   have_bmin:
00475     if (bmax>bmin)
00476       for (ib=bmax; ib>=bmin; --ib) {
00477        for (ir=rmin; ir<=rmax; ir++) {
00478          histp = &histogram[ir][gmin][ib];
00479          for (ig=gmin; ig<=gmax; ig++) {
00480            if (*histp != 0) {
00481              bmax = ib;
00482              goto have_bmax;
00483            }
00484            histp += B_LEN;
00485          }
00486        }
00487       }
00488   }
00489 
00490  have_bmax: return;
00491 }
00492 
00493 
00494 
00495 /*******************************/
00496 static void assign_color(CBOX *ptr,byte *rp,byte *gp, byte *bp)
00497 /*******************************/
00498 {
00499   *rp = ((ptr->rmin + ptr->rmax) << (COLOR_DEPTH - B_DEPTH)) / 2;
00500   *gp = ((ptr->gmin + ptr->gmax) << (COLOR_DEPTH - B_DEPTH)) / 2;
00501   *bp = ((ptr->bmin + ptr->bmax) << (COLOR_DEPTH - B_DEPTH)) / 2;
00502 }
00503 
00504 
00505 
00506 /*******************************/
00507 CCELL *create_colorcell(int r1, int g1, int b1,
00508                      byte *r,byte *g, byte *b)
00509 /*******************************/
00510 {
00511   register int    i,tmp, dist;
00512   register CCELL *ptr;
00513   register byte  *rp,*gp,*bp;
00514   int             ir,ig,ib, mindist;
00515 
00516   ir = r1 >> (COLOR_DEPTH-C_DEPTH);
00517   ig = g1 >> (COLOR_DEPTH-C_DEPTH);
00518   ib = b1 >> (COLOR_DEPTH-C_DEPTH);
00519 
00520   r1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
00521   g1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
00522   b1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
00523 
00524   ptr = (CCELL *) malloc(sizeof(CCELL));
00525   *(ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib) = ptr;
00526   ptr->num_ents = 0;
00527 
00528   /* step 1: find all colors inside this cell, while we're at
00529      it, find distance of centermost point to furthest
00530      corner */
00531 
00532   mindist = 99999999;
00533 
00534   rp=r;  gp=g;  bp=b;
00535   for (i=0; i<num_colors; i++,rp++,gp++,bp++) {
00536     if( *rp>>(COLOR_DEPTH-C_DEPTH) == ir  &&
00537         *gp>>(COLOR_DEPTH-C_DEPTH) == ig  &&
00538         *bp>>(COLOR_DEPTH-C_DEPTH) == ib) {
00539 
00540       ptr->entries[ptr->num_ents][0] = i;
00541       ptr->entries[ptr->num_ents][1] = 0;
00542       ++ptr->num_ents;
00543 
00544       tmp = *rp - r1;
00545       if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
00546       dist = tmp*tmp;
00547 
00548       tmp = *gp - g1;
00549       if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
00550       dist += tmp*tmp;
00551 
00552       tmp = *bp - b1;
00553       if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
00554       dist += tmp*tmp;
00555 
00556       if (dist < mindist) mindist = dist;
00557     }
00558   }
00559 
00560   /* step 3: find all points within that distance to box */
00561 
00562   rp=r;  gp=g;  bp=b;
00563   for (i=0; i<num_colors; i++,rp++,gp++,bp++) {
00564     if (*rp >> (COLOR_DEPTH-C_DEPTH) != ir  ||
00565        *gp >> (COLOR_DEPTH-C_DEPTH) != ig  ||
00566        *bp >> (COLOR_DEPTH-C_DEPTH) != ib) {
00567 
00568       dist = 0;
00569 
00570       if ((tmp = r1 - *rp)>0 || (tmp = *rp - (r1 + MAX_COLOR/C_LEN-1)) > 0 )
00571        dist += tmp*tmp;
00572 
00573       if( (tmp = g1 - *gp)>0 || (tmp = *gp - (g1 + MAX_COLOR/C_LEN-1)) > 0 )
00574        dist += tmp*tmp;
00575 
00576       if( (tmp = b1 - *bp)>0 || (tmp = *bp - (b1 + MAX_COLOR/C_LEN-1)) > 0 )
00577        dist += tmp*tmp;
00578 
00579       if( dist < mindist ) {
00580        ptr->entries[ptr->num_ents][0] = i;
00581        ptr->entries[ptr->num_ents][1] = dist;
00582        ++ptr->num_ents;
00583       }
00584     }
00585   }
00586 
00587   /* sort color cells by distance, use cheap exchange sort */
00588   {
00589     int n, next_n;
00590 
00591     n = ptr->num_ents - 1;
00592     while (n>0) {
00593       next_n = 0;
00594       for (i=0; i<n; ++i) {
00595        if (ptr->entries[i][1] > ptr->entries[i+1][1]) {
00596          tmp = ptr->entries[i][0];
00597          ptr->entries[i][0] = ptr->entries[i+1][0];
00598          ptr->entries[i+1][0] = tmp;
00599          tmp = ptr->entries[i][1];
00600          ptr->entries[i][1] = ptr->entries[i+1][1];
00601          ptr->entries[i+1][1] = tmp;
00602          next_n = i;
00603        }
00604       }
00605       n = next_n;
00606     }
00607   }
00608   return (ptr);
00609 }
00610 
00611 
00612 
00613 
00614 /***************************/
00615 static void map_colortable(byte *r, byte *g, byte *b)
00616 /***************************/
00617 {
00618   int    ir,ig,ib, *histp;
00619   CCELL *cell;
00620 
00621   histp  = &histogram[0][0][0];
00622   for (ir=0; ir<B_LEN; ir++) {
00623     for (ig=0; ig<B_LEN; ig++) {
00624       for (ib=0; ib<B_LEN; ib++) {
00625        if (*histp==0) *histp = -1;
00626        else {
00627          int  i, j, tmp, d2, dist;
00628          
00629          cell = *(ColorCells +
00630                  ( ((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2)
00631                  + ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH)
00632                  +  (ib>>(B_DEPTH-C_DEPTH)) ) );
00633               
00634          if (cell==NULL)
00635            cell = create_colorcell(ir<<(COLOR_DEPTH-B_DEPTH),
00636                                 ig<<(COLOR_DEPTH-B_DEPTH),
00637                                 ib<<(COLOR_DEPTH-B_DEPTH),
00638                                 r, g, b);
00639 
00640          dist = 9999999;
00641          for (i=0; i<cell->num_ents && dist>cell->entries[i][1]; i++) {
00642            j = cell->entries[i][0];
00643            d2 = r[j] - (ir << (COLOR_DEPTH-B_DEPTH));
00644            d2 *= d2;
00645            tmp = g[j] - (ig << (COLOR_DEPTH-B_DEPTH));
00646            d2 += tmp*tmp;
00647            tmp = b[j] - (ib << (COLOR_DEPTH-B_DEPTH));
00648            d2 += tmp*tmp;
00649            if( d2 < dist ) { dist = d2;  *histp = j; }
00650          }
00651        }
00652        histp++;
00653       }
00654     }
00655   }
00656 }
00657 
00658 
00659 
00660 /*****************************/
00661 int wxImage::quant_fsdither()
00662 /*****************************/
00663 {
00664   register int  *thisptr, *nextptr;
00665   int           *thisline, *nextline, *tmpptr;
00666   int            r1, g1, b1, r2, g2, b2;
00667   int            i, j, imax, jmax, oval;
00668   byte          *inptr, *outptr, *tmpbptr;
00669   int            lastline, lastpixel;
00670 
00671   imax = HIGH - 1;
00672   jmax = WIDE - 1;
00673   
00674   thisline = (int *) malloc(WIDE * 3 * sizeof(int));
00675   nextline = (int *) malloc(WIDE * 3 * sizeof(int));
00676 
00677   if (thisline == NULL || nextline == NULL) {
00678     fprintf(stderr,"unable to allocate stuff for the 'dither' routine\n");
00679     return 1;
00680   }
00681 
00682 
00683   inptr  = (byte *) pic24;
00684   outptr = (byte *) pic;
00685 
00686   /* get first line of picture */
00687   for (j=WIDE * 3, tmpptr=nextline, tmpbptr=inptr; j; j--) {
00688     *tmpptr++ = (int) *tmpbptr++;
00689   }
00690 
00691   for (i=0; i<HIGH; i++) {
00692     /* swap thisline and nextline */
00693     tmpptr = thisline;  thisline = nextline;  nextline = tmpptr;
00694     lastline = (i==imax);
00695 
00696     /* read in next line */
00697     for (j=WIDE * 3, tmpptr=nextline; j; j--) {
00698       *tmpptr++ = (int) *inptr++;
00699     }
00700 
00701     /* dither this line and put it into the output picture */
00702     thisptr = thisline;  nextptr = nextline;
00703 
00704     for (j=0; j<WIDE; j++) {
00705       lastpixel = (j==jmax);
00706 
00707       r2 = *thisptr++;  g2 = *thisptr++;  b2 = *thisptr++;
00708 
00709       if (r2<0) r2=0;  else if (r2>=MAX_COLOR) r2=MAX_COLOR-1;
00710       if (g2<0) g2=0;  else if (g2>=MAX_COLOR) g2=MAX_COLOR-1;
00711       if (b2<0) b2=0;  else if (b2>=MAX_COLOR) b2=MAX_COLOR-1;
00712 
00713       r1 = r2;  g1 = g2;  b1 = b2;
00714 
00715       r2 >>= (COLOR_DEPTH-B_DEPTH);
00716       g2 >>= (COLOR_DEPTH-B_DEPTH);
00717       b2 >>= (COLOR_DEPTH-B_DEPTH);
00718 
00719       if ( (oval=histogram[r2][g2][b2]) == -1) {
00720        int ci, cj, dist, d2, tmp;
00721        CCELL *cell;
00722 
00723        cell = *( ColorCells + 
00724               ( ((r2>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2)
00725                + ((g2>>(B_DEPTH-C_DEPTH)) << C_DEPTH )
00726               +  (b2>>(B_DEPTH-C_DEPTH)) ) );
00727              
00728        if (cell==NULL) cell = create_colorcell(r1,g1,b1, r, g, b);
00729 
00730        dist = 9999999;
00731        for (ci=0; ci<cell->num_ents && dist>cell->entries[ci][1]; ci++) {
00732          cj = cell->entries[ci][0];
00733          d2 = (r[cj] >> (COLOR_DEPTH-B_DEPTH)) - r2;
00734          d2 *= d2;
00735          tmp = (g[cj] >> (COLOR_DEPTH-B_DEPTH)) - g2;
00736          d2 += tmp*tmp;
00737          tmp = (b[cj] >> (COLOR_DEPTH-B_DEPTH)) - b2;
00738          d2 += tmp*tmp;
00739          if (d2<dist) { dist = d2;  oval = cj; }
00740        }
00741        histogram[r2][g2][b2] = oval;
00742       }
00743 
00744       *outptr++ = oval;
00745 
00746       r1 -= r[oval];  g1 -= g[oval];  b1 -= b[oval];
00747       /* can't use tables because r1,g1,b1 go negative */
00748 
00749       if (!lastpixel) {
00750        thisptr[0] += (r1*7)/16;
00751        thisptr[1] += (g1*7)/16;
00752        thisptr[2] += (b1*7)/16;
00753       }
00754 
00755       if (!lastline) {
00756        if (j) {
00757          nextptr[-3] += (r1*3)/16;
00758          nextptr[-2] += (g1*3)/16;
00759          nextptr[-1] += (b1*3)/16;
00760        }
00761 
00762        nextptr[0] += (r1*5)/16;
00763        nextptr[1] += (g1*5)/16;
00764        nextptr[2] += (b1*5)/16;
00765 
00766        if (!lastpixel) {
00767          nextptr[3] += r1/16;
00768          nextptr[4] += g1/16;
00769          nextptr[5] += b1/16;
00770        }
00771        nextptr += 3;
00772       }
00773     }
00774   }
00775   free(thisline);  free(nextline);
00776   return 0;
00777 }
00778 
00779 
00780 
00781 
00782 
00783 /************************************/
00784 int wxImage::Quick24to8(byte *p24, int w, int h)
00785 {
00786 
00787   /* floyd-steinberg dithering.
00788    *
00789    * ----   x    7/16
00790    * 3/16  5/16  1/16
00791    *
00792    */
00793 
00794   /* called after 'pic' has been alloced, pWIDE,pHIGH set up, mono/1-bit
00795      checked already */
00796 
00797   byte *pp;
00798   int  r1, g1, b1;
00799   int  *thisline, *nextline, *thisptr, *nextptr, *tmpptr;
00800   int  i, j, rerr, gerr, berr, pwide3;
00801   int  imax, jmax;
00802 
00803   pp = pic;  pwide3 = w * 3;  imax = h-1;  jmax = w-1;
00804 
00805   /* load up colormap, 3 bits R, 3 bits G, 2 bits B  (RRRGGGBB) */
00806   for (i=0; i<256; i++) {
00807     r[i] =  ((i&0xe0) * 255) / 0xe0;  
00808     g[i] =  ((i&0x1c) * 255) / 0x1c;
00809     b[i] =  ((i&0x03) * 255) / 0x03;
00810   }
00811 
00812   thisline = (int *) malloc(pwide3 * sizeof(int));
00813   nextline = (int *) malloc(pwide3 * sizeof(int));
00814   if (!thisline || !nextline) {
00815     fprintf(stderr,"Unable to allocate memory in Quick24to8()\n");
00816     return(1);
00817     }
00818 
00819   /* get first line of picture */
00820   for (j=pwide3, tmpptr=nextline; j; j--) { *tmpptr++ = (int) *p24++; }
00821 
00822   for (i=0; i<h; i++) {
00823     tmpptr = thisline;  thisline = nextline;  nextline = tmpptr;   /* swap */
00824 
00825     if (i!=imax)   /* get next line */
00826       for (j=pwide3, tmpptr=nextline; j; j--) {
00827        *tmpptr++ = (int) *p24++;
00828       }
00829 
00830     for (j=0, thisptr=thisline, nextptr=nextline; j<w; j++,pp++) {
00831       r1 = *thisptr++;  g1 = *thisptr++;  b1 = *thisptr++;
00832       RANGE(r1,0,255);  RANGE(g1,0,255);  RANGE(b1,0,255);  
00833 
00834       rerr = r1 & 0x1f;  gerr = g1 & 0x1f;  berr = b1 & 0x3f;
00835       *pp = (r1&0xe0) | ((g1>>3)&0x1c) | (b1>>6); 
00836 
00837       if (j!=jmax) {  /* adjust RIGHT pixel */
00838        thisptr[0] += tbl7[rerr];
00839        thisptr[1] += tbl7[gerr];
00840        thisptr[2] += tbl7[berr];
00841       }
00842       
00843       if (i!=imax) { /* do BOTTOM pixel */
00844        nextptr[0] += tbl5[rerr];
00845        nextptr[1] += tbl5[gerr];
00846        nextptr[2] += tbl5[berr];
00847 
00848        if (j>0) {  /* do BOTTOM LEFT pixel */
00849          nextptr[-3] += tbl3[rerr];
00850          nextptr[-2] += tbl3[gerr];
00851          nextptr[-1] += tbl3[berr];
00852        }
00853 
00854        if (j!=jmax) {  /* do BOTTOM RIGHT pixel */
00855          nextptr[3] += tbl1[rerr];
00856          nextptr[4] += tbl1[gerr];
00857          nextptr[5] += tbl1[berr];
00858        }
00859        nextptr += 3;
00860       }
00861     }
00862   }
00863 
00864   return 0;
00865 }
00866       
00867 
00868 
00869 /****************************/
00870 void InitFSDTables()
00871 /****************************/
00872 {
00873   int i;
00874   for (i=0; i<256; i++) {     /* initialize Floyd-Steinberg division tables */
00875     tbl1[i] = i/16;
00876     tbl3[i] = (3*i)/16;
00877     tbl5[i] = (5*i)/16;
00878     tbl7[i] = (7*i)/16;
00879   }
00880 }
00881 
00882 /****************************/
00883 int wxImage::QuickCheck(byte *pic24, int w, int h, int maxcol)
00884 {
00885   /* scans picture until it finds more than 'maxcol' different colors.  If it
00886      finds more than 'maxcol' colors, it returns '0'.  If it DOESN'T, it does
00887      the 24-to-8 conversion by simply sticking the colors it found into
00888      a colormap, and changing instances of a color in pic24 into colormap
00889      indicies (in pic) */
00890 
00891   unsigned long colors[256],col;
00892   int           i, nc, low, high, mid;
00893   byte         *p, *pix;
00894 
00895   if (maxcol>256) maxcol = 256;
00896 
00897   /* put the first color in the table by hand */
00898   nc = 0;  mid = 0;  
00899 
00900   for (i=w*h,p=pic24; i; i--) {
00901     col  = (*p++ << 16);  
00902     col += (*p++ << 8);
00903     col +=  *p++;
00904 
00905     /* binary search the 'colors' array to see if it's in there */
00906     low = 0;  high = nc-1;
00907     while (low <= high) {
00908       mid = (low+high)/2;
00909       if      (col < colors[mid]) high = mid - 1;
00910       else if (col > colors[mid]) low  = mid + 1;
00911       else break;
00912     }
00913 
00914     if (high < low) { /* didn't find color in list, add it. */
00915       if (nc>=maxcol) return 0;
00916       memmove((char *)&colors[low], (char *)&colors[low+1], (nc - low) * sizeof(unsigned long));
00917       colors[low] = col;
00918       nc++;
00919     }
00920   }
00921 
00922 
00923   /* run through the data a second time, this time mapping pixel values in
00924      pic24 into colormap offsets into 'colors' */
00925 
00926   for (i=w*h,p=pic24, pix=pic; i; i--,pix++) {
00927     col  = (*p++ << 16);  
00928     col += (*p++ << 8);
00929     col +=  *p++;
00930 
00931     /* binary search the 'colors' array.  It *IS* in there */
00932     low = 0;  high = nc-1;
00933     while (low <= high) {
00934       mid = (low+high)/2;
00935       if      (col < colors[mid]) high = mid - 1;
00936       else if (col > colors[mid]) low  = mid + 1;
00937       else break;
00938     }
00939 
00940     if (high < low) {
00941       fprintf(stderr,"QuickCheck:  impossible!\n");
00942       exit(1);
00943     }
00944     *pix = mid;
00945   }
00946 
00947   /* and load up the 'desired colormap' */
00948   for (i=0; i<nc; i++) {
00949     r[i] =  colors[i]>>16;  
00950     g[i] = (colors[i]>>8) & 0xff;
00951     b[i] =  colors[i]     & 0xff;
00952   }
00953 
00954   return 1;
00955 }