contrib/tools/chunkhash.c - third_party/libpng - Git at Google

 /* 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);
 }
	/* 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);
	}