Pull in BE-compatible crc32c

with my qemu-mips test the CRC fails and the items are never fetched,
this updated crc32c seems to fix that.

1 files changed, 203 insertions, 193 deletions

diff --git a/crc32c.c b/crc32c.c
index a3c526e..4d413bf 100644
--- a/crc32c.c
+++ b/crc32c.c
@@ -1,6 +1,6 @@
 /* crc32c.c -- compute CRC-32C using the Intel crc32 instruction
- * Copyright (C) 2013 Mark Adler
- * Version 1.1  1 Aug 2013  Mark Adler
+ * Copyright (C) 2013, 2015 Mark Adler
+ * Version 1.3  31 Dec 2015  Mark Adler
  */
 
 /*
@@ -31,153 +31,33 @@
 /* Version history:
    1.0  10 Feb 2013  First version
    1.1   1 Aug 2013  Correct comments on why three crc instructions in parallel
+   1.2   1 Nov 2015  Add const qualifier to avoid compiler warning
+                     Load entire input into memory (test code)
+                     Argument gives number of times to repeat (test code)
+                     Argument < 0 forces software implementation (test code)
+   1.3  31 Dec 2015  Check for Intel architecture using compiler macro
+                     Support big-endian processors in software calculation
+                     Add header for external use
  */
 
-/* This version has been modified by dormando for inclusion in memcached */
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <stdint.h>
-#include <unistd.h>
 #include <pthread.h>
-#include "config.h"
-#if defined(__linux__) && defined(__aarch64__)
-#include <sys/auxv.h>
-#endif
 #include "crc32c.h"
 
-crc_func crc32c;
-
 /* CRC-32C (iSCSI) polynomial in reversed bit order. */
 #define POLY 0x82f63b78
 
-/* Table for a quadword-at-a-time software crc. */
-static pthread_once_t crc32c_once_sw = PTHREAD_ONCE_INIT;
-static uint32_t crc32c_table[8][256];
-
-/* Construct table for software CRC-32C calculation. */
-static void crc32c_init_sw(void)
-{
-    uint32_t n, crc, k;
-
-    for (n = 0; n < 256; n++) {
-        crc = n;
-        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
-        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
-        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
-        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
-        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
-        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
-        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
-        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
-        crc32c_table[0][n] = crc;
-    }
-    for (n = 0; n < 256; n++) {
-        crc = crc32c_table[0][n];
-        for (k = 1; k < 8; k++) {
-            crc = crc32c_table[0][crc & 0xff] ^ (crc >> 8);
-            crc32c_table[k][n] = crc;
-        }
-    }
-}
-
-/* Table-driven software version as a fall-back.  This is about 15 times slower
-   than using the hardware instructions.  This assumes little-endian integers,
-   as is the case on Intel processors that the assembler code here is for. */
-static uint32_t crc32c_sw(uint32_t crci, const void *buf, size_t len)
-{
-    const unsigned char *next = buf;
-    uint64_t crc;
-
-    pthread_once(&crc32c_once_sw, crc32c_init_sw);
-    crc = crci ^ 0xffffffff;
-    while (len && ((uintptr_t)next & 7) != 0) {
-        crc = crc32c_table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
-        len--;
-    }
-    while (len >= 8) {
-        crc ^= *(uint64_t *)next;
-        crc = crc32c_table[7][crc & 0xff] ^
-              crc32c_table[6][(crc >> 8) & 0xff] ^
-              crc32c_table[5][(crc >> 16) & 0xff] ^
-              crc32c_table[4][(crc >> 24) & 0xff] ^
-              crc32c_table[3][(crc >> 32) & 0xff] ^
-              crc32c_table[2][(crc >> 40) & 0xff] ^
-              crc32c_table[1][(crc >> 48) & 0xff] ^
-              crc32c_table[0][crc >> 56];
-        next += 8;
-        len -= 8;
-    }
-    while (len) {
-        crc = crc32c_table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
-        len--;
-    }
-    return (uint32_t)crc ^ 0xffffffff;
-}
-
-/* Hardware CRC support for aarch64 platform */
-#if defined(__linux__) && defined(__aarch64__) && defined(ARM_CRC32)
-
-#define CRC32CX(crc, value) __asm__("crc32cx %w[c], %w[c], %x[v]":[c]"+r"(crc):[v]"r"(+value))
-#define CRC32CW(crc, value) __asm__("crc32cw %w[c], %w[c], %w[v]":[c]"+r"(crc):[v]"r"(+value))
-#define CRC32CH(crc, value) __asm__("crc32ch %w[c], %w[c], %w[v]":[c]"+r"(crc):[v]"r"(+value))
-#define CRC32CB(crc, value) __asm__("crc32cb %w[c], %w[c], %w[v]":[c]"+r"(crc):[v]"r"(+value))
-
-#ifndef HWCAP_CRC32
-#define HWCAP_CRC32             (1 << 7)
-#endif /* HWCAP for crc32 */
-
-static uint32_t crc32c_hw_aarch64(uint32_t crc, const void* buf, size_t len)
-{
-        const uint8_t* p_buf = buf;
-        uint64_t crc64bit = crc;
-        for (size_t i = 0; i < len / sizeof(uint64_t); i++) {
-                CRC32CX(crc64bit, *(uint64_t*) p_buf);
-                p_buf += sizeof(uint64_t);
-        }
+uint32_t crc32c_sw_little(uint32_t crc, void const *buf, size_t len);
+uint32_t crc32c_sw_big(uint32_t crc, void const *buf, size_t len);
+#ifdef __x86_64__
 
-        uint32_t crc32bit = (uint32_t) crc64bit;
-        len &= sizeof(uint64_t) - 1;
-        switch (len) {
-        case 7:
-                CRC32CB(crc32bit, *p_buf++);
-        case 6:
-                CRC32CH(crc32bit, *(uint16_t*) p_buf);
-                p_buf += 2;
-        case 4:
-                CRC32CW(crc32bit, *(uint32_t*) p_buf);
-                break;
-        case 3:
-                CRC32CB(crc32bit, *p_buf++);
-        case 2:
-                CRC32CH(crc32bit, *(uint16_t*) p_buf);
-                break;
-        case 5:
-                CRC32CW(crc32bit, *(uint32_t*) p_buf);
-                p_buf += 4;
-        case 1:
-                CRC32CB(crc32bit, *p_buf);
-                break;
-        case 0:
-                break;
-        }
-
-        return crc32bit;
-}
-#endif
-
-/* Apply if the platform is intel */
-#if defined(__X86_64__)||defined(__x86_64__)||defined(__ia64__)
+/* Hardware CRC-32C for Intel and compatible processors. */
 
 /* Multiply a matrix times a vector over the Galois field of two elements,
    GF(2).  Each element is a bit in an unsigned integer.  mat must have at
    least as many entries as the power of two for most significant one bit in
    vec. */
-static inline uint32_t gf2_matrix_times(uint32_t *mat, uint32_t vec)
-{
-    uint32_t sum;
-
-    sum = 0;
+static inline uint32_t gf2_matrix_times(uint32_t *mat, uint32_t vec) {
+    uint32_t sum = 0;
     while (vec) {
         if (vec & 1)
             sum ^= *mat;
@@ -189,11 +69,8 @@ static inline uint32_t gf2_matrix_times(uint32_t *mat, uint32_t vec)
 
 /* Multiply a matrix by itself over GF(2).  Both mat and square must have 32
    rows. */
-static inline void gf2_matrix_square(uint32_t *square, uint32_t *mat)
-{
-    int n;
-
-    for (n = 0; n < 32; n++)
+static inline void gf2_matrix_square(uint32_t *square, uint32_t *mat) {
+    for (unsigned n = 0; n < 32; n++)
         square[n] = gf2_matrix_times(mat, mat[n]);
 }
 
@@ -202,16 +79,13 @@ static inline void gf2_matrix_square(uint32_t *square, uint32_t *mat)
    largest power of two less than len.  The result for len == 0 is the same as
    for len == 1.  A version of this routine could be easily written for any
    len, but that is not needed for this application. */
-static void crc32c_zeros_op(uint32_t *even, size_t len)
-{
-    int n;
-    uint32_t row;
+static void crc32c_zeros_op(uint32_t *even, size_t len) {
     uint32_t odd[32];       /* odd-power-of-two zeros operator */
 
     /* put operator for one zero bit in odd */
     odd[0] = POLY;              /* CRC-32C polynomial */
-    row = 1;
-    for (n = 1; n < 32; n++) {
+    uint32_t row = 1;
+    for (unsigned n = 1; n < 32; n++) {
         odd[n] = row;
         row <<= 1;
     }
@@ -235,19 +109,17 @@ static void crc32c_zeros_op(uint32_t *even, size_t len)
     } while (len);
 
     /* answer ended up in odd -- copy to even */
-    for (n = 0; n < 32; n++)
+    for (unsigned n = 0; n < 32; n++)
         even[n] = odd[n];
 }
 
 /* Take a length and build four lookup tables for applying the zeros operator
    for that length, byte-by-byte on the operand. */
-static void crc32c_zeros(uint32_t zeros[][256], size_t len)
-{
-    uint32_t n;
+static void crc32c_zeros(uint32_t zeros[][256], size_t len) {
     uint32_t op[32];
 
     crc32c_zeros_op(op, len);
-    for (n = 0; n < 256; n++) {
+    for (unsigned n = 0; n < 256; n++) {
         zeros[0][n] = gf2_matrix_times(op, n);
         zeros[1][n] = gf2_matrix_times(op, n << 8);
         zeros[2][n] = gf2_matrix_times(op, n << 16);
@@ -256,8 +128,7 @@ static void crc32c_zeros(uint32_t zeros[][256], size_t len)
 }
 
 /* Apply the zeros operator table to crc. */
-static inline uint32_t crc32c_shift(uint32_t zeros[][256], uint32_t crc)
-{
+static inline uint32_t crc32c_shift(uint32_t zeros[][256], uint32_t crc) {
     return zeros[0][crc & 0xff] ^ zeros[1][(crc >> 8) & 0xff] ^
            zeros[2][(crc >> 16) & 0xff] ^ zeros[3][crc >> 24];
 }
@@ -278,27 +149,23 @@ static uint32_t crc32c_long[4][256];
 static uint32_t crc32c_short[4][256];
 
 /* Initialize tables for shifting crcs. */
-static void crc32c_init_hw(void)
-{
+static void crc32c_init_hw(void) {
     crc32c_zeros(crc32c_long, LONG);
     crc32c_zeros(crc32c_short, SHORT);
 }
 
 /* Compute CRC-32C using the Intel hardware instruction. */
-static uint32_t crc32c_hw(uint32_t crc, const void *buf, size_t len)
-{
-    const unsigned char *next = buf;
-    const unsigned char *end;
-    uint64_t crc0, crc1, crc2;      /* need to be 64 bits for crc32q */
-
+static uint32_t crc32c_hw(uint32_t crc, void const *buf, size_t len) {
     /* populate shift tables the first time through */
     pthread_once(&crc32c_once_hw, crc32c_init_hw);
 
     /* pre-process the crc */
-    crc0 = crc ^ 0xffffffff;
+    crc = ~crc;
+    uint64_t crc0 = crc;            /* 64-bits for crc32q instruction */
 
     /* compute the crc for up to seven leading bytes to bring the data pointer
        to an eight-byte boundary */
+    unsigned char const *next = buf;
     while (len && ((uintptr_t)next & 7) != 0) {
         __asm__("crc32b\t" "(%1), %0"
                 : "=r"(crc0)
@@ -312,9 +179,9 @@ static uint32_t crc32c_hw(uint32_t crc, const void *buf, size_t len)
        Westmere, Sandy Bridge, and Ivy Bridge architectures, which have a
        throughput of one crc per cycle, but a latency of three cycles */
     while (len >= LONG*3) {
-        crc1 = 0;
-        crc2 = 0;
-        end = next + LONG;
+        uint64_t crc1 = 0;
+        uint64_t crc2 = 0;
+        unsigned char const * const end = next + LONG;
         do {
             __asm__("crc32q\t" "(%3), %0\n\t"
                     "crc32q\t" LONGx1 "(%3), %1\n\t"
@@ -332,9 +199,9 @@ static uint32_t crc32c_hw(uint32_t crc, const void *buf, size_t len)
     /* do the same thing, but now on SHORT*3 blocks for the remaining data less
        than a LONG*3 block */
     while (len >= SHORT*3) {
-        crc1 = 0;
-        crc2 = 0;
-        end = next + SHORT;
+        uint64_t crc1 = 0;
+        uint64_t crc2 = 0;
+        unsigned char const * const end = next + SHORT;
         do {
             __asm__("crc32q\t" "(%3), %0\n\t"
                     "crc32q\t" SHORTx1 "(%3), %1\n\t"
@@ -351,14 +218,16 @@ static uint32_t crc32c_hw(uint32_t crc, const void *buf, size_t len)
 
     /* compute the crc on the remaining eight-byte units less than a SHORT*3
        block */
-    end = next + (len - (len & 7));
-    while (next < end) {
-        __asm__("crc32q\t" "(%1), %0"
-                : "=r"(crc0)
-                : "r"(next), "0"(crc0));
-        next += 8;
+    {
+        unsigned char const * const end = next + (len - (len & 7));
+        while (next < end) {
+            __asm__("crc32q\t" "(%1), %0"
+                    : "=r"(crc0)
+                    : "r"(next), "0"(crc0));
+            next += 8;
+        }
+        len &= 7;
     }
-    len &= 7;
 
     /* compute the crc for up to seven trailing bytes */
     while (len) {
@@ -370,7 +239,7 @@ static uint32_t crc32c_hw(uint32_t crc, const void *buf, size_t len)
     }
 
     /* return a post-processed crc */
-    return (uint32_t)crc0 ^ 0xffffffff;
+    return ~crc0;
 }
 
 /* Check for SSE 4.2.  SSE 4.2 was first supported in Nehalem processors
@@ -389,27 +258,168 @@ static uint32_t crc32c_hw(uint32_t crc, const void *buf, size_t len)
         (have) = (ecx >> 20) & 1; \
     } while (0)
 
-#endif
 /* Compute a CRC-32C.  If the crc32 instruction is available, use the hardware
    version.  Otherwise, use the software version. */
-void crc32c_init(void) {
-    #if defined(__X86_64__)||defined(__x86_64__)||defined(__ia64__)
+uint32_t crc32c(uint32_t crc, void const *buf, size_t len) {
     int sse42;
+
     SSE42(sse42);
+    return sse42 ? crc32c_hw(crc, buf, len) : crc32c_sw(crc, buf, len);
+}
 
-    if (sse42) {
-        crc32c = crc32c_hw;
-    } else
-    #endif
-    /* Check if CRC instructions supported by aarch64 */
-    #if defined(__linux__) && defined(__aarch64__) && defined(ARM_CRC32)
-    unsigned long hwcap = getauxval(AT_HWCAP);
-
-    if (hwcap & HWCAP_CRC32) {
-        crc32c = crc32c_hw_aarch64;
-    } else
-    #endif
-    {
-        crc32c = crc32c_sw;
+#else /* !__x86_64__ */
+
+uint32_t crc32c(uint32_t crc, void const *buf, size_t len) {
+    return crc32c_sw(crc, buf, len);
+}
+
+#endif
+
+/* Construct table for software CRC-32C little-endian calculation. */
+static pthread_once_t crc32c_once_little = PTHREAD_ONCE_INIT;
+static uint32_t crc32c_table_little[8][256];
+static void crc32c_init_sw_little(void) {
+    for (unsigned n = 0; n < 256; n++) {
+        uint32_t crc = n;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc32c_table_little[0][n] = crc;
+    }
+    for (unsigned n = 0; n < 256; n++) {
+        uint32_t crc = crc32c_table_little[0][n];
+        for (unsigned k = 1; k < 8; k++) {
+            crc = crc32c_table_little[0][crc & 0xff] ^ (crc >> 8);
+            crc32c_table_little[k][n] = crc;
+        }
+    }
+}
+
+/* Compute a CRC-32C in software assuming a little-endian architecture,
+   constructing the required table if that hasn't already been done. */
+uint32_t crc32c_sw_little(uint32_t crc, void const *buf, size_t len) {
+    unsigned char const *next = buf;
+
+    pthread_once(&crc32c_once_little, crc32c_init_sw_little);
+    crc = ~crc;
+    while (len && ((uintptr_t)next & 7) != 0) {
+        crc = crc32c_table_little[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
+        len--;
     }
+    if (len >= 8) {
+        uint64_t crcw = crc;
+        do {
+            crcw ^= *(uint64_t const *)next;
+            crcw = crc32c_table_little[7][crcw & 0xff] ^
+                   crc32c_table_little[6][(crcw >> 8) & 0xff] ^
+                   crc32c_table_little[5][(crcw >> 16) & 0xff] ^
+                   crc32c_table_little[4][(crcw >> 24) & 0xff] ^
+                   crc32c_table_little[3][(crcw >> 32) & 0xff] ^
+                   crc32c_table_little[2][(crcw >> 40) & 0xff] ^
+                   crc32c_table_little[1][(crcw >> 48) & 0xff] ^
+                   crc32c_table_little[0][crcw >> 56];
+            next += 8;
+            len -= 8;
+        } while (len >= 8);
+        crc = crcw;
+    }
+    while (len) {
+        crc = crc32c_table_little[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
+        len--;
+    }
+    return ~crc;
+}
+
+/* Swap the bytes in a uint64_t.  (Only for big-endian.) */
+#if defined(__has_builtin) || (defined(__GNUC__) && \
+    (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)))
+#  define swap __builtin_bswap64
+#else
+static inline uint64_t swap(uint64_t x) {
+    x = ((x << 8) & 0xff00ff00ff00ff00) | ((x >> 8) & 0xff00ff00ff00ff);
+    x = ((x << 16) & 0xffff0000ffff0000) | ((x >> 16) & 0xffff0000ffff);
+    return (x << 32) | (x >> 32);
+}
+#endif
+
+/* Construct tables for software CRC-32C big-endian calculation. */
+static pthread_once_t crc32c_once_big = PTHREAD_ONCE_INIT;
+static uint32_t crc32c_table_big_byte[256];
+static uint64_t crc32c_table_big[8][256];
+static void crc32c_init_sw_big(void) {
+    for (unsigned n = 0; n < 256; n++) {
+        uint32_t crc = n;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
+        crc32c_table_big_byte[n] = crc;
+    }
+    for (unsigned n = 0; n < 256; n++) {
+        uint32_t crc = crc32c_table_big_byte[n];
+        crc32c_table_big[0][n] = swap(crc);
+        for (unsigned k = 1; k < 8; k++) {
+            crc = crc32c_table_big_byte[crc & 0xff] ^ (crc >> 8);
+            crc32c_table_big[k][n] = swap(crc);
+        }
+    }
+}
+
+/* Compute a CRC-32C in software assuming a big-endian architecture,
+   constructing the required tables if that hasn't already been done. */
+uint32_t crc32c_sw_big(uint32_t crc, void const *buf, size_t len) {
+    unsigned char const *next = buf;
+
+    pthread_once(&crc32c_once_big, crc32c_init_sw_big);
+    crc = ~crc;
+    while (len && ((uintptr_t)next & 7) != 0) {
+        crc = crc32c_table_big_byte[(crc ^ *next++) & 0xff] ^ (crc >> 8);
+        len--;
+    }
+    if (len >= 8) {
+        uint64_t crcw = swap(crc);
+        do {
+            crcw ^= *(uint64_t const *)next;
+            crcw = crc32c_table_big[0][crcw & 0xff] ^
+                   crc32c_table_big[1][(crcw >> 8) & 0xff] ^
+                   crc32c_table_big[2][(crcw >> 16) & 0xff] ^
+                   crc32c_table_big[3][(crcw >> 24) & 0xff] ^
+                   crc32c_table_big[4][(crcw >> 32) & 0xff] ^
+                   crc32c_table_big[5][(crcw >> 40) & 0xff] ^
+                   crc32c_table_big[6][(crcw >> 48) & 0xff] ^
+                   crc32c_table_big[7][(crcw >> 56)];
+            next += 8;
+            len -= 8;
+        } while (len >= 8);
+        crc = swap(crcw);
+    }
+    while (len) {
+        crc = crc32c_table_big_byte[(crc ^ *next++) & 0xff] ^ (crc >> 8);
+        len--;
+    }
+    return ~crc;
+}
+
+/* Table-driven software CRC-32C.  This is about 15 times slower than using the
+   hardware instructions.  Determine the endianess of the processor and proceed
+   accordingly.  Ideally the endianess will be determined at compile time, in
+   which case the unused functions and tables for the other endianess will be
+   removed by the optimizer.  If not, then the proper routines and tables will
+   be used, even if the endianess is changed mid-stream.  (Yes, there are
+   processors that permit that -- go figure.) */
+uint32_t crc32c_sw(uint32_t crc, void const *buf, size_t len) {
+    static int const little = 1;
+    if (*(char const *)&little)
+        return crc32c_sw_little(crc, buf, len);
+    else
+        return crc32c_sw_big(crc, buf, len);
 }