| 1 |
|
| #ifndef QR_MASK_H |
| 2 |
|
| #define QR_MASK_H |
| 3 |
|
| |
| 4 |
|
| /* qr_mask.h - data masking, penalty scoring, and the BCH-coded format |
| 5 |
|
| * and version information blocks. |
| 6 |
|
| * |
| 7 |
|
| * Masking exists because an unmasked symbol can contain long runs of one |
| 8 |
|
| * colour, or accidental copies of the finder pattern, both of which |
| 9 |
|
| * confuse a decoder. All eight masks are applied in turn, each result is |
| 10 |
|
| * scored by four penalty rules, and the lowest score wins. |
| 11 |
|
| * |
| 12 |
|
| * A symbol with a suboptimal mask still scans, which is exactly why the |
| 13 |
|
| * penalty rules need testing against fixtures rather than against "did a |
| 14 |
|
| * decoder read it". A quiet mistake here costs robustness and reports |
| 15 |
|
| * nothing. |
| 16 |
|
| */ |
| 17 |
|
| |
| 18 |
|
| /* Whether module (row, col) is inverted under mask `m`. The eight |
| 19 |
|
| * conditions are fixed by ISO/IEC 18004 Table 10. */ |
| 20 |
10494320 |
| static int qr_mask_bit(int m, int row, int col) |
| 21 |
|
| { |
| 22 |
10494320 |
| switch (m) { |
| 23 |
1311790 |
| case 0: return ((row + col) % 2) == 0; |
| 24 |
1311790 |
| case 1: return (row % 2) == 0; |
| 25 |
1311790 |
| case 2: return (col % 3) == 0; |
| 26 |
1311790 |
| case 3: return ((row + col) % 3) == 0; |
| 27 |
1311790 |
| case 4: return (((row / 2) + (col / 3)) % 2) == 0; |
| 28 |
1311790 |
| case 5: return (((row * col) % 2) + ((row * col) % 3)) == 0; |
| 29 |
1311790 |
| case 6: return (((((row * col) % 2) + ((row * col) % 3)) % 2)) == 0; |
| 30 |
1311790 |
| case 7: return (((((row + col) % 2) + ((row * col) % 3)) % 2)) == 0; |
| 31 |
0 |
| default: return 0; |
| 32 |
|
| } |
| 33 |
|
| } |
| 34 |
|
| |
| 35 |
|
| /* --- penalty rules ------------------------------------------------------- */ |
| 36 |
|
| |
| 37 |
|
| /* Rule 1: runs of five or more same-coloured modules in a row or column |
| 38 |
|
| * score 3, plus 1 for each module past five. */ |
| 39 |
2920 |
| static int qr_penalty_1(const unsigned char *m, int size) |
| 40 |
|
| { |
| 41 |
2920 |
| int total = 0, i, j; |
| 42 |
|
| |
| 43 |
128848 |
▶ | for (i = 0; i < size; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < size; i++) { |
125928 |
2920 |
128848 |
|
| 44 |
125928 |
| int run_h = 1, run_v = 1; |
| 45 |
6375784 |
▶ | for (j = 1; j < size; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (j = 1; j < size; j++) { |
6249856 |
125928 |
6375784 |
|
| 46 |
|
| /* horizontal */ |
| 47 |
6249856 |
▶ | if (m[i * size + j] == m[i * size + j - 1]) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (m[i * size + j] == m[i * size + j - 1]) { |
3169747 |
3080109 |
6249856 |
|
| 48 |
3169747 |
| run_h++; |
| 49 |
|
| } else { |
| 50 |
3080109 |
▶ | if (run_h >= 5) total += 3 + (run_h - 5); |
Branch: 1 branch
| Branch | True | False | Total |
| if (run_h >= 5) total += 3 + (run_h - 5); |
217191 |
2862918 |
3080109 |
|
| 51 |
3080109 |
| run_h = 1; |
| 52 |
|
| } |
| 53 |
|
| /* vertical */ |
| 54 |
6249856 |
▶ | if (m[j * size + i] == m[(j - 1) * size + i]) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (m[j * size + i] == m[(j - 1) * size + i]) { |
3186657 |
3063199 |
6249856 |
|
| 55 |
3186657 |
| run_v++; |
| 56 |
|
| } else { |
| 57 |
3063199 |
▶ | if (run_v >= 5) total += 3 + (run_v - 5); |
Branch: 1 branch
| Branch | True | False | Total |
| if (run_v >= 5) total += 3 + (run_v - 5); |
181895 |
2881304 |
3063199 |
|
| 58 |
3063199 |
| run_v = 1; |
| 59 |
|
| } |
| 60 |
|
| } |
| 61 |
125928 |
▶ | if (run_h >= 5) total += 3 + (run_h - 5); |
Branch: 1 branch
| Branch | True | False | Total |
| if (run_h >= 5) total += 3 + (run_h - 5); |
15598 |
110330 |
125928 |
|
| 62 |
125928 |
▶ | if (run_v >= 5) total += 3 + (run_v - 5); |
Branch: 1 branch
| Branch | True | False | Total |
| if (run_v >= 5) total += 3 + (run_v - 5); |
15979 |
109949 |
125928 |
|
| 63 |
|
| } |
| 64 |
2920 |
| return total; |
| 65 |
|
| } |
| 66 |
|
| |
| 67 |
|
| /* Rule 2: every 2x2 block of one colour scores 3. Blocks overlap, so a |
| 68 |
|
| * 3x3 solid area contributes four of them. */ |
| 69 |
2920 |
| static int qr_penalty_2(const unsigned char *m, int size) |
| 70 |
|
| { |
| 71 |
2920 |
| int total = 0, i, j; |
| 72 |
|
| |
| 73 |
125928 |
▶ | for (i = 0; i < size - 1; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < size - 1; i++) { |
123008 |
2920 |
125928 |
|
| 74 |
6249856 |
▶ | for (j = 0; j < size - 1; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (j = 0; j < size - 1; j++) { |
6126848 |
123008 |
6249856 |
|
| 75 |
6126848 |
| unsigned char a = m[i * size + j]; |
| 76 |
6126848 |
▶ | if (a == m[i * size + j + 1] && |
Branch: 1 branch
| Branch | True | False | Total |
| if (a == m[i * size + j + 1] && |
3101484 |
3025364 |
6126848 |
|
| 77 |
3101484 |
▶ | a == m[(i + 1) * size + j] && |
Branch: 1 branch
| Branch | True | False | Total |
| a == m[(i + 1) * size + j] && |
1489219 |
1612265 |
3101484 |
|
| 78 |
1489219 |
▶ | a == m[(i + 1) * size + j + 1]) |
Branch: 1 branch
| Branch | True | False | Total |
| a == m[(i + 1) * size + j + 1]) |
722991 |
766228 |
1489219 |
|
| 79 |
722991 |
| total += 3; |
| 80 |
|
| } |
| 81 |
|
| } |
| 82 |
2920 |
| return total; |
| 83 |
|
| } |
| 84 |
|
| |
| 85 |
|
| /* Rule 3: the finder-like 1:1:3:1:1 sequence with four light modules on |
| 86 |
|
| * one side scores 40, in rows and in columns. |
| 87 |
|
| * |
| 88 |
|
| * This is the rule implementations diverge on. The spec describes the |
| 89 |
|
| * pattern as 1011101 preceded or followed by 0000, and the ambiguity is |
| 90 |
|
| * whether the four light modules must be inside the symbol or may run |
| 91 |
|
| * off the edge. Taken here as eleven modules that must all be inside - |
| 92 |
|
| * the reading that matches the published penalty scores for the |
| 93 |
|
| * ISO worked example. Both readings produce a scannable symbol, which |
| 94 |
|
| * is why the fixture test rather than a decoder is what settles it. */ |
| 95 |
2920 |
| static int qr_penalty_3(const unsigned char *m, int size) |
| 96 |
|
| { |
| 97 |
|
| static const unsigned char a[11] = { 1,0,1,1,1,0,1,0,0,0,0 }; |
| 98 |
|
| static const unsigned char b[11] = { 0,0,0,0,1,0,1,1,1,0,1 }; |
| 99 |
2920 |
| int total = 0, i, j, k; |
| 100 |
|
| |
| 101 |
128848 |
▶ | for (i = 0; i < size; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < size; i++) { |
125928 |
2920 |
128848 |
|
| 102 |
5242432 |
▶ | for (j = 0; j + 11 <= size; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (j = 0; j + 11 <= size; j++) { |
5116504 |
125928 |
5242432 |
|
| 103 |
5116504 |
| int ha = 1, hb = 1, va = 1, vb = 1; |
| 104 |
61398048 |
▶ | for (k = 0; k < 11; k++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (k = 0; k < 11; k++) { |
56281544 |
5116504 |
61398048 |
|
| 105 |
56281544 |
| unsigned char h = m[i * size + j + k]; |
| 106 |
56281544 |
| unsigned char v = m[(j + k) * size + i]; |
| 107 |
56281544 |
▶ | if (h != a[k]) ha = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (h != a[k]) ha = 0; |
28155842 |
28125702 |
56281544 |
|
| 108 |
56281544 |
▶ | if (h != b[k]) hb = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (h != b[k]) hb = 0; |
28103304 |
28178240 |
56281544 |
|
| 109 |
56281544 |
▶ | if (v != a[k]) va = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (v != a[k]) va = 0; |
28154614 |
28126930 |
56281544 |
|
| 110 |
56281544 |
▶ | if (v != b[k]) vb = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (v != b[k]) vb = 0; |
28099370 |
28182174 |
56281544 |
|
| 111 |
|
| } |
| 112 |
5116504 |
▶ | if (ha) total += 40; |
Branch: 1 branch
| Branch | True | False | Total |
| if (ha) total += 40; |
4219 |
5112285 |
5116504 |
|
| 113 |
5116504 |
▶ | if (hb) total += 40; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hb) total += 40; |
6915 |
5109589 |
5116504 |
|
| 114 |
5116504 |
▶ | if (va) total += 40; |
Branch: 1 branch
| Branch | True | False | Total |
| if (va) total += 40; |
3937 |
5112567 |
5116504 |
|
| 115 |
5116504 |
▶ | if (vb) total += 40; |
Branch: 1 branch
| Branch | True | False | Total |
| if (vb) total += 40; |
6635 |
5109869 |
5116504 |
|
| 116 |
|
| } |
| 117 |
|
| } |
| 118 |
2920 |
| return total; |
| 119 |
|
| } |
| 120 |
|
| |
| 121 |
|
| /* Rule 4: deviation of the dark module proportion from 50%, scored 10 |
| 122 |
|
| * per 5% step. */ |
| 123 |
2920 |
| static int qr_penalty_4(const unsigned char *m, int size) |
| 124 |
|
| { |
| 125 |
2920 |
| int dark = 0, total = size * size, i; |
| 126 |
|
| int percent, deviation; |
| 127 |
|
| |
| 128 |
6378704 |
▶ | for (i = 0; i < total; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < total; i++) |
6375784 |
2920 |
6378704 |
|
| 129 |
6375784 |
▶ | if (m[i]) |
Branch: 1 branch
| Branch | True | False | Total |
| if (m[i]) |
3229685 |
3146099 |
6375784 |
|
| 130 |
3229685 |
| dark++; |
| 131 |
|
| |
| 132 |
2920 |
| percent = (dark * 100) / total; |
| 133 |
2920 |
▶ | deviation = percent > 50 ? percent - 50 : 50 - percent; |
Branch: 1 branch
| Branch | True | False | Total |
| deviation = percent > 50 ? percent - 50 : 50 - percent; |
1120 |
1800 |
2920 |
|
| 134 |
2920 |
| return (deviation / 5) * 10; |
| 135 |
|
| } |
| 136 |
|
| |
| 137 |
2920 |
| static int qr_penalty(const unsigned char *m, int size) |
| 138 |
|
| { |
| 139 |
2920 |
| return qr_penalty_1(m, size) + qr_penalty_2(m, size) |
| 140 |
2920 |
| + qr_penalty_3(m, size) + qr_penalty_4(m, size); |
| 141 |
|
| } |
| 142 |
|
| |
| 143 |
|
| /* --- format and version information -------------------------------------- */ |
| 144 |
|
| |
| 145 |
|
| /* ECC level to its two-bit format indicator. Note the ordering is NOT |
| 146 |
|
| * the L/M/Q/H of the capacity tables: L is 01 and M is 00, so a |
| 147 |
|
| * straight index would silently swap the two most common levels. */ |
| 148 |
2920 |
| static unsigned int qr_format_ecc_bits(int ecc) |
| 149 |
|
| { |
| 150 |
2920 |
| switch (ecc) { |
| 151 |
496 |
| case 0: return 1u; /* L */ |
| 152 |
1216 |
| case 1: return 0u; /* M */ |
| 153 |
504 |
| case 2: return 3u; /* Q */ |
| 154 |
704 |
| default: return 2u; /* H */ |
| 155 |
|
| } |
| 156 |
|
| } |
| 157 |
|
| |
| 158 |
|
| /* 15-bit format information: 5 data bits (2 ECC + 3 mask) extended by |
| 159 |
|
| * BCH(15,5) over generator 0x537, then XORed with 0x5412 so that an |
| 160 |
|
| * all-zero format is not all-zero on the symbol. */ |
| 161 |
2920 |
| static unsigned int qr_format_bits(int ecc, int mask) |
| 162 |
|
| { |
| 163 |
2920 |
| unsigned int data = (qr_format_ecc_bits(ecc) << 3) | (unsigned int)mask; |
| 164 |
2920 |
| unsigned int rem = data; |
| 165 |
|
| int i; |
| 166 |
|
| |
| 167 |
32120 |
▶ | for (i = 0; i < 10; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 10; i++) |
29200 |
2920 |
32120 |
|
| 168 |
29200 |
| rem = (rem << 1) ^ ((rem >> 9) * 0x537u); |
| 169 |
|
| |
| 170 |
2920 |
| return ((data << 10) | (rem & 0x3FFu)) ^ 0x5412u; |
| 171 |
|
| } |
| 172 |
|
| |
| 173 |
|
| /* 18-bit version information, versions 7 and up: 6 data bits extended by |
| 174 |
|
| * BCH(18,6) over generator 0x1F25. No final XOR, unlike the format |
| 175 |
|
| * block. */ |
| 176 |
171 |
| static unsigned int qr_version_bits(int version) |
| 177 |
|
| { |
| 178 |
171 |
| unsigned int rem = (unsigned int)version; |
| 179 |
|
| int i; |
| 180 |
|
| |
| 181 |
2223 |
▶ | for (i = 0; i < 12; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 12; i++) |
2052 |
171 |
2223 |
|
| 182 |
2052 |
| rem = (rem << 1) ^ ((rem >> 11) * 0x1F25u); |
| 183 |
|
| |
| 184 |
171 |
| return ((unsigned int)version << 12) | (rem & 0xFFFu); |
| 185 |
|
| } |
| 186 |
|
| |
| 187 |
|
| #endif /* QR_MASK_H */ |