Google Git
Sign in
chromium / chromium / src.git / 857c8d8c9792d3911148f05031d11dd5fe0f9235 / . / components / qr_code_generator / qr_code_generator.cc
blob: 12e38b823ad6b88614cf98c0b2ff284c097b414b [file] [log] [blame]
// Copyright 2020 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "components/qr_code_generator/qr_code_generator.h"
#include <math.h>
#include <string.h>
#include <ostream>
#include <vector>
#include "base/check_op.h"
#include "base/memory/raw_ptr.h"
#include "base/notreached.h"
// kMaxVersionWithSmallLengths is the maximum QR version that uses the smaller
// length fields, i.e. that is |VersionClass::SMALL|. See table 3.
static constexpr int kMaxVersionWithSmallLengths = 9;
// A structure containing QR version-specific constants and data.
// All versions currently use error correction at level M.
struct QRVersionInfo {
enum class ECC {
kLow = 0,
kMedium = 1,
};
constexpr QRVersionInfo(const int version,
const ECC ecc,
const uint32_t encoded_version,
const int size,
const size_t group1_bytes,
const size_t group1_num_blocks,
const size_t group1_block_data_bytes,
const size_t group2_bytes,
const size_t group2_num_blocks,
const size_t group2_block_data_bytes,
const std::array<int, 3> alignment_locations)
: version(version),
ecc(ecc),
encoded_version(encoded_version),
size(size),
group1_bytes(group1_bytes),
group1_num_blocks(group1_num_blocks),
group1_block_data_bytes(group1_block_data_bytes),
group2_bytes(group2_bytes),
group2_num_blocks(group2_num_blocks),
group2_block_data_bytes(group2_block_data_bytes),
alignment_locations(alignment_locations) {
if (version < 1 || version > 40 || size < 0 ||
!CheckBlockGroupParameters(group1_bytes, group1_num_blocks,
group1_block_data_bytes) ||
(group2_num_blocks != 0 &&
!CheckBlockGroupParameters(group2_bytes, group2_num_blocks,
group2_block_data_bytes)) ||
(version < 7 && encoded_version != 0) ||
(version >= 7 &&
encoded_version >> 12 != static_cast<uint32_t>(version)) ||
(group2_num_blocks != 0 &&
group2_block_ec_bytes() != group1_block_ec_bytes())) {
__builtin_unreachable();
}
}
QRVersionInfo(const QRVersionInfo&) = delete;
QRVersionInfo& operator=(const QRVersionInfo&) = delete;
// The version of the QR code.
const int version;
// The error correction level.
const ECC ecc;
// An 18-bit value that contains the version, BCH (18,6)-encoded. Only valid
// for versions seven and above. See table D.1 for values.
const uint32_t encoded_version;
// The number of "tiles" in each dimension for a QR code of |version|. See
// table 1. (The colored squares in in QR codes are called tiles in the
// spec.)
const int size;
// Values taken from Table 9, page 38, for a QR code of version |version|.
const size_t group1_bytes;
const size_t group1_num_blocks;
const size_t group1_block_data_bytes;
const size_t group2_bytes;
const size_t group2_num_blocks;
const size_t group2_block_data_bytes;
const std::array<int, 3> alignment_locations;
// Total number of tiles for the QR code, size*size.
constexpr int total_size() const { return size * size; }
constexpr size_t total_bytes() const { return group1_bytes + group2_bytes; }
constexpr size_t group1_block_bytes() const {
return group1_bytes / group1_num_blocks;
}
constexpr size_t group1_block_ec_bytes() const {
return group1_block_bytes() - group1_block_data_bytes;
}
constexpr size_t group1_data_bytes() const {
return group1_block_data_bytes * group1_num_blocks;
}
constexpr size_t group2_block_bytes() const {
if (group2_num_blocks == 0)
return 0;
return group2_bytes / group2_num_blocks;
}
constexpr size_t group2_block_ec_bytes() const {
return group2_block_bytes() - group2_block_data_bytes;
}
constexpr size_t group2_data_bytes() const {
return group2_block_data_bytes * group2_num_blocks;
}
// input_bytes is the maximum number of data bytes, including framing bytes.
constexpr size_t input_bytes() const {
return group1_data_bytes() + group2_data_bytes();
}
private:
static constexpr bool CheckBlockGroupParameters(
const size_t bytes,
const size_t num_blocks,
const size_t block_data_bytes) {
if (num_blocks == 0 || bytes % num_blocks != 0 || block_data_bytes == 0 ||
block_data_bytes * num_blocks > bytes ||
(bytes - block_data_bytes * num_blocks) % num_blocks != 0) {
return false;
}
return true;
}
};
namespace {
constexpr QRVersionInfo version_infos[] = {
// See table 9 in the spec for the source of these numbers.
// 2-L
// 44 bytes in a single block.
{
2, // version
QRVersionInfo::ECC::kLow,
0, // encoded version (not included in this version)
25, // size (num tiles in each axis)
// Block group 1:
44, // Total bytes in group
1, // Number of blocks
34, // Data bytes per block
// Block group 2:
0,
0,
0,
// Alignment locations
{6, 18, 0},
},
// 5-M
// 134 bytes, as 2 blocks of 67.
{
5, // version
QRVersionInfo::ECC::kMedium,
0, // encoded version (not included in this version)
37, // size (num tiles in each axis)
// Block group 1:
134, // Total bytes in group
2, // Number of blocks
43, // Data bytes per block
// Block group 2:
0,
0,
0,
// Alignment locations
{6, 30, 0},
},
// 7-M
// 196 bytes, as 4 blocks of 49.
{
7, // version
QRVersionInfo::ECC::kMedium,
0b000111110010010100, // encoded version
45, // size (num tiles in each axis)
// Block group 1:
196, // Total bytes in group
4, // Number of blocks
31, // Data bytes per block
// Block group 2:
0,
0,
0,
// Alignment locations
{6, 22, 38},
},
// 9-M
// 292 bytes, as 3 blocks of 58 plus 2 blocks of 59.
{
9, // version
QRVersionInfo::ECC::kMedium,
0b001001101010011001, // encoded version
53, // size (num tiles in each axis)
// Block group 1:
174, // Total bytes in group
3, // Number of blocks
36, // Data bytes per block
// Block group 2:
118,
2,
37,
// Alignment locations
{6, 26, 46},
},
// 12-M
// 466 bytes, as 6 blocks of 58 and 2 blocks of 59.
{
12, // version
QRVersionInfo::ECC::kMedium,
0b001100011101100010, // encoded version
65, // size (num tiles in each axis)
// Block group 1:
348, // Total bytes in group
6, // Number of blocks
36, // Data bytes per block
// Block group 2:
118,
2,
37,
// Alignment locations
{6, 32, 58},
},
};
const QRVersionInfo* GetVersionForDataSize(size_t num_data_bytes,
absl::optional<int> min_version) {
for (const auto& version : version_infos) {
if (version.input_bytes() >= num_data_bytes &&
(!min_version || *min_version <= version.version)) {
return &version;
}
}
return nullptr;
}
// kMaxMask is the maximum masking function number. See table 10.
constexpr uint8_t kMaxMask = 7;
// The following functions implement the masks specified in table 10.
uint8_t MaskFunction0(int x, int y) {
return (x + y) % 2 == 0;
}
uint8_t MaskFunction1(int x, int y) {
return y % 2 == 0;
}
uint8_t MaskFunction2(int x, int y) {
return x % 3 == 0;
}
uint8_t MaskFunction3(int x, int y) {
return (x + y) % 3 == 0;
}
uint8_t MaskFunction4(int x, int y) {
return ((y / 2) + (x / 3)) % 2 == 0;
}
uint8_t MaskFunction5(int x, int y) {
return ((x * y) % 2) + ((x * y) % 3) == 0;
}
uint8_t MaskFunction6(int x, int y) {
return (((x * y) % 2) + ((x * y) % 3)) % 2 == 0;
}
uint8_t MaskFunction7(int x, int y) {
return (((x + y) % 2) + ((x * y) % 3)) % 2 == 0;
}
static uint8_t (*const kMaskFunctions[kMaxMask + 1])(int x, int y) = {
MaskFunction0, MaskFunction1, MaskFunction2, MaskFunction3,
MaskFunction4, MaskFunction5, MaskFunction6, MaskFunction7,
};
// FormatInformationForECC returns an array of eight format values (one for each
// mask) for the given ECC level.
base::span<const uint16_t, 8> FormatInformationForECC(QRVersionInfo::ECC ecc) {
// kFormatInformation is taken from table C.1 on page 80 and specifies the
// format value for each masking function. The first eight values assume ECC
// level 'L' and the rest assume ECC level 'M'.
static const uint16_t kFormatInformation[2 * (kMaxMask + 1)] = {
0x77c4, 0x72f3, 0x7daa, 0x789d, 0x662f, 0x6318, 0x6c41, 0x6976,
0x5412, 0x5125, 0x5e7c, 0x5b4b, 0x45f9, 0x40ce, 0x4f97, 0x4aa0,
};
switch (ecc) {
case QRVersionInfo::ECC::kLow:
return base::span<const uint16_t, 8>(kFormatInformation, 8);
case QRVersionInfo::ECC::kMedium:
return base::span<const uint16_t, 8>(&kFormatInformation[8], 8);
}
}
// kAlphanumValue maps from the beginning of the ASCII codespace to the value
// of a character in QR's alphanumeric mode, or 255 if the ASCII byte isn't
// represented. This is taken from table five of ISO 18004 (2015 edition).
static constexpr uint8_t kAlphanumValue[91] = {
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 36, 255, 255, 255, 37, 38, 255,
255, 255, 255, 39, 40, 255, 41, 42, 43, 0, 1, 2, 3,
4, 5, 6, 7, 8, 9, 44, 255, 255, 255, 255, 255, 255,
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,
};
// These assertions are spot checks of a few values from the table.
static_assert(kAlphanumValue[static_cast<int>('0')] == 0, "");
static_assert(kAlphanumValue[static_cast<int>('A')] == 10, "");
static_assert(kAlphanumValue[static_cast<int>('Z')] == 35, "");
static_assert(kAlphanumValue[static_cast<int>(' ')] == 36, "");
static_assert(kAlphanumValue[static_cast<int>(':')] == 44, "");
static_assert(kAlphanumValue[static_cast<int>('"')] == 255, "");
// LengthBits returns the number of bits used to encode the length of a given
// segment type. See table 3.
constexpr size_t LengthBits(QRCodeGenerator::VersionClass vclass,
QRCodeGenerator::SegmentType type) {
switch (type) {
case QRCodeGenerator::SegmentType::DIGIT:
switch (vclass) {
case QRCodeGenerator::VersionClass::SMALL:
return 10;
case QRCodeGenerator::VersionClass::LARGE:
return 12;
}
case QRCodeGenerator::SegmentType::ALPHANUM:
switch (vclass) {
case QRCodeGenerator::VersionClass::SMALL:
return 9;
case QRCodeGenerator::VersionClass::LARGE:
return 11;
}
case QRCodeGenerator::SegmentType::BINARY:
switch (vclass) {
case QRCodeGenerator::VersionClass::SMALL:
return 8;
case QRCodeGenerator::VersionClass::LARGE:
return 16;
}
}
}
// BitPacker appends bits to |output|, packing them from most-significant place
// to least significant.
class BitPacker {
public:
explicit BitPacker(std::vector<uint8_t>* output) : out_(output) {}
// AppendSegments adds the contents of |input| using the segmentation from
// |segments|.
void AppendSegments(const std::vector<QRCodeGenerator::Segment>& segments,
QRCodeGenerator::VersionClass vclass,
base::span<const uint8_t> input) {
size_t offset = 0;
for (const auto& segment : segments) {
base::span<const uint8_t> segment_data =
input.subspan(offset, segment.length);
switch (segment.type) {
case QRCodeGenerator::SegmentType::DIGIT:
AppendDigits(segment_data, vclass);
break;
case QRCodeGenerator::SegmentType::ALPHANUM:
AppendAlphanum(segment_data, vclass);
break;
case QRCodeGenerator::SegmentType::BINARY:
AppendBinary(segment_data, vclass);
break;
}
offset += segment.length;
}
}
void AppendTerminator() { AppendBitsFromByte(0, 4); }
private:
// ModeNumber returns the 4-bit identifier for the given mode. See table 2.
static constexpr uint8_t ModeNumber(QRCodeGenerator::SegmentType stype) {
switch (stype) {
case QRCodeGenerator::SegmentType::DIGIT:
return 1;
case QRCodeGenerator::SegmentType::ALPHANUM:
return 2;
case QRCodeGenerator::SegmentType::BINARY:
return 4;
}
}
// AppendBitsFromByte appends |num_bits| (which must be <= 8) from |v|.
void AppendBitsFromByte(uint8_t v, int num_bits) {
DCHECK_LE(num_bits, 8);
v <<= 8 - num_bits;
if (bits_remaining_in_final_byte_ > 0) {
out_->back() |= v >> (8 - bits_remaining_in_final_byte_);
}
bits_remaining_in_final_byte_ -= num_bits;
if (bits_remaining_in_final_byte_ < 0) {
out_->push_back(v << (num_bits + bits_remaining_in_final_byte_));
bits_remaining_in_final_byte_ += 8;
}
}
// AppendBits appends |num_bits| (which must be <= 16) from |v|.
void AppendBits(const uint16_t v, const int num_bits) {
DCHECK_LE(num_bits, 16);
DCHECK_LT(v, 1u << num_bits);
if (num_bits <= 8) {
AppendBitsFromByte(static_cast<uint8_t>(v), num_bits);
return;
}
const int n = num_bits - 8;
AppendBitsFromByte(static_cast<uint8_t>(v >> n), 8);
AppendBitsFromByte(static_cast<uint8_t>(v & ((1u << n) - 1)), n);
}
static unsigned DigitValue(uint8_t digit) {
DCHECK('0' <= digit && digit <= '9');
return digit - '0';
}
void AppendDigits(base::span<const uint8_t> in,
QRCodeGenerator::VersionClass vclass) {
const auto stype = QRCodeGenerator::SegmentType::DIGIT;
AppendBitsFromByte(ModeNumber(stype), 4);
AppendBits(in.size(), LengthBits(vclass, stype));
while (in.size() >= 3) {
// Triples of digits are encoded as 10-bit values.
AppendBits(
DigitValue(in[0]) * 100 + DigitValue(in[1]) * 10 + DigitValue(in[2]),
10);
in = in.subspan(3);
}
// Any remaining digits are encoded using the minimal number of bits.
if (in.size() == 2) {
AppendBitsFromByte(DigitValue(in[0]) * 10 + DigitValue(in[1]), 7);
} else if (in.size() == 1) {
AppendBitsFromByte(DigitValue(in[0]), 4);
}
}
void AppendAlphanum(base::span<const uint8_t> in,
QRCodeGenerator::VersionClass vclass) {
const auto stype = QRCodeGenerator::SegmentType::ALPHANUM;
AppendBitsFromByte(ModeNumber(stype), 4);
AppendBits(in.size(), LengthBits(vclass, stype));
while (in.size() >= 2) {
DCHECK(in[0] < sizeof(kAlphanumValue) && kAlphanumValue[in[0]] != 0xff)
<< in[0];
DCHECK(in[1] < sizeof(kAlphanumValue) && kAlphanumValue[in[1]] != 0xff)
<< in[1];
AppendBits(kAlphanumValue[in[0]] * 45 + kAlphanumValue[in[1]], 11);
in = in.subspan(2);
}
if (!in.empty()) {
AppendBitsFromByte(kAlphanumValue[in[0]], 6);
}
}
void AppendBinary(base::span<const uint8_t> in,
QRCodeGenerator::VersionClass vclass) {
const auto stype = QRCodeGenerator::SegmentType::BINARY;
AppendBitsFromByte(ModeNumber(stype), 4);
AppendBits(in.size(), LengthBits(vclass, stype));
for (const uint8_t b : in) {
AppendBitsFromByte(b, 8);
}
}
const raw_ptr<std::vector<uint8_t>> out_;
int bits_remaining_in_final_byte_ = 0;
};
// VersionClassForVersion translates a QR code version number into whether it
// uses small or large lengths.
QRCodeGenerator::VersionClass VersionClassForVersion(int version) {
return version <= kMaxVersionWithSmallLengths
? QRCodeGenerator::VersionClass::SMALL
: QRCodeGenerator::VersionClass::LARGE;
}
// SegmentBits returns the number of bits needed to encode the given segment.
size_t SegmentBits(QRCodeGenerator::VersionClass vclass,
const QRCodeGenerator::Segment& segment) {
static const uint8_t kDigitTrailingBits[3] = {0, 4, 7};
const size_t header_bits = 4 + LengthBits(vclass, segment.type);
switch (segment.type) {
case QRCodeGenerator::SegmentType::DIGIT:
return header_bits + (10 * (segment.length / 3)) +
kDigitTrailingBits[segment.length % 3];
case QRCodeGenerator::SegmentType::ALPHANUM:
return header_bits + (11 * (segment.length / 2)) +
(segment.length & 1 ? 6 : 0);
case QRCodeGenerator::SegmentType::BINARY:
return header_bits + 8 * segment.length;
}
}
size_t SegmentBits(QRCodeGenerator::VersionClass vclass,
base::span<const QRCodeGenerator::Segment> segments) {
size_t sum = 0;
for (const auto& segment : segments) {
sum += SegmentBits(vclass, segment);
}
return sum;
}
// SegmentSpanLength returns the total length of |segments|.
size_t SegmentSpanLength(base::span<const QRCodeGenerator::Segment> segments) {
size_t sum = 0;
for (const auto& segment : segments) {
sum += segment.length;
}
return sum;
}
} // namespace
QRCodeGenerator::QRCodeGenerator() = default;
QRCodeGenerator::~QRCodeGenerator() = default;
QRCodeGenerator::GeneratedCode::GeneratedCode() = default;
QRCodeGenerator::GeneratedCode::GeneratedCode(
QRCodeGenerator::GeneratedCode&&) = default;
QRCodeGenerator::GeneratedCode::~GeneratedCode() = default;
absl::optional<QRCodeGenerator::GeneratedCode> QRCodeGenerator::Generate(
base::span<const uint8_t> in,
absl::optional<int> min_version,
absl::optional<uint8_t> mask) {
CHECK(!mask || *mask <= kMaxMask);
std::vector<Segment> segments;
const QRVersionInfo* version_info = nullptr;
// First assume that we can use |SMALL| QR codes. If the input is too large
// for that than recalculate for |LARGE| codes.
for (VersionClass version_class :
{VersionClass::SMALL, VersionClass::LARGE}) {
segments = SegmentInput(version_class, in);
DCHECK(IsValidSegmentation(segments, in));
const size_t length_bits =
SegmentBits(version_class, segments) + 4 /* for the terminator */;
const size_t length_bytes = (length_bits + 7) / 8;
version_info = GetVersionForDataSize(length_bytes, min_version);
if (!version_info) {
return absl::nullopt;
}
if (VersionClassForVersion(version_info->version) == version_class) {
break;
}
}
const VersionClass version_class =
VersionClassForVersion(version_info->version);
if (version_info != version_info_) {
version_info_ = version_info;
d_.resize(version_info_->total_size());
}
// Previous data and "set" bits must be cleared.
memset(&d_[0], 0, version_info_->total_size());
const size_t framed_input_size =
version_info_->group1_data_bytes() + version_info_->group2_data_bytes();
std::vector<uint8_t> prefixed_data;
prefixed_data.reserve(framed_input_size);
BitPacker packer(&prefixed_data);
packer.AppendSegments(segments, version_class, in);
packer.AppendTerminator();
// The remainder of the space is filled with alternatining 0xec and 0x11
// bytes, as per the standard. (Although the contents of this padding do not,
// in practice, matter.)
bool padding_phase = false;
while (prefixed_data.size() < framed_input_size) {
prefixed_data.push_back(padding_phase ? 0x11 : 0xec);
padding_phase = !padding_phase;
}
PutVerticalTiming(6);
PutHorizontalTiming(6);
PutFinder(3, 3);
PutFinder(3, version_info_->size - 4);
PutFinder(version_info_->size - 4, 3);
const auto& alignment_locations = version_info_->alignment_locations;
size_t num_alignment_locations = 0;
for (size_t i = 0; i < alignment_locations.size(); i++) {
if (alignment_locations[i] == 0) {
break;
}
num_alignment_locations++;
}
for (size_t i = 0; i < num_alignment_locations; i++) {
for (size_t j = 0; j < num_alignment_locations; j++) {
// Three of the corners already have finder symbols.
if ((i == 0 && j == 0) || (i == 0 && j == num_alignment_locations - 1) ||
(i == num_alignment_locations - 1 && j == 0)) {
continue;
}
PutAlignment(alignment_locations[i], alignment_locations[j]);
}
}
if (version_info_->encoded_version != 0) {
PutVersionBlocks(version_info_->encoded_version);
}
// Each block of input data is expanded with error correcting
// information and then interleaved.
// Error Correction for Group 1, present for all versions.
const size_t group1_num_blocks = version_info_->group1_num_blocks;
const size_t group1_block_bytes = version_info_->group1_block_bytes();
const size_t group1_block_data_bytes = version_info_->group1_block_data_bytes;
const size_t group1_block_ec_bytes = version_info_->group1_block_ec_bytes();
std::vector<std::vector<uint8_t>> expanded_blocks(group1_num_blocks);
for (size_t i = 0; i < group1_num_blocks; i++) {
expanded_blocks[i].resize(group1_block_bytes);
AddErrorCorrection(
expanded_blocks[i],
base::span<const uint8_t>(&prefixed_data[group1_block_data_bytes * i],
group1_block_data_bytes),
group1_block_bytes, group1_block_ec_bytes);
}
// Error Correction for Group 2, present for some versions.
// Factor out the number of bytes written by the prior group.
const size_t group_data_offset = version_info_->group1_data_bytes();
const size_t group2_num_blocks = version_info_->group2_num_blocks;
const size_t group2_block_bytes = version_info_->group2_block_bytes();
const size_t group2_block_data_bytes = version_info_->group2_block_data_bytes;
const size_t group2_block_ec_bytes = version_info_->group2_block_ec_bytes();
std::vector<std::vector<uint8_t>> expanded_blocks_2;
if (group2_num_blocks > 0) {
expanded_blocks_2.resize(group2_num_blocks);
for (size_t i = 0; i < group2_num_blocks; i++) {
expanded_blocks_2[i].resize(group2_block_bytes);
AddErrorCorrection(
expanded_blocks_2[i],
base::span<const uint8_t>(
&prefixed_data[group_data_offset + group2_block_data_bytes * i],
group2_block_data_bytes),
group2_block_bytes, group2_block_ec_bytes);
}
}
const size_t total_bytes = version_info_->total_bytes();
uint8_t interleaved_data[total_bytes];
CHECK(total_bytes == group1_block_bytes * group1_num_blocks +
group2_block_bytes * group2_num_blocks)
<< "internal error";
size_t k = 0;
// Interleave data from all blocks. All non-ECC data is written before any ECC
// data. The group two blocks, if any, will be longer than the group one
// blocks. Once group one is exhausted then the interleave considers only
// group two.
DCHECK(group2_num_blocks == 0 || version_info_->group2_block_data_bytes >
version_info_->group1_block_data_bytes);
size_t j = 0;
for (; j < version_info_->group1_block_data_bytes; j++) {
for (size_t i = 0; i < group1_num_blocks; i++) {
interleaved_data[k++] = expanded_blocks[i][j];
}
for (size_t i = 0; i < group2_num_blocks; i++) {
interleaved_data[k++] = expanded_blocks_2[i][j];
}
}
if (group2_num_blocks > 0) {
for (; j < version_info_->group2_block_data_bytes; j++) {
for (size_t i = 0; i < group2_num_blocks; i++) {
interleaved_data[k++] = expanded_blocks_2[i][j];
}
}
}
// The number of ECC bytes in each group is the same so the interleave
// considers them uniformly.
DCHECK(version_info_->group2_num_blocks == 0 ||
version_info_->group2_block_ec_bytes() ==
version_info_->group1_block_ec_bytes());
for (j = 0; j < version_info_->group1_block_ec_bytes(); j++) {
for (size_t i = 0; i < group1_num_blocks; i++) {
interleaved_data[k++] =
expanded_blocks[i][version_info_->group1_block_data_bytes + j];
}
for (size_t i = 0; i < group2_num_blocks; i++) {
interleaved_data[k++] =
expanded_blocks_2[i][version_info_->group2_block_data_bytes + j];
}
}
DCHECK_EQ(k, total_bytes);
uint8_t best_mask = mask.value_or(0);
absl::optional<unsigned> lowest_penalty;
// If |mask| was not specified, then evaluate each masking function to find
// the one with the lowest penalty score.
for (uint8_t mask_num = 0; !mask && mask_num <= kMaxMask; mask_num++) {
// FormatInformationForECC returns an array of encoded formatting words for
// the QR code that this code generates. See tables 10 and 12. For example:
// 00 011
// --|---
// error correction M | Mask pattern 3
//
// It's translated into a 15-bit value using the table on page 80.
PutFormatBits(FormatInformationForECC(version_info_->ecc)[mask_num]);
PutBits(interleaved_data, sizeof(interleaved_data),
kMaskFunctions[mask_num]);
const unsigned penalty = CountPenaltyPoints();
if (!lowest_penalty || *lowest_penalty > penalty) {
lowest_penalty = penalty;
best_mask = mask_num;
}
}
// Repaint with the best mask function.
PutFormatBits(FormatInformationForECC(version_info_->ecc)[best_mask]);
PutBits(interleaved_data, sizeof(interleaved_data),
kMaskFunctions[best_mask]);
GeneratedCode code;
code.data = base::span<uint8_t>(&d_[0], version_info_->total_size());
code.qr_size = version_info_->size;
return code;
}
// PutFinder paints a finder symbol at the given coordinates.
void QRCodeGenerator::PutFinder(int x, int y) {
DCHECK_GE(x, 3);
DCHECK_GE(y, 3);
fillAt(x - 3, y - 3, 7, 0b11);
fillAt(x - 2, y - 2, 5, 0b10);
fillAt(x - 2, y + 2, 5, 0b10);
fillAt(x - 3, y + 3, 7, 0b11);
static constexpr uint8_t kLine[7] = {0b11, 0b10, 0b11, 0b11,
0b11, 0b10, 0b11};
copyTo(x - 3, y - 1, kLine, sizeof(kLine));
copyTo(x - 3, y, kLine, sizeof(kLine));
copyTo(x - 3, y + 1, kLine, sizeof(kLine));
at(x - 3, y - 2) = 0b11;
at(x + 3, y - 2) = 0b11;
at(x - 3, y + 2) = 0b11;
at(x + 3, y + 2) = 0b11;
for (int xx = x - 4; xx <= x + 4; xx++) {
clipped(xx, y - 4) = 0b10;
clipped(xx, y + 4) = 0b10;
}
for (int yy = y - 3; yy <= y + 3; yy++) {
clipped(x - 4, yy) = 0b10;
clipped(x + 4, yy) = 0b10;
}
}
// PutAlignment paints an alignment symbol centered at the given coordinates.
void QRCodeGenerator::PutAlignment(int x, int y) {
fillAt(x - 2, y - 2, 5, 0b11);
fillAt(x - 2, y + 2, 5, 0b11);
static constexpr uint8_t kLine[5] = {0b11, 0b10, 0b10, 0b10, 0b11};
copyTo(x - 2, y - 1, kLine, sizeof(kLine));
copyTo(x - 2, y, kLine, sizeof(kLine));
copyTo(x - 2, y + 1, kLine, sizeof(kLine));
at(x, y) = 0b11;
}
// PutVerticalTiming paints the vertical timing signal.
void QRCodeGenerator::PutVerticalTiming(int x) {
for (int y = 0; y < version_info_->size; y++) {
at(x, y) = 0b10 | (1 ^ (y & 1));
}
}
// PutVerticalTiming paints the horizontal timing signal.
void QRCodeGenerator::PutHorizontalTiming(int y) {
for (int x = 0; x < version_info_->size; x++) {
at(x, y) = 0b10 | (1 ^ (x & 1));
}
}
// PutFormatBits paints the 15-bit, pre-encoded format metadata. See page 56
// for the location of the format bits.
void QRCodeGenerator::PutFormatBits(const uint16_t format) {
// kRun1 is the location of the initial format bits, where the upper nibble
// is the x coordinate and the lower the y.
static constexpr uint8_t kRun1[15] = {
0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x87, 0x88,
0x78, 0x58, 0x48, 0x38, 0x28, 0x18, 0x08,
};
uint16_t v = format;
for (size_t i = 0; i < sizeof(kRun1); i++) {
const uint8_t location = kRun1[i];
at(location >> 4, location & 15) = 0b10 | (v & 1);
v >>= 1;
}
const int size = version_info_->size;
v = format;
for (int x = size - 1; x >= size - 1 - 7; x--) {
at(x, 8) = 0b10 | (v & 1);
v >>= 1;
}
at(8, size - 1 - 7) = 0b11;
for (int y = size - 1 - 6; y <= size - 1; y++) {
at(8, y) = 0b10 | (v & 1);
v >>= 1;
}
}
void QRCodeGenerator::PutVersionBlocks(uint32_t encoded_version) {
// Version 7 and larger require 18-bit version information taking the form
// of 6x3 rectangles above the bottom-left locator and to the left of the
// top-right locator.
const int size = version_info_->size;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 3; j++) {
// Bottom-left rectangle is top-to-bottom, left-to-right
at(i, size - 8 - 3 + j) = 0b10 | (encoded_version & 1);
// Top-right rectangle is left-to-right, top-to-bottom
at(size - 8 - 3 + j, i) = 0b10 | (encoded_version & 1);
// Shift to consider the next bit.
encoded_version >>= 1;
}
}
}
// PutBits writes the given data into the QR code in correct order, avoiding
// structural elements that must have already been painted. See section 7.7.3
// about the placement algorithm.
void QRCodeGenerator::PutBits(const uint8_t* data,
size_t data_len,
uint8_t (*mask_func)(int, int)) {
// BitStream vends bits from |data| on demand, in the order that QR codes
// expect them.
class BitStream {
public:
BitStream(const uint8_t* data, size_t data_len)
: data_(data), data_len_(data_len), i_(0), bits_in_current_byte_(0) {}
uint8_t Next() {
if (bits_in_current_byte_ == 0) {
if (i_ >= data_len_) {
byte_ = 0;
} else {
byte_ = data_[i_++];
}
bits_in_current_byte_ = 8;
}
const uint8_t ret = byte_ >> 7;
byte_ <<= 1;
bits_in_current_byte_--;
return ret;
}
private:
const uint8_t* const data_;
const size_t data_len_;
size_t i_;
unsigned bits_in_current_byte_;
uint8_t byte_;
};
BitStream stream(data, data_len);
bool going_up = true;
int x = version_info_->size - 1;
int y = version_info_->size - 1;
for (;;) {
uint8_t& right = at(x, y);
// Test the current value in the QR code to avoid painting over any
// existing structural elements.
if ((right & 2) == 0) {
right = stream.Next() ^ mask_func(x, y);
}
uint8_t& left = at(x - 1, y);
if ((left & 2) == 0) {
left = stream.Next() ^ mask_func(x - 1, y);
}
if ((going_up && y == 0) || (!going_up && y == version_info_->size - 1)) {
if (x == 1) {
break;
}
x -= 2;
// The vertical timing column is skipped over.
if (x == 6) {
x--;
}
going_up = !going_up;
} else {
if (going_up) {
y--;
} else {
y++;
}
}
}
}
// at returns a reference to the given element of |d_|.
uint8_t& QRCodeGenerator::at(int x, int y) {
DCHECK_LE(0, x);
DCHECK_LT(x, version_info_->size);
DCHECK_LE(0, y);
DCHECK_LT(y, version_info_->size);
return d_[version_info_->size * y + x];
}
// fillAt sets the |len| elements at (x, y) to |value|.
void QRCodeGenerator::fillAt(int x, int y, size_t len, uint8_t value) {
DCHECK_LE(0, x);
DCHECK_LE(static_cast<int>(x + len), version_info_->size);
DCHECK_LE(0, y);
DCHECK_LT(y, version_info_->size);
memset(&d_[version_info_->size * y + x], value, len);
}
// copyTo copies |len| elements from |data| to the elements at (x, y).
void QRCodeGenerator::copyTo(int x, int y, const uint8_t* data, size_t len) {
DCHECK_LE(0, x);
DCHECK_LE(static_cast<int>(x + len), version_info_->size);
DCHECK_LE(0, y);
DCHECK_LT(y, version_info_->size);
memcpy(&d_[version_info_->size * y + x], data, len);
}
// clipped returns a reference to the given element of |d_|, or to
// |clip_dump_| if the coordinates are out of bounds.
uint8_t& QRCodeGenerator::clipped(int x, int y) {
if (0 <= x && x < version_info_->size && 0 <= y && y < version_info_->size) {
return d_[version_info_->size * y + x];
}
return clip_dump_;
}
// GF28Mul returns the product of |a| and |b| (which must be field elements,
// i.e. < 256) in the field GF(2^8) mod x^8 + x^4 + x^3 + x^2 + 1.
// static
uint8_t QRCodeGenerator::GF28Mul(uint16_t a, uint16_t b) {
uint16_t acc = 0;
// Perform 8-bit, carry-less multiplication of |a| and |b|.
for (int i = 0; i < 8; i++) {
const uint16_t mask = ~((b & 1) - 1);
acc ^= a & mask;
b >>= 1;
a <<= 1;
}
// Add multiples of the modulus to eliminate all bits past a byte. Note that
// the bits in |modulus| have a one where there's a non-zero power of |x| in
// the field modulus.
uint16_t modulus = 0b100011101 << 7;
for (int i = 15; i >= 8; i--) {
const uint16_t mask = ~((acc >> i) - 1);
acc ^= modulus & mask;
modulus >>= 1;
}
return acc;
}
// AddErrorCorrection writes the Reed-Solomon expanded version of |in| to
// |out|.
// |out| should have length block_bytes for the code's version.
// |in| should have length block_data_bytes for the code's version.
void QRCodeGenerator::AddErrorCorrection(base::span<uint8_t> out,
base::span<const uint8_t> in,
size_t block_bytes,
size_t block_ec_bytes) {
// kGenerator is the product of (z - x^i) for 0 <= i < |block_ec_bytes|,
// where x is the term of GF(2^8) and z is the term of a polynomial ring
// over GF(2^8). It's generated with the following Sage script:
//
// F.<x> = GF(2^8, modulus = x^8 + x^4 + x^3 + x^2 + 1)
// R.<z> = PolynomialRing(F, 'z')
//
// def toByte(p):
// return sum([(1<<i) * int(term) for (i, term) in
// enumerate(p.polynomial())])
//
// def generatorPoly(n):
// acc = (z - F(1))
// for i in range(1,n):
// acc *= (z - x^i)
// return acc
//
// gen = generatorPoly(24)
// coeffs = list(gen)
// gen = [toByte(x) for x in coeffs]
// print 'uint8_t kGenerator[' + str(len(gen)) + '] = {' + str(gen) + '}'
// Used for 2-L: 10 error correction codewords per block.
static const uint8_t kGenerator10[] = {
193, 157, 113, 95, 94, 199, 111, 159, 194, 216, 1,
};
// Used for 7-M: 18 error correction codewords per block.
static const uint8_t kGenerator18[] = {
146, 217, 67, 32, 75, 173, 82, 73, 220, 240,
215, 199, 175, 149, 113, 183, 251, 239, 1,
};
// Used for 9-M and 12-M; 22 error correction codewords per block.
static const uint8_t kGenerator22[] = {
245, 145, 26, 230, 218, 86, 253, 67, 123, 29, 137, 28,
40, 69, 189, 19, 244, 182, 176, 131, 179, 89, 1,
};
// Used for 5-M, 24 error correction codewords per block.
static const uint8_t kGenerator24[] = {
117, 144, 217, 127, 247, 237, 1, 206, 43, 61, 72, 130, 73,
229, 150, 115, 102, 216, 237, 178, 70, 169, 118, 122, 1,
};
const uint8_t* generator = nullptr;
switch (block_ec_bytes) {
case 10:
generator = kGenerator10;
break;
case 18:
generator = kGenerator18;
break;
case 22:
generator = kGenerator22;
break;
case 24:
generator = kGenerator24;
break;
default: {
NOTREACHED() << "Unsupported Generator Polynomial for block_ec_bytes: "
<< block_ec_bytes;
return;
}
}
// The error-correction bytes are the remainder of dividing |in| * x^k by
// |kGenerator|, where |k| is the number of EC codewords. Polynomials here
// are represented in little-endian order, i.e. the value at index |i| is
// the coefficient of z^i.
// Multiplication of |in| by x^k thus just involves moving it up.
uint8_t remainder[block_bytes];
DCHECK_LE(block_ec_bytes, block_bytes);
memset(remainder, 0, block_ec_bytes);
size_t block_data_bytes = block_bytes - block_ec_bytes;
// Reed-Solomon input is backwards. See section 7.5.2.
for (size_t i = 0; i < block_data_bytes; i++) {
remainder[block_ec_bytes + i] = in[block_data_bytes - 1 - i];
}
// Progressively eliminate the leading coefficient by subtracting some
// multiple of |generator| until we have a value smaller than |generator|.
for (size_t i = block_bytes - 1; i >= block_ec_bytes; i--) {
// The leading coefficient of |generator| is 1, so the multiple to
// subtract to eliminate the leading term of |remainder| is the value of
// that leading term. The polynomial ring is characteristic two, so
// subtraction is the same as addition, which is XOR.
for (size_t j = 0; j < block_ec_bytes; j++) {
remainder[i - block_ec_bytes + j] ^= GF28Mul(generator[j], remainder[i]);
}
}
memmove(&out[0], &in[0], block_data_bytes);
// Remove the Reed-Solomon remainder again to match QR's convention.
for (size_t i = 0; i < block_ec_bytes; i++) {
out[block_data_bytes + i] = remainder[block_ec_bytes - 1 - i];
}
}
unsigned QRCodeGenerator::CountPenaltyPoints() const {
const int size = version_info_->size;
unsigned penalty = 0;
// The spec penalises the pattern X.XXX.X with four unpainted tiles to
// the left or right. These are "finder-like" patterns. To catch them, a
// sliding window of 11 tiles is used.
static const unsigned k11Bits = 0x7ff;
static const unsigned kFinderLeft = 0b00001011101;
static const unsigned kFinderRight = 0b10111010000;
// Count:
// * Horizontal runs of the same color, at least five tiles in a row.
// * The number of horizontal finder-like patterns.
// * Total number of painted tiles, which is used later.
unsigned current_run_length;
int current_color;
unsigned total_painted_tiles = 0;
unsigned window = 0;
size_t i = 0;
for (int y = 0; y < size; y++) {
current_color = d_[i++] & 1;
current_run_length = 0;
window = current_color;
total_painted_tiles += current_color;
for (int x = 1; x < size; x++) {
const int color = d_[i++] & 1;
window = k11Bits & ((window << 1) | color);
if (window == kFinderLeft || window == kFinderRight) {
penalty += 40;
}
total_painted_tiles += color;
if (color == current_color) {
current_run_length++;
continue;
}
if (current_run_length >= 5) {
penalty += current_run_length - 2;
}
current_run_length = 0;
current_color = color;
}
if (current_run_length >= 5) {
penalty += current_run_length - 2;
}
window = k11Bits & (window << 4);
if (window == kFinderRight) {
penalty += 40;
}
}
DCHECK_EQ(i, static_cast<size_t>(size * size));
// Count:
// * Vertical runs of the same color, at least five tiles in a row.
// * The number of vertical finder-like patterns.
for (int x = 0; x < size; x++) {
i = x;
current_run_length = 0;
current_color = d_[i] & 1;
i += size;
window = current_color;
for (int y = 1; y < size; y++, i += size) {
const int color = d_[i] & 1;
window = k11Bits & ((window << 1) | color);
if (window == kFinderLeft || window == kFinderRight) {
penalty += 40;
}
if (color == current_color) {
current_run_length++;
continue;
}
if (current_run_length >= 5) {
penalty += current_run_length - 2;
}
current_run_length = 0;
current_color = color;
}
if (current_run_length >= 5) {
penalty += current_run_length - 2;
}
window = k11Bits & (window << 4);
if (window == kFinderRight) {
penalty += 40;
}
}
DCHECK_EQ(i, static_cast<size_t>(size * size + size - 1));
// Count 2x2 blocks of the same color.
i = 0;
for (int y = 0; y < size - 1; y++) {
for (int x = 0; x < size - 1; x++) {
const int color = d_[i++] & 1;
if ((d_[i + 1] & 1) == color && (d_[i + size] & 1) == color &&
(d_[i + size + 1] & 1) == color) {
penalty += 3;
}
}
}
// Each deviation of 5% away from 50%-painted costs five points.
DCHECK_LE(total_painted_tiles, static_cast<unsigned>(size) * size);
double painted_fraction = static_cast<double>(total_painted_tiles) /
(static_cast<double>(size) * size);
if (painted_fraction < 0.5) {
painted_fraction = 1.0 - painted_fraction;
}
const double deviation = (painted_fraction - 0.5) / 0.05;
penalty += 5 * static_cast<unsigned>(floor(deviation));
return penalty;
}
// Segmentation
//
// The data in a QR code is a series of "segments". Each segment has a type,
// a length, and encoding rules. The set of bytes that can be encoded varies
// between segment types. A DIGIT segment can only encode '0'<=x<='9' but it
// encodes them more efficiently than ASCII.
//
// For the segment types that we support here, there is a super-set relation:
// BINARY can encode everything that ALPHANUM can, which can encode everything
// that DIGIT can.
//
// To perform segmentation we first need a function that returns the minimum
// segment type for a given byte. "Minimum" here is defined using the super-set
// relation, so DIGIT < ALPHANUM < BINARY.
// static
QRCodeGenerator::SegmentType QRCodeGenerator::ClassifyByte(uint8_t byte) {
if ('0' <= byte && byte <= '9') {
return QRCodeGenerator::SegmentType::DIGIT;
} else if (byte < sizeof(kAlphanumValue) && kAlphanumValue[byte] != 0xff) {
return QRCodeGenerator::SegmentType::ALPHANUM;
} else {
return QRCodeGenerator::SegmentType::BINARY;
}
}
// A "valid" segmentation is one where:
//
// 1. The sum of the segment lengths is equal to the input length.
// 2. No byte of input is in a segment that cannot encode it.
// static
bool QRCodeGenerator::IsValidSegmentation(const std::vector<Segment>& segments,
base::span<const uint8_t> input) {
size_t offset = 0;
for (const auto& segment : segments) {
for (size_t i = offset; i < offset + segment.length; i++) {
const auto min_type = ClassifyByte(input[i]);
if (static_cast<int>(segment.type) < static_cast<int>(min_type)) {
return false;
}
}
offset += segment.length;
}
return offset == input.size();
}
// Segmentation is the problem of finding a valid segmentation for an input and,
// preferably, one that is optimal. Segments have headers that take space so,
// for example, it's not optimal to use a DIGIT segment to encode a single digit
// in a span of otherwise BINARY data.
//
// To start, we define an additional invariant that we will always maintain:
//
// 3. No two consecutive segments have the same type.
//
// (I.e. consecutive segments with the same type must immediately be merged
// together.)
bool QRCodeGenerator::NoSuperfluousSegments(
const std::vector<Segment>& segments) {
for (size_t i = 1; i < segments.size(); i++) {
if (segments[i - 1].type == segments[i].type) {
return false;
}
}
return true;
}
// Given a classification for each byte of an input, the "initial segmentation"
// is defined as a segmentation that puts each byte of the input into a segment
// of minimal type.
// static
std::vector<QRCodeGenerator::Segment> QRCodeGenerator::InitialSegmentation(
base::span<const uint8_t> input) {
std::vector<Segment> segments;
absl::optional<Segment> current;
for (const uint8_t b : input) {
const SegmentType type = ClassifyByte(b);
if (current.has_value() && type == current->type) {
current->length++;
} else {
if (current.has_value()) {
segments.push_back(*current);
} else {
current.emplace();
}
current->type = type;
current->length = 1;
}
}
if (current.has_value()) {
segments.push_back(*current);
}
DCHECK(IsValidSegmentation(segments, input));
DCHECK(NoSuperfluousSegments(segments));
return segments;
}
// In order to improve on the initial segmentation we need the ability to
// merge segments. Spans of segments are specified by (start, end) indexes where
// start is the index of the first segment of the span and end is the index of
// the last.
//
// |MergeSegments| replaces a span of segments with a given segment and returns
// the index of the replacement.
// static
size_t QRCodeGenerator::MergeSegments(std::vector<Segment>* segments,
size_t start,
size_t end,
Segment replacement) {
DCHECK_LT(start, segments->size());
DCHECK_LT(end, segments->size());
DCHECK_LT(start, end);
segments->at(start) = replacement;
segments->erase(segments->begin() + start + 1, segments->begin() + end + 1);
return start;
}
// Segments should only be merged when the replacement is smaller than the
// separate segments. |MaybeMerge| will replace a span of segments with a
// single segment of |merged_type| if the merged form is equal or smaller than
// the span. It returns the index of the right-edge of the span, whether merged
// or not.
//
// Callers of this function must ensure that merging a span doesn't violate
// invariant three.
// static
size_t QRCodeGenerator::MaybeMerge(VersionClass vclass,
std::vector<Segment>* segments,
size_t start,
size_t end,
SegmentType merged_type) {
auto s = base::span<const Segment>(&segments->at(start), (end - start) + 1);
const size_t unmerged_cost = SegmentBits(vclass, s);
const Segment merged = {
.type = merged_type,
.length = SegmentSpanLength(s),
};
const size_t merged_cost = SegmentBits(vclass, merged);
if (merged_cost <= unmerged_cost) {
return MergeSegments(segments, start, end, merged);
}
return end;
}
// If there were only two classes then there would be an obvious solution for
// merging: for each transition to the smaller class, consider whether the
// overhead of the segment was worth the more compact encoding and promote the
// segment if not.
//
// There are three classes here but we deal with that by using the two-class
// solution twice. Runs of DIGIT and ALPHANUM segments are considered to be
// subproblems and solved using the two-class pattern. Then those runs are
// considered to be a single segment for the purpose of applying the two-class
// solution again for BINARY and DIGIT/ALPHANUM runs.
//
// It is not clear that is gives an optimal segmentation, but it does a pretty
// good job in linear time. ("Sort of" linear: since the segments are kept in
// a vector and moved down when merging, it's probably quadratic. But I
// suspect the fixed overhead of a linked list would make it slower in practice
// for the sizes of problems that we care about.)
//
// Since the size of a segment is monotonic with number of input bytes
// contained, and the edge cases (where an additional input element can cost
// different numbers of bits depending on the length mod 3 or 2) differ only by
// one bit, I _suspect_ that this algorithm might be optimal. It would be a fun
// formal verification problem had I a couple of months to spare. But I don't,
// so pressing on:
//
// First we define a function, |SegmentDigitAlphaSpan|, which performs the
// two-class solution on a span of segments that are all DIGIT or ALPHANUM
// segments.
// static
size_t QRCodeGenerator::SegmentDigitAlphaSpan(VersionClass vclass,
std::vector<Segment>* segments,
size_t start,
size_t end) {
// |start| and |end| are the indexes of the first and last segment of the
// span.
DCHECK_LE(start, end);
for (size_t i = start; i <= end; i++) {
DCHECK(segments->at(i).type == SegmentType::DIGIT ||
segments->at(i).type == SegmentType::ALPHANUM);
}
// A single segment span is trivially optimal.
if (end - start == 0) {
return end;
}
// Merging segments invalidates |end| (but not |start|). The distance from the
// end of |segments| to |end| is constant, however, and used to fix up |end|
// after merging.
const size_t distance_from_vector_end = segments->size() - end;
for (size_t i = start + 1; i <= end; i++) {
// Find an ALPHANUM segment.
if (segments->at(i).type != SegmentType::ALPHANUM) {
continue;
}
// |segments[i]| is ALPHANUM and, because of invariant three, |i-1| must
// be DIGIT.
DCHECK_EQ(segments->at(i - 1).type, SegmentType::DIGIT);
DCHECK_EQ(segments->at(i).type, SegmentType::ALPHANUM);
// If there's another ALPHANUM segment at |i-2| then we must include it in
// any merge decisions in order to maintain invariant three. Thus figure
// out if segment |i-2| exists.
const bool have_left = i >= 2 && i - 2 >= start;
if (!have_left) {
i = MaybeMerge(vclass, segments, i - 1, i, SegmentType::ALPHANUM);
} else {
DCHECK_EQ(segments->at(i - 2).type, SegmentType::ALPHANUM);
i = MaybeMerge(vclass, segments, i - 2, i, SegmentType::ALPHANUM);
}
end = segments->size() - distance_from_vector_end;
}
if (segments->at(end).type == SegmentType::DIGIT) {
// If the last segment was DIGIT then it won't have been considered for
// merging. So do that.
DCHECK_EQ(segments->at(end - 1).type, SegmentType::ALPHANUM);
DCHECK_EQ(segments->at(end).type, SegmentType::DIGIT);
return MaybeMerge(vclass, segments, end - 1, end, SegmentType::ALPHANUM);
}
return end;
}
// Having seen the two-class solution for the subproblem of DIGIT/ALPHANUM
// segments we use the same pattern to cover BINARY segments too. Spans of
// DIGIT/ALPHANUM segments are found and optimised using the previous function.
// Then those spans are treated like a single segment for the purposes of
// merging with BINARY segments.
// static
std::vector<QRCodeGenerator::Segment> QRCodeGenerator::SegmentInput(
VersionClass vclass,
base::span<const uint8_t> input) {
std::vector<Segment> segments = InitialSegmentation(input);
// Zero or one segments are trivially optimal.
if (segments.size() < 2) {
return segments;
}
// digit_alpha_start_idx is the index of the start of the current span of
// DIGIT/ALPHANUM segments.
absl::optional<size_t> digit_alpha_start_idx;
for (size_t i = 0; i < segments.size(); i++) {
// Invariants must always be maintained.
DCHECK(IsValidSegmentation(segments, input));
DCHECK(NoSuperfluousSegments(segments));
const bool is_digit_alpha = segments[i].type == SegmentType::DIGIT ||
segments[i].type == SegmentType::ALPHANUM;
if (is_digit_alpha) {
if (!digit_alpha_start_idx) {
digit_alpha_start_idx = i;
}
continue;
}
if (!digit_alpha_start_idx) {
continue;
}
// |segment[i]| is BINARY and |*digit_alpha_start_idx| to i-1 are all
// DIGIT/ALPHANUM segments.
DCHECK_EQ(segments[i].type, SegmentType::BINARY);
// Optimise the span of DIGIT/ALPHANUM segments. This returns the index of
// the right edge of the span after merging, i.e. the translation of |i-1|.
// Thus |i| is adjusted to be that plus one.
i = SegmentDigitAlphaSpan(vclass, &segments, *digit_alpha_start_idx,
i - 1) +
1;
// Is there also a BINARY segment on the left of the DIGIT/ALPHANUM span? If
// so it must be included in merge decisions in order to maintain invariant
// three.
const bool has_left = *digit_alpha_start_idx != 0;
DCHECK(!has_left ||
segments[*digit_alpha_start_idx - 1].type == SegmentType::BINARY);
if (!has_left) {
i = MaybeMerge(vclass, &segments, *digit_alpha_start_idx, i,
SegmentType::BINARY);
} else {
i = MaybeMerge(vclass, &segments, *digit_alpha_start_idx - 1, i,
SegmentType::BINARY);
}
digit_alpha_start_idx.reset();
}
if (digit_alpha_start_idx) {
// There was a trailing span of DIGIT/ALPHANUM segments that wasn't
// considered for merging. So we do that now.
SegmentDigitAlphaSpan(vclass, &segments, *digit_alpha_start_idx,
segments.size() - 1);
if (*digit_alpha_start_idx != 0) {
DCHECK_EQ(segments[*digit_alpha_start_idx - 1].type, SegmentType::BINARY);
MaybeMerge(vclass, &segments, *digit_alpha_start_idx - 1,
segments.size() - 1, SegmentType::BINARY);
}
}
return segments;
}