1 /*
2 * Copyright (c) 1996, 2000, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 /* Iterative color palette generation */
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30 #include <math.h>
31 #ifdef TIMES
32 #include <time.h>
33 #endif /* TIMES */
34
35 #ifndef MAKECUBE_EXE
36 #include "jvm.h"
37 #include "jni_util.h"
38
39 extern JavaVM *jvm;
40 #endif
41
42 #define jio_fprintf fprintf
43
44 #define TRUE 1
45 #define FALSE 0
46 static float monitor_gamma[3] = {2.6f, 2.6f, 2.4f}; /* r,g,b */
47 static float mat[3][3] = {
48 {0.3811f, 0.2073f, 0.0213f},
49 {0.3203f, 0.6805f, 0.1430f},
50 {0.2483f, 0.1122f, 1.2417f}
51 };
52 static float whiteXYZ[3] = { 0.9497f, 1.0000f, 1.4060f };
53 #define whitex (0.9497f / (0.9497f + 1.0000f + 1.4060f))
54 #define whitey (1.0000f / (0.9497f + 1.0000f + 1.4060f))
55 static float uwht = 4*whitex/(-2*whitex + 12*whitey + 3);
56 static float vwht = 9*whitey/(-2*whitex + 12*whitey + 3);
57
58 static float Rmat[3][256];
59 static float Gmat[3][256];
60 static float Bmat[3][256];
61 static float Ltab[256], Utab[256], Vtab[256];
62
63 typedef struct {
64 unsigned char red;
65 unsigned char green;
66 unsigned char blue;
67 unsigned char bestidx;
68 int nextidx;
69 float L, U, V;
70 float dist;
71 float dE;
72 float dL;
73 } CmapEntry;
74
75 static int num_virt_cmap_entries;
76 static CmapEntry *virt_cmap;
77 static int prevtest[256];
78 static int nexttest[256];
79
80 static float Lscale = 10.0f;
81 /* this is a multiplier--it should not be zero */
82 static float Weight = 250.0f;
83
84 #define WEIGHT_DIST(d,l) (Weight*(d)/(Weight+(l)))
85 #define UNWEIGHT_DIST(d,l) ((Weight+(l))*(d)/Weight)
86
87 #if 0
88 #define WEIGHT_DIST(d,l) (d)
89 #define UNWEIGHT_DIST(d,l) (d)
90 #endif
91
92 static void
93 init_matrices()
94 {
95 static int done = 0;
96 int i;
97
98 if (done) {
99 return;
100 }
101 for (i = 0; i < 256; ++i)
102 {
103 float iG = (float) pow(i/255.0, monitor_gamma[0]);
104 Rmat[0][i] = mat[0][0] * iG;
105 Rmat[1][i] = mat[0][1] * iG;
106 Rmat[2][i] = mat[0][2] * iG;
107
108 iG = (float) pow(i/255.0, monitor_gamma[1]);
109 Gmat[0][i] = mat[1][0] * iG;
110 Gmat[1][i] = mat[1][1] * iG;
111 Gmat[2][i] = mat[1][2] * iG;
112
113 iG = (float) pow(i/255.0, monitor_gamma[2]);
114 Bmat[0][i] = mat[2][0] * iG;
115 Bmat[1][i] = mat[2][1] * iG;
116 Bmat[2][i] = mat[2][2] * iG;
117 }
118 done = 1;
119 }
120
121 static void
122 LUV_convert(int red, int grn, int blu, float *L, float *u, float *v)
123 {
124 float X = Rmat[0][red] + Gmat[0][grn] + Bmat[0][blu];
125 float Y = Rmat[1][red] + Gmat[1][grn] + Bmat[1][blu];
126 float Z = Rmat[2][red] + Gmat[2][grn] + Bmat[2][blu];
127 float sum = X+Y+Z;
128
129 if (sum != 0.0f) {
130 float x = X/sum;
131 float y = Y/sum;
132 float dnm = -2*x + 12*y + 3;
133 float ytmp = (float) pow(Y/whiteXYZ[1], 1.0/3.0);
134
135 if (ytmp < .206893f) {
136 *L = 903.3f*Y/whiteXYZ[1];
137 } else {
138 *L = 116*(ytmp) - 16;
139 }
140 if (dnm != 0.0f) {
141 float uprm = 4*x/dnm;
142 float vprm = 9*y/dnm;
143
144 *u = 13*(*L)*(uprm-uwht);
145 *v = 13*(*L)*(vprm-vwht);
146 } else {
147 *u = 0.0f;
148 *v = 0.0f;
149 }
150 } else {
151 *L = 0.0f;
152 *u = 0.0f;
153 *v = 0.0f;
154 }
155 }
156
157 static int cmapmax;
158 static int total;
159 static unsigned char cmap_r[256], cmap_g[256], cmap_b[256];
160
161 #define DIST_THRESHOLD 7
162 static int
163 no_close_color(float l, float u, float v, int c_tot, int exact) {
164 int i;
165 for (i = 0; i < c_tot; ++i) {
166 float t, dist = 0.0f;
167 t = Ltab[i] - l; dist += t*t*Lscale;
168 t = Utab[i] - u; dist += t*t;
169 t = Vtab[i] - v; dist += t*t;
170
171 if (dist < (exact ? 0.1 : DIST_THRESHOLD))
172 return 0;
173 }
174
175 return 1;
176 }
177
178 static int
179 add_color(int r, int g, int b, int f) {
180 if (total >= cmapmax)
181 return 0;
182 cmap_r[total] = r;
183 cmap_g[total] = g;
184 cmap_b[total] = b;
185 LUV_convert(cmap_r[total],cmap_g[total],cmap_b[total],
186 Ltab + total, Utab + total, Vtab + total);
187 if (no_close_color(Ltab[total], Utab[total], Vtab[total], total-1, f)) {
188 ++total;
189 return 1;
190 } else {
191 return 0;
192 }
193 }
194
195 static void
196 init_primaries() {
197 int r, g, b;
198
199 for (r = 0; r < 256; r += (r?128:127)) {
200 for (g = 0; g < 256; g += (g?128:127)) {
201 for (b = 0; b < 256; b += (b?128:127)) {
202 if ((r == g) && (g == b)) continue; /* black or white */
203 add_color(r, g, b, TRUE);
204 }
205 }
206 }
207 }
208
209 static void
210 init_pastels() {
211 int i;
212 /* very light colors */
213 for (i = 6; i >= 0; --i)
214 add_color((i&4) ? 0xff : 0xf0,
215 (i&2) ? 0xff : 0xf0,
216 (i&1) ? 0xff : 0xf0, TRUE);
217 }
218
219 static void
220 init_grays() {
221 int i;
222 for (i = 15; i < 255; i += 16)
223 add_color(i, i, i, TRUE);
224 }
225
226 static void
227 init_mac_palette() {
228 add_color(255, 255, 204, TRUE);
229 add_color(255, 255, 0, TRUE);
230 add_color(255, 204, 153, TRUE);
231 add_color(255, 102, 204, TRUE);
232 add_color(255, 102, 51, TRUE);
233 add_color(221, 0, 0, TRUE);
234 add_color(204, 204, 255, TRUE);
235 add_color(204, 153, 102, TRUE);
236 add_color(153, 255, 255, TRUE);
237 add_color(153, 153, 255, TRUE);
238 add_color(153, 102, 153, TRUE);
239 add_color(153, 0, 102, TRUE);
240 add_color(102, 102, 204, TRUE);
241 add_color(51, 255, 153, TRUE);
242 add_color(51, 153, 102, TRUE);
243 add_color(51, 102, 102, TRUE);
244 add_color(51, 51, 102, TRUE);
245 add_color(51, 0, 153, TRUE);
246 add_color(0, 187, 0, TRUE);
247 add_color(0, 153, 255, TRUE);
248 add_color(0, 0, 221, TRUE);
249 }
250
251 static void
252 init_virt_cmap(int tablesize, int testsize)
253 {
254 int r, g, b;
255 int gray = -1;
256 CmapEntry *pCmap;
257 unsigned int dotest[256];
258
259 if (virt_cmap) {
260 free(virt_cmap);
261 virt_cmap = 0;
262 }
263
264 num_virt_cmap_entries = tablesize * tablesize * tablesize;
265 virt_cmap = malloc(sizeof(CmapEntry) * num_virt_cmap_entries);
266 /*
267 * Fix for bug 4070647 malloc return value not check in img_colors.c
268 * We have to handle the malloc failure differently under
269 * Win32 and Solaris since under Solaris this file is linked with
270 * libawt.so and under Win32 it's a separate awt_makecube.exe
271 * application.
272 */
273 if (virt_cmap == NULL) {
274 #ifndef MAKECUBE_EXE
275 JNIEnv *env = (JNIEnv *)JNU_GetEnv(jvm, JNI_VERSION_1_2);
276 JNU_ThrowOutOfMemoryError(env, "init_virt_cmap: OutOfMemoryError");
277 return;
278 #else
279 fprintf(stderr,"init_virt_cmap: OutOfMemoryError\n");
280 exit(-1);
281 #endif
282 }
283 pCmap = virt_cmap;
284 for (r = 0; r < total; r++) {
285 if (cmap_r[r] == cmap_g[r] && cmap_g[r] == cmap_b[r]) {
286 if (gray < 0 || cmap_r[gray] < cmap_r[r]) {
287 gray = r;
288 }
289 }
290 }
291 if (gray < 0) {
292 #ifdef DEBUG
293 jio_fprintf(stderr, "Didn't find any grays in color table!\n");
294 #endif /* DEBUG */
295 gray = 0;
296 }
297 g = 0;
298 b = 0;
299 for (r = 0; r < tablesize - 1; ++r) {
300 if (g >= 0) {
301 b = r;
302 dotest[r] = 1;
303 g -= tablesize;
304 } else {
305 dotest[r] = 0;
306 }
307 prevtest[r] = b;
308 g += testsize;
309 }
310 b = r;
311 prevtest[r] = b;
312 dotest[r] = 1;
313 for (r = tablesize - 1; r >= 0; --r) {
314 if (prevtest[r] == r) {
315 b = r;
316 }
317 nexttest[r] = b;
318 }
319 #ifdef DEBUG
320 for (r = 0; r < tablesize; ++r) {
321 if (dotest[r]) {
322 if (prevtest[r] != r || nexttest[r] != r) {
323 jio_fprintf(stderr, "prev/next != r!\n");
324 }
325 }
326 }
327 #endif /* DEBUG */
328 for (r = 0; r < tablesize; ++r)
329 {
330 int red = (int)(floor(r*255.0/(tablesize - 1)));
331 for (g = 0; g < tablesize; ++g)
332 {
333 int green = (int)(floor(g*255.0/(tablesize - 1)));
334 for (b = 0; b < tablesize; ++b)
335 {
336 int blue = (int)(floor(b*255.0/(tablesize - 1)));
337 float t, d;
338 if (pCmap >= virt_cmap + num_virt_cmap_entries) {
339 #ifdef DEBUG
340 jio_fprintf(stderr, "OUT OF pCmap CONVERSION SPACE!\n");
341 #endif /* DEBUG */
342 continue; /* Shouldn't happen */
343 }
344 pCmap->red = red;
345 pCmap->green = green;
346 pCmap->blue = blue;
347 LUV_convert(red, green, blue, &pCmap->L, &pCmap->U, &pCmap->V);
348 if ((red != green || green != blue) &&
349 (!dotest[r] || !dotest[g] || !dotest[b]))
350 {
351 pCmap->nextidx = -1;
352 pCmap++;
353 continue;
354 }
355 pCmap->bestidx = gray;
356 pCmap->nextidx = 0;
357 t = Ltab[gray] - pCmap->L;
358 d = t * t;
359 if (red == green && green == blue) {
360 pCmap->dist = d;
361 d *= Lscale;
362 } else {
363 d *= Lscale;
364 t = Utab[gray] - pCmap->U;
365 d += t * t;
366 t = Vtab[gray] - pCmap->V;
367 d += t * t;
368 pCmap->dist = d;
369 }
370 pCmap->dE = WEIGHT_DIST(d, pCmap->L);
371 pCmap++;
372 }
373 }
374 }
375 #ifdef DEBUG
376 if (pCmap < virt_cmap + num_virt_cmap_entries) {
377 jio_fprintf(stderr, "Didn't fill pCmap conversion table!\n");
378 }
379 #endif /* DEBUG */
380 }
381
382 static int
383 find_nearest(CmapEntry *pCmap) {
384 int red = pCmap->red;
385 int grn = pCmap->green;
386 int blu = pCmap->blue;
387 float L = pCmap->L;
388 float dist;
389 int i;
390
391 if ((red == grn) && (grn == blu)) {
392 dist = pCmap->dist;
393
394 for (i = pCmap->nextidx; i < total; ++i) {
395 float dL;
396
397 if (cmap_r[i] != cmap_g[i] || cmap_g[i] != cmap_b[i]) {
398 continue;
399 }
400
401 dL = Ltab[i] - L; dL *= dL;
402
403 if (dL < dist) {
404 dist = dL;
405 pCmap->dist = dist;
406 pCmap->dL = dist;
407 pCmap->dE = WEIGHT_DIST(dist*Lscale,L);
408 pCmap->bestidx = i;
409 }
410 }
411 pCmap->nextidx = total;
412 } else {
413 float U = pCmap->U;
414 float V = pCmap->V;
415 dist = pCmap->dist;
416
417 for (i = pCmap->nextidx; i < total; ++i) {
418 float dL, dU, dV, dE;
419 dL = Ltab[i] - L; dL *= (dL*Lscale);
420 dU = Utab[i] - U; dU *= dU;
421 dV = Vtab[i] - V; dV *= dV;
422
423 dE = dL + dU + dV;
424 if (dE < dist)
425 {
426 dist = dE;
427 /* *delta = (dL/4) + dU + dV; */
428 /* *delta = dist */
429 /* *delta = dL + 100*(dU+dV)/(100+L); */
430 pCmap->dist = dist;
431 pCmap->dE = WEIGHT_DIST(dE, L);
432 pCmap->dL = dL/Lscale;
433 pCmap->bestidx = i;
434 }
435 }
436 pCmap->nextidx = total;
437 }
438
439 return pCmap->bestidx;
440 }
441
442 #define MAX_OFFENDERS 32
443 static CmapEntry *offenders[MAX_OFFENDERS + 1];
444 static int num_offenders;
445
446 static void
447 insert_in_list(CmapEntry *pCmap)
448 {
449 int i;
450 float dE = pCmap->dE;
451
452 for (i = num_offenders; i > 0; --i) {
453 if (dE < offenders[i-1]->dE) break;
454 offenders[i] = offenders[i-1];
455 }
456
457 offenders[i] = pCmap;
458 if (num_offenders < MAX_OFFENDERS) ++num_offenders;
459 }
460
461 static void
462 handle_biggest_offenders(int testtblsize, int maxcolors) {
463 int i, j;
464 float dEthresh = 0;
465 CmapEntry *pCmap;
466
467 num_offenders = 0;
468
469 for (pCmap = virt_cmap, i = 0; i < num_virt_cmap_entries; i++, pCmap++) {
470 if (pCmap->nextidx < 0) {
471 continue;
472 }
473 if (num_offenders == MAX_OFFENDERS
474 && pCmap->dE < offenders[MAX_OFFENDERS-1]->dE)
475 {
476 continue;
477 }
478 find_nearest(pCmap);
479 insert_in_list(pCmap);
480 }
481
482 if (num_offenders > 0) {
483 dEthresh = offenders[num_offenders-1]->dE;
484 }
485
486 for (i = 0; (total < maxcolors) && (i < num_offenders); ++i) {
487 pCmap = offenders[i];
488
489 if (!pCmap) continue;
490
491 j = add_color(pCmap->red, pCmap->green, pCmap->blue, FALSE);
492
493 if (j) {
494 for (j = i+1; j < num_offenders; ++j) {
495 float dE;
496
497 pCmap = offenders[j];
498 if (!pCmap) {
499 continue;
500 }
501
502 find_nearest(pCmap);
503
504 dE = pCmap->dE;
505 if (dE < dEthresh) {
506 offenders[j] = 0;
507 } else {
508 if (offenders[i+1] == 0 || dE > offenders[i+1]->dE) {
509 offenders[j] = offenders[i+1];
510 offenders[i+1] = pCmap;
511 }
512 }
513 }
514 }
515 }
516 }
517
518 void
519 img_makePalette(int cmapsize, int tablesize, int lookupsize,
520 float lscale, float weight,
521 int prevclrs, int doMac,
522 unsigned char *reds,
523 unsigned char *greens,
524 unsigned char *blues,
525 unsigned char *lookup)
526 {
527 CmapEntry *pCmap;
528 int i, ix;
529 #ifdef STATS
530 double ave_dL, ave_dE;
531 double max_dL, max_dE;
532 #endif /* STATS */
533 #ifdef TIMES
534 clock_t start, mid, tbl, end;
535
536 start = clock();
537 #endif /* TIMES */
538
539 init_matrices();
540 Lscale = lscale;
541 Weight = weight;
542
543 cmapmax = cmapsize;
544 total = 0;
545 for (i = 0; i < prevclrs; i++) {
546 add_color(reds[i], greens[i], blues[i], TRUE);
547 }
548
549 add_color(0, 0, 0, TRUE);
550 add_color(255,255,255, TRUE);
551
552 /* do grays next; otherwise find_nearest may break! */
553 init_grays();
554 if (doMac) {
555 init_mac_palette();
556 }
557 init_pastels();
558
559 init_primaries();
560
561 /* special case some blues */
562 add_color(0,0,192,TRUE);
563 add_color(0x30,0x20,0x80,TRUE);
564 add_color(0x20,0x60,0xc0,TRUE);
565
566 init_virt_cmap(lookupsize, tablesize);
567
568 while (total < cmapsize) {
569 handle_biggest_offenders(tablesize, cmapsize);
570 }
571
572 memcpy(reds, cmap_r, cmapsize);
573 memcpy(greens, cmap_g, cmapsize);
574 memcpy(blues, cmap_b, cmapsize);
575
576 #ifdef TIMES
577 mid = clock();
578 #endif /* TIMES */
579
580 pCmap = virt_cmap;
581 for (i = 0; i < num_virt_cmap_entries; i++, pCmap++) {
582 if (pCmap->nextidx < 0) {
583 continue;
584 }
585 if (pCmap->nextidx < total) {
586 ix = find_nearest(pCmap);
587 }
588 }
589
590 #ifdef TIMES
591 tbl = clock();
592 #endif /* TIMES */
593
594 pCmap = virt_cmap;
595 if (tablesize != lookupsize) {
596 int r, g, b;
597 for (r = 0; r < lookupsize; ++r)
598 {
599 for (g = 0; g < lookupsize; ++g)
600 {
601 for (b = 0; b < lookupsize; ++b, pCmap++)
602 {
603 float L, U, V;
604 float bestd = 0;
605 CmapEntry *pTest;
606
607 if (pCmap->nextidx >= 0) {
608 continue;
609 }
610 #ifdef DEBUG
611 if (r == g && g == b) {
612 jio_fprintf(stderr, "GRAY VALUE!?\n");
613 }
614 #endif /* DEBUG */
615 L = pCmap->L;
616 U = pCmap->U;
617 V = pCmap->V;
618 for (i = 0; i < 8; i++) {
619 int ri, gi, bi;
620 float d, t;
621 ri = (i & 1) ? prevtest[r] : nexttest[r];
622 gi = (i & 2) ? prevtest[g] : nexttest[g];
623 bi = (i & 4) ? prevtest[b] : nexttest[b];
624 pTest = &virt_cmap[((ri * lookupsize)
625 + gi) * lookupsize
626 + bi];
627 #ifdef DEBUG
628 if (pTest->nextidx < 0) {
629 jio_fprintf(stderr, "OOPS!\n");
630 }
631 #endif /* DEBUG */
632 ix = pTest->bestidx;
633 t = Ltab[ix] - L; d = t * t * Lscale;
634 if (i != 0 && d > bestd) continue;
635 t = Utab[ix] - U; d += t * t;
636 if (i != 0 && d > bestd) continue;
637 t = Vtab[ix] - V; d += t * t;
638 if (i != 0 && d > bestd) continue;
639 bestd = d;
640 pCmap->bestidx = ix;
641 }
642 }
643 }
644 }
645 }
646 pCmap = virt_cmap;
647 for (i = 0; i < num_virt_cmap_entries; i++) {
648 *lookup++ = (pCmap++)->bestidx;
649 }
650
651 #ifdef TIMES
652 end = clock();
653 #endif /* TIMES */
654
655 #ifdef STATS
656 max_dL = 0.0;
657 max_dE = 0.0;
658 ave_dL = 0.0;
659 ave_dE = 0.0;
660
661 pCmap = virt_cmap;
662 for (i = 0; i < num_virt_cmap_entries; i++, pCmap++) {
663 double t, dL, dU, dV, dE;
664 if (pCmap->nextidx < 0) {
665 int ix = pCmap->bestidx;
666 dL = pCmap->L - Ltab[ix]; dL *= dL;
667 dU = pCmap->U - Utab[ix]; dU *= dU;
668 dV = pCmap->V - Vtab[ix]; dV *= dV;
669 dE = dL * Lscale + dU + dV;
670 dE = WEIGHT_DIST(dE, pCmap->L);
671 } else {
672 dL = pCmap->dL;
673 dE = pCmap->dE;
674 }
675
676 if (dL > max_dL) max_dL = dL;
677 t = UNWEIGHT_DIST(dE,dL) - dL*(Lscale-1);
678 if (t > max_dE) max_dE = t;
679
680 ave_dL += (dL > 0) ? sqrt(dL) : 0.0;
681 ave_dE += (t > 0) ? sqrt(t) : 0.0;
682 }
683
684 jio_fprintf(stderr, "colors=%d, tablesize=%d, cubesize=%d, ",
685 cmapsize, tablesize, lookupsize);
686 jio_fprintf(stderr, "Lscale=%5.3f, Weight=%5.3f mac=%s\n",
687 (double)lscale, (double)weight, doMac ? "true" : "false");
688 jio_fprintf(stderr, "Worst case error dL = %5.3f, dE = %5.3f\n",
689 sqrt(max_dL), sqrt(max_dE));
690 jio_fprintf(stderr, "Average error dL = %5.3f, dE = %5.3f\n",
691 ave_dL / num_virt_cmap_entries, ave_dE / num_virt_cmap_entries);
692 #endif /* STATS */
693 #ifdef TIMES
694 jio_fprintf(stderr, "%f seconds to find colors\n",
695 (double)(mid - start) / CLOCKS_PER_SEC);
696 jio_fprintf(stderr, "%f seconds to finish nearest colors\n",
697 (double)(tbl - mid) / CLOCKS_PER_SEC);
698 jio_fprintf(stderr, "%f seconds to make lookup table\n",
699 (double)(end - tbl) / CLOCKS_PER_SEC);
700 jio_fprintf(stderr, "%f seconds total\n",
701 (double)(end - start) / CLOCKS_PER_SEC);
702 #endif /* TIMES */
703
704 free(virt_cmap);
705 virt_cmap = 0;
706 }