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 #pragma once 25 #ifndef QRCODEEGEN_H 26 #define QRCODEEGEN_H 27 28 #include <array> 29 #include <cstdint> 30 #include <stdexcept> 31 #include <string> 32 #include <vector> 33 34 35 namespace qrcodegen { 36 37 /* 38 * A segment of character/binary/control data in a QR Code symbol. 39 * Instances of this class are immutable. 40 * The mid-level way to create a segment is to take the payload data 41 * and call a static factory function such as QrSegment::makeNumeric(). 42 * The low-level way to create a segment is to custom-make the bit buffer 43 * and call the QrSegment() constructor with appropriate values. 44 * This segment class imposes no length restrictions, but QR Codes have restrictions. 45 * Even in the most favorable conditions, a QR Code can only hold 7089 characters of data. 46 * Any segment longer than this is meaningless for the purpose of generating QR Codes. 47 */ 48 class QrSegment final { 49 50 /*---- Public helper enumeration ----*/ 51 52 /* 53 * Describes how a segment's data bits are interpreted. Immutable. 54 */ 55 public: class Mode final { 56 57 #if !defined(ACE_ENGINE_QRCODE_ABLE) 58 /*-- Constants --*/ 59 60 public: static const Mode NUMERIC; 61 public: static const Mode ALPHANUMERIC; 62 public: static const Mode BYTE; 63 public: static const Mode KANJI; 64 public: static const Mode ECI; 65 #endif 66 67 68 /*-- Fields --*/ 69 70 // The mode indicator bits, which is a uint4 value (range 0 to 15). 71 private: int modeBits; 72 73 // Number of character count bits for three different version ranges. 74 private: int numBitsCharCount[3]; 75 76 77 /*-- Constructor --*/ 78 79 #if defined(ACE_ENGINE_QRCODE_ABLE) 80 public: Mode(int mode, int cc0, int cc1, int cc2); 81 Mode()82 public: Mode() {} 83 #else 84 private: Mode(int mode, int cc0, int cc1, int cc2); 85 #endif 86 87 88 /*-- Methods --*/ 89 90 /* 91 * (Package-private) Returns the mode indicator bits, which is an unsigned 4-bit value (range 0 to 15). 92 */ 93 public: int getModeBits() const; 94 95 /* 96 * (Package-private) Returns the bit width of the character count field for a segment in 97 * this mode in a QR Code at the given version number. The result is in the range [0, 16]. 98 */ 99 public: int numCharCountBits(int ver) const; 100 101 }; 102 103 104 105 /*---- Static factory functions (mid level) ----*/ 106 107 /* 108 * Returns a segment representing the given binary data encoded in 109 * byte mode. All input byte vectors are acceptable. Any text string 110 * can be converted to UTF-8 bytes and encoded as a byte mode segment. 111 */ 112 #if defined(ACE_ENGINE_QRCODE_ABLE) 113 private: static QrSegment makeBytes(const std::vector<std::uint8_t> &data); 114 #else 115 public: static QrSegment makeBytes(const std::vector<std::uint8_t> &data); 116 117 #endif 118 119 #if !defined(ACE_ENGINE_QRCODE_ABLE) 120 /* 121 * Returns a segment representing the given string of decimal digits encoded in numeric mode. 122 */ 123 public: static QrSegment makeNumeric(const char *digits); 124 125 126 /* 127 * Returns a segment representing the given text string encoded in alphanumeric mode. 128 * The characters allowed are: 0 to 9, A to Z (uppercase only), space, 129 * dollar, percent, asterisk, plus, hyphen, period, slash, colon. 130 */ 131 public: static QrSegment makeAlphanumeric(const char *text); 132 133 #endif 134 135 /* 136 * Returns a list of zero or more segments to represent the given text string. The result 137 * may use various segment modes and switch modes to optimize the length of the bit stream. 138 */ 139 public: static std::vector<QrSegment> makeSegments(const char *text); 140 141 142 #if !defined(ACE_ENGINE_QRCODE_ABLE) 143 /* 144 * Returns a segment representing an Extended Channel Interpretation 145 * (ECI) designator with the given assignment value. 146 */ 147 public: static QrSegment makeEci(long assignVal); 148 149 150 /*---- Public static helper functions ----*/ 151 152 /* 153 * Tests whether the given string can be encoded as a segment in numeric mode. 154 * A string is encodable iff each character is in the range 0 to 9. 155 */ 156 public: static bool isNumeric(const char *text); 157 158 159 /* 160 * Tests whether the given string can be encoded as a segment in alphanumeric mode. 161 * A string is encodable iff each character is in the following set: 0 to 9, A to Z 162 * (uppercase only), space, dollar, percent, asterisk, plus, hyphen, period, slash, colon. 163 */ 164 public: static bool isAlphanumeric(const char *text); 165 #endif 166 167 168 /*---- Instance fields ----*/ 169 170 /* The mode indicator of this segment. Accessed through getMode(). */ 171 #if defined(ACE_ENGINE_QRCODE_ABLE) 172 private: Mode mode; 173 #else 174 private: const Mode *mode; 175 #endif 176 177 178 /* The length of this segment's unencoded data. Measured in characters for 179 * numeric/alphanumeric/kanji mode, bytes for byte mode, and 0 for ECI mode. 180 * Always zero or positive. Not the same as the data's bit length. 181 * Accessed through getNumChars(). */ 182 private: int numChars; 183 184 /* The data bits of this segment. Accessed through getData(). */ 185 private: std::vector<bool> data; 186 187 188 /*---- Constructors (low level) ----*/ 189 190 #if !defined(ACE_ENGINE_QRCODE_ABLE) 191 /* 192 * Creates a new QR Code segment with the given attributes and data. 193 * The character count (numCh) must agree with the mode and the bit buffer length, 194 * but the constraint isn't checked. The given bit buffer is copied and stored. 195 */ 196 public: QrSegment(const Mode &md, int numCh, const std::vector<bool> &dt); 197 #endif 198 199 200 /* 201 * Creates a new QR Code segment with the given parameters and data. 202 * The character count (numCh) must agree with the mode and the bit buffer length, 203 * but the constraint isn't checked. The given bit buffer is moved and stored. 204 */ 205 public: QrSegment(const Mode &md, int numCh, std::vector<bool> &&dt); 206 207 208 /*---- Methods ----*/ 209 210 /* 211 * Returns the mode field of this segment. 212 */ 213 public: const Mode &getMode() const; 214 215 216 /* 217 * Returns the character count field of this segment. 218 */ 219 public: int getNumChars() const; 220 221 222 /* 223 * Returns the data bits of this segment. 224 */ 225 public: const std::vector<bool> &getData() const; 226 227 228 // (Package-private) Calculates the number of bits needed to encode the given segments at 229 // the given version. Returns a non-negative number if successful. Otherwise returns -1 if a 230 // segment has too many characters to fit its length field, or the total bits exceeds INT_MAX. 231 public: static int getTotalBits(const std::vector<QrSegment> &segs, int version); 232 233 #if !defined(ACE_ENGINE_QRCODE_ABLE) 234 /*---- Private constant ----*/ 235 236 /* The set of all legal characters in alphanumeric mode, where 237 * each character value maps to the index in the string. */ 238 private: static const char *ALPHANUMERIC_CHARSET; 239 #endif 240 }; 241 242 243 244 /* 245 * A QR Code symbol, which is a type of two-dimension barcode. 246 * Invented by Denso Wave and described in the ISO/IEC 18004 standard. 247 * Instances of this class represent an immutable square grid of dark and light cells. 248 * The class provides static factory functions to create a QR Code from text or binary data. 249 * The class covers the QR Code Model 2 specification, supporting all versions (sizes) 250 * from 1 to 40, all 4 error correction levels, and 4 character encoding modes. 251 * 252 * Ways to create a QR Code object: 253 * - High level: Take the payload data and call QrCode::encodeText() or QrCode::encodeBinary(). 254 * - Mid level: Custom-make the list of segments and call QrCode::encodeSegments(). 255 * - Low level: Custom-make the array of data codeword bytes (including 256 * segment headers and final padding, excluding error correction codewords), 257 * supply the appropriate version number, and call the QrCode() constructor. 258 * (Note that all ways require supplying the desired error correction level.) 259 */ 260 class QrCode final { 261 262 /*---- Public helper enumeration ----*/ 263 264 /* 265 * The error correction level in a QR Code symbol. 266 */ 267 public: enum class Ecc { 268 LOW = 0 , // The QR Code can tolerate about 7% erroneous codewords 269 MEDIUM , // The QR Code can tolerate about 15% erroneous codewords 270 QUARTILE, // The QR Code can tolerate about 25% erroneous codewords 271 HIGH , // The QR Code can tolerate about 30% erroneous codewords 272 }; 273 274 275 // Returns a value in the range 0 to 3 (unsigned 2-bit integer). 276 private: static int getFormatBits(Ecc ecl); 277 278 279 280 /*---- Static factory functions (high level) ----*/ 281 282 /* 283 * Returns a QR Code representing the given Unicode text string at the given error correction level. 284 * As a conservative upper bound, this function is guaranteed to succeed for strings that have 2953 or fewer 285 * UTF-8 code units (not Unicode code points) if the low error correction level is used. The smallest possible 286 * QR Code version is automatically chosen for the output. The ECC level of the result may be higher than 287 * the ecl argument if it can be done without increasing the version. 288 */ 289 public: static QrCode encodeText(const char *text, Ecc ecl); 290 291 292 #if !defined(ACE_ENGINE_QRCODE_ABLE) 293 /* 294 * Returns a QR Code representing the given binary data at the given error correction level. 295 * This function always encodes using the binary segment mode, not any text mode. The maximum number of 296 * bytes allowed is 2953. The smallest possible QR Code version is automatically chosen for the output. 297 * The ECC level of the result may be higher than the ecl argument if it can be done without increasing the version. 298 */ 299 public: static QrCode encodeBinary(const std::vector<std::uint8_t> &data, Ecc ecl); 300 #endif 301 302 303 /*---- Static factory functions (mid level) ----*/ 304 305 /* 306 * Returns a QR Code representing the given segments with the given encoding parameters. 307 * The smallest possible QR Code version within the given range is automatically 308 * chosen for the output. Iff boostEcl is true, then the ECC level of the result 309 * may be higher than the ecl argument if it can be done without increasing the 310 * version. The mask number is either between 0 to 7 (inclusive) to force that 311 * mask, or -1 to automatically choose an appropriate mask (which may be slow). 312 * This function allows the user to create a custom sequence of segments that switches 313 * between modes (such as alphanumeric and byte) to encode text in less space. 314 * This is a mid-level API; the high-level API is encodeText() and encodeBinary(). 315 */ 316 #if defined(ACE_ENGINE_QRCODE_ABLE) 317 private: static QrCode encodeSegments(const std::vector<QrSegment> &segs, Ecc ecl, 318 int minVersion=1, int maxVersion=40, int mask=-1, bool boostEcl=true); // All optional parameters 319 #else 320 public: static QrCode encodeSegments(const std::vector<QrSegment> &segs, Ecc ecl, 321 int minVersion=1, int maxVersion=40, int mask=-1, bool boostEcl=true); // All optional parameters 322 #endif 323 324 325 326 /*---- Instance fields ----*/ 327 328 // Immutable scalar parameters: 329 330 /* The version number of this QR Code, which is between 1 and 40 (inclusive). 331 * This determines the size of this barcode. */ 332 private: int version; 333 334 /* The width and height of this QR Code, measured in modules, between 335 * 21 and 177 (inclusive). This is equal to version * 4 + 17. */ 336 private: int size; 337 338 /* The error correction level used in this QR Code. */ 339 private: Ecc errorCorrectionLevel; 340 341 /* The index of the mask pattern used in this QR Code, which is between 0 and 7 (inclusive). 342 * Even if a QR Code is created with automatic masking requested (mask = -1), 343 * the resulting object still has a mask value between 0 and 7. */ 344 private: int mask; 345 346 // Private grids of modules/pixels, with dimensions of size*size: 347 348 // The modules of this QR Code (false = light, true = dark). 349 // Immutable after constructor finishes. Accessed through getModule(). 350 private: std::vector<std::vector<bool> > modules; 351 352 // Indicates function modules that are not subjected to masking. Discarded when constructor finishes. 353 private: std::vector<std::vector<bool> > isFunction; 354 355 #if defined(ACE_ENGINE_QRCODE_ABLE) 356 /* QR Code Generation Success Flag. 357 * This Success :true */ 358 private: bool flag; 359 #endif 360 361 362 /*---- Constructor (low level) ----*/ 363 364 /* 365 * Creates a new QR Code with the given version number, 366 * error correction level, data codeword bytes, and mask number. 367 * This is a low-level API that most users should not use directly. 368 * A mid-level API is the encodeSegments() function. 369 */ 370 #if defined(ACE_ENGINE_QRCODE_ABLE) 371 private: QrCode(int ver, Ecc ecl, const std::vector<std::uint8_t> &dataCodewords, int msk); 372 #else 373 public: QrCode(int ver, Ecc ecl, const std::vector<std::uint8_t> &dataCodewords, int msk); 374 #endif 375 376 377 378 /*---- Public instance methods ----*/ 379 #if defined(ACE_ENGINE_QRCODE_ABLE) 380 /* 381 * Returns this QR Code's version, in the range [1, 40]. 382 */ 383 public: bool getFlag() const; 384 #endif 385 386 /* 387 * Returns this QR Code's version, in the range [1, 40]. 388 */ 389 public: int getVersion() const; 390 391 392 /* 393 * Returns this QR Code's size, in the range [21, 177]. 394 */ 395 public: int getSize() const; 396 397 398 /* 399 * Returns this QR Code's error correction level. 400 */ 401 public: Ecc getErrorCorrectionLevel() const; 402 403 404 /* 405 * Returns this QR Code's mask, in the range [0, 7]. 406 */ 407 public: int getMask() const; 408 409 410 /* 411 * Returns the color of the module (pixel) at the given coordinates, which is false 412 * for light or true for dark. The top left corner has the coordinates (x=0, y=0). 413 * If the given coordinates are out of bounds, then false (light) is returned. 414 */ 415 public: bool getModule(int x, int y) const; 416 417 418 419 /*---- Private helper methods for constructor: Drawing function modules ----*/ 420 421 // Reads this object's version field, and draws and marks all function modules. 422 private: void drawFunctionPatterns(); 423 424 425 // Draws two copies of the format bits (with its own error correction code) 426 // based on the given mask and this object's error correction level field. 427 private: void drawFormatBits(int msk); 428 429 430 // Draws two copies of the version bits (with its own error correction code), 431 // based on this object's version field, iff 7 <= version <= 40. 432 private: void drawVersion(); 433 434 435 // Draws a 9*9 finder pattern including the border separator, 436 // with the center module at (x, y). Modules can be out of bounds. 437 private: void drawFinderPattern(int x, int y); 438 439 440 // Draws a 5*5 alignment pattern, with the center module 441 // at (x, y). All modules must be in bounds. 442 private: void drawAlignmentPattern(int x, int y); 443 444 445 // Sets the color of a module and marks it as a function module. 446 // Only used by the constructor. Coordinates must be in bounds. 447 private: void setFunctionModule(int x, int y, bool isDark); 448 449 450 // Returns the color of the module at the given coordinates, which must be in range. 451 private: bool module(int x, int y) const; 452 453 454 /*---- Private helper methods for constructor: Codewords and masking ----*/ 455 456 // Returns a new byte string representing the given data with the appropriate error correction 457 // codewords appended to it, based on this object's version and error correction level. 458 #if defined(ACE_ENGINE_QRCODE_ABLE) 459 private: std::vector<std::uint8_t> addEccAndInterleave(const std::vector<std::uint8_t> &data); 460 #else 461 private: std::vector<std::uint8_t> addEccAndInterleave(const std::vector<std::uint8_t> &data) const; 462 #endif 463 464 465 // Draws the given sequence of 8-bit codewords (data and error correction) onto the entire 466 // data area of this QR Code. Function modules need to be marked off before this is called. 467 private: void drawCodewords(const std::vector<std::uint8_t> &data); 468 469 470 // XORs the codeword modules in this QR Code with the given mask pattern. 471 // The function modules must be marked and the codeword bits must be drawn 472 // before masking. Due to the arithmetic of XOR, calling applyMask() with 473 // the same mask value a second time will undo the mask. A final well-formed 474 // QR Code needs exactly one (not zero, two, etc.) mask applied. 475 private: void applyMask(int msk); 476 477 478 #if !defined(ACE_ENGINE_QRCODE_ABLE) 479 // Calculates and returns the penalty score based on state of this QR Code's current modules. 480 // This is used by the automatic mask choice algorithm to find the mask pattern that yields the lowest score. 481 private: long getPenaltyScore() const; 482 #endif 483 484 485 486 /*---- Private helper functions ----*/ 487 488 // Returns an ascending list of positions of alignment patterns for this version number. 489 // Each position is in the range [0,177), and are used on both the x and y axes. 490 // This could be implemented as lookup table of 40 variable-length lists of unsigned bytes. 491 private: std::vector<int> getAlignmentPatternPositions() const; 492 493 494 // Returns the number of data bits that can be stored in a QR Code of the given version number, after 495 // all function modules are excluded. This includes remainder bits, so it might not be a multiple of 8. 496 // The result is in the range [208, 29648]. This could be implemented as a 40-entry lookup table. 497 private: static int getNumRawDataModules(int ver); 498 499 500 // Returns the number of 8-bit data (i.e. not error correction) codewords contained in any 501 // QR Code of the given version number and error correction level, with remainder bits discarded. 502 // This stateless pure function could be implemented as a (40*4)-cell lookup table. 503 private: static int getNumDataCodewords(int ver, Ecc ecl); 504 505 506 // Returns a Reed-Solomon ECC generator polynomial for the given degree. This could be 507 // implemented as a lookup table over all possible parameter values, instead of as an algorithm. 508 #if defined(ACE_ENGINE_QRCODE_ABLE) 509 private: std::vector<std::uint8_t> reedSolomonComputeDivisor(int degree); 510 #else 511 private: static std::vector<std::uint8_t> reedSolomonComputeDivisor(int degree); 512 #endif 513 514 515 // Returns the Reed-Solomon error correction codeword for the given data and divisor polynomials. 516 #if defined(ACE_ENGINE_QRCODE_ABLE) 517 private: std::vector<std::uint8_t> reedSolomonComputeRemainder(const std::vector<std::uint8_t> &data, const std::vector<std::uint8_t> &divisor); 518 #else 519 private: static std::vector<std::uint8_t> reedSolomonComputeRemainder(const std::vector<std::uint8_t> &data, const std::vector<std::uint8_t> &divisor); 520 #endif 521 522 523 // Returns the product of the two given field elements modulo GF(2^8/0x11D). 524 // All inputs are valid. This could be implemented as a 256*256 lookup table. 525 #if defined(ACE_ENGINE_QRCODE_ABLE) 526 private: std::uint8_t reedSolomonMultiply(std::uint8_t x, std::uint8_t y); 527 #else 528 private: static std::uint8_t reedSolomonMultiply(std::uint8_t x, std::uint8_t y); 529 #endif 530 531 #if !defined(ACE_ENGINE_QRCODE_ABLE) 532 // Can only be called immediately after a light run is added, and 533 // returns either 0, 1, or 2. A helper function for getPenaltyScore(). 534 private: int finderPenaltyCountPatterns(const std::array<int,7> &runHistory) const; 535 536 537 // Must be called at the end of a line (row or column) of modules. A helper function for getPenaltyScore(). 538 private: int finderPenaltyTerminateAndCount(bool currentRunColor, int currentRunLength, std::array<int,7> &runHistory) const; 539 540 541 // Pushes the given value to the front and drops the last value. A helper function for getPenaltyScore(). 542 private: void finderPenaltyAddHistory(int currentRunLength, std::array<int,7> &runHistory) const; 543 #endif 544 545 #if defined(ACE_ENGINE_QRCODE_ABLE) 546 // clear Function. 547 private: void clearFunctionPatterns(); 548 #endif 549 550 551 // Returns true iff the i'th bit of x is set to 1. 552 private: static bool getBit(long x, int i); 553 554 555 /*---- Constants and tables ----*/ 556 557 #if defined(ACE_ENGINE_QRCODE_ABLE) 558 // The error version number supported in the QR Code Model 2 standard. 559 private: static constexpr int ERR_VERSION = 0; 560 #endif 561 // The minimum version number supported in the QR Code Model 2 standard. 562 #if defined(ACE_ENGINE_QRCODE_ABLE) 563 private: static constexpr int MIN_VERSION = 1; 564 #else 565 public: static constexpr int MIN_VERSION = 1; 566 #endif 567 568 // The maximum version number supported in the QR Code Model 2 standard. 569 #if defined(ACE_ENGINE_QRCODE_ABLE) 570 private: static constexpr int MAX_VERSION = 40; 571 #else 572 public: static constexpr int MAX_VERSION = 40; 573 #endif 574 #if !defined(ACE_ENGINE_QRCODE_ABLE) 575 // For use in getPenaltyScore(), when evaluating which mask is best. 576 private: static const int PENALTY_N1; 577 private: static const int PENALTY_N2; 578 private: static const int PENALTY_N3; 579 private: static const int PENALTY_N4; 580 #endif 581 582 private: static const std::int8_t ECC_CODEWORDS_PER_BLOCK[4][41]; 583 private: static const std::int8_t NUM_ERROR_CORRECTION_BLOCKS[4][41]; 584 585 }; 586 587 588 589 /*---- Public exception class ----*/ 590 591 /* 592 * Thrown when the supplied data does not fit any QR Code version. Ways to handle this exception include: 593 * - Decrease the error correction level if it was greater than Ecc::LOW. 594 * - If the encodeSegments() function was called with a maxVersion argument, then increase 595 * it if it was less than QrCode::MAX_VERSION. (This advice does not apply to the other 596 * factory functions because they search all versions up to QrCode::MAX_VERSION.) 597 * - Split the text data into better or optimal segments in order to reduce the number of bits required. 598 * - Change the text or binary data to be shorter. 599 * - Change the text to fit the character set of a particular segment mode (e.g. alphanumeric). 600 * - Propagate the error upward to the caller/user. 601 */ 602 class data_too_long : public std::length_error { 603 604 public: explicit data_too_long(const std::string &msg); 605 606 }; 607 608 609 610 /* 611 * An appendable sequence of bits (0s and 1s). Mainly used by QrSegment. 612 */ 613 class BitBuffer final : public std::vector<bool> { 614 615 /*---- Constructor ----*/ 616 617 // Creates an empty bit buffer (length 0). 618 public: BitBuffer(); 619 620 621 622 /*---- Method ----*/ 623 624 // Appends the given number of low-order bits of the given value 625 // to this buffer. Requires 0 <= len <= 31 and val < 2^len. 626 public: void appendBits(std::uint32_t val, int len); 627 628 }; 629 630 } 631 #endif // QRCODEEGEN_H 632