げんげんの頭の中とQRコードを解析してみる

はじめに

どうも、知識量もルックスも到底げんげん¹には勝てないあさっちです。
先日、某クイズ番組にて「以下のQRコードを解析せよ」との問題が出されました。

正解は東北学院大学のHPであり、げんげんは見事に正解。
げんげんは「屋上にQRコードがある」と解説していましたが、きっとこれは後付けであり、肉眼でQRコードを解析して正解を確信したのだろうと思われます²。

スマホ片手にQRコードを読み取った(その結果リンク先サーバがダウンしたらしいですが…)我々一般人の多くが「げんげんの頭の中は一体どうなっているんだ？」と思ったことでしょう。

僭越ながら私が、正解に至るまでのげんげんの脳内を少し覗いてみようと思います。

(この記事を読むにあたって必要な知識は「2進法を10進法に直す」のみです³。)

フォーマット情報取得とマスク処理解除

まず、前提として黒マスには"1"という情報が、白マスには"0"という情報が入っているものとして話を進めていきます。

まずはQRコードの左上に注目します。
ここにどういうフォーマット形式なのかを記した情報が載っています。

青の斜め線を引いた箇所⁴はスキップして、赤の矢印の方向に沿って読んでいくと
「1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1」
となります。

QRコードは白と黒の比率が極端に偏らないようにマスク処理を施しているので、ここでそれを剥がしてしまいます。
そのために「形式情報のマスクパターン101010000010010⁵とのXOR演算をとる」ということを行います。

XOR演算は「(各桁に対して)同じ数字なら0を、違う数字なら1を返す」という処理です。
QRコード情報とマスクパターンの各桁を見比べていくと下のようになります。

1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1 (QRコード情報)
1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0 (マスクパターン)
　　　　　　　　　　↓
0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1 (マスク処理解除後)

マスクパターン参照子

マスク処理解除により得られた数字列で注目して欲しいのは、左から3~5番目の「1, 1, 0」という情報です(マスクパターン参照子と言います)。

これはどういうことかと言うと、
「上から数えて$i$番目、左から数えて$j$番目のマスに注目して、$ij$を2で割った余りと3で割った余りの和が偶数なら、そのマスの白黒を反転させる」
です。

ピンとこないと思うので、具体例を交えて説明していきます。
赤い矢印に沿って進んでいき、最初に通過する青いマスに注目しましょう。

0からカウントし始めることに注意してください。
これは上から8番目($i=8$)、左から6番目($j=6$)のマスです。
まずはこれらを掛け算します($8\times6 = 48$)。
この48を2で割った余り(0です)と、48を3で割った余り(同じく0です)を足します。
当然$0+0=0$でこれは偶数となります。
なので、(実際にはこのマスには何の情報もありませんが)この上から8番目、左から6番目の黒マスは白マスとして扱え(つまり"0"の情報を持ったマスとせよ)、ということになります。
奇数であればそのまま読み進めて構いません。

何となく分かっていただけたでしょうか？
これを300個ほどのマスに対して行っていくことになります…

下の図の、緑の丸がついているところ以外はすべて白黒反転します⁶。
読み進めていけばわかりますが、左側は必要ないので手をつけていません。

そして、それを元に0と1の情報を書き込んだものが下図になります。
先程と同様に、数字が書き込まれてない箇所は必要ありません。

実際の解析とASCIIコード表

さて、いよいよQRコードを読み解いていきます。

QRコードは右下から2列ずつ上に、突き当たり(上図でいう数字が書かれていないところ)まで行ったら次の左2列を下に、そしてまた上に…、と以下の図のような規則に従って読んでいきます。

これを参考にしつつ、一番右下の4つに書かれている「0100」から順に解析していきます。
まず、この「0100」ですが、これは8ビットバイトモードという記録方式の一種ですので飛ばしてOKです。

次の「00011110」は10進数では30に相当します。
これは「このQRコードは30文字の情報を持っています」ということを意味します。

ここからが本題です。
続いて「01101000」ですが、10進法に直すと104です。
ここからはASCIIコード表でこの10進数をアルファベットや記号に直していきます。
こちらのサイトにASCIIコード表があるので、左の列の「10進」から104にあたるものを探してきます。
すると、アルファベット"h"があります。

以下、同じようにして
「8つ区切りで0,1の数字を読み取る→10進数に直す→ASCIIコード表と照らし合わせる」
ということを繰り返していきます。

01110100：116→t
01110100：116→t
01110000：112→p
00111010：58→:
00101111：47→/
00101111：47→/
01110111：119→w
01110111：119→w
01110111：119→w
00101110：46→.
01110100：116→t
01101111：111→o
01101000：104→h
01101111：111→o
01101011：107→k
01110101：117→u
00101101：45→-
01100111：103→g
01100001：97→a
01101011：107→k
01110101：117→u
01101001：105→i
01101110：110→n
00101110：46→.
01100001：97→a
01100011：99→c
00101110：46→.
01101010：106→j
01110000：112→p

上から順に読むと
http://www.tohoku-gakuin.ac.jp (30文字)
となります。

30文字読み取ったのでここで終了します。
上の図ですべてのマスに0と1を書いていないのもこのためです。
なお、残りのマスはエラー検出などに使います。

終わりに

このQRコードのみの解析に特化した記事ですので、これを読めばすべてのQRコードを肉眼で読めることは保証しません、というか無理です。

なお、この記事はここを参照させていただきました。
ここで触れた以外にもQRコードについての情報が載っており大変参考になるサイトです。
最後の「8文字ずつ取り出す」流れはこのサイトの方が図を交えてあるので見やすいと思います。
画像も一部拝借しております。

末筆ながら、げんげん優勝おめでとうございます。

1. twitterはこちら ↩

2. もしそうなら本当に尊敬します… ↩

3. バイナリ解析などでは普通16進変換ですが、それに慣れない人もいると思うので。目をつぶってください。 ↩

4. タイミングパターンと呼ばれ、簡単に言うと基準となる座標軸のようなものです。 ↩

5. なぜこれ(101010000010010)を使うのかの結論には至りませんでした。知っている人は教えてくれると助かります。 ↩

6. 最初は「丸をつけたところはbit反転」の予定でしたが、半数以上はbit反転するので見やすさ重視のため逆にしました。 ↩