epan/crc32.c

   1 /* crc32.c
   2  * CRC-32 routine
   3  *
   4  * $Id$
   5  *
   6  * Wireshark - Network traffic analyzer
   7  * By Gerald Combs <gerald@wireshark.org>
   8  * Copyright 1998 Gerald Combs
   9  *
  10  * Copied from README.developer
  11  *
  12  * This program is free software; you can redistribute it and/or
  13  * modify it under the terms of the GNU General Public License
  14  * as published by the Free Software Foundation; either version 2
  15  * of the License, or (at your option) any later version.
  16  *
  17  * This program is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU General Public License
  23  * along with this program; if not, write to the Free Software
  24  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  25  *
  26  * Credits:
  27  *
  28  * Table from Solomon Peachy
  29  * Routine from Chris Waters
  30  */
  31
  32 #include <glib.h>
  33 #include <epan/tvbuff.h>
  34 #include <epan/crc32.h>
  35
  36 /*****************************************************************/
  37 /*                                                               */
  38 /* CRC32C LOOKUP TABLE                                           */
  39 /* +++================                                           */
  40 /* The following CRC lookup table was generated automagically    */
  41 /* by the Rocksoft^tm Model CRC Algorithm Table Generation       */
  42 /* Program V1.0 using the following model parameters:            */
  43 /*                                                               */
  44 /*    Width   : 4 bytes.                                         */
  45 /*    Poly    : 0x1EDC6F41L                                      */
  46 /*    Reverse : TRUE.                                            */
  47 /*                                                               */
  48 /* For more information on the Rocksoft^tm Model CRC Algorithm,  */
  49 /* see the document titled "A Painless Guide to CRC Error        */
  50 /* Detection Algorithms" by Ross Williams                        */
  51 /* (ross@guest.adelaide.edu.au.). This document is likely to be  */
  52 /* in the FTP archive "ftp.adelaide.edu.au/pub/rocksoft".        */
  53 /*                                                               */
  54 /*****************************************************************/
  55 const guint32 crc32c_table[256] = {
  56                 0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L, 0xC79A971FL,
  57                 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL, 0x8AD958CFL, 0x78B2DBCCL,
  58                 0x6BE22838L, 0x9989AB3BL, 0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L,
  59                 0x5E133C24L, 0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL,
  60                 0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L, 0x9A879FA0L,
  61                 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L, 0x5D1D08BFL, 0xAF768BBCL,
  62                 0xBC267848L, 0x4E4DFB4BL, 0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L,
  63                 0x33ED7D2AL, 0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L,
  64                 0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L, 0x6DFE410EL,
  65                 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL, 0x30E349B1L, 0xC288CAB2L,
  66                 0xD1D83946L, 0x23B3BA45L, 0xF779DEAEL, 0x05125DADL, 0x1642AE59L,
  67                 0xE4292D5AL, 0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL,
  68                 0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L, 0x417B1DBCL,
  69                 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L, 0x86E18AA3L, 0x748A09A0L,
  70                 0x67DAFA54L, 0x95B17957L, 0xCBA24573L, 0x39C9C670L, 0x2A993584L,
  71                 0xD8F2B687L, 0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L,
  72                 0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L, 0x96BF4DCCL,
  73                 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L, 0xDBFC821CL, 0x2997011FL,
  74                 0x3AC7F2EBL, 0xC8AC71E8L, 0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L,
  75                 0x0F36E6F7L, 0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L,
  76                 0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L, 0xEB1FCBADL,
  77                 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L, 0x2C855CB2L, 0xDEEEDFB1L,
  78                 0xCDBE2C45L, 0x3FD5AF46L, 0x7198540DL, 0x83F3D70EL, 0x90A324FAL,
  79                 0x62C8A7F9L, 0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L,
  80                 0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L, 0x3CDB9BDDL,
  81                 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L, 0x82F63B78L, 0x709DB87BL,
  82                 0x63CD4B8FL, 0x91A6C88CL, 0x456CAC67L, 0xB7072F64L, 0xA457DC90L,
  83                 0x563C5F93L, 0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L,
  84                 0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL, 0x92A8FC17L,
  85                 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L, 0x55326B08L, 0xA759E80BL,
  86                 0xB4091BFFL, 0x466298FCL, 0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL,
  87                 0x0B21572CL, 0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L,
  88                 0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L, 0x65D122B9L,
  89                 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL, 0x2892ED69L, 0xDAF96E6AL,
  90                 0xC9A99D9EL, 0x3BC21E9DL, 0xEF087A76L, 0x1D63F975L, 0x0E330A81L,
  91                 0xFC588982L, 0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL,
  92                 0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L, 0x38CC2A06L,
  93                 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L, 0xFF56BD19L, 0x0D3D3E1AL,
  94                 0x1E6DCDEEL, 0xEC064EEDL, 0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L,
  95                 0xD0DDD530L, 0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL,
  96                 0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL, 0x8ECEE914L,
  97                 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L, 0xD3D3E1ABL, 0x21B862A8L,
  98                 0x32E8915CL, 0xC083125FL, 0x144976B4L, 0xE622F5B7L, 0xF5720643L,
  99                 0x07198540L, 0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L,
 100                 0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL, 0xE330A81AL,
 101                 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL, 0x24AA3F05L, 0xD6C1BC06L,
 102                 0xC5914FF2L, 0x37FACCF1L, 0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L,
 103                 0x7AB90321L, 0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL,
 104                 0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L, 0x34F4F86AL,
 105                 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL, 0x79B737BAL, 0x8BDCB4B9L,
 106                 0x988C474DL, 0x6AE7C44EL, 0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L,
 107                 0xAD7D5351L };
 108
 109 /*
 110  * Table for the AUTODIN/HDLC/802.x CRC.
 111  *
 112  * Polynomial is
 113  *
 114  *  x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^8 + x^7 +
 115  *      x^5 + x^4 + x^2 + x + 1
 116  */
 117 const guint32 crc32_ccitt_table[256] = {
 118         0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419,
 119         0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4,
 120         0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07,
 121         0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
 122         0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856,
 123         0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
 124         0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4,
 125         0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
 126         0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3,
 127         0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a,
 128         0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599,
 129         0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
 130         0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190,
 131         0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f,
 132         0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e,
 133         0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
 134         0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed,
 135         0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
 136         0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3,
 137         0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
 138         0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a,
 139         0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5,
 140         0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010,
 141         0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
 142         0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17,
 143         0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6,
 144         0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615,
 145         0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
 146         0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344,
 147         0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
 148         0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a,
 149         0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
 150         0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1,
 151         0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c,
 152         0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef,
 153         0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
 154         0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe,
 155         0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31,
 156         0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c,
 157         0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
 158         0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b,
 159         0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
 160         0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1,
 161         0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
 162         0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278,
 163         0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7,
 164         0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66,
 165         0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 166         0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605,
 167         0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8,
 168         0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b,
 169         0x2d02ef8d
 170 };
 171
 172 #define CRC32_CCITT_SEED    0xFFFFFFFF
 173
 174 guint32 calculate_crc32c(const void *buf, int len, guint32 crc)
 175 {
 176         const guint8 *p = (const guint8 *)buf;
 177         crc = CRC32C_SWAP(crc);
 178         while (len-- > 0) {
 179                 CRC32C(crc, *p++);
 180         }
 181         return CRC32C_SWAP(crc);
 182 }
 183
 184 guint32
 185 crc32_ccitt(const guint8 *buf, guint len)
 186 {
 187   return ( crc32_ccitt_seed(buf, len, CRC32_CCITT_SEED) );
 188 }
 189
 190 guint32
 191 crc32_ccitt_seed(const guint8 *buf, guint len, guint32 seed)
 192 {
 193   guint i;
 194   guint32 crc32 = seed;
 195
 196   for (i = 0; i < len; i++)
 197     crc32 = crc32_ccitt_table[(crc32 ^ buf[i]) & 0xff] ^ (crc32 >> 8);
 198
 199   return ( ~crc32 );
 200 }
 201
 202 guint32
 203 crc32_ccitt_tvb(tvbuff_t *tvb, guint len)
 204 {
 205   const guint8* buf = tvb_get_ptr(tvb, 0, len);
 206
 207   return ( crc32_ccitt_seed(buf, len, CRC32_CCITT_SEED) );
 208 }
 209
 210 guint32
 211 crc32_ccitt_tvb_offset(tvbuff_t *tvb, guint offset, guint len)
 212 {
 213   const guint8* buf = tvb_get_ptr(tvb, offset, len);
 214
 215   return ( crc32_ccitt(buf, len) );
 216 }
 217
 218 guint32
 219 crc32_ccitt_tvb_seed(tvbuff_t *tvb, guint len, guint32 seed)
 220 {
 221   const guint8* buf = tvb_get_ptr(tvb, 0, len);
 222
 223   return ( crc32_ccitt_seed(buf, len, seed) );
 224 }
 225
 226 guint32
 227 crc32_ccitt_tvb_offset_seed(tvbuff_t *tvb, guint offset, guint len, guint32 seed)
 228 {
 229   const guint8* buf = tvb_get_ptr(tvb, offset, len);
 230
 231   return ( crc32_ccitt_seed(buf, len, seed) );
 232 }
 233
 234 /*
 235  * IEEE 802.x version (Ethernet and 802.11, at least) - byte-swap
 236  * the result of "crc32()".
 237  *
 238  * XXX - does this mean we should fetch the Ethernet and 802.11
 239  * FCS with "tvb_get_letohl()" rather than "tvb_get_ntohl()",
 240  * or is fetching it big-endian and byte-swapping the CRC done
 241  * to cope with 802.x sending stuff out in reverse bit order?
 242  */
 243 guint32
 244 crc32_802_tvb(tvbuff_t *tvb, guint len)
 245 {
 246   guint32 c_crc;
 247
 248   c_crc = crc32_ccitt_tvb(tvb, len);
 249
 250   /* Byte reverse. */
 251   c_crc = ((unsigned char)(c_crc>>0)<<24) |
 252     ((unsigned char)(c_crc>>8)<<16) |
 253     ((unsigned char)(c_crc>>16)<<8) |
 254     ((unsigned char)(c_crc>>24)<<0);
 255
 256   return ( c_crc );
 257 }