7 #include "aztecbarcode.h"
8 #include "bitvector_p.h"
9 #include "prison_debug.h"
10 #include "reedsolomon_p.h"
25 FullGridInterval = 16,
26 FullModeMessageSize = 40,
31 CompactModeMessageSize = 28,
32 CompactLayerCount = 4,
35 AztecBarcode::AztecBarcode()
39 AztecBarcode::~AztecBarcode() =
default;
42 struct aztec_layer_property_t {
48 static const aztec_layer_property_t aztec_layer_properties[] = {{2, 6, ReedSolomon::GF64},
49 {8, 8, ReedSolomon::GF256},
50 {22, 10, ReedSolomon::GF1024},
51 {32, 12, ReedSolomon::GF4096}};
54 static int aztecCompactDataBits(
int layer)
56 return (88 + 16 * layer) * layer;
59 static int aztecFullDataBits(
int layer)
61 return (112 + 16 * layer) * layer;
70 int codewordCount = 0;
71 int availableBits = 0;
73 bool compactMode =
false;
74 BitVector encodedData;
79 for (
auto i = 1; i <= FullLayerCount; ++i) {
80 if (aztecFullDataBits(i) * 0.77 > (inputData.size() + stuffSize)) {
85 for (
auto i = 1; i <= CompactLayerCount; ++i) {
86 if (aztecCompactDataBits(i) * 0.77 > (inputData.size() + stuffSize)) {
92 if (layerCount == 0) {
93 qCWarning(
Log) <<
"data too large for Aztec code" << inputData.size();
98 const auto propIt = std::lower_bound(aztec_layer_properties, aztec_layer_properties + 4, layerCount, [](
const aztec_layer_property_t &lhs,
int rhs) {
99 return lhs.layer < rhs;
103 auto stuffedData = bitStuffAndPad(inputData, (*propIt).codeWordSize);
104 stuffSize = stuffedData.size() - inputData.size();
106 availableBits = compactMode ? aztecCompactDataBits(layerCount) : aztecFullDataBits(layerCount);
107 codewordCount = stuffedData.size() / (*propIt).codeWordSize;
108 const auto rsWordCount = availableBits / (*propIt).codeWordSize - codewordCount;
111 ReedSolomon rs((*propIt).gf, rsWordCount);
112 const auto rsData = rs.encode(stuffedData);
115 encodedData.reserve(availableBits);
116 if (
int diff = availableBits - stuffedData.size() - rsData.size()) {
117 encodedData.appendMSB(0, diff);
119 encodedData.append(stuffedData);
120 encodedData.append(rsData);
123 }
while (encodedData.size() > availableBits);
128 modeMsg.appendMSB(layerCount - 1, 2);
129 modeMsg.appendMSB(codewordCount - 1, 6);
130 ReedSolomon rs(ReedSolomon::GF16, 5);
131 modeMsg.append(rs.encode(modeMsg));
133 modeMsg.appendMSB(layerCount - 1, 5);
134 modeMsg.appendMSB(codewordCount - 1, 11);
135 ReedSolomon rs(ReedSolomon::GF16, 6);
136 modeMsg.append(rs.encode(modeMsg));
143 paintCompactGrid(&img);
144 paintCompactData(&img, encodedData, layerCount);
145 paintCompactModeMessage(&img, modeMsg);
146 return cropAndScaleCompact(&img, layerCount);
151 paintFullData(&img, encodedData, layerCount);
152 paintFullModeMessage(&img, modeMsg);
153 return cropAndScaleFull(&img, layerCount);
178 struct aztec_code_t {
183 static const aztec_code_t aztec_code_table[] = {
185 {2, Mixed}, {3, Mixed}, {4, Mixed},
186 {5, Mixed}, {6, Mixed}, {7, Mixed},
188 {9, Mixed}, {10, Mixed}, {11, Mixed},
189 {12, Mixed}, {13, Mixed}, {CarriageReturn, Special},
196 {16, Mixed}, {17, Mixed}, {18, Mixed},
197 {19, Mixed}, {Space, Special},
198 {6, Punct}, {7, Punct}, {8, Punct},
199 {9, Punct}, {10, Punct}, {11, Punct},
200 {12, Punct}, {13, Punct},
201 {14, Punct}, {15, Punct}, {16, Punct},
207 {3, Digit}, {4, Digit}, {5, Digit},
208 {6, Digit}, {7, Digit}, {8, Digit},
209 {9, Digit}, {10, Digit}, {11, Digit},
213 {24, Punct}, {25, Punct},
217 {3, Upper}, {4, Upper}, {5, Upper},
218 {6, Upper}, {7, Upper}, {8, Upper},
219 {9, Upper}, {10, Upper}, {11, Upper},
220 {12, Upper}, {13, Upper}, {14, Upper},
221 {15, Upper}, {16, Upper}, {17, Upper},
222 {18, Upper}, {19, Upper}, {20, Upper},
223 {21, Upper}, {22, Upper}, {23, Upper},
224 {24, Upper}, {25, Upper}, {26, Upper},
233 {3, Lower}, {4, Lower}, {5, Lower},
234 {6, Lower}, {7, Lower}, {8, Lower},
235 {9, Lower}, {10, Lower}, {11, Lower},
236 {12, Lower}, {13, Lower}, {14, Lower},
237 {15, Lower}, {16, Lower}, {17, Lower},
238 {18, Lower}, {19, Lower}, {20, Lower},
239 {21, Lower}, {22, Lower}, {23, Lower},
240 {24, Lower}, {25, Lower}, {26, Lower},
248 Q_STATIC_ASSERT(
sizeof(aztec_code_table) == 256);
250 static const struct {
254 } aztec_code_double_symbols[] = {
255 {
'\r',
'\n', {2, Punct}},
256 {
'.',
' ', {3, Punct}},
257 {
',',
' ', {4, Punct}},
258 {
':',
' ', {5, Punct}}
261 static const int aztec_code_size[] = {0, 5, 5, 5, 5, 4, 8};
262 Q_STATIC_ASSERT(
sizeof(aztec_code_size) /
sizeof(
int) == MODE_COUNT);
265 static const aztec_code_t aztec_special_chars[SPECIAL_CHAR_COUNT][MODE_COUNT] = {
267 {{0, NoMode}, {1, Upper}, {1, Lower}, {1, Mixed}, {1, Upper}, {1, Digit}, {0, NoMode}},
268 {{0, NoMode}, {1, Punct}, {1, Punct}, {14, Mixed}, {1, Punct}, {1, Punct}, {0, NoMode}},
269 {{0, NoMode}, {17, Punct}, {17, Punct}, {17, Punct}, {17, Punct}, {12, Digit}, {0, NoMode}},
270 {{0, NoMode}, {19, Punct}, {19, Punct}, {19, Punct}, {19, Punct}, {13, Digit}, {0, NoMode}},
275 static const aztec_code_t aztec_shift_codes[MODE_COUNT - 1][MODE_COUNT - 1] = {
277 {{0, NoMode}, {0, NoMode}, {0, NoMode}, {0, NoMode}, {0, NoMode}, {0, NoMode}},
278 {{0, NoMode}, {0, NoMode}, {0, NoMode}, {0, NoMode}, {0, Punct}, {0, NoMode}},
279 {{0, NoMode}, {28, Upper}, {0, NoMode}, {0, NoMode}, {0, Punct}, {0, NoMode}},
280 {{0, NoMode}, {0, NoMode}, {0, NoMode}, {0, NoMode}, {0, Punct}, {0, NoMode}},
281 {{0, NoMode}, {0, NoMode}, {0, NoMode}, {0, NoMode}, {0, NoMode}, {0, NoMode}},
282 {{0, NoMode}, {15, Upper}, {0, NoMode}, {0, NoMode}, {0, Punct}, {0, NoMode}}};
285 static const aztec_code_t aztec_latch_codes[MODE_COUNT - 1][MODE_COUNT] = {
287 {{0, NoMode}, {0, NoMode}, {0, NoMode}, {0, NoMode}, {0, NoMode}, {0, NoMode}, {0, NoMode}},
288 {{0, NoMode}, {0, NoMode}, {28, Lower}, {29, Mixed}, {29, Mixed}, {30, Digit}, {31,
Binary}},
289 {{0, NoMode}, {30, Digit}, {0, NoMode}, {29, Mixed}, {29, Mixed}, {30, Digit}, {31,
Binary}},
290 {{0, NoMode}, {29, Upper}, {28, Lower}, {0, NoMode}, {30, Punct}, {28, Lower}, {31,
Binary}},
291 {{0, NoMode}, {31, Upper}, {31, Upper}, {31, Upper}, {0, NoMode}, {31, Upper}, {31, Upper}},
292 {{0, NoMode}, {14, Upper}, {14, Upper}, {14, Upper}, {14, Upper}, {0, NoMode}, {14, Upper}}};
294 static Mode aztecCodeLatchTo(Mode currentMode, Mode targetMode, BitVector *v)
296 if (currentMode == targetMode) {
299 const auto latchCode = aztec_latch_codes[currentMode][targetMode];
300 qCDebug(
Log) <<
"latch" << latchCode.code << aztec_code_size[currentMode];
301 v->appendMSB(latchCode.code, aztec_code_size[currentMode]);
302 return static_cast<Mode
>(latchCode.mode);
305 static void aztecEncodeBinary(std::vector<aztec_code_t>::iterator &it,
const std::vector<aztec_code_t>::iterator &end, BitVector *v)
308 const auto binEndIt = std::find_if(it, end, [](aztec_code_t sym) {
309 return sym.mode !=
Binary;
311 const auto length = std::distance(it, binEndIt);
314 qCDebug(
Log) <<
"binary length" << length;
316 v->appendMSB(length, 5);
319 v->appendMSB(length - 31, 11);
323 for (; it != binEndIt; ++it) {
324 qCDebug(
Log) <<
"binary data" << (*it).code;
325 v->appendMSB((*it).code, 8);
329 static void aztecEncodeResolveAmbigious(Mode currentMode,
const std::vector<aztec_code_t>::iterator &begin,
const std::vector<aztec_code_t>::iterator &end)
331 Q_ASSERT(begin != end);
332 Q_ASSERT(currentMode != (*begin).mode);
333 Q_ASSERT((*begin).mode == Special);
337 for (; it !=
end && (*it).mode == Special; ++it) {
338 if (aztec_special_chars[(*it).code][currentMode].mode == currentMode) {
339 qCDebug(
Log) <<
"special resolved to current mode by forward search";
340 (*it).mode = aztec_special_chars[(*it).code][currentMode].mode;
341 (*it).code = aztec_special_chars[(*it).code][currentMode].code;
347 while (std::distance(begin, backIt) >= 1 && it != end) {
349 if ((*backIt).mode == Special && aztec_special_chars[(*backIt).code][(*it).mode].mode == (*it).mode) {
350 qCDebug(
Log) <<
"special resolved by backward search";
351 (*backIt).mode = aztec_special_chars[(*backIt).code][(*it).mode].mode;
352 (*backIt).code = aztec_special_chars[(*backIt).code][(*it).mode].code;
359 if ((*begin).mode != Special) {
362 (*begin).mode = aztec_special_chars[(*begin).code][currentMode].mode;
363 (*begin).code = aztec_special_chars[(*begin).code][currentMode].code;
365 if (it != end && (*it).mode == Special) {
366 aztecEncodeResolveAmbigious(
static_cast<Mode
>((*begin).mode), it, end);
370 static Mode aztecNextMode(Mode currentMode,
const std::vector<aztec_code_t>::iterator &nextSym,
const std::vector<aztec_code_t>::iterator &end,
bool &tryShift)
372 Q_ASSERT(currentMode != (*nextSym).mode);
373 Q_ASSERT(nextSym != end);
374 Q_ASSERT((*nextSym).mode != Special);
377 if (it != end && (*it).mode == Special) {
378 aztecEncodeResolveAmbigious(
static_cast<Mode
>((*nextSym).mode), it, end);
381 if ((it == end || (*it).mode == currentMode) && std::distance(nextSym, it) == 1) {
385 qCDebug(
Log) << currentMode << (*nextSym).mode << tryShift << std::distance(nextSym, it);
386 return static_cast<Mode
>((*nextSym).mode);
389 BitVector AztecBarcode::aztecEncode(
const QByteArray &data)
const
392 std::vector<aztec_code_t> codes;
394 for (
int i = 0; i <
data.
size(); ++i) {
395 const uint8_t c1 =
data.
at(i);
398 const uint8_t c2 =
data.
at(i + 1);
400 for (
const auto &dblCode : aztec_code_double_symbols) {
401 if (dblCode.c1 != c1 || dblCode.c2 != c2) {
404 codes.push_back(dblCode.sym);
415 codes.push_back({c1,
Binary});
418 codes.push_back(aztec_code_table[c1]);
423 Mode currentMode = Upper;
425 for (
auto it = codes.begin(); it != codes.end();) {
426 if ((*it).mode == Binary) {
427 auto newMode = aztecCodeLatchTo(currentMode, Binary, &result);
428 while (newMode != Binary) {
429 currentMode = newMode;
430 newMode = aztecCodeLatchTo(currentMode, Binary, &result);
432 aztecEncodeBinary(it, codes.end(), &result);
436 if ((*it).mode == Special) {
437 aztecEncodeResolveAmbigious(currentMode, it, codes.end());
441 Mode nextMode = currentMode;
442 if ((*it).mode != currentMode) {
443 bool tryShift =
false;
444 const auto newMode = aztecNextMode(currentMode, it, codes.end(), tryShift);
447 if (tryShift && aztec_shift_codes[currentMode][newMode].mode != NoMode) {
448 qCDebug(
Log) <<
"shift" << aztec_shift_codes[currentMode][newMode].code << aztec_code_size[currentMode];
449 result.appendMSB(aztec_shift_codes[currentMode][newMode].code, aztec_code_size[currentMode]);
450 currentMode = newMode;
454 while (currentMode != newMode && newMode != NoMode && currentMode != NoMode) {
455 currentMode = aztecCodeLatchTo(currentMode, newMode, &result);
456 nextMode = currentMode;
460 qCDebug(
Log) << (*it).code << aztec_code_size[currentMode];
461 result.appendMSB((*it).code, aztec_code_size[currentMode]);
464 currentMode = nextMode;
470 BitVector AztecBarcode::bitStuffAndPad(
const BitVector &input,
int codeWordSize)
const
473 res.reserve(input.size());
477 while (i < input.size() - (codeWordSize - 1)) {
478 int v = input.valueAtMSB(i, codeWordSize - 1);
479 res.appendMSB(v, codeWordSize - 1);
480 i += codeWordSize - 1;
483 }
else if (v == (1 << (codeWordSize - 1)) - 1) {
484 res.appendBit(
false);
486 res.appendBit(input.at(i++));
489 while (i < input.size()) {
490 res.appendBit(input.at(i++));
494 const auto trailingBits = res.size() % codeWordSize;
502 for (
int i = res.size() - trailingBits; i < res.size(); ++i) {
503 allOnes &= res.at(i);
505 while (res.size() % codeWordSize) {
506 if ((res.size() % codeWordSize) == (codeWordSize - 1)) {
507 res.appendBit(allOnes ?
false :
true);
516 void AztecBarcode::paintFullGrid(
QImage *img)
const
523 pen.setDashPattern({1, 1});
525 for (
int i = 0; i < img->
width() / 2; i += FullGridInterval) {
526 p.drawLine(-i, -FullRadius, -i, FullRadius);
527 p.drawLine(i, -FullRadius, i, FullRadius);
528 p.drawLine(-FullRadius, -i, FullRadius, -i);
529 p.drawLine(-FullRadius, i, FullRadius, i);
535 p.drawRect(-7, -7, 14, 14);
541 p.drawRect(-2, -2, 4, 4);
542 p.drawRect(-4, -4, 8, 8);
543 p.drawRect(-6, -6, 12, 12);
546 p.drawRect(-7, -7, 1, 1);
547 p.drawRect(7, -7, 0, 1);
551 static const int aztecFullLayerOffset[] = {
553 66, 64, 62, 60, 57, 55, 53, 51, 49, 47, 45, 42, 40, 38, 36, 34, 32, 30, 28, 25, 23, 21, 19, 17, 15, 13, 10, 8, 6, 4, 2, 0};
555 void AztecBarcode::paintFullData(
QImage *img,
const BitVector &data,
int layerCount)
const
561 for (
int layer = layerCount - 1; layer >= 0; --layer) {
562 const auto x1 = aztecFullLayerOffset[layer];
564 const auto gridInMiddle = (x1 - FullRadius) % FullGridInterval == 0;
565 const auto x2 = gridInMiddle ? x1 + 2 : x1 + 1;
566 const auto segmentLength = FullMaxSize - 2 * y1 - 2 - (gridInMiddle ? 1 : 0);
568 for (
int rotation = 0; rotation < 4; ++rotation) {
571 p.rotate(-90 * rotation);
572 p.translate(-img->
width() / 2, -img->
height() / 2);
574 for (
int i = 0; it !=
data.
end(); ++i, ++it) {
575 const auto x = (i % 2 == 0) ? x1 : x2;
577 if (((y - FullRadius - 1) % FullGridInterval) == 0) {
581 if (y >= y1 + segmentLength) {
592 void AztecBarcode::paintFullModeMessage(
QImage *img,
const BitVector &modeData)
const
594 Q_ASSERT(modeData.size() == FullModeMessageSize);
599 auto it = modeData.begin();
600 for (
int rotation = 0; rotation < 4; ++rotation) {
603 p.rotate(90 * rotation);
605 for (
int i = -5; i <= 5; ++i) {
617 QImage AztecBarcode::cropAndScaleFull(
QImage *img,
int layerCount)
619 const auto offset = aztecFullLayerOffset[layerCount - 1];
620 const auto minSize = FullMaxSize - 2 * offset;
625 const auto srcRect = img->
rect().
adjusted(offset, offset, -offset, -offset);
626 p.drawImage(out.rect(), *img, srcRect);
630 void AztecBarcode::paintCompactGrid(
QImage *img)
const
638 p.drawRect(-2, -2, 4, 4);
639 p.drawRect(-4, -4, 8, 8);
642 p.drawRect(-5, -5, 1, 1);
643 p.drawRect(5, -5, 0, 1);
647 static const int aztecCompactLayerOffset[] = {6, 4, 2, 0};
649 void AztecBarcode::paintCompactData(
QImage *img,
const BitVector &data,
int layerCount)
const
655 for (
int layer = layerCount - 1; layer >= 0; --layer) {
656 const auto x1 = aztecCompactLayerOffset[layer];
658 const auto x2 = x1 + 1;
659 const auto segmentLength = CompactMaxSize - 2 * y1 - 2;
661 for (
int rotation = 0; rotation < 4; ++rotation) {
664 p.rotate(-90 * rotation);
665 p.translate(-img->
width() / 2, -img->
height() / 2);
667 for (
int i = 0; it !=
data.
end(); ++i, ++it) {
668 const auto x = (i % 2 == 0) ? x1 : x2;
670 if (y >= y1 + segmentLength) {
681 void AztecBarcode::paintCompactModeMessage(
QImage *img,
const BitVector &modeData)
const
683 Q_ASSERT(modeData.size() == CompactModeMessageSize);
688 auto it = modeData.begin();
689 for (
int rotation = 0; rotation < 4; ++rotation) {
692 p.rotate(90 * rotation);
694 for (
int i = -3; i <= 3; ++i) {
703 QImage AztecBarcode::cropAndScaleCompact(
QImage *img,
int layerCount)
705 const auto offset = aztecCompactLayerOffset[layerCount - 1];
706 const auto minSize = CompactMaxSize - 2 * offset;
711 const auto srcRect = img->
rect().
adjusted(offset, offset, -offset, -offset);
712 p.drawImage(out.rect(), *img, srcRect);