kernel-lib/crc32c.c

   1 /*
   2  * Copied from the kernel source code, lib/libcrc32c.c.
   3  *
   4  * This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License as published by the Free
   6  * Software Foundation; either version 2 of the License, or (at your option)
   7  * any later version.
   8  *
   9  */
  10 #include "kerncompat.h"
  11 #include "crc32c.h"
  12 #include <inttypes.h>
  13 #include <string.h>
  14 #include <unistd.h>
  15 #include <stdlib.h>
  16 #include <signal.h>
  17 #include <sys/types.h>
  18 #include <sys/wait.h>
  19
  20 u32 __crc32c_le(u32 crc, unsigned char const *data, size_t length);
  21 static u32 (*crc_function)(u32 crc, unsigned char const *data, size_t length) = __crc32c_le;
  22
  23 #ifdef __x86_64__
  24
  25 /*
  26  * Based on a posting to lkml by Austin Zhang <austin.zhang@intel.com>
  27  *
  28  * Using hardware provided CRC32 instruction to accelerate the CRC32 disposal.
  29  * CRC32C polynomial:0x1EDC6F41(BE)/0x82F63B78(LE)
  30  * CRC32 is a new instruction in Intel SSE4.2, the reference can be found at:
  31  * http://www.intel.com/products/processor/manuals/
  32  * Intel(R) 64 and IA-32 Architectures Software Developer's Manual
  33  * Volume 2A: Instruction Set Reference, A-M
  34  */
  35 #if  __SIZEOF_LONG__ == 8
  36 #define REX_PRE "0x48, "
  37 #define SCALE_F 8
  38 #else
  39 #define REX_PRE
  40 #define SCALE_F 4
  41 #endif
  42
  43 static int crc32c_probed = 0;
  44 static int crc32c_intel_available = 0;
  45
  46 static uint32_t crc32c_intel_le_hw_byte(uint32_t crc, unsigned char const *data,
  47                                         unsigned long length)
  48 {
  49         while (length--) {
  50                 __asm__ __volatile__(
  51                         ".byte 0xf2, 0xf, 0x38, 0xf0, 0xf1"
  52                         :"=S"(crc)
  53                         :"0"(crc), "c"(*data)
  54                 );
  55                 data++;
  56         }
  57
  58         return crc;
  59 }
  60
  61 /*
  62  * Steps through buffer one byte at at time, calculates reflected
  63  * crc using table.
  64  */
  65 static uint32_t crc32c_intel(u32 crc, unsigned char const *data, unsigned long length)
  66 {
  67         unsigned int iquotient = length / SCALE_F;
  68         unsigned int iremainder = length % SCALE_F;
  69         unsigned long *ptmp = (unsigned long *)data;
  70
  71         while (iquotient--) {
  72                 __asm__ __volatile__(
  73                         ".byte 0xf2, " REX_PRE "0xf, 0x38, 0xf1, 0xf1;"
  74                         :"=S"(crc)
  75                         :"0"(crc), "c"(*ptmp)
  76                 );
  77                 ptmp++;
  78         }
  79
  80         if (iremainder)
  81                 crc = crc32c_intel_le_hw_byte(crc, (unsigned char *)ptmp,
  82                                  iremainder);
  83
  84         return crc;
  85 }
  86
  87 static void do_cpuid(unsigned int *eax, unsigned int *ebx, unsigned int *ecx,
  88                      unsigned int *edx)
  89 {
  90         int id = *eax;
  91
  92         asm("movl %4, %%eax;"
  93             "cpuid;"
  94             "movl %%eax, %0;"
  95             "movl %%ebx, %1;"
  96             "movl %%ecx, %2;"
  97             "movl %%edx, %3;"
  98                 : "=r" (*eax), "=r" (*ebx), "=r" (*ecx), "=r" (*edx)
  99                 : "r" (id)
 100                 : "eax", "ebx", "ecx", "edx");
 101 }
 102
 103 static void crc32c_intel_probe(void)
 104 {
 105         if (!crc32c_probed) {
 106                 unsigned int eax, ebx, ecx, edx;
 107
 108                 eax = 1;
 109
 110                 do_cpuid(&eax, &ebx, &ecx, &edx);
 111                 crc32c_intel_available = (ecx & (1 << 20)) != 0;
 112                 crc32c_probed = 1;
 113         }
 114 }
 115
 116 void crc32c_optimization_init(void)
 117 {
 118         crc32c_intel_probe();
 119         if (crc32c_intel_available)
 120                 crc_function = crc32c_intel;
 121 }
 122 #else
 123
 124 void crc32c_optimization_init(void)
 125 {
 126 }
 127
 128 #endif /* __x86_64__ */
 129
 130 /*
 131  * This is the CRC-32C table
 132  * Generated with:
 133  * width = 32 bits
 134  * poly = 0x1EDC6F41
 135  * reflect input bytes = true
 136  * reflect output bytes = true
 137  */
 138
 139 static const u32 crc32c_table[256] = {
 140         0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L,
 141         0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL,
 142         0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL,
 143         0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L,
 144         0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL,
 145         0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L,
 146         0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L,
 147         0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL,
 148         0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL,
 149         0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L,
 150         0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L,
 151         0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL,
 152         0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L,
 153         0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL,
 154         0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL,
 155         0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L,
 156         0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L,
 157         0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L,
 158         0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L,
 159         0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L,
 160         0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L,
 161         0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L,
 162         0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L,
 163         0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L,
 164         0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L,
 165         0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L,
 166         0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L,
 167         0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L,
 168         0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L,
 169         0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L,
 170         0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L,
 171         0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L,
 172         0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL,
 173         0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L,
 174         0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L,
 175         0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL,
 176         0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L,
 177         0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL,
 178         0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL,
 179         0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L,
 180         0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L,
 181         0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL,
 182         0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL,
 183         0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L,
 184         0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL,
 185         0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L,
 186         0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L,
 187         0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL,
 188         0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L,
 189         0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL,
 190         0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL,
 191         0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L,
 192         0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL,
 193         0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L,
 194         0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L,
 195         0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL,
 196         0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL,
 197         0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L,
 198         0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L,
 199         0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL,
 200         0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L,
 201         0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL,
 202         0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL,
 203         0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L
 204 };
 205
 206 /*
 207  * Steps through buffer one byte at at time, calculates reflected
 208  * crc using table.
 209  */
 210
 211 u32 __crc32c_le(u32 crc, unsigned char const *data, size_t length)
 212 {
 213         while (length--)
 214                 crc =
 215                     crc32c_table[(crc ^ *data++) & 0xFFL] ^ (crc >> 8);
 216         return crc;
 217 }
 218
 219 u32 crc32c_le(u32 crc, unsigned char const *data, size_t length)
 220 {
 221         /* Use by-byte access for unaligned buffers */
 222         if ((unsigned long)data % sizeof(unsigned long))
 223                 return __crc32c_le(crc, data, length);
 224
 225         return crc_function(crc, data, length);
 226 }