From 5baa9566801e902afaad733b6a23e8cfb7e376ee Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Tue, 14 Jul 2020 12:11:09 +0200 Subject: Redefined declare_CHash() interface, reverted back to original. declare_CHash(tag, Key, Value, ...). To define sets, use declare_CHash_set(tag, Key, ...); with only two params, you also may use: declare_CHash(tag, Key). Also added method: at, which works like c++ map[key] operator: inserts a new key if not existing (with given value 0), else return existing. Useful for e.g: ++chash_ii_at(&map, key, 0)->value; --- README.md | 14 +- examples/benchmark.c | 2 +- examples/complex.c | 72 ++++----- examples/demos.c | 420 +++++++++++++++++++++++++-------------------------- stc/carray.h | 26 ++-- stc/chash.h | 143 +++++++++--------- stc/crandom.h | 382 +++++++++++++++++++++++----------------------- 7 files changed, 526 insertions(+), 533 deletions(-) diff --git a/README.md b/README.md index 1ebc3490..897d080e 100644 --- a/README.md +++ b/README.md @@ -49,8 +49,8 @@ Because it is headers only, files can simply be included in your program. The fu #include #include -declare_CHash(ii, MAP, int, int); -declare_CHash(ix, SET, int64_t); +declare_CHash(ii, int, int); // map +declare_CHash(ix, int64_t); // set declare_CVector(i, int); ... ``` @@ -137,8 +137,8 @@ void check_destroy(float* v) {printf("destroy %g\n", *v);} declare_CArray(f, float, check_destroy); // normally omit the last argument - float type need no destroy. declare_CList(t2, CArray2_f, carray2_f_destroy, c_noCompare); -declare_CHash(il, MAP, int, CList_t2, clist_t2_destroy); -declare_CHash_string(sm, MAP, CHash_il, chash_il_destroy); +declare_CHash(il, int, CList_t2, clist_t2_destroy); +declare_CHash_string(sm, CHash_il, chash_il_destroy); int main() { int xdim = 4, ydim = 6; @@ -230,7 +230,7 @@ int main() { ``` #include #include "stc/chash.h" -declare_CHash(ii, MAP, int, int); +declare_CHash(ii, int, int); int main() { CHash_ii nums = chash_init; @@ -245,7 +245,7 @@ int main() { ``` #include "stc/cstring.h" #include "stc/chash.h" -declare_CHash_string(s, SET); // See the discussion above regarding this declaration. +declare_CHash_string(s); // CString set. See the discussion above. int main() { CHash_s words = chash_init; @@ -263,7 +263,7 @@ int main() { ``` #include "stc/cstring.h" #include "stc/chash.h" -declare_CHash_string(ss, MAP, CString, cstring_destroy); +declare_CHash_string(ss, CString, cstring_destroy); int main() { CHash_ss table = chash_init; diff --git a/examples/benchmark.c b/examples/benchmark.c index 5c13cf2e..12449e27 100644 --- a/examples/benchmark.c +++ b/examples/benchmark.c @@ -19,7 +19,7 @@ static inline uint32_t fibonacci_hash(const void* data, size_t len) { const uint64_t key = *(const uint64_t *) data; return (uint32_t) (key * 11400714819323198485llu); } -declare_CHash(ii, MAP, int64_t, int64_t, c_emptyDestroy, fibonacci_hash); +declare_CHash(ii, int64_t, int64_t, c_emptyDestroy, fibonacci_hash); KHASH_MAP_INIT_INT64(ii, uint64_t) diff --git a/examples/complex.c b/examples/complex.c index 91a1d4c2..8c44f6cc 100644 --- a/examples/complex.c +++ b/examples/complex.c @@ -1,37 +1,37 @@ -#include "../stc/cstring.h" -#include "../stc/chash.h" -#include "../stc/clist.h" -#include "../stc/carray.h" - -void check_destroy(float* v) {printf("destroy %g\n", *v);} - -declare_CArray(f, float, check_destroy); // normally omit the last argument - float type need no destroy. -declare_CList(t2, CArray2_f, carray2_f_destroy, c_noCompare); -declare_CHash(il, MAP, int, CList_t2, clist_t2_destroy); -declare_CHash_string(sm, MAP, CHash_il, chash_il_destroy); - -int main() { - int xdim = 4, ydim = 6; - int x = 1, y = 5, tableKey = 42; - const char* strKey = "first"; - CHash_sm theMap = chash_init; - - { // Construct. - CArray2_f table = carray2_f_make(ydim, xdim, -0.f); - printf("table: (%zu, %zu)\n", carray2_ydim(table), carray2_xdim(table)); - CList_t2 tableList = clist_init; - CHash_il listMap = chash_init; - - // Put in some data. - carray2_f_data(table, y)[x] = 3.1415927; // table[x][y] - clist_t2_pushBack(&tableList, table); - chash_il_put(&listMap, tableKey, tableList); - chash_sm_put(&theMap, strKey, listMap); - } - { // Access the data entry - CArray2_f table = clist_back(chash_il_get(&chash_sm_get(&theMap, strKey)->value, tableKey)->value); - printf("value (%d, %d) is: %f\n", y, x, carray2_f_value(table, y, x)); - } - - chash_sm_destroy(&theMap); // free up the whole shebang! +#include "../stc/cstring.h" +#include "../stc/chash.h" +#include "../stc/clist.h" +#include "../stc/carray.h" + +void check_destroy(float* v) {printf("destroy %g\n", *v);} + +declare_CArray(f, float, check_destroy); // normally omit the last argument - float type need no destroy. +declare_CList(t2, CArray2_f, carray2_f_destroy, c_noCompare); +declare_CHash(il, int, CList_t2, clist_t2_destroy); +declare_CHash_string(sm, CHash_il, chash_il_destroy); + +int main() { + int xdim = 4, ydim = 6; + int x = 1, y = 5, tableKey = 42; + const char* strKey = "first"; + CHash_sm theMap = chash_init; + + { // Construct. + CArray2_f table = carray2_f_make(ydim, xdim, 0.f); + printf("table: (%zu, %zu)\n", carray2_ydim(table), carray2_xdim(table)); + CList_t2 tableList = clist_init; + CHash_il listMap = chash_init; + + // Put in some data. + carray2_f_data(table, y)[x] = 3.1415927; // table[y][x] + clist_t2_pushBack(&tableList, table); + chash_il_put(&listMap, tableKey, tableList); + chash_sm_put(&theMap, strKey, listMap); + } + { // Access the data entry + CArray2_f table = clist_back(chash_il_get(&chash_sm_get(&theMap, strKey)->value, tableKey)->value); + printf("value (%d, %d) is: %f\n", y, x, carray2_f_value(table, y, x)); + } + + chash_sm_destroy(&theMap); // free up the whole shebang! } \ No newline at end of file diff --git a/examples/demos.c b/examples/demos.c index ea8607db..b0e31f6e 100644 --- a/examples/demos.c +++ b/examples/demos.c @@ -1,210 +1,210 @@ -#include "../stc/cvector.h" -#include "../stc/clist.h" -#include "../stc/carray.h" -#include "../stc/chash.h" -#include "../stc/cstring.h" - - -void stringdemo1() -{ - printf("\nSTRINGDEMO1\n"); - CString cs = cstring_make("one-nine-three-seven-five"); - printf("%s.\n", cs.str); - - cstring_insert(&cs, 3, "-two"); - printf("%s.\n", cs.str); - - cstring_erase(&cs, 7, 5); // -nine - printf("%s.\n", cs.str); - - cstring_replace(&cs, 0, "seven", "four"); - printf("%s.\n", cs.str); - cstring_take(&cs, cstring_makeFmt("%s *** %s", cs.str, cs.str)); - printf("%s.\n", cs.str); - - printf("find: %s\n", cs.str + cstring_find(cs, 0, "four")); - - // reassign: - cstring_assign(&cs, "one two three four five six seven"); - cstring_append(&cs, " eight"); - printf("append: %s\n", cs.str); - - cstring_destroy(&cs); -} - - -declare_CVector(ix, int64_t); // ix is just an example tag name. - -void vectordemo1() -{ - printf("\nVECTORDEMO1\n"); - CVector_ix bignums = cvector_init; // = (CVector_ix) cvector_init; if initializing after declaration. - cvector_ix_reserve(&bignums, 100); - for (size_t i = 0; i<=100; ++i) - cvector_ix_pushBack(&bignums, i * i * i); - - printf("erase - %d: %zu\n", 100, bignums.data[100]); - cvector_ix_popBack(&bignums); // erase the last - - for (size_t i = 0; i < cvector_size(bignums); ++i) { - if (i >= 90) printf("%zu: %zu\n", i, bignums.data[i]); - } - cvector_ix_destroy(&bignums); -} - - - -declare_CVector(cs, CString, cstring_destroy, cstring_compare); // supply inline destructor of values - -void vectordemo2() -{ - printf("\nVECTORDEMO2\n"); - CVector_cs names = cvector_init; - cvector_cs_pushBack(&names, cstring_make("Mary")); - cvector_cs_pushBack(&names, cstring_make("Joe")); - cvector_cs_pushBack(&names, cstring_make("Chris")); - cstring_assign(&names.data[1], "Jane"); // replace Joe - printf("names[1]: %s\n", names.data[1].str); - - cvector_cs_sort(&names); // Sort the array - c_foreach (i, cvector_cs, names) - printf("sorted: %s\n", i.item->str); - cvector_cs_destroy(&names); -} - -declare_CList(ix, int); - -void listdemo1() -{ - printf("\nLISTDEMO1\n"); - 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); - /* 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, 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); -} - -declare_CHash(i, SET, int); - -void setdemo1() -{ - printf("\nSETDEMO1\n"); - CHash_i nums = chash_init; - chash_i_put(&nums, 8); - chash_i_put(&nums, 11); - - c_foreach (i, chash_i, nums) - printf("set: %d\n", i.item->key); - chash_i_destroy(&nums); -} - - -declare_CHash(ii, MAP, int, int); - -void mapdemo1() -{ - printf("\nMAPDEMO1\n"); - CHash_ii nums = chash_init; - chash_ii_put(&nums, 8, 64); - chash_ii_put(&nums, 11, 121); - - printf("get 8: %d\n", chash_ii_get(&nums, 8)->value); - chash_ii_destroy(&nums); -} - - -declare_CHash_string(si, MAP, int); // Shorthand macro for the general declare_CHash expansion. - -void mapdemo2() -{ - printf("\nMAPDEMO2\n"); - CHash_si nums = chash_init; - chash_si_put(&nums, "Hello", 64); - chash_si_put(&nums, "Groovy", 121); - chash_si_put(&nums, "Groovy", 200); // overwrite previous - - // iterate the map: - for (chash_si_iter_t i = chash_si_begin(&nums); i.item; i = chash_si_next(i)) - printf("long: %s: %d\n", i.item->key.str, i.item->value); - - // or rather use the short form: - c_foreach (i, chash_si, nums) - printf("short: %s: %d\n", i.item->key.str, i.item->value); - - chash_si_destroy(&nums); -} - - -declare_CHash_string(ss, MAP, CString, cstring_destroy); - -void mapdemo3() -{ - printf("\nMAPDEMO3\n"); - CHash_ss table = chash_init; - chash_ss_put(&table, "Map", cstring_make("test")); - chash_ss_put(&table, "Make", cstring_make("my")); - chash_ss_put(&table, "Sunny", cstring_make("day")); - printf("remove: Make: %s\n", chash_ss_get(&table, "Make")->value.str); - chash_ss_erase(&table, "Make"); - - printf("size %zu\n", chash_size(table)); - c_foreach (i, chash_ss, table) - printf("key: %s\n", i.item->key.str); - chash_ss_destroy(&table); // frees key and value CStrings, and hash table (CVector). -} - - - -declare_CArray(f, float); - -void arraydemo1() -{ - printf("\nARRAYDEMO1\n"); - CArray3_f a3 = carray3_f_make(30, 20, 10, 0.f); - carray3_f_data(a3, 5, 4)[3] = 10.2f; // a3[5][4][3] - CArray2_f a2 = carray3_f_at(a3, 5); // sub-array reference (no data copy). - - printf("a3: %zu: (%zu, %zu, %zu) = %zu\n", sizeof(a3), carray3_xdim(a3), carray3_ydim(a3), carray3_zdim(a3), carray3_size(a3)); - printf("a2: %zu: (%zu, %zu) = %zu\n", sizeof(a2), carray2_xdim(a2), carray2_ydim(a2), carray2_size(a2)); - - printf("%f\n", carray2_f_value(a2, 4, 3)); // readonly lookup a2[4][3] (=10.2f) - printf("%f\n", carray2_f_data(a2, 4)[3]); // same, but this is writable. - printf("%f\n", carray2_f_at(a2, 4).data[3]); // same, via sub-array access. - - printf("%f\n", carray3_f_value(a3, 5, 4, 3)); // same data location, via a3 array. - printf("%f\n", carray3_f_data(a3, 5, 4)[3]); - printf("%f\n", carray3_f_at2(a3, 5, 4).data[3]); - - carray2_f_destroy(&a2); // does nothing, since it is a sub-array. - carray3_f_destroy(&a3); // also invalidates a2. -} - - - -int main() -{ - stringdemo1(); - vectordemo1(); - vectordemo2(); - listdemo1(); - setdemo1(); - mapdemo1(); - mapdemo2(); - mapdemo3(); - arraydemo1(); -} +#include "../stc/cvector.h" +#include "../stc/clist.h" +#include "../stc/carray.h" +#include "../stc/chash.h" +#include "../stc/cstring.h" + + +void stringdemo1() +{ + printf("\nSTRINGDEMO1\n"); + CString cs = cstring_make("one-nine-three-seven-five"); + printf("%s.\n", cs.str); + + cstring_insert(&cs, 3, "-two"); + printf("%s.\n", cs.str); + + cstring_erase(&cs, 7, 5); // -nine + printf("%s.\n", cs.str); + + cstring_replace(&cs, 0, "seven", "four"); + printf("%s.\n", cs.str); + cstring_take(&cs, cstring_makeFmt("%s *** %s", cs.str, cs.str)); + printf("%s.\n", cs.str); + + printf("find: %s\n", cs.str + cstring_find(cs, 0, "four")); + + // reassign: + cstring_assign(&cs, "one two three four five six seven"); + cstring_append(&cs, " eight"); + printf("append: %s\n", cs.str); + + cstring_destroy(&cs); +} + + +declare_CVector(ix, int64_t); // ix is just an example tag name. + +void vectordemo1() +{ + printf("\nVECTORDEMO1\n"); + CVector_ix bignums = cvector_init; // = (CVector_ix) cvector_init; if initializing after declaration. + cvector_ix_reserve(&bignums, 100); + for (size_t i = 0; i<=100; ++i) + cvector_ix_pushBack(&bignums, i * i * i); + + printf("erase - %d: %zu\n", 100, bignums.data[100]); + cvector_ix_popBack(&bignums); // erase the last + + for (size_t i = 0; i < cvector_size(bignums); ++i) { + if (i >= 90) printf("%zu: %zu\n", i, bignums.data[i]); + } + cvector_ix_destroy(&bignums); +} + + + +declare_CVector(cs, CString, cstring_destroy, cstring_compare); // supply inline destructor of values + +void vectordemo2() +{ + printf("\nVECTORDEMO2\n"); + CVector_cs names = cvector_init; + cvector_cs_pushBack(&names, cstring_make("Mary")); + cvector_cs_pushBack(&names, cstring_make("Joe")); + cvector_cs_pushBack(&names, cstring_make("Chris")); + cstring_assign(&names.data[1], "Jane"); // replace Joe + printf("names[1]: %s\n", names.data[1].str); + + cvector_cs_sort(&names); // Sort the array + c_foreach (i, cvector_cs, names) + printf("sorted: %s\n", i.item->str); + cvector_cs_destroy(&names); +} + +declare_CList(ix, int); + +void listdemo1() +{ + printf("\nLISTDEMO1\n"); + 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); + /* 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, 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); +} + +declare_CHash_set(i, int); // alias: declare_CHash(i, int); + +void setdemo1() +{ + printf("\nSETDEMO1\n"); + CHash_i nums = chash_init; + chash_i_put(&nums, 8); + chash_i_put(&nums, 11); + + c_foreach (i, chash_i, nums) + printf("set: %d\n", i.item->key); + chash_i_destroy(&nums); +} + + +declare_CHash(ii, int, int); + +void mapdemo1() +{ + printf("\nMAPDEMO1\n"); + CHash_ii nums = chash_init; + chash_ii_put(&nums, 8, 64); + chash_ii_put(&nums, 11, 121); + + printf("get 8: %d\n", chash_ii_get(&nums, 8)->value); + chash_ii_destroy(&nums); +} + + +declare_CHash_string(si, int); // Shorthand macro for the general declare_CHash expansion. + +void mapdemo2() +{ + printf("\nMAPDEMO2\n"); + CHash_si nums = chash_init; + chash_si_put(&nums, "Hello", 64); + chash_si_put(&nums, "Groovy", 121); + chash_si_put(&nums, "Groovy", 200); // overwrite previous + + // iterate the map: + for (chash_si_iter_t i = chash_si_begin(&nums); i.item; i = chash_si_next(i)) + printf("long: %s: %d\n", i.item->key.str, i.item->value); + + // or rather use the short form: + c_foreach (i, chash_si, nums) + printf("short: %s: %d\n", i.item->key.str, i.item->value); + + chash_si_destroy(&nums); +} + + +declare_CHash_string(ss, CString, cstring_destroy); + +void mapdemo3() +{ + printf("\nMAPDEMO3\n"); + CHash_ss table = chash_init; + chash_ss_put(&table, "Map", cstring_make("test")); + chash_ss_put(&table, "Make", cstring_make("my")); + chash_ss_put(&table, "Sunny", cstring_make("day")); + printf("remove: Make: %s\n", chash_ss_get(&table, "Make")->value.str); + chash_ss_erase(&table, "Make"); + + printf("size %zu\n", chash_size(table)); + c_foreach (i, chash_ss, table) + printf("key: %s\n", i.item->key.str); + chash_ss_destroy(&table); // frees key and value CStrings, and hash table (CVector). +} + + + +declare_CArray(f, float); + +void arraydemo1() +{ + printf("\nARRAYDEMO1\n"); + CArray3_f a3 = carray3_f_make(30, 20, 10, 0.f); + carray3_f_data(a3, 5, 4)[3] = 10.2f; // a3[5][4][3] + CArray2_f a2 = carray3_f_at(a3, 5); // sub-array reference (no data copy). + + printf("a3: %zu: (%zu, %zu, %zu) = %zu\n", sizeof(a3), carray3_xdim(a3), carray3_ydim(a3), carray3_zdim(a3), carray3_size(a3)); + printf("a2: %zu: (%zu, %zu) = %zu\n", sizeof(a2), carray2_xdim(a2), carray2_ydim(a2), carray2_size(a2)); + + printf("%f\n", carray2_f_value(a2, 4, 3)); // readonly lookup a2[4][3] (=10.2f) + printf("%f\n", carray2_f_data(a2, 4)[3]); // same, but this is writable. + printf("%f\n", carray2_f_at(a2, 4).data[3]); // same, via sub-array access. + + printf("%f\n", carray3_f_value(a3, 5, 4, 3)); // same data location, via a3 array. + printf("%f\n", carray3_f_data(a3, 5, 4)[3]); + printf("%f\n", carray3_f_at2(a3, 5, 4).data[3]); + + carray2_f_destroy(&a2); // does nothing, since it is a sub-array. + carray3_f_destroy(&a3); // also invalidates a2. +} + + + +int main() +{ + stringdemo1(); + vectordemo1(); + vectordemo2(); + listdemo1(); + setdemo1(); + mapdemo1(); + mapdemo2(); + mapdemo3(); + arraydemo1(); +} diff --git a/stc/carray.h b/stc/carray.h index 659474b1..63a970b7 100644 --- a/stc/carray.h +++ b/stc/carray.h @@ -49,7 +49,7 @@ int main() } */ -#define carray1_xdim(a) ((a)._xdim & _carray_sub) +#define carray1_xdim(a) ((a)._xdim & _carray_SUB) #define carray1_size(a) carray1_xdim(a) #define carray2_xdim(a) carray1_xdim(a) @@ -61,11 +61,11 @@ int main() #define carray3_zdim(a) ((a)._zdim) #define carray3_size(a) _carray3_size(&(a)._zdim) -#define _carray_sub (SIZE_MAX >> 1) -#define _carray_own (_carray_sub + 1) +#define _carray_SUB (SIZE_MAX >> 1) +#define _carray_OWN (_carray_SUB + 1) static inline size_t _carray2_ydim(const size_t* yxdim) { - return yxdim[0] / (yxdim[-1] & _carray_sub); + return yxdim[0] / (yxdim[-1] & _carray_SUB); } static inline size_t _carray3_size(const size_t* zdim) { return zdim[0] * zdim[-1]; @@ -98,7 +98,7 @@ static inline size_t _carray3_size(const size_t* zdim) { carray1_##tag##_make(size_t xdim, Value val) { \ Value* m = c_new_N(Value, xdim); \ for (size_t i=0; i_xdim & _carray_own) { \ + if (self->_xdim & _carray_OWN) { \ size_t n = carray1_size(*self); Value* a = self->data; \ while (n--) valueDestroy(&a[n]); free(a); \ } \ } \ static inline void \ carray2_##tag##_destroy(CArray2_##tag* self) { \ - if (self->_xdim & _carray_own) { \ + if (self->_xdim & _carray_OWN) { \ size_t n = carray2_size(*self); Value* a = self->data; \ while (n--) valueDestroy(&a[n]); free(a); \ } \ } \ static inline void \ carray3_##tag##_destroy(CArray3_##tag* self) { \ - if (self->_xdim & _carray_own) { \ + if (self->_xdim & _carray_OWN) { \ size_t n = carray3_size(*self); Value* a = self->data; \ while (n--) valueDestroy(&a[n]); free(a); \ } \ diff --git a/stc/chash.h b/stc/chash.h index 74ae88a8..1518d1dc 100644 --- a/stc/chash.h +++ b/stc/chash.h @@ -23,9 +23,9 @@ /* // Example: #include -#include "stc/cmap.h" -declare_CHash(sx, set, int); -declare_CHash(mx, map, int, char); +#include +declare_CHash(sx, int); // Set of int +declare_CHash(mx, int, char); // Map of int -> char int main(void) { CHash_sx s = chash_init; @@ -54,8 +54,8 @@ int main(void) { #include "cdefs.h" #define chash_init {NULL, NULL, 0, 0, 0.85f, 0.15f} -#define chash_size(map) ((size_t) (map)._size) -#define chash_bucketCount(map) ((size_t) (map)._cap) +#define chash_size(map) ((size_t) (map).size) +#define chash_bucketCount(map) ((size_t) (map).capacity) /* https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction */ #define chash_reduce(x, N) ((uint32_t) (((uint64_t) (x) * (N)) >> 32)) @@ -65,32 +65,44 @@ enum {chash_HASH = 0x7f, chash_USED = 0x80}; #define declare_CHash(...) \ c_MACRO_OVERLOAD(declare_CHash, __VA_ARGS__) -#define declare_CHash_3(tag, type, Key) \ - declare_CHash_4(tag, type, Key, void) +#define declare_CHash_2(tag, Key) \ + declare_CHash_set_2(tag, Key) -#define declare_CHash_4(tag, type, Key, Value) \ - declare_CHash_5(tag, type, Key, Value, c_emptyDestroy) +#define declare_CHash_3(tag, Key, Value) \ + declare_CHash_4(tag, Key, Value, c_emptyDestroy) -#define declare_CHash_5(tag, type, Key, Value, valueDestroy) \ - declare_CHash_6(tag, type, Key, Value, valueDestroy, c_defaultHash) +#define declare_CHash_4(tag, Key, Value, valueDestroy) \ + declare_CHash_5(tag, Key, Value, valueDestroy, c_defaultHash) -#define declare_CHash_6(tag, type, Key, Value, valueDestroy, keyHash) \ - declare_CHash_7(tag, type, Key, Value, valueDestroy, keyHash, c_defaultEquals) +#define declare_CHash_5(tag, Key, Value, valueDestroy, keyHash) \ + declare_CHash_6(tag, Key, Value, valueDestroy, keyHash, c_defaultEquals) -#define declare_CHash_7(tag, type, Key, Value, valueDestroy, keyHash, keyEquals) \ - declare_CHash_11(tag, type, Key, Value, valueDestroy, keyHash, keyEquals, \ +#define declare_CHash_6(tag, Key, Value, valueDestroy, keyHash, keyEquals) \ + declare_CHash_11(tag, MAP, Key, Value, valueDestroy, keyHash, keyEquals, \ c_emptyDestroy, Key, c_defaultGetRaw, c_defaultInitRaw) -/* CHash: */ +/* CHash_set: */ +#define declare_CHash_set(...) \ + c_MACRO_OVERLOAD(declare_CHash_set, __VA_ARGS__) +#define declare_CHash_set_2(tag, Key) \ + declare_CHash_set_3(tag, Key, c_emptyDestroy) +#define declare_CHash_set_3(tag, Key, keyDestroy) \ + declare_CHash_set_4(tag, Key, keyDestroy, c_defaultHash) +#define declare_CHash_set_4(tag, Key, keyDestroy, keyHash) \ + declare_CHash_set_5(tag, Key, keyDestroy, keyHash, c_defaultEquals) +#define declare_CHash_set_5(tag, Key, keyDestroy, keyHash, keyEquals) \ + declare_CHash_11(tag, SET, Key, void, void, keyHash, keyEquals, \ + keyDestroy, Key, c_defaultGetRaw, c_defaultInitRaw) + +/* CHash_string: */ #define declare_CHash_string(...) \ c_MACRO_OVERLOAD(declare_CHash_string, __VA_ARGS__) - -#define declare_CHash_string_2(tag, type) \ - declare_CHash_string_3(tag, type, void) - -#define declare_CHash_string_3(tag, type, Value) \ - declare_CHash_string_4(tag, type, Value, c_emptyDestroy) - +#define declare_CHash_string_1(tag) \ + declare_CHash_string_4(tag, SET, void, void) +#define declare_CHash_string_2(tag, Value) \ + declare_CHash_string_4(tag, MAP, Value, c_emptyDestroy) +#define declare_CHash_string_3(tag, Value, ValueDestroy) \ + declare_CHash_string_4(tag, MAP, Value, ValueDestroy) #define declare_CHash_string_4(tag, type, Value, valueDestroy) \ declare_CHash_11(tag, type, CString, Value, valueDestroy, cstring_hashRaw, cstring_equalsRaw, \ cstring_destroy, const char*, cstring_getRaw, cstring_make) @@ -100,7 +112,7 @@ enum {chash_HASH = 0x7f, chash_USED = 0x80}; #define _chash1_MAP(x) x #define _chash2_MAP(x, y) x, y -/* CHash full: */ +/* CHash full: use 'void' for Value if type is SET */ #define declare_CHash_11(tag, type, Key, Value, valueDestroy, keyHashRaw, keyEqualsRaw, \ keyDestroy, RawKey, keyGetRaw, keyInitRaw) \ typedef struct CHashEntry_##tag { \ @@ -108,10 +120,7 @@ typedef struct CHashEntry_##tag { \ _chash1_##type(Value value;) \ } CHashEntry_##tag; \ \ -static inline CHashEntry_##tag chashentry_##tag##_make(_chash2_##type(Key k, Value v)) { \ - CHashEntry_##tag e = {_chash2_##type(k, v)}; return e; \ -} \ -static inline void \ +STC_INLINE void \ chashentry_##tag##_destroy(CHashEntry_##tag* e) { \ keyDestroy(&e->key); \ _chash1_##type(valueDestroy(&e->value);) \ @@ -120,9 +129,9 @@ chashentry_##tag##_destroy(CHashEntry_##tag* e) { \ typedef RawKey CHashRawKey_##tag; \ \ typedef struct CHash_##tag { \ - CHashEntry_##tag* _table; \ + CHashEntry_##tag* table; \ uint8_t* _hashx; \ - uint32_t _size, _cap; \ + uint32_t size, capacity; \ float maxLoadFactor; \ float shrinkLimitFactor; \ } CHash_##tag; \ @@ -132,12 +141,6 @@ typedef struct { \ uint8_t* _hx; \ } CHashIter_##tag, chash_##tag##_iter_t; \ \ -typedef struct { \ - CHashRawKey_##tag rawKey; \ - size_t index; \ - uint32_t hashx; \ -} CHashBucket_##tag; \ - \ STC_API CHash_##tag \ chash_##tag##_make(size_t initialSize); \ STC_API void \ @@ -152,10 +155,10 @@ STC_API CHashEntry_##tag* \ chash_##tag##_get(const CHash_##tag* self, CHashRawKey_##tag rawKey); \ STC_API CHashEntry_##tag* \ chash_##tag##_put(CHash_##tag* self, _chash2_##type(CHashRawKey_##tag rawKey, Value value)); \ -STC_API CHashEntry_##tag* \ -chash_##tag##_find(CHash_##tag* self, CHashRawKey_##tag rawKey, CHashBucket_##tag* b); \ -STC_API void \ -chash_##tag##_insert(CHash_##tag* self, _chash2_##type(CHashBucket_##tag b, Value value)); \ +_chash1_##type( STC_API CHashEntry_##tag* \ +chash_##tag##_at(CHash_##tag* self, CHashRawKey_##tag rawKey, Value initValue);) \ +STC_INLINE void \ +chash_##tag##_swap(CHash_##tag* a, CHash_##tag* b) { c_swap(CHash_##tag, *a, *b); } \ STC_API size_t \ chash_##tag##_reserve(CHash_##tag* self, size_t size); \ STC_API bool \ @@ -189,17 +192,17 @@ STC_API void \ chash_##tag##_destroy(CHash_##tag* self) { \ if (chash_size(*self)) { \ size_t cap = chash_bucketCount(*self); \ - CHashEntry_##tag* e = self->_table, *end = e + cap; \ + CHashEntry_##tag* e = self->table, *end = e + cap; \ uint8_t *hashx = self->_hashx; \ for (; e != end; ++e) if (*hashx++) chashentry_##tag##_destroy(e); \ } \ free(self->_hashx); \ - free(self->_table); \ + free(self->table); \ } \ \ STC_API void chash_##tag##_clear(CHash_##tag* self) { \ chash_##tag##_destroy(self); \ - self->_cap = self->_size = 0; \ + self->capacity = self->size = 0; \ } \ \ STC_API void \ @@ -217,7 +220,7 @@ chash_##tag##_bucket(const CHash_##tag* self, const CHashRawKey_##tag* rawKeyPtr uint8_t* hashx = self->_hashx; \ while ((sx = hashx[idx])) { \ if (sx == hx) { \ - CHashRawKey_##tag r = keyGetRaw(&self->_table[idx].key); \ + CHashRawKey_##tag r = keyGetRaw(&self->table[idx].key); \ if (keyEqualsRaw(&r, rawKeyPtr)) break; \ } \ if (++idx == cap) idx = 0; \ @@ -231,7 +234,7 @@ chash_##tag##_get(const CHash_##tag* self, CHashRawKey_##tag rawKey) { \ if (chash_bucketCount(*self) == 0) return NULL; \ uint32_t hx; \ size_t idx = chash_##tag##_bucket(self, &rawKey, &hx); \ - return self->_hashx[idx] ? &self->_table[idx] : NULL; \ + return self->_hashx[idx] ? &self->table[idx] : NULL; \ } \ \ static inline void _chash_##tag##_reserveExpand(CHash_##tag* self) { \ @@ -244,43 +247,33 @@ chash_##tag##_put(CHash_##tag* self, _chash2_##type(CHashRawKey_##tag rawKey, Va _chash_##tag##_reserveExpand(self); \ uint32_t hx; \ size_t idx = chash_##tag##_bucket(self, &rawKey, &hx); \ - CHashEntry_##tag* e = &self->_table[idx]; \ + CHashEntry_##tag* e = &self->table[idx]; \ if (self->_hashx[idx]) \ _chash1_##type(valueDestroy(&e->value)) ; \ else { \ e->key = keyInitRaw(rawKey); \ self->_hashx[idx] = (uint8_t) hx; \ - ++self->_size; \ + ++self->size; \ } \ _chash1_##type(e->value = value;) \ return e; \ } \ \ +_chash1_##type( \ STC_API CHashEntry_##tag* \ -chash_##tag##_find(CHash_##tag* self, CHashRawKey_##tag rawKey, CHashBucket_##tag* b) { \ +chash_##tag##_at(CHash_##tag* self, CHashRawKey_##tag rawKey, Value initValue) { \ _chash_##tag##_reserveExpand(self); \ - b->rawKey = rawKey; \ - b->index = chash_##tag##_bucket(self, &rawKey, &b->hashx); \ - return self->_hashx[b->index] ? &self->_table[b->index] : NULL; \ -} \ - \ -STC_API void \ -chash_##tag##_insert(CHash_##tag* self, _chash2_##type(CHashBucket_##tag b, Value value)) { \ - CHashEntry_##tag* e = &self->_table[b.index]; \ - if (self->_hashx[b.index]) \ - _chash1_##type(valueDestroy(&e->value)) ; \ - else { \ - e->key = keyInitRaw(b.rawKey); \ - self->_hashx[b.index] = (uint8_t) b.hashx; \ - ++self->_size; \ + uint32_t hx; \ + size_t idx = chash_##tag##_bucket(self, &rawKey, &hx); \ + CHashEntry_##tag* e = &self->table[idx]; \ + if (! self->_hashx[idx]) { \ + e->key = keyInitRaw(rawKey); \ + self->_hashx[idx] = (uint8_t) hx; \ + ++self->size; \ + e->value = initValue; \ } \ - _chash1_##type(e->value = value;) \ -} \ - \ -static inline void \ -chash_##tag##_swap(CHash_##tag* a, CHash_##tag* b) { \ - c_swap(CHash_##tag, *a, *b); \ -} \ + return e; \ +}) \ \ STC_API size_t \ chash_##tag##_reserve(CHash_##tag* self, size_t newcap) { \ @@ -289,12 +282,12 @@ chash_##tag##_reserve(CHash_##tag* self, size_t newcap) { \ CHash_##tag tmp = { \ c_new_N(CHashEntry_##tag, newcap), \ (uint8_t *) calloc(newcap, sizeof(uint8_t)), \ - self->_size, (uint32_t) newcap, \ + self->size, (uint32_t) newcap, \ self->maxLoadFactor, self->shrinkLimitFactor \ }; \ chash_##tag##_swap(self, &tmp); \ \ - CHashEntry_##tag* e = tmp._table, *slot = self->_table; \ + CHashEntry_##tag* e = tmp.table, *slot = self->table; \ uint8_t* hashx = self->_hashx; \ uint32_t hx; \ for (size_t i = 0; i < oldcap; ++i, ++e) \ @@ -305,14 +298,14 @@ chash_##tag##_reserve(CHash_##tag* self, size_t newcap) { \ hashx[idx] = (uint8_t) hx; \ } \ free(tmp._hashx); \ - free(tmp._table); \ + free(tmp.table); \ return newcap; \ } \ \ STC_API bool \ chash_##tag##_eraseBucket(CHash_##tag* self, size_t i) { \ size_t j = i, k, cap = chash_bucketCount(*self); \ - CHashEntry_##tag* slot = self->_table; \ + CHashEntry_##tag* slot = self->table; \ uint8_t* hashx = self->_hashx; \ CHashRawKey_##tag r; \ if (! hashx[i]) \ @@ -328,7 +321,7 @@ chash_##tag##_eraseBucket(CHash_##tag* self, size_t i) { \ } while (true); \ hashx[i] = 0; \ chashentry_##tag##_destroy(&slot[i]); \ - --self->_size; \ + --self->size; \ return true; \ } \ \ @@ -347,7 +340,7 @@ chash_##tag##_erase(CHash_##tag* self, CHashRawKey_##tag rawKey) { \ STC_API chash_##tag##_iter_t \ chash_##tag##_begin(CHash_##tag* map) { \ uint8_t* hx = map->_hashx; \ - CHashEntry_##tag* e = map->_table, *end = e + chash_bucketCount(*map); \ + CHashEntry_##tag* e = map->table, *end = e + chash_bucketCount(*map); \ while (e != end && !*hx) ++e, ++hx; \ chash_##tag##_iter_t it = {e == end ? NULL : e, end, hx}; return it; \ } \ diff --git a/stc/crandom.h b/stc/crandom.h index 7cd22619..06f1c26a 100644 --- a/stc/crandom.h +++ b/stc/crandom.h @@ -1,191 +1,191 @@ -#ifndef CRANDOM__H__ -#define CRANDOM__H__ - -#include "cdefs.h" -#include - -typedef struct {uint64_t state; uint64_t inc;} pcg32_random_t; - -/* 32 bit random number generator */ -STC_INLINE uint32_t pcg32_random(pcg32_random_t* rng) -{ - uint64_t old = rng->state; - rng->state = old * 6364136223846793005ull + rng->inc; - uint32_t xos = ((old >> 18u) ^ old) >> 27u; - uint32_t rot = old >> 59u; - return (xos >> rot) | (xos << ((-rot) & 31)); -} - -/* float random int number in range [0, 1). NB: 23 bit resolution. */ -STC_INLINE float pcg32_fRandom(pcg32_random_t* rng) { - union {uint32_t i; float f;} u = {0x3F800000u | (pcg32_random(rng) >> 9)}; - return u.f - 1.0f; -} - -/* Uniform random number in range [0, bound) */ -STC_INLINE uint32_t pcg32_bRandom(pcg32_random_t* rng, uint32_t bound) { - return (uint32_t) (((uint64_t) pcg32_random(rng) * bound) >> 32); -} - -STC_INLINE pcg32_random_t pcg32_seed(uint64_t seed, uint64_t seq) { - pcg32_random_t rng = {0u, (seq << 1u) | 1u}; /* inc must be odd */ - pcg32_random(&rng); - rng.state += seed; - pcg32_random(&rng); - return rng; -} - -/* - * Rotate bits left - */ -STC_INLINE uint64_t c_rotateLeft64(uint64_t x, int bits) { - return (x << bits) | (x >> (64 - bits)); -} - -/* - * sfc64: http://pracrand.sourceforge.net - */ -typedef struct {uint64_t state[4];} sfc64_random_t; - -/* 64 bit random number generator */ -STC_API uint64_t sfc64_random(sfc64_random_t* rng) { - enum {LR=24, RS=11, LS=3}; - uint64_t *s = rng->state; - const uint64_t result = s[0] + s[1] + s[3]++; - s[0] = s[1] ^ (s[1] >> RS); - s[1] = s[2] + (s[2] << LS); - s[2] = c_rotateLeft64(s[2], LR) + result; - return result; -} - -/* double random int number in range [0, 1). */ -STC_INLINE double sfc64_fRandom(sfc64_random_t* rng) { - union {uint64_t i; double f;} u = {0x3FF0000000000000ull | (sfc64_random(rng) >> 12)}; - return u.f - 1.0; -} - -STC_API sfc64_random_t sfc64_seed(const uint64_t seed) { - sfc64_random_t state = {{seed, seed, seed, 1}}; - for (int i = 0; i < 12; ++i) sfc64_random(&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 - STC_INLINE uint64_t c_le64ToHost(uint64_t x) { return OSSwapLittleToHostInt64(x); } -#elif defined(__FreeBSD__) || defined(__NetBSD__) || defined(__OpenBSD__) || defined(__DragonFly__) - #include - STC_INLINE uint64_t c_le64ToHost(uint64_t x) { return letoh64(x); } -#elif defined(__linux__) || defined(__CYGWIN__) || defined(__GNUC__) || defined(__GNU_LIBRARY__) - #include - STC_INLINE uint64_t c_le64ToHost(uint64_t x) { return le64toh(x); } -#endif - -typedef struct siphash_t { - uint64_t v[4], padding; - size_t length; - int c, d; -} siphash_t; - -/* c=2, d=4 or c=1, d=3 */ -STC_INLINE 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->v[0] = key[0] ^ 0x736f6d6570736575; - s->v[1] = key[1] ^ 0x646f72616e646f6d; - s->v[2] = key[0] ^ 0x6c7967656e657261; - s->v[3] = key[1] ^ 0x7465646279746573; -} - -/* default init 2-4 */ -STC_API siphash_t siphash_init(const uint64_t key[2]) { - siphash_t state; - siphash_init_c_d(&state, key, 2, 4); - return state; -} - -#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, v) \ - for (int r = 0; r < rounds; ++r) { \ - _siphash_halfRound(13, 16, v[0], v[1], v[2], v[3]); \ - _siphash_halfRound(17, 21, v[2], v[1], v[0], v[3]); \ - } - -#define _siphash_digest(rounds, v, m) { \ - const uint64_t _m = m; \ - v[3] ^= _m; \ - _siphash_compress(rounds, v); \ - v[0] ^= _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; - uint64_t *v = s->v; - s->length += size; - - if (offset) { - const 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, v, 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, v, 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) { - uint64_t *v = s->v; - _siphash_digest(s->c, v, s->padding | (s->length << 56)); - v[2] ^= 0xff; - _siphash_compress(s->d, v); - return v[0] ^ v[1] ^ v[2] ^ v[3]; -} - -/* 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_INLINE 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 +#ifndef CRANDOM__H__ +#define CRANDOM__H__ + +#include "cdefs.h" +#include + +typedef struct {uint64_t state; uint64_t inc;} pcg32_random_t; + +/* 32 bit random number generator */ +STC_INLINE uint32_t pcg32_random(pcg32_random_t* rng) +{ + uint64_t old = rng->state; + rng->state = old * 6364136223846793005ull + rng->inc; + uint32_t xos = ((old >> 18u) ^ old) >> 27u; + uint32_t rot = old >> 59u; + return (xos >> rot) | (xos << ((-rot) & 31)); +} + +/* float random int number in range [0, 1). NB: 23 bit resolution. */ +STC_INLINE float pcg32_floatRandom(pcg32_random_t* rng) { + union {uint32_t i; float f;} u = {0x3F800000u | (pcg32_random(rng) >> 9)}; + return u.f - 1.0f; +} + +/* Uniform random number in range [0, bound) */ +STC_INLINE uint32_t pcg32_boundedRandom(pcg32_random_t* rng, uint32_t bound) { + return (uint32_t) (((uint64_t) pcg32_random(rng) * bound) >> 32); +} + +STC_INLINE pcg32_random_t pcg32_seed(uint64_t seed, uint64_t seq) { + pcg32_random_t rng = {0u, (seq << 1u) | 1u}; /* inc must be odd */ + pcg32_random(&rng); + rng.state += seed; + pcg32_random(&rng); + return rng; +} + +/* + * Rotate bits left + */ +STC_INLINE uint64_t c_rotateLeft64(uint64_t x, int bits) { + return (x << bits) | (x >> (64 - bits)); +} + +/* + * sfc64: http://pracrand.sourceforge.net + */ +typedef struct {uint64_t state[4];} sfc64_random_t; + +/* 64 bit random number generator */ +STC_API uint64_t sfc64_random(sfc64_random_t* rng) { + enum {LR=24, RS=11, LS=3}; + uint64_t *s = rng->state; + const uint64_t result = s[0] + s[1] + s[3]++; + s[0] = s[1] ^ (s[1] >> RS); + s[1] = s[2] + (s[2] << LS); + s[2] = c_rotateLeft64(s[2], LR) + result; + return result; +} + +/* double random int number in range [0, 1). */ +STC_INLINE double sfc64_fRandom(sfc64_random_t* rng) { + union {uint64_t i; double f;} u = {0x3FF0000000000000ull | (sfc64_random(rng) >> 12)}; + return u.f - 1.0; +} + +STC_API sfc64_random_t sfc64_seed(const uint64_t seed) { + sfc64_random_t state = {{seed, seed, seed, 1}}; + for (int i = 0; i < 12; ++i) sfc64_random(&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 + STC_INLINE uint64_t c_le64ToHost(uint64_t x) { return OSSwapLittleToHostInt64(x); } +#elif defined(__FreeBSD__) || defined(__NetBSD__) || defined(__OpenBSD__) || defined(__DragonFly__) + #include + STC_INLINE uint64_t c_le64ToHost(uint64_t x) { return letoh64(x); } +#elif defined(__linux__) || defined(__CYGWIN__) || defined(__GNUC__) || defined(__GNU_LIBRARY__) + #include + STC_INLINE uint64_t c_le64ToHost(uint64_t x) { return le64toh(x); } +#endif + +typedef struct siphash_t { + uint64_t v[4], padding; + size_t length; + int c, d; +} siphash_t; + +/* c=2, d=4 or c=1, d=3 */ +STC_INLINE 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->v[0] = key[0] ^ 0x736f6d6570736575; + s->v[1] = key[1] ^ 0x646f72616e646f6d; + s->v[2] = key[0] ^ 0x6c7967656e657261; + s->v[3] = key[1] ^ 0x7465646279746573; +} + +/* default init 2-4 */ +STC_API siphash_t siphash_init(const uint64_t key[2]) { + siphash_t state; + siphash_init_c_d(&state, key, 2, 4); + return state; +} + +#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, v) \ + for (int r = 0; r < rounds; ++r) { \ + _siphash_halfRound(13, 16, v[0], v[1], v[2], v[3]); \ + _siphash_halfRound(17, 21, v[2], v[1], v[0], v[3]); \ + } + +#define _siphash_digest(rounds, v, m) { \ + const uint64_t _m = m; \ + v[3] ^= _m; \ + _siphash_compress(rounds, v); \ + v[0] ^= _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; + uint64_t *v = s->v; + s->length += size; + + if (offset) { + const 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, v, 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, v, 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) { + uint64_t *v = s->v; + _siphash_digest(s->c, v, s->padding | (s->length << 56)); + v[2] ^= 0xff; + _siphash_compress(s->d, v); + return v[0] ^ v[1] ^ v[2] ^ v[3]; +} + +/* 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_INLINE 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 -- cgit v1.2.3