net/sctp/crc32c.c

   1 /* SCTP kernel reference Implementation
   2  * Copyright (c) 1999-2001 Motorola, Inc.
   3  * Copyright (c) 2001 International Business Machines, Corp.
   4  *
   5  * This file is part of the SCTP kernel reference Implementation
   6  *
   7  * SCTP Checksum functions
   8  *
   9  * The SCTP reference implementation is free software;
  10  * you can redistribute it and/or modify it under the terms of
  11  * the GNU General Public License as published by
  12  * the Free Software Foundation; either version 2, or (at your option)
  13  * any later version.
  14  *
  15  * The SCTP reference implementation is distributed in the hope that it
  16  * will be useful, but WITHOUT ANY WARRANTY; without even the implied
  17  *                 ************************
  18  * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  19  * See the GNU General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU General Public License
  22  * along with GNU CC; see the file COPYING.  If not, write to
  23  * the Free Software Foundation, 59 Temple Place - Suite 330,
  24  * Boston, MA 02111-1307, USA.
  25  *
  26  * Please send any bug reports or fixes you make to the
  27  * email address(es):
  28  *    lksctp developers <lksctp-developers@lists.sourceforge.net>
  29  *
  30  * Or submit a bug report through the following website:
  31  *    http://www.sf.net/projects/lksctp
  32  *
  33  * Written or modified by:
  34  *    Dinakaran Joseph
  35  *    Jon Grimm <jgrimm@us.ibm.com>
  36  *
  37  * Any bugs reported given to us we will try to fix... any fixes shared will
  38  * be incorporated into the next SCTP release.
  39  */
  40
  41 /* The following code has been taken directly from
  42  * draft-ietf-tsvwg-sctpcsum-03.txt
  43  *
  44  * The code has now been modified specifically for SCTP knowledge.
  45  */
  46
  47 #include <linux/types.h>
  48 #include <net/sctp/sctp.h>
  49
  50 #define CRC32C_POLY 0x1EDC6F41
  51 #define CRC32C(c,d) (c=(c>>8)^crc_c[(c^(d))&0xFF])
  52 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
  53 /* Copyright 2001, D. Otis.  Use this program, code or tables    */
  54 /* extracted from it, as desired without restriction.            */
  55 /*                                                               */
  56 /* 32 Bit Reflected CRC table generation for SCTP.               */
  57 /* To accommodate serial byte data being shifted out least       */
  58 /* significant bit first, the table's 32 bit words are reflected */
  59 /* which flips both byte and bit MS and LS positions.  The CRC   */
  60 /* is calculated MS bits first from the perspective of the serial*/
  61 /* stream.  The x^32 term is implied and the x^0 term may also   */
  62 /* be shown as +1.  The polynomial code used is 0x1EDC6F41.      */
  63 /* Castagnoli93                                                  */
  64 /* x^32+x^28+x^27+x^26+x^25+x^23+x^22+x^20+x^19+x^18+x^14+x^13+  */
  65 /* x^11+x^10+x^9+x^8+x^6+x^0                                     */
  66 /* Guy Castagnoli Stefan Braeuer and Martin Herrman              */
  67 /* "Optimization of Cyclic Redundancy-Check Codes                */
  68 /* with 24 and 32 Parity Bits",                                  */
  69 /* IEEE Transactions on Communications, Vol.41, No.6, June 1993  */
  70 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
  71 __u32 crc_c[256] = {
  72         0x00000000, 0xF26B8303, 0xE13B70F7, 0x1350F3F4,
  73         0xC79A971F, 0x35F1141C, 0x26A1E7E8, 0xD4CA64EB,
  74         0x8AD958CF, 0x78B2DBCC, 0x6BE22838, 0x9989AB3B,
  75         0x4D43CFD0, 0xBF284CD3, 0xAC78BF27, 0x5E133C24,
  76         0x105EC76F, 0xE235446C, 0xF165B798, 0x030E349B,
  77         0xD7C45070, 0x25AFD373, 0x36FF2087, 0xC494A384,
  78         0x9A879FA0, 0x68EC1CA3, 0x7BBCEF57, 0x89D76C54,
  79         0x5D1D08BF, 0xAF768BBC, 0xBC267848, 0x4E4DFB4B,
  80         0x20BD8EDE, 0xD2D60DDD, 0xC186FE29, 0x33ED7D2A,
  81         0xE72719C1, 0x154C9AC2, 0x061C6936, 0xF477EA35,
  82         0xAA64D611, 0x580F5512, 0x4B5FA6E6, 0xB93425E5,
  83         0x6DFE410E, 0x9F95C20D, 0x8CC531F9, 0x7EAEB2FA,
  84         0x30E349B1, 0xC288CAB2, 0xD1D83946, 0x23B3BA45,
  85         0xF779DEAE, 0x05125DAD, 0x1642AE59, 0xE4292D5A,
  86         0xBA3A117E, 0x4851927D, 0x5B016189, 0xA96AE28A,
  87         0x7DA08661, 0x8FCB0562, 0x9C9BF696, 0x6EF07595,
  88         0x417B1DBC, 0xB3109EBF, 0xA0406D4B, 0x522BEE48,
  89         0x86E18AA3, 0x748A09A0, 0x67DAFA54, 0x95B17957,
  90         0xCBA24573, 0x39C9C670, 0x2A993584, 0xD8F2B687,
  91         0x0C38D26C, 0xFE53516F, 0xED03A29B, 0x1F682198,
  92         0x5125DAD3, 0xA34E59D0, 0xB01EAA24, 0x42752927,
  93         0x96BF4DCC, 0x64D4CECF, 0x77843D3B, 0x85EFBE38,
  94         0xDBFC821C, 0x2997011F, 0x3AC7F2EB, 0xC8AC71E8,
  95         0x1C661503, 0xEE0D9600, 0xFD5D65F4, 0x0F36E6F7,
  96         0x61C69362, 0x93AD1061, 0x80FDE395, 0x72966096,
  97         0xA65C047D, 0x5437877E, 0x4767748A, 0xB50CF789,
  98         0xEB1FCBAD, 0x197448AE, 0x0A24BB5A, 0xF84F3859,
  99         0x2C855CB2, 0xDEEEDFB1, 0xCDBE2C45, 0x3FD5AF46,
 100         0x7198540D, 0x83F3D70E, 0x90A324FA, 0x62C8A7F9,
 101         0xB602C312, 0x44694011, 0x5739B3E5, 0xA55230E6,
 102         0xFB410CC2, 0x092A8FC1, 0x1A7A7C35, 0xE811FF36,
 103         0x3CDB9BDD, 0xCEB018DE, 0xDDE0EB2A, 0x2F8B6829,
 104         0x82F63B78, 0x709DB87B, 0x63CD4B8F, 0x91A6C88C,
 105         0x456CAC67, 0xB7072F64, 0xA457DC90, 0x563C5F93,
 106         0x082F63B7, 0xFA44E0B4, 0xE9141340, 0x1B7F9043,
 107         0xCFB5F4A8, 0x3DDE77AB, 0x2E8E845F, 0xDCE5075C,
 108         0x92A8FC17, 0x60C37F14, 0x73938CE0, 0x81F80FE3,
 109         0x55326B08, 0xA759E80B, 0xB4091BFF, 0x466298FC,
 110         0x1871A4D8, 0xEA1A27DB, 0xF94AD42F, 0x0B21572C,
 111         0xDFEB33C7, 0x2D80B0C4, 0x3ED04330, 0xCCBBC033,
 112         0xA24BB5A6, 0x502036A5, 0x4370C551, 0xB11B4652,
 113         0x65D122B9, 0x97BAA1BA, 0x84EA524E, 0x7681D14D,
 114         0x2892ED69, 0xDAF96E6A, 0xC9A99D9E, 0x3BC21E9D,
 115         0xEF087A76, 0x1D63F975, 0x0E330A81, 0xFC588982,
 116         0xB21572C9, 0x407EF1CA, 0x532E023E, 0xA145813D,
 117         0x758FE5D6, 0x87E466D5, 0x94B49521, 0x66DF1622,
 118         0x38CC2A06, 0xCAA7A905, 0xD9F75AF1, 0x2B9CD9F2,
 119         0xFF56BD19, 0x0D3D3E1A, 0x1E6DCDEE, 0xEC064EED,
 120         0xC38D26C4, 0x31E6A5C7, 0x22B65633, 0xD0DDD530,
 121         0x0417B1DB, 0xF67C32D8, 0xE52CC12C, 0x1747422F,
 122         0x49547E0B, 0xBB3FFD08, 0xA86F0EFC, 0x5A048DFF,
 123         0x8ECEE914, 0x7CA56A17, 0x6FF599E3, 0x9D9E1AE0,
 124         0xD3D3E1AB, 0x21B862A8, 0x32E8915C, 0xC083125F,
 125         0x144976B4, 0xE622F5B7, 0xF5720643, 0x07198540,
 126         0x590AB964, 0xAB613A67, 0xB831C993, 0x4A5A4A90,
 127         0x9E902E7B, 0x6CFBAD78, 0x7FAB5E8C, 0x8DC0DD8F,
 128         0xE330A81A, 0x115B2B19, 0x020BD8ED, 0xF0605BEE,
 129         0x24AA3F05, 0xD6C1BC06, 0xC5914FF2, 0x37FACCF1,
 130         0x69E9F0D5, 0x9B8273D6, 0x88D28022, 0x7AB90321,
 131         0xAE7367CA, 0x5C18E4C9, 0x4F48173D, 0xBD23943E,
 132         0xF36E6F75, 0x0105EC76, 0x12551F82, 0xE03E9C81,
 133         0x34F4F86A, 0xC69F7B69, 0xD5CF889D, 0x27A40B9E,
 134         0x79B737BA, 0x8BDCB4B9, 0x988C474D, 0x6AE7C44E,
 135         0xBE2DA0A5, 0x4C4623A6, 0x5F16D052, 0xAD7D5351,
 136 };
 137
 138 __u32 count_crc(__u8 *buffer, __u16 length)
 139 {
 140         __u32 crc32 = ~(__u32) 0;
 141         __u32 i, result;
 142         __u8 byte0, byte1, byte2, byte3;
 143
 144         /* Optimize this routine to be SCTP specific, knowing how
 145          * to skip the checksum field of the SCTP header.
 146          */
 147
 148         /* Calculate CRC up to the checksum. */
 149         for (i = 0; i < (sizeof(struct sctphdr) - sizeof(__u32)); i++)
 150                 CRC32C(crc32, buffer[i]);
 151
 152         /* Skip checksum field of the header. */
 153         for (i = 0; i < sizeof(__u32); i++)
 154                 CRC32C(crc32, 0);
 155
 156         /* Calculate the rest of the CRC. */
 157         for (i = sizeof(struct sctphdr); i < length ; i++)
 158                 CRC32C(crc32, buffer[i]);
 159
 160         result = ~crc32;
 161
 162         /*  result  now holds the negated polynomial remainder;
 163          *  since the table and algorithm is "reflected" [williams95].
 164          *  That is,  result has the same value as if we mapped the message
 165          *  to a polyomial, computed the host-bit-order polynomial
 166          *  remainder, performed final negation, then did an end-for-end
 167          *  bit-reversal.
 168          *  Note that a 32-bit bit-reversal is identical to four inplace
 169          *  8-bit reversals followed by an end-for-end byteswap.
 170          *  In other words, the bytes of each bit are in the right order,
 171          *  but the bytes have been byteswapped.  So we now do an explicit
 172          *  byteswap.  On a little-endian machine, this byteswap and
 173          *  the final ntohl cancel out and could be elided.
 174          */
 175         byte0 = result & 0xff;
 176         byte1 = (result>>8) & 0xff;
 177         byte2 = (result>>16) & 0xff;
 178         byte3 = (result>>24) & 0xff;
 179
 180         crc32 = ((byte0 << 24) |
 181                  (byte1 << 16) |
 182                  (byte2 << 8)  |
 183                  byte3);
 184         return crc32;
 185 }
 186
 187