アセンブリ言語でバブルソートを実装してみる
はじめに
以前、「実際に手を動かして学ぶアセンブリ入門」という記事を書きました。
前回は指定した文字列を出力するだけの簡単な例でした。今回は、少し踏み込んでアセンブリ言語でバブルソートを実装してみようと思います。高水準言語であれば数行で済むソート処理も、アセンブリでは配列アクセスやループの仕組みを直接書く必要があります。こうした低レベルの手続きを追うことで、CPUやメモリ、そしてOSのシステムコールとのやり取りをより深く理解できるのがアセンブリの学習上の大きな利点です。
実行環境と準備
前回に引き続き、godboltを使用します。(詳細については、前回の記事の実行環境と準備の箇所を参考にしてみてください！)
解説
以下コード全体になります。
global _start
section .data
array dd 3, 1, 6, 2
n equ 4
section .bss
int_buffer resb 12
section .text
_start:
mov ecx, n
outer_loop:
dec ecx
jz sorting_done
mov esi, 0
inner_loop:
mov eax, [array + esi*4]
mov ebx, [array + esi*4 + 4]
cmp eax, ebx
jle no_swap
mov [array + esi*4], ebx
mov [array + esi*4 + 4], eax
no_swap:
inc esi
cmp esi, ecx
jl inner_loop
jmp outer_loop
sorting_done:
mov ecx, n
mov esi, array
print_loop:
mov eax, [esi]
call print_int
add esi, 4
loop print_loop
mov eax, 1
xor ebx, ebx
int 0x80
print_int:
push ebp
mov ebp, esp
push ebx
push ecx
push edx
push esi
push edi
jmp .convert_digits
.convert_digits:
lea edi, [int_buffer + 11]
mov byte [edi], 0
dec edi
cmp eax, 0
jne .convert_loop
mov byte [edi], '0'
jmp .print_number
.convert_loop:
.convert_digit_loop:
xor edx, edx
mov ebx, 10
div ebx
add dl, '0'
mov [edi], dl
dec edi
cmp eax, 0
jne .convert_digit_loop
.print_number:
lea ecx, [edi+1]
lea ebx, [int_buffer + 11]
sub ebx, ecx
mov eax, 4
mov edx, ebx
mov ebx, 1
int 0x80
pop edi
pop esi
pop edx
pop ecx
pop ebx
pop ebp
ret
出力結果は以下になります。
3, 1, 6, 2として事前に定義した並び順が、1, 2, 3, 6に昇順で並び替えられています。
これからstep by stepで説明していきます。
section .data
array dd 3, 1, 6, 2
n equ 4
こちらは、今回ソートしたい数値を４つ指定しています。
section .bss
int_buffer resb 12
この部分は、整数を文字列に変換する際に一時的に使用するメモリ領域を確保しています。
section .bss: .bss セクションは「未初期化データ」を格納する領域です。ここに定義された変数は、プログラム実行時に必要なメモリ容量だけ確保されますが、初期値は与えられません。
int_bufferは、このバッファに付けられたラベル名になります。後にこのラベル名を使用して先頭アドレスにアクセスします。resbは "reserve byte"の略で、指定したバイト数分の未初期化の領域を確保するディレクティブになります(参考)。12は、バッファに予約するバイト数です。これは「最大10桁＋符号＋終端用の合計12バイト分」を確保しています(今回は負の値を扱っていないので符号分は必須ではないです)。
section .text
_start:
mov ecx, n
outer_loop:
dec ecx
jz sorting_done
mov esi, 0
inner_loop:
mov eax, [array + esi*4]
mov ebx, [array + esi*4 + 4]
cmp eax, ebx
jle no_swap
mov [array + esi*4], ebx
mov [array + esi*4 + 4], eax
これからバブルソート部分を中心に、詳しく解説していきます。その前に、このプログラムで使用しているレジスタの主な役割を簡単に整理しておきましょう。
| レジスタ | 用途 |
|---|---|
| EAX | 比較用の値(配列の要素)をロードする。 割り算の被除数としても使用。 |
| EBX | 隣接要素を読み込んだり、一時的な値の保管に使用。 |
| ECX | ループカウンタとして使用。(外側・内側双方でカウンタとして) |
| EDX | 割り算の余りが格納されるレジスタ。 |
| ESI | 配列のインデックスとして使用。(esi×4で要素アクセス) |
| EDI | 文字列変換時のバッファ先頭/末尾管理に使用。 |
これで各レジスタが何をしているかイメージしやすくなると思います。それではコードを順に見ていきます。
mov ecx, n
ここでデータセクションで定義した定数のn(ここでは、配列の要素数)を汎用レジスタであるecxにロードします。これがあることで、外側ループのカウンタとして使用され、最終的にはn-1回の繰り返し処理を行うために使います。
outer_loop:
dec ecx
jz sorting_done
mov esi, 0
外側ループの開始位置を示すラベルになります。dec ecxで値を1減少させます(decはdecreaseの略です)。バブルソートでは、配列の要素数がnの場合、n-1回の繰り返しで十分なため、最初にecxにnをセットし、ループ開始時に1減らすことでn-1回のループになります(少し回りくどいですが...)。
jz sorting_doneはecxがゼロになった場合(すなわち、外側ループの回数が終わった場合)、sorting_doneラベルへジャンプしてソート処理を終了します。
mov esi, 0は、内側ループのインデックスとして使うレジスタesiをゼロに初期化し、用途としては配列内の現在の要素の位置を示すために使用します。
このように、esi*4は配列のインデックスをバイト単位のオフセットに変換するための計算です。もし要素のサイズが異なれば、乗算する値も変わります。この計算を行うことで、アセンブリでは配列内の任意の要素に正確にアクセスすることが可能となります。
inner_loop:
mov eax, [array + esi*4]
mov ebx, [array + esi*4 + 4]
cmp eax, ebx
jle no_swap
mov [array + esi*4], ebx
mov [array + esi*4 + 4], eax
要素の比較をしてソートをする処理がこちらになります。
mov eax, [array + esi*4]
NASMでの配列は、メモリ上に連続して並んだ領域として定義されます。今回のコードでは、array dd 3, 1, 6, 2として配列を定義していますが、ddはすなわち4バイトのデータを定義するという意味です。つまり、配列の各要素は4バイトのメモリを占めています。arrayの中で、esi番目の要素(各要素は4バイトなので、esi*4オフセット)を読み込み、レジスタeaxに格納します。
なぜesi*4なのかというと、各整数は4バイトであるため、配列の0番目の要素はアドレスarrayに格納されます。 1番目の要素は、最初の4バイトを飛ばして、その次の4バイトに格納されるので、アドレスはarray + 4になります。2番目はarray + 8、3番目はarray + 12となります。
cmp eax, ebx
レジスタeaxとebxの値を比較します。
jle no_swap
eaxがebx以下（jle...jump if less or equal）なら、交換せずにno_swapラベルへジャンプします。要素がすでに昇順の場合は交換の必要がないため、次の比較に進みます。
mov [array + esi*4], ebx
要素の入れ替え処理の部分です。現在の位置esiに、次の要素(ebxの値)を格納します。これで2つの要素の順序を入れ替えるための第一ステップが完了します。
mov [array + esi*4 + 4], eax
次の位置esi+1に、現在の要素(eaxの値)を格納します。こうすることで交換が完了してペア内で値の順序が正しくなります。
no_swap:
inc esi
cmp esi, ecx
jl inner_loop
jmp outer_loop
この処理は、要素の交換が不要だった場合に呼ばれます。
inc esiは、現在のペアの比較が終わり、次のペアに進むために、現在の内側ループのインデックスを1増やします。
cmp esi, ecxは、内側ループのインデックスesiと、外側ループで設定した残りの比較回数ecxを比較します。これは、既に決定した部分を再度ソートしないための処理になります。
jl inner_loopは、もしesiがecxより小さければ、再び内側ループinner_loopにジャンプして次のペアの比較を行います。
jmp outer_loopは、内側ループが終わった場合、つまりesiがecxと同じか大きくなった場合、外側ループに戻って新たな走査を開始します。
sorting_done:
mov ecx, n
mov esi, array
これは、ソート処理が完了したときにジャンプしてくるラベルです。ここから、ソート済みの配列の各要素を出力する処理を行います。
mov ecx, nは、出力する要素数として、定数n(配列の要素数)をレジスタecxにセットします。
この値をカウンタとして、全要素を順に出力するループを制御します。
mov esi, arrayは、esiを使って配列内の各要素へ順にアクセスします。
print_loop:
mov eax, [esi]
call print_int
add esi, 4
loop print_loop
mov eax, 1
xor ebx, ebx
int 0x80
次にループ内の処理を追っていきます。
mov eax, [esi]は、現在の要素(4バイト分)をメモリから読み込み、eaxにセットします。
call print_intは、eaxにある整数を文字列に変換して出力するサブルーチンprint_intを呼び出します(print_intについては、後述します)。
add esi, 4は、次の配列要素へ進むため、アドレスを4バイト分(1要素分)進めます。
loop print_loopは、ecxの値を1減らし、もしまだ0でなければprint_loopラベルにジャンプします。これにより、配列の全要素を順に出力します。
mov eax, 1とxor ebx, ebxは、これらは sys_exit システムコール(終了)の準備で、int 0x80は、システムコールを実行して、プログラムを終了します。
print_int:
push ebp
mov ebp, esp
push ebx
push ecx
push edx
push esi
push edi
jmp .convert_digits
先ほど飛ばしたサブルーチンであるprint_intについて見ていきます。このサブルーチンは、レジスタeaxに格納された整数を ASCII文字列に変換し、標準出力へ表示する機能を持っています。
push ebpは、現在のベースポインタ(関数呼び出し前のフレームポインタ)をスタックに保存します。
mov ebp, espは、スタックポインタであるespの値をベースポインタebpに移し、新しいスタックフレームの開始を示します。これを行う理由としては、関数終了後に元の状態に戻せるようにするためです。
push ebx、push ecx、push edx、push esi、push edi...これらは、呼び出し側が保存すべきレジスタをスタックに保存しています。ebx、ecx、edx、esi、ediは、このサブルーチン内で自由に使いますが、呼び出し元がこれらのレジスタの値に依存している可能性があるため、必ず退避しておく必要があります。
上記簡潔にやっていることとしては、以下です。
- スタックフレームの確立
- 呼び出し元のレジスタの値の保存
jmp .convert_digitsは、無条件で.convert_digitsラベルにジャンプします。
.convert_digits:
lea edi, [int_buffer + 11]
mov byte [edi], 0
dec edi
cmp eax, 0
jne .convert_loop
mov byte [edi], '0'
jmp .print_number
lea edi, [int_buffer + 11]について、int_bufferは12バイトのバッファです。この命令は、バッファの最後のバイトのアドレス(int_bufferから11バイト目)をediにロードします。これを行う理由について、数字の変換では、最下位の桁から順に計算されるため、桁が逆順に生成されます。後で正しい順序で出力するため、バッファの末尾から数字を詰めていく準備をここでしています。
mov byte [edi], 0は、ediが指しているバッファの最後の位置に0を格納します。ここで文字列が終わるという目印になります。見やすくするためにしているので必須ではありません。
dec ediは、シンプルにediの値を1減らすだけの処理です。
cmp eax, 0は、変換する数が0かどうかを判断するために使用します。数字が0の場合、変換ループに入る必要はありません。
jne .convert_loopは、EAXが0でなければ.convert_loopラベルにジャンプします。
mov byte [edi], '0'は、もしEAXの値が0だった場合(上記の比較で等しいなら)、現在の ediが指す位置に文字0を書き込みます。
jmp .print_numberは、数字が0の場合も、変換ループをスキップしてそのまま出力処理へジャンプします。
.convert_loop:
.convert_digit_loop:
xor edx, edx
mov ebx, 10
div ebx
add dl, '0'
mov [edi], dl
dec edi
cmp eax, 0
jne .convert_digit_loop
このコードは、EAXに入った整数を10で割っていき、余りとして得られる各桁（0～9）をASCII文字に変換し、下位桁から順にバッファに逆順で保存することで、整数を文字列に変換しようとしています。
10で割っていく理由して、例えば1234の場合、10で割ると余り4(最下位桁)が得られ、次に123を10で割って余り3、その後余り2、1と取り出すことで、各桁を抽出し、それぞれを文字に変換しています。
.print_number:
lea ecx, [edi+1]
lea ebx, [int_buffer + 11]
sub ebx, ecx
mov eax, 4
mov edx, ebx
mov ebx, 1
int 0x80
pop edi
pop esi
pop edx
pop ecx
pop ebx
pop ebp
ret
上記のコードをさらに分割してみていきます。
lea ecx, [edi+1]
lea ebx, [int_buffer + 11]
sub ebx, ecx
文字列の先頭アドレスと長さの計算を行います。lea ecx, [edi+1]について、EDIは数字を書き込んだ最後の位置(逆順に書いたため、実際の文字列の直前)を指しています。ここでedi+1により、変換後の数字文字列の先頭アドレスをECXに取得します。
lea ebx, [int_buffer + 11]は、バッファの末尾(ヌル文字が置かれた位置)のアドレスをEBXに取得します。
sub ebx, ecxはバッファの末尾と数字文字列の先頭アドレスの差を計算することで、出力すべき文字列の長さをEBXに求めます。
mov eax, 4
mov edx, ebx
mov ebx, 1
int 0x80
こちらは、sys_writeを用いた出力になります。
mov eax, 4はLinuxのシステムコールsys_writeの番号をEAXにセットします。
mov edx, ebxは、先ほど計算した文字列の長さを、sys_writeの第3引数としてEDXにセットします。
mov ebx, 1は、出力先を標準出力(ファイルディスクリプタ 1)に設定します。
int 0x80は、システムコールを呼び出し、文字列を標準出力に出力します。
pop edi
pop esi
pop edx
pop ecx
pop ebx
pop ebp
ret
サブルーチンの終了処理になります。これらのpop命令は、サブルーチンの冒頭で pushしたレジスタを元の状態に復元します。最後にretで、print_intサブルーチンから呼び出し元に戻ります。
まとめ
アセンブリ言語でバブルソートを組むと、コード量が増えてレジスタの管理(初めはどのようなレジスタがあるのかなど対応表を見ながら学んでいます)などの細部まで意識する必要があります。その分、高水準言語では抽象化されているメモリ操作やシステムコールの仕組みを直接扱うため、より低レベルな観点からコンピュータの動きを理解しやすいのが魅力です。バブルソートは計算量が大きく実用には不向きですが、単純なループ構造ゆえ学習教材としては最適だと感じました。慣れていない言語で知らない概念や知識が出てくるので、自分の場合、実装するまでに非常に時間を要します...。次は別のアルゴリズムをアセンブリで書いてみるなどしてみたいと思います。
参考
Discussion