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