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 AMAug 23
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 PMAug 23
Reply all
Reply to author
0 new messages