23 ms·

QOI – The Quite OK Image Format

219 points by rrauenza 5y ago

ltbarcly3 5y ago
So it only compresses to the size of PNG, but it's faster to decode? I could see this being useful for something like training sets for AI, if loading is fast enough you could avoid saving raw pixel arrays.
- porbelm 5y ago
  Seems like it compresses to /around/ the size of PNG but with like 10-50x faster encoding AND decoding?
  - andai 5y ago
    >20x-50x faster encoding and 3x-4x faster decoding
  - mpais 5y ago
    QOI is not on the pareto frontier for compression [1], it is however extremely simple and is a nice introduction to data compression for anyone wanting to learn about the field. [1] See: https://www.lucaversari.it/FJXL_and_FPNGE.pdf https://www.lucaversari.it/FJXL_and_FPNGE.pdf https://github.com/libjxl/libjxl/tree/main/experimental/fast_lossless https://github.com/libjxl/libjxl/tree/main/experimental/fast... https://github.com/veluca93/fpnge https://github.com/veluca93/fpnge
fortysixdegrees 5y ago
Is there anything in the algorithm which would preclude an efficient CUDA implementation?
- krasin 5y ago
  Good question. I've taken a look at the final revision of the spec ([1]) and it seems that parallelizing a QOI decoder may be non-trivial, because of back references. More over, it's possible to come up with QOI-encoded images which would see no speedup from any concurrent decoding (for example, if every single pixel refers to the previous). On the other hand, a parallel QOI encoder is relatively straightforward and will only have about 4*N bytes of compression penalty per image, where N is the number of threads, which is a trivial cost, if we talk about megapixel-scale images (as opposed to tiny icons). 1. https://qoiformat.org/qoi-specification.pdf https://qoiformat.org/qoi-specification.pdf
- astrange 5y ago
  Compression is fundamentally not suitable for GPGPU, because if it can be parallelized then it's not compressed well enough. That's why codec acceleration all uses ASICs. Of course in some situations you don't care about compression efficiency that much.
  - riedel 5y ago
    That is a strange statement, most machine learning boils down to compression in essence (OK it is lossy, but any image quantisation is also lossy). E.g. autoencoders are compression algorithms: take the model as a dictionary and the latent space weights as compressed representation. For most algorithms you are right though. Particularly it is worth the effort to put things in to Asics as the "wiring" normally stays stable and you do not need the flexibility of gpgpus . Still also there is nothing that keeps you from using them e.g. for efficient parallel decoding.
    - astrange 5y ago
      I think it's axiomatically true and ML models get a pass on being inefficient because people are so busy being impressed by their magic tricks. In particular, using ML models for compression would get a free advantage because they're often several GBs where a traditional codec is KBs, so they can hide data in there, but most people wouldn't think of that as being part of the compressed message size. But they could have very differently shaped dependency trees, especially if you somehow managed to not run an entropy coder as the last step of compression.
      - riedel 5y ago
        Totally agree, tgeneral compression that requires the dictionary to be transmitted on every message is not the best use case (if there even is any). Minimal description length is actually a nice information theoretical measure to describe power of ML models to compress. However I have also seen tons of theoretical proof that probably there is no optimal compression method ( I looked at grammar vs entropy coding some time ago) hence there is probably no optimal hardware in general. In the end it depends on your assumption about the the data (quality, structure, size, chunking,...) you want to compress.
- mkcg 5y ago
  I don't know about CUDA, however I've made an AVX2 based encoder a few months ago : https://github.com/phoboslab/qoi/pull/143 https://github.com/phoboslab/qoi/pull/143 I intend to create an AVX2 based decoder but I had absolutely no time to work on side projects in the past three months. You might also want to take a look at this streaming encoder if you want to encode large files with a tiny memory footprint : https://github.com/MKCG/php-qoi/blob/main/src/FFI/lib/qoi.c https://github.com/MKCG/php-qoi/blob/main/src/FFI/lib/qoi.c
lifthrasiir 5y ago
Significant past discussions in HN: https://news.ycombinator.com/item?id=29328750 https://news.ycombinator.com/item?id=29328750 (2021-11-24, 293 comments) and https://news.ycombinator.com/item?id=29661498 https://news.ycombinator.com/item?id=29661498 (2021-12-23, 103 comments).
- dang 5y ago
  Thanks! Macroexpanded: QOI – The “Quite OK Image Format” for fast, lossless image compression - https://news.ycombinator.com/item?id=29661498 https://news.ycombinator.com/item?id=29661498 - Dec 2021 (103 comments) The QOI File Format Specification - https://news.ycombinator.com/item?id=29625084 https://news.ycombinator.com/item?id=29625084 - Dec 2021 (54 comments) QOI: Lossless Image Compression in O(n) Time - https://news.ycombinator.com/item?id=29328750 https://news.ycombinator.com/item?id=29328750 - Nov 2021 (293 comments)
armamut 5y ago
There is a video on Youtube explaining some image formats. At the end of the video, QOI is mentioned as well. Check this out https://youtu.be/EFUYNoFRHQI https://youtu.be/EFUYNoFRHQI
- slig 5y ago
  +1. Reducible is the 3Blue1Brown of Computer Science.
  - hackernewds 5y ago
    What is 3blue1brown?
    - Timwi 5y ago
      3blue1brown is the Reducible of math.
    - malobre 5y ago
      It's a YouTube channel focused on mathematics: https://www.youtube.com/c/3blue1brown https://www.youtube.com/c/3blue1brown
- rrauenza 5y ago
  This video was the inspiration for posting this!
dvh 5y ago
This is something people at https://suckless.org https://suckless.org would like
- toxik 5y ago
  [flagged]
  - franga2000 5y ago
    That's one hell of an entirely unsubstantiated claim...
    - toxik 5y ago
      https://news.ycombinator.com/item?id=20845633 https://news.ycombinator.com/item?id=20845633
      - teddyh 5y ago
        They hiked with torches, and one of them had a laptop named “Wolf’s lair”. Sure, they could be nazis or something, but those things do not exactly prove that. Point is, no matter how suspicios you think that would look, I would not go as far as declaring it “Nazi dog whistling”.
        tom_ 5y ago
        Laptop called "Wolf's Lair"? Hiking at night with burning torches? Hmm, you're right... while it's no cast-iron proof, they could definitely be nazis or something.
        jhgb 5y ago
        In Czech Republic at least, "Vlčata" (Wolf pups) are young scouts. Not everything named after wolves necessarily has to be ominous.
        5y ago
eyelidlessness 5y ago
Very unrelated and I really hope my admitted ignorance won’t be unwelcome, but I was quite curious and… let’s just say I’ve never been so curious about something written in C, much less written any myself. I glanced at the possibly relevant .c files and none were 300 SLOC or even LOC. That left only the .h file. I had no idea you could even provide implementation in .h files. I mean in hindsight that seems perfectly cromulent, if maybe still questionably intuitive. Is this common practice? I’ve been assuming header files are used for unimplemented type definitions similar to TypeScript .d.ts files. Is this wildly wrong to assume?
- bhaney 5y ago
  > Is this common practice? For small libraries, yes https://en.wikipedia.org/wiki/Header-only https://en.wikipedia.org/wiki/Header-only
- ncmncm 5y ago
  Header-only libraries for C++ are very common, and not just small libraries. They make a great deal of sense for libraries used mainly in small programs or small parts of big programs.
- mananaysiempre 5y ago
  > Is this common practice? I’ve been assuming header files are used for unimplemented type definitions similar to TypeScript .d.ts files. Is this wildly wrong to assume? By traditional reckoning, you’re almost correct, but this is an exception. Unlike many other languages (including TypeScript AFAIK), C and C++ compilers are defined to process a self-contained piece of text (the “compilation unit”), which must declare the type of everything it uses from the outside; those are then linked together into an executable with external references bound by name, with the types blindly assumed to be correct. (The linker works at the assembly level, not the C level, the types are already gone.) The usual workaround is to have the preprocessor, which puts together said piece of text[1], pull in the declarations from a common source, the “headers”, just plain insert the declaration text into the source file. Thus the headers play a similar role to .d.ts files, but the toolchain does not impose any convention on how things are arranged in files, unlike in TypeScript, Go, or Java. There are two downsides for this: first, the declarations go through the compiler once for every source file that uses them, yielding slower compiles; second, if you want to consume a library in source form you’ll have to marry the build system for the library with the build system for your consumer. (The “build system” is the conceptual thing that knows how to set up the header search paths, which files to compile, and how to link or otherwise package the results into build artifacts.) An alternative to this traditional organization is the “header-only library”; it mostly eliminates the second downside at the cost of exacerbating the first. - In the C++ world, the dumb linker model I described above is something of a lie: a lot of C++ things (vtables, inline functions, template instances, etc.) do not actually have a well-defined compilation unit they belong to (“vague linkage”), so in the simplest approach the compiler generates a definition for every compilation unit and the linker has to (know enough to be able to) throw away all of these except one. (You see where the notoriously long C++ compile times come from.) A header-only library then just bites the bullet, defines everything inline, and has the linker sort them out. These have become fairly common over the last decade. (This does not help the compile times.) - In the C or C-ish-C++ gamedev world, there’s a practical need to get prototypes or good-enough preliminary versions out the door quickly, so the library that is easiest to integrate across as much build systems as possible has an advantage. A different variety of header-only libraries has gained traction there. These have the header contain both declarations and implementation, but the implementation is guarded by a preprocessor macro; the user of the library defines that macro in a single compilation unit that they designate as owning that implementation. (This has worse “tree-shaking” characteristics than a well-organized static library, but if the library isn’t large that’s probably not a big deal, and in any case many common libraries, such as libjpeg and libtiff, are not well organized in this sense.) The QOI reference implementation comes from the second tradition and is probably influenced by the popular stb libraries[2]. [1] Actually a token stream. [2] https://github.com/nothings/stb https://github.com/nothings/stb
graderjs 5y ago
I just read the PDF spec. That's awesome! I particularly like the four 2-bit tags that allow you to encode: runs of a previously seen pixel, or a color Delta (big or small), or a previously seen pixel. Plus, the simple hash function of previously seen pixels (inner product of rgba and the first four odd primes) based on their color values, into a 64 slot array, it's just really nice. It's so refreshing to see one page specification. it just comes across as really elegant. Almost a work of art and has a certain aesthetic to it that I really like. It'll be cool to see more people creatively inventing standards. It's a worthwhile pursuit not because you think okay we're going to create a standard that's going to take over some other standard...nor a proliferation. But a file format a specification is a valid sort of medium of creative expression and output. It's a valid creative product I think. So it's just really really cool to see this!
bscphil 5y ago
> It losslessy compresses images to a similar size of PNG It's worth pointing out that in cases where PNG is still the most reasonable format to use, compression gains are frequently left on the table. I frequently see 20-30% additional compression with tools like ect ("efficient compression tool"), oxipng, and zopflipng, and that's starting with images that are already pretty well compressed (using the strongest settings available from traditional PNG libraries). In other words, even PNG compresses better than PNG. :-) Case in point: I downloaded the sample images in the zip on the page and recompressed them with ect. It took only a few seconds, but 4 of the 7 sample images could be further compressed by more than 33%! After compressing them as much as I could achieve, the resulting PNG images were only 77% the size of the QOI images. Compression gains of 23% are nothing to sneeze at when it comes to lossless compression. Of course, that's not to say that something like QOI wouldn't be useful. Even if it wasn't, I do love seeing tiny but effective implementations of algorithms like this - well done.
- amelius 5y ago
  Sounds like you should use a compression tool that recognizes the content and recodes QOI as PNG on the fly, then zips it.
  - dylan604 5y ago
    If you've already encoded the content to the most effecient size, why then zip it?
    - idontknowifican 5y ago
      because the size of the download affects time to action
      - dylan604 5y ago
        care to elaborate on how you think zipping it affects time to action? it's not making it smaller.
      - 5y ago
fitba72 5y ago
Does this have application in video compression? I know almost nothing about image or video compression so just curious.
- nmalaguti 5y ago
  No. This is a very simple and reasonably efficient image format. It is notable for its simplicity and straightforward implementation, as well as its speed compared with png.
  - hackernewds 5y ago
    Why does it not have an application in video compression?
    - mekkkkkk 5y ago
      Video compression is typically not about "take each frame, and make it as small as possible". Video compression revolves around cleverly making use of deltas and segmenting the image so that you can reuse as much data as possible from previous frames/keyframes.
    - jug 5y ago
      I'm no expert on this but I assume because it would be all keyframes? I.e. the format doesn't support encoding transitions from frame to frame. But I guess decent video support could be possible if you define video as pixel perfect animation, i.e. Animated GIF. These would of course not compete with traditional video.
    - _flux 5y ago
      I didn't read the spec, but I assume that if a single-picture format doesn't have the concept of making use of reference pictures (so previous or future frames), it's leaving _a lot_ of compression potential on the table. You can of course just have a sequence of individually compressed frames, just as you can do with PNG, TARGA, or JPEG, but these are not usually the ways you would want to distribute the video due to the huge sizes.
athrowaway3z 5y ago
On a tangent, is there a source for the qoi-specification.pdf? I like the format.
- aasasd 5y ago
  You realize that you can do such a format with HTML? And ‘print’ to PDF if you wish? Truly my bafflement is infinite as to why people keep dragging in PDF when all they make is a bunch of text with maybe a few images or tables. My guess is, those people just hate and wish constant suffering upon everyone who doesn't have a 14" portrait-oriented screen nor has to fumble with paper. Asking for PDF is also bitterly ironic in the context of QOI.
gman83 5y ago
How does it compare to WebP?
- user-the-name 5y ago
Klasiaster 5y ago
Essentially good compression needs prediction. Here the previous pixels are used but it seems only from the row. Given that this is a linear decompression (not a progressive) it would help a lot to instead of looking just at the row, also look at the above row where the other previously seen neighbor pixels are. With something like arithmetic coding and only the previously seen neighbor pixels as prediction contexts with some tweaking one can quickly get better compression than PNG offers. Doing this in a short C implementation is left to the reader ;)
- adgjlsfhk1 5y ago
  the main downside of this is it pretty much requires storing a full row of the image in memory, while QOI only needs to store 66 pixels.
amelius 5y ago
My preferred image format looks like: byte 0-3: magic code byte 3-10: 64-bit index into global decoder table byte 11-...: compressed data The global decoder table is maintained by a standards organization. For every occupied index, it contains a piece of WebAssembly code that decodes the data and produces an image and metadata. Advantage: no more dealing with various image formats and installing decoders libs; there is just 1 format that can be tuned to specific uses and it will be available hundreds of years into the future. The WebAssembly code can be hand-optimized into native code (or even hardware) for frequently used decoders. The only downside is that you might occasionally need to access the central code repository over the internet to download a decoder.
- mrob 5y ago
  >and metadata You glossed over the most difficult part of the specification.
- planck01 5y ago
  Including a futureproof decoder in every single image is a huge filesize overhead though. Or maybe I don't exactly understand your proposal.
  - amelius 5y ago
    The decoder-part is the same for many images, so the idea is to store them inside a standardized codebook that is pointed to from the data.
    - deleted 5y ago
      [deleted]
  - xvector 5y ago
    IIUC he is saying that there will be a 64-bit index into a global standards-maintained table, and the decoder is downloaded from said table. Not that the decoder is actually included with the image. The decoder itself would probably eventually be cached if not shipped with browsers by default.
rsp1984 5y ago
Unfortunately not everything compresses well with QOI. I have considered using it for our company but then did some tests with real images from real (noisy, low-res) cameras. The result is that in many cases QOI did not offer much compression at all over just storing all the raw bytes and in some cases it even increased the size. The sample images that come with the download look well selected. I encourage everyone to try it on real data and see for themselves. Personally I was quite underwhelmed by the format and we are sticking with PNG for the time being.
- eps 5y ago
  > images from real (noisy, low-res) cameras But these won't compress well _losslessly_ in principle, would they? Or did you manage to find a format that did in fact work well?
  - rsp1984 5y ago
    PNG works quite well on these kinds of images too.
    - eps 5y ago
      Do you have any specific examples you can share? PNG should not be able to compress noisy images well, because noise removes patterning. JPEG obviously can, but exactly because it is lossy.
      - lifthrasiir 5y ago
        PNG can't transform noisy images into something more compressible, but it uses better entropy coding compared to QOI.
  - minimalc 5y ago
    I haven't evaluated this personally but the (close to?) lossless raw sensor image compression from Dotphoton [1] seems like an interesting approach for getting around the issue of sensor noise in image compression. However the implementation details are disappointly vague, as it's a proprietary product. [1]https://dotphoton.com/ https://dotphoton.com/
codazoda 5y ago
This format (or something similar) may work for my project. I’ve designed a set of low color images for a retro TRS-80 computer I own and would like to write a slot machine app for. With its low processing power and my self-imposed requirement to write it in the BASIC language I would have used as a kid, the machine doesn’t have a lot of processing power or memory to do decompression stuff. Some of the concepts here seem simple enough to implement. I can probably reduce it even farther since I have less colors.
yboris 5y ago
Awesome! Also, a PSA about the next image format for the web: JPEG XL (.jxl) - should be on everyone's radar. Already supported by browsers (behind a feature flag). Has lossy and lossless mode. https://jpegxl.info/ https://jpegxl.info/ https://cloudinary.com/blog/time_for_next_gen_codecs_to_dethrone_jpeg https://cloudinary.com/blog/time_for_next_gen_codecs_to_deth...
- pornel 5y ago
  It's worth adding that lossless JXL can be faster and compress better than QOI (at the same time == Pareto improvement). It basically obsoletes QOI. There are also special-case trimmed-down PNG encoders that are in the same league as QOI in terms of compression and simplicity.
  - lifthrasiir 5y ago
    > lossless JXL can be faster and compress better than QOI It should be noted that it "can be", not it always is. The implementation in question [1] is currently experimental and not what you get from cjxl. In any case it is worth noting that QOI inspired both FPNG and FJXL. [1] https://github.com/libjxl/libjxl/tree/main/experimental/fast_lossless https://github.com/libjxl/libjxl/tree/main/experimental/fast...

219 points by rrauenza 5y ago

So it only compresses to the size of PNG, but it's faster to decode? I could see this being useful for something like training sets for AI, if loading is fast enough you could avoid saving raw pixel arrays.

porbelm 5y ago
Seems like it compresses to /around/ the size of PNG but with like 10-50x faster encoding AND decoding?
- andai 5y ago
  >20x-50x faster encoding and 3x-4x faster decoding
- mpais 5y ago
  QOI is not on the pareto frontier for compression [1], it is however extremely simple and is a nice introduction to data compression for anyone wanting to learn about the field. [1] See: https://www.lucaversari.it/FJXL_and_FPNGE.pdf https://www.lucaversari.it/FJXL_and_FPNGE.pdf https://github.com/libjxl/libjxl/tree/main/experimental/fast_lossless https://github.com/libjxl/libjxl/tree/main/experimental/fast... https://github.com/veluca93/fpnge https://github.com/veluca93/fpnge

fortysixdegrees 5y ago

Is there anything in the algorithm which would preclude an efficient CUDA implementation?

krasin 5y ago
Good question. I've taken a look at the final revision of the spec ([1]) and it seems that parallelizing a QOI decoder may be non-trivial, because of back references. More over, it's possible to come up with QOI-encoded images which would see no speedup from any concurrent decoding (for example, if every single pixel refers to the previous). On the other hand, a parallel QOI encoder is relatively straightforward and will only have about 4*N bytes of compression penalty per image, where N is the number of threads, which is a trivial cost, if we talk about megapixel-scale images (as opposed to tiny icons). 1. https://qoiformat.org/qoi-specification.pdf https://qoiformat.org/qoi-specification.pdf
astrange 5y ago
Compression is fundamentally not suitable for GPGPU, because if it can be parallelized then it's not compressed well enough. That's why codec acceleration all uses ASICs. Of course in some situations you don't care about compression efficiency that much.
- riedel 5y ago
  That is a strange statement, most machine learning boils down to compression in essence (OK it is lossy, but any image quantisation is also lossy). E.g. autoencoders are compression algorithms: take the model as a dictionary and the latent space weights as compressed representation. For most algorithms you are right though. Particularly it is worth the effort to put things in to Asics as the "wiring" normally stays stable and you do not need the flexibility of gpgpus . Still also there is nothing that keeps you from using them e.g. for efficient parallel decoding.
  - astrange 5y ago
    I think it's axiomatically true and ML models get a pass on being inefficient because people are so busy being impressed by their magic tricks. In particular, using ML models for compression would get a free advantage because they're often several GBs where a traditional codec is KBs, so they can hide data in there, but most people wouldn't think of that as being part of the compressed message size. But they could have very differently shaped dependency trees, especially if you somehow managed to not run an entropy coder as the last step of compression.
    - riedel 5y ago
      Totally agree, tgeneral compression that requires the dictionary to be transmitted on every message is not the best use case (if there even is any). Minimal description length is actually a nice information theoretical measure to describe power of ML models to compress. However I have also seen tons of theoretical proof that probably there is no optimal compression method ( I looked at grammar vs entropy coding some time ago) hence there is probably no optimal hardware in general. In the end it depends on your assumption about the the data (quality, structure, size, chunking,...) you want to compress.
mkcg 5y ago
I don't know about CUDA, however I've made an AVX2 based encoder a few months ago : https://github.com/phoboslab/qoi/pull/143 https://github.com/phoboslab/qoi/pull/143 I intend to create an AVX2 based decoder but I had absolutely no time to work on side projects in the past three months. You might also want to take a look at this streaming encoder if you want to encode large files with a tiny memory footprint : https://github.com/MKCG/php-qoi/blob/main/src/FFI/lib/qoi.c https://github.com/MKCG/php-qoi/blob/main/src/FFI/lib/qoi.c

lifthrasiir 5y ago

Significant past discussions in HN: https://news.ycombinator.com/item?id=29328750 https://news.ycombinator.com/item?id=29328750 (2021-11-24, 293 comments) and https://news.ycombinator.com/item?id=29661498 https://news.ycombinator.com/item?id=29661498 (2021-12-23, 103 comments).

dang 5y ago
Thanks! Macroexpanded: QOI – The “Quite OK Image Format” for fast, lossless image compression - https://news.ycombinator.com/item?id=29661498 https://news.ycombinator.com/item?id=29661498 - Dec 2021 (103 comments) The QOI File Format Specification - https://news.ycombinator.com/item?id=29625084 https://news.ycombinator.com/item?id=29625084 - Dec 2021 (54 comments) QOI: Lossless Image Compression in O(n) Time - https://news.ycombinator.com/item?id=29328750 https://news.ycombinator.com/item?id=29328750 - Nov 2021 (293 comments)

armamut 5y ago

There is a video on Youtube explaining some image formats. At the end of the video, QOI is mentioned as well. Check this out https://youtu.be/EFUYNoFRHQI https://youtu.be/EFUYNoFRHQI

slig 5y ago
+1. Reducible is the 3Blue1Brown of Computer Science.
- hackernewds 5y ago
  What is 3blue1brown?
  - Timwi 5y ago
    3blue1brown is the Reducible of math.
  - malobre 5y ago
    It's a YouTube channel focused on mathematics: https://www.youtube.com/c/3blue1brown https://www.youtube.com/c/3blue1brown
rrauenza 5y ago
This video was the inspiration for posting this!

dvh 5y ago

This is something people at https://suckless.org https://suckless.org would like

toxik 5y ago
[flagged]
- franga2000 5y ago
  That's one hell of an entirely unsubstantiated claim...
  - toxik 5y ago
    https://news.ycombinator.com/item?id=20845633 https://news.ycombinator.com/item?id=20845633
    - teddyh 5y ago
      They hiked with torches, and one of them had a laptop named “Wolf’s lair”. Sure, they could be nazis or something, but those things do not exactly prove that. Point is, no matter how suspicios you think that would look, I would not go as far as declaring it “Nazi dog whistling”.
      - tom_ 5y ago
        Laptop called "Wolf's Lair"? Hiking at night with burning torches? Hmm, you're right... while it's no cast-iron proof, they could definitely be nazis or something.
        jhgb 5y ago
        In Czech Republic at least, "Vlčata" (Wolf pups) are young scouts. Not everything named after wolves necessarily has to be ominous.
      - 5y ago

eyelidlessness 5y ago

Very unrelated and I really hope my admitted ignorance won’t be unwelcome, but I was quite curious and… let’s just say I’ve never been so curious about something written in C, much less written any myself. I glanced at the possibly relevant .c files and none were 300 SLOC or even LOC. That left only the .h file. I had no idea you could even provide implementation in .h files. I mean in hindsight that seems perfectly cromulent, if maybe still questionably intuitive. Is this common practice? I’ve been assuming header files are used for unimplemented type definitions similar to TypeScript .d.ts files. Is this wildly wrong to assume?

bhaney 5y ago
> Is this common practice? For small libraries, yes https://en.wikipedia.org/wiki/Header-only https://en.wikipedia.org/wiki/Header-only
ncmncm 5y ago
Header-only libraries for C++ are very common, and not just small libraries. They make a great deal of sense for libraries used mainly in small programs or small parts of big programs.
mananaysiempre 5y ago
> Is this common practice? I’ve been assuming header files are used for unimplemented type definitions similar to TypeScript .d.ts files. Is this wildly wrong to assume? By traditional reckoning, you’re almost correct, but this is an exception. Unlike many other languages (including TypeScript AFAIK), C and C++ compilers are defined to process a self-contained piece of text (the “compilation unit”), which must declare the type of everything it uses from the outside; those are then linked together into an executable with external references bound by name, with the types blindly assumed to be correct. (The linker works at the assembly level, not the C level, the types are already gone.) The usual workaround is to have the preprocessor, which puts together said piece of text[1], pull in the declarations from a common source, the “headers”, just plain insert the declaration text into the source file. Thus the headers play a similar role to .d.ts files, but the toolchain does not impose any convention on how things are arranged in files, unlike in TypeScript, Go, or Java. There are two downsides for this: first, the declarations go through the compiler once for every source file that uses them, yielding slower compiles; second, if you want to consume a library in source form you’ll have to marry the build system for the library with the build system for your consumer. (The “build system” is the conceptual thing that knows how to set up the header search paths, which files to compile, and how to link or otherwise package the results into build artifacts.) An alternative to this traditional organization is the “header-only library”; it mostly eliminates the second downside at the cost of exacerbating the first. - In the C++ world, the dumb linker model I described above is something of a lie: a lot of C++ things (vtables, inline functions, template instances, etc.) do not actually have a well-defined compilation unit they belong to (“vague linkage”), so in the simplest approach the compiler generates a definition for every compilation unit and the linker has to (know enough to be able to) throw away all of these except one. (You see where the notoriously long C++ compile times come from.) A header-only library then just bites the bullet, defines everything inline, and has the linker sort them out. These have become fairly common over the last decade. (This does not help the compile times.) - In the C or C-ish-C++ gamedev world, there’s a practical need to get prototypes or good-enough preliminary versions out the door quickly, so the library that is easiest to integrate across as much build systems as possible has an advantage. A different variety of header-only libraries has gained traction there. These have the header contain both declarations and implementation, but the implementation is guarded by a preprocessor macro; the user of the library defines that macro in a single compilation unit that they designate as owning that implementation. (This has worse “tree-shaking” characteristics than a well-organized static library, but if the library isn’t large that’s probably not a big deal, and in any case many common libraries, such as libjpeg and libtiff, are not well organized in this sense.) The QOI reference implementation comes from the second tradition and is probably influenced by the popular stb libraries[2]. [1] Actually a token stream. [2] https://github.com/nothings/stb https://github.com/nothings/stb

graderjs 5y ago

I just read the PDF spec. That's awesome! I particularly like the four 2-bit tags that allow you to encode: runs of a previously seen pixel, or a color Delta (big or small), or a previously seen pixel. Plus, the simple hash function of previously seen pixels (inner product of rgba and the first four odd primes) based on their color values, into a 64 slot array, it's just really nice. It's so refreshing to see one page specification. it just comes across as really elegant. Almost a work of art and has a certain aesthetic to it that I really like. It'll be cool to see more people creatively inventing standards. It's a worthwhile pursuit not because you think okay we're going to create a standard that's going to take over some other standard...nor a proliferation. But a file format a specification is a valid sort of medium of creative expression and output. It's a valid creative product I think. So it's just really really cool to see this!

bscphil 5y ago

> It losslessy compresses images to a similar size of PNG It's worth pointing out that in cases where PNG is still the most reasonable format to use, compression gains are frequently left on the table. I frequently see 20-30% additional compression with tools like ect ("efficient compression tool"), oxipng, and zopflipng, and that's starting with images that are already pretty well compressed (using the strongest settings available from traditional PNG libraries). In other words, even PNG compresses better than PNG. :-) Case in point: I downloaded the sample images in the zip on the page and recompressed them with ect. It took only a few seconds, but 4 of the 7 sample images could be further compressed by more than 33%! After compressing them as much as I could achieve, the resulting PNG images were only 77% the size of the QOI images. Compression gains of 23% are nothing to sneeze at when it comes to lossless compression. Of course, that's not to say that something like QOI wouldn't be useful. Even if it wasn't, I do love seeing tiny but effective implementations of algorithms like this - well done.

amelius 5y ago
Sounds like you should use a compression tool that recognizes the content and recodes QOI as PNG on the fly, then zips it.
- dylan604 5y ago
  If you've already encoded the content to the most effecient size, why then zip it?
  - idontknowifican 5y ago
    because the size of the download affects time to action
    - dylan604 5y ago
      care to elaborate on how you think zipping it affects time to action? it's not making it smaller.
    - 5y ago

fitba72 5y ago

Does this have application in video compression? I know almost nothing about image or video compression so just curious.

nmalaguti 5y ago
No. This is a very simple and reasonably efficient image format. It is notable for its simplicity and straightforward implementation, as well as its speed compared with png.
- hackernewds 5y ago
  Why does it not have an application in video compression?
  - mekkkkkk 5y ago
    Video compression is typically not about "take each frame, and make it as small as possible". Video compression revolves around cleverly making use of deltas and segmenting the image so that you can reuse as much data as possible from previous frames/keyframes.
  - jug 5y ago
    I'm no expert on this but I assume because it would be all keyframes? I.e. the format doesn't support encoding transitions from frame to frame. But I guess decent video support could be possible if you define video as pixel perfect animation, i.e. Animated GIF. These would of course not compete with traditional video.
  - _flux 5y ago
    I didn't read the spec, but I assume that if a single-picture format doesn't have the concept of making use of reference pictures (so previous or future frames), it's leaving _a lot_ of compression potential on the table. You can of course just have a sequence of individually compressed frames, just as you can do with PNG, TARGA, or JPEG, but these are not usually the ways you would want to distribute the video due to the huge sizes.

athrowaway3z 5y ago

On a tangent, is there a source for the qoi-specification.pdf? I like the format.

aasasd 5y ago
You realize that you can do such a format with HTML? And ‘print’ to PDF if you wish? Truly my bafflement is infinite as to why people keep dragging in PDF when all they make is a bunch of text with maybe a few images or tables. My guess is, those people just hate and wish constant suffering upon everyone who doesn't have a 14" portrait-oriented screen nor has to fumble with paper. Asking for PDF is also bitterly ironic in the context of QOI.

gman83 5y ago

How does it compare to WebP?

user-the-name 5y ago

Klasiaster 5y ago

Essentially good compression needs prediction. Here the previous pixels are used but it seems only from the row. Given that this is a linear decompression (not a progressive) it would help a lot to instead of looking just at the row, also look at the above row where the other previously seen neighbor pixels are. With something like arithmetic coding and only the previously seen neighbor pixels as prediction contexts with some tweaking one can quickly get better compression than PNG offers. Doing this in a short C implementation is left to the reader ;)

adgjlsfhk1 5y ago
the main downside of this is it pretty much requires storing a full row of the image in memory, while QOI only needs to store 66 pixels.

amelius 5y ago

My preferred image format looks like: byte 0-3: magic code byte 3-10: 64-bit index into global decoder table byte 11-...: compressed data The global decoder table is maintained by a standards organization. For every occupied index, it contains a piece of WebAssembly code that decodes the data and produces an image and metadata. Advantage: no more dealing with various image formats and installing decoders libs; there is just 1 format that can be tuned to specific uses and it will be available hundreds of years into the future. The WebAssembly code can be hand-optimized into native code (or even hardware) for frequently used decoders. The only downside is that you might occasionally need to access the central code repository over the internet to download a decoder.

mrob 5y ago
>and metadata You glossed over the most difficult part of the specification.
planck01 5y ago
Including a futureproof decoder in every single image is a huge filesize overhead though. Or maybe I don't exactly understand your proposal.
- amelius 5y ago
  The decoder-part is the same for many images, so the idea is to store them inside a standardized codebook that is pointed to from the data.
  - deleted 5y ago
    [deleted]
- xvector 5y ago
  IIUC he is saying that there will be a 64-bit index into a global standards-maintained table, and the decoder is downloaded from said table. Not that the decoder is actually included with the image. The decoder itself would probably eventually be cached if not shipped with browsers by default.

rsp1984 5y ago

Unfortunately not everything compresses well with QOI. I have considered using it for our company but then did some tests with real images from real (noisy, low-res) cameras. The result is that in many cases QOI did not offer much compression at all over just storing all the raw bytes and in some cases it even increased the size. The sample images that come with the download look well selected. I encourage everyone to try it on real data and see for themselves. Personally I was quite underwhelmed by the format and we are sticking with PNG for the time being.

eps 5y ago
> images from real (noisy, low-res) cameras But these won't compress well _losslessly_ in principle, would they? Or did you manage to find a format that did in fact work well?
- rsp1984 5y ago
  PNG works quite well on these kinds of images too.
  - eps 5y ago
    Do you have any specific examples you can share? PNG should not be able to compress noisy images well, because noise removes patterning. JPEG obviously can, but exactly because it is lossy.
    - lifthrasiir 5y ago
      PNG can't transform noisy images into something more compressible, but it uses better entropy coding compared to QOI.
- minimalc 5y ago
  I haven't evaluated this personally but the (close to?) lossless raw sensor image compression from Dotphoton [1] seems like an interesting approach for getting around the issue of sensor noise in image compression. However the implementation details are disappointly vague, as it's a proprietary product. [1]https://dotphoton.com/ https://dotphoton.com/

codazoda 5y ago

This format (or something similar) may work for my project. I’ve designed a set of low color images for a retro TRS-80 computer I own and would like to write a slot machine app for. With its low processing power and my self-imposed requirement to write it in the BASIC language I would have used as a kid, the machine doesn’t have a lot of processing power or memory to do decompression stuff. Some of the concepts here seem simple enough to implement. I can probably reduce it even farther since I have less colors.

yboris 5y ago

Awesome! Also, a PSA about the next image format for the web: JPEG XL (.jxl) - should be on everyone's radar. Already supported by browsers (behind a feature flag). Has lossy and lossless mode. https://jpegxl.info/ https://jpegxl.info/ https://cloudinary.com/blog/time_for_next_gen_codecs_to_dethrone_jpeg https://cloudinary.com/blog/time_for_next_gen_codecs_to_deth...

pornel 5y ago
It's worth adding that lossless JXL can be faster and compress better than QOI (at the same time == Pareto improvement). It basically obsoletes QOI. There are also special-case trimmed-down PNG encoders that are in the same league as QOI in terms of compression and simplicity.
- lifthrasiir 5y ago
  > lossless JXL can be faster and compress better than QOI It should be noted that it "can be", not it always is. The implementation in question [1] is currently experimental and not what you get from cjxl. In any case it is worth noting that QOI inspired both FPNG and FJXL. [1] https://github.com/libjxl/libjxl/tree/main/experimental/fast_lossless https://github.com/libjxl/libjxl/tree/main/experimental/fast...