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" 36 CBC_QRDetector::CBC_QRDetector(CBC_CommonBitMatrix* image) : m_image(image) {} 37 CBC_QRDetector::~CBC_QRDetector() {} 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 } 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 } 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 } 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 } 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 } 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 } 184 int32_t CBC_QRDetector::Round(FX_FLOAT d) { 185 return (int32_t)(d + 0.5f); 186 } 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 } 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 } 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