include/qr/qr_encode.h

filter: Statementstmt 98.9% 180 / 182 Branchbran 96.4% 164 / 170 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 97.7% 344 / 352 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/qr/qr_bits.h ↑ Summary include/qr/qr_gf.h »
1 #ifndef QR_ENCODE_H
2 #define QR_ENCODE_H
3  
4 #include <stdlib.h>
5 #include <string.h>
6  
7 #include "qr/qr_gf.h"
8 #include "qr/qr_bits.h"
9 #include "qr/qr_mask.h"
10  
11 /* qr_encode.h - byte mode QR encoding, versions 1 to 15.
12 *
13 * Byte mode only. An otpauth:// URI is mixed case, which alphanumeric
14 * mode cannot represent at all, so the denser mode is not available and
15 * numeric mode is irrelevant. Adding a mode later is additive: it
16 * changes the header and the capacity check and nothing else.
17 *
18 * Versions stop at 15 because a centre logo forces ECC level H, which
19 * roughly halves capacity - version 10 at H holds 119 bytes and a
20 * typical enrolment URI is 149. Versions 7 and up carry a second
21 * BCH-coded version information block; nothing further changes between
22 * 7 and 15, so the ceiling is a matter of table rows.
23 */
24  
25 #define QR_ECC_L 0
26 #define QR_ECC_M 1
27 #define QR_ECC_Q 2
28 #define QR_ECC_H 3
29  
30 #define QR_MIN_VERSION 1
31 #define QR_MAX_VERSION 15
32 #define QR_MAX_SIZE (17 + 4 * QR_MAX_VERSION) /* 77 */
33 #define QR_MAX_CW 655
34  
35 /* Total codewords per version, data plus error correction. */
36 static const short qr_total_cw[QR_MAX_VERSION + 1] = {
37 0, 26, 44, 70, 100, 134, 172, 196, 242, 292, 346, 404, 466, 532, 581, 655
38 };
39  
40 /* Reed-Solomon block structure, ISO/IEC 18004 Table 9, indexed
41 * [version][ecc] as { ec_per_block, g1_blocks, g1_data, g2_blocks,
42 * g2_data }. Group 2 blocks, where present, hold exactly one more data
43 * codeword than group 1. */
44 static const unsigned char qr_rs[QR_MAX_VERSION + 1][4][5] = {
45 /* v0 unused */
46 { {0,0,0,0,0}, {0,0,0,0,0}, {0,0,0,0,0}, {0,0,0,0,0} },
47 /* v1 */ { { 7,1, 19,0, 0}, {10,1, 16,0, 0}, {13,1, 13,0, 0}, {17,1, 9,0, 0} },
48 /* v2 */ { {10,1, 34,0, 0}, {16,1, 28,0, 0}, {22,1, 22,0, 0}, {28,1, 16,0, 0} },
49 /* v3 */ { {15,1, 55,0, 0}, {26,1, 44,0, 0}, {18,2, 17,0, 0}, {22,2, 13,0, 0} },
50 /* v4 */ { {20,1, 80,0, 0}, {18,2, 32,0, 0}, {26,2, 24,0, 0}, {16,4, 9,0, 0} },
51 /* v5 */ { {26,1,108,0, 0}, {24,2, 43,0, 0}, {18,2, 15,2, 16}, {22,2, 11,2, 12} },
52 /* v6 */ { {18,2, 68,0, 0}, {16,4, 27,0, 0}, {24,4, 19,0, 0}, {28,4, 15,0, 0} },
53 /* v7 */ { {20,2, 78,0, 0}, {18,4, 31,0, 0}, {18,2, 14,4, 15}, {26,4, 13,1, 14} },
54 /* v8 */ { {24,2, 97,0, 0}, {22,2, 38,2, 39}, {22,4, 18,2, 19}, {26,4, 14,2, 15} },
55 /* v9 */ { {30,2,116,0, 0}, {22,3, 36,2, 37}, {20,4, 16,4, 17}, {24,4, 12,4, 13} },
56 /* v10 */ { {18,2, 68,2, 69}, {26,4, 43,1, 44}, {24,6, 19,2, 20}, {28,6, 15,2, 16} },
57 /* v11 */ { {20,4, 81,0, 0}, {30,1, 50,4, 51}, {28,4, 22,4, 23}, {24,3, 12,8, 13} },
58 /* v12 */ { {24,2, 92,2, 93}, {22,6, 36,2, 37}, {26,4, 20,6, 21}, {28,7, 14,4, 15} },
59 /* v13 */ { {26,4,107,0, 0}, {22,8, 37,1, 38}, {24,8, 20,4, 21}, {22,12,11,4, 12} },
60 /* v14 */ { {30,3,115,1,116}, {24,4, 40,5, 41}, {20,11,16,5, 17}, {24,11,12,5, 13} },
61 /* v15 */ { {22,5, 87,1, 88}, {24,5, 41,5, 42}, {30,5, 24,7, 25}, {24,11,12,7, 13} }
62 };
63  
64 /* Alignment pattern centre coordinates, zero-terminated. Patterns go at
65 * every combination of these, minus the three that would land on a
66 * finder.
67 *
68 * Worth noticing for anything that overlays the centre of a symbol:
69 * versions with an odd number of centres (7 to 13) place one exactly in
70 * the middle, and versions with an even number (2 to 6, 14, 15) do not. */
71 static const unsigned char qr_align[QR_MAX_VERSION + 1][8] = {
72 {0}, /* v0 unused */
73 {0}, /* v1 none */
74 {6,18,0}, /* v2 */
75 {6,22,0}, /* v3 */
76 {6,26,0}, /* v4 */
77 {6,30,0}, /* v5 */
78 {6,34,0}, /* v6 */
79 {6,22,38,0}, /* v7 */
80 {6,24,42,0}, /* v8 */
81 {6,26,46,0}, /* v9 */
82 {6,28,50,0}, /* v10 */
83 {6,30,54,0}, /* v11 */
84 {6,32,58,0}, /* v12 */
85 {6,34,62,0}, /* v13 */
86 {6,26,46,66,0}, /* v14 */
87 {6,26,48,70,0} /* v15 */
88 };
89  
90 typedef struct {
91 int version;
92 int ecc;
93 int mask;
94 int size;
95 unsigned char mod[QR_MAX_SIZE * QR_MAX_SIZE]; /* 1 = dark */
96 unsigned char fixed[QR_MAX_SIZE * QR_MAX_SIZE]; /* 1 = function pattern */
97 } qr_matrix;
98  
99 /* Data codewords available at this version and ECC level. */
100 2020 static int qr_data_cw(int version, int ecc)
101 {
102 2020 const unsigned char *r = qr_rs[version][ecc];
103 2020 return r[1] * r[2] + r[3] * r[4];
104 }
105  
106 /* Byte mode payload capacity: the data codewords less the 4-bit mode
107 * indicator and the character count. */
108 1655 static int qr_capacity(int version, int ecc)
109 {
110 1655 int bits = qr_data_cw(version, ecc) * 8;
111 1655 return (bits - 4 - qr_bits_count_len(version)) / 8;
112 }
113  
114 /* Smallest version holding `len` bytes at this ECC level, or -1. */
115 219 static int qr_pick_version(int len, int ecc)
116 {
117 int v;
118  
119 1336 ▶ for (v = QR_MIN_VERSION; v <= QR_MAX_VERSION; v++)
Branch: 1 branch
BranchTrueFalseTotal
for (v = QR_MIN_VERSION; v <= QR_MAX_VERSION; v++) 1331 5 1336
120 1331 ▶ if (qr_capacity(v, ecc) >= len)
Branch: 1 branch
BranchTrueFalseTotal
if (qr_capacity(v, ecc) >= len) 214 1117 1331
121 214 return v;
122  
123 5 return -1;
124 }
125  
126 /* --- function patterns --------------------------------------------------- */
127  
128 259199 static void qr_set(qr_matrix *q, int row, int col, int dark, int fixed)
129 {
130 259199 ▶ if (row < 0 || col < 0 || row >= q->size || col >= q->size)
Branch: 4 branches
BranchTrueFalseTotal
if (row < 0 || col < 0 || row >= q->size || col >= q->size) 252629 6570 259199
if (row < 0 || col < 0 || row >= q->size || col >= q->size) 246424 6205 252629
if (row < 0 || col < 0 || row >= q->size || col >= q->size) 243504 2920 246424
if (row < 0 || col < 0 || row >= q->size || col >= q->size) 2920 240584 243504
131 18615 return;
132 240584 ▶ q->mod[row * q->size + col] = (unsigned char)(dark ? 1 : 0);
Branch: 1 branch
BranchTrueFalseTotal
q->mod[row * q->size + col] = (unsigned char)(dark ? 1 : 0); 120271 120313 240584
133 240584 ▶ q->fixed[row * q->size + col] = (unsigned char)(fixed ? 1 : 0);
Branch: 1 branch
BranchTrueFalseTotal
q->fixed[row * q->size + col] = (unsigned char)(fixed ? 1 : 0); 240584 0 240584
134 }
135  
136 /* A finder pattern and its separator, anchored at the given top-left of
137 * the 7x7 finder. The separator is the ring of light modules outside it,
138 * which is written one module wider in every direction and simply falls
139 * off the edge where the finder is against a border. */
140 1095 static void qr_place_finder(qr_matrix *q, int top, int left)
141 {
142 int r, c;
143  
144 10950 ▶ for (r = -1; r <= 7; r++) {
Branch: 1 branch
BranchTrueFalseTotal
for (r = -1; r <= 7; r++) { 9855 1095 10950
145 98550 ▶ for (c = -1; c <= 7; c++) {
Branch: 1 branch
BranchTrueFalseTotal
for (c = -1; c <= 7; c++) { 88695 9855 98550
146 88695 ▶ int inner = (r >= 2 && r <= 4 && c >= 2 && c <= 4);
Branch: 4 branches
BranchTrueFalseTotal
int inner = (r >= 2 && r <= 4 && c >= 2 && c <= 4); 59130 29565 88695
int inner = (r >= 2 && r <= 4 && c >= 2 && c <= 4); 29565 29565 59130
int inner = (r >= 2 && r <= 4 && c >= 2 && c <= 4); 19710 9855 29565
int inner = (r >= 2 && r <= 4 && c >= 2 && c <= 4); 9855 9855 19710
147 134685 ▶ int ring = (r >= 0 && r <= 6 && c >= 0 && c <= 6) &&
Branch: 5 branches
BranchTrueFalseTotal
int ring = (r >= 0 && r <= 6 && c >= 0 && c <= 6) && 78840 9855 88695
int ring = (r >= 0 && r <= 6 && c >= 0 && c <= 6) && 68985 9855 78840
int ring = (r >= 0 && r <= 6 && c >= 0 && c <= 6) && 61320 7665 68985
int ring = (r >= 0 && r <= 6 && c >= 0 && c <= 6) && 53655 7665 61320
int ring = (r >= 0 && r <= 6 && c >= 0 && c <= 6) && 45990 7665 53655
148 45990 ▶ (r == 0 || r == 6 || c == 0 || c == 6);
Branch: 3 branches
BranchTrueFalseTotal
(r == 0 || r == 6 || c == 0 || c == 6); 38325 7665 45990
(r == 0 || r == 6 || c == 0 || c == 6); 32850 5475 38325
(r == 0 || r == 6 || c == 0 || c == 6); 5475 27375 32850
149 88695 ▶ qr_set(q, top + r, left + c, inner || ring, 1);
Branch: 2 branches
BranchTrueFalseTotal
qr_set(q, top + r, left + c, inner || ring, 1); 78840 9855 88695
qr_set(q, top + r, left + c, inner || ring, 1); 26280 52560 78840
150 }
151 }
152 1095 }
153  
154 1433 static void qr_place_alignment(qr_matrix *q, int row, int col)
155 {
156 int r, c;
157  
158 8598 ▶ for (r = -2; r <= 2; r++)
Branch: 1 branch
BranchTrueFalseTotal
for (r = -2; r <= 2; r++) 7165 1433 8598
159 42990 ▶ for (c = -2; c <= 2; c++) {
Branch: 1 branch
BranchTrueFalseTotal
for (c = -2; c <= 2; c++) { 35825 7165 42990
160 63052 ▶ int dark = (r == 0 && c == 0) ||
Branch: 3 branches
BranchTrueFalseTotal
int dark = (r == 0 && c == 0) || 7165 28660 35825
int dark = (r == 0 && c == 0) || 5732 1433 7165
int dark = (r == 0 && c == 0) || 27227 7165 34392
161 27227 ▶ (r == -2 || r == 2 || c == -2 || c == 2);
Branch: 3 branches
BranchTrueFalseTotal
(r == -2 || r == 2 || c == -2 || c == 2); 20062 7165 27227
(r == -2 || r == 2 || c == -2 || c == 2); 15763 4299 20062
(r == -2 || r == 2 || c == -2 || c == 2); 4299 11464 15763
162 35825 qr_set(q, row + r, col + c, dark, 1);
163 }
164 1433 }
165  
166 /* Reserve, without writing, the modules the format and version blocks
167 * will occupy. They have to be off-limits to the data walk before it
168 * runs, but their contents depend on the mask, which is not chosen
169 * until after the data is placed. */
170 365 static void qr_reserve_info(qr_matrix *q)
171 {
172 365 int size = q->size, i;
173  
174 /* Row 8 and column 8, except where they cross the timing patterns:
175 * the format block skips (8,6) and (6,8) precisely because those
176 * modules belong to the timing pattern. Reserving them here would
177 * blank two timing modules - which still produces a symbol that
178 * looks right at a glance, and a timing pattern is the one thing a
179 * decoder cannot recover by error correction. */
180 3650 ▶ for (i = 0; i <= 8; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i <= 8; i++) { 3285 365 3650
181 3285 ▶ if (i != 6) {
Branch: 1 branch
BranchTrueFalseTotal
if (i != 6) { 2920 365 3285
182 2920 qr_set(q, 8, i, 0, 1);
183 2920 qr_set(q, i, 8, 0, 1);
184 }
185 }
186 3285 ▶ for (i = 0; i < 8; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 8; i++) { 2920 365 3285
187 2920 qr_set(q, 8, size - 1 - i, 0, 1);
188 2920 qr_set(q, size - 1 - i, 8, 0, 1);
189 }
190  
191 /* the dark module, which is a constant rather than format data */
192 365 qr_set(q, size - 8, 8, 1, 1);
193  
194 365 ▶ if (q->version >= 7) {
Branch: 1 branch
BranchTrueFalseTotal
if (q->version >= 7) { 171 194 365
195 3249 ▶ for (i = 0; i < 18; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 18; i++) { 3078 171 3249
196 3078 qr_set(q, i / 3, size - 11 + i % 3, 0, 1);
197 3078 qr_set(q, size - 11 + i % 3, i / 3, 0, 1);
198 }
199 }
200 365 }
201  
202 365 static void qr_place_function_patterns(qr_matrix *q)
203 {
204 365 int size = q->size, i, j;
205 365 const unsigned char *a = qr_align[q->version];
206  
207 365 memset(q->mod, 0, (size_t)(size * size));
208 365 memset(q->fixed, 0, (size_t)(size * size));
209  
210 365 qr_place_finder(q, 0, 0);
211 365 qr_place_finder(q, 0, size - 7);
212 365 qr_place_finder(q, size - 7, 0);
213  
214 /* timing patterns: row 6 and column 6, dark on even coordinates */
215 10266 ▶ for (i = 8; i < size - 8; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 8; i < size - 8; i++) { 9901 365 10266
216 9901 qr_set(q, 6, i, (i % 2) == 0, 1);
217 9901 qr_set(q, i, 6, (i % 2) == 0, 1);
218 }
219  
220 /* alignment patterns at every pair of centres except the three that
221 * would sit on a finder */
222 1185 ▶ for (i = 0; a[i]; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; a[i]; i++) { 820 365 1185
223 3168 ▶ for (j = 0; a[j]; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; a[j]; j++) { 2348 820 3168
224 2348 int r = a[i], c = a[j];
225 2348 int last = size - 7;
226 2348 ▶ if ((r == 6 && c == 6) ||
Branch: 3 branches
BranchTrueFalseTotal
if ((r == 6 && c == 6) || 820 1528 2348
if ((r == 6 && c == 6) || 515 305 820
if ((r == 6 && c == 6) || 515 1528 2043
227 2043 ▶ (r == 6 && c >= last) ||
Branch: 2 branches
BranchTrueFalseTotal
(r == 6 && c >= last) || 210 305 515
(r == 6 && c >= last) || 820 918 1738
228 820 ▶ (r >= last && c == 6))
Branch: 1 branch
BranchTrueFalseTotal
(r >= last && c == 6)) 305 515 820
229 915 continue;
230 1433 qr_place_alignment(q, r, c);
231 }
232 }
233  
234 365 qr_reserve_info(q);
235 365 }
236  
237 /* --- data placement ------------------------------------------------------ */
238  
239 /* The zigzag walk: two-module-wide columns from the right edge leftward,
240 * alternating upward and downward, right module before left, skipping
241 * every module already claimed by a function pattern. Column 6 is
242 * skipped entirely because the vertical timing pattern runs down it. */
243 365 static void qr_place_data(qr_matrix *q, const unsigned char *cw, int cw_len)
244 {
245 365 int size = q->size;
246 365 int bit = 0, total = cw_len * 8;
247 int col, i, c;
248 365 int upward = 1;
249  
250 8053 ▶ for (col = size - 1; col > 0; col -= 2) {
Branch: 1 branch
BranchTrueFalseTotal
for (col = size - 1; col > 0; col -= 2) { 7688 365 8053
251 7688 ▶ if (col == 6)
Branch: 1 branch
BranchTrueFalseTotal
if (col == 6) 365 7323 7688
252 365 col = 5;
253  
254 398304 ▶ for (i = 0; i < size; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < size; i++) { 390616 7688 398304
255 390616 ▶ int row = upward ? (size - 1 - i) : i;
Branch: 1 branch
BranchTrueFalseTotal
int row = upward ? (size - 1 - i) : i; 195308 195308 390616
256  
257 1171848 ▶ for (c = 0; c < 2; c++) {
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c < 2; c++) { 781232 390616 1171848
258 781232 int cc = col - c;
259 781232 int idx = row * size + cc;
260 int dark;
261  
262 781232 ▶ if (q->fixed[idx])
Branch: 1 branch
BranchTrueFalseTotal
if (q->fixed[idx]) 125337 655895 781232
263 125337 continue;
264  
265 655895 dark = 0;
266 655895 ▶ if (bit < total)
Branch: 1 branch
BranchTrueFalseTotal
if (bit < total) 654840 1055 655895
267 654840 dark = (cw[bit >> 3] >> (7 - (bit & 7))) & 1;
268 655895 bit++;
269  
270 655895 q->mod[idx] = (unsigned char)dark;
271 }
272 }
273 7688 upward = !upward;
274 }
275 365 }
276  
277 /* --- error correction ---------------------------------------------------- */
278  
279 /* Split the data codewords into blocks, error-correct each, and
280 * interleave. The interleave is what makes a contiguous burst of damage
281 * survivable: consecutive modules on the symbol belong to different
282 * blocks, so a blot covering one region spreads its damage evenly rather
283 * than destroying one block outright. It is also what makes a centre
284 * logo work. */
285 365 static int qr_build_codewords(int version, int ecc,
286 const unsigned char *data,
287 unsigned char *out)
288 {
289 365 const unsigned char *r = qr_rs[version][ecc];
290 365 int ec_len = r[0];
291 365 int g1_blocks = r[1], g1_data = r[2];
292 365 int g2_blocks = r[3], g2_data = r[4];
293 365 int blocks = g1_blocks + g2_blocks;
294 365 int max_data = g2_data > g1_data ? g2_data : g1_data;
295 unsigned char ecbuf[64][QR_MAX_EC];
296 const unsigned char *dstart[64];
297 int dlen[64];
298 365 int i, j, pos = 0, n = 0;
299  
300 1992 ▶ for (i = 0; i < blocks; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < blocks; i++) { 1627 365 1992
301 1627 ▶ int len = (i < g1_blocks) ? g1_data : g2_data;
Branch: 1 branch
BranchTrueFalseTotal
int len = (i < g1_blocks) ? g1_data : g2_data; 1106 521 1627
302 1627 dstart[i] = data + pos;
303 1627 dlen[i] = len;
304 1627 pos += len;
305 1627 qr_rs_encode(dstart[i], len, ec_len, ecbuf[i]);
306 }
307  
308 /* data codewords, column-major across blocks */
309 12441 ▶ for (j = 0; j < max_data; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < max_data; j++) 12076 365 12441
310 57302 ▶ for (i = 0; i < blocks; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < blocks; i++) 45226 12076 57302
311 45226 ▶ if (j < dlen[i])
Branch: 1 branch
BranchTrueFalseTotal
if (j < dlen[i]) 44458 768 45226
312 44458 out[n++] = dstart[i][j];
313  
314 /* then the error correction codewords, same way */
315 7918 ▶ for (j = 0; j < ec_len; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < ec_len; j++) 7553 365 7918
316 44950 ▶ for (i = 0; i < blocks; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < blocks; i++) 37397 7553 44950
317 37397 out[n++] = ecbuf[i][j];
318  
319 365 return n;
320 }
321  
322 /* --- masking and the information blocks ---------------------------------- */
323  
324 /* The fifteen format bits, twice.
325 *
326 * Bit 14 is the MSB and it goes FIRST, at (8,0). Writing this the other
327 * way round - bit 0 at (8,0) - produces a symbol that is perfectly
328 * self-consistent and that no scanner on earth can read, because the
329 * format block is the one field a decoder must interpret before it can
330 * do anything else. Verified against a known-good symbol rather than
331 * from memory: both copies match at Hamming distance 0 MSB-first and 3
332 * LSB-first.
333 *
334 * The second copy is seven modules up the right-hand column and eight
335 * along the bottom row - not eight and seven. The eighth position down
336 * that column is the dark module, so an off-by-one there silently loses
337 * bit 7 when the dark module is written over it. */
338 2920 static void qr_write_format(qr_matrix *q, int mask)
339 {
340 static const unsigned char c1r[15] =
341 { 8,8,8,8,8,8,8,8,7,5,4,3,2,1,0 };
342 static const unsigned char c1c[15] =
343 { 0,1,2,3,4,5,7,8,8,8,8,8,8,8,8 };
344 2920 unsigned int f = qr_format_bits(q->ecc, mask);
345 2920 int size = q->size, i;
346  
347 46720 ▶ for (i = 0; i < 15; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 15; i++) 43800 2920 46720
348 43800 qr_set(q, c1r[i], c1c[i], (f >> (14 - i)) & 1u, 1);
349  
350 23360 ▶ for (i = 0; i < 7; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 7; i++) 20440 2920 23360
351 20440 qr_set(q, size - 1 - i, 8, (f >> (14 - i)) & 1u, 1);
352 26280 ▶ for (i = 0; i < 8; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 8; i++) 23360 2920 26280
353 23360 qr_set(q, 8, size - 8 + i, (f >> (7 - i)) & 1u, 1);
354  
355 2920 qr_set(q, size - 8, 8, 1, 1);
356 2920 }
357  
358 365 static void qr_write_version(qr_matrix *q)
359 {
360 unsigned int v;
361 365 int size = q->size, i;
362  
363 365 ▶ if (q->version < 7)
Branch: 1 branch
BranchTrueFalseTotal
if (q->version < 7) 194 171 365
364 194 return;
365  
366 171 v = qr_version_bits(q->version);
367 3249 ▶ for (i = 0; i < 18; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 18; i++) { 3078 171 3249
368 3078 int b = (int)((v >> i) & 1u);
369 3078 qr_set(q, i / 3, size - 11 + i % 3, b, 1);
370 3078 qr_set(q, size - 11 + i % 3, i / 3, b, 1);
371 }
372 }
373  
374 /* Apply every mask in turn, score each, keep the best. The format block
375 * has to be written before scoring, because its modules are part of the
376 * symbol the penalty rules see. */
377 365 static void qr_apply_best_mask(qr_matrix *q)
378 {
379 unsigned char best[QR_MAX_SIZE * QR_MAX_SIZE];
380 365 int size = q->size, n = size * size;
381 365 int best_score = -1, best_mask = 0;
382 int m, i, j;
383  
384 3285 ▶ for (m = 0; m < 8; m++) {
Branch: 1 branch
BranchTrueFalseTotal
for (m = 0; m < 8; m++) { 2920 365 3285
385 int score;
386  
387 128848 ▶ for (i = 0; i < size; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < size; i++) 125928 2920 128848
388 6501712 ▶ for (j = 0; j < size; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < size; j++) { 6375784 125928 6501712
389 6375784 int idx = i * size + j;
390 6375784 ▶ if (!q->fixed[idx] && qr_mask_bit(m, i, j))
Branch: 2 branches
BranchTrueFalseTotal
if (!q->fixed[idx] && qr_mask_bit(m, i, j)) 5247160 1128624 6375784
if (!q->fixed[idx] && qr_mask_bit(m, i, j)) 2428993 2818167 5247160
391 2428993 q->mod[idx] ^= 1;
392 }
393  
394 2920 qr_write_format(q, m);
395 2920 score = qr_penalty(q->mod, size);
396  
397 2920 ▶ if (best_score < 0 || score < best_score) {
Branch: 2 branches
BranchTrueFalseTotal
if (best_score < 0 || score < best_score) { 2555 365 2920
if (best_score < 0 || score < best_score) { 477 2078 2555
398 842 best_score = score;
399 842 best_mask = m;
400 842 memcpy(best, q->mod, (size_t)n);
401 }
402  
403 /* undo, ready for the next mask */
404 128848 ▶ for (i = 0; i < size; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < size; i++) 125928 2920 128848
405 6501712 ▶ for (j = 0; j < size; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < size; j++) { 6375784 125928 6501712
406 6375784 int idx = i * size + j;
407 6375784 ▶ if (!q->fixed[idx] && qr_mask_bit(m, i, j))
Branch: 2 branches
BranchTrueFalseTotal
if (!q->fixed[idx] && qr_mask_bit(m, i, j)) 5247160 1128624 6375784
if (!q->fixed[idx] && qr_mask_bit(m, i, j)) 2428993 2818167 5247160
408 2428993 q->mod[idx] ^= 1;
409 }
410 }
411  
412 365 memcpy(q->mod, best, (size_t)n);
413 365 q->mask = best_mask;
414 365 }
415  
416 /* --- the entry point ----------------------------------------------------- */
417  
418 /* Encode `len` bytes at the given ECC level into `q`. Pass version 0 to
419 * choose the smallest that fits. Returns 0 on success, -1 if the payload
420 * does not fit at this level, -2 if the arguments are out of range. */
421 372 static int qr_encode(qr_matrix *q, const unsigned char *data, int len,
422 int ecc, int version)
423 {
424 unsigned char stream[QR_MAX_CW];
425 unsigned char final[QR_MAX_CW];
426 qr_bits bits;
427 int data_cw, n, i;
428  
429 372 ▶ if (ecc < 0 || ecc > 3 || len < 0)
Branch: 3 branches
BranchTrueFalseTotal
if (ecc < 0 || ecc > 3 || len < 0) 372 0 372
if (ecc < 0 || ecc > 3 || len < 0) 372 0 372
if (ecc < 0 || ecc > 3 || len < 0) 0 372 372
430 0 return -2;
431  
432 372 ▶ if (version == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (version == 0) { 219 153 372
433 219 version = qr_pick_version(len, ecc);
434 219 ▶ if (version < 0)
Branch: 1 branch
BranchTrueFalseTotal
if (version < 0) 5 214 219
435 5 return -1;
436 } else {
437 153 ▶ if (version < QR_MIN_VERSION || version > QR_MAX_VERSION)
Branch: 2 branches
BranchTrueFalseTotal
if (version < QR_MIN_VERSION || version > QR_MAX_VERSION) 153 0 153
if (version < QR_MIN_VERSION || version > QR_MAX_VERSION) 0 153 153
438 0 return -2;
439 153 ▶ if (qr_capacity(version, ecc) < len)
Branch: 1 branch
BranchTrueFalseTotal
if (qr_capacity(version, ecc) < len) 2 151 153
440 2 return -1;
441 }
442  
443 365 q->version = version;
444 365 q->ecc = ecc;
445 365 q->size = 17 + 4 * version;
446 365 q->mask = 0;
447  
448 365 data_cw = qr_data_cw(version, ecc);
449  
450 365 qr_bits_init(&bits, stream, data_cw);
451 365 qr_bits_put(&bits, 0x4u, 4); /* byte mode */
452 365 qr_bits_put(&bits, (unsigned int)len, qr_bits_count_len(version));
453 34213 ▶ for (i = 0; i < len; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < len; i++) 33848 365 34213
454 33848 qr_bits_put(&bits, data[i], 8);
455 365 qr_bits_finish(&bits, data_cw);
456  
457 365 n = qr_build_codewords(version, ecc, stream, final);
458  
459 365 qr_place_function_patterns(q);
460 365 qr_place_data(q, final, n);
461 365 qr_apply_best_mask(q);
462 365 qr_write_version(q);
463  
464 365 return 0;
465 }
466  
467 #endif /* QR_ENCODE_H */
« include/qr/qr_bits.h ↑ Summary include/qr/qr_gf.h »