Python version of Verhoeff alphanumeric check digit algorithm

verhoeff_alpha.py

#!/usr/bin/env python

"""
Python port of alphanumeric derivative of Verhoeff check digit algorithm.

Ported from: https://gist.github.com/mwgamera/1088656
"""

N  = 18
N2 = N * 2

class Verhoeff(object):
    
    def __init__(self):
        
        # Multiplication table
        self.d18_op = [0 for i in xrange(N2*N2)]
        for i in xrange(N):
            for j in xrange(N):
                self.d18_op[N2*i+j] = (i + j) % N
        for i in xrange(N):
            for j in xrange(N, N2):
                self.d18_op[N2*i+j] = N + (i + j) % N
        for i in xrange(N, N2):
            for j in xrange(N):
                self.d18_op[N2*i+j] = N + (i - j) % N
        for i in xrange(N, N2):
            for j in xrange(N, N2):
                self.d18_op[N2*i+j] = (N + i - j) % N
        
        # Inverse table
        self.d18_inv = [0 for i in xrange(N2)]
        for i in xrange(1, N):
            self.d18_inv[i] = N - i
        for i in xrange(N, N2):
            self.d18_inv[i] = i
        
        # Permutation table
        self.perm = [[] for i in xrange(N2)]
        p = [29,0,32,11,35,20,7,27,2,4,19,28,30,1,5,12,3,9,16,
             22,6,33,8,24,26,21,14,10,34,31,15,25,17,13,23,18]
        b = [False for i in xrange(len(p))]
        i = 0
        while i < len(b):
            h = [None]
            c = h
            ln = 0
            while not b[i]:
                cc = [None, p[i]]
                c[0] = cc
                c = cc
                b[i] = True
                i = p[i]
                ln += 1
            c[0] = h[0]
            for j in xrange(ln):
                pp = [0 for x in xrange(ln)]
                self.perm[c[1]] = pp
                for k in xrange(ln):
                    pp[k] = c[1]
                    c = c[0]
                c = c[0]
            while i < len(b) and b[i] == True:
                i += 1
        
        # Alphanumeric to numeric conversion table
        self.a2i = [0xff for i in xrange(256)]
        for i in xrange(0x30, 0x3a): self.a2i[i] = i - 0x30
        for i in xrange(0x41, 0x5b): self.a2i[i] = i - 0x41 + 10
        for i in xrange(0x61, 0x7b): self.a2i[i] = i - 0x61 + 10
        
        # Numeric to alphanumeric conversion table
        self.i2a = [0 for i in xrange(N2)]
        for i in xrange(0, 10):  self.i2a[i] = i + 0x30
        for i in xrange(10, N2): self.i2a[i] = i + 0x41 - 10
    
    def op(self, i, j):
        """ Group operation """
        return self.d18_op[N2*i+j]
    
    def nperm(self, i , n):
        """ Compute n-th application of the permutation """
        return self.perm[i][n % len(self.perm[i])]
    
    def is_valid(self, s):
        return self.verify(s) == 0
    
    def verify(self, s):
        """ Verify correctness of check digit, returns 0 if correct """
        i = 0
        c = 0
        for ch in reversed(s):
            ch = self.a2i[ord(ch) & 0xff]
            if ch != 0xff:
                c = self.op(c, self.nperm(ch, i))
                i += 1
        return c
    
    def create(self, s):
        """ Create a new check digit """
        i = 1
        c = 0
        for ch in reversed(s):
            ch = self.a2i[ord(ch) & 0xff]
            if ch != 0xff:
                c = self.op(c, self.nperm(ch, i))
                i += 1
        return self.i2a[self.d18_inv[c]]
    
    def append(self, s):
        """ Append check digit to the given string """
        return s + chr(self.create(s))

def main():
    
    v = Verhoeff()
    assert v.create('ABCDEF') == 67
    assert v.append('123ABCDEF') == '123ABCDEFD'
    assert v.append('ABCDEF')    == 'ABCDEFC'
    
    assert v.verify('ABCDEFC')   == 0

if __name__ == '__main__':
    main()