1 /*
2 This is a forked version of the qrduino project. The original is at
3 "https://github.com/tz1/qrduino". The author of this code is Tom
4 Zerucha, https://github.com/tz1.
5
6 This file is licenced under the GNU General Public Licence, version 3.
7
8 This file, "qrencode.c", contains all of the C code of the qrduino
9 project in one file, except for the jpeg code which I don't need
10 since I output to PNG.
11
12 This comment was added by Ben Bullock <benkasminbullock@gmail.com>,
13 on 2015-09-05.
14 */
15
16 #include <assert.h>
17 #include <stdio.h>
18 #include <string.h>
19 #include <stdlib.h>
20
21 #include "qrencode.h"
22
23 #ifdef HEADER
24
25 typedef struct qr {
26 char * input;
27 int input_length;
28 unsigned level;
29 unsigned version;
30 unsigned char * strinbuf;
31 unsigned char * qrframe;
32 unsigned char *framebase;
33 unsigned char *framask;
34 unsigned char *rlens;
35 unsigned char WD;
36 unsigned char WDB;
37 unsigned char neccblk1;
38 unsigned char neccblk2;
39 unsigned char datablkw;
40 unsigned char eccblkwid;
41
42 unsigned initialized : 1;
43 }
44 qr_t;
45
46 #define QRBIT(f,x,y) ( ( qr->f[((x)>>3) + (y) * qr->WDB] >> (7-((x) & 7 ))) & 1 )
47
48 #define QR_MINIMUM_VERSION 1
49 #define QR_MAXIMUM_VERSION 40
50 #define QR_MINIMUM_LEVEL 1
51 #define QR_MAXIMUM_LEVEL 4
52
53 #endif /* def HEADER */
54
55 #define SETQRBIT(f,x,y) qr->f[((x)>>3) + (y) * qr->WDB] |= 0x80 >> ((x) & 7)
56 #define TOGQRBIT(f,x,y) qr->f[((x)>>3) + (y) * qr->WDB] ^= 0x80 >> ((x) & 7)
57
setmask(qr_t * qr,unsigned char x,unsigned char y)58 static void setmask(qr_t * qr, unsigned char x, unsigned char y)
59 {
60 unsigned bt;
61 if (x > y) {
62 bt = x;
63 x = y;
64 y = bt;
65 }
66 // y*y = 1+3+5...
67 bt = y;
68 bt *= y;
69 bt += y;
70 bt >>= 1;
71 bt += x;
72 qr->framask[bt >> 3] |= 0x80 >> (bt & 7);
73 }
74
putfind(qr_t * qr)75 static void putfind(qr_t * qr)
76 {
77 unsigned char j, i, k, t;
78 for (t = 0; t < 3; t++) {
79 k = 0;
80 i = 0;
81 if (t == 1)
82 k = (qr->WD - 7);
83 if (t == 2)
84 i = (qr->WD - 7);
85 SETQRBIT(framebase,i + 3, k + 3);
86 for (j = 0; j < 6; j++) {
87 SETQRBIT(framebase,i + j, k);
88 SETQRBIT(framebase,i, k + j + 1);
89 SETQRBIT(framebase,i + 6, k + j);
90 SETQRBIT(framebase,i + j + 1, k + 6);
91 }
92 for (j = 1; j < 5; j++) {
93 setmask(qr, i + j, k + 1);
94 setmask(qr, i + 1, k + j + 1);
95 setmask(qr, i + 5, k + j);
96 setmask(qr, i + j + 1, k + 5);
97 }
98 for (j = 2; j < 4; j++) {
99 SETQRBIT(framebase,i + j, k + 2);
100 SETQRBIT(framebase,i + 2, k + j + 1);
101 SETQRBIT(framebase,i + 4, k + j);
102 SETQRBIT(framebase,i + j + 1, k + 4);
103 }
104 }
105 }
106
putalign(qr_t * qr,int x,int y)107 static void putalign(qr_t * qr, int x, int y)
108 {
109 int j;
110
111 SETQRBIT(framebase,x, y);
112 for (j = -2; j < 2; j++) {
113 SETQRBIT(framebase,x + j, y - 2);
114 SETQRBIT(framebase,x - 2, y + j + 1);
115 SETQRBIT(framebase,x + 2, y + j);
116 SETQRBIT(framebase,x + j + 1, y + 2);
117 }
118 for (j = 0; j < 2; j++) {
119 setmask(qr, x - 1, y + j);
120 setmask(qr, x + 1, y - j);
121 setmask(qr, x - j, y - 1);
122 setmask(qr, x + j, y + 1);
123 }
124 }
125
126 static const unsigned char adelta[41] = {
127 0, 11, 15, 19, 23, 27, 31, // force 1 pat
128 16, 18, 20, 22, 24, 26, 28, 20, 22, 24, 24, 26, 28, 28, 22, 24, 24,
129 26, 26, 28, 28, 24, 24, 26, 26, 26, 28, 28, 24, 26, 26, 26, 28, 28,
130 };
131
doaligns(qr_t * qr)132 static void doaligns(qr_t * qr)
133 {
134 unsigned char delta, x, y;
135 if (qr->version < 2)
136 return;
137 delta = adelta[qr->version];
138 y = qr->WD - 7;
139 for (;;) {
140 x = qr->WD - 7;
141 while (x > delta - 3U) {
142 putalign(qr, x, y);
143 if (x < delta)
144 break;
145 x -= delta;
146 }
147 if (y <= delta + 9U)
148 break;
149 y -= delta;
150 putalign(qr, 6, y);
151 putalign(qr, y, 6);
152 }
153 }
154
155 static const unsigned vpat[] = {
156 0xc94, 0x5bc, 0xa99, 0x4d3, 0xbf6, 0x762, 0x847, 0x60d,
157 0x928, 0xb78, 0x45d, 0xa17, 0x532, 0x9a6, 0x683, 0x8c9,
158 0x7ec, 0xec4, 0x1e1, 0xfab, 0x08e, 0xc1a, 0x33f, 0xd75,
159 0x250, 0x9d5, 0x6f0, 0x8ba, 0x79f, 0xb0b, 0x42e, 0xa64,
160 0x541, 0xc69
161 };
162
putvpat(qr_t * qr)163 static void putvpat(qr_t * qr)
164 {
165 unsigned char vers = qr->version;
166 unsigned char x, y, bc;
167 unsigned verinfo;
168 if (vers < 7)
169 return;
170 verinfo = vpat[vers - 7];
171
172 bc = 17;
173 for (x = 0; x < 6; x++)
174 for (y = 0; y < 3; y++, bc--)
175 if (1 & (bc > 11 ? vers >> (bc - 12) : verinfo >> bc)) {
176 SETQRBIT(framebase,5 - x, 2 - y + qr->WD - 11);
177 SETQRBIT(framebase,2 - y + qr->WD - 11, 5 - x);
178 } else {
179 setmask(qr, 5 - x, 2 - y + qr->WD - 11);
180 setmask(qr, 2 - y + qr->WD - 11, 5 - x);
181 }
182 }
183
initframe(qr_t * qr)184 void initframe(qr_t * qr)
185 {
186 unsigned x, y;
187
188 qr->framebase = calloc(qr->WDB * qr->WD, 1);
189 qr->framask = calloc(((qr->WD * (qr->WD + 1) / 2) + 7) / 8, 1);
190 qr->rlens = malloc(qr->WD + 1);
191 // finders
192 putfind(qr);
193 // alignment blocks
194 doaligns(qr);
195 // single black
196 SETQRBIT(framebase,8, qr->WD - 8);
197 // timing gap - masks only
198 for (y = 0; y < 7; y++) {
199 setmask(qr, 7, y);
200 setmask(qr, qr->WD - 8, y);
201 setmask(qr, 7, y + qr->WD - 7);
202 }
203 for (x = 0; x < 8; x++) {
204 setmask(qr, x, 7);
205 setmask(qr, x + qr->WD - 8, 7);
206 setmask(qr, x, qr->WD - 8);
207 }
208 // reserve mask-format area
209 for (x = 0; x < 9; x++)
210 setmask(qr,x, 8);
211 for (x = 0; x < 8; x++) {
212 setmask(qr,x + qr->WD - 8, 8);
213 setmask(qr,8, x);
214 }
215 for (y = 0; y < 7; y++)
216 setmask(qr,8, y + qr->WD - 7);
217 // timing
218 for (x = 0; x < qr->WD - 14; x++)
219 if (x & 1) {
220 setmask(qr,8 + x, 6);
221 setmask(qr,6, 8 + x);
222 } else {
223 SETQRBIT(framebase,8 + x, 6);
224 SETQRBIT(framebase,6, 8 + x);
225 }
226
227 // version block
228 putvpat(qr);
229 for (y = 0; y < qr->WD; y++)
230 for (x = 0; x <= y; x++)
231 if (QRBIT(framebase,x, y))
232 setmask(qr,x, y);
233 }
234
freeframe(qr_t * qr)235 static void freeframe(qr_t * qr)
236 {
237 free( qr->framebase );
238 free( qr->framask );
239 free( qr->rlens );
240 free (qr->qrframe);
241 free (qr->strinbuf);
242 }
243
244 static const unsigned char eccblocks[] = {
245 1, 0, 19, 7, 1, 0, 16, 10, 1, 0, 13, 13, 1, 0, 9, 17,
246 1, 0, 34, 10, 1, 0, 28, 16, 1, 0, 22, 22, 1, 0, 16, 28,
247 1, 0, 55, 15, 1, 0, 44, 26, 2, 0, 17, 18, 2, 0, 13, 22,
248 1, 0, 80, 20, 2, 0, 32, 18, 2, 0, 24, 26, 4, 0, 9, 16,
249 1, 0,108, 26, 2, 0, 43, 24, 2, 2, 15, 18, 2, 2, 11, 22,
250 2, 0, 68, 18, 4, 0, 27, 16, 4, 0, 19, 24, 4, 0, 15, 28,
251 2, 0, 78, 20, 4, 0, 31, 18, 2, 4, 14, 18, 4, 1, 13, 26,
252 2, 0, 97, 24, 2, 2, 38, 22, 4, 2, 18, 22, 4, 2, 14, 26,
253 2, 0,116, 30, 3, 2, 36, 22, 4, 4, 16, 20, 4, 4, 12, 24,
254 2, 2, 68, 18, 4, 1, 43, 26, 6, 2, 19, 24, 6, 2, 15, 28,
255 4, 0, 81, 20, 1, 4, 50, 30, 4, 4, 22, 28, 3, 8, 12, 24,
256 2, 2, 92, 24, 6, 2, 36, 22, 4, 6, 20, 26, 7, 4, 14, 28,
257 4, 0,107, 26, 8, 1, 37, 22, 8, 4, 20, 24, 12, 4, 11, 22,
258 3, 1,115, 30, 4, 5, 40, 24, 11, 5, 16, 20, 11, 5, 12, 24,
259 5, 1, 87, 22, 5, 5, 41, 24, 5, 7, 24, 30, 11, 7, 12, 24,
260 5, 1, 98, 24, 7, 3, 45, 28, 15, 2, 19, 24, 3,13, 15, 30,
261 1, 5,107, 28, 10, 1, 46, 28, 1,15, 22, 28, 2,17, 14, 28,
262 5, 1,120, 30, 9, 4, 43, 26, 17, 1, 22, 28, 2,19, 14, 28,
263 3, 4,113, 28, 3,11, 44, 26, 17, 4, 21, 26, 9,16, 13, 26,
264 3, 5,107, 28, 3,13, 41, 26, 15, 5, 24, 30, 15,10, 15, 28,
265 4, 4,116, 28, 17, 0, 42, 26, 17, 6, 22, 28, 19, 6, 16, 30,
266 2, 7,111, 28, 17, 0, 46, 28, 7,16, 24, 30, 34, 0, 13, 24,
267 4, 5,121, 30, 4,14, 47, 28, 11,14, 24, 30, 16,14, 15, 30,
268 6, 4,117, 30, 6,14, 45, 28, 11,16, 24, 30, 30, 2, 16, 30,
269 8, 4,106, 26, 8,13, 47, 28, 7,22, 24, 30, 22,13, 15, 30,
270 10, 2,114, 28, 19, 4, 46, 28, 28, 6, 22, 28, 33, 4, 16, 30,
271 8, 4,122, 30, 22, 3, 45, 28, 8,26, 23, 30, 12,28, 15, 30,
272 3,10,117, 30, 3,23, 45, 28, 4,31, 24, 30, 11,31, 15, 30,
273 7, 7,116, 30, 21, 7, 45, 28, 1,37, 23, 30, 19,26, 15, 30,
274 5,10,115, 30, 19,10, 47, 28, 15,25, 24, 30, 23,25, 15, 30,
275 13, 3,115, 30, 2,29, 46, 28, 42, 1, 24, 30, 23,28, 15, 30,
276 17, 0,115, 30, 10,23, 46, 28, 10,35, 24, 30, 19,35, 15, 30,
277 17, 1,115, 30, 14,21, 46, 28, 29,19, 24, 30, 11,46, 15, 30,
278 13, 6,115, 30, 14,23, 46, 28, 44, 7, 24, 30, 59, 1, 16, 30,
279 12, 7,121, 30, 12,26, 47, 28, 39,14, 24, 30, 22,41, 15, 30,
280 6,14,121, 30, 6,34, 47, 28, 46,10, 24, 30, 2,64, 15, 30,
281 17, 4,122, 30, 29,14, 46, 28, 49,10, 24, 30, 24,46, 15, 30,
282 4,18,122, 30, 13,32, 46, 28, 48,14, 24, 30, 42,32, 15, 30,
283 20, 4,117, 30, 40, 7, 47, 28, 43,22, 24, 30, 10,67, 15, 30,
284 19, 6,118, 30, 18,31, 47, 28, 34,34, 24, 30, 20,61, 15, 30,
285 };
286
initecc(qr_t * qr)287 unsigned initecc(qr_t * qr)
288 {
289 assert (qr->version >= QR_MINIMUM_VERSION &&
290 qr->version <= QR_MAXIMUM_VERSION);
291
292 qr->WD = 17 + 4 * qr->version;
293 qr->WDB = (qr->WD + 7) / 8;
294
295 unsigned fsz = qr->WD * qr->WDB;
296 if (fsz < 768) {
297 // for ECC math buffers
298 fsz = 768;
299 }
300 qr->qrframe = malloc (fsz);
301 assert (qr->qrframe);
302
303 assert (qr->level >= QR_MINIMUM_LEVEL && qr->level <= QR_MAXIMUM_LEVEL);
304
305 unsigned eccindex = (qr->level - 1) * 4 + (qr->version - 1) * 16;
306
307 qr->neccblk1 = eccblocks[eccindex++];
308 qr->neccblk2 = eccblocks[eccindex++];
309 qr->datablkw = eccblocks[eccindex++];
310 qr->eccblkwid = eccblocks[eccindex++];
311
312 if (fsz < qr->datablkw + (qr->datablkw + qr->eccblkwid) * (qr->neccblk1 + qr->neccblk2) + qr->neccblk2)
313 fsz = qr->datablkw + (qr->datablkw + qr->eccblkwid) * (qr->neccblk1 + qr->neccblk2) + qr->neccblk2;
314 qr->strinbuf = calloc(fsz, sizeof (unsigned char));
315 qr->initialized = 1;
316 return qr->datablkw * (qr->neccblk1 + qr->neccblk2) + qr->neccblk2 - 3; //-2 if vers <= 9!
317 }
318
319 /* Initialize using string length. */
320
initeccsize(qr_t * qr)321 unsigned initeccsize (qr_t * qr)
322 {
323 unsigned eccindex;
324 unsigned vers;
325
326 assert (qr->input);
327 assert (qr->input_length > 0);
328 assert (qr->level >= 1 && qr->level <= 4);
329
330 for (vers = 1; vers < 40; vers++) {
331 eccindex = (qr->level - 1) * 4 + (vers - 1) * 16;
332 qr->neccblk1 = eccblocks[eccindex++];
333 qr->neccblk2 = eccblocks[eccindex++];
334 qr->datablkw = eccblocks[eccindex++];
335 if (qr->input_length < qr->datablkw * (qr->neccblk1 + qr->neccblk2) + qr->neccblk2 - 3) {
336 qr->version = vers;
337 break;
338 }
339 }
340 return initecc (qr);
341 }
342
343 //========================================================================
344 // Reed Solomon error correction
modnn(unsigned x)345 static unsigned modnn(unsigned x)
346 {
347 while (x >= 255) {
348 x -= 255;
349 x = (x >> 8) + (x & 255);
350 }
351 return x;
352 }
353
354 static const unsigned char g0log[256] = {
355 0xff,0x00,0x01,0x19,0x02,0x32,0x1a,0xc6,0x03,0xdf,0x33,0xee,0x1b,0x68,0xc7,0x4b,
356 0x04,0x64,0xe0,0x0e,0x34,0x8d,0xef,0x81,0x1c,0xc1,0x69,0xf8,0xc8,0x08,0x4c,0x71,
357 0x05,0x8a,0x65,0x2f,0xe1,0x24,0x0f,0x21,0x35,0x93,0x8e,0xda,0xf0,0x12,0x82,0x45,
358 0x1d,0xb5,0xc2,0x7d,0x6a,0x27,0xf9,0xb9,0xc9,0x9a,0x09,0x78,0x4d,0xe4,0x72,0xa6,
359 0x06,0xbf,0x8b,0x62,0x66,0xdd,0x30,0xfd,0xe2,0x98,0x25,0xb3,0x10,0x91,0x22,0x88,
360 0x36,0xd0,0x94,0xce,0x8f,0x96,0xdb,0xbd,0xf1,0xd2,0x13,0x5c,0x83,0x38,0x46,0x40,
361 0x1e,0x42,0xb6,0xa3,0xc3,0x48,0x7e,0x6e,0x6b,0x3a,0x28,0x54,0xfa,0x85,0xba,0x3d,
362 0xca,0x5e,0x9b,0x9f,0x0a,0x15,0x79,0x2b,0x4e,0xd4,0xe5,0xac,0x73,0xf3,0xa7,0x57,
363 0x07,0x70,0xc0,0xf7,0x8c,0x80,0x63,0x0d,0x67,0x4a,0xde,0xed,0x31,0xc5,0xfe,0x18,
364 0xe3,0xa5,0x99,0x77,0x26,0xb8,0xb4,0x7c,0x11,0x44,0x92,0xd9,0x23,0x20,0x89,0x2e,
365 0x37,0x3f,0xd1,0x5b,0x95,0xbc,0xcf,0xcd,0x90,0x87,0x97,0xb2,0xdc,0xfc,0xbe,0x61,
366 0xf2,0x56,0xd3,0xab,0x14,0x2a,0x5d,0x9e,0x84,0x3c,0x39,0x53,0x47,0x6d,0x41,0xa2,
367 0x1f,0x2d,0x43,0xd8,0xb7,0x7b,0xa4,0x76,0xc4,0x17,0x49,0xec,0x7f,0x0c,0x6f,0xf6,
368 0x6c,0xa1,0x3b,0x52,0x29,0x9d,0x55,0xaa,0xfb,0x60,0x86,0xb1,0xbb,0xcc,0x3e,0x5a,
369 0xcb,0x59,0x5f,0xb0,0x9c,0xa9,0xa0,0x51,0x0b,0xf5,0x16,0xeb,0x7a,0x75,0x2c,0xd7,
370 0x4f,0xae,0xd5,0xe9,0xe6,0xe7,0xad,0xe8,0x74,0xd6,0xf4,0xea,0xa8,0x50,0x58,0xaf,
371 };
372
373 static const unsigned char g0exp[256] = {
374 0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x1d,0x3a,0x74,0xe8,0xcd,0x87,0x13,0x26,
375 0x4c,0x98,0x2d,0x5a,0xb4,0x75,0xea,0xc9,0x8f,0x03,0x06,0x0c,0x18,0x30,0x60,0xc0,
376 0x9d,0x27,0x4e,0x9c,0x25,0x4a,0x94,0x35,0x6a,0xd4,0xb5,0x77,0xee,0xc1,0x9f,0x23,
377 0x46,0x8c,0x05,0x0a,0x14,0x28,0x50,0xa0,0x5d,0xba,0x69,0xd2,0xb9,0x6f,0xde,0xa1,
378 0x5f,0xbe,0x61,0xc2,0x99,0x2f,0x5e,0xbc,0x65,0xca,0x89,0x0f,0x1e,0x3c,0x78,0xf0,
379 0xfd,0xe7,0xd3,0xbb,0x6b,0xd6,0xb1,0x7f,0xfe,0xe1,0xdf,0xa3,0x5b,0xb6,0x71,0xe2,
380 0xd9,0xaf,0x43,0x86,0x11,0x22,0x44,0x88,0x0d,0x1a,0x34,0x68,0xd0,0xbd,0x67,0xce,
381 0x81,0x1f,0x3e,0x7c,0xf8,0xed,0xc7,0x93,0x3b,0x76,0xec,0xc5,0x97,0x33,0x66,0xcc,
382 0x85,0x17,0x2e,0x5c,0xb8,0x6d,0xda,0xa9,0x4f,0x9e,0x21,0x42,0x84,0x15,0x2a,0x54,
383 0xa8,0x4d,0x9a,0x29,0x52,0xa4,0x55,0xaa,0x49,0x92,0x39,0x72,0xe4,0xd5,0xb7,0x73,
384 0xe6,0xd1,0xbf,0x63,0xc6,0x91,0x3f,0x7e,0xfc,0xe5,0xd7,0xb3,0x7b,0xf6,0xf1,0xff,
385 0xe3,0xdb,0xab,0x4b,0x96,0x31,0x62,0xc4,0x95,0x37,0x6e,0xdc,0xa5,0x57,0xae,0x41,
386 0x82,0x19,0x32,0x64,0xc8,0x8d,0x07,0x0e,0x1c,0x38,0x70,0xe0,0xdd,0xa7,0x53,0xa6,
387 0x51,0xa2,0x59,0xb2,0x79,0xf2,0xf9,0xef,0xc3,0x9b,0x2b,0x56,0xac,0x45,0x8a,0x09,
388 0x12,0x24,0x48,0x90,0x3d,0x7a,0xf4,0xf5,0xf7,0xf3,0xfb,0xeb,0xcb,0x8b,0x0b,0x16,
389 0x2c,0x58,0xb0,0x7d,0xfa,0xe9,0xcf,0x83,0x1b,0x36,0x6c,0xd8,0xad,0x47,0x8e,0x00,
390 };
391
392 #define glog(x) g0log[x]
393 #define gexp(x) g0exp[x]
394
initrspoly(unsigned char eclen,unsigned char * genpoly)395 static void initrspoly(unsigned char eclen, unsigned char *genpoly)
396 {
397 unsigned char i, j;
398
399 genpoly[0] = 1;
400 for (i = 0; i < eclen; i++) {
401 genpoly[i + 1] = 1;
402 for (j = i; j > 0; j--)
403 genpoly[j] = genpoly[j]
404 ? genpoly[j - 1] ^ gexp(modnn(glog(genpoly[j]) + i)) : genpoly[j - 1];
405 genpoly[0] = gexp(modnn(glog(genpoly[0]) + i));
406 }
407 for (i = 0; i <= eclen; i++)
408 genpoly[i] = glog(genpoly[i]); // use logs for genpoly[]
409 }
410
appendrs(unsigned char * data,unsigned char dlen,unsigned char * ecbuf,unsigned char eclen,unsigned char * genpoly)411 static void appendrs(unsigned char *data, unsigned char dlen,
412 unsigned char *ecbuf, unsigned char eclen, unsigned char *genpoly)
413 {
414 unsigned char i, j, fb;
415
416 memset(ecbuf, 0, eclen);
417 for (i = 0; i < dlen; i++) {
418 fb = glog(data[i] ^ ecbuf[0]);
419 if (fb != 255) /* fb term is non-zero */
420 for (j = 1; j < eclen; j++)
421 ecbuf[j-1] = ecbuf[j] ^ gexp(modnn(fb + genpoly[eclen - j]));
422 else
423 memmove(ecbuf, ecbuf + 1, eclen - 1);
424 ecbuf[eclen - 1] = fb == 255 ? 0 : gexp(modnn(fb + genpoly[0]));
425 }
426 }
427
428 //========================================================================
429 // 8 bit data to QR-coded 8 bit data
stringtoqr(qr_t * qr)430 static void stringtoqr (qr_t * qr)
431 {
432 unsigned i;
433 unsigned size, max;
434
435 assert (qr->initialized);
436 assert (qr->input);
437 assert (qr->input_length > 0);
438
439 memcpy (qr->strinbuf, (unsigned char *) qr->input, qr->input_length);
440 size = qr->input_length;
441
442 max = qr->datablkw * (qr->neccblk1 + qr->neccblk2) + qr->neccblk2;
443 if (size >= max - 2) {
444 size = max - 2;
445 if (qr->version > 9)
446 size--;
447 }
448
449 i = size;
450 if (qr->version > 9) {
451 qr->strinbuf[i + 2] = 0;
452 while (i--) {
453 qr->strinbuf[i + 3] |= qr->strinbuf[i] << 4;
454 qr->strinbuf[i + 2] = qr->strinbuf[i] >> 4;
455 }
456 qr->strinbuf[2] |= size << 4;
457 qr->strinbuf[1] = size >> 4;
458 qr->strinbuf[0] = 0x40 | (size >> 12);
459 }
460 else {
461 qr->strinbuf[i + 1] = 0;
462 while (i--) {
463 qr->strinbuf[i + 2] |= qr->strinbuf[i] << 4;
464 qr->strinbuf[i + 1] = qr->strinbuf[i] >> 4;
465 }
466 qr->strinbuf[1] |= size << 4;
467 qr->strinbuf[0] = 0x40 | (size >> 4);
468 }
469 i = size + 3 - (qr->version < 10);
470 while (i < max) {
471 qr->strinbuf[i++] = 0xec;
472 // buffer has room if (i == max) break;
473 qr->strinbuf[i++] = 0x11;
474 }
475
476 // calculate and append ECC
477 unsigned char *ecc = &qr->strinbuf[max];
478 unsigned char *dat = qr->strinbuf;
479 initrspoly(qr->eccblkwid,qr->qrframe);
480
481 for (i = 0; i < qr->neccblk1; i++) {
482 appendrs(dat, qr->datablkw, ecc, qr->eccblkwid, qr->qrframe);
483 dat += qr->datablkw;
484 ecc += qr->eccblkwid;
485 }
486 for (i = 0; i < qr->neccblk2; i++) {
487 appendrs(dat, qr->datablkw + 1, ecc, qr->eccblkwid, qr->qrframe);
488 dat += qr->datablkw + 1;
489 ecc += qr->eccblkwid;
490 }
491 unsigned j;
492 dat = qr->qrframe;
493 for (i = 0; i < qr->datablkw; i++) {
494 for (j = 0; j < qr->neccblk1; j++)
495 *dat++ = qr->strinbuf[i + j * qr->datablkw];
496 for (j = 0; j < qr->neccblk2; j++)
497 *dat++ = qr->strinbuf[(qr->neccblk1 * qr->datablkw) + i + (j * (qr->datablkw + 1))];
498 }
499 for (j = 0; j < qr->neccblk2; j++)
500 *dat++ = qr->strinbuf[(qr->neccblk1 * qr->datablkw) + i + (j * (qr->datablkw + 1))];
501 for (i = 0; i < qr->eccblkwid; i++)
502 for (j = 0; j < qr->neccblk1 + qr->neccblk2; j++)
503 *dat++ = qr->strinbuf[max + i + j * qr->eccblkwid];
504 memcpy(qr->strinbuf, qr->qrframe, max + qr->eccblkwid * (qr->neccblk1 + qr->neccblk2));
505
506 }
507
508 //========================================================================
509 // Frame data insert following the path rules
ismasked(qr_t * qr,unsigned char x,unsigned char y)510 static unsigned char ismasked(qr_t * qr, unsigned char x, unsigned char y)
511 {
512 unsigned bt;
513 if (x > y) {
514 bt = x;
515 x = y;
516 y = bt;
517 }
518 bt = y;
519 bt += y * y;
520 bt >>= 1;
521 bt += x;
522 return ((qr->framask[bt >> 3]) >> (7 - (bt & 7))) & 1;
523 }
524
fillframe(qr_t * qr)525 static void fillframe(qr_t * qr)
526 {
527 unsigned i;
528 unsigned char d, j;
529 unsigned char x, y, ffdecy, ffgohv;
530
531 memcpy (qr->qrframe, qr->framebase, qr->WDB * qr->WD);
532 x = y = qr->WD - 1;
533 ffdecy = 1; // up, minus
534 ffgohv = 1;
535
536 /* inteleaved data and ecc codes */
537 for (i = 0; i < ((qr->datablkw + qr->eccblkwid) * (qr->neccblk1 + qr->neccblk2) + qr->neccblk2); i++) {
538 d = qr->strinbuf[i];
539 for (j = 0; j < 8; j++, d <<= 1) {
540 if (0x80 & d)
541 SETQRBIT(qrframe,x, y);
542 do { // find next fill position
543 if (ffgohv)
544 x--;
545 else {
546 x++;
547 if (ffdecy) {
548 if (y != 0)
549 y--;
550 else {
551 x -= 2;
552 ffdecy = !ffdecy;
553 if (x == 6) {
554 x--;
555 y = 9;
556 }
557 }
558 } else {
559 if (y != qr->WD - 1)
560 y++;
561 else {
562 x -= 2;
563 ffdecy = !ffdecy;
564 if (x == 6) {
565 x--;
566 y -= 8;
567 }
568 }
569 }
570 }
571 ffgohv = !ffgohv;
572 /* This was found by valgrind, sometimes x goes to 255
573 and it tries to read from uninitialized memory. */
574 if (x > qr->WD - 1 || y > qr->WD - 1) {
575 break;
576 //fprintf (stderr, "%d %d\n", x, y);
577 }
578 } while (ismasked(qr, x, y));
579 }
580 }
581 }
582
583 //========================================================================
584 // Masking
applymask(qr_t * qr,unsigned char m)585 static void applymask(qr_t * qr, unsigned char m)
586 {
587 unsigned char x, y, r3x, r3y;
588
589 switch (m) {
590 case 0:
591 for (y = 0; y < qr->WD; y++)
592 for (x = 0; x < qr->WD; x++)
593 if (!((x + y) & 1) && !ismasked(qr, x, y))
594 TOGQRBIT(qrframe,x, y);
595 break;
596 case 1:
597 for (y = 0; y < qr->WD; y++)
598 for (x = 0; x < qr->WD; x++)
599 if (!(y & 1) && !ismasked(qr,x, y))
600 TOGQRBIT(qrframe,x, y);
601 break;
602 case 2:
603 for (y = 0; y < qr->WD; y++)
604 for (r3x = 0, x = 0; x < qr->WD; x++, r3x++) {
605 if (r3x == 3)
606 r3x = 0;
607 if (!r3x && !ismasked(qr,x, y))
608 TOGQRBIT(qrframe,x, y);
609 }
610 break;
611 case 3:
612 for (r3y = 0, y = 0; y < qr->WD; y++, r3y++) {
613 if (r3y == 3)
614 r3y = 0;
615 for (r3x = r3y, x = 0; x < qr->WD; x++, r3x++) {
616 if (r3x == 3)
617 r3x = 0;
618 if (!r3x && !ismasked(qr,x, y))
619 TOGQRBIT(qrframe,x, y);
620 }
621 }
622 break;
623 case 4:
624 for (y = 0; y < qr->WD; y++)
625 for (r3x = 0, r3y = ((y >> 1) & 1), x = 0; x < qr->WD; x++, r3x++) {
626 if (r3x == 3) {
627 r3x = 0;
628 r3y = !r3y;
629 }
630 if (!r3y && !ismasked(qr,x, y))
631 TOGQRBIT(qrframe,x, y);
632 }
633 break;
634 case 5:
635 for (r3y = 0, y = 0; y < qr->WD; y++, r3y++) {
636 if (r3y == 3)
637 r3y = 0;
638 for (r3x = 0, x = 0; x < qr->WD; x++, r3x++) {
639 if (r3x == 3)
640 r3x = 0;
641 if (!((x & y & 1) + !(!r3x | !r3y)) && !ismasked(qr,x, y))
642 TOGQRBIT(qrframe,x, y);
643 }
644 }
645 break;
646 case 6:
647 for (r3y = 0, y = 0; y < qr->WD; y++, r3y++) {
648 if (r3y == 3)
649 r3y = 0;
650 for (r3x = 0, x = 0; x < qr->WD; x++, r3x++) {
651 if (r3x == 3)
652 r3x = 0;
653 if (!(((x & y & 1) + (r3x && (r3x == r3y))) & 1) && !ismasked(qr,x, y))
654 TOGQRBIT(qrframe,x, y);
655 }
656 }
657 break;
658 case 7:
659 for (r3y = 0, y = 0; y < qr->WD; y++, r3y++) {
660 if (r3y == 3)
661 r3y = 0;
662 for (r3x = 0, x = 0; x < qr->WD; x++, r3x++) {
663 if (r3x == 3)
664 r3x = 0;
665 if (!(((r3x && (r3x == r3y)) + ((x + y) & 1)) & 1) && !ismasked(qr,x, y))
666 TOGQRBIT(qrframe,x, y);
667 }
668 }
669 break;
670 }
671 return;
672 }
673
674 // Badness coefficients.
675 static const unsigned char N1 = 3;
676 static const unsigned char N2 = 3;
677 static const unsigned char N3 = 40;
678 static const unsigned char N4 = 10;
679
badruns(qr_t * qr,unsigned char length)680 static unsigned badruns(qr_t * qr, unsigned char length)
681 {
682 unsigned char i;
683 unsigned runsbad = 0;
684 for (i = 0; i <= length; i++)
685 if (qr->rlens[i] >= 5)
686 runsbad += N1 + qr->rlens[i] - 5;
687 // BwBBBwB
688 for (i = 3; i < length - 1; i += 2)
689 if (qr->rlens[i - 2] == qr->rlens[i + 2]
690 && qr->rlens[i + 2] == qr->rlens[i - 1]
691 && qr->rlens[i - 1] == qr->rlens[i + 1]
692 && qr->rlens[i - 1] * 3 == qr->rlens[i]
693 // white around the black pattern? Not part of spec
694 && (qr->rlens[i - 3] == 0 // beginning
695 || i + 3 > length // end
696 || qr->rlens[i - 3] * 3 >= qr->rlens[i] * 4 || qr->rlens[i + 3] * 3 >= qr->rlens[i] * 4)
697 )
698 runsbad += N3;
699 return runsbad;
700 }
701
badcheck(qr_t * qr)702 static int badcheck(qr_t * qr)
703 {
704 unsigned char x, y, h, b, b1;
705 unsigned thisbad = 0;
706 int bw = 0;
707
708 // blocks of same color.
709 for (y = 0; y < qr->WD - 1; y++)
710 for (x = 0; x < qr->WD - 1; x++)
711 if ((QRBIT(qrframe,x, y) && QRBIT(qrframe,x + 1, y) && QRBIT(qrframe,x, y + 1) && QRBIT(qrframe,x + 1, y + 1)) // all black
712 || !(QRBIT(qrframe,x, y) || QRBIT(qrframe,x + 1, y) || QRBIT(qrframe,x, y + 1) || QRBIT(qrframe,x + 1, y + 1))) // all white
713 thisbad += N2;
714
715 // X runs
716 for (y = 0; y < qr->WD; y++) {
717 qr->rlens[0] = 0;
718 for (h = b = x = 0; x < qr->WD; x++) {
719 if ((b1 = QRBIT(qrframe,x, y)) == b)
720 qr->rlens[h]++;
721 else
722 qr->rlens[++h] = 1;
723 b = b1;
724 bw += b ? 1 : -1;
725 }
726 thisbad += badruns(qr, h);
727 }
728
729 // black/white imbalance
730 if (bw < 0)
731 bw = -bw;
732
733 unsigned long big = bw;
734 unsigned count = 0;
735 big += big << 2;
736 big <<= 1;
737 while (big > qr->WD * qr->WD)
738 big -= qr->WD * qr->WD, count++;
739 thisbad += count * N4;
740
741 // Y runs
742 for (x = 0; x < qr->WD; x++) {
743 qr->rlens[0] = 0;
744 for (h = b = y = 0; y < qr->WD; y++) {
745 if ((b1 = QRBIT(qrframe,x, y)) == b)
746 qr->rlens[h]++;
747 else
748 qr->rlens[++h] = 1;
749 b = b1;
750 }
751 thisbad += badruns(qr, h);
752 }
753 return thisbad;
754 }
755
756 // final format bits with mask
757 // level << 3 | mask
758 static const unsigned fmtword[] = {
759 0x77c4, 0x72f3, 0x7daa, 0x789d, 0x662f, 0x6318, 0x6c41, 0x6976, //L
760 0x5412, 0x5125, 0x5e7c, 0x5b4b, 0x45f9, 0x40ce, 0x4f97, 0x4aa0, //M
761 0x355f, 0x3068, 0x3f31, 0x3a06, 0x24b4, 0x2183, 0x2eda, 0x2bed, //Q
762 0x1689, 0x13be, 0x1ce7, 0x19d0, 0x0762, 0x0255, 0x0d0c, 0x083b, //H
763 };
764
addfmt(qr_t * qr,unsigned char masknum)765 static void addfmt(qr_t * qr, unsigned char masknum)
766 {
767 unsigned fmtbits;
768 unsigned char i, lvl = qr->level - 1;
769
770 fmtbits = fmtword[masknum + (lvl << 3)];
771 // low byte
772 for (i = 0; i < 8; i++, fmtbits >>= 1)
773 if (fmtbits & 1) {
774 SETQRBIT(qrframe,qr->WD - 1 - i, 8);
775 if (i < 6)
776 SETQRBIT(qrframe,8, i);
777 else
778 SETQRBIT(qrframe,8, i + 1);
779 }
780 // high byte
781 for (i = 0; i < 7; i++, fmtbits >>= 1)
782 if (fmtbits & 1) {
783 SETQRBIT(qrframe,8, qr->WD - 7 + i);
784 if (i)
785 SETQRBIT(qrframe,6 - i, 8);
786 else
787 SETQRBIT(qrframe,7, 8);
788 }
789 }
790
qrencode(qr_t * qr)791 void qrencode(qr_t * qr)
792 {
793 unsigned mindem = 30000;
794 unsigned char best = 0;
795 unsigned char i;
796 unsigned badness;
797 unsigned qrsize;
798
799 qrsize = qr->WD * qr->WDB;
800 assert (qrsize > 0);
801
802 stringtoqr(qr);
803 // Inisde loop to avoid having separate mask buffer
804 fillframe(qr);
805 memcpy(qr->strinbuf, qr->qrframe, qrsize);
806 for (i = 0; i < 8; i++) {
807 applymask(qr,i); // returns black-white imbalance
808 badness = badcheck(qr);
809 if (badness < mindem) {
810 mindem = badness;
811 best = i;
812 }
813 if (best == 7)
814 break; // don't increment i to avoid redoing mask
815 memcpy(qr->qrframe, qr->strinbuf, qrsize); // reset filled frame
816 }
817 if (best != i) {
818 // redo best mask - none good enough, last wasn't best
819 applymask(qr,best);
820 }
821 addfmt(qr,best); // add in final format bytes
822 }
823
qrfree(qr_t * qr)824 void qrfree (qr_t * qr)
825 {
826 freeframe (qr);
827 }
828