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