ptx: prefer xpalloc to x2nrealloc
[coreutils.git] / src / cksum.c
bloba977bf29601bb697dd609871e598e65e4952f2f8
1 /* cksum -- calculate and print POSIX checksums and sizes of files
2 Copyright (C) 1992-2024 Free Software Foundation, Inc.
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.
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.
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/>. */
17 /* Written by Q. Frank Xia, qx@math.columbia.edu.
18 Cosmetic changes and reorganization by David MacKenzie, djm@gnu.ai.mit.edu.
20 Usage: cksum [file...]
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:
27 cc -I../lib -DCRCTAB -o crctab cksum.c
28 ./crctab > crctab.c
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. */
35 #include <config.h>
37 #include <stdio.h>
38 #include <sys/types.h>
39 #include <stdint.h>
40 #include <endian.h>
41 #include "system.h"
43 #ifdef CRCTAB
45 # define BIT(x) ((uint_fast32_t) 1 << (x))
46 # define SBIT BIT (31)
48 /* The generating polynomial is
50 32 26 23 22 16 12 11 10 8 7 5 4 2 1
51 G(X)=X + X + X + X + X + X + X + X + X + X + X + X + X + X + 1
53 The i bit in GEN is set if X^i is a summand of G(X) except X^32. */
55 # define GEN (BIT (26) | BIT (23) | BIT (22) | BIT (16) | BIT (12) \
56 | BIT (11) | BIT (10) | BIT (8) | BIT (7) | BIT (5) \
57 | BIT (4) | BIT (2) | BIT (1) | BIT (0))
59 static uint_fast32_t r[8];
61 static void
62 fill_r (void)
64 r[0] = GEN;
65 for (int i = 1; i < 8; i++)
66 r[i] = (r[i - 1] << 1) ^ ((r[i - 1] & SBIT) ? GEN : 0);
69 static uint_fast32_t
70 crc_remainder (int m)
72 uint_fast32_t rem = 0;
74 for (int i = 0; i < 8; i++)
75 if (BIT (i) & m)
76 rem ^= r[i];
78 return rem & 0xFFFFFFFF; /* Make it run on 64-bit machine. */
81 int
82 main (void)
84 int i;
85 static uint_fast32_t crctab[8][256];
87 fill_r ();
89 for (i = 0; i < 256; i++)
91 crctab[0][i] = crc_remainder (i);
94 /* CRC(0x11 0x22 0x33 0x44)
95 is equal to
96 CRC(0x11 0x00 0x00 0x00) XOR CRC(0x22 0x00 0x00) XOR
97 CRC(0x33 0x00) XOR CRC(0x44)
98 We precompute the CRC values for the offset values into
99 separate CRC tables. We can then use them to speed up
100 CRC calculation by processing multiple bytes at the time. */
101 for (i = 0; i < 256; i++)
103 uint32_t crc = 0;
105 crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ (i & 0xFF)) & 0xFF];
106 for (idx_t offset = 1; offset < 8; offset++)
108 crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ 0x00) & 0xFF];
109 crctab[offset][i] = crc;
113 printf ("#include <config.h>\n");
114 printf ("#include <stdint.h>\n");
115 printf ("#include <stdio.h>\n");
116 printf ("#include \"cksum.h\"\n");
117 printf ("\n");
118 printf ("uint_fast32_t const crctab[8][256] = {\n");
119 for (int y = 0; y < 8; y++)
121 printf ("{\n 0x%08x", crctab[y][0]);
122 for (i = 0; i < 51; i++)
124 printf (",\n 0x%08x, 0x%08x, 0x%08x, 0x%08x, 0x%08x",
125 crctab[y][i * 5 + 1], crctab[y][i * 5 + 2],
126 crctab[y][i * 5 + 3], crctab[y][i * 5 + 4],
127 crctab[y][i * 5 + 5]);
129 printf ("\n},\n");
131 printf ("};\n");
132 return EXIT_SUCCESS;
135 #else /* !CRCTAB */
137 # include "cksum.h"
138 # include "crc.h"
140 /* Number of bytes to read at once. */
141 # define BUFLEN (1 << 16)
143 # if USE_PCLMUL_CRC32
144 static bool
145 pclmul_supported (void)
147 bool pclmul_enabled = (0 < __builtin_cpu_supports ("pclmul")
148 && 0 < __builtin_cpu_supports ("avx"));
150 if (cksum_debug)
151 error (0, 0, "%s",
152 (pclmul_enabled
153 ? _("using pclmul hardware support")
154 : _("pclmul support not detected")));
156 return pclmul_enabled;
158 # endif /* USE_PCLMUL_CRC32 */
160 static bool
161 cksum_slice8 (FILE *fp, uint_fast32_t *crc_out, uintmax_t *length_out)
163 uint32_t buf[BUFLEN / sizeof (uint32_t)];
164 uint_fast32_t crc = 0;
165 uintmax_t length = 0;
166 size_t bytes_read;
168 if (!fp || !crc_out || !length_out)
169 return false;
171 while ((bytes_read = fread (buf, 1, BUFLEN, fp)) > 0)
173 uint32_t *datap;
175 if (length + bytes_read < length)
177 errno = EOVERFLOW;
178 return false;
180 length += bytes_read;
182 /* Process multiples of 8 bytes */
183 datap = (uint32_t *)buf;
184 while (bytes_read >= 8)
186 uint32_t first = *datap++, second = *datap++;
187 crc ^= htobe32 (first);
188 second = htobe32 (second);
189 crc = (crctab[7][(crc >> 24) & 0xFF]
190 ^ crctab[6][(crc >> 16) & 0xFF]
191 ^ crctab[5][(crc >> 8) & 0xFF]
192 ^ crctab[4][(crc) & 0xFF]
193 ^ crctab[3][(second >> 24) & 0xFF]
194 ^ crctab[2][(second >> 16) & 0xFF]
195 ^ crctab[1][(second >> 8) & 0xFF]
196 ^ crctab[0][(second) & 0xFF]);
197 bytes_read -= 8;
200 /* And finish up last 0-7 bytes in a byte by byte fashion */
201 unsigned char *cp = (unsigned char *)datap;
202 while (bytes_read--)
203 crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ *cp++) & 0xFF];
204 if (feof (fp))
205 break;
208 *crc_out = crc;
209 *length_out = length;
211 return !ferror (fp);
214 /* Calculate the checksum and length in bytes of stream STREAM.
215 Return -1 on error, 0 on success. */
218 crc_sum_stream (FILE *stream, void *resstream, uintmax_t *length)
220 uintmax_t total_bytes = 0;
221 uint_fast32_t crc = 0;
223 # if USE_PCLMUL_CRC32
224 static bool (*cksum_fp) (FILE *, uint_fast32_t *, uintmax_t *);
225 if (! cksum_fp)
226 cksum_fp = pclmul_supported () ? cksum_pclmul : cksum_slice8;
227 # else
228 bool (*cksum_fp) (FILE *, uint_fast32_t *, uintmax_t *) = cksum_slice8;
229 # endif
231 if (! cksum_fp (stream, &crc, &total_bytes))
232 return -1;
234 *length = total_bytes;
236 for (; total_bytes; total_bytes >>= 8)
237 crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ total_bytes) & 0xFF];
238 crc = ~crc & 0xFFFFFFFF;
240 unsigned int crc_out = crc;
241 memcpy (resstream, &crc_out, sizeof crc_out);
243 return 0;
246 /* Calculate the crc32b checksum and length in bytes of stream STREAM.
247 Return -1 on error, 0 on success. */
250 crc32b_sum_stream (FILE *stream, void *resstream, uintmax_t *reslen)
252 uint32_t buf[BUFLEN / sizeof (uint32_t)];
253 uint32_t crc = 0;
254 uintmax_t len = 0;
255 size_t bytes_read;
257 if (!stream || !resstream || !reslen)
258 return -1;
260 while ((bytes_read = fread (buf, 1, BUFLEN, stream)) > 0)
262 if (len + bytes_read < len)
264 errno = EOVERFLOW;
265 return -1;
267 len += bytes_read;
269 crc = crc32_update (crc, (char const *)buf, bytes_read);
271 if (feof (stream))
272 break;
275 unsigned int crc_out = crc;
276 memcpy (resstream, &crc_out, sizeof crc_out);
278 *reslen = len;
280 return ferror (stream) ? -1 : 0;
283 /* Print the checksum and size to stdout.
284 If ARGS is true, also print the FILE name. */
286 void
287 output_crc (char const *file, int binary_file, void const *digest, bool raw,
288 bool tagged, unsigned char delim, bool args, uintmax_t length)
290 if (raw)
292 /* Output in network byte order (big endian). */
293 uint32_t out_int = htobe32 (*(uint32_t *)digest);
294 fwrite (&out_int, 1, 32/8, stdout);
295 return;
298 printf ("%u %ju", *(unsigned int *)digest, length);
299 if (args)
300 printf (" %s", file);
301 putchar (delim);
304 #endif /* !CRCTAB */