1 // Copyright 2014 The PDFium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
6 // Original code is licensed as follows:
7 /*
8 * Copyright 2008 ZXing authors
9 *
10 * Licensed under the Apache License, Version 2.0 (the "License");
11 * you may not use this file except in compliance with the License.
12 * You may obtain a copy of the License at
13 *
14 * http://www.apache.org/licenses/LICENSE-2.0
15 *
16 * Unless required by applicable law or agreed to in writing, software
17 * distributed under the License is distributed on an "AS IS" BASIS,
18 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19 * See the License for the specific language governing permissions and
20 * limitations under the License.
21 */
22
23 #include "fxbarcode/qrcode/BC_QRCoderMatrixUtil.h"
24
25 #include <array>
26 #include <iterator>
27
28 #include "core/fxcrt/check.h"
29 #include "core/fxcrt/check_op.h"
30 #include "fxbarcode/common/BC_CommonByteMatrix.h"
31 #include "fxbarcode/qrcode/BC_QRCoder.h"
32 #include "fxbarcode/qrcode/BC_QRCoderBitVector.h"
33 #include "fxbarcode/qrcode/BC_QRCoderErrorCorrectionLevel.h"
34 #include "fxbarcode/qrcode/BC_QRCoderMaskUtil.h"
35
36 namespace {
37
38 using PositionDetectionPatternRow = std::array<uint8_t, 7>;
39 constexpr std::array<const PositionDetectionPatternRow, 7>
40 kPositionDetectionPatternTable = {{{{1, 1, 1, 1, 1, 1, 1}},
41 {{1, 0, 0, 0, 0, 0, 1}},
42 {{1, 0, 1, 1, 1, 0, 1}},
43 {{1, 0, 1, 1, 1, 0, 1}},
44 {{1, 0, 1, 1, 1, 0, 1}},
45 {{1, 0, 0, 0, 0, 0, 1}},
46 {{1, 1, 1, 1, 1, 1, 1}}}};
47
48 using PositionAdjustmentPatternRow = std::array<uint8_t, 5>;
49 constexpr std::array<const PositionAdjustmentPatternRow, 5>
50 kPositionAdjustmentPatternTable = {{{{1, 1, 1, 1, 1}},
51 {{1, 0, 0, 0, 1}},
52 {{1, 0, 1, 0, 1}},
53 {{1, 0, 0, 0, 1}},
54 {{1, 1, 1, 1, 1}}}};
55
56 constexpr size_t kNumCoordinate = 7;
57 using PositionCoordinatePatternRow = std::array<uint8_t, kNumCoordinate>;
58 constexpr std::array<const PositionCoordinatePatternRow, 39>
59 kPositionCoordinatePatternTable = {{
60 {{6, 18, 0, 0, 0, 0, 0}}, {{6, 22, 0, 0, 0, 0, 0}},
61 {{6, 26, 0, 0, 0, 0, 0}}, {{6, 30, 0, 0, 0, 0, 0}},
62 {{6, 34, 0, 0, 0, 0, 0}}, {{6, 22, 38, 0, 0, 0, 0}},
63 {{6, 24, 42, 0, 0, 0, 0}}, {{6, 26, 46, 0, 0, 0, 0}},
64 {{6, 28, 50, 0, 0, 0, 0}}, {{6, 30, 54, 0, 0, 0, 0}},
65 {{6, 32, 58, 0, 0, 0, 0}}, {{6, 34, 62, 0, 0, 0, 0}},
66 {{6, 26, 46, 66, 0, 0, 0}}, {{6, 26, 48, 70, 0, 0, 0}},
67 {{6, 26, 50, 74, 0, 0, 0}}, {{6, 30, 54, 78, 0, 0, 0}},
68 {{6, 30, 56, 82, 0, 0, 0}}, {{6, 30, 58, 86, 0, 0, 0}},
69 {{6, 34, 62, 90, 0, 0, 0}}, {{6, 28, 50, 72, 94, 0, 0}},
70 {{6, 26, 50, 74, 98, 0, 0}}, {{6, 30, 54, 78, 102, 0, 0}},
71 {{6, 28, 54, 80, 106, 0, 0}}, {{6, 32, 58, 84, 110, 0, 0}},
72 {{6, 30, 58, 86, 114, 0, 0}}, {{6, 34, 62, 90, 118, 0, 0}},
73 {{6, 26, 50, 74, 98, 122, 0}}, {{6, 30, 54, 78, 102, 126, 0}},
74 {{6, 26, 52, 78, 104, 130, 0}}, {{6, 30, 56, 82, 108, 134, 0}},
75 {{6, 34, 60, 86, 112, 138, 0}}, {{6, 30, 58, 86, 114, 142, 0}},
76 {{6, 34, 62, 90, 118, 146, 0}}, {{6, 30, 54, 78, 102, 126, 150}},
77 {{6, 24, 50, 76, 102, 128, 154}}, {{6, 28, 54, 80, 106, 132, 158}},
78 {{6, 32, 58, 84, 110, 136, 162}}, {{6, 26, 54, 82, 110, 138, 166}},
79 {{6, 30, 58, 86, 114, 142, 170}},
80 }};
81
82 struct TypeInfoCoordinate {
83 uint8_t x;
84 uint8_t y;
85 };
86
87 const std::array<const TypeInfoCoordinate, 15> kTypeInfoCoordinates = {{
88 {8, 0},
89 {8, 1},
90 {8, 2},
91 {8, 3},
92 {8, 4},
93 {8, 5},
94 {8, 7},
95 {8, 8},
96 {7, 8},
97 {5, 8},
98 {4, 8},
99 {3, 8},
100 {2, 8},
101 {1, 8},
102 {0, 8},
103 }};
104
105 constexpr int32_t VERSION_INFO_POLY = 0x1f25;
106 constexpr int32_t TYPE_INFO_POLY = 0x0537;
107 constexpr int32_t TYPE_INFO_MASK_PATTERN = 0x5412;
108
IsEmpty(int32_t value)109 bool IsEmpty(int32_t value) {
110 return (uint8_t)value == 0xff;
111 }
112
IsValidValue(int32_t value)113 bool IsValidValue(int32_t value) {
114 return ((uint8_t)value == 0xff || (uint8_t)value == 0x00 ||
115 (uint8_t)value == 0x01);
116 }
117
FindMSBSet(int32_t value)118 int32_t FindMSBSet(int32_t value) {
119 int32_t numDigits = 0;
120 while (value != 0) {
121 value >>= 1;
122 ++numDigits;
123 }
124 return numDigits;
125 }
126
EmbedDataBits(CBC_QRCoderBitVector * dataBits,int32_t maskPattern,CBC_CommonByteMatrix * matrix)127 bool EmbedDataBits(CBC_QRCoderBitVector* dataBits,
128 int32_t maskPattern,
129 CBC_CommonByteMatrix* matrix) {
130 size_t szBitIndex = 0;
131 int32_t direction = -1;
132 int32_t x = matrix->GetWidth() - 1;
133 int32_t y = matrix->GetHeight() - 1;
134 while (x > 0) {
135 if (x == 6)
136 x -= 1;
137
138 while (y >= 0 && y < static_cast<int32_t>(matrix->GetHeight())) {
139 if (y == 6) {
140 y += direction;
141 continue;
142 }
143 for (int32_t i = 0; i < 2; i++) {
144 int32_t xx = x - i;
145 if (!IsEmpty(matrix->Get(xx, y))) {
146 continue;
147 }
148 int32_t bit;
149 if (szBitIndex < dataBits->Size()) {
150 bit = dataBits->At(szBitIndex);
151 szBitIndex++;
152 } else {
153 bit = 0;
154 }
155 DCHECK(CBC_QRCoder::IsValidMaskPattern(maskPattern));
156 if (CBC_QRCoderMaskUtil::GetDataMaskBit(maskPattern, xx, y))
157 bit ^= 0x01;
158 matrix->Set(xx, y, bit);
159 }
160 y += direction;
161 }
162 direction = -direction;
163 y += direction;
164 x -= 2;
165 }
166 return szBitIndex == dataBits->Size();
167 }
168
CalculateBCHCode(int32_t value,int32_t poly)169 int32_t CalculateBCHCode(int32_t value, int32_t poly) {
170 int32_t msbSetInPoly = FindMSBSet(poly);
171 value <<= msbSetInPoly - 1;
172 while (FindMSBSet(value) >= msbSetInPoly) {
173 value ^= poly << (FindMSBSet(value) - msbSetInPoly);
174 }
175 return value;
176 }
177
MakeTypeInfoBits(const CBC_QRCoderErrorCorrectionLevel * ecLevel,int32_t maskPattern,CBC_QRCoderBitVector * bits)178 bool MakeTypeInfoBits(const CBC_QRCoderErrorCorrectionLevel* ecLevel,
179 int32_t maskPattern,
180 CBC_QRCoderBitVector* bits) {
181 if (!CBC_QRCoder::IsValidMaskPattern(maskPattern))
182 return false;
183
184 int32_t typeInfo = (ecLevel->GetBits() << 3) | maskPattern;
185 bits->AppendBits(typeInfo, 5);
186 int32_t bchCode = CalculateBCHCode(typeInfo, TYPE_INFO_POLY);
187 bits->AppendBits(bchCode, 10);
188 CBC_QRCoderBitVector maskBits;
189 maskBits.AppendBits(TYPE_INFO_MASK_PATTERN, 15);
190 if (!bits->XOR(&maskBits))
191 return false;
192
193 DCHECK_EQ(bits->Size(), 15);
194 return true;
195 }
196
MakeVersionInfoBits(int32_t version,CBC_QRCoderBitVector * bits)197 void MakeVersionInfoBits(int32_t version, CBC_QRCoderBitVector* bits) {
198 bits->AppendBits(version, 6);
199 int32_t bchCode = CalculateBCHCode(version, VERSION_INFO_POLY);
200 bits->AppendBits(bchCode, 12);
201 DCHECK_EQ(bits->Size(), 18);
202 }
203
EmbedTypeInfo(const CBC_QRCoderErrorCorrectionLevel * ecLevel,int32_t maskPattern,CBC_CommonByteMatrix * matrix)204 bool EmbedTypeInfo(const CBC_QRCoderErrorCorrectionLevel* ecLevel,
205 int32_t maskPattern,
206 CBC_CommonByteMatrix* matrix) {
207 CBC_QRCoderBitVector typeInfoBits;
208 if (!MakeTypeInfoBits(ecLevel, maskPattern, &typeInfoBits))
209 return false;
210
211 for (size_t i = 0; i < typeInfoBits.Size(); i++) {
212 int32_t bit = typeInfoBits.At(typeInfoBits.Size() - 1 - i);
213 int32_t x1 = kTypeInfoCoordinates[i].x;
214 int32_t y1 = kTypeInfoCoordinates[i].y;
215 matrix->Set(x1, y1, bit);
216 if (i < 8) {
217 int32_t x2 = matrix->GetWidth() - i - 1;
218 int32_t y2 = 8;
219 matrix->Set(x2, y2, bit);
220 } else {
221 int32_t x2 = 8;
222 int32_t y2 = matrix->GetHeight() - 7 + (i - 8);
223 matrix->Set(x2, y2, bit);
224 }
225 }
226 return true;
227 }
228
MaybeEmbedVersionInfo(int32_t version,CBC_CommonByteMatrix * matrix)229 void MaybeEmbedVersionInfo(int32_t version, CBC_CommonByteMatrix* matrix) {
230 if (version < 7)
231 return;
232
233 CBC_QRCoderBitVector versionInfoBits;
234 MakeVersionInfoBits(version, &versionInfoBits);
235 int32_t bitIndex = 6 * 3 - 1;
236 for (int32_t i = 0; i < 6; i++) {
237 for (int32_t j = 0; j < 3; j++) {
238 int32_t bit = versionInfoBits.At(bitIndex);
239 bitIndex--;
240 matrix->Set(i, matrix->GetHeight() - 11 + j, bit);
241 matrix->Set(matrix->GetHeight() - 11 + j, i, bit);
242 }
243 }
244 }
245
EmbedTimingPatterns(CBC_CommonByteMatrix * matrix)246 bool EmbedTimingPatterns(CBC_CommonByteMatrix* matrix) {
247 for (size_t i = 8; i + 8 < matrix->GetWidth(); i++) {
248 const uint8_t bit = static_cast<uint8_t>((i + 1) % 2);
249 if (!IsValidValue(matrix->Get(i, 6)))
250 return false;
251
252 if (IsEmpty(matrix->Get(i, 6)))
253 matrix->Set(i, 6, bit);
254
255 if (!IsValidValue(matrix->Get(6, i)))
256 return false;
257
258 if (IsEmpty(matrix->Get(6, i)))
259 matrix->Set(6, i, bit);
260 }
261 return true;
262 }
263
EmbedDarkDotAtLeftBottomCorner(CBC_CommonByteMatrix * matrix)264 bool EmbedDarkDotAtLeftBottomCorner(CBC_CommonByteMatrix* matrix) {
265 if (matrix->Get(8, matrix->GetHeight() - 8) == 0)
266 return false;
267
268 matrix->Set(8, matrix->GetHeight() - 8, 1);
269 return true;
270 }
271
EmbedHorizontalSeparationPattern(int32_t xStart,int32_t yStart,CBC_CommonByteMatrix * matrix)272 bool EmbedHorizontalSeparationPattern(int32_t xStart,
273 int32_t yStart,
274 CBC_CommonByteMatrix* matrix) {
275 for (int32_t x = 0; x < 8; x++) {
276 if (!IsEmpty(matrix->Get(xStart + x, yStart)))
277 return false;
278
279 matrix->Set(xStart + x, yStart, 0);
280 }
281 return true;
282 }
283
EmbedVerticalSeparationPattern(int32_t xStart,int32_t yStart,CBC_CommonByteMatrix * matrix)284 bool EmbedVerticalSeparationPattern(int32_t xStart,
285 int32_t yStart,
286 CBC_CommonByteMatrix* matrix) {
287 for (int32_t y = 0; y < 7; y++) {
288 if (!IsEmpty(matrix->Get(xStart, yStart + y)))
289 return false;
290
291 matrix->Set(xStart, yStart + y, 0);
292 }
293 return true;
294 }
295
EmbedPositionAdjustmentPattern(int32_t xStart,int32_t yStart,CBC_CommonByteMatrix * matrix)296 bool EmbedPositionAdjustmentPattern(int32_t xStart,
297 int32_t yStart,
298 CBC_CommonByteMatrix* matrix) {
299 for (int32_t y = 0; y < 5; y++) {
300 for (int32_t x = 0; x < 5; x++) {
301 if (!IsEmpty(matrix->Get(xStart + x, y + yStart))) {
302 return false;
303 }
304 matrix->Set(xStart + x, yStart + y,
305 kPositionAdjustmentPatternTable[y][x]);
306 }
307 }
308 return true;
309 }
310
EmbedPositionDetectionPattern(int32_t xStart,int32_t yStart,CBC_CommonByteMatrix * matrix)311 bool EmbedPositionDetectionPattern(int32_t xStart,
312 int32_t yStart,
313 CBC_CommonByteMatrix* matrix) {
314 for (int32_t y = 0; y < 7; y++) {
315 for (int32_t x = 0; x < 7; x++) {
316 if (!IsEmpty(matrix->Get(xStart + x, yStart + y)))
317 return false;
318
319 matrix->Set(xStart + x, yStart + y, kPositionDetectionPatternTable[y][x]);
320 }
321 }
322 return true;
323 }
324
EmbedPositionDetectionPatternsAndSeparators(CBC_CommonByteMatrix * matrix)325 bool EmbedPositionDetectionPatternsAndSeparators(CBC_CommonByteMatrix* matrix) {
326 constexpr int32_t pdpWidth = 7;
327 if (!EmbedPositionDetectionPattern(0, 0, matrix))
328 return false;
329 if (!EmbedPositionDetectionPattern(matrix->GetWidth() - pdpWidth, 0, matrix))
330 return false;
331 if (!EmbedPositionDetectionPattern(0, matrix->GetWidth() - pdpWidth, matrix))
332 return false;
333
334 constexpr int32_t hspWidth = 8;
335 if (!EmbedHorizontalSeparationPattern(0, hspWidth - 1, matrix))
336 return false;
337 if (!EmbedHorizontalSeparationPattern(matrix->GetWidth() - hspWidth,
338 hspWidth - 1, matrix)) {
339 return false;
340 }
341 if (!EmbedHorizontalSeparationPattern(0, matrix->GetWidth() - hspWidth,
342 matrix)) {
343 return false;
344 }
345
346 constexpr int32_t vspSize = 7;
347 if (!EmbedVerticalSeparationPattern(vspSize, 0, matrix))
348 return false;
349 if (!EmbedVerticalSeparationPattern(matrix->GetHeight() - vspSize - 1, 0,
350 matrix)) {
351 return false;
352 }
353 if (!EmbedVerticalSeparationPattern(vspSize, matrix->GetHeight() - vspSize,
354 matrix)) {
355 return false;
356 }
357 return true;
358 }
359
MaybeEmbedPositionAdjustmentPatterns(int32_t version,CBC_CommonByteMatrix * matrix)360 bool MaybeEmbedPositionAdjustmentPatterns(int32_t version,
361 CBC_CommonByteMatrix* matrix) {
362 if (version < 2)
363 return true;
364
365 const size_t index = version - 2;
366 if (index >= std::size(kPositionCoordinatePatternTable)) {
367 return false;
368 }
369
370 const auto& coordinates = kPositionCoordinatePatternTable[index];
371 for (size_t i = 0; i < kNumCoordinate; i++) {
372 const int32_t y = coordinates[i];
373 if (y == 0)
374 break;
375 for (size_t j = 0; j < kNumCoordinate; j++) {
376 const int32_t x = coordinates[j];
377 if (x == 0)
378 break;
379
380 if (IsEmpty(matrix->Get(x, y))) {
381 if (!EmbedPositionAdjustmentPattern(x - 2, y - 2, matrix))
382 return false;
383 }
384 }
385 }
386 return true;
387 }
388
EmbedBasicPatterns(int32_t version,CBC_CommonByteMatrix * matrix)389 bool EmbedBasicPatterns(int32_t version, CBC_CommonByteMatrix* matrix) {
390 if (!EmbedPositionDetectionPatternsAndSeparators(matrix))
391 return false;
392 if (!EmbedDarkDotAtLeftBottomCorner(matrix))
393 return false;
394 if (!MaybeEmbedPositionAdjustmentPatterns(version, matrix))
395 return false;
396 if (!EmbedTimingPatterns(matrix))
397 return false;
398 return true;
399 }
400
401 } // namespace
402
BuildMatrix(CBC_QRCoderBitVector * dataBits,const CBC_QRCoderErrorCorrectionLevel * ecLevel,int32_t version,int32_t maskPattern,CBC_CommonByteMatrix * matrix)403 bool CBC_QRCoderMatrixUtil::BuildMatrix(
404 CBC_QRCoderBitVector* dataBits,
405 const CBC_QRCoderErrorCorrectionLevel* ecLevel,
406 int32_t version,
407 int32_t maskPattern,
408 CBC_CommonByteMatrix* matrix) {
409 if (!dataBits || !matrix)
410 return false;
411
412 matrix->Fill(0xff);
413
414 if (!EmbedBasicPatterns(version, matrix))
415 return false;
416 if (!EmbedTypeInfo(ecLevel, maskPattern, matrix))
417 return false;
418
419 MaybeEmbedVersionInfo(version, matrix);
420 return EmbedDataBits(dataBits, maskPattern, matrix);
421 }
422