Computing a boot checksum (C on windows)

[andreas]

Hi,

the coding virus has owned me again, so I'm very busy with coding something new ATM, although I can't tell about it yet

Only thing where I'm struggling is the routine how to compute the boot checksum. There are nice routines, but I must UNDERSTAND the thing, hence I do not want any nifty optimizations until I grasped what I'm actually doing there.

I have tried to code something, unfortunately it does not seem to work as expected yet.

The .h file has a full DOS0 boot block (2 tracks, 1024 bytes) declared which my routine uses to calculate the boot checksum (should result 0xc0200f19).
I've also cut-n-pasted a small inline log routine into the header file so you always know what the score is.

I've avoided implicit stuff where possible and even split some up to have a well-understandable code.

This tutorial helped a bit, albeit it is currently a bit of a pain to read because you have to take some declarations from the 1st version to make the 2nd variant work too, as it's incomplete. (Arghh!)

When running my program, I got a preposterous value of checksum, 0x000003FF. (after 2's complement line)

[StingRay]

Just had a quick look, you need to clear the bootchecksum before calculating the checksum and I can't see anywhere that you do this.

[andreas]

OMG yes thanks!

I forgot the memset() line - very embarrassing!

Now I'm close, but still no cigar ...
Final checksum computes to 0xc02012fe instead of actual 0xc0200f19.

However, my block data appears to be 100% correct: I took a test disk, formatted BB, hand-edited it, reading the bytes off the .h and ended up with the correct (!) sum.

So the bug lies in the calc routine, but where?
(memset-fixed version upped)

[OddbOd]

Not sure what to suggest as your code looks correct and gives me the right checksum, I even tried it again with the bootblock below and it worked 100%... weird

unsigned char blkdata[] = 
 {0x44,0x4f,0x53,0x00,0xd8,0x0e,0x24,0x02,0x00,0x00,0x03,0x70,0x2c,
  0x79,0x00,0x00,0x00,0x04,0x23,0x7c,0x00,0x02,0x00,0x00,0x00,0x28,
  0x23,0x7c,0x00,0x00,0xdc,0x00,0x00,0x24,0x23,0x7c,0x00,0x00,0x2c,
  0x00,0x00,0x2c,0x4e,0xae,0xfe,0x38,0x33,0xfc,0x7f,0xff,0x00,0xdf,
  0xf0,0x9a,0x33,0xfc,0x7f,0xff,0x00,0xdf,0xf0,0x9c,0x4f,0xf9,0x00,
  0x07,0x80,0x00,0x4e,0xf9,0x00,0x02,0x00,0x00,0x20,0x20,0x20,0x4f,
  0x4e,0x20,0x54,0x52,0x41,0x43,0x4b,0x20,0x35,0x38,0x20,0x59,0x4f,
  0x55,0x20,0x57,0x49,0x4c,0x4c,0x20,0x46,0x49,0x4e,0x44,0x20,0x41,
  0x20,0x43,0x4f,0x50,0x59,0x20,0x4f,0x46,0x20,0x54,0x48,0x49,0x53,
  0x20,0x42,0x4f,0x4f,0x54,0x42,0x4c,0x4f,0x43,0x4b,0x21,0x21,0x21,
  0x20,0x20,0x4f,0x4e,0x20,0x54,0x52,0x41,0x43,0x4b,0x20,0x35,0x39,
  0x20,0x49,0x53,0x20,0x54,0x48,0x45,0x20,0x42,0x4f,0x4f,0x54,0x42,
  0x4c,0x4f,0x43,0x4b,0x20,0x4f,0x46,0x20,0x44,0x49,0x53,0x4b,0x20,
  0x4f,0x4e,0x45,0x21,0x21,0x20,0x20,0x20,0x20,0x48,0x41,0x56,0x45,
  0x20,0x46,0x55,0x4e,0x21,0x21,0x20,0x52,0x45,0x44,0x20,0x53,0x45,
  0x43,0x54,0x4f,0x52,0x20,0x49,0x4e,0x43,0x2e,0x20,0x49,0x4e,0x20,
  0x31,0x39,0x38,0x39,0x2e,0x2e,0x2e,0x20,0x20,0x20,0x20,0x20,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,
  0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,
  0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,
  0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,
  0x63,0x21,0x74,0x63,0x63,0x21,0x74,0x63,0x63,0x21,0x21
  };

[andreas]

Thanks for testing! - especially Oddbod!

The problem was in the string buffer for the log file, which - and only on gcc 4 - falsified the resulting checksum! Arrgh! Typically C really

More updates / fixes:

- got rid of the macros for compatibility reasons (Turbo C did not like the huge LSHs and only operated on words instead of long words [MSB always zero]), now using a somewhat awkward logical operation instead
- got rid of strcpy after Toni told me this is safe without (With C you can never be sure, mind you )
- shortened chksum.h (I wasn't sure about everything being initialized to 0 either, it could also have been that the compiler had simply left some garbage data in)
- lots of more cleanups

[Kalms]

Originally Posted by andreas

The problem was in the string buffer for the log file, which - and only on gcc 4 - falsified the resulting checksum! Arrgh! Typically C really

"A Poor Workman Blames His Tools." Show a little love and understanding for the language, please.

Originally Posted by andreas

- got rid of the macros for compatibility reasons (Turbo C did not like the huge LSHs and only operated on words instead of long words [MSB always zero]), now using a somewhat awkward logical operation instead

This is because Turbo C has int as a 16-bit datatype.

When you have code such as the following:

char x = 1;
unsigned long y = 2;

int z = (x << 3) + y;

then, it's up to the compiler whether it wants to convert x from being a char to another datatype before performing the shift operation in "x << 3".
The most common scenario is that the compiler promotes any types smaller than int to int format, and then performs an int left shift.

Once the shift has been completed (and whose answer is an int in this case), there is an expression on the form () + y. Types involved are: int + unsigned long. Here, the compiler will promote the int to an unsigned long, and then perform a unsigned long + unsigned long addition.

The final result of the computation will thus be an unsigned long. This value will subsequently be stored in z, as an integer. I'm not sure if it is well defined what's going to happen when converting from a larger to a smaller datatype when the value won't fit into the smaller type, but all compilers I've come across just ignore the top bits of the larger value.

So, to make this type of construct compile properly on a platform where int is 16-bit and long is 32-bit:

long value = x << 24;

... you do by first converting (casting) x to a long:

long value = ((long) x) << 24;

Now, first x will get promoted to long format, and then that 32bit value is getting shifted left by 24 steps. All compliant C compilers will interpret that code in the same way.


You might say that the compiler should realize that an expression like "x << 24" needs to have the first operand converted to 32-bit format before the shift. However, the C standard specifies that if you shift more steps than there are bits in the datatype itself, the results are undefined. So "x << 16" on a 16-bit int is undefined, and "x << 32" on a 32-bit long is undefined. It's up to the individual compiler developer how to handle those cases.

Given the discussion above:

* if int is 32bit, then your current implementation is good and safe
* if int is 16bit, then you need to add (unsigned long) casts to your code if you want to be compliant with all such compilers

Originally Posted by andreas

- shortened chksum.h (I wasn't sure about everything being initialized to 0 either, it could also have been that the compiler had simply left some garbage data in)

With the following construct:

char x[1024] = { 5 };

the C standard guarantees that the rest of the array will be initialized to zeroes.

[andreas]

Wow, this was almost a tutorial in one post!

Latter section:
Well, I simply wasn't sure about that. But as you see, if knowledgeable people say this is safe, I may rely on it.

This is because Turbo C has int as a 16-bit datatype.

Yep, that's exactly what I assumed too. (one word = zero, second word = data almost tells some tales). FWIW, I could have made the macros work (yes I'm sure), by simply splitting everything up in slices and then look where the bugger is, and, if required, split up "huge" LSHs into two smaller ones.

However, since additional parentheses can sometimes decide upon "working" or "non-working" with macros (even though one first thinks the additional () are superfluous), getting rid of them is always a good thought.

[Kalms]

Originally Posted by andreas

FWIW, I could have made the macros work (yes I'm sure), by simply splitting everything up in slices and then look where the bugger is, and, if required, split up "huge" LSHs into two smaller ones.

I presume these are the macros:

#define Short(p) ((p)[0]<<8 | (p)[1])
#define Long(p) (Short(p)<<16 | Short(p+2))

... and it's being used such as,

long x = Long(myUnsignedCharBuffer);

.. then we can directly see that the macros do a bunch of computations on chars. The result will thus be an integer. A 16-bit integer in the case of Turbo C.

To be more precise: Short(p) is supposed to output a short (two bytes in the proper byte-order). That is fine. Long(p), however, contains the expression:

Short(p) << 16

There the code attempts to shift an integer left by 16 places. Won't work very well. Long(p) needs to do all its computations on longs.

If you assemble the line "Long(p);" then one valid interpretation of the C code could be:

    clr.w    d0           ; Fetch p[0] and convert to int
    move.b   0(a0),d0

    clr.w    d1           ; Fetch p[1] and convert to int
    move.b   1(a0),d1

    lsl.w    #8,d0        ; p[0] << 8

    or.w     d1,d0        ; (p[0] << 8) | p[1]


    clr.w    d2           ; Fetch p[2] and convert to int
    move.b   2(a0),d2

    clr.w    d3           ; Fetch p[3] and convert to int
    move.b   3(a0),d3

    lsl.w    #8,d2        ; p[2] << 8

    or.w     d3,d2        ; (p[2] << 8) | p[3]

    moveq    #16,d4       ; Short(p) << 16
    lsl.w    d4,d0

    or.w     d2,d0        ; (Short(p) << 16) | Short(p+2)

Notice the last three lines -- looking at the assembly code it's pretty obvious why the code won't work as is.


One fixed version would be:

#define Short(p) ((p)[0]<<8 | (p)[1])
#define Long(p) (((unsigned long) Short(p))<<16 | (unsigned long) Short(p+2))

This could result in the following code:

    clr.w    d0           ; Fetch p[0] and convert to int
    move.b   0(a0),d0

    clr.w    d1           ; Fetch p[1] and convert to int
    move.b   1(a0),d1

    lsl.w    #8,d0        ; p[0] << 8

    or.w     d1,d0        ; (p[0] << 8) | p[1]


    clr.w    d2           ; Fetch p[2] and convert to int
    move.b   2(a0),d2

    clr.w    d3           ; Fetch p[3] and convert to int
    move.b   3(a0),d3

    lsl.w    #8,d2        ; p[2] << 8

    or.w     d3,d2        ; (p[2] << 8) | p[3]

    and.l    #$0000ffff,d0  ; convert subexpressions to unsigned long
    and.l    #$0000ffff,d2

    moveq    #16,d4       ; ((unsigned long) Short(p)) << 16
    lsl.l    d4,d0

    or.l     d2,d0        ; (((unsigned long) Short(p) << 16) | (unsigned long) Short(p+2)

Or, by making all the computations in 32-bit might be easier:

#define Short(p) (((unsigned long) (p)[0])<<8 | (unsigned long) (p)[1])
#define Long(p) (Short(p)<<16 | Short(p+2))

This could assemble into:

    moveq    #0,d0        ; Fetch p[0] and convert to unsigned long
    move.b   0(a0),d0

    moveq    #0,d1        ; Fetch p[1] and convert to unsigned long
    move.b   1(a0),d1

    lsl.l    #8,d0        ; ((unsigned long) p[0]) << 8

    or.l     d1,d0        ; ((unsigned long) (p[0] << 8)) | (unsigned long) p[1]

    moveq    #0,d2        ; Fetch p[2] and convert to unsigned long
    move.b   0(a0),d2

    moveq    #0,d3        ; Fetch p[3] and convert to unsigned long
    move.b   1(a0),d3

    lsl.l    #8,d2        ; ((unsigned long) p[2]) << 8

    or.l     d3,d2        ; ((unsigned long) (p[2] << 8)) | (unsigned long) p[3]

    moveq    #16,d4       ; Short(p) << 16
    lsl.l    d4,d0

    or.l     d2,d0        ; (Short(p) << 16 | Short(p+2)

The reason why you'd cast all the input variables to unsigned long immediately is, that you know you'll be shuffling around bytes inside the full space of the 32bit unsigned longs; by ensuring that all calculations are done as 32 bits you don't need to do as detailed analysis on each individual operation to see whether or not you will be losing critical bits during some intermediate step.


And finally, this brings us to your current implementation:

unsigned char blkdata[1024] = ...;
unsigned long longword =  (blkdata[i*4+0] << 24) | 
                          (blkdata[i*4+1] << 16) | 
                          (blkdata[i*4+2] << 8)  | 
                           blkdata[i*4+3];

This code is still not guaranteed to work on a compiler with 16-bit ints. It might, but there is no guarantee.

Why not? Here is a somewhat easier-to-read version of the same code:

unsigned char a = ..., b = ..., c = ..., d = ...;
unsigned long longword = (a << 24) | (b << 16) | (c << 8) | d;

Look at the subexpression (a << 24). What are the types? (char << int). Now, the C standard requires us to promote the char into at least an int before the shift is performed. So this is a perfectly valid compilation of that piece of code:

     clr.w      d0
     move.b     a,d0
     moveq      #24,d1
     lsl.w      d1,d0

That is obviously not going to fly. Why was the compiler allowed to output that code? Because int is 16 bits. If int had been 32 bits, then the char would have been promoted into a 32-bit value before the shift operation, the result would have been a 32-bit value, and all would have been well.

Solution: Convert your values to longs before you do the shifts and the arithmetic.

Here is what the fixed C code code look like:

unsigned char blkdata[1024] = ...;
unsigned long longword =  (((unsigned long) blkdata[i*4+0]) << 24) | 
                          (((unsigned long) blkdata[i*4+1]) << 16) | 
                          (((unsigned long) blkdata[i*4+2]) << 8)  | 
                           ((unsigned long) blkdata[i*4+3]);

So uh. To wrap up:

- if you do computations on smaller-than-int variables, all the computations will be performed in int format
- if you do computations where there is any variation in the size of input variables and/or intermediate expressions, you need to do size/range analysis on the data, or else the code will be unreliable when porting between different compilers
- writing code that compiles properly when the size of char/int/long varies is hard, and not always worth the effort; when writing the code, you should however be aware of what assumptions it makes so you can document this (just a note like, "assumes int and long are 32 bits" at the top will suffice)

Originally Posted by andreas

However, since additional parentheses can sometimes decide upon "working" or "non-working" with macros (even though one first thinks the additional () are superfluous), getting rid of them is always a good thought.

yes. exercising care with macros is a good idea. Generally speaking, if it can be expressed using an inline function (and the compiler does a decent job with inlining it) then an inline function is to be preferred over a macro.

[andreas]

Full ACK, and thanks again. Blimey! You could make a perfect programming teacher in a school or even university!

BTW: my assembly language knowledge is a lot more limited than my C knowledge, thus not too easy to follow for me