From 032f8807f7c1aa2d0c973b6664b9ab6be6863e90 Mon Sep 17 00:00:00 2001 From: Anthony Pesch Date: Sat, 18 Jan 2020 00:51:42 -0500 Subject: [PATCH] util: move fnv1a hash implementation into its own header Reviewed-by: Eric Anholt Reviewed-by: Iago Toral Quiroga Part-of: --- src/util/Makefile.sources | 1 + src/util/fnv1a.h | 61 +++++++++++++++++++++++++++++++++++++++ src/util/hash_table.c | 9 ------ src/util/hash_table.h | 22 +------------- src/util/meson.build | 1 + 5 files changed, 64 insertions(+), 30 deletions(-) create mode 100644 src/util/fnv1a.h diff --git a/src/util/Makefile.sources b/src/util/Makefile.sources index addfe63598b..5a8f9429428 100644 --- a/src/util/Makefile.sources +++ b/src/util/Makefile.sources @@ -21,6 +21,7 @@ MESA_UTIL_FILES := \ double.h \ fast_idiv_by_const.c \ fast_idiv_by_const.h \ + fnv1a.h \ format/u_format.c \ format/u_format.h \ format/u_format_bptc.c \ diff --git a/src/util/fnv1a.h b/src/util/fnv1a.h new file mode 100644 index 00000000000..0f92d0b0e40 --- /dev/null +++ b/src/util/fnv1a.h @@ -0,0 +1,61 @@ +/* + * Copyright © 2009,2012 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Authors: + * Eric Anholt + * + */ + +#ifndef _FNV1A_H +#define _FNV1A_H + +enum { + _mesa_fnv32_1a_offset_bias = 2166136261u, +}; + +/** + * Quick FNV-1a hash implementation based on: + * http://www.isthe.com/chongo/tech/comp/fnv/ + * + * FNV-1a is not be the best hash out there -- Jenkins's lookup3 is supposed + * to be quite good, and it probably beats FNV. But FNV has the advantage + * that it involves almost no code. For an improvement on both, see Paul + * Hsieh's http://www.azillionmonkeys.com/qed/hash.html + */ +static inline uint32_t +_mesa_fnv32_1a_accumulate_block(uint32_t hash, const void *data, size_t size) +{ + const uint8_t *bytes = (const uint8_t *)data; + + while (size-- != 0) { + hash ^= *bytes; + hash = hash * 0x01000193; + bytes++; + } + + return hash; +} + +#define _mesa_fnv32_1a_accumulate(hash, expr) \ + _mesa_fnv32_1a_accumulate_block(hash, &(expr), sizeof(expr)) + +#endif diff --git a/src/util/hash_table.c b/src/util/hash_table.c index 58e6fc2d916..9d982708868 100644 --- a/src/util/hash_table.c +++ b/src/util/hash_table.c @@ -546,15 +546,6 @@ _mesa_hash_table_random_entry(struct hash_table *ht, } -/** - * Quick FNV-1a hash implementation based on: - * http://www.isthe.com/chongo/tech/comp/fnv/ - * - * FNV-1a is not be the best hash out there -- Jenkins's lookup3 is supposed - * to be quite good, and it probably beats FNV. But FNV has the advantage - * that it involves almost no code. For an improvement on both, see Paul - * Hsieh's http://www.azillionmonkeys.com/qed/hash.html - */ uint32_t _mesa_hash_data(const void *data, size_t size) { diff --git a/src/util/hash_table.h b/src/util/hash_table.h index 87b1409c457..e2cd889f6da 100644 --- a/src/util/hash_table.h +++ b/src/util/hash_table.h @@ -32,6 +32,7 @@ #include #include #include "c99_compat.h" +#include "fnv1a.h" #include "macros.h" #ifdef __cplusplus @@ -126,27 +127,6 @@ static inline uint32_t _mesa_hash_pointer(const void *pointer) struct hash_table * _mesa_pointer_hash_table_create(void *mem_ctx); -enum { - _mesa_fnv32_1a_offset_bias = 2166136261u, -}; - -static inline uint32_t -_mesa_fnv32_1a_accumulate_block(uint32_t hash, const void *data, size_t size) -{ - const uint8_t *bytes = (const uint8_t *)data; - - while (size-- != 0) { - hash ^= *bytes; - hash = hash * 0x01000193; - bytes++; - } - - return hash; -} - -#define _mesa_fnv32_1a_accumulate(hash, expr) \ - _mesa_fnv32_1a_accumulate_block(hash, &(expr), sizeof(expr)) - /** * This foreach function is safe against deletion (which just replaces * an entry's data with the deleted marker), but not against insertion diff --git a/src/util/meson.build b/src/util/meson.build index 66d097783cc..7791be73cde 100644 --- a/src/util/meson.build +++ b/src/util/meson.build @@ -45,6 +45,7 @@ files_mesa_util = files( 'double.h', 'fast_idiv_by_const.c', 'fast_idiv_by_const.h', + 'fnv1a.h', 'format_r11g11b10f.h', 'format_rgb9e5.h', 'format_srgb.h', -- 2.30.2