1. 概要
現実で使われている QRコード作成ライブラリpython での人気の実装(githubで2000近いスター)である python-qrcodeのコードを読んだ結果を共有します。
QRコードのざっくりとした仕様と作り方を知っている人向けです。知らない人はいきなりコードを読むのではなく以下のサイト等で概要をつかんでおくとよいです（本当は仕様書とか読むべきなのだろうけど有料なので・・）
- 『ＱＲコードをつくってみる』: http://www.swetake.com/qrcode/qr1.html
2. コードのツリー構造
大したコード量ではないので全部読んでもよいのだけれど、一応構造を共有します:
-
main.py: ファイル名から想像する以上に実装に踏み込んでいます。具体的にはQRCodeという最も重要で上位概念であるクラスを定義・実装しています。 -
util.py: 名前の通り各種ユーティリティ関数(例: 入力に対してベストフィットなサイズを探すことや、フォーマット情報のBCHによる誤り訂正符号の生成など)を集めています。また、QRコードではバイト列単位で操作をしますが、モジュールに書き出すときはビット列になります。そこら辺の界面をしっかりやってくれるBitBufferというクラスも定義しています。 -
base.py: 数学的なのはここにまとまっています。GF256上の演算と、GF256を係数に持つ多項式のクラスを定義します。 -
constant.pyおよびLUT.py: 定数を集めたものですが、正直あまり一貫性を感じません（util.pyやmain.pyの冒頭でも定数を定義してたりするので）。ここに記載されているのはファイルをまたいで参照されるのでしょうか？？なお、LUTはルックアップテーブルの略としているようです。リードソロモン符号における生成多項式の一覧が格納されています。 -
image/: 出力先が 画像(PILライブラリとpymagingライブラリの2種)・SVGが選べるのですが、抽象クラスBaseImageの子クラスとして実装しています。
上記以外は本質とずれているので読まなくても何とかなります。
3. コードリーディング！
3-1. QRコード作成の難所
私がQRコードを1から作ってみたときに厄介だなあと思ったのは以下のような点です。コードを読むときの手がかりになります。本章の節の構成とも対応付きます。
- 誤り訂正符号の作成
- データ本体にはリードソロモン符号を採用し、形式情報とタイプ情報には BCH符号を使います。どのように効率よく実装されているのかが気になります。
- モジュール上への配置
- ご存知の通りQRコードは結構複雑な形をしています。2次元のlistでビット列を表すとすると、どの順番に格納するのか自明ではありません（アライメント等の場所の配置を含め）。複数のバージョンのモジュールをどのように処理しているのかに興味があります。
- マスクとロス関数の実装
- あまりQRコード重要なファクターではないのですが、どのXORマスクを使うのかを動的に決める必要があります。（適当に決め打ちしてもよいので）結構実装をサボられがちな部分だし、実装が相当めんどくさいこともあり、どのように実装しているのか気になります。
以上3点をコードリーディングの目標と定め、本稿を構成します。
3-2. コードを読む前に
上記の観点で読む前に python-qrcode の実装のアウトラインを記載しておくのは有用でしょう。記述の妥当性は あなたに判断してもらいたいですが、何もないよりもスケッチがあった方がよいと思います。
main.pyでのQRCodeクラスが最重要です。box,borderといった画像の見た目上のプロパティや、version, error_correction のような形式に関わるプロパティ、そして modules という二次元list構造, data_list という（モジュールに配置すべき）バイト列を保持するプロパティなどから構成されます。特に data_listというのは 格納すべきデータ(URLとか）を圧縮効率のため分割することができるので、QRData のリストという形で保持していることに注意します（後述）。典型的には、 QRCodeをnewして、add_dataメソッドでURLなどの情報を更新し makeメソッドで、modulesにタイミングパターンを構築したり(setup_**メソッド)、上述のdata_listを構築したり、make_image で画像の書き出しをします。
util.pyで定義されるQRDataというのはまさに URLなどの文字列（もしくは 上位モジュールが分割した結果の部分文字列）です。dataというプロパティに元の文字列が格納されています。writeというメソッドを持ち、BitArray（前述）に符号化されたdataを書き込むという形で使われます。URLのような8bitモードではほとんど何もしないに等しいのですが、英数字モードでは2文字をセットに1byteにするという特有の処理が挟まります。
3-3. 誤り訂正符号の作成
リードソロモン符号です。読み始めるのは util.py の create_data関数です。上位モジュールからの呼ばれるI/Fで 書き込むバイト列とバージョンとエラー訂正レベルが与えられるので、適当にRSブロックに分割して誤り訂正符号を作成し、メタなビットや埋め草ビットを配置するなどのアライメントをして呼び出し元にバイト列として返します。
ただ、誤り訂正符号の実装本体はむしろ create_data によって呼ばれる create_bytes の方です。入力バイト列をビット列にした buffer と rsブロックの一覧である rs_blocks が入力から与えられるので、ブロックごとに適切な生成多項式を選択し、誤り訂正符号を作成し、インターリーブしながら出力を構築します。ざっくりいって以下の役割分担です
-
create_data: お膳立てとビットアライメント -
create_bytes: 誤り訂正符号の作成
GF(2^8)を係数に持つ多項式は base.py の Polynomial で定義されています。__mod__やその他の演算子が定義されているので、以下のように直観的な記述で剰余多項式すなわち誤り訂正符号が計算できます:
#.. 前略 ..
#注:第二引数は x^n を掛けることに相当。 I(x)x^n という式を生成することに相当
rawPoly = base.Polynomial(dcdata[r], len(rsPoly) - 1)
modPoly = rawPoly % rsPoly
有限体での演算の定義を見てみましょう。base.py です。バイト型n をGF256 でも n で表します。つまりヌル文字は 0 と対応させ "a" という文字は 94 に対応付けます。二進表示したときに1byteは8bitとなり256個の数を表現できますが、それが有限体の標数です（αのベクトル表現がバイトnと対応付けるということです）。
GF256での演算を定義するには実質的に $\alpha^i \cdot \alpha^j = \alpha^k$ となる $k$ を探すことと、$n + m = \alpha^k$ となる $k$ を探すという演算に還元できるので、モジュールの先頭で EXP_TABLE, LOG_TABLE として、一気に計算しています。この二つがあれば、GF256を係数とする多項式の加算・乗算・剰余算は簡単に定義できます(Polynomialクラスの__mul__,__mod__)。
フォーマット情報はBCHによる誤り訂正符号ですが、これは簡単なので、base.py ではなく util.py で数行で実装されています (生成多項式は G15とG18。符号化は BCH_type_info と BCH_type_number)
3-4. モジュールへのデータ配置
QRCodeオブジェクトの modulesプロパティが2次元のlistという構造を持ち、modules[row][col]という形で座標を指定したデータを入れることが目的になります。最初にモジュール全体を None で初期化し、位置合わせパターンとかの定型は setup_* というメソッドで動的に値を True/Falseで埋めて、データ部は map_data というメソッドで値を埋めます。
setup_*なメソッドはシンプルながらも動的にモジュールを作成・埋める方法として勉強になります。
map_dataがポイントでしょう。幅2でデータを埋めるので、rangeのintervalは-2になります。またx=6にある縦のタイミングパターンで内部的なインデックスを調整します。このことで奇数幅のモジュールを偶数幅の帯で巡ることができます:
for col in six.moves.xrange(self.modules_count - 1, 0, -2):
if col <= 6:
col -= 1
3-5. マスクとロス関数の実装
util.py の lost_lost_point に実装があります。インターネット上にあまりこの辺をきちんと書いている文書がないのでこの実装を参考にしたい。