crc24q.c

   1 /*
   2  * This is an implementation of the CRC-24Q cyclic redundancy checksum
   3  * used by Qualcomm, RTCM104V3, and PGP 6.5.1. According to the RTCM104V3
   4  * standard, it uses the error polynomial
   5  *
   6  *    x^24+ x^23+ x^18+ x^17+ x^14+ x^11+ x^10+ x^7+ x^6+ x^5+ x^4+ x^3+ x+1
   7  *
   8  * This corresponds to a mask of 0x1864CFB.  For a primer on CRC theory,
   9  * including detailed discussion of how and why the error polynomial is
  10  * expressed by this mask, see <http://www.ross.net/crc/>.
  11  *
  12  * 1) It detects all single bit errors per 24-bit code word.
  13  * 2) It detects all double bit error combinations in a code word.
  14  * 3) It detects any odd number of errors.
  15  * 4) It detects any burst error for which the length of the burst is less than
  16  *    or equal to 24 bits.
  17  * 5) It detects most large error bursts with length greater than 24 bits;
  18  *    the odds of a false positive are at most 2^-23.
  19  *
  20  * This hash should not be considered cryptographically secure, but it
  21  * is extremely good at detecting noise errors.
  22  *
  23  * Note that this version has a seed of 0 wired in.  The RTCM104V3 standard
  24  * requires this.
  25  *
  26  * This file is Copyright (c) 2008,2010 by the GPSD project
  27  * BSD terms apply: see the file COPYING in the distribution root for details.
  28  */
  29 #include <stdbool.h>
  30
  31 #include "crc24q.h"
  32
  33 #ifdef REBUILD_CRC_TABLE
  34 /*
  35  * The crc24q code table below can be regenerated with the following code:
  36  */
  37 #include <stdio.h>
  38 #include <stdlib.h>
  39
  40 unsigned table[256];
  41
  42 #define CRCSEED 0               /* could be NZ to detect leading zeros */
  43 #define CRCPOLY 0x1864CFB       /* encodes all info about the polynomial */
  44
  45 static void crc_init(unsigned table[256])
  46 {
  47     unsigned i, j;
  48     unsigned h;
  49
  50     table[0] = CRCSEED;
  51     table[1] = h = CRCPOLY;
  52
  53     for (i = 2; i < 256; i *= 2) {
  54         if ((h <<= 1) & 0x1000000)
  55             h ^= CRCPOLY;
  56         for (j = 0; j < i; j++)
  57             table[i + j] = table[j] ^ h;
  58     }
  59 }
  60
  61 int main(int argc, char *argv[])
  62 {
  63     int i;
  64
  65     crc_init(table);
  66
  67     for (i = 0; i < 256; i++) {
  68         printf("0x%08X, ", table[i]);
  69         if ((i % 4) == 3)
  70             putchar('\n');
  71     }
  72
  73     exit(0);
  74 }
  75 #endif
  76
  77 static const unsigned crc24q[256] = {
  78     0x00000000, 0x01864CFB, 0x028AD50D, 0x030C99F6,
  79     0x0493E6E1, 0x0515AA1A, 0x061933EC, 0x079F7F17,
  80     0x08A18139, 0x0927CDC2, 0x0A2B5434, 0x0BAD18CF,
  81     0x0C3267D8, 0x0DB42B23, 0x0EB8B2D5, 0x0F3EFE2E,
  82     0x10C54E89, 0x11430272, 0x124F9B84, 0x13C9D77F,
  83     0x1456A868, 0x15D0E493, 0x16DC7D65, 0x175A319E,
  84     0x1864CFB0, 0x19E2834B, 0x1AEE1ABD, 0x1B685646,
  85     0x1CF72951, 0x1D7165AA, 0x1E7DFC5C, 0x1FFBB0A7,
  86     0x200CD1E9, 0x218A9D12, 0x228604E4, 0x2300481F,
  87     0x249F3708, 0x25197BF3, 0x2615E205, 0x2793AEFE,
  88     0x28AD50D0, 0x292B1C2B, 0x2A2785DD, 0x2BA1C926,
  89     0x2C3EB631, 0x2DB8FACA, 0x2EB4633C, 0x2F322FC7,
  90     0x30C99F60, 0x314FD39B, 0x32434A6D, 0x33C50696,
  91     0x345A7981, 0x35DC357A, 0x36D0AC8C, 0x3756E077,
  92     0x38681E59, 0x39EE52A2, 0x3AE2CB54, 0x3B6487AF,
  93     0x3CFBF8B8, 0x3D7DB443, 0x3E712DB5, 0x3FF7614E,
  94     0x4019A3D2, 0x419FEF29, 0x429376DF, 0x43153A24,
  95     0x448A4533, 0x450C09C8, 0x4600903E, 0x4786DCC5,
  96     0x48B822EB, 0x493E6E10, 0x4A32F7E6, 0x4BB4BB1D,
  97     0x4C2BC40A, 0x4DAD88F1, 0x4EA11107, 0x4F275DFC,
  98     0x50DCED5B, 0x515AA1A0, 0x52563856, 0x53D074AD,
  99     0x544F0BBA, 0x55C94741, 0x56C5DEB7, 0x5743924C,
 100     0x587D6C62, 0x59FB2099, 0x5AF7B96F, 0x5B71F594,
 101     0x5CEE8A83, 0x5D68C678, 0x5E645F8E, 0x5FE21375,
 102     0x6015723B, 0x61933EC0, 0x629FA736, 0x6319EBCD,
 103     0x648694DA, 0x6500D821, 0x660C41D7, 0x678A0D2C,
 104     0x68B4F302, 0x6932BFF9, 0x6A3E260F, 0x6BB86AF4,
 105     0x6C2715E3, 0x6DA15918, 0x6EADC0EE, 0x6F2B8C15,
 106     0x70D03CB2, 0x71567049, 0x725AE9BF, 0x73DCA544,
 107     0x7443DA53, 0x75C596A8, 0x76C90F5E, 0x774F43A5,
 108     0x7871BD8B, 0x79F7F170, 0x7AFB6886, 0x7B7D247D,
 109     0x7CE25B6A, 0x7D641791, 0x7E688E67, 0x7FEEC29C,
 110     0x803347A4, 0x81B50B5F, 0x82B992A9, 0x833FDE52,
 111     0x84A0A145, 0x8526EDBE, 0x862A7448, 0x87AC38B3,
 112     0x8892C69D, 0x89148A66, 0x8A181390, 0x8B9E5F6B,
 113     0x8C01207C, 0x8D876C87, 0x8E8BF571, 0x8F0DB98A,
 114     0x90F6092D, 0x917045D6, 0x927CDC20, 0x93FA90DB,
 115     0x9465EFCC, 0x95E3A337, 0x96EF3AC1, 0x9769763A,
 116     0x98578814, 0x99D1C4EF, 0x9ADD5D19, 0x9B5B11E2,
 117     0x9CC46EF5, 0x9D42220E, 0x9E4EBBF8, 0x9FC8F703,
 118     0xA03F964D, 0xA1B9DAB6, 0xA2B54340, 0xA3330FBB,
 119     0xA4AC70AC, 0xA52A3C57, 0xA626A5A1, 0xA7A0E95A,
 120     0xA89E1774, 0xA9185B8F, 0xAA14C279, 0xAB928E82,
 121     0xAC0DF195, 0xAD8BBD6E, 0xAE872498, 0xAF016863,
 122     0xB0FAD8C4, 0xB17C943F, 0xB2700DC9, 0xB3F64132,
 123     0xB4693E25, 0xB5EF72DE, 0xB6E3EB28, 0xB765A7D3,
 124     0xB85B59FD, 0xB9DD1506, 0xBAD18CF0, 0xBB57C00B,
 125     0xBCC8BF1C, 0xBD4EF3E7, 0xBE426A11, 0xBFC426EA,
 126     0xC02AE476, 0xC1ACA88D, 0xC2A0317B, 0xC3267D80,
 127     0xC4B90297, 0xC53F4E6C, 0xC633D79A, 0xC7B59B61,
 128     0xC88B654F, 0xC90D29B4, 0xCA01B042, 0xCB87FCB9,
 129     0xCC1883AE, 0xCD9ECF55, 0xCE9256A3, 0xCF141A58,
 130     0xD0EFAAFF, 0xD169E604, 0xD2657FF2, 0xD3E33309,
 131     0xD47C4C1E, 0xD5FA00E5, 0xD6F69913, 0xD770D5E8,
 132     0xD84E2BC6, 0xD9C8673D, 0xDAC4FECB, 0xDB42B230,
 133     0xDCDDCD27, 0xDD5B81DC, 0xDE57182A, 0xDFD154D1,
 134     0xE026359F, 0xE1A07964, 0xE2ACE092, 0xE32AAC69,
 135     0xE4B5D37E, 0xE5339F85, 0xE63F0673, 0xE7B94A88,
 136     0xE887B4A6, 0xE901F85D, 0xEA0D61AB, 0xEB8B2D50,
 137     0xEC145247, 0xED921EBC, 0xEE9E874A, 0xEF18CBB1,
 138     0xF0E37B16, 0xF16537ED, 0xF269AE1B, 0xF3EFE2E0,
 139     0xF4709DF7, 0xF5F6D10C, 0xF6FA48FA, 0xF77C0401,
 140     0xF842FA2F, 0xF9C4B6D4, 0xFAC82F22, 0xFB4E63D9,
 141     0xFCD11CCE, 0xFD575035, 0xFE5BC9C3, 0xFFDD8538,
 142 };
 143
 144 unsigned crc24q_hash(unsigned char *data, int len)
 145 {
 146     int i;
 147     unsigned crc = 0;
 148
 149     for (i = 0; i < len; i++) {
 150         crc = (crc << 8) ^ crc24q[data[i] ^ (unsigned char)(crc >> 16)];
 151     }
 152
 153     crc = (crc & 0x00ffffff);
 154
 155     return crc;
 156 }
 157
 158 #define LO(x)   (unsigned char)((x) & 0xff)
 159 #define MID(x)  (unsigned char)(((x) >> 8) & 0xff)
 160 #define HI(x)   (unsigned char)(((x) >> 16) & 0xff)
 161
 162 void crc24q_sign(unsigned char *data, int len)
 163 {
 164     unsigned crc = crc24q_hash(data, len);
 165
 166     data[len] = HI(crc);
 167     data[len + 1] = MID(crc);
 168     data[len + 2] = LO(crc);
 169 }
 170
 171 bool crc24q_check(unsigned char *data, int len)
 172 {
 173     unsigned crc = crc24q_hash(data, len - 3);
 174
 175     return (((data[len - 3] == HI(crc)) &&
 176              (data[len - 2] == MID(crc)) && (data[len - 1] == LO(crc))));
 177 }