util/crc32c.c

   1 /*
   2  *  Castagnoli CRC32C Checksum Algorithm
   3  *
   4  *  Polynomial: 0x11EDC6F41
   5  *
   6  *  Castagnoli93: Guy Castagnoli and Stefan Braeuer and Martin Herrman
   7  *               "Optimization of Cyclic Redundancy-Check Codes with 24
   8  *                 and 32 Parity Bits",IEEE Transactions on Communication,
   9  *                Volume 41, Number 6, June 1993
  10  *
  11  *  Copyright (c) 2013 Red Hat, Inc.,
  12  *
  13  *  Authors:
  14  *   Jeff Cody <jcody@redhat.com>
  15  *
  16  *  Based on the Linux kernel cryptographic crc32c module,
  17  *
  18  *  Copyright (c) 2004 Cisco Systems, Inc.
  19  *  Copyright (c) 2008 Herbert Xu <herbert@gondor.apana.org.au>
  20  *
  21  * This program is free software; you can redistribute it and/or modify it
  22  * under the terms of the GNU General Public License as published by the Free
  23  * Software Foundation; either version 2 of the License, or (at your option)
  24  * any later version.
  25  *
  26  */
  27
  28 #include "qemu/osdep.h"
  29 #include "qemu-common.h"
  30 #include "qemu/crc32c.h"
  31
  32 /*
  33  * This is the CRC-32C table
  34  * Generated with:
  35  * width = 32 bits
  36  * poly = 0x1EDC6F41
  37  * reflect input bytes = true
  38  * reflect output bytes = true
  39  */
  40
  41 static const uint32_t crc32c_table[256] = {
  42     0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L,
  43     0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL,
  44     0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL,
  45     0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L,
  46     0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL,
  47     0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L,
  48     0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L,
  49     0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL,
  50     0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL,
  51     0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L,
  52     0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L,
  53     0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL,
  54     0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L,
  55     0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL,
  56     0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL,
  57     0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L,
  58     0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L,
  59     0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L,
  60     0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L,
  61     0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L,
  62     0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L,
  63     0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L,
  64     0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L,
  65     0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L,
  66     0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L,
  67     0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L,
  68     0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L,
  69     0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L,
  70     0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L,
  71     0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L,
  72     0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L,
  73     0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L,
  74     0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL,
  75     0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L,
  76     0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L,
  77     0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL,
  78     0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L,
  79     0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL,
  80     0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL,
  81     0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L,
  82     0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L,
  83     0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL,
  84     0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL,
  85     0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L,
  86     0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL,
  87     0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L,
  88     0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L,
  89     0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL,
  90     0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L,
  91     0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL,
  92     0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL,
  93     0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L,
  94     0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL,
  95     0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L,
  96     0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L,
  97     0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL,
  98     0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL,
  99     0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L,
 100     0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L,
 101     0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL,
 102     0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L,
 103     0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL,
 104     0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL,
 105     0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L
 106 };
 107
 108
 109 uint32_t crc32c(uint32_t crc, const uint8_t *data, unsigned int length)
 110 {
 111     while (length--) {
 112         crc = crc32c_table[(crc ^ *data++) & 0xFFL] ^ (crc >> 8);
 113     }
 114     return crc^0xffffffff;
 115 }
 116