1//! https://tools.ietf.org/html/rfc1950#section-9
  2//! https://github.com/madler/zlib/blob/master/adler32.c
  3
  4const Adler32 = @This();
  5const std = @import("std");
  6const testing = std.testing;
  7
  8adler: u32 = 1,
  9
 10pub fn permute(state: u32, input: []const u8) u32 {
 11    const base = 65521;
 12    const nmax = 5552;
 13
 14    var s1 = state & 0xffff;
 15    var s2 = (state >> 16) & 0xffff;
 16
 17    if (input.len == 1) {
 18        s1 +%= input[0];
 19        if (s1 >= base) {
 20            s1 -= base;
 21        }
 22        s2 +%= s1;
 23        if (s2 >= base) {
 24            s2 -= base;
 25        }
 26    } else if (input.len < 16) {
 27        for (input) |b| {
 28            s1 +%= b;
 29            s2 +%= s1;
 30        }
 31        if (s1 >= base) {
 32            s1 -= base;
 33        }
 34
 35        s2 %= base;
 36    } else {
 37        const n = nmax / 16; // note: 16 | nmax
 38
 39        var i: usize = 0;
 40
 41        while (i + nmax <= input.len) {
 42            var rounds: usize = 0;
 43            while (rounds < n) : (rounds += 1) {
 44                comptime var j: usize = 0;
 45                inline while (j < 16) : (j += 1) {
 46                    s1 +%= input[i + j];
 47                    s2 +%= s1;
 48                }
 49                i += 16;
 50            }
 51
 52            s1 %= base;
 53            s2 %= base;
 54        }
 55
 56        if (i < input.len) {
 57            while (i + 16 <= input.len) : (i += 16) {
 58                comptime var j: usize = 0;
 59                inline while (j < 16) : (j += 1) {
 60                    s1 +%= input[i + j];
 61                    s2 +%= s1;
 62                }
 63            }
 64            while (i < input.len) : (i += 1) {
 65                s1 +%= input[i];
 66                s2 +%= s1;
 67            }
 68
 69            s1 %= base;
 70            s2 %= base;
 71        }
 72    }
 73
 74    return s1 | (s2 << 16);
 75}
 76
 77pub fn update(a: *Adler32, input: []const u8) void {
 78    a.adler = permute(a.adler, input);
 79}
 80
 81pub fn hash(input: []const u8) u32 {
 82    return permute(1, input);
 83}
 84
 85test "sanity" {
 86    try testing.expectEqual(@as(u32, 0x620062), hash("a"));
 87    try testing.expectEqual(@as(u32, 0xbc002ed), hash("example"));
 88}
 89
 90test "long" {
 91    const long1 = [_]u8{1} ** 1024;
 92    try testing.expectEqual(@as(u32, 0x06780401), hash(long1[0..]));
 93
 94    const long2 = [_]u8{1} ** 1025;
 95    try testing.expectEqual(@as(u32, 0x0a7a0402), hash(long2[0..]));
 96}
 97
 98test "very long" {
 99    const long = [_]u8{1} ** 5553;
100    try testing.expectEqual(@as(u32, 0x707f15b2), hash(long[0..]));
101}
102
103test "very long with variation" {
104    const long = comptime blk: {
105        @setEvalBranchQuota(7000);
106        var result: [6000]u8 = undefined;
107
108        var i: usize = 0;
109        while (i < result.len) : (i += 1) {
110            result[i] = @as(u8, @truncate(i));
111        }
112
113        break :blk result;
114    };
115
116    try testing.expectEqual(@as(u32, 0x5af38d6e), hash(long[0..]));
117}