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 46typedef 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 */ 57static 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 101int QRspec_getDataLength(int version, QRecLevel level) 102{ 103 return qrspecCapacity[version].words - qrspecCapacity[version].ec[level]; 104} 105 106int QRspec_getECCLength(int version, QRecLevel level) 107{ 108 return qrspecCapacity[version].ec[level]; 109} 110 111int 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 124int QRspec_getWidth(int version) 125{ 126 return qrspecCapacity[version].width; 127} 128 129int QRspec_getRemainder(int version) 130{ 131 return qrspecCapacity[version].remainder; 132} 133 134/****************************************************************************** 135 * Length indicator 136 *****************************************************************************/ 137 138static const int lengthTableBits[4][3] = { 139 {10, 12, 14}, 140 { 9, 11, 13}, 141 { 8, 16, 16}, 142 { 8, 10, 12} 143}; 144 145int 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 161int 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 */ 193static 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 237void 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 */ 272static 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 */ 290static 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 313static 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 */ 359static 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 367unsigned 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 */ 379static 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 386unsigned 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. */ 402static unsigned char *frames[QRSPEC_VERSION_MAX + 1]; 403#ifdef HAVE_LIBPTHREAD 404static 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 */ 413static 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 439static 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 522unsigned 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 548void 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