LXR linux-bk/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#include <asm/byteorder.h>
  37
  38MODULE_AUTHOR("Clay Haapala <chaapala@cisco.com>");
  39MODULE_DESCRIPTION("CRC32c (Castagnoli) calculations");
  40MODULE_LICENSE("GPL");
  41
  42#define CRC32C_POLY_BE 0x1EDC6F41
  43#define CRC32C_POLY_LE 0x82F63B78
  44
  45#ifndef CRC_LE_BITS 
  46# define CRC_LE_BITS 8
  47#endif
  48
  49
  50/*
  51 * Haven't generated a big-endian table yet, but the bit-wise version
  52 * should at least work.
  53 */
  54#if defined CRC_BE_BITS && CRC_BE_BITS != 1
  55#undef CRC_BE_BITS
  56#endif
  57#ifndef CRC_BE_BITS
  58# define CRC_BE_BITS 1
  59#endif
  60
  61EXPORT_SYMBOL(crc32c_le);
  62
  63#if CRC_LE_BITS == 1
  64/*
  65 * Compute things bit-wise, as done in crc32.c.  We could share the tight 
  66 * loop below with crc32 and vary the POLY if we don't find value in terms
  67 * of space and maintainability in keeping the two modules separate.
  68 */
  69u32 __attribute_pure__
  70crc32c_le(u32 crc, unsigned char const *p, size_t len)
  71{
  72        int i;
  73        while (len--) {
  74                crc ^= *p++;
  75                for (i = 0; i < 8; i++)
  76                        crc = (crc >> 1) ^ ((crc & 1) ? CRC32C_POLY_LE : 0);
  77        }
  78        return crc;
  79}
  80#else
  81
  82/*
  83 * This is the CRC-32C table
  84 * Generated with:
  85 * width = 32 bits
  86 * poly = 0x1EDC6F41
  87 * reflect input bytes = true
  88 * reflect output bytes = true
  89 */
  90
  91static u32 crc32c_table[256] = {
  92        0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L,
  93        0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL,
  94        0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL,
  95        0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L,
  96        0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL,
  97        0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L,
  98        0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L,
  99        0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL,
 100        0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL,
 101        0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L,
 102        0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L,
 103        0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL,
 104        0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L,
 105        0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL,
 106        0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL,
 107        0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L,
 108        0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L,
 109        0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L,
 110        0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L,
 111        0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L,
 112        0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L,
 113        0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L,
 114        0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L,
 115        0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L,
 116        0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L,
 117        0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L,
 118        0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L,
 119        0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L,
 120        0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L,
 121        0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L,
 122        0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L,
 123        0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L,
 124        0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL,
 125        0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L,
 126        0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L,
 127        0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL,
 128        0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L,
 129        0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL,
 130        0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL,
 131        0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L,
 132        0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L,
 133        0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL,
 134        0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL,
 135        0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L,
 136        0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL,
 137        0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L,
 138        0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L,
 139        0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL,
 140        0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L,
 141        0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL,
 142        0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL,
 143        0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L,
 144        0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL,
 145        0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L,
 146        0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L,
 147        0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL,
 148        0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL,
 149        0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L,
 150        0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L,
 151        0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL,
 152        0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L,
 153        0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL,
 154        0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL,
 155        0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L
 156};
 157
 158/*
 159 * Steps through buffer one byte at at time, calculates reflected 
 160 * crc using table.
 161 */
 162
 163u32 __attribute_pure__
 164crc32c_le(u32 seed, unsigned char const *data, size_t length)
 165{
 166        u32 crc = __cpu_to_le32(seed);
 167        
 168        while (length--)
 169                crc =
 170                    crc32c_table[(crc ^ *data++) & 0xFFL] ^ (crc >> 8);
 171
 172        return __le32_to_cpu(crc);
 173}
 174
 175#endif  /* CRC_LE_BITS == 8 */
 176
 177EXPORT_SYMBOL(crc32c_be);
 178
 179#if CRC_BE_BITS == 1
 180u32 __attribute_pure__
 181crc32c_be(u32 crc, unsigned char const *p, size_t len)
 182{
 183        int i;
 184        while (len--) {
 185                crc ^= *p++ << 24;
 186                for (i = 0; i < 8; i++)
 187                        crc =
 188                            (crc << 1) ^ ((crc & 0x80000000) ? CRC32C_POLY_BE :
 189                                          0);
 190        }
 191        return crc;
 192}
 193#endif
 194
 195/*
 196 * Unit test
 197 *
 198 * A small unit test suite is implemented as part of the crypto suite.
 199 * Select CRYPTO_CRC32C and use the tcrypt module to run the tests.
 200 */
 201