src/cksum.c

   1 /* cksum -- calculate and print POSIX checksums and sizes of files
   2    Copyright (C) 1992-2024 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 <endian.h>
  41 #include "system.h"
  42
  43 #ifdef USE_VMULL_CRC32
  44 # include <sys/auxv.h>
  45 # include <asm/hwcap.h>
  46 #endif
  47
  48 #ifdef CRCTAB
  49
  50 # define BIT(x) ((uint_fast32_t) 1 << (x))
  51 # define SBIT   BIT (31)
  52
  53 /* The generating polynomial is
  54
  55           32   26   23   22   16   12   11   10   8   7   5   4   2   1
  56     G(X)=X  + X  + X  + X  + X  + X  + X  + X  + X + X + X + X + X + X + 1
  57
  58   The i bit in GEN is set if X^i is a summand of G(X) except X^32.  */
  59
  60 # define GEN    (BIT (26) | BIT (23) | BIT (22) | BIT (16) | BIT (12) \
  61                  | BIT (11) | BIT (10) | BIT (8) | BIT (7) | BIT (5) \
  62                  | BIT (4) | BIT (2) | BIT (1) | BIT (0))
  63
  64 static uint_fast32_t r[8];
  65
  66 static void
  67 fill_r (void)
  68 {
  69   r[0] = GEN;
  70   for (int i = 1; i < 8; i++)
  71     r[i] = (r[i - 1] << 1) ^ ((r[i - 1] & SBIT) ? GEN : 0);
  72 }
  73
  74 static uint_fast32_t
  75 crc_remainder (int m)
  76 {
  77   uint_fast32_t rem = 0;
  78
  79   for (int i = 0; i < 8; i++)
  80     if (BIT (i) & m)
  81       rem ^= r[i];
  82
  83   return rem & 0xFFFFFFFF;      /* Make it run on 64-bit machine.  */
  84 }
  85
  86 int
  87 main (void)
  88 {
  89   int i;
  90   static uint_fast32_t crctab[8][256];
  91
  92   fill_r ();
  93
  94   for (i = 0; i < 256; i++)
  95     {
  96       crctab[0][i] = crc_remainder (i);
  97     }
  98
  99   /* CRC(0x11 0x22 0x33 0x44)
 100      is equal to
 101      CRC(0x11 0x00 0x00 0x00) XOR CRC(0x22 0x00 0x00) XOR
 102      CRC(0x33 0x00) XOR CRC(0x44)
 103      We precompute the CRC values for the offset values into
 104      separate CRC tables. We can then use them to speed up
 105      CRC calculation by processing multiple bytes at the time. */
 106   for (i = 0; i < 256; i++)
 107     {
 108       uint32_t crc = 0;
 109
 110       crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ (i & 0xFF)) & 0xFF];
 111       for (idx_t offset = 1; offset < 8; offset++)
 112         {
 113           crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ 0x00) & 0xFF];
 114           crctab[offset][i] = crc;
 115         }
 116     }
 117
 118   printf ("#include <config.h>\n");
 119   printf ("#include <stdint.h>\n");
 120   printf ("#include <stdio.h>\n");
 121   printf ("#include \"cksum.h\"\n");
 122   printf ("\n");
 123   printf ("uint_fast32_t const crctab[8][256] = {\n");
 124   for (int y = 0; y < 8; y++)
 125     {
 126       printf ("{\n  0x%08x", crctab[y][0]);
 127       for (i = 0; i < 51; i++)
 128         {
 129           printf (",\n  0x%08x, 0x%08x, 0x%08x, 0x%08x, 0x%08x",
 130                   crctab[y][i * 5 + 1], crctab[y][i * 5 + 2],
 131                   crctab[y][i * 5 + 3], crctab[y][i * 5 + 4],
 132                   crctab[y][i * 5 + 5]);
 133         }
 134         printf ("\n},\n");
 135     }
 136   printf ("};\n");
 137   return EXIT_SUCCESS;
 138 }
 139
 140 #else /* !CRCTAB */
 141
 142 # include "cksum.h"
 143 # include "crc.h"
 144
 145 /* Number of bytes to read at once.  */
 146 # define BUFLEN (1 << 16)
 147
 148 static bool
 149 pclmul_supported (void)
 150 {
 151   bool pclmul_enabled = false;
 152 # if USE_PCLMUL_CRC32 || GL_CRC_X86_64_PCLMUL
 153   pclmul_enabled = (0 < __builtin_cpu_supports ("pclmul")
 154                     && 0 < __builtin_cpu_supports ("avx"));
 155
 156   if (cksum_debug)
 157     error (0, 0, "%s",
 158            (pclmul_enabled
 159             ? _("using pclmul hardware support")
 160             : _("pclmul support not detected")));
 161 # endif
 162
 163   return pclmul_enabled;
 164 }
 165
 166 static bool
 167 avx2_supported (void)
 168 {
 169   /* AVX512 processors will not set vpclmulqdq unless they support
 170      the avx512 version, but it implies that the avx2 version
 171      is supported  */
 172   bool avx2_enabled = false;
 173 # if USE_AVX2_CRC32
 174   avx2_enabled = (0 < __builtin_cpu_supports ("vpclmulqdq")
 175                   && 0 < __builtin_cpu_supports ("avx2"));
 176
 177   if (cksum_debug)
 178     error (0, 0, "%s",
 179            (avx2_enabled
 180             ? _("using avx2 hardware support")
 181             : _("avx2 support not detected")));
 182 # endif
 183
 184   return avx2_enabled;
 185 }
 186
 187 static bool
 188 avx512_supported (void)
 189 {
 190   /* vpclmulqdq for multiplication
 191      mavx512f for most of the avx512 functions we're using
 192      mavx512bw for byte swapping  */
 193   bool avx512_enabled = false;
 194 # if USE_AVX512_CRC32
 195   avx512_enabled = (0 < __builtin_cpu_supports ("vpclmulqdq")
 196                     && 0 < __builtin_cpu_supports ("avx512bw")
 197                     && 0 < __builtin_cpu_supports ("avx512f"));
 198
 199   if (cksum_debug)
 200     error (0, 0, "%s",
 201            (avx512_enabled
 202             ? _("using avx512 hardware support")
 203             : _("avx512 support not detected")));
 204 # endif
 205
 206   return avx512_enabled;
 207 }
 208
 209 static bool
 210 vmull_supported (void)
 211 {
 212   /* vmull for multiplication  */
 213   bool vmull_enabled = false;
 214 # if USE_VMULL_CRC32
 215
 216   vmull_enabled = (getauxval (AT_HWCAP) & HWCAP_PMULL) > 0;
 217
 218   if (cksum_debug)
 219     error (0, 0, "%s",
 220            (vmull_enabled
 221             ? _("using vmull hardware support")
 222             : _("vmull support not detected")));
 223 # endif
 224
 225   return vmull_enabled;
 226 }
 227
 228 static bool
 229 cksum_slice8 (FILE *fp, uint_fast32_t *crc_out, uintmax_t *length_out)
 230 {
 231   uint32_t buf[BUFLEN / sizeof (uint32_t)];
 232   uint_fast32_t crc = 0;
 233   uintmax_t length = 0;
 234   size_t bytes_read;
 235
 236   if (!fp || !crc_out || !length_out)
 237     return false;
 238
 239   while ((bytes_read = fread (buf, 1, BUFLEN, fp)) > 0)
 240     {
 241       uint32_t *datap;
 242
 243       if (length + bytes_read < length)
 244         {
 245           errno = EOVERFLOW;
 246           return false;
 247         }
 248       length += bytes_read;
 249
 250       /* Process multiples of 8 bytes */
 251       datap = (uint32_t *)buf;
 252       while (bytes_read >= 8)
 253         {
 254           uint32_t first = *datap++, second = *datap++;
 255           crc ^= htobe32 (first);
 256           second = htobe32 (second);
 257           crc = (crctab[7][(crc >> 24) & 0xFF]
 258                  ^ crctab[6][(crc >> 16) & 0xFF]
 259                  ^ crctab[5][(crc >> 8) & 0xFF]
 260                  ^ crctab[4][(crc) & 0xFF]
 261                  ^ crctab[3][(second >> 24) & 0xFF]
 262                  ^ crctab[2][(second >> 16) & 0xFF]
 263                  ^ crctab[1][(second >> 8) & 0xFF]
 264                  ^ crctab[0][(second) & 0xFF]);
 265           bytes_read -= 8;
 266         }
 267
 268       /* And finish up last 0-7 bytes in a byte by byte fashion */
 269       unsigned char *cp = (unsigned char *)datap;
 270       while (bytes_read--)
 271         crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ *cp++) & 0xFF];
 272       if (feof (fp))
 273         break;
 274     }
 275
 276   *crc_out = crc;
 277   *length_out = length;
 278
 279   return !ferror (fp);
 280 }
 281
 282 /* Calculate the checksum and length in bytes of stream STREAM.
 283    Return -1 on error, 0 on success.  */
 284
 285 int
 286 crc_sum_stream (FILE *stream, void *resstream, uintmax_t *length)
 287 {
 288   uintmax_t total_bytes = 0;
 289   uint_fast32_t crc = 0;
 290
 291   static bool (*cksum_fp) (FILE *, uint_fast32_t *, uintmax_t *);
 292   if (! cksum_fp)
 293     {
 294       if (avx512_supported ())
 295         cksum_fp = cksum_avx512;
 296       else if (avx2_supported ())
 297         cksum_fp = cksum_avx2;
 298       else if (pclmul_supported ())
 299         cksum_fp = cksum_pclmul;
 300       else if (vmull_supported ())
 301         cksum_fp = cksum_vmull;
 302       else
 303         cksum_fp = cksum_slice8;
 304     }
 305
 306   if (! cksum_fp (stream, &crc, &total_bytes))
 307     return -1;
 308
 309   *length = total_bytes;
 310
 311   for (; total_bytes; total_bytes >>= 8)
 312     crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ total_bytes) & 0xFF];
 313   crc = ~crc & 0xFFFFFFFF;
 314
 315   unsigned int crc_out = crc;
 316   memcpy (resstream, &crc_out, sizeof crc_out);
 317
 318   return 0;
 319 }
 320
 321 /* Calculate the crc32b checksum and length in bytes of stream STREAM.
 322    Return -1 on error, 0 on success.  */
 323
 324 int
 325 crc32b_sum_stream (FILE *stream, void *resstream, uintmax_t *reslen)
 326 {
 327   uint32_t buf[BUFLEN / sizeof (uint32_t)];
 328   uint32_t crc = 0;
 329   uintmax_t len = 0;
 330   size_t bytes_read;
 331
 332   if (!stream || !resstream || !reslen)
 333     return -1;
 334
 335 # if GL_CRC_X86_64_PCLMUL
 336   if (cksum_debug)
 337     (void) pclmul_supported ();
 338 # endif
 339
 340   while ((bytes_read = fread (buf, 1, BUFLEN, stream)) > 0)
 341     {
 342       if (len + bytes_read < len)
 343         {
 344           errno = EOVERFLOW;
 345           return -1;
 346         }
 347       len += bytes_read;
 348
 349       crc = crc32_update (crc, (char const *)buf, bytes_read);
 350
 351       if (feof (stream))
 352         break;
 353     }
 354
 355   unsigned int crc_out = crc;
 356   memcpy (resstream, &crc_out, sizeof crc_out);
 357
 358   *reslen = len;
 359
 360   return ferror (stream) ? -1 : 0;
 361 }
 362
 363 /* Print the checksum and size to stdout.
 364    If ARGS is true, also print the FILE name.  */
 365
 366 void
 367 output_crc (char const *file, int binary_file, void const *digest, bool raw,
 368             bool tagged, unsigned char delim, bool args, uintmax_t length)
 369 {
 370   if (raw)
 371     {
 372       /* Output in network byte order (big endian).  */
 373       uint32_t out_int = htobe32 (*(uint32_t *)digest);
 374       fwrite (&out_int, 1, 32/8, stdout);
 375       return;
 376     }
 377
 378   printf ("%u %ju", *(unsigned int *)digest, length);
 379   if (args)
 380     printf (" %s", file);
 381   putchar (delim);
 382 }
 383
 384 #endif /* !CRCTAB */