1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * The crc32c algorithms are taken from sctp_crc32 implementation
  23  * common/inet/sctp_crc32.{c,h}, which in turn were taken from nxge_fflp_hash.c
  24  */
  25 
  26 #include <sys/zfs_context.h>
  27 #include <sys/far_crc32c.h>
  28 
  29 static void far_crc32c_word(uint32_t *crcptr, const uint32_t *buf, int len);
  30 
  31 /*
  32  * Fast CRC32C calculation algorithm.  The basic idea is to look at it
  33  * four bytes (one word) at a time, using four tables.  The
  34  * standard algorithm in RFC 3309 uses one table.
  35  */
  36 
  37 #define CRC_32C_POLY 0x1EDC6F41L
  38 
  39 /* The four CRC32c tables. */
  40 static uint32_t crc32c_tab[4][256];
  41 static int initialized;
  42 
  43 
  44 static uint32_t
  45 reflect_32(uint32_t b)
  46 {
  47         int i;
  48         uint32_t rw = 0;
  49 
  50         for (i = 0; i < 32; i++) {
  51                 if (b & 1) {
  52                         rw |= 1 << (31 - i);
  53                 }
  54                 b >>= 1;
  55         }
  56         return (rw);
  57 }
  58 
  59 #ifdef _BIG_ENDIAN
  60 static uint32_t
  61 flip32(uint32_t w)
  62 {
  63         return (((w >> 24) | ((w >> 8) & 0xff00) |
  64             ((w << 8) & 0xff0000) | (w << 24)));
  65 }
  66 #endif
  67 
  68 /*
  69  * Initialize the crc32c tables.
  70  */
  71 
  72 void
  73 far_crc32c_init(void)
  74 {
  75         uint32_t index, bit, byte, crc;
  76 
  77         for (index = 0; index < 256; index++) {
  78                 crc = reflect_32(index);
  79                 for (byte = 0; byte < 4; byte++) {
  80                         for (bit = 0; bit < 8; bit++) {
  81                                 crc = (crc & 0x80000000) ?
  82                                     (crc << 1) ^ CRC_32C_POLY : crc << 1;
  83                         }
  84 #ifdef _BIG_ENDIAN
  85                         crc32c_tab[3 - byte][index] = flip32(reflect_32(crc));
  86 #else
  87                         crc32c_tab[byte][index] = reflect_32(crc);
  88 #endif
  89                 }
  90         }
  91 }
  92 
  93 /*
  94  * Lookup  the crc32c for a byte stream
  95  */
  96 static void
  97 far_crc32c_byte(uint32_t *crcptr, const uint8_t *buf, int len)
  98 {
  99         uint32_t crc;
 100         int i;
 101 
 102         crc = *crcptr;
 103         for (i = 0; i < len; i++) {
 104 #ifdef _BIG_ENDIAN
 105                 crc = (crc << 8) ^ crc32c_tab[3][buf[i] ^ (crc >> 24)];
 106 #else
 107                 crc = (crc >> 8) ^ crc32c_tab[0][buf[i] ^ (crc & 0xff)];
 108 #endif
 109         }
 110         *crcptr = crc;
 111 }
 112 
 113 /*
 114  * Lookup  the crc32c for a 32 bit word stream
 115  * Lookup is done fro the 4 bytes in parallel
 116  * from the tables computed earlier
 117  *
 118  */
 119 static void
 120 far_crc32c_word(uint32_t *crcptr, const uint32_t *buf, int len)
 121 {
 122         uint32_t w, crc;
 123         int i;
 124 
 125         crc = *crcptr;
 126         for (i = 0; i < len; i++) {
 127                 w = crc ^ buf[i];
 128                 crc = crc32c_tab[0][w >> 24] ^
 129                     crc32c_tab[1][(w >> 16) & 0xff] ^
 130                     crc32c_tab[2][(w >> 8) & 0xff] ^
 131                     crc32c_tab[3][w & 0xff];
 132         }
 133         *crcptr = crc;
 134 }
 135 
 136 /*
 137  * Lookup  the crc32c for a stream of bytes
 138  *
 139  * Tries to lookup the CRC on 4 byte words
 140  * If the buffer is not 4 byte aligned, first compute
 141  * with byte lookup until aligned. Then compute crc
 142  * for each 4 bytes. If there are bytes left at the end of
 143  * the buffer, then perform a byte lookup for the remaining bytes
 144  *
 145  *
 146  */
 147 uint32_t
 148 far_crc32c(uint32_t crc32, const uint8_t *buf, int len)
 149 {
 150         int rem;
 151 
 152         if (!initialized) {
 153                 far_crc32c_init();
 154                 initialized = 1;
 155         }
 156 
 157         rem = 4 - (((uintptr_t)buf) & 3);
 158         if (rem != 0) {
 159                 if (len < rem) {
 160                         rem = len;
 161                 }
 162                 far_crc32c_byte(&crc32, buf, rem);
 163                 buf = buf + rem;
 164                 len = len - rem;
 165         }
 166         if (len > 3) {
 167                 far_crc32c_word(&crc32, (const uint32_t *) buf, len / 4);
 168         }
 169         rem = len & 3;
 170         if (rem != 0) {
 171                 far_crc32c_byte(&crc32, buf + len - rem, rem);
 172         }
 173         return (crc32);
 174 }