[v4,00/12] Base SHA-256 implementation

Message

brian m. carlson Oct. 25, 2018, 2:39 a.m. UTC

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.sh

Range-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