diff options
Diffstat (limited to 'mesalib/src/util')
| -rw-r--r-- | mesalib/src/util/Makefile.am | 9 | ||||
| -rw-r--r-- | mesalib/src/util/Makefile.sources | 8 | ||||
| -rw-r--r-- | mesalib/src/util/SConscript | 7 | ||||
| -rw-r--r-- | mesalib/src/util/bitset.h | 99 | ||||
| -rw-r--r-- | mesalib/src/util/hash_table.c | 46 | ||||
| -rw-r--r-- | mesalib/src/util/hash_table.h | 23 | ||||
| -rw-r--r-- | mesalib/src/util/macros.h | 2 | ||||
| -rw-r--r-- | mesalib/src/util/mesa-sha1.c | 316 | ||||
| -rw-r--r-- | mesalib/src/util/mesa-sha1.h | 53 | ||||
| -rw-r--r-- | mesalib/src/util/register_allocate.c | 2 | ||||
| -rw-r--r-- | mesalib/src/util/set.c | 391 | ||||
| -rw-r--r-- | mesalib/src/util/set.h | 100 | ||||
| -rw-r--r-- | mesalib/src/util/simple_list.h | 211 | ||||
| -rw-r--r-- | mesalib/src/util/u_atomic.h | 105 | ||||
| -rw-r--r-- | mesalib/src/util/u_atomic_test.c | 40 |
15 files changed, 1359 insertions, 53 deletions
diff --git a/mesalib/src/util/Makefile.am b/mesalib/src/util/Makefile.am index c7e183e8d..9af233059 100644 --- a/mesalib/src/util/Makefile.am +++ b/mesalib/src/util/Makefile.am @@ -31,12 +31,21 @@ libmesautil_la_CPPFLAGS = \ -I$(top_srcdir)/src \ -I$(top_srcdir)/src/mapi \ -I$(top_srcdir)/src/mesa \ + -I$(top_srcdir)/src/gallium/include \ + -I$(top_srcdir)/src/gallium/auxiliary \ + $(SHA1_CFLAGS) \ $(VISIBILITY_CFLAGS) libmesautil_la_SOURCES = \ $(MESA_UTIL_FILES) \ $(MESA_UTIL_GENERATED_FILES) +if ENABLE_SHADER_CACHE +libmesautil_la_SOURCES += $(MESA_UTIL_SHADER_CACHE_FILES) +endif + +libmesautil_la_LIBADD = $(SHA1_LIBS) + check_PROGRAMS = u_atomic_test TESTS = $(check_PROGRAMS) diff --git a/mesalib/src/util/Makefile.sources b/mesalib/src/util/Makefile.sources index 5f87fc32a..560ea836a 100644 --- a/mesalib/src/util/Makefile.sources +++ b/mesalib/src/util/Makefile.sources @@ -1,4 +1,9 @@ +MESA_UTIL_SHADER_CACHE_FILES := \ + mesa-sha1.c \ + mesa-sha1.h + MESA_UTIL_FILES := \ + bitset.h \ format_srgb.h \ hash_table.c \ hash_table.h \ @@ -9,6 +14,9 @@ MESA_UTIL_FILES := \ register_allocate.h \ rgtc.c \ rgtc.h \ + set.c \ + set.h \ + simple_list.h \ strtod.cpp \ strtod.h \ texcompress_rgtc_tmp.h \ diff --git a/mesalib/src/util/SConscript b/mesalib/src/util/SConscript index 34b9a2dea..84bd7a1e1 100644 --- a/mesalib/src/util/SConscript +++ b/mesalib/src/util/SConscript @@ -11,6 +11,8 @@ env.Prepend(CPPPATH = [ '#src', '#src/mapi', '#src/mesa', + '#src/gallium/include', + '#src/gallium/auxiliary', '#src/util', ]) @@ -29,6 +31,11 @@ mesautil_sources = ( source_lists['MESA_UTIL_GENERATED_FILES'] ) +# XXX We don't yet have scons support for detecting any of the various +# HAVE_SHA1_* definitions, so for now simply disable the shader cache. +if False: + mesautil_sources += source_lists['MESA_UTIL_SHADER_CACHE_FILES'] + mesautil = env.ConvenienceLibrary( target = 'mesautil', source = mesautil_sources, diff --git a/mesalib/src/util/bitset.h b/mesalib/src/util/bitset.h new file mode 100644 index 000000000..17c5d5d25 --- /dev/null +++ b/mesalib/src/util/bitset.h @@ -0,0 +1,99 @@ +/* + * Mesa 3-D graphics library + * + * Copyright (C) 2006 Brian Paul All Rights Reserved. + * + * 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 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. + */ + +/** + * \file bitset.h + * \brief Bitset of arbitrary size definitions. + * \author Michal Krol + */ + +#ifndef BITSET_H +#define BITSET_H + +#include "util/u_math.h" + +/**************************************************************************** + * generic bitset implementation + */ + +#define BITSET_WORD unsigned int +#define BITSET_WORDBITS (sizeof (BITSET_WORD) * 8) + +/* bitset declarations + */ +#define BITSET_WORDS(bits) (((bits) + BITSET_WORDBITS - 1) / BITSET_WORDBITS) +#define BITSET_DECLARE(name, bits) BITSET_WORD name[BITSET_WORDS(bits)] + +/* bitset operations + */ +#define BITSET_COPY(x, y) memcpy( (x), (y), sizeof (x) ) +#define BITSET_EQUAL(x, y) (memcmp( (x), (y), sizeof (x) ) == 0) +#define BITSET_ZERO(x) memset( (x), 0, sizeof (x) ) +#define BITSET_ONES(x) memset( (x), 0xff, sizeof (x) ) + +#define BITSET_BITWORD(b) ((b) / BITSET_WORDBITS) +#define BITSET_BIT(b) (1 << ((b) % BITSET_WORDBITS)) + +/* single bit operations + */ +#define BITSET_TEST(x, b) ((x)[BITSET_BITWORD(b)] & BITSET_BIT(b)) +#define BITSET_SET(x, b) ((x)[BITSET_BITWORD(b)] |= BITSET_BIT(b)) +#define BITSET_CLEAR(x, b) ((x)[BITSET_BITWORD(b)] &= ~BITSET_BIT(b)) + +#define BITSET_MASK(b) ((b) == BITSET_WORDBITS ? ~0 : BITSET_BIT(b) - 1) +#define BITSET_RANGE(b, e) (BITSET_MASK((e) + 1) & ~BITSET_MASK(b)) + +/* bit range operations + */ +#define BITSET_TEST_RANGE(x, b, e) \ + (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \ + ((x)[BITSET_BITWORD(b)] & BITSET_RANGE(b, e)) : \ + (assert (!"BITSET_TEST_RANGE: bit range crosses word boundary"), 0)) +#define BITSET_SET_RANGE(x, b, e) \ + (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \ + ((x)[BITSET_BITWORD(b)] |= BITSET_RANGE(b, e)) : \ + (assert (!"BITSET_SET_RANGE: bit range crosses word boundary"), 0)) +#define BITSET_CLEAR_RANGE(x, b, e) \ + (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \ + ((x)[BITSET_BITWORD(b)] &= ~BITSET_RANGE(b, e)) : \ + (assert (!"BITSET_CLEAR_RANGE: bit range crosses word boundary"), 0)) + +/* Get first bit set in a bitset. + */ +static inline int +__bitset_ffs(const BITSET_WORD *x, int n) +{ + int i; + + for (i = 0; i < n; i++) { + if (x[i]) + return ffs(x[i]) + BITSET_WORDBITS * i; + } + + return 0; +} + +#define BITSET_FFS(x) __bitset_ffs(x, Elements(x)) + +#endif diff --git a/mesalib/src/util/hash_table.c b/mesalib/src/util/hash_table.c index 0ad038377..3247593c1 100644 --- a/mesalib/src/util/hash_table.c +++ b/mesalib/src/util/hash_table.c @@ -232,7 +232,7 @@ hash_table_insert(struct hash_table *ht, uint32_t hash, const void *key, void *data); static void -_mesa_hash_table_rehash(struct hash_table *ht, int new_size_index) +_mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index) { struct hash_table old_ht; struct hash_entry *table, *entry; @@ -267,6 +267,7 @@ hash_table_insert(struct hash_table *ht, uint32_t hash, const void *key, void *data) { uint32_t start_hash_address, hash_address; + struct hash_entry *available_entry = NULL; if (ht->entries >= ht->max_entries) { _mesa_hash_table_rehash(ht, ht->size_index + 1); @@ -281,13 +282,11 @@ hash_table_insert(struct hash_table *ht, uint32_t hash, uint32_t double_hash; if (!entry_is_present(ht, entry)) { - if (entry_is_deleted(ht, entry)) - ht->deleted_entries--; - entry->hash = hash; - entry->key = key; - entry->data = data; - ht->entries++; - return entry; + /* Stash the first available entry we find */ + if (available_entry == NULL) + available_entry = entry; + if (entry_is_free(entry)) + break; } /* Implement replacement when another insert happens @@ -314,6 +313,16 @@ hash_table_insert(struct hash_table *ht, uint32_t hash, hash_address = (hash_address + double_hash) % ht->size; } while (hash_address != start_hash_address); + if (available_entry) { + if (entry_is_deleted(ht, available_entry)) + ht->deleted_entries--; + available_entry->hash = hash; + available_entry->key = key; + available_entry->data = data; + ht->entries++; + return available_entry; + } + /* We could hit here if a required resize failed. An unchecked-malloc * application could ignore this result. */ @@ -334,8 +343,8 @@ _mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data) } struct hash_entry * -_mesa_hash_table_insert_with_hash(struct hash_table *ht, uint32_t hash, - const void *key, void *data) +_mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash, + const void *key, void *data) { assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key)); return hash_table_insert(ht, hash, key, data); @@ -431,27 +440,18 @@ _mesa_hash_table_random_entry(struct hash_table *ht, uint32_t _mesa_hash_data(const void *data, size_t size) { - uint32_t hash = 2166136261ul; - const uint8_t *bytes = data; - - while (size-- != 0) { - hash ^= *bytes; - hash = hash * 0x01000193; - bytes++; - } - - return hash; + return _mesa_fnv32_1a_accumulate_block(_mesa_fnv32_1a_offset_bias, + data, size); } /** FNV-1a string hash implementation */ uint32_t _mesa_hash_string(const char *key) { - uint32_t hash = 2166136261ul; + uint32_t hash = _mesa_fnv32_1a_offset_bias; while (*key != 0) { - hash ^= *key; - hash = hash * 0x01000193; + hash = _mesa_fnv32_1a_accumulate(hash, *key); key++; } diff --git a/mesalib/src/util/hash_table.h b/mesalib/src/util/hash_table.h index 5561e1584..eb9dbc333 100644 --- a/mesalib/src/util/hash_table.h +++ b/mesalib/src/util/hash_table.h @@ -70,8 +70,8 @@ void _mesa_hash_table_set_deleted_key(struct hash_table *ht, struct hash_entry * _mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data); struct hash_entry * -_mesa_hash_table_insert_with_hash(struct hash_table *ht, uint32_t hash, - const void *key, void *data); +_mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash, + const void *key, void *data); struct hash_entry * _mesa_hash_table_search(struct hash_table *ht, const void *key); struct hash_entry * @@ -101,6 +101,25 @@ static inline uint32_t _mesa_hash_pointer(const void *pointer) return _mesa_hash_data(&pointer, sizeof(pointer)); } +static const uint32_t _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/mesalib/src/util/macros.h b/mesalib/src/util/macros.h index 5fc672953..eec8b9352 100644 --- a/mesalib/src/util/macros.h +++ b/mesalib/src/util/macros.h @@ -82,7 +82,7 @@ do { \ #endif #ifndef unreachable -#define unreachable(str) +#define unreachable(str) assert(!str) #endif /** diff --git a/mesalib/src/util/mesa-sha1.c b/mesalib/src/util/mesa-sha1.c new file mode 100644 index 000000000..fa2819377 --- /dev/null +++ b/mesalib/src/util/mesa-sha1.c @@ -0,0 +1,316 @@ +/* Copyright © 2007 Carl Worth + * Copyright © 2009 Jeremy Huddleston, Julien Cristau, and Matthieu Herrb + * Copyright © 2009-2010 Mikhail Gusarov + * Copyright © 2012 Yaakov Selkowitz and Keith Packard + * Copyright © 2014 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. + */ + +#include "mesa-sha1.h" + +#if defined(HAVE_SHA1_IN_LIBMD) /* Use libmd for SHA1 */ \ + || defined(HAVE_SHA1_IN_LIBC) /* Use libc for SHA1 */ + +#include <sha1.h> + +struct mesa_sha1 * +_mesa_sha1_init(void) +{ + SHA1_CTX *ctx = malloc(sizeof(*ctx)); + + if (!ctx) + return NULL; + + SHA1Init(ctx); + return (struct mesa_sha1 *) ctx; +} + +int +_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size) +{ + SHA1_CTX *sha1_ctx = (SHA1_CTX *) ctx; + + SHA1Update(sha1_ctx, data, size); + return 1; +} + +int +_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20]) +{ + SHA1_CTX *sha1_ctx = (SHA1_CTX *) ctx; + + SHA1Final(result, sha1_ctx); + free(sha1_ctx); + return 1; +} + +#elif defined(HAVE_SHA1_IN_COMMONCRYPTO) /* Use CommonCrypto for SHA1 */ + +#include <CommonCrypto/CommonDigest.h> + +struct mesa_sha1 * +_mesa_sha1_init(void) +{ + CC_SHA1_CTX *ctx = malloc(sizeof(*ctx)); + + if (!ctx) + return NULL; + + CC_SHA1_Init(ctx); + return (struct mesa_sha1 *) ctx; +} + +int +_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size) +{ + CC_SHA1_CTX *sha1_ctx = (CC_SHA1_CTX *) ctx; + + CC_SHA1_Update(sha1_ctx, data, size); + return 1; +} + +int +_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20]) +{ + CC_SHA1_CTX *sha1_ctx = (CC_SHA1_CTX *) ctx; + + CC_SHA1_Final(result, sha1_ctx); + free(sha1_ctx); + return 1; +} + +#elif defined(HAVE_SHA1_IN_CRYPTOAPI) /* Use CryptoAPI for SHA1 */ + +#define WIN32_LEAN_AND_MEAN +#include <windows.h> +#include <wincrypt.h> + +static HCRYPTPROV hProv; + +struct mesa_sha1 * +_mesa_sha1_init(void) +{ + HCRYPTHASH *ctx = malloc(sizeof(*ctx)); + + if (!ctx) + return NULL; + + CryptAcquireContext(&hProv, NULL, MS_DEF_PROV, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT); + CryptCreateHash(hProv, CALG_SHA1, 0, 0, ctx); + return (struct mesa_sha1 *) ctx; +} + +int +_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size) +{ + HCRYPTHASH *hHash = (HCRYPTHASH *) ctx; + + CryptHashData(*hHash, data, size, 0); + return 1; +} + +int +_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20]) +{ + HCRYPTHASH *hHash = (HCRYPTHASH *) ctx; + DWORD len = 20; + + CryptGetHashParam(*hHash, HP_HASHVAL, result, &len, 0); + CryptDestroyHash(*hHash); + CryptReleaseContext(hProv, 0); + free(ctx); + return 1; +} + +#elif defined(HAVE_SHA1_IN_LIBNETTLE) /* Use libnettle for SHA1 */ + +#include <nettle/sha.h> + +struct mesa_sha1 * +_mesa_sha1_init(void) +{ + struct sha1_ctx *ctx = malloc(sizeof(*ctx)); + + if (!ctx) + return NULL; + sha1_init(ctx); + return (struct mesa_sha1 *) ctx; +} + +int +_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size) +{ + sha1_update((struct sha1_ctx *) ctx, size, data); + return 1; +} + +int +_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20]) +{ + sha1_digest((struct sha1_ctx *) ctx, 20, result); + free(ctx); + return 1; +} + +#elif defined(HAVE_SHA1_IN_LIBGCRYPT) /* Use libgcrypt for SHA1 */ + +#include <gcrypt.h> + +struct mesa_sha1 * +_mesa_sha1_init(void) +{ + static int init; + gcry_md_hd_t h; + gcry_error_t err; + + if (!init) { + if (!gcry_check_version(NULL)) + return NULL; + gcry_control(GCRYCTL_DISABLE_SECMEM, 0); + gcry_control(GCRYCTL_INITIALIZATION_FINISHED, 0); + init = 1; + } + + err = gcry_md_open(&h, GCRY_MD_SHA1, 0); + if (err) + return NULL; + return (struct mesa_sha1 *) h; +} + +int +_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size) +{ + gcry_md_hd_t h = (gcry_md_hd_t) ctx; + + gcry_md_write(h, data, size); + return 1; +} + +int +_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20]) +{ + gcry_md_hd_t h = (gcry_md_hd_t) ctx; + + memcpy(result, gcry_md_read(h, GCRY_MD_SHA1), 20); + gcry_md_close(h); + return 1; +} + +#elif defined(HAVE_SHA1_IN_LIBSHA1) /* Use libsha1 */ + +#include <libsha1.h> + +struct mesa_sha1 * +_mesa_sha1_init(void) +{ + sha1_ctx *ctx = malloc(sizeof(*ctx)); + + if (!ctx) + return NULL; + sha1_begin(ctx); + return (struct mesa_sha1 *) ctx; +} + +int +_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size) +{ + sha1_hash(data, size, (sha1_ctx *) ctx); + return 1; +} + +int +_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20]) +{ + sha1_end(result, (sha1_ctx *) ctx); + free(ctx); + return 1; +} + +#else /* Use OpenSSL's libcrypto */ + +#include <stddef.h> /* buggy openssl/sha.h wants size_t */ +#include <openssl/sha.h> + +struct mesa_sha1 * +_mesa_sha1_init(void) +{ + int ret; + SHA_CTX *ctx = malloc(sizeof(*ctx)); + + if (!ctx) + return NULL; + ret = SHA1_Init(ctx); + if (!ret) { + free(ctx); + return NULL; + } + return (struct mesa_sha1 *) ctx; +} + +int +_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size) +{ + int ret; + SHA_CTX *sha_ctx = (SHA_CTX *) ctx; + + ret = SHA1_Update(sha_ctx, data, size); + if (!ret) + free(sha_ctx); + return ret; +} + +int +_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20]) +{ + int ret; + SHA_CTX *sha_ctx = (SHA_CTX *) ctx; + + ret = SHA1_Final(result, (SHA_CTX *) sha_ctx); + free(sha_ctx); + return ret; +} + +#endif + +void +_mesa_sha1_compute(const void *data, size_t size, unsigned char result[20]) +{ + struct mesa_sha1 *ctx; + + ctx = _mesa_sha1_init(); + _mesa_sha1_update(ctx, data, size); + _mesa_sha1_final(ctx, result); +} + +char * +_mesa_sha1_format(char *buf, const unsigned char *sha1) +{ + static const char hex_digits[] = "0123456789abcdef"; + int i; + + for (i = 0; i < 40; i += 2) { + buf[i] = hex_digits[sha1[i >> 1] >> 4]; + buf[i + 1] = hex_digits[sha1[i >> 1] & 0x0f]; + } + buf[i] = '\0'; + + return buf; +} diff --git a/mesalib/src/util/mesa-sha1.h b/mesalib/src/util/mesa-sha1.h new file mode 100644 index 000000000..1599405cd --- /dev/null +++ b/mesalib/src/util/mesa-sha1.h @@ -0,0 +1,53 @@ +/* Copyright © 2014 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. + */ + +#ifndef SHA1_H +#define SHA1_H + +#ifdef __cplusplus +extern "C" { +#endif + +#include <stdlib.h> + +struct mesa_sha1; + +struct mesa_sha1 * +_mesa_sha1_init(void); + +int +_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size); + +int +_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20]); + +char * +_mesa_sha1_format(char *buf, const unsigned char *sha1); + +void +_mesa_sha1_compute(const void *data, size_t size, unsigned char result[20]); + +#ifdef __cplusplus +} /* extern C */ +#endif + +#endif diff --git a/mesalib/src/util/register_allocate.c b/mesalib/src/util/register_allocate.c index af7a20c09..684ee5d6c 100644 --- a/mesalib/src/util/register_allocate.c +++ b/mesalib/src/util/register_allocate.c @@ -76,7 +76,7 @@ #include "main/imports.h" #include "main/macros.h" #include "main/mtypes.h" -#include "main/bitset.h" +#include "util/bitset.h" #include "register_allocate.h" #define NO_REG ~0U diff --git a/mesalib/src/util/set.c b/mesalib/src/util/set.c new file mode 100644 index 000000000..f01f8699a --- /dev/null +++ b/mesalib/src/util/set.c @@ -0,0 +1,391 @@ +/* + * Copyright © 2009-2012 Intel Corporation + * Copyright © 1988-2004 Keith Packard and Bart Massey. + * + * 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. + * + * Except as contained in this notice, the names of the authors + * or their institutions shall not be used in advertising or + * otherwise to promote the sale, use or other dealings in this + * Software without prior written authorization from the + * authors. + * + * Authors: + * Eric Anholt <eric@anholt.net> + * Keith Packard <keithp@keithp.com> + */ + +#include <stdlib.h> +#include <assert.h> + +#include "macros.h" +#include "ralloc.h" +#include "set.h" + +/* + * From Knuth -- a good choice for hash/rehash values is p, p-2 where + * p and p-2 are both prime. These tables are sized to have an extra 10% + * free to avoid exponential performance degradation as the hash table fills + */ + +uint32_t deleted_key_value; +const void *deleted_key = &deleted_key_value; + +static const struct { + uint32_t max_entries, size, rehash; +} hash_sizes[] = { + { 2, 5, 3 }, + { 4, 7, 5 }, + { 8, 13, 11 }, + { 16, 19, 17 }, + { 32, 43, 41 }, + { 64, 73, 71 }, + { 128, 151, 149 }, + { 256, 283, 281 }, + { 512, 571, 569 }, + { 1024, 1153, 1151 }, + { 2048, 2269, 2267 }, + { 4096, 4519, 4517 }, + { 8192, 9013, 9011 }, + { 16384, 18043, 18041 }, + { 32768, 36109, 36107 }, + { 65536, 72091, 72089 }, + { 131072, 144409, 144407 }, + { 262144, 288361, 288359 }, + { 524288, 576883, 576881 }, + { 1048576, 1153459, 1153457 }, + { 2097152, 2307163, 2307161 }, + { 4194304, 4613893, 4613891 }, + { 8388608, 9227641, 9227639 }, + { 16777216, 18455029, 18455027 }, + { 33554432, 36911011, 36911009 }, + { 67108864, 73819861, 73819859 }, + { 134217728, 147639589, 147639587 }, + { 268435456, 295279081, 295279079 }, + { 536870912, 590559793, 590559791 }, + { 1073741824, 1181116273, 1181116271 }, + { 2147483648ul, 2362232233ul, 2362232231ul } +}; + +static int +entry_is_free(struct set_entry *entry) +{ + return entry->key == NULL; +} + +static int +entry_is_deleted(struct set_entry *entry) +{ + return entry->key == deleted_key; +} + +static int +entry_is_present(struct set_entry *entry) +{ + return entry->key != NULL && entry->key != deleted_key; +} + +struct set * +_mesa_set_create(void *mem_ctx, + uint32_t (*key_hash_function)(const void *key), + bool (*key_equals_function)(const void *a, + const void *b)) +{ + struct set *ht; + + ht = ralloc(mem_ctx, struct set); + if (ht == NULL) + return NULL; + + ht->size_index = 0; + ht->size = hash_sizes[ht->size_index].size; + ht->rehash = hash_sizes[ht->size_index].rehash; + ht->max_entries = hash_sizes[ht->size_index].max_entries; + ht->key_hash_function = key_hash_function; + ht->key_equals_function = key_equals_function; + ht->table = rzalloc_array(ht, struct set_entry, ht->size); + ht->entries = 0; + ht->deleted_entries = 0; + + if (ht->table == NULL) { + ralloc_free(ht); + return NULL; + } + + return ht; +} + +/** + * Frees the given set. + * + * If delete_function is passed, it gets called on each entry present before + * freeing. + */ +void +_mesa_set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entry)) +{ + if (!ht) + return; + + if (delete_function) { + struct set_entry *entry; + + set_foreach (ht, entry) { + delete_function(entry); + } + } + ralloc_free(ht->table); + ralloc_free(ht); +} + +/** + * Finds a set entry with the given key and hash of that key. + * + * Returns NULL if no entry is found. + */ +static struct set_entry * +set_search(const struct set *ht, uint32_t hash, const void *key) +{ + uint32_t hash_address; + + hash_address = hash % ht->size; + do { + uint32_t double_hash; + + struct set_entry *entry = ht->table + hash_address; + + if (entry_is_free(entry)) { + return NULL; + } else if (entry_is_present(entry) && entry->hash == hash) { + if (ht->key_equals_function(key, entry->key)) { + return entry; + } + } + + double_hash = 1 + hash % ht->rehash; + + hash_address = (hash_address + double_hash) % ht->size; + } while (hash_address != hash % ht->size); + + return NULL; +} + +struct set_entry * +_mesa_set_search(const struct set *set, const void *key) +{ + assert(set->key_hash_function); + return set_search(set, set->key_hash_function(key), key); +} + +struct set_entry * +_mesa_set_search_pre_hashed(const struct set *set, uint32_t hash, + const void *key) +{ + assert(set->key_hash_function == NULL || + hash == set->key_hash_function(key)); + return set_search(set, hash, key); +} + +static struct set_entry * +set_add(struct set *ht, uint32_t hash, const void *key); + +static void +set_rehash(struct set *ht, unsigned new_size_index) +{ + struct set old_ht; + struct set_entry *table, *entry; + + if (new_size_index >= ARRAY_SIZE(hash_sizes)) + return; + + table = rzalloc_array(ht, struct set_entry, + hash_sizes[new_size_index].size); + if (table == NULL) + return; + + old_ht = *ht; + + ht->table = table; + ht->size_index = new_size_index; + ht->size = hash_sizes[ht->size_index].size; + ht->rehash = hash_sizes[ht->size_index].rehash; + ht->max_entries = hash_sizes[ht->size_index].max_entries; + ht->entries = 0; + ht->deleted_entries = 0; + + for (entry = old_ht.table; + entry != old_ht.table + old_ht.size; + entry++) { + if (entry_is_present(entry)) { + set_add(ht, entry->hash, entry->key); + } + } + + ralloc_free(old_ht.table); +} + +/** + * Inserts the key with the given hash into the table. + * + * Note that insertion may rearrange the table on a resize or rehash, + * so previously found hash_entries are no longer valid after this function. + */ +static struct set_entry * +set_add(struct set *ht, uint32_t hash, const void *key) +{ + uint32_t hash_address; + struct set_entry *available_entry = NULL; + + if (ht->entries >= ht->max_entries) { + set_rehash(ht, ht->size_index + 1); + } else if (ht->deleted_entries + ht->entries >= ht->max_entries) { + set_rehash(ht, ht->size_index); + } + + hash_address = hash % ht->size; + do { + struct set_entry *entry = ht->table + hash_address; + uint32_t double_hash; + + if (!entry_is_present(entry)) { + /* Stash the first available entry we find */ + if (available_entry == NULL) + available_entry = entry; + if (entry_is_free(entry)) + break; + } + + /* Implement replacement when another insert happens + * with a matching key. This is a relatively common + * feature of hash tables, with the alternative + * generally being "insert the new value as well, and + * return it first when the key is searched for". + * + * Note that the hash table doesn't have a delete callback. + * If freeing of old keys is required to avoid memory leaks, + * perform a search before inserting. + */ + if (entry->hash == hash && + ht->key_equals_function(key, entry->key)) { + entry->key = key; + return entry; + } + + double_hash = 1 + hash % ht->rehash; + + hash_address = (hash_address + double_hash) % ht->size; + } while (hash_address != hash % ht->size); + + if (available_entry) { + if (entry_is_deleted(available_entry)) + ht->deleted_entries--; + available_entry->hash = hash; + available_entry->key = key; + ht->entries++; + return available_entry; + } + + /* We could hit here if a required resize failed. An unchecked-malloc + * application could ignore this result. + */ + return NULL; +} + +struct set_entry * +_mesa_set_add(struct set *set, const void *key) +{ + assert(set->key_hash_function); + return set_add(set, set->key_hash_function(key), key); +} + +struct set_entry * +_mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key) +{ + assert(set->key_hash_function == NULL || + hash == set->key_hash_function(key)); + return set_add(set, hash, key); +} + +/** + * This function deletes the given hash table entry. + * + * Note that deletion doesn't otherwise modify the table, so an iteration over + * the table deleting entries is safe. + */ +void +_mesa_set_remove(struct set *ht, struct set_entry *entry) +{ + if (!entry) + return; + + entry->key = deleted_key; + ht->entries--; + ht->deleted_entries++; +} + +/** + * This function is an iterator over the hash table. + * + * Pass in NULL for the first entry, as in the start of a for loop. Note that + * an iteration over the table is O(table_size) not O(entries). + */ +struct set_entry * +_mesa_set_next_entry(const struct set *ht, struct set_entry *entry) +{ + if (entry == NULL) + entry = ht->table; + else + entry = entry + 1; + + for (; entry != ht->table + ht->size; entry++) { + if (entry_is_present(entry)) { + return entry; + } + } + + return NULL; +} + +struct set_entry * +_mesa_set_random_entry(struct set *ht, + int (*predicate)(struct set_entry *entry)) +{ + struct set_entry *entry; + uint32_t i = rand() % ht->size; + + if (ht->entries == 0) + return NULL; + + for (entry = ht->table + i; entry != ht->table + ht->size; entry++) { + if (entry_is_present(entry) && + (!predicate || predicate(entry))) { + return entry; + } + } + + for (entry = ht->table; entry != ht->table + i; entry++) { + if (entry_is_present(entry) && + (!predicate || predicate(entry))) { + return entry; + } + } + + return NULL; +} diff --git a/mesalib/src/util/set.h b/mesalib/src/util/set.h new file mode 100644 index 000000000..9acd2c28c --- /dev/null +++ b/mesalib/src/util/set.h @@ -0,0 +1,100 @@ +/* + * 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 <eric@anholt.net> + * + */ + +#ifndef _SET_H +#define _SET_H + +#include <inttypes.h> +#include <stdbool.h> + +#ifdef __cplusplus +extern "C" { +#endif + +struct set_entry { + uint32_t hash; + const void *key; +}; + +struct set { + void *mem_ctx; + struct set_entry *table; + uint32_t (*key_hash_function)(const void *key); + bool (*key_equals_function)(const void *a, const void *b); + uint32_t size; + uint32_t rehash; + uint32_t max_entries; + uint32_t size_index; + uint32_t entries; + uint32_t deleted_entries; +}; + +struct set * +_mesa_set_create(void *mem_ctx, + uint32_t (*key_hash_function)(const void *key), + bool (*key_equals_function)(const void *a, + const void *b)); +void +_mesa_set_destroy(struct set *set, + void (*delete_function)(struct set_entry *entry)); + +struct set_entry * +_mesa_set_add(struct set *set, const void *key); +struct set_entry * +_mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key); + +struct set_entry * +_mesa_set_search(const struct set *set, const void *key); +struct set_entry * +_mesa_set_search_pre_hashed(const struct set *set, uint32_t hash, + const void *key); + +void +_mesa_set_remove(struct set *set, struct set_entry *entry); + +struct set_entry * +_mesa_set_next_entry(const struct set *set, struct set_entry *entry); + +struct set_entry * +_mesa_set_random_entry(struct set *set, + int (*predicate)(struct set_entry *entry)); + +/** + * This foreach function is safe against deletion, but not against + * insertion (which may rehash the set, making entry a dangling + * pointer). + */ +#define set_foreach(set, entry) \ + for (entry = _mesa_set_next_entry(set, NULL); \ + entry != NULL; \ + entry = _mesa_set_next_entry(set, entry)) + +#ifdef __cplusplus +} /* extern C */ +#endif + +#endif /* _SET_H */ diff --git a/mesalib/src/util/simple_list.h b/mesalib/src/util/simple_list.h new file mode 100644 index 000000000..5f261612a --- /dev/null +++ b/mesalib/src/util/simple_list.h @@ -0,0 +1,211 @@ +/** + * \file simple_list.h + * Simple macros for type-safe, intrusive lists. + * + * Intended to work with a list sentinal which is created as an empty + * list. Insert & delete are O(1). + * + * \author + * (C) 1997, Keith Whitwell + */ + +/* + * Mesa 3-D graphics library + * + * Copyright (C) 1999-2001 Brian Paul All Rights Reserved. + * + * 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 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. + */ + + +#ifndef _SIMPLE_LIST_H +#define _SIMPLE_LIST_H + +#ifdef __cplusplus +extern "C" { +#endif + +struct simple_node { + struct simple_node *next; + struct simple_node *prev; +}; + +/** + * Remove an element from list. + * + * \param elem element to remove. + */ +#define remove_from_list(elem) \ +do { \ + (elem)->next->prev = (elem)->prev; \ + (elem)->prev->next = (elem)->next; \ + make_empty_list(elem); \ +} while (0) + +/** + * Insert an element to the list head. + * + * \param list list. + * \param elem element to insert. + */ +#define insert_at_head(list, elem) \ +do { \ + (elem)->prev = list; \ + (elem)->next = (list)->next; \ + (list)->next->prev = elem; \ + (list)->next = elem; \ +} while(0) + +/** + * Insert an element to the list tail. + * + * \param list list. + * \param elem element to insert. + */ +#define insert_at_tail(list, elem) \ +do { \ + (elem)->next = list; \ + (elem)->prev = (list)->prev; \ + (list)->prev->next = elem; \ + (list)->prev = elem; \ +} while(0) + +/** + * Move an element to the list head. + * + * \param list list. + * \param elem element to move. + */ +#define move_to_head(list, elem) \ +do { \ + remove_from_list(elem); \ + insert_at_head(list, elem); \ +} while (0) + +/** + * Move an element to the list tail. + * + * \param list list. + * \param elem element to move. + */ +#define move_to_tail(list, elem) \ +do { \ + remove_from_list(elem); \ + insert_at_tail(list, elem); \ +} while (0) + +/** + * Make a empty list empty. + * + * \param sentinal list (sentinal element). + */ +#define make_empty_list(sentinal) \ +do { \ + (sentinal)->next = sentinal; \ + (sentinal)->prev = sentinal; \ +} while (0) + +/** + * Get list first element. + * + * \param list list. + * + * \return pointer to first element. + */ +#define first_elem(list) ((list)->next) + +/** + * Get list last element. + * + * \param list list. + * + * \return pointer to last element. + */ +#define last_elem(list) ((list)->prev) + +/** + * Get next element. + * + * \param elem element. + * + * \return pointer to next element. + */ +#define next_elem(elem) ((elem)->next) + +/** + * Get previous element. + * + * \param elem element. + * + * \return pointer to previous element. + */ +#define prev_elem(elem) ((elem)->prev) + +/** + * Test whether element is at end of the list. + * + * \param list list. + * \param elem element. + * + * \return non-zero if element is at end of list, or zero otherwise. + */ +#define at_end(list, elem) ((elem) == (list)) + +/** + * Test if a list is empty. + * + * \param list list. + * + * \return non-zero if list empty, or zero otherwise. + */ +#define is_empty_list(list) ((list)->next == (list)) + +/** + * Walk through the elements of a list. + * + * \param ptr pointer to the current element. + * \param list list. + * + * \note It should be followed by a { } block or a single statement, as in a \c + * for loop. + */ +#define foreach(ptr, list) \ + for( ptr=(list)->next ; ptr!=list ; ptr=(ptr)->next ) + +/** + * Walk through the elements of a list. + * + * Same as #foreach but lets you unlink the current value during a list + * traversal. Useful for freeing a list, element by element. + * + * \param ptr pointer to the current element. + * \param t temporary pointer. + * \param list list. + * + * \note It should be followed by a { } block or a single statement, as in a \c + * for loop. + */ +#define foreach_s(ptr, t, list) \ + for(ptr=(list)->next,t=(ptr)->next; list != ptr; ptr=t, t=(t)->next) + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/mesalib/src/util/u_atomic.h b/mesalib/src/util/u_atomic.h index 401003638..d15398e1e 100644 --- a/mesalib/src/util/u_atomic.h +++ b/mesalib/src/util/u_atomic.h @@ -39,6 +39,7 @@ #define p_atomic_dec_zero(v) (__sync_sub_and_fetch((v), 1) == 0) #define p_atomic_inc(v) (void) __sync_add_and_fetch((v), 1) #define p_atomic_dec(v) (void) __sync_sub_and_fetch((v), 1) +#define p_atomic_add(v, i) (void) __sync_add_and_fetch((v), (i)) #define p_atomic_inc_return(v) __sync_add_and_fetch((v), 1) #define p_atomic_dec_return(v) __sync_sub_and_fetch((v), 1) #define p_atomic_cmpxchg(v, old, _new) \ @@ -60,6 +61,7 @@ #define p_atomic_dec_zero(_v) (p_atomic_dec_return(_v) == 0) #define p_atomic_inc(_v) ((void) p_atomic_inc_return(_v)) #define p_atomic_dec(_v) ((void) p_atomic_dec_return(_v)) +#define p_atomic_add(_v, _i) (*(_v) = *(_v) + (_i)) #define p_atomic_inc_return(_v) (++(*(_v))) #define p_atomic_dec_return(_v) (--(*(_v))) #define p_atomic_cmpxchg(_v, _old, _new) (*(_v) == (_old) ? (*(_v) = (_new), (_old)) : *(_v)) @@ -71,8 +73,8 @@ #define PIPE_ATOMIC "MSVC Intrinsics" -/* We use the Windows header's Interlocked* functions instead of the - * _Interlocked* intrinsics wherever we can, as support for the latter varies +/* We use the Windows header's Interlocked*64 functions instead of the + * _Interlocked*64 intrinsics wherever we can, as support for the latter varies * with target CPU, whereas Windows headers take care of all portability * issues: using intrinsics where available, falling back to library * implementations where not. @@ -84,7 +86,64 @@ #include <intrin.h> #include <assert.h> -#pragma intrinsic(_InterlockedCompareExchange8) +#if _MSC_VER < 1600 + +/* Implement _InterlockedCompareExchange8 in terms of _InterlockedCompareExchange16 */ +static __inline char +_InterlockedCompareExchange8(char volatile *destination8, char exchange8, char comparand8) +{ + INT_PTR destinationAddr = (INT_PTR)destination8; + short volatile *destination16 = (short volatile *)(destinationAddr & ~1); + const short shift8 = (destinationAddr & 1) * 8; + const short mask8 = 0xff << shift8; + short initial16 = *destination16; + char initial8 = initial16 >> shift8; + while (initial8 == comparand8) { + /* initial *destination8 matches, so try exchange it while keeping the + * neighboring byte untouched */ + short exchange16 = (initial16 & ~mask8) | ((short)exchange8 << shift8); + short comparand16 = initial16; + short initial16 = _InterlockedCompareExchange16(destination16, exchange16, comparand16); + if (initial16 == comparand16) { + /* succeeded */ + return comparand8; + } + /* something changed, retry with the new initial value */ + initial8 = initial16 >> shift8; + } + return initial8; +} + +/* Implement _InterlockedExchangeAdd16 in terms of _InterlockedCompareExchange16 */ +static __inline short +_InterlockedExchangeAdd16(short volatile *addend, short value) +{ + short initial = *addend; + short comparand; + do { + short exchange = initial + value; + comparand = initial; + /* if *addend==comparand then *addend=exchange, return original *addend */ + initial = _InterlockedCompareExchange16(addend, exchange, comparand); + } while(initial != comparand); + return comparand; +} + +/* Implement _InterlockedExchangeAdd8 in terms of _InterlockedCompareExchange8 */ +static __inline char +_InterlockedExchangeAdd8(char volatile *addend, char value) +{ + char initial = *addend; + char comparand; + do { + char exchange = initial + value; + comparand = initial; + initial = _InterlockedCompareExchange8(addend, exchange, comparand); + } while(initial != comparand); + return comparand; +} + +#endif /* _MSC_VER < 1600 */ /* MSVC supports decltype keyword, but it's only supported on C++ and doesn't * quite work here; and if a C++-only solution is worthwhile, then it would be @@ -102,25 +161,32 @@ ((void) p_atomic_inc_return(_v)) #define p_atomic_inc_return(_v) (\ - sizeof *(_v) == sizeof(short) ? InterlockedIncrement16((short *) (_v)) : \ - sizeof *(_v) == sizeof(long) ? InterlockedIncrement ((long *) (_v)) : \ - sizeof *(_v) == sizeof(__int64) ? InterlockedIncrement64((__int64 *)(_v)) : \ + sizeof *(_v) == sizeof(short) ? _InterlockedIncrement16((short *) (_v)) : \ + sizeof *(_v) == sizeof(long) ? _InterlockedIncrement ((long *) (_v)) : \ + sizeof *(_v) == sizeof(__int64) ? InterlockedIncrement64 ((__int64 *)(_v)) : \ (assert(!"should not get here"), 0)) #define p_atomic_dec(_v) \ ((void) p_atomic_dec_return(_v)) #define p_atomic_dec_return(_v) (\ - sizeof *(_v) == sizeof(short) ? InterlockedDecrement16((short *) (_v)) : \ - sizeof *(_v) == sizeof(long) ? InterlockedDecrement ((long *) (_v)) : \ - sizeof *(_v) == sizeof(__int64) ? InterlockedDecrement64((__int64 *)(_v)) : \ + sizeof *(_v) == sizeof(short) ? _InterlockedDecrement16((short *) (_v)) : \ + sizeof *(_v) == sizeof(long) ? _InterlockedDecrement ((long *) (_v)) : \ + sizeof *(_v) == sizeof(__int64) ? InterlockedDecrement64 ((__int64 *)(_v)) : \ + (assert(!"should not get here"), 0)) + +#define p_atomic_add(_v, _i) (\ + sizeof *(_v) == sizeof(char) ? _InterlockedExchangeAdd8 ((char *) (_v), (_i)) : \ + sizeof *(_v) == sizeof(short) ? _InterlockedExchangeAdd16((short *) (_v), (_i)) : \ + sizeof *(_v) == sizeof(long) ? _InterlockedExchangeAdd ((long *) (_v), (_i)) : \ + sizeof *(_v) == sizeof(__int64) ? InterlockedExchangeAdd64((__int64 *)(_v), (_i)) : \ (assert(!"should not get here"), 0)) #define p_atomic_cmpxchg(_v, _old, _new) (\ - sizeof *(_v) == sizeof(char) ? _InterlockedCompareExchange8((char *) (_v), (char) (_new), (char) (_old)) : \ - sizeof *(_v) == sizeof(short) ? InterlockedCompareExchange16((short *) (_v), (short) (_new), (short) (_old)) : \ - sizeof *(_v) == sizeof(long) ? InterlockedCompareExchange ((long *) (_v), (long) (_new), (long) (_old)) : \ - sizeof *(_v) == sizeof(__int64) ? InterlockedCompareExchange64((__int64 *)(_v), (__int64)(_new), (__int64)(_old)) : \ + sizeof *(_v) == sizeof(char) ? _InterlockedCompareExchange8 ((char *) (_v), (char) (_new), (char) (_old)) : \ + sizeof *(_v) == sizeof(short) ? _InterlockedCompareExchange16((short *) (_v), (short) (_new), (short) (_old)) : \ + sizeof *(_v) == sizeof(long) ? _InterlockedCompareExchange ((long *) (_v), (long) (_new), (long) (_old)) : \ + sizeof *(_v) == sizeof(__int64) ? InterlockedCompareExchange64 ((__int64 *)(_v), (__int64)(_new), (__int64)(_old)) : \ (assert(!"should not get here"), 0)) #endif @@ -149,7 +215,7 @@ sizeof(*v) == sizeof(uint64_t) ? atomic_inc_64((uint64_t *)(v)) : \ (assert(!"should not get here"), 0)) -#define p_atomic_inc_return(v) ((typeof(*v)) \ +#define p_atomic_inc_return(v) ((__typeof(*v)) \ sizeof(*v) == sizeof(uint8_t) ? atomic_inc_8_nv ((uint8_t *)(v)) : \ sizeof(*v) == sizeof(uint16_t) ? atomic_inc_16_nv((uint16_t *)(v)) : \ sizeof(*v) == sizeof(uint32_t) ? atomic_inc_32_nv((uint32_t *)(v)) : \ @@ -163,14 +229,21 @@ sizeof(*v) == sizeof(uint64_t) ? atomic_dec_64((uint64_t *)(v)) : \ (assert(!"should not get here"), 0)) -#define p_atomic_dec_return(v) ((typeof(*v)) \ +#define p_atomic_dec_return(v) ((__typeof(*v)) \ sizeof(*v) == sizeof(uint8_t) ? atomic_dec_8_nv ((uint8_t *)(v)) : \ sizeof(*v) == sizeof(uint16_t) ? atomic_dec_16_nv((uint16_t *)(v)) : \ sizeof(*v) == sizeof(uint32_t) ? atomic_dec_32_nv((uint32_t *)(v)) : \ sizeof(*v) == sizeof(uint64_t) ? atomic_dec_64_nv((uint64_t *)(v)) : \ (assert(!"should not get here"), 0)) -#define p_atomic_cmpxchg(v, old, _new) ((typeof(*v)) \ +#define p_atomic_add(v, i) ((void) \ + sizeof(*v) == sizeof(uint8_t) ? atomic_add_8 ((uint8_t *)(v), (i)) : \ + sizeof(*v) == sizeof(uint16_t) ? atomic_add_16((uint16_t *)(v), (i)) : \ + sizeof(*v) == sizeof(uint32_t) ? atomic_add_32((uint32_t *)(v), (i)) : \ + sizeof(*v) == sizeof(uint64_t) ? atomic_add_64((uint64_t *)(v), (i)) : \ + (assert(!"should not get here"), 0)) + +#define p_atomic_cmpxchg(v, old, _new) ((__typeof(*v)) \ sizeof(*v) == sizeof(uint8_t) ? atomic_cas_8 ((uint8_t *)(v), (uint8_t )(old), (uint8_t )(_new)) : \ sizeof(*v) == sizeof(uint16_t) ? atomic_cas_16((uint16_t *)(v), (uint16_t)(old), (uint16_t)(_new)) : \ sizeof(*v) == sizeof(uint32_t) ? atomic_cas_32((uint32_t *)(v), (uint32_t)(old), (uint32_t)(_new)) : \ diff --git a/mesalib/src/util/u_atomic_test.c b/mesalib/src/util/u_atomic_test.c index 4845e753e..939cfe445 100644 --- a/mesalib/src/util/u_atomic_test.c +++ b/mesalib/src/util/u_atomic_test.c @@ -37,8 +37,9 @@ #include "u_atomic.h" -#define test_atomic_cmpxchg(type, ones) \ - static void test_atomic_cmpxchg_##type (void) { \ +/* Test only assignment-like operations, which are supported on all types */ +#define test_atomic_assign(type, ones) \ + static void test_atomic_assign_##type (void) { \ type v, r; \ \ p_atomic_set(&v, ones); \ @@ -59,14 +60,33 @@ } +/* Test arithmetic operations that are supported on 8 bits integer types */ +#define test_atomic_8bits(type, ones) \ + test_atomic_assign(type, ones) \ + \ + static void test_atomic_8bits_##type (void) { \ + type v, r; \ + \ + test_atomic_assign_##type(); \ + \ + v = 23; \ + p_atomic_add(&v, 42); \ + r = p_atomic_read(&v); \ + assert(r == 65 && "p_atomic_add"); \ + \ + (void) r; \ + } + + +/* Test all operations */ #define test_atomic(type, ones) \ - test_atomic_cmpxchg(type, ones) \ + test_atomic_8bits(type, ones) \ \ static void test_atomic_##type (void) { \ type v, r; \ bool b; \ \ - test_atomic_cmpxchg_##type(); \ + test_atomic_8bits_##type(); \ \ v = 2; \ b = p_atomic_dec_zero(&v); \ @@ -112,9 +132,9 @@ test_atomic(uint32_t, UINT32_C(0xffffffff)) test_atomic(int64_t, INT64_C(-1)) test_atomic(uint64_t, UINT64_C(0xffffffffffffffff)) -test_atomic_cmpxchg(int8_t, INT8_C(-1)) -test_atomic_cmpxchg(uint8_t, UINT8_C(0xff)) -test_atomic_cmpxchg(bool, true) +test_atomic_8bits(int8_t, INT8_C(-1)) +test_atomic_8bits(uint8_t, UINT8_C(0xff)) +test_atomic_assign(bool, true) int main() @@ -129,9 +149,9 @@ main() test_atomic_int64_t(); test_atomic_uint64_t(); - test_atomic_cmpxchg_int8_t(); - test_atomic_cmpxchg_uint8_t(); - test_atomic_cmpxchg_bool(); + test_atomic_8bits_int8_t(); + test_atomic_8bits_uint8_t(); + test_atomic_assign_bool(); return 0; } |