10進文字列を高速に整数に変換する

"01234567"のようなバイト列があるとする。ここから1234567を得たい

このようなデータをuint64にキャストすると0x3736353433323130となる

リトルエンディアンでかつ ASCII もしくはその拡張とする

0x3030303030303030を引く(もしくは XOR をとる)ことで0x0706050403020100となる

なんかこいつに重みをつけて足すのはビットカウントや総和の応用でできる気がしますね?

SWAR と呼ばれるテクニックらしい

ということで:

code:atoi1.c

u = ((u & 0x00ff00ff00ff00ff) * 10) + ((u & 0xff00ff00ff00ff00) >> 8)

u = ((u & 0x0000ffff0000ffff) * 100) + ((u & 0xffff0000ffff0000) >> 16)

u = ((u & 0x00000000ffffffff) * 10000) + ((u & 0xffffffff00000000) >> 32)

1回目では下位に10をかけて上位と足す。つまり0x0043002d00170001

0x43=67, 0x2d=45, ...

2回目では0x000011d70000007b、3回目では0x000000000012d687=1234567となり計算できていることがわかる

ところで1回目の和の各部分の結果は99以下なので、8ビットの範囲に収まりマスクする必要がない。

また、2回目と3回目では合計4つの部分を足し合わせているが、普通に足しても4つの部分に分解することになるので分割統治の意味が薄い。これを意識して書き直すと:

code:atoi2.c

u = u*10 + (u>>8)

u = (u&0xff)*1000000 + ((u>>16)&0xff)*10000 + ((u>>32)&0xff)*100 + (u>>48)&0xff

さらに計算を減らしたい。$ 10^8 < 2^{32}なので、結果は32ビットの範囲に収まる。つまり上位32ビットはどうなってもいいので32ビット離れた部分ではマスクを共有してもいい:

code:atoi3.c

const mask = 0x000000ff000000ff

u = u*10 + (u>>8)

u1 = u&mask

u1 = u1*1000000 + (u1>>32)*100

u2 = (u>>16)&mask

u2 = u2*10000 + (u2>>32)

u = (u1+u2)&0xffffffff

ここでu1について式変形をすると

u1*1000000 + (u1>>32)*100 = (u1*(1000000<<32) + u1*100)>>32 = (u1 * ((1000000<<32)+100))>>32

乗算(とシフト)を減らせる

u*10 + (u>>8)もいけそうに見えるが10=0b1010であることを考えるとする必要がない

変形すると(u*2561)>>8となるが、2561は3つしか立っているビットがない整数なので、最適化で(u<<3) + (u<<1) + (u>>8)になる。結局同じ

100や10000、1000000は多くのビットが立っているのでシフト和に分解されない。そのため積をまとめるモチベーションが出る

code:atod4.c

const mask = 0x000000ff000000ff

const c1 = (1000000<<32) + 100

const c2 = (10000<<32) + 1

u = u*10 + (u>>8)

u = ((u&mask)*c1 + (((u>>16)&mask)*c2)>>32

めちゃくちゃ演算が減ってHappy……

ところで入力が8というのは多くの場合大きすぎて扱いにくい。4にしてみると、上位32ビットに広大な空間が生まれるのでそこで一回の乗算で計算できそう:

code:atoi5.c

const c = 1 + (10<<48) + (100<<16) + (1000<<32)

u = ((u & 0xff00ff00)<<24) | (u & 0x00ff00ff) // xyzw -> 0x0z0y0w

u = (u * c)>>24

参考

Parsing decimal numbers — part 1: SWAR

SWAR explained: parsing eight digits – Daniel Lemire's blog