IchigoJamAdvent Calendar 2024

IchigoJam P で SHA-256 の定数を計算してみる (Bootrom の数学関数を使ってみる)

Posted at 2024-12-10

はじめに

IchigoJam P は、CPU として RP2040 (Raspberry Pi Pico) を用いている。
この RP2040 のデータシートを読むと、内臓の Bootrom に浮動小数点数を扱うライブラリが埋め込まれていることがわかる。
そこで、今回は IchigoJam P でこのライブラリを使ってみる。

※IchigoJamはjig.jpの登録商標です。

SHA-256 で用いる定数

RFC 6234 - US Secure Hash Algorithms (SHA and SHA-based HMAC and HKDF)
より、SHA-256 の計算には「最初の64個の素数それぞれの3乗根の小数部分の最初32ビット」が使われることがわかる。

IEEE 754 の倍精度 (64ビット) 形式では、下位52ビットが仮数部である。
すなわち、整数部分が 1 になるように表す数に2の累乗を掛けたり割ったりしたときの小数部分が下位52ビットに格納される。

そこで、倍精度浮動小数点数のデータを整数として見て、「3乗根の整数部分が1になるように右にシフトするビット数」だけ左にシフトすることで、下位52ビットの部分に本来の「3乗根の小数部分」が現れる。
そうして求めた「3乗根の小数部分」の上位32ビットを取り出す (すなわち、下位20ビットを捨てる) ことで、「3乗根の小数部分の最初32ビット」を求めることができる。

double が IEEE 754 の倍精度である環境では、C言語で以下のようにして「3乗根の小数部分の最初32ビット」を求めることができる。

#include <stdio.h>
#include <math.h>
#include <inttypes.h>

uint32_t calc(int num) {
	union {
		double d;
		uint64_t u;
	} value;
	/* 3乗根を求める */
	value.d = pow(num, 1.0 / 3.0);
	/* 正規化を解除し、整数部分が本来の値になるようにシフトする */
	for (int v = (int)value.d; v > 1; v >>= 1) value.u <<= 1;
	/* 求めた値の下位52ビット (仮数部) のうち、上位32ビットを取り出す */
	return value.u >> 20;
}

int main(void) {
	printf("%08" PRIx32 "\n", calc(2));
	printf("%08" PRIx32 "\n", calc(311));
	return 0;
}

これを実行すると、SHA-256 で用いる定数 K0 の値 428a2f98 および K63 の値 c67178f2 が求まることが確認できる。
なお、311 が (K63 の計算に用いる) 64番目の素数であることは、以下のサイトで確認できる。
素数一覧（４桁以下，番号つき） | 高校数学の美しい物語

数学関数のアドレスを取得する

この章では、データシートの 2.8.3. Bootrom Contents を参考に、RP2040 の Bootrom に搭載されている数学関数のアドレスを取得する方法を確認する。

データテーブルのアドレスを取得する

Bootrom は、メモリ上のアドレス 0x00000000 から配置されている。

アドレス 0x10 からの3バイトはマジックナンバー 0x4D 0x75 0x01 であり、その次のアドレス 0x13 には Bootrom のバージョンを表す値が格納されている。
今回用いる倍精度用の数学関数があるのは、このバージョンを表す値が 2 以降の Bootrom である。

これらの4バイトの値を確認したら、アドレス 0x16 からの2バイトにデータテーブルのアドレスが格納されている。

以下のコードは、このマジックナンバーとバージョンを確認し、データテーブルのアドレスを取得する。

asm15

	R0 = 0
	R0 -= 1
	R1 = #10
	R2 = [R1]
	R2 - #4D
	IF !0 GOTO @END
	R2 = [R1 + 1]
	R2 - #75
	IF !0 GOTO @END
	R2 = [R1 + 2]
	R2 - #01
	IF !0 GOTO @END
	R2 = [R1 + 3]
	R2 - 2
	IF CC GOTO @END
	R0 = [R1 + 3]W
@END
	RET

BASIC

10 POKE#700,0,32,1,56,16,33,10,120,77,42,9,209,74,120,117,42,6,209,138,120,1,42,3,209,202,120,2,42,0,211,200,136,112,71
20 A=USR(#700)
30 IF A=-1 ?"ERROR" ELSE ?HEX$(A,4)

手元の IchigoJam P で実行すると

実行結果

00C4

と出力された。

数学関数テーブルのアドレスを取得する

以下のコードで、求めたアドレス 0x00C4 付近をダンプしてみた。

BASIC

10 POKE#700,0,120,112,71
20 FOR I=#C0 TO #FF
30 IF I%8=0 ?HEX$(I,2);" : ";
40 ?HEX$(USR(#700,I),2);" ";:
50 IF (I+1)%8=0 ?""
60 NEXT

手元の IchigoJam P では、以下の結果が得られた。

実行結果

C0 : 21 23 00 00 47 52 50 00
C8 : 43 52 58 00 53 46 CC 01
D0 : 53 44 4C 02 46 5A CA 01
D8 : 46 53 34 27 46 45 28 2E
E0 : 44 53 30 2E 44 45 A4 3D
E8 : 00 00 7D 48 01 68 00 29
F0 : 28 D1 FF F7 9F FF 7B 49
F8 : 0A 68 53 0E 01 D3 0A 60

テーブルの1個の要素は4バイトで、最初の2バイトにデータの意味を表すキーが、次の2バイトにデータが格納されているようである。

とはいえ、このテーブルの構造はデータシートで定義されていなそうであり、ここから目的のデータを自分で探そうとするのは避けるべきだろう。
かわりに、アドレス 0x18 からの2バイトにアドレスが格納されている関数を用いて、目的のデータを取得する。
この関数は、第1引数にテーブルの先頭アドレスを、第2引数に欲しいデータのキーをとり、与えられたキーに対応するデータを返す。
今回用いる倍精度用の数学関数テーブルのアドレスに対応するキーは #4453 ("SD" をリトルエンディアンなので反転) である。

以下のコードにより、この関数を呼び出し、倍精度用の数学関数テーブルのアドレスを取得できる。

asm15

	PUSH {LR}
	R0 = 0
	' マジックナンバー・バージョンチェック
	R1 = #10
	R2 = [R1]
	R2 - #4D
	IF !0 GOTO @END
	R2 = [R1 + 1]
	R2 - #75
	IF !0 GOTO @END
	R2 = [R1 + 2]
	R2 - #01
	IF !0 GOTO @END
	R2 = [R1 + 3]
	R2 - 2
	IF CC GOTO @END
	' テーブルとデータ取得用関数のアドレスの取得
	R0 = [R1 + 3]W
	R2 = [R1 + 4]W
	' 倍精度用数学関数テーブルのアドレスの取得
	R1 = #44
	R1 = R1 << 8
	R1 += #53
	GOSUB R2
@END
	POP {PC}

BASIC

10 POKE#700,0,181,0,32,16,33,10,120,77,42,14,209,74,120,117,42,11,209,138,120,1,42,8,209,202,120,2,42,5,211,200,136,10,137,68,33,9,2,83,49,144,71,0,189
20 A=USR(#700)
30 IF A=0 ?"ERROR" ELSE ?HEX$(A,4)

手元の IchigoJam P で実行すると

実行結果

024C

と出力された。

数学関数のアドレスを取得する

以下のコードで、求めたアドレス 0x024C 付近をダンプしてみた。

BASIC

10 POKE#700,0,120,112,71
20 A=#024C
30 FOR I=#00 TO #7F
40 IF I%8=0 ?HEX$(A+I,4);" : ";
50 ?HEX$(USR(#700,A+I),2);" ";:
60 IF (I+1)%8=0 ?""
70 NEXT

手元の IchigoJam P では、以下の結果が得られた。

実行結果

024C : 3D 2E 00 00 31 2E 00 00
0254 : 99 2F 00 00 F5 30 00 00
025C : 47 34 00 00 47 34 00 00
0264 : B9 32 00 00 41 35 00 00
026C : 43 35 00 00 4F 35 00 00
0274 : 51 35 00 00 9F 36 00 00
027C : A1 36 00 00 97 36 00 00
0284 : 99 36 00 00 0D 38 00 00
028C : 1D 38 00 00 ED 37 00 00
0294 : 31 38 00 00 3D 3B 00 00
029C : D9 3B 00 00 4B 34 00 00
02A4 : 29 39 00 00 AD 36 00 00
02AC : AF 36 00 00 A7 36 00 00
02B4 : A9 36 00 00 9D 35 00 00
02BC : 9F 35 00 00 B7 35 00 00
02C4 : B9 35 00 00 3F 36 00 00

4バイトずつ関数のアドレス (LSBが 1) が格納されていそうであることがうかがえる。

ここから使いたい数学関数のアドレスを得るには、関数ごとにあらかじめ決まっているオフセットを用いてこのテーブルから要素を取得する。
今回用いる数学関数のアドレスのオフセットは、以下の通りである。

オフセット (バイト)	オフセット (要素)	関数
0x0c	3	`double _ddiv(double a, double b)`
0x1c	7	`int _double2int(double v)`
0x2c	11	`double _int2double(int v)`
0x4c	19	`double _dexp(double v)`
0x50	20	`double _dln(double v)`

以下のコードで、これらの数学関数のアドレスを配列に格納する。
4バイトの値を格納するので、関数1個につき配列を2要素用いる。

asm15

	PUSH {R4,LR}
	R4 = 8
	R4 = R4 << 8
	R4 += R1
	' マジックナンバー・バージョンチェック
	R0 = 1
	R1 = #10
	R2 = [R1]
	R2 - #4D
	IF !0 GOTO @END
	R2 = [R1 + 1]
	R2 - #75
	IF !0 GOTO @END
	R2 = [R1 + 2]
	R2 - #01
	IF !0 GOTO @END
	R2 = [R1 + 3]
	R2 - 2
	IF CC GOTO @END
	' テーブルとデータ取得用関数のアドレスの取得
	R0 = [R1 + 3]W
	R2 = [R1 + 4]W
	' 倍精度用数学関数テーブルのアドレスの取得
	R1 = #44
	R1 = R1 << 8
	R1 += #53
	GOSUB R2
	' 数学関数のアドレスの取得
	R2 = [R0 + 3]L
	[R4]L = R2
	R2 = [R0 + 7]L
	[R4 + 1]L = R2
	R2 = [R0 + 11]L
	[R4 + 2]L = R2
	R2 = [R0 + 19]L
	[R4 + 3]L = R2
	R2 = [R0 + 20]L
	[R4 + 4]L = R2
	R0 = 0
@END
	POP {R4,PC}

BASIC

10 POKE#700,16,181,8,36,36,2,12,68,1,32,16,33,10,120,77,42,25,209,74,120,117,42,22,209,138,120,1,42,19,209,202,120,2,42,16,211,200,136,10,137,68,33,9,2,83,49,144,71,194,104,34,96,194,105,98,96,194,106
20 POKE#73A,162,96,194,108,226,96,2,109,34,97,0,32,16,189
30 IF USR(#700) ?"ERROR":END
40 ?"ddiv       : ";HEX$([1],4);HEX$([0],4)
50 ?"double2int : ";HEX$([3],4);HEX$([2],4)
60 ?"int2double : ";HEX$([5],4);HEX$([4],4)
70 ?"dexp       : ";HEX$([7],4);HEX$([6],4)
80 ?"dln        : ";HEX$([9],4);HEX$([8],4)

手元の IchigoJam P で実行すると

実行結果

ddiv       : 000030F5
double2int : 00003541
int2double : 0000369F
dexp       : 00003B3D
dln        : 00003BD9

と出力された。

SHA-256 の定数を計算する

素数を列挙する

今回はあまり大きな素数を扱わないので、シンプルな試し割りによって素数かを判定する。

BASIC

10 I=2:C=0
20 T=1:GOTO40
30 IF I%T=0 GOTO60
40 T=T+1:IF T*T<=I GOTO30
50 ?DEC$(I,4);:C=C+1:IF C%4=0 ?"" ELSE ?" ";
60 IF C<64 I=I+1:GOTO20

I が素数かを判定する数値、C がこれまでに発見した素数の数、T が試し割りで割る数である。
以下のように、素数を列挙することができた。

実行結果

   2    3    5    7
  11   13   17   19
  23   29   31   37
  41   43   47   53
  59   61   67   71
  73   79   83   89
  97  101  103  107
 109  113  127  131
 137  139  149  151
 157  163  167  173
 179  181  191  193
 197  199  211  223
 227  229  233  239
 241  251  257  263
 269  271  277  281
 283  293  307  311

3乗根の小数部分を求める

RP2040 の Bootrom に搭載されている数学関数には pow(a, b) ($a^b$) は無いようである。
しかし、exp(a) ($e^a$) と ln(a) ($\log_e a$) を用いると

a^b = \left(e^{\log_e a}\right)^b = e^{b \log_e a}

を用いて $a^b$ を計算することができる。
特に、今回求めたい3乗根 pow(a, 1.0 / 3.0) は exp(ln(a) / 3.0) と表せる。

以下のコードは、前章のコードで配列に格納した数学関数のアドレスを用いる。
関数を呼び出す際、double 型の値 (64ビット) は以下のように配置する。

値	上位	下位
第1引数	R1	R0
第2引数	R3	R2
返り値	R1	R0

asm15

	PUSH {R4,R5,R6,LR}
	' R6 に配列の先頭アドレスを置く
	R6 = 8
	R6 = R6 << 8
	R6 += R1
	' 引数 R0 を double に変換し、ln(R0) を計算する
	R3 = [R6 + 2]L
	GOSUB R3
	R3 = [R6 + 4]L
	GOSUB R3
	' 求めた ln(R0) を R5:R4 に退避し、割る数 3.0 を用意する
	R5 = R1
	R4 = R0
	R0 = 3
	R3 = [R6 + 2]L
	GOSUB R3
	' ln(R0) / 3.0 を計算する
	R3 = R1
	R2 = R0
	R1 = R5
	R0 = R4
	R4 = [R6]L
	GOSUB R4
	' exp(ln(R0) / 3.0) を計算する
	R3 = [R6 + 3]L
	GOSUB R3
	' 計算結果を R5:R4 に保存し、整数に変換する
	R5 = R1
	R4 = R0
	R3 = [R6 + 1]L
	GOSUB R3
	' 求めた整数が 1 になるまで右シフトし、その分計算結果を左シフトする
	R1 = 0
	GOTO @SHIFT_LOOP_CHECK
@SHIFT_LOOP
	R0 = R0 >> 1
	R5 = R5 << 1
	R4 = R4 << 1
	R5 += R1 + C
@SHIFT_LOOP_CHECK
	R0 - 1
	IF HI GOTO @SHIFT_LOOP
	' 計算結果の下位20ビットを捨て、その次の32ビットを配列に格納する
	' 欲しい部分は、R4の上位12ビットと、R5の下位20ビットである
	R0 = R5 << 12
	R1 = R4 >> 20
	R0 |= R1
	[R6 + 5]L = R0

	POP {R4,R5,R6,PC}

# 700 から格納している数学関数のアドレスを取得するコードと重ならないよう、このコードは # 750 から格納する。

BASIC

10 POKE#700,16,181,8,36,36,2,12,68,1,32,16,33,10,120,77,42,25,209,74,120,117,42,22,209,138,120,1,42,19,209,202,120,2,42,16,211,200,136,10,137,68,33,9,2,83,49,144,71,194,104,34,96,194,105,98,96,194,106
20 POKE#73A,162,96,194,108,226,96,2,109,34,97,0,32,16,189
30 POKE#750,112,181,8,38,54,2,14,68,179,104,152,71,51,105,152,71,13,70,4,70,3,32,179,104,152,71,11,70,2,70,41,70,32,70,52,104,160,71,243,104,152,71,13,70,4,70,115,104,152,71,0,33,3,224,64,8,109,0
40 POKE#78A,100,0,77,65,1,40,249,216,40,3,33,13,8,67,112,97,112,189
50 IF USR(#700) ?"ERROR":END
60 X=USR(#750,2):?HEX$([11],4);HEX$([10],4)
70 X=USR(#750,311):?HEX$([11],4);HEX$([10],4)

実行すると、「SHA-256 で用いる定数」の章で掲載したC言語のコードと同じ値が得られた。

実行結果

428A2F98
C67178F2

処理を組み合わせる

「素数を列挙する」処理と「3乗根の小数部分を求める」処理を組み合わせれば、「SHA-256 の定数を計算する」処理が完成する。

BASIC

10 ' SHA-256 ﾉ Kn ｦ ｹｲｻﾝ
20 POKE#700,16,181,8,36,36,2,12,68,1,32,16,33,10,120,77,42,25,209,74,120,117,42,22,209,138,120,1,42,19,209,202,120,2,42,16,211,200,136,10,137,68,33,9,2,83,49,144,71,194,104,34,96,194,105,98,96,194,106
30 POKE#73A,162,96,194,108,226,96,2,109,34,97,0,32,16,189
40 POKE#750,112,181,8,38,54,2,14,68,179,104,152,71,51,105,152,71,13,70,4,70,3,32,179,104,152,71,11,70,2,70,41,70,32,70,52,104,160,71,243,104,152,71,13,70,4,70,115,104,152,71,0,33,3,224,64,8,109,0
50 POKE#78A,100,0,77,65,1,40,249,216,40,3,33,13,8,67,112,97,112,189
60 IF USR(#700) ?"ERROR":END
70 I=2:C=0
80 T=1:GOTO100
90 IF I%T=0 GOTO120
100 T=T+1:IF T*T<=I GOTO90
110 X=USR(#750,I):?HEX$([11],4);HEX$([10],4);:C=C+1:IF C%4=0 ?"" ELSE ?" ";
120 IF C<64 I=I+1:GOTO80

実行すると、RFC 6234 に載っているのと同じ64個の値が得られた。

実行結果

428A2F98 71374491 B5C0FBCF E9B5DBA5
3956C25B 59F111F1 923F82A4 AB1C5ED5
D807AA98 12835B01 243185BE 550C7DC3
72BE5D74 80DEB1FE 9BDC06A7 C19BF174
E49B69C1 EFBE4786 0FC19DC6 240CA1CC
2DE92C6F 4A7484AA 5CB0A9DC 76F988DA
983E5152 A831C66D B00327C8 BF597FC7
C6E00BF3 D5A79147 06CA6351 14292967
27B70A85 2E1B2138 4D2C6DFC 53380D13
650A7354 766A0ABB 81C2C92E 92722C85
A2BFE8A1 A81A664B C24B8B70 C76C51A3
D192E819 D6990624 F40E3585 106AA070
19A4C116 1E376C08 2748774C 34B0BCB5
391C0CB3 4ED8AA4A 5B9CCA4F 682E6FF3
748F82EE 78A5636F 84C87814 8CC70208
90BEFFFA A4506CEB BEF9A3F7 C67178F2

まとめ

IchigoJam P を用いて、マシン語から RP2040 の Bootrom に格納されている数学関数を呼び出すことで、SHA-256 の計算で用いられる「3乗根の小数部分」を求めることができた。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up