はじめに

ゲームボーイアドバンス（以下「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モードです。

Division.s

    .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関数はゼロ除算時に無限ループします）

Division.s

@---------------------------------------------------------------------------------
    .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、剰余を被除数として即座に処理を終了するようになっています。

アセンブラによる実装

Division.s

@---------------------------------------------------------------------------------
    .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ビット整数値の剰余（余り）

アセンブラによる実装

DivisionModulo.s

    .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言語のコードはこのようにマッピングされました。

ProjectName.map

0x08000450                SDM
0x08000498                UDM

符号あり、ARMモードの場合の処理を辿る

逆アセンブラで確認していきます。重要な部分のみ抜粋します。

08000460    bl      $0800aa88

何やら0x0800aa88の関数を呼んでいますね。
マップファイルで何が割り当てられているのかを確認すると、ちょうど0x0800aa88に割り当てられた関数はなく、

ProjectName.map

0x0800a930                0x168 linker stubs

の範囲内のアドレスであることがわかりました。
では、0x0800aa88には何があるかというと、

0800aa88    ldr     pc, =0x03000520

という処理がありました。モード切り替えを伴わないロングジャンプ（b命令やbl命令で届かない範囲へのジャンプ手法）ですね。0x03000520にジャンプするようです。
では、0x03000520に何があるかというと、

ProjectName.map

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に何があるかというと、

ProjectName.map

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命令くらいかかります¹）

といったメリットを享受できます。費用対効果で見ればかなり得になっているかと思われます。

参考記事
（この記事では要点のみの抜粋ですが、重要な処理だけでも8命令あります　残りの12命令はソフトウェア割込みを処理するための命令です） ↩