mirror of https://gitlab.freedesktop.org/mesa/mesa
245 lines
8.2 KiB
C
245 lines
8.2 KiB
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;
|
|
}
|