LoginSignup
63
80

More than 3 years have passed since last update.

@bellbind

JavaScriptで実装してみるQRコードジェネレータ

Last updated at Posted at 2020-04-25

「有限体のプログラミング」での応用例として、リードソロモン符号とBCH符号のしくみを取り上げました。

その中では、このリードソロモン符号とBCH符号を両方使っている例として、QRコードに触れました。

そこで、有限体のプログラミングの知識を元に、実際にQRコード画像ジェネレータを、ライブラリ等は用いずに、JavaScript実行環境にある標準機能だけでコードを実装してみました。

A. QRコード仕様の情報源

QRコードの各機能の実装で参考にした記事は、"QR Code Tutorial"でした。
この記事では、説明の中にデータ値の実例が省略されずに載っており、実装した動作の確認に使えます。
そして、仕様上のサイズなどの定数値のデータ全部の表があるので、どのようにパラメータを設計するのがよいかの判断ができます。

次に、実装で生成してみた画像が認識可能かどうかを判断する手段として、ZXing TeamのAndroid版「QRコードスキャナー」を使いました。

最近はアップデートされておらずAndroid10では横画面固定だったりしますが、SJISエンコードもUnicode emojiも含め、長文全体の読み取り表示が可能でした。

また、QRコードの仕様書として、以下のURLにあるページの内容も参照しました。

この仕様文を読むには、バーコードやSJIS等についての知識が必要かもしれません。


参考: QRコードと特許

特許について｜QRコードドットコム｜株式会社デンソーウェーブより、

JIS/ISOの規格に準拠したQRコードは誰でもご自由にお使いいただけます。規格から逸脱したQRコードの使用をご検討される場合は、事前にデンソーウェーブまでご相談ください。

とあるように、X0510規格に従ったQRコードを扱うのでなければ、各特許への確認が必要となるでしょう。

QRコードそのものの特許は、「二次元情報コード」、「二次元コード」、「2次元コード」がキーワードのようです。

これとは別に、たとえば、多色刷りで絵に見えるようなQRコードを作ることは規格準拠で読み取り可能なものではあっても、他の特許に関与する可能性があるかもしれません。
実際、特許検索で「QRコード」で検索すると、2000件以上ヒットします。「色」や「デザイン」等の単語と合わせて検索するとよいかもしれません。


参考ですが、iOSやAndroidでは、WebのURL以外にも、QRコード文字列の特定パターンの解釈をすることで、アドレス帳やWIFI接続など、いくつかの応用が組み込まれています。以下のzxingのwikiページに、その応用例が解説されています:

B. この記事中のJavaScriptプログラムについて

主題のJavaScriptモジュール、および、モジュールのデモ実行用のHTMLやJSコードもふくめ、すべて、以下のgistにおいてあります:

gist URLのQRコード

コードのECMAScript仕様は、Array.flatMapのあるECMAScript2019仕様であり、.jsファイルはすべてES module形式です(モジュールが.mjsでない理由はリンク先参照)。

モジュール実装では、ECMAScriptビルトイン以外には、console.logとconsole.assert、および、Web標準のTextEncoderとTextDecoderのみを使用しています。
また、TextDecoderの"shift_jis"デコード実装も使用しています。

  • 注: TextEncoderはutf-8のみ対応へと制限されたが、TextDecoderはいまでもutf-8以外にも対応できる
  • 参考: TextDecoderの"shift_jis"デコードは、Chrome, Firefox, Safariで有効。nodejsではfull-icuが必要で、nodejs-13以降はデフォルトで対応。denoではICU自体に非対応

ただし、各HTML example内では、GUI構築のために、DOMやCanvas 2D、MediaDevicesなども使用しています。

このモジュール実装を用いたブラウザ実行アプリケーション例のQRコードジェネレータGUIは以下のリンク先になっています。

実装例1は、ボタンを押したときにフォーム中のテキストをQRコード化していくタイプです。実装例2は以下の画像のUIで、入力が変化するたびにQRコードを更新していくタイプとなっています。どちらもQRコード部分をクリックすることでPNG画像で保存できるようにしてあります。

qrcode-generator2.htmlの画面

C. QRコード関連用語集

C.1. QRコード全般の用語

  • モデル: 新旧QRコード仕様のこと
    • 注: モデル2仕様が、一般的に呼ばれる「QRコード」のこと
  • モジュール/セル: QRコード画像内の正方形1つのこと。黒が1で白が0のビット値に対応。QRコードモデル2では、縦横のセル数は同じ数である。
  • エラー訂正レベル/品質: QRコード内のパリティデータの量の目安。低品質から並べて"L"、"M"、"Q"、"H"の4つ。品質が上がるほど埋め込めるテキストデータ量は少なくなる
  • バージョン/型番: QRコードの縦横セル数のバリエーション。1から40までの40種あり、21セルから177セルまで、バージョンが1上がるごとに縦横4セルづつ長くなる
  • マスク: 埋め込むデータの0と1は、そのままセルに埋めるのではなく、セル位置に応じたマスクパターンのマスクビットとXORした値が埋め込まれる。 マスクの種類は、IDが0から7までの8種
  • フォーマット/形式: エラー訂正レベルのIDとマスクのIDをあわせた、4x8=32パターンの情報

C.2. QRコード画像関連の用語

  • クワイエットゾーン/余白: QRコードでは、白余白として、上下左右それぞれ4セル分づつ開けるのが仕様。ただし、QRコード生成時は、余白部分はないものとして処理する。
  • パターン: QRコード画像内に、データとは関係なく固定的に埋め込まれるセル。 「ファインダー」、「アラインメント」、「タイミング」の３つ、と左下ファインダーの右上の1黒モジュールの4種。
    • ファインダーパターン: 「白:黒:白:黒黒黒:白:黒:白」が縦横のの正方形の大きな目玉。左上、右上、左下、の3箇所にある。 画像がQRコードであること、QRコードの傾き、目安のセル幅を認識するために用いる。
    • タイミングパターン: 左上と左下、左上と右上の、ファインダーの黒角同士をつなぐ黒白交互の破線
    • アラインメントパターン: 「黒:白:黒:白:黒」が縦横のの正方形の小さな目玉。画像の位置補正で使用する -注: バージョン1のみ、アラインメントは1つもない。また、バージョン2から6までは右下に一つあり、以降7バージョンごとに、画像内のアラインメントの個数が増える
  • フォーマット領域: ファインダーパターンのすぐ外の枠。15セルが2箇所。フォーマット情報が得られなければ、データ部分のパーズはできない。
  • バージョン領域: バージョン7より、右上ファインダーの直左と、左下ファインダーの直上に埋め込まれる領域。18セルが2箇所。
  • 符号化領域/コード領域: 各パターンとフォーマット領域とバージョン領域を除いた全てのセル。テキストのデータとそのパリティデータが埋め込まれる。

QRコード用語

C.3. QRコードのデータ関連の用語

  • 符号化モード: テキストデータのビット列パッキング時のタイプ。1QRコード内で、複数種を混ぜて埋め込める。4ビットの値で表現
    • データ用モード: 数字(0001)、英数(0010)、JIS漢字(0100)、バイト列(1000)の4つと終端マーク(0000)
    • 制御用モード: ECIモード(0111)、 FNC1モード(0101,1001)、連結モード(0011)
    • 独自拡張モード: GB漢字(1101)
  • 数字: 0から9までの文字10種
  • 英数: 数字と大文字、半角空白と$%*+-./:の45文字種のみ。小文字は含まない。
  • JIS漢字: SJISで2バイトコードになる文字(JIS X 0208)
    • 注: SJISで1バイトなASCIIと半角カナは含まず、全角英数キリルかな記号は含む
  • バイト列: 任意のバイト列
    • 注: 多くのQRコードスキャナー実装では、バイト列データはUTF-8テキストと解釈する
  • ECI(バーコードの仕様): 後続のバイト列のエンコードタイプを表す識別値
  • FNC1(バーコードの仕様): バーコードのファンクションコード
  • 連結: 各QRコードの分割位置(4ビット)と分割数(４ビット)、パリティデータ(未分割の全文字データのバイト値でのXOR値8ビット)が続く。連結データ20ビットは全データの先頭3バイト内に置く。
    • 参考: 5分割中3盤目の連結データは、0011,0010,0100,XXXXXXXXとなる(順序や分割数は1引いた値。最後尾8ビットは全文字のXOR値)

  • パディング/埋め草: バイト単位で埋め込めるデータ領域が余るときに、埋め込まれる繰り返しの特定のバイトパターン(11101100,00010001)

  • 符号化データ: テキストのパッキングとパディングを行ったデータ

  • パリティデータ: エラー検出・訂正のために追加されるデータ

  • コードワード/符号語: 符号化データとパリティデータをあわせた、QRコードに埋め込まれるデータ

  • コードブロック: パリティデータを計算する単位となる、符号化データを分割したバイトチャンク。
    バージョンとエラー訂正レベルごとに、パリティサイズ、チャンクサイズとブロック個数が定義されている

C.4. エラー訂正符号の用語

  • リードソロモン符号/RSコード: 埋め込みデータで用いるエラー訂正可能符号システム
  • BCH符号/BCHコード: フォーマット領域で用いる15ビットのエラー訂正可能符号システム
  • 拡張BCHコード: バージョン領域で用いる18ビットのエラー訂正可能符号システム
  • エラー訂正率: エラー訂正レベルのエラー訂正率とは、1ブロック内での訂正可能バイト数の比率
    • 注: 1バイトを構成する8セル中のうち1セルでもエラーなら、8セルすべてエラー値扱いになる

０. QRコード実装オーバービュー

「有限体のプログラミング」が前提にあるため、"QR Code Tutorial"の順序とは違う順で実装しています。

具体的には、以下の順番で実装しています。

  1. 有限体と多項式の実装: qrgf.js
  2. リードソロモン符号の実装: qrrscode.js
  3. ビッグエンディアン型のビットストリームの実装: bitstream.js
  4. Unicode-SJISマッピング: cp2sjis.js
  5. 各種テキスト形式のビット列パッキング実装: qrdata.js
  6. パリティ計算および画像埋め込みデータ形式の実装: qrmessage.js
  7. 空フレーム画像生成の実装: grframe.js
  8. マスク付きデータ埋め込みの実装: qrencode.js
  9. マスク性能評価関数の実装: qrevaluation.js
  10. フレームデータのSVG化およびImageData書き込みの実装: qrimagedata.js
  11. データからのフレーム選択およびA*アルゴリズムによる自動パッキングの実装: qrauto.js
  12. QRコード生成ライブラリAPI: qrcode.js
  13. フレーム画像からテキストを取り出すデコーダー: qrdecode.js

このうち、cp2sjis.jsまではQRコード実装のための汎用技術を実装したライブラリであり、QRコード固有の仕組みに入るのはqrdata.jsからになります。

これらのESモジュールのjsファイル全部あわせて、空行含めて1200行くらいでした。

また、QRコードスキャナ用として、以下のコードも実装してみました。

キャプチャの実装では、ファインダーと右下のアラインメント1つだけを検出して補正する簡易なものです。
しかし、前述のモジュールのどれよりも大きな330行ほどになってしまいました。

以降は、各モジュール実装で、ポイントとなる部分にフォーカスして説明します。

1.a. 有限体と多項式の実装


コード: qrgf.js
qrgf.js
// Tiny GF2n and Polynomial
export const range = n => [...Array(n).keys()];

export const PF2Poly = () => {
  const order = e => Math.max(0, 31 - Math.clz32(e));
  const neg = e => e;
  const add = (a, b) => a ^ b;
  const sub = (a, b) => a ^ b;
  const carry = (e, k) => e << k;
  const mul = (a, b) => {
    let r = 0;
    for (; b > 0; b >>>= 1, a <<= 1) if (b & 1) r ^= a;
    return r;
  };
  const mod = (a, b) => {
    const ma = order(a), mb = order(b);
    for (let i = ma - mb, m = 1 << ma; i >= 0; i--, m >>>= 1) {
      if (a & m) a ^= b << i;
    }
    return a;
  };
  const times = (e, k) => k % 2 === 0 ? 0 : e;
  return {order, neg, add, sub, carry, mul, mod, times};
};

export const GF2n = (n, f) => {
  const poly = Object.freeze(PF2Poly());
  const pn = 2 ** n, pn1 = pn - 1;
  const modpn1 = k => (pn1 + k % pn1) % pn1;

  const zero = 0, one = 1, a = 2, isZero = e => e === 0;

  const {add, sub, neg, times} = poly;
  const sum = es => es.reduce((r, e) => add(r, e), zero);
  const mul0 = (a, b) => poly.mod(poly.mul(a, b), f);

  const powList = [one];
  for (let i = 1; i < pn1; i++) {
    powList.push(mul0(powList[powList.length - 1], a));
  }
  const expoList = range(pn).map(e => e === 0 ? NaN : powList.indexOf(e));

  const exponent = e => expoList[e];
  const mul = (a, b) => a === 0 || b === 0 ? 0 :
        powList[modpn1(exponent(a) + exponent(b))];
  const pow = (e, k) => e === 0 ? 0 : k === 1 ? e :
        powList[modpn1(exponent(e) * k)];
  const inv = e => e === 0 ? NaN : powList[modpn1(-exponent(e))];
  const div = (a, b) => b === 0 ? NaN : a === 0 ? 0 :
        powList[modpn1(exponent(a) - exponent(b))];
  const alpha = (k = 1) => pow(a, k);

  return {
    n, f, pn, neg, zero, one, a, isZero,
    add, sub, times, sum, mul, pow, inv, div, exponent, alpha,
  };
};

// Polynomial as reversed array 
export const Polynomial = K => {
  // convert index and order
  const deg = (e, i) => i < 0 ? 0 : e.length - 1 - i;

  const zero = Object.freeze([K.zero]), one = Object.freeze([K.one]);
  const add = (a, b) => {
    const [A, B] = a.length >= b.length ? [a, b] : [b, a];
    const offs = A.length - B.length;
    return A.map((c, i) => i < offs ? c : K.add(c, B[i - offs])); 
  };

  const neg = e => e.map(c => K.neg(c));
  const scale = (e, c) => e.map(ci => K.mul(ci, c));
  const sub = (a, b) => add(a, neg(b));
  const sum = es => es.reduce((r, e) => add(r, e), zero);
  const carry = (e, k) => e.concat(Array(k).fill(K.zero));
  const mul = (a, b) => sum(b.map(
    (bi, i) => carry(scale(a, bi), deg(b, i))));
  const prod = es => es.reduce((r, e) => mul(r, e), one);
  const order = e => deg(e, e.findIndex(ek => !K.isZero(ek)));
  const mod = (a, b) => {
    const ma = order(a), mb = order(b);
    if (ma < mb) return a.slice(-mb);
    const f = K.div(a[0], b[0]);
    return mod(sub(a, carry(scale(b, f), ma - mb)).slice(1), b);
  };
  const coef = (e, k) => e[deg(e, k)] || K.zero;
  const monomial = (c, k) => carry([c], k);
  const diff = e => e.map((c, i) => K.times(c, deg(e, i))).slice(0, -1);
  const apply = (e, v) => K.sum(
    e.map((c, i) => K.mul(c, K.pow(v, deg(e, i)))));

  return {
    K, zero, one, neg, scale, add, sub, sum, carry, mul, order, mod, prod,
    coef, monomial, diff, apply,
  };
};


qrgf.jsでは、

  • ビット列にマッピングしたモジュロ2係数値の多項式実装PF2Polynomial
  • 2のべき乗要素数の有限体GF($2^n$)実装GF2n、
  • 係数配列にマッピングする多項式実装Polynomial

を実装しています。
これらは、「有限体のプログラミング中編: JavaScriptで実装する有限体」のものからQRコードで使う部分を抜粋したものです。
ただし、Polynomialのみ、リンク先の実装とは違い、リードソロモン符号に合わせた、変数の指数値と配列のインデックスが逆順になる形式で実装しています。

PF2Polynomialは、GF2n内だけではなく、モジュロ2係数多項式として、BCHコードや拡張BCHコードの符号化(エンコード)でも用います。


参考: QRコードにおけるBCHコードと拡張BCHコードのデコード

QRコードでのBCHコードや拡張BCHコードのデコードでは、リードソロモン符号でのエラー位置計算はせずに、符号訂正ができます。
QRコードでは、フォーマット32個やバージョン34個(注: バージョン6まではバージョン領域が存在しない)の符号データ全パターンを列挙したうえで、その中からハミング距離が一番小さいものを選ぶ、という手段が利用できます。

  • 多項式でのハミング距離: 係数値の違う項の個数
  • ビット列でのハミング距離: XORした結果の1の個数: popcnt(xor(a, b))


1.b. リードソロモン符号の実装


コード: qrrscode.js
qrrscode.js
const range = n => [...Array(n).keys()];

export const findLinearRecurrence = (poly, s) => {
  // Berlekamp-Massey algorithm
  // NOTE: s as [s0, s1, ...]
  const {K, one, add, sub, scale, carry, mul, coef} = poly;
  let cx = one, cl = 1, bx = one, bl = 1, b = K.one, m = 0;
  for (let i = 0; i < s.length; i++) {
    const d = K.sum(range(cl).map(k => K.mul(coef(cx, k), s[i - k])));
    m++;
    if (K.isZero(d)) continue;
    const tx = cx, tl = cl;
    cx = sub(cx, scale(carry(bx, m), K.div(d, b)));
    cl = Math.max(cl, bl + m);
    if (cl > tl) [bx, bl, b, m] = [tx, tl, d, 0];
  }
  return cx;
};

export const RSCode = (poly, d, b = 0) => {
  const {
    K, add, sub, carry, mul, mod, sum, prod, monomial, apply, diff} = poly;

  const gen = prod(range(d).map(
    k => add(monomial(K.one, 1), monomial(K.alpha(b + k), 0))));
  const parity = msg => mod(carry(msg, d), gen);

  const decode = rx => {
    const N = rx.length;
    // NOTE: synds as [s0, s1, ...]
    const synds = range(d).map(k => apply(rx, K.alpha(b + k)));
    if (synds.every(si => K.isZero(si))) return rx;

    const lx = findLinearRecurrence(poly, synds);
    if (lx.length - 1 > (d >>> 1)) throw Error(
      "RSCode.decode: too many errors");
    // NOTE: positions as power of a: index of cx as cx[N - 1 - k]
    const pos = range(N).filter(k => K.isZero(apply(lx, K.alpha(-k))));

    const sx = sum(synds.map((sk, k ) => monomial(sk, k)));
    const ox = mod(mul(sx, lx), monomial(K.one, d));
    const dlx = diff(lx);
    // NOTE: errors index is same as positions index (not array index)
    const errors = pos.map(k => {
      const akinv = K.alpha(-k);
      const oAkinv = apply(ox, akinv);
      const dlAkinv = apply(dlx, akinv);
      const ak1b = K.alpha(k * (1 - b));
      return K.neg(K.mul(ak1b, K.div(oAkinv, dlAkinv)));
    });
    const ex = sum(pos.map((k, i) => monomial(errors[i], k)));
    return sub(rx, ex);
  };

  return {poly, b, d, gen, parity, decode};
};


qrrscode.jsは、qrgf.jsのPolynomialとGF2nを使用するリードソロモン符号RSCodeの実装モジュールです。
リードソロモン符号の仕組み全体は、「有限体のプログラミング後編: リードソロモン符号のしくみ」で説明してあります。

ただしこの実装では、エラー位置方程式の導出では、連立方程式を解くPGZアルゴリズムではなく、よりコード量の少ないBerlekamp-Masseyアルゴリズムを使用しました。
このBerlekamp-Masseyアルゴリズムについては、「有限体のプログラミング中編: JavaScriptで実装する有限体」の多項式ユーティリティの章で、「数列が満たす線形漸化式の係数を求める関数findLinearRecurrence」として説明しています。

QRコード実装で使いやすいよう、RSCodeのパラメータでは、(符号長Nとデータ長Kではなく、)パリティ長dを指定するようにし、また、エンコード機能ではパリティデータだけを返すparity()を提供するようにしてあります。

  • 参考: リードソロモン符号では、dの半分以下のエラー出現数であれば訂正可能
  • 注: エラー数が訂正可能数より多く起これば、訂正失敗、もしくは、誤訂正される(誤訂正かどうかは、リードソロモン符号上では検出不可能)

2. ビッグエンディアン型のビットストリームの実装


コード: bitstream.js
bitstream.js
// big endian bit stream
export class BitWriter {
  constructor(buf = [], byte = 0, pos = 7) {
    this.byte = byte;
    this.pos = pos;
    this.buf = Array.from(buf);
  }
  writeBit(b) {
    this.byte |= (b & 1) << this.pos;
    this.pos--;
    if (this.pos < 0) {
      this.buf.push(this.byte);
      this.byte = 0;
      this.pos = 7;
    }
  }
  write(value, n) {
    for (let i = n - 1; i >= 0; i--) this.writeBit((value >>> i) & 1);
  }
  writeBytes(bytes) {
    if (this.pos < 7) {
      this.buf.push(this.byte);
      this.byte = 0;
      this.pos = 7;
    }
    for (const v of bytes) this.buf.push(v);
  }
  toBuffer() {
    const bytes = this.buf.slice();
    if (this.pos < 7) bytes.push(this.byte);
    return new Uint8Array(bytes);
  }
  bitLength() {
    return this.buf.length * 8 + (7 - this.pos);
  }
  byteLength() {
    return this.buf.length + (this.pos === 7 ? 0 : 1);
  }
}

export class BitReader {
  constructor(buf, index = 0, pos = 7) {
    this.buf = Uint8Array.from(buf);
    this.index = index;
    this.pos = pos;
  }
  isEnd() {
    return this.index >= this.buf.length;
  }
  canReadBits(n) {
    const finished = this.index * 8 + 7 - this.pos;
    return finished + n <= this.buf.length * 8;
  }
  readBit() {
    if (this.isEnd()) throw Error(`no enough bytes`);
    const b = (this.buf[this.index] >>> this.pos) & 1;
    this.pos--;
    if (this.pos < 0) {
      this.pos = 7;
      this.index++;
    }
    return b;
  }
  read(n) {
    let r = 0;
    for (let i = n - 1; i >= 0; i--) r |= this.readBit() << i;
    return r;
  }
  readBytes(n = 1) {
    // drop incomplete reading byte
    if (this.pos < 7) {
      this.index++;
      this.pos = 7;
    }
    if (this.index + n > this.buf.length) throw Error(`no enough bytes`);
    const slice = this.buf.slice(this.index, this.index + n);
    this.index += n;
    return slice;
  }
}


bitstream.jsでは、バイト列へ1ビットづつ書き込むBitWriterと、バイト列から1ビットづつ読み込むBitReaderの実装をしています。

この注意点は、バイト内でのビットオーダー (ビットの読み書き順序)です。
QRコードでは、ビッグエンディアンとかMSBファーストとか呼ばれるオーダーが採用されます。
つまり、上位ビットから読み書きをするタイプのビット列になります。

たとえば、4ビット0100を空白のバイトへ書き込むと、結果のバイトは0100XXXXとなります。これは入力値を0,1,0,0の順に読み込んで、バイトの上位から詰めていくことに相当します。
この次に2ビット11を書き込むと、010011XXとなります。


参考: リトルエンディアン/LSBファーストなビット列

リトルエンディアン/LSBファーストなら、0100は0,0,1,0の順に読み込み、バイトの下位から書き込むので、XXXX0100となり、つぎに11を書き込むとXX110010になります。
たとえば、zlibのdeflate/infrateでは、このLSBファーストなビット列を採用しています。

読み書きのビットオーダーが一致していれば、1つのビット列を書き込んだ結果のビットの左右の位置関係も変わりません。しかし、複数のビット列を書き込んだときの並びには違いが現れます。

読み込み順とビット位置が同じであることからLSBファーストのほうが実装は若干楽ですが、MSBファーストは後に書き込んだビット列がバイト内でも右に来るので表示面では若干わかりやすくなります。


3. Unicode-SJISマッピング実装


コード: cp2sjis.js
cp2sjis.js
const t = new Map(),  rev = new Map();
export const has = c => t.has(c);
export const get = c => t.get(c);
export const toChar = j => rev.get(j);

try {
  const td = new TextDecoder("shift_jis", {fatal: true});
  const dv = new DataView(new ArrayBuffer(2));
  const putSjis = code => {
    dv.setUint16(0, code, false);
    try {
      const ch = td.decode(dv);
      t.set(ch, code);
      rev.set(code, ch);
    } catch (err) {}
  };
  for (let code = 0x8140; code <= 0x9ffc; code++) putSjis(code);
  for (let code = 0xe040; code <= 0xebbf; code++) putSjis(code);
} catch (error) {
  console.info("[INFO] cp2sjis.js depends on SJIS supported TextDecoer, but");
  console.info(error);
}


QRコードの漢字モードに対応するには、以下の機能が必要です。

  • string中の文字がSJIS漢字文字かどうかの判定: has(ch)
  • SJIS漢字文字から、SJISコードを得る: get(ch)
  • (SJISコードから、Unicode文字を得る: toChar(sjis))

(最後の機能はデコード時に必要)。

いずれの機能も、SJISコードとUnicode文字のマッピングテーブルが必要になります。

SJISデコード機能を持つ他のプログラミング言語を用いて、テーブルをオフラインで生成することもできますが、対象のJIS X 0208文字は約8000文字あるので、JavaScriptコードにシリアライズすると100KBを超える量になってしまいます。

このcp2sjis.js実装ではコード量を優先し、JavaScriptランタイム上でモジュールロード時にマッピングテーブルを生成する手段を採用しました。

Web標準APIのTextDecoderを用い、SJISコードの範囲のSJISコード値すべてを一つづつデコードをしてみて、失敗しなければテーブルに登録する、という手法です。
(この手法はオフライン生成の場合でも同様で、生成したテーブルをJavaScriptコードとしてシリアライズするかどうかの違いです。)


cp2sjis.js事前生成プログラム: gen-cp2sjis.js
gen-cp2sjis.js
// $ node gen-cp2sjis.js > cp2sjis.js
try {
  const td = new TextDecoder("shift_jis", {fatal: true});
  const dv = new DataView(new ArrayBuffer(2));
  const t = [];
  const putSjis = code => {
    dv.setUint16(0, code, false);
    try {
      const ch = td.decode(dv);
      t.push([ch, code]);
    } catch (err) {}
  };
  for (let code = 0x8140; code <= 0x9ffc; code++) putSjis(code);
  for (let code = 0xe040; code <= 0xebbf; code++) putSjis(code);
  const entries = t.map(
    ([ch, code]) => `["\\u{${ch.codePointAt(0).toString(16)}}", ${code}]`
    //kv => JSON.stringify(kv)
  ).join(",");
  console.log(`
const t = new Map([${entries}]),  rev = new Map();
for (const [ch, code] of t) rev.set(code, ch);
export const has = c => t.has(c);
export const get = c => t.get(c);
export const toChar = j => rev.get(j);
`);
} catch (error) {
  console.info("[INFO] cp2sjis.js depends on SJIS supported TextDecoer, but");
  console.info(error);
}

生成したJavaScriptコードは、136KBになりました。
Unicodeエスケープ表現を使わずに、JSON.stringifyで漢字を埋め込めば、95KBになります。



参考: UnicodeとSJISの関係

UnicodeとSJISコードとの対応づけは、Unicode側で定義されています。

以下のURLにあるUnicode Dataファイル内にUnicode-SJISマッピングが記述されたファイルが存在しています。


4. 各種テキスト形式のビット列パッキング実装


コード: qrdata.js
qrdata.js
import * as cp2sjis from "./cp2sjis.js";

// utilities
export const range = n => [...Array(n).keys()];
export const chunking = (a, n) => range(Math.ceil(a.length / n)).map(
  i => a.slice(i * n, (i + 1) * n));

// data length varied by version
const lengthBitTable = [
  // version: 1<=>9, 10<=>26, 27<=>40
  [10, 12, 14], // Numbers
  [ 9, 11, 13], // AlphaNums
  [ 8, 16, 16], // Bytes
  [ 8, 10, 12], // Kanjis
];
const maxLengthTable = lengthBitTable.map(l => l.map(b => 2 ** b));

export const lengthBit = (mode, version) => {
  console.assert(1 <= version && version <= 40, "invalid version", version);
  return lengthBitTable[mode][version <= 9 ? 0 : version <= 26 ? 1 : 2];
};
export const maxLength = (mode, version) => {
  console.assert(1 <= version && version <= 40, "invalid version", version);
  return maxLengthTable[mode][version <= 9 ? 0 : version <= 26 ? 1 : 2];
};

// 0. terminateor
export const addTerminator = (bitwriter) => {
  bitwriter.write(0, 4);
  return bitwriter;
};
export const bitTerminator = () => 4;
// last padding
export const addPads = (bitwriter, totalLength) => {
  const pad = totalLength - bitwriter.byteLength();
  bitwriter.writeBytes(range(pad).map(k => (k & 1) ? 0b00010001 : 0b11101100));
  return bitwriter;
};
export const terminateData = (bitwriter, totalLength) => {
  if (totalLength - bitwriter.byteLength()) addTerminator(bitwriter); 
  return addPads(bitwriter, totalLength);
};

// 1. numbers
export const regExpNumbers = (version, least = 1) =>
  RegExp(`^\\d{${least},${maxLength(0, version)}}$`);
export const addNumbers = (bitwriter, version, text) => {
  console.assert(regExpNumbers(version).test(text), "invalid numbers", text);
  bitwriter.write(1 << 0, 4);
  bitwriter.write(text.length, lengthBit(0, version));
  const chunks = chunking(text, 3);
  const last = chunks[chunks.length - 1].length !== 3 ? chunks.pop() : "";
  for (const chunk of chunks) bitwriter.write(+chunk, 10);
  if (last.length === 2) bitwriter.write(+last, 7);
  else if (last.length === 1) bitwriter.write(+last, 4);
  return bitwriter;
};
export const bitNumbers = (version, len) => {
  if (maxLength(0, version) < len) return -1;
  const rem = len % 3, c3 = (len - rem) / 3;
  return 4 + lengthBit(0, version) + 10 * c3 +
    (rem === 2 ? 7 : rem === 1 ? 4 : 0);
};

// 2. alphanums
export const alphaNumTable = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:";
//console.assert(alphaNumTable.length === 45);
export const regExpAlphaNums = (version, least = 1) =>
  RegExp(`^[${alphaNumTable}]{${least},${maxLength(1, version)}}$`);
export const addAlphaNums = (bitwriter, version, text) => {
  console.assert(regExpAlphaNums(version).test(text), "invalid alphanums", text);
  bitwriter.write(1 << 1, 4);
  bitwriter.write(text.length, lengthBit(1, version));
  const chunks = chunking(text, 2);
  const last = chunks[chunks.length - 1].length !== 2 ? chunks.pop() : "";
  for (const chunk of chunks) bitwriter.write(
    45 * alphaNumTable.indexOf(chunk[0]) + alphaNumTable.indexOf(chunk[1]), 11);
  if (last.length === 1) bitwriter.write(alphaNumTable.indexOf(last), 6);
  return bitwriter;
};
export const bitAlphaNums = (version, len) => {
  if (maxLength(1, version) < len) return -1;
  const rem = len % 2, c2 = (len - rem) / 2;
  return 4 + lengthBit(1, version) + 11 * c2 + (rem === 1 ? 6 : 0);
};

// 3. bytes
export const addBytes = (bitwriter, version, text) => {
  const chunks = new TextEncoder().encode(text);
  console.assert(chunks.length <= maxLength(2, version), "invalid length bytes", text);
  bitwriter.write(1 << 2, 4);
  bitwriter.write(chunks.length, lengthBit(2, version));
  for (const chunk of chunks) bitwriter.write(chunk, 8);
  return bitwriter;
};

export const bitBytes = (version, len) => {
  // NOTE: `len` as  byte count (not character count)
  if (maxLength(2, version) < len) return -1;
  return 4 + lengthBit(2, version) + 8 * len;
};

// 4. Kanjis: SJIS 2-byte code numbers except for ASCII, half-width KATAKANA
export const addKanjis = (bitwriter, version, text) => {
  const kanjiArray = [...text].map(ch => cp2sjis.get(ch));
  console.assert(kanjiArray.every(
    c => 0x8140 <= c && c <= 0x9ffc || 0xe040 <= c && c <= 0xebbf) &&
                 kanjiArray.length <= maxLength(3, version));
  bitwriter.write(1 << 3, 4);
  bitwriter.write(kanjiArray.length, lengthBit(3, version));
  for (const c of kanjiArray) {
    const o = c - (c <= 0x9ffc ? 0x8140 : 0xc140);
    bitwriter.write((o >> 8) * 0xc0 + (o & 0xff), 13);
  }
  return bitwriter;
};
export const bitKanjis = (version, len) => {
  // NOTE: `len` as character counts (not byte count)
  if (maxLength(3, version) < len) return -1;
  return 4 + lengthBit(3, version) + 13 * len;
};


ここから、QRコード固有の仕組みの実装に入ります。

qrdata.jsでは、BitWRiterへ、各モードでのテキストのビット列パッキングを行う機能を実装します。

  • addNumbers(bw, version, text)
  • addAlphaNums(bw, version, text)
  • addBytes(bw, version, text)
  • addKanjis(bw, version, text)

QRコードのテキストデータのパッキング形式はすべて、

  • モード(4ビット) | 文字長(モード依存ビット数) | 文字データ(可変長)

の順でならぶビット列として、1つのチャンクデータにパッキングされます。

この文字長は、バイト列モードの場合ではバイト長になります。
文字長につかうビット数は固定ではなく、各モードと各バージョンにより決定されます。

  • 注: 文字長のビット数は各バージョンのレベルLでのQRコードの最大文字数を入れることが十分可能なビット数になっています。

以下は、文字数に対して各モードで必要となる(モード4ビットと文字数部分含む)ビット数を計算する関数です。

  • bitNumbers(version, len)
  • bitAlphaNums(version, len)
  • bitBytes(version, len) (注: lenはバイト数)
  • bitkanjis(version, len)

文字データのビット数は、数字モードは3文字で10ビット、英数モードは2文字で11ビット、漢字モードは1文字13ビットになります。バイト列モードは1バイト8ビットですが、アラインメントで区切らず途中ビットから続けて埋め込みます。

また、qrdata.jsでは、ECIモード、FNC1モード、連結モードは実装していません(ZxingのQRコードスキャナーが非対応で、確認手段がないため)。

BitWriterへの終端のパッキングを行う関数も提供します。

  • terminateData(bw, totalByteLength)

注意点として、終端マーク(0000)は、文字列データを詰め込んだあとで、QRコードに入れられるバイト単位で余るときのみ埋めます。
文字列データだけで、QRコードデータの最後のバイトを、たとえ1ビットでも、使っていれば、終端コードは不要であり、残りは0ビットで埋めます。
そして、パディング(11101100,00010001)は、終端マークを入れた後でも更にバイト単位で残っているときに埋めるものです。

5. パリティ計算および画像埋め込みデータ形式の実装


コード: qrmessage.js
qrmessage.js
import {range, PF2Poly, GF2n, Polynomial} from "./qrgf.js";
import {RSCode} from "./qrrscode.js";

// Reed-Solomon encode on GF(2^8) with a^8+a^4+a^3+a^2+1=0
// - https://www.thonky.com/qr-code-tutorial/error-correction-coding
export const gf = Object.freeze(GF2n(8, 0b100011101));
export const poly = Object.freeze(Polynomial(gf));

// message encode
// - https://www.thonky.com/qr-code-tutorial/structure-final-message
export const quarities = "LMQH";
const blockTable = [
  // each version has at most two block;
  //    parity byte length is same, data length b2 is b1 + 1
  // quarities L/M/Q/H has different parity different block counts
  // - https://www.thonky.com/qr-code-tutorial/error-correction-table
  [[/*L: parity, b1 bytes, b1 count, b2 count,*/], [/*M*/], [/*Q*/], [/*H*/],],
  [[7, 19, 1, 0], [10, 16, 1, 0], [13, 13, 1, 0], [17, 9, 1, 0]],    // 1
  [[10, 34, 1, 0], [16, 28, 1, 0], [22, 22, 1, 0], [28, 16, 1, 0]],  // 2
  [[15, 55, 1, 0], [26, 44, 1, 0], [18, 17, 2, 0], [22, 13, 2, 0]],  // 3
  [[20, 80, 1, 0], [18, 32, 2, 0], [26, 24, 2, 0], [16, 9, 4, 0]],   // 4 
  [[26, 108, 1, 0], [24, 43, 2, 0], [18, 15, 2, 2], [22, 11, 2, 2]], // 5
  [[18, 68, 2, 0], [16, 27, 4, 0], [24, 19, 4, 0], [28, 15, 4, 0]],  // 6

  [[20, 78, 2, 0], [18, 31, 4, 0], [18, 14, 2, 4], [26, 13, 4, 1]],   // 7
  [[24, 97, 2, 0], [22, 38, 2, 2], [22, 18, 4, 2], [26, 14, 4, 2]],   // 8
  [[30, 116, 2, 0], [22, 36, 3, 2], [20, 16, 4, 4], [24, 12, 4, 4]],  // 9
  [[18, 68, 2, 2], [26, 43, 4, 1], [24, 19, 6, 2], [28, 15, 6, 2]],   //10
  [[20, 81, 4, 0], [30, 50, 1, 4], [28, 22, 4, 4], [24, 12, 3, 8]],   //11
  [[24, 92, 2, 2], [22, 36, 6, 2], [26, 20, 4, 6], [28, 14, 7, 4]],   //12 
  [[26, 107, 4, 0], [22, 37, 8, 1], [24, 20, 8, 4], [22, 11, 12, 4]], //13

  [[30, 115, 3, 1], [24, 40, 4, 5], [20, 16, 11, 5], [24, 12, 11, 5]],   //14
  [[22, 87, 5, 1], [24, 41, 5, 5], [30, 24, 5, 7], [24, 12, 11, 7]],     //15
  [[24, 98, 5, 1], [28, 45, 7, 3], [24, 19, 15, 2], [30, 15, 3, 13]],    //16
  [[28, 107, 1, 5], [28, 46, 10, 1], [28, 22, 1, 15], [28, 14, 2, 17]],  //17
  [[30, 120, 5, 1], [26, 43, 9, 4], [28, 22, 17, 1], [28, 14, 2, 19]],   //18
  [[28, 113, 3, 4], [26, 44, 3, 11], [26, 21, 17, 4], [26, 13, 9, 16]],  //19
  [[28, 107, 3, 5], [26, 41, 3, 13], [30, 24, 15, 5], [28, 15, 15, 10]], //20

  [[28, 116, 4, 4], [26, 42, 17, 0], [28, 22, 17, 6], [30, 16, 19, 6]],   //21
  [[28, 111, 2, 7], [28, 46, 17, 0], [30, 24, 7, 16], [24, 13, 34, 0]],   //22
  [[30, 121, 4, 5], [28, 47, 4, 14], [30, 24, 11, 14], [30, 15, 16, 14]], //23
  [[30, 117, 6, 4], [28, 45, 6, 14], [30, 24, 11, 16], [30, 16, 30, 2]],  //24
  [[26, 106, 8, 4], [28, 47, 8, 13], [30, 24, 7, 22], [30, 15, 22, 13]],  //25
  [[28, 114, 10, 2], [28, 46, 19, 4], [28, 22, 28, 6], [30, 16, 33, 4]],  //26
  [[30, 122, 8, 4], [28, 45, 22, 3], [30, 23, 8, 26], [30, 15, 12, 28]],  //27

  [[30, 117, 3, 10], [28, 45, 3, 23], [30, 24, 4, 31], [30, 15, 11, 31]],  //28
  [[30, 116, 7, 7], [28, 45, 21, 7], [30, 23, 1, 37], [30, 15, 19, 26]],   //29
  [[30, 115, 5, 10], [28, 47, 19, 10], [30, 24, 15, 25], [30, 15, 23, 25]],//30
  [[30, 115, 13, 3], [28, 46, 2, 29], [30, 24, 42, 1], [30, 15, 23, 28]],  //31
  [[30, 115, 17, 0], [28, 46, 10, 23], [30, 24, 10, 35], [30, 15, 19, 35]],//32
  [[30, 115, 17, 1], [28, 46, 14, 21], [30, 24, 29, 19], [30, 15, 11, 46]],//33
  [[30, 115, 13, 6], [28, 46, 14, 23], [30, 24, 44, 7], [30, 16, 59, 1]],  //34

  [[30, 121, 12, 7], [28, 47, 12, 26], [30, 24, 39, 14], [30, 15, 22, 41]],//35
  [[30, 121, 6, 14], [28, 47, 6, 34], [30, 24, 46, 10], [30, 15, 2, 64]],  //36
  [[30, 122, 17, 4], [28, 46, 29, 14], [30, 24, 49, 10], [30, 15, 24, 46]],//37
  [[30, 122, 4, 18], [28, 46, 13, 32], [30, 24, 48, 14], [30, 15, 42, 32]],//38
  [[30, 117, 20, 4], [28, 47, 40, 7], [30, 24, 43, 22], [30, 15, 10, 67]], //39
  [[30, 118, 19, 6], [28, 47, 18, 31], [30, 24, 34, 34], [30, 15, 20, 61]],//40
];

export const blockInfo = (version, qi) => blockTable[version][qi].slice();
export const quarityIndex = c => quarities.indexOf(c);
export const codeBytes = (version, qindex) => {
  const [parity, b1data, b1count, b2count] = blockTable[version][qindex];
  return (parity + b1data) * b1count + (parity + b1data + 1) * b2count;
};
export const dataBytes = (version, qindex) => {
  const [parity, b1data, b1count, b2count] = blockTable[version][qindex];
  return b1data * b1count + (b1data + 1) * b2count;
};

export const splitBlocks = (bytes, b1data, b1count, b2count) => {
  const b2data = b1data + 1, b2offs = b1data * b1count;
  const b1blocks = range(b1count).map(
    i => bytes.slice(i * b1data, (i + 1) * b1data));
  const b2blocks = range(b2count).map(
    i => bytes.slice(b2offs + i * b2data, b2offs + (i + 1) * b2data));
  return [...b1blocks, ...b2blocks];
};

export const transpose = m => range(m[0].length).map(i => m.map(l => l[i]));

export const interleaveBlocks = (blocks, b1data, b1count) => {
  const former = transpose(blocks.map(b => b.slice(0, b1data))).flat();
  const latter = blocks.slice(b1count).flatMap(b => b[b.length - 1]);
  return [...former, ...latter];
};

export const encodeMessage = (bytes, version, qindex) => {
  console.assert(bytes.length === dataBytes(version, qindex));
  const [paritySize, b1data, b1count, b2count] = blockTable[version][qindex];
  const rscode = RSCode(poly, paritySize);
  const blocks = splitBlocks(Array.from(bytes), b1data, b1count, b2count);
  const parities = blocks.map(block => rscode.parity(block));
  const iblocks = interleaveBlocks(blocks, b1data, b1count);
  const iparities = transpose(parities).flat();
  return [...iblocks, ...iparities];
};

// BCH encode
// - https://www.thonky.com/qr-code-tutorial/format-version-information
const pf2poly = PF2Poly();
const formatBit = 15, formatCarry = 10, formatGen = 0b10100110111;

const quarityBits = [1, 0, 3, 2];
export const formatMask = 0b101010000010010;
export const formatValue = (qIndex, maskId) => {
  const data = pf2poly.carry((quarityBits[qIndex] << 3) | maskId, formatCarry);
  return pf2poly.sub(data, pf2poly.mod(data, formatGen));
};
export const formatBits = (qIndex, maskId) => {
  const coded = formatValue(qIndex, maskId) ^ formatMask;
  return range(formatBit).map(k => (coded >>> k) & 1).reverse();
};

// Version bits uses Extended BCH code (18, 6) such as
// - Use primitive element a an GF2n(11, 0b101011100011)
// - the versionGen is (x-a^0)*...*(x-a^2^11) => 0b11 * 0b101011100011
// - error posistion k is of e^2^k (not e^k as usual BCH code)
const versionBit = 18, versionCarry = 12, versionGen = 0b1111100100101;
export const versionBits = (version) => {
  const data = pf2poly.carry(version, versionCarry);
  const coded = pf2poly.sub(data, pf2poly.mod(data, versionGen));
  return range(formatBit).map(k => (coded >>> k) & 1);
};


qrmessage.jsでは、qrdata.jsでパッキングした文字データを、まずブロックへと分割し、各ブロックごとのにエラー訂正のパリティデータを計算し、ブロックとパリティをコード領域へ埋め込む順序に並べなおす機能を実装しています。

また、フォーマット領域とバージョン領域で埋め込むための、パリティ付きのビット列を構築する機能も実装しています。

  • dataBytes(version, qi): 引数のバージョンと品質での(最大)データバイト数
  • encodeMessage(bytes, version, qi): データバイトを、パリティをつけデータ領域へ埋め込む順序のバイト列へと変換
  • formatBits(qi, maskId): フォーマット領域に埋め込むためのビット列データ
  • versionBits(version): バージョン領域に埋め込むためのビット列データ

qrdata.jsの機能で書き込んだバイト列の終端マークやパディングを入れるためには、QRコードのデータバイト数が必要で、これを解決する関数がdataBytesです。

encodeMessageの中では、まず、データバイト列をブロックに分割します。

ブロックのバイト数はバージョンと品質ごとにQRコードの仕様で決まっています。

ブロックのパリティ数は全ブロックで共通ですが、データバイト数が1バイト多い2種類目のブロックがある場合があります。このデータ数の多いブロックは、データの後ろ側に割り当てられます。

データとパリティデータは、それぞれ分けてまとめられ、各バイトごと転置をしてから、連結します。

この結果として、QRコード画像上では、各ブロック内のバイトは、散らばって配置されます。

RSコードでのエラー訂正が可能なのは各ブロックごとであり、全ブロックが品質で指定される一定数以下のエラー発生のときのみ補正できます。
たった一つのブロックでも、品質以上のエラーが起きてしまうと失敗です。

この結果から、QRコードは、欠損のようにスポットに集まったエラーには耐性があるけど、飛び散り汚れのように散らばったエラーには弱いことがわかります。
とくにRSコードとしてバイト内の8ビットのうち1ビットでもエラーになると、8ビット全体でエラー扱いなので、ランダムな飛び散り汚れなら、名目上のエラー訂正率の1/8以下で認識不能/誤認識になるかもしれません。

QRコードの各エラー訂正符号の仕様一覧

QRコード領域 エラー訂正符号 多項式係数の有限体 原始元aの既約方程式 エラー訂正数 生成多項式
コード領域 RSコード GF($2^8$) $a^8+a^4+a^3+a^2+1=0$ (パリティバイト数dの半分以下の整数) $\prod_{k=0}^{d-1}(x-a^k)$
フォーマット領域 BCHコード GF($2^4$) $a^4+a+1=0$ 3 $x^{10}+x^8+x^5+x^4+x^2+x+1$
バージョン領域 拡張BCHコード GF($2^{11}$) $a^{11}+a^9+a^7+a^6+a^5+a+1=0$ 3 $x^{12}+x^{11}+x^{10}*x^9+x^8+x^5+x^2+1$


参考: 拡張BCHコード

拡張BCHコードの生成多項式は、実は、原始元aの既約多項式1つに$(x-1)$をかけ合わせた多項式になっていました。

つまり、BCHコードでの原始元aの連続する指数の一次式$(x-a^k)$の相乗ではなく、$(x-a^{p^k})$の相乗と(x-1)の積になっています。
この生成多項式は、多項式$x^{2^{11}-1}-1$を割り切る多項式であり、$2^{11}-1$ビットで巡回する符号となるでしょう。

拡張BCHコードは、BCHコードとは別の仕組みですが、巡回符号ではあります。
巡回符号であるため、BCHコードと同様に、生成多項式の0でない係数の項数の半分程度までのエラー出現を補正することが可能でしょう。

BCHコードは、パリティビット桁数に融通が効きません。
しかし、この拡張BCHコードでは、有限体の要素数の指数値に基づくため、自由にパリティビット桁数が選べます。

拡張BCHコードでのシンドローム計算もおそらく、多項式へ代入する$a^k$の代わりに、$a^{p*k}$を使えばできるのでしょう。
(それ以降の、一般的なエラー訂正の仕組みはわかりませんでした。)

QRコードのX0510仕様でも、この部分だけはエラー位置を計算するのではなく、全パターンの中から一番ハミング距離が近い符号値を採用する手段をとっています。


6. 空フレーム画像生成の実装


コード: grframe.js
qrframe.js
export const range = n => [...Array(n).keys()];
export const qrwidth = version => 17 + version * 4;

export const blankFrame = width => Array(width ** 2).fill(null);

export const get = (frame, width, x, y) => frame[y * width + x];
export const set = (frame, width, x, y, value) => frame[y * width + x] = value;

// finder patterns
export const markFinder = (frame, width, cx, cy) => {
  for (let x = 0; x < 7; x++) for (let y = 0; y < 7; y++) {
    const b = x === 0 || x === 6 || y === 0 || y === 6 ||
          (2 <= x && x <= 4 && 2 <= y && y <= 4);
    set(frame, width, cx - 3 + x, cy - 3 + y, +b);
  }
};
export const markSeparator = (frame, width) => {
  for (let i = 0; i < 8; i++) {
    // top left
    set(frame, width, 7, i, 0); // v
    set(frame, width, i, 7, 0); // h
    // top right
    set(frame, width, width - 8, i, 0);     // v
    set(frame, width, width - 1 - i, 7, 0); // h
    // bottom left
    set(frame, width, 7, width - 1 - i, 0); // v
    set(frame, width, i, width - 8, 0);     // h
  }
};
export const markFinders = (frame, width) => {
  markFinder(frame, width, 3, 3);
  markFinder(frame, width, width - 4, 3);
  markFinder(frame, width, 3, width - 4);
  markSeparator(frame, width);
};

// alignment patterns
// - https://www.thonky.com/qr-code-tutorial/alignment-pattern-locations
const alignmentSpans = [
   0,  0,  0,  0,  0,  0,  0, // 1 <=> 6       
  16, 18, 20, 22, 24, 26, 28, // 7 <=> 13
  20, 22, 24, 24, 26, 28, 28, //14 <=> 20
  22, 24, 24, 26, 26, 28, 28, //21 <=> 27
  24, 24, 26, 26, 26, 28, 28, //28 <=> 34
  24, 26, 26, 26, 28, 28,     //35 <=> 40
];
export const alignmentIndexes = version => {
  if (version < 2) return [];
  const last = qrwidth(version) - 7;
  const count = Math.floor(version / 7) + 1;
  const span = alignmentSpans[version];
  return range(count).map(k => last - k * span).reverse();
};
export const markAlignment = (frame, width, cx, cy) => {
  for (let x = 0; x < 5; x++) for (let y = 0; y < 5; y++) {
    const b = x === 0 || x === 4 || y === 0 || y === 4 || (x === 2 && y === 2);
    set(frame, width, cx - 2 + x, cy - 2 + y, +b);
  }
};
export const markAlignments = (frame, width, indexes) => {
  for (const cx of indexes) for (const cy of indexes) {
    markAlignment(frame, width, cx, cy);
  }
  for (const cx of indexes.slice(0, -1)) markAlignment(frame, width, cx, 6);
  for (const cy of indexes.slice(0, -1)) markAlignment(frame, width, 6, cy);
};

export const markTimings = (frame, width) => {
  for (let i = 8; i < width - 8; i++) {
    set(frame, width, 6, i, 1 - (i & 1)); // v-line
    set(frame, width, i, 6, 1 - (i & 1)); // h-line
  }
};

// non data frame
export const makeFrame = version => {
  const width = qrwidth(version);
  const frame = blankFrame(width);
  markFinders(frame, width);
  const indexes = alignmentIndexes(version);
  markAlignments(frame, width, indexes);
  markTimings(frame, width);
  set(frame, width, 8, width - 8, 1);
  return frame;
};


このQRコード実装全体で、QRコード画像を表すデータを「フレーム」とし、セル数xセル数の要素数の、セルの1次元配列で表現しています。
このフレームには、余白(クワイエットゾーン)は含みません。

フレーム内の各セルの値は黒がビット1、白がビット0で、未完成のセルにはnullを割り当てます。フレームでは、セルが未完成かどうかが区別できることが重要です。
QRコードでデータ領域を埋めるときは、フレーム全体を一様の手順で走査(スキャン)しながら、パターン等ですでにビットが埋まっているセルはスキップすることで、埋めていくからです。

qrframe.jsでは、データに依存しない各パターンを埋め込んだフレームを作成します。

  • makeFrame(version): データ領域、フォーマット領域、バージョン領域が未完成の空フレームを作る

空フレーム作成時、ファインダーパターンとタイミングパターンの埋め方は、どのバージョンでも同じ手続きで可能です。

注意点は、バージョン7以上で、アラインメントパターンを複数個に配置するときの、アラインメントを置く間隔はバージョンにより増減がまちまちなことです。このため、バージョンと間隔の表をコード内に埋め込んでいます。


参考: 各パターンの役割

ファインダーパターン

  • 画像からQRコードを検出するするとき、一番最初に３つのアラインメントパターンの存在を調べる
  • ファインダーの大きさと間隔から、フレームのセル数を推定する
  • ファインダーの中央の位置から、各セルの座標変換行列を作る
    • バージョン領域のセルの値を得る
  • 左下のアラインメントパターンの位置を推定する (バージョン2以上)

タイミングパターン

  • タイミングパターン上にある各アラインメントの中央の位置を推定する (バージョン7以上)

左下のアラインメントパターン

  • ファインダーとともに、他の左端、最下部のアラインメントの位置を推定するために用いる

タイミングパターン上にあるアラインメントパターン

  • 左下以外のアラインメントの中央の位置を推定するために用いる

アラインメントパターン

  • ファインダーとともに、アラインメントの中央の位置を、各セルの座標変換行列を作るために用いる

フレーム上の各セルの内容を、画像から取り出すとき、ファインダーやアラインメントの位置を用いて、座標変換行列を作ることができます。
変換行列のために各セルにより近いファインダーやアラインメントを3つ用いることで、より正確な値を得ることができます。

ファインダーの大きさから推定するフレームのセル数は、大きいバージョンになるほど不正確になります。
バージョン７以上にある、ファインダーに隣接しているバージョン領域の歪みは少ないため、正確なセル数を得る場合は、バージョン領域の値を用いる必要があるでしょう。


7. マスク付きデータ埋め込みの実装


コード: qrencode.js
qrencode.js
import {BitReader} from "./bitstream.js";
import * as QRMessage from "./qrmessage.js";
import {qrwidth, get, set, makeFrame} from "./qrframe.js";

export const buildEmptyFrame = (version, qi, maskId) => {
  const width = qrwidth(version);
  const frame = makeFrame(version);

  const formatBits = QRMessage.formatBits(qi, maskId);
  embedFormat(frame, width, formatBits);
  if (version >= 7) {
    const versionBits = QRMessage.versionBits(version);
    embedVersion(frame, width, versionBits);
  }
  return [frame, width];
};
export const buildFrame = (coded, version, qi, maskId) => {
  console.assert(coded.length === QRMessage.codeBytes(version, qi),
                 "Invalid data length");
  const [frame, width] = buildEmptyFrame(version, qi, maskId);
  embedCode(frame, width, coded, maskId);
  return frame;
};

// embedding code info
export const embedFormat = (frame, width, formatBits) => {
  // top left: go left then go up
  for (let i = 0; i < 6; i++) set(frame, width, i, 8, formatBits[i]);
  set(frame, width, 7, 8, formatBits[6]);
  set(frame, width, 8, 8, formatBits[7]);
  set(frame, width, 8, 7, formatBits[8]);
  for (let i = 9; i < 15; i++) set(frame, width, 8, 14 - i, formatBits[i]);

  // bottom-left: go left
  for (let i = 0; i < 7; i++) {
    set(frame, width, 8, width - 1 - i, formatBits[i]);
  }
  // top-right: go up
  for (let i = 7; i < 15; i++) {
    set(frame, width, width - 15 + i, 8, formatBits[i]);
  }
};
export const embedVersion = (frame, width, versionBits) => {
  for (let i = 0; i < 18; i++) {
    const rem = i % 3, u = (i - rem) / 3, v = (width - 11) + rem;
    set(frame, width, u, v, versionBits[i]); // bottom-left
    set(frame, width, v, u, versionBits[i]); // top-right
  }
};

// generator of zigzag scan [x, y] to set bit
export const makeScanner = function* (width) {
  let x = width - 1, y = width - 1, dy = -1;
  while (x >= 0) {
    yield [x, y];
    x--;
    yield [x, y];
    y += dy;
    if (0 <= y & y < width) {
      x++;
    } else {
      y -= dy;
      dy *= -1;
      x--;
      if (x === 6) x--;
    }
  }
};

// mask pattern
// - https://www.thonky.com/qr-code-tutorial/mask-patterns
const qrmaskTable = [
  (x, y) => (x + y) % 2 === 0,
  (x, y) => y % 2 === 0,
  (x, y) => x % 3 === 0,
  (x, y) => (x + y) % 3 === 0,
  (x, y) => ((x - x % 3) / 3 + (y - y % 2) / 2) % 2 === 0,
  (x, y) => (x * y) % 2 + (x * y) % 3 === 0,
  (x, y) => ((x * y) % 2 + (x * y) % 3) % 2 === 0,
  (x, y) => ((x + y) % 2 + (x * y) % 3) % 2 === 0,
];
export const qrmask = (maskId, x, y) => +qrmaskTable[maskId](x, y);

export const embedCode = (frame, width, coded, maskId) => {
  const br = new BitReader(coded);
  for (const [x, y] of makeScanner(width)) {
    if (get(frame, width, x, y) !== null) continue;
    const b = br.isEnd() ? 0 : br.readBit();
    const m = qrmask(maskId, x, y);
    set(frame, width, x, y, m ^ b);
  }
  console.assert(br.isEnd(), "incomplete read");
};


  • buildEmptyFrame(version, qi, maskId): データ領域が空のQRコード画像を作る
  • buildFrame(coded, version, qi, maskId): 符号語バイト列と指定したバージョン、品質、マスクのQRコード画像を作る

ジェネレータmakeScanner(width)で実装しているデータ領域の走査方法は、以下の手続きになります。

  • 最右下(x = width-1、y = width-1)より始める
  • 右=>左上=>右=>...と上へとジグザグにたどる
  • 最上に到達する(y < 0)と右にずらし、右=>左下=>右=>...と下へと向きを変える
  • 最下に到達する(y > width - 1)と右にずらし、右=>左下=>右=>...と上へと向きを変える
  • 向きを変えるとき、特別にx=6の縦タイミングパターンの列は全体が無いものとする

行yを変える直前の位置は、必ずジグザグ2列の右側にあり、左上か左下に移動します。
行を変えるとフレームからはみ出すとき(y=0かy=width-1)は、一つ右(x--)に移動させて、行を変える方向を上下反転させます。
このとき、x=6なら、さらにx--します。

この走査ではx=6以外のパターンは特別扱いする必要はなく、buildEmptyFrameで得たフレームで非空セルにあたれば単にスキップするだけです。
結果として、ファンダーパターンのところで折り返していたり、アラインメントを迂回しているような並びになったように見えます。

マスク計算では、左上のセルを0行(y=0)0列(x=0)として、計算します。

たとえば、マスクID 1の場合では、`yが偶数つまりy % 2 === 0ならマスクは1としてデータビットとXORしたもの、つまり0/1反転させてをセルに埋めます。
もし、yが奇数ならマスクは0で、データビットをそのままセルに埋めます。

8. マスク性能評価関数の実装


コード: qrevaluation.js
qrevaluation.js
import {get} from "./qrframe.js";

// mask evaluation
// - https://www.thonky.com/qr-code-tutorial/data-masking
export const evaluate1 = (frame, width) => {
  // longer line (len >= 5) as penalty len-2
  let score = 0;
  for (let y = 0; y < width; y++) {
    let len = 1, cur = get(frame, width, 0, y);
    for (let x = 1; x < width; x++) {
      const c = get(frame, width, x, y);
      if (c === cur) {
        len++;
        if (len === 5) score += 3;
        else if (len > 5) score++;
      } else {
        cur = c, len = 1;
      }
    }
  }

  for (let x = 0; x < width; x++) {
    let len = 1, cur = get(frame, width, x, 0);
    for (let y = 1; y < width; y++) {
      const c = get(frame, width, x, y);
      if (c === cur) {
        len++;
        if (len === 5) score += 3;
        else if (len > 5) score++;
      } else {
        cur = c, len = 1;
      }
    }
  }
  return score;
};

export const evaluate2 = (frame, width) => {
  // 2x2 square as penalty 3
  let score = 0;
  for (let y = 1; y < width; y++) {
    for (let x = 1; x < width; x++) {
      const c = get(frame, width, x, y);
      const up = get(frame, width, x, y - 1);
      if (c !== up) {
        x++;
        continue;
      }
      if (get(frame, width, x - 1, y - 1) === c &&
          get(frame, width, x - 1, y) === c) score += 3;
    }
  }
  return score;
};

export const evaluate3 = (frame, width) => {
  // 11-bit line pattern 10111010000 or 00001011101 as penalty 40
  const p1 = 0b10111010000, p2 = 0b00001011101, m = 0b11111111111;
  let score = 0;
  for (let y = 0; y < width; y++) {
    let scan = 0;
    for (let x = 0; x < 10; x++) scan = (scan << 1) | get(frame, width, x, y);
    for (let x = 10; x < width; x++) {
      scan = ((scan << 1) | get(frame, width, x, y)) & m;
      if (scan === p1 || scan === p2) score += 40;
    }
  }
  for (let x = 0; x < width; x++) {
    let scan = 0;
    for (let y = 0; y < 10; y++) scan = (scan << 1) | get(frame, width, x, y);
    for (let y = 10; y < width; y++) {
      scan = ((scan << 1) | get(frame, width, x, y)) & m;
      if (scan === p1 || scan === p2) score += 40;
    }
  }
  return score;
};

export const evaluate4 = (frame, width) => {
  // dark/light rate as penalty as 10 each 5% difeerence
  const total = frame.length, dark = frame.filter(b => b === 1).length;
  return Math.floor(Math.abs(dark * 100 / total - 50) / 5) * 10;
};

export const evaluate = (frame, width) =>
  evaluate1(frame, width) + evaluate2(frame, width) + evaluate3(frame, width) +
  evaluate4(frame, width);


QRコードの仕様では、8種類あるマスクの中から、一番ペナルティ(失点)の低いマスクを採用することになっています。
ペナルティ評価方法は以下のリンクにあるとおりです。

4種のペナルティ評価の総和が、そのマスクのペナルティになります。

  • ペナルティ1: 縦横で、同色セルの5以上続く連続列ごとにペナルティ +(連続列の長さ-2)
  • ペナルティ2: 2x2同色矩形ごとにペナルティ +3
  • ペナルティ3: 縦横で、黒白黒黒黒白黒のセルの列があり、その前後どちらかが白セル４つであればペナルティ +40
  • ペナルティ4: 黒比率が50%から、5%広がるごとにペナルティ +10

(ペナルティ4の、X0510仕様書での例示(p45)では、たとえば53%なら+10のように読めるが、続く20点の部分をみるに、「の場合」ではなく「を超えた場合」だと思う)

ただし、X0510仕様書では、形式情報(フォーマット領域)と型番情報(バージョン領域)の埋め込みの前にマスクのペナルティ評価を行っています。

(すべて白扱いするよう。画像へのペナルティであるならば、先に全部埋めた上で評価するほうがよりよいと思うけど)

注意点として、ペナルティ評価はそれぞれでフレーム内のセル全体を走査するので、バージョンが大きくなるとそれなりに重い処理になります。

9. フレームデータのSVG化およびImageData書き込みの実装


コード: qrimagedata.js
qrimagedata.js
const get = (frame, width, x, y) => frame[y * width + x];
const set = (image, x, y, p) => {
  if (p === null) return;
  const i = 4 * (y * image.width + x);
  image.data[i + 0] = image.data[i + 1] = image.data[i + 2] = p ? 0 : 255;
  image.data[i + 3] = 255;
};

// HTML 2D Canvas ImageData
export const renderWidth = width => width + 8;
export const render = (image, frame, width, scale) => {
  const pxwidth = (width + 8) * scale;
  console.assert(image.width >= pxwidth && image.height >= pxwidth);
  for (let x = 0; x < width + 8; x++) for (let y = 0; y < width + 8; y++) {
    const margin = x < 4 || width + 4 <= x || y < 4 || width + 4 <= y;
    const p = margin ? 0 : get(frame, width, x - 4, y - 4);
    for (let u = 0; u < scale; u++) for (let v = 0; v < scale; v++) {
      set(image, x * scale + u, y * scale + v, p);
    }
  }
  return image;
};

// SVG string
export const svg = (frame, width, scale) => {
  const darks = frame.map((b, i) => {
    if (b === 0) return "";
    const x = i % width, y = (i - x) / width;
    return `<rect x="${x + 4}" y="${y + 4}" width="1" height="1" />`;
  });
  const w = width + 8, size = w * scale;
  return `<svg xmlns="http://www.w3.org/2000/svg" version="1.1"  
viewBox="0 0 ${w} ${w}" width="${size}px" height="${size}px">\
<rect x="0" y="0" width="${w}" height="${w}" fill="white" />\
${darks.join("")}</svg>`;
};


画像表示用の機能の実装です。SVGテキストと、HTML 2D CanvasのImageDataへのRGBA転写の２つを実装しています。

  • render(image, frame, width, scale): ImageDataへの書き込み。引数imageはImageDataオブジェクト。scaleは1セルのピクセル幅
  • svg(frame, width, scale): SVGテキスト文字列に変換。

SVGを使うほうがより正確な表示ができるでしょう。
HTML上でスケーリングをするなら、SVG属性値ではなく、CSSスタイルでのwidthとheight値を使うと良いです(例: <svg style="width: 50vmin; height: 50vmin;" ...>)。

10. データからのフレーム選択およびA*アルゴリズムによる自動パッキングの実装


コード: qrauto.js
qrauto.js
import * as cp2sjis from "./cp2sjis.js";
import {BitWriter} from "./bitstream.js";
import {
  lengthBit, alphaNumTable, bitNumbers, bitAlphaNums, bitBytes, bitKanjis,
  terminateData, addNumbers, addAlphaNums, addBytes, addKanjis,
} from "./qrdata.js";
import {dataBytes} from "./qrmessage.js";

// find version to fit bytes
export const minVersion = (qi, bytes) => {
  for (let v = 1; v <= 40; v++) if (dataBytes(v, qi) >= bytes) return v;
  return -1; // overflow data
};

// heqp queue
export const heapPush = (queue, less, elem) => {
  queue.push(elem);
  let idx = queue.length - 1;
  while (idx > 0) {
    const parent = (idx - 1) >>> 1;
    if (less(elem, queue[parent])) {
      [queue[idx], queue[parent], idx] = [queue[parent], elem, parent];
    } else break;
  }
};
export const heapPop = (queue, less) => {
  const ret = queue[0], elem = queue.pop();
  if (queue.length === 0) return ret;
  queue[0] = elem;
  let idx = 0;
  for (let l = idx * 2 + 1; l < queue.length; l = idx * 2 + 1) {
    const r = l + 1;
    const child = (r < queue.length && less(queue[r], queue[l])) ? r : l;
    if (less(queue[child], elem)) {
      [queue[idx], queue[child], idx] = [queue[child], elem, child];
    } else break;
  }
  return ret;
};

// split runs of same type char in bytes
const nums = new Set(alphaNumTable.slice(0, 10));
const alphas = new Set(alphaNumTable.slice(10));
export const toRuns = (text, useKanji = true) => {
  const te = new TextEncoder();
  const r = [];
  let mode = -1, s = 0, i = 0, ts = 0, ti = 0;
  for (const ch of text) { // for surrogate pair
    const cmode = nums.has(ch) ? 0 : alphas.has(ch) ? 1 :
          useKanji && cp2sjis.has(ch) ? 3 : 2;
    if (cmode !== mode)  {
      if (mode >= 0) r.push({mode, s, e: i, ts, te: ti});
      [mode, s, ts] = [cmode, i, ti];
    }
    ti += ch.length; // for surrogate pair
    i += te.encode(ch).length;
  }
  if (mode >= 0) r.push({mode, s, e: i, ts, te: ti});
  return r;
};

// bit size as score of chunks
export const bits = (mode, version, len, tlen) => {
  if (mode === 0) return bitNumbers(version, len);
  if (mode === 1) return bitAlphaNums(version, len);
  if (mode === 2) return bitBytes(version, len);
  if (mode === 3) return bitKanjis(version, tlen);
  return bitBytes(version, len);
};
export const guessChunks = (qi, runs, v) => {
  //const maxlen = bytes.length;
  const maxlen = runs[runs.length - 1].e;
  // A*/Dijkstra-algorithm (heuristic distance: bytelen * 3)
  const chunk = (mode, s, e, ts, te, prev) => ({
    mode, s, e, ts, te, bits: prev.bits + bits(mode, v, e - s, te - ts)});
  const node = (head, mode, run, last) => {
    const prevs = mode !== last.mode ? head.chunks : head.chunks.slice(0, -1);
    const tail = mode !== last.mode ?
          chunk(mode, run.s, run.e, run.ts, run.te, last) :
          chunk(mode, last.s, run.e, last.ts, run.te,
                head.chunks[head.chunks.length - 2]);
    const score = tail.bits + (maxlen - run.e) * 3;
    return {cur: head.cur + 1, score, chunks: [...prevs, tail]};
  };

  const queue = [], less = (a, b) => a.score < b.score;
  const root = {mode: -1, s: 0, e: 0, bits: 0};
  queue.push({cur: 0, score: (maxlen - runs[0].s) * 3, chunks: [root]});
  while (queue.length > 0) {
    const head = heapPop(queue, less);
    if (head.cur === runs.length) return head.chunks.slice(1);
    const run = runs[head.cur];
    const last = head.chunks[head.chunks.length - 1];
    if (run.mode === 0) {
      heapPush(queue, less, node(head, 0, run, last));
      heapPush(queue, less, node(head, 1, run, last));
      if (last.mode === 2) heapPush(queue, less, node(head, 2, run, last));
    } else if (run.mode === 1) {
      heapPush(queue, less, node(head, 1, run, last));
      heapPush(queue, less, node(head, 2, run, last));
    } else if (run.mode === 3) {
      heapPush(queue, less, node(head, 3, run, last));
      heapPush(queue, less, node(head, 2, run, last));
    } else {
      heapPush(queue, less, node(head, 2, run, last));
    }
  }
  throw Error("never reached");
};

export const byteSize = (chunks, version) => chunks.reduce(
  (r, ch) => r + bits(ch.mode, version, ch.e - ch.s, ch.te - ch.ts), 0) / 8;

export const guessChunksRec = (qi, runs, v0, runSize = 19) => {
  const chunks = [];
  for (let i = 0; i < runs.length; i += runSize) {
    // guessChunks is O(run.length^2). Split shorter runs with runSize param
    const part = guessChunks(qi, runs.slice(i, i + runSize), v0);
    if (chunks.length > 0 && chunks[chunks.length - 1].mode === part[0].mode) {
      chunks[chunks.length - 1].e = part[0].e;
      chunks[chunks.length - 1].te = part[0].te;
      chunks.push(...part.slice(1));
    } else {
      chunks.push(...part);
    }
  }
  if (chunks.length === runs.length) return chunks;
  return guessChunksRec(qi, chunks, v0, runSize >= 11 ? runSize - 2 : 11);
};

export const guess = (qi, text, useKanji = true) => {
  if (text.length === 0) {
    const v = 1;
    const bw = new BitWriter();
    const datalen = dataBytes(v, qi);
    terminateData(bw, datalen);
    return [bw, v];
  }
  const max = dataBytes(40, qi);
  if (Math.ceil(bitNumbers(40, text.length) / 8) > max) throw Error(
    `text is too long: ${text.length}`);
  const runs = toRuns(text, useKanji);
  const bytelen = runs[runs.length - 1].e;
  const v0 = bytelen + 3 > max ? 40 : minVersion(qi, bytelen + 3);
  const chunks = guessChunksRec(qi, runs, v0);
  const size = byteSize(chunks, v0);
  if (size > max) throw Error(`Too large text: ${size}-byte (max: ${max})`);
  const v = minVersion(qi, size);
  const datalen = dataBytes(v, qi);
  const bw = new BitWriter();
  for (const {mode, s, e, ts, te} of chunks) {
    const str = text.slice(ts, te);
    if (mode === 0) addNumbers(bw, v, str);
    if (mode === 1) addAlphaNums(bw, v, str);
    if (mode === 3) addKanjis(bw, v, str);
    if (mode === 2) addBytes(bw, v, str);
  }
  terminateData(bw, datalen);
  return [bw, v];
};


QRコードの文字列パッキングは、数字、英数、漢字、バイト列、それぞれの文字セットの一部がオーバラップしています。
このため、文字列に対してうまくモードの区切りを選べば、より多くのテキストを詰め込むことができます。

X0510仕様には、漢字を除く、数字、英数、バイト列の間での、長さに基づく詰め込み方が記載されてあります。
しかし、バイト列をUTF-8とすると、漢字もこの選択肢に入り、仕様のこの手法では不十分です。

qrauto.jsでは、A＊アルゴリズムを用いることで、なるべくよいビット列パッキングを行う実装をしてみました。


自動パッキング実装の詳細

まず、toRunsで、文字列を、数字、数字抜き英数、漢字、その他、の区間(run)で区分けします。
runは1つのパッキングモード情報modeと、始点インデックスのs、終点インデックスのeを持つオブジェクトです。
ただし、SJISとUTF-8の双方が関係するため、SJISのためのstringでのインデックス(ts, te)と、UTF-8バイト列でのインデックス(s, e)の双方をもたせています。
絵文字などのUTF-16サロゲートペアにも対応させています。

guessChunksのA＊アルゴリズムでは、この区間ごとに、取りうる可能なモードでパッキングさせていき、最小ビットで最後まで到達した結果を選びます。
評価はこの区間までの総消費ビットを用い、ゴールまでのヒューリスティックにはバイト列の残り数x3を用いています。
A＊の結果も、入力のrun配列と同じ形式の、モード、始点、終点のオブジェクトの配列です。

A＊は、ゴールまでのパス数が増えると急激に遅くなります。
そこで、このguess実装では、run配列を19個づつに分割して、個別にguessChunksに渡し、結果を結合することを、入出力で変化しなくなるまで、再帰的に繰り返すようにしています。


qrauto.jsには、A＊で用いる優先度キューとして、ヒープキューの実装(heapPush、heapPop)も含んでいます。

11. QRコード生成ライブラリAPI


コード: qrcode.js
qrcode.js
import {BitWriter} from "./bitstream.js";
import * as QRData from "./qrdata.js";
import {
  quarities, quarityIndex, dataBytes, encodeMessage,
} from "./qrmessage.js";
import {qrwidth} from "./qrframe.js";
import {buildFrame} from "./qrencode.js";
import {evaluate} from "./qrevaluation.js";
import {guess} from "./qrauto.js";

export {render, renderWidth, svg} from "./qrimagedata.js";

const range = n => [...Array(n).keys()];
export const quarityList = Object.freeze([...quarities]);
export const versionList = Object.freeze(range(40).map(k => k + 1));
export const maskIdList = Object.freeze(range(8));

// QR-Code builder auto data packing with minimum version
// - returns {frame, width, version, quarity, maskId} 
export const qrcode = (text, quarity = "Q", useKanji = true) => {
  if (!quarityList.includes(quarity)) throw TypeError(
    `invalid quarity: ${quarity}`);
  const qi = quarityIndex(quarity);
  const [bw, version] = guess(qi, text, useKanji);
  if (bw.byteLength() > dataBytes(version, qi)) throw Error(
    `Overflow text in version-${version}`);
  const coded = encodeMessage(bw.toBuffer(), version, qi);
  const width = qrwidth(version);
  const {frame, maskId} = buildBestFrame(coded, version, qi, width);
  return {frame, width, version, quarity, maskId};
};

export const buildBestFrame = (coded, version, qi, width) => {
  return maskIdList.map(maskId => {
    const frame = buildFrame(coded, version, qi, maskId);
    const penalty = evaluate(frame, width);
    return {penalty, frame, maskId};
  }).sort((a, b) => a.penalty - b.penalty)[0];
};

// QR-Code builder with specified version and quarity (and mask)
// 1. add each text with data type
// 2. then build a frame
export const qrbuilder = (version, quarity) => {
  if (!quarityList.includes(quarity)) throw TypeError(
    `invalid quarity: ${quarity}`);
  if (!versionList.includes(version)) throw TypeError(
    `invalid version: ${version}`);
  const bw = new BitWriter();
  const qi = quarityIndex(quarity);
  const dataLength = dataBytes(version, qi);

  // builder object
  let result = null;
  const self = {dataLength};
  return Object.freeze(Object.assign(self, {
    addNumbers: (text) => {
      QRData.addNumbers(bw, version, text);
      return self;
    },
    addAlphaNums: (text) => {
      QRData.addAlphaNums(bw, version, text);
      return self;
    },
    addBytes: (text) => {
      QRData.addBytes(bw, version, text);
      return self;
    },
    addKanjis: (text) => {
      QRData.addKanjis(bw, version, text);
      return self;
    },
    build: (maskId = null) => {
      if (result) return result;
      QRData.terminateData(bw, dataLength);
      if (bw.byteLength() > dataBytes(version)) throw Error(
        `Overflow text in version-${version}`);
      const coded = encodeMessage(bw.toBuffer(), version, qi);
      const width = qrwidth(version);
      const fm = maskId === null ? buildBestFrame(coded, version, qi, width) :
            {frame: buildFrame(coded, version, qi, maskId), maskId};
      return {frame: fm.frame, width, version, quarity, maskId: fm.maskId};
    },
  }));
};


QRコード構築APIとして以下の２つを用意しました。

  • テキスト(と品質)を与えればQRコード画像のフレームデータを返すqrcode(text, q="Q")
  • バージョンやマスクなども設定でき、パッキングも自由に行えるqrbuilder(version, quarity)

実装としては、ここまでの各モジュール実装を用いたものとなります。

API利用コードは以下のようになります。

qr-code-example2.html
<!doctype html>
<html>
  <head>
    <meta charset="utf-8" />
    <script type="module">
import * as QRCode from "./qrcode.js";

const {frame, width, version, quarity, maskId} = QRCode.qrcode("こんにちは👌");
const scale = 8;

const h2 = document.createElement("h2");
const div = document.createElement("div");

h2.textContent = `Version-Quarity (maskId): ${version}-${quarity} (${maskId})`;
div.innerHTML = QRCode.svg(frame, width, scale);

document.body.append(h2, div);
    </script>
  </head>
  <body style="background-color: gray;"></body>
</html>

12. フレーム画像からテキストを取り出すデコーダー


コード: qrdecode.js
qrdecode.js
import {BitWriter, BitReader} from "./bitstream.js";
import * as cp2sjis from "./cp2sjis.js";
import {lengthBit, alphaNumTable} from "./qrdata.js";
import {
  formatMask, formatValue, blockInfo, transpose, poly,
} from "./qrmessage.js";
import {range, get, set} from "./qrframe.js";
import {buildEmptyFrame, makeScanner, qrmask} from "./qrencode.js";
import {RSCode} from "./qrrscode.js";

export const qrversion = width => (width - 17) / 4;

export const qrdecode = (frame, width) => {
  if (frame.length !== width * width) throw Error(`invalid frame size`);
  if (!frame.every(v => v === 0 || v === 1)) {
    throw Error(`invalid frame values: should be 0 or 1`);
  }
  const version = qrversion(width);
  if (!(Number.isInteger(version) && 1 <= version && version <= 40)) {
    throw Error(`any version does not match width: ${width}`);
  }
  const {qi, maskId} = scanFormat(frame, width);
  const coded = scanCode(frame, width, version, qi, maskId);
  const bytes = decodePlain(coded, version, qi);
  return unpackText(bytes, version);
};

// unpack string from bitstream
export const unpackText = (bytes, version) => {
  const br = new BitReader(bytes);
  const chunks = [];
  while (br.canReadBits(4)) {
    const mode = br.read(4);
    if (mode === 0) break;
    else if (mode === 1) unpackNumbers(br, version, chunks);
    else if (mode === 2) unpackAlphaNums(br, version, chunks);
    else if (mode === 4) unpackBytes(br, version, chunks);
    else if (mode === 8) unpackKanjis(br, version, chunks);
    // TBD: other modes
    else throw Error(`invalid packing mode: ${mode}`);
  }
  return chunks.join("");
};

export const unpackNumbers = (br, version, chunks) => {
  const len = br.read(lengthBit(0, version));
  const rem = len % 3, d = (len - rem) / 3;
  for (let i = 0; i < d; i++) {
    chunks.push(br.read(10).toString().padStart(3, "0"));
  }
  if (rem === 2) chunks.push(br.read(7).toString().padStart(2, "0"));
  if (rem === 1) chunks.push(br.read(4).toString().padStart(1, "0"));
};

export const unpackAlphaNums = (br, version, chunks) => {
  const len = br.read(lengthBit(1, version));
  const rem = len % 2, d = (len - rem) / 2;
  for (let i = 0; i < d; i++) {
    const v = br.read(11);
    const c2 = v % 45, c1 = (v - c2) / 45;
    chunks.push(alphaNumTable[c1], alphaNumTable[c2]);
  }
  if (rem === 1) chunks.push(alphaNumTable[br.read(6)]);
};

export const unpackBytes = (br, version, chunks) => {
  const len = br.read(lengthBit(2, version));
  const buf = new Uint8Array(len);
  for (let i = 0; i < len; i++) buf[i] = br.read(8);
  chunks.push(new TextDecoder().decode(buf));
};

export const unpackKanjis = (br, version, chunks) => {
  const len = br.read(lengthBit(3, version));
  for (let i = 0; i < len; i++) {
    const v = br.read(13);
    const low = v % 0xc0, high = (v - low) / 0xc0;
    const sjis = ((high << 8) | low) + (high >= 0x1f ? 0xc140 : 0x8140);
    chunks.push(cp2sjis.toChar(sjis));
  }
};


// decode to plain bytes
export const decodePlain = (coded, version, qi) => {
  const [paritySize, b1Size, b1count, b2count] = blockInfo(version, qi);
  const blockCount = b1count + b2count;
  const dataSize = b1Size * blockCount + b2count;

  const dataList = transpose(
    range(b1Size).map(i => coded.slice(i * blockCount, (i + 1) * blockCount)));
  const b1dataList = dataList.slice(0, b1count);
  const b2dataList = dataList.slice(b1count).map(
    (block, i) => [...block, coded[dataSize - b2count + i]]);

  const parityList = transpose(range(paritySize).map(i => coded.slice(
    dataSize + i * blockCount, dataSize + (i + 1) * blockCount)));

  const messageList = [...b1dataList, ...b2dataList].map(
    (data, i) => [...data, ...parityList[i]]);

  const rscode = RSCode(poly, paritySize);
  return messageList.map(
    msg => rscode.decode(msg).slice(0, -paritySize)).flat();
};

// scan format
const formats = range(4).flatMap(qi => range(8).map(
  maskId => ({qi, maskId, format: formatValue(qi, maskId)})));

const popcnt32 = n => {
  n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
  n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);
  n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);
  return (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);
};

export const scanFormat = (frame, width) => {
  const f1a = [];
  for (let i = 0; i < 6; i++) f1a.push(get(frame, width, i, 8));
  f1a.push(get(frame, width, 7, 8));
  f1a.push(get(frame, width, 8, 8));
  f1a.push(get(frame, width, 8, 7));
  for (let i = 9; i < 15; i++) f1a.push(get(frame, width, 8, 14 - i));
  const f1v = f1a.reduce((r, b) => (r << 1) | b, 0) ^ formatMask;
  const f1r = formats.map(f => [popcnt32(f.format ^ f1v), f]);

  const f2a = [];
  for (let i = 0; i < 7; i++) {
    f2a.push(get(frame, width, 8, width - 1 - i));
  }
  for (let i = 7; i < 15; i++) {
    f2a.push(get(frame, width, width - 15 + i, 8));
  }
  const f2v = f2a.reduce((r, b) => (r << 1) | b, 0) ^ formatMask;
  const f2r = formats.map(f => [popcnt32(f.format ^ f2v), f]);

  // NOTE: choose the nearest format code, instead of computing BCH syndromes
  //  because too many erros easily match invalid format codes
  const ordered = [...f1r, ...f2r].sort(([a], [b]) => a - b);
  const min = ordered[0][0];
  if (min > 4) throw Error(`cannot scan version`); // over BCH error collect
  return ordered[0][1];
};

// scan code
export const scanCode = (frame, width, version, qi, maskId) => {
  const [empty, w] = buildEmptyFrame(version, qi, maskId);
  console.assert(w === width, "invalid width");
  const bw = new BitWriter();
  for (const [x, y] of makeScanner(width)) {
    if (get(empty, width, x, y) !== null) continue;
    const m = qrmask(maskId, x, y);
    const b = get(frame, width, x, y) ^ m;
    bw.writeBit(b);
  }
  return bw.buf; // ignore bits in incomplete byte
};


qrdecode.jsは、セルの1次元配列であるフレームから、埋め込まれたテキストを復元する機能の実装を行っています。

  • qrdecode(frame, width): QRコードに埋め込まれたテキストを返す

デコード手順は、QRコード生成の逆です。

  • 幅widthからバージョンを解決
  • フォーマット領域から、品質とマスクIDを解決(ハミング距離の近い符号へ補正)
  • バージョン情報をもとに空フレームを作りコード領域をスキャンし、マスクIDを使い、ビット列を獲得
  • バージョンと品質から、ブロックごとのデータとパリティに再編成
  • RSコードでエラー訂正したデータバイト列を作成
  • モードに基づくビット列からのアンパッキングを行い、テキスト化する

BitReaderなどはこれまでのモジュールで実装済みであり、空フレーム構築やスキャンはQRコード生成と同じものを使用します。

13. カメラ画像からフレーム画像を取り出すキャプチャ簡易実装


コード: qrcapture.js
qrcapture.js
// low quality image scanner for QR codes
const range = n => [...Array(n).keys()];

// Binarize width * height sized  array of black as true 
export const binarize = ({data, width, height}) => {
  const len = width * height, w = width, h = height;
  const colors = range(len).map(
    i => 0.299 * data[i * 4] + 0.587 * data[i * 4 + 1] +
      0.114 * data[i * 4 + 2]); //Y of YUV;

  const diffs = range(len).map(i => {
    const x = i % w, y = (i - x) / w;
    if (x < 1 ||  w - 1 <= x || y < 1 || h - 1 <= y) return colors[i];
    const dxx = colors[i - 1] - 2 * colors[i] + colors[i + 1];
    const dyy = colors[i - w] - 2 * colors[i] + colors[i + w];
    const dxy = (colors[i - 1 - w] + colors[i + 1 - w] +
                 colors[i - 1 + w] + colors[i + 1 + w]) / 4;
    const md1 = Math.abs(dxx) > Math.abs(dyy) ? dxx : dyy;
    return Math.abs(md1) > Math.abs(dxy) ? md1 : dxy;
  });
  const ave = diffs.reduce((r, c) => r + c, 0) / len;
  const bin = diffs.map(c => c < ave);
  return [bin, diffs];
};


// split binarized image as black or white runs for each rows
const binToHRuns = (bin, width) => range(width).map(y => {
  const runs = [];
  let cur = {j: y, b: false, s: 0, e: 0};
  for (let x = 0; x < width; x++) {
    const b = bin[y * width + x];
    if (cur.b === b) cur.e = x + 1;
    else if (cur.e !== 0) {
      runs.push(cur);
      cur = {j: y, b, s: x, e: x + 1};
    }
  }
  runs.push(cur);
  return runs;
});
// split binarized image as black or white runs for each columns
const binToVRuns = (bin, width) => range(width).map(x => {
  const runs = [];
  let cur = {j: x, b: false, s: 0, e: 0};
  for (let y = 0; y < width; y++) {
    const b = bin[y * width + x];
    if (cur.b === b) cur.e = y + 1;
    else if (cur.e !== 0) {
      runs.push(cur);
      cur = {j: x, b, s: y, e: y + 1};
    }
  }
  runs.push(cur);
  return runs;
});

// get finder candidates from black or white runs
const getFinders = (runs, width) => {
  const finders = [];
  for (let j = 0; j < width; j++) {
    const lruns = runs[j];
    if (lruns.length < 5) continue;
    for (let i = 0; i < lruns.length - 4; i++) {
      const cellW = (lruns[i + 4].e - lruns[i].s) / 7; //as finder width
      if (cellW < 2) continue;
      const lb = lruns[i], lw = lruns[i + 1], center = lruns[i + 2],
            rw = lruns[i + 3], rb = lruns[i + 4];
      const isFinder = Math.abs(lb.e - lb.s - cellW) < cellW &&
                       Math.abs(lw.e - lw.s  - cellW) < cellW &&
                       Math.abs(center.e - center.s - 3 * cellW) < cellW &&
                       Math.abs(rw.e - rw.s - cellW) < cellW &&
                       Math.abs(rb.e - rb.s - cellW) < cellW ;
      if (!isFinder) continue;
      const connected = finders.find(f => {
        const last = f[f.length - 1];
        if (last.j !== j - 1) return false;
        if (last.b !== center.b) return false;
        if (last.s <= center.s && center.s < last.e) return true;
        if (last.s < center.e && center.e <= last.e) return true;
        if (last.e <= center.s || center.e <= last.s) return false;
        const r = (center.e - center.s) / (last.e - last.s);
        return 0.5 < r && r < 1.5;
      });
      if (connected) connected.push(center);
      else finders.push([center]);
    }
  }
  return finders.filter(f => f.length > 1).map(f => {
    const i = f.reduce((r, l) => r + l.e + l.s, 0) / (2 * f.length);
    const j = (f[0].j + f[f.length - 1].j) / 2;
    const w = f.reduce((r, l) => r + l.e - l.s, 0) / (3 * f.length);
    return {i, j, w};
  });
};

// sort finder candidates
const sortFinders = (hfinders, vfinders, bin, width) => {
  const {abs, round} = Math;
  const filtered = hfinders.filter(
    hf => vfinders.findIndex(
      vf => Math.hypot(vf.j - hf.i, vf.i - hf.j) <= hf.w) >= 0);
  if (filtered.length === 0) return [];
  const ordered = filtered.map(({i, j, w}) => {
    const b = bin[round(j) * width + round(i)];
    const score = range(7 * 7).reduce((s, k) => {
      const rem = k % 7, dx = rem - 3, dy = (k - rem) / 7 - 3;
      const m = abs(dy) <= 1 && abs(dx) <= 1 ? b :
                abs(dy) <= 2 && abs(dx) <= 2 ? !b : b;
      return s + (bin[round(j + dy * w) * width + round(i + dx * w)] === m);
    }, 0);
    return {x: i, y: j, b, w, score};
  }).sort((a, b) => b.score - a.score);
  return ordered.filter(f => f.b === ordered[0].b);
};

// resolve location of 3 finders: [tl, tr, bl]
const resolveFinders = (finders) => {
  const [a, b, c] = finders;
  const ab = Math.hypot(b.x - a.x, b.y - a.y);
  const bc = Math.hypot(c.x - b.x, c.y - b.y);
  const ca = Math.hypot(a.x - c.x, a.y - c.y);
  const toLR = (o, e1, e2) =>
        (e1.x - o.x) * (e2.y - o.y) - (e1.y - o.y) * (e2.x - o.x) > 0 ?
        [o, e1, e2] : [o, e2, e1];
  return (bc > ab && bc > ca) ? toLR(a, b, c) :
         (ca > ab && ca > bc) ? toLR(b, c, a) : toLR(c, a, b);
};

// get 3 finders from binarized image
export const captureFinders = (bin, width) => {
  const vruns = binToVRuns(bin, width);
  const hruns = binToHRuns(bin, width);
  const hfinders = getFinders(hruns, width);
  const vfinders = getFinders(vruns, width);
  const finders = sortFinders(hfinders, vfinders, bin, width).slice(0, 3);
  return finders.length === 3 ? resolveFinders(finders) : [];
};

// compute cell width/height and cell size
const toAngledRuns = (o, p, bin, width) => {
  const {sign, abs, floor, ceil, max, min} = Math;
  const op = [p.x - o.x, p.y - o.y];
  const s = [o.x - op[0], o.y - op[1]];
  const e = [p.x + op[0], p.y + op[1]];
  const [m, n] = abs(op[0]) > abs(op[1]) ? [0, 1] : [1, 0];
  const idx = abs(op[0]) > abs(op[1]) ? (i, j) => j * width + i :
        (i, j) => i * width + j;
  const angle = op[n] / op[m], di = sign(e[m] - s[m]);
  const runs = [];
  const is = max(floor(s[m]), 0), js = floor(s[n] + angle * (is - s[m]));
  const last = min(ceil(e[m]), width);
  let cur = {b: false, m, sm: is, sn: js, em: is, en: js};
  for (let i = is; di * (last - i) > 0; i += di) {
    if (i < 0 || i >= width) continue;
    const j = floor(s[n] + angle * (i - s[m]));
    const b = bin[idx(i, j)];
    if (cur.b === b) {
      cur.em = i;
      cur.en = j;
    } else if (cur.sm !== cur.em || cur.sn !== cur.en) {
      runs.push(cur);
      cur = {
        b, m, i, j, sm: i, sn: j,
        em: i + 1, en: floor(s[n] + angle * (i + 1 - s[m]))};
    }
  }
  if (cur.sm !== cur.em || cur.sn !== cur.en) runs.push(cur);
  return runs;
};

const indexOfAngledRun = (runs, p) => runs.findIndex(run => {
  const v = run.m === 0 ? p.x : p.y;
  return Math.min(run.sm, run.em) <= v && v < Math.max(run.sm, run.em);
});
const runsWidth = (runS, runE) =>
      Math.hypot(runE.em - runS.sm, runE.en - runS.sn);

const resolveCellSize = ([tl, tr, bl], bin, width) => {
  const hruns = toAngledRuns(tl, tr, bin, width);
  const vruns = toAngledRuns(tl, bl, bin, width);
  const htl = indexOfAngledRun(hruns, tl);
  const htr = indexOfAngledRun(hruns, tr);
  const vtl = indexOfAngledRun(vruns, tl);
  const vbl = indexOfAngledRun(vruns, bl);
  if (htl - 2 < 0 || htr - 2 < 0 || vtl - 2 < 0 || vbl - 2 < 0) {
    return {size: 0};
  }
  if (htl + 2 >= hruns.length || htr + 2 >= hruns.length ||
      vtl + 2 >= vruns.length || vbl + 2 >= vruns.length) return {size: 0};

  const htlw = runsWidth(hruns[htl - 2], hruns[htl + 2]);
  const htrw = runsWidth(hruns[htr - 2], hruns[htr + 2]);
  const vtlw = runsWidth(vruns[vtl - 2], vruns[vtl + 2]);
  const vblw = runsWidth(vruns[vbl - 2], vruns[vbl + 2]);

  const cellH = (htlw + htrw) / 14;
  const cellV = (vtlw + vblw) / 14;

  const hsize = Math.hypot(tr.x - tl.x, tr.y - tl.y) / cellH + 6;
  const vsize = Math.hypot(bl.x - tl.x, bl.y - tl.y) / cellV + 6;
  const size = Math.round((hsize + vsize) / 8) * 4 + 1;
  return {size, cellH, cellV};
};


// TBD: Alignment pattern
const findAlignment = ([tl, tr, bl], cellSize, cellH, cellV, bin, width) => {
  const b = tl.b;
  const br = {x: tr.x + (bl.x - tl.x), y: tr.y + (bl.y - tl.y)};
  const prov = {
    x: tl.x + (cellSize - 10) / (cellSize - 7) * (br.x - tl.x),
    y: tl.y + (cellSize - 10) / (cellSize - 7) * (br.y - tl.y)};
  if (cellSize < 25) return prov;
  const hAsX = Math.abs(tr.x - tl.x) > Math.abs(tr.y - tl.y);
  const dx = hAsX ? cellH : cellV, dy = hAsX ? cellV : cellH;
  const hruns = binToHRuns(bin, width);
  const align = findAlignmentAt(hruns, bin, width, b, prov, dx, dy);
  return align ? align : prov;
};

const findAlignmentAt = (hruns, bin, width, b, prov, dx, dy) => {
  const {abs, hypot, floor} = Math;
  const w = (dx + dy) / 2;
  const shruns = hruns.map(runs => runs.filter(run => {
    if (run.b !== b) return false;
    if (abs(run.e - run.s) > dx * 2) return false;
    const x = (run.e + run.s) / 2, y = run.j + 0.5;
    const dist = hypot(x - prov.x, y - prov.y);
    if (dist > w * 8) return false;
    if (bin[floor(y) * width + floor(x)] !== b) return false;
    if (bin[floor(y - dy / 3) * width + floor(x)] !== b) return false;
    if (bin[floor(y + dy / 3) * width + floor(x)] !== b) return false;

    for (let i = 0; i < 25; i++) {
      const rem = i % 5, s = rem - 2, t = (i - rem) / 5 - 2;
      if (s === 0 && t === 0) continue;
      if (abs(s) <= 1 && abs(t) <= 1) {
        if (bin[floor(y + dy * t) * width + floor(x + dx * s)] === b) {
          return false;
        }
        continue;
      }
      if (bin[floor(y + dy * t) * width + floor(x + dx * s)] !== b) {
        return false;
      }
    }
    return true;
  })).flat();
  if (shruns.length > 0) {
    const s = shruns[0], e = shruns[shruns.length - 1];
    return {x: (s.e + s.s + e.e + e.s) / 4 + 0.5, y: (s.j + e.j) / 2 + 0.5};
  } else return null;
};

// matrix math
const mat3mul = (ma, mb) => {
  const r = [[0, 0, 0], [0, 0, 0], [0, 0, 0]];
  for (let i = 0; i < 3; i++) for (let k = 0; k < 3; k++) {
    for (let j = 0; j < 3; j++) r[i][j] += ma[i][k] * mb[k][j];
  }
  return r;
};
//console.log(mat3mul(
//  [[3.5, 25 - 3.5, 3.5], [3.5, 3.5, 25 - 3.5], [1, 1, 1]],
//  [[1, 2, 3],[1, 2, 3],[1,2,3]]));

const mat3tr = m => range(3).map(i => range(3).map(j => m[j][i]));
const mat3scale = (m, c) => m.map(l => l.map(v => v * c));
const mat3submat = (m, i, j) => m.filter(
  (l, mi) => mi !== i).map(l => l.filter((_, lj) => lj !== j));
const mat2det = m => m[0][0] * m[1][1] - m[0][1] * m[1][0];
const mat3adj = m => mat3tr(m.map(
  (l, i) => l.map((_, j) => (-1) ** (i + j) * mat2det(mat3submat(m, i, j)))));
const mat3det = m => m[0].reduce(
  (r, c, i) => r + (-1) ** i * c * mat2det(mat3submat(m, 0, i)), 0);
const mat3inv = m => mat3scale(mat3adj(m), 1 / mat3det(m));
//console.log(mat3det([[3.5,25-3.5,3.5], [3.5,3.5,25-3.5], [1,1,1]]));
//console.log(mat3adj([[3.5,25-3.5,3.5], [3.5,3.5,25-3.5], [1,1,1]]));
//console.log(mat3inv([[3.5,25-3.5,3.5], [3.5,3.5,25-3.5], [1,1,1]]));
//console.log(mat3inv(mat3inv([[3.5,25-3.5,3.5], [3.5,3.5,25-3.5], [1,1,1]])));

const transform = (m, x, y) =>  {
  const z = m[2][0] * x + m[2][1] * y + m[2][2];
  return {
    x: (m[0][0] * x + m[0][1] * y + m[0][2]) / z,
    y: (m[1][0] * x + m[1][1] * y + m[1][2]) / z,
  };
};

// image to cells
// P = [[3.5, w-3.5, 3.5], [3.5, 3.5, w-3.5], [1, 1, 1]]
// R = [[tl.x, tr.x, bl.x], [tl.y. tr.y, bl.y], [1, 1, 1]]
// M*P = R => M = R*P^-1
export const toFrame = (alignedFinders, bin, width) => {
  const [tl, tr, bl] = alignedFinders;
  const {size, cellH, cellV} = resolveCellSize(alignedFinders, bin, width);
  if (size <= 0) return [[], size, cellH, cellV];
  const br = findAlignment(alignedFinders, size, cellH, cellV, bin, width);

  const P0 = [[3.5, size - 3.5, 3.5], [3.5, 3.5, size - 3.5], [1, 1, 1]];
  const R0 = [[tl.x, tr.x, bl.x], [tl.y, tr.y, bl.y], [1, 1, 1]];
  const M0 = mat3mul(R0, mat3inv(P0));

  const P1 = [
    [3.5, size - 3.5, size - 6.5], [3.5, 3.5, size - 6.5], [1, 1, 1]];
  const R1 = [[tl.x, tr.x, br.x], [tl.y, tr.y, br.y], [1, 1, 1]];
  const M1 = mat3mul(R1, mat3inv(P1));

  const P2 = [
    [3.5, size - 6.5, 3.5], [3.5, size - 6.5, size - 3.5], [1, 1, 1]];
  const R2 = [[tl.x, br.x, bl.x], [tl.y, br.y, bl.y], [1, 1, 1]];
  const M2 = mat3mul(R2, mat3inv(P2));

  const P3 = [
    [size - 3.5, 3.5, size - 6.5], [3.5, size - 3.5, size - 6.5], [1, 1, 1]];
  const R3 = [[tr.x, bl.x, br.x], [tr.y, bl.y, br.y], [1, 1, 1]];
  const M3 = mat3mul(R3, mat3inv(P3));

  return [range(size * size).map(i => {
    const x = i % size, y = (i - x) / size;
    const M = (x > size * 2 / 4) && (y > size * 2 / 4) ? M3 :
          (x < size * 2 / 4) && (y > size * 2 / 4) ? M2 :
          (x > size * 2 / 4) && (y < size * 2 / 4) ? M1 : M0;
    const p = transform(M, x + 0.5, y + 0.5);
    const b = bin[Math.floor(p.y) * width + Math.floor(p.x)];
    return +(tr.b === b);
  }), size, cellH, cellV, br];
};


qrcapture.jsは、QRコード画像キャプチャ機能の実装です。
HTML 2D CanvasのImageDataから、qrdecodeに渡すためのフレームとフレーム幅を取り出すまでの機能を簡易実装しています。

このモジュールで行うことは、以下のことになります。

  • 二値化(binarize): ImageDataのRGBA画像から、白黒2値の画像に変換
  • ファインダー検出(captureFinders): 2値画像から、３つのファインダーを検出し、(左上、右上、左下)の順で、それぞれの画像上での中心座標を得る
  • フレーム化(toFrame): 2値画像と3ファインダーの位置から、セルの1次元配列であるフレームや、フレームの幅、2値画像上のセル幅や右下アラインメントの中心位置などを得る


キャプチャ実装の課題

実装する上で一番ネックになったのは、カメラの品質に影響されることでした。
たとえば、バージョン40のセル数は177ですが、画像の幅が480ピクセルしかなければ、1セル3ピクセル幅もない状態です。アラインメント中心点のような孤立点は画像から消える場合も多くなります。
あとカメラしだいなのかもしれませんが、そこそこ大きなセルでも、アラインメントの正方形が、ほぼ丸になってキャプチャされたりします。

この実装では、右下以外のアラインメントは検出もしていません。
ファインダーと右下アラインメントのうち各セルに近い3つによる変換行列を使い、セル位置から行列演算で画像上の位置へ変換してサンプリングします。
このため、どのファインダーやアラインメントからも遠い、中央部分の認識から悪くなります。

また、バージョン領域も活用していません。ある程度のバージョン以上では、ファインダー位置からのセル幅算出と実際の幅とにギャップが出ます。
セルが細かくなっても、ファインダー間の部分の揺れは相対的に少ないので、アラインメント検出の前に、バージョン情報を得て幅を得る必要があるでしょう。


実装時に参考にしたのは、以下の２つのQRコードスキャナ実装です(これらのコード量は、qrcapture.jsよりずっと大きなものです)。


参考: WICG Shape Detection APIのBarcodeDetector

WICG Shape Detection APIというWeb APIが提案されており、その中のBarcodeDetectorの実装はAndroid版Chromeには実装されています。chrome://flagsの"Experimental Web Platform features"をEnableすることで使えます。QRコードもBarcodeDetectorが認識するバーコード仕様のフォーマットの一つに入っています。

BarcodeDetectorのインスタンスへ、video要素等をdetectメソッドへ渡すと、非同期(await)で、テキストや形式、バウンディングボックス、コーナー点配列が複数個得られるようになっています。

const video = document.querySelector("video");

const barcodes = await new BarcodeDetector().detect(video);
for (const {rawValue, format, boundingBox, cornerPoints} of barcodes) {
   console.log(`- ${format}: ${rawValue}`);
}

もし、他のブラウザやデスクトップOSでも無設定で使えるようになるなら、QRコードスキャナ機能は、このShape Detection APIを用いることで、Webページ内にかんたんに組み込めるようになるでしょう。


実装してみた感想

QRコード自体の仕様の解釈が不明瞭のまま実装していったので、記事に従って実装したことが正しいかどうかは、QRコード画像を出すところまでいって、AndroidでQRコードスキャナで文字が出でる時点になって確認できたことでした。
qrencode-example.htmlで、HTML上で生成した全バージョン全マスクのQRコード画像が、AndroidのQRコードキャプチャで認識できたときは少し嬉しくなりました。

QRコードを作るプログラムは、ゼロから実装したとしてもコード量もそれほど多いわけではなく、なにより実用できるものになるので、プログラミング演習向きな題材だと思いました。
あらかじめテストコードを用意するなどでガイドをつければ、脱初級者レベルの題材になりそうです。
エラー訂正符号部分とSJIS部分は、教養が必要だけど、こういう部分が1つ２つあってもよいのではないでしょうか。

QRコードリーダー側の実装は、個々のUSBカメラの精度にも影響される面もあり、それほど手軽には作れないかもしれません。
ただ、精度の悪いキャプチャリングでも、エラー訂正が機能して読み込めてしまうのには、ちょっと感動しましたが(あまりにもエラーが多くなると、誤訂正されてしまいます)。

付録: qr-codeカスタムエレメント実装

qrcode.jsモジュールを、HTMLカスタムエレメント化させるコード以下のようになります。タグ名はqr-codeにしています。

qr-code.js
import * as qrcode from "./qrcode.js";

class QRCode extends HTMLElement {
  constructor(opts = {}) {
    super();
    Object.assign(this.dataset, opts);
    this.attachShadow({mode: "open"});
    this.observer = new MutationObserver(muts => this.update());
  }
  connectedCallback() {
    this.update();
    this.observer.observe(this, {attributes: true});
  }
  disconnectedCallback() {
    this.observer.disconnect();
  }
  update() {
    const {text = "", quarity = "Q", scale = 8, style = ""} = this.dataset;
    const {frame, width} = qrcode.qrcode(text, quarity);
    this.shadowRoot.innerHTML = qrcode.svg(frame, width, scale >>> 0);
    this.shadowRoot.firstElementChild.setAttribute("style", style);
  }
}
customElements.define("qr-code", QRCode);

MutationObserverを使うことで、qr-codeタグの各属性値の変更にも追従する実装にしてあることで、以下のようなHTMLタグでも、QRコードジェネレータを実装することができるようになっています。

qr-code-element-example.html
<!doctype html>
<html>
  <head>
    <script type="module" src="./qr-code.js"></script>
  </head>
  <body>
    <h1><code>qr-code</code> custom element</h1>
    <div>
      <label>text: <input value="Hello World!" size="80" oninput="
        document.querySelector('qr-code').dataset.text = this.value;"></label>
    </div>
    <qr-code data-text="Hello World!" data-quarity="M" data-scale="4"
             data-style="border: solid; width: 50vmin; height: 50vmin;"
    ></qr-code>
  </body>
</html>

デモ

63
80
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
63
80