examples/common/QRCode/repo/cpp/QrCode.cpp

   1 /*
   2  * QR Code generator library (C++)
   3  *
   4  * Copyright (c) Project Nayuki. (MIT License)
   5  * https://www.nayuki.io/page/qr-code-generator-library
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy of
   8  * this software and associated documentation files (the "Software"), to deal in
   9  * the Software without restriction, including without limitation the rights to
  10  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
  11  * the Software, and to permit persons to whom the Software is furnished to do so,
  12  * subject to the following conditions:
  13  * - The above copyright notice and this permission notice shall be included in
  14  *   all copies or substantial portions of the Software.
  15  * - The Software is provided "as is", without warranty of any kind, express or
  16  *   implied, including but not limited to the warranties of merchantability,
  17  *   fitness for a particular purpose and noninfringement. In no event shall the
  18  *   authors or copyright holders be liable for any claim, damages or other
  19  *   liability, whether in an action of contract, tort or otherwise, arising from,
  20  *   out of or in connection with the Software or the use or other dealings in the
  21  *   Software.
  22  */
  23
  24 #include <algorithm>
  25 #include <climits>
  26 #include <cstddef>
  27 #include <cstdlib>
  28 #include <cstring>
  29 #include <sstream>
  30 #include <stdexcept>
  31 #include <utility>
  32 #include "QrCode.hpp"
  33
  34 using std::int8_t;
  35 using std::uint8_t;
  36 using std::size_t;
  37 using std::vector;
  38
  39
  40 namespace qrcodegen {
  41
  42 QrSegment::Mode::Mode(int mode, int cc0, int cc1, int cc2) :
  43                 modeBits(mode) {
  44         numBitsCharCount[0] = cc0;
  45         numBitsCharCount[1] = cc1;
  46         numBitsCharCount[2] = cc2;
  47 }
  48
  49
  50 int QrSegment::Mode::getModeBits() const {
  51         return modeBits;
  52 }
  53
  54
  55 int QrSegment::Mode::numCharCountBits(int ver) const {
  56         return numBitsCharCount[(ver + 7) / 17];
  57 }
  58
  59
  60 const QrSegment::Mode QrSegment::Mode::NUMERIC     (0x1, 10, 12, 14);
  61 const QrSegment::Mode QrSegment::Mode::ALPHANUMERIC(0x2,  9, 11, 13);
  62 const QrSegment::Mode QrSegment::Mode::BYTE        (0x4,  8, 16, 16);
  63 const QrSegment::Mode QrSegment::Mode::KANJI       (0x8,  8, 10, 12);
  64 const QrSegment::Mode QrSegment::Mode::ECI         (0x7,  0,  0,  0);
  65
  66
  67 QrSegment QrSegment::makeBytes(const vector<uint8_t> &data) {
  68         if (data.size() > static_cast<unsigned int>(INT_MAX))
  69                 throw std::length_error("Data too long");
  70         BitBuffer bb;
  71         for (uint8_t b : data)
  72                 bb.appendBits(b, 8);
  73         return QrSegment(Mode::BYTE, static_cast<int>(data.size()), std::move(bb));
  74 }
  75
  76
  77 QrSegment QrSegment::makeNumeric(const char *digits) {
  78         BitBuffer bb;
  79         int accumData = 0;
  80         int accumCount = 0;
  81         int charCount = 0;
  82         for (; *digits != '\0'; digits++, charCount++) {
  83                 char c = *digits;
  84                 if (c < '0' || c > '9')
  85                         throw std::domain_error("String contains non-numeric characters");
  86                 accumData = accumData * 10 + (c - '0');
  87                 accumCount++;
  88                 if (accumCount == 3) {
  89                         bb.appendBits(static_cast<uint32_t>(accumData), 10);
  90                         accumData = 0;
  91                         accumCount = 0;
  92                 }
  93         }
  94         if (accumCount > 0)  // 1 or 2 digits remaining
  95                 bb.appendBits(static_cast<uint32_t>(accumData), accumCount * 3 + 1);
  96         return QrSegment(Mode::NUMERIC, charCount, std::move(bb));
  97 }
  98
  99
 100 QrSegment QrSegment::makeAlphanumeric(const char *text) {
 101         BitBuffer bb;
 102         int accumData = 0;
 103         int accumCount = 0;
 104         int charCount = 0;
 105         for (; *text != '\0'; text++, charCount++) {
 106                 const char *temp = std::strchr(ALPHANUMERIC_CHARSET, *text);
 107                 if (temp == nullptr)
 108                         throw std::domain_error("String contains unencodable characters in alphanumeric mode");
 109                 accumData = accumData * 45 + static_cast<int>(temp - ALPHANUMERIC_CHARSET);
 110                 accumCount++;
 111                 if (accumCount == 2) {
 112                         bb.appendBits(static_cast<uint32_t>(accumData), 11);
 113                         accumData = 0;
 114                         accumCount = 0;
 115                 }
 116         }
 117         if (accumCount > 0)  // 1 character remaining
 118                 bb.appendBits(static_cast<uint32_t>(accumData), 6);
 119         return QrSegment(Mode::ALPHANUMERIC, charCount, std::move(bb));
 120 }
 121
 122
 123 vector<QrSegment> QrSegment::makeSegments(const char *text) {
 124         // Select the most efficient segment encoding automatically
 125         vector<QrSegment> result;
 126         if (*text == '\0');  // Leave result empty
 127         else if (isNumeric(text))
 128                 result.push_back(makeNumeric(text));
 129         else if (isAlphanumeric(text))
 130                 result.push_back(makeAlphanumeric(text));
 131         else {
 132                 vector<uint8_t> bytes;
 133                 for (; *text != '\0'; text++)
 134                         bytes.push_back(static_cast<uint8_t>(*text));
 135                 result.push_back(makeBytes(bytes));
 136         }
 137         return result;
 138 }
 139
 140
 141 QrSegment QrSegment::makeEci(long assignVal) {
 142         BitBuffer bb;
 143         if (assignVal < 0)
 144                 throw std::domain_error("ECI assignment value out of range");
 145         else if (assignVal < (1 << 7))
 146                 bb.appendBits(static_cast<uint32_t>(assignVal), 8);
 147         else if (assignVal < (1 << 14)) {
 148                 bb.appendBits(2, 2);
 149                 bb.appendBits(static_cast<uint32_t>(assignVal), 14);
 150         } else if (assignVal < 1000000L) {
 151                 bb.appendBits(6, 3);
 152                 bb.appendBits(static_cast<uint32_t>(assignVal), 21);
 153         } else
 154                 throw std::domain_error("ECI assignment value out of range");
 155         return QrSegment(Mode::ECI, 0, std::move(bb));
 156 }
 157
 158
 159 QrSegment::QrSegment(Mode md, int numCh, const std::vector<bool> &dt) :
 160                 mode(md),
 161                 numChars(numCh),
 162                 data(dt) {
 163         if (numCh < 0)
 164                 throw std::domain_error("Invalid value");
 165 }
 166
 167
 168 QrSegment::QrSegment(Mode md, int numCh, std::vector<bool> &&dt) :
 169                 mode(md),
 170                 numChars(numCh),
 171                 data(std::move(dt)) {
 172         if (numCh < 0)
 173                 throw std::domain_error("Invalid value");
 174 }
 175
 176
 177 int QrSegment::getTotalBits(const vector<QrSegment> &segs, int version) {
 178         int result = 0;
 179         for (const QrSegment &seg : segs) {
 180                 int ccbits = seg.mode.numCharCountBits(version);
 181                 if (seg.numChars >= (1L << ccbits))
 182                         return -1;  // The segment's length doesn't fit the field's bit width
 183                 if (4 + ccbits > INT_MAX - result)
 184                         return -1;  // The sum will overflow an int type
 185                 result += 4 + ccbits;
 186                 if (seg.data.size() > static_cast<unsigned int>(INT_MAX - result))
 187                         return -1;  // The sum will overflow an int type
 188                 result += static_cast<int>(seg.data.size());
 189         }
 190         return result;
 191 }
 192
 193
 194 bool QrSegment::isAlphanumeric(const char *text) {
 195         for (; *text != '\0'; text++) {
 196                 if (std::strchr(ALPHANUMERIC_CHARSET, *text) == nullptr)
 197                         return false;
 198         }
 199         return true;
 200 }
 201
 202
 203 bool QrSegment::isNumeric(const char *text) {
 204         for (; *text != '\0'; text++) {
 205                 char c = *text;
 206                 if (c < '0' || c > '9')
 207                         return false;
 208         }
 209         return true;
 210 }
 211
 212
 213 QrSegment::Mode QrSegment::getMode() const {
 214         return mode;
 215 }
 216
 217
 218 int QrSegment::getNumChars() const {
 219         return numChars;
 220 }
 221
 222
 223 const std::vector<bool> &QrSegment::getData() const {
 224         return data;
 225 }
 226
 227
 228 const char *QrSegment::ALPHANUMERIC_CHARSET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:";
 229
 230
 231
 232 int QrCode::getFormatBits(Ecc ecl) {
 233         switch (ecl) {
 234                 case Ecc::LOW     :  return 1;
 235                 case Ecc::MEDIUM  :  return 0;
 236                 case Ecc::QUARTILE:  return 3;
 237                 case Ecc::HIGH    :  return 2;
 238                 default:  throw std::logic_error("Assertion error");
 239         }
 240 }
 241
 242
 243 QrCode QrCode::encodeText(const char *text, Ecc ecl) {
 244         vector<QrSegment> segs = QrSegment::makeSegments(text);
 245         return encodeSegments(segs, ecl);
 246 }
 247
 248
 249 QrCode QrCode::encodeBinary(const vector<uint8_t> &data, Ecc ecl) {
 250         vector<QrSegment> segs{QrSegment::makeBytes(data)};
 251         return encodeSegments(segs, ecl);
 252 }
 253
 254
 255 QrCode QrCode::encodeSegments(const vector<QrSegment> &segs, Ecc ecl,
 256                 int minVersion, int maxVersion, int mask, bool boostEcl) {
 257         if (!(MIN_VERSION <= minVersion && minVersion <= maxVersion && maxVersion <= MAX_VERSION) || mask < -1 || mask > 7)
 258                 throw std::invalid_argument("Invalid value");
 259
 260         // Find the minimal version number to use
 261         int version, dataUsedBits;
 262         for (version = minVersion; ; version++) {
 263                 int dataCapacityBits = getNumDataCodewords(version, ecl) * 8;  // Number of data bits available
 264                 dataUsedBits = QrSegment::getTotalBits(segs, version);
 265                 if (dataUsedBits != -1 && dataUsedBits <= dataCapacityBits)
 266                         break;  // This version number is found to be suitable
 267                 if (version >= maxVersion) {  // All versions in the range could not fit the given data
 268                         std::ostringstream sb;
 269                         if (dataUsedBits == -1)
 270                                 sb << "Segment too long";
 271                         else {
 272                                 sb << "Data length = " << dataUsedBits << " bits, ";
 273                                 sb << "Max capacity = " << dataCapacityBits << " bits";
 274                         }
 275                         throw data_too_long(sb.str());
 276                 }
 277         }
 278         if (dataUsedBits == -1)
 279                 throw std::logic_error("Assertion error");
 280
 281         // Increase the error correction level while the data still fits in the current version number
 282         for (Ecc newEcl : vector<Ecc>{Ecc::MEDIUM, Ecc::QUARTILE, Ecc::HIGH}) {  // From low to high
 283                 if (boostEcl && dataUsedBits <= getNumDataCodewords(version, newEcl) * 8)
 284                         ecl = newEcl;
 285         }
 286
 287         // Concatenate all segments to create the data bit string
 288         BitBuffer bb;
 289         for (const QrSegment &seg : segs) {
 290                 bb.appendBits(static_cast<uint32_t>(seg.getMode().getModeBits()), 4);
 291                 bb.appendBits(static_cast<uint32_t>(seg.getNumChars()), seg.getMode().numCharCountBits(version));
 292                 bb.insert(bb.end(), seg.getData().begin(), seg.getData().end());
 293         }
 294         if (bb.size() != static_cast<unsigned int>(dataUsedBits))
 295                 throw std::logic_error("Assertion error");
 296
 297         // Add terminator and pad up to a byte if applicable
 298         size_t dataCapacityBits = static_cast<size_t>(getNumDataCodewords(version, ecl)) * 8;
 299         if (bb.size() > dataCapacityBits)
 300                 throw std::logic_error("Assertion error");
 301         bb.appendBits(0, std::min(4, static_cast<int>(dataCapacityBits - bb.size())));
 302         bb.appendBits(0, (8 - static_cast<int>(bb.size() % 8)) % 8);
 303         if (bb.size() % 8 != 0)
 304                 throw std::logic_error("Assertion error");
 305
 306         // Pad with alternating bytes until data capacity is reached
 307         for (uint8_t padByte = 0xEC; bb.size() < dataCapacityBits; padByte ^= 0xEC ^ 0x11)
 308                 bb.appendBits(padByte, 8);
 309
 310         // Pack bits into bytes in big endian
 311         vector<uint8_t> dataCodewords(bb.size() / 8);
 312         for (size_t i = 0; i < bb.size(); i++)
 313                 dataCodewords[i >> 3] |= (bb.at(i) ? 1 : 0) << (7 - (i & 7));
 314
 315         // Create the QR Code object
 316         return QrCode(version, ecl, dataCodewords, mask);
 317 }
 318
 319
 320 QrCode::QrCode(int ver, Ecc ecl, const vector<uint8_t> &dataCodewords, int msk) :
 321                 // Initialize fields and check arguments
 322                 version(ver),
 323                 errorCorrectionLevel(ecl) {
 324         if (ver < MIN_VERSION || ver > MAX_VERSION)
 325                 throw std::domain_error("Version value out of range");
 326         if (msk < -1 || msk > 7)
 327                 throw std::domain_error("Mask value out of range");
 328         size = ver * 4 + 17;
 329         size_t sz = static_cast<size_t>(size);
 330         modules    = vector<vector<bool> >(sz, vector<bool>(sz));  // Initially all white
 331         isFunction = vector<vector<bool> >(sz, vector<bool>(sz));
 332
 333         // Compute ECC, draw modules
 334         drawFunctionPatterns();
 335         const vector<uint8_t> allCodewords = addEccAndInterleave(dataCodewords);
 336         drawCodewords(allCodewords);
 337
 338         // Do masking
 339         if (msk == -1) {  // Automatically choose best mask
 340                 long minPenalty = LONG_MAX;
 341                 for (int i = 0; i < 8; i++) {
 342                         applyMask(i);
 343                         drawFormatBits(i);
 344                         long penalty = getPenaltyScore();
 345                         if (penalty < minPenalty) {
 346                                 msk = i;
 347                                 minPenalty = penalty;
 348                         }
 349                         applyMask(i);  // Undoes the mask due to XOR
 350                 }
 351         }
 352         if (msk < 0 || msk > 7)
 353                 throw std::logic_error("Assertion error");
 354         this->mask = msk;
 355         applyMask(msk);  // Apply the final choice of mask
 356         drawFormatBits(msk);  // Overwrite old format bits
 357
 358         isFunction.clear();
 359         isFunction.shrink_to_fit();
 360 }
 361
 362
 363 int QrCode::getVersion() const {
 364         return version;
 365 }
 366
 367
 368 int QrCode::getSize() const {
 369         return size;
 370 }
 371
 372
 373 QrCode::Ecc QrCode::getErrorCorrectionLevel() const {
 374         return errorCorrectionLevel;
 375 }
 376
 377
 378 int QrCode::getMask() const {
 379         return mask;
 380 }
 381
 382
 383 bool QrCode::getModule(int x, int y) const {
 384         return 0 <= x && x < size && 0 <= y && y < size && module(x, y);
 385 }
 386
 387
 388 std::string QrCode::toSvgString(int border) const {
 389         if (border < 0)
 390                 throw std::domain_error("Border must be non-negative");
 391         if (border > INT_MAX / 2 || border * 2 > INT_MAX - size)
 392                 throw std::overflow_error("Border too large");
 393
 394         std::ostringstream sb;
 395         sb << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n";
 396         sb << "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\" \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n";
 397         sb << "<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" viewBox=\"0 0 ";
 398         sb << (size + border * 2) << " " << (size + border * 2) << "\" stroke=\"none\">\n";
 399         sb << "\t<rect width=\"100%\" height=\"100%\" fill=\"#FFFFFF\"/>\n";
 400         sb << "\t<path d=\"";
 401         for (int y = 0; y < size; y++) {
 402                 for (int x = 0; x < size; x++) {
 403                         if (getModule(x, y)) {
 404                                 if (x != 0 || y != 0)
 405                                         sb << " ";
 406                                 sb << "M" << (x + border) << "," << (y + border) << "h1v1h-1z";
 407                         }
 408                 }
 409         }
 410         sb << "\" fill=\"#000000\"/>\n";
 411         sb << "</svg>\n";
 412         return sb.str();
 413 }
 414
 415
 416 void QrCode::drawFunctionPatterns() {
 417         // Draw horizontal and vertical timing patterns
 418         for (int i = 0; i < size; i++) {
 419                 setFunctionModule(6, i, i % 2 == 0);
 420                 setFunctionModule(i, 6, i % 2 == 0);
 421         }
 422
 423         // Draw 3 finder patterns (all corners except bottom right; overwrites some timing modules)
 424         drawFinderPattern(3, 3);
 425         drawFinderPattern(size - 4, 3);
 426         drawFinderPattern(3, size - 4);
 427
 428         // Draw numerous alignment patterns
 429         const vector<int> alignPatPos = getAlignmentPatternPositions();
 430         size_t numAlign = alignPatPos.size();
 431         for (size_t i = 0; i < numAlign; i++) {
 432                 for (size_t j = 0; j < numAlign; j++) {
 433                         // Don't draw on the three finder corners
 434                         if (!((i == 0 && j == 0) || (i == 0 && j == numAlign - 1) || (i == numAlign - 1 && j == 0)))
 435                                 drawAlignmentPattern(alignPatPos.at(i), alignPatPos.at(j));
 436                 }
 437         }
 438
 439         // Draw configuration data
 440         drawFormatBits(0);  // Dummy mask value; overwritten later in the constructor
 441         drawVersion();
 442 }
 443
 444
 445 void QrCode::drawFormatBits(int msk) {
 446         // Calculate error correction code and pack bits
 447         int data = getFormatBits(errorCorrectionLevel) << 3 | msk;  // errCorrLvl is uint2, msk is uint3
 448         int rem = data;
 449         for (int i = 0; i < 10; i++)
 450                 rem = (rem << 1) ^ ((rem >> 9) * 0x537);
 451         int bits = (data << 10 | rem) ^ 0x5412;  // uint15
 452         if (bits >> 15 != 0)
 453                 throw std::logic_error("Assertion error");
 454
 455         // Draw first copy
 456         for (int i = 0; i <= 5; i++)
 457                 setFunctionModule(8, i, getBit(bits, i));
 458         setFunctionModule(8, 7, getBit(bits, 6));
 459         setFunctionModule(8, 8, getBit(bits, 7));
 460         setFunctionModule(7, 8, getBit(bits, 8));
 461         for (int i = 9; i < 15; i++)
 462                 setFunctionModule(14 - i, 8, getBit(bits, i));
 463
 464         // Draw second copy
 465         for (int i = 0; i < 8; i++)
 466                 setFunctionModule(size - 1 - i, 8, getBit(bits, i));
 467         for (int i = 8; i < 15; i++)
 468                 setFunctionModule(8, size - 15 + i, getBit(bits, i));
 469         setFunctionModule(8, size - 8, true);  // Always black
 470 }
 471
 472
 473 void QrCode::drawVersion() {
 474         if (version < 7)
 475                 return;
 476
 477         // Calculate error correction code and pack bits
 478         int rem = version;  // version is uint6, in the range [7, 40]
 479         for (int i = 0; i < 12; i++)
 480                 rem = (rem << 1) ^ ((rem >> 11) * 0x1F25);
 481         long bits = static_cast<long>(version) << 12 | rem;  // uint18
 482         if (bits >> 18 != 0)
 483                 throw std::logic_error("Assertion error");
 484
 485         // Draw two copies
 486         for (int i = 0; i < 18; i++) {
 487                 bool bit = getBit(bits, i);
 488                 int a = size - 11 + i % 3;
 489                 int b = i / 3;
 490                 setFunctionModule(a, b, bit);
 491                 setFunctionModule(b, a, bit);
 492         }
 493 }
 494
 495
 496 void QrCode::drawFinderPattern(int x, int y) {
 497         for (int dy = -4; dy <= 4; dy++) {
 498                 for (int dx = -4; dx <= 4; dx++) {
 499                         int dist = std::max(std::abs(dx), std::abs(dy));  // Chebyshev/infinity norm
 500                         int xx = x + dx, yy = y + dy;
 501                         if (0 <= xx && xx < size && 0 <= yy && yy < size)
 502                                 setFunctionModule(xx, yy, dist != 2 && dist != 4);
 503                 }
 504         }
 505 }
 506
 507
 508 void QrCode::drawAlignmentPattern(int x, int y) {
 509         for (int dy = -2; dy <= 2; dy++) {
 510                 for (int dx = -2; dx <= 2; dx++)
 511                         setFunctionModule(x + dx, y + dy, std::max(std::abs(dx), std::abs(dy)) != 1);
 512         }
 513 }
 514
 515
 516 void QrCode::setFunctionModule(int x, int y, bool isBlack) {
 517         size_t ux = static_cast<size_t>(x);
 518         size_t uy = static_cast<size_t>(y);
 519         modules   .at(uy).at(ux) = isBlack;
 520         isFunction.at(uy).at(ux) = true;
 521 }
 522
 523
 524 bool QrCode::module(int x, int y) const {
 525         return modules.at(static_cast<size_t>(y)).at(static_cast<size_t>(x));
 526 }
 527
 528
 529 vector<uint8_t> QrCode::addEccAndInterleave(const vector<uint8_t> &data) const {
 530         if (data.size() != static_cast<unsigned int>(getNumDataCodewords(version, errorCorrectionLevel)))
 531                 throw std::invalid_argument("Invalid argument");
 532
 533         // Calculate parameter numbers
 534         int numBlocks = NUM_ERROR_CORRECTION_BLOCKS[static_cast<int>(errorCorrectionLevel)][version];
 535         int blockEccLen = ECC_CODEWORDS_PER_BLOCK  [static_cast<int>(errorCorrectionLevel)][version];
 536         int rawCodewords = getNumRawDataModules(version) / 8;
 537         int numShortBlocks = numBlocks - rawCodewords % numBlocks;
 538         int shortBlockLen = rawCodewords / numBlocks;
 539
 540         // Split data into blocks and append ECC to each block
 541         vector<vector<uint8_t> > blocks;
 542         const vector<uint8_t> rsDiv = reedSolomonComputeDivisor(blockEccLen);
 543         for (int i = 0, k = 0; i < numBlocks; i++) {
 544                 vector<uint8_t> dat(data.cbegin() + k, data.cbegin() + (k + shortBlockLen - blockEccLen + (i < numShortBlocks ? 0 : 1)));
 545                 k += static_cast<int>(dat.size());
 546                 const vector<uint8_t> ecc = reedSolomonComputeRemainder(dat, rsDiv);
 547                 if (i < numShortBlocks)
 548                         dat.push_back(0);
 549                 dat.insert(dat.end(), ecc.cbegin(), ecc.cend());
 550                 blocks.push_back(std::move(dat));
 551         }
 552
 553         // Interleave (not concatenate) the bytes from every block into a single sequence
 554         vector<uint8_t> result;
 555         for (size_t i = 0; i < blocks.at(0).size(); i++) {
 556                 for (size_t j = 0; j < blocks.size(); j++) {
 557                         // Skip the padding byte in short blocks
 558                         if (i != static_cast<unsigned int>(shortBlockLen - blockEccLen) || j >= static_cast<unsigned int>(numShortBlocks))
 559                                 result.push_back(blocks.at(j).at(i));
 560                 }
 561         }
 562         if (result.size() != static_cast<unsigned int>(rawCodewords))
 563                 throw std::logic_error("Assertion error");
 564         return result;
 565 }
 566
 567
 568 void QrCode::drawCodewords(const vector<uint8_t> &data) {
 569         if (data.size() != static_cast<unsigned int>(getNumRawDataModules(version) / 8))
 570                 throw std::invalid_argument("Invalid argument");
 571
 572         size_t i = 0;  // Bit index into the data
 573         // Do the funny zigzag scan
 574         for (int right = size - 1; right >= 1; right -= 2) {  // Index of right column in each column pair
 575                 if (right == 6)
 576                         right = 5;
 577                 for (int vert = 0; vert < size; vert++) {  // Vertical counter
 578                         for (int j = 0; j < 2; j++) {
 579                                 size_t x = static_cast<size_t>(right - j);  // Actual x coordinate
 580                                 bool upward = ((right + 1) & 2) == 0;
 581                                 size_t y = static_cast<size_t>(upward ? size - 1 - vert : vert);  // Actual y coordinate
 582                                 if (!isFunction.at(y).at(x) && i < data.size() * 8) {
 583                                         modules.at(y).at(x) = getBit(data.at(i >> 3), 7 - static_cast<int>(i & 7));
 584                                         i++;
 585                                 }
 586                                 // If this QR Code has any remainder bits (0 to 7), they were assigned as
 587                                 // 0/false/white by the constructor and are left unchanged by this method
 588                         }
 589                 }
 590         }
 591         if (i != data.size() * 8)
 592                 throw std::logic_error("Assertion error");
 593 }
 594
 595
 596 void QrCode::applyMask(int msk) {
 597         if (msk < 0 || msk > 7)
 598                 throw std::domain_error("Mask value out of range");
 599         size_t sz = static_cast<size_t>(size);
 600         for (size_t y = 0; y < sz; y++) {
 601                 for (size_t x = 0; x < sz; x++) {
 602                         bool invert;
 603                         switch (msk) {
 604                                 case 0:  invert = (x + y) % 2 == 0;                    break;
 605                                 case 1:  invert = y % 2 == 0;                          break;
 606                                 case 2:  invert = x % 3 == 0;                          break;
 607                                 case 3:  invert = (x + y) % 3 == 0;                    break;
 608                                 case 4:  invert = (x / 3 + y / 2) % 2 == 0;            break;
 609                                 case 5:  invert = x * y % 2 + x * y % 3 == 0;          break;
 610                                 case 6:  invert = (x * y % 2 + x * y % 3) % 2 == 0;    break;
 611                                 case 7:  invert = ((x + y) % 2 + x * y % 3) % 2 == 0;  break;
 612                                 default:  throw std::logic_error("Assertion error");
 613                         }
 614                         modules.at(y).at(x) = modules.at(y).at(x) ^ (invert & !isFunction.at(y).at(x));
 615                 }
 616         }
 617 }
 618
 619
 620 long QrCode::getPenaltyScore() const {
 621         long result = 0;
 622
 623         // Adjacent modules in row having same color, and finder-like patterns
 624         for (int y = 0; y < size; y++) {
 625                 bool runColor = false;
 626                 int runX = 0;
 627                 std::array<int,7> runHistory = {};
 628                 for (int x = 0; x < size; x++) {
 629                         if (module(x, y) == runColor) {
 630                                 runX++;
 631                                 if (runX == 5)
 632                                         result += PENALTY_N1;
 633                                 else if (runX > 5)
 634                                         result++;
 635                         } else {
 636                                 finderPenaltyAddHistory(runX, runHistory);
 637                                 if (!runColor)
 638                                         result += finderPenaltyCountPatterns(runHistory) * PENALTY_N3;
 639                                 runColor = module(x, y);
 640                                 runX = 1;
 641                         }
 642                 }
 643                 result += finderPenaltyTerminateAndCount(runColor, runX, runHistory) * PENALTY_N3;
 644         }
 645         // Adjacent modules in column having same color, and finder-like patterns
 646         for (int x = 0; x < size; x++) {
 647                 bool runColor = false;
 648                 int runY = 0;
 649                 std::array<int,7> runHistory = {};
 650                 for (int y = 0; y < size; y++) {
 651                         if (module(x, y) == runColor) {
 652                                 runY++;
 653                                 if (runY == 5)
 654                                         result += PENALTY_N1;
 655                                 else if (runY > 5)
 656                                         result++;
 657                         } else {
 658                                 finderPenaltyAddHistory(runY, runHistory);
 659                                 if (!runColor)
 660                                         result += finderPenaltyCountPatterns(runHistory) * PENALTY_N3;
 661                                 runColor = module(x, y);
 662                                 runY = 1;
 663                         }
 664                 }
 665                 result += finderPenaltyTerminateAndCount(runColor, runY, runHistory) * PENALTY_N3;
 666         }
 667
 668         // 2*2 blocks of modules having same color
 669         for (int y = 0; y < size - 1; y++) {
 670                 for (int x = 0; x < size - 1; x++) {
 671                         bool  color = module(x, y);
 672                         if (  color == module(x + 1, y) &&
 673                               color == module(x, y + 1) &&
 674                               color == module(x + 1, y + 1))
 675                                 result += PENALTY_N2;
 676                 }
 677         }
 678
 679         // Balance of black and white modules
 680         int black = 0;
 681         for (const vector<bool> &row : modules) {
 682                 for (bool color : row) {
 683                         if (color)
 684                                 black++;
 685                 }
 686         }
 687         int total = size * size;  // Note that size is odd, so black/total != 1/2
 688         // Compute the smallest integer k >= 0 such that (45-5k)% <= black/total <= (55+5k)%
 689         int k = static_cast<int>((std::abs(black * 20L - total * 10L) + total - 1) / total) - 1;
 690         result += k * PENALTY_N4;
 691         return result;
 692 }
 693
 694
 695 vector<int> QrCode::getAlignmentPatternPositions() const {
 696         if (version == 1)
 697                 return vector<int>();
 698         else {
 699                 int numAlign = version / 7 + 2;
 700                 int step = (version == 32) ? 26 :
 701                         (version*4 + numAlign*2 + 1) / (numAlign*2 - 2) * 2;
 702                 vector<int> result;
 703                 for (int i = 0, pos = size - 7; i < numAlign - 1; i++, pos -= step)
 704                         result.insert(result.begin(), pos);
 705                 result.insert(result.begin(), 6);
 706                 return result;
 707         }
 708 }
 709
 710
 711 int QrCode::getNumRawDataModules(int ver) {
 712         if (ver < MIN_VERSION || ver > MAX_VERSION)
 713                 throw std::domain_error("Version number out of range");
 714         int result = (16 * ver + 128) * ver + 64;
 715         if (ver >= 2) {
 716                 int numAlign = ver / 7 + 2;
 717                 result -= (25 * numAlign - 10) * numAlign - 55;
 718                 if (ver >= 7)
 719                         result -= 36;
 720         }
 721         if (!(208 <= result && result <= 29648))
 722                 throw std::logic_error("Assertion error");
 723         return result;
 724 }
 725
 726
 727 int QrCode::getNumDataCodewords(int ver, Ecc ecl) {
 728         return getNumRawDataModules(ver) / 8
 729                 - ECC_CODEWORDS_PER_BLOCK    [static_cast<int>(ecl)][ver]
 730                 * NUM_ERROR_CORRECTION_BLOCKS[static_cast<int>(ecl)][ver];
 731 }
 732
 733
 734 vector<uint8_t> QrCode::reedSolomonComputeDivisor(int degree) {
 735         if (degree < 1 || degree > 255)
 736                 throw std::domain_error("Degree out of range");
 737         // Polynomial coefficients are stored from highest to lowest power, excluding the leading term which is always 1.
 738         // For example the polynomial x^3 + 255x^2 + 8x + 93 is stored as the uint8 array {255, 8, 93}.
 739         vector<uint8_t> result(static_cast<size_t>(degree));
 740         result.at(result.size() - 1) = 1;  // Start off with the monomial x^0
 741
 742         // Compute the product polynomial (x - r^0) * (x - r^1) * (x - r^2) * ... * (x - r^{degree-1}),
 743         // and drop the highest monomial term which is always 1x^degree.
 744         // Note that r = 0x02, which is a generator element of this field GF(2^8/0x11D).
 745         uint8_t root = 1;
 746         for (int i = 0; i < degree; i++) {
 747                 // Multiply the current product by (x - r^i)
 748                 for (size_t j = 0; j < result.size(); j++) {
 749                         result.at(j) = reedSolomonMultiply(result.at(j), root);
 750                         if (j + 1 < result.size())
 751                                 result.at(j) ^= result.at(j + 1);
 752                 }
 753                 root = reedSolomonMultiply(root, 0x02);
 754         }
 755         return result;
 756 }
 757
 758
 759 vector<uint8_t> QrCode::reedSolomonComputeRemainder(const vector<uint8_t> &data, const vector<uint8_t> &divisor) {
 760         vector<uint8_t> result(divisor.size());
 761         for (uint8_t b : data) {  // Polynomial division
 762                 uint8_t factor = b ^ result.at(0);
 763                 result.erase(result.begin());
 764                 result.push_back(0);
 765                 for (size_t i = 0; i < result.size(); i++)
 766                         result.at(i) ^= reedSolomonMultiply(divisor.at(i), factor);
 767         }
 768         return result;
 769 }
 770
 771
 772 uint8_t QrCode::reedSolomonMultiply(uint8_t x, uint8_t y) {
 773         // Russian peasant multiplication
 774         int z = 0;
 775         for (int i = 7; i >= 0; i--) {
 776                 z = (z << 1) ^ ((z >> 7) * 0x11D);
 777                 z ^= ((y >> i) & 1) * x;
 778         }
 779         if (z >> 8 != 0)
 780                 throw std::logic_error("Assertion error");
 781         return static_cast<uint8_t>(z);
 782 }
 783
 784
 785 int QrCode::finderPenaltyCountPatterns(const std::array<int,7> &runHistory) const {
 786         int n = runHistory.at(1);
 787         if (n > size * 3)
 788                 throw std::logic_error("Assertion error");
 789         bool core = n > 0 && runHistory.at(2) == n && runHistory.at(3) == n * 3 && runHistory.at(4) == n && runHistory.at(5) == n;
 790         return (core && runHistory.at(0) >= n * 4 && runHistory.at(6) >= n ? 1 : 0)
 791              + (core && runHistory.at(6) >= n * 4 && runHistory.at(0) >= n ? 1 : 0);
 792 }
 793
 794
 795 int QrCode::finderPenaltyTerminateAndCount(bool currentRunColor, int currentRunLength, std::array<int,7> &runHistory) const {
 796         if (currentRunColor) {  // Terminate black run
 797                 finderPenaltyAddHistory(currentRunLength, runHistory);
 798                 currentRunLength = 0;
 799         }
 800         currentRunLength += size;  // Add white border to final run
 801         finderPenaltyAddHistory(currentRunLength, runHistory);
 802         return finderPenaltyCountPatterns(runHistory);
 803 }
 804
 805
 806 void QrCode::finderPenaltyAddHistory(int currentRunLength, std::array<int,7> &runHistory) const {
 807         if (runHistory.at(0) == 0)
 808                 currentRunLength += size;  // Add white border to initial run
 809         std::copy_backward(runHistory.cbegin(), runHistory.cend() - 1, runHistory.end());
 810         runHistory.at(0) = currentRunLength;
 811 }
 812
 813
 814 bool QrCode::getBit(long x, int i) {
 815         return ((x >> i) & 1) != 0;
 816 }
 817
 818
 819 /*---- Tables of constants ----*/
 820
 821 const int QrCode::PENALTY_N1 =  3;
 822 const int QrCode::PENALTY_N2 =  3;
 823 const int QrCode::PENALTY_N3 = 40;
 824 const int QrCode::PENALTY_N4 = 10;
 825
 826
 827 const int8_t QrCode::ECC_CODEWORDS_PER_BLOCK[4][41] = {
 828         // Version: (note that index 0 is for padding, and is set to an illegal value)
 829         //0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40    Error correction level
 830         {-1,  7, 10, 15, 20, 26, 18, 20, 24, 30, 18, 20, 24, 26, 30, 22, 24, 28, 30, 28, 28, 28, 28, 30, 30, 26, 28, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30},  // Low
 831         {-1, 10, 16, 26, 18, 24, 16, 18, 22, 22, 26, 30, 22, 22, 24, 24, 28, 28, 26, 26, 26, 26, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28},  // Medium
 832         {-1, 13, 22, 18, 26, 18, 24, 18, 22, 20, 24, 28, 26, 24, 20, 30, 24, 28, 28, 26, 30, 28, 30, 30, 30, 30, 28, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30},  // Quartile
 833         {-1, 17, 28, 22, 16, 22, 28, 26, 26, 24, 28, 24, 28, 22, 24, 24, 30, 28, 28, 26, 28, 30, 24, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30},  // High
 834 };
 835
 836 const int8_t QrCode::NUM_ERROR_CORRECTION_BLOCKS[4][41] = {
 837         // Version: (note that index 0 is for padding, and is set to an illegal value)
 838         //0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40    Error correction level
 839         {-1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4,  4,  4,  4,  4,  6,  6,  6,  6,  7,  8,  8,  9,  9, 10, 12, 12, 12, 13, 14, 15, 16, 17, 18, 19, 19, 20, 21, 22, 24, 25},  // Low
 840         {-1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5,  5,  8,  9,  9, 10, 10, 11, 13, 14, 16, 17, 17, 18, 20, 21, 23, 25, 26, 28, 29, 31, 33, 35, 37, 38, 40, 43, 45, 47, 49},  // Medium
 841         {-1, 1, 1, 2, 2, 4, 4, 6, 6, 8, 8,  8, 10, 12, 16, 12, 17, 16, 18, 21, 20, 23, 23, 25, 27, 29, 34, 34, 35, 38, 40, 43, 45, 48, 51, 53, 56, 59, 62, 65, 68},  // Quartile
 842         {-1, 1, 1, 2, 4, 4, 4, 5, 6, 8, 8, 11, 11, 16, 16, 18, 16, 19, 21, 25, 25, 25, 34, 30, 32, 35, 37, 40, 42, 45, 48, 51, 54, 57, 60, 63, 66, 70, 74, 77, 81},  // High
 843 };
 844
 845
 846 data_too_long::data_too_long(const std::string &msg) :
 847         std::length_error(msg) {}
 848
 849
 850
 851 BitBuffer::BitBuffer()
 852         : std::vector<bool>() {}
 853
 854
 855 void BitBuffer::appendBits(std::uint32_t val, int len) {
 856         if (len < 0 || len > 31 || val >> len != 0)
 857                 throw std::domain_error("Value out of range");
 858         for (int i = len - 1; i >= 0; i--)  // Append bit by bit
 859                 this->push_back(((val >> i) & 1) != 0);
 860 }
 861
 862 }