半端なbit長の、固定幅の整数型

C99/C++11で追加された、固定幅の整数型(uint8_tint32_tのようなものたち)は特定のビット幅で計算したいときに大変便利です。何ビットの整数が要求されているかを明示することで移植性が高まります。

また、uint16_tは必ずオーバーフローせず、結果の上位ビットが無視されるだけの結果になるなど、ハードウェアに近いことをやりたいときにも便利です。しかし、この用途ではint13_tuint42_tが欲しくなることはないでしょうか。

大きめのbit幅の整数型を用い、適宜ビットマスクを掛けることで所望の動作をシミュレートすることはできますが、ユーザーコードで行うのは不便です。 当然そのようなライブラリが求められますが、少し探した感じではそのようなライブラリは見当たりませんでした。

そこで自作してみたというのが今日のお話です。

GitHubで公開してありますので、興味があれば使っていただけると嬉しいです。間違いなどの指摘も歓迎です。

github.com

以下、このライブラリを作るにあたって、移植性と効率性を両立するために工夫した点です。

下位bitを使ってシミュレートするのではなく、上位bitを使ってシミュレートする

単純な発想では、uint13_tをシミュレートするためには、uint16_tの下位13bitを用いる方法が考えられます。つまり、演算の後に常に0x1fffとのビットごと論理積を取りその結果を保持するという実装です。

この方法は、標準にある整数型に変換するときのコストが全くかからないというメリットがありますが、毎演算ごとにビットごと論理積が発生するというデメリットがあります(コンパイラがどのくらい見抜いてくれるかは確認していないですが……)。

そうではなく、あえてuint16_tの上位13bitを使うという方法を使っています。この方法を使うと、上位ビットが無視される状況が何の追加演算もなしに得られます。また、表現は単に定数倍(uint13_tuint16_tでシミュレートする場合は、3bit分なので8倍)されているだけであるので、大小比較は特に工夫せずにそのまま行って問題ありません。

代わりに、右シフトの場合は下位ビットが0になるように少しだけ補正が必要です。また、乗除算はビットマスクを掛ける処理の代わりにオフセットをずらす分の処理が少し増えます(ライブラリの実装では、左右のオペランドのどちらもオフセットを取り除き通常の表現にした後計算し、オフセットを戻すという処理を行っています。オフセットを取り除く処理とオフセットを戻す処理は打ち消す合うはずなので冗長ですが、コーナーケースが怖く、安全な実装に逃げました)。

ナイーブな実装と比べ、標準にある整数型との変換コストがかかる点だけは劣りますが、シフト演算一回分であり、頻繁な変換は普通は発生しないと考えられるため、問題ないものと考えました。

safe_abs

safe_absC++で安全に絶対値を求める - よーる で紹介した、未定義動作であるオーバーフローを起こさずに絶対値を取る関数です(詳細は以前の記事を参照ください)。

bit_cast

bit_castは移植性のある方法で、符号なし整数型を符号あり整数型(二の補数表現)に変換する(ビット表現を解釈しなおす)関数です。単にstatic_castを使う場合、変換後の値が負になる場合、処理系定義の動作となります。std::memcpyC++20で入る予定のstd::bit_castを用いても同じ動作が実現でき、そのような問題はなくなりますが、constexpr化できなくなります。

この関数では、uintN_tintN_tの変換において値が変わらない場合は移植性が保たれることを利用し、

  • 値が変わらない範囲(つまり、0x0000...から0x7fff...の範囲)にある場合はそのまま変換
  • 値が変わってしまう範囲(つまり、0x8000...から0xffff...の範囲)にある場合は、0x8000...を引いた値を求め、その値を変換(0x0000...から0x7fff...の範囲にあるので変換は移植性がある)したのち、0x8000...に相当する値(intN_tの最小値にあたる値)を加算する(この加算ではオーバーフローは発生しえない)

という方法で移植性を担保しています。最適化コンパイラを用いた場合、この処理は消失します。

算術シフト

符号あり整数型の右シフトの挙動は処理系定義となっています。x86にはsar (Shift arithmetic right) 命令が存在するため(他の多くのアーキテクチャにも算術シフト命令はあります)、多くの処理系では算術シフトとなるはずですが、やはり移植性のあるものではありません。 このライブラリを用いた場合、必ず算術シフトとなります。

なるべくオーバーヘッドを減らしたいため、少なくともx86のg++やclang++ではsar命令にコンパイルされるようなコードを書きたいところですが、うまくいきませんでした。

移植性よく、しかし既存のx86処理系にsar命令を推論させる方法は、試した限りでは存在しませんでした。コンパイラsar命令を出力するのは、

  1. 符号あり整数型を右シフトした場合
  2. 定数での除算の場合

に限られるようです。特に、以下のようなコードであっても最適化されてsar命令になることはありませんでした。

constexpr uint64_t sar1( uint64_t x ) noexcept {
    const uint64_t sign = x & 0x8000'0000'0000'0000;
    return sign | (x>>1);
}

1の場合を移植性よく使うことはできませんので、2の場合をうまく活用する方法を考えたいところですが、右算術シフトと除算では、被除数が負の時の丸め方向が異なります(右算術シフトは負の無限大への丸め、除算はゼロへの丸め)。そのため、正負で場合分けするコードが出現してしまいます。

この定数除算がsar命令を使ったコードに変換される動作は、コンパイラバックエンドで行われているようです。つまり、コンパイラフロントエンドでの情報(特に、未定義動作が起こる値が来ているかどうか)の情報が失われてしまっている点が厄介です。

定数除算がsar命令に変換されるのはほぼ定型文として変換されているようで、正の数が来ないはず、などの情報を活用できていません。コンパイラフロントエンドでの情報が残っていれば、定型文として変換した後にあり得ない分岐が取り除かれる最適化がかかるはずですが、失われているためにそれができていません。

おわりに

このライブラリはあまりビット効率のことを考えていないので、uintN_t<3>などとしても64bit使ってしまっています。8bitで十分なので、そういった点は改良の余地がありますが、あまり気にしないことにしました。

また、通常の整数と混ぜて使いたいためexplicitがほとんどつけていません。意図せぬ暗黙変換が発生してわけのわからないことになることが発生しそうですが、利便性を優先しました。この辺は好みが分かれるところですが、あまり新設ではないかもしれません。

再びになりますが、興味があればぜひ使ってみてください。間違いなどの指摘も歓迎です。