home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 580b.lha / Wasp_v1.23 / src.LZH / src / wriffdistr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  24.1 KB  |  1,226 lines
  1. /* wasp - copyright Steven Reiz 1990, 1991
  2.  * see wasp.c for further info
  3.  * wriffdistr.c, 4/12/90 - 30/1/91, 2/6/91, 23/6/91,
  4.  * 3/7/91 - 10/7/91
  5.  * symbols: SORT_SLICED, SHAM_BLACK
  6.  */
  7.  
  8. struct hs_t {
  9.     char dist;
  10.     char pad;
  11.     short color;
  12. };
  13.  
  14. #include "wasp.h"
  15. #include "wriff.h"
  16. #ifndef NOSH
  17. #include "wriffdistr.sh"
  18. #endif
  19. #define SORT_SLICED
  20. /* #define SHAM_BLACK */
  21.  
  22.  
  23. static char regind;
  24. static long squares[]={
  25.     0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225
  26. };
  27.  
  28.  
  29. #ifdef __STDC__
  30. compute_distr(int firstrow, int lastrow)
  31. #else
  32. compute_distr(firstrow, lastrow)
  33. int firstrow, lastrow;
  34. #endif
  35. {
  36.     assert(counts!=NULL1);
  37.     if (icolors<=nregs)
  38.         no_distr();
  39.     else {
  40.         switch (distrmeth) {
  41.         case DISTRMETH_MOSTUSED:
  42.             mostused_distr();
  43.         break;
  44.         case DISTRMETH_WORSTFIRST:
  45.             worstfirst_distr();
  46.         break;
  47.         case DISTRMETH_EHB:
  48.             ehb_distr();
  49.         break;
  50.         case DISTRMETH_MUE:
  51.             mue_distr();
  52.         break;
  53.         case DISTRMETH_HAMSHARP:
  54.             hamsharp_distr();
  55.         break;
  56.         case DISTRMETH_CONTRACTION:
  57.             contraction_distr();
  58.         break;
  59.         default:
  60.         error0(E0_FATAL, E1_IFF, E2_OPTION, E3_DISTRMETH);
  61.         break;
  62.         }
  63.     }
  64.     if (xmode!=EHB) {
  65. #ifdef SORT_SLICED
  66.         sort_cm();
  67. #else
  68.         if (!slicedo)
  69.             sort_cm();
  70. #endif
  71.     }
  72.     count_pixels(firstrow, lastrow, 1);
  73.     fill_newcol();
  74. }
  75.  
  76.  
  77. #ifdef __STDC__
  78. PRIVATE no_distr(void)
  79. #else
  80. PRIVATE no_distr()
  81. #endif
  82. {
  83.     short i;
  84.     u_long th, *p;
  85.     u_short *q;
  86.  
  87.     p=counts+NRGB;
  88.     th=threshold;
  89.     q=curcm;
  90.     i=NRGB-1;
  91.     if (th<=1) {
  92.         do {
  93.             if (*--p)
  94.                 *q++ =i;
  95.         } while (--i>=0);
  96.     } else {
  97.         do {
  98.             if (*--p >=th)
  99.                 *q++ =i;
  100.         } while (--i>=0);
  101.     }
  102.     assert(q==curcm+icolors);
  103.     while (q<curcm+nregs)
  104.         *q++ =0;
  105. }
  106.  
  107.  
  108. #ifdef __STDC__
  109. PRIVATE mostused_distr(void)
  110. #else
  111. PRIVATE mostused_distr()
  112. #endif
  113. {
  114.     static u_long regcounts[MAXNREGS];
  115.     u_long *countp, *countp2, th;
  116.     static u_long *savecountp;
  117.     u_short *cmp;
  118.     short i;
  119.     
  120.     countp=regcounts;
  121.     i=nregs-1;
  122.     do {
  123.         *countp++ =0;
  124.     } while (--i>=0);
  125.     th=0;
  126.     countp=counts+NRGB;
  127.     i=NRGB-1;
  128.     do {
  129.         if (*--countp>th) {
  130.             th= *countp;
  131.             savecountp=countp;
  132.             countp=regcounts;
  133.             do {
  134.                 /* tight loop! */
  135.             } while (*countp++ >=th);
  136.             countp2=regcounts+nregs;
  137.             cmp=curcm+nregs;
  138.             if (countp2>countp) {
  139.                 do {
  140.                     *--countp2= *(countp2-2);
  141.                     *--cmp    = *(cmp-2);
  142.                 } while (countp2>countp);
  143.             }
  144.             *--countp2=th;
  145.             *--cmp=i;
  146.             th=regcounts[nregs-1];
  147.             countp=savecountp;
  148.         }
  149.     } while (--i>=0);
  150. #ifdef SHAM_BLACK
  151.     if (slicedo) {
  152.         for (i=0; i<nregs; ++i)
  153.             if (curcm[i]==0x000)
  154.                 break;
  155.         if (i>=nregs) { /* black isn't amongst the colors, add it */
  156.             curcm[nregs-1]=0x000;
  157.         }
  158.     }
  159. #endif
  160. }
  161.  
  162.  
  163. #ifdef __STDC__
  164. PRIVATE worstfirst_distr(void)
  165. #else
  166. PRIVATE worstfirst_distr()
  167. #endif
  168. {
  169.     static int sicolors= -1;
  170.     static int startreg;
  171.     int i;
  172.     short rgb1, rgb2;
  173.  
  174.     if (sicolors<icolors) {
  175.     if (sicolors== -1) {
  176.             if (icolors<128)
  177.                 sicolors=128;
  178.             else
  179.                 sicolors=icolors;
  180.         } else {
  181.             free(wfmindist);
  182.             free(wfminind);
  183.             free(wfrgb);
  184.             if (icolors<256)
  185.                 sicolors=256;
  186.             else
  187.                 sicolors=icolors;
  188.         }
  189.         wfmindist=Malloc(sicolors);
  190.         wfminind=Malloc(sicolors);
  191.         wfrgb=Malloc(sicolors*3);
  192.     }
  193.     fill_wf_rgb();
  194.     startreg=2;
  195. #ifdef SHAM_BLACK
  196.     if (slicedo) {
  197.     startreg=1;
  198.     rgb1=0x000; regind=0;
  199.     fill_wf_dist_1(rgb1);
  200.     } else {
  201. #endif
  202.     find_2_furthest(&rgb1, &rgb2);
  203.     curcm[0]=rgb1; regind=0;
  204.     fill_wf_dist_1(rgb1);
  205.     curcm[1]=rgb2; regind=1;
  206.     fill_wf_dist_2(rgb2);
  207. #ifdef SHAM_BLACK
  208.     }
  209. #endif
  210.     for (i=startreg; i<nregs; ++i) {
  211.         find_1_furthest(&rgb1);
  212.         curcm[i]=rgb1; regind=i;
  213.         fill_wf_dist_2(rgb1);
  214.     }
  215.     fill_wf2rgbweight();
  216.     wf2_redo_curcm();
  217. }
  218.  
  219.  
  220. #ifdef __STDC__
  221. PRIVATE fill_wf_rgb(void)
  222. #else
  223. PRIVATE fill_wf_rgb()
  224. #endif
  225. {
  226.     long i;
  227.     u_long th, *p;
  228.     char *q;
  229.  
  230.     p=counts+NRGB;
  231.     th=threshold;
  232.     q=wfrgb;
  233.     i=NRGB-1;
  234.     if (th<=1) {
  235.         do {
  236.             if (*--p) {
  237.                 *q++ =i>>8;
  238.                 *q++ =(i>>4)&0x0f;
  239.                 *q++ =i&0x0f;
  240.             }
  241.         } while (--i>=0);
  242.     } else {
  243.         do {
  244.             if (*--p >=th) {
  245.                 *q++ =i>>8;
  246.                 *q++ =(i>>4)&0x0f;
  247.                 *q++ =i&0x0f;
  248.             }
  249.         } while (--i>=0);
  250.     }
  251.     assert(q==wfrgb+3*icolors);
  252. }
  253.  
  254.  
  255. #ifdef __STDC__
  256. PRIVATE find_2_furthest(short *rgb1p, short *rgb2p)
  257. #else
  258. PRIVATE find_2_furthest(rgb1p, rgb2p)
  259. short *rgb1p, *rgb2p;
  260. #endif
  261. {
  262.     REG char *p, *q;
  263.     REG char r, g, b, t, dist, bigdist;
  264.     NON_REG char *bigp, *bigq;
  265.  
  266.     bigdist=0;
  267.     p=wfrgb+3*icolors;
  268.     while (p>wfrgb) {
  269.         b= *--p;
  270.         g= *--p;
  271.         r= *--p;
  272.         q=wfrgb;
  273.         do {
  274.             if ((dist=r- *q++)<0) dist= -dist;
  275.             if ((t=g- *q++)<0)    dist-=t; else dist+=t;
  276.             if ((t=b- *q++)<0)    dist-=t; else dist+=t;
  277.             if (dist>bigdist) {
  278.                 bigdist=dist;
  279.                 bigp=p;
  280.                 bigq=q;
  281.             }
  282.         } while (q<p);
  283.     }
  284.     *rgb1p=(*bigp<<8)    |(*(bigp+1)<<4)|(*(bigp+2));
  285.     *rgb2p=(*(bigq-3)<<8)|(*(bigq-2)<<4)|(*(bigq-1));
  286. }
  287.  
  288.  
  289. #ifdef __STDC__
  290. PRIVATE fill_wf_dist_1(short color)
  291. #else
  292. PRIVATE fill_wf_dist_1(color)
  293. short color;
  294. #endif
  295. {
  296.     short i;
  297.     char r, g, b, t, dist;
  298.     char *mdp, *mip, *rgbp;
  299.  
  300.     r=color>>8;
  301.     g=(color>>4)&0x0f;
  302.     b=color&0x0f;
  303.     mdp=wfmindist+icolors;
  304.     mip=wfminind+icolors;
  305.     rgbp=wfrgb+3*icolors;
  306.     i=icolors-1;
  307.     do {
  308.         if ((dist=b- *--rgbp)<0) dist= -dist;
  309.         if ((t=g- *--rgbp)<0)    dist-=t; else dist+=t;
  310.         if ((t=r- *--rgbp)<0)    dist-=t; else dist+=t;
  311.         *--mdp=dist;
  312.         *--mip=regind;
  313.     } while (--i>=0);
  314. }
  315.  
  316.  
  317. #ifdef __STDC__
  318. PRIVATE fill_wf_dist_2(short color)
  319. #else
  320. PRIVATE fill_wf_dist_2(color)
  321. short color;
  322. #endif
  323. {
  324.     short i;
  325.     char r, g, b, t, dist;
  326.     char *mdp, *mip, *rgbp;
  327.  
  328.     r=color>>8;
  329.     g=(color>>4)&0x0f;
  330.     b=color&0x0f;
  331.     mdp=wfmindist+icolors;
  332.     mip=wfminind+icolors;
  333.     rgbp=wfrgb+3*icolors;
  334.     i=icolors-1;
  335.     do {
  336.         if ((dist=b- *--rgbp)<0) dist= -dist;
  337.         if ((t=g- *--rgbp)<0)    dist-=t; else dist+=t;
  338.         if ((t=r- *--rgbp)<0)    dist-=t; else dist+=t;
  339.         if (dist< *--mdp) {
  340.             *mdp=dist;
  341.             *--mip=regind;
  342.         } else
  343.             --mip;
  344.     } while (--i>=0);
  345. }
  346.  
  347.  
  348. #ifdef __STDC__
  349. PRIVATE find_1_furthest(short *rgbp)
  350. #else
  351. PRIVATE find_1_furthest(rgbp)
  352. short *rgbp;
  353. #endif
  354. {
  355.     char *p, max;
  356.     short i, maxi;
  357.  
  358.     p=wfmindist+icolors;
  359.     max=0;
  360.     i=icolors-1;
  361.     do {
  362.         if (*--p>max) {
  363.             max= *p;
  364.             maxi=i;
  365.         }
  366.     } while (--i>=0);
  367.     p=wfrgb+3*maxi;
  368.     *rgbp=(*p<<8)|(*(p+1)<<4)|(*(p+2));
  369. }
  370.  
  371.  
  372. #ifdef __STDC__
  373. PRIVATE fill_wf2rgbweight(void)
  374. #else
  375. PRIVATE fill_wf2rgbweight()
  376. #endif
  377. {
  378.     char *rgbp, *mip;
  379.     u_long *weightp, weight;
  380.     short i;
  381.     char r, g, b;
  382.  
  383.     if (wf2rgbweight==NULL1)
  384.         wf2rgbweight=Malloc(nregs*4*sizeof(u_long));
  385.     weightp=wf2rgbweight;
  386.     i=nregs-1;
  387.     do {
  388.         *weightp++ =0;
  389.         *weightp++ =0;
  390.         *weightp++ =0;
  391.         *weightp++ =0;
  392.     } while (--i>=0);
  393.     rgbp=wfrgb;
  394.     mip=wfminind;
  395.     i=icolors-1;
  396.     do {
  397.         r= *rgbp++;
  398.         g= *rgbp++;
  399.         b= *rgbp++;
  400.         weight=counts[(r<<8)|(g<<4)|b];
  401.         weightp=wf2rgbweight+4* (*mip++);
  402.         *weightp++ += r*weight;
  403.         *weightp++ += g*weight;
  404.         *weightp++ += b*weight;
  405.         *weightp   += weight;
  406.     } while (--i>=0);
  407. }
  408.  
  409.  
  410. #ifdef __STDC__
  411. PRIVATE wf2_redo_curcm(void)
  412. #else
  413. PRIVATE wf2_redo_curcm()
  414. #endif
  415. {
  416.     u_long *weightp, weight, r, g, b;
  417.     short i;
  418.     u_short *cmp;
  419.     
  420.     weightp=wf2rgbweight;
  421.     cmp=curcm;
  422.     i=nregs-1;
  423.     do {
  424.         r= *weightp++;
  425.         g= *weightp++;
  426.         b= *weightp++;
  427.         weight= *weightp++;
  428.         if (!weight)
  429.             weight=1;
  430.         r=(r+weight/2)/weight;
  431.         if (r>15) r=15;
  432.         g=(g+weight/2)/weight;
  433.         if (g>15) g=15;
  434.         b=(b+weight/2)/weight;
  435.         if (b>15) b=15;
  436.         *cmp++ =(r<<8)|(g<<4)|b;
  437.     } while (--i>=0);
  438. #ifdef SHAM_BLACK
  439.     if (slicedo)
  440.     black_darkest();
  441. #endif
  442. }
  443.  
  444.  
  445. #ifdef __STDC__
  446. PRIVATE black_darkest(void)
  447. #else
  448. PRIVATE black_darkest()
  449. #endif
  450. {
  451.     short i, besti, val, bestval;
  452.  
  453.     bestval=100;
  454.     for (i=0; i<nregs; ++i) {
  455.         val=(curcm[i]&0xf)+((curcm[i]>>4)&0xf)+(curcm[i]>>8);
  456.         if (val<bestval) {
  457.             bestval=val;
  458.             besti=i;
  459.         }
  460.     }
  461.     curcm[besti]=0x000;
  462. }
  463.  
  464.  
  465. #ifdef __STDC__
  466. PRIVATE ehb_distr(void)
  467. #else
  468. PRIVATE ehb_distr()
  469. #endif
  470. {
  471.     static int sicolors= -1;
  472.     int i, nr;
  473.     short rgb1, rgb2;
  474.  
  475.     nr=nregs/2;
  476.     if (sicolors<icolors) {
  477.         if (sicolors== -1) {
  478.             if (icolors<128)
  479.                 sicolors=128;
  480.             else
  481.                 sicolors=icolors;
  482.         } else {
  483.             free(wfmindist);
  484.             free(wfminind);
  485.             free(wfrgb);
  486.             if (icolors<256)
  487.                 sicolors=256;
  488.             else
  489.                 sicolors=icolors;
  490.         }
  491.         wfmindist=Malloc(sicolors);
  492.         wfminind=Malloc(sicolors);
  493.         wfrgb=Malloc(sicolors*3);
  494.     }
  495.     fill_wf_rgb();
  496.     find_2_furthest(&rgb1, &rgb2);
  497.     regind=0;
  498.     fill_wf_dist_1(rgb1);
  499.     ehb_pair(rgb1, 0);
  500.     for (i=1; i<nr; ++i) {
  501.         find_1_furthest(&rgb1);
  502.         regind=i;
  503.         fill_wf_dist_2(rgb1);
  504.         ehb_pair(rgb1, i);
  505.     }
  506.     fill_wf2rgbweight();
  507.     ehb_redo_curcm();
  508. }
  509.  
  510.  
  511. #ifdef __STDC__
  512. PRIVATE ehb_pair(short c1, int i)
  513. #else
  514. PRIVATE ehb_pair(c1, i)
  515. short c1;
  516. int i;
  517. #endif
  518. {
  519.     short c2, c3, c4;
  520.     short r, g, b;
  521.     int nr;
  522.  
  523.     nr=nregs/2;
  524.     r=c1>>8;
  525.     g=(c1>>4)&0x0f;
  526.     b=c1&0x0f;
  527.     c2=((r>>1)<<8)|((g>>1)<<4)|(b>>1);
  528.     if (r<8 && g<8 && b<8) {
  529.         c3=(r<<9)|(g<<5)|(b<<1);
  530.         ehb_worst(c2, c3, &c4);
  531.         if (c4==c2) {
  532.             curcm[i]=c1;
  533.             curcm[nr+i]=c2;
  534.             regind=nr+i;
  535.         } else {
  536.             curcm[i]=c4;
  537.             curcm[nr+i]=c1;
  538.             c2=c4;
  539.             ehb_minind_adjust((int)i, (int)(nr+i));
  540.             regind=i;
  541.         }
  542.     } else {
  543.         curcm[i]=c1;
  544.         curcm[nr+i]=c2;
  545.         regind=nr+i;
  546.     }
  547.     fill_wf_dist_2(c2);
  548. }
  549.  
  550.  
  551. #ifdef __STDC__
  552. PRIVATE ehb_worst(short col1, short col8, short *worstp)
  553. #else
  554. PRIVATE ehb_worst(col1, col8, worstp)
  555. short col1, col8;
  556. short *worstp;
  557. #endif
  558. {
  559.     short curcol;
  560.     int curdist, bestdist;
  561.     short i;
  562.  
  563.     bestdist=ehb_farcol(col1);
  564.     *worstp=col1;
  565.     i=7;
  566.     do {
  567.         curcol=col8;
  568.         if (i&1)
  569.             curcol|=0x001;
  570.         if (i&2)
  571.             curcol|=0x010;
  572.         if (i&4)
  573.             curcol|=0x100;
  574.         curdist=ehb_farcol(curcol);
  575.         if (curdist>bestdist) {
  576.             bestdist=curdist;
  577.             *worstp=curcol;
  578.         }
  579.     } while (--i>=0);
  580. }
  581.  
  582.  
  583. #ifdef __STDC__
  584. PRIVATE int ehb_farcol(short color)
  585. #else
  586. PRIVATE int ehb_farcol(color)
  587. short color;
  588. #endif
  589. {
  590.     char r, g, b;
  591.     char *p, *q;
  592.     char t, dist, bigdist;
  593.     short i;
  594.  
  595.     r=color>>8;
  596.     g=(color>>4)&0x0f;
  597.     b=color&0x0f;
  598.     bigdist=0;
  599.     i=icolors-1;
  600.     p=wfmindist;
  601.     q=wfrgb;
  602.     do {
  603.         if ((dist=r- *q++)>0) dist= -dist;
  604.         if ((t=g- *q++)>0)    dist-=t; else dist+=t;
  605.         if ((t=b- *q++)>0)    dist-=t; else dist+=t;
  606.         dist+= *p++;
  607.         if (dist>bigdist)
  608.             bigdist=dist;
  609.     } while (--i>=0);
  610.     return (int)bigdist;
  611. }
  612.  
  613.  
  614. #ifdef __STDC__
  615. PRIVATE ehb_minind_adjust(int from, int to)
  616. #else
  617. PRIVATE ehb_minind_adjust(from, to)
  618. int from, to;
  619. #endif
  620. {
  621.     char *p;
  622.     char fromc, toc;
  623.     short i;
  624.  
  625.     p=wfminind+icolors;
  626.     i=icolors-1;
  627.     fromc=from;
  628.     toc=to;
  629.     do {
  630.         if (*--p ==fromc)
  631.             *p=toc;
  632.     } while (--i>=0);
  633. }
  634.  
  635.  
  636. #ifdef __STDC__
  637. PRIVATE ehb_redo_curcm(void)
  638. #else
  639. PRIVATE ehb_redo_curcm()
  640. #endif
  641. {
  642.     short nr, i;
  643.     long r1, g1, b1, w1, r2, g2, b2, w2;
  644.     u_long *p1, *p2;
  645.  
  646.     nr=nregs/2;
  647.     p1=wf2rgbweight;
  648.     p2=wf2rgbweight+4*nr;
  649.     for (i=0; i<nr; ++i) {
  650.         r1= *p1++;     g1= *p1++;     b1= *p1++;     w1= *p1++;
  651.         r2=(*p2++)<<1; g2=(*p2++)<<1; b2=(*p2++)<<1; w2= *p2++;
  652.         w1=w1+w2;
  653.         assert(w1);
  654.         w2=w1/2;
  655.         r1=(r1+r2+w2)/w1;
  656.         if (r1>15) r1=15;
  657.         g1=(g1+g2+w2)/w1;
  658.         if (g1>15) g1=15;
  659.         b1=(b1+b2+w2)/w1;
  660.         if (b1>15) b1=15;
  661.         curcm[i]=(r1<<8)|(g1<<4)|b1;
  662.         r1>>=1; g1>>=1; b1>>=1;
  663.         curcm[nr+i]=(r1<<8)|(g1<<4)|b1;
  664.     }
  665. }
  666.  
  667.  
  668. #ifdef __STDC__
  669. PRIVATE mue_distr(void)
  670. #else
  671. PRIVATE mue_distr()
  672. #endif
  673. {
  674.     static u_long regcounts[MAXNREGS];
  675.     u_long *countp, *countp2, th;
  676.     static u_long *savecountp;
  677.     u_short *cmp;
  678.     short i, nr;
  679.     
  680.     nr=nregs/2;
  681.     countp=regcounts;
  682.     i=nr-1;
  683.     do {
  684.         *countp++ =0;
  685.     } while (--i>=0);
  686.     th=0;
  687.     countp=counts+NRGB;
  688.     i=NRGB-1;
  689.     do {
  690.         if (*--countp>th) {
  691.             th= *countp;
  692.             savecountp=countp;
  693.             countp=regcounts;
  694.             do {
  695.                 /* tight loop! */
  696.             } while (*countp++ >=th);
  697.             countp2=regcounts+nr;
  698.             cmp=curcm+nr;
  699.             if (countp2>countp) {
  700.                 do {
  701.                     *--countp2= *(countp2-2);
  702.                     *--cmp    = *(cmp-2);
  703.                 } while (countp2>countp);
  704.             }
  705.             *--countp2=th;
  706.             *--cmp=i;
  707.             th=regcounts[nr-1];
  708.             countp=savecountp;
  709.         }
  710.     } while (--i>=0);
  711.     mue_extend();
  712. }
  713.  
  714.  
  715. #ifdef __STDC__
  716. PRIVATE mue_extend(void)
  717. #else
  718. PRIVATE mue_extend()
  719. #endif
  720. {
  721.     short i;
  722.     short r, g, b, color;
  723.     u_short *p, *q;
  724.  
  725.     i=nregs/2;
  726.     p=curcm;
  727.     q=p+i;
  728.     --i;
  729.     do {
  730.         color= *p++;
  731.         r=color>>9;
  732.         g=(color>>5)&0x07;
  733.         b=(color>>1)&0x07;
  734.         *q++ = (r<<8)|(g<<4)|b;
  735.     } while (--i>=0);
  736. }
  737.  
  738.  
  739. #ifdef __STDC__
  740. PRIVATE hamsharp_distr(void)
  741. #else
  742. PRIVATE hamsharp_distr()
  743. #endif
  744. {
  745.     static int sicolors= -1;
  746.     int i;
  747.  
  748.     if (sicolors<icolors) {
  749.         if (sicolors!= -1) {
  750.             for (i=0; i<sicolors; ++i)
  751.                 free(hshead[i]);
  752.             free(hshead);
  753.             free(hsmark);
  754.             free(wfminind);
  755.             free(wfrgb);
  756.         }
  757.         sicolors=icolors;
  758.         wfrgb=Malloc(sicolors*3);
  759.         wfminind=Malloc(sicolors);
  760.         hsmark=Malloc(sicolors);
  761.         hshead=Malloc(sicolors*sizeof(void *));
  762.         for (i=0; i<sicolors; ++i)
  763.             hshead[i]=Malloc(sicolors*sizeof(struct hs_t));
  764.     }
  765.     fill_wf_rgb();
  766.     fill_hsmark();
  767.     fill_hshead();
  768.     fill_hs_cm();
  769.     fill_wf2rgbweight();
  770.     wf2_redo_curcm();
  771. }
  772.  
  773.  
  774. #ifdef __STDC__
  775. PRIVATE fill_hsmark(void)
  776. #else
  777. PRIVATE fill_hsmark()
  778. #endif
  779. {
  780.     short i;
  781.     char *q;
  782.  
  783.     q=hsmark;
  784.     i=icolors-1;
  785.     do {
  786.         *q++ =1;
  787.     } while (--i>=0);
  788. }
  789.  
  790.  
  791. #ifdef __STDC__
  792. PRIVATE int cmphs(struct hs_t *p1, struct hs_t *p2)
  793. #else
  794. PRIVATE int cmphs(p1, p2)
  795. struct hs_t *p1, *p2;
  796. #endif
  797. {
  798.     return p1->dist - p2->dist;
  799. }
  800.  
  801.  
  802. #ifdef __STDC__
  803. PRIVATE fill_hshead(void)
  804. #else
  805. PRIVATE fill_hshead()
  806. #endif
  807. {
  808.     REG char *p, *q;
  809.     REG struct hs_t *hp;
  810.     NON_REG int ic;
  811.     REG short i;
  812.     REG char r, g, b, t, dist;
  813.  
  814.     p=wfrgb+3*icolors;
  815.     ic=icolors;
  816.     while (p>wfrgb) {
  817.         b= *--p;
  818.         g= *--p;
  819.         r= *--p;
  820.         q=wfrgb+3*icolors;
  821.         hp=hshead[--ic];
  822.         i=icolors-1;
  823.         do {
  824.             if ((dist=b- *--q)<0) dist= -dist;
  825.             if ((t=g- *--q)<0)    dist-=t; else dist+=t;
  826.             if ((t=r- *--q)<0)    dist-=t; else dist+=t;
  827.             hp->dist=dist;
  828.             hp->color=i;
  829.             ++hp;
  830.         } while (--i>=0);
  831.         qsort((char *)hshead[ic], (int)icolors, sizeof(struct hs_t), cmphs);
  832.     }
  833. }
  834.  
  835.  
  836. #ifdef __STDC__
  837. PRIVATE fill_hs_cm(void)
  838. #else
  839. PRIVATE fill_hs_cm()
  840. #endif
  841. {
  842.     NON_REG short j;
  843.     REG short i, k, bestk, colperreg;
  844.     REG long dist, bestdist;
  845.     REG struct hs_t *p;
  846.     REG char *q, *r;
  847.  
  848.     colperreg=icolors/nregs;
  849.     q=hsmark;
  850.     for (j=0; j<nregs; ++j) {
  851.         if (j==nregs-1)
  852.             colperreg+=icolors-nregs*colperreg;
  853.         bestdist=1000000000L;
  854.         for (k=0; k<icolors; ++k) {
  855.             dist=0;
  856.             p=hshead[k];
  857.             i=colperreg-1;
  858.             do {
  859.                 while (!q[p->color])
  860.                     ++p;
  861.                 dist+=p->dist;
  862.                 ++p;
  863.             } while (--i>=0);
  864.             if (dist<bestdist) {
  865.                 bestdist=dist;
  866.                 bestk=k;
  867.             }
  868.         }
  869.         p=hshead[bestk];
  870.         i=colperreg-1;
  871.         do {
  872.             while (!q[p->color])
  873.                 ++p;
  874.             q[p->color]=0;
  875.             wfminind[p->color]=j;
  876.             ++p;
  877.         } while (--i>=0);
  878.         r=wfrgb+3*bestk;
  879.         curcm[j]=(*r<<8)|(*(r+1)<<4)|*(r+2);
  880.     }
  881. }
  882.  
  883.  
  884. #define CONTRACT2
  885. #ifdef __STDC__
  886. PRIVATE contraction_distr(void)
  887. #else
  888. PRIVATE contraction_distr()
  889. #endif
  890. {
  891.     static int sicolors= -1;
  892.     int i;
  893.  
  894.     if (sicolors!= -1) {
  895.         for (i=0; i<sicolors; ++i)
  896.             if (cthead[i])
  897.                 free(cthead[i]);
  898.         free(cthead);
  899.         free(ctrgbw);
  900.     }
  901.     sicolors=icolors;
  902.     ctrgbw=Malloc(sicolors*4*sizeof(float));
  903.     cthead=Malloc(sicolors*sizeof(void *));
  904.     cthead[0]=NULL;
  905.     for (i=1; i<sicolors; ++i)
  906.         cthead[i]=Malloc(i*sizeof(float));
  907.     fill_ctrgbw();
  908.     fill_cthead();
  909.     do_contraction();
  910.     fill_ct_cm();
  911. }
  912.  
  913.  
  914. #ifdef __STDC__
  915. PRIVATE fill_ctrgbw(void)
  916. #else
  917. PRIVATE fill_ctrgbw()
  918. #endif
  919. {
  920.     short i;
  921.     u_long th, *p;
  922.     float *q;
  923.  
  924.     p=counts+NRGB;
  925.     th=threshold;
  926.     q=ctrgbw;
  927.     i=NRGB-1;
  928.     do {
  929.         if (*--p >=th) {
  930.             *q++ =(float)(i>>8);
  931.             *q++ =(float)((i>>4)&0x0f);
  932.             *q++ =(float)(i&0x0f);
  933.             *q++ =(float)*p;
  934.         }
  935.     } while (--i>=0);
  936.     assert(q==ctrgbw+4*icolors);
  937. }
  938.  
  939.  
  940. #ifdef __STDC__
  941. PRIVATE fill_cthead(void)
  942. #else
  943. PRIVATE fill_cthead()
  944. #endif
  945. {
  946.     short i, j;
  947.     float *p, *q;
  948.     float r, g, b, dist, t;
  949.  
  950.     for (i=1; i<icolors; ++i) {
  951.         p=cthead[i];
  952.         q=ctrgbw+4*i;
  953.         r= *q++;
  954.         g= *q++;
  955.         b= *q;
  956.         q=ctrgbw;
  957. #ifdef CONTRACT2
  958.         for (j=0; j<i; ++j) {
  959.             t=r- *q++; dist=t*t;
  960.             t=g- *q++; dist+=t*t;
  961.             t=b- *q++; dist+=t*t;
  962.             ++q;
  963.             *p++ =dist;
  964.         }
  965. #else
  966.         for (j=0; j<i; ++j) {
  967.             if ((dist=r- *q++)<0) dist= -dist;
  968.             if ((t=g- *q++)<0)    dist-=t; else dist+=t;
  969.             if ((t=b- *q++)<0)    dist-=t; else dist+=t;
  970.             ++q;
  971.             *p++ =dist;
  972.         }
  973. #endif
  974.     }
  975. }
  976.  
  977.  
  978. #ifdef __STDC__
  979. PRIVATE do_contraction(void)
  980. #else
  981. PRIVATE do_contraction()
  982. #endif
  983. {
  984.     short ncolors, i, j, besti, bestj;
  985.     float *p, *q, bestdist;
  986.     float newr, newg, newb, neww, wi, wj;
  987.     float t, dist;
  988.  
  989.     ncolors=icolors;
  990.     while (ncolors>nregs) {
  991.         /* find minimum pair */
  992.         bestdist=2000.0;
  993.         for (i=0; i<icolors; ++i) {
  994.             p=cthead[i];
  995.             if (!p)
  996.                 continue;
  997.             j=0;
  998.             do {
  999.                 if (*p++ <bestdist) {
  1000.                     besti=i;
  1001.                     bestj=j;
  1002.                     bestdist= *(p-1);
  1003.                 }
  1004.             } while (++j<i);
  1005.         }
  1006.         /* contract pair to new pair */
  1007.         p=ctrgbw+4*besti;
  1008.         q=ctrgbw+4*bestj;
  1009.         wi=p[3];
  1010.         wj=q[3];
  1011.         neww=wi+wj;
  1012.         newr=(wi*p[0]+wj*q[0])/neww;
  1013.         newg=(wi*p[1]+wj*q[1])/neww;
  1014.         newb=(wi*p[2]+wj*q[2])/neww;
  1015.         /* delete 1 of pair */
  1016.         if (bestj>besti) {
  1017.             i=besti;
  1018.             besti=bestj;
  1019.             bestj=i;
  1020.         }
  1021.         free(cthead[besti]);
  1022.         cthead[besti]=NULL;
  1023.         ctrgbw[4*besti+3]= -1.0;
  1024.         for (i=besti+1; i<icolors; ++i) {
  1025.             p=cthead[i];
  1026.             if (p)
  1027.                 p[besti]=1000.0;
  1028.         }
  1029.         /* replace other of pair by new contracted color */
  1030.         p=ctrgbw+4*bestj;
  1031.         *p++ =newr;
  1032.         *p++ =newg;
  1033.         *p++ =newb;
  1034.         *p   =neww;
  1035.         for (i=bestj+1, q=ctrgbw+4*i; i<icolors; ++i) {
  1036.             p=cthead[i];
  1037.             if (p) {
  1038. #ifdef CONTRACT2
  1039.                 t=newr- *q++; dist=t*t;
  1040.                 t=newg- *q++; dist+=t*t;
  1041.                 t=newb- *q++; dist+=t*t;
  1042. #else
  1043.                 if ((dist=newr- *q++)<0) dist= -dist;
  1044.                 if ((t=newg- *q++)<0)    dist-=t; else dist+=t;
  1045.                 if ((t=newb- *q++)<0)    dist-=t; else dist+=t;
  1046. #endif
  1047.                 ++q;
  1048.                 p[bestj]=dist;
  1049.             } else {
  1050.                 q+=4;
  1051.             }
  1052.         }
  1053.         for (i=0, p=cthead[bestj]; i<bestj; ++i) {
  1054.             q=ctrgbw+4*i;
  1055.             if (q[3]< -0.5) {
  1056.                 *p++ =1000.0;
  1057.             } else {
  1058. #ifdef CONTRACT2
  1059.                 t=newr- *q++; dist=t*t;
  1060.                 t=newg- *q++; dist+=t*t;
  1061.                 t=newb- *q;   dist+=t*t;
  1062. #else
  1063.                 if ((dist=newr- *q++)<0) dist= -dist;
  1064.                 if ((t=newg- *q++)<0)    dist-=t; else dist+=t;
  1065.                 if ((t=newb- *q)<0)      dist-=t; else dist+=t;
  1066. #endif
  1067.                 *p++ =dist;
  1068.             }
  1069.         }
  1070.         /* decrease number of colors */
  1071.         --ncolors;
  1072.     }
  1073. }
  1074.  
  1075.  
  1076. #ifdef __STDC__
  1077. PRIVATE fill_ct_cm(void)
  1078. #else
  1079. PRIVATE fill_ct_cm()
  1080. #endif
  1081. {
  1082.     float *p;
  1083.     u_short *q, color;
  1084.     short i;
  1085.  
  1086.     p=ctrgbw;
  1087.     q=curcm;
  1088.     i=icolors-1;
  1089.     do {
  1090.         if (p[3]< -0.5) {
  1091.             p+=4;
  1092.         } else {
  1093.             color =((int)(*p++ + 0.5)<<8)&0xf00;
  1094.             color|=((int)(*p++ + 0.5)<<4)&0x0f0;
  1095.             color|=((int)(*p++ + 0.5))   &0x00f;
  1096.             ++p;
  1097.             *q++ =color;
  1098.         }
  1099.     } while (--i>=0);
  1100.     assert(q==curcm+nregs);
  1101. #ifdef SHAM_BLACK
  1102.     if (slicedo)
  1103.     black_darkest();
  1104. #endif
  1105. }
  1106.  
  1107.  
  1108. #ifdef __STDC__
  1109. PRIVATE fill_cmrgb(void)
  1110. #else
  1111. PRIVATE fill_cmrgb()
  1112. #endif
  1113. {
  1114.     short i, color;
  1115.     u_short *p;
  1116.     char *q;
  1117.  
  1118.     if (cmrgb==NULL1)
  1119.     cmrgb=Malloc(3*nregs);
  1120.     p=curcm;
  1121.     q=cmrgb;
  1122.     i=nregs-1;
  1123.     do {
  1124.         color= *p++;
  1125.         *q++ = color>>8;
  1126.         *q++ = (color>>4)&0x0f;
  1127.         *q++ = color&0x0f;
  1128.     } while (--i>=0);
  1129. }
  1130.  
  1131.  
  1132. #ifdef __STDC__
  1133. fill_newcol(void)
  1134. #else
  1135. fill_newcol()
  1136. #endif
  1137. {
  1138.     short i, mini;
  1139.     char r, g, b, min, dist, t;
  1140.     NON_REG short savei;
  1141.     u_long *countp;
  1142.     char *rgbp;
  1143.  
  1144.     fill_cmrgb();
  1145.     if (newcol==NULL1) {
  1146.     newcol=Malloc(NRGB);
  1147.     error=Malloc(NRGB);
  1148.     error2=Malloc(NRGB*sizeof(u_long));
  1149.     }
  1150.     i=NRGB-1;
  1151.     countp=counts+NRGB;
  1152.     do {
  1153.         if (*--countp) {
  1154.             savei=i;
  1155.             r=i>>8;
  1156.             g=(i>>4)&0x0f;
  1157.             b=i&0x0f;
  1158.             min=100;
  1159.             rgbp=cmrgb+3*nregs;
  1160.             i=nregs-1;
  1161.             do {
  1162.                 if ((dist=b- *--rgbp)<0) dist= -dist;
  1163.                 if ((t=g- *--rgbp)<0)    dist-=t; else dist+=t;
  1164.                 if ((t=r- *--rgbp)<0)    dist-=t; else dist+=t;
  1165.                 if (dist<min) {
  1166.                     min=dist;
  1167.                     mini=i;
  1168.                 }
  1169.             } while (--i>=0);
  1170.             i=savei;
  1171.             newcol[i]=mini;
  1172.             error[i]=min;
  1173.         rgbp=cmrgb+3*mini;
  1174.         if ((t=r- *rgbp++)<0) t= -t; error2[i]=squares[t];
  1175.         if ((t=g- *rgbp++)<0) t= -t; error2[i]+=squares[t];
  1176.         if ((t=b- *rgbp  )<0) t= -t; error2[i]+=squares[t];
  1177.         }
  1178.     } while (--i>=0);
  1179. }
  1180.  
  1181.  
  1182. #ifdef __STDC__
  1183. fill_newcol_count(void)
  1184. #else
  1185. fill_newcol_count()
  1186. #endif
  1187. {
  1188.     short i, mini;
  1189.     char r, g, b, min, dist, t;
  1190.     NON_REG short savei;
  1191.     u_long *countp;
  1192.     char *rgbp;
  1193.  
  1194.     fill_cmrgb();
  1195.     if (newcol==NULL1) {
  1196.     newcol=Malloc(NRGB);
  1197.     error=Malloc(NRGB);
  1198.     error2=Malloc(NRGB*sizeof(u_long));
  1199.     }
  1200.     i=NRGB-1;
  1201.     countp=counts+NRGB;
  1202.     do {
  1203.         if (*--countp) {
  1204.             savei=i;
  1205.             r=i>>8;
  1206.             g=(i>>4)&0x0f;
  1207.             b=i&0x0f;
  1208.             min=100;
  1209.             rgbp=cmrgb+3*nregs;
  1210.             i=nregs-1;
  1211.             do {
  1212.                 if ((dist=b- *--rgbp)<0) dist= -dist;
  1213.                 if ((t=g- *--rgbp)<0)    dist-=t; else dist+=t;
  1214.                 if ((t=r- *--rgbp)<0)    dist-=t; else dist+=t;
  1215.                 if (dist<min) {
  1216.                     min=dist;
  1217.                     mini=i;
  1218.                 }
  1219.             } while (--i>=0);
  1220.             i=savei;
  1221.             newcol[i]=mini;
  1222.             error[i]=min;
  1223.         }
  1224.     } while (--i>=0);
  1225. }
  1226.