1 /* cksum -- calculate and print POSIX checksums and sizes of files
2 Copyright (C) 1992-2023 Free Software Foundation, Inc.
3
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <https://www.gnu.org/licenses/>. */
16
17 /* Written by Q. Frank Xia, qx@math.columbia.edu.
18 Cosmetic changes and reorganization by David MacKenzie, djm@gnu.ai.mit.edu.
19
20 Usage: cksum [file...]
21
22 The code segment between "#ifdef CRCTAB" and "#else" is the code
23 which calculates the "crctab". It is included for those who want
24 verify the correctness of the "crctab". To recreate the "crctab",
25 do something like the following:
26
27 cc -I../lib -DCRCTAB -o crctab cksum.c
28 crctab > crctab.c
29
30 This software is compatible with neither the System V nor the BSD
31 'sum' program. It is supposed to conform to POSIX, except perhaps
32 for foreign language support. Any inconsistency with the standard
33 (other than foreign language support) is a bug. */
34
35 #include <config.h>
36
37 #include <stdio.h>
38 #include <sys/types.h>
39 #include <stdint.h>
40 #include "system.h"
41
42 #include <byteswap.h>
43 #ifdef WORDS_BIGENDIAN
44 # define SWAP(n) (n)
45 #else
46 # define SWAP(n) bswap_32 (n)
47 #endif
48
49 #ifdef CRCTAB
50
51 # define BIT(x) ((uint_fast32_t) 1 << (x))
52 # define SBIT BIT (31)
53
54 /* The generating polynomial is
55
56 32 26 23 22 16 12 11 10 8 7 5 4 2 1
57 G(X)=X + X + X + X + X + X + X + X + X + X + X + X + X + X + 1
58
59 The i bit in GEN is set if X^i is a summand of G(X) except X^32. */
60
61 # define GEN (BIT (26) | BIT (23) | BIT (22) | BIT (16) | BIT (12) \
62 | BIT (11) | BIT (10) | BIT (8) | BIT (7) | BIT (5) \
63 | BIT (4) | BIT (2) | BIT (1) | BIT (0))
64
65 static uint_fast32_t r[8];
66
67 static void
68 fill_r (void)
69 {
70 r[0] = GEN;
71 for (int i = 1; i < 8; i++)
72 r[i] = (r[i - 1] << 1) ^ ((r[i - 1] & SBIT) ? GEN : 0);
73 }
74
75 static uint_fast32_t
76 crc_remainder (int m)
77 {
78 uint_fast32_t rem = 0;
79
80 for (int i = 0; i < 8; i++)
81 if (BIT (i) & m)
82 rem ^= r[i];
83
84 return rem & 0xFFFFFFFF; /* Make it run on 64-bit machine. */
85 }
86
87 int
88 main (void)
89 {
90 int i;
91 static uint_fast32_t crctab[8][256];
92
93 fill_r ();
94
95 for (i = 0; i < 256; i++)
96 {
97 crctab[0][i] = crc_remainder (i);
98 }
99
100 /* CRC(0x11 0x22 0x33 0x44)
101 is equal to
102 CRC(0x11 0x00 0x00 0x00) XOR CRC(0x22 0x00 0x00) XOR
103 CRC(0x33 0x00) XOR CRC(0x44)
104 We precompute the CRC values for the offset values into
105 separate CRC tables. We can then use them to speed up
106 CRC calculation by processing multiple bytes at the time. */
107 for (i = 0; i < 256; i++)
108 {
109 uint32_t crc = 0;
110
111 crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ (i & 0xFF)) & 0xFF];
112 for (idx_t offset = 1; offset < 8; offset++)
113 {
114 crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ 0x00) & 0xFF];
115 crctab[offset][i] = crc;
116 }
117 }
118
119 printf ("#include <config.h>\n");
120 printf ("#include <stdint.h>\n");
121 printf ("\nuint_fast32_t const crctab[8][256] = {\n");
122 for (int y = 0; y < 8; y++)
123 {
124 printf ("{\n 0x%08x", crctab[y][0]);
125 for (i = 0; i < 51; i++)
126 {
127 printf (",\n 0x%08x, 0x%08x, 0x%08x, 0x%08x, 0x%08x",
128 crctab[y][i * 5 + 1], crctab[y][i * 5 + 2],
129 crctab[y][i * 5 + 3], crctab[y][i * 5 + 4],
130 crctab[y][i * 5 + 5]);
131 }
132 printf ("\n},\n");
133 }
134 printf ("};\n");
135 return EXIT_SUCCESS;
136 }
137
138 #else /* !CRCTAB */
139
140 # include "cksum.h"
141
142 /* Number of bytes to read at once. */
143 # define BUFLEN (1 << 16)
144
145 # if USE_PCLMUL_CRC32
146 static bool
147 pclmul_supported (void)
148 {
149 bool pclmul_enabled = (0 < __builtin_cpu_supports ("pclmul")
150 && 0 < __builtin_cpu_supports ("avx"));
151
152 if (cksum_debug)
153 error (0, 0, "%s",
154 (pclmul_enabled
155 ? _("using pclmul hardware support")
156 : _("pclmul support not detected")));
157
158 return pclmul_enabled;
159 }
160 # endif /* USE_PCLMUL_CRC32 */
161
162 static bool
163 cksum_slice8 (FILE *fp, uint_fast32_t *crc_out, uintmax_t *length_out)
164 {
165 uint32_t buf[BUFLEN / sizeof (uint32_t)];
166 uint_fast32_t crc = 0;
167 uintmax_t length = 0;
168 size_t bytes_read;
169
170 if (!fp || !crc_out || !length_out)
171 return false;
172
173 while ((bytes_read = fread (buf, 1, BUFLEN, fp)) > 0)
174 {
175 uint32_t *datap;
176
177 if (length + bytes_read < length)
178 {
179 errno = EOVERFLOW;
180 return false;
181 }
182 length += bytes_read;
183
184 /* Process multiples of 8 bytes */
185 datap = (uint32_t *)buf;
186 while (bytes_read >= 8)
187 {
188 uint32_t first = *datap++, second = *datap++;
189 crc ^= SWAP (first);
190 second = SWAP (second);
191 crc = (crctab[7][(crc >> 24) & 0xFF]
192 ^ crctab[6][(crc >> 16) & 0xFF]
193 ^ crctab[5][(crc >> 8) & 0xFF]
194 ^ crctab[4][(crc) & 0xFF]
195 ^ crctab[3][(second >> 24) & 0xFF]
196 ^ crctab[2][(second >> 16) & 0xFF]
197 ^ crctab[1][(second >> 8) & 0xFF]
198 ^ crctab[0][(second) & 0xFF]);
199 bytes_read -= 8;
200 }
201
202 /* And finish up last 0-7 bytes in a byte by byte fashion */
203 unsigned char *cp = (unsigned char *)datap;
204 while (bytes_read--)
205 crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ *cp++) & 0xFF];
206 if (feof (fp))
207 break;
208 }
209
210 *crc_out = crc;
211 *length_out = length;
212
213 return !ferror (fp);
214 }
215
216 /* Calculate the checksum and length in bytes of stream STREAM.
217 Return -1 on error, 0 on success. */
218
219 int
220 crc_sum_stream (FILE *stream, void *resstream, uintmax_t *length)
221 {
222 uintmax_t total_bytes = 0;
223 uint_fast32_t crc = 0;
224
225 # if USE_PCLMUL_CRC32
226 static bool (*cksum_fp) (FILE *, uint_fast32_t *, uintmax_t *);
227 if (! cksum_fp)
228 cksum_fp = pclmul_supported () ? cksum_pclmul : cksum_slice8;
229 # else
230 bool (*cksum_fp) (FILE *, uint_fast32_t *, uintmax_t *) = cksum_slice8;
231 # endif
232
233 if (! cksum_fp (stream, &crc, &total_bytes))
234 return -1;
235
236 *length = total_bytes;
237
238 for (; total_bytes; total_bytes >>= 8)
239 crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ total_bytes) & 0xFF];
240 crc = ~crc & 0xFFFFFFFF;
241
242 unsigned int crc_out = crc;
243 memcpy (resstream, &crc_out, sizeof crc_out);
244
245 return 0;
246 }
247
248 /* Print the checksum and size to stdout.
249 If ARGS is true, also print the FILE name. */
250
251 void
252 output_crc (char const *file, int binary_file, void const *digest, bool raw,
253 bool tagged, unsigned char delim, bool args, uintmax_t length)
254 {
255 if (raw)
256 {
257 /* Output in network byte order (big endian). */
258 uint32_t out_int = SWAP (*(uint32_t *)digest);
259 fwrite (&out_int, 1, 32/8, stdout);
260 return;
261 }
262
263 char length_buf[INT_BUFSIZE_BOUND (uintmax_t)];
264 printf ("%u %s", *(unsigned int *)digest, umaxtostr (length, length_buf));
265 if (args)
266 printf (" %s", file);
267 putchar (delim);
268 }
269
270 #endif /* !CRCTAB */