1 /* === C R E D I T S & D I S C L A I M E R S ============== 2 * Permission is given by the author to freely redistribute and include 3 * this code in any program as long as this credit is given where due. 4 * 5 * CQuantizer (c) 1996-1997 Jeff Prosise 6 * 7 * 31/08/2003 Davide Pizzolato - www.xdp.it 8 * - fixed minor bug in ProcessImage when bpp<=8 9 * - better color reduction to less than 16 colors 10 * 11 * COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS, WITHOUT 12 * WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, WITHOUT 13 * LIMITATION, WARRANTIES THAT THE COVERED CODE IS FREE OF DEFECTS, 14 * MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE OR NON-INFRINGING. THE ENTIRE 15 * RISK AS TO THE QUALITY AND PERFORMANCE OF THE COVERED CODE IS WITH YOU. 16 * SHOULD ANY COVERED CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT THE INITIAL 17 * DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY NECESSARY 18 * SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF WARRANTY CONSTITUTES AN 19 * ESSENTIAL PART OF THIS LICENSE. NO USE OF ANY COVERED CODE IS AUTHORIZED 20 * HEREUNDER EXCEPT UNDER THIS DISCLAIMER. 21 * 22 * Use at your own risk! 23 * ========================================================== 24 * 25 * Modified for use with Haiku by David Powell & Stephan Aßmus. 26 */ 27 #include "ColorQuantizer.h" 28 29 #include <stddef.h> 30 #include <stdlib.h> 31 #include <string.h> 32 33 34 static inline uint8 35 clip(float component) 36 { 37 if (component > 255.0) 38 return 255; 39 40 return (uint8)(component + 0.5f); 41 } 42 43 struct BColorQuantizer::Node { 44 bool isLeaf; // TRUE if node has no children 45 uint32 pixelCount; // Number of pixels represented by this leaf 46 uint32 sumR; // Sum of red components 47 uint32 sumG; // Sum of green components 48 uint32 sumB; // Sum of blue components 49 uint32 sumA; // Sum of alpha components 50 Node* child[8]; // Pointers to child nodes 51 Node* next; // Pointer to next reducible node 52 }; 53 54 55 BColorQuantizer::BColorQuantizer(uint32 maxColors, uint32 bitsPerColor) 56 : fTree(NULL), 57 fLeafCount(0), 58 fMaxColors(maxColors), 59 fOutputMaxColors(maxColors), 60 fBitsPerColor(bitsPerColor) 61 { 62 // override parameters if out of range 63 if (fBitsPerColor > 8) 64 fBitsPerColor = 8; 65 66 if (fMaxColors < 16) 67 fMaxColors = 16; 68 69 for (int i = 0; i <= (int)fBitsPerColor; i++) 70 fReducibleNodes[i] = NULL; 71 } 72 73 74 BColorQuantizer::~BColorQuantizer() 75 { 76 if (fTree != NULL) 77 _DeleteTree(&fTree); 78 } 79 80 81 bool 82 BColorQuantizer::ProcessImage(const uint8* const * rowPtrs, int width, 83 int height) 84 { 85 for (int y = 0; y < height; y++) { 86 for (int x = 0; x < width; x += 3) { 87 uint8 b = rowPtrs[y][x]; 88 uint8 g = rowPtrs[y][x + 1]; 89 uint8 r = rowPtrs[y][x + 2]; 90 _AddColor(&fTree, r, g, b, 0, fBitsPerColor, 0, &fLeafCount, 91 fReducibleNodes); 92 93 while (fLeafCount > fMaxColors) 94 _ReduceTree(fBitsPerColor, &fLeafCount, fReducibleNodes); 95 } 96 } 97 98 return true; 99 } 100 101 102 uint32 103 BColorQuantizer::GetColorCount() const 104 { 105 return fLeafCount; 106 } 107 108 109 void 110 BColorQuantizer::GetColorTable(RGBA* table) const 111 { 112 uint32 index = 0; 113 if (fOutputMaxColors < 16) { 114 uint32 sums[16]; 115 RGBA tmpPalette[16]; 116 _GetPaletteColors(fTree, tmpPalette, &index, sums); 117 if (fLeafCount > fOutputMaxColors) { 118 for (uint32 j = 0; j < fOutputMaxColors; j++) { 119 uint32 a = (j * fLeafCount) / fOutputMaxColors; 120 uint32 b = ((j + 1) * fLeafCount) / fOutputMaxColors; 121 uint32 nr = 0; 122 uint32 ng = 0; 123 uint32 nb = 0; 124 uint32 na = 0; 125 uint32 ns = 0; 126 for (uint32 k = a; k < b; k++){ 127 nr += tmpPalette[k].r * sums[k]; 128 ng += tmpPalette[k].g * sums[k]; 129 nb += tmpPalette[k].b * sums[k]; 130 na += tmpPalette[k].a * sums[k]; 131 ns += sums[k]; 132 } 133 table[j].r = clip((float)nr / ns); 134 table[j].g = clip((float)ng / ns); 135 table[j].b = clip((float)nb / ns); 136 table[j].a = clip((float)na / ns); 137 } 138 } else { 139 memcpy(table, tmpPalette, fLeafCount * sizeof(RGBA)); 140 } 141 } else { 142 _GetPaletteColors(fTree, table, &index, NULL); 143 } 144 } 145 146 147 // #pragma mark - private 148 149 150 void 151 BColorQuantizer::_AddColor(Node** _node, uint8 r, uint8 g, uint8 b, uint8 a, 152 uint32 bitsPerColor, uint32 level, uint32* _leafCount, 153 Node** reducibleNodes) 154 { 155 static const uint8 kMask[8] 156 = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01}; 157 158 // If the node doesn't exist, create it. 159 if (*_node == NULL) 160 *_node = _CreateNode(level, bitsPerColor, _leafCount, reducibleNodes); 161 162 // Update color information if it's a leaf node. 163 if ((*_node)->isLeaf) { 164 (*_node)->pixelCount++; 165 (*_node)->sumR += r; 166 (*_node)->sumG += g; 167 (*_node)->sumB += b; 168 (*_node)->sumA += a; 169 } else { 170 // Recurse a level deeper if the node is not a leaf. 171 int shift = 7 - level; 172 int index = (((r & kMask[level]) >> shift) << 2) | 173 (((g & kMask[level]) >> shift) << 1) | 174 (( b & kMask[level]) >> shift); 175 _AddColor(&((*_node)->child[index]), r, g, b, a, bitsPerColor, 176 level + 1, _leafCount, reducibleNodes); 177 } 178 } 179 180 181 BColorQuantizer::Node* 182 BColorQuantizer::_CreateNode(uint32 level, uint32 bitsPerColor, 183 uint32* _leafCount, Node** reducibleNodes) 184 { 185 Node* node = (Node*)calloc(1, sizeof(Node)); 186 187 if (node == NULL) 188 return NULL; 189 190 node->isLeaf = (level == bitsPerColor) ? true : false; 191 if (node->isLeaf) 192 (*_leafCount)++; 193 else { 194 node->next = reducibleNodes[level]; 195 reducibleNodes[level] = node; 196 } 197 return node; 198 } 199 200 201 void 202 BColorQuantizer::_ReduceTree(uint32 bitsPerColor, uint32* _leafCount, 203 Node** reducibleNodes) 204 { 205 int i = bitsPerColor - 1; 206 // Find the deepest level containing at least one reducible node. 207 for (; i > 0 && reducibleNodes[i] == NULL; i--) 208 ; 209 210 // Reduce the node most recently added to the list at level i. 211 Node* node = reducibleNodes[i]; 212 reducibleNodes[i] = node->next; 213 214 uint32 sumR = 0; 215 uint32 sumG = 0; 216 uint32 sumB = 0; 217 uint32 sumA = 0; 218 uint32 childCount = 0; 219 220 for (i = 0; i < 8; i++) { 221 if (node->child[i] != NULL) { 222 sumR += node->child[i]->sumR; 223 sumG += node->child[i]->sumG; 224 sumB += node->child[i]->sumB; 225 sumA += node->child[i]->sumA; 226 node->pixelCount += node->child[i]->pixelCount; 227 228 free(node->child[i]); 229 node->child[i] = NULL; 230 231 childCount++; 232 } 233 } 234 235 node->isLeaf = true; 236 node->sumR = sumR; 237 node->sumG = sumG; 238 node->sumB = sumB; 239 node->sumA = sumA; 240 241 *_leafCount -= (childCount - 1); 242 } 243 244 245 void 246 BColorQuantizer::_DeleteTree(Node** _node) 247 { 248 for (int i = 0; i < 8; i++) { 249 if ((*_node)->child[i] != NULL) 250 _DeleteTree(&((*_node)->child[i])); 251 } 252 free(*_node); 253 *_node = NULL; 254 } 255 256 257 void 258 BColorQuantizer::_GetPaletteColors(Node* node, RGBA* table, uint32* _index, 259 uint32* sums) const 260 { 261 if (node == NULL) 262 return; 263 264 if (node->isLeaf) { 265 table[*_index].r = clip((float)node->sumR / node->pixelCount); 266 table[*_index].g = clip((float)node->sumG / node->pixelCount); 267 table[*_index].b = clip((float)node->sumB / node->pixelCount); 268 table[*_index].a = clip((float)node->sumA / node->pixelCount); 269 if (sums) 270 sums[*_index] = node->pixelCount; 271 (*_index)++; 272 } else { 273 for (int i = 0; i < 8; i++) { 274 if (node->child[i] != NULL) 275 _GetPaletteColors(node->child[i], table, _index, sums); 276 } 277 } 278 } 279 280