src/lib/crypto/crc32/crc.c

   1 /*
   2  * lib/crypto/crc32/crc.c
   3  *
   4  * Copyright 1990 by the Massachusetts Institute of Technology.
   5  * All Rights Reserved.
   6  *
   7  * Export of this software from the United States of America may
   8  *   require a specific license from the United States Government.
   9  *   It is the responsibility of any person or organization contemplating
  10  *   export to obtain such a license before exporting.
  11  *
  12  * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
  13  * distribute this software and its documentation for any purpose and
  14  * without fee is hereby granted, provided that the above copyright
  15  * notice appear in all copies and that both that copyright notice and
  16  * this permission notice appear in supporting documentation, and that
  17  * the name of M.I.T. not be used in advertising or publicity pertaining
  18  * to distribution of the software without specific, written prior
  19  * permission.  M.I.T. makes no representations about the suitability of
  20  * this software for any purpose.  It is provided "as is" without express
  21  * or implied warranty.
  22  *
  23  *
  24  * CRC-32/AUTODIN-II routines
  25  */
  26
  27 #include "k5-int.h"
  28 #include "crc-32.h"
  29
  30 /* This table and block of comments are taken from code labeled: */
  31 /*
  32  * Copyright (C) 1986 Gary S. Brown.  You may use this program, or
  33  * code or tables extracted from it, as desired without restriction.
  34  */
  35
  36 /* First, the polynomial itself and its table of feedback terms.  The  */
  37 /* polynomial is                                                       */
  38 /* 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 */
  39 /* Note that we take it "backwards" and put the highest-order term in  */
  40 /* the lowest-order bit.  The X^32 term is "implied"; the LSB is the   */
  41 /* X^31 term, etc.  The X^0 term (usually shown as "+1") results in    */
  42 /* the MSB being 1.                                                    */
  43
  44 /* Note that the usual hardware shift register implementation, which   */
  45 /* is what we're using (we're merely optimizing it by doing eight-bit  */
  46 /* chunks at a time) shifts bits into the lowest-order term.  In our   */
  47 /* implementation, that means shifting towards the right.  Why do we   */
  48 /* do it this way?  Because the calculated CRC must be transmitted in  */
  49 /* order from highest-order term to lowest-order term.  UARTs transmit */
  50 /* characters in order from LSB to MSB.  By storing the CRC this way,  */
  51 /* we hand it to the UART in the order low-byte to high-byte; the UART */
  52 /* sends each low-bit to hight-bit; and the result is transmission bit */
  53 /* by bit from highest- to lowest-order term without requiring any bit */
  54 /* shuffling on our part.  Reception works similarly.                  */
  55
  56 /* The feedback terms table consists of 256, 32-bit entries.  Notes:   */
  57 /*                                                                     */
  58 /*  1. The table can be generated at runtime if desired; code to do so */
  59 /*     is shown later.  It might not be obvious, but the feedback      */
  60 /*     terms simply represent the results of eight shift/xor opera-    */
  61 /*     tions for all combinations of data and CRC register values.     */
  62 /*                                                                     */
  63 /*  2. The CRC accumulation logic is the same for all CRC polynomials, */
  64 /*     be they sixteen or thirty-two bits wide.  You simply choose the */
  65 /*     appropriate table.  Alternatively, because the table can be     */
  66 /*     generated at runtime, you can start by generating the table for */
  67 /*     the polynomial in question and use exactly the same "updcrc",   */
  68 /*     if your application needn't simultaneously handle two CRC       */
  69 /*     polynomials.  (Note, however, that XMODEM is strange.)          */
  70 /*                                                                     */
  71 /*  3. For 16-bit CRCs, the table entries need be only 16 bits wide;   */
  72 /*     of course, 32-bit entries work OK if the high 16 bits are zero. */
  73 /*                                                                     */
  74 /*  4. The values must be right-shifted by eight bits by the "updcrc"  */
  75 /*     logic; the shift must be unsigned (bring in zeroes).  On some   */
  76 /*     hardware you could probably optimize the shift in assembler by  */
  77 /*     using byte-swap instructions.                                   */
  78
  79 static u_long const crc_table[256] = {
  80     0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
  81     0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
  82     0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
  83     0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
  84     0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
  85     0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
  86     0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
  87     0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
  88     0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
  89     0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
  90     0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
  91     0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
  92     0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
  93     0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
  94     0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
  95     0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
  96     0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
  97     0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
  98     0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
  99     0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
 100     0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
 101     0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
 102     0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
 103     0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
 104     0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
 105     0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
 106     0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
 107     0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
 108     0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
 109     0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
 110     0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
 111     0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
 112     0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
 113     0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
 114     0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
 115     0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
 116     0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
 117     0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
 118     0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
 119     0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
 120     0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
 121     0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
 122     0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
 123     0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
 124     0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
 125     0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
 126     0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
 127     0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
 128     0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
 129     0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
 130     0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
 131     0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
 132     0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
 133     0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
 134     0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
 135     0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
 136     0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
 137     0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
 138     0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
 139     0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 140     0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
 141     0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
 142     0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
 143     0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 144     };
 145
 146 krb5_error_code INTERFACE
 147 crc32_sum_func NPROTOTYPE((krb5_pointer in, size_t in_length,
 148     krb5_pointer seed, size_t seed_length, krb5_checksum *outcksum));
 149
 150 krb5_error_code INTERFACE
 151 crc32_sum_func(in, in_length, seed, seed_length, outcksum)
 152 krb5_pointer in;
 153 size_t in_length;
 154 krb5_pointer seed;
 155 size_t seed_length;
 156 krb5_checksum FAR *outcksum;
 157 {
 158     register u_char *data;
 159     register u_long c = 0;
 160     register int idx;
 161     size_t i;
 162
 163     data = (u_char *)in;
 164     for (i = 0; i < in_length; i++) {
 165         idx = (int) (data[i] ^ c);
 166         idx &= 0xff;
 167         c >>= 8;
 168         c ^= crc_table[idx];
 169     }
 170     /* c now holds the result */
 171     outcksum->checksum_type = CKSUMTYPE_CRC32;
 172     outcksum->length = 4;
 173     outcksum->contents[0] = (krb5_octet) (c & 0xff);
 174     outcksum->contents[1] = (krb5_octet) ((c >> 8) & 0xff);
 175     outcksum->contents[2] = (krb5_octet) ((c >> 16) & 0xff);
 176     outcksum->contents[3] = (krb5_octet) ((c >> 24) & 0xff);
 177     return 0;
 178 }
 179
 180
 181 krb5_checksum_entry crc32_cksumtable_entry = {
 182     0,
 183     crc32_sum_func,
 184     CRC32_CKSUM_LENGTH, /* CRC-32 is 4 octets */
 185     0,                                  /* not collision proof */
 186     0,                                  /* doesn't use key */
 187 };