From 3bf571bd7f0c8eface28bb5d2b7607d934865e00 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 30 Jul 2020 09:59:24 +0200 Subject: Renamed cvecpq.h to cvec_pq.h and changed API. Added pqueue initialization example in inits.c. Documented my 64bit PRNG engine. --- stc/crand.h | 29 +++++++------- stc/cvec_pq.h | 125 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ stc/cvecpq.h | 122 -------------------------------------------------------- 3 files changed, 140 insertions(+), 136 deletions(-) create mode 100644 stc/cvec_pq.h delete mode 100644 stc/cvecpq.h (limited to 'stc') diff --git a/stc/crand.h b/stc/crand.h index 841cb473..63a10156 100644 --- a/stc/crand.h +++ b/stc/crand.h @@ -115,34 +115,35 @@ STC_API uint32_t crand_gen_i32(crand_eng32_t* rng) { return (xors >> rot) | (xors << ((-rot) & 31)); } -/* SFC64 random number generator: http://pracrand.sourceforge.net */ - +/* New 64bit PRNG losely based on SFC64: Copyright 2020, Tyge Løvset */ +/* Faster: Updates only 192bit state. Parallel: Ensures unique sequence for each seq (2^63 seqs) */ +/* Minimal period is 2^64 per seq, average ~ 2^127 per seq */ STC_API crand_eng64_t crand_eng64_with_seq(uint64_t seed, uint64_t seq) { crand_eng64_t rng = {seed, seed, seed, (seq << 1u) | 1u}; /* increment must be odd */ for (int i = 0; i < 12; ++i) crand_gen_i64(&rng); return rng; } -#if USE_SFC64 -STC_API uint64_t crand_gen_i64(crand_eng64_t* rng) { /* original sfc64 */ +STC_API uint64_t crand_gen_i64(crand_eng64_t* rng) { enum {LROT = 24, RSHIFT = 11, LSHIFT = 3}; uint64_t *s = rng->state; - const uint64_t result = s[0] + s[1] + s[3]++; - s[0] = s[1] ^ (s[1] >> RSHIFT); - s[1] = s[2] + (s[2] << LSHIFT); - s[2] = ((s[2] << LROT) | (s[2] >> (64 - LROT))) + result; + const uint64_t b = s[1], result = s[0] ^ (s[2] += s[3]|1); + s[0] = (b + (b << LSHIFT)) ^ (b >> RSHIFT); + s[1] = ((b << LROT) | (b >> (64 - LROT))) + result; return result; } -#else -STC_API uint64_t crand_gen_i64(crand_eng64_t* rng) { /* copyright: Tyge Løvset */ + +/* // Original SFC64 random number generator: http://pracrand.sourceforge.net +STC_API uint64_t crand_gen_i64(crand_eng64_t* rng) { enum {LROT = 24, RSHIFT = 11, LSHIFT = 3}; uint64_t *s = rng->state; - const uint64_t b = s[1], result = s[0] ^ (s[2] += s[3]|1); - s[0] = (b + (b << LSHIFT)) ^ (b >> RSHIFT); - s[1] = ((b << LROT) | (b >> (64 - LROT))) + result; + const uint64_t result = s[0] + s[1] + s[3]++; + s[0] = s[1] ^ (s[1] >> RSHIFT); + s[1] = s[2] + (s[2] << LSHIFT); + s[2] = ((s[2] << LROT) | (s[2] >> (64 - LROT))) + result; return result; } -#endif +*/ #endif #endif diff --git a/stc/cvec_pq.h b/stc/cvec_pq.h new file mode 100644 index 00000000..c6a896d3 --- /dev/null +++ b/stc/cvec_pq.h @@ -0,0 +1,125 @@ +/* MIT License + * + * Copyright (c) 2020 Tyge Løvset, NORCE, www.norceresearch.no + * + * 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. + */ + +/* Priority Queue using cvec as heap. + + #include + #include + declare_cvec(f, float); + declare_cvec_pqueue(f, >); // min-heap (increasing values) + + int main() { + crand_eng32_t gen = crand_eng32_init(1234); + crand_uniform_f32_t dist = crand_uniform_f32_init(10.0f, 100.0f); + + cvec_f queue = cvec_init; + // Push ten million random numbers onto the queue. + for (int i=0; i<10000000; ++i) + cvec_f_pqueue_push(&queue, crand_uniform_f32(&gen, dist)); + // Extract the 100 smallest. + for (int i=0; i<100; ++i) { + printf("%f ", cvec_f_pqueue_top(&queue)); + cvec_f_pqueue_pop(&queue); + } + cvec_f_destroy(&queue); + } +*/ + +#ifndef CVEC_PQ__H__ +#define CVEC_PQ__H__ + +#include "cvec.h" + +#define declare_cvec_pqueue(tag, cmpOpr) /* < or > */ \ + \ +STC_API void \ +cvec_##tag##_pqueue_build(cvec_##tag* self); \ +STC_API void \ +cvec_##tag##_pqueue_erase(cvec_##tag* self, size_t i); \ +STC_INLINE cvec_##tag##_value_t \ +cvec_##tag##_pqueue_top(cvec_##tag* self) {return self->data[0];} \ +STC_INLINE void \ +cvec_##tag##_pqueue_pop(cvec_##tag* self) {cvec_##tag##_pqueue_erase(self, 0);} \ +STC_API void \ +cvec_##tag##_pqueue_push(cvec_##tag* self, cvec_##tag##_value_t value); \ +STC_API void \ +cvec_##tag##_pqueue_push_n(cvec_##tag *self, const cvec_##tag##_value_t in[], size_t size); \ + \ +implement_cvec_pqueue(tag, cmpOpr) \ +typedef cvec_##tag##_value_t cvec_##tag##_pqueue_input_t + +/* -------------------------- IMPLEMENTATION ------------------------- */ + +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +#define implement_cvec_pqueue(tag, cmpOpr) \ + \ +STC_INLINE void \ +_cvec_##tag##_pqueue_sift_down(cvec_##tag##_value_t* arr, size_t i, size_t n) { \ + size_t r = i, c = i << 1; \ + while (c <= n) { \ + if (c < n && cvec_##tag##_sort_compare(&arr[c], &arr[c + 1]) cmpOpr 0) \ + ++c; \ + if (cvec_##tag##_sort_compare(&arr[r], &arr[c]) cmpOpr 0) { \ + cvec_##tag##_value_t t = arr[r]; arr[r] = arr[c]; arr[r = c] = t; \ + } else \ + return; \ + c <<= 1; \ + } \ +} \ + \ +STC_API void \ +cvec_##tag##_pqueue_build(cvec_##tag* self) { \ + size_t n = cvec_size(*self); \ + cvec_##tag##_value_t *arr = self->data - 1; \ + for (size_t k = n >> 1; k != 0; --k) \ + _cvec_##tag##_pqueue_sift_down(arr, k, n); \ +} \ + \ +STC_API void \ +cvec_##tag##_pqueue_erase(cvec_##tag* self, size_t i) { \ + size_t n = cvec_size(*self) - 1; \ + self->data[i] = self->data[n]; \ + cvec_##tag##_pop_back(self); \ + _cvec_##tag##_pqueue_sift_down(self->data - 1, i + 1, n); \ +} \ + \ +STC_API void \ +cvec_##tag##_pqueue_push(cvec_##tag* self, cvec_##tag##_value_t value) { \ + cvec_##tag##_push_back(self, value); /* sift-up the value */ \ + size_t n = cvec_size(*self), c = n; \ + cvec_##tag##_value_t *arr = self->data - 1; \ + for (; c > 1 && cvec_##tag##_sort_compare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \ + arr[c] = arr[c >> 1]; \ + if (c != n) arr[c] = value; \ +} \ +STC_API void \ +cvec_##tag##_pqueue_push_n(cvec_##tag *self, const cvec_##tag##_value_t in[], size_t size) { \ + cvec_##tag##_reserve(self, cvec_size(*self) + size); \ + for (size_t i=0; i - #include - declare_cvec(i, int); - declare_cvec_priority_queue(i, >); // min-heap (increasing values) - int main() { - crand_eng32_t pcg = crand_eng32_init(1234); - cvec_i heap = cvec_init; - // Push one million random numbers onto the queue. - for (int i=0; i<1000000; ++i) - cvecpq_i_push(&heap, crand_gen_i32(&pcg)); - // Extract the 100 smallest. - for (int i=0; i<100; ++i) { - printf("%d ", cvecpq_i_top(&heap)); - cvecpq_i_pop(&heap); - } - cvec_i_destroy(&heap); - } -*/ - -#ifndef CVECPQ__H__ -#define CVECPQ__H__ - -#include "cvec.h" - -#define declare_cvec_priority_queue(tag, cmpOpr) /* < or > */ \ - \ -STC_API void \ -cvecpq_##tag##_build(cvec_##tag* self); \ -STC_API void \ -cvecpq_##tag##_erase(cvec_##tag* self, size_t i); \ -STC_INLINE cvec_##tag##_value_t \ -cvecpq_##tag##_top(cvec_##tag* self) {return self->data[0];} \ -STC_INLINE void \ -cvecpq_##tag##_pop(cvec_##tag* self) {cvecpq_##tag##_erase(self, 0);} \ -STC_API void \ -cvecpq_##tag##_push(cvec_##tag* self, cvec_##tag##_value_t value); \ -STC_API void \ -cvecpq_##tag##_push_n(cvec_##tag *self, const cvec_##tag##_value_t in[], size_t size); \ - \ -implement_cvec_priority_queue(tag, cmpOpr) \ -typedef cvec_##tag##_value_t cvecpq_##tag##_input_t - -/* -------------------------- IMPLEMENTATION ------------------------- */ - -#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -#define implement_cvec_priority_queue(tag, cmpOpr) \ - \ -STC_INLINE void \ -_cvecpq_##tag##_siftDown(cvec_##tag##_value_t* arr, size_t i, size_t n) { \ - size_t r = i, c = i << 1; \ - while (c <= n) { \ - if (c < n && cvec_##tag##_sort_compare(&arr[c], &arr[c + 1]) cmpOpr 0) \ - ++c; \ - if (cvec_##tag##_sort_compare(&arr[r], &arr[c]) cmpOpr 0) { \ - cvec_##tag##_value_t t = arr[r]; arr[r] = arr[c]; arr[r = c] = t; \ - } else \ - return; \ - c <<= 1; \ - } \ -} \ - \ -STC_API void \ -cvecpq_##tag##_erase(cvec_##tag* self, size_t i) { \ - size_t n = cvec_size(*self) - 1; \ - self->data[i] = self->data[n]; \ - cvec_##tag##_pop_back(self); \ - _cvecpq_##tag##_siftDown(self->data - 1, i + 1, n); \ -} \ - \ -STC_API void \ -cvecpq_##tag##_push(cvec_##tag* self, cvec_##tag##_value_t value) { \ - cvec_##tag##_push_back(self, value); /* sift-up the value */ \ - size_t n = cvec_size(*self), c = n; \ - cvec_##tag##_value_t *arr = self->data - 1; \ - for (; c > 1 && cvec_##tag##_sort_compare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \ - arr[c] = arr[c >> 1]; \ - if (c != n) arr[c] = value; \ -} \ -STC_API void \ -cvecpq_##tag##_push_n(cvec_##tag *self, const cvec_##tag##_value_t in[], size_t size) { \ - cvec_##tag##_reserve(self, cvec_size(*self) + size); \ - for (size_t i=0; idata - 1; \ - for (size_t k = n >> 1; k != 0; --k) \ - _cvecpq_##tag##_siftDown(arr, k, n); \ -} - -#else -#define implement_cvec_priority_queue(tag, cmpOpr) -#endif - -#endif -- cgit v1.2.3