epan/crc16.c

   1 /* crc16.c
   2  * CRC-16 routine
   3  *
   4  * 2004 Richard van der Hoff <richardv@mxtelecom.com>
   5  *
   6  * $Id$
   7  *
   8  * Wireshark - Network traffic analyzer
   9  * By Gerald Combs <gerald@xxxxxxxxxxxx>
  10  * Copyright 1998 Gerald Combs
  11  *
  12  * Copied from README.developer
  13  *
  14  * This program is free software; you can redistribute it and/or
  15  * modify it under the terms of the GNU General Public License
  16  * as published by the Free Software Foundation; either version 2
  17  * of the License, or (at your option) any later version.
  18  *
  19  * This program is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU General Public License
  25  * along with this program; if not, write to the Free Software
  26  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  27  *
  28  * References:
  29  *  "A Painless Guide to CRC Error Detection Algorithms", Ross Williams
  30  *      http://www.repairfaq.org/filipg/LINK/F_crc_v3.html
  31  *
  32  *  ITU-T Recommendation V.42 (2002), "Error-Correcting Procedures for
  33  *      DCEs using asynchronous-to-synchronous conversion", Para. 8.1.1.6.1
  34  */
  35
  36 #include <glib.h>
  37 #include <epan/tvbuff.h>
  38 #include <epan/crc16.h>
  39
  40
  41 /*****************************************************************/
  42
  43 /*
  44  * Table for the CCITT/ITU/CRC-16 16-bit CRC
  45  *
  46  * Polynomial is
  47  *
  48  *     x^16 + x^12 + x^5 + 1
  49  */
  50
  51 /*                                                               */
  52 /* CRC LOOKUP TABLE                                              */
  53 /* ================                                              */
  54 /* The following CRC lookup table was generated automagically    */
  55 /* by the Rocksoft^tm Model CRC Algorithm Table Generation       */
  56 /* Program V1.0 using the following model parameters:            */
  57 /*                                                               */
  58 /*    Width   : 2 bytes.                                         */
  59 /*    Poly    : 0x1021                                           */
  60 /*    Reverse : TRUE.                                           */
  61 /*                                                               */
  62 /* For more information on the Rocksoft^tm Model CRC Algorithm,  */
  63 /* see the document titled "A Painless Guide to CRC Error        */
  64 /* Detection Algorithms" by Ross Williams                        */
  65 /* (ross@xxxxxxxxxxxxxxxxxxxxxx). This document is likely to be  */
  66 /* in the FTP archive "ftp.adelaide.edu.au/pub/rocksoft".        */
  67 /*                                                               */
  68 /*****************************************************************/
  69
  70 static const guint crc16_ccitt_table[256] =
  71 {
  72  0x0000, 0x1189, 0x2312, 0x329B, 0x4624, 0x57AD, 0x6536, 0x74BF,
  73  0x8C48, 0x9DC1, 0xAF5A, 0xBED3, 0xCA6C, 0xDBE5, 0xE97E, 0xF8F7,
  74  0x1081, 0x0108, 0x3393, 0x221A, 0x56A5, 0x472C, 0x75B7, 0x643E,
  75  0x9CC9, 0x8D40, 0xBFDB, 0xAE52, 0xDAED, 0xCB64, 0xF9FF, 0xE876,
  76  0x2102, 0x308B, 0x0210, 0x1399, 0x6726, 0x76AF, 0x4434, 0x55BD,
  77  0xAD4A, 0xBCC3, 0x8E58, 0x9FD1, 0xEB6E, 0xFAE7, 0xC87C, 0xD9F5,
  78  0x3183, 0x200A, 0x1291, 0x0318, 0x77A7, 0x662E, 0x54B5, 0x453C,
  79  0xBDCB, 0xAC42, 0x9ED9, 0x8F50, 0xFBEF, 0xEA66, 0xD8FD, 0xC974,
  80  0x4204, 0x538D, 0x6116, 0x709F, 0x0420, 0x15A9, 0x2732, 0x36BB,
  81  0xCE4C, 0xDFC5, 0xED5E, 0xFCD7, 0x8868, 0x99E1, 0xAB7A, 0xBAF3,
  82  0x5285, 0x430C, 0x7197, 0x601E, 0x14A1, 0x0528, 0x37B3, 0x263A,
  83  0xDECD, 0xCF44, 0xFDDF, 0xEC56, 0x98E9, 0x8960, 0xBBFB, 0xAA72,
  84  0x6306, 0x728F, 0x4014, 0x519D, 0x2522, 0x34AB, 0x0630, 0x17B9,
  85  0xEF4E, 0xFEC7, 0xCC5C, 0xDDD5, 0xA96A, 0xB8E3, 0x8A78, 0x9BF1,
  86  0x7387, 0x620E, 0x5095, 0x411C, 0x35A3, 0x242A, 0x16B1, 0x0738,
  87  0xFFCF, 0xEE46, 0xDCDD, 0xCD54, 0xB9EB, 0xA862, 0x9AF9, 0x8B70,
  88  0x8408, 0x9581, 0xA71A, 0xB693, 0xC22C, 0xD3A5, 0xE13E, 0xF0B7,
  89  0x0840, 0x19C9, 0x2B52, 0x3ADB, 0x4E64, 0x5FED, 0x6D76, 0x7CFF,
  90  0x9489, 0x8500, 0xB79B, 0xA612, 0xD2AD, 0xC324, 0xF1BF, 0xE036,
  91  0x18C1, 0x0948, 0x3BD3, 0x2A5A, 0x5EE5, 0x4F6C, 0x7DF7, 0x6C7E,
  92  0xA50A, 0xB483, 0x8618, 0x9791, 0xE32E, 0xF2A7, 0xC03C, 0xD1B5,
  93  0x2942, 0x38CB, 0x0A50, 0x1BD9, 0x6F66, 0x7EEF, 0x4C74, 0x5DFD,
  94  0xB58B, 0xA402, 0x9699, 0x8710, 0xF3AF, 0xE226, 0xD0BD, 0xC134,
  95  0x39C3, 0x284A, 0x1AD1, 0x0B58, 0x7FE7, 0x6E6E, 0x5CF5, 0x4D7C,
  96  0xC60C, 0xD785, 0xE51E, 0xF497, 0x8028, 0x91A1, 0xA33A, 0xB2B3,
  97  0x4A44, 0x5BCD, 0x6956, 0x78DF, 0x0C60, 0x1DE9, 0x2F72, 0x3EFB,
  98  0xD68D, 0xC704, 0xF59F, 0xE416, 0x90A9, 0x8120, 0xB3BB, 0xA232,
  99  0x5AC5, 0x4B4C, 0x79D7, 0x685E, 0x1CE1, 0x0D68, 0x3FF3, 0x2E7A,
 100  0xE70E, 0xF687, 0xC41C, 0xD595, 0xA12A, 0xB0A3, 0x8238, 0x93B1,
 101  0x6B46, 0x7ACF, 0x4854, 0x59DD, 0x2D62, 0x3CEB, 0x0E70, 0x1FF9,
 102  0xF78F, 0xE606, 0xD49D, 0xC514, 0xB1AB, 0xA022, 0x92B9, 0x8330,
 103  0x7BC7, 0x6A4E, 0x58D5, 0x495C, 0x3DE3, 0x2C6A, 0x1EF1, 0x0F78
 104 };
 105
 106 static const guint16 crc16_ccitt_start = 0xFFFF;
 107 static const guint16 crc16_ccitt_xorout = 0xFFFF;
 108
 109 /* two types of crcs are possible: unreflected (bits shift left) and
 110  * reflected (bits shift right).
 111  */
 112 #if 0
 113 static guint16 crc16_unreflected(const guint8 *buf, guint len,
 114                                 guint16 crc_in, const guint table[])
 115 {
 116     /* we use guints, rather than guint16s, as they are likely to be
 117        faster. We just ignore the top 16 bits and let them do what they want. */
 118     guint crc16 = (guint)crc_in;;
 119
 120     while( len-- != 0 )
 121        crc16 = table[(crc16 ^ *buf++) & 0xff] ^ (crc16 << 8);
 122
 123     return (guint16)crc16;
 124 }
 125 #endif
 126
 127 static guint16 crc16_reflected(const guint8 *buf, guint len,
 128                                 guint16 crc_in, const guint table[])
 129 {
 130     /* we use guints, rather than guint16s, as they are likely to be
 131        faster. We just ignore the top 16 bits and let them do what they want.
 132        XXX - does any time saved not zero-extending guint16's to 32 bits
 133        into a register outweigh any increased cache footprint from the
 134        larger CRC table? */
 135     guint crc16 = (guint)crc_in;
 136
 137     while( len-- != 0 )
 138        crc16 = table[(crc16 ^ *buf++) & 0xff] ^ (crc16 >> 8);
 139
 140     return (guint16)crc16;
 141 }
 142
 143 guint16 crc16_ccitt(const guint8 *buf, guint len)
 144 {
 145     return crc16_reflected(buf,len,crc16_ccitt_start,crc16_ccitt_table)
 146        ^ crc16_ccitt_xorout;
 147 }
 148
 149 guint16 crc16_ccitt_seed(const guint8 *buf, guint len, guint16 seed)
 150 {
 151     return crc16_reflected(buf,len,seed,crc16_ccitt_table)
 152        ^ crc16_ccitt_xorout;
 153 }
 154
 155 guint16 crc16_ccitt_tvb(tvbuff_t *tvb, guint len)
 156 {
 157     const guint8* buf = tvb_get_ptr(tvb, 0, len);
 158
 159     return crc16_ccitt(buf, len);
 160 }
 161
 162 guint16 crc16_ccitt_tvb_offset(tvbuff_t *tvb, guint offset, guint len)
 163 {
 164     const guint8* buf = tvb_get_ptr(tvb, offset, len);
 165
 166     return crc16_ccitt(buf, len);
 167 }
 168
 169 guint16 crc16_ccitt_tvb_seed(tvbuff_t *tvb, guint len, guint16 seed)
 170 {
 171     const guint8* buf = tvb_get_ptr(tvb, 0, len);
 172
 173     return crc16_ccitt_seed(buf, len, seed);
 174 }
 175
 176 guint16 crc16_ccitt_tvb_offset_seed(tvbuff_t *tvb, guint offset, guint len, guint16 seed)
 177 {
 178     const guint8* buf = tvb_get_ptr(tvb, offset, len);
 179
 180     return crc16_ccitt_seed(buf, len, seed);
 181 }
 182