# -*- coding: utf-8 -*-

#

# Copyright (c) 2016 - 2019 -- Lars Heuer - Semagia <http://www.semagia.com/>.

# All rights reserved.

#

# License: BSD License

#

"""\

QR Code and Micro QR Code encoder.

"QR Code" and "Micro QR Code" are registered trademarks of DENSO WAVE INCORPORATED.

"""

from __future__ import absolute_import, division

from operator import itemgetter, gt, lt, xor

from functools import partial, reduce

import re

import math

import codecs

from collections import namedtuple

from . import consts

_PY2 = False

try: # pragma: no cover

from itertools import zip_longest

str_type = str

numeric = int

except ImportError: # pragma: no cover

_PY2 = True

from itertools import izip_longest as zip_longest, imap as map

str_type = basestring

from numbers import Number

numeric = Number

str = unicode

range = xrange

import sys

_MAX_PENALTY_SCORE = sys.maxsize

del sys

__all__ = ('encode', 'encode_sequence', 'QRCodeError', 'VersionError',

'ModeError', 'ErrorLevelError', 'MaskError', 'DataOverflowError')

# <https://wiki.python.org/moin/PortingToPy3k/BilingualQuickRef#New_Style_Classes>

__metaclass__ = type

class QRCodeError(ValueError):

"""\

Generic QR Code error.

"""

class VersionError(QRCodeError):

"""\

Indicates errors related to the QR Code version.

"""

class ModeError(QRCodeError):

"""\

Indicates errors related to QR Code mode.

"""

class ErrorLevelError(QRCodeError):

"""\

Indicates errors related to QR Code error correction level.

"""

class MaskError(QRCodeError):

"""\

Indicates errors related to QR Code data mask.

"""

class DataOverflowError(QRCodeError):

"""\

Indicates a problem that the provided data does not fit into the

provided QR Code version or the data is too large in general.

"""

Code = namedtuple('Code', 'matrix version error mask segments')

def encode(content, error=None, version=None, mode=None, mask=None,

encoding=None, eci=False, micro=None, boost_error=True):

"""\

Creates a (Micro) QR Code.

See :py:func:`segno.make` for a detailed description of the parameters.

Contrary to ``make`` this function returns a named tuple:

``(matrix, version, error, mask, segments)``

Note that ``version`` is always an integer referring

to the values of the :py:mod:`segno.consts` constants. ``error`` is ``None``

iff a M1 QR Code was generated, otherwise it is always an integer.

:rtype: namedtuple

"""

version = normalize_version(version)

if not micro and micro is not None and version in consts.MICRO_VERSIONS:

raise VersionError('A Micro QR Code version ("{0}") is provided but '

'parameter "micro" is False'

.format(get_version_name(version)))

if micro and version is not None and version not in consts.MICRO_VERSIONS:

raise VersionError('Illegal Micro QR Code version "{0}"'

.format(get_version_name(version)))

error = normalize_errorlevel(error, accept_none=True)

mode = normalize_mode(mode)

if mode is not None and version is not None \

and not is_mode_supported(mode, version):

raise ModeError('Mode "{0}" is not available in version "{1}"'

.format(get_mode_name(mode), get_version_name(version)))

if error == consts.ERROR_LEVEL_H and (micro or version in consts.MICRO_VERSIONS):

raise ErrorLevelError('Error correction level "H" is not available for '

'Micro QR Codes')

if eci and (micro or version in consts.MICRO_VERSIONS):

raise VersionError('The ECI mode is not available for Micro QR Codes')

segments = prepare_data(content, mode, encoding, version)

guessed_version = find_version(segments, error, eci=eci, micro=micro)

if version is None:

version = guessed_version

elif guessed_version > version:

raise DataOverflowError('The provided data does not fit into version '

'"{0}". Proposal: version {1}'

.format(get_version_name(version),

get_version_name(guessed_version)))

if error is None and version != consts.VERSION_M1:

error = consts.ERROR_LEVEL_L

is_micro = version < 1

mask = normalize_mask(mask, is_micro)

return _encode(segments, error, version, mask, eci, boost_error)

def encode_sequence(content, error=None, version=None, mode=None,

mask=None, encoding=None, eci=False, boost_error=True,

symbol_count=None):

"""\

EXPERIMENTAL: Creates a sequence of QR Codes in Structured Append mode.

:return: Iterable of named tuples, see :py:func:`encode` for details.

"""

def one_item_segments(chunk, mode):

"""\

Creates a Segments sequence with one item.

"""

segs = Segments()

segs.add_segment(make_segment(chunk, mode=mode, encoding=encoding))

return segs

def divide_into_chunks(data, num):

k, m = divmod(len(data), num)

return [data[i * k + min(i, m):(i + 1) * k + min(i + 1, m)] for i in range(num)]

def calc_qrcode_bit_length(char_count, ver_range, mode, encoding=None,

is_eci=False, is_sa=False):

overhead = 4 # Mode indicator for QR Codes, only

# Number of bits in character count indicator

overhead += consts.CHAR_COUNT_INDICATOR_LENGTH[mode][ver_range]

if is_eci and mode == consts.MODE_BYTE and encoding != consts.DEFAULT_BYTE_ENCODING:

overhead += 4 # ECI indicator

overhead += 8 # ECI assignment no

if is_sa:

# 4 bit for mode, 4 bit for the position, 4 bit for total number of symbols

# 8 bit for parity data

overhead += 5 * 4

bits = 0

if mode == consts.MODE_NUMERIC:

num, remainder = divmod(char_count, 3)

bits += num * 10 + (4 if remainder == 1 else 7)

elif mode == consts.MODE_ALPHANUMERIC:

num, remainder = divmod(char_count, 2)

bits += num * 11 + (6 if remainder else 0)

elif mode == consts.MODE_BYTE:

bits += char_count * 8

elif mode == consts.MODE_KANJI:

bits += char_count * 13

return overhead + bits

def number_of_symbols_by_version(content, version, error, mode):

"""\

Returns the number of symbols for the provided version.

"""

length = len(content)

ver_range = version_range(version)

bit_length = calc_qrcode_bit_length(length, ver_range, mode, encoding,

is_eci=eci, is_sa=True)

capacity = consts.SYMBOL_CAPACITY[version][error]

# Initial result does not contain the overhead of SA mode for all QR Codes

cnt = int(math.ceil(bit_length / capacity))

# Overhead of SA mode for all QR Codes

bit_length += 5 * 4 * (cnt - 1) + (12 * (cnt - 1) if eci else 0)

return int(math.ceil(bit_length / capacity))

version = normalize_version(version)

if version is not None:

if version < 1:

raise VersionError('This function does not accept Micro QR Code versions. '

'Provided: "{0}"'.format(get_version_name(version)))

elif symbol_count is None:

raise ValueError('Please provide a QR Code version or the symbol count')

if symbol_count is not None and not 1 <= symbol_count <= 16:

raise ValueError('The symbol count must be in range 1 .. 16')

error = normalize_errorlevel(error, accept_none=True)

if error is None:

error = consts.ERROR_LEVEL_L

mode = normalize_mode(mode)

mask = normalize_mask(mask, is_micro=False)

segments = prepare_data(content, mode, encoding, version)

guessed_version = None

if symbol_count is None:

try:

# Try to find a version which fits without using Structured Append

guessed_version = find_version(segments, error, eci=eci, micro=False)

except DataOverflowError:

# Data does fit into a usual QR Code but ignore the error silently,

# guessed_version is None

pass

if guessed_version and guessed_version <= (version or guessed_version):

# Return iterable of size 1

return [_encode(segments, error=error, version=(version or guessed_version),

mask=mask, eci=eci, boost_error=boost_error)]

if len(segments.modes) > 1:

raise ValueError('This function cannot handle more than one mode (yet). Sorry.')

mode = segments.modes[0] # CHANGE iff more than one mode is supported!

# Creating one QR code failed or max_no is not None

if mode == consts.MODE_NUMERIC:

content = str(content)

if symbol_count is not None and len(content) < symbol_count:

raise ValueError('The content is not long enough to be divided into {0} symbols'.format(symbol_count))

sa_parity_data = calc_structured_append_parity(content)

num_symbols = symbol_count or 16

if version is not None:

num_symbols = number_of_symbols_by_version(content, version, error, mode)

if num_symbols > 16:

raise DataOverflowError('The data does not fit into Structured Append version {0}'.format(version))

chunks = divide_into_chunks(content, num_symbols)

if symbol_count is not None:

segments = one_item_segments(max(chunks, key=len), mode)

version = find_version(segments, error, eci=eci, micro=False, is_sa=True)

sa_info = partial(_StructuredAppendInfo, total=len(chunks) - 1,

parity=sa_parity_data)

return [_encode(one_item_segments(chunk, mode), error=error, version=version,

mask=mask, eci=eci, boost_error=boost_error,

sa_info=sa_info(i)) for i, chunk in enumerate(chunks)]

def _encode(segments, error, version, mask, eci, boost_error, sa_info=None):

"""\

Creates a (Micro) QR Code.

NOTE: This function does not check if the input is valid and does not belong

to the public API.

"""

is_micro = version < 1

sa_mode = sa_info is not None

buff = Buffer()

ver = version

ver_range = version

if not is_micro:

ver = None

ver_range = version_range(version)

if boost_error:

error = boost_error_level(version, error, segments, eci, is_sa=sa_mode)

if sa_mode:

# ISO/IEC 18004:2015(E) -- 8 Structured Append (page 59)

for i in sa_info[:3]:

buff.append_bits(i, 4)

buff.append_bits(sa_info.parity, 8)

# ISO/IEC 18004:2015(E) -- 7.4 Data encoding (page 22)

for segment in segments:

write_segment(buff, segment, ver, ver_range, eci)

capacity = consts.SYMBOL_CAPACITY[version][error]

# ISO/IEC 18004:2015(E) -- 7.4.9 Terminator (page 32)

write_terminator(buff, capacity, ver, len(buff))

# ISO/IEC 18004:2015(E) -- 7.4.10 Bit stream to codeword conversion (page 34)

write_padding_bits(buff, version, len(buff))

# ISO/IEC 18004:2015(E) -- 7.4.10 Bit stream to codeword conversion (page 34)

write_pad_codewords(buff, version, capacity, len(buff))

# ISO/IEC 18004:2015(E) -- 7.6 Constructing the final message codeword sequence (page 45)

buff = make_final_message(version, error, buff.toints())

# Matrix with timing pattern and reserved format / version regions

matrix = make_matrix(version)

# ISO/IEC 18004:2015 -- 6.3.3 Finder pattern (page 16)

add_finder_patterns(matrix, is_micro)

# ISO/IEC 18004:2015 -- 6.3.6 Alignment patterns (page 17)

add_alignment_patterns(matrix, version)

# ISO/IEC 18004:2015 -- 7.7 Codeword placement in matrix (page 46)

add_codewords(matrix, buff, version)

# ISO/IEC 18004:2015(E) -- 7.8.2 Data mask patterns (page 50)

# ISO/IEC 18004:2015(E) -- 7.8.3 Evaluation of data masking results (page 53)

mask = find_and_apply_best_mask(matrix, version, is_micro, mask)

# ISO/IEC 18004:2015(E) -- 7.9 Format information (page 55)

add_format_info(matrix, version, error, mask)

# ISO/IEC 18004:2015(E) -- 7.10 Version information (page 58)

add_version_info(matrix, version)

return Code(matrix, version, error, mask, segments)

def boost_error_level(version, error, segments, eci, is_sa=False):

"""\

Increases the error level if possible.

:param int version: Version constant.

:param int|None error: Error level constant or ``None``

:param Segments segments: Instance of :py:class:`Segments`

:param bool eci: Indicates if ECI designator should be written.

:param bool is_sa: Indicates if Structured Append mode ist used.

"""

if error not in (consts.ERROR_LEVEL_H, None) and len(segments) == 1:

levels = [consts.ERROR_LEVEL_L, consts.ERROR_LEVEL_M,

consts.ERROR_LEVEL_Q, consts.ERROR_LEVEL_H]

if version < 1:

levels.pop() # H isn't support by Micro QR Codes

if version < consts.VERSION_M4:

levels.pop() # Error level Q isn't supported by M2 and M3

data_length = segments.bit_length_with_overhead(version, eci, is_sa=is_sa)

for level in levels[levels.index(error)+1:]:

try:

found = consts.SYMBOL_CAPACITY[version][level] >= data_length

except KeyError:

break

if found:

error = level

return error

def write_segment(buff, segment, ver, ver_range, eci=False):

"""\

Writes a segment.

:param buff: The byte buffer.

:param _Segment segment: The segment to serialize.

:param ver: ``None`` if a QR Code is written, "M1", "M2", "M3", or "M4" if a

Micro QR Code is written.

:param ver_range: "M1", "M2", "M3", or "M4" if a Micro QR Code is written,

otherwise a constant representing a range of QR Code versions.

"""

mode = segment.mode

append_bits = buff.append_bits

# Write ECI header if requested

if eci and mode == consts.MODE_BYTE \

and segment.encoding != consts.DEFAULT_BYTE_ENCODING:

append_bits(consts.MODE_ECI, 4)

append_bits(get_eci_assignment_number(segment.encoding), 8)

if ver is None: # QR Code

append_bits(mode, 4)

elif ver > consts.VERSION_M1: # Micro QR Code (M1 has no mode indicator)

append_bits(consts.MODE_TO_MICRO_MODE_MAPPING[mode], ver + 3)

# Character count indicator

append_bits(segment.char_count,

consts.CHAR_COUNT_INDICATOR_LENGTH[mode][ver_range])

buff.extend(segment.bits)

def write_terminator(buff, capacity, ver, length):

"""\

Writes the terminator.

:param buff: The byte buffer.

:param capacity: Symbol capacity.

:param ver: ``None`` if a QR Code is written, "M1", "M2", "M3", or "M4" if a

Micro QR Code is written.

:param length: Length of the data bit stream.

"""

# ISO/IEC 18004:2015 -- 7.4.9 Terminator (page 32)

buff.extend([0] * min(capacity - length, consts.TERMINATOR_LENGTH[ver]))

def write_padding_bits(buff, version, length):

"""\

Writes padding bits if the data stream does not meet the codeword boundary.

:param buff: The byte buffer.

:param int length: Data stream length.

"""

# ISO/IEC 18004:2015(E) - 7.4.10 Bit stream to codeword conversion -- page 32

# [...]

# All codewords are 8 bits in length, except for the final data symbol

# character in Micro QR Code versions M1 and M3 symbols, which is 4 bits

# in length. If the bit stream length is such that it does not end at a

# codeword boundary, padding bits with binary value 0 shall be added after

# the final bit (least significant bit) of the data stream to extend it

# to the codeword boundary. [...]

if version not in (consts.VERSION_M1, consts.VERSION_M3):

buff.extend([0] * (8 - (length % 8)))

def write_pad_codewords(buff, version, capacity, length):

"""\

Writes the pad codewords iff the data does not fill the capacity of the

symbol.

:param buff: The byte buffer.

:param int version: The (Micro) QR Code version.

:param int capacity: The total capacity of the symbol (incl. error correction)

:param int length: Length of the data bit stream.

"""

# ISO/IEC 18004:2015(E) -- 7.4.10 Bit stream to codeword conversion (page 32)

# The message bit stream shall then be extended to fill the data capacity

# of the symbol corresponding to the Version and Error Correction Level, as

# defined in Table 8, by adding the Pad Codewords 11101100 and 00010001

# alternately. For Micro QR Code versions M1 and M3 symbols, the final data

# codeword is 4 bits long. The Pad Codeword used in the final data symbol

# character position in Micro QR Code versions M1 and M3 symbols shall be

# represented as 0000.

write = buff.extend

if version in (consts.VERSION_M1, consts.VERSION_M3):

write([0] * (capacity - length))

else:

pad_codewords = ((1, 1, 1, 0, 1, 1, 0, 0), (0, 0, 0, 1, 0, 0, 0, 1))

for i in range(capacity // 8 - length // 8):

write(pad_codewords[i % 2])

def add_finder_patterns(matrix, is_micro):

"""\

Adds the finder pattern(s) to the matrix.

QR Codes get three finder patterns, Micro QR Codes have just one finder

pattern.

ISO/IEC 18004:2015(E) -- 6.3.3 Finder pattern (page 16)

ISO/IEC 18004:2015(E) -- 6.3.4 Separator (page 17)

:param matrix: The matrix.

:param bool is_micro: Indicates if the matrix represents a Micro QR Code.

"""

add_finder_pattern(matrix, 0, 0) # Upper left corner

if not is_micro:

add_finder_pattern(matrix, 0, -7) # Upper right corner

add_finder_pattern(matrix, -7, 0) # Bottom left corner

# Finder pattern (includes separator around each side!)

_FINDER_PATTERN = ((0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0),

(0x0, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x0),

(0x0, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x1, 0x0),

(0x0, 0x1, 0x0, 0x1, 0x1, 0x1, 0x0, 0x1, 0x0),

(0x0, 0x1, 0x0, 0x1, 0x1, 0x1, 0x0, 0x1, 0x0),

(0x0, 0x1, 0x0, 0x1, 0x1, 0x1, 0x0, 0x1, 0x0),

(0x0, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x1, 0x0),

(0x0, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x0),

(0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0))

def add_finder_pattern(matrix, x, y):

"""\

Adds the finder pattern (black rect with black square) and

the finder separator (white horizontal line and white vertical line) to the

provided `matrix`.

ISO/IEC 18004:2015(E) -- 6.3.3 Finder pattern (page 16)

ISO/IEC 18004:2015(E) -- 6.3.4 Separator (page 17)

:param matrix: Matrix to add the finder into.

:param x: x-index of the first *black* module (upper left corner)

:param y: y-index of the first *black* module (upper left corner)

"""

fidx1, fidx2 = (0, 8) if y != 0 else (1, 9)

fyoff = 1 if x == 0 else 0

idx1, idx2 = (0, 8) if y > -1 else (y - 1, len(matrix))

x -= fyoff ^ 0x1

for i in range(8):

matrix[x + i][idx1:idx2] = _FINDER_PATTERN[fyoff + i][fidx1:fidx2]

def add_timing_pattern(matrix, is_micro):

"""\

Adds the (horizontal and vertical) timinig pattern to the provided `matrix`.

ISO/IEC 18004:2015(E) -- 6.3.5 Timing pattern (page 17)

:param matrix: Matrix to add the timing pattern into.

:param bool is_micro: Indicates if the timing pattern for a Micro QR Code

should be added.

"""

bit = 0x1

y, stop = (0, len(matrix)) if is_micro else (6, len(matrix) - 8)

for x in range(8, stop):

matrix[x][y] = bit

matrix[y][x] = bit

bit ^= 0x1

_ALIGNMENT_PATTERN = ((0x1, 0x1, 0x1, 0x1, 0x1),

(0x1, 0x0, 0x0, 0x0, 0x1),

(0x1, 0x0, 0x1, 0x0, 0x1),

(0x1, 0x0, 0x0, 0x0, 0x1),

(0x1, 0x1, 0x1, 0x1, 0x1))

def add_alignment_patterns(matrix, version):

"""\

Adds the adjustment patterns to the matrix. For versions < 2 this is a

no-op.

ISO/IEC 18004:2015(E) -- 6.3.6 Alignment patterns (page 17)

ISO/IEC 18004:2015(E) -- Annex E Position of alignment patterns (page 83)

"""

if version < 2:

return

matrix_size = len(matrix)

positions = consts.ALIGNMENT_POS[version - 2]

for pos_x in positions:

for pos_y in positions:

# Finder pattern?

if pos_x - 6 == 0 and (pos_y - 6 == 0 or pos_y + 7 == matrix_size) \

or pos_y - 6 == 0 and pos_x + 7 == matrix_size:

continue

row, col = pos_x - 2, pos_y - 2

for r in range(5):

matrix[row + r][col:col+5] = _ALIGNMENT_PATTERN[r]

def add_codewords(matrix, codewords, version):

"""\

Adds the codewords (data and error correction) to the provided matrix.

ISO/IEC 18004:2015(E) -- 7.7.3 Symbol character placement (page 46)

:param matrix: The matrix to add the codewords into.

:param codewords: Sequence of ints

"""

matrix_size = len(matrix)

is_micro = version < 1

# Necessary for M1 and M3: The algorithm would start at the upper right

# corner, see <https://github.com/heuer/segno/issues/36>

inc = 0 if version not in (consts.VERSION_M1, consts.VERSION_M3) else 2

idx = 0 # Pointer to the current codeword

# ISO/IEC 18004:2015(E) - page 48

# [...] An alternative method for placement in the symbol [...] is to regard

# the interleaved codeword sequence as a single bit stream, which is placed

# (starting with the most significant bit) in the two-module wide columns

# alternately upwards and downwards from the right to left of the symbol.

# [...]

for right in range(matrix_size - 1, 0, -2):

if not is_micro and right <= 6:

right -= 1

for vertical in range(matrix_size):

for z in range(2):

j = right - z

upwards = ((right + inc) & 2) == 0

if not is_micro:

upwards ^= j < 6

i = (matrix_size - 1 - vertical) if upwards else vertical

if matrix[i][j] == 0x2 and idx < len(codewords):

matrix[i][j] = codewords[idx]

idx += 1

if idx != len(codewords): # pragma: no cover

raise QRCodeError('Internal error: Adding codewords to matrix failed. '

'Added {0} of {1} codewords'.format(idx, len(codewords)))

def make_final_message(version, error, codewords):

"""\

Constructs the final message (codewords incl. error correction).

ISO/IEC 18004:2015(E) -- 7.6 Constructing the final message codeword sequence (page 45)

:param int version: (Micro) QR Code version constant.

:param int error: Error level constant.

:param codewords: An iterable sequence of codewords (ints)

:return: Byte buffer representing the final message.

"""

ec_infos = consts.ECC[version][error]

last_cw_is_four = version in (consts.VERSION_M1, consts.VERSION_M3)

data_blocks, error_blocks = make_blocks(ec_infos, codewords)

if last_cw_is_four:

# All codewords are 8 bit by default, M1 and M3 symbols use 4 bits

# to represent the last last codeword

# datablocks[0] is save since Micro QR Codes use just one datablock and

# one error block

data_blocks[0][-1] >>= 4

buff = Buffer()

append_int = partial(buff.append_bits, length=8)

# Write codewords

for i in range(max(info.num_data for info in ec_infos)):

for block in data_blocks:

if i >= len(block):

continue

if last_cw_is_four and i + 1 == len(block):

buff.append_bits(block[i], 4)

else:

append_int(block[i])

# Write error codewords

for i in range(max(info.num_total - info.num_data for info in ec_infos)):

for block in error_blocks:

if i >= len(block):

continue

append_int(block[i])

# ISO/IEC 18004:2015(E) -- 7.6 Constructing the final message codeword sequence

# [...] In certain QR Code versions, however, where the number of modules

# available for data and error correction codewords is not an exact multiple

# of 8, there may be a need for 3, 4 or 7 Remainder Bits to be appended to

# the final message bit stream in order to fill exactly the number of

# modules in the encoding region

remainder = 0 # Calculation: Number of Data modules - number of bits

if version in (2, 3, 4, 5, 6):

remainder = 7

elif version in (14, 15, 16, 17, 18, 19, 20, 28, 29, 30, 31, 32, 33, 34):

remainder = 3

elif version in (21, 22, 23, 24, 25, 26, 27):

remainder = 4

buff.extend(b'\0' * remainder)

return buff

def make_blocks(ec_infos, codewords):

"""\

Returns the data and error blocks.

:param ec_infos: Iterable of ECC information

:param codewords: Iterable of (integer) code words.

"""

data_blocks, error_blocks = [], []

offset = 0

for ec_info in ec_infos:

for i in range(ec_info.num_blocks):

block = codewords[offset:offset + ec_info.num_data]

data_blocks.append(block)

error_blocks.append(make_error_block(ec_info, block))

offset += ec_info.num_data

return data_blocks, error_blocks

def make_error_block(ec_info, data_block):

"""\

Creates the error code words for the provided data block.

:param ec_info: ECC information (number of blocks, number of code words etc.)

:param data_block: Iterable of (integer) code words.

"""

num_error_words = ec_info.num_total - ec_info.num_data

error_block = bytearray(data_block)

error_block.extend([0] * num_error_words)

gen = consts.GEN_POLY[num_error_words]

gen_log = consts.GALIOS_LOG

gen_exp = consts.GALIOS_EXP

len_data = len(data_block)

# Extended synthetic division, see http://research.swtch.com/field

for i in range(len_data):

coef = error_block[i]

if coef != 0: # log(0) is undefined

lcoef = gen_log[coef]

for j in range(num_error_words):

error_block[i + j + 1] ^= gen_exp[lcoef + gen[j]]

return error_block[len_data:]

def find_and_apply_best_mask(matrix, version, is_micro, proposed_mask=None):

"""\

Applies all mask patterns against the provided QR Code matrix and returns

the best matrix and best pattern.

ISO/IEC 18004:2015(E) -- 7.8.2 Data mask patterns (page 50)

ISO/IEC 18004:2015(E) -- 7.8.3 Evaluation of data masking results (page 53)

ISO/IEC 18004:2015(E) -- 7.8.3.1 Evaluation of QR Code symbols (page 53/54)

ISO/IEC 18004:2015(E) -- 7.8.3.2 Evaluation of Micro QR Code symbols (page 54/55)

:param matrix: A matrix.

:param int version: A version (Micro) QR Code version constant.

:param bool is_micro: Indicates if the matrix represents a Micro QR Code

:param proposed_mask: Optional int to indicate the preferred mask.

:rtype: tuple

:return: A tuple of the best matrix and best data mask pattern index.

"""

matrix_size = len(matrix)

# ISO/IEC 18004:2015 -- 7.8.3.1 Evaluation of QR Code symbols (page 53/54)

# The data mask pattern which results in the lowest penalty score shall

# be selected for the symbol.

is_better = lt

best_score = _MAX_PENALTY_SCORE

eval_mask = evaluate_mask

if is_micro:

# ISO/IEC 18004:2015(E) - 7.8.3.2 Evaluation of Micro QR Code symbols (page 54/55)

# The data mask pattern which results in the highest score shall be

# selected for the symbol.

is_better = gt

best_score = -1

eval_mask = evaluate_micro_mask

# Matrix to check if a module belongs to the encoding region

# or function patterns

function_matrix = make_matrix(version)

add_finder_patterns(function_matrix, is_micro)

add_alignment_patterns(function_matrix, version)

if not is_micro:

function_matrix[-8][8] = 0x1

def is_encoding_region(i, j):

return function_matrix[i][j] == 0x2

mask_patterns = get_data_mask_functions(is_micro)

# If the user supplied a mask pattern, the evaluation step is skipped

if proposed_mask is not None:

apply_mask(matrix, mask_patterns[proposed_mask], matrix_size,

is_encoding_region)

return proposed_mask

for mask_number, mask_pattern in enumerate(mask_patterns):

apply_mask(matrix, mask_pattern, matrix_size, is_encoding_region)

# NOTE: DO NOT add format / version info in advance of evaluation

# See ISO/IEC 18004:2015(E) -- 7.8. Data masking (page 50)

score = eval_mask(matrix, matrix_size)

if is_better(score, best_score):

best_score = score

best_pattern = mask_number

# Undo mask

apply_mask(matrix, mask_pattern, matrix_size, is_encoding_region)

apply_mask(matrix, mask_patterns[best_pattern], matrix_size, is_encoding_region)

return best_pattern

def apply_mask(matrix, mask_pattern, matrix_size, is_encoding_region):

"""\

Applies the provided mask pattern on the `matrix`.

ISO/IEC 18004:2015(E) -- 7.8.2 Data mask patterns (page 50)

:param tuple matrix: A tuple of bytearrays

:param mask_pattern: A mask pattern (a function)

:param int matrix_size: width or height of the matrix

:param is_encoding_region: A function which returns ``True`` iff the

row index / col index belongs to the data region.

"""

for i in range(matrix_size):

for j in range(matrix_size):

if is_encoding_region(i, j):

matrix[i][j] ^= mask_pattern(i, j)

def evaluate_mask(matrix, matrix_size):

"""\

Evaluates the provided `matrix` of a QR code.

ISO/IEC 18004:2015(E) -- 7.8.3 Evaluation of data masking results (page 53)

:param matrix: The matrix to evaluate

:param matrix_size: The width (or height) of the matrix.

:return int: The penalty score of the matrix.

"""

return score_n1(matrix, matrix_size) + score_n2(matrix, matrix_size) \

+ score_n3(matrix, matrix_size) + score_n4(matrix, matrix_size)

def score_n1(matrix, matrix_size):

"""\

Implements the penalty score feature 1.

ISO/IEC 18004:2015(E) -- 7.8.3 Evaluation of data masking results - Table 11 (page 54)

============================================ ======================== ======

Feature Evaluation condition Points

============================================ ======================== ======

Adjacent modules in row/column in same color No. of modules = (5 + i) N1 + i

============================================ ======================== ======

N1 = 3

:param matrix: The matrix to evaluate

:param matrix_size: The width (or height) of the matrix.

:return int: The penalty score (feature 1) of the matrix.

"""

score = 0

for i in range(matrix_size):

prev_bit_row, prev_bit_col = -1, -1

row_counter, col_counter = 0, 0

for j in range(matrix_size):

# Row-wise

bit = matrix[i][j]

if bit == prev_bit_row:

row_counter += 1

else:

if row_counter >= 5:

score += row_counter - 2 # N1 == 3

row_counter = 1

prev_bit_row = bit

# Col-wise

bit = matrix[j][i]

if bit == prev_bit_col:

col_counter += 1

else:

if col_counter >= 5:

score += col_counter - 2 # N1 == 3

col_counter = 1

prev_bit_col = bit

if row_counter >= 5:

score += row_counter - 2 # N1 == 3

if col_counter >= 5:

score += col_counter - 2 # N1 == 3

return score

def score_n2(matrix, matrix_size):

"""\

Implements the penalty score feature 2.

ISO/IEC 18004:2015(E) -- 7.8.3 Evaluation of data masking results - Table 11 (page 54)

============================== ==================== ===============

Feature Evaluation condition Points

============================== ==================== ===============

Block of modules in same color Block size = m × n N2 ×(m-1)×(n-1)

============================== ==================== ===============

N2 = 3

:param matrix: The matrix to evaluate

:param matrix_size: The width (or height) of the matrix.

:return int: The penalty score (feature 2) of the matrix.

"""

score = 0

for i in range(matrix_size - 1):

for j in range(matrix_size - 1):

bit = matrix[i][j]

if bit == matrix[i][j + 1] and bit == matrix[i + 1][j] \

and bit == matrix[i + 1][j + 1]:

score += 1

return score * 3 # N2 == 3

_N3_PATTERN = bytearray((0x1, 0x0, 0x1, 0x1, 0x1, 0x0, 0x1))

def score_n3(matrix, matrix_size):

"""\

Implements the penalty score feature 3.

ISO/IEC 18004:2015(E) -- 7.8.3 Evaluation of data masking results - Table 11 (page 54)

========================================= ======================== ======

Feature Evaluation condition Points

========================================= ======================== ======

1 : 1 : 3 : 1 : 1 ratio Existence of the pattern N3

(dark:light:dark:light:dark) pattern in

row/column, preceded or followed by light

area 4 modules wide

========================================= ======================== ======

N3 = 40

:param matrix: The matrix to evaluate

:param matrix_size: The width (or height) of the matrix.

:return int: The penalty score (feature 3) of the matrix.

"""

def is_match(seq, start, end):

start = max(start, 0)

end = min(end, matrix_size)

for i in range(start, end):

if seq[i] == 0x1:

return False

return True

def find_occurrences(seq):

count = 0

idx = seq.find(_N3_PATTERN)

while idx != -1:

offset = idx + 7

if is_match(seq, idx - 4, idx) or is_match(seq, offset, offset + 4):

count += 1

else:

# Found no / not enough light patterns, start at next possible

# match:

# v

# dark light dark dark dark light dark

# ^

offset = idx + 4

idx = seq.find(_N3_PATTERN, offset)

return count

score = 0

for i in range(matrix_size):

score += find_occurrences(matrix[i])

score += find_occurrences(bytearray([matrix[y][i] for y in range(matrix_size)]))

return score * 40 # N3 = 40

def score_n4(matrix, matrix_size):

"""\

Implements the penalty score feature 4.

ISO/IEC 18004:2015(E) -- 7.8.3 Evaluation of data masking results - Table 11 (page 54)

=========================================== ==================================== ======

Feature Evaluation condition Points

=========================================== ==================================== ======

Proportion of dark modules in entire symbol 50 × (5 × k)% to 50 × (5 × (k + 1))% N4 × k

=========================================== ==================================== ======

N4 = 10

:param matrix: The matrix to evaluate

:param matrix_size: The width (or height) of the matrix.

:return int: The penalty score (feature 4) of the matrix.

"""

dark_modules = sum(map(sum, matrix))

total_modules = matrix_size ** 2

k = int(abs(dark_modules * 2 - total_modules) * 10 // total_modules)

return 10 * k # N4 = 10

def evaluate_micro_mask(matrix, matrix_size):

"""\

Evaluates the provided `matrix` of a Micro QR code.

ISO/IEC 18004:2015(E) -- 7.8.3.2 Evaluation of Micro QR Code symbols (page 54)

:param matrix: The matrix to evaluate

:param matrix_size: The width (or height) of the matrix.

:return int: The penalty score of the matrix.

"""

sum1 = sum(matrix[i][-1] == 0x1 for i in range(1, matrix_size))

sum2 = sum(matrix[-1][i] == 0x1 for i in range(1, matrix_size))

return sum1 * 16 + sum2 if sum1 <= sum2 else sum2 * 16 + sum1

def calc_format_info(version, error, mask_pattern):

"""\

Returns the format information for the provided error level and mask patttern.

ISO/IEC 18004:2015(E) -- 7.9 Format information (page 55)

ISO/IEC 18004:2015(E) -- Table C.1 — Valid format information bit sequences (page 80)

:param int version: Version constant

:param int error: Error level constant.

:param int mask_pattern: Mask pattern number.

"""

fmt = mask_pattern

if version > 0:

if error == consts.ERROR_LEVEL_L:

fmt += 0x08

elif error == consts.ERROR_LEVEL_H:

fmt += 0x10

elif error == consts.ERROR_LEVEL_Q:

fmt += 0x18

format_info = consts.FORMAT_INFO[fmt]

else:

fmt += consts.ERROR_LEVEL_TO_MICRO_MAPPING[version][error] << 2

format_info = consts.FORMAT_INFO_MICRO[fmt]

return format_info

def add_format_info(matrix, version, error, mask_pattern):

"""\

Adds the format information into the provided matrix.

ISO/IEC 18004:2015(E) -- 7.9 Format information (page 55)

ISO/IEC 18004:2015(E) -- 7.9.1 QR Code symbols

ISO/IEC 18004:2015(E) -- 7.9.2 Micro QR Code symbols

:param matrix: The matrix.

:param int version: Version constant

:param int error: Error level constant.

:param int mask_pattern: Mask pattern number.

"""

# 14: most significant bit

# 0: least significant bit

#

# QR Code format info: Micro QR format info

# col 0 col 7 col matrix[-1] col 1

# 0 | | [ ]

# 1 0

# 2 1

# 3 2

# 4 3

# 5 4

# [ ] 5

# 6 6

# 14 13 12 11 10 9 [ ] 8 7 ... 7 6 5 4 3 2 1 0 14 13 12 11 10 9 8 7

#

# ...

# [ ] (dark module)

# 8

# 9

# 10

# 11

# 12

# 13

# 14

is_micro = version < 1

format_info = calc_format_info(version, error, mask_pattern)

offset = int(is_micro)

for i in range(8):

bit = (format_info >> i) & 0x01

if i == 6 and not is_micro: # Timing pattern

offset += 1

# vertical row, upper left corner

matrix[i + offset][8] = bit

if not is_micro:

# horizontal row, upper right corner

matrix[8][-1 - i] = bit

offset = int(is_micro)

for i in range(8):

bit = (format_info >> (14 - i)) & 0x01

if i == 6 and not is_micro: # Timing pattern

offset = 1

# horizontal row, upper left corner

matrix[8][i + offset] = bit