One of the digits of your credit card number is not like the rest of them: it’s purpose is to check for value correctness, this way any website or form knows what if checksum matches - the value was typed in correctly. Or you are lucky with a typo because it’s not a very good checksum - it was designed to be easy to calculate on a mechanical device and been sticking around mostly for historical reasons.

To check if a number is valid according to Luhn checksum you would go from right to left, double every second digit, add all the digits together, if result ends with 0 - checksum matches, if it ends with some other value - it does not.

For example let’s check the number 1594: write down the number as a bunch of digits

1 5 9 4

double every second digit from the right

2 5 18 4

add all the digits

2 + 5 + 1 + 8 + 4 = 20

ends with 0, so checksum is valid

Three key optimizations help to calculate it fast:

  • You can split longer sums into short ones
  • You can skip second splitting into digits by doing multiplication as usual and adding number of digits above 5 to the total
  • SWAR can to perform a bunch of operations on individual digits at once

To illustrate first optimization let’s calculate 1 5 9 4 sum in two parts

1 5 => 2 5 => 2 + 5 = 7
9 4 => 18 4 => 1 + 8 + 4 = 13
7 + 13 = 20 - checksum is valid

to illustrate the second one

// digits themselves
1 5 9 4 => 2 5 18 4 => 2 + 5 + 18 + 4 = 29
// correction
0 0 1 0 => 0 + 0 + 1 + 0 = 1
total: 29 + 1 = 30

Result is off by 10, but for checksum validity purposes it’s good enough.

Last trick comes from doing SWAR and skipping extracting digits in the first place.

User input comes as an ASCII string “1594”, which we split into chunks of size 8 to fit into 64 bit register and pad with “0” from the right:

"1594" => "00001594"
// subtract  0x3030303030303030 ("00000000")
// to get decimal values
"00001594" - "00000000" => [0, 0, 0, 0, 1, 5, 9, 4]

At this point it is easy to check if string consists of only decimal digits just by adding 0x4646464646464646 and looking for overflows and underflows in both results - can be done for both at once

Multiplying every other digit by 2 and adding them together is done with a regular multiplication by 0x0201020102010201, and math will do the rest:

    A   B
  * 1   2
----------
   2A  2B
 A  B

Top byte of the lower half of the result will contain 2A + B for 2 digit case or the full result for all 8 digits in the actual code. Because all the digits are below 10 - there’s no overflow from earlier digits.

Whole code looks like this:

fn fold10_swar(mask1: u64, mask2: u64, raw: &[u8]) -> Option<u64> {
    let mut sum = 0;

    for c in raw.rchunks(8) {
        let mut buf = [b'0'; 8];
        copy_from_small_slice(&mut buf, c);

        let mut v = u64::from_le_bytes(buf);
        // try to overflow value up
        let a = v.wrapping_add(0x4646464646464646);
        // and down
        v = v.wrapping_sub(0x3030303030303030);
        // if either direction overflows - there are non 0..9 digits so
        // checksum can't possibly be valid, otherwise all the values are digits
        if (a | v) & 0x8080808080808080 == 0 {
            // Calculate number of digits above 5 located at positions that would double
            // Doubling them would result to values above 9 which will necessitate subtracting
            // 9. But in mod 10 arithmetic -9 and +1 is the same so simply adding
            // count of such digits is enough
            sum += u64::from((mask2.wrapping_sub(v) & 0x8080808080808080).count_ones());
            sum += v.wrapping_mul(mask1) >> 56;
        } else {
            return None;
        }
    }
    Some(sum)
}

And good news - luhn3 crate can check the correctness or calculate a digit to use as a checksum for you and it works somewhat fast - on a 5 year old processor when compiled with target-cpu=native it can verify a 16 digit credit card checksum in about 3 nanoseconds - in 12 or so CPU cycles, benchmarks included.

No comments yet!

Rust Lang

!rustlang@lemmyrs.org

Create post

Rules [Developing]

Observe our code of conduct

  • Strive to treat others with respect, patience, kindness, and empathy.
  • We observe the Rust Project Code of Conduct.
  • Submissions must be on-topic
  • Posts must reference Rust or relate to things using Rust. For content that does not, use a text post to explain its relevance.
  • Post titles should include useful context.
  • For Rust questions, use the stickied Q&A thread. [TBD]
  • Arts-and-crafts posts are permitted on weekends.
  • No meta posts; message the mods instead.

Constructive criticism only

  • Criticism is encouraged, though it must be constructive, useful and actionable.
  • If criticizing a project on GitHub, you may not link directly to the project’s issue tracker. Please create a read-only mirror and link that instead.
  • Keep things in perspective
  • A programming language is rarely worth getting worked up over.
  • No zealotry or fanaticism.
  • Be charitable in intent. Err on the side of giving others the benefit of the doubt.

No endless relitigation

  • Avoid re-treading topics that have been long-settled or utterly exhausted.
  • Avoid bikeshedding.
  • This is not an official Rust forum, and cannot fulfill feature requests. Use the official venues for that.

No low-effort content

  • Showing off your new projects is fine

No memes or image macros

  • Please find other communities to post memes

No NSFW Content

  • There are many other NSFW communities, let’s keep this related to the language

Community stats

  • 1

    Monthly active users

  • 79

    Posts

  • 135

    Comments