Debian Codegraph @

src/Common/BitMatrix.php

raw
1 <?php
2 declare(strict_types = 1);
3
4 namespace BaconQrCode\Common;
5
6 use BaconQrCode\Exception\InvalidArgumentException;
7 use SplFixedArray;
8
9 /**
10 * Bit matrix.
11 *
12 * Represents a 2D matrix of bits. In function arguments below, and throughout
13 * the common module, x is the column position, and y is the row position. The
14 * ordering is always x, y. The origin is at the top-left.
15 */
16 class BitMatrix
17 {
18 /**
19 * Width of the bit matrix.
20 */
21 private int $width;
22
23 /**
24 * Height of the bit matrix.
25 */
26 private ?int $height;
27
28 /**
29 * Size in bits of each individual row.
30 */
31 private int $rowSize;
32
33 /**
34 * Bits representation.
35 *
36 * @var SplFixedArray<int>
37 */
38 private SplFixedArray $bits;
39
40 /**
41 * @throws InvalidArgumentException if a dimension is smaller than zero
42 */
43 public function __construct(int $width, ?int $height = null)
44 {
45 if (null === $height) {
46 $height = $width;
47 }
48
49 if ($width < 1 || $height < 1) {
50 throw new InvalidArgumentException('Both dimensions must be greater than zero');
51 }
52
53 $this->width = $width;
54 $this->height = $height;
55 $this->rowSize = ($width + 31) >> 5;
56 $this->bits = SplFixedArray::fromArray(array_fill(0, $this->rowSize * $height, 0));
57 }
58
59 /**
60 * Gets the requested bit, where true means black.
61 */
62 public function get(int $x, int $y) : bool
63 {
64 $offset = $y * $this->rowSize + ($x >> 5);
65 return 0 !== (BitUtils::unsignedRightShift($this->bits[$offset], ($x & 0x1f)) & 1);
66 }
67
68 /**
69 * Sets the given bit to true.
70 */
71 public function set(int $x, int $y) : void
72 {
73 $offset = $y * $this->rowSize + ($x >> 5);
74 $this->bits[$offset] = $this->bits[$offset] | (1 << ($x & 0x1f));
75 }
76
77 /**
78 * Flips the given bit.
79 */
80 public function flip(int $x, int $y) : void
81 {
82 $offset = $y * $this->rowSize + ($x >> 5);
83 $this->bits[$offset] = $this->bits[$offset] ^ (1 << ($x & 0x1f));
84 }
85
86 /**
87 * Clears all bits (set to false).
88 */
89 public function clear() : void
90 {
91 $max = count($this->bits);
92
93 for ($i = 0; $i < $max; ++$i) {
94 $this->bits[$i] = 0;
95 }
96 }
97
98 /**
99 * Sets a square region of the bit matrix to true.
100 *
101 * @throws InvalidArgumentException if left or top are negative
102 * @throws InvalidArgumentException if width or height are smaller than 1
103 * @throws InvalidArgumentException if region does not fit into the matix
104 */
105 public function setRegion(int $left, int $top, int $width, int $height) : void
106 {
107 if ($top < 0 || $left < 0) {
108 throw new InvalidArgumentException('Left and top must be non-negative');
109 }
110
111 if ($height < 1 || $width < 1) {
112 throw new InvalidArgumentException('Width and height must be at least 1');
113 }
114
115 $right = $left + $width;
116 $bottom = $top + $height;
117
118 if ($bottom > $this->height || $right > $this->width) {
119 throw new InvalidArgumentException('The region must fit inside the matrix');
120 }
121
122 for ($y = $top; $y < $bottom; ++$y) {
123 $offset = $y * $this->rowSize;
124
125 for ($x = $left; $x < $right; ++$x) {
126 $index = $offset + ($x >> 5);
127 $this->bits[$index] = $this->bits[$index] | (1 << ($x & 0x1f));
128 }
129 }
130 }
131
132 /**
133 * A fast method to retrieve one row of data from the matrix as a BitArray.
134 */
135 public function getRow(int $y, ?BitArray $row = null) : BitArray
136 {
137 if (null === $row || $row->getSize() < $this->width) {
138 $row = new BitArray($this->width);
139 }
140
141 $offset = $y * $this->rowSize;
142
143 for ($x = 0; $x < $this->rowSize; ++$x) {
144 $row->setBulk($x << 5, $this->bits[$offset + $x]);
145 }
146
147 return $row;
148 }
149
150 /**
151 * Sets a row of data from a BitArray.
152 */
153 public function setRow(int $y, BitArray $row) : void
154 {
155 $bits = $row->getBitArray();
156
157 for ($i = 0; $i < $this->rowSize; ++$i) {
158 $this->bits[$y * $this->rowSize + $i] = $bits[$i];
159 }
160 }
161
162 /**
163 * This is useful in detecting the enclosing rectangle of a 'pure' barcode.
164 *
165 * @return int[]|null
166 */
167 public function getEnclosingRectangle() : ?array
168 {
169 $left = $this->width;
170 $top = $this->height;
171 $right = -1;
172 $bottom = -1;
173
174 for ($y = 0; $y < $this->height; ++$y) {
175 for ($x32 = 0; $x32 < $this->rowSize; ++$x32) {
176 $bits = $this->bits[$y * $this->rowSize + $x32];
177
178 if (0 !== $bits) {
179 if ($y < $top) {
180 $top = $y;
181 }
182
183 if ($y > $bottom) {
184 $bottom = $y;
185 }
186
187 if ($x32 * 32 < $left) {
188 $bit = 0;
189
190 while (($bits << (31 - $bit)) === 0) {
191 $bit++;
192 }
193
194 if (($x32 * 32 + $bit) < $left) {
195 $left = $x32 * 32 + $bit;
196 }
197 }
198 }
199
200 if ($x32 * 32 + 31 > $right) {
201 $bit = 31;
202
203 while (0 === BitUtils::unsignedRightShift($bits, $bit)) {
204 --$bit;
205 }
206
207 if (($x32 * 32 + $bit) > $right) {
208 $right = $x32 * 32 + $bit;
209 }
210 }
211 }
212 }
213
214 $width = $right - $left;
215 $height = $bottom - $top;
216
217 if ($width < 0 || $height < 0) {
218 return null;
219 }
220
221 return [$left, $top, $width, $height];
222 }
223
224 /**
225 * Gets the most top left set bit.
226 *
227 * This is useful in detecting a corner of a 'pure' barcode.
228 *
229 * @return int[]|null
230 */
231 public function getTopLeftOnBit() : ?array
232 {
233 $bitsOffset = 0;
234
235 while ($bitsOffset < count($this->bits) && 0 === $this->bits[$bitsOffset]) {
236 ++$bitsOffset;
237 }
238
239 if (count($this->bits) === $bitsOffset) {
240 return null;
241 }
242
243 $x = intdiv($bitsOffset, $this->rowSize);
244 $y = ($bitsOffset % $this->rowSize) << 5;
245
246 $bits = $this->bits[$bitsOffset];
247 $bit = 0;
248
249 while (0 === ($bits << (31 - $bit))) {
250 ++$bit;
251 }
252
253 $x += $bit;
254
255 return [$x, $y];
256 }
257
258 /**
259 * Gets the most bottom right set bit.
260 *
261 * This is useful in detecting a corner of a 'pure' barcode.
262 *
263 * @return int[]|null
264 */
265 public function getBottomRightOnBit() : ?array
266 {
267 $bitsOffset = count($this->bits) - 1;
268
269 while ($bitsOffset >= 0 && 0 === $this->bits[$bitsOffset]) {
270 --$bitsOffset;
271 }
272
273 if ($bitsOffset < 0) {
274 return null;
275 }
276
277 $x = intdiv($bitsOffset, $this->rowSize);
278 $y = ($bitsOffset % $this->rowSize) << 5;
279
280 $bits = $this->bits[$bitsOffset];
281 $bit = 0;
282
283 while (0 === BitUtils::unsignedRightShift($bits, $bit)) {
284 --$bit;
285 }
286
287 $x += $bit;
288
289 return [$x, $y];
290 }
291
292 /**
293 * Gets the width of the matrix,
294 */
295 public function getWidth() : int
296 {
297 return $this->width;
298 }
299
300 /**
301 * Gets the height of the matrix.
302 */
303 public function getHeight() : int
304 {
305 return $this->height;
306 }
307 }