bamboo’s blog

Bambooの気まぐれブログ

CTRPFで学ぶソートアルゴリズム

はじめに

　CTRPFと呼ばれるNintendo 3DS向けのプラグインシステムがある。今回はこれを用いて、ソートアルゴリズムについて学ぶ。

ソートアルゴリズム

　データの集合を一定の規則に従って並べることを「ソート」と言う。このソートを行う手順や計算手法のことを「ソートアルゴリズム」という。今回はCTRPFを用いて、ソートアルゴリズムの一種である「バブルソート」を実装する。

バブルソートとは

　バブルソートとは、隣り合う要素の大小を比較しながら整列するアルゴリズムのこと。例えば4, 3, 2の順に並んでいる要素を昇順ソートすると、以下のような処理になる。

1周目

　最初の２つを比較する。３より４の方が大きいため、３と４を交換する。

|4, 3|, 2
  ↓
|3, 4|, 2

　１つずらして比較。４と２では４の方が大きいため、２と４を交換する。

3, |4, 2|
     ↓
3, |2, 4|

　これで最大値を一番右に持ってくることができた。1周目終わり。

2周目

　２周目では一番右に最大値があることが既に分かっているため、比較回数は1回でよい。３と２を比較して、３の方が大きいため交換。

|3, 2|, 4
  ↓
|2, 3|, 4

　これで昇順に並べ替えることができた。

アルゴリズム

　上記の例では分かりにくかったかもしれないが、このアルゴリズムについて、要素数をnとすると以下のようなことが言える。

  • 比較を繰り返す周の数はn-1周
  • m周目に行う比較回数はn-m回

実装

　さて、ここからが本題。上記のアルゴリズムを以下の条件を元に実装する。

  • 要素のサイズは8bit
  • r0は残りの周数
  • r1は残りの比較回数
  • r2は1番目の比較対象
  • r3は2番目の比較対象
  • r10は要素のポインタ（CTRPFの場合共有メモリのポインタ）
  • 要素数は2以上256以下
  • r10の操作にはスタックを使用
E92D4400    @ push {r10, lr}
E3A000XX    @ mov r0, #0xXX
E2400001    @ sub r0, r0, #1
E1A01000    @ mov r1, r0
E5DA2000    @ ldrb r2, [r10]
E5DA3001    @ ldrb r3, [r10, #1]
E1520003    @ cmp r2, r3
C5CA3000    @ strbgt r3, [r10]
C5CA2001    @ strbgt r2, [r10, #1]
E2511001    @ subs r1, r1, #1
C28AA001    @ addgt r10, r10, #1
CAFFFFF7    @ bgt #-0x1c
E2500001    @ subs r0, r0, #1
C59DA000    @ ldrgt r10, [sp]
CAFFFFF3    @ bgt #-0x2c
E8BD8400    @ pop {r10, pc}

　以下各行解説。（見たいコードをクリック）

push {r10, lr} 　r10とlrをスタックに積む。ここで注意すべき点は、複数のレジスタを同時にスタックに積む場合、レジスタ番号の小さい方が後（低位アドレス）に積まれることである。例えば、push {r4-r6}の直後にldr r0, [sp]とすると、r4の値がr0にロードされる。

mov r0, #0xXX 　要素数をr0に読み込む。XXには要素数を指定。

sub r0, r0, #1 　バブルソートの説明の箇所で述べた通り、比較を繰り返す周の数は要素数-1である。この値をr0にセットする。

mov r1, r0 　今回の実装方法の場合、残りの周数=その周での比較回数になる。各周のはじめにr1をr0で初期化しておく必要があるため、r0の値をr1にコピー。

ldrb r2, [r10] 　1番目の要素をr2にロード。

ldrb r3, [r10, #1] 　2番目の要素をr3にロード。

cmp r2, r3 　r2とr3を比較。

strbgt r3, [r10] 　1番目の要素(r2)の方が大きい場合は、2番目の要素(r3)を1番目の要素の位置に格納。

strbgt r2, [r10, #1] 　1番目の要素(r2)の方が大きい場合は、１番目の要素(r2)を２番目の要素の位置に格納。

subs r1, r1, #1 　r1をデクリメント。結果をステータスフラグに反映。

addgt r10, r10, #1 　r1が0より大きい場合、r10をインクリメント。（次の要素を比較するため。）

bgt #-0x1c 　r1が0より大きい場合、ldrb r2, [r10]へと分岐。次の要素の比較が始まる。

subs r0, r0, #1 　r0をデクリメント。結果をステータスフラグに反映。

ldrgt r10, [sp] 　r0が0より大きい場合、spからr10をロード。このときsp(スタックポインタ)は最初にpushしたr10を指しているため、元のr10の値を復元するということになる。

bgt #-0x2c 　r0が0より大きい場合、mov r1, r0へと分岐。次の周の処理が始まる。

pop {r10, pc} 　r10の値を復元、lrの値をpcにロードしサブルーチン終了。

CTRPFで実行

　コードは先程の通り。今回は例として0x10バイトを昇順ソートする。

f:id:bamboo_cpu:20210303211501j:plain
Bubble sort in CTRPF

次に、共有メモリに0x10バイトのランダムな値を書き込む。

f:id:bamboo_cpu:20210303212240j:plain

そして先程のソートコードを実行すると、、、？

f:id:bamboo_cpu:20210303212403j:plain

正しく昇順ソートとなっていることが分かる。

まとめ

　アルゴリズムの知識は必要不可欠。いくらプログラミングの知識を持っていても、効率の悪いコードを書いていては意味がない。他にもアセンブリで簡単に実装できるアルゴリズムは色々とあるので、是非試してみよう。