4
\$\begingroup\$

I was able to find all kinds of examples that demonstrate how to validate a Luhn Checksum but very few that actually generated the check digit. Here is my attempt in base 10, based on the validation examples found at Wikipedia and Rosetta Code:

/// <summary>
/// Constructs the check digit for a given numeric string using the Luhn algorithm; also known as the "mod 10" algorithm.
/// </summary>
/// <param name="value">The string that a check digit will be calculated from.</param>
public static int Mod10(string value) {
    const int validCodePointCount = 10;
    const int validCodePointOffset = 48;

    var index = value.Length;
    var parity = true;
    var sum = 0;

    while (0 < index--) {
        var digit = (value[index] - validCodePointOffset);

        if (parity) {
            if ((validCodePointCount - 1) < (digit <<= 1)) {
                digit -= (validCodePointCount - 1);
            }
        }

        parity = !parity;
        sum += digit;
    }

    return ((validCodePointCount - (sum %= validCodePointCount)) % validCodePointCount);
}
\$\endgroup\$
  • \$\begingroup\$ The site you linked has c# code for the check digit (Luhn.GetCheckValue) : rosettacode.org/wiki/Luhn_test_of_credit_card_numbers#C.23 \$\endgroup\$ – Xiaoy312 Oct 5 '18 at 21:21
  • 1
    \$\begingroup\$ I was actually mislead by that particular example (and many like it) earlier today; the problem with it is that it validates a value that already has the "check digit" appended to it while I'm trying to generate the digit itself. \$\endgroup\$ – Kittoes0124 Oct 5 '18 at 22:37
5
\$\begingroup\$

All in all it seems OK to me. A couple of things though:

1)

  const int validCodePointCount = 10;
  const int validCodePointOffset = 48;

The names of these constants are hard to distinguish from each other and to understand in the context and they blur the behavior of the algorithm.

Better names could be:

const int numberBase = 10;
const int zero = '0';

Here I use '0' instead of 48 because the first is much more recognizable to programmers than the latter, and we instantly grasp the meaning. In fact in such a relatively small algorithm, I would prefer to use the literals directly in the code than the named constants like:

var digit = (value[index] - '0');

This is such a common operation and we all know what it's about immediately when seeing it.

In general it is wise to avoid magic numbers, but in some situations it is preferable in order to improve readability - IMO.


2)

You don't have to iterate backwards because you can determine the initial parity from the length of the input string:

var parity = value.Length % 2 != 0;

You can then iterate forward:

foreach (int n in value.Select(c => c - '0'))
{
  ...
  parity = !parity;
}
\$\endgroup\$
3
\$\begingroup\$
const int validCodePointCount = 10;
const int validCodePointOffset = 48;

Constants should be written in PascalCase, whether it is private or local.

while (0 < index--) {
var digit = (value[index] - validCodePointOffset);

What is this? A reverse foreach which could be written as foreach(var c in value.Reverse()). Also, the community standard for bracket placement is generally vertically aligned. (Although, this is more a question of style that you or your team follow.)

var digit = (value[index] - validCodePointOffset); // validCodePointOffset -> 48

A int.Parse could be used instead. While we are at it, there is no argument guard that ensures value will always be a string of digits.
edit: If you look to support an arbitrary set of characters, you can use a lookup table to map the character to its "numerical" value.

if ((validCodePointCount - 1) < (digit <<= 1)) {
    digit -= (validCodePointCount - 1);
}

It it really hard to understand what this code is trying to do. The wiki says: "If the result of this doubling operation is greater than 9, then add the digits of the product." This could be added as a comment to explain this bit of code. I wouldn't recommend using bit-shifting for simple multiplication. It adds an unnecessary layer in this case, when *= 2 could be used. Or, use code that is easier to read:

digit *= 2;
if (digit >= @base)
    digit = digit % @base + 1;
return ((validCodePointCount - (sum %= validCodePointCount)) % validCodePointCount);

10 - (x mod 10) can never exceed 10, so the last modulo operation is completely unnecessary. I would suggest replacing the validCodePointCount constant with its value. Unless there is a better variable name, which I have a lack of word for.
Again quoting the wiki: "The check digit (x) is obtained by computing the sum of the other digits (third row) then subtracting the units digit from 10."


private static readonly Dictionary<char, int> CharacterMap = 
    "0123456789"
        .Select((x,i) => (x,i))
        .ToDictionary(x => x.x, x => x.i);

public static int GetLuhnCheckSum(string value)
{
    if (!value.All(CharacterMap.ContainsKey))
        throw new ArgumentException("Value contains invalid characters", nameof(value));

    int @base = CharacterMap.Count;
    var parity = true;
    var sum = 0;

    // process the number from right to left
    foreach (var c in value.Reverse())
    {
        var digit = CharacterMap[c];

        // From the rightmost digit, which is the check digit, and moving left, double the value of every second digit.
        if (parity)
        {
            digit *= 2;

            // If the result of this doubling operation is greater than 9, then add the digits of the product.
            if (digit >= @base)
                digit = digit % @base + 1;
        }

        parity = !parity;
        sum += digit;
    }

    // The check digit (x) is obtained by computing the sum of the other digits then subtracting the units digit from 10
    return (@base - (sum % @base)) % @base;
}

edit: fixed check sum can be base instead of 0
edit: updated the code to support different base system

\$\endgroup\$
  • 1
    \$\begingroup\$ The last mod operation is necessary because (10 - (sum % 10)) can result in 10 which is not a single digit; the solution is to check if (sum % 10) is equal to 0 before performing the subtraction or to just mod by 10 again. Also, failing to subtract 48 from the character means that you're no longer working within the proper base. Might wanna test your code against working examples in order to correct. \$\endgroup\$ – Kittoes0124 Oct 5 '18 at 21:49
  • 1
    \$\begingroup\$ Reintroducing the "magic" value of 10 instead of the abstracted constant not only makes the code harder to truly understand but also forces one to refactor portions of the code that don't change under any base. The Luhn algorithm is used for a lot more than just credit cards and can be generalized to any n (which I plan to do in the future). \$\endgroup\$ – Kittoes0124 Oct 5 '18 at 21:54
  • 1
    \$\begingroup\$ "can never exceed 10", but 10 is not an acceptable value... Indeed it is necessary. \$\endgroup\$ – Xiaoy312 Oct 5 '18 at 22:08
  • \$\begingroup\$ "Constructs the check digit for a given numeric string", you are implying that we are dealing with characters ranging from 0 to 9. However, I agree with you that extracting the base into a constant make it easier to support other base system. \$\endgroup\$ – Xiaoy312 Oct 5 '18 at 22:15
  • 1
    \$\begingroup\$ @Kittoes0124 I've updated my answer to address the checksum and nth-base problem. \$\endgroup\$ – Xiaoy312 Oct 5 '18 at 22:40
1
\$\begingroup\$

Review

Most tips and issues have already been addressed by fellow reviewers. I would like to add or re-iterate:

  • when implementing an algorithm, you should always include unit tests
  • when providing a public API, you should handle argument checks; in this case, check value against null and check each of its code points against the specified entropy - in this case ['0'-'9']
  • when checking a string for a missing character, return a char rather than an int. Return '0' instead of 0, and so on.
  • use clear and compact variable names to enhance readability
  • develop for human beings rather than a computer to read your code: avoid statements that could introduce ambiguity for a human reader; while (0 < index--) makes people think about the order of operations (first comparison, or first decrementation)
  • develop for extensibility; this algorithm only works for base 10, and it can't be reused for entropies where characters are not only digits and aren't necesseraly consecutive code points, as allowed by Luhn mod N generic case

Luhn mod N

Following the instructions at wikipedia, we can implement Luhn mod N as follows:

A converter is required, so we are not restricted to base 10 or digits only.

interface ICodePointConverter
{
    int CodePointFromCharacter(char character);
    char CharacterFromCodePoint(int codePoint);
    int NumberOfValidInputCharacters();
}

A default implementation could use lookup maps for both directions (int -> char and char -> int).

class MemoryCodePointConverter : ICodePointConverter
{
    IDictionary<int, char> characterByCodePointMap;
    IDictionary<char, int> codePointByCharacterMap;

    public int NumberOfValidInputCharacters() => characterByCodePointMap.Count;

    public static MemoryCodePointConverter FromEntropy(string entropy)
    {
        entropy = entropy ?? throw new ArgumentNullException(nameof(entropy));
        return new MemoryCodePointConverter(
            Enumerable.Range(0, entropy.Length).Select(i => (i, entropy[i])));
    }

    public MemoryCodePointConverter(
        IEnumerable<(int codePoint, char character)> entries)
    {
        entries = entries ?? throw new ArgumentNullException(nameof(entries));
        characterByCodePointMap = new Dictionary<int, char>();
        codePointByCharacterMap = new Dictionary<char, int>();

        foreach (var entry in entries)
        {
            characterByCodePointMap.Add(entry.codePoint, entry.character);
            codePointByCharacterMap.Add(entry.character, entry.codePoint);
        }
    }

    public char CharacterFromCodePoint(int codePoint)
    {
        if (!characterByCodePointMap
            .TryGetValue(codePoint, out var character))
        {
            throw new ArgumentException(
                $"Invalid code point {codePoint}", nameof(codePoint));
        }

        return character;
    }

    public int CodePointFromCharacter(char character)
    {
        if (!codePointByCharacterMap
            .TryGetValue(character, out var codePoint))
        {
            throw new ArgumentException(
                $"Invalid character {character}", nameof(character));
        }

        return codePoint;
    }
}

The algorithm can then be implemented given the pseudo code at wikipedia:

static class LuhnCheck
{
    public static char GenerateCheckCharacter(string input, ICodePointConverter converter)
    {
        converter = converter ?? throw new ArgumentNullException(nameof(converter));
        input = input ?? throw new ArgumentNullException(nameof(input));

        int factor = 2;
        int sum = 0;
        int n = converter.NumberOfValidInputCharacters();

        // Starting from the right and working leftwards is easier since 
        // the initial "factor" will always be "2" 
        for (int i = input.Length - 1; i >= 0; i--)
        {
            int codePoint = converter.CodePointFromCharacter(input[i]);
            int addend = factor * codePoint;

            // Alternate the "factor" that each "codePoint" is multiplied by
            factor = (factor == 2) ? 1 : 2;

            // Sum the digits of the "addend" as expressed in base "n"
            addend = (addend / n) + (addend % n);
            sum += addend;
        }

        // Calculate the number that must be added to the "sum" 
        // to make it divisible by "n"
        int remainder = sum % n;
        int checkCodePoint = (n - remainder) % n;

        return converter.CharacterFromCodePoint(checkCodePoint);
    }
}

Unit tests show us the results are the same for the luhn test mod 10 from OP.

[TestMethod]
public void Fixture()
{
    var input = "7992739871";
    var converter = MemoryCodePointConverter.FromEntropy("0123456789");

    // + '0' is required to get the character from the resulting code point
    var m1 = LuhnCheckOP.Mod10(input) + '0';
    var m2 = LuhnCheck.GenerateCheckCharacter(input, converter);

    Assert.AreEqual(m1, m2);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.