class QRCode:
''' supports Version 1, 2, 4, and 5 QR codes with quality L
encodes data in alphanumeric form '''
def __init__(self, version, dataStr):
'''QRCode.__init__(int, str) -> None
Initializes QRCode object '''
## Look-up tables
self.charCapacityDict = {'1L':25 ,'2L':47, '3L':77, '4L':114, '5L':154, '6L':195,
'1M':20 ,'2M':38, '3M':61, '4M':90, '5M':122, '6M':154,
'1Q':16 ,'2Q':29, '3Q':47, '4Q':67, '5Q':87, '6Q':108,
'1H':10 ,'2H':20, '3H':35, '4H':50, '5H':64, '6H':84}
self.bytesCapacityDict = {'1L':19 ,'2L':34, '3L':55, '4L':80, '5L':108, '6L':136,
'1M':16 ,'2M':28, '3M':44, '4M':64, '5M':86, '6M':108,
'1Q':13 ,'2Q':22, '3Q':34, '4Q':48, '5Q':62, '6Q':76,
'1H':9 ,'2H':16, '3H':26, '4H':36, '5H':46, '6H':60}
self.ECcodewords = {'1L': (7,1,19), '2L':(10,1,34) ,'3L':(15,1,55) , '4L':(20,1,80) ,'5L':(26,1,108)}
self.generatorPolynomials = {7:[0,87,229,146,149,238,102,21],
10:[0,251,67,46,61,118,70,64,94,32,45],
15:[0,8,183,61,91,202,37,51,58,237,140,124,5,99,105],
20:[0,17,60,79,50,61,163,26,187,202,180,221,225,83,239,156,164,212,212,188,190],
26:[0,173,125,158,2,103,182,118,17,145,201,111,28,165,53,161,21,245,142,13,102,48,227,153,145,218,70],
18:[0,215,234,158,94,184,97,118,170,79,187,152,148,252,179,5,98,96,153]}
self.alphanumEncode = {'0': '0', '1': '1', '2': '2', '3': '3', '4': '4',
'5': '5', '6': '6', '7': '7', '8': '8', '9': '9',
'A': '10', 'B': '11', 'C': '12', 'D': '13', 'E': '14',
'F': '15', 'G': '16', 'H': '17', 'I': '18', 'J': '19',
'K': '20', 'L': '21', 'M': '22', 'N': '23', 'O': '24',
'P': '25', 'Q': '26', 'R': '27', 'S': '28', 'T': '29',
'U': '30', 'V': '31', 'W': '32', 'X': '33', 'Y': '34',
'Z': '35', '$':'37', '%': '38', '*': '39', '+': '40',
'-': '41', '.': '42', '/': '43', ':': '44', ' ': '36'}
self.formatStrings = {'L0': '111011111000100','L1': '111001011110011',
'L2': '111110110101010','L3': '111100010011101',
'L4': '110011000101111','L5': '110001100011000',
'L6': '110110001000001','L7': '110100101110110'}
# raise AttributeError's for unsupported data types
if version not in range(1,6) or version == 3:
raise AttributeError
if self.charCapacityDict[str(version)+"L"] < len(dataStr):
raise AttributeError
# define attributes
self.dataStr = dataStr.upper()
self.error = 'L'
self.dataBits = ''
self.errorBits = ''
self.bits = ''
self.mask = 3
self.version = version
self.size = 17 + 4 * version
self.matrix = [[0 for i in range(self.size)] for j in range(self.size)]
self.reserved = []
# set up grid and encode data
self.encode_data()
self.encode_ec()
self.interleave_blocks()
self.add_finders()
self.add_reserved_areas()
self.add_alignment_patterns()
self.add_darkmodule()
self.add_timing()
self.place_data_bits()
self.add_format_string(self.mask)
self.apply_mask(self.mask)
def __str__(self):
'''str(QRCode) -> str
string method for QRCode object'''
out = "" # empty string
for r in range(self.size):
for c in range(self.size):
out += str(self.matrix[r][c]) + " "
out += "\n" # add new line at end of row
return out
def asy(self):
'''QRCode.asy() -> str
returns string containing asymptote code to draw QR code'''
# define output matrix qrdata in asymptote
out = "[asy]\nint[][] qrdata = {"
for r in range(self.size):
row = "{"
for c in range(self.size):
row += str(self.matrix[r][c]) + ","
row = row[:len(row)-1] # remove last comma
row += "},\n" # add newline and bracket
out += row
# add code to draw matrix
out += "};\nint side = " + str(self.size) + ";"
out += '''filldraw((-4, 4)--(-4,-(side+4))--(side+4, -(side+4))--(side+4, 4)--cycle, white);
for (int i = 0; i < side; ++i) {
for (int j = 0; j < side; ++j) {
if (qrdata[j][i] == 1) {
fill((i, -j)--(i+1,-j)--(i+1,-j-1)--(i,-j-1)--cycle, black);
}
}
}\n[/asy]'''
return out # return asymptote code as string
def encode_data(self):
'''QRCode.encode_data() -> str
Encodes alphanumeric characters as binary and returns it'''
# if not empty, don't allow new encoding
if self.dataBits != '':
return self.dataBits
# determine number of bits
size = 8*self.bytesCapacityDict[str(self.version) + self.error]
# add alphanumeric encoding indicator
self.dataBits += '0010' # alphanumeric mode
charCount = bin(len(self.dataStr))[2:]
# add chracter count indicator
self.dataBits += '0' * (9-len(charCount)) + charCount # char count indicator
# convet characters to binary and add to string
for i in range(0, len(self.dataStr)-1, 2):
first = int(self.alphanumEncode[self.dataStr[i]])
second = int(self.alphanumEncode[self.dataStr[i+1]])
score = bin(45 * first + second)[2:]
score = "0" * (11-len(score)) + score
self.dataBits += score
if len(self.dataStr) % 2 == 1:
first = int(self.alphanumEncode[self.dataStr[len(self.dataStr)-1]])
score = bin(first)[2:]
score = "0" * (6-len(score)) + score
self.dataBits += score
# add terminator
self.dataBits += '0' * min(4, size-len(self.dataBits))
# add padding
if len(self.dataBits) % 8 != 0:
self.dataBits += '0' * (8 - len(self.dataBits) % 8)
for i in range((size - len(self.dataBits))//8):
if i % 2 == 0:
self.dataBits += '0'*(8-len(bin(236)[2:])) + bin(236)[2:]
else:
self.dataBits += '0'*(8-len(bin(17)[2:])) + bin(17)[2:]
return self.dataBits
def encode_ec(self):
'''QRCode.encode_ec() -> str
Calculates error correction bits and returns them'''
# if already encoded, don't allow new encoding
if self.errorBits != "":
return self.errorBits
# get message coefficients
message = []
for i in range(0, len(self.dataBits), 8):
message.append(int(self.dataBits[i:i+8],base=2))
# get generator polynomial
generator = self.generatorPolynomials[self.ECcodewords[str(self.version)+self.error][0]]
# calculate error correction code words
ECcodewords = self.error_correction_coeff(message, generator)
# combine to form error correction string
for word in ECcodewords:
binary = bin(word)[2:]
self.errorBits += '0' * (8-len(binary)) + binary
if self.version > 1:
self.errorBits += '0' * 7
return self.errorBits
def convert_to_int(self, coeff):
'''QRCode.conver_to_int(int) -> int
Convert exponent alpha^coeff to integer newCoeff'''
exp_to_int = {-1:0, 0: 1, 1: 2, 2: 4, 3: 8, 4: 16, 5: 32, 6: 64, 7: 128, 8: 29, 9: 58, 10: 116,
11: 232, 12: 205, 13: 135, 14: 19, 15: 38, 16: 76, 17: 152, 18: 45, 19: 90, 20: 180,
21: 117, 22: 234, 23: 201, 24: 143, 25: 3, 26: 6, 27: 12, 28: 24, 29: 48, 30: 96,
31: 192, 32: 157, 33: 39, 34: 78, 35: 156, 36: 37, 37: 74, 38: 148, 39: 53, 40: 106,
41: 212, 42: 181, 43: 119, 44: 238, 45: 193, 46: 159, 47: 35, 48: 70, 49: 140, 50: 5,
51: 10, 52: 20, 53: 40, 54: 80, 55: 160, 56: 93, 57: 186, 58: 105, 59: 210, 60: 185,
61: 111, 62: 222, 63: 161, 64: 95, 65: 190, 66: 97, 67: 194, 68: 153, 69: 47, 70: 94,
71: 188, 72: 101, 73: 202, 74: 137, 75: 15, 76: 30, 77: 60, 78: 120, 79: 240, 80: 253,
81: 231, 82: 211, 83: 187, 84: 107, 85: 214, 86: 177, 87: 127, 88: 254, 89: 225, 90: 223,
91: 163, 92: 91, 93: 182, 94: 113, 95: 226, 96: 217, 97: 175, 98: 67, 99: 134, 100: 17,
101: 34, 102: 68, 103: 136, 104: 13, 105: 26, 106: 52, 107: 104, 108: 208, 109: 189, 110: 103,
111: 206, 112: 129, 113: 31, 114: 62, 115: 124, 116: 248, 117: 237, 118: 199, 119: 147, 120: 59,
121: 118, 122: 236, 123: 197, 124: 151, 125: 51, 126: 102, 127: 204, 128: 133, 129: 23, 130: 46,
131: 92, 132: 184, 133: 109, 134: 218, 135: 169, 136: 79, 137: 158, 138: 33, 139: 66, 140: 132,
141: 21, 142: 42, 143: 84, 144: 168, 145: 77, 146: 154, 147: 41, 148: 82, 149: 164, 150: 85,
151: 170, 152: 73, 153: 146, 154: 57, 155: 114, 156: 228, 157: 213, 158: 183, 159: 115, 160: 230,
161: 209, 162: 191, 163: 99, 164: 198, 165: 145, 166: 63, 167: 126, 168: 252, 169: 229, 170: 215,
171: 179, 172: 123, 173: 246, 174: 241, 175: 255, 176: 227, 177: 219, 178: 171, 179: 75, 180: 150,
181: 49, 182: 98, 183: 196, 184: 149, 185: 55, 186: 110, 187: 220, 188: 165, 189: 87, 190: 174,
191: 65, 192: 130, 193: 25, 194: 50, 195: 100, 196: 200, 197: 141, 198: 7, 199: 14, 200: 28,
201: 56, 202: 112, 203: 224, 204: 221, 205: 167, 206: 83, 207: 166, 208: 81, 209: 162, 210: 89,
211: 178, 212: 121, 213: 242, 214: 249, 215: 239, 216: 195, 217: 155, 218: 43, 219: 86, 220: 172,
221: 69, 222: 138, 223: 9, 224: 18, 225: 36, 226: 72, 227: 144, 228: 61, 229: 122, 230: 244,
231: 245, 232: 247, 233: 243, 234: 251, 235: 235, 236: 203, 237: 139, 238: 11, 239: 22, 240: 44,
241: 88, 242: 176, 243: 125, 244: 250, 245: 233, 246: 207, 247: 131, 248: 27, 249: 54, 250: 108,
251: 216, 252: 173, 253: 71, 254: 142, 255: 1}
newCoeff = []
for el in coeff:
newCoeff.append(exp_to_int[el])
return newCoeff
def convert_to_exp(self, coeff):
'''QRCode.convert_to_exp(int) -> int
COnvert int coeff to exponent alpha^newCoeff'''
int_to_exp = {0: -1, 1: 0, 2: 1, 3: 25, 4: 2, 5: 50, 6: 26, 7: 198, 8: 3, 9: 223, 10: 51,
11: 238, 12: 27, 13: 104, 14: 199, 15: 75, 16: 4, 17: 100, 18: 224, 19: 14, 20: 52,
21: 141, 22: 239, 23: 129, 24: 28, 25: 193, 26: 105, 27: 248, 28: 200, 29: 8, 30: 76,
31: 113, 32: 5, 33: 138, 34: 101, 35: 47, 36: 225, 37: 36, 38: 15, 39: 33, 40: 53,
41: 147, 42: 142, 43: 218, 44: 240, 45: 18, 46: 130, 47: 69, 48: 29, 49: 181, 50: 194,
51: 125, 52: 106, 53: 39, 54: 249, 55: 185, 56: 201, 57: 154, 58: 9, 59: 120, 60: 77,
61: 228, 62: 114, 63: 166, 64: 6, 65: 191, 66: 139, 67: 98, 68: 102, 69: 221, 70: 48,
71: 253, 72: 226, 73: 152, 74: 37, 75: 179, 76: 16, 77: 145, 78: 34, 79: 136, 80: 54,
81: 208, 82: 148, 83: 206, 84: 143, 85: 150, 86: 219, 87: 189, 88: 241, 89: 210, 90: 19,
91: 92, 92: 131, 93: 56, 94: 70, 95: 64, 96: 30, 97: 66, 98: 182, 99: 163, 100: 195,
101: 72, 102: 126, 103: 110, 104: 107, 105: 58, 106: 40, 107: 84, 108: 250, 109: 133,
110: 186, 111: 61, 112: 202, 113: 94, 114: 155, 115: 159, 116: 10, 117: 21, 118: 121, 119: 43, 120: 78,
121: 212, 122: 229, 123: 172, 124: 115, 125: 243, 126: 167, 127: 87, 128: 7, 129: 112, 130: 192,
131: 247, 132: 140, 133: 128, 134: 99, 135: 13, 136: 103, 137: 74, 138: 222, 139: 237, 140: 49,
141: 197, 142: 254, 143: 24, 144: 227, 145: 165, 146: 153, 147: 119, 148: 38, 149: 184, 150: 180,
151: 124, 152: 17, 153: 68, 154: 146, 155: 217, 156: 35, 157: 32, 158: 137, 159: 46, 160: 55,
161: 63, 162: 209, 163: 91, 164: 149, 165: 188, 166: 207, 167: 205, 168: 144, 169: 135, 170: 151,
171: 178, 172: 220, 173: 252, 174: 190, 175: 97, 176: 242, 177: 86, 178: 211, 179: 171, 180: 20,
181: 42, 182: 93, 183: 158, 184: 132, 185: 60, 186: 57, 187: 83, 188: 71, 189: 109, 190: 65,
191: 162, 192: 31, 193: 45, 194: 67, 195: 216, 196: 183, 197: 123, 198: 164, 199: 118, 200: 196,
201: 23, 202: 73, 203: 236, 204: 127, 205: 12, 206: 111, 207: 246, 208: 108, 209: 161, 210: 59,
211: 82, 212: 41, 213: 157, 214: 85, 215: 170, 216: 251, 217: 96, 218: 134, 219: 177, 220: 187,
221: 204, 222: 62, 223: 90, 224: 203, 225: 89, 226: 95, 227: 176, 228: 156, 229: 169, 230: 160,
231: 81, 232: 11, 233: 245, 234: 22, 235: 235, 236: 122, 237: 117, 238: 44, 239: 215, 240: 79,
241: 174, 242: 213, 243: 233, 244: 230, 245: 231, 246: 173, 247: 232, 248: 116, 249: 214, 250: 244,
251: 234, 252: 168, 253: 80, 254: 88, 255: 175}
newCoeff = []
for el in coeff:
newCoeff.append(int_to_exp[el])
return newCoeff
def error_correction_coeff(self, messageIntCoeff, generatorAlphaCoeff):
'''QRCOde.error_correction_coeff(list, list) -> list
Returns a list of error correction coefficients as integers'''
numSteps = len(messageIntCoeff)
# pad message with 0's
# pad generator polynomial with -1's
message = []
message.extend(messageIntCoeff)
message.extend([0] * (len(generatorAlphaCoeff)-1))
generator = []
generator.extend(generatorAlphaCoeff)
generator.extend([-1] * (len(messageIntCoeff)-1))
for steps in range(numSteps):
# find first term of message polynomial
firstCoeff = self.convert_to_exp([message[0]])[0]
# multiply generator polynomial by first term
result = []
for i in range(len(generator)):
if generator[i] != -1:
result.append((generator[i] + firstCoeff) % 255)
else:
result.append(-1)
# convert resulting polynomial to int coeffs
result = self.convert_to_int(result)
# XOR resulting polynomial with message
for i in range(len(message)):
message[i] = message[i] ^ result[i]
# set message polynomial to result
message.pop(0)
generator.pop(-1)
return message
def interleave_blocks(self):
'''QRCode.interleave_blocks() -> str
Combine data and error correction bits and return result'''
self.bits = self.dataBits + self.errorBits
return self.bits
def add_finders(self):
'''QRCode.add_finders() -> list
Add finders to matrix and return it'''
finderPattern = [[1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1],
[1, 0, 1, 1, 1, 0, 1],
[1, 0, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1]]
# add finder patterns to all three locations
for i in range(7):
for j in range(7):
# add patterns
finderModule = finderPattern[i][j]
self.matrix[i][j] = finderModule
self.matrix[self.size-7+i][j] = finderModule
self.matrix[i][self.size-7+j] = finderModule
# reserve areas in matrix with finders
self.reserved.append((i, j))
self.reserved.append((self.size-7+i, j))
self.reserved.append((i, self.size-7+j))
return self.matrix
def add_reserved_areas(self):
'''QRCode.add_reserved_areas() -> None
reserve seperator and format location'''
# vertical seperators
for i in range(8):
for j in [(0, 7), (0, self.size - 8), (self.size - 8, 7)]:
(r, c) = j
self.reserved.append((r+i, c))
# horizontal seperators
for i in range(8):
for j in [(7, 0), (self.size - 8, 0), (7, self.size - 8)]:
(r, c) = j
self.reserved.append((r, c+i))
# format info area
for i in range(9):
if (i, 8) not in self.reserved:
self.reserved.append((i, 8))
if (8, i) not in self.reserved:
self.reserved.append((8, i))
if (8, self.size-8+i) not in self.reserved:
self.reserved.append((8, self.size-8+i))
if (self.size-8+i, 8) not in self.reserved:
self.reserved.append((self.size-8+i, 8))
def add_alignment_patterns(self):
'''QRCode.add_alignment_patterns() -> list
Add alignment pattern to matrix and return it'''
alignPattern = [[1, 1, 1, 1, 1],
[1, 0, 0, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 0, 0, 1],
[1, 1, 1, 1, 1]]
# don't add alignment patterns to version 1
if self.version == 1:
return self.matrix
# add alignment pattern otherwise
for i in range(5):
for j in range(5):
row = 10 + self.version * 4 - 2
self.matrix[row + i][row + j] = alignPattern[i][j]
self.reserved.append((row + i, row + j))
return self.matrix
def add_timing(self):
'''QRCode.add_timing() -> list
Add timing patterns to matrix and return it'''
# define and add timing patterns
for i in range(8, self.size-8):
# add a 1 for dark squares
if i % 2 == 0:
self.matrix[6][i] = 1
self.matrix[i][6] = 1
# reserve all modules in timing pattern
self.reserved.append((6, i))
self.reserved.append((i, 6))
return self.matrix
def add_darkmodule(self):
'''QRCode.add_darkmodule() -> list
Add dark module to matrix and return it'''
self.matrix[self.size-8][8] = 1
self.reserved.append((self.size-8, 8))
return self.matrix
def place_data_bits(self):
'''QRCode.place_data_bits() -> list
Add data and error correction bits to matrix and return it'''
msgIndex = 0
for r in range(self.size-1, 0, -2):
# up a column
if r % 4 == 0:
if r <= 6:
r -= 1
for c in range(self.size-1,-1, -1):
# place bits
if (c, r) not in self.reserved:
# add a bit
self.matrix[c][r] = int(self.bits[msgIndex])
msgIndex += 1
if (c, r-1) not in self.reserved:
# add a bit
self.matrix[c][r-1] = int(self.bits[msgIndex])
msgIndex += 1
# down a column
elif r % 4 == 2:
if r <= 6:
r -= 1
for c in range(self.size):
# place bits
if (c, r) not in self.reserved:
# add a bit
self.matrix[c][r] = int(self.bits[msgIndex])
msgIndex += 1
if (c, r-1) not in self.reserved:
# add a bit
self.matrix[c][r-1] = int(self.bits[msgIndex])
msgIndex += 1
return self.matrix
def apply_mask(self, mask):
'''QRCode.apply_mask(int) -> list
Applies the given mask and returns the updated matrix'''
# loop through grid
for r in range(self.size):
for c in range(self.size):
# if it is not a reserved cell, ...
if (r,c) not in self.reserved:
# apply correct mask
if mask == 0 and (r + c) % 2 == 0:
self.matrix[r][c] = (self.matrix[r][c] + 1) % 2
elif mask == 1 and r % 2 == 0:
self.matrix[r][c] = (self.matrix[r][c] + 1) % 2
elif mask == 2 and c % 3 == 0:
self.matrix[r][c] = (self.matrix[r][c] + 1) % 2
elif mask == 3 and (r + c) % 3 == 0:
self.matrix[r][c] = (self.matrix[r][c] + 1) % 2
elif mask == 4 and (r//2 + c//3) % 2 == 0:
self.matrix[r][c] = (self.matrix[r][c] + 1) % 2
elif mask == 5 and (r*c) % 2 + (r * c) % 3 == 0:
self.matrix[r][c] = (self.matrix[r][c] + 1) % 2
elif mask == 6 and (r*c) %2 + ((r*c) % 3) % 2 == 0:
self.matrix[r][c] = (self.matrix[r][c] + 1) % 2
elif mask == 7 and (r+c) % 2 + ((r*c) % 3 ) % 3 == 0:
self.matrix[r][c] = (self.matrix[r][c] + 1) % 2
return self.matrix
def add_format_string(self, mask):
'''QRCode.add_format_string(int) -> list
Adds format string to matrix and returns it'''
# get format string
formatString = self.formatStrings['L' + str(mask)]
# add format string to grid
for i in range(7):
self.matrix[8][self.size-8+i] = int(formatString[i+7])
self.matrix[self.size-1-i][8] = int(formatString[i])
for i in range(6):
self.matrix[8][i] = int(formatString[i])
self.matrix[i][8] = int(formatString[14-i])
self.matrix[8][7] = int(formatString[6])
self.matrix[8][8] = int(formatString[7])
self.matrix[7][8] = int(formatString[8])
return self.matrix
def valid_str(string):
'''valid_str(str) -> bool
returns true if valid str, false otherwise'''
if len(string) == 0:
return False
if len(string) > 150:
print("Maximum lenght exceeded!")
return False
validChars = "1234567890QWERTYUIOPASDFGHJKLZXCVBNM$%*+-./: "
for ch in string:
if ch not in validChars:
print(ch + " is an invalid character!")
return False
return True
userInput = ''
while not valid_str(userInput):
print("Valid charcaters: 0-9, A-Z (captial only), $, %, *, +, -, ., /, and :")
print("Maximum Length: 150 characters.")
userInput = input("Please enter a string to encode using only valid characters: ")
qr = QRCode(2, userInput)
print("Your Asymptote code is below. Please go to aops.com/texer to render the asymptote code.")
print()
print(qr.asy())