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

253 views
Skip to first unread message

alec.… via monorail

unread,
Aug 23, 2022, 8:08:38 AMAug 23
to webp-d...@webmproject.org
Status: New
Owner: ----
Labels: Type-Defect Priority-Medium

New issue 581 by alec....@gmail.com: Undocumented Constraint on Huffman Coding for VP8L
https://bugs.chromium.org/p/webp/issues/detail?id=581

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:
524946461e000000574542505650384c110000002f02000000e87f01cd266c9a48daff882c00

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:
524946461e000000574542505650384c110000002f02000000e87f01cd266c1a4adab6ff1159

--
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:
https://bugs.chromium.org/hosting/settings

jz… via monorail

unread,
Aug 23, 2022, 9:26:01 PMAug 23
to webp-d...@webmproject.org
Reply all
Reply to author
Forward
0 new messages