1 /* Palette-manipulation functions functions for xcftools
2 *
3 * This file was written by Henning Makholm <henning@makholm.net>
4 * It is hereby in the public domain.
5 *
6 * In jurisdictions that do not recognise grants of copyright to the
7 * public domain: I, the author and (presumably, in those jurisdictions)
8 * copyright holder, hereby permit anyone to distribute and use this code,
9 * in source code or binary form, with or without modifications. This
10 * permission is world-wide and irrevocable.
11 *
12 * Of course, I will not be liable for any errors or shortcomings in the
13 * code, since I give it away without asking any compenstations.
14 *
15 * If you use or distribute this code, I would appreciate receiving
16 * credit for writing it, in whichever way you find proper and customary.
17 */
18
19 #include "palette.h"
20 #include <assert.h>
21
22 #define HASH_SIZE 1711
23 /* If I remember correctly, this size hash will be able to handle
24 * either of
25 * a) the Netscape cube with intensities 0x00, 0x33, 0x66, 0x99, 0xCC, xFF
26 * b) the EGA cube with intensities 0x00, 0x55, 0xAA, 0xFF
27 * c) the "CGA cube" with intensites 0x00, 0x80, 0xFF
28 * d) a full 256-step grayscale
29 * without collisions. It will also have a minimal number of collisions
30 * (4) on a full 16-to-a-side cube with intensities
31 * 0x00, 0x11, 0x22, ..., 0xDD, 0xEE, 0xFF.
32 */
33
34 unsigned paletteSize ;
35 rgba palette[MAX_PALETTE] ;
36 static int masterhash[HASH_SIZE];
37 static int bucketlinks[MAX_PALETTE];
38
39 void
init_palette_hash(void)40 init_palette_hash(void)
41 {
42 unsigned i ;
43 for( i=0; i<HASH_SIZE; i++ )
44 masterhash[i] = -1 ;
45 for( i=0; i<MAX_PALETTE; i++ )
46 bucketlinks[i] = -1 ;
47 paletteSize = 0 ;
48 }
49
50 inline int
lookup_or_intern(rgba color)51 lookup_or_intern(rgba color) {
52 int *target = &masterhash[color % HASH_SIZE];
53 while( *target >= 0 ) {
54 if( palette[*target] == color )
55 return *target ;
56 target = &bucketlinks[*target] ;
57 }
58 #if 0
59 fprintf(stderr,"Palette[%u] = %08x (%u --> %d)\n",paletteSize,color,
60 color % HASH_SIZE, *target);
61 #endif
62 if( paletteSize >= MAX_PALETTE )
63 return -1 ;
64 *target = paletteSize ;
65 palette[paletteSize] = color ;
66 return paletteSize++ ;
67 }
68
69 static inline void
unpalettify_row(rgba * row,unsigned ncols)70 unpalettify_row(rgba *row,unsigned ncols)
71 {
72 index_t *newrow = (index_t*) row ;
73 unsigned i ;
74 for( i=ncols; i--; ) {
75 row[i] = palette[newrow[i]] ;
76 }
77 }
78
79 int
palettify_row(rgba * row,unsigned ncols)80 palettify_row(rgba *row,unsigned ncols)
81 {
82 index_t *newrow = (index_t*)row ;
83 assert(sizeof(index_t) <= sizeof(rgba));
84 unsigned i ;
85 for( i=0; i<ncols; i++ ) {
86 int j = lookup_or_intern(row[i]) ;
87 if( j < 0 ) {
88 unpalettify_row(row,i);
89 return 0 ;
90 }
91 newrow[i] = j ;
92 }
93 return 1 ;
94 }
95
96 int
palettify_rows(rgba * rows[],unsigned ncols,unsigned nlines)97 palettify_rows (rgba *rows[],unsigned ncols,unsigned nlines)
98 {
99 unsigned i ;
100 for( i=0; i<nlines; i++ ) {
101 if( !palettify_row(rows[i],ncols) ) {
102 while( i-- )
103 unpalettify_row(rows[i],ncols);
104 return 0 ;
105 }
106 }
107 return 1 ;
108 }
109
110
111