bswap

今日のコード。Windows XPMac OS X 10.6.8で動作することを確認しています。


バイナリプログラミングをやっていると、エンディアンに応じてバイトオーダーをひっくり返す(バイトスワップ)というのがよくあります。バイトスワップは高速にやろうと思うと中々厄介で、マクロにすると分かりづらいし、ライブラリ関数にするとインライン展開が効かなくなります。というわけでいい方法がないのか少しだけ調べてみました。


ここまでのまとめ。

  • x86というか80486では、CPUにbswap命令があるのでこれを使うとよい*1
  • htonl、htons、ntohl、ntohs関数を使うとbswap命令を使ってくれることがある
  • Visual Studioのstdlib.hにはバイトスワップのための関数群が容易されている*2
  • ヘッダにコードを書いてしまえばインライン展開が効く


なかなか面倒そうだな、ということが分かりました。でも、こんなよくあることは誰かがうまいことやってくれているはずです。ということでさらに調べてみると、以下のようなコードが見つかりました。


コードを眺めてみると以下のようになっているようです。

  • ARM、x86x86_64の場合は専用のCPU命令を呼び出す
  • ヘッダにコードを書いてインライン展開が効くようにしている
  • 知らないCPUに対しては普通にCのコードを呼び出す


Cだけで書くならこんな感じでヘッダに書くのが定石みたいですね。まるで魔法のようですが、自分で計算してもコンパイルして実行してもちゃんと動きます。特に、bswap_32。右シフトも左シフトも論理和論理積もすべて二回ずつなのでとても美しい感じがします。

static inline uint16_t bswap_16(uint16_t x) {
  return (x >> 8) | (x << 8);
}

static inline uint32_t bswap_32(uint32_t x) {
  x= ((x << 8) & 0xFF00FF00) | ((x >> 8) & 0x00FF00FF);
  return (x >> 16) | (x << 16);
}

static inline uint64_t bswap_64(uint64_t x) {
    union {
        uint64_t ll;
        uint32_t l[2];
    } w, r;
    w.ll = x;
    r.l[0] = bswap_32 (w.l[1]);
    r.l[1] = bswap_32 (w.l[0]);
    return r.ll;
}

bswap_32、普通に考えたらこうですよね。

static inline uint32_t bswap_32(uint32_t x) {
  return
		(((x & 0x000000ff) >> 0x00) << 0x18) |
		(((x & 0x0000ff00) >> 0x08) << 0x10) |
		(((x & 0x00ff0000) >> 0x10) << 0x08) |
		(((x & 0xff000000) >> 0x18) << 0x00);
}

んで、こうなって・・・

static inline uint32_t bswap_32(uint32_t x) {
  return
		((x & 0x000000ff) << 0x18) |
		((x & 0x0000ff00) << 0x08) |
		((x & 0x00ff0000) >> 0x08) |
		((x & 0xff000000) >> 0x18);
}

こうですよね。

static inline uint32_t bswap_32(uint32_t x) {
  return
		(x << 0x18) |
		((x & 0x0000ff00) << 0x08) |
		((x & 0x00ff0000) >> 0x08) |
		(x >> 0x18);
}

さっきのbswap_32よりも、論理和が一回多くなります。それだけですけど、それを減らせるってのがさっきのbswap_32のすごいところ。Graphic Gems Iにはこういうことが一杯書いてありそうだな。

Graphics Gems (Graphics Gems - IBM)

Graphics Gems (Graphics Gems - IBM)