crc16.ha (12835B)
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-16 checksum. 10 export def SZ: size = 2; 11 12 // CRC-CCITT polynomial for CRC-16. The most commonly used polynomial, used in 13 // Bluetooth, X.25, XMODEM, and many other places. Also known as CRC-X25. 14 export def CCITT: u16 = 0x8408; 15 16 // CMDA200 polynomial for CRC-16. Used in the infrastructure of mobile networks. 17 export def CMDA2000: u16 = 0xE613; 18 19 // DECT polynomial for CRC-16. Typically used in cordless phones. 20 export def DECT: u16 = 0x91A0; 21 22 // ANSI polynomial for CRC-16. Another widely used polynomial, it's seen in USB 23 // devices, Modbus, ANSI X3.28, and many others places. Also known as CRC-IBM. 24 export def ANSI: u16 = 0xA001; 25 26 // Table of memoized values for each byte with the CCITT polynomial. 27 export const ccitt_table: [256]u16 = [ 28 0x0000, 0x1189, 0x2312, 0x329B, 0x4624, 0x57AD, 0x6536, 0x74BF, 0x8C48, 29 0x9DC1, 0xAF5A, 0xBED3, 0xCA6C, 0xDBE5, 0xE97E, 0xF8F7, 0x1081, 0x0108, 30 0x3393, 0x221A, 0x56A5, 0x472C, 0x75B7, 0x643E, 0x9CC9, 0x8D40, 0xBFDB, 31 0xAE52, 0xDAED, 0xCB64, 0xF9FF, 0xE876, 0x2102, 0x308B, 0x0210, 0x1399, 32 0x6726, 0x76AF, 0x4434, 0x55BD, 0xAD4A, 0xBCC3, 0x8E58, 0x9FD1, 0xEB6E, 33 0xFAE7, 0xC87C, 0xD9F5, 0x3183, 0x200A, 0x1291, 0x0318, 0x77A7, 0x662E, 34 0x54B5, 0x453C, 0xBDCB, 0xAC42, 0x9ED9, 0x8F50, 0xFBEF, 0xEA66, 0xD8FD, 35 0xC974, 0x4204, 0x538D, 0x6116, 0x709F, 0x0420, 0x15A9, 0x2732, 0x36BB, 36 0xCE4C, 0xDFC5, 0xED5E, 0xFCD7, 0x8868, 0x99E1, 0xAB7A, 0xBAF3, 0x5285, 37 0x430C, 0x7197, 0x601E, 0x14A1, 0x0528, 0x37B3, 0x263A, 0xDECD, 0xCF44, 38 0xFDDF, 0xEC56, 0x98E9, 0x8960, 0xBBFB, 0xAA72, 0x6306, 0x728F, 0x4014, 39 0x519D, 0x2522, 0x34AB, 0x0630, 0x17B9, 0xEF4E, 0xFEC7, 0xCC5C, 0xDDD5, 40 0xA96A, 0xB8E3, 0x8A78, 0x9BF1, 0x7387, 0x620E, 0x5095, 0x411C, 0x35A3, 41 0x242A, 0x16B1, 0x0738, 0xFFCF, 0xEE46, 0xDCDD, 0xCD54, 0xB9EB, 0xA862, 42 0x9AF9, 0x8B70, 0x8408, 0x9581, 0xA71A, 0xB693, 0xC22C, 0xD3A5, 0xE13E, 43 0xF0B7, 0x0840, 0x19C9, 0x2B52, 0x3ADB, 0x4E64, 0x5FED, 0x6D76, 0x7CFF, 44 0x9489, 0x8500, 0xB79B, 0xA612, 0xD2AD, 0xC324, 0xF1BF, 0xE036, 0x18C1, 45 0x0948, 0x3BD3, 0x2A5A, 0x5EE5, 0x4F6C, 0x7DF7, 0x6C7E, 0xA50A, 0xB483, 46 0x8618, 0x9791, 0xE32E, 0xF2A7, 0xC03C, 0xD1B5, 0x2942, 0x38CB, 0x0A50, 47 0x1BD9, 0x6F66, 0x7EEF, 0x4C74, 0x5DFD, 0xB58B, 0xA402, 0x9699, 0x8710, 48 0xF3AF, 0xE226, 0xD0BD, 0xC134, 0x39C3, 0x284A, 0x1AD1, 0x0B58, 0x7FE7, 49 0x6E6E, 0x5CF5, 0x4D7C, 0xC60C, 0xD785, 0xE51E, 0xF497, 0x8028, 0x91A1, 50 0xA33A, 0xB2B3, 0x4A44, 0x5BCD, 0x6956, 0x78DF, 0x0C60, 0x1DE9, 0x2F72, 51 0x3EFB, 0xD68D, 0xC704, 0xF59F, 0xE416, 0x90A9, 0x8120, 0xB3BB, 0xA232, 52 0x5AC5, 0x4B4C, 0x79D7, 0x685E, 0x1CE1, 0x0D68, 0x3FF3, 0x2E7A, 0xE70E, 53 0xF687, 0xC41C, 0xD595, 0xA12A, 0xB0A3, 0x8238, 0x93B1, 0x6B46, 0x7ACF, 54 0x4854, 0x59DD, 0x2D62, 0x3CEB, 0x0E70, 0x1FF9, 0xF78F, 0xE606, 0xD49D, 55 0xC514, 0xB1AB, 0xA022, 0x92B9, 0x8330, 0x7BC7, 0x6A4E, 0x58D5, 0x495C, 56 0x3DE3, 0x2C6A, 0x1EF1, 0x0F78, 57 ]; 58 59 // Table of memoized values for each byte with the CMDA2000 polynomial. 60 export const cmda2000_table: [256]u16 = [ 61 0x0000, 0x5A7A, 0xB4F4, 0xEE8E, 0xA5CF, 0xFFB5, 0x113B, 0x4B41, 0x87B9, 62 0xDDC3, 0x334D, 0x6937, 0x2276, 0x780C, 0x9682, 0xCCF8, 0xC355, 0x992F, 63 0x77A1, 0x2DDB, 0x669A, 0x3CE0, 0xD26E, 0x8814, 0x44EC, 0x1E96, 0xF018, 64 0xAA62, 0xE123, 0xBB59, 0x55D7, 0x0FAD, 0x4A8D, 0x10F7, 0xFE79, 0xA403, 65 0xEF42, 0xB538, 0x5BB6, 0x01CC, 0xCD34, 0x974E, 0x79C0, 0x23BA, 0x68FB, 66 0x3281, 0xDC0F, 0x8675, 0x89D8, 0xD3A2, 0x3D2C, 0x6756, 0x2C17, 0x766D, 67 0x98E3, 0xC299, 0x0E61, 0x541B, 0xBA95, 0xE0EF, 0xABAE, 0xF1D4, 0x1F5A, 68 0x4520, 0x951A, 0xCF60, 0x21EE, 0x7B94, 0x30D5, 0x6AAF, 0x8421, 0xDE5B, 69 0x12A3, 0x48D9, 0xA657, 0xFC2D, 0xB76C, 0xED16, 0x0398, 0x59E2, 0x564F, 70 0x0C35, 0xE2BB, 0xB8C1, 0xF380, 0xA9FA, 0x4774, 0x1D0E, 0xD1F6, 0x8B8C, 71 0x6502, 0x3F78, 0x7439, 0x2E43, 0xC0CD, 0x9AB7, 0xDF97, 0x85ED, 0x6B63, 72 0x3119, 0x7A58, 0x2022, 0xCEAC, 0x94D6, 0x582E, 0x0254, 0xECDA, 0xB6A0, 73 0xFDE1, 0xA79B, 0x4915, 0x136F, 0x1CC2, 0x46B8, 0xA836, 0xF24C, 0xB90D, 74 0xE377, 0x0DF9, 0x5783, 0x9B7B, 0xC101, 0x2F8F, 0x75F5, 0x3EB4, 0x64CE, 75 0x8A40, 0xD03A, 0xE613, 0xBC69, 0x52E7, 0x089D, 0x43DC, 0x19A6, 0xF728, 76 0xAD52, 0x61AA, 0x3BD0, 0xD55E, 0x8F24, 0xC465, 0x9E1F, 0x7091, 0x2AEB, 77 0x2546, 0x7F3C, 0x91B2, 0xCBC8, 0x8089, 0xDAF3, 0x347D, 0x6E07, 0xA2FF, 78 0xF885, 0x160B, 0x4C71, 0x0730, 0x5D4A, 0xB3C4, 0xE9BE, 0xAC9E, 0xF6E4, 79 0x186A, 0x4210, 0x0951, 0x532B, 0xBDA5, 0xE7DF, 0x2B27, 0x715D, 0x9FD3, 80 0xC5A9, 0x8EE8, 0xD492, 0x3A1C, 0x6066, 0x6FCB, 0x35B1, 0xDB3F, 0x8145, 81 0xCA04, 0x907E, 0x7EF0, 0x248A, 0xE872, 0xB208, 0x5C86, 0x06FC, 0x4DBD, 82 0x17C7, 0xF949, 0xA333, 0x7309, 0x2973, 0xC7FD, 0x9D87, 0xD6C6, 0x8CBC, 83 0x6232, 0x3848, 0xF4B0, 0xAECA, 0x4044, 0x1A3E, 0x517F, 0x0B05, 0xE58B, 84 0xBFF1, 0xB05C, 0xEA26, 0x04A8, 0x5ED2, 0x1593, 0x4FE9, 0xA167, 0xFB1D, 85 0x37E5, 0x6D9F, 0x8311, 0xD96B, 0x922A, 0xC850, 0x26DE, 0x7CA4, 0x3984, 86 0x63FE, 0x8D70, 0xD70A, 0x9C4B, 0xC631, 0x28BF, 0x72C5, 0xBE3D, 0xE447, 87 0x0AC9, 0x50B3, 0x1BF2, 0x4188, 0xAF06, 0xF57C, 0xFAD1, 0xA0AB, 0x4E25, 88 0x145F, 0x5F1E, 0x0564, 0xEBEA, 0xB190, 0x7D68, 0x2712, 0xC99C, 0x93E6, 89 0xD8A7, 0x82DD, 0x6C53, 0x3629, 90 ]; 91 92 93 // Table of memoized values for each byte with the DECT polynomial. 94 export const dect_table: [256]u16 = [ 95 0x0000, 0x49F3, 0x93E6, 0xDA15, 0x048D, 0x4D7E, 0x976B, 0xDE98, 0x091A, 96 0x40E9, 0x9AFC, 0xD30F, 0x0D97, 0x4464, 0x9E71, 0xD782, 0x1234, 0x5BC7, 97 0x81D2, 0xC821, 0x16B9, 0x5F4A, 0x855F, 0xCCAC, 0x1B2E, 0x52DD, 0x88C8, 98 0xC13B, 0x1FA3, 0x5650, 0x8C45, 0xC5B6, 0x2468, 0x6D9B, 0xB78E, 0xFE7D, 99 0x20E5, 0x6916, 0xB303, 0xFAF0, 0x2D72, 0x6481, 0xBE94, 0xF767, 0x29FF, 100 0x600C, 0xBA19, 0xF3EA, 0x365C, 0x7FAF, 0xA5BA, 0xEC49, 0x32D1, 0x7B22, 101 0xA137, 0xE8C4, 0x3F46, 0x76B5, 0xACA0, 0xE553, 0x3BCB, 0x7238, 0xA82D, 102 0xE1DE, 0x48D0, 0x0123, 0xDB36, 0x92C5, 0x4C5D, 0x05AE, 0xDFBB, 0x9648, 103 0x41CA, 0x0839, 0xD22C, 0x9BDF, 0x4547, 0x0CB4, 0xD6A1, 0x9F52, 0x5AE4, 104 0x1317, 0xC902, 0x80F1, 0x5E69, 0x179A, 0xCD8F, 0x847C, 0x53FE, 0x1A0D, 105 0xC018, 0x89EB, 0x5773, 0x1E80, 0xC495, 0x8D66, 0x6CB8, 0x254B, 0xFF5E, 106 0xB6AD, 0x6835, 0x21C6, 0xFBD3, 0xB220, 0x65A2, 0x2C51, 0xF644, 0xBFB7, 107 0x612F, 0x28DC, 0xF2C9, 0xBB3A, 0x7E8C, 0x377F, 0xED6A, 0xA499, 0x7A01, 108 0x33F2, 0xE9E7, 0xA014, 0x7796, 0x3E65, 0xE470, 0xAD83, 0x731B, 0x3AE8, 109 0xE0FD, 0xA90E, 0x91A0, 0xD853, 0x0246, 0x4BB5, 0x952D, 0xDCDE, 0x06CB, 110 0x4F38, 0x98BA, 0xD149, 0x0B5C, 0x42AF, 0x9C37, 0xD5C4, 0x0FD1, 0x4622, 111 0x8394, 0xCA67, 0x1072, 0x5981, 0x8719, 0xCEEA, 0x14FF, 0x5D0C, 0x8A8E, 112 0xC37D, 0x1968, 0x509B, 0x8E03, 0xC7F0, 0x1DE5, 0x5416, 0xB5C8, 0xFC3B, 113 0x262E, 0x6FDD, 0xB145, 0xF8B6, 0x22A3, 0x6B50, 0xBCD2, 0xF521, 0x2F34, 114 0x66C7, 0xB85F, 0xF1AC, 0x2BB9, 0x624A, 0xA7FC, 0xEE0F, 0x341A, 0x7DE9, 115 0xA371, 0xEA82, 0x3097, 0x7964, 0xAEE6, 0xE715, 0x3D00, 0x74F3, 0xAA6B, 116 0xE398, 0x398D, 0x707E, 0xD970, 0x9083, 0x4A96, 0x0365, 0xDDFD, 0x940E, 117 0x4E1B, 0x07E8, 0xD06A, 0x9999, 0x438C, 0x0A7F, 0xD4E7, 0x9D14, 0x4701, 118 0x0EF2, 0xCB44, 0x82B7, 0x58A2, 0x1151, 0xCFC9, 0x863A, 0x5C2F, 0x15DC, 119 0xC25E, 0x8BAD, 0x51B8, 0x184B, 0xC6D3, 0x8F20, 0x5535, 0x1CC6, 0xFD18, 120 0xB4EB, 0x6EFE, 0x270D, 0xF995, 0xB066, 0x6A73, 0x2380, 0xF402, 0xBDF1, 121 0x67E4, 0x2E17, 0xF08F, 0xB97C, 0x6369, 0x2A9A, 0xEF2C, 0xA6DF, 0x7CCA, 122 0x3539, 0xEBA1, 0xA252, 0x7847, 0x31B4, 0xE636, 0xAFC5, 0x75D0, 0x3C23, 123 0xE2BB, 0xAB48, 0x715D, 0x38AE, 124 ]; 125 126 // Table of memoized values for each byte with the ANSI polynomial. 127 export const ansi_table: [256]u16 = [ 128 0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241, 0xC601, 129 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440, 0xCC01, 0x0CC0, 130 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40, 0x0A00, 0xCAC1, 0xCB81, 131 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841, 0xD801, 0x18C0, 0x1980, 0xD941, 132 0x1B00, 0xDBC1, 0xDA81, 0x1A40, 0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 133 0x1DC0, 0x1C80, 0xDC41, 0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 134 0x1680, 0xD641, 0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 135 0x1040, 0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240, 136 0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441, 0x3C00, 137 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41, 0xFA01, 0x3AC0, 138 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840, 0x2800, 0xE8C1, 0xE981, 139 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41, 0xEE01, 0x2EC0, 0x2F80, 0xEF41, 140 0x2D00, 0xEDC1, 0xEC81, 0x2C40, 0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 141 0xE7C1, 0xE681, 0x2640, 0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 142 0x2080, 0xE041, 0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 143 0x6240, 0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441, 144 0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41, 0xAA01, 145 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840, 0x7800, 0xB8C1, 146 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41, 0xBE01, 0x7EC0, 0x7F80, 147 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40, 0xB401, 0x74C0, 0x7580, 0xB541, 148 0x7700, 0xB7C1, 0xB681, 0x7640, 0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 149 0x71C0, 0x7080, 0xB041, 0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 150 0x5280, 0x9241, 0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 151 0x5440, 0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40, 152 0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841, 0x8801, 153 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40, 0x4E00, 0x8EC1, 154 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41, 0x4400, 0x84C1, 0x8581, 155 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641, 0x8201, 0x42C0, 0x4380, 0x8341, 156 0x4100, 0x81C1, 0x8081, 0x4040, 157 ]; 158 159 // Populate a user-provided buffer with the memoized values for a custom 160 // polynomial. 161 // 162 // The user-provided polynomial must be in the reversed form. 163 export fn memoize(polynomial: u16, buf: *[256]u16) void = { 164 for (let i = 0z; i < 256; i += 1) { 165 let value = i: u16; 166 for (let z = 0z; z < 8; z += 1) { 167 value = if (value & 0x1 == 1) { 168 yield (value >> 1) ^ polynomial; 169 } else { 170 yield value >> 1; 171 }; 172 }; 173 buf[i] = value; 174 }; 175 }; 176 177 export type state = struct { 178 hash::hash, 179 table: *[256]u16, 180 cval: u16, 181 }; 182 183 const crc16_vtable: io::vtable = io::vtable { 184 writer = &write, 185 ... 186 }; 187 188 // Creates a [[hash::hash]] which computes the CRC-16 algorithm. This hash 189 // function does not allocate any state, so you do not need to call 190 // [[hash::close]] when you are done with it. 191 // 192 // It takes a table of memoized values for a given polynomail (for example, 193 // [[ccitt_table]], [[dect_table]], or [[ansi_table]]); a table for a 194 // custom polynomial, populated by [[memoize]] function, may also be used. 195 export fn crc16(table: *[256]u16) state = state { 196 stream = &crc16_vtable, 197 sum = &sum, 198 reset = &reset, 199 sz = SZ, 200 table = table, 201 cval = ~0u16, 202 ... 203 }; 204 205 fn close(s: *io::stream) void = void; 206 207 fn write(s: *io::stream, buf: const []u8) (size | io::error) = { 208 let s = s: *state; 209 for (let i = 0z; i < len(buf); i += 1) { 210 let rightbits = s.cval & 0xFF; 211 s.cval = s.table[rightbits ^ buf[i]] ^ (s.cval >> 8); 212 }; 213 return len(buf); 214 }; 215 216 fn reset(h: *hash::hash) void = { 217 let h = h: *state; 218 h.cval = ~0u16; 219 }; 220 221 fn sum(h: *hash::hash, buf: []u8) void = { 222 let h = h: *state; 223 endian::host.putu16(buf, ~h.cval); 224 }; 225 226 export fn sum16(h: *hash::hash) u16 = { 227 assert(h.reset == &reset); 228 let h = h: *state; 229 return ~h.cval; 230 }; 231 232 @test fn crc16() void = { 233 const vectors: [](str, u16, u16, u16, u16) = [ 234 ("", 0, 0, 0, 0), 235 ("Always be sincere, even if you don't mean it. -- Harry Truman", 236 0x38DF, 0x2441, 0x8E44, 0xEF5E), 237 ("You get along very well with everyone except animals and people.", 238 0xB6AE, 0xFED0, 0x8739, 0xCF56), 239 ("All generalizations are false, including this one. -- Mark Twain", 240 0xCA68, 0x65EC, 0x98A, 0x45B4), 241 ("I want peace and I'm willing to fight for it. -- Harry Truman", 242 0xB0E8, 0xFE1F, 0x4659, 0x5062), 243 ]; 244 245 let crc_ccitt = crc16(&ccitt_table); 246 let crc_cmda2000 = crc16(&cmda2000_table); 247 let crc_dect = crc16(&dect_table); 248 let crc_ansi = crc16(&ansi_table); 249 250 let buf: [SZ]u8 = [0...]; 251 252 for (let i = 0z; i < len(vectors); i += 1) { 253 let vec = vectors[i]; 254 255 hash::reset(&crc_ccitt); 256 hash::write(&crc_ccitt, strings::toutf8(vec.0)); 257 hash::sum(&crc_ccitt, buf); 258 assert(endian::host.getu16(buf) == vec.1); 259 assert(sum16(&crc_ccitt) == vec.1); 260 261 hash::reset(&crc_cmda2000); 262 hash::write(&crc_cmda2000, strings::toutf8(vec.0)); 263 hash::sum(&crc_cmda2000, buf); 264 assert(endian::host.getu16(buf) == vec.2); 265 assert(sum16(&crc_cmda2000) == vec.2); 266 267 hash::reset(&crc_dect); 268 hash::write(&crc_dect, strings::toutf8(vec.0)); 269 hash::sum(&crc_dect, buf); 270 assert(endian::host.getu16(buf) == vec.3); 271 assert(sum16(&crc_dect) == vec.3); 272 273 hash::reset(&crc_ansi); 274 hash::write(&crc_ansi, strings::toutf8(vec.0)); 275 hash::sum(&crc_ansi, buf); 276 assert(endian::host.getu16(buf) == vec.4); 277 assert(sum16(&crc_ansi) == vec.4); 278 }; 279 };