src/cksum.c

   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 */