Help with easy checksum

[Scott Sheffield]

I have created a binary file using Interleaf LISP and I need to put a
checksum at the end of the file so that it can be loaded into the
hardware. The problem is though I have a good idea what a checksum is
and does I have no idea how to do this in LISP. Here is what I am told I
need to do:

1) create a 32 integer object, initialize it to 0. refer to LISP
manual for machine sizing.

2) Write 32 bit chunks to the file, also accumulate the 32 bit chunks
into this 32 bit integer object. The accumulation is a add, ignoring
overflows (which is standard), then the final step is to take the
negative (2's complement) all the accumulations have been done.

3) when you get to the last entry take the negative of the accumulated
32 bit chunks. This value is the checksum. Write it as the
last file entry.

I am a lone LISP guy in a sea of ADA guys so I am on my own. Can anyone
help me with this....please?

Thanks,
Scott

[Robert Monfera]

Scott Sheffield wrote:

> 1) create a 32 integer object, initialize it to 0. refer to LISP
> manual for machine sizing.
>
> 2) Write 32 bit chunks to the file, also accumulate the 32 bit chunks
> into this 32 bit integer object. The accumulation is a add, ignoring
> overflows (which is standard),

What is standard is that the sum of two numbers is the sum of two
numbers no matter how many bits you need to represent it in binary.
Many languages (excluding Common Lisp) depart from this several thousand
year rule. There is no guaranteed way in Common Lisp to
"loose" the carry, even if optimizing compilers will do so when a number
is declared to be a 32-bit value.

Maybe you could just accumulate numbers and don't worry about overflows
until the end of the file (i.e., your total may well exceed the 32-bit
range). You can complement and chop bits with BOOLE really easily.

I'd recommend studying the Hyperspec because it's straightforward to
find things like BOOLE, LOGNOT and other bit-manipulating functions.

This additive checksum is not the best way to ensure integrity: rows of
0s won't be missed. Isn't it better to use some standard method or just
count the number of records?

Robert

[Erik Naggum]

* Scott Sheffield <scott.y....@lmco.com>

| I have created a binary file using Interleaf LISP and I need to put a
| checksum at the end of the file so that it can be loaded into the
| hardware. The problem is though I have a good idea what a checksum is
| and does I have no idea how to do this in LISP. Here is what I am told I
| need to do:

when you are told what to do in language-specific terms, there's a
serious flaw in the thinking of the person telling you what to do. I'll
try to correct that serious flaw by simplifying your requirement to this
simple rule:

when the contents of the file is regarded as a sequence of 32-bit
integers, the value of the last 32-bit integer of the file is such that
the sum of the 32-bit integers throughout the file is 0 modulo 2^32.

this is fairly easy to hack together, but it depends on how you write to
your stream. if you write 32-bit integers to the stream (which means it
should be opened with :ELEMENT-TYPE '(SIGNED-BYTE 32) or UNSIGNED-BYTE
ditto), just sum them up while you write each integer, then write
(LDB (BYTE 32 0) (- <SUM>)) to the same stream just before closing it.

if you don't write 32-bit integers to the file, you're probably better
off writing it in one pass and reading it as 32-bit integers in another
pass, only to tack on the same 32-bit integer as describe above at the
end.

| 2) Write 32 bit chunks to the file, also accumulate the 32 bit chunks
| into this 32 bit integer object. The accumulation is a add, ignoring

| overflows (which is standard), then the final step is to take the
| negative (2's complement) all the accumulations have been done.

no, ignoring overflows is _not_ standard, it's a a hardware-oriented
design decision local to particular languages. the standard addition
function does not overflow to begin with. please don't confuse the
internal hardware representation of a value with the value.

however, whether you ignore overflow or extract a bit field from an
integer is only a conceptual difference. C-based life forms think in
terms of ignoring overflow because they don't know what it means not to.
Common Lisp programmers don't ignore overflows, but talk about values
_modulo_ some other value, instead.

#:Erik

[Andrew Cooke]

I recently looked at the following package. It provides an elegant
(imho) way of moving between binary and symbolic representations.
Basically, it's a framework that lets you describe binary structures and
access fields within them. (On the other hand, I never got round to
using it as I found a way of avoiding binary files altogether).

It might help you with your problem.

http://www.cs.uit.no/~frodef/sw/binary-types/

Andrew

PS I also contacted the author with some questions and got a helpful
reply, so it is supported.

In article <38A81589...@lmco.com>,

Scott Sheffield <scott.y....@lmco.com> wrote:
> I have created a binary file using Interleaf LISP and I need to put a
> checksum at the end of the file so that it can be loaded into the
> hardware. The problem is though I have a good idea what a checksum is
> and does I have no idea how to do this in LISP. Here is what I am told
I
> need to do:

[...]

Sent via Deja.com http://www.deja.com/
Before you buy.

[Philip Lijnzaad]

As other have remarked, doing a modulo is a very poor way to do checksums. A
commonly used checksum is the CRC32 described in RCS1952. A Lisp
implementation for this can be found on

http://www.thoughtstuff.com/rme/lisp.html#crc-32

along with background information on checksums and a link to the RFC.

Philip
--
Not getting what you want is sometimes a wonderful stroke of luck.
-----------------------------------------------------------------------------
Philip Lijnzaad, lijn...@ebi.ac.uk | European Bioinformatics Institute,rm A2-24
+44 (0)1223 49 4639 | Wellcome Trust Genome Campus, Hinxton
+44 (0)1223 49 4468 (fax) | Cambridgeshire CB10 1SD, GREAT BRITAIN
PGP fingerprint: E1 03 BF 80 94 61 B6 FC 50 3D 1F 64 40 75 FB 53

[David Hanley]

Interesting problem!

It is possible 32 bit values are not the best way to go, as it will
probably result in bignums being used on your system. Not
efficient. This *might* be more efficient ( and might not, too ):

(defmacro trim(x) `(setf ,x (logand ,x 65535)))

'loop'
(setf val (get-16-bits))
(write-to-file-val)
(incf low-16-checksum val)
(setf val (get-16-bits))
(write-to-file val)
(incf high-16-checksum (+ val (ash low-16-checksum val -15)))
(trim low-16-checksum-val)
(trim high-16-checksum-val)
'end-loop'

Of course, this is a pain, and is probably not worth it. You probably
just want something like:

'loop'
(setf val (get-32-bit-chunk))
(write-to-file val)
(setf checksum-32 (logand (+ checksum-32 val) 65535))
'end-loop'

But it's hard to know until we know more abut your in/out data
structures.

dave

[Christopher Browne]

Centuries ago, Nostradamus foresaw a time when Stig Hemmer would say:

>Robert Monfera <mon...@fisec.com> writes:
>> This additive checksum is not the best way to ensure integrity: rows of
>> 0s won't be missed. Isn't it better to use some standard method or just
>> count the number of records?
>

>The problem is he has to interact with some other system that uses
>this form of checksumming. I have seen this (fairly braindead) way of
>doing checksums before, and not in an Interleaf context, so you could
>call it a "standard method".

On the upside, in the "worse-is-better" frame of mind, this may be a
satisfactory approach for eliminating *most* errors.

It's obviously not as satisfactory as doing a leetle bit more work and
having a checksum capable of catching all errors with a high
probability of success.
--
The last good thing written in C was Franz Schubert's Symphony number 9.
-- Erwin Dieterich
cbbr...@hex.net- <http://www.hex.net/~cbbrowne/lsf.html>

[Pierre R. Mai]

cbbr...@news.hex.net (Christopher Browne) writes:

> On the upside, in the "worse-is-better" frame of mind, this may be a
> satisfactory approach for eliminating *most* errors.
>
> It's obviously not as satisfactory as doing a leetle bit more work and
> having a checksum capable of catching all errors with a high
> probability of success.

Well, it is only a very small amount of more work, since even Adler-32
checksums are much better, well documented (see e.g. RFC 1950), and
_very_ easy to implement (even on "strange" hardware like Palm's ;).

Here's a snippet of code that gives you an idea:

(defconstant +adler32-initial-seed+ #x00000001)

(declaim (inline update-adler32-byte))
(defun update-adler32-byte (adler byte)
(declare (type (unsigned-byte 32) adler)
(type (unsigned-byte 8) byte))
(macrolet ((s1 (adler) `(ldb (byte 16 0) ,adler))
(s2 (adler) `(ldb (byte 16 16) ,adler)))
(setf (s1 adler) (mod (+ (s1 adler) byte) 65521))
(setf (s2 adler) (mod (+ (s2 adler) (s1 adler)) 65521))
adler))

Regs, Pierre.

--
Pierre Mai <pm...@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]