git.oblomov.eu Git - linux-2.6/blob - lib/libcrc32c.c

   1 /*
   2  * CRC32C
   3  *@Article{castagnoli-crc,
   4  * author =       { Guy Castagnoli and Stefan Braeuer and Martin Herrman},
   5  * title =        {{Optimization of Cyclic Redundancy-Check Codes with 24
   6  *                 and 32 Parity Bits}},
   7  * journal =      IEEE Transactions on Communication,
   8  * year =         {1993},
   9  * volume =       {41},
  10  * number =       {6},
  11  * pages =        {},
  12  * month =        {June},
  13  *}
  14  * Used by the iSCSI driver, possibly others, and derived from the
  15  * the iscsi-crc.c module of the linux-iscsi driver at
  16  * http://linux-iscsi.sourceforge.net.
  17  *
  18  * Following the example of lib/crc32, this function is intended to be
  19  * flexible and useful for all users.  Modules that currently have their
  20  * own crc32c, but hopefully may be able to use this one are:
  21  *  net/sctp (please add all your doco to here if you change to
  22  *            use this one!)
  23  *  <endoflist>
  24  *
  25  * Copyright (c) 2004 Cisco Systems, Inc.
  26  *
  27  * This program is free software; you can redistribute it and/or modify it
  28  * under the terms of the GNU General Public License as published by the Free
  29  * Software Foundation; either version 2 of the License, or (at your option)
  30  * any later version.
  31  *
  32  */
  33 #include <linux/crc32c.h>
  34 #include <linux/compiler.h>
  35 #include <linux/module.h>
  36
  37 MODULE_AUTHOR("Clay Haapala <chaapala@cisco.com>");
  38 MODULE_DESCRIPTION("CRC32c (Castagnoli) calculations");
  39 MODULE_LICENSE("GPL");
  40
  41 #define CRC32C_POLY_BE 0x1EDC6F41
  42 #define CRC32C_POLY_LE 0x82F63B78
  43
  44 #ifndef CRC_LE_BITS
  45 # define CRC_LE_BITS 8
  46 #endif
  47
  48
  49 /*
  50  * Haven't generated a big-endian table yet, but the bit-wise version
  51  * should at least work.
  52  */
  53 #if defined CRC_BE_BITS && CRC_BE_BITS != 1
  54 #undef CRC_BE_BITS
  55 #endif
  56 #ifndef CRC_BE_BITS
  57 # define CRC_BE_BITS 1
  58 #endif
  59
  60 EXPORT_SYMBOL(crc32c_le);
  61
  62 #if CRC_LE_BITS == 1
  63 /*
  64  * Compute things bit-wise, as done in crc32.c.  We could share the tight
  65  * loop below with crc32 and vary the POLY if we don't find value in terms
  66  * of space and maintainability in keeping the two modules separate.
  67  */
  68 u32 __pure
  69 crc32c_le(u32 crc, unsigned char const *p, size_t len)
  70 {
  71         int i;
  72         while (len--) {
  73                 crc ^= *p++;
  74                 for (i = 0; i < 8; i++)
  75                         crc = (crc >> 1) ^ ((crc & 1) ? CRC32C_POLY_LE : 0);
  76         }
  77         return crc;
  78 }
  79 #else
  80
  81 /*
  82  * This is the CRC-32C table
  83  * Generated with:
  84  * width = 32 bits
  85  * poly = 0x1EDC6F41
  86  * reflect input bytes = true
  87  * reflect output bytes = true
  88  */
  89
  90 static const u32 crc32c_table[256] = {
  91         0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L,
  92         0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL,
  93         0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL,
  94         0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L,
  95         0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL,
  96         0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L,
  97         0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L,
  98         0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL,
  99         0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL,
 100         0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L,
 101         0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L,
 102         0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL,
 103         0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L,
 104         0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL,
 105         0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL,
 106         0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L,
 107         0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L,
 108         0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L,
 109         0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L,
 110         0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L,
 111         0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L,
 112         0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L,
 113         0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L,
 114         0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L,
 115         0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L,
 116         0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L,
 117         0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L,
 118         0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L,
 119         0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L,
 120         0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L,
 121         0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L,
 122         0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L,
 123         0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL,
 124         0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L,
 125         0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L,
 126         0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL,
 127         0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L,
 128         0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL,
 129         0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL,
 130         0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L,
 131         0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L,
 132         0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL,
 133         0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL,
 134         0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L,
 135         0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL,
 136         0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L,
 137         0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L,
 138         0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL,
 139         0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L,
 140         0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL,
 141         0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL,
 142         0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L,
 143         0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL,
 144         0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L,
 145         0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L,
 146         0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL,
 147         0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL,
 148         0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L,
 149         0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L,
 150         0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL,
 151         0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L,
 152         0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL,
 153         0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL,
 154         0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L
 155 };
 156
 157 /*
 158  * Steps through buffer one byte at at time, calculates reflected
 159  * crc using table.
 160  */
 161
 162 u32 __pure
 163 crc32c_le(u32 crc, unsigned char const *data, size_t length)
 164 {
 165         while (length--)
 166                 crc =
 167                     crc32c_table[(crc ^ *data++) & 0xFFL] ^ (crc >> 8);
 168
 169         return crc;
 170 }
 171
 172 #endif  /* CRC_LE_BITS == 8 */
 173
 174 EXPORT_SYMBOL(crc32c_be);
 175
 176 #if CRC_BE_BITS == 1
 177 u32 __pure
 178 crc32c_be(u32 crc, unsigned char const *p, size_t len)
 179 {
 180         int i;
 181         while (len--) {
 182                 crc ^= *p++ << 24;
 183                 for (i = 0; i < 8; i++)
 184                         crc =
 185                             (crc << 1) ^ ((crc & 0x80000000) ? CRC32C_POLY_BE :
 186                                           0);
 187         }
 188         return crc;
 189 }
 190 #endif
 191
 192 /*
 193  * Unit test
 194  *
 195  * A small unit test suite is implemented as part of the crypto suite.
 196  * Select CRYPTO_CRC32C and use the tcrypt module to run the tests.
 197  */