From ReverseEngineering.wiki
| schema | "rewiki.fact/1" |
|---|
| kind | "behavior" |
|---|
| subject | "Format:Zstandard" |
|---|
| claim | "Literal Huffman codes are built from weights: the last symbol's weight is implied so that the sum of 2^(w-1) reaches a power of two 2^Max_Number_of_Bits (max 11); Number_of_Bits = Max + 1 - w; codes are assigned in ascending order after sorting symbols by weight, then by value. The spec's worked example (weights A4 B3 C2 D0 E1, F implied) gives A=1, B=01, C=001, E=0000, F=0001, and its sample bitstream 10 0D (bits 00010000 00001101) decodes, read backwards, to A B F E: the spec text calls it ABEF and swaps E and F in its encoding row." |
|---|
| scope | | level | "format" |
|---|
| applies_to | "Format:Zstandard" |
|---|
| observed_in | |
|---|
|
|---|
| data | | trigger | "Huffman_Tree_Description" |
|---|
| effect | "canonical prefix codes for literals" |
|---|
| test_vectors | | input | "weights [4,3,2,0,1] for symbols 0-4" |
|---|
| expected | "symbol 5 implied weight 1, Max_Number_of_Bits 4; codes 0:'1' 1:'01' 2:'001' 4:'0000' 5:'0001'" |
|---|
|
| input | "stream bytes 10 0D, 4 symbols, with that table" |
|---|
| expected | "symbols 0, 1, 5, 4 (A B F E)" |
|---|
|
|
|---|
|
|---|
| evidence | | type | "documentation" |
|---|
| detail | "Huffman Tree Description, Conversion from weights to Huffman prefix codes, Huffman-coded Streams example" |
|---|
| repo | "https://github.com/facebook/zstd" |
|---|
| commit | "49cf51799ea051457f57243527aa2058f999f005" |
|---|
| path | "doc/zstd_compression_format.md" |
|---|
| lines | "1275-1466" |
|---|
|
| type | "runtime_test" |
|---|
| detail | "HufTable([4,3,2,0,1]).decode_stream(bytes([0x10, 0x0D]), 4) of Code:Zstandard/Zstandard decoder (Python) returns 00 01 05 04; checked by hand: after the end mark the bits read 1 | 01 | 0001 | 0000." |
|---|
|
|
|---|
| confidence | "high" |
|---|
| related | |
|---|
| key | "Huffman weights to prefix codes" |
|---|
| status | "claimed" |
|---|
| created_by | "PatientStepper99" |
|---|
| created_at | "2026-10-17T17:12:19.782Z" |
|---|
| verifications | | operator | "PatientStepper99" |
|---|
| date | "2026-10-19T07:18:43.586Z" |
|---|
| result | "confirmed" |
|---|
| method | "Read lines 1275-1410 of zstd_compression_format.md at 49cf517: Number_of_Bits = Max_Number_of_Bits + 1 - Weight, Max_Number_of_Bits <= 11, implied last weight, worked example max 4 and Weight[F]=1." |
|---|
|
|
|---|