|
1
|
|
|
<?php |
|
2
|
|
|
/** |
|
3
|
|
|
* Class Polynomial |
|
4
|
|
|
* |
|
5
|
|
|
* @filesource Polynomial.php |
|
6
|
|
|
* @created 25.11.2015 |
|
7
|
|
|
* @package chillerlan\QRCode\Helpers |
|
8
|
|
|
* @author Smiley <[email protected]> |
|
9
|
|
|
* @copyright 2015 Smiley |
|
10
|
|
|
* @license MIT |
|
11
|
|
|
*/ |
|
12
|
|
|
|
|
13
|
|
|
namespace chillerlan\QRCode\Helpers; |
|
14
|
|
|
|
|
15
|
|
|
use chillerlan\QRCode\QRCodeException; |
|
16
|
|
|
|
|
17
|
|
|
use function array_fill, count, sprintf; |
|
18
|
|
|
|
|
19
|
|
|
/** |
|
20
|
|
|
* @link http://www.thonky.com/qr-code-tutorial/error-correction-coding |
|
21
|
|
|
*/ |
|
22
|
|
|
class Polynomial{ |
|
23
|
|
|
|
|
24
|
|
|
/** |
|
25
|
|
|
* @link http://www.thonky.com/qr-code-tutorial/log-antilog-table |
|
26
|
|
|
*/ |
|
27
|
|
|
protected const table = [ |
|
28
|
|
|
[ 1, 0], [ 2, 0], [ 4, 1], [ 8, 25], [ 16, 2], [ 32, 50], [ 64, 26], [128, 198], |
|
29
|
|
|
[ 29, 3], [ 58, 223], [116, 51], [232, 238], [205, 27], [135, 104], [ 19, 199], [ 38, 75], |
|
30
|
|
|
[ 76, 4], [152, 100], [ 45, 224], [ 90, 14], [180, 52], [117, 141], [234, 239], [201, 129], |
|
31
|
|
|
[143, 28], [ 3, 193], [ 6, 105], [ 12, 248], [ 24, 200], [ 48, 8], [ 96, 76], [192, 113], |
|
32
|
|
|
[157, 5], [ 39, 138], [ 78, 101], [156, 47], [ 37, 225], [ 74, 36], [148, 15], [ 53, 33], |
|
33
|
|
|
[106, 53], [212, 147], [181, 142], [119, 218], [238, 240], [193, 18], [159, 130], [ 35, 69], |
|
34
|
|
|
[ 70, 29], [140, 181], [ 5, 194], [ 10, 125], [ 20, 106], [ 40, 39], [ 80, 249], [160, 185], |
|
35
|
|
|
[ 93, 201], [186, 154], [105, 9], [210, 120], [185, 77], [111, 228], [222, 114], [161, 166], |
|
36
|
|
|
[ 95, 6], [190, 191], [ 97, 139], [194, 98], [153, 102], [ 47, 221], [ 94, 48], [188, 253], |
|
37
|
|
|
[101, 226], [202, 152], [137, 37], [ 15, 179], [ 30, 16], [ 60, 145], [120, 34], [240, 136], |
|
38
|
|
|
[253, 54], [231, 208], [211, 148], [187, 206], [107, 143], [214, 150], [177, 219], [127, 189], |
|
39
|
|
|
[254, 241], [225, 210], [223, 19], [163, 92], [ 91, 131], [182, 56], [113, 70], [226, 64], |
|
40
|
|
|
[217, 30], [175, 66], [ 67, 182], [134, 163], [ 17, 195], [ 34, 72], [ 68, 126], [136, 110], |
|
41
|
|
|
[ 13, 107], [ 26, 58], [ 52, 40], [104, 84], [208, 250], [189, 133], [103, 186], [206, 61], |
|
42
|
|
|
[129, 202], [ 31, 94], [ 62, 155], [124, 159], [248, 10], [237, 21], [199, 121], [147, 43], |
|
43
|
|
|
[ 59, 78], [118, 212], [236, 229], [197, 172], [151, 115], [ 51, 243], [102, 167], [204, 87], |
|
44
|
|
|
[133, 7], [ 23, 112], [ 46, 192], [ 92, 247], [184, 140], [109, 128], [218, 99], [169, 13], |
|
45
|
|
|
[ 79, 103], [158, 74], [ 33, 222], [ 66, 237], [132, 49], [ 21, 197], [ 42, 254], [ 84, 24], |
|
46
|
|
|
[168, 227], [ 77, 165], [154, 153], [ 41, 119], [ 82, 38], [164, 184], [ 85, 180], [170, 124], |
|
47
|
|
|
[ 73, 17], [146, 68], [ 57, 146], [114, 217], [228, 35], [213, 32], [183, 137], [115, 46], |
|
48
|
|
|
[230, 55], [209, 63], [191, 209], [ 99, 91], [198, 149], [145, 188], [ 63, 207], [126, 205], |
|
49
|
|
|
[252, 144], [229, 135], [215, 151], [179, 178], [123, 220], [246, 252], [241, 190], [255, 97], |
|
50
|
|
|
[227, 242], [219, 86], [171, 211], [ 75, 171], [150, 20], [ 49, 42], [ 98, 93], [196, 158], |
|
51
|
|
|
[149, 132], [ 55, 60], [110, 57], [220, 83], [165, 71], [ 87, 109], [174, 65], [ 65, 162], |
|
52
|
|
|
[130, 31], [ 25, 45], [ 50, 67], [100, 216], [200, 183], [141, 123], [ 7, 164], [ 14, 118], |
|
53
|
|
|
[ 28, 196], [ 56, 23], [112, 73], [224, 236], [221, 127], [167, 12], [ 83, 111], [166, 246], |
|
54
|
|
|
[ 81, 108], [162, 161], [ 89, 59], [178, 82], [121, 41], [242, 157], [249, 85], [239, 170], |
|
55
|
|
|
[195, 251], [155, 96], [ 43, 134], [ 86, 177], [172, 187], [ 69, 204], [138, 62], [ 9, 90], |
|
56
|
|
|
[ 18, 203], [ 36, 89], [ 72, 95], [144, 176], [ 61, 156], [122, 169], [244, 160], [245, 81], |
|
57
|
|
|
[247, 11], [243, 245], [251, 22], [235, 235], [203, 122], [139, 117], [ 11, 44], [ 22, 215], |
|
58
|
|
|
[ 44, 79], [ 88, 174], [176, 213], [125, 233], [250, 230], [233, 231], [207, 173], [131, 232], |
|
59
|
|
|
[ 27, 116], [ 54, 214], [108, 244], [216, 234], [173, 168], [ 71, 80], [142, 88], [ 1, 175], |
|
60
|
|
|
]; |
|
61
|
|
|
|
|
62
|
|
|
/** |
|
63
|
|
|
* @var int[] |
|
64
|
|
|
*/ |
|
65
|
|
|
protected array $num = []; |
|
66
|
|
|
|
|
67
|
|
|
/** |
|
68
|
|
|
* Polynomial constructor. |
|
69
|
|
|
*/ |
|
70
|
|
|
public function __construct(array $num = null, int $shift = null){ |
|
71
|
|
|
$this->setNum($num ?? [1], $shift); |
|
72
|
|
|
} |
|
73
|
|
|
|
|
74
|
|
|
/** |
|
75
|
|
|
* |
|
76
|
|
|
*/ |
|
77
|
|
|
public function getNum():array{ |
|
78
|
|
|
return $this->num; |
|
79
|
|
|
} |
|
80
|
|
|
|
|
81
|
|
|
/** |
|
82
|
|
|
* |
|
83
|
|
|
*/ |
|
84
|
|
|
public function setNum(array $num, int $shift = null):Polynomial{ |
|
85
|
|
|
$offset = 0; |
|
86
|
|
|
$numCount = count($num); |
|
87
|
|
|
|
|
88
|
|
|
while($offset < $numCount && $num[$offset] === 0){ |
|
89
|
|
|
$offset++; |
|
90
|
|
|
} |
|
91
|
|
|
|
|
92
|
|
|
$this->num = array_fill(0, $numCount - $offset + ($shift ?? 0), 0); |
|
93
|
|
|
|
|
94
|
|
|
for($i = 0; $i < $numCount - $offset; $i++){ |
|
95
|
|
|
$this->num[$i] = $num[$i + $offset]; |
|
96
|
|
|
} |
|
97
|
|
|
|
|
98
|
|
|
return $this; |
|
99
|
|
|
} |
|
100
|
|
|
|
|
101
|
|
|
/** |
|
102
|
|
|
* |
|
103
|
|
|
*/ |
|
104
|
|
|
public function multiply(array $e):Polynomial{ |
|
105
|
|
|
$n = array_fill(0, count($this->num) + count($e) - 1, 0); |
|
106
|
|
|
|
|
107
|
|
|
foreach($this->num as $i => $vi){ |
|
108
|
|
|
$vi = $this->glog($vi); |
|
109
|
|
|
|
|
110
|
|
|
foreach($e as $j => $vj){ |
|
111
|
|
|
$n[$i + $j] ^= $this->gexp($vi + $this->glog($vj)); |
|
112
|
|
|
} |
|
113
|
|
|
|
|
114
|
|
|
} |
|
115
|
|
|
|
|
116
|
|
|
$this->setNum($n); |
|
117
|
|
|
|
|
118
|
|
|
return $this; |
|
119
|
|
|
} |
|
120
|
|
|
|
|
121
|
|
|
/** |
|
122
|
|
|
* |
|
123
|
|
|
*/ |
|
124
|
|
|
public function mod(array $e):Polynomial{ |
|
125
|
|
|
$n = $this->num; |
|
126
|
|
|
|
|
127
|
|
|
if(count($n) - count($e) < 0){ |
|
128
|
|
|
return $this; |
|
129
|
|
|
} |
|
130
|
|
|
|
|
131
|
|
|
$ratio = $this->glog($n[0]) - $this->glog($e[0]); |
|
132
|
|
|
|
|
133
|
|
|
foreach($e as $i => $v){ |
|
134
|
|
|
$n[$i] ^= $this->gexp($this->glog($v) + $ratio); |
|
135
|
|
|
} |
|
136
|
|
|
|
|
137
|
|
|
$this->setNum($n)->mod($e); |
|
138
|
|
|
|
|
139
|
|
|
return $this; |
|
140
|
|
|
} |
|
141
|
|
|
|
|
142
|
|
|
/** |
|
143
|
|
|
* @throws \chillerlan\QRCode\QRCodeException |
|
144
|
|
|
*/ |
|
145
|
|
|
public function glog(int $n):int{ |
|
146
|
|
|
|
|
147
|
|
|
if($n < 1){ |
|
148
|
|
|
throw new QRCodeException(sprintf('log(%s)', $n)); |
|
149
|
|
|
} |
|
150
|
|
|
|
|
151
|
|
|
return Polynomial::table[$n][1]; |
|
152
|
|
|
} |
|
153
|
|
|
|
|
154
|
|
|
/** |
|
155
|
|
|
* |
|
156
|
|
|
*/ |
|
157
|
|
|
public function gexp(int $n):int{ |
|
158
|
|
|
|
|
159
|
|
|
if($n < 0){ |
|
160
|
|
|
$n += 255; |
|
161
|
|
|
} |
|
162
|
|
|
elseif($n >= 256){ |
|
163
|
|
|
$n -= 255; |
|
164
|
|
|
} |
|
165
|
|
|
|
|
166
|
|
|
return Polynomial::table[$n][0]; |
|
167
|
|
|
} |
|
168
|
|
|
|
|
169
|
|
|
} |
|
170
|
|
|
|
chillerlan /
php-qrcode
