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
34static inline uint8
35clip(float component)
36{
37	if (component > 255.0)
38		return 255;
39
40	return (uint8)(component + 0.5f);
41}
42
43struct 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
55BColorQuantizer::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
74BColorQuantizer::~BColorQuantizer()
75{
76	if (fTree != NULL)
77		_DeleteTree(&fTree);
78}
79
80
81bool
82BColorQuantizer::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
102uint32
103BColorQuantizer::GetColorCount() const
104{
105	return fLeafCount;
106}
107
108
109void
110BColorQuantizer::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
150void
151BColorQuantizer::_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
181BColorQuantizer::Node*
182BColorQuantizer::_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
201void
202BColorQuantizer::_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
245void
246BColorQuantizer::_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
257void
258BColorQuantizer::_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