stun/stuncrc32.c

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