diff options
Diffstat (limited to '')
| -rwxr-xr-x | share/extensions/render_barcode_datamatrix.py | 588 |
1 files changed, 588 insertions, 0 deletions
diff --git a/share/extensions/render_barcode_datamatrix.py b/share/extensions/render_barcode_datamatrix.py new file mode 100755 index 0000000..5b3906c --- /dev/null +++ b/share/extensions/render_barcode_datamatrix.py @@ -0,0 +1,588 @@ +#!/usr/bin/env python +# -*- coding: UTF-8 -*- +# +# Copyright (C) 2009 John Beard john.j.beard@gmail.com +# +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software +# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. +# +""" +This extension renders a DataMatrix 2D barcode, as specified in +BS ISO/IEC 16022:2006. Only ECC200 codes are considered, as these are the only +ones recommended for an "open" system. + +The size of the DataMatrix is variable between 10x10 to 144x144 + +The absolute size of the DataMatrix modules (the little squares) is also +variable. + +If more data is given than can be contained in one DataMatrix, +more than one DataMatrices will be produced. + +Text is encoded as ASCII (the standard provides for other options, but these are +not implemented). Consecutive digits are encoded in a compressed form, halving +the space required to store them. + +The basis processing flow is; + * Convert input string to codewords (modified ASCII and compressed digits) + * Split codewords into blocks of the right size for Reed-Solomon coding + * Interleave the blocks if required + * Apply Reed-Solomon coding + * De-interleave the blocks if required + * Place the codewords into the matrix bit by bit + * Render the modules in the matrix as squares +""" + +import inkex +from inkex import Rectangle +from inkex.localization import inkex_gettext as _ + +INVALID_BIT = 2 + +# return parameters for the selected datamatrix size +# drow number of rows in each data region +# dcol number of cols in each data region +# reg_row number of rows of data regions +# reg_col number of cols of data regions +# nd number of data codewords per reed-solomon block +# nc number of ECC codewords per reed-solomon block +# inter number of interleaved Reed-Solomon blocks +SYMBOLS = { + # 'id': (nrow, ncol, drow, dcol, reg_row, reg_col, nd, nc, inter) + "sq10": (10, 10, 8, 8, 1, 1, 3, 5, 1), + "sq12": (12, 12, 10, 10, 1, 1, 5, 7, 1), + "sq14": (14, 14, 12, 12, 1, 1, 8, 10, 1), + "sq16": (16, 16, 14, 14, 1, 1, 12, 12, 1), + "sq18": (18, 18, 16, 16, 1, 1, 18, 14, 1), + "sq20": (20, 20, 18, 18, 1, 1, 22, 18, 1), + "sq22": (22, 22, 20, 20, 1, 1, 30, 20, 1), + "sq24": (24, 24, 22, 22, 1, 1, 36, 24, 1), + "sq26": (26, 26, 24, 24, 1, 1, 44, 28, 1), + "sq32": (32, 32, 14, 14, 2, 2, 62, 36, 1), + "sq36": (36, 36, 16, 16, 2, 2, 86, 42, 1), + "sq40": (40, 40, 18, 18, 2, 2, 114, 48, 1), + "sq44": (44, 44, 20, 20, 2, 2, 144, 56, 1), + "sq48": (48, 48, 22, 22, 2, 2, 174, 68, 1), + "sq52": (52, 52, 24, 24, 2, 2, 102, 42, 2), + "sq64": (64, 64, 14, 14, 4, 4, 140, 56, 2), + "sq72": (72, 72, 16, 16, 4, 4, 92, 36, 4), + "sq80": (80, 80, 18, 18, 4, 4, 114, 48, 4), + "sq88": (88, 88, 20, 20, 4, 4, 144, 56, 4), + "sq96": (96, 96, 22, 22, 4, 4, 174, 68, 4), + "sq104": (104, 104, 24, 24, 4, 4, 136, 56, 6), + "sq120": (120, 120, 18, 18, 6, 6, 175, 68, 6), + "sq132": (132, 132, 20, 20, 6, 6, 163, 62, 8), + # there are two separate sections of the data matrix with different interleaving + # and reed-solomon parameters. this will be handled separately. + "sq144": (144, 144, 22, 22, 6, 6, 0, 0, 0), + "rect8x18": (8, 18, 6, 16, 1, 1, 5, 7, 1), + "rect8x32": (8, 32, 6, 14, 1, 2, 10, 11, 1), + "rect12x26": (12, 26, 10, 24, 1, 1, 16, 14, 1), + "rect12x36": (12, 36, 10, 16, 1, 2, 22, 18, 1), + "rect16x36": (16, 36, 14, 16, 1, 2, 32, 24, 1), + "rect16x48": (16, 48, 14, 22, 1, 2, 49, 28, 1), +} + + +# CODEWORD STREAM GENERATION ========================================= +# take the text input and return the codewords, +# including the Reed-Solomon error-correcting codes. +# ===================================================================== + + +def get_codewords(text, nd, nc, inter, size144): + # convert the data to the codewords + data = list(encode_to_ascii(text)) + + if not size144: # render a "normal" datamatrix + data_blocks = partition_data( + data, nd * inter + ) # partition into data blocks of length nd*inter -> inter Reed-Solomon block + + data_blocks = interleave( + data_blocks, inter + ) # interleave consecutive inter blocks if required + + data_blocks = reed_solomon( + data_blocks, nd, nc + ) # generate and append the Reed-Solomon codewords + + data_blocks = combine_interleaved( + data_blocks, inter, nd, nc, False + ) # concatenate Reed-Solomon blocks bound for the same datamatrix + + else: # we have a 144x144 datamatrix + data_blocks = partition_data( + data, 1558 + ) # partition the data into datamtrix-sized chunks (1558 =156*8 + 155*2 ) + + for i in range(len(data_blocks)): # for each datamtrix + + inter = 8 + nd = 156 + nc = 62 + block1 = data_blocks[i][0 : 156 * 8] + block1 = interleave([block1], inter) # interleave into 8 blocks + block1 = reed_solomon( + block1, nd, nc + ) # generate and append the Reed-Solomon codewords + + inter = 2 + nd = 155 + nc = 62 + block2 = data_blocks[i][156 * 8 :] + block2 = interleave([block2], inter) # interleave into 2 blocks + block2 = reed_solomon( + block2, nd, nc + ) # generate and append the Reed-Solomon codewords + + blocks = block1 + blocks.extend(block2) + + blocks = combine_interleaved(blocks, 10, nd, nc, True) + + data_blocks[i] = blocks[0] + + return data_blocks + + +# Takes a codeword stream and splits up into "inter" blocks. +# eg interleave( [1,2,3,4,5,6], 2 ) -> [1,3,5], [2,4,6] +def interleave(blocks, inter): + if inter == 1: # if we don't have to interleave, just return the blocks + return blocks + else: + result = [] + for block in blocks: # for each codeword block in the stream + block_length = int(len(block) / inter) # length of each interleaved block + inter_blocks = [ + [0] * block_length for i in range(inter) + ] # the interleaved blocks + + for i in range(block_length): # for each element in the interleaved blocks + for j in range(inter): # for each interleaved block + inter_blocks[j][i] = block[i * inter + j] + + result.extend(inter_blocks) # add the interleaved blocks to the output + + return result + + +# Combine interleaved blocks into the groups for the same datamatrix +# +# e.g combine_interleaved( [[d1, d3, d5, e1, e3, e5], [d2, d4, d6, e2, e4, e6]], 2, 3, 3 ) +# --> [[d1, d2, d3, d4, d5, d6, e1, e2, e3, e4, e5, e6]] +def combine_interleaved(blocks, inter, nd, nc, size144): + if inter == 1: # the blocks aren't interleaved + return blocks + else: + result = [] + for i in range( + len(blocks) // inter + ): # for each group of "inter" blocks -> one full datamatrix + data_codewords = [] # interleaved data blocks + + if size144: + nd_range = 1558 # 1558 = 156*8 + 155*2 + nc_range = 620 # 620 = 62*8 + 62*2 + else: + nd_range = nd * inter + nc_range = nc * inter + + for j in range(nd_range): # for each codeword in the final list + data_codewords.append(blocks[i * inter + j % inter][j // inter]) + + for j in range(nc_range): # for each block, add the ecc codewords + data_codewords.append(blocks[i * inter + j % inter][nd + j // inter]) + + result.append(data_codewords) + return result + + +def encode_to_ascii(text): + """Encode this text into chunks, ascii or digits""" + i = 0 + while i < len(text): + # check for double digits, if the next char is also a digit + if text[i].isdigit() and (i < len(text) - 1) and text[i + 1].isdigit(): + yield int(text[i] + text[i + 1]) + 130 + i += 2 # move on 2 characters + else: # encode as a normal ascii, + yield ord(text[i]) + 1 # codeword is ASCII value + 1 (ISO 16022:2006 5.2.3) + i += 1 # next character + + +# partition data into blocks of the appropriate size to suit the +# Reed-Solomon block being used. +# e.g. partition_data([1,2,3,4,5], 3) -> [[1,2,3],[4,5,PAD]] +def partition_data(data, rs_data): + PAD_VAL = 129 # PAD codeword (ISO 16022:2006 5.2.3) + data_blocks = [] + i = 0 + while i < len(data): + if len(data) >= i + rs_data: # we have a whole block in our data + data_blocks.append(data[i : i + rs_data]) + i = i + rs_data + else: # pad out with the pad codeword + data_block = data[i : len(data)] # add any remaining data + pad_pos = len(data) + padded = False + while ( + len(data_block) < rs_data + ): # and then pad with randomised pad codewords + if not padded: + data_block.append(PAD_VAL) # add a normal pad codeword + padded = True + else: + data_block.append(randomise_pad_253(PAD_VAL, pad_pos)) + pad_pos += 1 + data_blocks.append(data_block) + break + + return data_blocks + + +# Pad character randomisation, to prevent regular patterns appearing +# in the data matrix +def randomise_pad_253(pad_value, pad_position): + pseudo_random_number = ((149 * pad_position) % 253) + 1 + randomised = pad_value + pseudo_random_number + if randomised <= 254: + return randomised + else: + return randomised - 254 + + +# REED-SOLOMON ENCODING ROUTINES ===================================== + +# "prod(x,y,log,alog,gf)" returns the product "x" times "y" +def prod(x, y, log, alog, gf): + if x == 0 or y == 0: + return 0 + else: + result = alog[(log[x] + log[y]) % (gf - 1)] + return result + + +# generate the log & antilog lists: +def gen_log_alog(gf, pp): + log = [0] * gf + alog = [0] * gf + + log[0] = 1 - gf + alog[0] = 1 + + for i in range(1, gf): + alog[i] = alog[i - 1] * 2 + + if alog[i] >= gf: + alog[i] = alog[i] ^ pp + + log[alog[i]] = i + + return log, alog + + +# generate the generator polynomial coefficients: +def gen_poly_coeffs(nc, log, alog, gf): + c = [0] * (nc + 1) + c[0] = 1 + + for i in range(1, nc + 1): + c[i] = c[i - 1] + + j = i - 1 + while j >= 1: + c[j] = c[j - 1] ^ prod(c[j], alog[i], log, alog, gf) + j -= 1 + + c[0] = prod(c[0], alog[i], log, alog, gf) + + return c + + +# "ReedSolomon(wd,nd,nc)" takes "nd" data codeword values in wd[] +# and adds on "nc" check codewords, all within GF(gf) where "gf" is a +# power of 2 and "pp" is the value of its prime modulus polynomial */ +def reed_solomon(data, nd, nc): + # parameters of the polynomial arithmetic + gf = 256 # operating on 8-bit codewords -> Galois field = 2^8 = 256 + pp = 301 # prime modulus polynomial for ECC-200 is 0b100101101 = 301 (ISO 16022:2006 5.7.1) + + log, alog = gen_log_alog(gf, pp) + c = gen_poly_coeffs(nc, log, alog, gf) + + for block in data: # for each block of data codewords + + block.extend([0] * (nc + 1)) # extend to make space for the error codewords + + # generate "nc" checkwords in the list block + for i in range(0, nd): + k = block[nd] ^ block[i] + + for j in range(0, nc): + block[nd + j] = block[nd + j + 1] ^ prod( + k, c[nc - j - 1], log, alog, gf + ) + + block.pop() + + return data + + +# MODULE PLACEMENT ROUTINES=========================================== +# These routines take a steam of codewords, and place them into the +# DataMatrix in accordance with Annex F of BS ISO/IEC 16022:2006 + + +def bit(byte, bit_ch): + """bit() returns the bit'th bit of the byte""" + # the MSB is bit 1, LSB is bit 8 + return (byte >> (8 - bit_ch)) % 2 + + +def module(array, nrow, ncol, row, col, bit_ch): + """place a given bit with appropriate wrapping within array""" + if row < 0: + row = row + nrow + col = col + 4 - ((nrow + 4) % 8) + + if col < 0: + col = col + ncol + row = row + 4 - ((ncol + 4) % 8) + + array[row][col] = bit_ch + + +def place_square(case, array, nrow, ncol, row, col, char): + """Populate corner cases (0-3) and utah case (-1)""" + for i in range(8): + x, y = [ + [ + (row - 1, 0), + (row - 1, 1), + (row - 1, 2), + (0, col - 2), + (0, col - 1), + (1, col - 1), + (2, col - 1), + (3, col - 1), + ], + [ + (row - 3, 0), + (row - 2, 0), + (row - 1, 0), + (0, col - 4), + (0, col - 3), + (0, col - 2), + (0, col - 1), + (1, col - 1), + ], + [ + (row - 3, 0), + (row - 2, 0), + (row - 1, 0), + (0, col - 2), + (0, col - 1), + (1, col - 1), + (2, col - 1), + (3, col - 1), + ], + [ + (row - 1, 0), + (row - 1, col - 1), + (0, col - 3), + (0, col - 2), + (0, col - 1), + (1, col - 3), + (1, col - 2), + (1, col - 1), + ], + # "utah" places the 8 bits of a utah-shaped symbol character in ECC200 + [ + (row - 2, col - 2), + (row - 2, col - 1), + (row - 1, col - 2), + (row - 1, col - 1), + (row - 1, col), + (row, col - 2), + (row, col - 1), + (row, col), + ], + ][case][i] + module(array, nrow, ncol, x, y, bit(char, i + 1)) + return 1 + + +def place_bits(data, nrow, ncol): + """fill an nrow x ncol array with the bits from the codewords in data.""" + # initialise and fill with -1's (invalid value) + array = [[INVALID_BIT] * ncol for i in range(nrow)] + # Starting in the correct location for character #1, bit 8,... + char = 0 + row = 4 + col = 0 + while True: + + # first check for one of the special corner cases, then... + if (row == nrow) and (col == 0): + char += place_square(0, array, nrow, ncol, nrow, ncol, data[char]) + elif (row == nrow - 2) and (col == 0) and (ncol % 4): + char += place_square(1, array, nrow, ncol, nrow, ncol, data[char]) + elif (row == nrow - 2) and (col == 0) and (ncol % 8 == 4): + char += place_square(2, array, nrow, ncol, nrow, ncol, data[char]) + elif (row == nrow + 4) and (col == 2) and ((ncol % 8) == 0): + char += place_square(3, array, nrow, ncol, nrow, ncol, data[char]) + + # sweep upward diagonally, inserting successive characters,... + while (row >= 0) and (col < ncol): + if (row < nrow) and (col >= 0) and (array[row][col] == INVALID_BIT): + char += place_square(-1, array, nrow, ncol, row, col, data[char]) + row -= 2 + col += 2 + + row += 1 + col += 3 + + # & then sweep downward diagonally, inserting successive characters,... + while (row < nrow) and (col >= 0): + if (row >= 0) and (col < ncol) and (array[row][col] == INVALID_BIT): + char += place_square(-1, array, nrow, ncol, row, col, data[char]) + row += 2 + col -= 2 + + row += 3 + col += 1 + + # ... until the entire array is scanned + if not ((row < nrow) or (col < ncol)): + break + + # Lastly, if the lower righthand corner is untouched, fill in fixed pattern */ + if array[nrow - 1][ncol - 1] == INVALID_BIT: + array[nrow - 1][ncol - 2] = 0 + array[nrow - 1][ncol - 1] = 1 + array[nrow - 2][ncol - 1] = 0 + array[nrow - 2][ncol - 2] = 1 + + return array # return the array of 1's and 0's + + +def add_finder_pattern(array, data_nrow, data_ncol, reg_row, reg_col): + # get the total size of the datamatrix + nrow = (data_nrow + 2) * reg_row + ncol = (data_ncol + 2) * reg_col + + datamatrix = [[0] * ncol for i in range(nrow)] # initialise and fill with 0's + + for i in range(reg_col): # for each column of data regions + for j in range(nrow): + datamatrix[j][i * (data_ncol + 2)] = 1 # vertical black bar on left + datamatrix[j][i * (data_ncol + 2) + data_ncol + 1] = ( + j % 2 + ) # alternating blocks + + for i in range(reg_row): # for each row of data regions + for j in range(ncol): + datamatrix[i * (data_nrow + 2) + data_nrow + 1][ + j + ] = 1 # horizontal black bar at bottom + datamatrix[i * (data_nrow + 2)][j] = (j + 1) % 2 # alternating blocks + + for i in range(data_nrow * reg_row): + for j in range(data_ncol * reg_col): + # offset by 1, plus two for every addition block + dest_col = j + 1 + 2 * (j // data_ncol) + dest_row = i + 1 + 2 * (i // data_nrow) + + datamatrix[dest_row][dest_col] = array[i][ + j + ] # transfer from the plain bit array + + return datamatrix + + +class DataMatrix(inkex.GenerateExtension): + container_label = "DataMatrix" + + def add_arguments(self, pars): + pars.add_argument("--text", default="Inkscape") + pars.add_argument("--symbol", type=self.arg_symbols, required=True) + pars.add_argument("--size", type=int, default=4) + + @staticmethod + def arg_symbols(value): + """Turn a symbol key into matrix metrics""" + try: + return SYMBOLS[value] + except KeyError: + raise inkex.AbortExtension(_("Invalid symbol size.")) + + def generate(self): + size = str(self.options.size) + style = inkex.Style({"stroke": "none", "stroke-width": "1", "fill": "#000000"}) + attribs = {"style": str(style), "height": size, "width": size} + + if not self.options.text: + raise inkex.AbortExtension(_("Please enter an input string.")) + + # create a 2d list corresponding to the 1's and 0s of the DataMatrix + encoded = self.encode(self.options.text, *self.options.symbol) + for x, y in self.render_data_matrix(encoded): + attribs.update({"x": str(x), "y": str(y)}) + yield Rectangle(**attribs) + + def encode( + self, text, nrow, ncol, data_nrow, data_ncol, reg_row, reg_col, nd, nc, inter + ): + """ + Take an input string and convert it to a sequence (or sequences) + of codewords as specified in ISO/IEC 16022:2006 (section 5.2.3) + """ + # generate the codewords including padding and ECC + codewords = get_codewords(text, nd, nc, inter, nrow == 144) + + # break up into separate arrays if more than one DataMatrix is needed + module_arrays = [] + for codeword_stream in codewords: # for each datamatrix + # place the codewords' bits across the array as modules + bit_array = place_bits( + codeword_stream, data_nrow * reg_row, data_ncol * reg_col + ) + # add finder patterns around the modules + module_arrays.append( + add_finder_pattern(bit_array, data_nrow, data_ncol, reg_row, reg_col) + ) + + return module_arrays + + def render_data_matrix(self, module_arrays): + """turn a 2D array of 1's and 0's into a set of black squares""" + ncol = self.options.symbol[1] + size = self.options.size + spacing = ncol * size * 1.5 + for i, line in enumerate(module_arrays): + height = len(line) + width = len(line[0]) + + for y in range(height): # loop over all the modules in the datamatrix + for x in range(width): + if line[y][x] == 1: # A binary 1 is a filled square + yield (x * size + i * spacing, y * size) + elif line[y][x] == INVALID_BIT: # we have an invalid bit value + inkex.errormsg(_("Invalid bit value, {}!").format(line[y][x])) + + +if __name__ == "__main__": + DataMatrix().run() |