Lecture on Programming I 7/5

Menu Menu

先週の復習

    先週は自習

授業について

課題の提出は、電子メールで7月一杯までとします。それ以降は受け付けません。試験はありません。宿題あるいは授業のレポートのどちらかを一つも提出してない人に単位を出すことはありません。

Typing の練習

今日も typing の練習をすること (20分)

結果をscript でメールすること。

整形した結果を、 

    Subject: Report on Programming I   7/5-typist
というサブジェクトで、kono@ie.u-ryukyu.ac.jp までメールを出すこと。 

    % rsh pw006 "Mail -s 'Report on Programming I   7/5-typist' kono@ie.u-ryukyu
.ac.jp" < typescript

アセンブラ

コンピュータの中の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)
などとする。 

    (1) 10000 は16進数でいくつか?
    (2) 0x1000 は10進数でいくつか?
    (3) 1000+0x2134 を計算せよ
    (4) 100000 を表すのに何バイト必要か? 各バイトは16進数でいくつになるか?
    (5) 0x1234 の16倍はいくつか?
    (6) 0x12345 を 0x100 で割った余りは?
    (7) 0x12345 を 2 で徐々に割っていく。0になるまで、数字がどのように変化するかを
	16進数と10進数で示せ
    (8) コンピュータの世界では、
             1K = 1024
             1M = 1024*1024
             1G = 1024*1024*1024
        とすることが多い。
	32bit で表すことができる数字の最大は、何G か?
     (9)	1MB のメモリは、100万バイトとどれだけ異なるか?
     (10)	4GB のハードディスクは、40億バイトの何%増しの容量があるか?

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 単位でアクセスするのか  (命令にbをつける)
    2byte 単位でアクセスするのか  (命令にwをつける)
    4byte 単位でアクセスするのか  (命令にlをつける)
を決定することが重要である。

簡単な例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                 # 帰る

アセンブラのプログラムの要素

領域のはじまりを示す
.text命令を置く領域の始まり。通常、read only
.dataデータを置く領域、初期化されない
.commデータを置く領域、初期化される
場所を確保する
.byte 1010バイト確保する
.word 1010ワード確保する
シンボルの性質を示す
.gloabl大域名であることを表す
ラベル.L3:その場所のアドレスを表すシンボル
命令
オペコードアセンブラの命令部分 movl
オペランドアセンブラのデータ部分 , で複数記述する %eax

アセンブラのプログラム

通常は、Mission Critical な部分にのみアセンブラを使う。特に、適当なコンパイラの出力を人間が書き直す手法を使うことが多い。ゲームプログラミングや、デジタル信号処理では、それが普通であろう。

しかし、この場合に計算量そのものが変わることは少ない。通常は、数倍程度の速度の差に留まる。それが重要な場合に行なう。

アセンブラの使い方

file.s という.s という名前で作る。 
	gcc file.s
で a.out ができる。 
	./a.out
という形で走らせる

簡単な例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

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
上の例を、gdb で trace して見よ。

メモリのある部分を0にする

    .text                       # プログラム開始
    .globl main                 # main を他から呼び出せるようにする宣言
    main:                       # ここが main というアドレスだというラベル
            pushl %ebp          # おまじない
            movl %esp,%ebp      # おまじない
            movl $.buf,%esi     # %esi にクリアする番地を入れる
            movl $20,%ecx       # %ecx にクリアするbyte数を入れる
    .L2:                        # loop 用のラベル
            movl $0,(%esi)      # 1byte クリア
            decl %ecx           # %ecx を一つ減らす
            cmpl $0,%ecx        # 0 だったら終わり
            jne .L2             # 終わりでなかったら .L2 にjump
    
            leave               # おまじない
            ret                 # 帰る
            .data               # データセクションの開始
     .buf
            .byte 20            # 20byte 分

16進数で表示する

レジスタの内容を16進数で表示する方法を考えよう。16進数は、'0'-'9' 'a'-'f'で表す。 

	0123456789abcdef
	    movl $30, %eax      # ascii code '0' を %eax にいれる
	    pushl %eax          # 出力をスタックにつむ
	    call putchar        # 出力ルーチンを呼び出す
	    addl $4,%esp        # スタックを元に戻す
で 0 が表示される。

16進数は、4bit 分を表している。 

    (11) %eax の 4bit を、一桁の16 進数に変換するルーチン puthex1 を作れ
    (12) %eax の 32bit を 4bit ずつ取り出して、
           16 進数に変換するルーチン puthex 1 を作れ
ヒント: 
    まず、Perl か Java で書いてみよう。
4bit を取り出すには、 
	andl  $15,%eax
とする。これに、48 を足す。 
 	addl  $48,%eax
これを putchar してやれば良い。

4bit ずらすには、 

     sar    arithmetic shift right
             sarl $4,%eax
を使う。(roll の方がいいかもね)

スタック

サブルーチン・コールがあるので、現代のCPUは、必ず特別なスタックを持っている。これを使って、一時変数やメソッド変数を実現するのが普通である。

Post-Increment 

	push %eax                 
	movl %eax,(%esp)
	incl %esp
Pre-Decrement 
	popl %eax
	decl %esp
	movl (%esp),%eax
 (13) %eax の内容を10進数で表示するルーチンを作ろう。
     まず、0-9 の値を数字で表示するルーチン putdec1 を作れ。
 (14) 順々に 10 で割ったあまりを計算して、逆順に10進数を
      表示するルーチン putdec_r を作れ。
 (15) スタックを使って、正しい順に表示するルーチンを作れ。

アセンブラの速度

  (16)
1 から 600000 までを足した結果を10進で表示するルーチンを作れ。

Perl で計算した場合と時間を比較せよ。(time command を使う)

メモリがない場合

どこかを指している場合

Segmentation Violation, Illigal Instruction とは..

文字列の表示

文字列は、 
    .section        .rodata
    string_data:
	    .string "hello world\n"
    .text
のようにデータとして用意する。

(18)これを表示するルーチン putstring を作れ。

メモリのコピー

(19)特定のメモリ領域をコピーするプログラムを作れ

(20)アドレスが重なっていても大丈夫なように修正せよ

提出

以上の問題を 

  Subject: Practice on Programming I   7/5
というサブジェクトで、18:30 までに、できるだけ、kono@ie.u-ryukyu.ac.jp までメールを出すこと。

宿題

残りは、 

  Subject: Report on Programming I   7/5
というサブジェクトで、kono@ie.u-ryukyu.ac.jp までメールを出すこと。

Shinji KONO / Fri Jul 13 16:09:29 2001