openMSX
utils/sha1.cc
Go to the documentation of this file.
1/*
2Based on:
3100% free public domain implementation of the SHA-1 algorithm
4by Dominik Reichl <Dominik.Reichl@tiscali.de>
5
6Refactored in C++ style as part of openMSX
7by Maarten ter Huurne and Wouter Vermaelen.
8
9=== Test Vectors (from FIPS PUB 180-1) ===
10
11"abc"
12A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D
13
14"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
1584983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1
16
17A million repetitions of "a"
1834AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F
19*/
20
21#include "sha1.hh"
22#include "MSXException.hh"
23#include "endian.hh"
24#include "ranges.hh"
25#include <cassert>
26#include <cstring>
27#ifdef __SSE2__
28#include <emmintrin.h> // SSE2
29#endif
30
31namespace openmsx {
32
33// Rotate x bits to the left
34[[nodiscard]] static constexpr uint32_t rol32(uint32_t value, int bits)
35{
36 return (value << bits) | (value >> (32 - bits));
37}
38
40private:
41 uint32_t data[16];
42
43 [[nodiscard]] uint32_t next0(int i)
44 {
45 data[i] = Endian::readB32(&data[i]);
46 return data[i];
47 }
48 [[nodiscard]] uint32_t next(int i)
49 {
50 return data[i & 15] = rol32(
51 data[(i + 13) & 15] ^ data[(i + 8) & 15] ^
52 data[(i + 2) & 15] ^ data[ i & 15]
53 , 1);
54 }
55
56public:
57 explicit WorkspaceBlock(const uint8_t buffer[64]);
58
59 // SHA-1 rounds
60 void r0(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
61 {
62 z += ((w & (x ^ y)) ^ y) + next0(i) + 0x5A827999 + rol32(v, 5);
63 w = rol32(w, 30);
64 }
65 void r1(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
66 {
67 z += ((w & (x ^ y)) ^ y) + next(i) + 0x5A827999 + rol32(v, 5);
68 w = rol32(w, 30);
69 }
70 void r2(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
71 {
72 z += (w ^ x ^ y) + next(i) + 0x6ED9EBA1 + rol32(v, 5);
73 w = rol32(w, 30);
74 }
75 void r3(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
76 {
77 z += (((w | x) & y) | (w & x)) + next(i) + 0x8F1BBCDC + rol32(v, 5);
78 w = rol32(w, 30);
79 }
80 void r4(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
81 {
82 z += (w ^ x ^ y) + next(i) + 0xCA62C1D6 + rol32(v, 5);
83 w = rol32(w, 30);
84 }
85};
86
87WorkspaceBlock::WorkspaceBlock(const uint8_t buffer[64])
88{
89 memcpy(data, buffer, sizeof(data));
90}
91
92
93// class Sha1Sum
94
96{
97 clear();
98}
99
100Sha1Sum::Sha1Sum(std::string_view hex)
101{
102 if (hex.size() != 40) {
103 throw MSXException("Invalid sha1, should be exactly 40 digits long: ", hex);
104 }
105 parse40(hex.data());
106}
107
108#ifdef __SSE2__
109// emulate some missing unsigned-8-bit comparison functions
110[[nodiscard]] static inline __m128i _mm_cmpge_epu8(__m128i a, __m128i b)
111{
112 return _mm_cmpeq_epi8(_mm_max_epu8(a, b), a);
113}
114
115[[nodiscard]] static inline __m128i _mm_cmple_epu8(__m128i a, __m128i b)
116{
117 return _mm_cmpge_epu8(b, a);
118}
119
120// load 64-bit (possibly unaligned) and swap bytes
121[[nodiscard]] static inline uint64_t loadSwap64(const char* s)
122{
123 return Endian::read_UA_B64(s);
124}
125
126#else
127
128[[nodiscard]] static /*constexpr*/ unsigned hex(char x, const char* str)
129{
130 if (('0' <= x) && (x <= '9')) return x - '0';
131 if (('a' <= x) && (x <= 'f')) return x - 'a' + 10;
132 if (('A' <= x) && (x <= 'F')) return x - 'A' + 10;
133 throw MSXException("Invalid sha1, digits should be 0-9, a-f: ",
134 std::string_view(str, 40));
135}
136#endif
137
138void Sha1Sum::parse40(const char* str)
139{
140#ifdef __SSE2__
141 // SSE2 version
142
143 // load characters
144 __m128i s0 = _mm_set_epi64x(loadSwap64(str + 8), loadSwap64(str + 0));
145 __m128i s1 = _mm_set_epi64x(loadSwap64(str + 24), loadSwap64(str + 16));
146 __m128i s2 = _mm_set_epi64x('0' * 0x0101010101010101, loadSwap64(str + 32));
147
148 // chars - '0'
149 __m128i cc0 = _mm_set1_epi8(char(-'0'));
150 __m128i s0_0 = _mm_add_epi8(s0, cc0);
151 __m128i s1_0 = _mm_add_epi8(s1, cc0);
152 __m128i s2_0 = _mm_add_epi8(s2, cc0);
153
154 // (chars | 32) - 'a' (convert uppercase 'A'-'F' into lower case)
155 __m128i c32 = _mm_set1_epi8(32);
156 __m128i cca = _mm_set1_epi8(char(-'a'));
157 __m128i s0_a = _mm_add_epi8(_mm_or_si128(s0, c32), cca);
158 __m128i s1_a = _mm_add_epi8(_mm_or_si128(s1, c32), cca);
159 __m128i s2_a = _mm_add_epi8(_mm_or_si128(s2, c32), cca);
160
161 // was in range '0'-'9'?
162 __m128i c9 = _mm_set1_epi8(9);
163 __m128i c0_0 = _mm_cmple_epu8(s0_0, c9);
164 __m128i c1_0 = _mm_cmple_epu8(s1_0, c9);
165 __m128i c2_0 = _mm_cmple_epu8(s2_0, c9);
166
167 // was in range 'a'-'f'?
168 __m128i c5 = _mm_set1_epi8(5);
169 __m128i c0_a = _mm_cmple_epu8(s0_a, c5);
170 __m128i c1_a = _mm_cmple_epu8(s1_a, c5);
171 __m128i c2_a = _mm_cmple_epu8(s2_a, c5);
172
173 // either '0'-'9' or 'a'-f' must be in range for all chars
174 __m128i ok0 = _mm_or_si128(c0_0, c0_a);
175 __m128i ok1 = _mm_or_si128(c1_0, c1_a);
176 __m128i ok2 = _mm_or_si128(c2_0, c2_a);
177 __m128i ok = _mm_and_si128(_mm_and_si128(ok0, ok1), ok2);
178 if (_mm_movemask_epi8(ok) != 0xffff) [[unlikely]] {
179 throw MSXException("Invalid sha1, digits should be 0-9, a-f: ",
180 std::string_view(str, 40));
181 }
182
183 // '0'-'9' to numeric value (or zero)
184 __m128i d0_0 = _mm_and_si128(s0_0, c0_0);
185 __m128i d1_0 = _mm_and_si128(s1_0, c1_0);
186 __m128i d2_0 = _mm_and_si128(s2_0, c2_0);
187
188 // 'a'-'f' to numeric value (or zero)
189 __m128i c10 = _mm_set1_epi8(10);
190 __m128i d0_a = _mm_and_si128(_mm_add_epi8(s0_a, c10), c0_a);
191 __m128i d1_a = _mm_and_si128(_mm_add_epi8(s1_a, c10), c1_a);
192 __m128i d2_a = _mm_and_si128(_mm_add_epi8(s2_a, c10), c2_a);
193
194 // combine 0-9 / 10-15 into 0-15
195 __m128i d0 = _mm_or_si128(d0_0, d0_a);
196 __m128i d1 = _mm_or_si128(d1_0, d1_a);
197 __m128i d2 = _mm_or_si128(d2_0, d2_a);
198
199 // compact bytes to nibbles
200 __m128i c00ff = _mm_set1_epi16(0x00ff);
201 __m128i e0 = _mm_and_si128(_mm_or_si128(d0, _mm_srli_epi16(d0, 4)), c00ff);
202 __m128i e1 = _mm_and_si128(_mm_or_si128(d1, _mm_srli_epi16(d1, 4)), c00ff);
203 __m128i e2 = _mm_and_si128(_mm_or_si128(d2, _mm_srli_epi16(d2, 4)), c00ff);
204 __m128i f0 = _mm_packus_epi16(e0, e0);
205 __m128i f1 = _mm_packus_epi16(e1, e1);
206 __m128i f2 = _mm_packus_epi16(e2, e2);
207
208 // store result
209 _mm_storeu_si128(reinterpret_cast<__m128i*>(a), _mm_unpacklo_epi64(f0, f1));
210 a[4] = _mm_cvtsi128_si32(f2);
211#else
212 // equivalent c++ version
213 const char* p = str;
214 for (auto& ai : a) {
215 unsigned t = 0;
216 repeat(8, [&] {
217 t <<= 4;
218 t |= hex(*p++, str);
219 });
220 ai = t;
221 }
222#endif
223}
224
225[[nodiscard]] static constexpr char digit(unsigned x)
226{
227 return (x < 10) ? (x + '0') : (x - 10 + 'a');
228}
229std::string Sha1Sum::toString() const
230{
231 char buf[40];
232 char* p = buf;
233 for (const auto& ai : a) {
234 for (int j = 28; j >= 0; j -= 4) {
235 *p++ = digit((ai >> j) & 0xf);
236 }
237 }
238 return {buf, 40};
239}
240
241bool Sha1Sum::empty() const
242{
243 return ranges::all_of(a, [](auto& e) { return e == 0; });
244}
246{
247 ranges::fill(a, 0);
248}
249
250
251// class SHA1
252
254 : m_count(0)
255 , m_finalized(false)
256{
257 // SHA1 initialization constants
258 m_state.a[0] = 0x67452301;
259 m_state.a[1] = 0xEFCDAB89;
260 m_state.a[2] = 0x98BADCFE;
261 m_state.a[3] = 0x10325476;
262 m_state.a[4] = 0xC3D2E1F0;
263}
264
265void SHA1::transform(const uint8_t buffer[64])
266{
267 WorkspaceBlock block(buffer);
268
269 // Copy m_state[] to working vars
270 uint32_t a = m_state.a[0];
271 uint32_t b = m_state.a[1];
272 uint32_t c = m_state.a[2];
273 uint32_t d = m_state.a[3];
274 uint32_t e = m_state.a[4];
275
276 // 4 rounds of 20 operations each. Loop unrolled
277 block.r0(a,b,c,d,e, 0); block.r0(e,a,b,c,d, 1); block.r0(d,e,a,b,c, 2);
278 block.r0(c,d,e,a,b, 3); block.r0(b,c,d,e,a, 4); block.r0(a,b,c,d,e, 5);
279 block.r0(e,a,b,c,d, 6); block.r0(d,e,a,b,c, 7); block.r0(c,d,e,a,b, 8);
280 block.r0(b,c,d,e,a, 9); block.r0(a,b,c,d,e,10); block.r0(e,a,b,c,d,11);
281 block.r0(d,e,a,b,c,12); block.r0(c,d,e,a,b,13); block.r0(b,c,d,e,a,14);
282 block.r0(a,b,c,d,e,15); block.r1(e,a,b,c,d,16); block.r1(d,e,a,b,c,17);
283 block.r1(c,d,e,a,b,18); block.r1(b,c,d,e,a,19); block.r2(a,b,c,d,e,20);
284 block.r2(e,a,b,c,d,21); block.r2(d,e,a,b,c,22); block.r2(c,d,e,a,b,23);
285 block.r2(b,c,d,e,a,24); block.r2(a,b,c,d,e,25); block.r2(e,a,b,c,d,26);
286 block.r2(d,e,a,b,c,27); block.r2(c,d,e,a,b,28); block.r2(b,c,d,e,a,29);
287 block.r2(a,b,c,d,e,30); block.r2(e,a,b,c,d,31); block.r2(d,e,a,b,c,32);
288 block.r2(c,d,e,a,b,33); block.r2(b,c,d,e,a,34); block.r2(a,b,c,d,e,35);
289 block.r2(e,a,b,c,d,36); block.r2(d,e,a,b,c,37); block.r2(c,d,e,a,b,38);
290 block.r2(b,c,d,e,a,39); block.r3(a,b,c,d,e,40); block.r3(e,a,b,c,d,41);
291 block.r3(d,e,a,b,c,42); block.r3(c,d,e,a,b,43); block.r3(b,c,d,e,a,44);
292 block.r3(a,b,c,d,e,45); block.r3(e,a,b,c,d,46); block.r3(d,e,a,b,c,47);
293 block.r3(c,d,e,a,b,48); block.r3(b,c,d,e,a,49); block.r3(a,b,c,d,e,50);
294 block.r3(e,a,b,c,d,51); block.r3(d,e,a,b,c,52); block.r3(c,d,e,a,b,53);
295 block.r3(b,c,d,e,a,54); block.r3(a,b,c,d,e,55); block.r3(e,a,b,c,d,56);
296 block.r3(d,e,a,b,c,57); block.r3(c,d,e,a,b,58); block.r3(b,c,d,e,a,59);
297 block.r4(a,b,c,d,e,60); block.r4(e,a,b,c,d,61); block.r4(d,e,a,b,c,62);
298 block.r4(c,d,e,a,b,63); block.r4(b,c,d,e,a,64); block.r4(a,b,c,d,e,65);
299 block.r4(e,a,b,c,d,66); block.r4(d,e,a,b,c,67); block.r4(c,d,e,a,b,68);
300 block.r4(b,c,d,e,a,69); block.r4(a,b,c,d,e,70); block.r4(e,a,b,c,d,71);
301 block.r4(d,e,a,b,c,72); block.r4(c,d,e,a,b,73); block.r4(b,c,d,e,a,74);
302 block.r4(a,b,c,d,e,75); block.r4(e,a,b,c,d,76); block.r4(d,e,a,b,c,77);
303 block.r4(c,d,e,a,b,78); block.r4(b,c,d,e,a,79);
304
305 // Add the working vars back into m_state[]
306 m_state.a[0] += a;
307 m_state.a[1] += b;
308 m_state.a[2] += c;
309 m_state.a[3] += d;
310 m_state.a[4] += e;
311}
312
313// Use this function to hash in binary data and strings
314void SHA1::update(std::span<const uint8_t> data_)
315{
316 const uint8_t* data = data_.data();
317 size_t len = data_.size();
318
319 assert(!m_finalized);
320 uint32_t j = m_count & 63;
321
322 m_count += len;
323
324 size_t i;
325 if ((j + len) > 63) {
326 memcpy(&m_buffer[j], data, (i = 64 - j));
327 transform(m_buffer);
328 for (; i + 63 < len; i += 64) {
329 transform(&data[i]);
330 }
331 j = 0;
332 } else {
333 i = 0;
334 }
335 memcpy(&m_buffer[j], &data[i], len - i);
336}
337
338void SHA1::finalize()
339{
340 assert(!m_finalized);
341
342 uint32_t j = m_count & 63;
343 m_buffer[j++] = 0x80;
344 if (j > 56) {
345 memset(&m_buffer[j], 0, 64 - j);
346 transform(m_buffer);
347 j = 0;
348 }
349 memset(&m_buffer[j], 0, 56 - j);
350 Endian::B64 finalCount = 8 * m_count; // convert number of bytes to bits
351 memcpy(&m_buffer[56], &finalCount, 8);
352 transform(m_buffer);
353
354 m_finalized = true;
355}
356
358{
359 if (!m_finalized) finalize();
360 return m_state;
361}
362
363Sha1Sum SHA1::calc(std::span<const uint8_t> data)
364{
365 SHA1 sha1;
366 sha1.update(data);
367 return sha1.digest();
368}
369
370} // namespace openmsx
TclObject t
Helper class to perform a sha1 calculation.
Definition: sha1.hh:79
Sha1Sum digest()
Get the final hash.
Definition: utils/sha1.cc:357
void update(std::span< const uint8_t > data)
Incrementally calculate the hash value.
Definition: utils/sha1.cc:314
static Sha1Sum calc(std::span< const uint8_t > data)
Easier to use interface, if you can pass all data in one go.
Definition: utils/sha1.cc:363
This class represents the result of a sha1 calculation (a 160-bit value).
Definition: sha1.hh:22
bool empty() const
Definition: utils/sha1.cc:241
void parse40(const char *str)
Parse from a 40-character long buffer.
Definition: utils/sha1.cc:138
std::string toString() const
Definition: utils/sha1.cc:229
void r1(uint32_t v, uint32_t &w, uint32_t x, uint32_t y, uint32_t &z, int i)
Definition: utils/sha1.cc:65
void r2(uint32_t v, uint32_t &w, uint32_t x, uint32_t y, uint32_t &z, int i)
Definition: utils/sha1.cc:70
WorkspaceBlock(const uint8_t buffer[64])
Definition: utils/sha1.cc:87
void r4(uint32_t v, uint32_t &w, uint32_t x, uint32_t y, uint32_t &z, int i)
Definition: utils/sha1.cc:80
void r0(uint32_t v, uint32_t &w, uint32_t x, uint32_t y, uint32_t &z, int i)
Definition: utils/sha1.cc:60
void r3(uint32_t v, uint32_t &w, uint32_t x, uint32_t y, uint32_t &z, int i)
Definition: utils/sha1.cc:75
ALWAYS_INLINE uint64_t read_UA_B64(const void *p)
Definition: endian.hh:244
uint32_t readB32(const void *p)
Definition: endian.hh:162
constexpr double e
Definition: Math.hh:18
This file implemented 3 utility functions:
Definition: Autofire.cc:9
constexpr KeyMatrixPosition x
Keyboard bindings.
Definition: Keyboard.cc:127
bool all_of(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:163
constexpr void fill(ForwardRange &&range, const T &value)
Definition: ranges.hh:256
constexpr void repeat(T n, Op op)
Repeat the given operation 'op' 'n' times.
Definition: xrange.hh:148