1's Complement Checksum problem..... please HELP!!

[prosper50]

Hello everyone. I'm in some serious need of help here.

Several months back I posted a request for assistance in coming up with a 1's-complement checksum generator, given a string of hex data that my application generates. The request was successful and I was able to implement the code with fantastic results. That is, until last week.

There are two parties that need to verify the data that the 2-digit checksum covers. My office, and a remote office. The remote office uses a different software application programmed in C. Thus far there haven't been any issues. Recently however, the other office noted that some of the checksum values were NOT validated by their software.

On our end, the checksum is implemented by the software performing a simple comparison and if the checksum is "valid", a field turns green and the software progresses. If not, an error is flagged. The errors are usually as a result of the user entering erroneous data on our end. We never really look at the checksum value, itself.... we go by the system we have in place with color alerts. Going back and looking at the actual data, I now see that there are a lot of values of "00" as the checksum which our software is flagging as "valid". When the same data set is run through the competing software in the other office, their checksum is coming up as "5F" or "4E", etc. Values that you would expect to see. When I see "00", I think PROBLEM.

So here is the code in question:

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        strInput = String.Empty
        checksumhexstring = String.Empty
        intSum = 0
        Label1.Text = String.Empty
        Label3.Text = String.Empty
        checksumhexstring = TextBox1.Text
        strInput = checksumhexstring

        'Step 1: Sum all
        'The loop is to 158 because we only consider 80 bytes. Is this always it?
        For i As Integer = 0 To 158 Step 2
            intSum += CInt("&H" & strInput.Substring(i, 2))
        Next

        'Step 2: Rollover
        intSum = intSum \ 256 + (intSum - 256 * (intSum \ 256))

        'Step 3: Find 1's compliment
        intSum = intSum Xor &HFF

        'The following lines check to see the quantity of checksum characters.
        'If there is one character, front-pad with a zero to make two characters.
        'If there are two characters, pass the hex conversion directly.
        'If there are three characters, flag as an error.
        Dim checksumtest As String = String.Empty
        checksumtest = Hex(intSum).ToString.Trim

        If checksumtest.Length = 1 Then
            Label1.Text = "0" & Hex(intSum).ToString
        End If
        If checksumtest.Length = 2 Then
            Label1.Text = Hex(intSum).ToString
        End If
        If checksumtest.Length > 2 Then
            MsgBox("Checksum exceeds two characters")
            Label3.Text = Hex(intSum).ToString
        End If
    End Sub

Now, the variable "checksumhexstring" would contain the following data. I will provide a few sets:

SAMPLE SET
0101513633302D30303033312D303039322D3530585858582D58585800000000000000000000000000000000005430303030 30303030310000000000000000000001010001010E0009AC503603001803

DATA SET 1
0101513930302d30303033302d303039322d3530383133312d30303200000000000000000000000000000000005430303030 3031303036000000000000000000000103050a080e0009ac503600046003

DATA SET 2
0101513930302d30303033302d303039322d3530383133312d30303200000000000000000000000000000000005430303030 3031303035000000000000000000000103050a080e0009ac503600046f03

DATA SET 3
0101513930302d30303033302d303039322d3530383133312d30303200000000000000000000000000000000005430303030 3031303032000000000000000000000103050a080e0009ac503600046603

DATA SET 4
0101513930302d30303033322d303039322d3530383037392d30313500000000000000000000000000000000005430303030 3031303235000000000000000000000103000a100e0009ac503600103e03

DATA SET 5
0101513930302d30303033322d303039322d3530383037392d30313500000000000000000000000000000000005430303030 3031303236000000000000000000000103000a100e0009ac503600104103


When the application is running properly, I see that the checksum for the "Sample Set" is 5A. That is valid and correct.

Data set 1, however, is flagging an error, and the checksum is calculated to be 1FF. That is valid to itself, but is an invalid 2-digit checksum value.

Data set 2 comes up with a F0. That is valid and correct.

Data set 3 is calculated to be 1FD. Again, not a valid value. [As a NOTE, the "valid" checksum the remote office calculated for this set was FC]

Data set 4 is one of those 00 sets. This is not valid. It READS as valid, but in reality it is not valid.

Data set 5 is calculated to be 1FC. Not valid.

I don't know what is going on here. The field lengths have not changed which generates the hex string. Not much of the data within the string changes.... a few bytes here and there. I'm not understanding why these errors are occurring. And especially because it has been working flawlessly since the start - the remote office hasn't had one issue up until recently.

In discussing the issue with the remote office, they suggested that there may be a "folding issue". Now, I'm familiar with the binary process for calculating the 1's-complement, and I'm familiar with folding..... but I am NOT a programming expert and I am not totally clear on how this code works. I received a cursory explanation from the individual who contributed the solution. All I know is it has been working. Could this be a strange math error??

For reference, the remote office has provided JUST the segment of their C code that deals with this checksum:

/*
 * Function:    card_calc_idprom_checksum
 *
 * Description: This function is used to calculate the 1's complement checksum
 *              of a block of IDPROM data (per RFC 1071, but 8-bit).
 *
 * Parameter:   CARD_IDPROM_SECTION1_FORMAT_T
 *              Pointer to a complete SECTION1 IDPROM data block.
 *
 * Returns:     uint8_t
 *              1's complement checksum of all data bytes in the SECTION1
 *              except the checksum byte its self.
 */
static __inline uint8_t card_calc_idprom_checksum(
    CARD_IDPROM_SECTION1_FORMAT_T * idprom_data)
{
    uint8_t               * data_p;
    int                     index;
    uint32_t                checksum = 0;

    /* We are going to step through the data byte-by-byte */
    data_p = (uint8_t *)idprom_data;

    for (index = 0; index < sizeof(CARD_IDPROM_SECTION1_FORMAT_T) - 1; index++)
{
        checksum += data_p[index];
    }

    /* Fold the carries for the 8-bit checksum */
    while (checksum > 0xFF) {
        checksum = (checksum & 0xFF) + (checksum >> 8);
    }

    return((uint8_t)(~(checksum) & 0xFF));
}

The data they feed into this is identical to the hex strings that I provided above.

I am HOPING that someone who is far more familiar with this material than I am can help me out here. This is above my head and I would appreciate the collective insight of this forum.

THANK YOU VERY MUCH!!

-Dave

[passel]

You're only folding one time from the upper bytes into the checksum

        'Step 2: Rollover
        intSum = intSum \ 256 + (intSum - 256 * (intSum \ 256))

You should have a loop like they do to keep folding until there are no bits in the upper three bytes set.

        'Step 2: Rollover
        Do While intSum > &HFF
            intSum = intSum \ 256 + (intSum - 256 * (intSum \ 256))
        Loop

Of course you could implement it similar to the way they did, which should be more efficient without the divides and multiplies

        'Step 2: Rollover
        Do While intSum > &HFF
            intSum = (intSum And &HFF) + (intSum >> 8)
        Loop

Even though your buffer is small enough that you won't carry bits into the third and fourth bytes, when you fold the second byte into the first (by shifting it down and adding), the addition can carry a 1 back into the second byte (so you end up with 1xx).
You need to fold that 1 back into the lower byte by doing the shift and add again.
And it looks like it might be possible if you ended up with "1FF" after the first fold, the second fold will add FF and 1, so you'll end up with 100, and require a third fold.
So, the loop is necessary to reduce the checksum down to 1 byte.

[prosper50]

Passel, that is brilliant. With your explanation, I am now able to follow the C code to see what is going on a bit better. I see the error, and I have implemented your change (specifically, the one you provided that is similar to the C code).

HOWEVER, I am still puzzled with one of these hex strings. It is still returning a "0" from the intSum=intSum \ 256.... calculation. Therefore, with my padding, the end result is "00". This is invalid. Do you have any insight into this? The hex string is as follows:

0101513930302d30303033322d303039322d3530383037392d30313500000000000000000000000000000000005430303030 3031303235000000000000000000000103000a100e0009ac503600103e03

I have hundreds of these hex strings, and there are several that keep coming out to zero.

Also, one additional question. If you are indeed familiar with this checksum process, can you explain the intSum calculation (intsum\256+(intsum=256*(intsum\256))?? I am a bit baffled by this. As I mentioned, I can do the calculations in binary manually to come up with an answer, but the scope of operations contained in this calculation have me scratching my head. I'm not exactly sure what it is accomplishing.

THANK YOU, THANK YOU!!

[passel]

Unless there is a bias added elsewhere, I don't see that a checksum of 00 is invalid.
If you run Data Set 4 through their C function it returns 0 for the checksum as well.

As for intSum \ 256 + (intSum - 256 * (intSum \ 256)) ...
The "\" is an Integer divide (returns the Integer portion of the dividend, the "remainder" or fractional part is dropped).
If you do an Integer divide by a power of 2 it is the same as doing an arithmetic right shift of a binary number.
256 is 2^8 (2 to the 8th power), so an integer divide by 256 ( \ 256) is the same as shifting to the right 8 bits ( >> 8).

1057 \ 256 = 4 (256 will go into 1057 four times, with some remainder which is dropped, aka. truncated).
1057 >> 8 = 4
1057 = 421 hex. If you shift the 8 bits to the right, the bottom two hex digits are shifted into the "bit bucket" and the 4 is shifted down to be the lowest hex digit.

Let's take 1057 as an example, but use the hex (421) and hex for the constants (256 is 100 hex) as well in the equation and work through it.

intSum \ 256 + (intSum - 256 * (intSum \ 256))
421    \ 100 + ( 421   - 100 * (421    \ 100))
      4      + ( 421   - 100 *      4)
      4      + ( 421   -    400  )
      4      +      21
=            25

So, the equation isolates the upper 3 bytes twice (intSum \ 256) (by "shifting right")
On the left so it can be shifted down to add to the checksum byte,
On the right side ( intSum - 256 * (intSum \ 256)) is a round about way to isolate the lowest byte by subtracting the 3 upper bytes from themselves.
(shift the upper 3 bytes to the right(\256) and then shift them back to the left(256 *), so you just have the bits in the upper 3 bytes left
and now subract that from the original number (intSum), thus subtracking the upper 3 bytes values from themselves making the upper 3 bytes 0 (on the right side of the equation leaving you with the lowest byte, ready to be added to the left side of the equation).

It would have been simpler to just isolate the lowest byte directly by anding it with an eight bit mask (And 255) or (And &HFF).
intSum = intSum \ 256 + (intSum And 255)

Which, when you look back it, is what the C code is doing (except shift is first and "And" is second here, and in the reverse order in the C code).

[dbasnett]

This code is close to the C code, though it does produce a checksum of zero for one of the cases...

    Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
        Dim sets As New List(Of String)
        sets.Add("0101513633302D30303033312D303039322D3530585858582D5858580000000000000000000000000000000000543030303030303030310000000000000000000001010001010E0009AC503603001803")
        sets.Add("0101513930302d30303033302d303039322d3530383133312d303032000000000000000000000000000000000054303030303031303036000000000000000000000103050a080e0009ac503600046003")
        sets.Add("0101513930302d30303033322d303039322d3530383037392d303135000000000000000000000000000000000054303030303031303235000000000000000000000103000a100e0009ac503600103e03")
        sets.Add("0101513930302d30303033302d303039322d3530383133312d303032000000000000000000000000000000000054303030303031303032000000000000000000000103050a080e0009ac503600046603")
        Debug.WriteLine("")
        For Each s As String In sets
            Dim tchksum As Integer = 0 'temp

            'sum the bytes
            Do While s.Length > 0
                Dim foo As Integer = Convert.ToInt32(s.Substring(0, 2), 16)
                tchksum += foo
                s = s.Remove(0, 2)
            Loop

            Debug.Write("Before fold " & tchksum.ToString & "  " & tchksum.ToString("X"))

            'do the fold
            Dim chksum As Integer = tchksum
            Do While chksum > 255
                Debug.Write(".")
                chksum = (chksum And 255) + (chksum >> 8)
            Loop
            chksum = (Not chksum) And 255
            Debug.WriteLine("   After fold " & chksum.ToString & "  " & chksum.ToString("X"))

        Next
    End Sub

[prosper50]

Passel, THANK YOU for that marvelous explanation. Holy cow!! This is a topic that is so widely necessary in the computer/software field, but trying to track down any sort of clear explanation is impossible. I Google'd my heart out trying to figure out the computational math behind this issue, as well as trying to track down an error within the code. It couldn't be found. Your reference is invaluable. I have printed it out and stored it in my binder.

Also, thank you for clarification on the "00" checksum error. I never looked at a 0 as invalid, but in light of all the other errors that I was having (because of the remaining fold-ins), I wasn't about to assume that it was correct. Knowing that the C function also returns 0 is refreshing.

Once again, THANK YOU!!!!!

[prosper50]

dbasnett, likewise, thank you for your contribution of code. I just set that up in a little application and went through it. Your details and output messages within the code help to reveal a lot of the inner mathematical workings. This is a fantastic resource as well!!!!!