はじめに
ビット操作
整数の各ビットは、2進数の値を格納するために使えます。
真か偽、含めるか含めないか、オンかオフかといった2値の情報を扱う場面は多いため、Nビット整数の2進表現を使うと、N個の項目の2値の状態をコンパクトに符号化できます。
そのため、アセンブリではビットやバイトを操作する能力が欠かせません。
x86-64の命令セットには、ビット操作の命令が豊富に用意されています。
単一ビットの操作
これらの命令は、オペランド内の単一のビットを対象に動作します。
いずれも2つのオペランドを取り、2つ目のオペランドが、1つ目のオペランド内で操作するビットのインデックスを表します。
いずれも、選択したビットを**キャリーフラグ（CF）**にコピーします。
| 名前 |
説明 |
bt |
オペランドを変更せずに、ビットをCFにコピーします |
bts |
ビットをCFにコピーし、宛先オペランドでそのビットをセットします |
btr |
ビットをCFにコピーし、宛先オペランドでそのビットをクリアします |
btc |
ビットをCFにコピーし、宛先オペランドでそのビットを反転（補数化）します |
ビット演算
ビット演算は、オペランドのすべてのビットに対して行われます。
どのビット演算にも、その演算と同じ名前の命令があります。
| 名前 |
説明 |
and |
両方のビットが1なら1 |
or |
少なくとも一方のビットが1なら1 |
xor |
ビットが異なれば1 |
not |
ビットが0なら1、1なら0 |
ほとんどの命令は2つのオペランドを取り、両方に対してビット演算を行い、結果を宛先オペランドに格納します。
例外はnotで、宛先オペランドを1つだけ取ります。
マスク
1を「含める」、0を「含めない」とそれぞれ解釈するとき、その整数を_ビットマスク_（単に_マスク_とも）と呼びます。
ビットマスクは項目を「選別」します。i番目のビットが0ならi番目の項目が除外され、1なら含まれるからです。
また、整数のあるビットを含め、それ以外を除外するためにビットマスクを使うこともよくあります。
たとえば、Aを次の2進表現を持つ整数とします。
| インデックス |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
| ビット |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
同様に、Mを次の2進表現を持つ整数とします。
| インデックス |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
| ビット |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
どちらも8ビットの整数です。
このとき、MはAの0、2、3番目のビットを選び、残りを除外していると言えます。
先ほど説明したビット演算命令は、マスクを使った整数の操作に役立ちます。
たとえば、次のとおりです。
-
Mが選択していないAのビットをクリアするには、ビット単位のANDを取ります：A AND M。
-
Mが選択しているAのビットをセットするには、ビット単位のORを取ります：A OR M。
test命令
test命令は、2つのオペランド間でビット単位のANDを取り、その結果に応じてフラグを設定します。
Aを1つ目のオペランド、Bを2つ目のオペランドとすると、次のようになります。
| フラグ |
設定される条件 |
CF |
常にクリア |
ZF |
A AND B == 0 |
SF |
A AND Bの符号ビットがセットされている |
OF |
常にクリア |
この命令は2つのオペランドを取り、フラグを更新しますが、オペランド自体は変更しません。
シフト演算
これらの命令は、宛先オペランドのビットを、2つ目のオペランドで指定された位置数だけ移動させます。
2つ目のオペランドには、定数（immediate）か、レジスタcl（rcxの下位8ビット）を指定する必要があります。
| 名前 |
説明 |
shl/sal
|
ビットを左にシフトします |
shr/sar
|
ビットを右にシフトします |
2つ目のオペランドのカウントは5ビット（宛先オペランドが64ビットの場合は6ビット）にマスクされる点に注意してください。
それより上のビットは事実上無視されます。
つまり、最大のシフト量は31（64ビットのオペランドでは63）です。
shl/sal
shlとsalはまったく同じ演算を行い、一方は他方の別名です。
左シフトを行うと、シフト量の分だけ列の端に近いビットは、まずCFに移動し、その後破棄されます。
一方、シフト量と同じ数のクリアされた新しいビットが先頭に追加されます。
整数の各ビットは2の累乗を表すため、n桁の左シフトは、その整数を2ⁿ倍するのと同じ効果があります。
shr/sar
ビットを右に移動させる命令には、shrとsarの2つがあります。
どちらの命令を使う場合でも、シフト量の分だけ列の先頭に近いビットは、まずCFに移動し、その後破棄されます。
一方、シフト量と同じ数の新しいビットが末尾に追加されます。
両者の違いは、shrは左端に0を入れるのに対し、sarは最上位ビットがセットされていれば1を、そうでなければ0を入れる点です。
つまり、sarは符号付き整数のシフトで符号を保つということです。
整数の各ビットは2の累乗を表すため、shrを使ったn桁の右シフトは、2ⁿによる符号なしの除算を行うのと同じ効果があります。
同様に、sarを使ったn桁の右シフトは、2ⁿによる符号付きの除算を行うのと同じ効果があります。
ローテーション演算
これらの命令は、宛先オペランドのビットを、2つ目のオペランドで指定された位置数だけ移動させます。
2つ目のオペランドには、定数（immediate）か、レジスタcl（rcxの下位8ビット）を指定する必要があります。
ローテーションとシフトの違いは、ローテーションではビットを破棄も追加もしないことです。
シフトなら破棄されるはずのビットは、代わりに反対の端へ移動します。
つまり、すべてのビットが残り、それぞれが場所を入れ替わります。
| 名前 |
説明 |
rol |
ビットを左にローテートします |
ror |
ビットを右にローテートします |
2つ目のオペランドのカウントは5ビット（宛先オペランドが64ビットの場合は6ビット）にマスクされる点に注意してください。
それより上のビットは事実上無視されます。
つまり、最大のローテーション量は31（64ビットのオペランドでは63）です。
その他のビット操作命令
ほかにも役立つビット操作命令があります。
| 名前 |
説明 |
popcnt |
セットされているビットの数を数えます |
bsr |
最上位のセットされたビットのインデックスを取得します。ビットが1つもセットされていない場合、結果は不定です |
bsf |
最下位のセットされたビットのインデックスを取得します。ビットが1つもセットされていない場合、結果は不定です |
これらの命令はすべて、2つの16ビット、32ビット、または64ビットのオペランドを扱います。
8ビットのオペランドには使えません。
説明
友達から、大事な秘密が書かれたメッセージが届きました。
他の人に簡単に読まれないように、メッセージは一連のビット操作によって暗号化されています。
メッセージの復号を助けるメソッドを書く必要があります。
このコンセプトで登場する単一ビット命令は次のとおりです：
| 名前 |
説明 |
| bt |
どのオペランドも変更せず、そのビットをCFにコピーします |
| bts |
そのビットをCFにコピーし、宛先オペランドでそのビットをセットします |
| btr |
そのビットをCFにコピーし、宛先オペランドでそのビットをクリアします |
| btc |
そのビットをCFにコピーし、宛先オペランドでそのビットを補数化（反転）します |
このコンセプトで登場するビット演算命令は次のとおりです：
| 名前 |
説明 |
| and |
両方のビットが1のとき1 |
| or |
少なくとも片方のビットが1のとき1 |
| xor |
ビットが異なるとき1 |
| not |
ビットが0だったとき1、1だったとき0 |
このコンセプトで登場するシフト命令は次のとおりです：
| 名前 |
説明 |
| shl/sal |
ビットを左にシフトします |
| shr/sar |
ビットを右にシフトします |
このコンセプトで登場する回転命令は次のとおりです：
| 名前 |
説明 |
| rol |
ビットを左に回転させます |
| ror |
ビットを右に回転させます |
このコンセプトで登場するその他の命令は次のとおりです：
| 名前 |
説明 |
| popcnt |
セットされているビットの数を数えます |
| bsr |
最上位のセットビットのインデックスを取得します。セットされているビットがない場合、結果は未定義です |
| bsf |
最下位のセットビットのインデックスを取得します。セットされているビットがない場合、結果は未定義です |
1. マスクを抽出する
メッセージは16ビットの整数にエンコードされています。
ただし、そのうち上位8ビットは実際にはメッセージの一部ではなく、復号で使う必要のあるマスクです。
16ビットの整数を受け取り、その上位8ビットを返すextract_higher_bits関数を実装してください。
extract_higher_bits(0b1010010011000101)
// => 0b10100100
2. メッセージを抽出する
マスクを抽出できるだけでは十分ではありません。メッセージも分離する必要があります。
16ビットの整数を受け取り、その下位8ビットを返すextract_lower_bits関数を実装してください。
extract_lower_bits(0b1010010011000101);
// => 0b11000101
3. 冗長ビットを抽出する
メッセージとマスクの両方でセットされているビットがいくつかあります。
これは後で使う、とても重要な情報です。
メッセージとマスクの両方をエンコードした16ビットの整数を受け取り、冗長ビットだけがセットされた8ビットの整数を返すextract_redundant_bitsを実装してください。
返される数値のビットは、メッセージとマスクの両方で1になっている位置で1にセットします。
それ以外のビットはすべて_クリア_します。
extract_redundant_bits(0b1010010011000101);
// => 0b10000100
4. メッセージのビットをすべてセットする
次に、マスクに従って、メッセージの中で1にセットする必要のあるビットがあります。
メッセージとマスクの両方をエンコードした16ビットの整数を受け取り、メッセージのビットを1にセットした結果を返すset_message_bits関数を実装してください。
メッセージのビットは、マスクのビットが1である位置で1にセットします。
それ以外のビットはすべて_変更せず_、すでにセットされていたビットはセットされたまま、すでにクリアされていたビットはクリアされたままにします。
set_message_bits(0b1010010011000101);
// => 0b11100101
5. 秘密鍵を回転させる
メッセージには明示されていないパズルのピースが1つあります。それが16ビットの数値0b1011001100111100です。
この数値は共有の秘密鍵であり、メッセージの復号に役立てるために使います。
そのためにはまず、秘密鍵のビットを、ある位置の数だけ左に回転させる必要があります。
その位置の数は、メッセージとマスクの両方でセットされている冗長ビットの数と同じです。
メッセージとマスクの両方をエンコードした16ビットの整数を受け取り、秘密鍵を回転させた結果を返すrotate_private_key関数を実装してください。
この結果は16ビットの整数です。
rotate_private_key(0b1010010011000101);
// => 0b1100110011110010
NASM（The Netwide Assembler、このトラックで使われているアセンブラー）は、0bを先頭に付けた2進数形式の定数をサポートしています。
また、可読性のために、定数の区切り文字としてアンダースコア（_）を使うこともできます：
PRIVATE_KEY equ 0b1011_0011_0011_1100
6. 秘密鍵を整形する
復号に使うために、秘密鍵は関連するビットを分離できるよう整形する必要があります。
秘密鍵を完全に整形するには、次のことを行います：
- 回転させます。
- 回転させた秘密鍵の下位8ビット部分を分離します。これがベース値です。
- 回転させた秘密鍵の上位8ビット部分を分離します。これはベース値に適用するマスクです。
- ベース値のうち、マスクでもセットされているビットを反転させます。
- その結果のすべてのビットを反転させます。
反転したビットは、0だった場合は1に、1だった場合は0になります。
メッセージとマスクの両方をエンコードした16ビットの整数を受け取り、完全に整形された8ビットの秘密鍵を返すformat_private_key関数を実装してください。
format_private_key(0b1010010011000101);
// => 0b11000001
7. 復号を完了する
関連するビットをすべてセットしたメッセージと、整形済みの秘密鍵がそろったら、それらを組み合わせて最終的なメッセージを手に入れましょう。
最終的なメッセージは16ビットの整数で、その内容は次のとおりです：
- 上位8ビットには、整形済みの秘密鍵が入ります。
- 下位8ビットには、関連するビットをすべてセットした後のメッセージが入ります。
メッセージとマスクの両方をエンコードした16ビットの整数を受け取り、完全に復号されたメッセージを16ビットの整数として返すdecrypt_message関数を実装してください。
この関数では、format_private_keyで生成した整形済みの秘密鍵と、set_message_bitsで関連するビットをすべてセットしたメッセージを利用します。
decrypt_message(0b1010010011000101);
// => 0b1100000111100101
学習演習
