suwako / LittleBeast

master
ブランチ master
LittleBeast / src / Std / Lib / Qr.php
15.7 KB、391行 生 Blame 履歴
1<?php
2/*************************************************************
3# 076 License
4
5Copyright (c) テクニカル諏訪子
6
7Permission is hereby granted to any person obtaining a copy of the software
8Little Beast (the "Software") to use, modify, merge, copy, publish, distribute,
9sublicense, and/or sell copies of the Software, subject to the following conditions:
10
11 1. **Origin Attribution**:
12 - You must not misrepresent the origin of the Software; you must not claim
13 you created the original Software.
14 - If the Software is used in a product, you must either:
15 a. Provide clear attribution in the product's documentation, user interface,
16 or other visible areas, **OR**
17 b. Pay the original developers a fee they specify in writing.
18 2. **Usage Restriction**:
19 - The Software, or any derivative works, dependencies, or libraries
20 incorporating it, must not be used for censorship or to suppress freedom of
21 speech, expression, or creativity. Prohibited uses include, but are not
22 limited to:
23 - Censorship of so-called "hate speech", visuals, non-mainstream opinions,
24 ideas, or objective reality.
25 - Tools or systems designed to restrict access to information or
26 artistic works.
27 3. **Notice Preservation**:
28 - This license and the above copyright notice must remain intact in all copies
29 of the source code.
30
31THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
32INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
33PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
34HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
35CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
36OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 */
38namespace Std\Lib;
39
40use Std\Lib\Image\Bitmap;
41
42/**
43 * QRコード（ISO/IEC 18004）
44 *
45 * 型番1～40、誤り訂正L・M・Q・H、数字・英数字・バイト（UTF-8）のモード、8つのマスクから減点の一番少ない物。
46 * 画像にはbitmap()（PNG等はImage::encodeで）。
47 */
48final class Qr {
49 /** 誤り訂正のレベル => [形式情報のビット, 1ブロックの誤り訂正の数（型番1～40）, ブロックの数] */
50 private const EC = [
51 'L' => [1, [7, 10, 15, 20, 26, 18, 20, 24, 30, 18, 20, 24, 26, 30, 22, 24, 28, 30, 28, 28, 28, 28, 30, 30, 26, 28, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30],
52 [1, 1, 1, 1, 1, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6, 6, 6, 6, 7, 8, 8, 9, 9, 10, 12, 12, 12, 13, 14, 15, 16, 17, 18, 19, 19, 20, 21, 22, 24, 25]],
53 'M' => [0, [10, 16, 26, 18, 24, 16, 18, 22, 22, 26, 30, 22, 22, 24, 24, 28, 28, 26, 26, 26, 26, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28],
54 [1, 1, 1, 2, 2, 4, 4, 4, 5, 5, 5, 8, 9, 9, 10, 10, 11, 13, 14, 16, 17, 17, 18, 20, 21, 23, 25, 26, 28, 29, 31, 33, 35, 37, 38, 40, 43, 45, 47, 49]],
55 'Q' => [3, [13, 22, 18, 26, 18, 24, 18, 22, 20, 24, 28, 26, 24, 20, 30, 24, 28, 28, 26, 30, 28, 30, 30, 30, 30, 28, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30],
56 [1, 1, 2, 2, 4, 4, 6, 6, 8, 8, 8, 10, 12, 16, 12, 17, 16, 18, 21, 20, 23, 23, 25, 27, 29, 34, 34, 35, 38, 40, 43, 45, 48, 51, 53, 56, 59, 62, 65, 68]],
57 'H' => [2, [17, 28, 22, 16, 22, 28, 26, 26, 24, 28, 24, 28, 22, 24, 24, 30, 28, 28, 26, 28, 30, 24, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30],
58 [1, 1, 2, 4, 4, 4, 5, 6, 8, 8, 11, 11, 16, 16, 18, 16, 19, 21, 25, 25, 25, 34, 30, 32, 35, 37, 40, 42, 45, 48, 51, 54, 57, 60, 63, 66, 70, 74, 77, 81]],
59 ];
60 private const ALNUM = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:';
61
62 public int $version;
63 public int $size;
64 public int $mask;
65 public string $level;
66 /** 行毎のモジュール（trueが黒） */
67 public array $modules = [];
68 /** 機能パターン（データを置かない所） */
69 private array $function = [];
70
71 /**
72 * @param string $text 中身（数字だけ、英大文字等だけなら小さいモードを使う）
73 * @param string $level 誤り訂正（L：7%、M：15%、Q：25%、H：30%）
74 * @param int $minVersion 最小の型番
75 * @throws \InvalidArgumentException 入り切らない場合
76 */
77 public function __construct(string $text, string $level = 'M', int $minVersion = 1) {
78 if (!isset(self::EC[$level])) throw new \InvalidArgumentException('誤り訂正のレベルはL・M・Q・Hです。');
79 $this->level = $level;
80 [$mode, $count] = match (true) {
81 preg_match('/^\d*$/', $text) === 1 => [1, strlen($text)],
82 strspn($text, self::ALNUM) === strlen($text) => [2, strlen($text)],
83 default => [4, strlen($text)],
84 };
85 for ($v = max(1, $minVersion); $v <= 40; $v++) {
86 $bits = self::segment($text, $mode, $count, $v);
87 if ($bits !== null && strlen($bits) <= self::dataCodewords($v, $level) * 8) break;
88 }
89 if ($v > 40) throw new \InvalidArgumentException('QRコードに入り切りません。');
90 $this->version = $v;
91 $this->size = $v * 4 + 17;
92
93 // 終端（4ビットまで）、8ビットに揃え、残りは0xEC・0x11の繰り返し
94 $cap = self::dataCodewords($v, $level) * 8;
95 $bits .= str_repeat('0', min(4, $cap - strlen($bits)));
96 $bits .= str_repeat('0', (8 - strlen($bits) % 8) % 8);
97 for ($pad = 0xec; strlen($bits) < $cap; $pad ^= 0xec ^ 0x11) $bits .= sprintf('%08b', $pad);
98 $data = array_map('bindec', str_split($bits, 8));
99
100 $this->modules = array_fill(0, $this->size, array_fill(0, $this->size, false));
101 $this->function = $this->modules;
102 $this->drawFunctions();
103 $this->drawCodewords(self::interleave($data, $v, $level));
104
105 // 減点の一番少ないマスク
106 $best = null;
107 for ($m = 0; $m < 8; $m++) {
108 $this->applyMask($m);
109 $this->drawFormat($m);
110 $p = $this->penalty();
111 if ($best === null || $p < $best[0]) $best = [$p, $m];
112 $this->applyMask($m);
113 }
114 $this->mask = $best[1];
115 $this->applyMask($this->mask);
116 $this->drawFormat($this->mask);
117 unset($this->function);
118 }
119
120 /**
121 * 画像にする
122 *
123 * @param int $scale 1モジュールの画素数
124 * @param int $margin 周りの白（モジュール、規格では4以上）
125 */
126 public function bitmap(int $scale = 4, int $margin = 4): Bitmap {
127 $w = ($this->size + 2 * $margin) * $scale;
128 $white = str_repeat("\xff\xff\xff\xff", $w);
129 $data = str_repeat($white, $margin * $scale);
130 foreach ($this->modules as $row) {
131 $line = str_repeat("\xff\xff\xff\xff", $margin * $scale);
132 foreach ($row as $dark) $line .= str_repeat($dark ? "\0\0\0\xff" : "\xff\xff\xff\xff", $scale);
133 $line .= str_repeat("\xff\xff\xff\xff", $margin * $scale);
134 $data .= str_repeat($line, $scale);
135 }
136 $data .= str_repeat($white, $margin * $scale);
137 return new Bitmap($w, $w, $data);
138 }
139
140 /**
141 * モード、文字数、データのビット列（文字数が型番の欄に入らなければnull）
142 */
143 private static function segment(string $text, int $mode, int $count, int $v): ?string {
144 $cbits = match ($mode) {
145 1 => $v < 10 ? 10 : ($v < 27 ? 12 : 14),
146 2 => $v < 10 ? 9 : ($v < 27 ? 11 : 13),
147 default => $v < 10 ? 8 : 16,
148 };
149 if ($count >= 1 << $cbits) return null;
150 $bits = sprintf('%04b', $mode).str_pad(decbin($count), $cbits, '0', STR_PAD_LEFT);
151 if ($mode === 1) {
152 foreach (str_split($text, 3) as $g) if ($g !== '') $bits .= str_pad(decbin((int)$g), [1 => 4, 2 => 7, 3 => 10][strlen($g)], '0', STR_PAD_LEFT);
153 } else if ($mode === 2) {
154 foreach (str_split($text, 2) as $g) {
155 if ($g === '') continue;
156 $bits .= strlen($g) === 2
157 ? str_pad(decbin(strpos(self::ALNUM, $g[0]) * 45 + strpos(self::ALNUM, $g[1])), 11, '0', STR_PAD_LEFT)
158 : str_pad(decbin(strpos(self::ALNUM, $g)), 6, '0', STR_PAD_LEFT);
159 }
160 } else {
161 for ($i = 0; $i < $count; $i++) $bits .= sprintf('%08b', ord($text[$i]));
162 }
163 return $bits;
164 }
165
166 /** データを置けるモジュールの数（機能パターンと形式・型番情報を除く） */
167 private static function rawModules(int $v): int {
168 $n = (16 * $v + 128) * $v + 64;
169 if ($v >= 2) {
170 $align = intdiv($v, 7) + 2;
171 $n -= (25 * $align - 10) * $align - 55;
172 if ($v >= 7) $n -= 36;
173 }
174 return $n;
175 }
176
177 private static function dataCodewords(int $v, string $level): int {
178 [, $ecc, $blocks] = self::EC[$level];
179 return intdiv(self::rawModules($v), 8) - $ecc[$v - 1] * $blocks[$v - 1];
180 }
181
182 /**
183 * ブロックに分けて誤り訂正を付け、交互に並べる
184 */
185 private static function interleave(array $data, int $v, string $level): array {
186 [, $eccs, $nblocks] = self::EC[$level];
187 $ecc = $eccs[$v - 1];
188 $n = $nblocks[$v - 1];
189 $total = intdiv(self::rawModules($v), 8);
190 $short = $n - $total % $n;
191 $shortLen = intdiv($total, $n);
192 $gen = self::generator($ecc);
193 $blocks = [];
194 $pos = 0;
195 for ($i = 0; $i < $n; $i++) {
196 $len = $shortLen - $ecc + ($i < $short ? 0 : 1);
197 $d = array_slice($data, $pos, $len);
198 $pos += $len;
199 $blocks[] = [$d, self::remainder($d, $gen)];
200 }
201 $out = [];
202 for ($i = 0; $i <= $shortLen - $ecc; $i++) {
203 foreach ($blocks as [$d]) if (isset($d[$i])) $out[] = $d[$i];
204 }
205 for ($i = 0; $i < $ecc; $i++) {
206 foreach ($blocks as [, $e]) $out[] = $e[$i];
207 }
208 return $out;
209 }
210
211 /** GF(2^8)（x^8 + x^4 + x^3 + x^2 + 1）の掛け算 */
212 private static function mul(int $x, int $y): int {
213 $z = 0;
214 for ($i = 7; $i >= 0; $i--) {
215 $z = ($z << 1) ^ (($z >> 7) * 0x11d);
216 $z ^= (($y >> $i) & 1) * $x;
217 }
218 return $z;
219 }
220
221 /** リード・ソロモンの生成多項式（最高次の係数は省く） */
222 private static function generator(int $degree): array {
223 $g = array_fill(0, $degree, 0);
224 $g[$degree - 1] = 1;
225 $root = 1;
226 for ($i = 0; $i < $degree; $i++) {
227 for ($j = 0; $j < $degree; $j++) {
228 $g[$j] = self::mul($g[$j], $root);
229 if ($j + 1 < $degree) $g[$j] ^= $g[$j + 1];
230 }
231 $root = self::mul($root, 0x02);
232 }
233 return $g;
234 }
235
236 private static function remainder(array $data, array $gen): array {
237 $r = array_fill(0, count($gen), 0);
238 foreach ($data as $b) {
239 $f = $b ^ array_shift($r);
240 $r[] = 0;
241 foreach ($gen as $i => $c) $r[$i] ^= self::mul($c, $f);
242 }
243 return $r;
244 }
245
246 private function set(int $x, int $y, bool $dark): void {
247 $this->modules[$y][$x] = $dark;
248 $this->function[$y][$x] = true;
249 }
250
251 /** 位置検出、タイミング、位置合わせのパターン、型番情報（形式情報の場所は先に取っておく） */
252 private function drawFunctions(): void {
253 $s = $this->size;
254 for ($i = 0; $i < $s; $i++) {
255 $this->set(6, $i, $i % 2 === 0);
256 $this->set($i, 6, $i % 2 === 0);
257 }
258 foreach ([[3, 3], [$s - 4, 3], [3, $s - 4]] as [$cx, $cy]) {
259 for ($dy = -4; $dy <= 4; $dy++) {
260 for ($dx = -4; $dx <= 4; $dx++) {
261 $x = $cx + $dx;
262 $y = $cy + $dy;
263 if ($x < 0 || $y < 0 || $x >= $s || $y >= $s) continue;
264 $d = max(abs($dx), abs($dy));
265 $this->set($x, $y, $d !== 2 && $d !== 4);
266 }
267 }
268 }
269 // 位置合わせ（位置検出と重なる3つの角以外）
270 if ($this->version > 1) {
271 $n = intdiv($this->version, 7) + 2;
272 $step = intdiv($this->version * 8 + $n * 3 + 5, $n * 4 - 4) * 2;
273 $pos = [6];
274 for ($i = $n - 1; $i >= 1; $i--) $pos[$i] = $s - 7 - ($n - 1 - $i) * $step;
275 ksort($pos);
276 foreach ($pos as $i => $x) {
277 foreach ($pos as $j => $y) {
278 if (($i === 0 && $j === 0) || ($i === 0 && $j === $n - 1) || ($i === $n - 1 && $j === 0)) continue;
279 for ($dy = -2; $dy <= 2; $dy++) for ($dx = -2; $dx <= 2; $dx++) $this->set($x + $dx, $y + $dy, max(abs($dx), abs($dy)) !== 1);
280 }
281 }
282 }
283 $this->drawFormat(0);
284 if ($this->version >= 7) {
285 $rem = $this->version;
286 for ($i = 0; $i < 12; $i++) $rem = ($rem << 1) ^ (($rem >> 11) * 0x1f25);
287 $bits = ($this->version << 12) | $rem;
288 for ($i = 0; $i < 18; $i++) {
289 $dark = (($bits >> $i) & 1) === 1;
290 $a = $s - 11 + $i % 3;
291 $b = intdiv($i, 3);
292 $this->set($a, $b, $dark);
293 $this->set($b, $a, $dark);
294 }
295 }
296 }
297
298 /** 形式情報（誤り訂正のレベルとマスク）の2つの写し */
299 private function drawFormat(int $mask): void {
300 $data = (self::EC[$this->level][0] << 3) | $mask;
301 $rem = $data;
302 for ($i = 0; $i < 10; $i++) $rem = ($rem << 1) ^ (($rem >> 9) * 0x537);
303 $bits = (($data << 10) | $rem) ^ 0x5412;
304 $bit = fn(int $i): bool => (($bits >> $i) & 1) === 1;
305 $s = $this->size;
306 for ($i = 0; $i <= 5; $i++) $this->set(8, $i, $bit($i));
307 $this->set(8, 7, $bit(6));
308 $this->set(8, 8, $bit(7));
309 $this->set(7, 8, $bit(8));
310 for ($i = 9; $i < 15; $i++) $this->set(14 - $i, 8, $bit($i));
311 for ($i = 0; $i < 8; $i++) $this->set($s - 1 - $i, 8, $bit($i));
312 for ($i = 8; $i < 15; $i++) $this->set(8, $s - 15 + $i, $bit($i));
313 $this->set(8, $s - 8, true);
314 }
315
316 /** 右下から2列ずつ、上下にジグザグに置く */
317 private function drawCodewords(array $data): void {
318 $s = $this->size;
319 $total = count($data) * 8;
320 $i = 0;
321 for ($right = $s - 1; $right >= 1; $right -= 2) {
322 if ($right === 6) $right = 5;
323 $up = (($right + 1) & 2) === 0;
324 for ($vert = 0; $vert < $s; $vert++) {
325 $y = $up ? $s - 1 - $vert : $vert;
326 for ($j = 0; $j < 2; $j++) {
327 $x = $right - $j;
328 if ($this->function[$y][$x]) continue;
329 // 残りのモジュールは0（白）
330 if ($i < $total) $this->modules[$y][$x] = (($data[$i >> 3] >> (7 - ($i & 7))) & 1) === 1;
331 $i++;
332 }
333 }
334 }
335 }
336
337 /** マスク（2回掛けると元に戻る） */
338 private function applyMask(int $m): void {
339 for ($y = 0; $y < $this->size; $y++) {
340 for ($x = 0; $x < $this->size; $x++) {
341 if ($this->function[$y][$x]) continue;
342 $flip = match ($m) {
343 0 => ($x + $y) % 2 === 0,
344 1 => $y % 2 === 0,
345 2 => $x % 3 === 0,
346 3 => ($x + $y) % 3 === 0,
347 4 => (intdiv($x, 3) + intdiv($y, 2)) % 2 === 0,
348 5 => $x * $y % 2 + $x * $y % 3 === 0,
349 6 => ($x * $y % 2 + $x * $y % 3) % 2 === 0,
350 default => (($x + $y) % 2 + $x * $y % 3) % 2 === 0,
351 };
352 if ($flip) $this->modules[$y][$x] = !$this->modules[$y][$x];
353 }
354 }
355 }
356
357 /**
358 * 減点（同じ色の5つ以上の並び、2x2の塊、位置検出に似た模様、黒の割合）
359 */
360 private function penalty(): int {
361 $s = $this->size;
362 $p = 0;
363 $lines = [];
364 for ($y = 0; $y < $s; $y++) {
365 $lines[] = implode('', array_map(fn($d) => $d ? '1' : '0', $this->modules[$y]));
366 }
367 $cols = [];
368 for ($x = 0; $x < $s; $x++) {
369 $c = '';
370 for ($y = 0; $y < $s; $y++) $c .= $lines[$y][$x];
371 $cols[] = $c;
372 }
373 $dark = 0;
374 foreach ([...$lines, ...$cols] as $k => $line) {
375 if ($k < $s) $dark += substr_count($line, '1');
376 if (preg_match_all('/0{5,}|1{5,}/', $line, $m)) foreach ($m[0] as $run) $p += strlen($run) - 2;
377 // 1:1:3:1:1の両側に4つの白（外側は白とみなす）
378 $padded = '0000'.$line.'0000';
379 $p += 40 * (preg_match_all('/(?=00001011101)/', $padded) + preg_match_all('/(?=10111010000)/', $padded));
380 }
381 for ($y = 0; $y < $s - 1; $y++) {
382 for ($x = 0; $x < $s - 1; $x++) {
383 $c = $lines[$y][$x];
384 if ($c === $lines[$y][$x + 1] && $c === $lines[$y + 1][$x] && $c === $lines[$y + 1][$x + 1]) $p += 3;
385 }
386 }
387 $total = $s * $s;
388 $p += 10 * max(0, intdiv(abs($dark * 20 - $total * 10) + $total - 1, $total) - 1);
389 return $p;
390 }
391}