Commit | Line | Data |
---|---|---|
10427eb2 MW |
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 -------------------------------------------------*/ |