12
\$\begingroup\$

This is a function for checking if the checksum provided by card[] is valid. card[] contains six pairs of characters. The first five pairs make up a hexadecimal number, and the last pair contains the checksum. The checksum is valid if it is equal to XOR of the first five pairs.

It is working fine, but the code is awful. I was trying to use a nested loop, but it wasn't working. Now I'm getting pairs from card[], converting them into numbers and checking whether the checksum is valid.

bool checksum(char card[])
{
int a=0;
char character0[2];
char character1[2];
char character2[2];
char character3[2];
char character4[2];
char character5[2];
long n0,n1,n2,n3,n4,n5;
char card_number;

    for(int i=0;i<2;i++)
    {
        for(a=0;a<2;a++)
        {
        character0[a]=card[i];
        }
    }
    for(int i=2;i<4;i++)
    {
        for(a=0;a<2;a++)
        {
            character1[a]=card[i];
        }
    }
    for(int i=4;i<6;i++)
    {
        for(a=0;a<2;a++)
        {
            character2[a]=card[i];
        }
    }
    for(int i=6;i<8;i++)
    {
        for(a=0;a<2;a++)
        {
            character3[a]=card[i];
        }
    }
    for(int i=8;i<10;i++)
    {
        for(a=0;a<2;a++)
        {
            character4[a]=card[i];
        }
    }
    for(int i=10;i<12;i++)
    {
        for(a=0;a<2;a++)
        {
            character5[a]=card[i];
        }
    }
    n0 = strtol(character0, NULL, 16);
    n1 = strtol(character1, NULL, 16);
    n2 = strtol(character2, NULL, 16);
    n3 = strtol(character3, NULL, 16);
    n4 = strtol(character4, NULL, 16);
    n5 = strtol(character5, NULL, 16);


if(n0^n1^n2^n3^n4==n5)     return true;
else return false;


}

The input for the example is "1E00EDE5E5F3", so 1E^00^ED^E5^E5 should be F3.

And something is wrong with this code. I see it now, because

if(n0^n1^n2^n3^n4==n5)     return true;
else return false;

is working good, but

if((n0^n1^n2^n3^n4)==n5))     return true;
else return false;

is not working at all.

\$\endgroup\$
  • 3
    \$\begingroup\$ Obvious nitpick here, but your aim shouldn't be to make it "shorter". It should be to make it "better". I know that's what you mean, but it's always worth pointing out that the two are not necessarily equivalent. \$\endgroup\$ – Tasos Papastylianou Jan 29 at 9:11
20
\$\begingroup\$

Use a 2D array instead of 6 1D arrays (vs. character0, character1, ...)

Use a 1D array for n instead of (n0, n1, ...)

Add EOS termination to the string that gets passed to strtol

Here's a refactored version:

bool
checksum(char card[])
{
    char chars[6][3];
    long nx[6];

    for (int col = 0;  col < 6;  ++col) {
        int lo = col << 1;
        int hi = lo + 2;
        for (int i = lo;  i < hi;  ++i)
            chars[col][i - lo] = card[i];
    }

    for (int i = 0;  i < 6;  ++i) {
        char *ptr = chars[i];
        ptr[2] = 0;
        nx[i] = strtol(ptr,NULL,16);
    }

    if (nx[0] ^ nx[1] ^ nx[2] ^ nx[3] ^ nx[4] == nx[5])
        return true;
    else
        return false;
}

UPDATE:

Here's a cleaner/simpler version:

bool
checksum(char card[])
{
    char tmp[3];
    long nx[6];

    tmp[2] = 0;
    for (int col = 0;  col < 6;  ++col) {
        int lo = col << 1;

        tmp[0] = card[lo + 0];
        tmp[1] = card[lo + 1];

        nx[col] = strtol(tmp,NULL,16);
    }

    if (nx[0] ^ nx[1] ^ nx[2] ^ nx[3] ^ nx[4] == nx[5])
        return true;
    else
        return false;
}

UPDATE #2:

Here's an even simpler version:

bool
checksum(char card[])
{
    char tmp[3];
    long nx;

    tmp[2] = 0;
    nx = 0;
    for (int idx = 0;  idx < 12;  idx += 2) {
        tmp[0] = card[idx + 0];
        tmp[1] = card[idx + 1];

        nx ^= strtol(tmp,NULL,16);
    }

    if (nx == 0)
        return true;
    else
        return false;
}

UPDATE #3:

Based on some feedback ...

The first two examples above, were to eliminate "parallel scalar" variables (e.g.) v0, v1, v2, ... vN in favor of an array: v[N+1]. This allowed replicated code to be replaced with loops. OP's code had two such instances for character* and n* variables, so I converted both to arrays.

When starting out [as a programmer], when to use an array isn't always obvious [particularly for small numbers]. In the above case, N was 6. So, the code could be built up by cut-and-paste.

If, however, N had been a much larger number, say, 1000, the original code would then not scale well. And, the array solution would have become [more] obvious.

OP's code was trying to copy two bytes from the buffer into different char arrays of the form character* in the first code block [to add an EOS char to allow strtol to work]. This still had a bug because there was no space for the EOS.

OP's second block would use strtol on the intermediate character* variables to produce n* variables.

My first example [in my original post], did the conversion from separate scalar variables to arrays.

My second example [in my first update], combined both blocks/loops into one, so that character* [which I had replaced with the 2D chars array], could be eliminated with a single tmp array.

When I did my example in update #2, I assumed that OP's algorithm was correct. I didn't realize that:

if (nx[0] ^ nx[1] ^ nx[2] ^ nx[3] ^ nx[4] == nx[5])

was being interpreted [by the compiler, based on precedence] as:

if (nx[0] ^ nx[1] ^ nx[2] ^ nx[3] ^ (nx[4] == nx[5]))

I assumed it was grouped as:

if ((nx[0] ^ nx[1] ^ nx[2] ^ nx[3] ^ nx[4]) == nx[5])

Because that's what made sense for the CRC calculations [and I assumed OP had done it correctly].

My refinement [to eliminate the nx array in favor of a running CRC], was based on the following identity:

(x == y) === ((x ^ y) == 0)

So, XORing all values (including the checksum), if the message was correct/intact, would produce a final value of zero. So, by doing this, I fixed OP's second bug, based on some serendipity.

Others have pointed out that:

if (nx == 0)
    return true;
else
    return false;

Can be replaced with:

return (nx == 0);

I had debated doing that, but decided that the example was already far afield from OP's original and that it would be clearer to leave the return sequence as it was. And, the optimizer would [probably] produce the same exact code for both.

At that point, I had debated coming up with a hex function that decoded a single hex char as others have suggested, calling it twice and eliminating the copy to tmp and call to strtol, but, again, felt I was getting far enough away from the original code.

But, just for the sake of completeness, here is my final/best example, generalized to allow an arbitrary buffer size:

unsigned int
hex(unsigned int chr)
{

    // NOTE: hopefully, this function gets inlined ...

    do {
        if ((chr >= '0') && (chr <= '9')) {
            chr -= '0';
            break;
        }

        chr = tolower(chr);

        if ((chr >= 'a') && (chr <= 'f')) {
            chr -= 'a';
            chr += 10;
            break;
        }

        // should blow up here (but there was no error checking in original)
        chr = 0;
    } while (0);

    return chr;
}

bool
checksum(const char *card,size_t len)
{
    unsigned int cur;
    unsigned int crc = 0;

    for (size_t idx = 0;  idx < len;  idx += 2) {
        cur = hex(card[idx + 0]);
        cur <<= 4;

        cur |= hex(card[idx + 1]);

        crc ^= cur;
    }

    return (crc == 0);
}

Note that even this could be tweaked a bit more for speed with some careful benchmarking ...


UPDATE #4:

Eliminating the call to hex in favor of a [single] table lookup may be faster and provide some error checking:

int
checksum(const char *card,size_t len)
{
    static unsigned char hex[256] = { ['0'] = 0xFF };
    unsigned int chr;
    unsigned int cur;
    unsigned int crc = 0;

    // one time init of translation table
    if (hex['0'] == 0xFF) {
        for (chr = 0x00;  chr <= 0xFF;  ++chr)
            hex[chr] = 0xFF;

        for (chr = 0;  chr <= 9;  ++chr)
            hex[chr + '0'] = chr;

        for (chr = 0x00;  chr <= 0x05;  ++chr) {
            hex[chr + 'a'] = chr + 0x0A;
            hex[chr + 'A'] = chr + 0x0A;
        }
    }

    for (size_t idx = 0;  idx < len;  idx += 2) {
        chr = hex[card[idx + 0]];
#ifdef ABORT_ON_ERROR
        if (chr == 0xFF)
            return -1;
#endif
        cur = chr;
        cur <<= 4;

        chr = hex[card[idx + 1]];
#ifdef ABORT_ON_ERROR
        if (chr == 0xFF)
            return -1;
#endif
        cur |= chr;

        crc ^= cur;
    }

    return (crc == 0);
}
| improve this answer | |
\$\endgroup\$
  • 43
    \$\begingroup\$ In your last code snippet, you can simply return nx == 0 instead of the if statement. \$\endgroup\$ – Roland Illig Jan 27 at 6:10
  • 9
    \$\begingroup\$ If I read the operator precedence chart correctly, == has precedence over ^ so that nx[0] ^ nx[1] ^ nx[2] ^ nx[3] ^ nx[4] == nx[5] amounts to nx[0] ^ nx[1] ^ nx[2] ^ nx[3] ^ (nx[4] == nx[5]). (The OP suspected as much already.) It is recommended to bracket the more obscure and seldomly used operators. Of course that judgement is in the eye of the beholder: Too many brackets again obscure the code. \$\endgroup\$ – Peter - Reinstate Monica Jan 27 at 17:16
  • \$\begingroup\$ I really like the explanation since it teaches a lot of the mindset of a C programmer. \$\endgroup\$ – Roland Illig Jan 28 at 16:23
  • \$\begingroup\$ In your update #3, you made the typical mistake of passing an illegal value to tolower. You must not cast from char directly to unsigned int, but take the intermediate step of casting from char to unsigned char. Also you are assuming that the letters abcdef are adjacent in the execution character set, which is not guaranteed. ASCII and EBCDIC behave that way, but you can never know. Therefore the strtol from the original code was better. \$\endgroup\$ – Roland Illig Jan 28 at 16:25
  • \$\begingroup\$ Update 4 feels like a lot of speculative code for a "may be faster" with no benchmarking. If I wrote that and then stepped back to look at it, I think I'd stash it away and then test the original to see whether any speedup is required. And if it is, I'd then test this version to see if it was a real improvement ... \$\endgroup\$ – Useless Jan 28 at 18:59
8
\$\begingroup\$

The most obvious issue is that you create excessive double loops for the same type of array initialisations.

Convert similar loops into one

Instead of creating 6 separate double loops for each character array, set each array in the same double loop:

...
for(int i=0;i<2;i++) {
    for(a=0;a<2;a++) {
        character0[a]=card[i];
        character1[a]=card[i + 2];
        character2[a]=card[i + 4];
        character3[a]=card[i + 6];
        character4[a]=card[i + 8];
        character5[a]=card[i + 10];
    }
}
...

This change alone will make your code much shorter and more readable already. IT can be simplified even further - check the answer from @Craig Estey.

Minor improvements

  • Your char card_number; is never used so you can simply remove it.
  • Declaring a outside of your loops is not necessary. You can create it within a for loop as for(int a=0; a<2; a++).
  • Maybe n1 or n2 and so on could have better names but I fail to come up with any.
  • As mentioned by @PeterMortensen, indentation in your code should be more consistent. For example, in your loop your character array is indented as:

    for(a=0;a<2;a++)
    {
    character0[a]=card[i];
    }
    

    But then in another for loop as:

    for(a=0;a<2;a++)
    {
        character4[a]=card[i];
    }
    

    Also, indentation for local variables declaration and return statements is different from that of the for loops.

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

I have a recommendation. But first a critique.

The main problem with the program is that it's very badly broken. You have six loops, none of which is working correctly.

First, if you were to actually write down the steps of your first loop and what part of card is copied to character0 at each step, you should find at the end that the last thing written to character[0] is card[1] and the last thing written to character[1] is card[1]. In other words, character0 ends up containing two copies of card[1], and card[0] ends up being ignored. Likewise card[2], card[4], card[6], card[8], and card[10] all will be ignored in your final calculations.

A second serious defect is that you pass a string to strtol without putting a null terminator at the end of the string. Therefore you are telling strtol to parse the two characters you gave it plus whatever is after them in memory. "Whatever is after" might be a null character, which will give you the result you want, or it might be some other non-hexadecimal character, which also will give you the result you want, or it might be one or more hexadecimal characters, which usually will give you a wrong result. When I tried running your code in an online compiler and gave it the input 112233445566, and inserted printf("n = %x %x %x %x %x %x\n", n0, n1, n2, n3, n4, n5); near the end to see what six numbers it got, the output was

11 2211 332211 44332211 44332211 44332211

This tells me something about how that particular compiler laid out the twelve bytes of memory for character0 through character5. It also tells me you were asking for undefined behavior when you called your strtol functions. This is basic test and debugging that you should have done before posting here.

There is a third defect, that n0^n1^n2^n3^n4==n5 does not work the way you meant it to, but you already have realized that this needs to be looked into.


Now my recommendation. My main recommendation is to write smaller functions. You could do the whole thing very compactly in one function via loops, but I recommend smaller functions because small functions force you to think about what each one is doing by itself: what are the inputs, exactly, what is the output, what is the task the function has to perform. If you name your function well, it will even make the code more self-documenting.

A smaller function that seems obvious to me is:

Take two characters from card. Parse them as a hexadecimal number, turning them into an integer in the range 0 to 255, and return that integer.

It's also fairly obvious that you'll end up calling the function six times, due to the way the larger function's specification is written:

card[] contains six pairs of characters. The first five pairs make up a hexadecimal number, the last pair contains the checksum.

Now you just need to figure out how to pass each pair of characters to your function. For example, if you name the function convertCharacterPairToNumber you might pass the second pair like this:

convertCharacterPairToNumber(card[2], card[3])

Or you might decide to make your function aware of card but tell it which two characters to use:

convertCharacterPairToNumber(card, 2, 3)

Or you might realize that the second character is always right after the first one, so you just need to tell your function where the first character is:

convertCharacterPairToNumber(card, 2)

Or you might decide that a pointer into the string, pointing at the first of the two characters in the pair, is enough:

convertCharacterPairToNumber(&card[2])

Then you just need to write the function's implementation and test it before you put it into the larger function. You could solve two of the three major defects in your program this way.

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Instead of calling strtol repeatedly, you could also call it once to extract a 64-bit integer, and then do some calculations on that integer.

The basic idea is:

bool checksum(const char *card) {

    unsigned long long int num = strtoull(card, NULL, 16);

    unsigned long long int xored = 0;

    xored ^= num >> 40;
    xored ^= num >> 32;
    xored ^= num >> 24;
    xored ^= num >> 16;
    xored ^= num >> 8;
    xored ^= num;

    return (xored & 0xFF) == 0;
}

The above code works by looking at a small "window" of the number in each line. One after another, the digit pairs are shifted into that "window" and xored to form the final result. It basically looks like this:

AABBCCDDEEFF   <- the number
00AABBCCDDEE   <- the number, shifted by 8 bits to the right
        00AA   <- the number, shifted by 40 bits to the right

          **
          AABBCCDDEEFF    40 bits
        AABBCCDDEEFF      32 bits
      AABBCCDDEEFF        24 bits
    AABBCCDDEEFF          16 bits
  AABBCCDDEEFF             8 bits
AABBCCDDEEFF               0 bits
          **

The small part between the asterisks is the interesting part of the "window", which will form the final result. Outside this window, the bits also take part in the computation, but they will be ignored. The nice thing about xor is that the outside bits cannot influence the inside bits. This is different from the usual integer addition or subtraction.

After xoring all the shifted numbers, the interesting part of the window is extracted using & 0xFF. In the first attempt I used an unsigned char xored, but then I realized that it might be larger than 8 bits. It seemed clever at first but really wasn't. I could have used uint8_t, which would have worked as well. Which one is better depends on the generated machine code. When you have learned assembler, you can look at the generated code and compare them.

What's left now is some error checking. Your code silently assumes that it will only be passed valid data, that is a 12-digit hex number. It's not that difficult to add the missing error handling:

#include <ctype.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

bool checksum(const char *card) {
    if (strlen(card) != 12) {
        return false;
    }

    // Make sure that the whole card number looks like a hex number.
    char *end;
    unsigned long long int num = strtoull(card, &end, 16);
    if (end != card + 12) {
        return false;
    }

    // Make sure the first character is not a space or hyphen or plus,
    // which would be accepted by strtoull.
    if (!isxdigit((unsigned char)card[0])) {
        return false;
    }

    // Make sure the second character is not an x, since 0x would be
    // interpreted as "hex" by strtoull.
    if (!isxdigit((unsigned char)card[1])) {
        return false;
    }

    unsigned long long int xored = 0;

    xored ^= num >> 40;
    xored ^= num >> 32;
    xored ^= num >> 24;
    xored ^= num >> 16;
    xored ^= num >> 8;
    xored ^= num;

    return (xored & 0xFF) == 0;
}

To be sure that the above code is correct, you must think of a whole bunch of test cases. One test case is definitely not enough since a simple return true would have made that test succeed.

A few test cases I came up with are:

#include <assert.h>

int main(void) {
    assert(checksum("") == false);
    assert(checksum("00000000000") == false); // 11 digits are too short
    assert(checksum("000000000000") == true);
    assert(checksum("0000000000000") == false); // 13 digits are too long
    assert(checksum("000000000001") == false);
    assert(checksum("000000000101") == true);
    assert(checksum("000000010001") == true);
    assert(checksum("000001000001") == true);
    assert(checksum("000100000001") == true);
    assert(checksum("010000000001") == true);
    assert(checksum("FF01020408F0") == true);
    assert(checksum("123456563412") == true);
    assert(checksum("123456654321") == false);
    assert(checksum("abcdefABCDEF") == true);
    assert(checksum("abcdefABCDEF") == true);
    assert(checksum("abcdegABCDEF") == false); // invalid character in the middle
    assert(checksum("-00000000000") == false); // invalid character at the beginning
    assert(checksum("           0") == false); // invalid character at the beginning
    assert(checksum("+00000000000") == false); // invalid character at the beginning
    assert(checksum("0x0000000000") == false); // don't let strtoull trick us with hex

    assert(checksum("1E00EDE5E5F3") == true);
}

I intentionally used the == true and == false here to keep the beginnings of the lines the same, to make them clearly stick out as a block of code. If I had used the often recommended form of omitting the == true and replacing x == false with !x, the visual code layout would have been much more chaotic.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

It would be interesting to eliminate the loops; I suspect the optimizer will deal with the hard coded indexes and optimize the code.

character0[0]=card[0];
character1[0]=card[2];
character2[0]=card[4];
character3[0]=card[6];
character4[0]=card[8];
character5[0]=card[10];
character0[0]=card[1];
character1[0]=card[3];
character2[0]=card[5];
character3[0]=card[7];
character4[0]=card[9];
character5[0]=card[11];
character0[1]=card[0];
character1[1]=card[2];
character2[1]=card[4];
character3[1]=card[6];
character4[1]=card[8];
character5[1]=card[10];
character0[1]=card[1];
character1[1]=card[3];
character2[1]=card[5];
character3[1]=card[7];
character4[1]=card[9];
character5[1]=card[11];
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The compiler will likely leave it. Even though it's ugly, this type of code is performant. \$\endgroup\$ – S.S. Anne Jan 27 at 15:53
  • 2
    \$\begingroup\$ This does exactly what the largest part of the original program does (up to the first strtol). Now observe that you can delete lines 1-6 and lines 13-18 without changing the results. \$\endgroup\$ – David K Jan 28 at 3:09
  • 1
    \$\begingroup\$ What's up with all the re-assignment nonsense? (e.g., character0[0]=card[0]; on line 1, and then character0[0]=card[1]; on line 7?) \$\endgroup\$ – Will Jan 28 at 11:41
  • 2
    \$\begingroup\$ Since a decent compiler is perfectly capable of unrolling constant loops itself, I'm not sure what this answer is trying to achieve. Anyway, manual unrolling is pretty much never used to make the code better, but to make it worse-and-faster where that tradeoff is justified. \$\endgroup\$ – Useless Jan 29 at 10:00
  • 1
    \$\begingroup\$ @Useless by unrolling the code manually it's easier to see that half of the assignments are useless and can be removed. After that, the loops can be added again. \$\endgroup\$ – Roland Illig Feb 5 at 20:51
3
\$\begingroup\$

You have several answers showing alternative solutions, or describing what's wrong with your existing code. I'm going to try to show how I'd get from here (your current code) to something I'd actually be happy using.

1. The Declaration

bool checksum(char card[])

is already kind of a problem. There's no way to communicate to the caller that conversion failed. This might be OK if it's only used inside a module that already guarantees our pre-requisites, but we should at least say very clearly what they are.

The function name actually isn't great either, because a checksum is a noun, which means this function sounds like it should calculate and return one of those.

I'm using Doxygen markdown just to get in the mood of writing real code.

/**
 * Validate a checksummed card number.
 * The format is 12 hex digits, with the last two representing
 * a single-octet checksum of the first 10 chars/5 octets.
 *
 * @param card must contain 12 hex digits.
 *
 * @note This function will not check for short (or NULL)
 * arguments and will not gracefully handle invalid digits.
 *
 * @return true if the input is valid
 */
bool validate_checksum(const char *card)

2. The Repetition

You have five identical loops populating five variables with numbers in their names - this should always always be factored out somehow. Variables with numbers in their names (ordinal numbers, rather than say point3d) are a particular red flag - they should either be an array, or a loop.

Even when we know we should move the repeated code into a function, it isn't always obvious how best to structure it. One approach is to work backwards from the desired result, and see how to get there.

2.a The End Result

We want something equivalent to the expression

return (b0 ^ b1 ^ b2 ^ b3 ^ b4 ^ b5) == 0;

(note that if b0 ^ ... ^ b4 == b5 then b0 ^ ... ^ b4 ^ b5 must be zero, and grouping all the input values together makes it easy to naturally avoid the operator precedence problem in your original code)

... but ideally without those numbered variables I called out earlier. We don't really need to keep all six values around at one time either, so we could write

unsigned long result = 0;
/* 5 is NUM_OCTETS_IN_CARD or similar */
for (int octnum = 0; octnum < 6; ++octnum)
{
    result ^= hex_octet(card);
    card += 2;
    /* 2 is CHARS_PER_OCTET */
}
return result == 0;

I made a note of things that should probably be clearly-defined constants instead of magic numbers, but I'm not writing the whole program here.

2.b The Repetition pt.2

Now we know what we want the interface to our factored-out code to look like, it's easier to write:

/**
 * Convert two hexadecimal characters to an integer.
 * The parameter must point to a string with at least two valid
 * hex characters.
 */
unsigned long hex_octet(const char *o)
{
    char tmp[3] = { o[0], o[1], 0 };
    return strtoul(tmp, NULL, 16);
}

Note that the only reason for using unsigned long above was to avoid extra work converting from strtoul - otherwise we could have just used uint8_t for the octet values.

Writing our own hex conversion is certainly feasible, but not immediately necessary. If lots of (well, six) calls to strtoul look expensive during profiling, it might be less work to replace them with a single call to strtoull returning all six octets in a single unsigned long long, and then work on the low six bytes of that (the minimum allowed size for unsigned long is 32 bits or 4 bytes, which isn't enough).

After all that, we should have something that works up to the constraints we imposed on the input.

3. Interface Improvements

We could actually check our pre-requisites, either just with

assert(isxdigit(c)==0)

for every character, or perhaps with

char *end;
unsigned long long whole = strtoull(card, &end, 16);
assert(end == card+12);

if card is guaranteed to be null-terminated.

Either way, if we don't want to just abort (in debug builds, and continue blithely on in release builds), we need a different interface to tell the caller about errors. With all those constants I mentioned earlier, and proper error-checking, we might end up with

/**
 * Validate a checksummed card number.
 * The format is 12 hex digits, representing 6 octets.
 * The last octet is a checksum for the first five.
 *
 * @param card must contain 12 hex digits. If it is not null-terminated, only the
 * first 12 digits are used.
 *
 * @return 0 (zero) if the checksum is correct, or
 *         a positive integer if the checksum is incorrect
 *         a negative integer if the input format is invalid
 */
int validate_checksum(const char *card)
{
    static const int BITS_PER_OCTET = 8;
    static const unsigned long long LOW_OCTET_MASK = 0xFF;
    static const int CHARS_PER_OCTET = 2;
    static const int EXPECTED_OCTETS = 6;
    static const int EXPECTED_CHARS = EXPECTED_OCTETS * CHARS_PER_OCTET;

    char tmp[EXPECTED_CHARS + 1];
    memcpy(tmp, card, EXPECTED_CHARS);
    tmp[EXPECTED_CHARS] = 0;

    char *end;
    unsigned long long value = strtoull(tmp, &end, 16);
    if (end != tmp + EXPECTED_CHARS)
    {
        /* error: got (end-tmp) hex digits instead of EXPECTED_CHARS */
        return -1;   
    }

    uint8_t octet = 0;
    for (int i = 0; i < EXPECTED_OCTETS; ++i)
    {
        octet ^= (uint8_t)(value & LOW_OCTET_MASK);
        value >>= BITS_PER_OCTET;
    }

    return octet; /* zero is correct, non-zero must be +ve */
}

Things like BITS_PER_OCTET are probably overkill when "octet" literally means "eight bits", but I decided to eliminate magic numbers from the code almost entirely. Conversely, the integer constant 0xFF could have been written (1 << BITS_PER_OCTET) - 1, but I'm used to reading this sort of value in hex - YMMV.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Fixed the off-by-one. The low octet mask is already addressed in the text, and the CHARS_PER_OCTET change really suggests another constant, BITS_PER_CHAR = 4 or something. I generally prefer masking explicitly, it's easier to reason about in general. \$\endgroup\$ – Useless Feb 5 at 22:46
3
\$\begingroup\$

The majority of your function consists of parsing a string of 12 characters into six numbers, expecting that each number is represented as a two-digit hexadecimal value in the input string. This is unfortunate, since it obfuscates the core of this function - the algorithm by which the checksum is computed!

Luckily, this kind of parsing is so common that there's a ready-made function in the standard library for this task, called sscanf. Reusing sscanf instead of doing your own parsing also does away with any bugs you may have introduced, so your perfectly reasonable expectation of

if((n0^n1^n2^n3^n4)==n5))   return true; 
else return false;

working should be met.

Lastly, you might like to consider a stylistic adjustment and eliminate the unneeded if statement, given that for some expression e, the code

if (e) return true;
else return false;

is equivalent to

return e;

Thus, you could shorten your function to

bool checksum(char card[])
{
    unsigned n0, n1, n2, n3, n4, n5;
    int num_fields_converted;

    num_fields_converted = sscanf(card, "%02X%02X%02X%02X%02X%02X", &n0, &n1, &n2, &n3, &n4, &n5);

    assert(num_fields_converted == 6 || !"Input string malformed");

    return (n0 ^ n1 ^ n2 ^ n3 ^ n4) == n5;
}

This nicely emphasises the actual way by which the checksum function computes its output value: it XOR's the first five bytes and then verifies that this equals the sixth byte.

Note that this assumes (by checking the sscanf return value) that the input string is well-formed before bothering to verify the checksum. Instead of using an assert, some other behaviour might be more convenient in your use case (e.g. returning false).

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Of course, when using scanf() family of functions, we always check the return value. Don't we? \$\endgroup\$ – Toby Speight Jan 29 at 18:18
  • \$\begingroup\$ @TobySpeight It depends: in case sscanf fails, how should checksum behave? After all, it cannot even compute the checksum, so how could it test if the checksum matches. You could set e.g. a global error code, but it's not far-fetched to just document the function as being undefined for malformed inputs. Partial functions are tricky though, a good fix might be to have some assertions or maybe a dedicated type (instead of char*) which expresses the preconditions explicitly (and moves the input validation to the caller). \$\endgroup\$ – Frerich Raabe Jan 30 at 8:34
  • 1
    \$\begingroup\$ That's a good question, and when I'm writing code that's a time to go back to the customer and ask what they want to happen. Most likely, we should return false if we can't read or can't parse the string; other possibilities include changing the functions return type to be able to express more than boolean (e.g. use an int or enum). \$\endgroup\$ – Toby Speight Jan 30 at 16:23
  • \$\begingroup\$ I think what Toby wanted to say politely is: We expect every answer on Code Review to either use and check the return value of scanf, or alternatively give a very good reason why the return value does not need to be checked. Silently ignoring the return value is questionable. \$\endgroup\$ – Roland Illig Feb 5 at 20:55
  • \$\begingroup\$ @RolandIllig That makes perfect sense; I now added assertions to express the preconditions of the function (not satisfying them renders the behaviour undefined). \$\endgroup\$ – Frerich Raabe Feb 6 at 9:52
1
\$\begingroup\$

As x ^ x == 0 on can do a homogeneous:

return nx[0] ^ nx[1] ^ nx[2] ^ nx[3] ^ nx[4] ^ nx[5] == 0;

A char, a hex digit represent a nibble, 4 bits. As XORing does not influence other positions (like ADDing), one can do the checksum separately on the two nibbles:

int
hex(char ch)
{
    // For ASCII
    return ch <= '9' ? (int) ch - '0' : (ch & 0xF) + 9;
}

The hex function should give a number 0 <= x < 16 for characters 0-9A-Fa-f, for ASCII based character encodings.

After feedback to the non-validating hex function:

int
hex(char ch)
{
    char* digits = "0123456789ABCDEFabcdef";
    char* p = strchr(digits, ch);
    if (!p) {
        return -1;
    }
    int digit = p - digits;
    return digit < 16 ? digit : digit - 6;
}

One might do more than returning -1. Or check it at the call site.

bool
checksum_valid(char* card)
{
    if (strlen(card) != 6*2) {
        return false;
    }
    int crc0 = 0;
    int crc1 = 0;
    while (*card) {
        crc0 ^= hex(*card++);
        crc1 ^= hex(*card++);
    }
    return crc0 == 0 && crc1 == 0;
}

Using 0 ^ x == x and x ^ x == 0.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ While your answer isn't code only, it doesn't really review the original posters code. Good answers on code review review the code and don't necessarily provide an alternate solution at all. \$\endgroup\$ – pacmaninbw Jan 27 at 13:16
  • \$\begingroup\$ @pacmaninbw thanks, that explains to me not receiving points ;). After the review of the return statement of the OP, "making the answer shorter" went to an entire removal of the extra array and so on. I leave the answer for who it wants to use, \$\endgroup\$ – Joop Eggen Jan 27 at 13:22
  • \$\begingroup\$ Letters are not guaranteed by the standard to be contiguous. You'll probably have to use a lookup table for it. \$\endgroup\$ – S.S. Anne Jan 27 at 15:52
  • \$\begingroup\$ @S.S.Anne yes EBCDIC is such a case. I assumed ASCII however. A strchr or such is nicer though. And allows to validate that the characters are valid hex digits. \$\endgroup\$ – Joop Eggen Jan 27 at 15:59
  • 1
    \$\begingroup\$ strchr(digits, tolower(ch)) would be better, especially as the sample input from the OP uses upper case. \$\endgroup\$ – Ken Y-N Jan 28 at 0:16

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.