From 67417456c81ccc241cb0e7257d6ca3a955e1d29e Mon Sep 17 00:00:00 2001 From: Chris Morgan Date: Mon, 3 Jan 2022 23:07:04 +1100 Subject: [PATCH] verhoeff 1.0.0 --- .gitignore | 2 + COPYRIGHT | 17 ++++ Cargo.toml | 14 +++ README.md | 49 ++++++++++ src/lib.rs | 281 +++++++++++++++++++++++++++++++++++++++++++++++++++++ test | 10 ++ 6 files changed, 373 insertions(+) create mode 100644 .gitignore create mode 100644 COPYRIGHT create mode 100644 Cargo.toml create mode 100644 README.md create mode 100644 src/lib.rs create mode 100755 test diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..96ef6c0 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +/target +Cargo.lock diff --git a/COPYRIGHT b/COPYRIGHT new file mode 100644 index 0000000..2cced42 --- /dev/null +++ b/COPYRIGHT @@ -0,0 +1,17 @@ +Copyright © 2022 Chris Morgan + +This project is distributed under the terms of three different licenses, +at your choice: + +- Blue Oak Model License 1.0.0: https://blueoakcouncil.org/license/1.0.0 +- MIT License: https://opensource.org/licenses/MIT +- Apache License, Version 2.0: https://www.apache.org/licenses/LICENSE-2.0 + +If you do not have particular cause to select the MIT or the Apache-2.0 +license, Chris Morgan recommends that you select BlueOak-1.0.0, which is +better and simpler than both MIT and Apache-2.0, which are only offered +due to their greater recognition and their conventional use in the Rust +ecosystem. (BlueOak-1.0.0 was only published in March 2019.) + +When using this code, ensure you comply with the terms of at least one of +these licenses. diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..2266ef0 --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,14 @@ +[package] +name = "verhoeff" +description = "The Verhoeff algorithm, for number checksums" +authors = ["Chris Morgan "] +license = "BlueOak-1.0.0 OR MIT OR Apache-2.0" +version = "1.0.0" +edition = "2021" +categories = ["algorithms"] +repository = "https://gitlab.com/chris-morgan/verhoeff" + +[features] +default = ["std"] +std = ["alloc"] +alloc = [] diff --git a/README.md b/README.md new file mode 100644 index 0000000..8e9e030 --- /dev/null +++ b/README.md @@ -0,0 +1,49 @@ +# The Verhoeff algorithm, for number checksums + +An implementation of the Verhoeff algorithm. + +This checksum algorithm is not particularly common (the simpler and somewhat inferior Luhn +algorithm is much more widely used, e.g. in credit card numbers), but it definitely gets some +use; for example, India’s Aadhaar biometric identity system uses 12-digit numbers as the ID +number, with the final digit being a Verhoeff checksum. + +Background reading: + +---- + +## Examples + +```rust +use verhoeff::Verhoeff; +assert_eq!("12345".calculate_verhoeff_check_digit(), 1); +assert!(verhoeff::validate(&[1, 2, 3, 4, 5, 1])); +assert!(!"123456".validate_verhoeff_check_digit()); + +use verhoeff::VerhoeffMut; +let mut digits = vec![1, 2, 3, 4, 5]; +digits.push_verhoeff_check_digit(); +assert_eq!(digits, [1, 2, 3, 4, 5, 1]); +``` + +## Cargo.toml usage and features + +Standard: + +```toml +[dependencies] +verhoeff = "1" +``` + +Disabling the `std` feature to get `#![no_std]`, but retaining `alloc` in order to not lose any functionality: + +```toml +[dependencies] +verhoeff = { version = "1", default-features = false, features = ["alloc"] } +``` + +Disabling the `std` feature without reenabling `alloc`, thereby losing the implementations of `VerhoeffMut` (`push_verhoeff_check_digit`) for `String` and `Vec`: + +```toml +[dependencies] +verhoeff = { version = "1", default-features = false } +``` diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..69fb557 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,281 @@ +//! An implementation of the Verhoeff algorithm. +//! +//! This checksum algorithm is not particularly common (the simpler and somewhat inferior Luhn +//! algorithm is much more widely used, e.g. in credit card numbers), but it definitely gets some +//! use; for example, India’s Aadhaar biometric identity system uses 12-digit numbers as the ID +//! number, with the final digit being a Verhoeff checksum. +//! +//! Background reading: + +#![cfg_attr(not(feature = "std"), no_std)] + +#[cfg(feature = "alloc")] +extern crate alloc; + +/// The multiplication table. +static D: [[u8; 10]; 10] = [ + [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], + [1, 2, 3, 4, 0, 6, 7, 8, 9, 5], + [2, 3, 4, 0, 1, 7, 8, 9, 5, 6], + [3, 4, 0, 1, 2, 8, 9, 5, 6, 7], + [4, 0, 1, 2, 3, 9, 5, 6, 7, 8], + [5, 9, 8, 7, 6, 0, 4, 3, 2, 1], + [6, 5, 9, 8, 7, 1, 0, 4, 3, 2], + [7, 6, 5, 9, 8, 2, 1, 0, 4, 3], + [8, 7, 6, 5, 9, 3, 2, 1, 0, 4], + [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], +]; + +/// The permutation table. +static P: [[u8; 10]; 8] = [ + [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], + [1, 5, 7, 6, 2, 8, 3, 0, 9, 4], + [5, 8, 0, 3, 7, 9, 6, 1, 4, 2], + [8, 9, 1, 6, 0, 4, 3, 5, 2, 7], + [9, 4, 5, 3, 1, 2, 6, 8, 7, 0], + [4, 2, 8, 6, 5, 7, 3, 9, 0, 1], + [2, 7, 9, 3, 8, 0, 6, 4, 1, 5], + [7, 0, 4, 6, 9, 1, 3, 2, 5, 8], +]; + +/// The inverse table. +static INV: [u8; 10] = [0, 4, 3, 2, 1, 5, 6, 7, 8, 9]; + +/// Methods to perform the Verhoeff algorithm. +/// +/// This is implemented for strings (which must contain only the ASCII digits 0–9) and u8 slices +/// (which must contain only the numbers 0–9). +/// +/// ## Examples +/// +/// ``` +/// use verhoeff::Verhoeff; +/// assert_eq!("12345".calculate_verhoeff_check_digit(), 1); +/// assert!("123451".validate_verhoeff_check_digit()); +/// ``` +pub trait Verhoeff { + /// Confirm that the digits are valid and that the last is the correct check digit. + /// + /// If any digit is not valid (a character other than ASCII digits 0–9 in strings, or a + /// number greater than nine in `u8` slices), it returns false. + fn validate_verhoeff_check_digit(&self) -> bool; + + /// Calculate the check digit for this input. + /// + /// If any digit is not valid (a character other than ASCII digits 0–9 in strings, or a + /// number greater than nine in `u8` slices), it will panic. + /// + /// The return value is an integer in the range 0–9. + fn calculate_verhoeff_check_digit(&self) -> u8; +} + +impl Verhoeff for str { + fn validate_verhoeff_check_digit(&self) -> bool { + let mut c = 0; + for (i, digit) in self.bytes().rev().enumerate() { + let digit = match digit { + b'0'..=b'9' => digit - b'0', + _ => return false, + }; + c = D[c][P[i % 8][digit as usize] as usize] as usize; + } + + c == 0 + } + + fn calculate_verhoeff_check_digit(&self) -> u8 { + let mut c = 0; + for (i, digit) in self.bytes().rev().enumerate() { + assert!( + matches!(digit, b'0'..=b'9'), + "number string contains a non-digit character", + ); + c = D[c][P[(i + 1) % 8][(digit - b'0') as usize] as usize] as usize; + } + + INV[c] + } +} + +impl Verhoeff for [u8] { + fn validate_verhoeff_check_digit(&self) -> bool { + let mut c = 0; + for (i, &digit) in self.iter().rev().enumerate() { + if digit > 9 { + return false; + } + c = D[c][P[i % 8][digit as usize] as usize] as usize; + } + + c == 0 + } + + fn calculate_verhoeff_check_digit(&self) -> u8 { + let mut c = 0; + for (i, &digit) in self.iter().rev().enumerate() { + assert!(digit < 10, "number sequence contains a value above nine"); + c = D[c][P[(i + 1) % 8][digit as usize] as usize] as usize; + } + + INV[c] + } +} + +/// A convenience trait for mutable methods pertaining to the Verhoeff algorithm. +/// +#[cfg_attr( + feature = "alloc", + doc = " This is implemented for `String` and `Vec`.", +)] +#[cfg_attr( + not(feature = "alloc"), + doc = " This is normally implemented for `String` and `Vec`, but you’ve you’ve disabled \ + the alloc feature, so it’s not implemented on anything out of the box.", +)] +pub trait VerhoeffMut { + /// A convenience method to apply the Verhoeff algorithm in-place. + /// + /// ## Example + /// + #[cfg_attr(feature = "alloc", doc = " ```")] + #[cfg_attr(not(feature = "alloc"), doc = " ```rust,ignore")] + /// use verhoeff::VerhoeffMut; + /// let mut digits = String::from("12345"); + /// digits.push_verhoeff_check_digit(); + /// assert_eq!(digits, "123451"); + #[doc = " ```"] // just to keep the Vim syntax highlighter happy. Silly, huh? + fn push_verhoeff_check_digit(&mut self); +} + +#[cfg(feature = "alloc")] +impl VerhoeffMut for alloc::string::String { + fn push_verhoeff_check_digit(&mut self) { + self.push(char::from(b'0' + self.calculate_verhoeff_check_digit())); + } +} + +#[cfg(feature = "alloc")] +impl VerhoeffMut for alloc::vec::Vec { + /// A convenience method to apply the Verhoeff algorithm in-place. + /// + /// ## Example + /// + /// ``` + /// use verhoeff::VerhoeffMut; + /// let mut digits = vec![1, 2, 3, 4, 5]; + /// digits.push_verhoeff_check_digit(); + /// assert_eq!(digits, [1, 2, 3, 4, 5, 1]); + /// ``` + fn push_verhoeff_check_digit(&mut self) { + self.push(self.calculate_verhoeff_check_digit()); + } +} + +/// A convenience method to calculate the Verhoeff algorithm check digit. +/// +/// You can pass in a `&str` or a `&[u8]`, and get back a number in the range 0–9. +/// +/// This is equivalent to calling [`Verhoeff::calculate_verhoeff_check_digit`]. +/// It will panic if the input is not comprised of appropriate digits. +#[inline] +pub fn calculate(input: &T) -> u8 { + input.calculate_verhoeff_check_digit() +} + +/// A convenience method to validate against the Verhoeff algorithm. +/// +/// The check digit is presumed to be at the end of the input. +/// +/// You can pass in a `&str` or a `&[u8]`. +/// +/// This is equivalent to calling [`Verhoeff::validate_verhoeff_check_digit`]. +/// It will return false if the input is not comprised of appropriate digits. +#[inline] +pub fn validate(input: &T) -> bool { + input.validate_verhoeff_check_digit() +} + +#[test] +fn test() { + for full in [ + "0", + "2363", + "758722", + "123451", + "1428570", + "1234567890120", + "84736430954837284567892", + ] { + let sans_check_digit = &full[..full.len() - 1]; + let expected_check_digit = full.chars().last().unwrap() as u32 as u8 - b'0'; + let actual_check_digit = calculate(sans_check_digit); + if expected_check_digit != actual_check_digit { + panic!( + "On {}, expected check digit {} but calculated {}", + sans_check_digit, expected_check_digit, actual_check_digit, + ); + } + if !validate(full) { + panic!("{} failed to validate", full); + } + #[cfg(feature = "alloc")] + { + let mut new = alloc::string::String::from(sans_check_digit); + new.push_verhoeff_check_digit(); + assert_eq!(new, full); + } + } + for full in [ + &[0], + &[2, 3, 6, 3], + &[7, 5, 8, 7, 2, 2], + &[1, 2, 3, 4, 5, 1], + &[1, 4, 2, 8, 5, 7, 0], + &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 0], + &[ + 8, 4, 7, 3, 6, 4, 3, 0, 9, 5, 4, 8, 3, 7, 2, 8, 4, 5, 6, 7, 8, 9, 2, + ], + ] as [&[u8]; 7] { + let sans_check_digit = &full[..full.len() - 1]; + let expected_check_digit = *full.iter().last().unwrap(); + let actual_check_digit = calculate(sans_check_digit); + if expected_check_digit != actual_check_digit { + panic!( + "On {:?}, expected check digit {:?} but calculated {:?}", + sans_check_digit, expected_check_digit, actual_check_digit, + ); + } + if !validate(full) { + panic!("{:?} failed to validate", full); + } + #[cfg(feature = "alloc")] + { + let mut new = alloc::vec::Vec::from(sans_check_digit); + new.push_verhoeff_check_digit(); + assert_eq!(new, full); + } + } + assert!(!validate("122451")); + assert!(!"128451".validate_verhoeff_check_digit()); + assert!(![1, 2, 4, 3, 5, 1].validate_verhoeff_check_digit()); +} + +#[test] +fn malformed_inputs_1() { + assert!([].validate_verhoeff_check_digit()); + assert!("".validate_verhoeff_check_digit()); + assert!(![1, 2, 3, 4, 10, 5, 6].validate_verhoeff_check_digit()); + assert!(!validate("1234∞56")); +} + +#[test] +#[should_panic] +fn malformed_inputs_2() { + [1, 2, 3, 4, 10, 5, 6].calculate_verhoeff_check_digit(); +} + +#[test] +#[should_panic] +fn malformed_inputs_3() { + calculate("1234∞56"); +} diff --git a/test b/test new file mode 100755 index 0000000..9181a3f --- /dev/null +++ b/test @@ -0,0 +1,10 @@ +#!/bin/sh +set -e +export RUSTFLAGS="-D warnings" +for release in "" "--release"; do + for subcommand in clippy test doc; do + for features in "" "--no-default-features" "--no-default-features --features alloc"; do + cargo $subcommand $release $features + done + done +done -- 2.42.0