[PATCH 0/4] faster SHA-1 collision detection

[Scott Chacon <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)