MachiKania type Zで使われている多次元配列の実装について
2016年10月23日
MachiKania type Zでは、多次元配列をサポートしている。そのアルゴリズム及び実装方法についてのメモ。
例えば、次のように宣言した場合。
DIM A(1,2,3)
使用可能な変数は、次の通り。
A(0,0,0) A(0,0,1) A(0,0,2) A(0,0,3) A(0,0,0) A(0,1,1) A(0,1,2) A(0,1,3) A(0,2,0) A(0,2,1) A(0,2,2) A(0,2,3) A(1,0,0) A(1,0,1) A(1,0,2) A(1,0,3) A(1,0,0) A(1,1,1) A(1,1,2) A(1,1,3) A(1,2,0) A(1,2,1) A(1,2,2) A(1,2,3)
ここで、次の変数には、多次元配列へのポインターが入っている。
A(0):A(0,0)へのポインター: A(0,0)+0
A(1):A(1,0)へのポインター: A(0,0)+3
A(0,0):A(0,0,0)へのポインター: A(0,0,0)+0
A(0,1):A(0,1,0)へのポインター: A(0,0,0)+4
A(0,2):A(0,2,0)へのポインター: A(0,0,0)+8
A(1,0):A(1,0,0)へのポインター: A(0,0,0)+16
A(1,1):A(1,1,0)へのポインター: A(0,0,0)+20
A(1,2):A(1,2,0)へのポインター: A(0,0,0)+24
実行時には、配列Ａの次元数は明らかになっていないから、上記ポインター値は、DIM宣言した時に挿入しておく。実行時には、配列へのポインターは次のように解決する。A(1,2,3)へのポインターの解決方法を例に取る。
1. AにはA(0)へのポインターが挿入されているので、&A(1)=A+1*4
2. A(1)にはA(1,0)へのポインターが挿入されているので、&A(1,2)=A(1)+2*4
3. A(1,2)にはA(1,2,0)へのポインターが挿入されているので、&A(1,2,3)=A(1,2)+3*4
アセンブリー中では、以下の順でアドレス解決を行なう。括弧内は、A(1,2,3)のケース。
1. $v1に、変数名(A-Z)に従って、$s8からアドレスを取得。（$v1は、A(0)へのポインター）
2. 最初の引数を、$v0に取得。
3. $v1=$v1+($v0<<2)（$v1は、A(1)へのポインター）
4. ","がある場合
1. 次の引数を、$v0に取得
2. $v1=0($v1)（$v1は、A(1,0)へのポインター）（$v1は、A(1,2,0)へのポインター）
3. $v1=$v1+($v0<<2)（$v1は、A(1,2)へのポインター）（$v1は、A(1,2,3)へのポインター）
4. さらに","があれば、繰り返し
5. ")"であれば、エラー無し。
6. $v1に、アドレスが格納されている。
DIM A(1,2,3)の宣言の際には、以下の順で領域を確保する。
1. A(0) A(1)の領域を確保し、&A(0)をAに代入する
2. A(0,0) A(0,1) A(0,2) A(1,0) A(1,1) A(1,2) の領域を確保し、&A(0,0,0) &A(0,1,0) ... &A(1,2,0)を代入する
3. A(0,0,0) A(0,0,1) ... A(1,2,2) A(1,2,3)の領域を確保する
DIM A(x,y,z)と宣言した場合、(x+1)+(x+1)*(y+1)+(x+1)*(y+1)*(z+1)ワードが確保される。DIM A(1,2,3)の場合は、３２ワード。配列宣言時に消費する容量が大きい反面、コンパイルオブジェクトが簡潔になるので、実行速度も速くなるし、コンパイルオブジェクトが多量のRAMを使わずに済む。
例えば、次のように宣言した場合。
DIM A(1,2,3)
使用可能な変数は、次の通り。
A(0,0,0) A(0,0,1) A(0,0,2) A(0,0,3) A(0,0,0) A(0,1,1) A(0,1,2) A(0,1,3) A(0,2,0) A(0,2,1) A(0,2,2) A(0,2,3) A(1,0,0) A(1,0,1) A(1,0,2) A(1,0,3) A(1,0,0) A(1,1,1) A(1,1,2) A(1,1,3) A(1,2,0) A(1,2,1) A(1,2,2) A(1,2,3)
ここで、次の変数には、多次元配列へのポインターが入っている。
A(0):A(0,0)へのポインター: A(0,0)+0
A(1):A(1,0)へのポインター: A(0,0)+3
A(0,0):A(0,0,0)へのポインター: A(0,0,0)+0
A(0,1):A(0,1,0)へのポインター: A(0,0,0)+4
A(0,2):A(0,2,0)へのポインター: A(0,0,0)+8
A(1,0):A(1,0,0)へのポインター: A(0,0,0)+16
A(1,1):A(1,1,0)へのポインター: A(0,0,0)+20
A(1,2):A(1,2,0)へのポインター: A(0,0,0)+24
実行時には、配列Ａの次元数は明らかになっていないから、上記ポインター値は、DIM宣言した時に挿入しておく。実行時には、配列へのポインターは次のように解決する。A(1,2,3)へのポインターの解決方法を例に取る。
1. AにはA(0)へのポインターが挿入されているので、&A(1)=A+1*4
2. A(1)にはA(1,0)へのポインターが挿入されているので、&A(1,2)=A(1)+2*4
3. A(1,2)にはA(1,2,0)へのポインターが挿入されているので、&A(1,2,3)=A(1,2)+3*4
アセンブリー中では、以下の順でアドレス解決を行なう。括弧内は、A(1,2,3)のケース。
1. $v1に、変数名(A-Z)に従って、$s8からアドレスを取得。（$v1は、A(0)へのポインター）
2. 最初の引数を、$v0に取得。
3. $v1=$v1+($v0<<2)（$v1は、A(1)へのポインター）
4. ","がある場合
1. 次の引数を、$v0に取得
2. $v1=0($v1)（$v1は、A(1,0)へのポインター）（$v1は、A(1,2,0)へのポインター）
3. $v1=$v1+($v0<<2)（$v1は、A(1,2)へのポインター）（$v1は、A(1,2,3)へのポインター）
4. さらに","があれば、繰り返し
5. ")"であれば、エラー無し。
6. $v1に、アドレスが格納されている。
DIM A(1,2,3)の宣言の際には、以下の順で領域を確保する。
1. A(0) A(1)の領域を確保し、&A(0)をAに代入する
2. A(0,0) A(0,1) A(0,2) A(1,0) A(1,1) A(1,2) の領域を確保し、&A(0,0,0) &A(0,1,0) ... &A(1,2,0)を代入する
3. A(0,0,0) A(0,0,1) ... A(1,2,2) A(1,2,3)の領域を確保する
DIM A(x,y,z)と宣言した場合、(x+1)+(x+1)*(y+1)+(x+1)*(y+1)*(z+1)ワードが確保される。DIM A(1,2,3)の場合は、３２ワード。配列宣言時に消費する容量が大きい反面、コンパイルオブジェクトが簡潔になるので、実行速度も速くなるし、コンパイルオブジェクトが多量のRAMを使わずに済む。