path: root/src/util/tools/find_hash_func.c

/*
 * Copyright 2022 Advanced Micro Devices, Inc.
 *
 * SPDX-License-Identifier: MIT
 */

/* See the big comment.
 *
 * Compile: gcc find_hash_func.c -fopenmp -O3 -g -o find_hash_func
 */

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <alloca.h>
#include <GL/gl.h>
#include <GL/glext.h>
#include <GLES2/gl2.h>
#include <GLES2/gl2ext.h>

#define MAX_GLENUM_BITS 16

/* Duplicate this here. Don't pull the whole Mesa's built system into this. */
static inline unsigned
util_next_power_of_two(unsigned x)
{
   if (x <= 1)
       return 1;

   return (1 << ((sizeof(unsigned) * 8) - __builtin_clz(x - 1)));
}

struct entry {
   unsigned result;
   const char *name;
   unsigned value;
};

/* Given a list of large values (such as GLenums), find a simple perfect hash
 * function that maps the large values to smallest possible numbers for use as
 * array indices, so that we can index arrays by hash(GLenum). This is useful
 * when a switch statement for conversions from GLenums to indices would be
 * undesirable.
 *
 * The final hash function is always in this form:
 *      hash(x) = ((x * mul) >> rshift) & BITFIELD_MASK(bits)
 *
 * This is a brute force algorithm that tries to find all injective
 * (mul, rshift, bits) hash functions and return the one whose maximum
 * generated value is the smallest.
 */
static bool
find_perfect_hash_func(const struct entry *list, unsigned *best_mul,
                       unsigned *best_rshift, unsigned *best_mask,
                       unsigned *best_max)
{
   bool found = false;
   *best_mul = 1;
   *best_rshift = 0;
   *best_mask = ~0;
   *best_max = (1 << MAX_GLENUM_BITS) - 1;

   for (unsigned mul = 1; mul < (1 << 16); mul++) {
      for (unsigned rshift = 1; rshift <= 31; rshift++) {
         for (unsigned bits = 1; bits <= MAX_GLENUM_BITS; bits++) {
            unsigned mask = (1 << bits) - 1;
            unsigned max = 0;

            for (unsigned a = 0; list[a].name; a++) {
               unsigned hash = ((list[a].value * mul) >> rshift) & mask;

               max = hash > max ? hash : max;

               for (unsigned b = a + 1; list[b].name; b++) {
                  /* Skip if the mapping is not injective. */
                  if (hash == (((list[b].value * mul) >> rshift) & mask))
                     goto fail;
               }
            }
            if (max < *best_max) {
               *best_mul = mul;
               *best_rshift = rshift;
               *best_mask = mask;
               *best_max = max;
               found = true;
            }
         fail:;
         }
      }
   }
   return found;
}

static bool
find_translate_func(const struct entry *list, unsigned *out_mul,
                    unsigned *out_rshift, unsigned *out_mask,
                    unsigned max_result)
{
   unsigned mask = util_next_power_of_two(max_result + 1) - 1;
   unsigned num_threads = 24;
   unsigned start_mul = 1;
   unsigned end_mul = (1 << 31) - num_threads;

   int thread_id_finished = -1;
   unsigned *result_mul = alloca(4 * num_threads);
   unsigned *result_rshift = alloca(4 * num_threads);

#pragma omp parallel for
   for (unsigned thread_id = 0; thread_id < num_threads; thread_id++) {
      for (unsigned mul = start_mul; mul < end_mul; mul += num_threads) {
         for (unsigned rshift = 1; rshift <= 31; rshift++) {
            for (unsigned add = 0; add <= max_result; add++) {
               for (unsigned a = 0; list[a].name; a++) {
                  unsigned hash = (((list[a].value * mul) >> rshift) + add) & mask;

                  /* Reject the mapping if it doesn't return the expected result. */
                  if (hash != list[a].result)
                     goto fail;
               }

               result_mul[thread_id] = mul;
               result_rshift[thread_id] = rshift;
               __atomic_store_n(&thread_id_finished, thread_id, __ATOMIC_RELEASE);
               puts("found");
               goto done;
            fail:;
            }
         }
      }
   done:;
   }

   if (__atomic_load_n(&thread_id_finished, __ATOMIC_ACQUIRE) >= 0) {
      *out_mul = result_mul[thread_id_finished];
      *out_rshift = result_rshift[thread_id_finished];
      *out_mask = mask;
      return true;
   }

   return false;
}

static void
print_hash_code(const char *uppercase_name, const char *lowercase_name,
                const struct entry *list, bool get_translate_func)
{
   unsigned mul, rshift, mask, max;
   unsigned max_strlen = 0, max_result = 0;

   for (unsigned i = 0; list[i].name; i++) {
      int len = strlen(list[i].name);
      max_strlen = len > max_strlen ? len : max_strlen;
      max_result = list[i].result > max_result ? list[i].result : max_result;
   }

   /* Find the hash function that can be used as a translation function (no table). */
   if (get_translate_func) {
      if (find_translate_func(list, &mul, &rshift, &mask, max_result)) {
         printf("/* Translate enums to desired values arithmetically (without a switch) */\n");
         printf("#define TRANSLATE_%s(x) ((((uint32_t)(x) * %u) >> %u) & 0x%x)\n\n",
                uppercase_name, mul, rshift, mask);

         for (unsigned i = 0; list[i].name; i++) {
            printf("static_assert(TRANSLATE_%s(%s) == %u)\n",
                   uppercase_name, list[i].name, list[i].result);
         }
         printf("\n");
      } else {
         puts("/* ERROR: Can't find the hash function for translating. */");
      }
   } else {
      /* Find the hash function that can be used for indexing into a table. */
      if (find_perfect_hash_func(list, &mul, &rshift, &mask, &max)) {
         printf("/* Map enums to smaller enums arithmetically (without a switch) */\n");
         printf("#define PERF_HASH_%s(x) ((((uint32_t))(x) * %u) >> %u) & 0x%x)\n\n",
                uppercase_name, mul, rshift, mask);

         /* Print the translation table. */
         printf("static const uint%u_t %s_table[16] = {\n",
                max > 255 ? 16 : 8, lowercase_name);
         printf("   /* These elements are sorted by meaning, not value. */\n");
         for (unsigned i = 0; list[i].name; i++)
            printf("   [/*%2u*/ PERF_HASH_%s(%s)] = 0,\n",
                   ((list[i].value * mul) >> rshift) & mask, uppercase_name, list[i].name);
         printf("};\n\n");

         /* Print the uniqueness compile check. */
         printf("static inline void\n");
         printf("compile_check_uniqueness_of_%s(unsigned x)\n", lowercase_name);
         printf("{\n");
         printf("   /* This switch has the same purpose as static_assert.\n");
         printf("    * It should fail compilation if any case is not unique.\n");
         printf("    */\n");
         printf("   switch (x) {\n");
         for (unsigned i = 0; list[i].name; i++)
            printf("   case PERF_HASH_%s(%s):\n", uppercase_name, list[i].name);
         printf("      break;\n");
         printf("   }\n");
         printf("}\n\n");

         printf("/* GL enums mapped to smaller numbers. The number are not contiguous. */\n");
         printf("typedef enum {\n");
         for (unsigned i = 0; list[i].name; i++) {
            printf("   MESA_%s = %*s/*%2u*/ PERF_HASH_%s(%s),\n",
                   list[i].name + 3,
                   1 + max_strlen - (int)strlen(list[i].name), " ",
                   ((list[i].value * mul) >> rshift) & mask,
                   uppercase_name, list[i].name);
         }
         printf("\n   NUM_%sS = %u,\n", uppercase_name, max + 1);
         printf("   NUM_%sS_POW2 = %u,\n",
                uppercase_name, util_next_power_of_two(max + 1));
         printf("} %s;\n\n", lowercase_name);
      } else {
         puts("/* ERROR: Can't find the hash function for indexing. */");
      }
   }
}

#define S(x) #x, x

int main(int argc, char **argv)
{
   struct entry vertex_types[] = {
      {0, S(GL_BYTE)},
      {0, S(GL_UNSIGNED_BYTE)},
      {0, S(GL_INT_2_10_10_10_REV)},
      {0, S(GL_UNSIGNED_INT_2_10_10_10_REV)},
      {1, S(GL_SHORT)},
      {1, S(GL_UNSIGNED_SHORT)},
      {1, S(GL_HALF_FLOAT_ARB)},
      {1, S(GL_HALF_FLOAT_OES)},
      {2, S(GL_INT)},
      {2, S(GL_UNSIGNED_INT)},
      {2, S(GL_FLOAT)},
      {2, S(GL_FIXED)},
      {3, S(GL_DOUBLE)},
      {3, S(GL_UNSIGNED_INT64_ARB)},
      {0},
   };
   print_hash_code("GL_VERTEX_TYPE", "gl_vertex_type", vertex_types, false);

   return 0;
}