1 /*
2 * qrencode - QR Code encoder
3 *
4 * QR Code specification in convenient format.
5 * Copyright (C) 2006-2011 Kentaro Fukuchi <kentaro@fukuchi.org>
6 *
7 * The following data / specifications are taken from
8 * "Two dimensional symbol -- QR-code -- Basic Specification" (JIS X0510:2004)
9 * or
10 * "Automatic identification and data capture techniques --
11 * QR Code 2005 bar code symbology specification" (ISO/IEC 18004:2006)
12 *
13 * This library is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU Lesser General Public
15 * License as published by the Free Software Foundation; either
16 * version 2.1 of the License, or any later version.
17 *
18 * This library is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 * Lesser General Public License for more details.
22 *
23 * You should have received a copy of the GNU Lesser General Public
24 * License along with this library; if not, write to the Free Software
25 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
26 */
27
28 #if HAVE_CONFIG_H
29 # include "config.h"
30 #endif
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <errno.h>
35 #ifdef HAVE_LIBPTHREAD
36 #include <pthread.h>
37 #endif
38
39 #include "qrspec.h"
40 #include "qrinput.h"
41
42 /******************************************************************************
43 * Version and capacity
44 *****************************************************************************/
45
46 typedef struct {
47 int width; //< Edge length of the symbol
48 int words; //< Data capacity (bytes)
49 int remainder; //< Remainder bit (bits)
50 int ec[4]; //< Number of ECC code (bytes)
51 } QRspec_Capacity;
52
53 /**
54 * Table of the capacity of symbols
55 * See Table 1 (pp.13) and Table 12-16 (pp.30-36), JIS X0510:2004.
56 */
57 static const QRspec_Capacity qrspecCapacity[QRSPEC_VERSION_MAX + 1] = {
58 { 0, 0, 0, { 0, 0, 0, 0}},
59 { 21, 26, 0, { 7, 10, 13, 17}}, // 1
60 { 25, 44, 7, { 10, 16, 22, 28}},
61 { 29, 70, 7, { 15, 26, 36, 44}},
62 { 33, 100, 7, { 20, 36, 52, 64}},
63 { 37, 134, 7, { 26, 48, 72, 88}}, // 5
64 { 41, 172, 7, { 36, 64, 96, 112}},
65 { 45, 196, 0, { 40, 72, 108, 130}},
66 { 49, 242, 0, { 48, 88, 132, 156}},
67 { 53, 292, 0, { 60, 110, 160, 192}},
68 { 57, 346, 0, { 72, 130, 192, 224}}, //10
69 { 61, 404, 0, { 80, 150, 224, 264}},
70 { 65, 466, 0, { 96, 176, 260, 308}},
71 { 69, 532, 0, { 104, 198, 288, 352}},
72 { 73, 581, 3, { 120, 216, 320, 384}},
73 { 77, 655, 3, { 132, 240, 360, 432}}, //15
74 { 81, 733, 3, { 144, 280, 408, 480}},
75 { 85, 815, 3, { 168, 308, 448, 532}},
76 { 89, 901, 3, { 180, 338, 504, 588}},
77 { 93, 991, 3, { 196, 364, 546, 650}},
78 { 97, 1085, 3, { 224, 416, 600, 700}}, //20
79 {101, 1156, 4, { 224, 442, 644, 750}},
80 {105, 1258, 4, { 252, 476, 690, 816}},
81 {109, 1364, 4, { 270, 504, 750, 900}},
82 {113, 1474, 4, { 300, 560, 810, 960}},
83 {117, 1588, 4, { 312, 588, 870, 1050}}, //25
84 {121, 1706, 4, { 336, 644, 952, 1110}},
85 {125, 1828, 4, { 360, 700, 1020, 1200}},
86 {129, 1921, 3, { 390, 728, 1050, 1260}},
87 {133, 2051, 3, { 420, 784, 1140, 1350}},
88 {137, 2185, 3, { 450, 812, 1200, 1440}}, //30
89 {141, 2323, 3, { 480, 868, 1290, 1530}},
90 {145, 2465, 3, { 510, 924, 1350, 1620}},
91 {149, 2611, 3, { 540, 980, 1440, 1710}},
92 {153, 2761, 3, { 570, 1036, 1530, 1800}},
93 {157, 2876, 0, { 570, 1064, 1590, 1890}}, //35
94 {161, 3034, 0, { 600, 1120, 1680, 1980}},
95 {165, 3196, 0, { 630, 1204, 1770, 2100}},
96 {169, 3362, 0, { 660, 1260, 1860, 2220}},
97 {173, 3532, 0, { 720, 1316, 1950, 2310}},
98 {177, 3706, 0, { 750, 1372, 2040, 2430}} //40
99 };
100
QRspec_getDataLength(int version,QRecLevel level)101 int QRspec_getDataLength(int version, QRecLevel level)
102 {
103 return qrspecCapacity[version].words - qrspecCapacity[version].ec[level];
104 }
105
QRspec_getECCLength(int version,QRecLevel level)106 int QRspec_getECCLength(int version, QRecLevel level)
107 {
108 return qrspecCapacity[version].ec[level];
109 }
110
QRspec_getMinimumVersion(int size,QRecLevel level)111 int QRspec_getMinimumVersion(int size, QRecLevel level)
112 {
113 int i;
114 int words;
115
116 for(i=1; i<= QRSPEC_VERSION_MAX; i++) {
117 words = qrspecCapacity[i].words - qrspecCapacity[i].ec[level];
118 if(words >= size) return i;
119 }
120
121 return -1;
122 }
123
QRspec_getWidth(int version)124 int QRspec_getWidth(int version)
125 {
126 return qrspecCapacity[version].width;
127 }
128
QRspec_getRemainder(int version)129 int QRspec_getRemainder(int version)
130 {
131 return qrspecCapacity[version].remainder;
132 }
133
134 /******************************************************************************
135 * Length indicator
136 *****************************************************************************/
137
138 static const int lengthTableBits[4][3] = {
139 {10, 12, 14},
140 { 9, 11, 13},
141 { 8, 16, 16},
142 { 8, 10, 12}
143 };
144
QRspec_lengthIndicator(QRencodeMode mode,int version)145 int QRspec_lengthIndicator(QRencodeMode mode, int version)
146 {
147 int l;
148
149 if(!QRinput_isSplittableMode(mode)) return 0;
150 if(version <= 9) {
151 l = 0;
152 } else if(version <= 26) {
153 l = 1;
154 } else {
155 l = 2;
156 }
157
158 return lengthTableBits[mode][l];
159 }
160
QRspec_maximumWords(QRencodeMode mode,int version)161 int QRspec_maximumWords(QRencodeMode mode, int version)
162 {
163 int l;
164 int bits;
165 int words;
166
167 if(!QRinput_isSplittableMode(mode)) return 0;
168 if(version <= 9) {
169 l = 0;
170 } else if(version <= 26) {
171 l = 1;
172 } else {
173 l = 2;
174 }
175
176 bits = lengthTableBits[mode][l];
177 words = (1 << bits) - 1;
178 if(mode == QR_MODE_KANJI) {
179 words *= 2; // the number of bytes is required
180 }
181
182 return words;
183 }
184
185 /******************************************************************************
186 * Error correction code
187 *****************************************************************************/
188
189 /**
190 * Table of the error correction code (Reed-Solomon block)
191 * See Table 12-16 (pp.30-36), JIS X0510:2004.
192 */
193 static const int eccTable[QRSPEC_VERSION_MAX+1][4][2] = {
194 {{ 0, 0}, { 0, 0}, { 0, 0}, { 0, 0}},
195 {{ 1, 0}, { 1, 0}, { 1, 0}, { 1, 0}}, // 1
196 {{ 1, 0}, { 1, 0}, { 1, 0}, { 1, 0}},
197 {{ 1, 0}, { 1, 0}, { 2, 0}, { 2, 0}},
198 {{ 1, 0}, { 2, 0}, { 2, 0}, { 4, 0}},
199 {{ 1, 0}, { 2, 0}, { 2, 2}, { 2, 2}}, // 5
200 {{ 2, 0}, { 4, 0}, { 4, 0}, { 4, 0}},
201 {{ 2, 0}, { 4, 0}, { 2, 4}, { 4, 1}},
202 {{ 2, 0}, { 2, 2}, { 4, 2}, { 4, 2}},
203 {{ 2, 0}, { 3, 2}, { 4, 4}, { 4, 4}},
204 {{ 2, 2}, { 4, 1}, { 6, 2}, { 6, 2}}, //10
205 {{ 4, 0}, { 1, 4}, { 4, 4}, { 3, 8}},
206 {{ 2, 2}, { 6, 2}, { 4, 6}, { 7, 4}},
207 {{ 4, 0}, { 8, 1}, { 8, 4}, {12, 4}},
208 {{ 3, 1}, { 4, 5}, {11, 5}, {11, 5}},
209 {{ 5, 1}, { 5, 5}, { 5, 7}, {11, 7}}, //15
210 {{ 5, 1}, { 7, 3}, {15, 2}, { 3, 13}},
211 {{ 1, 5}, {10, 1}, { 1, 15}, { 2, 17}},
212 {{ 5, 1}, { 9, 4}, {17, 1}, { 2, 19}},
213 {{ 3, 4}, { 3, 11}, {17, 4}, { 9, 16}},
214 {{ 3, 5}, { 3, 13}, {15, 5}, {15, 10}}, //20
215 {{ 4, 4}, {17, 0}, {17, 6}, {19, 6}},
216 {{ 2, 7}, {17, 0}, { 7, 16}, {34, 0}},
217 {{ 4, 5}, { 4, 14}, {11, 14}, {16, 14}},
218 {{ 6, 4}, { 6, 14}, {11, 16}, {30, 2}},
219 {{ 8, 4}, { 8, 13}, { 7, 22}, {22, 13}}, //25
220 {{10, 2}, {19, 4}, {28, 6}, {33, 4}},
221 {{ 8, 4}, {22, 3}, { 8, 26}, {12, 28}},
222 {{ 3, 10}, { 3, 23}, { 4, 31}, {11, 31}},
223 {{ 7, 7}, {21, 7}, { 1, 37}, {19, 26}},
224 {{ 5, 10}, {19, 10}, {15, 25}, {23, 25}}, //30
225 {{13, 3}, { 2, 29}, {42, 1}, {23, 28}},
226 {{17, 0}, {10, 23}, {10, 35}, {19, 35}},
227 {{17, 1}, {14, 21}, {29, 19}, {11, 46}},
228 {{13, 6}, {14, 23}, {44, 7}, {59, 1}},
229 {{12, 7}, {12, 26}, {39, 14}, {22, 41}}, //35
230 {{ 6, 14}, { 6, 34}, {46, 10}, { 2, 64}},
231 {{17, 4}, {29, 14}, {49, 10}, {24, 46}},
232 {{ 4, 18}, {13, 32}, {48, 14}, {42, 32}},
233 {{20, 4}, {40, 7}, {43, 22}, {10, 67}},
234 {{19, 6}, {18, 31}, {34, 34}, {20, 61}},//40
235 };
236
QRspec_getEccSpec(int version,QRecLevel level,int spec[5])237 void QRspec_getEccSpec(int version, QRecLevel level, int spec[5])
238 {
239 int b1, b2;
240 int data, ecc;
241
242 b1 = eccTable[version][level][0];
243 b2 = eccTable[version][level][1];
244 data = QRspec_getDataLength(version, level);
245 ecc = QRspec_getECCLength(version, level);
246
247 if(b2 == 0) {
248 spec[0] = b1;
249 spec[1] = data / b1;
250 spec[2] = ecc / b1;
251 spec[3] = spec[4] = 0;
252 } else {
253 spec[0] = b1;
254 spec[1] = data / (b1 + b2);
255 spec[2] = ecc / (b1 + b2);
256 spec[3] = b2;
257 spec[4] = spec[1] + 1;
258 }
259 }
260
261 /******************************************************************************
262 * Alignment pattern
263 *****************************************************************************/
264
265 /**
266 * Positions of alignment patterns.
267 * This array includes only the second and the third position of the alignment
268 * patterns. Rest of them can be calculated from the distance between them.
269 *
270 * See Table 1 in Appendix E (pp.71) of JIS X0510:2004.
271 */
272 static const int alignmentPattern[QRSPEC_VERSION_MAX+1][2] = {
273 { 0, 0},
274 { 0, 0}, {18, 0}, {22, 0}, {26, 0}, {30, 0}, // 1- 5
275 {34, 0}, {22, 38}, {24, 42}, {26, 46}, {28, 50}, // 6-10
276 {30, 54}, {32, 58}, {34, 62}, {26, 46}, {26, 48}, //11-15
277 {26, 50}, {30, 54}, {30, 56}, {30, 58}, {34, 62}, //16-20
278 {28, 50}, {26, 50}, {30, 54}, {28, 54}, {32, 58}, //21-25
279 {30, 58}, {34, 62}, {26, 50}, {30, 54}, {26, 52}, //26-30
280 {30, 56}, {34, 60}, {30, 58}, {34, 62}, {30, 54}, //31-35
281 {24, 50}, {28, 54}, {32, 58}, {26, 54}, {30, 58}, //35-40
282 };
283
284 /**
285 * Put an alignment marker.
286 * @param frame
287 * @param width
288 * @param ox,oy center coordinate of the pattern
289 */
QRspec_putAlignmentMarker(unsigned char * frame,int width,int ox,int oy)290 static void QRspec_putAlignmentMarker(unsigned char *frame, int width, int ox, int oy)
291 {
292 static const unsigned char finder[] = {
293 0xa1, 0xa1, 0xa1, 0xa1, 0xa1,
294 0xa1, 0xa0, 0xa0, 0xa0, 0xa1,
295 0xa1, 0xa0, 0xa1, 0xa0, 0xa1,
296 0xa1, 0xa0, 0xa0, 0xa0, 0xa1,
297 0xa1, 0xa1, 0xa1, 0xa1, 0xa1,
298 };
299 int x, y;
300 const unsigned char *s;
301
302 frame += (oy - 2) * width + ox - 2;
303 s = finder;
304 for(y=0; y<5; y++) {
305 for(x=0; x<5; x++) {
306 frame[x] = s[x];
307 }
308 frame += width;
309 s += 5;
310 }
311 }
312
QRspec_putAlignmentPattern(int version,unsigned char * frame,int width)313 static void QRspec_putAlignmentPattern(int version, unsigned char *frame, int width)
314 {
315 int d, w, x, y, cx, cy;
316
317 if(version < 2) return;
318
319 d = alignmentPattern[version][1] - alignmentPattern[version][0];
320 if(d < 0) {
321 w = 2;
322 } else {
323 w = (width - alignmentPattern[version][0]) / d + 2;
324 }
325
326 if(w * w - 3 == 1) {
327 x = alignmentPattern[version][0];
328 y = alignmentPattern[version][0];
329 QRspec_putAlignmentMarker(frame, width, x, y);
330 return;
331 }
332
333 cx = alignmentPattern[version][0];
334 for(x=1; x<w - 1; x++) {
335 QRspec_putAlignmentMarker(frame, width, 6, cx);
336 QRspec_putAlignmentMarker(frame, width, cx, 6);
337 cx += d;
338 }
339
340 cy = alignmentPattern[version][0];
341 for(y=0; y<w-1; y++) {
342 cx = alignmentPattern[version][0];
343 for(x=0; x<w-1; x++) {
344 QRspec_putAlignmentMarker(frame, width, cx, cy);
345 cx += d;
346 }
347 cy += d;
348 }
349 }
350
351 /******************************************************************************
352 * Version information pattern
353 *****************************************************************************/
354
355 /**
356 * Version information pattern (BCH coded).
357 * See Table 1 in Appendix D (pp.68) of JIS X0510:2004.
358 */
359 static const unsigned int versionPattern[QRSPEC_VERSION_MAX - 6] = {
360 0x07c94, 0x085bc, 0x09a99, 0x0a4d3, 0x0bbf6, 0x0c762, 0x0d847, 0x0e60d,
361 0x0f928, 0x10b78, 0x1145d, 0x12a17, 0x13532, 0x149a6, 0x15683, 0x168c9,
362 0x177ec, 0x18ec4, 0x191e1, 0x1afab, 0x1b08e, 0x1cc1a, 0x1d33f, 0x1ed75,
363 0x1f250, 0x209d5, 0x216f0, 0x228ba, 0x2379f, 0x24b0b, 0x2542e, 0x26a64,
364 0x27541, 0x28c69
365 };
366
QRspec_getVersionPattern(int version)367 unsigned int QRspec_getVersionPattern(int version)
368 {
369 if(version < 7 || version > QRSPEC_VERSION_MAX) return 0;
370
371 return versionPattern[version - 7];
372 }
373
374 /******************************************************************************
375 * Format information
376 *****************************************************************************/
377
378 /* See calcFormatInfo in tests/test_qrspec.c */
379 static const unsigned int formatInfo[4][8] = {
380 {0x77c4, 0x72f3, 0x7daa, 0x789d, 0x662f, 0x6318, 0x6c41, 0x6976},
381 {0x5412, 0x5125, 0x5e7c, 0x5b4b, 0x45f9, 0x40ce, 0x4f97, 0x4aa0},
382 {0x355f, 0x3068, 0x3f31, 0x3a06, 0x24b4, 0x2183, 0x2eda, 0x2bed},
383 {0x1689, 0x13be, 0x1ce7, 0x19d0, 0x0762, 0x0255, 0x0d0c, 0x083b}
384 };
385
QRspec_getFormatInfo(int mask,QRecLevel level)386 unsigned int QRspec_getFormatInfo(int mask, QRecLevel level)
387 {
388 if(mask < 0 || mask > 7) return 0;
389
390 return formatInfo[level][mask];
391 }
392
393 /******************************************************************************
394 * Frame
395 *****************************************************************************/
396
397 /**
398 * Cache of initial frames.
399 */
400 /* C99 says that static storage shall be initialized to a null pointer
401 * by compiler. */
402 static unsigned char *frames[QRSPEC_VERSION_MAX + 1];
403 #ifdef HAVE_LIBPTHREAD
404 static pthread_mutex_t frames_mutex = PTHREAD_MUTEX_INITIALIZER;
405 #endif
406
407 /**
408 * Put a finder pattern.
409 * @param frame
410 * @param width
411 * @param ox,oy upper-left coordinate of the pattern
412 */
putFinderPattern(unsigned char * frame,int width,int ox,int oy)413 static void putFinderPattern(unsigned char *frame, int width, int ox, int oy)
414 {
415 static const unsigned char finder[] = {
416 0xc1, 0xc1, 0xc1, 0xc1, 0xc1, 0xc1, 0xc1,
417 0xc1, 0xc0, 0xc0, 0xc0, 0xc0, 0xc0, 0xc1,
418 0xc1, 0xc0, 0xc1, 0xc1, 0xc1, 0xc0, 0xc1,
419 0xc1, 0xc0, 0xc1, 0xc1, 0xc1, 0xc0, 0xc1,
420 0xc1, 0xc0, 0xc1, 0xc1, 0xc1, 0xc0, 0xc1,
421 0xc1, 0xc0, 0xc0, 0xc0, 0xc0, 0xc0, 0xc1,
422 0xc1, 0xc1, 0xc1, 0xc1, 0xc1, 0xc1, 0xc1,
423 };
424 int x, y;
425 const unsigned char *s;
426
427 frame += oy * width + ox;
428 s = finder;
429 for(y=0; y<7; y++) {
430 for(x=0; x<7; x++) {
431 frame[x] = s[x];
432 }
433 frame += width;
434 s += 7;
435 }
436 }
437
438
QRspec_createFrame(int version)439 static unsigned char *QRspec_createFrame(int version)
440 {
441 unsigned char *frame, *p, *q;
442 int width;
443 int x, y;
444 unsigned int verinfo, v;
445
446 width = qrspecCapacity[version].width;
447 frame = (unsigned char *)malloc(width * width);
448 if(frame == NULL) return NULL;
449
450 memset(frame, 0, width * width);
451 /* Finder pattern */
452 putFinderPattern(frame, width, 0, 0);
453 putFinderPattern(frame, width, width - 7, 0);
454 putFinderPattern(frame, width, 0, width - 7);
455 /* Separator */
456 p = frame;
457 q = frame + width * (width - 7);
458 for(y=0; y<7; y++) {
459 p[7] = 0xc0;
460 p[width - 8] = 0xc0;
461 q[7] = 0xc0;
462 p += width;
463 q += width;
464 }
465 memset(frame + width * 7, 0xc0, 8);
466 memset(frame + width * 8 - 8, 0xc0, 8);
467 memset(frame + width * (width - 8), 0xc0, 8);
468 /* Mask format information area */
469 memset(frame + width * 8, 0x84, 9);
470 memset(frame + width * 9 - 8, 0x84, 8);
471 p = frame + 8;
472 for(y=0; y<8; y++) {
473 *p = 0x84;
474 p += width;
475 }
476 p = frame + width * (width - 7) + 8;
477 for(y=0; y<7; y++) {
478 *p = 0x84;
479 p += width;
480 }
481 /* Timing pattern */
482 p = frame + width * 6 + 8;
483 q = frame + width * 8 + 6;
484 for(x=1; x<width-15; x++) {
485 *p = 0x90 | (x & 1);
486 *q = 0x90 | (x & 1);
487 p++;
488 q += width;
489 }
490 /* Alignment pattern */
491 QRspec_putAlignmentPattern(version, frame, width);
492
493 /* Version information */
494 if(version >= 7) {
495 verinfo = QRspec_getVersionPattern(version);
496
497 p = frame + width * (width - 11);
498 v = verinfo;
499 for(x=0; x<6; x++) {
500 for(y=0; y<3; y++) {
501 p[width * y + x] = 0x88 | (v & 1);
502 v = v >> 1;
503 }
504 }
505
506 p = frame + width - 11;
507 v = verinfo;
508 for(y=0; y<6; y++) {
509 for(x=0; x<3; x++) {
510 p[x] = 0x88 | (v & 1);
511 v = v >> 1;
512 }
513 p += width;
514 }
515 }
516 /* and a little bit... */
517 frame[width * (width - 8) + 8] = 0x81;
518
519 return frame;
520 }
521
QRspec_newFrame(int version)522 unsigned char *QRspec_newFrame(int version)
523 {
524 unsigned char *frame;
525 int width;
526
527 if(version < 1 || version > QRSPEC_VERSION_MAX) return NULL;
528
529 #ifdef HAVE_LIBPTHREAD
530 pthread_mutex_lock(&frames_mutex);
531 #endif
532 if(frames[version] == NULL) {
533 frames[version] = QRspec_createFrame(version);
534 }
535 #ifdef HAVE_LIBPTHREAD
536 pthread_mutex_unlock(&frames_mutex);
537 #endif
538 if(frames[version] == NULL) return NULL;
539
540 width = qrspecCapacity[version].width;
541 frame = (unsigned char *)malloc(width * width);
542 if(frame == NULL) return NULL;
543 memcpy(frame, frames[version], width * width);
544
545 return frame;
546 }
547
QRspec_clearCache(void)548 void QRspec_clearCache(void)
549 {
550 int i;
551
552 #ifdef HAVE_LIBPTHREAD
553 pthread_mutex_lock(&frames_mutex);
554 #endif
555 for(i=1; i<=QRSPEC_VERSION_MAX; i++) {
556 free(frames[i]);
557 frames[i] = NULL;
558 }
559 #ifdef HAVE_LIBPTHREAD
560 pthread_mutex_unlock(&frames_mutex);
561 #endif
562 }
563