2025/07/22
842 Compression Algorithmというものを見かけたので調べた。
基本的な情報は、https://github.com/plauth/lib842このGitHubリポジトリにまとまっている。
あとはリポジトリにリンクのあるIEEEの論文とリポジトリ内の実装を読めばよい。コメントしっかりしているのでC言語とかC++とかCudaとかしらないけれど、なんとなくわかる。
まずは、https://github.com/plauth/lib842/blob/43df3c87f3cd15acb325146589cc44c82f3b5d53/src/common/842.hのコメントを読んでいく。(英語で大体理解できるし、翻訳はAIがほぼやってる)
まず、圧縮したファイルは複数のブロックによって構成されていて、それらは以下のような形式となっている。
<template>[arg1][arg2][arg3][arg4]
引数の数は<template>によって異なり、0~4個存在する。基本的には出力バッファに追加する特定のデータバイトの値か、出力バッファにコピーする既に書き込まれたデータバイトの値である。
Template codeは5bitの値で、後続のデータをどのように扱うかを示している。0から0x19までのテンプレートコードは展開時に使用される静的な"decomp_ops" tableを使用する(should)。各テンプレート(table row)には、1から4つのアクションがあり、各アクションは後続の引数に対応する。各アクションは"data"型アクションまたは"index"型アクションのいずれかで、各アクションの結果として2, 4 or 8バイトが出力バッファに書き込まれる。各テンプレート（テーブル行のすべてのアクション）は、合計8バイトが出力バッファに書き込まれ、4個未満のアクションを持つ行は、N0で示されるnoop（何もしない）アクションでパディングされる（これに対する圧縮データバッファに対応する引数はない。）。
“Data"アクション（テーブルではD2, D4, D8で示される）は、対応する引数がそれぞれ圧縮データバッファ内の2, 4, 8バイトであることを意味し、出力バッファに直接コピーされる必要がある(should)。
“Index"アクション（テーブルでI2, I4, I8で示される）は、対応する引数が出力バッファ内の既存の2, 4, 8バイトの値を指すインデックスパラメータであることを意味し、この値は出力バッファの末尾にコピーされる必要がある。原則、インデックスは出力バッファデータの最後のNバイトを含むリングバッファ内の位置を指す。各インデックスの引数のビット数は：I2で8ビット、I4で9ビット、I8で8ビットである。各インデックスは2、4、または8バイトセクションを指すため、I2は512バイト（(2^8 bits) * 2 bytes）、I4は2048バイト（(2^9) * 4 bytes）、I8は2048バイト（(2^8) * 8 bytes）を参照できる。出力バッファに書き込まれる各バイトに対して更新される各I2、I4、I8は、一種のリングバッファと考えられる。この実装(今見てる842.h)では、各インデックスに対して出力バッファが直接使用され、追加のメモリは必要としない。インデックスはスライディングウィンドウではなくリングバッファへのものであることに注意。例えば、出力バッファに260バイトが書き込まれている場合、I2インデックス0は出力バッファのバイト256をインデックスし、I2インデックス16は出力バッファのバイト16をインデックスする。
さらに、3つの特別なテンプレートコードがある：0x1bは"repeat”、0x1cは"zeros”、0x1eは"end"である。“repeat"操作には、何回繰り返すかを示す6ビットの引数Nが続き、出力バッファに書き込まれた最後の8バイトが、出力バッファに再度N+1回書き込む。“zeros"操作は引数ビットがなく、出力バッファに8個のゼロを書き込む。“end"操作も引数ビットがなく、圧縮データの終了を知らせる。“end"操作ビットの後に、バッファ長を特定のバイト倍数（通常8, 16 or 32 bytesの倍数）に調整するため、いくつかのパディングビットがある場合がある（何でもよいが通常0）。
このソフトウェア実装では、未定義のテンプレート値の1つである0x1dを特別な"short data"テンプレートコードとして使用し、8バイト未満の非圧縮データを表わす。これには、何バイトのデータが続くかを示す3ビットの引数Nが続き、その後にNバイトのデータが続き、このデータは出力バッファにコピーされる必要がある。これにより、ソフトウェア842圧縮で8バイトの正確な倍数でない入力バッファを受け入れることができる。ただし、このソフトウェア専用テンプレートを含む圧縮バッファはハードウェアの842展開では拒否され、このソフトウェアライブラリで展開する必要がある。842ソフトウェア圧縮モジュールには、このソフトウェア専用の"short data"テンプレートの使用を無効にし、代わりに8バイトの倍数でない入力バッファを単純に拒否するパラメータが含まれている。
各操作コードのすべてのアクションが処理された後、次の5ビットに別のテンプレートコードがあり、“end"テンプレートコードが検出されると展開が終了する。
こんなところですね。
んで、この定義の実装を一応確認。
/* special templates */
#define OP_REPEAT (0x1B)
#define OP_ZEROS (0x1C)
#define OP_END (0x1E)
/* sw only template - this is not in the hw design; it's used only by this
* software compressor and decompressor, to allow input buffers that aren't
* a multiple of 8.
*/
#define OP_SHORT_DATA (0x1D)
/* additional bits of each op param */
#define OP_BITS (5)
#define REPEAT_BITS (6)
#define SHORT_DATA_BITS (3)
#define I2_BITS (8)
#define I4_BITS (9)
#define I8_BITS (8)
#define CRC_BITS (32)
#define REPEAT_BITS_MAX (0x3f)
#define SHORT_DATA_BITS_MAX (0x7)
/* Arbitrary values used to indicate action */
#define OP_ACTION (0x70)
#define OP_ACTION_INDEX (0x10)
#define OP_ACTION_DATA (0x20)
#define OP_ACTION_NOOP (0x40)
#define OP_AMOUNT (0x0f)
#define OP_AMOUNT_0 (0x00)
#define OP_AMOUNT_2 (0x02)
#define OP_AMOUNT_4 (0x04)
#define OP_AMOUNT_8 (0x08)
#define D2 (OP_ACTION_DATA | OP_AMOUNT_2)
#define D4 (OP_ACTION_DATA | OP_AMOUNT_4)
#define D8 (OP_ACTION_DATA | OP_AMOUNT_8)
#define I2 (OP_ACTION_INDEX | OP_AMOUNT_2)
#define I4 (OP_ACTION_INDEX | OP_AMOUNT_4)
#define I8 (OP_ACTION_INDEX | OP_AMOUNT_8)
#define N0 (OP_ACTION_NOOP | OP_AMOUNT_0)
/* the max of the regular templates - not including the special templates */
#define OPS_MAX (0x1a)
/* Extended definitions - used by the optimized implementations */
#define D2_BITS (16)
#define D4_BITS (32)
#define D8_BITS (64)
#define N0_BITS (0)
/* Extended definitions - used by the optimized, branch-free implementations */
#define OP_DEC_NOOP (0x00)
#define OP_DEC_DATA (0x00)
#define OP_DEC_INDEX (0x80)
#define OP_DEC_N0 {(N0_BITS | OP_DEC_NOOP), 0}
#define OP_DEC_D2 {(D2_BITS | OP_DEC_DATA), 2}
#define OP_DEC_D4 {(D4_BITS | OP_DEC_DATA), 4}
#define OP_DEC_D8 {(D8_BITS | OP_DEC_DATA), 8}
#define OP_DEC_I2 {(I2_BITS | OP_DEC_INDEX), 2}
#define OP_DEC_I4 {(I4_BITS | OP_DEC_INDEX), 4}
#define OP_DEC_I8 {(I8_BITS | OP_DEC_INDEX), 8}
そしたら、実際の圧縮処理を見ていく。
src/serial_optimized/842_compress.cppとかsrc/serial/842_compress.cそのままではある。ただ、自分はCとかC++を読むのはほぼ初めてなのでちょっと面白かった。なんとなくで大体読めるのだけれど、goto文という概念が今までなかったので、そこだけ初見だった(あとビット演算すらすら読めないくらい)。とはいえ、アセンブリでジャンプという概念は得ているので、それと同じ要領と認識した。
whileで8bytesずつ取り出して、まず一個前と全く一緒じゃないかを確認した上で、process_next内(のcheck_templateのcheck_indexのfind_index)でhashtableと突き合わせている。ヒットしたりしなかったり、それぞれ定義したテンプレートに沿って組んで、最後に追加する。
それだけ。
2025/08/02_20:02:30
とりあえず、これで公開したいと思う。他の方式と圧縮率とか比べられたらいいんだけど、また機会があれば。