1 | // SPDX-License-Identifier: GPL-2.0-only |
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 | * |
7 | * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com> |
8 | * Nicer crc32 functions/docs submitted by linux@horizon.com. Thanks! |
9 | * Code was from the public domain, copyright abandoned. Code was |
10 | * subsequently included in the kernel, thus was re-licensed under the |
11 | * GNU GPL v2. |
12 | * |
13 | * Oct 12, 2000 Matt Domsch <Matt_Domsch@dell.com> |
14 | * Same crc32 function was used in 5 other places in the kernel. |
15 | * I made one version, and deleted the others. |
16 | * There are various incantations of crc32(). Some use a seed of 0 or ~0. |
17 | * Some xor at the end with ~0. The generic crc32() function takes |
18 | * seed as an argument, and doesn't xor at the end. Then individual |
19 | * users can do whatever they need. |
20 | * drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0. |
21 | * fs/jffs2 uses seed 0, doesn't xor with ~0. |
22 | * fs/partitions/efi.c uses seed ~0, xor's with ~0. |
23 | */ |
24 | |
25 | /* see: Documentation/staging/crc32.rst for a description of algorithms */ |
26 | |
27 | #include <linux/crc32.h> |
28 | #include <linux/crc32poly.h> |
29 | #include <linux/module.h> |
30 | #include <linux/types.h> |
31 | |
32 | #include "crc32table.h" |
33 | |
34 | MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>" ); |
35 | MODULE_DESCRIPTION("Various CRC32 calculations" ); |
36 | MODULE_LICENSE("GPL" ); |
37 | |
38 | u32 crc32_le_base(u32 crc, const u8 *p, size_t len) |
39 | { |
40 | while (len--) |
41 | crc = (crc >> 8) ^ crc32table_le[(crc & 255) ^ *p++]; |
42 | return crc; |
43 | } |
44 | EXPORT_SYMBOL(crc32_le_base); |
45 | |
46 | u32 crc32c_base(u32 crc, const u8 *p, size_t len) |
47 | { |
48 | while (len--) |
49 | crc = (crc >> 8) ^ crc32ctable_le[(crc & 255) ^ *p++]; |
50 | return crc; |
51 | } |
52 | EXPORT_SYMBOL(crc32c_base); |
53 | |
54 | /* |
55 | * This multiplies the polynomials x and y modulo the given modulus. |
56 | * This follows the "little-endian" CRC convention that the lsbit |
57 | * represents the highest power of x, and the msbit represents x^0. |
58 | */ |
59 | static u32 gf2_multiply(u32 x, u32 y, u32 modulus) |
60 | { |
61 | u32 product = x & 1 ? y : 0; |
62 | int i; |
63 | |
64 | for (i = 0; i < 31; i++) { |
65 | product = (product >> 1) ^ (product & 1 ? modulus : 0); |
66 | x >>= 1; |
67 | product ^= x & 1 ? y : 0; |
68 | } |
69 | |
70 | return product; |
71 | } |
72 | |
73 | /** |
74 | * crc32_generic_shift - Append @len 0 bytes to crc, in logarithmic time |
75 | * @crc: The original little-endian CRC (i.e. lsbit is x^31 coefficient) |
76 | * @len: The number of bytes. @crc is multiplied by x^(8*@len) |
77 | * @polynomial: The modulus used to reduce the result to 32 bits. |
78 | * |
79 | * It's possible to parallelize CRC computations by computing a CRC |
80 | * over separate ranges of a buffer, then summing them. |
81 | * This shifts the given CRC by 8*len bits (i.e. produces the same effect |
82 | * as appending len bytes of zero to the data), in time proportional |
83 | * to log(len). |
84 | */ |
85 | static u32 crc32_generic_shift(u32 crc, size_t len, u32 polynomial) |
86 | { |
87 | u32 power = polynomial; /* CRC of x^32 */ |
88 | int i; |
89 | |
90 | /* Shift up to 32 bits in the simple linear way */ |
91 | for (i = 0; i < 8 * (int)(len & 3); i++) |
92 | crc = (crc >> 1) ^ (crc & 1 ? polynomial : 0); |
93 | |
94 | len >>= 2; |
95 | if (!len) |
96 | return crc; |
97 | |
98 | for (;;) { |
99 | /* "power" is x^(2^i), modulo the polynomial */ |
100 | if (len & 1) |
101 | crc = gf2_multiply(x: crc, y: power, modulus: polynomial); |
102 | |
103 | len >>= 1; |
104 | if (!len) |
105 | break; |
106 | |
107 | /* Square power, advancing to x^(2^(i+1)) */ |
108 | power = gf2_multiply(x: power, y: power, modulus: polynomial); |
109 | } |
110 | |
111 | return crc; |
112 | } |
113 | |
114 | u32 crc32_le_shift(u32 crc, size_t len) |
115 | { |
116 | return crc32_generic_shift(crc, len, CRC32_POLY_LE); |
117 | } |
118 | EXPORT_SYMBOL(crc32_le_shift); |
119 | |
120 | u32 crc32_be_base(u32 crc, const u8 *p, size_t len) |
121 | { |
122 | while (len--) |
123 | crc = (crc << 8) ^ crc32table_be[(crc >> 24) ^ *p++]; |
124 | return crc; |
125 | } |
126 | EXPORT_SYMBOL(crc32_be_base); |
127 | |