home *** CD-ROM | disk | FTP | other *** search
/ QBasic & Borland Pascal & C / Delphi5.iso / C / Samples / CSAPE32.ARJ / SOURCE / OWLSCR / DIGSQCM.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-06-01  |  11.2 KB  |  372 lines
  1. /*
  2.     digsqcm.c
  3.  
  4.     % Compress the color palette for given pixel maps into a given color range.
  5.  
  6.     2/22/88 By Ted.
  7.  
  8.     OWL-DIG 1.2
  9.     Copyright (c) 1988-1990 by Oakland Group, Inc.
  10.     ALL RIGHTS RESERVED.
  11.  
  12.     Revision History:
  13.     -----------------
  14.      2/14/90 ted    Moved to dig from pc directory for access by pc & mgr code
  15.      2/29/90 ted    Added OCDECL for assembly function
  16.      3/28/90 jmd    ansi-fied
  17.      4/21/90 ted    Worked around some M6 warnings
  18.      6/01/90 jmd    preened, added some casts to hist macros
  19. */
  20.  
  21. #include "oakhead.h"
  22. #include "disppriv.h"
  23. #include "digutil.h"
  24. /* -------------------------------------------------------------------------- */
  25.  
  26. typedef struct image_struct {
  27.     pmap_type     *maps;            /* array of pmaps to be translated to new colormap */
  28.     int             nmaps;            /* number of pmaps in array */
  29.     ocolmap_type cmap;            /* old color map */
  30.     unsigned short hist[256];    /* histogram of color frequency in pmap */
  31.     byte         swaptab[256];    /* pixel map table for mapping pmap to new colormap */
  32.     unsigned      nunpicked;        /* number of unpicked colors in new table */
  33.     byte          picktab[256];    /* map table from picked color in old map to new map */
  34.     byte          nopickval;        /* place holder val for unpicked colors in picktab */
  35. } *image_type;
  36.  
  37. #define inithist(hist)            memset((VOID *)hist, 0, 256*sizeof(unsigned))
  38. #define initbtab(ptab, val)        memset((VOID *)ptab, val, 256*sizeof(byte))
  39. #define OC_BLACK                0,0,0
  40.  
  41. /* -------------------------------------------------------------------------- */
  42.  
  43. OSTATIC void     DIGPRIV pal_slide(image_type image, ocolmap_type crange);
  44. OSTATIC void     DIGPRIV pal_pickcols(image_type image, ocolmap_type crange);
  45. OSTATIC void     DIGPRIV pal_match(image_type image, ocolmap_type tcmap, pmcswap_fptr pmcswap, pmnearcol_fptr nearest);
  46. OSTATIC void     DIGPRIV initpick(image_type image);
  47. OSTATIC boolean DIGPRIV pickcol(image_type image, ocolmap_type crange, int next);
  48. OSTATIC byte     DIGPRIV markpick(image_type image, unsigned pick);
  49. OSTATIC unsigned DIGPRIV dohist(image_type image, pmhist_fptr pmhist);
  50. OSTATIC void     DIGPRIV initcswap(byte *swaptab);
  51.  
  52. /* -------------------------------------------------------------------------- */
  53.  
  54. void DIGPRIV dig_squeezecmap(pmap_type pmap, ocolmap_type cmap, ocolmap_type crange, pmhist_fptr pmhist, pmcswap_fptr pmcswap, pmnearcol_fptr nearest)
  55. /*
  56.     Compress the color palette for a given set of pixel maps into a
  57.     given color range.
  58.     NOTE: currently works only for 8 bit-per-pixel pmaps.
  59.  
  60.     'cmap'        cmap belonging to pmap
  61.     'crange'     color range to be squeezed into
  62.     'pmhist'     DIG - specific way to histogram a pmap ' s pixvals
  63.     'pmcswap'    DIG - specific way to shuffle a pmap ' s pixvals
  64.     'nearest'     DIG - specific nearest - color finder
  65. */
  66. {
  67.     struct image_struct image;
  68.     
  69.     if (pmap == NULL || crange == NULL) {
  70.         return;
  71.     }
  72.     /* If no cmap is given, put default colors in crange */ 
  73.     if (cmap == NULL) {
  74.         ocolmap_set(crange, disp_GetDefColMapp());
  75.         return;
  76.     }
  77.     image.maps = &pmap;
  78.     image.nmaps = 1;
  79.     image.cmap = cmap;
  80.  
  81.     /* If all colors are allocated, no need to squeeze */
  82.     if (crange->nentries >= cmap->nentries) {
  83.         if (crange->firstpix == cmap->firstpix) {
  84.             /* Color range in place; just copy it */
  85.             ocolmap_set(crange, cmap);
  86.         }
  87.         else {
  88.             /* Color range can be slid to fit */
  89.             pal_slide(&image, crange);        /* slide color range into place */
  90.             pal_match(&image, crange, pmcswap, nearest); /* match pmap to new colors */
  91.         }
  92.     }
  93.     else {    /* Must squeeze */
  94.         if (crange->nentries >= dohist(&image, pmhist)) {
  95.             /* Can just shuffle by throwing out unused colors */
  96.             pal_slide(&image, crange);        /* slide color range into place */
  97.             pal_match(&image, crange, pmcswap, nearest); /* match pmap to new colors */
  98.         }
  99.         else {
  100.             /* Must really squeeze */
  101.  
  102.             /* Clear out top 2 bits of each rgb level - squeeze funcs handle 6 bit levels */
  103.             dig_shiftcmap(cmap, 2);
  104.  
  105.             pal_pickcols(&image, crange);    /* squeeze colors into smaller range */
  106.             pal_match(&image, crange, pmcswap, nearest); /* match pmap to new colors */
  107.  
  108.             /* Restore levels to 8-bit values */
  109.             dig_shiftcmap(cmap, -2);
  110.             dig_shiftcmap(crange, -2);
  111.         }
  112.     }
  113. }
  114. /* -------------------------------------------------------------------------- */
  115.  
  116. static void DIGPRIV pal_slide(image_type image, ocolmap_type crange)
  117. /*
  118.     slide color range into place
  119.     (sets up image->picktab & crange rgb entries)
  120. */
  121. {
  122.     int iscol, idcol, firstdcol, lastscol;
  123.     boolean doall;
  124.  
  125.     /* If crange has room for even unused colors, take them along for the ride */
  126.     doall = (crange->nentries >= image->cmap->nentries);
  127.  
  128.     iscol = (int) image->cmap->firstpix;
  129.     firstdcol = (int) crange->firstpix;
  130.     idcol = firstdcol;
  131.     lastscol = iscol + image->cmap->nentries - 1;
  132.  
  133.     image->nopickval = (byte) (firstdcol-1);    /* this will not get picked */
  134.     initbtab(image->picktab, image->nopickval);
  135.  
  136.     for ( ; iscol <= lastscol; iscol++) {
  137.         /* If a color is used or if we have room for it, take it */
  138.         if (doall || image->hist[iscol] != 0) {
  139.             ocolmap_getcolor(image->cmap, (opixval)iscol,
  140.                                     crange, (opixval)idcol);
  141.             image->picktab[iscol] = (byte)idcol++;
  142.         }
  143.         else {    /* If color is unused, skip it and mark it as picked by mapping it to first dcol */
  144.             image->picktab[iscol] = (byte)firstdcol;
  145.         }
  146.     }
  147. }
  148. /* -------------------------------------------------------------------------- */
  149.  
  150. static void DIGPRIV pal_pickcols(image_type image, ocolmap_type crange)
  151. /*
  152.     Squeeze colors from image cmap into smaller crange
  153.     (sets up image->picktab & crange rgb entries)
  154. */
  155. {
  156.     int next, last;
  157.  
  158.     /* If crange starts at 0, use nentries as place marker instead of 0 */
  159.     if ((int)crange->firstpix != 0 || crange->nentries == 256) {
  160.         image->nopickval = 0;
  161.     }
  162.     else {
  163.         image->nopickval = (byte)(((int)crange->firstpix) + crange->nentries);
  164.     }
  165.  
  166.     initbtab(image->picktab, image->nopickval);
  167.  
  168.     initpick(image);
  169.  
  170.     next = (int) crange->firstpix;
  171.     last = next + crange->nentries - 1;
  172.  
  173.     for (;;) {
  174.         if (pickcol(image, crange, next)) {
  175.             if (++next > last) {
  176.                 break;
  177.             }
  178.         }
  179.         else {
  180.             break;        /* if no more can be picked, quit */
  181.         }
  182.     }
  183.  
  184.     /* Set leftover colors to black */
  185.     for ( ; next <= last; next++) {
  186.         ocolmap_setpixrgb(crange, (opixval) next, OC_BLACK);
  187.     }
  188. }
  189. /* -------------------------------------------------------------------------- */
  190.  
  191. static void DIGPRIV pal_match(image_type image, ocolmap_type tcmap, pmcswap_fptr pmcswap, pmnearcol_fptr nearest)
  192. /*
  193.     Match image colors to target colormap
  194.     (construct color swap translation table from image to target cmap
  195.     and then do the swap on image pmap(s))
  196. */
  197. {
  198.     int ipix, jpix, ifirst, ilast;
  199.     int ipm;
  200.     int first, last;
  201.     orgb_struct *ifirstentry;
  202.  
  203.     first = (int)tcmap->firstpix;
  204.     last = first + tcmap->nentries - 1;
  205.  
  206.     /* Map any image colors not defined in image cmap to first target color */
  207.     initbtab(image->swaptab, first);
  208.  
  209.     ifirst = (int)image->cmap->firstpix;
  210.     ilast = ifirst + image->cmap->nentries - 1;
  211.     ifirstentry = ocolmap_entry(image->cmap, ifirst);
  212.     for (ipix = ifirst ; ipix <= ilast; ipix++) {
  213.         
  214.         /* First check if we've picked this color */
  215.         if (image->picktab[ipix] != image->nopickval) {
  216.             image->swaptab[ipix] = image->picktab[ipix];
  217.             goto LOOP;
  218.         }
  219.  
  220.         /* Next check if we've already done it */
  221.         for (jpix = ifirst; jpix < ipix; jpix++) {
  222.             if (ocolmap_samecolor(image->cmap, (opixval) ipix,
  223.                                     image->cmap, (opixval) jpix)) {
  224.                 image->swaptab[ipix] = image->swaptab[jpix];
  225.                 goto LOOP;
  226.             }
  227.         }
  228.  
  229.         /* Then check if we're already there */
  230.         if (ipix >= first && ipix <= last) {
  231.             if (ocolmap_samecolor(image->cmap, (opixval)ipix,
  232.                                         tcmap, (opixval)ipix)) {
  233.                 image->swaptab[ipix] = (byte)ipix;
  234.                 goto LOOP;
  235.             }
  236.         }
  237.  
  238.         /* If those didn't work, do the search */
  239.         image->swaptab[ipix] = 
  240.             (byte) (*nearest)(ifirstentry + (ipix-ifirst), tcmap);
  241. LOOP: ;
  242.     }
  243.  
  244.     /* Finally, do the color swap translation on the pmap image buffers */
  245.     for (ipm = 0; ipm < image->nmaps; ipm++) {
  246.         if (image->maps[ipm] != NULL) {
  247.             (*pmcswap)(image->maps[ipm], image->swaptab);
  248.         }
  249.     }
  250. }
  251. /* -------------------------------------------------------------------------- */
  252.  
  253. static void DIGPRIV initpick(image_type image)
  254. {
  255.     int ipix, firstpix, lastpix;
  256. /*
  257.     Note- The image swaptab is used for a different purpose here than in
  258.     pal_match.  Here it is used to speed picking an unpicked color at random
  259.     It is used by the matching algorithm, not the mixing one, so at this
  260.     point it is ok to make alternate use of it.
  261. */
  262.  
  263.     /* Mark out unused colors by marking them as already picked */
  264.     /* (Count down instead of up to avoid side effects of markpick) */
  265.  
  266.     image->nunpicked = 256;
  267.     initcswap(image->swaptab);
  268.  
  269.     firstpix = (int)image->cmap->firstpix;
  270.     lastpix = firstpix + image->cmap->nentries - 1;
  271.  
  272.     for (ipix = 256-1; ipix >= 0; ipix--) {
  273.         if (ipix > lastpix || image->hist[ipix] == 0 || ipix < firstpix) {
  274.             markpick(image, ipix);
  275.         }
  276.     }
  277. }
  278. /* -------------------------------------------------------------------------- */
  279.  
  280. static boolean DIGPRIV pickcol(image_type image, ocolmap_type crange, int next)
  281. {
  282.     byte pick;
  283.     int ipix;
  284.  
  285. LOOP:
  286.     if (image->nunpicked == 0) {
  287.         return FALSE;
  288.     }
  289.  
  290.     /* Get remapped pick value and also mark that choice as picked */
  291.     pick = markpick(image, rand());
  292.     
  293.     /* Check if we've already done it */
  294.     for (ipix = (int)crange->firstpix; ipix < next; ipix++) {
  295.         if (ocolmap_samecolor(crange, (opixval) ipix,
  296.                             image->cmap, (opixval) pick)) {
  297.             goto LOOP;    /* Already had that one; go get another */
  298.         }
  299.     }
  300.     
  301.     /* It's a new color; make an entry for it */
  302.     ocolmap_getcolor(image->cmap, (opixval) pick, crange, (opixval) next);
  303.     image->picktab[pick] = (byte) next;
  304.     return(TRUE);
  305. }
  306. /* -------------------------------------------------------------------------- */
  307.  
  308. static byte DIGPRIV markpick(image_type image, unsigned pick)
  309. /*
  310.     Pick a value, make sure it never gets picked again
  311.     (returns an unpicked value even though 'pick' may have been picked before)
  312. */
  313. {
  314.     byte realpick;
  315.  
  316.     pick %= image->nunpicked;
  317.  
  318.     /* Get out value just picked */
  319.     realpick = image->swaptab[pick];
  320.     image->nunpicked--;
  321.  
  322.     /* Slide remaining unpicked values into space just vacated */
  323.     if (pick < image->nunpicked) {
  324.         memcpy(&image->swaptab[pick],
  325.                 &image->swaptab[pick+1],
  326.                 image->nunpicked - pick);
  327.     }
  328.  
  329.     /* Zero out the space just slid out of */
  330.     image->swaptab[image->nunpicked] = 0;
  331.  
  332.     return(realpick);
  333. }
  334. /* -------------------------------------------------------------------------- */
  335.  
  336. static unsigned DIGPRIV dohist(image_type image, pmhist_fptr pmhist)
  337. {
  338.     int      ipm, icol, lastpix;
  339.     unsigned nused;
  340.  
  341.     inithist(image->hist);
  342.     for (ipm = 0; ipm < image->nmaps; ipm++) {
  343.         if (image->maps[ipm] != NULL) {
  344.             (*pmhist)(image->maps[ipm], image->hist);
  345.         }
  346.     }
  347.     icol = (int)image->cmap->firstpix;
  348.     lastpix = icol + image->cmap->nentries - 1;
  349.  
  350.     nused = 0;
  351.     for ( ; icol <= lastpix; icol++) {
  352.         if (image->hist[icol] != 0) {
  353.             nused++;
  354.         }
  355.     }
  356.     return(nused);
  357. }
  358. /* -------------------------------------------------------------------------- */
  359.  
  360. static void DIGPRIV initcswap(byte *swaptab)
  361. {
  362.     int ipix;
  363.  
  364.     if (swaptab) {
  365.         for (ipix=0; ipix < 256; ipix++) {
  366.             swaptab[ipix] = (byte)ipix;
  367.         }
  368.     }
  369. }
  370. /* -------------------------------------------------------------------------- */
  371.  
  372.