14 ms·
Wuffs’ PNG image decoder
- dividuum 6y agoInteresting. First time I've head of Wuffs. As someone that still uses C, this in particular sounds neat: (from https://github.com/google/wuffs#goals-and-non-goals https://github.com/google/wuffs#goals-and-non-goals) """ Wuffs' goal is to produce software libraries that are as safe as Go or Rust, roughly speaking, but as fast as C, and that can be used anywhere C libraries are used. [...] Wuffs the Library is available as transpiled C code. Other C/C++ projects can use that library without requiring the Wuffs the Language toolchain. Those projects can use Wuffs the Library like using any other third party C library. """
- andrewla 6y agoThe language itself is a little unreadable at first glance, but the idea of it is a very good one. sbt [1] is an amazing project for small embeddable toy programs, but using fuzzers rapidly shows how unsafe the code is, and the benchmarks in the original article show the extent of performance compromises made to make it work. It seems like this would be an interesting approach to a lot of security programming where it involves data structures, since those have typically been a source of issues. Having a memory-safe ASN.1 parser would be really nice, considering how much difficulty that has caused in the security space. With a lot of security programming there's a reliance on constant-time algorithms, which this may not be well-suited to, however. [1] https://github.com/nothings/stb https://github.com/nothings/stb
- saagarjha 6y ago*stb; sbt is something entirely different :)
- quotemstr 6y agoAll of Windows (including the NT kernel) is written using the same basic proof model that Wuffs uses, except that the constraints are specified as annotations on top of C and C++ instead of as a new programming language. I prefer the annotation approach, TBH, but I'm glad to see people working on safety. Specifically, Wuffs (like Rust) has this problem where it tries to fill the same niche as C and C++ and improve on these older languages in specific ways, but in addition to being different in ways necessary to achieve the language's objective is also different from C and C++ in totally gratuitous ways that are basically just aesthetic differences --- for example, "type var" vs "var: type". I'm a big believer in technical continuity. IMHO, a lot of recent language developments should have instead been extensions of C, C++, Java, or Python.
- amelius 6y agoBut the C++ spec has become quite unwieldy, so I can understand the desire to start a totally new language.
- edflsafoiewq 6y agoThe previous post on the blog has an observation that applies to languages as well > 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.
- matu3ba 6y agoWhat tool/framework do they use for annotation and are there standards like SMTlib2, but for annotating those kind of things? Can this tools verify that the annotations are correct wrt the code below or above?
- quotemstr 6y agohttps://docs.microsoft.com/en-us/cpp/code-quality/understanding-sal?view=msvc-160 https://docs.microsoft.com/en-us/cpp/code-quality/understand...
- remexre 6y agoI work on (well, mostly near) an extensible C compiler, designed so extension authors can independently create extensions, and users can import them as easily as libraries: https://github.com/melt-umn/ableC/ https://github.com/melt-umn/ableC/ (and I'd love to answer any questions you have about our approach or code.) IMO this approach hasn't taken off because maintaining compatibility with C while adding safety (or really just about any property) means implementing your own sublanguage that can't arbitrarily call C functions while maintaining your safety properties. On the other hand, C being able to call into your sublanguage easier is a benefit versus jury-rigging Cargo into your build system (in the case of Rust). On the other hand, this approach works great for adding extensions that increase the expressive power of C with new abstractions, for example algebraic data types, C++-like templating, etc.
- mleonhard 6y agoWuffs touts its lack of memory allocation as a safety feature [0]. Rust could add a `#![forbid(alloc)]` declaration and achieve the same effect. I think this would be a good idea. Wuffs types are not parameterized with lifetimes, so they may contain references only to items with static lifetime. This means that Wuffs cannot implement linked lists, hash tables, or other common data structures. To support those structures, Wuffs will need to either add lifetime parameters and a borrow-checker (like Rust) or add reference counting (like Rust `Arc`, C++ `shared_ptr`, Golang, Java, etc). [0] https://github.com/google/wuffs/blob/v0.3.0-beta.1/doc/note/memory-safety.md https://github.com/google/wuffs/blob/v0.3.0-beta.1/doc/note/...
- andrepd 6y agoIsn't that stupidly limiting?
- danielheath 6y agoDepends. AFAICT it’s designed to be embedded in a c project; in that context, it’s merely saying “the wuffs part does not allocate; do that in the c code”.
- andrepd 6y agoMakes sense.
- amelius 6y agoAfter NoSQL, now we also have NoAlloc :)
- dahart 6y agoSome people consider avoiding heap allocations to be smartly limiting. ;) It’s not really that limiting either, when you learn the techniques for it. There’s a famous list of NASA’s rules for safety-critical code that you’ll see pop up now and then, that subscribes to the “avoid heap memory allocation” philosophy. https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Developing_Safety-Critical_Code https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev... It’s not nearly as true anymore today, but working in console games 10-20 years ago, it was very common to try to avoid dynamic memory allocation because it was viewed as slow, unsafe, and unnecessary. A common strategy was to statically pre-allocate a single block of the worst-case memory needed for a given feature, because you need to be prepared to hit the worst case without crashing, so you might as well just reserve the max and focus on reducing what the maximum possible usage is. I once debugged a crash in a console game that was caused by someone trying to be too clever by half with their allocation and copy constructors. We had a team of a dozen people working on the crash through a weekend during crunch because the crash only occurred in a release build on the console dev kit. The cost of this one stupid bug due to using memory allocation could literally accounted for in the thousands of dollars. I basically had to write a mini one-off release-build stack-tracing sampling debugger in order to trap it. So, anyway, long story short, I’m old enough to appreciate why some people suggest that avoiding allocations is a good thing.
- Stanzilla 6y agoI don't understand why he just doesn't use Rust instead. The speed difference can't be that big.
- _delirium 6y agoFrom reading the docs, one main reason is that they want the output of compilation to be plain C. The Wuffs toolchain source-to-source compiles to plain C source, which can then be compiled and linked anywhere that has a C compiler and/or an FFI to the C ABI, which is a lot of places. Wuffs verifies its safety properties entirely at compile time, so once verified, it can translate the code to completely unchecked C code that is nonetheless known to be safe.
- pjmlp 6y agoYou should have a look at Frama-C (https://frama-c.com/ https://frama-c.com/) as well for this kind of stuff.
- 1-6 6y agoI wonder if the same performance benefits apply to Encoding PNGs.
- dividuum 6y agoLooks like there isn't an encoder for PNG: https://github.com/google/wuffs/tree/main/std/png https://github.com/google/wuffs/tree/main/std/png Given the project goals, I guess most encoders don't make a lot of sense: For image encoding you basically provide an "x * y * bytes_per_pixel" memory area and an encoder does its magic on that. There isn't really any complicated untrusted input in that case.
- 1-6 6y agoDarn, I had a handful of NumPy arrays which could use a fast encoder.
- xyzzy_plugh 6y agoBut I'm sure there are plenty of fast encoders? Wuffs isn't the path to a fast encoder. It's a path to something safe that is also pretty fast. If you're encoding PNGs from NumPY arrays you don't care at all about safety. If, for some reason I can't quite comprehend, whatever encoder you have on hand isn't fast enough, you can just disable compression optimizations -- but at that point you may as well be writing out a bitmap.
- commandlinefan 6y agoThe performance tradeoff isn't as justifiable, either: most images are decompressed orders of magnitude more times than they're compressed (generally just once).
- mjevans 6y agooptipng and pngcrush come to mind, but in the spirit of big O notation a run through those might be considered one macro-encoding process.
- com2kid 6y agoMy favorite part of the Wuffs github page has to be the definition it gives for Dependent Types > ...Dependent types are a way to implement compile-time bounds checking, but they're not the only way, and there's more to programming languages than their type systems. Wuffs does not use dependent types. Wuffs looks really interesting! I don't think I've ever even heard of a language that is designed to only be used in an auxiliary role along side another general purpose programming language! Edit: As pointed out below, scripting languages like Lua are used in an auxiliary role, but in a very different way! Wuffs is designed for use in the deepest most crucial parts of an app, where as scripting languages are typically GC'd and used at the very highest levels, often times by animations, game designers, or even end users!
- coldtea 6y ago>I don't think I've ever even heard of a language that is designed to only be used in an auxiliary role along side another general purpose programming language! Embeddedable scripting languages come to mind. E.g.: "Lua is a lightweight, high-level, multi-paradigm programming language designed primarily for embedded use in applications."
- com2kid 6y agoAh, of course. But opposite use case! Lua is used at the very top level of a program, sometimes its even user accessible! Wuffs is the exact opposite, it is designed for use in the deepest levels of a program! Very cool idea.
- zellyn 6y agolex, yacc?
- tyingq 6y agoRagel might be a related example: http://www.colm.net/open-source/ragel/ http://www.colm.net/open-source/ragel/
- stefan_ 6y agoThere is T0, part of BearSSL. This presentation has an explanation of it (starts slide 19): https://t1lang.github.io/NorthSec-20190516.pdf https://t1lang.github.io/NorthSec-20190516.pdf
- zelphirkalt 6y ago> Also, unlike Go or Rust, Wuffs’ memory safety is enforced at compile time, not by inserting runtime checks that e.g. the i in a[i] is within bounds or that (x + y) doesn’t overflow a u32. Am I missing something, or is this statement simply wrong? Have not used Go, but Rust checks its stuff at compile time as far as I know.
- justwalt 6y agoThis was my understanding as well, at least for the majority of memory related tasks. Edit: actually, it would help if I read the actual quote in your post. I think they’re right in saying that those things are checked at runtime in Rust, though I could be mistaken.
- boogies 6y agoI think it’s right: https://uploads.peterme.net/nimsafe.html https://uploads.peterme.net/nimsafe.html
- cakoose 6y agoYes, Rust checks a lot of things at compile time, but not all. For example, dynamic bounds checks (indexing into a Vec or slice).
- nwmcsween 6y agoStatement is correct, Rust does insert runtime bounds checking when needed.
- alpaca128 6y agoRust does use runtime checks for overflows and will panic if an overflow happens. In cases where you don't care or where it's intentional you can use `overflowing_add()` and its variants.
- steveklabnik 6y ago... in debug builds only, by default. In release, by default, there are no checks, and you get two’s compliment overflow, though the correct thing to do is use those variants, yes.
- wiml 6y agoAnother tool along these lines is Galois' Ivory language https://ivorylang.org/ https://ivorylang.org/ , a Haskell-embedded language for writing safe/reliable C.
- ExcavateGrandMa 6y agosounds epic but an eager use of SIMD for anything... hmmmm.
- ChuckMcM 6y agoNice. Still putting everything into memory make algorithm go brrrr is not too surprising :-). I'm really happy that folks continue to improve it though.
- quelsolaar 6y agoThe check-summing in PnG is poorly designed. It uses 2 different checksum on top of each other. The format itself checksum each chunk, but then the pixel data is using zlibs compression header that have a second checksum on top of that, using a different algorithm.
- astrange 6y agoMost everything about PNG is poorly designed. Using a text codec to encode image data doesn't make any sense even if you pre-filter it. A consequence of this is how much larger PNG files get with alpha, even if the alpha channel has no information in it. Lossy codecs with lossless modes tend to be a lot more efficient although may be harder to decode.
- bob1029 6y agoI know there are information theory tradeoffs, but if you want to go really fast, use JPEG. Specifically, LibJpegTurbo. I have been playing around with this, and it is fast enough to encode a 1080p+ 8bpp framebuffer in under 5 milliseconds. This is fast enough for interactive applications. Most web browsers likely use something similar to this, so as long as you encode quickly on the server you can expect fast decode on the client.
- parhamn 6y agoInteresting! Do you have an example of how such a thing could be used in an interactive language?
- bob1029 6y agoThink about extreme forms of server-side rendered applications where you need to keep the client device as simple, cheap and locked-down as possible. All you need are 2 streams: 1 from client-to-server w/ all touch/keyboard events, and another from server-to-client with JPEG frames. One could easily build client devices using FPGAs or other integrated technologies with this sort of architecture. The only caveats are latency & bandwidth requirements, but there are strategies for managing this, as well as problem domains where sufficient constraints exist on both counts (i.e. secure local networks).
- matu3ba 6y agoAre there any compiletime benchmarks? I would be interested how much their approach scales in terms of code size, since they use likely SMT solvers to guarantee having no arithmetic overflows (which is more than Rust guarantees). Ideally as comparison with compile times of Rust programs.
- aw1621107 6y ago> since they use likely SMT solvers to guarantee having no arithmetic overflows At least based on a quick skim of the docs, they use a combination of programmer assertions, interval arithmetic, and their type system for bounds checking and ensuring no arithmetic overflows.
- matu3ba 6y agoChecked as well. They can only do this, because they require that heap memory owned by pointers does not get fragmented. So programmers must manage pointer offsets to each heap structure themself. Hence you never get potential pointer soup (pointers pointing to subparts and pointing to other things), which Rust resolves with pointer lifetime checking. Also loop invariants etc must all be annotated. I would be more interested how they plan to handle IO effects or if they want to omit that.
- nigeltao 6y ago> programmers must manage pointer offsets to each heap structure I'm sorry but I don't understand this statement. Can you re-phrase it? > I would be more interested how they plan to handle IO effects or if they want to omit that. I'm not sure exactly what you're asking for, but see the Coroutines, Effects and I/O pages in https://github.com/google/wuffs/tree/main/doc/note https://github.com/google/wuffs/tree/main/doc/note
- sanxiyn 6y agoWuffs does not use a SMT solver. https://github.com/google/wuffs/blob/main/doc/note/assertions.md https://github.com/google/wuffs/blob/main/doc/note/assertion... explains.
- adamrezich 6y agowhy did the title change on this submission? is it not the fastest in the world?
- bugfix 6y agoThe title changed multiple times. I've seen at least 3 in the last 30 minutes (safest, fastest and now this one).
- adamrezich 6y agowhy? usually I only see this happen for misleading headlines and appending "(year)" to old articles that might be construed as recent. what's misleading about the actual article's headline? as far as I can tell it seems to be true.
- convery 6y agoThe author of Mango posted a benchmark on Reddit: https://www.reddit.com/r/programming/comments/mld1ob/the_fastest_safest_png_decoder_in_the_world/gtnbv50/ https://www.reddit.com/r/programming/comments/mld1ob/the_fas... load save ---------------------------------------------- // image: 1165 x 859 (1943 KB) 24bpp libpng: 19.2 ms 494.7 ms wuffs: 14.9 ms 0.0 ms mango: 10.0 ms 84.7 ms // image: 312 x 442 (43 KB) 32bpp libpng: 2.9 ms 18.3 ms wuffs: 0.4 ms 0.0 ms mango: 0.1 ms 7.3 ms // image: 160 x 120 (13 KB) 8bpp libpng: 0.7 ms 9.5 ms wuffs: 0.1 ms 0.0 ms mango: 0.1 ms 3.2 ms // image: 90 x 112 (23 KB) 24bpp libpng: 0.9 ms 3.9 ms wuffs: 0.5 ms 0.0 ms mango: 0.2 ms 1.3 ms
- adamrezich 6y agoAh cool, it would be neat to see a response from OP about this!
- ivoras 6y agoSurprisingly, Go's png decoder is half as slow as the default libpng :( https://nigeltao.github.io/blog/2021/fastest-safest-png-decoder.html#appendix-benchmark-numbers https://nigeltao.github.io/blog/2021/fastest-safest-png-deco...
- michaelcampbell 6y agoUgh, what does "half as slow" mean? Twice as fast? Half the speed? Any comparison to "slow" is generally the wrong direction.
- kevincox 6y agoThis isn't that surprising. In general Go is about half the speed of C to barring specifically optimized code or calling out to a faster library this would be expected.
- The_rationalist 6y agoSo will it makes its way into browsers?
- miohtama 6y agoFirst time hearing about Wuffs. It says Wuffs compiles to C. In this case, will the choice of C compiler affect the performance?
- saagarjha 6y agoYes: > Note that gcc10 performs slightly faster than clang9 in Wuffs’ benchmark numbers at the top of this post (as well as in an earlier non-SIMD Adler-32 implementation), although clang9 sometimes performs better for the other C mimic libraries.
- rurban 6y agoLooks good, but has somewhat widely false claims: > SMHasher is a test and benchmark suite for a variety of hash function implementations. It can provide data for claims like “our new Foo hash function is faster than the widely used Bar, Baz and Qux hash functions”. However, when comparing Foo to CRC-32, be aware that a SIMD-accelerated CRC-32 implementation can be 47x faster than SMHasher’s simple CRC-32 implementation. In fact smhasher implements both, the slow soft crc32 he cites, and the fastest crc32_pclmul, which is not just 47x faster, but 5000x faster. Other than wuff's implementation of the crc32_pclmul variant. Compare https://github.com/rurban/smhasher/#smhasher https://github.com/rurban/smhasher/#smhasher crc32 392.10 vs crc32_pclmul 1972140.38 MiB/sec Reminds me a lot on ATS
- Karliss 6y agoThat number doesn't seem realistic. Even for future generations of ram and PCIe the bandwidth is on the order of 50GB/s not 2TB/s .
- nigeltao 6y ago> smhasher implements both Ah, I'm based on aappleby/smasher, which is what the original location (http://code.google.com/p/smhasher http://code.google.com/p/smhasher) redirects to. I didn't realize that you have a more active fork. > not just 47x faster, but 5000x faster It's 47x faster: https://github.com/rurban/smhasher/issues/189 https://github.com/rurban/smhasher/issues/189
- rurban 6y agoThanks a lot for detecting this bug! Nigel's numbers were right, mine were wrong
- ape4 6y agoWuffs == Wrangling Untrusted File Formats Safely it appears
- the8472 6y ago> decompressing the entire image all-at-once (into one large intermediate buffer) instead of one row at a time (into smaller, re-usable buffers). All-at-once requires more intermediate memory but allows substantially more of the image to be decoded in the zlib-decompressor’s fastest code paths. Mozilla's imagelib has a neat trick to gain performance while working with smaller memory buffers when you want to render the output image at a smaller resolution than it is encoded. They call it downscale-during-decode. So this library pulls zlib decompression into the decode loop. Imagelib on the other hand optimizes at the other end of the pipeline and pulls downscaling into the decode loop. imagelib's optimization has the advantage that it helps with both small images as long as they're not displayed pixel-exact and also makes decoding humungous images feasible without causing the browser to explode with OOMs.
- deleted 6y ago[deleted]
- CyberRabbi 6y ago> Wuffs is not a general purpose programming language. It is for writing libraries, not programs. The idea isn't to write your whole program in Wuffs, only the parts that are both performance-conscious and security-conscious. Aren’t all apps (anything not one-off scripts) performance and security conscious? Being performance and security conscious seems like the rule, not the exception.
- saagarjha 6y agoGenerally code that deals with untrusted input often needs to balance the scale more towards security than other parts of the program might.
- FounderBurr 6y agoDespite the intent to push “wuffs a 21st century programming language”, nothing here is presented that couldn’t be achieved by just applying the same limitations/optimizations to the current libpng code.
- nigeltao 6y agoThat could get to parity with "Fastest", but it wouldn't match it with "Safest".
- renox 6y agoInteresting 'single purpose' language though I'm surprised that 1) variables have to be declared before the code (I had to do this a long time ago and it was annoying) 2) the separated section for uninitialised variable in struct, why not =undef like all the other languages? Also having to use base.u32 everywhere instead of just u32 must be annoying fast.
- person_of_color 6y agoFun fact, author is Terence Tao’s brother.
- ashkankiani 6y agoThe author is now a new favorite person of mine. I've been working on my own language, and I have an incredible overlap with the features that Wuff has, specifically the coroutines, refinement types, the "facts" (which I had been inspired to implement from ATS with its proof threading), the io_buffer slice type, and the effects system. It's kind of shocking how much stuff there is on overlap, but it does give a good indication to me that this is a "good idea." I'm especially pleased with his approach to practicality re: compile times. I'm also glad it's Apache2 licensed because I'm going to be reading through its source for inspiration at a future point for reference for my own implementations. I also see a strong likelihood that I will use it extensively for a few projects I had been working on in embedded for the ESP32 on my mobile device prototype and for non-embedded projects with my PL and otherwise (like for my Neovim UI frontend). I'm so glad this was posted.
- nigeltao 6y agoThanks for the kind words!
- rurban 6y agoWhat does `choosy_up` stand for? Looks like choosy stands for vtable, and up for parent, right?
- nigeltao 6y agoSorry, that part is relatively new and poorly documented. Choosy is sort of vtable-ish. It selects between method implementations (which all have the same signature), typically based on cpuid (e.g. if the CPU is SSE4.2+PCLMUL capable, set foo = foo_x86_sse42; if not, use the default foo impl). up (the private method) just implements update (the public method). Only private methods can be choosy.
- volta83 6y agoSo what happens if you try to decode a really big PNG, e.g., like any of the > 1Tb large pngs of space photos that are around?
- bschwindHN 6y agoI recently wrote a Rust PNG decoder mostly for use in no_std contexts, and it was motivated out of wanting to decode emoji for a font rasterizer. I didn't really put any effort into optimizing it yet, though it does use miniz_oxide and it decompresses the entire image at once instead of per-scanline. I'm curious if it is at all competitive with the Wuffs decoder, I'm guessing probably not because I haven't put any effort into using SIMD. https://github.com/bschwind/png-decoder https://github.com/bschwind/png-decoder But overall the implementation was pretty straightforward, I just read the RFC and wrote it out over a few weeks. One quirk of my library currently is it always returns an RGBA buffer, instead of potentially letting you save memory on a grayscale or RGB image.
- nigeltao 6y ago> I'm curious if it is at all competitive with the Wuffs decoder You could try adapting https://github.com/google/wuffs/tree/main/script/bench-rust-png https://github.com/google/wuffs/tree/main/script/bench-rust-... > https://github.com/bschwind/png-decoder https://github.com/bschwind/png-decoder Note that statements like: let bytes_per_scanline = ((header.width * header.bit_depth as u32 * header.color_type.sample_multiplier()) + 7) / 8; can silently overflow a u32 if width is 0x800_0000, bit_depth is 8 and sample_multiplier is 4. Part of the point of Wuffs is to catch things like that (at compile time).
- bschwindHN 6y ago> You could try adapting ... Do you accept PRs for the Rust benchmarks? My code is nowhere near competitive to the Wuffs implementation, but it would be a fun goal to work towards. > Note that statements like ... can silently overflow a u32 Thank you for catching that, I'll go through the entire codebase and try to fix those up. That's a part of Rust that always makes me feel uneasy - the compiler will tell you if you're doing math with numbers of different bit widths, but it won't warn you in most cases about overflow. That would be a good addition to the Rust compiler, or at least a Clippy lint.
- nigeltao 6y ago
- junon 6y agoWuffs sounds really cool, surprised I haven't heard about it. It claims memory safety but I'd be interested in how it has proven this - is it verified? Sad that it's a Google project, but I can look past every now and again.
- chmaynard 6y agoThe README on GitHub looks useful: https://github.com/google/wuffs https://github.com/google/wuffs
- sam_goody 6y agoCan someone please explain usage? I assume this would not be useful on a web server, unless it could be used by Image-Magick or GD. Is this targeting Software devs (like Chrome or Affinity Designer)? Is this meant to replace the default decoder somehow, for a user that wants to speed up his system? Is there some other use I am missing?