hare

[hare] The Hare programming language
git clone https://git.torresjrjr.com/hare.git
Log | Files | Refs | README | LICENSE

fnv.ha (4917B)


      1 // SPDX-License-Identifier: MPL-2.0
      2 // (c) Hare authors <https://harelang.org>
      3 
      4 use endian;
      5 use hash;
      6 use io;
      7 use strings;
      8 
      9 def PRIME32: u32 = 16777619;
     10 def PRIME64: u64 = 1099511628211;
     11 def BASIS32: u32 = 2166136261;
     12 def BASIS64: u64 = 14695981039346656037;
     13 
     14 export type state32 = struct {
     15 	hash::hash,
     16 	v: u32,
     17 };
     18 
     19 export type state64 = struct {
     20 	hash::hash,
     21 	v: u64,
     22 };
     23 
     24 // Hashes a string, returning a 32-bit key.
     25 export fn string32(s: str) u32 = {
     26 	let hash = fnv32a();
     27 	hash::write(&hash, strings::toutf8(s));
     28 	return sum32(&hash);
     29 };
     30 
     31 // Hashes a string, returning a 64-bit key.
     32 export fn string64(s: str) u64 = {
     33 	let hash = fnv64a();
     34 	hash::write(&hash, strings::toutf8(s));
     35 	return sum64(&hash);
     36 };
     37 
     38 const fnv32_vtable: io::vtable = io::vtable {
     39 	writer = &fnv32_write,
     40 	...
     41 };
     42 
     43 // Creates a [[hash::hash]] which computes the FNV-1 32-bit hash function. This
     44 // hash does not allocate any state, so you do not need to call [[hash::close]]
     45 // when you're done with it.
     46 //
     47 // Unless you have a reason to use this, [[fnv32a]] is recommended instead.
     48 export fn fnv32() state32 = state32 {
     49 	stream = &fnv32_vtable,
     50 	sum = &fnv32_sum,
     51 	reset = &fnv32_reset,
     52 	sz = 4,
     53 	v = BASIS32,
     54 	...
     55 };
     56 
     57 const fnv32a_vtable: io::vtable = io::vtable {
     58 	writer = &fnv32a_write,
     59 	...
     60 };
     61 
     62 // Creates a [[hash::hash]] which computes the FNV-1a 32-bit hash function. This
     63 // hash does not allocate any state, so you do not need to call [[hash::close]]
     64 // when you're done with it.
     65 export fn fnv32a() state32 = state32 {
     66 	stream = &fnv32a_vtable,
     67 	sum = &fnv32_sum,
     68 	reset = &fnv32_reset,
     69 	sz = 4,
     70 	v = BASIS32,
     71 	...
     72 };
     73 
     74 const fnv64_vtable: io::vtable = io::vtable {
     75 	writer = &fnv64_write,
     76 	...
     77 };
     78 
     79 // Creates a [[hash::hash]] which computes the FNV-1 64-bit hash function. This
     80 // hash does not allocate any state, so you do not need to call [[hash::close]]
     81 // when you're done with it.
     82 //
     83 // Unless you have a reason to use this, [[fnv64a]] is recommended instead.
     84 export fn fnv64() state64 = state64 {
     85 	stream = &fnv64_vtable,
     86 	sum = &fnv64_sum,
     87 	reset = &fnv64_reset,
     88 	sz = 8,
     89 	v = BASIS64,
     90 	...
     91 };
     92 
     93 const fnv64a_vtable: io::vtable = io::vtable {
     94 	writer = &fnv64a_write,
     95 	...
     96 };
     97 
     98 // Creates a [[hash::hash]] which computes the FNV-1a 64-bit hash function. This
     99 // hash does not allocate any state, so you do not need to call [[hash::close]]
    100 // when you're done with it.
    101 export fn fnv64a() state64 = state64 {
    102 	stream = &fnv64a_vtable,
    103 	sum = &fnv64_sum,
    104 	reset = &fnv64_reset,
    105 	sz = 8,
    106 	v = BASIS64,
    107 	...
    108 };
    109 
    110 fn fnv32_write(s: *io::stream, buf: const []u8) (size | io::error) = {
    111 	let s = s: *state32;
    112 	for (let i = 0z; i < len(buf); i += 1) {
    113 		s.v *= PRIME32;
    114 		s.v ^= buf[i];
    115 	};
    116 	return len(buf);
    117 };
    118 
    119 fn fnv32a_write(s: *io::stream, buf: const []u8) (size | io::error) = {
    120 	let s = s: *state32;
    121 	for (let i = 0z; i < len(buf); i += 1) {
    122 		s.v ^= buf[i];
    123 		s.v *= PRIME32;
    124 	};
    125 	return len(buf);
    126 };
    127 
    128 fn fnv32_reset(h: *hash::hash) void = {
    129 	let h = h: *state32;
    130 	h.v = BASIS32;
    131 };
    132 
    133 fn fnv32_sum(h: *hash::hash, buf: []u8) void = {
    134 	let h = h: *state32;
    135 	endian::host.putu32(buf, h.v);
    136 };
    137 
    138 fn fnv64_write(s: *io::stream, buf: const []u8) (size | io::error) = {
    139 	let s = s: *state64;
    140 	for (let i = 0z; i < len(buf); i += 1) {
    141 		s.v *= PRIME64;
    142 		s.v ^= buf[i];
    143 	};
    144 	return len(buf);
    145 };
    146 
    147 fn fnv64a_write(s: *io::stream, buf: const []u8) (size | io::error) = {
    148 	let s = s: *state64;
    149 	for (let i = 0z; i < len(buf); i += 1) {
    150 		s.v ^= buf[i];
    151 		s.v *= PRIME64;
    152 	};
    153 	return len(buf);
    154 };
    155 
    156 fn fnv64_reset(h: *hash::hash) void = {
    157 	let h = h: *state64;
    158 	h.v = BASIS64;
    159 };
    160 
    161 fn fnv64_sum(h: *hash::hash, buf: []u8) void = {
    162 	let h = h: *state64;
    163 	endian::host.putu64(buf, h.v);
    164 };
    165 
    166 // Returns the sum of a 32-bit FNV hash.
    167 export fn sum32(h: *hash::hash) u32 = {
    168 	assert(h.reset == &fnv32_reset);
    169 	let h = h: *state32;
    170 	return h.v;
    171 };
    172 
    173 // Returns the sum of a 64-bit FNV hash.
    174 export fn sum64(h: *hash::hash) u64 = {
    175 	assert(h.reset == &fnv64_reset);
    176 	let h = h: *state64;
    177 	return h.v;
    178 };
    179 
    180 @test fn fnv32() void = {
    181 	// TODO: Expand these tests
    182 	// I am too tired
    183 	const vectors: [_](str, u32) = [
    184 		("", 2166136261),
    185 		("hello world", 1418570095),
    186 		("Hare is a cool language", 2663852071),
    187 		("'UNIX was not designed to stop its users from doing stupid things, as that would also stop them from doing clever things' - Doug Gwyn", 1203174417),
    188 		("'Life is too short to run proprietary software' - Bdale Garbee", 493463614),
    189 		("'The central enemy of reliability is complexity.' - Geer et al", 3263526736),
    190 		("'A language that doesn’t have everything is actually easier to program in than some that do.' - Dennis Ritchie", 3069348265),
    191 	];
    192 
    193 	let hash = fnv32();
    194 	let s: [4]u8 = [0...];
    195 
    196 	for (let i = 0z; i < len(vectors); i += 1) {
    197 		let vec = vectors[i];
    198 
    199 		hash::reset(&hash);
    200 		hash::write(&hash, strings::toutf8(vec.0));
    201 		hash::sum(&hash, s);
    202 
    203 		assert(endian::host.getu32(s) == vec.1);
    204 		assert(sum32(&hash) == vec.1);
    205 	};
    206 };