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

[Johannes Schindelin <Johannes.Schindelin@gmx.de>]

Hi Scott,

On Tue, 29 Sep 2026, Scott Chacon wrote:

> diff --git a/sha1dc-accel/sha1.c b/sha1dc-accel/sha1.c
> new file mode 100644
> index 0000000000..fd75289997
> --- /dev/null
> +++ b/sha1dc-accel/sha1.c
> @@ -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
> +

The following lines, including the definition of `compress_portable()`,
duplicate the functionality implemented in `sha1_compression_states()` in
sha1dc/. Maybe we could use that latter function here, too, to make the
code DRYer?

> +/*
> + * 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;
> +}

Ciao,
Johannes