Merge to XFA: Use stdint.h types throughout PDFium.
[pdfium.git] / xfa / src / fxbarcode / pdf417 / BC_PDF417Detector.cpp
1 // Copyright 2014 PDFium Authors. All rights reserved.\r
2 // Use of this source code is governed by a BSD-style license that can be\r
3 // found in the LICENSE file.\r
4 \r
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com\r
6 // Original code is licensed as follows:\r
7 /*\r
8  * Copyright 2009 ZXing authors\r
9  *\r
10  * Licensed under the Apache License, Version 2.0 (the "License");\r
11  * you may not use this file except in compliance with the License.\r
12  * You may obtain a copy of the License at\r
13  *\r
14  *      http://www.apache.org/licenses/LICENSE-2.0\r
15  *\r
16  * Unless required by applicable law or agreed to in writing, software\r
17  * distributed under the License is distributed on an "AS IS" BASIS,\r
18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
19  * See the License for the specific language governing permissions and\r
20  * limitations under the License.\r
21  */\r
22 \r
23 #include "../barcode.h"\r
24 #include "../BC_ResultPoint.h"\r
25 #include "../BC_BinaryBitmap.h"\r
26 #include "../common/BC_CommonBitMatrix.h"\r
27 #include "../common/BC_CommonBitArray.h"\r
28 #include "BC_PDF417DetectorResult.h"\r
29 #include "BC_PDF417Detector.h"\r
30 #define  INTERGER_MAX     2147483647\r
31 int32_t CBC_Detector::INDEXES_START_PATTERN[] = {0, 4, 1, 5};\r
32 int32_t CBC_Detector::INDEXES_STOP_PATTERN[] = {6, 2, 7, 3};\r
33 int32_t CBC_Detector::INTEGER_MATH_SHIFT = 8;\r
34 int32_t CBC_Detector::PATTERN_MATCH_RESULT_SCALE_FACTOR = 1 << INTEGER_MATH_SHIFT;\r
35 int32_t CBC_Detector::MAX_AVG_VARIANCE = (int32_t) (PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.42f);\r
36 int32_t CBC_Detector::MAX_INDIVIDUAL_VARIANCE = (int32_t) (PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.8f);\r
37 int32_t CBC_Detector::START_PATTERN[] = {8, 1, 1, 1, 1, 1, 1, 3};\r
38 int32_t CBC_Detector::STOP_PATTERN[] = {7, 1, 1, 3, 1, 1, 1, 2, 1};\r
39 int32_t CBC_Detector::MAX_PIXEL_DRIFT = 3;\r
40 int32_t CBC_Detector::MAX_PATTERN_DRIFT = 5;\r
41 int32_t CBC_Detector::SKIPPED_ROW_COUNT_MAX = 25;\r
42 int32_t CBC_Detector::ROW_STEP = 5;\r
43 int32_t CBC_Detector::BARCODE_MIN_HEIGHT = 10;\r
44 CBC_Detector::CBC_Detector()\r
45 {\r
46 }\r
47 CBC_Detector::~CBC_Detector()\r
48 {\r
49 }\r
50 CBC_PDF417DetectorResult* CBC_Detector::detect(CBC_BinaryBitmap* image, int32_t hints, FX_BOOL multiple, int32_t &e)\r
51 {\r
52     CBC_CommonBitMatrix* bitMatrix = image->GetBlackMatrix(e);\r
53     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
54     CFX_PtrArray* barcodeCoordinates = detect(multiple, bitMatrix);\r
55     if (barcodeCoordinates->GetSize() == 0) {\r
56         rotate180(bitMatrix);\r
57         barcodeCoordinates = detect(multiple, bitMatrix);\r
58     }\r
59     if (barcodeCoordinates->GetSize() == 0) {\r
60         e = BCExceptionUnSupportedBarcode;\r
61         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
62     }\r
63     CBC_PDF417DetectorResult* detectorResult = FX_NEW CBC_PDF417DetectorResult(bitMatrix, barcodeCoordinates);\r
64     return detectorResult;\r
65 }\r
66 void CBC_Detector::rotate180(CBC_CommonBitMatrix* bitMatrix)\r
67 {\r
68     int32_t width = bitMatrix->GetWidth();\r
69     int32_t height = bitMatrix->GetHeight();\r
70     CBC_CommonBitArray* firstRowBitArray = FX_NEW CBC_CommonBitArray(width);\r
71     CBC_CommonBitArray* secondRowBitArray = FX_NEW CBC_CommonBitArray(width);\r
72     CBC_CommonBitArray* tmpBitArray = FX_NEW CBC_CommonBitArray(width);\r
73     for (int32_t y = 0; y < (height + 1) >> 1; y++) {\r
74         CBC_CommonBitArray* temp = bitMatrix->GetRow(height - 1 - y, secondRowBitArray);\r
75         CBC_CommonBitArray* tempfirstRow = firstRowBitArray;\r
76         firstRowBitArray = bitMatrix->GetRow(y, tempfirstRow);\r
77         delete tempfirstRow;\r
78         CBC_CommonBitArray* row = mirror(temp, tmpBitArray);\r
79         delete temp;\r
80         bitMatrix->SetRow(y, row);\r
81         delete row;\r
82         CBC_CommonBitArray* rowfirstRow = mirror(firstRowBitArray, tmpBitArray);\r
83         bitMatrix->SetRow(height - 1 - y, rowfirstRow);\r
84         delete rowfirstRow;\r
85     }\r
86     delete tmpBitArray;\r
87     delete firstRowBitArray;\r
88     delete secondRowBitArray;\r
89 }\r
90 CBC_CommonBitArray* CBC_Detector::mirror(CBC_CommonBitArray* input, CBC_CommonBitArray* result)\r
91 {\r
92     CBC_CommonBitArray* array = FX_NEW CBC_CommonBitArray(result->GetSize());\r
93     array->Clear();\r
94     int32_t size = input->GetSize();\r
95     for (int32_t i = 0; i < size; i++) {\r
96         if (input->Get(i)) {\r
97             array->Set(size - 1 - i);\r
98         }\r
99     }\r
100     return array;\r
101 }\r
102 CFX_PtrArray* CBC_Detector::detect(FX_BOOL multiple, CBC_CommonBitMatrix* bitMatrix)\r
103 {\r
104     CFX_PtrArray* barcodeCoordinates = FX_NEW CFX_PtrArray;\r
105     int32_t row = 0;\r
106     int32_t column = 0;\r
107     FX_BOOL foundBarcodeInRow = FALSE;\r
108     while (row < bitMatrix->GetHeight()) {\r
109         CFX_PtrArray* vertices = findVertices(bitMatrix, row, column);\r
110         if (vertices->GetAt(0) == NULL && vertices->GetAt(3) == NULL) {\r
111             if (!foundBarcodeInRow) {\r
112                 if (vertices) {\r
113                     delete(vertices);\r
114                 }\r
115                 break;\r
116             }\r
117             foundBarcodeInRow = FALSE;\r
118             column = 0;\r
119             for (int32_t i = 0; i < barcodeCoordinates->GetSize(); i++) {\r
120                 CFX_PtrArray* barcodeCoordinate = (CFX_PtrArray*)barcodeCoordinates->GetAt(i);\r
121                 if (barcodeCoordinate->GetAt(1) != NULL) {\r
122                     row = row > ((CBC_ResultPoint*)barcodeCoordinate->GetAt(1))->GetY();\r
123                 }\r
124                 if (barcodeCoordinate->GetAt(3) != NULL) {\r
125                     row = row > ((CBC_ResultPoint*)barcodeCoordinate->GetAt(3))->GetY();\r
126                 }\r
127             }\r
128             row += ROW_STEP;\r
129             if (vertices) {\r
130                 delete(vertices);\r
131             }\r
132             continue;\r
133         }\r
134         foundBarcodeInRow = TRUE;\r
135         barcodeCoordinates->Add(vertices);\r
136         if (!multiple) {\r
137             break;\r
138         }\r
139         if (vertices->GetAt(2) != NULL) {\r
140             column = (int32_t) ((CBC_ResultPoint*)vertices->GetAt(2))->GetX();\r
141             row = (int32_t) ((CBC_ResultPoint*)vertices->GetAt(2))->GetY();\r
142         } else {\r
143             column = (int32_t) ((CBC_ResultPoint*)vertices->GetAt(4))->GetX();\r
144             row = (int32_t) ((CBC_ResultPoint*)vertices->GetAt(4))->GetY();\r
145         }\r
146     }\r
147     return barcodeCoordinates;\r
148 }\r
149 CFX_PtrArray* CBC_Detector::findVertices(CBC_CommonBitMatrix* matrix, int32_t startRow, int32_t startColumn)\r
150 {\r
151     int32_t height = matrix->GetHeight();\r
152     int32_t width = matrix->GetWidth();\r
153     CFX_PtrArray* result = FX_NEW CFX_PtrArray;\r
154     result->SetSize(8);\r
155     CFX_PtrArray* startptr =  findRowsWithPattern(matrix, height, width, startRow, startColumn, START_PATTERN, sizeof(START_PATTERN) / sizeof(START_PATTERN[0]));\r
156     copyToResult(result, startptr, INDEXES_START_PATTERN, sizeof(INDEXES_START_PATTERN) / sizeof(INDEXES_START_PATTERN[0]));\r
157     startptr->RemoveAll();\r
158     delete startptr;\r
159     if (result->GetAt(4) != NULL) {\r
160         startColumn = (int32_t) ((CBC_ResultPoint*)result->GetAt(4))->GetX();\r
161         startRow = (int32_t) ((CBC_ResultPoint*)result->GetAt(4))->GetY();\r
162     }\r
163     CFX_PtrArray*  stopptr = findRowsWithPattern(matrix, height, width, startRow, startColumn, STOP_PATTERN, sizeof(STOP_PATTERN) / sizeof(STOP_PATTERN[0]));\r
164     copyToResult(result, stopptr, INDEXES_STOP_PATTERN, sizeof(INDEXES_STOP_PATTERN) / sizeof(INDEXES_STOP_PATTERN[0]));\r
165     stopptr->RemoveAll();\r
166     delete stopptr;\r
167     return result;\r
168 }\r
169 void CBC_Detector::copyToResult(CFX_PtrArray *result, CFX_PtrArray* tmpResult, int32_t* destinationIndexes, int32_t destinationLength)\r
170 {\r
171     for (int32_t i = 0; i < destinationLength; i++) {\r
172         result->SetAt(destinationIndexes[i], tmpResult->GetAt(i));\r
173     }\r
174 }\r
175 CFX_PtrArray* CBC_Detector::findRowsWithPattern(CBC_CommonBitMatrix* matrix, int32_t height, int32_t width, int32_t startRow, int32_t startColumn, int32_t* pattern, int32_t patternLength)\r
176 {\r
177     CFX_PtrArray* result = FX_NEW CFX_PtrArray;\r
178     result->SetSize(4);\r
179     FX_BOOL found = FALSE;\r
180     CFX_Int32Array counters;\r
181     counters.SetSize(patternLength);\r
182     for (; startRow < height; startRow += ROW_STEP) {\r
183         CFX_Int32Array* loc = findGuardPattern(matrix, startColumn, startRow, width, FALSE, pattern, patternLength, counters);\r
184         if (loc != NULL) {\r
185             while (startRow > 0) {\r
186                 CFX_Int32Array* previousRowLoc = findGuardPattern(matrix, startColumn, --startRow, width, FALSE, pattern, patternLength, counters);\r
187                 if (previousRowLoc != NULL) {\r
188                     delete loc;\r
189                     loc = previousRowLoc;\r
190                 } else {\r
191                     startRow++;\r
192                     break;\r
193                 }\r
194             }\r
195             result->SetAt(0, FX_NEW CBC_ResultPoint((FX_FLOAT)loc->GetAt(0), (FX_FLOAT)startRow));\r
196             result->SetAt(1, FX_NEW CBC_ResultPoint((FX_FLOAT)loc->GetAt(1), (FX_FLOAT)startRow));\r
197             found = TRUE;\r
198             delete loc;\r
199             break;\r
200         }\r
201     }\r
202     int32_t stopRow = startRow + 1;\r
203     if (found) {\r
204         int32_t skippedRowCount = 0;\r
205         CFX_Int32Array previousRowLoc;\r
206         previousRowLoc.Add((int32_t)((CBC_ResultPoint*)result->GetAt(0))->GetX());\r
207         previousRowLoc.Add((int32_t)((CBC_ResultPoint*)result->GetAt(1))->GetX());\r
208         for (; stopRow < height; stopRow++) {\r
209             CFX_Int32Array* loc = findGuardPattern(matrix, previousRowLoc[0], stopRow, width, FALSE, pattern, patternLength, counters);\r
210             if (loc != NULL &&\r
211                     abs(previousRowLoc[0] - loc->GetAt(0)) < MAX_PATTERN_DRIFT &&\r
212                     abs(previousRowLoc[1] - loc->GetAt(1)) < MAX_PATTERN_DRIFT) {\r
213                 previousRowLoc.Copy(*loc);\r
214                 skippedRowCount = 0;\r
215             } else {\r
216                 if (skippedRowCount > SKIPPED_ROW_COUNT_MAX) {\r
217                     delete loc;\r
218                     break;\r
219                 } else {\r
220                     skippedRowCount++;\r
221                 }\r
222             }\r
223             delete loc;\r
224         }\r
225         stopRow -= skippedRowCount + 1;\r
226         result->SetAt(2, FX_NEW CBC_ResultPoint((FX_FLOAT)previousRowLoc.GetAt(0), (FX_FLOAT)stopRow));\r
227         result->SetAt(3, FX_NEW CBC_ResultPoint((FX_FLOAT)previousRowLoc.GetAt(1), (FX_FLOAT)stopRow));\r
228     }\r
229     if (stopRow - startRow < BARCODE_MIN_HEIGHT) {\r
230         for (int32_t i = 0; i < result->GetSize(); i++) {\r
231             result->SetAt(i, NULL);\r
232         }\r
233     }\r
234     return result;\r
235 }\r
236 CFX_Int32Array* CBC_Detector::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)\r
237 {\r
238     for (int32_t i = 0; i < counters.GetSize(); i++) {\r
239         counters.SetAt(i, 0);\r
240     }\r
241     FX_BOOL isWhite = whiteFirst;\r
242     int32_t patternStart = column;\r
243     int32_t pixelDrift = 0;\r
244     CFX_Int32Array* intarray = FX_NEW CFX_Int32Array;\r
245     while (matrix->Get(patternStart, row) && patternStart > 0 && pixelDrift++ < MAX_PIXEL_DRIFT) {\r
246         patternStart--;\r
247     }\r
248     int32_t x = patternStart;\r
249     int32_t counterPosition = 0;\r
250     for (; x < width; x++) {\r
251         FX_BOOL pixel = matrix->Get(x, row);\r
252         if (pixel ^ isWhite) {\r
253             counters[counterPosition]++;\r
254         } else {\r
255             if (counterPosition == patternLength - 1) {\r
256                 if (patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE) < MAX_AVG_VARIANCE) {\r
257                     intarray->Add(patternStart);\r
258                     intarray->Add(x);\r
259                     return intarray;\r
260                 }\r
261                 patternStart += counters[0] + counters[1];\r
262                 for (int32_t l = 2, k = 0; l < patternLength; l++, k++) {\r
263                     counters.SetAt(k, counters.GetAt(l));\r
264                 }\r
265                 counters.SetAt(patternLength - 2, 0);\r
266                 counters.SetAt(patternLength - 1, 0);\r
267                 counterPosition--;\r
268             } else {\r
269                 counterPosition++;\r
270             }\r
271             counters[counterPosition] = 1;\r
272             isWhite = !isWhite;\r
273         }\r
274     }\r
275     if (counterPosition == patternLength - 1) {\r
276         if (patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE) < MAX_AVG_VARIANCE) {\r
277             intarray->Add(patternStart);\r
278             intarray->Add(x - 1);\r
279             return intarray;\r
280         }\r
281     }\r
282     delete intarray;\r
283     return NULL;\r
284 }\r
285 int32_t CBC_Detector::patternMatchVariance(CFX_Int32Array &counters, int32_t* pattern, int32_t maxIndividualVariance)\r
286 {\r
287     int32_t numCounters = counters.GetSize();\r
288     int32_t total = 0;\r
289     int32_t patternLength = 0;\r
290     for (int32_t i = 0; i < numCounters; i++) {\r
291         total += counters[i];\r
292         patternLength += pattern[i];\r
293     }\r
294     if (total < patternLength) {\r
295         return INTERGER_MAX;\r
296     }\r
297     int32_t unitBarWidth = (total << INTEGER_MATH_SHIFT) / patternLength;\r
298     maxIndividualVariance = (maxIndividualVariance * unitBarWidth) >> INTEGER_MATH_SHIFT;\r
299     int32_t totalVariance = 0;\r
300     for (int32_t x = 0; x < numCounters; x++) {\r
301         int32_t counter = counters[x] << INTEGER_MATH_SHIFT;\r
302         int32_t scaledPattern = pattern[x] * unitBarWidth;\r
303         int32_t variance = counter > scaledPattern ? counter - scaledPattern : scaledPattern - counter;\r
304         if (variance > maxIndividualVariance) {\r
305             return INTERGER_MAX;\r
306         }\r
307         totalVariance += variance;\r
308     }\r
309     return totalVariance / total;\r
310 }\r
311 \r