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