IchigoJam Advent Calendar 2025

IchigoJam でQRコード生成

Posted at 2025-12-13

去年は、IchigoJam でQRコードを生成するAPIを呼び出し、その結果を画面に表示した。

IchigoJam + MixJuice でQRコードを表示する #QRcode - Qiita

今回は、IchigoJam (1.4 系以降) で最低限のQRコード生成処理を行う。

※IchigoJamはjig.jpの登録商標です
「QRコード」は株式会社デンソーウェーブの登録商標です。

QRコードの生成方法

ヘッダ・フッタの付与

Creating a QR Code step by step
の情報をもとに、QRコードに格納するデータの前後にデータを付与し、以下の構造にする。

エンコードの種類 (4ビット)
データの長さ (8ビット)
データ
終端を表すゼロ (4ビット)
パディング

今回は、データとしてバイト列をそのまま格納するバイナリモードを用い、エンコードの種類は 0100 である。
ここが4ビットであるため、もとのデータと格納されるデータは4ビットずれ、もとの1バイトを2個のバイトにまたがって格納することになる。

パディングは、#EC と #11 のバイトを、残った容量の分だけ繰り返す。
今回は、バージョン 1、誤り訂正レベル L のQRコードを作るので、これにより全体の長さを19バイトにする。

リード・ソロモン符号の計算

リードソロモン符号 | 技術説明 | Siglead
ＱＲコードをつくってみるその３ - 誤り訂正コード語の作成

QRコードでは、格納するデータにリード・ソロモン符号による誤り訂正データを追加してから格納する。
リード・ソロモン符号のエンコードは、以下のように行う。

計算に用いる「数」の準備

まず、

\alpha^8 + \alpha^4 + \alpha^3 + \alpha^2 + 1 = 0

となる特殊な数 $\alpha$ を考える。
また、この $\alpha$ に関する多項式の計算では、係数は $\mod 2$ で考える。
すなわち、$1 + 1 = 0$ となり、加算を xor で行うことができる。
このとき、両辺に $\alpha^4 + \alpha^3 + \alpha^2 + 1$ を加えることで

\alpha^8 = \alpha^4 + \alpha^3 + \alpha^2 + 1

が成り立つことがわかる。
ここで、$\alpha^k$ に、これを $\alpha^0$ から $\alpha^7$ までの和で表し、$\alpha$ に $2$ を代入したときの数値を対応付ける。($\alpha^0 = 1$ であることに注意)
たとえば、$\alpha^8$ には $2^4 + 2^3 + 2^2 + 1 = 29$ が対応付けられる。
この対応する数値は、以下のようにして求めることができる。

$\alpha^0$ に 1 を対応付ける
$\alpha^{k+1}$ には、$\alpha^k$ に対応付けた値の2倍の値を対応付ける
ただし、2倍の値が 256 以上の場合は、かわりにそれを 256 で割った余りと 29 (#1D) の xor を対応付ける

「2倍の値」になるのは、$\alpha$ の多項式に $\alpha$ を掛けることで、何乗かの数値がそれぞれ 1 増えるためである。
「2倍の値が 256 以上」とは $\alpha^8$ が現れたことに対応しており、$\alpha^8 = \alpha^4 + \alpha^3 + \alpha^2 + 1$ を用いて変形を行うことを xor で表す。

この方法で計算を進めると、$\alpha^{255} = 1 = \alpha^0$ となることがわかる。
しかし、このままでは 1 が複数の $\alpha^k\ (0 \leq k \leq 255)$ に対応付いてしまい、計算処理が面倒になる。
そこで、計算処理の便宜上、$\alpha^{255}$ には 0 を対応付ける。
このことにより $\alpha^0$ から $\alpha^{255}$ と 0～255 の整数が1対1に対応付き、逆に整数から $\alpha^k$ に変換するテーブルも用意できる。

生成多項式の用意

誤り訂正データを求めるために用いる生成多項式を用意する。
$n$ バイトの誤り訂正データを追加するとき、生成多項式は以下の式になる。

\prod_{i=0}^{n-1}(x+\alpha^i) = (x+1)(x+\alpha)\cdots(x+\alpha^{n-1})

今回は 7 バイトの誤り訂正データを追加するので $n=7$ とし、生成多項式を展開すると以下の式になる。

x^7 +  \alpha^{87} x^6 + \alpha^{229} x^5 + \alpha^{146} x^4 + \alpha^{149} x^3 + \alpha^{238} x^2 + \alpha^{102} x + \alpha^{21}

誤り訂正データの計算

まず、入力データ (バイト列) を $x$ の多項式で表す。
入力データの最初のバイトを $x$ の最高次の項、最後のバイトを定数項 ($x^0$ の項) に変換する。
それぞれの項の係数は、それぞれのバイトが表す整数に対応する $\alpha^k$ とする。

たとえば、19 バイトのデータ #40, #D6, ..., #EC, #11 は、対応関係

整数 (十六進)	整数 (十進)	$\alpha^k$
`#40`	64	$\alpha^6$
`#D6`	214	$\alpha^{85}$
…	…	…
`#EC`	236	$\alpha^{122}$
`#11`	17	$\alpha^{100}$

を用いて

\alpha^6 x^{18} + \alpha^{85} x^{17} + \cdots + \alpha^{122} x + \alpha^{100}

と表せる。
誤り訂正データが入る場所を空けるため、$n$ バイトの誤り訂正データを追加するとき、この式に $x^n$ を掛ける。
今回は $n=7$ なので

\alpha^6 x^{25} + \alpha^{85} x^{24} + \cdots + \alpha^{122} x^8 + \alpha^{100} x^7

となる。
この式を生成多項式で割った余りを求める。
これは、$x^n$ 以上の次数の項が無くなるまで、以下の手順を繰り返すことで行える。

生成多項式に、現在の式の最高次の項を $x^n$ で割ったものを掛ける
それを現在の式から引く

たとえば、先ほどの式の場合、最高次の項は $\alpha^6 x^{25}$ であり、これを $x^7$ で割ったものを生成多項式に掛けると

\alpha^{6} x^{25} + \alpha^{93} x^{24} + \alpha^{235} x^{23} + \alpha^{152} x^{22} + \alpha^{155} x^{21} + \alpha^{244} x^{20} + \alpha^{108} x^{19} + \alpha^{27} x^{18}

となる。

$\alpha^{255} = 1 = \alpha^0$ なので、$\alpha^p \alpha^q = \alpha^{(p+q) \bmod 255}$ である。

これを現在の式から引く。
このとき、$\mod 2$ で考えるので、「引く」と「足す」は実質同じ操作となる。
よって、同じ $x$ の次数の項の係数同士を足せばよい。
$\alpha^p + \alpha^q = \alpha^r$ となる $r$ は、$p, q$ から以下のようにして求めることができる。

$\alpha^p$ および $\alpha^q$ に対応する整数 $p'$ および $q'$ を求める
$r'$ を $p'$ と $q'$ の xor とする
$\alpha^r$ が整数 $r'$ に対応するような $r$ を求める

$p = q$ のとき、$\alpha^p + \alpha^q = 0$ となり、これは $\alpha^r$ の形で表せない。
しかし、今回は計算の便宜上 $\alpha^{255}$ に $0$ を対応付けることにしたので、このときは $r=255$ である。

最終的に、余り

\alpha^{k_0} x^{n-1} + \alpha^{k_1} x^{n-2} + \cdots + \alpha^{k_{n-2}} x + \alpha^{k_{n-1}}

が求まったら、$\alpha^{k_0}, \ldots, \alpha^{k_{n-1}}$ に対応する整数を順に求め、これらが表すバイトの列を誤り訂正データとする。

プログラムによる計算

ここまでの処理を行い、入力データから誤り訂正データを求めるプログラムを実装した。

Python

計算中、一気に上位2項が消え、単純なループを用いると0を掛ける操作が発生するよう、入力データを工夫した。
計算結果として、生成多項式の $x$ の係数がそれぞれ $\alpha$ の何乗かと、最終的に求めた誤り訂正データを出力する。
また、「Creating a QR Code step by step」で求めた誤り訂正データを埋め込んでおき、計算で求めた誤り訂正データと同じかをチェックする。

# `ello, world!
data = [0x40,0xD6,0x06,0x56,0xC6,0xC6,0xF2,0xC2,0x07,0x76,0xF7,0x26,0xC6,0x42,0x10,0xEC,0x11,0xEC,0x11]
code = [0x9F,0xAF,0x14,0x5D,0x89,0x05,0x37]

garoa = 0x1d

# garoa_table[i] = α**i のベクトル表現
garoa_table = []
cur = 1
for _ in range(256):
    garoa_table.append(cur)
    cur <<= 1
    if cur > 0xff:
        cur = (cur & 0xff) ^ garoa

inv_garoa_table = [None for _ in range(256)]
# garoa_table[255] = 1 を変換の対象から外す
for i, g in enumerate(garoa_table[:255]):
    inv_garoa_table[g] = i

# 計算の便宜上、α**255 を多項式表現 0 として扱う
garoa_table[255] = 0
inv_garoa_table[0] = 255

def garoa_add(v1, v2):
    return inv_garoa_table[garoa_table[v1] ^ garoa_table[v2]]

def garoa_mult(v1, v2):
    if v1 == 255 or v2 == 255:
        # 0 に何を掛けても 0
        return 255
    return (v1 + v2) % 255

# リストの各要素はαの何乗かを表すとして、多項式の掛け算を行う
def garoa_formula_mult(f1, f2):
    res = [255 for _ in range(len(f1) + len(f2) - 1)]
    for i, v1 in enumerate(f1):
        for j, v2 in enumerate(f2):
            res[i + j] = garoa_add(res[i + j], garoa_mult(v1, v2))
    return res

gen_formula = [0]
for i in range(len(code)):
    gen_formula = garoa_formula_mult(gen_formula, [i, 0])

# divider の各要素は、αの何乗かを表す
divider = gen_formula[::-1]
print(divider)

# dividend の各要素は、ベクトル表現を表す
dividend = data + [0 for _ in code]

for i in range(len(data)):
    factor = inv_garoa_table[dividend[i]]
    divider_multed = [garoa_mult(factor, v) for v in divider]
    for j in range(len(divider)):
       dividend[i + j] = garoa_table[garoa_add(inv_garoa_table[dividend[i + j]], divider_multed[j])]

code_calculated = dividend[-len(code):]
print(code_calculated)
print(code_calculated == code)

これを実行すると以下の出力が得られ、生成多項式と誤り訂正データが正しく求まっていることを確かめることができた。

実行結果

[0, 87, 229, 146, 149, 238, 102, 21]
[159, 175, 20, 93, 137, 5, 55]
True

IchigoJam BASIC

Python のプログラムで確認した計算手順を、IchigoJam BASIC で実装した。

10 CLS:LET[0],#40,#D6,#06,#56,#C6,#C6,#F2,#C2,#07,#76,#F7,#26,#C6,#42,#10,#EC,#11,#EC,#11,0,0,0,0,0,0,0
20 C=1:FOR I=0 TO #FE:POKE#900+I,C:C=C*2^(#11D*(C>127)):NEXT:POKE#9FF,0
30 FOR I=0 TO #FF:POKE#A00+PEEK(#900+I),I:NEXT
40 LET[31],87,229,146,149,238,102,21
50 FOR I=0 TO 18
60 IF [I]<>0 F=PEEK(#A00+[I]):FORJ=1TO7:[I+J]=[I+J]^PEEK(#900+(F+[30+J])%255):NEXT
70 NEXT
80 LOCATE 0,18:FOR I=1 TO 7:?" ";HEX$([18+I],2);:NEXT:?""

各行の役割は、以下の通りである。

10行目：計算に用いる入力データと、誤り訂正データを格納する領域を用意する
20行目：$\alpha^k$ の $k$ から対応する整数に変換するテーブルを用意する
30行目：対応する整数から $\alpha^k$ の $k$ に変換するテーブルを用意する
40行目：生成多項式の係数 ($\alpha$ の何乗か) を用意する
50～70行目：多項式の除算を行い、誤り訂正データを求める
80行目：求めた誤り訂正データを出力する

変換テーブルには、連続した領域が確保でき、動作への影響も少ない VRAM を用いた。

多項式の除算では、Python 版と比べ、無駄なテーブル参照 (変換の直後の逆変換) を消去した。
また、Python 版では便宜上 $\alpha^{255}$ を $0$ として扱うための処理を乗算処理 garoa_mult で行っているが、このプログラムでは係数が 0 のときは掛け算と引き算の処理をスキップし、そもそも「0 を掛ける」処理が発生しないようにした。

これを実行すると以下の実行結果が得られ、「Creating a QR Code step by step」と同じ誤り訂正データが求まっていることが確認できた。

データのQRコード化

Creating a QR Code step by step
をもとに、誤り訂正データを含むバイト列をQRコードとして描画していく。
今回は、以下の順番で処理を行う。

ファインダパターンの描画
形式情報とタイミングパターンの描画
データの描画
マスク処理

本来は、定義された全てのマスクパターンを試し、評価が最高となるマスクパターンを選択することが求められる。
しかし、今回は簡単のため、マスクパターン2で決め打ちする。
これにより、形式情報も一定となる。(誤り訂正レベルも固定のため)

これを IchigoJam BASIC で実装したのが、以下のプログラムである。
データを10行目で埋め込み、それを描画する。

10 LET[0],#40,#D6,#06,#56,#C6,#C6,#F2,#C2,#07,#76,#F7,#26,#C6,#42,#10,#EC,#11,#EC,#11,#9F,#AF,#14,#5D,#89,#05,#37
20 CLS:FOR X=4 TO 18 STEP 14:FOR Y=4 TO 18 STEP 14
30 FOR I=0 TO 1:DRAW X,Y+6*I,X+6,Y+6*I:DRAW X+6*I,Y,X+6*I,Y+6:DRAW X+2,Y+2+I,X+4,Y+2+I:NEXT
40 DRAW X+2,Y+4,X+4,Y+4
50 NEXT:NEXT
60 DRAW 4,12,17,12:DRAW 9,12,0:DRAW 12,17,12,24:DRAW 12,19,0
70 FOR I=0 TO 4 STEP 2:DRAW 12,5+I:DRAW 19+I,12:DRAW 12+I,10:DRAW 10,12+I:NEXT
80 X=24:Y=24:D=-1:FOR I=0 TO 26*8-1:DRAW X,Y,[I/8]>>(7-I%8)&1
90 IF (Y=13 AND (X=6 OR X=11 OR X=19 OR X=23)) OR (Y=4 AND X=15) X=X-1-(X=11):D=-D:GOTO 130
100 IF Y=24 AND X%4=1 Y=Y-8*(X=13):X=X-1:D=-D:GOTO 130
110 IF Y=16 AND X=8 X=X-1:D=-D:GOTO 130
120 IF X%2=(X>10) X=X+1:Y=Y+D+D*((Y=9 OR Y=11) AND Y=10-D) ELSE X=X-1
130 NEXT
140 FOR X=4 TO 22 STEP 3:IF X<>10 DRAW X,13-9*(X=13 OR X=16),X,24-8*(X<9),2
150 NEXT:DRAW 13,10,2:DRAW 16,10,2
160 LOCATE 0,15

これを実行すると、以下の結果が得られた。

20～50行目：ファインダパターンの描画

X および Y のループで、四隅にファインダパターンを描画する。
必要ない右下にも描画されるが、後でデータで上書きするので問題ない。

I のループで、横線2本、縦線2本、中の四角のうち上2行を描画する。
その後、中の四角の残った1行を描画する。

60～70行目：形式情報とタイミングパターンの描画

まず、横方向と縦方向に、黒い線の中に1箇所だけ白い点がある部分を描画する。
横方向は、データで上書きされる部分を通り、右側の端まで一気に描画する。

次に、FOR 文を用い、黒い点と白い点が交互になっている部分を描画する。

80～130行目：データの描画

描画する座標 (X, Y) および描画の方向 D を用いて、データの描画を行う。
基本的に、2列単位で描画を行い、右の列に居るときは左の列に、左の列に居るときは次の行の右の列に移動する。
端の行に居る場合は、方向転換および次の2列への移動を行う。
また、タイミングパターンが入る行や列は飛ばす。

140～150行目：マスク処理

今回は、マスクパターン2の処理のみを行う。
これは、左端の列から始め、3列ごとに列内のデータを反転させる処理である。
これを、DRAW の反転機能を用いて行う。

このとき、タイミングパターンは反転させないようにする。
タイミングパターンの列は、反転処理を IF 文で回避するようにした。
タイミングパターンの行は、一旦反転処理を行い、後でもう一度反転処理をして打ち消すようにした。

実装

「リード・ソロモン符号の計算」と「データのQRコード化」の2本のプログラムを合体し、入力を受け付けて「ヘッダ・フッタの付与」を行う処理を追加し、

余計な空白の削除
行の統合
FOR 文や IF 文の統合
式変形や演算子の優先順位の考慮による、カッコの削減などの式の短縮

などの工夫を行って規定の容量に収まるようにプログラムを縮めることで、以下のプログラムが完成した。

10 'QRﾂｸﾙ
20 CLV:LET[31],87,229,146,149,238,102,21:CLS:?"ﾓｼﾞﾚﾂ? (17 ﾓｼﾞ ﾏﾃﾞ)":S=#900+POS():INPUT"",L:L=LEN(S):IFL>17L=17
30 LET[0],64+L/16,L%16*16:IFLFORI=1TOL:C=PEEK(S+I-1):[I]=[I]+C/16:[I+1]=C%16*16:NEXT
40 IFL<17FORI=L+2TO18:[I]=17+I^L%2^1*#DB:NEXT
50 COPY#880,#800,38:C=1:FORI=0TO#FE:POKE#A00+I,C:POKE#B00+C,I:C=C*2^(C/128*285):NEXT:POKE#AFF,0,#FF:FORI=0TO18:IF[I]F=PEEK(#B00+[I]):FORJ=1TO7:[I+J]=[I+J]^PEEK(#A00+(F+[30+J])%255):NEXT
60 NEXT:COPY#800,#880,38:CLS:FORI=0TO2:J=I/2:K=I*2:FORX=4TO18STEP14:FORY=4TO18STEP14:DRAWX,Y+6*J,X+6,Y+6*J:DRAWX+6*J,Y,X+6*J,Y+6:DRAWX+2,Y+2+I,X+4,Y+2+I:NEXT
70 NEXT:DRAW12,5+K:DRAW19+K,12:DRAW12+K,10:DRAW10,12+K:NEXT:DRAW4,12,17,12:DRAW9,12,0:DRAW12,17,12,24:DRAW12,19,0:X=24:Y=24:D=-1:FORI=0TO207:DRAWX,Y,[I/8]>>(7-I%8)&1
80 IFY=13AND(X=6ORX=11ORX=19ORX=23)ORY=4ANDX=15ORY=24ANDX%4=1ORY=16ANDX=8Y=Y-8*(X=13):X=X-1-(X=11):D=-DELSEIFX%2=(X>10)X=X+1:Y=Y+D<<(Y=10-D)ELSEX=X-1
90 NEXT:FORX=4TO22STEP3:IFX-10DRAWX,4+9*(X<13OR16<X),X,24-8*(X<9),2
100 NEXT:DRAW13,10,2:DRAW16,10:LOCATE0,15