From d80bf9bb4ef1b5a5a6d4edb550b93b93a75972f4 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 19 Aug 2021 21:39:29 +0200 Subject: Maintenance update. Added stc32_rand() to crandom.h, doc fixes and cqueue.h updated to have its own size counter. --- docs/cset_api.md | 2 +- docs/csset_api.md | 2 +- docs/cstr_api.md | 5 ++++- include/stc/ccommon.h | 4 ++-- include/stc/cqueue.h | 30 +++++++++++++------------- include/stc/crandom.h | 60 +++++++++++++++++++++++++++++++++++---------------- 6 files changed, 65 insertions(+), 38 deletions(-) diff --git a/docs/cset_api.md b/docs/cset_api.md index 31ff2ac6..2c0f4611 100644 --- a/docs/cset_api.md +++ b/docs/cset_api.md @@ -1,4 +1,4 @@ -# STC [cset](../include/stc/cmap.h): Unordered Set +# STC [cset](../include/stc/cset.h): Unordered Set ![Set](pics/set.jpg) A **cset** is an associative container that contains a set of unique objects of type Key. Search, insertion, and removal have average constant-time complexity. See the c++ class diff --git a/docs/csset_api.md b/docs/csset_api.md index 058ffd8e..38e9072e 100644 --- a/docs/csset_api.md +++ b/docs/csset_api.md @@ -1,4 +1,4 @@ -# STC [csset](../include/stc/csmap.h): Sorted Set +# STC [csset](../include/stc/csset.h): Sorted Set ![Set](pics/sset.jpg) A **csset** is an associative container that contains a sorted set of unique objects of type *Key*. Sorting is done using the key comparison function *keyCompare*. Search, removal, and insertion operations have logarithmic complexity. **csset** is implemented as an AA-tree. diff --git a/docs/cstr_api.md b/docs/cstr_api.md index 8c3c104f..adf57209 100644 --- a/docs/cstr_api.md +++ b/docs/cstr_api.md @@ -58,7 +58,6 @@ void cstr_replace_all(cstr* self, const char* find, const char* replace) void cstr_erase(cstr* self, size_t pos); void cstr_erase_n(cstr* self, size_t pos, size_t n); -int cstr_compare(const cstr *s1, const cstr *s2); bool cstr_equals(cstr s, const char* str); bool cstr_equals_s(cstr s, cstr s2); size_t cstr_find(cstr s, const char* needle); @@ -92,9 +91,13 @@ Note that all methods with arguments `(..., const char* str, size_t n)`, `n` mus ```c const char* cstr_toraw(const cstr* self); +int cstr_compare_ref(const cstr *s1, const cstr *s2); +bool cstr_equals_ref(const cstr *s1, const cstr *s2); + int c_rawstr_compare(const char** x, const char** y); bool c_rawstr_equals(const char** x, const char** y); uint64_t c_rawstr_hash(const char* const* x, size_t ignored); + int c_strncasecmp(const char* str1, const char* str2, size_t n); char* c_strnstrn(const char* str, const char* needle, size_t slen, size_t nlen); char* c_strncasestrn(const char* str, const char* needle, size_t slen, size_t nlen); diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index 48fae679..cdfb1e61 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -45,8 +45,8 @@ # define STC_LIBRARY_ONLY(...) __VA_ARGS__ # define STC_STATIC_ONLY(...) #else -# define STC_API static inline -# define STC_DEF static inline +# define STC_API static +# define STC_DEF static # define STC_LIBRARY_ONLY(...) # define STC_STATIC_ONLY(...) __VA_ARGS__ #endif diff --git a/include/stc/cqueue.h b/include/stc/cqueue.h index 464b6383..b89291c8 100644 --- a/include/stc/cqueue.h +++ b/include/stc/cqueue.h @@ -60,33 +60,33 @@ _c_using_cqueue(cqueue_##X, ctype) #define _c_using_cqueue(CX, ctype) \ - typedef ctype CX; \ + typedef struct { ctype rep; size_t size; } CX; \ typedef ctype##_value_t CX##_value_t; \ typedef ctype##_rawvalue_t CX##_rawvalue_t; \ typedef ctype##_iter_t CX##_iter_t; \ \ - STC_INLINE CX CX##_init(void) {return ctype##_init();} \ - STC_INLINE CX CX##_clone(CX q) {return ctype##_clone(q);} \ + STC_INLINE CX CX##_init(void) {return c_make(CX){ctype##_init(), 0};} \ + STC_INLINE CX CX##_clone(CX q) {return c_make(CX){ctype##_clone(q.rep), q.size};} \ STC_INLINE CX##_value_t CX##_value_clone(CX##_value_t val) \ {return ctype##_value_clone(val);} \ - STC_INLINE void CX##_clear(CX* self) {ctype##_clear(self);} \ - STC_INLINE void CX##_del(CX* self) {ctype##_del(self);} \ + STC_INLINE void CX##_clear(CX* self) {ctype##_clear(&self->rep); self->size = 0;} \ + STC_INLINE void CX##_del(CX* self) {ctype##_del(&self->rep);} \ \ - STC_INLINE size_t CX##_size(CX q) {return ctype##_size(q);} \ - STC_INLINE bool CX##_empty(CX q) {return ctype##_empty(q);} \ - STC_INLINE CX##_value_t* CX##_front(const CX* self) {return ctype##_front(self);} \ - STC_INLINE CX##_value_t* CX##_back(const CX* self) {return ctype##_back(self);} \ + STC_INLINE size_t CX##_size(CX q) {return q.size;} \ + STC_INLINE bool CX##_empty(CX q) {return q.size == 0;} \ + STC_INLINE CX##_value_t* CX##_front(const CX* self) {return ctype##_front(&self->rep);} \ + STC_INLINE CX##_value_t* CX##_back(const CX* self) {return ctype##_back(&self->rep);} \ \ - STC_INLINE void CX##_pop(CX* self) {ctype##_pop_front(self);} \ + STC_INLINE void CX##_pop(CX* self) {ctype##_pop_front(&self->rep); --self->size;} \ STC_INLINE void CX##_push(CX* self, ctype##_value_t value) \ - {ctype##_push_back(self, value);} \ + {ctype##_push_back(&self->rep, value); ++self->size;} \ STC_INLINE void CX##_emplace(CX* self, CX##_rawvalue_t raw) \ - {ctype##_emplace_back(self, raw);} \ + {ctype##_emplace_back(&self->rep, raw); ++self->size;} \ STC_INLINE void CX##_emplace_items(CX *self, const CX##_rawvalue_t arr[], size_t n) \ - {ctype##_emplace_items(self, arr, n);} \ + {ctype##_emplace_items(&self->rep, arr, n); self->size += n;} \ \ - STC_INLINE CX##_iter_t CX##_begin(const CX* self) {return ctype##_begin(self);} \ - STC_INLINE CX##_iter_t CX##_end(const CX* self) {return ctype##_end(self);} \ + STC_INLINE CX##_iter_t CX##_begin(const CX* self) {return ctype##_begin(&self->rep);} \ + STC_INLINE CX##_iter_t CX##_end(const CX* self) {return ctype##_end(&self->rep);} \ STC_INLINE void CX##_next(CX##_iter_t* it) {ctype##_next(it);} \ struct stc_trailing_semicolon diff --git a/include/stc/crandom.h b/include/stc/crandom.h index 3e911d93..7be7ea6c 100644 --- a/include/stc/crandom.h +++ b/include/stc/crandom.h @@ -43,37 +43,48 @@ int main() { #include #include -typedef struct {uint64_t state[5];} stc64_t; -typedef struct {int64_t lower; uint64_t range, threshold;} stc64_uniform_t; -typedef struct {double lower, range;} stc64_uniformf_t; -typedef struct {double mean, stddev, next; unsigned has_next;} stc64_normalf_t; +typedef struct { uint64_t state[5]; } stc64_t; +typedef struct { uint32_t state[5]; } stc32_t; +typedef struct { int64_t lower; uint64_t range, threshold; } stc64_uniform_t; +typedef struct { double lower, range; } stc64_uniformf_t; +typedef struct { double mean, stddev, next; unsigned has_next; } stc64_normalf_t; /* PRNG stc64. * Very fast PRNG suited for parallel usage with Weyl-sequence parameter. * 320-bit state, 256 bit is mutable. - * Noticable faster than xoshiro and pcg, but slighly slower than wyrand64, - * which only has a single 64-bit state and therefore unfit when - * multiple threads are required. + * Noticable faster than xoshiro and pcg, slighly slower than wyrand64 and + * Romu, but these have restricted capacity for larger parallel jobs or unknown minimum periods. * stc64 supports 2^63 unique threads with a minimum 2^64 period lengths each. - * Passes PractRand tested up to 8TB output, Vigna's Hamming weight test, - * and simple correlation tests, i.e. interleaved streams with one-bit diff state. - * The 16-bit version with LR=6, RS=5, LS=3 passes PractRand to multiple TB input. + * Passes all statistical tests, e.g PractRand and correlation tests, i.e. interleaved + * streams with one-bit diff state. Even the 16-bit version (LR=6, RS=5, LS=3) passes + * PractRand to multiple TB input. */ /* Global STC64 PRNG */ STC_API void stc64_srandom(uint64_t seed); STC_API uint64_t stc64_random(void); -/* STC64 PRNG state */ -STC_API stc64_t stc64_init(uint64_t seed); + +/* Init with sequence number */ STC_API stc64_t stc64_with_seq(uint64_t seed, uint64_t seq); +STC_API stc32_t stc32_with_seq(uint32_t seed, uint32_t seq); + /* Int64 uniform distributed RNG, range [low, high]. */ STC_API stc64_uniform_t stc64_uniform_init(int64_t low, int64_t high); + /* Float64 uniform distributed RNG, range [low, high). */ STC_API stc64_uniformf_t stc64_uniformf_init(double low, double high); + /* Normal distribution (double) */ STC_API stc64_normalf_t stc64_normalf_init(double mean, double stddev); STC_API double stc64_normalf(stc64_t* rng, stc64_normalf_t* dist); +STC_INLINE stc64_t stc64_init(uint64_t seed) { + return stc64_with_seq(seed, seed + 0x3504f333d3aa0b37); +} + +STC_INLINE stc32_t stc32_init(uint32_t seed) { + return stc32_with_seq(seed, seed + 0xd3aa0b37); +} STC_INLINE uint64_t stc64_rand(stc64_t* rng) { uint64_t *s = rng->state; enum {LR=24, RS=11, LS=3}; @@ -84,6 +95,15 @@ STC_INLINE uint64_t stc64_rand(stc64_t* rng) { return result; } +STC_INLINE uint32_t stc32_rand(stc32_t* rng) { + uint32_t *s = rng->state; enum {LR=21, RS=9, LS=3}; + const uint32_t result = (s[0] ^ (s[3] += s[4])) + s[1]; + s[0] = s[1] ^ (s[1] >> RS); + s[1] = s[2] + (s[2] << LS); + s[2] = ((s[2] << LR) | (s[2] >> (32 - LR))) + result; + return result; +} + /* Float64 random number in range [0.0, 1.0). */ STC_INLINE double stc64_randf(stc64_t* rng) { union {uint64_t i; double f;} u = {0x3FF0000000000000ull | (stc64_rand(rng) >> 12)}; @@ -125,14 +145,18 @@ STC_DEF uint64_t stc64_random(void) { return stc64_rand(&stc64_global); } -STC_DEF stc64_t stc64_init(uint64_t seed) { - return stc64_with_seq(seed, seed + 0x3504f333d3aa0b34); -} - /* rng.state[4] must be odd */ STC_DEF stc64_t stc64_with_seq(uint64_t seed, uint64_t seq) { - stc64_t rng = {{seed, seed, seed, seed, (seq << 1) | 1}}; - for (int i = 0; i < 12; ++i) stc64_rand(&rng); + stc64_t rng = {{seed, seed+0x26aa069ea2fb1a4d, seed+0x70c72c95cd592d04, + seed+0x504f333d3aa0b359, (seq << 1) | 1}}; + for (int i = 0; i < 6; ++i) stc64_rand(&rng); + return rng; +} + +STC_DEF stc32_t stc32_with_seq(uint32_t seed, uint32_t seq) { + stc32_t rng = {{seed, seed+0x26aa069e, seed+0xa2fb1a4d, + seed+0x70c72c95, (seq << 1) | 1}}; + for (int i = 0; i < 6; ++i) stc32_rand(&rng); return rng; } -- cgit v1.2.3