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

[alec.… via monorail]

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]

Updates:
Cc: jy...@google.com vra...@google.com

Comment #1 on issue 581 by jz...@google.com: Undocumented Constraint on Huffman Coding for VP8L
https://bugs.chromium.org/p/webp/issues/detail?id=581#c1

Original thread:
https://groups.google.com/a/webmproject.org/g/webp-discuss/c/JLIYeMylo1g/m/Zptapz0KAgAJ

Jyrki, do you think a clarifying note should be added to the bitstream doc?
https://chromium.googlesource.com/webm/libwebp/+/7a0a9935ed5f2a91b788b4b5ee48e1b757a625a5/doc/webp-lossless-bitstream-spec.txt

[jy… via monorail]

Comment #3 on issue 581 by jy...@google.com: Undocumented Constraint on Huffman Coding for VP8L
https://bugs.chromium.org/p/webp/issues/detail?id=581#c3

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]

Comment #4 on issue 581 by vra...@google.com: Undocumented Constraint on Huffman Coding for VP8L
https://bugs.chromium.org/p/webp/issues/detail?id=581#c4

This is actually where the code asks for a balanced tree: https://chromium.googlesource.com/webm/libwebp/+/refs/heads/main/src/utils/huffman_utils.c#199
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]

Comment #5 on issue 581 by Git Watcher: Undocumented Constraint on Huffman Coding for VP8L
https://bugs.chromium.org/p/webp/issues/detail?id=581#c5

The following revision refers to this bug:
https://chromium.googlesource.com/webm/libwebp/+/428588ef905c70d6b158bad202a0f274dae7a904

commit 428588ef905c70d6b158bad202a0f274dae7a904
Author: Jyrki Alakuijala <jy...@google.com>
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

[modify] https://crrev.com/428588ef905c70d6b158bad202a0f274dae7a904/doc/webp-lossless-bitstream-spec.txt

[jz… via monorail]

Updates:
Owner: jz...@google.com
Status: Fixed

Comment #7 on issue 581 by jz...@google.com: Undocumented Constraint on Huffman Coding for VP8L
https://bugs.chromium.org/p/webp/issues/detail?id=581#c7

(No comment was entered for this change.)