include/qr/qr_gf.h

filter: Statementstmt 100% 26 / 26 Branchbran 94.4% 17 / 18 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 97.7% 43 / 44 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/qr/qr_encode.h ↑ Summary include/qr/qr_mask.h »
1 #ifndef QR_GF_H
2 #define QR_GF_H
3  
4 /* qr_gf.h - GF(256) arithmetic and Reed-Solomon error correction.
5 *
6 * The field is GF(2^8) modulo the QR primitive polynomial
7 * x^8 + x^4 + x^3 + x^2 + 1 (0x11D), with 2 as the generator. Every
8 * value below is fixed by ISO/IEC 18004: there is nothing to tune here
9 * and no latitude in the result. It either matches the published test
10 * vectors exactly or it is wrong.
11 *
12 * The log and antilog tables are compiled in rather than built at load
13 * time. Computing them in a BOOT: block would be a handful of
14 * instructions, but it would also be a static buffer written by every
15 * interpreter that loads the module - benign in practice and still a
16 * data race under ithreads. Constants cost 512 bytes of rodata and have
17 * neither problem, nor any initialisation order to get wrong.
18 */
19  
20 static const unsigned char qr_gf_exp[256] = {
21 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80,
22 0x1D, 0x3A, 0x74, 0xE8, 0xCD, 0x87, 0x13, 0x26,
23 0x4C, 0x98, 0x2D, 0x5A, 0xB4, 0x75, 0xEA, 0xC9,
24 0x8F, 0x03, 0x06, 0x0C, 0x18, 0x30, 0x60, 0xC0,
25 0x9D, 0x27, 0x4E, 0x9C, 0x25, 0x4A, 0x94, 0x35,
26 0x6A, 0xD4, 0xB5, 0x77, 0xEE, 0xC1, 0x9F, 0x23,
27 0x46, 0x8C, 0x05, 0x0A, 0x14, 0x28, 0x50, 0xA0,
28 0x5D, 0xBA, 0x69, 0xD2, 0xB9, 0x6F, 0xDE, 0xA1,
29 0x5F, 0xBE, 0x61, 0xC2, 0x99, 0x2F, 0x5E, 0xBC,
30 0x65, 0xCA, 0x89, 0x0F, 0x1E, 0x3C, 0x78, 0xF0,
31 0xFD, 0xE7, 0xD3, 0xBB, 0x6B, 0xD6, 0xB1, 0x7F,
32 0xFE, 0xE1, 0xDF, 0xA3, 0x5B, 0xB6, 0x71, 0xE2,
33 0xD9, 0xAF, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88,
34 0x0D, 0x1A, 0x34, 0x68, 0xD0, 0xBD, 0x67, 0xCE,
35 0x81, 0x1F, 0x3E, 0x7C, 0xF8, 0xED, 0xC7, 0x93,
36 0x3B, 0x76, 0xEC, 0xC5, 0x97, 0x33, 0x66, 0xCC,
37 0x85, 0x17, 0x2E, 0x5C, 0xB8, 0x6D, 0xDA, 0xA9,
38 0x4F, 0x9E, 0x21, 0x42, 0x84, 0x15, 0x2A, 0x54,
39 0xA8, 0x4D, 0x9A, 0x29, 0x52, 0xA4, 0x55, 0xAA,
40 0x49, 0x92, 0x39, 0x72, 0xE4, 0xD5, 0xB7, 0x73,
41 0xE6, 0xD1, 0xBF, 0x63, 0xC6, 0x91, 0x3F, 0x7E,
42 0xFC, 0xE5, 0xD7, 0xB3, 0x7B, 0xF6, 0xF1, 0xFF,
43 0xE3, 0xDB, 0xAB, 0x4B, 0x96, 0x31, 0x62, 0xC4,
44 0x95, 0x37, 0x6E, 0xDC, 0xA5, 0x57, 0xAE, 0x41,
45 0x82, 0x19, 0x32, 0x64, 0xC8, 0x8D, 0x07, 0x0E,
46 0x1C, 0x38, 0x70, 0xE0, 0xDD, 0xA7, 0x53, 0xA6,
47 0x51, 0xA2, 0x59, 0xB2, 0x79, 0xF2, 0xF9, 0xEF,
48 0xC3, 0x9B, 0x2B, 0x56, 0xAC, 0x45, 0x8A, 0x09,
49 0x12, 0x24, 0x48, 0x90, 0x3D, 0x7A, 0xF4, 0xF5,
50 0xF7, 0xF3, 0xFB, 0xEB, 0xCB, 0x8B, 0x0B, 0x16,
51 0x2C, 0x58, 0xB0, 0x7D, 0xFA, 0xE9, 0xCF, 0x83,
52 0x1B, 0x36, 0x6C, 0xD8, 0xAD, 0x47, 0x8E, 0x01
53 };
54  
55 static const unsigned char qr_gf_log[256] = {
56 0x00, 0x00, 0x01, 0x19, 0x02, 0x32, 0x1A, 0xC6,
57 0x03, 0xDF, 0x33, 0xEE, 0x1B, 0x68, 0xC7, 0x4B,
58 0x04, 0x64, 0xE0, 0x0E, 0x34, 0x8D, 0xEF, 0x81,
59 0x1C, 0xC1, 0x69, 0xF8, 0xC8, 0x08, 0x4C, 0x71,
60 0x05, 0x8A, 0x65, 0x2F, 0xE1, 0x24, 0x0F, 0x21,
61 0x35, 0x93, 0x8E, 0xDA, 0xF0, 0x12, 0x82, 0x45,
62 0x1D, 0xB5, 0xC2, 0x7D, 0x6A, 0x27, 0xF9, 0xB9,
63 0xC9, 0x9A, 0x09, 0x78, 0x4D, 0xE4, 0x72, 0xA6,
64 0x06, 0xBF, 0x8B, 0x62, 0x66, 0xDD, 0x30, 0xFD,
65 0xE2, 0x98, 0x25, 0xB3, 0x10, 0x91, 0x22, 0x88,
66 0x36, 0xD0, 0x94, 0xCE, 0x8F, 0x96, 0xDB, 0xBD,
67 0xF1, 0xD2, 0x13, 0x5C, 0x83, 0x38, 0x46, 0x40,
68 0x1E, 0x42, 0xB6, 0xA3, 0xC3, 0x48, 0x7E, 0x6E,
69 0x6B, 0x3A, 0x28, 0x54, 0xFA, 0x85, 0xBA, 0x3D,
70 0xCA, 0x5E, 0x9B, 0x9F, 0x0A, 0x15, 0x79, 0x2B,
71 0x4E, 0xD4, 0xE5, 0xAC, 0x73, 0xF3, 0xA7, 0x57,
72 0x07, 0x70, 0xC0, 0xF7, 0x8C, 0x80, 0x63, 0x0D,
73 0x67, 0x4A, 0xDE, 0xED, 0x31, 0xC5, 0xFE, 0x18,
74 0xE3, 0xA5, 0x99, 0x77, 0x26, 0xB8, 0xB4, 0x7C,
75 0x11, 0x44, 0x92, 0xD9, 0x23, 0x20, 0x89, 0x2E,
76 0x37, 0x3F, 0xD1, 0x5B, 0x95, 0xBC, 0xCF, 0xCD,
77 0x90, 0x87, 0x97, 0xB2, 0xDC, 0xFC, 0xBE, 0x61,
78 0xF2, 0x56, 0xD3, 0xAB, 0x14, 0x2A, 0x5D, 0x9E,
79 0x84, 0x3C, 0x39, 0x53, 0x47, 0x6D, 0x41, 0xA2,
80 0x1F, 0x2D, 0x43, 0xD8, 0xB7, 0x7B, 0xA4, 0x76,
81 0xC4, 0x17, 0x49, 0xEC, 0x7F, 0x0C, 0x6F, 0xF6,
82 0x6C, 0xA1, 0x3B, 0x52, 0x29, 0x9D, 0x55, 0xAA,
83 0xFB, 0x60, 0x86, 0xB1, 0xBB, 0xCC, 0x3E, 0x5A,
84 0xCB, 0x59, 0x5F, 0xB0, 0x9C, 0xA9, 0xA0, 0x51,
85 0x0B, 0xF5, 0x16, 0xEB, 0x7A, 0x75, 0x2C, 0xD7,
86 0x4F, 0xAE, 0xD5, 0xE9, 0xE6, 0xE7, 0xAD, 0xE8,
87 0x74, 0xD6, 0xF4, 0xEA, 0xA8, 0x50, 0x58, 0xAF
88 };
89  
90 /* The largest error correction block in versions 1-10 is 30 codewords
91 * (version 9, level L), so a generator polynomial never exceeds degree
92 * 30. The bound is stated rather than assumed because every buffer
93 * below is sized from it. */
94 #define QR_MAX_EC 68
95  
96 /* a * b in GF(256). Zero is special-cased: log(0) is undefined, and the
97 * table stores 0 there, which would otherwise make 0 * x come out as
98 * exp(log(x)) rather than 0. */
99 1501421 static unsigned char qr_gf_mul(unsigned char a, unsigned char b)
100 {
101 1501421 ▶ if (a == 0 || b == 0)
Branch: 2 branches
BranchTrueFalseTotal
if (a == 0 || b == 0) 1501421 0 1501421
if (a == 0 || b == 0) 4187 1497234 1501421
102 4187 return 0;
103 1497234 return qr_gf_exp[(qr_gf_log[a] + qr_gf_log[b]) % 255];
104 }
105  
106 /* The generator polynomial for `n` error correction codewords, which is
107 * the product of (x - a^i) for i in 0..n-1. Coefficients come back
108 * highest power first, and the leading coefficient is always 1, so the
109 * caller gets n+1 of them.
110 *
111 * Built by repeated multiplication rather than tabulated: the table
112 * would be 30 rows of up to 31 bytes to save a few hundred
113 * multiplications once per encode. */
114 1627 static void qr_gf_generator(int n, unsigned char *out)
115 {
116 int i, j;
117  
118 1627 out[0] = 1;
119  
120 39024 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 37397 1627 39024
121 /* Multiply the accumulated polynomial by (x - a^i). Coefficients
122 * are highest power first, so multiplying by x is a shift up and
123 * the new coefficient at j picks up root * the one below it:
124 *
125 * res[0] = out[0] (always 1)
126 * res[j] = out[j] + root * out[j-1]
127 *
128 * Getting these two terms the wrong way round produces the
129 * polynomial with its coefficients reversed, which still looks
130 * like a plausible generator and fails only when a syndrome is
131 * taken. */
132 37397 unsigned char root = qr_gf_exp[i];
133  
134 37397 out[i + 1] = 0;
135 500049 ▶ for (j = i + 1; j > 0; j--)
Branch: 1 branch
BranchTrueFalseTotal
for (j = i + 1; j > 0; j--) 462652 37397 500049
136 462652 out[j] = (unsigned char)(out[j] ^ qr_gf_mul(out[j - 1], root));
137 }
138 1627 }
139  
140 /* Reed-Solomon: the remainder of data * x^n divided by the generator,
141 * which is the n error correction codewords for that block.
142 *
143 * Polynomial long division in place over a scratch buffer. `data` is
144 * not modified. */
145 1627 static void qr_rs_encode(const unsigned char *data, int len,
146 int n, unsigned char *out)
147 {
148 unsigned char gen[QR_MAX_EC + 1];
149 unsigned char rem[QR_MAX_EC];
150 int i, j;
151  
152 1627 qr_gf_generator(n, gen);
153  
154 39024 ▶ for (i = 0; i < n; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) 37397 1627 39024
155 37397 rem[i] = 0;
156  
157 46085 ▶ for (i = 0; i < len; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < len; i++) { 44458 1627 46085
158 44458 unsigned char factor = (unsigned char)(data[i] ^ rem[0]);
159  
160 /* shift the remainder left one codeword */
161 1038769 ▶ for (j = 0; j < n - 1; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < n - 1; j++) 994311 44458 1038769
162 994311 rem[j] = rem[j + 1];
163 44458 rem[n - 1] = 0;
164  
165 /* subtract factor * generator; gen[0] is 1 and was consumed by
166 * the shift, so the loop starts at the next coefficient */
167 1083227 ▶ for (j = 0; j < n; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < n; j++) 1038769 44458 1083227
168 1038769 rem[j] ^= qr_gf_mul(gen[j + 1], factor);
169 }
170  
171 39024 ▶ for (i = 0; i < n; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) 37397 1627 39024
172 37397 out[i] = rem[i];
173 1627 }
174  
175 #endif /* QR_GF_H */
« include/qr/qr_encode.h ↑ Summary include/qr/qr_mask.h »