Panda3D
|
00001 /* libppm3.c - ppm utility library part 3 00002 ** 00003 ** Colormap routines. 00004 ** 00005 ** Copyright (C) 1989, 1991 by Jef Poskanzer. 00006 ** 00007 ** Permission to use, copy, modify, and distribute this software and its 00008 ** documentation for any purpose and without fee is hereby granted, provided 00009 ** that the above copyright notice appear in all copies and that both that 00010 ** copyright notice and this permission notice appear in supporting 00011 ** documentation. This software is provided "as is" without express or 00012 ** implied warranty. 00013 */ 00014 00015 #include "ppmcmap.h" 00016 00017 #define HASH_SIZE 20023 00018 00019 #ifdef PPM_PACKCOLORS 00020 #define ppm_hashpixel(p) ( ( (int) (p) & 0x7fffffff ) % HASH_SIZE ) 00021 #else /*PPM_PACKCOLORS*/ 00022 #define ppm_hashpixel(p) ( ( ( (long) PPM_GETR(p) * 33023 + (long) PPM_GETG(p) * 30013 + (long) PPM_GETB(p) * 27011 ) & 0x7fffffff ) % HASH_SIZE ) 00023 #endif /*PPM_PACKCOLORS*/ 00024 00025 colorhist_vector 00026 ppm_computecolorhist(pixel** pixels, 00027 int cols, int rows, int maxcolors, 00028 int* colorsP) 00029 { 00030 colorhash_table cht; 00031 colorhist_vector chv; 00032 00033 cht = ppm_computecolorhash( pixels, cols, rows, maxcolors, colorsP ); 00034 if ( cht == (colorhash_table) 0 ) 00035 return (colorhist_vector) 0; 00036 chv = ppm_colorhashtocolorhist( cht, maxcolors ); 00037 ppm_freecolorhash( cht ); 00038 return chv; 00039 } 00040 00041 void 00042 ppm_addtocolorhist(colorhist_vector chv, 00043 int* colorsP, 00044 int maxcolors, 00045 pixel* colorP, 00046 int value, int position) 00047 { 00048 int i, j; 00049 00050 /* Search colorhist for the color. */ 00051 for ( i = 0; i < *colorsP; ++i ) 00052 if ( PPM_EQUAL( chv[i].color, *colorP ) ) 00053 { 00054 /* Found it - move to new slot. */ 00055 if ( position > i ) 00056 { 00057 for ( j = i; j < position; ++j ) 00058 chv[j] = chv[j + 1]; 00059 } 00060 else if ( position < i ) 00061 { 00062 for ( j = i; j > position; --j ) 00063 chv[j] = chv[j - 1]; 00064 } 00065 chv[position].color = *colorP; 00066 chv[position].value = value; 00067 return; 00068 } 00069 if ( *colorsP < maxcolors ) 00070 { 00071 /* Didn't find it, but there's room to add it; so do so. */ 00072 for ( i = *colorsP; i > position; --i ) 00073 chv[i] = chv[i - 1]; 00074 chv[position].color = *colorP; 00075 chv[position].value = value; 00076 ++(*colorsP); 00077 } 00078 } 00079 00080 colorhash_table 00081 ppm_computecolorhash(pixel** pixels, 00082 int cols, int rows, int maxcolors, 00083 int* colorsP) 00084 { 00085 colorhash_table cht; 00086 register pixel* pP; 00087 colorhist_list chl; 00088 int col, row, hash; 00089 00090 cht = ppm_alloccolorhash( ); 00091 *colorsP = 0; 00092 00093 /* Go through the entire image, building a hash table of colors. */ 00094 for ( row = 0; row < rows; ++row ) 00095 for ( col = 0, pP = pixels[row]; col < cols; ++col, ++pP ) 00096 { 00097 hash = ppm_hashpixel( *pP ); 00098 for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next ) 00099 if ( PPM_EQUAL( chl->ch.color, *pP ) ) 00100 break; 00101 if ( chl != (colorhist_list) 0 ) 00102 ++(chl->ch.value); 00103 else 00104 { 00105 if ( ++(*colorsP) > maxcolors ) 00106 { 00107 ppm_freecolorhash( cht ); 00108 return (colorhash_table) 0; 00109 } 00110 chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) ); 00111 if ( chl == 0 ) 00112 pm_error( "out of memory computing hash table" ); 00113 chl->ch.color = *pP; 00114 chl->ch.value = 1; 00115 chl->next = cht[hash]; 00116 cht[hash] = chl; 00117 } 00118 } 00119 00120 return cht; 00121 } 00122 00123 colorhash_table 00124 ppm_alloccolorhash( ) 00125 { 00126 colorhash_table cht; 00127 int i; 00128 00129 cht = (colorhash_table) malloc( HASH_SIZE * sizeof(colorhist_list) ); 00130 if ( cht == 0 ) 00131 pm_error( "out of memory allocating hash table" ); 00132 00133 for ( i = 0; i < HASH_SIZE; ++i ) 00134 cht[i] = (colorhist_list) 0; 00135 00136 return cht; 00137 } 00138 00139 int 00140 ppm_addtocolorhash(colorhash_table cht, 00141 pixel* colorP, 00142 int value) 00143 { 00144 register int hash; 00145 register colorhist_list chl; 00146 00147 chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) ); 00148 if ( chl == 0 ) 00149 return -1; 00150 hash = ppm_hashpixel( *colorP ); 00151 chl->ch.color = *colorP; 00152 chl->ch.value = value; 00153 chl->next = cht[hash]; 00154 cht[hash] = chl; 00155 return 0; 00156 } 00157 00158 colorhist_vector 00159 ppm_colorhashtocolorhist(colorhash_table cht, 00160 int maxcolors) 00161 { 00162 colorhist_vector chv; 00163 colorhist_list chl; 00164 int i, j; 00165 00166 /* Now collate the hash table into a simple colorhist array. */ 00167 chv = (colorhist_vector) malloc( maxcolors * sizeof(struct colorhist_item) ); 00168 /* (Leave room for expansion by caller.) */ 00169 if ( chv == (colorhist_vector) 0 ) 00170 pm_error( "out of memory generating histogram" ); 00171 00172 /* Loop through the hash table. */ 00173 j = 0; 00174 for ( i = 0; i < HASH_SIZE; ++i ) 00175 for ( chl = cht[i]; chl != (colorhist_list) 0; chl = chl->next ) 00176 { 00177 /* Add the new entry. */ 00178 chv[j] = chl->ch; 00179 ++j; 00180 } 00181 00182 /* All done. */ 00183 return chv; 00184 } 00185 00186 colorhash_table 00187 ppm_colorhisttocolorhash(colorhist_vector chv, 00188 int colors) 00189 { 00190 colorhash_table cht; 00191 int i, hash; 00192 pixel color; 00193 colorhist_list chl; 00194 00195 cht = ppm_alloccolorhash( ); 00196 00197 for ( i = 0; i < colors; ++i ) 00198 { 00199 color = chv[i].color; 00200 hash = ppm_hashpixel( color ); 00201 for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next ) 00202 if ( PPM_EQUAL( chl->ch.color, color ) ) 00203 pm_error( 00204 "same color found twice - %d %d %d", PPM_GETR(color), 00205 PPM_GETG(color), PPM_GETB(color) ); 00206 chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) ); 00207 if ( chl == (colorhist_list) 0 ) 00208 pm_error( "out of memory" ); 00209 chl->ch.color = color; 00210 chl->ch.value = i; 00211 chl->next = cht[hash]; 00212 cht[hash] = chl; 00213 } 00214 00215 return cht; 00216 } 00217 00218 int 00219 ppm_lookupcolor(colorhash_table cht, 00220 pixel* colorP) 00221 { 00222 int hash; 00223 colorhist_list chl; 00224 00225 hash = ppm_hashpixel( *colorP ); 00226 for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next ) 00227 if ( PPM_EQUAL( chl->ch.color, *colorP ) ) 00228 return chl->ch.value; 00229 00230 return -1; 00231 } 00232 00233 void 00234 ppm_freecolorhist(colorhist_vector chv) 00235 { 00236 free( (char*) chv ); 00237 } 00238 00239 void 00240 ppm_freecolorhash(colorhash_table cht) 00241 { 00242 int i; 00243 colorhist_list chl, chlnext; 00244 00245 for ( i = 0; i < HASH_SIZE; ++i ) 00246 for ( chl = cht[i]; chl != (colorhist_list) 0; chl = chlnext ) 00247 { 00248 chlnext = chl->next; 00249 free( (char*) chl ); 00250 } 00251 free( (char*) cht ); 00252 }