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 2009 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/src/fxbarcode/barcode.h"
24#include "xfa/src/fxbarcode/BC_ResultPoint.h"
25#include "xfa/src/fxbarcode/BC_BinaryBitmap.h"
26#include "xfa/src/fxbarcode/common/BC_CommonBitMatrix.h"
27#include "xfa/src/fxbarcode/common/BC_CommonBitArray.h"
28#include "BC_PDF417DetectorResult.h"
29#include "BC_PDF417Detector.h"
30#define INTERGER_MAX 2147483647
31int32_t CBC_Detector::INDEXES_START_PATTERN[] = {0, 4, 1, 5};
32int32_t CBC_Detector::INDEXES_STOP_PATTERN[] = {6, 2, 7, 3};
33int32_t CBC_Detector::INTEGER_MATH_SHIFT = 8;
34int32_t CBC_Detector::PATTERN_MATCH_RESULT_SCALE_FACTOR = 1
35                                                          << INTEGER_MATH_SHIFT;
36int32_t CBC_Detector::MAX_AVG_VARIANCE =
37    (int32_t)(PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.42f);
38int32_t CBC_Detector::MAX_INDIVIDUAL_VARIANCE =
39    (int32_t)(PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.8f);
40int32_t CBC_Detector::START_PATTERN[] = {8, 1, 1, 1, 1, 1, 1, 3};
41int32_t CBC_Detector::STOP_PATTERN[] = {7, 1, 1, 3, 1, 1, 1, 2, 1};
42int32_t CBC_Detector::MAX_PIXEL_DRIFT = 3;
43int32_t CBC_Detector::MAX_PATTERN_DRIFT = 5;
44int32_t CBC_Detector::SKIPPED_ROW_COUNT_MAX = 25;
45int32_t CBC_Detector::ROW_STEP = 5;
46int32_t CBC_Detector::BARCODE_MIN_HEIGHT = 10;
47CBC_Detector::CBC_Detector() {}
48CBC_Detector::~CBC_Detector() {}
49CBC_PDF417DetectorResult* CBC_Detector::detect(CBC_BinaryBitmap* image,
50                                               int32_t hints,
51                                               FX_BOOL multiple,
52                                               int32_t& e) {
53  CBC_CommonBitMatrix* bitMatrix = image->GetBlackMatrix(e);
54  BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
55  CFX_PtrArray* barcodeCoordinates = detect(multiple, bitMatrix);
56  if (barcodeCoordinates->GetSize() == 0) {
57    rotate180(bitMatrix);
58    barcodeCoordinates = detect(multiple, bitMatrix);
59  }
60  if (barcodeCoordinates->GetSize() == 0) {
61    e = BCExceptionUnSupportedBarcode;
62    BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
63  }
64  CBC_PDF417DetectorResult* detectorResult =
65      new CBC_PDF417DetectorResult(bitMatrix, barcodeCoordinates);
66  return detectorResult;
67}
68void CBC_Detector::rotate180(CBC_CommonBitMatrix* bitMatrix) {
69  int32_t width = bitMatrix->GetWidth();
70  int32_t height = bitMatrix->GetHeight();
71  CBC_CommonBitArray* firstRowBitArray = new CBC_CommonBitArray(width);
72  CBC_CommonBitArray* secondRowBitArray = new CBC_CommonBitArray(width);
73  CBC_CommonBitArray* tmpBitArray = new CBC_CommonBitArray(width);
74  for (int32_t y = 0; y<(height + 1)>> 1; y++) {
75    CBC_CommonBitArray* temp =
76        bitMatrix->GetRow(height - 1 - y, secondRowBitArray);
77    CBC_CommonBitArray* tempfirstRow = firstRowBitArray;
78    firstRowBitArray = bitMatrix->GetRow(y, tempfirstRow);
79    delete tempfirstRow;
80    CBC_CommonBitArray* row = mirror(temp, tmpBitArray);
81    delete temp;
82    bitMatrix->SetRow(y, row);
83    delete row;
84    CBC_CommonBitArray* rowfirstRow = mirror(firstRowBitArray, tmpBitArray);
85    bitMatrix->SetRow(height - 1 - y, rowfirstRow);
86    delete rowfirstRow;
87  }
88  delete tmpBitArray;
89  delete firstRowBitArray;
90  delete secondRowBitArray;
91}
92CBC_CommonBitArray* CBC_Detector::mirror(CBC_CommonBitArray* input,
93                                         CBC_CommonBitArray* result) {
94  CBC_CommonBitArray* array = new CBC_CommonBitArray(result->GetSize());
95  array->Clear();
96  int32_t size = input->GetSize();
97  for (int32_t i = 0; i < size; i++) {
98    if (input->Get(i)) {
99      array->Set(size - 1 - i);
100    }
101  }
102  return array;
103}
104CFX_PtrArray* CBC_Detector::detect(FX_BOOL multiple,
105                                   CBC_CommonBitMatrix* bitMatrix) {
106  CFX_PtrArray* barcodeCoordinates = new CFX_PtrArray;
107  int32_t row = 0;
108  int32_t column = 0;
109  FX_BOOL foundBarcodeInRow = FALSE;
110  while (row < bitMatrix->GetHeight()) {
111    CFX_PtrArray* vertices = findVertices(bitMatrix, row, column);
112    if (vertices->GetAt(0) == NULL && vertices->GetAt(3) == NULL) {
113      if (!foundBarcodeInRow) {
114        if (vertices) {
115          delete (vertices);
116        }
117        break;
118      }
119      foundBarcodeInRow = FALSE;
120      column = 0;
121      for (int32_t i = 0; i < barcodeCoordinates->GetSize(); i++) {
122        CFX_PtrArray* barcodeCoordinate =
123            (CFX_PtrArray*)barcodeCoordinates->GetAt(i);
124        if (barcodeCoordinate->GetAt(1) != NULL) {
125          row = row > ((CBC_ResultPoint*)barcodeCoordinate->GetAt(1))->GetY();
126        }
127        if (barcodeCoordinate->GetAt(3) != NULL) {
128          row = row > ((CBC_ResultPoint*)barcodeCoordinate->GetAt(3))->GetY();
129        }
130      }
131      row += ROW_STEP;
132      if (vertices) {
133        delete (vertices);
134      }
135      continue;
136    }
137    foundBarcodeInRow = TRUE;
138    barcodeCoordinates->Add(vertices);
139    if (!multiple) {
140      break;
141    }
142    if (vertices->GetAt(2) != NULL) {
143      column = (int32_t)((CBC_ResultPoint*)vertices->GetAt(2))->GetX();
144      row = (int32_t)((CBC_ResultPoint*)vertices->GetAt(2))->GetY();
145    } else {
146      column = (int32_t)((CBC_ResultPoint*)vertices->GetAt(4))->GetX();
147      row = (int32_t)((CBC_ResultPoint*)vertices->GetAt(4))->GetY();
148    }
149  }
150  return barcodeCoordinates;
151}
152CFX_PtrArray* CBC_Detector::findVertices(CBC_CommonBitMatrix* matrix,
153                                         int32_t startRow,
154                                         int32_t startColumn) {
155  int32_t height = matrix->GetHeight();
156  int32_t width = matrix->GetWidth();
157  CFX_PtrArray* result = new CFX_PtrArray;
158  result->SetSize(8);
159  CFX_PtrArray* startptr = findRowsWithPattern(
160      matrix, height, width, startRow, startColumn, START_PATTERN,
161      sizeof(START_PATTERN) / sizeof(START_PATTERN[0]));
162  copyToResult(
163      result, startptr, INDEXES_START_PATTERN,
164      sizeof(INDEXES_START_PATTERN) / sizeof(INDEXES_START_PATTERN[0]));
165  startptr->RemoveAll();
166  delete startptr;
167  if (result->GetAt(4) != NULL) {
168    startColumn = (int32_t)((CBC_ResultPoint*)result->GetAt(4))->GetX();
169    startRow = (int32_t)((CBC_ResultPoint*)result->GetAt(4))->GetY();
170  }
171  CFX_PtrArray* stopptr = findRowsWithPattern(
172      matrix, height, width, startRow, startColumn, STOP_PATTERN,
173      sizeof(STOP_PATTERN) / sizeof(STOP_PATTERN[0]));
174  copyToResult(result, stopptr, INDEXES_STOP_PATTERN,
175               sizeof(INDEXES_STOP_PATTERN) / sizeof(INDEXES_STOP_PATTERN[0]));
176  stopptr->RemoveAll();
177  delete stopptr;
178  return result;
179}
180void CBC_Detector::copyToResult(CFX_PtrArray* result,
181                                CFX_PtrArray* tmpResult,
182                                int32_t* destinationIndexes,
183                                int32_t destinationLength) {
184  for (int32_t i = 0; i < destinationLength; i++) {
185    result->SetAt(destinationIndexes[i], tmpResult->GetAt(i));
186  }
187}
188CFX_PtrArray* CBC_Detector::findRowsWithPattern(CBC_CommonBitMatrix* matrix,
189                                                int32_t height,
190                                                int32_t width,
191                                                int32_t startRow,
192                                                int32_t startColumn,
193                                                int32_t* pattern,
194                                                int32_t patternLength) {
195  CFX_PtrArray* result = new CFX_PtrArray;
196  result->SetSize(4);
197  FX_BOOL found = FALSE;
198  CFX_Int32Array counters;
199  counters.SetSize(patternLength);
200  for (; startRow < height; startRow += ROW_STEP) {
201    CFX_Int32Array* loc =
202        findGuardPattern(matrix, startColumn, startRow, width, FALSE, pattern,
203                         patternLength, counters);
204    if (loc != NULL) {
205      while (startRow > 0) {
206        CFX_Int32Array* previousRowLoc =
207            findGuardPattern(matrix, startColumn, --startRow, width, FALSE,
208                             pattern, patternLength, counters);
209        if (previousRowLoc != NULL) {
210          delete loc;
211          loc = previousRowLoc;
212        } else {
213          startRow++;
214          break;
215        }
216      }
217      result->SetAt(
218          0, new CBC_ResultPoint((FX_FLOAT)loc->GetAt(0), (FX_FLOAT)startRow));
219      result->SetAt(
220          1, new CBC_ResultPoint((FX_FLOAT)loc->GetAt(1), (FX_FLOAT)startRow));
221      found = TRUE;
222      delete loc;
223      break;
224    }
225  }
226  int32_t stopRow = startRow + 1;
227  if (found) {
228    int32_t skippedRowCount = 0;
229    CFX_Int32Array previousRowLoc;
230    previousRowLoc.Add((int32_t)((CBC_ResultPoint*)result->GetAt(0))->GetX());
231    previousRowLoc.Add((int32_t)((CBC_ResultPoint*)result->GetAt(1))->GetX());
232    for (; stopRow < height; stopRow++) {
233      CFX_Int32Array* loc =
234          findGuardPattern(matrix, previousRowLoc[0], stopRow, width, FALSE,
235                           pattern, patternLength, counters);
236      if (loc != NULL &&
237          abs(previousRowLoc[0] - loc->GetAt(0)) < MAX_PATTERN_DRIFT &&
238          abs(previousRowLoc[1] - loc->GetAt(1)) < MAX_PATTERN_DRIFT) {
239        previousRowLoc.Copy(*loc);
240        skippedRowCount = 0;
241      } else {
242        if (skippedRowCount > SKIPPED_ROW_COUNT_MAX) {
243          delete loc;
244          break;
245        } else {
246          skippedRowCount++;
247        }
248      }
249      delete loc;
250    }
251    stopRow -= skippedRowCount + 1;
252    result->SetAt(2, new CBC_ResultPoint((FX_FLOAT)previousRowLoc.GetAt(0),
253                                         (FX_FLOAT)stopRow));
254    result->SetAt(3, new CBC_ResultPoint((FX_FLOAT)previousRowLoc.GetAt(1),
255                                         (FX_FLOAT)stopRow));
256  }
257  if (stopRow - startRow < BARCODE_MIN_HEIGHT) {
258    for (int32_t i = 0; i < result->GetSize(); i++) {
259      result->SetAt(i, NULL);
260    }
261  }
262  return result;
263}
264CFX_Int32Array* CBC_Detector::findGuardPattern(CBC_CommonBitMatrix* matrix,
265                                               int32_t column,
266                                               int32_t row,
267                                               int32_t width,
268                                               FX_BOOL whiteFirst,
269                                               int32_t* pattern,
270                                               int32_t patternLength,
271                                               CFX_Int32Array& counters) {
272  for (int32_t i = 0; i < counters.GetSize(); i++) {
273    counters.SetAt(i, 0);
274  }
275  FX_BOOL isWhite = whiteFirst;
276  int32_t patternStart = column;
277  int32_t pixelDrift = 0;
278  CFX_Int32Array* intarray = new CFX_Int32Array;
279  while (matrix->Get(patternStart, row) && patternStart > 0 &&
280         pixelDrift++ < MAX_PIXEL_DRIFT) {
281    patternStart--;
282  }
283  int32_t x = patternStart;
284  int32_t counterPosition = 0;
285  for (; x < width; x++) {
286    FX_BOOL pixel = matrix->Get(x, row);
287    if (pixel ^ isWhite) {
288      counters[counterPosition]++;
289    } else {
290      if (counterPosition == patternLength - 1) {
291        if (patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE) <
292            MAX_AVG_VARIANCE) {
293          intarray->Add(patternStart);
294          intarray->Add(x);
295          return intarray;
296        }
297        patternStart += counters[0] + counters[1];
298        for (int32_t l = 2, k = 0; l < patternLength; l++, k++) {
299          counters.SetAt(k, counters.GetAt(l));
300        }
301        counters.SetAt(patternLength - 2, 0);
302        counters.SetAt(patternLength - 1, 0);
303        counterPosition--;
304      } else {
305        counterPosition++;
306      }
307      counters[counterPosition] = 1;
308      isWhite = !isWhite;
309    }
310  }
311  if (counterPosition == patternLength - 1) {
312    if (patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE) <
313        MAX_AVG_VARIANCE) {
314      intarray->Add(patternStart);
315      intarray->Add(x - 1);
316      return intarray;
317    }
318  }
319  delete intarray;
320  return NULL;
321}
322int32_t CBC_Detector::patternMatchVariance(CFX_Int32Array& counters,
323                                           int32_t* pattern,
324                                           int32_t maxIndividualVariance) {
325  int32_t numCounters = counters.GetSize();
326  int32_t total = 0;
327  int32_t patternLength = 0;
328  for (int32_t i = 0; i < numCounters; i++) {
329    total += counters[i];
330    patternLength += pattern[i];
331  }
332  if (total < patternLength) {
333    return INTERGER_MAX;
334  }
335  int32_t unitBarWidth = (total << INTEGER_MATH_SHIFT) / patternLength;
336  maxIndividualVariance =
337      (maxIndividualVariance * unitBarWidth) >> INTEGER_MATH_SHIFT;
338  int32_t totalVariance = 0;
339  for (int32_t x = 0; x < numCounters; x++) {
340    int32_t counter = counters[x] << INTEGER_MATH_SHIFT;
341    int32_t scaledPattern = pattern[x] * unitBarWidth;
342    int32_t variance = counter > scaledPattern ? counter - scaledPattern
343                                               : scaledPattern - counter;
344    if (variance > maxIndividualVariance) {
345      return INTERGER_MAX;
346    }
347    totalVariance += variance;
348  }
349  return totalVariance / total;
350}
351