1 /*
2 This file is Copyright © 1994-1995 Olivier Montanuy,
3 Copyright © 1999-2005 André Majorel,
4 Copyright © 2006-2019 contributors to the DeuTex project.
5
6 DeuTex incorporates code derived from DEU 5.21 that was put in the
7 public domain in 1994 by Raphaël Quinet and Brendon Wyber.
8
9 SPDX-License-Identifier: GPL-2.0-or-later
10 */
11
12 #include "deutex.h"
13 #include "tools.h"
14 #include "color.h"
15
16 /*
17 ** hash table
18 **
19 */
20 uint8_t COLindex(uint8_t R, uint8_t G, uint8_t B, uint8_t index);
21 static uint8_t COLpalMatch(uint8_t R, uint8_t G, uint8_t B);
22
23 static struct PIXEL *COLpal; /* The game palette (comes from PLAYPAL) */
24 static struct PIXEL *COLpalAlt = NULL; /* Alternate palette (TITLEPAL) */
25 static struct PIXEL COLinv;
26 static uint8_t COLinvisib;
27 static bool COLok = false;
28
29 /*
30 * pixel_cmp
31 * Compare two PIXEL structures à la memcmp()
32 */
pixel_cmp(const void * pixel1,const void * pixel2)33 static int pixel_cmp(const void *pixel1, const void *pixel2)
34 {
35 const struct PIXEL *const p1 = (const struct PIXEL *) pixel1;
36 const struct PIXEL *const p2 = (const struct PIXEL *) pixel2;
37 if (p1->R != p2->R)
38 return p1->R - p2->R;
39 if (p1->G != p2->G)
40 return p1->G - p2->G;
41 if (p1->B != p2->B)
42 return p1->B - p2->B;
43 return 0;
44
45 }
46
47 const int COLsame = 3;
48
49 /*
50 * COLdiff - compute the distance between two colours
51 *
52 * Return a number between 0 (closest) and 24384 (farthest).
53 */
COLdiff(uint8_t R,uint8_t G,uint8_t B,uint8_t idx)54 int16_t COLdiff(uint8_t R, uint8_t G, uint8_t B, uint8_t idx)
55 {
56 register struct PIXEL *pixel = &COLpal[(int16_t) (idx & 0xFF)];
57 register int16_t d; /*signed */
58 register int16_t e = 0;
59 d = (((int16_t) R) & 0xFF) - (((int16_t) pixel->R) & 0xFF);
60 d >>= 1;
61 e += d * d;
62 d = (((int16_t) G) & 0xFF) - (((int16_t) pixel->G) & 0xFF);
63 d >>= 1;
64 e += d * d;
65 d = (((int16_t) B) & 0xFF) - (((int16_t) pixel->B) & 0xFF);
66 d >>= 1;
67 e += d * d;
68 if (e < 0)
69 return 0x7FFF;
70 return e;
71 }
72
COLpalMatch(uint8_t R,uint8_t G,uint8_t B)73 static uint8_t COLpalMatch(uint8_t R, uint8_t G, uint8_t B)
74 {
75 int16_t i, test, min = 0x7FFF;
76 uint8_t idxmin = '\0';
77 if (!COLok)
78 Bug("PL24", "COLok");
79 for (i = 0; i < 256; i++) {
80 if ((uint8_t) i != COLinvisib) {
81 test = COLdiff(R, G, B, (uint8_t) i);
82 if (test < min) {
83 min = test;
84 idxmin = (uint8_t) i;
85 }
86 if (min < COLsame) {
87 break;
88 }
89 }
90 }
91 return idxmin;
92 }
93
94 /* Choose only 10,11...16 */
95 #define POWER 12
96 const int16_t HashP2 = POWER; /* 10=1024 */
97 const int16_t HashSz = 1 << POWER; /* 1<< HashP2 */
98 const int16_t HashMask = (1 << POWER) - 1; /* HashSz-1 */
99 /*const int16_t HashStop = -1;*/
100 static uint8_t *COLhash; /*hash table */
101 /*static int16_t *COLnext;*/
102
Hash(uint8_t r,uint8_t g,uint8_t b)103 int16_t Hash(uint8_t r, uint8_t g, uint8_t b)
104 {
105 int res;
106 uint8_t R = r & 0xFC, G = g & 0xFC, B = b & 0xFC;
107 res = (((R << 3) ^ G) << 2) ^ B;
108 res = (res << 3) + (R & 0xC3) + (G & 0x61) + (~B & 0x98);
109 res = (res << 5) + (R & 0x3B) + (~G & 0x95) + (B & 0x33);
110 res ^= res >> 8;
111 res &= HashMask;
112 return (int16_t) res;
113 }
114
115 /*original colors*/
COLputColHash(int16_t index,uint8_t R,uint8_t G,uint8_t B)116 static void COLputColHash(int16_t index, uint8_t R, uint8_t G, uint8_t B)
117 {
118 int16_t count, idx, nextidx;
119 idx = Hash(R, G, B);
120 for (count = 0; count < 8; count++) {
121 nextidx = (idx + count) & HashMask;
122 if (COLhash[nextidx] == COLinvisib) {
123 COLhash[nextidx] = (uint8_t) (index & 0xFF);
124 return;
125 }
126 }
127 Bug("PL07", "Can't hash Doom pal");
128 }
129
130 /*new colors, with matching*/
COLgetIndexHash(uint8_t R,uint8_t G,uint8_t B)131 static uint8_t COLgetIndexHash(uint8_t R, uint8_t G, uint8_t B)
132 {
133 int16_t idx, nextidx, count;
134 uint8_t res;
135 idx = Hash(R, G, B);
136 for (count = 0; count < 8; count++) {
137 nextidx = (idx + count) & HashMask;
138 res = COLhash[nextidx];
139 if (res == COLinvisib) { /*free */
140 COLhash[nextidx] = res = COLpalMatch(R, G, B);
141 return res;
142 } else if (COLdiff(R, G, B, res) < COLsame) {
143 return res;
144 }
145 }
146 /*no good solution. slow match */
147 return COLpalMatch(R, G, B);
148 }
149
150 /*
151 * Normal palette (PLAYPAL)
152 */
COLinit(uint8_t invR,uint8_t invG,uint8_t invB,char * Colors,int16_t Colsz,const char * pathname,const char * lumpname)153 void COLinit(uint8_t invR, uint8_t invG, uint8_t invB, char *Colors,
154 int16_t Colsz, const char *pathname, const char *lumpname)
155 {
156 int16_t i;
157 const char *name = NULL;
158 /*int16_t R,G,B; */
159 if (COLok)
160 Bug("PL02", "COLok");
161 if (Colsz < 256 * sizeof(struct PIXEL)) {
162 if (lumpname == NULL) {
163 ProgError("PL03", "%s: wrong size for PLAYPAL",
164 fname(pathname));
165 } else {
166 ProgError("PL04", "%s: %s: wrong size for PLAYPAL",
167 fname(pathname), lump_name(lumpname));
168 }
169 }
170 COLok = true;
171 COLpal = (struct PIXEL *) Malloc(256 * sizeof(struct PIXEL));
172 for (i = 0; i < NCOLOURS; i++) {
173 COLpal[i].R = Colors[i * 3 + 0];
174 COLpal[i].G = Colors[i * 3 + 1];
175 COLpal[i].B = Colors[i * 3 + 2];
176 }
177 if (COLpal[0].R == 0 && COLpal[0].G == 0 && COLpal[0].B == 0
178 && COLpal[0xf7].R == 0 && COLpal[0xf7].G == 0
179 && COLpal[0xf7].B == 0) {
180 i = 0xf7;
181 name = "Doom";
182 } else if (COLpal[35].R == 255 && COLpal[35].G == 255
183 && COLpal[35].B == 255 && COLpal[255].R == 255
184 && COLpal[255].G == 255 && COLpal[255].B == 255) {
185 i = 0xff;
186 name = "Heretic";
187 } else if (COLpal[33].R == 29 && COLpal[33].G == 32
188 && COLpal[33].B == 29 && COLpal[255].R == 255
189 && COLpal[255].G == 255 && COLpal[255].B == 255) {
190 i = 0xff;
191 name = "Hexen";
192 } else if (COLpal[0].R == 0 && COLpal[0].G == 0 && COLpal[0].B == 0
193 && COLpal[240].R == 0 && COLpal[240].G == 0
194 && COLpal[240].B == 0) {
195 i = 0xf0;
196 name = "Strife";
197 } else {
198 i = 0xff;
199 name = NULL;
200 }
201 /*
202 ** correction to doom palette
203 */
204 COLinvisib = (uint8_t) (i & 0xFF);
205 Info("PL05", "Palette is %s", name ? name : "(unknown)");
206 if (name == NULL) {
207 Warning("PL06",
208 "Unknown palette, using colour 0xff as transparent colour");
209 Warning("PL06", "Some graphics may appear moth-eaten");
210 }
211 COLinv.R = COLpal[i].R = invR;
212 COLinv.G = COLpal[i].G = invG;
213 COLinv.B = COLpal[i].B = invB;
214
215 /* Init hash table.
216 We take special care of hashing only unique RGB triplets.
217 This precaution is unnecessary for Doom, Heretic, Hexen
218 and Strife but Doom alpha O.2, 0.4 and 0.5 have a PLAYPAL
219 that contains many duplicates that would fill the hash
220 table with useless data. */
221 {
222 struct PIXEL *unique = Malloc(NCOLOURS * sizeof *unique);
223 for (i = 0; i < NCOLOURS; i++)
224 unique[i] = COLpal[i];
225 qsort(unique, NCOLOURS, sizeof *unique, pixel_cmp);
226 COLhash = (uint8_t *) Malloc(HashSz);
227 Memset(COLhash, COLinvisib, HashSz); /*clear hash table */
228 for (i = 0; i < NCOLOURS; i++) {
229 if ((uint8_t) i != COLinvisib
230 && (i == 0 || pixel_cmp(unique + i, unique + i - 1) != 0))
231 COLputColHash(i, unique[i].R, unique[i].G, unique[i].B);
232 }
233 free(unique);
234 }
235 }
236
COLfree(void)237 void COLfree(void)
238 {
239 if (!COLok)
240 Bug("PL99", "COLok");
241 COLok = false;
242 free(COLpal);
243 free(COLhash);
244 if (COLpalAlt != NULL)
245 free(COLpalAlt);
246 }
247
COLinvisible(void)248 uint8_t COLinvisible(void)
249 {
250 if (!COLok)
251 Bug("PL27", "COLok");
252 return COLinvisib;
253 }
254
COLdoomPalet(void)255 struct PIXEL *COLdoomPalet(void)
256 {
257 if (!COLok)
258 Bug("PL20", "COLok");
259 return COLpal;
260 }
261
COLindex(uint8_t R,uint8_t G,uint8_t B,uint8_t index)262 uint8_t COLindex(uint8_t R, uint8_t G, uint8_t B, uint8_t index)
263 {
264 int16_t i;
265 if (!COLok)
266 Bug("PL23", "COLok");
267 /*check for invisible color */
268 if (R == COLinv.R && G == COLinv.G && B == COLinv.B)
269 return COLinvisib;
270 /*check for DOOM palette */
271 i = ((int16_t) index) & 0xFF;
272 if (R == COLpal[i].R)
273 if (G == COLpal[i].G)
274 if (B == COLpal[i].B)
275 return index;
276 /*else, check hash palette */
277 i = (int16_t) COLgetIndexHash(R, G, B);
278 return (uint8_t) i;
279 }
280
281 /*
282 * Alternate palette (TITLEPAL)
283 */
284 static char *titlepal_data = NULL;
285 static size_t titlepal_size = 0;
286
COLinitAlt(char * _titlepal_data,int32_t _titlepal_size)287 void COLinitAlt(char *_titlepal_data, int32_t _titlepal_size)
288 {
289 titlepal_data = _titlepal_data;
290 titlepal_size = _titlepal_size;
291 }
292
COLaltPalet(void)293 struct PIXEL *COLaltPalet(void)
294 {
295 if (COLpalAlt != NULL)
296 return COLpalAlt;
297
298 /* What follows is done only once : */
299 if (titlepal_data == NULL) {
300 int n;
301
302 Warning("PL11", "TITLEPAL not found, using PLAYPAL instead");
303 COLpalAlt = (struct PIXEL *) Malloc(NCOLOURS * sizeof *COLpalAlt);
304 for (n = 0; n < NCOLOURS; n++)
305 COLpalAlt[n] = COLpal[n];
306 } else {
307 struct PIXEL *p;
308 struct PIXEL *pmax;
309 const unsigned char *d = (const unsigned char *) titlepal_data;
310 const unsigned char *dmax = d + titlepal_size;
311
312 if (titlepal_size < 3 * NCOLOURS)
313 Warning("PL13", "TITLEPAL too short (%ld), filling with black",
314 (long) titlepal_size);
315 COLpalAlt = (struct PIXEL *) Malloc(NCOLOURS * sizeof *COLpalAlt);
316 /* Copy the contents of TITLEPAL into COLpalAlt */
317 for (p = COLpalAlt, pmax = p + NCOLOURS; p < pmax; p++) {
318 p->R = d < dmax ? *d++ : 0;
319 p->G = d < dmax ? *d++ : 0;
320 p->B = d < dmax ? *d++ : 0;
321 }
322 free(titlepal_data);
323 titlepal_data = NULL; /* Paranoia */
324 }
325
326 return COLpalAlt;
327 }
328