1// There is a generic CRC implementation "Crc()" which can be parameterized via
  2// the Algorithm struct for a plethora of uses.
  3//
  4// The primary interface for all of the standard CRC algorithms is the
  5// generated file "crc.zig", which uses the implementation code here to define
  6// many standard CRCs.
  7
  8const std = @import("std");
  9
 10pub fn Algorithm(comptime W: type) type {
 11    return struct {
 12        polynomial: W,
 13        initial: W,
 14        reflect_input: bool,
 15        reflect_output: bool,
 16        xor_output: W,
 17    };
 18}
 19
 20pub fn Crc(comptime W: type, comptime algorithm: Algorithm(W)) type {
 21    return struct {
 22        const Self = @This();
 23        const I = if (@bitSizeOf(W) < 8) u8 else W;
 24        const lookup_table = blk: {
 25            @setEvalBranchQuota(2500);
 26
 27            const poly = if (algorithm.reflect_input)
 28                @bitReverse(@as(I, algorithm.polynomial)) >> (@bitSizeOf(I) - @bitSizeOf(W))
 29            else
 30                @as(I, algorithm.polynomial) << (@bitSizeOf(I) - @bitSizeOf(W));
 31
 32            var table: [256]I = undefined;
 33            for (&table, 0..) |*e, i| {
 34                var crc: I = i;
 35                if (algorithm.reflect_input) {
 36                    var j: usize = 0;
 37                    while (j < 8) : (j += 1) {
 38                        crc = (crc >> 1) ^ ((crc & 1) * poly);
 39                    }
 40                } else {
 41                    crc <<= @bitSizeOf(I) - 8;
 42                    var j: usize = 0;
 43                    while (j < 8) : (j += 1) {
 44                        crc = (crc << 1) ^ (((crc >> (@bitSizeOf(I) - 1)) & 1) * poly);
 45                    }
 46                }
 47                e.* = crc;
 48            }
 49            break :blk table;
 50        };
 51
 52        crc: I,
 53
 54        pub fn init() Self {
 55            const initial = if (algorithm.reflect_input)
 56                @bitReverse(@as(I, algorithm.initial)) >> (@bitSizeOf(I) - @bitSizeOf(W))
 57            else
 58                @as(I, algorithm.initial) << (@bitSizeOf(I) - @bitSizeOf(W));
 59            return Self{ .crc = initial };
 60        }
 61
 62        inline fn tableEntry(index: I) I {
 63            return lookup_table[@as(u8, @intCast(index & 0xFF))];
 64        }
 65
 66        pub fn update(self: *Self, bytes: []const u8) void {
 67            var i: usize = 0;
 68            if (@bitSizeOf(I) <= 8) {
 69                while (i < bytes.len) : (i += 1) {
 70                    self.crc = tableEntry(self.crc ^ bytes[i]);
 71                }
 72            } else if (algorithm.reflect_input) {
 73                while (i < bytes.len) : (i += 1) {
 74                    const table_index = self.crc ^ bytes[i];
 75                    self.crc = tableEntry(table_index) ^ (self.crc >> 8);
 76                }
 77            } else {
 78                while (i < bytes.len) : (i += 1) {
 79                    const table_index = (self.crc >> (@bitSizeOf(I) - 8)) ^ bytes[i];
 80                    self.crc = tableEntry(table_index) ^ (self.crc << 8);
 81                }
 82            }
 83        }
 84
 85        pub fn final(self: Self) W {
 86            var c = self.crc;
 87            if (algorithm.reflect_input != algorithm.reflect_output) {
 88                c = @bitReverse(c);
 89            }
 90            if (!algorithm.reflect_output) {
 91                c >>= @bitSizeOf(I) - @bitSizeOf(W);
 92            }
 93            return @as(W, @intCast(c ^ algorithm.xor_output));
 94        }
 95
 96        pub fn hash(bytes: []const u8) W {
 97            var c = Self.init();
 98            c.update(bytes);
 99            return c.final();
100        }
101    };
102}