From c2969d7a290eb16a21d097822ce63a89e5c313e5 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 28 Feb 2021 21:29:07 +0100 Subject: Made it possible use full 64-bit size_t range for cmap, by defining CMAP_SIZE_T uint64_t --- stc/ccommon.h | 16 ++++++++++++++-- stc/cmap.h | 25 ++++++++++++++----------- stc/crandom.h | 17 ++--------------- 3 files changed, 30 insertions(+), 28 deletions(-) diff --git a/stc/ccommon.h b/stc/ccommon.h index 77f76bf0..15a7ecdf 100644 --- a/stc/ccommon.h +++ b/stc/ccommon.h @@ -58,9 +58,9 @@ #define _c_RSEQ_N 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 #define _c_APPLY_ARG_N(ARGS) _c_EXPAND(_c_ARG_N ARGS) #define _c_VA_ARG_SIZE(...) _c_EXPAND(_c_APPLY_ARG_N((__VA_ARGS__, _c_RSEQ_N))) -#define _c_OVERLOAD_SELECT(NAME, NUM) _c_CAT( NAME ## _, NUM) +#define _c_SELECT(NAME, NUM) _c_CAT( NAME ## _, NUM) -#define c_MACRO_OVERLOAD(NAME, ...) _c_OVERLOAD_SELECT(NAME, _c_VA_ARG_SIZE(__VA_ARGS__))(__VA_ARGS__) +#define c_MACRO_OVERLOAD(NAME, ...) _c_SELECT(NAME, _c_VA_ARG_SIZE(__VA_ARGS__))(__VA_ARGS__) #define c_static_assert(cond, ...) typedef char _static_assert_[(cond) ? 1 : -1] #define c_container_of(ptr, type, member) \ ((type *)((char *)(ptr) - offsetof(type, member))) @@ -129,4 +129,16 @@ ctype##_del(__arr[__i]); \ } while (0) +#if defined(__SIZEOF_INT128__) + #define c_umul128(a, b, lo, hi) \ + do { __uint128_t _z = (__uint128_t)(a) * (b); \ + *(lo) = (uint64_t)_z, *(hi) = _z >> 64; } while(0) +#elif defined(_MSC_VER) && defined(_WIN64) + #include + #define c_umul128(a, b, lo, hi) (*(lo) = _umul128(a, b, hi), (void)0) +#elif defined(__x86_64__) + #define c_umul128(a, b, lo, hi) \ + asm("mulq %[rhs]" : "=a" (*(lo)), "=d" (*(hi)) \ + : [lhs] "0" (a), [rhs] "rm" (b)) +#endif #endif diff --git a/stc/cmap.h b/stc/cmap.h index d5fae750..c8649f28 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -56,7 +56,7 @@ int main(void) { #include #define _cmap_inits {NULL, NULL, 0, 0, 0.15f, 0.85f} -typedef struct {size_t idx; uint32_t hx;} chash_bucket_t; +typedef struct {size_t idx; uint_fast8_t hx;} chash_bucket_t; #define using_cmap(...) c_MACRO_OVERLOAD(using_cmap, __VA_ARGS__) @@ -347,9 +347,12 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored) #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -#define chash_reduce32(x, N) ((uint32_t) (((uint64_t)(uint32_t)(x) * (N)) >> 32)) -#define chash_entry_index(h, entryPtr) ((entryPtr) - (h).table) -enum {chash_HASH = 0x7f, chash_USED = 0x80}; +#define fastrange_uint32_t(x, n) ((size_t) (((uint32_t)(x)*(uint64_t)(n)) >> 32)) +#ifdef c_umul128 +STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) {uint64_t l,h; c_umul128(x,n,&l,&h); return h;} +#endif +#define chash_index_(h, entryPtr) ((entryPtr) - (h).table) +enum {chash_HASH_ = 0x7f, chash_USED_ = 0x80}; #define _implement_CHASH(X, C, Key, Mapped, keyEqualsRaw, keyHashRaw, \ mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ @@ -382,10 +385,10 @@ enum {chash_HASH = 0x7f, chash_USED = 0x80}; \ STC_DEF chash_bucket_t \ C##_##X##_bucket_(const C##_##X* self, const C##_##X##_rawkey_t* rkeyptr) { \ - uint32_t sx, hash = keyHashRaw(rkeyptr, sizeof(C##_##X##_rawkey_t)); \ - size_t cap = self->bucket_count; \ - chash_bucket_t b = {chash_reduce32(hash, cap), (hash & chash_HASH) | chash_USED}; \ - uint8_t* hashx = self->_hashx; \ + const size_t hash = keyHashRaw(rkeyptr, sizeof(C##_##X##_rawkey_t)); \ + uint_fast8_t sx; size_t cap = self->bucket_count; \ + chash_bucket_t b = {_c_SELECT(fastrange,CMAP_SIZE_T)(hash, cap), (hash & chash_HASH_) | chash_USED_}; \ + const uint8_t* hashx = self->_hashx; \ while ((sx = hashx[b.idx])) { \ if (sx == b.hx) { \ C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(self->table + b.idx)); \ @@ -442,7 +445,7 @@ enum {chash_HASH = 0x7f, chash_USED = 0x80}; C##_##X tmp = { \ c_new_2 (C##_##X##_value_t, newcap), \ (uint8_t *) c_calloc(newcap + 1, sizeof(uint8_t)), \ - self->size, (uint32_t) newcap, \ + self->size, (C##_##X##_size_t) newcap, \ self->min_load_factor, self->max_load_factor \ }; \ /* Rehash: */ \ @@ -462,7 +465,7 @@ enum {chash_HASH = 0x7f, chash_USED = 0x80}; \ STC_DEF void \ C##_##X##_erase_entry(C##_##X* self, C##_##X##_value_t* val) { \ - size_t i = chash_entry_index(*self, val), j = i, k, cap = self->bucket_count; \ + size_t i = chash_index_(*self, val), j = i, k, cap = self->bucket_count; \ C##_##X##_value_t* slot = self->table; \ uint8_t* hashx = self->_hashx; \ C##_##X##_value_del(&slot[i]); \ @@ -471,7 +474,7 @@ enum {chash_HASH = 0x7f, chash_USED = 0x80}; if (! hashx[j]) \ break; \ RawKey r = keyToRaw(KEY_REF_##C(slot + j)); \ - k = chash_reduce32(keyHashRaw(&r, sizeof(RawKey)), cap); \ + k = _c_SELECT(fastrange,CMAP_SIZE_T)(keyHashRaw(&r, sizeof(RawKey)), cap); \ if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \ slot[i] = slot[j], hashx[i] = hashx[j], i = j; \ } \ diff --git a/stc/crandom.h b/stc/crandom.h index 689bf620..5734be26 100644 --- a/stc/crandom.h +++ b/stc/crandom.h @@ -83,24 +83,11 @@ STC_INLINE double stc64_uniformf(stc64_t* rng, stc64_uniformf_t* dist) { return stc64_randf(rng)*dist->range + dist->lower; } -#if defined(__SIZEOF_INT128__) - #define cmul128(a, b, lo, hi) \ - do { __uint128_t _z = (__uint128_t)(a) * (b); \ - *(lo) = (uint64_t)_z, *(hi) = _z >> 64; } while(0) -#elif defined(_MSC_VER) && defined(_WIN64) - #include - #define cmul128(a, b, lo, hi) (*(lo) = _umul128(a, b, hi), (void)0) -#elif defined(__x86_64__) - #define cmul128(a, b, lo, hi) \ - asm("mulq %[rhs]" : "=a" (*(lo)), "=d" (*(hi)) \ - : [lhs] "0" (a), [rhs] "rm" (b)) -#endif - /* Unbiased bounded uniform distribution. */ STC_INLINE int64_t stc64_uniform(stc64_t* rng, stc64_uniform_t* d) { uint64_t lo, hi; -#ifdef cmul128 - do { cmul128(stc64_rand(rng), d->range, &lo, &hi); } while (lo < d->threshold); +#ifdef c_umul128 + do { c_umul128(stc64_rand(rng), d->range, &lo, &hi); } while (lo < d->threshold); #else hi = stc64_rand(rng) % d->range; #endif -- cgit v1.2.3