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"
CBC_QRDetector(CBC_CommonBitMatrix * image)36 CBC_QRDetector::CBC_QRDetector(CBC_CommonBitMatrix* image) : m_image(image) {}
~CBC_QRDetector()37 CBC_QRDetector::~CBC_QRDetector() {}
Detect(int32_t hints,int32_t & e)38 CBC_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 }
ProcessFinderPatternInfo(CBC_QRFinderPatternInfo * info,int32_t & e)47 CBC_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 }
SampleGrid(CBC_CommonBitMatrix * image,CBC_ResultPoint * topLeft,CBC_ResultPoint * topRight,CBC_ResultPoint * bottomLeft,CBC_ResultPoint * alignmentPattern,int32_t dimension,int32_t & e)105 CBC_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 }
ComputeDimension(CBC_ResultPoint * topLeft,CBC_ResultPoint * topRight,CBC_ResultPoint * bottomLeft,FX_FLOAT moduleSize,int32_t & e)136 int32_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 }
CalculateModuleSize(CBC_ResultPoint * topLeft,CBC_ResultPoint * topRight,CBC_ResultPoint * bottomLeft)160 FX_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 }
CalculateModuleSizeOneWay(CBC_ResultPoint * pattern,CBC_ResultPoint * otherPattern)167 FX_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 }
Round(FX_FLOAT d)184 int32_t CBC_QRDetector::Round(FX_FLOAT d) {
185   return (int32_t)(d + 0.5f);
186 }
SizeOfBlackWhiteBlackRunBothWays(int32_t fromX,int32_t fromY,int32_t toX,int32_t toY)187 FX_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 }
SizeOfBlackWhiteBlackRun(int32_t fromX,int32_t fromY,int32_t toX,int32_t toY)207 FX_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 }
FindAlignmentInRegion(FX_FLOAT overallEstModuleSize,int32_t estAlignmentX,int32_t estAlignmentY,FX_FLOAT allowanceFactor,int32_t & e)253 CBC_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