QRコード作成 pythonライブラリ python-qrcode を読む

# 1. 概要
現実で使われている QRコード作成ライブラリpython での人気の実装(githubで2000近いスター)である `python-qrcode`のコードを読んだ結果を共有します。

- https://github.com/lincolnloop/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__`やその他の演算子が定義されているので、以下のように直観的な記述で剰余多項式すなわち誤り訂正符号が計算できます:

```create_bytes.py
#.. 前略 .. 
#注:第二引数は 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にある縦のタイミングパターンで内部的なインデックスを調整します。このことで奇数幅のモジュールを偶数幅の帯で巡ることができます:

```py
        for col in six.moves.xrange(self.modules_count - 1, 0, -2):
            if col <= 6:
                col -= 1
```

## 3-5. マスクとロス関数の実装
util.py の `lost_lost_point` に実装があります。インターネット上にあまりこの辺をきちんと書いている文書がないのでこの実装を参考にしたい。