bit列のマッチングを行う方法

bit列操作のような低級なことをやっていると、bit列に対してマッチングを行いたいことがあります。 たとえば、以下のような例です。

t=0b11011010pattern=0b11xx1010にマッチするか?→マッチする。

このようなことを行うためには、pattern中に出現するx0に、それ以外を1に置き換えたmask=0b11001111pattern中に出現するx0に置き換えたbits=0b11001010を作成し、 (t&mask)==bitsであるかを確かめれば十分であり、一般的には最高速です(pattern=0b0000xxxx*1などの特殊な場合には、符号なし比較だけで判定できるため、常に最高速ではありません)。

さて、このようなmaskbitsを手作業で作成するのは発見しづらいミスのもとであり、ソースコードの意図も分かりづらくなります。 ソースコード中にpatternを文字列として記述できれば、そのような問題を解決できます。

しかし、そのような方法を用いた場合、実行時に処理されるため、低速になることが予想されます。 bit列操作のような低級なことをやっている場合、高速化のために行っていることが多く、いくらソースコードが見やすくなっても低速なのでは意味がないという状況も考えられます。

こういったときに便利なのがconstexprです。以下のように少しコードを書くだけで、上記の問題を解決することができます。以下のコードはC++17以降で動作します *2

#include <cstdint>
#include <cassert>

constexpr uint64_t make_mask( const char* str, uint64_t acc = 0 ) {
    assert( *str == '\0' || *str == '0' || *str == '1' || *str == 'x' );
    return *str ? make_mask( str+1, acc<<1 | *str!='x' ) : acc;
}

constexpr uint64_t make_bits( const char* str, uint64_t acc = 0 ) {
    assert( *str == '\0' || *str == '0' || *str == '1' || *str == 'x' );
    return *str ? make_bits( str+1, acc<<1 | *str=='1' ) : acc;
}


template<class Str>
constexpr bool match( Str pattern, uint64_t test_bits ) {
    constexpr uint64_t mask = make_mask( pattern() );
    constexpr uint64_t bits = make_bits( pattern() );
    
    return (test_bits&mask) == bits;
}

#include <iostream>
int main() {
    std::cout << match( []{return"xxxxxxxx1111xxxx";}, 0xacf9 ) << std::endl;
}

ところで、match関数の第一引数として、patternの文字列そのものではなく、ラムダ式を使っているのは、あまり普通の見た目ではないと言えるかもしれません。

マクロレス型安全printf - よーるでも使ったテクニックですが、文字列を返すラムダ式を使うことで、各々の文字列に異なる型を与えるといったことを行っています。

    constexpr const char* pattern = "xxxxxxxx1111xxxx";
    constexpr uint64_t mask = make_mask( pattern );
    constexpr uint64_t bits = make_bits( pattern );

のように自分でmaskbitsを計算してconstexpr変数に入れる場合は、ラムダ式を使った型付けテクニックを使わなくてもよいのですが、match関数のようにpatternも受け取る関数を作る場合はこのテクニックを使う必要があります。

パターンを文字列で書くのではなく、ユーザー定義リテラルで書く方法も考えられます。しかし、ユーザー定義リテラル(整数)は実際の整数リテラルとして有効な表現しか使えないという弱点があります。 今回の目的である可読性向上の目的には、今一歩使い勝手が悪いです。また、異なる型を与えないといけないという制約はユーザー定義リテラルを用いた場合でも満たさないといけないため、ユーザー定義リテラル(文字列)ではうまくいきません。ユーザー定義リテラル(文字列・テンプレート)があったらこんなラムダ式で囲むなんていう方法を取らなくてすむようになります。

*1:10/07訂正:もともとは0bxxxx1111と書いていましたが、誤りでした

*2:時代はC++17だというのに、いまだにループで回すみたいなコードではなく実質リターン文ひとつみたいなコードを書いてしまっています(別に悪いというわけではないはずですが)。あと-Wparenthesesに怒られますが、演算子の優先順位は把握している(し、スペーシングもそれを反映したものになっている)のになぁって思ってしまいます。まぁ優先順位を把握していないプログラマーに不親切だから、常識的にわかる優先順位以外はかっこでくくろうという意見も分からないではないですが。特にC++は暗黙変換で型検査を通ってしまう怖い言語なので、用心しようという姿勢は大切ですね(このコードでは暗黙変換を使っているわけですが)。