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 指令集加速,這樣猜測應該還有不少空間...

在 command line 下生出全灰的圖片

因為需要一張 1920x1080 全灰色的圖片,翻了一下 DuckDuckGo 找到這篇:「Linux create Image pixel by pixel in command line」。

裡面抓重點,主要的想法是 PPM 格式 (可以參考「Netpbm」這個條目),然後找到「PPM Format Specification」這份文件。

主要就是用 P3 模式下去產生檔案:

repeat 2073600 echo '127 127 127' >> grey.ppm

然後開頭的地方修一下,加上 P3、長寬資訊以及最大的值:

P3
1920 1080
255

接著就用 ImageMagick 轉檔:

convert grey.ppm grey.png

然後用 viewer 看一下,確認沒問題就收工了...

RFC 3339 與 ISO 8601 用範例的比較

Hacker News 首頁上看到「RFC 3339 vs. ISO 8601 (ijmacd.github.io)」這個連結,原始網站是「RFC 3339 vs ISO 8601」。

兩個都是試著定義日期與時間的表達方式,其中 ISO 8601 是在 1988 年定義出來的,被廣泛應用在很多 spec 裡,但最大的問題就是 ISO 8601 沒辦法公開免費取得,這點在前幾個月也在 Hacker News 上被討論過:「ISO-8601 date format reference not publicly available (twitter.com/isostandards)」。

RFC 3339 是在 2002 年訂出來,其中一個目標就是試著解決 ISO 8601 不公開的問題 (沒講明就是了):

This document includes an Internet profile of the ISO 8601 [ISO8601] standard for representation of dates and times using the Gregorian calendar.

這份 RFC 3339 與 ISO 8601 的比較可以讓設計 spec 的人可以看一下,在大多數的情況下,RFC 3339 應該是夠用的...

為資料庫提案新的 UUID 格式

前幾天在 Hacker News Daily 上看到的東西,今年四月的時候有人針對資料庫提案新的 UUID 格式:「New UUID Formats – IETF Draft (ietf.org)」。

在 draft 開頭有說明這個提案的目標:

This document presents new time-based UUID formats which are suited for use as a database key.

A common case for modern applications is to create a unique identifier for use as a primary key in a database table. This identifier usually implements an embedded timestamp that is sortable using the monotonic creation time in the most significant bits. In addition the identifier is highly collision resistant, difficult to guess, and provides minimal security attack surfaces. None of the existing UUID versions, including UUIDv1, fulfill each of these requirements in the most efficient possible way. This document is a proposal to update [RFC4122] with three new UUID versions that address these concerns, each with different trade-offs.

另外在 Hacker News 上有人整理出來,可以直接理解提案所提出的新格式是什麼:

A somewhat oversimplified summary of the new UUID formats:

UUID6: a timestamp with a weird epoch and 100 ns precision like in UUID1, but in a big-endian order that sorts naturally by time, plus some random bits instead of a predictable MAC address.

UUID7: like UUID6, but uses normal Unix timestamps and allows more timestamp precision.

UUID8: like UUID7, but relaxes requirements on where the timestamp is coming from. Want to use a custom epoch or NTP timestamps or something? UUID8 allows it for the sake of flexibility and future-proofing, but the downside is that there's no standard way to parse the time from one of these -- the time source could be anything monotonic.

這在不同的 storage engine 上面會有不同的討論,這邊先討論 MySQL 系列的 InnoDB,至於 PostgreSQL 的 engine 以及其他資料庫系統,就另外讓更熟悉的人討論了。

InnoDB 採用了 clustered index (可以參考「Database index」這邊的說明),也就是資料本體是以某種定義的大小順序存放。

在 InnoDB 裡面則是用 primary key 的順序來存放資料 (沒有指定 primary key 時會有 fallback 行為),其他的 unique key 與 index key 則是指到 primary key,所以你可以看到 primary key 的大小也會影響到其他的 index key。

所以 128 bits 的 UUID 在大型的 MySQL ecosystem 實在不怎麼受歡迎,在 2010 年的時候 FlickrTwitter 都有發表過 ticket system:「Ticket Servers: Distributed Unique Primary Keys on the Cheap」、「Announcing Snowflake」,兩個系統有不同的需求,但都是產生 64 bits 的 unique id。

其中 Flickr 的系統算是很簡單的,沒有要保證時間順序 (i.e. 先取的號碼一定比較小,以及後取的號碼一定比較大),就用兩台 MySQL 跑 active-active 架構,然後錯開產生的值:

TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1

TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2

到現在還是一個蠻簡單的解法...

GitHub 的 API Token 換格式

GitHub 前幾天宣佈更換 API token 的格式:「Authentication token format updates are generally available」,在今年三月初的時候有先公告要換:「Authentication token format updates」。

另外昨天也解釋了換成這樣的優點:「Behind GitHub’s new authentication token formats」。

首先是 token 的字元集合變大了:

The character set changed from [a-f0-9] to [A-Za-z0-9_]

另外是增加了 prefix 直接指出是什麼種類的 token:

The format now includes a prefix for each token type:

  • ghp_ for Personal Access Tokens
  • gho_ for OAuth Access tokens
  • ghu_ for GitHub App user-to-server tokens
  • ghs_ for GitHub App server-to-server tokens
  • ghr_ for GitHub App refresh tokens

另外官方目前先不會改變 token 長度 (透過字元變多增加 entropy),但未來有打算要增加:

The length of our tokens is remaining the same for now. However, GitHub tokens will likely increase in length in future updates, so integrators should plan to support tokens up to 255 characters after June 1, 2021.

看起來當初當作 hex string 而轉成 binary 會有問題,不過就算這樣做應該也是轉的回來的。

回到好處的部份,這個作法跟 SlackStripe 類似,讓開發者或是管理者更容易辨識 token 的類型:

As we see across the industry from companies like Slack and Stripe, token prefixes are a clear way to make tokens identifiable. We are including specific 3 letter prefixes to represent each token, starting with a company signifier, gh, and the first letter of the token type.

另外這也讓 secret scanning 的準確度更高,本來是 40 bytes 的 hex string,有機會撞到程式碼內的 SHA-1 string:

Many of our old authentication token formats are hex-encoded 40 character strings that are indistinguishable from other encoded data like SHA hashes. These have several limitations, such as inefficient or even inaccurate detection of compromised tokens for our secret scanning feature.

另外官方也建議現有的 token 換成新的格式,這樣如果真的發生洩漏,可以透過 secret scanning 偵測並通知:

We strongly encourage you to reset any personal access tokens and OAuth tokens you have. These improvements help secret scanning detection and will help you mitigate any risk to compromised tokens.

還原被碼掉的 PEM 資訊 (SSH RSA key)

在「Recovering a full PEM Private Key when half of it is redacted」這邊看到的,起因是 _SaxX_ 幫客戶做滲透測試時找到客戶公開在網路上的 SSH key,然後他就碼掉一部分貼出來:

原圖是這樣,接下來就開始被還原 XD

首先是 OCR 的過程,被稱為是整個還原過程最難的一部分 (哭爸啊):

Ironically, this was the hardest part of the challenge. It took the longest time of all the steps and was the easiest to make errors in.

接下來就是解讀 PEM 檔的格式,可以藉此得到裡面的參數。

然後是套公式,窮舉運算裡面的值,可以看到迴圈 kp 只算了 365537,就推算出可能的 p

e = 65537
q = 0xc28871e8714090e0a33327b88acc57eef2eb6033ac6bc44f31baeac33cbc026c3e8bbe9e0f77c8dbc0b4bfed0273f6621d24bc1effc0b6c06427b89758f6d433a02bf996d42e1e2750738ac3b85b4a187a3bcb4124d62296cb0eecaa5b70fb84a12254b0973797a1e53829ec59f22238eab77b211664fc2fa686893dda43756c895953e573fd52aa9bb41d22306135c81174a001b32f5407d4f72d80c5de2850541de5d55c19c1f817eea994dfa534b6d941ba204b306225a9e06ddb048f4e34507540fb3f03efeb30bdd076cfa22b135c9037c9e18fe4fa70cf61cea8c002e9c85e53c1eaac935042d00697270f05b8a7976846963c933dadd527227e6c45e1
dp = 0x878f7c1b9b19b1693c1371305f194cd08c770c8f5976b2d8e3cf769a1117080d6e90a10aef9da6eb5b34219b71f4c8e5cde3a9d36945ac507ee6dfe4c146e7458ef83fa065e3036e5fbf15597e97a7ba93a31124d97c177e68e38adc4c45858417abf8034745d6b3782a195e6dd3cf0be14f5d97247900e9aac3b2b5a89f33a3f8f71d27d670401ca185eb9c88644b7985e4d98a7da37bfffdb737e54b6e0de2004d0c8c425fb16380431d7de40540c02346c98991b748ebbc8aac73dd58de6f7ff00a302f4047020b6cd9098f6ba686994f5e043e7181edfc552e18bce42b3a42b63f7ccb7729b74e76a040055d397278cb939240f236d0a2a79757ba7a9f09

for kp in range(3, e):
    p_mul = dp * e - 1
    if p_mul % kp == 0:
        p = (p_mul // kp) + 1
        if isPrime(p):
            print(f"Possible p: {p}")

後面就是跑驗證確認,就被打出來了...

Firefox 86 預設支援 AVIF 影像格式

在「Firefox 86: AVIF support enabled by default」這邊看到的消息,在 Firefox 86 (目前是 nightly) 預設啟用了 AVIF 影像格式,這是繼「Chrome 85 支援 AVIF」後另外一個主要的瀏覽器也跳下來支援了,大概再幾個月後就會推到 stable channel 上了。

不過想測試的人不用去裝 nightly,77 之後的版本已經支援,只是預設沒有啟用,可以透過 image.avif.enabled 開起來。

另外當初在「WebP 的檔案大小未必比 JPEG 小...」這邊剛好也有帶到 AVIF 的壓縮率不錯,不過演算法判斷非重點部位的細節會被吃掉,這點對於一般的網頁應該還好,但對於希望還是保留細節的網站,也許就不是那麼適合了...

Amazon Transcribe 可以吃其他格式了

Amazon TranscribeAWS 推出語音轉文字的服務,先前只有提供 WAVFLACMP3MP4 格式,現在則是多支援不少格式:

Today, we are excited to announce native support for media files in AMR, AMR-WB, Ogg and WebM format by Amazon Transcribe.

AMRAMR-WB 以前還蠻常看到的,最近比較少看到了,可能是專利加上選擇性多之後用的人就變少了。

再來是 OggWebM 兩個都是開放格式。

上次拿 Amazon Transcribe 測日文的影片,先用 FFmpeg 把 MP4 檔內的 audio track 抽出來再丟上去轉,轉完後用 andyhopp/aws-transcribe-to-srt 把 Amazon Transcribe 輸出的 JSON 再轉成 SRT 檔,就辨識正確度測起來算是堪用,但專有名詞 (像是人名) 就得另外處理,不過比什麼都沒有好不少...

用 picture + source + img 替代本來的 JavaScript 替換

目前我在 blog 上使用 Imgur 的圖檔主要是用 WebP 格式,然後針對不支援 WebP 的瀏覽器 (主要就是蘋果家的 Safari) 是用 JavaScript 換回 JPEG 格式...

昨天早上看到「AVIF has landed」這篇,提醒我有 <picture> 這個原生支援的方式可以用,翻了一下 Can I Use 上面的支援程度,看起來除了 IE11 以外幾乎都支援了 (參考「Picture element」),而且 IE11 應該也會因為語法的關係走到正確的 JPEG fallback,大概是這樣:

<picture>
    <source type="image/webp" srcset="https://i.imgur.com/xxxxxx.webp" />
    <img src="https://i.imgur.com/xxxxxx.jpg" alt="" />
</picture>

換完後來觀察看看...

MariaDB 的 S3 Engine 效能測試

PerconaMariaDB 在 10.5 (目前的最新穩定版) 裡出的 S3 Engine 給出了簡單的測試報告:「MariaDB S3 Engine: Implementation and Benchmarking」。

這個 engine 顧名思義就是把資料丟到 Amazon S3 上,目前是 alpha 版本,預設是不會載入的,需要開 alpha flag 才能用:

The S3 engine is READ_ONLY so you can’t perform any write operations ( INSERT/UPDATE/DELETE ), but you can change the table structure.

另外這是從 Aria 改出來的 read-only engine,而 Aria 是從 MyISAM 改出來的:

The S3 storage engine is based on the Aria code and the main feature is that you can directly move your table from a local device to S3 using ALTER.

測出來發現在 read-only 的情境下,COUNT(*) 超快,看起來就是跟 MyISAM 體系有關,直接撈 MyISAM 內的資料,所以本地要 18 秒,但放到 S3 反而秒殺 XDDD

整體看起來還不錯?算是一種 Data warehouse 的方案,主要是要用到 row-based format 儲存的優點,遇到一些冷資料可以這樣玩。

從「Using the S3 Storage Engine」這邊的設定方式看到 s3_host_name,看起來有機會接其他家的 S3 API,或是本地的 Storage。

話說 Aria 這個引擎當初最主要的重點就在 crash-safe,在有了 crash-safe 之後,DRBD 這種 block-level replication 機制就可以硬幹上去,後來主力就在擴充其他型態了,像是 GIS 與 virtual column 的功能,不過這些功能本家在 InnoDB 上好像也都陸陸續續跟上來了,單純的 Aria engine 好像還好...