1 # include "bitmapConfig.h"
2
3 # include "bmRender.h"
4 # include <string.h>
5 # include <stdlib.h>
6 # include <appDebugon.h>
7
8 /************************************************************************/
9 /* */
10 /* Color reduction. */
11 /* */
12 /************************************************************************/
13
14 # define LOG_CUTS 0
15 # define LOG_PALETTE 0
16
17 typedef struct HistogramEntry
18 {
19 int heCount;
20 RGB8Color heColor;
21 } HistogramEntry;
22
23 # define heRed heColor.rgb8Red
24 # define heGreen heColor.rgb8Green
25 # define heBlue heColor.rgb8Blue
26
27 typedef struct HashBucket
28 {
29 HistogramEntry hbHistogramEntry;
30 int hbNumber;
31 struct HashBucket * hbNext;
32 } HashBucket;
33
34 # define hbCount hbHistogramEntry.heCount
35 # define hbRed hbHistogramEntry.heColor.rgb8Red
36 # define hbGreen hbHistogramEntry.heColor.rgb8Green
37 # define hbBlue hbHistogramEntry.heColor.rgb8Blue
38
39 typedef struct ColorBox
40 {
41 int cbHistogramOffset;
42 int cbColorCount;
43 int cbPixelCount;
44 int cbCutNumber;
45
46 int cbRMin;
47 int cbRMax;
48 int cbGMin;
49 int cbGMax;
50 int cbBMin;
51 int cbBMax;
52 } ColorBox;
53
54 typedef struct CutNode
55 {
56 unsigned int cnLeft;
57 unsigned int cnRight;
58 unsigned char cnLeftMaximum;
59 unsigned char cnComponent;
60 } CutNode;
61
62 # define CN_LEAF 0
63 # define CN_RED 1
64 # define CN_GREEN 2
65 # define CN_BLUE 3
66
67 typedef struct ColorReducer
68 {
69 HashBucket ** crHashTable;
70 HistogramEntry * crHistogram;
71 const ColorPalette * crPalette; /* Borrowed from target */
72 CutNode * crCutNodes;
73 int crColorsCounted;
74 } ColorReducer;
75
76 /************************************************************************/
77 /* */
78 /* Color hash varia. */
79 /* */
80 /************************************************************************/
81
82 #define HASH_SIZE 6553
83
84 #define ppm_hash(r,g,b) ((( (int) (r) * 33023 + \
85 (int) (g) * 30013 + \
86 (int) (b) * 27011 ) & 0x7fffffff) % HASH_SIZE )
87
bmFreeColorHash(HashBucket ** hashTable)88 static void bmFreeColorHash( HashBucket ** hashTable )
89 {
90 int i;
91
92 for ( i= 0; i < HASH_SIZE; i++ )
93 {
94 HashBucket * hashBucket= hashTable[i];
95
96 while( hashBucket )
97 {
98 HashBucket * nx= hashBucket->hbNext;
99 free( (char *)hashBucket );
100 hashBucket= nx;
101 }
102 }
103
104 return;
105 }
106
107 /************************************************************************/
108 /* */
109 /* Insert a new hash item: Convenience routine. */
110 /* */
111 /************************************************************************/
112
bmInsertHash(HashBucket ** hashTable,int hash,int number,int r,int g,int b)113 static int bmInsertHash( HashBucket ** hashTable,
114 int hash,
115 int number,
116 int r,
117 int g,
118 int b )
119 {
120 HashBucket * hashBucket= (HashBucket *)malloc( sizeof(HashBucket) );
121
122 if ( ! hashBucket )
123 { XDEB(hashBucket); return -1; }
124
125 hashBucket->hbNext= hashTable[hash];
126 hashTable[hash]= hashBucket;
127
128 hashBucket->hbCount= 1;
129 hashBucket->hbNumber= number;
130
131 hashBucket->hbRed= r;
132 hashBucket->hbGreen= g;
133 hashBucket->hbBlue= b;
134
135 return 0;
136 }
137
138 /************************************************************************/
139 /* */
140 /* Utility functions: Manage a color reducer. */
141 /* */
142 /************************************************************************/
143
bmInitColorReducer(ColorReducer * cr)144 static void bmInitColorReducer( ColorReducer * cr )
145 {
146 cr->crHashTable= (HashBucket **)0;
147 cr->crHistogram= (HistogramEntry *)0;
148 cr->crPalette= (ColorPalette *)0;
149 cr->crCutNodes= (CutNode *)0;
150
151 return;
152 }
153
bmCleanColorReducer(ColorReducer * cr)154 static void bmCleanColorReducer( ColorReducer * cr )
155 {
156 if ( cr->crHistogram )
157 { free( cr->crHistogram ); }
158 if ( cr->crCutNodes )
159 { free( cr->crCutNodes ); }
160 if ( cr->crHashTable )
161 { bmFreeColorHash( cr->crHashTable ); }
162
163 return;
164 }
165
bmAllocateCutNodes(ColorReducer * cr,int colorCount)166 static int bmAllocateCutNodes( ColorReducer * cr,
167 int colorCount )
168 {
169 CutNode * fresh;
170
171 fresh= (CutNode *)realloc( cr->crCutNodes, 2* colorCount* sizeof(CutNode) );
172 if ( ! fresh )
173 { LLDEB(colorCount,fresh); return -1; }
174
175 cr->crCutNodes= fresh;
176 memset( cr->crCutNodes, 0, 2* colorCount* sizeof(CutNode) );
177
178 return 0;
179 }
180
bmAllocateHistogram(ColorReducer * cr,int colorCount)181 static int bmAllocateHistogram( ColorReducer * cr,
182 int colorCount )
183 {
184 HistogramEntry * fresh;
185
186 fresh= (HistogramEntry *)realloc( cr->crHistogram,
187 colorCount* sizeof(HistogramEntry) );
188 if ( ! fresh )
189 { LLDEB(colorCount,fresh); return -1; }
190
191 cr->crHistogram= fresh;
192
193 return 0;
194 }
195
196 /************************************************************************/
197 /* */
198 /* Determine median. */
199 /* */
200 /************************************************************************/
201
bmHistRedMedian(int * pPixelCount,int * pColorCount,int pixelCount,HistogramEntry * histogram,int colorCount,unsigned int cMin,unsigned int cMax)202 static int bmHistRedMedian( int * pPixelCount,
203 int * pColorCount,
204 int pixelCount,
205 HistogramEntry * histogram,
206 int colorCount,
207 unsigned int cMin,
208 unsigned int cMax )
209 {
210 int cMed;
211
212 int lt= 0;
213 int eq= 0;
214 int gt= 0;
215
216 cMax++;
217
218 cMed= ( cMin+ cMax )/ 2;
219 for (;;)
220 {
221 int i;
222 const HistogramEntry * he;
223
224 lt= 0; eq= 0; gt= 0;
225
226 he= histogram;
227 for ( i= 0; i < colorCount; he++, i++ )
228 {
229 if ( he->heRed > cMed )
230 { gt += he->heCount; continue; }
231 if ( he->heRed < cMed )
232 { lt += he->heCount; continue; }
233
234 eq += he->heCount; continue;
235 }
236
237 if ( lt+ eq < pixelCount/ 2 )
238 {
239 cMin= cMed;
240 cMed= ( cMin+ cMax )/ 2;
241 continue;
242 }
243
244 if ( eq+ gt < pixelCount/ 2 )
245 {
246 cMax= cMed;
247 cMed= ( cMin+ cMax )/ 2;
248 continue;
249 }
250
251 break;
252 }
253
254 if ( lt+ eq < eq+ gt )
255 { pixelCount= lt+ eq; }
256 else{ cMed--; pixelCount= lt; }
257
258 lt= 0; gt= colorCount- 1;
259 while( gt > lt )
260 {
261 while( gt > lt && histogram[lt].heColor.rgb8Red <= cMed )
262 { lt++; }
263 while( gt > lt && histogram[gt].heColor.rgb8Red > cMed )
264 { gt--; }
265
266 if ( gt > lt )
267 {
268 HistogramEntry swap;
269
270 swap= histogram[lt];
271 histogram[lt]= histogram[gt];
272 histogram[gt]= swap;
273 }
274 }
275
276 while( lt < colorCount && histogram[lt].heColor.rgb8Red <= cMed )
277 { lt++; }
278
279 *pPixelCount= pixelCount; *pColorCount= lt; return cMed;
280 }
281
bmHistGreenMedian(int * pPixelCount,int * pColorCount,int pixelCount,HistogramEntry * histogram,int colorCount,unsigned int cMin,unsigned int cMax)282 static int bmHistGreenMedian( int * pPixelCount,
283 int * pColorCount,
284 int pixelCount,
285 HistogramEntry * histogram,
286 int colorCount,
287 unsigned int cMin,
288 unsigned int cMax )
289 {
290 int cMed;
291
292 int lt= 0;
293 int eq= 0;
294 int gt= 0;
295
296 cMax++;
297
298 cMed= ( cMin+ cMax )/ 2;
299 for (;;)
300 {
301 int i;
302 const HistogramEntry * he;
303
304 lt= 0; eq= 0; gt= 0;
305
306 he= histogram;
307 for ( i= 0; i < colorCount; he++, i++ )
308 {
309 if ( he->heGreen > cMed )
310 { gt += he->heCount; continue; }
311 if ( he->heGreen < cMed )
312 { lt += he->heCount; continue; }
313
314 eq += he->heCount; continue;
315 }
316
317 if ( lt+ eq < pixelCount/ 2 )
318 {
319 cMin= cMed;
320 cMed= ( cMin+ cMax )/ 2;
321 continue;
322 }
323
324 if ( eq+ gt < pixelCount/ 2 )
325 {
326 cMax= cMed;
327 cMed= ( cMin+ cMax )/ 2;
328 continue;
329 }
330
331 break;
332 }
333
334 if ( lt+ eq < eq+ gt )
335 { pixelCount= lt+ eq; }
336 else{ cMed--; pixelCount= lt; }
337
338 lt= 0; gt= colorCount- 1;
339 while( gt > lt )
340 {
341 while( gt > lt && histogram[lt].heColor.rgb8Green <= cMed )
342 { lt++; }
343 while( gt > lt && histogram[gt].heColor.rgb8Green > cMed )
344 { gt--; }
345
346 if ( gt > lt )
347 {
348 HistogramEntry swap;
349
350 swap= histogram[lt];
351 histogram[lt]= histogram[gt];
352 histogram[gt]= swap;
353 }
354 }
355
356 while( lt < colorCount && histogram[lt].heColor.rgb8Green <= cMed )
357 { lt++; }
358
359 *pPixelCount= pixelCount; *pColorCount= lt; return cMed;
360 }
361
bmHistBlueMedian(int * pPixelCount,int * pColorCount,int pixelCount,HistogramEntry * histogram,int colorCount,unsigned int cMin,unsigned int cMax)362 static int bmHistBlueMedian( int * pPixelCount,
363 int * pColorCount,
364 int pixelCount,
365 HistogramEntry * histogram,
366 int colorCount,
367 unsigned int cMin,
368 unsigned int cMax )
369 {
370 int cMed;
371
372 int lt= 0;
373 int eq= 0;
374 int gt= 0;
375
376 cMax++;
377
378
379 cMed= ( cMin+ cMax )/ 2;
380 for (;;)
381 {
382 int i;
383 const HistogramEntry * he;
384
385 lt= 0; eq= 0; gt= 0;
386
387 he= histogram;
388 for ( i= 0; i < colorCount; he++, i++ )
389 {
390 if ( he->heBlue > cMed )
391 { gt += he->heCount; continue; }
392 if ( he->heBlue < cMed )
393 { lt += he->heCount; continue; }
394
395 eq += he->heCount; continue;
396 }
397
398 if ( lt+ eq < pixelCount/ 2 )
399 {
400 cMin= cMed;
401 cMed= ( cMin+ cMax )/ 2;
402 continue;
403 }
404
405 if ( eq+ gt < pixelCount/ 2 )
406 {
407 cMax= cMed;
408 cMed= ( cMin+ cMax )/ 2;
409 continue;
410 }
411
412 break;
413 }
414
415 if ( lt+ eq < eq+ gt )
416 { pixelCount= lt+ eq; }
417 else{ cMed--; pixelCount= lt; }
418
419 lt= 0; gt= colorCount- 1;
420 while( gt > lt )
421 {
422 while( gt > lt && histogram[lt].heColor.rgb8Blue <= cMed )
423 { lt++; }
424 while( gt > lt && histogram[gt].heColor.rgb8Blue > cMed )
425 { gt--; }
426
427 if ( gt > lt )
428 {
429 HistogramEntry swap;
430
431 swap= histogram[lt];
432 histogram[lt]= histogram[gt];
433 histogram[gt]= swap;
434 }
435 }
436
437 while( lt < colorCount && histogram[lt].heColor.rgb8Blue <= cMed )
438 { lt++; }
439
440 *pPixelCount= pixelCount; *pColorCount= lt; return cMed;
441 }
442
443 /************************************************************************/
444 /* */
445 /* Determine the range of the colors in a box. */
446 /* */
447 /************************************************************************/
448
bmDelimitColorBox(ColorBox * cb,const HistogramEntry * histogram)449 static void bmDelimitColorBox( ColorBox * cb,
450 const HistogramEntry * histogram )
451 {
452 const HistogramEntry * he;
453 int i;
454
455 if ( cb->cbColorCount == 0 )
456 { LDEB(cb->cbColorCount); return; }
457
458 he= histogram+ cb->cbHistogramOffset;
459 cb->cbRMin= cb->cbRMax= he->heRed;
460 cb->cbGMin= cb->cbGMax= he->heGreen;
461 cb->cbBMin= cb->cbBMax= he->heBlue;
462
463 he++;
464
465 for ( i= 1; i < cb->cbColorCount; he++, i++ )
466 {
467 if ( cb->cbRMin > he->heRed )
468 { cb->cbRMin= he->heRed; }
469 if ( cb->cbRMax < he->heRed )
470 { cb->cbRMax= he->heRed; }
471
472 if ( cb->cbGMin > he->heGreen )
473 { cb->cbGMin= he->heGreen; }
474 if ( cb->cbGMax < he->heGreen )
475 { cb->cbGMax= he->heGreen; }
476
477 if ( cb->cbBMin > he->heBlue )
478 { cb->cbBMin= he->heBlue; }
479 if ( cb->cbBMax < he->heBlue )
480 { cb->cbBMax= he->heBlue; }
481 }
482
483 return;
484 }
485
486 /************************************************************************/
487 /* */
488 /* Find the median for splitting a box. */
489 /* */
490 /************************************************************************/
491
bmSplitBox(HistogramEntry * histogram,const ColorBox * cbParent,ColorBox * cbLow,ColorBox * cbHigh,int * pLeftMaximum,int * pComponent)492 static void bmSplitBox( HistogramEntry * histogram,
493 const ColorBox * cbParent,
494 ColorBox * cbLow,
495 ColorBox * cbHigh,
496 int * pLeftMaximum,
497 int * pComponent )
498 {
499 int rDif= cbParent->cbRMax- cbParent->cbRMin;
500 int gDif= cbParent->cbGMax- cbParent->cbGMin;
501 int bDif= cbParent->cbBMax- cbParent->cbBMin;
502
503 histogram += cbParent->cbHistogramOffset;
504
505 *cbLow= *cbParent;
506 *cbHigh= *cbParent;
507
508 if ( 77* rDif > 150* gDif && 77* rDif > 29* bDif )
509 {
510 cbLow->cbRMax= bmHistRedMedian( &(cbLow->cbPixelCount),
511 &(cbLow->cbColorCount),
512 cbParent->cbPixelCount, histogram,
513 cbParent->cbColorCount,
514 cbParent->cbRMin, cbParent->cbRMax );
515
516 cbHigh->cbRMin= cbLow->cbRMax+ 1;
517 cbHigh->cbColorCount= cbParent->cbColorCount- cbLow->cbColorCount;
518 cbHigh->cbPixelCount= cbParent->cbPixelCount- cbLow->cbPixelCount;
519 cbHigh->cbHistogramOffset= cbParent->cbHistogramOffset+
520 cbLow->cbColorCount;
521 *pLeftMaximum= cbLow->cbRMax;
522 *pComponent= CN_RED;
523
524 # if LOG_CUTS
525 appDebug( "CUT RED at %3d..%3d..%3d "
526 "%4d+ %4d= %4dC %6d+ %6d= %6dP\n",
527 cbParent->cbRMin, cbLow->cbRMax, cbParent->cbRMax,
528 cbLow->cbColorCount, cbHigh->cbColorCount,
529 cbParent->cbColorCount,
530 cbLow->cbPixelCount, cbHigh->cbPixelCount,
531 cbParent->cbPixelCount );
532 # endif
533 }
534 else{
535 if ( 150* gDif > 29* bDif )
536 {
537 cbLow->cbGMax= bmHistGreenMedian( &(cbLow->cbPixelCount),
538 &(cbLow->cbColorCount),
539 cbParent->cbPixelCount, histogram,
540 cbParent->cbColorCount,
541 cbParent->cbGMin, cbParent->cbGMax );
542 cbHigh->cbGMin= cbLow->cbGMax+ 1;
543 cbHigh->cbColorCount= cbParent->cbColorCount- cbLow->cbColorCount;
544 cbHigh->cbPixelCount= cbParent->cbPixelCount- cbLow->cbPixelCount;
545 cbHigh->cbHistogramOffset= cbParent->cbHistogramOffset+
546 cbLow->cbColorCount;
547 *pLeftMaximum= cbLow->cbGMax;
548 *pComponent= CN_GREEN;
549
550 # if LOG_CUTS
551 appDebug( "CUT GREEN at %3d..%3d..%3d "
552 "%4d+ %4d= %4dC %6d+ %6d= %6dP\n",
553 cbParent->cbGMin, cbLow->cbGMax, cbParent->cbGMax,
554 cbLow->cbColorCount, cbHigh->cbColorCount,
555 cbParent->cbColorCount,
556 cbLow->cbPixelCount, cbHigh->cbPixelCount,
557 cbParent->cbPixelCount );
558 # endif
559 }
560 else{
561 cbLow->cbBMax= bmHistBlueMedian( &(cbLow->cbPixelCount),
562 &(cbLow->cbColorCount),
563 cbParent->cbPixelCount, histogram,
564 cbParent->cbColorCount,
565 cbParent->cbBMin, cbParent->cbBMax );
566
567 cbHigh->cbBMin= cbLow->cbBMax+ 1;
568 cbHigh->cbColorCount= cbParent->cbColorCount- cbLow->cbColorCount;
569 cbHigh->cbPixelCount= cbParent->cbPixelCount- cbLow->cbPixelCount;
570 cbHigh->cbHistogramOffset= cbParent->cbHistogramOffset+
571 cbLow->cbColorCount;
572 *pLeftMaximum= cbLow->cbBMax;
573 *pComponent= CN_BLUE;
574
575 # if LOG_CUTS
576 appDebug( "CUT BLUE at %3d..%3d..%3d "
577 "%4d+ %4d= %4dC %6d+ %6d= %6dP\n",
578 cbParent->cbBMin, cbLow->cbBMax, cbParent->cbBMax,
579 cbLow->cbColorCount, cbHigh->cbColorCount,
580 cbParent->cbColorCount,
581 cbLow->cbPixelCount, cbHigh->cbPixelCount,
582 cbParent->cbPixelCount );
583 # endif
584 }
585 }
586
587 return;
588 }
589
590 /************************************************************************/
591 /* */
592 /* Find a collection of colors using 'median cut'. */
593 /* */
594 /************************************************************************/
595
bmFindCuts(ColorBox * boxes,CutNode * nodes,HistogramEntry * histo,int colorCount,int pixelCount,int maxcolors)596 static int bmFindCuts( ColorBox * boxes,
597 CutNode * nodes,
598 HistogramEntry * histo,
599 int colorCount,
600 int pixelCount,
601 int maxcolors )
602 {
603 int i;
604 int boxCount;
605 int nodeCount= 0;
606
607 boxes[0].cbHistogramOffset= 0;
608 boxes[0].cbColorCount= colorCount;
609 boxes[0].cbPixelCount= pixelCount;
610 boxes[0].cbCutNumber= 0;
611 boxCount= 1;
612
613 nodes[0].cnComponent= CN_LEAF;
614 nodes[0].cnLeftMaximum= 0; /* Irrelevant ! */
615 nodes[0].cnLeft= 0; /* Both to this color. */
616 nodes[0].cnRight= 0; /* Both to this color. */
617 nodeCount= 1;
618
619 while( boxCount < maxcolors )
620 {
621 int biggestBox;
622 int leftMaximum;
623 int cutComponent;
624
625 ColorBox cbSplit;
626
627 for ( i= 0; i < boxCount; i++ )
628 {
629 if ( boxes[i].cbColorCount > 1 )
630 { break; }
631 }
632 if ( i >= boxCount )
633 { /* LLDEB(i,boxCount); */ break; }
634 biggestBox= i;
635 for ( i= biggestBox+ 1; i < boxCount; i++ )
636 {
637 if ( boxes[i].cbColorCount > 1 &&
638 boxes[i].cbPixelCount > boxes[biggestBox].cbPixelCount )
639 { biggestBox= i; }
640 }
641
642 bmDelimitColorBox( boxes+ biggestBox, histo );
643
644 cbSplit= boxes[biggestBox];
645 bmSplitBox( histo,
646 &cbSplit, boxes+ biggestBox, boxes+ boxCount,
647 &leftMaximum, &cutComponent );
648
649 /****************/
650 /* Cut Nodes */
651 /****************/
652 i= cbSplit.cbCutNumber;
653 nodes[i].cnComponent= cutComponent;
654 nodes[i].cnLeftMaximum= leftMaximum;
655 nodes[i].cnLeft= nodeCount;
656 nodes[i].cnRight= nodeCount+ 1;
657
658 nodes[nodeCount].cnComponent= CN_LEAF;
659 nodes[nodeCount].cnLeftMaximum= 0;
660 nodes[nodeCount].cnLeft= biggestBox;
661 nodes[nodeCount].cnRight= biggestBox;
662
663 nodes[nodeCount+1].cnComponent= CN_LEAF;
664 nodes[nodeCount+1].cnLeftMaximum= 0;
665 nodes[nodeCount+1].cnLeft= boxCount;
666 nodes[nodeCount+1].cnRight= boxCount;
667
668 /****************/
669 /* Boxes */
670 /****************/
671 boxes[biggestBox].cbCutNumber= nodeCount;
672 boxes[boxCount].cbCutNumber= nodeCount+ 1;
673
674 nodeCount += 2; boxCount++;
675 }
676
677 return boxCount;
678 }
679
bmFindColors(ColorReducer * cr,int colorCount,int pixelCount,int maxcolors)680 static int bmFindColors( ColorReducer * cr,
681 int colorCount,
682 int pixelCount,
683 int maxcolors )
684 {
685 ColorBox * boxes;
686 const ColorBox * cb;
687 int i;
688 int j;
689 int boxCount;
690
691 boxes= (ColorBox *)malloc( maxcolors* sizeof(ColorBox) );
692 if ( ! boxes )
693 { LLDEB(maxcolors,boxes); return -1; }
694
695 boxCount= bmFindCuts( boxes, cr->crCutNodes, cr->crHistogram,
696 colorCount, pixelCount, maxcolors );
697
698 cb= boxes;
699 for ( i= 0; i < boxCount; cb++, i++ )
700 {
701 long sR= 0;
702 long sG= 0;
703 long sB= 0;
704 long N= 0;
705
706 HistogramEntry * he= cr->crHistogram+ cb->cbHistogramOffset;
707
708 for ( j= 0; j < boxes[i].cbColorCount; j++, he++ )
709 {
710 sR += he->heCount* he->heRed;
711 sG += he->heCount* he->heGreen;
712 sB += he->heCount* he->heBlue;
713 N += he->heCount;
714 }
715
716 if ( N == 0 )
717 {
718 LDEB(N);
719 cr->crPalette->cpColors[i].rgb8Red= 0;
720 cr->crPalette->cpColors[i].rgb8Green= 0;
721 cr->crPalette->cpColors[i].rgb8Blue= 0;
722 }
723 else{
724 cr->crPalette->cpColors[i].rgb8Red= sR/ N;
725 cr->crPalette->cpColors[i].rgb8Green= sG/ N;
726 cr->crPalette->cpColors[i].rgb8Blue= sB/ N;
727 }
728
729 # if LOG_PALETTE
730 appDebug( "BOX %3d: "
731 "R %3d..%3d..%3d "
732 "G %3d..%3d..%3d "
733 "B %3d..%3d..%3d "
734 "%4dC %6ldP\n",
735
736 i,
737 cb->cbRMin, cr->crPalette[i].rgb8Red, cb->cbRMax,
738 cb->cbGMin, cr->crPalette[i].rgb8Green, cb->cbGMax,
739 cb->cbBMin, cr->crPalette[i].rgb8Blue, cb->cbBMax,
740 boxes[i].cbColorCount, N );
741 # endif
742 }
743
744 free( boxes );
745
746 return boxCount;
747 }
748
749 /************************************************************************/
750 /* */
751 /* Various translation routines. */
752 /* */
753 /************************************************************************/
754
bmReduceAllocateColorCut(AllocatorColor * ac,ColorAllocator * ca,unsigned int r,unsigned int g,unsigned int b)755 static int bmReduceAllocateColorCut( AllocatorColor * ac,
756 ColorAllocator * ca,
757 unsigned int r,
758 unsigned int g,
759 unsigned int b )
760 {
761 ColorReducer * cr= (ColorReducer *)ca->caSystemPrivate;
762 const CutNode * cn= cr->crCutNodes;
763 int i;
764
765 i= 0;
766 for (;;)
767 {
768 switch( cn[i].cnComponent )
769 {
770 case CN_RED:
771 if ( r <= cn[i].cnLeftMaximum )
772 { i= cn[i].cnLeft; }
773 else{ i= cn[i].cnRight; }
774 continue;
775
776 case CN_GREEN:
777 if ( g <= cn[i].cnLeftMaximum )
778 { i= cn[i].cnLeft; }
779 else{ i= cn[i].cnRight; }
780 continue;
781
782 case CN_BLUE:
783 if ( b <= cn[i].cnLeftMaximum )
784 { i= cn[i].cnLeft; }
785 else{ i= cn[i].cnRight; }
786 continue;
787
788 case CN_LEAF:
789 i= cn[i].cnLeft;
790
791 ac->acRed= 257* cr->crPalette->cpColors[i].rgb8Red;
792 ac->acGreen= 257* cr->crPalette->cpColors[i].rgb8Green;
793 ac->acBlue= 257* cr->crPalette->cpColors[i].rgb8Blue;
794 ac->acColorNumber= i;
795 return 0;
796
797 default:
798 LDEB(cn[i].cnComponent); return -1;
799 }
800 }
801 }
802
bmReduceAllocateColorHash(AllocatorColor * ac,ColorAllocator * ca,unsigned int r,unsigned int g,unsigned int b)803 static int bmReduceAllocateColorHash( AllocatorColor * ac,
804 ColorAllocator * ca,
805 unsigned int r,
806 unsigned int g,
807 unsigned int b )
808 {
809 ColorReducer * cr= (ColorReducer *)ca->caSystemPrivate;
810 int hash;
811 HashBucket * hashBucket;
812 int i;
813
814 hash= ppm_hash( r, g, b );
815 hashBucket= cr->crHashTable[hash];
816 while( hashBucket )
817 {
818 if ( hashBucket->hbRed == r &&
819 hashBucket->hbGreen == g &&
820 hashBucket->hbBlue == b )
821 { break; }
822
823 hashBucket= hashBucket->hbNext;
824 }
825
826 if ( ! hashBucket )
827 { XDEB(hashBucket); i= 0; }
828 else{ i= hashBucket->hbNumber; }
829
830 ac->acRed= 257* cr->crPalette->cpColors[i].rgb8Red;
831 ac->acGreen= 257* cr->crPalette->cpColors[i].rgb8Green;
832 ac->acBlue= 257* cr->crPalette->cpColors[i].rgb8Blue;
833 ac->acColorNumber= i;
834
835 return 0;
836 }
837
bmReduceCleanupAllocator(ColorAllocator * ca)838 static void bmReduceCleanupAllocator( ColorAllocator * ca )
839 {
840 ColorReducer * cr= (ColorReducer *)ca->caSystemPrivate;
841
842 if ( cr )
843 {
844 bmCleanColorReducer( cr );
845 free( cr );
846 }
847
848 return;
849 }
850
851 /************************************************************************/
852 /* */
853 /* Hash the colors in a 24 bit image. Do not return more than a */
854 /* given number of colors. */
855 /* */
856 /* 1) Make a hash table for the colors. */
857 /* */
858 /************************************************************************/
859
bmHashColorsRGB8(HashBucket *** pHashTable,int * pColorCount,int pixelsHigh,int pixelsWide,int bytesPerRow,int hasAlpha,const unsigned char * bufIn,int maxcolors,unsigned int mask)860 static int bmHashColorsRGB8( HashBucket *** pHashTable,
861 int * pColorCount,
862 int pixelsHigh,
863 int pixelsWide,
864 int bytesPerRow,
865 int hasAlpha,
866 const unsigned char * bufIn,
867 int maxcolors,
868 unsigned int mask )
869 {
870 unsigned int r;
871 unsigned int g;
872 unsigned int b;
873
874 int row;
875 int col;
876
877 HashBucket ** hashTable;
878 HashBucket * hashBucket;
879 int hash;
880
881 int colorCount= 0;
882
883 const unsigned char * from;
884
885 /* 1 */
886 hashTable= (HashBucket **)malloc( HASH_SIZE* sizeof(HashBucket *) );
887 if ( ! hashTable )
888 { XDEB(hashTable); return -1; }
889 for ( row= 0; row < HASH_SIZE; row++ )
890 { hashTable[row]= (HashBucket *)0; }
891
892 for ( row= 0; row < pixelsHigh; row++ )
893 {
894 from= bufIn+ row* bytesPerRow;
895
896 for ( col= 0; col < pixelsWide; col++ )
897 {
898 r= *(from++) & mask; g= *(from++) & mask; b= *(from++) & mask;
899 hash= ppm_hash( r, g, b );
900
901 if ( hasAlpha )
902 { from++; }
903
904 if ( hash < 0 || hash >= HASH_SIZE )
905 { LLDEB(hash,HASH_SIZE); return -1; }
906
907 hashBucket= hashTable[hash];
908 while( hashBucket )
909 {
910 if ( hashBucket->hbRed == r &&
911 hashBucket->hbGreen == g &&
912 hashBucket->hbBlue == b )
913 { break; }
914 hashBucket= hashBucket->hbNext;
915 }
916 if ( hashBucket )
917 { hashBucket->hbCount++; continue; }
918
919 if ( bmInsertHash( hashTable, hash, colorCount++, r, g, b ) )
920 { LDEB(1); bmFreeColorHash( hashTable ); return -1; }
921
922 if ( colorCount > maxcolors )
923 { bmFreeColorHash( hashTable ); return 1; }
924 }
925 }
926
927 *pColorCount= colorCount;
928 *pHashTable= hashTable;
929
930 return 0;
931 }
932
933 /************************************************************************/
934 /* */
935 /* Convert a color hash table to a histogram. */
936 /* */
937 /************************************************************************/
938
bmHashToHistogram(ColorReducer * cr,int colorCount)939 static int bmHashToHistogram( ColorReducer * cr,
940 int colorCount )
941 {
942 HashBucket * hashBucket;
943
944 int row;
945 int i;
946
947 row= 0;
948 for ( i= 0; i < HASH_SIZE; i++ )
949 {
950 hashBucket= cr->crHashTable[i];
951
952 while( hashBucket )
953 {
954 cr->crHistogram[row++]= hashBucket->hbHistogramEntry;
955 hashBucket= hashBucket->hbNext;
956 }
957 }
958
959 return 0;
960 }
961
bmHashToPalette(ColorReducer * cr)962 static void bmHashToPalette( ColorReducer * cr )
963 {
964 HashBucket * hashBucket;
965
966 int i;
967
968 for ( i= 0; i < HASH_SIZE; i++ )
969 {
970 hashBucket= cr->crHashTable[i];
971
972 while( hashBucket )
973 {
974 cr->crPalette->cpColors[hashBucket->hbNumber]=
975 hashBucket->hbHistogramEntry.heColor;
976
977 hashBucket= hashBucket->hbNext;
978 }
979 }
980
981 return;
982 }
983
984 /************************************************************************/
985 /* */
986 /* Reduce the number of colors in an image to at most 'maxcolors'. */
987 /* */
988 /* 0) Allocate the palette. */
989 /* 1) Make a hash table for the colors. */
990 /* 2) Store and count all the colors in the hash table. */
991 /* 3) If the number of colors is below the maximum, fill the palette */
992 /* with the colors in the hash table. */
993 /* 4) Else translate the hash table to a histogram. */
994
995 /* 4) Allocate memory for the palette and for the tree that will be */
996 /* used to classify the colors. */
997 /* 5) Classify colors: Yields a palette and a tree. */
998 /* 6) Allocate and initialise output. */
999 /* 7) Translate to representative of box. */
1000 /* */
1001 /************************************************************************/
1002
bmColorReduce(RasterImage * riOut,const RasterImage * riIn,int maxcolors)1003 int bmColorReduce( RasterImage * riOut,
1004 const RasterImage * riIn,
1005 int maxcolors )
1006 {
1007 const BitmapDescription * bdIn= &(riIn->riDescription);
1008 int rval= 0;
1009
1010 int row;
1011 int i;
1012
1013 unsigned char mask= 0xff;
1014
1015 ColorAllocator ca;
1016 ColorReducer * cr;
1017
1018 int colorCount= 0;
1019 int colorsFound;
1020
1021 int bitsPerPixel;
1022
1023 int bitmapUnit= 0;
1024 int swapBitmapBytes= 0;
1025 int swapBitmapBits= 0;
1026 const int dither= 0;
1027
1028 RasterImage ri;
1029
1030 bmInitColorAllocator( &ca );
1031 bmInitRasterImage( &ri );
1032
1033 cr= (ColorReducer *)malloc( sizeof( ColorReducer ) );
1034 if ( ! cr )
1035 { XDEB(cr); rval= -1; goto ready; }
1036
1037 bmInitColorReducer( cr );
1038
1039 ca.caSystemPrivate= (void *)cr;
1040 ca.caAllocationType= CA_ALLOCATOR;
1041 ca.caSystemCleanup= bmReduceCleanupAllocator;
1042
1043 if ( maxcolors > 256 )
1044 { LDEB(maxcolors); rval= -1; goto ready; }
1045
1046 if ( maxcolors <= 16 )
1047 { bitsPerPixel= 4; }
1048 else{ bitsPerPixel= 8; }
1049
1050 /* 0 */
1051 if ( utilPaletteSetCount( &(ri.riDescription.bdPalette), maxcolors ) )
1052 { LDEB(maxcolors); rval= -1; goto ready; }
1053
1054 cr->crPalette= &(ri.riDescription.bdPalette);
1055
1056 /* 1, 2 */
1057 switch( bdIn->bdBitsPerPixel )
1058 {
1059 case 24:
1060 case 32:
1061 for ( i= 0; i < 8; i++ )
1062 {
1063 mask= ~( 0xff >> ( 8- i ) );
1064
1065 row= bmHashColorsRGB8( &(cr->crHashTable), &colorCount,
1066 bdIn->bdPixelsHigh, bdIn->bdPixelsWide,
1067 bdIn->bdBytesPerRow, bdIn->bdHasAlpha,
1068 riIn->riBytes, 32768, mask );
1069 if ( row < 0 )
1070 { LDEB(row); rval= -1; goto ready; }
1071 if ( row == 0 )
1072 { break; }
1073 }
1074 break;
1075
1076 default:
1077 LDEB(bdIn->bdBitsPerPixel); rval= -1; goto ready;
1078 }
1079
1080 /* 3 */
1081 if ( mask == 0xff && colorCount <= maxcolors )
1082 {
1083 bmHashToPalette( cr );
1084
1085 colorsFound= colorCount;
1086 }
1087 else{
1088 /* 4 */
1089 if ( bmAllocateHistogram( cr, colorCount ) )
1090 { LDEB(colorCount); rval= -1; goto ready; }
1091
1092 if ( bmHashToHistogram( cr, colorCount ) )
1093 { LDEB(colorCount); rval= -1; goto ready; }
1094
1095 if ( bmAllocateCutNodes( cr, maxcolors ) )
1096 { LDEB(maxcolors); rval= -1; goto ready; }
1097
1098 /* 5 */
1099 colorsFound= bmFindColors( cr, colorCount,
1100 bdIn->bdPixelsHigh* bdIn->bdPixelsWide, maxcolors );
1101
1102 if ( colorsFound < 1 )
1103 { LLDEB(maxcolors,colorsFound); rval= -1; goto ready; }
1104 }
1105
1106 /* 6 */
1107 ri.riDescription.bdPixelsWide= bdIn->bdPixelsWide;
1108 ri.riDescription.bdPixelsHigh= bdIn->bdPixelsHigh;
1109
1110 ri.riDescription.bdBitsPerSample= bdIn->bdBitsPerSample;
1111 ri.riDescription.bdSamplesPerPixel= 3;
1112 ri.riDescription.bdBitsPerPixel= bitsPerPixel;
1113
1114 ri.riDescription.bdXResolution= bdIn->bdXResolution;
1115 ri.riDescription.bdYResolution= bdIn->bdYResolution;
1116 ri.riDescription.bdUnit= bdIn->bdUnit;
1117
1118 ri.riDescription.bdColorEncoding= BMcoRGB8PALETTE;
1119 ri.riDescription.bdPalette.cpColorCount= colorsFound;
1120
1121 ri.riDescription.bdHasAlpha= 0;
1122
1123 if ( bmCalculateSizes( &(ri.riDescription) ) )
1124 { LDEB(1); rval= -1; goto ready; }
1125
1126 if ( bmAllocateBuffer( &ri ) )
1127 { LLDEB(ri.riDescription.bdBufferLength,ri.riBytes); rval= -1; goto ready; }
1128
1129 /* 7 */
1130 if ( cr->crCutNodes )
1131 { ca.caSystemAllocator= bmReduceAllocateColorCut; }
1132 else{ ca.caSystemAllocator= bmReduceAllocateColorHash; }
1133
1134 if ( bmFillImage( &ca, bitmapUnit, swapBitmapBytes, swapBitmapBits,
1135 dither, ri.riBytes, &(ri.riDescription),
1136 riIn, (const DocumentRectangle *)0 ) )
1137 { LDEB(1); rval= -1; goto ready; }
1138
1139 /* steal */
1140 *riOut= ri; bmInitRasterImage( &ri );
1141
1142 ready:
1143
1144 bmCleanRasterImage( &ri );
1145 bmCleanColorAllocator( &ca ); /* also frees cr */
1146
1147 return rval;
1148 }
1149
1150 /************************************************************************/
1151 /* */
1152 /* Make a color allocator to be used with a certain palette. */
1153 /* */
1154 /************************************************************************/
1155
bmSetColorAllocatorForPaletteImage(ColorAllocator * ca,const BitmapDescription * bd)1156 int bmSetColorAllocatorForPaletteImage( ColorAllocator * ca,
1157 const BitmapDescription * bd )
1158 {
1159 int rval= 0;
1160
1161 int i;
1162 ColorReducer * cr= (ColorReducer *)0;
1163 ColorBox * boxes= (ColorBox *)0;
1164 int * map= (int *)0;
1165 int boxCount;
1166
1167 const ColorPalette * cp= &(bd->bdPalette);
1168
1169 if ( bd->bdColorEncoding != BMcoRGB8PALETTE )
1170 { LLDEB(bd->bdColorEncoding,BMcoRGB8PALETTE); rval= -1; goto ready; }
1171
1172 cr= (ColorReducer *)malloc( sizeof( ColorReducer ) );
1173 if ( ! cr )
1174 { XDEB(cr); rval= -1; goto ready; }
1175
1176 bmInitColorReducer( cr );
1177
1178 ca->caSystemPrivate= (void *)cr;
1179 ca->caAllocationType= CA_ALLOCATOR;
1180 ca->caSystemCleanup= bmReduceCleanupAllocator;
1181
1182 cr->crPalette= &(bd->bdPalette);
1183
1184 if ( bmAllocateCutNodes( cr, cp->cpColorCount ) )
1185 { LDEB(cp->cpColorCount); rval= -1; goto ready; }
1186
1187 if ( bmAllocateHistogram( cr, cp->cpColorCount ) )
1188 { LDEB(cp->cpColorCount); rval= -1; goto ready; }
1189
1190 boxes= (ColorBox *)malloc( cp->cpColorCount* sizeof(ColorBox) );
1191 if ( ! boxes )
1192 { LLDEB(cp->cpColorCount,boxes); return -1; }
1193
1194 map= (int *)malloc( cp->cpColorCount* sizeof(int) );
1195 if ( ! map )
1196 { LLDEB(cp->cpColorCount,map); return -1; }
1197
1198 for ( i= 0; i < cp->cpColorCount; i++ )
1199 {
1200 cr->crHistogram[i].heColor= cp->cpColors[i];
1201 cr->crHistogram[i].heCount= 1;
1202
1203 map[i]= -1;
1204 }
1205
1206 boxCount= bmFindCuts( boxes, cr->crCutNodes, cr->crHistogram,
1207 cp->cpColorCount,
1208 cp->cpColorCount,
1209 cp->cpColorCount );
1210
1211 if ( boxCount != cp->cpColorCount )
1212 { LLDEB(boxCount,cp->cpColorCount); rval= -1; goto ready; }
1213
1214 ca->caSystemAllocator= bmReduceAllocateColorCut;
1215
1216 for ( i= 0; i < cp->cpColorCount; i++ )
1217 {
1218 AllocatorColor ac;
1219
1220 bmReduceAllocateColorCut( &ac, ca,
1221 cp->cpColors[i].rgb8Red,
1222 cp->cpColors[i].rgb8Green,
1223 cp->cpColors[i].rgb8Blue );
1224
1225 if ( /*ac.acColorNumber < 0 ||*/
1226 ac.acColorNumber >= cp->cpColorCount )
1227 { LLDEB(i,ac.acColorNumber); }
1228
1229 map[ac.acColorNumber]= i;
1230 }
1231
1232 for ( i= 0; i < 2* cp->cpColorCount; i++ )
1233 {
1234 if ( cr->crCutNodes[i].cnComponent != CN_LEAF )
1235 { continue; }
1236
1237 cr->crCutNodes[i].cnLeft=map[cr->crCutNodes[i].cnLeft];
1238 }
1239
1240 # if 0
1241 for ( i= 0; i < cp->cpColorCount; i++ )
1242 {
1243 AllocatorColor ac;
1244
1245 bmReduceAllocateColorCut( &ac, ca,
1246 cp->cpColors[i].rgb8Red,
1247 cp->cpColors[i].rgb8Green,
1248 cp->cpColors[i].rgb8Blue );
1249
1250 if ( ac.acColorNumber != i )
1251 {
1252 LLDEB(i,ac.acColorNumber);
1253 LDEB(cp->cpColors[i].rgb8Red);
1254 LDEB(cp->cpColors[i].rgb8Green);
1255 LDEB(cp->cpColors[i].rgb8Blue);
1256 }
1257 }
1258 # endif
1259
1260 ready:
1261
1262 if ( boxes )
1263 { free( boxes ); }
1264 if ( map )
1265 { free( map ); }
1266
1267 return rval;
1268 }
1269
1270