libfrog/crc32.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Aug 8, 2011 Bob Pearson with help from Joakim Tjernlund and George Spelvin
   4  * cleaned up code to current version of sparse and added the slicing-by-8
   5  * algorithm to the closely similar existing slicing-by-4 algorithm.
   6  * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com>
   7  * Nicer crc32 functions/docs submitted by linux@horizon.com.  Thanks!
   8  * Code was from the public domain, copyright abandoned.  Code was
   9  * subsequently included in the kernel, thus was re-licensed under the
  10  * GNU GPL v2.
  11  * Oct 12, 2000 Matt Domsch <Matt_Domsch@dell.com>
  12  * Same crc32 function was used in 5 other places in the kernel.
  13  * I made one version, and deleted the others.
  14  * There are various incantations of crc32().  Some use a seed of 0 or ~0.
  15  * Some xor at the end with ~0.  The generic crc32() function takes
  16  * seed as an argument, and doesn't xor at the end.  Then individual
  17  * users can do whatever they need.
  18  *   drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0.
  19  *   fs/jffs2 uses seed 0, doesn't xor with ~0.
  20  *   fs/partitions/efi.c uses seed ~0, xor's with ~0.
  21  */
  22
  23 /* see: Documentation/crc32.txt for a description of algorithms */
  24
  25 /*
  26  * lifted from the 3.8-rc2 kernel source for xfsprogs. Killed CONFIG_X86
  27  * specific bits for just the generic algorithm. Also removed the big endian
  28  * version of the algorithm as XFS only uses the little endian CRC version to
  29  * match the hardware acceleration available on Intel CPUs.
  30  */
  31
  32 #include <inttypes.h>
  33 #include <asm/types.h>
  34 #include <sys/time.h>
  35 #include "platform_defs.h"
  36 /* For endian conversion routines */
  37 #include "xfs_arch.h"
  38 #include "crc32defs.h"
  39 #include "crc32c.h"
  40
  41 /* types specifc to this file */
  42 typedef __u8    u8;
  43 typedef __u16   u16;
  44 typedef __u32   u32;
  45 typedef __u32   u64;
  46 #define __pure
  47
  48 #if CRC_LE_BITS > 8
  49 # define tole(x) ((__force u32) __constant_cpu_to_le32(x))
  50 #else
  51 # define tole(x) (x)
  52 #endif
  53
  54 #include "crc32table.h"
  55
  56 #if CRC_LE_BITS > 8
  57
  58 /* implements slicing-by-4 or slicing-by-8 algorithm */
  59 static inline u32
  60 crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256])
  61 {
  62 #if __BYTE_ORDER == __LITTLE_ENDIAN
  63 #  define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8)
  64 #  define DO_CRC4 (t3[(q) & 255] ^ t2[(q >> 8) & 255] ^ \
  65                    t1[(q >> 16) & 255] ^ t0[(q >> 24) & 255])
  66 #  define DO_CRC8 (t7[(q) & 255] ^ t6[(q >> 8) & 255] ^ \
  67                    t5[(q >> 16) & 255] ^ t4[(q >> 24) & 255])
  68 # elif __BYTE_ORDER == __BIG_ENDIAN
  69 #  define DO_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
  70 #  define DO_CRC4 (t0[(q) & 255] ^ t1[(q >> 8) & 255] ^ \
  71                    t2[(q >> 16) & 255] ^ t3[(q >> 24) & 255])
  72 #  define DO_CRC8 (t4[(q) & 255] ^ t5[(q >> 8) & 255] ^ \
  73                    t6[(q >> 16) & 255] ^ t7[(q >> 24) & 255])
  74 # else
  75 #  error What endian are you?
  76 # endif
  77         const u32 *b;
  78         size_t    rem_len;
  79         const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3];
  80 # if CRC_LE_BITS != 32
  81         const u32 *t4 = tab[4], *t5 = tab[5], *t6 = tab[6], *t7 = tab[7];
  82 # endif
  83         u32 q;
  84
  85         /* Align it */
  86         if (((long)buf & 3) && len) {
  87                 do {
  88                         DO_CRC(*buf++);
  89                 } while ((--len) && ((long)buf)&3);
  90         }
  91
  92 # if CRC_LE_BITS == 32
  93         rem_len = len & 3;
  94         len = len >> 2;
  95 # else
  96         rem_len = len & 7;
  97         len = len >> 3;
  98 # endif
  99
 100         b = (const u32 *)buf;
 101         for (--b; len; --len) {
 102                 q = crc ^ *++b; /* use pre increment for speed */
 103 # if CRC_LE_BITS == 32
 104                 crc = DO_CRC4;
 105 # else
 106                 crc = DO_CRC8;
 107                 q = *++b;
 108                 crc ^= DO_CRC4;
 109 # endif
 110         }
 111         len = rem_len;
 112         /* And the last few bytes */
 113         if (len) {
 114                 u8 *p = (u8 *)(b + 1) - 1;
 115                 do {
 116                         DO_CRC(*++p); /* use pre increment for speed */
 117                 } while (--len);
 118         }
 119         return crc;
 120 #undef DO_CRC
 121 #undef DO_CRC4
 122 #undef DO_CRC8
 123 }
 124 #endif
 125
 126 /**
 127  * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32
 128  * @crc: seed value for computation.  ~0 for Ethernet, sometimes 0 for
 129  *      other uses, or the previous crc32 value if computing incrementally.
 130  * @p: pointer to buffer over which CRC is run
 131  * @len: length of buffer @p
 132  */
 133 static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p,
 134                                           size_t len, const u32 (*tab)[256],
 135                                           u32 polynomial)
 136 {
 137 #if CRC_LE_BITS == 1
 138         int i;
 139         while (len--) {
 140                 crc ^= *p++;
 141                 for (i = 0; i < 8; i++)
 142                         crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0);
 143         }
 144 # elif CRC_LE_BITS == 2
 145         while (len--) {
 146                 crc ^= *p++;
 147                 crc = (crc >> 2) ^ tab[0][crc & 3];
 148                 crc = (crc >> 2) ^ tab[0][crc & 3];
 149                 crc = (crc >> 2) ^ tab[0][crc & 3];
 150                 crc = (crc >> 2) ^ tab[0][crc & 3];
 151         }
 152 # elif CRC_LE_BITS == 4
 153         while (len--) {
 154                 crc ^= *p++;
 155                 crc = (crc >> 4) ^ tab[0][crc & 15];
 156                 crc = (crc >> 4) ^ tab[0][crc & 15];
 157         }
 158 # elif CRC_LE_BITS == 8
 159         /* aka Sarwate algorithm */
 160         while (len--) {
 161                 crc ^= *p++;
 162                 crc = (crc >> 8) ^ tab[0][crc & 255];
 163         }
 164 # else
 165         crc = (__force u32) cpu_to_le32(crc);
 166         crc = crc32_body(crc, p, len, tab);
 167         crc = le32_to_cpu((__force __le32)crc);
 168 #endif
 169         return crc;
 170 }
 171
 172 #if CRC_LE_BITS == 1
 173 u32 __pure crc32c_le(u32 crc, unsigned char const *p, size_t len)
 174 {
 175         return crc32_le_generic(crc, p, len, NULL, CRC32C_POLY_LE);
 176 }
 177 #else
 178 u32 __pure crc32c_le(u32 crc, unsigned char const *p, size_t len)
 179 {
 180         return crc32_le_generic(crc, p, len,
 181                         (const u32 (*)[256])crc32ctable_le, CRC32C_POLY_LE);
 182 }
 183 #endif
 184
 185
 186 #ifdef CRC32_SELFTEST
 187 # include "crc32cselftest.h"
 188
 189 /*
 190  * make sure we always return 0 for a successful test run, and non-zero for a
 191  * failed run. The build infrastructure is looking for this information to
 192  * determine whether to allow the build to proceed.
 193  */
 194 int main(int argc, char **argv)
 195 {
 196         int errors;
 197
 198         printf("CRC_LE_BITS = %d\n", CRC_LE_BITS);
 199
 200         errors = crc32c_test();
 201
 202         return errors != 0;
 203 }
 204 #endif /* CRC32_SELFTEST */