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