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