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

   1 /*
   2  * qrencode - QR Code encoder
   3  *
   4  * Input data chunk class
   5  * Copyright (C) 2006, 2007, 2008, 2009 Kentaro Fukuchi <fukuchi@megaui.net>
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  20  */
  21
  22 #include <stdio.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <errno.h>
  26
  27 #include "config.h"
  28 #include "qrencode.h"
  29 #include "qrspec.h"
  30 #include "bitstream.h"
  31 #include "qrinput.h"
  32
  33 /******************************************************************************
  34  * Entry of input data
  35  *****************************************************************************/
  36
  37 static QRinput_List *QRinput_List_newEntry(QRencodeMode mode, int size, const unsigned char *data)
  38 {
  39         QRinput_List *entry;
  40
  41         if(QRinput_check(mode, size, data)) {
  42                 errno = EINVAL;
  43                 return NULL;
  44         }
  45
  46         entry = (QRinput_List *)malloc(sizeof(QRinput_List));
  47         if(entry == NULL) return NULL;
  48
  49         entry->mode = mode;
  50         entry->size = size;
  51         entry->data = (unsigned char *)malloc(size);
  52         if(entry->data == NULL) {
  53                 free(entry);
  54                 return NULL;
  55         }
  56         memcpy(entry->data, data, size);
  57         entry->bstream = NULL;
  58         entry->next = NULL;
  59
  60         return entry;
  61 }
  62
  63 static void QRinput_List_freeEntry(QRinput_List *entry)
  64 {
  65         if(entry != NULL) {
  66                 free(entry->data);
  67                 BitStream_free(entry->bstream);
  68                 free(entry);
  69         }
  70 }
  71
  72 static QRinput_List *QRinput_List_dup(QRinput_List *entry)
  73 {
  74         QRinput_List *n;
  75
  76         n = (QRinput_List *)malloc(sizeof(QRinput_List));
  77         if(n == NULL) return NULL;
  78
  79         n->mode = entry->mode;
  80         n->size = entry->size;
  81         n->data = (unsigned char *)malloc(n->size);
  82         if(n->data == NULL) {
  83                 free(n);
  84                 return NULL;
  85         }
  86         memcpy(n->data, entry->data, entry->size);
  87         n->bstream = NULL;
  88         n->next = NULL;
  89
  90         return n;
  91 }
  92
  93 /******************************************************************************
  94  * Input Data
  95  *****************************************************************************/
  96
  97 QRinput *QRinput_new(void)
  98 {
  99         return QRinput_new2(0, QR_ECLEVEL_L);
 100 }
 101
 102 QRinput *QRinput_new2(int version, QRecLevel level)
 103 {
 104         QRinput *input;
 105
 106         if(version < 0 || version > QRSPEC_VERSION_MAX || level > QR_ECLEVEL_H) {
 107                 errno = EINVAL;
 108                 return NULL;
 109         }
 110
 111         input = (QRinput *)malloc(sizeof(QRinput));
 112         if(input == NULL) return NULL;
 113
 114         input->head = NULL;
 115         input->tail = NULL;
 116         input->version = version;
 117         input->level = level;
 118
 119         return input;
 120 }
 121
 122 int QRinput_getVersion(QRinput *input)
 123 {
 124         return input->version;
 125 }
 126
 127 int QRinput_setVersion(QRinput *input, int version)
 128 {
 129         if(version < 0 || version > QRSPEC_VERSION_MAX) {
 130                 errno = EINVAL;
 131                 return -1;
 132         }
 133
 134         input->version = version;
 135
 136         return 0;
 137 }
 138
 139 QRecLevel QRinput_getErrorCorrectionLevel(QRinput *input)
 140 {
 141         return input->level;
 142 }
 143
 144 int QRinput_setErrorCorrectionLevel(QRinput *input, QRecLevel level)
 145 {
 146         if(level > QR_ECLEVEL_H) {
 147                 errno = EINVAL;
 148                 return -1;
 149         }
 150
 151         input->level = level;
 152
 153         return 0;
 154 }
 155
 156 static void QRinput_appendEntry(QRinput *input, QRinput_List *entry)
 157 {
 158         if(input->tail == NULL) {
 159                 input->head = entry;
 160                 input->tail = entry;
 161         } else {
 162                 input->tail->next = entry;
 163                 input->tail = entry;
 164         }
 165         entry->next = NULL;
 166 }
 167
 168 int QRinput_append(QRinput *input, QRencodeMode mode, int size, const unsigned char *data)
 169 {
 170         QRinput_List *entry;
 171
 172         entry = QRinput_List_newEntry(mode, size, data);
 173         if(entry == NULL) {
 174                 return -1;
 175         }
 176
 177         QRinput_appendEntry(input, entry);
 178
 179         return 0;
 180 }
 181
 182 /**
 183  * Insert a structured-append header to the head of the input data.
 184  * @param input input data.
 185  * @param size number of structured symbols.
 186  * @param index index number of the symbol. (1 <= index <= size)
 187  * @param parity parity among input data. (NOTE: each symbol of a set of structured symbols has the same parity data)
 188  * @retval 0 success.
 189  * @retval -1 error occurred and errno is set to indeicate the error. See Execptions for the details.
 190  * @throw EINVAL invalid parameter.
 191  * @throw ENOMEM unable to allocate memory.
 192  */
 193 __STATIC int QRinput_insertStructuredAppendHeader(QRinput *input, int size, int index, unsigned char parity)
 194 {
 195         QRinput_List *entry;
 196         unsigned char buf[3];
 197
 198         if(size > MAX_STRUCTURED_SYMBOLS) {
 199                 errno = EINVAL;
 200                 return -1;
 201         }
 202         if(index <= 0 || index > MAX_STRUCTURED_SYMBOLS) {
 203                 errno = EINVAL;
 204                 return -1;
 205         }
 206
 207         buf[0] = (unsigned char)size;
 208         buf[1] = (unsigned char)index;
 209         buf[2] = parity;
 210         entry = QRinput_List_newEntry(QR_MODE_STRUCTURE, 3, buf);
 211         if(entry == NULL) {
 212                 return -1;
 213         }
 214
 215         entry->next = input->head;
 216         input->head = entry;
 217
 218         return 0;
 219 }
 220
 221 void QRinput_free(QRinput *input)
 222 {
 223         QRinput_List *list, *next;
 224
 225         if(input != NULL) {
 226                 list = input->head;
 227                 while(list != NULL) {
 228                         next = list->next;
 229                         QRinput_List_freeEntry(list);
 230                         list = next;
 231                 }
 232                 free(input);
 233         }
 234 }
 235
 236 static unsigned char QRinput_calcParity(QRinput *input)
 237 {
 238         unsigned char parity = 0;
 239         QRinput_List *list;
 240         int i;
 241
 242         list = input->head;
 243         while(list != NULL) {
 244                 if(list->mode != QR_MODE_STRUCTURE) {
 245                         for(i=list->size-1; i>=0; i--) {
 246                                 parity ^= list->data[i];
 247                         }
 248                 }
 249                 list = list->next;
 250         }
 251
 252         return parity;
 253 }
 254
 255 QRinput *QRinput_dup(QRinput *input)
 256 {
 257         QRinput *n;
 258         QRinput_List *list, *e;
 259
 260         n = QRinput_new2(input->version, input->level);
 261         if(n == NULL) return NULL;
 262
 263         list = input->head;
 264         while(list != NULL) {
 265                 e = QRinput_List_dup(list);
 266                 if(e == NULL) {
 267                         QRinput_free(n);
 268                         return NULL;
 269                 }
 270                 QRinput_appendEntry(n, e);
 271                 list = list->next;
 272         }
 273
 274         return n;
 275 }
 276
 277 /******************************************************************************
 278  * Numeric data
 279  *****************************************************************************/
 280
 281 /**
 282  * Check the input data.
 283  * @param size
 284  * @param data
 285  * @return result
 286  */
 287 static int QRinput_checkModeNum(int size, const char *data)
 288 {
 289         int i;
 290
 291         for(i=0; i<size; i++) {
 292                 if(data[i] < '0' || data[i] > '9')
 293                         return -1;
 294         }
 295
 296         return 0;
 297 }
 298
 299 /**
 300  * Estimates the length of the encoded bit stream of numeric data.
 301  * @param size
 302  * @return number of bits
 303  */
 304 int QRinput_estimateBitsModeNum(int size)
 305 {
 306         int w;
 307         int bits;
 308
 309         w = size / 3;
 310         bits = w * 10;
 311         switch(size - w * 3) {
 312                 case 1:
 313                         bits += 4;
 314                         break;
 315                 case 2:
 316                         bits += 7;
 317                         break;
 318                 default:
 319                         break;
 320         }
 321
 322         return bits;
 323 }
 324
 325 /**
 326  * Convert the number data to a bit stream.
 327  * @param entry
 328  * @retval 0 success
 329  * @retval -1 an error occurred and errno is set to indeicate the error.
 330  *            See Execptions for the details.
 331  * @throw ENOMEM unable to allocate memory.
 332  */
 333 static int QRinput_encodeModeNum(QRinput_List *entry, int version)
 334 {
 335         int words, i, ret;
 336         unsigned int val;
 337
 338         words = entry->size / 3;
 339         entry->bstream = BitStream_new();
 340         if(entry->bstream == NULL) return -1;
 341
 342         val = 0x1;
 343         ret = BitStream_appendNum(entry->bstream, 4, val);
 344         if(ret < 0) goto ABORT;
 345
 346         val = entry->size;
 347         ret = BitStream_appendNum(entry->bstream, QRspec_lengthIndicator(QR_MODE_NUM, version), val);
 348         if(ret < 0) goto ABORT;
 349
 350         for(i=0; i<words; i++) {
 351                 val  = (entry->data[i*3  ] - '0') * 100;
 352                 val += (entry->data[i*3+1] - '0') * 10;
 353                 val += (entry->data[i*3+2] - '0');
 354
 355                 ret = BitStream_appendNum(entry->bstream, 10, val);
 356                 if(ret < 0) goto ABORT;
 357         }
 358
 359         if(entry->size - words * 3 == 1) {
 360                 val = entry->data[words*3] - '0';
 361                 ret = BitStream_appendNum(entry->bstream, 4, val);
 362                 if(ret < 0) goto ABORT;
 363         } else if(entry->size - words * 3 == 2) {
 364                 val  = (entry->data[words*3  ] - '0') * 10;
 365                 val += (entry->data[words*3+1] - '0');
 366                 BitStream_appendNum(entry->bstream, 7, val);
 367                 if(ret < 0) goto ABORT;
 368         }
 369
 370         return 0;
 371 ABORT:
 372         BitStream_free(entry->bstream);
 373         entry->bstream = NULL;
 374         return -1;
 375 }
 376
 377 /******************************************************************************
 378  * Alphabet-numeric data
 379  *****************************************************************************/
 380
 381 const signed char QRinput_anTable[128] = {
 382         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 383         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 384         36, -1, -1, -1, 37, 38, -1, -1, -1, -1, 39, 40, -1, 41, 42, 43,
 385          0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 44, -1, -1, -1, -1, -1,
 386         -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
 387         25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1,
 388         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 389         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
 390 };
 391
 392 /**
 393  * Check the input data.
 394  * @param size
 395  * @param data
 396  * @return result
 397  */
 398 static int QRinput_checkModeAn(int size, const char *data)
 399 {
 400         int i;
 401
 402         for(i=0; i<size; i++) {
 403                 if(QRinput_lookAnTable(data[i]) < 0)
 404                         return -1;
 405         }
 406
 407         return 0;
 408 }
 409
 410 /**
 411  * Estimates the length of the encoded bit stream of alphabet-numeric data.
 412  * @param size
 413  * @return number of bits
 414  */
 415 int QRinput_estimateBitsModeAn(int size)
 416 {
 417         int w;
 418         int bits;
 419
 420         w = size / 2;
 421         bits = w * 11;
 422         if(size & 1) {
 423                 bits += 6;
 424         }
 425
 426         return bits;
 427 }
 428
 429 /**
 430  * Convert the alphabet-numeric data to a bit stream.
 431  * @param entry
 432  * @retval 0 success
 433  * @retval -1 an error occurred and errno is set to indeicate the error.
 434  *            See Execptions for the details.
 435  * @throw ENOMEM unable to allocate memory.
 436  */
 437 static int QRinput_encodeModeAn(QRinput_List *entry, int version)
 438 {
 439         int words, i, ret;
 440         unsigned int val;
 441
 442         words = entry->size / 2;
 443         entry->bstream = BitStream_new();
 444         if(entry->bstream == NULL) return -1;
 445
 446         val = 0x2;
 447         ret = BitStream_appendNum(entry->bstream, 4, val);
 448         if(ret < 0) goto ABORT;
 449
 450         val = entry->size;
 451         ret = BitStream_appendNum(entry->bstream, QRspec_lengthIndicator(QR_MODE_AN, version), val);
 452         if(ret < 0) goto ABORT;
 453
 454         for(i=0; i<words; i++) {
 455                 val  = (unsigned int)QRinput_lookAnTable(entry->data[i*2  ]) * 45;
 456                 val += (unsigned int)QRinput_lookAnTable(entry->data[i*2+1]);
 457
 458                 ret = BitStream_appendNum(entry->bstream, 11, val);
 459                 if(ret < 0) goto ABORT;
 460         }
 461
 462         if(entry->size & 1) {
 463                 val = (unsigned int)QRinput_lookAnTable(entry->data[words * 2]);
 464
 465                 ret = BitStream_appendNum(entry->bstream, 6, val);
 466                 if(ret < 0) goto ABORT;
 467         }
 468
 469         return 0;
 470 ABORT:
 471         BitStream_free(entry->bstream);
 472         entry->bstream = NULL;
 473         return -1;
 474 }
 475
 476 /******************************************************************************
 477  * 8 bit data
 478  *****************************************************************************/
 479
 480 /**
 481  * Estimates the length of the encoded bit stream of 8 bit data.
 482  * @param size
 483  * @return number of bits
 484  */
 485 int QRinput_estimateBitsMode8(int size)
 486 {
 487         return size * 8;
 488 }
 489
 490 /**
 491  * Convert the 8bits data to a bit stream.
 492  * @param entry
 493  * @retval 0 success
 494  * @retval -1 an error occurred and errno is set to indeicate the error.
 495  *            See Execptions for the details.
 496  * @throw ENOMEM unable to allocate memory.
 497  */
 498 static int QRinput_encodeMode8(QRinput_List *entry, int version)
 499 {
 500         int ret, i;
 501         unsigned int val;
 502
 503         entry->bstream = BitStream_new();
 504         if(entry->bstream == NULL) return -1;
 505
 506         val = 0x4;
 507         ret = BitStream_appendNum(entry->bstream, 4, val);
 508         if(ret < 0) goto ABORT;
 509
 510         val = entry->size;
 511         ret = BitStream_appendNum(entry->bstream, QRspec_lengthIndicator(QR_MODE_8, version), val);
 512         if(ret < 0) goto ABORT;
 513
 514         for(i=0; i<entry->size; i++) {
 515                 ret = BitStream_appendNum(entry->bstream, 8, entry->data[i]);
 516                 if(ret < 0) goto ABORT;
 517         }
 518
 519         return 0;
 520 ABORT:
 521         BitStream_free(entry->bstream);
 522         entry->bstream = NULL;
 523         return -1;
 524 }
 525
 526
 527 /******************************************************************************
 528  * Kanji data
 529  *****************************************************************************/
 530
 531 /**
 532  * Estimates the length of the encoded bit stream of kanji data.
 533  * @param size
 534  * @return number of bits
 535  */
 536 int QRinput_estimateBitsModeKanji(int size)
 537 {
 538         return (size / 2) * 13;
 539 }
 540
 541 /**
 542  * Check the input data.
 543  * @param size
 544  * @param data
 545  * @return result
 546  */
 547 static int QRinput_checkModeKanji(int size, const unsigned char *data)
 548 {
 549         int i;
 550         unsigned int val;
 551
 552         if(size & 1)
 553                 return -1;
 554
 555         for(i=0; i<size; i+=2) {
 556                 val = ((unsigned int)data[i] << 8) | data[i+1];
 557                 if(val < 0x8140 || (val > 0x9ffc && val < 0xe040) || val > 0xebbf) {
 558                         return -1;
 559                 }
 560         }
 561
 562         return 0;
 563 }
 564
 565 /**
 566  * Convert the kanji data to a bit stream.
 567  * @param entry
 568  * @retval 0 success
 569  * @retval -1 an error occurred and errno is set to indeicate the error.
 570  *            See Execptions for the details.
 571  * @throw ENOMEM unable to allocate memory.
 572  */
 573 static int QRinput_encodeModeKanji(QRinput_List *entry, int version)
 574 {
 575         int ret, i;
 576         unsigned int val, h;
 577
 578         entry->bstream = BitStream_new();
 579         if(entry->bstream == NULL) return -1;
 580
 581         val = 0x8;
 582         ret = BitStream_appendNum(entry->bstream, 4, val);
 583         if(ret < 0) goto ABORT;
 584
 585         val = entry->size / 2;
 586         ret = BitStream_appendNum(entry->bstream, QRspec_lengthIndicator(QR_MODE_KANJI, version), val);
 587         if(ret < 0) goto ABORT;
 588
 589         for(i=0; i<entry->size; i+=2) {
 590                 val = ((unsigned int)entry->data[i] << 8) | entry->data[i+1];
 591                 if(val <= 0x9ffc) {
 592                         val -= 0x8140;
 593                 } else {
 594                         val -= 0xc140;
 595                 }
 596                 h = (val >> 8) * 0xc0;
 597                 val = (val & 0xff) + h;
 598
 599                 ret = BitStream_appendNum(entry->bstream, 13, val);
 600                 if(ret < 0) goto ABORT;
 601         }
 602
 603         return 0;
 604 ABORT:
 605         BitStream_free(entry->bstream);
 606         entry->bstream = NULL;
 607         return -1;
 608 }
 609
 610 /******************************************************************************
 611  * Structured Symbol
 612  *****************************************************************************/
 613
 614 /**
 615  * Convert a structure symbol code to a bit stream.
 616  * @param entry
 617  * @retval 0 success
 618  * @retval -1 an error occurred and errno is set to indeicate the error.
 619  *            See Execptions for the details.
 620  * @throw ENOMEM unable to allocate memory.
 621  */
 622 static int QRinput_encodeModeStructure(QRinput_List *entry)
 623 {
 624         int ret;
 625
 626         entry->bstream = BitStream_new();
 627         if(entry->bstream == NULL) return -1;
 628
 629         ret = BitStream_appendNum(entry->bstream, 4, 0x03);
 630         if(ret < 0) goto ABORT;
 631         ret = BitStream_appendNum(entry->bstream, 4, entry->data[1] - 1);
 632         if(ret < 0) goto ABORT;
 633         ret = BitStream_appendNum(entry->bstream, 4, entry->data[0] - 1);
 634         if(ret < 0) goto ABORT;
 635         ret = BitStream_appendNum(entry->bstream, 8, entry->data[2]);
 636         if(ret < 0) goto ABORT;
 637
 638         return 0;
 639 ABORT:
 640         BitStream_free(entry->bstream);
 641         entry->bstream = NULL;
 642         return -1;
 643 }
 644
 645 /******************************************************************************
 646  * Validation
 647  *****************************************************************************/
 648
 649 int QRinput_check(QRencodeMode mode, int size, const unsigned char *data)
 650 {
 651         if(size <= 0) return -1;
 652
 653         switch(mode) {
 654                 case QR_MODE_NUM:
 655                         return QRinput_checkModeNum(size, (const char *)data);
 656                         break;
 657                 case QR_MODE_AN:
 658                         return QRinput_checkModeAn(size, (const char *)data);
 659                         break;
 660                 case QR_MODE_KANJI:
 661                         return QRinput_checkModeKanji(size, data);
 662                         break;
 663                 case QR_MODE_8:
 664                         return 0;
 665                         break;
 666                 case QR_MODE_STRUCTURE:
 667                         return 0;
 668                         break;
 669                 default:
 670                         break;
 671         }
 672
 673         return -1;
 674 }
 675
 676 /******************************************************************************
 677  * Estimation of the bit length
 678  *****************************************************************************/
 679
 680 /**
 681  * Estimates the length of the encoded bit stream on the current version.
 682  * @param entry
 683  * @param version version of the symbol
 684  * @return number of bits
 685  */
 686 static int QRinput_estimateBitStreamSizeOfEntry(QRinput_List *entry, int version)
 687 {
 688         int bits = 0;
 689         int l, m;
 690         int num;
 691
 692         if(version == 0) version = 1;
 693
 694         switch(entry->mode) {
 695                 case QR_MODE_NUM:
 696                         bits = QRinput_estimateBitsModeNum(entry->size);
 697                         break;
 698                 case QR_MODE_AN:
 699                         bits = QRinput_estimateBitsModeAn(entry->size);
 700                         break;
 701                 case QR_MODE_8:
 702                         bits = QRinput_estimateBitsMode8(entry->size);
 703                         break;
 704                 case QR_MODE_KANJI:
 705                         bits = QRinput_estimateBitsModeKanji(entry->size);
 706                         break;
 707                 case QR_MODE_STRUCTURE:
 708                         return STRUCTURE_HEADER_BITS;
 709                 default:
 710                         return 0;
 711         }
 712
 713         l = QRspec_lengthIndicator(entry->mode, version);
 714         m = 1 << l;
 715         num = (entry->size + m - 1) / m;
 716
 717         bits += num * (4 + l); // mode indicator (4bits) + length indicator
 718
 719         return bits;
 720 }
 721
 722 /**
 723  * Estimates the length of the encoded bit stream of the data.
 724  * @param input input data
 725  * @param version version of the symbol
 726  * @return number of bits
 727  */
 728 __STATIC int QRinput_estimateBitStreamSize(QRinput *input, int version)
 729 {
 730         QRinput_List *list;
 731         int bits = 0;
 732
 733         list = input->head;
 734         while(list != NULL) {
 735                 bits += QRinput_estimateBitStreamSizeOfEntry(list, version);
 736                 list = list->next;
 737         }
 738
 739         return bits;
 740 }
 741
 742 /**
 743  * Estimates the required version number of the symbol.
 744  * @param input input data
 745  * @return required version number
 746  */
 747 static int QRinput_estimateVersion(QRinput *input)
 748 {
 749         int bits;
 750         int version, prev;
 751
 752         version = 0;
 753         do {
 754                 prev = version;
 755                 bits = QRinput_estimateBitStreamSize(input, prev);
 756                 version = QRspec_getMinimumVersion((bits + 7) / 8, input->level);
 757                 if (version < 0) {
 758                         return -1;
 759                 }
 760         } while (version > prev);
 761
 762         return version;
 763 }
 764
 765 /**
 766  * Returns required length in bytes for specified mode, version and bits.
 767  * @param mode
 768  * @param version
 769  * @param bits
 770  * @return required length of code words in bytes.
 771  */
 772 __STATIC int QRinput_lengthOfCode(QRencodeMode mode, int version, int bits)
 773 {
 774         int payload, size, chunks, remain, maxsize;
 775
 776         payload = bits - 4 - QRspec_lengthIndicator(mode, version);
 777         switch(mode) {
 778                 case QR_MODE_NUM:
 779                         chunks = payload / 10;
 780                         remain = payload - chunks * 10;
 781                         size = chunks * 3;
 782                         if(remain >= 7) {
 783                                 size += 2;
 784                         } else if(remain >= 4) {
 785                                 size += 1;
 786                         }
 787                         break;
 788                 case QR_MODE_AN:
 789                         chunks = payload / 11;
 790                         remain = payload - chunks * 11;
 791                         size = chunks * 2;
 792                         if(remain >= 6) size++;
 793                         break;
 794                 case QR_MODE_8:
 795                         size = payload / 8;
 796                         break;
 797                 case QR_MODE_KANJI:
 798                         size = (payload / 13) * 2;
 799                         break;
 800                 case QR_MODE_STRUCTURE:
 801                         size = payload / 8;
 802                         break;
 803                 default:
 804                         size = 0;
 805                         break;
 806         }
 807         maxsize = QRspec_maximumWords(mode, version);
 808         if(size < 0) size = 0;
 809         if(size > maxsize) size = maxsize;
 810
 811         return size;
 812 }
 813
 814 /******************************************************************************
 815  * Data conversion
 816  *****************************************************************************/
 817
 818 /**
 819  * Convert the input data in the data chunk to a bit stream.
 820  * @param entry
 821  * @return number of bits (>0) or -1 for failure.
 822  */
 823 static int QRinput_encodeBitStream(QRinput_List *entry, int version)
 824 {
 825         int words, ret;
 826         QRinput_List *st1 = NULL, *st2 = NULL;
 827
 828         if(entry->bstream != NULL) {
 829                 BitStream_free(entry->bstream);
 830                 entry->bstream = NULL;
 831         }
 832
 833         words = QRspec_maximumWords(entry->mode, version);
 834         if(entry->size > words) {
 835                 st1 = QRinput_List_newEntry(entry->mode, words, entry->data);
 836                 if(st1 == NULL) goto ABORT;
 837                 st2 = QRinput_List_newEntry(entry->mode, entry->size - words, &entry->data[words]);
 838                 if(st2 == NULL) goto ABORT;
 839
 840                 ret = QRinput_encodeBitStream(st1, version);
 841                 if(ret < 0) goto ABORT;
 842                 ret = QRinput_encodeBitStream(st2, version);
 843                 if(ret < 0) goto ABORT;
 844                 entry->bstream = BitStream_new();
 845                 if(entry->bstream == NULL) goto ABORT;
 846                 ret = BitStream_append(entry->bstream, st1->bstream);
 847                 if(ret < 0) goto ABORT;
 848                 ret = BitStream_append(entry->bstream, st2->bstream);
 849                 if(ret < 0) goto ABORT;
 850                 QRinput_List_freeEntry(st1);
 851                 QRinput_List_freeEntry(st2);
 852         } else {
 853                 ret = 0;
 854                 switch(entry->mode) {
 855                         case QR_MODE_NUM:
 856                                 ret = QRinput_encodeModeNum(entry, version);
 857                                 break;
 858                         case QR_MODE_AN:
 859                                 ret = QRinput_encodeModeAn(entry, version);
 860                                 break;
 861                         case QR_MODE_8:
 862                                 ret = QRinput_encodeMode8(entry, version);
 863                                 break;
 864                         case QR_MODE_KANJI:
 865                                 ret = QRinput_encodeModeKanji(entry, version);
 866                                 break;
 867                         case QR_MODE_STRUCTURE:
 868                                 ret = QRinput_encodeModeStructure(entry);
 869                                 break;
 870                         default:
 871                                 break;
 872                 }
 873                 if(ret < 0) return -1;
 874         }
 875
 876         return BitStream_size(entry->bstream);
 877 ABORT:
 878         QRinput_List_freeEntry(st1);
 879         QRinput_List_freeEntry(st2);
 880         return -1;
 881 }
 882
 883 /**
 884  * Convert the input data to a bit stream.
 885  * @param input input data.
 886  * @retval 0 success
 887  * @retval -1 an error occurred and errno is set to indeicate the error.
 888  *            See Execptions for the details.
 889  * @throw ENOMEM unable to allocate memory.
 890  */
 891 static int QRinput_createBitStream(QRinput *input)
 892 {
 893         QRinput_List *list;
 894         int bits, total = 0;
 895
 896         list = input->head;
 897         while(list != NULL) {
 898                 bits = QRinput_encodeBitStream(list, input->version);
 899                 if(bits < 0) return -1;
 900                 total += bits;
 901                 list = list->next;
 902         }
 903
 904         return total;
 905 }
 906
 907 /**
 908  * Convert the input data to a bit stream.
 909  * When the version number is given and that is not sufficient, it is increased
 910  * automatically.
 911  * @param input input data.
 912  * @retval 0 success
 913  * @retval -1 an error occurred and errno is set to indeicate the error.
 914  *            See Execptions for the details.
 915  * @throw ENOMEM unable to allocate memory.
 916  * @throw EINVAL input is too large.
 917  */
 918 static int QRinput_convertData(QRinput *input)
 919 {
 920         int bits;
 921         int ver;
 922
 923         ver = QRinput_estimateVersion(input);
 924         if(ver > QRinput_getVersion(input)) {
 925                 QRinput_setVersion(input, ver);
 926         }
 927
 928         for(;;) {
 929                 bits = QRinput_createBitStream(input);
 930                 if(bits < 0) return -1;
 931                 ver = QRspec_getMinimumVersion((bits + 7) / 8, input->level);
 932                 if(ver < 0) {
 933                         errno = EINVAL;
 934                         return -1;
 935                 } else if(ver > QRinput_getVersion(input)) {
 936                         QRinput_setVersion(input, ver);
 937                 } else {
 938                         break;
 939                 }
 940         }
 941
 942         return 0;
 943 }
 944
 945 /**
 946  * Append padding bits for the input data.
 947  * @param bstream Bitstream to be appended.
 948  * @param input input data.
 949  * @retval 0 success
 950  * @retval -1 an error occurred and errno is set to indeicate the error.
 951  *            See Execptions for the details.
 952  * @throw ENOMEM unable to allocate memory.
 953  */
 954 static int QRinput_appendPaddingBit(BitStream *bstream, QRinput *input)
 955 {
 956         int bits, maxbits, words, maxwords, i, ret;
 957         BitStream *padding = NULL;
 958         unsigned char *padbuf;
 959         int padlen;
 960
 961         bits = BitStream_size(bstream);
 962         maxwords = QRspec_getDataLength(input->version, input->level);
 963         maxbits = maxwords * 8;
 964
 965         if(maxbits == bits) {
 966                 return 0;
 967         }
 968
 969         if(maxbits - bits < 5) {
 970                 ret = BitStream_appendNum(bstream, maxbits - bits, 0);
 971                 goto DONE;
 972         }
 973
 974         bits += 4;
 975         words = (bits + 7) / 8;
 976
 977         padding = BitStream_new();
 978         if(padding == NULL) return -1;
 979         ret = BitStream_appendNum(padding, words * 8 - bits + 4, 0);
 980         if(ret < 0) goto DONE;
 981
 982         padlen = maxwords - words;
 983         if(padlen > 0) {
 984                 padbuf = (unsigned char *)malloc(padlen);
 985                 if(padbuf == NULL) {
 986                         ret = -1;
 987                         goto DONE;
 988                 }
 989                 for(i=0; i<padlen; i++) {
 990                         padbuf[i] = (i&1)?0x11:0xec;
 991                 }
 992                 ret = BitStream_appendBytes(padding, padlen, padbuf);
 993                 free(padbuf);
 994                 if(ret < 0) {
 995                         goto DONE;
 996                 }
 997         }
 998
 999         ret = BitStream_append(bstream, padding);
1000
1001 DONE:
1002         BitStream_free(padding);
1003         return ret;
1004 }
1005
1006 /**
1007  * Merge all bit streams in the input data.
1008  * @param input input data.
1009  * @return merged bit stream
1010  */
1011
1012 __STATIC BitStream *QRinput_mergeBitStream(QRinput *input)
1013 {
1014         BitStream *bstream;
1015         QRinput_List *list;
1016         int ret;
1017
1018         if(QRinput_convertData(input) < 0) {
1019                 return NULL;
1020         }
1021
1022         bstream = BitStream_new();
1023         if(bstream == NULL) return NULL;
1024
1025         list = input->head;
1026         while(list != NULL) {
1027                 ret = BitStream_append(bstream, list->bstream);
1028                 if(ret < 0) {
1029                         BitStream_free(bstream);
1030                         return NULL;
1031                 }
1032                 list = list->next;
1033         }
1034
1035         return bstream;
1036 }
1037
1038 /**
1039  * Merge all bit streams in the input data and append padding bits
1040  * @param input input data.
1041  * @return padded merged bit stream
1042  */
1043
1044 __STATIC BitStream *QRinput_getBitStream(QRinput *input)
1045 {
1046         BitStream *bstream;
1047         int ret;
1048
1049         bstream = QRinput_mergeBitStream(input);
1050         if(bstream == NULL) {
1051                 return NULL;
1052         }
1053         ret = QRinput_appendPaddingBit(bstream, input);
1054         if(ret < 0) {
1055                 BitStream_free(bstream);
1056                 return NULL;
1057         }
1058
1059         return bstream;
1060 }
1061
1062 /**
1063  * Pack all bit streams padding bits into a byte array.
1064  * @param input input data.
1065  * @return padded merged byte stream
1066  */
1067
1068 unsigned char *QRinput_getByteStream(QRinput *input)
1069 {
1070         BitStream *bstream;
1071         unsigned char *array;
1072
1073         bstream = QRinput_getBitStream(input);
1074         if(bstream == NULL) {
1075                 return NULL;
1076         }
1077         array = BitStream_toByte(bstream);
1078         BitStream_free(bstream);
1079
1080         return array;
1081 }
1082
1083 /******************************************************************************
1084  * Structured input data
1085  *****************************************************************************/
1086
1087 static QRinput_InputList *QRinput_InputList_newEntry(QRinput *input)
1088 {
1089         QRinput_InputList *entry;
1090
1091         entry = (QRinput_InputList *)malloc(sizeof(QRinput_InputList));
1092         if(entry == NULL) return NULL;
1093
1094         entry->input = input;
1095         entry->next = NULL;
1096
1097         return entry;
1098 }
1099
1100 static void QRinput_InputList_freeEntry(QRinput_InputList *entry)
1101 {
1102         if(entry != NULL) {
1103                 QRinput_free(entry->input);
1104                 free(entry);
1105         }
1106 }
1107
1108 QRinput_Struct *QRinput_Struct_new(void)
1109 {
1110         QRinput_Struct *s;
1111
1112         s = (QRinput_Struct *)malloc(sizeof(QRinput_Struct));
1113         if(s == NULL) return NULL;
1114
1115         s->size = 0;
1116         s->parity = -1;
1117         s->head = NULL;
1118         s->tail = NULL;
1119
1120         return s;
1121 }
1122
1123 void QRinput_Struct_setParity(QRinput_Struct *s, unsigned char parity)
1124 {
1125         s->parity = (int)parity;
1126 }
1127
1128 int QRinput_Struct_appendInput(QRinput_Struct *s, QRinput *input)
1129 {
1130         QRinput_InputList *e;
1131
1132         e = QRinput_InputList_newEntry(input);
1133         if(e == NULL) return -1;
1134
1135         s->size++;
1136         if(s->tail == NULL) {
1137                 s->head = e;
1138                 s->tail = e;
1139         } else {
1140                 s->tail->next = e;
1141                 s->tail = e;
1142         }
1143
1144         return s->size;
1145 }
1146
1147 void QRinput_Struct_free(QRinput_Struct *s)
1148 {
1149         QRinput_InputList *list, *next;
1150
1151         if(s != NULL) {
1152                 list = s->head;
1153                 while(list != NULL) {
1154                         next = list->next;
1155                         QRinput_InputList_freeEntry(list);
1156                         list = next;
1157                 }
1158                 free(s);
1159         }
1160 }
1161
1162 static unsigned char QRinput_Struct_calcParity(QRinput_Struct *s)
1163 {
1164         QRinput_InputList *list;
1165         unsigned char parity = 0;
1166
1167         list = s->head;
1168         while(list != NULL) {
1169                 parity ^= QRinput_calcParity(list->input);
1170                 list = list->next;
1171         }
1172
1173         QRinput_Struct_setParity(s, parity);
1174
1175         return parity;
1176 }
1177
1178 static int QRinput_List_shrinkEntry(QRinput_List *entry, int bytes)
1179 {
1180         unsigned char *data;
1181
1182         data = (unsigned char *)malloc(bytes);
1183         if(data == NULL) return -1;
1184
1185         memcpy(data, entry->data, bytes);
1186         free(entry->data);
1187         entry->data = data;
1188         entry->size = bytes;
1189
1190         return 0;
1191 }
1192
1193 __STATIC int QRinput_splitEntry(QRinput_List *entry, int bytes)
1194 {
1195         QRinput_List *e;
1196         int ret;
1197
1198         e = QRinput_List_newEntry(entry->mode, entry->size - bytes, entry->data + bytes);
1199         if(e == NULL) {
1200                 return -1;
1201         }
1202
1203         ret = QRinput_List_shrinkEntry(entry, bytes);
1204         if(ret < 0) {
1205                 QRinput_List_freeEntry(e);
1206                 return -1;
1207         }
1208
1209         e->next = entry->next;
1210         entry->next = e;
1211
1212         return 0;
1213 }
1214
1215 QRinput_Struct *QRinput_splitQRinputToStruct(QRinput *input)
1216 {
1217         QRinput *p;
1218         QRinput_Struct *s;
1219         int bits, maxbits, nextbits, bytes, ret;
1220         QRinput_List *list, *next, *prev;
1221
1222         s = QRinput_Struct_new();
1223         if(s == NULL) return NULL;
1224
1225         input = QRinput_dup(input);
1226         if(input == NULL) {
1227                 QRinput_Struct_free(s);
1228                 return NULL;
1229         }
1230
1231         QRinput_Struct_setParity(s, QRinput_calcParity(input));
1232         maxbits = QRspec_getDataLength(input->version, input->level) * 8 - STRUCTURE_HEADER_BITS;
1233
1234         if(maxbits <= 0) {
1235                 QRinput_Struct_free(s);
1236                 QRinput_free(input);
1237                 return NULL;
1238         }
1239
1240         bits = 0;
1241         list = input->head;
1242         prev = NULL;
1243         while(list != NULL) {
1244                 nextbits = QRinput_estimateBitStreamSizeOfEntry(list, input->version);
1245                 if(bits + nextbits <= maxbits) {
1246                         ret = QRinput_encodeBitStream(list, input->version);
1247                         if(ret < 0) goto ABORT;
1248                         bits += ret;
1249                         prev = list;
1250                         list = list->next;
1251                 } else {
1252                         bytes = QRinput_lengthOfCode(list->mode, input->version, maxbits - bits);
1253                         if(bytes > 0) {
1254                                 /* Splits this entry into 2 entries. */
1255                                 ret = QRinput_splitEntry(list, bytes);
1256                                 if(ret < 0) goto ABORT;
1257                                 /* First half is the tail of the current input. */
1258                                 next = list->next;
1259                                 list->next = NULL;
1260                                 /* Second half is the head of the next input, p.*/
1261                                 p = QRinput_new2(input->version, input->level);
1262                                 if(p == NULL) goto ABORT;
1263                                 p->head = next;
1264                                 /* Renew QRinput.tail. */
1265                                 p->tail = input->tail;
1266                                 input->tail = list;
1267                                 /* Point to the next entry. */
1268                                 prev = list;
1269                                 list = next;
1270                         } else {
1271                                 /* Current entry will go to the next input. */
1272                                 prev->next = NULL;
1273                                 p = QRinput_new2(input->version, input->level);
1274                                 if(p == NULL) goto ABORT;
1275                                 p->head = list;
1276                                 p->tail = input->tail;
1277                                 input->tail = prev;
1278                         }
1279                         ret = QRinput_Struct_appendInput(s, input);
1280                         if(ret < 0) goto ABORT;
1281                         input = p;
1282                         bits = 0;
1283                 }
1284         }
1285         QRinput_Struct_appendInput(s, input);
1286         if(s->size > MAX_STRUCTURED_SYMBOLS) {
1287                 QRinput_Struct_free(s);
1288                 errno = ERANGE;
1289                 return NULL;
1290         }
1291         ret = QRinput_Struct_insertStructuredAppendHeaders(s);
1292         if(ret < 0) {
1293                 QRinput_Struct_free(s);
1294                 return NULL;
1295         }
1296
1297         return s;
1298
1299 ABORT:
1300         QRinput_free(input);
1301         QRinput_Struct_free(s);
1302         return NULL;
1303 }
1304
1305 int QRinput_Struct_insertStructuredAppendHeaders(QRinput_Struct *s)
1306 {
1307         int num, i;
1308         QRinput_InputList *list;
1309
1310         if(s->parity < 0) {
1311                 QRinput_Struct_calcParity(s);
1312         }
1313         num = 0;
1314         list = s->head;
1315         while(list != NULL) {
1316                 num++;
1317                 list = list->next;
1318         }
1319         i = 1;
1320         list = s->head;
1321         while(list != NULL) {
1322                 if(QRinput_insertStructuredAppendHeader(list->input, num, i, s->parity))
1323                         return -1;
1324                 i++;
1325                 list = list->next;
1326         }
1327
1328         return 0;
1329 }