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 2008 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/BC_ResultPoint.h"
27#include "xfa/src/fxbarcode/common/BC_WhiteRectangleDetector.h"
28#include "xfa/src/fxbarcode/common/BC_CommonBitMatrix.h"
29#include "xfa/src/fxbarcode/qrcode/BC_QRFinderPatternFinder.h"
30#include "xfa/src/fxbarcode/qrcode/BC_QRDetectorResult.h"
31#include "xfa/src/fxbarcode/qrcode/BC_QRGridSampler.h"
32#include "BC_DataMatrixDetector.h"
33const int32_t CBC_DataMatrixDetector::INTEGERS[5] = {0, 1, 2, 3, 4};
34CBC_DataMatrixDetector::CBC_DataMatrixDetector(CBC_CommonBitMatrix* image)
35    : m_image(image), m_rectangleDetector(NULL) {}
36void CBC_DataMatrixDetector::Init(int32_t& e) {
37  m_rectangleDetector = new CBC_WhiteRectangleDetector(m_image);
38  m_rectangleDetector->Init(e);
39  BC_EXCEPTION_CHECK_ReturnVoid(e);
40}
41CBC_DataMatrixDetector::~CBC_DataMatrixDetector() {
42  if (m_rectangleDetector != NULL) {
43    delete m_rectangleDetector;
44  }
45  m_rectangleDetector = NULL;
46}
47inline FX_BOOL ResultPointsAndTransitionsComparator(void* a, void* b) {
48  return ((CBC_ResultPointsAndTransitions*)b)->GetTransitions() >
49         ((CBC_ResultPointsAndTransitions*)a)->GetTransitions();
50}
51CBC_QRDetectorResult* CBC_DataMatrixDetector::Detect(int32_t& e) {
52  CFX_PtrArray* cornerPoints = m_rectangleDetector->Detect(e);
53  BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
54  CBC_ResultPoint* pointA = (CBC_ResultPoint*)(*cornerPoints)[0];
55  CBC_ResultPoint* pointB = (CBC_ResultPoint*)(*cornerPoints)[1];
56  CBC_ResultPoint* pointC = (CBC_ResultPoint*)(*cornerPoints)[2];
57  CBC_ResultPoint* pointD = (CBC_ResultPoint*)(*cornerPoints)[3];
58  delete cornerPoints;
59  cornerPoints = NULL;
60  CFX_PtrArray transitions;
61  transitions.Add(TransitionsBetween(pointA, pointB));
62  transitions.Add(TransitionsBetween(pointA, pointC));
63  transitions.Add(TransitionsBetween(pointB, pointD));
64  transitions.Add(TransitionsBetween(pointC, pointD));
65  BC_FX_PtrArray_Sort(transitions, &ResultPointsAndTransitionsComparator);
66  delete ((CBC_ResultPointsAndTransitions*)transitions[2]);
67  delete ((CBC_ResultPointsAndTransitions*)transitions[3]);
68  CBC_ResultPointsAndTransitions* lSideOne =
69      (CBC_ResultPointsAndTransitions*)transitions[0];
70  CBC_ResultPointsAndTransitions* lSideTwo =
71      (CBC_ResultPointsAndTransitions*)transitions[1];
72  CFX_MapPtrTemplate<CBC_ResultPoint*, int32_t> pointCount;
73  Increment(pointCount, lSideOne->GetFrom());
74  Increment(pointCount, lSideOne->GetTo());
75  Increment(pointCount, lSideTwo->GetFrom());
76  Increment(pointCount, lSideTwo->GetTo());
77  delete ((CBC_ResultPointsAndTransitions*)transitions[1]);
78  delete ((CBC_ResultPointsAndTransitions*)transitions[0]);
79  transitions.RemoveAll();
80  CBC_ResultPoint* maybeTopLeft = NULL;
81  CBC_ResultPoint* bottomLeft = NULL;
82  CBC_ResultPoint* maybeBottomRight = NULL;
83  FX_POSITION itBegin = pointCount.GetStartPosition();
84  while (itBegin != NULL) {
85    CBC_ResultPoint* key = 0;
86    int32_t value = 0;
87    pointCount.GetNextAssoc(itBegin, key, value);
88    if (value == 2) {
89      bottomLeft = key;
90    } else {
91      if (maybeBottomRight == NULL) {
92        maybeBottomRight = key;
93      } else {
94        maybeTopLeft = key;
95      }
96    }
97  }
98  if (maybeTopLeft == NULL || bottomLeft == NULL || maybeBottomRight == NULL) {
99    delete pointA;
100    delete pointB;
101    delete pointC;
102    delete pointD;
103    e = BCExceptionNotFound;
104    return NULL;
105  }
106  CFX_PtrArray corners;
107  corners.SetSize(3);
108  corners[0] = maybeTopLeft;
109  corners[1] = bottomLeft;
110  corners[2] = maybeBottomRight;
111  OrderBestPatterns(&corners);
112  CBC_ResultPoint* bottomRight = (CBC_ResultPoint*)corners[0];
113  bottomLeft = (CBC_ResultPoint*)corners[1];
114  CBC_ResultPoint* topLeft = (CBC_ResultPoint*)corners[2];
115  CBC_ResultPoint* topRight = NULL;
116  int32_t value;
117  if (!pointCount.Lookup(pointA, value)) {
118    topRight = pointA;
119  } else if (!pointCount.Lookup(pointB, value)) {
120    topRight = pointB;
121  } else if (!pointCount.Lookup(pointC, value)) {
122    topRight = pointC;
123  } else {
124    topRight = pointD;
125  }
126  int32_t dimensionTop = CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
127                             TransitionsBetween(topLeft, topRight))
128                             ->GetTransitions();
129  int32_t dimensionRight = CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
130                               TransitionsBetween(bottomRight, topRight))
131                               ->GetTransitions();
132  if ((dimensionTop & 0x01) == 1) {
133    dimensionTop++;
134  }
135  dimensionTop += 2;
136  if ((dimensionRight & 0x01) == 1) {
137    dimensionRight++;
138  }
139  dimensionRight += 2;
140  CBC_AutoPtr<CBC_CommonBitMatrix> bits(NULL);
141  CBC_AutoPtr<CBC_ResultPoint> correctedTopRight(NULL);
142  if (4 * dimensionTop >= 7 * dimensionRight ||
143      4 * dimensionRight >= 7 * dimensionTop) {
144    correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(
145        CorrectTopRightRectangular(bottomLeft, bottomRight, topLeft, topRight,
146                                   dimensionTop, dimensionRight));
147    if (correctedTopRight.get() == NULL) {
148      correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(topRight);
149    } else {
150      delete topRight;
151      topRight = NULL;
152    }
153    dimensionTop = CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
154                       TransitionsBetween(topLeft, correctedTopRight.get()))
155                       ->GetTransitions();
156    dimensionRight =
157        CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
158            TransitionsBetween(bottomRight, correctedTopRight.get()))
159            ->GetTransitions();
160    if ((dimensionTop & 0x01) == 1) {
161      dimensionTop++;
162    }
163    if ((dimensionRight & 0x01) == 1) {
164      dimensionRight++;
165    }
166    bits = CBC_AutoPtr<CBC_CommonBitMatrix>(
167        SampleGrid(m_image, topLeft, bottomLeft, bottomRight,
168                   correctedTopRight.get(), dimensionTop, dimensionRight, e));
169    BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
170  } else {
171    int32_t dimension = std::min(dimensionRight, dimensionTop);
172    correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(
173        CorrectTopRight(bottomLeft, bottomRight, topLeft, topRight, dimension));
174    if (correctedTopRight.get() == NULL) {
175      correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(topRight);
176    } else {
177      delete topRight;
178      topRight = NULL;
179    }
180    int32_t dimensionCorrected =
181        std::max(CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
182                     TransitionsBetween(topLeft, correctedTopRight.get()))
183                     ->GetTransitions(),
184                 CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
185                     TransitionsBetween(bottomRight, correctedTopRight.get()))
186                     ->GetTransitions());
187    dimensionCorrected++;
188    if ((dimensionCorrected & 0x01) == 1) {
189      dimensionCorrected++;
190    }
191    bits = CBC_AutoPtr<CBC_CommonBitMatrix>(SampleGrid(
192        m_image, topLeft, bottomLeft, bottomRight, correctedTopRight.get(),
193        dimensionCorrected, dimensionCorrected, e));
194    BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
195  }
196  CFX_PtrArray* result = new CFX_PtrArray;
197  result->SetSize(4);
198  result->Add(topLeft);
199  result->Add(bottomLeft);
200  result->Add(bottomRight);
201  result->Add(correctedTopRight.release());
202  return new CBC_QRDetectorResult(bits.release(), result);
203}
204CBC_ResultPoint* CBC_DataMatrixDetector::CorrectTopRightRectangular(
205    CBC_ResultPoint* bottomLeft,
206    CBC_ResultPoint* bottomRight,
207    CBC_ResultPoint* topLeft,
208    CBC_ResultPoint* topRight,
209    int32_t dimensionTop,
210    int32_t dimensionRight) {
211  FX_FLOAT corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT)dimensionTop;
212  int32_t norm = Distance(topLeft, topRight);
213  FX_FLOAT cos = (topRight->GetX() - topLeft->GetX()) / norm;
214  FX_FLOAT sin = (topRight->GetY() - topLeft->GetY()) / norm;
215  CBC_AutoPtr<CBC_ResultPoint> c1(new CBC_ResultPoint(
216      topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));
217  corr = Distance(bottomLeft, topLeft) / (FX_FLOAT)dimensionRight;
218  norm = Distance(bottomRight, topRight);
219  cos = (topRight->GetX() - bottomRight->GetX()) / norm;
220  sin = (topRight->GetY() - bottomRight->GetY()) / norm;
221  CBC_AutoPtr<CBC_ResultPoint> c2(new CBC_ResultPoint(
222      topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));
223  if (!IsValid(c1.get())) {
224    if (IsValid(c2.get())) {
225      return c2.release();
226    }
227    return NULL;
228  } else if (!IsValid(c2.get())) {
229    return c1.release();
230  }
231  int32_t l1 = FXSYS_abs(dimensionTop -
232                         CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
233                             TransitionsBetween(topLeft, c1.get()))
234                             ->GetTransitions()) +
235               FXSYS_abs(dimensionRight -
236                         CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
237                             TransitionsBetween(bottomRight, c1.get()))
238                             ->GetTransitions());
239  int32_t l2 = FXSYS_abs(dimensionTop -
240                         CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
241                             TransitionsBetween(topLeft, c2.get()))
242                             ->GetTransitions()) +
243               FXSYS_abs(dimensionRight -
244                         CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
245                             TransitionsBetween(bottomRight, c2.get()))
246                             ->GetTransitions());
247  if (l1 <= l2) {
248    return c1.release();
249  }
250  return c2.release();
251}
252CBC_ResultPoint* CBC_DataMatrixDetector::CorrectTopRight(
253    CBC_ResultPoint* bottomLeft,
254    CBC_ResultPoint* bottomRight,
255    CBC_ResultPoint* topLeft,
256    CBC_ResultPoint* topRight,
257    int32_t dimension) {
258  FX_FLOAT corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT)dimension;
259  int32_t norm = Distance(topLeft, topRight);
260  FX_FLOAT cos = (topRight->GetX() - topLeft->GetX()) / norm;
261  FX_FLOAT sin = (topRight->GetY() - topLeft->GetY()) / norm;
262  CBC_AutoPtr<CBC_ResultPoint> c1(new CBC_ResultPoint(
263      topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));
264  corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT)dimension;
265  norm = Distance(bottomRight, topRight);
266  cos = (topRight->GetX() - bottomRight->GetX()) / norm;
267  sin = (topRight->GetY() - bottomRight->GetY()) / norm;
268  CBC_AutoPtr<CBC_ResultPoint> c2(new CBC_ResultPoint(
269      topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));
270  if (!IsValid(c1.get())) {
271    if (IsValid(c2.get())) {
272      return c2.release();
273    }
274    return NULL;
275  } else if (!IsValid(c2.get())) {
276    return c1.release();
277  }
278  int32_t l1 = FXSYS_abs(CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
279                             TransitionsBetween(topLeft, c1.get()))
280                             ->GetTransitions() -
281                         CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
282                             TransitionsBetween(bottomRight, c1.get()))
283                             ->GetTransitions());
284  int32_t l2 = FXSYS_abs(CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
285                             TransitionsBetween(topLeft, c2.get()))
286                             ->GetTransitions() -
287                         CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
288                             TransitionsBetween(bottomRight, c2.get()))
289                             ->GetTransitions());
290  return l1 <= l2 ? c1.release() : c2.release();
291}
292FX_BOOL CBC_DataMatrixDetector::IsValid(CBC_ResultPoint* p) {
293  return p->GetX() >= 0 && p->GetX() < m_image->GetWidth() && p->GetY() > 0 &&
294         p->GetY() < m_image->GetHeight();
295}
296int32_t CBC_DataMatrixDetector::Round(FX_FLOAT d) {
297  return (int32_t)(d + 0.5f);
298}
299int32_t CBC_DataMatrixDetector::Distance(CBC_ResultPoint* a,
300                                         CBC_ResultPoint* b) {
301  return Round(
302      (FX_FLOAT)sqrt((a->GetX() - b->GetX()) * (a->GetX() - b->GetX()) +
303                     (a->GetY() - b->GetY()) * (a->GetY() - b->GetY())));
304}
305void CBC_DataMatrixDetector::Increment(
306    CFX_MapPtrTemplate<CBC_ResultPoint*, int32_t>& table,
307    CBC_ResultPoint* key) {
308  int32_t value;
309  if (table.Lookup(key, value)) {
310    table.SetAt(key, INTEGERS[value + 1]);
311  } else {
312    table.SetAt(key, INTEGERS[1]);
313  }
314}
315CBC_CommonBitMatrix* CBC_DataMatrixDetector::SampleGrid(
316    CBC_CommonBitMatrix* image,
317    CBC_ResultPoint* topLeft,
318    CBC_ResultPoint* bottomLeft,
319    CBC_ResultPoint* bottomRight,
320    CBC_ResultPoint* topRight,
321    int32_t dimensionX,
322    int32_t dimensionY,
323    int32_t& e) {
324  CBC_QRGridSampler& sampler = CBC_QRGridSampler::GetInstance();
325  CBC_CommonBitMatrix* cbm = sampler.SampleGrid(
326      image, dimensionX, dimensionY, 0.5f, 0.5f, dimensionX - 0.5f, 0.5f,
327      dimensionX - 0.5f, dimensionY - 0.5f, 0.5f, dimensionY - 0.5f,
328      topLeft->GetX(), topLeft->GetY(), topRight->GetX(), topRight->GetY(),
329      bottomRight->GetX(), bottomRight->GetY(), bottomLeft->GetX(),
330      bottomLeft->GetY(), e);
331  BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
332  return cbm;
333}
334CBC_ResultPointsAndTransitions* CBC_DataMatrixDetector::TransitionsBetween(
335    CBC_ResultPoint* from,
336    CBC_ResultPoint* to) {
337  int32_t fromX = (int32_t)from->GetX();
338  int32_t fromY = (int32_t)from->GetY();
339  int32_t toX = (int32_t)to->GetX();
340  int32_t toY = (int32_t)to->GetY();
341  FX_BOOL steep = FXSYS_abs(toY - fromY) > FXSYS_abs(toX - fromX);
342  if (steep) {
343    int32_t temp = fromX;
344    fromX = fromY;
345    fromY = temp;
346    temp = toX;
347    toX = toY;
348    toY = temp;
349  }
350  int32_t dx = FXSYS_abs(toX - fromX);
351  int32_t dy = FXSYS_abs(toY - fromY);
352  int32_t error = -dx >> 1;
353  int32_t ystep = fromY < toY ? 1 : -1;
354  int32_t xstep = fromX < toX ? 1 : -1;
355  int32_t transitions = 0;
356  FX_BOOL inBlack = m_image->Get(steep ? fromY : fromX, steep ? fromX : fromY);
357  for (int32_t x = fromX, y = fromY; x != toX; x += xstep) {
358    FX_BOOL isBlack = m_image->Get(steep ? y : x, steep ? x : y);
359    if (isBlack != inBlack) {
360      transitions++;
361      inBlack = isBlack;
362    }
363    error += dy;
364    if (error > 0) {
365      if (y == toY) {
366        break;
367      }
368      y += ystep;
369      error -= dx;
370    }
371  }
372  return new CBC_ResultPointsAndTransitions(from, to, transitions);
373}
374void CBC_DataMatrixDetector::OrderBestPatterns(CFX_PtrArray* patterns) {
375  FX_FLOAT abDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[0],
376                                           (CBC_ResultPoint*)(*patterns)[1]);
377  FX_FLOAT bcDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[1],
378                                           (CBC_ResultPoint*)(*patterns)[2]);
379  FX_FLOAT acDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[0],
380                                           (CBC_ResultPoint*)(*patterns)[2]);
381  CBC_ResultPoint *topLeft, *topRight, *bottomLeft;
382  if (bcDistance >= abDistance && bcDistance >= acDistance) {
383    topLeft = (CBC_ResultPoint*)(*patterns)[0];
384    topRight = (CBC_ResultPoint*)(*patterns)[1];
385    bottomLeft = (CBC_ResultPoint*)(*patterns)[2];
386  } else if (acDistance >= bcDistance && acDistance >= abDistance) {
387    topLeft = (CBC_ResultPoint*)(*patterns)[1];
388    topRight = (CBC_ResultPoint*)(*patterns)[0];
389    bottomLeft = (CBC_ResultPoint*)(*patterns)[2];
390  } else {
391    topLeft = (CBC_ResultPoint*)(*patterns)[2];
392    topRight = (CBC_ResultPoint*)(*patterns)[0];
393    bottomLeft = (CBC_ResultPoint*)(*patterns)[1];
394  }
395  if ((bottomLeft->GetY() - topLeft->GetY()) *
396          (topRight->GetX() - topLeft->GetX()) <
397      (bottomLeft->GetX() - topLeft->GetX()) *
398          (topRight->GetY() - topLeft->GetY())) {
399    CBC_ResultPoint* temp = topRight;
400    topRight = bottomLeft;
401    bottomLeft = temp;
402  }
403  (*patterns)[0] = bottomLeft;
404  (*patterns)[1] = topLeft;
405  (*patterns)[2] = topRight;
406}
407