1# verhoeff.py - functions for performing the Verhoeff checksum
2#
3# Copyright (C) 2010-2015 Arthur de Jong
4#
5# This library is free software; you can redistribute it and/or
6# modify it under the terms of the GNU Lesser General Public
7# License as published by the Free Software Foundation; either
8# version 2.1 of the License, or (at your option) any later version.
9#
10# This library is distributed in the hope that it will be useful,
11# but WITHOUT ANY WARRANTY; without even the implied warranty of
12# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13# Lesser General Public License for more details.
14#
15# You should have received a copy of the GNU Lesser General Public
16# License along with this library; if not, write to the Free Software
17# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
18# 02110-1301 USA
19
20"""The Verhoeff algorithm.
21
22The Verhoeff algorithm is a checksum algorithm that should catch most common
23(typing) errors in numbers. The algorithm uses two tables for permutations
24and multiplications and as a result is more complex than the Luhn algorithm.
25
26More information:
27
28* https://en.wikipedia.org/wiki/Verhoeff_algorithm
29* https://en.wikibooks.org/wiki/Algorithm_Implementation/Checksums/Verhoeff_Algorithm
30
31The module provides the checksum() function to calculate the Verhoeff
32checksum a calc_check_digit() function to generate a check digit that can be
33append to an existing number to result in a number with a valid checksum and
34validation functions.
35
36>>> validate('1234')
37Traceback (most recent call last):
38    ...
39InvalidChecksum: ...
40>>> checksum('1234')
411
42>>> calc_check_digit('1234')
43'0'
44>>> validate('12340')
45'12340'
46"""
47
48from stdnum.exceptions import *
49
50
51# These are the multiplication and permutation tables used in the
52# Verhoeff algorithm.
53
54_multiplication_table = (
55    (0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
56    (1, 2, 3, 4, 0, 6, 7, 8, 9, 5),
57    (2, 3, 4, 0, 1, 7, 8, 9, 5, 6),
58    (3, 4, 0, 1, 2, 8, 9, 5, 6, 7),
59    (4, 0, 1, 2, 3, 9, 5, 6, 7, 8),
60    (5, 9, 8, 7, 6, 0, 4, 3, 2, 1),
61    (6, 5, 9, 8, 7, 1, 0, 4, 3, 2),
62    (7, 6, 5, 9, 8, 2, 1, 0, 4, 3),
63    (8, 7, 6, 5, 9, 3, 2, 1, 0, 4),
64    (9, 8, 7, 6, 5, 4, 3, 2, 1, 0))
65
66_permutation_table = (
67    (0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
68    (1, 5, 7, 6, 2, 8, 3, 0, 9, 4),
69    (5, 8, 0, 3, 7, 9, 6, 1, 4, 2),
70    (8, 9, 1, 6, 0, 4, 3, 5, 2, 7),
71    (9, 4, 5, 3, 1, 2, 6, 8, 7, 0),
72    (4, 2, 8, 6, 5, 7, 3, 9, 0, 1),
73    (2, 7, 9, 3, 8, 0, 6, 4, 1, 5),
74    (7, 0, 4, 6, 9, 1, 3, 2, 5, 8))
75
76
77def checksum(number):
78    """Calculate the Verhoeff checksum over the provided number. The checksum
79    is returned as an int. Valid numbers should have a checksum of 0."""
80    # transform number list
81    number = tuple(int(n) for n in reversed(str(number)))
82    # calculate checksum
83    check = 0
84    for i, n in enumerate(number):
85        check = _multiplication_table[check][_permutation_table[i % 8][n]]
86    return check
87
88
89def validate(number):
90    """Check if the number provided passes the Verhoeff checksum."""
91    if not bool(number):
92        raise InvalidFormat()
93    try:
94        valid = checksum(number) == 0
95    except Exception:
96        raise InvalidFormat()
97    if not valid:
98        raise InvalidChecksum()
99    return number
100
101
102def is_valid(number):
103    """Check if the number provided passes the Verhoeff checksum."""
104    try:
105        return bool(validate(number))
106    except ValidationError:
107        return False
108
109
110def calc_check_digit(number):
111    """Calculate the extra digit that should be appended to the number to
112    make it a valid number."""
113    return str(_multiplication_table[checksum(str(number) + '0')].index(0))
114