BC_QRCoderMatrixUtil.cpp revision 4d3acf4ec42bf6e838f9060103aff98fbf170794 
1// Copyright 2014 PDFium Authors. All rights reserved.
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 "xfa/fxbarcode/common/BC_CommonByteMatrix.h"
24#include "xfa/fxbarcode/qrcode/BC_QRCoder.h"
25#include "xfa/fxbarcode/qrcode/BC_QRCoderBitVector.h"
26#include "xfa/fxbarcode/qrcode/BC_QRCoderErrorCorrectionLevel.h"
27#include "xfa/fxbarcode/qrcode/BC_QRCoderMaskUtil.h"
28#include "xfa/fxbarcode/qrcode/BC_QRCoderMatrixUtil.h"
29#include "xfa/fxbarcode/utils.h"
30
31const int32_t CBC_QRCoderMatrixUtil::POSITION_DETECTION_PATTERN[7][7] = {
32    {1, 1, 1, 1, 1, 1, 1}, {1, 0, 0, 0, 0, 0, 1}, {1, 0, 1, 1, 1, 0, 1},
33    {1, 0, 1, 1, 1, 0, 1}, {1, 0, 1, 1, 1, 0, 1}, {1, 0, 0, 0, 0, 0, 1},
34    {1, 1, 1, 1, 1, 1, 1}};
35const int32_t CBC_QRCoderMatrixUtil::HORIZONTAL_SEPARATION_PATTERN[1][8] = {
36    {0, 0, 0, 0, 0, 0, 0, 0}};
37const int32_t CBC_QRCoderMatrixUtil::VERTICAL_SEPARATION_PATTERN[7][1] = {
38    {0}, {0}, {0}, {0}, {0}, {0}, {0}};
39const int32_t CBC_QRCoderMatrixUtil::POSITION_ADJUSTMENT_PATTERN[5][5] = {
40    {1, 1, 1, 1, 1},
41    {1, 0, 0, 0, 1},
42    {1, 0, 1, 0, 1},
43    {1, 0, 0, 0, 1},
44    {1, 1, 1, 1, 1}};
45const int32_t
46    CBC_QRCoderMatrixUtil::POSITION_ADJUSTMENT_PATTERN_COORDINATE_TABLE[40][7] =
47        // NOLINTNEXTLINE
48    {
49        {-1, -1, -1, -1, -1, -1, -1},   {6, 18, -1, -1, -1, -1, -1},
50        {6, 22, -1, -1, -1, -1, -1},    {6, 26, -1, -1, -1, -1, -1},
51        {6, 30, -1, -1, -1, -1, -1},    {6, 34, -1, -1, -1, -1, -1},
52        {6, 22, 38, -1, -1, -1, -1},    {6, 24, 42, -1, -1, -1, -1},
53        {6, 26, 46, -1, -1, -1, -1},    {6, 28, 50, -1, -1, -1, -1},
54        {6, 30, 54, -1, -1, -1, -1},    {6, 32, 58, -1, -1, -1, -1},
55        {6, 34, 62, -1, -1, -1, -1},    {6, 26, 46, 66, -1, -1, -1},
56        {6, 26, 48, 70, -1, -1, -1},    {6, 26, 50, 74, -1, -1, -1},
57        {6, 30, 54, 78, -1, -1, -1},    {6, 30, 56, 82, -1, -1, -1},
58        {6, 30, 58, 86, -1, -1, -1},    {6, 34, 62, 90, -1, -1, -1},
59        {6, 28, 50, 72, 94, -1, -1},    {6, 26, 50, 74, 98, -1, -1},
60        {6, 30, 54, 78, 102, -1, -1},   {6, 28, 54, 80, 106, -1, -1},
61        {6, 32, 58, 84, 110, -1, -1},   {6, 30, 58, 86, 114, -1, -1},
62        {6, 34, 62, 90, 118, -1, -1},   {6, 26, 50, 74, 98, 122, -1},
63        {6, 30, 54, 78, 102, 126, -1},  {6, 26, 52, 78, 104, 130, -1},
64        {6, 30, 56, 82, 108, 134, -1},  {6, 34, 60, 86, 112, 138, -1},
65        {6, 30, 58, 86, 114, 142, -1},  {6, 34, 62, 90, 118, 146, -1},
66        {6, 30, 54, 78, 102, 126, 150}, {6, 24, 50, 76, 102, 128, 154},
67        {6, 28, 54, 80, 106, 132, 158}, {6, 32, 58, 84, 110, 136, 162},
68        {6, 26, 54, 82, 110, 138, 166}, {6, 30, 58, 86, 114, 142, 170},
69};
70const int32_t CBC_QRCoderMatrixUtil::TYPE_INFO_COORDINATES[15][2] = {
71    {8, 0}, {8, 1}, {8, 2}, {8, 3}, {8, 4}, {8, 5}, {8, 7}, {8, 8},
72    {7, 8}, {5, 8}, {4, 8}, {3, 8}, {2, 8}, {1, 8}, {0, 8},
73};
74const int32_t CBC_QRCoderMatrixUtil::VERSION_INFO_POLY = 0x1f25;
75const int32_t CBC_QRCoderMatrixUtil::TYPE_INFO_POLY = 0x0537;
76const int32_t CBC_QRCoderMatrixUtil::TYPE_INFO_MASK_PATTERN = 0x5412;
77
78void CBC_QRCoderMatrixUtil::ClearMatrix(CBC_CommonByteMatrix* matrix,
79                                        int32_t& e) {
80  if (!matrix) {
81    e = BCExceptionNullPointer;
82    BC_EXCEPTION_CHECK_ReturnVoid(e);
83  }
84  matrix->clear((uint8_t)-1);
85}
86void CBC_QRCoderMatrixUtil::BuildMatrix(
87    CBC_QRCoderBitVector* dataBits,
88    CBC_QRCoderErrorCorrectionLevel* ecLevel,
89    int32_t version,
90    int32_t maskPattern,
91    CBC_CommonByteMatrix* matrix,
92    int32_t& e) {
93  if (!matrix) {
94    e = BCExceptionNullPointer;
95    BC_EXCEPTION_CHECK_ReturnVoid(e);
96  }
97  ClearMatrix(matrix, e);
98  BC_EXCEPTION_CHECK_ReturnVoid(e);
99  EmbedBasicPatterns(version, matrix, e);
100  BC_EXCEPTION_CHECK_ReturnVoid(e);
101  EmbedTypeInfo(ecLevel, maskPattern, matrix, e);
102  BC_EXCEPTION_CHECK_ReturnVoid(e);
103  MaybeEmbedVersionInfo(version, matrix, e);
104  BC_EXCEPTION_CHECK_ReturnVoid(e);
105  EmbedDataBits(dataBits, maskPattern, matrix, e);
106  BC_EXCEPTION_CHECK_ReturnVoid(e);
107}
108void CBC_QRCoderMatrixUtil::EmbedBasicPatterns(int32_t version,
109                                               CBC_CommonByteMatrix* matrix,
110                                               int32_t& e) {
111  if (!matrix) {
112    e = BCExceptionNullPointer;
113    BC_EXCEPTION_CHECK_ReturnVoid(e);
114  }
115  EmbedPositionDetectionPatternsAndSeparators(matrix, e);
116  BC_EXCEPTION_CHECK_ReturnVoid(e);
117  EmbedDarkDotAtLeftBottomCorner(matrix, e);
118  BC_EXCEPTION_CHECK_ReturnVoid(e);
119  MaybeEmbedPositionAdjustmentPatterns(version, matrix, e);
120  BC_EXCEPTION_CHECK_ReturnVoid(e);
121  EmbedTimingPatterns(matrix, e);
122  BC_EXCEPTION_CHECK_ReturnVoid(e);
123}
124void CBC_QRCoderMatrixUtil::EmbedTypeInfo(
125    CBC_QRCoderErrorCorrectionLevel* ecLevel,
126    int32_t maskPattern,
127    CBC_CommonByteMatrix* matrix,
128    int32_t& e) {
129  if (!matrix) {
130    e = BCExceptionNullPointer;
131    BC_EXCEPTION_CHECK_ReturnVoid(e);
132  }
133  CBC_QRCoderBitVector typeInfoBits;
134  typeInfoBits.Init();
135  MakeTypeInfoBits(ecLevel, maskPattern, &typeInfoBits, e);
136  BC_EXCEPTION_CHECK_ReturnVoid(e);
137  for (int32_t i = 0; i < typeInfoBits.Size(); i++) {
138    int32_t bit = typeInfoBits.At(typeInfoBits.Size() - 1 - i, e);
139    BC_EXCEPTION_CHECK_ReturnVoid(e);
140    int32_t x1 = TYPE_INFO_COORDINATES[i][0];
141    int32_t y1 = TYPE_INFO_COORDINATES[i][1];
142    matrix->Set(x1, y1, bit);
143    if (i < 8) {
144      int32_t x2 = matrix->GetWidth() - i - 1;
145      int32_t y2 = 8;
146      matrix->Set(x2, y2, bit);
147    } else {
148      int32_t x2 = 8;
149      int32_t y2 = matrix->GetHeight() - 7 + (i - 8);
150      matrix->Set(x2, y2, bit);
151    }
152  }
153}
154void CBC_QRCoderMatrixUtil::MaybeEmbedVersionInfo(int32_t version,
155                                                  CBC_CommonByteMatrix* matrix,
156                                                  int32_t& e) {
157  if (!matrix) {
158    e = BCExceptionNullPointer;
159    BC_EXCEPTION_CHECK_ReturnVoid(e);
160  }
161  if (version < 7) {
162    return;
163  }
164  CBC_QRCoderBitVector versionInfoBits;
165  versionInfoBits.Init();
166  MakeVersionInfoBits(version, &versionInfoBits, e);
167  BC_EXCEPTION_CHECK_ReturnVoid(e);
168  int32_t bitIndex = 6 * 3 - 1;
169  for (int32_t i = 0; i < 6; i++) {
170    for (int32_t j = 0; j < 3; j++) {
171      int32_t bit = versionInfoBits.At(bitIndex, e);
172      BC_EXCEPTION_CHECK_ReturnVoid(e);
173      bitIndex--;
174      matrix->Set(i, matrix->GetHeight() - 11 + j, bit);
175      matrix->Set(matrix->GetHeight() - 11 + j, i, bit);
176    }
177  }
178}
179void CBC_QRCoderMatrixUtil::EmbedDataBits(CBC_QRCoderBitVector* dataBits,
180                                          int32_t maskPattern,
181                                          CBC_CommonByteMatrix* matrix,
182                                          int32_t& e) {
183  if (!matrix || !dataBits) {
184    e = BCExceptionNullPointer;
185    BC_EXCEPTION_CHECK_ReturnVoid(e);
186  }
187  int32_t bitIndex = 0;
188  int32_t direction = -1;
189  int32_t x = matrix->GetWidth() - 1;
190  int32_t y = matrix->GetHeight() - 1;
191  while (x > 0) {
192    if (x == 6) {
193      x -= 1;
194    }
195    while (y >= 0 && y < matrix->GetHeight()) {
196      if (y == 6) {
197        y += direction;
198        continue;
199      }
200      for (int32_t i = 0; i < 2; i++) {
201        int32_t xx = x - i;
202        if (!IsEmpty(matrix->Get(xx, y))) {
203          continue;
204        }
205        int32_t bit;
206        if (bitIndex < dataBits->Size()) {
207          bit = dataBits->At(bitIndex, e);
208          BC_EXCEPTION_CHECK_ReturnVoid(e);
209          bitIndex++;
210        } else {
211          bit = 0;
212        }
213        if (maskPattern != -1) {
214          bool bol = CBC_QRCoderMaskUtil::GetDataMaskBit(maskPattern, xx, y, e);
215          BC_EXCEPTION_CHECK_ReturnVoid(e);
216          if (bol) {
217            bit ^= 0x01;
218          }
219        }
220        matrix->Set(xx, y, bit);
221      }
222      y += direction;
223    }
224    direction = -direction;
225    y += direction;
226    x -= 2;
227  }
228  if (bitIndex != dataBits->Size()) {
229    return;
230  }
231}
232int32_t CBC_QRCoderMatrixUtil::CalculateBCHCode(int32_t value, int32_t poly) {
233  int32_t msbSetInPoly = FindMSBSet(poly);
234  value <<= msbSetInPoly - 1;
235  while (FindMSBSet(value) >= msbSetInPoly) {
236    value ^= poly << (FindMSBSet(value) - msbSetInPoly);
237  }
238  return value;
239}
240void CBC_QRCoderMatrixUtil::MakeTypeInfoBits(
241    CBC_QRCoderErrorCorrectionLevel* ecLevel,
242    int32_t maskPattern,
243    CBC_QRCoderBitVector* bits,
244    int32_t& e) {
245  if (!bits) {
246    e = BCExceptionNullPointer;
247    BC_EXCEPTION_CHECK_ReturnVoid(e);
248  }
249  if (!CBC_QRCoder::IsValidMaskPattern(maskPattern)) {
250    e = BCExceptionBadMask;
251    BC_EXCEPTION_CHECK_ReturnVoid(e);
252  }
253  int32_t typeInfo = (ecLevel->GetBits() << 3) | maskPattern;
254  BC_EXCEPTION_CHECK_ReturnVoid(e);
255  bits->AppendBits(typeInfo, 5, e);
256  int32_t bchCode = CalculateBCHCode(typeInfo, TYPE_INFO_POLY);
257  BC_EXCEPTION_CHECK_ReturnVoid(e);
258  bits->AppendBits(bchCode, 10, e);
259  CBC_QRCoderBitVector maskBits;
260  maskBits.Init();
261  maskBits.AppendBits(TYPE_INFO_MASK_PATTERN, 15, e);
262  BC_EXCEPTION_CHECK_ReturnVoid(e);
263  bits->XOR(&maskBits, e);
264  BC_EXCEPTION_CHECK_ReturnVoid(e);
265  if (bits->Size() != 15) {
266    e = BCExceptionBitSizeNot15;
267    BC_EXCEPTION_CHECK_ReturnVoid(e);
268  }
269}
270void CBC_QRCoderMatrixUtil::MakeVersionInfoBits(int32_t version,
271                                                CBC_QRCoderBitVector* bits,
272                                                int32_t& e) {
273  if (!bits) {
274    e = BCExceptionNullPointer;
275    BC_EXCEPTION_CHECK_ReturnVoid(e);
276  }
277  bits->AppendBits(version, 6, e);
278  BC_EXCEPTION_CHECK_ReturnVoid(e);
279  int32_t bchCode = CalculateBCHCode(version, VERSION_INFO_POLY);
280  bits->AppendBits(bchCode, 12, e);
281  BC_EXCEPTION_CHECK_ReturnVoid(e);
282  if (bits->Size() != 18) {
283    e = BCExceptionBitSizeNot18;
284    BC_EXCEPTION_CHECK_ReturnVoid(e);
285  }
286}
287bool CBC_QRCoderMatrixUtil::IsEmpty(int32_t value) {
288  return (uint8_t)value == 0xff;
289}
290bool CBC_QRCoderMatrixUtil::IsValidValue(int32_t value) {
291  return ((uint8_t)value == 0xff || (uint8_t)value == 0x00 ||
292          (uint8_t)value == 0x01);
293}
294void CBC_QRCoderMatrixUtil::EmbedTimingPatterns(CBC_CommonByteMatrix* matrix,
295                                                int32_t& e) {
296  if (!matrix) {
297    e = BCExceptionNullPointer;
298    BC_EXCEPTION_CHECK_ReturnVoid(e);
299  }
300  for (int32_t i = 8; i < matrix->GetWidth() - 8; i++) {
301    int32_t bit = (i + 1) % 2;
302    if (!IsValidValue(matrix->Get(i, 6))) {
303      e = BCExceptionInvalidateImageData;
304      BC_EXCEPTION_CHECK_ReturnVoid(e);
305    }
306    if (IsEmpty(matrix->Get(i, 6))) {
307      matrix->Set(i, 6, bit);
308    }
309    if (!IsValidValue(matrix->Get(6, i))) {
310      e = BCExceptionInvalidateImageData;
311      BC_EXCEPTION_CHECK_ReturnVoid(e);
312    }
313    if (IsEmpty(matrix->Get(6, i))) {
314      matrix->Set(6, i, bit);
315    }
316  }
317}
318void CBC_QRCoderMatrixUtil::EmbedDarkDotAtLeftBottomCorner(
319    CBC_CommonByteMatrix* matrix,
320    int32_t& e) {
321  if (!matrix) {
322    e = BCExceptionNullPointer;
323    BC_EXCEPTION_CHECK_ReturnVoid(e);
324  }
325  if (matrix->Get(8, matrix->GetHeight() - 8) == 0) {
326    e = BCExceptionHeight_8BeZero;
327    BC_EXCEPTION_CHECK_ReturnVoid(e);
328  }
329  matrix->Set(8, matrix->GetHeight() - 8, 1);
330}
331void CBC_QRCoderMatrixUtil::EmbedHorizontalSeparationPattern(
332    int32_t xStart,
333    int32_t yStart,
334    CBC_CommonByteMatrix* matrix,
335    int32_t& e) {
336  if (!matrix) {
337    e = BCExceptionNullPointer;
338    BC_EXCEPTION_CHECK_ReturnVoid(e);
339  }
340  for (int32_t x = 0; x < 8; x++) {
341    if (!IsEmpty(matrix->Get(xStart + x, yStart))) {
342      e = BCExceptionInvalidateData;
343      BC_EXCEPTION_CHECK_ReturnVoid(e)
344    }
345    matrix->Set(xStart + x, yStart, HORIZONTAL_SEPARATION_PATTERN[0][x]);
346  }
347}
348void CBC_QRCoderMatrixUtil::EmbedVerticalSeparationPattern(
349    int32_t xStart,
350    int32_t yStart,
351    CBC_CommonByteMatrix* matrix,
352    int32_t& e) {
353  if (!matrix) {
354    e = BCExceptionNullPointer;
355    BC_EXCEPTION_CHECK_ReturnVoid(e);
356  }
357  for (int32_t y = 0; y < 7; y++) {
358    if (!IsEmpty(matrix->Get(xStart, yStart + y))) {
359      e = BCExceptionInvalidateData;
360      BC_EXCEPTION_CHECK_ReturnVoid(e);
361    }
362    matrix->Set(xStart, yStart + y, VERTICAL_SEPARATION_PATTERN[y][0]);
363  }
364}
365void CBC_QRCoderMatrixUtil::EmbedPositionAdjustmentPattern(
366    int32_t xStart,
367    int32_t yStart,
368    CBC_CommonByteMatrix* matrix,
369    int32_t& e) {
370  if (!matrix) {
371    e = BCExceptionNullPointer;
372    BC_EXCEPTION_CHECK_ReturnVoid(e);
373  }
374  for (int32_t y = 0; y < 5; y++) {
375    for (int32_t x = 0; x < 5; x++) {
376      if (!IsEmpty(matrix->Get(xStart + x, y + yStart))) {
377        e = BCExceptionInvalidateData;
378        BC_EXCEPTION_CHECK_ReturnVoid(e);
379      }
380      matrix->Set(xStart + x, yStart + y, POSITION_ADJUSTMENT_PATTERN[y][x]);
381    }
382  }
383}
384void CBC_QRCoderMatrixUtil::EmbedPositionDetectionPattern(
385    int32_t xStart,
386    int32_t yStart,
387    CBC_CommonByteMatrix* matrix,
388    int32_t& e) {
389  if (!matrix) {
390    e = BCExceptionNullPointer;
391    BC_EXCEPTION_CHECK_ReturnVoid(e);
392  }
393  for (int32_t y = 0; y < 7; y++) {
394    for (int32_t x = 0; x < 7; x++) {
395      if (!IsEmpty(matrix->Get(xStart + x, yStart + y))) {
396        e = BCExceptionInvalidateData;
397        BC_EXCEPTION_CHECK_ReturnVoid(e);
398      }
399      matrix->Set(xStart + x, yStart + y, POSITION_DETECTION_PATTERN[y][x]);
400    }
401  }
402}
403void CBC_QRCoderMatrixUtil::EmbedPositionDetectionPatternsAndSeparators(
404    CBC_CommonByteMatrix* matrix,
405    int32_t& e) {
406  if (!matrix) {
407    e = BCExceptionNullPointer;
408    BC_EXCEPTION_CHECK_ReturnVoid(e);
409  }
410  int32_t pdpWidth = 7;
411  EmbedPositionDetectionPattern(0, 0, matrix, e);
412  BC_EXCEPTION_CHECK_ReturnVoid(e);
413  EmbedPositionDetectionPattern(matrix->GetWidth() - pdpWidth, 0, matrix, e);
414  BC_EXCEPTION_CHECK_ReturnVoid(e);
415  EmbedPositionDetectionPattern(0, matrix->GetWidth() - pdpWidth, matrix, e);
416  BC_EXCEPTION_CHECK_ReturnVoid(e);
417  int32_t hspWidth = 8;
418  EmbedHorizontalSeparationPattern(0, hspWidth - 1, matrix, e);
419  BC_EXCEPTION_CHECK_ReturnVoid(e);
420  EmbedHorizontalSeparationPattern(matrix->GetWidth() - hspWidth, hspWidth - 1,
421                                   matrix, e);
422  BC_EXCEPTION_CHECK_ReturnVoid(e);
423  EmbedHorizontalSeparationPattern(0, matrix->GetWidth() - hspWidth, matrix, e);
424  BC_EXCEPTION_CHECK_ReturnVoid(e);
425  int32_t vspSize = 7;
426  EmbedVerticalSeparationPattern(vspSize, 0, matrix, e);
427  BC_EXCEPTION_CHECK_ReturnVoid(e);
428  EmbedVerticalSeparationPattern(matrix->GetHeight() - vspSize - 1, 0, matrix,
429                                 e);
430  BC_EXCEPTION_CHECK_ReturnVoid(e);
431  EmbedVerticalSeparationPattern(vspSize, matrix->GetHeight() - vspSize, matrix,
432                                 e);
433  BC_EXCEPTION_CHECK_ReturnVoid(e);
434}
435void CBC_QRCoderMatrixUtil::MaybeEmbedPositionAdjustmentPatterns(
436    int32_t version,
437    CBC_CommonByteMatrix* matrix,
438    int32_t& e) {
439  if (!matrix) {
440    e = BCExceptionNullPointer;
441    BC_EXCEPTION_CHECK_ReturnVoid(e);
442  }
443  if (version < 2) {
444    return;
445  }
446  int32_t index = version - 1;
447  int32_t const* coordinates =
448      &(POSITION_ADJUSTMENT_PATTERN_COORDINATE_TABLE[index][0]);
449  int32_t numCoordinate = 7;
450  for (int32_t i = 0; i < numCoordinate; i++) {
451    for (int32_t j = 0; j < numCoordinate; j++) {
452      int32_t y = coordinates[i];
453      int32_t x = coordinates[j];
454      if (x == -1 || y == -1) {
455        continue;
456      }
457      if (IsEmpty(matrix->Get(x, y))) {
458        EmbedPositionAdjustmentPattern(x - 2, y - 2, matrix, e);
459        BC_EXCEPTION_CHECK_ReturnVoid(e);
460      }
461    }
462  }
463}
464int32_t CBC_QRCoderMatrixUtil::FindMSBSet(int32_t value) {
465  int32_t numDigits = 0;
466  while (value != 0) {
467    value >>= 1;
468    ++numDigits;
469  }
470  return numDigits;
471}
472CBC_QRCoderMatrixUtil::CBC_QRCoderMatrixUtil() {}
473CBC_QRCoderMatrixUtil::~CBC_QRCoderMatrixUtil() {}
474