HEICデコーダーをSHA-256コンピュータに変換する

HEICデコーダーをSHA-256コンピュータに変換する

［画像: Appleの標準ImageIOでデコードされた最終フレーム、HEICファイルのSHA-256を表示］

最終的にImageIOでデコードされた画像は、それ自体を含む正確なHEICバイト列のSHA-256を表示します。

前回の記事last articleでは、JPEG XLデコーダーを人工的なCPUに変換し、初のJXL SHA-256 ハッシュクインを構築しました。今回はHEICでこれを実現しました。JXLよりもはるかに困難でした。JXLデコーダーは決定木とタグ付けされた31ビットワードを提供しますが、HEVCはピクセルとモーションベクトルを提供するため、エンコーダーをパッチする代わりに、コンパイラを一から書き直すことになりました。

正確な536,870,946バイトのファイルは、このSHA-256を持ちます。

802cc6d654ad15aafbb1ca5db4824292cc39fd72cf23fd80e1230d90679b9ff1

同じファイル内の最終画像を標準のApple ImageIOでデコードすると、そのピクセルは以下のように表示されます。

802cc6d654ad15aa
fbb1ca5db4824292
cc39fd72cf23fd80
e1230d90679b9ff1

これら二つの値は同一であり、文字はデコード自体から来ています。HEVCデコーダーは、SHA-256メッセージスケジュールと64回の圧縮ラウンドを実行する564ピクセルの計算を再構築し、フィードフォワードを行い、ダイジェストビットを16進数に変換し、フォントROMを評価し、結果を最後のピクセルに描画します。私たちのコンパイラがファイルを書き、Appleの標準デコーダーがそれを実行します。

表示に関する注意。 Apple ImageIOは564ピクセルすべてを報告し、ピクセル563（上記の最終ゼロベースインデックス）を正しくデコードします。一部の写真ライブラリUIは、画像シーケンスのポスターフレームとしてピクセル0を選択します。そのピクセルは意図的にほとんど灰色の計算サーフェスです。ハッシュクインの主張と検証は、最終的にデコードされたピクセルに関するものです。

画像デコーダーは小さな言語のインタープリター

ウィアードマシンとは、システムの通常の状態遷移が、設計者が意図しなかった方法でプログラム可能であることが判明した場合に得られるものです。パーサー、デコンプレッサー、または画像デコーダーは、既に言語を読み取り、入力が選択するルールに従って状態を更新します。ロジック、ストレージ、および順序が与えられれば、ファイルは単なるコンテンツではなく計算を記述でき、その計算は文書化された動作のみに乗ることができます。

最もよく知られている例は、NSO GroupのゼロクリックiMessageエクスプロイトであるFORCEDENTRYです。Project Zeroの言葉を借りれば、「70,000以上のセグメントコマンドで論理ビット演算を定義することにより、レジスタや完全な64ビット加算器および比較器のような機能を備えた小さなコンピュータアーキテクチャを定義しました。」彼らのマシンはJBIG2画像操作で動作し、開始にはメモリ破壊バグが必要でした。私たちのマシンは、文書化されたデコーダーの動作で、最初から最後まで動作します。

HEVCでは、イントラ予測はデータをローカルに移動させ、残差は正確な補正を適用し、ラスター順序は因果関係を強制し、PCMは入力アパーチャを提供し、インター予測はピクセル間でデータを移動させ、最終的なルマサンプルが出力となります。

［画像: マシンコンポーネントにマッピングされたHEVCメカニズム］

通常のHEVC再構築ツールは、コンパイラがそれらにマシンの役割を割り当てると、ワイヤー、状態、タイミング、入力、および出力になります。

このマシンは有限で固定プログラムです。SHA-256圧縮1回とグリフレンダリング、約15万個の2入力ゲートで、ストレージ、ブール論理、モジュラ加算、ルーティング、および時間のみが必要です。デコーダーが無限の汎用コンピュータをホストできるかどうかは、1つの合法的なファイルがそれを特定の64ラウンド回路を評価させることができるかどうかという問題とは別の問題です。私たちは後者の問題に答えました。

HEIC、HEIF、および使用したデコーダーサーフェス

HEIF (ISO/IEC 23008-12) は、.mp4 と同じネストボックス構造を持つISO Base Media File Format上に構築されたコンテナです。「HEIC」は、ピクセルがHEVCコーディングを使用するHEIFファイルの拡張子です。AppleはiOS 11とmacOS High Sierraでシステムサポートをリリースし、それをデフォルトのiPhone写真フォーマットにし、ImageIOでデコードします。これが私たちのテストターゲットです。

HEIFファイルは、ピクセルを2つの方法で保持できます。最終的な成果物は2番目の方法を使用します。

HEIF静止画

ftyp: heic, mif1->meta: pitm, iinf, iloc, iprp->mdat: 1つのHEVCピクセル

HEIF画像シーケンス（私たちのファイル）

ftyp: msf1, hevc->moov / trak / stbl: hvc1, stsz, stco (564サンプル用)->mdat: 564個のHEVCピクセル、任意の物理的順序で

「任意の物理的順序」が自己参照を機能させる鍵となります。後述します。

HEVCはブロックからピクセルを再構築します。私たちの目的では、セルは4つの4x4予測ユニットを含む1つの8x8ルマコーディングユニットです。イントラコード化されたユニットは、既に再構築された北、西、または北西のサンプルを読み取る予測子を選択し、その後、コード化された残差を適用します。Pピクセルは代わりに、前のピクセルからサンプルをコピーするためにモーション補償を使用できます。

->32x32 CTU: 8x8 CU、4つの4x4 PU

->予測

->再構築されたサンプル（北/西/北西）から

->前のピクセルから、モーションベクトルで変位

->ビットストリームに格納された生のサンプル

デコーダーを正確に予測可能な構成に固定します。cu_transquant_bypassにより残差はロスレスで加算され、PCMは生の文字列表現、デブロッキングおよびSAOフィルターはオフです。すべての出力サンプルは、参照の正確な整数関数となり、私たちの予測子のソフトウェアモデルはデコーダーとビット単位で一致します。それがなければ、「ピクセルがハッシュに等しい」という主張は決して成り立ちません。

北、西、および前のピクセルの参照は、物理的なマシンを定義します。ブロックは既にデコードされたものしか読み取れないため、情報は東と南に流れます。値を西に移動させるには、行ごとに1セルかかり、Z順序が右上参照を露出させる場合にのみ可能です。値を維持するには、存続する行ごとに1列かかります。東と南は安価で、西は高価で、状態は家賃を払います。この3つの事実は、後続のすべてを形作ります。

コンパイラはビットストリームを直接生成します。VPS、SPS、PPS、スライス、予測モード、残差係数、モーションベクトル、PCMブロック、CABACビン、そして最後にHEIFボックスとサンプルテーブルです。デコーダーは標準のままで、コーデック機能は標準のままで、エンコーダーは私たちのものです。商用エンコーダーはエラーを最小限に抑えるためにモードを選択しますが、私たちはすべてのモード、残差、およびモーションベクトルを指示する必要がありました。

AIコーディングシステムのための有用なベンチマーク

このプロジェクトは、コーディングエージェントのベンチマークとしても役立ちました。CodexのGPT-6 UltraとClaude CodeのClaude Opus 5.5での試行を通じて、エージェントは繰り返しターゲットは不可能だと宣言しました。動作する中間成果物を見せられた後でも、いくつかのエージェントは同じ失敗した単一ピクセル仮説に戻りました。

SHA-256の計算は簡単な部分でした。実際の作業は、証拠がそれらを殺したときに抽象化を捨てることでした。ピクセルは信号トラックになり、トラックはシストリックアレイになり、値は仮想レジスタになり、1つのピクセルはデコーダー供給の状態バスを持つ画像シーケンスになりました。一日中コードを生成できたエージェントでさえ、そこで失敗しました。なぜなら、ボトルネックは物理的な証拠に対して間違った仮説を修正することだったからです。

PXFのヒント：状態をステージを通して流す

有用なアナロジーは、CiscoのParallel eXpress Forwardingの作業から得られました。彼らのPXFネットワークプロセッサ、「トースター」というニックネームで呼ばれるものは、4x4グリッドに16個のパケットCPUを配置しました。パケットはパイプラインとして行に沿って移動し、列はシフトフェーズで並列に実行されました。Ciscoの特許はそれをシストリックアレイパイプラインとして説明しています。各ステージはレジスタファイルと機能ユニットを持ち、コンテキストを処理し、次のステージに渡します。

その背後にある古いアイデアは、H. T. Kungの「なぜシストリックアーキテクチャなのか？」です。計算を正規のローカルステージにマッピングし、データを移動させ続けます。それはランダムアクセスのCPUを持っているふりをするよりも優れていました。それは問題自体を解決しませんでしたが、適切な質問を与えてくれました。

• パケットコンテキストとは何か？ 128バイトの永続的なSHAレジスタバンクです。
• ステージとは何か？ 1つの制限付きHEVC Pピクセルです。
• バイパスパスとは何か？ イントラ予測ワイヤーとインターピクセルモーションコピーです。
• レジスタ依存関係はどこにあるか？ コンパイラのスロットマップとチェックポイントオブジェクトにあります。
• グローバルクロスバーを避けるにはどうすればよいか？ 値をローカルに配置し、名前を変更し、制限付き再パッキングステージを挿入します。

FPGAとROMエクスプロイトの経験は、同じ理由で役立ちました。この作業は、ソフトウェアを書くというよりは、固定機能ファブリックのタイミングをクロージングするようなものでした。より小さなブール式でも、長いワイヤーを追加したり、参照サンプルを消費したり、他のルートをラスターから締め出したりすると、物理的には悪くなる可能性がありました。

JXLよりもHEICがはるかに困難だった理由

JXLは寛大なプリミティブを提供しました。明示的な分岐を持つメタアダプティブツリー、タグ付けされた31ビット値、ルックアップのようなリーフ、数十の状態チャネル、および厳格なチャネル/ラスタースケジュールです。私たちは大きな有限マッピングを1つの画像にコンパイルし、オプションのチャネルをワイドな状態レーンとして扱いました。

HEVCは、より小さく、より物理的なピースを提供しました。

• ワイドなタグ付きワードではなく、再構築されたサンプル。
• 任意のチャネル読み取りではなく、ローカルな北、西、および対角線の依存関係。
• 大きな決定木ではなく、固定された予測子ジオメトリ。
• ピクセル内での厳格な将来参照なしルール。
• Apple ImageIOでの実用的なデコード次元制限。
• 構成時に孤立したプリミティブの動作を変える参照サンプル境界効果。
• すべての長いイントラ予測パスを正確に維持しない任意のバイト値。

次元制限は厳しく、測定しました。clap（クリーンアパーチャ）クロップでHEIFにラップされたソリッドテストピクセルをサイズを増やしながらエンコードし、Core Graphics/ImageIO経由でメモリにデコードしました。

形状に関わらず、1つのコード化されたピクセルは最大2^30サンプルを保持できます。クロップがない場合、出力バッファは2^29付近で失敗します。SHA-256の1つのフラットピクセルには、その約10倍が必要です。

したがって、コンパイラはデジタルデザインとバックエンドコンパイラ作業からの問題を解決する必要がありました。セル特性評価、論理合成、レジスタ割り当て、ライブネス、配置、ルーティング、クロスオーバー、キャリー伝播、バンク割り当て、モーションベクトル到達可能性、および物理検証です。

最初に役立ったメンタルモデルは、時空間図として描かれた一次元セルオートマトンでした。列は信号トラック、行は時間です。各コーディングユニットは、合法的な北/西/北西の隣接要素を読み取り、ローカル遷移を適用し、一度だけ書き込みます。SHA-256は固定レートとデータ非依存制御を持つため、同期データフローにも適合します。ラウンドごとのトークン数はコンパイル時にわかります。

3つのレイアウト法則が続きました。

1. 各ライブビットを可能な限り長く既知の垂直トラック上に保持する。
2. トランスポートをローカルにし、単一の均一な因果せん断に従う。
3. キャリーを時間または専用のローカル波面を通して移動させる。キャンバス全体を繰り返し収集しない。

実際の命令セットの発見

ソフトウェアモデルで関連するすべての入力組み合わせを再構築することにより、各候補セルを特性評価し、構成とAppleデコードを生き残ったセルのみを昇格させました。

ブール代数は狭いです。128はゼロ、129は1です。ゲートは、HEVC予測が持つ唯一の非線形性である整数丸めとクリッピングから来ています。DCモードを取ってみましょう。これは参照サンプルを平均化します。

dc = (sum_x T_x + sum_y L_y + N) >> (log2 N + 1)

単一の4x4 DCユニットに北参照[128+a, 128+a, 128+b, 128]と西参照[128+b, 128+c, 128+c, 128]を与えると：

dc = 128 + floor((2(a+b+c) + 4) / 8) = 128 + [a+b+c >= 2] = 128 + Maj(a,b,c)

DCの丸めは多数決です。垂直モード26は、pred[0][y] = T_0 + ((L_y - T_NW) >> 1)で最初の列を補正します。T_0 = 129、L_y = 128、T_NW = 128 + aとすると、129 + (-a >> 1) = 128 + (1-a)となり、これは正確なNOTです。セルライブラリはこれらを直接記録します。

// src/cells.hpp
//   NOT   1つの4x4 PU、モード26（または10）：ゼロ角度エッジ補正
//         T0 + ((L[y]-TL)>>1) で T0=129, L=128, TL=128+a は 129-a を与える。
//   MAJ   1つの4x4 DC PU：北 [a,a,b,128]、西 [b,c,c,128] -> 一様
//         128+Maj(a,b,c) (DCの+4丸めが閾値)

1ビットレジスタは、8x8コーディングユニットの南サンプルx=3に存在します。水平パケットは、東サンプルy=4,5,6を使用します。この分離により、最初の決定的なプリミティブ、つまり実際のクロスオーバーが得られました。

// src/point_fabric.hpp
inline hevc::CU hold()  { return hevc::nxn_cu({26,26,26,26}); } // 垂直ビットを保持
inline hevc::CU cross() { return hevc::nxn_cu({ 2,18,34,11}); } // 垂直信号と水平信号をクロスさせる
inline hevc::CU read()  { return hevc::nxn_cu({27,18,34,34}); } // 水平レーンにブロードキャスト
inline hevc::CU write() { return hevc::nxn_cu({27,27,16, 2}); } // 水平値を垂直レジスタに書き込む

inline hevc::CU gate(bool is_and, bool forward_result=false) {
    std::array<int,64> residual{};
    residual[31] = 1;
    if (is_and) residual[30] = -1;
    return hevc::nxn_cu(
        {2,18,33,forward_result ? 2 : 11}, residual);
}

以前の網羅的な検索では、単一セルでのクロスオーバーは存在しないと結論付けられました。なぜなら、両方の信号がサンプルレーンを共有する必要があると静かに仮定していたからです。それらに別々のレーンを与えると、セルが存在します。

［画像: 直交レーン交差セル］

垂直レジスタと水平パケットは、1つの8x8コーディングユニット内の異なるサンプルレーンを占有します。

crossを使用すると、独立した水平オペランドが同じ8x8ユニットを通過する間、垂直レジスタは維持されます。ファブリックは、平面的なブロックワイヤーの絡み合いではなく、小さな粗粒度再構成可能アレイになります。

動作するプリミティブセットは以下のようになりました。

観測可能な境界サンプルで各プリミティブをチェックし、単独では機能するがタイル化すると失敗するいくつかの設計を捕捉しました。

初の完全なコンパイラと110億ピクセル壁

クロスオーバーセルにより、完全なSHAグラフを1つのピクセルにコンパイルできました。フロントエンドはワードレベルのDAGを構築しました。

enum Op { INPUT, CONST, XOR, AND, OR, ADD };

struct Word {
    int id;
    int rotate = 0;   // 表示用、コピーデータではない
    int shift  = 0;
};

Word sigma(Word x, int a, int b, int c, bool small=false) {
    return gate(XOR,
                gate(XOR, rotate(x,a), rotate(x,b)),
                small ? shift(x,c) : rotate(x,c));
}

重要なのは「表示」という言葉です。回転は仮想値のタグであり、コンパイラは物理的に回転したコピーを構築するのではなく、コンシューマーがそれを読み取るときにビットからトラックへのマッピングを変更します。ポインタ算術やレジスタリネーミングと同じ考え方です。

加算はローカルなリップルキャリーアダーを使用しました。ビットjの場合、伝播と生成は以下のようになります。

P_j = A_j XOR B_j,    G_j = A_j AND B_j

その後、リップルします。

C_{j+1} = G_j OR (P_j AND C_j),    S_j = P_j XOR C_j

ファブリックのフォワードリザルトゲートにより、すべての32回のキャリーステップが水平波面として1つのCU行を共有できます。オペランド準備とXORマクロを使用すると、1つの32ビット加算は約20 CU行を要します。

完全な単一ピクセル低下は再構築オラクルで機能しました。1ラウンドはデコード精度で、すべての2,176個のプローブされたサンプルがソフトウェアSHA-256と一致し、4つの連鎖ラウンドがすべての7,808個のプローブで一致しました。しかし、それは絶望的に大きすぎました。

幅:     1,040 コーディングユニット
高さ:  168,129 コーディングユニット行
ピクセル:   8,320 x 1,345,032 = 11.19 十億

［画像: 失敗した単一ピクセルレイアウトの測定コスト］

単一ピクセルコンパイラは、その行の91パーセントをSHA-256算術の評価ではなく、値の移動に費やしました。

高さの9パーセントが算術でした。残りの91パーセントはビットの移動でした。

アロケータは、スピルメモリのないレジスタアロケータのように動作しました。結果ブロックを東にバンプアロケートし、値が消滅した場所に穴を残し、フロンティアがエッジに達すると、compact()はすべてのライブレジスタを長い階段を通して西にウォークしました。オペランドコピーは、32個の独立してルーティングされたビットを新しいストライド4ブロックに収集しました。ピークライブネスは約832ビットでした。これは16ワードのスケジュールウィンドウ、8つのワーキングワード、および一時変数です。

インターバルバッチコピー、ファーストフィットホール再利用、均一ストライド4ストレージ、代替Ch/Maj形式、およびキャリーセーブ実験を試しました。これらは個々のケースを助けましたが、何も変えませんでした。最後に測定されたバージョンは、依然として92億6千万ピクセル、つまり2^30の天井の8.6倍を必要としました。

教訓：物理コストモデルを最適化する。代数式の数は間違ったターゲットです。XORをAND/ORノードに置き換えると、各ノードが別の32行のギャザーにコストをかけるまで安く見えます。キャリーセーブは、配信が支配的であった間、何も得られませんでした。配置を最初に解決する必要がありました。

スライス、フォールド、および半自動ルーティングプロセス

ポイントファブリックは自然にビットスライスを示唆しています。ビット0から31まで、小さなローカル配置を繰り返します。スライス内では、A[j]、B[j]、伝播、生成、およびキャリートラックが隣接して配置され、1つのイントラ予測行がすべての32個のブールゲートを並列に計算します。私たちが発見した最も密なスライスは、1つの2x2ブロックのセルでのフルアダーです。キャリーはまっすぐ東に走り、合計はまっすぐ南にドロップします。

// src/chainadd.hpp
//        [ U0 (平面)   xor_cell ]   西 (上段) = 127 + c_in
//        [ U17           flood2   ]   北           = 129 + P_j , 129 + G_j
//   東、全8行      = 129 + (G_j | (P_j & c_in))      (キャリーアウト、一様)
//   南、flood2 列0   = 128 + (P_j ^ c_in)              (サムビット)
// -1 西レベルとの平面はAND、等しいレベルとのDCはORです。

構成がスライスを困難にします。ピクセルの全幅を横切って水平コピーセルの行を伝播するキャリーは、その行を南に移動する値を破壊します。この問題をプロジェクト中に3つの方法で解決しました。キャリーが全幅行を駆動しない対角線アダー、クロスオーバーセル、そして最後に状態がアダーをまったく横断しないアーキテクチャです。

フォールドは、論理パスが物理エッジにヒットしたとき、またはキャリーまたはメッセージパスが再利用可能な領域に再入力する必要があるときに発生します。HEVC参照の利用可能性は方向性があるため、これらは高価です。数学的に有効なフォールドは、デコーダーがそのコーディングツリー境界でまだ到達していない右上サンプルを要求する可能性があります。機能するフォールドは、Z順序が許可する場所にのみ配置されるシフトセルの階段です。2サンプル/ビットのバスワードの場合、テストしたすべての距離でロスレスであり、オペランドをいくら追加しても常に536 CU幅を維持する制限付き幅のアキュムレータを構築できます。

これらすべてを半自動プロセスでチェーンしました。

1. 検索：プリミティブ検索エンジンは約107個のデコーダーで証明されたセルとその小さな構成を列挙し、各エッジサンプルを128 + f(a,b,g)（ブール値f）として分類します。
2. ライブレンジ、型付きステージ契約、および優先トラック位置から候補レイアウトを生成します。プロデューサーのポートフォーマットがコンシューマーのフォーマットと異なる場合、ルーターは検証済みのフォーマットアダプターを自動的に挿入します。
3. ソフトウェア再構築オラクルを使用して、エクスポートされた各サンプルを検査します。
4. 小さなネイティブHEVC制御アーティファクトを生成します。
5. FFmpegとApple ImageIO経由でデコードします。
6. 正確な失敗を配置制約にフィードバックし、不正なレイアウトが誤ってデコードする代わりにスローするように、ハードウェアルールを表明としてエンコードします。

コンパイラはCU粒度で占有率、サンプル粒度で参照ハロ、ワードおよびビット粒度で論理値を追跡します。ルーターは1つのレジスタ、3レーンパケット、またはパックされたバイトを移動させます。アロケータは、ブールトラックには空きがあるが、予測参照が境界を横切る可能性があるため使用できない場所を知っています。

これにより、完全なラウンドが1つ、次に4つ、さらに長いスケジュールフラグメントがクローズされました。また、壁が否定できないものになりました。完璧な単一ピクセル配置でさえ、Appleの許容次元の下でトランスポートとプレゼンテーションの作業を収めることができませんでした。

ブレークスルー：HEVCシーケンスが時間軸

修正は、コンピュータを1つのピクセル内に存在させるという主張をやめることでした。

HEIFはHEVC画像シーケンスを保持でき、HEVCには既にピクセル間のバイト単位で正確なトランスポートエンジンがあります。それがインター予測です。各制限付きPピクセルは1つのハードウェアステージになり、モーション補償は状態バスになります。

［画像: マルチピクセル時間パイプライン］

最終的な設計では、ピクセルを時間ステップとして、モーション補償を永続的な状態バスとして使用します。

各ピクセルは、前のピクセルから128バイトのレジスタバンクをインポートし、1つのスケジュール、ラウンド、フィードフォワード、プレーン、グリフ、またはアトラス操作を実行し、既知のサンプル座標で更新されたバンクをエクスポートします。次のステージがそれらの座標への合法的なモーションベクトルを持たない場合、コンパイラは各バイトを正規スロットに向かって制限された距離だけ移動させる再パッキングピクセルを挿入します。

デコーダーには既に最適化されたモーション補償エンジンとデコード済みピクセルバッファがあるため、数百のイントラピクセルコピーの手動構築をやめ、それを実行させました。1つの通常のインターコード化ユニットは、デコーダーに前のピクセルからサンプルを取得するように要求します。モーションベクトルは1/4サンプル単位であるため、列x_srcのバイトはmv_x = 4 * (x_src - x_dst)で列x_dstに到達します。

// src/byte_program.hpp: ピクセルの先頭でバンクをインポート
int mvx = 4 * (source_samples[i].x - (8*x + 7));
int mvy = 4 * (source_samples[i].y - 7);
if (mvx < -32768 || mvx > 32767 || mvy < -32768 || mvy > 32767)
    throw std::runtime_error("byte resume motion-vector range");
set(x, 0, hevc::inter_cu(mvx, mvy));          // 前のピクセルから取得
set(x, 1, pointfabric::main_read());
set(x, 2, byteregister::read());
set(x, 3, byteregister::hold());

ソースコメントは、設計を機能させたルールを述べています。「ピクセル内のバイトトラックを固定する。フレーム間モーションのみがバイト単位で安全な再パッキングを実行する。」

最終的な論理パイプラインは以下を含みます。

制限付き再パッキングは403のトランスポートピクセルを追加します。合計564ピクセルです。各ピクセルは2,048x872コーディングユニット（16,384x6,976ルマピクセル、約1.14 x 10^8サンプル）であり、Appleのピクセルあたりの制限の10分の1です。ファイルは大きいですが、単一のピクセルが許容ジオメトリを破ることはありません。

サンプルサイズテーブルからスケジュールを直接読み取ることができます。158個の計算ステージは、2.1〜3.4 MBの158個のコード化されたピクセルです。リレーと403個の再パッキングピクセルは、100〜200 KBの404個のピクセルです。ソースIピクセル（30,790バイト）とプレゼンテーションピクセル（81,704バイト）は、最も小さい2つです。最初の16ラウンドでは、各ラウンドの前に3つまたは4つのトランスポートピクセルがあります。メッセージスケジュールが開始されると、リズムは4つのトランスポート、1つのスケジュールステージ、2つのトランスポート、1つのラウンドになります。

ここに1つの計算ステージのデコード結果を示します。ピクセル4、最初のSHAラウンド、8x8 CUあたりの1ドットです。濃い灰色はアイドル（すべてのサンプルが128）、緑はアクティブなブール論理（129）、青とオレンジは128より下および上のバイトレーン、黒と白は0と255です。

［画像: ピクセル4、最初のラウンドステージ、コーディングユニットあたり1ドット］

レジスタバンクは左端に沿って実行されます。オペランドは上部を東に移動し、ビットトラックに展開され、ラウンドのロジックは南東に進みます。これは、因果関係のルールが要求するように正確です。

コンパイラの内容

［画像: コンパイラレイヤー］

ツールチェーンは、SHA-256をワードIR、物理ルーティング、ピクセルスケジューリング、HEVC発行、およびHEIF最終化に低下させます。

1. SHA-256フロントエンド

フロントエンドはFIPS 180-4を実装しています。ラウンドtでは：

T1 = h + Sigma1(e) + Ch(e,f,g) + K_t + W_t   (mod 2^32)
T2 = Sigma0(a) + Maj(a,b,c)               (mod 2^32)
a' = T1 + T2,    e' = d + T1

スケジュールリングはインプレースで更新されます。

W_t = sigma1(W_{t-2}) + W_{t-7} + sigma0(W_{t-15}) + W_{t-16}   (mod 2^32)

2. ワードIRと回転ビュー

ワードIRはINPUT、CONST、XOR、AND、OR、およびADDを持ちます。回転とシフトはエッジアノテーションです。定数畳み込みは、物理的な低下の前に演算を削除します。各小さなプログラムは独立した評価子を持つため、コンパイラは配置された回路に対して期待される各ワードをチェックできます。

ラウンドビルダーはコンパクトなままです。なぜなら、複雑さはロワーに宿るからです。

auto hs  = p.add(h, p.sigma(e, 6, 11, 25));
auto ch  = p.gate(XOR, g, p.gate(AND, e, p.gate(XOR, f, g)));
auto t1  = p.add(p.add(p.add(hs, ch), p.constant(K[t])), w);
auto ne  = p.add(d, t1);
auto maj = p.gate(OR, p.gate(AND,a,b),
                      p.gate(AND,c,p.gate(OR,a,b)));
auto t2  = p.add(p.sigma(a,2,13,22), maj);
p.outputs = { p.add(t1,t2), ne };

Chはg XOR (e AND (f XOR g))であり、Majは(a AND b) OR (c AND (a OR b))です。これらは教科書的な形式と同等で、このファブリックではより安価です。

3. 物理ロワーとルーター

ロワーはバイトオペランドを32個のブールトラックに展開し、一時的なパネルを割り当て、ゲートとアダーを配置し、クロスオーバーセルを通してオペランドをルーティングし、結果ビットをバイトにパックし、次のピクセルがインポートする必要がある正確な出力サンプルを記録します。これは占有率を認識しています。各ライブビットには列があり、各パックされたバイトにはポートがあり、各ルートは参照ハロを予約します。重ならないルートはインターバルパーティショニングによって行を共有します。

4. 永続レジスタと仮想リネーミング

レジスタファイルは128バイトのバンクです。32ワード。8ビットサンプルはバイト全体を保持するため、ワードは32個ではなく4つのセルを必要とします。バイトレジスタセルは小さく、すべての65,536個の入力ペアに対して、すべての読み取り、クロス、書き込み契約をチェックしました。

// src/byte_register.hpp
// N3 を消費し、S3..S7 および E4..E6 を N3 と等しく生成する。
inline hevc::CU read(){return hevc::nxn_cu({26,10,26,10});}
// S3=N3 を保持し、独立して W4/W5/W6 を E4/E5/E6 に渡す。
inline hevc::CU cross(){return hevc::nxn_cu({2,18,34,18});}
// W5=W6=H を必要とし、H を S3/S7 に書き込む。
inline hevc::CU write(){return hevc::nxn_cu({26,26,14,10});}
// N3 を S3 に、N7 を S7 に独立して保持する。
inline hevc::CU hold(){return hevc::nxn_cu({26,26,26,26});}

［画像: 永続バイトバンクと仮想レジスタリネーミング］

固定された物理スロットが状態とスケジュールを保持します。ポインタのような名前は、各ラウンド後に回転します。

• スロット0..7はワーキング状態を保持します。
• スロット8..23は16ワードのスケジュールリングを保持します。
• スロット24..31はフィードフォワードの初期チェーン状態を保持します。

各ラウンドで物理的に上書きされる状態ワードは2つだけです。新しいaはhを保持していたスロットに、新しいeはdを保持していたスロットに入ります。残りのSHA状態シフトは、実際のCPUのレジスタリネーミングと同じポインタリネーミングです。

kernel(program, mapping, {state_slots[7], state_slots[3]});

state_slots = {
    state_slots[7], state_slots[0], state_slots[1], state_slots[2],
    state_slots[3], state_slots[4], state_slots[5], state_slots[6]
};

スケジュールも同様に機能します。W[t]はスロット8 + (t mod 16)を占有し、その最後の古い使用が過ぎると、W[t+16]がスロットを上書きします。物理的な16ワードシフトはありません。

5. バイトからビットへ、そしてその逆

任意のバイトはブールゲートを壊すため、各ステージはまず必要なバイトを8つの128/129ポイントトラック（12行パネル）に正規化し、次に計算されたビットをバイトにパックして終了します（59行パネル）。パッカーはデコーダー自身の予測子で算術を実行します。固定の「ゲイン」セルは以下を計算します。

R(P) = floor((8P + 24*clip(P + floor(P/2), 0, 255) + 16) / 32)

127を引いた後、18回の適用でレベル1と2が1と255にマッピングされます。1を引いて、さらに1ステップ適用すると、正確に0と255が得られます。8つのDC平均セルが、まず最下位ビットからビットを結合します。q = 0から開始します。

q <- ceil((q + 255*b_j) / 2)   (j = 0..7)
   =>  q = ceil((255 * byte) / 256) = byte   すべての 0 <= byte <= 255 に対して

デコーダーの平均化がビットパッキング命令です。

6. ピクセルスケジューラとモーションベクトル制限付き再パッキング

ピクセルスケジューラは、各小さなプログラムをCheckpointでラップし、各計算ピクセルの前にバンクを正規化します。再パッキングプランナーは、正規列の近くに一意のターゲットトラックを選択し、ソースからターゲットへのすべての変位をモーションベクトル範囲内に保ちます。

for (int i = 0; i < 128; ++i) {
    int want = 4 + i;
    int lo = std::max(0, source[i] - 511);
    int hi = std::min(width - 1, source[i] + 511);
    target[i] = nearest_unused(want, lo, hi);
}

制約付き割り当て問題として解決されます。コンパイラは、収束が必要とするだけの制限付きピクセルを挿入し、すべての128個の宛先が異なることを証明します。

7. HEVCおよびHEIFバックエンド

バックエンドはモノクロHEVCを直接書き込みます。32x32コーディングツリーユニット、8x8最小コーディングユニット、NxN予測ユニット、必要に応じてPCM、およびPスライス内の明示的なL0モーションベクトル（それぞれ前のピクセルのみを参照）。次に、1チャンクあたり1サンプルとhvc1サンプルエントリを持つHEIF画像シーケンスコンテナを書き込みます。

hvc1の詳細は経験的で負荷の高いものでした。意味的に同一のhev1リマックスは、ターゲットとしたAppleパスによって拒否されました。hvc1構成契約を維持することで、シーケンスはImageIOに受け入れられました。

自己参照の構築

ハッシュクインは循環的に聞こえます。画像は、表示をエンコードするバイトに依存するダイジェストを表示する必要があります。SHA-256の連鎖構造で固定小数点検索を回避しました。SHA-256はMerkle–Damgård構造です。ダイジェストは、最後のブロック（ミッドステート）の後の連鎖状態と最後のブロックのみに依存します。これは長さ拡張攻撃の背後にあるのと同じ特性です。

［画像: プレフィックス-ミッドステート構築］

通常のハッシャーとデコーダー回路は、同じ連鎖状態から最後のブロックを開始し、同じダイジェストに収束します。

最終ファイルを以下とします。

F = P || S || FE80

ここで：

• Pは正確に2^29 = 536,870,912バイトの既に固定されたプレフィックスです。
• SはPをハッシュした後の32バイトのSHA-256連鎖状態です。
• FE80はファイルの通常の2バイトです。
• ファイルの総長は536,870,946バイトです。

|P|は64バイトブロックサイズの倍数なので、Pの直後の8ワード連鎖状態をH_Pとすると：

S = BE32(H_P[0]) || ... || BE32(H_P[7])

通常のSHA-256実装は、最後の34バイトのファイルを読み取り、次に独自の0x80、ゼロフィル、および64ビット長を付加します。その最後の圧縮ブロックは次のとおりです。

S || FE 80 80 || 21 バイトのゼロ || BE64(8|F|)

デコーダーはSを初期連鎖状態としてインポートし、それらの同じバイトをメッセージワードW0..W7として使用します。W8 = 0xFE808000をハードワイヤリングし、W9..W13をゼロにし、ファイルビット長をW14..W15に入れます。ファイルは512 MiBより大きいため、8|F| = 4,294,967,568 = 2^32 + 0x110は32ビットをオーバーフローします。つまり、W14 = 0x00000001、W15 = 0x00000110となり、回路の長さ入力は64ビットに拡張する必要がありました。両方のパスは正確に同じ圧縮とフィードフォワードを実行します。

SHA256(F) = Compress(H_P, S || FE8080 || 21*00 || BE64(8|F|))

コンテナトリック：物理的なファイル順序とデコード順序は異なっていても構いません。最終化処理は、mdatにPピクセルプログラムサンプルを最初に書き込み、物理的なプレフィックスを正確に2^29バイトにパディングし、ソースIピクセルバイトを最後に格納します。サンプルテーブルは依然としてそのソースを論理サンプルゼロとして名前付けするため、デコーダーはそれを最初に訪問します。ハッシュはバイト順序に従い、デコードはサンプルテーブルに従います。したがって、固定プレフィックスは、それを初期化する32バイト値の前に、ほぼすべてのコンピュータを含めることができます。

->mdat: Pピクセル 1..563（コンピュータ）

->Iピクセル 0（30,790バイト、最後に格納）

->最後の34バイト：BE32(H_P) + FE 80

最終化処理は次の手順を実行します。

1. 32バイトのプレースホルダーを使用して完全なシーケンスを構築します。
2. stco/stsc/stszで論理サンプル順序を維持しながら、物理サンプルペイロードを並べ替えます。
3. プレフィックスを正確に2^29バイトにパディングします。
4. そのプレフィックス上でSHA-256をストリームし、その連鎖状態を抽出します。
5. 状態を置き換えても、置換境界で禁止されているHEVCエミュレーション防止パターンが作成されないことを確認します。
6. 32バイトの状態とFE80を付加します。
7. ファイルを独立してハッシュします。

プレフィックスが固定されると、サフィックスは決定論的に続きます。最終化処理はそれを1パスで計算します。配信されるファイルでは、Iピクセルのサンプルはバイトオフセット536,840,156からファイル末尾まで開始し、その末尾はプレフィックスミッドステートです。

プレフィックス 536870912 バイト、末尾 34 バイト
ミッドステート  : 3f4afacaa0d8b13afeffe5e47d93eb0b582721cf29ee35a5337f95162009a22b
末尾[0:32]: 3f4afacaa0d8b13afeffe5e47d93eb0b582721cf29ee35a5337f95162009a22b
一致：ファイルは自身のプレフィックスミッドステートで終わる

デコードされたピクセル0の右下ルマサンプルの行で直接確認できます。3f 4a fa ca a0 d8 b1 3a ...、つまりミッドステート自体です。

8つのワードから64個の読み取り可能なグリフへ

［画像: ダイジェストから表示へのパイプライン］

ニブルビットプレーンがブールフォントROMに供給され、デコーダーネイティブ予測が結果のアトラスを読み取り可能なグリフに拡大します。

まず、8つのダイジェストプレーンステージが一度に4つのSHAワードを転置します。結果の4つの32ビット値は、32個の16進数桁の4つのニブルビットを保持します。これにより、次のステージはワード並列になります。1つのブール演算は、32個の異なるグリフに対して同じフォントピクセルを評価します。

フォントは、0–9およびa–f用のコンパクトな3x5デザインです。15個のピクセルそれぞれについて、コンパイラは最小化された積和をニブルビットa,b,c,dに対して使用します。例えば、中央上部のピクセルは、4（0100）以外のすべての桁で点灯するため、a OR ~b OR c OR dにコンパイルされます。16個の固定グリフのうち1つを選択する4ビット入力は、まさに順序付きバイナリ決定木の観点から役立つ場所です。SHAコア全体をOBDDとしてモデル化すると爆発しますが、4ビットフォントROMは理想的です。

for (int column = 0; column < 3; ++column) {
    int pixel = 3 * font_row + column;
    Word sum = p.constant(0);
    for (const char* term : minimized_terms[pixel]) {
        Word product = p.constant(~0u);
        for (int k = 0; k < 4; ++k)
            if (term[k] != '-')
                product = p.gate(AND, product,
                    is_lower(term[k]) ? nibble[k] : not_nibble[k]);
        sum = p.gate(OR, sum, product);
    }
    p.outputs.push_back(sum);
}

コンパイラは結果を128x48 CUのグリフアトラスに書き込み、最終的なルートが確定した行を横切らないように、下から上に向かって行をコミットします。

遅延したデコーダーの不一致により、最後のアーキテクチャ変更が必要になりました。長いイントラ予測パスは128/129ブール代数を維持しましたが、ImageIOの下で一部の任意のバイト値を破損させました。ソフトウェアモデルはそれらを正確に維持しました。それに抵抗するのではなく、アトラスステージはインター予測を使用して、前のピクセルから必要な12個の任意のバイトを3つの分離した正規化パネルにコピーします。高速正規化子はそれらをビットトラックに展開し、ゲインステージは128/129を正確な0/255サンプルにマッピングします。（静止画像であればフォントROMとしてICCカラープロファイルを使用できたかもしれませんが、ImageIOはHEIFシーケンスのトラックICCプロファイルを無視するため、ここではフォントは計算されます。）

プレゼンテーションピクセルは、デコーダーがアトラスを拡大できるようにします。各ソースフォントピクセルは、独立してアドレス指定可能なモーションコピーシードを取得します。水平イントラモード10は最初の行の残りを埋め、垂直モード26は残りの行を埋めます。計算されたアトラスピクセル1つが、プロジェクトの他の部分と同じ原則で、デコーダーネイティブ予測を通じてほとんど完全に読み取り可能な128x128の正方形になります。デコーダーが既に正しい、安価なプリミティブを持っている場合、ゲートから再構築するのではなく、それにコンパイルします。

検証

両方向から検証しました。バイト側：

$ shasum -a 256 sha256_hashquine.heic
802cc6d654ad15aafbb1ca5db4824292cc39fd72cf23fd80e1230d90679b9ff1

デコーダー側、最終成果物上の標準ImageIO：

ファイルバイト数:                   536,870,946
ImageIO ピクセル数:       564
最終ピクセルインデックス:         563
デコードされた寸法:          16,384 x 6,976
デコードされたグリフ:              64 / 64
デコードされたテキスト:                802cc6d654ad15aafbb1ca5db4824292
                             cc39fd72cf23fd80e1230d90679b9ff1
セル不一致:             0

検証ツールは、各3x5グリフセルの中心をサンプリングし、ビットマップを固定フォントテーブルを通してマッピングし、独立してハッシュされたファイルと比較して64文字すべてを比較します。最終ピクセルのサンプルは正確に0、128、および255であるため、読み取りは曖昧ではありません。コンテナ側も独立してチェックアウトします。ファイルの最後の34バイトは、最初の2^29バイトのミッドステートです。

コンパイル中、各レイヤーで差分テストも実行しました。

• 独立したSHA-256リファレンスに対するワードIR評価。
• 各プリミティブの網羅的な真理値表。
• 各コーディングユニットの境界サンプルチェック。
• フルピクセルソフトウェア再構築プローブ。
• FFmpegデコード制御。
• Apple ImageIOデコード制御。
• 物理ファイルダイジェストに対する最終グリフOCR。

ソフトウェアモデルは有用でしたが、Appleのデコーダーが承認のオラクルでした。それらが意見の相違があった場所では、出荷された動作を中心に再設計しました。

どのようなコンピュータを構築したか？

最終的なマシンは、有限で、空間的および時間的に展開された、デコーダーホスト型のプロセッサとして最もよく説明できます。

レベルに応じて、CGRA、シストリックアレイ、またはセルオートマトンとして見えます。ビットレベルではローカルCA、ワードレベルではルーティングされたデータフローマシン、ピクセルレベルでは状態変換ステージのパイプライン、コンテナレベルでは分離された物理的および論理的順序を持つ自己参照プログラムです。同じマシン、4つのコンパイラレイヤー。

セキュリティへの影響

このアーティファクトは無害です。固定のSHA-256継続を計算し、有効なデコーダー操作を使用してピクセルを描画します。不正なメモリに触れることはなく、通常のデコードパス内で完全に実行されます。

これは、パーサーバグを超えてデコーダーセマンティクスが注意に値する理由を示しています。FORCEDENTRY分析は、標準化された画像操作が論理ゲートマシンに構成できることを証明しました。セマンティックコンピュータは、メモリ安全性バグの前、後、または並行して、決定論的な作業を実行できます。埋め込みデータを変換したり、事前計算された戦略の中から選択したり、タイミングを正規化したり、ネイティブコードを注入することなく、より予測可能なデコーダー状態を作成したりできます。

フォーマットレベルのマシンは、依然として最新の緩和策に対応します。Arm MTEとAppleのMemory Integrity Enforcementは、カバーするドメインを依然として保護しており、標準準拠の回路は任意のメモリを読み取ったりタグを偽造したりする権限を持ちません。関連性は構成可能です。分離されたバグが安全でない遷移を提供する場合、リッチなセマンティックマシンは、それに到達または安定させるために必要な、破損後の脆弱な作業を減らすことができます。

この構築のいくつかの特性は、それ自体で注目に値します。

• 画像シーケンスはより静かな表面です。 ここにあるすべては、インター予測とHEIFシーケクストラックボックスにあります。これらは「画像」処理が到達するパスですが、静止画像パスよりもはるかに調査が少ないです。
• ビューアが表示するピクセルによって、見えるものが異なります。 このファイルのピクセル0は灰色のフィールドですが、ピクセル563はペイロードを運びます。サムネイル作成者、コンテンツスキャナー、知覚ハッシュ、およびポスターフレームのみを見るモデレーションパイプラインは、シーケンスをスクラブするビューアとはまったく異なるものを見ることができます。
• ピクセルあたりの制限は、総作業量を制限しません。 1.14 x 10^8サンプルの564ピクセルは、512 MiBファイルから約6.4 x 10^10個のデコードされたサンプルになります。
• 出所は不活性データを想定しています。 自身のバイトに対して選択された回路を評価できるメディアは、画像をパッシブコンテンツとして扱うC2PAマニフェストからフォレンジック重複排除まで、スキームを複雑にします。

有用な質問は、「各操作は安全か？」という問いから、より難しい「数千の安全な操作が攻撃者が制御するデータフローの下で構成されたときに、どのような計算が可能になるか？」という問いに移ります。

ループを閉じる

単一のHEVCモードではこれを解決できませんでした。各失敗はより良い抽象化を強制し、各抽象化は次のステップを解除しました。

• 直交サンプルレーンは、見かけ上の平面的な壁をクロスオーバーに変えました。
• 回転タグは、ビット移動をポインタのようなビューに変えました。
• スケジュールと状態マップは、物理的なシフトをレジスタリネーミングに変えました。
• 計装により、SHA算術ではなく移動がキャンバスを消費することが明らかになりました。
• 画像シーケンスはピクセルを時間ステップに変えました。
• モーション補償はバイトセーフな状態バスになりました。
• サンプルテーブルの間接参照は、物理的なハッシュ順序とデコーダー実行順序を分離しました。
• デコーダーネイティブ複製は、小さな計算されたアトラスを読み取り可能なテキストにスケーリングしました。

結果は、特殊化されたコンピュータを含む合法的なHEIC画像シーケンスです。標準のImageIOはそれを再構築し、固定SHA-256プログラムを実行し、ファイル自身のダイジェストをピクセルとして描画します。

アーティファクトとソースを取得する

536,870,946バイトのハッシュクイン、カスタムコンパイラ、検証ツール、およびこの投稿のすべての測定値の背後にある実験。

GitHubで表示

さらに読む