home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / x / volume10 / xv / part08 < prev    next >
Text File  |  1990-12-09  |  24KB  |  1,009 lines
  1. Path: uunet!cs.utexas.edu!sun-barr!newstop!exodus!appserv!halibut.cis.upenn.edu
  2. From: bradley@halibut.cis.upenn.edu (John Bradley)
  3. Newsgroups: comp.sources.x
  4. Subject: v10i086: xv - display and manipulate images, Part08/10
  5. Message-ID: <324@appserv.Eng.Sun.COM>
  6. Date: 27 Nov 90 20:08:41 GMT
  7. References: <csx-10i079:xv@uunet.UU.NET>
  8. Sender: news@exodus.Eng.Sun.COM
  9. Lines: 992
  10. Approved: argv@sun.com
  11.  
  12. Submitted-by: bradley@halibut.cis.upenn.edu (John Bradley)
  13. Posting-number: Volume 10, Issue 86
  14. Archive-name: xv/part08
  15.  
  16. #!/bin/sh
  17. # to extract, remove the header and type "sh filename"
  18. if `test ! -s ./xv24to8.c`
  19. then
  20. echo "writting ./xv24to8.c"
  21. cat > ./xv24to8.c << '\BARFOO\'
  22. /*
  23.  * xv24to8.c  -  contains the 24-to-8-bit Conv24to8 procedure
  24.  *
  25.  * The Conv24to8 procedure takes a pointer to a 24-bit image (loaded
  26.  * previously).  The image will be a w * h * 3 byte array of
  27.  * bytes.  The image will be arranged with 3 bytes per pixel (in order
  28.  * R, G, and B), pixel 0 at the top left corner.  (As normal.)
  29.  * The procedure also takes a maximum number of colors to use (numcols)
  30.  *
  31.  * The Conv24to8 procedure will set up the following:  it will allocate and
  32.  * create 'pic', a pWIDE*pHIGH 8-bit picture.  it will set up pWIDE and pHIGH.
  33.  * it will load up the r[], g[], and b[] colormap arrays.  it will NOT 
  34.  * calculate numcols, since the cmap sort procedure has to be called anyway
  35.  *
  36.  * Conv24to8 returns '0' if successful, '1' if it failed (presumably on a 
  37.  * malloc())
  38.  *
  39.  * contains:
  40.  *   Cont24to8()
  41.  *   InitFSDTables()
  42.  */
  43.  
  44. /*
  45.  * Copyright 1989, 1990 by the University of Pennsylvania
  46.  *
  47.  * Permission to use, copy, and distribute for non-commercial purposes,
  48.  * is hereby granted without fee, providing that the above copyright
  49.  * notice appear in all copies and that both the copyright notice and this
  50.  * permission notice appear in supporting documentation.
  51.  *
  52.  * The software may be modified for your own purposes, but modified versions
  53.  * may not be distributed.
  54.  *
  55.  * This software is provided "as is" without any express or implied warranty.
  56.  */
  57.  
  58. #include "xv.h"
  59.  
  60. #define    MAX_CMAP_SIZE    256
  61. #define    COLOR_DEPTH    8
  62. #define    MAX_COLOR    256
  63. #define    B_DEPTH        5        /* # bits/pixel to use */
  64. #define    B_LEN        (1<<B_DEPTH)
  65. #define    C_DEPTH        2
  66. #define    C_LEN        (1<<C_DEPTH)    /* # cells/color to use */
  67.  
  68. typedef    struct colorbox {
  69.   struct colorbox *next, *prev;
  70.   int              rmin,rmax, gmin,gmax, bmin,bmax;
  71.   int              total;
  72. } CBOX;
  73.  
  74. typedef struct {
  75.   int num_ents;
  76.   int entries[MAX_CMAP_SIZE][2];
  77. } CCELL;
  78.  
  79. static byte *pic24;
  80. static int   num_colors, WIDE, HIGH;
  81. static int   histogram[B_LEN][B_LEN][B_LEN];
  82.  
  83. CBOX   *freeboxes, *usedboxes;
  84. CCELL **ColorCells;
  85.  
  86. static void   get_histogram();
  87. static CBOX  *largest_box();
  88. static void   splitbox();
  89. static void   shrinkbox();
  90. static void   assign_color();
  91. static CCELL *create_colorcell();
  92. static void   map_colortable();
  93. static int    quant_fsdither();
  94. static int    Quick24to8();
  95. static int    QuickCheck();
  96.  
  97. static byte   tbl1[256],     /* tables used in F-S Dithering */
  98.               tbl3[256],     /* contain i/16, 3i/16, 5i/16, 7i/16, */
  99.               tbl5[256],     /* (i=0-255) respectively */
  100.               tbl7[256];
  101.  
  102.  
  103. /****************************/
  104. int Conv24to8(p,w,h,nc)
  105. /****************************/
  106. byte *p;
  107. int   w,h,nc;
  108. {
  109.   int   i;
  110.   CBOX *box_list, *ptr;
  111.  
  112.   /* copy arguments to local-global variables */
  113.   pic24 = p;  pWIDE = WIDE = w;  pHIGH = HIGH = h;  num_colors = nc;
  114.  
  115.  
  116.   /* allocate pic immediately, so that if we can't allocate it, we don't
  117.      waste time running this algorithm */
  118.  
  119.   pic = (byte *) malloc(WIDE * HIGH);
  120.   if (pic == NULL) {
  121.     fprintf(stderr,"%s: Conv24to8() - failed to allocate 'pic'\n",cmd);
  122.     return(1);
  123.   }
  124.  
  125.  
  126.   /* quick check:  if we're going to display a greyscale or 1-bit image,
  127.      DON'T run this annoyingly time-consuming code.  Just convert the 24-bit
  128.      color image to an 8-bit greyscale.  This takes virtually no time, by
  129.      comparision, and it has the same effect. */
  130.  
  131.   if (mono || nc==0) {
  132.     byte *pp, *p24;
  133.  
  134.     for (i=0; i<256; i++) r[i]=g[i]=b[i]=i;   /* greyscale colormap */
  135.     pp = pic;  p24 = pic24;
  136.     for (i=WIDE*HIGH; i>0; i--, pp++, p24+=3) 
  137.       *pp = (p24[0]*11 + p24[1]*16 + p24[2]*5) >> 5;  /* pp=.33R+.5G+.17B */
  138.  
  139.     return(0);
  140.   }
  141.  
  142.   if (!noqcheck && QuickCheck(pic24,w,h,nc)) { 
  143.     /* see if it's a <256 color RGB pic */
  144.     SetISTR(ISTR_INFO,"No color compression was necessary.\n");
  145.     return 0;   
  146.   }
  147.   else if (!slow24) {
  148.     SetISTR(ISTR_INFO,"Doing quick 24-bit to 8-bit conversion.");
  149.     return(Quick24to8(pic24,w,h));
  150.   }
  151.   else 
  152.     SetISTR(ISTR_INFO,"Doing full 24-bit to 8-bit conversion.");
  153.  
  154.  
  155.   /**** STEP 1:  create empty boxes ****/
  156.  
  157.   usedboxes = NULL;
  158.   box_list = freeboxes = (CBOX *) malloc(num_colors * sizeof(CBOX));
  159.  
  160.   if (box_list == NULL) {
  161.     fprintf(stderr,"%s: Conv24to8() - failed to allocate 'freeboxes'\n",cmd);
  162.     return(1);
  163.   }
  164.  
  165.   for (i=0; i<num_colors; i++) {
  166.     freeboxes[i].next = &freeboxes[i+1];
  167.     freeboxes[i].prev = &freeboxes[i-1];
  168.   }
  169.   freeboxes[0].prev = NULL;
  170.   freeboxes[num_colors-1].next = NULL;
  171.  
  172.  
  173.   /**** STEP 2: get histogram, initialize first box ****/
  174.  
  175.   ptr = freeboxes;
  176.   freeboxes = ptr->next;
  177.   if (freeboxes) freeboxes->prev = NULL;
  178.  
  179.   ptr->next = usedboxes;
  180.   usedboxes = ptr;
  181.   if (ptr->next) ptr->next->prev = ptr;
  182.     
  183.   get_histogram(ptr);
  184.  
  185.  
  186.   /**** STEP 3: continually subdivide boxes until no more free boxes remain */
  187.  
  188.   while (freeboxes) {
  189.     ptr = largest_box();
  190.     if (ptr) splitbox(ptr);
  191.     else break;
  192.   }
  193.  
  194.   
  195.   /**** STEP 4: assign colors to all boxes ****/
  196.  
  197.   for (i=0, ptr=usedboxes; i<num_colors && ptr; i++, ptr=ptr->next) {
  198.     assign_color(ptr, &r[i], &g[i], &b[i]);
  199.   }
  200.  
  201.   /* We're done with the boxes now */
  202.   num_colors = i;
  203.   free(box_list);
  204.   box_list = freeboxes = usedboxes = NULL;
  205.  
  206.  
  207.   /**** STEP 5: scan histogram and map all values to closest color */
  208.  
  209.   /* 5a: create cell list as described in Heckbert[2] */
  210.  
  211.   ColorCells = (CCELL **) calloc(C_LEN*C_LEN*C_LEN, sizeof(CCELL *));
  212.  
  213.  
  214.   /* 5b: create mapping from truncated pixel space to color table entries */
  215.  
  216.   map_colortable();
  217.  
  218.  
  219.   /**** STEP 6: scan image, match input values to table entries */
  220.  
  221.   i=quant_fsdither();
  222.  
  223.   /* free everything that can be freed */
  224.   free(ColorCells);
  225.  
  226.   return i;
  227. }
  228.  
  229.  
  230. /****************************/
  231. static void get_histogram(box)
  232.      CBOX *box;
  233. /****************************/
  234. {
  235.   int   i,j,r,g,b,*ptr;
  236.   byte *p;
  237.  
  238.   box->rmin = box->gmin = box->bmin = 999;
  239.   box->rmax = box->gmax = box->bmax = -1;
  240.   box->total = WIDE * HIGH;
  241.  
  242.   /* zero out histogram */
  243.   ptr = &histogram[0][0][0];
  244.   for (i=B_LEN*B_LEN*B_LEN; i>0; i-- )  *ptr++ = 0;
  245.  
  246.   /* calculate histogram */
  247.   p = pic24;
  248.   for (i=0; i<HIGH; i++)
  249.     for (j=0; j<WIDE; j++) {
  250.       r = (*p++) >> (COLOR_DEPTH-B_DEPTH);
  251.       g = (*p++) >> (COLOR_DEPTH-B_DEPTH);
  252.       b = (*p++) >> (COLOR_DEPTH-B_DEPTH);
  253.  
  254.       if (r < box->rmin) box->rmin = r;
  255.       if (r > box->rmax) box->rmax = r;
  256.  
  257.       if (g < box->gmin) box->gmin = g;
  258.       if (g > box->gmax) box->gmax = g;
  259.  
  260.       if (b < box->bmin) box->bmin = b;
  261.       if (b > box->bmax) box->bmax = b;
  262.       histogram[r][g][b]++;
  263.     }
  264. }
  265.  
  266.  
  267.  
  268. /******************************/
  269. static CBOX *largest_box()
  270. /******************************/
  271. {
  272.   CBOX *tmp, *ptr;
  273.   int   size = -1;
  274.  
  275.   tmp = usedboxes;
  276.   ptr = NULL;
  277.  
  278.   while (tmp) {
  279.     if ( (tmp->rmax > tmp->rmin  ||
  280.       tmp->gmax > tmp->gmin  ||
  281.       tmp->bmax > tmp->bmin)  &&  tmp->total > size ) {
  282.       ptr = tmp;
  283.       size = tmp->total;
  284.     }
  285.     tmp = tmp->next;
  286.   }
  287.   return(ptr);
  288. }
  289.  
  290.  
  291.  
  292. /******************************/
  293. static void splitbox(ptr)
  294.      CBOX *ptr;
  295. /******************************/
  296. {
  297.   int   hist2[B_LEN], first, last, i, rdel, gdel, bdel;
  298.   CBOX *new;
  299.   int  *iptr, *histp, ir, ig, ib;
  300.   int  rmin,rmax,gmin,gmax,bmin,bmax;
  301.   enum {RED,GREEN,BLUE} which;
  302.  
  303.   /*
  304.    * see which axis is the largest, do a histogram along that
  305.    * axis.  Split at median point.  Contract both new boxes to
  306.    * fit points and return
  307.    */
  308.  
  309.   first = last = 0;   /* shut RT hcc compiler up */
  310.  
  311.   rmin = ptr->rmin;  rmax = ptr->rmax;
  312.   gmin = ptr->gmin;  gmax = ptr->gmax;
  313.   bmin = ptr->bmin;  bmax = ptr->bmax;
  314.  
  315.   rdel = rmax - rmin;
  316.   gdel = gmax - gmin;
  317.   bdel = bmax - bmin;
  318.  
  319.   if      (rdel>=gdel && rdel>=bdel) which = RED;
  320.   else if (gdel>=bdel)               which = GREEN;
  321.   else                               which = BLUE;
  322.  
  323.   /* get histogram along longest axis */
  324.   switch (which) {
  325.  
  326.   case RED:
  327.     histp = &hist2[rmin];
  328.     for (ir=rmin; ir<=rmax; ir++) {
  329.       *histp = 0;
  330.       for (ig=gmin; ig<=gmax; ig++) {
  331.     iptr = &histogram[ir][ig][bmin];
  332.     for (ib=bmin; ib<=bmax; ib++) {
  333.       *histp += *iptr;
  334.       ++iptr;
  335.     }
  336.       }
  337.       ++histp;
  338.     }
  339.     first = rmin;  last = rmax;
  340.     break;
  341.  
  342.   case GREEN:
  343.     histp = &hist2[gmin];
  344.     for (ig=gmin; ig<=gmax; ig++) {
  345.       *histp = 0;
  346.       for (ir=rmin; ir<=rmax; ir++) {
  347.     iptr = &histogram[ir][ig][bmin];
  348.     for (ib=bmin; ib<=bmax; ib++) {
  349.       *histp += *iptr;
  350.       ++iptr;
  351.     }
  352.       }
  353.       ++histp;
  354.     }
  355.     first = gmin;  last = gmax;
  356.     break;
  357.  
  358.   case BLUE:
  359.     histp = &hist2[bmin];
  360.     for (ib=bmin; ib<=bmax; ib++) {
  361.       *histp = 0;
  362.       for (ir=rmin; ir<=rmax; ir++) {
  363.     iptr = &histogram[ir][gmin][ib];
  364.     for (ig=gmin; ig<=gmax; ig++) {
  365.       *histp += *iptr;
  366.       iptr += B_LEN;
  367.     }
  368.       }
  369.       ++histp;
  370.     }
  371.     first = bmin;  last = bmax;
  372.     break;
  373.   }
  374.  
  375.  
  376.   /* find median point */
  377.   {
  378.     int sum, sum2;
  379.  
  380.     histp = &hist2[first];
  381.  
  382.     sum2 = ptr->total/2;
  383.     histp = &hist2[first];
  384.     sum = 0;
  385.         
  386.     for (i=first; i<=last && (sum += *histp++)<sum2; i++);
  387.     if (i==first) i++;
  388.   }
  389.  
  390.  
  391.   /* Create new box, re-allocate points */
  392.   
  393.   new = freeboxes;
  394.   freeboxes = new->next;
  395.   if (freeboxes) freeboxes->prev = NULL;
  396.  
  397.   if (usedboxes) usedboxes->prev = new;
  398.   new->next = usedboxes;
  399.   usedboxes = new;
  400.  
  401.   {
  402.     int sum1,sum2,j;
  403.     
  404.     histp = &hist2[first];
  405.     sum1 = 0;
  406.     for (j = first; j < i; ++j) sum1 += *histp++;
  407.     sum2 = 0;
  408.     for (j = i; j <= last; ++j) sum2 += *histp++;
  409.     new->total = sum1;
  410.     ptr->total = sum2;
  411.   }
  412.  
  413.  
  414.   new->rmin = rmin;  new->rmax = rmax;
  415.   new->gmin = gmin;  new->gmax = gmax;
  416.   new->bmin = bmin;  new->bmax = bmax;
  417.  
  418.   switch (which) {
  419.   case RED:    new->rmax = i-1;  ptr->rmin = i;  break;
  420.   case GREEN:  new->gmax = i-1;  ptr->gmin = i;  break;
  421.   case BLUE:   new->bmax = i-1;  ptr->bmin = i;  break;
  422.   }
  423.  
  424.   shrinkbox(new);
  425.   shrinkbox(ptr);
  426. }
  427.  
  428.  
  429. /****************************/
  430. static void shrinkbox(box)
  431.      CBOX *box;
  432. /****************************/
  433. {
  434.   int *histp,ir,ig,ib;
  435.   int  rmin,rmax,gmin,gmax,bmin,bmax;
  436.  
  437.   rmin = box->rmin;  rmax = box->rmax;
  438.   gmin = box->gmin;  gmax = box->gmax;
  439.   bmin = box->bmin;  bmax = box->bmax;
  440.  
  441.   if (rmax>rmin) {
  442.     for (ir=rmin; ir<=rmax; ir++)
  443.       for (ig=gmin; ig<=gmax; ig++) {
  444.     histp = &histogram[ir][ig][bmin];
  445.     for (ib=bmin; ib<=bmax; ib++)
  446.       if (*histp++ != 0) {
  447.         box->rmin = rmin = ir;
  448.         goto have_rmin;
  449.       }
  450.       }
  451.  
  452.   have_rmin:
  453.     if (rmax>rmin)
  454.       for (ir=rmax; ir>=rmin; --ir)
  455.     for (ig=gmin; ig<=gmax; ig++) {
  456.       histp = &histogram[ir][ig][bmin];
  457.       for (ib=bmin; ib<=bmax; ib++)
  458.         if (*histp++ != 0) {
  459.           box->rmax = rmax = ir;
  460.           goto have_rmax;
  461.         }
  462.     }
  463.   }
  464.  
  465.  
  466.  have_rmax:
  467.  
  468.   if (gmax>gmin) {
  469.     for (ig=gmin; ig<=gmax; ig++)
  470.       for (ir=rmin; ir<=rmax; ir++) {
  471.     histp = &histogram[ir][ig][bmin];
  472.     for (ib=bmin; ib<=bmax; ib++)
  473.       if (*histp++ != 0) {
  474.         box->gmin = gmin = ig;
  475.         goto have_gmin;
  476.       }
  477.       }
  478.   have_gmin:
  479.     if (gmax>gmin)
  480.       for (ig=gmax; ig>=gmin; --ig)
  481.     for (ir=rmin; ir<=rmax; ir++) {
  482.       histp = &histogram[ir][ig][bmin];
  483.       for (ib=bmin; ib<=bmax; ib++)
  484.         if (*histp++ != 0) {
  485.           box->gmax = gmax = ig;
  486.           goto have_gmax;
  487.         }
  488.     }
  489.   }
  490.  
  491.  
  492.  have_gmax:
  493.  
  494.   if (bmax>bmin) {
  495.     for (ib=bmin; ib<=bmax; ib++)
  496.       for (ir=rmin; ir<=rmax; ir++) {
  497.     histp = &histogram[ir][gmin][ib];
  498.     for (ig=gmin; ig<=gmax; ig++) {
  499.       if (*histp != 0) {
  500.         box->bmin = bmin = ib;
  501.         goto have_bmin;
  502.       }
  503.       histp += B_LEN;
  504.     }
  505.       }
  506.   have_bmin:
  507.     if (bmax>bmin)
  508.       for (ib=bmax; ib>=bmin; --ib)
  509.     for (ir=rmin; ir<=rmax; ir++) {
  510.       histp = &histogram[ir][gmin][ib];
  511.       for (ig=gmin; ig<=gmax; ig++) {
  512.         if (*histp != 0) {
  513.           bmax = ib;
  514.           goto have_bmax;
  515.         }
  516.         histp += B_LEN;
  517.       }
  518.     }
  519.   }
  520.  
  521.  have_bmax: return;
  522. }
  523.  
  524.  
  525.  
  526. /*******************************/
  527. static void assign_color(ptr,rp,gp,bp)
  528.      CBOX *ptr;
  529.      byte *rp,*gp,*bp;
  530. /*******************************/
  531. {
  532.   *rp = ((ptr->rmin + ptr->rmax) << (COLOR_DEPTH - B_DEPTH)) / 2;
  533.   *gp = ((ptr->gmin + ptr->gmax) << (COLOR_DEPTH - B_DEPTH)) / 2;
  534.   *bp = ((ptr->bmin + ptr->bmax) << (COLOR_DEPTH - B_DEPTH)) / 2;
  535. }
  536.  
  537.  
  538.  
  539. /*******************************/
  540. static CCELL *create_colorcell(r1,g1,b1)
  541.      int r1,g1,b1;
  542. /*******************************/
  543. {
  544.   register int    i,tmp, dist;
  545.   register CCELL *ptr;
  546.   register byte  *rp,*gp,*bp;
  547.   int             ir,ig,ib, mindist;
  548.  
  549.   ir = r1 >> (COLOR_DEPTH-C_DEPTH);
  550.   ig = g1 >> (COLOR_DEPTH-C_DEPTH);
  551.   ib = b1 >> (COLOR_DEPTH-C_DEPTH);
  552.  
  553.   r1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
  554.   g1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
  555.   b1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
  556.  
  557.   ptr = (CCELL *) malloc(sizeof(CCELL));
  558.   *(ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib) = ptr;
  559.   ptr->num_ents = 0;
  560.  
  561.   /* step 1: find all colors inside this cell, while we're at
  562.      it, find distance of centermost point to furthest
  563.      corner */
  564.  
  565.   mindist = 99999999;
  566.  
  567.   rp=r;  gp=g;  bp=b;
  568.   for (i=0; i<num_colors; i++,rp++,gp++,bp++)
  569.     if( *rp>>(COLOR_DEPTH-C_DEPTH) == ir  &&
  570.         *gp>>(COLOR_DEPTH-C_DEPTH) == ig  &&
  571.         *bp>>(COLOR_DEPTH-C_DEPTH) == ib) {
  572.  
  573.       ptr->entries[ptr->num_ents][0] = i;
  574.       ptr->entries[ptr->num_ents][1] = 0;
  575.       ++ptr->num_ents;
  576.  
  577.       tmp = *rp - r1;
  578.       if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
  579.       dist = tmp*tmp;
  580.  
  581.       tmp = *gp - g1;
  582.       if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
  583.       dist += tmp*tmp;
  584.  
  585.       tmp = *bp - b1;
  586.       if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
  587.       dist += tmp*tmp;
  588.  
  589.       if (dist < mindist) mindist = dist;
  590.     }
  591.  
  592.  
  593.   /* step 3: find all points within that distance to box */
  594.  
  595.   rp=r;  gp=g;  bp=b;
  596.   for (i=0; i<num_colors; i++,rp++,gp++,bp++)
  597.     if (*rp >> (COLOR_DEPTH-C_DEPTH) != ir  ||
  598.     *gp >> (COLOR_DEPTH-C_DEPTH) != ig  ||
  599.     *bp >> (COLOR_DEPTH-C_DEPTH) != ib) {
  600.  
  601.       dist = 0;
  602.  
  603.       if ((tmp = r1 - *rp)>0 || (tmp = *rp - (r1 + MAX_COLOR/C_LEN-1)) > 0 )
  604.     dist += tmp*tmp;
  605.  
  606.       if( (tmp = g1 - *gp)>0 || (tmp = *gp - (g1 + MAX_COLOR/C_LEN-1)) > 0 )
  607.     dist += tmp*tmp;
  608.  
  609.       if( (tmp = b1 - *bp)>0 || (tmp = *bp - (b1 + MAX_COLOR/C_LEN-1)) > 0 )
  610.     dist += tmp*tmp;
  611.  
  612.       if( dist < mindist ) {
  613.     ptr->entries[ptr->num_ents][0] = i;
  614.     ptr->entries[ptr->num_ents][1] = dist;
  615.     ++ptr->num_ents;
  616.       }
  617.     }
  618.  
  619.  
  620.   /* sort color cells by distance, use cheap exchange sort */
  621.   {
  622.     int n, next_n;
  623.  
  624.     n = ptr->num_ents - 1;
  625.     while (n>0) {
  626.       next_n = 0;
  627.       for (i=0; i<n; ++i) {
  628.     if (ptr->entries[i][1] > ptr->entries[i+1][1]) {
  629.       tmp = ptr->entries[i][0];
  630.       ptr->entries[i][0] = ptr->entries[i+1][0];
  631.       ptr->entries[i+1][0] = tmp;
  632.       tmp = ptr->entries[i][1];
  633.       ptr->entries[i][1] = ptr->entries[i+1][1];
  634.       ptr->entries[i+1][1] = tmp;
  635.       next_n = i;
  636.     }
  637.       }
  638.       n = next_n;
  639.     }
  640.   }
  641.   return (ptr);
  642. }
  643.  
  644.  
  645.  
  646.  
  647. /***************************/
  648. static void map_colortable()
  649. /***************************/
  650. {
  651.   int    ir,ig,ib, *histp;
  652.   CCELL *cell;
  653.  
  654.   histp  = &histogram[0][0][0];
  655.   for (ir=0; ir<B_LEN; ir++)
  656.     for (ig=0; ig<B_LEN; ig++)
  657.       for (ib=0; ib<B_LEN; ib++) {
  658.     if (*histp==0) *histp = -1;
  659.     else {
  660.       int    i, j, tmp, d2, dist;
  661.       
  662.       cell = *(ColorCells +
  663.            ( ((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2)
  664.            + ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH)
  665.            +  (ib>>(B_DEPTH-C_DEPTH)) ) );
  666.         
  667.       if (cell==NULL)
  668.         cell = create_colorcell(ir<<(COLOR_DEPTH-B_DEPTH),
  669.                     ig<<(COLOR_DEPTH-B_DEPTH),
  670.                     ib<<(COLOR_DEPTH-B_DEPTH));
  671.  
  672.       dist = 9999999;
  673.       for (i=0; i<cell->num_ents && dist>cell->entries[i][1]; i++) {
  674.         j = cell->entries[i][0];
  675.         d2 = r[j] - (ir << (COLOR_DEPTH-B_DEPTH));
  676.         d2 *= d2;
  677.         tmp = g[j] - (ig << (COLOR_DEPTH-B_DEPTH));
  678.         d2 += tmp*tmp;
  679.         tmp = b[j] - (ib << (COLOR_DEPTH-B_DEPTH));
  680.         d2 += tmp*tmp;
  681.         if( d2 < dist ) { dist = d2;  *histp = j; }
  682.       }
  683.     }
  684.     histp++;
  685.       }
  686. }
  687.  
  688.  
  689.  
  690. /*****************************/
  691. static int quant_fsdither()
  692. /*****************************/
  693. {
  694.   register int  *thisptr, *nextptr;
  695.   int           *thisline, *nextline, *tmpptr;
  696.   int            r1, g1, b1, r2, g2, b2;
  697.   int            i, j, imax, jmax, oval;
  698.   byte          *inptr, *outptr, *tmpbptr;
  699.   int            lastline, lastpixel;
  700.  
  701.   imax = HIGH - 1;
  702.   jmax = WIDE - 1;
  703.   
  704.   thisline = (int *) malloc(WIDE * 3 * sizeof(int));
  705.   nextline = (int *) malloc(WIDE * 3 * sizeof(int));
  706.  
  707.   if (thisline == NULL || nextline == NULL) {
  708.     fprintf(stderr,"%s: unable to allocate stuff for the 'dither' routine\n",
  709.         cmd);
  710.     return 1;
  711.   }
  712.  
  713.  
  714.   inptr  = (byte *) pic24;
  715.   outptr = (byte *) pic;
  716.  
  717.   /* get first line of picture */
  718.   for (j=WIDE * 3, tmpptr=nextline, tmpbptr=inptr; j; j--) 
  719.     *tmpptr++ = (int) *tmpbptr++;
  720.  
  721.   for (i=0; i<HIGH; i++) {
  722.     /* swap thisline and nextline */
  723.     tmpptr = thisline;  thisline = nextline;  nextline = tmpptr;
  724.     lastline = (i==imax);
  725.  
  726.     /* read in next line */
  727.     for (j=WIDE * 3, tmpptr=nextline; j; j--) 
  728.       *tmpptr++ = (int) *inptr++;
  729.  
  730.     /* dither this line and put it into the output picture */
  731.     thisptr = thisline;  nextptr = nextline;
  732.  
  733.     for (j=0; j<WIDE; j++) {
  734.       lastpixel = (j==jmax);
  735.  
  736.       r2 = *thisptr++;  g2 = *thisptr++;  b2 = *thisptr++;
  737.  
  738.       if (r2<0) r2=0;  else if (r2>=MAX_COLOR) r2=MAX_COLOR-1;
  739.       if (g2<0) g2=0;  else if (g2>=MAX_COLOR) g2=MAX_COLOR-1;
  740.       if (b2<0) b2=0;  else if (b2>=MAX_COLOR) b2=MAX_COLOR-1;
  741.  
  742.       r1 = r2;  g1 = g2;  b1 = b2;
  743.  
  744.       r2 >>= (COLOR_DEPTH-B_DEPTH);
  745.       g2 >>= (COLOR_DEPTH-B_DEPTH);
  746.       b2 >>= (COLOR_DEPTH-B_DEPTH);
  747.  
  748.       if ( (oval=histogram[r2][g2][b2]) == -1) {
  749.     int ci, cj, dist, d2, tmp;
  750.     CCELL *cell;
  751.  
  752.     cell = *( ColorCells + 
  753.         ( ((r2>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2)
  754.             + ((g2>>(B_DEPTH-C_DEPTH)) << C_DEPTH )
  755.         +  (b2>>(B_DEPTH-C_DEPTH)) ) );
  756.           
  757.     if (cell==NULL) cell = create_colorcell(r1,g1,b1);
  758.  
  759.     dist = 9999999;
  760.     for (ci=0; ci<cell->num_ents && dist>cell->entries[ci][1]; ci++) {
  761.       cj = cell->entries[ci][0];
  762.       d2 = (r[cj] >> (COLOR_DEPTH-B_DEPTH)) - r2;
  763.       d2 *= d2;
  764.       tmp = (g[cj] >> (COLOR_DEPTH-B_DEPTH)) - g2;
  765.       d2 += tmp*tmp;
  766.       tmp = (b[cj] >> (COLOR_DEPTH-B_DEPTH)) - b2;
  767.       d2 += tmp*tmp;
  768.       if (d2<dist) { dist = d2;  oval = cj; }
  769.     }
  770.     histogram[r2][g2][b2] = oval;
  771.       }
  772.  
  773.       *outptr++ = oval;
  774.  
  775.       r1 -= r[oval];  g1 -= g[oval];  b1 -= b[oval];
  776.       /* can't use tables because r1,g1,b1 go negative */
  777.  
  778.       if (!lastpixel) {
  779.     thisptr[0] += (r1*7)/16;
  780.     thisptr[1] += (g1*7)/16;
  781.     thisptr[2] += (b1*7)/16;
  782.       }
  783.  
  784.       if (!lastline) {
  785.     if (j) {
  786.       nextptr[-3] += (r1*3)/16;
  787.       nextptr[-2] += (g1*3)/16;
  788.       nextptr[-1] += (b1*3)/16;
  789.     }
  790.  
  791.     nextptr[0] += (r1*5)/16;
  792.     nextptr[1] += (g1*5)/16;
  793.     nextptr[2] += (b1*5)/16;
  794.  
  795.     if (!lastpixel) {
  796.       nextptr[3] += r1/16;
  797.       nextptr[4] += g1/16;
  798.       nextptr[5] += b1/16;
  799.     }
  800.     nextptr += 3;
  801.       }
  802.     }
  803.   }
  804.   free(thisline);  free(nextline);
  805.   return 0;
  806. }
  807.  
  808.  
  809.  
  810.  
  811.  
  812. /************************************/
  813. static int Quick24to8(p24,w,h)
  814. byte *p24;
  815. int   w,h;
  816. {
  817.  
  818.   /* floyd-steinberg dithering.
  819.    *
  820.    * ----   x    7/16
  821.    * 3/16  5/16  1/16
  822.    *
  823.    */
  824.  
  825.   /* called after 'pic' has been alloced, pWIDE,pHIGH set up, mono/1-bit
  826.      checked already */
  827.  
  828.   byte *pp;
  829.   int  r1, g1, b1;
  830.   int  *thisline, *nextline, *thisptr, *nextptr, *tmpptr;
  831.   int  i, j, rerr, gerr, berr, pwide3;
  832.   int  imax, jmax;
  833.  
  834.   pp = pic;  pwide3 = w * 3;  imax = h-1;  jmax = w-1;
  835.  
  836.   /* load up colormap, 3 bits R, 3 bits G, 2 bits B  (RRRGGGBB) */
  837.   for (i=0; i<256; i++) {
  838.     r[i] =  ((i&0xe0) * 255) / 0xe0;  
  839.     g[i] =  ((i&0x1c) * 255) / 0x1c;
  840.     b[i] =  ((i&0x03) * 255) / 0x03;
  841.   }
  842.  
  843.   thisline = (int *) malloc(pwide3 * sizeof(int));
  844.   nextline = (int *) malloc(pwide3 * sizeof(int));
  845.   if (!thisline || !nextline) {
  846.     fprintf(stderr,"%s: unable to allocate memory in Quick24to8()\n", cmd);
  847.     return(1);
  848.     }
  849.  
  850.   /* get first line of picture */
  851.   for (j=pwide3, tmpptr=nextline; j; j--) *tmpptr++ = (int) *p24++;
  852.  
  853.   for (i=0; i<h; i++) {
  854.     tmpptr = thisline;  thisline = nextline;  nextline = tmpptr;   /* swap */
  855.  
  856.     if (i!=imax)   /* get next line */
  857.       for (j=pwide3, tmpptr=nextline; j; j--)
  858.     *tmpptr++ = (int) *p24++;
  859.  
  860.     for (j=0, thisptr=thisline, nextptr=nextline; j<w; j++,pp++) {
  861.       r1 = *thisptr++;  g1 = *thisptr++;  b1 = *thisptr++;
  862.       RANGE(r1,0,255);  RANGE(g1,0,255);  RANGE(b1,0,255);  
  863.  
  864.       rerr = r1 & 0x1f;  gerr = g1 & 0x1f;  berr = b1 & 0x3f;
  865.       *pp = (r1&0xe0) | ((g1>>3)&0x1c) | (b1>>6); 
  866.  
  867.       if (j!=jmax) {  /* adjust RIGHT pixel */
  868.     thisptr[0] += tbl7[rerr];
  869.     thisptr[1] += tbl7[gerr];
  870.     thisptr[2] += tbl7[berr];
  871.       }
  872.       
  873.       if (i!=imax) {    /* do BOTTOM pixel */
  874.     nextptr[0] += tbl5[rerr];
  875.     nextptr[1] += tbl5[gerr];
  876.     nextptr[2] += tbl5[berr];
  877.  
  878.     if (j>0) {  /* do BOTTOM LEFT pixel */
  879.       nextptr[-3] += tbl3[rerr];
  880.       nextptr[-2] += tbl3[gerr];
  881.       nextptr[-1] += tbl3[berr];
  882.     }
  883.  
  884.     if (j!=jmax) {  /* do BOTTOM RIGHT pixel */
  885.       nextptr[3] += tbl1[rerr];
  886.       nextptr[4] += tbl1[gerr];
  887.       nextptr[5] += tbl1[berr];
  888.     }
  889.     nextptr += 3;
  890.       }
  891.     }
  892.   }
  893.  
  894.   return 0;
  895. }
  896.       
  897.  
  898.  
  899. /****************************/
  900. void InitFSDTables()
  901. /****************************/
  902. {
  903.   int i;
  904.   for (i=0; i<256; i++) {     /* initialize Floyd-Steinberg division tables */
  905.     tbl1[i] = i/16;
  906.     tbl3[i] = (3*i)/16;
  907.     tbl5[i] = (5*i)/16;
  908.     tbl7[i] = (7*i)/16;
  909.   }
  910. }
  911.  
  912.  
  913.  
  914.  
  915. /****************************/
  916. static int QuickCheck(pic24,w,h,maxcol)
  917. byte *pic24;
  918. int   w,h,maxcol;
  919. {
  920.   /* scans picture until it finds more than 'maxcol' different colors.  If it
  921.      finds more than 'maxcol' colors, it returns '0'.  If it DOESN'T, it does
  922.      the 24-to-8 conversion by simply sticking the colors it found into
  923.      a colormap, and changing instances of a color in pic24 into colormap
  924.      indicies (in pic) */
  925.  
  926.   unsigned long colors[256],col;
  927.   int           i, nc, low, high, mid;
  928.   byte         *p, *pix;
  929.  
  930.   if (maxcol>256) maxcol = 256;
  931.  
  932.   /* put the first color in the table by hand */
  933.   nc = 0;  mid = 0;  
  934.  
  935.   for (i=w*h,p=pic24; i; i--) {
  936.     col  = (*p++ << 16);  
  937.     col += (*p++ << 8);
  938.     col +=  *p++;
  939.  
  940.     /* binary search the 'colors' array to see if it's in there */
  941.     low = 0;  high = nc-1;
  942.     while (low <= high) {
  943.       mid = (low+high)/2;
  944.       if      (col < colors[mid]) high = mid - 1;
  945.       else if (col > colors[mid]) low  = mid + 1;
  946.       else break;
  947.     }
  948.  
  949.     if (high < low) { /* didn't find color in list, add it. */
  950.       /* WARNING: this is an overlapped memory copy.  memcpy doesn't do
  951.      it correctly, hence 'bcopy', which claims to */
  952.       if (nc>=maxcol) return 0;
  953.       bcopy(&colors[low], &colors[low+1], (nc - low) * sizeof(unsigned long));
  954.       colors[low] = col;
  955.       nc++;
  956.     }
  957.   }
  958.  
  959.  
  960.   /* run through the data a second time, this time mapping pixel values in
  961.      pic24 into colormap offsets into 'colors' */
  962.  
  963.   for (i=w*h,p=pic24, pix=pic; i; i--,pix++) {
  964.     col  = (*p++ << 16);  
  965.     col += (*p++ << 8);
  966.     col +=  *p++;
  967.  
  968.     /* binary search the 'colors' array.  It *IS* in there */
  969.     low = 0;  high = nc-1;
  970.     while (low <= high) {
  971.       mid = (low+high)/2;
  972.       if      (col < colors[mid]) high = mid - 1;
  973.       else if (col > colors[mid]) low  = mid + 1;
  974.       else break;
  975.     }
  976.  
  977.     if (high < low) {
  978.       fprintf(stderr,"QuickCheck:  impossible!\n");
  979.       exit(1);
  980.     }
  981.     *pix = mid;
  982.   }
  983.  
  984.   /* and load up the 'desired colormap' */
  985.   for (i=0; i<nc; i++) {
  986.     r[i] =  colors[i]>>16;  
  987.     g[i] = (colors[i]>>8) & 0xff;
  988.     b[i] =  colors[i]     & 0xff;
  989.   }
  990.  
  991.   return 1;
  992. }
  993. \BARFOO\
  994. else
  995.   echo "will not over write ./xv24to8.c"
  996. fi
  997. echo "Finished archive 8 of 10"
  998. exit
  999.  
  1000. dan
  1001. ----------------------------------------------------
  1002. O'Reilly && Associates   argv@sun.com / argv@ora.com
  1003. Opinions expressed reflect those of the author only.
  1004. --
  1005. dan
  1006. ----------------------------------------------------
  1007. O'Reilly && Associates   argv@sun.com / argv@ora.com
  1008. Opinions expressed reflect those of the author only.
  1009.