mirror of
https://github.com/odin-lang/Odin.git
synced 2026-07-17 13:11:07 +00:00
842cfee0f3
This change was made in order to allow things produced with Odin and using Odin's core library, to not require the LICENSE to also be distributed alongside the binary form.
323 lines
9.2 KiB
Odin
323 lines
9.2 KiB
Odin
package xxhash
|
|
|
|
/*
|
|
An implementation of Yann Collet's [xxhash Fast Hash Algorithm](https://cyan4973.github.io/xxHash/).
|
|
Copyright 2021 Jeroen van Rijn <nom@duclavier.com>.
|
|
|
|
Made available under Odin's license, based on the original C code.
|
|
|
|
List of contributors:
|
|
Jeroen van Rijn: Initial implementation.
|
|
*/
|
|
|
|
import "base:intrinsics"
|
|
|
|
/*
|
|
32-bit hash functions
|
|
*/
|
|
XXH32_hash :: u32
|
|
xxh_u32 :: u32
|
|
XXH32_DEFAULT_SEED :: XXH32_hash(0)
|
|
|
|
XXH32_state :: struct {
|
|
total_len_32: XXH32_hash, /*!< Total length hashed, modulo 2^32 */
|
|
large_len: XXH32_hash, /*!< Whether the hash is >= 16 (handles @ref total_len_32 overflow) */
|
|
v1: XXH32_hash, /*!< First accumulator lane */
|
|
v2: XXH32_hash, /*!< Second accumulator lane */
|
|
v3: XXH32_hash, /*!< Third accumulator lane */
|
|
v4: XXH32_hash, /*!< Fourth accumulator lane */
|
|
mem32: [4]XXH32_hash, /*!< Internal buffer for partial reads. Treated as unsigned char[16]. */
|
|
memsize: XXH32_hash, /*!< Amount of data in @ref mem32 */
|
|
reserved: XXH32_hash, /*!< Reserved field. Do not read or write to it, it may be removed. */
|
|
}
|
|
|
|
XXH32_canonical :: struct {
|
|
digest: [4]u8,
|
|
}
|
|
|
|
XXH_PRIME32_1 :: 0x9E3779B1 /*!< 0b10011110001101110111100110110001 */
|
|
XXH_PRIME32_2 :: 0x85EBCA77 /*!< 0b10000101111010111100101001110111 */
|
|
XXH_PRIME32_3 :: 0xC2B2AE3D /*!< 0b11000010101100101010111000111101 */
|
|
XXH_PRIME32_4 :: 0x27D4EB2F /*!< 0b00100111110101001110101100101111 */
|
|
XXH_PRIME32_5 :: 0x165667B1 /*!< 0b00010110010101100110011110110001 */
|
|
|
|
@(optimization_mode="favor_size")
|
|
XXH32_round :: #force_inline proc(seed, input: XXH32_hash) -> (res: XXH32_hash) {
|
|
seed := seed
|
|
|
|
seed += input * XXH_PRIME32_2
|
|
seed = XXH_rotl32(seed, 13)
|
|
seed *= XXH_PRIME32_1
|
|
return seed
|
|
}
|
|
|
|
/*
|
|
Mix all bits
|
|
*/
|
|
@(optimization_mode="favor_size")
|
|
XXH32_avalanche :: #force_inline proc(h32: u32) -> (res: u32) {
|
|
h32 := h32
|
|
|
|
h32 ~= h32 >> 15
|
|
h32 *= XXH_PRIME32_2
|
|
h32 ~= h32 >> 13
|
|
h32 *= XXH_PRIME32_3
|
|
h32 ~= h32 >> 16
|
|
return h32
|
|
}
|
|
|
|
@(optimization_mode="favor_size")
|
|
XXH32_finalize :: #force_inline proc(h32: u32, buf: []u8, alignment: Alignment) -> (res: u32) {
|
|
process_1 :: #force_inline proc(h32: u32, buf: []u8) -> (h32_res: u32, buf_res: []u8) {
|
|
#no_bounds_check b := u32(buf[0])
|
|
h32_res = h32 + b * XXH_PRIME32_5
|
|
h32_res = XXH_rotl32(h32_res, 11) * XXH_PRIME32_1
|
|
#no_bounds_check return h32_res, buf[1:]
|
|
}
|
|
|
|
process_4 :: #force_inline proc(h32: u32, buf: []u8, alignment: Alignment) -> (h32_res: u32, buf_res: []u8) {
|
|
b := XXH32_read32(buf, alignment)
|
|
h32_res = h32 + b * XXH_PRIME32_3
|
|
h32_res = XXH_rotl32(h32_res, 17) * XXH_PRIME32_4
|
|
#no_bounds_check return h32_res, buf[4:]
|
|
}
|
|
|
|
buf := buf
|
|
h32 := h32
|
|
|
|
switch len(buf) & 15 {
|
|
case 12:
|
|
h32, buf = process_4(h32, buf, alignment)
|
|
fallthrough
|
|
case 8:
|
|
h32, buf = process_4(h32, buf, alignment)
|
|
fallthrough
|
|
case 4:
|
|
h32, _ = process_4(h32, buf, alignment)
|
|
return XXH32_avalanche(h32)
|
|
|
|
case 13:
|
|
h32, buf = process_4(h32, buf, alignment)
|
|
fallthrough
|
|
case 9:
|
|
h32, buf = process_4(h32, buf, alignment)
|
|
fallthrough
|
|
case 5:
|
|
h32, buf = process_4(h32, buf, alignment)
|
|
h32, buf = process_1(h32, buf)
|
|
return XXH32_avalanche(h32)
|
|
|
|
case 14:
|
|
h32, buf = process_4(h32, buf, alignment)
|
|
fallthrough
|
|
case 10:
|
|
h32, buf = process_4(h32, buf, alignment)
|
|
fallthrough
|
|
case 6:
|
|
h32, buf = process_4(h32, buf, alignment)
|
|
h32, buf = process_1(h32, buf)
|
|
h32, buf = process_1(h32, buf)
|
|
return XXH32_avalanche(h32)
|
|
|
|
case 15:
|
|
h32, buf = process_4(h32, buf, alignment)
|
|
fallthrough
|
|
case 11:
|
|
h32, buf = process_4(h32, buf, alignment)
|
|
fallthrough
|
|
case 7:
|
|
h32, buf = process_4(h32, buf, alignment)
|
|
fallthrough
|
|
|
|
case 3:
|
|
h32, buf = process_1(h32, buf)
|
|
fallthrough
|
|
case 2:
|
|
h32, buf = process_1(h32, buf)
|
|
fallthrough
|
|
case 1:
|
|
h32, buf = process_1(h32, buf)
|
|
fallthrough
|
|
case 0:
|
|
return XXH32_avalanche(h32)
|
|
}
|
|
unreachable()
|
|
}
|
|
|
|
@(optimization_mode="favor_size")
|
|
XXH32_endian_align :: #force_inline proc(input: []u8, seed := XXH32_DEFAULT_SEED, alignment: Alignment) -> (res: XXH32_hash) {
|
|
buf := input
|
|
length := len(input)
|
|
|
|
if length >= 16 {
|
|
v1 := seed + XXH_PRIME32_1 + XXH_PRIME32_2
|
|
v2 := seed + XXH_PRIME32_2
|
|
v3 := seed + 0
|
|
v4 := seed - XXH_PRIME32_1
|
|
|
|
for len(buf) >= 16 {
|
|
#no_bounds_check v1 = XXH32_round(v1, XXH32_read32(buf, alignment)); buf = buf[4:]
|
|
#no_bounds_check v2 = XXH32_round(v2, XXH32_read32(buf, alignment)); buf = buf[4:]
|
|
#no_bounds_check v3 = XXH32_round(v3, XXH32_read32(buf, alignment)); buf = buf[4:]
|
|
#no_bounds_check v4 = XXH32_round(v4, XXH32_read32(buf, alignment)); buf = buf[4:]
|
|
}
|
|
|
|
res = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18)
|
|
} else {
|
|
res = seed + XXH_PRIME32_5
|
|
}
|
|
|
|
res += u32(length)
|
|
return XXH32_finalize(res, buf, alignment)
|
|
}
|
|
|
|
XXH32 :: proc(input: []u8, seed := XXH32_DEFAULT_SEED) -> (digest: XXH32_hash) {
|
|
when false {
|
|
/*
|
|
Simple version, good for code maintenance, but unfortunately slow for small inputs.
|
|
*/
|
|
state: XXH32_state
|
|
XXH32_reset_state(&state, seed)
|
|
XXH32_update(&state, input)
|
|
return XXH32_digest(&state)
|
|
} else {
|
|
when XXH_FORCE_ALIGN_CHECK {
|
|
if uintptr(raw_data(input)) & uintptr(3) == 0 {
|
|
/*
|
|
Input is 4-bytes aligned, leverage the speed benefit.
|
|
*/
|
|
return XXH32_endian_align(input, seed, .Aligned)
|
|
}
|
|
}
|
|
return XXH32_endian_align(input, seed, .Unaligned)
|
|
}
|
|
}
|
|
|
|
/*
|
|
****** Hash streaming ******
|
|
*/
|
|
XXH32_create_state :: proc(allocator := context.allocator) -> (res: ^XXH32_state, err: Error) {
|
|
state := new(XXH32_state, allocator)
|
|
XXH32_reset_state(state)
|
|
return state, .None if state != nil else .Error
|
|
}
|
|
|
|
XXH32_destroy_state :: proc(state: ^XXH32_state, allocator := context.allocator) -> (err: Error) {
|
|
free(state, allocator)
|
|
return .None
|
|
}
|
|
|
|
XXH32_copy_state :: proc(dest, src: ^XXH32_state) {
|
|
assert(dest != nil && src != nil)
|
|
mem_copy(dest, src, size_of(XXH32_state))
|
|
}
|
|
|
|
XXH32_reset_state :: proc(state_ptr: ^XXH32_state, seed := XXH32_DEFAULT_SEED) -> (err: Error) {
|
|
state := XXH32_state{}
|
|
|
|
state.v1 = seed + XXH_PRIME32_1 + XXH_PRIME32_2
|
|
state.v2 = seed + XXH_PRIME32_2
|
|
state.v3 = seed + 0
|
|
state.v4 = seed - XXH_PRIME32_1
|
|
/*
|
|
Do not write into reserved, planned to be removed in a future version.
|
|
*/
|
|
mem_copy(state_ptr, &state, size_of(state) - size_of(state.reserved))
|
|
return .None
|
|
}
|
|
|
|
XXH32_update :: proc(state: ^XXH32_state, input: []u8) -> (err: Error) {
|
|
|
|
buf := input
|
|
length := len(buf)
|
|
|
|
state.total_len_32 += XXH32_hash(length)
|
|
state.large_len |= 1 if length >= 16 || state.total_len_32 >= 16 else 0
|
|
|
|
if state.memsize + u32(length) < 16 { /* Fill in tmp buffer */
|
|
ptr := uintptr(raw_data(state.mem32[:])) + uintptr(state.memsize)
|
|
mem_copy(rawptr(ptr), raw_data(input), int(length))
|
|
state.memsize += XXH32_hash(length)
|
|
return .None
|
|
}
|
|
|
|
if state.memsize > 0 {/* Some data left from previous update */
|
|
ptr := uintptr(raw_data(state.mem32[:])) + uintptr(state.memsize)
|
|
mem_copy(rawptr(ptr), raw_data(input), int(16 - state.memsize))
|
|
{
|
|
#no_bounds_check state.v1 = XXH32_round(state.v1, state.mem32[0])
|
|
#no_bounds_check state.v2 = XXH32_round(state.v2, state.mem32[1])
|
|
#no_bounds_check state.v3 = XXH32_round(state.v3, state.mem32[2])
|
|
#no_bounds_check state.v4 = XXH32_round(state.v4, state.mem32[3])
|
|
}
|
|
buf = buf[16 - state.memsize:]
|
|
state.memsize = 0
|
|
}
|
|
|
|
if len(buf) >= 16 {
|
|
v1 := state.v1
|
|
v2 := state.v2
|
|
v3 := state.v3
|
|
v4 := state.v4
|
|
|
|
for len(buf) >= 16 {
|
|
#no_bounds_check v1 = XXH32_round(v1, XXH32_read32(buf, .Unaligned)); buf = buf[4:]
|
|
#no_bounds_check v2 = XXH32_round(v2, XXH32_read32(buf, .Unaligned)); buf = buf[4:]
|
|
#no_bounds_check v3 = XXH32_round(v3, XXH32_read32(buf, .Unaligned)); buf = buf[4:]
|
|
#no_bounds_check v4 = XXH32_round(v4, XXH32_read32(buf, .Unaligned)); buf = buf[4:]
|
|
}
|
|
|
|
state.v1 = v1
|
|
state.v2 = v2
|
|
state.v3 = v3
|
|
state.v4 = v4
|
|
}
|
|
|
|
length = len(buf)
|
|
if length > 0 {
|
|
mem_copy(raw_data(state.mem32[:]), raw_data(buf[:]), int(length))
|
|
state.memsize = u32(length)
|
|
}
|
|
return .None
|
|
}
|
|
|
|
XXH32_digest :: proc(state: ^XXH32_state) -> (res: XXH32_hash) {
|
|
if state.large_len > 0 {
|
|
res = XXH_rotl32(state.v1, 1) + XXH_rotl32(state.v2, 7) + XXH_rotl32(state.v3, 12) + XXH_rotl32(state.v4, 18)
|
|
} else {
|
|
res = state.v3 /* == seed */ + XXH_PRIME32_5
|
|
}
|
|
|
|
res += state.total_len_32
|
|
|
|
buf := (^[16]u8)(&state.mem32)^
|
|
alignment: Alignment = .Aligned if uintptr(&state.mem32) & 15 == 0 else .Unaligned
|
|
return XXH32_finalize(res, buf[:state.memsize], alignment)
|
|
}
|
|
|
|
/*
|
|
****** Canonical representation ******
|
|
|
|
The default return values from XXH functions are unsigned 32 and 64 bit integers.
|
|
|
|
The canonical representation uses big endian convention,
|
|
the same convention as human-readable numbers (large digits first).
|
|
|
|
This way, hash values can be written into a file or buffer, remaining
|
|
comparable across different systems.
|
|
|
|
The following functions allow transformation of hash values to and from their
|
|
canonical format.
|
|
*/
|
|
XXH32_canonical_from_hash :: proc(hash: XXH32_hash) -> (canonical: XXH32_canonical) {
|
|
#assert(size_of(XXH32_canonical) == size_of(XXH32_hash))
|
|
h := u32be(hash)
|
|
mem_copy(&canonical, &h, size_of(canonical))
|
|
return
|
|
}
|
|
|
|
XXH32_hash_from_canonical :: proc(canonical: ^XXH32_canonical) -> (hash: XXH32_hash) {
|
|
h := (^u32be)(&canonical.digest)^
|
|
return XXH32_hash(h)
|
|
}
|