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 <cassert>
26 #include <climits>
27 #include <cstddef>
28 #include <cstdlib>
29 #include <cstring>
30 #include <sstream>
31 #include <utility>
32 #include "qrcodegen.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 /*---- Class QrSegment ----*/
43
Mode(int mode,int cc0,int cc1,int cc2)44 QrSegment::Mode::Mode(int mode, int cc0, int cc1, int cc2) :
45 modeBits(mode) {
46 numBitsCharCount[0] = cc0;
47 numBitsCharCount[1] = cc1;
48 numBitsCharCount[2] = cc2;
49 }
50
51
getModeBits() const52 int QrSegment::Mode::getModeBits() const {
53 return modeBits;
54 }
55
56
numCharCountBits(int ver) const57 int QrSegment::Mode::numCharCountBits(int ver) const {
58 return numBitsCharCount[(ver + 7) / 17];
59 }
60
61
62 #if !defined(ACE_ENGINE_QRCODE_ABLE)
63 const QrSegment::Mode QrSegment::Mode::NUMERIC (0x1, 10, 12, 14);
64 const QrSegment::Mode QrSegment::Mode::ALPHANUMERIC(0x2, 9, 11, 13);
65 const QrSegment::Mode QrSegment::Mode::BYTE (0x4, 8, 16, 16);
66 const QrSegment::Mode QrSegment::Mode::KANJI (0x8, 8, 10, 12);
67 const QrSegment::Mode QrSegment::Mode::ECI (0x7, 0, 0, 0);
68
69 #endif
70
makeBytes(const vector<uint8_t> & data)71 QrSegment QrSegment::makeBytes(const vector<uint8_t> &data) {
72 #if defined(ACE_ENGINE_QRCODE_ABLE)
73 BitBuffer bb;
74 for (uint8_t b : data)
75 bb.appendBits(b, 8);
76 Mode md(0x4, 8, 16, 16);
77 return QrSegment(md, static_cast<int>(data.size()), std::move(bb));
78 #else
79 if (data.size() > static_cast<unsigned int>(INT_MAX))
80 throw std::length_error("Data too long");
81 BitBuffer bb;
82 for (uint8_t b : data)
83 bb.appendBits(b, 8);
84 return QrSegment(Mode::BYTE, static_cast<int>(data.size()), std::move(bb));
85 #endif
86 }
87
88
89 #if !defined(ACE_ENGINE_QRCODE_ABLE)
makeNumeric(const char * digits)90 QrSegment QrSegment::makeNumeric(const char *digits) {
91 BitBuffer bb;
92 int accumData = 0;
93 int accumCount = 0;
94 int charCount = 0;
95 for (; *digits != '\0'; digits++, charCount++) {
96 char c = *digits;
97 if (c < '0' || c > '9')
98 throw std::domain_error("String contains non-numeric characters");
99 accumData = accumData * 10 + (c - '0');
100 accumCount++;
101 if (accumCount == 3) {
102 bb.appendBits(static_cast<uint32_t>(accumData), 10);
103 accumData = 0;
104 accumCount = 0;
105 }
106 }
107 if (accumCount > 0) // 1 or 2 digits remaining
108 bb.appendBits(static_cast<uint32_t>(accumData), accumCount * 3 + 1);
109 return QrSegment(Mode::NUMERIC, charCount, std::move(bb));
110 }
111
112
makeAlphanumeric(const char * text)113 QrSegment QrSegment::makeAlphanumeric(const char *text) {
114 BitBuffer bb;
115 int accumData = 0;
116 int accumCount = 0;
117 int charCount = 0;
118 for (; *text != '\0'; text++, charCount++) {
119 const char *temp = std::strchr(ALPHANUMERIC_CHARSET, *text);
120 if (temp == nullptr)
121 throw std::domain_error("String contains unencodable characters in alphanumeric mode");
122 accumData = accumData * 45 + static_cast<int>(temp - ALPHANUMERIC_CHARSET);
123 accumCount++;
124 if (accumCount == 2) {
125 bb.appendBits(static_cast<uint32_t>(accumData), 11);
126 accumData = 0;
127 accumCount = 0;
128 }
129 }
130 if (accumCount > 0) // 1 character remaining
131 bb.appendBits(static_cast<uint32_t>(accumData), 6);
132 return QrSegment(Mode::ALPHANUMERIC, charCount, std::move(bb));
133 }
134
135 #endif
136
makeSegments(const char * text)137 vector<QrSegment> QrSegment::makeSegments(const char *text) {
138 // Select the most efficient segment encoding automatically
139 vector<QrSegment> result;
140 if (*text == '\0'); // Leave result empty
141 #if !defined(ACE_ENGINE_QRCODE_ABLE)
142 else if (isNumeric(text))
143 result.push_back(makeNumeric(text));
144 else if (isAlphanumeric(text))
145 result.push_back(makeAlphanumeric(text));
146 #endif
147 else {
148 vector<uint8_t> bytes;
149 for (; *text != '\0'; text++)
150 bytes.push_back(static_cast<uint8_t>(*text));
151 result.push_back(makeBytes(bytes));
152 }
153 return result;
154 }
155
156 #if !defined(ACE_ENGINE_QRCODE_ABLE)
157
makeEci(long assignVal)158 QrSegment QrSegment::makeEci(long assignVal) {
159 BitBuffer bb;
160 if (assignVal < 0)
161 throw std::domain_error("ECI assignment value out of range");
162 else if (assignVal < (1 << 7))
163 bb.appendBits(static_cast<uint32_t>(assignVal), 8);
164 else if (assignVal < (1 << 14)) {
165 bb.appendBits(2, 2);
166 bb.appendBits(static_cast<uint32_t>(assignVal), 14);
167 } else if (assignVal < 1000000L) {
168 bb.appendBits(6, 3);
169 bb.appendBits(static_cast<uint32_t>(assignVal), 21);
170 } else
171 throw std::domain_error("ECI assignment value out of range");
172 return QrSegment(Mode::ECI, 0, std::move(bb));
173 }
174
175
QrSegment(const Mode & md,int numCh,const std::vector<bool> & dt)176 QrSegment::QrSegment(const Mode &md, int numCh, const std::vector<bool> &dt) :
177 mode(&md),
178 numChars(numCh),
179 data(dt) {
180 if (numCh < 0)
181 throw std::domain_error("Invalid value");
182 }
183
184 #endif
185
QrSegment(const Mode & md,int numCh,std::vector<bool> && dt)186 QrSegment::QrSegment(const Mode &md, int numCh, std::vector<bool> &&dt) :
187 #if defined(ACE_ENGINE_QRCODE_ABLE)
188 mode(md),
189 #else
190 mode(&md),
191 #endif
192 numChars(numCh),
193 data(std::move(dt)) {
194 #if !defined(ACE_ENGINE_QRCODE_ABLE)
195 if (numCh < 0)
196 throw std::domain_error("Invalid value");
197 #endif
198 }
199
200
getTotalBits(const vector<QrSegment> & segs,int version)201 int QrSegment::getTotalBits(const vector<QrSegment> &segs, int version) {
202 int result = 0;
203 for (const QrSegment &seg : segs) {
204 #if defined(ACE_ENGINE_QRCODE_ABLE)
205 int ccbits = seg.mode.numCharCountBits(version);
206 #else
207 int ccbits = seg.mode->numCharCountBits(version);
208 #endif
209 if (seg.numChars >= (1L << ccbits))
210 return -1; // The segment's length doesn't fit the field's bit width
211 if (4 + ccbits > INT_MAX - result)
212 return -1; // The sum will overflow an int type
213 result += 4 + ccbits;
214 if (seg.data.size() > static_cast<unsigned int>(INT_MAX - result))
215 return -1; // The sum will overflow an int type
216 result += static_cast<int>(seg.data.size());
217 }
218 return result;
219 }
220
221 #if !defined(ACE_ENGINE_QRCODE_ABLE)
222
isNumeric(const char * text)223 bool QrSegment::isNumeric(const char *text) {
224 for (; *text != '\0'; text++) {
225 char c = *text;
226 if (c < '0' || c > '9')
227 return false;
228 }
229 return true;
230 }
231
232
isAlphanumeric(const char * text)233 bool QrSegment::isAlphanumeric(const char *text) {
234 for (; *text != '\0'; text++) {
235 if (std::strchr(ALPHANUMERIC_CHARSET, *text) == nullptr)
236 return false;
237 }
238 return true;
239 }
240
241 #endif
242
getMode() const243 const QrSegment::Mode &QrSegment::getMode() const {
244 #if defined(ACE_ENGINE_QRCODE_ABLE)
245 return mode;
246 #else
247 return *mode;
248 #endif
249 }
250
251
getNumChars() const252 int QrSegment::getNumChars() const {
253 return numChars;
254 }
255
256
getData() const257 const std::vector<bool> &QrSegment::getData() const {
258 return data;
259 }
260
261 #if !defined(ACE_ENGINE_QRCODE_ABLE)
262
263 const char *QrSegment::ALPHANUMERIC_CHARSET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:";
264
265 #endif
266
267 /*---- Class QrCode ----*/
268
getFormatBits(Ecc ecl)269 int QrCode::getFormatBits(Ecc ecl) {
270 switch (ecl) {
271 case Ecc::LOW : return 1;
272 case Ecc::MEDIUM : return 0;
273 case Ecc::QUARTILE: return 3;
274 case Ecc::HIGH : return 2;
275 #if defined(ACE_ENGINE_QRCODE_ABLE)
276 default: return -1; //This scenario does not exist after adaptation.
277 #else
278 default: throw std::logic_error("Unreachable");
279 #endif
280 }
281 }
282
283
encodeText(const char * text,Ecc ecl)284 QrCode QrCode::encodeText(const char *text, Ecc ecl) {
285 vector<QrSegment> segs = QrSegment::makeSegments(text);
286 #if defined(ACE_ENGINE_QRCODE_ABLE)
287 return encodeSegments(segs, ecl, MIN_VERSION, MAX_VERSION, 5);
288 #else
289 return encodeSegments(segs, ecl);
290 #endif
291 }
292
293
294 #if !defined(ACE_ENGINE_QRCODE_ABLE)
encodeBinary(const vector<uint8_t> & data,Ecc ecl)295 QrCode QrCode::encodeBinary(const vector<uint8_t> &data, Ecc ecl) {
296 vector<QrSegment> segs{QrSegment::makeBytes(data)};
297 return encodeSegments(segs, ecl);
298 }
299 #endif
300
301
encodeSegments(const vector<QrSegment> & segs,Ecc ecl,int minVersion,int maxVersion,int mask,bool boostEcl)302 QrCode QrCode::encodeSegments(const vector<QrSegment> &segs, Ecc ecl,
303 int minVersion, int maxVersion, int mask, bool boostEcl) {
304 #if !defined(ACE_ENGINE_QRCODE_ABLE)
305 if (!(MIN_VERSION <= minVersion && minVersion <= maxVersion && maxVersion <= MAX_VERSION) || mask < -1 || mask > 7)
306 throw std::invalid_argument("Invalid value");
307
308 #endif
309 // Find the minimal version number to use
310 int version, dataUsedBits;
311 #if defined(ACE_ENGINE_QRCODE_ABLE)
312 vector<uint8_t> dataCodewordsTemp;
313 #endif
314 #if defined(ACE_ENGINE_QRCODE_ABLE)
315 for (version = minVersion; ; version++) {
316 int dataCapacityBits = getNumDataCodewords(version, ecl) * 8; // Number of data bits available
317 dataUsedBits = QrSegment::getTotalBits(segs, version);
318 if (dataUsedBits != -1 && dataUsedBits <= dataCapacityBits)
319 break; // This version number is found to be suitable
320 if (version >= maxVersion) { // All versions in the range could not fit the given data
321 return QrCode(ERR_VERSION, ecl, dataCodewordsTemp, mask);
322 }
323 }
324 #else
325 for (version = minVersion; ; version++) {
326 int dataCapacityBits = getNumDataCodewords(version, ecl) * 8; // Number of data bits available
327 dataUsedBits = QrSegment::getTotalBits(segs, version);
328 if (dataUsedBits != -1 && dataUsedBits <= dataCapacityBits)
329 break; // This version number is found to be suitable
330 if (version >= maxVersion) { // All versions in the range could not fit the given data
331 std::ostringstream sb;
332 if (dataUsedBits == -1)
333 sb << "Segment too long";
334 else {
335 sb << "Data length = " << dataUsedBits << " bits, ";
336 sb << "Max capacity = " << dataCapacityBits << " bits";
337 }
338 throw data_too_long(sb.str());
339 }
340 }
341 #endif
342 #if defined(ACE_ENGINE_QRCODE_ABLE)
343 if (dataUsedBits == -1)
344 return QrCode(ERR_VERSION, ecl, dataCodewordsTemp, mask);
345 #else
346 assert(dataUsedBits != -1);
347 #endif
348
349 // Increase the error correction level while the data still fits in the current version number
350 for (Ecc newEcl : {Ecc::MEDIUM, Ecc::QUARTILE, Ecc::HIGH}) { // From low to high
351 if (boostEcl && dataUsedBits <= getNumDataCodewords(version, newEcl) * 8)
352 ecl = newEcl;
353 }
354
355 // Concatenate all segments to create the data bit string
356 BitBuffer bb;
357 for (const QrSegment &seg : segs) {
358 bb.appendBits(static_cast<uint32_t>(seg.getMode().getModeBits()), 4);
359 bb.appendBits(static_cast<uint32_t>(seg.getNumChars()), seg.getMode().numCharCountBits(version));
360 bb.insert(bb.end(), seg.getData().begin(), seg.getData().end());
361 }
362 #if defined(ACE_ENGINE_QRCODE_ABLE)
363 if (bb.size() != static_cast<unsigned int>(dataUsedBits))
364 return QrCode(ERR_VERSION, ecl, dataCodewordsTemp, mask);
365 #else
366 assert(bb.size() == static_cast<unsigned int>(dataUsedBits));
367 #endif
368
369 // Add terminator and pad up to a byte if applicable
370 size_t dataCapacityBits = static_cast<size_t>(getNumDataCodewords(version, ecl)) * 8;
371 #if defined(ACE_ENGINE_QRCODE_ABLE)
372 if (bb.size() > dataCapacityBits)
373 return QrCode(ERR_VERSION, ecl, dataCodewordsTemp, mask);
374 #else
375 assert(bb.size() <= dataCapacityBits);
376 #endif
377 bb.appendBits(0, std::min(4, static_cast<int>(dataCapacityBits - bb.size())));
378 bb.appendBits(0, (8 - static_cast<int>(bb.size() % 8)) % 8);
379 #if defined(ACE_ENGINE_QRCODE_ABLE)
380 if (bb.size() % 8 != 0)
381 return QrCode(ERR_VERSION, ecl, dataCodewordsTemp, mask);
382 #else
383 assert(bb.size() % 8 == 0);
384 #endif
385
386 // Pad with alternating bytes until data capacity is reached
387 for (uint8_t padByte = 0xEC; bb.size() < dataCapacityBits; padByte ^= 0xEC ^ 0x11)
388 bb.appendBits(padByte, 8);
389
390 // Pack bits into bytes in big endian
391 vector<uint8_t> dataCodewords(bb.size() / 8);
392 for (size_t i = 0; i < bb.size(); i++)
393 dataCodewords.at(i >> 3) |= (bb.at(i) ? 1 : 0) << (7 - (i & 7));
394
395 // Create the QR Code object
396 return QrCode(version, ecl, dataCodewords, mask);
397 }
398
399
QrCode(int ver,Ecc ecl,const vector<uint8_t> & dataCodewords,int msk)400 QrCode::QrCode(int ver, Ecc ecl, const vector<uint8_t> &dataCodewords, int msk) :
401 // Initialize fields and check arguments
402 #if defined(ACE_ENGINE_QRCODE_ABLE)
403 version(ver), errorCorrectionLevel(ecl), flag(true) {
404 if (ver < MIN_VERSION || ver > MAX_VERSION) {
405 flag = false;
406 return;
407 }
408
409 if (msk < -1 || msk > 7) {
410 flag = false;
411 return;
412 }
413 #else
414 version(ver),
415 errorCorrectionLevel(ecl) {
416 if (ver < MIN_VERSION || ver > MAX_VERSION)
417 throw std::domain_error("Version value out of range");
418 if (msk < -1 || msk > 7)
419 throw std::domain_error("Mask value out of range");
420 #endif
421 size = ver * 4 + 17;
422 size_t sz = static_cast<size_t>(size);
423 modules = vector<vector<bool> >(sz, vector<bool>(sz)); // Initially all light
424 isFunction = vector<vector<bool> >(sz, vector<bool>(sz));
425
426 // Compute ECC, draw modules
427 drawFunctionPatterns();
428 #if defined(ACE_ENGINE_QRCODE_ABLE)
429 if (!flag) {
430 clearFunctionPatterns();
431 return;
432 }
433 #endif
434
435 const vector<uint8_t> allCodewords = addEccAndInterleave(dataCodewords);
436 #if defined(ACE_ENGINE_QRCODE_ABLE)
437 if (!flag){
438 clearFunctionPatterns();
439 return;
440 }
441 #endif
442
443 drawCodewords(allCodewords);
444 #if defined(ACE_ENGINE_QRCODE_ABLE)
445 if (!flag) {
446 clearFunctionPatterns();
447 return;
448 }
449 #else
450 // Do masking
451 if (msk == -1) { // Automatically choose best mask
452 long minPenalty = LONG_MAX;
453 for (int i = 0; i < 8; i++) {
454 applyMask(i);
455 drawFormatBits(i);
456 long penalty = getPenaltyScore();
457 if (penalty < minPenalty) {
458 msk = i;
459 minPenalty = penalty;
460 }
461 applyMask(i); // Undoes the mask due to XOR
462 }
463 }
464 assert(0 <= msk && msk <= 7);
465 #endif
466 mask = msk;
467 applyMask(msk); // Apply the final choice of mask
468 #if defined(ACE_ENGINE_QRCODE_ABLE)
469 if (!flag) {
470 clearFunctionPatterns();
471 return;
472 }
473 #endif
474
475 drawFormatBits(msk); // Overwrite old format bits
476
477 #if defined(ACE_ENGINE_QRCODE_ABLE)
478 clearFunctionPatterns();
479 #else
480 isFunction.clear();
481 isFunction.shrink_to_fit();
482 #endif
483 }
484
485 #if defined(ACE_ENGINE_QRCODE_ABLE)
486 bool QrCode::getFlag() const {
487 return flag;
488 }
489 #endif
490
491 int QrCode::getVersion() const {
492 return version;
493 }
494
495
496 int QrCode::getSize() const {
497 return size;
498 }
499
500
501 QrCode::Ecc QrCode::getErrorCorrectionLevel() const {
502 return errorCorrectionLevel;
503 }
504
505
506 int QrCode::getMask() const {
507 return mask;
508 }
509
510
511 bool QrCode::getModule(int x, int y) const {
512 return 0 <= x && x < size && 0 <= y && y < size && module(x, y);
513 }
514
515
516 void QrCode::drawFunctionPatterns() {
517 // Draw horizontal and vertical timing patterns
518 for (int i = 0; i < size; i++) {
519 setFunctionModule(6, i, i % 2 == 0);
520 setFunctionModule(i, 6, i % 2 == 0);
521 }
522
523 // Draw 3 finder patterns (all corners except bottom right; overwrites some timing modules)
524 drawFinderPattern(3, 3);
525 drawFinderPattern(size - 4, 3);
526 drawFinderPattern(3, size - 4);
527
528 // Draw numerous alignment patterns
529 const vector<int> alignPatPos = getAlignmentPatternPositions();
530 size_t numAlign = alignPatPos.size();
531 for (size_t i = 0; i < numAlign; i++) {
532 for (size_t j = 0; j < numAlign; j++) {
533 // Don't draw on the three finder corners
534 if (!((i == 0 && j == 0) || (i == 0 && j == numAlign - 1) || (i == numAlign - 1 && j == 0)))
535 drawAlignmentPattern(alignPatPos.at(i), alignPatPos.at(j));
536 }
537 }
538
539 // Draw configuration data
540 drawFormatBits(0); // Dummy mask value; overwritten later in the constructor
541
542 #if defined(ACE_ENGINE_QRCODE_ABLE)
543 if (!flag) {
544 return;
545 }
546 #endif
547
548 drawVersion();
549 }
550
551
552 void QrCode::drawFormatBits(int msk) {
553 // Calculate error correction code and pack bits
554 int data = getFormatBits(errorCorrectionLevel) << 3 | msk; // errCorrLvl is uint2, msk is uint3
555 int rem = data;
556 for (int i = 0; i < 10; i++)
557 rem = (rem << 1) ^ ((rem >> 9) * 0x537);
558 int bits = (data << 10 | rem) ^ 0x5412; // uint15
559 #if defined(ACE_ENGINE_QRCODE_ABLE)
560 if (bits >> 15 != 0) {
561 flag = false;
562 return;
563 }
564 #else
565 assert(bits >> 15 == 0);
566 #endif
567
568 // Draw first copy
569 for (int i = 0; i <= 5; i++)
570 setFunctionModule(8, i, getBit(bits, i));
571 setFunctionModule(8, 7, getBit(bits, 6));
572 setFunctionModule(8, 8, getBit(bits, 7));
573 setFunctionModule(7, 8, getBit(bits, 8));
574 for (int i = 9; i < 15; i++)
575 setFunctionModule(14 - i, 8, getBit(bits, i));
576
577 // Draw second copy
578 for (int i = 0; i < 8; i++)
579 setFunctionModule(size - 1 - i, 8, getBit(bits, i));
580 for (int i = 8; i < 15; i++)
581 setFunctionModule(8, size - 15 + i, getBit(bits, i));
582 setFunctionModule(8, size - 8, true); // Always dark
583 }
584
585
586 void QrCode::drawVersion() {
587 if (version < 7)
588 return;
589
590 // Calculate error correction code and pack bits
591 int rem = version; // version is uint6, in the range [7, 40]
592 for (int i = 0; i < 12; i++)
593 rem = (rem << 1) ^ ((rem >> 11) * 0x1F25);
594 long bits = static_cast<long>(version) << 12 | rem; // uint18
595 #if defined(ACE_ENGINE_QRCODE_ABLE)
596 if (bits >> 18 != 0) {
597 flag = false;
598 return;
599 }
600 #else
601 assert(bits >> 18 == 0);
602 #endif
603
604 // Draw two copies
605 for (int i = 0; i < 18; i++) {
606 bool bit = getBit(bits, i);
607 int a = size - 11 + i % 3;
608 int b = i / 3;
609 setFunctionModule(a, b, bit);
610 setFunctionModule(b, a, bit);
611 }
612 }
613
614
615 void QrCode::drawFinderPattern(int x, int y) {
616 for (int dy = -4; dy <= 4; dy++) {
617 for (int dx = -4; dx <= 4; dx++) {
618 int dist = std::max(std::abs(dx), std::abs(dy)); // Chebyshev/infinity norm
619 int xx = x + dx, yy = y + dy;
620 if (0 <= xx && xx < size && 0 <= yy && yy < size)
621 setFunctionModule(xx, yy, dist != 2 && dist != 4);
622 }
623 }
624 }
625
626
627 void QrCode::drawAlignmentPattern(int x, int y) {
628 for (int dy = -2; dy <= 2; dy++) {
629 for (int dx = -2; dx <= 2; dx++)
630 setFunctionModule(x + dx, y + dy, std::max(std::abs(dx), std::abs(dy)) != 1);
631 }
632 }
633
634
635 void QrCode::setFunctionModule(int x, int y, bool isDark) {
636 size_t ux = static_cast<size_t>(x);
637 size_t uy = static_cast<size_t>(y);
638 modules .at(uy).at(ux) = isDark;
639 isFunction.at(uy).at(ux) = true;
640 }
641
642
643 bool QrCode::module(int x, int y) const {
644 return modules.at(static_cast<size_t>(y)).at(static_cast<size_t>(x));
645 }
646
647
648 #if defined(ACE_ENGINE_QRCODE_ABLE)
649 vector<uint8_t> QrCode::addEccAndInterleave(const vector<uint8_t> &data) {
650 vector<uint8_t> result;
651 if (data.size() != static_cast<unsigned int>(getNumDataCodewords(version, errorCorrectionLevel))) {
652 flag = false;
653 return result;
654 }
655 #else
656 vector<uint8_t> QrCode::addEccAndInterleave(const vector<uint8_t> &data) const {
657 if (data.size() != static_cast<unsigned int>(getNumDataCodewords(version, errorCorrectionLevel)))
658 throw std::invalid_argument("Invalid argument");
659 #endif
660
661 // Calculate parameter numbers
662 int numBlocks = NUM_ERROR_CORRECTION_BLOCKS[static_cast<int>(errorCorrectionLevel)][version];
663 int blockEccLen = ECC_CODEWORDS_PER_BLOCK [static_cast<int>(errorCorrectionLevel)][version];
664 int rawCodewords = getNumRawDataModules(version) / 8;
665 int numShortBlocks = numBlocks - rawCodewords % numBlocks;
666 int shortBlockLen = rawCodewords / numBlocks;
667
668 // Split data into blocks and append ECC to each block
669 vector<vector<uint8_t> > blocks;
670 const vector<uint8_t> rsDiv = reedSolomonComputeDivisor(blockEccLen);
671 #if defined(ACE_ENGINE_QRCODE_ABLE)
672 if (!flag) {
673 return result;
674 }
675 #endif
676 for (int i = 0, k = 0; i < numBlocks; i++) {
677 vector<uint8_t> dat(data.cbegin() + k, data.cbegin() + (k + shortBlockLen - blockEccLen + (i < numShortBlocks ? 0 : 1)));
678 k += static_cast<int>(dat.size());
679 const vector<uint8_t> ecc = reedSolomonComputeRemainder(dat, rsDiv);
680 #if defined(ACE_ENGINE_QRCODE_ABLE)
681 if (!flag) {
682 return result;
683 }
684 #endif
685 if (i < numShortBlocks)
686 dat.push_back(0);
687 dat.insert(dat.end(), ecc.cbegin(), ecc.cend());
688 blocks.push_back(std::move(dat));
689 }
690
691 // Interleave (not concatenate) the bytes from every block into a single sequence
692 #if !defined(ACE_ENGINE_QRCODE_ABLE)
693 vector<uint8_t> result;
694 #endif
695 for (size_t i = 0; i < blocks.at(0).size(); i++) {
696 for (size_t j = 0; j < blocks.size(); j++) {
697 // Skip the padding byte in short blocks
698 if (i != static_cast<unsigned int>(shortBlockLen - blockEccLen) || j >= static_cast<unsigned int>(numShortBlocks))
699 result.push_back(blocks.at(j).at(i));
700 }
701 }
702 #if defined(ACE_ENGINE_QRCODE_ABLE)
703 if (result.size() != static_cast<unsigned int>(rawCodewords))
704 flag = false;
705 #else
706 assert(result.size() == static_cast<unsigned int>(rawCodewords));
707 #endif
708 return result;
709 }
710
711
712 void QrCode::drawCodewords(const vector<uint8_t> &data) {
713 #if defined(ACE_ENGINE_QRCODE_ABLE)
714 if (data.size() != static_cast<unsigned int>(getNumRawDataModules(version) / 8)) {
715 flag = false;
716 return;
717 }
718 #else
719 if (data.size() != static_cast<unsigned int>(getNumRawDataModules(version) / 8))
720 throw std::invalid_argument("Invalid argument");
721 #endif
722
723 size_t i = 0; // Bit index into the data
724 // Do the funny zigzag scan
725 for (int right = size - 1; right >= 1; right -= 2) { // Index of right column in each column pair
726 if (right == 6)
727 right = 5;
728 for (int vert = 0; vert < size; vert++) { // Vertical counter
729 for (int j = 0; j < 2; j++) {
730 size_t x = static_cast<size_t>(right - j); // Actual x coordinate
731 bool upward = ((right + 1) & 2) == 0;
732 size_t y = static_cast<size_t>(upward ? size - 1 - vert : vert); // Actual y coordinate
733 if (!isFunction.at(y).at(x) && i < data.size() * 8) {
734 modules.at(y).at(x) = getBit(data.at(i >> 3), 7 - static_cast<int>(i & 7));
735 i++;
736 }
737 // If this QR Code has any remainder bits (0 to 7), they were assigned as
738 // 0/false/light by the constructor and are left unchanged by this method
739 }
740 }
741 }
742 #if defined(ACE_ENGINE_QRCODE_ABLE)
743 if (i != data.size() * 8){
744 flag = false;
745 return;
746 }
747 #else
748 assert(i == data.size() * 8);
749 #endif
750 }
751
752
753 void QrCode::applyMask(int msk) {
754 #if !defined(ACE_ENGINE_QRCODE_ABLE)
755 if (msk < 0 || msk > 7)
756 throw std::domain_error("Mask value out of range");
757 #endif
758 size_t sz = static_cast<size_t>(size);
759 for (size_t y = 0; y < sz; y++) {
760 for (size_t x = 0; x < sz; x++) {
761 bool invert;
762 switch (msk) {
763 case 0: invert = (x + y) % 2 == 0; break;
764 case 1: invert = y % 2 == 0; break;
765 case 2: invert = x % 3 == 0; break;
766 case 3: invert = (x + y) % 3 == 0; break;
767 case 4: invert = (x / 3 + y / 2) % 2 == 0; break;
768 case 5: invert = x * y % 2 + x * y % 3 == 0; break;
769 case 6: invert = (x * y % 2 + x * y % 3) % 2 == 0; break;
770 case 7: invert = ((x + y) % 2 + x * y % 3) % 2 == 0; break;
771 #if defined(ACE_ENGINE_QRCODE_ABLE)
772 default: return;
773 #else
774 default: throw std::logic_error("Unreachable");
775 #endif
776 }
777 modules.at(y).at(x) = modules.at(y).at(x) ^ (invert & !isFunction.at(y).at(x));
778 }
779 }
780 }
781
782
783 #if !defined(ACE_ENGINE_QRCODE_ABLE)
784 long QrCode::getPenaltyScore() const {
785 long result = 0;
786
787 // Adjacent modules in row having same color, and finder-like patterns
788 for (int y = 0; y < size; y++) {
789 bool runColor = false;
790 int runX = 0;
791 std::array<int,7> runHistory = {};
792 for (int x = 0; x < size; x++) {
793 if (module(x, y) == runColor) {
794 runX++;
795 if (runX == 5)
796 result += PENALTY_N1;
797 else if (runX > 5)
798 result++;
799 } else {
800 finderPenaltyAddHistory(runX, runHistory);
801 if (!runColor)
802 result += finderPenaltyCountPatterns(runHistory) * PENALTY_N3;
803 runColor = module(x, y);
804 runX = 1;
805 }
806 }
807 result += finderPenaltyTerminateAndCount(runColor, runX, runHistory) * PENALTY_N3;
808 }
809 // Adjacent modules in column having same color, and finder-like patterns
810 for (int x = 0; x < size; x++) {
811 bool runColor = false;
812 int runY = 0;
813 std::array<int,7> runHistory = {};
814 for (int y = 0; y < size; y++) {
815 if (module(x, y) == runColor) {
816 runY++;
817 if (runY == 5)
818 result += PENALTY_N1;
819 else if (runY > 5)
820 result++;
821 } else {
822 finderPenaltyAddHistory(runY, runHistory);
823 if (!runColor)
824 result += finderPenaltyCountPatterns(runHistory) * PENALTY_N3;
825 runColor = module(x, y);
826 runY = 1;
827 }
828 }
829 result += finderPenaltyTerminateAndCount(runColor, runY, runHistory) * PENALTY_N3;
830 }
831
832 // 2*2 blocks of modules having same color
833 for (int y = 0; y < size - 1; y++) {
834 for (int x = 0; x < size - 1; x++) {
835 bool color = module(x, y);
836 if ( color == module(x + 1, y) &&
837 color == module(x, y + 1) &&
838 color == module(x + 1, y + 1))
839 result += PENALTY_N2;
840 }
841 }
842
843 // Balance of dark and light modules
844 int dark = 0;
845 for (const vector<bool> &row : modules) {
846 for (bool color : row) {
847 if (color)
848 dark++;
849 }
850 }
851 int total = size * size; // Note that size is odd, so dark/total != 1/2
852 // Compute the smallest integer k >= 0 such that (45-5k)% <= dark/total <= (55+5k)%
853 int k = static_cast<int>((std::abs(dark * 20L - total * 10L) + total - 1) / total) - 1;
854 assert(0 <= k && k <= 9);
855 result += k * PENALTY_N4;
856 assert(0 <= result && result <= 2568888L); // Non-tight upper bound based on default values of PENALTY_N1, ..., N4
857 return result;
858 }
859
860 #endif
861
862 vector<int> QrCode::getAlignmentPatternPositions() const {
863 if (version == 1)
864 return vector<int>();
865 else {
866 int numAlign = version / 7 + 2;
867 int step = (version == 32) ? 26 :
868 (version * 4 + numAlign * 2 + 1) / (numAlign * 2 - 2) * 2;
869 vector<int> result;
870 for (int i = 0, pos = size - 7; i < numAlign - 1; i++, pos -= step)
871 result.insert(result.begin(), pos);
872 result.insert(result.begin(), 6);
873 return result;
874 }
875 }
876
877
878 int QrCode::getNumRawDataModules(int ver) {
879 #if !defined(ACE_ENGINE_QRCODE_ABLE)
880 if (ver < MIN_VERSION || ver > MAX_VERSION)
881 throw std::domain_error("Version number out of range");
882 #endif
883 int result = (16 * ver + 128) * ver + 64;
884 if (ver >= 2) {
885 int numAlign = ver / 7 + 2;
886 result -= (25 * numAlign - 10) * numAlign - 55;
887 if (ver >= 7)
888 result -= 36;
889 }
890 #if !defined(ACE_ENGINE_QRCODE_ABLE)
891 assert(208 <= result && result <= 29648);
892 #endif
893 return result;
894 }
895
896
897 int QrCode::getNumDataCodewords(int ver, Ecc ecl) {
898 return getNumRawDataModules(ver) / 8
899 - ECC_CODEWORDS_PER_BLOCK [static_cast<int>(ecl)][ver]
900 * NUM_ERROR_CORRECTION_BLOCKS[static_cast<int>(ecl)][ver];
901 }
902
903
904 vector<uint8_t> QrCode::reedSolomonComputeDivisor(int degree) {
905 #if !defined(ACE_ENGINE_QRCODE_ABLE)
906 if (degree < 1 || degree > 255)
907 throw std::domain_error("Degree out of range");
908 #endif
909 // Polynomial coefficients are stored from highest to lowest power, excluding the leading term which is always 1.
910 // For example the polynomial x^3 + 255x^2 + 8x + 93 is stored as the uint8 array {255, 8, 93}.
911 vector<uint8_t> result(static_cast<size_t>(degree));
912 result.at(result.size() - 1) = 1; // Start off with the monomial x^0
913
914 // Compute the product polynomial (x - r^0) * (x - r^1) * (x - r^2) * ... * (x - r^{degree-1}),
915 // and drop the highest monomial term which is always 1x^degree.
916 // Note that r = 0x02, which is a generator element of this field GF(2^8/0x11D).
917 uint8_t root = 1;
918 for (int i = 0; i < degree; i++) {
919 // Multiply the current product by (x - r^i)
920 for (size_t j = 0; j < result.size(); j++) {
921 result.at(j) = reedSolomonMultiply(result.at(j), root);
922 #if defined(ACE_ENGINE_QRCODE_ABLE)
923 if (!flag) {
924 return result;
925 }
926 #endif
927 if (j + 1 < result.size())
928 result.at(j) ^= result.at(j + 1);
929 }
930 root = reedSolomonMultiply(root, 0x02);
931 #if defined(ACE_ENGINE_QRCODE_ABLE)
932 if (!flag) {
933 return result;
934 }
935 #endif
936 }
937 return result;
938 }
939
940
941 vector<uint8_t> QrCode::reedSolomonComputeRemainder(const vector<uint8_t> &data, const vector<uint8_t> &divisor) {
942 vector<uint8_t> result(divisor.size());
943 for (uint8_t b : data) { // Polynomial division
944 uint8_t factor = b ^ result.at(0);
945 result.erase(result.begin());
946 result.push_back(0);
947 #if defined(ACE_ENGINE_QRCODE_ABLE)
948 for (size_t i = 0; i < result.size(); i++) {
949 result.at(i) ^= reedSolomonMultiply(divisor.at(i), factor);
950 if (!flag) {
951 return result;
952 }
953 }
954 #else
955 for (size_t i = 0; i < result.size(); i++)
956 result.at(i) ^= reedSolomonMultiply(divisor.at(i), factor);
957 #endif
958 }
959 return result;
960 }
961
962
963 uint8_t QrCode::reedSolomonMultiply(uint8_t x, uint8_t y) {
964 // Russian peasant multiplication
965 int z = 0;
966 for (int i = 7; i >= 0; i--) {
967 z = (z << 1) ^ ((z >> 7) * 0x11D);
968 z ^= ((y >> i) & 1) * x;
969 }
970 #if defined(ACE_ENGINE_QRCODE_ABLE)
971 if (z >> 8 != 0)
972 flag = false;
973 return static_cast<uint8_t>(z);
974 #else
975 assert(z >> 8 == 0);
976 return static_cast<uint8_t>(z);
977 #endif
978 }
979
980 #if !defined(ACE_ENGINE_QRCODE_ABLE)
981 int QrCode::finderPenaltyCountPatterns(const std::array<int,7> &runHistory) const {
982 int n = runHistory.at(1);
983 assert(n <= size * 3);
984 bool core = n > 0 && runHistory.at(2) == n && runHistory.at(3) == n * 3 && runHistory.at(4) == n && runHistory.at(5) == n;
985 return (core && runHistory.at(0) >= n * 4 && runHistory.at(6) >= n ? 1 : 0)
986 + (core && runHistory.at(6) >= n * 4 && runHistory.at(0) >= n ? 1 : 0);
987 }
988
989
990 int QrCode::finderPenaltyTerminateAndCount(bool currentRunColor, int currentRunLength, std::array<int,7> &runHistory) const {
991 if (currentRunColor) { // Terminate dark run
992 finderPenaltyAddHistory(currentRunLength, runHistory);
993 currentRunLength = 0;
994 }
995 currentRunLength += size; // Add light border to final run
996 finderPenaltyAddHistory(currentRunLength, runHistory);
997 return finderPenaltyCountPatterns(runHistory);
998 }
999
1000
1001 void QrCode::finderPenaltyAddHistory(int currentRunLength, std::array<int,7> &runHistory) const {
1002 if (runHistory.at(0) == 0)
1003 currentRunLength += size; // Add light border to initial run
1004 std::copy_backward(runHistory.cbegin(), runHistory.cend() - 1, runHistory.end());
1005 runHistory.at(0) = currentRunLength;
1006 }
1007 #endif
1008
1009 #if defined(ACE_ENGINE_QRCODE_ABLE)
1010 void QrCode::clearFunctionPatterns()
1011 {
1012 isFunction.clear();
1013 isFunction.shrink_to_fit();
1014 }
1015 #endif
1016
1017
1018 bool QrCode::getBit(long x, int i) {
1019 return ((x >> i) & 1) != 0;
1020 }
1021
1022
1023 /*---- Tables of constants ----*/
1024
1025 #if !defined(ACE_ENGINE_QRCODE_ABLE)
1026 const int QrCode::PENALTY_N1 = 3;
1027 const int QrCode::PENALTY_N2 = 3;
1028 const int QrCode::PENALTY_N3 = 40;
1029 const int QrCode::PENALTY_N4 = 10;
1030 #endif
1031
1032
1033 const int8_t QrCode::ECC_CODEWORDS_PER_BLOCK[4][41] = {
1034 // Version: (note that index 0 is for padding, and is set to an illegal value)
1035 //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
1036 {-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
1037 {-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
1038 {-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
1039 {-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
1040 };
1041
1042 const int8_t QrCode::NUM_ERROR_CORRECTION_BLOCKS[4][41] = {
1043 // Version: (note that index 0 is for padding, and is set to an illegal value)
1044 //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
1045 {-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
1046 {-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
1047 {-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
1048 {-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
1049 };
1050
1051
1052 #if !defined(ACE_ENGINE_QRCODE_ABLE)
1053 data_too_long::data_too_long(const std::string &msg) :
1054 std::length_error(msg) {}
1055 #endif
1056
1057
1058
1059 /*---- Class BitBuffer ----*/
1060
1061 BitBuffer::BitBuffer()
1062 : std::vector<bool>() {}
1063
1064
1065 void BitBuffer::appendBits(std::uint32_t val, int len) {
1066 #if defined(ACE_ENGINE_QRCODE_ABLE)
1067 if (len < 0 || len > 31 || val >> len != 0)
1068 return;
1069 #else
1070 if (len < 0 || len > 31 || val >> len != 0)
1071 throw std::domain_error("Value out of range");
1072 #endif
1073 for (int i = len - 1; i >= 0; i--) // Append bit by bit
1074 this->push_back(((val >> i) & 1) != 0);
1075 }
1076
1077 }
1078