home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / gbmsrc.zip / gbmmcut.c < prev    next >
C/C++ Source or Header  |  1996-04-14  |  8KB  |  402 lines
  1. /*
  2.  
  3. gbmmcut.c - Median Cut colour reductions
  4.  
  5. */
  6.  
  7. /*...sincludes:0:*/
  8. #include <stdio.h>
  9. #include <stddef.h>
  10. #include <stdlib.h>
  11. #include <string.h>
  12. #include <memory.h>
  13. #include "gbm.h"
  14.  
  15. /*...vgbm\46\h:0:*/
  16. /*...e*/
  17.  
  18. #define    DIV_R 4
  19. #define    DIV_G 2
  20. #define    DIV_B 1
  21.  
  22. typedef struct
  23.     {
  24.     dword freq;
  25.     byte r0,r1,g0,g1,b0,b1;
  26.     byte dividable;
  27.     } CELL;
  28.  
  29. typedef struct
  30.     {
  31.     dword freqs[0x20][0x20][0x20]; /* 128Kb */
  32.     dword total;
  33.     int n_cells;
  34.     CELL cells[0x100];
  35.     } GBMMCUT;
  36.  
  37. /*...sgbm_create_mcut \45\ create empty mcut:0:*/
  38. GBMMCUT *gbm_create_mcut(void)
  39.     {
  40.     GBMMCUT *mcut;
  41.  
  42.     if ( (mcut = malloc((size_t) sizeof(GBMMCUT))) == NULL )
  43.         return NULL;
  44.  
  45.     memset(mcut->freqs, 0x00, sizeof(mcut->freqs));
  46.     mcut->total = 0;
  47.     return mcut;
  48.     }
  49. /*...e*/
  50. /*...sgbm_delete_mcut \45\ delete mcut:0:*/
  51. void gbm_delete_mcut(GBMMCUT *mcut)
  52.     {
  53.     free(mcut);
  54.     }
  55. /*...e*/
  56. /*...sgbm_add_to_mcut \45\ add statistics from file data:0:*/
  57. void gbm_add_to_mcut(
  58.     GBMMCUT *mcut,    
  59.     const GBM *gbm, const byte *data24
  60.     )
  61.     {
  62.     int stride24 = ((gbm->w * 3 + 3) & ~3);
  63.     int step24   = stride24 - gbm->w * 3;
  64.     int x, y;
  65.  
  66.     for ( y = 0; y < gbm->h; y++, data24 += step24 )
  67.         for ( x = 0; x < gbm->w; x++ )
  68.             {
  69.             byte b = (byte) (*data24++ >> 3);
  70.             byte g = (byte) (*data24++ >> 3);
  71.             byte r = (byte) (*data24++ >> 3);
  72.  
  73.             ( mcut->freqs[b][g][r] )++;
  74.             }
  75.     mcut->total += ( gbm->w * gbm->h );
  76.     }
  77. /*...e*/
  78. /*...sgbm_pal_mcut    \45\ build median palette via median cut:0:*/
  79. /*...sshrink:0:*/
  80. /* Apologies for use of 'goto'
  81.    In this case, its considered appropriate. */
  82.  
  83. static void shrink(GBMMCUT *mcut, CELL *c)
  84.     {
  85.     byte r, g, b;
  86.     
  87.     for ( ;; c->r0++ )
  88.         for ( g = c->g0; g < c->g1; g++ )
  89.             for ( b = c->b0; b < c->b1; b++ )
  90.                 if ( mcut->freqs[b][g][c->r0] )
  91.                     goto quit_r0;
  92. quit_r0:
  93.  
  94.     for ( ; c->r1-c->r0 > 1; c->r1-- )
  95.         for ( g = c->g0; g < c->g1; g++ )
  96.             for ( b = c->b0; b < c->b1; b++ )
  97.                 if ( mcut->freqs[b][g][c->r1-1] )
  98.                     goto quit_r1;
  99. quit_r1:
  100.     
  101.     for ( ;; c->g0++ )
  102.         for ( r = c->r0; r < c->r1; r++ )
  103.             for ( b = c->b0; b < c->b1; b++ )
  104.                 if ( mcut->freqs[b][c->g0][r] )
  105.                     goto quit_g0;
  106. quit_g0:
  107.  
  108.     for ( ; c->g1-c->g0 > 1; c->g1-- )
  109.         for ( r = c->r0; r < c->r1; r++ )
  110.             for ( b = c->b0; b < c->b1; b++ )
  111.                 if ( mcut->freqs[b][c->g1-1][r] )
  112.                     goto quit_g1;
  113. quit_g1:
  114.     
  115.     for ( ;; c->b0++ )
  116.         for ( r = c->r0; r < c->r1; r++ )
  117.             for ( g = c->g0; g < c->g1; g++ )
  118.                 if ( mcut->freqs[c->b0][g][r] )
  119.                     goto quit_b0;
  120. quit_b0:
  121.  
  122.     for ( ; c->b1-c->b0 > 1; c->b1-- )
  123.         for ( r = c->r0; r < c->r1; r++ )
  124.             for ( g = c->g0; g < c->g1; g++ )
  125.                 if ( mcut->freqs[c->b1-1][g][r] )
  126.                     goto quit_b1;
  127. quit_b1:
  128.  
  129.     c->dividable = ( ( c->r1-c->r0 > 1 ) ? DIV_R : 0 ) +
  130.                ( ( c->g1-c->g0 > 1 ) ? DIV_G : 0 ) +
  131.                ( ( c->b1-c->b0 > 1 ) ? DIV_B : 0 ) ;
  132.     }
  133. /*...e*/
  134.  
  135. void gbm_pal_mcut(
  136.     GBMMCUT *mcut,
  137.     GBMRGB gbmrgb[],
  138.     int n_cols_wanted
  139.     )
  140.     {
  141.     CELL *c = mcut->cells;
  142.     int i, j;
  143.     byte reorder[0x100];
  144.  
  145.     if ( n_cols_wanted > 0x100 )
  146.         n_cols_wanted = 0x100;
  147.  
  148.     /* Initially, a single cell covers the whole colour cube */
  149.  
  150.     c->r0 = c->g0 = c->b0 =    0;
  151.     c->r1 = c->g1 = c->b1 = 0x20;
  152.     c->freq = mcut->total;
  153.     shrink(mcut, c);
  154.     mcut->n_cells = 1;
  155.  
  156.     /* Do the following until got as many colours (cells) as reqd. */
  157.  
  158.     while ( mcut->n_cells < n_cols_wanted )
  159.         {
  160.         CELL *cmax = NULL;
  161.  
  162. /*...sfind cell with most pixels in it\44\ that can be divided:16:*/
  163. {
  164. int j;
  165. dword freqmax = 1;
  166.  
  167. for ( j = 0; j < mcut->n_cells; j++ )
  168.     if ( c[j].freq > freqmax && c[j].dividable )
  169.         {
  170.         cmax = &(c[j]);
  171.         freqmax = cmax->freq;
  172.         }
  173. }
  174. /*...e*/
  175.         if ( cmax == NULL )
  176.             break;
  177.  
  178.         while ( cmax->dividable )
  179.             {
  180.             byte split;
  181.             CELL *cnew = &(c[mcut->n_cells]);
  182.  
  183. /*...scalculate way to do the split:24:*/
  184. {
  185. int dr = (cmax->dividable&DIV_R) ? cmax->r1 - cmax->r0 : 0;
  186. int dg = (cmax->dividable&DIV_G) ? cmax->g1 - cmax->g0 : 0;
  187. int db = (cmax->dividable&DIV_B) ? cmax->b1 - cmax->b0 : 0;
  188.  
  189. if ( dg >= dr && dg >= db )
  190.     split = DIV_G;
  191. else if ( dr >= db )
  192.     split = DIV_R;
  193. else 
  194.     split = DIV_B;
  195. }
  196. /*...e*/
  197.             switch ( split )
  198.                 {
  199. /*...sDIV_R:32:*/
  200. case DIV_R:
  201.     {
  202.     byte r, g, b;
  203.     dword slice, total = 0;
  204.  
  205.     for ( r = cmax->r0; total < (cmax->freq>>1); r++ )
  206.         {
  207.         slice = 0;
  208.         for ( g = cmax->g0; g < cmax->g1; g++ )
  209.             for ( b = cmax->b0; b < cmax->b1; b++ )
  210.                 slice += mcut->freqs[b][g][r];
  211.         total += slice;
  212.         }
  213.  
  214.     if ( r == cmax->r1 && total > slice )
  215.         {
  216.         r--;
  217.         total -= slice;
  218.         }
  219.  
  220.     cnew->r1 = cmax->r1;
  221.     cnew->r0 = cmax->r1 = r;
  222.     cnew->g0 = cmax->g0;
  223.     cnew->g1 = cmax->g1;
  224.     cnew->b0 = cmax->b0;
  225.     cnew->b1 = cmax->b1;
  226.     cnew->freq = cmax->freq - total;
  227.     cmax->freq = total;
  228.     }
  229.     break;
  230. /*...e*/
  231. /*...sDIV_G:32:*/
  232. case DIV_G:
  233.     {
  234.     byte r, g, b;
  235.     dword slice, total = 0;
  236.  
  237.     for ( g = cmax->g0; total < (cmax->freq>>1); g++ )
  238.         {
  239.         slice = 0;
  240.         for ( r = cmax->r0; r < cmax->r1; r++ )
  241.             for ( b = cmax->b0; b < cmax->b1; b++ )
  242.                 slice += mcut->freqs[b][g][r];
  243.         total += slice;
  244.         }
  245.  
  246.     if ( g == cmax->g1 && total > slice )
  247.         {
  248.         g--;
  249.         total -= slice;
  250.         }
  251.  
  252.     cnew->r0 = cmax->r0;
  253.     cnew->r1 = cmax->r1;
  254.     cnew->g1 = cmax->g1;
  255.     cnew->g0 = cmax->g1 = g;
  256.     cnew->b0 = cmax->b0;
  257.     cnew->b1 = cmax->b1;
  258.     cnew->freq = cmax->freq - total;
  259.     cmax->freq = total;
  260.     }
  261.     break;
  262. /*...e*/
  263. /*...sDIV_B:32:*/
  264. case DIV_B:
  265.     {
  266.     byte r, g, b;
  267.     dword slice, total = 0;
  268.  
  269.     for ( b = cmax->b0; total < (cmax->freq>>1); b++ )
  270.         {
  271.         slice = 0;
  272.         for ( r = cmax->r0; r < cmax->r1; r++ )
  273.             for ( g = cmax->g0; g < cmax->g1; g++ )
  274.                 slice += mcut->freqs[b][g][r];
  275.         total += slice;
  276.         }
  277.  
  278.     if ( b == cmax->b1 && total > slice )
  279.         {
  280.         b--;
  281.         total -= slice;
  282.         }
  283.  
  284.     cnew->r0 = cmax->r0;
  285.     cnew->r1 = cmax->r1;
  286.     cnew->g0 = cmax->g0;
  287.     cnew->g1 = cmax->g1;
  288.     cnew->b1 = cmax->b1;
  289.     cnew->b0 = cmax->b1 = b;
  290.     cnew->freq = cmax->freq - total;
  291.     cmax->freq = total;
  292.     }
  293.     break;
  294. /*...e*/
  295.                 }
  296.             if ( cnew->freq > 0 )
  297.                 {
  298.                 mcut->n_cells++;
  299.                 shrink(mcut, cmax);
  300.                 shrink(mcut, cnew);
  301.                 break;
  302.                 }
  303.             cmax->dividable &= ~split;
  304.             }
  305.         }
  306.  
  307.     /* I would like to return the palette sorted by frequency of use */
  308.     /* This isn't technically a requirement of this algorithm        */
  309.     /* If I do though, it allows me to do other things afterwards    */
  310.  
  311.     for ( i = 0; i < mcut->n_cells; i++ )
  312.         reorder[i] = (byte) i;
  313.  
  314.     for ( j = mcut->n_cells; j > 0; j-- )
  315.         {
  316.         BOOLEAN noswaps = TRUE;
  317.         for ( i = 0; i < j - 1; i++ )
  318.             if ( c[reorder[i]].freq < c[reorder[i+1]].freq )
  319.                 {
  320.                 byte t = reorder[i];
  321.                 reorder[i] = reorder[i+1];
  322.                 reorder[i+1] = t;
  323.                 noswaps = FALSE;
  324.                 }
  325.         if ( noswaps )
  326.             break;
  327.         }
  328.  
  329.  
  330.     /* Now set up the palette array passed in */
  331.     /* Note: ( ((x+y)/2) << 3 ) == ( (x+y) << 2 ) */
  332.     /* Also, label each point in the cell as being a member of that cell */
  333.  
  334.     for ( i = 0; i < mcut->n_cells; i++ )
  335.         {
  336.         int inx = reorder[i];
  337.         byte r, g, b;
  338.  
  339.         gbmrgb[i].r = ( (c[inx].r0 + c[inx].r1) << 2 );
  340.         gbmrgb[i].g = ( (c[inx].g0 + c[inx].g1) << 2 );
  341.         gbmrgb[i].b = ( (c[inx].b0 + c[inx].b1) << 2 );
  342.  
  343.         for ( r = c[inx].r0; r < c[inx].r1; r++ )
  344.             for ( g = c[inx].g0; g < c[inx].g1; g++ )
  345.                 for ( b = c[inx].b0; b < c[inx].b1; b++ )
  346.                     mcut->freqs[b][g][r] = i;
  347.         }
  348.  
  349.     /* Unused palette entries will be medium grey */
  350.     for ( ; i < 0x100; i++ )
  351.         {
  352.         gbmrgb[i].r = 0x80;
  353.         gbmrgb[i].g = 0x80;
  354.         gbmrgb[i].b = 0x80;
  355.         }
  356.     }
  357. /*...e*/
  358. /*...sgbm_map_mcut    \45\ map to median cutted palette:0:*/
  359. void gbm_map_mcut(
  360.     GBMMCUT *mcut,
  361.     const GBM *gbm, const byte *data24, byte *data8
  362.     )
  363.     {
  364.     int stride24 = ((gbm->w * 3 + 3) & ~3);
  365.     int step24   = stride24 - gbm->w * 3;
  366.     int stride8  = ((gbm->w + 3) & ~3);
  367.     int step8    = stride8 - gbm->w;
  368.     int x, y;
  369.  
  370.     /* Now transform the image data */
  371.  
  372.     for ( y = 0; y < gbm->h; y++, data24 += step24, data8 += step8 )
  373.         for ( x = 0; x < gbm->w; x++ )
  374.             {
  375.             byte b = (*data24++ >> 3);
  376.             byte g = (*data24++ >> 3);
  377.             byte r = (*data24++ >> 3);
  378.  
  379.             *data8++ = (byte) ( mcut->freqs[b][g][r] );
  380.             }
  381.     }
  382. /*...e*/
  383. /*...sgbm_mcut        \45\ map single bitmap using median cut:0:*/
  384. BOOLEAN gbm_mcut(
  385.     const GBM *gbm, const byte *data24,
  386.     GBMRGB gbmrgb[],
  387.     byte *data8,
  388.     int n_cols_wanted
  389.     )
  390.     {
  391.     GBMMCUT *mcut;
  392.  
  393.     if ( (mcut = gbm_create_mcut()) == NULL )
  394.         return FALSE;
  395.     gbm_add_to_mcut(mcut, gbm, data24);
  396.     gbm_pal_mcut(mcut, gbmrgb, n_cols_wanted);
  397.     gbm_map_mcut(mcut, gbm, data24, data8);
  398.     gbm_delete_mcut(mcut);
  399.     return TRUE;
  400.     }
  401. /*...e*/
  402.