From: Johannes Schindelin Date: Wed, 07 Oct 2026 12:17:31 GMT Subject: Re: [PATCH 1/4] sha1dc-accel: add a block loop for sha1dc's SHA1_CTX Message-ID: In-Reply-To: <20260929112544.86511-2-scott@gitbutler.net> 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