はじめに
ゲームボーイアドバンス（以下「GBA」）には、ARM7TDMIというCPUが使われています。
ですが、ARM7TDMIには除算命令が存在しません。
C言語で除算や剰余を書き、gccでコンパイルした時に除算や剰余はどうなるか
除算や剰余の部分は、コンパイルするとヘルパー関数の呼び出しに変化します。
どんなヘルパー関数が呼び出されるのかは符号の有無とgccの最適化レベルの設定、および書いたコードの状況によって変化します。
符号あり演算の場合
| 演算（C言語） | 最適化レベル（gcc） | あてがわれるヘルパー関数 |
|---|---|---|
a / bとa % bを近い場所で |
O1以上 |
__aeabi_idivmod |
a / b単体 |
||
a % b単体 |
||
a / bとa % bを近い場所で |
O0 |
|
a / b単体 |
__aeabi_idiv |
|
a % b単体 |
__aeabi_imod |
コンパイラが最適化する場合と除算と剰余を一度にする場面では、符号を考慮して除算と剰余を両方計算するヘルパー関数__aeabi_idivmodがあてがわれます。
符号なし演算の場合
| 演算（C言語） | 最適化レベル（gcc） | あてがわれるヘルパー関数 |
|---|---|---|
a / bとa % bを近い場所で |
O1以上 |
__aeabi_uidivmod |
a / b単体 |
||
a % b単体 |
||
a / bとa % bを近い場所で |
O0 |
|
a / b単体 |
__aeabi_uidiv |
|
a % b単体 |
__aeabi_uimod |
コンパイラが最適化する場合と除算と剰余を一度にする場面では、符号を考慮せずに除算と剰余を両方計算するヘルパー関数__aeabi_uidivmodがあてがわれます。
ヘルパー関数のいどころ
これらのヘルパー関数は、標準ライブラリにあります。つまり、一般的にはコンパイル時に配置場所を指定できません。つまり、ROM領域に配置されます。処理速度が心配ですね。
なので、GBAプログラミングの情報では「除算や剰余をしたい場合、C言語の除算（/）や剰余（%）の演算子を使わずに、システムROM（BIOS）のDiv（SWI 0x06）を使うべき」と触れられることが多々あります。
対策
それならば、それらのヘルパー関数を独自実装すればよいのです。
独自実装であれば、配置もこちら側で決められます。
独自実装
結果を返すのにr1レジスタも使われるため、アセンブラで実装します。
今回は筆算法で実装していきます。モードはARMモードです。
.text
.section .iwram,"ax",%progbits
.arm
.align 4
符号ありの__aeabi_idivmod
__aeabi_idivmodのシグネチャ
- 引数
-
r0：符号あり32ビット整数値の被除数（割られる数） -
r1：符号あり32ビット整数値の除数（割る数）
-
- 戻り値
-
r0：符号あり32ビット整数値の商（除算の結果） -
r1：符号あり32ビット整数値の剰余（余り）
-
システムROMのDiv（SWI 0x06）関数も、__aeabi_idivmodと同じシグネチャをしています。
また、GBATEKではr3に商の絶対値が返されるとの記載があるのですが、計算処理場の都合で偶然r3に符号処理前の商が格納されているのに過ぎません。
実装
アセンブラによる実装
一般的な__aeabi_idivmodやシステムROMのDiv（SWI 0x06）関数と異なり、ゼロ除算時には商を0、剰余を被除数として即座に処理を終了するようになっています。
（たとえば、システムROMのDiv関数はゼロ除算時に無限ループします）
@---------------------------------------------------------------------------------
.global Division
.type Division, %function
.global __aeabi_idiv
.type __aeabi_idiv, %function
.global __aeabi_idivmod
.type __aeabi_idivmod, %function
@---------------------------------------------------------------------------------
Division:
__aeabi_idiv:
__aeabi_idivmod:
@---------------------------------------------------------------------------------
cmp r1, #0
bne PreSignProcessStart @ ゼロ除算の判定
mov r1, r0 @ ゼロ除算時は被除数を剰余とする
mov r0, #0 @ ゼロ除算時は商を0とする
bx lr @ return
PreSignProcessStart:
ands r3, r1, #0x80000000 @ r3 = 除数の符号(bit31)
rsbmi r1, r1, #0 @ r1 = abs(r1)
eors ip, r3, r0, asr #32 @ ip = [bit31: 被除数と除数のどちらか片方が負の数か], [bit30-0: r0の符号]
rsbcs r0, r0, #0 @ r0 = abs(r0)
mov r2, r1 @ 臨時除数の初期化
PreDigitAscensionLoopStart:
cmp r2, r0, lsr #1
lslls r2, r2, #1 @ 臨時除数を2倍にする
blo PreDigitAscensionLoopStart @ 臨時除数が被除数以上になるまで繰り返す
DivisionMainLoopStart:
cmp r0, r2
adc r3, r3, r3 @ 商を2倍する 被除数の残りが臨時除数以上の場合はさらに1を加える
subhs r0, r0, r2 @ 被除数の残りが臨時除数以上の場合は被除数の残りから臨時除数を減算する
teq r1, r2
lsrne r2, r2, #1 @ 臨時除数が除数と等しくない(戻り切っていない場合)は臨時除数を半分にする
bne DivisionMainLoopStart @ 臨時除数が除数と等しくない(戻り切っていない場合)は繰り返す
mov r1, r0 @ r1 = r0(剰余)
mov r0, r3 @ r0 = r3(商)
lsls ip, ip, #1 @ CF = [被除数と除数のどちらか片方が負の値であるか]、 NF = [被除数が負の数であるか]
rsbcs r0, r0, #0 @ 被除数と除数のどちらか片方が負の値であればr0(商)の符号を反転する
rsbmi r1, r1, #0 @ 被除数が負の数であればr1(剰余)の符号を反転する
bx lr @ return
__aeabi_idivのシグネチャは、__aeabi_idivmodのシグネチャから戻り値のr1をなくした以外は__aeabi_idivmodと同じであるため、同じ処理をあてがってもよいです。
符号なしの__aeabi_uidivmod
__aeabi_uidivmodのシグネチャ
- 引数
-
r0：符号なし32ビット整数値の被除数（割られる数） -
r1：符号なし32ビット整数値の除数（割る数）
-
- 戻り値
-
r0：符号なし32ビット整数値の商（除算の結果） -
r1：符号なし32ビット整数値の剰余（余り）
-
実装
一般的な__aeabi_uidivmodとは異なり、ゼロ除算時には商を0、剰余を被除数として即座に処理を終了するようになっています。
アセンブラによる実装
@---------------------------------------------------------------------------------
.global UDivision
.type UDivision, %function
.global __aeabi_uidiv
.type __aeabi_uidiv, %function
.global __aeabi_uidivmod
.type __aeabi_uidivmod, %function
@---------------------------------------------------------------------------------
UDivision:
__aeabi_uidiv:
__aeabi_uidivmod:
@---------------------------------------------------------------------------------
mov r3, #0 @ 商の初期化(ゼロ除算時の商の設定も兼ねる)
movs r2, r1 @ 臨時除数の初期化(ゼロ除算の判定も兼ねる)
beq UDivisionReturn @ ゼロ除算の判定
UPreDigitAscensionLoopStart:
cmp r2, r0, lsr #1
lslls r2, r2, #1 @ 臨時除数を2倍にする
blo UPreDigitAscensionLoopStart @ 臨時除数が被除数以上になるまで繰り返す
UDivisionMainLoopStart:
cmp r0, r2
adc r3, r3, r3 @ 商を2倍する 被除数の残りが臨時除数以上の場合はさらに1を加える
subhs r0, r0, r2 @ 被除数の残りが臨時除数以上の場合は被除数の残りから臨時除数を減算する
teq r1, r2
lsrne r2, r2, #1 @ 臨時除数が除数と等しくない(戻り切っていない場合)は臨時除数を半分にする
bne UDivisionMainLoopStart @ 臨時除数が除数と等しくない(戻り切っていない場合)は繰り返す
UDivisionReturn:
mov r1, r0 @ r1 = r0(剰余)
mov r0, r3 @ r0 = r3(商)
bx lr @ return
__aeabi_uidivのシグネチャは、__aeabi_uidivmodのシグネチャから戻り値のr1をなくした以外は__aeabi_uidivmodと同じであるため、同じ処理をあてがってもよいです。
__aeabi_imodと__aeabi_uimod
最適化される設定であれば直接的に呼ばれることはありませんが、念のため実装します。
また、最適化される設定の時に必要なければ使われないようにするため、divmod系の処理とは別のファイル（翻訳単位）で書いた方がよいかもしれません。
シグネチャ
__aeabi_imodの場合はいずれも符号あり、__aeabi_uimodの場合はいずれも符号なしです。
- 引数
-
r0：32ビット整数値の被除数（割られる数） -
r1：32ビット整数値の除数（割る数）
-
- 戻り値
-
r0：32ビット整数値の剰余（余り）
-
アセンブラによる実装
.text
.section .iwram,"ax",%progbits
.arm
.align 4
@---------------------------------------------------------------------------------
.global Modulo
.type Modulo, %function
.global __aeabi_imod
.type __aeabi_imod, %function
@---------------------------------------------------------------------------------
Modulo:
__aeabi_imod:
@---------------------------------------------------------------------------------
stmfd sp!, {lr} @ push {lr}
bl Division @ 関数呼び出し: Division(r0, r1);
mov r0, r1 @ r0 = r1(剰余)
ldmfd sp!, {lr} @ pop {lr}
bx lr @ return
@---------------------------------------------------------------------------------
.global UModulo
.type UModulo, %function
.global __aeabi_uimod
.type __aeabi_uimod, %function
@---------------------------------------------------------------------------------
UModulo:
__aeabi_uimod:
@---------------------------------------------------------------------------------
stmfd sp!, {lr} @ push {lr}
bl UDivision @ 関数呼び出し: UDivision(r0, r1);
mov r0, r1 @ r0 = r1(剰余)
ldmfd sp!, {lr} @ pop {lr}
bx lr @ return
やっていることは単純で、先ほどのdivmod系の処理を実行してr0にr1を代入するだけです。
使用法
以上のコード（本記事ではDivision.sとDivisionModulo.s）をコンパイルされる場所に配置し、C言語でa / bやa % bといった記述をすると、コンパイル時にDivision.s（最適化設定と状況によりDivisionModulo.s）内のヘルパー関数を呼び出すようにコンパイルされます。
また、明示的に使用したい場合はDivision(s32, s32)、UDivision(u32, u32)、Modulo(s32, s32)、UModulo(u32, u32)からも使うことができます。
実験
このようなC言語のソースコードを書いて、本当に今回実装したアセンブラの処理が呼び出されるのかを確認してみます。
void SDM(s32 a, s32 b)
{
s32 div = a / b;
s32 mod = a % b;
// divやmodの値を使う何らかの処理
}
// Thumbモードからの呼び出しのテストも兼ねる
THUMB_FUNC void UDM(u32 a, u32 b)
{
u32 div = a / b;
u32 mod = a % b;
// divやmodの値を使う何らかの処理
}
今回の検証ではこのC言語のコードはこのようにマッピングされました。
0x08000450 SDM
0x08000498 UDM
符号あり、ARMモードの場合の処理を辿る
逆アセンブラで確認していきます。重要な部分のみ抜粋します。
08000460 bl $0800aa88
何やら0x0800aa88の関数を呼んでいますね。
マップファイルで何が割り当てられているのかを確認すると、ちょうど0x0800aa88に割り当てられた関数はなく、
0x0800a930 0x168 linker stubs
の範囲内のアドレスであることがわかりました。
では、0x0800aa88には何があるかというと、
0800aa88 ldr pc, =0x03000520
という処理がありました。モード切り替えを伴わないロングジャンプ（b命令やbl命令で届かない範囲へのジャンプ手法）ですね。0x03000520にジャンプするようです。
では、0x03000520に何があるかというと、
0x03000520 __aeabi_idivmod
0x03000520 Division
0x03000520 __aeabi_idiv
先ほど実装した__aeabi_idivmodがありました。/演算子や%演算子で記述したコードから呼び出せています。
符号なし、Thumbモードの場合の処理を辿る
同じく逆アセンブラで確認していきます。重要な部分のみ抜粋します。
080004a0 bl $0800aa00
こちらでは0x0800aa00の関数を呼んでいますね。符号ありの時と同様にlinker stubsの範囲内です。
では、0x0800aa00には何があるかというと、
0800aa00 bx pc
という処理がありました。モードを切り替えてジャンプする命令ですね。2命令先（0x0800aa04）にジャンプして、ARMモードにするようです。
では、0x0800aa04には何があるかというと、
0800aa04 ldr pc, =0x03000584
という処理がありました。符号ありの時にも見た、モード切り替えを伴わないロングジャンプですね。0x03000584にジャンプするようです。
では、0x03000584に何があるかというと、
0x03000584 __aeabi_uidivmod
0x03000584 UDivision
0x03000584 __aeabi_uidiv
先ほど実装した__aeabi_uidivmodがありました。Thumbモードや符号なしの場合でも/演算子や%演算子で記述したコードから呼び出せています。
実行までにかかるコスト
引数の設定を除くと、ARMモードであれば2命令、Thumbモードであれば3命令で呼び出せます。
また、IWRAMに配置されるコードであればロングジャンプの必要がないのでもしかしたら1命令減るかもしれません。
おわりに
独自実装した分システムROMのDiv関数を呼ぶ方法と比べると、いくらかはコードサイズが増えてしまったのですが、この程度の増加であれば大体の場合においては問題ないかと思われます。
その代わり、
- 書きなれた
a / bやa % bで記述できる -
符号なしの除算や剰余もできる
（システムROMのDiv関数は符号ありの演算処理です） -
呼び出しにかかる手順が削減される
（システム関数の呼び出しは、ユーザーコードのswi命令を含めると1回あたり20命令くらいかかります1）
といったメリットを享受できます。費用対効果で見ればかなり得になっているかと思われます。