Zig 0.17.0-dev (Split by item)

Shortcut keys
?
Show these tips
S
Focus search field
Esc
Clear focus & close tips
U
Jump to source code
↑
Move up in search results
↓
Move down in search results
↵
Go to active search result
This is an example of documentation generated by ZigDoc, an alternative to Zig's built-in Auto Doc feature. See also examples in other modes/formats. The project being documented here (as the example) is the Zig standard library. Private Function

checkCompleteness

Private Function
std.compress.flate.Decompress.HuffmanDecoder.checkCompleteness
fn checkCompleteness(lens: []const u4) !void

Given the list of code lengths check that it represents a canonical Huffman code for n symbols.

Reference: https://github.com/madler/zlib/blob/5c42a230b7b468dff011f444161c0145b5efae59/contrib/puff/puff.c#L340

Params

  • lens: []const u4

File

compress/flate/Decompress.zig:742
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
        fn checkCompleteness(lens: []const u4) !void {
            if (alphabet_size == 286)
                if (lens[256] == 0) return error.MissingEndOfBlockCode;

            var count: [@as(usize, max_code_bits) + 1]u16 = @splat(0);
            var max: usize = 0;
            for (lens) |n| {
                if (n == 0) continue;
                if (n > max) max = n;
                count[n] += 1;
            }
            if (max == 0) // empty tree
                return;

            // check for an over-subscribed or incomplete set of lengths
            var left: usize = 1; // one possible code of zero length
            for (1..count.len) |len| {
                left <<= 1; // one more bit, double codes left
                if (count[len] > left)
                    return error.OversubscribedHuffmanTree;
                left -= count[len]; // deduct count from possible codes
            }
            if (left > 0) { // left > 0 means incomplete
                // incomplete code ok only for single length 1 code
                if (max_code_bits > 7 and max == count[0] + count[1]) return;
                return error.IncompleteHuffmanTree;
            }
        }