// SPDX-License-Identifier: MPL-2.0 // (c) Hare authors use endian; use hash; use io; use strings; // The size, in bytes, of a CRC-16 checksum. export def SZ: size = 2; // CRC-CCITT polynomial for CRC-16. The most commonly used polynomial, used in // Bluetooth, X.25, XMODEM, and many other places. Also known as CRC-X25. export def CCITT: u16 = 0x8408; // CMDA200 polynomial for CRC-16. Used in the infrastructure of mobile networks. export def CMDA2000: u16 = 0xE613; // DECT polynomial for CRC-16. Typically used in cordless phones. export def DECT: u16 = 0x91A0; // ANSI polynomial for CRC-16. Another widely used polynomial, it's seen in USB // devices, Modbus, ANSI X3.28, and many others places. Also known as CRC-IBM. export def ANSI: u16 = 0xA001; // Table of memoized values for each byte with the CCITT polynomial. export const ccitt_table: [256]u16 = [ 0x0000, 0x1189, 0x2312, 0x329B, 0x4624, 0x57AD, 0x6536, 0x74BF, 0x8C48, 0x9DC1, 0xAF5A, 0xBED3, 0xCA6C, 0xDBE5, 0xE97E, 0xF8F7, 0x1081, 0x0108, 0x3393, 0x221A, 0x56A5, 0x472C, 0x75B7, 0x643E, 0x9CC9, 0x8D40, 0xBFDB, 0xAE52, 0xDAED, 0xCB64, 0xF9FF, 0xE876, 0x2102, 0x308B, 0x0210, 0x1399, 0x6726, 0x76AF, 0x4434, 0x55BD, 0xAD4A, 0xBCC3, 0x8E58, 0x9FD1, 0xEB6E, 0xFAE7, 0xC87C, 0xD9F5, 0x3183, 0x200A, 0x1291, 0x0318, 0x77A7, 0x662E, 0x54B5, 0x453C, 0xBDCB, 0xAC42, 0x9ED9, 0x8F50, 0xFBEF, 0xEA66, 0xD8FD, 0xC974, 0x4204, 0x538D, 0x6116, 0x709F, 0x0420, 0x15A9, 0x2732, 0x36BB, 0xCE4C, 0xDFC5, 0xED5E, 0xFCD7, 0x8868, 0x99E1, 0xAB7A, 0xBAF3, 0x5285, 0x430C, 0x7197, 0x601E, 0x14A1, 0x0528, 0x37B3, 0x263A, 0xDECD, 0xCF44, 0xFDDF, 0xEC56, 0x98E9, 0x8960, 0xBBFB, 0xAA72, 0x6306, 0x728F, 0x4014, 0x519D, 0x2522, 0x34AB, 0x0630, 0x17B9, 0xEF4E, 0xFEC7, 0xCC5C, 0xDDD5, 0xA96A, 0xB8E3, 0x8A78, 0x9BF1, 0x7387, 0x620E, 0x5095, 0x411C, 0x35A3, 0x242A, 0x16B1, 0x0738, 0xFFCF, 0xEE46, 0xDCDD, 0xCD54, 0xB9EB, 0xA862, 0x9AF9, 0x8B70, 0x8408, 0x9581, 0xA71A, 0xB693, 0xC22C, 0xD3A5, 0xE13E, 0xF0B7, 0x0840, 0x19C9, 0x2B52, 0x3ADB, 0x4E64, 0x5FED, 0x6D76, 0x7CFF, 0x9489, 0x8500, 0xB79B, 0xA612, 0xD2AD, 0xC324, 0xF1BF, 0xE036, 0x18C1, 0x0948, 0x3BD3, 0x2A5A, 0x5EE5, 0x4F6C, 0x7DF7, 0x6C7E, 0xA50A, 0xB483, 0x8618, 0x9791, 0xE32E, 0xF2A7, 0xC03C, 0xD1B5, 0x2942, 0x38CB, 0x0A50, 0x1BD9, 0x6F66, 0x7EEF, 0x4C74, 0x5DFD, 0xB58B, 0xA402, 0x9699, 0x8710, 0xF3AF, 0xE226, 0xD0BD, 0xC134, 0x39C3, 0x284A, 0x1AD1, 0x0B58, 0x7FE7, 0x6E6E, 0x5CF5, 0x4D7C, 0xC60C, 0xD785, 0xE51E, 0xF497, 0x8028, 0x91A1, 0xA33A, 0xB2B3, 0x4A44, 0x5BCD, 0x6956, 0x78DF, 0x0C60, 0x1DE9, 0x2F72, 0x3EFB, 0xD68D, 0xC704, 0xF59F, 0xE416, 0x90A9, 0x8120, 0xB3BB, 0xA232, 0x5AC5, 0x4B4C, 0x79D7, 0x685E, 0x1CE1, 0x0D68, 0x3FF3, 0x2E7A, 0xE70E, 0xF687, 0xC41C, 0xD595, 0xA12A, 0xB0A3, 0x8238, 0x93B1, 0x6B46, 0x7ACF, 0x4854, 0x59DD, 0x2D62, 0x3CEB, 0x0E70, 0x1FF9, 0xF78F, 0xE606, 0xD49D, 0xC514, 0xB1AB, 0xA022, 0x92B9, 0x8330, 0x7BC7, 0x6A4E, 0x58D5, 0x495C, 0x3DE3, 0x2C6A, 0x1EF1, 0x0F78, ]; // Table of memoized values for each byte with the CMDA2000 polynomial. export const cmda2000_table: [256]u16 = [ 0x0000, 0x5A7A, 0xB4F4, 0xEE8E, 0xA5CF, 0xFFB5, 0x113B, 0x4B41, 0x87B9, 0xDDC3, 0x334D, 0x6937, 0x2276, 0x780C, 0x9682, 0xCCF8, 0xC355, 0x992F, 0x77A1, 0x2DDB, 0x669A, 0x3CE0, 0xD26E, 0x8814, 0x44EC, 0x1E96, 0xF018, 0xAA62, 0xE123, 0xBB59, 0x55D7, 0x0FAD, 0x4A8D, 0x10F7, 0xFE79, 0xA403, 0xEF42, 0xB538, 0x5BB6, 0x01CC, 0xCD34, 0x974E, 0x79C0, 0x23BA, 0x68FB, 0x3281, 0xDC0F, 0x8675, 0x89D8, 0xD3A2, 0x3D2C, 0x6756, 0x2C17, 0x766D, 0x98E3, 0xC299, 0x0E61, 0x541B, 0xBA95, 0xE0EF, 0xABAE, 0xF1D4, 0x1F5A, 0x4520, 0x951A, 0xCF60, 0x21EE, 0x7B94, 0x30D5, 0x6AAF, 0x8421, 0xDE5B, 0x12A3, 0x48D9, 0xA657, 0xFC2D, 0xB76C, 0xED16, 0x0398, 0x59E2, 0x564F, 0x0C35, 0xE2BB, 0xB8C1, 0xF380, 0xA9FA, 0x4774, 0x1D0E, 0xD1F6, 0x8B8C, 0x6502, 0x3F78, 0x7439, 0x2E43, 0xC0CD, 0x9AB7, 0xDF97, 0x85ED, 0x6B63, 0x3119, 0x7A58, 0x2022, 0xCEAC, 0x94D6, 0x582E, 0x0254, 0xECDA, 0xB6A0, 0xFDE1, 0xA79B, 0x4915, 0x136F, 0x1CC2, 0x46B8, 0xA836, 0xF24C, 0xB90D, 0xE377, 0x0DF9, 0x5783, 0x9B7B, 0xC101, 0x2F8F, 0x75F5, 0x3EB4, 0x64CE, 0x8A40, 0xD03A, 0xE613, 0xBC69, 0x52E7, 0x089D, 0x43DC, 0x19A6, 0xF728, 0xAD52, 0x61AA, 0x3BD0, 0xD55E, 0x8F24, 0xC465, 0x9E1F, 0x7091, 0x2AEB, 0x2546, 0x7F3C, 0x91B2, 0xCBC8, 0x8089, 0xDAF3, 0x347D, 0x6E07, 0xA2FF, 0xF885, 0x160B, 0x4C71, 0x0730, 0x5D4A, 0xB3C4, 0xE9BE, 0xAC9E, 0xF6E4, 0x186A, 0x4210, 0x0951, 0x532B, 0xBDA5, 0xE7DF, 0x2B27, 0x715D, 0x9FD3, 0xC5A9, 0x8EE8, 0xD492, 0x3A1C, 0x6066, 0x6FCB, 0x35B1, 0xDB3F, 0x8145, 0xCA04, 0x907E, 0x7EF0, 0x248A, 0xE872, 0xB208, 0x5C86, 0x06FC, 0x4DBD, 0x17C7, 0xF949, 0xA333, 0x7309, 0x2973, 0xC7FD, 0x9D87, 0xD6C6, 0x8CBC, 0x6232, 0x3848, 0xF4B0, 0xAECA, 0x4044, 0x1A3E, 0x517F, 0x0B05, 0xE58B, 0xBFF1, 0xB05C, 0xEA26, 0x04A8, 0x5ED2, 0x1593, 0x4FE9, 0xA167, 0xFB1D, 0x37E5, 0x6D9F, 0x8311, 0xD96B, 0x922A, 0xC850, 0x26DE, 0x7CA4, 0x3984, 0x63FE, 0x8D70, 0xD70A, 0x9C4B, 0xC631, 0x28BF, 0x72C5, 0xBE3D, 0xE447, 0x0AC9, 0x50B3, 0x1BF2, 0x4188, 0xAF06, 0xF57C, 0xFAD1, 0xA0AB, 0x4E25, 0x145F, 0x5F1E, 0x0564, 0xEBEA, 0xB190, 0x7D68, 0x2712, 0xC99C, 0x93E6, 0xD8A7, 0x82DD, 0x6C53, 0x3629, ]; // Table of memoized values for each byte with the DECT polynomial. export const dect_table: [256]u16 = [ 0x0000, 0x49F3, 0x93E6, 0xDA15, 0x048D, 0x4D7E, 0x976B, 0xDE98, 0x091A, 0x40E9, 0x9AFC, 0xD30F, 0x0D97, 0x4464, 0x9E71, 0xD782, 0x1234, 0x5BC7, 0x81D2, 0xC821, 0x16B9, 0x5F4A, 0x855F, 0xCCAC, 0x1B2E, 0x52DD, 0x88C8, 0xC13B, 0x1FA3, 0x5650, 0x8C45, 0xC5B6, 0x2468, 0x6D9B, 0xB78E, 0xFE7D, 0x20E5, 0x6916, 0xB303, 0xFAF0, 0x2D72, 0x6481, 0xBE94, 0xF767, 0x29FF, 0x600C, 0xBA19, 0xF3EA, 0x365C, 0x7FAF, 0xA5BA, 0xEC49, 0x32D1, 0x7B22, 0xA137, 0xE8C4, 0x3F46, 0x76B5, 0xACA0, 0xE553, 0x3BCB, 0x7238, 0xA82D, 0xE1DE, 0x48D0, 0x0123, 0xDB36, 0x92C5, 0x4C5D, 0x05AE, 0xDFBB, 0x9648, 0x41CA, 0x0839, 0xD22C, 0x9BDF, 0x4547, 0x0CB4, 0xD6A1, 0x9F52, 0x5AE4, 0x1317, 0xC902, 0x80F1, 0x5E69, 0x179A, 0xCD8F, 0x847C, 0x53FE, 0x1A0D, 0xC018, 0x89EB, 0x5773, 0x1E80, 0xC495, 0x8D66, 0x6CB8, 0x254B, 0xFF5E, 0xB6AD, 0x6835, 0x21C6, 0xFBD3, 0xB220, 0x65A2, 0x2C51, 0xF644, 0xBFB7, 0x612F, 0x28DC, 0xF2C9, 0xBB3A, 0x7E8C, 0x377F, 0xED6A, 0xA499, 0x7A01, 0x33F2, 0xE9E7, 0xA014, 0x7796, 0x3E65, 0xE470, 0xAD83, 0x731B, 0x3AE8, 0xE0FD, 0xA90E, 0x91A0, 0xD853, 0x0246, 0x4BB5, 0x952D, 0xDCDE, 0x06CB, 0x4F38, 0x98BA, 0xD149, 0x0B5C, 0x42AF, 0x9C37, 0xD5C4, 0x0FD1, 0x4622, 0x8394, 0xCA67, 0x1072, 0x5981, 0x8719, 0xCEEA, 0x14FF, 0x5D0C, 0x8A8E, 0xC37D, 0x1968, 0x509B, 0x8E03, 0xC7F0, 0x1DE5, 0x5416, 0xB5C8, 0xFC3B, 0x262E, 0x6FDD, 0xB145, 0xF8B6, 0x22A3, 0x6B50, 0xBCD2, 0xF521, 0x2F34, 0x66C7, 0xB85F, 0xF1AC, 0x2BB9, 0x624A, 0xA7FC, 0xEE0F, 0x341A, 0x7DE9, 0xA371, 0xEA82, 0x3097, 0x7964, 0xAEE6, 0xE715, 0x3D00, 0x74F3, 0xAA6B, 0xE398, 0x398D, 0x707E, 0xD970, 0x9083, 0x4A96, 0x0365, 0xDDFD, 0x940E, 0x4E1B, 0x07E8, 0xD06A, 0x9999, 0x438C, 0x0A7F, 0xD4E7, 0x9D14, 0x4701, 0x0EF2, 0xCB44, 0x82B7, 0x58A2, 0x1151, 0xCFC9, 0x863A, 0x5C2F, 0x15DC, 0xC25E, 0x8BAD, 0x51B8, 0x184B, 0xC6D3, 0x8F20, 0x5535, 0x1CC6, 0xFD18, 0xB4EB, 0x6EFE, 0x270D, 0xF995, 0xB066, 0x6A73, 0x2380, 0xF402, 0xBDF1, 0x67E4, 0x2E17, 0xF08F, 0xB97C, 0x6369, 0x2A9A, 0xEF2C, 0xA6DF, 0x7CCA, 0x3539, 0xEBA1, 0xA252, 0x7847, 0x31B4, 0xE636, 0xAFC5, 0x75D0, 0x3C23, 0xE2BB, 0xAB48, 0x715D, 0x38AE, ]; // Table of memoized values for each byte with the ANSI polynomial. export const ansi_table: [256]u16 = [ 0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241, 0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440, 0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40, 0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841, 0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40, 0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41, 0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641, 0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040, 0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240, 0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441, 0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41, 0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840, 0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41, 0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40, 0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640, 0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041, 0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240, 0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441, 0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41, 0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840, 0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41, 0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40, 0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640, 0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041, 0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241, 0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440, 0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40, 0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841, 0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40, 0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41, 0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641, 0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040, ]; // 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: u16, buf: *[256]u16) void = { for (let i = 0z; i < 256; i += 1) { let value = i: u16; 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]u16, cval: u16, }; const crc16_vtable: io::vtable = io::vtable { writer = &write, ... }; // Creates a [[hash::hash]] which computes the CRC-16 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, // [[ccitt_table]], [[dect_table]], or [[ansi_table]]); a table for a // custom polynomial, populated by [[memoize]] function, may also be used. export fn crc16(table: *[256]u16) state = state { stream = &crc16_vtable, sum = &sum, reset = &reset, sz = SZ, table = table, cval = ~0u16, ... }; fn close(s: *io::stream) void = void; 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 = ~0u16; }; fn sum(h: *hash::hash, buf: []u8) void = { let h = h: *state; endian::host.putu16(buf, ~h.cval); }; export fn sum16(h: *hash::hash) u16 = { assert(h.reset == &reset); let h = h: *state; return ~h.cval; }; @test fn crc16() void = { const vectors: [](str, u16, u16, u16, u16) = [ ("", 0, 0, 0, 0), ("Always be sincere, even if you don't mean it. -- Harry Truman", 0x38DF, 0x2441, 0x8E44, 0xEF5E), ("You get along very well with everyone except animals and people.", 0xB6AE, 0xFED0, 0x8739, 0xCF56), ("All generalizations are false, including this one. -- Mark Twain", 0xCA68, 0x65EC, 0x98A, 0x45B4), ("I want peace and I'm willing to fight for it. -- Harry Truman", 0xB0E8, 0xFE1F, 0x4659, 0x5062), ]; let crc_ccitt = crc16(&ccitt_table); let crc_cmda2000 = crc16(&cmda2000_table); let crc_dect = crc16(&dect_table); let crc_ansi = crc16(&ansi_table); let buf: [SZ]u8 = [0...]; for (let i = 0z; i < len(vectors); i += 1) { let vec = vectors[i]; hash::reset(&crc_ccitt); hash::write(&crc_ccitt, strings::toutf8(vec.0)); hash::sum(&crc_ccitt, buf); assert(endian::host.getu16(buf) == vec.1); assert(sum16(&crc_ccitt) == vec.1); hash::reset(&crc_cmda2000); hash::write(&crc_cmda2000, strings::toutf8(vec.0)); hash::sum(&crc_cmda2000, buf); assert(endian::host.getu16(buf) == vec.2); assert(sum16(&crc_cmda2000) == vec.2); hash::reset(&crc_dect); hash::write(&crc_dect, strings::toutf8(vec.0)); hash::sum(&crc_dect, buf); assert(endian::host.getu16(buf) == vec.3); assert(sum16(&crc_dect) == vec.3); hash::reset(&crc_ansi); hash::write(&crc_ansi, strings::toutf8(vec.0)); hash::sum(&crc_ansi, buf); assert(endian::host.getu16(buf) == vec.4); assert(sum16(&crc_ansi) == vec.4); }; };