src/TortoisePlink/SSHCRC.C

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