^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1) /*
78dff4189708d (Bob Pearson 2012-03-23 15:02:24 -0700 2) * Aug 8, 2011 Bob Pearson with help from Joakim Tjernlund and George Spelvin
78dff4189708d (Bob Pearson 2012-03-23 15:02:24 -0700 3) * cleaned up code to current version of sparse and added the slicing-by-8
78dff4189708d (Bob Pearson 2012-03-23 15:02:24 -0700 4) * algorithm to the closely similar existing slicing-by-4 algorithm.
78dff4189708d (Bob Pearson 2012-03-23 15:02:24 -0700 5) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 6) * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com>
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 7) * Nicer crc32 functions/docs submitted by linux@horizon.com. Thanks!
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 8) * Code was from the public domain, copyright abandoned. Code was
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 9) * subsequently included in the kernel, thus was re-licensed under the
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 10) * GNU GPL v2.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 11) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 12) * Oct 12, 2000 Matt Domsch <Matt_Domsch@dell.com>
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 13) * Same crc32 function was used in 5 other places in the kernel.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 14) * I made one version, and deleted the others.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 15) * There are various incantations of crc32(). Some use a seed of 0 or ~0.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 16) * Some xor at the end with ~0. The generic crc32() function takes
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 17) * seed as an argument, and doesn't xor at the end. Then individual
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 18) * users can do whatever they need.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 19) * drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 20) * fs/jffs2 uses seed 0, doesn't xor with ~0.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 21) * fs/partitions/efi.c uses seed ~0, xor's with ~0.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 22) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 23) * This source code is licensed under the GNU General Public License,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 24) * Version 2. See the file COPYING for more details.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 25) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 26)
8e2a46a40fa76 (Mauro Carvalho Chehab 2020-06-15 08:50:25 +0200 27) /* see: Documentation/staging/crc32.rst for a description of algorithms */
fbedceb100664 (Bob Pearson 2012-03-23 15:02:22 -0700 28)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 29) #include <linux/crc32.h>
1fb2e3f276dda (Krzysztof Kozlowski 2018-07-17 18:05:36 +0200 30) #include <linux/crc32poly.h>
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 31) #include <linux/module.h>
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 32) #include <linux/types.h>
cc0ac1999589c (Daniel Borkmann 2013-11-04 17:10:26 +0100 33) #include <linux/sched.h>
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 34) #include "crc32defs.h"
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 35)
9a1dbf6a29694 (Bob Pearson 2012-03-23 15:02:23 -0700 36) #if CRC_LE_BITS > 8
38b4fe5fcc869 (Fabian Frederick 2014-06-04 16:11:56 -0700 37) # define tole(x) ((__force u32) cpu_to_le32(x))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 38) #else
4f2a9463d1851 (Joakim Tjernlund 2010-03-05 13:43:55 -0800 39) # define tole(x) (x)
4f2a9463d1851 (Joakim Tjernlund 2010-03-05 13:43:55 -0800 40) #endif
4f2a9463d1851 (Joakim Tjernlund 2010-03-05 13:43:55 -0800 41)
9a1dbf6a29694 (Bob Pearson 2012-03-23 15:02:23 -0700 42) #if CRC_BE_BITS > 8
38b4fe5fcc869 (Fabian Frederick 2014-06-04 16:11:56 -0700 43) # define tobe(x) ((__force u32) cpu_to_be32(x))
4f2a9463d1851 (Joakim Tjernlund 2010-03-05 13:43:55 -0800 44) #else
4f2a9463d1851 (Joakim Tjernlund 2010-03-05 13:43:55 -0800 45) # define tobe(x) (x)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 46) #endif
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 47)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 48) #include "crc32table.h"
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 49)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 50) MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 51) MODULE_DESCRIPTION("Various CRC32 calculations");
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 52) MODULE_LICENSE("GPL");
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 53)
9a1dbf6a29694 (Bob Pearson 2012-03-23 15:02:23 -0700 54) #if CRC_LE_BITS > 8 || CRC_BE_BITS > 8
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 55)
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 56) /* implements slicing-by-4 or slicing-by-8 algorithm */
d8f1c4778e957 (George Spelvin 2014-06-23 15:11:56 +0200 57) static inline u32 __pure
836e2af92503f (Joakim Tjernlund 2010-05-24 14:33:31 -0700 58) crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256])
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 59) {
0d2daf5cc858b (Andrew Morton 2010-05-25 23:43:03 -0700 60) # ifdef __LITTLE_ENDIAN
5742332dea556 (Joakim Tjernlund 2012-01-10 15:10:18 -0800 61) # define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8)
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 62) # define DO_CRC4 (t3[(q) & 255] ^ t2[(q >> 8) & 255] ^ \
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 63) t1[(q >> 16) & 255] ^ t0[(q >> 24) & 255])
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 64) # define DO_CRC8 (t7[(q) & 255] ^ t6[(q >> 8) & 255] ^ \
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 65) t5[(q >> 16) & 255] ^ t4[(q >> 24) & 255])
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 66) # else
5742332dea556 (Joakim Tjernlund 2012-01-10 15:10:18 -0800 67) # define DO_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 68) # define DO_CRC4 (t0[(q) & 255] ^ t1[(q >> 8) & 255] ^ \
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 69) t2[(q >> 16) & 255] ^ t3[(q >> 24) & 255])
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 70) # define DO_CRC8 (t4[(q) & 255] ^ t5[(q >> 8) & 255] ^ \
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 71) t6[(q >> 16) & 255] ^ t7[(q >> 24) & 255])
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 72) # endif
4f2a9463d1851 (Joakim Tjernlund 2010-03-05 13:43:55 -0800 73) const u32 *b;
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 74) size_t rem_len;
0292c497b6b94 (Bob Pearson 2012-03-23 15:02:24 -0700 75) # ifdef CONFIG_X86
0292c497b6b94 (Bob Pearson 2012-03-23 15:02:24 -0700 76) size_t i;
0292c497b6b94 (Bob Pearson 2012-03-23 15:02:24 -0700 77) # endif
5742332dea556 (Joakim Tjernlund 2012-01-10 15:10:18 -0800 78) const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3];
49ac572b93832 (Thiago Rafael Becker 2012-07-30 14:41:26 -0700 79) # if CRC_LE_BITS != 32
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 80) const u32 *t4 = tab[4], *t5 = tab[5], *t6 = tab[6], *t7 = tab[7];
49ac572b93832 (Thiago Rafael Becker 2012-07-30 14:41:26 -0700 81) # endif
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 82) u32 q;
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 83)
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 84) /* Align it */
4f2a9463d1851 (Joakim Tjernlund 2010-03-05 13:43:55 -0800 85) if (unlikely((long)buf & 3 && len)) {
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 86) do {
4f2a9463d1851 (Joakim Tjernlund 2010-03-05 13:43:55 -0800 87) DO_CRC(*buf++);
4f2a9463d1851 (Joakim Tjernlund 2010-03-05 13:43:55 -0800 88) } while ((--len) && ((long)buf)&3);
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 89) }
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 90)
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 91) # if CRC_LE_BITS == 32
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 92) rem_len = len & 3;
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 93) len = len >> 2;
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 94) # else
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 95) rem_len = len & 7;
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 96) len = len >> 3;
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 97) # endif
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 98)
4f2a9463d1851 (Joakim Tjernlund 2010-03-05 13:43:55 -0800 99) b = (const u32 *)buf;
0292c497b6b94 (Bob Pearson 2012-03-23 15:02:24 -0700 100) # ifdef CONFIG_X86
0292c497b6b94 (Bob Pearson 2012-03-23 15:02:24 -0700 101) --b;
0292c497b6b94 (Bob Pearson 2012-03-23 15:02:24 -0700 102) for (i = 0; i < len; i++) {
0292c497b6b94 (Bob Pearson 2012-03-23 15:02:24 -0700 103) # else
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 104) for (--b; len; --len) {
0292c497b6b94 (Bob Pearson 2012-03-23 15:02:24 -0700 105) # endif
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 106) q = crc ^ *++b; /* use pre increment for speed */
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 107) # if CRC_LE_BITS == 32
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 108) crc = DO_CRC4;
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 109) # else
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 110) crc = DO_CRC8;
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 111) q = *++b;
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 112) crc ^= DO_CRC4;
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 113) # endif
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 114) }
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 115) len = rem_len;
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 116) /* And the last few bytes */
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 117) if (len) {
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 118) u8 *p = (u8 *)(b + 1) - 1;
0292c497b6b94 (Bob Pearson 2012-03-23 15:02:24 -0700 119) # ifdef CONFIG_X86
0292c497b6b94 (Bob Pearson 2012-03-23 15:02:24 -0700 120) for (i = 0; i < len; i++)
0292c497b6b94 (Bob Pearson 2012-03-23 15:02:24 -0700 121) DO_CRC(*++p); /* use pre increment for speed */
0292c497b6b94 (Bob Pearson 2012-03-23 15:02:24 -0700 122) # else
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 123) do {
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 124) DO_CRC(*++p); /* use pre increment for speed */
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 125) } while (--len);
0292c497b6b94 (Bob Pearson 2012-03-23 15:02:24 -0700 126) # endif
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 127) }
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 128) return crc;
4f2a9463d1851 (Joakim Tjernlund 2010-03-05 13:43:55 -0800 129) #undef DO_CRC
836e2af92503f (Joakim Tjernlund 2010-05-24 14:33:31 -0700 130) #undef DO_CRC4
324eb0f17d9dc (Bob Pearson 2012-03-23 15:02:24 -0700 131) #undef DO_CRC8
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 132) }
ddcaccbc17d7d (Joakim Tjernlund 2009-12-14 18:01:33 -0800 133) #endif
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 134)
6e95fcaa42e50 (Daniel Borkmann 2013-10-30 11:50:49 +0100 135)
2f72100c01dd3 (Randy Dunlap 2006-06-25 05:48:59 -0700 136) /**
f2e1d2ac344bc (Gu Zheng 2013-09-11 14:23:52 -0700 137) * crc32_le_generic() - Calculate bitwise little-endian Ethernet AUTODIN II
f2e1d2ac344bc (Gu Zheng 2013-09-11 14:23:52 -0700 138) * CRC32/CRC32C
f2e1d2ac344bc (Gu Zheng 2013-09-11 14:23:52 -0700 139) * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for other
f2e1d2ac344bc (Gu Zheng 2013-09-11 14:23:52 -0700 140) * uses, or the previous crc32/crc32c value if computing incrementally.
f2e1d2ac344bc (Gu Zheng 2013-09-11 14:23:52 -0700 141) * @p: pointer to buffer over which CRC32/CRC32C is run
2f72100c01dd3 (Randy Dunlap 2006-06-25 05:48:59 -0700 142) * @len: length of buffer @p
f2e1d2ac344bc (Gu Zheng 2013-09-11 14:23:52 -0700 143) * @tab: little-endian Ethernet table
f2e1d2ac344bc (Gu Zheng 2013-09-11 14:23:52 -0700 144) * @polynomial: CRC32/CRC32c LE polynomial
2f72100c01dd3 (Randy Dunlap 2006-06-25 05:48:59 -0700 145) */
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 146) static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p,
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 147) size_t len, const u32 (*tab)[256],
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 148) u32 polynomial)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 149) {
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 150) #if CRC_LE_BITS == 1
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 151) int i;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 152) while (len--) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 153) crc ^= *p++;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 154) for (i = 0; i < 8; i++)
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 155) crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 156) }
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 157) # elif CRC_LE_BITS == 2
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 158) while (len--) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 159) crc ^= *p++;
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 160) crc = (crc >> 2) ^ tab[0][crc & 3];
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 161) crc = (crc >> 2) ^ tab[0][crc & 3];
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 162) crc = (crc >> 2) ^ tab[0][crc & 3];
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 163) crc = (crc >> 2) ^ tab[0][crc & 3];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 164) }
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 165) # elif CRC_LE_BITS == 4
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 166) while (len--) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 167) crc ^= *p++;
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 168) crc = (crc >> 4) ^ tab[0][crc & 15];
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 169) crc = (crc >> 4) ^ tab[0][crc & 15];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 170) }
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 171) # elif CRC_LE_BITS == 8
9a1dbf6a29694 (Bob Pearson 2012-03-23 15:02:23 -0700 172) /* aka Sarwate algorithm */
9a1dbf6a29694 (Bob Pearson 2012-03-23 15:02:23 -0700 173) while (len--) {
9a1dbf6a29694 (Bob Pearson 2012-03-23 15:02:23 -0700 174) crc ^= *p++;
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 175) crc = (crc >> 8) ^ tab[0][crc & 255];
9a1dbf6a29694 (Bob Pearson 2012-03-23 15:02:23 -0700 176) }
9a1dbf6a29694 (Bob Pearson 2012-03-23 15:02:23 -0700 177) # else
ce4320ddda4c2 (Bob Pearson 2012-03-23 15:02:23 -0700 178) crc = (__force u32) __cpu_to_le32(crc);
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 179) crc = crc32_body(crc, p, len, tab);
ce4320ddda4c2 (Bob Pearson 2012-03-23 15:02:23 -0700 180) crc = __le32_to_cpu((__force __le32)crc);
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 181) #endif
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 182) return crc;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 183) }
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 184)
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 185) #if CRC_LE_BITS == 1
9784d82db3eb3 (Ard Biesheuvel 2018-08-27 13:02:42 +0200 186) u32 __pure __weak crc32_le(u32 crc, unsigned char const *p, size_t len)
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 187) {
e37f2f93afe59 (Krzysztof Kozlowski 2018-07-17 18:05:37 +0200 188) return crc32_le_generic(crc, p, len, NULL, CRC32_POLY_LE);
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 189) }
9784d82db3eb3 (Ard Biesheuvel 2018-08-27 13:02:42 +0200 190) u32 __pure __weak __crc32c_le(u32 crc, unsigned char const *p, size_t len)
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 191) {
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 192) return crc32_le_generic(crc, p, len, NULL, CRC32C_POLY_LE);
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 193) }
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 194) #else
9784d82db3eb3 (Ard Biesheuvel 2018-08-27 13:02:42 +0200 195) u32 __pure __weak crc32_le(u32 crc, unsigned char const *p, size_t len)
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 196) {
8f243af42adef (Joe Mario 2012-10-04 17:12:15 -0700 197) return crc32_le_generic(crc, p, len,
e37f2f93afe59 (Krzysztof Kozlowski 2018-07-17 18:05:37 +0200 198) (const u32 (*)[256])crc32table_le, CRC32_POLY_LE);
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 199) }
9784d82db3eb3 (Ard Biesheuvel 2018-08-27 13:02:42 +0200 200) u32 __pure __weak __crc32c_le(u32 crc, unsigned char const *p, size_t len)
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 201) {
8f243af42adef (Joe Mario 2012-10-04 17:12:15 -0700 202) return crc32_le_generic(crc, p, len,
8f243af42adef (Joe Mario 2012-10-04 17:12:15 -0700 203) (const u32 (*)[256])crc32ctable_le, CRC32C_POLY_LE);
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 204) }
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 205) #endif
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 206) EXPORT_SYMBOL(crc32_le);
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 207) EXPORT_SYMBOL(__crc32c_le);
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 208)
ff98e20ef2081 (Miguel Ojeda 2019-01-24 15:59:11 +0100 209) u32 __pure crc32_le_base(u32, unsigned char const *, size_t) __alias(crc32_le);
ff98e20ef2081 (Miguel Ojeda 2019-01-24 15:59:11 +0100 210) u32 __pure __crc32c_le_base(u32, unsigned char const *, size_t) __alias(__crc32c_le);
9784d82db3eb3 (Ard Biesheuvel 2018-08-27 13:02:42 +0200 211)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 212) /*
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 213) * This multiplies the polynomials x and y modulo the given modulus.
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 214) * This follows the "little-endian" CRC convention that the lsbit
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 215) * represents the highest power of x, and the msbit represents x^0.
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 216) */
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 217) static u32 __attribute_const__ gf2_multiply(u32 x, u32 y, u32 modulus)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 218) {
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 219) u32 product = x & 1 ? y : 0;
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 220) int i;
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 221)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 222) for (i = 0; i < 31; i++) {
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 223) product = (product >> 1) ^ (product & 1 ? modulus : 0);
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 224) x >>= 1;
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 225) product ^= x & 1 ? y : 0;
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 226) }
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 227)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 228) return product;
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 229) }
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 230)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 231) /**
8a29896a6e31c (Randy Dunlap 2017-09-08 16:35:55 -0700 232) * crc32_generic_shift - Append @len 0 bytes to crc, in logarithmic time
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 233) * @crc: The original little-endian CRC (i.e. lsbit is x^31 coefficient)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 234) * @len: The number of bytes. @crc is multiplied by x^(8*@len)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 235) * @polynomial: The modulus used to reduce the result to 32 bits.
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 236) *
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 237) * It's possible to parallelize CRC computations by computing a CRC
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 238) * over separate ranges of a buffer, then summing them.
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 239) * This shifts the given CRC by 8*len bits (i.e. produces the same effect
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 240) * as appending len bytes of zero to the data), in time proportional
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 241) * to log(len).
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 242) */
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 243) static u32 __attribute_const__ crc32_generic_shift(u32 crc, size_t len,
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 244) u32 polynomial)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 245) {
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 246) u32 power = polynomial; /* CRC of x^32 */
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 247) int i;
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 248)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 249) /* Shift up to 32 bits in the simple linear way */
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 250) for (i = 0; i < 8 * (int)(len & 3); i++)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 251) crc = (crc >> 1) ^ (crc & 1 ? polynomial : 0);
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 252)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 253) len >>= 2;
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 254) if (!len)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 255) return crc;
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 256)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 257) for (;;) {
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 258) /* "power" is x^(2^i), modulo the polynomial */
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 259) if (len & 1)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 260) crc = gf2_multiply(crc, power, polynomial);
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 261)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 262) len >>= 1;
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 263) if (!len)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 264) break;
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 265)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 266) /* Square power, advancing to x^(2^(i+1)) */
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 267) power = gf2_multiply(power, power, polynomial);
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 268) }
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 269)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 270) return crc;
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 271) }
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 272)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 273) u32 __attribute_const__ crc32_le_shift(u32 crc, size_t len)
6e95fcaa42e50 (Daniel Borkmann 2013-10-30 11:50:49 +0100 274) {
e37f2f93afe59 (Krzysztof Kozlowski 2018-07-17 18:05:37 +0200 275) return crc32_generic_shift(crc, len, CRC32_POLY_LE);
6e95fcaa42e50 (Daniel Borkmann 2013-10-30 11:50:49 +0100 276) }
6e95fcaa42e50 (Daniel Borkmann 2013-10-30 11:50:49 +0100 277)
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 278) u32 __attribute_const__ __crc32c_le_shift(u32 crc, size_t len)
6e95fcaa42e50 (Daniel Borkmann 2013-10-30 11:50:49 +0100 279) {
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 280) return crc32_generic_shift(crc, len, CRC32C_POLY_LE);
6e95fcaa42e50 (Daniel Borkmann 2013-10-30 11:50:49 +0100 281) }
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 282) EXPORT_SYMBOL(crc32_le_shift);
6d514b4e7737a (George Spelvin 2014-06-23 15:11:54 +0200 283) EXPORT_SYMBOL(__crc32c_le_shift);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 284)
2f72100c01dd3 (Randy Dunlap 2006-06-25 05:48:59 -0700 285) /**
f2e1d2ac344bc (Gu Zheng 2013-09-11 14:23:52 -0700 286) * crc32_be_generic() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32
2f72100c01dd3 (Randy Dunlap 2006-06-25 05:48:59 -0700 287) * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for
2f72100c01dd3 (Randy Dunlap 2006-06-25 05:48:59 -0700 288) * other uses, or the previous crc32 value if computing incrementally.
f2e1d2ac344bc (Gu Zheng 2013-09-11 14:23:52 -0700 289) * @p: pointer to buffer over which CRC32 is run
2f72100c01dd3 (Randy Dunlap 2006-06-25 05:48:59 -0700 290) * @len: length of buffer @p
f2e1d2ac344bc (Gu Zheng 2013-09-11 14:23:52 -0700 291) * @tab: big-endian Ethernet table
f2e1d2ac344bc (Gu Zheng 2013-09-11 14:23:52 -0700 292) * @polynomial: CRC32 BE polynomial
2f72100c01dd3 (Randy Dunlap 2006-06-25 05:48:59 -0700 293) */
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 294) static inline u32 __pure crc32_be_generic(u32 crc, unsigned char const *p,
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 295) size_t len, const u32 (*tab)[256],
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 296) u32 polynomial)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 297) {
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 298) #if CRC_BE_BITS == 1
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 299) int i;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 300) while (len--) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 301) crc ^= *p++ << 24;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 302) for (i = 0; i < 8; i++)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 303) crc =
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 304) (crc << 1) ^ ((crc & 0x80000000) ? polynomial :
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 305) 0);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 306) }
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 307) # elif CRC_BE_BITS == 2
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 308) while (len--) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 309) crc ^= *p++ << 24;
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 310) crc = (crc << 2) ^ tab[0][crc >> 30];
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 311) crc = (crc << 2) ^ tab[0][crc >> 30];
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 312) crc = (crc << 2) ^ tab[0][crc >> 30];
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 313) crc = (crc << 2) ^ tab[0][crc >> 30];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 314) }
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 315) # elif CRC_BE_BITS == 4
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 316) while (len--) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 317) crc ^= *p++ << 24;
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 318) crc = (crc << 4) ^ tab[0][crc >> 28];
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 319) crc = (crc << 4) ^ tab[0][crc >> 28];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 320) }
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 321) # elif CRC_BE_BITS == 8
9a1dbf6a29694 (Bob Pearson 2012-03-23 15:02:23 -0700 322) while (len--) {
9a1dbf6a29694 (Bob Pearson 2012-03-23 15:02:23 -0700 323) crc ^= *p++ << 24;
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 324) crc = (crc << 8) ^ tab[0][crc >> 24];
9a1dbf6a29694 (Bob Pearson 2012-03-23 15:02:23 -0700 325) }
9a1dbf6a29694 (Bob Pearson 2012-03-23 15:02:23 -0700 326) # else
ce4320ddda4c2 (Bob Pearson 2012-03-23 15:02:23 -0700 327) crc = (__force u32) __cpu_to_be32(crc);
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 328) crc = crc32_body(crc, p, len, tab);
ce4320ddda4c2 (Bob Pearson 2012-03-23 15:02:23 -0700 329) crc = __be32_to_cpu((__force __be32)crc);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 330) # endif
60e58d5c9d8d6 (Bob Pearson 2012-03-23 15:02:22 -0700 331) return crc;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 332) }
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 333)
904542dc56524 (Tobias Jordan 2020-10-15 20:11:38 -0700 334) #if CRC_BE_BITS == 1
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 335) u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 336) {
e37f2f93afe59 (Krzysztof Kozlowski 2018-07-17 18:05:37 +0200 337) return crc32_be_generic(crc, p, len, NULL, CRC32_POLY_BE);
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 338) }
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 339) #else
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 340) u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 341) {
8f243af42adef (Joe Mario 2012-10-04 17:12:15 -0700 342) return crc32_be_generic(crc, p, len,
e37f2f93afe59 (Krzysztof Kozlowski 2018-07-17 18:05:37 +0200 343) (const u32 (*)[256])crc32table_be, CRC32_POLY_BE);
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 344) }
46c5801eaf86e (Darrick J. Wong 2012-03-23 15:02:25 -0700 345) #endif
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 346) EXPORT_SYMBOL(crc32_be);
VisionFive2 Linux kernel
StarFive Tech Linux Kernel for VisionFive (JH7110) boards (mirror)
More than 9999 Commits
32 Branches
54 Tags