Merge to XFA: Use stdint.h types throughout PDFium.
[pdfium.git] / xfa / src / fxbarcode / datamatrix / BC_DataMatrixDetector.cpp
1 // Copyright 2014 PDFium Authors. All rights reserved.\r
2 // Use of this source code is governed by a BSD-style license that can be\r
3 // found in the LICENSE file.\r
4 \r
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com\r
6 // Original code is licensed as follows:\r
7 /*\r
8  * Copyright 2008 ZXing authors\r
9  *\r
10  * Licensed under the Apache License, Version 2.0 (the "License");\r
11  * you may not use this file except in compliance with the License.\r
12  * You may obtain a copy of the License at\r
13  *\r
14  *      http://www.apache.org/licenses/LICENSE-2.0\r
15  *\r
16  * Unless required by applicable law or agreed to in writing, software\r
17  * distributed under the License is distributed on an "AS IS" BASIS,\r
18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
19  * See the License for the specific language governing permissions and\r
20  * limitations under the License.\r
21  */\r
22 \r
23 #include "../barcode.h"\r
24 #include "../BC_ResultPoint.h"\r
25 #include "../common/BC_WhiteRectangleDetector.h"\r
26 #include "../common/BC_CommonBitMatrix.h"\r
27 #include "../qrcode/BC_QRFinderPatternFinder.h"\r
28 #include "../qrcode/BC_QRDetectorResult.h"\r
29 #include "../qrcode/BC_QRGridSampler.h"\r
30 #include "BC_DataMatrixDetector.h"\r
31 const int32_t CBC_DataMatrixDetector::INTEGERS[5] = {0, 1, 2, 3, 4};\r
32 CBC_DataMatrixDetector::CBC_DataMatrixDetector(CBC_CommonBitMatrix *image):\r
33     m_image(image), m_rectangleDetector(NULL)\r
34 {\r
35 }\r
36 void CBC_DataMatrixDetector::Init(int32_t &e)\r
37 {\r
38     m_rectangleDetector = FX_NEW CBC_WhiteRectangleDetector(m_image);\r
39     m_rectangleDetector->Init(e);\r
40     BC_EXCEPTION_CHECK_ReturnVoid(e);\r
41 }\r
42 CBC_DataMatrixDetector::~CBC_DataMatrixDetector()\r
43 {\r
44     if(m_rectangleDetector != NULL) {\r
45         delete m_rectangleDetector;\r
46     }\r
47     m_rectangleDetector = NULL;\r
48 }\r
49 inline FX_BOOL ResultPointsAndTransitionsComparator(FX_LPVOID a, FX_LPVOID b)\r
50 {\r
51     return ((CBC_ResultPointsAndTransitions *)b)->GetTransitions() > ((CBC_ResultPointsAndTransitions *)a)->GetTransitions();\r
52 }\r
53 CBC_QRDetectorResult *CBC_DataMatrixDetector::Detect(int32_t &e)\r
54 {\r
55     CFX_PtrArray* cornerPoints = m_rectangleDetector->Detect(e);\r
56     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
57     CBC_ResultPoint *pointA = (CBC_ResultPoint*)(*cornerPoints)[0];\r
58     CBC_ResultPoint *pointB = (CBC_ResultPoint*)(*cornerPoints)[1];\r
59     CBC_ResultPoint *pointC = (CBC_ResultPoint*)(*cornerPoints)[2];\r
60     CBC_ResultPoint *pointD = (CBC_ResultPoint*)(*cornerPoints)[3];\r
61     delete cornerPoints;\r
62     cornerPoints = NULL;\r
63     CFX_PtrArray transitions;\r
64     transitions.Add(TransitionsBetween(pointA, pointB));\r
65     transitions.Add(TransitionsBetween(pointA, pointC));\r
66     transitions.Add(TransitionsBetween(pointB, pointD));\r
67     transitions.Add(TransitionsBetween(pointC, pointD));\r
68     BC_FX_PtrArray_Sort(transitions, &ResultPointsAndTransitionsComparator);\r
69     delete ( (CBC_ResultPointsAndTransitions *)transitions[2] );\r
70     delete ( (CBC_ResultPointsAndTransitions *)transitions[3] );\r
71     CBC_ResultPointsAndTransitions *lSideOne = (CBC_ResultPointsAndTransitions*)transitions[0];\r
72     CBC_ResultPointsAndTransitions *lSideTwo = (CBC_ResultPointsAndTransitions*)transitions[1];\r
73     CFX_MapPtrTemplate<CBC_ResultPoint*, int32_t> pointCount;\r
74     Increment(pointCount, lSideOne->GetFrom());\r
75     Increment(pointCount, lSideOne->GetTo());\r
76     Increment(pointCount, lSideTwo->GetFrom());\r
77     Increment(pointCount, lSideTwo->GetTo());\r
78     delete ( (CBC_ResultPointsAndTransitions *)transitions[1] );\r
79     delete ( (CBC_ResultPointsAndTransitions *)transitions[0] );\r
80     transitions.RemoveAll();\r
81     CBC_ResultPoint *maybeTopLeft = NULL;\r
82     CBC_ResultPoint *bottomLeft = NULL;\r
83     CBC_ResultPoint *maybeBottomRight = NULL;\r
84     FX_POSITION itBegin = pointCount.GetStartPosition();\r
85     while(itBegin != NULL) {\r
86         CBC_ResultPoint *key = 0;\r
87         int32_t value = 0;\r
88         pointCount.GetNextAssoc(itBegin, key, value);\r
89         if(value == 2) {\r
90             bottomLeft = key;\r
91         } else {\r
92             if (maybeBottomRight == NULL) {\r
93                 maybeBottomRight = key;\r
94             } else {\r
95                 maybeTopLeft = key;\r
96             }\r
97         }\r
98     }\r
99     if (maybeTopLeft == NULL || bottomLeft == NULL || maybeBottomRight == NULL) {\r
100         delete pointA;\r
101         delete pointB;\r
102         delete pointC;\r
103         delete pointD;\r
104         e = BCExceptionNotFound;\r
105         return NULL;\r
106     }\r
107     CFX_PtrArray corners;\r
108     corners.SetSize(3);\r
109     corners[0] = maybeTopLeft;\r
110     corners[1] = bottomLeft;\r
111     corners[2] = maybeBottomRight;\r
112     OrderBestPatterns(&corners);\r
113     CBC_ResultPoint *bottomRight = (CBC_ResultPoint*)corners[0];\r
114     bottomLeft = (CBC_ResultPoint*)corners[1];\r
115     CBC_ResultPoint *topLeft = (CBC_ResultPoint*)corners[2];\r
116     CBC_ResultPoint *topRight = NULL;\r
117     int32_t value;\r
118     if (!pointCount.Lookup(pointA, value)) {\r
119         topRight = pointA;\r
120     } else if (!pointCount.Lookup(pointB, value)) {\r
121         topRight = pointB;\r
122     } else if (!pointCount.Lookup(pointC, value)) {\r
123         topRight = pointC;\r
124     } else {\r
125         topRight = pointD;\r
126     }\r
127     int32_t dimensionTop = CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(topLeft, topRight))->GetTransitions();\r
128     int32_t dimensionRight = CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(bottomRight, topRight))->GetTransitions();\r
129     if ((dimensionTop & 0x01) == 1) {\r
130         dimensionTop++;\r
131     }\r
132     dimensionTop += 2;\r
133     if ((dimensionRight & 0x01) == 1) {\r
134         dimensionRight++;\r
135     }\r
136     dimensionRight += 2;\r
137     CBC_AutoPtr<CBC_CommonBitMatrix> bits(NULL);\r
138     CBC_AutoPtr<CBC_ResultPoint> correctedTopRight(NULL);\r
139     if (4 * dimensionTop >= 7 * dimensionRight || 4 * dimensionRight >= 7 * dimensionTop) {\r
140         correctedTopRight =\r
141             CBC_AutoPtr<CBC_ResultPoint>(CorrectTopRightRectangular(bottomLeft, bottomRight, topLeft, topRight,\r
142                                          dimensionTop, dimensionRight));\r
143         if (correctedTopRight.get() == NULL) {\r
144             correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(topRight);\r
145         } else {\r
146             delete topRight;\r
147             topRight = NULL;\r
148         }\r
149         dimensionTop = CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(topLeft, correctedTopRight.get()))->GetTransitions();\r
150         dimensionRight = CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(bottomRight, correctedTopRight.get()))->GetTransitions();\r
151         if ((dimensionTop & 0x01) == 1) {\r
152             dimensionTop++;\r
153         }\r
154         if ((dimensionRight & 0x01) == 1) {\r
155             dimensionRight++;\r
156         }\r
157         bits = CBC_AutoPtr<CBC_CommonBitMatrix>(SampleGrid(m_image, topLeft, bottomLeft, bottomRight,\r
158                                                 correctedTopRight.get(), dimensionTop, dimensionRight, e));\r
159         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
160     } else {\r
161         int32_t dimension = FX_MIN(dimensionRight, dimensionTop);\r
162         correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(CorrectTopRight(bottomLeft, bottomRight,\r
163                             topLeft, topRight, dimension));\r
164         if (correctedTopRight.get() == NULL) {\r
165             correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(topRight);\r
166         } else {\r
167             delete topRight;\r
168             topRight = NULL;\r
169         }\r
170         int32_t dimensionCorrected = FX_MAX(CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(topLeft, correctedTopRight.get()))->GetTransitions(),\r
171                                              CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(bottomRight, correctedTopRight.get()))->GetTransitions());\r
172         dimensionCorrected++;\r
173         if ((dimensionCorrected & 0x01) == 1) {\r
174             dimensionCorrected++;\r
175         }\r
176         bits = CBC_AutoPtr<CBC_CommonBitMatrix>(SampleGrid(m_image,\r
177                                                 topLeft,\r
178                                                 bottomLeft,\r
179                                                 bottomRight,\r
180                                                 correctedTopRight.get(),\r
181                                                 dimensionCorrected,\r
182                                                 dimensionCorrected, e));\r
183         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
184     }\r
185     CFX_PtrArray *result = FX_NEW CFX_PtrArray;\r
186     result->SetSize(4);\r
187     result->Add(topLeft);\r
188     result->Add(bottomLeft);\r
189     result->Add(bottomRight);\r
190     result->Add(correctedTopRight.release());\r
191     return FX_NEW CBC_QRDetectorResult(bits.release(), result);\r
192 }\r
193 CBC_ResultPoint *CBC_DataMatrixDetector::CorrectTopRightRectangular(CBC_ResultPoint *bottomLeft, CBC_ResultPoint *bottomRight, CBC_ResultPoint *topLeft, CBC_ResultPoint *topRight, int32_t dimensionTop, int32_t dimensionRight)\r
194 {\r
195     FX_FLOAT corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT)dimensionTop;\r
196     int32_t norm = Distance(topLeft, topRight);\r
197     FX_FLOAT cos = (topRight->GetX() - topLeft->GetX()) / norm;\r
198     FX_FLOAT sin = (topRight->GetY() - topLeft->GetY()) / norm;\r
199     CBC_AutoPtr<CBC_ResultPoint> c1(FX_NEW CBC_ResultPoint(topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));\r
200     corr = Distance(bottomLeft, topLeft) / (FX_FLOAT)dimensionRight;\r
201     norm = Distance(bottomRight, topRight);\r
202     cos = (topRight->GetX() - bottomRight->GetX()) / norm;\r
203     sin = (topRight->GetY() - bottomRight->GetY()) / norm;\r
204     CBC_AutoPtr<CBC_ResultPoint> c2(FX_NEW CBC_ResultPoint(topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));\r
205     if (!IsValid(c1.get())) {\r
206         if (IsValid(c2.get())) {\r
207             return c2.release();\r
208         }\r
209         return NULL;\r
210     } else if (!IsValid(c2.get())) {\r
211         return c1.release();\r
212     }\r
213     int32_t l1 = FXSYS_abs(dimensionTop - CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(topLeft, c1.get()))->GetTransitions()) +\r
214                   FXSYS_abs(dimensionRight - CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(bottomRight, c1.get()))->GetTransitions());\r
215     int32_t l2 = FXSYS_abs(dimensionTop - CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(topLeft, c2.get()))->GetTransitions()) +\r
216                   FXSYS_abs(dimensionRight - CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(bottomRight, c2.get()))->GetTransitions());\r
217     if (l1 <= l2) {\r
218         return c1.release();\r
219     }\r
220     return c2.release();\r
221 }\r
222 CBC_ResultPoint *CBC_DataMatrixDetector::CorrectTopRight(CBC_ResultPoint *bottomLeft, CBC_ResultPoint *bottomRight, CBC_ResultPoint *topLeft, CBC_ResultPoint *topRight, int32_t dimension)\r
223 {\r
224     FX_FLOAT corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT) dimension;\r
225     int32_t norm = Distance(topLeft, topRight);\r
226     FX_FLOAT cos = (topRight->GetX() - topLeft->GetX()) / norm;\r
227     FX_FLOAT sin = (topRight->GetY() - topLeft->GetY()) / norm;\r
228     CBC_AutoPtr<CBC_ResultPoint> c1(FX_NEW CBC_ResultPoint(topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));\r
229     corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT) dimension;\r
230     norm = Distance(bottomRight, topRight);\r
231     cos = (topRight->GetX() - bottomRight->GetX()) / norm;\r
232     sin = (topRight->GetY() - bottomRight->GetY()) / norm;\r
233     CBC_AutoPtr<CBC_ResultPoint> c2(FX_NEW CBC_ResultPoint(topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));\r
234     if (!IsValid(c1.get())) {\r
235         if (IsValid(c2.get())) {\r
236             return c2.release();\r
237         }\r
238         return NULL;\r
239     } else if (!IsValid(c2.get())) {\r
240         return c1.release();\r
241     }\r
242     int32_t l1 = FXSYS_abs(CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(topLeft, c1.get()))->GetTransitions() -\r
243                             CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(bottomRight, c1.get()))->GetTransitions());\r
244     int32_t l2 = FXSYS_abs(CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(topLeft, c2.get()))->GetTransitions() -\r
245                             CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(bottomRight, c2.get()))->GetTransitions());\r
246     return l1 <= l2 ? c1.release() : c2.release();\r
247 }\r
248 FX_BOOL CBC_DataMatrixDetector::IsValid(CBC_ResultPoint *p)\r
249 {\r
250     return p->GetX() >= 0 && p->GetX() < m_image->GetWidth() && p->GetY() > 0 && p->GetY() < m_image->GetHeight();\r
251 }\r
252 int32_t CBC_DataMatrixDetector::Round(FX_FLOAT d)\r
253 {\r
254     return (int32_t) (d + 0.5f);\r
255 }\r
256 int32_t CBC_DataMatrixDetector::Distance(CBC_ResultPoint *a, CBC_ResultPoint *b)\r
257 {\r
258     return Round((FX_FLOAT) sqrt((a->GetX() - b->GetX())\r
259                                  * (a->GetX() - b->GetX()) + (a->GetY() - b->GetY())\r
260                                  * (a->GetY() - b->GetY())));\r
261 }\r
262 void CBC_DataMatrixDetector::Increment(CFX_MapPtrTemplate<CBC_ResultPoint*, int32_t> &table, CBC_ResultPoint *key)\r
263 {\r
264     int32_t value;\r
265     if(table.Lookup(key, value)) {\r
266         table.SetAt(key, INTEGERS[value + 1]);\r
267     } else {\r
268         table.SetAt(key, INTEGERS[1]);\r
269     }\r
270 }\r
271 CBC_CommonBitMatrix *CBC_DataMatrixDetector::SampleGrid(CBC_CommonBitMatrix *image,\r
272         CBC_ResultPoint *topLeft,\r
273         CBC_ResultPoint *bottomLeft,\r
274         CBC_ResultPoint *bottomRight,\r
275         CBC_ResultPoint *topRight,\r
276         int32_t dimensionX, int32_t dimensionY, int32_t &e)\r
277 {\r
278     CBC_QRGridSampler &sampler = CBC_QRGridSampler::GetInstance();\r
279     CBC_CommonBitMatrix* cbm = sampler.SampleGrid(image,\r
280                                dimensionX,\r
281                                dimensionY,\r
282                                0.5f,\r
283                                0.5f,\r
284                                dimensionX - 0.5f,\r
285                                0.5f,\r
286                                dimensionX - 0.5f,\r
287                                dimensionY - 0.5f,\r
288                                0.5f,\r
289                                dimensionY - 0.5f,\r
290                                topLeft->GetX(),\r
291                                topLeft->GetY(),\r
292                                topRight->GetX(),\r
293                                topRight->GetY(),\r
294                                bottomRight->GetX(),\r
295                                bottomRight->GetY(),\r
296                                bottomLeft->GetX(),\r
297                                bottomLeft->GetY(), e);\r
298     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
299     return cbm;\r
300 }\r
301 CBC_ResultPointsAndTransitions *CBC_DataMatrixDetector::TransitionsBetween(CBC_ResultPoint *from, CBC_ResultPoint *to)\r
302 {\r
303     int32_t fromX = (int32_t) from->GetX();\r
304     int32_t fromY = (int32_t) from->GetY();\r
305     int32_t toX = (int32_t) to->GetX();\r
306     int32_t toY = (int32_t) to->GetY();\r
307     FX_BOOL steep = FXSYS_abs(toY - fromY) > FXSYS_abs(toX - fromX);\r
308     if (steep) {\r
309         int32_t temp = fromX;\r
310         fromX = fromY;\r
311         fromY = temp;\r
312         temp = toX;\r
313         toX = toY;\r
314         toY = temp;\r
315     }\r
316     int32_t dx = FXSYS_abs(toX - fromX);\r
317     int32_t dy = FXSYS_abs(toY - fromY);\r
318     int32_t error = -dx >> 1;\r
319     int32_t ystep = fromY < toY ? 1 : -1;\r
320     int32_t xstep = fromX < toX ? 1 : -1;\r
321     int32_t transitions = 0;\r
322     FX_BOOL inBlack = m_image->Get(steep ? fromY : fromX, steep ? fromX : fromY);\r
323     for (int32_t x = fromX, y = fromY; x != toX; x += xstep) {\r
324         FX_BOOL isBlack = m_image->Get(steep ? y : x, steep ? x : y);\r
325         if (isBlack != inBlack) {\r
326             transitions++;\r
327             inBlack = isBlack;\r
328         }\r
329         error += dy;\r
330         if (error > 0) {\r
331             if (y == toY) {\r
332                 break;\r
333             }\r
334             y += ystep;\r
335             error -= dx;\r
336         }\r
337     }\r
338     return FX_NEW CBC_ResultPointsAndTransitions(from, to, transitions);\r
339 }\r
340 void CBC_DataMatrixDetector::OrderBestPatterns(CFX_PtrArray *patterns)\r
341 {\r
342     FX_FLOAT abDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[0], (CBC_ResultPoint*)(*patterns)[1]);\r
343     FX_FLOAT bcDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[1], (CBC_ResultPoint*)(*patterns)[2]);\r
344     FX_FLOAT acDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[0], (CBC_ResultPoint*)(*patterns)[2]);\r
345     CBC_ResultPoint *topLeft, *topRight, *bottomLeft;\r
346     if (bcDistance >= abDistance && bcDistance >= acDistance) {\r
347         topLeft = (CBC_ResultPoint*)(*patterns)[0];\r
348         topRight = (CBC_ResultPoint*)(*patterns)[1];\r
349         bottomLeft = (CBC_ResultPoint*)(*patterns)[2];\r
350     } else if (acDistance >= bcDistance && acDistance >= abDistance) {\r
351         topLeft = (CBC_ResultPoint*)(*patterns)[1];\r
352         topRight = (CBC_ResultPoint*)(*patterns)[0];\r
353         bottomLeft = (CBC_ResultPoint*)(*patterns)[2];\r
354     } else {\r
355         topLeft = (CBC_ResultPoint*)(*patterns)[2];\r
356         topRight = (CBC_ResultPoint*)(*patterns)[0];\r
357         bottomLeft = (CBC_ResultPoint*)(*patterns)[1];\r
358     }\r
359     if ((bottomLeft->GetY() - topLeft->GetY()) * (topRight->GetX() - topLeft->GetX()) < (bottomLeft->GetX()\r
360             - topLeft->GetX()) * (topRight->GetY() - topLeft->GetY())) {\r
361         CBC_ResultPoint *temp = topRight;\r
362         topRight = bottomLeft;\r
363         bottomLeft = temp;\r
364     }\r
365     (*patterns)[0] = bottomLeft;\r
366     (*patterns)[1] = topLeft;\r
367     (*patterns)[2] = topRight;\r
368 }\r