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