home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / procssng / ccs / ccs-11.lha / ccs-lib / lib / quantto8.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-04-19  |  13.7 KB  |  636 lines
  1. /*
  2. %    QUANT_TO_8 . C
  3. */
  4.  
  5. #include "header.def"
  6. #include "imagedef.h"
  7.  
  8. #define    SYS_DEPTH    8
  9. #define    BitsPPix    5        /* # bits/per pixel */
  10. #define    HC_SIZE        (1<<BitsPPix)    /* histo size for each color */
  11. #define    C_DEPTH        2
  12. #define    C_LEN        (1<<C_DEPTH)    /* # cells/color to use */
  13. #define    MAX_CMAP_SIZE    256
  14. #define    TOP_VALUE    (1<<24)
  15. #define    RED    0
  16. #define    GREEN    1
  17. #define    BLUE    2
  18.  
  19. typedef    struct colorbox {
  20.     struct colorbox    *next, *prev;
  21.     int    rmin,rmax, gmin,gmax, bmin,bmax,
  22.         total;
  23. } CBOX;
  24.  
  25. typedef    struct {
  26.     int    num_ents,
  27.         entries[MAX_CMAP_SIZE][2];
  28.     } CCELL;
  29.  
  30. CBOX    *freeboxes, *usedboxes;
  31. CCELL    **ColorCells;
  32. static    int    histogram[HC_SIZE][HC_SIZE][HC_SIZE],
  33.         height, width, num_colors;
  34.  
  35.  
  36. static void
  37. shrinkbox(box)
  38. CBOX    *box;
  39. {
  40. int    *histp,ir,ig,ib;
  41. int    rmin,rmax,gmin,gmax,bmin,bmax;
  42.  
  43.     rmin = box->rmin;    rmax = box->rmax;
  44.     gmin = box->gmin;    gmax = box->gmax;
  45.     bmin = box->bmin;    bmax = box->bmax;
  46.  
  47.     if (rmax>rmin) {
  48.         for (ir=rmin; ir<=rmax; ir++)
  49.         for (ig=gmin; ig<=gmax; ig++) {
  50.             histp = &histogram[ir][ig][bmin];
  51.             for (ib=bmin; ib<=bmax; ib++)
  52.             if (*histp++) {
  53.                 box->rmin = rmin = ir;
  54.                 goto    have_rmin;
  55.             }
  56.         }
  57.     have_rmin:
  58.         if (rmax>rmin)
  59.             for (ir=rmax; ir>=rmin; ir--)
  60.             for (ig=gmin; ig<=gmax; ig++) {
  61.                 histp = &histogram[ir][ig][bmin];
  62.                 for (ib=bmin; ib<=bmax; ib++)
  63.                 if (*histp++) {
  64.                     box->rmax = rmax = ir;
  65.                     goto    have_rmax;
  66.                 }
  67.             }
  68.     }
  69. have_rmax:
  70.     if (gmax>gmin) {
  71.         for (ig=gmin; ig<=gmax; ig++)
  72.         for (ir=rmin; ir<=rmax; ir++) {
  73.             histp = &histogram[ir][ig][bmin];
  74.             for (ib=bmin; ib<=bmax; ib++)
  75.             if (*histp++) {
  76.                 box->gmin = gmin = ig;
  77.                 goto    have_gmin;
  78.             }
  79.         }
  80.     have_gmin:
  81.         if (gmax>gmin)
  82.             for (ig=gmax; ig>=gmin; ig--)
  83.             for (ir=rmin; ir<=rmax; ir++) {
  84.                 histp = &histogram[ir][ig][bmin];
  85.                 for (ib=bmin; ib<=bmax; ib++)
  86.                 if (*histp++) {
  87.                     box->gmax = gmax = ig;
  88.                     goto    have_gmax;
  89.                 }
  90.             }
  91.     }
  92. have_gmax:
  93.     if (bmax>bmin) {
  94.         for (ib=bmin; ib<=bmax; ib++)
  95.         for (ir=rmin; ir<=rmax; ir++) {
  96.             histp = &histogram[ir][gmin][ib];
  97.             for (ig=gmin; ig<=gmax; ig++) {
  98.             if (*histp != 0) {
  99.                 box->bmin = bmin = ib;
  100.                 goto    have_bmin;
  101.             }
  102.             histp += HC_SIZE;
  103.             }
  104.         }
  105.     have_bmin:
  106.         if (bmax>bmin)
  107.             for (ib=bmax; ib>=bmin; ib--)
  108.             for (ir=rmin; ir<=rmax; ir++) {
  109.                 histp = &histogram[ir][gmin][ib];
  110.                 for (ig=gmin; ig<=gmax; ig++) {
  111.                 if (*histp) {
  112.                     bmax = ib;
  113.                     goto    have_bmax;
  114.                 }
  115.                 histp += HC_SIZE;
  116.                 }
  117.             }
  118.     }
  119. have_bmax: return;
  120. }
  121.  
  122.  
  123. static void
  124. calc_histogram(p, box)
  125. byte    *p;
  126. CBOX *box;
  127. {
  128. int    i,j,r,g,b,*ptr;
  129.  
  130.     box->rmin = box->gmin = box->bmin = 999;
  131.     box->rmax = box->gmax = box->bmax = -1;
  132.     box->total = width * height;
  133.  
  134.     /* zero out histogram */
  135.     ptr = &histogram[0][0][0];
  136.     for (i=HC_SIZE*HC_SIZE*HC_SIZE; i>0; i--)    *ptr++ = 0;
  137.  
  138.     /* calculate histogram */
  139.     for (i=0; i<height; i++)
  140.         for (j=0; j<width; j++) {
  141.         r = (*p++) >> (SYS_DEPTH-BitsPPix);
  142.         g = (*p++) >> (SYS_DEPTH-BitsPPix);
  143.         b = (*p++) >> (SYS_DEPTH-BitsPPix);
  144.  
  145.         if (r < box->rmin) box->rmin = r;
  146.         if (r > box->rmax) box->rmax = r;
  147.  
  148.         if (g < box->gmin) box->gmin = g;
  149.         if (g > box->gmax) box->gmax = g;
  150.  
  151.         if (b < box->bmin) box->bmin = b;
  152.         if (b > box->bmax) box->bmax = b;
  153.         histogram[r][g][b]++;
  154.         }
  155. }
  156.  
  157.  
  158. static void
  159. splitbox(ptr)
  160. CBOX *ptr;
  161. {
  162. CBOX    *new;
  163. int    hist2[HC_SIZE], first, last, i, rdel, gdel, bdel;
  164. int    *iptr, *histp, ir, ig, ib,
  165.     rmin,rmax,gmin,gmax,bmin,bmax,    which;
  166.  
  167.     /*
  168.     * see which axis is the largest, do a histogram along that axis.
  169.     * Split at median point. Contract both new boxes to fit points and return
  170.     */
  171.  
  172.     first = last = 0;    /* shut RT hcc compiler up */
  173.  
  174.     rmin = ptr->rmin;  rmax = ptr->rmax;
  175.     gmin = ptr->gmin;  gmax = ptr->gmax;
  176.     bmin = ptr->bmin;  bmax = ptr->bmax;
  177.  
  178.     rdel = rmax - rmin;
  179.     gdel = gmax - gmin;
  180.     bdel = bmax - bmin;
  181.  
  182.     if (rdel>=gdel && rdel>=bdel)
  183.                 which = RED;
  184.     else if (gdel>=bdel)    which = GREEN;
  185.     else            which = BLUE;
  186.  
  187.     /* get histogram along longest axis */
  188.     switch (which) {
  189.     case RED:
  190.         histp = &hist2[rmin];
  191.         for (ir=rmin; ir<=rmax; ir++) {
  192.             *histp = 0;
  193.             for (ig=gmin; ig<=gmax; ig++) {
  194.             iptr = &histogram[ir][ig][bmin];
  195.             for (ib=bmin; ib<=bmax; ib++)
  196.                 *histp += *iptr++;
  197.             }
  198.             ++histp;
  199.         }
  200.         first = rmin;  last = rmax;
  201.         break;
  202.     case GREEN:
  203.         histp = &hist2[gmin];
  204.         for (ig=gmin; ig<=gmax; ig++) {
  205.             *histp = 0;
  206.             for (ir=rmin; ir<=rmax; ir++) {
  207.             iptr = &histogram[ir][ig][bmin];
  208.             for (ib=bmin; ib<=bmax; ib++)
  209.             *histp += *iptr++;
  210.             }
  211.             ++histp;
  212.         }
  213.         first = gmin;  last = gmax;
  214.         break;
  215.     case BLUE:
  216.         histp = &hist2[bmin];
  217.         for (ib=bmin; ib<=bmax; ib++) {
  218.             *histp = 0;
  219.             for (ir=rmin; ir<=rmax; ir++) {
  220.             iptr = &histogram[ir][gmin][ib];
  221.             for (ig=gmin; ig<=gmax; ig++) {
  222.                 *histp += *iptr;
  223.                 iptr += HC_SIZE;
  224.             }
  225.             }
  226.             ++histp;
  227.         }
  228.         first = bmin;  last = bmax;
  229.         break;
  230.     }
  231.  
  232.     {
  233.     int    sum, sum2;    /* find median point */
  234.  
  235.     histp = &hist2[first];
  236.  
  237.     sum2 = ptr->total/2;
  238.     histp = &hist2[first];
  239.     sum = 0;
  240.  
  241.     for (i=first; i<=last && (sum += *histp++)<sum2; i++);
  242.     if (i==first) i++;
  243.     }
  244.  
  245.     /* Create new box, re-allocate points */
  246.  
  247.     new = freeboxes;
  248.     freeboxes = new->next;
  249.     if (freeboxes) freeboxes->prev = NULL;
  250.  
  251.     if (usedboxes) usedboxes->prev = new;
  252.     new->next = usedboxes;
  253.     usedboxes = new;
  254.  
  255.     {
  256.     int    sum1,sum2,j;
  257.  
  258.     histp = &hist2[first];
  259.  
  260.     for (sum1=0, j=first; j < i; ++j)
  261.         sum1 += *histp++;
  262.     for (sum2=0, j=i; j <= last; ++j)
  263.         sum2 += *histp++;
  264.     new->total = sum1;
  265.     ptr->total = sum2;
  266.     }
  267.  
  268.     new->rmin = rmin;  new->rmax = rmax;
  269.     new->gmin = gmin;  new->gmax = gmax;
  270.     new->bmin = bmin;  new->bmax = bmax;
  271.  
  272.     switch (which) {
  273.     case RED:    new->rmax = i-1; ptr->rmin = i;    break;
  274.     case GREEN:    new->gmax = i-1; ptr->gmin = i;    break;
  275.     case BLUE:    new->bmax = i-1; ptr->bmin = i;    break;
  276.     }
  277.  
  278.     shrinkbox(new);
  279.     shrinkbox(ptr);
  280. }
  281.  
  282.  
  283. static    void
  284. fill_freeboxes()
  285. {
  286. while (freeboxes) {
  287. CBOX    *tmp, *ptr=NULL;
  288. int    size = -1;
  289.  
  290.     tmp = usedboxes;
  291.  
  292.     while (tmp) {
  293.        if ((tmp->rmax > tmp->rmin  ||
  294.         tmp->gmax > tmp->gmin  ||
  295.         tmp->bmax > tmp->bmin)  &&  tmp->total > size) {
  296.         ptr = tmp;
  297.         size = tmp->total;
  298.         }
  299.         tmp = tmp->next;
  300.     }
  301.     if (ptr)
  302.         splitbox(ptr);
  303.     else    break;
  304. }
  305. }
  306.  
  307. static void
  308. assign_color(ptr, rp, gp, bp)
  309. CBOX    *ptr;
  310. byte    *rp, *gp, *bp;
  311. {
  312.     *rp = ((ptr->rmin + ptr->rmax) << (SYS_DEPTH - BitsPPix)) >> 1;
  313.     *gp = ((ptr->gmin + ptr->gmax) << (SYS_DEPTH - BitsPPix)) >> 1;
  314.     *bp = ((ptr->bmin + ptr->bmax) << (SYS_DEPTH - BitsPPix)) >> 1;
  315. }
  316.  
  317.  
  318. static CCELL*
  319. create_colorcell(rg_cmap,r1,g1,b1)
  320. cmap_t    *rg_cmap[];
  321. int    r1,g1,b1;
  322. {
  323. register int    i,tmp, dist;
  324. register CCELL    *ptr;
  325. register byte    *rp,*gp,*bp;
  326. int        ir,ig,ib, mindist;
  327.  
  328.     ir = r1 >> (SYS_DEPTH-C_DEPTH);
  329.     ig = g1 >> (SYS_DEPTH-C_DEPTH);
  330.     ib = b1 >> (SYS_DEPTH-C_DEPTH);
  331.  
  332.     r1 &= ~1 << (SYS_DEPTH-C_DEPTH);
  333.     g1 &= ~1 << (SYS_DEPTH-C_DEPTH);
  334.     b1 &= ~1 << (SYS_DEPTH-C_DEPTH);
  335.  
  336.     ptr = (CCELL *) nzalloc(sizeof(CCELL), 1);
  337.     *(ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib) = ptr;
  338.     ptr->num_ents = 0;
  339.  
  340.     /* step 1: find all colors inside this cell, while we're at
  341.     it, find distance of centermost point to furthest corner */
  342.  
  343.     mindist = 99999999;
  344.  
  345.     rp=rg_cmap[RED];  gp=rg_cmap[GREEN];  bp=rg_cmap[BLUE];
  346.     for (i=0; i<num_colors; i++,rp++,gp++,bp++)
  347.         if (*rp>>(SYS_DEPTH-C_DEPTH) == ir &&
  348.         *gp>>(SYS_DEPTH-C_DEPTH) == ig &&
  349.         *bp>>(SYS_DEPTH-C_DEPTH) == ib)    {
  350.  
  351.         ptr->entries[ptr->num_ents][0] = i;
  352.         ptr->entries[ptr->num_ents][1] = 0;
  353.         ++ptr->num_ents;
  354.  
  355.         tmp = *rp - r1;
  356.         if (tmp < (MaxColors/C_LEN/2))
  357.             tmp = MaxColors/C_LEN-1 - tmp;
  358.         dist = tmp*tmp;
  359.  
  360.         tmp = *gp - g1;
  361.         if (tmp < (MaxColors/C_LEN/2))
  362.             tmp = MaxColors/C_LEN-1 - tmp;
  363.         dist += tmp*tmp;
  364.  
  365.         tmp = *bp - b1;
  366.         if (tmp < (MaxColors/C_LEN/2))
  367.             tmp = MaxColors/C_LEN-1 - tmp;
  368.         dist += tmp*tmp;
  369.  
  370.         if (dist < mindist)    mindist = dist;
  371.         }
  372.  
  373.     /* step 3: find all points within that distance to box */
  374.  
  375.     rp=rg_cmap[RED];  gp=rg_cmap[GREEN];  bp=rg_cmap[BLUE];
  376.     for (i=0; i<num_colors; i++,rp++,gp++,bp++)
  377.         if (*rp >> (SYS_DEPTH-C_DEPTH) != ir ||
  378.         *gp >> (SYS_DEPTH-C_DEPTH) != ig ||
  379.         *bp >> (SYS_DEPTH-C_DEPTH) != ib)    {
  380.  
  381.         dist = 0;
  382.  
  383.         if ((tmp = r1 - *rp)>0 ||
  384.             (tmp = *rp - (r1 + MaxColors/C_LEN-1)) > 0 )
  385.             dist += tmp*tmp;
  386.  
  387.         if( (tmp = g1 - *gp)>0 ||
  388.             (tmp = *gp - (g1 + MaxColors/C_LEN-1)) > 0 )
  389.             dist += tmp*tmp;
  390.  
  391.         if( (tmp = b1 - *bp)>0 ||
  392.             (tmp = *bp - (b1 + MaxColors/C_LEN-1)) > 0 )
  393.             dist += tmp*tmp;
  394.  
  395.         if( dist < mindist ) {
  396.             ptr->entries[ptr->num_ents][0] = i;
  397.             ptr->entries[ptr->num_ents][1] = dist;
  398.             ++ptr->num_ents;
  399.         }
  400.         }
  401.  
  402.     /* sort color cells by distance, use cheap exchange sort */
  403.     {
  404.     int    n, next_n;
  405.  
  406.     n = ptr->num_ents - 1;
  407.     while (n>0) {
  408.         next_n = 0;
  409.         for (i=0; i<n; ++i)
  410.         if (ptr->entries[i][1] > ptr->entries[i+1][1]) {
  411.             tmp = ptr->entries[i][0];
  412.             ptr->entries[i][0] = ptr->entries[i+1][0];
  413.             ptr->entries[i+1][0] = tmp;
  414.             tmp = ptr->entries[i][1];
  415.             ptr->entries[i][1] = ptr->entries[i+1][1];
  416.             ptr->entries[i+1][1] = tmp;
  417.             next_n = i;
  418.         }
  419.         n = next_n;
  420.     }
  421.     }
  422. return (ptr);
  423. }
  424.  
  425.  
  426. static void
  427. map_colortable(rg_cmap)
  428. cmap_t    *rg_cmap[];
  429. {
  430. CCELL    *cell;
  431. int    ir,ig,ib, *histp = &histogram[0][0][0];
  432.  
  433.     for (ir=0; ir<HC_SIZE; ir++)
  434.     for (ig=0; ig<HC_SIZE; ig++)
  435.         for (ib=0; ib<HC_SIZE; ib++) {
  436.         if (*histp==0) *histp = -1;
  437.         else {
  438.         int    i, j, tmp, d2, dist;
  439.  
  440.             cell = *(ColorCells +
  441.             ( ((ir>>(BitsPPix-C_DEPTH)) << C_DEPTH*2)
  442.             + ((ig>>(BitsPPix-C_DEPTH)) << C_DEPTH)
  443.             + (ib>>(BitsPPix-C_DEPTH)) ) );
  444.  
  445.             if (cell==NULL)
  446.             cell = create_colorcell(rg_cmap,
  447.                 ir<<(SYS_DEPTH-BitsPPix),
  448.                 ig<<(SYS_DEPTH-BitsPPix),
  449.                 ib<<(SYS_DEPTH-BitsPPix));
  450.  
  451.             dist = TOP_VALUE;
  452.             for (i=0; i<cell->num_ents && dist>cell->entries[i][1]; i++) {
  453.             j = cell->entries[i][0];
  454.             d2 = rg_cmap[RED][j] - (ir << (SYS_DEPTH-BitsPPix));
  455.             d2 *= d2;
  456.             tmp = rg_cmap[GREEN][j] - (ig << (SYS_DEPTH-BitsPPix));
  457.             d2 += tmp*tmp;
  458.             tmp = rg_cmap[BLUE][j] - (ib << (SYS_DEPTH-BitsPPix));
  459.             d2 += tmp*tmp;
  460.             if(d2 < dist)    { dist = d2;    *histp = j; }
  461.             }
  462.         }
  463.         histp++;
  464.         }
  465. }
  466.  
  467.  
  468. static
  469. quant_fsdither(inptr, outptr, rg_cmap)
  470. byte    *inptr, *outptr;
  471. cmap_t    *rg_cmap[];
  472. {
  473. register int    *thisptr, *nextptr;
  474. int    *thisline, *nextline, *tmpptr,
  475.     r1, g1, b1, r2, g2, b2,
  476.     i, j, imax, jmax, oval;
  477. byte    *tmpbptr;
  478. int    lastline, lastpixel;
  479.  
  480.     imax = height - 1;
  481.     jmax = width - 1;
  482.  
  483.     thisline = (int *) nzalloc(width, 3 * sizeof(int), "dither this");
  484.     nextline = (int *) nzalloc(width, 3 * sizeof(int), "dither next");
  485.  
  486.     /* get first line of picture */
  487.     for (j=width * 3, tmpptr=nextline, tmpbptr=inptr; j; j--)
  488.     *tmpptr++ = (int) *tmpbptr++;
  489.  
  490.     for (i=0; i<height; i++) {
  491.     /* swap thisline and nextline */
  492.         tmpptr = thisline; thisline = nextline; nextline = tmpptr;
  493.         lastline = i==imax;
  494.  
  495.     /* read in next line */
  496.         for (j=width * 3, tmpptr=nextline; j; j--)
  497.         *tmpptr++ = (int) *inptr++;
  498.  
  499.     /* dither this line and put it into the output picture */
  500.         thisptr = thisline;    nextptr = nextline;
  501.  
  502.         for (j=0; j<width; j++) {
  503.         lastpixel = (j==jmax);
  504.  
  505.         r2 = *thisptr++;  g2 = *thisptr++;  b2 = *thisptr++;
  506.  
  507.         if (r2<0)    r2=0;
  508.         else if (r2>=MaxColors)    r2=MaxColors-1;
  509.         if (g2<0)    g2=0;
  510.         else if (g2>=MaxColors)    g2=MaxColors-1;
  511.         if (b2<0)    b2=0;
  512.         else if (b2>=MaxColors)    b2=MaxColors-1;
  513.  
  514.         r1 = r2;  g1 = g2;  b1 = b2;
  515.  
  516.         r2 >>= (SYS_DEPTH-BitsPPix);
  517.         g2 >>= (SYS_DEPTH-BitsPPix);
  518.         b2 >>= (SYS_DEPTH-BitsPPix);
  519.  
  520.         if ( (oval=histogram[r2][g2][b2]) == -1) {
  521.         int    ci, cj, dist, d2, tmp;
  522.         CCELL*    cell = *( ColorCells +
  523.                 ( ((r2>>(BitsPPix-C_DEPTH)) << C_DEPTH*2)
  524.                 + ((g2>>(BitsPPix-C_DEPTH)) << C_DEPTH )
  525.                 +  (b2>>(BitsPPix-C_DEPTH)) ) );
  526.  
  527.             if (cell==NULL)    cell = create_colorcell(rg_cmap,r1,g1,b1);
  528.  
  529.             dist = TOP_VALUE;
  530.             for (ci=0; ci<cell->num_ents && dist>cell->entries[ci][1]; ci++) {
  531.             cj = cell->entries[ci][0];
  532.             d2 = (rg_cmap[RED][cj] >> (SYS_DEPTH-BitsPPix)) - r2;
  533.             d2 *= d2;
  534.             tmp = (rg_cmap[GREEN][cj] >> (SYS_DEPTH-BitsPPix)) - g2;
  535.             d2 += tmp*tmp;
  536.             tmp = (rg_cmap[BLUE][cj] >> (SYS_DEPTH-BitsPPix)) - b2;
  537.             d2 += tmp*tmp;
  538.             if (d2<dist) { dist = d2;  oval = cj; }
  539.             }
  540.             histogram[r2][g2][b2] = oval;
  541.         }
  542.  
  543.         *outptr++ = oval;
  544.         r1 -= rg_cmap[RED][oval];
  545.         g1 -= rg_cmap[GREEN][oval];
  546.         b1 -= rg_cmap[BLUE][oval];
  547.         /* can't use tables because r1,g1,b1 go negative */
  548.  
  549.         if (!lastpixel) {
  550.             thisptr[0] += r1*7 >> 4;
  551.             thisptr[1] += g1*7 >> 4;
  552.             thisptr[2] += b1*7 >> 4;
  553.         }
  554.  
  555.         if (!lastline) {
  556.             if (j) {
  557.             nextptr[-3] += r1*3 >> 4;
  558.             nextptr[-2] += g1*3 >> 4;
  559.             nextptr[-1] += b1*3 >> 4;
  560.             }
  561.  
  562.             nextptr[0] += r1*5 >> 4;
  563.             nextptr[1] += g1*5 >> 4;
  564.             nextptr[2] += b1*5 >> 4;
  565.  
  566.             if (!lastpixel) {
  567.             nextptr[3] += r1 >> 4;
  568.             nextptr[4] += g1 >> 4;
  569.             nextptr[5] += b1 >> 4;
  570.             }
  571.             nextptr += 3;
  572.         }
  573.         }
  574.     }
  575.     free(thisline);
  576.     free(nextline);
  577. return    0;
  578. }
  579.  
  580.  
  581. quant_to_8(img, i, rg_cmap, obuf)
  582. U_IMAGE    *img;
  583. cmap_t    *rg_cmap[];
  584. VType    *obuf;
  585. {
  586. CBOX    *box_list, *ptr;
  587.  
  588.     if (img->color_form == CFM_ILL)    {
  589.     register char    *buffer = img->src;
  590.         img->src = nzalloc(img->width*img->height, 3, "l_2_c");
  591.         line_to_cell_color(img->src, buffer, img->width, img->height);
  592.         free(buffer);
  593.     }
  594.     height = img->height;    width = img->width;    num_colors = i;
  595.     usedboxes = NULL;
  596.     box_list = freeboxes = (CBOX *) zalloc(num_colors, sizeof(CBOX),
  597.                     "to8() - 'freeboxes'\n");
  598.  
  599.     for (i=0; i<num_colors; i++) {
  600.         freeboxes[i].next = &freeboxes[i+1];
  601.         freeboxes[i].prev = &freeboxes[i-1];
  602.     }
  603.     freeboxes[0].prev = NULL;
  604.     freeboxes[num_colors-1].next = NULL;
  605.  
  606.     ptr = freeboxes;
  607.     freeboxes = ptr->next;
  608.     if (freeboxes)
  609.         freeboxes->prev = NULL;
  610.  
  611.     ptr->next = usedboxes;
  612.     usedboxes = ptr;
  613.     if (ptr->next)    ptr->next->prev = ptr;
  614.  
  615.     calc_histogram(img->src, ptr);
  616.  
  617.     fill_freeboxes();
  618.  
  619.     for (i=0, ptr=usedboxes; i<num_colors && ptr; i++, ptr=ptr->next)
  620.     assign_color(ptr, rg_cmap[RED]+i, rg_cmap[GREEN]+i, rg_cmap[BLUE]+i);
  621.  
  622.     num_colors = i;
  623.     free(box_list);
  624.     box_list = freeboxes = usedboxes = NULL;
  625.  
  626.     ColorCells = (CCELL **) zalloc(C_LEN*C_LEN*C_LEN, sizeof(CCELL *),
  627.             "CCELL");
  628.  
  629.     map_colortable(rg_cmap);
  630.  
  631.     i = quant_fsdither(img->src, obuf, rg_cmap);
  632.  
  633.     free(ColorCells);
  634. return    i;
  635. }
  636.