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 CRCTAB
  44
  45 # define BIT(x) ((uint_fast32_t) 1 << (x))
  46 # define SBIT   BIT (31)
  47
  48 /* The generating polynomial is
  49
  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
  52
  53   The i bit in GEN is set if X^i is a summand of G(X) except X^32.  */
  54
  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))
  58
  59 static uint_fast32_t r[8];
  60
  61 static void
  62 fill_r (void)
  63 {
  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);
  67 }
  68
  69 static uint_fast32_t
  70 crc_remainder (int m)
  71 {
  72   uint_fast32_t rem = 0;
  73
  74   for (int i = 0; i < 8; i++)
  75     if (BIT (i) & m)
  76       rem ^= r[i];
  77
  78   return rem & 0xFFFFFFFF;      /* Make it run on 64-bit machine.  */
  79 }
  80
  81 int
  82 main (void)
  83 {
  84   int i;
  85   static uint_fast32_t crctab[8][256];
  86
  87   fill_r ();
  88
  89   for (i = 0; i < 256; i++)
  90     {
  91       crctab[0][i] = crc_remainder (i);
  92     }
  93
  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++)
 102     {
 103       uint32_t crc = 0;
 104
 105       crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ (i & 0xFF)) & 0xFF];
 106       for (idx_t offset = 1; offset < 8; offset++)
 107         {
 108           crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ 0x00) & 0xFF];
 109           crctab[offset][i] = crc;
 110         }
 111     }
 112
 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++)
 120     {
 121       printf ("{\n  0x%08x", crctab[y][0]);
 122       for (i = 0; i < 51; i++)
 123         {
 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]);
 128         }
 129         printf ("\n},\n");
 130     }
 131   printf ("};\n");
 132   return EXIT_SUCCESS;
 133 }
 134
 135 #else /* !CRCTAB */
 136
 137 # include "cksum.h"
 138
 139 /* Number of bytes to read at once.  */
 140 # define BUFLEN (1 << 16)
 141
 142 # if USE_PCLMUL_CRC32
 143 static bool
 144 pclmul_supported (void)
 145 {
 146   bool pclmul_enabled = (0 < __builtin_cpu_supports ("pclmul")
 147                          && 0 < __builtin_cpu_supports ("avx"));
 148
 149   if (cksum_debug)
 150     error (0, 0, "%s",
 151            (pclmul_enabled
 152             ? _("using pclmul hardware support")
 153             : _("pclmul support not detected")));
 154
 155   return pclmul_enabled;
 156 }
 157 # endif /* USE_PCLMUL_CRC32 */
 158
 159 static bool
 160 cksum_slice8 (FILE *fp, uint_fast32_t *crc_out, uintmax_t *length_out)
 161 {
 162   uint32_t buf[BUFLEN / sizeof (uint32_t)];
 163   uint_fast32_t crc = 0;
 164   uintmax_t length = 0;
 165   size_t bytes_read;
 166
 167   if (!fp || !crc_out || !length_out)
 168     return false;
 169
 170   while ((bytes_read = fread (buf, 1, BUFLEN, fp)) > 0)
 171     {
 172       uint32_t *datap;
 173
 174       if (length + bytes_read < length)
 175         {
 176           errno = EOVERFLOW;
 177           return false;
 178         }
 179       length += bytes_read;
 180
 181       /* Process multiples of 8 bytes */
 182       datap = (uint32_t *)buf;
 183       while (bytes_read >= 8)
 184         {
 185           uint32_t first = *datap++, second = *datap++;
 186           crc ^= htobe32 (first);
 187           second = htobe32 (second);
 188           crc = (crctab[7][(crc >> 24) & 0xFF]
 189                  ^ crctab[6][(crc >> 16) & 0xFF]
 190                  ^ crctab[5][(crc >> 8) & 0xFF]
 191                  ^ crctab[4][(crc) & 0xFF]
 192                  ^ crctab[3][(second >> 24) & 0xFF]
 193                  ^ crctab[2][(second >> 16) & 0xFF]
 194                  ^ crctab[1][(second >> 8) & 0xFF]
 195                  ^ crctab[0][(second) & 0xFF]);
 196           bytes_read -= 8;
 197         }
 198
 199       /* And finish up last 0-7 bytes in a byte by byte fashion */
 200       unsigned char *cp = (unsigned char *)datap;
 201       while (bytes_read--)
 202         crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ *cp++) & 0xFF];
 203       if (feof (fp))
 204         break;
 205     }
 206
 207   *crc_out = crc;
 208   *length_out = length;
 209
 210   return !ferror (fp);
 211 }
 212
 213 /* Calculate the checksum and length in bytes of stream STREAM.
 214    Return -1 on error, 0 on success.  */
 215
 216 int
 217 crc_sum_stream (FILE *stream, void *resstream, uintmax_t *length)
 218 {
 219   uintmax_t total_bytes = 0;
 220   uint_fast32_t crc = 0;
 221
 222 # if USE_PCLMUL_CRC32
 223   static bool (*cksum_fp) (FILE *, uint_fast32_t *, uintmax_t *);
 224   if (! cksum_fp)
 225     cksum_fp = pclmul_supported () ? cksum_pclmul : cksum_slice8;
 226 # else
 227   bool (*cksum_fp) (FILE *, uint_fast32_t *, uintmax_t *) = cksum_slice8;
 228 # endif
 229
 230   if (! cksum_fp (stream, &crc, &total_bytes))
 231     return -1;
 232
 233   *length = total_bytes;
 234
 235   for (; total_bytes; total_bytes >>= 8)
 236     crc = (crc << 8) ^ crctab[0][((crc >> 24) ^ total_bytes) & 0xFF];
 237   crc = ~crc & 0xFFFFFFFF;
 238
 239   unsigned int crc_out = crc;
 240   memcpy (resstream, &crc_out, sizeof crc_out);
 241
 242   return 0;
 243 }
 244
 245 /* Print the checksum and size to stdout.
 246    If ARGS is true, also print the FILE name.  */
 247
 248 void
 249 output_crc (char const *file, int binary_file, void const *digest, bool raw,
 250             bool tagged, unsigned char delim, bool args, uintmax_t length)
 251 {
 252   if (raw)
 253     {
 254       /* Output in network byte order (big endian).  */
 255       uint32_t out_int = htobe32 (*(uint32_t *)digest);
 256       fwrite (&out_int, 1, 32/8, stdout);
 257       return;
 258     }
 259
 260   printf ("%u %ju", *(unsigned int *)digest, length);
 261   if (args)
 262     printf (" %s", file);
 263   putchar (delim);
 264 }
 265
 266 #endif /* !CRCTAB */