Packing up to 3 consecutive literals into a single send_bits makes deflate 1% to 4.5% faster on
most data types, with byte-identical output and no regressions.
compress_block emits one symbol at a time. Each symbol ORs its Huffman code into the 64-bit bit
buffer at the running bit position, then updates that position. bi_buf/bi_valid are therefore a
loop-carried dependency: symbol N+1 cannot be placed until symbol N's length is known. That chain,
not table lookups or addressing, is what limits the emit loop.
Literals dominate most data and arrive in runs. Their codes are at most 15 bits, so three of them fit
in 45 bits, comfortably inside the 64-bit buffer. Packing a run of three into one send_bits removes
two of every three serial buffer updates.
Two restructurings were measured against the same baseline.
Reordering the accumulation inside zng_emit_dist (building the length and distance groups
independently, then merging with one shift and OR) does shorten the dependency chain in the emitted
assembly, from three serial ORs to two. It measured a wash, within 0.3%. It reorders work without
removing any, and zng_emit_dist is too small a slice of deflate for a one-cycle win to surface.
Batching literals across symbols removes buffer updates outright. That is the one that pays.
A negative result worth recording: writing the four match_bits terms separately and combining them
with a balanced OR tree changes nothing. OR is associative, so clang reassociates the tree straight
back into a serial chain and emits the same code. Only a structure with a non-associative shift
between the halves resists it.
compress_block is a small slice of deflate, which bounds the whole exercise:
| level | compress_block | longest_match |
|---|---|---|
| 3 | ~13% | 43% |
| 6 | ~4.5% | 62% |
| 9 | ~3.3% | 72% |
This is why the gains concentrate at level 3 and on literal-heavy data, and why text at level 6 is
flat. It is also why the zng_emit_dist reordering was undetectable.
Prototype against develop @ 05b270cc.
@@ -708,6 +708,12 @@ void Z_INTERNAL zng_tr_flush_block(deflate_state *s, unsigned char *buf, uint32_
/* ===========================================================================
* Send the block data compressed using the given Huffman trees
*/
+/* Maximum number of consecutive literals packed into a single send_bits. Bounded so
+ * MAX_LIT_BATCH * MAX_BITS stays within the 64-bit bit buffer. */
+#ifndef MAX_LIT_BATCH
+# define MAX_LIT_BATCH 3
+#endif
+
static void compress_block(deflate_state *s, const ct_data *ltree, const ct_data *dtree) {
/* ltree: literal tree */
/* dtree: distance tree */
@@ -745,7 +751,24 @@ static void compress_block(deflate_state *s, const ct_data *ltree, const ct_data
sx += 3;
#endif
if (dist == 0) {
+#if !defined(LIT_MEM) && OPTIMAL_CMP >= 32
+ /* Pack up to MAX_LIT_BATCH consecutive literals into a single send_bits
+ * to reduce the serial bit-buffer updates on literal runs. */
+ uint64_t bits = ltree[lc].Code;
+ uint32_t nbits = ltree[lc].Len;
+ for (unsigned n = 1; n < MAX_LIT_BATCH && sx + 3 <= sym_next; n++) {
+ uint32_t nval = Z_U32_FROM_LE(zng_memread_4(&sym_buf[sx]));
+ if ((nval & 0xffff) != 0)
+ break;
+ unsigned lc2 = (nval >> 16) & 0xff;
+ bits |= (uint64_t)ltree[lc2].Code << nbits;
+ nbits += ltree[lc2].Len;
+ sx += 3;
+ }
+ send_bits(s, bits, nbits, bi_buf, bi_valid);
+#else
zng_emit_lit(s, ltree, lc, &bi_buf, &bi_valid);
+#endif
} else {
zng_emit_dist(s, ltree, dtree, lc, dist, &bi_buf, &bi_valid);
} /* literal or match pair ? */Change in minimum CPU time versus develop, 1 MB inputs, batch size 3. Measured twice from
independent builds, the second with -falign-functions=64 -falign-loops=32, to rule out code layout
artifacts. Base and contender were interleaved round by round so both saw the same machine load;
minimum of 14 rounds is reported because it rejects scheduler noise best.
| data type | L3 default | L3 aligned | L6 default | L6 aligned |
|---|---|---|---|---|
| literals | -3.43% | -4.25% | -5.62% | -4.35% |
| realistic_rgb | -3.23% | -2.49% | -2.28% | -3.93% |
| mixed | -2.56% | -3.43% | -1.32% | -1.67% |
| short_match | -0.22% | -2.49% | -0.77% | -1.04% |
| text | -0.97% | -1.35% | +0.08% | +0.34% |
| dna | -1.07% | -0.43% | -0.33% | +0.29% |
| random | -0.75% | -0.62% | -1.00% | noisy |
Every emit-sensitive type reproduces across both builds, so the gains are real rather than layout
luck. random is incompressible and memcpy-bound rather than emit-bound, so it swings; striped_rgb
runs in 0.3 ms and is too short to measure, and is omitted.
On batch size: 2 captures about half the gain (literals at level 6 is -3.70% versus -5.62% at 3).
Size 4 lands within noise of 3, slightly better on mixed and image data but slightly worse on pure
literals, because 4 x 15 = 60 bits leaves only 3 bits of headroom and hits the send_bits split path
more often. Size 3 keeps a 19-bit margin and was chosen for that reason.
This paragraph is wrong. Size 4 is not a wash, and the split path is not why it looked like one. See the follow-up below.
Compressed output is byte-identical to develop across all 48 configurations (8 data types x 2 sizes
x levels 3, 6, 9), for batch sizes 2, 3 and 4. The packing identity was also fuzzed over 20 million
random field combinations. Builds are warning-free under -D WITH_MAINTAINER_WARNINGS=ON.
The prototype only wires the sym_buf path with OPTIMAL_CMP >= 32. The LIT_MEM and
byte-by-byte layouts need the same treatment before this is a real patch, so platforms using those
see no benefit yet.
- Apple M5, 4 performance + 6 efficiency cores, 32 GB
- macOS 26.5.2
- Apple clang 21.0.0 (clang-2100.1.1.101)
- CMake Release,
-D BUILD_SHARED_LIBS=OFF, separate build directory per variant - zlib-ng develop @ 05b270cc
Everything above was timed against full zng_deflate. That was a mistake, and it buried the result.
compress_block is about a tenth of deflate, and under the default strategy literals are only about a
quarter of the symbols. On text at level 6 there are 29,796 literal batches against 90,444
length/distance pairs. So anything done to the literal path is diluted roughly tenfold before it
reaches the stopwatch, and a real 5% win on compress_block reads as 0.08% on deflate, which is
indistinguishable from noise. That is exactly what happened to batch size 4.
Z_HUFFMAN_ONLY fixes the resolution. It skips match finding, so every symbol is a literal and
compress_block dominates: text at level 6 goes from 29,796 literal batches to 349,526, with zero
pairs. The same batch-3 patch that reads -1.32% on full deflate reads -12.99% there. Same code, ten
times the signal.
Measured against batch 3, under Z_HUFFMAN_ONLY, 1 MB inputs, minimum of 10 rounds with the run order
rotated so no variant is systematically first or last.
| data type | batch 4 | batch 4 + paired accumulate |
|---|---|---|
| text | -4.09% | -9.57% |
| dna | -3.48% | -8.74% |
| short_match | -5.50% | -6.95% |
| realistic_rgb | -0.38% | -5.53% |
| mixed | -0.48% | -2.36% |
| literals | +1.73% | +1.57% |
| mean | -2.03% | -5.26% |
Batching four literals instead of three is worth -2.03%. Doing it off a single masked load, instead of a per-symbol load and test each time round a loop, is worth a further -3.32% on top. Only pure literals regresses, slightly.
Careful with that second column: it changes two things at once against the first, the load/test consolidation and the paired accumulate, so it cannot attribute between them. Isolating the accumulate on its own — same masked load, same cascade, same dispatch, only the four-literal accumulate differing — the pairing is worth -0.54%, which is inside the noise. A second, independent isolation further down agrees at -0.56%. So essentially all of the -3.32% is the consolidated load, and next to none of it is the pairing.
A control comparing the same binary against itself, rotated the same way, spreads -0.65% to +0.84%, so these are clear of the noise floor. Output stays byte-identical to develop across three corpora, five strategies and ten levels.
The batch is built as two halves that do not depend on each other:
uint64_t pair0 = code0 | ((uint64_t)code1 << l0);
uint64_t pair1 = code2 | ((uint64_t)code3 << l2);
bits = pair0 | (pair1 << (l0 + l1));
nbits = l0 + l1 + l2 + l3;The two pairs really do accumulate in parallel, and the shift that merges them is not associative with
OR, which is what stops clang flattening the whole thing back into a serial chain. That is the
mechanism the original note guessed at when the balanced OR tree changed nothing: a plain tree gets
reassociated away, a shift between the halves does not. The assembly confirms all of it — four
independent table loads, pair0 and pair1 on separate shift/or chains, nbits summed as a balanced
add tree off the critical path, the merge shift intact.
And it buys almost nothing: -0.54% isolated, inside the noise. Look at why, in the emitted code. The
longest chain runs load, shift, or, merge-shift, merge-or — four deep — because the merge itself costs
both a shift and an or, handing back exactly the level the pairing won. pair0's own path is only
three. So the structure is parallel and the critical path is unchanged, which is what the isolation
measures.
That is worth recording as a prediction that was right, then wrongly retracted. The depth argument said up front that pairing four terms is pointless for precisely this reason. A confounded comparison then appeared to show -3.32% and the argument was dropped. The clean isolation vindicates it.
The same depth model gets the next question wrong, though, so it earns no credit. It also says the serial prepend used by the switch below — which shifts the accumulator every symbol, eight deep for four literals — should lose badly to the four-deep pairing. It ties, at -0.56%. Depth eight and depth four measure the same. The honest reading is that dependency depth is not a lever in this loop at all, in either direction, and the model happened to land on the right answer once.
The three following distance fields are tested with one masked load, since the 3-byte packing puts them at bits 0..15, 24..39 and 48..63 of a 64-bit little-endian load:
uint64_t v = Z_U64_FROM_LE(zng_memread_8(&sym_buf[sx]));
if ((v & 0xFFFF00FFFF00FFFFULL) == 0) {
/* four literals; lc3 is the byte at sx + 8, outside the load */
}Against PR #2365 @ 6cca401e, with the double-shift refinement to the secure shift applied.
-5.35% against batch 3 under Z_HUFFMAN_ONLY.
lit_run turns the masked word into a count: the dist fields start at bit 0, 24 and 48, so the lowest
set bit says which one broke the run and ctz/24 is the length. lit_prepend then builds the batch
backwards, each literal slotting in below what is already there, which is what lets a fallthrough
switch emit exactly the first k symbols by entering at case k. Every case body is identical, so there
is no duplication and no knob.
Three other shapes measure the same within noise — an if cascade over the masks, with either this
accumulate or a paired one, and a switch without fallthrough. They are all in the scoreboard near the
end. This one is kept because it is the leanest thing the compiler is handed: on x86-64, where there
are 16 general registers rather than 32, it is 196 instructions against the cascade's 215 and the
serial cascade's 227, with 8 stack references against 10 and 15. The serial accumulate spills bits
mid-loop there; this one keeps only tail and tbits live, briefly, and does not.
@@ -708,6 +708,25 @@ void Z_INTERNAL zng_tr_flush_block(deflate_state *s, unsigned char *buf, uint32_
/* ===========================================================================
* Send the block data compressed using the given Huffman trees
*/
+/* One 64-bit little-endian load at sx spans the next three symbols' dist fields
+ * (bits 0..15, 24..39, 48..63) and two of their literals (bits 16..23, 40..47). */
+#define LIT3_DIST_MASK 0xFFFF00FFFF00FFFFULL
+
+/* The dist fields start at bit 0, 24 and 48, so the lowest set bit of the masked word
+ * says which one broke the literal run: ctz/24 is the number of literals that follow,
+ * and no bits set at all means three. */
+Z_FORCEINLINE static unsigned lit_run(uint64_t v) {
+ uint64_t t = v & LIT3_DIST_MASK;
+ return t ? (unsigned)(zng_ctz64(t) / 24) : 3;
+}
+
+/* Prepend one literal below whatever tail already holds, so entering the switch at case k
+ * emits exactly the first k symbols in order. */
+Z_FORCEINLINE static void lit_prepend(const ct_data *ltree, unsigned lc, uint64_t *tail, uint32_t *tbits) {
+ *tail = (uint64_t)ltree[lc].Code | (*tail << ltree[lc].Len);
+ *tbits += ltree[lc].Len;
+}
+
static void compress_block(deflate_state *s, const ct_data *ltree, const ct_data *dtree) {
/* ltree: literal tree */
/* dtree: distance tree */
@@ -745,7 +764,37 @@ static void compress_block(deflate_state *s, const ct_data *ltree, const ct_data
sx += 3;
#endif
if (dist == 0) {
+#if !defined(LIT_MEM) && OPTIMAL_CMP >= 64
+ uint64_t bits = ltree[lc].Code;
+ uint32_t nbits = ltree[lc].Len;
+
+ if (sx + 9 <= sym_next) {
+ uint64_t v = Z_U64_FROM_LE(zng_memread_8(&sym_buf[sx]));
+ unsigned n = lit_run(v);
+ uint64_t tail = 0;
+ uint32_t tbits = 0;
+
+ switch (n) {
+ case 3:
+ lit_prepend(ltree, sym_buf[sx + 8], &tail, &tbits);
+ Z_FALLTHROUGH;
+ case 2:
+ lit_prepend(ltree, (v >> 40) & 0xff, &tail, &tbits);
+ Z_FALLTHROUGH;
+ case 1:
+ lit_prepend(ltree, (v >> 16) & 0xff, &tail, &tbits);
+ Z_FALLTHROUGH;
+ case 0:
+ break;
+ }
+ bits |= tail << nbits;
+ nbits += tbits;
+ sx += 3 * n;
+ }
+ send_bits(s, bits, nbits, bi_buf, bi_valid);
+#else
zng_emit_lit(s, ltree, lc, &bi_buf, &bi_valid);
+#endif
} else {
zng_emit_dist(s, ltree, dtree, lc, dist, &bi_buf, &bi_valid);
} /* literal or match pair ? */The guard is sx + 9 rather than sx + 8 because the fourth literal lives at byte sx + 8, outside
the 64-bit load. Runs shorter than four fall to the 3, 2 and 1 cases, and the last symbol or two of a
block fall through unbatched, which is nothing against a block of tens of thousands.
The explicit address arithmetic that appeared in the earlier version — a LIT_OFF macro shifting the
literal into a scaled byte offset, and a lit_code_len helper fetching Code and Len in one 32-bit
load — is gone. It measures as a wash against plain ltree[lc1].Code (-0.30%, inside the noise), so
there is no reason to pay for it in readability.
There is a caveat on this cleanup that the earlier version did not have: it is gated
OPTIMAL_CMP >= 64 rather than the original note's >= 32, because the masked test needs a 64-bit
load. Platforms below that fall back to the unbatched path.
Unrolling the batch loop. clang already fully unrolls it at -O2 on both arm64 and x86-64: the trip
count is at most two against a constant bound, so there is no back-edge and no counter in the emitted
code. gcc-15 at -O2 leaves it rolled, and #pragma GCC unroll 3 does remove the back-edge, but buys
nothing measurable.
The masked distance test at batch 3. Replacing the serial loop's per-symbol checks with a single masked test is 0.44% slower. Those tests were never the bottleneck — clang issues them as independent loads behind well-predicted branches, so collapsing them removes branches that cost nothing while adding a wider load and a 64-bit constant. The mask only earns its keep at batch 4, where it feeds the pairs.
Writing the address arithmetic by hand. Spelling out the scaled offset and the fused 32-bit
Code+Len load, rather than letting the compiler fold ltree[lc].Code, costs a further 0.21%.
A branchless flush. Storing eight bytes unconditionally and advancing by whole bytes only pays if
each send_bits carries enough bits to amortise the store. It does not: nbits averages 16 to 21 bits,
two to three bytes, and exceeds 32 bits in 0.0% of calls on every data type and level. It would roughly
triple the store count. It is unreachable by construction anyway — five literals average about 35 bits,
but the worst case of five 15-bit codes is 75 and overflows the buffer.
Three ideas in this note were argued down on dependency-chain grounds, and all three arguments were wrong. The wrong model was seductive enough to be worth writing down.
A switch with fallthrough looks like a natural fit. Build the batch backwards, prepending each literal below what is already there, and entering at case k emits exactly the first k symbols in order:
#define LIT_PREPEND(sym) do { \
unsigned lc_ = (sym); \
tail = (uint64_t)ltree[lc_].Code | (tail << ltree[lc_].Len); \
tbits += ltree[lc_].Len; \
} while (0)
switch (n) {
case 3: LIT_PREPEND(sym_buf[sx + 8]); Z_FALLTHROUGH;
case 2: LIT_PREPEND((v >> 40) & 0xff); Z_FALLTHROUGH;
case 1: LIT_PREPEND((v >> 16) & 0xff); Z_FALLTHROUGH;
case 0: break;
}
The prediction was that this has to lose, because prepending shifts the value you have already built, so every literal waits on the one before it. It did lose, by 9.71%. But not for that reason.
The count was the problem. Deriving n from three separate masked compares does all three, every
time. The dist fields sit at bits 0, 24 and 48, so the lowest set bit of the masked word already says
which one broke the run:
static inline unsigned lit_run(uint64_t v) {
uint64_t t = v & LIT3_DIST_MASK;
return t ? (unsigned)(zng_ctz64(t) / 24) : 3;
}
Swapping three compares for that one ctz recovers -8.10%, and the fallthrough version then ties the cascade — with the serial prepend chain still fully intact. So the chain costs approximately nothing. Replacing it with the paired accumulate on top buys another -0.56%, which is also nothing.
| variant | vs the cascade above |
|---|---|
| switch + fallthrough, three compares | +9.71% |
| switch + fallthrough, ctz count | +0.33% |
| switch + paired accumulate, ctz count | -0.24% |
Noise floor is +/-0.8%, so the last two are ties, not wins.
The rule that actually holds in this loop is not about dependency depth. It is: do less work on the
common path. The cascade's if / else if exits on the first test, and on literal-heavy data that first
test almost always hits. Anything computed unconditionally — a count, one extra masked test — is paid
on every symbol, and that is what shows up in the timings. The out-of-order engine has enough
independent work in flight to hide the chains that the depth argument frets about.
That also explains the masked-test result above, which otherwise looks like an anomaly: same disease. It computes a test unconditionally where the serial loop's first check exits immediately.
The if cascade is kept because nothing beats not computing the thing at all. The switch is a real
alternative rather than a mistake — its body is shorter and it carries no duplication — but it is not
faster, so it does not buy its way in.
The ctz-counted version is the diff at the top of this note, so it is not repeated here. It carries one
change from the shape shown above: LIT_PREPEND reached into tail, tbits and ltree from
enclosing scope, which is a rename away from breaking, so it became a Z_FORCEINLINE helper taking
them explicitly — the same pass-by-pointer shape zng_emit_lit already uses. That costs nothing: the
x86-64 output is one instruction shorter than the macro's and otherwise identical bar register
allocation.
zng_ctz64 reaches trees.c through deflate_p.h, and it asserts a non-zero input, which is why
lit_run keeps the t ? ... : 3 select rather than feeding it the empty word. The / 24 compiles to
a multiply and a shift on both targets — tzcntq plus imull $0x2b on x86-64 — never a divide.
PR #2365 removes branches from send_bits
independently of any of this. Batch 3 on top of it is -1.32% on full deflate and -12.99% under
Z_HUFFMAN_ONLY, so the two optimizations are independent and stack.
Batch 4 stays a wash against batch 3 even with the split-path branch gone, which is the direct evidence that the split path was never the reason size 4 underperformed. The measurement was.
Under the default strategy this is still about -0.08% on full deflate, because the literal path is a
minority of the symbols there. The win on compress_block is real, and so is the win for
Z_HUFFMAN_ONLY workloads and literal-heavy low levels. Sizing the real-world payoff needs a
deflatebench run over silesia at the default strategy, which has not been done.
Five shapes were built and measured against each other. The one kept is the diff at the top. Here are the rest, plus a scoreboard, so the whole set is in one place.
All five emit byte-identical output to develop across three corpora x five strategies x ten levels, and
build warning-free under -D WITH_MAINTAINER_WARNINGS=ON.
Runtime is Z_HUFFMAN_ONLY. Every variant was measured directly against the if cascade in its own
order-rotated run, so that is the baseline column here rather than the kept variant — chaining the
deltas together to re-base them would be arithmetic, not measurement. The x86-64 columns are static
objdump counts, not timings: nothing was run on x86 hardware.
| variant | dispatch | accumulate | vs if cascade |
x86 insns | x86 stack refs |
|---|---|---|---|---|---|
| switch + fallthrough, ctz (kept) | ctz count | serial prepend | +0.17% | 196 | 8 |
| switch, ctz count | ctz count | paired tree | -0.24% | 214 | 9 |
if cascade |
masks, exits first | paired tree | -- | 215 | 10 |
if cascade, serial accumulate |
masks, exits first | serial | +0.54% | 227 | 15 |
| switch + fallthrough, three compares | eager count | serial prepend | +9.71% | 198 | 6 |
Noise floor is +/-0.8%, so every runtime figure except the last is a tie. The one real result is the three-compares switch, and its cost is entirely the eager count. With the runtimes tied, the kept variant is chosen on x86 register pressure instead — which is a static argument, and wants confirming on an actual x86 box before it counts for much.
No count at all: three masked tests in order, exiting on the first hit. Ties on runtime, and the simplest thing to explain, but 215 x86 instructions against 196.
@@ -708,6 +708,11 @@ void Z_INTERNAL zng_tr_flush_block(deflate_state *s, unsigned char *buf, uint32_
/* ===========================================================================
* Send the block data compressed using the given Huffman trees
*/
+/* One 64-bit little-endian load at sx spans the next three symbols' dist fields
+ * (bits 0..15, 24..39, 48..63) and two of their literals (bits 16..23, 40..47). */
+#define LIT3_DIST_MASK 0xFFFF00FFFF00FFFFULL
+#define LIT2_DIST_MASK 0x000000FFFF00FFFFULL
+
static void compress_block(deflate_state *s, const ct_data *ltree, const ct_data *dtree) {
/* ltree: literal tree */
/* dtree: distance tree */
@@ -745,7 +750,43 @@ static void compress_block(deflate_state *s, const ct_data *ltree, const ct_data
sx += 3;
#endif
if (dist == 0) {
+#if !defined(LIT_MEM) && OPTIMAL_CMP >= 64
+ uint64_t bits = ltree[lc].Code;
+ uint32_t nbits = ltree[lc].Len;
+
+ if (sx + 9 <= sym_next) {
+ uint64_t v = Z_U64_FROM_LE(zng_memread_8(&sym_buf[sx]));
+ unsigned lc1 = (v >> 16) & 0xff;
+ unsigned lc2 = (v >> 40) & 0xff;
+
+ if ((v & LIT3_DIST_MASK) == 0) {
+ /* Four literals: two pairs built independently, merged with one shift,
+ * so the halves accumulate in parallel. */
+ unsigned lc3 = sym_buf[sx + 8];
+ uint32_t l0 = nbits;
+ uint32_t l1 = ltree[lc1].Len;
+ uint64_t pair0 = bits | ((uint64_t)ltree[lc1].Code << l0);
+ uint64_t pair1 = (uint64_t)ltree[lc2].Code
+ | ((uint64_t)ltree[lc3].Code << ltree[lc2].Len);
+ bits = pair0 | (pair1 << (l0 + l1));
+ nbits = l0 + l1 + ltree[lc2].Len + ltree[lc3].Len;
+ sx += 9;
+ } else if ((v & LIT2_DIST_MASK) == 0) {
+ bits |= (uint64_t)ltree[lc1].Code << nbits;
+ nbits += ltree[lc1].Len;
+ bits |= (uint64_t)ltree[lc2].Code << nbits;
+ nbits += ltree[lc2].Len;
+ sx += 6;
+ } else if ((v & 0xffff) == 0) {
+ bits |= (uint64_t)ltree[lc1].Code << nbits;
+ nbits += ltree[lc1].Len;
+ sx += 3;
+ }
+ }
+ send_bits(s, bits, nbits, bi_buf, bi_valid);
+#else
zng_emit_lit(s, ltree, lc, &bi_buf, &bi_valid);
+#endif
} else {
zng_emit_dist(s, ltree, dtree, lc, dist, &bi_buf, &bi_valid);
} /* literal or match pair ? */Identical to the primary diff except the four-literal accumulate, which keeps the plain
bits |= ... << nbits form instead of pairing. It is -0.54% behind, which is inside the noise, and its
four-literal case reads in the same shape as the three- and two-literal cases below it. A genuine
alternative on readability grounds.
@@ -708,6 +708,11 @@ void Z_INTERNAL zng_tr_flush_block(deflate_state *s, unsigned char *buf, uint32_
/* ===========================================================================
* Send the block data compressed using the given Huffman trees
*/
+/* One 64-bit little-endian load at sx spans the next three symbols' dist fields
+ * (bits 0..15, 24..39, 48..63) and two of their literals (bits 16..23, 40..47). */
+#define LIT3_DIST_MASK 0xFFFF00FFFF00FFFFULL
+#define LIT2_DIST_MASK 0x000000FFFF00FFFFULL
+
static void compress_block(deflate_state *s, const ct_data *ltree, const ct_data *dtree) {
/* ltree: literal tree */
/* dtree: distance tree */
@@ -745,7 +750,41 @@ static void compress_block(deflate_state *s, const ct_data *ltree, const ct_data
sx += 3;
#endif
if (dist == 0) {
+#if !defined(LIT_MEM) && OPTIMAL_CMP >= 64
+ uint64_t bits = ltree[lc].Code;
+ uint32_t nbits = ltree[lc].Len;
+
+ if (sx + 9 <= sym_next) {
+ uint64_t v = Z_U64_FROM_LE(zng_memread_8(&sym_buf[sx]));
+ unsigned lc1 = (v >> 16) & 0xff;
+ unsigned lc2 = (v >> 40) & 0xff;
+
+ if ((v & LIT3_DIST_MASK) == 0) {
+ /* Four literals, serial accumulate (the original form). */
+ unsigned lc3 = sym_buf[sx + 8];
+ bits |= (uint64_t)ltree[lc1].Code << nbits;
+ nbits += ltree[lc1].Len;
+ bits |= (uint64_t)ltree[lc2].Code << nbits;
+ nbits += ltree[lc2].Len;
+ bits |= (uint64_t)ltree[lc3].Code << nbits;
+ nbits += ltree[lc3].Len;
+ sx += 9;
+ } else if ((v & LIT2_DIST_MASK) == 0) {
+ bits |= (uint64_t)ltree[lc1].Code << nbits;
+ nbits += ltree[lc1].Len;
+ bits |= (uint64_t)ltree[lc2].Code << nbits;
+ nbits += ltree[lc2].Len;
+ sx += 6;
+ } else if ((v & 0xffff) == 0) {
+ bits |= (uint64_t)ltree[lc1].Code << nbits;
+ nbits += ltree[lc1].Len;
+ sx += 3;
+ }
+ }
+ send_bits(s, bits, nbits, bi_buf, bi_valid);
+#else
zng_emit_lit(s, ltree, lc, &bi_buf, &bi_valid);
+#endif
} else {
zng_emit_dist(s, ltree, dtree, lc, dist, &bi_buf, &bi_valid);
} /* literal or match pair ? */The other end of the design space: the count computed once by ctz, dispatched by a switch, with each case carrying its own accumulate. Nominally the fastest thing measured at -0.24%, which is a tie, and it duplicates the body across cases.
@@ -708,6 +708,18 @@ void Z_INTERNAL zng_tr_flush_block(deflate_state *s, unsigned char *buf, uint32_
/* ===========================================================================
* Send the block data compressed using the given Huffman trees
*/
+/* One 64-bit little-endian load at sx spans the next three symbols' dist fields
+ * (bits 0..15, 24..39, 48..63) and two of their literals (bits 16..23, 40..47). */
+#define LIT3_DIST_MASK 0xFFFF00FFFF00FFFFULL
+
+/* The dist fields start at bit 0, 24 and 48, so the lowest set bit of the masked word
+ * says which one broke the literal run: ctz/24 is the number of literals that follow,
+ * and no bits set at all means three. */
+static inline unsigned lit_run(uint64_t v) {
+ uint64_t t = v & LIT3_DIST_MASK;
+ return t ? (unsigned)(zng_ctz64(t) / 24) : 3;
+}
+
static void compress_block(deflate_state *s, const ct_data *ltree, const ct_data *dtree) {
/* ltree: literal tree */
/* dtree: distance tree */
@@ -745,7 +757,49 @@ static void compress_block(deflate_state *s, const ct_data *ltree, const ct_data
sx += 3;
#endif
if (dist == 0) {
+#if !defined(LIT_MEM) && OPTIMAL_CMP >= 64
+ uint64_t bits = ltree[lc].Code;
+ uint32_t nbits = ltree[lc].Len;
+
+ if (sx + 9 <= sym_next) {
+ uint64_t v = Z_U64_FROM_LE(zng_memread_8(&sym_buf[sx]));
+ unsigned lc1 = (v >> 16) & 0xff;
+ unsigned lc2 = (v >> 40) & 0xff;
+
+ switch (lit_run(v)) {
+ case 3: {
+ /* Four literals: two pairs built independently, merged with one shift. */
+ unsigned lc3 = sym_buf[sx + 8];
+ uint32_t l0 = nbits;
+ uint32_t l1 = ltree[lc1].Len;
+ uint64_t pair0 = bits | ((uint64_t)ltree[lc1].Code << l0);
+ uint64_t pair1 = (uint64_t)ltree[lc2].Code
+ | ((uint64_t)ltree[lc3].Code << ltree[lc2].Len);
+ bits = pair0 | (pair1 << (l0 + l1));
+ nbits = l0 + l1 + ltree[lc2].Len + ltree[lc3].Len;
+ sx += 9;
+ break;
+ }
+ case 2:
+ bits |= (uint64_t)ltree[lc1].Code << nbits;
+ nbits += ltree[lc1].Len;
+ bits |= (uint64_t)ltree[lc2].Code << nbits;
+ nbits += ltree[lc2].Len;
+ sx += 6;
+ break;
+ case 1:
+ bits |= (uint64_t)ltree[lc1].Code << nbits;
+ nbits += ltree[lc1].Len;
+ sx += 3;
+ break;
+ default:
+ break;
+ }
+ }
+ send_bits(s, bits, nbits, bi_buf, bi_valid);
+#else
zng_emit_lit(s, ltree, lc, &bi_buf, &bi_valid);
+#endif
} else {
zng_emit_dist(s, ltree, dtree, lc, dist, &bi_buf, &bi_valid);
} /* literal or match pair ? */Same machine and toolchain as above. Variants built on PR #2365 @ 6cca401e with the double-shift refinement to the secure shift applied; earlier variants on develop @ 05b270cc.