Lecture on Programming I 7/13
Menu Menu
先週の復習
Java の演習
授業について
この授業は今日まで。課題の提出は、電子メールで7月一杯までとします。それ以降は受け付けません。試験はありません。宿題あるいは授業のレポートのどちらかを一つも提出してない人に単位を出すことはありません。
アセンブラ
コンピュータの中のCPUが直接実行する言語。あるいは、それを一応人間が読める形にしたもの。CPUが実行する命令とも呼ばれる。機械語、マシンコードなどと呼ばれることがある。現代のコンピュータは、実行する命令とデータが同じ記憶装置(メモリ)上に置かれることが特徴である。
メモリ
コンピュータのメモリは、1/0を格納するbit(ビット)と呼ばれるものの集合である。これを、8bit (byte)あるいは、それをさらにまとめた 16bit, 32bit, 64bit 単位で、任意にアクセス(読み書き)することができるようになっている。CPU によって、32bit をword と呼ぶこともある。今は、32bit CPU が主流なので、メモリを32bit (word) 単位で取り扱うことが多い。アクセスは、byte単位ごとに付けられたaddress(アドレス)と呼ばれる番号でアクセスする。つまり、メモリは、address でアクセスする巨大な配列である。
これをbyte の配列ではなく、word の配列とみなすこともできるが、その場合は、アドレスは4の倍数になることに注意しよう。
アドレスは最近のアーキテクチャでは32bit である。しかし、どのアドレスのメモリが実際のメモリにどう対応するかは、それほど自明ではない。これに関しては OS の授業で勉強することになる。
16進数
コンピュータのハードウェアに近い部分では、16進数で考えるのが便利である。16進数は、0,1,2,3,4,5,6,,7,8,9,a,b,c,e,f で表す。Perl では、0x を先頭につけて16進数を表す。以下の計算をPerlを使っておこなえ。
Perl で16進数を表示するには、
printf("%x",123456)
などとする。
10000 は16進数でいくつか?
0x1000 は10進数でいくつか?
1000+0x2134 を計算せよ
100000 を表すのに何バイト必要か? 各バイトは16進数でいくつになるか?
0x1234 の16倍はいくつか?
0x12345 を 0x100 で割った余りは?
0x12345 を 2 で徐々に割っていく。0になるまで、数字がどのように変化するかを
16進数と10進数で示せ
CPU のアーキテクチャ
機械語は、メモリとCPUのデータのやり取りを指示する。CPU 側には、Regisetr (レジスタ)と呼ばれる少数(1-32程度)のメモリがあり、一旦、そこに値を格納して、そこで計算をするのが普通である。i386 (IA32 とも呼ばれる) 系のCPUには、図のようなレジスタがある。
命令は、通常、1byteから10数byte程度の大きさである。RISC系のCPU では、32bit 固定長であることが多い。
データの移動や計算に関する命令
命令には、例えば、
レジスタに定数を入れる
レジスタ間で計算をする (足し算とかかけ算とか)
命令で指示されたアドレスのメモリからデータをレジスタに持って来る
あるレジスタの値のアドレスのメモリからデータをレジスタに持って来る
などがある。特に命令やデータを指し示すアドレスを指しているデータをPointer(ポインタ) という。アドレスのことを番地ともいう。
制御に関する命令
命令は、メモリに格納された順に一つ一つCPUが読みだし、実行されるのが普通である。つまり、次に実行される命令のアドレスというのがある。このアドレスもレジスタに格納されているのが普通である。IA32 では、IP (Instruction Pointer)というレジスタに格納されている。IP を直接操作すると、次にどの命令を実行するかを変更することができる。これにも専用の命令が用意されている。
命令に書いてあるアドレスを次の命令のアドレスとする (Jump)
何か条件が満たされたときに、指示されたアドレスへJumpする
特に、以下のような一連の動作をサブルーチン呼出し(Call)という。
次の命令のアドレスを特別なスタックにプッシュする(戻り番地をとっておく)
指示されたアドレスから命令を実行する
そして、
とってある戻り番地をIPに戻し、そこから命令を実行する
が、Return である。これが、関数呼出しに相当する。Java や、Perl
の method 呼出しは、呼出し番地を決める方法が複雑なだけで、基本的には、これと同じである。
命令の形式
機械語は、だいたい、二つから三つの部分で構成されている
命令
命令と対象
命令と入力対象と出力対象
命令部分をOpcode (オペコード)、対象部分をOperand (オペランド)という。
Operand には、レジスタやアドレスが来るのだが、複数のレジスタと定数を組み合わせた形式もある。これらは、配列などのアクセスに適した形式となっている。これを、Addressing Mode という。
レジスタ
直接アドレス
間接アドレス (指し示したアドレスに格納されているアドレス)
レジスタ間接 (レジスタで示されたアドレス)
一つのレジスタで指示する
一つのレジスタの値に定数を足した形
二つのレジスタの和の値をアドレスとする
二つのレジスタの和の値に定数を足してアドレスとする
だいたい、一つのCPUで、数十から数百の命令がある。それにアドレッシングモードが入るので実際の命令数は膨大である。しかし、大半は特殊なものであり、通常使われる命令は極少数である。IA32の命令はIA32の命令 (Unix Assembler)
のようになっている。
データの型
機械語が扱う形式は決まっている
1byte の正の整数 0〜255
1byte の整数 -128〜127
4byte の正の整数 0〜4294967296
4byte の整数 -2147483648〜2147483647
通常は整数は「2の補数」という形で表現されている。例えば 2bit ならば、
10 -2
11 -1
00 0
01 1
となる。最上位ビットが符号を表すが符号付き整数とか異なることに注意しよう。
メモリをアクセスするときに、
1byte 単位でアクセスするのか
2byte 単位でアクセスするのか
4byte 単位でアクセスするのか
を決定することが重要である。
簡単な例1
入力から出力をコピーする簡単なプログラム
.text # プログラム開始
.globl main # main を他から呼び出せるようにする宣言
main: # ここが main というアドレスだというラベル
pushl %ebp # おまじない
movl %esp,%ebp # おまじない
.L2: # loop 用のラベル
call getchar # 入力を読み込む
cmpl $-1,%eax # -1 だったら終わり
je .L3 # 終わりだったら .L3 にjump
pushl %eax # 出力をスタックにつむ
call putchar # 出力ルーチンを呼び出す
addl $4,%esp # スタックを元に戻す
jmp .L2 # .L2 に飛ぶ
.L3:
leave # おまじない
ret # 帰る
簡単な例2
レジスタ同士の値の交換
movl %eax,%ecx movl %ebx,%eax movl %ecx,%ebx (余計なレジスタを使わない方法は?)メモリからのデータの読みだし、メモリへの書き出し
.comm data,256,1
で領域を取る。
movl $data,%ebx movl (%ebx),%eax incl %eax movl %eax,(%ebx)足し算
addl %eax,(%ebx)簡単な例2
スタック
サブルーチン・コールがあるので、現代のCPUは、必ず特別なスタックを持っている。これを使って、一時変数やメソッド変数を実現するのが普通である。
Post-Increment
push %eax movl %eax,(%esp) incl %espPre-Decrement
popl %eax decl %esp movl (%esp),%eax
コンパイラ
コンパイラは、より人間向けのプログラミング言語を機械語に翻訳する。これに関しては、コンパイラの授業で説明する。しかし、簡単な対応があることがわかるだろう。
Java の場合は、
Java ソース => Java 仮想機械コード => Native 機械コード
仮想機械による実行 CPU による直接実行
という手順となる。
Perl はバイトコード・インタプリタなので、
Perl ソース => Perl バイトコード
仮想機械による実行
となる。
アセンブラのプログラム
通常は、Mission Critical な部分にのみアセンブラを使う。特に、適当なコンパイラの出力を人間が書き直す手法を使うことが多い。ゲームプログラミングや、デジタル信号処理では、それが普通であろう。しかし、この場合に計算量そのものが変わることは少ない。通常は、数倍程度の速度の差に留まる。それが重要な場合に行なう。
アセンブラの使い方
file.s という.s という名前で作る。gcc file.sで a.out ができる。
./a.outという形で走らせる
gdbの使い方
gdb a.out
とする。dissassemble コマンドで命令が表示される
(gdb) disass main
Dump of assembler code for function main:
0x8048440 <main>: pushl %ebp
0x8048441 <main+1>: movl %esp,%ebp
main に breakpoint をかけて run する。
(gdb) b main
Breakpoint 1 at 0x8048443
(gdb) run < data
Starting program: /usr/home/teacher/kono/a.out
Breakpoint 1, 0x8048443 in main ()
nexti で一命令実行する。
Breakpoint 1, 0x8048443 in main ()
(gdb) nexti
0x8048448 in main ()
p でレジスタの内容を表示する
(gdb) p $eax
$1 = 49
data のアドレスの内容を表示する
(gdb) x/20x &data
0x8049560 <data>: 0x00000000 0x00000000 0x00000000 0x00000000
0x8049570 <data+16>: 0x00000000 0x00000000 0x00000000 0x00000000
0x8049580 <data+32>: 0x00000000 0x00000000 0x00000000 0x00000000
0x8049590 <data+48>: 0x00000000 0x00000000 0x00000000 0x00000000
0x80495a0 <data+64>: 0x00000000 0x00000000 0x00000000 0x00000000
メモリがない場合
どこかを指している場合
Segmentation Violation, Illigal Instruction とは..
メモリのクリア
特定のメモリ領域を0 で埋めるプログラムを作れ
メモリのコピー
特定のメモリ領域をコピーするプログラムを作れアドレスが重なっていても大丈夫なように修正せよ
以下の問題はオプションとします
音声処理
WAV フォーマット。sox コマンド。 vplay コマンドで音を出してみよう。
ヘッダを読み飛ばす
二つの音を足す
人工の音を作る (Synthesizer)
矩形波
三角波
サイン波
ADSR とは?
音の大きさを変える
shift が割算に相当する
エコーを加える
MMX 命令を使って見る
Binary Tree Sort をアセンブラで書く
(時間を測るにはどうすれば良いか?)
提出
以上の問題を
Subject: Practice on Programming I 7/13というサブジェクトで、18:30 までに、できるだけ、kono@ie.u-ryukyu.ac.jp までメールを出すこと。
宿題
残りは、
Subject: Report on Programming I 7/13というサブジェクトで、kono@ie.u-ryukyu.ac.jp までメールを出すこと。
(*) がついている問題は option とします。