[PATCH 1/4] sha1dc-accel: add a block loop for sha1dc's SHA1_CTX

@@ -567,6 +567,10 @@ include shared.mak
 # by the git project to migrate to using sha1collisiondetection as a
 # submodule.
 #
+# Unless DC_SHA1_EXTERNAL is defined, the built-in code is driven by the
+# block loop in sha1dc-accel/, which gives the same results.
+# Define DC_SHA1_NO_ACCEL to use the sha1collisiondetection code alone.
+#
 # === SHA-256 backend ===
 #
 # ==== Security ====

@@ -1555,6 +1559,7 @@ CLAR_TEST_SUITES += u-reftable-readwrite
 CLAR_TEST_SUITES += u-reftable-stack
 CLAR_TEST_SUITES += u-reftable-table
 CLAR_TEST_SUITES += u-reftable-tree
+CLAR_TEST_SUITES += u-sha1dc
 CLAR_TEST_SUITES += u-strbuf
 CLAR_TEST_SUITES += u-strcmp-offset
 CLAR_TEST_SUITES += u-string-list

@@ -2167,6 +2172,11 @@ ifdef DC_SHA1_SUBMODULE
 else
 	LIB_OBJS += sha1dc/sha1.o
 	LIB_OBJS += sha1dc/ubc_check.o
+endif
+ifdef DC_SHA1_NO_ACCEL
+	BASIC_CFLAGS += -DDC_SHA1_NO_ACCEL
+else
+	LIB_OBJS += sha1dc-accel/sha1.o
 endif
 	BASIC_CFLAGS += \
 		-DSHA1DC_NO_STANDARD_INCLUDES \

@@ -218,7 +218,7 @@ add_compile_definitions(NO_OPENSSL SHA1_DC SHA1DC_NO_STANDARD_INCLUDES
 			SHA1DC_INIT_SAFE_HASH_DEFAULT=0
 			SHA1DC_CUSTOM_INCLUDE_SHA1_C="git-compat-util.h"
 			SHA1DC_CUSTOM_INCLUDE_UBC_CHECK_C="git-compat-util.h" )
-list(APPEND compat_SOURCES sha1dc_git.c sha1dc/sha1.c sha1dc/ubc_check.c block-sha1/sha1.c sha256/block/sha256.c compat/qsort_s.c)
+list(APPEND compat_SOURCES sha1dc_git.c sha1dc/sha1.c sha1dc/ubc_check.c sha1dc-accel/sha1.c block-sha1/sha1.c sha256/block/sha256.c compat/qsort_s.c)
 
 
 add_compile_definitions(PAGER_ENV="LESS=FRX LV=-c"

@@ -1631,6 +1631,7 @@ if sha1_backend == 'sha1dc'
     'sha1dc_git.c',
     'sha1dc/sha1.c',
     'sha1dc/ubc_check.c',
+    'sha1dc-accel/sha1.c',
   ]
 endif
 if sha1_backend == 'CommonCrypto' or sha1_unsafe_backend == 'CommonCrypto'

@@ -0,0 +1,25 @@
+#ifndef SHA1DC_ACCEL_INTERNAL_H
+#define SHA1DC_ACCEL_INTERNAL_H
+
+/*
+ * Shared between the files of sha1dc-accel/. See sha1.c for an overview.
+ *
+ * The schedule `w` is always the 80 expanded message words in step order,
+ * w[t] at index t, which is also what sha1dc/ keeps in SHA1_CTX.m1.
+ *
+ * A "state" is the five working words [a, b, c, d, e] before a step.
+ */
+
+#if defined(__GNUC__)
+# define SHA1DC_NOINLINE __attribute__((noinline))
+#else
+# define SHA1DC_NOINLINE
+#endif
+
+/* The step a DV's recompression starts from. */
+enum sha1dc_from {
+	SHA1DC_FROM_58 = 58,
+	SHA1DC_FROM_65 = 65
+};
+
+#endif /* SHA1DC_ACCEL_INTERNAL_H */

@@ -0,0 +1,434 @@
+/*
+ * SHA-1 with collision detection.
+ *
+ * This computes exactly what sha1dc/ computes: the SHA-1 digest of the
+ * input, and whether any block of it looks like one half of a collision
+ * made by one of the 32 known disturbance vectors (DVs) of Stevens and
+ * Shumow. It works on sha1dc's SHA1_CTX, and uses its table of DVs, but
+ * has its own block loop, which gives the following patches room to
+ * follow the approach of the "sha1dc" Rust crate by Sam Reis
+ * (https://github.com/srijs/sha1dc), which gitoxide uses.
+ *
+ * Each block is compressed by a "backend", which also spills the expanded
+ * message schedule, and the two intermediate states that recompression
+ * starts from (at steps 58 and 65). The unavoidable-bitconditions (UBC)
+ * filter then rules out about 95% of blocks; the rest are recompressed,
+ * once for each DV the filter could not rule out.
+ */
+
+#include "../git-compat-util.h"
+#include "../sha1dc_git.h"
+#if defined(DC_SHA1_SUBMODULE)
+#include "../sha1collisiondetection/lib/ubc_check.h"
+#else
+#include "../sha1dc/ubc_check.h"
+#endif
+#include "sha1.h"
+#include "internal.h"
+
+#define ROL(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
+
+#define F_CH(b, c, d) ((d) ^ ((b) & ((c) ^ (d))))
+#define F_PARITY(b, c, d) ((b) ^ (c) ^ (d))
+#define F_MAJ(b, c, d) (((b) & (c)) | ((d) & ((b) | (c))))
+
+#define K0 0x5A827999
+#define K1 0x6ED9EBA1
+#define K2 0x8F1BBCDC
+#define K3 0xCA62C1D6
+
+/*
+ * One step, on names that rotate: after it, (e, a, b, c, d) are the new
+ * (a, b, c, d, e).
+ */
+#define STEP(f, k, a, b, c, d, e, x) \
+	do { \
+		e += ROL(a, 5) + f(b, c, d) + (k) + (x); \
+		b = ROL(b, 30); \
+	} while (0)
+
+#define LOAD(t) (w[t] = get_be32(block + 4 * (t)))
+#define EXPAND(t) (w[t] = ROL(w[(t) - 3] ^ w[(t) - 8] ^ w[(t) - 14] ^ w[(t) - 16], 1))
+
+#define FIVE_LOAD(f, k, a, b, c, d, e, t) \
+	do { \
+		STEP(f, k, a, b, c, d, e, LOAD(t)); \
+		STEP(f, k, e, a, b, c, d, LOAD((t) + 1)); \
+		STEP(f, k, d, e, a, b, c, LOAD((t) + 2)); \
+		STEP(f, k, c, d, e, a, b, LOAD((t) + 3)); \
+		STEP(f, k, b, c, d, e, a, LOAD((t) + 4)); \
+	} while (0)
+
+#define FIVE_EXPAND(f, k, a, b, c, d, e, t) \
+	do { \
+		STEP(f, k, a, b, c, d, e, EXPAND(t)); \
+		STEP(f, k, e, a, b, c, d, EXPAND((t) + 1)); \
+		STEP(f, k, d, e, a, b, c, EXPAND((t) + 2)); \
+		STEP(f, k, c, d, e, a, b, EXPAND((t) + 3)); \
+		STEP(f, k, b, c, d, e, a, EXPAND((t) + 4)); \
+	} while (0)
+
+/*
+ * The portable compression. Like the hardware ones it spills the schedule,
+ * but it writes the states at steps 58 and 65 directly, on the way past.
+ */
+static void compress_portable(uint32_t ihv[5], const unsigned char *block,
+			      uint32_t w[80], uint32_t state_58[5],
+			      uint32_t state_65[5])
+{
+	uint32_t a = ihv[0], b = ihv[1], c = ihv[2], d = ihv[3], e = ihv[4];
+
+	FIVE_LOAD(F_CH, K0, a, b, c, d, e, 0);
+	FIVE_LOAD(F_CH, K0, a, b, c, d, e, 5);
+	FIVE_LOAD(F_CH, K0, a, b, c, d, e, 10);
+	STEP(F_CH, K0, a, b, c, d, e, LOAD(15));
+	STEP(F_CH, K0, e, a, b, c, d, EXPAND(16));
+	STEP(F_CH, K0, d, e, a, b, c, EXPAND(17));
+	STEP(F_CH, K0, c, d, e, a, b, EXPAND(18));
+	STEP(F_CH, K0, b, c, d, e, a, EXPAND(19));
+
+	FIVE_EXPAND(F_PARITY, K1, a, b, c, d, e, 20);
+	FIVE_EXPAND(F_PARITY, K1, a, b, c, d, e, 25);
+	FIVE_EXPAND(F_PARITY, K1, a, b, c, d, e, 30);
+	FIVE_EXPAND(F_PARITY, K1, a, b, c, d, e, 35);
+
+	FIVE_EXPAND(F_MAJ, K2, a, b, c, d, e, 40);
+	FIVE_EXPAND(F_MAJ, K2, a, b, c, d, e, 45);
+	FIVE_EXPAND(F_MAJ, K2, a, b, c, d, e, 50);
+	STEP(F_MAJ, K2, a, b, c, d, e, EXPAND(55));
+	STEP(F_MAJ, K2, e, a, b, c, d, EXPAND(56));
+	STEP(F_MAJ, K2, d, e, a, b, c, EXPAND(57));
+	state_58[0] = c;
+	state_58[1] = d;
+	state_58[2] = e;
+	state_58[3] = a;
+	state_58[4] = b;
+	STEP(F_MAJ, K2, c, d, e, a, b, EXPAND(58));
+	STEP(F_MAJ, K2, b, c, d, e, a, EXPAND(59));
+
+	FIVE_EXPAND(F_PARITY, K3, a, b, c, d, e, 60);
+	state_65[0] = a;
+	state_65[1] = b;
+	state_65[2] = c;
+	state_65[3] = d;
+	state_65[4] = e;
+	FIVE_EXPAND(F_PARITY, K3, a, b, c, d, e, 65);
+	FIVE_EXPAND(F_PARITY, K3, a, b, c, d, e, 70);
+	FIVE_EXPAND(F_PARITY, K3, a, b, c, d, e, 75);
+
+	ihv[0] += a;
+	ihv[1] += b;
+	ihv[2] += c;
+	ihv[3] += d;
+	ihv[4] += e;
+}
+
+/*
+ * The rest runs only for blocks the filter flags, about one in twenty, so
+ * it favours being short over being fast.
+ */
+
+/*
+ * Moves `s` from the state before step `from` to the one before step `to`,
+ * either way, on the schedule `m1 ^ dm` (`dm` may be NULL). One loop per
+ * round function keeps the steps free of branches.
+ */
+#define WORD(t) (dm ? m1[t] ^ dm[t] : m1[t])
+#define FORWARD(f, k, end) \
+	for (; t < to && t < (end); t++) { \
+		x = ROL(a, 5) + f(b, c, d) + (k) + e + WORD(t); \
+		e = d; \
+		d = c; \
+		c = ROL(b, 30); \
+		b = a; \
+		a = x; \
+	}
+#define BACKWARD(f, k, start) \
+	for (; t > to && t > (start); t--) { \
+		x = a; \
+		a = b; \
+		b = ROL(c, 2); \
+		c = d; \
+		d = e; \
+		e = x - (ROL(a, 5) + f(b, c, d) + (k) + WORD(t - 1)); \
+	}
+
+static void walk(uint32_t s[5], const uint32_t *m1, const uint32_t *dm,
+		 unsigned from, unsigned to)
+{
+	uint32_t a = s[0], b = s[1], c = s[2], d = s[3], e = s[4], x;
+	unsigned t = from;
+
+	FORWARD(F_CH, K0, 20);
+	FORWARD(F_PARITY, K1, 40);
+	FORWARD(F_MAJ, K2, 60);
+	FORWARD(F_PARITY, K3, 80);
+
+	BACKWARD(F_PARITY, K3, 60);
+	BACKWARD(F_MAJ, K2, 40);
+	BACKWARD(F_PARITY, K1, 20);
+	BACKWARD(F_CH, K0, 0);
+
+	s[0] = a;
+	s[1] = b;
+	s[2] = c;
+	s[3] = d;
+	s[4] = e;
+}
+
+/*
+ * The recompression, the way sha1dc/ does it: from this block's state at
+ * `from`, the partner block's chaining value on the way in (`ihv_in`) and
+ * on the way out (`ihv_out`).
+ */
+static void recompress_portable(enum sha1dc_from from, const uint32_t m1[80],
+				const uint32_t dm[80], const uint32_t state[5],
+				uint32_t ihv_in[5], uint32_t ihv_out[5])
+{
+	uint32_t fwd[5];
+	int i;
+
+	memcpy(ihv_in, state, 5 * sizeof(*ihv_in));
+	walk(ihv_in, m1, dm, from, 0);
+	memcpy(fwd, state, sizeof(fwd));
+	walk(fwd, m1, dm, from, 80);
+	for (i = 0; i < 5; i++)
+		ihv_out[i] = ihv_in[i] + fwd[i];
+}
+
+/* For a mitigated ("safe") hash: one more compression of the schedule. */
+static void compress_schedule(uint32_t ihv[5], const uint32_t w[80])
+{
+	uint32_t s[5];
+	int i;
+
+	memcpy(s, ihv, sizeof(s));
+	walk(s, w, NULL, 0, 80);
+	for (i = 0; i < 5; i++)
+		ihv[i] += s[i];
+}
+
+struct backend {
+	const char *name;
+	/*
+	 * Compresses a block, spilling its schedule and the states at steps
+	 * 58 and 65.
+	 */
+	void (*compress)(uint32_t ihv[5], const unsigned char *block,
+			 uint32_t w[80], uint32_t state_58[5],
+			 uint32_t state_65[5]);
+	uint32_t (*ubc_check)(const uint32_t w[80]);
+	int (*available)(void);
+};
+
+/* sha1dc's own UBC check. */
+static uint32_t ubc_check_sha1dc(const uint32_t w[80])
+{
+	uint32_t mask;
+
+	ubc_check(w, &mask);
+	return mask;
+}
+
+/* In order of preference. */
+static const struct backend backends[] = {
+	{ "portable", compress_portable, ubc_check_sha1dc, NULL },
+};
+
+static int usable(const struct backend *be)
+{
+	return !be->available || be->available();
+}
+
+#if defined(__GNUC__)
+/*
+ * The backend in use, chosen on first use. Threads that race to choose it
+ * all store the same value, with relaxed atomics so that they may.
+ */
+static const struct backend *selected;
+
+static const struct backend *backend(void)
+{
+	const struct backend *be = __atomic_load_n(&selected, __ATOMIC_RELAXED);
+	size_t i;
+
+	if (be)
+		return be;
+	/* The last one, "portable", is always usable. */
+	for (i = 0; !usable(&backends[i]); i++)
+		;
+	be = &backends[i];
+	__atomic_store_n(&selected, be, __ATOMIC_RELAXED);
+	return be;
+}
+
+static void select_backend(const struct backend *be)
+{
+	__atomic_store_n(&selected, be, __ATOMIC_RELAXED);
+}
+#else
+/*
+ * Other compilers only get the portable backend (see internal.h), so
+ * there is nothing to choose, and no shared state to guard.
+ */
+static const struct backend *backend(void)
+{
+	return &backends[0];
+}
+
+static void select_backend(const struct backend *be UNUSED)
+{
+}
+#endif
+
+const char *sha1dc_accel_backend(void)
+{
+	return backend()->name;
+}
+
+int sha1dc_accel_select(const char *name)
+{
+	size_t i;
+
+	for (i = 0; i < ARRAY_SIZE(backends); i++) {
+		if (!strcmp(backends[i].name, name) && usable(&backends[i])) {
+			select_backend(&backends[i]);
+			return 0;
+		}
+	}
+	return -1;
+}
+
+const char *const *sha1dc_accel_backends(void)
+{
+	static const char *names[ARRAY_SIZE(backends) + 1];
+	size_t i, n = 0;
+
+	for (i = 0; i < ARRAY_SIZE(backends); i++)
+		if (usable(&backends[i]))
+			names[n++] = backends[i].name;
+	names[n] = NULL;
+	return names;
+}
+
+/*
+ * Whether any DV in `candidates` makes this block half of a collision.
+ * `ihv_in` and `ihv_out` are the chaining values before and after it.
+ */
+static SHA1DC_NOINLINE int attacked(SHA1_CTX *ctx, uint32_t candidates,
+				    const uint32_t w[80],
+				    const uint32_t state_58[5],
+				    const uint32_t state_65[5],
+				    const uint32_t ihv_in[5],
+				    const uint32_t ihv_out[5])
+{
+	int i;
+
+	for (i = 0; sha1_dvs[i].dvType != 0; i++) {
+		const dv_info_t *dv = &sha1_dvs[i];
+		enum sha1dc_from from;
+		const uint32_t *state;
+		uint32_t ihv2_in[5], ihv2_out[5];
+
+		if (!(candidates & ((uint32_t)1 << dv->maskb)))
+			continue;
+		switch (dv->testt) {
+		case 58:
+			from = SHA1DC_FROM_58;
+			state = state_58;
+			break;
+		case 65:
+			from = SHA1DC_FROM_65;
+			state = state_65;
+			break;
+		default:
+			BUG("sha1dc DV %d(%d,%d) recompresses from step %d, "
+			    "which sha1dc-accel does not save",
+			    dv->dvType, dv->dvK, dv->dvB, dv->testt);
+		}
+
+		recompress_portable(from, w, dv->dm, state, ihv2_in, ihv2_out);
+		if (!memcmp(ihv2_out, ihv_out, sizeof(ihv2_out)) ||
+		    (ctx->reduced_round_coll &&
+		     !memcmp(ihv2_in, ihv_in, sizeof(ihv2_in))))
+			return 1;
+	}
+	return 0;
+}
+
+static inline void process(const struct backend *be, SHA1_CTX *ctx,
+			   const unsigned char *block)
+{
+	uint32_t w[80], state_58[5], state_65[5], ihv_in[5], candidates;
+
+	memcpy(ihv_in, ctx->ihv, sizeof(ihv_in));
+	be->compress(ctx->ihv, block, w, state_58, state_65);
+	if (!ctx->detect_coll)
+		return;
+
+	candidates = ctx->ubc_check ? be->ubc_check(w) : 0xFFFFFFFF;
+	if (candidates &&
+	    attacked(ctx, candidates, w, state_58, state_65, ihv_in,
+		     ctx->ihv)) {
+		ctx->found_collision = 1;
+		/*
+		 * Two more compressions of this block give a digest that the
+		 * other block of the pair does not share.
+		 */
+		if (ctx->safe_hash) {
+			compress_schedule(ctx->ihv, w);
+			compress_schedule(ctx->ihv, w);
+		}
+	}
+}
+
+void sha1dc_accel_update(SHA1_CTX *ctx, const void *data, size_t len)
+{
+	const struct backend *be = backend();
+	const unsigned char *buf = data;
+	unsigned left, fill;
+
+	if (!len)
+		return;
+
+	left = ctx->total & 63;
+	fill = 64 - left;
+
+	if (left && len >= fill) {
+		ctx->total += fill;
+		memcpy(ctx->buffer + left, buf, fill);
+		process(be, ctx, ctx->buffer);
+		buf += fill;
+		len -= fill;
+		left = 0;
+	}
+	while (len >= 64) {
+		ctx->total += 64;
+		process(be, ctx, buf);
+		buf += 64;
+		len -= 64;
+	}
+	if (len) {
+		ctx->total += len;
+		memcpy(ctx->buffer + left, buf, len);
+	}
+}
+
+int sha1dc_accel_final(unsigned char hash[20], SHA1_CTX *ctx)
+{
+	static const unsigned char padding[64] = { 0x80 };
+	uint32_t last = ctx->total & 63;
+	uint32_t padn = last < 56 ? 56 - last : 120 - last;
+	uint64_t bits;
+	int i;
+
+	sha1dc_accel_update(ctx, padding, padn);
+	bits = (ctx->total - padn) << 3;
+	put_be32(ctx->buffer + 56, (uint32_t)(bits >> 32));
+	put_be32(ctx->buffer + 60, (uint32_t)bits);
+	process(backend(), ctx, ctx->buffer);
+
+	for (i = 0; i < 5; i++)
+		put_be32(hash + 4 * i, ctx->ihv[i]);
+	return ctx->found_collision;
+}

@@ -0,0 +1,31 @@
+#ifndef SHA1DC_ACCEL_SHA1_H
+#define SHA1DC_ACCEL_SHA1_H
+
+#if defined(DC_SHA1_SUBMODULE)
+#include "../sha1collisiondetection/lib/sha1.h"
+#else
+#include "../sha1dc/sha1.h"
+#endif
+
+/*
+ * A faster implementation of SHA-1 with collision detection, working on
+ * the SHA1_CTX of sha1dc/ (or of the sha1collisiondetection submodule).
+ * SHA1DCInit() and the SHA1DCSet*() functions set it up as usual; these
+ * then take the place of SHA1DCUpdate() and SHA1DCFinal(), with the same
+ * results. See sha1.c.
+ */
+
+void sha1dc_accel_update(SHA1_CTX *ctx, const void *data, size_t len);
+int sha1dc_accel_final(unsigned char hash[20], SHA1_CTX *ctx);
+
+/*
+ * The implementation in use, such as "shani+avx2" or "portable". For tests,
+ * sha1dc_accel_select() switches to another one by that name; it returns -1
+ * if this build or CPU does not have it. Neither is thread-safe.
+ */
+const char *sha1dc_accel_backend(void);
+int sha1dc_accel_select(const char *name);
+/* The names this build and CPU can use, NULL-terminated. */
+const char *const *sha1dc_accel_backends(void);
+
+#endif /* SHA1DC_ACCEL_SHA1_H */

@@ -2,6 +2,15 @@
 #include "sha1dc_git.h"
 #include "hex.h"
 
+/*
+ * Unless told otherwise, hash with sha1dc-accel/, which gives the same
+ * results as sha1dc/ on the same SHA1_CTX.
+ */
+#if !defined(DC_SHA1_EXTERNAL) && !defined(DC_SHA1_NO_ACCEL)
+#include "sha1dc-accel/sha1.h"
+#define USE_SHA1DC_ACCEL
+#endif
+
 #ifdef DC_SHA1_EXTERNAL
 /*
  * Same as SHA1DCInit, but with default save_hash=0

@@ -18,8 +27,13 @@ void git_SHA1DCInit(SHA1_CTX *ctx)
  */
 void git_SHA1DCFinal(unsigned char hash[20], SHA1_CTX *ctx)
 {
+#ifdef USE_SHA1DC_ACCEL
+	if (!sha1dc_accel_final(hash, ctx))
+		return;
+#else
 	if (!SHA1DCFinal(hash, ctx))
 		return;
+#endif
 	die("SHA-1 appears to be part of a collision attack: %s",
 	    hash_to_hex_algop(hash, &hash_algos[GIT_HASH_SHA1]));
 }

@@ -29,6 +43,9 @@ void git_SHA1DCFinal(unsigned char hash[20], SHA1_CTX *ctx)
  */
 void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *vdata, size_t len)
 {
+#ifdef USE_SHA1DC_ACCEL
+	sha1dc_accel_update(ctx, vdata, len);
+#else
 	const char *data = vdata;
 	while (len > INT_MAX) {
 		SHA1DCUpdate(ctx, data, INT_MAX);

@@ -36,4 +53,5 @@ void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *vdata, size_t len)
 		len -= INT_MAX;
 	}
 	SHA1DCUpdate(ctx, data, len);
+#endif
 }

@@ -2,6 +2,7 @@ t[0-9][0-9][0-9][0-9]/* -whitespace
 /chainlint/*.expect eol=lf -whitespace
 /greplint/*.expect eol=lf -whitespace
 /greplint/*.test eol=lf -whitespace
+/t0013/*.bin binary
 /t0110/url-* binary
 /t3206/* eol=lf
 /t3900/*.txt eol=lf

@@ -1,8 +1,20 @@
 #include "test-tool.h"
 #include "hash.h"
+#include "strbuf.h"
+
+#if defined(SHA1_DC) && !defined(DC_SHA1_EXTERNAL) && !defined(DC_SHA1_NO_ACCEL)
+#include "sha1dc-accel/sha1.h"
+#define HAVE_SHA1DC_ACCEL
+#endif
 
 int cmd__sha1(int ac, const char **av)
 {
+#ifdef HAVE_SHA1DC_ACCEL
+	const char *backend = getenv("GIT_TEST_SHA1DC_BACKEND");
+
+	if (backend && sha1dc_accel_select(backend))
+		die("sha1dc backend '%s' is not available", backend);
+#endif
 	return cmd_hash_impl(ac, av, GIT_HASH_SHA1, 0);
 }
 

@@ -14,6 +26,89 @@ int cmd__sha1_is_sha1dc(int argc UNUSED, const char **argv UNUSED)
 	return 1;
 }
 
+/*
+ * Lists the implementations of collision-detecting SHA-1 this build and
+ * CPU can use, which GIT_TEST_SHA1DC_BACKEND selects for "test-tool sha1".
+ */
+int cmd__sha1dc_backends(int argc UNUSED, const char **argv UNUSED)
+{
+#ifdef HAVE_SHA1DC_ACCEL
+	const char *const *names;
+
+	for (names = sha1dc_accel_backends(); *names; names++)
+		puts(*names);
+#endif
+	return 0;
+}
+
+/*
+ * Hashes a file with sha1dc/ and with sha1dc-accel/ (the backend that
+ * GIT_TEST_SHA1DC_BACKEND selects), under every combination of settings,
+ * and dies if they ever disagree on the digest or on whether there is a
+ * collision. sha1dc-accel/ sees the file split at and around every block
+ * boundary, with an empty update in between. Prints what sha1dc/ found for
+ * each combination.
+ */
+int cmd__sha1dc_compare(int argc MAYBE_UNUSED, const char **argv MAYBE_UNUSED)
+{
+#ifdef HAVE_SHA1DC_ACCEL
+	const char *backend = getenv("GIT_TEST_SHA1DC_BACKEND");
+	struct strbuf buf = STRBUF_INIT;
+	int mode;
+
+	if (argc != 2)
+		die("usage: test-tool sha1dc-compare <file>");
+	if (backend && sha1dc_accel_select(backend))
+		die("sha1dc backend '%s' is not available", backend);
+	if (strbuf_read_file(&buf, argv[1], 0) < 0)
+		die_errno("could not read '%s'", argv[1]);
+
+	for (mode = 0; mode < 16; mode++) {
+		int detect = !!(mode & 8), safe = !!(mode & 4);
+		int ubc = !!(mode & 2), reduced = !!(mode & 1);
+		unsigned char want[20], got[20];
+		SHA1_CTX init, ctx;
+		int want_coll, got_coll, i;
+		size_t split;
+
+		SHA1DCInit(&init);
+		SHA1DCSetUseDetectColl(&init, detect);
+		SHA1DCSetSafeHash(&init, safe);
+		SHA1DCSetUseUBC(&init, ubc);
+		SHA1DCSetDetectReducedRoundCollision(&init, reduced);
+
+		ctx = init;
+		SHA1DCUpdate(&ctx, buf.buf, buf.len);
+		want_coll = SHA1DCFinal(want, &ctx);
+
+		for (split = 0; split <= buf.len; split++) {
+			if (split % 64 > 1 && split % 64 < 63 && split != buf.len)
+				continue;
+			ctx = init;
+			sha1dc_accel_update(&ctx, buf.buf, split);
+			sha1dc_accel_update(&ctx, buf.buf + split, 0);
+			sha1dc_accel_update(&ctx, buf.buf + split, buf.len - split);
+			got_coll = sha1dc_accel_final(got, &ctx);
+			if (got_coll != want_coll || memcmp(got, want, sizeof(got)))
+				die("%s disagrees with sha1dc/ on '%s' with detect=%d "
+				    "safe=%d ubc=%d reduced=%d, split at %"PRIuMAX,
+				    sha1dc_accel_backend(), argv[1], detect, safe,
+				    ubc, reduced, (uintmax_t)split);
+		}
+
+		printf("detect=%d safe=%d ubc=%d reduced=%d collision=%d ",
+		       detect, safe, ubc, reduced, want_coll);
+		for (i = 0; i < 20; i++)
+			printf("%02x", want[i]);
+		putchar('\n');
+	}
+	strbuf_release(&buf);
+	return 0;
+#else
+	die("test-tool sha1dc-compare: not built with sha1dc-accel");
+#endif
+}
+
 int cmd__sha1_unsafe(int ac, const char **av)
 {
 	return cmd_hash_impl(ac, av, GIT_HASH_SHA1, 1);

@@ -73,6 +73,8 @@ static struct test_cmd cmds[] = {
 	{ "serve-v2", cmd__serve_v2 },
 	{ "sha1", cmd__sha1 },
 	{ "sha1-is-sha1dc", cmd__sha1_is_sha1dc },
+	{ "sha1dc-backends", cmd__sha1dc_backends },
+	{ "sha1dc-compare", cmd__sha1dc_compare },
 	{ "sha1-unsafe", cmd__sha1_unsafe },
 	{ "sha256", cmd__sha256 },
 	{ "sigchain", cmd__sigchain },