1// FNV1a - Fowler-Noll-Vo hash function
 2//
 3// FNV1a is a fast, non-cryptographic hash function with fairly good distribution properties.
 4//
 5// https://tools.ietf.org/html/draft-eastlake-fnv-14
 6
 7const std = @import("std");
 8const testing = std.testing;
 9
10pub const Fnv1a_32 = Fnv1a(u32, 0x01000193, 0x811c9dc5);
11pub const Fnv1a_64 = Fnv1a(u64, 0x100000001b3, 0xcbf29ce484222325);
12pub const Fnv1a_128 = Fnv1a(u128, 0x1000000000000000000013b, 0x6c62272e07bb014262b821756295c58d);
13
14fn Fnv1a(comptime T: type, comptime prime: T, comptime offset: T) type {
15    return struct {
16        const Self = @This();
17
18        value: T,
19
20        pub fn init() Self {
21            return Self{ .value = offset };
22        }
23
24        pub fn update(self: *Self, input: []const u8) void {
25            for (input) |b| {
26                self.value ^= b;
27                self.value *%= prime;
28            }
29        }
30
31        pub fn final(self: *Self) T {
32            return self.value;
33        }
34
35        pub fn hash(input: []const u8) T {
36            var c = Self.init();
37            c.update(input);
38            return c.final();
39        }
40    };
41}
42
43const verify = @import("verify.zig");
44
45test "fnv1a-32" {
46    try testing.expect(Fnv1a_32.hash("") == 0x811c9dc5);
47    try testing.expect(Fnv1a_32.hash("a") == 0xe40c292c);
48    try testing.expect(Fnv1a_32.hash("foobar") == 0xbf9cf968);
49    try verify.iterativeApi(Fnv1a_32);
50}
51
52test "fnv1a-64" {
53    try testing.expect(Fnv1a_64.hash("") == 0xcbf29ce484222325);
54    try testing.expect(Fnv1a_64.hash("a") == 0xaf63dc4c8601ec8c);
55    try testing.expect(Fnv1a_64.hash("foobar") == 0x85944171f73967e8);
56    try verify.iterativeApi(Fnv1a_64);
57}
58
59test "fnv1a-128" {
60    try testing.expect(Fnv1a_128.hash("") == 0x6c62272e07bb014262b821756295c58d);
61    try testing.expect(Fnv1a_128.hash("a") == 0xd228cb696f1a8caf78912b704e4a8964);
62    try verify.iterativeApi(Fnv1a_128);
63}