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