summaryrefslogtreecommitdiff
path: root/xfa/fxbarcode/qrcode/BC_QRFinderPatternFinder.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'xfa/fxbarcode/qrcode/BC_QRFinderPatternFinder.cpp')
-rw-r--r--xfa/fxbarcode/qrcode/BC_QRFinderPatternFinder.cpp477
1 files changed, 477 insertions, 0 deletions
diff --git a/xfa/fxbarcode/qrcode/BC_QRFinderPatternFinder.cpp b/xfa/fxbarcode/qrcode/BC_QRFinderPatternFinder.cpp
new file mode 100644
index 0000000000..5ccbd9804b
--- /dev/null
+++ b/xfa/fxbarcode/qrcode/BC_QRFinderPatternFinder.cpp
@@ -0,0 +1,477 @@
+// Copyright 2014 PDFium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
+// Original code is licensed as follows:
+/*
+ * Copyright 2007 ZXing authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "xfa/fxbarcode/qrcode/BC_QRFinderPatternFinder.h"
+
+#include <memory>
+
+#include "core/include/fxcrt/fx_basic.h"
+#include "xfa/fxbarcode/BC_ResultPoint.h"
+#include "xfa/fxbarcode/common/BC_CommonBitMatrix.h"
+#include "xfa/fxbarcode/qrcode/BC_FinderPatternInfo.h"
+#include "xfa/fxbarcode/qrcode/BC_QRFinderPattern.h"
+#include "xfa/fxbarcode/utils.h"
+
+const int32_t CBC_QRFinderPatternFinder::CENTER_QUORUM = 2;
+const int32_t CBC_QRFinderPatternFinder::MIN_SKIP = 3;
+const int32_t CBC_QRFinderPatternFinder::MAX_MODULES = 57;
+const int32_t CBC_QRFinderPatternFinder::INTEGER_MATH_SHIFT = 8;
+
+CBC_QRFinderPatternFinder::CBC_QRFinderPatternFinder(
+ CBC_CommonBitMatrix* image) {
+ m_image = image;
+ m_crossCheckStateCount.SetSize(5);
+ m_hasSkipped = FALSE;
+}
+CBC_QRFinderPatternFinder::~CBC_QRFinderPatternFinder() {
+ for (int32_t i = 0; i < m_possibleCenters.GetSize(); i++) {
+ delete (CBC_QRFinderPattern*)m_possibleCenters[i];
+ }
+ m_possibleCenters.RemoveAll();
+}
+class ClosestToAverageComparator {
+ private:
+ FX_FLOAT m_averageModuleSize;
+
+ public:
+ ClosestToAverageComparator(FX_FLOAT averageModuleSize)
+ : m_averageModuleSize(averageModuleSize) {}
+ int32_t operator()(FinderPattern* a, FinderPattern* b) {
+ FX_FLOAT dA =
+ (FX_FLOAT)fabs(a->GetEstimatedModuleSize() - m_averageModuleSize);
+ FX_FLOAT dB =
+ (FX_FLOAT)fabs(b->GetEstimatedModuleSize() - m_averageModuleSize);
+ return dA < dB ? -1 : dA > dB ? 1 : 0;
+ }
+};
+class CenterComparator {
+ public:
+ int32_t operator()(FinderPattern* a, FinderPattern* b) {
+ return b->GetCount() - a->GetCount();
+ }
+};
+CBC_CommonBitMatrix* CBC_QRFinderPatternFinder::GetImage() {
+ return m_image;
+}
+CFX_Int32Array& CBC_QRFinderPatternFinder::GetCrossCheckStateCount() {
+ m_crossCheckStateCount[0] = 0;
+ m_crossCheckStateCount[1] = 0;
+ m_crossCheckStateCount[2] = 0;
+ m_crossCheckStateCount[3] = 0;
+ m_crossCheckStateCount[4] = 0;
+ return m_crossCheckStateCount;
+}
+CFX_PtrArray* CBC_QRFinderPatternFinder::GetPossibleCenters() {
+ return &m_possibleCenters;
+}
+CBC_QRFinderPatternInfo* CBC_QRFinderPatternFinder::Find(int32_t hint,
+ int32_t& e) {
+ int32_t maxI = m_image->GetHeight();
+ int32_t maxJ = m_image->GetWidth();
+ int32_t iSkip = (3 * maxI) / (4 * MAX_MODULES);
+ if (iSkip < MIN_SKIP || 0) {
+ iSkip = MIN_SKIP;
+ }
+ FX_BOOL done = FALSE;
+ CFX_Int32Array stateCount;
+ stateCount.SetSize(5);
+ for (int32_t i = iSkip - 1; i < maxI && !done; i += iSkip) {
+ stateCount[0] = 0;
+ stateCount[1] = 0;
+ stateCount[2] = 0;
+ stateCount[3] = 0;
+ stateCount[4] = 0;
+ int32_t currentState = 0;
+ for (int32_t j = 0; j < maxJ; j++) {
+ if (m_image->Get(j, i)) {
+ if ((currentState & 1) == 1) {
+ currentState++;
+ }
+ stateCount[currentState]++;
+ } else {
+ if ((currentState & 1) == 0) {
+ if (currentState == 4) {
+ if (FoundPatternCross(stateCount)) {
+ FX_BOOL confirmed = HandlePossibleCenter(stateCount, i, j);
+ if (confirmed) {
+ iSkip = 2;
+ if (m_hasSkipped) {
+ done = HaveMultiplyConfirmedCenters();
+ } else {
+ int32_t rowSkip = FindRowSkip();
+ if (rowSkip > stateCount[2]) {
+ i += rowSkip - stateCount[2] - iSkip;
+ j = maxJ - 1;
+ }
+ }
+ } else {
+ do {
+ j++;
+ } while (j < maxJ && !m_image->Get(j, i));
+ j--;
+ }
+ currentState = 0;
+ stateCount[0] = 0;
+ stateCount[1] = 0;
+ stateCount[2] = 0;
+ stateCount[3] = 0;
+ stateCount[4] = 0;
+ } else {
+ stateCount[0] = stateCount[2];
+ stateCount[1] = stateCount[3];
+ stateCount[2] = stateCount[4];
+ stateCount[3] = 1;
+ stateCount[4] = 0;
+ currentState = 3;
+ }
+ } else {
+ stateCount[++currentState]++;
+ }
+ } else {
+ stateCount[currentState]++;
+ }
+ }
+ }
+ if (FoundPatternCross(stateCount)) {
+ FX_BOOL confirmed = HandlePossibleCenter(stateCount, i, maxJ);
+ if (confirmed) {
+ iSkip = stateCount[0];
+ if (m_hasSkipped) {
+ done = HaveMultiplyConfirmedCenters();
+ }
+ }
+ }
+ }
+ std::unique_ptr<CFX_PtrArray> patternInfo(SelectBestpatterns(e));
+ BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
+ OrderBestPatterns(patternInfo.get());
+ return new CBC_QRFinderPatternInfo(patternInfo.get());
+}
+void CBC_QRFinderPatternFinder::OrderBestPatterns(CFX_PtrArray* patterns) {
+ FX_FLOAT abDistance = Distance((CBC_ResultPoint*)(*patterns)[0],
+ (CBC_ResultPoint*)(*patterns)[1]);
+ FX_FLOAT bcDistance = Distance((CBC_ResultPoint*)(*patterns)[1],
+ (CBC_ResultPoint*)(*patterns)[2]);
+ FX_FLOAT acDistance = Distance((CBC_ResultPoint*)(*patterns)[0],
+ (CBC_ResultPoint*)(*patterns)[2]);
+ CBC_QRFinderPattern *topLeft, *topRight, *bottomLeft;
+ if (bcDistance >= abDistance && bcDistance >= acDistance) {
+ topLeft = (CBC_QRFinderPattern*)(*patterns)[0];
+ topRight = (CBC_QRFinderPattern*)(*patterns)[1];
+ bottomLeft = (CBC_QRFinderPattern*)(*patterns)[2];
+ } else if (acDistance >= bcDistance && acDistance >= abDistance) {
+ topLeft = (CBC_QRFinderPattern*)(*patterns)[1];
+ topRight = (CBC_QRFinderPattern*)(*patterns)[0];
+ bottomLeft = (CBC_QRFinderPattern*)(*patterns)[2];
+ } else {
+ topLeft = (CBC_QRFinderPattern*)(*patterns)[2];
+ topRight = (CBC_QRFinderPattern*)(*patterns)[0];
+ bottomLeft = (CBC_QRFinderPattern*)(*patterns)[1];
+ }
+ if ((bottomLeft->GetY() - topLeft->GetY()) *
+ (topRight->GetX() - topLeft->GetX()) <
+ (bottomLeft->GetX() - topLeft->GetX()) *
+ (topRight->GetY() - topLeft->GetY())) {
+ CBC_QRFinderPattern* temp = topRight;
+ topRight = bottomLeft;
+ bottomLeft = temp;
+ }
+ (*patterns)[0] = bottomLeft;
+ (*patterns)[1] = topLeft;
+ (*patterns)[2] = topRight;
+}
+FX_FLOAT CBC_QRFinderPatternFinder::Distance(CBC_ResultPoint* point1,
+ CBC_ResultPoint* point2) {
+ FX_FLOAT dx = point1->GetX() - point2->GetX();
+ FX_FLOAT dy = point1->GetY() - point2->GetY();
+ return (FX_FLOAT)FXSYS_sqrt(dx * dx + dy * dy);
+}
+FX_FLOAT CBC_QRFinderPatternFinder::CenterFromEnd(
+ const CFX_Int32Array& stateCount,
+ int32_t end) {
+ return (FX_FLOAT)(end - stateCount[4] - stateCount[3]) - stateCount[2] / 2.0f;
+}
+FX_BOOL CBC_QRFinderPatternFinder::FoundPatternCross(
+ const CFX_Int32Array& stateCount) {
+ int32_t totalModuleSize = 0;
+ for (int32_t i = 0; i < 5; i++) {
+ int32_t count = stateCount[i];
+ if (count == 0) {
+ return FALSE;
+ }
+ totalModuleSize += count;
+ }
+ if (totalModuleSize < 7) {
+ return FALSE;
+ }
+ int32_t moduleSize = (totalModuleSize << INTEGER_MATH_SHIFT) / 7;
+ int32_t maxVariance = moduleSize / 2;
+ return FXSYS_abs(moduleSize - (stateCount[0] << INTEGER_MATH_SHIFT)) <
+ maxVariance &&
+ FXSYS_abs(moduleSize - (stateCount[1] << INTEGER_MATH_SHIFT)) <
+ maxVariance &&
+ FXSYS_abs(3 * moduleSize - (stateCount[2] << INTEGER_MATH_SHIFT)) <
+ 3 * maxVariance &&
+ FXSYS_abs(moduleSize - (stateCount[3] << INTEGER_MATH_SHIFT)) <
+ maxVariance &&
+ FXSYS_abs(moduleSize - (stateCount[4] << INTEGER_MATH_SHIFT)) <
+ maxVariance;
+}
+FX_FLOAT CBC_QRFinderPatternFinder::CrossCheckVertical(
+ int32_t startI,
+ int32_t centerJ,
+ int32_t maxCount,
+ int32_t originalStateCountTotal) {
+ CBC_CommonBitMatrix* image = m_image;
+ int32_t maxI = image->GetHeight();
+ CFX_Int32Array& stateCount = GetCrossCheckStateCount();
+ int32_t i = startI;
+ while (i >= 0 && image->Get(centerJ, i)) {
+ stateCount[2]++;
+ i--;
+ }
+ if (i < 0) {
+ return FXSYS_nan();
+ }
+ while (i >= 0 && !image->Get(centerJ, i) && stateCount[1] <= maxCount) {
+ stateCount[1]++;
+ i--;
+ }
+ if (i < 0 || stateCount[1] > maxCount) {
+ return FXSYS_nan();
+ }
+ while (i >= 0 && image->Get(centerJ, i) && stateCount[0] <= maxCount) {
+ stateCount[0]++;
+ i--;
+ }
+ if (stateCount[0] > maxCount) {
+ return FXSYS_nan();
+ }
+ i = startI + 1;
+ while (i < maxI && image->Get(centerJ, i)) {
+ stateCount[2]++;
+ i++;
+ }
+ if (i == maxI) {
+ return FXSYS_nan();
+ }
+ while (i < maxI && !image->Get(centerJ, i) && stateCount[3] < maxCount) {
+ stateCount[3]++;
+ i++;
+ }
+ if (i == maxI || stateCount[3] >= maxCount) {
+ return FXSYS_nan();
+ }
+ while (i < maxI && image->Get(centerJ, i) && stateCount[4] < maxCount) {
+ stateCount[4]++;
+ i++;
+ }
+ if (stateCount[4] >= maxCount) {
+ return FXSYS_nan();
+ }
+ int32_t stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] +
+ stateCount[3] + stateCount[4];
+ if (5 * FXSYS_abs(stateCountTotal - originalStateCountTotal) >=
+ originalStateCountTotal) {
+ return FXSYS_nan();
+ }
+ return FoundPatternCross(stateCount) ? CenterFromEnd(stateCount, i)
+ : FXSYS_nan();
+}
+FX_FLOAT CBC_QRFinderPatternFinder::CrossCheckHorizontal(
+ int32_t startJ,
+ int32_t centerI,
+ int32_t maxCount,
+ int32_t originalStateCountTotal) {
+ CBC_CommonBitMatrix* image = m_image;
+ int32_t maxJ = image->GetWidth();
+ CFX_Int32Array& stateCount = GetCrossCheckStateCount();
+ int32_t j = startJ;
+ while (j >= 0 && image->Get(j, centerI)) {
+ stateCount[2]++;
+ j--;
+ }
+ if (j < 0) {
+ return FXSYS_nan();
+ }
+ while (j >= 0 && !image->Get(j, centerI) && stateCount[1] <= maxCount) {
+ stateCount[1]++;
+ j--;
+ }
+ if (j < 0 || stateCount[1] > maxCount) {
+ return FXSYS_nan();
+ }
+ while (j >= 0 && image->Get(j, centerI) && stateCount[0] <= maxCount) {
+ stateCount[0]++;
+ j--;
+ }
+ if (stateCount[0] > maxCount) {
+ return FXSYS_nan();
+ }
+ j = startJ + 1;
+ while (j < maxJ && image->Get(j, centerI)) {
+ stateCount[2]++;
+ j++;
+ }
+ if (j == maxJ) {
+ return FXSYS_nan();
+ }
+ while (j < maxJ && !image->Get(j, centerI) && stateCount[3] < maxCount) {
+ stateCount[3]++;
+ j++;
+ }
+ if (j == maxJ || stateCount[3] >= maxCount) {
+ return FXSYS_nan();
+ }
+ while (j < maxJ && image->Get(j, centerI) && stateCount[4] < maxCount) {
+ stateCount[4]++;
+ j++;
+ }
+ if (stateCount[4] >= maxCount) {
+ return FXSYS_nan();
+ }
+ int32_t stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] +
+ stateCount[3] + stateCount[4];
+ if (5 * FXSYS_abs(stateCountTotal - originalStateCountTotal) >=
+ originalStateCountTotal) {
+ return FXSYS_nan();
+ }
+ return FoundPatternCross(stateCount) ? CenterFromEnd(stateCount, j)
+ : FXSYS_nan();
+}
+FX_BOOL CBC_QRFinderPatternFinder::HandlePossibleCenter(
+ const CFX_Int32Array& stateCount,
+ int32_t i,
+ int32_t j) {
+ int32_t stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] +
+ stateCount[3] + stateCount[4];
+ FX_FLOAT centerJ = CenterFromEnd(stateCount, j);
+ FX_FLOAT centerI =
+ CrossCheckVertical(i, (int32_t)centerJ, stateCount[2], stateCountTotal);
+ if (!FXSYS_isnan(centerI)) {
+ centerJ = CrossCheckHorizontal((int32_t)centerJ, (int32_t)centerI,
+ stateCount[2], stateCountTotal);
+ if (!FXSYS_isnan(centerJ)) {
+ FX_FLOAT estimatedModuleSize = (FX_FLOAT)stateCountTotal / 7.0f;
+ FX_BOOL found = FALSE;
+ int32_t max = m_possibleCenters.GetSize();
+ for (int32_t index = 0; index < max; index++) {
+ CBC_QRFinderPattern* center =
+ (CBC_QRFinderPattern*)(m_possibleCenters[index]);
+ if (center->AboutEquals(estimatedModuleSize, centerI, centerJ)) {
+ center->IncrementCount();
+ found = TRUE;
+ break;
+ }
+ }
+ if (!found) {
+ m_possibleCenters.Add(
+ new CBC_QRFinderPattern(centerJ, centerI, estimatedModuleSize));
+ }
+ return TRUE;
+ }
+ }
+ return FALSE;
+}
+int32_t CBC_QRFinderPatternFinder::FindRowSkip() {
+ int32_t max = m_possibleCenters.GetSize();
+ if (max <= 1) {
+ return 0;
+ }
+ FinderPattern* firstConfirmedCenter = NULL;
+ for (int32_t i = 0; i < max; i++) {
+ CBC_QRFinderPattern* center = (CBC_QRFinderPattern*)m_possibleCenters[i];
+ if (center->GetCount() >= CENTER_QUORUM) {
+ if (firstConfirmedCenter == NULL) {
+ firstConfirmedCenter = center;
+ } else {
+ m_hasSkipped = TRUE;
+ return (int32_t)((fabs(firstConfirmedCenter->GetX() - center->GetX()) -
+ fabs(firstConfirmedCenter->GetY() - center->GetY())) /
+ 2);
+ }
+ }
+ }
+ return 0;
+}
+FX_BOOL CBC_QRFinderPatternFinder::HaveMultiplyConfirmedCenters() {
+ int32_t confirmedCount = 0;
+ FX_FLOAT totalModuleSize = 0.0f;
+ int32_t max = m_possibleCenters.GetSize();
+ int32_t i;
+ for (i = 0; i < max; i++) {
+ CBC_QRFinderPattern* pattern = (CBC_QRFinderPattern*)m_possibleCenters[i];
+ if (pattern->GetCount() >= CENTER_QUORUM) {
+ confirmedCount++;
+ totalModuleSize += pattern->GetEstimatedModuleSize();
+ }
+ }
+ if (confirmedCount < 3) {
+ return FALSE;
+ }
+ FX_FLOAT average = totalModuleSize / (FX_FLOAT)max;
+ FX_FLOAT totalDeviation = 0.0f;
+ for (i = 0; i < max; i++) {
+ CBC_QRFinderPattern* pattern = (CBC_QRFinderPattern*)m_possibleCenters[i];
+ totalDeviation += fabs(pattern->GetEstimatedModuleSize() - average);
+ }
+ return totalDeviation <= 0.05f * totalModuleSize;
+}
+inline FX_BOOL centerComparator(void* a, void* b) {
+ return ((CBC_QRFinderPattern*)b)->GetCount() <
+ ((CBC_QRFinderPattern*)a)->GetCount();
+}
+CFX_PtrArray* CBC_QRFinderPatternFinder::SelectBestpatterns(int32_t& e) {
+ int32_t startSize = m_possibleCenters.GetSize();
+ if (m_possibleCenters.GetSize() < 3) {
+ e = BCExceptionRead;
+ BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
+ }
+ FX_FLOAT average = 0.0f;
+ if (startSize > 3) {
+ FX_FLOAT totalModuleSize = 0.0f;
+ for (int32_t i = 0; i < startSize; i++) {
+ totalModuleSize += ((CBC_QRFinderPattern*)m_possibleCenters[i])
+ ->GetEstimatedModuleSize();
+ }
+ average = totalModuleSize / (FX_FLOAT)startSize;
+ for (int32_t j = 0;
+ j < m_possibleCenters.GetSize() && m_possibleCenters.GetSize() > 3;
+ j++) {
+ CBC_QRFinderPattern* pattern = (CBC_QRFinderPattern*)m_possibleCenters[j];
+ if (fabs(pattern->GetEstimatedModuleSize() - average) > 0.2f * average) {
+ delete pattern;
+ m_possibleCenters.RemoveAt(j);
+ j--;
+ }
+ }
+ }
+ if (m_possibleCenters.GetSize() > 3) {
+ BC_FX_PtrArray_Sort(m_possibleCenters, centerComparator);
+ }
+ CFX_PtrArray* vec = new CFX_PtrArray();
+ vec->SetSize(3);
+ (*vec)[0] = ((CBC_QRFinderPattern*)m_possibleCenters[0])->Clone();
+ (*vec)[1] = ((CBC_QRFinderPattern*)m_possibleCenters[1])->Clone();
+ (*vec)[2] = ((CBC_QRFinderPattern*)m_possibleCenters[2])->Clone();
+ return vec;
+}