// SPDX-License-Identifier: MPL-2.0 // (c) Hare authors use endian; use hash; use io; use strings; // The size, in bytes, of a CRC-64 checksum. export def SZ: size = 8; // ECMA polynomial for CRC-64. Used in ECMA-182 and xz-utils. export def ECMA: u64 = 0xC96C5795D7870F42; // ISO polynomial for CRC-64. Used in ISO 3309 (high-level data link controls). export def ISO: u64 = 0xD800000000000000; // Table of memoized values for each byte with the ECMA polynomial. export const ecma_table: [256]u64 = [ 0x0000000000000000, 0xB32E4CBE03A75F6F, 0xF4843657A840A05B, 0x47AA7AE9ABE7FF34, 0x7BD0C384FF8F5E33, 0xC8FE8F3AFC28015C, 0x8F54F5D357CFFE68, 0x3C7AB96D5468A107, 0xF7A18709FF1EBC66, 0x448FCBB7FCB9E309, 0x0325B15E575E1C3D, 0xB00BFDE054F94352, 0x8C71448D0091E255, 0x3F5F08330336BD3A, 0x78F572DAA8D1420E, 0xCBDB3E64AB761D61, 0x7D9BA13851336649, 0xCEB5ED8652943926, 0x891F976FF973C612, 0x3A31DBD1FAD4997D, 0x064B62BCAEBC387A, 0xB5652E02AD1B6715, 0xF2CF54EB06FC9821, 0x41E11855055BC74E, 0x8A3A2631AE2DDA2F, 0x39146A8FAD8A8540, 0x7EBE1066066D7A74, 0xCD905CD805CA251B, 0xF1EAE5B551A2841C, 0x42C4A90B5205DB73, 0x056ED3E2F9E22447, 0xB6409F5CFA457B28, 0xFB374270A266CC92, 0x48190ECEA1C193FD, 0x0FB374270A266CC9, 0xBC9D3899098133A6, 0x80E781F45DE992A1, 0x33C9CD4A5E4ECDCE, 0x7463B7A3F5A932FA, 0xC74DFB1DF60E6D95, 0x0C96C5795D7870F4, 0xBFB889C75EDF2F9B, 0xF812F32EF538D0AF, 0x4B3CBF90F69F8FC0, 0x774606FDA2F72EC7, 0xC4684A43A15071A8, 0x83C230AA0AB78E9C, 0x30EC7C140910D1F3, 0x86ACE348F355AADB, 0x3582AFF6F0F2F5B4, 0x7228D51F5B150A80, 0xC10699A158B255EF, 0xFD7C20CC0CDAF4E8, 0x4E526C720F7DAB87, 0x09F8169BA49A54B3, 0xBAD65A25A73D0BDC, 0x710D64410C4B16BD, 0xC22328FF0FEC49D2, 0x85895216A40BB6E6, 0x36A71EA8A7ACE989, 0x0ADDA7C5F3C4488E, 0xB9F3EB7BF06317E1, 0xFE5991925B84E8D5, 0x4D77DD2C5823B7BA, 0x64B62BCAEBC387A1, 0xD7986774E864D8CE, 0x90321D9D438327FA, 0x231C512340247895, 0x1F66E84E144CD992, 0xAC48A4F017EB86FD, 0xEBE2DE19BC0C79C9, 0x58CC92A7BFAB26A6, 0x9317ACC314DD3BC7, 0x2039E07D177A64A8, 0x67939A94BC9D9B9C, 0xD4BDD62ABF3AC4F3, 0xE8C76F47EB5265F4, 0x5BE923F9E8F53A9B, 0x1C4359104312C5AF, 0xAF6D15AE40B59AC0, 0x192D8AF2BAF0E1E8, 0xAA03C64CB957BE87, 0xEDA9BCA512B041B3, 0x5E87F01B11171EDC, 0x62FD4976457FBFDB, 0xD1D305C846D8E0B4, 0x96797F21ED3F1F80, 0x2557339FEE9840EF, 0xEE8C0DFB45EE5D8E, 0x5DA24145464902E1, 0x1A083BACEDAEFDD5, 0xA9267712EE09A2BA, 0x955CCE7FBA6103BD, 0x267282C1B9C65CD2, 0x61D8F8281221A3E6, 0xD2F6B4961186FC89, 0x9F8169BA49A54B33, 0x2CAF25044A02145C, 0x6B055FEDE1E5EB68, 0xD82B1353E242B407, 0xE451AA3EB62A1500, 0x577FE680B58D4A6F, 0x10D59C691E6AB55B, 0xA3FBD0D71DCDEA34, 0x6820EEB3B6BBF755, 0xDB0EA20DB51CA83A, 0x9CA4D8E41EFB570E, 0x2F8A945A1D5C0861, 0x13F02D374934A966, 0xA0DE61894A93F609, 0xE7741B60E174093D, 0x545A57DEE2D35652, 0xE21AC88218962D7A, 0x5134843C1B317215, 0x169EFED5B0D68D21, 0xA5B0B26BB371D24E, 0x99CA0B06E7197349, 0x2AE447B8E4BE2C26, 0x6D4E3D514F59D312, 0xDE6071EF4CFE8C7D, 0x15BB4F8BE788911C, 0xA6950335E42FCE73, 0xE13F79DC4FC83147, 0x521135624C6F6E28, 0x6E6B8C0F1807CF2F, 0xDD45C0B11BA09040, 0x9AEFBA58B0476F74, 0x29C1F6E6B3E0301B, 0xC96C5795D7870F42, 0x7A421B2BD420502D, 0x3DE861C27FC7AF19, 0x8EC62D7C7C60F076, 0xB2BC941128085171, 0x0192D8AF2BAF0E1E, 0x4638A2468048F12A, 0xF516EEF883EFAE45, 0x3ECDD09C2899B324, 0x8DE39C222B3EEC4B, 0xCA49E6CB80D9137F, 0x7967AA75837E4C10, 0x451D1318D716ED17, 0xF6335FA6D4B1B278, 0xB199254F7F564D4C, 0x02B769F17CF11223, 0xB4F7F6AD86B4690B, 0x07D9BA1385133664, 0x4073C0FA2EF4C950, 0xF35D8C442D53963F, 0xCF273529793B3738, 0x7C0979977A9C6857, 0x3BA3037ED17B9763, 0x888D4FC0D2DCC80C, 0x435671A479AAD56D, 0xF0783D1A7A0D8A02, 0xB7D247F3D1EA7536, 0x04FC0B4DD24D2A59, 0x3886B22086258B5E, 0x8BA8FE9E8582D431, 0xCC0284772E652B05, 0x7F2CC8C92DC2746A, 0x325B15E575E1C3D0, 0x8175595B76469CBF, 0xC6DF23B2DDA1638B, 0x75F16F0CDE063CE4, 0x498BD6618A6E9DE3, 0xFAA59ADF89C9C28C, 0xBD0FE036222E3DB8, 0x0E21AC88218962D7, 0xC5FA92EC8AFF7FB6, 0x76D4DE52895820D9, 0x317EA4BB22BFDFED, 0x8250E80521188082, 0xBE2A516875702185, 0x0D041DD676D77EEA, 0x4AAE673FDD3081DE, 0xF9802B81DE97DEB1, 0x4FC0B4DD24D2A599, 0xFCEEF8632775FAF6, 0xBB44828A8C9205C2, 0x086ACE348F355AAD, 0x34107759DB5DFBAA, 0x873E3BE7D8FAA4C5, 0xC094410E731D5BF1, 0x73BA0DB070BA049E, 0xB86133D4DBCC19FF, 0x0B4F7F6AD86B4690, 0x4CE50583738CB9A4, 0xFFCB493D702BE6CB, 0xC3B1F050244347CC, 0x709FBCEE27E418A3, 0x3735C6078C03E797, 0x841B8AB98FA4B8F8, 0xADDA7C5F3C4488E3, 0x1EF430E13FE3D78C, 0x595E4A08940428B8, 0xEA7006B697A377D7, 0xD60ABFDBC3CBD6D0, 0x6524F365C06C89BF, 0x228E898C6B8B768B, 0x91A0C532682C29E4, 0x5A7BFB56C35A3485, 0xE955B7E8C0FD6BEA, 0xAEFFCD016B1A94DE, 0x1DD181BF68BDCBB1, 0x21AB38D23CD56AB6, 0x9285746C3F7235D9, 0xD52F0E859495CAED, 0x6601423B97329582, 0xD041DD676D77EEAA, 0x636F91D96ED0B1C5, 0x24C5EB30C5374EF1, 0x97EBA78EC690119E, 0xAB911EE392F8B099, 0x18BF525D915FEFF6, 0x5F1528B43AB810C2, 0xEC3B640A391F4FAD, 0x27E05A6E926952CC, 0x94CE16D091CE0DA3, 0xD3646C393A29F297, 0x604A2087398EADF8, 0x5C3099EA6DE60CFF, 0xEF1ED5546E415390, 0xA8B4AFBDC5A6ACA4, 0x1B9AE303C601F3CB, 0x56ED3E2F9E224471, 0xE5C372919D851B1E, 0xA26908783662E42A, 0x114744C635C5BB45, 0x2D3DFDAB61AD1A42, 0x9E13B115620A452D, 0xD9B9CBFCC9EDBA19, 0x6A978742CA4AE576, 0xA14CB926613CF817, 0x1262F598629BA778, 0x55C88F71C97C584C, 0xE6E6C3CFCADB0723, 0xDA9C7AA29EB3A624, 0x69B2361C9D14F94B, 0x2E184CF536F3067F, 0x9D36004B35545910, 0x2B769F17CF112238, 0x9858D3A9CCB67D57, 0xDFF2A94067518263, 0x6CDCE5FE64F6DD0C, 0x50A65C93309E7C0B, 0xE388102D33392364, 0xA4226AC498DEDC50, 0x170C267A9B79833F, 0xDCD7181E300F9E5E, 0x6FF954A033A8C131, 0x28532E49984F3E05, 0x9B7D62F79BE8616A, 0xA707DB9ACF80C06D, 0x14299724CC279F02, 0x5383EDCD67C06036, 0xE0ADA17364673F59, ]; // Table of memoized values for each byte with the ISO polynomial. export const iso_table: [256]u64 = [ 0x0000000000000000, 0x01B0000000000000, 0x0360000000000000, 0x02D0000000000000, 0x06C0000000000000, 0x0770000000000000, 0x05A0000000000000, 0x0410000000000000, 0x0D80000000000000, 0x0C30000000000000, 0x0EE0000000000000, 0x0F50000000000000, 0x0B40000000000000, 0x0AF0000000000000, 0x0820000000000000, 0x0990000000000000, 0x1B00000000000000, 0x1AB0000000000000, 0x1860000000000000, 0x19D0000000000000, 0x1DC0000000000000, 0x1C70000000000000, 0x1EA0000000000000, 0x1F10000000000000, 0x1680000000000000, 0x1730000000000000, 0x15E0000000000000, 0x1450000000000000, 0x1040000000000000, 0x11F0000000000000, 0x1320000000000000, 0x1290000000000000, 0x3600000000000000, 0x37B0000000000000, 0x3560000000000000, 0x34D0000000000000, 0x30C0000000000000, 0x3170000000000000, 0x33A0000000000000, 0x3210000000000000, 0x3B80000000000000, 0x3A30000000000000, 0x38E0000000000000, 0x3950000000000000, 0x3D40000000000000, 0x3CF0000000000000, 0x3E20000000000000, 0x3F90000000000000, 0x2D00000000000000, 0x2CB0000000000000, 0x2E60000000000000, 0x2FD0000000000000, 0x2BC0000000000000, 0x2A70000000000000, 0x28A0000000000000, 0x2910000000000000, 0x2080000000000000, 0x2130000000000000, 0x23E0000000000000, 0x2250000000000000, 0x2640000000000000, 0x27F0000000000000, 0x2520000000000000, 0x2490000000000000, 0x6C00000000000000, 0x6DB0000000000000, 0x6F60000000000000, 0x6ED0000000000000, 0x6AC0000000000000, 0x6B70000000000000, 0x69A0000000000000, 0x6810000000000000, 0x6180000000000000, 0x6030000000000000, 0x62E0000000000000, 0x6350000000000000, 0x6740000000000000, 0x66F0000000000000, 0x6420000000000000, 0x6590000000000000, 0x7700000000000000, 0x76B0000000000000, 0x7460000000000000, 0x75D0000000000000, 0x71C0000000000000, 0x7070000000000000, 0x72A0000000000000, 0x7310000000000000, 0x7A80000000000000, 0x7B30000000000000, 0x79E0000000000000, 0x7850000000000000, 0x7C40000000000000, 0x7DF0000000000000, 0x7F20000000000000, 0x7E90000000000000, 0x5A00000000000000, 0x5BB0000000000000, 0x5960000000000000, 0x58D0000000000000, 0x5CC0000000000000, 0x5D70000000000000, 0x5FA0000000000000, 0x5E10000000000000, 0x5780000000000000, 0x5630000000000000, 0x54E0000000000000, 0x5550000000000000, 0x5140000000000000, 0x50F0000000000000, 0x5220000000000000, 0x5390000000000000, 0x4100000000000000, 0x40B0000000000000, 0x4260000000000000, 0x43D0000000000000, 0x47C0000000000000, 0x4670000000000000, 0x44A0000000000000, 0x4510000000000000, 0x4C80000000000000, 0x4D30000000000000, 0x4FE0000000000000, 0x4E50000000000000, 0x4A40000000000000, 0x4BF0000000000000, 0x4920000000000000, 0x4890000000000000, 0xD800000000000000, 0xD9B0000000000000, 0xDB60000000000000, 0xDAD0000000000000, 0xDEC0000000000000, 0xDF70000000000000, 0xDDA0000000000000, 0xDC10000000000000, 0xD580000000000000, 0xD430000000000000, 0xD6E0000000000000, 0xD750000000000000, 0xD340000000000000, 0xD2F0000000000000, 0xD020000000000000, 0xD190000000000000, 0xC300000000000000, 0xC2B0000000000000, 0xC060000000000000, 0xC1D0000000000000, 0xC5C0000000000000, 0xC470000000000000, 0xC6A0000000000000, 0xC710000000000000, 0xCE80000000000000, 0xCF30000000000000, 0xCDE0000000000000, 0xCC50000000000000, 0xC840000000000000, 0xC9F0000000000000, 0xCB20000000000000, 0xCA90000000000000, 0xEE00000000000000, 0xEFB0000000000000, 0xED60000000000000, 0xECD0000000000000, 0xE8C0000000000000, 0xE970000000000000, 0xEBA0000000000000, 0xEA10000000000000, 0xE380000000000000, 0xE230000000000000, 0xE0E0000000000000, 0xE150000000000000, 0xE540000000000000, 0xE4F0000000000000, 0xE620000000000000, 0xE790000000000000, 0xF500000000000000, 0xF4B0000000000000, 0xF660000000000000, 0xF7D0000000000000, 0xF3C0000000000000, 0xF270000000000000, 0xF0A0000000000000, 0xF110000000000000, 0xF880000000000000, 0xF930000000000000, 0xFBE0000000000000, 0xFA50000000000000, 0xFE40000000000000, 0xFFF0000000000000, 0xFD20000000000000, 0xFC90000000000000, 0xB400000000000000, 0xB5B0000000000000, 0xB760000000000000, 0xB6D0000000000000, 0xB2C0000000000000, 0xB370000000000000, 0xB1A0000000000000, 0xB010000000000000, 0xB980000000000000, 0xB830000000000000, 0xBAE0000000000000, 0xBB50000000000000, 0xBF40000000000000, 0xBEF0000000000000, 0xBC20000000000000, 0xBD90000000000000, 0xAF00000000000000, 0xAEB0000000000000, 0xAC60000000000000, 0xADD0000000000000, 0xA9C0000000000000, 0xA870000000000000, 0xAAA0000000000000, 0xAB10000000000000, 0xA280000000000000, 0xA330000000000000, 0xA1E0000000000000, 0xA050000000000000, 0xA440000000000000, 0xA5F0000000000000, 0xA720000000000000, 0xA690000000000000, 0x8200000000000000, 0x83B0000000000000, 0x8160000000000000, 0x80D0000000000000, 0x84C0000000000000, 0x8570000000000000, 0x87A0000000000000, 0x8610000000000000, 0x8F80000000000000, 0x8E30000000000000, 0x8CE0000000000000, 0x8D50000000000000, 0x8940000000000000, 0x88F0000000000000, 0x8A20000000000000, 0x8B90000000000000, 0x9900000000000000, 0x98B0000000000000, 0x9A60000000000000, 0x9BD0000000000000, 0x9FC0000000000000, 0x9E70000000000000, 0x9CA0000000000000, 0x9D10000000000000, 0x9480000000000000, 0x9530000000000000, 0x97E0000000000000, 0x9650000000000000, 0x9240000000000000, 0x93F0000000000000, 0x9120000000000000, 0x9090000000000000, ]; // Populate a user-provided buffer with the memoized values for a custom // polynomial. // // The user-provided polynomial must be in the reversed form. export fn memoize(polynomial: u64, buf: *[256]u64) void = { for (let i = 0z; i < 256; i += 1) { let value = i: u64; for (let z = 0z; z < 8; z += 1) { value = if (value & 0x1 == 1) { yield (value >> 1) ^ polynomial; } else { yield value >> 1; }; }; buf[i] = value; }; }; export type state = struct { hash::hash, table: *[256]u64, cval: u64, }; const crc64_vtable: io::vtable = io::vtable { writer = &write, ... }; // Creates a [[hash::hash]] which computes the CRC-64 algorithm. This hash // function does not allocate any state, so you do not need to call // [[hash::close]] when you are done with it. // // It takes a table of memoized values for a given polynomail (for example, // [[iso_table]] or [[ecma_table]]); a table for a custom polynomial, populated // by [[memoize]] function, may also be used. export fn crc64(table: *[256]u64) state = state { stream = &crc64_vtable, sum = &sum, reset = &reset, sz = SZ, table = table, cval = ~0u64, ... }; fn write(s: *io::stream, buf: const []u8) (size | io::error) = { let s = s: *state; for (let i = 0z; i < len(buf); i += 1) { let rightbits = s.cval & 0xFF; s.cval = s.table[rightbits ^ buf[i]] ^ (s.cval >> 8); }; return len(buf); }; fn reset(h: *hash::hash) void = { let h = h: *state; h.cval = ~0u64; }; fn sum(h: *hash::hash, buf: []u8) void = { let h = h: *state; endian::host.putu64(buf, ~h.cval); }; // Returns the 64-bit computed CRC. export fn sum64(h: *hash::hash) u64 = { assert(h.reset == &reset); let h = h: *state; return ~h.cval; }; @test fn crc64() void = { const vectors: [](str, u64, u64) = [ ("", 0, 0), ("Man can believe the impossible, but can never believe the improbable. -- Oscar Wilde", 0x17F71EF3BB851DC7, 0xD0E8ED57865D6AC6), ("We learn from history that we do not learn from history. -- Georg Hegel", 0xAA3C335BB49ABE9D, 0x5FD192CC516BBEC3), ("The final delusion is the belief that one has lost all delusions. -- Maurice Chapelain", 0x7DFC4F7CE9552D23, 0xF71B429C925D99AE), ]; let crc_ecma = crc64(&ecma_table); let crc_iso = crc64(&iso_table); let buf: [SZ]u8 = [0...]; for (let i = 0z; i < len(vectors); i += 1) { let vec = vectors[i]; hash::reset(&crc_ecma); hash::write(&crc_ecma, strings::toutf8(vec.0)); hash::sum(&crc_ecma, buf); assert(endian::host.getu64(buf) == vec.1); assert(sum64(&crc_ecma) == vec.1); hash::reset(&crc_iso); hash::write(&crc_iso, strings::toutf8(vec.0)); hash::sum(&crc_iso, buf); assert(endian::host.getu64(buf) == vec.2); assert(sum64(&crc_iso) == vec.2); }; };