git.sur5r.net Git - glabels/blob - qrencode-3.1.0/qrspec.c

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