crc64.ha (13794B)
1 // SPDX-License-Identifier: MPL-2.0 2 // (c) Hare authors <https://harelang.org> 3 4 use endian; 5 use hash; 6 use io; 7 use strings; 8 9 // The size, in bytes, of a CRC-64 checksum. 10 export def SZ: size = 8; 11 12 // ECMA polynomial for CRC-64. Used in ECMA-182 and xz-utils. 13 export def ECMA: u64 = 0xC96C5795D7870F42; 14 15 // ISO polynomial for CRC-64. Used in ISO 3309 (high-level data link controls). 16 export def ISO: u64 = 0xD800000000000000; 17 18 // Table of memoized values for each byte with the ECMA polynomial. 19 export const ecma_table: [256]u64 = [ 20 0x0000000000000000, 0xB32E4CBE03A75F6F, 0xF4843657A840A05B, 21 0x47AA7AE9ABE7FF34, 0x7BD0C384FF8F5E33, 0xC8FE8F3AFC28015C, 22 0x8F54F5D357CFFE68, 0x3C7AB96D5468A107, 0xF7A18709FF1EBC66, 23 0x448FCBB7FCB9E309, 0x0325B15E575E1C3D, 0xB00BFDE054F94352, 24 0x8C71448D0091E255, 0x3F5F08330336BD3A, 0x78F572DAA8D1420E, 25 0xCBDB3E64AB761D61, 0x7D9BA13851336649, 0xCEB5ED8652943926, 26 0x891F976FF973C612, 0x3A31DBD1FAD4997D, 0x064B62BCAEBC387A, 27 0xB5652E02AD1B6715, 0xF2CF54EB06FC9821, 0x41E11855055BC74E, 28 0x8A3A2631AE2DDA2F, 0x39146A8FAD8A8540, 0x7EBE1066066D7A74, 29 0xCD905CD805CA251B, 0xF1EAE5B551A2841C, 0x42C4A90B5205DB73, 30 0x056ED3E2F9E22447, 0xB6409F5CFA457B28, 0xFB374270A266CC92, 31 0x48190ECEA1C193FD, 0x0FB374270A266CC9, 0xBC9D3899098133A6, 32 0x80E781F45DE992A1, 0x33C9CD4A5E4ECDCE, 0x7463B7A3F5A932FA, 33 0xC74DFB1DF60E6D95, 0x0C96C5795D7870F4, 0xBFB889C75EDF2F9B, 34 0xF812F32EF538D0AF, 0x4B3CBF90F69F8FC0, 0x774606FDA2F72EC7, 35 0xC4684A43A15071A8, 0x83C230AA0AB78E9C, 0x30EC7C140910D1F3, 36 0x86ACE348F355AADB, 0x3582AFF6F0F2F5B4, 0x7228D51F5B150A80, 37 0xC10699A158B255EF, 0xFD7C20CC0CDAF4E8, 0x4E526C720F7DAB87, 38 0x09F8169BA49A54B3, 0xBAD65A25A73D0BDC, 0x710D64410C4B16BD, 39 0xC22328FF0FEC49D2, 0x85895216A40BB6E6, 0x36A71EA8A7ACE989, 40 0x0ADDA7C5F3C4488E, 0xB9F3EB7BF06317E1, 0xFE5991925B84E8D5, 41 0x4D77DD2C5823B7BA, 0x64B62BCAEBC387A1, 0xD7986774E864D8CE, 42 0x90321D9D438327FA, 0x231C512340247895, 0x1F66E84E144CD992, 43 0xAC48A4F017EB86FD, 0xEBE2DE19BC0C79C9, 0x58CC92A7BFAB26A6, 44 0x9317ACC314DD3BC7, 0x2039E07D177A64A8, 0x67939A94BC9D9B9C, 45 0xD4BDD62ABF3AC4F3, 0xE8C76F47EB5265F4, 0x5BE923F9E8F53A9B, 46 0x1C4359104312C5AF, 0xAF6D15AE40B59AC0, 0x192D8AF2BAF0E1E8, 47 0xAA03C64CB957BE87, 0xEDA9BCA512B041B3, 0x5E87F01B11171EDC, 48 0x62FD4976457FBFDB, 0xD1D305C846D8E0B4, 0x96797F21ED3F1F80, 49 0x2557339FEE9840EF, 0xEE8C0DFB45EE5D8E, 0x5DA24145464902E1, 50 0x1A083BACEDAEFDD5, 0xA9267712EE09A2BA, 0x955CCE7FBA6103BD, 51 0x267282C1B9C65CD2, 0x61D8F8281221A3E6, 0xD2F6B4961186FC89, 52 0x9F8169BA49A54B33, 0x2CAF25044A02145C, 0x6B055FEDE1E5EB68, 53 0xD82B1353E242B407, 0xE451AA3EB62A1500, 0x577FE680B58D4A6F, 54 0x10D59C691E6AB55B, 0xA3FBD0D71DCDEA34, 0x6820EEB3B6BBF755, 55 0xDB0EA20DB51CA83A, 0x9CA4D8E41EFB570E, 0x2F8A945A1D5C0861, 56 0x13F02D374934A966, 0xA0DE61894A93F609, 0xE7741B60E174093D, 57 0x545A57DEE2D35652, 0xE21AC88218962D7A, 0x5134843C1B317215, 58 0x169EFED5B0D68D21, 0xA5B0B26BB371D24E, 0x99CA0B06E7197349, 59 0x2AE447B8E4BE2C26, 0x6D4E3D514F59D312, 0xDE6071EF4CFE8C7D, 60 0x15BB4F8BE788911C, 0xA6950335E42FCE73, 0xE13F79DC4FC83147, 61 0x521135624C6F6E28, 0x6E6B8C0F1807CF2F, 0xDD45C0B11BA09040, 62 0x9AEFBA58B0476F74, 0x29C1F6E6B3E0301B, 0xC96C5795D7870F42, 63 0x7A421B2BD420502D, 0x3DE861C27FC7AF19, 0x8EC62D7C7C60F076, 64 0xB2BC941128085171, 0x0192D8AF2BAF0E1E, 0x4638A2468048F12A, 65 0xF516EEF883EFAE45, 0x3ECDD09C2899B324, 0x8DE39C222B3EEC4B, 66 0xCA49E6CB80D9137F, 0x7967AA75837E4C10, 0x451D1318D716ED17, 67 0xF6335FA6D4B1B278, 0xB199254F7F564D4C, 0x02B769F17CF11223, 68 0xB4F7F6AD86B4690B, 0x07D9BA1385133664, 0x4073C0FA2EF4C950, 69 0xF35D8C442D53963F, 0xCF273529793B3738, 0x7C0979977A9C6857, 70 0x3BA3037ED17B9763, 0x888D4FC0D2DCC80C, 0x435671A479AAD56D, 71 0xF0783D1A7A0D8A02, 0xB7D247F3D1EA7536, 0x04FC0B4DD24D2A59, 72 0x3886B22086258B5E, 0x8BA8FE9E8582D431, 0xCC0284772E652B05, 73 0x7F2CC8C92DC2746A, 0x325B15E575E1C3D0, 0x8175595B76469CBF, 74 0xC6DF23B2DDA1638B, 0x75F16F0CDE063CE4, 0x498BD6618A6E9DE3, 75 0xFAA59ADF89C9C28C, 0xBD0FE036222E3DB8, 0x0E21AC88218962D7, 76 0xC5FA92EC8AFF7FB6, 0x76D4DE52895820D9, 0x317EA4BB22BFDFED, 77 0x8250E80521188082, 0xBE2A516875702185, 0x0D041DD676D77EEA, 78 0x4AAE673FDD3081DE, 0xF9802B81DE97DEB1, 0x4FC0B4DD24D2A599, 79 0xFCEEF8632775FAF6, 0xBB44828A8C9205C2, 0x086ACE348F355AAD, 80 0x34107759DB5DFBAA, 0x873E3BE7D8FAA4C5, 0xC094410E731D5BF1, 81 0x73BA0DB070BA049E, 0xB86133D4DBCC19FF, 0x0B4F7F6AD86B4690, 82 0x4CE50583738CB9A4, 0xFFCB493D702BE6CB, 0xC3B1F050244347CC, 83 0x709FBCEE27E418A3, 0x3735C6078C03E797, 0x841B8AB98FA4B8F8, 84 0xADDA7C5F3C4488E3, 0x1EF430E13FE3D78C, 0x595E4A08940428B8, 85 0xEA7006B697A377D7, 0xD60ABFDBC3CBD6D0, 0x6524F365C06C89BF, 86 0x228E898C6B8B768B, 0x91A0C532682C29E4, 0x5A7BFB56C35A3485, 87 0xE955B7E8C0FD6BEA, 0xAEFFCD016B1A94DE, 0x1DD181BF68BDCBB1, 88 0x21AB38D23CD56AB6, 0x9285746C3F7235D9, 0xD52F0E859495CAED, 89 0x6601423B97329582, 0xD041DD676D77EEAA, 0x636F91D96ED0B1C5, 90 0x24C5EB30C5374EF1, 0x97EBA78EC690119E, 0xAB911EE392F8B099, 91 0x18BF525D915FEFF6, 0x5F1528B43AB810C2, 0xEC3B640A391F4FAD, 92 0x27E05A6E926952CC, 0x94CE16D091CE0DA3, 0xD3646C393A29F297, 93 0x604A2087398EADF8, 0x5C3099EA6DE60CFF, 0xEF1ED5546E415390, 94 0xA8B4AFBDC5A6ACA4, 0x1B9AE303C601F3CB, 0x56ED3E2F9E224471, 95 0xE5C372919D851B1E, 0xA26908783662E42A, 0x114744C635C5BB45, 96 0x2D3DFDAB61AD1A42, 0x9E13B115620A452D, 0xD9B9CBFCC9EDBA19, 97 0x6A978742CA4AE576, 0xA14CB926613CF817, 0x1262F598629BA778, 98 0x55C88F71C97C584C, 0xE6E6C3CFCADB0723, 0xDA9C7AA29EB3A624, 99 0x69B2361C9D14F94B, 0x2E184CF536F3067F, 0x9D36004B35545910, 100 0x2B769F17CF112238, 0x9858D3A9CCB67D57, 0xDFF2A94067518263, 101 0x6CDCE5FE64F6DD0C, 0x50A65C93309E7C0B, 0xE388102D33392364, 102 0xA4226AC498DEDC50, 0x170C267A9B79833F, 0xDCD7181E300F9E5E, 103 0x6FF954A033A8C131, 0x28532E49984F3E05, 0x9B7D62F79BE8616A, 104 0xA707DB9ACF80C06D, 0x14299724CC279F02, 0x5383EDCD67C06036, 105 0xE0ADA17364673F59, 106 ]; 107 108 // Table of memoized values for each byte with the ISO polynomial. 109 export const iso_table: [256]u64 = [ 110 0x0000000000000000, 0x01B0000000000000, 0x0360000000000000, 111 0x02D0000000000000, 0x06C0000000000000, 0x0770000000000000, 112 0x05A0000000000000, 0x0410000000000000, 0x0D80000000000000, 113 0x0C30000000000000, 0x0EE0000000000000, 0x0F50000000000000, 114 0x0B40000000000000, 0x0AF0000000000000, 0x0820000000000000, 115 0x0990000000000000, 0x1B00000000000000, 0x1AB0000000000000, 116 0x1860000000000000, 0x19D0000000000000, 0x1DC0000000000000, 117 0x1C70000000000000, 0x1EA0000000000000, 0x1F10000000000000, 118 0x1680000000000000, 0x1730000000000000, 0x15E0000000000000, 119 0x1450000000000000, 0x1040000000000000, 0x11F0000000000000, 120 0x1320000000000000, 0x1290000000000000, 0x3600000000000000, 121 0x37B0000000000000, 0x3560000000000000, 0x34D0000000000000, 122 0x30C0000000000000, 0x3170000000000000, 0x33A0000000000000, 123 0x3210000000000000, 0x3B80000000000000, 0x3A30000000000000, 124 0x38E0000000000000, 0x3950000000000000, 0x3D40000000000000, 125 0x3CF0000000000000, 0x3E20000000000000, 0x3F90000000000000, 126 0x2D00000000000000, 0x2CB0000000000000, 0x2E60000000000000, 127 0x2FD0000000000000, 0x2BC0000000000000, 0x2A70000000000000, 128 0x28A0000000000000, 0x2910000000000000, 0x2080000000000000, 129 0x2130000000000000, 0x23E0000000000000, 0x2250000000000000, 130 0x2640000000000000, 0x27F0000000000000, 0x2520000000000000, 131 0x2490000000000000, 0x6C00000000000000, 0x6DB0000000000000, 132 0x6F60000000000000, 0x6ED0000000000000, 0x6AC0000000000000, 133 0x6B70000000000000, 0x69A0000000000000, 0x6810000000000000, 134 0x6180000000000000, 0x6030000000000000, 0x62E0000000000000, 135 0x6350000000000000, 0x6740000000000000, 0x66F0000000000000, 136 0x6420000000000000, 0x6590000000000000, 0x7700000000000000, 137 0x76B0000000000000, 0x7460000000000000, 0x75D0000000000000, 138 0x71C0000000000000, 0x7070000000000000, 0x72A0000000000000, 139 0x7310000000000000, 0x7A80000000000000, 0x7B30000000000000, 140 0x79E0000000000000, 0x7850000000000000, 0x7C40000000000000, 141 0x7DF0000000000000, 0x7F20000000000000, 0x7E90000000000000, 142 0x5A00000000000000, 0x5BB0000000000000, 0x5960000000000000, 143 0x58D0000000000000, 0x5CC0000000000000, 0x5D70000000000000, 144 0x5FA0000000000000, 0x5E10000000000000, 0x5780000000000000, 145 0x5630000000000000, 0x54E0000000000000, 0x5550000000000000, 146 0x5140000000000000, 0x50F0000000000000, 0x5220000000000000, 147 0x5390000000000000, 0x4100000000000000, 0x40B0000000000000, 148 0x4260000000000000, 0x43D0000000000000, 0x47C0000000000000, 149 0x4670000000000000, 0x44A0000000000000, 0x4510000000000000, 150 0x4C80000000000000, 0x4D30000000000000, 0x4FE0000000000000, 151 0x4E50000000000000, 0x4A40000000000000, 0x4BF0000000000000, 152 0x4920000000000000, 0x4890000000000000, 0xD800000000000000, 153 0xD9B0000000000000, 0xDB60000000000000, 0xDAD0000000000000, 154 0xDEC0000000000000, 0xDF70000000000000, 0xDDA0000000000000, 155 0xDC10000000000000, 0xD580000000000000, 0xD430000000000000, 156 0xD6E0000000000000, 0xD750000000000000, 0xD340000000000000, 157 0xD2F0000000000000, 0xD020000000000000, 0xD190000000000000, 158 0xC300000000000000, 0xC2B0000000000000, 0xC060000000000000, 159 0xC1D0000000000000, 0xC5C0000000000000, 0xC470000000000000, 160 0xC6A0000000000000, 0xC710000000000000, 0xCE80000000000000, 161 0xCF30000000000000, 0xCDE0000000000000, 0xCC50000000000000, 162 0xC840000000000000, 0xC9F0000000000000, 0xCB20000000000000, 163 0xCA90000000000000, 0xEE00000000000000, 0xEFB0000000000000, 164 0xED60000000000000, 0xECD0000000000000, 0xE8C0000000000000, 165 0xE970000000000000, 0xEBA0000000000000, 0xEA10000000000000, 166 0xE380000000000000, 0xE230000000000000, 0xE0E0000000000000, 167 0xE150000000000000, 0xE540000000000000, 0xE4F0000000000000, 168 0xE620000000000000, 0xE790000000000000, 0xF500000000000000, 169 0xF4B0000000000000, 0xF660000000000000, 0xF7D0000000000000, 170 0xF3C0000000000000, 0xF270000000000000, 0xF0A0000000000000, 171 0xF110000000000000, 0xF880000000000000, 0xF930000000000000, 172 0xFBE0000000000000, 0xFA50000000000000, 0xFE40000000000000, 173 0xFFF0000000000000, 0xFD20000000000000, 0xFC90000000000000, 174 0xB400000000000000, 0xB5B0000000000000, 0xB760000000000000, 175 0xB6D0000000000000, 0xB2C0000000000000, 0xB370000000000000, 176 0xB1A0000000000000, 0xB010000000000000, 0xB980000000000000, 177 0xB830000000000000, 0xBAE0000000000000, 0xBB50000000000000, 178 0xBF40000000000000, 0xBEF0000000000000, 0xBC20000000000000, 179 0xBD90000000000000, 0xAF00000000000000, 0xAEB0000000000000, 180 0xAC60000000000000, 0xADD0000000000000, 0xA9C0000000000000, 181 0xA870000000000000, 0xAAA0000000000000, 0xAB10000000000000, 182 0xA280000000000000, 0xA330000000000000, 0xA1E0000000000000, 183 0xA050000000000000, 0xA440000000000000, 0xA5F0000000000000, 184 0xA720000000000000, 0xA690000000000000, 0x8200000000000000, 185 0x83B0000000000000, 0x8160000000000000, 0x80D0000000000000, 186 0x84C0000000000000, 0x8570000000000000, 0x87A0000000000000, 187 0x8610000000000000, 0x8F80000000000000, 0x8E30000000000000, 188 0x8CE0000000000000, 0x8D50000000000000, 0x8940000000000000, 189 0x88F0000000000000, 0x8A20000000000000, 0x8B90000000000000, 190 0x9900000000000000, 0x98B0000000000000, 0x9A60000000000000, 191 0x9BD0000000000000, 0x9FC0000000000000, 0x9E70000000000000, 192 0x9CA0000000000000, 0x9D10000000000000, 0x9480000000000000, 193 0x9530000000000000, 0x97E0000000000000, 0x9650000000000000, 194 0x9240000000000000, 0x93F0000000000000, 0x9120000000000000, 195 0x9090000000000000, 196 ]; 197 198 // Populate a user-provided buffer with the memoized values for a custom 199 // polynomial. 200 // 201 // The user-provided polynomial must be in the reversed form. 202 export fn memoize(polynomial: u64, buf: *[256]u64) void = { 203 for (let i = 0z; i < 256; i += 1) { 204 let value = i: u64; 205 for (let z = 0z; z < 8; z += 1) { 206 value = if (value & 0x1 == 1) { 207 yield (value >> 1) ^ polynomial; 208 } else { 209 yield value >> 1; 210 }; 211 }; 212 buf[i] = value; 213 }; 214 }; 215 216 export type state = struct { 217 hash::hash, 218 table: *[256]u64, 219 cval: u64, 220 }; 221 222 const crc64_vtable: io::vtable = io::vtable { 223 writer = &write, 224 ... 225 }; 226 227 // Creates a [[hash::hash]] which computes the CRC-64 algorithm. This hash 228 // function does not allocate any state, so you do not need to call 229 // [[hash::close]] when you are done with it. 230 // 231 // It takes a table of memoized values for a given polynomail (for example, 232 // [[iso_table]] or [[ecma_table]]); a table for a custom polynomial, populated 233 // by [[memoize]] function, may also be used. 234 export fn crc64(table: *[256]u64) state = state { 235 stream = &crc64_vtable, 236 sum = &sum, 237 reset = &reset, 238 sz = SZ, 239 table = table, 240 cval = ~0u64, 241 ... 242 }; 243 244 fn write(s: *io::stream, buf: const []u8) (size | io::error) = { 245 let s = s: *state; 246 for (let i = 0z; i < len(buf); i += 1) { 247 let rightbits = s.cval & 0xFF; 248 s.cval = s.table[rightbits ^ buf[i]] ^ (s.cval >> 8); 249 }; 250 return len(buf); 251 }; 252 253 fn reset(h: *hash::hash) void = { 254 let h = h: *state; 255 h.cval = ~0u64; 256 }; 257 258 fn sum(h: *hash::hash, buf: []u8) void = { 259 let h = h: *state; 260 endian::host.putu64(buf, ~h.cval); 261 }; 262 263 // Returns the 64-bit computed CRC. 264 export fn sum64(h: *hash::hash) u64 = { 265 assert(h.reset == &reset); 266 let h = h: *state; 267 return ~h.cval; 268 }; 269 270 @test fn crc64() void = { 271 const vectors: [](str, u64, u64) = [ 272 ("", 0, 0), 273 ("Man can believe the impossible, but can never believe the improbable. -- Oscar Wilde", 274 0x17F71EF3BB851DC7, 0xD0E8ED57865D6AC6), 275 ("We learn from history that we do not learn from history. -- Georg Hegel", 276 0xAA3C335BB49ABE9D, 0x5FD192CC516BBEC3), 277 ("The final delusion is the belief that one has lost all delusions. -- Maurice Chapelain", 278 0x7DFC4F7CE9552D23, 0xF71B429C925D99AE), 279 ]; 280 281 let crc_ecma = crc64(&ecma_table); 282 let crc_iso = crc64(&iso_table); 283 284 let buf: [SZ]u8 = [0...]; 285 286 for (let i = 0z; i < len(vectors); i += 1) { 287 let vec = vectors[i]; 288 289 hash::reset(&crc_ecma); 290 hash::write(&crc_ecma, strings::toutf8(vec.0)); 291 hash::sum(&crc_ecma, buf); 292 assert(endian::host.getu64(buf) == vec.1); 293 assert(sum64(&crc_ecma) == vec.1); 294 295 hash::reset(&crc_iso); 296 hash::write(&crc_iso, strings::toutf8(vec.0)); 297 hash::sum(&crc_iso, buf); 298 assert(endian::host.getu64(buf) == vec.2); 299 assert(sum64(&crc_iso) == vec.2); 300 }; 301 };