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