home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume9 / pbmplus / part11 / ppm / libppm3.c < prev    next >
C/C++ Source or Header  |  1989-11-26  |  6KB  |  259 lines
  1. /* libppm3.c - ppm utility library part 3
  2. **
  3. ** Copyright (C) 1989 by Jef Poskanzer.
  4. **
  5. ** Permission to use, copy, modify, and distribute this software and its
  6. ** documentation for any purpose and without fee is hereby granted, provided
  7. ** that the above copyright notice appear in all copies and that both that
  8. ** copyright notice and this permission notice appear in supporting
  9. ** documentation.  This software is provided "as is" without express or
  10. ** implied warranty.
  11. */
  12.  
  13. #include <stdio.h>
  14. #include "ppm.h"
  15. #include "ppmcmap.h"
  16. #include "libppm.h"
  17.  
  18. #define HASH_SIZE 6553
  19. /* #define HASH_SIZE 157 */
  20.  
  21. #ifdef PPM_PACKCOLORS
  22. #define ppm_hashpixel(p) ( ( (int) (p) * 353 ) % HASH_SIZE )
  23. #else /*PPM_PACKCOLORS*/
  24. #define ppm_hashpixel(p) ( ( (int) PPM_GETR(p) * 33023 + (int) PPM_GETG(p) * 30013 + (int) PPM_GETB(p) * 27011 ) % HASH_SIZE )
  25. #endif /*PPM_PACKCOLORS*/
  26.  
  27. colorhist_vector
  28. ppm_computecolorhist( pixels, cols, rows, maxcolors, colorsP )
  29. pixel **pixels;
  30. int cols, rows, *colorsP;
  31.     {
  32.     colorhash_table cht;
  33.     colorhist_vector chv;
  34.  
  35.     cht = ppm_computecolorhash( pixels, cols, rows, maxcolors, colorsP );
  36.     if ( cht == (colorhash_table) 0 )
  37.     return (colorhist_vector) 0;
  38.     chv = ppm_colorhashtocolorhist( cht, maxcolors );
  39.     ppm_freecolorhash( cht );
  40.     return chv;
  41.     }
  42.  
  43. void
  44. ppm_addtocolorhist( chv, colorsP, maxcolors, color, value, position )
  45. colorhist_vector chv;
  46. pixel color;
  47. int *colorsP, maxcolors, value, position;
  48.     {
  49.     int i, j;
  50.  
  51.     /* Search colorhist for the color. */
  52.     for ( i = 0; i < *colorsP; i++ )
  53.     if ( PPM_EQUAL( chv[i].color, color ) )
  54.         {
  55.         /* Found it - move to new slot. */
  56.         if ( position > i )
  57.         {
  58.         for ( j = i; j < position; ++j )
  59.             chv[j] = chv[j + 1];
  60.         }
  61.         else if ( position < i )
  62.         {
  63.         for ( j = i; j > position; --j )
  64.             chv[j] = chv[j - 1];
  65.         }
  66.         chv[position].color = color;
  67.         chv[position].value = value;
  68.         return;
  69.         }
  70.     if ( *colorsP < maxcolors )
  71.     {
  72.     /* Didn't find it, but there's room to add it; so do so. */
  73.     for ( i = *colorsP; i > position; i-- )
  74.         chv[i] = chv[i - 1];
  75.     chv[position].color = color;
  76.     chv[position].value = value;
  77.     (*colorsP)++;
  78.     }
  79.     }
  80.  
  81. colorhash_table
  82. ppm_computecolorhash( pixels, cols, rows, maxcolors, colorsP )
  83. pixel **pixels;
  84. int cols, rows, *colorsP;
  85.     {
  86.     colorhash_table cht;
  87.     register pixel *pP;
  88.     colorhist_list chl;
  89.     int col, row, hash;
  90.  
  91.     cht = ppm_alloccolorhash( );
  92.     *colorsP = 0;
  93.  
  94.     /* Go through the entire image, building a hash table of colors. */
  95.     for ( row = 0; row < rows; row++ )
  96.     for ( col = 0, pP = pixels[row]; col < cols; col++, pP++ )
  97.         {
  98.         hash = ppm_hashpixel( *pP );
  99.         for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next )
  100.         if ( PPM_EQUAL( chl->ch.color, *pP ) )
  101.             break;
  102.         if ( chl != (colorhist_list) 0 )
  103.         chl->ch.value++;
  104.         else
  105.         {
  106.         if ( (*colorsP)++ > maxcolors )
  107.             {
  108.             ppm_freecolorhash( cht );
  109.             return (colorhash_table) 0;
  110.             }
  111.         chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) );
  112.         if ( chl == 0 )
  113.             pm_error( "out of memory computing hash table", 0,0,0,0,0 );
  114.         chl->ch.color = *pP;
  115.         chl->ch.value = 1;
  116.         chl->next = cht[hash];
  117.         cht[hash] = chl;
  118.         }
  119.         }
  120.     
  121.     return cht;
  122.     }
  123.  
  124. colorhash_table
  125. ppm_alloccolorhash( )
  126.     {
  127.     colorhash_table cht;
  128.     int i;
  129.  
  130.     cht = (colorhash_table) malloc( HASH_SIZE * sizeof(colorhist_list) );
  131.     if ( cht == 0 )
  132.     pm_error( "out of memory allocating hash table", 0,0,0,0,0 );
  133.  
  134.     for ( i = 0; i < HASH_SIZE; i++ )
  135.     cht[i] = (colorhist_list) 0;
  136.  
  137.     return cht;
  138.     }
  139.  
  140. void
  141. ppm_addtocolorhash( cht, color, value )
  142. colorhash_table cht;
  143. pixel color;
  144. int value;
  145.     {
  146.     int hash;
  147.     colorhist_list chl;
  148.  
  149.     hash = ppm_hashpixel( color );
  150.     chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) );
  151.     if ( chl == 0 )
  152.     pm_error( "out of memory adding to hash table", 0,0,0,0,0 );
  153.     chl->ch.color = color;
  154.     chl->ch.value = value;
  155.     chl->next = cht[hash];
  156.     cht[hash] = chl;
  157. }
  158.  
  159. colorhist_vector
  160. ppm_colorhashtocolorhist( cht, maxcolors )
  161. colorhash_table cht;
  162. int maxcolors;
  163.     {
  164.     colorhist_vector chv;
  165.     colorhist_list chl;
  166.     int i, j;
  167.  
  168.     /* Now collate the hash table into a simple colorhist array. */
  169.     chv = (colorhist_vector) malloc( maxcolors * sizeof(struct colorhist_item) );
  170.     /* (Leave room for expansion by caller.) */
  171.     if ( chv == (colorhist_vector) 0 )
  172.     pm_error( "out of memory generating histogram", 0,0,0,0,0 );
  173.  
  174.     /* Loop through the hash table. */
  175.     j = 0;
  176.     for ( i = 0; i < HASH_SIZE; i++ )
  177.     for ( chl = cht[i]; chl != (colorhist_list) 0; chl = chl->next )
  178.         {
  179.         /* Add the new entry. */
  180.         chv[j] = chl->ch;
  181.         j++;
  182.         }
  183.  
  184.     /* All done. */
  185.     return chv;
  186.     }
  187.  
  188. colorhash_table
  189. ppm_colorhisttocolorhash( chv, colors )
  190. colorhist_vector chv;
  191. int colors;
  192.     {
  193.     colorhash_table cht;
  194.     int i, hash;
  195.     pixel color;
  196.     colorhist_list chl;
  197.  
  198.     cht = ppm_alloccolorhash( );
  199.  
  200.     for ( i = 0; i < colors; i++ )
  201.     {
  202.     color = chv[i].color;
  203.     hash = ppm_hashpixel( color );
  204.     for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next )
  205.         if ( PPM_EQUAL( chl->ch.color, color ) )
  206.         pm_error(
  207.             "same color found twice - %d %d %d", PPM_GETR(color),
  208.             PPM_GETG(color), PPM_GETB(color), 0,0 );
  209.     chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) );
  210.     if ( chl == (colorhist_list) 0 )
  211.         pm_error( "out of memory", 0,0,0,0,0 );
  212.     chl->ch.color = color;
  213.     chl->ch.value = i;
  214.     chl->next = cht[hash];
  215.     cht[hash] = chl;
  216.     }
  217.  
  218.     return cht;
  219.     }
  220.  
  221. int
  222. ppm_lookupcolor( cht, color )
  223. colorhash_table cht;
  224. pixel color;
  225.     {
  226.     int hash;
  227.     colorhist_list chl;
  228.  
  229.     hash = ppm_hashpixel( color );
  230.     for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next )
  231.     if ( PPM_EQUAL( chl->ch.color, color ) )
  232.         return chl->ch.value;
  233.  
  234.     return -1;
  235.     }
  236.  
  237. void
  238. ppm_freecolorhist( chv )
  239. colorhist_vector chv;
  240.     {
  241.     free( (char *) chv );
  242.     }
  243.  
  244. void
  245. ppm_freecolorhash( cht )
  246. colorhash_table cht;
  247.     {
  248.     int i;
  249.     colorhist_list chl, chlnext;
  250.  
  251.     for ( i = 0; i < HASH_SIZE; i++ )
  252.     for ( chl = cht[i]; chl != (colorhist_list) 0; chl = chlnext )
  253.         {
  254.         chlnext = chl->next;
  255.         free( (char *) chl );
  256.         }
  257.     free( (char *) cht );
  258.     }
  259.