stun/stuncrc32.c

   1 /*
   2  * This file is part of the Nice GLib ICE library.
   3  *
   4  * (C) 2007 Nokia Corporation. All rights reserved.
   5  *  Contact: Rémi Denis-Courmont
   6  * COPYRIGHT (C) 1986 Gary S. Brown
   7  *  See documentation of the function crc32() below.
   8  *
   9  * The contents of this file are subject to the Mozilla Public License Version
  10  * 1.1 (the "License"); you may not use this file except in compliance with
  11  * the License. You may obtain a copy of the License at
  12  * http://www.mozilla.org/MPL/
  13  *
  14  * Software distributed under the License is distributed on an "AS IS" basis,
  15  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  16  * for the specific language governing rights and limitations under the
  17  * License.
  18  *
  19  * The Original Code is the Nice GLib ICE library.
  20  *
  21  * The Initial Developers of the Original Code are Collabora Ltd and Nokia
  22  * Corporation. All Rights Reserved.
  23  *
  24  * Contributors:
  25  *   Rémi Denis-Courmont, Nokia
  26  *
  27  * Alternatively, the contents of this file may be used under the terms of the
  28  * the GNU Lesser General Public License Version 2.1 (the "LGPL"), in which
  29  * case the provisions of LGPL are applicable instead of those above. If you
  30  * wish to allow use of your version of this file only under the terms of the
  31  * LGPL and not to allow others to use your version of this file under the
  32  * MPL, indicate your decision by deleting the provisions above and replace
  33  * them with the notice and other provisions required by the LGPL. If you do
  34  * not delete the provisions above, a recipient may use your version of this
  35  * file under either the MPL or the LGPL.
  36  */
  37
  38 /*-
  39  *  COPYRIGHT (C) 1986 Gary S. Brown.  You may use this program, or
  40  *  code or tables extracted from it, as desired without restriction.
  41  *
  42  *  Extracted from FreeBSD CVS (src/sys/libkern/crc32.c)
  43  *  and adapted by Rémi Denis-Courmont, 2007.
  44  */
  45
  46 /*
  47  *  First, the polynomial itself and its table of feedback terms.  The
  48  *  polynomial is
  49  *  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
  50  *
  51  *  Note that we take it "backwards" and put the highest-order term in
  52  *  the lowest-order bit.  The X^32 term is "implied"; the LSB is the
  53  *  X^31 term, etc.  The X^0 term (usually shown as "+1") results in
  54  *  the MSB being 1
  55  *
  56  *  Note that the usual hardware shift register implementation, which
  57  *  is what we're using (we're merely optimizing it by doing eight-bit
  58  *  chunks at a time) shifts bits into the lowest-order term.  In our
  59  *  implementation, that means shifting towards the right.  Why do we
  60  *  do it this way?  Because the calculated CRC must be transmitted in
  61  *  order from highest-order term to lowest-order term.  UARTs transmit
  62  *  characters in order from LSB to MSB.  By storing the CRC this way
  63  *  we hand it to the UART in the order low-byte to high-byte; the UART
  64  *  sends each low-bit to hight-bit; and the result is transmission bit
  65  *  by bit from highest- to lowest-order term without requiring any bit
  66  *  shuffling on our part.  Reception works similarly
  67  *
  68  *  The feedback terms table consists of 256, 32-bit entries.  Notes
  69  *
  70  *      The table can be generated at runtime if desired; code to do so
  71  *      is shown later.  It might not be obvious, but the feedback
  72  *      terms simply represent the results of eight shift/xor opera
  73  *      tions for all combinations of data and CRC register values
  74  *
  75  *      The values must be right-shifted by eight bits by the "updcrc
  76  *      logic; the shift must be unsigned (bring in zeroes).  On some
  77  *      hardware you could probably optimize the shift in assembler by
  78  *      using byte-swap instructions
  79  *      polynomial $edb88320
  80  *
  81  *
  82  * CRC32 code derived from work by Gary S. Brown.
  83  */
  84
  85
  86 #ifdef HAVE_CONFIG_H
  87 # include <config.h>
  88 #endif
  89
  90 #include "stuncrc32.h"
  91
  92 static const uint32_t crc32_tab[] = {
  93         0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
  94         0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
  95         0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
  96         0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
  97         0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
  98         0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
  99         0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
 100         0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
 101         0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
 102         0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
 103         0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
 104         0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
 105         0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
 106         0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
 107         0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
 108         0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
 109         0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
 110         0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
 111         0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
 112         0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
 113         0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
 114         0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
 115         0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
 116         0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
 117         0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
 118         0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
 119         0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
 120         0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
 121         0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
 122         0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
 123         0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
 124         0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
 125         0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
 126         0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
 127         0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
 128         0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
 129         0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
 130         0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
 131         0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
 132         0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 133         0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
 134         0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
 135         0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 136 };
 137
 138
 139 uint32_t crc32 (const crc_data *data, size_t n, bool wlm2009_stupid_crc32_typo)
 140 {
 141   size_t i;
 142   uint32_t crc = 0xffffffff;
 143
 144   for (i = 0; i < n; i++)
 145   {
 146     const uint8_t *p = data[i].buf;
 147     size_t size = data[i].len;
 148
 149     while (size--) {
 150       uint32_t lkp = crc32_tab[(crc ^ *p++) & 0xFF];
 151       if (lkp == 0x8bbeb8ea && wlm2009_stupid_crc32_typo)
 152         lkp = 0x8bbe8ea;
 153       crc =  lkp ^ (crc >> 8);
 154     }
 155   }
 156
 157   return crc ^ 0xffffffff;
 158 }