checksum calculation
[1/6] from: rebol-list2::seznam::cz at: 10-Sep-2003 0:46
Hello rebol-list,
I still have problems with calculation of CRCs
for example how to implement this C code in Rebol:
ULONG
CalcTableChecksum(ULONG *Table, ULONG Length)
{
ULONG Sum = 0L;
ULONG *Endptr = Table+((Length+3) & ~3) / sizeof(ULONG);
while (Table < EndPtr)
Sum += *Table++;
return Sum;
}
where ULONG is 32-bit unsigned integer and Table is just some binary
data which needs to be signed.
Can anybody help me?
thanks Oldes
[2/6] from: antonr:iinet:au at: 11-Sep-2003 17:48
Hi Oldes,
Well, what have you got so far?
I suppose your algorithm in rebol doesn't match the
one in C?
(Just refreshing my memory, ~3 in C just means
get the bitwise inverse of 3, that means all
bits on except bit 0 and bit 1.)
I presume the ((Length+3) & ~3) is so that the length
(in bytes) is truncated at a four byte boundary, which
makes sure that you have the last ULONG.
How does your table data look in rebol?
What is the byte-order for each ULONG ?
calc-table-checksum: func [table [binary!] /local sum length pos][
sum: 0 ; (signed long integer)
length: (and~ 3 (3 + length? table)) / 4 ; ULONG = 4 bytes
; step through the table data in chunks of four bytes
repeat n length [
pos: n * 4
; (I don't know if this byte order is correct)
val: to-integer rejoin [# (table/:pos) (pick table pos + 1)
(pick table pos + 2) (pick table pos + 3)]
; catch math overflow
sum: either error? try [sum + val][
; which way did it overflow? (positive/negative)
either positive? sum [
print "positive"
; overflowed in positive direction
; to-integer required because -2147483648 is by default a decimal
(sum + to-integer -2147483648) + (val + to-integer -2147483648)
][
print "negative"
; overflowed in negative direction
(2147483647 + sum) + (2147483647 + val) + 2
]
][sum + val] ; no error, just add it up
probe type? sum
sum ]
; a negative final sum (signed long) is converted to decimal by the
addition
either positive? sum [sum][sum + (2 * 2147483648)]
]
The above is not fully tested.
I quickly tested the overflow code, and it seems to be ok.
Getting the table data out in the right order remains to be tested.
Anton.
[3/6] from: rotenca:telvia:it at: 11-Sep-2003 14:39
Hi,
> ; catch math overflow
> sum: either error? try [sum + val][
<<quoted lines omitted: 12>>
> probe type? sum
> sum ]
You can use:
first sum + to pair! val
---
Ciao
Romano
[4/6] from: antonr:iinet:au at: 12-Sep-2003 1:22
Interesting!
Pairs do not give you a math overflow error
and wrap around automatically when you add
or subtract beyond the limits.
Anton.
[5/6] from: rebol-list2:seznam:cz at: 11-Sep-2003 14:31
Hello Anton,
Thursday, September 11, 2003, 9:48:38 AM, you wrote:
AR> Hi Oldes,
AR> Well, what have you got so far?
AR> I suppose your algorithm in rebol doesn't match the
AR> one in C?
Thanx Anton... your script helped me very much...
Yes... almost none of checksums I've found in binary formats I was
working with doesn't match the rebol's one:( Another problem with
rebol's checksum is that it's not possible to use it on large files or
data streams, because it first loads all the content into memory.
I was trying to use it (for example) for counting md5 checksums of redhat
distribution cds and I have to say it's useless:(
You script was not working but I found the right way how to detect the
length and improved your script to this one (with a hope that negative
overflow should never happen) and it's working:))
ULONG: [;(byte-order is Big Endian)
copy v 4 skip (
v: to binary! v
v: either #{80000000} = and v #{80000000} [
2147483648 + to integer! (and v #{7FFFFFFF})
][to integer! v]
)
] ;returns decimal if the u.integer is >= 2147483648
calc-table-checksum: func [table [binary!] /local sum length n][
sum: 0 ; (unsigned long integer)
length: length? table
if 0 < n: length // 4 [
length: length + 4 - n
insert/dup tail table #{00} (4 - n)
;print "padding"
]
; step through the table data in chunks of four bytes
parse/all table [
any [
ULONG (
either error? try [sum: sum + v][
;print "positive overflow"
sum: sum - 4294967296 + v
][
if sum >= 4294967295 [sum: sum - 4294967296]
]
)
]
]
either positive? sum [sum][sum + 4294967296]
]
--
Best regards,
rebOldes -----------------[ http://oldes.multimedia.cz/ ]
[6/6] from: antonr:iinet:au at: 12-Sep-2003 17:11
Hi Oldes,
Good that it helped and it works!
It seems a pity to me that you abandon integer! so
quickly for decimal!
I think my code keeps integer! type for longer.
(I am worried about decimal format: it might give
a fractional result one day? Perhaps it is an unfounded worry.)
Don't forget Romano's point about pair!s.
I am sure using a pair we can reduce the necessary
code a lot!
This will be good for the library or the cookbook
when it's finished.
Do you know what style of checksum this is called?
Anton.
Notes
- Quoted lines have been omitted from some messages.
View the message alone to see the lines that have been omitted