git.distorted.org.uk Git - u/mdw/putty/blob - sshcrc.c

   1 /*
   2  * CRC32 implementation.
   3  *
   4  * The basic concept of a CRC is that you treat your bit-string
   5  * abcdefg... as a ludicrously long polynomial M=a+bx+cx^2+dx^3+...
   6  * over Z[2]. You then take a modulus polynomial P, and compute the
   7  * remainder of M on division by P. Thus, an erroneous message N
   8  * will only have the same CRC if the difference E = M-N is an
   9  * exact multiple of P. (Note that as we are working over Z[2], M-N
  10  * = N-M = M+N; but that's not very important.)
  11  *
  12  * What makes the CRC good is choosing P to have good properties:
  13  *
  14  *  - If its first and last terms are both nonzero then it cannot
  15  *    be a factor of any single term x^i. Therefore if M and N
  16  *    differ by exactly one bit their CRCs will guaranteeably
  17  *    be distinct.
  18  *
  19  *  - If it has a prime (irreducible) factor with three terms then
  20  *    it cannot divide a polynomial of the form x^i(1+x^j).
  21  *    Therefore if M and N differ by exactly _two_ bits they will
  22  *    have different CRCs.
  23  *
  24  *  - If it has a factor (x+1) then it cannot divide a polynomial
  25  *    with an odd number of terms. Therefore if M and N differ by
  26  *    _any odd_ number of bits they will have different CRCs.
  27  *
  28  *  - If the error term E is of the form x^i*B(x) where B(x) has
  29  *    order less than P (i.e. a short _burst_ of errors) then P
  30  *    cannot divide E (since no polynomial can divide a shorter
  31  *    one), so any such error burst will be spotted.
  32  *
  33  * The CRC32 standard polynomial is
  34  *   x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^1+x^0
  35  *
  36  * In fact, we don't compute M mod P; we compute M*x^32 mod P.
  37  *
  38  * The concrete implementation of the CRC is this: we maintain at
  39  * all times a 32-bit word which is the current remainder of the
  40  * polynomial mod P. Whenever we receive an extra bit, we multiply
  41  * the existing remainder by x, add (XOR) the x^32 term thus
  42  * generated to the new x^32 term caused by the incoming bit, and
  43  * remove the resulting combined x^32 term if present by replacing
  44  * it with (P-x^32).
  45  *
  46  * Bit 0 of the word is the x^31 term and bit 31 is the x^0 term.
  47  * Thus, multiplying by x means shifting right. So the actual
  48  * algorithm goes like this:
  49  *
  50  *   x32term = (crcword & 1) ^ newbit;
  51  *   crcword = (crcword >> 1) ^ (x32term * 0xEDB88320);
  52  *
  53  * In practice, we pre-compute what will happen to crcword on any
  54  * given sequence of eight incoming bits, and store that in a table
  55  * which we then use at run-time to do the job:
  56  *
  57  *   outgoingplusnew = (crcword & 0xFF) ^ newbyte;
  58  *   crcword = (crcword >> 8) ^ table[outgoingplusnew];
  59  *
  60  * where table[outgoingplusnew] is computed by setting crcword=0
  61  * and then iterating the first code fragment eight times (taking
  62  * the incoming byte low bit first).
  63  *
  64  * Note that all shifts are rightward and thus no assumption is
  65  * made about exact word length! (Although word length must be at
  66  * _least_ 32 bits, but ANSI C guarantees this for `unsigned long'
  67  * anyway.)
  68  */
  69
  70 #include <stdlib.h>
  71
  72 /* ----------------------------------------------------------------------
  73  * Multi-function module. Can be compiled three ways.
  74  *
  75  *  - Compile with no special #defines. Will generate a table
  76  *    that's already initialised at compile time, and one function
  77  *    crc32(buf,len) that uses it. Normal usage.
  78  *
  79  *  - Compile with INITFUNC defined. Will generate an uninitialised
  80  *    array as the table, and as well as crc32(buf,len) it will
  81  *    also generate void crc32_init(void) which sets up the table
  82  *    at run time. Useful if binary size is important.
  83  *
  84  *  - Compile with GENPROGRAM defined. Will create a standalone
  85  *    program that does the initialisation and outputs the table as
  86  *    C code.
  87  */
  88
  89 #define POLY (0xEDB88320L)
  90
  91 #ifdef GENPROGRAM
  92 #define INITFUNC /* the gen program needs the init func :-) */
  93 #endif
  94
  95 #ifdef INITFUNC
  96
  97 /*
  98  * This variant of the code generates the table at run-time from an
  99  * init function.
 100  */
 101 static unsigned long crc32_table[256];
 102
 103 void crc32_init(void) {
 104     unsigned long crcword;
 105     int i;
 106
 107     for (i = 0; i < 256; i++) {
 108         unsigned long newbyte, x32term;
 109         int j;
 110         crcword = 0;
 111         newbyte = i;
 112         for (j = 0; j < 8; j++) {
 113             x32term = (crcword ^ newbyte) & 1;
 114             crcword = (crcword >> 1) ^ (x32term * POLY);
 115             newbyte >>= 1;
 116         }
 117         crc32_table[i] = crcword;
 118     }
 119 }
 120
 121 #else
 122
 123 /*
 124  * This variant of the code has the data already prepared.
 125  */
 126 static const unsigned long crc32_table[256] = {
 127     0x00000000L, 0x77073096L, 0xEE0E612CL, 0x990951BAL,
 128     0x076DC419L, 0x706AF48FL, 0xE963A535L, 0x9E6495A3L,
 129     0x0EDB8832L, 0x79DCB8A4L, 0xE0D5E91EL, 0x97D2D988L,
 130     0x09B64C2BL, 0x7EB17CBDL, 0xE7B82D07L, 0x90BF1D91L,
 131     0x1DB71064L, 0x6AB020F2L, 0xF3B97148L, 0x84BE41DEL,
 132     0x1ADAD47DL, 0x6DDDE4EBL, 0xF4D4B551L, 0x83D385C7L,
 133     0x136C9856L, 0x646BA8C0L, 0xFD62F97AL, 0x8A65C9ECL,
 134     0x14015C4FL, 0x63066CD9L, 0xFA0F3D63L, 0x8D080DF5L,
 135     0x3B6E20C8L, 0x4C69105EL, 0xD56041E4L, 0xA2677172L,
 136     0x3C03E4D1L, 0x4B04D447L, 0xD20D85FDL, 0xA50AB56BL,
 137     0x35B5A8FAL, 0x42B2986CL, 0xDBBBC9D6L, 0xACBCF940L,
 138     0x32D86CE3L, 0x45DF5C75L, 0xDCD60DCFL, 0xABD13D59L,
 139     0x26D930ACL, 0x51DE003AL, 0xC8D75180L, 0xBFD06116L,
 140     0x21B4F4B5L, 0x56B3C423L, 0xCFBA9599L, 0xB8BDA50FL,
 141     0x2802B89EL, 0x5F058808L, 0xC60CD9B2L, 0xB10BE924L,
 142     0x2F6F7C87L, 0x58684C11L, 0xC1611DABL, 0xB6662D3DL,
 143     0x76DC4190L, 0x01DB7106L, 0x98D220BCL, 0xEFD5102AL,
 144     0x71B18589L, 0x06B6B51FL, 0x9FBFE4A5L, 0xE8B8D433L,
 145     0x7807C9A2L, 0x0F00F934L, 0x9609A88EL, 0xE10E9818L,
 146     0x7F6A0DBBL, 0x086D3D2DL, 0x91646C97L, 0xE6635C01L,
 147     0x6B6B51F4L, 0x1C6C6162L, 0x856530D8L, 0xF262004EL,
 148     0x6C0695EDL, 0x1B01A57BL, 0x8208F4C1L, 0xF50FC457L,
 149     0x65B0D9C6L, 0x12B7E950L, 0x8BBEB8EAL, 0xFCB9887CL,
 150     0x62DD1DDFL, 0x15DA2D49L, 0x8CD37CF3L, 0xFBD44C65L,
 151     0x4DB26158L, 0x3AB551CEL, 0xA3BC0074L, 0xD4BB30E2L,
 152     0x4ADFA541L, 0x3DD895D7L, 0xA4D1C46DL, 0xD3D6F4FBL,
 153     0x4369E96AL, 0x346ED9FCL, 0xAD678846L, 0xDA60B8D0L,
 154     0x44042D73L, 0x33031DE5L, 0xAA0A4C5FL, 0xDD0D7CC9L,
 155     0x5005713CL, 0x270241AAL, 0xBE0B1010L, 0xC90C2086L,
 156     0x5768B525L, 0x206F85B3L, 0xB966D409L, 0xCE61E49FL,
 157     0x5EDEF90EL, 0x29D9C998L, 0xB0D09822L, 0xC7D7A8B4L,
 158     0x59B33D17L, 0x2EB40D81L, 0xB7BD5C3BL, 0xC0BA6CADL,
 159     0xEDB88320L, 0x9ABFB3B6L, 0x03B6E20CL, 0x74B1D29AL,
 160     0xEAD54739L, 0x9DD277AFL, 0x04DB2615L, 0x73DC1683L,
 161     0xE3630B12L, 0x94643B84L, 0x0D6D6A3EL, 0x7A6A5AA8L,
 162     0xE40ECF0BL, 0x9309FF9DL, 0x0A00AE27L, 0x7D079EB1L,
 163     0xF00F9344L, 0x8708A3D2L, 0x1E01F268L, 0x6906C2FEL,
 164     0xF762575DL, 0x806567CBL, 0x196C3671L, 0x6E6B06E7L,
 165     0xFED41B76L, 0x89D32BE0L, 0x10DA7A5AL, 0x67DD4ACCL,
 166     0xF9B9DF6FL, 0x8EBEEFF9L, 0x17B7BE43L, 0x60B08ED5L,
 167     0xD6D6A3E8L, 0xA1D1937EL, 0x38D8C2C4L, 0x4FDFF252L,
 168     0xD1BB67F1L, 0xA6BC5767L, 0x3FB506DDL, 0x48B2364BL,
 169     0xD80D2BDAL, 0xAF0A1B4CL, 0x36034AF6L, 0x41047A60L,
 170     0xDF60EFC3L, 0xA867DF55L, 0x316E8EEFL, 0x4669BE79L,
 171     0xCB61B38CL, 0xBC66831AL, 0x256FD2A0L, 0x5268E236L,
 172     0xCC0C7795L, 0xBB0B4703L, 0x220216B9L, 0x5505262FL,
 173     0xC5BA3BBEL, 0xB2BD0B28L, 0x2BB45A92L, 0x5CB36A04L,
 174     0xC2D7FFA7L, 0xB5D0CF31L, 0x2CD99E8BL, 0x5BDEAE1DL,
 175     0x9B64C2B0L, 0xEC63F226L, 0x756AA39CL, 0x026D930AL,
 176     0x9C0906A9L, 0xEB0E363FL, 0x72076785L, 0x05005713L,
 177     0x95BF4A82L, 0xE2B87A14L, 0x7BB12BAEL, 0x0CB61B38L,
 178     0x92D28E9BL, 0xE5D5BE0DL, 0x7CDCEFB7L, 0x0BDBDF21L,
 179     0x86D3D2D4L, 0xF1D4E242L, 0x68DDB3F8L, 0x1FDA836EL,
 180     0x81BE16CDL, 0xF6B9265BL, 0x6FB077E1L, 0x18B74777L,
 181     0x88085AE6L, 0xFF0F6A70L, 0x66063BCAL, 0x11010B5CL,
 182     0x8F659EFFL, 0xF862AE69L, 0x616BFFD3L, 0x166CCF45L,
 183     0xA00AE278L, 0xD70DD2EEL, 0x4E048354L, 0x3903B3C2L,
 184     0xA7672661L, 0xD06016F7L, 0x4969474DL, 0x3E6E77DBL,
 185     0xAED16A4AL, 0xD9D65ADCL, 0x40DF0B66L, 0x37D83BF0L,
 186     0xA9BCAE53L, 0xDEBB9EC5L, 0x47B2CF7FL, 0x30B5FFE9L,
 187     0xBDBDF21CL, 0xCABAC28AL, 0x53B39330L, 0x24B4A3A6L,
 188     0xBAD03605L, 0xCDD70693L, 0x54DE5729L, 0x23D967BFL,
 189     0xB3667A2EL, 0xC4614AB8L, 0x5D681B02L, 0x2A6F2B94L,
 190     0xB40BBE37L, 0xC30C8EA1L, 0x5A05DF1BL, 0x2D02EF8DL
 191 };
 192
 193 #endif
 194
 195 #ifdef GENPROGRAM
 196 int main(void) {
 197     unsigned long crcword;
 198     int i;
 199
 200     crc32_init();
 201     for (i = 0; i < 256; i++) {
 202         printf("%s0x%08XL%s",
 203                (i % 4 == 0 ? "    " : " "),
 204                crc32_table[i],
 205                (i % 4 == 3 ? (i == 255 ? "\n" : ",\n") : ","));
 206     }
 207
 208     return 0;
 209 }
 210 #endif
 211
 212 unsigned long crc32(const void *buf, size_t len) {
 213     unsigned long crcword = 0L;
 214     const unsigned char *p = (const unsigned char *) buf;
 215     while (len--) {
 216         unsigned long newbyte = *p++;
 217         newbyte ^= crcword & 0xFFL;
 218         crcword = (crcword >> 8) ^ crc32_table[newbyte];
 219     }
 220     return crcword;
 221 }