| 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
| Branch | True | False | Total |
| for (v = QR_MIN_VERSION; v <= QR_MAX_VERSION; v++) |
1331 |
5 |
1336 |
|
| 120 |
1331 |
▶ | if (qr_capacity(v, ecc) >= len) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (r = -1; r <= 7; r++) { |
9855 |
1095 |
10950 |
|
| 145 |
98550 |
▶ | for (c = -1; c <= 7; c++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (c = -1; c <= 7; c++) { |
88695 |
9855 |
98550 |
|
| 146 |
88695 |
▶ | int inner = (r >= 2 && r <= 4 && c >= 2 && c <= 4); |
Branch: 4 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| (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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (r = -2; r <= 2; r++) |
7165 |
1433 |
8598 |
|
| 159 |
42990 |
▶ | for (c = -2; c <= 2; c++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (c = -2; c <= 2; c++) { |
35825 |
7165 |
42990 |
|
| 160 |
63052 |
▶ | int dark = (r == 0 && c == 0) || |
Branch: 3 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| (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
| Branch | True | False | Total |
| for (i = 0; i <= 8; i++) { |
3285 |
365 |
3650 |
|
| 181 |
3285 |
▶ | if (i != 6) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (q->version >= 7) { |
171 |
194 |
365 |
|
| 195 |
3249 |
▶ | for (i = 0; i < 18; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 0; a[i]; i++) { |
820 |
365 |
1185 |
|
| 223 |
3168 |
▶ | for (j = 0; a[j]; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| (r == 6 && c >= last) || |
210 |
305 |
515 |
| (r == 6 && c >= last) || |
820 |
918 |
1738 |
|
| 228 |
820 |
▶ | (r >= last && c == 6)) |
Branch: 1 branch
| Branch | True | False | Total |
| (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
| Branch | True | False | Total |
| for (col = size - 1; col > 0; col -= 2) { |
7688 |
365 |
8053 |
|
| 251 |
7688 |
▶ | if (col == 6) |
Branch: 1 branch
| Branch | True | False | Total |
| if (col == 6) |
365 |
7323 |
7688 |
|
| 252 |
365 |
| col = 5; |
| 253 |
|
| |
| 254 |
398304 |
▶ | for (i = 0; i < size; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < size; i++) { |
390616 |
7688 |
398304 |
|
| 255 |
390616 |
▶ | int row = upward ? (size - 1 - i) : i; |
Branch: 1 branch
| Branch | True | False | Total |
| int row = upward ? (size - 1 - i) : i; |
195308 |
195308 |
390616 |
|
| 256 |
|
| |
| 257 |
1171848 |
▶ | for (c = 0; c < 2; c++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (q->fixed[idx]) |
125337 |
655895 |
781232 |
|
| 263 |
125337 |
| continue; |
| 264 |
|
| |
| 265 |
655895 |
| dark = 0; |
| 266 |
655895 |
▶ | if (bit < total) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 0; i < blocks; i++) { |
1627 |
365 |
1992 |
|
| 301 |
1627 |
▶ | int len = (i < g1_blocks) ? g1_data : g2_data; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (j = 0; j < max_data; j++) |
12076 |
365 |
12441 |
|
| 310 |
57302 |
▶ | for (i = 0; i < blocks; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < blocks; i++) |
45226 |
12076 |
57302 |
|
| 311 |
45226 |
▶ | if (j < dlen[i]) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (j = 0; j < ec_len; j++) |
7553 |
365 |
7918 |
|
| 316 |
44950 |
▶ | for (i = 0; i < blocks; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (m = 0; m < 8; m++) { |
2920 |
365 |
3285 |
|
| 385 |
|
| int score; |
| 386 |
|
| |
| 387 |
128848 |
▶ | for (i = 0; i < size; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < size; i++) |
125928 |
2920 |
128848 |
|
| 388 |
6501712 |
▶ | for (j = 0; j < size; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 0; i < size; i++) |
125928 |
2920 |
128848 |
|
| 405 |
6501712 |
▶ | for (j = 0; j < size; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (version == 0) { |
219 |
153 |
372 |
|
| 433 |
219 |
| version = qr_pick_version(len, ecc); |
| 434 |
219 |
▶ | if (version < 0) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 */ |