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