QOI 圖片無損壓縮演算法

Hacker News Daily 上看到「Lossless Image Compression in O(n) Time」這篇,作者丟出了一個圖片的無損壓縮演算法,壓縮與解壓縮的速度超快,但壓縮率又不輸 PNG 太多,在 Hacker News 上的討論也可以看一下:「QOI: Lossless Image Compression in O(n) Time (phoboslab.org)」。

裡面有提到在遊戲產業常用到的 stb_image.h

Yes, stb_image saved us all from the pains of dealing with libpng and is therefore used in countless games and apps. A while ago I aimed to do the same for video with pl_mpeg, with some success.


My name is Dominic Szablewski. I build games, experiment with JavaScript and occasionally tinker with low-level C.

圖片的無損壓縮與解壓縮算是遊戲創作者蠻常用到的功能,所以他想要看看這塊有沒有機會有更好的工具,於是他就用了四個很簡單的演算法幹完了 QOI (然後發現效果很讚):

  • A run of the previous pixel
  • An index into a previously seen pixel
  • The difference to the previous pixel
  • Full rgba values

其實從 Hacker News 的討論也可以看到這組演算法也常被拿出來在現代的壓縮演算法使用,所以雖然作者自稱不是 compression guy,但他用的演算法其實蠻專業的...

然後挑 single thread 主要是可以避免 threading 的複雜度以及 overhead,在「QOI Benchmark Results」這頁可以看到,無論是什麼類型的檔案,壓縮與解壓縮的速度都相當漂亮,而且壓縮率又沒有差 libpng 太多。

而且作者自己有提到,還沒用到 SIMD 指令集加速,這樣猜測應該還有不少空間...

libpng 漏洞...

libpng 的安全性問題,CVE-2015-8126

Multiple buffer overflows in the (1) png_set_PLTE and (2) png_get_PLTE functions in libpng before 1.0.64, 1.1.x and 1.2.x before 1.2.54, 1.3.x and 1.4.x before 1.4.17, 1.5.x before 1.5.24, and 1.6.x before 1.6.19 allow remote attackers to cause a denial of service (application crash) or possibly have unspecified other impact via a small bit-depth value in an IHDR (aka image header) chunk in a PNG image.


Google 將發現安全問題的獎勵延伸到 Open Source 專案上...

Slashdot 上看到 Google 將發現安全問題的獎勵從自家產品延伸到 Open Source 專案上:「Google Offers Cash For Security Fixes To Linux and Other FOSS Projects」。

官方的公告在「Going beyond vulnerability rewards」,規則則是在「Patch Rewards – Application Security – Google」。


  • Core infrastructure network services: OpenSSH, BIND, ISC DHCP
  • Core infrastructure image parsers: libjpeg, libjpeg-turbo, libpng, giflib
  • Open-source foundations of Google Chrome: Chromium, Blink
  • Other high-impact libraries: OpenSSL, zlib
  • Security-critical, commonly used components of the Linux kernel (including KVM)

獎勵金額從 USD$500 到 USD$3133.7,這邊的 31337 應該是出自「Leet」吧...