1 // ==========================================================
2 // LFPQuantizer class implementation
3 //
4 // Design and implementation by
5 // - Carsten Klein (cklein05@users.sourceforge.net)
6 //
7 // This file is part of FreeImage 3
8 //
9 // COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS, WITHOUT WARRANTY
10 // OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, WITHOUT LIMITATION, WARRANTIES
11 // THAT THE COVERED CODE IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE
12 // OR NON-INFRINGING. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE COVERED
13 // CODE IS WITH YOU. SHOULD ANY COVERED CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT
14 // THE INITIAL DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY NECESSARY
15 // SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF WARRANTY CONSTITUTES AN ESSENTIAL
16 // PART OF THIS LICENSE. NO USE OF ANY COVERED CODE IS AUTHORIZED HEREUNDER EXCEPT UNDER
17 // THIS DISCLAIMER.
18 //
19 // Use at your own risk!
20 // ==========================================================
21
22 #include "Quantizers.h"
23 #include "FreeImage.h"
24 #include "Utilities.h"
25
LFPQuantizer(unsigned PaletteSize)26 LFPQuantizer::LFPQuantizer(unsigned PaletteSize) :
27 m_size(0), m_limit(PaletteSize), m_index(0) {
28 m_map = new MapEntry[MAP_SIZE];
29 memset(m_map, 0xFF, MAP_SIZE * sizeof(MapEntry));
30 }
31
~LFPQuantizer()32 LFPQuantizer::~LFPQuantizer() {
33 delete[] m_map;
34 }
35
Quantize(FIBITMAP * dib,int ReserveSize,RGBQUAD * ReservePalette)36 FIBITMAP* LFPQuantizer::Quantize(FIBITMAP *dib, int ReserveSize, RGBQUAD *ReservePalette) {
37
38 if (ReserveSize > 0 && ReservePalette != NULL) {
39 AddReservePalette(ReservePalette, ReserveSize);
40 }
41
42 const unsigned width = FreeImage_GetWidth(dib);
43 const unsigned height = FreeImage_GetHeight(dib);
44
45 FIBITMAP *dib8 = FreeImage_Allocate(width, height, 8);
46 if (dib8 == NULL) {
47 return NULL;
48 }
49
50 const unsigned src_pitch = FreeImage_GetPitch(dib);
51 const unsigned dst_pitch = FreeImage_GetPitch(dib8);
52
53 const BYTE * const src_bits = FreeImage_GetBits(dib);
54 BYTE * const dst_bits = FreeImage_GetBits(dib8);
55
56 unsigned last_color = -1;
57 int last_index = 0;
58
59 if (FreeImage_GetBPP(dib) == 24) {
60
61 // Getting the source pixel as an unsigned int is much faster than
62 // working with FI_RGBA_xxx and shifting. However, this may fail
63 // for the very last pixel, since its rgbReserved member (alpha)
64 // may actually point to an address beyond the bitmap's memory. So,
65 // we do not process the last scanline in the first loop.
66
67 // Process all but the last scanline.
68 for (unsigned y = 0; y < height - 1; ++y) {
69 BYTE *dst_line = dst_bits + y * dst_pitch;
70 const BYTE *src_line = src_bits + y * src_pitch;
71 for (unsigned x = 0; x < width; ++x) {
72 const unsigned color = *((unsigned *) src_line) & 0x00FFFFFF;
73 if (color != last_color) {
74 last_color = color;
75 last_index = GetIndexForColor(color);
76 if (last_index == -1) {
77 FreeImage_Unload(dib8);
78 return NULL;
79 }
80 }
81 dst_line[x] = last_index;
82 src_line += 3;
83 }
84 }
85
86 // Process all but the last pixel of the last scanline.
87 BYTE *dst_line = dst_bits + (height - 1) * dst_pitch;
88 const BYTE *src_line = src_bits + (height - 1) * src_pitch;
89 for (unsigned x = 0; x < width - 1; ++x) {
90 const unsigned color = *((unsigned *) src_line) & 0x00FFFFFF;
91 if (color != last_color) {
92 last_color = color;
93 last_index = GetIndexForColor(color);
94 if (last_index == -1) {
95 FreeImage_Unload(dib8);
96 return NULL;
97 }
98 }
99 dst_line[x] = last_index;
100 src_line += 3;
101 }
102
103 // Process the last pixel (src_line should already point to it).
104 const unsigned color = 0 | src_line[FI_RGBA_BLUE] << FI_RGBA_BLUE_SHIFT
105 | src_line[FI_RGBA_GREEN] << FI_RGBA_GREEN_SHIFT
106 | src_line[FI_RGBA_RED] << FI_RGBA_RED_SHIFT;
107 if (color != last_color) {
108 last_color = color;
109 last_index = GetIndexForColor(color);
110 if (last_index == -1) {
111 FreeImage_Unload(dib8);
112 return NULL;
113 }
114 }
115 dst_line[width - 1] = last_index;
116
117 } else {
118 for (unsigned y = 0; y < height; ++y) {
119 BYTE *dst_line = dst_bits + y * dst_pitch;
120 const BYTE *src_line = src_bits + y * src_pitch;
121 for (unsigned x = 0; x < width; ++x) {
122 const unsigned color = *((unsigned *) src_line) & 0x00FFFFFF;
123 if (color != last_color) {
124 last_color = color;
125 last_index = GetIndexForColor(color);
126 if (last_index == -1) {
127 FreeImage_Unload(dib8);
128 return NULL;
129 }
130 }
131 dst_line[x] = last_index;
132 src_line += 4;
133 }
134 }
135 }
136
137 WritePalette(FreeImage_GetPalette(dib8));
138 return dib8;
139 }
140
141 /**
142 * Returns the palette index of the specified color. Tries to put the
143 * color into the map, if it's not already present in the map. In that
144 * case, a new index is used for the color. Returns -1, if adding the
145 * color would exceed the desired maximum number of colors in the
146 * palette.
147 * @param color the color to get the index from
148 * @return the palette index of the specified color or -1, if there
149 * is no space left in the palette
150 */
GetIndexForColor(unsigned color)151 inline int LFPQuantizer::GetIndexForColor(unsigned color) {
152 unsigned bucket = hash(color) & (MAP_SIZE - 1);
153 while (m_map[bucket].color != color) {
154 if (m_map[bucket].color == EMPTY_BUCKET) {
155 if (m_size == m_limit) {
156 return -1;
157 }
158 m_map[bucket].color = color;
159 m_map[bucket].index = m_index++;
160 ++m_size;
161 break;
162 }
163 bucket = (bucket + 1) % MAP_SIZE;
164 }
165 return m_map[bucket].index;
166 }
167
168 /**
169 * Adds the specified number of entries of the specified reserve
170 * palette to the newly created palette.
171 * @param *palette a pointer to the reserve palette to copy from
172 * @param size the number of entries to copy
173 */
AddReservePalette(const void * palette,unsigned size)174 void LFPQuantizer::AddReservePalette(const void *palette, unsigned size) {
175 if (size > MAX_SIZE) {
176 size = MAX_SIZE;
177 }
178 unsigned *ppal = (unsigned *) palette;
179 const unsigned offset = m_limit - size;
180 for (unsigned i = 0; i < size; ++i) {
181 const unsigned color = *ppal++;
182 const unsigned index = i + offset;
183 unsigned bucket = hash(color) & (MAP_SIZE - 1);
184 while((m_map[bucket].color != EMPTY_BUCKET) && (m_map[bucket].color != color)) {
185 bucket = (bucket + 1) % MAP_SIZE;
186 }
187 if(m_map[bucket].color != color) {
188 m_map[bucket].color = color;
189 m_map[bucket].index = index;
190 }
191 }
192 m_size += size;
193 }
194
195 /**
196 * Copies the newly created palette into the specified destination
197 * palette. Although unused palette entries are not overwritten in
198 * the destination palette, it is assumed to have space for at
199 * least 256 entries.
200 * @param palette a pointer to the destination palette
201 */
WritePalette(void * palette)202 void LFPQuantizer::WritePalette(void *palette) {
203 for (unsigned i = 0; i < MAP_SIZE; ++i) {
204 if (m_map[i].color != EMPTY_BUCKET) {
205 ((unsigned *) palette)[m_map[i].index] = m_map[i].color;
206 }
207 }
208 }
209