Conversation
WalkthroughRefactors Huffman tree construction to use local heap/depth arrays and inlined pqdownheap/pqremove, introduces a new static build_tree implementation, and reduces indirection in compress_block by using local pointers and a local sym_next variable. Changes
Sequence Diagram(s)sequenceDiagram
participant Deflater as deflate_state
participant Build as build_tree()
participant Heap as pqdownheap()/pqremove
participant Bitlen as gen_bitlen()
participant Codes as gen_codes()
Deflater->>Build: build_tree(desc)
Build->>Heap: init heap from non-zero freqs, ensure 2 nodes
loop combine nodes until single root
Build->>Heap: pqremove(depth,heap,tree,SMALLEST) twice
Heap-->>Build: two smallest nodes
Build->>Build: create parent node, set Freq/Dad/Depth
Build->>Heap: pqdownheap(depth,heap,heap_len,tree,k)
end
Build->>Bitlen: gen_bitlen(desc)
Bitlen-->>Build: populated bit lengths
Build->>Codes: gen_codes(desc)
Codes-->>Build: populated codes
Build-->>Deflater: desc->max_code
sequenceDiagram
participant Deflater as deflate_state
participant Compress as compress_block()
Deflater->>Compress: compress_block(...)
Compress->>Compress: bind local pointers and sym_next
loop for each symbol
Compress->>Compress: process symbol using local buffers and sym_next
end
Compress-->>Deflater: emitted compressed block
Estimated code review effort🎯 4 (Complex) | ⏱️ ~45–75 minutes Suggested labels
Suggested reviewers
Tip 🔌 Remote MCP (Model Context Protocol) integration is now available!Pro plan users can now connect to remote MCP servers from the Integrations page. Connect with popular remote MCPs such as Notion and Linear to add more context to your reviews and chats. ✨ Finishing Touches
🧪 Generate unit tests
Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out. 🪧 TipsChatThere are 3 ways to chat with CodeRabbit:
SupportNeed help? Create a ticket on our support page for assistance with any issues or questions. CodeRabbit Commands (Invoked using PR/Issue comments)Type Other keywords and placeholders
CodeRabbit Configuration File (
|
Codecov Report❌ Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## develop #1954 +/- ##
==========================================
Coverage ? 81.90%
==========================================
Files ? 162
Lines ? 13928
Branches ? 3122
==========================================
Hits ? 11408
Misses ? 1555
Partials ? 965 ☔ View full report in Codecov by Sentry. 🚀 New features to boost your workflow:
|
There was a problem hiding this comment.
Actionable comments posted: 0
🧹 Nitpick comments (3)
trees.c (3)
69-69: Make pqdownheap parameters const to express intent and help the compilerpqdownheap doesn't mutate depth or tree; marking them const documents intent, can enable better alias analysis, and prevents accidental writes later.
Apply:
- static inline void pqdownheap (unsigned char *depth, int *heap, const int heap_len, ct_data *tree, int k); + static inline void pqdownheap (const unsigned char *depth, int *heap, const int heap_len, const ct_data *tree, int k);And the definition:
-static inline void pqdownheap(unsigned char *depth, int *heap, const int heap_len, ct_data *tree, int k) { +static inline void pqdownheap(const unsigned char *depth, int *heap, const int heap_len, const ct_data *tree, int k) {Also applies to: 150-150
726-735: Minor micro-optimization/readability in byte-to-uint16 distance loadAvoid two post-increments when reading the 16-bit distance; compute then bump once. Same codegen on many compilers, slightly clearer in reviews.
- dist = sym_buf[sx++] & 0xff; - dist += (unsigned)(sym_buf[sx++] & 0xff) << 8; - lc = sym_buf[sx++]; + dist = (unsigned)sym_buf[sx] | ((unsigned)sym_buf[sx + 1] << 8); + sx += 2; + lc = sym_buf[sx++];
138-142: Makedepthan explicit parameter of thepqremovemacroTo avoid an implicit dependency on a free identifier, update the macro and its sole call site as follows:
• In trees.c (lines 138–142), change the macro signature:
-#define pqremove(s, heap, tree, top) { \ +#define pqremove(s, depth, heap, tree, top) { \ top = heap[SMALLEST]; \ heap[SMALLEST] = heap[s->heap_len--]; \ pqdownheap(depth, heap, s->heap_len, tree, SMALLEST); \ }• In trees.c (around line 237), update the call in build_tree():
- pqremove(s, heap, tree, n); /* n = node of least frequency */ + pqremove(s, depth, heap, tree, n); /* n = node of least frequency */No other
pqremoveinvocations were found.
📜 Review details
Configuration used: CodeRabbit UI
Review profile: CHILL
Plan: Pro
💡 Knowledge Base configuration:
- MCP integration is disabled by default for public repositories
- Jira integration is disabled by default for public repositories
- Linear integration is disabled by default for public repositories
You can enable these sources in your CodeRabbit configuration.
📒 Files selected for processing (1)
trees.c(6 hunks)
⏰ Context from checks skipped due to timeout of 90000ms. You can increase the timeout in your CodeRabbit configuration to a maximum of 15 minutes (900000ms). (40)
- GitHub Check: Windows MSVC 2022 v141 Win32
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: EL9 GCC S390X DFLTCC UBSAN
- GitHub Check: Ubuntu GCC ASAN
- GitHub Check: Windows MSVC 2022 v141 Win32
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: EL9 GCC S390X DFLTCC UBSAN
- GitHub Check: Ubuntu GCC ASAN
- GitHub Check: Windows MSVC 2022 v141 Win32
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: EL9 GCC S390X DFLTCC UBSAN
- GitHub Check: Ubuntu GCC ASAN
- GitHub Check: Windows MSVC 2022 v141 Win32
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: EL9 GCC S390X DFLTCC UBSAN
- GitHub Check: Ubuntu GCC ASAN
- GitHub Check: Windows MSVC 2022 v141 Win32
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: EL9 GCC S390X DFLTCC UBSAN
- GitHub Check: Ubuntu GCC ASAN
- GitHub Check: Windows MSVC 2022 v141 Win32
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: EL9 GCC S390X DFLTCC UBSAN
- GitHub Check: Ubuntu GCC ASAN
- GitHub Check: Windows MSVC 2022 v141 Win32
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: EL9 GCC S390X DFLTCC UBSAN
- GitHub Check: Ubuntu GCC ASAN
- GitHub Check: Windows MSVC 2022 v141 Win32
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: EL9 GCC S390X DFLTCC UBSAN
- GitHub Check: Ubuntu GCC ASAN
- GitHub Check: Windows MSVC 2022 v141 Win32
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: EL9 GCC S390X DFLTCC UBSAN
- GitHub Check: Ubuntu GCC ASAN
- GitHub Check: Windows MSVC 2022 v141 Win32
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: EL9 GCC S390X DFLTCC UBSAN
- GitHub Check: Ubuntu GCC ASAN
🔇 Additional comments (3)
trees.c (3)
156-173: pqdownheap rework looks correct and tighterHeapify-down logic is standard: picks smaller child, uses depth as tie-breaker, and performs a single placement write at the end. Using v as a cached root value and passing heap_len explicitly avoids repeated s->heap_len loads. Looks good.
183-268: build_tree refactor: semantics preserved with clearer data flowGood use of local pointers (depth/heap/tree) to reduce indirection. Forcing at least two non-zero codes, heap construction, combining two smallest nodes, and bookkeeping of heap_max match the canonical algorithm. gen_bitlen/gen_codes integration unchanged. Nice cleanup.
717-725: Good: reduce indirection in compress_block by caching sym_next and buffersCapturing sym_next and buffer pointers locally reduces repeated loads and enables the compiler to optimize the inner loop better. Aligned with the PR goal.
actual usage in the code. Could also help with cache locality.
There was a problem hiding this comment.
Actionable comments posted: 0
🧹 Nitpick comments (3)
trees.c (3)
69-69: Inline pqdownheap signature refactor looks good; consider const-qualifying read-only paramspqdownheap now operates on explicit depth/heap arrays. Since it only reads from depth and tree, you can const-qualify them to help the compiler and document intent.
Apply this diff:
- static inline void pqdownheap (unsigned char *depth, int *heap, const int heap_len, ct_data *tree, int k); + static inline void pqdownheap (const unsigned char *depth, int *heap, const int heap_len, const ct_data *tree, int k);
134-142: Wrap pqremove macro in do { } while (0) to behave as a single statementCurrent multi-statement macro can be used safely as a statement, but do-while(0) is a safer pattern in all contexts (if/else without braces, etc.).
-#define pqremove(s, depth, heap, tree, top) { \ - top = heap[SMALLEST]; \ - heap[SMALLEST] = heap[s->heap_len--]; \ - pqdownheap(depth, heap, s->heap_len, tree, SMALLEST); \ -} +#define pqremove(s, depth, heap, tree, top) do { \ + top = heap[SMALLEST]; \ + heap[SMALLEST] = heap[s->heap_len--]; \ + pqdownheap(depth, heap, s->heap_len, tree, SMALLEST); \ +} while (0)
150-174: pqdownheap inline implementation: logic matches canonical heapify; no regressions spotted
- Uses explicit heap_len and local v; comparisons and swaps are correct.
- Integration with smaller() tie-breaker remains unchanged.
Optional: mirror the header nitpick by const-qualifying depth/tree here too:
-static inline void pqdownheap(unsigned char *depth, int *heap, const int heap_len, ct_data *tree, int k) { +static inline void pqdownheap(const unsigned char *depth, int *heap, const int heap_len, const ct_data *tree, int k) {
📜 Review details
Configuration used: CodeRabbit UI
Review profile: CHILL
Plan: Pro
💡 Knowledge Base configuration:
- MCP integration is disabled by default for public repositories
- Jira integration is disabled by default for public repositories
- Linear integration is disabled by default for public repositories
You can enable these sources in your CodeRabbit configuration.
📒 Files selected for processing (1)
trees.c(6 hunks)
🧰 Additional context used
🧬 Code Graph Analysis (1)
trees.c (1)
deflate.h (5)
tree_desc_s(261-261)tree_desc_s(260-260)tree_desc_s(259-259)tree_desc_s(108-112)static_tree_desc_s(106-106)
⏰ Context from checks skipped due to timeout of 90000ms. You can increase the timeout in your CodeRabbit configuration to a maximum of 15 minutes (900000ms). (20)
- GitHub Check: Windows ClangCl Win64
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: Windows ClangCl Win64
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: Windows ClangCl Win64
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: Windows ClangCl Win64
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: Windows ClangCl Win64
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: Windows ClangCl Win64
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: Windows ClangCl Win64
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: Windows ClangCl Win64
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: Windows ClangCl Win64
- GitHub Check: Windows MSVC 2022 v140 Win64
- GitHub Check: Windows ClangCl Win64
- GitHub Check: Windows MSVC 2022 v140 Win64
🔇 Additional comments (5)
trees.c (5)
183-268: build_tree refactor: clear, localized, and faithful to original algorithm
- Using local pointers (depth, heap, tree) reduces indirection and is cache-friendly.
- Heap construction, forced minimal codes, combination loop, and bookkeeping match zlib’s classic approach.
- Properly updates desc->max_code and calls gen_bitlen/gen_codes.
No functional issues found.
560-583: LGTM: send_all_trees adopts the same bi_buf/bi_valid cachingConsistent with send_tree; storing back to s at the end is correct and avoids redundant field accesses within the emission loop.
717-749: compress_block: local aliases and bounded loop guard are solid micro-opts
- Capturing sym_next once avoids repeated loads and preserves the intended snapshot semantics.
- Local d_buf/l_buf or sym_buf aliases reduce indirection in the hot loop.
- The do-while with precheck keeps behavior identical for sym_next == 0.
Looks good.
69-69: Keep declaration and definition in sync if const-qualifying pqdownheapIf you adopt the const-qualification nitpick for the prototype (Line 69), ensure the definition (Line 150) is updated identically to avoid mismatched prototypes.
Also applies to: 150-150
476-521: send_code/send_bits updated with new parameters, no legacy calls remain
- Macros in trees_emit.h now define send_code(s, c, tree, bi_buf, bi_valid) and send_bits(s, t_val, t_len, bi_buf, bi_valid).
- No 3-argument send_code calls were found.
- The only send_bits usage in arch/s390/dfltcc_deflate.c already passes five arguments (state, value, length, bi_buf, bi_valid).
All call sites have been migrated to the new signatures.
|
The failures on macOS workflows seem to be caused by mismatch between gcc/clang version and Xcode version. Xcode 16 is currently oldest supported but some workflows try to use for example Xcode 15.2. |
Tested on Intel i7-11700K, AMD E450 and Rpi-5, all showing good speed results in multiple builds of different configs.
Deflatebench shows compression is 0.25 - 0.75% faster
compress_bench shows compression is 0.95% - 2.65% faster
i7-11700K:
Develop
PR
Summary by CodeRabbit
Refactor
Performance
Documentation