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 <algorithm>
24
25#include "xfa/src/fxbarcode/barcode.h"
26#include "xfa/src/fxbarcode/common/BC_CommonBitMatrix.h"
27#include "xfa/src/fxbarcode/BC_ResultPoint.h"
28#include "BC_QRFinderPattern.h"
29#include "BC_QRCoderVersion.h"
30#include "BC_FinderPatternInfo.h"
31#include "BC_QRGridSampler.h"
32#include "BC_QRAlignmentPatternFinder.h"
33#include "BC_QRFinderPatternFinder.h"
34#include "BC_QRDetectorResult.h"
35#include "BC_QRDetector.h"
36CBC_QRDetector::CBC_QRDetector(CBC_CommonBitMatrix* image) : m_image(image) {}
37CBC_QRDetector::~CBC_QRDetector() {}
38CBC_QRDetectorResult* CBC_QRDetector::Detect(int32_t hints, int32_t& e) {
39  CBC_QRFinderPatternFinder finder(m_image);
40  CBC_QRFinderPatternInfo* qpi = finder.Find(hints, e);
41  BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
42  CBC_AutoPtr<CBC_QRFinderPatternInfo> info(qpi);
43  CBC_QRDetectorResult* qdr = ProcessFinderPatternInfo(info.get(), e);
44  BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
45  return qdr;
46}
47CBC_QRDetectorResult* CBC_QRDetector::ProcessFinderPatternInfo(
48    CBC_QRFinderPatternInfo* info,
49    int32_t& e) {
50  CBC_AutoPtr<CBC_QRFinderPattern> topLeft(info->GetTopLeft());
51  CBC_AutoPtr<CBC_QRFinderPattern> topRight(info->GetTopRight());
52  CBC_AutoPtr<CBC_QRFinderPattern> bottomLeft(info->GetBottomLeft());
53  FX_FLOAT moduleSize =
54      CalculateModuleSize(topLeft.get(), topRight.get(), bottomLeft.get());
55  if (moduleSize < 1.0f) {
56    e = BCExceptionRead;
57    BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
58  }
59  int32_t dimension = ComputeDimension(topLeft.get(), topRight.get(),
60                                       bottomLeft.get(), moduleSize, e);
61  BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
62  CBC_QRCoderVersion* provisionalVersion =
63      CBC_QRCoderVersion::GetProvisionalVersionForDimension(dimension, e);
64  BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
65  int32_t modulesBetweenFPCenters =
66      provisionalVersion->GetDimensionForVersion() - 7;
67  CBC_QRAlignmentPattern* alignmentPattern = NULL;
68  if (provisionalVersion->GetAlignmentPatternCenters()->GetSize() > 0) {
69    FX_FLOAT bottomRightX =
70        topRight->GetX() - topLeft->GetX() + bottomLeft->GetX();
71    FX_FLOAT bottomRightY =
72        topRight->GetY() - topLeft->GetY() + bottomLeft->GetY();
73    FX_FLOAT correctionToTopLeft =
74        1.0f - 3.0f / (FX_FLOAT)modulesBetweenFPCenters;
75    FX_FLOAT xtemp = (topLeft->GetX() +
76                      correctionToTopLeft * (bottomRightX - topLeft->GetX()));
77    int32_t estAlignmentX = (int32_t)xtemp;
78    FX_FLOAT ytemp = (topLeft->GetY() +
79                      correctionToTopLeft * (bottomRightY - topLeft->GetY()));
80    int32_t estAlignmentY = (int32_t)ytemp;
81    for (int32_t i = 4; i <= 16; i <<= 1) {
82      CBC_QRAlignmentPattern* temp = FindAlignmentInRegion(
83          moduleSize, estAlignmentX, estAlignmentY, (FX_FLOAT)i, e);
84      alignmentPattern = temp;
85      break;
86    }
87  }
88  CBC_CommonBitMatrix* bits =
89      SampleGrid(m_image, topLeft.get(), topRight.get(), bottomLeft.get(),
90                 (CBC_ResultPoint*)(alignmentPattern), dimension, e);
91  BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
92  CFX_PtrArray* points = new CFX_PtrArray;
93  if (alignmentPattern == NULL) {
94    points->Add(bottomLeft.release());
95    points->Add(topLeft.release());
96    points->Add(topRight.release());
97  } else {
98    points->Add(bottomLeft.release());
99    points->Add(topLeft.release());
100    points->Add(topRight.release());
101    points->Add(alignmentPattern);
102  }
103  return new CBC_QRDetectorResult(bits, points);
104}
105CBC_CommonBitMatrix* CBC_QRDetector::SampleGrid(
106    CBC_CommonBitMatrix* image,
107    CBC_ResultPoint* topLeft,
108    CBC_ResultPoint* topRight,
109    CBC_ResultPoint* bottomLeft,
110    CBC_ResultPoint* alignmentPattern,
111    int32_t dimension,
112    int32_t& e) {
113  FX_FLOAT dimMinusThree = (FX_FLOAT)dimension - 3.5f;
114  FX_FLOAT bottomRightX;
115  FX_FLOAT bottomRightY;
116  FX_FLOAT sourceBottomRightX;
117  FX_FLOAT sourceBottomRightY;
118  if (alignmentPattern != NULL) {
119    bottomRightX = alignmentPattern->GetX();
120    bottomRightY = alignmentPattern->GetY();
121    sourceBottomRightX = sourceBottomRightY = dimMinusThree - 3.0f;
122  } else {
123    bottomRightX = (topRight->GetX() - topLeft->GetX()) + bottomLeft->GetX();
124    bottomRightY = (topRight->GetY() - topLeft->GetY()) + bottomLeft->GetY();
125    sourceBottomRightX = sourceBottomRightY = dimMinusThree;
126  }
127  CBC_QRGridSampler& sampler = CBC_QRGridSampler::GetInstance();
128  CBC_CommonBitMatrix* cbm = sampler.SampleGrid(
129      image, dimension, dimension, 3.5f, 3.5f, dimMinusThree, 3.5f,
130      sourceBottomRightX, sourceBottomRightY, 3.5f, dimMinusThree,
131      topLeft->GetX(), topLeft->GetY(), topRight->GetX(), topRight->GetY(),
132      bottomRightX, bottomRightY, bottomLeft->GetX(), bottomLeft->GetY(), e);
133  BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
134  return cbm;
135}
136int32_t CBC_QRDetector::ComputeDimension(CBC_ResultPoint* topLeft,
137                                         CBC_ResultPoint* topRight,
138                                         CBC_ResultPoint* bottomLeft,
139                                         FX_FLOAT moduleSize,
140                                         int32_t& e) {
141  int32_t tltrCentersDimension = Round(
142      CBC_QRFinderPatternFinder::Distance(topLeft, topRight) / moduleSize);
143  int32_t tlblCentersDimension = Round(
144      CBC_QRFinderPatternFinder::Distance(topLeft, bottomLeft) / moduleSize);
145  int32_t dimension = ((tltrCentersDimension + tlblCentersDimension) >> 1) + 7;
146  switch (dimension & 0x03) {
147    case 0:
148      dimension++;
149      break;
150    case 2:
151      dimension--;
152      break;
153    case 3: {
154      e = BCExceptionRead;
155      BC_EXCEPTION_CHECK_ReturnValue(e, 0);
156    }
157  }
158  return dimension;
159}
160FX_FLOAT CBC_QRDetector::CalculateModuleSize(CBC_ResultPoint* topLeft,
161                                             CBC_ResultPoint* topRight,
162                                             CBC_ResultPoint* bottomLeft) {
163  return (CalculateModuleSizeOneWay(topLeft, topRight) +
164          CalculateModuleSizeOneWay(topLeft, bottomLeft)) /
165         2.0f;
166}
167FX_FLOAT CBC_QRDetector::CalculateModuleSizeOneWay(
168    CBC_ResultPoint* pattern,
169    CBC_ResultPoint* otherPattern) {
170  FX_FLOAT moduleSizeEst1 = SizeOfBlackWhiteBlackRunBothWays(
171      (int32_t)pattern->GetX(), (int32_t)pattern->GetY(),
172      (int32_t)otherPattern->GetX(), (int32_t)otherPattern->GetY());
173  FX_FLOAT moduleSizeEst2 = SizeOfBlackWhiteBlackRunBothWays(
174      (int32_t)otherPattern->GetX(), (int32_t)otherPattern->GetY(),
175      (int32_t)pattern->GetX(), (int32_t)pattern->GetY());
176  if (FXSYS_isnan(moduleSizeEst1)) {
177    return moduleSizeEst2;
178  }
179  if (FXSYS_isnan(moduleSizeEst2)) {
180    return moduleSizeEst1;
181  }
182  return (moduleSizeEst1 + moduleSizeEst2) / 14.0f;
183}
184int32_t CBC_QRDetector::Round(FX_FLOAT d) {
185  return (int32_t)(d + 0.5f);
186}
187FX_FLOAT CBC_QRDetector::SizeOfBlackWhiteBlackRunBothWays(int32_t fromX,
188                                                          int32_t fromY,
189                                                          int32_t toX,
190                                                          int32_t toY) {
191  FX_FLOAT result = SizeOfBlackWhiteBlackRun(fromX, fromY, toX, toY);
192  int32_t otherToX = fromX - (toX - fromX);
193  if (otherToX < 0) {
194    otherToX = -1;
195  } else if (otherToX >= m_image->GetWidth()) {
196    otherToX = m_image->GetWidth();
197  }
198  int32_t otherToY = fromY - (toY - fromY);
199  if (otherToY < 0) {
200    otherToY = -1;
201  } else if (otherToY >= m_image->GetHeight()) {
202    otherToY = m_image->GetHeight();
203  }
204  result += SizeOfBlackWhiteBlackRun(fromX, fromY, otherToX, otherToY);
205  return result - 1.0f;
206}
207FX_FLOAT CBC_QRDetector::SizeOfBlackWhiteBlackRun(int32_t fromX,
208                                                  int32_t fromY,
209                                                  int32_t toX,
210                                                  int32_t toY) {
211  FX_BOOL steep = FXSYS_abs(toY - fromY) > FXSYS_abs(toX - fromX);
212  if (steep) {
213    int32_t temp = fromX;
214    fromX = fromY;
215    fromY = temp;
216    temp = toX;
217    toX = toY;
218    toY = temp;
219  }
220  int32_t dx = FXSYS_abs(toX - fromX);
221  int32_t dy = FXSYS_abs(toY - fromY);
222  int32_t error = -dx >> 1;
223  int32_t ystep = fromY < toY ? 1 : -1;
224  int32_t xstep = fromX < toX ? 1 : -1;
225  int32_t state = 0;
226  for (int32_t x = fromX, y = fromY; x != toX; x += xstep) {
227    int32_t realX = steep ? y : x;
228    int32_t realY = steep ? x : y;
229    if (state == 1) {
230      if (m_image->Get(realX, realY)) {
231        state++;
232      }
233    } else {
234      if (!m_image->Get(realX, realY)) {
235        state++;
236      }
237    }
238    if (state == 3) {
239      int32_t diffX = x - fromX;
240      int32_t diffY = y - fromY;
241      return (FX_FLOAT)sqrt((double)(diffX * diffX + diffY * diffY));
242    }
243    error += dy;
244    if (error > 0) {
245      y += ystep;
246      error -= dx;
247    }
248  }
249  int32_t diffX = toX - fromX;
250  int32_t diffY = toY - fromY;
251  return (FX_FLOAT)sqrt((double)(diffX * diffX + diffY * diffY));
252}
253CBC_QRAlignmentPattern* CBC_QRDetector::FindAlignmentInRegion(
254    FX_FLOAT overallEstModuleSize,
255    int32_t estAlignmentX,
256    int32_t estAlignmentY,
257    FX_FLOAT allowanceFactor,
258    int32_t& e) {
259  int32_t allowance = (int32_t)(allowanceFactor * overallEstModuleSize);
260  int32_t alignmentAreaLeftX = std::max(0, estAlignmentX - allowance);
261  int32_t alignmentAreaRightX =
262      std::min(m_image->GetWidth() - 1, estAlignmentX + allowance);
263  if (alignmentAreaRightX - alignmentAreaLeftX < overallEstModuleSize * 3) {
264    e = BCExceptionRead;
265    BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
266  }
267  int32_t alignmentAreaTopY = std::max(0, estAlignmentY - allowance);
268  int32_t alignmentAreaBottomY =
269      std::min(m_image->GetHeight() - 1, estAlignmentY + allowance);
270  CBC_QRAlignmentPatternFinder alignmentFinder(
271      m_image, alignmentAreaLeftX, alignmentAreaTopY,
272      alignmentAreaRightX - alignmentAreaLeftX,
273      alignmentAreaBottomY - alignmentAreaTopY, overallEstModuleSize);
274  CBC_QRAlignmentPattern* qap = alignmentFinder.Find(e);
275  BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
276  return qap;
277}
278