Remco Bloemen / SHA256

A fine-tuned implementation of the SHA256 hashing algorithm.

Dependents:   EntropySource Wallet_v1

SHA256.cpp@2:1991439ea6b8, 2011-06-20 (annotated)

Committer:
Remco
Date:
Mon Jun 20 09:45:02 2011 +0000
Revision:
2:1991439ea6b8
Parent:
0:772b6de3a841
Child:
3:f19b10394f9c
Optimized chunk loop

Who changed what in which revision?

UserRevisionLine numberNew contents of line
Remco 0:772b6de3a841 1 // Author: Remco Bloemen
Remco 0:772b6de3a841 2 // Based on:
Remco 0:772b6de3a841 3 // http://en.wikipedia.org/wiki/SHA-2
Remco 0:772b6de3a841 4 // http://www.iwar.org.uk/comsec/resources/cipher/sha256-384-512.pdf
Remco 2:1991439ea6b8 5 // some of the OpenSSL optimizations
Remco 0:772b6de3a841 6
Remco 0:772b6de3a841 7 #include "SHA256.h"
Remco 0:772b6de3a841 8
Remco 0:772b6de3a841 9 inline unsigned int byte_swap(unsigned int x)
Remco 0:772b6de3a841 10 {
Remco 0:772b6de3a841 11 // unsigned int result;
Remco 0:772b6de3a841 12 // asm("REV %0, %1" : "=r"(result) : "r"(x));
Remco 0:772b6de3a841 13 // return result
Remco 0:772b6de3a841 14 return __rev(x);
Remco 0:772b6de3a841 15 }
Remco 0:772b6de3a841 16
Remco 0:772b6de3a841 17 inline unsigned int rotate_right(unsigned int x, int shift)
Remco 0:772b6de3a841 18 {
Remco 2:1991439ea6b8 19 // return (x >> shift) | (x << (32 - shift));
Remco 2:1991439ea6b8 20 return __ror(x, shift);
Remco 0:772b6de3a841 21 }
Remco 0:772b6de3a841 22
Remco 0:772b6de3a841 23 void SHA256::reset()
Remco 0:772b6de3a841 24 {
Remco 0:772b6de3a841 25 hash[0] = 0x6A09E667;
Remco 0:772b6de3a841 26 hash[1] = 0xBB67AE85;
Remco 0:772b6de3a841 27 hash[2] = 0x3C6EF372;
Remco 0:772b6de3a841 28 hash[3] = 0xA54FF53A;
Remco 0:772b6de3a841 29 hash[4] = 0x510E527F;
Remco 0:772b6de3a841 30 hash[5] = 0x9B05688C;
Remco 0:772b6de3a841 31 hash[6] = 0x1F83D9AB;
Remco 0:772b6de3a841 32 hash[7] = 0x5BE0CD19;
Remco 0:772b6de3a841 33 length = 0;
Remco 0:772b6de3a841 34 }
Remco 0:772b6de3a841 35
Remco 0:772b6de3a841 36 void SHA256::append(const char* data, int size)
Remco 0:772b6de3a841 37 {
Remco 2:1991439ea6b8 38 /*
Remco 2:1991439ea6b8 39 unsigned int* dataw = reinterpret_cast<unsigned int*>(data);
Remco 2:1991439ea6b8 40
Remco 2:1991439ea6b8 41 while(length & 0x3) {
Remco 2:1991439ea6b8 42 if(data == end) {
Remco 2:1991439ea6b8 43 length += size;
Remco 2:1991439ea6b8 44 return;
Remco 2:1991439ea6b8 45 }
Remco 2:1991439ea6b8 46 buffer[3 + (length & (~0x3)) - (length & 0x3)] = *data;
Remco 2:1991439ea6b8 47 ++length;
Remco 2:1991439ea6b8 48 ++data;
Remco 2:1991439ea6b8 49 }
Remco 2:1991439ea6b8 50 if(length % 64 == 0) {
Remco 2:1991439ea6b8 51 process_chunk();
Remco 2:1991439ea6b8 52 }
Remco 2:1991439ea6b8 53
Remco 2:1991439ea6b8 54 // Process words
Remco 2:1991439ea6b8 55 int num_words = (end - data) / 4;
Remco 2:1991439ea6b8 56 int index = (length % 64) / 4;
Remco 2:1991439ea6b8 57 unsigned int* data_words = reinterpret_cast<unsigned int*>(data);
Remco 2:1991439ea6b8 58 while(num_words--)
Remco 2:1991439ea6b8 59 {
Remco 2:1991439ea6b8 60 if(index == 16) {
Remco 2:1991439ea6b8 61 process_chunk();
Remco 2:1991439ea6b8 62 }
Remco 2:1991439ea6b8 63 }
Remco 2:1991439ea6b8 64 */
Remco 2:1991439ea6b8 65
Remco 0:772b6de3a841 66 const char* end = data + size;
Remco 0:772b6de3a841 67 char* buffer = reinterpret_cast<char*>(w);
Remco 2:1991439ea6b8 68
Remco 0:772b6de3a841 69 int index = length % 64;
Remco 0:772b6de3a841 70 while(data != end) {
Remco 0:772b6de3a841 71 int word_index = index / 4;
Remco 0:772b6de3a841 72 int byte_index = index % 4;
Remco 0:772b6de3a841 73 buffer[4 * word_index + 3 - byte_index] = *data;
Remco 0:772b6de3a841 74 ++index;
Remco 0:772b6de3a841 75 ++data;
Remco 0:772b6de3a841 76 if(index == 64) {
Remco 0:772b6de3a841 77 process_chunk();
Remco 0:772b6de3a841 78 index = 0;
Remco 0:772b6de3a841 79 }
Remco 0:772b6de3a841 80 }
Remco 2:1991439ea6b8 81
Remco 0:772b6de3a841 82 length += size;
Remco 0:772b6de3a841 83 }
Remco 0:772b6de3a841 84
Remco 0:772b6de3a841 85 void SHA256::finalize()
Remco 0:772b6de3a841 86 {
Remco 0:772b6de3a841 87 int trailing = length % 64;
Remco 0:772b6de3a841 88
Remco 0:772b6de3a841 89 // Append the bit '1' to the message
Remco 0:772b6de3a841 90 int last_block = trailing / 4;
Remco 0:772b6de3a841 91 unsigned int bit_in_block = 0x80 << (24 - (trailing % 4) * 8);
Remco 0:772b6de3a841 92 w[last_block] |= bit_in_block;
Remco 0:772b6de3a841 93
Remco 0:772b6de3a841 94 // Set all other bits to zero
Remco 2:1991439ea6b8 95 w[last_block] &= ~(bit_in_block - 1);
Remco 0:772b6de3a841 96 for(int i = last_block + 1; i < 15; ++i)
Remco 0:772b6de3a841 97 w[i] = 0;
Remco 0:772b6de3a841 98
Remco 0:772b6de3a841 99 // Make room for the length if necessary
Remco 0:772b6de3a841 100 if(trailing >= 56) {
Remco 0:772b6de3a841 101 process_chunk();
Remco 0:772b6de3a841 102 for(int i = 0; i <= last_block; ++i)
Remco 0:772b6de3a841 103 w[i] = 0;
Remco 0:772b6de3a841 104 }
Remco 0:772b6de3a841 105
Remco 0:772b6de3a841 106 // Append the length in bits
Remco 0:772b6de3a841 107 w[14] = length >> (32 - 3);
Remco 0:772b6de3a841 108 w[15] = length << 3;
Remco 0:772b6de3a841 109 process_chunk();
Remco 0:772b6de3a841 110
Remco 0:772b6de3a841 111 // Convert the result to big endian
Remco 0:772b6de3a841 112 for(int i = 0; i < 8; ++i)
Remco 0:772b6de3a841 113 hash[i] = byte_swap(hash[i]);
Remco 0:772b6de3a841 114 }
Remco 0:772b6de3a841 115
Remco 2:1991439ea6b8 116 #define s0(x) (rotate_right(x, 7) ^ rotate_right(x, 18) ^ (x >> 3))
Remco 2:1991439ea6b8 117 #define s1(x) (rotate_right(x, 17) ^ rotate_right(x, 19) ^ (x >> 10))
Remco 2:1991439ea6b8 118 #define s2(x) (rotate_right(x, 2) ^ rotate_right(x, 13) ^ rotate_right(x, 22))
Remco 2:1991439ea6b8 119 #define s3(x) (rotate_right(x, 6) ^ rotate_right(x, 11) ^ rotate_right(x, 25))
Remco 2:1991439ea6b8 120 #define maj(a,b,c) ((a & b) ^ (a & c) ^ (b & c))
Remco 2:1991439ea6b8 121 #define ch(a,b,c) ((a & b) ^ ((~a) & c))
Remco 2:1991439ea6b8 122
Remco 2:1991439ea6b8 123 const unsigned int k[64] = {
Remco 2:1991439ea6b8 124 0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5, 0x3956C25B, 0x59F111F1, 0x923F82A4, 0xAB1C5ED5,
Remco 2:1991439ea6b8 125 0xD807AA98, 0x12835B01, 0x243185BE, 0x550C7DC3, 0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7, 0xC19BF174,
Remco 2:1991439ea6b8 126 0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC, 0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA,
Remco 2:1991439ea6b8 127 0x983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7, 0xC6E00BF3, 0xD5A79147, 0x06CA6351, 0x14292967,
Remco 2:1991439ea6b8 128 0x27B70A85, 0x2E1B2138, 0x4D2C6DFC, 0x53380D13, 0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85,
Remco 2:1991439ea6b8 129 0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3, 0xD192E819, 0xD6990624, 0xF40E3585, 0x106AA070,
Remco 2:1991439ea6b8 130 0x19A4C116, 0x1E376C08, 0x2748774C, 0x34B0BCB5, 0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F, 0x682E6FF3,
Remco 2:1991439ea6b8 131 0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208, 0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2
Remco 2:1991439ea6b8 132 };
Remco 2:1991439ea6b8 133
Remco 2:1991439ea6b8 134 #define ROUND(a,b,c,d,e,f,g,h,i) \
Remco 2:1991439ea6b8 135 h += w[i];\
Remco 2:1991439ea6b8 136 h += *K++;\
Remco 2:1991439ea6b8 137 h += s3(e); \
Remco 2:1991439ea6b8 138 h += ch(e, f, g); \
Remco 2:1991439ea6b8 139 d += h;\
Remco 2:1991439ea6b8 140 h += s2(a);\
Remco 2:1991439ea6b8 141 h += maj(a, b, c);
Remco 2:1991439ea6b8 142
Remco 2:1991439ea6b8 143 #define W(n) w[(n) & 0xf]
Remco 2:1991439ea6b8 144
Remco 2:1991439ea6b8 145 #define ROUND2(a,b,c,d,e,f,g,h,i) \
Remco 2:1991439ea6b8 146 W(i) += s0(W(i+1)) + W(i+9) + s1(W(i+14));\
Remco 2:1991439ea6b8 147 h += W(i); \
Remco 2:1991439ea6b8 148 h += *K++;\
Remco 2:1991439ea6b8 149 h += s3(e);\
Remco 2:1991439ea6b8 150 h += ch(e, f, g); \
Remco 2:1991439ea6b8 151 d += h;\
Remco 2:1991439ea6b8 152 h += s2(a);\
Remco 2:1991439ea6b8 153 h += maj(a, b, c);
Remco 2:1991439ea6b8 154
Remco 0:772b6de3a841 155 // Process a 512 bit chunk stored in w[1...15]
Remco 0:772b6de3a841 156 void SHA256::process_chunk()
Remco 0:772b6de3a841 157 {
Remco 0:772b6de3a841 158 // Initialize using current hash
Remco 0:772b6de3a841 159 unsigned int a = hash[0];
Remco 0:772b6de3a841 160 unsigned int b = hash[1];
Remco 0:772b6de3a841 161 unsigned int c = hash[2];
Remco 0:772b6de3a841 162 unsigned int d = hash[3];
Remco 0:772b6de3a841 163 unsigned int e = hash[4];
Remco 0:772b6de3a841 164 unsigned int f = hash[5];
Remco 0:772b6de3a841 165 unsigned int g = hash[6];
Remco 0:772b6de3a841 166 unsigned int h = hash[7];
Remco 0:772b6de3a841 167
Remco 0:772b6de3a841 168 // Main loop
Remco 2:1991439ea6b8 169 const unsigned int* K = k;
Remco 2:1991439ea6b8 170 const unsigned int* K_end = k + 64;
Remco 2:1991439ea6b8 171 ROUND(a,b,c,d,e,f,g,h,0);
Remco 2:1991439ea6b8 172 ROUND(h,a,b,c,d,e,f,g,1);
Remco 2:1991439ea6b8 173 ROUND(g,h,a,b,c,d,e,f,2);
Remco 2:1991439ea6b8 174 ROUND(f,g,h,a,b,c,d,e,3);
Remco 2:1991439ea6b8 175 ROUND(e,f,g,h,a,b,c,d,4);
Remco 2:1991439ea6b8 176 ROUND(d,e,f,g,h,a,b,c,5);
Remco 2:1991439ea6b8 177 ROUND(c,d,e,f,g,h,a,b,6);
Remco 2:1991439ea6b8 178 ROUND(b,c,d,e,f,g,h,a,7);
Remco 2:1991439ea6b8 179 ROUND(a,b,c,d,e,f,g,h,8);
Remco 2:1991439ea6b8 180 ROUND(h,a,b,c,d,e,f,g,9);
Remco 2:1991439ea6b8 181 ROUND(g,h,a,b,c,d,e,f,10);
Remco 2:1991439ea6b8 182 ROUND(f,g,h,a,b,c,d,e,11);
Remco 2:1991439ea6b8 183 ROUND(e,f,g,h,a,b,c,d,12);
Remco 2:1991439ea6b8 184 ROUND(d,e,f,g,h,a,b,c,13);
Remco 2:1991439ea6b8 185 ROUND(c,d,e,f,g,h,a,b,14);
Remco 2:1991439ea6b8 186 ROUND(b,c,d,e,f,g,h,a,15);
Remco 2:1991439ea6b8 187 do {
Remco 2:1991439ea6b8 188 ROUND2(a,b,c,d,e,f,g,h,0);
Remco 2:1991439ea6b8 189 ROUND2(h,a,b,c,d,e,f,g,1);
Remco 2:1991439ea6b8 190 ROUND2(g,h,a,b,c,d,e,f,2);
Remco 2:1991439ea6b8 191 ROUND2(f,g,h,a,b,c,d,e,3);
Remco 2:1991439ea6b8 192 ROUND2(e,f,g,h,a,b,c,d,4);
Remco 2:1991439ea6b8 193 ROUND2(d,e,f,g,h,a,b,c,5);
Remco 2:1991439ea6b8 194 ROUND2(c,d,e,f,g,h,a,b,6);
Remco 2:1991439ea6b8 195 ROUND2(b,c,d,e,f,g,h,a,7);
Remco 2:1991439ea6b8 196 ROUND2(a,b,c,d,e,f,g,h,8);
Remco 2:1991439ea6b8 197 ROUND2(h,a,b,c,d,e,f,g,9);
Remco 2:1991439ea6b8 198 ROUND2(g,h,a,b,c,d,e,f,10);
Remco 2:1991439ea6b8 199 ROUND2(f,g,h,a,b,c,d,e,11);
Remco 2:1991439ea6b8 200 ROUND2(e,f,g,h,a,b,c,d,12);
Remco 2:1991439ea6b8 201 ROUND2(d,e,f,g,h,a,b,c,13);
Remco 2:1991439ea6b8 202 ROUND2(c,d,e,f,g,h,a,b,14);
Remco 2:1991439ea6b8 203 ROUND2(b,c,d,e,f,g,h,a,15);
Remco 2:1991439ea6b8 204 } while(K != K_end);
Remco 0:772b6de3a841 205
Remco 0:772b6de3a841 206 // Update hash
Remco 0:772b6de3a841 207 hash[0] += a;
Remco 0:772b6de3a841 208 hash[1] += b;
Remco 0:772b6de3a841 209 hash[2] += c;
Remco 0:772b6de3a841 210 hash[3] += d;
Remco 0:772b6de3a841 211 hash[4] += e;
Remco 0:772b6de3a841 212 hash[5] += f;
Remco 0:772b6de3a841 213 hash[6] += g;
Remco 0:772b6de3a841 214 hash[7] += h;
Remco 0:772b6de3a841 215 }
Remco 0:772b6de3a841 216
Remco 0:772b6de3a841 217