From: Scott Chacon Date: Tue, 29 Sep 2026 11:25:40 GMT Subject: [PATCH 0/4] faster SHA-1 collision detection Message-ID: <20260929112544.86511-1-scott@gitbutler.net> So, spoiler alert, the code in this patch series is mainly AI generated. I would try to fool you, but too many of you are far too aware of my actual C skills. That being said, I thought maybe someone here (especially those of you working on server optimization stuff) would be interested in the speed increases for both the server and client in making sha1dc quite a bit faster. This series ports the approach of Sam Reis's sha1dc Rust crate [1], which gitoxide recently switched to [2], to C. The end result hashes roughly 2.7x faster on the Xeon and 2.85x faster on the M5 Max. Single-threaded index-pack of git.git goes from 24.3s to 12.7s on the Xeon, and from 16.1s to 8.7s on the M5 Max. Hashing throughput on the Xeon, in MiB/s: 16KiB 1MiB vs OpenSSL OpenSSL SHA-1 (no detection) 1234 1129 1.00x sha1dc/ (today) 435 450 2.67x shani+avx2 (default here) 1002 901 1.24x shani+sse2 1075 1008 1.13x portable+avx2 553 654 1.96x portable+sse2 603 681 1.84x portable 466 565 2.29x In other words, currently collision detection costs about 1.5–2.5x on top of the hashing itself today, but only about 0.2x with the series. The patches are: [1/4]: sha1dc-accel: add a block loop for sha1dc's SHA1_CTX Just groundwork: our own block loop around sha1dc's context and DV table, with the same results and a few percent slower, plus tests that compare against sha1dc/ directly, including on real collisions in every mode. [2/4]: sha1dc-accel: vectorize the unavoidable-bitconditions check The UBC filter rewritten as SSE2, AVX2, NEON, and new scalar forms, using the conditions the crate's solver picks for each. They're carried as tables, with a short loop per form to run them. 1.29x on the Xeon, 1.27x on the M5 Max. [3/4]: sha1dc-accel: compress with SHA-NI on x86-64 Hardware compression, with the schedule spilled, and recompression of flagged blocks in hardware, too. Another 2.07x on the Xeon. [4/4]: sha1dc-accel: compress with the ARMv8 SHA-1 instructions The same for arm64. Another 2.4x on the M5 Max. The x86 numbers are from a 4-vCPU Xeon VM with SHA-NI and AVX2 (GCC 13, Linux), which is unfortunately rather noisy; the per-patch hyperfine output has the spread. The arm64 numbers are medians of 9 runs on an Apple M5 Max (Apple clang, macOS). The full test suite passes on both. [1] https://sam.dev/blog/faster-sha1-collision-detection [2] https://github.com/GitoxideLabs/gitoxide/pull/3008 Scott Chacon (4): sha1dc-accel: add a block loop for sha1dc's SHA1_CTX sha1dc-accel: vectorize the unavoidable-bitconditions check sha1dc-accel: compress with SHA-NI on x86-64 sha1dc-accel: compress with the ARMv8 SHA-1 instructions Makefile | 14 + contrib/buildsystems/CMakeLists.txt | 2 +- meson.build | 4 + sha1dc-accel/arm.c | 274 ++++ sha1dc-accel/internal.h | 126 ++ sha1dc-accel/sha1.c | 498 ++++++++ sha1dc-accel/sha1.h | 31 + sha1dc-accel/ubc_check.c | 1789 +++++++++++++++++++++++++++ sha1dc-accel/x86.c | 260 ++++ sha1dc_git.c | 18 + t/.gitattributes | 1 + t/helper/test-sha1.c | 95 ++ t/helper/test-tool.c | 2 + t/helper/test-tool.h | 2 + t/meson.build | 1 + t/t0013-sha1dc.sh | 47 + t/t0013/sha-mbles-1.bin | Bin 0 -> 640 bytes t/t0013/sha1-reduced-round.bin | Bin 0 -> 128 bytes t/unit-tests/u-sha1dc.c | 366 ++++++ 19 files changed, 3529 insertions(+), 1 deletion(-) create mode 100644 sha1dc-accel/arm.c create mode 100644 sha1dc-accel/internal.h create mode 100644 sha1dc-accel/sha1.c create mode 100644 sha1dc-accel/sha1.h create mode 100644 sha1dc-accel/ubc_check.c create mode 100644 sha1dc-accel/x86.c create mode 100644 t/t0013/sha-mbles-1.bin create mode 100644 t/t0013/sha1-reduced-round.bin create mode 100644 t/unit-tests/u-sha1dc.c base-commit: a018953688f1b10bddf91bff8747068f5f4746a4 -- 2.50.1 (Apple Git-155)