Merge to XFA: Use stdint.h types throughout PDFium.
[pdfium.git] / xfa / src / fxbarcode / qrcode / BC_QRFinderPatternFinder.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 2007 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 "../common/BC_CommonBitMatrix.h"\r
26 #include "BC_QRFinderPatternFinder.h"\r
27 #include "BC_FinderPatternInfo.h"\r
28 #include "BC_QRFinderPattern.h"\r
29 const int32_t CBC_QRFinderPatternFinder::CENTER_QUORUM = 2;\r
30 const int32_t CBC_QRFinderPatternFinder::MIN_SKIP = 3;\r
31 const int32_t CBC_QRFinderPatternFinder::MAX_MODULES = 57;\r
32 const int32_t CBC_QRFinderPatternFinder::INTEGER_MATH_SHIFT = 8;\r
33 CBC_QRFinderPatternFinder::CBC_QRFinderPatternFinder(CBC_CommonBitMatrix* image)\r
34 {\r
35     m_image = image;\r
36     m_crossCheckStateCount.SetSize(5);\r
37     m_hasSkipped = FALSE;\r
38 }\r
39 CBC_QRFinderPatternFinder::~CBC_QRFinderPatternFinder()\r
40 {\r
41     for(int32_t i = 0; i < m_possibleCenters.GetSize(); i++) {\r
42         delete (CBC_QRFinderPattern*)m_possibleCenters[i];\r
43     }\r
44     m_possibleCenters.RemoveAll();\r
45 }\r
46 class ClosestToAverageComparator\r
47 {\r
48 private:\r
49     FX_FLOAT m_averageModuleSize;\r
50 public:\r
51     ClosestToAverageComparator(FX_FLOAT averageModuleSize) : m_averageModuleSize(averageModuleSize)\r
52     {\r
53     }\r
54     int32_t operator()(FinderPattern *a, FinderPattern *b)\r
55     {\r
56         FX_FLOAT dA = (FX_FLOAT)fabs(a->GetEstimatedModuleSize() - m_averageModuleSize);\r
57         FX_FLOAT dB = (FX_FLOAT)fabs(b->GetEstimatedModuleSize() - m_averageModuleSize);\r
58         return dA < dB ? -1 : dA > dB ? 1 : 0;\r
59     }\r
60 };\r
61 class CenterComparator\r
62 {\r
63 public:\r
64     int32_t operator()(FinderPattern *a, FinderPattern *b)\r
65     {\r
66         return b->GetCount() - a->GetCount();\r
67     }\r
68 };\r
69 CBC_CommonBitMatrix *CBC_QRFinderPatternFinder::GetImage()\r
70 {\r
71     return m_image;\r
72 }\r
73 CFX_Int32Array &CBC_QRFinderPatternFinder::GetCrossCheckStateCount()\r
74 {\r
75     m_crossCheckStateCount[0] = 0;\r
76     m_crossCheckStateCount[1] = 0;\r
77     m_crossCheckStateCount[2] = 0;\r
78     m_crossCheckStateCount[3] = 0;\r
79     m_crossCheckStateCount[4] = 0;\r
80     return m_crossCheckStateCount;\r
81 }\r
82 CFX_PtrArray *CBC_QRFinderPatternFinder::GetPossibleCenters()\r
83 {\r
84     return &m_possibleCenters;\r
85 }\r
86 CBC_QRFinderPatternInfo* CBC_QRFinderPatternFinder::Find(int32_t hint, int32_t &e)\r
87 {\r
88     int32_t maxI = m_image->GetHeight();\r
89     int32_t maxJ = m_image->GetWidth();\r
90     int32_t iSkip = (3 * maxI) / (4 * MAX_MODULES);\r
91     if(iSkip < MIN_SKIP || 0) {\r
92         iSkip = MIN_SKIP;\r
93     }\r
94     FX_BOOL done = FALSE;\r
95     CFX_Int32Array stateCount;\r
96     stateCount.SetSize(5);\r
97     for(int32_t i = iSkip - 1; i < maxI && !done; i += iSkip) {\r
98         stateCount[0] = 0;\r
99         stateCount[1] = 0;\r
100         stateCount[2] = 0;\r
101         stateCount[3] = 0;\r
102         stateCount[4] = 0;\r
103         int32_t currentState = 0;\r
104         for(int32_t j = 0; j < maxJ; j++) {\r
105             if(m_image->Get(j, i)) {\r
106                 if((currentState & 1) == 1) {\r
107                     currentState++;\r
108                 }\r
109                 stateCount[currentState]++;\r
110             } else {\r
111                 if((currentState & 1) == 0) {\r
112                     if(currentState == 4) {\r
113                         if(FoundPatternCross(stateCount)) {\r
114                             FX_BOOL confirmed = HandlePossibleCenter(stateCount, i, j);\r
115                             if(confirmed) {\r
116                                 iSkip = 2;\r
117                                 if(m_hasSkipped) {\r
118                                     done = HaveMultiplyConfirmedCenters();\r
119                                 } else {\r
120                                     int32_t rowSkip = FindRowSkip();\r
121                                     if(rowSkip > stateCount[2]) {\r
122                                         i += rowSkip - stateCount[2] - iSkip;\r
123                                         j = maxJ - 1;\r
124                                     }\r
125                                 }\r
126                             } else {\r
127                                 do {\r
128                                     j++;\r
129                                 } while (j < maxJ && !m_image->Get(j, i));\r
130                                 j--;\r
131                             }\r
132                             currentState = 0;\r
133                             stateCount[0] = 0;\r
134                             stateCount[1] = 0;\r
135                             stateCount[2] = 0;\r
136                             stateCount[3] = 0;\r
137                             stateCount[4] = 0;\r
138                         } else {\r
139                             stateCount[0] = stateCount[2];\r
140                             stateCount[1] = stateCount[3];\r
141                             stateCount[2] = stateCount[4];\r
142                             stateCount[3] = 1;\r
143                             stateCount[4] = 0;\r
144                             currentState = 3;\r
145                         }\r
146                     } else {\r
147                         stateCount[++currentState]++;\r
148                     }\r
149                 } else {\r
150                     stateCount[currentState]++;\r
151                 }\r
152             }\r
153         }\r
154         if(FoundPatternCross(stateCount)) {\r
155             FX_BOOL confirmed = HandlePossibleCenter(stateCount, i, maxJ);\r
156             if(confirmed) {\r
157                 iSkip = stateCount[0];\r
158                 if(m_hasSkipped) {\r
159                     done = HaveMultiplyConfirmedCenters();\r
160                 }\r
161             }\r
162         }\r
163     }\r
164     CFX_PtrArray* ptr = SelectBestpatterns(e);\r
165     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
166     CBC_AutoPtr<CFX_PtrArray > patternInfo(ptr);\r
167     OrderBestPatterns(patternInfo.get());\r
168     return new CBC_QRFinderPatternInfo(patternInfo.get());\r
169 }\r
170 void CBC_QRFinderPatternFinder::OrderBestPatterns(CFX_PtrArray *patterns)\r
171 {\r
172     FX_FLOAT abDistance = Distance((CBC_ResultPoint*)(*patterns)[0], (CBC_ResultPoint*)(*patterns)[1]);\r
173     FX_FLOAT bcDistance = Distance((CBC_ResultPoint*)(*patterns)[1], (CBC_ResultPoint*)(*patterns)[2]);\r
174     FX_FLOAT acDistance = Distance((CBC_ResultPoint*)(*patterns)[0], (CBC_ResultPoint*)(*patterns)[2]);\r
175     CBC_QRFinderPattern *topLeft, *topRight, *bottomLeft;\r
176     if (bcDistance >= abDistance && bcDistance >= acDistance) {\r
177         topLeft = (CBC_QRFinderPattern *)(*patterns)[0];\r
178         topRight = (CBC_QRFinderPattern *)(*patterns)[1];\r
179         bottomLeft = (CBC_QRFinderPattern *)(*patterns)[2];\r
180     } else if (acDistance >= bcDistance && acDistance >= abDistance) {\r
181         topLeft = (CBC_QRFinderPattern *)(*patterns)[1];\r
182         topRight = (CBC_QRFinderPattern *)(*patterns)[0];\r
183         bottomLeft = (CBC_QRFinderPattern *)(*patterns)[2];\r
184     } else {\r
185         topLeft = (CBC_QRFinderPattern *)(*patterns)[2];\r
186         topRight = (CBC_QRFinderPattern *)(*patterns)[0];\r
187         bottomLeft = (CBC_QRFinderPattern *)(*patterns)[1];\r
188     }\r
189     if ((bottomLeft->GetY() - topLeft->GetY()) * (topRight->GetX() - topLeft->GetX()) < (bottomLeft->GetX()\r
190             - topLeft->GetX()) * (topRight->GetY() - topLeft->GetY())) {\r
191         CBC_QRFinderPattern* temp = topRight;\r
192         topRight = bottomLeft;\r
193         bottomLeft = temp;\r
194     }\r
195     (*patterns)[0] = bottomLeft;\r
196     (*patterns)[1] = topLeft;\r
197     (*patterns)[2] = topRight;\r
198 }\r
199 FX_FLOAT CBC_QRFinderPatternFinder::Distance(CBC_ResultPoint* point1, CBC_ResultPoint* point2)\r
200 {\r
201     FX_FLOAT dx = point1->GetX() - point2->GetX();\r
202     FX_FLOAT dy = point1->GetY() - point2->GetY();\r
203     return (FX_FLOAT)FXSYS_sqrt(dx * dx + dy * dy);\r
204 }\r
205 FX_FLOAT CBC_QRFinderPatternFinder::CenterFromEnd(const CFX_Int32Array &stateCount, int32_t end)\r
206 {\r
207     return (FX_FLOAT)(end - stateCount[4] - stateCount[3]) - stateCount[2] / 2.0f;\r
208 }\r
209 FX_BOOL CBC_QRFinderPatternFinder::FoundPatternCross(const CFX_Int32Array &stateCount)\r
210 {\r
211     int32_t totalModuleSize = 0;\r
212     for (int32_t i = 0; i < 5; i++) {\r
213         int32_t count = stateCount[i];\r
214         if (count == 0) {\r
215             return FALSE;\r
216         }\r
217         totalModuleSize += count;\r
218     }\r
219     if (totalModuleSize < 7) {\r
220         return FALSE;\r
221     }\r
222     int32_t moduleSize = (totalModuleSize << INTEGER_MATH_SHIFT) / 7;\r
223     int32_t maxVariance = moduleSize / 2;\r
224     return FXSYS_abs(moduleSize - (stateCount[0] << INTEGER_MATH_SHIFT)) < maxVariance &&\r
225            FXSYS_abs(moduleSize - (stateCount[1] << INTEGER_MATH_SHIFT)) < maxVariance &&\r
226            FXSYS_abs(3 * moduleSize - (stateCount[2] << INTEGER_MATH_SHIFT)) < 3 * maxVariance &&\r
227            FXSYS_abs(moduleSize - (stateCount[3] << INTEGER_MATH_SHIFT)) < maxVariance &&\r
228            FXSYS_abs(moduleSize - (stateCount[4] << INTEGER_MATH_SHIFT)) < maxVariance;\r
229 }\r
230 FX_FLOAT CBC_QRFinderPatternFinder::CrossCheckVertical(int32_t startI, int32_t centerJ, int32_t maxCount,\r
231         int32_t originalStateCountTotal)\r
232 {\r
233     CBC_CommonBitMatrix *image = m_image;\r
234     int32_t maxI = image->GetHeight();\r
235     CFX_Int32Array &stateCount = GetCrossCheckStateCount();\r
236     int32_t i = startI;\r
237     while(i >= 0 && image->Get(centerJ, i)) {\r
238         stateCount[2]++;\r
239         i--;\r
240     }\r
241     if(i < 0) {\r
242         return FXSYS_nan();\r
243     }\r
244     while(i >= 0 && !image->Get(centerJ, i) && stateCount[1] <= maxCount) {\r
245         stateCount[1]++;\r
246         i--;\r
247     }\r
248     if(i < 0 || stateCount[1] > maxCount) {\r
249         return FXSYS_nan();\r
250     }\r
251     while(i >= 0 && image->Get(centerJ, i) && stateCount[0] <= maxCount) {\r
252         stateCount[0]++;\r
253         i--;\r
254     }\r
255     if(stateCount[0] > maxCount) {\r
256         return FXSYS_nan();\r
257     }\r
258     i = startI + 1;\r
259     while(i < maxI && image->Get(centerJ, i)) {\r
260         stateCount[2]++;\r
261         i++;\r
262     }\r
263     if(i == maxI) {\r
264         return FXSYS_nan();\r
265     }\r
266     while (i < maxI && !image->Get(centerJ, i) && stateCount[3] < maxCount) {\r
267         stateCount[3]++;\r
268         i++;\r
269     }\r
270     if (i == maxI || stateCount[3] >= maxCount) {\r
271         return FXSYS_nan();\r
272     }\r
273     while (i < maxI && image->Get(centerJ, i) && stateCount[4] < maxCount) {\r
274         stateCount[4]++;\r
275         i++;\r
276     }\r
277     if (stateCount[4] >= maxCount) {\r
278         return FXSYS_nan();\r
279     }\r
280     int32_t stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4];\r
281     if (5 * FXSYS_abs(stateCountTotal - originalStateCountTotal) >= originalStateCountTotal) {\r
282         return FXSYS_nan();\r
283     }\r
284     return FoundPatternCross(stateCount) ? CenterFromEnd(stateCount, i) : FXSYS_nan();\r
285 }\r
286 FX_FLOAT CBC_QRFinderPatternFinder::CrossCheckHorizontal(int32_t startJ, int32_t centerI, int32_t maxCount, int32_t originalStateCountTotal)\r
287 {\r
288     CBC_CommonBitMatrix *image = m_image;\r
289     int32_t maxJ = image->GetWidth();\r
290     CFX_Int32Array &stateCount = GetCrossCheckStateCount();\r
291     int32_t j = startJ;\r
292     while (j >= 0 && image->Get(j, centerI)) {\r
293         stateCount[2]++;\r
294         j--;\r
295     }\r
296     if (j < 0) {\r
297         return FXSYS_nan();\r
298     }\r
299     while (j >= 0 && !image->Get(j, centerI) && stateCount[1] <= maxCount) {\r
300         stateCount[1]++;\r
301         j--;\r
302     }\r
303     if (j < 0 || stateCount[1] > maxCount) {\r
304         return FXSYS_nan();\r
305     }\r
306     while (j >= 0 && image->Get(j, centerI) && stateCount[0] <= maxCount) {\r
307         stateCount[0]++;\r
308         j--;\r
309     }\r
310     if (stateCount[0] > maxCount) {\r
311         return FXSYS_nan();\r
312     }\r
313     j = startJ + 1;\r
314     while (j < maxJ && image->Get(j, centerI)) {\r
315         stateCount[2]++;\r
316         j++;\r
317     }\r
318     if (j == maxJ) {\r
319         return FXSYS_nan();\r
320     }\r
321     while (j < maxJ && !image->Get(j, centerI) && stateCount[3] < maxCount) {\r
322         stateCount[3]++;\r
323         j++;\r
324     }\r
325     if (j == maxJ || stateCount[3] >= maxCount) {\r
326         return FXSYS_nan();\r
327     }\r
328     while (j < maxJ && image->Get(j, centerI) && stateCount[4] < maxCount) {\r
329         stateCount[4]++;\r
330         j++;\r
331     }\r
332     if (stateCount[4] >= maxCount) {\r
333         return FXSYS_nan();\r
334     }\r
335     int32_t stateCountTotal = stateCount[0] + stateCount[1] +\r
336                                stateCount[2] + stateCount[3] +\r
337                                stateCount[4];\r
338     if (5 * FXSYS_abs(stateCountTotal - originalStateCountTotal) >= originalStateCountTotal) {\r
339         return FXSYS_nan();\r
340     }\r
341     return FoundPatternCross(stateCount) ? CenterFromEnd(stateCount, j) : FXSYS_nan();\r
342 }\r
343 FX_BOOL CBC_QRFinderPatternFinder::HandlePossibleCenter(const CFX_Int32Array &stateCount, int32_t i, int32_t j)\r
344 {\r
345     int32_t stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4];\r
346     FX_FLOAT centerJ = CenterFromEnd(stateCount, j);\r
347     FX_FLOAT centerI = CrossCheckVertical(i, (int32_t) centerJ, stateCount[2], stateCountTotal);\r
348     if(!FXSYS_isnan(centerI)) {\r
349         centerJ = CrossCheckHorizontal((int32_t) centerJ, (int32_t) centerI, stateCount[2], stateCountTotal);\r
350         if(!FXSYS_isnan(centerJ)) {\r
351             FX_FLOAT estimatedModuleSize = (FX_FLOAT) stateCountTotal / 7.0f;\r
352             FX_BOOL found = FALSE;\r
353             int32_t max = m_possibleCenters.GetSize();\r
354             for(int32_t index = 0; index < max; index++) {\r
355                 CBC_QRFinderPattern *center = (CBC_QRFinderPattern*)(m_possibleCenters[index]);\r
356                 if(center->AboutEquals(estimatedModuleSize, centerI, centerJ)) {\r
357                     center->IncrementCount();\r
358                     found = TRUE;\r
359                     break;\r
360                 }\r
361             }\r
362             if(!found) {\r
363                 m_possibleCenters.Add(FX_NEW CBC_QRFinderPattern(centerJ, centerI, estimatedModuleSize));\r
364             }\r
365             return TRUE;\r
366         }\r
367     }\r
368     return FALSE;\r
369 }\r
370 int32_t CBC_QRFinderPatternFinder::FindRowSkip()\r
371 {\r
372     int32_t max = m_possibleCenters.GetSize();\r
373     if (max <= 1) {\r
374         return 0;\r
375     }\r
376     FinderPattern *firstConfirmedCenter = NULL;\r
377     for (int32_t i = 0; i < max; i++) {\r
378         CBC_QRFinderPattern *center = (CBC_QRFinderPattern*)m_possibleCenters[i];\r
379         if (center->GetCount() >= CENTER_QUORUM) {\r
380             if (firstConfirmedCenter == NULL) {\r
381                 firstConfirmedCenter = center;\r
382             } else {\r
383                 m_hasSkipped = TRUE;\r
384                 return (int32_t) ((fabs(firstConfirmedCenter->GetX() - center->GetX()) -\r
385                                     fabs(firstConfirmedCenter->GetY() - center->GetY())) / 2);\r
386             }\r
387         }\r
388     }\r
389     return 0;\r
390 }\r
391 FX_BOOL CBC_QRFinderPatternFinder::HaveMultiplyConfirmedCenters()\r
392 {\r
393     int32_t confirmedCount = 0;\r
394     FX_FLOAT totalModuleSize = 0.0f;\r
395     int32_t max = m_possibleCenters.GetSize();\r
396     int32_t i;\r
397     for (i = 0; i < max; i++) {\r
398         CBC_QRFinderPattern *pattern = (CBC_QRFinderPattern*)m_possibleCenters[i];\r
399         if (pattern->GetCount() >= CENTER_QUORUM) {\r
400             confirmedCount++;\r
401             totalModuleSize += pattern->GetEstimatedModuleSize();\r
402         }\r
403     }\r
404     if (confirmedCount < 3) {\r
405         return FALSE;\r
406     }\r
407     FX_FLOAT average = totalModuleSize / (FX_FLOAT) max;\r
408     FX_FLOAT totalDeviation = 0.0f;\r
409     for (i = 0; i < max; i++) {\r
410         CBC_QRFinderPattern *pattern = (CBC_QRFinderPattern*)m_possibleCenters[i];\r
411         totalDeviation += fabs(pattern->GetEstimatedModuleSize() - average);\r
412     }\r
413     return totalDeviation <= 0.05f * totalModuleSize;\r
414 }\r
415 inline FX_BOOL centerComparator(FX_LPVOID a, FX_LPVOID b)\r
416 {\r
417     return ((CBC_QRFinderPattern*)b)->GetCount() < ((CBC_QRFinderPattern*)a)->GetCount();\r
418 }\r
419 CFX_PtrArray *CBC_QRFinderPatternFinder::SelectBestpatterns(int32_t &e)\r
420 {\r
421     int32_t startSize = m_possibleCenters.GetSize();\r
422     if(m_possibleCenters.GetSize() < 3) {\r
423         e = BCExceptionRead;\r
424         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
425     }\r
426     FX_FLOAT average = 0.0f;\r
427     if(startSize > 3) {\r
428         FX_FLOAT totalModuleSize = 0.0f;\r
429         for(int32_t i = 0; i < startSize; i++) {\r
430             totalModuleSize += ((CBC_QRFinderPattern*)m_possibleCenters[i])->GetEstimatedModuleSize();\r
431         }\r
432         average = totalModuleSize / (FX_FLOAT)startSize;\r
433         for(int32_t j = 0; j < m_possibleCenters.GetSize() && m_possibleCenters.GetSize() > 3; j++) {\r
434             CBC_QRFinderPattern *pattern = (CBC_QRFinderPattern*)m_possibleCenters[j];\r
435             if(fabs(pattern->GetEstimatedModuleSize() - average) > 0.2f * average) {\r
436                 delete pattern;\r
437                 m_possibleCenters.RemoveAt(j);\r
438                 j--;\r
439             }\r
440         }\r
441     }\r
442     if(m_possibleCenters.GetSize() > 3) {\r
443         BC_FX_PtrArray_Sort(m_possibleCenters, centerComparator);\r
444     }\r
445     CFX_PtrArray *vec = FX_NEW CFX_PtrArray();\r
446     vec->SetSize(3);\r
447     (*vec)[0] = ((CBC_QRFinderPattern*)m_possibleCenters[0])->Clone();\r
448     (*vec)[1] = ((CBC_QRFinderPattern*)m_possibleCenters[1])->Clone();\r
449     (*vec)[2] = ((CBC_QRFinderPattern*)m_possibleCenters[2])->Clone();\r
450     return vec;\r
451 }\r