chiark - git - mdw - runlisp/blob - sha256.c

   1 /* -*-c-*-
   2  *
   3  * The SHA256 hash function (compact edition)
   4  *
   5  * (c) 2020 Mark Wooding
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Runlisp, a tool for invoking Common Lisp scripts.
  11  *
  12  * Runlisp is free software: you can redistribute it and/or modify it
  13  * under the terms of the GNU General Public License as published by the
  14  * Free Software Foundation; either version 3 of the License, or (at your
  15  * option) any later version.
  16  *
  17  * Runlisp is distributed in the hope that it will be useful, but WITHOUT
  18  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  20  * for more details.
  21  *
  22  * You should have received a copy of the GNU General Public License
  23  * along with Runlisp.  If not, see <https://www.gnu.org/licenses/>.
  24  */
  25
  26 /*----- Header files ------------------------------------------------------*/
  27
  28 #include <string.h>
  29
  30 #include "sha256.h"
  31
  32 /*----- Preliminary definitions -------------------------------------------*/
  33
  34 /* The initial values of the state variables.  These are in reverse order --
  35  * see the note in `compress'.
  36  */
  37 static const u32 iv[8] = {
  38   0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f,
  39   0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667
  40 };
  41
  42 /* The round constants. */
  43 static const u32 rc[64] = {
  44   0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
  45   0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
  46   0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
  47   0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
  48   0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
  49   0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
  50   0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
  51   0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
  52   0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
  53   0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
  54   0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
  55   0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
  56   0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
  57   0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
  58   0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
  59   0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
  60 };
  61
  62 /* Standard bithacking operations on 32-bit words.
  63  *
  64  * Note that this code assumes that a `u32' is /at least/ 32 bits wide, but
  65  * may be longer, so we must do some work to keep cruft in the top bits from
  66  * messing things up.
  67  */
  68 #define M32 0xffffffff
  69 #define LSL32(x, n) ((x) << ((n)))
  70 #define LSR32(x, n) (((x)&M32) >> ((n)))
  71 #define ROR32(x, n) (LSL32((x), 32 - (n)) | LSR32((x), (n)))
  72
  73 /* Reading and writing 32-bit words. */
  74 #define LOAD32_B(p)                                                     \
  75   (((u32)(((const unsigned char *)(p))[0]&0xff) << 24) |                \
  76    ((u32)(((const unsigned char *)(p))[1]&0xff) << 16) |                \
  77    ((u32)(((const unsigned char *)(p))[2]&0xff) <<  8) |                \
  78    ((u32)(((const unsigned char *)(p))[3]&0xff) <<  0))
  79 #define STORE32_B(p, x) do {                                            \
  80   (void)sizeof(memmove((p), (p), 1));                                   \
  81   ((unsigned char *)(p))[0] = ((x) >> 24)&0xff;                         \
  82   ((unsigned char *)(p))[1] = ((x) >> 16)&0xff;                         \
  83   ((unsigned char *)(p))[2] = ((x) >>  8)&0xff;                         \
  84   ((unsigned char *)(p))[3] = ((x) >>  0)&0xff;                         \
  85 } while (0)
  86
  87 /* SHA256's balanced ternary operators. */
  88 #define CH(x, y, z) (((x)&(y)) | (~(x)&(z)))
  89 #define MAJ(x, y, z) (((x)&(y)) | ((y)&(z)) | ((z)&(x)))
  90
  91 /* The SHA256 Σ and σ functions. */
  92 #define S0(x) (ROR32((x),  2) ^ ROR32((x), 13) ^ ROR32((x), 22))
  93 #define S1(x) (ROR32((x),  6) ^ ROR32((x), 11) ^ ROR32((x), 25))
  94 #define s0(x) (ROR32((x),  7) ^ ROR32((x), 18) ^ LSR32((x),  3))
  95 #define s1(x) (ROR32((x), 17) ^ ROR32((x), 19) ^ LSR32((x), 10))
  96
  97 /*----- Main code ---------------------------------------------------------*/
  98
  99 /* Compress a 64-byte buffer at P, updating the hash state S. */
 100 static void compress(struct sha256_state *s, const unsigned char *p)
 101 {
 102   u32 t, u, a[8], m[16];
 103   const u32 *r = rc;
 104   size_t i;
 105
 106   /* This is a mostly straightforward implementation of the specification, as
 107    * a rolled-up loop, one iteration per round.  The only wrinkle is that the
 108    * vector of state variables, conventionally named a, b, ..., h, are
 109    * maintained in our state structure in reverse order, so h is in S->a[0],
 110    * b is in S->a[6], and a is in S->a[7].  We do this so that we advance
 111    * through our vector in the correct direction from round to round: this
 112    * avoids making the indexing arithmetic too complicated.
 113    */
 114
 115   /* Move the state and message data into our internal vectors. */
 116   for (i = 0; i < 8; i++) a[i] = s->a[i];
 117   for (i = 0; i < 16; i++, p += 4) m[i] = LOAD32_B(p);
 118
 119   /* Perform 64 rounds of update.  Update the message schedule as we go.  The
 120    * last 16 rounds of message-schedule update are pointless: doing the
 121    * message-schedule update conditionally would make the loop messier, and
 122    * running the message schedule separately would add a second loop and
 123    * require more intermediate storage.
 124    */
 125   for (i = 0; i < 64; i++) {
 126 #define A(j) (a[(i + (j))%8])
 127 #define M(j) (m[(i + (j))%16])
 128     t = A(0) + S1(A(3)) + CH(A(3), A(2), A(1)) + M(0) + *r++;
 129     u = S0(A(7)) + MAJ(A(7), A(6), A(5));
 130     A(4) += t; A(0) = t + u;
 131     M(0) += s1(M(14)) + M(9) + s0(M(1));
 132 #undef A
 133 #undef M
 134   }
 135
 136   /* Write out the updated state. */
 137   for (i = 0; i < 8; i++) s->a[i] += a[i];
 138 }
 139
 140 /* Initialize the hash state S. */
 141 void sha256_init(struct sha256_state *s)
 142   { size_t i; s->n = s->nblk = 0; for (i = 0; i < 8; i++) s->a[i] = iv[i]; }
 143
 144 /* Append SZ bytes of data starting at M to the hash state S. */
 145 void sha256_hash(struct sha256_state *s, const void *m, size_t sz)
 146 {
 147   const unsigned char *p = m;
 148   size_t r = SHA256_BLKSZ - s->n;
 149
 150   /* Feed the input data into the hash function.  Our buffer-management
 151    * policy is to empty the buffer by calling the compression function as
 152    * soon as the buffer fills completely.
 153    */
 154   if (sz < r) {
 155     /* The whole input will fit into the buffer, with space to spare.  We
 156      * just copy it in and update the occupancy counter.
 157      */
 158
 159     memcpy(s->buf + s->n, p, sz);
 160     s->n += sz;
 161   } else {
 162     /* We're going to fill the buffer at least once. */
 163
 164     /* If the buffer contains any data already then copy the initial portion
 165      * of the new input chunk into the buffer and compress it there.
 166      * Otherwise, if the buffer is entirely empty, then we can compress the
 167      * initial block from the input directly.
 168      */
 169     if (!s->n) { compress(s, p); p += SHA256_BLKSZ; sz -= SHA256_BLKSZ; }
 170     else { memcpy(s->buf + s->n, p, r); compress(s, s->buf); p += r; sz -= r; }
 171     s->nblk++;
 172
 173     /* Continue compressing complete blocks from the input while enough
 174      * material remains.
 175      */
 176     while (sz >= SHA256_BLKSZ)
 177       { compress(s, p); s->nblk++; p += SHA256_BLKSZ; sz -= SHA256_BLKSZ; }
 178
 179     /* Copy the tail end into the buffer and record how much there is. */
 180     s->n = sz; if (sz) memcpy(s->buf, p, sz);
 181   }
 182 }
 183
 184 /* Write the final hash of state S to buffer H. */
 185 void sha256_done(struct sha256_state *s, unsigned char *h)
 186 {
 187   size_t i, n, r;
 188   u32 lo, hi;
 189
 190   /* Add the end-of-data marker to the buffer.  There must be at least one
 191    * byte spare, or we'd have compressed already.
 192    */
 193   n = s->n; s->buf[n++] = 0x80; r = SHA256_BLKSZ - n;
 194
 195   /* If there's enough space for the message length, then fill the gap
 196    * between with zeros.  Otherwise, fill the whole of the remaining space,
 197    * compress, and then refill the initial portion of the buffer.  Either
 198    * way, after this, there's just eight bytes left at the end of the buffer,
 199    * into which we can drop the length.
 200    */
 201   if (r >= 8)
 202     memset(s->buf + n, 0, r - 8);
 203   else {
 204     if (r) memset(s->buf + n, 0, r);
 205     compress(s, s->buf);
 206     memset(s->buf, 0, SHA256_BLKSZ - 8);
 207   }
 208
 209   /* Convert the length into two 32-bit halves measuring the total input
 210    * length in bits, and run the compression function one last time.  There
 211    * can be no carry, since S->n is always less than 64.
 212    */
 213   lo = ((s->nblk <<  9) | (s->n <<  3))&M32; hi = (s->nblk >> 23)&M32;
 214   STORE32_B(s->buf + 56, hi); STORE32_B(s->buf + 60, lo);
 215   compress(s, s->buf);
 216
 217   /* Write out the final hash value.  We must compensate here because the
 218    * state variables are in reverse order.
 219    */
 220   for (i = 8; i-- > 0; h += 4) STORE32_B(h, s->a[i]);
 221 }
 222
 223 /*----- That's all, folks -------------------------------------------------*/