1// tQuantizeFixed.cpp 
2// 
3// This module implements quantization of an image based on a fixed palette of colours as well as a function to perform 
4// an exact palettization if the number of unique pixel colours is less-than or equal to the number of colours available 
5// to the palette. 
6// 
7// Copyright (c) 2022-2024 Tristan Grimmer. 
8// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
9// granted, provided that the above copyright notice and this permission notice appear in all copies. 
10// 
11// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
12// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
13// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
14// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
15// PERFORMANCE OF THIS SOFTWARE. 
16 
17#include <Math/tColour.h> 
18#include <Foundation/tMap.h> 
19#include <System/tPrint.h> 
20#include <System/tFile.h> 
21#include "Image/tQuantize.h" 
22// #define QUANTIZE_GENERATE_FIXED_PALETTES 
23namespace tImage { 
24 
25 
26namespace tQuantizeFixed 
27{ 
28 int FindIndexOfClosestColour_Redmean(const tColour3b* searchSpace, int searchSize, const tColour3b& colour); 
29 
30 #ifdef QUANTIZE_GENERATE_FIXED_PALETTES 
31 // This is the function used to generate the power of 2 palettes (2, 4, 8, 16, 32, 64, 128, and 256 colour). 
32 // It is ifdeffed out and ony for reference as it's output is just a bunch of tables that are generated once and 
33 // included as static tabled in this source file. 
34 void GenerateFixedPalettes(const tString& filename); 
35 void GenerateFixedPalette(tFileHandle, int bitsR, int bitsG, int bitsB); 
36 #endif 
37} 
38 
39 
40#ifdef QUANTIZE_GENERATE_FIXED_PALETTES 
41void tQuantizeFixed::GenerateFixedPalettes(const tString& filename) 
42{ 
43 tFileHandle file = tSystem::tOpenFile(filename, "wt"); 
44 
45 // Note favouring of green, then red, then blue. 
46 GenerateFixedPalette(file, 3, 3, 2); // 8 bits. 
47 GenerateFixedPalette(file, 2, 3, 2); // 7 bits. 
48 GenerateFixedPalette(file, 2, 2, 2); // 6 bits. 
49 GenerateFixedPalette(file, 2, 2, 1); // 5 bits. 
50 GenerateFixedPalette(file, 1, 2, 1); // 4 bits. 
51 GenerateFixedPalette(file, 1, 1, 1); // 3 bits. 
52 GenerateFixedPalette(file, 1, 1, 0); // 2 bits. 
53 GenerateFixedPalette(file, 0, 1, 0); // 1 bits. 
54 
55 tSystem::tCloseFile(file); 
56} 
57 
58 
59void tQuantizeFixed::GenerateFixedPalette(tFileHandle file, int bitsR, int bitsG, int bitsB) 
60{ 
61 int numR = tMath::tPow2(bitsR); 
62 int numG = tMath::tPow2(bitsG); 
63 int numB = tMath::tPow2(bitsB); 
64 int numColours = numR * numG * numB; 
65 
66 tfPrintf(file, "// Generated fixed %d colour palette.\n", numColours); 
67 tfPrintf(file, "namespace tQuantizeFixed { tColour3b Palette%d[] =\n", numColours); 
68 tfPrintf(file, "{\n"); 
69 
70 int entriesPerRow = tMath::tMin(numColours, 8); 
71 int idx = 0; 
72 
73 // Order is important. Favour green, then red, then blue.  
74 for (int bi = 0; bi < numB; bi++) 
75 { 
76 for (int ri = 0; ri < numR; ri++) 
77 { 
78 for (int gi = 0; gi < numG; gi++) 
79 { 
80 int r = (numR == 1) ? 0 : (255 * ri) / (numR-1); 
81 int g = (numG == 1) ? 0 : (255 * gi) / (numG-1); 
82 int b = (numB == 1) ? 0 : (255 * bi) / (numB-1); 
83 
84 if (!((idx) % entriesPerRow)) 
85 tfPrintf(file, "\t"); 
86 else 
87 tfPrintf(file, " "); 
88 
89 if (((numColours == 4) && (idx == 3)) || ((numColours == 2) && (idx == 1))) 
90 r = g = b = 0xFF; 
91 
92 tfPrintf(file, "{ 0x%02X, 0x%02X, 0x%02X }%s", r, g, b, (idx == numColours-1) ? "" : ","); 
93 if (!((idx+1) % entriesPerRow)) 
94 tfPrintf(file, "\n"); 
95 idx++; 
96 } 
97 } 
98 } 
99 tfPrintf(file, "}; tStaticAssert(tNumElements(tQuantizeFixed::Palette%d) == %d); }\n", numColours, numColours); 
100 tfPrintf(file, "\n"); 
101} 
102#endif 
103 
104 
105// Generated fixed 256 colour palette. 
106namespace tQuantizeFixed { tColour3b Palette256[] = 
107{ 
108 { 0x00, 0x00, 0x00 }, { 0x00, 0x24, 0x00 }, { 0x00, 0x48, 0x00 }, { 0x00, 0x6D, 0x00 }, { 0x00, 0x91, 0x00 }, { 0x00, 0xB6, 0x00 }, { 0x00, 0xDA, 0x00 }, { 0x00, 0xFF, 0x00 }, 
109 { 0x24, 0x00, 0x00 }, { 0x24, 0x24, 0x00 }, { 0x24, 0x48, 0x00 }, { 0x24, 0x6D, 0x00 }, { 0x24, 0x91, 0x00 }, { 0x24, 0xB6, 0x00 }, { 0x24, 0xDA, 0x00 }, { 0x24, 0xFF, 0x00 }, 
110 { 0x48, 0x00, 0x00 }, { 0x48, 0x24, 0x00 }, { 0x48, 0x48, 0x00 }, { 0x48, 0x6D, 0x00 }, { 0x48, 0x91, 0x00 }, { 0x48, 0xB6, 0x00 }, { 0x48, 0xDA, 0x00 }, { 0x48, 0xFF, 0x00 }, 
111 { 0x6D, 0x00, 0x00 }, { 0x6D, 0x24, 0x00 }, { 0x6D, 0x48, 0x00 }, { 0x6D, 0x6D, 0x00 }, { 0x6D, 0x91, 0x00 }, { 0x6D, 0xB6, 0x00 }, { 0x6D, 0xDA, 0x00 }, { 0x6D, 0xFF, 0x00 }, 
112 { 0x91, 0x00, 0x00 }, { 0x91, 0x24, 0x00 }, { 0x91, 0x48, 0x00 }, { 0x91, 0x6D, 0x00 }, { 0x91, 0x91, 0x00 }, { 0x91, 0xB6, 0x00 }, { 0x91, 0xDA, 0x00 }, { 0x91, 0xFF, 0x00 }, 
113 { 0xB6, 0x00, 0x00 }, { 0xB6, 0x24, 0x00 }, { 0xB6, 0x48, 0x00 }, { 0xB6, 0x6D, 0x00 }, { 0xB6, 0x91, 0x00 }, { 0xB6, 0xB6, 0x00 }, { 0xB6, 0xDA, 0x00 }, { 0xB6, 0xFF, 0x00 }, 
114 { 0xDA, 0x00, 0x00 }, { 0xDA, 0x24, 0x00 }, { 0xDA, 0x48, 0x00 }, { 0xDA, 0x6D, 0x00 }, { 0xDA, 0x91, 0x00 }, { 0xDA, 0xB6, 0x00 }, { 0xDA, 0xDA, 0x00 }, { 0xDA, 0xFF, 0x00 }, 
115 { 0xFF, 0x00, 0x00 }, { 0xFF, 0x24, 0x00 }, { 0xFF, 0x48, 0x00 }, { 0xFF, 0x6D, 0x00 }, { 0xFF, 0x91, 0x00 }, { 0xFF, 0xB6, 0x00 }, { 0xFF, 0xDA, 0x00 }, { 0xFF, 0xFF, 0x00 }, 
116 { 0x00, 0x00, 0x55 }, { 0x00, 0x24, 0x55 }, { 0x00, 0x48, 0x55 }, { 0x00, 0x6D, 0x55 }, { 0x00, 0x91, 0x55 }, { 0x00, 0xB6, 0x55 }, { 0x00, 0xDA, 0x55 }, { 0x00, 0xFF, 0x55 }, 
117 { 0x24, 0x00, 0x55 }, { 0x24, 0x24, 0x55 }, { 0x24, 0x48, 0x55 }, { 0x24, 0x6D, 0x55 }, { 0x24, 0x91, 0x55 }, { 0x24, 0xB6, 0x55 }, { 0x24, 0xDA, 0x55 }, { 0x24, 0xFF, 0x55 }, 
118 { 0x48, 0x00, 0x55 }, { 0x48, 0x24, 0x55 }, { 0x48, 0x48, 0x55 }, { 0x48, 0x6D, 0x55 }, { 0x48, 0x91, 0x55 }, { 0x48, 0xB6, 0x55 }, { 0x48, 0xDA, 0x55 }, { 0x48, 0xFF, 0x55 }, 
119 { 0x6D, 0x00, 0x55 }, { 0x6D, 0x24, 0x55 }, { 0x6D, 0x48, 0x55 }, { 0x6D, 0x6D, 0x55 }, { 0x6D, 0x91, 0x55 }, { 0x6D, 0xB6, 0x55 }, { 0x6D, 0xDA, 0x55 }, { 0x6D, 0xFF, 0x55 }, 
120 { 0x91, 0x00, 0x55 }, { 0x91, 0x24, 0x55 }, { 0x91, 0x48, 0x55 }, { 0x91, 0x6D, 0x55 }, { 0x91, 0x91, 0x55 }, { 0x91, 0xB6, 0x55 }, { 0x91, 0xDA, 0x55 }, { 0x91, 0xFF, 0x55 }, 
121 { 0xB6, 0x00, 0x55 }, { 0xB6, 0x24, 0x55 }, { 0xB6, 0x48, 0x55 }, { 0xB6, 0x6D, 0x55 }, { 0xB6, 0x91, 0x55 }, { 0xB6, 0xB6, 0x55 }, { 0xB6, 0xDA, 0x55 }, { 0xB6, 0xFF, 0x55 }, 
122 { 0xDA, 0x00, 0x55 }, { 0xDA, 0x24, 0x55 }, { 0xDA, 0x48, 0x55 }, { 0xDA, 0x6D, 0x55 }, { 0xDA, 0x91, 0x55 }, { 0xDA, 0xB6, 0x55 }, { 0xDA, 0xDA, 0x55 }, { 0xDA, 0xFF, 0x55 }, 
123 { 0xFF, 0x00, 0x55 }, { 0xFF, 0x24, 0x55 }, { 0xFF, 0x48, 0x55 }, { 0xFF, 0x6D, 0x55 }, { 0xFF, 0x91, 0x55 }, { 0xFF, 0xB6, 0x55 }, { 0xFF, 0xDA, 0x55 }, { 0xFF, 0xFF, 0x55 }, 
124 { 0x00, 0x00, 0xAA }, { 0x00, 0x24, 0xAA }, { 0x00, 0x48, 0xAA }, { 0x00, 0x6D, 0xAA }, { 0x00, 0x91, 0xAA }, { 0x00, 0xB6, 0xAA }, { 0x00, 0xDA, 0xAA }, { 0x00, 0xFF, 0xAA }, 
125 { 0x24, 0x00, 0xAA }, { 0x24, 0x24, 0xAA }, { 0x24, 0x48, 0xAA }, { 0x24, 0x6D, 0xAA }, { 0x24, 0x91, 0xAA }, { 0x24, 0xB6, 0xAA }, { 0x24, 0xDA, 0xAA }, { 0x24, 0xFF, 0xAA }, 
126 { 0x48, 0x00, 0xAA }, { 0x48, 0x24, 0xAA }, { 0x48, 0x48, 0xAA }, { 0x48, 0x6D, 0xAA }, { 0x48, 0x91, 0xAA }, { 0x48, 0xB6, 0xAA }, { 0x48, 0xDA, 0xAA }, { 0x48, 0xFF, 0xAA }, 
127 { 0x6D, 0x00, 0xAA }, { 0x6D, 0x24, 0xAA }, { 0x6D, 0x48, 0xAA }, { 0x6D, 0x6D, 0xAA }, { 0x6D, 0x91, 0xAA }, { 0x6D, 0xB6, 0xAA }, { 0x6D, 0xDA, 0xAA }, { 0x6D, 0xFF, 0xAA }, 
128 { 0x91, 0x00, 0xAA }, { 0x91, 0x24, 0xAA }, { 0x91, 0x48, 0xAA }, { 0x91, 0x6D, 0xAA }, { 0x91, 0x91, 0xAA }, { 0x91, 0xB6, 0xAA }, { 0x91, 0xDA, 0xAA }, { 0x91, 0xFF, 0xAA }, 
129 { 0xB6, 0x00, 0xAA }, { 0xB6, 0x24, 0xAA }, { 0xB6, 0x48, 0xAA }, { 0xB6, 0x6D, 0xAA }, { 0xB6, 0x91, 0xAA }, { 0xB6, 0xB6, 0xAA }, { 0xB6, 0xDA, 0xAA }, { 0xB6, 0xFF, 0xAA }, 
130 { 0xDA, 0x00, 0xAA }, { 0xDA, 0x24, 0xAA }, { 0xDA, 0x48, 0xAA }, { 0xDA, 0x6D, 0xAA }, { 0xDA, 0x91, 0xAA }, { 0xDA, 0xB6, 0xAA }, { 0xDA, 0xDA, 0xAA }, { 0xDA, 0xFF, 0xAA }, 
131 { 0xFF, 0x00, 0xAA }, { 0xFF, 0x24, 0xAA }, { 0xFF, 0x48, 0xAA }, { 0xFF, 0x6D, 0xAA }, { 0xFF, 0x91, 0xAA }, { 0xFF, 0xB6, 0xAA }, { 0xFF, 0xDA, 0xAA }, { 0xFF, 0xFF, 0xAA }, 
132 { 0x00, 0x00, 0xFF }, { 0x00, 0x24, 0xFF }, { 0x00, 0x48, 0xFF }, { 0x00, 0x6D, 0xFF }, { 0x00, 0x91, 0xFF }, { 0x00, 0xB6, 0xFF }, { 0x00, 0xDA, 0xFF }, { 0x00, 0xFF, 0xFF }, 
133 { 0x24, 0x00, 0xFF }, { 0x24, 0x24, 0xFF }, { 0x24, 0x48, 0xFF }, { 0x24, 0x6D, 0xFF }, { 0x24, 0x91, 0xFF }, { 0x24, 0xB6, 0xFF }, { 0x24, 0xDA, 0xFF }, { 0x24, 0xFF, 0xFF }, 
134 { 0x48, 0x00, 0xFF }, { 0x48, 0x24, 0xFF }, { 0x48, 0x48, 0xFF }, { 0x48, 0x6D, 0xFF }, { 0x48, 0x91, 0xFF }, { 0x48, 0xB6, 0xFF }, { 0x48, 0xDA, 0xFF }, { 0x48, 0xFF, 0xFF }, 
135 { 0x6D, 0x00, 0xFF }, { 0x6D, 0x24, 0xFF }, { 0x6D, 0x48, 0xFF }, { 0x6D, 0x6D, 0xFF }, { 0x6D, 0x91, 0xFF }, { 0x6D, 0xB6, 0xFF }, { 0x6D, 0xDA, 0xFF }, { 0x6D, 0xFF, 0xFF }, 
136 { 0x91, 0x00, 0xFF }, { 0x91, 0x24, 0xFF }, { 0x91, 0x48, 0xFF }, { 0x91, 0x6D, 0xFF }, { 0x91, 0x91, 0xFF }, { 0x91, 0xB6, 0xFF }, { 0x91, 0xDA, 0xFF }, { 0x91, 0xFF, 0xFF }, 
137 { 0xB6, 0x00, 0xFF }, { 0xB6, 0x24, 0xFF }, { 0xB6, 0x48, 0xFF }, { 0xB6, 0x6D, 0xFF }, { 0xB6, 0x91, 0xFF }, { 0xB6, 0xB6, 0xFF }, { 0xB6, 0xDA, 0xFF }, { 0xB6, 0xFF, 0xFF }, 
138 { 0xDA, 0x00, 0xFF }, { 0xDA, 0x24, 0xFF }, { 0xDA, 0x48, 0xFF }, { 0xDA, 0x6D, 0xFF }, { 0xDA, 0x91, 0xFF }, { 0xDA, 0xB6, 0xFF }, { 0xDA, 0xDA, 0xFF }, { 0xDA, 0xFF, 0xFF }, 
139 { 0xFF, 0x00, 0xFF }, { 0xFF, 0x24, 0xFF }, { 0xFF, 0x48, 0xFF }, { 0xFF, 0x6D, 0xFF }, { 0xFF, 0x91, 0xFF }, { 0xFF, 0xB6, 0xFF }, { 0xFF, 0xDA, 0xFF }, { 0xFF, 0xFF, 0xFF } 
140}; tStaticAssert(tNumElements(tQuantizeFixed::Palette256) == 256); } 
141 
142// Generated fixed 128 colour palette. 
143namespace tQuantizeFixed { tColour3b Palette128[] = 
144{ 
145 { 0x00, 0x00, 0x00 }, { 0x00, 0x24, 0x00 }, { 0x00, 0x48, 0x00 }, { 0x00, 0x6D, 0x00 }, { 0x00, 0x91, 0x00 }, { 0x00, 0xB6, 0x00 }, { 0x00, 0xDA, 0x00 }, { 0x00, 0xFF, 0x00 }, 
146 { 0x55, 0x00, 0x00 }, { 0x55, 0x24, 0x00 }, { 0x55, 0x48, 0x00 }, { 0x55, 0x6D, 0x00 }, { 0x55, 0x91, 0x00 }, { 0x55, 0xB6, 0x00 }, { 0x55, 0xDA, 0x00 }, { 0x55, 0xFF, 0x00 }, 
147 { 0xAA, 0x00, 0x00 }, { 0xAA, 0x24, 0x00 }, { 0xAA, 0x48, 0x00 }, { 0xAA, 0x6D, 0x00 }, { 0xAA, 0x91, 0x00 }, { 0xAA, 0xB6, 0x00 }, { 0xAA, 0xDA, 0x00 }, { 0xAA, 0xFF, 0x00 }, 
148 { 0xFF, 0x00, 0x00 }, { 0xFF, 0x24, 0x00 }, { 0xFF, 0x48, 0x00 }, { 0xFF, 0x6D, 0x00 }, { 0xFF, 0x91, 0x00 }, { 0xFF, 0xB6, 0x00 }, { 0xFF, 0xDA, 0x00 }, { 0xFF, 0xFF, 0x00 }, 
149 { 0x00, 0x00, 0x55 }, { 0x00, 0x24, 0x55 }, { 0x00, 0x48, 0x55 }, { 0x00, 0x6D, 0x55 }, { 0x00, 0x91, 0x55 }, { 0x00, 0xB6, 0x55 }, { 0x00, 0xDA, 0x55 }, { 0x00, 0xFF, 0x55 }, 
150 { 0x55, 0x00, 0x55 }, { 0x55, 0x24, 0x55 }, { 0x55, 0x48, 0x55 }, { 0x55, 0x6D, 0x55 }, { 0x55, 0x91, 0x55 }, { 0x55, 0xB6, 0x55 }, { 0x55, 0xDA, 0x55 }, { 0x55, 0xFF, 0x55 }, 
151 { 0xAA, 0x00, 0x55 }, { 0xAA, 0x24, 0x55 }, { 0xAA, 0x48, 0x55 }, { 0xAA, 0x6D, 0x55 }, { 0xAA, 0x91, 0x55 }, { 0xAA, 0xB6, 0x55 }, { 0xAA, 0xDA, 0x55 }, { 0xAA, 0xFF, 0x55 }, 
152 { 0xFF, 0x00, 0x55 }, { 0xFF, 0x24, 0x55 }, { 0xFF, 0x48, 0x55 }, { 0xFF, 0x6D, 0x55 }, { 0xFF, 0x91, 0x55 }, { 0xFF, 0xB6, 0x55 }, { 0xFF, 0xDA, 0x55 }, { 0xFF, 0xFF, 0x55 }, 
153 { 0x00, 0x00, 0xAA }, { 0x00, 0x24, 0xAA }, { 0x00, 0x48, 0xAA }, { 0x00, 0x6D, 0xAA }, { 0x00, 0x91, 0xAA }, { 0x00, 0xB6, 0xAA }, { 0x00, 0xDA, 0xAA }, { 0x00, 0xFF, 0xAA }, 
154 { 0x55, 0x00, 0xAA }, { 0x55, 0x24, 0xAA }, { 0x55, 0x48, 0xAA }, { 0x55, 0x6D, 0xAA }, { 0x55, 0x91, 0xAA }, { 0x55, 0xB6, 0xAA }, { 0x55, 0xDA, 0xAA }, { 0x55, 0xFF, 0xAA }, 
155 { 0xAA, 0x00, 0xAA }, { 0xAA, 0x24, 0xAA }, { 0xAA, 0x48, 0xAA }, { 0xAA, 0x6D, 0xAA }, { 0xAA, 0x91, 0xAA }, { 0xAA, 0xB6, 0xAA }, { 0xAA, 0xDA, 0xAA }, { 0xAA, 0xFF, 0xAA }, 
156 { 0xFF, 0x00, 0xAA }, { 0xFF, 0x24, 0xAA }, { 0xFF, 0x48, 0xAA }, { 0xFF, 0x6D, 0xAA }, { 0xFF, 0x91, 0xAA }, { 0xFF, 0xB6, 0xAA }, { 0xFF, 0xDA, 0xAA }, { 0xFF, 0xFF, 0xAA }, 
157 { 0x00, 0x00, 0xFF }, { 0x00, 0x24, 0xFF }, { 0x00, 0x48, 0xFF }, { 0x00, 0x6D, 0xFF }, { 0x00, 0x91, 0xFF }, { 0x00, 0xB6, 0xFF }, { 0x00, 0xDA, 0xFF }, { 0x00, 0xFF, 0xFF }, 
158 { 0x55, 0x00, 0xFF }, { 0x55, 0x24, 0xFF }, { 0x55, 0x48, 0xFF }, { 0x55, 0x6D, 0xFF }, { 0x55, 0x91, 0xFF }, { 0x55, 0xB6, 0xFF }, { 0x55, 0xDA, 0xFF }, { 0x55, 0xFF, 0xFF }, 
159 { 0xAA, 0x00, 0xFF }, { 0xAA, 0x24, 0xFF }, { 0xAA, 0x48, 0xFF }, { 0xAA, 0x6D, 0xFF }, { 0xAA, 0x91, 0xFF }, { 0xAA, 0xB6, 0xFF }, { 0xAA, 0xDA, 0xFF }, { 0xAA, 0xFF, 0xFF }, 
160 { 0xFF, 0x00, 0xFF }, { 0xFF, 0x24, 0xFF }, { 0xFF, 0x48, 0xFF }, { 0xFF, 0x6D, 0xFF }, { 0xFF, 0x91, 0xFF }, { 0xFF, 0xB6, 0xFF }, { 0xFF, 0xDA, 0xFF }, { 0xFF, 0xFF, 0xFF } 
161}; tStaticAssert(tNumElements(tQuantizeFixed::Palette128) == 128); } 
162 
163// Generated fixed 64 colour palette. 
164namespace tQuantizeFixed { tColour3b Palette64[] = 
165{ 
166 { 0x00, 0x00, 0x00 }, { 0x00, 0x55, 0x00 }, { 0x00, 0xAA, 0x00 }, { 0x00, 0xFF, 0x00 }, { 0x55, 0x00, 0x00 }, { 0x55, 0x55, 0x00 }, { 0x55, 0xAA, 0x00 }, { 0x55, 0xFF, 0x00 }, 
167 { 0xAA, 0x00, 0x00 }, { 0xAA, 0x55, 0x00 }, { 0xAA, 0xAA, 0x00 }, { 0xAA, 0xFF, 0x00 }, { 0xFF, 0x00, 0x00 }, { 0xFF, 0x55, 0x00 }, { 0xFF, 0xAA, 0x00 }, { 0xFF, 0xFF, 0x00 }, 
168 { 0x00, 0x00, 0x55 }, { 0x00, 0x55, 0x55 }, { 0x00, 0xAA, 0x55 }, { 0x00, 0xFF, 0x55 }, { 0x55, 0x00, 0x55 }, { 0x55, 0x55, 0x55 }, { 0x55, 0xAA, 0x55 }, { 0x55, 0xFF, 0x55 }, 
169 { 0xAA, 0x00, 0x55 }, { 0xAA, 0x55, 0x55 }, { 0xAA, 0xAA, 0x55 }, { 0xAA, 0xFF, 0x55 }, { 0xFF, 0x00, 0x55 }, { 0xFF, 0x55, 0x55 }, { 0xFF, 0xAA, 0x55 }, { 0xFF, 0xFF, 0x55 }, 
170 { 0x00, 0x00, 0xAA }, { 0x00, 0x55, 0xAA }, { 0x00, 0xAA, 0xAA }, { 0x00, 0xFF, 0xAA }, { 0x55, 0x00, 0xAA }, { 0x55, 0x55, 0xAA }, { 0x55, 0xAA, 0xAA }, { 0x55, 0xFF, 0xAA }, 
171 { 0xAA, 0x00, 0xAA }, { 0xAA, 0x55, 0xAA }, { 0xAA, 0xAA, 0xAA }, { 0xAA, 0xFF, 0xAA }, { 0xFF, 0x00, 0xAA }, { 0xFF, 0x55, 0xAA }, { 0xFF, 0xAA, 0xAA }, { 0xFF, 0xFF, 0xAA }, 
172 { 0x00, 0x00, 0xFF }, { 0x00, 0x55, 0xFF }, { 0x00, 0xAA, 0xFF }, { 0x00, 0xFF, 0xFF }, { 0x55, 0x00, 0xFF }, { 0x55, 0x55, 0xFF }, { 0x55, 0xAA, 0xFF }, { 0x55, 0xFF, 0xFF }, 
173 { 0xAA, 0x00, 0xFF }, { 0xAA, 0x55, 0xFF }, { 0xAA, 0xAA, 0xFF }, { 0xAA, 0xFF, 0xFF }, { 0xFF, 0x00, 0xFF }, { 0xFF, 0x55, 0xFF }, { 0xFF, 0xAA, 0xFF }, { 0xFF, 0xFF, 0xFF } 
174}; tStaticAssert(tNumElements(tQuantizeFixed::Palette64) == 64); } 
175 
176// Generated fixed 32 colour palette. 
177namespace tQuantizeFixed { tColour3b Palette32[] = 
178{ 
179 { 0x00, 0x00, 0x00 }, { 0x00, 0x55, 0x00 }, { 0x00, 0xAA, 0x00 }, { 0x00, 0xFF, 0x00 }, { 0x55, 0x00, 0x00 }, { 0x55, 0x55, 0x00 }, { 0x55, 0xAA, 0x00 }, { 0x55, 0xFF, 0x00 }, 
180 { 0xAA, 0x00, 0x00 }, { 0xAA, 0x55, 0x00 }, { 0xAA, 0xAA, 0x00 }, { 0xAA, 0xFF, 0x00 }, { 0xFF, 0x00, 0x00 }, { 0xFF, 0x55, 0x00 }, { 0xFF, 0xAA, 0x00 }, { 0xFF, 0xFF, 0x00 }, 
181 { 0x00, 0x00, 0xFF }, { 0x00, 0x55, 0xFF }, { 0x00, 0xAA, 0xFF }, { 0x00, 0xFF, 0xFF }, { 0x55, 0x00, 0xFF }, { 0x55, 0x55, 0xFF }, { 0x55, 0xAA, 0xFF }, { 0x55, 0xFF, 0xFF }, 
182 { 0xAA, 0x00, 0xFF }, { 0xAA, 0x55, 0xFF }, { 0xAA, 0xAA, 0xFF }, { 0xAA, 0xFF, 0xFF }, { 0xFF, 0x00, 0xFF }, { 0xFF, 0x55, 0xFF }, { 0xFF, 0xAA, 0xFF }, { 0xFF, 0xFF, 0xFF } 
183}; tStaticAssert(tNumElements(tQuantizeFixed::Palette32) == 32); } 
184 
185// Generated fixed 16 colour palette. 
186namespace tQuantizeFixed { tColour3b Palette16[] = 
187{ 
188 { 0x00, 0x00, 0x00 }, { 0x00, 0x55, 0x00 }, { 0x00, 0xAA, 0x00 }, { 0x00, 0xFF, 0x00 }, { 0xFF, 0x00, 0x00 }, { 0xFF, 0x55, 0x00 }, { 0xFF, 0xAA, 0x00 }, { 0xFF, 0xFF, 0x00 }, 
189 { 0x00, 0x00, 0xFF }, { 0x00, 0x55, 0xFF }, { 0x00, 0xAA, 0xFF }, { 0x00, 0xFF, 0xFF }, { 0xFF, 0x00, 0xFF }, { 0xFF, 0x55, 0xFF }, { 0xFF, 0xAA, 0xFF }, { 0xFF, 0xFF, 0xFF } 
190}; tStaticAssert(tNumElements(tQuantizeFixed::Palette16) == 16); } 
191 
192// Generated fixed 8 colour palette. 
193namespace tQuantizeFixed { tColour3b Palette8[] = 
194{ 
195 { 0x00, 0x00, 0x00 }, { 0x00, 0xFF, 0x00 }, { 0xFF, 0x00, 0x00 }, { 0xFF, 0xFF, 0x00 }, { 0x00, 0x00, 0xFF }, { 0x00, 0xFF, 0xFF }, { 0xFF, 0x00, 0xFF }, { 0xFF, 0xFF, 0xFF } 
196}; tStaticAssert(tNumElements(tQuantizeFixed::Palette8) == 8); } 
197 
198// Generated fixed 4 colour palette. 
199namespace tQuantizeFixed { tColour3b Palette4[] = 
200{ 
201 { 0x00, 0x00, 0x00 }, { 0x00, 0xFF, 0x00 }, { 0xFF, 0x00, 0x00 }, { 0xFF, 0xFF, 0xFF } 
202}; tStaticAssert(tNumElements(tQuantizeFixed::Palette4) == 4); } 
203 
204// Generated fixed 2 colour palette. 
205namespace tQuantizeFixed { tColour3b Palette2[] = 
206{ 
207 { 0x00, 0x00, 0x00 }, { 0xFF, 0xFF, 0xFF } 
208}; tStaticAssert(tNumElements(tQuantizeFixed::Palette2) == 2); } 
209 
210 
211int tQuantizeFixed::FindIndexOfClosestColour_Redmean(const tColour3b* searchSpace, int searchSize, const tColour3b& colour) 
212{ 
213 float closest = 1000.0f; 
214 int closestIndex = -1; 
215 
216 for (int i = 0; i < searchSize; i++) 
217 { 
218 float diff = tMath::tColourDiffRedmean(a: colour, b: searchSpace[i]); 
219 if (diff < closest) 
220 { 
221 closest = diff; 
222 closestIndex = i; 
223 } 
224 } 
225 return closestIndex; 
226} 
227 
228 
229// 
230// The functions below make up the external interface. 
231// 
232 
233 
234bool tQuantizeFixed::QuantizeImage 
235( 
236 int numColours, int width, int height, const tPixel3b* pixels, tColour3b* destPalette, uint8* destIndices, 
237 bool checkExact 
238) 
239{ 
240 #ifdef QUANTIZE_GENERATE_FIXED_PALETTES 
241 static bool hasRun = false; 
242 if (!hasRun) 
243 { 
244 GenerateFixedPalettes("FixedPalettes.cpp"); 
245 hasRun = true; 
246 } 
247 return false; 
248 #endif 
249 
250 if ((numColours < 2) || (numColours > 256) || (width <= 0) || (height <= 0) || !pixels || !destPalette || !destIndices) 
251 return false; 
252 
253 if (checkExact) 
254 { 
255 bool success = tQuantize::QuantizeImageExact(numColours, width, height, pixels, destPalette, destIndices); 
256 if (success) 
257 return true; 
258 } 
259 
260 int tableSize = numColours; 
261 if (!tMath::tIsPower2(v: tableSize)) 
262 tableSize = tMath::tNextHigherPower2(v: tableSize); 
263 tAssert(tMath::tIsPower2(tableSize) && (tableSize >= 2) && (tableSize <= 256)); 
264 
265 bool skipIndexArray[256]; 
266 tStd::tMemset(dest: skipIndexArray, val: 0, numBytes: sizeof(skipIndexArray)); 
267 
268 // Skipping entries for non-power-of-two involves flipping from end to end (not including both ends). eg. 
269 // 
270 // 0 1 2 3 4 5 6 7 : Total 8. Worst case 5. Reduce by 3. 
271 // ^ 
272 // ^ 
273 // ^ 
274 // 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 : Total 16. Worst case 9. Reduce by 7. 
275 // ^ 
276 // ^ 
277 // ^ 
278 // ^ 
279 // ^ 
280 // ^ 
281 // ^ 
282 int numSkipped = 0; 
283 bool flipFlop = false; 
284 int skipIndexLow = 1; 
285 int skipIndexHigh = tableSize - 2; 
286 while (tableSize - numColours - numSkipped) 
287 { 
288 skipIndexArray[!flipFlop ? skipIndexLow : skipIndexHigh] = true; 
289 if (!flipFlop) skipIndexLow += 2; 
290 else skipIndexHigh -= 2; 
291 flipFlop = !flipFlop; 
292 numSkipped++; 
293 } 
294 
295 tColour3b* srcPalette = nullptr; 
296 switch (tableSize) 
297 { 
298 case 2: srcPalette = Palette2; break; 
299 case 4: srcPalette = Palette4; break; 
300 case 8: srcPalette = Palette8; break; 
301 case 16: srcPalette = Palette16; break; 
302 case 32: srcPalette = Palette32; break; 
303 case 64: srcPalette = Palette64; break; 
304 case 128: srcPalette = Palette128; break; 
305 case 256: srcPalette = Palette256; break; 
306 } 
307 
308 // Populate the dest palette, skipping as necessary. 
309 int destIndex = 0; 
310 for (int srcIndex = 0; srcIndex < tableSize; srcIndex++) 
311 { 
312 if (skipIndexArray[srcIndex]) 
313 continue; 
314 destPalette[destIndex++] = srcPalette[srcIndex]; 
315 } 
316 tAssert(destIndex == numColours); 
317 
318 // Exhaustive redmean search for each pixel colour. 
319 for (int y = 0; y < height; y++) 
320 { 
321 for (int x = 0; x < width; x++) 
322 { 
323 const tPixel3b& pixel = pixels[x + y*width]; 
324 destIndices[x + y*width] = FindIndexOfClosestColour_Redmean(searchSpace: destPalette, searchSize: numColours, colour: pixel); 
325 } 
326 } 
327 
328 return true; 
329} 
330 
331 
332bool tQuantizeFixed::QuantizeImage 
333( 
334 int numColours, int width, int height, const tPixel4b* pixels, tColour3b* destPalette, uint8* destIndices, 
335 bool checkExact 
336) 
337{ 
338 if ((numColours < 2) || (numColours > 256) || (width <= 0) || (height <= 0) || !pixels || !destPalette || !destIndices) 
339 return false; 
340 
341 tPixel3b* pixels3 = new tPixel3b[width*height]; 
342 for (int p = 0; p < width*height; p++) 
343 pixels3[p].Set( r: pixels[p].R, g: pixels[p].G, b: pixels[p].B ); 
344 
345 bool success = QuantizeImage(numColours, width, height, pixels: pixels3, destPalette, destIndices, checkExact); 
346 delete[] pixels3; 
347 return success; 
348} 
349 
350 
351} 
352