[PATCH v4 00/12] Base SHA-256 implementation
- From
brian m. carlson <sandals@crustytoothpaste.net>
- Date
- Oct 25, 2018, 02:39 UTC
- Message-ID
- <20181025024005.154208-1-sandals@crustytoothpaste.net>
This series provides a functional SHA-256 implementation and wires it up, along with some housekeeping patches to make it suitable for testing.
While I was fixing the macros, I wondered if I could make the code a bit cleaner by using inline functions. I tried it and found that not only did it make the code cleaner, it made the code significantly faster across all sizes of output, with larger gains on larger chunks (e.g., 214 MiB/s on 16 KiB chunks vs 151 MiB/s). I'm unsure why this effect occurs, but I figured nobody would complain about improved performance.
Changes from v3: * Switch to using inline functions instead of macros in many cases. * Undefine remaining macros at the top.
Changes from v2: * Improve commit messages to include timing and performance information. * Improve commit messages to be less ambiguous and more friendly to a wider variety of English speakers. * Prefer functions taking struct git_hash_algo in hex.c. * Port pieces of the block-sha1 implementation over to the block-sha256 implementation for better compatibility. * Drop patch 13 in favor of further discussion about the best way forward for versioning commit graph. * Rename the test so as to have a different number from other tests. * Rebase on master.
Changes from v1: * Add a hash_to_hex function mirroring sha1_to_hex, but for the_hash_algo. * Strip commit message explanation about why we chose SHA-256. * Rebase on master * Strip leading whitespace from commit message. * Improve commit-graph patch to cover new code added since v1. * Be more honest about the scope of work involved in porting the SHA-256 implementation out of libtomcrypt. * Revert change to limit hashcmp to 20 bytes.
brian m. carlson (12): sha1-file: rename algorithm to "sha1" sha1-file: provide functions to look up hash algorithms hex: introduce functions to print arbitrary hashes cache: make hashcmp and hasheq work with larger hashes t: add basic tests for our SHA-1 implementation t: make the sha1 test-tool helper generic sha1-file: add a constant for hash block size t/helper: add a test helper to compute hash speed commit-graph: convert to using the_hash_algo Add a base implementation of SHA-256 support sha256: add an SHA-256 implementation using libgcrypt hash: add an SHA-256 implementation using OpenSSL
Makefile | 22 +++
cache.h | 51 ++++---
commit-graph.c | 33 +++--
hash.h | 41 +++++-
hex.c | 32 +++-
sha1-file.c | 70 ++++++++-
sha256/block/sha256.c | 201 ++++++++++++++++++++++++++
sha256/block/sha256.h | 26 ++++
sha256/gcrypt.h | 30 ++++
t/helper/test-hash-speed.c | 61 ++++++++
t/helper/{test-sha1.c => test-hash.c} | 19 +--
t/helper/test-sha1.c | 52 +------
t/helper/test-sha256.c | 7 +
t/helper/test-tool.c | 2 +
t/helper/test-tool.h | 4 +
t/t0015-hash.sh | 54 +++++++
16 files changed, 601 insertions(+), 104 deletions(-)
create mode 100644 sha256/block/sha256.c
create mode 100644 sha256/block/sha256.h
create mode 100644 sha256/gcrypt.h
create mode 100644 t/helper/test-hash-speed.c
copy t/helper/{test-sha1.c => test-hash.c} (65%)
create mode 100644 t/helper/test-sha256.c
create mode 100755 t/t0015-hash.shRange-diff against v3:
1: a004a4c982 < -: ---------- :hash-impl
2: cf9f7f5620 = 1: cf9f7f5620 sha1-file: rename algorithm to "sha1"
3: 0144deaebe = 2: 0144deaebe sha1-file: provide functions to look up hash algorithms
4: b74858fb03 = 3: b74858fb03 hex: introduce functions to print arbitrary hashes
5: e9703017a4 = 4: e9703017a4 cache: make hashcmp and hasheq work with larger hashes
6: ab85a834fd = 5: ab85a834fd t: add basic tests for our SHA-1 implementation
7: 962f6d8903 = 6: 962f6d8903 t: make the sha1 test-tool helper generic
8: 53addf4d58 = 7: 53addf4d58 sha1-file: add a constant for hash block size
9: 9ace10faa2 = 8: 9ace10faa2 t/helper: add a test helper to compute hash speed
10: 9adc56d01e = 9: 9adc56d01e commit-graph: convert to using the_hash_algo
11: 8e82cb0dfb ! 10: f48cb1ad27 Add a base implementation of SHA-256 support
@@ -207,6 +207,9 @@
+#include "git-compat-util.h"
+#include "./sha256.h"
+
++#undef RND
++#undef BLKSIZE
++
+#define BLKSIZE blk_SHA256_BLKSIZE
+
+void blk_SHA256_Init(blk_SHA256_CTX *ctx)
@@ -228,14 +231,35 @@
+ return (x >> n) | (x << (32 - n));
+}
+
-+#define Ch(x,y,z) (z ^ (x & (y ^ z)))
-+#define Maj(x,y,z) (((x | y) & z) | (x & y))
-+#define S(x, n) ror((x),(n))
-+#define R(x, n) ((x)>>(n))
-+#define Sigma0(x) (S(x, 2) ^ S(x, 13) ^ S(x, 22))
-+#define Sigma1(x) (S(x, 6) ^ S(x, 11) ^ S(x, 25))
-+#define Gamma0(x) (S(x, 7) ^ S(x, 18) ^ R(x, 3))
-+#define Gamma1(x) (S(x, 17) ^ S(x, 19) ^ R(x, 10))
++static inline uint32_t ch(uint32_t x, uint32_t y, uint32_t z)
++{
++ return (z ^ (x & (y ^ z)));
++}
++
++static inline uint32_t maj(uint32_t x, uint32_t y, uint32_t z)
++{
++ return (((x | y) & z) | (x & y));
++}
++
++static inline uint32_t sigma0(uint32_t x)
++{
++ return ror(x, 2) ^ ror(x, 13) ^ ror(x, 22);
++}
++
++static inline uint32_t sigma1(uint32_t x)
++{
++ return ror(x, 6) ^ ror(x, 11) ^ ror(x, 25);
++}
++
++static inline uint32_t gamma0(uint32_t x)
++{
++ return ror(x, 7) ^ ror(x, 18) ^ (x >> 3);
++}
++
++static inline uint32_t gamma1(uint32_t x)
++{
++ return ror(x, 17) ^ ror(x, 19) ^ (x >> 10);
++}
+
+static void blk_SHA256_Transform(blk_SHA256_CTX *ctx, const unsigned char *buf)
+{
@@ -255,12 +279,12 @@
+
+ /* fill W[16..63] */
+ for (i = 16; i < 64; i++) {
-+ W[i] = Gamma1(W[i - 2]) + W[i - 7] + Gamma0(W[i - 15]) + W[i - 16];
++ W[i] = gamma1(W[i - 2]) + W[i - 7] + gamma0(W[i - 15]) + W[i - 16];
+ }
+
+#define RND(a,b,c,d,e,f,g,h,i,ki) \
-+ t0 = h + Sigma1(e) + Ch(e, f, g) + ki + W[i]; \
-+ t1 = Sigma0(a) + Maj(a, b, c); \
++ t0 = h + sigma1(e) + ch(e, f, g) + ki + W[i]; \
++ t1 = sigma0(a) + maj(a, b, c); \
+ d += t0; \
+ h = t0 + t1;
+
@@ -329,15 +353,6 @@
+ RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],62,0xbef9a3f7);
+ RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],63,0xc67178f2);
+
-+#undef RND
-+#undef Ch
-+#undef Maj
-+#undef S
-+#undef R
-+#undef Sigma0
-+#undef Sigma1
-+#undef Gamma0
-+#undef Gamma1
+
+ for (i = 0; i < 8; i++) {
+ ctx->state[i] = ctx->state[i] + S[i];
12: 9e0061bd74 = 11: fe8f2ba01c sha256: add an SHA-256 implementation using libgcrypt
13: 128d6b8150 = 12: 38142d8fc6 hash: add an SHA-256 implementation using OpenSSL