🎰

複数のビットフィールドを持つ数値の並列演算

2021/05/18に公開

並列化といえばHadoopだSparkだMPIだといったキーワードが世の中を賑わせているが、古典的な話としてゲームなどのグラフィクス処理界隈ではMMX命令などのSIMDを使う事なくデータ並列性を引き出すことによって高速化していた。
このテクの一部を扱った傑作記事が気づいたら検索で辿れなくなっていてWebArchive入りしてしまっていたので一つの機会として解説記事を書くことにした。

古株のエンジニアからすれば見慣れたテクニックではあるが知らない人から見るとパズルのような面白みがあり応用の幅もある面白いテクニックである。

複数のビットフィールドとは

スーパーファミコンのように表示可能色が32,768色に制限されている環境というのは、内部的には1色を15bit(2^15=32,768)を使って表現している事が多い。当然この色数で自然界のあらゆる物を自然に描写するのは難しいが、ゲーム用途などでは省メモリ・高速・低コストといった多くのメリットがあった。
その内部では16bitの整数1つを1+5+5+5bitの構造体として扱いデータを表現する。3つの5bitがそれぞれ赤・緑・青の明るさを32段階で表現し、1bitは使わなかったり人間の目がより敏感に見分けるとされる緑色に割り当てて6bitで64段階の表現に使ったりする(らしい)。

行いたい並列計算とは

みんな大好き戦闘中の魔法エフェクト、これは端的にはエフェクト用に用意した画像を上から半透明・加算・減算などの方法で画像の上に重ねる事で表現している。とりわけ加算合成をふんだんに使った派手なエフェクトはかっこよくて目を引く。しかしただ単に加算をするだけだと32段階目の上の数字に繰り上がってしまった時に見た目が壊れてしまうため、最大値でクリッピングしてやる必要があり、それを飽和処理とかサチュレーションとか呼んだりする。
16bitの整数で表現された2つのピクセルを飽和処理付きで加算合成する処理を愚直にCで書くならこんな感じになる。

uint16_t AddBlend(uint16_t p1, uint16_t p2) {
  // 赤色の処理
  uint16_t p1_red = (p1 >> 10) & 0x1f;
  uint16_t p2_red = (p2 >> 10) & 0x1f;
  uint16_t result_red = p1_red + p2_red;
  if (31 < result_red) result_red = 31;

  // 緑色の処理
  uint16_t p1_green = (p1 >> 5) & 0x1f;
  uint16_t p2_green = (p2 >> 5) & 0x1f;
  uint16_t result_green = p1_green + p2_green;
  if (31 < result_green) result_green = 31;
  
  // 青色の処理
  uint16_t p1_blue = p1 & 0x1f;
  uint16_t p2_blue = p2 & 0x1f;
  uint16_t result_blue = p1_blue + p2_blue;
  if (31 < result_blue) result_blue = 31;
  
  return (result_red << 10) | (result_green << 5) | result_blue;
}

それぞれの色に対応する部分を足して加算して31を超えたらクリッピングして最後に合成して、というわかりやすいコードであるが改善の余地が大きい。とりわけCPUは分岐命令によってパイプラインにハザードが発生した場合での速度面でのペナルティは無視できず、画像処理のように大量のピクセルに対して処理を行う状況においてはゲーム性に悪影響すら与えかねない致命傷となりうる。そこでこれと同等の結果をif文なしで、更にはRGBそれぞれの色についての計算を一度に行うことで高速化しよう、というのがこの記事の主題である。

最適化されたコード

オリジナルの記事で「やねうらお様とさ～様から更に最適化する方法を教えていただきました。」として紹介されていたコードはこんな感じである。パッと見では上に書いたコードと同じ結果を返すとはわからない。

uint16_t AddBlend(uint16_t p1, uint16_t p2) {
    uint16_t c = (((p1 & p2) << 1) + ((p1 ^ p2) & 0x7bde)) & 0x8420;
    c = ((c >> 5) + 0x3def) ^ 0x3def;
    return (p1 + p2 - c) | c;
}

謎の定数やビット演算が並んでいて怖く見えるかも知れないが順を追って理解していくと実はそこまで難しい話ではない。

飽和するフィールドを検出する

uint16_t c = (((p1 & p2) << 1) + ((p1 ^ p2) & 0x7bde)) & 0x8420; の1行について解説する。

RGBそれぞれに付いて足し算を行いたいのだが、単純に16bit幅の足し算を行うとGreenやBlueを表すフィールドでの加算結果の繰り上がりが一つ左のフィールドの最下位ビットに影響を与えてしまう。
そこで「直接足し算することなくそれぞれのフィールドでのキャリーフラグ(繰り上がりが発生した時に立つビット)」を取り出すという作業を行う。

((p1 & p2) << 1) は「両方のピクセルで共通で立っているビットを取り出して1ビット左にずらす(繰り上がる)」を表わし、半加算器におけるCarry Out部分である。
(p1 ^ p2) は「両方のピクセルで片方だけ立っているビット」を表わし、半加算器におけるSum出力である。
0x7bde は2進数で表すと 011110 11110 11110 つまりR,G,B各ビットフィールドにおける最下位ビットが0になっているものであり、これと半加算器のSum出力を & 演算することで「加算の結果立っていたかも知れない各ビットフィールドの最下位ビットを強制的に倒す」という処理になる。
繰り上がったCarry Out部分と最下位ビットを潰した(XORの)半加算結果を足し合わせる事によって「繰り上がりが発生するフィールドだけの最上位ビットの一個左が1になる」という結果が出てくる。
0x8420 は2進数で表すと 10000 10000 100000 で、1になっている部分はまさに「各フィールドの最上位ビットの一個左」である。これと & 演算することによって「32を超えて繰り上がる(=飽和する)」フィールドだけが1bit立ったキャリー情報変数 c が手に入る。全フィールドが飽和するなら c == 0x8420 であり、どのフィールドも飽和しないなら c == 0x0000 であり、例えば真ん中の緑だけ飽和するなら c == 0x0400 になる。

キャリーを用いてマスクを生成

c = ((c >> 5) + 0x3def) ^ 0x3def; の1行について解説する。
ここでは前段で算出した飽和フィールド情報から、計算に使えるマスクを生成する。

(c >> 5) これは5ビット右にずらす事を意味し飽和するフィールドだけが1、それ以外は0のままとなることを意味する。
それと足されている 0x3def は2進数で 0 01111 01111 01111 である。飽和するフィールドだけ1が足されるので、全フィールドが飽和するなら 0 10000 10000 10000 になるしどれも飽和しないなら 0x3def のままである。
その結果を更に 0x3def とXORする。すると「ビットが逆になっている部分だけが1」になったビット列が手に入る、飽和するフィールドについては (01111 + 1) ^ 01111) = 10000 ^ 01111 = 11111 という飽和済み最大値が手に入る。飽和しないフィールドについては (01111 + 0) ^ 01111 = 01111 ^ 01111 = 00000 で0が手に入る。

マスクを用いて飽和を表現

(p1 + p2 - c) | c; の1行について解説する。
cは前段で計算した結果、飽和するフィールドが1の羅列、飽和しないフィールドが0の羅列になっている。
ここで最初に与えられた2つのピクセルをいきなり加算する、すると当然ながら飽和したフィールドが隣のフィールドに繰り上がって値を破壊する、しかし - c によって飽和して得られる最大値を引き戻して隣のフィールドに掛けた迷惑も元通りになる、予め必ず31を超える事は算出済みなので31をそこから引き算しても全体を狂わせることはない。しかし31を愚直に引いただけだと値が狂うので | c によって31で書き潰す、そのフィールドの全ビットを立てれば元の値がどう狂っていようと問答無用で31になる。飽和しなかったフィールドの部分に対しては - c | c は - 0 | 0 という無意味な計算になるためただの足し算結果がそのまま出力される。完。

一言で言うと何なのか

ここまでの説明で目が滑って理解が追いつかなかった人のために平坦な言葉で表現し直すと「C言語というよりは論理回路に近い処理を半加算器の再現によってキャリーフラグを取り出して埋めている」でわかった気になるだろうか。

みんな大好きマイクロベンチ

さて、気になるのはこれで例えばどの程度高速化したのか、である。
長さ4096のuint16_tの乱数列2つに対して飽和加算を行う簡単なマイクロベンチを行う。比較対象はこの記事の上の方に書いた愚直な方法と、オリジナルの記事で紹介されていた高速化された方法である。C++のベンチマークが簡単に取れる Quick C++ Benchmark というサービスを用いて測定した、リンクはこちらである https://quick-bench.com/q/E87luFkw85Kj9YQYmD7jz8SQXP8 。コンパイラはGCC10.2を用いた。

確かに高速化しているがパイプラインハザードとか薀蓄を垂れた程度の差を説明するほどの大きな差にはなっていない。ついでにClang11.0でも測定してみる。

なんと更に差が縮まった。軽くアセンブリを眺めてみたがClangが特段変な事をしているとは感じなかった（プロが見たらまた違うのかも知れない）気になる人はこのサイトでアセンブリ結果を1行ずつ対応関係を追いかける事ができるので調べてみて欲しい（投げっぱなし）。少なくともGCC,Clangどちらもif文はコンパイラのレベルで別の方法で置き換えられており分岐は無くなっていた。

まとめ

最近はコンパイラが賢いので人間が命令レベルでガチャガチャやって労力に見合う成果を得る難度は上昇傾向にあるが、古代の教養の一つとしてこういうテクニックを嗜んでおくと思わぬ所で役に立つかも知れない。この手のテクニックが好きでもっと知りたい人は Bit Twiddling Hacks とかハッカーのたのしみとかを楽しめると思う。

繰り返しになるが、ここに書かれたコードの出典は https://web.archive.org/web/20201109041800/http://www.emit.jp/prog/prog_b.html にアーカイブされた記事でありkumagiのオリジナルではない。発案者に敬意を。