1#!/usr/local/bin/python3.8 2# -*- coding: UTF-8 -*- 3# 4# Copyright (C) 2009 John Beard john.j.beard@gmail.com 5# 6# This program is free software; you can redistribute it and/or modify 7# it under the terms of the GNU General Public License as published by 8# the Free Software Foundation; either version 2 of the License, or 9# (at your option) any later version. 10# 11# This program is distributed in the hope that it will be useful, 12# but WITHOUT ANY WARRANTY; without even the implied warranty of 13# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14# GNU General Public License for more details. 15# 16# You should have received a copy of the GNU General Public License 17# along with this program; if not, write to the Free Software 18# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 19# 20""" 21This extension renders a DataMatrix 2D barcode, as specified in 22BS ISO/IEC 16022:2006. Only ECC200 codes are considered, as these are the only 23ones recommended for an "open" system. 24 25The size of the DataMatrix is variable between 10x10 to 144x144 26 27The absolute size of the DataMatrix modules (the little squares) is also 28variable. 29 30If more data is given than can be contained in one DataMatrix, 31more than one DataMatrices will be produced. 32 33Text is encoded as ASCII (the standard provides for other options, but these are 34not implemented). Consecutive digits are encoded in a compressed form, halving 35the space required to store them. 36 37The basis processing flow is; 38 * Convert input string to codewords (modified ASCII and compressed digits) 39 * Split codewords into blocks of the right size for Reed-Solomon coding 40 * Interleave the blocks if required 41 * Apply Reed-Solomon coding 42 * De-interleave the blocks if required 43 * Place the codewords into the matrix bit by bit 44 * Render the modules in the matrix as squares 45""" 46 47import inkex 48from inkex import Rectangle 49 50INVALID_BIT = 2 51 52# return parameters for the selected datamatrix size 53# drow number of rows in each data region 54# dcol number of cols in each data region 55# reg_row number of rows of data regions 56# reg_col number of cols of data regions 57# nd number of data codewords per reed-solomon block 58# nc number of ECC codewords per reed-solomon block 59# inter number of interleaved Reed-Solomon blocks 60SYMBOLS = { 61 # 'id': (nrow, ncol, drow, dcol, reg_row, reg_col, nd, nc, inter) 62 'sq10': (10, 10, 8, 8, 1, 1, 3, 5, 1), 63 'sq12': (12, 12, 10, 10, 1, 1, 5, 7, 1), 64 'sq14': (14, 14, 12, 12, 1, 1, 8, 10, 1), 65 'sq16': (16, 16, 14, 14, 1, 1, 12, 12, 1), 66 'sq18': (18, 18, 16, 16, 1, 1, 18, 14, 1), 67 'sq20': (20, 20, 18, 18, 1, 1, 22, 18, 1), 68 'sq22': (22, 22, 20, 20, 1, 1, 30, 20, 1), 69 'sq24': (24, 24, 22, 22, 1, 1, 36, 24, 1), 70 'sq26': (26, 26, 24, 24, 1, 1, 44, 28, 1), 71 'sq32': (32, 32, 14, 14, 2, 2, 62, 36, 1), 72 'sq36': (36, 36, 16, 16, 2, 2, 86, 42, 1), 73 'sq40': (40, 40, 18, 18, 2, 2, 114, 48, 1), 74 'sq44': (44, 44, 20, 20, 2, 2, 144, 56, 1), 75 'sq48': (48, 48, 22, 22, 2, 2, 174, 68, 1), 76 'sq52': (52, 52, 24, 24, 2, 2, 102, 42, 2), 77 'sq64': (64, 64, 14, 14, 4, 4, 140, 56, 2), 78 'sq72': (72, 72, 16, 16, 4, 4, 92, 36, 4), 79 'sq80': (80, 80, 18, 18, 4, 4, 114, 48, 4), 80 'sq88': (88, 88, 20, 20, 4, 4, 144, 56, 4), 81 'sq96': (96, 96, 22, 22, 4, 4, 174, 68, 4), 82 'sq104': (104, 104, 24, 24, 4, 4, 136, 56, 6), 83 'sq120': (120, 120, 18, 18, 6, 6, 175, 68, 6), 84 'sq132': (132, 132, 20, 20, 6, 6, 163, 62, 8), 85 # there are two separate sections of the data matrix with different interleaving 86 # and reed-solomon parameters. this will be handled separately. 87 'sq144': (144, 144, 22, 22, 6, 6, 0, 0, 0), 88 'rect8x18': (8, 18, 6, 16, 1, 1, 5, 7, 1), 89 'rect8x32': (8, 32, 6, 14, 1, 2, 10, 11, 1), 90 'rect12x26': (12, 26, 10, 24, 1, 1, 16, 14, 1), 91 'rect12x36': (12, 36, 10, 16, 1, 2, 22, 18, 1), 92 'rect16x36': (16, 36, 14, 16, 1, 2, 32, 24, 1), 93 'rect16x48': (16, 48, 14, 22, 1, 2, 49, 28, 1), 94} 95 96 97 98# CODEWORD STREAM GENERATION ========================================= 99# take the text input and return the codewords, 100# including the Reed-Solomon error-correcting codes. 101# ===================================================================== 102 103def get_codewords(text, nd, nc, inter, size144): 104 # convert the data to the codewords 105 data = list(encode_to_ascii(text)) 106 107 if not size144: # render a "normal" datamatrix 108 data_blocks = partition_data(data, nd * inter) # partition into data blocks of length nd*inter -> inter Reed-Solomon block 109 110 data_blocks = interleave(data_blocks, inter) # interleave consecutive inter blocks if required 111 112 data_blocks = reed_solomon(data_blocks, nd, nc) # generate and append the Reed-Solomon codewords 113 114 data_blocks = combine_interleaved(data_blocks, inter, nd, nc, False) # concatenate Reed-Solomon blocks bound for the same datamatrix 115 116 else: # we have a 144x144 datamatrix 117 data_blocks = partition_data(data, 1558) # partition the data into datamtrix-sized chunks (1558 =156*8 + 155*2 ) 118 119 for i in range(len(data_blocks)): # for each datamtrix 120 121 inter = 8 122 nd = 156 123 nc = 62 124 block1 = data_blocks[i][0:156 * 8] 125 block1 = interleave([block1], inter) # interleave into 8 blocks 126 block1 = reed_solomon(block1, nd, nc) # generate and append the Reed-Solomon codewords 127 128 inter = 2 129 nd = 155 130 nc = 62 131 block2 = data_blocks[i][156 * 8:] 132 block2 = interleave([block2], inter) # interleave into 2 blocks 133 block2 = reed_solomon(block2, nd, nc) # generate and append the Reed-Solomon codewords 134 135 blocks = block1 136 blocks.extend(block2) 137 138 blocks = combine_interleaved(blocks, 10, nd, nc, True) 139 140 data_blocks[i] = blocks[0] 141 142 return data_blocks 143 144 145# Takes a codeword stream and splits up into "inter" blocks. 146# eg interleave( [1,2,3,4,5,6], 2 ) -> [1,3,5], [2,4,6] 147def interleave(blocks, inter): 148 if inter == 1: # if we don't have to interleave, just return the blocks 149 return blocks 150 else: 151 result = [] 152 for block in blocks: # for each codeword block in the stream 153 block_length = int(len(block) / inter) # length of each interleaved block 154 inter_blocks = [[0] * block_length for i in range(inter)] # the interleaved blocks 155 156 for i in range(block_length): # for each element in the interleaved blocks 157 for j in range(inter): # for each interleaved block 158 inter_blocks[j][i] = block[i * inter + j] 159 160 result.extend(inter_blocks) # add the interleaved blocks to the output 161 162 return result 163 164 165# Combine interleaved blocks into the groups for the same datamatrix 166# 167# e.g combine_interleaved( [[d1, d3, d5, e1, e3, e5], [d2, d4, d6, e2, e4, e6]], 2, 3, 3 ) 168# --> [[d1, d2, d3, d4, d5, d6, e1, e2, e3, e4, e5, e6]] 169def combine_interleaved(blocks, inter, nd, nc, size144): 170 if inter == 1: # the blocks aren't interleaved 171 return blocks 172 else: 173 result = [] 174 for i in range(len(blocks) // inter): # for each group of "inter" blocks -> one full datamatrix 175 data_codewords = [] # interleaved data blocks 176 177 if size144: 178 nd_range = 1558 # 1558 = 156*8 + 155*2 179 nc_range = 620 # 620 = 62*8 + 62*2 180 else: 181 nd_range = nd * inter 182 nc_range = nc * inter 183 184 for j in range(nd_range): # for each codeword in the final list 185 data_codewords.append(blocks[i * inter + j % inter][j // inter]) 186 187 for j in range(nc_range): # for each block, add the ecc codewords 188 data_codewords.append(blocks[i * inter + j % inter][nd + j // inter]) 189 190 result.append(data_codewords) 191 return result 192 193 194def encode_to_ascii(text): 195 """Encode this text into chunks, ascii or digits""" 196 i = 0 197 while i < len(text): 198 # check for double digits, if the next char is also a digit 199 if text[i].isdigit() and (i < len(text) - 1) and text[i + 1].isdigit(): 200 yield int(text[i] + text[i + 1]) + 130 201 i += 2 # move on 2 characters 202 else: # encode as a normal ascii, 203 yield ord(text[i]) + 1 # codeword is ASCII value + 1 (ISO 16022:2006 5.2.3) 204 i += 1 # next character 205 206 207# partition data into blocks of the appropriate size to suit the 208# Reed-Solomon block being used. 209# e.g. partition_data([1,2,3,4,5], 3) -> [[1,2,3],[4,5,PAD]] 210def partition_data(data, rs_data): 211 PAD_VAL = 129 # PAD codeword (ISO 16022:2006 5.2.3) 212 data_blocks = [] 213 i = 0 214 while i < len(data): 215 if len(data) >= i + rs_data: # we have a whole block in our data 216 data_blocks.append(data[i:i + rs_data]) 217 i = i + rs_data 218 else: # pad out with the pad codeword 219 data_block = data[i:len(data)] # add any remaining data 220 pad_pos = len(data) 221 padded = False 222 while len(data_block) < rs_data: # and then pad with randomised pad codewords 223 if not padded: 224 data_block.append(PAD_VAL) # add a normal pad codeword 225 padded = True 226 else: 227 data_block.append(randomise_pad_253(PAD_VAL, pad_pos)) 228 pad_pos += 1 229 data_blocks.append(data_block) 230 break 231 232 return data_blocks 233 234 235# Pad character randomisation, to prevent regular patterns appearing 236# in the data matrix 237def randomise_pad_253(pad_value, pad_position): 238 pseudo_random_number = ((149 * pad_position) % 253) + 1 239 randomised = pad_value + pseudo_random_number 240 if randomised <= 254: 241 return randomised 242 else: 243 return randomised - 254 244 245 246# REED-SOLOMON ENCODING ROUTINES ===================================== 247 248# "prod(x,y,log,alog,gf)" returns the product "x" times "y" 249def prod(x, y, log, alog, gf): 250 if x == 0 or y == 0: 251 return 0 252 else: 253 result = alog[(log[x] + log[y]) % (gf - 1)] 254 return result 255 256 257# generate the log & antilog lists: 258def gen_log_alog(gf, pp): 259 log = [0] * gf 260 alog = [0] * gf 261 262 log[0] = 1 - gf 263 alog[0] = 1 264 265 for i in range(1, gf): 266 alog[i] = alog[i - 1] * 2 267 268 if alog[i] >= gf: 269 alog[i] = alog[i] ^ pp 270 271 log[alog[i]] = i 272 273 return log, alog 274 275 276# generate the generator polynomial coefficients: 277def gen_poly_coeffs(nc, log, alog, gf): 278 c = [0] * (nc + 1) 279 c[0] = 1 280 281 for i in range(1, nc + 1): 282 c[i] = c[i - 1] 283 284 j = i - 1 285 while j >= 1: 286 c[j] = c[j - 1] ^ prod(c[j], alog[i], log, alog, gf) 287 j -= 1 288 289 c[0] = prod(c[0], alog[i], log, alog, gf) 290 291 return c 292 293 294# "ReedSolomon(wd,nd,nc)" takes "nd" data codeword values in wd[] 295# and adds on "nc" check codewords, all within GF(gf) where "gf" is a 296# power of 2 and "pp" is the value of its prime modulus polynomial */ 297def reed_solomon(data, nd, nc): 298 # parameters of the polynomial arithmetic 299 gf = 256 # operating on 8-bit codewords -> Galois field = 2^8 = 256 300 pp = 301 # prime modulus polynomial for ECC-200 is 0b100101101 = 301 (ISO 16022:2006 5.7.1) 301 302 log, alog = gen_log_alog(gf, pp) 303 c = gen_poly_coeffs(nc, log, alog, gf) 304 305 for block in data: # for each block of data codewords 306 307 block.extend([0] * (nc + 1)) # extend to make space for the error codewords 308 309 # generate "nc" checkwords in the list block 310 for i in range(0, nd): 311 k = block[nd] ^ block[i] 312 313 for j in range(0, nc): 314 block[nd + j] = block[nd + j + 1] ^ prod(k, c[nc - j - 1], log, alog, gf) 315 316 block.pop() 317 318 return data 319 320 321# MODULE PLACEMENT ROUTINES=========================================== 322# These routines take a steam of codewords, and place them into the 323# DataMatrix in accordance with Annex F of BS ISO/IEC 16022:2006 324 325def bit(byte, bit_ch): 326 """bit() returns the bit'th bit of the byte""" 327 # the MSB is bit 1, LSB is bit 8 328 return (byte >> (8 - bit_ch)) % 2 329 330 331def module(array, nrow, ncol, row, col, bit_ch): 332 """place a given bit with appropriate wrapping within array""" 333 if row < 0: 334 row = row + nrow 335 col = col + 4 - ((nrow + 4) % 8) 336 337 if col < 0: 338 col = col + ncol 339 row = row + 4 - ((ncol + 4) % 8) 340 341 array[row][col] = bit_ch 342 343 344def place_square(case, array, nrow, ncol, row, col, char): 345 """Populate corner cases (0-3) and utah case (-1)""" 346 for i in range(8): 347 x, y = [ 348 [(row - 1, 0), (row - 1, 1), (row - 1, 2), (0, col - 2), 349 (0, col - 1), (1, col - 1), (2, col - 1), (3, col - 1)], 350 [(row - 3, 0), (row - 2, 0), (row - 1, 0), (0, col - 4), 351 (0, col - 3), (0, col - 2), (0, col - 1), (1, col - 1)], 352 [(row - 3, 0), (row - 2, 0), (row - 1, 0), (0, col - 2), 353 (0, col - 1), (1, col - 1), (2, col - 1), (3, col - 1)], 354 [(row - 1, 0), (row - 1, col - 1), (0, col - 3), (0, col - 2), 355 (0, col - 1), (1, col - 3), (1, col - 2), (1, col - 1)], 356 357 # "utah" places the 8 bits of a utah-shaped symbol character in ECC200 358 [(row - 2, col -2), (row - 2, col -1), (row - 1, col - 2), (row - 1, col - 1), 359 (row - 1, col), (row, col - 2), (row, col - 1), (row, col)], 360 ][case][i] 361 module(array, nrow, ncol, x, y, bit(char, i + 1)) 362 return 1 363 364def place_bits(data, nrow, ncol): 365 """fill an nrow x ncol array with the bits from the codewords in data.""" 366 # initialise and fill with -1's (invalid value) 367 array = [[INVALID_BIT] * ncol for i in range(nrow)] 368 # Starting in the correct location for character #1, bit 8,... 369 char = 0 370 row = 4 371 col = 0 372 while True: 373 374 # first check for one of the special corner cases, then... 375 if (row == nrow) and (col == 0): 376 char += place_square(0, array, nrow, ncol, nrow, ncol, data[char]) 377 elif (row == nrow - 2) and (col == 0) and (ncol % 4): 378 char += place_square(1, array, nrow, ncol, nrow, ncol, data[char]) 379 elif (row == nrow - 2) and (col == 0) and (ncol % 8 == 4): 380 char += place_square(2, array, nrow, ncol, nrow, ncol, data[char]) 381 elif (row == nrow + 4) and (col == 2) and ((ncol % 8) == 0): 382 char += place_square(3, array, nrow, ncol, nrow, ncol, data[char]) 383 384 # sweep upward diagonally, inserting successive characters,... 385 while (row >= 0) and (col < ncol): 386 if (row < nrow) and (col >= 0) and (array[row][col] == INVALID_BIT): 387 char += place_square(-1, array, nrow, ncol, row, col, data[char]) 388 row -= 2 389 col += 2 390 391 row += 1 392 col += 3 393 394 # & then sweep downward diagonally, inserting successive characters,... 395 while (row < nrow) and (col >= 0): 396 if (row >= 0) and (col < ncol) and (array[row][col] == INVALID_BIT): 397 char += place_square(-1, array, nrow, ncol, row, col, data[char]) 398 row += 2 399 col -= 2 400 401 row += 3 402 col += 1 403 404 # ... until the entire array is scanned 405 if not ((row < nrow) or (col < ncol)): 406 break 407 408 # Lastly, if the lower righthand corner is untouched, fill in fixed pattern */ 409 if array[nrow - 1][ncol - 1] == INVALID_BIT: 410 array[nrow - 1][ncol - 2] = 0 411 array[nrow - 1][ncol - 1] = 1 412 array[nrow - 2][ncol - 1] = 0 413 array[nrow - 2][ncol - 2] = 1 414 415 return array # return the array of 1's and 0's 416 417 418def add_finder_pattern(array, data_nrow, data_ncol, reg_row, reg_col): 419 # get the total size of the datamatrix 420 nrow = (data_nrow + 2) * reg_row 421 ncol = (data_ncol + 2) * reg_col 422 423 datamatrix = [[0] * ncol for i in range(nrow)] # initialise and fill with 0's 424 425 for i in range(reg_col): # for each column of data regions 426 for j in range(nrow): 427 datamatrix[j][i * (data_ncol + 2)] = 1 # vertical black bar on left 428 datamatrix[j][i * (data_ncol + 2) + data_ncol + 1] = j % 2 # alternating blocks 429 430 for i in range(reg_row): # for each row of data regions 431 for j in range(ncol): 432 datamatrix[i * (data_nrow + 2) + data_nrow + 1][j] = 1 # horizontal black bar at bottom 433 datamatrix[i * (data_nrow + 2)][j] = (j + 1) % 2 # alternating blocks 434 435 for i in range(data_nrow * reg_row): 436 for j in range(data_ncol * reg_col): 437 # offset by 1, plus two for every addition block 438 dest_col = j + 1 + 2 * (j // data_ncol) 439 dest_row = i + 1 + 2 * (i // data_nrow) 440 441 datamatrix[dest_row][dest_col] = array[i][j] # transfer from the plain bit array 442 443 return datamatrix 444 445 446 447 448class DataMatrix(inkex.GenerateExtension): 449 container_label = 'DataMatrix' 450 451 def add_arguments(self, pars): 452 pars.add_argument("--text", default='Inkscape') 453 pars.add_argument("--symbol", type=self.arg_symbols, required=True) 454 pars.add_argument("--size", type=int, default=4) 455 456 @staticmethod 457 def arg_symbols(value): 458 """Turn a symbol key into matrix metrics""" 459 try: 460 return SYMBOLS[value] 461 except KeyError: 462 raise inkex.AbortExtension("Invalid symbol size.") 463 464 def generate(self): 465 size = str(self.options.size) 466 style = inkex.Style({'stroke': 'none', 'stroke-width': '1', 'fill': '#000000'}) 467 attribs = {'style': str(style), 'height': size, 'width': size} 468 469 if not self.options.text: 470 raise inkex.AbortExtension("Please enter an input string.") 471 472 # create a 2d list corresponding to the 1's and 0s of the DataMatrix 473 encoded = self.encode(self.options.text, *self.options.symbol) 474 for x, y in self.render_data_matrix(encoded): 475 attribs.update({'x': str(x), 'y': str(y)}) 476 yield Rectangle(**attribs) 477 478 def encode(self, text, nrow, ncol, data_nrow, data_ncol, reg_row, reg_col, nd, nc, inter): 479 """ 480 Take an input string and convert it to a sequence (or sequences) 481 of codewords as specified in ISO/IEC 16022:2006 (section 5.2.3) 482 """ 483 # generate the codewords including padding and ECC 484 codewords = get_codewords(text, nd, nc, inter, nrow == 144) 485 486 # break up into separate arrays if more than one DataMatrix is needed 487 module_arrays = [] 488 for codeword_stream in codewords: # for each datamatrix 489 # place the codewords' bits across the array as modules 490 bit_array = place_bits(codeword_stream, data_nrow * reg_row, data_ncol * reg_col) 491 # add finder patterns around the modules 492 module_arrays.append(add_finder_pattern(bit_array, data_nrow, data_ncol, reg_row, reg_col)) 493 494 return module_arrays 495 496 def render_data_matrix(self, module_arrays): 497 """turn a 2D array of 1's and 0's into a set of black squares""" 498 ncol = self.options.symbol[1] 499 size = self.options.size 500 spacing = ncol * size * 1.5 501 for i, line in enumerate(module_arrays): 502 height = len(line) 503 width = len(line[0]) 504 505 for y in range(height): # loop over all the modules in the datamatrix 506 for x in range(width): 507 if line[y][x] == 1: # A binary 1 is a filled square 508 yield (x * size + i * spacing, y * size) 509 elif line[y][x] == INVALID_BIT: # we have an invalid bit value 510 inkex.errormsg('Invalid bit value, {}!'.format(line[y][x])) 511 512if __name__ == '__main__': 513 DataMatrix().run() 514