Created
December 1, 2019 22:28
-
-
Save chromia/5aebd459a5cda2a6620f9944b1ad7f26 to your computer and use it in GitHub Desktop.
「大石泉すき」と表示するQRコードの生成プログラム
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from PIL import Image | |
from enum import Enum | |
""" | |
「大石泉すき」と表示するQRコードを作るプログラム | |
QRコードのバージョン: 2-H(44,16,14)のみ | |
対応機能: 漢字モードのみ | |
動かすには別途Pillowが必要です。-> pip install Pillow | |
author : chromia<chromia@outlook.jp> | |
license : Unlicense | |
""" | |
map_e2i = {} | |
map_i2e = {} | |
SIZE = 25 # 1辺のモジュール数 | |
N_DATA = 44 # データ容量 | |
K_DATA = 16 # 誤り訂正符号を除く実データ容量 | |
MASK_TARGET_BITS = N_DATA * 8 # 符号化領域(=マスク対象部)の合計ビット数 | |
FORMAT_START_BIT = MASK_TARGET_BITS + 7 # 形式番号開始位置のビット番号 | |
# RS誤り訂正符号の生成多項式係数(αの指数部) | |
COEFFICIENT_D16 = [0, 168, 223, 200, 104, 224, 234, 108, 180, 110, | |
190, 195, 147, 205, 27, 232, 201, 21, 43, 245, | |
87, 42, 195, 212, 119, 242, 37, 9, 123] | |
N_BCH = 15 # 形式情報の総ビット数 | |
K_BCH = 5 # BCHの誤り訂正対象ビット数 | |
# BCH(15,5)の生成多項式係数 | |
COEFFICIENT_BCH = [1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1] | |
# QRシンボルレイアウト(今回はバージョンが決まっているので決め打ちで準備) | |
BBB = -1 # 暗モジュール | |
___ = -2 # 明モジュール | |
layout_ver2 = [ | |
[BBB, BBB, BBB, BBB, BBB, BBB, BBB, ___, 373, 248, 247, 246, 245, 152, 151, 150, 149, ___, BBB, BBB, BBB, BBB, BBB, BBB, BBB], | |
[BBB, ___, ___, ___, ___, ___, BBB, ___, 372, 250, 249, 244, 243, 154, 153, 148, 147, ___, BBB, ___, ___, ___, ___, ___, BBB], | |
[BBB, ___, BBB, BBB, BBB, ___, BBB, ___, 371, 252, 251, 242, 241, 156, 155, 146, 145, ___, BBB, ___, BBB, BBB, BBB, ___, BBB], | |
[BBB, ___, BBB, BBB, BBB, ___, BBB, ___, 370, 254, 253, 240, 239, 158, 157, 144, 143, ___, BBB, ___, BBB, BBB, BBB, ___, BBB], | |
[BBB, ___, BBB, BBB, BBB, ___, BBB, ___, 369, 256, 255, 238, 237, 160, 159, 142, 141, ___, BBB, ___, BBB, BBB, BBB, ___, BBB], | |
[BBB, ___, ___, ___, ___, ___, BBB, ___, 368, 258, 257, 236, 235, 162, 161, 140, 139, ___, BBB, ___, ___, ___, ___, ___, BBB], | |
[BBB, BBB, BBB, BBB, BBB, BBB, BBB, ___, BBB, ___, BBB, ___, BBB, ___, BBB, ___, BBB, ___, BBB, BBB, BBB, BBB, BBB, BBB, BBB], | |
[___, ___, ___, ___, ___, ___, ___, ___, 367, 260, 259, 234, 233, 164, 163, 138, 137, ___, ___, ___, ___, ___, ___, ___, ___], | |
[359, 360, 361, 362, 363, 364, BBB, 365, 366, 262, 261, 232, 231, 166, 165, 136, 135, 366, 367, 368, 369, 370, 371, 372, 373], | |
[344, 343, 342, 341, 312, 311, ___, 310, 309, 264, 263, 230, 229, 168, 167, 134, 133, 87, 86, 85, 84, 33, 32, 31, 30], | |
[346, 345, 340, 339, 314, 313, BBB, 308, 307, 266, 265, 228, 227, 170, 169, 132, 131, 89, 88, 83, 82, 35, 34, 29, 28], | |
[348, 347, 338, 337, 316, 315, ___, 306, 305, 268, 267, 226, 225, 172, 171, 130, 129, 91, 90, 81, 80, 37, 36, 27, 26], | |
[350, 349, 336, 335, 318, 317, BBB, 304, 303, 270, 269, 224, 223, 174, 173, 128, 127, 93, 92, 79, 78, 39, 38, 25, 24], | |
[352, 351, 334, 333, 320, 319, ___, 302, 301, 272, 271, 222, 221, 176, 175, 126, 125, 95, 94, 77, 76, 41, 40, 23, 22], | |
[354, 353, 332, 331, 322, 321, BBB, 300, 299, 274, 273, 220, 219, 178, 177, 124, 123, 97, 96, 75, 74, 43, 42, 21, 20], | |
[356, 355, 330, 329, 324, 323, ___, 298, 297, 276, 275, 218, 217, 180, 179, 122, 121, 99, 98, 73, 72, 45, 44, 19, 18], | |
[358, 357, 328, 327, 326, 325, BBB, 296, 295, 278, 277, 216, 215, 182, 181, 120, BBB, BBB, BBB, BBB, BBB, 47, 46, 17, 16], | |
[___, ___, ___, ___, ___, ___, ___, ___, BBB, 280, 279, 214, 213, 184, 183, 119, BBB, ___, ___, ___, BBB, 49, 48, 15, 14], | |
[BBB, BBB, BBB, BBB, BBB, BBB, BBB, ___, 365, 282, 281, 212, 211, 186, 185, 118, BBB, ___, BBB, ___, BBB, 51, 50, 13, 12], | |
[BBB, ___, ___, ___, ___, ___, BBB, ___, 364, 284, 283, 210, 209, 188, 187, 117, BBB, ___, ___, ___, BBB, 53, 52, 11, 10], | |
[BBB, ___, BBB, BBB, BBB, ___, BBB, ___, 363, 286, 285, 208, 207, 190, 189, 116, BBB, BBB, BBB, BBB, BBB, 55, 54, 9, 8], | |
[BBB, ___, BBB, BBB, BBB, ___, BBB, ___, 362, 288, 287, 206, 205, 192, 191, 115, 114, 101, 100, 71, 70, 57, 56, 7, 6], | |
[BBB, ___, BBB, BBB, BBB, ___, BBB, ___, 361, 290, 289, 204, 203, 194, 193, 113, 112, 103, 102, 69, 68, 59, 58, 5, 4], | |
[BBB, ___, ___, ___, ___, ___, BBB, ___, 360, 292, 291, 202, 201, 196, 195, 111, 110, 105, 104, 67, 66, 61, 60, 3, 2], | |
[BBB, BBB, BBB, BBB, BBB, BBB, BBB, ___, 359, 294, 293, 200, 199, 198, 197, 109, 108, 107, 106, 65, 64, 63, 62, 1, 0] | |
] | |
class BitStream: | |
# ビットを蓄積するための簡易クラス | |
# こういうの標準で欲しい…… | |
def __init__(self, limit=None): | |
self.bytes = [] | |
self.bit_num = 0 | |
self.limit = limit | |
def _add_bit(self, bit): # 1ビット入れる | |
if self.limit: | |
if self.bit_num >= self.limit: | |
return | |
index_byte = self.bit_num // 8 | |
index_bit = 7 - self.bit_num % 8 | |
if index_bit == 7: | |
self.bytes.append(0) | |
mask = 1 << index_bit | |
if bit: | |
self.bytes[index_byte] |= mask | |
self.bit_num += 1 | |
def add_bits(self, bit_list, cancellable=False): # 任意の数のビット入れる | |
if not cancellable and self.limit: | |
if self.bit_num + len(bit_list) > self.limit: | |
raise MemoryError('容量がたりません') | |
for b in bit_list: | |
self._add_bit(b) | |
def add_integer(self, n, length): # 整数を指定のビット数で入れる | |
bits = [(n & (1 << i)) >> i for i in range(length-1, -1, -1)] | |
self.add_bits(bits) | |
def get_bit(self, index): | |
index_byte = index // 8 | |
index_bit = 7 - (index % 8) | |
mask = 1 << index_bit | |
return (self.bytes[index_byte] & mask) >> index_bit | |
def fill_zero(self): # バイト境界まで0パディング | |
self.bit_num = (self.bit_num + 7) & ~7 | |
def clear_limit(self): | |
self.limit = None | |
def init_tables(): | |
# GF(2^8)における a^e (e=0..254) に対する数値表現nの対応表を求める | |
map_e2i[0] = 1 | |
# a^e 0, 1, 2, 3, 4, 5, 6, 7, 8 | |
buffer = [1, 0, 0, 0, 0, 0, 0, 0, 0] | |
for e in range(1, 255): | |
# バッファを右シフトする | |
buffer = [0] + buffer[0:8] | |
if buffer[8]: | |
buffer[8] = 0 | |
# a^8が発生したのでa^4+a^3+a^2+a^0に置換する | |
added = [1, 0, 1, 1, 1] | |
for i in range(len(added)): | |
# GF(2)において桁同士の加算はXORに等しい(そして繰り上げもない) | |
buffer[i] = buffer[i] ^ added[i] | |
n = sum([buffer[i] * (2 ** i) for i in range(8)]) | |
map_e2i[e] = n | |
# 逆引き辞書を求める ( n -> e ) | |
for k, v in map_e2i.items(): | |
map_i2e[v] = k | |
def convert_char(c): | |
s = c.encode('shift_jis') # 文字をShift-JISでエンコードされたbytes型に変換 | |
i = int.from_bytes(s, 'big') # 数値に変換 | |
if 0x8140 <= i <= 0x9FFC: | |
i -= 0x8140 | |
elif 0xE040 <= i <= 0xEBBF: | |
i -= 0xC140 | |
else: | |
raise ValueError(f'サポートしてない文字です: {c}') | |
hi, lo = i // 256, i % 256 # 上位バイトと下位バイトに分離 | |
code = hi * 0xC0 + lo | |
b = f'{code:013b}' # 13桁の2進数文字列に変換 | |
return [int(k) for k in b] # 数値(0or1)のリストに変換して返す | |
def calc_rs_mod(data, n, k, coefficients): | |
# Reed-Solomon符号を求める | |
# 計算用バッファ(ビット表現値を格納する) | |
box = data + [0] * (n - k) | |
# オフセットを変えつつ(シフトしつつ)、誤り訂正符号を求める | |
for i in range(k): | |
# 最大次数項の係数を取り出す | |
mul = box[i] | |
if mul == 0: | |
continue | |
# 指数形式に直す | |
mul_exp = map_i2e[mul] | |
# 生成多項式の各係数に掛ける | |
for j in range(0, n - k + 1): | |
# 累乗どうしの積は指数の足し算 | |
sum_exp = (mul_exp + coefficients[j]) % 255 # α^255 = 1を利用して指数を255未満に維持する(辞書で引けるように) | |
# 数値に換算する | |
sum_num = map_e2i[sum_exp] | |
# 係数を引き算する(ただしGF(2)の特性により減算はXORに等しい) | |
box[i + j] ^= sum_num | |
return box[-(n-k):] | |
def calc_bch_mod(data, n, k, coefficients): | |
# BCHの訂正ビットを求める | |
# RSとの違いは全ての項の係数が0か1に限られるので、指数を用いる必要がない点 | |
# 計算用バッファ(係数を格納する) | |
box = data + [0] * (n - k) | |
# オフセットを変えつつ(シフトしつつ)、誤り訂正符号を求める | |
for i in range(k): | |
# 最大次数項の係数を取り出す | |
if box[i] == 0: | |
continue | |
for j in range(0, n - k + 1): | |
# 係数を引き算する(XOR) | |
box[i + j] ^= coefficients[j] | |
return box[-(n-k):] | |
masks = [ # 8種類のマスク(順番は規格と一致) | |
lambda i, j: (i+j) % 2 == 0, | |
lambda i, j: i % 2 == 0, | |
lambda i, j: j % 3 == 0, | |
lambda i, j: (i+j) % 3 == 0, | |
lambda i, j: ((i // 2) + (j // 3)) % 2 == 0, | |
lambda i, j: ((i*j) % 2) + ((i*j) % 3) == 0, | |
lambda i, j: (((i*j) % 2) + ((i*j) % 3)) % 2 == 0, | |
lambda i, j: (((i+j) % 2) + ((i*j) % 3)) % 2 == 0 | |
] | |
class Color(Enum): | |
TBD = -1 | |
WHITE = 0 | |
BLACK = 1 | |
class MaskGridCell: | |
def __init__(self, maskable, color): | |
self.maskable = maskable | |
self.color = color | |
def eval_mask1(grid): | |
# 評価1: 同行・同列の隣接モジュール (5個以上連続で失点) | |
def eval_sub(accessor): | |
penalty_n1 = 3 | |
minus = 0 | |
for i in range(SIZE): | |
last_color = accessor(i, 0) | |
count = 1 | |
for j in range(1, SIZE): | |
current_cell = accessor(i, j) | |
if not current_cell.maskable: | |
continue | |
if current_cell.color == last_color: | |
count += 1 | |
else: | |
if count >= 5: | |
minus += penalty_n1 + (count - 5) | |
last_color = current_cell.color | |
count = 1 | |
return minus | |
minus_row = eval_sub(lambda i, j: grid[i][j]) # 行を見る | |
minus_col = eval_sub(lambda i, j: grid[j][i]) # 列を見る | |
return minus_row + minus_col | |
def eval_mask2(grid): | |
# 評価2 : 2x2のブロック (1つにつき失点) | |
penalty_n2 = 3 | |
minus = 0 | |
for i in range(SIZE-1): | |
for j in range(SIZE-1): | |
c1 = grid[i][j].color | |
c2 = grid[i+1][j].color | |
c3 = grid[i][j+1].color | |
c4 = grid[i+1][j+1].color | |
if c1 == Color.TBD or c2 == Color.TBD or c3 == Color.TBD or c4 == Color.TBD: | |
continue # 形式情報の未決定部分をどう解釈するか規格から読み取れないがどうすりゃいいんだ…… | |
elif c1 == Color.WHITE and c2 == Color.WHITE and c3 == Color.WHITE and c4 == Color.WHITE: | |
minus += penalty_n2 | |
elif c1 == Color.BLACK and c2 == Color.BLACK and c3 == Color.BLACK and c4 == Color.BLACK: | |
minus += penalty_n2 | |
return minus | |
def eval_mask3(grid): | |
# 評価3 : 暗:明:暗:明:暗:明=1:1:3:1:1:4 | |
def eval_sub(accessor, lines): | |
penalty_n3 = 40 | |
minus = 0 | |
w, b = Color.WHITE, Color.BLACK | |
pattern1 = [b, w, b, b, b, w, b, w, w, w, w] # 左端(or上端)->内側 | |
pattern2 = [w, w, w, w, b, w, b, b, b, w, b] # 内側<-右端(or下端) | |
k = len(pattern1) | |
for i in lines: | |
for j in range(k): | |
col = accessor(i, j).color | |
if pattern1[j] != col: | |
break | |
else: | |
minus += penalty_n3 | |
for j in range(SIZE-k): | |
col = accessor(i, j).color | |
if pattern2[j] != col: | |
break | |
else: | |
minus += penalty_n3 | |
return minus | |
target_lines = [2, 3, 4, SIZE-5, SIZE-4, SIZE-3] # 位置検出パターンがあるラインの番号 | |
minus_row = eval_sub(lambda i, j: grid[i][j], target_lines) # 行を見る | |
minus_col = eval_sub(lambda i, j: grid[j][i], target_lines) # 列を見る | |
return minus_row + minus_col | |
def eval_mask4(grid): | |
# 評価4 : 全体に占める暗モジュールの割合 (5%偏差ごとに失点) | |
n4 = 10 | |
minus = 0 | |
c_black = 0 | |
for i in range(SIZE): | |
for j in range(SIZE): | |
if grid[i][j].color == Color.BLACK: | |
c_black += 1 | |
percentage = 100 * c_black / SIZE**2 | |
diff = abs(percentage - 50.0) | |
while diff > 5.0: | |
diff -= 5.0 | |
minus += n4 | |
return minus | |
def eval_mask(stream, mask_num): | |
# マスク適用後のグリッド情報を生成する | |
grid = [] | |
mask = masks[mask_num] | |
for i in range(SIZE): | |
row = [] | |
for j in range(SIZE): | |
index = layout_ver2[i][j] | |
if index == BBB: # 機能パターン暗モジュール | |
row.append(MaskGridCell(False, Color.BLACK)) | |
elif index == ___: # 機能パターン明モジュール | |
row.append(MaskGridCell(False, Color.WHITE)) | |
elif index >= FORMAT_START_BIT: # 形式情報 | |
# どうすればいいのか分からない。とりあえず白でも黒でもない値を入れておく。 | |
row.append(MaskGridCell(False, Color.TBD)) | |
else: | |
# マスク掛ける | |
b = stream.get_bit(index) | |
m = mask(i, j) | |
col = Color.BLACK if b ^ m else Color.WHITE | |
row.append(MaskGridCell(True, col)) | |
grid.append(row) | |
# 評価1-4を実施 | |
m1, m2, m3, m4 = eval_mask1(grid), eval_mask2(grid), eval_mask3(grid), eval_mask4(grid) | |
minus = m1 + m2 + m3 + m4 | |
print(f'eval{mask_num}: {m1}, {m2}, {m3}, {m4}, total={minus}') | |
return minus | |
def make_code(stream, mask_num): | |
grid = [] | |
mask = masks[mask_num] | |
for i in range(SIZE): | |
row = [] | |
for j in range(SIZE): | |
index = layout_ver2[i][j] | |
if 0 <= index < MASK_TARGET_BITS: | |
# マスク適用対象 | |
b = stream.get_bit(index) | |
m = mask(i, j) | |
row.append(b ^ m) | |
elif MASK_TARGET_BITS <= index < FORMAT_START_BIT: | |
# 残余ビット(明モジュール) | |
row.append(Color.WHITE.value) | |
elif index >= FORMAT_START_BIT: | |
# 形式情報 | |
b = stream.get_bit(index) | |
row.append(b) | |
elif index == BBB: | |
# 機能パターン部(暗モジュール) | |
row.append(Color.BLACK.value) | |
elif index == ___: | |
# 機能パターン部(明モジュール) | |
row.append(Color.WHITE.value) | |
else: | |
raise ValueError(f'Bad definition in layout_ver2: ({i},{j}), index={index}') | |
grid.append(row) | |
return grid | |
def make_image(code): | |
quiet = 4 | |
block_size = 8 | |
block_num = SIZE + quiet * 2 | |
width = height = block_num * block_size | |
offset = quiet | |
image = Image.new('RGB', (block_num, block_num), (255, 255, 255)) | |
for i in range(SIZE): | |
y = offset + i | |
for j in range(SIZE): | |
x = offset + j | |
b = code[i][j] | |
if b: # 明:0 暗:1なので色を反転させる | |
lm = 0 | |
else: | |
lm = 255 | |
image.putpixel((x, y), (lm, lm, lm)) | |
return image.resize((width, height)) | |
def create_qr(text, filename): | |
# 準備: テーブルを作成 | |
init_tables() | |
# 1. データを用意する | |
char_codes = [convert_char(c) for c in text] # Shift-JISから13ビットコードに変換 | |
stream = BitStream(K_DATA * 8) # データ16バイト分を作成する | |
stream.add_bits([1, 0, 0, 0]) # 漢字モード | |
stream.add_integer(len(text), length=8) # 文字数 | |
for char in char_codes: | |
stream.add_bits(char) | |
stream.add_bits([0, 0, 0, 0], cancellable=True) # 終端パターン | |
stream.fill_zero() # バイト境界までをビット0で埋める | |
try: # 後は容量いっぱいまでの規定のデータで埋める | |
while True: | |
stream.add_bits([1, 1, 1, 0, 1, 1, 0, 0]) | |
stream.add_bits([0, 0, 0, 1, 0, 0, 0, 1]) | |
except MemoryError: | |
pass | |
print('embedded data:') | |
for byte in stream.bytes: | |
print(f'{byte:#08b}', end=',') | |
print() | |
# 2. RS誤り訂正符号を生成する | |
correction_code = calc_rs_mod(stream.bytes, N_DATA, K_DATA, COEFFICIENT_D16) | |
print('correction code:') | |
print(correction_code) | |
# 3. QRに埋め込むための情報(データ+誤り訂正符号+残余ビット)を結合する | |
stream.clear_limit() # もう容量チェックは不要 | |
# 誤り訂正記号を突っ込む | |
for code in correction_code: | |
stream.add_integer(code, 8) | |
# 残余ビット(7bit)を突っ込む | |
stream.add_bits([0, 0, 0, 0, 0, 0, 0]) | |
# 4. 最適なマスクを検証する | |
min_score = 10**8 | |
mask_index = -1 | |
print('mask:') | |
for i in range(8): | |
score = eval_mask(stream, i) | |
if score < min_score: | |
min_score = score | |
mask_index = i | |
print(f'selected mask: {mask_index:#03b}') | |
# 5. 形式情報を生成する | |
correction_level = [1, 0] # 誤り訂正レベルH | |
mask_b2 = (mask_index & 0b100) >> 2 # 適用マスク番号 | |
mask_b1 = (mask_index & 0b010) >> 1 | |
mask_b0 = (mask_index & 0b001) >> 0 | |
format_info = correction_level + [mask_b2, mask_b1, mask_b0] | |
format_info += calc_bch_mod(format_info, N_BCH, K_BCH, COEFFICIENT_BCH) # 訂正ビットを求める | |
format_num = int(''.join([str(i) for i in format_info]), 2) # 2進リストから10進値に変換 | |
format_num ^= 0b101010000010010 # マスクとのXORをとる | |
stream.add_integer(format_num, 15) | |
print('format_info', format_info) | |
# 6. データ完成 | |
code = make_code(stream, mask_index) | |
print('result:') | |
for row in code: | |
for col in row: | |
print(col, end="") | |
print() | |
# 7. 画像に出力 | |
image = make_image(code) | |
image.save(filename) | |
if __name__ == '__main__': | |
# QRコードを作る | |
# 他のアイドル担当のPちゃんはここを任意の名前に変えてね☆ (上限8文字) | |
create_qr(text='大石泉すき', filename='izumi_ohishi.png') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment