nigeltao

Wuffs author here.

Congratulations to the Halide folks on wpd, their new decoder. The performance numbers are impressive. If wpd (a Rust library) works for you, great, you should use it!

But since Wuffs was mentioned, I'll just drop a few selling points for why you'd still consider Wuffs.

1. Wuffs' implementation is transpiled to C code (and that in-C-form is checked into the repository, as well as into the leaner google/wuffs-mirror-release-c Github repo). If your existing project is C/C++, not a Rust one, then it's very easy to add Wuffs as a dependency. It's like adding any other third-party C library. It's just not hand-written .c code. It's hand-written .wuffs code that gets transpiled to a single-file C library, as easy to integrate as the STB libraries but memory-safe.

1.a. Similarly, if you're a Python project, or Java, or whatever, if you can wrap C code, you can wrap the Wuffs library (in its C form) and still get in-process, memory-safe image decoding without having to add a new toolchain to your build process.

2. Wuffs is a zero-capability language. It's a language for writing (safe) libraries, that only compute. It's not a language for writing applications. The Wuffs language cannot open files or write to the network. It can't even dynamically allocate memory. That means that Wuffs code can operate under `SECCOMP_MODE_STRICT` sandbox that prohibits basically everything except reading from stdin and writing to stdout.

2.a. For out-of-process, extremely memory-safe image decoding, the example/convert-to-nia/convert-to-nia.c program in the Wuffs repository reads an image (JPEG, PNG, WebP, etc) on stdin and writes NIA (a trivial image format, similar to Farbfeld) on stdout. Even if you don't want to audit the Wuffs language and toolchain itself, the security review for that convert-to-nia program is also absolutely trivial, because one of the first things that the main function does is to self-impose a `SECCOMP_MODE_STRICT` sandbox.

3. Wuffs uses intrinsics for SIMD, like C/C++, but memory safety is enforced on all loads and stores. And the toolchain also enforces that Wuffs general code can't call into Wuffs AVX2-using code unless your cpuid is AVX2-capable. The memory safety story of all of that is a bit better than just "we do SIMD via assembly in unsafe blocks". Wuffs (the language) doesn't even have an "unsafe" keyword.

Wuffs author here.

We got a pull request (https://github.com/google/wuffs/pull/168) in February to add lossy WebP support. Lossless WebP (which in some sense is an entirely different format, just reusing the WebP "brand") has had a Wuffs implementation for a couple of years now.

Anyway, the PR included SIMD acceleration and performance was on par with libwebp (C code).

The PR's code was, as far as I could tell, somewhat or mostly AI assisted. While that's great in terms of features, I still have more confidence in hand-crafted code.

I have since been working to manually rewrite the PR. I'd also like to add animation support, and last month I landed some Wuffs tooling changes re animated PNG, to be better able to (as a comparison baseline) decode and test animated WebP.

A lot of that manual rewrite has been committed, but the SIMD parts haven't landed yet. So yes, for what's on the main branch (not the PR), performance is not as good as libwebp yet, but landing the SIMD parts should fix that.

> wuffs is not bit-identical to libwebp

That's news to me. PR 168 says it produces pixel-identical output to libwebp. And what's in the main branch aims to be pixel-identical, e.g. for YUV to RGB conversion, it implements libwebp's formulae, not libjpeg's formulae. Both use BT.601, but libwebp uses studio range and libjpeg uses full range.

Can you link to some example .webp images that are not bit-identical?

Hi, author here. Thanks for the "check your HTML" bug report.

Handsum is intrinsically 16x16. Decoding to 32x32 is a two step process:

1. Decode to 16x16. This is done by the Handsum library.

2. Upscale 2x. This is done by the caller of the Handsum library (or, for the Wasm demo, by the HTML renderer).

If you want 48x48 or 64x64, just raise the 2x, in step 2, to 3x or 4x.

> Russ Cox should make a C version of his code.

https://github.com/rsc/fpfmt/blob/main/bench/uscalec/ftoa.c

It's a great idea. Chromium uses Wuffs to parse GIF data from the untrusted network.

There's also a "wget some JSON and pipe that to what Wuffs calls example/jsonptr" example at https://nigeltao.github.io/blog/2020/jsonptr.html#sandboxing

The top-level README has a link called "Getting Started".

See https://github.com/google/wuffs/blob/main/doc/related-work.m...

> Kaitai Struct is in a similar space, generating safe parsers for multiple target programming languages from one declarative specification. Again, Wuffs differs in that it is a complete (and performant) end to end implementation, not just for the structured parts of a file format. Repeating a point in the previous paragraph, the difficulty in decoding the GIF format isn't in the regularly-expressible part of the format, it's in the LZW compression. Kaitai's GIF parser returns the compressed LZW data as an opaque blob.

Taking PNG as an example, Kaitai will tell you the image's metadata (including width and height) and that the compressed pixels are in the such-and-such part of the file. But unlike Wuffs, Kaitai doesn't actually decode the compressed pixels.

---

Wuffs' generated C code also doesn't need any capabilities, including the ability to malloc or free. Its example/mzcat program (equivalent to /bin/bzcat or /bin/zcat, for decoding BZIP2 or GZIP) self-imposes a SECCOMP_MODE_STRICT sandbox, which is so restrictive (and secure!) that it prohibits any syscalls other than read, write, _exit and sigreturn.

(I am the Wuffs author.)

I like my colleague Simon Morris's observation about software complexity:

> Software has a Peter Principle. If a piece of code is comprehensible, someone will extend it, so they can apply it to their own problem. If it’s incomprehensible, they’ll write their own code instead. Code tends to be extended to its level of incomprehensibility.

> Compressing QOI with something like LZ4 would generally outperform PNG.

https://github.com/nigeltao/qoir has some numbers comparing QOIR (which is QOI-inspired-with-LZ4) vs PNG.

QOIR has better decode speed and comparable compression ratio (depending on which PNG encoder you use).

QOIR's numbers are also roughly similar to ZPNG.

For Wuffs, top level declarations start with either pub or pri (and both keywords have the same width, in a monospace font).

    pub status "#blah"
    pub struct foo(etc etc)
    pri func foo.bar(etc etc)

Since code is also auto-formatted, you can do things like "show me a structural overview of a package's source code" with a simple grep:

    rg -N ^p   std/jpeg/*.wuffs

If you want just the exported API, change p to pub:

    rg -N ^pub std/jpeg/*.wuffs

Might be relevant to your interests:

https://nigeltao.github.io/blog/2022/gamma-aware-ordered-dit...

You might like JWCC, which literally stands for JSON With Commas and Comments.

https://nigeltao.github.io/blog/2021/json-with-commas-commen...

JWCC literally stands for JSON With Commas and Comments.

JWCC is also what Tailscale call HuJSON, as in "JSON for Humans", which as amusingly also what json5 claims to be.

https://github.com/tailscale/hujson

> I believe the standard does not specify what the intermediate progressive renderings should look like.

This is possibly getting too academic, but IIUC for a progressive JPEG, e.g. encoded by cjpeg to have 10 0xDA Start Of Scan markers, it's actually legitimate to post-process the file, truncating to fewer scans (but re-appending the 0xD9 End Of Image marker). The shorter file is still a valid JPEG, and so still relevant for discussing whether all decoders will render the same pixels.

I might be wrong about validity, though. It's been a while since I've studied the JPEG spec.

> all decoders will render the same pixels

Not true. Even just within libjpeg, there are three different IDCT implementations (jidctflt.c, jidctfst.c, jidctint.c) and they produce different pixels (it's a classic speed vs quality trade-off). It's spec-compliant to choose any of those.

A few years ago, in libjpeg-turbo, they changed the smoothing kernel used for decoding (incomplete) progressive JPEGs, from a 3x3 window to 5x5. This meant the decoder produced different pixels, but again, that's still valid:

https://github.com/libjpeg-turbo/libjpeg-turbo/commit/6d91e9...

You're right that Wuffs' memory-safety isn't relevant for this attack.

Still, Wuffs doesn't use autotools, and if you're pulling the library from the https://github.com/google/wuffs-mirror-release-c repository then that repo doesn't even contain any binary-data test files.

Yeah, it's just a coincidence (†), but I started working on Wuffs' LZMA and XZ decoders last December. It works well enough to decode the Linux source code tarball correctly (producing the same output as /usr/bin/xz).

    $ git clone --quiet --depth=1 https://github.com/google/wuffs.git
    $ gcc -O3 wuffs/example/mzcat/mzcat.c -o my-mzcat
    $ ./my-mzcat     < linux-6.8.2.tar.xz | sha256sum 
    d53c712611ea6cb5acaf6627a84d5226692ae90ce41ee599fcc3203e7f8aa359  -
    $ /usr/bin/xz -d < linux-6.8.2.tar.xz | sha256sum 
    d53c712611ea6cb5acaf6627a84d5226692ae90ce41ee599fcc3203e7f8aa359  -

(†) Also, I'm not "Jia Tan"! You're just going to have to trust me on both of those claims. :-/

Encoding is definitely in Wuffs' long term objectives (it's issue #2 and literally in its doc/roadmap.md file). It's just that decoding has been a higher priority. It's also a simpler problem. There's often only one valid decoding for any given input.

Decoding takes a compressed image file as input, which have complicated formats. Roughly speaking, encoding just takes a width x height x 4 pixel buffer, with very regular structure. It's much easier to hide something malicious in a complicated format.

Higher priority means that, when deciding whether to work on a Wuffs PNG encoder or a Wuffs JPEG decoder next, when neither existed at the time, I chose to have more decoders.

(I work at Google, and am the Wuffs author, but have nothing to do with Jpegli. Google is indeed a big company.)

Yeah, you're right. It's not as easy to write Wuffs code during the research phase, since you don't just have to write the code, you also have to help the compiler prove that the code is safe, and sometimes refactor the code to make that tractable.

Wuffs doesn't support global variables, but when I'm writing my own research phase code, sometimes I like to just tweak some global state (without checking the code in) just to get some experimental data: hey, how do the numbers change if I disable the blahblah phase when the such-and-such condition (best evaluated in some other part of the code) holds?

Also, part of Wuffs' safety story is that Wuffs code cannot make any syscalls at all, which implies that it cannot allocate or free memory, or call printf. Wuffs is a language for writing libraries, not whole programs, and the library caller (not callee) is responsible for e.g. allocating pixel buffers. That also makes it harder to use during the research phase.

When I wrote my jsonptr tool a few years ago, I noticed that some JSON libraries (in both C++ and Rust) don't even do "parse a string of decimal digits as a float64" properly. I don't mean that in the "0.3 isn't exactly representable; have 0.30000000000000004 instead" sense.

I mean that rapidjson (C++) parsed the string "0.99999999999999999" as the number 1.0000000000000003. Apart from just looking weird, it's a different float64 bit-pattern: 0x3FF0000000000000 vs 0x3FF0000000000001.

Similarly, serde-json (Rust) parsed "122.416294033786585" as 122.4162940337866. This isn't as obvious a difference, but the bit-patterns differ by one: 0x405E9AA48FBB2888 vs 0x405E9AA48FBB2889. Serde-json does have an "float_roundtrip" feature flag, but it's opt-in, not enabled by default.

For details, look for "rapidjson issue #1773" and "serde_json issue #707" at https://nigeltao.github.io/blog/2020/jsonptr.html

If you want commas and comments, another term to search for is JWCC, which literally stands for "JSON With Commas and Comments". HuJSON is another name for it.

> Isn't it fixed during the decoding process though?

For Wuffs' image decoding, it's flexible up until decode_image_config returns. It's fixed afterwards.

In practice, that works fine for BMP, GIF, JPEG and PNG (and I'm confident will work for WebP too). No in-situ dynamic allocation (with or without sugar) needed. Even though, for the libjpeg-turbo C code, `grep mem..alloc_ jd*.c | wc -l` shows more than 50 "allocation" call sites, Wuffs' JPEG decoder does just fine with just the one work buffer.

1024 is a loose but correct bound. That's what enough.c (or script/print-deflate-huff-table-size.go) says.

Stepping back, I'm not sure if I understand what you're saying. Perhaps we're just disagreeing on how "formal" (as in, part of a "formal verification" process) the enough.c program (or equivalent) needs to be?

---

As for dynamic memory allocation, Wuffs has a mechanism for the callee (Wuffs code) to tell the caller (C/C++ glue code) that it needs N bytes of "scratch space" or "work buffer", where N is dynamically dependent (e.g. dependent on the image dimensions in pixels).

It's not "dynamic memory allocation" in that Wuffs still doesn't malloc/new and free/delete per se. But it is dynamically (run time, not compile time) sized.

Grepping for "work buffer" or "workbuf" in Wuffs' example/ or std/ code (or SkWuffsCodec.cpp) should give some leads, if you want to study some code. The workbuf_len is often zero but, for Wuffs' std/jpeg and std/png, it is positive. Manage the work buffer in the same way as the pixel buffer: it's always caller-owned and callee-borrowed.

The logo is no longer shown because I think the tweet-screenshot is a more compelling introduction for people new to Wuffs.

I've written a WebP Lossy decoder in Go and I'm confident that I can write one in Wuffs too.

As an intellectual 'puzzle', I'd be curious to see what that sort of trace-guided verification could look like, if that's even feasible. My recollection of enough.c is that, algorithmically, it's sufficiently complicated that I need to really think hard when I'm reading the code. But also, it uses clever data structures specifically to reduce the memory requirements at runtime.

In comparison, "array size is always 1024, array index is always bitwise-anded with 1023, therefore always in-bounds" is undeniably simple and, per "The Fastest, Safest PNG Decoder in the World", practical and fast.

If you want some code to study, https://github.com/golang/image/tree/master/vp8l is a WebP-Lossless decoder in under 1200 lines of code.

Wuffs author here.

It's not full-blown formal verification but it doesn't have to be. Unlike most formal verification projects that I've seen, the proof part of Wuffs isn't about correctness (proving that "this implementation satisfies the PNG specification"), it's about safety (proving that "this implementation won't read/write out of bounds"), which is much more tractable. Especially as the PNG spec (or WebP spec) doesn't mandate how to treat malicious input (like unbalanced Huffman tables).

Wuffs doesn't have a WebP decoder yet but it's literally in the Roadmap and I've previously written the golang.org/x/image/webp package in the Go programming language.

Wuffs does have a PNG decoder, PNG uses Deflate compression and Deflate and WebP's "decode a Huffman tree" data tables are very similar. Wuffs also has an equivalent of zlib's enough.c program mentioned in the original blog post to calculate worst-case memory requirements. Wuffs' version is called script/print-deflate-huff-table-size.go and it says that, for a 9-bit primary table, we need 852 table entries. Round that up to 1024, for nearest power-of-two.

If you look for HUFFS_TABLE_SIZE = 1024 and HUFFS_TABLE_MASK = 1023 in Wuffs' std/deflate source code, you'll notice that Wuffs' Deflate decoder isn't susceptible to the same problem as the C/C++ WebP decoder the original blog post discussed. This is because, unless the Wuffs compiler can prove otherwise, the code doesn't just look up the table like `this.huffs[0][i]`, it's like `this.huffs[0][i&mask]` and `i&mask` is always in bounds. The mask is either HUFFS_TABLE_MASK or it's of a refinement type guaranteed <= 511. The array is always (statically) allocated with 1024 entries even though enough.c says that, with dynamic allocation, we could possibly get away with a smaller table.

As you already know, for Wuffs (and unlike C/C++), taking out the `&mask` will lead to a compile-time error. Wuffs code won't compile unless the compiler can prove that array indexes are always within bounds.

From the grandparent:

> this WebP bug occurred because the largest table size was formally proven but it didn't match what was fed to the source code

With WebP+enough.c this 'largest table size' was calculated by exhaustive, brute-force search (not really a formal proof) but it was based on assumptions (balanced codes) that didn't match actual (malicious) input. Or, in zlib-the-library, there's other C code (https://github.com/madler/zlib/blob/ac8f12c97d1afd9bafa9c710...) that rejects unbalanced Huffman codes, but IIUC similar enforcement was (until very recently) missing in libwebp.

With Wuffs, even if the worst-case calculation was based on an incorrect model (or forgetting to separately reject unbalanced codes), the end result (on malicious input) might be "the wrong pixels" but it shouldn't be "buffer overflow".

Wuffs and SkWuffsCodec.cpp author here. Wuffs' GIF decoder has shipped in Google Chrome since July 2021 (milestone M93).

A fair chunk out of that 1000 lines of glue code is adapting Wuffs' API to Skia's API. (Skia is the 2-D graphics library used by Chromium and many other projects). Specifically, GIFs can be animated, Wuffs' animation API is designed for sequential access and its state needs O(1) memory but Skia's SkCodec animation API allows random access and needs O(N) memory, where N is the number of animation frames.

Random access means that, after decoding frame 100, the SkCodec can rewind and produce frame 70 (by scanning backwards through its O(N) state to find the most recent I-Frame equivalent that's <= 70 and replaying forward from there).

Random access seems a bit of a weird feature to me, but Chrome/Skia's old GIF codec could do it, for whatever historical reasons, so the new Wuffs-backed one does too (even though it needed a chunk of glue code).