1 /**
2  * libdmtx - Data Matrix Encoding/Decoding Library
3  * Copyright 2008, 2009 Mike Laughton. All rights reserved.
4  * Copyright 2012-2016 Vadim A. Misbakh-Soloviov. All rights reserved.
5  * Copyright 2016 Tim Zaman. All rights reserved.
6  *
7  * See LICENSE file in the main project directory for full
8  * terms of use and distribution.
9  *
10  * Contact:
11  * Vadim A. Misbakh-Soloviov <dmtx@mva.name>
12  * Mike Laughton <mike@dragonflylogic.com>
13  *
14  * \file dmtxregion.c
15  * \brief Detect barcode regions
16  */
17 
18 #define DMTX_HOUGH_RES 180
19 
20 /**
21  * \brief  Create copy of existing region struct
22  * \param  None
23  * \return Initialized DmtxRegion struct
24  */
25 extern DmtxRegion *
dmtxRegionCreate(DmtxRegion * reg)26 dmtxRegionCreate(DmtxRegion *reg)
27 {
28    DmtxRegion *regCopy;
29 
30    regCopy = (DmtxRegion *)malloc(sizeof(DmtxRegion));
31    if(regCopy == NULL)
32       return NULL;
33 
34    memcpy(regCopy, reg, sizeof(DmtxRegion));
35 
36    return regCopy;
37 }
38 
39 /**
40  * \brief  Destroy region struct
41  * \param  reg
42  * \return void
43  */
44 extern DmtxPassFail
dmtxRegionDestroy(DmtxRegion ** reg)45 dmtxRegionDestroy(DmtxRegion **reg)
46 {
47    if(reg == NULL || *reg == NULL)
48       return DmtxFail;
49 
50    free(*reg);
51 
52    *reg = NULL;
53 
54    return DmtxPass;
55 }
56 
57 /**
58  * \brief  Find next barcode region
59  * \param  dec Pointer to DmtxDecode information struct
60  * \param  timeout Pointer to timeout time (NULL if none)
61  * \return Detected region (if found)
62  */
63 extern DmtxRegion *
dmtxRegionFindNext(DmtxDecode * dec,DmtxTime * timeout)64 dmtxRegionFindNext(DmtxDecode *dec, DmtxTime *timeout)
65 {
66    int locStatus;
67    DmtxPixelLoc loc;
68    DmtxRegion   *reg;
69 
70    /* Continue until we find a region or run out of chances */
71    for(;;) {
72       locStatus = PopGridLocation(&(dec->grid), &loc);
73       if(locStatus == DmtxRangeEnd)
74          break;
75 
76       /* Scan location for presence of valid barcode region */
77       reg = dmtxRegionScanPixel(dec, loc.X, loc.Y);
78       if(reg != NULL)
79          return reg;
80 
81       /* Ran out of time? */
82       if(timeout != NULL && dmtxTimeExceeded(*timeout))
83          break;
84    }
85 
86    return NULL;
87 }
88 
89 /**
90  * \brief  Scan individual pixel for presence of barcode edge
91  * \param  dec Pointer to DmtxDecode information struct
92  * \param  loc Pixel location
93  * \return Detected region (if any)
94  */
95 extern DmtxRegion *
dmtxRegionScanPixel(DmtxDecode * dec,int x,int y)96 dmtxRegionScanPixel(DmtxDecode *dec, int x, int y)
97 {
98    unsigned char *cache;
99    DmtxRegion reg;
100    DmtxPointFlow flowBegin;
101    DmtxPixelLoc loc;
102 
103    loc.X = x;
104    loc.Y = y;
105 
106    cache = dmtxDecodeGetCache(dec, loc.X, loc.Y);
107    if(cache == NULL)
108       return NULL;
109 
110    if((int)(*cache & 0x80) != 0x00)
111       return NULL;
112 
113    /* Test for presence of any reasonable edge at this location */
114    flowBegin = MatrixRegionSeekEdge(dec, loc);
115    if(flowBegin.mag < (int)(dec->edgeThresh * 7.65 + 0.5))
116       return NULL;
117 
118    memset(&reg, 0x00, sizeof(DmtxRegion));
119 
120    /* Determine barcode orientation */
121    if(MatrixRegionOrientation(dec, &reg, flowBegin) == DmtxFail)
122       return NULL;
123    if(dmtxRegionUpdateXfrms(dec, &reg) == DmtxFail)
124       return NULL;
125 
126    /* Define top edge */
127    if(MatrixRegionAlignCalibEdge(dec, &reg, DmtxEdgeTop) == DmtxFail)
128       return NULL;
129    if(dmtxRegionUpdateXfrms(dec, &reg) == DmtxFail)
130       return NULL;
131 
132    /* Define right edge */
133    if(MatrixRegionAlignCalibEdge(dec, &reg, DmtxEdgeRight) == DmtxFail)
134       return NULL;
135    if(dmtxRegionUpdateXfrms(dec, &reg) == DmtxFail)
136       return NULL;
137 
138    CALLBACK_MATRIX(&reg);
139 
140    /* Calculate the best fitting symbol size */
141    if(MatrixRegionFindSize(dec, &reg) == DmtxFail)
142       return NULL;
143 
144    /* Found a valid matrix region */
145    return dmtxRegionCreate(&reg);
146 }
147 
148 /**
149  *
150  *
151  */
152 static DmtxPointFlow
MatrixRegionSeekEdge(DmtxDecode * dec,DmtxPixelLoc loc)153 MatrixRegionSeekEdge(DmtxDecode *dec, DmtxPixelLoc loc)
154 {
155    int i;
156    int strongIdx;
157    int channelCount;
158    DmtxPointFlow flow, flowPlane[3];
159    DmtxPointFlow flowPos, flowPosBack;
160    DmtxPointFlow flowNeg, flowNegBack;
161 
162    channelCount = dec->image->channelCount;
163 
164    /* Find whether red, green, or blue shows the strongest edge */
165    strongIdx = 0;
166    for(i = 0; i < channelCount; i++) {
167       flowPlane[i] = GetPointFlow(dec, i, loc, dmtxNeighborNone);
168       if(i > 0 && flowPlane[i].mag > flowPlane[strongIdx].mag)
169          strongIdx = i;
170    }
171 
172    if(flowPlane[strongIdx].mag < 10)
173       return dmtxBlankEdge;
174 
175    flow = flowPlane[strongIdx];
176 
177    flowPos = FindStrongestNeighbor(dec, flow, +1);
178    flowNeg = FindStrongestNeighbor(dec, flow, -1);
179    if(flowPos.mag != 0 && flowNeg.mag != 0) {
180       flowPosBack = FindStrongestNeighbor(dec, flowPos, -1);
181       flowNegBack = FindStrongestNeighbor(dec, flowNeg, +1);
182       if(flowPos.arrive == (flowPosBack.arrive+4)%8 &&
183             flowNeg.arrive == (flowNegBack.arrive+4)%8) {
184          flow.arrive = dmtxNeighborNone;
185          CALLBACK_POINT_PLOT(flow.loc, 1, 1, 1);
186          return flow;
187       }
188    }
189 
190    return dmtxBlankEdge;
191 }
192 
193 /**
194  *
195  *
196  */
197 static DmtxPassFail
MatrixRegionOrientation(DmtxDecode * dec,DmtxRegion * reg,DmtxPointFlow begin)198 MatrixRegionOrientation(DmtxDecode *dec, DmtxRegion *reg, DmtxPointFlow begin)
199 {
200    int cross;
201    int minArea;
202    int scale;
203    int symbolShape;
204    int maxDiagonal;
205    DmtxPassFail err;
206    DmtxBestLine line1x, line2x;
207    DmtxBestLine line2n, line2p;
208    DmtxFollow fTmp;
209 
210    if(dec->sizeIdxExpected == DmtxSymbolSquareAuto ||
211          (dec->sizeIdxExpected >= DmtxSymbol10x10 &&
212          dec->sizeIdxExpected <= DmtxSymbol144x144))
213       symbolShape = DmtxSymbolSquareAuto;
214    else if(dec->sizeIdxExpected == DmtxSymbolRectAuto ||
215          (dec->sizeIdxExpected >= DmtxSymbol8x18 &&
216          dec->sizeIdxExpected <= DmtxSymbol16x48))
217       symbolShape = DmtxSymbolRectAuto;
218    else
219       symbolShape = DmtxSymbolShapeAuto;
220 
221    if(dec->edgeMax != DmtxUndefined) {
222       if(symbolShape == DmtxSymbolRectAuto)
223          maxDiagonal = (int)(1.23 * dec->edgeMax + 0.5); /* sqrt(5/4) + 10% */
224       else
225          maxDiagonal = (int)(1.56 * dec->edgeMax + 0.5); /* sqrt(2) + 10% */
226    }
227    else {
228       maxDiagonal = DmtxUndefined;
229    }
230 
231    /* Follow to end in both directions */
232    err = TrailBlazeContinuous(dec, reg, begin, maxDiagonal);
233    if(err == DmtxFail || reg->stepsTotal < 40) {
234       TrailClear(dec, reg, 0x40);
235       return DmtxFail;
236    }
237 
238    /* Filter out region candidates that are smaller than expected */
239    if(dec->edgeMin != DmtxUndefined) {
240       scale = dmtxDecodeGetProp(dec, DmtxPropScale);
241 
242       if(symbolShape == DmtxSymbolSquareAuto)
243          minArea = (dec->edgeMin * dec->edgeMin)/(scale * scale);
244       else
245          minArea = (2 * dec->edgeMin * dec->edgeMin)/(scale * scale);
246 
247       if((reg->boundMax.X - reg->boundMin.X) * (reg->boundMax.Y - reg->boundMin.Y) < minArea) {
248          TrailClear(dec, reg, 0x40);
249          return DmtxFail;
250       }
251    }
252 
253    line1x = FindBestSolidLine(dec, reg, 0, 0, +1, DmtxUndefined);
254    if(line1x.mag < 5) {
255       TrailClear(dec, reg, 0x40);
256       return DmtxFail;
257    }
258 
259    err = FindTravelLimits(dec, reg, &line1x);
260    if(line1x.distSq < 100 || line1x.devn * 10 >= sqrt((double)line1x.distSq)) {
261       TrailClear(dec, reg, 0x40);
262       return DmtxFail;
263    }
264    assert(line1x.stepPos >= line1x.stepNeg);
265 
266    fTmp = FollowSeek(dec, reg, line1x.stepPos + 5);
267    line2p = FindBestSolidLine(dec, reg, fTmp.step, line1x.stepNeg, +1, line1x.angle);
268 
269    fTmp = FollowSeek(dec, reg, line1x.stepNeg - 5);
270    line2n = FindBestSolidLine(dec, reg, fTmp.step, line1x.stepPos, -1, line1x.angle);
271    if(max(line2p.mag, line2n.mag) < 5)
272       return DmtxFail;
273 
274    if(line2p.mag > line2n.mag) {
275       line2x = line2p;
276       err = FindTravelLimits(dec, reg, &line2x);
277       if(line2x.distSq < 100 || line2x.devn * 10 >= sqrt((double)line2x.distSq))
278          return DmtxFail;
279 
280       cross = ((line1x.locPos.X - line1x.locNeg.X) * (line2x.locPos.Y - line2x.locNeg.Y)) -
281             ((line1x.locPos.Y - line1x.locNeg.Y) * (line2x.locPos.X - line2x.locNeg.X));
282       if(cross > 0) {
283          /* Condition 2 */
284          reg->polarity = +1;
285          reg->locR = line2x.locPos;
286          reg->stepR = line2x.stepPos;
287          reg->locT = line1x.locNeg;
288          reg->stepT = line1x.stepNeg;
289          reg->leftLoc = line1x.locBeg;
290          reg->leftAngle = line1x.angle;
291          reg->bottomLoc = line2x.locBeg;
292          reg->bottomAngle = line2x.angle;
293          reg->leftLine = line1x;
294          reg->bottomLine = line2x;
295       }
296       else {
297          /* Condition 3 */
298          reg->polarity = -1;
299          reg->locR = line1x.locNeg;
300          reg->stepR = line1x.stepNeg;
301          reg->locT = line2x.locPos;
302          reg->stepT = line2x.stepPos;
303          reg->leftLoc = line2x.locBeg;
304          reg->leftAngle = line2x.angle;
305          reg->bottomLoc = line1x.locBeg;
306          reg->bottomAngle = line1x.angle;
307          reg->leftLine = line2x;
308          reg->bottomLine = line1x;
309       }
310    }
311    else {
312       line2x = line2n;
313       err = FindTravelLimits(dec, reg, &line2x);
314       if(line2x.distSq < 100 || line2x.devn / sqrt((double)line2x.distSq) >= 0.1)
315          return DmtxFail;
316 
317       cross = ((line1x.locNeg.X - line1x.locPos.X) * (line2x.locNeg.Y - line2x.locPos.Y)) -
318             ((line1x.locNeg.Y - line1x.locPos.Y) * (line2x.locNeg.X - line2x.locPos.X));
319       if(cross > 0) {
320          /* Condition 1 */
321          reg->polarity = -1;
322          reg->locR = line2x.locNeg;
323          reg->stepR = line2x.stepNeg;
324          reg->locT = line1x.locPos;
325          reg->stepT = line1x.stepPos;
326          reg->leftLoc = line1x.locBeg;
327          reg->leftAngle = line1x.angle;
328          reg->bottomLoc = line2x.locBeg;
329          reg->bottomAngle = line2x.angle;
330          reg->leftLine = line1x;
331          reg->bottomLine = line2x;
332       }
333       else {
334          /* Condition 4 */
335          reg->polarity = +1;
336          reg->locR = line1x.locPos;
337          reg->stepR = line1x.stepPos;
338          reg->locT = line2x.locNeg;
339          reg->stepT = line2x.stepNeg;
340          reg->leftLoc = line2x.locBeg;
341          reg->leftAngle = line2x.angle;
342          reg->bottomLoc = line1x.locBeg;
343          reg->bottomAngle = line1x.angle;
344          reg->leftLine = line2x;
345          reg->bottomLine = line1x;
346       }
347    }
348 /* CALLBACK_POINT_PLOT(reg->locR, 2, 1, 1);
349    CALLBACK_POINT_PLOT(reg->locT, 2, 1, 1); */
350 
351    reg->leftKnown = reg->bottomKnown = 1;
352 
353    return DmtxPass;
354 }
355 
356 /**
357  *
358  *
359  */
360 static long
DistanceSquared(DmtxPixelLoc a,DmtxPixelLoc b)361 DistanceSquared(DmtxPixelLoc a, DmtxPixelLoc b)
362 {
363    long xDelta, yDelta;
364 
365    xDelta = a.X - b.X;
366    yDelta = a.Y - b.Y;
367 
368    return (xDelta * xDelta) + (yDelta * yDelta);
369 }
370 
371 /**
372  *
373  *
374  */
375 extern DmtxPassFail
dmtxRegionUpdateCorners(DmtxDecode * dec,DmtxRegion * reg,DmtxVector2 p00,DmtxVector2 p10,DmtxVector2 p11,DmtxVector2 p01)376 dmtxRegionUpdateCorners(DmtxDecode *dec, DmtxRegion *reg, DmtxVector2 p00,
377       DmtxVector2 p10, DmtxVector2 p11, DmtxVector2 p01)
378 {
379    double xMax, yMax;
380    double tx, ty, phi, shx, scx, scy, skx, sky;
381    double dimOT, dimOR, dimTX, dimRX, ratio;
382    DmtxVector2 vOT, vOR, vTX, vRX, vTmp;
383    DmtxMatrix3 m, mtxy, mphi, mshx, mscx, mscy, mscxy, msky, mskx;
384 
385    xMax = (double)(dmtxDecodeGetProp(dec, DmtxPropWidth) - 1);
386    yMax = (double)(dmtxDecodeGetProp(dec, DmtxPropHeight) - 1);
387 
388    if(p00.X < 0.0 || p00.Y < 0.0 || p00.X > xMax || p00.Y > yMax ||
389          p01.X < 0.0 || p01.Y < 0.0 || p01.X > xMax || p01.Y > yMax ||
390          p10.X < 0.0 || p10.Y < 0.0 || p10.X > xMax || p10.Y > yMax)
391       return DmtxFail;
392 
393    dimOT = dmtxVector2Mag(dmtxVector2Sub(&vOT, &p01, &p00)); /* XXX could use MagSquared() */
394    dimOR = dmtxVector2Mag(dmtxVector2Sub(&vOR, &p10, &p00));
395    dimTX = dmtxVector2Mag(dmtxVector2Sub(&vTX, &p11, &p01));
396    dimRX = dmtxVector2Mag(dmtxVector2Sub(&vRX, &p11, &p10));
397 
398    /* Verify that sides are reasonably long */
399    if(dimOT <= 8.0 || dimOR <= 8.0 || dimTX <= 8.0 || dimRX <= 8.0)
400       return DmtxFail;
401 
402    /* Verify that the 4 corners define a reasonably fat quadrilateral */
403    ratio = dimOT / dimRX;
404    if(ratio <= 0.5 || ratio >= 2.0)
405       return DmtxFail;
406 
407    ratio = dimOR / dimTX;
408    if(ratio <= 0.5 || ratio >= 2.0)
409       return DmtxFail;
410 
411    /* Verify this is not a bowtie shape */
412    if(dmtxVector2Cross(&vOR, &vRX) <= 0.0 ||
413          dmtxVector2Cross(&vOT, &vTX) >= 0.0)
414       return DmtxFail;
415 
416    if(RightAngleTrueness(p00, p10, p11, M_PI_2) <= dec->squareDevn)
417       return DmtxFail;
418    if(RightAngleTrueness(p10, p11, p01, M_PI_2) <= dec->squareDevn)
419       return DmtxFail;
420 
421    /* Calculate values needed for transformations */
422    tx = -1 * p00.X;
423    ty = -1 * p00.Y;
424    dmtxMatrix3Translate(mtxy, tx, ty);
425 
426    phi = atan2(vOT.X, vOT.Y);
427    dmtxMatrix3Rotate(mphi, phi);
428    dmtxMatrix3Multiply(m, mtxy, mphi);
429 
430    dmtxMatrix3VMultiply(&vTmp, &p10, m);
431    shx = -vTmp.Y / vTmp.X;
432    dmtxMatrix3Shear(mshx, 0.0, shx);
433    dmtxMatrix3MultiplyBy(m, mshx);
434 
435    scx = 1.0/vTmp.X;
436    dmtxMatrix3Scale(mscx, scx, 1.0);
437    dmtxMatrix3MultiplyBy(m, mscx);
438 
439    dmtxMatrix3VMultiply(&vTmp, &p11, m);
440    scy = 1.0/vTmp.Y;
441    dmtxMatrix3Scale(mscy, 1.0, scy);
442    dmtxMatrix3MultiplyBy(m, mscy);
443 
444    dmtxMatrix3VMultiply(&vTmp, &p11, m);
445    skx = vTmp.X;
446    dmtxMatrix3LineSkewSide(mskx, 1.0, skx, 1.0);
447    dmtxMatrix3MultiplyBy(m, mskx);
448 
449    dmtxMatrix3VMultiply(&vTmp, &p01, m);
450    sky = vTmp.Y;
451    dmtxMatrix3LineSkewTop(msky, sky, 1.0, 1.0);
452    dmtxMatrix3Multiply(reg->raw2fit, m, msky);
453 
454    /* Create inverse matrix by reverse (avoid straight matrix inversion) */
455    dmtxMatrix3LineSkewTopInv(msky, sky, 1.0, 1.0);
456    dmtxMatrix3LineSkewSideInv(mskx, 1.0, skx, 1.0);
457    dmtxMatrix3Multiply(m, msky, mskx);
458 
459    dmtxMatrix3Scale(mscxy, 1.0/scx, 1.0/scy);
460    dmtxMatrix3MultiplyBy(m, mscxy);
461 
462    dmtxMatrix3Shear(mshx, 0.0, -shx);
463    dmtxMatrix3MultiplyBy(m, mshx);
464 
465    dmtxMatrix3Rotate(mphi, -phi);
466    dmtxMatrix3MultiplyBy(m, mphi);
467 
468    dmtxMatrix3Translate(mtxy, -tx, -ty);
469    dmtxMatrix3Multiply(reg->fit2raw, m, mtxy);
470 
471    return DmtxPass;
472 }
473 
474 /**
475  *
476  *
477  */
478 extern DmtxPassFail
dmtxRegionUpdateXfrms(DmtxDecode * dec,DmtxRegion * reg)479 dmtxRegionUpdateXfrms(DmtxDecode *dec, DmtxRegion *reg)
480 {
481    double radians;
482    DmtxRay2 rLeft, rBottom, rTop, rRight;
483    DmtxVector2 p00, p10, p11, p01;
484 
485    assert(reg->leftKnown != 0 && reg->bottomKnown != 0);
486 
487    /* Build ray representing left edge */
488    rLeft.p.X = (double)reg->leftLoc.X;
489    rLeft.p.Y = (double)reg->leftLoc.Y;
490    radians = reg->leftAngle * (M_PI/DMTX_HOUGH_RES);
491    rLeft.v.X = cos(radians);
492    rLeft.v.Y = sin(radians);
493    rLeft.tMin = 0.0;
494    rLeft.tMax = dmtxVector2Norm(&rLeft.v);
495 
496    /* Build ray representing bottom edge */
497    rBottom.p.X = (double)reg->bottomLoc.X;
498    rBottom.p.Y = (double)reg->bottomLoc.Y;
499    radians = reg->bottomAngle * (M_PI/DMTX_HOUGH_RES);
500    rBottom.v.X = cos(radians);
501    rBottom.v.Y = sin(radians);
502    rBottom.tMin = 0.0;
503    rBottom.tMax = dmtxVector2Norm(&rBottom.v);
504 
505    /* Build ray representing top edge */
506    if(reg->topKnown != 0) {
507       rTop.p.X = (double)reg->topLoc.X;
508       rTop.p.Y = (double)reg->topLoc.Y;
509       radians = reg->topAngle * (M_PI/DMTX_HOUGH_RES);
510       rTop.v.X = cos(radians);
511       rTop.v.Y = sin(radians);
512       rTop.tMin = 0.0;
513       rTop.tMax = dmtxVector2Norm(&rTop.v);
514    }
515    else {
516       rTop.p.X = (double)reg->locT.X;
517       rTop.p.Y = (double)reg->locT.Y;
518       radians = reg->bottomAngle * (M_PI/DMTX_HOUGH_RES);
519       rTop.v.X = cos(radians);
520       rTop.v.Y = sin(radians);
521       rTop.tMin = 0.0;
522       rTop.tMax = rBottom.tMax;
523    }
524 
525    /* Build ray representing right edge */
526    if(reg->rightKnown != 0) {
527       rRight.p.X = (double)reg->rightLoc.X;
528       rRight.p.Y = (double)reg->rightLoc.Y;
529       radians = reg->rightAngle * (M_PI/DMTX_HOUGH_RES);
530       rRight.v.X = cos(radians);
531       rRight.v.Y = sin(radians);
532       rRight.tMin = 0.0;
533       rRight.tMax = dmtxVector2Norm(&rRight.v);
534    }
535    else {
536       rRight.p.X = (double)reg->locR.X;
537       rRight.p.Y = (double)reg->locR.Y;
538       radians = reg->leftAngle * (M_PI/DMTX_HOUGH_RES);
539       rRight.v.X = cos(radians);
540       rRight.v.Y = sin(radians);
541       rRight.tMin = 0.0;
542       rRight.tMax = rLeft.tMax;
543    }
544 
545    /* Calculate 4 corners, real or imagined */
546    if(dmtxRay2Intersect(&p00, &rLeft, &rBottom) == DmtxFail)
547       return DmtxFail;
548 
549    if(dmtxRay2Intersect(&p10, &rBottom, &rRight) == DmtxFail)
550       return DmtxFail;
551 
552    if(dmtxRay2Intersect(&p11, &rRight, &rTop) == DmtxFail)
553       return DmtxFail;
554 
555    if(dmtxRay2Intersect(&p01, &rTop, &rLeft) == DmtxFail)
556       return DmtxFail;
557 
558    if(dmtxRegionUpdateCorners(dec, reg, p00, p10, p11, p01) != DmtxPass)
559       return DmtxFail;
560 
561    return DmtxPass;
562 }
563 
564 /**
565  *
566  *
567  */
568 static double
RightAngleTrueness(DmtxVector2 c0,DmtxVector2 c1,DmtxVector2 c2,double angle)569 RightAngleTrueness(DmtxVector2 c0, DmtxVector2 c1, DmtxVector2 c2, double angle)
570 {
571    DmtxVector2 vA, vB;
572    DmtxMatrix3 m;
573 
574    dmtxVector2Norm(dmtxVector2Sub(&vA, &c0, &c1));
575    dmtxVector2Norm(dmtxVector2Sub(&vB, &c2, &c1));
576 
577    dmtxMatrix3Rotate(m, angle);
578    dmtxMatrix3VMultiplyBy(&vB, m);
579 
580    return dmtxVector2Dot(&vA, &vB);
581 }
582 
583 /**
584  * \brief  Read color of Data Matrix module location
585  * \param  dec
586  * \param  reg
587  * \param  symbolRow
588  * \param  symbolCol
589  * \param  sizeIdx
590  * \return Averaged module color
591  */
592 static int
ReadModuleColor(DmtxDecode * dec,DmtxRegion * reg,int symbolRow,int symbolCol,int sizeIdx,int colorPlane)593 ReadModuleColor(DmtxDecode *dec, DmtxRegion *reg, int symbolRow, int symbolCol,
594       int sizeIdx, int colorPlane)
595 {
596    int i;
597    int symbolRows, symbolCols;
598    int color, colorTmp;
599    double sampleX[] = { 0.5, 0.4, 0.5, 0.6, 0.5 };
600    double sampleY[] = { 0.5, 0.5, 0.4, 0.5, 0.6 };
601    DmtxVector2 p;
602 
603    symbolRows = dmtxGetSymbolAttribute(DmtxSymAttribSymbolRows, sizeIdx);
604    symbolCols = dmtxGetSymbolAttribute(DmtxSymAttribSymbolCols, sizeIdx);
605 
606    color = 0;
607    for(i = 0; i < 5; i++) {
608 
609       p.X = (1.0/symbolCols) * (symbolCol + sampleX[i]);
610       p.Y = (1.0/symbolRows) * (symbolRow + sampleY[i]);
611 
612       dmtxMatrix3VMultiplyBy(&p, reg->fit2raw);
613 
614       //fprintf(stdout, "%dx%d\n", (int)(p.X + 0.5), (int)(p.Y + 0.5));
615 
616       dmtxDecodeGetPixelValue(dec, (int)(p.X + 0.5), (int)(p.Y + 0.5),
617             colorPlane, &colorTmp);
618       color += colorTmp;
619    }
620    //fprintf(stdout, "\n");
621    return color/5;
622 }
623 
624 /**
625  * \brief  Determine barcode size, expressed in modules
626  * \param  image
627  * \param  reg
628  * \return DmtxPass | DmtxFail
629  */
630 static DmtxPassFail
MatrixRegionFindSize(DmtxDecode * dec,DmtxRegion * reg)631 MatrixRegionFindSize(DmtxDecode *dec, DmtxRegion *reg)
632 {
633    int row, col;
634    int sizeIdxBeg, sizeIdxEnd;
635    int sizeIdx, bestSizeIdx;
636    int symbolRows, symbolCols;
637    int jumpCount, errors;
638    int color;
639    int colorOnAvg, bestColorOnAvg;
640    int colorOffAvg, bestColorOffAvg;
641    int contrast, bestContrast;
642 //   DmtxImage *img;
643 
644 //   img = dec->image;
645    bestSizeIdx = DmtxUndefined;
646    bestContrast = 0;
647    bestColorOnAvg = bestColorOffAvg = 0;
648 
649    if(dec->sizeIdxExpected == DmtxSymbolShapeAuto) {
650       sizeIdxBeg = 0;
651       sizeIdxEnd = DmtxSymbolSquareCount + DmtxSymbolRectCount;
652    }
653    else if(dec->sizeIdxExpected == DmtxSymbolSquareAuto) {
654       sizeIdxBeg = 0;
655       sizeIdxEnd = DmtxSymbolSquareCount;
656    }
657    else if(dec->sizeIdxExpected == DmtxSymbolRectAuto) {
658       sizeIdxBeg = DmtxSymbolSquareCount;
659       sizeIdxEnd = DmtxSymbolSquareCount + DmtxSymbolRectCount;
660    }
661    else {
662       sizeIdxBeg = dec->sizeIdxExpected;
663       sizeIdxEnd = dec->sizeIdxExpected + 1;
664    }
665 
666    /* Test each barcode size to find best contrast in calibration modules */
667    for(sizeIdx = sizeIdxBeg; sizeIdx < sizeIdxEnd; sizeIdx++) {
668 
669       symbolRows = dmtxGetSymbolAttribute(DmtxSymAttribSymbolRows, sizeIdx);
670       symbolCols = dmtxGetSymbolAttribute(DmtxSymAttribSymbolCols, sizeIdx);
671       colorOnAvg = colorOffAvg = 0;
672 
673       /* Sum module colors along horizontal calibration bar */
674       row = symbolRows - 1;
675       for(col = 0; col < symbolCols; col++) {
676          color = ReadModuleColor(dec, reg, row, col, sizeIdx, reg->flowBegin.plane);
677          if((col & 0x01) != 0x00)
678             colorOffAvg += color;
679          else
680             colorOnAvg += color;
681       }
682 
683       /* Sum module colors along vertical calibration bar */
684       col = symbolCols - 1;
685       for(row = 0; row < symbolRows; row++) {
686          color = ReadModuleColor(dec, reg, row, col, sizeIdx, reg->flowBegin.plane);
687          if((row & 0x01) != 0x00)
688             colorOffAvg += color;
689          else
690             colorOnAvg += color;
691       }
692 
693       colorOnAvg = (colorOnAvg * 2)/(symbolRows + symbolCols);
694       colorOffAvg = (colorOffAvg * 2)/(symbolRows + symbolCols);
695 
696       contrast = abs(colorOnAvg - colorOffAvg);
697       if(contrast < 20)
698          continue;
699 
700       if(contrast > bestContrast) {
701          bestContrast = contrast;
702          bestSizeIdx = sizeIdx;
703          bestColorOnAvg = colorOnAvg;
704          bestColorOffAvg = colorOffAvg;
705       }
706    }
707 
708    /* If no sizes produced acceptable contrast then call it quits */
709    if(bestSizeIdx == DmtxUndefined || bestContrast < 20)
710       return DmtxFail;
711 
712    reg->sizeIdx = bestSizeIdx;
713    reg->onColor = bestColorOnAvg;
714    reg->offColor = bestColorOffAvg;
715 
716    reg->symbolRows = dmtxGetSymbolAttribute(DmtxSymAttribSymbolRows, reg->sizeIdx);
717    reg->symbolCols = dmtxGetSymbolAttribute(DmtxSymAttribSymbolCols, reg->sizeIdx);
718    reg->mappingRows = dmtxGetSymbolAttribute(DmtxSymAttribMappingMatrixRows, reg->sizeIdx);
719    reg->mappingCols = dmtxGetSymbolAttribute(DmtxSymAttribMappingMatrixCols, reg->sizeIdx);
720 
721    /* Tally jumps on horizontal calibration bar to verify sizeIdx */
722    jumpCount = CountJumpTally(dec, reg, 0, reg->symbolRows - 1, DmtxDirRight);
723    errors = abs(1 + jumpCount - reg->symbolCols);
724    if(jumpCount < 0 || errors > 2)
725       return DmtxFail;
726 
727    /* Tally jumps on vertical calibration bar to verify sizeIdx */
728    jumpCount = CountJumpTally(dec, reg, reg->symbolCols - 1, 0, DmtxDirUp);
729    errors = abs(1 + jumpCount - reg->symbolRows);
730    if(jumpCount < 0 || errors > 2)
731       return DmtxFail;
732 
733    /* Tally jumps on horizontal finder bar to verify sizeIdx */
734    errors = CountJumpTally(dec, reg, 0, 0, DmtxDirRight);
735    if(jumpCount < 0 || errors > 2)
736       return DmtxFail;
737 
738    /* Tally jumps on vertical finder bar to verify sizeIdx */
739    errors = CountJumpTally(dec, reg, 0, 0, DmtxDirUp);
740    if(errors < 0 || errors > 2)
741       return DmtxFail;
742 
743    /* Tally jumps on surrounding whitespace, else fail */
744    errors = CountJumpTally(dec, reg, 0, -1, DmtxDirRight);
745    if(errors < 0 || errors > 2)
746       return DmtxFail;
747 
748    errors = CountJumpTally(dec, reg, -1, 0, DmtxDirUp);
749    if(errors < 0 || errors > 2)
750       return DmtxFail;
751 
752    errors = CountJumpTally(dec, reg, 0, reg->symbolRows, DmtxDirRight);
753    if(errors < 0 || errors > 2)
754       return DmtxFail;
755 
756    errors = CountJumpTally(dec, reg, reg->symbolCols, 0, DmtxDirUp);
757    if(errors < 0 || errors > 2)
758       return DmtxFail;
759 
760    return DmtxPass;
761 }
762 
763 /**
764  * \brief  Count the number of number of transitions between light and dark
765  * \param  img
766  * \param  reg
767  * \param  xStart
768  * \param  yStart
769  * \param  dir
770  * \return Jump count
771  */
772 static int
CountJumpTally(DmtxDecode * dec,DmtxRegion * reg,int xStart,int yStart,DmtxDirection dir)773 CountJumpTally(DmtxDecode *dec, DmtxRegion *reg, int xStart, int yStart, DmtxDirection dir)
774 {
775    int x, xInc = 0;
776    int y, yInc = 0;
777    int state = DmtxModuleOn;
778    int jumpCount = 0;
779    int jumpThreshold;
780    int tModule, tPrev;
781    int darkOnLight;
782    int color;
783 
784    assert(xStart == 0 || yStart == 0);
785    assert(dir == DmtxDirRight || dir == DmtxDirUp);
786 
787    if(dir == DmtxDirRight)
788       xInc = 1;
789    else
790       yInc = 1;
791 
792    if(xStart == -1 || xStart == reg->symbolCols ||
793          yStart == -1 || yStart == reg->symbolRows)
794       state = DmtxModuleOff;
795 
796    darkOnLight = (int)(reg->offColor > reg->onColor);
797    jumpThreshold = abs((int)(0.4 * (reg->onColor - reg->offColor) + 0.5));
798    color = ReadModuleColor(dec, reg, yStart, xStart, reg->sizeIdx, reg->flowBegin.plane);
799    tModule = (darkOnLight) ? reg->offColor - color : color - reg->offColor;
800 
801    for(x = xStart + xInc, y = yStart + yInc;
802          (dir == DmtxDirRight && x < reg->symbolCols) ||
803          (dir == DmtxDirUp && y < reg->symbolRows);
804          x += xInc, y += yInc) {
805 
806       tPrev = tModule;
807       color = ReadModuleColor(dec, reg, y, x, reg->sizeIdx, reg->flowBegin.plane);
808       tModule = (darkOnLight) ? reg->offColor - color : color - reg->offColor;
809 
810       if(state == DmtxModuleOff) {
811          if(tModule > tPrev + jumpThreshold) {
812             jumpCount++;
813             state = DmtxModuleOn;
814          }
815       }
816       else {
817          if(tModule < tPrev - jumpThreshold) {
818             jumpCount++;
819             state = DmtxModuleOff;
820          }
821       }
822    }
823 
824    return jumpCount;
825 }
826 
827 /**
828  *
829  *
830  */
831 static DmtxPointFlow
GetPointFlow(DmtxDecode * dec,int colorPlane,DmtxPixelLoc loc,int arrive)832 GetPointFlow(DmtxDecode *dec, int colorPlane, DmtxPixelLoc loc, int arrive)
833 {
834    static const int coefficient[] = {  0,  1,  2,  1,  0, -1, -2, -1 };
835    int err;
836    int patternIdx, coefficientIdx;
837    int compass, compassMax;
838    int mag[4] = { 0 };
839    int xAdjust, yAdjust;
840    int color, colorPattern[8];
841    DmtxPointFlow flow;
842 
843    for(patternIdx = 0; patternIdx < 8; patternIdx++) {
844       xAdjust = loc.X + dmtxPatternX[patternIdx];
845       yAdjust = loc.Y + dmtxPatternY[patternIdx];
846       err = dmtxDecodeGetPixelValue(dec, xAdjust, yAdjust, colorPlane,
847             &colorPattern[patternIdx]);
848       if(err == DmtxFail)
849          return dmtxBlankEdge;
850    }
851 
852    /* Calculate this pixel's flow intensity for each direction (-45, 0, 45, 90) */
853    compassMax = 0;
854    for(compass = 0; compass < 4; compass++) {
855 
856       /* Add portion from each position in the convolution matrix pattern */
857       for(patternIdx = 0; patternIdx < 8; patternIdx++) {
858 
859          coefficientIdx = (patternIdx - compass + 8) % 8;
860          if(coefficient[coefficientIdx] == 0)
861             continue;
862 
863          color = colorPattern[patternIdx];
864 
865          switch(coefficient[coefficientIdx]) {
866             case 2:
867                mag[compass] += color;
868                /* Fall through */
869             case 1:
870                mag[compass] += color;
871                break;
872             case -2:
873                mag[compass] -= color;
874                /* Fall through */
875             case -1:
876                mag[compass] -= color;
877                break;
878          }
879       }
880 
881       /* Identify strongest compass flow */
882       if(compass != 0 && abs(mag[compass]) > abs(mag[compassMax]))
883          compassMax = compass;
884    }
885 
886    /* Convert signed compass direction into unique flow directions (0-7) */
887    flow.plane = colorPlane;
888    flow.arrive = arrive;
889    flow.depart = (mag[compassMax] > 0) ? compassMax + 4 : compassMax;
890    flow.mag = abs(mag[compassMax]);
891    flow.loc = loc;
892 
893    return flow;
894 }
895 
896 /**
897  *
898  *
899  */
900 static DmtxPointFlow
FindStrongestNeighbor(DmtxDecode * dec,DmtxPointFlow center,int sign)901 FindStrongestNeighbor(DmtxDecode *dec, DmtxPointFlow center, int sign)
902 {
903    int i;
904    int strongIdx;
905    int attempt, attemptDiff;
906    int occupied;
907    unsigned char *cache;
908    DmtxPixelLoc loc;
909    DmtxPointFlow flow[8];
910 
911    attempt = (sign < 0) ? center.depart : (center.depart+4)%8;
912 
913    occupied = 0;
914    strongIdx = DmtxUndefined;
915    for(i = 0; i < 8; i++) {
916 
917       loc.X = center.loc.X + dmtxPatternX[i];
918       loc.Y = center.loc.Y + dmtxPatternY[i];
919 
920       cache = dmtxDecodeGetCache(dec, loc.X, loc.Y);
921       if(cache == NULL)
922          continue;
923 
924       if((int)(*cache & 0x80) != 0x00) {
925          if(++occupied > 2)
926             return dmtxBlankEdge;
927          else
928             continue;
929       }
930 
931       attemptDiff = abs(attempt - i);
932       if(attemptDiff > 4)
933          attemptDiff = 8 - attemptDiff;
934       if(attemptDiff > 1)
935          continue;
936 
937       flow[i] = GetPointFlow(dec, center.plane, loc, i);
938 
939       if(strongIdx == DmtxUndefined || flow[i].mag > flow[strongIdx].mag ||
940             (flow[i].mag == flow[strongIdx].mag && ((i & 0x01) != 0))) {
941          strongIdx = i;
942       }
943    }
944 
945    return (strongIdx == DmtxUndefined) ? dmtxBlankEdge : flow[strongIdx];
946 }
947 
948 /**
949  *
950  *
951  */
952 static DmtxFollow
FollowSeek(DmtxDecode * dec,DmtxRegion * reg,int seek)953 FollowSeek(DmtxDecode *dec, DmtxRegion *reg, int seek)
954 {
955    int i;
956    int sign;
957    DmtxFollow follow;
958 
959    follow.loc = reg->flowBegin.loc;
960    follow.step = 0;
961    follow.ptr = dmtxDecodeGetCache(dec, follow.loc.X, follow.loc.Y);
962    assert(follow.ptr != NULL);
963    follow.neighbor = *follow.ptr;
964 
965    sign = (seek > 0) ? +1 : -1;
966    for(i = 0; i != seek; i += sign) {
967       follow = FollowStep(dec, reg, follow, sign);
968       assert(follow.ptr != NULL);
969       assert(abs(follow.step) <= reg->stepsTotal);
970    }
971 
972    return follow;
973 }
974 
975 /**
976  *
977  *
978  */
979 static DmtxFollow
FollowSeekLoc(DmtxDecode * dec,DmtxPixelLoc loc)980 FollowSeekLoc(DmtxDecode *dec, DmtxPixelLoc loc)
981 {
982    DmtxFollow follow;
983 
984    follow.loc = loc;
985    follow.step = 0;
986    follow.ptr = dmtxDecodeGetCache(dec, follow.loc.X, follow.loc.Y);
987    assert(follow.ptr != NULL);
988    follow.neighbor = *follow.ptr;
989 
990    return follow;
991 }
992 
993 
994 /**
995  *
996  *
997  */
998 static DmtxFollow
FollowStep(DmtxDecode * dec,DmtxRegion * reg,DmtxFollow followBeg,int sign)999 FollowStep(DmtxDecode *dec, DmtxRegion *reg, DmtxFollow followBeg, int sign)
1000 {
1001    int patternIdx;
1002    int stepMod;
1003    int factor;
1004    DmtxFollow follow;
1005 
1006    assert(abs(sign) == 1);
1007    assert((int)(followBeg.neighbor & 0x40) != 0x00);
1008 
1009    factor = reg->stepsTotal + 1;
1010    if(sign > 0)
1011       stepMod = (factor + (followBeg.step % factor)) % factor;
1012    else
1013       stepMod = (factor - (followBeg.step % factor)) % factor;
1014 
1015    /* End of positive trail -- magic jump */
1016    if(sign > 0 && stepMod == reg->jumpToNeg) {
1017       follow.loc = reg->finalNeg;
1018    }
1019    /* End of negative trail -- magic jump */
1020    else if(sign < 0 && stepMod == reg->jumpToPos) {
1021       follow.loc = reg->finalPos;
1022    }
1023    /* Trail in progress -- normal jump */
1024    else {
1025       patternIdx = (sign < 0) ? followBeg.neighbor & 0x07 : ((followBeg.neighbor & 0x38) >> 3);
1026       follow.loc.X = followBeg.loc.X + dmtxPatternX[patternIdx];
1027       follow.loc.Y = followBeg.loc.Y + dmtxPatternY[patternIdx];
1028    }
1029 
1030    follow.step = followBeg.step + sign;
1031    follow.ptr = dmtxDecodeGetCache(dec, follow.loc.X, follow.loc.Y);
1032    assert(follow.ptr != NULL);
1033    follow.neighbor = *follow.ptr;
1034 
1035    return follow;
1036 }
1037 
1038 /**
1039  *
1040  *
1041  */
1042 static DmtxFollow
FollowStep2(DmtxDecode * dec,DmtxFollow followBeg,int sign)1043 FollowStep2(DmtxDecode *dec, DmtxFollow followBeg, int sign)
1044 {
1045    int patternIdx;
1046    DmtxFollow follow;
1047 
1048    assert(abs(sign) == 1);
1049    assert((int)(followBeg.neighbor & 0x40) != 0x00);
1050 
1051    patternIdx = (sign < 0) ? followBeg.neighbor & 0x07 : ((followBeg.neighbor & 0x38) >> 3);
1052    follow.loc.X = followBeg.loc.X + dmtxPatternX[patternIdx];
1053    follow.loc.Y = followBeg.loc.Y + dmtxPatternY[patternIdx];
1054 
1055    follow.step = followBeg.step + sign;
1056    follow.ptr = dmtxDecodeGetCache(dec, follow.loc.X, follow.loc.Y);
1057    assert(follow.ptr != NULL);
1058    follow.neighbor = *follow.ptr;
1059 
1060    return follow;
1061 }
1062 
1063 /**
1064  * vaiiiooo
1065  * --------
1066  * 0x80 v = visited bit
1067  * 0x40 a = assigned bit
1068  * 0x38 u = 3 bits points upstream 0-7
1069  * 0x07 d = 3 bits points downstream 0-7
1070  */
1071 static DmtxPassFail
TrailBlazeContinuous(DmtxDecode * dec,DmtxRegion * reg,DmtxPointFlow flowBegin,int maxDiagonal)1072 TrailBlazeContinuous(DmtxDecode *dec, DmtxRegion *reg, DmtxPointFlow flowBegin, int maxDiagonal)
1073 {
1074    int posAssigns, negAssigns, clears;
1075    int sign;
1076    int steps;
1077    unsigned char *cache, *cacheNext, *cacheBeg;
1078    DmtxPointFlow flow, flowNext;
1079    DmtxPixelLoc boundMin, boundMax;
1080 
1081    boundMin = boundMax = flowBegin.loc;
1082    cacheBeg = dmtxDecodeGetCache(dec, flowBegin.loc.X, flowBegin.loc.Y);
1083    if(cacheBeg == NULL)
1084       return DmtxFail;
1085    *cacheBeg = (0x80 | 0x40); /* Mark location as visited and assigned */
1086 
1087    reg->flowBegin = flowBegin;
1088 
1089    posAssigns = negAssigns = 0;
1090    for(sign = 1; sign >= -1; sign -= 2) {
1091 
1092       flow = flowBegin;
1093       cache = cacheBeg;
1094 
1095       for(steps = 0; ; steps++) {
1096 
1097          if(maxDiagonal != DmtxUndefined && (boundMax.X - boundMin.X > maxDiagonal ||
1098                boundMax.Y - boundMin.Y > maxDiagonal))
1099             break;
1100 
1101          /* Find the strongest eligible neighbor */
1102          flowNext = FindStrongestNeighbor(dec, flow, sign);
1103          if(flowNext.mag < 50)
1104             break;
1105 
1106          /* Get the neighbor's cache location */
1107          cacheNext = dmtxDecodeGetCache(dec, flowNext.loc.X, flowNext.loc.Y);
1108          if(cacheNext == NULL)
1109             break;
1110          assert(!(*cacheNext & 0x80));
1111 
1112          /* Mark departure from current location. If flowing downstream
1113           * (sign < 0) then departure vector here is the arrival vector
1114           * of the next location. Upstream flow uses the opposite rule. */
1115          *cache |= (sign < 0) ? flowNext.arrive : flowNext.arrive << 3;
1116 
1117          /* Mark known direction for next location */
1118          /* If testing downstream (sign < 0) then next upstream is opposite of next arrival */
1119          /* If testing upstream (sign > 0) then next downstream is opposite of next arrival */
1120          *cacheNext = (sign < 0) ? (((flowNext.arrive + 4)%8) << 3) : ((flowNext.arrive + 4)%8);
1121          *cacheNext |= (0x80 | 0x40); /* Mark location as visited and assigned */
1122          if(sign > 0)
1123             posAssigns++;
1124          else
1125             negAssigns++;
1126          cache = cacheNext;
1127          flow = flowNext;
1128 
1129          if(flow.loc.X > boundMax.X)
1130             boundMax.X = flow.loc.X;
1131          else if(flow.loc.X < boundMin.X)
1132             boundMin.X = flow.loc.X;
1133          if(flow.loc.Y > boundMax.Y)
1134             boundMax.Y = flow.loc.Y;
1135          else if(flow.loc.Y < boundMin.Y)
1136             boundMin.Y = flow.loc.Y;
1137 
1138 /*       CALLBACK_POINT_PLOT(flow.loc, (sign > 0) ? 2 : 3, 1, 2); */
1139       }
1140 
1141       if(sign > 0) {
1142          reg->finalPos = flow.loc;
1143          reg->jumpToNeg = steps;
1144       }
1145       else {
1146          reg->finalNeg = flow.loc;
1147          reg->jumpToPos = steps;
1148       }
1149    }
1150    reg->stepsTotal = reg->jumpToPos + reg->jumpToNeg;
1151    reg->boundMin = boundMin;
1152    reg->boundMax = boundMax;
1153 
1154    /* Clear "visited" bit from trail */
1155    clears = TrailClear(dec, reg, 0x80);
1156    assert(posAssigns + negAssigns == clears - 1);
1157 
1158    /* XXX clean this up ... redundant test above */
1159    if(maxDiagonal != DmtxUndefined && (boundMax.X - boundMin.X > maxDiagonal ||
1160          boundMax.Y - boundMin.Y > maxDiagonal))
1161       return DmtxFail;
1162 
1163    return DmtxPass;
1164 }
1165 
1166 /**
1167  * recives bresline, and follows strongest neighbor unless it involves
1168  * ratcheting bresline inward or backward (although back + outward is allowed).
1169  *
1170  */
1171 static int
TrailBlazeGapped(DmtxDecode * dec,DmtxRegion * reg,DmtxBresLine line,int streamDir)1172 TrailBlazeGapped(DmtxDecode *dec, DmtxRegion *reg, DmtxBresLine line, int streamDir)
1173 {
1174    unsigned char *beforeCache, *afterCache;
1175    DmtxBoolean onEdge;
1176    int distSq, distSqMax;
1177    int travel, outward;
1178    int xDiff, yDiff;
1179    int steps;
1180    int stepDir, dirMap[] = { 0, 1, 2, 7, 8, 3, 6, 5, 4 };
1181    DmtxPassFail err;
1182    DmtxPixelLoc beforeStep, afterStep;
1183    DmtxPointFlow flow, flowNext;
1184    DmtxPixelLoc loc0;
1185    int xStep, yStep;
1186 
1187    loc0 = line.loc;
1188    flow = GetPointFlow(dec, reg->flowBegin.plane, loc0, dmtxNeighborNone);
1189    distSqMax = (line.xDelta * line.xDelta) + (line.yDelta * line.yDelta);
1190    steps = 0;
1191    onEdge = DmtxTrue;
1192 
1193    beforeStep = loc0;
1194    beforeCache = dmtxDecodeGetCache(dec, loc0.X, loc0.Y);
1195    if(beforeCache == NULL)
1196       return DmtxFail;
1197    else
1198       *beforeCache = 0x00; /* probably should just overwrite one direction */
1199 
1200    do {
1201       if(onEdge == DmtxTrue) {
1202          flowNext = FindStrongestNeighbor(dec, flow, streamDir);
1203          if(flowNext.mag == DmtxUndefined)
1204             break;
1205 
1206          err = BresLineGetStep(line, flowNext.loc, &travel, &outward);
1207          if (err == DmtxFail) { return DmtxFail; }
1208 
1209          if(flowNext.mag < 50 || outward < 0 || (outward == 0 && travel < 0)) {
1210             onEdge = DmtxFalse;
1211          }
1212          else {
1213             BresLineStep(&line, travel, outward);
1214             flow = flowNext;
1215          }
1216       }
1217 
1218       if(onEdge == DmtxFalse) {
1219          BresLineStep(&line, 1, 0);
1220          flow = GetPointFlow(dec, reg->flowBegin.plane, line.loc, dmtxNeighborNone);
1221          if(flow.mag > 50)
1222             onEdge = DmtxTrue;
1223       }
1224 
1225       afterStep = line.loc;
1226       afterCache = dmtxDecodeGetCache(dec, afterStep.X, afterStep.Y);
1227       if(afterCache == NULL)
1228          break;
1229 
1230       /* Determine step direction using pure magic */
1231       xStep = afterStep.X - beforeStep.X;
1232       yStep = afterStep.Y - beforeStep.Y;
1233       assert(abs(xStep) <= 1 && abs(yStep) <= 1);
1234       stepDir = dirMap[3 * yStep + xStep + 4];
1235       assert(stepDir != 8);
1236 
1237       if(streamDir < 0) {
1238          *beforeCache |= (0x40 | stepDir);
1239          *afterCache = (((stepDir + 4)%8) << 3);
1240       }
1241       else {
1242          *beforeCache |= (0x40 | (stepDir << 3));
1243          *afterCache = ((stepDir + 4)%8);
1244       }
1245 
1246       /* Guaranteed to have taken one step since top of loop */
1247       xDiff = line.loc.X - loc0.X;
1248       yDiff = line.loc.Y - loc0.Y;
1249       distSq = (xDiff * xDiff) + (yDiff * yDiff);
1250 
1251       beforeStep = line.loc;
1252       beforeCache = afterCache;
1253       steps++;
1254 
1255    } while(distSq < distSqMax);
1256 
1257    return steps;
1258 }
1259 
1260 /**
1261  *
1262  *
1263  */
1264 static int
TrailClear(DmtxDecode * dec,DmtxRegion * reg,int clearMask)1265 TrailClear(DmtxDecode *dec, DmtxRegion *reg, int clearMask)
1266 {
1267    int clears;
1268    DmtxFollow follow;
1269 
1270    assert((clearMask | 0xff) == 0xff);
1271 
1272    /* Clear "visited" bit from trail */
1273    clears = 0;
1274    follow = FollowSeek(dec, reg, 0);
1275    while(abs(follow.step) <= reg->stepsTotal) {
1276       assert((int)(*follow.ptr & clearMask) != 0x00);
1277       *follow.ptr &= (clearMask ^ 0xff);
1278       follow = FollowStep(dec, reg, follow, +1);
1279       clears++;
1280    }
1281 
1282    return clears;
1283 }
1284 
1285 /**
1286  *
1287  *
1288  */
1289 static DmtxBestLine
FindBestSolidLine(DmtxDecode * dec,DmtxRegion * reg,int step0,int step1,int streamDir,int houghAvoid)1290 FindBestSolidLine(DmtxDecode *dec, DmtxRegion *reg, int step0, int step1, int streamDir, int houghAvoid)
1291 {
1292    int hough[3][DMTX_HOUGH_RES] = { { 0 } };
1293    int houghMin, houghMax;
1294    char houghTest[DMTX_HOUGH_RES];
1295    int i;
1296    int step;
1297    int sign;
1298    int tripSteps;
1299    int angleBest;
1300    int hOffset, hOffsetBest;
1301    int xDiff, yDiff;
1302    int dH;
1303    DmtxRay2 rH;
1304    DmtxFollow follow;
1305    DmtxBestLine line;
1306    DmtxPixelLoc rHp;
1307 
1308    memset(&line, 0x00, sizeof(DmtxBestLine));
1309    memset(&rH, 0x00, sizeof(DmtxRay2));
1310    angleBest = 0;
1311    hOffset = hOffsetBest = 0;
1312 
1313    sign = 0;
1314 
1315    /* Always follow path flowing away from the trail start */
1316    if(step0 != 0) {
1317       if(step0 > 0) {
1318          sign = +1;
1319          tripSteps = (step1 - step0 + reg->stepsTotal) % reg->stepsTotal;
1320       }
1321       else {
1322          sign = -1;
1323          tripSteps = (step0 - step1 + reg->stepsTotal) % reg->stepsTotal;
1324       }
1325       if(tripSteps == 0)
1326          tripSteps = reg->stepsTotal;
1327    }
1328    else if(step1 != 0) {
1329       sign = (step1 > 0) ? +1 : -1;
1330       tripSteps = abs(step1);
1331    }
1332    else if(step1 == 0) {
1333       sign = +1;
1334       tripSteps = reg->stepsTotal;
1335    }
1336    assert(sign == streamDir);
1337 
1338    follow = FollowSeek(dec, reg, step0);
1339    rHp = follow.loc;
1340 
1341    line.stepBeg = line.stepPos = line.stepNeg = step0;
1342    line.locBeg = follow.loc;
1343    line.locPos = follow.loc;
1344    line.locNeg = follow.loc;
1345 
1346    /* Predetermine which angles to test */
1347    for(i = 0; i < DMTX_HOUGH_RES; i++) {
1348       if(houghAvoid == DmtxUndefined) {
1349          houghTest[i] = 1;
1350       }
1351       else {
1352          houghMin = (houghAvoid + DMTX_HOUGH_RES/6) % DMTX_HOUGH_RES;
1353          houghMax = (houghAvoid - DMTX_HOUGH_RES/6 + DMTX_HOUGH_RES) % DMTX_HOUGH_RES;
1354          if(houghMin > houghMax)
1355             houghTest[i] = (i > houghMin || i < houghMax) ? 1 : 0;
1356          else
1357             houghTest[i] = (i > houghMin && i < houghMax) ? 1 : 0;
1358       }
1359    }
1360 
1361    /* Test each angle for steps along path */
1362    for(step = 0; step < tripSteps; step++) {
1363 
1364       xDiff = follow.loc.X - rHp.X;
1365       yDiff = follow.loc.Y - rHp.Y;
1366 
1367       /* Increment Hough accumulator */
1368       for(i = 0; i < DMTX_HOUGH_RES; i++) {
1369 
1370          if((int)houghTest[i] == 0)
1371             continue;
1372 
1373          dH = (rHvX[i] * yDiff) - (rHvY[i] * xDiff);
1374          if(dH >= -384 && dH <= 384) {
1375 
1376             if(dH > 128)
1377                hOffset = 2;
1378             else if(dH >= -128)
1379                hOffset = 1;
1380             else
1381                hOffset = 0;
1382 
1383             hough[hOffset][i]++;
1384 
1385             /* New angle takes over lead */
1386             if(hough[hOffset][i] > hough[hOffsetBest][angleBest]) {
1387                angleBest = i;
1388                hOffsetBest = hOffset;
1389             }
1390          }
1391       }
1392 
1393 /*    CALLBACK_POINT_PLOT(follow.loc, (sign > 1) ? 4 : 3, 1, 2); */
1394 
1395       follow = FollowStep(dec, reg, follow, sign);
1396    }
1397 
1398    line.angle = angleBest;
1399    line.hOffset = hOffsetBest;
1400    line.mag = hough[hOffsetBest][angleBest];
1401 
1402    return line;
1403 }
1404 
1405 /**
1406  *
1407  *
1408  */
1409 static DmtxBestLine
FindBestSolidLine2(DmtxDecode * dec,DmtxPixelLoc loc0,int tripSteps,int sign,int houghAvoid)1410 FindBestSolidLine2(DmtxDecode *dec, DmtxPixelLoc loc0, int tripSteps, int sign, int houghAvoid)
1411 {
1412    int hough[3][DMTX_HOUGH_RES] = { { 0 } };
1413    int houghMin, houghMax;
1414    char houghTest[DMTX_HOUGH_RES];
1415    int i;
1416    int step;
1417    int angleBest;
1418    int hOffset, hOffsetBest;
1419    int xDiff, yDiff;
1420    int dH;
1421    DmtxRay2 rH;
1422    DmtxBestLine line;
1423    DmtxPixelLoc rHp;
1424    DmtxFollow follow;
1425 
1426    memset(&line, 0x00, sizeof(DmtxBestLine));
1427    memset(&rH, 0x00, sizeof(DmtxRay2));
1428    angleBest = 0;
1429    hOffset = hOffsetBest = 0;
1430 
1431    follow = FollowSeekLoc(dec, loc0);
1432    rHp = line.locBeg = line.locPos = line.locNeg = follow.loc;
1433    line.stepBeg = line.stepPos = line.stepNeg = 0;
1434 
1435    /* Predetermine which angles to test */
1436    for(i = 0; i < DMTX_HOUGH_RES; i++) {
1437       if(houghAvoid == DmtxUndefined) {
1438          houghTest[i] = 1;
1439       }
1440       else {
1441          houghMin = (houghAvoid + DMTX_HOUGH_RES/6) % DMTX_HOUGH_RES;
1442          houghMax = (houghAvoid - DMTX_HOUGH_RES/6 + DMTX_HOUGH_RES) % DMTX_HOUGH_RES;
1443          if(houghMin > houghMax)
1444             houghTest[i] = (i > houghMin || i < houghMax) ? 1 : 0;
1445          else
1446             houghTest[i] = (i > houghMin && i < houghMax) ? 1 : 0;
1447       }
1448    }
1449 
1450    /* Test each angle for steps along path */
1451    for(step = 0; step < tripSteps; step++) {
1452 
1453       xDiff = follow.loc.X - rHp.X;
1454       yDiff = follow.loc.Y - rHp.Y;
1455 
1456       /* Increment Hough accumulator */
1457       for(i = 0; i < DMTX_HOUGH_RES; i++) {
1458 
1459          if((int)houghTest[i] == 0)
1460             continue;
1461 
1462          dH = (rHvX[i] * yDiff) - (rHvY[i] * xDiff);
1463          if(dH >= -384 && dH <= 384) {
1464             if(dH > 128)
1465                hOffset = 2;
1466             else if(dH >= -128)
1467                hOffset = 1;
1468             else
1469                hOffset = 0;
1470 
1471             hough[hOffset][i]++;
1472 
1473             /* New angle takes over lead */
1474             if(hough[hOffset][i] > hough[hOffsetBest][angleBest]) {
1475                angleBest = i;
1476                hOffsetBest = hOffset;
1477             }
1478          }
1479       }
1480 
1481 /*    CALLBACK_POINT_PLOT(follow.loc, (sign > 1) ? 4 : 3, 1, 2); */
1482 
1483       follow = FollowStep2(dec, follow, sign);
1484    }
1485 
1486    line.angle = angleBest;
1487    line.hOffset = hOffsetBest;
1488    line.mag = hough[hOffsetBest][angleBest];
1489 
1490    return line;
1491 }
1492 
1493 /**
1494  *
1495  *
1496  */
1497 static DmtxPassFail
FindTravelLimits(DmtxDecode * dec,DmtxRegion * reg,DmtxBestLine * line)1498 FindTravelLimits(DmtxDecode *dec, DmtxRegion *reg, DmtxBestLine *line)
1499 {
1500    int i;
1501    int distSq, distSqMax;
1502    int xDiff, yDiff;
1503    int posRunning, negRunning;
1504    int posTravel, negTravel;
1505    int posWander, posWanderMin, posWanderMax, posWanderMinLock, posWanderMaxLock;
1506    int negWander, negWanderMin, negWanderMax, negWanderMinLock, negWanderMaxLock;
1507    int cosAngle, sinAngle;
1508    DmtxFollow followPos, followNeg;
1509    DmtxPixelLoc loc0, posMax, negMax;
1510 
1511    /* line->stepBeg is already known to sit on the best Hough line */
1512    followPos = followNeg = FollowSeek(dec, reg, line->stepBeg);
1513    loc0 = followPos.loc;
1514 
1515    cosAngle = rHvX[line->angle];
1516    sinAngle = rHvY[line->angle];
1517 
1518    distSqMax = 0;
1519    posMax = negMax = followPos.loc;
1520 
1521    posTravel = negTravel = 0;
1522    posWander = posWanderMin = posWanderMax = posWanderMinLock = posWanderMaxLock = 0;
1523    negWander = negWanderMin = negWanderMax = negWanderMinLock = negWanderMaxLock = 0;
1524 
1525    for(i = 0; i < reg->stepsTotal/2; i++) {
1526 
1527       posRunning = (int)(i < 10 || abs(posWander) < abs(posTravel));
1528       negRunning = (int)(i < 10 || abs(negWander) < abs(negTravel));
1529 
1530       if(posRunning != 0) {
1531          xDiff = followPos.loc.X - loc0.X;
1532          yDiff = followPos.loc.Y - loc0.Y;
1533          posTravel = (cosAngle * xDiff) + (sinAngle * yDiff);
1534          posWander = (cosAngle * yDiff) - (sinAngle * xDiff);
1535 
1536          if(posWander >= -3*256 && posWander <= 3*256) {
1537             distSq = DistanceSquared(followPos.loc, negMax);
1538             if(distSq > distSqMax) {
1539                posMax = followPos.loc;
1540                distSqMax = distSq;
1541                line->stepPos = followPos.step;
1542                line->locPos = followPos.loc;
1543                posWanderMinLock = posWanderMin;
1544                posWanderMaxLock = posWanderMax;
1545             }
1546          }
1547          else {
1548             posWanderMin = min(posWanderMin, posWander);
1549             posWanderMax = max(posWanderMax, posWander);
1550          }
1551       }
1552       else if(!negRunning) {
1553          break;
1554       }
1555 
1556       if(negRunning != 0) {
1557          xDiff = followNeg.loc.X - loc0.X;
1558          yDiff = followNeg.loc.Y - loc0.Y;
1559          negTravel = (cosAngle * xDiff) + (sinAngle * yDiff);
1560          negWander = (cosAngle * yDiff) - (sinAngle * xDiff);
1561 
1562          if(negWander >= -3*256 && negWander < 3*256) {
1563             distSq = DistanceSquared(followNeg.loc, posMax);
1564             if(distSq > distSqMax) {
1565                negMax = followNeg.loc;
1566                distSqMax = distSq;
1567                line->stepNeg = followNeg.step;
1568                line->locNeg = followNeg.loc;
1569                negWanderMinLock = negWanderMin;
1570                negWanderMaxLock = negWanderMax;
1571             }
1572          }
1573          else {
1574             negWanderMin = min(negWanderMin, negWander);
1575             negWanderMax = max(negWanderMax, negWander);
1576          }
1577       }
1578       else if(!posRunning) {
1579          break;
1580       }
1581 
1582 /*  CALLBACK_POINT_PLOT(followPos.loc, 2, 1, 2);
1583     CALLBACK_POINT_PLOT(followNeg.loc, 4, 1, 2); */
1584 
1585       followPos = FollowStep(dec, reg, followPos, +1);
1586       followNeg = FollowStep(dec, reg, followNeg, -1);
1587    }
1588    line->devn = max(posWanderMaxLock - posWanderMinLock, negWanderMaxLock - negWanderMinLock)/256;
1589    line->distSq = distSqMax;
1590 
1591 /* CALLBACK_POINT_PLOT(posMax, 2, 1, 1);
1592    CALLBACK_POINT_PLOT(negMax, 2, 1, 1); */
1593 
1594    return DmtxPass;
1595 }
1596 
1597 /**
1598  *
1599  *
1600  */
1601 static DmtxPassFail
MatrixRegionAlignCalibEdge(DmtxDecode * dec,DmtxRegion * reg,int edgeLoc)1602 MatrixRegionAlignCalibEdge(DmtxDecode *dec, DmtxRegion *reg, int edgeLoc)
1603 {
1604    int streamDir;
1605    int steps;
1606    int avoidAngle;
1607    int symbolShape;
1608    DmtxVector2 pTmp;
1609    DmtxPixelLoc loc0, loc1, locOrigin;
1610    DmtxBresLine line;
1611    DmtxFollow follow;
1612    DmtxBestLine bestLine;
1613 
1614    /* Determine pixel coordinates of origin */
1615    pTmp.X = 0.0;
1616    pTmp.Y = 0.0;
1617    dmtxMatrix3VMultiplyBy(&pTmp, reg->fit2raw);
1618    locOrigin.X = (int)(pTmp.X + 0.5);
1619    locOrigin.Y = (int)(pTmp.Y + 0.5);
1620 
1621    if(dec->sizeIdxExpected == DmtxSymbolSquareAuto ||
1622          (dec->sizeIdxExpected >= DmtxSymbol10x10 &&
1623          dec->sizeIdxExpected <= DmtxSymbol144x144))
1624       symbolShape = DmtxSymbolSquareAuto;
1625    else if(dec->sizeIdxExpected == DmtxSymbolRectAuto ||
1626          (dec->sizeIdxExpected >= DmtxSymbol8x18 &&
1627          dec->sizeIdxExpected <= DmtxSymbol16x48))
1628       symbolShape = DmtxSymbolRectAuto;
1629    else
1630       symbolShape = DmtxSymbolShapeAuto;
1631 
1632    /* Determine end locations of test line */
1633    if(edgeLoc == DmtxEdgeTop) {
1634       streamDir = reg->polarity * -1;
1635       avoidAngle = reg->leftLine.angle;
1636       follow = FollowSeekLoc(dec, reg->locT);
1637       pTmp.X = 0.8;
1638       pTmp.Y = (symbolShape == DmtxSymbolRectAuto) ? 0.2 : 0.6;
1639    }
1640    else {
1641       assert(edgeLoc == DmtxEdgeRight);
1642       streamDir = reg->polarity;
1643       avoidAngle = reg->bottomLine.angle;
1644       follow = FollowSeekLoc(dec, reg->locR);
1645       pTmp.X = (symbolShape == DmtxSymbolSquareAuto) ? 0.7 : 0.9;
1646       pTmp.Y = 0.8;
1647    }
1648 
1649    dmtxMatrix3VMultiplyBy(&pTmp, reg->fit2raw);
1650    loc1.X = (int)(pTmp.X + 0.5);
1651    loc1.Y = (int)(pTmp.Y + 0.5);
1652 
1653    loc0 = follow.loc;
1654    line = BresLineInit(loc0, loc1, locOrigin);
1655    steps = TrailBlazeGapped(dec, reg, line, streamDir);
1656 
1657    bestLine = FindBestSolidLine2(dec, loc0, steps, streamDir, avoidAngle);
1658    if(bestLine.mag < 5) {
1659       ;
1660    }
1661 
1662    if(edgeLoc == DmtxEdgeTop) {
1663       reg->topKnown = 1;
1664       reg->topAngle = bestLine.angle;
1665       reg->topLoc = bestLine.locBeg;
1666    }
1667    else {
1668       reg->rightKnown = 1;
1669       reg->rightAngle = bestLine.angle;
1670       reg->rightLoc = bestLine.locBeg;
1671    }
1672 
1673    return DmtxPass;
1674 }
1675 
1676 /**
1677  *
1678  *
1679  */
1680 static DmtxBresLine
BresLineInit(DmtxPixelLoc loc0,DmtxPixelLoc loc1,DmtxPixelLoc locInside)1681 BresLineInit(DmtxPixelLoc loc0, DmtxPixelLoc loc1, DmtxPixelLoc locInside)
1682 {
1683    int cp;
1684    DmtxBresLine line;
1685    DmtxPixelLoc *locBeg, *locEnd;
1686 
1687    /* XXX Verify that loc0 and loc1 are inbounds */
1688 
1689    /* Values that stay the same after initialization */
1690    line.loc0 = loc0;
1691    line.loc1 = loc1;
1692    line.xStep = (loc0.X < loc1.X) ? +1 : -1;
1693    line.yStep = (loc0.Y < loc1.Y) ? +1 : -1;
1694    line.xDelta = abs(loc1.X - loc0.X);
1695    line.yDelta = abs(loc1.Y - loc0.Y);
1696    line.steep = (int)(line.yDelta > line.xDelta);
1697 
1698    /* Take cross product to determine outward step */
1699    if(line.steep != 0) {
1700       /* Point first vector up to get correct sign */
1701       if(loc0.Y < loc1.Y) {
1702          locBeg = &loc0;
1703          locEnd = &loc1;
1704       }
1705       else {
1706          locBeg = &loc1;
1707          locEnd = &loc0;
1708       }
1709       cp = (((locEnd->X - locBeg->X) * (locInside.Y - locEnd->Y)) -
1710             ((locEnd->Y - locBeg->Y) * (locInside.X - locEnd->X)));
1711 
1712       line.xOut = (cp > 0) ? +1 : -1;
1713       line.yOut = 0;
1714    }
1715    else {
1716       /* Point first vector left to get correct sign */
1717       if(loc0.X > loc1.X) {
1718          locBeg = &loc0;
1719          locEnd = &loc1;
1720       }
1721       else {
1722          locBeg = &loc1;
1723          locEnd = &loc0;
1724       }
1725       cp = (((locEnd->X - locBeg->X) * (locInside.Y - locEnd->Y)) -
1726             ((locEnd->Y - locBeg->Y) * (locInside.X - locEnd->X)));
1727 
1728       line.xOut = 0;
1729       line.yOut = (cp > 0) ? +1 : -1;
1730    }
1731 
1732    /* Values that change while stepping through line */
1733    line.loc = loc0;
1734    line.travel = 0;
1735    line.outward = 0;
1736    line.error = (line.steep) ? line.yDelta/2 : line.xDelta/2;
1737 
1738 /* CALLBACK_POINT_PLOT(loc0, 3, 1, 1);
1739    CALLBACK_POINT_PLOT(loc1, 3, 1, 1); */
1740 
1741    return line;
1742 }
1743 
1744 /**
1745  *
1746  *
1747  */
1748 static DmtxPassFail
BresLineGetStep(DmtxBresLine line,DmtxPixelLoc target,int * travel,int * outward)1749 BresLineGetStep(DmtxBresLine line, DmtxPixelLoc target, int *travel, int *outward)
1750 {
1751    /* Determine necessary step along and outward from Bresenham line */
1752    if(line.steep != 0) {
1753       *travel = (line.yStep > 0) ? target.Y - line.loc.Y : line.loc.Y - target.Y;
1754       BresLineStep(&line, *travel, 0);
1755       *outward = (line.xOut > 0) ? target.X - line.loc.X : line.loc.X - target.X;
1756       assert(line.yOut == 0);
1757    }
1758    else {
1759       *travel = (line.xStep > 0) ? target.X - line.loc.X : line.loc.X - target.X;
1760       BresLineStep(&line, *travel, 0);
1761       *outward = (line.yOut > 0) ? target.Y - line.loc.Y : line.loc.Y - target.Y;
1762       assert(line.xOut == 0);
1763    }
1764 
1765    return DmtxPass;
1766 }
1767 
1768 /**
1769  *
1770  *
1771  */
1772 static DmtxPassFail
BresLineStep(DmtxBresLine * line,int travel,int outward)1773 BresLineStep(DmtxBresLine *line, int travel, int outward)
1774 {
1775    int i;
1776    DmtxBresLine lineNew;
1777 
1778    lineNew = *line;
1779 
1780    assert(abs(travel) < 2);
1781    assert(abs(outward) >= 0);
1782 
1783    /* Perform forward step */
1784    if(travel > 0) {
1785       lineNew.travel++;
1786       if(lineNew.steep != 0) {
1787          lineNew.loc.Y += lineNew.yStep;
1788          lineNew.error -= lineNew.xDelta;
1789          if(lineNew.error < 0) {
1790             lineNew.loc.X += lineNew.xStep;
1791             lineNew.error += lineNew.yDelta;
1792          }
1793       }
1794       else {
1795          lineNew.loc.X += lineNew.xStep;
1796          lineNew.error -= lineNew.yDelta;
1797          if(lineNew.error < 0) {
1798             lineNew.loc.Y += lineNew.yStep;
1799             lineNew.error += lineNew.xDelta;
1800          }
1801       }
1802    }
1803    else if(travel < 0) {
1804       lineNew.travel--;
1805       if(lineNew.steep != 0) {
1806          lineNew.loc.Y -= lineNew.yStep;
1807          lineNew.error += lineNew.xDelta;
1808          if(lineNew.error >= lineNew.yDelta) {
1809             lineNew.loc.X -= lineNew.xStep;
1810             lineNew.error -= lineNew.yDelta;
1811          }
1812       }
1813       else {
1814          lineNew.loc.X -= lineNew.xStep;
1815          lineNew.error += lineNew.yDelta;
1816          if(lineNew.error >= lineNew.xDelta) {
1817             lineNew.loc.Y -= lineNew.yStep;
1818             lineNew.error -= lineNew.xDelta;
1819          }
1820       }
1821    }
1822 
1823    for(i = 0; i < outward; i++) {
1824       /* Outward steps */
1825       lineNew.outward++;
1826       lineNew.loc.X += lineNew.xOut;
1827       lineNew.loc.Y += lineNew.yOut;
1828    }
1829 
1830    *line = lineNew;
1831 
1832    return DmtxPass;
1833 }
1834 
1835 /**
1836  *
1837  *
1838  */
1839 #ifdef NOTDEFINED
1840 static void
WriteDiagnosticImage(DmtxDecode * dec,DmtxRegion * reg,char * imagePath)1841 WriteDiagnosticImage(DmtxDecode *dec, DmtxRegion *reg, char *imagePath)
1842 {
1843    int row, col;
1844    int width, height;
1845    unsigned char *cache;
1846    int rgb[3];
1847    FILE *fp;
1848    DmtxVector2 p;
1849    DmtxImage *img;
1850 
1851    assert(reg != NULL);
1852 
1853    fp = fopen(imagePath, "wb");
1854    if(fp == NULL) {
1855       exit(3);
1856    }
1857 
1858    width = dmtxDecodeGetProp(dec, DmtxPropWidth);
1859    height = dmtxDecodeGetProp(dec->image, DmtxPropHeight);
1860 
1861    img = dmtxImageCreate(NULL, width, height, DmtxPack24bppRGB);
1862 
1863    /* Populate image */
1864    for(row = 0; row < height; row++) {
1865       for(col = 0; col < width; col++) {
1866 
1867          cache = dmtxDecodeGetCache(dec, col, row);
1868          if(cache == NULL) {
1869             rgb[0] = 0;
1870             rgb[1] = 0;
1871             rgb[2] = 128;
1872          }
1873          else {
1874             dmtxDecodeGetPixelValue(dec, col, row, 0, &rgb[0]);
1875             dmtxDecodeGetPixelValue(dec, col, row, 1, &rgb[1]);
1876             dmtxDecodeGetPixelValue(dec, col, row, 2, &rgb[2]);
1877 
1878             p.X = col;
1879             p.Y = row;
1880             dmtxMatrix3VMultiplyBy(&p, reg->raw2fit);
1881 
1882             if(p.X < 0.0 || p.X > 1.0 || p.Y < 0.0 || p.Y > 1.0) {
1883                rgb[0] = 0;
1884                rgb[1] = 0;
1885                rgb[2] = 128;
1886             }
1887             else if(p.X + p.Y > 1.0) {
1888                rgb[0] += (0.4 * (255 - rgb[0]));
1889                rgb[1] += (0.4 * (255 - rgb[1]));
1890                rgb[2] += (0.4 * (255 - rgb[2]));
1891             }
1892          }
1893 
1894          dmtxImageSetRgb(img, col, row, rgb);
1895       }
1896    }
1897 
1898    /* Write additional markers */
1899    rgb[0] = 255;
1900    rgb[1] = 0;
1901    rgb[2] = 0;
1902    dmtxImageSetRgb(img, reg->topLoc.X, reg->topLoc.Y, rgb);
1903    dmtxImageSetRgb(img, reg->rightLoc.X, reg->rightLoc.Y, rgb);
1904 
1905    /* Write image to PNM file */
1906    fprintf(fp, "P6\n%d %d\n255\n", width, height);
1907    for(row = height - 1; row >= 0; row--) {
1908       for(col = 0; col < width; col++) {
1909          dmtxImageGetRgb(img, col, row, rgb);
1910          fwrite(rgb, sizeof(char), 3, fp);
1911       }
1912    }
1913 
1914    dmtxImageDestroy(&img);
1915 
1916    fclose(fp);
1917 }
1918 #endif
1919