commit 8e8000ef0e4b077ea707cf17e46d23b2695af928
parent 30873143c411b1f4c5fd73db6ecb79b0b0fb4c32
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Wed, 10 Jun 2026 19:05:02 -0700
perf: hardware SHA-256 + fused build-id hash; trim codegen type-query path
Linker: symbol-count was the only axis kit lost to ld64 (2.00x). For large
outputs the link was ~85% two full-image content hashes -- the mandatory macOS
codesig (SHA-256/page) and the LC_UUID/build-id (two byte-at-a-time FNV passes).
- src/core/sha256.c: ARMv8 crypto-extension block (sha256h/h2/su0/su1 inline
asm, no arm_neon.h so it survives -nostdinc), gated on __ARM_FEATURE_SHA2
(always set on Apple Silicon). Portable scalar fallback otherwise. Plus a
memcpy-free bulk update path. Bit-identical digest; ~5-8x throughput.
- src/link/link_image_id.c: fuse the two FNV-1a passes into one (each byte read
once, two multiply chains in parallel). Bit-identical, ~2x.
256k-symbol link 1.12s -> 0.46s; symbol-count 2.00x -> 0.89x clang (now faster
than ld64 across the axis).
Codegen: on body-size, cg_type_get was 9.6% self-time and memset 10%.
- type_cg_builtin fetched two structs by value per operand (the whole builtin
id table + the target spec) to read one field. New public
kit_cg_builtin_type_id() single-id accessor; target spec fetched lazily.
- cg_type_get: drop the redundant per-lookup cg_api_init_builtins and inline the
already-initialized cg_api_get fast path.
body-size ~2.36s -> ~2.06s (~13%); the type-query frames leave the top-10. Hot
path is now the lexer/pp token pump (documented next target).
Verified bit-identical: hash + 17-size kit-hash-vs-shasum differential across
block boundaries, link/macho/elf/dwarf/dist/tools/smoke/cg-api/toy/parse/opt/
isa/debug all green, end-to-end compile+link+run correct. doc/plan/PERF.md
Round 4.
Diffstat:
6 files changed, 309 insertions(+), 22 deletions(-)
diff --git a/doc/plan/PERF.md b/doc/plan/PERF.md
@@ -75,6 +75,69 @@ Quick wire-check: `KIT_CC_BENCH_SIZES='8 16 32' KIT_CC_BENCH_SAMPLE=0 make bench
## Findings
+### Round 4 — CPU work: linker output hashing + the codegen type-query path
+
+> 2026-06-10, M1, clang-built `PROFILE=1` kit. With memory + IO handled
+> (Rounds 2–3), the remaining cost is **CPU in the actual passes**. Profiling
+> the largest input of each axis (multi-second runs so `sample` captures a real
+> call graph) surfaced two concentrated hotspots.
+
+**Linker — `symbol-count` was the only axis kit lost to the system linker
+(2.00× ld64).** For a large output the link was ~85 % two full-image content
+hashes: `compute_codesig` (the mandatory macOS ad-hoc code signature — SHA-256
+over every 4 KB page) at ~58 %, and `link_image_id_compute` (the LC_UUID /
+build-id — **two** byte-at-a-time FNV-1a passes over the whole image) at ~27 %.
+kit hashed with a portable scalar SHA-256 while ld64 uses the ARMv8 crypto
+extension. Three fixes, all output-bit-identical:
+
+1. **Hardware SHA-256** (`src/core/sha256.c`). Added an ARMv8 crypto-extension
+ block (`sha256h`/`h2`/`su0`/`su1` inline asm, no `arm_neon.h` so it survives
+ the freestanding `-nostdinc` build) gated on `defined(__aarch64__) &&
+ defined(__ARM_FEATURE_SHA2)` — always set on Apple Silicon, so the macOS
+ linking host (the codesig consumer) is covered with zero runtime detection.
+ ~5–8× the scalar throughput; same digest. Linux/FreeBSD aarch64 could gain it
+ behind a HWCAP probe (deferred — keeps core free of platform detection).
+2. **memcpy-free `sha256_update`.** The old update staged every byte through a
+ 64-byte buffer; now full blocks are absorbed straight from the caller — a
+ whole pass over the data removed (helps every SHA user: codesig, CAS, pkg).
+3. **Fused FNV in `link_image_id_compute`.** One pass updating both 64-bit
+ streams (each byte read once, the two multiply chains issue in parallel)
+ instead of two passes — bit-identical, ~2× on that 27 %.
+
+Result: 256k-symbol link **1.12 s → 0.46 s**; benchmark `symbol-count`
+**2.00× → 0.89× clang** (per-symbol 3897 ns → 1472 ns), i.e. kit's linker is now
+faster than ld64 across the whole axis. The residual large-link top frame is the
+image-id FNV (now ~31 %, but only on pathologically large outputs); switching it
+to the hardware SHA would help further at the cost of changing UUID/build-id
+bytes — deferred.
+
+**Codegen — the type-query path.** On `body-size` (pure per-statement codegen),
+`cg_type_get` was 9.6 % self-time and `_platform_memset` 10 %. Two causes, both
+plumbing waste in the hot per-operand path:
+
+- `type_cg_builtin` (frontend type lowering) fetched **two structs by value per
+ call** — `kit_cg_builtin_types` builds + copies the whole ~15-entry id table,
+ `kit_compiler_target_spec` memset+copies the spec — to read one field. Added a
+ public `kit_cg_builtin_type_id(c, which)` single-id accessor and made the
+ target-spec fetch lazy (only the `long`/`long double` cases need it). Killed
+ the by-value-copy memsets (19 → 0 sampled, memset 10.2 % → 6.3 %).
+- `cg_type_get` called `cg_api_init_builtins` redundantly per lookup (cg_api_get
+ already guarantees init) and went through an un-inlined `cg_api_get` call;
+ inlined the already-initialized fast path (load + index, no call).
+
+Result: `body-size` **~2.36 s → ~2.06 s (~13 %)**; `cg_type_get`/`cg_api_get`
+fall out of the top-10. The hot frame is now the **lexer/pp token pump**
+(`lex_next`, `peek`, `pp_next_raw`) — in every compile's path and the clear next
+target (left untouched here: intricate, correctness-sensitive, diffuse gains).
+
+Verified: hash (24 checks + a 17-size `kit hash` vs `shasum` differential across
+every block boundary), link 124, macho 80, elf 41, dwarf, dist 182, tools 45,
+smoke-x64/rv64, cg-api, toy 1392, parse, opt, isa, debug — all green;
+compile+link+run end-to-end correct. (Pre-existing, unrelated:
+`test-driver-cc/cc-print-search-dirs-hosted` greps `<sysroot>/include` but the
+driver emits `<sysroot>/usr/include` for a Linux sysroot — untouched by this
+work.)
+
### Round 3 — bounded preprocessor memory (O(expansions) → O(depth))
> 2026-06-10. Round 2's note proposed a heap block free-list to kill the
diff --git a/include/kit/cg.h b/include/kit/cg.h
@@ -151,6 +151,11 @@ typedef struct KitCgRecordDesc {
* operations, comparisons, conversions, and ABI extension attributes. */
KIT_API KitCgBuiltinTypes kit_cg_builtin_types(KitCompiler*);
+/* Single builtin id. Equivalent to kit_cg_builtin_types(c).id[which] but
+ * without materializing (and copying by value) the whole table -- the hot
+ * type-lowering path queries one builtin at a time. */
+KIT_API KitCgTypeId kit_cg_builtin_type_id(KitCompiler*, KitCgBuiltinType which);
+
/* Interned structural types. Address space 0 is the normal target data
* address space. */
KIT_API KitCgTypeId kit_cg_type_func(KitCompiler*, KitCgFuncSig sig);
diff --git a/lang/c/type/type.c b/lang/c/type/type.c
@@ -512,44 +512,48 @@ int type_is_signed_integer(const Type* t) {
}
static KitCgTypeId type_cg_builtin(KitCompiler* c, TypeKind kind) {
- KitCgBuiltinTypes b = kit_cg_builtin_types(c);
- KitTargetSpec target = kit_compiler_target_spec(c);
+ /* Hot path: one builtin id per query, no whole-table copy. The target spec
+ * (a by-value struct) is only consulted for the two data-model-dependent
+ * widths, so it is fetched lazily inside those cases rather than per call. */
switch (kind) {
case TY_VOID:
- return b.id[KIT_CG_BUILTIN_VOID];
+ return kit_cg_builtin_type_id(c, KIT_CG_BUILTIN_VOID);
case TY_BOOL:
- return b.id[KIT_CG_BUILTIN_BOOL];
+ return kit_cg_builtin_type_id(c, KIT_CG_BUILTIN_BOOL);
case TY_CHAR:
case TY_SCHAR:
case TY_UCHAR:
- return b.id[KIT_CG_BUILTIN_I8];
+ return kit_cg_builtin_type_id(c, KIT_CG_BUILTIN_I8);
case TY_SHORT:
case TY_USHORT:
- return b.id[KIT_CG_BUILTIN_I16];
+ return kit_cg_builtin_type_id(c, KIT_CG_BUILTIN_I16);
case TY_INT:
case TY_UINT:
- return b.id[KIT_CG_BUILTIN_I32];
+ return kit_cg_builtin_type_id(c, KIT_CG_BUILTIN_I32);
case TY_LONG:
case TY_ULONG:
- return b.id[kit_target_uses_lp64(target) ? KIT_CG_BUILTIN_I64
- : KIT_CG_BUILTIN_I32];
+ return kit_cg_builtin_type_id(
+ c, kit_target_uses_lp64(kit_compiler_target_spec(c))
+ ? KIT_CG_BUILTIN_I64
+ : KIT_CG_BUILTIN_I32);
case TY_LLONG:
case TY_ULLONG:
- return b.id[KIT_CG_BUILTIN_I64];
+ return kit_cg_builtin_type_id(c, KIT_CG_BUILTIN_I64);
case TY_INT128:
case TY_UINT128:
- return b.id[KIT_CG_BUILTIN_I128];
+ return kit_cg_builtin_type_id(c, KIT_CG_BUILTIN_I128);
case TY_FLOAT:
- return b.id[KIT_CG_BUILTIN_F32];
+ return kit_cg_builtin_type_id(c, KIT_CG_BUILTIN_F32);
case TY_DOUBLE:
- return b.id[KIT_CG_BUILTIN_F64];
+ return kit_cg_builtin_type_id(c, KIT_CG_BUILTIN_F64);
case TY_LDOUBLE:
/* `long double` is IEEE-754 binary128 on targets that follow the quad
* psABI (RISC-V, aarch64-linux, wasm32); elsewhere it aliases `double`.
* See kit_target_long_double_is_binary128. */
- if (kit_target_long_double_is_binary128(target))
- return b.id[KIT_CG_BUILTIN_F128];
- return b.id[KIT_CG_BUILTIN_F64];
+ return kit_cg_builtin_type_id(
+ c, kit_target_long_double_is_binary128(kit_compiler_target_spec(c))
+ ? KIT_CG_BUILTIN_F128
+ : KIT_CG_BUILTIN_F64);
default:
break;
}
diff --git a/src/cg/type.c b/src/cg/type.c
@@ -186,9 +186,12 @@ const CgType* cg_type_get(Compiler* c, KitCgTypeId id) {
off = id & CG_API_TYPE_SEG_MASK;
if (seg == CG_API_TYPE_BUILTIN_SEG) {
if (off >= KIT_CG_BUILTIN_COUNT) return NULL;
- s = cg_api_get(c);
+ /* Fast path: the per-compiler state (with its builtin table) is created
+ * on first use and then stays put, so inline the already-initialized case
+ * -- the hot per-op type query becomes a load + index instead of a call
+ * into cg_api_get. cg_api_get still handles lazy first-time creation. */
+ s = c->cg_api ? (CgApiState*)c->cg_api : cg_api_get(c);
if (!s) return NULL;
- cg_api_init_builtins(c, s);
return &s->builtins[off];
}
e = api_type_from_id(c, id);
@@ -625,6 +628,12 @@ KitCgBuiltinTypes kit_cg_builtin_types(KitCompiler* c) {
return out;
}
+KitCgTypeId kit_cg_builtin_type_id(KitCompiler* c, KitCgBuiltinType which) {
+ (void)c;
+ if ((u32)which >= KIT_CG_BUILTIN_COUNT) return KIT_CG_TYPE_NONE;
+ return builtin_id(which);
+}
+
KitCgTypeId kit_cg_type_ptr(KitCompiler* c, KitCgTypeId pointee,
uint32_t address_space) {
KitCgTypeId id;
diff --git a/src/core/sha256.c b/src/core/sha256.c
@@ -2,6 +2,13 @@
#include <string.h>
+/* Use the AArch64 SHA-256 crypto extension when the compiler knows the host
+ * has it (always true on Apple Silicon). SHA256_K is shared: the scalar core
+ * indexes it and the hardware core loads round-key vectors from it. */
+#if defined(__aarch64__) && defined(__ARM_FEATURE_SHA2)
+#define SHA256_HW 1
+#endif
+
static const u32 SHA256_K[64] = {
0x428a2f98u, 0x71374491u, 0xb5c0fbcfu, 0xe9b5dba5u, 0x3956c25bu,
0x59f111f1u, 0x923f82a4u, 0xab1c5ed5u, 0xd807aa98u, 0x12835b01u,
@@ -17,7 +24,9 @@ static const u32 SHA256_K[64] = {
0x682e6ff3u, 0x748f82eeu, 0x78a5636fu, 0x84c87814u, 0x8cc70208u,
0x90befffau, 0xa4506cebu, 0xbef9a3f7u, 0xc67178f2u};
+#ifndef SHA256_HW
static u32 sha256_rotr32(u32 v, u32 n) { return (v >> n) | (v << (32 - n)); }
+#endif
void sha256_init(Sha256* s) {
s->h[0] = 0x6a09e667u;
@@ -32,6 +41,7 @@ void sha256_init(Sha256* s) {
s->total = 0;
}
+#ifndef SHA256_HW
static void sha256_block(Sha256* s, const u8* p) {
u32 w[64];
for (u32 i = 0; i < 16; ++i)
@@ -71,10 +81,182 @@ static void sha256_block(Sha256* s, const u8* p) {
s->h[6] += g;
s->h[7] += hh;
}
+#endif /* !SHA256_HW */
+
+/* Absorb `nblocks` complete 64-byte blocks starting at `p`.
+ *
+ * On AArch64 hosts that the compiler knows have the SHA-256 crypto extension
+ * (Apple Silicon always does), this dispatches to a vectorized inline-asm core
+ * that is ~5-8x the scalar throughput -- the same hardware path ld64 uses, and
+ * the reason kit's Mach-O code-signature hash (a SHA-256 over every output
+ * page) stops dominating large links. Output is identical to the scalar core;
+ * only the instruction selection differs. Other hosts (and AArch64 builds
+ * without the feature compiled in) use the portable block below. Linux/FreeBSD
+ * AArch64 could gain the same speedup behind a runtime HWCAP probe -- deferred
+ * to keep core free of platform feature-detection. */
+#ifdef SHA256_HW
+/* The fully unrolled 64-round asm template is one string literal past C99's
+ * 4095-char minimum; clang/gcc both accept it, so silence -Wpedantic here. */
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Woverlength-strings"
+static void sha256_blocks(Sha256* s, const u8* p, size_t nblocks) {
+ if (!nblocks) return;
+ __asm__ volatile(
+ "ld1 {v0.4s, v1.4s}, [%[st]] \n" /* ABCD / EFGH */
+ "1: \n"
+ "ld1 {v4.4s, v5.4s, v6.4s, v7.4s}, [%[d]], #64\n" /* MSG0..MSG3 */
+ "mov v2.16b, v0.16b \n" /* save ABCD */
+ "mov v3.16b, v1.16b \n" /* save EFGH */
+ "rev32 v4.16b, v4.16b \n"
+ "rev32 v5.16b, v5.16b \n"
+ "rev32 v6.16b, v6.16b \n"
+ "rev32 v7.16b, v7.16b \n"
+ "mov x8, %[k] \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v16.4s, v4.4s, v19.4s \n" /* TMP0 = M0+K0 */
+ /* rounds 0-3 */
+ "sha256su0 v4.4s, v5.4s \n"
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v17.4s, v5.4s, v19.4s \n"
+ "sha256h q0, q1, v16.4s \n"
+ "sha256h2 q1, q18, v16.4s \n"
+ "sha256su1 v4.4s, v6.4s, v7.4s \n"
+ /* rounds 4-7 */
+ "sha256su0 v5.4s, v6.4s \n"
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v16.4s, v6.4s, v19.4s \n"
+ "sha256h q0, q1, v17.4s \n"
+ "sha256h2 q1, q18, v17.4s \n"
+ "sha256su1 v5.4s, v7.4s, v4.4s \n"
+ /* rounds 8-11 */
+ "sha256su0 v6.4s, v7.4s \n"
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v17.4s, v7.4s, v19.4s \n"
+ "sha256h q0, q1, v16.4s \n"
+ "sha256h2 q1, q18, v16.4s \n"
+ "sha256su1 v6.4s, v4.4s, v5.4s \n"
+ /* rounds 12-15 */
+ "sha256su0 v7.4s, v4.4s \n"
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v16.4s, v4.4s, v19.4s \n"
+ "sha256h q0, q1, v17.4s \n"
+ "sha256h2 q1, q18, v17.4s \n"
+ "sha256su1 v7.4s, v5.4s, v6.4s \n"
+ /* rounds 16-19 */
+ "sha256su0 v4.4s, v5.4s \n"
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v17.4s, v5.4s, v19.4s \n"
+ "sha256h q0, q1, v16.4s \n"
+ "sha256h2 q1, q18, v16.4s \n"
+ "sha256su1 v4.4s, v6.4s, v7.4s \n"
+ /* rounds 20-23 */
+ "sha256su0 v5.4s, v6.4s \n"
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v16.4s, v6.4s, v19.4s \n"
+ "sha256h q0, q1, v17.4s \n"
+ "sha256h2 q1, q18, v17.4s \n"
+ "sha256su1 v5.4s, v7.4s, v4.4s \n"
+ /* rounds 24-27 */
+ "sha256su0 v6.4s, v7.4s \n"
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v17.4s, v7.4s, v19.4s \n"
+ "sha256h q0, q1, v16.4s \n"
+ "sha256h2 q1, q18, v16.4s \n"
+ "sha256su1 v6.4s, v4.4s, v5.4s \n"
+ /* rounds 28-31 */
+ "sha256su0 v7.4s, v4.4s \n"
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v16.4s, v4.4s, v19.4s \n"
+ "sha256h q0, q1, v17.4s \n"
+ "sha256h2 q1, q18, v17.4s \n"
+ "sha256su1 v7.4s, v5.4s, v6.4s \n"
+ /* rounds 32-35 */
+ "sha256su0 v4.4s, v5.4s \n"
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v17.4s, v5.4s, v19.4s \n"
+ "sha256h q0, q1, v16.4s \n"
+ "sha256h2 q1, q18, v16.4s \n"
+ "sha256su1 v4.4s, v6.4s, v7.4s \n"
+ /* rounds 36-39 */
+ "sha256su0 v5.4s, v6.4s \n"
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v16.4s, v6.4s, v19.4s \n"
+ "sha256h q0, q1, v17.4s \n"
+ "sha256h2 q1, q18, v17.4s \n"
+ "sha256su1 v5.4s, v7.4s, v4.4s \n"
+ /* rounds 40-43 */
+ "sha256su0 v6.4s, v7.4s \n"
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v17.4s, v7.4s, v19.4s \n"
+ "sha256h q0, q1, v16.4s \n"
+ "sha256h2 q1, q18, v16.4s \n"
+ "sha256su1 v6.4s, v4.4s, v5.4s \n"
+ /* rounds 44-47 */
+ "sha256su0 v7.4s, v4.4s \n"
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v16.4s, v4.4s, v19.4s \n"
+ "sha256h q0, q1, v17.4s \n"
+ "sha256h2 q1, q18, v17.4s \n"
+ "sha256su1 v7.4s, v5.4s, v6.4s \n"
+ /* rounds 48-51 (schedule complete) */
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v17.4s, v5.4s, v19.4s \n"
+ "sha256h q0, q1, v16.4s \n"
+ "sha256h2 q1, q18, v16.4s \n"
+ /* rounds 52-55 */
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v16.4s, v6.4s, v19.4s \n"
+ "sha256h q0, q1, v17.4s \n"
+ "sha256h2 q1, q18, v17.4s \n"
+ /* rounds 56-59 */
+ "mov v18.16b, v0.16b \n"
+ "ld1 {v19.4s}, [x8], #16 \n"
+ "add v17.4s, v7.4s, v19.4s \n"
+ "sha256h q0, q1, v16.4s \n"
+ "sha256h2 q1, q18, v16.4s \n"
+ /* rounds 60-63 */
+ "mov v18.16b, v0.16b \n"
+ "sha256h q0, q1, v17.4s \n"
+ "sha256h2 q1, q18, v17.4s \n"
+ /* fold block result back into running state */
+ "add v0.4s, v0.4s, v2.4s \n"
+ "add v1.4s, v1.4s, v3.4s \n"
+ "subs %[n], %[n], #1 \n"
+ "b.ne 1b \n"
+ "st1 {v0.4s, v1.4s}, [%[st]] \n"
+ : [d] "+r"(p), [n] "+r"(nblocks)
+ : [st] "r"(s->h), [k] "r"(SHA256_K)
+ : "x8", "v0", "v1", "v2", "v3", "v4", "v5", "v6", "v7", "v16", "v17",
+ "v18", "v19", "memory", "cc");
+}
+#pragma GCC diagnostic pop
+#else
+static void sha256_blocks(Sha256* s, const u8* p, size_t nblocks) {
+ while (nblocks--) {
+ sha256_block(s, p);
+ p += 64;
+ }
+}
+#endif
void sha256_update(Sha256* s, const u8* data, u32 n) {
s->total += n;
- while (n) {
+ /* Top off a partially filled block first. */
+ if (s->buflen) {
u32 take = 64u - s->buflen;
if (take > n) take = n;
memcpy(s->buf + s->buflen, data, take);
@@ -82,10 +264,24 @@ void sha256_update(Sha256* s, const u8* data, u32 n) {
data += take;
n -= take;
if (s->buflen == 64) {
- sha256_block(s, s->buf);
+ sha256_blocks(s, s->buf, 1);
s->buflen = 0;
}
}
+ /* Bulk: absorb full blocks straight from the caller's buffer -- no staging
+ * memcpy, which on a multi-MB hash (e.g. the Mach-O code signature) is a
+ * whole extra pass over the data avoided. */
+ if (n >= 64u) {
+ size_t nb = n >> 6;
+ sha256_blocks(s, data, nb);
+ data += nb * 64u;
+ n -= (u32)(nb * 64u);
+ }
+ /* Stash the sub-block tail. */
+ if (n) {
+ memcpy(s->buf + s->buflen, data, n);
+ s->buflen += n;
+ }
}
void sha256_final(Sha256* s, u8 out[SHA256_DIGEST_LEN]) {
diff --git a/src/link/link_image_id.c b/src/link/link_image_id.c
@@ -31,6 +31,7 @@ static u64 fnv1a64(const u8* data, size_t n, u64 seed) {
void link_image_id_compute(const LinkImage* img, u8 out[LINK_IMAGE_ID_BYTES]) {
const u64 SEED_LO = 0xcbf29ce484222325ull;
const u64 SEED_HI = 0x14650fb0739d0383ull;
+ const u64 PRIME = 0x100000001b3ull;
u64 lo = SEED_LO, hi = SEED_HI;
u32 i;
for (i = 0; i < img->nsegments; ++i) {
@@ -41,9 +42,18 @@ void link_image_id_compute(const LinkImage* img, u8 out[LINK_IMAGE_ID_BYTES]) {
lo = fnv1a64((const u8*)&fsz, sizeof fsz, lo);
hi = fnv1a64((const u8*)&vaddr, sizeof vaddr, hi);
hi = fnv1a64((const u8*)&fsz, sizeof fsz, hi);
+ /* Fold both digest streams over the segment bytes in a single pass: each
+ * byte is read once and the two independent multiply chains issue in
+ * parallel. Bit-for-bit identical to two separate fnv1a64() passes (the
+ * dominant cost for large images), but ~2x faster. */
if (img->segment_bytes[i] && fsz) {
- lo = fnv1a64(img->segment_bytes[i], (size_t)fsz, lo);
- hi = fnv1a64(img->segment_bytes[i], (size_t)fsz, hi);
+ const u8* data = img->segment_bytes[i];
+ size_t n = (size_t)fsz, j;
+ for (j = 0; j < n; ++j) {
+ u8 b = data[j];
+ lo = (lo ^ (u64)b) * PRIME;
+ hi = (hi ^ (u64)b) * PRIME;
+ }
}
}
for (i = 0; i < 8; ++i) out[i] = (u8)(lo >> (i * 8));
