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"
29const int32_t CBC_QRFinderPatternFinder::CENTER_QUORUM = 2;
30const int32_t CBC_QRFinderPatternFinder::MIN_SKIP = 3;
31const int32_t CBC_QRFinderPatternFinder::MAX_MODULES = 57;
32const int32_t CBC_QRFinderPatternFinder::INTEGER_MATH_SHIFT = 8;
33CBC_QRFinderPatternFinder::CBC_QRFinderPatternFinder(
34    CBC_CommonBitMatrix* image) {
35  m_image = image;
36  m_crossCheckStateCount.SetSize(5);
37  m_hasSkipped = FALSE;
38}
39CBC_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}
45class ClosestToAverageComparator {
46 private:
47  FX_FLOAT m_averageModuleSize;
48
49 public:
50  ClosestToAverageComparator(FX_FLOAT averageModuleSize)
51      : m_averageModuleSize(averageModuleSize) {}
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};
60class CenterComparator {
61 public:
62  int32_t operator()(FinderPattern* a, FinderPattern* b) {
63    return b->GetCount() - a->GetCount();
64  }
65};
66CBC_CommonBitMatrix* CBC_QRFinderPatternFinder::GetImage() {
67  return m_image;
68}
69CFX_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}
77CFX_PtrArray* CBC_QRFinderPatternFinder::GetPossibleCenters() {
78  return &m_possibleCenters;
79}
80CBC_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}
164void 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}
197FX_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}
203FX_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}
208FX_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}
234FX_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}
295FX_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}
356FX_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}
390int32_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}
411FX_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}
434inline FX_BOOL centerComparator(void* a, void* b) {
435  return ((CBC_QRFinderPattern*)b)->GetCount() <
436         ((CBC_QRFinderPattern*)a)->GetCount();
437}
438CFX_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