{"thread":{"id":"66420","subject":"[PATCH 0/4] faster SHA-1 collision detection","startedAt":"2026-09-29T11:25:49Z","lastAt":"2026-09-29T11:26:08Z","messageCount":5,"participants":["Scott Chacon"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"553583","messageId":"20260929112544.86511-1-scott@gitbutler.net","threadId":"66420","inReplyTo":null,"subject":"[PATCH 0/4] faster SHA-1 collision detection","fromName":"Scott Chacon","fromEmail":"scott@gitbutler.net","sentAt":"2026-09-29T11:25:40Z","receivedAt":"2026-09-29T11:25:49Z","isPatch":true,"body":"So, spoiler alert, the code in this patch series is mainly AI generated.\nI would try to fool you, but too many of you are far too aware of my\nactual C skills. That being said, I thought maybe someone here (especially\nthose of you working on server optimization stuff) would be interested\nin the speed increases for both the server and client in making sha1dc\nquite a bit faster.\n\nThis series ports the approach of Sam Reis's sha1dc Rust crate [1], \nwhich gitoxide recently switched to [2], to C. \n\nThe end result hashes roughly 2.7x faster on the Xeon and 2.85x faster\non the M5 Max. Single-threaded index-pack of git.git goes from 24.3s to\n12.7s on the Xeon, and from 16.1s to 8.7s on the M5 Max.\n\nHashing throughput on the Xeon, in MiB/s:\n\n                                16KiB    1MiB   vs OpenSSL\n  OpenSSL SHA-1 (no detection)   1234    1129      1.00x\n  sha1dc/ (today)                 435     450      2.67x\n  shani+avx2 (default here)      1002     901      1.24x\n  shani+sse2                     1075    1008      1.13x\n  portable+avx2                   553     654      1.96x\n  portable+sse2                   603     681      1.84x\n  portable                        466     565      2.29x\n\nIn other words, currently collision detection costs about 1.5–2.5x on\ntop of the hashing itself today, but only about 0.2x with the series. \n\nThe patches are:\n\n  [1/4]: sha1dc-accel: add a block loop for sha1dc's SHA1_CTX\n\n    Just groundwork: our own block loop around sha1dc's context and DV\n    table, with the same results and a few percent slower, plus tests\n    that compare against sha1dc/ directly, including on real collisions\n    in every mode.\n\n  [2/4]: sha1dc-accel: vectorize the unavoidable-bitconditions check\n\n    The UBC filter rewritten as SSE2, AVX2, NEON, and new scalar forms, \n    using the conditions the crate's solver picks for each. They're \n    carried as tables, with a short loop per form to run them. \n    1.29x on the Xeon, 1.27x on the M5 Max.\n\n  [3/4]: sha1dc-accel: compress with SHA-NI on x86-64\n\n    Hardware compression, with the schedule spilled, and recompression\n    of flagged blocks in hardware, too. Another 2.07x on the Xeon.\n\n  [4/4]: sha1dc-accel: compress with the ARMv8 SHA-1 instructions\n\n    The same for arm64. Another 2.4x on the M5 Max.\n\nThe x86 numbers are from a 4-vCPU Xeon VM with SHA-NI and AVX2 (GCC 13,\nLinux), which is unfortunately rather noisy; the per-patch hyperfine\noutput has the spread. The arm64 numbers are medians of 9 runs on an\nApple M5 Max (Apple clang, macOS). The full test suite passes on both.\n\n[1] https://sam.dev/blog/faster-sha1-collision-detection\n[2] https://github.com/GitoxideLabs/gitoxide/pull/3008\n\nScott Chacon (4):\n  sha1dc-accel: add a block loop for sha1dc's SHA1_CTX\n  sha1dc-accel: vectorize the unavoidable-bitconditions check\n  sha1dc-accel: compress with SHA-NI on x86-64\n  sha1dc-accel: compress with the ARMv8 SHA-1 instructions\n\n Makefile                            |   14 +\n contrib/buildsystems/CMakeLists.txt |    2 +-\n meson.build                         |    4 +\n sha1dc-accel/arm.c                  |  274 ++++\n sha1dc-accel/internal.h             |  126 ++\n sha1dc-accel/sha1.c                 |  498 ++++++++\n sha1dc-accel/sha1.h                 |   31 +\n sha1dc-accel/ubc_check.c            | 1789 +++++++++++++++++++++++++++\n sha1dc-accel/x86.c                  |  260 ++++\n sha1dc_git.c                        |   18 +\n t/.gitattributes                    |    1 +\n t/helper/test-sha1.c                |   95 ++\n t/helper/test-tool.c                |    2 +\n t/helper/test-tool.h                |    2 +\n t/meson.build                       |    1 +\n t/t0013-sha1dc.sh                   |   47 +\n t/t0013/sha-mbles-1.bin             |  Bin 0 -> 640 bytes\n t/t0013/sha1-reduced-round.bin      |  Bin 0 -> 128 bytes\n t/unit-tests/u-sha1dc.c             |  366 ++++++\n 19 files changed, 3529 insertions(+), 1 deletion(-)\n create mode 100644 sha1dc-accel/arm.c\n create mode 100644 sha1dc-accel/internal.h\n create mode 100644 sha1dc-accel/sha1.c\n create mode 100644 sha1dc-accel/sha1.h\n create mode 100644 sha1dc-accel/ubc_check.c\n create mode 100644 sha1dc-accel/x86.c\n create mode 100644 t/t0013/sha-mbles-1.bin\n create mode 100644 t/t0013/sha1-reduced-round.bin\n create mode 100644 t/unit-tests/u-sha1dc.c\n\n\nbase-commit: a018953688f1b10bddf91bff8747068f5f4746a4\n-- \n2.50.1 (Apple Git-155)\n\n\n"},{"id":"553584","messageId":"20260929112544.86511-2-scott@gitbutler.net","threadId":"66420","inReplyTo":"20260929112544.86511-1-scott@gitbutler.net","subject":"[PATCH 1/4] sha1dc-accel: add a block loop for sha1dc's SHA1_CTX","fromName":"Scott Chacon","fromEmail":"scott@gitbutler.net","sentAt":"2026-09-29T11:25:41Z","receivedAt":"2026-09-29T11:25:53Z","isPatch":true,"body":"Unless you build with some other SHA-1 implementation, every object we\nhash goes through sha1collisiondetection. That's what we want for\nsafety, but it's not free. On the machine I'm testing with (a 4-vCPU\nXeon VM, which has SHA-NI and AVX2), sha1dc hashes at about 400 MiB/s,\nwhile OpenSSL's SHA-1 (which does no detection) does about 1100 MiB/s.\nOn an Apple M5 Max, sha1dc manages about 700 MiB/s.\nThat matters for anything that hashes a lot of data we don't trust,\nlike index-pack.\n\nSam Reis recently wrote about closing that gap for gitoxide [1], with a\nfrom-scratch rewrite of the detection code as a Rust crate [2]. There\nare really three separate tricks in there:\n\n  1. Compress with the CPU's SHA-1 instructions, and spill the expanded\n     message schedule as we go. That's all the detection needs from the\n     vast majority of blocks.\n\n  2. The \"unavoidable bitconditions\" (UBC) filter, which rules out ~95%\n     of blocks before we get to the expensive part, is most of what\n     detection costs. Its conditions can be rewritten into an\n     equivalent set that lines up in vector lanes, and the crate has a\n     solver that does that for each instruction set.\n\n  3. Recompress the few blocks the filter can't rule out with the SHA-1\n     instructions, too.\n\nWe could in theory use the crate itself through our Rust support. But\nthat support is optional, the crate needs a much newer Rust than we\nallow, and none of the three is all that much code once you know what\nit's doing. So let's do it in C, which helps every build.\n\nWe can't really do any of that inside sha1dc/ itself. It's third-party\ncode (optionally a submodule), and its block loop is built around its\nscalar compression, which stores intermediate states as it goes. So this\npatch adds sha1dc-accel/, which has its own block loop but works on\nsha1dc's SHA1_CTX and uses its table of disturbance vectors (DVs). For\neach block it asks a \"backend\" to compress it (spilling the schedule and\nthe two states that recompression starts from), runs the UBC filter,\nand then recompresses the block for each DV the filter didn't rule out.\n\nFor now there's only one backend: a portable C compression, plus\nsha1dc's own ubc_check(). So this is just a reshuffling of what sha1dc/\nalready does, and the speedups come in the following patches. It comes\nout a little slower. With 256MB of random data on the Xeon (GCC 13,\npinned to one CPU):\n\n  Benchmark 1: test-tool.base sha1\n    Time (mean ± σ):     727.3 ms ±  60.8 ms    [User: 677.2 ms, System: 40.7 ms]\n    Range (min … max):   607.5 ms … 837.0 ms    30 runs\n\n  Benchmark 2: test-tool.new sha1\n    Time (mean ± σ):     797.2 ms ± 115.5 ms    [User: 745.4 ms, System: 41.8 ms]\n    Range (min … max):   630.5 ms … 1078.0 ms    30 runs\n\n  Summary\n    test-tool.base sha1 ran\n      1.10 ± 0.18 times faster than test-tool.new sha1\n\nThat's within the noise of this machine (which is quite noisy, sadly),\nbut callgrind counts 2.3% more instructions for the new code, and on the\nM5 Max (Apple clang), hashing 1GiB goes from 1.49s to 1.55s (median of\n9 runs), about 4% slower. That's a price I'm willing to pay for what\ncomes next.\n\nA few other notes:\n\n  - The results must be identical to sha1dc/'s: the same digest, and\n    the same verdict on collisions. That includes the modes that Git\n    itself doesn't use (the \"safe hash\" mitigation, disabling the UBC\n    filter, and detecting reduced-round collisions). The new unit test\n    checks exactly that against sha1dc/ for every backend the machine\n    can run, on random data. There's only one so far, but there will be\n    more. It also checks that sha1dc/'s table of DVs is laid out the way\n    we expect, so that a change there fails loudly.\n\n  - Likewise, \"test-tool sha1dc-backends\" lists the backends, and\n    GIT_TEST_SHA1DC_BACKEND picks one for \"test-tool sha1\", which lets\n    t0013 run its collision test against each of them. While I was\n    there I added a second collision, the SHA-mbles chosen-prefix one\n    [3]. It trips the same disturbance vector as SHAttered, II(52,0),\n    but it's a different kind of attack, and gets detected in the\n    tenth block rather than the fifth.\n\n  - \"test-tool sha1dc-compare\" hashes a file both ways, in every\n    combination of those modes and with the input split around each\n    block, and dies if the two ever disagree. t0013 runs it for each\n    backend on SHAttered, SHA-mbles and a reduced-round collision (from\n    the crate's tests), which is the only way to exercise what happens\n    after a collision is found. The last has no NUL byte, so\n    t/.gitattributes marks t0013's .bin files as binary.\n\n  - The backend is picked once, on first use. Threads can race to pick\n    it, but they'd all store the same value; with GCC and clang we use\n    relaxed atomics for that. Other compilers only get the portable\n    backend, so they have nothing to pick, and no shared state.\n\n  - DC_SHA1_EXTERNAL builds are left alone, since we don't know what\n    their context looks like. For everybody else, DC_SHA1_NO_ACCEL\n    goes back to using sha1dc/ on its own.\n\n[1] https://sam.dev/blog/faster-sha1-collision-detection\n[2] https://github.com/srijs/sha1dc\n[3] https://sha-mbles.github.io/\n\nSigned-off-by: Scott Chacon <scott@gitbutler.net>\nAssisted-by: Claude Opus 5.5 <noreply@anthropic.com>\n---\n Makefile                            |  10 +\n contrib/buildsystems/CMakeLists.txt |   2 +-\n meson.build                         |   1 +\n sha1dc-accel/internal.h             |  25 ++\n sha1dc-accel/sha1.c                 | 434 ++++++++++++++++++++++++++++\n sha1dc-accel/sha1.h                 |  31 ++\n sha1dc_git.c                        |  18 ++\n t/.gitattributes                    |   1 +\n t/helper/test-sha1.c                |  95 ++++++\n t/helper/test-tool.c                |   2 +\n t/helper/test-tool.h                |   2 +\n t/meson.build                       |   1 +\n t/t0013-sha1dc.sh                   |  47 +++\n t/t0013/sha-mbles-1.bin             | Bin 0 -> 640 bytes\n t/t0013/sha1-reduced-round.bin      | Bin 0 -> 128 bytes\n t/unit-tests/u-sha1dc.c             | 145 ++++++++++\n 16 files changed, 813 insertions(+), 1 deletion(-)\n create mode 100644 sha1dc-accel/internal.h\n create mode 100644 sha1dc-accel/sha1.c\n create mode 100644 sha1dc-accel/sha1.h\n create mode 100644 t/t0013/sha-mbles-1.bin\n create mode 100644 t/t0013/sha1-reduced-round.bin\n create mode 100644 t/unit-tests/u-sha1dc.c\n\ndiff --git a/Makefile b/Makefile\nindex c649c93c51..9ab13ca2ab 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -567,6 +567,10 @@ include shared.mak\n # by the git project to migrate to using sha1collisiondetection as a\n # submodule.\n #\n+# Unless DC_SHA1_EXTERNAL is defined, the built-in code is driven by the\n+# block loop in sha1dc-accel/, which gives the same results.\n+# Define DC_SHA1_NO_ACCEL to use the sha1collisiondetection code alone.\n+#\n # === SHA-256 backend ===\n #\n # ==== Security ====\n@@ -1555,6 +1559,7 @@ CLAR_TEST_SUITES += u-reftable-readwrite\n CLAR_TEST_SUITES += u-reftable-stack\n CLAR_TEST_SUITES += u-reftable-table\n CLAR_TEST_SUITES += u-reftable-tree\n+CLAR_TEST_SUITES += u-sha1dc\n CLAR_TEST_SUITES += u-strbuf\n CLAR_TEST_SUITES += u-strcmp-offset\n CLAR_TEST_SUITES += u-string-list\n@@ -2167,6 +2172,11 @@ ifdef DC_SHA1_SUBMODULE\n else\n \tLIB_OBJS += sha1dc/sha1.o\n \tLIB_OBJS += sha1dc/ubc_check.o\n+endif\n+ifdef DC_SHA1_NO_ACCEL\n+\tBASIC_CFLAGS += -DDC_SHA1_NO_ACCEL\n+else\n+\tLIB_OBJS += sha1dc-accel/sha1.o\n endif\n \tBASIC_CFLAGS += \\\n \t\t-DSHA1DC_NO_STANDARD_INCLUDES \\\ndiff --git a/contrib/buildsystems/CMakeLists.txt b/contrib/buildsystems/CMakeLists.txt\nindex 7874e5a326..3c0ea2a27c 100644\n--- a/contrib/buildsystems/CMakeLists.txt\n+++ b/contrib/buildsystems/CMakeLists.txt\n@@ -218,7 +218,7 @@ add_compile_definitions(NO_OPENSSL SHA1_DC SHA1DC_NO_STANDARD_INCLUDES\n \t\t\tSHA1DC_INIT_SAFE_HASH_DEFAULT=0\n \t\t\tSHA1DC_CUSTOM_INCLUDE_SHA1_C=\"git-compat-util.h\"\n \t\t\tSHA1DC_CUSTOM_INCLUDE_UBC_CHECK_C=\"git-compat-util.h\" )\n-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)\n+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)\n \n \n add_compile_definitions(PAGER_ENV=\"LESS=FRX LV=-c\"\ndiff --git a/meson.build b/meson.build\nindex 0a95d90d21..a821b85f30 100644\n--- a/meson.build\n+++ b/meson.build\n@@ -1631,6 +1631,7 @@ if sha1_backend == 'sha1dc'\n     'sha1dc_git.c',\n     'sha1dc/sha1.c',\n     'sha1dc/ubc_check.c',\n+    'sha1dc-accel/sha1.c',\n   ]\n endif\n if sha1_backend == 'CommonCrypto' or sha1_unsafe_backend == 'CommonCrypto'\ndiff --git a/sha1dc-accel/internal.h b/sha1dc-accel/internal.h\nnew file mode 100644\nindex 0000000000..bf3513a1e3\n--- /dev/null\n+++ b/sha1dc-accel/internal.h\n@@ -0,0 +1,25 @@\n+#ifndef SHA1DC_ACCEL_INTERNAL_H\n+#define SHA1DC_ACCEL_INTERNAL_H\n+\n+/*\n+ * Shared between the files of sha1dc-accel/. See sha1.c for an overview.\n+ *\n+ * The schedule `w` is always the 80 expanded message words in step order,\n+ * w[t] at index t, which is also what sha1dc/ keeps in SHA1_CTX.m1.\n+ *\n+ * A \"state\" is the five working words [a, b, c, d, e] before a step.\n+ */\n+\n+#if defined(__GNUC__)\n+# define SHA1DC_NOINLINE __attribute__((noinline))\n+#else\n+# define SHA1DC_NOINLINE\n+#endif\n+\n+/* The step a DV's recompression starts from. */\n+enum sha1dc_from {\n+\tSHA1DC_FROM_58 = 58,\n+\tSHA1DC_FROM_65 = 65\n+};\n+\n+#endif /* SHA1DC_ACCEL_INTERNAL_H */\ndiff --git a/sha1dc-accel/sha1.c b/sha1dc-accel/sha1.c\nnew file mode 100644\nindex 0000000000..fd75289997\n--- /dev/null\n+++ b/sha1dc-accel/sha1.c\n@@ -0,0 +1,434 @@\n+/*\n+ * SHA-1 with collision detection.\n+ *\n+ * This computes exactly what sha1dc/ computes: the SHA-1 digest of the\n+ * input, and whether any block of it looks like one half of a collision\n+ * made by one of the 32 known disturbance vectors (DVs) of Stevens and\n+ * Shumow. It works on sha1dc's SHA1_CTX, and uses its table of DVs, but\n+ * has its own block loop, which gives the following patches room to\n+ * follow the approach of the \"sha1dc\" Rust crate by Sam Reis\n+ * (https://github.com/srijs/sha1dc), which gitoxide uses.\n+ *\n+ * Each block is compressed by a \"backend\", which also spills the expanded\n+ * message schedule, and the two intermediate states that recompression\n+ * starts from (at steps 58 and 65). The unavoidable-bitconditions (UBC)\n+ * filter then rules out about 95% of blocks; the rest are recompressed,\n+ * once for each DV the filter could not rule out.\n+ */\n+\n+#include \"../git-compat-util.h\"\n+#include \"../sha1dc_git.h\"\n+#if defined(DC_SHA1_SUBMODULE)\n+#include \"../sha1collisiondetection/lib/ubc_check.h\"\n+#else\n+#include \"../sha1dc/ubc_check.h\"\n+#endif\n+#include \"sha1.h\"\n+#include \"internal.h\"\n+\n+#define ROL(x, n) (((x) << (n)) | ((x) >> (32 - (n))))\n+\n+#define F_CH(b, c, d) ((d) ^ ((b) & ((c) ^ (d))))\n+#define F_PARITY(b, c, d) ((b) ^ (c) ^ (d))\n+#define F_MAJ(b, c, d) (((b) & (c)) | ((d) & ((b) | (c))))\n+\n+#define K0 0x5A827999\n+#define K1 0x6ED9EBA1\n+#define K2 0x8F1BBCDC\n+#define K3 0xCA62C1D6\n+\n+/*\n+ * One step, on names that rotate: after it, (e, a, b, c, d) are the new\n+ * (a, b, c, d, e).\n+ */\n+#define STEP(f, k, a, b, c, d, e, x) \\\n+\tdo { \\\n+\t\te += ROL(a, 5) + f(b, c, d) + (k) + (x); \\\n+\t\tb = ROL(b, 30); \\\n+\t} while (0)\n+\n+#define LOAD(t) (w[t] = get_be32(block + 4 * (t)))\n+#define EXPAND(t) (w[t] = ROL(w[(t) - 3] ^ w[(t) - 8] ^ w[(t) - 14] ^ w[(t) - 16], 1))\n+\n+#define FIVE_LOAD(f, k, a, b, c, d, e, t) \\\n+\tdo { \\\n+\t\tSTEP(f, k, a, b, c, d, e, LOAD(t)); \\\n+\t\tSTEP(f, k, e, a, b, c, d, LOAD((t) + 1)); \\\n+\t\tSTEP(f, k, d, e, a, b, c, LOAD((t) + 2)); \\\n+\t\tSTEP(f, k, c, d, e, a, b, LOAD((t) + 3)); \\\n+\t\tSTEP(f, k, b, c, d, e, a, LOAD((t) + 4)); \\\n+\t} while (0)\n+\n+#define FIVE_EXPAND(f, k, a, b, c, d, e, t) \\\n+\tdo { \\\n+\t\tSTEP(f, k, a, b, c, d, e, EXPAND(t)); \\\n+\t\tSTEP(f, k, e, a, b, c, d, EXPAND((t) + 1)); \\\n+\t\tSTEP(f, k, d, e, a, b, c, EXPAND((t) + 2)); \\\n+\t\tSTEP(f, k, c, d, e, a, b, EXPAND((t) + 3)); \\\n+\t\tSTEP(f, k, b, c, d, e, a, EXPAND((t) + 4)); \\\n+\t} while (0)\n+\n+/*\n+ * The portable compression. Like the hardware ones it spills the schedule,\n+ * but it writes the states at steps 58 and 65 directly, on the way past.\n+ */\n+static void compress_portable(uint32_t ihv[5], const unsigned char *block,\n+\t\t\t      uint32_t w[80], uint32_t state_58[5],\n+\t\t\t      uint32_t state_65[5])\n+{\n+\tuint32_t a = ihv[0], b = ihv[1], c = ihv[2], d = ihv[3], e = ihv[4];\n+\n+\tFIVE_LOAD(F_CH, K0, a, b, c, d, e, 0);\n+\tFIVE_LOAD(F_CH, K0, a, b, c, d, e, 5);\n+\tFIVE_LOAD(F_CH, K0, a, b, c, d, e, 10);\n+\tSTEP(F_CH, K0, a, b, c, d, e, LOAD(15));\n+\tSTEP(F_CH, K0, e, a, b, c, d, EXPAND(16));\n+\tSTEP(F_CH, K0, d, e, a, b, c, EXPAND(17));\n+\tSTEP(F_CH, K0, c, d, e, a, b, EXPAND(18));\n+\tSTEP(F_CH, K0, b, c, d, e, a, EXPAND(19));\n+\n+\tFIVE_EXPAND(F_PARITY, K1, a, b, c, d, e, 20);\n+\tFIVE_EXPAND(F_PARITY, K1, a, b, c, d, e, 25);\n+\tFIVE_EXPAND(F_PARITY, K1, a, b, c, d, e, 30);\n+\tFIVE_EXPAND(F_PARITY, K1, a, b, c, d, e, 35);\n+\n+\tFIVE_EXPAND(F_MAJ, K2, a, b, c, d, e, 40);\n+\tFIVE_EXPAND(F_MAJ, K2, a, b, c, d, e, 45);\n+\tFIVE_EXPAND(F_MAJ, K2, a, b, c, d, e, 50);\n+\tSTEP(F_MAJ, K2, a, b, c, d, e, EXPAND(55));\n+\tSTEP(F_MAJ, K2, e, a, b, c, d, EXPAND(56));\n+\tSTEP(F_MAJ, K2, d, e, a, b, c, EXPAND(57));\n+\tstate_58[0] = c;\n+\tstate_58[1] = d;\n+\tstate_58[2] = e;\n+\tstate_58[3] = a;\n+\tstate_58[4] = b;\n+\tSTEP(F_MAJ, K2, c, d, e, a, b, EXPAND(58));\n+\tSTEP(F_MAJ, K2, b, c, d, e, a, EXPAND(59));\n+\n+\tFIVE_EXPAND(F_PARITY, K3, a, b, c, d, e, 60);\n+\tstate_65[0] = a;\n+\tstate_65[1] = b;\n+\tstate_65[2] = c;\n+\tstate_65[3] = d;\n+\tstate_65[4] = e;\n+\tFIVE_EXPAND(F_PARITY, K3, a, b, c, d, e, 65);\n+\tFIVE_EXPAND(F_PARITY, K3, a, b, c, d, e, 70);\n+\tFIVE_EXPAND(F_PARITY, K3, a, b, c, d, e, 75);\n+\n+\tihv[0] += a;\n+\tihv[1] += b;\n+\tihv[2] += c;\n+\tihv[3] += d;\n+\tihv[4] += e;\n+}\n+\n+/*\n+ * The rest runs only for blocks the filter flags, about one in twenty, so\n+ * it favours being short over being fast.\n+ */\n+\n+/*\n+ * Moves `s` from the state before step `from` to the one before step `to`,\n+ * either way, on the schedule `m1 ^ dm` (`dm` may be NULL). One loop per\n+ * round function keeps the steps free of branches.\n+ */\n+#define WORD(t) (dm ? m1[t] ^ dm[t] : m1[t])\n+#define FORWARD(f, k, end) \\\n+\tfor (; t < to && t < (end); t++) { \\\n+\t\tx = ROL(a, 5) + f(b, c, d) + (k) + e + WORD(t); \\\n+\t\te = d; \\\n+\t\td = c; \\\n+\t\tc = ROL(b, 30); \\\n+\t\tb = a; \\\n+\t\ta = x; \\\n+\t}\n+#define BACKWARD(f, k, start) \\\n+\tfor (; t > to && t > (start); t--) { \\\n+\t\tx = a; \\\n+\t\ta = b; \\\n+\t\tb = ROL(c, 2); \\\n+\t\tc = d; \\\n+\t\td = e; \\\n+\t\te = x - (ROL(a, 5) + f(b, c, d) + (k) + WORD(t - 1)); \\\n+\t}\n+\n+static void walk(uint32_t s[5], const uint32_t *m1, const uint32_t *dm,\n+\t\t unsigned from, unsigned to)\n+{\n+\tuint32_t a = s[0], b = s[1], c = s[2], d = s[3], e = s[4], x;\n+\tunsigned t = from;\n+\n+\tFORWARD(F_CH, K0, 20);\n+\tFORWARD(F_PARITY, K1, 40);\n+\tFORWARD(F_MAJ, K2, 60);\n+\tFORWARD(F_PARITY, K3, 80);\n+\n+\tBACKWARD(F_PARITY, K3, 60);\n+\tBACKWARD(F_MAJ, K2, 40);\n+\tBACKWARD(F_PARITY, K1, 20);\n+\tBACKWARD(F_CH, K0, 0);\n+\n+\ts[0] = a;\n+\ts[1] = b;\n+\ts[2] = c;\n+\ts[3] = d;\n+\ts[4] = e;\n+}\n+\n+/*\n+ * The recompression, the way sha1dc/ does it: from this block's state at\n+ * `from`, the partner block's chaining value on the way in (`ihv_in`) and\n+ * on the way out (`ihv_out`).\n+ */\n+static void recompress_portable(enum sha1dc_from from, const uint32_t m1[80],\n+\t\t\t\tconst uint32_t dm[80], const uint32_t state[5],\n+\t\t\t\tuint32_t ihv_in[5], uint32_t ihv_out[5])\n+{\n+\tuint32_t fwd[5];\n+\tint i;\n+\n+\tmemcpy(ihv_in, state, 5 * sizeof(*ihv_in));\n+\twalk(ihv_in, m1, dm, from, 0);\n+\tmemcpy(fwd, state, sizeof(fwd));\n+\twalk(fwd, m1, dm, from, 80);\n+\tfor (i = 0; i < 5; i++)\n+\t\tihv_out[i] = ihv_in[i] + fwd[i];\n+}\n+\n+/* For a mitigated (\"safe\") hash: one more compression of the schedule. */\n+static void compress_schedule(uint32_t ihv[5], const uint32_t w[80])\n+{\n+\tuint32_t s[5];\n+\tint i;\n+\n+\tmemcpy(s, ihv, sizeof(s));\n+\twalk(s, w, NULL, 0, 80);\n+\tfor (i = 0; i < 5; i++)\n+\t\tihv[i] += s[i];\n+}\n+\n+struct backend {\n+\tconst char *name;\n+\t/*\n+\t * Compresses a block, spilling its schedule and the states at steps\n+\t * 58 and 65.\n+\t */\n+\tvoid (*compress)(uint32_t ihv[5], const unsigned char *block,\n+\t\t\t uint32_t w[80], uint32_t state_58[5],\n+\t\t\t uint32_t state_65[5]);\n+\tuint32_t (*ubc_check)(const uint32_t w[80]);\n+\tint (*available)(void);\n+};\n+\n+/* sha1dc's own UBC check. */\n+static uint32_t ubc_check_sha1dc(const uint32_t w[80])\n+{\n+\tuint32_t mask;\n+\n+\tubc_check(w, &mask);\n+\treturn mask;\n+}\n+\n+/* In order of preference. */\n+static const struct backend backends[] = {\n+\t{ \"portable\", compress_portable, ubc_check_sha1dc, NULL },\n+};\n+\n+static int usable(const struct backend *be)\n+{\n+\treturn !be->available || be->available();\n+}\n+\n+#if defined(__GNUC__)\n+/*\n+ * The backend in use, chosen on first use. Threads that race to choose it\n+ * all store the same value, with relaxed atomics so that they may.\n+ */\n+static const struct backend *selected;\n+\n+static const struct backend *backend(void)\n+{\n+\tconst struct backend *be = __atomic_load_n(&selected, __ATOMIC_RELAXED);\n+\tsize_t i;\n+\n+\tif (be)\n+\t\treturn be;\n+\t/* The last one, \"portable\", is always usable. */\n+\tfor (i = 0; !usable(&backends[i]); i++)\n+\t\t;\n+\tbe = &backends[i];\n+\t__atomic_store_n(&selected, be, __ATOMIC_RELAXED);\n+\treturn be;\n+}\n+\n+static void select_backend(const struct backend *be)\n+{\n+\t__atomic_store_n(&selected, be, __ATOMIC_RELAXED);\n+}\n+#else\n+/*\n+ * Other compilers only get the portable backend (see internal.h), so\n+ * there is nothing to choose, and no shared state to guard.\n+ */\n+static const struct backend *backend(void)\n+{\n+\treturn &backends[0];\n+}\n+\n+static void select_backend(const struct backend *be UNUSED)\n+{\n+}\n+#endif\n+\n+const char *sha1dc_accel_backend(void)\n+{\n+\treturn backend()->name;\n+}\n+\n+int sha1dc_accel_select(const char *name)\n+{\n+\tsize_t i;\n+\n+\tfor (i = 0; i < ARRAY_SIZE(backends); i++) {\n+\t\tif (!strcmp(backends[i].name, name) && usable(&backends[i])) {\n+\t\t\tselect_backend(&backends[i]);\n+\t\t\treturn 0;\n+\t\t}\n+\t}\n+\treturn -1;\n+}\n+\n+const char *const *sha1dc_accel_backends(void)\n+{\n+\tstatic const char *names[ARRAY_SIZE(backends) + 1];\n+\tsize_t i, n = 0;\n+\n+\tfor (i = 0; i < ARRAY_SIZE(backends); i++)\n+\t\tif (usable(&backends[i]))\n+\t\t\tnames[n++] = backends[i].name;\n+\tnames[n] = NULL;\n+\treturn names;\n+}\n+\n+/*\n+ * Whether any DV in `candidates` makes this block half of a collision.\n+ * `ihv_in` and `ihv_out` are the chaining values before and after it.\n+ */\n+static SHA1DC_NOINLINE int attacked(SHA1_CTX *ctx, uint32_t candidates,\n+\t\t\t\t    const uint32_t w[80],\n+\t\t\t\t    const uint32_t state_58[5],\n+\t\t\t\t    const uint32_t state_65[5],\n+\t\t\t\t    const uint32_t ihv_in[5],\n+\t\t\t\t    const uint32_t ihv_out[5])\n+{\n+\tint i;\n+\n+\tfor (i = 0; sha1_dvs[i].dvType != 0; i++) {\n+\t\tconst dv_info_t *dv = &sha1_dvs[i];\n+\t\tenum sha1dc_from from;\n+\t\tconst uint32_t *state;\n+\t\tuint32_t ihv2_in[5], ihv2_out[5];\n+\n+\t\tif (!(candidates & ((uint32_t)1 << dv->maskb)))\n+\t\t\tcontinue;\n+\t\tswitch (dv->testt) {\n+\t\tcase 58:\n+\t\t\tfrom = SHA1DC_FROM_58;\n+\t\t\tstate = state_58;\n+\t\t\tbreak;\n+\t\tcase 65:\n+\t\t\tfrom = SHA1DC_FROM_65;\n+\t\t\tstate = state_65;\n+\t\t\tbreak;\n+\t\tdefault:\n+\t\t\tBUG(\"sha1dc DV %d(%d,%d) recompresses from step %d, \"\n+\t\t\t    \"which sha1dc-accel does not save\",\n+\t\t\t    dv->dvType, dv->dvK, dv->dvB, dv->testt);\n+\t\t}\n+\n+\t\trecompress_portable(from, w, dv->dm, state, ihv2_in, ihv2_out);\n+\t\tif (!memcmp(ihv2_out, ihv_out, sizeof(ihv2_out)) ||\n+\t\t    (ctx->reduced_round_coll &&\n+\t\t     !memcmp(ihv2_in, ihv_in, sizeof(ihv2_in))))\n+\t\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n+static inline void process(const struct backend *be, SHA1_CTX *ctx,\n+\t\t\t   const unsigned char *block)\n+{\n+\tuint32_t w[80], state_58[5], state_65[5], ihv_in[5], candidates;\n+\n+\tmemcpy(ihv_in, ctx->ihv, sizeof(ihv_in));\n+\tbe->compress(ctx->ihv, block, w, state_58, state_65);\n+\tif (!ctx->detect_coll)\n+\t\treturn;\n+\n+\tcandidates = ctx->ubc_check ? be->ubc_check(w) : 0xFFFFFFFF;\n+\tif (candidates &&\n+\t    attacked(ctx, candidates, w, state_58, state_65, ihv_in,\n+\t\t     ctx->ihv)) {\n+\t\tctx->found_collision = 1;\n+\t\t/*\n+\t\t * Two more compressions of this block give a digest that the\n+\t\t * other block of the pair does not share.\n+\t\t */\n+\t\tif (ctx->safe_hash) {\n+\t\t\tcompress_schedule(ctx->ihv, w);\n+\t\t\tcompress_schedule(ctx->ihv, w);\n+\t\t}\n+\t}\n+}\n+\n+void sha1dc_accel_update(SHA1_CTX *ctx, const void *data, size_t len)\n+{\n+\tconst struct backend *be = backend();\n+\tconst unsigned char *buf = data;\n+\tunsigned left, fill;\n+\n+\tif (!len)\n+\t\treturn;\n+\n+\tleft = ctx->total & 63;\n+\tfill = 64 - left;\n+\n+\tif (left && len >= fill) {\n+\t\tctx->total += fill;\n+\t\tmemcpy(ctx->buffer + left, buf, fill);\n+\t\tprocess(be, ctx, ctx->buffer);\n+\t\tbuf += fill;\n+\t\tlen -= fill;\n+\t\tleft = 0;\n+\t}\n+\twhile (len >= 64) {\n+\t\tctx->total += 64;\n+\t\tprocess(be, ctx, buf);\n+\t\tbuf += 64;\n+\t\tlen -= 64;\n+\t}\n+\tif (len) {\n+\t\tctx->total += len;\n+\t\tmemcpy(ctx->buffer + left, buf, len);\n+\t}\n+}\n+\n+int sha1dc_accel_final(unsigned char hash[20], SHA1_CTX *ctx)\n+{\n+\tstatic const unsigned char padding[64] = { 0x80 };\n+\tuint32_t last = ctx->total & 63;\n+\tuint32_t padn = last < 56 ? 56 - last : 120 - last;\n+\tuint64_t bits;\n+\tint i;\n+\n+\tsha1dc_accel_update(ctx, padding, padn);\n+\tbits = (ctx->total - padn) << 3;\n+\tput_be32(ctx->buffer + 56, (uint32_t)(bits >> 32));\n+\tput_be32(ctx->buffer + 60, (uint32_t)bits);\n+\tprocess(backend(), ctx, ctx->buffer);\n+\n+\tfor (i = 0; i < 5; i++)\n+\t\tput_be32(hash + 4 * i, ctx->ihv[i]);\n+\treturn ctx->found_collision;\n+}\ndiff --git a/sha1dc-accel/sha1.h b/sha1dc-accel/sha1.h\nnew file mode 100644\nindex 0000000000..53dda518f0\n--- /dev/null\n+++ b/sha1dc-accel/sha1.h\n@@ -0,0 +1,31 @@\n+#ifndef SHA1DC_ACCEL_SHA1_H\n+#define SHA1DC_ACCEL_SHA1_H\n+\n+#if defined(DC_SHA1_SUBMODULE)\n+#include \"../sha1collisiondetection/lib/sha1.h\"\n+#else\n+#include \"../sha1dc/sha1.h\"\n+#endif\n+\n+/*\n+ * A faster implementation of SHA-1 with collision detection, working on\n+ * the SHA1_CTX of sha1dc/ (or of the sha1collisiondetection submodule).\n+ * SHA1DCInit() and the SHA1DCSet*() functions set it up as usual; these\n+ * then take the place of SHA1DCUpdate() and SHA1DCFinal(), with the same\n+ * results. See sha1.c.\n+ */\n+\n+void sha1dc_accel_update(SHA1_CTX *ctx, const void *data, size_t len);\n+int sha1dc_accel_final(unsigned char hash[20], SHA1_CTX *ctx);\n+\n+/*\n+ * The implementation in use, such as \"shani+avx2\" or \"portable\". For tests,\n+ * sha1dc_accel_select() switches to another one by that name; it returns -1\n+ * if this build or CPU does not have it. Neither is thread-safe.\n+ */\n+const char *sha1dc_accel_backend(void);\n+int sha1dc_accel_select(const char *name);\n+/* The names this build and CPU can use, NULL-terminated. */\n+const char *const *sha1dc_accel_backends(void);\n+\n+#endif /* SHA1DC_ACCEL_SHA1_H */\ndiff --git a/sha1dc_git.c b/sha1dc_git.c\nindex fe58d7962a..03958762cf 100644\n--- a/sha1dc_git.c\n+++ b/sha1dc_git.c\n@@ -2,6 +2,15 @@\n #include \"sha1dc_git.h\"\n #include \"hex.h\"\n \n+/*\n+ * Unless told otherwise, hash with sha1dc-accel/, which gives the same\n+ * results as sha1dc/ on the same SHA1_CTX.\n+ */\n+#if !defined(DC_SHA1_EXTERNAL) && !defined(DC_SHA1_NO_ACCEL)\n+#include \"sha1dc-accel/sha1.h\"\n+#define USE_SHA1DC_ACCEL\n+#endif\n+\n #ifdef DC_SHA1_EXTERNAL\n /*\n  * Same as SHA1DCInit, but with default save_hash=0\n@@ -18,8 +27,13 @@ void git_SHA1DCInit(SHA1_CTX *ctx)\n  */\n void git_SHA1DCFinal(unsigned char hash[20], SHA1_CTX *ctx)\n {\n+#ifdef USE_SHA1DC_ACCEL\n+\tif (!sha1dc_accel_final(hash, ctx))\n+\t\treturn;\n+#else\n \tif (!SHA1DCFinal(hash, ctx))\n \t\treturn;\n+#endif\n \tdie(\"SHA-1 appears to be part of a collision attack: %s\",\n \t    hash_to_hex_algop(hash, &hash_algos[GIT_HASH_SHA1]));\n }\n@@ -29,6 +43,9 @@ void git_SHA1DCFinal(unsigned char hash[20], SHA1_CTX *ctx)\n  */\n void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *vdata, size_t len)\n {\n+#ifdef USE_SHA1DC_ACCEL\n+\tsha1dc_accel_update(ctx, vdata, len);\n+#else\n \tconst char *data = vdata;\n \twhile (len > INT_MAX) {\n \t\tSHA1DCUpdate(ctx, data, INT_MAX);\n@@ -36,4 +53,5 @@ void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *vdata, size_t len)\n \t\tlen -= INT_MAX;\n \t}\n \tSHA1DCUpdate(ctx, data, len);\n+#endif\n }\ndiff --git a/t/.gitattributes b/t/.gitattributes\nindex e867f38c71..f9437159ae 100644\n--- a/t/.gitattributes\n+++ b/t/.gitattributes\n@@ -2,6 +2,7 @@ t[0-9][0-9][0-9][0-9]/* -whitespace\n /chainlint/*.expect eol=lf -whitespace\n /greplint/*.expect eol=lf -whitespace\n /greplint/*.test eol=lf -whitespace\n+/t0013/*.bin binary\n /t0110/url-* binary\n /t3206/* eol=lf\n /t3900/*.txt eol=lf\ndiff --git a/t/helper/test-sha1.c b/t/helper/test-sha1.c\nindex 349540c4df..7a0e9cc716 100644\n--- a/t/helper/test-sha1.c\n+++ b/t/helper/test-sha1.c\n@@ -1,8 +1,20 @@\n #include \"test-tool.h\"\n #include \"hash.h\"\n+#include \"strbuf.h\"\n+\n+#if defined(SHA1_DC) && !defined(DC_SHA1_EXTERNAL) && !defined(DC_SHA1_NO_ACCEL)\n+#include \"sha1dc-accel/sha1.h\"\n+#define HAVE_SHA1DC_ACCEL\n+#endif\n \n int cmd__sha1(int ac, const char **av)\n {\n+#ifdef HAVE_SHA1DC_ACCEL\n+\tconst char *backend = getenv(\"GIT_TEST_SHA1DC_BACKEND\");\n+\n+\tif (backend && sha1dc_accel_select(backend))\n+\t\tdie(\"sha1dc backend '%s' is not available\", backend);\n+#endif\n \treturn cmd_hash_impl(ac, av, GIT_HASH_SHA1, 0);\n }\n \n@@ -14,6 +26,89 @@ int cmd__sha1_is_sha1dc(int argc UNUSED, const char **argv UNUSED)\n \treturn 1;\n }\n \n+/*\n+ * Lists the implementations of collision-detecting SHA-1 this build and\n+ * CPU can use, which GIT_TEST_SHA1DC_BACKEND selects for \"test-tool sha1\".\n+ */\n+int cmd__sha1dc_backends(int argc UNUSED, const char **argv UNUSED)\n+{\n+#ifdef HAVE_SHA1DC_ACCEL\n+\tconst char *const *names;\n+\n+\tfor (names = sha1dc_accel_backends(); *names; names++)\n+\t\tputs(*names);\n+#endif\n+\treturn 0;\n+}\n+\n+/*\n+ * Hashes a file with sha1dc/ and with sha1dc-accel/ (the backend that\n+ * GIT_TEST_SHA1DC_BACKEND selects), under every combination of settings,\n+ * and dies if they ever disagree on the digest or on whether there is a\n+ * collision. sha1dc-accel/ sees the file split at and around every block\n+ * boundary, with an empty update in between. Prints what sha1dc/ found for\n+ * each combination.\n+ */\n+int cmd__sha1dc_compare(int argc MAYBE_UNUSED, const char **argv MAYBE_UNUSED)\n+{\n+#ifdef HAVE_SHA1DC_ACCEL\n+\tconst char *backend = getenv(\"GIT_TEST_SHA1DC_BACKEND\");\n+\tstruct strbuf buf = STRBUF_INIT;\n+\tint mode;\n+\n+\tif (argc != 2)\n+\t\tdie(\"usage: test-tool sha1dc-compare <file>\");\n+\tif (backend && sha1dc_accel_select(backend))\n+\t\tdie(\"sha1dc backend '%s' is not available\", backend);\n+\tif (strbuf_read_file(&buf, argv[1], 0) < 0)\n+\t\tdie_errno(\"could not read '%s'\", argv[1]);\n+\n+\tfor (mode = 0; mode < 16; mode++) {\n+\t\tint detect = !!(mode & 8), safe = !!(mode & 4);\n+\t\tint ubc = !!(mode & 2), reduced = !!(mode & 1);\n+\t\tunsigned char want[20], got[20];\n+\t\tSHA1_CTX init, ctx;\n+\t\tint want_coll, got_coll, i;\n+\t\tsize_t split;\n+\n+\t\tSHA1DCInit(&init);\n+\t\tSHA1DCSetUseDetectColl(&init, detect);\n+\t\tSHA1DCSetSafeHash(&init, safe);\n+\t\tSHA1DCSetUseUBC(&init, ubc);\n+\t\tSHA1DCSetDetectReducedRoundCollision(&init, reduced);\n+\n+\t\tctx = init;\n+\t\tSHA1DCUpdate(&ctx, buf.buf, buf.len);\n+\t\twant_coll = SHA1DCFinal(want, &ctx);\n+\n+\t\tfor (split = 0; split <= buf.len; split++) {\n+\t\t\tif (split % 64 > 1 && split % 64 < 63 && split != buf.len)\n+\t\t\t\tcontinue;\n+\t\t\tctx = init;\n+\t\t\tsha1dc_accel_update(&ctx, buf.buf, split);\n+\t\t\tsha1dc_accel_update(&ctx, buf.buf + split, 0);\n+\t\t\tsha1dc_accel_update(&ctx, buf.buf + split, buf.len - split);\n+\t\t\tgot_coll = sha1dc_accel_final(got, &ctx);\n+\t\t\tif (got_coll != want_coll || memcmp(got, want, sizeof(got)))\n+\t\t\t\tdie(\"%s disagrees with sha1dc/ on '%s' with detect=%d \"\n+\t\t\t\t    \"safe=%d ubc=%d reduced=%d, split at %\"PRIuMAX,\n+\t\t\t\t    sha1dc_accel_backend(), argv[1], detect, safe,\n+\t\t\t\t    ubc, reduced, (uintmax_t)split);\n+\t\t}\n+\n+\t\tprintf(\"detect=%d safe=%d ubc=%d reduced=%d collision=%d \",\n+\t\t       detect, safe, ubc, reduced, want_coll);\n+\t\tfor (i = 0; i < 20; i++)\n+\t\t\tprintf(\"%02x\", want[i]);\n+\t\tputchar('\\n');\n+\t}\n+\tstrbuf_release(&buf);\n+\treturn 0;\n+#else\n+\tdie(\"test-tool sha1dc-compare: not built with sha1dc-accel\");\n+#endif\n+}\n+\n int cmd__sha1_unsafe(int ac, const char **av)\n {\n \treturn cmd_hash_impl(ac, av, GIT_HASH_SHA1, 1);\ndiff --git a/t/helper/test-tool.c b/t/helper/test-tool.c\nindex b71a22b43b..c459218f0b 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -73,6 +73,8 @@ static struct test_cmd cmds[] = {\n \t{ \"serve-v2\", cmd__serve_v2 },\n \t{ \"sha1\", cmd__sha1 },\n \t{ \"sha1-is-sha1dc\", cmd__sha1_is_sha1dc },\n+\t{ \"sha1dc-backends\", cmd__sha1dc_backends },\n+\t{ \"sha1dc-compare\", cmd__sha1dc_compare },\n \t{ \"sha1-unsafe\", cmd__sha1_unsafe },\n \t{ \"sha256\", cmd__sha256 },\n \t{ \"sigchain\", cmd__sigchain },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex f2885b33d5..f0cdbddcdf 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -66,6 +66,8 @@ int cmd__scrap_cache_tree(int argc, const char **argv);\n int cmd__serve_v2(int argc, const char **argv);\n int cmd__sha1(int argc, const char **argv);\n int cmd__sha1_is_sha1dc(int argc, const char **argv);\n+int cmd__sha1dc_backends(int argc, const char **argv);\n+int cmd__sha1dc_compare(int argc, const char **argv);\n int cmd__sha1_unsafe(int argc, const char **argv);\n int cmd__sha256(int argc, const char **argv);\n int cmd__sigchain(int argc, const char **argv);\ndiff --git a/t/meson.build b/t/meson.build\nindex 3ca7b27104..ec25f0de40 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -20,6 +20,7 @@ clar_test_suites = [\n   'unit-tests/u-reftable-stack.c',\n   'unit-tests/u-reftable-table.c',\n   'unit-tests/u-reftable-tree.c',\n+  'unit-tests/u-sha1dc.c',\n   'unit-tests/u-strbuf.c',\n   'unit-tests/u-strcmp-offset.c',\n   'unit-tests/u-string-list.c',\ndiff --git a/t/t0013-sha1dc.sh b/t/t0013-sha1dc.sh\nindex 3ea3169d92..c3c4b9d951 100755\n--- a/t/t0013-sha1dc.sh\n+++ b/t/t0013-sha1dc.sh\n@@ -19,4 +19,51 @@ test_expect_success 'test-sha1 detects shattered pdf' '\n \ttest_grep 38762cf7f55934b34d179ae6a4c80cadccbb7f0a err\n '\n \n+test_expect_success 'test-sha1 detects SHA-mbles chosen-prefix collision' '\n+\ttest_must_fail test-tool sha1 <\"$TEST_DATA/sha-mbles-1.bin\" 2>err &&\n+\ttest_grep collision err &&\n+\ttest_grep 8ac60ba76f1999a1ab70223f225aefdc78d4ddc0 err\n+'\n+\n+# Each implementation of the detection this build and CPU can use.\n+for backend in $(test-tool sha1dc-backends)\n+do\n+\ttest_expect_success \"$backend: detects collisions\" '\n+\t\ttest_must_fail env GIT_TEST_SHA1DC_BACKEND=$backend \\\n+\t\t\ttest-tool sha1 <\"$TEST_DATA/shattered-1.pdf\" 2>err &&\n+\t\ttest_grep 38762cf7f55934b34d179ae6a4c80cadccbb7f0a err &&\n+\t\ttest_must_fail env GIT_TEST_SHA1DC_BACKEND=$backend \\\n+\t\t\ttest-tool sha1 <\"$TEST_DATA/sha-mbles-1.bin\" 2>err &&\n+\t\ttest_grep 8ac60ba76f1999a1ab70223f225aefdc78d4ddc0 err\n+\t'\n+\n+\t# In every combination of settings, and with the input split around\n+\t# each block, it must find what sha1dc/ finds and give its digest.\n+\ttest_expect_success \"$backend: agrees with sha1dc/ on collisions\" '\n+\t\ttest_copy_bytes 320 <\"$TEST_DATA/shattered-1.pdf\" >shattered &&\n+\t\tfor f in shattered \"$TEST_DATA/sha-mbles-1.bin\"\n+\t\tdo\n+\t\t\tGIT_TEST_SHA1DC_BACKEND=$backend \\\n+\t\t\t\ttest-tool sha1dc-compare \"$f\" >out &&\n+\t\t\ttest_grep ! \"detect=1 .* collision=0\" out &&\n+\t\t\ttest_grep ! \"detect=0 .* collision=1\" out || return 1\n+\t\tdone &&\n+\n+\t\t# A reduced-round collision counts only when asked for.\n+\t\tGIT_TEST_SHA1DC_BACKEND=$backend test-tool sha1dc-compare \\\n+\t\t\t\"$TEST_DATA/sha1-reduced-round.bin\" >out &&\n+\t\tgrep \"collision=1\" out >actual &&\n+\t\tgrep \"detect=1 .* reduced=1 collision=1\" out >expect &&\n+\t\ttest_line_count = 4 expect &&\n+\t\ttest_cmp expect actual\n+\t'\n+\n+\ttest_expect_success \"$backend: hashes like the others\" '\n+\t\ttest-tool genrandom \"$backend\" 100000 >data &&\n+\t\tGIT_TEST_SHA1DC_BACKEND=$backend test-tool sha1 <data >actual &&\n+\t\ttest-tool sha1 <data >expect &&\n+\t\ttest_cmp expect actual\n+\t'\n+done\n+\n test_done\ndiff --git a/t/t0013/sha-mbles-1.bin b/t/t0013/sha-mbles-1.bin\nnew file mode 100644\nindex 0000000000000000000000000000000000000000..5a7c30e97646c66422abe0a9793a5fcb9f1cf8d6\nGIT binary patch\nliteral 640\nzcmV-`0)PFP1Pug#=of$iAOQbMWqBZJb0BbGa&#bXW*}i8V{dG1X>)0BZXqB^bSHBl\nzVIXvJVQ?XN#v1Ui%mqai*(XkO2VzSd$NM9gi@4s4S6#Y$o~tpzXG?9DLwKksb1(IU\nz9Co7S2XeKfeBtWE3%QfQEsSvDN>7bn&F#UnES&M4F|Q;kb)7=w-`g>9pICMy?o}x{\nzw%puBpUP8JJ8<}Z-Y}v^>N@tvS)%d_G7WYOwomkV2v5_@v(40lV%ch(Lk1Vh|7<qK\nzH|0OxC_#T>Z|qd<c|)XbUso{lyEywD_TUKs5YP@Jt$4qZWEqoSj*S(Hc%L-HZ{g+w\nze>J4b`+{(G#SY32i+svyyDTet0$KULm2lmSL^q=mU$6JW%D|e^Qf38QClE(f7mlv~\nzf?6!9D$ljvWX^U$+*zeTsr;OEXIA3kJ;xKs!c3Qts%s87r}bYHMJgPkg$>=6V*Q#J\nztwKp^sc;DQMsoI!^kM6Wu$eQ~Cban&bezB^{oQOrU&JA3HP91H6)0P)EVqQD_sg{V\nzQB6zm_9J}o3Z9=6E1CvwZ_$5jLYQ=TSa0@Gua<Owv?jTSE1HPp20vN5Gfcn+Q2084\nz#3xa=8FbSC{3scs=<(w$8&S&`=D)<-o38eC)T;HdS4sqbk8RTI6*`kaB9oU*l8=ba\nz*)}}>`F!H%LccW0YmW1WR(AfS%&6t}-k`d&K|M|24(A@=9~LXyZ62@LCFZWWu4*+-\nz@qF?Hqy+oh68uF?LH*fW@<o<pqOAih9i|F%CO~!9@!;0MKsx83*kRv4<#2I`-ChUL\naSeu`VW-wJhkHb>4;KF^V3*EX*WC9JhR6N@N\n\nliteral 0\nHcmV?d00001\n\ndiff --git a/t/t0013/sha1-reduced-round.bin b/t/t0013/sha1-reduced-round.bin\nnew file mode 100644\nindex 0000000000000000000000000000000000000000..4623336222bd5c9e7b1b0e244a5897430c1b5c12\nGIT binary patch\nliteral 128\nzcmV-`0Du3yemOb>aQ1}Yq=eq3R)<>6-}%Tb0s(7=4(It1;e;4*zrXPYaFxmJM6d36\nz5+n(uvg<Auz|X=4#ULmUI6NzJ=Hkdhf3ZGJO<lI*gWw%|>Le^HwlGv^MX^H+A(X58\niQZ~LT$sQRU5x<XSUiqt^kK<}UEWbI|d>^ztun2PMcs$<#\n\nliteral 0\nHcmV?d00001\n\ndiff --git a/t/unit-tests/u-sha1dc.c b/t/unit-tests/u-sha1dc.c\nnew file mode 100644\nindex 0000000000..31fcd68451\n--- /dev/null\n+++ b/t/unit-tests/u-sha1dc.c\n@@ -0,0 +1,145 @@\n+#include \"unit-test.h\"\n+#include \"hash.h\"\n+\n+/*\n+ * Tests sha1dc-accel/ against sha1dc/, which it must agree with exactly.\n+ */\n+#if defined(SHA1_DC) && !defined(DC_SHA1_EXTERNAL) && !defined(DC_SHA1_NO_ACCEL)\n+#define HAVE_SHA1DC_ACCEL\n+\n+#if defined(DC_SHA1_SUBMODULE)\n+#include \"sha1collisiondetection/lib/ubc_check.h\"\n+#else\n+#include \"sha1dc/ubc_check.h\"\n+#endif\n+#include \"sha1dc-accel/sha1.h\"\n+#include \"sha1dc-accel/internal.h\"\n+\n+static uint64_t rng_state;\n+\n+static void rng_seed(uint64_t seed)\n+{\n+\trng_state = seed * 2 + 1;\n+}\n+\n+static uint32_t rng(void)\n+{\n+\t/* xorshift64* */\n+\trng_state ^= rng_state >> 12;\n+\trng_state ^= rng_state << 25;\n+\trng_state ^= rng_state >> 27;\n+\treturn (uint32_t)((rng_state * 0x2545F4914F6CDD1DULL) >> 32);\n+}\n+\n+/*\n+ * Hashes `buf` with sha1dc/ and with sha1dc-accel/ under the same settings\n+ * and checks that both agree. Returns whether they found a collision.\n+ */\n+static int check_same(const unsigned char *buf, size_t len, int split,\n+\t\t      int safe_hash, int ubc, int reduced_round)\n+{\n+\tSHA1_CTX want_ctx, got_ctx;\n+\tunsigned char want[20], got[20];\n+\tint want_coll, got_coll;\n+\n+\tSHA1DCInit(&want_ctx);\n+\tSHA1DCSetSafeHash(&want_ctx, safe_hash);\n+\tSHA1DCSetUseUBC(&want_ctx, ubc);\n+\tSHA1DCSetDetectReducedRoundCollision(&want_ctx, reduced_round);\n+\tgot_ctx = want_ctx;\n+\n+\tSHA1DCUpdate(&want_ctx, (const char *)buf, len);\n+\twant_coll = SHA1DCFinal(want, &want_ctx);\n+\n+\tsha1dc_accel_update(&got_ctx, buf, split);\n+\tsha1dc_accel_update(&got_ctx, buf + split, len - split);\n+\tgot_coll = sha1dc_accel_final(got, &got_ctx);\n+\n+\tcl_assert_equal_i(got_coll, want_coll);\n+\tcl_assert(!memcmp(got, want, sizeof(want)));\n+\treturn got_coll;\n+}\n+\n+/*\n+ * sha1dc-accel/ relies on sha1dc/'s table of DVs having the 32 DVs below,\n+ * with DV n at bit n of the UBC mask, and each recompressing from a state\n+ * it saves (step 58 or 65). A change there must fail here, rather than\n+ * quietly check the wrong DV or start from the wrong state.\n+ */\n+static void dv_table_is_as_expected(void)\n+{\n+\tstatic const struct { int type, k, b; } want[] = {\n+\t\t{ 1, 43, 0 }, { 1, 44, 0 }, { 1, 45, 0 }, { 1, 46, 0 },\n+\t\t{ 1, 46, 2 }, { 1, 47, 0 }, { 1, 47, 2 }, { 1, 48, 0 },\n+\t\t{ 1, 48, 2 }, { 1, 49, 0 }, { 1, 49, 2 }, { 1, 50, 0 },\n+\t\t{ 1, 50, 2 }, { 1, 51, 0 }, { 1, 51, 2 }, { 1, 52, 0 },\n+\t\t{ 2, 45, 0 }, { 2, 46, 0 }, { 2, 46, 2 }, { 2, 47, 0 },\n+\t\t{ 2, 48, 0 }, { 2, 49, 0 }, { 2, 49, 2 }, { 2, 50, 0 },\n+\t\t{ 2, 50, 2 }, { 2, 51, 0 }, { 2, 51, 2 }, { 2, 52, 0 },\n+\t\t{ 2, 53, 0 }, { 2, 54, 0 }, { 2, 55, 0 }, { 2, 56, 0 },\n+\t};\n+\tint i;\n+\n+\tfor (i = 0; sha1_dvs[i].dvType != 0; i++) {\n+\t\tconst dv_info_t *dv = &sha1_dvs[i];\n+\n+\t\tcl_assert(i < (int)ARRAY_SIZE(want));\n+\t\tcl_assert_equal_i(dv->dvType, want[i].type);\n+\t\tcl_assert_equal_i(dv->dvK, want[i].k);\n+\t\tcl_assert_equal_i(dv->dvB, want[i].b);\n+\t\tcl_assert_equal_i(dv->maski, 0);\n+\t\tcl_assert_equal_i(dv->maskb, i);\n+\t\tcl_assert(dv->testt == SHA1DC_FROM_58 || dv->testt == SHA1DC_FROM_65);\n+\t}\n+\tcl_assert_equal_i(i, ARRAY_SIZE(want));\n+}\n+\n+static void every_backend_agrees_with_sha1dc(void)\n+{\n+\tconst char *const *names = sha1dc_accel_backends();\n+\tunsigned char buf[4200];\n+\tconst char *orig = sha1dc_accel_backend();\n+\n+\tfor (; *names; names++) {\n+\t\tsize_t i;\n+\n+\t\tcl_assert_equal_i(sha1dc_accel_select(*names), 0);\n+\t\trng_seed(1);\n+\t\tfor (i = 0; i < sizeof(buf); i++)\n+\t\t\tbuf[i] = rng();\n+\n+\t\tfor (i = 0; i < 600; i++) {\n+\t\t\tsize_t len = i < 200 ? i : rng() % (sizeof(buf) - 16);\n+\t\t\tsize_t off = rng() % 16;\n+\t\t\tsize_t split = len ? rng() % (len + 1) : 0;\n+\t\t\t/*\n+\t\t\t * Without the filter, every block is recompressed\n+\t\t\t * for all 32 DVs, which must not find anything in\n+\t\t\t * random data either.\n+\t\t\t */\n+\t\t\tint ubc = i % 5 != 4;\n+\n+\t\t\tcl_assert_equal_i(check_same(buf + off, len, split,\n+\t\t\t\t\t\t     i & 1, ubc, i % 3 == 0), 0);\n+\t\t}\n+\t}\n+\tcl_assert_equal_i(sha1dc_accel_select(orig), 0);\n+}\n+\n+#endif /* HAVE_SHA1DC_ACCEL */\n+\n+#ifdef HAVE_SHA1DC_ACCEL\n+#define RUN_OR_SKIP(fn) fn()\n+#else\n+#define RUN_OR_SKIP(fn) cl_skip()\n+#endif\n+\n+void test_sha1dc__dv_table_is_as_expected(void)\n+{\n+\tRUN_OR_SKIP(dv_table_is_as_expected);\n+}\n+\n+void test_sha1dc__every_backend_agrees_with_sha1dc(void)\n+{\n+\tRUN_OR_SKIP(every_backend_agrees_with_sha1dc);\n+}\n-- \n2.50.1 (Apple Git-155)\n\n\n"},{"id":"553585","messageId":"20260929112544.86511-3-scott@gitbutler.net","threadId":"66420","inReplyTo":"20260929112544.86511-1-scott@gitbutler.net","subject":"[PATCH 2/4] sha1dc-accel: vectorize the unavoidable-bitconditions check","fromName":"Scott Chacon","fromEmail":"scott@gitbutler.net","sentAt":"2026-09-29T11:25:42Z","receivedAt":"2026-09-29T11:25:59Z","isPatch":true,"body":"After compressing a block, sha1dc checks its expanded message schedule\nagainst the \"unavoidable bitconditions\" (UBCs) of each of its 32\ndisturbance vectors (DVs). Each condition says that one bit of W[i]\nXORed with one bit of W[j] must have a particular value if an attack\nalong that DV is in progress. A failed condition rules out its DVs, and\nif all 32 are ruled out, which happens for about 95% of blocks, we can\nskip the expensive recompression.\n\nThat makes the check a cheap filter, but it's cheap only compared to\nrecompressing. It's 111 scalar statements, of which 47 run for every\nblock, and the rest sit behind tests of whether their DVs are still\nalive. On this machine it takes about half as long as the compression\nitself.\n\nThe conditions for any one DV aren't a fixed list, though. They're\nequations over the bits of the schedule, and equations chain: if bit A\nmust equal bit B, and B must equal C, then A must equal C. So each DV\nreally has a whole space of equivalent condition sets. The generator\nthat wrote sha1dc's ubc_check.c picked conditions that are shared by\nmany DVs, which is the right thing for scalar code. But a vector unit\ncan check 4 (or 8) conditions in a single pair of loads if they have the\nsame shape: the same distance between the two words, the same bit\npositions, at consecutive values of i. That wants a different choice.\n\nThe sha1dc Rust crate has a solver that makes that choice for each\ninstruction set. It picks a \"prefix\" of vector groups that runs on every\nblock, sized so that it rules out as many blocks as possible for what\nit costs, and leaves the remaining conditions to a scalar \"tail\" that\nonly runs for DVs the prefix left alive. Its plans work out roughly like\nthis (the last column is the solver's estimate for random blocks):\n\n  form    prefix               tail   blocks reaching tail\n  scalar  70 statements        86     21%\n  sse2    26 groups of 4       58      9%\n  avx2    16 groups of 8       44      7%\n  neon    20 groups of 4       77     17%\n\nThe crate only emits Rust, so ubc_check.c carries its plans over as\ntables: for each form, the conditions of its prefix (as one entry per\nvector group, giving the two words, their shifts, and the bit and DVs\nof each lane), and the remaining conditions of each DV for its tail.\nThe code that runs them is a short loop per form. We ask the compiler to\nunroll the prefix loops fully, so that each table entry turns back into\nimmediates; without that, the forms are 2.2x to 2.4x slower with GCC\nand 1.3x to 3.6x slower with clang. With it, GCC's build of the tables\nruns the same number of instructions as the crate's plans written out as\nstraight-line code, at the same speed. The exception so far is clang 18\non x86-64, where the scalar form runs at half that speed (68ns a block\ninstead of 34ns), since it spills partial masks to the stack. That form\nis only the fallback for CPUs without SSE2 or NEON, and Apple clang 21\ndoes not do this.\n\nThe tables come from the crate as of commit 426b4afd. The crate is MIT\nor Apache-2.0 at your option (sha1collisiondetection itself is MIT); we\nuse the tables under the MIT license, and the file carries its notice.\nNote that the crate stores its schedule backwards on x86 (to save a\nshuffle in its SHA-NI code), where we keep it in step order everywhere,\nso our SSE2 and AVX2 tables list their lanes in the opposite order from\nthe crate's.\n\nWe now have these backends, in order of preference:\n\n  - portable+avx2: if the CPU has AVX2 (and the OS saves the YMM\n    registers, which we check with xgetbv)\n\n  - portable+sse2: always on x86-64, where SSE2 is part of the ABI\n\n  - portable+neon: always on arm64\n\n  - portable: everywhere else, which still gets the new scalar form\n\nThe vector forms need target attributes and intrinsics, so for now\nthey're only built with GCC 5 or newer and clang. Other compilers (and\n32-bit x86, where SSE2 isn't a given) get only the portable one.\n\nWith 256MB of random data again, the Xeon picks portable+avx2:\n\n  Benchmark 1: test-tool.old sha1\n    Time (mean ± σ):     801.1 ms ±  82.9 ms    [User: 750.1 ms, System: 40.3 ms]\n    Range (min … max):   673.1 ms … 1006.1 ms    30 runs\n\n  Benchmark 2: test-tool.new sha1\n    Time (mean ± σ):     620.4 ms ± 111.2 ms    [User: 571.0 ms, System: 41.9 ms]\n    Range (min … max):   486.4 ms … 857.2 ms    30 runs\n\n  Summary\n    test-tool.new sha1 ran\n      1.29 ± 0.27 times faster than test-tool.old sha1\n\nand callgrind counts 16% fewer instructions than before this patch. The\nM5 Max picks portable+neon, and hashes 1GiB in 1.22s instead of 1.55s\n(median of 9 runs), 1.27x faster.\n\nFor testing, the unit test compares every form against sha1dc's own\nubc_check(). Random schedules aren't enough, though: the prefix rules\nout most of them, so the tail checks for any one DV would hardly ever\nrun. So for each DV, the test also generates random schedules until one\nkeeps that DV alive, and then compares all forms on it with each of its\n2560 bits flipped in turn. That's the same approach the crate takes (and\nsha1collisiondetection's own tools before it).\n\nOutside of the test suite, I also checked every form against ubc_check()\non a million random schedules and 256 of those witnesses: built with\nGCC 13 and clang 18 on x86-64, with Apple clang on arm64 (and with it\ntargeting x86-64, running the SSE2 form under Rosetta and the AVX2 one\ntranslated to NEON by SIMDe), and with GCC and clang for aarch64 under\nqemu.\n\nSigned-off-by: Scott Chacon <scott@gitbutler.net>\nAssisted-by: Claude Opus 5.5 <noreply@anthropic.com>\n---\n Makefile                            |    5 +-\n contrib/buildsystems/CMakeLists.txt |    2 +-\n meson.build                         |    2 +\n sha1dc-accel/internal.h             |   49 +\n sha1dc-accel/sha1.c                 |   47 +-\n sha1dc-accel/ubc_check.c            | 1789 +++++++++++++++++++++++++++\n sha1dc-accel/x86.c                  |   38 +\n t/unit-tests/u-sha1dc.c             |   75 ++\n 8 files changed, 1985 insertions(+), 22 deletions(-)\n create mode 100644 sha1dc-accel/ubc_check.c\n create mode 100644 sha1dc-accel/x86.c\n\ndiff --git a/Makefile b/Makefile\nindex 9ab13ca2ab..3ad8a7fc92 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -568,7 +568,8 @@ include shared.mak\n # submodule.\n #\n # Unless DC_SHA1_EXTERNAL is defined, the built-in code is driven by the\n-# block loop in sha1dc-accel/, which gives the same results.\n+# faster implementation in sha1dc-accel/, which gives the same results\n+# using the CPU's vector units where it has them.\n # Define DC_SHA1_NO_ACCEL to use the sha1collisiondetection code alone.\n #\n # === SHA-256 backend ===\n@@ -2177,6 +2178,8 @@ ifdef DC_SHA1_NO_ACCEL\n \tBASIC_CFLAGS += -DDC_SHA1_NO_ACCEL\n else\n \tLIB_OBJS += sha1dc-accel/sha1.o\n+\tLIB_OBJS += sha1dc-accel/ubc_check.o\n+\tLIB_OBJS += sha1dc-accel/x86.o\n endif\n \tBASIC_CFLAGS += \\\n \t\t-DSHA1DC_NO_STANDARD_INCLUDES \\\ndiff --git a/contrib/buildsystems/CMakeLists.txt b/contrib/buildsystems/CMakeLists.txt\nindex 3c0ea2a27c..67b96d601b 100644\n--- a/contrib/buildsystems/CMakeLists.txt\n+++ b/contrib/buildsystems/CMakeLists.txt\n@@ -218,7 +218,7 @@ add_compile_definitions(NO_OPENSSL SHA1_DC SHA1DC_NO_STANDARD_INCLUDES\n \t\t\tSHA1DC_INIT_SAFE_HASH_DEFAULT=0\n \t\t\tSHA1DC_CUSTOM_INCLUDE_SHA1_C=\"git-compat-util.h\"\n \t\t\tSHA1DC_CUSTOM_INCLUDE_UBC_CHECK_C=\"git-compat-util.h\" )\n-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)\n+list(APPEND compat_SOURCES sha1dc_git.c sha1dc/sha1.c sha1dc/ubc_check.c sha1dc-accel/sha1.c sha1dc-accel/ubc_check.c sha1dc-accel/x86.c block-sha1/sha1.c sha256/block/sha256.c compat/qsort_s.c)\n \n \n add_compile_definitions(PAGER_ENV=\"LESS=FRX LV=-c\"\ndiff --git a/meson.build b/meson.build\nindex a821b85f30..47a60526e9 100644\n--- a/meson.build\n+++ b/meson.build\n@@ -1632,6 +1632,8 @@ if sha1_backend == 'sha1dc'\n     'sha1dc/sha1.c',\n     'sha1dc/ubc_check.c',\n     'sha1dc-accel/sha1.c',\n+    'sha1dc-accel/ubc_check.c',\n+    'sha1dc-accel/x86.c',\n   ]\n endif\n if sha1_backend == 'CommonCrypto' or sha1_unsafe_backend == 'CommonCrypto'\ndiff --git a/sha1dc-accel/internal.h b/sha1dc-accel/internal.h\nindex bf3513a1e3..03427224da 100644\n--- a/sha1dc-accel/internal.h\n+++ b/sha1dc-accel/internal.h\n@@ -10,10 +10,38 @@\n  * A \"state\" is the five working words [a, b, c, d, e] before a step.\n  */\n \n+/*\n+ * Which forms this build can have. The vector and hardware forms need\n+ * GCC-compatible target attributes and intrinsics; anything else gets the\n+ * portable form, which every build has.\n+ */\n+#if defined(__GNUC__) && !defined(SHA1DC_ACCEL_PORTABLE_ONLY)\n+# if defined(__x86_64__) && (defined(__clang__) || __GNUC__ >= 5)\n+#  define SHA1DC_HAVE_SSE2 1\n+#  define SHA1DC_HAVE_AVX2 1\n+#  include <immintrin.h>\n+#  define SHA1DC_TARGET_SSE2\n+#  define SHA1DC_TARGET_AVX2 __attribute__((target(\"avx2\")))\n+# elif defined(__aarch64__) && defined(__ARM_NEON)\n+#  define SHA1DC_HAVE_NEON 1\n+#  include <arm_neon.h>\n+# endif\n+#endif\n+\n #if defined(__GNUC__)\n # define SHA1DC_NOINLINE __attribute__((noinline))\n+# define sha1dc_ctz(x) ((unsigned)__builtin_ctz(x))\n #else\n # define SHA1DC_NOINLINE\n+static inline unsigned sha1dc_ctz(uint32_t x)\n+{\n+\tunsigned n = 0;\n+\twhile (!(x & 1)) {\n+\t\tx >>= 1;\n+\t\tn++;\n+\t}\n+\treturn n;\n+}\n #endif\n \n /* The step a DV's recompression starts from. */\n@@ -22,4 +50,25 @@ enum sha1dc_from {\n \tSHA1DC_FROM_65 = 65\n };\n \n+/*\n+ * The UBC check, one form per instruction set. Each returns the same mask\n+ * as ubc_check() in sha1dc/: a set bit names a DV that is still possible.\n+ * See ubc_check.c.\n+ */\n+uint32_t sha1dc_ubc_check_scalar(const uint32_t w[80]);\n+#ifdef SHA1DC_HAVE_SSE2\n+uint32_t sha1dc_ubc_check_sse2(const uint32_t w[80]);\n+#endif\n+#ifdef SHA1DC_HAVE_AVX2\n+uint32_t sha1dc_ubc_check_avx2(const uint32_t w[80]);\n+#endif\n+#ifdef SHA1DC_HAVE_NEON\n+uint32_t sha1dc_ubc_check_neon(const uint32_t w[80]);\n+#endif\n+\n+/* Whether the CPU (and OS) can run the AVX2 form. In x86.c. */\n+#ifdef SHA1DC_HAVE_AVX2\n+int sha1dc_avx2_available(void);\n+#endif\n+\n #endif /* SHA1DC_ACCEL_INTERNAL_H */\ndiff --git a/sha1dc-accel/sha1.c b/sha1dc-accel/sha1.c\nindex fd75289997..1b3d82b4e4 100644\n--- a/sha1dc-accel/sha1.c\n+++ b/sha1dc-accel/sha1.c\n@@ -1,19 +1,23 @@\n /*\n- * SHA-1 with collision detection.\n+ * SHA-1 with collision detection, faster.\n  *\n  * This computes exactly what sha1dc/ computes: the SHA-1 digest of the\n  * input, and whether any block of it looks like one half of a collision\n  * made by one of the 32 known disturbance vectors (DVs) of Stevens and\n- * Shumow. It works on sha1dc's SHA1_CTX, and uses its table of DVs, but\n- * has its own block loop, which gives the following patches room to\n- * follow the approach of the \"sha1dc\" Rust crate by Sam Reis\n- * (https://github.com/srijs/sha1dc), which gitoxide uses.\n+ * Shumow. It is a port to C of the approach of the \"sha1dc\" Rust crate by\n+ * Sam Reis (https://github.com/srijs/sha1dc), which gitoxide uses:\n  *\n- * Each block is compressed by a \"backend\", which also spills the expanded\n- * message schedule, and the two intermediate states that recompression\n- * starts from (at steps 58 and 65). The unavoidable-bitconditions (UBC)\n- * filter then rules out about 95% of blocks; the rest are recompressed,\n- * once for each DV the filter could not rule out.\n+ *  - The unavoidable-bitconditions (UBC) filter, which rules out about 95%\n+ *    of blocks and is most of what detection costs, has one form per\n+ *    instruction set (SSE2, AVX2, NEON and portable C). For each, the\n+ *    crate's solver picked conditions equivalent to the published ones\n+ *    that fill vector lanes well, for a prefix run on every block, and left\n+ *    the rest to a scalar tail that few blocks reach. Those choices are\n+ *    kept as tables, run by a short loop per form. See ubc_check.c.\n+ *\n+ * The compression is portable C, and spills the expanded message schedule\n+ * and the two states that recompression starts from (at steps 58 and 65)\n+ * as it goes.\n  */\n \n #include \"../git-compat-util.h\"\n@@ -221,18 +225,21 @@ struct backend {\n \tint (*available)(void);\n };\n \n-/* sha1dc's own UBC check. */\n-static uint32_t ubc_check_sha1dc(const uint32_t w[80])\n-{\n-\tuint32_t mask;\n-\n-\tubc_check(w, &mask);\n-\treturn mask;\n-}\n-\n /* In order of preference. */\n static const struct backend backends[] = {\n-\t{ \"portable\", compress_portable, ubc_check_sha1dc, NULL },\n+#ifdef SHA1DC_HAVE_AVX2\n+\t{ \"portable+avx2\", compress_portable, sha1dc_ubc_check_avx2,\n+\t  sha1dc_avx2_available },\n+#endif\n+#ifdef SHA1DC_HAVE_SSE2\n+\t{ \"portable+sse2\", compress_portable, sha1dc_ubc_check_sse2,\n+\t  NULL },\n+#endif\n+#ifdef SHA1DC_HAVE_NEON\n+\t{ \"portable+neon\", compress_portable, sha1dc_ubc_check_neon,\n+\t  NULL },\n+#endif\n+\t{ \"portable\", compress_portable, sha1dc_ubc_check_scalar, NULL },\n };\n \n static int usable(const struct backend *be)\ndiff --git a/sha1dc-accel/ubc_check.c b/sha1dc-accel/ubc_check.c\nnew file mode 100644\nindex 0000000000..f95b799f9d\n--- /dev/null\n+++ b/sha1dc-accel/ubc_check.c\n@@ -0,0 +1,1789 @@\n+/*\n+ * The unavoidable-bitconditions (UBC) check of SHA-1 collision detection,\n+ * in one form per instruction set.\n+ *\n+ * Every form returns the same mask as ubc_check() in sha1dc/ubc_check.c:\n+ * one bit per disturbance vector (DV) that the expanded message w[] has not\n+ * ruled out. A DV is ruled out as soon as one of its bitconditions fails;\n+ * each condition says that bit a of w[i] XOR bit b of w[j] equals c.\n+ *\n+ * Each form runs in two parts. The prefix tests a fixed set of conditions,\n+ * chosen and packed into vector lanes for that instruction set, on every\n+ * block; it rules out every DV for almost all blocks. The few blocks that\n+ * survive it run the tail, which tests the remaining conditions of each DV\n+ * still alive.\n+ *\n+ * The tables in this file were derived from the output of the solver in\n+ * the \"sha1dc\" Rust crate by Sam Reis (https://github.com/srijs/sha1dc,\n+ * commit 426b4afd), which picks the conditions and their packing. They are\n+ * used under the MIT license:\n+ *\n+ *   Copyright (c) 2017 Marc Stevens (Cryptology Group, Centrum Wiskunde &\n+ *   Informatica)\n+ *   Copyright (c) 2017 Dan Shumow (Microsoft Research)\n+ *   Copyright (c) 2026 Sam Reis\n+ *\n+ *   Permission is hereby granted, free of charge, to any person obtaining a\n+ *   copy of this software and associated documentation files (the\n+ *   \"Software\"), to deal in the Software without restriction, including\n+ *   without limitation the rights to use, copy, modify, merge, publish,\n+ *   distribute, sublicense, and/or sell copies of the Software, and to\n+ *   permit persons to whom the Software is furnished to do so, subject to\n+ *   the following conditions:\n+ *\n+ *   The above copyright notice and this permission notice shall be included\n+ *   in all copies or substantial portions of the Software.\n+ *\n+ *   THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS\n+ *   OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\n+ *   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.\n+ *   IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY\n+ *   CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,\n+ *   TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE\n+ *   SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.\n+ */\n+\n+#include \"../git-compat-util.h\"\n+#include \"internal.h\"\n+\n+#define DV_I_43_0_BIT ((uint32_t)1 << 0)\n+#define DV_I_44_0_BIT ((uint32_t)1 << 1)\n+#define DV_I_45_0_BIT ((uint32_t)1 << 2)\n+#define DV_I_46_0_BIT ((uint32_t)1 << 3)\n+#define DV_I_46_2_BIT ((uint32_t)1 << 4)\n+#define DV_I_47_0_BIT ((uint32_t)1 << 5)\n+#define DV_I_47_2_BIT ((uint32_t)1 << 6)\n+#define DV_I_48_0_BIT ((uint32_t)1 << 7)\n+#define DV_I_48_2_BIT ((uint32_t)1 << 8)\n+#define DV_I_49_0_BIT ((uint32_t)1 << 9)\n+#define DV_I_49_2_BIT ((uint32_t)1 << 10)\n+#define DV_I_50_0_BIT ((uint32_t)1 << 11)\n+#define DV_I_50_2_BIT ((uint32_t)1 << 12)\n+#define DV_I_51_0_BIT ((uint32_t)1 << 13)\n+#define DV_I_51_2_BIT ((uint32_t)1 << 14)\n+#define DV_I_52_0_BIT ((uint32_t)1 << 15)\n+#define DV_II_45_0_BIT ((uint32_t)1 << 16)\n+#define DV_II_46_0_BIT ((uint32_t)1 << 17)\n+#define DV_II_46_2_BIT ((uint32_t)1 << 18)\n+#define DV_II_47_0_BIT ((uint32_t)1 << 19)\n+#define DV_II_48_0_BIT ((uint32_t)1 << 20)\n+#define DV_II_49_0_BIT ((uint32_t)1 << 21)\n+#define DV_II_49_2_BIT ((uint32_t)1 << 22)\n+#define DV_II_50_0_BIT ((uint32_t)1 << 23)\n+#define DV_II_50_2_BIT ((uint32_t)1 << 24)\n+#define DV_II_51_0_BIT ((uint32_t)1 << 25)\n+#define DV_II_51_2_BIT ((uint32_t)1 << 26)\n+#define DV_II_52_0_BIT ((uint32_t)1 << 27)\n+#define DV_II_53_0_BIT ((uint32_t)1 << 28)\n+#define DV_II_54_0_BIT ((uint32_t)1 << 29)\n+#define DV_II_55_0_BIT ((uint32_t)1 << 30)\n+#define DV_II_56_0_BIT ((uint32_t)1 << 31)\n+\n+/*\n+ * The prefixes loop over constant tables. Unrolling those loops fully lets\n+ * the compiler fold each entry into the code as immediates, which is what\n+ * makes them fast; without it they are two to three times slower.\n+ */\n+#if defined(__clang__) || (defined(__GNUC__) && __GNUC__ >= 8)\n+#define UNROLL_TABLE _Pragma(\"GCC unroll 128\")\n+#else\n+#define UNROLL_TABLE\n+#endif\n+\n+/*\n+ * The tail loops run over a few conditions at a time, too few to gain from\n+ * vectorizing; clang would otherwise vectorize them when targeting AVX2.\n+ */\n+#ifdef __clang__\n+#define NO_VECTORIZE _Pragma(\"clang loop vectorize(disable)\")\n+#else\n+#define NO_VECTORIZE\n+#endif\n+\n+/* A bitcondition: bit a of w[i] XOR bit b of w[j] must equal c. */\n+struct ubc_cond {\n+\tuint8_t i, a, j, b, c;\n+};\n+\n+static inline uint32_t cond_fails(const uint32_t *w, const struct ubc_cond *c)\n+{\n+\treturn (((w[c->i] >> c->a) ^ (w[c->j] >> c->b) ^ c->c) & 1);\n+}\n+\n+/* A condition of the scalar prefix, and the DVs it rules out if it fails. */\n+struct ubc_prefix_cond {\n+\tstruct ubc_cond cond;\n+\tuint32_t dvs;\n+};\n+\n+/*\n+ * A group of conditions for a vector prefix, one per lane. In lane k, the\n+ * bit selected by test[k] of (w[lo + k] >> lo_shift) ^ (w[hi + k] >> hi_shift)\n+ * must equal want, or the DVs in dvs[k] are ruled out. The lanes share\n+ * everything but test[] and dvs[]; an unused lane has both 0.\n+ *\n+ * No group reads past w[66].\n+ */\n+struct ubc_group4 {\n+\tuint8_t lo, lo_shift, hi, hi_shift, want;\n+\tuint32_t test[4];\n+\tuint32_t dvs[4];\n+};\n+\n+struct ubc_group8 {\n+\tuint8_t lo, lo_shift, hi, hi_shift, want;\n+\tuint32_t test[8];\n+\tuint32_t dvs[8];\n+};\n+\n+/* The tail conditions of DV d are checks[spans[d].start] onwards. */\n+struct tail_span {\n+\tuint16_t start;\n+\tuint8_t len;\n+};\n+\n+/*\n+ * Runs the tail conditions of each DV still alive in `mask`, and clears\n+ * the DVs with a failing one. Each condition fails about half the time, so\n+ * it tests all of a DV's conditions rather than branch on each one.\n+ */\n+static inline uint32_t run_tail(const uint32_t *w, uint32_t mask,\n+\t\t\t\tconst struct ubc_cond *checks,\n+\t\t\t\tconst struct tail_span *spans)\n+{\n+\tuint32_t out = mask;\n+\twhile (mask) {\n+\t\tunsigned d = sha1dc_ctz(mask);\n+\t\tconst struct ubc_cond *c = checks + spans[d].start;\n+\t\tconst struct ubc_cond *end = c + spans[d].len;\n+\t\tuint32_t fail = 0;\n+\n+\t\tNO_VECTORIZE\n+\t\tfor (; c < end; c++)\n+\t\t\tfail |= cond_fails(w, c);\n+\t\tout &= ~(fail << d);\n+\t\tmask &= mask - 1;\n+\t}\n+\treturn out;\n+}\n+\n+/* scalar form */\n+\n+static const struct ubc_prefix_cond scalar_prefix_conds[] = {\n+\t{ { 44, 29, 45, 29, 0 },\n+\t  DV_I_48_0_BIT | DV_I_51_0_BIT | DV_I_52_0_BIT | DV_II_45_0_BIT |\n+\t  DV_II_46_0_BIT | DV_II_50_0_BIT | DV_II_51_0_BIT },\n+\t{ { 46, 29, 47, 29, 0 },\n+\t  DV_I_43_0_BIT | DV_I_50_0_BIT | DV_II_47_0_BIT | DV_II_48_0_BIT |\n+\t  DV_II_52_0_BIT | DV_II_53_0_BIT },\n+\t{ { 45, 4, 48, 29, 0 },\n+\t  DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_49_0_BIT | DV_I_51_0_BIT |\n+\t  DV_II_49_0_BIT | DV_II_54_0_BIT },\n+\t{ { 49, 29, 50, 29, 0 },\n+\t  DV_I_46_0_BIT | DV_II_45_0_BIT | DV_II_50_0_BIT | DV_II_51_0_BIT |\n+\t  DV_II_55_0_BIT | DV_II_56_0_BIT },\n+\t{ { 40, 29, 41, 29, 0 },\n+\t  DV_I_44_0_BIT | DV_I_47_0_BIT | DV_I_48_0_BIT | DV_II_46_0_BIT |\n+\t  DV_II_47_0_BIT | DV_II_56_0_BIT },\n+\t{ { 36, 1, 37, 6, 1 },\n+\t  DV_I_47_2_BIT | DV_I_50_2_BIT | DV_II_46_2_BIT },\n+\t{ { 47, 29, 48, 29, 0 },\n+\t  DV_I_44_0_BIT | DV_I_51_0_BIT | DV_II_48_0_BIT | DV_II_49_0_BIT |\n+\t  DV_II_53_0_BIT | DV_II_54_0_BIT },\n+\t{ { 39, 1, 40, 6, 1 },\n+\t  DV_I_46_2_BIT | DV_I_50_2_BIT | DV_II_49_2_BIT },\n+\t{ { 40, 1, 41, 6, 1 },\n+\t  DV_I_47_2_BIT | DV_I_51_2_BIT | DV_II_50_2_BIT },\n+\t{ { 41, 1, 42, 6, 1 },\n+\t  DV_I_48_2_BIT | DV_II_46_2_BIT | DV_II_51_2_BIT },\n+\t{ { 43, 4, 46, 29, 0 },\n+\t  DV_I_43_0_BIT | DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_49_0_BIT |\n+\t  DV_II_47_0_BIT | DV_II_52_0_BIT },\n+\t{ { 46, 4, 49, 29, 0 },\n+\t  DV_I_46_0_BIT | DV_I_48_0_BIT | DV_I_50_0_BIT | DV_I_52_0_BIT |\n+\t  DV_II_50_0_BIT | DV_II_55_0_BIT },\n+\t{ { 45, 6, 47, 6, 0 },\n+\t  DV_I_47_2_BIT | DV_I_49_2_BIT | DV_I_51_2_BIT },\n+\t{ { 45, 29, 46, 29, 0 },\n+\t  DV_I_49_0_BIT | DV_I_52_0_BIT | DV_II_46_0_BIT | DV_II_47_0_BIT |\n+\t  DV_II_51_0_BIT | DV_II_52_0_BIT },\n+\t{ { 44, 4, 47, 29, 0 },\n+\t  DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_48_0_BIT | DV_I_50_0_BIT |\n+\t  DV_II_48_0_BIT | DV_II_53_0_BIT },\n+\t{ { 48, 29, 49, 29, 0 },\n+\t  DV_I_45_0_BIT | DV_I_52_0_BIT | DV_II_49_0_BIT | DV_II_50_0_BIT |\n+\t  DV_II_54_0_BIT | DV_II_55_0_BIT },\n+\t{ { 44, 6, 46, 6, 0 },\n+\t  DV_I_46_2_BIT | DV_I_48_2_BIT | DV_I_50_2_BIT },\n+\t{ { 47, 4, 50, 29, 0 },\n+\t  DV_I_47_0_BIT | DV_I_49_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT |\n+\t  DV_II_51_0_BIT | DV_II_56_0_BIT },\n+\t{ { 35, 1, 36, 6, 1 },\n+\t  DV_I_46_2_BIT | DV_I_49_2_BIT },\n+\t{ { 44, 1, 45, 6, 1 },\n+\t  DV_I_51_2_BIT | DV_II_49_2_BIT },\n+\t{ { 42, 6, 43, 1, 0 },\n+\t  DV_II_46_2_BIT | DV_II_51_2_BIT },\n+\t{ { 37, 4, 40, 29, 0 },\n+\t  DV_I_43_0_BIT | DV_I_47_0_BIT | DV_II_46_0_BIT | DV_II_53_0_BIT |\n+\t  DV_II_55_0_BIT },\n+\t{ { 41, 6, 42, 1, 0 },\n+\t  DV_I_51_2_BIT | DV_II_50_2_BIT },\n+\t{ { 40, 4, 43, 29, 0 },\n+\t  DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_50_0_BIT | DV_II_49_0_BIT |\n+\t  DV_II_56_0_BIT },\n+\t{ { 41, 4, 44, 29, 0 },\n+\t  DV_I_43_0_BIT | DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_51_0_BIT |\n+\t  DV_II_45_0_BIT | DV_II_50_0_BIT },\n+\t{ { 52, 29, 53, 29, 0 },\n+\t  DV_I_49_0_BIT | DV_II_45_0_BIT | DV_II_48_0_BIT | DV_II_53_0_BIT |\n+\t  DV_II_54_0_BIT },\n+\t{ { 40, 6, 41, 1, 0 },\n+\t  DV_I_50_2_BIT | DV_II_49_2_BIT },\n+\t{ { 46, 6, 47, 1, 0 },\n+\t  DV_I_46_2_BIT | DV_II_50_2_BIT },\n+\t{ { 47, 6, 48, 1, 0 },\n+\t  DV_I_47_2_BIT | DV_II_51_2_BIT },\n+\t{ { 42, 4, 45, 29, 0 },\n+\t  DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_48_0_BIT | DV_I_52_0_BIT |\n+\t  DV_II_46_0_BIT | DV_II_51_0_BIT },\n+\t{ { 37, 1, 38, 6, 1 },\n+\t  DV_I_48_2_BIT | DV_I_51_2_BIT },\n+\t{ { 43, 6, 45, 6, 0 },\n+\t  DV_I_47_2_BIT | DV_I_49_2_BIT },\n+\t{ { 53, 29, 54, 29, 0 },\n+\t  DV_I_50_0_BIT | DV_II_46_0_BIT | DV_II_49_0_BIT | DV_II_54_0_BIT |\n+\t  DV_II_55_0_BIT },\n+\t{ { 41, 29, 42, 29, 0 },\n+\t  DV_I_45_0_BIT | DV_I_48_0_BIT | DV_I_49_0_BIT | DV_II_47_0_BIT |\n+\t  DV_II_48_0_BIT },\n+\t{ { 50, 29, 51, 29, 0 },\n+\t  DV_I_47_0_BIT | DV_II_46_0_BIT | DV_II_51_0_BIT | DV_II_52_0_BIT |\n+\t  DV_II_56_0_BIT },\n+\t{ { 61, 2, 62, 7, 1 },\n+\t  DV_I_46_2_BIT | DV_II_46_2_BIT },\n+\t{ { 46, 6, 48, 6, 0 },\n+\t  DV_I_48_2_BIT | DV_I_50_2_BIT },\n+\t{ { 39, 4, 42, 29, 0 },\n+\t  DV_I_43_0_BIT | DV_I_45_0_BIT | DV_I_49_0_BIT | DV_II_48_0_BIT |\n+\t  DV_II_55_0_BIT },\n+\t{ { 43, 29, 44, 29, 0 },\n+\t  DV_I_47_0_BIT | DV_I_50_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT |\n+\t  DV_II_49_0_BIT | DV_II_50_0_BIT },\n+\t{ { 47, 6, 49, 6, 0 },\n+\t  DV_I_49_2_BIT | DV_I_51_2_BIT },\n+\t{ { 51, 29, 52, 29, 0 },\n+\t  DV_I_48_0_BIT | DV_II_47_0_BIT | DV_II_52_0_BIT | DV_II_53_0_BIT },\n+\t{ { 36, 0, 37, 5, 1 },\n+\t  DV_II_49_2_BIT },\n+\t{ { 37, 0, 38, 5, 1 },\n+\t  DV_II_50_2_BIT },\n+\t{ { 38, 0, 39, 5, 1 },\n+\t  DV_II_51_2_BIT },\n+\t{ { 38, 4, 41, 29, 0 },\n+\t  DV_I_44_0_BIT | DV_I_48_0_BIT | DV_II_47_0_BIT | DV_II_54_0_BIT |\n+\t  DV_II_56_0_BIT },\n+\t{ { 50, 6, 51, 1, 0 },\n+\t  DV_I_50_2_BIT | DV_II_46_2_BIT },\n+\t{ { 42, 6, 44, 6, 0 },\n+\t  DV_I_46_2_BIT | DV_I_48_2_BIT },\n+\t{ { 48, 4, 51, 29, 0 },\n+\t  DV_I_48_0_BIT | DV_I_50_0_BIT | DV_I_52_0_BIT | DV_II_46_0_BIT |\n+\t  DV_II_52_0_BIT },\n+\t{ { 42, 29, 43, 29, 0 },\n+\t  DV_I_46_0_BIT | DV_I_49_0_BIT | DV_I_50_0_BIT | DV_II_48_0_BIT |\n+\t  DV_II_49_0_BIT },\n+\t{ { 54, 29, 55, 29, 0 },\n+\t  DV_I_51_0_BIT | DV_II_47_0_BIT | DV_II_50_0_BIT | DV_II_55_0_BIT |\n+\t  DV_II_56_0_BIT },\n+\t{ { 38, 1, 39, 6, 1 },\n+\t  DV_I_49_2_BIT },\n+\t{ { 45, 1, 46, 6, 1 },\n+\t  DV_II_50_2_BIT },\n+\t{ { 46, 1, 47, 6, 1 },\n+\t  DV_II_51_2_BIT },\n+\t{ { 50, 1, 51, 6, 1 },\n+\t  DV_II_49_2_BIT },\n+\t{ { 39, 4, 40, 29, 1 },\n+\t  DV_I_43_0_BIT | DV_II_53_0_BIT | DV_II_55_0_BIT },\n+\t{ { 55, 29, 56, 29, 0 },\n+\t  DV_I_52_0_BIT | DV_II_48_0_BIT | DV_II_51_0_BIT | DV_II_56_0_BIT },\n+\t{ { 48, 6, 50, 6, 0 },\n+\t  DV_I_50_2_BIT | DV_II_46_2_BIT },\n+\t{ { 49, 4, 52, 29, 0 },\n+\t  DV_I_49_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT | DV_II_47_0_BIT |\n+\t  DV_II_53_0_BIT },\n+\t{ { 40, 4, 41, 29, 1 },\n+\t  DV_I_44_0_BIT | DV_II_54_0_BIT | DV_II_56_0_BIT },\n+\t{ { 41, 4, 42, 29, 1 },\n+\t  DV_I_43_0_BIT | DV_I_45_0_BIT | DV_II_55_0_BIT },\n+\t{ { 42, 1, 43, 6, 1 },\n+\t  DV_I_49_2_BIT },\n+\t{ { 51, 1, 52, 6, 1 },\n+\t  DV_II_50_2_BIT },\n+\t{ { 52, 1, 53, 6, 1 },\n+\t  DV_II_51_2_BIT },\n+\t{ { 62, 2, 63, 7, 1 },\n+\t  DV_I_47_2_BIT },\n+\t{ { 63, 2, 64, 7, 1 },\n+\t  DV_I_48_2_BIT },\n+\t{ { 45, 6, 46, 1, 0 },\n+\t  DV_II_49_2_BIT },\n+\t{ { 36, 4, 40, 29, 0 },\n+\t  DV_I_46_0_BIT | DV_I_49_0_BIT | DV_II_45_0_BIT | DV_II_48_0_BIT },\n+\t{ { 50, 4, 53, 29, 0 },\n+\t  DV_I_50_0_BIT | DV_I_52_0_BIT | DV_II_46_0_BIT | DV_II_48_0_BIT |\n+\t  DV_II_54_0_BIT },\n+\t{ { 56, 29, 57, 29, 0 },\n+\t  DV_II_49_0_BIT | DV_II_52_0_BIT },\n+\t{ { 43, 4, 44, 29, 1 },\n+\t  DV_I_43_0_BIT | DV_I_45_0_BIT | DV_I_47_0_BIT }\n+};\n+\n+static const struct ubc_cond scalar_tail_checks[] = {\n+\t/* DV_I_43_0 */\n+\t{ 58, 0, 59, 5, 1 },\n+\t{ 58, 0, 63, 30, 1 },\n+\t{ 61, 1, 62, 6, 1 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t/* DV_I_44_0 */\n+\t{ 40, 4, 42, 4, 1 },\n+\t{ 42, 4, 44, 4, 1 },\n+\t{ 59, 0, 60, 5, 1 },\n+\t{ 59, 0, 64, 30, 1 },\n+\t{ 62, 1, 63, 6, 1 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t/* DV_I_45_0 */\n+\t{ 43, 4, 45, 4, 1 },\n+\t{ 60, 0, 61, 5, 1 },\n+\t{ 63, 1, 64, 6, 1 },\n+\t{ 35, 4, 39, 29, 0 },\n+\t/* DV_I_46_0 */\n+\t{ 40, 4, 42, 4, 1 },\n+\t{ 42, 4, 44, 4, 1 },\n+\t{ 44, 4, 46, 4, 1 },\n+\t{ 61, 0, 62, 5, 1 },\n+\t/* DV_I_46_2 */\n+\t{ 39, 1, 42, 6, 1 },\n+\t/* DV_I_47_0 */\n+\t{ 43, 4, 45, 4, 1 },\n+\t{ 45, 4, 47, 4, 1 },\n+\t{ 62, 0, 63, 5, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t/* DV_I_47_2 */\n+\t{ 40, 1, 43, 6, 1 },\n+\t/* DV_I_48_0 */\n+\t{ 42, 4, 44, 4, 1 },\n+\t{ 44, 4, 46, 4, 1 },\n+\t{ 46, 4, 48, 4, 1 },\n+\t{ 63, 0, 64, 5, 1 },\n+\t{ 35, 4, 39, 29, 0 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t/* DV_I_48_2 */\n+\t{ 41, 1, 49, 1, 1 },\n+\t/* DV_I_49_0 */\n+\t{ 43, 4, 45, 4, 1 },\n+\t{ 45, 4, 47, 4, 1 },\n+\t{ 47, 4, 49, 4, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t/* DV_I_49_2 */\n+\t{ 38, 1, 40, 1, 1 },\n+\t{ 42, 1, 50, 1, 1 },\n+\t/* DV_I_50_0 */\n+\t{ 36, 4, 37, 4, 1 },\n+\t{ 44, 4, 46, 4, 1 },\n+\t{ 46, 4, 48, 4, 1 },\n+\t{ 48, 4, 50, 4, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t{ 40, 4, 44, 29, 0 },\n+\t/* DV_I_50_2 */\n+\t{ 43, 1, 44, 6, 1 },\n+\t/* DV_I_51_0 */\n+\t{ 37, 4, 38, 4, 1 },\n+\t{ 45, 4, 47, 4, 1 },\n+\t{ 47, 4, 49, 4, 1 },\n+\t{ 52, 29, 55, 29, 1 },\n+\t{ 35, 3, 39, 28, 0 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t{ 51, 4, 54, 29, 0 },\n+\t/* DV_I_51_2 */\n+\t{ 44, 1, 51, 6, 1 },\n+\t{ 44, 1, 52, 1, 1 },\n+\t{ 35, 5, 39, 30, 0 },\n+\t{ 37, 1, 37, 6, 0 },\n+\t/* DV_I_52_0 */\n+\t{ 38, 4, 39, 4, 1 },\n+\t{ 46, 4, 48, 4, 1 },\n+\t{ 48, 4, 50, 4, 1 },\n+\t{ 53, 29, 56, 29, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t{ 42, 4, 46, 29, 0 },\n+\t{ 52, 4, 55, 29, 0 },\n+\t/* DV_II_45_0 */\n+\t{ 47, 4, 49, 4, 1 },\n+\t{ 60, 0, 61, 5, 1 },\n+\t{ 63, 1, 64, 6, 1 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t/* DV_II_46_0 */\n+\t{ 48, 4, 50, 4, 1 },\n+\t{ 61, 0, 62, 5, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t{ 42, 4, 46, 29, 0 },\n+\t/* DV_II_46_2 */\n+\t{ 47, 1, 48, 6, 1 },\n+\t/* DV_II_47_0 */\n+\t{ 52, 29, 55, 29, 1 },\n+\t{ 62, 0, 63, 5, 1 },\n+\t{ 35, 3, 39, 28, 0 },\n+\t{ 35, 4, 39, 29, 0 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t{ 51, 4, 54, 29, 0 },\n+\t/* DV_II_48_0 */\n+\t{ 35, 30, 36, 3, 1 },\n+\t{ 35, 30, 40, 28, 1 },\n+\t{ 52, 29, 55, 29, 1 },\n+\t{ 53, 29, 56, 29, 1 },\n+\t{ 63, 0, 64, 5, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t{ 52, 4, 55, 29, 0 },\n+\t/* DV_II_49_0 */\n+\t{ 36, 30, 37, 3, 1 },\n+\t{ 36, 30, 41, 28, 1 },\n+\t{ 53, 29, 56, 29, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t{ 40, 4, 44, 29, 0 },\n+\t{ 51, 4, 54, 29, 0 },\n+\t{ 53, 4, 56, 29, 0 },\n+\t/* DV_II_49_2 */\n+\t{ 36, 0, 41, 30, 1 },\n+\t{ 50, 1, 53, 6, 1 },\n+\t{ 50, 1, 54, 1, 1 },\n+\t/* DV_II_50_0 */\n+\t{ 37, 30, 38, 3, 1 },\n+\t{ 37, 30, 42, 28, 1 },\n+\t{ 55, 29, 58, 29, 1 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t{ 52, 4, 55, 29, 0 },\n+\t{ 54, 4, 57, 29, 0 },\n+\t{ 57, 29, 58, 29, 0 },\n+\t/* DV_II_50_2 */\n+\t{ 37, 0, 42, 30, 1 },\n+\t{ 51, 1, 54, 6, 1 },\n+\t{ 51, 1, 55, 1, 1 },\n+\t/* DV_II_51_0 */\n+\t{ 38, 30, 39, 3, 1 },\n+\t{ 38, 30, 43, 28, 1 },\n+\t{ 55, 29, 58, 29, 1 },\n+\t{ 56, 29, 59, 29, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t{ 42, 4, 46, 29, 0 },\n+\t{ 53, 4, 56, 29, 0 },\n+\t{ 55, 4, 58, 29, 0 },\n+\t/* DV_II_51_2 */\n+\t{ 38, 0, 43, 30, 1 },\n+\t{ 52, 1, 55, 6, 1 },\n+\t{ 52, 1, 56, 1, 1 },\n+\t/* DV_II_52_0 */\n+\t{ 36, 4, 38, 4, 1 },\n+\t{ 39, 30, 40, 3, 1 },\n+\t{ 39, 30, 44, 28, 1 },\n+\t{ 54, 4, 60, 29, 1 },\n+\t{ 56, 29, 59, 29, 1 },\n+\t{ 40, 4, 44, 29, 0 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t{ 54, 4, 57, 29, 0 },\n+\t{ 56, 4, 59, 29, 0 },\n+\t/* DV_II_53_0 */\n+\t{ 55, 4, 57, 4, 1 },\n+\t{ 55, 4, 61, 29, 1 },\n+\t{ 41, 3, 45, 28, 0 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t{ 55, 4, 58, 29, 0 },\n+\t{ 57, 29, 58, 29, 0 },\n+\t/* DV_II_54_0 */\n+\t{ 36, 4, 38, 4, 1 },\n+\t{ 42, 3, 46, 28, 0 },\n+\t{ 42, 4, 46, 29, 0 },\n+\t{ 56, 4, 59, 29, 0 },\n+\t{ 56, 4, 58, 29, 0 },\n+\t{ 58, 4, 62, 29, 0 },\n+\t/* DV_II_55_0 */\n+\t{ 43, 3, 47, 28, 0 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t{ 51, 4, 54, 29, 0 },\n+\t{ 57, 4, 59, 29, 0 },\n+\t{ 59, 4, 63, 29, 0 },\n+\t/* DV_II_56_0 */\n+\t{ 40, 4, 42, 4, 1 },\n+\t{ 44, 3, 48, 28, 0 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t{ 52, 4, 55, 29, 0 },\n+\t{ 60, 4, 64, 29, 0 }\n+};\n+\n+static const struct tail_span scalar_tail_spans[32] = {\n+\t{ 0, 4 },\t/* DV_I_43_0 */\n+\t{ 4, 6 },\t/* DV_I_44_0 */\n+\t{ 10, 4 },\t/* DV_I_45_0 */\n+\t{ 14, 4 },\t/* DV_I_46_0 */\n+\t{ 18, 1 },\t/* DV_I_46_2 */\n+\t{ 19, 4 },\t/* DV_I_47_0 */\n+\t{ 23, 1 },\t/* DV_I_47_2 */\n+\t{ 24, 6 },\t/* DV_I_48_0 */\n+\t{ 30, 1 },\t/* DV_I_48_2 */\n+\t{ 31, 4 },\t/* DV_I_49_0 */\n+\t{ 35, 2 },\t/* DV_I_49_2 */\n+\t{ 37, 6 },\t/* DV_I_50_0 */\n+\t{ 43, 1 },\t/* DV_I_50_2 */\n+\t{ 44, 8 },\t/* DV_I_51_0 */\n+\t{ 52, 4 },\t/* DV_I_51_2 */\n+\t{ 56, 7 },\t/* DV_I_52_0 */\n+\t{ 63, 4 },\t/* DV_II_45_0 */\n+\t{ 67, 4 },\t/* DV_II_46_0 */\n+\t{ 71, 1 },\t/* DV_II_46_2 */\n+\t{ 72, 7 },\t/* DV_II_47_0 */\n+\t{ 79, 8 },\t/* DV_II_48_0 */\n+\t{ 87, 7 },\t/* DV_II_49_0 */\n+\t{ 94, 3 },\t/* DV_II_49_2 */\n+\t{ 97, 8 },\t/* DV_II_50_0 */\n+\t{ 105, 3 },\t/* DV_II_50_2 */\n+\t{ 108, 8 },\t/* DV_II_51_0 */\n+\t{ 116, 3 },\t/* DV_II_51_2 */\n+\t{ 119, 9 },\t/* DV_II_52_0 */\n+\t{ 128, 7 },\t/* DV_II_53_0 */\n+\t{ 135, 6 },\t/* DV_II_54_0 */\n+\t{ 141, 5 },\t/* DV_II_55_0 */\n+\t{ 146, 5 }\t/* DV_II_56_0 */\n+};\n+\n+static uint32_t scalar_prefix(const uint32_t *w)\n+{\n+\tuint32_t mask = 0xFFFFFFFF;\n+\tsize_t i;\n+\n+\tUNROLL_TABLE\n+\tfor (i = 0; i < ARRAY_SIZE(scalar_prefix_conds); i++) {\n+\t\tconst struct ubc_prefix_cond *p = &scalar_prefix_conds[i];\n+\t\tmask &= ~(p->dvs & (0 - cond_fails(w, &p->cond)));\n+\t}\n+\treturn mask;\n+}\n+\n+uint32_t sha1dc_ubc_check_scalar(const uint32_t w[80])\n+{\n+\tuint32_t mask = scalar_prefix(w);\n+\t/* Every check only clears bits, so an empty mask settles it. */\n+\tif (!mask)\n+\t\treturn 0;\n+\treturn run_tail(w, mask, scalar_tail_checks, scalar_tail_spans);\n+}\n+\n+/* neon form */\n+\n+#ifdef SHA1DC_HAVE_NEON\n+\n+static const struct ubc_group4 neon_groups[] = {\n+\t{ 35, 0, 36, 5, 1,\n+\t  { 1u << 1, 1u << 1, 1u << 1, 1u << 0 },\n+\t  { DV_I_46_2_BIT | DV_I_49_2_BIT,\n+\t    DV_I_47_2_BIT | DV_I_50_2_BIT | DV_II_46_2_BIT,\n+\t    DV_I_48_2_BIT | DV_I_51_2_BIT,\n+\t    DV_II_51_2_BIT } },\n+\t{ 36, 0, 37, 5, 1,\n+\t  { 1u << 0, 1u << 0, 1u << 1, 1u << 1 },\n+\t  { DV_II_49_2_BIT,\n+\t    DV_II_50_2_BIT,\n+\t    DV_I_49_2_BIT,\n+\t    DV_I_46_2_BIT | DV_I_50_2_BIT | DV_II_49_2_BIT } },\n+\t{ 36, 0, 38, 0, 1,\n+\t  { 1u << 4, 1u << 4, 1u << 1, 1u << 4 },\n+\t  { DV_II_52_0_BIT | DV_II_54_0_BIT,\n+\t    DV_I_43_0_BIT | DV_II_53_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_49_2_BIT,\n+\t    DV_I_43_0_BIT | DV_I_45_0_BIT | DV_II_55_0_BIT } },\n+\t{ 36, 0, 40, 25, 0,\n+\t  { 1u << 4, 1u << 5, 1u << 5, 1u << 5 },\n+\t  { DV_I_46_0_BIT | DV_I_49_0_BIT | DV_II_45_0_BIT |\n+\t    DV_II_48_0_BIT,\n+\t    DV_II_49_2_BIT,\n+\t    DV_II_50_2_BIT,\n+\t    DV_II_51_2_BIT } },\n+\t{ 38, 0, 40, 0, 1,\n+\t  { 1u << 4, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_I_44_0_BIT | DV_II_54_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_50_2_BIT | DV_II_49_2_BIT,\n+\t    DV_I_51_2_BIT | DV_II_50_2_BIT,\n+\t    DV_II_46_2_BIT | DV_II_51_2_BIT } },\n+\t{ 37, 0, 40, 25, 0,\n+\t  { 1u << 4, 1u << 4, 1u << 4, 1u << 4 },\n+\t  { DV_I_43_0_BIT | DV_I_47_0_BIT | DV_II_46_0_BIT |\n+\t    DV_II_53_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_48_0_BIT | DV_II_47_0_BIT |\n+\t    DV_II_54_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_43_0_BIT | DV_I_45_0_BIT | DV_I_49_0_BIT | DV_II_48_0_BIT |\n+\t    DV_II_55_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_50_0_BIT | DV_II_49_0_BIT |\n+\t    DV_II_56_0_BIT } },\n+\t{ 40, 0, 41, 5, 1,\n+\t  { 1u << 1, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_I_47_2_BIT | DV_I_51_2_BIT | DV_II_50_2_BIT,\n+\t    DV_I_48_2_BIT | DV_II_46_2_BIT | DV_II_51_2_BIT,\n+\t    DV_I_49_2_BIT,\n+\t    DV_I_50_2_BIT } },\n+\t{ 40, 0, 41, 0, 0,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 29 },\n+\t  { DV_I_44_0_BIT | DV_I_47_0_BIT | DV_I_48_0_BIT | DV_II_46_0_BIT |\n+\t    DV_II_47_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_45_0_BIT | DV_I_48_0_BIT | DV_I_49_0_BIT | DV_II_47_0_BIT |\n+\t    DV_II_48_0_BIT,\n+\t    DV_I_46_0_BIT | DV_I_49_0_BIT | DV_I_50_0_BIT | DV_II_48_0_BIT |\n+\t    DV_II_49_0_BIT,\n+\t    DV_I_47_0_BIT | DV_I_50_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT |\n+\t    DV_II_49_0_BIT | DV_II_50_0_BIT } },\n+\t{ 41, 0, 43, 0, 0,\n+\t  { 1u << 6, 1u << 6, 1u << 6, 1u << 6 },\n+\t  { DV_I_47_2_BIT,\n+\t    DV_I_46_2_BIT | DV_I_48_2_BIT,\n+\t    DV_I_47_2_BIT | DV_I_49_2_BIT,\n+\t    DV_I_46_2_BIT | DV_I_48_2_BIT | DV_I_50_2_BIT } },\n+\t{ 41, 0, 44, 25, 0,\n+\t  { 1u << 4, 1u << 4, 1u << 4, 1u << 4 },\n+\t  { DV_I_43_0_BIT | DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_51_0_BIT |\n+\t    DV_II_45_0_BIT | DV_II_50_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_48_0_BIT | DV_I_52_0_BIT |\n+\t    DV_II_46_0_BIT | DV_II_51_0_BIT,\n+\t    DV_I_43_0_BIT | DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_49_0_BIT |\n+\t    DV_II_47_0_BIT | DV_II_52_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_48_0_BIT | DV_I_50_0_BIT |\n+\t    DV_II_48_0_BIT | DV_II_53_0_BIT } },\n+\t{ 44, 0, 45, 5, 1,\n+\t  { 1u << 1, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_I_51_2_BIT | DV_II_49_2_BIT,\n+\t    DV_II_50_2_BIT,\n+\t    DV_II_51_2_BIT,\n+\t    DV_II_46_2_BIT } },\n+\t{ 44, 0, 45, 0, 0,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 29 },\n+\t  { DV_I_48_0_BIT | DV_I_51_0_BIT | DV_I_52_0_BIT | DV_II_45_0_BIT |\n+\t    DV_II_46_0_BIT | DV_II_50_0_BIT | DV_II_51_0_BIT,\n+\t    DV_I_49_0_BIT | DV_I_52_0_BIT | DV_II_46_0_BIT |\n+\t    DV_II_47_0_BIT | DV_II_51_0_BIT | DV_II_52_0_BIT,\n+\t    DV_I_43_0_BIT | DV_I_50_0_BIT | DV_II_47_0_BIT |\n+\t    DV_II_48_0_BIT | DV_II_52_0_BIT | DV_II_53_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_51_0_BIT | DV_II_48_0_BIT |\n+\t    DV_II_49_0_BIT | DV_II_53_0_BIT | DV_II_54_0_BIT } },\n+\t{ 45, 5, 46, 0, 0,\n+\t  { 1u << 1, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_II_49_2_BIT,\n+\t    DV_I_46_2_BIT | DV_II_50_2_BIT,\n+\t    DV_I_47_2_BIT | DV_II_51_2_BIT,\n+\t    DV_I_48_2_BIT } },\n+\t{ 45, 0, 47, 0, 0,\n+\t  { 1u << 6, 1u << 6, 1u << 6, 1u << 6 },\n+\t  { DV_I_47_2_BIT | DV_I_49_2_BIT | DV_I_51_2_BIT,\n+\t    DV_I_48_2_BIT | DV_I_50_2_BIT,\n+\t    DV_I_49_2_BIT | DV_I_51_2_BIT,\n+\t    DV_I_50_2_BIT | DV_II_46_2_BIT } },\n+\t{ 45, 0, 47, 0, 1,\n+\t  { 1u << 29, 1u << 29, 1u << 4, 1u << 4 },\n+\t  { DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_48_0_BIT,\n+\t    DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_49_0_BIT,\n+\t    DV_I_49_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT,\n+\t    DV_I_50_0_BIT | DV_I_52_0_BIT | DV_II_46_0_BIT } },\n+\t{ 45, 0, 48, 25, 0,\n+\t  { 1u << 4, 1u << 4, 1u << 4, 1u << 4 },\n+\t  { DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_49_0_BIT | DV_I_51_0_BIT |\n+\t    DV_II_49_0_BIT | DV_II_54_0_BIT,\n+\t    DV_I_46_0_BIT | DV_I_48_0_BIT | DV_I_50_0_BIT | DV_I_52_0_BIT |\n+\t    DV_II_50_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_47_0_BIT | DV_I_49_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT |\n+\t    DV_II_51_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_48_0_BIT | DV_I_50_0_BIT | DV_I_52_0_BIT | DV_II_46_0_BIT |\n+\t    DV_II_52_0_BIT } },\n+\t{ 48, 0, 49, 0, 0,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 29 },\n+\t  { DV_I_45_0_BIT | DV_I_52_0_BIT | DV_II_49_0_BIT |\n+\t    DV_II_50_0_BIT | DV_II_54_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_46_0_BIT | DV_II_45_0_BIT | DV_II_50_0_BIT |\n+\t    DV_II_51_0_BIT | DV_II_55_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_47_0_BIT | DV_II_46_0_BIT | DV_II_51_0_BIT |\n+\t    DV_II_52_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_48_0_BIT | DV_II_47_0_BIT | DV_II_52_0_BIT |\n+\t    DV_II_53_0_BIT } },\n+\t{ 52, 0, 53, 0, 0,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 29 },\n+\t  { DV_I_49_0_BIT | DV_II_45_0_BIT | DV_II_48_0_BIT |\n+\t    DV_II_53_0_BIT | DV_II_54_0_BIT,\n+\t    DV_I_50_0_BIT | DV_II_46_0_BIT | DV_II_49_0_BIT |\n+\t    DV_II_54_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_51_0_BIT | DV_II_47_0_BIT | DV_II_50_0_BIT |\n+\t    DV_II_55_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_52_0_BIT | DV_II_48_0_BIT | DV_II_51_0_BIT |\n+\t    DV_II_56_0_BIT } },\n+\t{ 52, 0, 55, 0, 1,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 29 },\n+\t  { DV_I_51_0_BIT | DV_II_47_0_BIT | DV_II_48_0_BIT,\n+\t    DV_I_52_0_BIT | DV_II_48_0_BIT | DV_II_49_0_BIT,\n+\t    DV_II_49_0_BIT | DV_II_50_0_BIT,\n+\t    DV_II_50_0_BIT | DV_II_51_0_BIT } },\n+\t{ 60, 0, 61, 5, 1,\n+\t  { 1u << 0, 1u << 2, 1u << 2, 1u << 2 },\n+\t  { DV_I_45_0_BIT | DV_II_45_0_BIT,\n+\t    DV_I_46_2_BIT | DV_II_46_2_BIT,\n+\t    DV_I_47_2_BIT,\n+\t    DV_I_48_2_BIT } }\n+};\n+\n+static const struct ubc_cond neon_tail_checks[] = {\n+\t/* DV_I_43_0 */\n+\t{ 41, 4, 43, 4, 1 },\n+\t{ 58, 0, 59, 5, 1 },\n+\t{ 58, 0, 63, 30, 1 },\n+\t{ 61, 1, 62, 6, 1 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t/* DV_I_44_0 */\n+\t{ 40, 4, 42, 4, 1 },\n+\t{ 59, 0, 60, 5, 1 },\n+\t{ 59, 0, 64, 30, 1 },\n+\t{ 62, 1, 63, 6, 1 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t/* DV_I_45_0 */\n+\t{ 41, 4, 43, 4, 1 },\n+\t{ 63, 1, 64, 6, 1 },\n+\t{ 35, 4, 39, 29, 0 },\n+\t/* DV_I_46_0 */\n+\t{ 40, 4, 42, 4, 1 },\n+\t{ 44, 4, 46, 4, 1 },\n+\t{ 61, 0, 62, 5, 1 },\n+\t/* DV_I_46_2 */\n+\t{ 39, 1, 42, 6, 1 },\n+\t/* DV_I_47_0 */\n+\t{ 41, 4, 43, 4, 1 },\n+\t{ 45, 4, 47, 4, 1 },\n+\t{ 62, 0, 63, 5, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t/* DV_I_48_0 */\n+\t{ 44, 4, 46, 4, 1 },\n+\t{ 46, 4, 48, 4, 1 },\n+\t{ 63, 0, 64, 5, 1 },\n+\t{ 35, 4, 39, 29, 0 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t/* DV_I_49_0 */\n+\t{ 45, 4, 47, 4, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t{ 49, 4, 52, 29, 0 },\n+\t/* DV_I_49_2 */\n+\t{ 42, 1, 50, 1, 1 },\n+\t/* DV_I_50_0 */\n+\t{ 36, 4, 37, 4, 1 },\n+\t{ 44, 4, 46, 4, 1 },\n+\t{ 46, 4, 48, 4, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t{ 40, 4, 44, 29, 0 },\n+\t{ 50, 4, 53, 29, 0 },\n+\t/* DV_I_50_2 */\n+\t{ 48, 6, 51, 1, 0 },\n+\t/* DV_I_51_0 */\n+\t{ 37, 4, 38, 4, 1 },\n+\t{ 45, 4, 47, 4, 1 },\n+\t{ 35, 3, 39, 28, 0 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t{ 49, 4, 52, 29, 0 },\n+\t{ 51, 4, 54, 29, 0 },\n+\t/* DV_I_51_2 */\n+\t{ 44, 1, 51, 6, 1 },\n+\t{ 44, 1, 52, 1, 1 },\n+\t{ 35, 5, 39, 30, 0 },\n+\t{ 37, 1, 37, 6, 0 },\n+\t/* DV_I_52_0 */\n+\t{ 38, 4, 39, 4, 1 },\n+\t{ 46, 4, 48, 4, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t{ 42, 4, 46, 29, 0 },\n+\t{ 50, 4, 53, 29, 0 },\n+\t{ 52, 4, 55, 29, 0 },\n+\t/* DV_II_45_0 */\n+\t{ 63, 1, 64, 6, 1 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t{ 49, 4, 52, 29, 0 },\n+\t/* DV_II_46_0 */\n+\t{ 61, 0, 62, 5, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t{ 42, 4, 46, 29, 0 },\n+\t{ 50, 4, 53, 29, 0 },\n+\t/* DV_II_46_2 */\n+\t{ 48, 6, 51, 1, 0 },\n+\t/* DV_II_47_0 */\n+\t{ 62, 0, 63, 5, 1 },\n+\t{ 35, 3, 39, 28, 0 },\n+\t{ 35, 4, 39, 29, 0 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t{ 49, 4, 52, 29, 0 },\n+\t{ 51, 4, 54, 29, 0 },\n+\t/* DV_II_48_0 */\n+\t{ 35, 30, 36, 3, 1 },\n+\t{ 35, 30, 40, 28, 1 },\n+\t{ 63, 0, 64, 5, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t{ 50, 4, 53, 29, 0 },\n+\t{ 52, 4, 55, 29, 0 },\n+\t/* DV_II_49_0 */\n+\t{ 36, 30, 37, 3, 1 },\n+\t{ 36, 30, 41, 28, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t{ 40, 4, 44, 29, 0 },\n+\t{ 51, 4, 54, 29, 0 },\n+\t{ 53, 4, 56, 29, 0 },\n+\t/* DV_II_49_2 */\n+\t{ 50, 1, 51, 6, 1 },\n+\t{ 50, 1, 53, 6, 1 },\n+\t{ 50, 1, 54, 1, 1 },\n+\t/* DV_II_50_0 */\n+\t{ 37, 30, 38, 3, 1 },\n+\t{ 37, 30, 42, 28, 1 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t{ 52, 4, 55, 29, 0 },\n+\t{ 54, 4, 57, 29, 0 },\n+\t/* DV_II_50_2 */\n+\t{ 51, 1, 52, 6, 1 },\n+\t{ 51, 1, 54, 6, 1 },\n+\t{ 51, 1, 55, 1, 1 },\n+\t/* DV_II_51_0 */\n+\t{ 38, 30, 39, 3, 1 },\n+\t{ 38, 30, 43, 28, 1 },\n+\t{ 56, 29, 59, 29, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t{ 42, 4, 46, 29, 0 },\n+\t{ 53, 4, 56, 29, 0 },\n+\t{ 55, 4, 58, 29, 0 },\n+\t/* DV_II_51_2 */\n+\t{ 52, 1, 53, 6, 1 },\n+\t{ 52, 1, 55, 6, 1 },\n+\t{ 52, 1, 56, 1, 1 },\n+\t/* DV_II_52_0 */\n+\t{ 39, 30, 40, 3, 1 },\n+\t{ 39, 30, 44, 28, 1 },\n+\t{ 54, 4, 56, 4, 1 },\n+\t{ 54, 4, 60, 29, 1 },\n+\t{ 56, 29, 59, 29, 1 },\n+\t{ 40, 4, 44, 29, 0 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t{ 54, 4, 57, 29, 0 },\n+\t{ 56, 4, 59, 29, 0 },\n+\t/* DV_II_53_0 */\n+\t{ 55, 4, 57, 4, 1 },\n+\t{ 55, 4, 61, 29, 1 },\n+\t{ 41, 3, 45, 28, 0 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t{ 49, 4, 52, 29, 0 },\n+\t{ 55, 4, 58, 29, 0 },\n+\t{ 55, 4, 57, 29, 0 },\n+\t/* DV_II_54_0 */\n+\t{ 42, 3, 46, 28, 0 },\n+\t{ 42, 4, 46, 29, 0 },\n+\t{ 50, 4, 53, 29, 0 },\n+\t{ 56, 4, 59, 29, 0 },\n+\t{ 56, 4, 58, 29, 0 },\n+\t{ 58, 4, 62, 29, 0 },\n+\t/* DV_II_55_0 */\n+\t{ 43, 3, 47, 28, 0 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t{ 51, 4, 54, 29, 0 },\n+\t{ 57, 4, 59, 29, 0 },\n+\t{ 59, 4, 63, 29, 0 },\n+\t/* DV_II_56_0 */\n+\t{ 40, 4, 42, 4, 1 },\n+\t{ 44, 3, 48, 28, 0 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t{ 52, 4, 55, 29, 0 },\n+\t{ 60, 4, 64, 29, 0 }\n+};\n+\n+static const struct tail_span neon_tail_spans[32] = {\n+\t{ 0, 5 },\t/* DV_I_43_0 */\n+\t{ 5, 5 },\t/* DV_I_44_0 */\n+\t{ 10, 3 },\t/* DV_I_45_0 */\n+\t{ 13, 3 },\t/* DV_I_46_0 */\n+\t{ 16, 1 },\t/* DV_I_46_2 */\n+\t{ 17, 4 },\t/* DV_I_47_0 */\n+\t{ 21, 0 },\t/* DV_I_47_2 */\n+\t{ 21, 5 },\t/* DV_I_48_0 */\n+\t{ 26, 0 },\t/* DV_I_48_2 */\n+\t{ 26, 3 },\t/* DV_I_49_0 */\n+\t{ 29, 1 },\t/* DV_I_49_2 */\n+\t{ 30, 6 },\t/* DV_I_50_0 */\n+\t{ 36, 1 },\t/* DV_I_50_2 */\n+\t{ 37, 7 },\t/* DV_I_51_0 */\n+\t{ 44, 4 },\t/* DV_I_51_2 */\n+\t{ 48, 6 },\t/* DV_I_52_0 */\n+\t{ 54, 3 },\t/* DV_II_45_0 */\n+\t{ 57, 4 },\t/* DV_II_46_0 */\n+\t{ 61, 1 },\t/* DV_II_46_2 */\n+\t{ 62, 7 },\t/* DV_II_47_0 */\n+\t{ 69, 7 },\t/* DV_II_48_0 */\n+\t{ 76, 6 },\t/* DV_II_49_0 */\n+\t{ 82, 3 },\t/* DV_II_49_2 */\n+\t{ 85, 6 },\t/* DV_II_50_0 */\n+\t{ 91, 3 },\t/* DV_II_50_2 */\n+\t{ 94, 7 },\t/* DV_II_51_0 */\n+\t{ 101, 3 },\t/* DV_II_51_2 */\n+\t{ 104, 9 },\t/* DV_II_52_0 */\n+\t{ 113, 8 },\t/* DV_II_53_0 */\n+\t{ 121, 6 },\t/* DV_II_54_0 */\n+\t{ 127, 5 },\t/* DV_II_55_0 */\n+\t{ 132, 5 }\t/* DV_II_56_0 */\n+};\n+\n+static uint32_t neon_prefix(const uint32_t *w)\n+{\n+\tuint32x4_t acc = vdupq_n_u32(0);\n+\tuint32x2_t folded;\n+\tsize_t i;\n+\n+\tUNROLL_TABLE\n+\tfor (i = 0; i < ARRAY_SIZE(neon_groups); i++) {\n+\t\tconst struct ubc_group4 *g = &neon_groups[i];\n+\t\tuint32x4_t lo = vld1q_u32(w + g->lo);\n+\t\tuint32x4_t hi = vld1q_u32(w + g->hi);\n+\t\tuint32x4_t dvs = vld1q_u32(g->dvs);\n+\t\tuint32x4_t set, fail;\n+\n+\t\tlo = vshlq_u32(lo, vdupq_n_s32(-(int32_t)g->lo_shift));\n+\t\thi = vshlq_u32(hi, vdupq_n_s32(-(int32_t)g->hi_shift));\n+\t\tset = vtstq_u32(veorq_u32(lo, hi), vld1q_u32(g->test));\n+\t\t/*\n+\t\t * The DVs of the lanes where the bit is not g->want. Each lane\n+\t\t * of set is all ones or zero, so a saturating subtraction keeps\n+\t\t * dvs where the bit is clear, and min keeps it where it is set.\n+\t\t */\n+\t\tfail = g->want ? vqsubq_u32(dvs, set) : vminq_u32(set, dvs);\n+\t\tacc = vorrq_u32(acc, fail);\n+\t}\n+\n+\tfolded = vorr_u32(vget_low_u32(acc), vget_high_u32(acc));\n+\treturn ~vget_lane_u32(vorr_u32(folded, vdup_lane_u32(folded, 1)), 0);\n+}\n+\n+uint32_t sha1dc_ubc_check_neon(const uint32_t w[80])\n+{\n+\tuint32_t mask = neon_prefix(w);\n+\t/* Every check only clears bits, so an empty mask settles it. */\n+\tif (!mask)\n+\t\treturn 0;\n+\treturn run_tail(w, mask, neon_tail_checks, neon_tail_spans);\n+}\n+\n+#endif /* SHA1DC_HAVE_NEON */\n+\n+/* sse2 form */\n+\n+#ifdef SHA1DC_HAVE_SSE2\n+\n+static const struct ubc_group4 sse2_groups[] = {\n+\t{ 35, 0, 36, 5, 1,\n+\t  { 1u << 1, 1u << 1, 1u << 1, 1u << 0 },\n+\t  { DV_I_46_2_BIT | DV_I_49_2_BIT,\n+\t    DV_I_47_2_BIT | DV_I_50_2_BIT | DV_II_46_2_BIT,\n+\t    DV_I_48_2_BIT | DV_I_51_2_BIT,\n+\t    DV_II_51_2_BIT } },\n+\t{ 36, 0, 37, 5, 1,\n+\t  { 1u << 0, 1u << 0, 1u << 1, 1u << 1 },\n+\t  { DV_II_49_2_BIT,\n+\t    DV_II_50_2_BIT,\n+\t    DV_I_49_2_BIT,\n+\t    DV_I_46_2_BIT | DV_I_50_2_BIT | DV_II_49_2_BIT } },\n+\t{ 36, 0, 38, 0, 1,\n+\t  { 1u << 4, 1u << 4, 1u << 1, 1u << 4 },\n+\t  { DV_II_52_0_BIT | DV_II_54_0_BIT,\n+\t    DV_I_43_0_BIT | DV_II_53_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_49_2_BIT,\n+\t    DV_I_43_0_BIT | DV_I_45_0_BIT | DV_II_55_0_BIT } },\n+\t{ 37, 0, 40, 25, 0,\n+\t  { 1u << 4, 1u << 4, 1u << 4, 1u << 4 },\n+\t  { DV_I_43_0_BIT | DV_I_47_0_BIT | DV_II_46_0_BIT |\n+\t    DV_II_53_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_48_0_BIT | DV_II_47_0_BIT |\n+\t    DV_II_54_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_43_0_BIT | DV_I_45_0_BIT | DV_I_49_0_BIT | DV_II_48_0_BIT |\n+\t    DV_II_55_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_50_0_BIT | DV_II_49_0_BIT |\n+\t    DV_II_56_0_BIT } },\n+\t{ 36, 0, 40, 25, 0,\n+\t  { 1u << 4, 1u << 5, 1u << 5, 1u << 5 },\n+\t  { DV_I_46_0_BIT | DV_I_49_0_BIT | DV_II_45_0_BIT |\n+\t    DV_II_48_0_BIT,\n+\t    DV_II_49_2_BIT,\n+\t    DV_II_50_2_BIT,\n+\t    DV_II_51_2_BIT } },\n+\t{ 38, 0, 40, 0, 1,\n+\t  { 1u << 4, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_I_44_0_BIT | DV_II_54_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_50_2_BIT | DV_II_49_2_BIT,\n+\t    DV_I_51_2_BIT | DV_II_50_2_BIT,\n+\t    DV_II_46_2_BIT | DV_II_51_2_BIT } },\n+\t{ 40, 0, 41, 5, 1,\n+\t  { 1u << 1, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_I_47_2_BIT | DV_I_51_2_BIT | DV_II_50_2_BIT,\n+\t    DV_I_48_2_BIT | DV_II_46_2_BIT | DV_II_51_2_BIT,\n+\t    DV_I_49_2_BIT,\n+\t    DV_I_50_2_BIT } },\n+\t{ 40, 0, 41, 0, 0,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 29 },\n+\t  { DV_I_44_0_BIT | DV_I_47_0_BIT | DV_I_48_0_BIT | DV_II_46_0_BIT |\n+\t    DV_II_47_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_45_0_BIT | DV_I_48_0_BIT | DV_I_49_0_BIT | DV_II_47_0_BIT |\n+\t    DV_II_48_0_BIT,\n+\t    DV_I_46_0_BIT | DV_I_49_0_BIT | DV_I_50_0_BIT | DV_II_48_0_BIT |\n+\t    DV_II_49_0_BIT,\n+\t    DV_I_47_0_BIT | DV_I_50_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT |\n+\t    DV_II_49_0_BIT | DV_II_50_0_BIT } },\n+\t{ 41, 0, 44, 25, 0,\n+\t  { 1u << 4, 1u << 4, 1u << 4, 1u << 4 },\n+\t  { DV_I_43_0_BIT | DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_51_0_BIT |\n+\t    DV_II_45_0_BIT | DV_II_50_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_48_0_BIT | DV_I_52_0_BIT |\n+\t    DV_II_46_0_BIT | DV_II_51_0_BIT,\n+\t    DV_I_43_0_BIT | DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_49_0_BIT |\n+\t    DV_II_47_0_BIT | DV_II_52_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_48_0_BIT | DV_I_50_0_BIT |\n+\t    DV_II_48_0_BIT | DV_II_53_0_BIT } },\n+\t{ 42, 0, 44, 0, 0,\n+\t  { 1u << 6, 1u << 6, 1u << 6, 1u << 6 },\n+\t  { DV_I_46_2_BIT | DV_I_48_2_BIT,\n+\t    DV_I_47_2_BIT | DV_I_49_2_BIT,\n+\t    DV_I_46_2_BIT | DV_I_48_2_BIT | DV_I_50_2_BIT,\n+\t    DV_I_47_2_BIT | DV_I_49_2_BIT | DV_I_51_2_BIT } },\n+\t{ 40, 0, 44, 0, 0,\n+\t  { 1u << 6, 1u << 6, 1u << 29, 1u << 29 },\n+\t  { DV_I_46_2_BIT,\n+\t    DV_I_47_2_BIT,\n+\t    DV_I_43_0_BIT | DV_I_45_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_46_0_BIT } },\n+\t{ 44, 0, 45, 5, 1,\n+\t  { 1u << 1, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_I_51_2_BIT | DV_II_49_2_BIT,\n+\t    DV_II_50_2_BIT,\n+\t    DV_II_51_2_BIT,\n+\t    DV_II_46_2_BIT } },\n+\t{ 44, 0, 45, 0, 0,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 29 },\n+\t  { DV_I_48_0_BIT | DV_I_51_0_BIT | DV_I_52_0_BIT | DV_II_45_0_BIT |\n+\t    DV_II_46_0_BIT | DV_II_50_0_BIT | DV_II_51_0_BIT,\n+\t    DV_I_49_0_BIT | DV_I_52_0_BIT | DV_II_46_0_BIT |\n+\t    DV_II_47_0_BIT | DV_II_51_0_BIT | DV_II_52_0_BIT,\n+\t    DV_I_43_0_BIT | DV_I_50_0_BIT | DV_II_47_0_BIT |\n+\t    DV_II_48_0_BIT | DV_II_52_0_BIT | DV_II_53_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_51_0_BIT | DV_II_48_0_BIT |\n+\t    DV_II_49_0_BIT | DV_II_53_0_BIT | DV_II_54_0_BIT } },\n+\t{ 45, 5, 46, 0, 0,\n+\t  { 1u << 1, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_II_49_2_BIT,\n+\t    DV_I_46_2_BIT | DV_II_50_2_BIT,\n+\t    DV_I_47_2_BIT | DV_II_51_2_BIT,\n+\t    DV_I_48_2_BIT } },\n+\t{ 45, 0, 47, 0, 1,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 4 },\n+\t  { DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_48_0_BIT,\n+\t    DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_49_0_BIT,\n+\t    DV_I_46_0_BIT | DV_I_48_0_BIT | DV_I_50_0_BIT,\n+\t    DV_I_50_0_BIT | DV_I_52_0_BIT | DV_II_46_0_BIT } },\n+\t{ 46, 0, 48, 0, 0,\n+\t  { 1u << 6, 1u << 6, 1u << 6, 1u << 6 },\n+\t  { DV_I_48_2_BIT | DV_I_50_2_BIT,\n+\t    DV_I_49_2_BIT | DV_I_51_2_BIT,\n+\t    DV_I_50_2_BIT | DV_II_46_2_BIT,\n+\t    DV_I_51_2_BIT } },\n+\t{ 45, 0, 48, 25, 0,\n+\t  { 1u << 4, 1u << 4, 1u << 4, 1u << 4 },\n+\t  { DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_49_0_BIT | DV_I_51_0_BIT |\n+\t    DV_II_49_0_BIT | DV_II_54_0_BIT,\n+\t    DV_I_46_0_BIT | DV_I_48_0_BIT | DV_I_50_0_BIT | DV_I_52_0_BIT |\n+\t    DV_II_50_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_47_0_BIT | DV_I_49_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT |\n+\t    DV_II_51_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_48_0_BIT | DV_I_50_0_BIT | DV_I_52_0_BIT | DV_II_46_0_BIT |\n+\t    DV_II_52_0_BIT } },\n+\t{ 48, 0, 49, 0, 0,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 29 },\n+\t  { DV_I_45_0_BIT | DV_I_52_0_BIT | DV_II_49_0_BIT |\n+\t    DV_II_50_0_BIT | DV_II_54_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_46_0_BIT | DV_II_45_0_BIT | DV_II_50_0_BIT |\n+\t    DV_II_51_0_BIT | DV_II_55_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_47_0_BIT | DV_II_46_0_BIT | DV_II_51_0_BIT |\n+\t    DV_II_52_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_48_0_BIT | DV_II_47_0_BIT | DV_II_52_0_BIT |\n+\t    DV_II_53_0_BIT } },\n+\t{ 49, 5, 50, 0, 0,\n+\t  { 1u << 1, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_I_49_2_BIT,\n+\t    DV_I_50_2_BIT | DV_II_46_2_BIT,\n+\t    DV_I_51_2_BIT,\n+\t    0 } },\n+\t{ 49, 0, 52, 25, 0,\n+\t  { 1u << 4, 1u << 4, 1u << 4, 1u << 4 },\n+\t  { DV_I_49_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT |\n+\t    DV_II_47_0_BIT | DV_II_53_0_BIT,\n+\t    DV_I_50_0_BIT | DV_I_52_0_BIT | DV_II_46_0_BIT |\n+\t    DV_II_48_0_BIT | DV_II_54_0_BIT,\n+\t    DV_I_51_0_BIT | DV_II_47_0_BIT | DV_II_49_0_BIT |\n+\t    DV_II_55_0_BIT,\n+\t    DV_I_52_0_BIT | DV_II_48_0_BIT | DV_II_50_0_BIT |\n+\t    DV_II_56_0_BIT } },\n+\t{ 49, 0, 53, 0, 1,\n+\t  { 1u << 29, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_II_45_0_BIT,\n+\t    DV_II_49_2_BIT,\n+\t    DV_II_50_2_BIT,\n+\t    DV_II_51_2_BIT } },\n+\t{ 52, 0, 53, 0, 0,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 29 },\n+\t  { DV_I_49_0_BIT | DV_II_45_0_BIT | DV_II_48_0_BIT |\n+\t    DV_II_53_0_BIT | DV_II_54_0_BIT,\n+\t    DV_I_50_0_BIT | DV_II_46_0_BIT | DV_II_49_0_BIT |\n+\t    DV_II_54_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_51_0_BIT | DV_II_47_0_BIT | DV_II_50_0_BIT |\n+\t    DV_II_55_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_52_0_BIT | DV_II_48_0_BIT | DV_II_51_0_BIT |\n+\t    DV_II_56_0_BIT } },\n+\t{ 53, 5, 54, 0, 0,\n+\t  { 1u << 1, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_II_49_2_BIT,\n+\t    DV_II_50_2_BIT,\n+\t    DV_II_51_2_BIT,\n+\t    0 } },\n+\t{ 52, 0, 55, 0, 1,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 29 },\n+\t  { DV_I_51_0_BIT | DV_II_47_0_BIT | DV_II_48_0_BIT,\n+\t    DV_I_52_0_BIT | DV_II_48_0_BIT | DV_II_49_0_BIT,\n+\t    DV_II_49_0_BIT | DV_II_50_0_BIT,\n+\t    DV_II_50_0_BIT | DV_II_51_0_BIT } },\n+\t{ 53, 0, 56, 25, 0,\n+\t  { 1u << 4, 1u << 4, 1u << 4, 1u << 4 },\n+\t  { DV_II_49_0_BIT | DV_II_51_0_BIT,\n+\t    DV_II_50_0_BIT | DV_II_52_0_BIT,\n+\t    DV_II_51_0_BIT | DV_II_53_0_BIT,\n+\t    DV_II_52_0_BIT | DV_II_54_0_BIT } },\n+\t{ 60, 0, 61, 5, 1,\n+\t  { 1u << 0, 1u << 2, 1u << 2, 1u << 2 },\n+\t  { DV_I_45_0_BIT | DV_II_45_0_BIT,\n+\t    DV_I_46_2_BIT | DV_II_46_2_BIT,\n+\t    DV_I_47_2_BIT,\n+\t    DV_I_48_2_BIT } }\n+};\n+\n+static const struct ubc_cond sse2_tail_checks[] = {\n+\t/* DV_I_43_0 */\n+\t{ 41, 4, 43, 4, 1 },\n+\t{ 58, 0, 59, 5, 1 },\n+\t{ 58, 0, 63, 30, 1 },\n+\t{ 61, 1, 62, 6, 1 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t/* DV_I_44_0 */\n+\t{ 59, 0, 60, 5, 1 },\n+\t{ 59, 0, 64, 30, 1 },\n+\t{ 62, 1, 63, 6, 1 },\n+\t{ 38, 4, 42, 4, 0 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t/* DV_I_45_0 */\n+\t{ 41, 4, 43, 4, 1 },\n+\t{ 63, 1, 64, 6, 1 },\n+\t{ 35, 4, 39, 29, 0 },\n+\t/* DV_I_46_0 */\n+\t{ 61, 0, 62, 5, 1 },\n+\t/* DV_I_47_0 */\n+\t{ 41, 4, 43, 4, 1 },\n+\t{ 45, 4, 47, 4, 1 },\n+\t{ 62, 0, 63, 5, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t/* DV_I_48_0 */\n+\t{ 46, 4, 48, 4, 1 },\n+\t{ 63, 0, 64, 5, 1 },\n+\t{ 35, 4, 39, 29, 0 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t/* DV_I_49_0 */\n+\t{ 45, 4, 47, 4, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t{ 45, 4, 49, 4, 0 },\n+\t/* DV_I_50_0 */\n+\t{ 36, 4, 37, 4, 1 },\n+\t{ 46, 4, 48, 4, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t{ 40, 4, 44, 29, 0 },\n+\t/* DV_I_51_0 */\n+\t{ 37, 4, 38, 4, 1 },\n+\t{ 45, 4, 47, 4, 1 },\n+\t{ 35, 3, 39, 28, 0 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t{ 45, 4, 49, 4, 0 },\n+\t/* DV_I_51_2 */\n+\t{ 35, 5, 39, 30, 0 },\n+\t{ 37, 1, 37, 6, 0 },\n+\t/* DV_I_52_0 */\n+\t{ 38, 4, 39, 4, 1 },\n+\t{ 46, 4, 48, 4, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t{ 42, 4, 46, 29, 0 },\n+\t/* DV_II_45_0 */\n+\t{ 63, 1, 64, 6, 1 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t/* DV_II_46_0 */\n+\t{ 61, 0, 62, 5, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t{ 42, 4, 46, 29, 0 },\n+\t/* DV_II_47_0 */\n+\t{ 62, 0, 63, 5, 1 },\n+\t{ 35, 3, 39, 28, 0 },\n+\t{ 35, 4, 39, 29, 0 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t/* DV_II_48_0 */\n+\t{ 35, 30, 36, 3, 1 },\n+\t{ 35, 30, 40, 28, 1 },\n+\t{ 63, 0, 64, 5, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t/* DV_II_49_0 */\n+\t{ 36, 30, 37, 3, 1 },\n+\t{ 36, 30, 41, 28, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t{ 40, 4, 44, 29, 0 },\n+\t/* DV_II_49_2 */\n+\t{ 50, 1, 51, 6, 1 },\n+\t/* DV_II_50_0 */\n+\t{ 37, 30, 38, 3, 1 },\n+\t{ 37, 30, 42, 28, 1 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t/* DV_II_50_2 */\n+\t{ 51, 1, 52, 6, 1 },\n+\t/* DV_II_51_0 */\n+\t{ 38, 30, 39, 3, 1 },\n+\t{ 38, 30, 43, 28, 1 },\n+\t{ 56, 29, 59, 29, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t{ 42, 4, 46, 29, 0 },\n+\t/* DV_II_51_2 */\n+\t{ 52, 1, 53, 6, 1 },\n+\t/* DV_II_52_0 */\n+\t{ 39, 30, 40, 3, 1 },\n+\t{ 39, 30, 44, 28, 1 },\n+\t{ 54, 4, 56, 4, 1 },\n+\t{ 54, 4, 60, 29, 1 },\n+\t{ 56, 29, 59, 29, 1 },\n+\t{ 40, 4, 44, 29, 0 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t/* DV_II_53_0 */\n+\t{ 55, 4, 57, 4, 1 },\n+\t{ 55, 4, 61, 29, 1 },\n+\t{ 41, 3, 45, 28, 0 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t{ 55, 4, 57, 29, 0 },\n+\t/* DV_II_54_0 */\n+\t{ 42, 3, 46, 28, 0 },\n+\t{ 42, 4, 46, 29, 0 },\n+\t{ 56, 4, 58, 29, 0 },\n+\t{ 58, 4, 62, 29, 0 },\n+\t/* DV_II_55_0 */\n+\t{ 43, 3, 47, 28, 0 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t{ 57, 4, 59, 29, 0 },\n+\t{ 59, 4, 63, 29, 0 },\n+\t/* DV_II_56_0 */\n+\t{ 38, 4, 42, 4, 0 },\n+\t{ 44, 3, 48, 28, 0 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t{ 60, 4, 64, 29, 0 }\n+};\n+\n+static const struct tail_span sse2_tail_spans[32] = {\n+\t{ 0, 5 },\t/* DV_I_43_0 */\n+\t{ 5, 5 },\t/* DV_I_44_0 */\n+\t{ 10, 3 },\t/* DV_I_45_0 */\n+\t{ 13, 1 },\t/* DV_I_46_0 */\n+\t{ 14, 0 },\t/* DV_I_46_2 */\n+\t{ 14, 4 },\t/* DV_I_47_0 */\n+\t{ 18, 0 },\t/* DV_I_47_2 */\n+\t{ 18, 4 },\t/* DV_I_48_0 */\n+\t{ 22, 0 },\t/* DV_I_48_2 */\n+\t{ 22, 3 },\t/* DV_I_49_0 */\n+\t{ 25, 0 },\t/* DV_I_49_2 */\n+\t{ 25, 4 },\t/* DV_I_50_0 */\n+\t{ 29, 0 },\t/* DV_I_50_2 */\n+\t{ 29, 6 },\t/* DV_I_51_0 */\n+\t{ 35, 2 },\t/* DV_I_51_2 */\n+\t{ 37, 4 },\t/* DV_I_52_0 */\n+\t{ 41, 2 },\t/* DV_II_45_0 */\n+\t{ 43, 3 },\t/* DV_II_46_0 */\n+\t{ 46, 0 },\t/* DV_II_46_2 */\n+\t{ 46, 5 },\t/* DV_II_47_0 */\n+\t{ 51, 5 },\t/* DV_II_48_0 */\n+\t{ 56, 4 },\t/* DV_II_49_0 */\n+\t{ 60, 1 },\t/* DV_II_49_2 */\n+\t{ 61, 4 },\t/* DV_II_50_0 */\n+\t{ 65, 1 },\t/* DV_II_50_2 */\n+\t{ 66, 5 },\t/* DV_II_51_0 */\n+\t{ 71, 1 },\t/* DV_II_51_2 */\n+\t{ 72, 7 },\t/* DV_II_52_0 */\n+\t{ 79, 6 },\t/* DV_II_53_0 */\n+\t{ 85, 4 },\t/* DV_II_54_0 */\n+\t{ 89, 4 },\t/* DV_II_55_0 */\n+\t{ 93, 4 }\t/* DV_II_56_0 */\n+};\n+\n+SHA1DC_TARGET_SSE2\n+static uint32_t sse2_prefix(const uint32_t *w)\n+{\n+\tconst __m128i zero = _mm_setzero_si128();\n+\t__m128i acc = zero;\n+\tsize_t i;\n+\n+\tUNROLL_TABLE\n+\tfor (i = 0; i < ARRAY_SIZE(sse2_groups); i++) {\n+\t\tconst struct ubc_group4 *g = &sse2_groups[i];\n+\t\t__m128i lo = _mm_loadu_si128((const __m128i *)(w + g->lo));\n+\t\t__m128i hi = _mm_loadu_si128((const __m128i *)(w + g->hi));\n+\t\t__m128i test = _mm_loadu_si128((const __m128i *)g->test);\n+\t\t__m128i dvs = _mm_loadu_si128((const __m128i *)g->dvs);\n+\t\t__m128i clear, fail;\n+\n+\t\tlo = _mm_srl_epi32(lo, _mm_cvtsi32_si128(g->lo_shift));\n+\t\thi = _mm_srl_epi32(hi, _mm_cvtsi32_si128(g->hi_shift));\n+\t\tclear = _mm_and_si128(_mm_xor_si128(lo, hi), test);\n+\t\tclear = _mm_cmpeq_epi32(clear, zero);\n+\t\t/* The DVs of the lanes where the bit is not g->want. */\n+\t\tfail = g->want ? _mm_and_si128(clear, dvs) :\n+\t\t\t\t _mm_andnot_si128(clear, dvs);\n+\t\tacc = _mm_or_si128(acc, fail);\n+\t}\n+\n+\tacc = _mm_or_si128(acc, _mm_shuffle_epi32(acc, 0x4E));\n+\tacc = _mm_or_si128(acc, _mm_shuffle_epi32(acc, 0xB1));\n+\treturn ~(uint32_t)_mm_cvtsi128_si32(acc);\n+}\n+\n+SHA1DC_TARGET_SSE2\n+uint32_t sha1dc_ubc_check_sse2(const uint32_t w[80])\n+{\n+\tuint32_t mask = sse2_prefix(w);\n+\t/* Every check only clears bits, so an empty mask settles it. */\n+\tif (!mask)\n+\t\treturn 0;\n+\treturn run_tail(w, mask, sse2_tail_checks, sse2_tail_spans);\n+}\n+\n+#endif /* SHA1DC_HAVE_SSE2 */\n+\n+/* avx2 form */\n+\n+#ifdef SHA1DC_HAVE_AVX2\n+\n+static const struct ubc_group8 avx2_groups[] = {\n+\t{ 35, 0, 36, 5, 1,\n+\t  { 1u << 1, 1u << 1, 1u << 1, 1u << 0,\n+\t    1u << 1, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_I_46_2_BIT | DV_I_49_2_BIT,\n+\t    DV_I_47_2_BIT | DV_I_50_2_BIT | DV_II_46_2_BIT,\n+\t    DV_I_48_2_BIT | DV_I_51_2_BIT,\n+\t    DV_II_51_2_BIT,\n+\t    DV_I_46_2_BIT | DV_I_50_2_BIT | DV_II_49_2_BIT,\n+\t    DV_I_47_2_BIT | DV_I_51_2_BIT | DV_II_50_2_BIT,\n+\t    DV_I_48_2_BIT | DV_II_46_2_BIT | DV_II_51_2_BIT,\n+\t    DV_I_49_2_BIT } },\n+\t{ 36, 0, 38, 0, 1,\n+\t  { 1u << 4, 1u << 4, 1u << 4, 1u << 4,\n+\t    1u << 4, 1u << 4, 1u << 4, 1u << 4 },\n+\t  { DV_II_52_0_BIT | DV_II_54_0_BIT,\n+\t    DV_I_43_0_BIT | DV_II_53_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_44_0_BIT | DV_II_54_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_43_0_BIT | DV_I_45_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_46_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_43_0_BIT | DV_I_45_0_BIT | DV_I_47_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_48_0_BIT,\n+\t    DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_49_0_BIT } },\n+\t{ 37, 0, 38, 5, 1,\n+\t  { 1u << 0, 1u << 1, 0, 0,\n+\t    0, 0, 1u << 1, 1u << 1 },\n+\t  { DV_II_50_2_BIT,\n+\t    DV_I_49_2_BIT,\n+\t    0,\n+\t    0,\n+\t    0,\n+\t    0,\n+\t    DV_I_50_2_BIT,\n+\t    DV_I_51_2_BIT | DV_II_49_2_BIT } },\n+\t{ 35, 0, 39, 25, 0,\n+\t  { 1u << 5, 1u << 4, 1u << 5, 1u << 5,\n+\t    1u << 5, 1u << 3, 1u << 3, 1u << 4 },\n+\t  { DV_I_51_2_BIT,\n+\t    DV_I_46_0_BIT | DV_I_49_0_BIT | DV_II_45_0_BIT |\n+\t    DV_II_48_0_BIT,\n+\t    DV_II_49_2_BIT,\n+\t    DV_II_50_2_BIT,\n+\t    DV_II_51_2_BIT,\n+\t    DV_II_52_0_BIT,\n+\t    DV_II_53_0_BIT,\n+\t    DV_I_52_0_BIT | DV_II_46_0_BIT | DV_II_51_0_BIT |\n+\t    DV_II_54_0_BIT } },\n+\t{ 37, 0, 40, 25, 0,\n+\t  { 1u << 4, 1u << 4, 1u << 4, 1u << 4,\n+\t    1u << 4, 1u << 4, 1u << 4, 1u << 4 },\n+\t  { DV_I_43_0_BIT | DV_I_47_0_BIT | DV_II_46_0_BIT |\n+\t    DV_II_53_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_48_0_BIT | DV_II_47_0_BIT |\n+\t    DV_II_54_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_43_0_BIT | DV_I_45_0_BIT | DV_I_49_0_BIT | DV_II_48_0_BIT |\n+\t    DV_II_55_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_50_0_BIT | DV_II_49_0_BIT |\n+\t    DV_II_56_0_BIT,\n+\t    DV_I_43_0_BIT | DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_51_0_BIT |\n+\t    DV_II_45_0_BIT | DV_II_50_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_48_0_BIT | DV_I_52_0_BIT |\n+\t    DV_II_46_0_BIT | DV_II_51_0_BIT,\n+\t    DV_I_43_0_BIT | DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_49_0_BIT |\n+\t    DV_II_47_0_BIT | DV_II_52_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_46_0_BIT | DV_I_48_0_BIT | DV_I_50_0_BIT |\n+\t    DV_II_48_0_BIT | DV_II_53_0_BIT } },\n+\t{ 39, 5, 40, 0, 0,\n+\t  { 1u << 1, 1u << 1, 1u << 1, 1u << 1,\n+\t    1u << 1, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_I_49_2_BIT,\n+\t    DV_I_50_2_BIT | DV_II_49_2_BIT,\n+\t    DV_I_51_2_BIT | DV_II_50_2_BIT,\n+\t    DV_II_46_2_BIT | DV_II_51_2_BIT,\n+\t    0,\n+\t    0,\n+\t    DV_II_49_2_BIT,\n+\t    DV_I_46_2_BIT | DV_II_50_2_BIT } },\n+\t{ 40, 0, 41, 0, 0,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 29,\n+\t    1u << 29, 1u << 29, 1u << 29, 1u << 29 },\n+\t  { DV_I_44_0_BIT | DV_I_47_0_BIT | DV_I_48_0_BIT | DV_II_46_0_BIT |\n+\t    DV_II_47_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_45_0_BIT | DV_I_48_0_BIT | DV_I_49_0_BIT | DV_II_47_0_BIT |\n+\t    DV_II_48_0_BIT,\n+\t    DV_I_46_0_BIT | DV_I_49_0_BIT | DV_I_50_0_BIT | DV_II_48_0_BIT |\n+\t    DV_II_49_0_BIT,\n+\t    DV_I_47_0_BIT | DV_I_50_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT |\n+\t    DV_II_49_0_BIT | DV_II_50_0_BIT,\n+\t    DV_I_48_0_BIT | DV_I_51_0_BIT | DV_I_52_0_BIT | DV_II_45_0_BIT |\n+\t    DV_II_46_0_BIT | DV_II_50_0_BIT | DV_II_51_0_BIT,\n+\t    DV_I_49_0_BIT | DV_I_52_0_BIT | DV_II_46_0_BIT |\n+\t    DV_II_47_0_BIT | DV_II_51_0_BIT | DV_II_52_0_BIT,\n+\t    DV_I_43_0_BIT | DV_I_50_0_BIT | DV_II_47_0_BIT |\n+\t    DV_II_48_0_BIT | DV_II_52_0_BIT | DV_II_53_0_BIT,\n+\t    DV_I_44_0_BIT | DV_I_51_0_BIT | DV_II_48_0_BIT |\n+\t    DV_II_49_0_BIT | DV_II_53_0_BIT | DV_II_54_0_BIT } },\n+\t{ 40, 0, 42, 0, 0,\n+\t  { 1u << 6, 1u << 6, 1u << 6, 1u << 6,\n+\t    1u << 6, 1u << 6, 1u << 6, 1u << 6 },\n+\t  { DV_I_46_2_BIT,\n+\t    DV_I_47_2_BIT,\n+\t    DV_I_46_2_BIT | DV_I_48_2_BIT,\n+\t    DV_I_47_2_BIT | DV_I_49_2_BIT,\n+\t    DV_I_46_2_BIT | DV_I_48_2_BIT | DV_I_50_2_BIT,\n+\t    DV_I_47_2_BIT | DV_I_49_2_BIT | DV_I_51_2_BIT,\n+\t    DV_I_48_2_BIT | DV_I_50_2_BIT,\n+\t    DV_I_49_2_BIT | DV_I_51_2_BIT } },\n+\t{ 45, 0, 46, 5, 1,\n+\t  { 1u << 1, 1u << 1, 1u << 1, 1u << 1,\n+\t    1u << 1, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_II_50_2_BIT,\n+\t    DV_II_51_2_BIT,\n+\t    DV_II_46_2_BIT,\n+\t    0,\n+\t    0,\n+\t    DV_II_49_2_BIT,\n+\t    DV_II_50_2_BIT,\n+\t    DV_II_51_2_BIT } },\n+\t{ 45, 0, 48, 25, 0,\n+\t  { 1u << 4, 1u << 4, 1u << 4, 1u << 4,\n+\t    1u << 4, 1u << 4, 1u << 4, 1u << 4 },\n+\t  { DV_I_45_0_BIT | DV_I_47_0_BIT | DV_I_49_0_BIT | DV_I_51_0_BIT |\n+\t    DV_II_49_0_BIT | DV_II_54_0_BIT,\n+\t    DV_I_46_0_BIT | DV_I_48_0_BIT | DV_I_50_0_BIT | DV_I_52_0_BIT |\n+\t    DV_II_50_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_47_0_BIT | DV_I_49_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT |\n+\t    DV_II_51_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_48_0_BIT | DV_I_50_0_BIT | DV_I_52_0_BIT | DV_II_46_0_BIT |\n+\t    DV_II_52_0_BIT,\n+\t    DV_I_49_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT |\n+\t    DV_II_47_0_BIT | DV_II_53_0_BIT,\n+\t    DV_I_50_0_BIT | DV_I_52_0_BIT | DV_II_46_0_BIT |\n+\t    DV_II_48_0_BIT | DV_II_54_0_BIT,\n+\t    DV_I_51_0_BIT | DV_II_47_0_BIT | DV_II_49_0_BIT |\n+\t    DV_II_55_0_BIT,\n+\t    DV_I_52_0_BIT | DV_II_48_0_BIT | DV_II_50_0_BIT |\n+\t    DV_II_56_0_BIT } },\n+\t{ 47, 5, 48, 0, 0,\n+\t  { 1u << 1, 1u << 1, 1u << 1, 1u << 1,\n+\t    1u << 1, 1u << 1, 1u << 1, 1u << 1 },\n+\t  { DV_I_47_2_BIT | DV_II_51_2_BIT,\n+\t    DV_I_48_2_BIT,\n+\t    DV_I_49_2_BIT,\n+\t    DV_I_50_2_BIT | DV_II_46_2_BIT,\n+\t    DV_I_51_2_BIT,\n+\t    0,\n+\t    DV_II_49_2_BIT,\n+\t    DV_II_50_2_BIT } },\n+\t{ 47, 0, 49, 0, 1,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 29,\n+\t    1u << 4, 1u << 4, 1u << 4, 1u << 4 },\n+\t  { DV_I_46_0_BIT | DV_I_48_0_BIT | DV_I_50_0_BIT,\n+\t    DV_I_47_0_BIT | DV_I_49_0_BIT | DV_I_51_0_BIT,\n+\t    DV_I_48_0_BIT | DV_I_50_0_BIT | DV_I_52_0_BIT,\n+\t    DV_I_49_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT,\n+\t    DV_II_49_0_BIT,\n+\t    DV_II_50_0_BIT,\n+\t    DV_II_51_0_BIT,\n+\t    DV_II_52_0_BIT } },\n+\t{ 48, 0, 49, 0, 0,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 29,\n+\t    1u << 29, 1u << 29, 1u << 29, 1u << 29 },\n+\t  { DV_I_45_0_BIT | DV_I_52_0_BIT | DV_II_49_0_BIT |\n+\t    DV_II_50_0_BIT | DV_II_54_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_46_0_BIT | DV_II_45_0_BIT | DV_II_50_0_BIT |\n+\t    DV_II_51_0_BIT | DV_II_55_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_47_0_BIT | DV_II_46_0_BIT | DV_II_51_0_BIT |\n+\t    DV_II_52_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_48_0_BIT | DV_II_47_0_BIT | DV_II_52_0_BIT |\n+\t    DV_II_53_0_BIT,\n+\t    DV_I_49_0_BIT | DV_II_45_0_BIT | DV_II_48_0_BIT |\n+\t    DV_II_53_0_BIT | DV_II_54_0_BIT,\n+\t    DV_I_50_0_BIT | DV_II_46_0_BIT | DV_II_49_0_BIT |\n+\t    DV_II_54_0_BIT | DV_II_55_0_BIT,\n+\t    DV_I_51_0_BIT | DV_II_47_0_BIT | DV_II_50_0_BIT |\n+\t    DV_II_55_0_BIT | DV_II_56_0_BIT,\n+\t    DV_I_52_0_BIT | DV_II_48_0_BIT | DV_II_51_0_BIT |\n+\t    DV_II_56_0_BIT } },\n+\t{ 48, 0, 50, 0, 0,\n+\t  { 1u << 6, 1u << 6, 1u << 6, 1u << 6,\n+\t    1u << 6, 1u << 6, 1u << 6, 1u << 6 },\n+\t  { DV_I_50_2_BIT | DV_II_46_2_BIT,\n+\t    DV_I_51_2_BIT,\n+\t    0,\n+\t    DV_II_49_2_BIT,\n+\t    DV_II_50_2_BIT,\n+\t    DV_II_51_2_BIT,\n+\t    0,\n+\t    0 } },\n+\t{ 51, 0, 54, 0, 1,\n+\t  { 1u << 29, 1u << 29, 1u << 29, 1u << 29,\n+\t    1u << 29, 1u << 29, 1u << 29, 1u << 29 },\n+\t  { DV_I_50_0_BIT | DV_II_46_0_BIT | DV_II_47_0_BIT,\n+\t    DV_I_51_0_BIT | DV_II_47_0_BIT | DV_II_48_0_BIT,\n+\t    DV_I_52_0_BIT | DV_II_48_0_BIT | DV_II_49_0_BIT,\n+\t    DV_II_49_0_BIT | DV_II_50_0_BIT,\n+\t    DV_II_50_0_BIT | DV_II_51_0_BIT,\n+\t    DV_II_51_0_BIT | DV_II_52_0_BIT,\n+\t    DV_II_52_0_BIT,\n+\t    DV_II_53_0_BIT } },\n+\t{ 58, 0, 59, 5, 1,\n+\t  { 1u << 0, 1u << 0, 1u << 0, 1u << 2,\n+\t    1u << 2, 1u << 2, 0, 0 },\n+\t  { DV_I_43_0_BIT,\n+\t    DV_I_44_0_BIT,\n+\t    DV_I_45_0_BIT | DV_II_45_0_BIT,\n+\t    DV_I_46_2_BIT | DV_II_46_2_BIT,\n+\t    DV_I_47_2_BIT,\n+\t    DV_I_48_2_BIT,\n+\t    0,\n+\t    0 } }\n+};\n+\n+static const struct ubc_cond avx2_tail_checks[] = {\n+\t/* DV_I_43_0 */\n+\t{ 58, 0, 63, 30, 1 },\n+\t{ 61, 1, 62, 6, 1 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t/* DV_I_44_0 */\n+\t{ 59, 0, 64, 30, 1 },\n+\t{ 62, 1, 63, 6, 1 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t/* DV_I_45_0 */\n+\t{ 63, 1, 64, 6, 1 },\n+\t{ 35, 4, 39, 29, 0 },\n+\t/* DV_I_46_0 */\n+\t{ 61, 0, 62, 5, 1 },\n+\t/* DV_I_47_0 */\n+\t{ 62, 0, 63, 5, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t/* DV_I_48_0 */\n+\t{ 63, 0, 64, 5, 1 },\n+\t{ 35, 4, 39, 29, 0 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t/* DV_I_49_0 */\n+\t{ 39, 4, 43, 29, 0 },\n+\t/* DV_I_50_0 */\n+\t{ 36, 4, 37, 4, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t{ 40, 4, 44, 29, 0 },\n+\t{ 46, 4, 50, 4, 0 },\n+\t/* DV_I_51_0 */\n+\t{ 37, 4, 38, 4, 1 },\n+\t{ 35, 3, 39, 28, 0 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t/* DV_I_51_2 */\n+\t{ 37, 1, 37, 6, 0 },\n+\t/* DV_I_52_0 */\n+\t{ 38, 4, 39, 4, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t{ 46, 4, 50, 4, 0 },\n+\t/* DV_II_45_0 */\n+\t{ 63, 1, 64, 6, 1 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t/* DV_II_46_0 */\n+\t{ 61, 0, 62, 5, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t/* DV_II_47_0 */\n+\t{ 62, 0, 63, 5, 1 },\n+\t{ 35, 3, 39, 28, 0 },\n+\t{ 35, 4, 39, 29, 0 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t/* DV_II_48_0 */\n+\t{ 35, 30, 36, 3, 1 },\n+\t{ 35, 30, 40, 28, 1 },\n+\t{ 63, 0, 64, 5, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t/* DV_II_49_0 */\n+\t{ 36, 30, 37, 3, 1 },\n+\t{ 36, 30, 41, 28, 1 },\n+\t{ 37, 4, 41, 29, 0 },\n+\t{ 40, 4, 44, 29, 0 },\n+\t/* DV_II_49_2 */\n+\t{ 36, 0, 37, 5, 1 },\n+\t/* DV_II_50_0 */\n+\t{ 37, 30, 38, 3, 1 },\n+\t{ 37, 30, 42, 28, 1 },\n+\t{ 38, 4, 42, 29, 0 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t{ 54, 4, 57, 29, 0 },\n+\t/* DV_II_51_0 */\n+\t{ 38, 30, 39, 3, 1 },\n+\t{ 38, 30, 43, 28, 1 },\n+\t{ 39, 4, 43, 29, 0 },\n+\t{ 55, 4, 58, 29, 0 },\n+\t/* DV_II_51_2 */\n+\t{ 52, 1, 56, 1, 1 },\n+\t/* DV_II_52_0 */\n+\t{ 39, 30, 40, 3, 1 },\n+\t{ 40, 4, 44, 29, 0 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t{ 54, 4, 57, 29, 0 },\n+\t{ 56, 4, 59, 29, 0 },\n+\t/* DV_II_53_0 */\n+\t{ 55, 4, 57, 4, 1 },\n+\t{ 41, 4, 45, 29, 0 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t{ 55, 4, 58, 29, 0 },\n+\t{ 55, 4, 57, 29, 0 },\n+\t/* DV_II_54_0 */\n+\t{ 42, 3, 46, 28, 0 },\n+\t{ 56, 4, 59, 29, 0 },\n+\t{ 56, 4, 58, 29, 0 },\n+\t{ 58, 4, 62, 29, 0 },\n+\t/* DV_II_55_0 */\n+\t{ 43, 3, 47, 28, 0 },\n+\t{ 43, 4, 47, 29, 0 },\n+\t{ 57, 4, 59, 29, 0 },\n+\t{ 59, 4, 63, 29, 0 },\n+\t/* DV_II_56_0 */\n+\t{ 44, 3, 48, 28, 0 },\n+\t{ 44, 4, 48, 29, 0 },\n+\t{ 60, 4, 64, 29, 0 }\n+};\n+\n+static const struct tail_span avx2_tail_spans[32] = {\n+\t{ 0, 3 },\t/* DV_I_43_0 */\n+\t{ 3, 3 },\t/* DV_I_44_0 */\n+\t{ 6, 2 },\t/* DV_I_45_0 */\n+\t{ 8, 1 },\t/* DV_I_46_0 */\n+\t{ 9, 0 },\t/* DV_I_46_2 */\n+\t{ 9, 2 },\t/* DV_I_47_0 */\n+\t{ 11, 0 },\t/* DV_I_47_2 */\n+\t{ 11, 3 },\t/* DV_I_48_0 */\n+\t{ 14, 0 },\t/* DV_I_48_2 */\n+\t{ 14, 1 },\t/* DV_I_49_0 */\n+\t{ 15, 0 },\t/* DV_I_49_2 */\n+\t{ 15, 4 },\t/* DV_I_50_0 */\n+\t{ 19, 0 },\t/* DV_I_50_2 */\n+\t{ 19, 4 },\t/* DV_I_51_0 */\n+\t{ 23, 1 },\t/* DV_I_51_2 */\n+\t{ 24, 3 },\t/* DV_I_52_0 */\n+\t{ 27, 2 },\t/* DV_II_45_0 */\n+\t{ 29, 2 },\t/* DV_II_46_0 */\n+\t{ 31, 0 },\t/* DV_II_46_2 */\n+\t{ 31, 5 },\t/* DV_II_47_0 */\n+\t{ 36, 5 },\t/* DV_II_48_0 */\n+\t{ 41, 4 },\t/* DV_II_49_0 */\n+\t{ 45, 1 },\t/* DV_II_49_2 */\n+\t{ 46, 5 },\t/* DV_II_50_0 */\n+\t{ 51, 0 },\t/* DV_II_50_2 */\n+\t{ 51, 4 },\t/* DV_II_51_0 */\n+\t{ 55, 1 },\t/* DV_II_51_2 */\n+\t{ 56, 5 },\t/* DV_II_52_0 */\n+\t{ 61, 5 },\t/* DV_II_53_0 */\n+\t{ 66, 4 },\t/* DV_II_54_0 */\n+\t{ 70, 4 },\t/* DV_II_55_0 */\n+\t{ 74, 3 }\t/* DV_II_56_0 */\n+};\n+\n+SHA1DC_TARGET_AVX2\n+static uint32_t avx2_prefix(const uint32_t *w)\n+{\n+\tconst __m256i zero = _mm256_setzero_si256();\n+\t__m256i acc = zero;\n+\t__m128i half;\n+\tsize_t i;\n+\n+\tUNROLL_TABLE\n+\tfor (i = 0; i < ARRAY_SIZE(avx2_groups); i++) {\n+\t\tconst struct ubc_group8 *g = &avx2_groups[i];\n+\t\t__m256i lo = _mm256_loadu_si256((const __m256i *)(w + g->lo));\n+\t\t__m256i hi = _mm256_loadu_si256((const __m256i *)(w + g->hi));\n+\t\t__m256i test = _mm256_loadu_si256((const __m256i *)g->test);\n+\t\t__m256i dvs = _mm256_loadu_si256((const __m256i *)g->dvs);\n+\t\t__m256i clear, fail;\n+\n+\t\tlo = _mm256_srl_epi32(lo, _mm_cvtsi32_si128(g->lo_shift));\n+\t\thi = _mm256_srl_epi32(hi, _mm_cvtsi32_si128(g->hi_shift));\n+\t\tclear = _mm256_and_si256(_mm256_xor_si256(lo, hi), test);\n+\t\tclear = _mm256_cmpeq_epi32(clear, zero);\n+\t\t/* The DVs of the lanes where the bit is not g->want. */\n+\t\tfail = g->want ? _mm256_and_si256(clear, dvs) :\n+\t\t\t\t _mm256_andnot_si256(clear, dvs);\n+\t\tacc = _mm256_or_si256(acc, fail);\n+\t}\n+\n+\thalf = _mm_or_si128(_mm256_castsi256_si128(acc),\n+\t\t\t    _mm256_extracti128_si256(acc, 1));\n+\thalf = _mm_or_si128(half, _mm_shuffle_epi32(half, 0x4E));\n+\thalf = _mm_or_si128(half, _mm_shuffle_epi32(half, 0xB1));\n+\treturn ~(uint32_t)_mm_cvtsi128_si32(half);\n+}\n+\n+SHA1DC_TARGET_AVX2\n+uint32_t sha1dc_ubc_check_avx2(const uint32_t w[80])\n+{\n+\tuint32_t mask = avx2_prefix(w);\n+\t/* Every check only clears bits, so an empty mask settles it. */\n+\tif (!mask)\n+\t\treturn 0;\n+\treturn run_tail(w, mask, avx2_tail_checks, avx2_tail_spans);\n+}\n+\n+#endif /* SHA1DC_HAVE_AVX2 */\ndiff --git a/sha1dc-accel/x86.c b/sha1dc-accel/x86.c\nnew file mode 100644\nindex 0000000000..7c942fe4de\n--- /dev/null\n+++ b/sha1dc-accel/x86.c\n@@ -0,0 +1,38 @@\n+/*\n+ * The x86-64 parts of sha1.c: detecting what the CPU has.\n+ */\n+\n+#include \"../git-compat-util.h\"\n+#include \"internal.h\"\n+\n+#ifdef SHA1DC_HAVE_SSE2\n+\n+#include <cpuid.h>\n+\n+/* Leaf 7 of CPUID, subleaf 0, if the CPU has it. */\n+static int cpuid_7(unsigned int *ebx)\n+{\n+\tunsigned int eax, ecx, edx;\n+\n+\tif (__get_cpuid_max(0, NULL) < 7)\n+\t\treturn 0;\n+\t__cpuid_count(7, 0, eax, *ebx, ecx, edx);\n+\treturn 1;\n+}\n+\n+int sha1dc_avx2_available(void)\n+{\n+\tunsigned int eax, ebx, ecx, edx, xcr0_lo, xcr0_hi;\n+\n+\tif (!__get_cpuid(1, &eax, &ebx, &ecx, &edx))\n+\t\treturn 0;\n+\t/* OSXSAVE and AVX, then whether the OS saves the YMM registers. */\n+\tif ((ecx & (1u << 27 | 1u << 28)) != (1u << 27 | 1u << 28))\n+\t\treturn 0;\n+\t__asm__(\"xgetbv\" : \"=a\"(xcr0_lo), \"=d\"(xcr0_hi) : \"c\"(0));\n+\tif ((xcr0_lo & 6) != 6)\n+\t\treturn 0;\n+\treturn cpuid_7(&ebx) && (ebx & (1u << 5));\n+}\n+\n+#endif /* SHA1DC_HAVE_SSE2 */\ndiff --git a/t/unit-tests/u-sha1dc.c b/t/unit-tests/u-sha1dc.c\nindex 31fcd68451..15e71fb023 100644\n--- a/t/unit-tests/u-sha1dc.c\n+++ b/t/unit-tests/u-sha1dc.c\n@@ -126,6 +126,76 @@ static void every_backend_agrees_with_sha1dc(void)\n \tcl_assert_equal_i(sha1dc_accel_select(orig), 0);\n }\n \n+/* Asserts only on a mismatch; clar's assertions are too slow to run 10^5 times. */\n+#define check_form(got, want) do { \\\n+\t\tuint32_t got_ = (got); \\\n+\t\tif (got_ != (want)) \\\n+\t\t\tcl_assert_equal_i(got_, (want)); \\\n+\t} while (0)\n+\n+/*\n+ * Checks every form of the UBC check against sha1dc/'s on `w`, and next to\n+ * it, with each bit flipped in turn if `flip`.\n+ */\n+static void check_ubc_forms(uint32_t w[80], int flip, int avx2)\n+{\n+\tint k;\n+\n+\tfor (k = 0; k <= (flip ? 80 * 32 : 0); k++) {\n+\t\tuint32_t want;\n+\n+\t\tif (k)\n+\t\t\tw[(k - 1) / 32] ^= 1u << ((k - 1) % 32);\n+\t\tubc_check(w, &want);\n+\t\tcheck_form(sha1dc_ubc_check_scalar(w), want);\n+#ifdef SHA1DC_HAVE_SSE2\n+\t\tcheck_form(sha1dc_ubc_check_sse2(w), want);\n+#endif\n+#ifdef SHA1DC_HAVE_AVX2\n+\t\tif (avx2)\n+\t\t\tcheck_form(sha1dc_ubc_check_avx2(w), want);\n+#endif\n+#ifdef SHA1DC_HAVE_NEON\n+\t\tcheck_form(sha1dc_ubc_check_neon(w), want);\n+#endif\n+\t\t(void)avx2;\n+\t\tif (k)\n+\t\t\tw[(k - 1) / 32] ^= 1u << ((k - 1) % 32);\n+\t}\n+}\n+\n+static void ubc_forms_agree_with_sha1dc(void)\n+{\n+\tuint32_t w[80];\n+\tint i, k, dv, avx2 = 0;\n+\n+#ifdef SHA1DC_HAVE_AVX2\n+\t/* Once: CPUID can take microseconds under a hypervisor. */\n+\tavx2 = sha1dc_avx2_available();\n+#endif\n+\trng_seed(2);\n+\tfor (i = 0; i < 20000; i++) {\n+\t\tfor (k = 0; k < 80; k++)\n+\t\t\tw[k] = rng();\n+\t\tcheck_ubc_forms(w, 0, avx2);\n+\t}\n+\n+\t/*\n+\t * Random schedules rarely get past the vector prefix of a form, so\n+\t * look for one that keeps each DV alive, and check around it.\n+\t */\n+\tfor (dv = 0; dv < 32; dv++) {\n+\t\tuint32_t mask;\n+\n+\t\tdo {\n+\t\t\tfor (k = 0; k < 80; k++)\n+\t\t\t\tw[k] = rng();\n+\t\t\tubc_check(w, &mask);\n+\t\t} while (!(mask & (1u << dv)));\n+\t\tcheck_ubc_forms(w, 1, avx2);\n+\t}\n+}\n+\n #endif /* HAVE_SHA1DC_ACCEL */\n \n #ifdef HAVE_SHA1DC_ACCEL\n@@ -143,3 +213,8 @@ void test_sha1dc__every_backend_agrees_with_sha1dc(void)\n {\n \tRUN_OR_SKIP(every_backend_agrees_with_sha1dc);\n }\n+\n+void test_sha1dc__ubc_forms_agree_with_sha1dc(void)\n+{\n+\tRUN_OR_SKIP(ubc_forms_agree_with_sha1dc);\n+}\n-- \n2.50.1 (Apple Git-155)\n\n\n"},{"id":"553586","messageId":"20260929112544.86511-4-scott@gitbutler.net","threadId":"66420","inReplyTo":"20260929112544.86511-1-scott@gitbutler.net","subject":"[PATCH 3/4] sha1dc-accel: compress with SHA-NI on x86-64","fromName":"Scott Chacon","fromEmail":"scott@gitbutler.net","sentAt":"2026-09-29T11:25:43Z","receivedAt":"2026-09-29T11:26:03Z","isPatch":true,"body":"With the UBC check out of the way, most of what's left is the SHA-1\ncompression itself, which we still do in portable C. Most x86-64 CPUs\nfrom the last several years (Intel since Ice Lake and some Atoms, AMD\nsince Zen) have instructions for that: sha1rnds4 does four rounds at a\ntime, and sha1msg1/sha1msg2 do the message expansion.\n\nThere are two catches. The first is that the detection needs the\nexpanded schedule, which the instructions keep to themselves. That's\neasy enough: as each group of four words is used, we store it (with a\nshuffle, since SHA-NI holds them in reverse order). Words 16 to 31 come\nfrom sha1msg1/sha1msg2, and the rest from the recurrence\n\n  W[t] = (W[t-6] ^ W[t-16] ^ W[t-28] ^ W[t-32]) <<< 2\n\nin plain SSE, in which no word of a group depends on another. That's\nwhat the crate does, too; it notes that sha1msg2 is microcoded on\nSapphire Rapids, where this runs about 10% faster.\n\nThe second catch is that the recompression starts from the working\nstate before step 58 or step 65, and the instructions only let us see\nthe state between groups of four steps. But the state at step 60 is\njust two steps away from 58, and 64 is one step from 65. So we save\nthose two for every block, and only for a block that the filter flags\n(about one in twenty) do we walk them the rest of the way.\n\nWhile we're here, we can do the recompression of those flagged blocks\nwith the SHA-1 instructions, too. The portable code runs the partner\nblock backwards from its state at 58 or 65 to find the chaining value\nit started from, then forwards to find the one it ends on, and compares\nthat with ours. But the instructions only go forwards. So instead we run\nthe partner forwards from step 60 or 64 to step 80, which tells us the\nonly input chaining value that could produce our output (it's the output\nminus the state at 80, since the feed-forward is just addition). Then we\nrun forwards from that input to step 60 or 64 and see if we arrive back\nwhere we started. Since each step is a bijection, that's the same test.\n\nThe exception is reduced-round detection, which also wants to know the\npartner's input chaining value for its own sake. Git never turns that\non, so it just keeps using the portable recompression.\n\nWe check for SHA-NI (plus SSSE3 and SSE4.1, which the code also needs)\nwith cpuid when we pick a backend, and compile with target attributes,\nso there's nothing to configure. That gives two new backends in front of\nthe others, shani+avx2 and shani+sse2, which differ only in the UBC\ncheck.\n\nThe unit test gains a check of the compression against SHA-1 steps\nwritten out in the test itself, and of the recompression, which must\naccept the partner's real output and reject any other.\n\nWith the usual 256MB of random data (the Xeon picks shani+avx2):\n\n  Benchmark 1: test-tool.old sha1\n    Time (mean ± σ):     590.3 ms ±  83.8 ms    [User: 541.0 ms, System: 42.6 ms]\n    Range (min … max):   440.2 ms … 750.7 ms    30 runs\n\n  Benchmark 2: test-tool.new sha1\n    Time (mean ± σ):     285.2 ms ±  26.0 ms    [User: 238.9 ms, System: 42.1 ms]\n    Range (min … max):   223.9 ms … 341.5 ms    30 runs\n\n  Summary\n    test-tool.new sha1 ran\n      2.07 ± 0.35 times faster than test-tool.old sha1\n\nThat makes the whole series so far 2.70 ± 0.35 times faster than plain\nsha1dc/ on this machine. Or, for index-pack on the 208MB pack of a clone\nof git.git, single-threaded:\n\n  Benchmark 1: git.old index-pack --threads=1\n    Time (mean ± σ):     24.301 s ±  1.102 s    [User: 23.739 s, System: 0.219 s]\n    Range (min … max):   23.557 s … 26.215 s    5 runs\n\n  Benchmark 2: git.new index-pack --threads=1\n    Time (mean ± σ):     12.689 s ±  0.385 s    [User: 12.293 s, System: 0.197 s]\n    Range (min … max):   12.274 s … 13.226 s    5 runs\n\n  Summary\n    git.new index-pack --threads=1 ran\n      1.92 ± 0.10 times faster than git.old index-pack --threads=1\n\nand with 4 threads:\n\n  Benchmark 1: git.old index-pack --threads=4\n    Time (mean ± σ):     10.450 s ±  0.445 s    [User: 27.147 s, System: 0.497 s]\n    Range (min … max):    9.853 s … 10.782 s    5 runs\n\n  Benchmark 2: git.new index-pack --threads=4\n    Time (mean ± σ):      5.924 s ±  0.214 s    [User: 12.693 s, System: 0.527 s]\n    Range (min … max):    5.591 s …  6.185 s    5 runs\n\n  Summary\n    git.new index-pack --threads=4 ran\n      1.76 ± 0.10 times faster than git.old index-pack --threads=4\n\nHashing in-process, shani+avx2 runs at 900 to 1050 MiB/s for messages\nof 1KiB and up, against 1130 to 1230 MiB/s for OpenSSL's SHA-1 (which\ndoesn't detect collisions at all) and 420 to 450 MiB/s for sha1dc/. The\nfull test suite passes on this machine, as do t0013 and the unit tests\nfor each of its five backends.\n\nSigned-off-by: Scott Chacon <scott@gitbutler.net>\nAssisted-by: Claude Opus 5.5 <noreply@anthropic.com>\n---\n Makefile                |   2 +-\n sha1dc-accel/internal.h |  28 +++++\n sha1dc-accel/sha1.c     | 105 ++++++++++++++-----\n sha1dc-accel/x86.c      | 224 +++++++++++++++++++++++++++++++++++++++-\n t/unit-tests/u-sha1dc.c | 141 ++++++++++++++++++++++++-\n 5 files changed, 471 insertions(+), 29 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 3ad8a7fc92..8181ea5692 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -569,7 +569,7 @@ include shared.mak\n #\n # Unless DC_SHA1_EXTERNAL is defined, the built-in code is driven by the\n # faster implementation in sha1dc-accel/, which gives the same results\n-# using the CPU's vector units where it has them.\n+# using the CPU's SHA-1 instructions and vector units where it has them.\n # Define DC_SHA1_NO_ACCEL to use the sha1collisiondetection code alone.\n #\n # === SHA-256 backend ===\ndiff --git a/sha1dc-accel/internal.h b/sha1dc-accel/internal.h\nindex 03427224da..a27fda19d1 100644\n--- a/sha1dc-accel/internal.h\n+++ b/sha1dc-accel/internal.h\n@@ -19,9 +19,11 @@\n # if defined(__x86_64__) && (defined(__clang__) || __GNUC__ >= 5)\n #  define SHA1DC_HAVE_SSE2 1\n #  define SHA1DC_HAVE_AVX2 1\n+#  define SHA1DC_HAVE_SHANI 1\n #  include <immintrin.h>\n #  define SHA1DC_TARGET_SSE2\n #  define SHA1DC_TARGET_AVX2 __attribute__((target(\"avx2\")))\n+#  define SHA1DC_TARGET_SHANI __attribute__((target(\"sha,sse4.1,ssse3\")))\n # elif defined(__aarch64__) && defined(__ARM_NEON)\n #  define SHA1DC_HAVE_NEON 1\n #  include <arm_neon.h>\n@@ -71,4 +73,30 @@ uint32_t sha1dc_ubc_check_neon(const uint32_t w[80]);\n int sha1dc_avx2_available(void);\n #endif\n \n+/*\n+ * The state the partner block of a DV reaches at the group boundary next to\n+ * where its recompression starts: step 60 from step 58, step 64 from step\n+ * 65. `state` is this block's state at `from`. In sha1.c.\n+ */\n+void sha1dc_partner_boundary(enum sha1dc_from from, const uint32_t m1[80],\n+\t\t\t     const uint32_t dm[80], const uint32_t state[5],\n+\t\t\t     uint32_t out[5]);\n+\n+/*\n+ * The hardware compression. It compresses one 64-byte block into `ihv`,\n+ * writes the expanded schedule to `w`, and this block's own states at\n+ * steps 60 and 64 to `at_60` and `at_64`.\n+ *\n+ * Its recompression answers whether a DV candidate is really an attack,\n+ * running the partner block forwards from `state` (this block's state at\n+ * `from`) with the SHA-1 instructions.\n+ */\n+#ifdef SHA1DC_HAVE_SHANI\n+int sha1dc_shani_available(void);\n+void sha1dc_compress_shani(uint32_t ihv[5], const unsigned char *block,\n+\t\t\t   uint32_t w[80], uint32_t at_60[5], uint32_t at_64[5]);\n+int sha1dc_recompress_shani(enum sha1dc_from from, const uint32_t m1[80],\n+\t\t\t    const uint32_t dm[80], const uint32_t state[5],\n+\t\t\t    const uint32_t ihv_out[5]);\n+#endif\n #endif /* SHA1DC_ACCEL_INTERNAL_H */\ndiff --git a/sha1dc-accel/sha1.c b/sha1dc-accel/sha1.c\nindex 1b3d82b4e4..2f30b207db 100644\n--- a/sha1dc-accel/sha1.c\n+++ b/sha1dc-accel/sha1.c\n@@ -7,6 +7,14 @@\n  * Shumow. It is a port to C of the approach of the \"sha1dc\" Rust crate by\n  * Sam Reis (https://github.com/srijs/sha1dc), which gitoxide uses:\n  *\n+ *  - The compression runs on the CPU's SHA-1 instructions where it has them\n+ *    (SHA-NI on x86-64), and\n+ *    spills the expanded message schedule as it goes, which is all that\n+ *    detection needs from an ordinary block. The hardware keeps no\n+ *    intermediate states around, so the two states that recompression\n+ *    starts from (at steps 58 and 65) are recovered from the ones at steps\n+ *    60 and 64, and only for the rare block that needs them.\n+ *\n  *  - The unavoidable-bitconditions (UBC) filter, which rules out about 95%\n  *    of blocks and is most of what detection costs, has one form per\n  *    instruction set (SSE2, AVX2, NEON and portable C). For each, the\n@@ -15,9 +23,12 @@\n  *    the rest to a scalar tail that few blocks reach. Those choices are\n  *    kept as tables, run by a short loop per form. See ubc_check.c.\n  *\n- * The compression is portable C, and spills the expanded message schedule\n- * and the two states that recompression starts from (at steps 58 and 65)\n- * as it goes.\n+ *  - The recompression of a flagged block also runs on the SHA-1\n+ *    instructions, forwards from the partner block's state at step 60 or\n+ *    64, since that is the only direction they go.\n+ *\n+ * Without SHA-1 instructions the compression is portable C, and the\n+ * best-suited form of the filter still applies.\n  */\n \n #include \"../git-compat-util.h\"\n@@ -180,6 +191,14 @@ static void walk(uint32_t s[5], const uint32_t *m1, const uint32_t *dm,\n \ts[4] = e;\n }\n \n+void sha1dc_partner_boundary(enum sha1dc_from from, const uint32_t m1[80],\n+\t\t\t     const uint32_t dm[80], const uint32_t state[5],\n+\t\t\t     uint32_t out[5])\n+{\n+\tmemcpy(out, state, 5 * sizeof(*out));\n+\twalk(out, m1, dm, from, from == SHA1DC_FROM_58 ? 60 : 64);\n+}\n+\n /*\n  * The recompression, the way sha1dc/ does it: from this block's state at\n  * `from`, the partner block's chaining value on the way in (`ihv_in`) and\n@@ -215,31 +234,49 @@ static void compress_schedule(uint32_t ihv[5], const uint32_t w[80])\n struct backend {\n \tconst char *name;\n \t/*\n-\t * Compresses a block, spilling its schedule and the states at steps\n-\t * 58 and 65.\n+\t * Compresses a block and spills its schedule. If `at_60_64` is set,\n+\t * it leaves the states at steps 60 and 64 where the others leave the\n+\t * ones at 58 and 65.\n \t */\n \tvoid (*compress)(uint32_t ihv[5], const unsigned char *block,\n-\t\t\t uint32_t w[80], uint32_t state_58[5],\n-\t\t\t uint32_t state_65[5]);\n+\t\t\t uint32_t w[80], uint32_t s1[5], uint32_t s2[5]);\n+\tint at_60_64;\n \tuint32_t (*ubc_check)(const uint32_t w[80]);\n+\t/* Whether a candidate is an attack; NULL for recompress_portable(). */\n+\tint (*recompress)(enum sha1dc_from from, const uint32_t m1[80],\n+\t\t\t  const uint32_t dm[80], const uint32_t state[5],\n+\t\t\t  const uint32_t ihv_out[5]);\n \tint (*available)(void);\n };\n \n+#ifdef SHA1DC_HAVE_SHANI\n+static int shani_avx2_available(void)\n+{\n+\treturn sha1dc_shani_available() && sha1dc_avx2_available();\n+}\n+#endif\n+\n /* In order of preference. */\n static const struct backend backends[] = {\n+#ifdef SHA1DC_HAVE_SHANI\n+\t{ \"shani+avx2\", sha1dc_compress_shani, 1, sha1dc_ubc_check_avx2,\n+\t  sha1dc_recompress_shani, shani_avx2_available },\n+\t{ \"shani+sse2\", sha1dc_compress_shani, 1, sha1dc_ubc_check_sse2,\n+\t  sha1dc_recompress_shani, sha1dc_shani_available },\n+#endif\n #ifdef SHA1DC_HAVE_AVX2\n-\t{ \"portable+avx2\", compress_portable, sha1dc_ubc_check_avx2,\n+\t{ \"portable+avx2\", compress_portable, 0, sha1dc_ubc_check_avx2, NULL,\n \t  sha1dc_avx2_available },\n #endif\n #ifdef SHA1DC_HAVE_SSE2\n-\t{ \"portable+sse2\", compress_portable, sha1dc_ubc_check_sse2,\n+\t{ \"portable+sse2\", compress_portable, 0, sha1dc_ubc_check_sse2, NULL,\n \t  NULL },\n #endif\n #ifdef SHA1DC_HAVE_NEON\n-\t{ \"portable+neon\", compress_portable, sha1dc_ubc_check_neon,\n+\t{ \"portable+neon\", compress_portable, 0, sha1dc_ubc_check_neon, NULL,\n \t  NULL },\n #endif\n-\t{ \"portable\", compress_portable, sha1dc_ubc_check_scalar, NULL },\n+\t{ \"portable\", compress_portable, 0, sha1dc_ubc_check_scalar, NULL, NULL },\n };\n \n static int usable(const struct backend *be)\n@@ -320,22 +357,27 @@ const char *const *sha1dc_accel_backends(void)\n \n /*\n  * Whether any DV in `candidates` makes this block half of a collision.\n- * `ihv_in` and `ihv_out` are the chaining values before and after it.\n+ * `s1` and `s2` are what the compression left, `ihv_in` and `ihv_out` the\n+ * chaining values before and after it.\n  */\n-static SHA1DC_NOINLINE int attacked(SHA1_CTX *ctx, uint32_t candidates,\n-\t\t\t\t    const uint32_t w[80],\n-\t\t\t\t    const uint32_t state_58[5],\n-\t\t\t\t    const uint32_t state_65[5],\n+static SHA1DC_NOINLINE int attacked(const struct backend *be, SHA1_CTX *ctx,\n+\t\t\t\t    uint32_t candidates, const uint32_t w[80],\n+\t\t\t\t    uint32_t s1[5], uint32_t s2[5],\n \t\t\t\t    const uint32_t ihv_in[5],\n \t\t\t\t    const uint32_t ihv_out[5])\n {\n+\tconst uint32_t *state_58 = s1, *state_65 = s2;\n \tint i;\n \n+\tif (be->at_60_64) {\n+\t\twalk(s1, w, NULL, 60, 58);\n+\t\twalk(s2, w, NULL, 64, 65);\n+\t}\n+\n \tfor (i = 0; sha1_dvs[i].dvType != 0; i++) {\n \t\tconst dv_info_t *dv = &sha1_dvs[i];\n \t\tenum sha1dc_from from;\n \t\tconst uint32_t *state;\n-\t\tuint32_t ihv2_in[5], ihv2_out[5];\n \n \t\tif (!(candidates & ((uint32_t)1 << dv->maskb)))\n \t\t\tcontinue;\n@@ -354,11 +396,23 @@ static SHA1DC_NOINLINE int attacked(SHA1_CTX *ctx, uint32_t candidates,\n \t\t\t    dv->dvType, dv->dvK, dv->dvB, dv->testt);\n \t\t}\n \n-\t\trecompress_portable(from, w, dv->dm, state, ihv2_in, ihv2_out);\n-\t\tif (!memcmp(ihv2_out, ihv_out, sizeof(ihv2_out)) ||\n-\t\t    (ctx->reduced_round_coll &&\n-\t\t     !memcmp(ihv2_in, ihv_in, sizeof(ihv2_in))))\n-\t\t\treturn 1;\n+\t\t/*\n+\t\t * Reduced-round collisions are recognized by the partner\n+\t\t * block's chaining value on the way in, which only the\n+\t\t * portable recompression computes.\n+\t\t */\n+\t\tif (be->recompress && !ctx->reduced_round_coll) {\n+\t\t\tif (be->recompress(from, w, dv->dm, state, ihv_out))\n+\t\t\t\treturn 1;\n+\t\t} else {\n+\t\t\tuint32_t ihv2_in[5], ihv2_out[5];\n+\n+\t\t\trecompress_portable(from, w, dv->dm, state, ihv2_in, ihv2_out);\n+\t\t\tif (!memcmp(ihv2_out, ihv_out, sizeof(ihv2_out)) ||\n+\t\t\t    (ctx->reduced_round_coll &&\n+\t\t\t     !memcmp(ihv2_in, ihv_in, sizeof(ihv2_in))))\n+\t\t\t\treturn 1;\n+\t\t}\n \t}\n \treturn 0;\n }\n@@ -366,17 +420,16 @@ static SHA1DC_NOINLINE int attacked(SHA1_CTX *ctx, uint32_t candidates,\n static inline void process(const struct backend *be, SHA1_CTX *ctx,\n \t\t\t   const unsigned char *block)\n {\n-\tuint32_t w[80], state_58[5], state_65[5], ihv_in[5], candidates;\n+\tuint32_t w[80], s1[5], s2[5], ihv_in[5], candidates;\n \n \tmemcpy(ihv_in, ctx->ihv, sizeof(ihv_in));\n-\tbe->compress(ctx->ihv, block, w, state_58, state_65);\n+\tbe->compress(ctx->ihv, block, w, s1, s2);\n \tif (!ctx->detect_coll)\n \t\treturn;\n \n \tcandidates = ctx->ubc_check ? be->ubc_check(w) : 0xFFFFFFFF;\n \tif (candidates &&\n-\t    attacked(ctx, candidates, w, state_58, state_65, ihv_in,\n-\t\t     ctx->ihv)) {\n+\t    attacked(be, ctx, candidates, w, s1, s2, ihv_in, ctx->ihv)) {\n \t\tctx->found_collision = 1;\n \t\t/*\n \t\t * Two more compressions of this block give a digest that the\ndiff --git a/sha1dc-accel/x86.c b/sha1dc-accel/x86.c\nindex 7c942fe4de..c2a0c71f17 100644\n--- a/sha1dc-accel/x86.c\n+++ b/sha1dc-accel/x86.c\n@@ -1,5 +1,6 @@\n /*\n- * The x86-64 parts of sha1.c: detecting what the CPU has.\n+ * The x86-64 parts of sha1.c: detecting what the CPU has, and the SHA-1\n+ * compression and recompression on SHA-NI.\n  */\n \n #include \"../git-compat-util.h\"\n@@ -35,4 +36,225 @@ int sha1dc_avx2_available(void)\n \treturn cpuid_7(&ebx) && (ebx & (1u << 5));\n }\n \n+#ifdef SHA1DC_HAVE_SHANI\n+\n+int sha1dc_shani_available(void)\n+{\n+\tunsigned int eax, ebx, ecx, edx;\n+\n+\tif (!__get_cpuid(1, &eax, &ebx, &ecx, &edx))\n+\t\treturn 0;\n+\t/* SSSE3 and SSE4.1 */\n+\tif ((ecx & (1u << 9 | 1u << 19)) != (1u << 9 | 1u << 19))\n+\t\treturn 0;\n+\treturn cpuid_7(&ebx) && (ebx & (1u << 29));\n+}\n+\n+/*\n+ * `sha1rnds4` does four steps at a time, on `abcd` held with A in the top\n+ * lane; `sha1nexte` derives the fifth working word for the next group from\n+ * the previous `abcd`, which is why two registers alternate as `live` and\n+ * `held`. The group of schedule words for steps t..t+3 is held reversed too.\n+ * Words 16 to 31 come from `sha1msg1`/`sha1msg2`, the rest from plain SSE\n+ * by the recurrence W[t] = (W[t-6] ^ W[t-16] ^ W[t-28] ^ W[t-32]) <<< 2, in\n+ * which no word of a group depends on another.\n+ */\n+\n+/* Turns a group round, between step order and the order SHA-NI holds. */\n+#define REVERSE 0x1B\n+\n+#define LOADU(p) _mm_loadu_si128((const __m128i *)(const void *)(p))\n+#define STOREU(p, v) _mm_storeu_si128((__m128i *)(void *)(p), (v))\n+\n+/* Writes group `v` (steps t..t+3, held reversed) to w[t..t+3]. */\n+#define SPILL(t, v) STOREU(w + (t), _mm_shuffle_epi32((v), REVERSE))\n+\n+/* Schedule words 4k..4k+3 for k from 8 on, from groups k-8, k-7, k-4, k-2, k-1. */\n+SHA1DC_TARGET_SHANI\n+static inline __m128i expand_rol2(__m128i v8, __m128i v7, __m128i v4,\n+\t\t\t\t  __m128i v2, __m128i v1)\n+{\n+\t__m128i x = _mm_xor_si128(_mm_xor_si128(v8, v7), v4);\n+\t/* Words t-6 to t-3: the last two of group k-2, the first two of k-1. */\n+\tx = _mm_xor_si128(x, _mm_alignr_epi8(v2, v1, 8));\n+\treturn _mm_or_si128(_mm_slli_epi32(x, 2), _mm_srli_epi32(x, 30));\n+}\n+\n+/* Schedule words 4k..4k+3 for k from 4 to 7, with the SHA-NI instructions. */\n+#define EXPAND_NI(a, b, c, d) \\\n+\t_mm_sha1msg2_epu32(_mm_xor_si128(_mm_sha1msg1_epu32((a), (b)), (c)), (d))\n+\n+/* One group of four steps on schedule group `t / 4`, spilling it first. */\n+#define ROUNDS(t, k, live, held) \\\n+\tdo { \\\n+\t\tSPILL(t, v[(t) / 4]); \\\n+\t\tlive = _mm_sha1nexte_epu32(live, v[(t) / 4]); \\\n+\t\theld = abcd; \\\n+\t\tabcd = _mm_sha1rnds4_epu32(abcd, live, k); \\\n+\t} while (0)\n+\n+/* The same, also storing the state [A, B, C, D, E] before it in `at`. */\n+#define ROUNDS_AT(t, k, live, held, at) \\\n+\tdo { \\\n+\t\tSPILL(t, v[(t) / 4]); \\\n+\t\tlive = _mm_sha1nexte_epu32(live, v[(t) / 4]); \\\n+\t\tSTOREU(at, _mm_shuffle_epi32(abcd, REVERSE)); \\\n+\t\t/* `live` holds E + W[t] in its top lane. */ \\\n+\t\tat[4] = (uint32_t)_mm_extract_epi32(_mm_sub_epi32(live, v[(t) / 4]), 3); \\\n+\t\theld = abcd; \\\n+\t\tabcd = _mm_sha1rnds4_epu32(abcd, live, k); \\\n+\t} while (0)\n+\n+#define ROL2(k) v[k] = expand_rol2(v[(k) - 8], v[(k) - 7], v[(k) - 4], v[(k) - 2], v[(k) - 1])\n+\n+SHA1DC_TARGET_SHANI\n+void sha1dc_compress_shani(uint32_t ihv[5], const unsigned char *block,\n+\t\t\t   uint32_t w[80], uint32_t at_60[5], uint32_t at_64[5])\n+{\n+\t/* Big-endian words, and the four of a group reversed. */\n+\tconst __m128i swap = _mm_set_epi64x(0x0001020304050607LL,\n+\t\t\t\t\t    0x08090A0B0C0D0E0FLL);\n+\t__m128i abcd = _mm_shuffle_epi32(LOADU(ihv), REVERSE);\n+\tconst __m128i abcd_in = abcd;\n+\tconst __m128i e_in = _mm_set_epi32((int)ihv[4], 0, 0, 0);\n+\t__m128i e0, e1, v[20];\n+\n+\tv[0] = _mm_shuffle_epi8(LOADU(block), swap);\n+\tv[1] = _mm_shuffle_epi8(LOADU(block + 16), swap);\n+\tv[2] = _mm_shuffle_epi8(LOADU(block + 32), swap);\n+\tv[3] = _mm_shuffle_epi8(LOADU(block + 48), swap);\n+\n+\tSPILL(0, v[0]);\n+\te0 = _mm_add_epi32(e_in, v[0]);\n+\te1 = abcd;\n+\tabcd = _mm_sha1rnds4_epu32(abcd, e0, 0);\n+\tv[4] = EXPAND_NI(v[0], v[1], v[2], v[3]);\n+\n+\tROUNDS(4, 0, e1, e0);\n+\tv[5] = EXPAND_NI(v[1], v[2], v[3], v[4]);\n+\tROUNDS(8, 0, e0, e1);\n+\tv[6] = EXPAND_NI(v[2], v[3], v[4], v[5]);\n+\tROUNDS(12, 0, e1, e0);\n+\tv[7] = EXPAND_NI(v[3], v[4], v[5], v[6]);\n+\tROUNDS(16, 0, e0, e1);\n+\tROL2(8);\n+\tROUNDS(20, 1, e1, e0);\n+\tROL2(9);\n+\tROUNDS(24, 1, e0, e1);\n+\tROL2(10);\n+\tROUNDS(28, 1, e1, e0);\n+\tROL2(11);\n+\tROUNDS(32, 1, e0, e1);\n+\tROL2(12);\n+\tROUNDS(36, 1, e1, e0);\n+\tROL2(13);\n+\tROUNDS(40, 2, e0, e1);\n+\tROL2(14);\n+\tROUNDS(44, 2, e1, e0);\n+\tROL2(15);\n+\tROUNDS(48, 2, e0, e1);\n+\tROL2(16);\n+\tROUNDS(52, 2, e1, e0);\n+\tROL2(17);\n+\tROUNDS(56, 2, e0, e1);\n+\tROL2(18);\n+\tROUNDS_AT(60, 3, e1, e0, at_60);\n+\tROL2(19);\n+\tROUNDS_AT(64, 3, e0, e1, at_64);\n+\tROUNDS(68, 3, e1, e0);\n+\tROUNDS(72, 3, e0, e1);\n+\tROUNDS(76, 3, e1, e0);\n+\n+\t/* Feed-forward. */\n+\te0 = _mm_sha1nexte_epu32(e0, e_in);\n+\tabcd = _mm_add_epi32(abcd, abcd_in);\n+\tSTOREU(ihv, _mm_shuffle_epi32(abcd, REVERSE));\n+\tihv[4] = (uint32_t)_mm_extract_epi32(e0, 3);\n+}\n+\n+/*\n+ * The partner block's schedule words for group `g`, in the order the\n+ * rounds take them.\n+ */\n+#define WORDS(g) \\\n+\t_mm_shuffle_epi32(_mm_xor_si128(LOADU(m1 + 4 * (g)), LOADU(dm + 4 * (g))), REVERSE)\n+\n+/* Four steps. The first of a run adds the fifth word itself. */\n+#define GROUP_FIRST(e, g, k) \\\n+\tdo { \\\n+\t\t__m128i live_ = _mm_add_epi32((e), WORDS(g)); \\\n+\t\theld = abcd; \\\n+\t\tabcd = _mm_sha1rnds4_epu32(abcd, live_, k); \\\n+\t} while (0)\n+#define GROUP(g, k) \\\n+\tdo { \\\n+\t\t__m128i live_ = _mm_sha1nexte_epu32(held, WORDS(g)); \\\n+\t\theld = abcd; \\\n+\t\tabcd = _mm_sha1rnds4_epu32(abcd, live_, k); \\\n+\t} while (0)\n+\n+/*\n+ * Whether the partner block, whose state at `from` is `state`, ends on\n+ * `ihv_out`. From its state at step 60 or 64, it runs out to step 80,\n+ * which gives the chaining value an attack would have had to start from,\n+ * and then in from that value, which must arrive back at the same state.\n+ */\n+SHA1DC_TARGET_SHANI\n+int sha1dc_recompress_shani(enum sha1dc_from from, const uint32_t m1[80],\n+\t\t\t    const uint32_t dm[80], const uint32_t state[5],\n+\t\t\t    const uint32_t ihv_out[5])\n+{\n+\tuint32_t at[5], reached[5];\n+\t__m128i abcd, held, e_at, e_80, e_in;\n+\n+\tsha1dc_partner_boundary(from, m1, dm, state, at);\n+\tabcd = _mm_shuffle_epi32(LOADU(at), REVERSE);\n+\n+\t/* Out to step 80, from 60 or from 64. */\n+\te_at = _mm_set_epi32((int)at[4], 0, 0, 0);\n+\tif (from == SHA1DC_FROM_58) {\n+\t\tGROUP_FIRST(e_at, 15, 3);\n+\t\tGROUP(16, 3);\n+\t} else {\n+\t\tGROUP_FIRST(e_at, 16, 3);\n+\t}\n+\tGROUP(17, 3);\n+\tGROUP(18, 3);\n+\tGROUP(19, 3);\n+\n+\t/*\n+\t * The feed-forward adds the input to the state at 80, so the only\n+\t * input that gives this block's output is the output less that state.\n+\t */\n+\te_80 = _mm_sha1nexte_epu32(held, _mm_setzero_si128());\n+\tabcd = _mm_sub_epi32(_mm_shuffle_epi32(LOADU(ihv_out), REVERSE), abcd);\n+\te_in = _mm_sub_epi32(_mm_set_epi32((int)ihv_out[4], 0, 0, 0), e_80);\n+\n+\t/* In from there, as far as the state the way out started from. */\n+\tGROUP_FIRST(e_in, 0, 0);\n+\tGROUP(1, 0);\n+\tGROUP(2, 0);\n+\tGROUP(3, 0);\n+\tGROUP(4, 0);\n+\tGROUP(5, 1);\n+\tGROUP(6, 1);\n+\tGROUP(7, 1);\n+\tGROUP(8, 1);\n+\tGROUP(9, 1);\n+\tGROUP(10, 2);\n+\tGROUP(11, 2);\n+\tGROUP(12, 2);\n+\tGROUP(13, 2);\n+\tGROUP(14, 2);\n+\tif (from == SHA1DC_FROM_65)\n+\t\tGROUP(15, 3);\n+\n+\tSTOREU(reached, _mm_shuffle_epi32(abcd, REVERSE));\n+\treached[4] = (uint32_t)_mm_extract_epi32(\n+\t\t_mm_sha1nexte_epu32(held, _mm_setzero_si128()), 3);\n+\treturn !memcmp(reached, at, sizeof(at));\n+}\n+\n+#endif /* SHA1DC_HAVE_SHANI */\n+\n #endif /* SHA1DC_HAVE_SSE2 */\ndiff --git a/t/unit-tests/u-sha1dc.c b/t/unit-tests/u-sha1dc.c\nindex 15e71fb023..5948466cb9 100644\n--- a/t/unit-tests/u-sha1dc.c\n+++ b/t/unit-tests/u-sha1dc.c\n@@ -2,7 +2,8 @@\n #include \"hash.h\"\n \n /*\n- * Tests sha1dc-accel/ against sha1dc/, which it must agree with exactly.\n+ * Tests sha1dc-accel/ against sha1dc/, which it must agree with exactly,\n+ * and its parts against the plain SHA-1 step function written out here.\n  */\n #if defined(SHA1_DC) && !defined(DC_SHA1_EXTERNAL) && !defined(DC_SHA1_NO_ACCEL)\n #define HAVE_SHA1DC_ACCEL\n@@ -196,6 +197,139 @@ static void ubc_forms_agree_with_sha1dc(void)\n \t}\n }\n \n+#ifdef SHA1DC_HAVE_SHANI\n+\n+static uint32_t rol(uint32_t x, int n)\n+{\n+\treturn (x << n) | (x >> (32 - n));\n+}\n+\n+static uint32_t f_k(int t, uint32_t b, uint32_t c, uint32_t d)\n+{\n+\tif (t < 20)\n+\t\treturn ((b & c) | (~b & d)) + 0x5A827999;\n+\tif (t < 40)\n+\t\treturn (b ^ c ^ d) + 0x6ED9EBA1;\n+\tif (t < 60)\n+\t\treturn ((b & c) | (b & d) | (c & d)) + 0x8F1BBCDC;\n+\treturn (b ^ c ^ d) + 0xCA62C1D6;\n+}\n+\n+/* One SHA-1 step forwards, from the state before step t. */\n+static void step(uint32_t s[5], int t, uint32_t w)\n+{\n+\tuint32_t a = rol(s[0], 5) + f_k(t, s[1], s[2], s[3]) + s[4] + w;\n+\ts[4] = s[3];\n+\ts[3] = s[2];\n+\ts[2] = rol(s[1], 30);\n+\ts[1] = s[0];\n+\ts[0] = a;\n+}\n+\n+/* One SHA-1 step backwards, to the state before step t. */\n+static void unstep(uint32_t s[5], int t, uint32_t w)\n+{\n+\tuint32_t a = s[1], b = rol(s[2], 2), c = s[3], d = s[4];\n+\ts[4] = s[0] - (rol(a, 5) + f_k(t, b, c, d) + w);\n+\ts[0] = a;\n+\ts[1] = b;\n+\ts[2] = c;\n+\ts[3] = d;\n+}\n+\n+typedef void (*compress_fn)(uint32_t ihv[5], const unsigned char *block,\n+\t\t\t    uint32_t w[80], uint32_t at_60[5], uint32_t at_64[5]);\n+typedef int (*recompress_fn)(enum sha1dc_from from, const uint32_t m1[80],\n+\t\t\t     const uint32_t dm[80], const uint32_t state[5],\n+\t\t\t     const uint32_t ihv_out[5]);\n+\n+static void check_compress(compress_fn compress)\n+{\n+\tint i, t;\n+\n+\trng_seed(3);\n+\tfor (i = 0; i < 2000; i++) {\n+\t\tunsigned char block[64];\n+\t\tuint32_t ihv[5], got[5], w[80], at_60[5], at_64[5], s[5];\n+\n+\t\tfor (t = 0; t < 64; t++)\n+\t\t\tblock[t] = rng();\n+\t\tfor (t = 0; t < 5; t++)\n+\t\t\tihv[t] = got[t] = rng();\n+\t\tcompress(got, block, w, at_60, at_64);\n+\n+\t\tmemcpy(s, ihv, sizeof(s));\n+\t\tfor (t = 0; t < 80; t++) {\n+\t\t\tuint32_t want_w = t < 16 ? get_be32(block + 4 * t) :\n+\t\t\t\trol(w[t - 3] ^ w[t - 8] ^ w[t - 14] ^ w[t - 16], 1);\n+\t\t\tcl_assert_equal_i(w[t], want_w);\n+\t\t\tif (t == 60)\n+\t\t\t\tcl_assert(!memcmp(at_60, s, sizeof(s)));\n+\t\t\tif (t == 64)\n+\t\t\t\tcl_assert(!memcmp(at_64, s, sizeof(s)));\n+\t\t\tstep(s, t, w[t]);\n+\t\t}\n+\t\tfor (t = 0; t < 5; t++)\n+\t\t\tcl_assert_equal_i(got[t], ihv[t] + s[t]);\n+\t}\n+}\n+\n+/*\n+ * A recompression must accept exactly the chaining value the partner\n+ * block ends on, and nothing else.\n+ */\n+static void check_recompress(recompress_fn recompress)\n+{\n+\tint i, t, d;\n+\n+\trng_seed(4);\n+\tfor (i = 0; i < 50; i++) {\n+\t\tuint32_t w[80], state[5];\n+\n+\t\tfor (t = 0; t < 80; t++)\n+\t\t\tw[t] = rng();\n+\t\tfor (t = 0; t < 5; t++)\n+\t\t\tstate[t] = rng();\n+\n+\t\tfor (d = 0; sha1_dvs[d].dvType; d++) {\n+\t\t\tconst dv_info_t *dv = &sha1_dvs[d];\n+\t\t\tenum sha1dc_from from = dv->testt == 58 ? SHA1DC_FROM_58 : SHA1DC_FROM_65;\n+\t\t\tuint32_t in[5], out[5];\n+\t\t\tunsigned nudge = rng();\n+\n+\t\t\tmemcpy(in, state, sizeof(in));\n+\t\t\tfor (t = dv->testt - 1; t >= 0; t--)\n+\t\t\t\tunstep(in, t, w[t] ^ dv->dm[t]);\n+\t\t\tmemcpy(out, state, sizeof(out));\n+\t\t\tfor (t = dv->testt; t < 80; t++)\n+\t\t\t\tstep(out, t, w[t] ^ dv->dm[t]);\n+\t\t\tfor (t = 0; t < 5; t++)\n+\t\t\t\tout[t] += in[t];\n+\n+\t\t\tcl_assert(recompress(from, w, dv->dm, state, out));\n+\t\t\tout[nudge % 5] ^= 1u << (nudge / 5 % 32);\n+\t\t\tcl_assert(!recompress(from, w, dv->dm, state, out));\n+\t\t}\n+\t}\n+}\n+\n+#endif\n+\n+static void hardware_compression(void)\n+{\n+\tint tested = 0;\n+\n+#ifdef SHA1DC_HAVE_SHANI\n+\tif (sha1dc_shani_available()) {\n+\t\tcheck_compress(sha1dc_compress_shani);\n+\t\tcheck_recompress(sha1dc_recompress_shani);\n+\t\ttested = 1;\n+\t}\n+#endif\n+\tif (!tested)\n+\t\tcl_skip();\n+}\n+\n #endif /* HAVE_SHA1DC_ACCEL */\n \n #ifdef HAVE_SHA1DC_ACCEL\n@@ -218,3 +352,8 @@ void test_sha1dc__ubc_forms_agree_with_sha1dc(void)\n {\n \tRUN_OR_SKIP(ubc_forms_agree_with_sha1dc);\n }\n+\n+void test_sha1dc__hardware_compression(void)\n+{\n+\tRUN_OR_SKIP(hardware_compression);\n+}\n-- \n2.50.1 (Apple Git-155)\n\n\n"},{"id":"553587","messageId":"20260929112544.86511-5-scott@gitbutler.net","threadId":"66420","inReplyTo":"20260929112544.86511-1-scott@gitbutler.net","subject":"[PATCH 4/4] sha1dc-accel: compress with the ARMv8 SHA-1 instructions","fromName":"Scott Chacon","fromEmail":"scott@gitbutler.net","sentAt":"2026-09-29T11:25:44Z","receivedAt":"2026-09-29T11:26:08Z","isPatch":true,"body":"Most arm64 CPUs, including Apple's and the Graviton line, have SHA-1\ninstructions, too, and we can use them the same way as SHA-NI in the\nprevious patch. It's a little simpler here: the instructions keep the\nworking state in the natural order, and vsha1h gives us the fifth word\ndirectly, so there's no shuffling to be done.\n\nKnowing whether we can use them is a little trickier:\n\n  - If the compiler targets them already (__ARM_FEATURE_SHA2 or\n    __ARM_FEATURE_CRYPTO, which is the case with Apple's clang on\n    macOS), we just use them.\n\n  - Otherwise we build the two functions that need them with a target\n    attribute, and check at run time. On Linux that's getauxval(); on\n    other platforms we don't know how to ask yet, and so don't use them.\n\n  - Older compilers only declare the intrinsics when the whole file\n    targets the instructions, so a target attribute doesn't help there.\n    We only try the attribute with GCC 9+ and clang 17+.\n\nThe one new backend, armv8+neon, goes to the front of the list.\n\nOn an Apple M5 Max (macOS, Apple clang), which picks armv8+neon, hashing\n1GiB of random data with \"test-tool sha1\" (median of 9 runs) goes:\n\n  sha1dc, before this series        1.46s   (~700 MiB/s)\n  block loop, after 1/4             1.55s\n  portable+neon, after 2/4          1.22s\n  armv8+neon, this patch            0.51s   (~2 GiB/s)\n\nwhich is 2.85x overall. For index-pack of the 319MB pack of a clone of\ngit.git, it goes from 16.1s to 8.7s single-threaded (1.86x), and from\n6.7s to 5.9s with all 18 threads. The full test suite passes there, too.\nFor comparison, the crate reports 81% of plain SHA-1's throughput on an\nApple M4 and 80% on a Graviton4, up from 29% [1].\n\nThe run-time check on Linux is only tested under qemu-user so far,\nbuilt with GCC 13 and clang 18, in a harness that compares every backend\nand UBC form against sha1dc/ (the same comparisons as the unit tests).\nI'd be happy to see numbers from anybody with a Graviton or similar\nmachine.\n\n[1] https://sam.dev/blog/faster-sha1-collision-detection\n\nSigned-off-by: Scott Chacon <scott@gitbutler.net>\nAssisted-by: Claude Opus 5.5 <noreply@anthropic.com>\n---\n Makefile                            |   1 +\n contrib/buildsystems/CMakeLists.txt |   2 +-\n meson.build                         |   1 +\n sha1dc-accel/arm.c                  | 274 ++++++++++++++++++++++++++++\n sha1dc-accel/internal.h             |  28 ++-\n sha1dc-accel/sha1.c                 |   6 +-\n t/unit-tests/u-sha1dc.c             |   9 +-\n 7 files changed, 316 insertions(+), 5 deletions(-)\n create mode 100644 sha1dc-accel/arm.c\n\ndiff --git a/Makefile b/Makefile\nindex 8181ea5692..731a5f60e8 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -2177,6 +2177,7 @@ endif\n ifdef DC_SHA1_NO_ACCEL\n \tBASIC_CFLAGS += -DDC_SHA1_NO_ACCEL\n else\n+\tLIB_OBJS += sha1dc-accel/arm.o\n \tLIB_OBJS += sha1dc-accel/sha1.o\n \tLIB_OBJS += sha1dc-accel/ubc_check.o\n \tLIB_OBJS += sha1dc-accel/x86.o\ndiff --git a/contrib/buildsystems/CMakeLists.txt b/contrib/buildsystems/CMakeLists.txt\nindex 67b96d601b..37ebb67a8d 100644\n--- a/contrib/buildsystems/CMakeLists.txt\n+++ b/contrib/buildsystems/CMakeLists.txt\n@@ -218,7 +218,7 @@ add_compile_definitions(NO_OPENSSL SHA1_DC SHA1DC_NO_STANDARD_INCLUDES\n \t\t\tSHA1DC_INIT_SAFE_HASH_DEFAULT=0\n \t\t\tSHA1DC_CUSTOM_INCLUDE_SHA1_C=\"git-compat-util.h\"\n \t\t\tSHA1DC_CUSTOM_INCLUDE_UBC_CHECK_C=\"git-compat-util.h\" )\n-list(APPEND compat_SOURCES sha1dc_git.c sha1dc/sha1.c sha1dc/ubc_check.c sha1dc-accel/sha1.c sha1dc-accel/ubc_check.c sha1dc-accel/x86.c block-sha1/sha1.c sha256/block/sha256.c compat/qsort_s.c)\n+list(APPEND compat_SOURCES sha1dc_git.c sha1dc/sha1.c sha1dc/ubc_check.c sha1dc-accel/arm.c sha1dc-accel/sha1.c sha1dc-accel/ubc_check.c sha1dc-accel/x86.c block-sha1/sha1.c sha256/block/sha256.c compat/qsort_s.c)\n \n \n add_compile_definitions(PAGER_ENV=\"LESS=FRX LV=-c\"\ndiff --git a/meson.build b/meson.build\nindex 47a60526e9..7aed4db1ba 100644\n--- a/meson.build\n+++ b/meson.build\n@@ -1631,6 +1631,7 @@ if sha1_backend == 'sha1dc'\n     'sha1dc_git.c',\n     'sha1dc/sha1.c',\n     'sha1dc/ubc_check.c',\n+    'sha1dc-accel/arm.c',\n     'sha1dc-accel/sha1.c',\n     'sha1dc-accel/ubc_check.c',\n     'sha1dc-accel/x86.c',\ndiff --git a/sha1dc-accel/arm.c b/sha1dc-accel/arm.c\nnew file mode 100644\nindex 0000000000..0d18354e56\n--- /dev/null\n+++ b/sha1dc-accel/arm.c\n@@ -0,0 +1,274 @@\n+/*\n+ * The SHA-1 compression and recompression on the ARMv8 SHA-1 instructions,\n+ * for sha1.c. `vsha1{c,p,m}q_u32` do four steps at a time on `abcd`, with\n+ * the fifth working word carried apart and derived by `vsha1h_u32`.\n+ */\n+\n+#include \"../git-compat-util.h\"\n+#include \"internal.h\"\n+\n+#ifdef SHA1DC_HAVE_ARMV8\n+\n+#if !defined(__ARM_FEATURE_SHA2) && !defined(__ARM_FEATURE_CRYPTO) && \\\n+\tdefined(__linux__)\n+#include <sys/auxv.h>\n+#ifndef HWCAP_SHA1\n+#define HWCAP_SHA1 (1 << 5)\n+#endif\n+#endif\n+\n+int sha1dc_armv8_available(void)\n+{\n+#if defined(__ARM_FEATURE_SHA2) || defined(__ARM_FEATURE_CRYPTO) || \\\n+\tdefined(__APPLE__)\n+\treturn 1;\n+#elif defined(__linux__)\n+\treturn !!(getauxval(AT_HWCAP) & HWCAP_SHA1);\n+#else\n+\treturn 0;\n+#endif\n+}\n+\n+#define K0 0x5A827999\n+#define K1 0x6ED9EBA1\n+#define K2 0x8F1BBCDC\n+#define K3 0xCA62C1D6\n+\n+/* Big-endian message words t..t+3. */\n+#define MSG(t) vreinterpretq_u32_u8(vrev32q_u8(vld1q_u8(block + 4 * (t))))\n+\n+/*\n+ * Four steps of a compression that keeps the schedule four groups ahead:\n+ * `f` the round instruction, `e` the fifth word in, `next` where the one\n+ * for the next group goes, `wk` the schedule words plus the constant.\n+ */\n+#define QUAD(f, e, next, wk) \\\n+\tdo { \\\n+\t\tnext = vsha1h_u32(vgetq_lane_u32(abcd, 0)); \\\n+\t\tabcd = f(abcd, e, wk); \\\n+\t} while (0)\n+\n+SHA1DC_TARGET_ARMV8\n+void sha1dc_compress_armv8(uint32_t ihv[5], const unsigned char *block,\n+\t\t\t   uint32_t w[80], uint32_t at_60[5], uint32_t at_64[5])\n+{\n+\tuint32x4_t abcd = vld1q_u32(ihv);\n+\tconst uint32x4_t abcd_in = abcd;\n+\tuint32_t e0 = ihv[4], e1;\n+\tconst uint32_t e_in = e0;\n+\tconst uint32x4_t k0 = vdupq_n_u32(K0), k1 = vdupq_n_u32(K1);\n+\tconst uint32x4_t k2 = vdupq_n_u32(K2), k3 = vdupq_n_u32(K3);\n+\tuint32x4_t msg0 = MSG(0), msg1 = MSG(4), msg2 = MSG(8), msg3 = MSG(12);\n+\tuint32x4_t tmp0, tmp1;\n+\n+\tvst1q_u32(w + 0, msg0);\n+\tvst1q_u32(w + 4, msg1);\n+\tvst1q_u32(w + 8, msg2);\n+\tvst1q_u32(w + 12, msg3);\n+\n+\ttmp0 = vaddq_u32(msg0, k0);\n+\ttmp1 = vaddq_u32(msg1, k0);\n+\n+\t/* Steps 0-3 */\n+\tQUAD(vsha1cq_u32, e0, e1, tmp0);\n+\ttmp0 = vaddq_u32(msg2, k0);\n+\tmsg0 = vsha1su0q_u32(msg0, msg1, msg2);\n+\n+\t/* Steps 4-7 */\n+\tQUAD(vsha1cq_u32, e1, e0, tmp1);\n+\ttmp1 = vaddq_u32(msg3, k0);\n+\tmsg0 = vsha1su1q_u32(msg0, msg3);\n+\tvst1q_u32(w + 16, msg0);\n+\tmsg1 = vsha1su0q_u32(msg1, msg2, msg3);\n+\n+\t/* Steps 8-11 */\n+\tQUAD(vsha1cq_u32, e0, e1, tmp0);\n+\ttmp0 = vaddq_u32(msg0, k0);\n+\tmsg1 = vsha1su1q_u32(msg1, msg0);\n+\tvst1q_u32(w + 20, msg1);\n+\tmsg2 = vsha1su0q_u32(msg2, msg3, msg0);\n+\n+\t/* Steps 12-15 */\n+\tQUAD(vsha1cq_u32, e1, e0, tmp1);\n+\ttmp1 = vaddq_u32(msg1, k1);\n+\tmsg2 = vsha1su1q_u32(msg2, msg1);\n+\tvst1q_u32(w + 24, msg2);\n+\tmsg3 = vsha1su0q_u32(msg3, msg0, msg1);\n+\n+\t/* Steps 16-19 */\n+\tQUAD(vsha1cq_u32, e0, e1, tmp0);\n+\ttmp0 = vaddq_u32(msg2, k1);\n+\tmsg3 = vsha1su1q_u32(msg3, msg2);\n+\tvst1q_u32(w + 28, msg3);\n+\tmsg0 = vsha1su0q_u32(msg0, msg1, msg2);\n+\n+\t/* Steps 20-23 */\n+\tQUAD(vsha1pq_u32, e1, e0, tmp1);\n+\ttmp1 = vaddq_u32(msg3, k1);\n+\tmsg0 = vsha1su1q_u32(msg0, msg3);\n+\tvst1q_u32(w + 32, msg0);\n+\tmsg1 = vsha1su0q_u32(msg1, msg2, msg3);\n+\n+\t/* Steps 24-27 */\n+\tQUAD(vsha1pq_u32, e0, e1, tmp0);\n+\ttmp0 = vaddq_u32(msg0, k1);\n+\tmsg1 = vsha1su1q_u32(msg1, msg0);\n+\tvst1q_u32(w + 36, msg1);\n+\tmsg2 = vsha1su0q_u32(msg2, msg3, msg0);\n+\n+\t/* Steps 28-31 */\n+\tQUAD(vsha1pq_u32, e1, e0, tmp1);\n+\ttmp1 = vaddq_u32(msg1, k1);\n+\tmsg2 = vsha1su1q_u32(msg2, msg1);\n+\tvst1q_u32(w + 40, msg2);\n+\tmsg3 = vsha1su0q_u32(msg3, msg0, msg1);\n+\n+\t/* Steps 32-35 */\n+\tQUAD(vsha1pq_u32, e0, e1, tmp0);\n+\ttmp0 = vaddq_u32(msg2, k2);\n+\tmsg3 = vsha1su1q_u32(msg3, msg2);\n+\tvst1q_u32(w + 44, msg3);\n+\tmsg0 = vsha1su0q_u32(msg0, msg1, msg2);\n+\n+\t/* Steps 36-39 */\n+\tQUAD(vsha1pq_u32, e1, e0, tmp1);\n+\ttmp1 = vaddq_u32(msg3, k2);\n+\tmsg0 = vsha1su1q_u32(msg0, msg3);\n+\tvst1q_u32(w + 48, msg0);\n+\tmsg1 = vsha1su0q_u32(msg1, msg2, msg3);\n+\n+\t/* Steps 40-43 */\n+\tQUAD(vsha1mq_u32, e0, e1, tmp0);\n+\ttmp0 = vaddq_u32(msg0, k2);\n+\tmsg1 = vsha1su1q_u32(msg1, msg0);\n+\tvst1q_u32(w + 52, msg1);\n+\tmsg2 = vsha1su0q_u32(msg2, msg3, msg0);\n+\n+\t/* Steps 44-47 */\n+\tQUAD(vsha1mq_u32, e1, e0, tmp1);\n+\ttmp1 = vaddq_u32(msg1, k2);\n+\tmsg2 = vsha1su1q_u32(msg2, msg1);\n+\tvst1q_u32(w + 56, msg2);\n+\tmsg3 = vsha1su0q_u32(msg3, msg0, msg1);\n+\n+\t/* Steps 48-51 */\n+\tQUAD(vsha1mq_u32, e0, e1, tmp0);\n+\ttmp0 = vaddq_u32(msg2, k2);\n+\tmsg3 = vsha1su1q_u32(msg3, msg2);\n+\tvst1q_u32(w + 60, msg3);\n+\tmsg0 = vsha1su0q_u32(msg0, msg1, msg2);\n+\n+\t/* Steps 52-55 */\n+\tQUAD(vsha1mq_u32, e1, e0, tmp1);\n+\ttmp1 = vaddq_u32(msg3, k3);\n+\tmsg0 = vsha1su1q_u32(msg0, msg3);\n+\tvst1q_u32(w + 64, msg0);\n+\tmsg1 = vsha1su0q_u32(msg1, msg2, msg3);\n+\n+\t/* Steps 56-59 */\n+\tQUAD(vsha1mq_u32, e0, e1, tmp0);\n+\ttmp0 = vaddq_u32(msg0, k3);\n+\tmsg1 = vsha1su1q_u32(msg1, msg0);\n+\tvst1q_u32(w + 68, msg1);\n+\tmsg2 = vsha1su0q_u32(msg2, msg3, msg0);\n+\n+\t/* The state at step 60, for recompression to start from. */\n+\tvst1q_u32(at_60, abcd);\n+\tat_60[4] = e1;\n+\n+\t/* Steps 60-63 */\n+\tQUAD(vsha1pq_u32, e1, e0, tmp1);\n+\ttmp1 = vaddq_u32(msg1, k3);\n+\tmsg2 = vsha1su1q_u32(msg2, msg1);\n+\tvst1q_u32(w + 72, msg2);\n+\tmsg3 = vsha1su0q_u32(msg3, msg0, msg1);\n+\n+\t/* And at step 64. */\n+\tvst1q_u32(at_64, abcd);\n+\tat_64[4] = e0;\n+\n+\t/* Steps 64-67 */\n+\tQUAD(vsha1pq_u32, e0, e1, tmp0);\n+\ttmp0 = vaddq_u32(msg2, k3);\n+\tmsg3 = vsha1su1q_u32(msg3, msg2);\n+\tvst1q_u32(w + 76, msg3);\n+\n+\t/* Steps 68-71 */\n+\tQUAD(vsha1pq_u32, e1, e0, tmp1);\n+\ttmp1 = vaddq_u32(msg3, k3);\n+\n+\t/* Steps 72-75 */\n+\tQUAD(vsha1pq_u32, e0, e1, tmp0);\n+\n+\t/* Steps 76-79 */\n+\tQUAD(vsha1pq_u32, e1, e0, tmp1);\n+\n+\tvst1q_u32(ihv, vaddq_u32(abcd_in, abcd));\n+\tihv[4] = e0 + e_in;\n+}\n+\n+/* Four steps of the partner block, on schedule group `g`. */\n+#define GROUP(f, k, g) \\\n+\tdo { \\\n+\t\tuint32x4_t wk_ = vaddq_u32(veorq_u32(vld1q_u32(m1 + 4 * (g)), \\\n+\t\t\t\t\t\t     vld1q_u32(dm + 4 * (g))), \\\n+\t\t\t\t\t   vdupq_n_u32(k)); \\\n+\t\tuint32_t next_ = vsha1h_u32(vgetq_lane_u32(abcd, 0)); \\\n+\t\tabcd = f(abcd, e, wk_); \\\n+\t\te = next_; \\\n+\t} while (0)\n+\n+/*\n+ * Whether the partner block, whose state at `from` is `state`, ends on\n+ * `ihv_out`: out from its state at step 60 or 64 to step 80, then in from\n+ * the chaining value that implies, which must arrive back at that state.\n+ */\n+SHA1DC_TARGET_ARMV8\n+int sha1dc_recompress_armv8(enum sha1dc_from from, const uint32_t m1[80],\n+\t\t\t    const uint32_t dm[80], const uint32_t state[5],\n+\t\t\t    const uint32_t ihv_out[5])\n+{\n+\tuint32_t at[5], reached[5], e;\n+\tuint32x4_t abcd;\n+\n+\tsha1dc_partner_boundary(from, m1, dm, state, at);\n+\tabcd = vld1q_u32(at);\n+\te = at[4];\n+\n+\t/* Out to step 80, from 60 or from 64. */\n+\tif (from == SHA1DC_FROM_58)\n+\t\tGROUP(vsha1pq_u32, K3, 15);\n+\tGROUP(vsha1pq_u32, K3, 16);\n+\tGROUP(vsha1pq_u32, K3, 17);\n+\tGROUP(vsha1pq_u32, K3, 18);\n+\tGROUP(vsha1pq_u32, K3, 19);\n+\n+\t/* The only input that gives this output is the output less the state. */\n+\tabcd = vsubq_u32(vld1q_u32(ihv_out), abcd);\n+\te = ihv_out[4] - e;\n+\n+\t/* In from there, as far as the state the way out started from. */\n+\tGROUP(vsha1cq_u32, K0, 0);\n+\tGROUP(vsha1cq_u32, K0, 1);\n+\tGROUP(vsha1cq_u32, K0, 2);\n+\tGROUP(vsha1cq_u32, K0, 3);\n+\tGROUP(vsha1cq_u32, K0, 4);\n+\tGROUP(vsha1pq_u32, K1, 5);\n+\tGROUP(vsha1pq_u32, K1, 6);\n+\tGROUP(vsha1pq_u32, K1, 7);\n+\tGROUP(vsha1pq_u32, K1, 8);\n+\tGROUP(vsha1pq_u32, K1, 9);\n+\tGROUP(vsha1mq_u32, K2, 10);\n+\tGROUP(vsha1mq_u32, K2, 11);\n+\tGROUP(vsha1mq_u32, K2, 12);\n+\tGROUP(vsha1mq_u32, K2, 13);\n+\tGROUP(vsha1mq_u32, K2, 14);\n+\tif (from == SHA1DC_FROM_65)\n+\t\tGROUP(vsha1pq_u32, K3, 15);\n+\n+\tvst1q_u32(reached, abcd);\n+\treached[4] = e;\n+\treturn !memcmp(reached, at, sizeof(at));\n+}\n+\n+#endif /* SHA1DC_HAVE_ARMV8 */\ndiff --git a/sha1dc-accel/internal.h b/sha1dc-accel/internal.h\nindex a27fda19d1..a50b294b96 100644\n--- a/sha1dc-accel/internal.h\n+++ b/sha1dc-accel/internal.h\n@@ -27,6 +27,21 @@\n # elif defined(__aarch64__) && defined(__ARM_NEON)\n #  define SHA1DC_HAVE_NEON 1\n #  include <arm_neon.h>\n+/*\n+ * The SHA-1 instructions, where the compiler targets them already or can\n+ * enable them for one function: older compilers declare their intrinsics\n+ * only when the whole file targets them.\n+ */\n+#  if defined(__ARM_FEATURE_SHA2) || defined(__ARM_FEATURE_CRYPTO)\n+#   define SHA1DC_HAVE_ARMV8 1\n+#   define SHA1DC_TARGET_ARMV8\n+#  elif defined(__clang__) && __clang_major__ >= 17\n+#   define SHA1DC_HAVE_ARMV8 1\n+#   define SHA1DC_TARGET_ARMV8 __attribute__((target(\"sha2\")))\n+#  elif !defined(__clang__) && __GNUC__ >= 9\n+#   define SHA1DC_HAVE_ARMV8 1\n+#   define SHA1DC_TARGET_ARMV8 __attribute__((target(\"+crypto\")))\n+#  endif\n # endif\n #endif\n \n@@ -83,11 +98,11 @@ void sha1dc_partner_boundary(enum sha1dc_from from, const uint32_t m1[80],\n \t\t\t     uint32_t out[5]);\n \n /*\n- * The hardware compression. It compresses one 64-byte block into `ihv`,\n+ * The hardware compressions. Each compresses one 64-byte block into `ihv`,\n  * writes the expanded schedule to `w`, and this block's own states at\n  * steps 60 and 64 to `at_60` and `at_64`.\n  *\n- * Its recompression answers whether a DV candidate is really an attack,\n+ * Their recompressions answer whether a DV candidate is really an attack,\n  * running the partner block forwards from `state` (this block's state at\n  * `from`) with the SHA-1 instructions.\n  */\n@@ -99,4 +114,13 @@ int sha1dc_recompress_shani(enum sha1dc_from from, const uint32_t m1[80],\n \t\t\t    const uint32_t dm[80], const uint32_t state[5],\n \t\t\t    const uint32_t ihv_out[5]);\n #endif\n+#ifdef SHA1DC_HAVE_ARMV8\n+int sha1dc_armv8_available(void);\n+void sha1dc_compress_armv8(uint32_t ihv[5], const unsigned char *block,\n+\t\t\t   uint32_t w[80], uint32_t at_60[5], uint32_t at_64[5]);\n+int sha1dc_recompress_armv8(enum sha1dc_from from, const uint32_t m1[80],\n+\t\t\t    const uint32_t dm[80], const uint32_t state[5],\n+\t\t\t    const uint32_t ihv_out[5]);\n+#endif\n+\n #endif /* SHA1DC_ACCEL_INTERNAL_H */\ndiff --git a/sha1dc-accel/sha1.c b/sha1dc-accel/sha1.c\nindex 2f30b207db..1f1133169b 100644\n--- a/sha1dc-accel/sha1.c\n+++ b/sha1dc-accel/sha1.c\n@@ -8,7 +8,7 @@\n  * Sam Reis (https://github.com/srijs/sha1dc), which gitoxide uses:\n  *\n  *  - The compression runs on the CPU's SHA-1 instructions where it has them\n- *    (SHA-NI on x86-64), and\n+ *    (SHA-NI on x86-64, the ARMv8 cryptography extension on arm64), and\n  *    spills the expanded message schedule as it goes, which is all that\n  *    detection needs from an ordinary block. The hardware keeps no\n  *    intermediate states around, so the two states that recompression\n@@ -264,6 +264,10 @@ static const struct backend backends[] = {\n \t{ \"shani+sse2\", sha1dc_compress_shani, 1, sha1dc_ubc_check_sse2,\n \t  sha1dc_recompress_shani, sha1dc_shani_available },\n #endif\n+#ifdef SHA1DC_HAVE_ARMV8\n+\t{ \"armv8+neon\", sha1dc_compress_armv8, 1, sha1dc_ubc_check_neon,\n+\t  sha1dc_recompress_armv8, sha1dc_armv8_available },\n+#endif\n #ifdef SHA1DC_HAVE_AVX2\n \t{ \"portable+avx2\", compress_portable, 0, sha1dc_ubc_check_avx2, NULL,\n \t  sha1dc_avx2_available },\ndiff --git a/t/unit-tests/u-sha1dc.c b/t/unit-tests/u-sha1dc.c\nindex 5948466cb9..f629f59d1d 100644\n--- a/t/unit-tests/u-sha1dc.c\n+++ b/t/unit-tests/u-sha1dc.c\n@@ -197,7 +197,7 @@ static void ubc_forms_agree_with_sha1dc(void)\n \t}\n }\n \n-#ifdef SHA1DC_HAVE_SHANI\n+#if defined(SHA1DC_HAVE_SHANI) || defined(SHA1DC_HAVE_ARMV8)\n \n static uint32_t rol(uint32_t x, int n)\n {\n@@ -325,6 +325,13 @@ static void hardware_compression(void)\n \t\tcheck_recompress(sha1dc_recompress_shani);\n \t\ttested = 1;\n \t}\n+#endif\n+#ifdef SHA1DC_HAVE_ARMV8\n+\tif (sha1dc_armv8_available()) {\n+\t\tcheck_compress(sha1dc_compress_armv8);\n+\t\tcheck_recompress(sha1dc_recompress_armv8);\n+\t\ttested = 1;\n+\t}\n #endif\n \tif (!tested)\n \t\tcl_skip();\n-- \n2.50.1 (Apple Git-155)\n\n\n"}]}