Issue 581 in webp: Undocumented Constraint on Huffman Coding for VP8L

Skip to first unread message

alec.… via monorail

Aug 23, 2022, 8:08:38 AM8/23/22
Status: New
Owner: ----
Labels: Type-Defect Priority-Medium

New issue 581 by Undocumented Constraint on Huffman Coding for VP8L

What steps will reproduce the problem?
1. Construct a lossless (VP8L) Webp image such that one of the G, R, B, or A prefix codes consists of code lengths (2, 2, 3).
2. Try to decode the image.

What is the expected output? What do you see instead?

Based on the documentation, I expected this to be a valid normal prefix code. However, dwebp returns error code 3 (bitstream error).

What version of the product are you using? On what operating system?

I've mostly been using the latest Vivaldi browser (5.4.2753.37) to test this, but have confirmed it also affects dwebp from libwebp-1.2.4-windows-x64

Please provide any additional information below.

If you try decoding a stream of bits where the only difference is that instead of code lengths (2, 2, 3), you specify code lengths (2, 2, 3, 3, 3, 3), the image properly decodes, even though none of the color values specified by those additional codes are used in the image.

The problem seems to stem from dwebp requiring the code lengths to form a completely "balanced" canonical Huffman tree. That's why (2, 2, 3), which forms Canonical Huffman codes (00, 01, 100), is invalid, but (2, 2, 3, 3, 3, 3), which forms (00, 01, 100, 101, 110, 111), "balances" the tree by adding the remaining branches that start with "1".

Here's the complete hex code of a 3x1 pixel lossless Webp where the B component is specified by (2, 2, 3), so the image fails to decode:

And here's the exact same image, with the only difference being that the B component is specified by (2, 2, 3, 3, 3, 3), so the image successfully decodes:

You received this message because:
1. The project was configured to send all issue notifications to this address

You may adjust your notification preferences at:

jz… via monorail

Aug 23, 2022, 9:26:01 PM8/23/22

jy… via monorail

Mar 9, 2023, 8:04:22 AMMar 9

Comment #3 on issue 581 by Undocumented Constraint on Huffman Coding for VP8L

I am not aware of cases where webp lossless requires you to use unused code lenghts. I believe that adding extra codes is fully optional during the encoding process.

In the presented example of three codes we can choose code lengths of 1, 2, 2 instead of 2, 2, 3. That way no extra symbols need to be emitted.

vrab… via monorail

May 11, 2023, 10:24:23 AMMay 11

Comment #4 on issue 581 by Undocumented Constraint on Huffman Coding for VP8L

This is actually where the code asks for a balanced tree:
This was imported from an other project so it might not be necessary. The image can be decoded without this check.

Git Watcher via monorail

May 26, 2023, 2:59:36 PM (5 days ago) May 26

Comment #5 on issue 581 by Git Watcher: Undocumented Constraint on Huffman Coding for VP8L

The following revision refers to this bug:

commit 428588ef905c70d6b158bad202a0f274dae7a904
Author: Jyrki Alakuijala <>
Date: Thu May 25 14:13:38 2023

clarify single leaf node trees and use of canonical prefix coding

remove AMENDED-notes (the last functional spec change to match with the
implementation is from 2014, other amendments are clarifications)

Bug: webp:581
Change-Id: Ic47739be0fd5a975fd734d6813567ca615304f1d

Reply all
Reply to author
0 new messages