Skip to content

Commit e93e438

Browse files
authored
Merge pull request #2575 from DeusData/perf/sha256-hw
perf(sha256): compress blocks on ARMv8 SHA2 / x86 SHA-NI (#2441)
2 parents 72a2c0b + 3eeefa2 commit e93e438

3 files changed

Lines changed: 320 additions & 9 deletions

File tree

‎src/foundation/sha256.c‎

Lines changed: 245 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,49 @@
11
/* SHA-256 per FIPS 180-4. Straightforward reference implementation; validated
2-
* against the NIST test vectors in tests/test_cli.c. */
2+
* against the NIST test vectors in tests/test_cli.c.
3+
*
4+
* Block compression runs on the CPU's SHA-256 instructions when it has them
5+
* (ARMv8 SHA2, x86 SHA-NI), chosen once at runtime; the portable transform
6+
* below stays the fallback and the reference the tests compare against.
7+
* #2441: every process start fingerprints its own ~300 MB executable, and the
8+
* portable transform made that ~1.2 s of CPU — past the hook deadline. */
39

410
#include "foundation/sha256.h"
511
#include "foundation/secure_random.h"
612

13+
#include <stdatomic.h>
14+
#include <stdbool.h>
715
#include <string.h>
816

17+
/* The ARM path needs a way to ask the OS whether the CPU has SHA2; on any
18+
* other aarch64 OS the portable transform is used. */
19+
#if defined(__aarch64__) && (defined(__clang__) || defined(__GNUC__)) && \
20+
(defined(__APPLE__) || defined(__linux__) || defined(_WIN32))
21+
#define SHA256_HW_ARM 1
22+
#include <arm_neon.h>
23+
#if defined(__APPLE__)
24+
#include <sys/sysctl.h>
25+
#elif defined(__linux__)
26+
#include <sys/auxv.h>
27+
#ifndef HWCAP_SHA2
28+
#define HWCAP_SHA2 (1UL << 6)
29+
#endif
30+
#else
31+
#include <windows.h>
32+
#endif
33+
#if defined(__clang__)
34+
#define SHA256_ARM_TARGET __attribute__((target("sha2")))
35+
#else
36+
#define SHA256_ARM_TARGET __attribute__((target("+sha2")))
37+
#endif
38+
#elif defined(__x86_64__) && (defined(__clang__) || defined(__GNUC__))
39+
#define SHA256_HW_X86 1
40+
#include <cpuid.h>
41+
#include <immintrin.h>
42+
#define SHA256_X86_TARGET __attribute__((target("sha,sse4.1,ssse3")))
43+
#endif
44+
45+
enum { SHA256_BLOCK_BYTES = 64 };
46+
947
static const uint32_t K[64] = {
1048
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
1149
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
@@ -64,6 +102,181 @@ static void sha256_transform(cbm_sha256_ctx *c, const uint8_t *data) {
64102
c->state[7] += h;
65103
}
66104

105+
static void sha256_blocks_portable(cbm_sha256_ctx *c, const uint8_t *data, size_t blocks) {
106+
for (; blocks > 0; blocks--, data += SHA256_BLOCK_BYTES) {
107+
sha256_transform(c, data);
108+
}
109+
}
110+
111+
#if defined(SHA256_HW_ARM)
112+
/* ARMv8 SHA2: the state stays {a,b,c,d} / {e,f,g,h}; each SHA256H/H2 pair runs
113+
* four rounds, and SU0/SU1 extend the schedule four words at a time. */
114+
SHA256_ARM_TARGET static void sha256_blocks_arm(cbm_sha256_ctx *c, const uint8_t *data,
115+
size_t blocks) {
116+
uint32x4_t abcd = vld1q_u32(&c->state[0]);
117+
uint32x4_t efgh = vld1q_u32(&c->state[4]);
118+
for (; blocks > 0; blocks--, data += SHA256_BLOCK_BYTES) {
119+
uint32x4_t abcd_in = abcd;
120+
uint32x4_t efgh_in = efgh;
121+
uint32x4_t w[4];
122+
for (int i = 0; i < 4; i++) {
123+
w[i] = vreinterpretq_u32_u8(vrev32q_u8(vld1q_u8(data + i * 16)));
124+
}
125+
for (int i = 0; i < 16; i++) {
126+
uint32x4_t wk = vaddq_u32(w[i & 3], vld1q_u32(&K[i * 4]));
127+
uint32x4_t abcd_prev = abcd;
128+
abcd = vsha256hq_u32(abcd, efgh, wk);
129+
efgh = vsha256h2q_u32(efgh, abcd_prev, wk);
130+
if (i < 12) {
131+
w[i & 3] = vsha256su1q_u32(vsha256su0q_u32(w[i & 3], w[(i + 1) & 3]),
132+
w[(i + 2) & 3], w[(i + 3) & 3]);
133+
}
134+
}
135+
abcd = vaddq_u32(abcd, abcd_in);
136+
efgh = vaddq_u32(efgh, efgh_in);
137+
}
138+
vst1q_u32(&c->state[0], abcd);
139+
vst1q_u32(&c->state[4], efgh);
140+
}
141+
142+
static bool sha256_cpu_has_arm(void) {
143+
#if defined(__APPLE__)
144+
/* Present on every Apple arm64 CPU; the key itself exists since macOS 12. */
145+
int has = 0;
146+
size_t size = sizeof(has);
147+
return sysctlbyname("hw.optional.arm.FEAT_SHA256", &has, &size, NULL, 0) == 0 && has != 0;
148+
#elif defined(__linux__)
149+
return (getauxval(AT_HWCAP) & HWCAP_SHA2) != 0;
150+
#else
151+
return IsProcessorFeaturePresent(PF_ARM_V8_CRYPTO_INSTRUCTIONS_AVAILABLE) != 0;
152+
#endif
153+
}
154+
#endif
155+
156+
#if defined(SHA256_HW_X86)
157+
/* x86 SHA-NI: SHA256RNDS2 wants the state as {a,b,e,f} / {c,d,g,h}, so it is
158+
* shuffled in once per call and back out at the end. */
159+
SHA256_X86_TARGET static void sha256_blocks_x86(cbm_sha256_ctx *c, const uint8_t *data,
160+
size_t blocks) {
161+
const __m128i byteswap = _mm_set_epi64x(0x0c0d0e0f08090a0bULL, 0x0405060700010203ULL);
162+
__m128i dcba = _mm_shuffle_epi32(_mm_loadu_si128((const __m128i *)&c->state[0]), 0xB1);
163+
__m128i efgh = _mm_shuffle_epi32(_mm_loadu_si128((const __m128i *)&c->state[4]), 0x1B);
164+
__m128i abef = _mm_alignr_epi8(dcba, efgh, 8);
165+
__m128i cdgh = _mm_blend_epi16(efgh, dcba, 0xF0);
166+
for (; blocks > 0; blocks--, data += SHA256_BLOCK_BYTES) {
167+
__m128i abef_in = abef;
168+
__m128i cdgh_in = cdgh;
169+
__m128i w[4];
170+
for (int i = 0; i < 4; i++) {
171+
w[i] = _mm_shuffle_epi8(_mm_loadu_si128((const __m128i *)(data + i * 16)), byteswap);
172+
}
173+
for (int i = 0; i < 16; i++) {
174+
__m128i wk = _mm_add_epi32(w[i & 3], _mm_loadu_si128((const __m128i *)&K[i * 4]));
175+
cdgh = _mm_sha256rnds2_epu32(cdgh, abef, wk);
176+
abef = _mm_sha256rnds2_epu32(abef, cdgh, _mm_shuffle_epi32(wk, 0x0E));
177+
if (i < 12) {
178+
__m128i next = _mm_add_epi32(_mm_sha256msg1_epu32(w[i & 3], w[(i + 1) & 3]),
179+
_mm_alignr_epi8(w[(i + 3) & 3], w[(i + 2) & 3], 4));
180+
w[i & 3] = _mm_sha256msg2_epu32(next, w[(i + 3) & 3]);
181+
}
182+
}
183+
abef = _mm_add_epi32(abef, abef_in);
184+
cdgh = _mm_add_epi32(cdgh, cdgh_in);
185+
}
186+
__m128i feba = _mm_shuffle_epi32(abef, 0x1B);
187+
__m128i dchg = _mm_shuffle_epi32(cdgh, 0xB1);
188+
_mm_storeu_si128((__m128i *)&c->state[0], _mm_blend_epi16(feba, dchg, 0xF0));
189+
_mm_storeu_si128((__m128i *)&c->state[4], _mm_alignr_epi8(dchg, feba, 8));
190+
}
191+
192+
static bool sha256_cpu_has_x86(void) {
193+
unsigned int eax = 0;
194+
unsigned int ebx = 0;
195+
unsigned int ecx = 0;
196+
unsigned int edx = 0;
197+
if (!__get_cpuid(1, &eax, &ebx, &ecx, &edx)) {
198+
return false;
199+
}
200+
bool ssse3 = (ecx & (1U << 9)) != 0;
201+
bool sse41 = (ecx & (1U << 19)) != 0;
202+
if (!ssse3 || !sse41 || !__get_cpuid_count(7, 0, &eax, &ebx, &ecx, &edx)) {
203+
return false;
204+
}
205+
return (ebx & (1U << 29)) != 0; /* CPUID.(7,0):EBX.SHA */
206+
}
207+
#endif
208+
209+
typedef enum {
210+
SHA256_BACKEND_UNPROBED = 0,
211+
SHA256_BACKEND_PORTABLE,
212+
SHA256_BACKEND_ARM,
213+
SHA256_BACKEND_X86,
214+
} sha256_backend_t;
215+
216+
/* Probed once; every thread computes the same answer, so relaxed is enough. */
217+
static _Atomic int g_sha256_backend = SHA256_BACKEND_UNPROBED;
218+
static _Atomic bool g_sha256_force_portable = false;
219+
220+
static sha256_backend_t sha256_probe_backend(void) {
221+
#if defined(SHA256_HW_ARM)
222+
if (sha256_cpu_has_arm()) {
223+
return SHA256_BACKEND_ARM;
224+
}
225+
#elif defined(SHA256_HW_X86)
226+
if (sha256_cpu_has_x86()) {
227+
return SHA256_BACKEND_X86;
228+
}
229+
#endif
230+
return SHA256_BACKEND_PORTABLE;
231+
}
232+
233+
static sha256_backend_t sha256_backend(void) {
234+
if (atomic_load_explicit(&g_sha256_force_portable, memory_order_relaxed)) {
235+
return SHA256_BACKEND_PORTABLE;
236+
}
237+
int backend = atomic_load_explicit(&g_sha256_backend, memory_order_relaxed);
238+
if (backend == SHA256_BACKEND_UNPROBED) {
239+
backend = (int)sha256_probe_backend();
240+
atomic_store_explicit(&g_sha256_backend, backend, memory_order_relaxed);
241+
}
242+
return (sha256_backend_t)backend;
243+
}
244+
245+
static void sha256_blocks(cbm_sha256_ctx *c, const uint8_t *data, size_t blocks) {
246+
switch (sha256_backend()) {
247+
#if defined(SHA256_HW_ARM)
248+
case SHA256_BACKEND_ARM:
249+
sha256_blocks_arm(c, data, blocks);
250+
return;
251+
#endif
252+
#if defined(SHA256_HW_X86)
253+
case SHA256_BACKEND_X86:
254+
sha256_blocks_x86(c, data, blocks);
255+
return;
256+
#endif
257+
default:
258+
sha256_blocks_portable(c, data, blocks);
259+
return;
260+
}
261+
}
262+
263+
#if defined(CBM_ENABLE_TEST_SEAMS) && CBM_ENABLE_TEST_SEAMS
264+
const char *cbm_sha256_backend_name_for_testing(void) {
265+
switch (sha256_backend()) {
266+
case SHA256_BACKEND_ARM:
267+
return "arm-sha2";
268+
case SHA256_BACKEND_X86:
269+
return "x86-sha-ni";
270+
default:
271+
return "portable";
272+
}
273+
}
274+
275+
void cbm_sha256_force_portable_for_testing(bool force) {
276+
atomic_store_explicit(&g_sha256_force_portable, force, memory_order_relaxed);
277+
}
278+
#endif
279+
67280
void cbm_sha256_init(cbm_sha256_ctx *c) {
68281
c->bitlen = 0;
69282
c->buflen = 0;
@@ -78,14 +291,37 @@ void cbm_sha256_init(cbm_sha256_ctx *c) {
78291
}
79292

80293
void cbm_sha256_update(cbm_sha256_ctx *c, const void *data, size_t len) {
294+
if (len == 0) {
295+
return; /* data may be NULL when len is 0 */
296+
}
81297
const uint8_t *p = (const uint8_t *)data;
82-
for (size_t i = 0; i < len; i++) {
83-
c->buf[c->buflen++] = p[i];
84-
if (c->buflen == 64) {
85-
sha256_transform(c, c->buf);
86-
c->bitlen += 512;
87-
c->buflen = 0;
298+
if (c->buflen > 0) {
299+
size_t take = SHA256_BLOCK_BYTES - c->buflen;
300+
if (take > len) {
301+
take = len;
302+
}
303+
memcpy(c->buf + c->buflen, p, take);
304+
c->buflen += take;
305+
p += take;
306+
len -= take;
307+
if (c->buflen < SHA256_BLOCK_BYTES) {
308+
return;
88309
}
310+
sha256_blocks(c, c->buf, 1);
311+
c->bitlen += 512;
312+
c->buflen = 0;
313+
}
314+
/* Whole blocks straight from the input, without staging them in buf. */
315+
size_t blocks = len / SHA256_BLOCK_BYTES;
316+
if (blocks > 0) {
317+
sha256_blocks(c, p, blocks);
318+
c->bitlen += (uint64_t)blocks * 512;
319+
p += blocks * SHA256_BLOCK_BYTES;
320+
len -= blocks * SHA256_BLOCK_BYTES;
321+
}
322+
if (len > 0) {
323+
memcpy(c->buf, p, len);
324+
c->buflen = len;
89325
}
90326
}
91327

@@ -98,7 +334,7 @@ void cbm_sha256_final(cbm_sha256_ctx *c, uint8_t out[CBM_SHA256_DIGEST_LEN]) {
98334
while (i < 64) {
99335
c->buf[i++] = 0;
100336
}
101-
sha256_transform(c, c->buf);
337+
sha256_blocks(c, c->buf, 1);
102338
i = 0;
103339
}
104340
while (i < 56) {
@@ -108,7 +344,7 @@ void cbm_sha256_final(cbm_sha256_ctx *c, uint8_t out[CBM_SHA256_DIGEST_LEN]) {
108344
for (int j = 0; j < 8; j++) {
109345
c->buf[56 + j] = (uint8_t)(c->bitlen >> (56 - 8 * j));
110346
}
111-
sha256_transform(c, c->buf);
347+
sha256_blocks(c, c->buf, 1);
112348

113349
for (int j = 0; j < 8; j++) {
114350
out[j * 4] = (uint8_t)(c->state[j] >> 24);

‎src/foundation/sha256.h‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -41,4 +41,13 @@ void cbm_sha256_hex(const void *data, size_t len, char out[CBM_SHA256_HEX_LEN +
4141
void cbm_hmac_sha256(const void *key, size_t key_len, const void *data, size_t data_len,
4242
uint8_t out[CBM_SHA256_DIGEST_LEN]);
4343

44+
#if defined(CBM_ENABLE_TEST_SEAMS) && CBM_ENABLE_TEST_SEAMS
45+
#include <stdbool.h>
46+
/* The block backend in use: "arm-sha2", "x86-sha-ni" or "portable". */
47+
const char *cbm_sha256_backend_name_for_testing(void);
48+
/* Force the portable transform (true) or return to the probed backend (false),
49+
* so a test can hash the same input both ways. */
50+
void cbm_sha256_force_portable_for_testing(bool force);
51+
#endif
52+
4453
#endif /* CBM_SHA256_H */

‎tests/test_cli.c‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -17174,6 +17174,71 @@ TEST(cli_sha256_file_matches_known_vector) {
1717417174
PASS();
1717517175
}
1717617176

17177+
/* Hash `len` bytes fed in `chunk`-sized pieces (0 = one update) to hex. */
17178+
static void sha256_chunked_hex(const uint8_t *data, size_t len, size_t chunk,
17179+
char out[CBM_SHA256_HEX_LEN + 1]) {
17180+
static const char hex[] = "0123456789abcdef";
17181+
cbm_sha256_ctx ctx;
17182+
cbm_sha256_init(&ctx);
17183+
size_t step = chunk == 0 ? len : chunk;
17184+
for (size_t off = 0; off < len; off += step) {
17185+
cbm_sha256_update(&ctx, data + off, len - off < step ? len - off : step);
17186+
}
17187+
uint8_t digest[CBM_SHA256_DIGEST_LEN];
17188+
cbm_sha256_final(&ctx, digest);
17189+
for (int i = 0; i < CBM_SHA256_DIGEST_LEN; i++) {
17190+
out[i * 2] = hex[digest[i] >> 4];
17191+
out[i * 2 + 1] = hex[digest[i] & 0x0f];
17192+
}
17193+
out[CBM_SHA256_HEX_LEN] = '\0';
17194+
}
17195+
17196+
/* #2441: block compression runs on ARMv8 SHA2 / x86 SHA-NI when the CPU has
17197+
* them. The hardware path must agree with the portable transform bit for bit
17198+
* at every length around the block and padding boundaries, for every way the
17199+
* input is split across update calls, and on the NIST million-'a' vector that
17200+
* runs 15,625 blocks through it. */
17201+
TEST(cli_sha256_hardware_matches_portable_issue2441) {
17202+
enum { MAX_LEN = (1 << 20) + 13 };
17203+
uint8_t *data = malloc(MAX_LEN);
17204+
ASSERT_NOT_NULL(data);
17205+
uint32_t x = 0x2441u;
17206+
for (size_t i = 0; i < MAX_LEN; i++) {
17207+
x ^= x << 13;
17208+
x ^= x >> 17;
17209+
x ^= x << 5;
17210+
data[i] = (uint8_t)x;
17211+
}
17212+
static const size_t big[] = {4096, 65535, 65536, 65537, MAX_LEN};
17213+
static const size_t chunks[] = {0, 1, 3, 55, 63, 64, 65, 1000};
17214+
char hw[CBM_SHA256_HEX_LEN + 1];
17215+
char portable[CBM_SHA256_HEX_LEN + 1];
17216+
for (size_t n = 0; n < 300 + sizeof(big) / sizeof(big[0]); n++) {
17217+
size_t len = n < 300 ? n : big[n - 300];
17218+
for (size_t c = 0; c < sizeof(chunks) / sizeof(chunks[0]); c++) {
17219+
if (len > 70000 && chunks[c] != 0 && chunks[c] < 64) {
17220+
continue; /* byte-sized updates over 1 MiB add time, not coverage */
17221+
}
17222+
cbm_sha256_force_portable_for_testing(false);
17223+
sha256_chunked_hex(data, len, chunks[c], hw);
17224+
cbm_sha256_force_portable_for_testing(true);
17225+
sha256_chunked_hex(data, len, chunks[c], portable);
17226+
cbm_sha256_force_portable_for_testing(false);
17227+
ASSERT_STR_EQ(hw, portable);
17228+
}
17229+
}
17230+
memset(data, 'a', 1000000);
17231+
sha256_chunked_hex(data, 1000000, 0, hw);
17232+
ASSERT_STR_EQ(hw, "cdc76e5c9914fb9281a1c7e284d73e67f1809a48a497200e046d39ccc7112cd0");
17233+
free(data);
17234+
#if defined(__APPLE__) && defined(__aarch64__)
17235+
/* Every Apple arm64 CPU has the SHA2 extension: a portable answer here
17236+
* means the probe or dispatch broke, and startup is slow again. */
17237+
ASSERT_STR_EQ(cbm_sha256_backend_name_for_testing(), "arm-sha2");
17238+
#endif
17239+
PASS();
17240+
}
17241+
1717717242
/* #1544: v0.10.2 deleted the ui/standard chooser AND the flags that drove it,
1717817243
* so `update --ui` — a command people had in scripts and aliases — started
1717917244
* failing with "unknown update option". Retiring a choice is fine; breaking the
@@ -17669,6 +17734,7 @@ SUITE(cli) {
1766917734
RUN_TEST(cli_progress_sink_preserves_explicit_verbose_diagnostics);
1767017735
RUN_TEST(cli_progress_sink_serializes_concurrent_callbacks);
1767117736
RUN_TEST(cli_sha256_file_matches_known_vector);
17737+
RUN_TEST(cli_sha256_hardware_matches_portable_issue2441);
1767217738
RUN_TEST(cli_checksum_manifest_requires_exact_filename_and_accepts_star);
1767317739
RUN_TEST(cli_checksum_manifest_rejects_invalid_missing_and_conflicting_digest);
1767417740
RUN_TEST(cli_checksum_manifest_rejects_oversized_input);

0 commit comments

Comments
 (0)