3 * The SHA256 hash function (compact edition)
5 * (c) 2020 Mark Wooding
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Runlisp, a tool for invoking Common Lisp scripts.
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.
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
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/>.
26 /*----- Header files ------------------------------------------------------*/
32 /*----- Preliminary definitions -------------------------------------------*/
34 /* The initial values of the state variables. These are in reverse order --
35 * see the note in `compress'.
37 static const u32 iv
[8] = {
38 0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f,
39 0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667
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
62 /* Standard bithacking operations on 32-bit words.
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
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)))
73 /* Reading and writing 32-bit words. */
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; \
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)))
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))
97 /*----- Main code ---------------------------------------------------------*/
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
)
102 u32 t
, u
, a
[8], m
[16];
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.
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
);
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.
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));
136 /* Write out the updated state. */
137 for (i
= 0; i
< 8; i
++) s
->a
[i
] += a
[i
];
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
]; }
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
)
147 const unsigned char *p
= m
;
148 size_t r
= SHA256_BLKSZ
- s
->n
;
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.
155 /* The whole input will fit into the buffer, with space to spare. We
156 * just copy it in and update the occupancy counter.
159 memcpy(s
->buf
+ s
->n
, p
, sz
);
162 /* We're going to fill the buffer at least once. */
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.
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
; }
173 /* Continue compressing complete blocks from the input while enough
176 while (sz
>= SHA256_BLKSZ
)
177 { compress(s
, p
); s
->nblk
++; p
+= SHA256_BLKSZ
; sz
-= SHA256_BLKSZ
; }
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
);
184 /* Write the final hash of state S to buffer H. */
185 void sha256_done(struct sha256_state
*s
, unsigned char *h
)
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.
193 n
= s
->n
; s
->buf
[n
++] = 0x80; r
= SHA256_BLKSZ
- n
;
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.
202 memset(s
->buf
+ n
, 0, r
- 8);
204 if (r
) memset(s
->buf
+ n
, 0, r
);
206 memset(s
->buf
, 0, SHA256_BLKSZ
- 8);
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.
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
);
217 /* Write out the final hash value. We must compensate here because the
218 * state variables are in reverse order.
220 for (i
= 8; i
-- > 0; h
+= 4) STORE32_B(h
, s
->a
[i
]);
223 /*----- That's all, folks -------------------------------------------------*/