「128バイト以上で書いてて、これではジャンプできません。」の問題を推察する
はじめに
先日ツイッターで見かけたつぶやき、
@hatakenjiro 軽く流して欲しいとは思うけど、元がどんな問題だったのかあまり想像できない。
— 重巡洋艦 キノガッサ (@TKinugasa) June 13, 2020
まさかアセンブリで関数書かせるような問題だったのか? そりゃ難しかろう。 pic.twitter.com/dY3fT56Z8Z
折角なのでどういう問題だったか推察してみることとする。
前提
件の画像は小学館発行 週刊少年サンデー 2020年 27・28号の 210ページ、畑健二郎作『トニカクカワイイ』第113話「月と星の数式」からの一コマである。女子校でプログラミングを教えるボランティア講師となった主人公が生徒達の理解度が壊滅的であることに気付き、それまで教えていた先生方にテストを行った結果の場面らしい。テストの内容は他のページのコマも含めて情報を総合すると
- 基本的な内容である
- 一見簡単そう
- 128バイト以上で書くとジャンプできないひっかけがある
ということらしい。
推察してみた
問3 枠内を記入して FizzBuzz 問題を完成させなさい。動作環境は MS-DOS、動作プロセッサは 8086 とする。出力には MS-DOS のファンクションコールを使用し、外部サブルーチンの使用は認めない。
.8086 ; 8086 の命令のみ有効
assume cs:cseg ; CS に cseg を想定
cseg segment ; cseg 開始
org 0100h ; .COM 形式開始オフセット
start: xor ax, ax ; AX をループ変数とし、先ずクリア
loop0: inc ax ; ループ変数に 1 足して
cmp ax, 100 ; 100 と比較して
ja return ; 大きければ終了処理へ移行
+-----------------------------------------------------------------------+
| |
| |
| |
| |
| |
| |
| |
+-----------------------------------------------------------------------+
return: ret ; プログラムを終了しコマンドプロンプトへ復帰
cseg ends ; cseg 終了
end start ; 開始番地
解説
先の内容と推察した理由は以下の通りである。
- 基本的な内容である
基本的な内容ということで、プログラムの実行に複雑な機構を必要としない、プロセッサに直接命令を与え実行するアセンブラによるプログラムであることは容易に想像できた。FizzBuzz 問題もプログラミングの基礎的な力を試すには良く取り上げられるものなのでまあ妥当なところと思われる。
- 一見簡単そう
プログラムの大枠を予め提示し穴埋め問題とすることで一見簡単そうな印象を与えることは普通に可能だろう。
- 128バイト以上で書くとジャンプできないひっかけがある
80386 以降、分岐命令のディスプレースメントに 16ビットのオフセットが指定できることは自明であり、いまどきのプロセッサに慣れた人であれば 8ビットのオフセットしか指定できなかった 16ビット時代のことはもはや念頭にない可能性は高い。
先の問題の中にある JA 命令は 8086 では 16進数で77 XXという 2バイトの命令となり、2バイト目のXXは分岐先を表すオフセットとなる。分岐先は問題中で既にreturnというラベルが指定されており、そのラベルは回答を記入する枠の先にあるので分岐先を表すオフセットの最大値で枠内に書ける命令の最大バイト数が決まることとなる。x86 アーキテクチャでは命令実行中の命令ポインタの値は実行中の命令の次の命令を指すこととなっており、条件分岐命令のオフセットは命令ポインタの値への相対値として指定する。条件分岐命令のオフセットが 0 だった場合、条件成立時には条件分岐命令の次の命令に分岐することとなる。その場合、枠内に書ける命令は 0 バイトとなる。条件分岐命令のオフセットは 2の補数表現となるため、最大の値は 10進数で 127 となる。したがって、枠内に書ける命令は 127 バイトが上限となる。
回答例
先の推察に対し回答を考えてみた。
; 3 で割り切れて 5 で割り切れれば 'FizzBuzz' を出力する
isfizzbuzz: mov dx, 0 ; DX をクリアし
mov cx, 3 ; CX に除数 3 をセット。
push ax ; AX(ループ変数)をとりあえず保存
div cx ; DX:AX ÷ CX ⇒ AX 余りDX
pop ax ; AX(ループ変数)を復帰
cmp dx, 0 ; DX(余り) と 0 を比較
jnz isbuzz ; 余りが 0 じゃなければ 3 で割り切れなかったということで「5 で割り切れれば 'Buzz' を出力する」へ移行
mov dx, 0 ; DX をクリアし
mov cx, 5 ; CX に除数 5 をセット。
push ax ; AX(ループ変数)をとりあえず保存
div cx ; DX:AX ÷ CX ⇒ AX 余りDX
pop ax ; AX(ループ変数)を復帰
cmp dx, 0 ; DX(余り) と 0 を比較
jnz isfizz ; 余りが 0 じゃなければ 5 で割り切れなかったということで「3 で割り切れれば 'Fizz' を出力する」へ移行
mov dx, offset fizzbuzz ; 'FizzBuzz' 文字列のオフセットを DX に設定し
jmp putstr ; 文字列出力へ移行
fizzbuzz: db 'FizzBuzz$'
; 3 で割り切れれば 'Fizz' を出力する
isfizz: mov dx, 0 ; DX をクリアし
mov cx, 3 ; CX に除数 3 をセット。
push ax ; AX(ループ変数)をとりあえず保存
div cx ; DX:AX ÷ CX ⇒ AX 余りDX
pop ax ; AX(ループ変数)を復帰
cmp dx, 0 ; DX(余り) と 0 を比較
jnz isbuzz ; 余りが 0 じゃなければ 3 で割り切れなかったということで「5 で割り切れれば 'Buzz' を出力する」へ移行
mov dx, offset fizz ; 'Fizz' 文字列のオフセットを DX に設定し
jmp putstr ; 文字列出力へ移行
fizz: db 'Fizz$'
; 5 で割り切れれば 'Buzz' を出力する
isbuzz: mov dx, 0 ; DX をクリアし
mov cx, 5 ; CX に除数 5 をセット。
push ax ; AX(ループ変数)をとりあえず保存
div cx ; DX:AX ÷ CX ⇒ AX 余りDX
pop ax ; AX(ループ変数)を復帰
cmp dx, 0 ; DX(余り) と 0 を比較
jnz putnum ; 余りが 0 じゃなければ 5 で割り切れなかったということで「AX の値を 10進出力する」へ移行
mov dx, offset buzz ; 'Buzz' 文字列のオフセットを DX に設定し
jmp putstr ; 文字列出力へ移行
buzz: db 'Buzz$'
; AX の値を 10進出力する
putnum: push ax ; AX(ループ変数)を保存
mov bx, offset numbuf+5 ; BX へ 10進数展開バッファ+1 のアドレスを設定
putnum0: mov dx, 0 ; DX をクリアし
mov cx, 10 ; CX に除数 10 をセット。
div cx ; DX:AX ÷ CX ⇒ AX 余りDX
add dl, '0' ; 余り(0～9)が格納されてる DL に '0' を足し '0'～'9' へ変換
dec bx ; 10進数展開バッファのアドレスが格納されてる BX へ
mov [bx], dl ; 下の桁から格納する
cmp ax, 0 ; AX の値と 0 を比較し
jnz putnum0 ; 0 でなければ更に上の桁について処理を継続する。
pop ax ; AX(ループ変数)を復帰
mov dx, bx ; 最上位の桁の数字が格納されている BX の値を DX へ転送
jmp putstr ; 文字列出力へ移行
numbuf: db '00000$'
; DX に設定された文字列を出力し行頭復帰と改行を出力しメーンループ繰り返し
putstr: push ax ; AX(ループ変数)を保存
mov ah, 9 ; DX に設定されている文字列を
int 21h ; MS-DOS ファンクションコールで出力し
putcrlf: mov dx, offset crlf ; 行頭復帰と改行を出力する。
mov ah, 9 ;
int 21h ;
pop ax ; AX(ループ変数)を復帰
jmp loop0 ; メーンループ繰り返し
crlf: db 13, 10, '$'
コードサイズについて特に注意することなくお手軽に書いた場合を想定している。以上の回答を先の問題の枠内に記入しビルドすると、
C:\HOME\FUJITA\FIZZBUZZ>make
MAKE Version 3.0 Copyright (c) 1987, 1990 Borland International
Available memory 657015 bytes
tasm fizzbuzz,fizzbuzz,fizzbuzz
Turbo Assembler Version 2.0 Copyright (c) 1988, 1990 Borland International
Assembling file: fizzbuzz.ASM
**Error** fizzbuzz.ASM(9) Relative jump out of range by 0018h bytes
Error messages: 1
Warning messages: None
Passes: 1
Remaining memory: 481k
** error 1 ** deleting fizzbuzz.obj
C:\HOME\FUJITA\FIZZBUZZ>
9行目にあった JA 命令で相対ジャンプができる範囲を 18hバイト超えたというエラーとなってしまった。作中で言われてた「ひっかけ」とはこういうことではなかろうか。
もうひとつの回答として、コードサイズに注意を払った例を考えてみた。
mov bl, 0 ; 「文字列出力を行った」フラグをクリア
isfizz: mov cx, 3 ; AX の値が 3で割り切れたら
mov dx, offset fizz ; 'Fizz' を出力し
call putstr ;「文字列出力を行った」フラグをセット
isbuzz: mov cx, 5 ; AX の値が 5で割り切れたら
mov dx, offset buzz ; 'Buzz' を出力し
call putstr ;「文字列出力を行った」フラグをセット
isnum: test bl, bl ; 「文字列出力を行った」フラグがクリア
jnz putcrlf ; されてるままであれば
call putnum ; AX の値を 10進出力する
putcrlf: mov cx, 1 ; AX の値が 1で割り切れたら
mov dx, offset crlf ; (※常に割り切れる)
call putstr ; 行頭復帰と改行を出力する
jmp loop0 ; メーンループ繰り返し
fizz: db 'Fizz$'
buzz: db 'Buzz$'
crlf: db 13, 10, '$'
; AX の値が CX の値で割り切れたら DX で指標される文字列を
; 標準出力へ出力するサブルーチン
putstr: push ax ; AX(ループ変数)の値は保存
push dx ; DX の値をとりあえず保存
xor dx, dx ; DX をクリアし
div cx ; DX:AX ÷ CX ⇒ AX 余りDX
test dx, dx ; 余りがなかった?(割り切れた?)
pop dx ; DX の値を復帰(文字列のアドレス)
jnz putstr1 ; 余りがあれば(割り切れなければ)文字列出力しない
mov ah, 9 ; MS-DOS のファンクションコールで文字列出力
int 21h ;
mov bl, 1 ; 「文字列出力を行った」フラグをセット
putstr1: pop ax ; AX(ループ変数)の値を復帰
ret ; 呼び出し元へ戻る
; AX の値を標準出力へ 10進出力するサブルーチン
putnum: push ax ; AX(ループ変数)の値は保存
xor dx, dx ; DX をクリアし
mov cx, 10 ; CX に除数 10 をセットし
div cx ; DX:AX ÷ CX ⇒ AX 余りDX(0～9)
test ax, ax ; AX の値が
jz putnum1 ; 0 でなければ
push dx ; DX(出力すべき0～9)の値をとりあえず保存
call putnum ; putnum を再帰呼出しする(上の桁を出力する)
pop dx ; DX(出力すべき0～9)の値を復帰
putnum1: mov ah, 2 ; 先の割った余り(0～9)が DX の下位バイト DL に
add dl, '0' ; 格納されてるので '0' を足して '0'～'9'にして
int 21h ; MS-DOS のファンクションコールで出力する。
pop ax ; AX(ループ変数)の値を復帰
ret ; 呼び出し元へ戻る
これを先の回答例同様にビルドしてみると
C:\HOME\FUJITA\FIZZBUZZ>make
MAKE Version 3.0 Copyright (c) 1987, 1990 Borland International
Available memory 657104 bytes
tasm fizzbuzz,fizzbuzz,fizzbuzz
Turbo Assembler Version 2.0 Copyright (c) 1988, 1990 Borland International
Assembling file: fizzbuzz.ASM
Error messages: None
Warning messages: None
Passes: 1
Remaining memory: 481k
tlink /t fizzbuzz
Turbo Link Version 3.01 Copyright (c) 1987, 1990 Borland International
C:\HOME\FUJITA\FIZZBUZZ>dir fizzbuzz.*
Volume in drive C is WINDOWS
Directory of C:\HOME\FUJITA\FIZZBUZZ
FIZZBUZZ ASM 1671 6-24-20 8:30p
FIZZBUZZ COM 105 6-24-20 8:31p
FIZZBUZZ LST 3526 6-24-20 8:31p
FIZZBUZZ MAP 99 6-24-20 8:31p
FIZZBUZZ OBJ 255 6-24-20 8:31p
5 File(s) 168431360 bytes free
C:\HOME\FUJITA\FIZZBUZZ>fizzbuzz
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
～ 略 ～
FizzBuzz
91
92
Fizz
94
Buzz
Fizz
97
98
Fizz
Buzz
C:\HOME\FUJITA\FIZZBUZZ>
ビルドは成功し、プログラムの実行確認も取れた。
アセンブルリストを確認すると
$ cat fizzbuzz0.LST
Turbo Assembler Version 2.0 20/06/26 02:42:41 Page 1
fizzbuzz0.ASM
1 .8086 ; 8086 の命令のみ有効
2 assume cs:cseg ; CS に cseg を想定
3 0000 cseg segment ; cseg 開始
4
5 org 0100h ; .COM 形式開始オフセット
6 0100 33 C0 start: xor ax, ax ; AX をループ変数とし、先ずクリア
7 0102 40 loop0: inc ax ; ループ変数に 1 足して
8 0103 3D 0064 cmp ax, 100 ; 100 と比較して
9 0106 77 60 ja return ; 大きければ終了処理へ移行
JA 命令のオフセットは余裕ある値に収まっていることが確認できた。
おわりに
おわりです。
Author And Source
この問題について(「128バイト以上で書いてて、これではジャンプできません。」の問題を推察する), 我々は、より多くの情報をここで見つけました https://qiita.com/fujitanozomu/items/1ed6d6e7565dd97c2985著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .