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
clip(float component)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
BColorQuantizer(uint32 maxColors,uint32 bitsPerColor)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
~BColorQuantizer()74 BColorQuantizer::~BColorQuantizer()
75 {
76 if (fTree != NULL)
77 _DeleteTree(&fTree);
78 }
79
80
81 bool
ProcessImage(const uint8 * const * rowPtrs,int width,int height)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
GetColorCount() const103 BColorQuantizer::GetColorCount() const
104 {
105 return fLeafCount;
106 }
107
108
109 void
GetColorTable(RGBA * table) const110 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
_AddColor(Node ** _node,uint8 r,uint8 g,uint8 b,uint8 a,uint32 bitsPerColor,uint32 level,uint32 * _leafCount,Node ** reducibleNodes)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*
_CreateNode(uint32 level,uint32 bitsPerColor,uint32 * _leafCount,Node ** reducibleNodes)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
_ReduceTree(uint32 bitsPerColor,uint32 * _leafCount,Node ** reducibleNodes)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
_DeleteTree(Node ** _node)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
_GetPaletteColors(Node * node,RGBA * table,uint32 * _index,uint32 * sums) const258 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