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
31 int32_t CBC_Detector::INDEXES_START_PATTERN[] = {0, 4, 1, 5};
32 int32_t CBC_Detector::INDEXES_STOP_PATTERN[] = {6, 2, 7, 3};
33 int32_t CBC_Detector::INTEGER_MATH_SHIFT = 8;
34 int32_t CBC_Detector::PATTERN_MATCH_RESULT_SCALE_FACTOR = 1
35                                                           << INTEGER_MATH_SHIFT;
36 int32_t CBC_Detector::MAX_AVG_VARIANCE =
37     (int32_t)(PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.42f);
38 int32_t CBC_Detector::MAX_INDIVIDUAL_VARIANCE =
39     (int32_t)(PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.8f);
40 int32_t CBC_Detector::START_PATTERN[] = {8, 1, 1, 1, 1, 1, 1, 3};
41 int32_t CBC_Detector::STOP_PATTERN[] = {7, 1, 1, 3, 1, 1, 1, 2, 1};
42 int32_t CBC_Detector::MAX_PIXEL_DRIFT = 3;
43 int32_t CBC_Detector::MAX_PATTERN_DRIFT = 5;
44 int32_t CBC_Detector::SKIPPED_ROW_COUNT_MAX = 25;
45 int32_t CBC_Detector::ROW_STEP = 5;
46 int32_t CBC_Detector::BARCODE_MIN_HEIGHT = 10;
CBC_Detector()47 CBC_Detector::CBC_Detector() {}
~CBC_Detector()48 CBC_Detector::~CBC_Detector() {}
detect(CBC_BinaryBitmap * image,int32_t hints,FX_BOOL multiple,int32_t & e)49 CBC_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 }
rotate180(CBC_CommonBitMatrix * bitMatrix)68 void 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 }
mirror(CBC_CommonBitArray * input,CBC_CommonBitArray * result)92 CBC_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 }
detect(FX_BOOL multiple,CBC_CommonBitMatrix * bitMatrix)104 CFX_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 }
findVertices(CBC_CommonBitMatrix * matrix,int32_t startRow,int32_t startColumn)152 CFX_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 }
copyToResult(CFX_PtrArray * result,CFX_PtrArray * tmpResult,int32_t * destinationIndexes,int32_t destinationLength)180 void 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 }
findRowsWithPattern(CBC_CommonBitMatrix * matrix,int32_t height,int32_t width,int32_t startRow,int32_t startColumn,int32_t * pattern,int32_t patternLength)188 CFX_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 }
findGuardPattern(CBC_CommonBitMatrix * matrix,int32_t column,int32_t row,int32_t width,FX_BOOL whiteFirst,int32_t * pattern,int32_t patternLength,CFX_Int32Array & counters)264 CFX_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 }
patternMatchVariance(CFX_Int32Array & counters,int32_t * pattern,int32_t maxIndividualVariance)322 int32_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