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