Commit ef5618fcd5
Changed files (5)
tools
lib/std/hash/crc/impl.zig
@@ -1,11 +1,5 @@
// There is a generic CRC implementation "Crc()" which can be paramterized via
-// the Algorithm struct for a plethora of uses, along with two implementations
-// of CRC32 implemented with the following key characteristics:
-//
-// - Crc32WithPoly uses 8Kb of tables but is ~10x faster than the small method.
-//
-// - Crc32SmallWithPoly uses only 64 bytes of memory but is slower. Be aware that this is
-// still moderately fast just slow relative to the slicing approach.
+// the Algorithm struct for a plethora of uses.
//
// The primary interface for all of the standard CRC algorithms is the
// generated file "crc.zig", which uses the implementation code here to define
@@ -108,134 +102,11 @@ pub fn Crc(comptime W: type, comptime algorithm: Algorithm(W)) type {
}
pub const Polynomial = enum(u32) {
- IEEE = 0xedb88320,
- Castagnoli = 0x82f63b78,
- Koopman = 0xeb31d82e,
+ IEEE = @compileError("use Crc with algorithm .Crc32IsoHdlc"),
+ Castagnoli = @compileError("use Crc with algorithm .Crc32Iscsi"),
+ Koopman = @compileError("use Crc with algorithm .Crc32Koopman"),
_,
};
-// slicing-by-8 crc32 implementation.
-pub fn Crc32WithPoly(comptime poly: Polynomial) type {
- return struct {
- const Self = @This();
- const lookup_tables = block: {
- @setEvalBranchQuota(20000);
- var tables: [8][256]u32 = undefined;
-
- for (&tables[0], 0..) |*e, i| {
- var crc = @as(u32, @intCast(i));
- var j: usize = 0;
- while (j < 8) : (j += 1) {
- if (crc & 1 == 1) {
- crc = (crc >> 1) ^ @intFromEnum(poly);
- } else {
- crc = (crc >> 1);
- }
- }
- e.* = crc;
- }
-
- var i: usize = 0;
- while (i < 256) : (i += 1) {
- var crc = tables[0][i];
- var j: usize = 1;
- while (j < 8) : (j += 1) {
- const index: u8 = @truncate(crc);
- crc = tables[0][index] ^ (crc >> 8);
- tables[j][i] = crc;
- }
- }
-
- break :block tables;
- };
-
- crc: u32,
-
- pub fn init() Self {
- return Self{ .crc = 0xffffffff };
- }
-
- pub fn update(self: *Self, input: []const u8) void {
- var i: usize = 0;
- while (i + 8 <= input.len) : (i += 8) {
- const p = input[i..][0..8];
-
- // Unrolling this way gives ~50Mb/s increase
- self.crc ^= std.mem.readInt(u32, p[0..4], .little);
-
- self.crc =
- lookup_tables[0][p[7]] ^
- lookup_tables[1][p[6]] ^
- lookup_tables[2][p[5]] ^
- lookup_tables[3][p[4]] ^
- lookup_tables[4][@as(u8, @truncate(self.crc >> 24))] ^
- lookup_tables[5][@as(u8, @truncate(self.crc >> 16))] ^
- lookup_tables[6][@as(u8, @truncate(self.crc >> 8))] ^
- lookup_tables[7][@as(u8, @truncate(self.crc >> 0))];
- }
-
- while (i < input.len) : (i += 1) {
- const index = @as(u8, @truncate(self.crc)) ^ input[i];
- self.crc = (self.crc >> 8) ^ lookup_tables[0][index];
- }
- }
-
- pub fn final(self: *Self) u32 {
- return ~self.crc;
- }
-
- pub fn hash(input: []const u8) u32 {
- var c = Self.init();
- c.update(input);
- return c.final();
- }
- };
-}
-
-// half-byte lookup table implementation.
-pub fn Crc32SmallWithPoly(comptime poly: Polynomial) type {
- return struct {
- const Self = @This();
- const lookup_table = block: {
- var table: [16]u32 = undefined;
-
- for (&table, 0..) |*e, i| {
- var crc = @as(u32, @intCast(i * 16));
- var j: usize = 0;
- while (j < 8) : (j += 1) {
- if (crc & 1 == 1) {
- crc = (crc >> 1) ^ @intFromEnum(poly);
- } else {
- crc = (crc >> 1);
- }
- }
- e.* = crc;
- }
-
- break :block table;
- };
-
- crc: u32,
-
- pub fn init() Self {
- return Self{ .crc = 0xffffffff };
- }
-
- pub fn update(self: *Self, input: []const u8) void {
- for (input) |b| {
- self.crc = lookup_table[@as(u4, @truncate(self.crc ^ (b >> 0)))] ^ (self.crc >> 4);
- self.crc = lookup_table[@as(u4, @truncate(self.crc ^ (b >> 4)))] ^ (self.crc >> 4);
- }
- }
-
- pub fn final(self: *Self) u32 {
- return ~self.crc;
- }
-
- pub fn hash(input: []const u8) u32 {
- var c = Self.init();
- c.update(input);
- return c.final();
- }
- };
-}
+pub const Crc32WithPoly = @compileError("use Crc instead");
+pub const Crc32SmallWithPoly = @compileError("use Crc instead");
lib/std/hash/crc/test.zig
@@ -5,22 +5,25 @@ const testing = std.testing;
const verify = @import("../verify.zig");
const crc = @import("../crc.zig");
-test "crc32 ieee" {
- inline for ([2]type{ crc.Crc32WithPoly(.IEEE), crc.Crc32SmallWithPoly(.IEEE) }) |ieee| {
- try testing.expect(ieee.hash("") == 0x00000000);
- try testing.expect(ieee.hash("a") == 0xe8b7be43);
- try testing.expect(ieee.hash("abc") == 0x352441c2);
- try verify.iterativeApi(ieee);
- }
+test "crc32 ieee regression" {
+ const crc32 = crc.Crc32IsoHdlc;
+ try testing.expectEqual(crc32.hash(""), 0x00000000);
+ try testing.expectEqual(crc32.hash("a"), 0xe8b7be43);
+ try testing.expectEqual(crc32.hash("abc"), 0x352441c2);
}
-test "crc32 castagnoli" {
- inline for ([2]type{ crc.Crc32WithPoly(.Castagnoli), crc.Crc32SmallWithPoly(.Castagnoli) }) |casta| {
- try testing.expect(casta.hash("") == 0x00000000);
- try testing.expect(casta.hash("a") == 0xc1d04330);
- try testing.expect(casta.hash("abc") == 0x364b3fb7);
- try verify.iterativeApi(casta);
- }
+test "crc32 castagnoli regression" {
+ const crc32 = crc.Crc32Iscsi;
+ try testing.expectEqual(crc32.hash(""), 0x00000000);
+ try testing.expectEqual(crc32.hash("a"), 0xc1d04330);
+ try testing.expectEqual(crc32.hash("abc"), 0x364b3fb7);
+}
+
+test "crc32 koopman regression" {
+ const crc32 = crc.Crc32Koopman;
+ try testing.expectEqual(crc32.hash(""), 0x00000000);
+ try testing.expectEqual(crc32.hash("a"), 0x0da2aa8a);
+ try testing.expectEqual(crc32.hash("abc"), 0xba2322ac);
}
test "CRC-3/GSM" {
@@ -1134,6 +1137,17 @@ test "CRC-32/JAMCRC" {
try testing.expectEqual(@as(u32, 0x340bc6d9), c.final());
}
+test "CRC-32/KOOPMAN" {
+ const Crc32Koopman = crc.Crc32Koopman;
+
+ try testing.expectEqual(@as(u32, 0x2d3dd0ae), Crc32Koopman.hash("123456789"));
+
+ var c = Crc32Koopman.init();
+ c.update("1234");
+ c.update("56789");
+ try testing.expectEqual(@as(u32, 0x2d3dd0ae), c.final());
+}
+
test "CRC-32/MEF" {
const Crc32Mef = crc.Crc32Mef;
lib/std/hash/crc.zig
@@ -7,8 +7,7 @@ pub const Polynomial = impl.Polynomial;
pub const Crc32WithPoly = impl.Crc32WithPoly;
pub const Crc32SmallWithPoly = impl.Crc32SmallWithPoly;
-// IEEE is by far the most common CRC and so is aliased by default.
-pub const Crc32 = Crc32WithPoly(.IEEE);
+pub const Crc32 = Crc32IsoHdlc;
test {
_ = @import("crc/test.zig");
@@ -822,6 +821,14 @@ pub const Crc32Jamcrc = Crc(u32, .{
.xor_output = 0x00000000,
});
+pub const Crc32Koopman = Crc(u32, .{
+ .polynomial = 0x741b8cd7,
+ .initial = 0xffffffff,
+ .reflect_input = true,
+ .reflect_output = true,
+ .xor_output = 0xffffffff,
+});
+
pub const Crc32Mef = Crc(u32, .{
.polynomial = 0x741b8cd7,
.initial = 0xffffffff,
tools/crc/catalog.txt
@@ -100,6 +100,7 @@ width=32 poly=0x04c11db7 init=0x00000000 refin=false refout=false xorout=0x
width=32 poly=0x1edc6f41 init=0xffffffff refin=true refout=true xorout=0xffffffff check=0xe3069283 residue=0xb798b438 name="CRC-32/ISCSI"
width=32 poly=0x04c11db7 init=0xffffffff refin=true refout=true xorout=0xffffffff check=0xcbf43926 residue=0xdebb20e3 name="CRC-32/ISO-HDLC"
width=32 poly=0x04c11db7 init=0xffffffff refin=true refout=true xorout=0x00000000 check=0x340bc6d9 residue=0x00000000 name="CRC-32/JAMCRC"
+width=32 poly=0x741b8cd7 init=0xffffffff refin=true refout=true xorout=0xffffffff check=0x2d3dd0ae residue=0x00000000 name="CRC-32/KOOPMAN"
width=32 poly=0x741b8cd7 init=0xffffffff refin=true refout=true xorout=0x00000000 check=0xd2c22f51 residue=0x00000000 name="CRC-32/MEF"
width=32 poly=0x04c11db7 init=0xffffffff refin=false refout=false xorout=0x00000000 check=0x0376e6e7 residue=0x00000000 name="CRC-32/MPEG-2"
width=32 poly=0x000000af init=0x00000000 refin=false refout=false xorout=0x00000000 check=0xbd0be338 residue=0x00000000 name="CRC-32/XFER"
tools/update_crc_catalog.zig
@@ -48,8 +48,7 @@ pub fn main() anyerror!void {
\\pub const Crc32WithPoly = impl.Crc32WithPoly;
\\pub const Crc32SmallWithPoly = impl.Crc32SmallWithPoly;
\\
- \\// IEEE is by far the most common CRC and so is aliased by default.
- \\pub const Crc32 = Crc32WithPoly(.IEEE);
+ \\pub const Crc32 = Crc32IsoHdlc;
\\
\\test {
\\ _ = @import("crc/test.zig");
@@ -72,22 +71,25 @@ pub fn main() anyerror!void {
\\const verify = @import("../verify.zig");
\\const crc = @import("../crc.zig");
\\
- \\test "crc32 ieee" {
- \\ inline for ([2]type{ crc.Crc32WithPoly(.IEEE), crc.Crc32SmallWithPoly(.IEEE) }) |ieee| {
- \\ try testing.expect(ieee.hash("") == 0x00000000);
- \\ try testing.expect(ieee.hash("a") == 0xe8b7be43);
- \\ try testing.expect(ieee.hash("abc") == 0x352441c2);
- \\ try verify.iterativeApi(ieee);
- \\ }
+ \\test "crc32 ieee regression" {
+ \\ const crc32 = crc.Crc32IsoHdlc;
+ \\ try testing.expectEqual(crc32.hash(""), 0x00000000);
+ \\ try testing.expectEqual(crc32.hash("a"), 0xe8b7be43);
+ \\ try testing.expectEqual(crc32.hash("abc"), 0x352441c2);
\\}
\\
- \\test "crc32 castagnoli" {
- \\ inline for ([2]type{ crc.Crc32WithPoly(.Castagnoli), crc.Crc32SmallWithPoly(.Castagnoli) }) |casta| {
- \\ try testing.expect(casta.hash("") == 0x00000000);
- \\ try testing.expect(casta.hash("a") == 0xc1d04330);
- \\ try testing.expect(casta.hash("abc") == 0x364b3fb7);
- \\ try verify.iterativeApi(casta);
- \\ }
+ \\test "crc32 castagnoli regression" {
+ \\ const crc32 = crc.Crc32Iscsi;
+ \\ try testing.expectEqual(crc32.hash(""), 0x00000000);
+ \\ try testing.expectEqual(crc32.hash("a"), 0xc1d04330);
+ \\ try testing.expectEqual(crc32.hash("abc"), 0x364b3fb7);
+ \\}
+ \\
+ \\test "crc32 koopman regression" {
+ \\ const crc32 = crc.Koopman;
+ \\ try testing.expectEqual(crc32.hash(""), 0x00000000);
+ \\ try testing.expectEqual(crc32.hash("a"), 0x0da2aa8a);
+ \\ try testing.expectEqual(crc32.hash("abc"), 0xba2322ac);
\\}
\\
);