概要
bit rotation で CPU が1つのレジスタの幅を超えた場合、または 24 bit などの2の累乗の値ではない 8 の倍数では複数の bit rotation 命令を組み合わせて目的を達成することができる. 本説明ではすべて変数は符号なしの扱いでの計算とする. x64 の命令として記載する.
左循環
C r1 r0 |instructions
-----------+-----------
x 7654 3210|
|shl $1,%r0 -> add %r0,%r0
3 7654 210z|
|rcl $1,%r1 -> adc %r1,%r1
7 6543 210z|
|adc $0,%r0
z 6543 2107|
左側の表記の意味
C: carry flag
r1, r0: 4 bit レジスタ, 理解のために少なくしてある
数字: r1, r0 に最初にあった bit 番号. 数値ではない(重要).
z: 数値の 0
x: 未初期化値carry は1つであるものの入力と出力を区別するため命令前後の挙動の理解が極めて重要. 命令に対して行を半分ずらして記載すべきなのだが、単なるテキストではできないので1行ごとに空白を入れている.
- shl $1: r0 が左にずれて, 数値 0 が r0 bit 0 に 入り, 出力の carry に r0 bit3 の値が入る.
- rcl $1: r1 が左にずれて, 入力の carry が r1 bit 0 に入り, 出力 carry に r1 bit 3 の値が入る.
- adc $0: 入力の carry が r0 bit 0 に加算される. r0 bit 0 は shl 命令により数値は 0 なので, 桁上りなく r1 bit 3 の値が入る.
左シフト1回は数値の 2 倍になる特徴があるので add %r0,%r0 に変えても結果は同じ. carry 入力付き左循環1回は2倍+carryとなるので adc %r1,%r1 に変えても結果は同じ.
右循環
C r2 r1 r0 |instructions
----------------+-----------
x xxxx 7654 3210|
|mov %r0,%r2
x 3210 7654 3210|
|ror $1,%r2
0 0321 7654 3210|
|rcr $1,%r1
4 0321 0765 3210|
|rcr $1,%r0
0 0321 0765 4321|
left rotation の後にその値の bit 0 を 変数に取り込みたい場合
これは複数のレジスタをまたがない場合. Cで書くとこうなる.
d = (d << 1) | (d >> (width - 1)); q |= d & mask;
これは mask の値を限定しない場合は関数最後を除き下記のように一時的なレジスタを介す必要がある.
rol $1,%d mov %d,%temp and $mask,%temp or %temp,%q
mask = 1 かつ q の bit 0 = 0 だと保証されている場合は下記のようにして mov, and, or を adc $0 だけで済ますことが可能. また adc $0 により carry flag が更新されるので2度連続複数の変数への代入は不可能.
rol $1,%d adc $0,%q
さらなる条件:
x64 では adc $immediate,%register の addressing mode が存在するが、 adc %register,%register のみの CPU も多い. この場合は rol の実行前に一時的なレジスタへ 0 を代入しておく必要がある. レジスタを 0 に代入した時点で carry flag = 0 になることが大半である.
最後の説明は条件だらけだがつかえるかもしれない.
