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