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
34MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
35MODULE_DESCRIPTION("Various CRC32 calculations");
36MODULE_LICENSE("GPL");
37
38u32 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}
44EXPORT_SYMBOL(crc32_le_base);
45
46u32 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}
52EXPORT_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 */
59static 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 */
85static 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
114u32 crc32_le_shift(u32 crc, size_t len)
115{
116 return crc32_generic_shift(crc, len, CRC32_POLY_LE);
117}
118EXPORT_SYMBOL(crc32_le_shift);
119
120u32 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}
126EXPORT_SYMBOL(crc32_be_base);
127

Provided by KDAB

Privacy Policy
Improve your Profiling and Debugging skills
Find out more

source code of linux/lib/crc32.c