-
Notifications
You must be signed in to change notification settings - Fork 3
/
QrCode.hpp
346 lines (229 loc) · 13.8 KB
/
QrCode.hpp
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
#pragma once
#include <cstdint>
#include <deque>
#include <stdexcept>
#include <string>
#include <vector>
#include "QrSegment.hpp"
namespace qrcodegen {
/*
* A QR Code symbol, which is a type of two-dimension barcode.
* Invented by Denso Wave and described in the ISO/IEC 18004 standard.
* Instances of this class represent an immutable square grid of black and white cells.
* The class provides static factory functions to create a QR Code from text or binary data.
* The class covers the QR Code Model 2 specification, supporting all versions (sizes)
* from 1 to 40, all 4 error correction levels, and 4 character encoding modes.
*
* Ways to create a QR Code object:
* - High level: Take the payload data and call QrCode::encodeText() or QrCode::encodeBinary().
* - Mid level: Custom-make the list of segments and call QrCode::encodeSegments().
* - Low level: Custom-make the array of data codeword bytes (including
* segment headers and final padding, excluding error correction codewords),
* supply the appropriate version number, and call the QrCode() constructor.
* (Note that all ways require supplying the desired error correction level.)
*/
class QrCode final {
/*---- Public helper enumeration ----*/
/* The error correction level in a QR Code symbol. */
public: enum class Ecc {
LOW = 0, // The QR Code can tolerate about 7% erroneous codewords
MEDIUM, // The QR Code can tolerate about 15% erroneous codewords
QUARTILE, // The QR Code can tolerate about 25% erroneous codewords
HIGH, // The QR Code can tolerate about 30% erroneous codewords
};
// Returns a value in the range 0 to 3 (unsigned 2-bit integer).
private: static int getFormatBits(Ecc ecl);
/*---- Static factory functions (high level) ----*/
/*
* Returns a QR Code representing the given Unicode text string at the given error correction level.
* As a conservative upper bound, this function is guaranteed to succeed for strings that have 2953 or fewer
* UTF-8 code units (not Unicode code points) if the low error correction level is used. The smallest possible
* QR Code version is automatically chosen for the output. The ECC level of the result may be higher than
* the ecl argument if it can be done without increasing the version.
*/
public: static QrCode encodeText(const char *text, Ecc ecl);
/*
* Returns a QR Code representing the given binary data at the given error correction level.
* This function always encodes using the binary segment mode, not any text mode. The maximum number of
* bytes allowed is 2953. The smallest possible QR Code version is automatically chosen for the output.
* The ECC level of the result may be higher than the ecl argument if it can be done without increasing the version.
*/
public: static QrCode encodeBinary(const std::vector<std::uint8_t> &data, Ecc ecl);
/*---- Static factory functions (mid level) ----*/
/*
* Returns a QR Code representing the given segments with the given encoding parameters.
* The smallest possible QR Code version within the given range is automatically
* chosen for the output. Iff boostEcl is true, then the ECC level of the result
* may be higher than the ecl argument if it can be done without increasing the
* version. The mask number is either between 0 to 7 (inclusive) to force that
* mask, or -1 to automatically choose an appropriate mask (which may be slow).
* This function allows the user to create a custom sequence of segments that switches
* between modes (such as alphanumeric and byte) to encode text in less space.
* This is a mid-level API; the high-level API is encodeText() and encodeBinary().
*/
public: static QrCode encodeSegments(const std::vector<QrSegment> &segs, Ecc ecl,
int minVersion = 1, int maxVersion = 40, int mask = -1, bool boostEcl = true); // All optional parameters
/*---- Instance fields ----*/
// Immutable scalar parameters:
/* The version number of this QR Code, which is between 1 and 40 (inclusive).
* This determines the size of this barcode. */
private: int version;
/* The width and height of this QR Code, measured in modules, between
* 21 and 177 (inclusive). This is equal to version * 4 + 17. */
private: int size;
/* The error correction level used in this QR Code. */
private: Ecc errorCorrectionLevel;
/* The index of the mask pattern used in this QR Code, which is between 0 and 7 (inclusive).
* Even if a QR Code is created with automatic masking requested (mask = -1),
* the resulting object still has a mask value between 0 and 7. */
private: int mask;
// Private grids of modules/pixels, with dimensions of size*size:
// The modules of this QR Code (false = white, true = black).
// Immutable after constructor finishes. Accessed through getModule().
private: std::vector<std::vector<bool> > modules;
// Indicates function modules that are not subjected to masking. Discarded when constructor finishes.
private: std::vector<std::vector<bool> > isFunction;
/*---- Constructor (low level) ----*/
/*
* Creates a new QR Code with the given version number,
* error correction level, data codeword bytes, and mask number.
* This is a low-level API that most users should not use directly.
* A mid-level API is the encodeSegments() function.
*/
public: QrCode(int ver, Ecc ecl, const std::vector<std::uint8_t> &dataCodewords, int mask);
/*---- Public instance methods ----*/
/* Returns this QR Code's version, in the range [1, 40]. */
public: int getVersion() const;
/* Returns this QR Code's size, in the range [21, 177].*/
public: int getSize() const;
/* Returns this QR Code's error correction level.*/
public: Ecc getErrorCorrectionLevel() const;
/* Returns this QR Code's mask, in the range [0, 7]. */
public: int getMask() const;
/*
* Returns the color of the module (pixel) at the given coordinates, which is false
* for white or true for black. The top left corner has the coordinates (x=0, y=0).
* If the given coordinates are out of bounds, then false (white) is returned.
*/
public: bool getModule(int x, int y) const;
/*
* Returns a string of SVG code for an image depicting this QR Code, with the given number
* of border modules. The string always uses Unix newlines (\n), regardless of the platform.
*/
public: std::string toSvgString(int border) const;
/*---- Private helper methods for constructor: Drawing function modules ----*/
// Reads this object's version field, and draws and marks all function modules.
private: void drawFunctionPatterns();
// Draws two copies of the format bits (with its own error correction code)
// based on the given mask and this object's error correction level field.
private: void drawFormatBits(int mask);
// Draws two copies of the version bits (with its own error correction code),
// based on this object's version field, iff 7 <= version <= 40.
private: void drawVersion();
// Draws a 9*9 finder pattern including the border separator,
// with the center module at (x, y). Modules can be out of bounds.
private: void drawFinderPattern(int x, int y);
// Draws a 5*5 alignment pattern, with the center module
// at (x, y). All modules must be in bounds.
private: void drawAlignmentPattern(int x, int y);
// Sets the color of a module and marks it as a function module.
// Only used by the constructor. Coordinates must be in bounds.
private: void setFunctionModule(int x, int y, bool isBlack);
// Returns the color of the module at the given coordinates, which must be in range.
private: bool module(int x, int y) const;
/*---- Private helper methods for constructor: Codewords and masking ----*/
// Returns a new byte string representing the given data with the appropriate error correction
// codewords appended to it, based on this object's version and error correction level.
private: std::vector<std::uint8_t> addEccAndInterleave(const std::vector<std::uint8_t> &data) const;
// Draws the given sequence of 8-bit codewords (data and error correction) onto the entire
// data area of this QR Code. Function modules need to be marked off before this is called.
private: void drawCodewords(const std::vector<std::uint8_t> &data);
// XORs the codeword modules in this QR Code with the given mask pattern.
// The function modules must be marked and the codeword bits must be drawn
// before masking. Due to the arithmetic of XOR, calling applyMask() with
// the same mask value a second time will undo the mask. A final well-formed
// QR Code needs exactly one (not zero, two, etc.) mask applied.
private: void applyMask(int mask);
// Calculates and returns the penalty score based on state of this QR Code's current modules.
// This is used by the automatic mask choice algorithm to find the mask pattern that yields the lowest score.
private: long getPenaltyScore() const;
/*---- Private helper functions ----*/
// Returns an ascending list of positions of alignment patterns for this version number.
// Each position is in the range [0,177), and are used on both the x and y axes.
// This could be implemented as lookup table of 40 variable-length lists of unsigned bytes.
private: std::vector<int> getAlignmentPatternPositions() const;
// Returns the number of data bits that can be stored in a QR Code of the given version number, after
// all function modules are excluded. This includes remainder bits, so it might not be a multiple of 8.
// The result is in the range [208, 29648]. This could be implemented as a 40-entry lookup table.
private: static int getNumRawDataModules(int ver);
// Returns the number of 8-bit data (i.e. not error correction) codewords contained in any
// QR Code of the given version number and error correction level, with remainder bits discarded.
// This stateless pure function could be implemented as a (40*4)-cell lookup table.
private: static int getNumDataCodewords(int ver, Ecc ecl);
// Inserts the given value to the front of the given array, which shifts over the
// existing values and deletes the last value. A helper function for getPenaltyScore().
private: static void addRunToHistory(int run, std::deque<int> &history);
// Tests whether the given run history has the pattern of ratio 1:1:3:1:1 in the middle, and
// surrounded by at least 4 on either or both ends. A helper function for getPenaltyScore().
// Must only be called immediately after a run of white modules has ended.
private: static bool hasFinderLikePattern(const std::deque<int> &runHistory);
// Returns true iff the i'th bit of x is set to 1.
private: static bool getBit(long x, int i);
/*---- Constants and tables ----*/
// The minimum version number supported in the QR Code Model 2 standard.
public: static constexpr int MIN_VERSION = 1;
// The maximum version number supported in the QR Code Model 2 standard.
public: static constexpr int MAX_VERSION = 40;
// For use in getPenaltyScore(), when evaluating which mask is best.
private: static const int PENALTY_N1;
private: static const int PENALTY_N2;
private: static const int PENALTY_N3;
private: static const int PENALTY_N4;
private: static const std::int8_t ECC_CODEWORDS_PER_BLOCK[4][41];
private: static const std::int8_t NUM_ERROR_CORRECTION_BLOCKS[4][41];
/*---- Private helper class ----*/
/*
* Computes the Reed-Solomon error correction codewords for a sequence of data codewords
* at a given degree. Objects are immutable, and the state only depends on the degree.
* This class exists because each data block in a QR Code shares the same the divisor polynomial.
*/
private: class ReedSolomonGenerator final {
/*-- Immutable field --*/
// Coefficients of the divisor polynomial, stored from highest to lowest power, excluding the leading term which
// is always 1. For example the polynomial x^3 + 255x^2 + 8x + 93 is stored as the uint8 array {255, 8, 93}.
private: std::vector<std::uint8_t> coefficients;
/*-- Constructor --*/
/*
* Creates a Reed-Solomon ECC generator for the given degree. This could be implemented
* as a lookup table over all possible parameter values, instead of as an algorithm.
*/
public: explicit ReedSolomonGenerator(int degree);
/*-- Method --*/
/*
* Computes and returns the Reed-Solomon error correction codewords for the given
* sequence of data codewords. The returned object is always a new byte array.
* This method does not alter this object's state (because it is immutable).
*/
public: std::vector<std::uint8_t> getRemainder(const std::vector<std::uint8_t> &data) const;
/*-- Static function --*/
// Returns the product of the two given field elements modulo GF(2^8/0x11D).
// All inputs are valid. This could be implemented as a 256*256 lookup table.
private: static std::uint8_t multiply(std::uint8_t x, std::uint8_t y);
};
};
/*---- Public exception class ----*/
/*
* Thrown when the supplied data does not fit any QR Code version. Ways to handle this exception include:
* - Decrease the error correction level if it was greater than Ecc::LOW.
* - If the encodeSegments() function was called with a maxVersion argument, then increase
* it if it was less than QrCode::MAX_VERSION. (This advice does not apply to the other
* factory functions because they search all versions up to QrCode::MAX_VERSION.)
* - Split the text data into better or optimal segments in order to reduce the number of bits required.
* - Change the text or binary data to be shorter.
* - Change the text to fit the character set of a particular segment mode (e.g. alphanumeric).
* - Propagate the error upward to the caller/user.
*/
class data_too_long : public std::length_error {
public: explicit data_too_long(const std::string &msg);
};
}