1 /* chunkhash.c -- build a perfect hash code for the chunk names on stdin.
3 * Last changed in libpng 1.7.0 [(PENDING RELEASE)]
5 * COPYRIGHT: Written by John Cunningham Bowler, 2014.
6 * To the extent possible under law, the author has waived all copyright and
7 * related or neighboring rights to this work. This work is published from:
10 * Feed this program all the known chunks that libpng must recognize. It will
11 * generate an appropriate hash key for the macro in pngpriv.h To generate the
12 * list of chunks currently defined in png.h do this:
14 * sed -n -e 's/^#define png_\(....\) PNG_U32.*$/\1/p' png.h
16 * An alternative to using this program is to pipe the output of the above
17 * through gperf, however the code generated by perf is somewhat more verbose
18 * and it doesn't generate as good a result (however it's a heck of a lot faster
24 #include <png.h> /* for the libpng types for this platform */
26 /* The machine generated file is checked in, so this works and it obtains the
27 * definition of the PNG_CHUNK_HASH macro. To change this definition only ever
28 * alter the strings below!
30 #include "chunkhash.h"
32 /* The best_ variables are local variables defined in the functions below. When
33 * used in libpng code, however, they are just constants.
35 #define PNG_CHUNK_HASH_MASK best_mask
36 #define PNG_CHUNK_HASH_C0 best_c[0]
37 #define PNG_CHUNK_HASH_C1 best_c[1]
38 #define PNG_CHUNK_HASH_C2 best_c[2]
39 #define PNG_CHUNK_HASH_C3 best_c[3]
41 /* These strings contain the C text to copy into the new version of
42 * contrib/tools/chunkhash.c
44 static const char *strings[] = {
45 "/* chunkhash.h -- a perfect hash code for the chunk names in png.h",
47 " * Last changed in libpng 1.7.0 [(PENDING RELEASE)]",
49 " * THIS IS A MACHINE GENERATED FILE. See contrib/tools/chunkhash.c for",
50 " * copyright and other information.",
52 " * USAGE: To include the PNG_CHUNK_HASH macro and associated definitions:",
54 " * #define PNG_CHUNKHASH_DEFS",
55 " * #include \"contrib/tools/chunkhash.h\"",
57 " * To define the png_chunk_hash array used by the macro:",
59 " * #define PNG_CHUNKHASH_CODE",
60 " * #include \"contrib/tools/chunkhash.h\"",
62 " * One or both of the defines must be given except when building chunkhash",
65 "#ifdef PNG_CHUNKHASH_DEFS",
66 "#ifndef PNG_CHUNKHASH_H",
67 "#define PNG_CHUNKHASH_H",
68 "/* A perfect hash code - returns a value 0..(PNG_KNOWN_CHUNK_COUNT-1) and is",
69 " * generated by the ridiculously simple program in contrib/tools/chunkhash.c",
71 " * The hash code used here multiplies each byte by a different constant to",
72 " * return a single number:",
74 " * b0 * c[0] + b1 * [c1] + b2 * c[2] + b3 * c[3]",
76 " * The values of the constants are found by search using the a table of",
77 " * primes, including 0, and may be (in fact are at present) 0 for some of the",
78 " * bytes, the compiler is expected to optimize multiply by zero, or one!",
80 " * The lookup table reduces the sparse result of the hash calculation to the",
81 " * correct index values. The chunks are indexed in the string order of the",
82 " * png_uint_32 chunk names.",
84 0, /* HEADER definitions go here */
86 "extern const png_byte png_chunk_hash[PNG_CHUNK_HASH_MASK+1];",
87 "#endif /* !PNG_CHUNKHASH_H */",
88 "#endif /* PNG_CHUNKHASH_DEFS */",
90 "#ifndef PNG_CHUNK_HASH",
91 "#define PNG_CHUNK_HASH(chunk) (png_chunk_hash[PNG_CHUNK_HASH_MASK & (\\",
92 " ((chunk) >> 24) * PNG_CHUNK_HASH_C0 +\\",
93 " ((chunk) >> 16) * PNG_CHUNK_HASH_C1 +\\",
94 " ((chunk) >> 8) * PNG_CHUNK_HASH_C2 +\\",
95 " ((chunk) ) * PNG_CHUNK_HASH_C3)])",
98 "#ifdef PNG_CHUNKHASH_CODE",
99 "#ifndef PNG_CHUNKHASH_C",
100 "#define PNG_CHUNKHASH_C",
101 "const png_byte png_chunk_hash[PNG_CHUNK_HASH_MASK+1] = {",
102 0, /* png.c definitions go here */
104 "#endif /* !PNG_CHUNKHASH_C */",
105 "#endif /* PNG_CHUNKHASH_CODE */",
109 #define CHUNK_COUNT_MAX 32
110 /* If necessary this is easy to increase; just don't use a png_uint_32
111 * bitmask below, however it doesn't seem likely that the limit will be hit
115 static const png_byte
118 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
119 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
120 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
121 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78,
122 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97,
123 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113,
124 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128,
125 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,
126 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158,
127 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173,
128 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188,
129 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203,
130 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218,
131 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233,
132 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248,
133 249, 250, 251, 252, 253, 254, 255
137 error(const char *string)
139 fprintf(stderr, "chunkhash: %s\n", string);
143 /* Return a hash code for the given chunk; this is the same as the pngpriv.h
144 * macro, but parameterized. The names of the parameters have to be chosen to
145 * match the above #defines.
148 test_hash(png_uint_32 chunk, const unsigned int *best_c, png_uint_32 best_mask)
150 # define png_chunk_hash chunk_hash /* prevents lookup */
151 return PNG_CHUNK_HASH(chunk);
152 # undef png_chunk_hash
156 print_chunks(const png_uint_32 *chunks, unsigned int nchunks, png_uint_32 first,
157 png_uint_32 last, const unsigned int *best_c, png_uint_32 best_mask,
160 /* 'last' is the last code to print plus 1, this is used to detect duplicates
161 * (which should not happen - if there are any it's an internal error!)
165 /* Recursive algorithm; find the hash code of the next chunk, then print
166 * all remaining chunks with codes in the range first..code (including
167 * duplicates) and after print all remaining chunks with codes in the
168 * range (code+1)..last
170 const png_uint_32 chunk = *chunks++;
171 # define png_chunk_hash lut
172 const png_uint_32 code = PNG_CHUNK_HASH(chunk);
173 # undef png_chunk_hash
177 /* The code might be out of the print range */
178 if (code >= first && code <= last)
180 if (code >= first) /* not time yet */
181 print_chunks(chunks, nchunks, first, code, best_c, best_mask, lut);
183 printf("#define PNG_CHUNK_%c%c%c%c_TAG %lu%s\n", (char)(chunk>>24),
184 (char)(chunk>>16), (char)(chunk>>8), (char)chunk,
185 (unsigned long)code, code == last ? " /* DUPLICATE */" : "");
187 if (code < last) /* still some to go */
188 print_chunks(chunks, nchunks, code+1, last, best_c, best_mask, lut);
192 print_chunks(chunks, nchunks, first, last, best_c, best_mask, lut);
196 static unsigned int primes[] =
198 0, 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
199 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
200 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
204 #define NPRIMES ((sizeof primes)/(sizeof primes[0]))
209 /* Stdin should just contain chunk names, one per line */
210 png_uint_32 best_mask;
211 unsigned int best_c[4];
212 png_uint_32 chunks[CHUNK_COUNT_MAX];
213 png_byte known_chunk_count;
215 /* Not required; stop GCC whining: */
216 memset(best_c, 0xab, sizeof best_c);
217 best_mask = 0x12345678;
220 png_uint_32 this_chunk = 0;
221 png_byte n_chunks = 0;
227 if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
229 if (this_chunk > 0xffffffU)
230 error("chunk name too long");
232 this_chunk = (this_chunk << 8) + (unsigned)ch;
239 if (this_chunk <= 0xffffffU)
240 error("chunk name too short");
242 if (n_chunks >= CHUNK_COUNT_MAX)
243 error("too many chunks (check CHUNK_COUNT_MAX)");
245 chunks[n_chunks++] = this_chunk;
254 /* 22 is the number of chunks currently defined (excluding fRAc), at any
255 * time it should also be in PNG_KNOWN_CHUNK_COUNT, but this run of
256 * chunkhash may be trying to add a chunk so allow bigger numbers.
258 # ifdef PNG_KNOWN_CHUNK_COUNT
259 # define CHUNK_COUNT_MIN PNG_KNOWN_CHUNK_COUNT
261 # define CHUNK_COUNT_MIN 26
263 if (n_chunks < CHUNK_COUNT_MIN)
264 error("too few chunks (expecting at least 26)");
266 known_chunk_count = n_chunks;
269 /* Exhaustive search of the hash parameters - in fact this isn't very slow at
273 unsigned int i1, c_zero = 0, c_one = 0;
275 for (i1=0; i1<NPRIMES; ++i1)
280 fprintf(stderr, "TEST: %u\n", primes[i1]);
283 for (i2=0; i2<NPRIMES; ++i2)
289 for (i3=0; i3<NPRIMES; ++i3)
295 for (i4=0; i4<NPRIMES; ++i4)
298 png_uint_32 hash_mask = 0xffU;
299 png_uint_32 hashes[CHUNK_COUNT_MAX];
303 while (hash_mask > 0xfU)
305 for (i=0; i<known_chunk_count; ++i)
308 png_uint_32 hash = test_hash(chunks[i], c, hash_mask);
310 for (j=0; j<i; ++j) if (hashes[j] == hash) goto next_i4;
319 if (hash_mask < 0xffU)
322 unsigned int best, c0 = 0, c1 = 0;
336 if (hash_mask == best_mask)
337 best = (c0 > c_zero) || (c0 == c_zero && c1 > c_one);
340 best = (hash_mask < best_mask);
344 fprintf(stderr, "{%u,%u,%u,%u} & 0x%lx\n",
345 c[0], c[1], c[2], c[3],
346 (unsigned long)hash_mask);
350 best_mask = hash_mask;
351 memcpy(best_c, c, sizeof best_c);
360 /* Calculate the LUT (png_chunk_hash) */
365 /* A failure returns PNG_KNOWN_CHUNK_COUNT: */
366 memset(lut, known_chunk_count, sizeof lut);
368 for (b=0; b<known_chunk_count; ++b)
369 lut[test_hash(chunks[b], best_c, best_mask)] = b;
371 /* Validate the pngpriv.h hash function. */
372 # define png_chunk_hash lut
376 for (i=0; i<known_chunk_count; ++i)
378 png_uint_32 chunk = chunks[i];
380 if (PNG_CHUNK_HASH(chunk) != i)
381 error("internal error: hash didn't work!");
386 /* Print all the results, first the stuff for pngpriv.h */
390 while (strings[i] != 0)
393 printf("#define PNG_CHUNK_HASH_MASK 0x%lxU\n",
394 (unsigned long)best_mask);
395 printf("#define PNG_CHUNK_HASH_C0 %u\n", best_c[0]);
396 printf("#define PNG_CHUNK_HASH_C1 %u\n", best_c[1]);
397 printf("#define PNG_CHUNK_HASH_C2 %u\n", best_c[2]);
398 printf("#define PNG_CHUNK_HASH_C3 %u\n", best_c[3]);
400 /* Print the hash codes of all the chunks */
402 print_chunks(chunks, known_chunk_count, 0, 0xffffffff, best_c,
405 printf("#define PNG_KNOWN_CHUNK_COUNT %u\n", known_chunk_count);
407 while (strings[++i] != 0)
410 /* Now print the LUT */
415 for (j=0; j<=best_mask; ++j)
417 printf("%d", lut[j]);
419 if ((j % 16) == 15 && j < best_mask)
422 else if (j < best_mask)
430 /* And the trailing text */
431 while (strings[++i] != 0)