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 "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 ("#include <stdio.h>\n");
 122   printf ("#include \"cksum.h\"\n");
 123   printf ("\n");
 124   printf ("uint_fast32_t const crctab[8][256] = {\n");
 125   for (int y = 0; y < 8; y++)
 126     {
 127       printf ("{\n  0x%08x", crctab[y][0]);
 128       for (i = 0; i < 51; i++)
 129         {
 130           printf (",\n  0x%08x, 0x%08x, 0x%08x, 0x%08x, 0x%08x",
 131                   crctab[y][i * 5 + 1], crctab[y][i * 5 + 2],
 132                   crctab[y][i * 5 + 3], crctab[y][i * 5 + 4],
 133                   crctab[y][i * 5 + 5]);
 134         }
 135         printf ("\n},\n");
 136     }
 137   printf ("};\n");
 138   return EXIT_SUCCESS;
 139 }
 140
 141 #else /* !CRCTAB */
 142
 143 # include "cksum.h"
 144
 145 /* Number of bytes to read at once.  */
 146 # define BUFLEN (1 << 16)
 147
 148 # if USE_PCLMUL_CRC32
 149 static bool
 150 pclmul_supported (void)
 151 {
 152   bool pclmul_enabled = (0 < __builtin_cpu_supports ("pclmul")
 153                          && 0 < __builtin_cpu_supports ("avx"));
 154
 155   if (cksum_debug)
 156     error (0, 0, "%s",
 157            (pclmul_enabled
 158             ? _("using pclmul hardware support")
 159             : _("pclmul support not detected")));
 160
 161   return pclmul_enabled;
 162 }
 163 # endif /* USE_PCLMUL_CRC32 */
 164
 165 static bool
 166 cksum_slice8 (FILE *fp, uint_fast32_t *crc_out, uintmax_t *length_out)
 167 {
 168   uint32_t buf[BUFLEN / sizeof (uint32_t)];
 169   uint_fast32_t crc = 0;
 170   uintmax_t length = 0;
 171   size_t bytes_read;
 172
 173   if (!fp || !crc_out || !length_out)
 174     return false;
 175
 176   while ((bytes_read = fread (buf, 1, BUFLEN, fp)) > 0)
 177     {
 178       uint32_t *datap;
 179
 180       if (length + bytes_read < length)
 181         {
 182           errno = EOVERFLOW;
 183           return false;
 184         }
 185       length += bytes_read;
 186
 187       /* Process multiples of 8 bytes */
 188       datap = (uint32_t *)buf;
 189       while (bytes_read >= 8)
 190         {
 191           uint32_t first = *datap++, second = *datap++;
 192           crc ^= SWAP (first);
 193           second = SWAP (second);
 194           crc = (crctab[7][(crc >> 24) & 0xFF]
 195                  ^ crctab[6][(crc >> 16) & 0xFF]
 196                  ^ crctab[5][(crc >> 8) & 0xFF]
 197                  ^ crctab[4][(crc) & 0xFF]
 198                  ^ crctab[3][(second >> 24) & 0xFF]
 199                  ^ crctab[2][(second >> 16) & 0xFF]
 200                  ^ crctab[1][(second >> 8) & 0xFF]
 201                  ^ crctab[0][(second) & 0xFF]);
 202           bytes_read -= 8;
 203         }
 204
 205       /* And finish up last 0-7 bytes in a byte by byte fashion */
 206       unsigned char *cp = (unsigned char *)datap;
 207       while (bytes_read--)
 208         crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ *cp++) & 0xFF];
 209       if (feof (fp))
 210         break;
 211     }
 212
 213   *crc_out = crc;
 214   *length_out = length;
 215
 216   return !ferror (fp);
 217 }
 218
 219 /* Calculate the checksum and length in bytes of stream STREAM.
 220    Return -1 on error, 0 on success.  */
 221
 222 int
 223 crc_sum_stream (FILE *stream, void *resstream, uintmax_t *length)
 224 {
 225   uintmax_t total_bytes = 0;
 226   uint_fast32_t crc = 0;
 227
 228 # if USE_PCLMUL_CRC32
 229   static bool (*cksum_fp) (FILE *, uint_fast32_t *, uintmax_t *);
 230   if (! cksum_fp)
 231     cksum_fp = pclmul_supported () ? cksum_pclmul : cksum_slice8;
 232 # else
 233   bool (*cksum_fp) (FILE *, uint_fast32_t *, uintmax_t *) = cksum_slice8;
 234 # endif
 235
 236   if (! cksum_fp (stream, &crc, &total_bytes))
 237     return -1;
 238
 239   *length = total_bytes;
 240
 241   for (; total_bytes; total_bytes >>= 8)
 242     crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ total_bytes) & 0xFF];
 243   crc = ~crc & 0xFFFFFFFF;
 244
 245   unsigned int crc_out = crc;
 246   memcpy (resstream, &crc_out, sizeof crc_out);
 247
 248   return 0;
 249 }
 250
 251 /* Print the checksum and size to stdout.
 252    If ARGS is true, also print the FILE name.  */
 253
 254 void
 255 output_crc (char const *file, int binary_file, void const *digest, bool raw,
 256             bool tagged, unsigned char delim, bool args, uintmax_t length)
 257 {
 258   if (raw)
 259     {
 260       /* Output in network byte order (big endian).  */
 261       uint32_t out_int = SWAP (*(uint32_t *)digest);
 262       fwrite (&out_int, 1, 32/8, stdout);
 263       return;
 264     }
 265
 266   char length_buf[INT_BUFSIZE_BOUND (uintmax_t)];
 267   printf ("%u %s", *(unsigned int *)digest, umaxtostr (length, length_buf));
 268   if (args)
 269     printf (" %s", file);
 270   putchar (delim);
 271 }
 272
 273 #endif /* !CRCTAB */