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
  93 static const uint32_t crc32_tab[] = {
  94         0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
  95         0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
  96         0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
  97         0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
  98         0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
  99         0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
 100         0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
 101         0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
 102         0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
 103         0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
 104         0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
 105         0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
 106         0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
 107         0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
 108         0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
 109         0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
 110         0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
 111         0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
 112         0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
 113         0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
 114         0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
 115         0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
 116         0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
 117         0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
 118         0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
 119         0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
 120         0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
 121         0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
 122         0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
 123         0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
 124         0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
 125         0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
 126         0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
 127         0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
 128         0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
 129         0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
 130         0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
 131         0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
 132         0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
 133         0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 134         0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
 135         0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
 136         0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 137 };
 138
 139
 140 uint32_t crc32 (const struct iovec *iov, size_t n)
 141 {
 142   size_t i;
 143   uint32_t crc = 0xffffffff;
 144
 145   for (i = 0; i < n; i++)
 146   {
 147     const uint8_t *p = iov[i].iov_base;
 148     size_t size = iov[i].iov_len;
 149
 150     while (size--)
 151       crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
 152   }
 153
 154   return crc ^ 0xffffffff;
 155 }