論理演算

真偽値（0と1）の上の演算を論理演算 (logical operations) またはブール演算 (boolean operations) と言う。つまり，論理積，論理和，否定，及びそれらの組み合わせでできる演算のことだ。

論理積 ∧，論理和 ∨，排他的論理和 ⊕，否定 ¬ はそれぞれ以下のように定義される。

0 ∧ 0 = 00 ∨ 0 = 00 ⊕ 0 = 0¬ 0 = 1
0 ∧ 1 = 00 ∨ 1 = 10 ⊕ 1 = 1¬ 1 = 0
1 ∧ 0 = 01 ∨ 0 = 11 ⊕ 0 = 1 
1 ∧ 1 = 11 ∨ 1 = 11 ⊕ 1 = 0 

この章では，レジスタや主記憶の中身を「2進法で表された数」ではなく「真偽値の並び」として扱う演算命令について学ぶ。 そのような演算は，例えば以下のような場面で必要になる。

  • あるコンピュータに4つのスイッチ a, b, c, d が接続されており，それらが押下されているかどうかはそれぞれ，0xffbb 番地からの読み出しで得られる1バイトの値の第0〜3ビットに格納されている。このとき，スイッチ c が押下されているかどうか（第2ビットが1かどうか）を調べるにはどうしたらよいか?
  • ある動画像ファイル形式では，水平画素数 h（12ビット），垂直画素数 v（12ビット），画素の縦横比を表す符号 a（4ビット），フレームレートを表す符号 f（4ビット）を並べた32ビットの値を，定められた位置に含めなければならない。 与えられた h, v, a, f からこの32ビットの値を得るにはどうしたらよいか?　逆に，32ビットの値から h, v, a, f を得るにはどうしたらよいか?
  • あるコンピュータのCPUには乗算命令がない。このコンピュータでなるべく効率よく乗算を行うにはどのようにプログラムすればよいか?

ビットごとの (bitwise) 論理演算

下記の演算 &, |, ^, ~ は，それぞれ「ビットごとの論理積，論理和，排他的論理和，否定」と呼ばれる（C言語やJavaではこれらの演算記号を用いる）。 ビットごとの論理積，論理和，排他的論理和は，被演算数 a, b の第 i ビット同士の論理積，論理和，排他的論理和を並べたものだ。 ビットごとの否定は，被演算数 a の各ビットを反転（0は1に，1は0にする）したものだ。

    a = 1011100101110101 (= 0xb975)
    b = 1111111100000000 (= 0xff00)
とする。
a & b = 1011100100000000 (= 0xb900)
a | b = 1111111101110101 (= 0xff75)
a ^ b = 0100011001110101 (= 0x4675)
  ~ a = 0100011010001010 (= 0x468a)

機械語命令 AND, OR, XOR, NOT はそれぞれ上記の演算を表す。

    mov     ebx, 0xff0
    mov     eax, 0xb97531ca
    and     eax, 0xff00ff00   ; eaxの値は0xb9003100になる
    or      eax, ebx          ; eaxの値は0xb9003ff0になる
    xor     eax, 0xffff0000   ; eaxの値は0x46ff3ff0になる
    not     eax               ; eaxの値は0xb900c00fになる

AND, OR, XORは，ディスティネーションオペランドの一部のビットの値を変更したいときに使うことができる。

  • AND命令は，特定のビットを0にするために使える。
  • OR命令は，特定のビットを1にするために使える。
  • XOR命令は，特定のビットを反転するために使える。

例:

  • and eax, 0xff00ff00 では，eaxの第0〜7ビット及び第16〜23ビットが0になり，それ以外のビットは変化しない。
  • or eax, 0xff0 では，eaxの第4〜11ビットが1になり，それ以外のビットは変化しない。
  • xor eax, 0xffff0000 では，eaxの第16〜31ビットが反転し，それ以外のビットは変化しない。

一部のビットを0または1にすることを，「そのビットをマスクする」と言う。 また，0または1にしたいビットや反転したいビットを指定するためのビット列（上記の例の 0xff00ff00 や 0xff0 や 0xffff0000）のことを「ビットマスク」と言う（「レジスタXXの値はビットマスクを表す」のように言う）。

補足: TEST命令

TEST命令は，「ANDと同じ演算を行うが，結果をディスティネーションオペランドに代入しない」命令だ。CMP命令が「SUBと同じ演算を行うが，結果をディスティネーションオペランドに代入しない」のと類似している。CMPと同じく条件付きジャンプと組にして使うための命令であり，JZ または JNZ と組にして，「レジスタ（または主記憶内領域）の中のある1ビットが0かどうか（または複数のビットがすべて0かどうか）」を調べるのに使うことができる。

参考: xor eax, eax

問: xor eax, eax を実行すると，EAXの値はいくらになるか?

mov eax, 0 の代わりに xor eax, eax を使うことを好むプログラマもいる。 機械語にすると，前者は b8 00 00 00 00 の5バイト，後者は 31 c0 の2バイトだ。

シフト命令

SHL (shift logical left) は，ディスティネーションオペランド内の各ビットを左にずらす命令（左シフト命令）だ。 つまり，実行前の第0ビットの値が第1ビットに，実行前の第1ビットの値が第2ビットに，…，実行前の第30ビットの値が第31ビットに代入される。 実行前の最上位ビットの値はCFに代入される。 実行後の第0ビットの値は0になる。

何ビットずらすかを第2オペランドで指定できる。

    mov     eax, 0xcb20     ;   = 1100101100100000
    shl     eax, 1          ;    11001011001000000 (=0x19640)になる
    shl     eax, 3          ; 11001011001000000000 (=0xcb200)になる

上の例のように，計4ビットシフトすると，16進数の1桁分シフトしたのと同じになる。

同様に，SHR (shift logical right) は，右にシフトする命令だ。

    mov     eax, 0xcb20     ; = 1100101100100000
    shr     eax, 1          ;    110010110010000 (=0x6590)になる
    shr     eax, 3          ;       110010110010 (= 0xcb2)になる

  • 参考: SAR (shift arithmetic right) は，SHR とほとんど同じだが，「実行後の最上位ビットの値は実行前と同じ」である点だけが異なる（符号付き数を扱う場合は SAR の方が適している）。 SHR は，実行後の最上位ビットの値は0になる。

  • 参考: ROL (rotate left) は，SHL と同様に左シフトを行うが，実行前の最上位ビットの値を第0ビットに代入する（左端の値を右端に移動する）。 このような命令を巡回シフト命令（またはローテート命令）と言う。 右巡回シフトを行う ROR (rotate right) もある。

    • RCL (rotate left with carry) は，ROL と同様だが，実行前の最上位ビットの値をCFに代入し，実行前のCFの値を第0ビットに代入する（CFも含めて巡回シフトする）。 逆方向に巡回シフトする RCR (rotate right with carry) もある。

論理演算とシフト演算と乗除算

ビットをマスクする演算やシフト演算は，以下のように2進数に対する乗除算として解釈することもできる。

  • あるレジスタの下位 k ビットだけ残し，それ以外のビット（上位 32 − k ビット）を0にすることは，2k で割った余りを計算しているのと等しい（例えば，下位8ビットだけ残すことは，256で割った余りを計算しているのと等しい）。
  • あるレジスタを k ビット左にシフトすることは，2k 倍することと等しい（例えば3ビット左にシフトすることは8倍することと等しい）。
  • あるレジスタを k ビット右にシフトすることは，2k で割ることと等しい（ただし小数点以下は切り捨て）（例えば3ビット右にシフトすることは8で割ることと等しい）。

例えば「2倍する」「2で割る」などは乗除算命令を使うよりシフト命令を使った方が簡単だ。 どのレジスタに対しても実行できるし，処理時間も短い。 「2で割った余り（偶数なら0，奇数なら1）を求める」のも，最下位ビット以外を0にマスクすれば済む。

シフトと加算による乗算

小学校で習った10進法の筆算について考えよう。 34567 × 123 は以下のように計算できる。

   34567
x)   123
---------
  103701  ← 被乗数 × 乗数の第0桁
  69134   ← 被乗数 × 乗数の第1桁
 34567    ← 被乗数 × 乗数の第2桁
---------
 4251741  ← 上記の積の和

つまり，123 = 100 + 20 + 3 なので，被乗数の3倍と20倍と100倍を求めて和を計算すればよい，というわけだ。

2進法でも同じことだ。 被乗数と乗数の1桁との積を求めてすべて合計すればよい。 下記は，0xa7 (= 167) と 0x16 (= 22) の積を計算している。結果は 0xe5a (= 3674) だ。

    10100111
x)     10110
-------------
           0  ← 被乗数 × 乗数の第0桁
   10100111   ← 被乗数 × 乗数の第1桁
  10100111    ← 被乗数 × 乗数の第2桁
        0     ← 被乗数 × 乗数の第3桁
10100111      ← 被乗数 × 乗数の第4桁
-------------
111001011010  ← 上記の積の和

2進法では「乗数の1桁」は0か1なので，「乗数の第 i ビットが1ならば，被乗数を i ビット左シフトしたものを結果に加える」というアルゴリズムで乗算を行える。

乗算命令がなくても上記の方法で乗算を行うことができる。 定数倍する場合は，ループを使わなくても以下のように記述できる。

    ; eaxの値を10倍する
    mov     ebx, eax
    shl     eax, 2      ; 元の4倍
    add     eax, ebx    ; 元の5倍
    shl     eax, 1      ; 元の10倍
    ; eaxの値を100倍する
    mov     ebx, eax
    shl     eax, 1      ; 元の2倍
    add     eax, ebx    ; 元の3倍
    shl     eax, 3      ; 元の24倍
    add     eax, ebx    ; 元の25倍
    shl     eax, 2      ; 元の100倍

練習問題

以下の問題で述べるプログラムを作りなさい。

リポジトリのルートディレクトリにサブディレクトリ chap8 を作成し，その中にソースファイルを置きなさい。

演習1.8-1　EAXレジスタの値を16進数で標準出力に出力するサブルーチン print_eax_hex を，print_eax_hex.s というファイルにアセンブリ言語で記述しなさい。 ただし，乗除算命令 (DIV, IDIV, MUL, IMUL) を使わないこと。 リポジトリ中にサブディレクトリ chap8 を作成し，その中に print_eax_hex.s を置くこと。 作成したプログラムを共有リポジトリにpushしなさい。

下記の仕様を満たすように作成すること。

  • print_eax_hex.s には，サブルーチン print_eax_hex の定義（及びこのサブルーチンが必要とするデータ領域の定義）のみ記述すること。特に，print_eax_hex.s の中でラベル _start を定義してはいけない。
  • ラベル print_eax_hex をglobal宣言すること。
  • print_eax_hexを1回呼び出したときに出力される文字列は，演習1.4-2における出力文字列と同じ仕様を満たすこと。
  • print_eax_hex の呼び出し前と復帰後で汎用レジスタ (eax, ebx, ecx, edx, esi, edi, ebp, esp) の値が変化しないようにすること。

演習1.8-2　EAXレジスタとEDXレジスタの値の積をEAXレジスタに代入するサブルーチン mul_eax_edx を，mul_eax_edx.s というファイルにアセンブリ言語で記述しなさい。 ただし，乗除算命令 (DIV, IDIV, MUL, IMUL) を使わないこと。 リポジトリ中のサブディレクトリ chap8 の中に mul_eax_edx.s を置くこと。 作成したプログラムを共有リポジトリにpushしなさい。 ただし，演習1.8-1のプログラムをコミットしたメンバーとは別のメンバーがコミットすること（共有リポジトリ上のmul_eax_edx.sの最終変更者が，print_eax_hex.sの最終変更者と異なるようにすること）。

下記の仕様を満たすように作成すること。

  • mul_eax_edx.s には，サブルーチン mul_eax_edx の定義（及びこのサブルーチンが必要とするデータ領域の定義）のみ記述すること。特に，mul_eax_edx.s の中でラベル _start を定義してはいけない。
  • ラベル mul_eax_edx をglobal宣言すること。
  • mul_eax_edx は，標準出力に何も出力しない。
  • mul_eax_edx の呼び出し前と復帰後で，EAX以外の汎用レジスタ (ebx, ecx, edx, esi, edi, ebp, esp) の値が変化しないようにすること。

演習1.8-3　N という名前の名前付き定数を定義し，N の階乗を出力するアセンブリ言語プログラムを，factorial.s という名前のファイルに記述しなさい。 ただし，以下を満たすこと。

  • 乗算命令 (MUL, IMUL) を使わず，演習1.8-2で作成したファイル mul_eax_edx.s 中のサブルーチン mul_eax_edx を呼び出すことで乗算を行いなさい。
  • 出力は，演習1.8-1で作成したファイル print_eax_hex.s 中のサブルーチン print_eax_hex を呼び出すことで行いなさい。

print_eax_hex.s, mul_eax_edx,s は，演習1.8-1〜1.8-2の成果物をそのまま使用すること（この演習問題用に変更してはいけない）。 N は factorial.s 中でEQU命令を使って定義しなさい。 N の値は 0 以上 12 以下とする。 ソースファイル factorial.s をサブディレクトリ chap8 に置き，共有リポジトリにpushしなさい。 ただし，3人グループの場合，演習1.8-1及び演習1.8-2のプログラムをコミットしたメンバーとは別のメンバーがコミットすること（共有リポジトリ上のfactorial.sの最終変更者が，print_eax_hex.sの最終変更者ともmul_eax_edx.sの最終変更者とも異なるようにすること）。2人グループの場合はどちらがコミットしても構わない。

results matching ""

    No results matching ""