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