From b224d2f0b9b344a08c6c508d61f15bdf205464f8 Mon Sep 17 00:00:00 2001 From: ame Date: Fri, 17 Nov 2023 10:10:47 -0600 Subject: tons of hashes bleh --- b.c | 83 ---------- c.lua | 24 +-- src/crypto.c | 8 + src/crypto.h | 52 ++++++ src/hash/buzhash.c | 96 +++++++++++ src/hash/buzhash.h | 5 + src/hash/cityhash.c | 430 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/hash/cityhash.h | 40 +++++ src/hash/djb2.c | 27 ++++ src/hash/djb2.h | 3 + src/hash/farmhash.c | 169 ++++++++++++++++++++ src/hash/farmhash.h | 4 + src/hash/fasthash.c | 83 ++++++++++ src/hash/fasthash.h | 4 + src/hash/fnv.c | 62 ++++++++ src/hash/fnv.h | 9 ++ src/hash/jenkins.c | 31 ++++ src/hash/jenkins.h | 3 + src/hash/loselose.c | 27 ++++ src/hash/loselose.h | 3 + src/hash/metrohash.c | 227 ++++++++++++++++++++++++++ src/hash/metrohash.h | 6 + src/hash/murmur.c | 101 ++++++++++++ src/hash/murmur.h | 4 + src/hash/pjw.c | 31 ++++ src/hash/pjw.h | 3 + src/hash/sdbm.c | 28 ++++ src/hash/sdbm.h | 3 + src/hash/sha2-256.c | 211 +++++++++++++++++++++++++ src/hash/sha2-256.h | 5 + src/hash/spookyhash.c | 335 +++++++++++++++++++++++++++++++++++++++ src/hash/spookyhash.h | 8 + tests/hash.lua | 32 +++- 33 files changed, 2054 insertions(+), 103 deletions(-) delete mode 100644 b.c create mode 100644 src/hash/buzhash.c create mode 100644 src/hash/buzhash.h create mode 100644 src/hash/cityhash.c create mode 100644 src/hash/cityhash.h create mode 100644 src/hash/djb2.c create mode 100644 src/hash/djb2.h create mode 100644 src/hash/farmhash.c create mode 100644 src/hash/farmhash.h create mode 100644 src/hash/fasthash.c create mode 100644 src/hash/fasthash.h create mode 100644 src/hash/fnv.c create mode 100644 src/hash/fnv.h create mode 100644 src/hash/jenkins.c create mode 100644 src/hash/jenkins.h create mode 100644 src/hash/loselose.c create mode 100644 src/hash/loselose.h create mode 100644 src/hash/metrohash.c create mode 100644 src/hash/metrohash.h create mode 100644 src/hash/murmur.c create mode 100644 src/hash/murmur.h create mode 100644 src/hash/pjw.c create mode 100644 src/hash/pjw.h create mode 100644 src/hash/sdbm.c create mode 100644 src/hash/sdbm.h create mode 100644 src/hash/sha2-256.c create mode 100644 src/hash/sha2-256.h create mode 100644 src/hash/spookyhash.c create mode 100644 src/hash/spookyhash.h diff --git a/b.c b/b.c deleted file mode 100644 index 1f08f1f..0000000 --- a/b.c +++ /dev/null @@ -1,83 +0,0 @@ -#include -#include -#include - -int char_index(int c){ - if(c <= 25) return 65 + c; - if(c <= 51) return 71 + c; - if(c <= 61) return (c - 52)+48; - if(c == 62) return 43; - if(c == 63) return 47; - return 61; -} - -int ichar_index(int c){ - if(65 <= c && c <= 90) return c - 65; - if(97 <= c && c <= 122) return c - 97 + 26; - if(48 <= c && c <= 57) return c - 48 + 52; - if(c == 47) return 63; - return 0; -} - -int de_base64(char* in, char* out){ - int len = 0; - for(int i = 0; in[i]!='\0'; i++) len++; - - //char out[len]; - for(int i = 0; i < len; i+=4){ - uint8_t u1 = i>len?0:in[i]; - uint8_t u2 = i+1>len?0:in[i+1]; - uint8_t u3 = i+2>len?0:in[i+2]; - uint8_t u4 = i+3>len?0:in[i+3]; - - u1 = ichar_index(u1); - u2 = ichar_index(u2); - u3 = ichar_index(u3); - u4 = ichar_index(u4); - - uint8_t left = u1 << 2 | u2 >> 4; - uint8_t middle = u2 << 4 | u3 >> 2; - uint8_t right = u3 << 6 | u4; - - if(u4==0) sprintf(out,"%s%c%c",out,left,middle); - else if(u3==0) sprintf(out,"%s%c",out,left); - else sprintf(out,"%s%c%c%c",out,left,middle,right); - - } - return 0; -} -int en_base64(char* in, char* out){ - int len = 0; - for(int i = 0; in[i]!='\0'; i++) len++; - - //char out[(len+1)*3]; - for(int i = 0; i < len; i+=3){ - uint8_t f = i>len?0:in[i]; - uint8_t s = i+1>len?0:in[i+1]; - uint8_t t = i+2>len?0:in[i+2]; - - uint8_t i1 = f>>2; - uint8_t i2 = (uint8_t)(f<<6)>>2 | (s>>4); - uint8_t i3 = (uint8_t)(s<<4)>>2 | (t>>6); - uint8_t i4 = t & 0x3f; - - if(t==0)i4 = 64; - if(s==0)i3 = 64; - sprintf(out,"%s%c%c%c%c",out,char_index(i1),char_index(i2), - char_index(i3),char_index(i4)); - } - return 0; -} - -int main(){ - char* uwu = "Many hands make light work.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"; - char uwue[20*8000]; - char uwud[20*8000]; - - en_base64(uwu, uwue); - de_base64(uwue, uwud); - - printf("%s\n%s\n%s",uwu,uwue,uwud); -} - - diff --git a/c.lua b/c.lua index 05034e0..45a531a 100644 --- a/c.lua +++ b/c.lua @@ -1,20 +1,10 @@ require "llib" -print(llib.crypto.xor8("Hello World!")) -print(llib.crypto.sysvchecksum("nya")) -print(llib.crypto.fletcher32("nya")) -print(llib.crypto.fletcher16("nya")) -print(llib.crypto.fletcher8("nya")) -print(llib.crypto.crc8("nya")) -print(llib.crypto.crc16("nya")) -print(llib.crypto.crc32("nya2")) -print(llib.crypto.bsdchecksum("nya")) -print(llib.crypto.adler32("nya")) -print(llib.crypto.xxh64("nya",5)) -print(llib.crypto.xxh32("nya",5)) -print(llib.crypto.md5("wowa")); -print(llib.crypto.sha1("wowa")); -print(llib.crypto.sha0("wowa")); -print(llib.crypto.sha256("wowa")); -print(llib.crypto.sha224("wowa")); +print(llib.crypto.spookyhash128_v1("meow")) +print(llib.crypto.spookyhash128_v2("meow")) +print(llib.crypto.spookyhash64_v1("meow")) +print(llib.crypto.spookyhash64_v2("meow")) +print(llib.crypto.spookyhash32_v1("meow")) +print(llib.crypto.spookyhash32_v2("meow")) + diff --git a/src/crypto.c b/src/crypto.c index bddb2e6..b99add7 100644 --- a/src/crypto.c +++ b/src/crypto.c @@ -7,3 +7,11 @@ unsigned i_lr(unsigned y, unsigned offset){ unsigned i_rr(unsigned x, unsigned n) { return (x >> n % 32) | (x << (32-n) % 32); } + +uint64_t i_lr64(uint64_t y, uint64_t offset){ + return ( y << offset ) | ( y >> (64 - offset)); +} + +uint64_t i_rr64(uint64_t x, uint64_t n) { + return (x >> n) | (x << (64-n)); +} diff --git a/src/crypto.h b/src/crypto.h index f54047b..79be3df 100644 --- a/src/crypto.h +++ b/src/crypto.h @@ -11,12 +11,29 @@ #include "hash/fletcher.h" #include "hash/sysvchecksum.h" #include "hash/xor.h" +#include "hash/buzhash.h" +#include "hash/cityhash.h" +#include "hash/djb2.h" +#include "hash/farmhash.h" +#include "hash/fasthash.h" +#include "hash/fnv.h" +#include "hash/jenkins.h" +#include "hash/loselose.h" +#include "hash/metrohash.h" +#include "hash/murmur.h" +#include "hash/pjw.h" +#include "hash/sdbm.h" +#include "hash/sha2-256.h" +#include "hash/spookyhash.h" #include "encode/uuencode.h" #include "encode/base64.h" unsigned i_lr(unsigned, unsigned); unsigned i_rr(unsigned, unsigned); +uint64_t i_lr64(uint64_t, uint64_t); +uint64_t i_rr64(uint64_t, uint64_t); + static const luaL_Reg crypto_function_list [] = { {"md5",l_md5}, @@ -38,6 +55,41 @@ static const luaL_Reg crypto_function_list [] = { {"fletcher32",l_fletcher32}, {"sysvchecksum",l_sysvchecksum}, {"xor8",l_xor8}, + {"setbuzhash",l_setbuzhash}, + {"buzhash8",l_buzhash8}, + {"buzhash16",l_buzhash16}, + {"cityhash32", l_cityhash32}, + {"cityhash64", l_cityhash64}, + {"cityhash128", l_cityhash128}, + {"djb2", l_djb2}, + {"farmhash32", l_farmhash32}, + {"farmhash64", l_farmhash64}, + {"fasthash32", l_fasthash32}, + {"fasthash64", l_fasthash64}, + {"fnv_0", l_fnv_0}, + {"fnv_1", l_fnv_1}, + {"fnv_a", l_fnv_a}, + {"oaat", l_oaat}, + {"loselose", l_loselose}, + {"metrohash64_v1", l_metrohash64_v1}, + {"metrohash64_v2", l_metrohash64_v2}, + {"metrohash128_v1", l_metrohash128_v1}, + {"metrohash128_v2", l_metrohash128_v2}, + {"murmur1_32", l_murmur1_32}, + {"murmur2_32", l_murmur2_32}, + {"pjw", l_pjw}, + {"sdbm", l_sdbm}, + {"sha512", l_sha512}, + {"sha384", l_sha384}, + {"sha512_t", l_sha512_t}, + {"spookyhash128_v1", l_spookyhash128_v1}, + {"spookyhash128_v2", l_spookyhash128_v2}, + {"spookyhash64_v1", l_spookyhash64_v1}, + {"spookyhash64_v2", l_spookyhash64_v2}, + {"spookyhash32_v1", l_spookyhash32_v1}, + {"spookyhash32_v2", l_spookyhash32_v2}, + + {"uuencode",l_uuencode}, {"uudecode",l_uudecode}, diff --git a/src/hash/buzhash.c b/src/hash/buzhash.c new file mode 100644 index 0000000..36b39f3 --- /dev/null +++ b/src/hash/buzhash.c @@ -0,0 +1,96 @@ +#include "../i_util.h" +#include "../crypto.h" +#include +#include +#include + +static uint8_t T[256] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14, + 15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38, + 39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62, + 63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86, + 87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107, + 108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125, + 126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143, + 144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161, + 162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179, + 180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197, + 198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215, + 216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233, + 234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251, + 252,253,254,255}; + +uint8_t i_lr8(uint8_t y, uint8_t offset){ + return ( y << offset ) | ( y >> (8 - offset)); +} + +uint16_t i_lr16(uint16_t y, uint16_t offset){ + return ( y << offset ) | ( y >> (16 - offset)); +} + +uint8_t i_buzhash8(uint8_t* in, size_t len){ + uint8_t hash = 0; + + for(int i = 0; i != len; i++){ + hash ^= i_lr8(T[(uint8_t)in[i]],len - (i + 1)); + } + + return hash; +} +uint16_t i_buzhash16(uint8_t* in, size_t len){ + uint16_t hash = 0; + + for(int i = 0; i != len; i++){ + hash ^= i_lr16(T[(uint8_t)in[i]],len - (i + 1)); + } + + return hash; +} + +int l_setbuzhash(lua_State* L){ + luaL_checktype(L, 1, LUA_TTABLE); + size_t len = lua_objlen(L,1); + + if(len != 256) { + p_error("new table must have a length of 256"); + exit(0); + } + + double s = 0; + for(int i = 0; i <= len-1; i++){ + + lua_pushinteger(L,i+1); + lua_gettable(L,1); + + T[i] = luaL_checknumber(L, -1); + lua_pop(L,1); + } + return 0; +} + +int l_buzhash8(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[3]; + uint8_t u = i_buzhash8(a, len); + + sprintf(digest,"%x",u); + + lua_pushstring(L, digest); + + return 1; +} + +int l_buzhash16(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[6]; + uint16_t u = i_buzhash16(a, len); + + sprintf(digest,"%04x",u); + + lua_pushstring(L, digest); + + return 1; +} diff --git a/src/hash/buzhash.h b/src/hash/buzhash.h new file mode 100644 index 0000000..74020ea --- /dev/null +++ b/src/hash/buzhash.h @@ -0,0 +1,5 @@ +#include "../lua.h" + +int l_setbuzhash(lua_State*); +int l_buzhash8(lua_State*); +int l_buzhash16(lua_State*); diff --git a/src/hash/cityhash.c b/src/hash/cityhash.c new file mode 100644 index 0000000..46bb1ed --- /dev/null +++ b/src/hash/cityhash.c @@ -0,0 +1,430 @@ +#include +#include +#include "cityhash.h" + +uint32_t rot32(uint32_t val, int shift) { + return ((val >> shift) | (val << (32 - shift))); +} + +uint32_t fmix(uint32_t h){ + h ^= h >> 16; + h *= 0x85ebca6b; + h ^= h >> 13; + h *= 0xc2b2ae35; + h ^= h >> 16; + return h; +} + +uint32_t mur(uint32_t a, uint32_t h) { + a *= c1; + a = rot32(a, 17); + a *= c2; + h ^= a; + h = rot32(h, 19); + return h * 5 + 0xe6546b64; +} + +uint32_t hash32len0to4(uint8_t* in, size_t len){ + uint32_t b = 0, c = 9; + for(int i = 0; i != len; i++){ + b = b * c1 + (uint32_t)in[i]; + c ^= b; + } + return fmix(mur(b, mur((uint32_t)len, c))); +} + +uint32_t UNALIGNED_LOAD32(uint8_t *p) { + return *(uint32_t*)p; + /* original google code:p + uint32_t result; + memcpy(&result, p, sizeof(result)); + return result; + */ +} + +uint32_t hash32len5to12(uint8_t* in, size_t len){ + uint32_t a = (uint32_t)(len), b = a * 5, c = 9, d = b; + a += UNALIGNED_LOAD32(in); + b += UNALIGNED_LOAD32(in + len - 4); + c += UNALIGNED_LOAD32(in + ((len >> 1) & 4)); + return fmix(mur(c, mur(b, mur(a, d)))); +} + +uint32_t hash32len13to24(uint8_t* in, size_t len){ + uint32_t a = UNALIGNED_LOAD32(in - 4 + (len >> 1)); + uint32_t b = UNALIGNED_LOAD32(in + 4); + uint32_t c = UNALIGNED_LOAD32(in + len - 8); + uint32_t d = UNALIGNED_LOAD32(in + (len >> 1)); + uint32_t e = UNALIGNED_LOAD32(in); + uint32_t f = UNALIGNED_LOAD32(in + len - 4); + uint32_t h = (uint32_t)len; + + return fmix(mur(f, mur(e, mur(d, mur(c, mur(b, mur(a, h))))))); +} + +uint32_t cityhash32(uint8_t* in, size_t len){ + if(len <= 24){ + if(len <= 12){ + if(len <= 4) return hash32len0to4(in, len); + else return hash32len5to12(in, len); + }else return hash32len13to24(in, len); + } + + uint32_t h = (uint32_t)len, g = c1 * h, f = g; + uint32_t a0 = rot32(UNALIGNED_LOAD32(in + len - 4) * c1, 17) * c2; + uint32_t a1 = rot32(UNALIGNED_LOAD32(in + len - 8) * c1, 17) * c2; + uint32_t a2 = rot32(UNALIGNED_LOAD32(in + len - 16) * c1, 17) * c2; + uint32_t a3 = rot32(UNALIGNED_LOAD32(in + len - 12) * c1, 17) * c2; + uint32_t a4 = rot32(UNALIGNED_LOAD32(in + len - 20) * c1, 17) * c2; + h ^= a0; + h = rot32(h, 19); + h = h * 5 + 0xe6546b64; + h ^= a2; + h = rot32(h, 19); + h = h * 5 + 0xe6546b64; + g ^= a1; + g = rot32(g, 19); + g = g * 5 + 0xe6546b64; + g ^= a3; + g = rot32(g, 19); + g = g * 5 + 0xe6546b64; + f += a4; + f = rot32(f, 19); + f = f * 5 + 0xe6546b64; + + for(int i = (len - 1)/20; i != 0; i--){ + uint32_t a0 = rot32(UNALIGNED_LOAD32(in) * c1, 17) * c2; + uint32_t a1 = UNALIGNED_LOAD32(in + 4); + uint32_t a2 = rot32(UNALIGNED_LOAD32(in + 8) * c1, 17) * c2; + uint32_t a3 = rot32(UNALIGNED_LOAD32(in + 12) * c1, 17) * c2; + uint32_t a4 = UNALIGNED_LOAD32(in + 16); + h ^= a0; + h = rot32(h, 18); + h = h * 5 + 0xe6546b64; + f += a1; + f = rot32(f, 19); + f = f * c1; + g += a2; + g = rot32(g, 18); + g = g * 5 + 0xe6546b64; + h ^= a3 + a1; + h = rot32(h, 19); + h = h * 5 + 0xe6546b64; + g ^= a4; + g = __builtin_bswap32(g) * 5; + h += a4 * 5; + h = __builtin_bswap32(h); + f += a0; + //PERMUTE3(f, h, g); + uint32_t temp = f; + f = h; h = temp; + temp = f; + f = g; g = temp; + // + in += 20; + } + + g = rot32(g, 11) * c1; + g = rot32(g, 17) * c1; + f = rot32(f, 11) * c1; + f = rot32(f, 17) * c1; + h = rot32(h + g, 19); + h = h * 5 + 0xe6546b64; + h = rot32(h, 17) * c1; + h = rot32(h + f, 19); + h = h * 5 + 0xe6546b64; + h = rot32(h, 17) * c1; + + return h; +} + +//64 version + +uint64_t UNALIGNED_LOAD64(uint8_t *p) { + return *(uint64_t*)p; + /* + uint64_t result; + memcpy(&result, p, sizeof(result)); + return result; + //*/ +} + +uint64_t rot64(uint64_t val, int shift) { + return ((val >> shift) | (val << (64 - shift))); +} + +uint64_t hashlen16(uint64_t u, uint64_t v, uint64_t mul) { + uint64_t a = (u ^ v) * mul; + a ^= (a >> 47); + uint64_t b = (v ^ a) * mul; + b ^= (b >> 47); + b *= mul; + return b; +} + +uint64_t shiftmix(uint64_t val) { + return val ^ (val >> 47); +} + +uint64_t hashlen0to16(uint8_t* in, size_t len){ + if(len >= 8){ + uint64_t mul = k2 + len * 2; + uint64_t a = UNALIGNED_LOAD64(in) + k2; + uint64_t b = UNALIGNED_LOAD64(in + len - 8); + uint64_t c = rot64(b, 37) * mul + a; + uint64_t d = (rot64(a, 25) + b) * mul; + return hashlen16(c, d, mul); + } + if(len >= 4){ + uint64_t mul = k2 + len * 2; + uint64_t a = UNALIGNED_LOAD32(in); + return hashlen16(len + (a << 3), UNALIGNED_LOAD32(in + len - 4), mul); + } + if(len > 0){ + uint8_t a = (uint8_t)in[0]; + uint8_t b = (uint8_t)in[len >> 1]; + uint8_t c = (uint8_t)in[len - 1]; + uint32_t y = ((uint32_t)a) + (((uint32_t)b) << 8); + uint32_t z = ((uint32_t)len) + ((uint32_t)(c) << 2); + return shiftmix(y * k2 ^ z * k0) * k2; + } + return k2; +} +uint64_t hashlen17to32(uint8_t* in, size_t len){ + uint64_t mul = k2 + len * 2; + uint64_t a = UNALIGNED_LOAD64(in) * k1; + uint64_t b = UNALIGNED_LOAD64(in + 8); + uint64_t c = UNALIGNED_LOAD64(in + len - 8) * mul; + uint64_t d = UNALIGNED_LOAD64(in + len - 16) * k2; + return hashlen16(rot64(a + b, 43) + rot64(c, 30) + d, + a + rot64(b + k2, 18) + c, mul); +} + +uint64_t hashlen33to64(uint8_t* in, size_t len){ + uint64_t mul = k2 + len * 2; + uint64_t a = UNALIGNED_LOAD64(in) * k2; + uint64_t b = UNALIGNED_LOAD64(in + 8); + uint64_t c = UNALIGNED_LOAD64(in + len - 24); + uint64_t d = UNALIGNED_LOAD64(in + len - 32); + uint64_t e = UNALIGNED_LOAD64(in + 16) * k2; + uint64_t f = UNALIGNED_LOAD64(in + 24) * 9; + uint64_t g = UNALIGNED_LOAD64(in + len - 8); + uint64_t h = UNALIGNED_LOAD64(in + len - 16) * mul; + uint64_t u = rot64(a + g, 43) + (rot64(b, 30) + c) * 9; + uint64_t v = ((a + g) ^ d) + f + 1; + uint64_t w = __builtin_bswap64((u + v) * mul) + h; + uint64_t x = rot64(e + f, 42) + c; + uint64_t y = (__builtin_bswap64((v + w) * mul) + g) * mul; + uint64_t z = e + f + c; + a = __builtin_bswap64((x + z) * mul + y) + b; + b = shiftmix((z + a) * mul + d + h) * mul; + return b + x; +} + +void WeakHashLen32WithSeeds(uint64_t w, uint64_t x, uint64_t y, uint64_t z, uint64_t a, uint64_t b, uint64_t*p1, int64_t*p2) { + a += w; + b = rot64(b + a + z, 21); + uint64_t c = a; + a += x; + a += y; + b += rot64(a, 44); + *p1 = a + z; + *p2 = b + c; + //return make_pair(a + z, b + c); +} + +void pWeakHashLen32WithSeeds(uint8_t* s, uint64_t a, uint64_t b, uint64_t* p1, int64_t* p2) { + WeakHashLen32WithSeeds(UNALIGNED_LOAD64(s), UNALIGNED_LOAD64(s + 8), + UNALIGNED_LOAD64(s + 16), UNALIGNED_LOAD64(s + 24), a, b, p1, p2); +} + +uint64_t hash128to64(uint64_t f, uint64_t s) { + uint64_t kMul = 0x9ddfea08eb382d69ULL; + uint64_t a = (f ^ s) * kMul; + a ^= (a >> 47); + uint64_t b = (s ^ a) * kMul; + b ^= (b >> 47); + b *= kMul; + return b; +} + +uint64_t HashLen16_2(uint64_t u, uint64_t v) { + return hash128to64(u, v); +} + +uint64_t cityhash64(uint8_t* in, size_t len){ + if(len <= 32){ + if(len <= 16) return hashlen0to16(in, len); + else return hashlen17to32(in, len); + } else if(len <= 64) return hashlen33to64(in, len); + + uint64_t x = UNALIGNED_LOAD64(in + len - 40); + uint64_t y = UNALIGNED_LOAD64(in + len - 16) + UNALIGNED_LOAD64(in + len - 56); + uint64_t z = HashLen16_2(UNALIGNED_LOAD64(in + len - 48) + len, UNALIGNED_LOAD64(in + len - 24)); + uint64_t v1, w1; + int64_t v2, w2; + pWeakHashLen32WithSeeds(in + len - 64, len, z, &v1, &v2); + pWeakHashLen32WithSeeds(in + len - 32, y + k1, x, &w1, &w2); + x = x * k1 + UNALIGNED_LOAD64(in); + + for(int i = (len - 1) /64; i != 0; i--){ + x = rot64(x + y + v1 + UNALIGNED_LOAD64(in + 8), 37) * k1; + y = rot64(y + v2 + UNALIGNED_LOAD64(in + 48), 42) * k1; + x ^= w2; + y += v1 + UNALIGNED_LOAD64(in + 40); + z = rot64(z + w1, 33) * k1; + pWeakHashLen32WithSeeds(in, v2 * k1, x + w1, &v1, &v2); + pWeakHashLen32WithSeeds(in + 32, z + w2, y + UNALIGNED_LOAD64(in + 16), &w1, &w2); + //std::swap(z, x); + uint64_t temp = z; + z = x; + x = temp; + in += 64; + } + //printf("%llu %llu %llu\n",x,y,z); + return HashLen16_2(HashLen16_2(v1, w1) + shiftmix(y) * k1 + z, + HashLen16_2(v2, w2) + x); +} + +void citymurmur(uint8_t* in, size_t len, uint64_t f, uint64_t s, uint64_t* o1, uint64_t* o2){ + uint64_t a = f; + uint64_t b = s; + uint64_t c = 0; + uint64_t d = 0; + + if (len <= 16) { + a = shiftmix(a * k1) * k1; + c = b * k1 + hashlen0to16(in, len); + d = shiftmix(a + (len >= 8 ? UNALIGNED_LOAD64(in) : c)); + } else { + c = HashLen16_2(UNALIGNED_LOAD64(in + len - 8) + k1, a); + d = HashLen16_2(b + len, c + UNALIGNED_LOAD64(in + len - 16)); + a += d; + + for(; len > 16; len -=16) { + a ^= shiftmix(UNALIGNED_LOAD64(in) * k1) * k1; + a *= k1; + b ^= a; + c ^= shiftmix(UNALIGNED_LOAD64(in + 8) * k1) * k1; + c *= k1; + d ^= c; + s += 16; + len -= 16; + } + } + a = HashLen16_2(a, c); + b = HashLen16_2(d, b); + //return uint128(a ^ b, HashLen16(b, a)); + *o2 = a ^ b; + *o1 = HashLen16_2(b, a); +} + +void cityhash128withseed(uint8_t* in, size_t len, uint64_t f, uint64_t s, uint64_t* o1, uint64_t* o2){ + if(len < 128){ + citymurmur(in, len, k0, k1, o2, o1); + return; + } + + uint64_t v1, w1; + int64_t v2, w2; + uint64_t x = f; + uint64_t y = s; + uint64_t z = len * k1; + + v1 = rot64(y ^ k1, 49) * k1 + UNALIGNED_LOAD64(in); + v2 = rot64(v1, 42) * k1 + UNALIGNED_LOAD64(in + 8); + w1 = rot64(y + z, 35) * k1 + x; + w2 = rot64(x + UNALIGNED_LOAD64(in + 88), 53) * k1; + + for(; len >= 128; len-=128){ + x = rot64(x + y + v1 + UNALIGNED_LOAD64(in + 8), 37) * k1; + y = rot64(y + v2 + UNALIGNED_LOAD64(in + 48), 42) * k1; + x ^= w2; + y += v1 + UNALIGNED_LOAD64(in + 40); + z = rot64(z + w1, 33) * k1; + pWeakHashLen32WithSeeds(in, v2 * k1, x + w1, &v1, &v2); + pWeakHashLen32WithSeeds(in + 32, z + w2, y + UNALIGNED_LOAD64(in + 16), &w1, &w2); + uint64_t temp = z; + z = x; + x = temp; + in += 64; + // + x = rot64(x + y + v1 + UNALIGNED_LOAD64(in + 8), 37) * k1; + y = rot64(y + v2 + UNALIGNED_LOAD64(in + 48), 42) * k1; + x ^= w2; + y += v1 + UNALIGNED_LOAD64(in + 40); + z = rot64(z + w1, 33) * k1; + pWeakHashLen32WithSeeds(in, v2 * k1, x + w1, &v1, &v2); + pWeakHashLen32WithSeeds(in + 32, z + w2, y + UNALIGNED_LOAD64(in + 16), &w1, &w2); + temp = z; + z = x; + x = temp; + in += 64; + } + x += rot64(v1 + z, 49) * k0; + y = y * k0 + rot64(w2, 37); + z = z * k0 + rot64(w1, 27); + w1 *= 9; + v1 *= k0; + + for (size_t tail_done = 0; tail_done < len; ) { + tail_done += 32; + y = rot64(x + y, 42) * k0 + v2; + w1 += UNALIGNED_LOAD64(in + len - tail_done + 16); + x = x * k0 + w1; + z += w2 + UNALIGNED_LOAD64(in + len - tail_done); + w2 += v1; + pWeakHashLen32WithSeeds(in + len - tail_done, v1 + z, v2, &v1, &v2); + v1 *= k0; + } + + x = HashLen16_2(x, v1); + y = HashLen16_2(y + z, w1); + //return uint128(HashLen16(x + v.second, w.second) + y, + // HashLen16(x + w.second, y + v.second)); + *o1 = HashLen16_2(x + v2, w2) + y; + *o2 = HashLen16_2(x + w2, y + v2); + +} + +void cityhash128(uint8_t* in, size_t len, uint64_t* f, uint64_t* s){ + if(len >= 16) return cityhash128withseed(in + 16, len - 16,UNALIGNED_LOAD64(in), UNALIGNED_LOAD64(in + 8) + k0, f, s); + return cityhash128withseed(in, len, k0, k1, f, s); +} + +int l_cityhash32(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[32]; + + uint32_t u = cityhash32(a, len); + sprintf(digest,"%08x",u); + lua_pushstring(L, digest); + return 1; +} + +int l_cityhash64(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[64]; + + uint64_t u = cityhash64(a, len); + sprintf(digest,"%016lx",u); + lua_pushstring(L, digest); + return 1; +} + +int l_cityhash128(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[128]; + + uint64_t u1, u2; + cityhash128(a, len, &u1, &u2); + sprintf(digest,"%08lx%08lx",u1, u2); + lua_pushstring(L, digest); + return 1; +} diff --git a/src/hash/cityhash.h b/src/hash/cityhash.h new file mode 100644 index 0000000..77d1ff6 --- /dev/null +++ b/src/hash/cityhash.h @@ -0,0 +1,40 @@ +#include "../lua.h" +#include + +static const uint32_t c1 = 0xcc9e2d51; +static const uint32_t c2 = 0x1b873593; + +uint32_t rot32(uint32_t val, int shift); +uint32_t fmix(uint32_t h); +uint32_t mur(uint32_t a, uint32_t h); +uint32_t hash32len0to4(uint8_t* in, size_t len); +uint32_t UNALIGNED_LOAD32(uint8_t *p); +uint32_t hash32len5to12(uint8_t* in, size_t len); +uint32_t hash32len13to24(uint8_t* in, size_t len); +uint32_t cityhash32(uint8_t* in, size_t len); + +//64 version + +static const uint64_t k0 = 0xc3a5c85c97cb3127ULL; +static const uint64_t k1 = 0xb492b66fbe98f273ULL; +static const uint64_t k2 = 0x9ae16a3b2f90404fULL; + +uint64_t UNALIGNED_LOAD64(uint8_t *p); +uint64_t rot64(uint64_t val, int shift); +uint64_t hashlen16(uint64_t u, uint64_t v, uint64_t mul); +uint64_t shiftmix(uint64_t val); +uint64_t hashlen0to16(uint8_t* in, size_t len); +uint64_t hashlen17to32(uint8_t* in, size_t len); +uint64_t hashlen33to64(uint8_t* in, size_t len); +void WeakHashLen32WithSeeds(uint64_t w, uint64_t x, uint64_t y, uint64_t z, uint64_t a, uint64_t b, uint64_t*p1, int64_t*p2); +void pWeakHashLen32WithSeeds(uint8_t* s, uint64_t a, uint64_t b, uint64_t* p1, int64_t* p2); +uint64_t hash128to64(uint64_t f, uint64_t s); +uint64_t HashLen16_2(uint64_t u, uint64_t v); +uint64_t cityhash64(uint8_t* in, size_t len); +void citymurmur(uint8_t* in, size_t len, uint64_t f, uint64_t s, uint64_t* o1, uint64_t* o2); +void cityhash128withseed(uint8_t* in, size_t len, uint64_t f, uint64_t s, uint64_t* o1, uint64_t* o2); +void cityhash128(uint8_t* in, size_t len, uint64_t* f, uint64_t* s); + +int l_cityhash32(lua_State*); +int l_cityhash64(lua_State*); +int l_cityhash128(lua_State*); diff --git a/src/hash/djb2.c b/src/hash/djb2.c new file mode 100644 index 0000000..8949ca8 --- /dev/null +++ b/src/hash/djb2.c @@ -0,0 +1,27 @@ +#include "../i_util.h" +#include "../crypto.h" +#include +#include + +uint64_t djb2(uint8_t* in, size_t len){ + uint64_t hash = 5381; + + for(int i = 0; i != len; i++){ + hash = ((hash << 5) + hash) + (uint64_t)*in; + in++; + } + + return hash; +} + +int l_djb2(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[64]; + + uint64_t u = djb2(a, len); + sprintf(digest,"%08lx",u); + lua_pushstring(L, digest); + return 1; +} diff --git a/src/hash/djb2.h b/src/hash/djb2.h new file mode 100644 index 0000000..9c8036a --- /dev/null +++ b/src/hash/djb2.h @@ -0,0 +1,3 @@ +#include "../lua.h" + +int l_djb2(lua_State*); diff --git a/src/hash/farmhash.c b/src/hash/farmhash.c new file mode 100644 index 0000000..93e194b --- /dev/null +++ b/src/hash/farmhash.c @@ -0,0 +1,169 @@ +#include "../i_util.h" +#include "../crypto.h" //include city hash too +#include + +uint32_t farmhash32len13to24(uint8_t* in, size_t len) { + uint32_t seed = 0; + uint32_t a = UNALIGNED_LOAD32(in - 4 + (len >> 1)); + uint32_t b = UNALIGNED_LOAD32(in + 4); + uint32_t c = UNALIGNED_LOAD32(in + len - 8); + uint32_t d = UNALIGNED_LOAD32(in + (len >> 1)); + uint32_t e = UNALIGNED_LOAD32(in); + uint32_t f = UNALIGNED_LOAD32(in + len - 4); + uint32_t h = d * c1 + len + seed; + a = rot32(a, 12) + f; + h = mur(c, h) + a; + a = rot32(a, 3) + c; + h = mur(e, h) + a; + a = rot32(a + f, 12) + d; + h = mur(b ^ seed, h) + a; + return fmix(h); +} + +uint32_t farmhash32(uint8_t* in, size_t len){ + if(len <= 24){ + if(len <= 12){ + if(len <= 4) return hash32len0to4(in, len); + else return hash32len5to12(in, len); + } else return farmhash32len13to24(in, len); + } + + uint32_t h = len, g = c1 * len, f = g; + uint32_t a0 = rot32(UNALIGNED_LOAD32(in + len - 4) * c1, 17) * c2; + uint32_t a1 = rot32(UNALIGNED_LOAD32(in + len - 8) * c1, 17) * c2; + uint32_t a2 = rot32(UNALIGNED_LOAD32(in + len - 16) * c1, 17) * c2; + uint32_t a3 = rot32(UNALIGNED_LOAD32(in + len - 12) * c1, 17) * c2; + uint32_t a4 = rot32(UNALIGNED_LOAD32(in + len - 20) * c1, 17) * c2; + + h ^= a0; + h = rot32(h, 19); + h = h * 5 + 0xe6546b64; + h ^= a2; + h = rot32(h, 19); + h = h * 5 + 0xe6546b64; + g ^= a1; + g = rot32(g, 19); + g = g * 5 + 0xe6546b64; + g ^= a3; + g = rot32(g, 19); + g = g * 5 + 0xe6546b64; + f += a4; + f = rot32(f, 19) + 113; + size_t iters = (len - 1) / 20; + for(int i = (len - 1) / 20; i != 0; i--){ + uint32_t a = UNALIGNED_LOAD32(in); + uint32_t b = UNALIGNED_LOAD32(in + 4); + uint32_t c = UNALIGNED_LOAD32(in + 8); + uint32_t d = UNALIGNED_LOAD32(in + 12); + uint32_t e = UNALIGNED_LOAD32(in + 16); + h += a; + g += b; + f += c; + h = mur(d, h) + e; + g = mur(c, g) + a; + f = mur(b + e * c1, f) + d; + f += g; + g += f; + in += 20; + } + g = rot32(g, 11) * c1; + g = rot32(g, 17) * c1; + f = rot32(f, 11) * c1; + f = rot32(f, 17) * c1; + h = rot32(h + g, 19); + h = h * 5 + 0xe6546b64; + h = rot32(h, 17) * c1; + h = rot32(h + f, 19); + h = h * 5 + 0xe6546b64; + h = rot32(h, 17) * c1; + return h; +} + +uint64_t farmhashlen33to64(uint8_t *s, size_t len) { + uint64_t mul = k2 + len * 2; + uint64_t a = UNALIGNED_LOAD64(s) * k2; + uint64_t b = UNALIGNED_LOAD64(s + 8); + uint64_t c = UNALIGNED_LOAD64(s + len - 8) * mul; + uint64_t d = UNALIGNED_LOAD64(s + len - 16) * k2; + uint64_t y = rot64(a + b, 43) + rot64(c, 30) + d; + uint64_t z = hashlen16(y, a + rot64(b + k2, 18) + c, mul); + uint64_t e = UNALIGNED_LOAD64(s + 16) * mul; + uint64_t f = UNALIGNED_LOAD64(s + 24); + uint64_t g = (y + UNALIGNED_LOAD64(s + len - 32)) * mul; + uint64_t h = (z + UNALIGNED_LOAD64(s + len - 24)) * mul; + return hashlen16(rot64(e + f, 43) + rot64(g, 30) + h, + e + rot64(f + a, 18) + g, mul); +} + +uint64_t farmhash64(uint8_t* in, size_t len){ + if(len <= 32){ + if(len <= 16) return hashlen0to16(in, len); + else return hashlen17to32(in, len); + } else if(len <= 64) return farmhashlen33to64(in, len); + + uint64_t seed = 81; + uint64_t x = seed; + uint64_t y = seed * k1 + 113; + uint64_t z = shiftmix(y * k2 + 113) * k2; + + uint64_t v1 = 0, w1 = 0; + int64_t v2 = 0, w2 = 0; + x = x * k2 + UNALIGNED_LOAD64(in); + uint8_t* end = in + ((len - 1) / 64) * 64; + uint8_t* last64 = end + ((len - 1) & 63) - 63; + //assert(in + len - 64 == last64); + for(; in != end; in += 64) { + x = rot64(x + y + v1 + UNALIGNED_LOAD64(in + 8), 37) * k1; + y = rot64(y + v2 + UNALIGNED_LOAD64(in + 48), 42) * k1; + x ^= w2; + y += v1 + UNALIGNED_LOAD64(in + 40); + z = rot64(z + w1, 33) * k1; + pWeakHashLen32WithSeeds(in, v2 * k1, x + w1, &v1, &v2); + pWeakHashLen32WithSeeds(in + 32, z + w2, y + UNALIGNED_LOAD64(in + 16), &w1, &w2); + uint64_t temp = z; + z = x; x = temp; + } + uint64_t mul = k1 + ((z & 0xff) << 1); + + in = last64; + w1 += ((len - 1) & 63); + v1 += w1; + w1 += v1; + x = rot64(x + y + v1 + UNALIGNED_LOAD64(in + 8), 37) * mul; + y = rot64(y + v2 + UNALIGNED_LOAD64(in + 48), 42) * mul; + x ^= w2 * 9; + y += v1 * 9 + UNALIGNED_LOAD64(in + 40); + z = rot64(z + w1, 33) * mul; + pWeakHashLen32WithSeeds(in, v2 * mul, x + w1, &v1, &v2); + pWeakHashLen32WithSeeds(in + 32, z + w2, y + UNALIGNED_LOAD64(in + 16), &w1, &w2); + uint64_t temp = z; + z = x; x = temp; + return hashlen16(hashlen16(v1, w1, mul) + shiftmix(y) * k0 + z, + hashlen16(v2, w2, mul) + x, + mul); + return 1; +} + +int l_farmhash32(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[32]; + + uint32_t u = farmhash32(a, len); + sprintf(digest,"%04x",u); + lua_pushstring(L, digest); + return 1; +} + +int l_farmhash64(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[64]; + + uint64_t u = farmhash64(a, len); + sprintf(digest,"%08lx",u); + lua_pushstring(L, digest); + return 1; +} diff --git a/src/hash/farmhash.h b/src/hash/farmhash.h new file mode 100644 index 0000000..8d99a46 --- /dev/null +++ b/src/hash/farmhash.h @@ -0,0 +1,4 @@ +#include "../lua.h" + +int l_farmhash32(lua_State*); +int l_farmhash64(lua_State*); diff --git a/src/hash/fasthash.c b/src/hash/fasthash.c new file mode 100644 index 0000000..3ad0ba2 --- /dev/null +++ b/src/hash/fasthash.c @@ -0,0 +1,83 @@ +#include "../i_util.h" +#include "../crypto.h" +#include +#include +//almost entirely taken from https://github.com/ztanml/fast-hash/blob/master/fasthash.c + +#define mix(h) ({ \ + (h) ^= (h) >> 23; \ + (h) *= 0x2127599bf4325c37ULL; \ + (h) ^= (h) >> 47; }) + +uint64_t fasthash64(uint8_t* in, size_t len, uint64_t seed){ + uint64_t m = 0x880355f21e6d1965ULL; + uint64_t hash = seed ^ (len * m); + uint64_t* data = (uint64_t*)in; + uint64_t v; + for(;len >= 8; len-=8){ + v=*data++; + hash^=mix(v); + hash*=m; + + in+=4; + } + + uint8_t* data2 = (uint8_t*)data; + v=0; + + switch (len & 7) { + case 7: + v ^= (uint64_t)data2[6] << 48; + case 6: + v ^= (uint64_t)data2[5] << 40; + case 5: + v ^= (uint64_t)data2[4] << 32; + case 4: + v ^= (uint64_t)data2[3] << 24; + case 3: + v ^= (uint64_t)data2[2] << 16; + case 2: + v ^= (uint64_t)data2[1] << 8; + case 1: + v ^= (uint64_t)data2[0]; + hash ^= mix(v); + hash *= m; + } + + return mix(hash); +} + +uint32_t fasthash32(uint8_t *buf, size_t len, uint32_t seed){ + uint64_t hash = fasthash64(buf, len, seed); + return hash - (hash >> 32); +} + +int l_fasthash64(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + int argv = lua_gettop(L); + uint64_t seed = 0; + if(argv > 1) seed = luaL_checkinteger(L, 2); + + char digest[64]; + + uint64_t u = fasthash64(a, len, seed); + sprintf(digest,"%08lx",u); + lua_pushstring(L, digest); + return 1; +} + +int l_fasthash32(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + int argv = lua_gettop(L); + uint32_t seed = 0; + if(argv > 1) seed = luaL_checkinteger(L, 2); + + char digest[32]; + + uint32_t u = fasthash32(a, len, seed); + sprintf(digest,"%04x",u); + lua_pushstring(L, digest); + return 1; +} diff --git a/src/hash/fasthash.h b/src/hash/fasthash.h new file mode 100644 index 0000000..feff2fe --- /dev/null +++ b/src/hash/fasthash.h @@ -0,0 +1,4 @@ +#include "../lua.h" + +int l_fasthash32(lua_State*); +int l_fasthash64(lua_State*); diff --git a/src/hash/fnv.c b/src/hash/fnv.c new file mode 100644 index 0000000..1fc4d0a --- /dev/null +++ b/src/hash/fnv.c @@ -0,0 +1,62 @@ +#include "../i_util.h" +#include "../crypto.h" +#include +#include + + +uint64_t fnv_1(uint8_t* in, size_t len, enum fnv_version A){ + uint64_t hash = (A != v_0) * 0xcbf29ce484222325; + uint64_t prime = 0x100000001b3; + + for(int i = 0; i != len; i++){ + switch(A){ + case v_1: + case v_0: + hash *= prime; + hash ^= in[i]; + break; + case v_a: + hash ^= in[i]; + hash *= prime; + break; + } + } + + return hash; +} + +int l_fnv_0(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[64]; + + uint64_t u = fnv_1(a, len, v_0); + sprintf(digest,"%08lx",u); + lua_pushstring(L, digest); + return 1; +} + +int l_fnv_1(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[64]; + + uint64_t u = fnv_1(a, len, v_1); + sprintf(digest,"%08lx",u); + lua_pushstring(L, digest); + return 1; +} + +int l_fnv_a(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[64]; + + uint64_t u = fnv_1(a, len, v_a); + sprintf(digest,"%08lx",u); + lua_pushstring(L, digest); + return 1; +} diff --git a/src/hash/fnv.h b/src/hash/fnv.h new file mode 100644 index 0000000..029abcc --- /dev/null +++ b/src/hash/fnv.h @@ -0,0 +1,9 @@ +#include "../lua.h" + +enum fnv_version { + v_1, v_a, v_0 +}; + +int l_fnv_1(lua_State*); +int l_fnv_a(lua_State*); +int l_fnv_0(lua_State*); diff --git a/src/hash/jenkins.c b/src/hash/jenkins.c new file mode 100644 index 0000000..b11de8e --- /dev/null +++ b/src/hash/jenkins.c @@ -0,0 +1,31 @@ +#include "../i_util.h" +#include "../crypto.h" +#include +#include + +uint32_t jenkins_oaat(uint8_t* in, size_t len){ + uint32_t hash = 0; + + for(int i = 0; i != len;){ + hash += in[i++]; + hash += hash << 10; + hash ^= hash >> 6; + } + hash += hash << 3; + hash ^= hash >> 11; + hash += hash << 15; + + return hash; +} + +int l_oaat(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[64]; + + uint32_t u = jenkins_oaat(a, len); + sprintf(digest,"%04x",u); + lua_pushstring(L, digest); + return 1; +} diff --git a/src/hash/jenkins.h b/src/hash/jenkins.h new file mode 100644 index 0000000..d5959d2 --- /dev/null +++ b/src/hash/jenkins.h @@ -0,0 +1,3 @@ +#include "../lua.h" + +int l_oaat(lua_State*); diff --git a/src/hash/loselose.c b/src/hash/loselose.c new file mode 100644 index 0000000..a421079 --- /dev/null +++ b/src/hash/loselose.c @@ -0,0 +1,27 @@ +#include "../i_util.h" +#include "../crypto.h" +#include +#include + +uint64_t loselose(uint8_t* in, size_t len){ + uint64_t hash = 0; + + for(int i = 0; i != len; i++){ + hash += (uint64_t)*in; + in++; + } + + return hash; +} + +int l_loselose(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[64]; + + uint64_t u = loselose(a, len); + sprintf(digest,"%08lx",u); + lua_pushstring(L, digest); + return 1; +} diff --git a/src/hash/loselose.h b/src/hash/loselose.h new file mode 100644 index 0000000..dc7d200 --- /dev/null +++ b/src/hash/loselose.h @@ -0,0 +1,3 @@ +#include "../lua.h" + +int l_loselose(lua_State*); diff --git a/src/hash/metrohash.c b/src/hash/metrohash.c new file mode 100644 index 0000000..0b6ca42 --- /dev/null +++ b/src/hash/metrohash.c @@ -0,0 +1,227 @@ +#include "../i_util.h" +#include "../crypto.h" +#include +#include + +#define u64(a) (*(uint64_t*)a) +#define u32(a) (*(uint32_t*)a) +#define u16(a) (*(uint16_t*)a) +#define u8(a) (*(uint8_t*)a) + +enum metrohash_version { + v1, v2 +}; + +uint64_t metrohash64(uint8_t* in, size_t len, uint32_t seed, enum metrohash_version v){ + uint64_t k0, k1, k2, k3, inner_r, inner_r2; + if(v == v1){ + k0 = 0xC83A91E1; + k1 = 0x8648DBDB; + k2 = 0x7BDEC03B; + k3 = 0x2F5870A5; + inner_r = 33; + inner_r2 = 33; + } else { + k0 = 0xD6D018F5; + k1 = 0xA2AA033B; + k2 = 0x62992FC1; + k3 = 0x30BC5B29; + inner_r = 30; + inner_r2 = 29; + } + + uint8_t* end = in + len; + uint64_t hash = ((((uint64_t)seed) + k2) * k0) + len; + + if(len >= 32){ + uint64_t v[4]; + v[0] = hash; + v[1] = hash; + v[2] = hash; + v[3] = hash; + + for(; in <= (end - 32);){ + v[0] += u64(in) * k0; in += 8; v[0] = rot64(v[0],29) + v[2]; + v[1] += u64(in) * k1; in += 8; v[1] = rot64(v[1],29) + v[3]; + v[2] += u64(in) * k2; in += 8; v[2] = rot64(v[2],29) + v[0]; + v[3] += u64(in) * k3; in += 8; v[3] = rot64(v[3],29) + v[1]; + } + + v[2] ^= rot64(((v[0] + v[3]) * k0) + v[1], inner_r) * k1; + v[3] ^= rot64(((v[1] + v[2]) * k1) + v[0], inner_r) * k0; + v[0] ^= rot64(((v[0] + v[2]) * k0) + v[3], inner_r) * k1; + v[1] ^= rot64(((v[1] + v[3]) * k1) + v[2], inner_r) * k0; + hash += v[0] ^ v[1]; + } + + if ((end - in) >= 16){ + uint64_t v0 = hash + (u64(in) * (v == v1? k0 : k2)); in += 8; v0 = rot64(v0,inner_r2) * (v == v1? k1 : k3); + uint64_t v1 = hash + (u64(in) * (v == v1? k1 : k2)); in += 8; v1 = rot64(v1,inner_r2) * (v == v1? k2 : k3); + v0 ^= rot64(v0 * k0, (v == v1? 35 : 34)) + v1; + v1 ^= rot64(v1 * k3, (v == v1? 35 : 34)) + v0; + hash += v1; + } + + if ((end - in) >= 8){ + hash += u64(in) * k3; in += 8; + hash ^= rot64(hash, (v == v1? 33 : 36)) * k1; + + } + + if ((end - in) >= 4){ + hash += u32(in) * k3; in += 4; + hash ^= rot64(hash, 15) * k1; + } + + if ((end - in) >= 2){ + hash += u16(in) * k3; in += 2; + hash ^= rot64(hash, (v == v1? 13 : 15)) * k1; + } + + if ((end - in) >= 1){ + hash += u8(in) * k3; + hash ^= rot64(hash, (v == v1? 25 : 23)) * k1; + } + + hash ^= rot64(hash, (v == v1? 33 : 28)); + hash *= k0; + hash ^= rot64(hash, (v == v1? 33 : 29)); + + return hash; +} + +void metrohash128(uint8_t* in, size_t len, uint32_t seed, uint64_t *a, uint64_t *b, enum metrohash_version ver){ + uint64_t k0 = 0xC83A91E1; + uint64_t k1 = 0x8648DBDB; + uint64_t k2 = 0x7BDEC03B; + uint64_t k3 = 0x2F5870A5; + + if(ver == v2){ + k0 = 0xD6D018F5; + k1 = 0xA2AA033B; + k2 = 0x62992FC1; + k3 = 0x30BC5B29; + } + + uint8_t * end = in + len; + + uint64_t v[4]; + + v[0] = ((((uint64_t)seed) - k0) * k3) + len; + v[1] = ((((uint64_t)seed) + k1) * k2) + len; + + if(len >= 32){ + v[2] = ((((uint64_t)seed) + k0) * k2) + len; + v[3] = ((((uint64_t)seed) - k1) * k3) + len; + + for(;in <= end - 32;){ + v[0] += u64(in) * k0; in += 8; v[0] = rot64(v[0],29) + v[2]; + v[1] += u64(in) * k1; in += 8; v[1] = rot64(v[1],29) + v[3]; + v[2] += u64(in) * k2; in += 8; v[2] = rot64(v[2],29) + v[0]; + v[3] += u64(in) * k3; in += 8; v[3] = rot64(v[3],29) + v[1]; + } + + v[2] ^= rot64(((v[0] + v[3]) * k0) + v[1], ver == v1 ? 26 : 33) * k1; + v[3] ^= rot64(((v[1] + v[2]) * k1) + v[0], ver == v1 ? 26 : 33) * k0; + v[0] ^= rot64(((v[0] + v[2]) * k0) + v[3], ver == v1 ? 26 : 33) * k1; + v[1] ^= rot64(((v[1] + v[3]) * k1) + v[2], ver == v1 ? 26 : 33) * k0; + } + + if ((end - in) >= 16){ + v[0] += u64(in) * k2; in += 8; v[0] = rot64(v[0],ver == v1 ? 33 : 29) * k3; + v[1] += u64(in) * k2; in += 8; v[1] = rot64(v[1],ver == v1 ? 33 : 29) * k3; + v[0] ^= rot64((v[0] * k2) + v[1], ver == v1 ? 17 : 29) * k1; + v[1] ^= rot64((v[1] * k3) + v[0], ver == v1 ? 17 : 29) * k0; + } + + if ((end - in) >= 8){ + v[0] += u64(in) * k2; in += 8; v[0] = rot64(v[0],ver == v1 ? 33 : 29) * k3; + v[0] ^= rot64((v[0] * k2) + v[1], ver == v1 ? 20 : 29) * k1; + } + + if ((end - in) >= 4){ + v[1] += u32(in) * k2; in += 4; v[1] = rot64(v[1],ver == v1 ? 33 : 29) * k3; + v[1] ^= rot64((v[1] * k3) + v[0], ver == v1 ? 18 : 25) * k0; + } + + if ((end - in) >= 2){ + v[0] += u16(in) * k2; in += 2; v[0] = rot64(v[0],ver == v1 ? 33 : 29) * k3; + v[0] ^= rot64((v[0] * k2) + v[1], ver == v1 ? 24 : 30) * k1; + } + + if ((end - in) >= 1){ + v[1] += u8(in) * k2; v[1] = rot64(v[1],ver == v1 ? 33 : 29) * k3; + v[1] ^= rot64((v[1] * k3) + v[0], ver == v1 ? 24 : 18) * k0; + } + + v[0] += rot64((v[0] * k0) + v[1], ver == v1 ? 13 : 33); + v[1] += rot64((v[1] * k1) + v[0], ver == v1 ? 37 : 33); + v[0] += rot64((v[0] * k2) + v[1], ver == v1 ? 13 : 33); + v[1] += rot64((v[1] * k3) + v[0], ver == v1 ? 37 : 33); + + //printf("%llx %llx",v[0],v[1]); + *a = v[0]; + *b = v[1]; +} + +int l_metrohash64_v1(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + int argv = lua_gettop(L); + uint64_t seed = 0; + if(argv > 1) seed = luaL_checkinteger(L, 2); + + char digest[64]; + + uint64_t u = metrohash64(a, len, seed, v1); + sprintf(digest,"%016lx",u); + lua_pushstring(L, digest); + return 1; +} + +int l_metrohash64_v2(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + int argv = lua_gettop(L); + uint64_t seed = 0; + if(argv > 1) seed = luaL_checkinteger(L, 2); + + char digest[64]; + + uint64_t u = metrohash64(a, len, seed, v2); + sprintf(digest,"%016lx",u); + lua_pushstring(L, digest); + return 1; +} + +int l_metrohash128_v1(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + int argv = lua_gettop(L); + uint64_t seed = 0; + if(argv > 1) seed = luaL_checkinteger(L, 2); + + char digest[64]; + + uint64_t u1, u2; + metrohash128(a, len, seed, &u1, &u2, v1); + sprintf(digest,"%016lx%016lx",u1,u2); + lua_pushstring(L, digest); + return 1; +} + +int l_metrohash128_v2(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + int argv = lua_gettop(L); + uint64_t seed = 0; + if(argv > 1) seed = luaL_checkinteger(L, 2); + + char digest[64]; + + uint64_t u1, u2; + metrohash128(a, len, seed, &u1, &u2, v2); + sprintf(digest,"%016lx%016lx",u1,u2); + lua_pushstring(L, digest); + return 1; +} diff --git a/src/hash/metrohash.h b/src/hash/metrohash.h new file mode 100644 index 0000000..30dabb2 --- /dev/null +++ b/src/hash/metrohash.h @@ -0,0 +1,6 @@ +#include "../lua.h" + +int l_metrohash64_v1(lua_State*); +int l_metrohash64_v2(lua_State*); +int l_metrohash128_v1(lua_State*); +int l_metrohash128_v2(lua_State*); diff --git a/src/hash/murmur.c b/src/hash/murmur.c new file mode 100644 index 0000000..9d913db --- /dev/null +++ b/src/hash/murmur.c @@ -0,0 +1,101 @@ +#include "../i_util.h" +#include "../crypto.h" +#include +#include + +uint32_t murmur1_32(uint8_t* in, size_t len, uint32_t seed){ + uint32_t m = 0xc6a4a793; + uint32_t hash = seed ^ (len * m); + + for(;len >= 4; len-=4){ + hash+=*(uint32_t*)in; + hash*=m; + hash^=hash >> 16; + + in+=4; + } + + switch(len){ + case 3: + hash+=in[2]<<16; + case 2: + hash+=in[1]<<8; + case 1: + hash+=in[0]; + hash*=m; + hash^=hash>>16; + break; + } + + hash*=m; + hash^=hash>>10; + hash*=m; + hash^=hash>>17; + + return hash; +} + +uint32_t murmur2_32(uint8_t* in, size_t len, uint32_t seed){ + uint32_t m = 0x5bd1e995; + uint32_t hash = seed ^ len; + + for(;len >= 4; len-=4){ + uint32_t k = *(uint32_t*)in; + + k*=m; + k^=k>>24; + k*=m; + + hash*=m; + hash^=k; + + in+=4; + } + + switch(len){ + case 3: + hash+=in[2]<<16; + case 2: + hash+=in[1]<<8; + case 1: + hash+=in[0]; + hash*=m; + break; + } + + hash^=hash>>13; + hash*=m; + hash^=hash>>15; + + return hash; +} + +int l_murmur1_32(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + int argv = lua_gettop(L); + uint64_t seed = 0; + if(argv > 1) seed = luaL_checkinteger(L, 2); + + char digest[64]; + + uint64_t u = murmur1_32(a, len, seed); + sprintf(digest,"%08lx",u); + lua_pushstring(L, digest); + return 1; +} + +int l_murmur2_32(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + int argv = lua_gettop(L); + uint64_t seed = 0; + if(argv > 1) seed = luaL_checkinteger(L, 2); + + char digest[64]; + + uint64_t u = murmur2_32(a, len, seed); + sprintf(digest,"%08lx",u); + lua_pushstring(L, digest); + return 1; +} diff --git a/src/hash/murmur.h b/src/hash/murmur.h new file mode 100644 index 0000000..d7d7fc1 --- /dev/null +++ b/src/hash/murmur.h @@ -0,0 +1,4 @@ +#include "../lua.h" + +int l_murmur1_32(lua_State*); +int l_murmur2_32(lua_State*); diff --git a/src/hash/pjw.c b/src/hash/pjw.c new file mode 100644 index 0000000..8494ba2 --- /dev/null +++ b/src/hash/pjw.c @@ -0,0 +1,31 @@ +#include "../i_util.h" +#include "../crypto.h" + +#include +#include + +uint32_t pjw(uint8_t* in, size_t len){ + uint32_t hash = 0; + uint32_t high; + + for(int i = 0; i != len; i++){ + hash = (hash << 4) + *in++; + if((high = (hash & 0xf0000000))) + hash ^= high >> 24; + hash &= ~high; + } + + return hash; +} + +int l_pjw(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[32]; + + uint32_t u = pjw(a, len); + sprintf(digest,"%08x",u); + lua_pushstring(L, digest); + return 1; +} diff --git a/src/hash/pjw.h b/src/hash/pjw.h new file mode 100644 index 0000000..7a3c1de --- /dev/null +++ b/src/hash/pjw.h @@ -0,0 +1,3 @@ +#include "../lua.h" + +int l_pjw(lua_State*); diff --git a/src/hash/sdbm.c b/src/hash/sdbm.c new file mode 100644 index 0000000..bec251e --- /dev/null +++ b/src/hash/sdbm.c @@ -0,0 +1,28 @@ +#include "../i_util.h" +#include "../crypto.h" +#include +#include + +uint64_t sdbm(uint8_t* in, size_t len){ + uint64_t hash = 0; + + for(int i = 0; i != len; i++){ + hash = (uint64_t)*in + (hash << 6) + (hash << 16) - hash; + in++; + } + + return hash; +} + +int l_sdbm(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[64]; + + uint64_t u = sdbm(a, len); + sprintf(digest,"%016lx",u); + lua_pushstring(L, digest); + return 1; +} + diff --git a/src/hash/sdbm.h b/src/hash/sdbm.h new file mode 100644 index 0000000..1420e48 --- /dev/null +++ b/src/hash/sdbm.h @@ -0,0 +1,3 @@ +#include "../lua.h" + +int l_sdbm(lua_State*); diff --git a/src/hash/sha2-256.c b/src/hash/sha2-256.c new file mode 100644 index 0000000..34afe63 --- /dev/null +++ b/src/hash/sha2-256.c @@ -0,0 +1,211 @@ +#include "../i_util.h" +#include "../crypto.h" +#include +#include +#include +#include + +void endian_swap128(__uint128_t *x){ + uint8_t *y = (uint8_t*)x; + for (size_t low = 0, high = sizeof(__uint128_t) - 1; high > low; low++, high--){ + y[low] ^= y[high]; + y[high] ^= y[low]; + y[low] ^= y[high]; + } +} + +void endian_swap64(uint64_t *x){ + uint8_t *y = (uint8_t*)x; + for (size_t low = 0, high = sizeof(uint64_t) - 1; high > low; low++, high--){ + y[low] ^= y[high]; + y[high] ^= y[low]; + y[low] ^= y[high]; + } +} + +struct iv { + uint64_t h0, h1, h2, h3, h4, h5, h6, h7; +}; + +static const struct iv sha512_iv = {.h0 = 0x6a09e667f3bcc908, .h1 = 0xbb67ae8584caa73b, .h2 = 0x3c6ef372fe94f82b, .h3 = 0xa54ff53a5f1d36f1, + .h4 = 0x510e527fade682d1, .h5 = 0x9b05688c2b3e6c1f, .h6 = 0x1f83d9abfb41bd6b, .h7 = 0x5be0cd19137e2179}; + +static const struct iv sha384_iv = {.h0 = 0xcbbb9d5dc1059ed8, .h1 = 0x629a292a367cd507, .h2 = 0x9159015a3070dd17, .h3 = 0x152fecd8f70e5939, + .h4 = 0x67332667ffc00b31, .h5 = 0x8eb44a8768581511, .h6 = 0xdb0c2e0d64f98fa7, .h7 = 0x47b5481dbefa4fa4}; + +void sha512_gen(uint64_t* out_stream, uint8_t* input, struct iv sha_iv){ + uint64_t h0 = sha_iv.h0, h1 = sha_iv.h1, h2 = sha_iv.h2, h3 = sha_iv.h3, h4 = sha_iv.h4, h5 = sha_iv.h5, h6 = sha_iv.h6, h7 = sha_iv.h7; + + const uint64_t k[80] = {0x428a2f98d728ae22, 0x7137449123ef65cd, 0xb5c0fbcfec4d3b2f, 0xe9b5dba58189dbbc, 0x3956c25bf348b538, + 0x59f111f1b605d019, 0x923f82a4af194f9b, 0xab1c5ed5da6d8118, 0xd807aa98a3030242, 0x12835b0145706fbe, + 0x243185be4ee4b28c, 0x550c7dc3d5ffb4e2, 0x72be5d74f27b896f, 0x80deb1fe3b1696b1, 0x9bdc06a725c71235, + 0xc19bf174cf692694, 0xe49b69c19ef14ad2, 0xefbe4786384f25e3, 0x0fc19dc68b8cd5b5, 0x240ca1cc77ac9c65, + 0x2de92c6f592b0275, 0x4a7484aa6ea6e483, 0x5cb0a9dcbd41fbd4, 0x76f988da831153b5, 0x983e5152ee66dfab, + 0xa831c66d2db43210, 0xb00327c898fb213f, 0xbf597fc7beef0ee4, 0xc6e00bf33da88fc2, 0xd5a79147930aa725, + 0x06ca6351e003826f, 0x142929670a0e6e70, 0x27b70a8546d22ffc, 0x2e1b21385c26c926, 0x4d2c6dfc5ac42aed, + 0x53380d139d95b3df, 0x650a73548baf63de, 0x766a0abb3c77b2a8, 0x81c2c92e47edaee6, 0x92722c851482353b, + 0xa2bfe8a14cf10364, 0xa81a664bbc423001, 0xc24b8b70d0f89791, 0xc76c51a30654be30, 0xd192e819d6ef5218, + 0xd69906245565a910, 0xf40e35855771202a, 0x106aa07032bbd1b8, 0x19a4c116b8d2d0c8, 0x1e376c085141ab53, + 0x2748774cdf8eeb99, 0x34b0bcb5e19b48a8, 0x391c0cb3c5c95a63, 0x4ed8aa4ae3418acb, 0x5b9cca4f7763e373, + 0x682e6ff3d6b2b8a3, 0x748f82ee5defb2fc, 0x78a5636f43172f60, 0x84c87814a1f0ab72, 0x8cc702081a6439ec, + 0x90befffa23631e28, 0xa4506cebde82bde9, 0xbef9a3f7b2c67915, 0xc67178f2e372532b, 0xca273eceea26619c, + 0xd186b8c721c0c207, 0xeada7dd6cde0eb1e, 0xf57d4f7fee6ed178, 0x06f067aa72176fba, 0x0a637dc5a2c898a6, + 0x113f9804bef90dae, 0x1b710b35131c471b, 0x28db77f523047d84, 0x32caab7b40c72493, 0x3c9ebe0a15c9bebc, + 0x431d67c49c100d4c, 0x4cc5d4becb3e42b6, 0x597f299cfc657e2a, 0x5fcb6fab3ad6faec, 0x6c44198c4a475817}; + + size_t len = 0; + for(int i = 0; input[i]!='\0'; i++) len++; + + size_t blen = len*8; + int ulen = 0; + + size_t l = len * 8; + size_t k2 = (896 - ( (l + 1) % 1024 )) % 1024; + + ulen = ((l + k2 + 1) / 8) + 16; + uint64_t tlen = ulen/128; + uint8_t* by = calloc(ulen, sizeof * by); + for (size_t i = 0; i < len; i++) + by[i] = input[i]; + by[len] = 0x80; + + //this part is very lame + __uint128_t bigL = l; + endian_swap128(&bigL); + memcpy(&by[ulen - sizeof(__uint128_t)], &bigL, sizeof(__uint128_t)); + + uint64_t *msg = ((uint64_t*)&by[0]); + for (int i = 0; i < tlen * 16; i++) + endian_swap64(msg++); + + for(int z = 0; z < (int)tlen; z++){ + uint64_t* M = ((uint64_t*)(by)); + uint64_t W[80]; + + //i dont really understand this 0->16 part + uint64_t *m = &M[(z * 16)]; + for (int i = 0; i < 16; ++i){ + W[i] = *m; + ++m; + } + + for (int i = 16; i != 80; i++){ + W[i] = (i_rr64(W[i - 2],19) ^ i_rr64(W[i - 2], 61) ^ (W[i - 2] >> 6)) + + W[i - 7] + (i_rr64(W[i - 15],1) ^ i_rr64(W[i - 15],8) ^ (W[i - 15] >> 7)) + W[i - 16]; + } + + uint64_t a = h0; + uint64_t b = h1; + uint64_t c = h2; + uint64_t d = h3; + uint64_t e = h4; + uint64_t f = h5; + uint64_t g = h6; + uint64_t h = h7; + + for(int i = 0; i != 80; i++){ + uint64_t S1 = i_rr64(e, 14) ^ i_rr64(e, 18) ^ i_rr64(e, 41); + uint64_t ch = (e & f) ^ ((~e) & g); + uint64_t temp1 = h + S1 + ch + k[i] + W[i]; + + uint64_t S0 = i_rr64(a, 28) ^ i_rr64(a, 34) ^ i_rr64(a, 39); + uint64_t maj = (a & b) ^ (a & c) ^ (b & c); + uint64_t temp2 = S0 + maj; + + h = g; + g = f; + f = e; + e = d + temp1; + d = c; + c = b; + b = a; + a = temp1 + temp2; + } + + h0 += a; + h1 += b; + h2 += c; + h3 += d; + h4 += e; + h5 += f; + h6 += g; + h7 += h; + + } + out_stream[0] = h0; + out_stream[1] = h1; + out_stream[2] = h2; + out_stream[3] = h3; + out_stream[4] = h4; + out_stream[5] = h5; + out_stream[6] = h6; + out_stream[7] = h7; + free(by); + return; +} + +struct iv sha_iv_gen(int i){ + struct iv oh = {.h0 = sha512_iv.h0 ^ 0xa5a5a5a5a5a5a5a5, .h1 = sha512_iv.h1 ^ 0xa5a5a5a5a5a5a5a5, .h2 = sha512_iv.h2 ^ 0xa5a5a5a5a5a5a5a5, + .h3 = sha512_iv.h3 ^ 0xa5a5a5a5a5a5a5a5, .h4 = sha512_iv.h4 ^ 0xa5a5a5a5a5a5a5a5, .h5 = sha512_iv.h5 ^ 0xa5a5a5a5a5a5a5a5, + .h6 = sha512_iv.h6 ^ 0xa5a5a5a5a5a5a5a5, .h7 = sha512_iv.h7 ^ 0xa5a5a5a5a5a5a5a5}; + + uint64_t nh[8] = {0}; + uint8_t in[12]; + sprintf((char*)in, "SHA-512/%i",i); + sha512_gen(nh, in, oh); + return (struct iv){.h0 = nh[0], .h1 = nh[1], .h2 = nh[2], .h3 = nh[3], .h4 = nh[4], .h5 = nh[5], .h6 = nh[6], .h7 = nh[7]}; +} + +void sha2_512_t(uint8_t* out, uint8_t* in, int t){ + if(t%8!=0) return; + uint64_t out_stream[8] = {0}; + sha512_gen(out_stream, in, sha_iv_gen(t)); + for(int i = 0; i != 8; i++) sprintf((char*)out, "%s%016lx", out, out_stream[i]); + out[t/4] = '\0'; +} + +void sha2_512(uint8_t* out, uint8_t* in){ + uint64_t out_stream[8] = {0}; + sha512_gen(out_stream, in, sha512_iv); + for(int i = 0; i != 8; i++) sprintf((char*)out, "%s%016lx", out, out_stream[i]); +} + +void sha2_384(uint8_t* out, uint8_t* in){ + uint64_t out_stream[8] = {0}; + sha512_gen(out_stream, in, sha384_iv); + for(int i = 0; i != 6; i++) sprintf((char*)out, "%s%016lx", out, out_stream[i]); +} + +int l_sha512(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[512] = {0}; + + sha2_512((uint8_t*)digest, a); + lua_pushstring(L, digest); + return 1; +} + +int l_sha384(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + + char digest[384] = {0}; + + sha2_384((uint8_t*)digest, a); + lua_pushstring(L, digest); + return 1; +} + +int l_sha512_t(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + uint64_t t = luaL_checkinteger(L, 2); + + char digest[512] = {0}; + + sha2_512_t((uint8_t*)digest, a, t); + lua_pushstring(L, digest); + return 1; +} diff --git a/src/hash/sha2-256.h b/src/hash/sha2-256.h new file mode 100644 index 0000000..d794dec --- /dev/null +++ b/src/hash/sha2-256.h @@ -0,0 +1,5 @@ +#include "../lua.h" + +int l_sha512(lua_State*); +int l_sha384(lua_State*); +int l_sha512_t(lua_State*); diff --git a/src/hash/spookyhash.c b/src/hash/spookyhash.c new file mode 100644 index 0000000..7e27d26 --- /dev/null +++ b/src/hash/spookyhash.c @@ -0,0 +1,335 @@ +#include "../i_util.h" +#include "../crypto.h" +#include +#include + +static const int sc_numVars = 12; +static const uint64_t sc_const = 0xdeadbeefdeadbeefLL; +static const size_t sc_blockSize = sc_numVars*8; +static const size_t sc_bufSize = 2*sc_blockSize; + +enum spooky_version { + v1, v2 +}; + +uint64_t i_rot64(uint64_t x, int k){ + return (x << k) | (x >> (64 - k)); +} + +void short_mix(uint64_t* h0, uint64_t* h1, uint64_t* h2, uint64_t* h3){ + *h2 = i_rot64(*h2,50); *h2 += *h3; *h0 ^= *h2; + *h3 = i_rot64(*h3,52); *h3 += *h0; *h1 ^= *h3; + *h0 = i_rot64(*h0,30); *h0 += *h1; *h2 ^= *h0; + *h1 = i_rot64(*h1,41); *h1 += *h2; *h3 ^= *h1; + *h2 = i_rot64(*h2,54); *h2 += *h3; *h0 ^= *h2; + *h3 = i_rot64(*h3,48); *h3 += *h0; *h1 ^= *h3; + *h0 = i_rot64(*h0,38); *h0 += *h1; *h2 ^= *h0; + *h1 = i_rot64(*h1,37); *h1 += *h2; *h3 ^= *h1; + *h2 = i_rot64(*h2,62); *h2 += *h3; *h0 ^= *h2; + *h3 = i_rot64(*h3,34); *h3 += *h0; *h1 ^= *h3; + *h0 = i_rot64(*h0,5); *h0 += *h1; *h2 ^= *h0; + *h1 = i_rot64(*h1,36); *h1 += *h2; *h3 ^= *h1; +} + +void short_end(uint64_t* h0, uint64_t* h1, uint64_t* h2, uint64_t* h3){ + *h3 ^= *h2; *h2 = i_rot64(*h2,15); *h3 += *h2; + *h0 ^= *h3; *h3 = i_rot64(*h3,52); *h0 += *h3; + *h1 ^= *h0; *h0 = i_rot64(*h0,26); *h1 += *h0; + *h2 ^= *h1; *h1 = i_rot64(*h1,51); *h2 += *h1; + *h3 ^= *h2; *h2 = i_rot64(*h2,28); *h3 += *h2; + *h0 ^= *h3; *h3 = i_rot64(*h3,9); *h0 += *h3; + *h1 ^= *h0; *h0 = i_rot64(*h0,47); *h1 += *h0; + *h2 ^= *h1; *h1 = i_rot64(*h1,54); *h2 += *h1; + *h3 ^= *h2; *h2 = i_rot64(*h2,32); *h3 += *h2; + *h0 ^= *h3; *h3 = i_rot64(*h3,25); *h0 += *h3; + *h1 ^= *h0; *h0 = i_rot64(*h0,63); *h1 += *h0; +} +void spooky_short(uint8_t* in, size_t len, uint64_t* hash1, uint64_t* hash2, enum spooky_version v){ + uint64_t buffer[2*sc_numVars]; + union { + const uint8_t *p8; + uint32_t *p32; + uint64_t *p64; + size_t i; + } u; + + u.p8 = (const uint8_t*)in; + + size_t remainder = len%32; + uint64_t a=*hash1; + uint64_t b=*hash2; + uint64_t c=sc_const; + uint64_t d=sc_const; + + if(len > 12){ + const uint64_t *end = u.p64 + (len/32)*4; + + for(; u.p64 < end; u.p64 += 4){ + c += u.p64[0]; + d += u.p64[1]; + short_mix(&a,&b,&c,&d); + a += u.p64[2]; + b += u.p64[3]; + } + + if(remainder >= 16){ + c += u.p64[0]; + d += u.p64[1]; + short_mix(&a,&b,&c,&d); + u.p64 += 2; + remainder -= 16; + } + } + + d = (((uint64_t)len) << 56) + (d * (v == v2)); + switch(remainder){ + case 15: + d += ((uint64_t)u.p8[14]) << 48; + case 14: + d += ((uint64_t)u.p8[13]) << 40; + case 13: + d += ((uint64_t)u.p8[12]) << 32; + case 12: + d += u.p32[2]; + c += u.p64[0]; + break; + case 11: + d += ((uint64_t)u.p8[10]) << 16; + case 10: + d += ((uint64_t)u.p8[9]) << 8; + case 9: + d += (uint64_t)u.p8[8]; + case 8: + c += u.p64[0]; + break; + case 7: + c += ((uint64_t)u.p8[6]) << 48; + case 6: + c += ((uint64_t)u.p8[5]) << 40; + case 5: + c += ((uint64_t)u.p8[4]) << 32; + case 4: + c += u.p32[0]; + break; + case 3: + c += ((uint64_t)u.p8[2]) << 16; + case 2: + c += ((uint64_t)u.p8[1]) << 8; + case 1: + c += (uint64_t)u.p8[0]; + break; + case 0: + c += sc_const; + d += sc_const; + } + short_end(&a,&b,&c,&d); + *hash1 = a; + *hash2 = b; +} + +void mix(const uint64_t *data, + uint64_t* s0, uint64_t* s1, uint64_t* s2, uint64_t* s3, + uint64_t* s4, uint64_t* s5, uint64_t* s6, uint64_t* s7, + uint64_t* s8, uint64_t* s9, uint64_t* s10,uint64_t* s11){ + *s0 += data[0]; *s2 ^= *s10; *s11 ^= *s0; *s0 = i_rot64(*s0,11); *s11 += *s1; + *s1 += data[1]; *s3 ^= *s11; *s0 ^= *s1; *s1 = i_rot64(*s1,32); *s0 += *s2; + *s2 += data[2]; *s4 ^= *s0; *s1 ^= *s2; *s2 = i_rot64(*s2,43); *s1 += *s3; + *s3 += data[3]; *s5 ^= *s1; *s2 ^= *s3; *s3 = i_rot64(*s3,31); *s2 += *s4; + *s4 += data[4]; *s6 ^= *s2; *s3 ^= *s4; *s4 = i_rot64(*s4,17); *s3 += *s5; + *s5 += data[5]; *s7 ^= *s3; *s4 ^= *s5; *s5 = i_rot64(*s5,28); *s4 += *s6; + *s6 += data[6]; *s8 ^= *s4; *s5 ^= *s6; *s6 = i_rot64(*s6,39); *s5 += *s7; + *s7 += data[7]; *s9 ^= *s5; *s6 ^= *s7; *s7 = i_rot64(*s7,57); *s6 += *s8; + *s8 += data[8]; *s10 ^= *s6; *s7 ^= *s8; *s8 = i_rot64(*s8,55); *s7 += *s9; + *s9 += data[9]; *s11 ^= *s7; *s8 ^= *s9; *s9 = i_rot64(*s9,54); *s8 += *s10; + *s10 += data[10]; *s0 ^= *s8; *s9 ^= *s10; *s10 = i_rot64(*s10,22); *s9 += *s11; + *s11 += data[11]; *s1 ^= *s9; *s10 ^= *s11; *s11 = i_rot64(*s11,46); *s10 += *s0; +} + +void end_partial( + uint64_t* h0, uint64_t* h1, uint64_t* h2, uint64_t* h3, + uint64_t* h4, uint64_t* h5, uint64_t* h6, uint64_t* h7, + uint64_t* h8, uint64_t* h9, uint64_t* h10,uint64_t* h11) + { + *h11+= *h1; *h2 ^= *h11; *h1 = i_rot64(*h1,44); + *h0 += *h2; *h3 ^= *h0; *h2 = i_rot64(*h2,15); + *h1 += *h3; *h4 ^= *h1; *h3 = i_rot64(*h3,34); + *h2 += *h4; *h5 ^= *h2; *h4 = i_rot64(*h4,21); + *h3 += *h5; *h6 ^= *h3; *h5 = i_rot64(*h5,38); + *h4 += *h6; *h7 ^= *h4; *h6 = i_rot64(*h6,33); + *h5 += *h7; *h8 ^= *h5; *h7 = i_rot64(*h7,10); + *h6 += *h8; *h9 ^= *h6; *h8 = i_rot64(*h8,13); + *h7 += *h9; *h10^= *h7; *h9 = i_rot64(*h9,38); + *h8 += *h10; *h11^= *h8; *h10= i_rot64(*h10,53); + *h9 += *h11; *h0 ^= *h9; *h11= i_rot64(*h11,42); + *h10+= *h0; *h1 ^= *h10; *h0 = i_rot64(*h0,54); +} + +void end_f(uint64_t* h0, uint64_t* h1, uint64_t* h2, uint64_t* h3, + uint64_t* h4, uint64_t* h5, uint64_t* h6, uint64_t* h7, + uint64_t* h8, uint64_t* h9, uint64_t* h10,uint64_t* h11){ + end_partial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); + end_partial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); + end_partial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); +} + +#define allow_unali 1 +void spookyhash128(uint8_t* in, size_t len, uint64_t* hash1, uint64_t* hash2, enum spooky_version v){ + if(len < sc_bufSize){ + spooky_short(in, len, hash1, hash2,v); + return; + } + + uint64_t h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11; + uint64_t buf[sc_numVars]; + uint64_t *end; + union + { + const uint8_t *p8; + uint64_t *p64; + size_t i; + } u; + size_t remainder; + + h0=h3=h6=h9 = *hash1; + h1=h4=h7=h10 = *hash2; + h2=h5=h8=h11 = sc_const; + + u.p8 = (const uint8_t *)in; + end = u.p64 + (len/sc_blockSize)*sc_numVars; + + if(allow_unali || ((u.i & 0x7) == 0)){ + for(; u.p64 < end;){ + mix(u.p64, &h0,&h1,&h2,&h3,&h4,&h5,&h6,&h7,&h8,&h9,&h10,&h11); + u.p64 += sc_numVars; + } + } else { + //do this + + } + + remainder = (len - ((const uint8_t*)end - (const uint8_t*)in)); + memcpy(buf, end, remainder); + memset(((uint8_t*)buf)+remainder, 0, sc_blockSize - remainder); + ((uint8_t*)buf)[sc_blockSize - 1] = remainder; + + mix(buf, &h0,&h1,&h2,&h3,&h4,&h5,&h6,&h7,&h8,&h9,&h10,&h11); + end_f(&h0,&h1,&h2,&h3,&h4,&h5,&h6,&h7,&h8,&h9,&h10,&h11); + *hash1 = h0; + *hash2 = h1; + +} + +uint64_t spookyhash64(uint8_t *message, size_t length, uint64_t seed, enum spooky_version v){ + uint64_t hash1 = seed; + spookyhash128(message, length, &hash1, &seed, v); + return hash1; +} +uint32_t spookyhash32(uint8_t *message, size_t length, uint32_t seed, enum spooky_version v){ + uint64_t hash1 = seed, hash2 = seed; + spookyhash128(message, length, &hash1, &hash2, v); + return (uint32_t)hash1; +} + +int l_spookyhash128_v1(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + int argv = lua_gettop(L); + uint64_t b = 0, c = 0; + + if(argv > 1){ + b = luaL_checkinteger(L, 2); + c = luaL_checkinteger(L, 3); + } + char digest[128] = {0}; + //uint64_t b = 0; + //uint64_t c = 0; + spookyhash128(a, 4, &b, &c, v1); + + sprintf(digest, "%016lx%016lx", b, c); + lua_pushstring(L, digest); + return 1; +} + +int l_spookyhash128_v2(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + int argv = lua_gettop(L); + uint64_t b = 0, c = 0; + + if(argv > 1){ + b = luaL_checkinteger(L, 2); + c = luaL_checkinteger(L, 3); + } + char digest[128] = {0}; + //uint64_t b = 0; + //uint64_t c = 0; + spookyhash128(a, 4, &b, &c, v2); + + sprintf(digest, "%016lx%016lx", b, c); + lua_pushstring(L, digest); + return 1; +} + +int l_spookyhash64_v1(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + int argv = lua_gettop(L); + uint64_t seed = 0; + if(argv > 1) seed = luaL_checkinteger(L, 2); + + char digest[64] = {0}; + + sprintf(digest, "%08lx", spookyhash64(a, len, seed, v1)); + lua_pushstring(L, digest); + return 1; +} + +int l_spookyhash64_v2(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + int argv = lua_gettop(L); + uint64_t seed = 0; + if(argv > 1) seed = luaL_checkinteger(L, 2); + + char digest[64] = {0}; + + sprintf(digest, "%08lx", spookyhash64(a, len, seed, v2)); + lua_pushstring(L, digest); + return 1; +} + +int l_spookyhash32_v1(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + int argv = lua_gettop(L); + uint32_t seed = 0; + if(argv > 1) seed = luaL_checkinteger(L, 2); + + char digest[32] = {0}; + + sprintf(digest, "%04x", spookyhash32(a, len, seed, v1)); + lua_pushstring(L, digest); + return 1; +} + +int l_spookyhash32_v2(lua_State* L){ + size_t len = 0; + uint8_t* a = (uint8_t*)luaL_checklstring(L, 1, &len); + int argv = lua_gettop(L); + uint32_t seed = 0; + if(argv > 1) seed = luaL_checkinteger(L, 2); + + char digest[32] = {0}; + + sprintf(digest, "%04x", spookyhash32(a, len, seed, v2)); + lua_pushstring(L, digest); + return 1; +} +/* +int __main(){ + uint64_t a = 0; + uint64_t b = 0; + spookyhash128("meow",4,&a,&b,v2); + printf("%llx %llx %x",a,spookyhash64("meow",4,0,v2),spookyhash32("meow",4,0,v2)); + return 0; +}*/ diff --git a/src/hash/spookyhash.h b/src/hash/spookyhash.h new file mode 100644 index 0000000..5bcecf6 --- /dev/null +++ b/src/hash/spookyhash.h @@ -0,0 +1,8 @@ +#include "../lua.h" + +int l_spookyhash128_v1(lua_State*); +int l_spookyhash128_v2(lua_State*); +int l_spookyhash64_v1(lua_State*); +int l_spookyhash64_v2(lua_State*); +int l_spookyhash32_v1(lua_State*); +int l_spookyhash32_v2(lua_State*); diff --git a/tests/hash.lua b/tests/hash.lua index dd6d5b1..e26802c 100644 --- a/tests/hash.lua +++ b/tests/hash.lua @@ -3,7 +3,9 @@ require "llib" function test(name,b,exp) local hash = llib.crypto[name](b) if not (hash == exp) then - print(name.." not working, got "..hash) + print(name.." not working, got "..hash.." wanted "..exp) + else + --print(name.." was correct, "..hash) end end @@ -26,5 +28,29 @@ test("sysvchecksum","meow","1b8") test("xor8","meow","48") test("xxh32","meow","6ba6f6f0") test("xxh64","meow","bc11093a30a6315f") - - +test("buzhash8","meow","57") +test("buzhash16","meow","0255") +test("cityhash32","meow","c41a03e9") +test("cityhash64","meow","e99b592ae1ff868b") +test("cityhash128","meow","d73f2b9c5501a6524097c5d815f2152") +test("djb2","meow","17c9a913d") +test("farmhash32","meow","c41a03e9"); +test("farmhash64","meow","e99b592ae1ff868b") +--maybe test fasthash, metrohash, sha512_t and murmur blehh +test("fnv_0","meow","b0850402171532ac") +test("fnv_1","meow","c60a427ebfe83be5") +test("fnv_a","meow","42faffa2e30e025d") +test("oaat","meow","8532510") +test("loselose","meow","000001b8") +test("pjw","meow","00073c67") +test("sdbm","meow","006d50f201921b00") +test("sha512","meow","e88348269bad036160f0d9558b7c5de68163b50e1a6ce46e85ee64692eba074529a4a2b48db4d5c36496e845001e13e6d07c585eacd564defcbf719ec9033e17"); +test("sha384","meow","f0bb848a382b5ed5e2f49a46252f6b738c933dc20bb29dc4a5d312e310b395c4fa07f30a8a7380b4a5d367445e0ea8cb") +test("fasthash64","meow","7b9e494cf11ee113") +test("fasthash32","meow","758097c7") +test("metrohash64_v1", "meow", "7435945e80261ed1") +test("metrohash64_v2","meow","f951647d250e36f0") +test("metrohash128_v1","meow","bfd8835cbcc06d2be6fc2c8e5ecbcc26") +test("metrohash128_v2","meow","6d8634ccf529269297704cba8bf8707a") +test("murmur1_32","meow","743df82f") +test("murmur2_32","meow","05d01b88") -- cgit v1.2.3