ring buffer

古い本の整理をしていたら'93/5月号のInterfaceが出てきた。
RS-232Cのデバイスドライバの特集。
リングバッファの実装のところで比較演算子を使わない方法というのが面白かったのでメモ。

リングバッファの場合、バッファの終端に来たらポインタをバッファの先頭に戻す必要がある。
著者は比較演算子によるブランチはコストが高いという理由からバッファのアドレスを切りの良いところに置いて論理演算のみでポインタをバッファの先頭に戻している。

例えば８バイトのバッファで先頭のアドレスが0x8000であれば、バッファの終端まで書き込んだときポインタのアドレスは0x8008となる。
この時、0x0007でANDをとれば0x0000となり、これに先頭のアドレス0x8000をORすれば先頭アドレスに戻る。ポインタが終端になければ0x0007でANDをとってもポインタのアドレスは変わらない。

0x8000 & 0x0007 | 0x8000 = 0x8000
0x8001 & 0x0007 | 0x8000 = 0x8001
0x8002 & 0x0007 | 0x8000 = 0x8002
...
0x8007 & 0x0007 | 0x8000 = 0x8007
0x8008 & 0x0007 | 0x8000 = 0x8000

へぇ〜って思った。