Chris Morgan  ›  Git  ›  verhoeff  ›  blob
69fb5572c1edf4fe721000d27de30db217301a83
[verhoeff] / src / lib.rs
1 //! An implementation of the Verhoeff algorithm.
2 //!
3 //! This checksum algorithm is not particularly common (the simpler and somewhat inferior Luhn
4 //! algorithm is much more widely used, e.g. in credit card numbers), but it definitely gets some
5 //! use; for example, India’s Aadhaar biometric identity system uses 12-digit numbers as the ID
6 //! number, with the final digit being a Verhoeff checksum.
7 //!
8 //! Background reading: <https://en.wikipedia.org/wiki/Verhoeff_algorithm>
9
10 #![cfg_attr(not(feature = "std"), no_std)]
11
12 #[cfg(feature = "alloc")]
13 extern crate alloc;
14
15 /// The multiplication table.
16 static D: [[u8; 10]; 10] = [
17 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
18 [1, 2, 3, 4, 0, 6, 7, 8, 9, 5],
19 [2, 3, 4, 0, 1, 7, 8, 9, 5, 6],
20 [3, 4, 0, 1, 2, 8, 9, 5, 6, 7],
21 [4, 0, 1, 2, 3, 9, 5, 6, 7, 8],
22 [5, 9, 8, 7, 6, 0, 4, 3, 2, 1],
23 [6, 5, 9, 8, 7, 1, 0, 4, 3, 2],
24 [7, 6, 5, 9, 8, 2, 1, 0, 4, 3],
25 [8, 7, 6, 5, 9, 3, 2, 1, 0, 4],
26 [9, 8, 7, 6, 5, 4, 3, 2, 1, 0],
27 ];
28
29 /// The permutation table.
30 static P: [[u8; 10]; 8] = [
31 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
32 [1, 5, 7, 6, 2, 8, 3, 0, 9, 4],
33 [5, 8, 0, 3, 7, 9, 6, 1, 4, 2],
34 [8, 9, 1, 6, 0, 4, 3, 5, 2, 7],
35 [9, 4, 5, 3, 1, 2, 6, 8, 7, 0],
36 [4, 2, 8, 6, 5, 7, 3, 9, 0, 1],
37 [2, 7, 9, 3, 8, 0, 6, 4, 1, 5],
38 [7, 0, 4, 6, 9, 1, 3, 2, 5, 8],
39 ];
40
41 /// The inverse table.
42 static INV: [u8; 10] = [0, 4, 3, 2, 1, 5, 6, 7, 8, 9];
43
44 /// Methods to perform the Verhoeff algorithm.
45 ///
46 /// This is implemented for strings (which must contain only the ASCII digits 0–9) and u8 slices
47 /// (which must contain only the numbers 0–9).
48 ///
49 /// ## Examples
50 ///
51 /// ```
52 /// use verhoeff::Verhoeff;
53 /// assert_eq!("12345".calculate_verhoeff_check_digit(), 1);
54 /// assert!("123451".validate_verhoeff_check_digit());
55 /// ```
56 pub trait Verhoeff {
57 /// Confirm that the digits are valid and that the last is the correct check digit.
58 ///
59 /// If any digit is not valid (a character other than ASCII digits 0–9 in strings, or a
60 /// number greater than nine in `u8` slices), it returns false.
61 fn validate_verhoeff_check_digit(&self) -> bool;
62
63 /// Calculate the check digit for this input.
64 ///
65 /// If any digit is not valid (a character other than ASCII digits 0–9 in strings, or a
66 /// number greater than nine in `u8` slices), it will panic.
67 ///
68 /// The return value is an integer in the range 0–9.
69 fn calculate_verhoeff_check_digit(&self) -> u8;
70 }
71
72 impl Verhoeff for str {
73 fn validate_verhoeff_check_digit(&self) -> bool {
74 let mut c = 0;
75 for (i, digit) in self.bytes().rev().enumerate() {
76 let digit = match digit {
77 b'0'..=b'9' => digit - b'0',
78 _ => return false,
79 };
80 c = D[c][P[i % 8][digit as usize] as usize] as usize;
81 }
82
83 c == 0
84 }
85
86 fn calculate_verhoeff_check_digit(&self) -> u8 {
87 let mut c = 0;
88 for (i, digit) in self.bytes().rev().enumerate() {
89 assert!(
90 matches!(digit, b'0'..=b'9'),
91 "number string contains a non-digit character",
92 );
93 c = D[c][P[(i + 1) % 8][(digit - b'0') as usize] as usize] as usize;
94 }
95
96 INV[c]
97 }
98 }
99
100 impl Verhoeff for [u8] {
101 fn validate_verhoeff_check_digit(&self) -> bool {
102 let mut c = 0;
103 for (i, &digit) in self.iter().rev().enumerate() {
104 if digit > 9 {
105 return false;
106 }
107 c = D[c][P[i % 8][digit as usize] as usize] as usize;
108 }
109
110 c == 0
111 }
112
113 fn calculate_verhoeff_check_digit(&self) -> u8 {
114 let mut c = 0;
115 for (i, &digit) in self.iter().rev().enumerate() {
116 assert!(digit < 10, "number sequence contains a value above nine");
117 c = D[c][P[(i + 1) % 8][digit as usize] as usize] as usize;
118 }
119
120 INV[c]
121 }
122 }
123
124 /// A convenience trait for mutable methods pertaining to the Verhoeff algorithm.
125 ///
126 #[cfg_attr(
127 feature = "alloc",
128 doc = " This is implemented for `String` and `Vec<u8>`.",
129 )]
130 #[cfg_attr(
131 not(feature = "alloc"),
132 doc = " This is normally implemented for `String` and `Vec<u8>`, but you’ve you’ve disabled \
133 the alloc feature, so it’s not implemented on anything out of the box.",
134 )]
135 pub trait VerhoeffMut {
136 /// A convenience method to apply the Verhoeff algorithm in-place.
137 ///
138 /// ## Example
139 ///
140 #[cfg_attr(feature = "alloc", doc = " ```")]
141 #[cfg_attr(not(feature = "alloc"), doc = " ```rust,ignore")]
142 /// use verhoeff::VerhoeffMut;
143 /// let mut digits = String::from("12345");
144 /// digits.push_verhoeff_check_digit();
145 /// assert_eq!(digits, "123451");
146 #[doc = " ```"] // just to keep the Vim syntax highlighter happy. Silly, huh?
147 fn push_verhoeff_check_digit(&mut self);
148 }
149
150 #[cfg(feature = "alloc")]
151 impl VerhoeffMut for alloc::string::String {
152 fn push_verhoeff_check_digit(&mut self) {
153 self.push(char::from(b'0' + self.calculate_verhoeff_check_digit()));
154 }
155 }
156
157 #[cfg(feature = "alloc")]
158 impl VerhoeffMut for alloc::vec::Vec<u8> {
159 /// A convenience method to apply the Verhoeff algorithm in-place.
160 ///
161 /// ## Example
162 ///
163 /// ```
164 /// use verhoeff::VerhoeffMut;
165 /// let mut digits = vec![1, 2, 3, 4, 5];
166 /// digits.push_verhoeff_check_digit();
167 /// assert_eq!(digits, [1, 2, 3, 4, 5, 1]);
168 /// ```
169 fn push_verhoeff_check_digit(&mut self) {
170 self.push(self.calculate_verhoeff_check_digit());
171 }
172 }
173
174 /// A convenience method to calculate the Verhoeff algorithm check digit.
175 ///
176 /// You can pass in a `&str` or a `&[u8]`, and get back a number in the range 0–9.
177 ///
178 /// This is equivalent to calling [`Verhoeff::calculate_verhoeff_check_digit`].
179 /// It will panic if the input is not comprised of appropriate digits.
180 #[inline]
181 pub fn calculate<T: Verhoeff + ?Sized>(input: &T) -> u8 {
182 input.calculate_verhoeff_check_digit()
183 }
184
185 /// A convenience method to validate against the Verhoeff algorithm.
186 ///
187 /// The check digit is presumed to be at the end of the input.
188 ///
189 /// You can pass in a `&str` or a `&[u8]`.
190 ///
191 /// This is equivalent to calling [`Verhoeff::validate_verhoeff_check_digit`].
192 /// It will return false if the input is not comprised of appropriate digits.
193 #[inline]
194 pub fn validate<T: Verhoeff + ?Sized>(input: &T) -> bool {
195 input.validate_verhoeff_check_digit()
196 }
197
198 #[test]
199 fn test() {
200 for full in [
201 "0",
202 "2363",
203 "758722",
204 "123451",
205 "1428570",
206 "1234567890120",
207 "84736430954837284567892",
208 ] {
209 let sans_check_digit = &full[..full.len() - 1];
210 let expected_check_digit = full.chars().last().unwrap() as u32 as u8 - b'0';
211 let actual_check_digit = calculate(sans_check_digit);
212 if expected_check_digit != actual_check_digit {
213 panic!(
214 "On {}, expected check digit {} but calculated {}",
215 sans_check_digit, expected_check_digit, actual_check_digit,
216 );
217 }
218 if !validate(full) {
219 panic!("{} failed to validate", full);
220 }
221 #[cfg(feature = "alloc")]
222 {
223 let mut new = alloc::string::String::from(sans_check_digit);
224 new.push_verhoeff_check_digit();
225 assert_eq!(new, full);
226 }
227 }
228 for full in [
229 &[0],
230 &[2, 3, 6, 3],
231 &[7, 5, 8, 7, 2, 2],
232 &[1, 2, 3, 4, 5, 1],
233 &[1, 4, 2, 8, 5, 7, 0],
234 &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 0],
235 &[
236 8, 4, 7, 3, 6, 4, 3, 0, 9, 5, 4, 8, 3, 7, 2, 8, 4, 5, 6, 7, 8, 9, 2,
237 ],
238 ] as [&[u8]; 7] {
239 let sans_check_digit = &full[..full.len() - 1];
240 let expected_check_digit = *full.iter().last().unwrap();
241 let actual_check_digit = calculate(sans_check_digit);
242 if expected_check_digit != actual_check_digit {
243 panic!(
244 "On {:?}, expected check digit {:?} but calculated {:?}",
245 sans_check_digit, expected_check_digit, actual_check_digit,
246 );
247 }
248 if !validate(full) {
249 panic!("{:?} failed to validate", full);
250 }
251 #[cfg(feature = "alloc")]
252 {
253 let mut new = alloc::vec::Vec::from(sans_check_digit);
254 new.push_verhoeff_check_digit();
255 assert_eq!(new, full);
256 }
257 }
258 assert!(!validate("122451"));
259 assert!(!"128451".validate_verhoeff_check_digit());
260 assert!(![1, 2, 4, 3, 5, 1].validate_verhoeff_check_digit());
261 }
262
263 #[test]
264 fn malformed_inputs_1() {
265 assert!([].validate_verhoeff_check_digit());
266 assert!("".validate_verhoeff_check_digit());
267 assert!(![1, 2, 3, 4, 10, 5, 6].validate_verhoeff_check_digit());
268 assert!(!validate("1234∞56"));
269 }
270
271 #[test]
272 #[should_panic]
273 fn malformed_inputs_2() {
274 [1, 2, 3, 4, 10, 5, 6].calculate_verhoeff_check_digit();
275 }
276
277 #[test]
278 #[should_panic]
279 fn malformed_inputs_3() {
280 calculate("1234∞56");
281 }