1# 2# QR Code generator library (Python 2, 3) 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 24import collections, itertools, re, sys 25 26 27""" 28This module "qrcodegen", public members: 29- Class QrCode: 30 - Function encode_text(str text, QrCode.Ecc ecl) -> QrCode 31 - Function encode_binary(bytes data, QrCode.Ecc ecl) -> QrCode 32 - Function encode_segments(list<QrSegment> segs, QrCode.Ecc ecl, 33 int minversion=1, int maxversion=40, mask=-1, boostecl=true) -> QrCode 34 - Constants int MIN_VERSION, MAX_VERSION 35 - Constructor QrCode(int version, QrCode.Ecc ecl, bytes datacodewords, int mask) 36 - Method get_version() -> int 37 - Method get_size() -> int 38 - Method get_error_correction_level() -> QrCode.Ecc 39 - Method get_mask() -> int 40 - Method get_module(int x, int y) -> bool 41 - Method to_svg_str(int border) -> str 42 - Enum Ecc: 43 - Constants LOW, MEDIUM, QUARTILE, HIGH 44 - Field int ordinal 45- Class QrSegment: 46 - Function make_bytes(bytes data) -> QrSegment 47 - Function make_numeric(str digits) -> QrSegment 48 - Function make_alphanumeric(str text) -> QrSegment 49 - Function make_segments(str text) -> list<QrSegment> 50 - Function make_eci(int assignval) -> QrSegment 51 - Constructor QrSegment(QrSegment.Mode mode, int numch, list<int> bitdata) 52 - Method get_mode() -> QrSegment.Mode 53 - Method get_num_chars() -> int 54 - Method get_data() -> list<int> 55 - Constants regex NUMERIC_REGEX, ALPHANUMERIC_REGEX 56 - Enum Mode: 57 - Constants NUMERIC, ALPHANUMERIC, BYTE, KANJI, ECI 58""" 59 60 61# ---- QR Code symbol class ---- 62 63class QrCode(object): 64 """A QR Code symbol, which is a type of two-dimension barcode. 65 Invented by Denso Wave and described in the ISO/IEC 18004 standard. 66 Instances of this class represent an immutable square grid of black and white cells. 67 The class provides static factory functions to create a QR Code from text or binary data. 68 The class covers the QR Code Model 2 specification, supporting all versions (sizes) 69 from 1 to 40, all 4 error correction levels, and 4 character encoding modes. 70 71 Ways to create a QR Code object: 72 - High level: Take the payload data and call QrCode.encode_text() or QrCode.encode_binary(). 73 - Mid level: Custom-make the list of segments and call QrCode.encode_segments(). 74 - Low level: Custom-make the array of data codeword bytes (including 75 segment headers and final padding, excluding error correction codewords), 76 supply the appropriate version number, and call the QrCode() constructor. 77 (Note that all ways require supplying the desired error correction level.)""" 78 79 # ---- Static factory functions (high level) ---- 80 81 @staticmethod 82 def encode_text(text, ecl): 83 """Returns a QR Code representing the given Unicode text string at the given error correction level. 84 As a conservative upper bound, this function is guaranteed to succeed for strings that have 738 or fewer 85 Unicode code points (not UTF-16 code units) if the low error correction level is used. The smallest possible 86 QR Code version is automatically chosen for the output. The ECC level of the result may be higher than the 87 ecl argument if it can be done without increasing the version.""" 88 segs = QrSegment.make_segments(text) 89 return QrCode.encode_segments(segs, ecl) 90 91 92 @staticmethod 93 def encode_binary(data, ecl): 94 """Returns a QR Code representing the given binary data at the given error correction level. 95 This function always encodes using the binary segment mode, not any text mode. The maximum number of 96 bytes allowed is 2953. The smallest possible QR Code version is automatically chosen for the output. 97 The ECC level of the result may be higher than the ecl argument if it can be done without increasing the version.""" 98 if not isinstance(data, (bytes, bytearray)): 99 raise TypeError("Byte string/list expected") 100 return QrCode.encode_segments([QrSegment.make_bytes(data)], ecl) 101 102 103 # ---- Static factory functions (mid level) ---- 104 105 @staticmethod 106 def encode_segments(segs, ecl, minversion=1, maxversion=40, mask=-1, boostecl=True): 107 """Returns a QR Code representing the given segments with the given encoding parameters. 108 The smallest possible QR Code version within the given range is automatically 109 chosen for the output. Iff boostecl is true, then the ECC level of the result 110 may be higher than the ecl argument if it can be done without increasing the 111 version. The mask number is either between 0 to 7 (inclusive) to force that 112 mask, or -1 to automatically choose an appropriate mask (which may be slow). 113 This function allows the user to create a custom sequence of segments that switches 114 between modes (such as alphanumeric and byte) to encode text in less space. 115 This is a mid-level API; the high-level API is encode_text() and encode_binary().""" 116 117 if not (QrCode.MIN_VERSION <= minversion <= maxversion <= QrCode.MAX_VERSION) or not (-1 <= mask <= 7): 118 raise ValueError("Invalid value") 119 120 # Find the minimal version number to use 121 for version in range(minversion, maxversion + 1): 122 datacapacitybits = QrCode._get_num_data_codewords(version, ecl) * 8 # Number of data bits available 123 datausedbits = QrSegment.get_total_bits(segs, version) 124 if datausedbits is not None and datausedbits <= datacapacitybits: 125 break # This version number is found to be suitable 126 if version >= maxversion: # All versions in the range could not fit the given data 127 msg = "Segment too long" 128 if datausedbits is not None: 129 msg = "Data length = {} bits, Max capacity = {} bits".format(datausedbits, datacapacitybits) 130 raise DataTooLongError(msg) 131 if datausedbits is None: 132 raise AssertionError() 133 134 # Increase the error correction level while the data still fits in the current version number 135 for newecl in (QrCode.Ecc.MEDIUM, QrCode.Ecc.QUARTILE, QrCode.Ecc.HIGH): # From low to high 136 if boostecl and datausedbits <= QrCode._get_num_data_codewords(version, newecl) * 8: 137 ecl = newecl 138 139 # Concatenate all segments to create the data bit string 140 bb = _BitBuffer() 141 for seg in segs: 142 bb.append_bits(seg.get_mode().get_mode_bits(), 4) 143 bb.append_bits(seg.get_num_chars(), seg.get_mode().num_char_count_bits(version)) 144 bb.extend(seg._bitdata) 145 assert len(bb) == datausedbits 146 147 # Add terminator and pad up to a byte if applicable 148 datacapacitybits = QrCode._get_num_data_codewords(version, ecl) * 8 149 assert len(bb) <= datacapacitybits 150 bb.append_bits(0, min(4, datacapacitybits - len(bb))) 151 bb.append_bits(0, -len(bb) % 8) # Note: Python's modulo on negative numbers behaves better than C family languages 152 assert len(bb) % 8 == 0 153 154 # Pad with alternating bytes until data capacity is reached 155 for padbyte in itertools.cycle((0xEC, 0x11)): 156 if len(bb) >= datacapacitybits: 157 break 158 bb.append_bits(padbyte, 8) 159 160 # Pack bits into bytes in big endian 161 datacodewords = [0] * (len(bb) // 8) 162 for (i, bit) in enumerate(bb): 163 datacodewords[i >> 3] |= bit << (7 - (i & 7)) 164 165 # Create the QR Code object 166 return QrCode(version, ecl, datacodewords, mask) 167 168 169 # ---- Constructor (low level) ---- 170 171 def __init__(self, version, errcorlvl, datacodewords, mask): 172 """Creates a new QR Code with the given version number, 173 error correction level, data codeword bytes, and mask number. 174 This is a low-level API that most users should not use directly. 175 A mid-level API is the encode_segments() function.""" 176 177 # Check scalar arguments and set fields 178 if not (QrCode.MIN_VERSION <= version <= QrCode.MAX_VERSION): 179 raise ValueError("Version value out of range") 180 if not (-1 <= mask <= 7): 181 raise ValueError("Mask value out of range") 182 if not isinstance(errcorlvl, QrCode.Ecc): 183 raise TypeError("QrCode.Ecc expected") 184 185 # The version number of this QR Code, which is between 1 and 40 (inclusive). 186 # This determines the size of this barcode. 187 self._version = version 188 189 # The width and height of this QR Code, measured in modules, between 190 # 21 and 177 (inclusive). This is equal to version * 4 + 17. 191 self._size = version * 4 + 17 192 193 # The error correction level used in this QR Code. 194 self._errcorlvl = errcorlvl 195 196 # Initialize both grids to be size*size arrays of Boolean false 197 # The modules of this QR Code (False = white, True = black). 198 # Immutable after constructor finishes. Accessed through get_module(). 199 self._modules = [[False] * self._size for _ in range(self._size)] # Initially all white 200 # Indicates function modules that are not subjected to masking. Discarded when constructor finishes 201 self._isfunction = [[False] * self._size for _ in range(self._size)] 202 203 # Compute ECC, draw modules 204 self._draw_function_patterns() 205 allcodewords = self._add_ecc_and_interleave(datacodewords) 206 self._draw_codewords(allcodewords) 207 208 # Do masking 209 if mask == -1: # Automatically choose best mask 210 minpenalty = 1 << 32 211 for i in range(8): 212 self._apply_mask(i) 213 self._draw_format_bits(i) 214 penalty = self._get_penalty_score() 215 if penalty < minpenalty: 216 mask = i 217 minpenalty = penalty 218 self._apply_mask(i) # Undoes the mask due to XOR 219 assert 0 <= mask <= 7 220 self._apply_mask(mask) # Apply the final choice of mask 221 self._draw_format_bits(mask) # Overwrite old format bits 222 223 # The index of the mask pattern used in this QR Code, which is between 0 and 7 (inclusive). 224 # Even if a QR Code is created with automatic masking requested (mask = -1), 225 # the resulting object still has a mask value between 0 and 7. 226 self._mask = mask 227 228 del self._isfunction 229 230 231 # ---- Accessor methods ---- 232 233 def get_version(self): 234 """Returns this QR Code's version number, in the range [1, 40].""" 235 return self._version 236 237 def get_size(self): 238 """Returns this QR Code's size, in the range [21, 177].""" 239 return self._size 240 241 def get_error_correction_level(self): 242 """Returns this QR Code's error correction level.""" 243 return self._errcorlvl 244 245 def get_mask(self): 246 """Returns this QR Code's mask, in the range [0, 7].""" 247 return self._mask 248 249 def get_module(self, x, y): 250 """Returns the color of the module (pixel) at the given coordinates, which is False 251 for white or True for black. The top left corner has the coordinates (x=0, y=0). 252 If the given coordinates are out of bounds, then False (white) is returned.""" 253 return (0 <= x < self._size) and (0 <= y < self._size) and self._modules[y][x] 254 255 256 # ---- Public instance methods ---- 257 258 def to_svg_str(self, border): 259 """Returns a string of SVG code for an image depicting this QR Code, with the given number 260 of border modules. The string always uses Unix newlines (\n), regardless of the platform.""" 261 if border < 0: 262 raise ValueError("Border must be non-negative") 263 parts = [] 264 for y in range(self._size): 265 for x in range(self._size): 266 if self.get_module(x, y): 267 parts.append("M{},{}h1v1h-1z".format(x + border, y + border)) 268 return """<?xml version="1.0" encoding="UTF-8"?> 269<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> 270<svg xmlns="http://www.w3.org/2000/svg" version="1.1" viewBox="0 0 {0} {0}" stroke="none"> 271 <rect width="100%" height="100%" fill="#FFFFFF"/> 272 <path d="{1}" fill="#000000"/> 273</svg> 274""".format(self._size + border * 2, " ".join(parts)) 275 276 277 # ---- Private helper methods for constructor: Drawing function modules ---- 278 279 def _draw_function_patterns(self): 280 """Reads this object's version field, and draws and marks all function modules.""" 281 # Draw horizontal and vertical timing patterns 282 for i in range(self._size): 283 self._set_function_module(6, i, i % 2 == 0) 284 self._set_function_module(i, 6, i % 2 == 0) 285 286 # Draw 3 finder patterns (all corners except bottom right; overwrites some timing modules) 287 self._draw_finder_pattern(3, 3) 288 self._draw_finder_pattern(self._size - 4, 3) 289 self._draw_finder_pattern(3, self._size - 4) 290 291 # Draw numerous alignment patterns 292 alignpatpos = self._get_alignment_pattern_positions() 293 numalign = len(alignpatpos) 294 skips = ((0, 0), (0, numalign - 1), (numalign - 1, 0)) 295 for i in range(numalign): 296 for j in range(numalign): 297 if (i, j) not in skips: # Don't draw on the three finder corners 298 self._draw_alignment_pattern(alignpatpos[i], alignpatpos[j]) 299 300 # Draw configuration data 301 self._draw_format_bits(0) # Dummy mask value; overwritten later in the constructor 302 self._draw_version() 303 304 305 def _draw_format_bits(self, mask): 306 """Draws two copies of the format bits (with its own error correction code) 307 based on the given mask and this object's error correction level field.""" 308 # Calculate error correction code and pack bits 309 data = self._errcorlvl.formatbits << 3 | mask # errCorrLvl is uint2, mask is uint3 310 rem = data 311 for _ in range(10): 312 rem = (rem << 1) ^ ((rem >> 9) * 0x537) 313 bits = (data << 10 | rem) ^ 0x5412 # uint15 314 assert bits >> 15 == 0 315 316 # Draw first copy 317 for i in range(0, 6): 318 self._set_function_module(8, i, _get_bit(bits, i)) 319 self._set_function_module(8, 7, _get_bit(bits, 6)) 320 self._set_function_module(8, 8, _get_bit(bits, 7)) 321 self._set_function_module(7, 8, _get_bit(bits, 8)) 322 for i in range(9, 15): 323 self._set_function_module(14 - i, 8, _get_bit(bits, i)) 324 325 # Draw second copy 326 for i in range(0, 8): 327 self._set_function_module(self._size - 1 - i, 8, _get_bit(bits, i)) 328 for i in range(8, 15): 329 self._set_function_module(8, self._size - 15 + i, _get_bit(bits, i)) 330 self._set_function_module(8, self._size - 8, True) # Always black 331 332 333 def _draw_version(self): 334 """Draws two copies of the version bits (with its own error correction code), 335 based on this object's version field, iff 7 <= version <= 40.""" 336 if self._version < 7: 337 return 338 339 # Calculate error correction code and pack bits 340 rem = self._version # version is uint6, in the range [7, 40] 341 for _ in range(12): 342 rem = (rem << 1) ^ ((rem >> 11) * 0x1F25) 343 bits = self._version << 12 | rem # uint18 344 assert bits >> 18 == 0 345 346 # Draw two copies 347 for i in range(18): 348 bit = _get_bit(bits, i) 349 a = self._size - 11 + i % 3 350 b = i // 3 351 self._set_function_module(a, b, bit) 352 self._set_function_module(b, a, bit) 353 354 355 def _draw_finder_pattern(self, x, y): 356 """Draws a 9*9 finder pattern including the border separator, 357 with the center module at (x, y). Modules can be out of bounds.""" 358 for dy in range(-4, 5): 359 for dx in range(-4, 5): 360 xx, yy = x + dx, y + dy 361 if (0 <= xx < self._size) and (0 <= yy < self._size): 362 # Chebyshev/infinity norm 363 self._set_function_module(xx, yy, max(abs(dx), abs(dy)) not in (2, 4)) 364 365 366 def _draw_alignment_pattern(self, x, y): 367 """Draws a 5*5 alignment pattern, with the center module 368 at (x, y). All modules must be in bounds.""" 369 for dy in range(-2, 3): 370 for dx in range(-2, 3): 371 self._set_function_module(x + dx, y + dy, max(abs(dx), abs(dy)) != 1) 372 373 374 def _set_function_module(self, x, y, isblack): 375 """Sets the color of a module and marks it as a function module. 376 Only used by the constructor. Coordinates must be in bounds.""" 377 assert type(isblack) is bool 378 self._modules[y][x] = isblack 379 self._isfunction[y][x] = True 380 381 382 # ---- Private helper methods for constructor: Codewords and masking ---- 383 384 def _add_ecc_and_interleave(self, data): 385 """Returns a new byte string representing the given data with the appropriate error correction 386 codewords appended to it, based on this object's version and error correction level.""" 387 version = self._version 388 assert len(data) == QrCode._get_num_data_codewords(version, self._errcorlvl) 389 390 # Calculate parameter numbers 391 numblocks = QrCode._NUM_ERROR_CORRECTION_BLOCKS[self._errcorlvl.ordinal][version] 392 blockecclen = QrCode._ECC_CODEWORDS_PER_BLOCK [self._errcorlvl.ordinal][version] 393 rawcodewords = QrCode._get_num_raw_data_modules(version) // 8 394 numshortblocks = numblocks - rawcodewords % numblocks 395 shortblocklen = rawcodewords // numblocks 396 397 # Split data into blocks and append ECC to each block 398 blocks = [] 399 rsdiv = QrCode._reed_solomon_compute_divisor(blockecclen) 400 k = 0 401 for i in range(numblocks): 402 dat = data[k : k + shortblocklen - blockecclen + (0 if i < numshortblocks else 1)] 403 k += len(dat) 404 ecc = QrCode._reed_solomon_compute_remainder(dat, rsdiv) 405 if i < numshortblocks: 406 dat.append(0) 407 blocks.append(dat + ecc) 408 assert k == len(data) 409 410 # Interleave (not concatenate) the bytes from every block into a single sequence 411 result = [] 412 for i in range(len(blocks[0])): 413 for (j, blk) in enumerate(blocks): 414 # Skip the padding byte in short blocks 415 if i != shortblocklen - blockecclen or j >= numshortblocks: 416 result.append(blk[i]) 417 assert len(result) == rawcodewords 418 return result 419 420 421 def _draw_codewords(self, data): 422 """Draws the given sequence of 8-bit codewords (data and error correction) onto the entire 423 data area of this QR Code. Function modules need to be marked off before this is called.""" 424 assert len(data) == QrCode._get_num_raw_data_modules(self._version) // 8 425 426 i = 0 # Bit index into the data 427 # Do the funny zigzag scan 428 for right in range(self._size - 1, 0, -2): # Index of right column in each column pair 429 if right <= 6: 430 right -= 1 431 for vert in range(self._size): # Vertical counter 432 for j in range(2): 433 x = right - j # Actual x coordinate 434 upward = (right + 1) & 2 == 0 435 y = (self._size - 1 - vert) if upward else vert # Actual y coordinate 436 if not self._isfunction[y][x] and i < len(data) * 8: 437 self._modules[y][x] = _get_bit(data[i >> 3], 7 - (i & 7)) 438 i += 1 439 # If this QR Code has any remainder bits (0 to 7), they were assigned as 440 # 0/false/white by the constructor and are left unchanged by this method 441 assert i == len(data) * 8 442 443 444 def _apply_mask(self, mask): 445 """XORs the codeword modules in this QR Code with the given mask pattern. 446 The function modules must be marked and the codeword bits must be drawn 447 before masking. Due to the arithmetic of XOR, calling applyMask() with 448 the same mask value a second time will undo the mask. A final well-formed 449 QR Code needs exactly one (not zero, two, etc.) mask applied.""" 450 if not (0 <= mask <= 7): 451 raise ValueError("Mask value out of range") 452 masker = QrCode._MASK_PATTERNS[mask] 453 for y in range(self._size): 454 for x in range(self._size): 455 self._modules[y][x] ^= (masker(x, y) == 0) and (not self._isfunction[y][x]) 456 457 458 def _get_penalty_score(self): 459 """Calculates and returns the penalty score based on state of this QR Code's current modules. 460 This is used by the automatic mask choice algorithm to find the mask pattern that yields the lowest score.""" 461 result = 0 462 size = self._size 463 modules = self._modules 464 465 # Adjacent modules in row having same color, and finder-like patterns 466 for y in range(size): 467 runcolor = False 468 runx = 0 469 runhistory = collections.deque([0] * 7, 7) 470 for x in range(size): 471 if modules[y][x] == runcolor: 472 runx += 1 473 if runx == 5: 474 result += QrCode._PENALTY_N1 475 elif runx > 5: 476 result += 1 477 else: 478 self._finder_penalty_add_history(runx, runhistory) 479 if not runcolor: 480 result += self._finder_penalty_count_patterns(runhistory) * QrCode._PENALTY_N3 481 runcolor = modules[y][x] 482 runx = 1 483 result += self._finder_penalty_terminate_and_count(runcolor, runx, runhistory) * QrCode._PENALTY_N3 484 # Adjacent modules in column having same color, and finder-like patterns 485 for x in range(size): 486 runcolor = False 487 runy = 0 488 runhistory = collections.deque([0] * 7, 7) 489 for y in range(size): 490 if modules[y][x] == runcolor: 491 runy += 1 492 if runy == 5: 493 result += QrCode._PENALTY_N1 494 elif runy > 5: 495 result += 1 496 else: 497 self._finder_penalty_add_history(runy, runhistory) 498 if not runcolor: 499 result += self._finder_penalty_count_patterns(runhistory) * QrCode._PENALTY_N3 500 runcolor = modules[y][x] 501 runy = 1 502 result += self._finder_penalty_terminate_and_count(runcolor, runy, runhistory) * QrCode._PENALTY_N3 503 504 # 2*2 blocks of modules having same color 505 for y in range(size - 1): 506 for x in range(size - 1): 507 if modules[y][x] == modules[y][x + 1] == modules[y + 1][x] == modules[y + 1][x + 1]: 508 result += QrCode._PENALTY_N2 509 510 # Balance of black and white modules 511 black = sum((1 if cell else 0) for row in modules for cell in row) 512 total = size**2 # Note that size is odd, so black/total != 1/2 513 # Compute the smallest integer k >= 0 such that (45-5k)% <= black/total <= (55+5k)% 514 k = (abs(black * 20 - total * 10) + total - 1) // total - 1 515 result += k * QrCode._PENALTY_N4 516 return result 517 518 519 # ---- Private helper functions ---- 520 521 def _get_alignment_pattern_positions(self): 522 """Returns an ascending list of positions of alignment patterns for this version number. 523 Each position is in the range [0,177), and are used on both the x and y axes. 524 This could be implemented as lookup table of 40 variable-length lists of integers.""" 525 ver = self._version 526 if ver == 1: 527 return [] 528 else: 529 numalign = ver // 7 + 2 530 step = 26 if (ver == 32) else \ 531 (ver*4 + numalign*2 + 1) // (numalign*2 - 2) * 2 532 result = [(self._size - 7 - i * step) for i in range(numalign - 1)] + [6] 533 return list(reversed(result)) 534 535 536 @staticmethod 537 def _get_num_raw_data_modules(ver): 538 """Returns the number of data bits that can be stored in a QR Code of the given version number, after 539 all function modules are excluded. This includes remainder bits, so it might not be a multiple of 8. 540 The result is in the range [208, 29648]. This could be implemented as a 40-entry lookup table.""" 541 if not (QrCode.MIN_VERSION <= ver <= QrCode.MAX_VERSION): 542 raise ValueError("Version number out of range") 543 result = (16 * ver + 128) * ver + 64 544 if ver >= 2: 545 numalign = ver // 7 + 2 546 result -= (25 * numalign - 10) * numalign - 55 547 if ver >= 7: 548 result -= 36 549 assert 208 <= result <= 29648 550 return result 551 552 553 @staticmethod 554 def _get_num_data_codewords(ver, ecl): 555 """Returns the number of 8-bit data (i.e. not error correction) codewords contained in any 556 QR Code of the given version number and error correction level, with remainder bits discarded. 557 This stateless pure function could be implemented as a (40*4)-cell lookup table.""" 558 return QrCode._get_num_raw_data_modules(ver) // 8 \ 559 - QrCode._ECC_CODEWORDS_PER_BLOCK [ecl.ordinal][ver] \ 560 * QrCode._NUM_ERROR_CORRECTION_BLOCKS[ecl.ordinal][ver] 561 562 563 @staticmethod 564 def _reed_solomon_compute_divisor(degree): 565 """Returns a Reed-Solomon ECC generator polynomial for the given degree. This could be 566 implemented as a lookup table over all possible parameter values, instead of as an algorithm.""" 567 if not (1 <= degree <= 255): 568 raise ValueError("Degree out of range") 569 # Polynomial coefficients are stored from highest to lowest power, excluding the leading term which is always 1. 570 # For example the polynomial x^3 + 255x^2 + 8x + 93 is stored as the uint8 array [255, 8, 93]. 571 result = [0] * (degree - 1) + [1] # Start off with the monomial x^0 572 573 # Compute the product polynomial (x - r^0) * (x - r^1) * (x - r^2) * ... * (x - r^{degree-1}), 574 # and drop the highest monomial term which is always 1x^degree. 575 # Note that r = 0x02, which is a generator element of this field GF(2^8/0x11D). 576 root = 1 577 for _ in range(degree): # Unused variable i 578 # Multiply the current product by (x - r^i) 579 for j in range(degree): 580 result[j] = QrCode._reed_solomon_multiply(result[j], root) 581 if j + 1 < degree: 582 result[j] ^= result[j + 1] 583 root = QrCode._reed_solomon_multiply(root, 0x02) 584 return result 585 586 587 @staticmethod 588 def _reed_solomon_compute_remainder(data, divisor): 589 """Returns the Reed-Solomon error correction codeword for the given data and divisor polynomials.""" 590 result = [0] * len(divisor) 591 for b in data: # Polynomial division 592 factor = b ^ result.pop(0) 593 result.append(0) 594 for (i, coef) in enumerate(divisor): 595 result[i] ^= QrCode._reed_solomon_multiply(coef, factor) 596 return result 597 598 599 @staticmethod 600 def _reed_solomon_multiply(x, y): 601 """Returns the product of the two given field elements modulo GF(2^8/0x11D). The arguments and result 602 are unsigned 8-bit integers. This could be implemented as a lookup table of 256*256 entries of uint8.""" 603 if x >> 8 != 0 or y >> 8 != 0: 604 raise ValueError("Byte out of range") 605 # Russian peasant multiplication 606 z = 0 607 for i in reversed(range(8)): 608 z = (z << 1) ^ ((z >> 7) * 0x11D) 609 z ^= ((y >> i) & 1) * x 610 assert z >> 8 == 0 611 return z 612 613 614 def _finder_penalty_count_patterns(self, runhistory): 615 """Can only be called immediately after a white run is added, and 616 returns either 0, 1, or 2. A helper function for _get_penalty_score().""" 617 n = runhistory[1] 618 assert n <= self._size * 3 619 core = n > 0 and (runhistory[2] == runhistory[4] == runhistory[5] == n) and runhistory[3] == n * 3 620 return (1 if (core and runhistory[0] >= n * 4 and runhistory[6] >= n) else 0) \ 621 + (1 if (core and runhistory[6] >= n * 4 and runhistory[0] >= n) else 0) 622 623 624 def _finder_penalty_terminate_and_count(self, currentruncolor, currentrunlength, runhistory): 625 """Must be called at the end of a line (row or column) of modules. A helper function for _get_penalty_score().""" 626 if currentruncolor: # Terminate black run 627 self._finder_penalty_add_history(currentrunlength, runhistory) 628 currentrunlength = 0 629 currentrunlength += self._size # Add white border to final run 630 self._finder_penalty_add_history(currentrunlength, runhistory) 631 return self._finder_penalty_count_patterns(runhistory) 632 633 634 def _finder_penalty_add_history(self, currentrunlength, runhistory): 635 if runhistory[0] == 0: 636 currentrunlength += self._size # Add white border to initial run 637 runhistory.appendleft(currentrunlength) 638 639 640 # ---- Constants and tables ---- 641 642 MIN_VERSION = 1 # The minimum version number supported in the QR Code Model 2 standard 643 MAX_VERSION = 40 # The maximum version number supported in the QR Code Model 2 standard 644 645 # For use in getPenaltyScore(), when evaluating which mask is best. 646 _PENALTY_N1 = 3 647 _PENALTY_N2 = 3 648 _PENALTY_N3 = 40 649 _PENALTY_N4 = 10 650 651 _ECC_CODEWORDS_PER_BLOCK = ( 652 # Version: (note that index 0 is for padding, and is set to an illegal value) 653 # 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 654 (None, 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 655 (None, 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 656 (None, 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 657 (None, 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 658 659 _NUM_ERROR_CORRECTION_BLOCKS = ( 660 # Version: (note that index 0 is for padding, and is set to an illegal value) 661 # 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 662 (None, 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 663 (None, 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 664 (None, 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 665 (None, 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 666 667 _MASK_PATTERNS = ( 668 (lambda x, y: (x + y) % 2 ), 669 (lambda x, y: y % 2 ), 670 (lambda x, y: x % 3 ), 671 (lambda x, y: (x + y) % 3 ), 672 (lambda x, y: (x // 3 + y // 2) % 2 ), 673 (lambda x, y: x * y % 2 + x * y % 3 ), 674 (lambda x, y: (x * y % 2 + x * y % 3) % 2 ), 675 (lambda x, y: ((x + y) % 2 + x * y % 3) % 2), 676 ) 677 678 679 # ---- Public helper enumeration ---- 680 681 class Ecc(object): 682 """The error correction level in a QR Code symbol. Immutable.""" 683 # Private constructor 684 def __init__(self, i, fb): 685 self.ordinal = i # (Public) In the range 0 to 3 (unsigned 2-bit integer) 686 self.formatbits = fb # (Package-private) In the range 0 to 3 (unsigned 2-bit integer) 687 688 # Public constants. Create them outside the class. 689 Ecc.LOW = Ecc(0, 1) # The QR Code can tolerate about 7% erroneous codewords 690 Ecc.MEDIUM = Ecc(1, 0) # The QR Code can tolerate about 15% erroneous codewords 691 Ecc.QUARTILE = Ecc(2, 3) # The QR Code can tolerate about 25% erroneous codewords 692 Ecc.HIGH = Ecc(3, 2) # The QR Code can tolerate about 30% erroneous codewords 693 694 695 696# ---- Data segment class ---- 697 698class QrSegment(object): 699 """A segment of character/binary/control data in a QR Code symbol. 700 Instances of this class are immutable. 701 The mid-level way to create a segment is to take the payload data 702 and call a static factory function such as QrSegment.make_numeric(). 703 The low-level way to create a segment is to custom-make the bit buffer 704 and call the QrSegment() constructor with appropriate values. 705 This segment class imposes no length restrictions, but QR Codes have restrictions. 706 Even in the most favorable conditions, a QR Code can only hold 7089 characters of data. 707 Any segment longer than this is meaningless for the purpose of generating QR Codes.""" 708 709 # ---- Static factory functions (mid level) ---- 710 711 @staticmethod 712 def make_bytes(data): 713 """Returns a segment representing the given binary data encoded in byte mode. 714 All input byte lists are acceptable. Any text string can be converted to 715 UTF-8 bytes (s.encode("UTF-8")) and encoded as a byte mode segment.""" 716 py3 = sys.version_info.major >= 3 717 if (py3 and isinstance(data, str)) or (not py3 and isinstance(data, unicode)): 718 raise TypeError("Byte string/list expected") 719 if not py3 and isinstance(data, str): 720 data = bytearray(data) 721 bb = _BitBuffer() 722 for b in data: 723 bb.append_bits(b, 8) 724 return QrSegment(QrSegment.Mode.BYTE, len(data), bb) 725 726 727 @staticmethod 728 def make_numeric(digits): 729 """Returns a segment representing the given string of decimal digits encoded in numeric mode.""" 730 if QrSegment.NUMERIC_REGEX.match(digits) is None: 731 raise ValueError("String contains non-numeric characters") 732 bb = _BitBuffer() 733 i = 0 734 while i < len(digits): # Consume up to 3 digits per iteration 735 n = min(len(digits) - i, 3) 736 bb.append_bits(int(digits[i : i + n]), n * 3 + 1) 737 i += n 738 return QrSegment(QrSegment.Mode.NUMERIC, len(digits), bb) 739 740 741 @staticmethod 742 def make_alphanumeric(text): 743 """Returns a segment representing the given text string encoded in alphanumeric mode. 744 The characters allowed are: 0 to 9, A to Z (uppercase only), space, 745 dollar, percent, asterisk, plus, hyphen, period, slash, colon.""" 746 if QrSegment.ALPHANUMERIC_REGEX.match(text) is None: 747 raise ValueError("String contains unencodable characters in alphanumeric mode") 748 bb = _BitBuffer() 749 for i in range(0, len(text) - 1, 2): # Process groups of 2 750 temp = QrSegment._ALPHANUMERIC_ENCODING_TABLE[text[i]] * 45 751 temp += QrSegment._ALPHANUMERIC_ENCODING_TABLE[text[i + 1]] 752 bb.append_bits(temp, 11) 753 if len(text) % 2 > 0: # 1 character remaining 754 bb.append_bits(QrSegment._ALPHANUMERIC_ENCODING_TABLE[text[-1]], 6) 755 return QrSegment(QrSegment.Mode.ALPHANUMERIC, len(text), bb) 756 757 758 @staticmethod 759 def make_segments(text): 760 """Returns a new mutable list of zero or more segments to represent the given Unicode text string. 761 The result may use various segment modes and switch modes to optimize the length of the bit stream.""" 762 if not (isinstance(text, str) or (sys.version_info.major < 3 and isinstance(text, unicode))): 763 raise TypeError("Text string expected") 764 765 # Select the most efficient segment encoding automatically 766 if text == "": 767 return [] 768 elif QrSegment.NUMERIC_REGEX.match(text) is not None: 769 return [QrSegment.make_numeric(text)] 770 elif QrSegment.ALPHANUMERIC_REGEX.match(text) is not None: 771 return [QrSegment.make_alphanumeric(text)] 772 else: 773 return [QrSegment.make_bytes(text.encode("UTF-8"))] 774 775 776 @staticmethod 777 def make_eci(assignval): 778 """Returns a segment representing an Extended Channel Interpretation 779 (ECI) designator with the given assignment value.""" 780 bb = _BitBuffer() 781 if assignval < 0: 782 raise ValueError("ECI assignment value out of range") 783 elif assignval < (1 << 7): 784 bb.append_bits(assignval, 8) 785 elif assignval < (1 << 14): 786 bb.append_bits(2, 2) 787 bb.append_bits(assignval, 14) 788 elif assignval < 1000000: 789 bb.append_bits(6, 3) 790 bb.append_bits(assignval, 21) 791 else: 792 raise ValueError("ECI assignment value out of range") 793 return QrSegment(QrSegment.Mode.ECI, 0, bb) 794 795 796 # ---- Constructor (low level) ---- 797 798 def __init__(self, mode, numch, bitdata): 799 """Creates a new QR Code segment with the given attributes and data. 800 The character count (numch) must agree with the mode and the bit buffer length, 801 but the constraint isn't checked. The given bit buffer is cloned and stored.""" 802 if not isinstance(mode, QrSegment.Mode): 803 raise TypeError("QrSegment.Mode expected") 804 if numch < 0: 805 raise ValueError() 806 807 # The mode indicator of this segment. Accessed through get_mode(). 808 self._mode = mode 809 810 # The length of this segment's unencoded data. Measured in characters for 811 # numeric/alphanumeric/kanji mode, bytes for byte mode, and 0 for ECI mode. 812 # Always zero or positive. Not the same as the data's bit length. 813 # Accessed through get_num_chars(). 814 self._numchars = numch 815 816 # The data bits of this segment. Accessed through get_data(). 817 self._bitdata = list(bitdata) # Make defensive copy 818 819 820 # ---- Accessor methods ---- 821 822 def get_mode(self): 823 """Returns the mode field of this segment.""" 824 return self._mode 825 826 def get_num_chars(self): 827 """Returns the character count field of this segment.""" 828 return self._numchars 829 830 def get_data(self): 831 """Returns a new copy of the data bits of this segment.""" 832 return list(self._bitdata) # Make defensive copy 833 834 835 # Package-private function 836 @staticmethod 837 def get_total_bits(segs, version): 838 """Calculates the number of bits needed to encode the given segments at 839 the given version. Returns a non-negative number if successful. Otherwise 840 returns None if a segment has too many characters to fit its length field.""" 841 result = 0 842 for seg in segs: 843 ccbits = seg.get_mode().num_char_count_bits(version) 844 if seg.get_num_chars() >= (1 << ccbits): 845 return None # The segment's length doesn't fit the field's bit width 846 result += 4 + ccbits + len(seg._bitdata) 847 return result 848 849 850 # ---- Constants ---- 851 852 # (Public) Describes precisely all strings that are encodable in numeric mode. 853 # To test whether a string s is encodable: ok = NUMERIC_REGEX.fullmatch(s) is not None 854 # A string is encodable iff each character is in the range 0 to 9. 855 NUMERIC_REGEX = re.compile(r"[0-9]*\Z") 856 857 # (Public) Describes precisely all strings that are encodable in alphanumeric mode. 858 # To test whether a string s is encodable: ok = ALPHANUMERIC_REGEX.fullmatch(s) is not None 859 # A string is encodable iff each character is in the following set: 0 to 9, A to Z 860 # (uppercase only), space, dollar, percent, asterisk, plus, hyphen, period, slash, colon. 861 862 ALPHANUMERIC_REGEX = re.compile(r"[A-Z0-9 $%*+./:-]*\Z") 863 864 # (Private) Dictionary of "0"->0, "A"->10, "$"->37, etc. 865 _ALPHANUMERIC_ENCODING_TABLE = {ch: i for (i, ch) in enumerate("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:")} 866 867 868 # ---- Public helper enumeration ---- 869 870 class Mode(object): 871 """Describes how a segment's data bits are interpreted. Immutable.""" 872 873 # Private constructor 874 def __init__(self, modebits, charcounts): 875 self._modebits = modebits # The mode indicator bits, which is a uint4 value (range 0 to 15) 876 self._charcounts = charcounts # Number of character count bits for three different version ranges 877 878 # Package-private method 879 def get_mode_bits(self): 880 """Returns an unsigned 4-bit integer value (range 0 to 15) representing the mode indicator bits for this mode object.""" 881 return self._modebits 882 883 # Package-private method 884 def num_char_count_bits(self, ver): 885 """Returns the bit width of the character count field for a segment in this mode 886 in a QR Code at the given version number. The result is in the range [0, 16].""" 887 return self._charcounts[(ver + 7) // 17] 888 889 # Public constants. Create them outside the class. 890 Mode.NUMERIC = Mode(0x1, (10, 12, 14)) 891 Mode.ALPHANUMERIC = Mode(0x2, ( 9, 11, 13)) 892 Mode.BYTE = Mode(0x4, ( 8, 16, 16)) 893 Mode.KANJI = Mode(0x8, ( 8, 10, 12)) 894 Mode.ECI = Mode(0x7, ( 0, 0, 0)) 895 896 897 898# ---- Private helper class ---- 899 900class _BitBuffer(list): 901 """An appendable sequence of bits (0s and 1s). Mainly used by QrSegment.""" 902 903 def append_bits(self, val, n): 904 """Appends the given number of low-order bits of the given 905 value to this buffer. Requires n >= 0 and 0 <= val < 2^n.""" 906 if n < 0 or val >> n != 0: 907 raise ValueError("Value out of range") 908 self.extend(((val >> i) & 1) for i in reversed(range(n))) 909 910 911def _get_bit(x, i): 912 """Returns true iff the i'th bit of x is set to 1.""" 913 return (x >> i) & 1 != 0 914 915 916 917class DataTooLongError(ValueError): 918 """Raised when the supplied data does not fit any QR Code version. Ways to handle this exception include: 919 - Decrease the error correction level if it was greater than Ecc.LOW. 920 - If the encode_segments() function was called with a maxversion argument, then increase 921 it if it was less than QrCode.MAX_VERSION. (This advice does not apply to the other 922 factory functions because they search all versions up to QrCode.MAX_VERSION.) 923 - Split the text data into better or optimal segments in order to reduce the number of bits required. 924 - Change the text or binary data to be shorter. 925 - Change the text to fit the character set of a particular segment mode (e.g. alphanumeric). 926 - Propagate the error upward to the caller/user.""" 927 pass 928