はじめてな Elixir(35) ビットリバーサル：ビット列の順序を反対にする

はじめに

組込み系のカンファレンス SWEST の embLT slack チャンネルで以下のやりとりがありました。

ふ：ビットリバーサルはめんどいよねー
お：シフト・ローテートの使えるasmなら多少は楽ですけどね。C以上の高級言語だとめちゃむずくなりますね

全くその通りです。
ついでにいうと「C以上の高級言語」というのはアセンブリ言語を除くすべての高級言語があたりますから「きれいに書くならアセンブリ言語しかない」というのと同義です。

その通りではあるのですが「ビット列のパターンマッチがあるのでElixirは組込み向け」と宣伝してる立場としてはちょっと悔しい。ということでキレイに書けないか四苦八苦してたら「見つけた」ので備忘録としてここに残しておきます。

ビットリバーサルとは

ビットリバーサルとは、整数があるとしてそれを2進数表現でみたときに最上位ビット(MSB: Most Significant Bit) から最下位ビット(LSB: Least Significant Bit) までのビット列を逆順にする関数・操作です。

例えば 0b00100111 のビットリバーサルは 0b11100100 になります。

なお、ここで単に「反転」とか言うと 0 と 1 とを交換するのと紛らわしいので「ビットリバーサル」ないしは「リバーサル」ということにします。

アセンブリ言語で考える

導入部の話の通り、シフト命令やローテート命令を持つ CPU ならアセンブリ言語ですぐ書けます。アセンブリ言語でやるなら、ビット長の分だけ以下を繰り返します。

• 引数をレジスタに入れてシフトかローテイトして端の1ビットを追い出す（追い出したビットはどっかに保存される）
• 結果を溜めるレジスタには、逆向きに追い出された1ビットを付け加えてシフトかローテイトする

例えば Intel 8080A なら以下を8回繰り返すとBレジスタの値のビットリバーサルがCレジスタに入ります。

mov a, b
ral
mov b, a
mov a, c
rar
mov c, a

なおこれ、8回繰り返したあとさらに以下をつけておくと、CレジスタのビットリバーサルもBレジスタに残ります。（ついでに一番最初の PSW Cy ビットも Cy に保存されます。）

mov a, b
ral
mov b, a

Elixir で考える

これを Elixir でやるならどうするか考えてみました。

• bit 列を一旦 list とかにバラして Enum.reverse 関数で逆順にしてから組み立てる
• 再帰的に関数でやる
  　- ビット長が0のときはそれを返す
  　- そうでないときは「一番右の1bit」を「一番右の1bitを外した残りを逆順にしたビット列」の左に連結したビット列を返す
• パターンマッチでやる
• NIF で Rust か C に落とす

パターンマッチでできるとスパッと行きそうなので考えたのですが、あまり良いのが思いつきませんでした。固定長決め打ちならこんなのはどうでしょう。以下は 8bit 固定長の場合です。

<<a7::1, a6::1, a5::1, a4::1, a3::1, a2::1, a1::1, a0::1>> = <<your_byte>>
<<a0::1, a1::1, a2::1, a3::1, a4::1, a5::1, a6::1, a7::1>>

で your_byte のリバーサルが出てきます。以下は 0xb00010101 での例。10進数が出てきて見づらいので IO.inspect で2進数出力させてます。

iex(17)> <<a7::1, a6::1, a5::1, a4::1, a3::1, a2::1, a1::1, a0::1>> = <<0b00010101>>
<<21>>
iex(18)> <<a0::1, a1::1, a2::1, a3::1, a4::1, a5::1, a6::1, a7::1>> |> IO.inspect(base: :binary)
<<0b10101000>>
<<168>>

Erlang できれいにできる

Elixir のパターンマッチには little endian と big endian のマッチがあるので、それで逆順にできないかと思ったのですが、バイトオーダは逆転できますが、ビットオーダを逆転するワザを見つけられませんでした。で、ネットを探してたら Erlang の例がありました¹。

何箇所かでみつけましたが Github に転がってたのがEvadne WuさんのReversing Binaries in Elixirです。これ Elixir で書いてますが、ビットリバーサルで使ってる関数は Erlang 由来のものです。

あらためて転載しておきます（元のは変数が関数名と紛らわしいのでちょっと変えました）。

defmodule EncodeDecodeEndiannessReverse do
  #
  # https://elixir-lang.slackarchive.io/general/page-100/ts-1504039301000460
  #
  def reverse(bin) do
    bin |> :binary.decode_unsigned(:little) |> :binary.encode_unsigned(:big)
  end
end

実際にやってみるとこうなります。

iex(28)> <<1,　0,　1,　0,　0,　1,　1,　1>> |> :binary.decode_unsigned(:little) |> :binary.encode_unsigned
<<1, 1, 1, 0, 0, 1, 0, 1>>

Elixir の Binary 型に依存してないので、ビット長によらずビットリバーサルできます。以下は11ビットでの例です。

iex(30)> <<1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0>> |> :binary.decode_unsigned(:little) |> :binary.encode_unsigned
<<1, 0, 1, 1, 1, 0, 0, 1, 0, 1>>

このプログラム一式の中には Elixir で再帰で書いた例もあって、こちらもキレイですのでぜひ御覧ください。1ビット外して反対側に連結するのがうまく書けてます。

性能

Elixir にしても Erlang にしても仮想マシンの BEAM で実行するので、性能についてはあまり期待できません。BEAM仮想マシンの命令 にもそれっぽいのがありませんでした。アセンブリ言語で書いたのとは相当な差がつくと思います。
その中でも Erlang の decode-unsigned/2 encode-unsigned/2 を使った例は、Erlang の関数として定義してあるのでまだかなりマシじゃんじゃないかと想像します。
とゎいえ、実際に組込みで使おうかというときにはちょっと悩んでしまうケースではあります。

まとめ

Elixir でのビットリバーサルを考えてみました。組込みで使う場合には、ちょっと悩ましくてモニョることになりそうです。

参考文献

• Erlang decode-unsigned/2
• Erlang encode-unsigned/2
• 組込みに欠かせない Elixir でのビットの扱い方
• ビット操作関数 Bitwise を使ってみる
• はじめてなElixir(0)
• はじめてNerves(0) ElixirによるIoTフレームワークNervesがとにかく動くようになるためのリンク集

1. ここのくだり「Elixir ではできないけど Erlang ならできる」と思ってたのですが、Erlang もバイト単位でした。2024-09-02 追記。 ↩