1 /*Copyright (C) 2008-2009 Timothy B. Terriberry (tterribe@xiph.org)
2 You can redistribute this library and/or modify it under the terms of the
3 GNU Lesser General Public License as published by the Free Software
4 Foundation; either version 2.1 of the License, or (at your option) any later
5 version.*/
6 #include <stdlib.h>
7 #include <limits.h>
8 #include <string.h>
9 #include <time.h>
10 #include "qrcode.h"
11 #include "qrdec.h"
12 #include "bch15_5.h"
13 #include "rs.h"
14 #include "isaac.h"
15 #include "util.h"
16 #include "binarize.h"
17 #include "error.h"
18 #include "svg.h"
19
20 typedef int qr_line[3];
21
22 typedef struct qr_finder_cluster qr_finder_cluster;
23 typedef struct qr_finder_edge_pt qr_finder_edge_pt;
24 typedef struct qr_finder_center qr_finder_center;
25
26 typedef struct qr_aff qr_aff;
27 typedef struct qr_hom qr_hom;
28
29 typedef struct qr_finder qr_finder;
30
31 typedef struct qr_hom_cell qr_hom_cell;
32 typedef struct qr_sampling_grid qr_sampling_grid;
33 typedef struct qr_pack_buf qr_pack_buf;
34
35 /*The number of bits in an int.
36 Note the cast to (int): this prevents this value from "promoting" whole
37 expressions to an (unsigned) size_t.*/
38 #define QR_INT_BITS ((int)sizeof(int)*CHAR_BIT)
39 #define QR_INT_LOGBITS (QR_ILOG(QR_INT_BITS))
40
41 /*A 14 bit resolution for a homography ensures that the ideal module size for a
42 version 40 code differs from that of a version 39 code by at least 2.*/
43 #define QR_HOM_BITS (14)
44
45 /*The number of bits of sub-module precision to use when searching for
46 alignment patterns.
47 Two bits allows an alignment pattern to be found even if the modules have
48 been eroded by up to 50% (due to blurring, etc.).
49 This must be at least one, since it affects the dynamic range of the
50 transforms, and we sample at half-module resolution to compute a bounding
51 quadrilateral for the code.*/
52 #define QR_ALIGN_SUBPREC (2)
53
54
55 /* collection of finder lines */
56 typedef struct qr_finder_lines {
57 qr_finder_line *lines;
58 int nlines, clines;
59 } qr_finder_lines;
60
61
62 struct qr_reader {
63 /*The GF(256) representation used in Reed-Solomon decoding.*/
64 rs_gf256 gf;
65 /*The random number generator used by RANSAC.*/
66 isaac_ctx isaac;
67 /* current finder state, horizontal and vertical lines */
68 qr_finder_lines finder_lines[2];
69 };
70
71
72 /*Initializes a client reader handle.*/
qr_reader_init(qr_reader * reader)73 static void qr_reader_init (qr_reader *reader)
74 {
75 /*time_t now;
76 now=time(NULL);
77 isaac_init(&_reader->isaac,&now,sizeof(now));*/
78 isaac_init(&reader->isaac, NULL, 0);
79 rs_gf256_init(&reader->gf, QR_PPOLY);
80 }
81
82 /*Allocates a client reader handle.*/
_zbar_qr_create(void)83 qr_reader *_zbar_qr_create (void)
84 {
85 qr_reader *reader = (qr_reader*)calloc(1, sizeof(*reader));
86 qr_reader_init(reader);
87 return(reader);
88 }
89
90 /*Frees a client reader handle.*/
_zbar_qr_destroy(qr_reader * reader)91 void _zbar_qr_destroy (qr_reader *reader)
92 {
93 zprintf(1, "max finder lines = %dx%d\n",
94 reader->finder_lines[0].clines,
95 reader->finder_lines[1].clines);
96 if(reader->finder_lines[0].lines)
97 free(reader->finder_lines[0].lines);
98 if(reader->finder_lines[1].lines)
99 free(reader->finder_lines[1].lines);
100 free(reader);
101 }
102
103 /* reset finder state between scans */
_zbar_qr_reset(qr_reader * reader)104 void _zbar_qr_reset (qr_reader *reader)
105 {
106 reader->finder_lines[0].nlines = 0;
107 reader->finder_lines[1].nlines = 0;
108 }
109
110
111 /*A cluster of lines crossing a finder pattern (all in the same direction).*/
112 struct qr_finder_cluster{
113 /*Pointers to the lines crossing the pattern.*/
114 qr_finder_line **lines;
115 /*The number of lines in the cluster.*/
116 int nlines;
117 };
118
119
120 /*A point on the edge of a finder pattern.
121 These are obtained from the endpoints of the lines crossing this particular
122 pattern.*/
123 struct qr_finder_edge_pt{
124 /*The location of the edge point.*/
125 qr_point pos;
126 /*A label classifying which edge this belongs to:
127 0: negative u edge (left)
128 1: positive u edge (right)
129 2: negative v edge (top)
130 3: positive v edge (bottom)*/
131 int edge;
132 /*The (signed) perpendicular distance of the edge point from a line parallel
133 to the edge passing through the finder center, in (u,v) coordinates.
134 This is also re-used by RANSAC to store inlier flags.*/
135 int extent;
136 };
137
138
139 /*The center of a finder pattern obtained from the crossing of one or more
140 clusters of horizontal finder lines with one or more clusters of vertical
141 finder lines.*/
142 struct qr_finder_center{
143 /*The estimated location of the finder center.*/
144 qr_point pos;
145 /*The list of edge points from the crossing lines.*/
146 qr_finder_edge_pt *edge_pts;
147 /*The number of edge points from the crossing lines.*/
148 int nedge_pts;
149 };
150
151
qr_finder_vline_cmp(const void * _a,const void * _b)152 static int qr_finder_vline_cmp(const void *_a,const void *_b){
153 const qr_finder_line *a;
154 const qr_finder_line *b;
155 a=(const qr_finder_line *)_a;
156 b=(const qr_finder_line *)_b;
157 return ((a->pos[0]>b->pos[0])-(a->pos[0]<b->pos[0])<<1)+
158 (a->pos[1]>b->pos[1])-(a->pos[1]<b->pos[1]);
159 }
160
161 /*Clusters adjacent lines into groups that are large enough to be crossing a
162 finder pattern (relative to their length).
163 _clusters: The buffer in which to store the clusters found.
164 _neighbors: The buffer used to store the lists of lines in each cluster.
165 _lines: The list of lines to cluster.
166 Horizontal lines must be sorted in ascending order by Y
167 coordinate, with ties broken by X coordinate.
168 Vertical lines must be sorted in ascending order by X coordinate,
169 with ties broken by Y coordinate.
170 _nlines: The number of lines in the set of lines to cluster.
171 _v: 0 for horizontal lines, or 1 for vertical lines.
172 Return: The number of clusters.*/
qr_finder_cluster_lines(qr_finder_cluster * _clusters,qr_finder_line ** _neighbors,qr_finder_line * _lines,int _nlines,int _v)173 static int qr_finder_cluster_lines(qr_finder_cluster *_clusters,
174 qr_finder_line **_neighbors,qr_finder_line *_lines,int _nlines,int _v){
175 unsigned char *mark;
176 qr_finder_line **neighbors;
177 int nneighbors;
178 int nclusters;
179 int i;
180 /*TODO: Kalman filters!*/
181 mark=(unsigned char *)calloc(_nlines,sizeof(*mark));
182 neighbors=_neighbors;
183 nclusters=0;
184 for(i=0;i<_nlines-1;i++)if(!mark[i]){
185 int len;
186 int j;
187 nneighbors=1;
188 neighbors[0]=_lines+i;
189 len=_lines[i].len;
190 for(j=i+1;j<_nlines;j++)if(!mark[j]){
191 const qr_finder_line *a;
192 const qr_finder_line *b;
193 int thresh;
194 a=neighbors[nneighbors-1];
195 b=_lines+j;
196 /*The clustering threshold is proportional to the size of the lines,
197 since minor noise in large areas can interrupt patterns more easily
198 at high resolutions.*/
199 thresh=a->len+7>>2;
200 if(abs(a->pos[1-_v]-b->pos[1-_v])>thresh)break;
201 if(abs(a->pos[_v]-b->pos[_v])>thresh)continue;
202 if(abs(a->pos[_v]+a->len-b->pos[_v]-b->len)>thresh)continue;
203 if(a->boffs>0&&b->boffs>0&&
204 abs(a->pos[_v]-a->boffs-b->pos[_v]+b->boffs)>thresh){
205 continue;
206 }
207 if(a->eoffs>0&&b->eoffs>0&&
208 abs(a->pos[_v]+a->len+a->eoffs-b->pos[_v]-b->len-b->eoffs)>thresh){
209 continue;
210 }
211 neighbors[nneighbors++]=_lines+j;
212 len+=b->len;
213 }
214 /*We require at least three lines to form a cluster, which eliminates a
215 large number of false positives, saving considerable decoding time.
216 This should still be sufficient for 1-pixel codes with no noise.*/
217 if(nneighbors<3)continue;
218 /*The expected number of lines crossing a finder pattern is equal to their
219 average length.
220 We accept the cluster if size is at least 1/3 their average length (this
221 is a very small threshold, but was needed for some test images).*/
222 len=((len<<1)+nneighbors)/(nneighbors<<1);
223 if(nneighbors*(5<<QR_FINDER_SUBPREC)>=len){
224 _clusters[nclusters].lines=neighbors;
225 _clusters[nclusters].nlines=nneighbors;
226 for(j=0;j<nneighbors;j++)mark[neighbors[j]-_lines]=1;
227 neighbors+=nneighbors;
228 nclusters++;
229 }
230 }
231 free(mark);
232 return nclusters;
233 }
234
235 /*Adds the coordinates of the edge points from the lines contained in the
236 given list of clusters to the list of edge points for a finder center.
237 Only the edge point position is initialized.
238 The edge label and extent are set by qr_finder_edge_pts_aff_classify()
239 or qr_finder_edge_pts_hom_classify().
240 _edge_pts: The buffer in which to store the edge points.
241 _nedge_pts: The current number of edge points in the buffer.
242 _neighbors: The list of lines in the cluster.
243 _nneighbors: The number of lines in the list of lines in the cluster.
244 _v: 0 for horizontal lines and 1 for vertical lines.
245 Return: The new total number of edge points.*/
qr_finder_edge_pts_fill(qr_finder_edge_pt * _edge_pts,int _nedge_pts,qr_finder_cluster ** _neighbors,int _nneighbors,int _v)246 static int qr_finder_edge_pts_fill(qr_finder_edge_pt *_edge_pts,int _nedge_pts,
247 qr_finder_cluster **_neighbors,int _nneighbors,int _v){
248 int i;
249 for(i=0;i<_nneighbors;i++){
250 qr_finder_cluster *c;
251 int j;
252 c=_neighbors[i];
253 for(j=0;j<c->nlines;j++){
254 qr_finder_line *l;
255 l=c->lines[j];
256 if(l->boffs>0){
257 _edge_pts[_nedge_pts].pos[0]=l->pos[0];
258 _edge_pts[_nedge_pts].pos[1]=l->pos[1];
259 _edge_pts[_nedge_pts].pos[_v]-=l->boffs;
260 _nedge_pts++;
261 }
262 if(l->eoffs>0){
263 _edge_pts[_nedge_pts].pos[0]=l->pos[0];
264 _edge_pts[_nedge_pts].pos[1]=l->pos[1];
265 _edge_pts[_nedge_pts].pos[_v]+=l->len+l->eoffs;
266 _nedge_pts++;
267 }
268 }
269 }
270 return _nedge_pts;
271 }
272
qr_finder_center_cmp(const void * _a,const void * _b)273 static int qr_finder_center_cmp(const void *_a,const void *_b){
274 const qr_finder_center *a;
275 const qr_finder_center *b;
276 a=(const qr_finder_center *)_a;
277 b=(const qr_finder_center *)_b;
278 return ((b->nedge_pts>a->nedge_pts)-(b->nedge_pts<a->nedge_pts)<<2)+
279 ((a->pos[1]>b->pos[1])-(a->pos[1]<b->pos[1])<<1)+
280 (a->pos[0]>b->pos[0])-(a->pos[0]<b->pos[0]);
281 }
282
283 /*Determine if a horizontal line crosses a vertical line.
284 _hline: The horizontal line.
285 _vline: The vertical line.
286 Return: A non-zero value if the lines cross, or zero if they do not.*/
qr_finder_lines_are_crossing(const qr_finder_line * _hline,const qr_finder_line * _vline)287 static int qr_finder_lines_are_crossing(const qr_finder_line *_hline,
288 const qr_finder_line *_vline){
289 return
290 _hline->pos[0]<=_vline->pos[0]&&_vline->pos[0]<_hline->pos[0]+_hline->len&&
291 _vline->pos[1]<=_hline->pos[1]&&_hline->pos[1]<_vline->pos[1]+_vline->len;
292 }
293
294 /*Finds horizontal clusters that cross corresponding vertical clusters,
295 presumably corresponding to a finder center.
296 _center: The buffer in which to store putative finder centers.
297 _edge_pts: The buffer to use for the edge point lists for each finder
298 center.
299 _hclusters: The clusters of horizontal lines crossing finder patterns.
300 _nhclusters: The number of horizontal line clusters.
301 _vclusters: The clusters of vertical lines crossing finder patterns.
302 _nvclusters: The number of vertical line clusters.
303 Return: The number of putative finder centers.*/
qr_finder_find_crossings(qr_finder_center * _centers,qr_finder_edge_pt * _edge_pts,qr_finder_cluster * _hclusters,int _nhclusters,qr_finder_cluster * _vclusters,int _nvclusters)304 static int qr_finder_find_crossings(qr_finder_center *_centers,
305 qr_finder_edge_pt *_edge_pts,qr_finder_cluster *_hclusters,int _nhclusters,
306 qr_finder_cluster *_vclusters,int _nvclusters){
307 qr_finder_cluster **hneighbors;
308 qr_finder_cluster **vneighbors;
309 unsigned char *hmark;
310 unsigned char *vmark;
311 int ncenters;
312 int i;
313 int j;
314 hneighbors=(qr_finder_cluster **)malloc(_nhclusters*sizeof(*hneighbors));
315 vneighbors=(qr_finder_cluster **)malloc(_nvclusters*sizeof(*vneighbors));
316 hmark=(unsigned char *)calloc(_nhclusters,sizeof(*hmark));
317 vmark=(unsigned char *)calloc(_nvclusters,sizeof(*vmark));
318 ncenters=0;
319 /*TODO: This may need some re-working.
320 We should be finding groups of clusters such that _all_ horizontal lines in
321 _all_ horizontal clusters in the group cross _all_ vertical lines in _all_
322 vertical clusters in the group.
323 This is equivalent to finding the maximum bipartite clique in the
324 connectivity graph, which requires linear progamming to solve efficiently.
325 In principle, that is easy to do, but a realistic implementation without
326 floating point is a lot of work (and computationally expensive).
327 Right now we are relying on a sufficient border around the finder patterns
328 to prevent false positives.*/
329 for(i=0;i<_nhclusters;i++)if(!hmark[i]){
330 qr_finder_line *a;
331 qr_finder_line *b;
332 int nvneighbors;
333 int nedge_pts;
334 int y;
335 a=_hclusters[i].lines[_hclusters[i].nlines>>1];
336 y=nvneighbors=0;
337 for(j=0;j<_nvclusters;j++)if(!vmark[j]){
338 b=_vclusters[j].lines[_vclusters[j].nlines>>1];
339 if(qr_finder_lines_are_crossing(a,b)){
340 vmark[j]=1;
341 y+=(b->pos[1]<<1)+b->len;
342 if(b->boffs>0&&b->eoffs>0)y+=b->eoffs-b->boffs;
343 vneighbors[nvneighbors++]=_vclusters+j;
344 }
345 }
346 if(nvneighbors>0){
347 qr_finder_center *c;
348 int nhneighbors;
349 int x;
350 x=(a->pos[0]<<1)+a->len;
351 if(a->boffs>0&&a->eoffs>0)x+=a->eoffs-a->boffs;
352 hneighbors[0]=_hclusters+i;
353 nhneighbors=1;
354 j=nvneighbors>>1;
355 b=vneighbors[j]->lines[vneighbors[j]->nlines>>1];
356 for(j=i+1;j<_nhclusters;j++)if(!hmark[j]){
357 a=_hclusters[j].lines[_hclusters[j].nlines>>1];
358 if(qr_finder_lines_are_crossing(a,b)){
359 hmark[j]=1;
360 x+=(a->pos[0]<<1)+a->len;
361 if(a->boffs>0&&a->eoffs>0)x+=a->eoffs-a->boffs;
362 hneighbors[nhneighbors++]=_hclusters+j;
363 }
364 }
365 c=_centers+ncenters++;
366 c->pos[0]=(x+nhneighbors)/(nhneighbors<<1);
367 c->pos[1]=(y+nvneighbors)/(nvneighbors<<1);
368 c->edge_pts=_edge_pts;
369 nedge_pts=qr_finder_edge_pts_fill(_edge_pts,0,
370 hneighbors,nhneighbors,0);
371 nedge_pts=qr_finder_edge_pts_fill(_edge_pts,nedge_pts,
372 vneighbors,nvneighbors,1);
373 c->nedge_pts=nedge_pts;
374 _edge_pts+=nedge_pts;
375 }
376 }
377 free(vmark);
378 free(hmark);
379 free(vneighbors);
380 free(hneighbors);
381 /*Sort the centers by decreasing numbers of edge points.*/
382 qsort(_centers,ncenters,sizeof(*_centers),qr_finder_center_cmp);
383 return ncenters;
384 }
385
386 /*Locates a set of putative finder centers in the image.
387 First we search for horizontal and vertical lines that have
388 (dark:light:dark:light:dark) runs with size ratios of roughly (1:1:3:1:1).
389 Then we cluster them into groups such that each subsequent pair of endpoints
390 is close to the line before it in the cluster.
391 This will locate many line clusters that don't cross a finder pattern, but
392 qr_finder_find_crossings() will filter most of them out.
393 Where horizontal and vertical clusters cross, a prospective finder center is
394 returned.
395 _centers: Returns a pointer to a freshly-allocated list of finder centers.
396 This must be freed by the caller.
397 _edge_pts: Returns a pointer to a freshly-allocated list of edge points
398 around those centers.
399 This must be freed by the caller.
400 _img: The binary image to search.
401 _width: The width of the image.
402 _height: The height of the image.
403 Return: The number of putative finder centers located.*/
qr_finder_centers_locate(qr_finder_center ** _centers,qr_finder_edge_pt ** _edge_pts,qr_reader * reader,int _width,int _height)404 static int qr_finder_centers_locate(qr_finder_center **_centers,
405 qr_finder_edge_pt **_edge_pts, qr_reader *reader,
406 int _width,int _height){
407 qr_finder_line *hlines = reader->finder_lines[0].lines;
408 int nhlines = reader->finder_lines[0].nlines;
409 qr_finder_line *vlines = reader->finder_lines[1].lines;
410 int nvlines = reader->finder_lines[1].nlines;
411
412 qr_finder_line **hneighbors;
413 qr_finder_cluster *hclusters;
414 int nhclusters;
415 qr_finder_line **vneighbors;
416 qr_finder_cluster *vclusters;
417 int nvclusters;
418 int ncenters;
419
420 /*Cluster the detected lines.*/
421 hneighbors=(qr_finder_line **)malloc(nhlines*sizeof(*hneighbors));
422 /*We require more than one line per cluster, so there are at most nhlines/2.*/
423 hclusters=(qr_finder_cluster *)malloc((nhlines>>1)*sizeof(*hclusters));
424 nhclusters=qr_finder_cluster_lines(hclusters,hneighbors,hlines,nhlines,0);
425 /*We need vertical lines to be sorted by X coordinate, with ties broken by Y
426 coordinate, for clustering purposes.
427 We scan the image in the opposite order for cache efficiency, so sort the
428 lines we found here.*/
429 qsort(vlines,nvlines,sizeof(*vlines),qr_finder_vline_cmp);
430 vneighbors=(qr_finder_line **)malloc(nvlines*sizeof(*vneighbors));
431 /*We require more than one line per cluster, so there are at most nvlines/2.*/
432 vclusters=(qr_finder_cluster *)malloc((nvlines>>1)*sizeof(*vclusters));
433 nvclusters=qr_finder_cluster_lines(vclusters,vneighbors,vlines,nvlines,1);
434 /*Find line crossings among the clusters.*/
435 if(nhclusters>=3&&nvclusters>=3){
436 qr_finder_edge_pt *edge_pts;
437 qr_finder_center *centers;
438 int nedge_pts;
439 int i;
440 nedge_pts=0;
441 for(i=0;i<nhclusters;i++)nedge_pts+=hclusters[i].nlines;
442 for(i=0;i<nvclusters;i++)nedge_pts+=vclusters[i].nlines;
443 nedge_pts<<=1;
444 edge_pts=(qr_finder_edge_pt *)malloc(nedge_pts*sizeof(*edge_pts));
445 centers=(qr_finder_center *)malloc(
446 QR_MINI(nhclusters,nvclusters)*sizeof(*centers));
447 ncenters=qr_finder_find_crossings(centers,edge_pts,
448 hclusters,nhclusters,vclusters,nvclusters);
449 *_centers=centers;
450 *_edge_pts=edge_pts;
451 }
452 else ncenters=0;
453 free(vclusters);
454 free(vneighbors);
455 free(hclusters);
456 free(hneighbors);
457 return ncenters;
458 }
459
460
461
qr_point_translate(qr_point _point,int _dx,int _dy)462 static void qr_point_translate(qr_point _point,int _dx,int _dy){
463 _point[0]+=_dx;
464 _point[1]+=_dy;
465 }
466
qr_point_distance2(const qr_point _p1,const qr_point _p2)467 static unsigned qr_point_distance2(const qr_point _p1,const qr_point _p2){
468 return (_p1[0]-_p2[0])*(_p1[0]-_p2[0])+(_p1[1]-_p2[1])*(_p1[1]-_p2[1]);
469 }
470
471 /*Returns the cross product of the three points, which is positive if they are
472 in CCW order (in a right-handed coordinate system), and 0 if they're
473 colinear.*/
qr_point_ccw(const qr_point _p0,const qr_point _p1,const qr_point _p2)474 static int qr_point_ccw(const qr_point _p0,
475 const qr_point _p1,const qr_point _p2){
476 return (_p1[0]-_p0[0])*(_p2[1]-_p0[1])-(_p1[1]-_p0[1])*(_p2[0]-_p0[0]);
477 }
478
479
480
481 /*Evaluates a line equation at a point.
482 _line: The line to evaluate.
483 _x: The X coordinate of the point.
484 _y: The y coordinate of the point.
485 Return: The value of the line equation _line[0]*_x+_line[1]*_y+_line[2].*/
qr_line_eval(qr_line _line,int _x,int _y)486 static int qr_line_eval(qr_line _line,int _x,int _y){
487 return _line[0]*_x+_line[1]*_y+_line[2];
488 }
489
490 /*Computes a line passing through the given point using the specified second
491 order statistics.
492 Given a line defined by the equation
493 A*x+B*y+C = 0 ,
494 the least squares fit to n points (x_i,y_i) must satisfy the two equations
495 A^2 + (Syy - Sxx)/Sxy*A*B - B^2 = 0 ,
496 C = -(xbar*A+ybar*B) ,
497 where
498 xbar = sum(x_i)/n ,
499 ybar = sum(y_i)/n ,
500 Sxx = sum((x_i-xbar)**2) ,
501 Sxy = sum((x_i-xbar)*(y_i-ybar)) ,
502 Syy = sum((y_i-ybar)**2) .
503 The quadratic can be solved for the ratio (A/B) or (B/A):
504 A/B = (Syy + sqrt((Sxx-Syy)**2 + 4*Sxy**2) - Sxx)/(-2*Sxy) ,
505 B/A = (Sxx + sqrt((Sxx-Syy)**2 + 4*Sxy**2) - Syy)/(-2*Sxy) .
506 We pick the one that leads to the larger ratio to avoid destructive
507 cancellation (and e.g., 0/0 for horizontal or vertical lines).
508 The above solutions correspond to the actual minimum.
509 The other solution of the quadratic corresponds to a saddle point of the
510 least squares objective function.
511 _l: Returns the fitted line values A, B, and C.
512 _x0: The X coordinate of the point the line is supposed to pass through.
513 _y0: The Y coordinate of the point the line is supposed to pass through.
514 _sxx: The sum Sxx.
515 _sxy: The sum Sxy.
516 _syy: The sum Syy.
517 _res: The maximum number of bits occupied by the product of any two of
518 _l[0] or _l[1].
519 Smaller numbers give less angular resolution, but allow more overhead
520 room for computations.*/
qr_line_fit(qr_line _l,int _x0,int _y0,int _sxx,int _sxy,int _syy,int _res)521 static void qr_line_fit(qr_line _l,int _x0,int _y0,
522 int _sxx,int _sxy,int _syy,int _res){
523 int dshift;
524 int dround;
525 int u;
526 int v;
527 int w;
528 u=abs(_sxx-_syy);
529 v=-_sxy<<1;
530 w=qr_ihypot(u,v);
531 /*Computations in later stages can easily overflow with moderate sizes, so we
532 compute a shift factor to scale things down into a managable range.
533 We ensure that the product of any two of _l[0] and _l[1] fits within _res
534 bits, which allows computation of line intersections without overflow.*/
535 dshift=QR_MAXI(0,QR_MAXI(qr_ilog(u),qr_ilog(abs(v)))+1-(_res+1>>1));
536 dround=(1<<dshift)>>1;
537 if(_sxx>_syy){
538 _l[0]=v+dround>>dshift;
539 _l[1]=u+w+dround>>dshift;
540 }
541 else{
542 _l[0]=u+w+dround>>dshift;
543 _l[1]=v+dround>>dshift;
544 }
545 _l[2]=-(_x0*_l[0]+_y0*_l[1]);
546 }
547
548 /*Perform a least-squares line fit to a list of points.
549 At least two points are required.*/
qr_line_fit_points(qr_line _l,qr_point * _p,int _np,int _res)550 static void qr_line_fit_points(qr_line _l,qr_point *_p,int _np,int _res){
551 int sx;
552 int sy;
553 int xmin;
554 int xmax;
555 int ymin;
556 int ymax;
557 int xbar;
558 int ybar;
559 int dx;
560 int dy;
561 int sxx;
562 int sxy;
563 int syy;
564 int sshift;
565 int sround;
566 int i;
567 sx=sy=0;
568 ymax=xmax=INT_MIN;
569 ymin=xmin=INT_MAX;
570 for(i=0;i<_np;i++){
571 sx+=_p[i][0];
572 xmin=QR_MINI(xmin,_p[i][0]);
573 xmax=QR_MAXI(xmax,_p[i][0]);
574 sy+=_p[i][1];
575 ymin=QR_MINI(ymin,_p[i][1]);
576 ymax=QR_MAXI(ymax,_p[i][1]);
577 }
578 xbar=(sx+(_np>>1))/_np;
579 ybar=(sy+(_np>>1))/_np;
580 sshift=QR_MAXI(0,qr_ilog(_np*QR_MAXI(QR_MAXI(xmax-xbar,xbar-xmin),
581 QR_MAXI(ymax-ybar,ybar-ymin)))-(QR_INT_BITS-1>>1));
582 sround=(1<<sshift)>>1;
583 sxx=sxy=syy=0;
584 for(i=0;i<_np;i++){
585 dx=_p[i][0]-xbar+sround>>sshift;
586 dy=_p[i][1]-ybar+sround>>sshift;
587 sxx+=dx*dx;
588 sxy+=dx*dy;
589 syy+=dy*dy;
590 }
591 qr_line_fit(_l,xbar,ybar,sxx,sxy,syy,_res);
592 }
593
qr_line_orient(qr_line _l,int _x,int _y)594 static void qr_line_orient(qr_line _l,int _x,int _y){
595 if(qr_line_eval(_l,_x,_y)<0){
596 _l[0]=-_l[0];
597 _l[1]=-_l[1];
598 _l[2]=-_l[2];
599 }
600 }
601
qr_line_isect(qr_point _p,const qr_line _l0,const qr_line _l1)602 static int qr_line_isect(qr_point _p,const qr_line _l0,const qr_line _l1){
603 int d;
604 int x;
605 int y;
606 d=_l0[0]*_l1[1]-_l0[1]*_l1[0];
607 if(d==0)return -1;
608 x=_l0[1]*_l1[2]-_l1[1]*_l0[2];
609 y=_l1[0]*_l0[2]-_l0[0]*_l1[2];
610 if(d<0){
611 x=-x;
612 y=-y;
613 d=-d;
614 }
615 _p[0]=QR_DIVROUND(x,d);
616 _p[1]=QR_DIVROUND(y,d);
617 return 0;
618 }
619
620
621
622 /*An affine homography.
623 This maps from the image (at subpel resolution) to a square domain with
624 power-of-two sides (of res bits) and back.*/
625 struct qr_aff{
626 int fwd[2][2];
627 int inv[2][2];
628 int x0;
629 int y0;
630 int res;
631 };
632
633
qr_aff_init(qr_aff * _aff,const qr_point _p0,const qr_point _p1,const qr_point _p2,int _res)634 static void qr_aff_init(qr_aff *_aff,
635 const qr_point _p0,const qr_point _p1,const qr_point _p2,int _res){
636 int det;
637 int dx1;
638 int dy1;
639 int dx2;
640 int dy2;
641 /*det is ensured to be positive by our caller.*/
642 det=qr_point_ccw(_p0,_p1,_p2);
643 dx1=_p1[0]-_p0[0];
644 dx2=_p2[0]-_p0[0];
645 dy1=_p1[1]-_p0[1];
646 dy2=_p2[1]-_p0[1];
647 _aff->fwd[0][0]=dx1;
648 _aff->fwd[0][1]=dx2;
649 _aff->fwd[1][0]=dy1;
650 _aff->fwd[1][1]=dy2;
651 _aff->inv[0][0]=QR_DIVROUND(dy2<<_res,det);
652 _aff->inv[0][1]=QR_DIVROUND(-dx2<<_res,det);
653 _aff->inv[1][0]=QR_DIVROUND(-dy1<<_res,det);
654 _aff->inv[1][1]=QR_DIVROUND(dx1<<_res,det);
655 _aff->x0=_p0[0];
656 _aff->y0=_p0[1];
657 _aff->res=_res;
658 }
659
660 /*Map from the image (at subpel resolution) into the square domain.*/
qr_aff_unproject(qr_point _q,const qr_aff * _aff,int _x,int _y)661 static void qr_aff_unproject(qr_point _q,const qr_aff *_aff,
662 int _x,int _y){
663 _q[0]=_aff->inv[0][0]*(_x-_aff->x0)+_aff->inv[0][1]*(_y-_aff->y0);
664 _q[1]=_aff->inv[1][0]*(_x-_aff->x0)+_aff->inv[1][1]*(_y-_aff->y0);
665 }
666
667 /*Map from the square domain into the image (at subpel resolution).*/
qr_aff_project(qr_point _p,const qr_aff * _aff,int _u,int _v)668 static void qr_aff_project(qr_point _p,const qr_aff *_aff,
669 int _u,int _v){
670 _p[0]=(_aff->fwd[0][0]*_u+_aff->fwd[0][1]*_v+(1<<_aff->res-1)>>_aff->res)
671 +_aff->x0;
672 _p[1]=(_aff->fwd[1][0]*_u+_aff->fwd[1][1]*_v+(1<<_aff->res-1)>>_aff->res)
673 +_aff->y0;
674 }
675
676
677
678 /*A full homography.
679 Like the affine homography, this maps from the image (at subpel resolution)
680 to a square domain with power-of-two sides (of res bits) and back.*/
681 struct qr_hom{
682 int fwd[3][2];
683 int inv[3][2];
684 int fwd22;
685 int inv22;
686 int x0;
687 int y0;
688 int res;
689 };
690
691
qr_hom_init(qr_hom * _hom,int _x0,int _y0,int _x1,int _y1,int _x2,int _y2,int _x3,int _y3,int _res)692 static void qr_hom_init(qr_hom *_hom,int _x0,int _y0,
693 int _x1,int _y1,int _x2,int _y2,int _x3,int _y3,int _res){
694 int dx10;
695 int dx20;
696 int dx30;
697 int dx31;
698 int dx32;
699 int dy10;
700 int dy20;
701 int dy30;
702 int dy31;
703 int dy32;
704 int a20;
705 int a21;
706 int a22;
707 int b0;
708 int b1;
709 int b2;
710 int s1;
711 int s2;
712 int r1;
713 int r2;
714 dx10=_x1-_x0;
715 dx20=_x2-_x0;
716 dx30=_x3-_x0;
717 dx31=_x3-_x1;
718 dx32=_x3-_x2;
719 dy10=_y1-_y0;
720 dy20=_y2-_y0;
721 dy30=_y3-_y0;
722 dy31=_y3-_y1;
723 dy32=_y3-_y2;
724 a20=dx32*dy10-dx10*dy32;
725 a21=dx20*dy31-dx31*dy20;
726 a22=dx32*dy31-dx31*dy32;
727 /*Figure out if we need to downscale anything.*/
728 b0=qr_ilog(QR_MAXI(abs(dx10),abs(dy10)))+qr_ilog(abs(a20+a22));
729 b1=qr_ilog(QR_MAXI(abs(dx20),abs(dy20)))+qr_ilog(abs(a21+a22));
730 b2=qr_ilog(QR_MAXI(QR_MAXI(abs(a20),abs(a21)),abs(a22)));
731 s1=QR_MAXI(0,_res+QR_MAXI(QR_MAXI(b0,b1),b2)-(QR_INT_BITS-2));
732 r1=(1<<s1)>>1;
733 /*Compute the final coefficients of the forward transform.
734 The 32x32->64 bit multiplies are really needed for accuracy with large
735 versions.*/
736 _hom->fwd[0][0]=QR_FIXMUL(dx10,a20+a22,r1,s1);
737 _hom->fwd[0][1]=QR_FIXMUL(dx20,a21+a22,r1,s1);
738 _hom->x0=_x0;
739 _hom->fwd[1][0]=QR_FIXMUL(dy10,a20+a22,r1,s1);
740 _hom->fwd[1][1]=QR_FIXMUL(dy20,a21+a22,r1,s1);
741 _hom->y0=_y0;
742 _hom->fwd[2][0]=a20+r1>>s1;
743 _hom->fwd[2][1]=a21+r1>>s1;
744 _hom->fwd22=s1>_res?a22+(r1>>_res)>>s1-_res:a22<<_res-s1;
745 /*Now compute the inverse transform.*/
746 b0=qr_ilog(QR_MAXI(QR_MAXI(abs(dx10),abs(dx20)),abs(dx30)))+
747 qr_ilog(QR_MAXI(abs(_hom->fwd[0][0]),abs(_hom->fwd[1][0])));
748 b1=qr_ilog(QR_MAXI(QR_MAXI(abs(dy10),abs(dy20)),abs(dy30)))+
749 qr_ilog(QR_MAXI(abs(_hom->fwd[0][1]),abs(_hom->fwd[1][1])));
750 b2=qr_ilog(abs(a22))-s1;
751 s2=QR_MAXI(0,QR_MAXI(b0,b1)+b2-(QR_INT_BITS-3));
752 r2=(1<<s2)>>1;
753 s1+=s2;
754 r1<<=s2;
755 /*The 32x32->64 bit multiplies are really needed for accuracy with large
756 versions.*/
757 _hom->inv[0][0]=QR_FIXMUL(_hom->fwd[1][1],a22,r1,s1);
758 _hom->inv[0][1]=QR_FIXMUL(-_hom->fwd[0][1],a22,r1,s1);
759 _hom->inv[1][0]=QR_FIXMUL(-_hom->fwd[1][0],a22,r1,s1);
760 _hom->inv[1][1]=QR_FIXMUL(_hom->fwd[0][0],a22,r1,s1);
761 _hom->inv[2][0]=QR_FIXMUL(_hom->fwd[1][0],_hom->fwd[2][1],
762 -QR_EXTMUL(_hom->fwd[1][1],_hom->fwd[2][0],r2),s2);
763 _hom->inv[2][1]=QR_FIXMUL(_hom->fwd[0][1],_hom->fwd[2][0],
764 -QR_EXTMUL(_hom->fwd[0][0],_hom->fwd[2][1],r2),s2);
765 _hom->inv22=QR_FIXMUL(_hom->fwd[0][0],_hom->fwd[1][1],
766 -QR_EXTMUL(_hom->fwd[0][1],_hom->fwd[1][0],r2),s2);
767 _hom->res=_res;
768 }
769
770
771 /*Map from the image (at subpel resolution) into the square domain.
772 Returns a negative value if the point went to infinity.*/
qr_hom_unproject(qr_point _q,const qr_hom * _hom,int _x,int _y)773 static int qr_hom_unproject(qr_point _q,const qr_hom *_hom,int _x,int _y){
774 int x;
775 int y;
776 int w;
777 _x-=_hom->x0;
778 _y-=_hom->y0;
779 x=_hom->inv[0][0]*_x+_hom->inv[0][1]*_y;
780 y=_hom->inv[1][0]*_x+_hom->inv[1][1]*_y;
781 w=_hom->inv[2][0]*_x+_hom->inv[2][1]*_y
782 +_hom->inv22+(1<<_hom->res-1)>>_hom->res;
783 if(w==0){
784 _q[0]=x<0?INT_MIN:INT_MAX;
785 _q[1]=y<0?INT_MIN:INT_MAX;
786 return -1;
787 }
788 else{
789 if(w<0){
790 x=-x;
791 y=-y;
792 w=-w;
793 }
794 _q[0]=QR_DIVROUND(x,w);
795 _q[1]=QR_DIVROUND(y,w);
796 }
797 return 0;
798 }
799
800 /*Finish a partial projection, converting from homogeneous coordinates to the
801 normal 2-D representation.
802 In loops, we can avoid many multiplies by computing the homogeneous _x, _y,
803 and _w incrementally, but we cannot avoid the divisions, done here.*/
qr_hom_fproject(qr_point _p,const qr_hom * _hom,int _x,int _y,int _w)804 static void qr_hom_fproject(qr_point _p,const qr_hom *_hom,
805 int _x,int _y,int _w){
806 if(_w==0){
807 _p[0]=_x<0?INT_MIN:INT_MAX;
808 _p[1]=_y<0?INT_MIN:INT_MAX;
809 }
810 else{
811 if(_w<0){
812 _x=-_x;
813 _y=-_y;
814 _w=-_w;
815 }
816 _p[0]=QR_DIVROUND(_x,_w)+_hom->x0;
817 _p[1]=QR_DIVROUND(_y,_w)+_hom->y0;
818 }
819 }
820
821 #if defined(QR_DEBUG)
822 /*Map from the square domain into the image (at subpel resolution).
823 Currently only used directly by debug code.*/
qr_hom_project(qr_point _p,const qr_hom * _hom,int _u,int _v)824 static void qr_hom_project(qr_point _p,const qr_hom *_hom,
825 int _u,int _v){
826 qr_hom_fproject(_p,_hom,
827 _hom->fwd[0][0]*_u+_hom->fwd[0][1]*_v,
828 _hom->fwd[1][0]*_u+_hom->fwd[1][1]*_v,
829 _hom->fwd[2][0]*_u+_hom->fwd[2][1]*_v+_hom->fwd22);
830 }
831 #endif
832
833
834
835 /*All the information we've collected about a finder pattern in the current
836 configuration.*/
837 struct qr_finder{
838 /*The module size along each axis (in the square domain).*/
839 int size[2];
840 /*The version estimated from the module size along each axis.*/
841 int eversion[2];
842 /*The list of classified edge points for each edge.*/
843 qr_finder_edge_pt *edge_pts[4];
844 /*The number of edge points classified as belonging to each edge.*/
845 int nedge_pts[4];
846 /*The number of inliers found after running RANSAC on each edge.*/
847 int ninliers[4];
848 /*The center of the finder pattern (in the square domain).*/
849 qr_point o;
850 /*The finder center information from the original image.*/
851 qr_finder_center *c;
852 };
853
854
qr_cmp_edge_pt(const void * _a,const void * _b)855 static int qr_cmp_edge_pt(const void *_a,const void *_b){
856 const qr_finder_edge_pt *a;
857 const qr_finder_edge_pt *b;
858 a=(const qr_finder_edge_pt *)_a;
859 b=(const qr_finder_edge_pt *)_b;
860 return ((a->edge>b->edge)-(a->edge<b->edge)<<1)+
861 (a->extent>b->extent)-(a->extent<b->extent);
862 }
863
864 /*Computes the index of the edge each edge point belongs to, and its (signed)
865 distance along the corresponding axis from the center of the finder pattern
866 (in the square domain).
867 The resulting list of edge points is sorted by edge index, with ties broken
868 by extent.*/
qr_finder_edge_pts_aff_classify(qr_finder * _f,const qr_aff * _aff)869 static void qr_finder_edge_pts_aff_classify(qr_finder *_f,const qr_aff *_aff){
870 qr_finder_center *c;
871 int i;
872 int e;
873 c=_f->c;
874 for(e=0;e<4;e++)_f->nedge_pts[e]=0;
875 for(i=0;i<c->nedge_pts;i++){
876 qr_point q;
877 int d;
878 qr_aff_unproject(q,_aff,c->edge_pts[i].pos[0],c->edge_pts[i].pos[1]);
879 qr_point_translate(q,-_f->o[0],-_f->o[1]);
880 d=abs(q[1])>abs(q[0]);
881 e=d<<1|(q[d]>=0);
882 _f->nedge_pts[e]++;
883 c->edge_pts[i].edge=e;
884 c->edge_pts[i].extent=q[d];
885 }
886 qsort(c->edge_pts,c->nedge_pts,sizeof(*c->edge_pts),qr_cmp_edge_pt);
887 _f->edge_pts[0]=c->edge_pts;
888 for(e=1;e<4;e++)_f->edge_pts[e]=_f->edge_pts[e-1]+_f->nedge_pts[e-1];
889 }
890
891 /*Computes the index of the edge each edge point belongs to, and its (signed)
892 distance along the corresponding axis from the center of the finder pattern
893 (in the square domain).
894 The resulting list of edge points is sorted by edge index, with ties broken
895 by extent.*/
qr_finder_edge_pts_hom_classify(qr_finder * _f,const qr_hom * _hom)896 static void qr_finder_edge_pts_hom_classify(qr_finder *_f,const qr_hom *_hom){
897 qr_finder_center *c;
898 int i;
899 int e;
900 c=_f->c;
901 for(e=0;e<4;e++)_f->nedge_pts[e]=0;
902 for(i=0;i<c->nedge_pts;i++){
903 qr_point q;
904 int d;
905 if(qr_hom_unproject(q,_hom,
906 c->edge_pts[i].pos[0],c->edge_pts[i].pos[1])>=0){
907 qr_point_translate(q,-_f->o[0],-_f->o[1]);
908 d=abs(q[1])>abs(q[0]);
909 e=d<<1|(q[d]>=0);
910 _f->nedge_pts[e]++;
911 c->edge_pts[i].edge=e;
912 c->edge_pts[i].extent=q[d];
913 }
914 else{
915 c->edge_pts[i].edge=4;
916 c->edge_pts[i].extent=q[0];
917 }
918 }
919 qsort(c->edge_pts,c->nedge_pts,sizeof(*c->edge_pts),qr_cmp_edge_pt);
920 _f->edge_pts[0]=c->edge_pts;
921 for(e=1;e<4;e++)_f->edge_pts[e]=_f->edge_pts[e-1]+_f->nedge_pts[e-1];
922 }
923
924 /*TODO: Perhaps these thresholds should be on the module size instead?
925 Unfortunately, I'd need real-world images of codes with larger versions to
926 see if these thresholds are still effective, but such versions aren't used
927 often.*/
928
929 /*The amount that the estimated version numbers are allowed to differ from the
930 real version number and still be considered valid.*/
931 #define QR_SMALL_VERSION_SLACK (1)
932 /*Since cell phone cameras can have severe radial distortion, the estimated
933 version for larger versions can be off by larger amounts.*/
934 #define QR_LARGE_VERSION_SLACK (3)
935
936 /*Estimates the size of a module after classifying the edge points.
937 _width: The distance between UL and UR in the square domain.
938 _height: The distance between UL and DL in the square domain.*/
qr_finder_estimate_module_size_and_version(qr_finder * _f,int _width,int _height)939 static int qr_finder_estimate_module_size_and_version(qr_finder *_f,
940 int _width,int _height){
941 qr_point offs;
942 int sums[4];
943 int nsums[4];
944 int usize;
945 int nusize;
946 int vsize;
947 int nvsize;
948 int uversion;
949 int vversion;
950 int e;
951 offs[0]=offs[1]=0;
952 for(e=0;e<4;e++)if(_f->nedge_pts[e]>0){
953 qr_finder_edge_pt *edge_pts;
954 int sum;
955 int mean;
956 int n;
957 int i;
958 /*Average the samples for this edge, dropping the top and bottom 25%.*/
959 edge_pts=_f->edge_pts[e];
960 n=_f->nedge_pts[e];
961 sum=0;
962 for(i=(n>>2);i<n-(n>>2);i++)sum+=edge_pts[i].extent;
963 n=n-((n>>2)<<1);
964 mean=QR_DIVROUND(sum,n);
965 offs[e>>1]+=mean;
966 sums[e]=sum;
967 nsums[e]=n;
968 }
969 else nsums[e]=sums[e]=0;
970 /*If we have samples on both sides of an axis, refine our idea of where the
971 unprojected finder center is located.*/
972 if(_f->nedge_pts[0]>0&&_f->nedge_pts[1]>0){
973 _f->o[0]-=offs[0]>>1;
974 sums[0]-=offs[0]*nsums[0]>>1;
975 sums[1]-=offs[0]*nsums[1]>>1;
976 }
977 if(_f->nedge_pts[2]>0&&_f->nedge_pts[3]>0){
978 _f->o[1]-=offs[1]>>1;
979 sums[2]-=offs[1]*nsums[2]>>1;
980 sums[3]-=offs[1]*nsums[3]>>1;
981 }
982 /*We must have _some_ samples along each axis... if we don't, our transform
983 must be pretty severely distorting the original square (e.g., with
984 coordinates so large as to cause overflow).*/
985 nusize=nsums[0]+nsums[1];
986 if(nusize<=0)return -1;
987 /*The module size is 1/3 the average edge extent.*/
988 nusize*=3;
989 usize=sums[1]-sums[0];
990 usize=((usize<<1)+nusize)/(nusize<<1);
991 if(usize<=0)return -1;
992 /*Now estimate the version directly from the module size and the distance
993 between the finder patterns.
994 This is done independently using the extents along each axis.
995 If either falls significantly outside the valid range (1 to 40), reject the
996 configuration.*/
997 uversion=(_width-8*usize)/(usize<<2);
998 if(uversion<1||uversion>40+QR_LARGE_VERSION_SLACK)return -1;
999 /*Now do the same for the other axis.*/
1000 nvsize=nsums[2]+nsums[3];
1001 if(nvsize<=0)return -1;
1002 nvsize*=3;
1003 vsize=sums[3]-sums[2];
1004 vsize=((vsize<<1)+nvsize)/(nvsize<<1);
1005 if(vsize<=0)return -1;
1006 vversion=(_height-8*vsize)/(vsize<<2);
1007 if(vversion<1||vversion>40+QR_LARGE_VERSION_SLACK)return -1;
1008 /*If the estimated version using extents along one axis is significantly
1009 different than the estimated version along the other axis, then the axes
1010 have significantly different scalings (relative to the grid).
1011 This can happen, e.g., when we have multiple adjacent QR codes, and we've
1012 picked two finder patterns from one and the third finder pattern from
1013 another, e.g.:
1014 X---DL UL---X
1015 |.... |....
1016 X.... UR....
1017 Such a configuration might even pass any other geometric checks if we
1018 didn't reject it here.*/
1019 if(abs(uversion-vversion)>QR_LARGE_VERSION_SLACK)return -1;
1020 _f->size[0]=usize;
1021 _f->size[1]=vsize;
1022 /*We intentionally do not compute an average version from the sizes along
1023 both axes.
1024 In the presence of projective distortion, one of them will be much more
1025 accurate than the other.*/
1026 _f->eversion[0]=uversion;
1027 _f->eversion[1]=vversion;
1028 return 0;
1029 }
1030
1031 /*Eliminate outliers from the classified edge points with RANSAC.*/
qr_finder_ransac(qr_finder * _f,const qr_aff * _hom,isaac_ctx * _isaac,int _e)1032 static void qr_finder_ransac(qr_finder *_f,const qr_aff *_hom,
1033 isaac_ctx *_isaac,int _e){
1034 qr_finder_edge_pt *edge_pts;
1035 int best_ninliers;
1036 int n;
1037 edge_pts=_f->edge_pts[_e];
1038 n=_f->nedge_pts[_e];
1039 best_ninliers=0;
1040 if(n>1){
1041 int max_iters;
1042 int i;
1043 int j;
1044 /*17 iterations is enough to guarantee an outlier-free sample with more
1045 than 99% probability given as many as 50% outliers.*/
1046 max_iters=17;
1047 for(i=0;i<max_iters;i++){
1048 qr_point q0;
1049 qr_point q1;
1050 int ninliers;
1051 int thresh;
1052 int p0i;
1053 int p1i;
1054 int *p0;
1055 int *p1;
1056 int j;
1057 /*Pick two random points on this edge.*/
1058 p0i=isaac_next_uint(_isaac,n);
1059 p1i=isaac_next_uint(_isaac,n-1);
1060 if(p1i>=p0i)p1i++;
1061 p0=edge_pts[p0i].pos;
1062 p1=edge_pts[p1i].pos;
1063 /*If the corresponding line is not within 45 degrees of the proper
1064 orientation in the square domain, reject it outright.
1065 This can happen, e.g., when highly skewed orientations cause points to
1066 be misclassified into the wrong edge.
1067 The irony is that using such points might produce a line which _does_
1068 pass the corresponding validity checks.*/
1069 qr_aff_unproject(q0,_hom,p0[0],p0[1]);
1070 qr_aff_unproject(q1,_hom,p1[0],p1[1]);
1071 qr_point_translate(q0,-_f->o[0],-_f->o[1]);
1072 qr_point_translate(q1,-_f->o[0],-_f->o[1]);
1073 if(abs(q0[_e>>1]-q1[_e>>1])>abs(q0[1-(_e>>1)]-q1[1-(_e>>1)]))continue;
1074 /*Identify the other edge points which are inliers.
1075 The squared distance should be distributed as a \Chi^2 distribution
1076 with one degree of freedom, which means for a 95% confidence the
1077 point should lie within a factor 3.8414588 ~= 4 times the expected
1078 variance of the point locations.
1079 We grossly approximate the standard deviation as 1 pixel in one
1080 direction, and 0.5 pixels in the other (because we average two
1081 coordinates).*/
1082 thresh=qr_isqrt(qr_point_distance2(p0,p1)<<2*QR_FINDER_SUBPREC+1);
1083 ninliers=0;
1084 for(j=0;j<n;j++){
1085 if(abs(qr_point_ccw(p0,p1,edge_pts[j].pos))<=thresh){
1086 edge_pts[j].extent|=1;
1087 ninliers++;
1088 }
1089 else edge_pts[j].extent&=~1;
1090 }
1091 if(ninliers>best_ninliers){
1092 for(j=0;j<n;j++)edge_pts[j].extent<<=1;
1093 best_ninliers=ninliers;
1094 /*The actual number of iterations required is
1095 log(1-\alpha)/log(1-r*r),
1096 where \alpha is the required probability of taking a sample with
1097 no outliers (e.g., 0.99) and r is the estimated ratio of inliers
1098 (e.g. ninliers/n).
1099 This is just a rough (but conservative) approximation, but it
1100 should be good enough to stop the iteration early when we find
1101 a good set of inliers.*/
1102 if(ninliers>n>>1)max_iters=(67*n-63*ninliers-1)/(n<<1);
1103 }
1104 }
1105 /*Now collect all the inliers at the beginning of the list.*/
1106 for(i=j=0;j<best_ninliers;i++)if(edge_pts[i].extent&2){
1107 if(j<i){
1108 qr_finder_edge_pt tmp;
1109 *&tmp=*(edge_pts+i);
1110 *(edge_pts+j)=*(edge_pts+i);
1111 *(edge_pts+i)=*&tmp;
1112 }
1113 j++;
1114 }
1115 }
1116 _f->ninliers[_e]=best_ninliers;
1117 }
1118
1119 /*Perform a least-squares line fit to an edge of a finder pattern using the
1120 inliers found by RANSAC.*/
qr_line_fit_finder_edge(qr_line _l,const qr_finder * _f,int _e,int _res)1121 static int qr_line_fit_finder_edge(qr_line _l,
1122 const qr_finder *_f,int _e,int _res){
1123 qr_finder_edge_pt *edge_pts;
1124 qr_point *pts;
1125 int npts;
1126 int i;
1127 npts=_f->ninliers[_e];
1128 if(npts<2)return -1;
1129 /*We could write a custom version of qr_line_fit_points that accesses
1130 edge_pts directly, but this saves on code size and doesn't measurably slow
1131 things down.*/
1132 pts=(qr_point *)malloc(npts*sizeof(*pts));
1133 edge_pts=_f->edge_pts[_e];
1134 for(i=0;i<npts;i++){
1135 pts[i][0]=edge_pts[i].pos[0];
1136 pts[i][1]=edge_pts[i].pos[1];
1137 }
1138 qr_line_fit_points(_l,pts,npts,_res);
1139 /*Make sure the center of the finder pattern lies in the positive halfspace
1140 of the line.*/
1141 qr_line_orient(_l,_f->c->pos[0],_f->c->pos[1]);
1142 free(pts);
1143 return 0;
1144 }
1145
1146 /*Perform a least-squares line fit to a pair of common finder edges using the
1147 inliers found by RANSAC.
1148 Unlike a normal edge fit, we guarantee that this one succeeds by creating at
1149 least one point on each edge using the estimated module size if it has no
1150 inliers.*/
qr_line_fit_finder_pair(qr_line _l,const qr_aff * _aff,const qr_finder * _f0,const qr_finder * _f1,int _e)1151 static void qr_line_fit_finder_pair(qr_line _l,const qr_aff *_aff,
1152 const qr_finder *_f0,const qr_finder *_f1,int _e){
1153 qr_point *pts;
1154 int npts;
1155 qr_finder_edge_pt *edge_pts;
1156 qr_point q;
1157 int n0;
1158 int n1;
1159 int i;
1160 n0=_f0->ninliers[_e];
1161 n1=_f1->ninliers[_e];
1162 /*We could write a custom version of qr_line_fit_points that accesses
1163 edge_pts directly, but this saves on code size and doesn't measurably slow
1164 things down.*/
1165 npts=QR_MAXI(n0,1)+QR_MAXI(n1,1);
1166 pts=(qr_point *)malloc(npts*sizeof(*pts));
1167 if(n0>0){
1168 edge_pts=_f0->edge_pts[_e];
1169 for(i=0;i<n0;i++){
1170 pts[i][0]=edge_pts[i].pos[0];
1171 pts[i][1]=edge_pts[i].pos[1];
1172 }
1173 }
1174 else{
1175 q[0]=_f0->o[0];
1176 q[1]=_f0->o[1];
1177 q[_e>>1]+=_f0->size[_e>>1]*(2*(_e&1)-1);
1178 qr_aff_project(pts[0],_aff,q[0],q[1]);
1179 n0++;
1180 }
1181 if(n1>0){
1182 edge_pts=_f1->edge_pts[_e];
1183 for(i=0;i<n1;i++){
1184 pts[n0+i][0]=edge_pts[i].pos[0];
1185 pts[n0+i][1]=edge_pts[i].pos[1];
1186 }
1187 }
1188 else{
1189 q[0]=_f1->o[0];
1190 q[1]=_f1->o[1];
1191 q[_e>>1]+=_f1->size[_e>>1]*(2*(_e&1)-1);
1192 qr_aff_project(pts[n0],_aff,q[0],q[1]);
1193 n1++;
1194 }
1195 qr_line_fit_points(_l,pts,npts,_aff->res);
1196 /*Make sure at least one finder center lies in the positive halfspace.*/
1197 qr_line_orient(_l,_f0->c->pos[0],_f0->c->pos[1]);
1198 free(pts);
1199 }
1200
qr_finder_quick_crossing_check(const unsigned char * _img,int _width,int _height,int _x0,int _y0,int _x1,int _y1,int _v)1201 static int qr_finder_quick_crossing_check(const unsigned char *_img,
1202 int _width,int _height,int _x0,int _y0,int _x1,int _y1,int _v){
1203 /*The points must be inside the image, and have a !_v:_v:!_v pattern.
1204 We don't scan the whole line initially, but quickly reject if the endpoints
1205 aren't !_v, or the midpoint isn't _v.
1206 If either end point is out of the image, or we don't encounter a _v pixel,
1207 we return a negative value, indicating the region should be considered
1208 empty.
1209 Otherwise, we return a positive value to indicate it is non-empty.*/
1210 if(_x0<0||_x0>=_width||_y0<0||_y0>=_height||
1211 _x1<0||_x1>=_width||_y1<0||_y1>=_height){
1212 return -1;
1213 }
1214 if(!_img[_y0*_width+_x0]!=_v||!_img[_y1*_width+_x1]!=_v)return 1;
1215 if(!_img[(_y0+_y1>>1)*_width+(_x0+_x1>>1)]==_v)return -1;
1216 return 0;
1217 }
1218
1219 /*Locate the midpoint of a _v segment along a !_v:_v:!_v line from (_x0,_y0) to
1220 (_x1,_y1).
1221 All coordinates, which are NOT in subpel resolution, must lie inside the
1222 image, and the endpoints are already assumed to have the value !_v.
1223 The returned value is in subpel resolution.*/
qr_finder_locate_crossing(const unsigned char * _img,int _width,int _height,int _x0,int _y0,int _x1,int _y1,int _v,qr_point _p)1224 static int qr_finder_locate_crossing(const unsigned char *_img,
1225 int _width,int _height,int _x0,int _y0,int _x1,int _y1,int _v,qr_point _p){
1226 qr_point x0;
1227 qr_point x1;
1228 qr_point dx;
1229 int step[2];
1230 int steep;
1231 int err;
1232 int derr;
1233 /*Use Bresenham's algorithm to trace along the line and find the exact
1234 transitions from !_v to _v and back.*/
1235 x0[0]=_x0;
1236 x0[1]=_y0;
1237 x1[0]=_x1;
1238 x1[1]=_y1;
1239 dx[0]=abs(_x1-_x0);
1240 dx[1]=abs(_y1-_y0);
1241 steep=dx[1]>dx[0];
1242 err=0;
1243 derr=dx[1-steep];
1244 step[0]=((_x0<_x1)<<1)-1;
1245 step[1]=((_y0<_y1)<<1)-1;
1246 /*Find the first crossing from !_v to _v.*/
1247 for(;;){
1248 /*If we make it all the way to the other side, there's no crossing.*/
1249 if(x0[steep]==x1[steep])return -1;
1250 x0[steep]+=step[steep];
1251 err+=derr;
1252 if(err<<1>dx[steep]){
1253 x0[1-steep]+=step[1-steep];
1254 err-=dx[steep];
1255 }
1256 if(!_img[x0[1]*_width+x0[0]]!=_v)break;
1257 }
1258 /*Find the last crossing from _v to !_v.*/
1259 err=0;
1260 for(;;){
1261 if(x0[steep]==x1[steep])break;
1262 x1[steep]-=step[steep];
1263 err+=derr;
1264 if(err<<1>dx[steep]){
1265 x1[1-steep]-=step[1-steep];
1266 err-=dx[steep];
1267 }
1268 if(!_img[x1[1]*_width+x1[0]]!=_v)break;
1269 }
1270 /*Return the midpoint of the _v segment.*/
1271 _p[0]=(x0[0]+x1[0]+1<<QR_FINDER_SUBPREC)>>1;
1272 _p[1]=(x0[1]+x1[1]+1<<QR_FINDER_SUBPREC)>>1;
1273 return 0;
1274 }
1275
qr_aff_line_step(const qr_aff * _aff,qr_line _l,int _v,int _du,int * _dv)1276 static int qr_aff_line_step(const qr_aff *_aff,qr_line _l,
1277 int _v,int _du,int *_dv){
1278 int shift;
1279 int round;
1280 int dv;
1281 int n;
1282 int d;
1283 n=_aff->fwd[0][_v]*_l[0]+_aff->fwd[1][_v]*_l[1];
1284 d=_aff->fwd[0][1-_v]*_l[0]+_aff->fwd[1][1-_v]*_l[1];
1285 if(d<0){
1286 n=-n;
1287 d=-d;
1288 }
1289 shift=QR_MAXI(0,qr_ilog(_du)+qr_ilog(abs(n))+3-QR_INT_BITS);
1290 round=(1<<shift)>>1;
1291 n=n+round>>shift;
1292 d=d+round>>shift;
1293 /*The line should not be outside 45 degrees of horizontal/vertical.
1294 TODO: We impose this restriction to help ensure the loop below terminates,
1295 but it should not technically be required.
1296 It also, however, ensures we avoid division by zero.*/
1297 if(abs(n)>=d)return -1;
1298 n=-_du*n;
1299 dv=QR_DIVROUND(n,d);
1300 if(abs(dv)>=_du)return -1;
1301 *_dv=dv;
1302 return 0;
1303 }
1304
1305 /*Computes the Hamming distance between two bit patterns (the number of bits
1306 that differ).
1307 May stop counting after _maxdiff differences.*/
qr_hamming_dist(unsigned _y1,unsigned _y2,int _maxdiff)1308 static int qr_hamming_dist(unsigned _y1,unsigned _y2,int _maxdiff){
1309 unsigned y;
1310 int ret;
1311 y=_y1^_y2;
1312 for(ret=0;ret<_maxdiff&&y;ret++)y&=y-1;
1313 return ret;
1314 }
1315
1316 /*Retrieve a bit (guaranteed to be 0 or 1) from the image, given coordinates in
1317 subpel resolution which have not been bounds checked.*/
qr_img_get_bit(const unsigned char * _img,int _width,int _height,int _x,int _y)1318 static int qr_img_get_bit(const unsigned char *_img,int _width,int _height,
1319 int _x,int _y){
1320 _x>>=QR_FINDER_SUBPREC;
1321 _y>>=QR_FINDER_SUBPREC;
1322 return _img[QR_CLAMPI(0,_y,_height-1)*_width+QR_CLAMPI(0,_x,_width-1)]!=0;
1323 }
1324
1325
1326 /*A homography from one region of the grid back to the image.
1327 Unlike a qr_hom, this does not include an inverse transform and maps directly
1328 from the grid points, not a square with power-of-two sides.*/
1329 struct qr_hom_cell{
1330 int fwd[3][3];
1331 int x0;
1332 int y0;
1333 int u0;
1334 int v0;
1335 };
1336
1337
qr_hom_cell_init(qr_hom_cell * _cell,int _u0,int _v0,int _u1,int _v1,int _u2,int _v2,int _u3,int _v3,int _x0,int _y0,int _x1,int _y1,int _x2,int _y2,int _x3,int _y3)1338 static void qr_hom_cell_init(qr_hom_cell *_cell,int _u0,int _v0,
1339 int _u1,int _v1,int _u2,int _v2,int _u3,int _v3,int _x0,int _y0,
1340 int _x1,int _y1,int _x2,int _y2,int _x3,int _y3){
1341 int du10;
1342 int du20;
1343 int du30;
1344 int du31;
1345 int du32;
1346 int dv10;
1347 int dv20;
1348 int dv30;
1349 int dv31;
1350 int dv32;
1351 int dx10;
1352 int dx20;
1353 int dx30;
1354 int dx31;
1355 int dx32;
1356 int dy10;
1357 int dy20;
1358 int dy30;
1359 int dy31;
1360 int dy32;
1361 int a00;
1362 int a01;
1363 int a02;
1364 int a10;
1365 int a11;
1366 int a12;
1367 int a20;
1368 int a21;
1369 int a22;
1370 int i00;
1371 int i01;
1372 int i10;
1373 int i11;
1374 int i20;
1375 int i21;
1376 int i22;
1377 int b0;
1378 int b1;
1379 int b2;
1380 int shift;
1381 int round;
1382 int x;
1383 int y;
1384 int w;
1385 /*First, correct for the arrangement of the source points.
1386 We take advantage of the fact that we know the source points have a very
1387 limited dynamic range (so there will never be overflow) and a small amount
1388 of projective distortion.*/
1389 du10=_u1-_u0;
1390 du20=_u2-_u0;
1391 du30=_u3-_u0;
1392 du31=_u3-_u1;
1393 du32=_u3-_u2;
1394 dv10=_v1-_v0;
1395 dv20=_v2-_v0;
1396 dv30=_v3-_v0;
1397 dv31=_v3-_v1;
1398 dv32=_v3-_v2;
1399 /*Compute the coefficients of the forward transform from the unit square to
1400 the source point configuration.*/
1401 a20=du32*dv10-du10*dv32;
1402 a21=du20*dv31-du31*dv20;
1403 if(a20||a21)a22=du32*dv31-du31*dv32;
1404 /*If the source grid points aren't in a non-affine arrangement, there's no
1405 reason to scale everything by du32*dv31-du31*dv32.
1406 Not doing so allows a much larger dynamic range, and is the only way we can
1407 initialize a base cell that covers the whole grid.*/
1408 else a22=1;
1409 a00=du10*(a20+a22);
1410 a01=du20*(a21+a22);
1411 a10=dv10*(a20+a22);
1412 a11=dv20*(a21+a22);
1413 /*Now compute the inverse transform.*/
1414 i00=a11*a22;
1415 i01=-a01*a22;
1416 i10=-a10*a22;
1417 i11=a00*a22;
1418 i20=a10*a21-a11*a20;
1419 i21=a01*a20-a00*a21;
1420 i22=a00*a11-a01*a10;
1421 /*Invert the coefficients.
1422 Since i22 is the largest, we divide it by all the others.
1423 The quotient is often exact (e.g., when the source points contain no
1424 projective distortion), and is never zero.
1425 Hence we can use zero to signal "infinity" when the divisor is zero.*/
1426 if(i00)i00=QR_FLIPSIGNI(QR_DIVROUND(i22,abs(i00)),i00);
1427 if(i01)i01=QR_FLIPSIGNI(QR_DIVROUND(i22,abs(i01)),i01);
1428 if(i10)i10=QR_FLIPSIGNI(QR_DIVROUND(i22,abs(i10)),i10);
1429 if(i11)i11=QR_FLIPSIGNI(QR_DIVROUND(i22,abs(i11)),i11);
1430 if(i20)i20=QR_FLIPSIGNI(QR_DIVROUND(i22,abs(i20)),i20);
1431 if(i21)i21=QR_FLIPSIGNI(QR_DIVROUND(i22,abs(i21)),i21);
1432 /*Now compute the map from the unit square into the image.*/
1433 dx10=_x1-_x0;
1434 dx20=_x2-_x0;
1435 dx30=_x3-_x0;
1436 dx31=_x3-_x1;
1437 dx32=_x3-_x2;
1438 dy10=_y1-_y0;
1439 dy20=_y2-_y0;
1440 dy30=_y3-_y0;
1441 dy31=_y3-_y1;
1442 dy32=_y3-_y2;
1443 a20=dx32*dy10-dx10*dy32;
1444 a21=dx20*dy31-dx31*dy20;
1445 a22=dx32*dy31-dx31*dy32;
1446 /*Figure out if we need to downscale anything.*/
1447 b0=qr_ilog(QR_MAXI(abs(dx10),abs(dy10)))+qr_ilog(abs(a20+a22));
1448 b1=qr_ilog(QR_MAXI(abs(dx20),abs(dy20)))+qr_ilog(abs(a21+a22));
1449 b2=qr_ilog(QR_MAXI(QR_MAXI(abs(a20),abs(a21)),abs(a22)));
1450 shift=QR_MAXI(0,QR_MAXI(QR_MAXI(b0,b1),b2)-(QR_INT_BITS-3-QR_ALIGN_SUBPREC));
1451 round=(1<<shift)>>1;
1452 /*Compute the final coefficients of the forward transform.*/
1453 a00=QR_FIXMUL(dx10,a20+a22,round,shift);
1454 a01=QR_FIXMUL(dx20,a21+a22,round,shift);
1455 a10=QR_FIXMUL(dy10,a20+a22,round,shift);
1456 a11=QR_FIXMUL(dy20,a21+a22,round,shift);
1457 /*And compose the two transforms.
1458 Since we inverted the coefficients above, we divide by them here instead
1459 of multiplying.
1460 This lets us take advantage of the full dynamic range.
1461 Note a zero divisor is really "infinity", and thus the quotient should also
1462 be zero.*/
1463 _cell->fwd[0][0]=(i00?QR_DIVROUND(a00,i00):0)+(i10?QR_DIVROUND(a01,i10):0);
1464 _cell->fwd[0][1]=(i01?QR_DIVROUND(a00,i01):0)+(i11?QR_DIVROUND(a01,i11):0);
1465 _cell->fwd[1][0]=(i00?QR_DIVROUND(a10,i00):0)+(i10?QR_DIVROUND(a11,i10):0);
1466 _cell->fwd[1][1]=(i01?QR_DIVROUND(a10,i01):0)+(i11?QR_DIVROUND(a11,i11):0);
1467 _cell->fwd[2][0]=(i00?QR_DIVROUND(a20,i00):0)+(i10?QR_DIVROUND(a21,i10):0)
1468 +(i20?QR_DIVROUND(a22,i20):0)+round>>shift;
1469 _cell->fwd[2][1]=(i01?QR_DIVROUND(a20,i01):0)+(i11?QR_DIVROUND(a21,i11):0)
1470 +(i21?QR_DIVROUND(a22,i21):0)+round>>shift;
1471 _cell->fwd[2][2]=a22+round>>shift;
1472 /*Mathematically, a02 and a12 are exactly zero.
1473 However, that concentrates all of the rounding error in the (_u3,_v3)
1474 corner; we compute offsets which distribute it over the whole range.*/
1475 x=_cell->fwd[0][0]*du10+_cell->fwd[0][1]*dv10;
1476 y=_cell->fwd[1][0]*du10+_cell->fwd[1][1]*dv10;
1477 w=_cell->fwd[2][0]*du10+_cell->fwd[2][1]*dv10+_cell->fwd[2][2];
1478 a02=dx10*w-x;
1479 a12=dy10*w-y;
1480 x=_cell->fwd[0][0]*du20+_cell->fwd[0][1]*dv20;
1481 y=_cell->fwd[1][0]*du20+_cell->fwd[1][1]*dv20;
1482 w=_cell->fwd[2][0]*du20+_cell->fwd[2][1]*dv20+_cell->fwd[2][2];
1483 a02+=dx20*w-x;
1484 a12+=dy20*w-y;
1485 x=_cell->fwd[0][0]*du30+_cell->fwd[0][1]*dv30;
1486 y=_cell->fwd[1][0]*du30+_cell->fwd[1][1]*dv30;
1487 w=_cell->fwd[2][0]*du30+_cell->fwd[2][1]*dv30+_cell->fwd[2][2];
1488 a02+=dx30*w-x;
1489 a12+=dy30*w-y;
1490 _cell->fwd[0][2]=a02+2>>2;
1491 _cell->fwd[1][2]=a12+2>>2;
1492 _cell->x0=_x0;
1493 _cell->y0=_y0;
1494 _cell->u0=_u0;
1495 _cell->v0=_v0;
1496 }
1497
1498 /*Finish a partial projection, converting from homogeneous coordinates to the
1499 normal 2-D representation.
1500 In loops, we can avoid many multiplies by computing the homogeneous _x, _y,
1501 and _w incrementally, but we cannot avoid the divisions, done here.*/
qr_hom_cell_fproject(qr_point _p,const qr_hom_cell * _cell,int _x,int _y,int _w)1502 static void qr_hom_cell_fproject(qr_point _p,const qr_hom_cell *_cell,
1503 int _x,int _y,int _w){
1504 if(_w==0){
1505 _p[0]=_x<0?INT_MIN:INT_MAX;
1506 _p[1]=_y<0?INT_MIN:INT_MAX;
1507 }
1508 else{
1509 if(_w<0){
1510 _x=-_x;
1511 _y=-_y;
1512 _w=-_w;
1513 }
1514 _p[0]=QR_DIVROUND(_x,_w)+_cell->x0;
1515 _p[1]=QR_DIVROUND(_y,_w)+_cell->y0;
1516 }
1517 }
1518
qr_hom_cell_project(qr_point _p,const qr_hom_cell * _cell,int _u,int _v,int _res)1519 static void qr_hom_cell_project(qr_point _p,const qr_hom_cell *_cell,
1520 int _u,int _v,int _res){
1521 _u-=_cell->u0<<_res;
1522 _v-=_cell->v0<<_res;
1523 qr_hom_cell_fproject(_p,_cell,
1524 _cell->fwd[0][0]*_u+_cell->fwd[0][1]*_v+(_cell->fwd[0][2]<<_res),
1525 _cell->fwd[1][0]*_u+_cell->fwd[1][1]*_v+(_cell->fwd[1][2]<<_res),
1526 _cell->fwd[2][0]*_u+_cell->fwd[2][1]*_v+(_cell->fwd[2][2]<<_res));
1527 }
1528
1529
1530
1531 /*Retrieves the bits corresponding to the alignment pattern template centered
1532 at the given location in the original image (at subpel precision).*/
qr_alignment_pattern_fetch(qr_point _p[5][5],int _x0,int _y0,const unsigned char * _img,int _width,int _height)1533 static unsigned qr_alignment_pattern_fetch(qr_point _p[5][5],int _x0,int _y0,
1534 const unsigned char *_img,int _width,int _height){
1535 unsigned v;
1536 int i;
1537 int j;
1538 int k;
1539 int dx;
1540 int dy;
1541 dx=_x0-_p[2][2][0];
1542 dy=_y0-_p[2][2][1];
1543 v=0;
1544 for(k=i=0;i<5;i++)for(j=0;j<5;j++,k++){
1545 v|=qr_img_get_bit(_img,_width,_height,_p[i][j][0]+dx,_p[i][j][1]+dy)<<k;
1546 }
1547 return v;
1548 }
1549
1550 /*Searches for an alignment pattern near the given location.*/
qr_alignment_pattern_search(qr_point _p,const qr_hom_cell * _cell,int _u,int _v,int _r,const unsigned char * _img,int _width,int _height)1551 static int qr_alignment_pattern_search(qr_point _p,const qr_hom_cell *_cell,
1552 int _u,int _v,int _r,const unsigned char *_img,int _width,int _height){
1553 qr_point c[4];
1554 int nc[4];
1555 qr_point p[5][5];
1556 qr_point pc;
1557 unsigned best_match;
1558 int best_dist;
1559 int bestx;
1560 int besty;
1561 unsigned match;
1562 int dist;
1563 int u;
1564 int v;
1565 int x0;
1566 int y0;
1567 int w0;
1568 int x;
1569 int y;
1570 int w;
1571 int dxdu;
1572 int dydu;
1573 int dwdu;
1574 int dxdv;
1575 int dydv;
1576 int dwdv;
1577 int dx;
1578 int dy;
1579 int i;
1580 int j;
1581 /*Build up a basic template using _cell to control shape and scale.
1582 We project the points in the template back to the image just once, since if
1583 the alignment pattern has moved, we don't really know why.
1584 If it's because of radial distortion, or the code wasn't flat, or something
1585 else, there's no reason to expect that a re-projection around each
1586 subsequent search point would be any closer to the actual shape than our
1587 first projection.
1588 Therefore we simply slide this template around, as is.*/
1589 u=(_u-2)-_cell->u0;
1590 v=(_v-2)-_cell->v0;
1591 x0=_cell->fwd[0][0]*u+_cell->fwd[0][1]*v+_cell->fwd[0][2];
1592 y0=_cell->fwd[1][0]*u+_cell->fwd[1][1]*v+_cell->fwd[1][2];
1593 w0=_cell->fwd[2][0]*u+_cell->fwd[2][1]*v+_cell->fwd[2][2];
1594 dxdu=_cell->fwd[0][0];
1595 dydu=_cell->fwd[1][0];
1596 dwdu=_cell->fwd[2][0];
1597 dxdv=_cell->fwd[0][1];
1598 dydv=_cell->fwd[1][1];
1599 dwdv=_cell->fwd[2][1];
1600 for(i=0;i<5;i++){
1601 x=x0;
1602 y=y0;
1603 w=w0;
1604 for(j=0;j<5;j++){
1605 qr_hom_cell_fproject(p[i][j],_cell,x,y,w);
1606 x+=dxdu;
1607 y+=dydu;
1608 w+=dwdu;
1609 }
1610 x0+=dxdv;
1611 y0+=dydv;
1612 w0+=dwdv;
1613 }
1614 bestx=p[2][2][0];
1615 besty=p[2][2][1];
1616 best_match=qr_alignment_pattern_fetch(p,bestx,besty,_img,_width,_height);
1617 best_dist=qr_hamming_dist(best_match,0x1F8D63F,25);
1618 if(best_dist>0){
1619 u=_u-_cell->u0;
1620 v=_v-_cell->v0;
1621 x=_cell->fwd[0][0]*u+_cell->fwd[0][1]*v+_cell->fwd[0][2]<<QR_ALIGN_SUBPREC;
1622 y=_cell->fwd[1][0]*u+_cell->fwd[1][1]*v+_cell->fwd[1][2]<<QR_ALIGN_SUBPREC;
1623 w=_cell->fwd[2][0]*u+_cell->fwd[2][1]*v+_cell->fwd[2][2]<<QR_ALIGN_SUBPREC;
1624 /*Search an area at most _r modules around the target location, in
1625 concentric squares..*/
1626 for(i=1;i<_r<<QR_ALIGN_SUBPREC;i++){
1627 int side_len;
1628 side_len=(i<<1)-1;
1629 x-=dxdu+dxdv;
1630 y-=dydu+dydv;
1631 w-=dwdu+dwdv;
1632 for(j=0;j<4*side_len;j++){
1633 int dir;
1634 qr_hom_cell_fproject(pc,_cell,x,y,w);
1635 match=qr_alignment_pattern_fetch(p,pc[0],pc[1],_img,_width,_height);
1636 dist=qr_hamming_dist(match,0x1F8D63F,best_dist+1);
1637 if(dist<best_dist){
1638 best_match=match;
1639 best_dist=dist;
1640 bestx=pc[0];
1641 besty=pc[1];
1642 }
1643 if(j<2*side_len){
1644 dir=j>=side_len;
1645 x+=_cell->fwd[0][dir];
1646 y+=_cell->fwd[1][dir];
1647 w+=_cell->fwd[2][dir];
1648 }
1649 else{
1650 dir=j>=3*side_len;
1651 x-=_cell->fwd[0][dir];
1652 y-=_cell->fwd[1][dir];
1653 w-=_cell->fwd[2][dir];
1654 }
1655 if(!best_dist)break;
1656 }
1657 if(!best_dist)break;
1658 }
1659 }
1660 /*If the best result we got was sufficiently bad, reject the match.
1661 If we're wrong and we include it, we can grossly distort the nearby
1662 region, whereas using the initial starting point should at least be
1663 consistent with the geometry we already have.*/
1664 if(best_dist>6){
1665 _p[0]=p[2][2][0];
1666 _p[1]=p[2][2][1];
1667 return -1;
1668 }
1669 /*Now try to get a more accurate location of the pattern center.*/
1670 dx=bestx-p[2][2][0];
1671 dy=besty-p[2][2][1];
1672 memset(nc,0,sizeof(nc));
1673 memset(c,0,sizeof(c));
1674 /*We consider 8 lines across the finder pattern in turn.
1675 If we actually found a symmetric pattern along that line, search for its
1676 exact center in the image.
1677 There are plenty more lines we could use if these don't work, but if we've
1678 found anything remotely close to an alignment pattern, we should be able
1679 to use most of these.*/
1680 for(i=0;i<8;i++){
1681 static const unsigned MASK_TESTS[8][2]={
1682 {0x1040041,0x1000001},{0x0041040,0x0001000},
1683 {0x0110110,0x0100010},{0x0011100,0x0001000},
1684 {0x0420084,0x0400004},{0x0021080,0x0001000},
1685 {0x0006C00,0x0004400},{0x0003800,0x0001000},
1686 };
1687 static const unsigned char MASK_COORDS[8][2]={
1688 {0,0},{1,1},{4,0},{3,1},{2,0},{2,1},{0,2},{1,2}
1689 };
1690 if((best_match&MASK_TESTS[i][0])==MASK_TESTS[i][1]){
1691 int x0;
1692 int y0;
1693 int x1;
1694 int y1;
1695 x0=p[MASK_COORDS[i][1]][MASK_COORDS[i][0]][0]+dx>>QR_FINDER_SUBPREC;
1696 if(x0<0||x0>=_width)continue;
1697 y0=p[MASK_COORDS[i][1]][MASK_COORDS[i][0]][1]+dy>>QR_FINDER_SUBPREC;
1698 if(y0<0||y0>=_height)continue;
1699 x1=p[4-MASK_COORDS[i][1]][4-MASK_COORDS[i][0]][0]+dx>>QR_FINDER_SUBPREC;
1700 if(x1<0||x1>=_width)continue;
1701 y1=p[4-MASK_COORDS[i][1]][4-MASK_COORDS[i][0]][1]+dy>>QR_FINDER_SUBPREC;
1702 if(y1<0||y1>=_height)continue;
1703 if(!qr_finder_locate_crossing(_img,_width,_height,x0,y0,x1,y1,i&1,pc)){
1704 int w;
1705 int cx;
1706 int cy;
1707 cx=pc[0]-bestx;
1708 cy=pc[1]-besty;
1709 if(i&1){
1710 /*Weight crossings around the center dot more highly, as they are
1711 generally more reliable.*/
1712 w=3;
1713 cx+=cx<<1;
1714 cy+=cy<<1;
1715 }
1716 else w=1;
1717 nc[i>>1]+=w;
1718 c[i>>1][0]+=cx;
1719 c[i>>1][1]+=cy;
1720 }
1721 }
1722 }
1723 /*Sum offsets from lines in orthogonal directions.*/
1724 for(i=0;i<2;i++){
1725 int a;
1726 int b;
1727 a=nc[i<<1];
1728 b=nc[i<<1|1];
1729 if(a&&b){
1730 int w;
1731 w=QR_MAXI(a,b);
1732 c[i<<1][0]=QR_DIVROUND(w*(b*c[i<<1][0]+a*c[i<<1|1][0]),a*b);
1733 c[i<<1][1]=QR_DIVROUND(w*(b*c[i<<1][1]+a*c[i<<1|1][1]),a*b);
1734 nc[i<<1]=w<<1;
1735 }
1736 else{
1737 c[i<<1][0]+=c[i<<1|1][0];
1738 c[i<<1][1]+=c[i<<1|1][1];
1739 nc[i<<1]+=b;
1740 }
1741 }
1742 /*Average offsets from pairs of orthogonal lines.*/
1743 c[0][0]+=c[2][0];
1744 c[0][1]+=c[2][1];
1745 nc[0]+=nc[2];
1746 /*If we actually found any such lines, apply the adjustment.*/
1747 if(nc[0]){
1748 dx=QR_DIVROUND(c[0][0],nc[0]);
1749 dy=QR_DIVROUND(c[0][1],nc[0]);
1750 /*But only if it doesn't make things worse.*/
1751 match=qr_alignment_pattern_fetch(p,bestx+dx,besty+dy,_img,_width,_height);
1752 dist=qr_hamming_dist(match,0x1F8D63F,best_dist+1);
1753 if(dist<=best_dist){
1754 bestx+=dx;
1755 besty+=dy;
1756 }
1757 }
1758 _p[0]=bestx;
1759 _p[1]=besty;
1760 return 0;
1761 }
1762
qr_hom_fit(qr_hom * _hom,qr_finder * _ul,qr_finder * _ur,qr_finder * _dl,qr_point _p[4],const qr_aff * _aff,isaac_ctx * _isaac,const unsigned char * _img,int _width,int _height)1763 static int qr_hom_fit(qr_hom *_hom,qr_finder *_ul,qr_finder *_ur,
1764 qr_finder *_dl,qr_point _p[4],const qr_aff *_aff,isaac_ctx *_isaac,
1765 const unsigned char *_img,int _width,int _height){
1766 qr_point *b;
1767 int nb;
1768 int cb;
1769 qr_point *r;
1770 int nr;
1771 int cr;
1772 qr_line l[4];
1773 qr_point q;
1774 qr_point p;
1775 int ox;
1776 int oy;
1777 int ru;
1778 int rv;
1779 int dru;
1780 int drv;
1781 int bu;
1782 int bv;
1783 int dbu;
1784 int dbv;
1785 int rx;
1786 int ry;
1787 int drxi;
1788 int dryi;
1789 int drxj;
1790 int dryj;
1791 int rdone;
1792 int nrempty;
1793 int rlastfit;
1794 int bx;
1795 int by;
1796 int dbxi;
1797 int dbyi;
1798 int dbxj;
1799 int dbyj;
1800 int bdone;
1801 int nbempty;
1802 int blastfit;
1803 int shift;
1804 int round;
1805 int version4;
1806 int brx;
1807 int bry;
1808 int i;
1809 /*We attempt to correct large-scale perspective distortion by fitting lines
1810 to the edge of the code area.
1811 We could also look for an alignment pattern now, but that wouldn't work for
1812 version 1 codes, which have no alignment pattern.
1813 Even if the code is supposed to have one, there's go guarantee we'd find it
1814 intact.*/
1815 /*Fitting lines is easy for the edges on which we have two finder patterns.
1816 After the fit, UL is guaranteed to be on the proper side, but if either of
1817 the other two finder patterns aren't, something is wrong.*/
1818 qr_finder_ransac(_ul,_aff,_isaac,0);
1819 qr_finder_ransac(_dl,_aff,_isaac,0);
1820 qr_line_fit_finder_pair(l[0],_aff,_ul,_dl,0);
1821 if(qr_line_eval(l[0],_dl->c->pos[0],_dl->c->pos[1])<0||
1822 qr_line_eval(l[0],_ur->c->pos[0],_ur->c->pos[1])<0){
1823 return -1;
1824 }
1825 qr_finder_ransac(_ul,_aff,_isaac,2);
1826 qr_finder_ransac(_ur,_aff,_isaac,2);
1827 qr_line_fit_finder_pair(l[2],_aff,_ul,_ur,2);
1828 if(qr_line_eval(l[2],_dl->c->pos[0],_dl->c->pos[1])<0||
1829 qr_line_eval(l[2],_ur->c->pos[0],_ur->c->pos[1])<0){
1830 return -1;
1831 }
1832 /*The edges which only have one finder pattern are more difficult.
1833 We start by fitting a line to the edge of the one finder pattern we do
1834 have.
1835 This can fail due to an insufficient number of sample points, and even if
1836 it succeeds can be fairly inaccurate, because all of the points are
1837 clustered in one corner of the QR code.
1838 If it fails, we just use an axis-aligned line in the affine coordinate
1839 system.
1840 Then we walk along the edge of the entire code, looking for
1841 light:dark:light patterns perpendicular to the edge.
1842 Wherever we find one, we take the center of the dark portion as an
1843 additional sample point.
1844 At the end, we re-fit the line using all such sample points found.*/
1845 drv=_ur->size[1]>>1;
1846 qr_finder_ransac(_ur,_aff,_isaac,1);
1847 if(qr_line_fit_finder_edge(l[1],_ur,1,_aff->res)>=0){
1848 if(qr_line_eval(l[1],_ul->c->pos[0],_ul->c->pos[1])<0||
1849 qr_line_eval(l[1],_dl->c->pos[0],_dl->c->pos[1])<0){
1850 return -1;
1851 }
1852 /*Figure out the change in ru for a given change in rv when stepping along
1853 the fitted line.*/
1854 if(qr_aff_line_step(_aff,l[1],1,drv,&dru)<0)return -1;
1855 }
1856 else dru=0;
1857 ru=_ur->o[0]+3*_ur->size[0]-2*dru;
1858 rv=_ur->o[1]-2*drv;
1859 dbu=_dl->size[0]>>1;
1860 qr_finder_ransac(_dl,_aff,_isaac,3);
1861 if(qr_line_fit_finder_edge(l[3],_dl,3,_aff->res)>=0){
1862 if(qr_line_eval(l[3],_ul->c->pos[0],_ul->c->pos[1])<0||
1863 qr_line_eval(l[3],_ur->c->pos[0],_ur->c->pos[1])<0){
1864 return -1;
1865 }
1866 /*Figure out the change in bv for a given change in bu when stepping along
1867 the fitted line.*/
1868 if(qr_aff_line_step(_aff,l[3],0,dbu,&dbv)<0)return -1;
1869 }
1870 else dbv=0;
1871 bu=_dl->o[0]-2*dbu;
1872 bv=_dl->o[1]+3*_dl->size[1]-2*dbv;
1873 /*Set up the initial point lists.*/
1874 nr=rlastfit=_ur->ninliers[1];
1875 cr=nr+(_dl->o[1]-rv+drv-1)/drv;
1876 r=(qr_point *)malloc(cr*sizeof(*r));
1877 for(i=0;i<_ur->ninliers[1];i++){
1878 memcpy(r[i],_ur->edge_pts[1][i].pos,sizeof(r[i]));
1879 }
1880 nb=blastfit=_dl->ninliers[3];
1881 cb=nb+(_ur->o[0]-bu+dbu-1)/dbu;
1882 b=(qr_point *)malloc(cb*sizeof(*b));
1883 for(i=0;i<_dl->ninliers[3];i++){
1884 memcpy(b[i],_dl->edge_pts[3][i].pos,sizeof(b[i]));
1885 }
1886 /*Set up the step parameters for the affine projection.*/
1887 ox=(_aff->x0<<_aff->res)+(1<<_aff->res-1);
1888 oy=(_aff->y0<<_aff->res)+(1<<_aff->res-1);
1889 rx=_aff->fwd[0][0]*ru+_aff->fwd[0][1]*rv+ox;
1890 ry=_aff->fwd[1][0]*ru+_aff->fwd[1][1]*rv+oy;
1891 drxi=_aff->fwd[0][0]*dru+_aff->fwd[0][1]*drv;
1892 dryi=_aff->fwd[1][0]*dru+_aff->fwd[1][1]*drv;
1893 drxj=_aff->fwd[0][0]*_ur->size[0];
1894 dryj=_aff->fwd[1][0]*_ur->size[0];
1895 bx=_aff->fwd[0][0]*bu+_aff->fwd[0][1]*bv+ox;
1896 by=_aff->fwd[1][0]*bu+_aff->fwd[1][1]*bv+oy;
1897 dbxi=_aff->fwd[0][0]*dbu+_aff->fwd[0][1]*dbv;
1898 dbyi=_aff->fwd[1][0]*dbu+_aff->fwd[1][1]*dbv;
1899 dbxj=_aff->fwd[0][1]*_dl->size[1];
1900 dbyj=_aff->fwd[1][1]*_dl->size[1];
1901 /*Now step along the lines, looking for new sample points.*/
1902 nrempty=nbempty=0;
1903 for(;;){
1904 int ret;
1905 int x0;
1906 int y0;
1907 int x1;
1908 int y1;
1909 /*If we take too many steps without encountering a non-zero pixel, assume
1910 we have wandered off the edge and stop looking before we hit the other
1911 side of the quiet region.
1912 Otherwise, stop when the lines cross (if they do so inside the affine
1913 region) or come close to crossing (outside the affine region).
1914 TODO: We don't have any way of detecting when we've wandered into the
1915 code interior; we could stop if the outside sample ever shows up dark,
1916 but this could happen because of noise in the quiet region, too.*/
1917 rdone=rv>=QR_MINI(bv,_dl->o[1]+bv>>1)||nrempty>14;
1918 bdone=bu>=QR_MINI(ru,_ur->o[0]+ru>>1)||nbempty>14;
1919 if(!rdone&&(bdone||rv<bu)){
1920 x0=rx+drxj>>_aff->res+QR_FINDER_SUBPREC;
1921 y0=ry+dryj>>_aff->res+QR_FINDER_SUBPREC;
1922 x1=rx-drxj>>_aff->res+QR_FINDER_SUBPREC;
1923 y1=ry-dryj>>_aff->res+QR_FINDER_SUBPREC;
1924 if(nr>=cr){
1925 cr=cr<<1|1;
1926 r=(qr_point *)realloc(r,cr*sizeof(*r));
1927 }
1928 ret=qr_finder_quick_crossing_check(_img,_width,_height,x0,y0,x1,y1,1);
1929 if(!ret){
1930 ret=qr_finder_locate_crossing(_img,_width,_height,x0,y0,x1,y1,1,r[nr]);
1931 }
1932 if(ret>=0){
1933 if(!ret){
1934 qr_aff_unproject(q,_aff,r[nr][0],r[nr][1]);
1935 /*Move the current point halfway towards the crossing.
1936 We don't move the whole way to give us some robustness to noise.*/
1937 ru=ru+q[0]>>1;
1938 /*But ensure that rv monotonically increases.*/
1939 if(q[1]+drv>rv)rv=rv+q[1]>>1;
1940 rx=_aff->fwd[0][0]*ru+_aff->fwd[0][1]*rv+ox;
1941 ry=_aff->fwd[1][0]*ru+_aff->fwd[1][1]*rv+oy;
1942 nr++;
1943 /*Re-fit the line to update the step direction periodically.*/
1944 if(nr>QR_MAXI(1,rlastfit+(rlastfit>>2))){
1945 qr_line_fit_points(l[1],r,nr,_aff->res);
1946 if(qr_aff_line_step(_aff,l[1],1,drv,&dru)>=0){
1947 drxi=_aff->fwd[0][0]*dru+_aff->fwd[0][1]*drv;
1948 dryi=_aff->fwd[1][0]*dru+_aff->fwd[1][1]*drv;
1949 }
1950 rlastfit=nr;
1951 }
1952 }
1953 else nrempty=0;
1954 }
1955 else nrempty++;
1956 ru+=dru;
1957 /*Our final defense: if we overflow, stop.*/
1958 if(rv+drv>rv)rv+=drv;
1959 else nrempty=INT_MAX;
1960 rx+=drxi;
1961 ry+=dryi;
1962 }
1963 else if(!bdone){
1964 x0=bx+dbxj>>_aff->res+QR_FINDER_SUBPREC;
1965 y0=by+dbyj>>_aff->res+QR_FINDER_SUBPREC;
1966 x1=bx-dbxj>>_aff->res+QR_FINDER_SUBPREC;
1967 y1=by-dbyj>>_aff->res+QR_FINDER_SUBPREC;
1968 if(nb>=cb){
1969 cb=cb<<1|1;
1970 b=(qr_point *)realloc(b,cb*sizeof(*b));
1971 }
1972 ret=qr_finder_quick_crossing_check(_img,_width,_height,x0,y0,x1,y1,1);
1973 if(!ret){
1974 ret=qr_finder_locate_crossing(_img,_width,_height,x0,y0,x1,y1,1,b[nb]);
1975 }
1976 if(ret>=0){
1977 if(!ret){
1978 qr_aff_unproject(q,_aff,b[nb][0],b[nb][1]);
1979 /*Move the current point halfway towards the crossing.
1980 We don't move the whole way to give us some robustness to noise.*/
1981 /*But ensure that bu monotonically increases.*/
1982 if(q[0]+dbu>bu)bu=bu+q[0]>>1;
1983 bv=bv+q[1]>>1;
1984 bx=_aff->fwd[0][0]*bu+_aff->fwd[0][1]*bv+ox;
1985 by=_aff->fwd[1][0]*bu+_aff->fwd[1][1]*bv+oy;
1986 nb++;
1987 /*Re-fit the line to update the step direction periodically.*/
1988 if(nb>QR_MAXI(1,blastfit+(blastfit>>2))){
1989 qr_line_fit_points(l[3],b,nb,_aff->res);
1990 if(qr_aff_line_step(_aff,l[3],0,dbu,&dbv)>=0){
1991 dbxi=_aff->fwd[0][0]*dbu+_aff->fwd[0][1]*dbv;
1992 dbyi=_aff->fwd[1][0]*dbu+_aff->fwd[1][1]*dbv;
1993 }
1994 blastfit=nb;
1995 }
1996 }
1997 nbempty=0;
1998 }
1999 else nbempty++;
2000 /*Our final defense: if we overflow, stop.*/
2001 if(bu+dbu>bu)bu+=dbu;
2002 else nbempty=INT_MAX;
2003 bv+=dbv;
2004 bx+=dbxi;
2005 by+=dbyi;
2006 }
2007 else break;
2008 }
2009 /*Fit the new lines.
2010 If we _still_ don't have enough sample points, then just use an
2011 axis-aligned line from the affine coordinate system (e.g., one parallel
2012 to the opposite edge in the image).*/
2013 if(nr>1)qr_line_fit_points(l[1],r,nr,_aff->res);
2014 else{
2015 qr_aff_project(p,_aff,_ur->o[0]+3*_ur->size[0],_ur->o[1]);
2016 shift=QR_MAXI(0,
2017 qr_ilog(QR_MAXI(abs(_aff->fwd[0][1]),abs(_aff->fwd[1][1])))
2018 -(_aff->res+1>>1));
2019 round=(1<<shift)>>1;
2020 l[1][0]=_aff->fwd[1][1]+round>>shift;
2021 l[1][1]=-_aff->fwd[0][1]+round>>shift;
2022 l[1][2]=-(l[1][0]*p[0]+l[1][1]*p[1]);
2023 }
2024 free(r);
2025 if(nb>1)qr_line_fit_points(l[3],b,nb,_aff->res);
2026 else{
2027 qr_aff_project(p,_aff,_dl->o[0],_dl->o[1]+3*_dl->size[1]);
2028 shift=QR_MAXI(0,
2029 qr_ilog(QR_MAXI(abs(_aff->fwd[0][1]),abs(_aff->fwd[1][1])))
2030 -(_aff->res+1>>1));
2031 round=(1<<shift)>>1;
2032 l[3][0]=_aff->fwd[1][0]+round>>shift;
2033 l[3][1]=-_aff->fwd[0][0]+round>>shift;
2034 l[3][2]=-(l[1][0]*p[0]+l[1][1]*p[1]);
2035 }
2036 free(b);
2037 for(i=0;i<4;i++){
2038 if(qr_line_isect(_p[i],l[i&1],l[2+(i>>1)])<0)return -1;
2039 /*It's plausible for points to be somewhat outside the image, but too far
2040 and too much of the pattern will be gone for it to be decodable.*/
2041 if(_p[i][0]<-_width<<QR_FINDER_SUBPREC||
2042 _p[i][0]>=_width<<QR_FINDER_SUBPREC+1||
2043 _p[i][1]<-_height<<QR_FINDER_SUBPREC||
2044 _p[i][1]>=_height<<QR_FINDER_SUBPREC+1){
2045 return -1;
2046 }
2047 }
2048 /*By default, use the edge intersection point for the bottom-right corner.*/
2049 brx=_p[3][0];
2050 bry=_p[3][1];
2051 /*However, if our average version estimate is greater than 1, NOW we try to
2052 search for an alignment pattern.
2053 We get a much better success rate by doing this after our initial attempt
2054 to promote the transform to a homography than before.
2055 You might also think it would be more reliable to use the interior finder
2056 pattern edges, since the outer ones may be obscured or damaged, and it
2057 would save us a reprojection below, since they would form a nice square
2058 with the location of the alignment pattern, but this turns out to be a bad
2059 idea.
2060 Non-linear distortion is usually maximal on the outside edge, and thus
2061 estimating the grid position from points on the interior means we might
2062 get mis-aligned by the time we reach the edge.*/
2063 version4=_ul->eversion[0]+_ul->eversion[1]+_ur->eversion[0]+_dl->eversion[1];
2064 if(version4>4){
2065 qr_hom_cell cell;
2066 qr_point p3;
2067 int dim;
2068 dim=17+version4;
2069 qr_hom_cell_init(&cell,0,0,dim-1,0,0,dim-1,dim-1,dim-1,
2070 _p[0][0],_p[0][1],_p[1][0],_p[1][1],
2071 _p[2][0],_p[2][1],_p[3][0],_p[3][1]);
2072 if(qr_alignment_pattern_search(p3,&cell,dim-7,dim-7,4,
2073 _img,_width,_height)>=0){
2074 int c21;
2075 int dx21;
2076 int dy21;
2077 int mask;
2078 int w;
2079 /*There's no real need to update the bounding box corner, and in fact we
2080 actively perform worse if we do.
2081 Clearly it was good enough for us to find this alignment pattern, so
2082 it should be good enough to use for grid initialization.
2083 The point of doing the search was to get more accurate version
2084 estimates and a better chance of decoding the version and format info.
2085 This is particularly important for small versions that have no encoded
2086 version info, since any mismatch in version renders the code
2087 undecodable.*/
2088 /*We do, however, need four points in a square to initialize our
2089 homography, so project the point from the alignment center to the
2090 corner of the code area.*/
2091 c21=_p[2][0]*_p[1][1]-_p[2][1]*_p[1][0];
2092 dx21=_p[2][0]-_p[1][0];
2093 dy21=_p[2][1]-_p[1][1];
2094 w=(dim-7)*c21
2095 +(dim-13)*(_p[0][0]*dy21-_p[0][1]*dx21)+6*(p3[0]*dy21-p3[1]*dx21);
2096 mask=QR_SIGNMASK(w);
2097 w=abs(w);
2098 brx=(int)QR_DIVROUND(QR_EXTMUL((dim-7)*_p[0][0],p3[0]*dy21,
2099 QR_EXTMUL((dim-13)*p3[0],c21-_p[0][1]*dx21,
2100 QR_EXTMUL(6*_p[0][0],c21-p3[1]*dx21,0)))+mask^mask,w);
2101 bry=(int)QR_DIVROUND(QR_EXTMUL((dim-7)*_p[0][1],-p3[1]*dx21,
2102 QR_EXTMUL((dim-13)*p3[1],c21+_p[0][0]*dy21,
2103 QR_EXTMUL(6*_p[0][1],c21+p3[0]*dy21,0)))+mask^mask,w);
2104 }
2105 }
2106 /*Now we have four points that map to a square: initialize the projection.*/
2107 qr_hom_init(_hom,_p[0][0],_p[0][1],_p[1][0],_p[1][1],
2108 _p[2][0],_p[2][1],brx,bry,QR_HOM_BITS);
2109 return 0;
2110 }
2111
2112
2113
2114 /*The BCH(18,6,3) codes are only used for version information, which must lie
2115 between 7 and 40 (inclusive).*/
2116 static const unsigned BCH18_6_CODES[34]={
2117 0x07C94,
2118 0x085BC,0x09A99,0x0A4D3,0x0BBF6,0x0C762,0x0D847,0x0E60D,0x0F928,
2119 0x10B78,0x1145D,0x12A17,0x13532,0x149A6,0x15683,0x168C9,0x177EC,
2120 0x18EC4,0x191E1,0x1AFAB,0x1B08E,0x1CC1A,0x1D33F,0x1ED75,0x1F250,
2121 0x209D5,0x216F0,0x228BA,0x2379F,0x24B0B,0x2542E,0x26A64,0x27541,
2122 0x28C69
2123 };
2124
2125 /*Corrects a BCH(18,6,3) code word.
2126 _y: Contains the code word to be checked on input, and the corrected value on
2127 output.
2128 Return: The number of errors.
2129 If more than 3 errors are detected, returns a negative value and
2130 performs no correction.*/
bch18_6_correct(unsigned * _y)2131 static int bch18_6_correct(unsigned *_y){
2132 unsigned x;
2133 unsigned y;
2134 int nerrs;
2135 y=*_y;
2136 /*Check the easy case first: see if the data bits were uncorrupted.*/
2137 x=y>>12;
2138 if(x>=7&&x<=40){
2139 nerrs=qr_hamming_dist(y,BCH18_6_CODES[x-7],4);
2140 if(nerrs<4){
2141 *_y=BCH18_6_CODES[x-7];
2142 return nerrs;
2143 }
2144 }
2145 /*Exhaustive search is faster than field operations in GF(19).*/
2146 for(x=0;x<34;x++)if(x+7!=y>>12){
2147 nerrs=qr_hamming_dist(y,BCH18_6_CODES[x],4);
2148 if(nerrs<4){
2149 *_y=BCH18_6_CODES[x];
2150 return nerrs;
2151 }
2152 }
2153 return -1;
2154 }
2155
2156 #if 0
2157 static unsigned bch18_6_encode(unsigned _x){
2158 return (-(_x&1)&0x01F25)^(-(_x>>1&1)&0x0216F)^(-(_x>>2&1)&0x042DE)^
2159 (-(_x>>3&1)&0x085BC)^(-(_x>>4&1)&0x10B78)^(-(_x>>5&1)&0x209D5);
2160 }
2161 #endif
2162
2163 /*Reads the version bits near a finder module and decodes the version number.*/
qr_finder_version_decode(qr_finder * _f,const qr_hom * _hom,const unsigned char * _img,int _width,int _height,int _dir)2164 static int qr_finder_version_decode(qr_finder *_f,const qr_hom *_hom,
2165 const unsigned char *_img,int _width,int _height,int _dir){
2166 qr_point q;
2167 unsigned v;
2168 int x0;
2169 int y0;
2170 int w0;
2171 int dxi;
2172 int dyi;
2173 int dwi;
2174 int dxj;
2175 int dyj;
2176 int dwj;
2177 int ret;
2178 int i;
2179 int j;
2180 int k;
2181 v=0;
2182 q[_dir]=_f->o[_dir]-7*_f->size[_dir];
2183 q[1-_dir]=_f->o[1-_dir]-3*_f->size[1-_dir];
2184 x0=_hom->fwd[0][0]*q[0]+_hom->fwd[0][1]*q[1];
2185 y0=_hom->fwd[1][0]*q[0]+_hom->fwd[1][1]*q[1];
2186 w0=_hom->fwd[2][0]*q[0]+_hom->fwd[2][1]*q[1]+_hom->fwd22;
2187 dxi=_hom->fwd[0][1-_dir]*_f->size[1-_dir];
2188 dyi=_hom->fwd[1][1-_dir]*_f->size[1-_dir];
2189 dwi=_hom->fwd[2][1-_dir]*_f->size[1-_dir];
2190 dxj=_hom->fwd[0][_dir]*_f->size[_dir];
2191 dyj=_hom->fwd[1][_dir]*_f->size[_dir];
2192 dwj=_hom->fwd[2][_dir]*_f->size[_dir];
2193 for(k=i=0;i<6;i++){
2194 int x;
2195 int y;
2196 int w;
2197 x=x0;
2198 y=y0;
2199 w=w0;
2200 for(j=0;j<3;j++,k++){
2201 qr_point p;
2202 qr_hom_fproject(p,_hom,x,y,w);
2203 v|=qr_img_get_bit(_img,_width,_height,p[0],p[1])<<k;
2204 x+=dxj;
2205 y+=dyj;
2206 w+=dwj;
2207 }
2208 x0+=dxi;
2209 y0+=dyi;
2210 w0+=dwi;
2211 }
2212 ret=bch18_6_correct(&v);
2213 /*TODO: I'd certainly hope the order the version bits is accessed in is
2214 well-defined, but I seem to have images for two different codes with the
2215 same version using two different orders?
2216 Maybe the other one is a model 1 code?
2217 Even if I parse the version here, I can't decode the rest of the code.
2218 If this is really needed, we should just re-order the bits.*/
2219 #if 0
2220 if(ret<0){
2221 /*17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
2222 0 3 6 9 12 15 1 4 7 10 13 16 2 5 8 11 14 17
2223 17 13 9 5 1 -3 10 6 2 -2 -6-10 3 -1 -5 -9-13-17*/
2224 v=0;
2225 for(k=i=0;i<3;i++){
2226 p[_dir]=_f->o[_dir]+_f->size[_dir]*(-5-i);
2227 for(j=0;j<6;j++,k++){
2228 qr_point q;
2229 p[1-_dir]=_f->o[1-_dir]+_f->size[1-_dir]*(2-j);
2230 qr_hom_project(q,_hom,p[0],p[1]);
2231 v|=qr_img_get_bit(_img,_width,_height,q[0],q[1])<<k;
2232 }
2233 }
2234 ret=bch18_6_correct(&v);
2235 }
2236 #endif
2237 return ret>=0?(int)(v>>12):ret;
2238 }
2239
2240 /*Reads the format info bits near the finder modules and decodes them.*/
qr_finder_fmt_info_decode(qr_finder * _ul,qr_finder * _ur,qr_finder * _dl,const qr_hom * _hom,const unsigned char * _img,int _width,int _height)2241 static int qr_finder_fmt_info_decode(qr_finder *_ul,qr_finder *_ur,
2242 qr_finder *_dl,const qr_hom *_hom,
2243 const unsigned char *_img,int _width,int _height){
2244 qr_point p;
2245 unsigned lo[2];
2246 unsigned hi[2];
2247 int u;
2248 int v;
2249 int x;
2250 int y;
2251 int w;
2252 int dx;
2253 int dy;
2254 int dw;
2255 int fmt_info[4];
2256 int count[4];
2257 int nerrs[4];
2258 int nfmt_info;
2259 int besti;
2260 int imax;
2261 int di;
2262 int i;
2263 int k;
2264 /*Read the bits around the UL corner.*/
2265 lo[0]=0;
2266 u=_ul->o[0]+5*_ul->size[0];
2267 v=_ul->o[1]-3*_ul->size[1];
2268 x=_hom->fwd[0][0]*u+_hom->fwd[0][1]*v;
2269 y=_hom->fwd[1][0]*u+_hom->fwd[1][1]*v;
2270 w=_hom->fwd[2][0]*u+_hom->fwd[2][1]*v+_hom->fwd22;
2271 dx=_hom->fwd[0][1]*_ul->size[1];
2272 dy=_hom->fwd[1][1]*_ul->size[1];
2273 dw=_hom->fwd[2][1]*_ul->size[1];
2274 for(k=i=0;;i++){
2275 /*Skip the timing pattern row.*/
2276 if(i!=6){
2277 qr_hom_fproject(p,_hom,x,y,w);
2278 lo[0]|=qr_img_get_bit(_img,_width,_height,p[0],p[1])<<k++;
2279 /*Don't advance q in the last iteration... we'll start the next loop from
2280 the current position.*/
2281 if(i>=8)break;
2282 }
2283 x+=dx;
2284 y+=dy;
2285 w+=dw;
2286 }
2287 hi[0]=0;
2288 dx=-_hom->fwd[0][0]*_ul->size[0];
2289 dy=-_hom->fwd[1][0]*_ul->size[0];
2290 dw=-_hom->fwd[2][0]*_ul->size[0];
2291 while(i-->0){
2292 x+=dx;
2293 y+=dy;
2294 w+=dw;
2295 /*Skip the timing pattern column.*/
2296 if(i!=6){
2297 qr_hom_fproject(p,_hom,x,y,w);
2298 hi[0]|=qr_img_get_bit(_img,_width,_height,p[0],p[1])<<k++;
2299 }
2300 }
2301 /*Read the bits next to the UR corner.*/
2302 lo[1]=0;
2303 u=_ur->o[0]+3*_ur->size[0];
2304 v=_ur->o[1]+5*_ur->size[1];
2305 x=_hom->fwd[0][0]*u+_hom->fwd[0][1]*v;
2306 y=_hom->fwd[1][0]*u+_hom->fwd[1][1]*v;
2307 w=_hom->fwd[2][0]*u+_hom->fwd[2][1]*v+_hom->fwd22;
2308 dx=-_hom->fwd[0][0]*_ur->size[0];
2309 dy=-_hom->fwd[1][0]*_ur->size[0];
2310 dw=-_hom->fwd[2][0]*_ur->size[0];
2311 for(k=0;k<8;k++){
2312 qr_hom_fproject(p,_hom,x,y,w);
2313 lo[1]|=qr_img_get_bit(_img,_width,_height,p[0],p[1])<<k;
2314 x+=dx;
2315 y+=dy;
2316 w+=dw;
2317 }
2318 /*Read the bits next to the DL corner.*/
2319 hi[1]=0;
2320 u=_dl->o[0]+5*_dl->size[0];
2321 v=_dl->o[1]-3*_dl->size[1];
2322 x=_hom->fwd[0][0]*u+_hom->fwd[0][1]*v;
2323 y=_hom->fwd[1][0]*u+_hom->fwd[1][1]*v;
2324 w=_hom->fwd[2][0]*u+_hom->fwd[2][1]*v+_hom->fwd22;
2325 dx=_hom->fwd[0][1]*_dl->size[1];
2326 dy=_hom->fwd[1][1]*_dl->size[1];
2327 dw=_hom->fwd[2][1]*_dl->size[1];
2328 for(k=8;k<15;k++){
2329 qr_hom_fproject(p,_hom,x,y,w);
2330 hi[1]|=qr_img_get_bit(_img,_width,_height,p[0],p[1])<<k;
2331 x+=dx;
2332 y+=dy;
2333 w+=dw;
2334 }
2335 /*For the 8th bit we have 3 samples... use the majority value.
2336 TODO: The DL bit appears to be wrong as much as right? Guess it's not
2337 really a third copy after all, but doesn't appear to be used for data.
2338 i=((lo[0]>>7&1)+(lo[1]>>7&1)+(hi[1]>>7&1)>>1)<<7;
2339 lo[0]=lo[0]&~0x80|i;
2340 lo[1]=lo[1]&~0x80|i;
2341 hi[1]&=~0x80;*/
2342 /*For the remaining bits we have two samples... try them in all
2343 combinations and pick the most popular valid code, breaking ties using
2344 the number of bit errors.*/
2345 imax=2<<(hi[0]!=hi[1]);
2346 di=1+(lo[0]==lo[1]);
2347 nfmt_info=0;
2348 for(i=0;i<imax;i+=di){
2349 unsigned v;
2350 int ret;
2351 int j;
2352 v=(lo[i&1]|hi[i>>1])^0x5412;
2353 ret=bch15_5_correct(&v);
2354 v>>=10;
2355 if(ret<0)ret=4;
2356 for(j=0;;j++){
2357 if(j>=nfmt_info){
2358 fmt_info[j]=v;
2359 count[j]=1;
2360 nerrs[j]=ret;
2361 nfmt_info++;
2362 break;
2363 }
2364 if(fmt_info[j]==(int)v){
2365 count[j]++;
2366 if(ret<nerrs[j])nerrs[j]=ret;
2367 break;
2368 }
2369 }
2370 }
2371 besti=0;
2372 for(i=1;i<nfmt_info;i++){
2373 if(nerrs[besti]>3&&nerrs[i]<=3||
2374 count[i]>count[besti]||count[i]==count[besti]&&nerrs[i]<nerrs[besti]){
2375 besti=i;
2376 }
2377 }
2378 return nerrs[besti]<4?fmt_info[besti]:-1;
2379 }
2380
2381
2382
2383 /*The grid used to sample the image bits.
2384 The grid is divided into separate cells bounded by finder patterns and/or
2385 alignment patterns, and a separate map back to the original image is
2386 constructed for each cell.
2387 All of these structural elements, as well as the timing patterns, version
2388 info, and format info, are marked in fpmask so they can easily be skipped
2389 during decode.*/
2390 struct qr_sampling_grid{
2391 qr_hom_cell *cells[6];
2392 unsigned *fpmask;
2393 int cell_limits[6];
2394 int ncells;
2395 };
2396
2397
2398 /*Mark a given region as belonging to the function pattern.*/
qr_sampling_grid_fp_mask_rect(qr_sampling_grid * _grid,int _dim,int _u,int _v,int _w,int _h)2399 static void qr_sampling_grid_fp_mask_rect(qr_sampling_grid *_grid,int _dim,
2400 int _u,int _v,int _w,int _h){
2401 int i;
2402 int j;
2403 int stride;
2404 stride=_dim+QR_INT_BITS-1>>QR_INT_LOGBITS;
2405 /*Note that we store bits column-wise, since that's how they're read out of
2406 the grid.*/
2407 for(j=_u;j<_u+_w;j++)for(i=_v;i<_v+_h;i++){
2408 _grid->fpmask[j*stride+(i>>QR_INT_LOGBITS)]|=1<<(i&QR_INT_BITS-1);
2409 }
2410 }
2411
2412 /*Determine if a given grid location is inside the function pattern.*/
qr_sampling_grid_is_in_fp(const qr_sampling_grid * _grid,int _dim,int _u,int _v)2413 static int qr_sampling_grid_is_in_fp(const qr_sampling_grid *_grid,int _dim,
2414 int _u,int _v){
2415 return _grid->fpmask[_u*(_dim+QR_INT_BITS-1>>QR_INT_LOGBITS)
2416 +(_v>>QR_INT_LOGBITS)]>>(_v&QR_INT_BITS-1)&1;
2417 }
2418
2419 /*The spacing between alignment patterns after the second for versions >= 7.
2420 We could compact this more, but the code to access it would eliminate the
2421 gains.*/
2422 static const unsigned char QR_ALIGNMENT_SPACING[34]={
2423 16,18,20,22,24,26,28,
2424 20,22,24,24,26,28,28,
2425 22,24,24,26,26,28,28,
2426 24,24,26,26,26,28,28,
2427 24,26,26,26,28,28
2428 };
2429
qr_svg_points(const char * cls,qr_point * p,int n)2430 static inline void qr_svg_points(const char *cls,
2431 qr_point *p,
2432 int n)
2433 {
2434 svg_path_start(cls, 1, 0, 0);
2435 int i;
2436 for(i = 0; i < n; i++, p++)
2437 svg_path_moveto(SVG_ABS, p[0][0], p[0][1]);
2438 svg_path_end();
2439 }
2440
2441 /*Initialize the sampling grid for each region of the code.
2442 _version: The (decoded) version number.
2443 _ul_pos: The location of the UL finder pattern.
2444 _ur_pos: The location of the UR finder pattern.
2445 _dl_pos: The location of the DL finder pattern.
2446 _p: On input, contains estimated positions of the four corner modules.
2447 On output, contains a bounding quadrilateral for the code.
2448 _img: The binary input image.
2449 _width: The width of the input image.
2450 _height: The height of the input image.
2451 Return: 0 on success, or a negative value on error.*/
qr_sampling_grid_init(qr_sampling_grid * _grid,int _version,const qr_point _ul_pos,const qr_point _ur_pos,const qr_point _dl_pos,qr_point _p[4],const unsigned char * _img,int _width,int _height)2452 static void qr_sampling_grid_init(qr_sampling_grid *_grid,int _version,
2453 const qr_point _ul_pos,const qr_point _ur_pos,const qr_point _dl_pos,
2454 qr_point _p[4],const unsigned char *_img,int _width,int _height){
2455 qr_hom_cell base_cell;
2456 int align_pos[7];
2457 int dim;
2458 int nalign;
2459 int i;
2460 dim=17+(_version<<2);
2461 nalign=(_version/7)+2;
2462 /*Create a base cell to bootstrap the alignment pattern search.*/
2463 qr_hom_cell_init(&base_cell,0,0,dim-1,0,0,dim-1,dim-1,dim-1,
2464 _p[0][0],_p[0][1],_p[1][0],_p[1][1],_p[2][0],_p[2][1],_p[3][0],_p[3][1]);
2465 /*Allocate the array of cells.*/
2466 _grid->ncells=nalign-1;
2467 _grid->cells[0]=(qr_hom_cell *)malloc(
2468 (nalign-1)*(nalign-1)*sizeof(*_grid->cells[0]));
2469 for(i=1;i<_grid->ncells;i++)_grid->cells[i]=_grid->cells[i-1]+_grid->ncells;
2470 /*Initialize the function pattern mask.*/
2471 _grid->fpmask=(unsigned *)calloc(dim,
2472 (dim+QR_INT_BITS-1>>QR_INT_LOGBITS)*sizeof(*_grid->fpmask));
2473 /*Mask out the finder patterns (and separators and format info bits).*/
2474 qr_sampling_grid_fp_mask_rect(_grid,dim,0,0,9,9);
2475 qr_sampling_grid_fp_mask_rect(_grid,dim,0,dim-8,9,8);
2476 qr_sampling_grid_fp_mask_rect(_grid,dim,dim-8,0,8,9);
2477 /*Mask out the version number bits.*/
2478 if(_version>6){
2479 qr_sampling_grid_fp_mask_rect(_grid,dim,0,dim-11,6,3);
2480 qr_sampling_grid_fp_mask_rect(_grid,dim,dim-11,0,3,6);
2481 }
2482 /*Mask out the timing patterns.*/
2483 qr_sampling_grid_fp_mask_rect(_grid,dim,9,6,dim-17,1);
2484 qr_sampling_grid_fp_mask_rect(_grid,dim,6,9,1,dim-17);
2485 /*If we have no alignment patterns (e.g., this is a version 1 code), just use
2486 the base cell and hope it's good enough.*/
2487 if(_version<2)memcpy(_grid->cells[0],&base_cell,sizeof(base_cell));
2488 else{
2489 qr_point *q;
2490 qr_point *p;
2491 int j;
2492 int k;
2493 q=(qr_point *)malloc(nalign*nalign*sizeof(*q));
2494 p=(qr_point *)malloc(nalign*nalign*sizeof(*p));
2495 /*Initialize the alignment pattern position list.*/
2496 align_pos[0]=6;
2497 align_pos[nalign-1]=dim-7;
2498 if(_version>6){
2499 int d;
2500 d=QR_ALIGNMENT_SPACING[_version-7];
2501 for(i=nalign-1;i-->1;)align_pos[i]=align_pos[i+1]-d;
2502 }
2503 /*Three of the corners use a finder pattern instead of a separate
2504 alignment pattern.*/
2505 q[0][0]=3;
2506 q[0][1]=3;
2507 p[0][0]=_ul_pos[0];
2508 p[0][1]=_ul_pos[1];
2509 q[nalign-1][0]=dim-4;
2510 q[nalign-1][1]=3;
2511 p[nalign-1][0]=_ur_pos[0];
2512 p[nalign-1][1]=_ur_pos[1];
2513 q[(nalign-1)*nalign][0]=3;
2514 q[(nalign-1)*nalign][1]=dim-4;
2515 p[(nalign-1)*nalign][0]=_dl_pos[0];
2516 p[(nalign-1)*nalign][1]=_dl_pos[1];
2517 /*Scan for alignment patterns using a diagonal sweep.*/
2518 for(k=1;k<2*nalign-1;k++){
2519 int jmin;
2520 int jmax;
2521 jmax=QR_MINI(k,nalign-1)-(k==nalign-1);
2522 jmin=QR_MAXI(0,k-(nalign-1))+(k==nalign-1);
2523 for(j=jmin;j<=jmax;j++){
2524 qr_hom_cell *cell;
2525 int u;
2526 int v;
2527 int k;
2528 i=jmax-(j-jmin);
2529 k=i*nalign+j;
2530 u=align_pos[j];
2531 v=align_pos[i];
2532 q[k][0]=u;
2533 q[k][1]=v;
2534 /*Mask out the alignment pattern.*/
2535 qr_sampling_grid_fp_mask_rect(_grid,dim,u-2,v-2,5,5);
2536 /*Pick a cell to use to govern the alignment pattern search.*/
2537 if(i>1&&j>1){
2538 qr_point p0;
2539 qr_point p1;
2540 qr_point p2;
2541 /*Each predictor is basically a straight-line extrapolation from two
2542 neighboring alignment patterns (except possibly near the opposing
2543 finder patterns).*/
2544 qr_hom_cell_project(p0,_grid->cells[i-2]+j-1,u,v,0);
2545 qr_hom_cell_project(p1,_grid->cells[i-2]+j-2,u,v,0);
2546 qr_hom_cell_project(p2,_grid->cells[i-1]+j-2,u,v,0);
2547 /*Take the median of the predictions as the search center.*/
2548 QR_SORT2I(p0[0],p1[0]);
2549 QR_SORT2I(p0[1],p1[1]);
2550 QR_SORT2I(p1[0],p2[0]);
2551 QR_SORT2I(p1[1],p2[1]);
2552 QR_SORT2I(p0[0],p1[0]);
2553 QR_SORT2I(p0[1],p1[1]);
2554 /*We need a cell that has the target point at a known (u,v) location.
2555 Since our cells don't have inverses, just construct one from our
2556 neighboring points.*/
2557 cell=_grid->cells[i-1]+j-1;
2558 qr_hom_cell_init(cell,
2559 q[k-nalign-1][0],q[k-nalign-1][1],q[k-nalign][0],q[k-nalign][1],
2560 q[k-1][0],q[k-1][1],q[k][0],q[k][1],
2561 p[k-nalign-1][0],p[k-nalign-1][1],p[k-nalign][0],p[k-nalign][1],
2562 p[k-1][0],p[k-1][1],p1[0],p1[1]);
2563 }
2564 else if(i>1&&j>0)cell=_grid->cells[i-2]+j-1;
2565 else if(i>0&&j>1)cell=_grid->cells[i-1]+j-2;
2566 else cell=&base_cell;
2567 /*Use a very small search radius.
2568 A large displacement here usually means a false positive (e.g., when
2569 the real alignment pattern is damaged or missing), which can
2570 severely distort the projection.*/
2571 qr_alignment_pattern_search(p[k],cell,u,v,2,_img,_width,_height);
2572 if(i>0&&j>0){
2573 qr_hom_cell_init(_grid->cells[i-1]+j-1,
2574 q[k-nalign-1][0],q[k-nalign-1][1],q[k-nalign][0],q[k-nalign][1],
2575 q[k-1][0],q[k-1][1],q[k][0],q[k][1],
2576 p[k-nalign-1][0],p[k-nalign-1][1],p[k-nalign][0],p[k-nalign][1],
2577 p[k-1][0],p[k-1][1],p[k][0],p[k][1]);
2578 }
2579 }
2580 }
2581 qr_svg_points("align", p, nalign * nalign);
2582 free(q);
2583 free(p);
2584 }
2585 /*Set the limits over which each cell is used.*/
2586 memcpy(_grid->cell_limits,align_pos+1,
2587 (_grid->ncells-1)*sizeof(*_grid->cell_limits));
2588 _grid->cell_limits[_grid->ncells-1]=dim;
2589 /*Produce a bounding square for the code (to mark finder centers with).
2590 Because of non-linear distortion, this might not actually bound the code,
2591 but it should be good enough.
2592 I don't think it's worth computing a convex hull or anything silly like
2593 that.*/
2594 qr_hom_cell_project(_p[0],_grid->cells[0]+0,-1,-1,1);
2595 qr_hom_cell_project(_p[1],_grid->cells[0]+_grid->ncells-1,(dim<<1)-1,-1,1);
2596 qr_hom_cell_project(_p[2],_grid->cells[_grid->ncells-1]+0,-1,(dim<<1)-1,1);
2597 qr_hom_cell_project(_p[3],_grid->cells[_grid->ncells-1]+_grid->ncells-1,
2598 (dim<<1)-1,(dim<<1)-1,1);
2599 /*Clamp the points somewhere near the image (this is really just in case a
2600 corner is near the plane at infinity).*/
2601 for(i=0;i<4;i++){
2602 _p[i][0]=QR_CLAMPI(-_width<<QR_FINDER_SUBPREC,_p[i][0],
2603 _width<<QR_FINDER_SUBPREC+1);
2604 _p[i][1]=QR_CLAMPI(-_height<<QR_FINDER_SUBPREC,_p[i][1],
2605 _height<<QR_FINDER_SUBPREC+1);
2606 }
2607 /*TODO: Make fine adjustments using the timing patterns.
2608 Possible strategy: scan the timing pattern at QR_ALIGN_SUBPREC (or finer)
2609 resolution, use dynamic programming to match midpoints between
2610 transitions to the ideal grid locations.*/
2611 }
2612
qr_sampling_grid_clear(qr_sampling_grid * _grid)2613 static void qr_sampling_grid_clear(qr_sampling_grid *_grid){
2614 free(_grid->fpmask);
2615 free(_grid->cells[0]);
2616 }
2617
2618
2619
2620 #if defined(QR_DEBUG)
qr_sampling_grid_dump(qr_sampling_grid * _grid,int _version,const unsigned char * _img,int _width,int _height)2621 static void qr_sampling_grid_dump(qr_sampling_grid *_grid,int _version,
2622 const unsigned char *_img,int _width,int _height){
2623 unsigned char *gimg;
2624 FILE *fout;
2625 int dim;
2626 int u;
2627 int v;
2628 int x;
2629 int y;
2630 int w;
2631 int i;
2632 int j;
2633 int r;
2634 int s;
2635 dim=17+(_version<<2)+8<<QR_ALIGN_SUBPREC;
2636 gimg=(unsigned char *)malloc(dim*dim*sizeof(*gimg));
2637 for(i=0;i<dim;i++)for(j=0;j<dim;j++){
2638 qr_hom_cell *cell;
2639 if(i>=(4<<QR_ALIGN_SUBPREC)&&i<=dim-(5<<QR_ALIGN_SUBPREC)&&
2640 j>=(4<<QR_ALIGN_SUBPREC)&&j<=dim-(5<<QR_ALIGN_SUBPREC)&&
2641 ((!(i&(1<<QR_ALIGN_SUBPREC)-1))^(!(j&(1<<QR_ALIGN_SUBPREC)-1)))){
2642 gimg[i*dim+j]=0x7F;
2643 }
2644 else{
2645 qr_point p;
2646 u=(j>>QR_ALIGN_SUBPREC)-4;
2647 v=(i>>QR_ALIGN_SUBPREC)-4;
2648 for(r=0;r<_grid->ncells-1;r++)if(u<_grid->cell_limits[r])break;
2649 for(s=0;s<_grid->ncells-1;s++)if(v<_grid->cell_limits[s])break;
2650 cell=_grid->cells[s]+r;
2651 u=j-(cell->u0+4<<QR_ALIGN_SUBPREC);
2652 v=i-(cell->v0+4<<QR_ALIGN_SUBPREC);
2653 x=cell->fwd[0][0]*u+cell->fwd[0][1]*v+(cell->fwd[0][2]<<QR_ALIGN_SUBPREC);
2654 y=cell->fwd[1][0]*u+cell->fwd[1][1]*v+(cell->fwd[1][2]<<QR_ALIGN_SUBPREC);
2655 w=cell->fwd[2][0]*u+cell->fwd[2][1]*v+(cell->fwd[2][2]<<QR_ALIGN_SUBPREC);
2656 qr_hom_cell_fproject(p,cell,x,y,w);
2657 gimg[i*dim+j]=_img[
2658 QR_CLAMPI(0,p[1]>>QR_FINDER_SUBPREC,_height-1)*_width+
2659 QR_CLAMPI(0,p[0]>>QR_FINDER_SUBPREC,_width-1)];
2660 }
2661 }
2662 for(v=0;v<17+(_version<<2);v++)for(u=0;u<17+(_version<<2);u++){
2663 if(qr_sampling_grid_is_in_fp(_grid,17+(_version<<2),u,v)){
2664 j=u+4<<QR_ALIGN_SUBPREC;
2665 i=v+4<<QR_ALIGN_SUBPREC;
2666 gimg[(i-1)*dim+j-1]=0x7F;
2667 gimg[(i-1)*dim+j]=0x7F;
2668 gimg[(i-1)*dim+j+1]=0x7F;
2669 gimg[i*dim+j-1]=0x7F;
2670 gimg[i*dim+j+1]=0x7F;
2671 gimg[(i+1)*dim+j-1]=0x7F;
2672 gimg[(i+1)*dim+j]=0x7F;
2673 gimg[(i+1)*dim+j+1]=0x7F;
2674 }
2675 }
2676 fout=fopen("grid.png","wb");
2677 image_write_png(gimg,dim,dim,fout);
2678 fclose(fout);
2679 free(gimg);
2680 }
2681 #endif
2682
2683 /*Generate the data mask corresponding to the given mask pattern.*/
qr_data_mask_fill(unsigned * _mask,int _dim,int _pattern)2684 static void qr_data_mask_fill(unsigned *_mask,int _dim,int _pattern){
2685 int stride;
2686 int i;
2687 int j;
2688 stride=_dim+QR_INT_BITS-1>>QR_INT_LOGBITS;
2689 /*Note that we store bits column-wise, since that's how they're read out of
2690 the grid.*/
2691 switch(_pattern){
2692 /*10101010 i+j+1&1
2693 01010101
2694 10101010
2695 01010101*/
2696 case 0:{
2697 int m;
2698 m=0x55;
2699 for(j=0;j<_dim;j++){
2700 memset(_mask+j*stride,m,stride*sizeof(*_mask));
2701 m^=0xFF;
2702 }
2703 }break;
2704 /*11111111 i+1&1
2705 00000000
2706 11111111
2707 00000000*/
2708 case 1:memset(_mask,0x55,_dim*stride*sizeof(*_mask));break;
2709 /*10010010 (j+1)%3&1
2710 10010010
2711 10010010
2712 10010010*/
2713 case 2:{
2714 unsigned m;
2715 m=0xFF;
2716 for(j=0;j<_dim;j++){
2717 memset(_mask+j*stride,m&0xFF,stride*sizeof(*_mask));
2718 m=m<<8|m>>16;
2719 }
2720 }break;
2721 /*10010010 (i+j+1)%3&1
2722 00100100
2723 01001001
2724 10010010*/
2725 case 3:{
2726 unsigned mi;
2727 unsigned mj;
2728 mj=0;
2729 for(i=0;i<(QR_INT_BITS+2)/3;i++)mj|=1<<3*i;
2730 for(j=0;j<_dim;j++){
2731 mi=mj;
2732 for(i=0;i<stride;i++){
2733 _mask[j*stride+i]=mi;
2734 mi=mi>>QR_INT_BITS%3|mi<<3-QR_INT_BITS%3;
2735 }
2736 mj=mj>>1|mj<<2;
2737 }
2738 }break;
2739 /*11100011 (i>>1)+(j/3)+1&1
2740 11100011
2741 00011100
2742 00011100*/
2743 case 4:{
2744 unsigned m;
2745 m=7;
2746 for(j=0;j<_dim;j++){
2747 memset(_mask+j*stride,(0xCC^-(m&1))&0xFF,stride*sizeof(*_mask));
2748 m=m>>1|m<<5;
2749 }
2750 }break;
2751 /*11111111 !((i*j)%6)
2752 10000010
2753 10010010
2754 10101010*/
2755 case 5:{
2756 for(j=0;j<_dim;j++){
2757 unsigned m;
2758 m=0;
2759 for(i=0;i<6;i++)m|=!((i*j)%6)<<i;
2760 for(i=6;i<QR_INT_BITS;i<<=1)m|=m<<i;
2761 for(i=0;i<stride;i++){
2762 _mask[j*stride+i]=m;
2763 m=m>>QR_INT_BITS%6|m<<6-QR_INT_BITS%6;
2764 }
2765 }
2766 }break;
2767 /*11111111 (i*j)%3+i*j+1&1
2768 11100011
2769 11011011
2770 10101010*/
2771 case 6:{
2772 for(j=0;j<_dim;j++){
2773 unsigned m;
2774 m=0;
2775 for(i=0;i<6;i++)m|=((i*j)%3+i*j+1&1)<<i;
2776 for(i=6;i<QR_INT_BITS;i<<=1)m|=m<<i;
2777 for(i=0;i<stride;i++){
2778 _mask[j*stride+i]=m;
2779 m=m>>QR_INT_BITS%6|m<<6-QR_INT_BITS%6;
2780 }
2781 }
2782 }break;
2783 /*10101010 (i*j)%3+i+j+1&1
2784 00011100
2785 10001110
2786 01010101*/
2787 default:{
2788 for(j=0;j<_dim;j++){
2789 unsigned m;
2790 m=0;
2791 for(i=0;i<6;i++)m|=((i*j)%3+i+j+1&1)<<i;
2792 for(i=6;i<QR_INT_BITS;i<<=1)m|=m<<i;
2793 for(i=0;i<stride;i++){
2794 _mask[j*stride+i]=m;
2795 m=m>>QR_INT_BITS%6|m<<6-QR_INT_BITS%6;
2796 }
2797 }
2798 }break;
2799 }
2800 }
2801
qr_sampling_grid_sample(const qr_sampling_grid * _grid,unsigned * _data_bits,int _dim,int _fmt_info,const unsigned char * _img,int _width,int _height)2802 static void qr_sampling_grid_sample(const qr_sampling_grid *_grid,
2803 unsigned *_data_bits,int _dim,int _fmt_info,
2804 const unsigned char *_img,int _width,int _height){
2805 int stride;
2806 int u0;
2807 int u1;
2808 int j;
2809 /*We initialize the buffer with the data mask and XOR bits into it as we read
2810 them out of the image instead of unmasking in a separate step.*/
2811 qr_data_mask_fill(_data_bits,_dim,_fmt_info&7);
2812 stride=_dim+QR_INT_BITS-1>>QR_INT_LOGBITS;
2813 u0=0;
2814 svg_path_start("sampling-grid", 1, 0, 0);
2815 /*We read data cell-by-cell to avoid having to constantly change which
2816 projection we're using as we read each bit.
2817 This (and the position-dependent data mask) is the reason we buffer the
2818 bits we read instead of converting them directly to codewords here.
2819 Note that bits are stored column-wise, since that's how we'll scan them.*/
2820 for(j=0;j<_grid->ncells;j++){
2821 int i;
2822 int v0;
2823 int v1;
2824 u1=_grid->cell_limits[j];
2825 v0=0;
2826 for(i=0;i<_grid->ncells;i++){
2827 qr_hom_cell *cell;
2828 int x0;
2829 int y0;
2830 int w0;
2831 int u;
2832 int du;
2833 int dv;
2834 v1=_grid->cell_limits[i];
2835 cell=_grid->cells[i]+j;
2836 du=u0-cell->u0;
2837 dv=v0-cell->v0;
2838 x0=cell->fwd[0][0]*du+cell->fwd[0][1]*dv+cell->fwd[0][2];
2839 y0=cell->fwd[1][0]*du+cell->fwd[1][1]*dv+cell->fwd[1][2];
2840 w0=cell->fwd[2][0]*du+cell->fwd[2][1]*dv+cell->fwd[2][2];
2841 for(u=u0;u<u1;u++){
2842 int x;
2843 int y;
2844 int w;
2845 int v;
2846 x=x0;
2847 y=y0;
2848 w=w0;
2849 for(v=v0;v<v1;v++){
2850 /*Skip doing all the divisions and bounds checks if the bit is in the
2851 function pattern.*/
2852 if(!qr_sampling_grid_is_in_fp(_grid,_dim,u,v)){
2853 qr_point p;
2854 qr_hom_cell_fproject(p,cell,x,y,w);
2855 _data_bits[u*stride+(v>>QR_INT_LOGBITS)]^=
2856 qr_img_get_bit(_img,_width,_height,p[0],p[1])<<(v&QR_INT_BITS-1);
2857 svg_path_moveto(SVG_ABS, p[0], p[1]);
2858 }
2859 x+=cell->fwd[0][1];
2860 y+=cell->fwd[1][1];
2861 w+=cell->fwd[2][1];
2862 }
2863 x0+=cell->fwd[0][0];
2864 y0+=cell->fwd[1][0];
2865 w0+=cell->fwd[2][0];
2866 }
2867 v0=v1;
2868 }
2869 u0=u1;
2870 }
2871 svg_path_end();
2872 }
2873
2874 /*Arranges the sample bits read by qr_sampling_grid_sample() into bytes and
2875 groups those bytes into Reed-Solomon blocks.
2876 The individual block pointers are destroyed by this routine.*/
qr_samples_unpack(unsigned char ** _blocks,int _nblocks,int _nshort_data,int _nshort_blocks,const unsigned * _data_bits,const unsigned * _fp_mask,int _dim)2877 static void qr_samples_unpack(unsigned char **_blocks,int _nblocks,
2878 int _nshort_data,int _nshort_blocks,const unsigned *_data_bits,
2879 const unsigned *_fp_mask,int _dim){
2880 unsigned bits;
2881 int biti;
2882 int stride;
2883 int blocki;
2884 int blockj;
2885 int i;
2886 int j;
2887 stride=_dim+QR_INT_BITS-1>>QR_INT_LOGBITS;
2888 /*If _all_ the blocks are short, don't skip anything (see below).*/
2889 if(_nshort_blocks>=_nblocks)_nshort_blocks=0;
2890 /*Scan columns in pairs from right to left.*/
2891 bits=0;
2892 for(blocki=blockj=biti=0,j=_dim-1;j>0;j-=2){
2893 unsigned data1;
2894 unsigned data2;
2895 unsigned fp_mask1;
2896 unsigned fp_mask2;
2897 int nbits;
2898 int l;
2899 /*Scan up a pair of columns.*/
2900 nbits=(_dim-1&QR_INT_BITS-1)+1;
2901 l=j*stride;
2902 for(i=stride;i-->0;){
2903 data1=_data_bits[l+i];
2904 fp_mask1=_fp_mask[l+i];
2905 data2=_data_bits[l+i-stride];
2906 fp_mask2=_fp_mask[l+i-stride];
2907 while(nbits-->0){
2908 /*Pull a bit from the right column.*/
2909 if(!(fp_mask1>>nbits&1)){
2910 bits=bits<<1|data1>>nbits&1;
2911 biti++;
2912 }
2913 /*Pull a bit from the left column.*/
2914 if(!(fp_mask2>>nbits&1)){
2915 bits=bits<<1|data2>>nbits&1;
2916 biti++;
2917 }
2918 /*If we finished a byte, drop it in a block.*/
2919 if(biti>=8){
2920 biti-=8;
2921 *_blocks[blocki++]++=(unsigned char)(bits>>biti);
2922 /*For whatever reason, the long blocks are at the _end_ of the list,
2923 instead of the beginning.
2924 Even worse, the extra bytes they get come at the end of the data
2925 bytes, before the parity bytes.
2926 Hence the logic here: when we've filled up the data portion of the
2927 short blocks, skip directly to the long blocks for the next byte.
2928 It's also the reason we increment _blocks[blocki] on each store,
2929 instead of just indexing with blockj (after this iteration the
2930 number of bytes in each block differs).*/
2931 if(blocki>=_nblocks)blocki=++blockj==_nshort_data?_nshort_blocks:0;
2932 }
2933 }
2934 nbits=QR_INT_BITS;
2935 }
2936 j-=2;
2937 /*Skip the column with the vertical timing pattern.*/
2938 if(j==6)j--;
2939 /*Scan down a pair of columns.*/
2940 l=j*stride;
2941 for(i=0;i<stride;i++){
2942 data1=_data_bits[l+i];
2943 fp_mask1=_fp_mask[l+i];
2944 data2=_data_bits[l+i-stride];
2945 fp_mask2=_fp_mask[l+i-stride];
2946 nbits=QR_MINI(_dim-(i<<QR_INT_LOGBITS),QR_INT_BITS);
2947 while(nbits-->0){
2948 /*Pull a bit from the right column.*/
2949 if(!(fp_mask1&1)){
2950 bits=bits<<1|data1&1;
2951 biti++;
2952 }
2953 data1>>=1;
2954 fp_mask1>>=1;
2955 /*Pull a bit from the left column.*/
2956 if(!(fp_mask2&1)){
2957 bits=bits<<1|data2&1;
2958 biti++;
2959 }
2960 data2>>=1;
2961 fp_mask2>>=1;
2962 /*If we finished a byte, drop it in a block.*/
2963 if(biti>=8){
2964 biti-=8;
2965 *_blocks[blocki++]++=(unsigned char)(bits>>biti);
2966 /*See comments on the "up" loop for the reason behind this mess.*/
2967 if(blocki>=_nblocks)blocki=++blockj==_nshort_data?_nshort_blocks:0;
2968 }
2969 }
2970 }
2971 }
2972 }
2973
2974
2975 /*Bit reading code blatantly stolen^W^Wadapted from libogg/libtheora (because
2976 I've already debugged it and I know it works).
2977 Portions (C) Xiph.Org Foundation 1994-2008, BSD-style license.*/
2978 struct qr_pack_buf{
2979 const unsigned char *buf;
2980 int endbyte;
2981 int endbit;
2982 int storage;
2983 };
2984
2985
qr_pack_buf_init(qr_pack_buf * _b,const unsigned char * _data,int _ndata)2986 static void qr_pack_buf_init(qr_pack_buf *_b,
2987 const unsigned char *_data,int _ndata){
2988 _b->buf=_data;
2989 _b->storage=_ndata;
2990 _b->endbyte=_b->endbit=0;
2991 }
2992
2993 /*Assumes 0<=_bits<=16.*/
qr_pack_buf_read(qr_pack_buf * _b,int _bits)2994 static int qr_pack_buf_read(qr_pack_buf *_b,int _bits){
2995 const unsigned char *p;
2996 unsigned ret;
2997 int m;
2998 int d;
2999 m=16-_bits;
3000 _bits+=_b->endbit;
3001 d=_b->storage-_b->endbyte;
3002 if(d<=2){
3003 /*Not the main path.*/
3004 if(d*8<_bits){
3005 _b->endbyte+=_bits>>3;
3006 _b->endbit=_bits&7;
3007 return -1;
3008 }
3009 /*Special case to avoid reading p[0] below, which might be past the end of
3010 the buffer; also skips some useless accounting.*/
3011 else if(!_bits)return 0;
3012 }
3013 p=_b->buf+_b->endbyte;
3014 ret=p[0]<<8+_b->endbit;
3015 if(_bits>8){
3016 ret|=p[1]<<_b->endbit;
3017 if(_bits>16)ret|=p[2]>>8-_b->endbit;
3018 }
3019 _b->endbyte+=_bits>>3;
3020 _b->endbit=_bits&7;
3021 return (ret&0xFFFF)>>m;
3022 }
3023
qr_pack_buf_avail(const qr_pack_buf * _b)3024 static int qr_pack_buf_avail(const qr_pack_buf *_b){
3025 return (_b->storage-_b->endbyte<<3)-_b->endbit;
3026 }
3027
3028
3029 /*The characters available in QR_MODE_ALNUM.*/
3030 static const unsigned char QR_ALNUM_TABLE[45]={
3031 '0','1','2','3','4','5','6','7','8','9',
3032 'A','B','C','D','E','F','G','H','I','J',
3033 'K','L','M','N','O','P','Q','R','S','T',
3034 'U','V','W','X','Y','Z',' ','$','%','*',
3035 '+','-','.','/',':'
3036 };
3037
qr_code_data_parse(qr_code_data * _qrdata,int _version,const unsigned char * _data,int _ndata)3038 static int qr_code_data_parse(qr_code_data *_qrdata,int _version,
3039 const unsigned char *_data,int _ndata){
3040 qr_pack_buf qpb;
3041 int centries;
3042 int len_bits_idx;
3043 /*Entries are stored directly in the struct during parsing.
3044 Caller cleans up any allocated data on failure.*/
3045 _qrdata->entries=NULL;
3046 _qrdata->nentries=0;
3047 _qrdata->sa_size=0;
3048 centries=0;
3049 /*The versions are divided into 3 ranges that each use a different number of
3050 bits for length fields.*/
3051 len_bits_idx=(_version>9)+(_version>26);
3052 qr_pack_buf_init(&qpb,_data,_ndata);
3053 /*While we have enough bits to read a mode...*/
3054 while(qr_pack_buf_avail(&qpb)>=4){
3055 qr_code_data_entry *entry;
3056 int mode;
3057 mode=qr_pack_buf_read(&qpb,4);
3058 /*Mode 0 is a terminator.*/
3059 if(!mode)break;
3060 if(_qrdata->nentries>=centries){
3061 centries=centries<<1|1;
3062 _qrdata->entries=(qr_code_data_entry *)realloc(_qrdata->entries,
3063 centries*sizeof(*_qrdata->entries));
3064 }
3065 entry=_qrdata->entries+_qrdata->nentries++;
3066 /*Set the mode to an invalid value until we allocate a buffer for it.
3067 This ensures we don't try to free it on clean-up until then.*/
3068 entry->mode=-1;
3069 switch(mode){
3070 /*The number of bits used to encode the character count for each version
3071 range and each data mode.*/
3072 static const unsigned char LEN_BITS[3][4]={
3073 {10, 9, 8, 8},
3074 {12,11,16,10},
3075 {14,13,16,12}
3076 };
3077 case QR_MODE_NUM:{
3078 unsigned char *buf;
3079 unsigned bits;
3080 int len;
3081 int count;
3082 int rem;
3083 len=qr_pack_buf_read(&qpb,LEN_BITS[len_bits_idx][0]);
3084 if(len<0)return -1;
3085 /*Check to see if there are enough bits left now, so we don't have to
3086 in the decode loop.*/
3087 count=len/3;
3088 rem=len%3;
3089 if(qr_pack_buf_avail(&qpb)<10*count+7*(rem>>1&1)+4*(rem&1))return -1;
3090 entry->mode=mode;
3091 entry->payload.data.buf=buf=(unsigned char *)malloc(len*sizeof(*buf));
3092 entry->payload.data.len=len;
3093 /*Read groups of 3 digits encoded in 10 bits.*/
3094 while(count-->0){
3095 bits=qr_pack_buf_read(&qpb,10);
3096 if(bits>=1000)return -1;
3097 *buf++=(unsigned char)('0'+bits/100);
3098 bits%=100;
3099 *buf++=(unsigned char)('0'+bits/10);
3100 *buf++=(unsigned char)('0'+bits%10);
3101 }
3102 /*Read the last two digits encoded in 7 bits.*/
3103 if(rem>1){
3104 bits=qr_pack_buf_read(&qpb,7);
3105 if(bits>=100)return -1;
3106 *buf++=(unsigned char)('0'+bits/10);
3107 *buf++=(unsigned char)('0'+bits%10);
3108 }
3109 /*Or the last one digit encoded in 4 bits.*/
3110 else if(rem){
3111 bits=qr_pack_buf_read(&qpb,4);
3112 if(bits>=10)return -1;
3113 *buf++=(unsigned char)('0'+bits);
3114 }
3115 }break;
3116 case QR_MODE_ALNUM:{
3117 unsigned char *buf;
3118 unsigned bits;
3119 int len;
3120 int count;
3121 int rem;
3122 len=qr_pack_buf_read(&qpb,LEN_BITS[len_bits_idx][1]);
3123 if(len<0)return -1;
3124 /*Check to see if there are enough bits left now, so we don't have to
3125 in the decode loop.*/
3126 count=len>>1;
3127 rem=len&1;
3128 if(qr_pack_buf_avail(&qpb)<11*count+6*rem)return -1;
3129 entry->mode=mode;
3130 entry->payload.data.buf=buf=(unsigned char *)malloc(len*sizeof(*buf));
3131 entry->payload.data.len=len;
3132 /*Read groups of two characters encoded in 11 bits.*/
3133 while(count-->0){
3134 bits=qr_pack_buf_read(&qpb,11);
3135 if(bits>=2025)return -1;
3136 *buf++=QR_ALNUM_TABLE[bits/45];
3137 *buf++=QR_ALNUM_TABLE[bits%45];
3138 len-=2;
3139 }
3140 /*Read the last character encoded in 6 bits.*/
3141 if(rem){
3142 bits=qr_pack_buf_read(&qpb,6);
3143 if(bits>=45)return -1;
3144 *buf++=QR_ALNUM_TABLE[bits];
3145 }
3146 }break;
3147 /*Structured-append header.*/
3148 case QR_MODE_STRUCT:{
3149 int bits;
3150 entry->mode=mode;
3151 bits=qr_pack_buf_read(&qpb,16);
3152 if(bits<0)return -1;
3153 /*We also save a copy of the data in _qrdata for easy reference when
3154 grouping structured-append codes.
3155 If for some reason the code has multiple S-A headers, last one wins
3156 (TODO: should we return an error instead?).*/
3157 _qrdata->sa_index=entry->payload.sa.sa_index=
3158 (unsigned char)(bits>>12&0xF);
3159 _qrdata->sa_size=entry->payload.sa.sa_size=
3160 (unsigned char)((bits>>8&0xF)+1);
3161 _qrdata->sa_parity=entry->payload.sa.sa_parity=
3162 (unsigned char)(bits&0xFF);
3163 }break;
3164 case QR_MODE_BYTE:{
3165 unsigned char *buf;
3166 int len;
3167 len=qr_pack_buf_read(&qpb,LEN_BITS[len_bits_idx][2]);
3168 if(len<0)return -1;
3169 /*Check to see if there are enough bits left now, so we don't have to
3170 in the decode loop.*/
3171 if(qr_pack_buf_avail(&qpb)<len<<3)return -1;
3172 entry->mode=mode;
3173 entry->payload.data.buf=buf=(unsigned char *)malloc(len*sizeof(*buf));
3174 entry->payload.data.len=len;
3175 while(len-->0)*buf++=(unsigned char)qr_pack_buf_read(&qpb,8);
3176 }break;
3177 /*FNC1 first position marker.*/
3178 case QR_MODE_FNC1_1ST:entry->mode=mode;break;
3179 /*Extended Channel Interpretation data.*/
3180 case QR_MODE_ECI:{
3181 unsigned val;
3182 int bits;
3183 /*ECI uses a variable-width encoding similar to UTF-8*/
3184 bits=qr_pack_buf_read(&qpb,8);
3185 if(bits<0)return -1;
3186 /*One byte:*/
3187 if(!(bits&0x80))val=bits;
3188 /*Two bytes:*/
3189 else if(!(bits&0x40)){
3190 val=bits&0x3F<<8;
3191 bits=qr_pack_buf_read(&qpb,8);
3192 if(bits<0)return -1;
3193 val|=bits;
3194 }
3195 /*Three bytes:*/
3196 else if(!(bits&0x20)){
3197 val=bits&0x1F<<16;
3198 bits=qr_pack_buf_read(&qpb,16);
3199 if(bits<0)return -1;
3200 val|=bits;
3201 /*Valid ECI values are 0...999999.*/
3202 if(val>=1000000)return -1;
3203 }
3204 /*Invalid lead byte.*/
3205 else return -1;
3206 entry->mode=mode;
3207 entry->payload.eci=val;
3208 }break;
3209 case QR_MODE_KANJI:{
3210 unsigned char *buf;
3211 unsigned bits;
3212 int len;
3213 len=qr_pack_buf_read(&qpb,LEN_BITS[len_bits_idx][3]);
3214 if(len<0)return -1;
3215 /*Check to see if there are enough bits left now, so we don't have to
3216 in the decode loop.*/
3217 if(qr_pack_buf_avail(&qpb)<13*len)return -1;
3218 entry->mode=mode;
3219 entry->payload.data.buf=buf=(unsigned char *)malloc(2*len*sizeof(*buf));
3220 entry->payload.data.len=2*len;
3221 /*Decode 2-byte SJIS characters encoded in 13 bits.*/
3222 while(len-->0){
3223 bits=qr_pack_buf_read(&qpb,13);
3224 bits=(bits/0xC0<<8|bits%0xC0)+0x8140;
3225 if(bits>=0xA000)bits+=0x4000;
3226 /*Are values 0xXX7F, 0xXXFD...0xXXFF always invalid?
3227 Should we reject them here?*/
3228 *buf++=(unsigned char)(bits>>8);
3229 *buf++=(unsigned char)(bits&0xFF);
3230 }
3231 }break;
3232 /*FNC1 second position marker.*/
3233 case QR_MODE_FNC1_2ND:entry->mode=mode;break;
3234 /*Unknown mode number:*/
3235 default:{
3236 /*Unfortunately, because we have to understand the format of a mode to
3237 know how many bits it occupies, we can't skip unknown modes.
3238 Therefore we have to fail.*/
3239 return -1;
3240 }break;
3241 }
3242 }
3243 /*TODO: If there was a S-A header, we should compute the parity of this
3244 code; how are non-data modes handled (ECI, FNC1)?*/
3245 _qrdata->self_parity=0;
3246 /*Success.*/
3247 _qrdata->entries=(qr_code_data_entry *)realloc(_qrdata->entries,
3248 _qrdata->nentries*sizeof(*_qrdata->entries));
3249 return 0;
3250 }
3251
qr_code_data_clear(qr_code_data * _qrdata)3252 static void qr_code_data_clear(qr_code_data *_qrdata){
3253 int i;
3254 for(i=0;i<_qrdata->nentries;i++){
3255 if(QR_MODE_HAS_DATA(_qrdata->entries[i].mode)){
3256 free(_qrdata->entries[i].payload.data.buf);
3257 }
3258 }
3259 free(_qrdata->entries);
3260 }
3261
3262
qr_code_data_list_init(qr_code_data_list * _qrlist)3263 void qr_code_data_list_init(qr_code_data_list *_qrlist){
3264 _qrlist->qrdata=NULL;
3265 _qrlist->nqrdata=_qrlist->cqrdata=0;
3266 }
3267
qr_code_data_list_clear(qr_code_data_list * _qrlist)3268 void qr_code_data_list_clear(qr_code_data_list *_qrlist){
3269 int i;
3270 for(i=0;i<_qrlist->nqrdata;i++)qr_code_data_clear(_qrlist->qrdata+i);
3271 free(_qrlist->qrdata);
3272 qr_code_data_list_init(_qrlist);
3273 }
3274
qr_code_data_list_add(qr_code_data_list * _qrlist,qr_code_data * _qrdata)3275 static void qr_code_data_list_add(qr_code_data_list *_qrlist,
3276 qr_code_data *_qrdata){
3277 if(_qrlist->nqrdata>=_qrlist->cqrdata){
3278 _qrlist->cqrdata=_qrlist->cqrdata<<1|1;
3279 _qrlist->qrdata=(qr_code_data *)realloc(_qrlist->qrdata,
3280 _qrlist->cqrdata*sizeof(*_qrlist->qrdata));
3281 }
3282 memcpy(_qrlist->qrdata+_qrlist->nqrdata++,_qrdata,sizeof(*_qrdata));
3283 }
3284
3285 #if 0
3286 static const unsigned short QR_NCODEWORDS[40]={
3287 26, 44, 70, 100, 134, 172, 196, 242, 292, 346,
3288 404, 466, 532, 581, 655, 733, 815, 901, 991,1085,
3289 1156,1258,1364,1474,1588,1706,1828,1921,2051,2185,
3290 2323,2465,2611,2761,2876,3034,3196,3362,3532,3706
3291 };
3292 #endif
3293
3294 /*The total number of codewords in a QR code.*/
qr_code_ncodewords(unsigned _version)3295 static int qr_code_ncodewords(unsigned _version){
3296 unsigned nalign;
3297 /*This is 24-27 instructions on ARM in thumb mode, or a 26-32 byte savings
3298 over just using a table (not counting the instructions that would be
3299 needed to do the table lookup).*/
3300 if(_version==1)return 26;
3301 nalign=(_version/7)+2;
3302 return (_version<<4)*(_version+8)
3303 -(5*nalign)*(5*nalign-2)+36*(_version<7)+83>>3;
3304 }
3305
3306 #if 0
3307 /*The number of parity bytes per Reed-Solomon block for each version and error
3308 correction level.*/
3309 static const unsigned char QR_RS_NPAR[40][4]={
3310 { 7,10,13,17},{10,16,22,28},{15,26,18,22},{20,18,26,16},
3311 {26,24,18,22},{18,16,24,28},{20,18,18,26},{24,22,22,26},
3312 {30,22,20,24},{18,26,24,28},{20,30,28,24},{24,22,26,28},
3313 {26,22,24,22},{30,24,20,24},{22,24,30,24},{24,28,24,30},
3314 {28,28,28,28},{30,26,28,28},{28,26,26,26},{28,26,30,28},
3315 {28,26,28,30},{28,28,30,24},{30,28,30,30},{30,28,30,30},
3316 {26,28,30,30},{28,28,28,30},{30,28,30,30},{30,28,30,30},
3317 {30,28,30,30},{30,28,30,30},{30,28,30,30},{30,28,30,30},
3318 {30,28,30,30},{30,28,30,30},{30,28,30,30},{30,28,30,30},
3319 {30,28,30,30},{30,28,30,30},{30,28,30,30},{30,28,30,30}
3320 };
3321 #endif
3322
3323 /*Bulk data for the number of parity bytes per Reed-Solomon block.*/
3324 static const unsigned char QR_RS_NPAR_VALS[71]={
3325 /*[ 0]*/ 7,10,13,17,
3326 /*[ 4]*/10,16,22, 28,26,26, 26,22, 24,22,22, 26,24,18,22,
3327 /*[19]*/15,26,18, 22,24, 30,24,20,24,
3328 /*[28]*/18,16,24, 28, 28, 28,28,30,24,
3329 /*[37]*/20,18, 18,26, 24,28,24, 30,26,28, 28, 26,28,30, 30,22,20,24,
3330 /*[55]*/20,18,26,16,
3331 /*[59]*/20,30,28, 24,22,26, 28,26, 30,28,30,30
3332 };
3333
3334 /*An offset into QR_RS_NPAR_DATA for each version that gives the number of
3335 parity bytes per Reed-Solomon block for each error correction level.*/
3336 static const unsigned char QR_RS_NPAR_OFFS[40]={
3337 0, 4,19,55,15,28,37,12,51,39,
3338 59,62,10,24,22,41,31,44, 7,65,
3339 47,33,67,67,48,32,67,67,67,67,
3340 67,67,67,67,67,67,67,67,67,67
3341 };
3342
3343 /*The number of Reed-Solomon blocks for each version and error correction
3344 level.*/
3345 static const unsigned char QR_RS_NBLOCKS[40][4]={
3346 { 1, 1, 1, 1},{ 1, 1, 1, 1},{ 1, 1, 2, 2},{ 1, 2, 2, 4},
3347 { 1, 2, 4, 4},{ 2, 4, 4, 4},{ 2, 4, 6, 5},{ 2, 4, 6, 6},
3348 { 2, 5, 8, 8},{ 4, 5, 8, 8},{ 4, 5, 8,11},{ 4, 8,10,11},
3349 { 4, 9,12,16},{ 4, 9,16,16},{ 6,10,12,18},{ 6,10,17,16},
3350 { 6,11,16,19},{ 6,13,18,21},{ 7,14,21,25},{ 8,16,20,25},
3351 { 8,17,23,25},{ 9,17,23,34},{ 9,18,25,30},{10,20,27,32},
3352 {12,21,29,35},{12,23,34,37},{12,25,34,40},{13,26,35,42},
3353 {14,28,38,45},{15,29,40,48},{16,31,43,51},{17,33,45,54},
3354 {18,35,48,57},{19,37,51,60},{19,38,53,63},{20,40,56,66},
3355 {21,43,59,70},{22,45,62,74},{24,47,65,77},{25,49,68,81}
3356 };
3357
3358 /*Attempts to fully decode a QR code.
3359 _qrdata: Returns the parsed code data.
3360 _gf: Used for Reed-Solomon error correction.
3361 _ul_pos: The location of the UL finder pattern.
3362 _ur_pos: The location of the UR finder pattern.
3363 _dl_pos: The location of the DL finder pattern.
3364 _version: The (decoded) version number.
3365 _fmt_info: The decoded format info.
3366 _img: The binary input image.
3367 _width: The width of the input image.
3368 _height: The height of the input image.
3369 Return: 0 on success, or a negative value on error.*/
qr_code_decode(qr_code_data * _qrdata,const rs_gf256 * _gf,const qr_point _ul_pos,const qr_point _ur_pos,const qr_point _dl_pos,int _version,int _fmt_info,const unsigned char * _img,int _width,int _height)3370 static int qr_code_decode(qr_code_data *_qrdata,const rs_gf256 *_gf,
3371 const qr_point _ul_pos,const qr_point _ur_pos,const qr_point _dl_pos,
3372 int _version,int _fmt_info,
3373 const unsigned char *_img,int _width,int _height){
3374 qr_sampling_grid grid;
3375 unsigned *data_bits;
3376 unsigned char **blocks;
3377 unsigned char *block_data;
3378 int nblocks;
3379 int nshort_blocks;
3380 int ncodewords;
3381 int block_sz;
3382 int ecc_level;
3383 int ndata;
3384 int npar;
3385 int dim;
3386 int ret;
3387 int i;
3388 /*Read the bits out of the image.*/
3389 qr_sampling_grid_init(&grid,_version,_ul_pos,_ur_pos,_dl_pos,_qrdata->bbox,
3390 _img,_width,_height);
3391 #if defined(QR_DEBUG)
3392 qr_sampling_grid_dump(&grid,_version,_img,_width,_height);
3393 #endif
3394 dim=17+(_version<<2);
3395 data_bits=(unsigned *)malloc(
3396 dim*(dim+QR_INT_BITS-1>>QR_INT_LOGBITS)*sizeof(*data_bits));
3397 qr_sampling_grid_sample(&grid,data_bits,dim,_fmt_info,_img,_width,_height);
3398 /*Group those bits into Reed-Solomon codewords.*/
3399 ecc_level=(_fmt_info>>3)^1;
3400 nblocks=QR_RS_NBLOCKS[_version-1][ecc_level];
3401 npar=*(QR_RS_NPAR_VALS+QR_RS_NPAR_OFFS[_version-1]+ecc_level);
3402 ncodewords=qr_code_ncodewords(_version);
3403 block_sz=ncodewords/nblocks;
3404 nshort_blocks=nblocks-(ncodewords%nblocks);
3405 blocks=(unsigned char **)malloc(nblocks*sizeof(*blocks));
3406 block_data=(unsigned char *)malloc(ncodewords*sizeof(*block_data));
3407 blocks[0]=block_data;
3408 for(i=1;i<nblocks;i++)blocks[i]=blocks[i-1]+block_sz+(i>nshort_blocks);
3409 qr_samples_unpack(blocks,nblocks,block_sz-npar,nshort_blocks,
3410 data_bits,grid.fpmask,dim);
3411 qr_sampling_grid_clear(&grid);
3412 free(blocks);
3413 free(data_bits);
3414 /*Perform the error correction.*/
3415 ndata=0;
3416 ncodewords=0;
3417 ret=0;
3418 for(i=0;i<nblocks;i++){
3419 int block_szi;
3420 int ndatai;
3421 block_szi=block_sz+(i>=nshort_blocks);
3422 if(rs_correct(_gf,QR_M0,block_data+ncodewords,block_szi,npar,NULL,0)<0){
3423 ret=-1;
3424 break;
3425 }
3426 ndatai=block_szi-npar;
3427 memmove(block_data+ndata,block_data+ncodewords,ndatai*sizeof(*block_data));
3428 ncodewords+=block_szi;
3429 ndata+=ndatai;
3430 }
3431 /*Parse the corrected bitstream.*/
3432 if(ret>=0){
3433 ret=qr_code_data_parse(_qrdata,_version,block_data,ndata);
3434 /*We could return any partially decoded data, but then we'd have to have
3435 API support for that; a mode ignoring ECC errors might also be useful.*/
3436 if(ret<0)qr_code_data_clear(_qrdata);
3437 _qrdata->version=_version;
3438 _qrdata->ecc_level=ecc_level;
3439 }
3440 free(block_data);
3441 return ret;
3442 }
3443
3444 /*Searches for an arrangement of these three finder centers that yields a valid
3445 configuration.
3446 _c: On input, the three finder centers to consider in any order.
3447 Return: The detected version number, or a negative value on error.*/
qr_reader_try_configuration(qr_reader * _reader,qr_code_data * _qrdata,const unsigned char * _img,int _width,int _height,qr_finder_center * _c[3])3448 static int qr_reader_try_configuration(qr_reader *_reader,
3449 qr_code_data *_qrdata,const unsigned char *_img,int _width,int _height,
3450 qr_finder_center *_c[3]){
3451 int ci[7];
3452 unsigned maxd;
3453 int ccw;
3454 int i0;
3455 int i;
3456 /*Sort the points in counter-clockwise order.*/
3457 ccw=qr_point_ccw(_c[0]->pos,_c[1]->pos,_c[2]->pos);
3458 /*Colinear points can't be the corners of a quadrilateral.*/
3459 if(!ccw)return -1;
3460 /*Include a few extra copies of the cyclical list to avoid mods.*/
3461 ci[6]=ci[3]=ci[0]=0;
3462 ci[4]=ci[1]=1+(ccw<0);
3463 ci[5]=ci[2]=2-(ccw<0);
3464 /*Assume the points farthest from each other are the opposite corners, and
3465 find the top-left point.*/
3466 maxd=qr_point_distance2(_c[1]->pos,_c[2]->pos);
3467 i0=0;
3468 for(i=1;i<3;i++){
3469 unsigned d;
3470 d=qr_point_distance2(_c[ci[i+1]]->pos,_c[ci[i+2]]->pos);
3471 if(d>maxd){
3472 i0=i;
3473 maxd=d;
3474 }
3475 }
3476 /*However, try all three possible orderings, just to be sure (a severely
3477 skewed projection could move opposite corners closer than adjacent).*/
3478 for(i=i0;i<i0+3;i++){
3479 qr_aff aff;
3480 qr_hom hom;
3481 qr_finder ul;
3482 qr_finder ur;
3483 qr_finder dl;
3484 int res;
3485 int ur_version;
3486 int dl_version;
3487 int fmt_info;
3488 ul.c=_c[ci[i]];
3489 ur.c=_c[ci[i+1]];
3490 dl.c=_c[ci[i+2]];
3491 /*Estimate the module size and version number from the two opposite corners.
3492 The module size is not constant in the image, so we compute an affine
3493 projection from the three points we have to a square domain, and
3494 estimate it there.
3495 Although it should be the same along both axes, we keep separate
3496 estimates to account for any remaining projective distortion.*/
3497 res=QR_INT_BITS-2-QR_FINDER_SUBPREC-qr_ilog(QR_MAXI(_width,_height)-1);
3498 qr_aff_init(&aff,ul.c->pos,ur.c->pos,dl.c->pos,res);
3499 qr_aff_unproject(ur.o,&aff,ur.c->pos[0],ur.c->pos[1]);
3500 qr_finder_edge_pts_aff_classify(&ur,&aff);
3501 if(qr_finder_estimate_module_size_and_version(&ur,1<<res,1<<res)<0)continue;
3502 qr_aff_unproject(dl.o,&aff,dl.c->pos[0],dl.c->pos[1]);
3503 qr_finder_edge_pts_aff_classify(&dl,&aff);
3504 if(qr_finder_estimate_module_size_and_version(&dl,1<<res,1<<res)<0)continue;
3505 /*If the estimated versions are significantly different, reject the
3506 configuration.*/
3507 if(abs(ur.eversion[1]-dl.eversion[0])>QR_LARGE_VERSION_SLACK)continue;
3508 qr_aff_unproject(ul.o,&aff,ul.c->pos[0],ul.c->pos[1]);
3509 qr_finder_edge_pts_aff_classify(&ul,&aff);
3510 if(qr_finder_estimate_module_size_and_version(&ul,1<<res,1<<res)<0||
3511 abs(ul.eversion[1]-ur.eversion[1])>QR_LARGE_VERSION_SLACK||
3512 abs(ul.eversion[0]-dl.eversion[0])>QR_LARGE_VERSION_SLACK){
3513 continue;
3514 }
3515 #if defined(QR_DEBUG)
3516 qr_finder_dump_aff_undistorted(&ul,&ur,&dl,&aff,_img,_width,_height);
3517 #endif
3518 /*If we made it this far, upgrade the affine homography to a full
3519 homography.*/
3520 if(qr_hom_fit(&hom,&ul,&ur,&dl,_qrdata->bbox,&aff,
3521 &_reader->isaac,_img,_width,_height)<0){
3522 continue;
3523 }
3524 qr_hom_unproject(ul.o,&hom,ul.c->pos[0],ul.c->pos[1]);
3525 qr_hom_unproject(ur.o,&hom,ur.c->pos[0],ur.c->pos[1]);
3526 qr_hom_unproject(dl.o,&hom,dl.c->pos[0],dl.c->pos[1]);
3527 qr_finder_edge_pts_hom_classify(&ur,&hom);
3528 if(qr_finder_estimate_module_size_and_version(&ur,
3529 ur.o[0]-ul.o[0],ur.o[0]-ul.o[0])<0){
3530 continue;
3531 }
3532 qr_finder_edge_pts_hom_classify(&dl,&hom);
3533 if(qr_finder_estimate_module_size_and_version(&dl,
3534 dl.o[1]-ul.o[1],dl.o[1]-ul.o[1])<0){
3535 continue;
3536 }
3537 #if defined(QR_DEBUG)
3538 qr_finder_dump_hom_undistorted(&ul,&ur,&dl,&hom,_img,_width,_height);
3539 #endif
3540 /*If we have a small version (less than 7), there's no encoded version
3541 information.
3542 If the estimated version on the two corners matches and is sufficiently
3543 small, we assume this is the case.*/
3544 if(ur.eversion[1]==dl.eversion[0]&&ur.eversion[1]<7){
3545 /*We used to do a whole bunch of extra geometric checks for small
3546 versions, because with just an affine correction, it was fairly easy
3547 to estimate two consistent module sizes given a random configuration.
3548 However, now that we're estimating a full homography, these appear to
3549 be unnecessary.*/
3550 #if 0
3551 static const signed char LINE_TESTS[12][6]={
3552 /*DL left, UL > 0, UR > 0*/
3553 {2,0,0, 1,1, 1},
3554 /*DL right, UL > 0, UR < 0*/
3555 {2,1,0, 1,1,-1},
3556 /*UR top, UL > 0, DL > 0*/
3557 {1,2,0, 1,2, 1},
3558 /*UR bottom, UL > 0, DL < 0*/
3559 {1,3,0, 1,2,-1},
3560 /*UR left, DL < 0, UL < 0*/
3561 {1,0,2,-1,0,-1},
3562 /*UR right, DL > 0, UL > 0*/
3563 {1,1,2, 1,0, 1},
3564 /*DL top, UR < 0, UL < 0*/
3565 {2,2,1,-1,0,-1},
3566 /*DL bottom, UR > 0, UL > 0*/
3567 {2,3,1, 1,0, 1},
3568 /*UL left, DL > 0, UR > 0*/
3569 {0,0,2, 1,1, 1},
3570 /*UL right, DL > 0, UR < 0*/
3571 {0,1,2, 1,1,-1},
3572 /*UL top, UR > 0, DL > 0*/
3573 {0,2,1, 1,2, 1},
3574 /*UL bottom, UR > 0, DL < 0*/
3575 {0,3,1, 1,2,-1}
3576 };
3577 qr_finder *f[3];
3578 int j;
3579 /*Start by decoding the format information.
3580 This is cheap, but unlikely to reject invalid configurations.
3581 56.25% of all bitstrings are valid, and we mix and match several pieces
3582 until we find a valid combination, so our real chances of finding a
3583 valid codeword in random bits are even higher.*/
3584 fmt_info=qr_finder_fmt_info_decode(&ul,&ur,&dl,&aff,_img,_width,_height);
3585 if(fmt_info<0)continue;
3586 /*Now we fit lines to the edges of each finder pattern and check to make
3587 sure the centers of the other finder patterns lie on the proper side.*/
3588 f[0]=&ul;
3589 f[1]=&ur;
3590 f[2]=&dl;
3591 for(j=0;j<12;j++){
3592 const signed char *t;
3593 qr_line l0;
3594 int *p;
3595 t=LINE_TESTS[j];
3596 qr_finder_ransac(f[t[0]],&aff,&_reader->isaac,t[1]);
3597 /*We may not have enough points to fit a line accurately here.
3598 If not, we just skip the test.*/
3599 if(qr_line_fit_finder_edge(l0,f[t[0]],t[1],res)<0)continue;
3600 p=f[t[2]]->c->pos;
3601 if(qr_line_eval(l0,p[0],p[1])*t[3]<0)break;
3602 p=f[t[4]]->c->pos;
3603 if(qr_line_eval(l0,p[0],p[1])*t[5]<0)break;
3604 }
3605 if(j<12)continue;
3606 /*All tests passed.*/
3607 #endif
3608 ur_version=ur.eversion[1];
3609 }
3610 else{
3611 /*If the estimated versions are significantly different, reject the
3612 configuration.*/
3613 if(abs(ur.eversion[1]-dl.eversion[0])>QR_LARGE_VERSION_SLACK)continue;
3614 /*Otherwise we try to read the actual version data from the image.
3615 If the real version is not sufficiently close to our estimated version,
3616 then we assume there was an unrecoverable decoding error (so many bit
3617 errors we were within 3 errors of another valid code), and throw that
3618 value away.
3619 If no decoded version could be sufficiently close, we don't even try.*/
3620 if(ur.eversion[1]>=7-QR_LARGE_VERSION_SLACK){
3621 ur_version=qr_finder_version_decode(&ur,&hom,_img,_width,_height,0);
3622 if(abs(ur_version-ur.eversion[1])>QR_LARGE_VERSION_SLACK)ur_version=-1;
3623 }
3624 else ur_version=-1;
3625 if(dl.eversion[0]>=7-QR_LARGE_VERSION_SLACK){
3626 dl_version=qr_finder_version_decode(&dl,&hom,_img,_width,_height,1);
3627 if(abs(dl_version-dl.eversion[0])>QR_LARGE_VERSION_SLACK)dl_version=-1;
3628 }
3629 else dl_version=-1;
3630 /*If we got at least one valid version, or we got two and they match,
3631 then we found a valid configuration.*/
3632 if(ur_version>=0){
3633 if(dl_version>=0&&dl_version!=ur_version)continue;
3634 }
3635 else if(dl_version<0)continue;
3636 else ur_version=dl_version;
3637 }
3638 qr_finder_edge_pts_hom_classify(&ul,&hom);
3639 if(qr_finder_estimate_module_size_and_version(&ul,
3640 ur.o[0]-dl.o[0],dl.o[1]-ul.o[1])<0||
3641 abs(ul.eversion[1]-ur.eversion[1])>QR_SMALL_VERSION_SLACK||
3642 abs(ul.eversion[0]-dl.eversion[0])>QR_SMALL_VERSION_SLACK){
3643 continue;
3644 }
3645 fmt_info=qr_finder_fmt_info_decode(&ul,&ur,&dl,&hom,_img,_width,_height);
3646 if(fmt_info<0)continue;
3647 if(qr_code_decode(_qrdata,&_reader->gf,ul.c->pos,ur.c->pos,dl.c->pos,
3648 ur_version,fmt_info,_img,_width,_height)<0){
3649 /*TODO: Maybe somebody flipped the code?
3650 We'd still get a valid version, and probably valid (but incorrect)
3651 format info.
3652 After we've come this far, it should be a simple matter to check.*/
3653 continue;
3654 }
3655 return ur_version;
3656 }
3657 return -1;
3658 }
3659
qr_reader_match_centers(qr_reader * _reader,qr_code_data_list * _qrlist,qr_finder_center * _centers,int _ncenters,const unsigned char * _img,int _width,int _height)3660 void qr_reader_match_centers(qr_reader *_reader,qr_code_data_list *_qrlist,
3661 qr_finder_center *_centers,int _ncenters,
3662 const unsigned char *_img,int _width,int _height){
3663 /*The number of centers should be small, so an O(n^3) exhaustive search of
3664 which ones go together should be reasonable.*/
3665 unsigned char *mark;
3666 int i;
3667 int j;
3668 int k;
3669 mark=(unsigned char *)calloc(_ncenters,sizeof(*mark));
3670 for(i=0;i<_ncenters;i++){
3671 /*TODO: We might be able to accelerate this step significantly by
3672 considering the remaining finder centers in a more intelligent order,
3673 based on the first finder center we just chose.*/
3674 for(j=i+1;!mark[i]&&j<_ncenters;j++){
3675 for(k=j+1;!mark[j]&&k<_ncenters;k++)if(!mark[k]){
3676 qr_finder_center *c[3];
3677 qr_code_data qrdata;
3678 int version;
3679 c[0]=_centers+i;
3680 c[1]=_centers+j;
3681 c[2]=_centers+k;
3682 version=qr_reader_try_configuration(_reader,&qrdata,
3683 _img,_width,_height,c);
3684 if(version>=0){
3685 int ninside;
3686 int l;
3687 /*Add the data to the list.*/
3688 qr_code_data_list_add(_qrlist,&qrdata);
3689 /*Convert the bounding box we're returning to the user to normal
3690 image coordinates.*/
3691 for(l=0;l<4;l++){
3692 _qrlist->qrdata[_qrlist->nqrdata-1].bbox[l][0]>>=QR_FINDER_SUBPREC;
3693 _qrlist->qrdata[_qrlist->nqrdata-1].bbox[l][1]>>=QR_FINDER_SUBPREC;
3694 }
3695 /*Mark these centers as used.*/
3696 mark[i]=mark[j]=mark[k]=1;
3697 /*Find any other finder centers located inside this code.*/
3698 for(l=ninside=0;l<_ncenters;l++)if(!mark[l]){
3699 if(qr_point_ccw(qrdata.bbox[0],qrdata.bbox[1],_centers[l].pos)>=0&&
3700 qr_point_ccw(qrdata.bbox[1],qrdata.bbox[3],_centers[l].pos)>=0&&
3701 qr_point_ccw(qrdata.bbox[3],qrdata.bbox[2],_centers[l].pos)>=0&&
3702 qr_point_ccw(qrdata.bbox[2],qrdata.bbox[0],_centers[l].pos)>=0){
3703 mark[l]=2;
3704 ninside++;
3705 }
3706 }
3707 if(ninside>=3){
3708 /*We might have a "Double QR": a code inside a code.
3709 Copy the relevant centers to a new array and do a search confined
3710 to that subset.*/
3711 qr_finder_center *inside;
3712 inside=(qr_finder_center *)malloc(ninside*sizeof(*inside));
3713 for(l=ninside=0;l<_ncenters;l++){
3714 if(mark[l]==2)*&inside[ninside++]=*&_centers[l];
3715 }
3716 qr_reader_match_centers(_reader,_qrlist,inside,ninside,
3717 _img,_width,_height);
3718 free(inside);
3719 }
3720 /*Mark _all_ such centers used: codes cannot partially overlap.*/
3721 for(l=0;l<_ncenters;l++)if(mark[l]==2)mark[l]=1;
3722 }
3723 }
3724 }
3725 }
3726 free(mark);
3727 }
3728
_zbar_qr_found_line(qr_reader * reader,int dir,const qr_finder_line * line)3729 int _zbar_qr_found_line (qr_reader *reader,
3730 int dir,
3731 const qr_finder_line *line)
3732 {
3733 /* minimally intrusive brute force version */
3734 qr_finder_lines *lines = &reader->finder_lines[dir];
3735
3736 if(lines->nlines >= lines->clines) {
3737 lines->clines *= 2;
3738 lines->lines = realloc(lines->lines,
3739 ++lines->clines * sizeof(*lines->lines));
3740 }
3741
3742 memcpy(lines->lines + lines->nlines++, line, sizeof(*line));
3743
3744 return(0);
3745 }
3746
qr_svg_centers(const qr_finder_center * centers,int ncenters)3747 static inline void qr_svg_centers (const qr_finder_center *centers,
3748 int ncenters)
3749 {
3750 int i, j;
3751 svg_path_start("centers", 1, 0, 0);
3752 for(i = 0; i < ncenters; i++)
3753 svg_path_moveto(SVG_ABS, centers[i].pos[0], centers[i].pos[1]);
3754 svg_path_end();
3755
3756 svg_path_start("edge-pts", 1, 0, 0);
3757 for(i = 0; i < ncenters; i++) {
3758 const qr_finder_center *cen = centers + i;
3759 for(j = 0; j < cen->nedge_pts; j++)
3760 svg_path_moveto(SVG_ABS,
3761 cen->edge_pts[j].pos[0], cen->edge_pts[j].pos[1]);
3762 }
3763 svg_path_end();
3764 }
3765
_zbar_qr_decode(qr_reader * reader,zbar_image_scanner_t * iscn,unsigned width,unsigned height,const unsigned char * data)3766 int _zbar_qr_decode (qr_reader *reader,
3767 zbar_image_scanner_t *iscn,
3768 unsigned width, unsigned height, const unsigned char *data)
3769 {
3770 int nqrdata = 0;
3771 qr_finder_edge_pt *edge_pts = NULL;
3772 qr_finder_center *centers = NULL;
3773
3774 if(reader->finder_lines[0].nlines < 9 ||
3775 reader->finder_lines[1].nlines < 9)
3776 return(0);
3777
3778 svg_group_start("finder", 0, 1. / (1 << QR_FINDER_SUBPREC), 0, 0, 0);
3779
3780 int ncenters = qr_finder_centers_locate(¢ers, &edge_pts, reader, 0, 0);
3781
3782 zprintf(14, "%dx%d finders, %d centers:\n",
3783 reader->finder_lines[0].nlines,
3784 reader->finder_lines[1].nlines,
3785 ncenters);
3786 qr_svg_centers(centers, ncenters);
3787
3788 if(ncenters >= 3) {
3789 void *bin = qr_binarize(data, width, height);
3790
3791 qr_code_data_list qrlist;
3792 qr_code_data_list_init(&qrlist);
3793
3794 qr_reader_match_centers(reader, &qrlist, centers, ncenters,
3795 bin, width, height);
3796
3797 if(qrlist.nqrdata > 0)
3798 nqrdata = qr_code_data_list_extract_text(&qrlist, iscn, width, height);
3799
3800 qr_code_data_list_clear(&qrlist);
3801 free(bin);
3802 }
3803 svg_group_end();
3804
3805 if(centers)
3806 free(centers);
3807 if(edge_pts)
3808 free(edge_pts);
3809 return(nqrdata);
3810 }
3811