Added siphash to crandom.h and some small enhancements.

4 files changed, 161 insertions, 38 deletions

diff --git a/demos.c b/demos.c
index 83724841..d9a0824c 100644
--- a/demos.c
+++ b/demos.c
@@ -77,19 +77,25 @@ declare_CList(ix, int);
 void listdemo1()
 {
     printf("\nLISTDEMO1\n");
-    CList_ix nums = clist_init;
-    clist_ix_pushBack(&nums, 123);
-    clist_ix_pushBack(&nums, 231);
-    clist_ix_pushBack(&nums, 444);
-    clist_ix_pushBack(&nums, 321);
-    *clist_ix_find(&nums, 231) = 1000;
+    CList_ix nums = clist_init, nums2 = clist_init;
+    for (int i = 0; i < 10; ++i)
+        clist_ix_pushBack(&nums, i);
+    for (int i = 100; i < 110; ++i)
+        clist_ix_pushBack(&nums2, i);
     c_foreach (i, clist_ix, nums)
-        printf("value: %d\n", i.item->value);    
+        printf("value: %d\n", i.item->value);
+    /* merge/append nums2 to nums */
+    clist_ix_spliceAfter(&nums, clist_ix_last(&nums), &nums2);
+    c_foreach (i, clist_ix, nums)
+        printf("spliced: %d\n", i.item->value);
+
+    *clist_ix_find(&nums, 100) *= 10;
     clist_ix_sort(&nums);                     // Sort the array
-    clist_ix_remove(&nums, 123);
+    clist_ix_remove(&nums, 105);
+    clist_ix_popFront(&nums);
+    clist_ix_pushFront(&nums, -99);
     c_foreach (i, clist_ix, nums)
         printf("sorted: %d\n", i.item->value);
-
     clist_ix_destroy(&nums);
 }
 
diff --git a/rngtest.c b/rngtest.c
index b24caaa9..f5344b47 100644
--- a/rngtest.c
+++ b/rngtest.c
@@ -1,5 +1,4 @@
 #include <stdio.h>
-#include <stdlib.h>
 #include <time.h>
 #include "stc/crandom.h"
 #ifdef __cplusplus
diff --git a/stc/crandom.h b/stc/crandom.h
index 2bf88028..1464a300 100644
--- a/stc/crandom.h
+++ b/stc/crandom.h
@@ -1,7 +1,8 @@
 #ifndef CRANDOM__H__
 #define CRANDOM__H__
 
-#include <stdint.h>
+#include "cdefs.h"
+#include <string.h>
 
 /*
  * Mersenne Twister random number generator MT19937, 32 bit.
@@ -18,7 +19,7 @@ typedef struct mt19937 {
 } mt19937_t;
 
 /* initializes state with a seed */
-static inline void mt19937_init(mt19937_t *state, uint32_t seed) {
+STC_API void mt19937_init(mt19937_t *state, uint32_t seed) {
     state->idx = mt19937_N;
     state->arr[0] = seed;
     for (int i = 1; i < mt19937_N; ++i) {
@@ -26,20 +27,20 @@ static inline void mt19937_init(mt19937_t *state, uint32_t seed) {
     }
 }
 /* creates a new state from a seed */
-static inline mt19937_t mt19937_seed(uint32_t seed) {
+STC_API mt19937_t mt19937_seed(uint32_t seed) {
     mt19937_t state;
     mt19937_init(&state, seed);
     return state;
 }
 /* creates a new state from default seed */
-static inline mt19937_t mt19937_default(void) {
+STC_API mt19937_t mt19937_default(void) {
     mt19937_t state;
     mt19937_init(&state, 5489);
     return state;
 }
 
 /* generates a random number on [0, 0xffffffff]-interval */
-static inline uint32_t mt19937_rand(mt19937_t *state) {
+STC_API uint32_t mt19937_rand(mt19937_t *state) {
     enum {N = mt19937_N, M = mt19937_M};
 
     uint32_t y, *arr = state->arr;
@@ -68,38 +69,42 @@ static inline uint32_t mt19937_rand(mt19937_t *state) {
 }
 
 /* 
+ * rotate bits left uint64
+ */
+
+STC_INLINE uint64_t c_rotateLeft64(uint64_t x, int bits) {
+    return (x << bits) | (x >> (64 - bits));
+}
+
+/* 
  * xoroshiro128** with splitmix64 seed initialization
  */
 
-static inline uint64_t splitmix64(uint64_t *state) {
+STC_API uint64_t splitmix64(uint64_t *state) {
     uint64_t z = (*state += 0x9e3779b97f4a7c15);
     z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
     z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
     return z ^ (z >> 31);
 }
 
-static inline uint64_t c_rotl(uint64_t x, int s) {
-    return (x << s) | (x >> (64 - s));
-}
-
 typedef struct xoroshiro128ss {
     uint64_t s[2];
 } xoroshiro128ss_t;
 
-static inline xoroshiro128ss_t xoroshiro128ss_seed(uint64_t seed) {
+STC_API xoroshiro128ss_t xoroshiro128ss_seed(uint64_t seed) {
     xoroshiro128ss_t state;
     state.s[0] = splitmix64(&seed);
     state.s[1] = splitmix64(&seed);
     return state;
 }
 
-static inline uint64_t xoroshiro128ss_rand(xoroshiro128ss_t *state) {
+STC_API uint64_t xoroshiro128ss_rand(xoroshiro128ss_t *state) {
     uint64_t *s = state->s, s1 = s[1];
     const uint64_t s0 = s[0];
-    const uint64_t result = c_rotl(s0 * 5, 7) * 9;
+    const uint64_t result = c_rotateLeft64(s0 * 5, 7) * 9;
     s1 ^= s0;
-    s[0] = c_rotl(s0, 24) ^ s1 ^ (s1 << 16);
-    s[1] = c_rotl(s1, 37);
+    s[0] = c_rotateLeft64(s0, 24) ^ s1 ^ (s1 << 16);
+    s[1] = c_rotateLeft64(s1, 37);
     return result;
 }
 
@@ -111,21 +116,137 @@ typedef struct sfc64 {
     uint64_t s[3], counter;
 } sfc64_t;
 
-static inline uint64_t sfc64_rand(sfc64_t* state) {
+STC_API uint64_t sfc64_rand(sfc64_t* state) {
     enum {LROT = 24, RSHIFT = 11, LSHIFT = 3};
     uint64_t *s = state->s;
 
     uint64_t result = s[0] + s[1] + ++state->counter;
     s[0] = s[1] ^ (s[1] >> RSHIFT);
     s[1] = s[2] + (s[2] << LSHIFT);
-    s[2] = c_rotl(s[2], LROT) + result;
+    s[2] = c_rotateLeft64(s[2], LROT) + result;
     return result;
 }
 
-static inline sfc64_t sfc64_seed(uint64_t seed) {
+STC_API sfc64_t sfc64_seed(const uint64_t seed) {
     sfc64_t state = {{seed, seed, seed}, 0};
     for (int i = 0; i < 12; ++i) sfc64_rand(&state);
     return state;
 }
 
+/*
+ * siphash implementation.
+ */
+
+#if defined(_WIN32) || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
+    STC_INLINE uint64_t c_le64ToHost(uint64_t x) { return x; }
+#elif defined(__APPLE__)
+    #include <libkern/OSByteOrder.h>
+    STC_INLINE uint64_t c_le64ToHost(uint64_t x) { return OSSwapLittleToHostInt64(x); }
+#elif defined(__FreeBSD__) || defined(__NetBSD__) || defined(__OpenBSD__) || defined(__DragonFly__)
+    #include <sys/endian.h>
+    STC_INLINE uint64_t c_le64ToHost(uint64_t x) { return letoh64(x); }
+#elif defined(__linux__) || defined(__CYGWIN__) || defined(__GNUC__) || defined(__GNU_LIBRARY__)
+    #include <endian.h>
+    STC_INLINE uint64_t c_le64ToHost(uint64_t x) { return le64toh(x); }
+#endif
+
+typedef struct siphash_t {
+    int c, d;
+    size_t length;
+    uint64_t padding, v0, v1, v2, v3;
+} siphash_t;
+
+/* c=2, d=4 or c=1, d=3 */
+STC_API void siphash_init_c_d(siphash_t* s, const uint64_t key[2], const int c, const int d) {
+    s->c = c;
+    s->d = d;
+    s->length = 0;
+    s->padding = 0;
+    s->v0 = key[0] ^ 0x736f6d6570736575;
+    s->v1 = key[1] ^ 0x646f72616e646f6d;
+    s->v2 = key[0] ^ 0x6c7967656e657261;
+    s->v3 = key[1] ^ 0x7465646279746573;
+}
+
+// default init 2-4
+STC_API siphash_t siphash_init(const uint64_t key[2]) {
+    siphash_t s;
+    siphash_init_c_d(&s, key, 2, 4);
+    return s;
+}
+
+#define _siphash_halfRound(i, j, a, b, c, d) \
+    (a += b, \
+     c += d, \
+     b = c_rotateLeft64(b, i) ^ a, \
+     d = c_rotateLeft64(d, j) ^ c, \
+     a = c_rotateLeft64(a, 32))
+
+#define _siphash_compress(rounds, s) \
+    for (int r = 0; r < rounds; ++r) { \
+        _siphash_halfRound(13, 16, s->v0, s->v1, s->v2, s->v3); \
+        _siphash_halfRound(17, 21, s->v2, s->v1, s->v0, s->v3); \
+    }
+
+#define _siphash_digest(rounds, s, m) { \
+        uint64_t _m = m; \
+        s->v3 ^= _m; \
+        _siphash_compress(rounds, s); \
+        s->v0 ^= _m; \
+    }
+
+STC_API void siphash_update(siphash_t* s, const void* bytes, size_t size) {
+    union { const uint8_t* u8; const uint64_t* u64; } in;
+    in.u8 = (const uint8_t*) bytes;
+    size_t offset = s->length & 7;
+    s->length += size;
+
+    if (offset) {
+        size_t end = offset + size;
+        size -= 8 - offset;
+        while (offset < end && offset < 8) {
+            s->padding |= ((uint64_t) *in.u8++) << (offset++ << 3);
+        }
+        if (end < 8) return;
+
+        _siphash_digest(s->c, s, s->padding);
+        s->padding = 0;
+    }
+    size_t n_words = size >> 3;
+    uint64_t m;
+
+    while (n_words--) {
+        memcpy(&m, in.u64++, 8);
+        _siphash_digest(s->c, s, c_le64ToHost(m));
+    }
+    switch (s->length & 7) {
+        case 7: s->padding |= ((uint64_t) in.u8[6]) << 48;
+        case 6: s->padding |= ((uint64_t) in.u8[5]) << 40;
+        case 5: s->padding |= ((uint64_t) in.u8[4]) << 32;
+        case 4: s->padding |= ((uint64_t) in.u8[3]) << 24;
+        case 3: s->padding |= ((uint64_t) in.u8[2]) << 16;
+        case 2: s->padding |= ((uint64_t) in.u8[1]) << 8;
+        case 1: s->padding |= ((uint64_t) in.u8[0]);
+    }
+}
+
+STC_API uint64_t siphash_finalize(siphash_t* s) {
+    _siphash_digest(s->c, s, s->padding | (s->length << 56));
+    s->v2 ^= 0xff;
+    _siphash_compress(s->d, s);
+    return s->v0 ^ s->v1 ^ s->v2 ^ s->v3;
+}
+/* c=2, d=4 or c=1, d=3 */
+STC_API uint64_t siphash_hash_c_d(const uint64_t key[2], const void* bytes, const uint64_t size, const int c, const int d) {
+    siphash_t state;
+    siphash_init_c_d(&state, key, c, d);
+    siphash_update(&state, bytes, size);
+    return siphash_finalize(&state);
+}
+
+/* default hash 2-4 */
+STC_API uint64_t siphash_hash(const uint64_t key[2], const void* bytes, const uint64_t size) {
+    return siphash_hash_c_d(key, bytes, size, 2, 4);
+}
+
 #endif
diff --git a/stc/cvector.h b/stc/cvector.h
index 27caca6a..292954b1 100644
--- a/stc/cvector.h
+++ b/stc/cvector.h
@@ -94,8 +94,12 @@ typedef struct { \
     Value *item, *end; \

 } CVectorIter_##tag, cvector_##tag##_iter_t; \

  \

-STC_API cvector_##tag##_iter_t \

-cvector_##tag##_begin(CVector_##tag* vec); \

+static inline cvector_##tag##_iter_t \

+cvector_##tag##_begin(CVector_##tag* vec) { \

+    const size_t n = cvector_size(*vec); \

+    cvector_##tag##_iter_t it = {n ? vec->data : NULL, vec->data + n}; \

+    return it; \

+} \

  \

 static inline cvector_##tag##_iter_t \

 cvector_##tag##_next(cvector_##tag##_iter_t it) { \

@@ -190,15 +194,8 @@ STC_API void \
 cvector_##tag##_sort(CVector_##tag* self) { \

     size_t len = cvector_size(*self); \

     if (len) qsort(self->data, len, sizeof(Value), cvector_##tag##_sortCompare); \

-} \

- \

-STC_API cvector_##tag##_iter_t \

-cvector_##tag##_begin(CVector_##tag* vec) { \

-    cvector_##tag##_iter_t it; \

-    it.item = vec->data, it.end = it.item + cvector_size(*vec); \

-    if (it.item == it.end) it.item = NULL; \

-    return it; \

 }

+

 #else

 #define implement_CVector_6(tag, Value, valueDestroy, RawValue, valueCompareRaw, valueGetRaw)

 #endif