I am looking for a simple way (usable on a powerful PC or a tiny
microcontroller) to verify a small amount of data of about eight
bytes.

Is it better to compare the data against a checksum or an xor of the
bytes?

The code is to look at certain offsets in some data for a header. The
header is to consist of the following fields in sequence.
  * a magic value
  * the eight bytes of data
  * the check value (based on the 8 bytes not including the magic
value)

Once the code recognises the above sequence as valid it can go ahead
with using the data in the eight-byte field. I know a CRC would be
stronger but would be space-consuming to calculate on a
microcontroller.

Of course an xor will give a multi-way parity check and a sum will mix
lower bits into higher ones. Is there any quantitative way of
assessing which is better?

James

James Harris <james.harris.1@googlemail.com> writes:

> I am looking for a simple way (usable on a powerful PC or a tiny
> microcontroller) to verify a small amount of data of about eight
> bytes.
>
> Is it better to compare the data against a checksum or an xor of the
> bytes?

For 8 bytes, it is easier and faster to compare the data with itself.

if a = 0x123456789ABCDEF then 
   ok
else
   bad
end


If you don't have 64-bit arithmetic, just do it twice on 32-bit words,
or four times on 16-bit words, or eight times on bytes.


> The code is to look at certain offsets in some data for a header. The
> header is to consist of the following fields in sequence.
>   * a magic value
>   * the eight bytes of data
>   * the check value (based on the 8 bytes not including the magic
> value)

if magic_value = EXPECTED_MAGIC
   and eight_bytes_of_data = eight_bytes_check_value then
    ok
else
    bad
end


> Once the code recognises the above sequence as valid it can go ahead
> with using the data in the eight-byte field. I know a CRC would be
> stronger but would be space-consuming to calculate on a
> microcontroller.

    lea eight_bytes_of_data,a0
    lea eight_butes_check_value,a1
    cmp.l (a0),(a1)
    bne.s bad
    cmp.l 4(a0),4(a1)
    bne.s bad
ok:
    do_good_things
bad:
    do_bad_things



> Of course an xor will give a multi-way parity check and a sum will mix
> lower bits into higher ones. Is there any quantitative way of
> assessing which is better?

What are your criteria?

-- 
__Pascal Bourguignon__

James Harris <james.harris.1@googlemail.com> writes:

> I am looking for a simple way (usable on a powerful PC or a tiny
> microcontroller) to verify a small amount of data of about eight
> bytes.
>
> Is it better to compare the data against a checksum or an xor of the
> bytes?

For an 8-byte value, just send it twice and compare.
-- 
"Writing is easy.
 All you do is sit in front of a typewriter and open a vein."
--Walter Smith

On Tue, 23 Dec 2008 09:44:03 -0800, Ben Pfaff
<blp@cs.stanford.edu> wrote:

>James Harris <james.harris.1@googlemail.com> writes:
>
>> I am looking for a simple way (usable on a powerful PC or a tiny
>> microcontroller) to verify a small amount of data of about eight
>> bytes.
>>
>> Is it better to compare the data against a checksum or an xor of the
>> bytes?
>
>For an 8-byte value, just send it twice and compare.

And if the data cannot be sent twice?

The OP says he has data; he did not say how he got it.


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

On 23 Dec, 17:31, p...@informatimago.com (Pascal J. Bourguignon)
wrote:
> James Harris <james.harri...@googlemail.com> writes:
> > I am looking for a simple way (usable on a powerful PC or a tiny
> > microcontroller) to verify a small amount of data of about eight
> > bytes.
>
> > Is it better to compare the data against a checksum or an xor of the
> > bytes?
>
> For 8 bytes, it is easier and faster to compare the data with itself.

I'll have _about_ 8 bytes. It could be 7 or it could be 9 or 10 for
example.


> if a =3D 0x123456789ABCDEF then
> =A0 =A0ok
> else
> =A0 =A0bad
> end

This will be fine for the magic value but the 8ish bytes of data will
not have the same values in each case.

....

> > The code is to look at certain offsets in some data for a header. The
> > header is to consist of the following fields in sequence.
> > =A0 * a magic value
> > =A0 * the eight bytes of data
> > =A0 * the check value (based on the 8 bytes not including the magic
> > value)
>
> if magic_value =3D EXPECTED_MAGIC
> =A0 =A0and eight_bytes_of_data =3D eight_bytes_check_value then
> =A0 =A0 ok
> else
> =A0 =A0 bad
> end

The eight or so bytes are of _data_ and are not fixed.

>
> > Once the code recognises the above sequence as valid it can go ahead
> > with using the data in the eight-byte field. I know a CRC would be
> > stronger but would be space-consuming to calculate on a
> > microcontroller.
>
....

> > Of course an xor will give a multi-way parity check and a sum will mix
> > lower bits into higher ones. Is there any quantitative way of
> > assessing which is better?
>
> What are your criteria?

* About 8 bytes of data
* Need a checksum or an xor of all bytes
* Byte based arithmetic (so is suitable for tiny computer; a 9th byte
would be the check value)

James

On 23 Dec, 17:44, Ben Pfaff <b...@cs.stanford.edu> wrote:
> James Harris <james.harri...@googlemail.com> writes:
> > I am looking for a simple way (usable on a powerful PC or a tiny
> > microcontroller) to verify a small amount of data of about eight
> > bytes.
>
> > Is it better to compare the data against a checksum or an xor of the
> > bytes?
>
> For an 8-byte value, just send it twice and compare.

Not good as this would give a false positive of data such as all of
the same value such as all nulls or all asterisks. I'd rather use a
value calculated from the data.

James

cri@tiac.net (Richard Harter) writes:

> On Tue, 23 Dec 2008 09:44:03 -0800, Ben Pfaff
> <blp@cs.stanford.edu> wrote:
>
>>James Harris <james.harris.1@googlemail.com> writes:
>>
>>> I am looking for a simple way (usable on a powerful PC or a tiny
>>> microcontroller) to verify a small amount of data of about eight
>>> bytes.
>>>
>>> Is it better to compare the data against a checksum or an xor of the
>>> bytes?
>>
>>For an 8-byte value, just send it twice and compare.
>
> And if the data cannot be sent twice?
>
> The OP says he has data; he did not say how he got it.

If he can choose the checksum to be sent, and its size, then
presumably he can choose to send something a little bigger.
-- 
Ben Pfaff 
http://benpfaff.org

James Harris <james.harris.1@googlemail.com> writes:

> On 23 Dec, 17:44, Ben Pfaff <b...@cs.stanford.edu> wrote:
>> James Harris <james.harri...@googlemail.com> writes:
>> > I am looking for a simple way (usable on a powerful PC or a tiny
>> > microcontroller) to verify a small amount of data of about eight
>> > bytes.
>>
>> > Is it better to compare the data against a checksum or an xor of the
>> > bytes?
>>
>> For an 8-byte value, just send it twice and compare.
>
> Not good as this would give a false positive of data such as all of
> the same value such as all nulls or all asterisks. I'd rather use a
> value calculated from the data.

How about sending the data, then sending it again passed through
some kind of simple transform, e.g. XOR each byte with 0xaa?

Beyond that, there are many choices for a simple checksum:

        * An 8- or 16-bit CRC.

        * The TCP/IP checksum.

        * A traditional hash function
          (http://burtleburtle.net/bob/hash/ is a good place to
          start).
-- 
"J'avais trouv'e ma religion :
 rien ne me parut plus important qu'un livre.
 La biblioth`eque, j'y voyais un temple."
--Jean-Paul Sartre

On 23 Dec, 22:20, Ben Pfaff <b...@cs.stanford.edu> wrote:
> James Harris <james.harri...@googlemail.com> writes:
> > On 23 Dec, 17:44, Ben Pfaff <b...@cs.stanford.edu> wrote:
> >> James Harris <james.harri...@googlemail.com> writes:
> >> > I am looking for a simple way (usable on a powerful PC or a tiny
> >> > microcontroller) to verify a small amount of data of about eight
> >> > bytes.
>
> >> > Is it better to compare the data against a checksum or an xor of the
> >> > bytes?
>
> >> For an 8-byte value, just send it twice and compare.
>
> > Not good as this would give a false positive of data such as all of
> > the same value such as all nulls or all asterisks. I'd rather use a
> > value calculated from the data.
>
> How about sending the data, then sending it again passed through
> some kind of simple transform, e.g. XOR each byte with 0xaa?
>
> Beyond that, there are many choices for a simple checksum:
>
> =A0 =A0 =A0 =A0 * An 8- or 16-bit CRC.
>
> =A0 =A0 =A0 =A0 * The TCP/IP checksum.
>
> =A0 =A0 =A0 =A0 * A traditional hash function
> =A0 =A0 =A0 =A0 =A0 (http://burtleburtle.net/bob/hash/is a good place to
> =A0 =A0 =A0 =A0 =A0 start).

I'll bear these in mind but I don't want to overcomplicate this just
now. A simple 8-bit checksum would be fine. I was just wondering
whether I'd be better to change that checksum into a big xor of the
data.

One slight alteration to the basic algorithm: I may require the
checksum to add to 0xff or 0x55 or something nonzero rather than zero
as I don't want to get a false positive on all-zeros data.

James

Ben Pfaff wrote:
> James Harris <james.harris.1@googlemail.com> writes:
> 
>> On 23 Dec, 17:44, Ben Pfaff <b...@cs.stanford.edu> wrote:
>>> James Harris <james.harri...@googlemail.com> writes:
>>>> I am looking for a simple way (usable on a powerful PC or a tiny
>>>> microcontroller) to verify a small amount of data of about eight
>>>> bytes.
>>>> Is it better to compare the data against a checksum or an xor of the
>>>> bytes?
>>> For an 8-byte value, just send it twice and compare.
>> Not good as this would give a false positive of data such as all of
>> the same value such as all nulls or all asterisks. I'd rather use a
>> value calculated from the data.
> 
> How about sending the data, then sending it again passed through
> some kind of simple transform, e.g. XOR each byte with 0xaa?
....

Why 0xaa rather than 0x00? In other words, why not send the data
followed by its own 1's complement? The check would xor the two values
and reject if any bit is zero.

The best approach depends on the types of failures that are expected.
Sending the original and the 1's complement deals with any group of
wires stuck at 0 or 1 in a parallel path, as well as one bit errors in a
serial path.

Patricia

"James Harris" <james.harris.1@googlemail.com> wrote in message 
news:b3f93c69-e85b-41ea-88a9-5ad830ce67d4@w24g2000prd.googlegroups.com...
>I am looking for a simple way (usable on a powerful PC or a tiny
> microcontroller) to verify a small amount of data of about eight
> bytes.
>
> Is it better to compare the data against a checksum or an xor of the
> bytes?
>
> The code is to look at certain offsets in some data for a header. The
> header is to consist of the following fields in sequence.
>  * a magic value
>  * the eight bytes of data
>  * the check value (based on the 8 bytes not including the magic
> value)
>
> Once the code recognises the above sequence as valid it can go ahead
> with using the data in the eight-byte field. I know a CRC would be
> stronger but would be space-consuming to calculate on a
> microcontroller.
>
> Of course an xor will give a multi-way parity check and a sum will mix
> lower bits into higher ones. Is there any quantitative way of
> assessing which is better?

What about the ninth byte being the parity bits of each of the other eight? 
Then you can detect (but not fix) single bit errors in any of the eight data 
bytes.

To fix single bit errors, you might need Hamming codes, taking more data and 
being more complex.

What error-rate are you expecting?

-- 
Bartc 

On 23 Dec, 23:33, "Bartc" <ba...@freeuk.com> wrote:
> "James Harris" <james.harri...@googlemail.com> wrote in message
>
> news:b3f93c69-e85b-41ea-88a9-5ad830ce67d4@w24g2000prd.googlegroups.com...
>
>
>
> >I am looking for a simple way (usable on a powerful PC or a tiny
> > microcontroller) to verify a small amount of data of about eight
> > bytes.
>
> > Is it better to compare the data against a checksum or an xor of the
> > bytes?
>
> > The code is to look at certain offsets in some data for a header. The
> > header is to consist of the following fields in sequence.
> > =A0* a magic value
> > =A0* the eight bytes of data
> > =A0* the check value (based on the 8 bytes not including the magic
> > value)
>
> > Once the code recognises the above sequence as valid it can go ahead
> > with using the data in the eight-byte field. I know a CRC would be
> > stronger but would be space-consuming to calculate on a
> > microcontroller.
>
> > Of course an xor will give a multi-way parity check and a sum will mix
> > lower bits into higher ones. Is there any quantitative way of
> > assessing which is better?
>
> What about the ninth byte being the parity bits of each of the other eigh=
t?
> Then you can detect (but not fix) single bit errors in any of the eight d=
ata
> bytes.

The bytes don't have parity bits ... so I guess you mean something
else. If you mean the ninth byte being eight parity bits where bit
zero is a parity bit for the other bit zeros that's what I mean by
xor. If you mean to work out parity bits of each byte and store these
in the ninth I think that a) is more complex to implement, b) doesn't
add anything to xor, c) doesn't work well if I need 9 bytes of data or
more.

>
> To fix single bit errors, you might need Hamming codes, taking more data =
and
> being more complex.
>
> What error-rate are you expecting?

No error rate. People seem to be expecting network transmission but I
didn't mention that. The issue is I have a block of text and binary
data and need to determine where within it the significant data start.
The significant data will start with a known magic value but I want to
supplement that with a checksum of the data in the header.

James

James Harris wrote:
> On 23 Dec, 23:33, "Bartc" <ba...@freeuk.com> wrote:
>> "James Harris" <james.harri...@googlemail.com> wrote in message
>> news:b3f93c69-e85b-41ea-88a9-5ad830ce67d4@w24g2000prd.googlegroups.com...
>>> I am looking for a simple way (usable on a powerful PC or a tiny
>>> microcontroller) to verify a small amount of data of about eight
>>> bytes.
>>
>>> Is it better to compare the data against a checksum or an xor of the
>>> bytes?
>>
>>> The code is to look at certain offsets in some data for a header.
>>> The header is to consist of the following fields in sequence.
>>> * a magic value
>>> * the eight bytes of data
>>> * the check value (based on the 8 bytes not including the magic
>>> value)

>> What about the ninth byte being the parity bits of each of the other
>> eight?

> The bytes don't have parity bits ... so I guess you mean something
> else. If you mean the ninth byte being eight parity bits where bit
> zero is a parity bit for the other bit zeros that's what I mean by
> xor.

Yes, although I was thinking the other way (parity for byte 0 then byte 1
etc). But it's clear calculating the other way will be nearly the same.

>> What error-rate are you expecting?
>
> No error rate. People seem to be expecting network transmission but I
> didn't mention that. The issue is I have a block of text and binary
> data and need to determine where within it the significant data start.
> The significant data will start with a known magic value but I want to
> supplement that with a checksum of the data in the header.

So you want a marker of some kind? So for example in this text:

ABCDEF#SECT12*PQRST

# is the magic number, SECT12 is the data you need, and * is the checkbyte.
And the idea is to embellish SECT12 in a way that is not likely to occur by
chance in the normal text? (BTW how will you know the length of the data?)

-- 
Bartc

James Harris wrote:
> 
> I am looking for a simple way (usable on a powerful PC or a tiny
> microcontroller) to verify a small amount of data of about eight
> bytes.
> 
> Is it better to compare the data against a checksum or an xor of
> the bytes?

I would do neither.  I would compute a 16 bit CCIT crc during
transmission, and append those two bytes.  The receiver can repeat
the process and compare the crcs.  This is not sensitive to the
message length, but you will need to know it.  The chance of an
undetected error is extremely low.

-- 
Merry Christmas, Happy Hanukah, Happy New Year
 Joyeux Noel, Bonne Annee, Frohe Weihnachten
Chuck F (cbfalconer at maineline dot net)
     <http://cbfalconer.home.att.net>

On 24 Dec, 01:07, "Bartc" <ba...@freeuk.com> wrote:

....

> So you want a marker of some kind? So for example in this text:
>
> ABCDEF#SECT12*PQRST
>
> # is the magic number, SECT12 is the data you need, and * is the checkbyte.
> And the idea is to embellish SECT12 in a way that is not likely to occur by
> chance in the normal text? (BTW how will you know the length of the data?)

Yes, that's well expressed. '#' will really be a mulitibyte magic
number rather than a single byte. SECT12 will be around 8 bytes of
data whose content will vary but not its length. The length will be
fixed once the format is defined and stable. And, yes, '*' should be
one byte.

If it's relevant SECT12 will be a header to what follows, PQRST... in
your example.

BTW, I'm sorry this has become such that these details needed to be
added after the original question. I would have posted the full
picture at the start (maybe I should still do so) if I thought it was
relevant. All I wanted was some data on whether a multi-way xor or a
checksum gave a better error detection rate.

James

On 24 Dec, 01:44, CBFalconer <cbfalco...@yahoo.com> wrote:
> James Harris wrote:
>
> > I am looking for a simple way (usable on a powerful PC or a tiny
> > microcontroller) to verify a small amount of data of about eight
> > bytes.
>
> > Is it better to compare the data against a checksum or an xor of
> > the bytes?
>
> I would do neither. =A0I would compute a 16 bit CCIT crc during
> transmission, and append those two bytes. =A0The receiver can repeat
> the process and compare the crcs. =A0This is not sensitive to the
> message length, but you will need to know it. =A0The chance of an
> undetected error is extremely low.

There is no transmission. This will be a block of data in memory. At
the beginning of the block will be an unknown number of garbage bytes
which need to be skipped.

All values should be 8-bit only.

James

James Harris <james.harris.1@googlemail.com> writes:

> On 23 Dec, 17:31, p...@informatimago.com (Pascal J. Bourguignon)
> wrote:
>> James Harris <james.harri...@googlemail.com> writes:
>> > I am looking for a simple way (usable on a powerful PC or a tiny
>> > microcontroller) to verify a small amount of data of about eight
>> > bytes.
>>
>> > Is it better to compare the data against a checksum or an xor of the
>> > bytes?
>>
>> For 8 bytes, it is easier and faster to compare the data with itself.
>
> I'll have _about_ 8 bytes. It could be 7 or it could be 9 or 10 for
> example.

Ah, ok.


>> > Of course an xor will give a multi-way parity check and a sum will mix
>> > lower bits into higher ones. Is there any quantitative way of
>> > assessing which is better?
>>
>> What are your criteria?
>
> * About 8 bytes of data
> * Need a checksum or an xor of all bytes
> * Byte based arithmetic (so is suitable for tiny computer; a 9th byte
>   would be the check value)

The question is how many errors do you want to be able to detect, and
how many errors do you want to be able to correct?  Also, if several
bit errors may occur, what kind of error patterns do  you expect?
(eg. if you expect to lose one byte, then an XOR is good enough.  But
if you expect to lose the same bit over several bytes, then you'd
rather want parity bits or a checksum).

http://en.wikipedia.org/wiki/Error_detection_and_correction

In any case, it's hard to beat the simplicity of the checksum.
-- 
__Pascal Bourguignon__

CBFalconer <cbfalconer@yahoo.com> writes:

> James Harris wrote:
>> 
>> I am looking for a simple way (usable on a powerful PC or a tiny
>> microcontroller) to verify a small amount of data of about eight
>> bytes.
>> 
>> Is it better to compare the data against a checksum or an xor of
>> the bytes?
>
> I would do neither.  I would compute a 16 bit CCIT crc during
> transmission, and append those two bytes.  The receiver can repeat
> the process and compare the crcs.  This is not sensitive to the
> message length, but you will need to know it.  The chance of an
> undetected error is extremely low.

About 1/65536 I'd say, no?

-- 
__Pascal Bourguignon__

James Harris <james.harris.1@googlemail.com> writes:

> On 24 Dec, 01:44, CBFalconer <cbfalco...@yahoo.com> wrote:
>> James Harris wrote:
>>
>> > I am looking for a simple way (usable on a powerful PC or a tiny
>> > microcontroller) to verify a small amount of data of about eight
>> > bytes.
>>
>> > Is it better to compare the data against a checksum or an xor of
>> > the bytes?
>>
>> I would do neither. �I would compute a 16 bit CCIT crc during
>> transmission, and append those two bytes. �The receiver can repeat
>> the process and compare the crcs. �This is not sensitive to the
>> message length, but you will need to know it. �The chance of an
>> undetected error is extremely low.
>
> There is no transmission. This will be a block of data in memory. At
> the beginning of the block will be an unknown number of garbage bytes
> which need to be skipped.
>
> All values should be 8-bit only.

Do you realize that this is an entirely different problem?

Do you know at least the length of the block to be recognized?
Are your garbage bytes random?  
Are the patterns to be recognized random too?

-- 
__Pascal Bourguignon__

On 24 Dec, 09:56, p...@informatimago.com (Pascal J. Bourguignon)
wrote:
....
> > There is no transmission. This will be a block of data in memory. At
> > the beginning of the block will be an unknown number of garbage bytes
> > which need to be skipped.
>
> > All values should be 8-bit only.
>
> Do you realize that this is an entirely different problem?

Really? In what respect?

>
> Do you know at least the length of the block to be recognized?

The block to be recognised will be about 8 bytes long.....

> Are your garbage bytes random? =A0

They could contain anything.

> Are the patterns to be recognized random too?

The data to be recognised will be, er, data. It will vary. Hence the
need for a check value.

James

James Harris wrote:
) On 24 Dec, 09:56, p...@informatimago.com (Pascal J. Bourguignon)
) wrote:
) ...
)> > There is no transmission. This will be a block of data in memory. At
)> > the beginning of the block will be an unknown number of garbage bytes
)> > which need to be skipped.
)>
)> > All values should be 8-bit only.
)>
)> Do you realize that this is an entirely different problem?
)
) Really? In what respect?

How many 'unknown garbage bytes' will have to be skipped ?

For example, for 10 garbage bytes that means that 10 checksums must
(correctly) fail.  If you have an 8-bit checksum/CRC/xor/whatever then
there is roughly a 1/256 chance that any one of those checks gives
a false positive.

For a mere 10 'unknown garbage bytes' that turns out to be almost
a 4% cumulative chance of a fail (false positive).

Are you still sure you want only 8 bits ?


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

On 24 Dec, 10:35, Willem <wil...@stack.nl> wrote:
> James Harris wrote:
>
> ) On 24 Dec, 09:56, p...@informatimago.com (Pascal J. Bourguignon)) wrote=
:
>
> ) ...
> )> > There is no transmission. This will be a block of data in memory. At
> )> > the beginning of the block will be an unknown number of garbage byte=
s
> )> > which need to be skipped.
> )>
> )> > All values should be 8-bit only.
> )>
> )> Do you realize that this is an entirely different problem?
> )
> ) Really? In what respect?
>
> How many 'unknown garbage bytes' will have to be skipped ?
>
> For example, for 10 garbage bytes that means that 10 checksums must
> (correctly) fail. =A0If you have an 8-bit checksum/CRC/xor/whatever then
> there is roughly a 1/256 chance that any one of those checks gives
> a false positive.
>
> For a mere 10 'unknown garbage bytes' that turns out to be almost
> a 4% cumulative chance of a fail (false positive).
>
> Are you still sure you want only 8 bits ?

Very good point but let me repeat some of my original post:

"I am looking for a simple way (usable on a powerful PC or a tiny
microcontroller) to verify a small amount of data of about eight
bytes.

The code is to look at certain offsets in some data for a header. The
header is to consist of the following fields in sequence.
  * a magic value
  * the eight bytes of data
  * the check value (based on the 8 bytes not including the magic
value)"

The magic value will be a number of bytes (as they can be checked
individually). The rest (the data and the check value) will be single
bytes. I'm not happy with using the magic value as the only check for
a valid header hence the need for a check value. Both the magic value
and the check value will need to match.

James

James Harris wrote:
> On 24 Dec, 01:07, "Bartc" <ba...@freeuk.com> wrote:

>> ABCDEF#SECT12*PQRST
>>
>> # is the magic number, SECT12 is the data you need, and * is the
>> checkbyte. And the idea is to embellish SECT12 in a way that is not
>> likely to occur by chance in the normal text? (BTW how will you know
>> the length of the data?)
>
> Yes, that's well expressed. '#' will really be a mulitibyte magic
> number rather than a single byte. SECT12 will be around 8 bytes of
> data whose content will vary but not its length. The length will be
> fixed once the format is defined and stable. And, yes, '*' should be
> one byte.
>
> If it's relevant SECT12 will be a header to what follows, PQRST... in
> your example.
>
> BTW, I'm sorry this has become such that these details needed to be
> added after the original question. I would have posted the full
> picture at the start (maybe I should still do so) if I thought it was
> relevant. All I wanted was some data on whether a multi-way xor or a
> checksum gave a better error detection rate.

As Pascal has said this is a rather different problem. There is no actual 
error to be detected.

You just have to consider the probability that the marker block you need, 
#SECT12* for example, may occur in the preceding 'garbage' bytes ABCDEF.

And if the bytes are really garbage (for example may happen to be the 
contents of some memory location that happen to contain the last calculation 
of #SECT12*, no matter how elaborate), then this probability could be 
significant.

-- 
Bartc 

On 24 Dec, 11:02, "Bartc" <ba...@freeuk.com> wrote:

....

> As Pascal has said this is a rather different problem. There is no actual
> error to be detected.

I never said there was! Someone has assumed that.

James

James Harris <james.harris.1@googlemail.com> writes:

> On 24 Dec, 10:35, Willem <wil...@stack.nl> wrote:
>> James Harris wrote:
>>
>> ) On 24 Dec, 09:56, p...@informatimago.com (Pascal J. Bourguignon)) wrote:
>>
>> ) ...
>> )> > There is no transmission. This will be a block of data in memory. At
>> )> > the beginning of the block will be an unknown number of garbage bytes
>> )> > which need to be skipped.
>> )>
>> )> > All values should be 8-bit only.
>> )>
>> )> Do you realize that this is an entirely different problem?
>> )
>> ) Really? In what respect?
>>
>> How many 'unknown garbage bytes' will have to be skipped ?
>>
>> For example, for 10 garbage bytes that means that 10 checksums must
>> (correctly) fail. �If you have an 8-bit checksum/CRC/xor/whatever then
>> there is roughly a 1/256 chance that any one of those checks gives
>> a false positive.
>>
>> For a mere 10 'unknown garbage bytes' that turns out to be almost
>> a 4% cumulative chance of a fail (false positive).
>>
>> Are you still sure you want only 8 bits ?
>
> Very good point but let me repeat some of my original post:
>
> "I am looking for a simple way (usable on a powerful PC or a tiny
> microcontroller) to verify a small amount of data of about eight
> bytes.
>
> The code is to look at certain offsets in some data for a header. The
> header is to consist of the following fields in sequence.
>   * a magic value
>   * the eight bytes of data
>   * the check value (based on the 8 bytes not including the magic
> value)"
>
> The magic value will be a number of bytes (as they can be checked
> individually). The rest (the data and the check value) will be single
> bytes. I'm not happy with using the magic value as the only check for
> a valid header hence the need for a check value. Both the magic value
> and the check value will need to match.

I would use a hash.  If there was more bytes and processing power like
MD5.  But since there's so little data to match we would have to
reduce it, perhaps using bytes instead of 32-bit chunks.  In any case,
you will probably want to benefit from the avalanche effect.  I think
we can exclude simple xor or parity based checks.

Do you further have any time or code space constraints on the "tiny"
microcontroller?


In the mean time, a simple checksum on 16 bits, where successive bytes
are shifted by 0, 2, 4, 6, 1, 3, 5, 7, added to the length of the
tested patted (shifted by 8) seems to give good results, given that we
already have a 2 or 4 byte magic value preceding.

However, if the patterns are to be identified in not too many random
bytes, just using a 32-bit magic value instead of a 16-bit magic value
seems to be enough.  If you add 16-bit checksum, then it could be
easier to use a 48-bit magic value instead.




;; Common Lisp code following ; http://clisp.cons.org

(deftype uint8  () '(unsigned-byte 8))
(deftype uint16 () '(unsigned-byte 16))

(defun +[16]     (x y) (mod (+ x y) #x10000))
(defun shift[16] (x n) (logand #xffff (ash x n)))


(defun compute-check (pattern)
  (loop
     :with sum = (shift[16] (length pattern) 8)
     :for shift = 0 :then (case shift (7 0) (8 1) (otherwise (+ 2 shift)))
     :for byte :across pattern
     :do (setf sum (+[16] sum (shift[16] byte shift)))
     :finally (return (vector (ldb (byte 8 8) sum) (ldb (byte 8 0) sum)))))


(defun random-byte-vector (length)
  (loop
     :with vector = (make-array length :element-type 'uint8 :initial-element 0)
     :for i :from 0 :below (length vector)
     :do (setf (aref vector i) (random 256))
     :finally (return vector)))

(defparameter *smallest-block-length* 5)
(defparameter *greatest-block-length* 11)
(defparameter *test-store-length* 1000000)

(defun count-occurences (data instance)
  (loop
     :for start = 0 :then (1+ pos)
     :for pos = (search instance data :start2 start)
     :while pos
     :count 1))

(defun make-test-case ()
  (let* ((store   (random-byte-vector *test-store-length*))
         (magic   (random-byte-vector (+ 2 (* 2 (random 2)))))
         (pattern (random-byte-vector (+ *smallest-block-length* (random (- *greatest-block-length* *smallest-block-length* -1)))))
         (check   (compute-check pattern))
         (position (random (- (length store)
                              (length magic) (length pattern) (length check)))))
    (replace store magic   :start1 position)
    (replace store pattern :start1 (+ position (length magic)))
    (replace store check   :start1 (+ position (length magic) (length pattern)))
    (list store magic position (count-occurences store magic))))


(defun find-pattern (store magic)
  (loop
     :with results = '()
     :with pattern = (make-array *greatest-block-length* :element-type 'uint8
                                 :adjustable t :displaced-to store
                                 :fill-pointer 0 :displaced-index-offset 0)
     :with check  = (make-array 2 :element-type 'uint8
                                 :adjustable t :displaced-to store
                                 :displaced-index-offset 0)
     :for start = 0 :then (1+ magicpos)
     :for magicpos = (search magic store :start2 start)
     :while magicpos
     :do (loop
            :for patternlen :from *smallest-block-length* :to *greatest-block-length*
            :do
            (setf pattern (adjust-array pattern *greatest-block-length* :element-type 'uint8
                                        :displaced-to store
                                        :fill-pointer patternlen :displaced-index-offset (+ magicpos (length magic)))
                  check (adjust-array check 2 :element-type 'uint8
                                      :displaced-to store
                                      :displaced-index-offset (+ magicpos (length magic) patternlen)))
            (when (equalp (compute-check pattern) check)
              (push magicpos results)))
     :finally (return results)))

(loop
   :repeat 1000
   :do (destructuring-bind (store magic position magic-occurences) (make-test-case)
         (format t "~2%~D occurences of the magic ~S in the store.~%" magic-occurences magic)
         (format t "pattern position: ~D~%" position)
         (let ((result  (find-pattern store magic)))
           (format t "found pattern at position~p: ~{~D~^, ~}~%" (length result) result)
           (unless (and (= 1 (length result)) (= (first result) position))
             (if (null result)
                 (format t "FALSE NEGATIVE!~%")
                 (format t "FALSE POSITIVE~:(~P~)!~%" (1- (length result))))))))


16 occurences of the magic #(203 205) in the store.
pattern position: 416443
found pattern at position: 416443


1 occurences of the magic #(49 178 57 4) in the store.
pattern position: 877734
found pattern at position: 877734


14 occurences of the magic #(197 110) in the store.
pattern position: 793484
found pattern at position: 793484


1 occurences of the magic #(197 66 107 250) in the store.
pattern position: 553626
found pattern at position: 553626


1 occurences of the magic #(251 139 90 240) in the store.
pattern position: 15663
found pattern at position: 15663


1 occurences of the magic #(71 114 227 22) in the store.
pattern position: 565064
found pattern at position: 565064


16 occurences of the magic #(103 46) in the store.
pattern position: 832710
found pattern at position: 832710


17 occurences of the magic #(96 129) in the store.
pattern position: 998777
found pattern at position: 998777


1 occurences of the magic #(158 152 223 188) in the store.
pattern position: 219018
found pattern at position: 219018


16 occurences of the magic #(230 180) in the store.
pattern position: 477921
found pattern at position: 477921


1 occurences of the magic #(46 232 5 197) in the store.
pattern position: 194366
found pattern at position: 194366


1 occurences of the magic #(7 15 54 158) in the store.
pattern position: 521988
found pattern at position: 521988


15 occurences of the magic #(27 32) in the store.
pattern position: 30889
found pattern at position: 30889


1 occurences of the magic #(189 95 160 187) in the store.
pattern position: 1525
found pattern at position: 1525


1 occurences of the magic #(112 8 23 64) in the store.
pattern position: 988448
found pattern at position: 988448


1 occurences of the magic #(93 208 222 1) in the store.
pattern position: 803004
found pattern at position: 803004


14 occurences of the magic #(232 188) in the store.
pattern position: 484755
found pattern at position: 484755

....



-- 
__Pascal Bourguignon__

James Harris wrote:
> On 24 Dec, 09:56, p...@informatimago.com (Pascal J. Bourguignon)
> wrote:
> ...
>>> There is no transmission. This will be a block of data in memory. At
>>> the beginning of the block will be an unknown number of garbage bytes
>>> which need to be skipped.
>>> All values should be 8-bit only.
>> Do you realize that this is an entirely different problem?
> 
> Really? In what respect?
> 
>> Do you know at least the length of the block to be recognized?
> 
> The block to be recognised will be about 8 bytes long.....
> 
>> Are your garbage bytes random?  
> 
> They could contain anything.
> 
>> Are the patterns to be recognized random too?
> 
> The data to be recognised will be, er, data. It will vary. Hence the
> need for a check value.

Disregard my previous comment - I didn't understand the problem.

In this situation, any pattern in the marker tends to increase the
probability of a false match, because the same pattern could appear in
the junk data, especially if you use a well know checksum algorithm

My new suggestion is a truly random key, obtained from e.g.
http://www.fourmilab.ch/hotbits/. Every additional byte of true random
data divides the probability of a false match by 256. You just have to
decide what probability of false match is acceptable to you, and use
enough bytes of random data.

Encode the random key in your program in some way that ensures that it
is not present literally. For example, store it as a hex string, two
characters per byte.

Even if the false match data was produced by a program that also uses
HotBits, it would get a different bit pattern.

If you need to deal with false matches due to old copies of your own
data, xor the random key with a string produced by repeating a
sequence number enough times to be the same length as the random string.

Patricia

On 24 Dec, 15:38, p...@informatimago.com (Pascal J. Bourguignon)
wrote:
....
> > "I am looking for a simple way (usable on a powerful PC or a tiny
> > microcontroller) to verify a small amount of data of about eight
> > bytes.
>
> > The code is to look at certain offsets in some data for a header. The
> > header is to consist of the following fields in sequence.
> > =A0 * a magic value
> > =A0 * the eight bytes of data
> > =A0 * the check value (based on the 8 bytes not including the magic
> > value)"
>
> > The magic value will be a number of bytes (as they can be checked
> > individually). The rest (the data and the check value) will be single
> > bytes. I'm not happy with using the magic value as the only check for
> > a valid header hence the need for a check value. Both the magic value
> > and the check value will need to match.
>
> I would use a hash. =A0If there was more bytes and processing power like
> MD5. =A0But since there's so little data to match we would have to
> reduce it, perhaps using bytes instead of 32-bit chunks. =A0In any case,
> you will probably want to benefit from the avalanche effect. =A0I think
> we can exclude simple xor or parity based checks.

This is what I was asking. (In fact it is the only thing I was
asking.) Why would you say addition is better than an xor? (i.e. why
is the carry propagation an advantage?) The output will be the same
size - one byte - in either case.

>
> Do you further have any time or code space constraints on the "tiny"
> microcontroller?
>

Not really. The tinyest I am aware of is a PIC. Maybe there are
smaller. The PIC is an 8-bit machine.

>
> In the mean time, a simple checksum on 16 bits, where successive bytes
> are shifted by 0, 2, 4, 6, 1, 3, 5, 7, added to the length of the
> tested patted (shifted by 8) seems to give good results, given that we
> already have a 2 or 4 byte magic value preceding.

I think I would use a magic of at least 4 bytes.

Thanks for the code (snipped) but a simple solution is all that's
needed. I'm just needing to know if a checksum or an xor would be more
dependable (and why).

The one thing that has come up is to use a 1's complement of the check
value to guard against the input data being all zeros.

James

James Harris <james.harris.1@googlemail.com> writes:

> I am looking for a simple way (usable on a powerful PC or a tiny
> microcontroller) to verify a small amount of data of about eight
> bytes.
> 
> Is it better to compare the data against a checksum or an xor of the
> bytes?
> 
> The code is to look at certain offsets in some data for a header. The
> header is to consist of the following fields in sequence.
>   * a magic value
>   * the eight bytes of data
>   * the check value (based on the 8 bytes not including the magic
> value)
> 
> Once the code recognises the above sequence as valid it can go ahead
> with using the data in the eight-byte field. I know a CRC would be
> stronger but would be space-consuming to calculate on a
> microcontroller.
> 
> Of course an xor will give a multi-way parity check and a sum will mix
> lower bits into higher ones. Is there any quantitative way of
> assessing which is better?

There are two kinds of "errors" I think you're interested in here.

The first is where one or more of the data bytes is corrupted;  this
situation is the standard one in data transmission, and probably well
understood.

The second is where you're somehow looking at just the wrong memory
locations, and the (random) checksum doesn't have anything to do with
the data bytes.  For this situation you want checksum values that are
biased /against/ whatever values are common in your environment.
These considerations may lead to a quite different set of choices for
how you do the checksumming.

Having said that, I offer this suggestion for a checksum method:

    unsigned
    checksum_for( const unsigned char data[], unsigned n ){
        unsigned i;
        unsigned char a;

        for(  a = 0x18, i = 0;  i < n;  i++  ){
            a += data[i] + (0xFF - a <= data[i]);
            a = (a << 1) + (a >> 7);
        }

        return  a + 1;
    }

The idea is to form a byte sum modulo 255, circular shifting by one as
we go.  Adding one at the end produces a value in the range of 1 to
255 (ie, always non-zero).  The initial value of a is chosen rather
arbitrarily, as is the shift amount;  I don't think the result is
especially sensitive to either, although I've tried changing only the
initial value of a.  The code space cost is a little more than doing
XOR, but not a lot more.

The behavior of this function under the first set of considerations
seems at least reasonably good.  It detects all one-bit errors on
inputs of three bytes, so it's at least as good as XOR in that
respect.  The output (usually) changes under swaps or extending with
zeroes, which is better than XOR.

The behavior under the second set of considerations (biasing against
byte values that are common in the execution environment) depends
on the particulars of that environment;  needless to say, you're
better equipped to evaluate that than I am.

Depending on the relative weights of the two kind of considerations,
you might want a very different sort of checksumming scheme, that
yields a smaller set of checksum values, all of which are unlikely
values in your execution environment.  Here again you have a better
idea of how important that is.

Good luck!

On Dec 24, 12:03=A0pm, James Harris <james.harri...@googlemail.com>
wrote:
> On 24 Dec, 15:38, p...@informatimago.com (Pascal J. Bourguignon)
> wrote:
> ...
>
[]
> This is what I was asking. (In fact it is the only thing I was
> asking.) Why would you say addition is better than an xor? (i.e. why
> is the carry propagation an advantage?) The output will be the same
> size - one byte - in either case.
>
>
>
> > Do you further have any time or code space constraints on the "tiny"
> > microcontroller?
>
> Not really. The tinyest I am aware of is a PIC. Maybe there are
> smaller. The PIC is an 8-bit machine.
>
>
>
> > In the mean time, a simple checksum on 16 bits, where successive bytes
> > are shifted by 0, 2, 4, 6, 1, 3, 5, 7, added to the length of the
> > tested patted (shifted by 8) seems to give good results, given that we
> > already have a 2 or 4 byte magic value preceding.
>
> I think I would use a magic of at least 4 bytes.
>
> Thanks for the code (snipped) but a simple solution is all that's
> needed. I'm just needing to know if a checksum or an xor would be more
> dependable (and why).

Let me rephrase your question:
I am just needing to know if painting the house blue or planting roses
would be more dependable (and why).

You have not really defined the errors you seek to avoid. So answering
the WHY is nearly impossible. And you seem to reject suggestions of
one over the other without the WHY. Basically IMHO we cannot answer an
incomplete question.

Ed

James Harris <james.harris.1@googlemail.com> writes:

> On 24 Dec, 15:38, p...@informatimago.com (Pascal J. Bourguignon)
> wrote:
> ...
>> I would use a hash. �If there was more bytes and processing power like
>> MD5. �But since there's so little data to match we would have to
>> reduce it, perhaps using bytes instead of 32-bit chunks. �In any case,
>> you will probably want to benefit from the avalanche effect. �I think
>> we can exclude simple xor or parity based checks.
>
> This is what I was asking. (In fact it is the only thing I was
> asking.) Why would you say addition is better than an xor? (i.e. why
> is the carry propagation an advantage?) The output will be the same
> size - one byte - in either case.

The "avalanche effect" means that a small change in the input data means
a big change in the output.  It's a good feature for a hash function,
and it's a good feature for your purpose, I think.  If you only XOR rows
of bits, then a small change (flip one bit of the input) implies a small
change of the output (the same only bit will be flipped on the output).

Notice that I would preconize to use at least two bytes for the check
sum, and that the input is spread over the 16 bits by shifting each byte
a different position.  If you expected much more than 8 byte, then it
would be good to use a cyclic redundancy check (CRC), that is, don't
lose the carry, but reintroduce it back into the sum.


>> Do you further have any time or code space constraints on the "tiny"
>> microcontroller?
>>
>
> Not really. The tinyest I am aware of is a PIC. Maybe there are
> smaller. The PIC is an 8-bit machine.

Doing 16-bit additions on 8-bit processors is easy, you just write two
ADD instructions instead of one.


>> In the mean time, a simple checksum on 16 bits, where successive bytes
>> are shifted by 0, 2, 4, 6, 1, 3, 5, 7, added to the length of the
>> tested patted (shifted by 8) seems to give good results, given that we
>> already have a 2 or 4 byte magic value preceding.
>
> I think I would use a magic of at least 4 bytes.
>
> Thanks for the code (snipped) but a simple solution is all that's
> needed. I'm just needing to know if a checksum or an xor would be more
> dependable (and why).
>
> The one thing that has come up is to use a 1's complement of the check
> value to guard against the input data being all zeros.

You really need to take care of that only if there's more probability
getting all zeroes.  If your garbage is equiprobable, it wouldn't
matter.


-- 
__Pascal Bourguignon__

Pascal J. Bourguignon <pjb@informatimago.com> wrote:
> CBFalconer <cbfalconer@yahoo.com> writes:
>
> > The chance of an undetected error is extremely low.
> 
> About 1/65536 I'd say, no?

No.  Well, it depends on the distribution of errors.  If they're
uniformly distributed then Pascal is right.  But actual errors aren't
uniformly distributed, and the CCITT CRC polynomial is particularly good
at spotting the kinds of errors that actually occur.

CRCs are linear (they're a surjective homomorphism of rings): if CRC(m)
= CRC(m') then CRC(m XOR m') = 0: this immediately characterizes the
errors that a CRC can detect.  For example, if the CRC polynomial is
chosen to be primitive (as the CCITT one is) then the CRC will detect
/any/ two-bit error unless the bits are exactly a multiple of 65535
positions apart.  Also, any error pattern which fits in 15 bits will be
detected.

-- [mdw]

Tim Rentsch <txr@alumnus.caltech.edu> wrote:

> The idea is to form a byte sum modulo 255, circular shifting by one as
> we go.  Adding one at the end produces a value in the range of 1 to
> 255 (ie, always non-zero).  The initial value of a is chosen rather
> arbitrarily, as is the shift amount;  I don't think the result is
> especially sensitive to either, although I've tried changing only the
> initial value of a.

You're likely to want the rotate amount to be coprime to the register
width, i.e., (since the width is 8) odd.  Otherwise you limit the number
of rotations of the register in a cycle, and in turn you reduce the
kinds of reorderings that you can detect.  For example, if you rotate by
4 bits each time, then you can't tell the difference between ABC and
CBA; if you rotate by 2 or 6 then you can't distinguish ABCDE from
EBCDA.

There'll be some other fallout from 255 being composite, but that
doesn't seem too bad.  I agree that the starting value is arbitrary.

-- [mdw]

Mark Wooding <mdw@distorted.org.uk> writes:

> Tim Rentsch <txr@alumnus.caltech.edu> wrote:
> 
> > The idea is to form a byte sum modulo 255, circular shifting by one as
> > we go.  Adding one at the end produces a value in the range of 1 to
> > 255 (ie, always non-zero).  The initial value of a is chosen rather
> > arbitrarily, as is the shift amount;  I don't think the result is
> > especially sensitive to either, although I've tried changing only the
> > initial value of a.
> 
> You're likely to want the rotate amount to be coprime to the register
> width, i.e., (since the width is 8) odd.  Otherwise you limit the number
> of rotations of the register in a cycle, and in turn you reduce the
> kinds of reorderings that you can detect.  For example, if you rotate by
> 4 bits each time, then you can't tell the difference between ABC and
> CBA; if you rotate by 2 or 6 then you can't distinguish ABCDE from
> EBCDA.

Yes, good observation.  It wasn't immediately obvious to me
that this would be true, but after thinking a little more
it sort of makes sense.  (I still don't have a proof though;
it's my old mathematical training popping up again. :)

> From: James Harris <james.harri...@googlemail.com>
> I am looking for a simple way (usable on a powerful PC or a tiny
> microcontroller) to verify a small amount of data of about eight
> bytes.
> Is it better to compare the data against a checksum or an xor of the
> bytes?

It depends on the types of errors you want to protect against, and
the total number of such errors in worst case. If the number of
errors is unbounded then it's impossible to protect against errors
by any sort of checksum/CRC/whatever.

If this is a *real* (practical) problem, I suggest you test the
electronics by echoing all data back to the source and comparing
what was sent against what echoed back, and collect statistics of
the types of errors that are thereby detected. After you have
enough statistics to generate a good mathematical model of the
types and rates of errors in practie, *then* state clearly those
statistics and ask what type of checksum/whatever would be most
effective in detecting those types/numbers of errors per the stats.

> > I am looking for a simple way (usable on a powerful PC or a tiny
> > microcontroller) to verify a small amount of data of about eight
> > bytes.
> From: Ben Pfaff <b...@cs.stanford.edu>
> For an 8-byte value, just send it twice and compare.

That wouldn't protect against data-dependent errors that are
repeatable, i.e. when you send the data twice then the same error
repeats and the first instance of the bad data matches the second
instance of the bad data. For example, after a string of five or
more "1" bits, the electronics "stick" and the next "0" bit is
received as "1" instead. Or after ten or more consecutive "1" bits,
the electronics overloads and momentarily resets to "0" where
there's supposed to be a "1". Or there's a resonance so that a
strong pattern of "1010101010" tends to extend into whatever data
is supposed to be after it.

It doesn't even protect against repeatable errors that don't depend
on the data at all, such as the third bit always being zero, or the
nineth bit duplicated to overwrite the tenth, etc. Or the
parallel-port wired backwards so each 8-bit byte arrives
bit-reversed. Or a logic error where data is sent big-end-first but
receiver is expecting little-end-first.

Until you know what sorts of errors to expect, you can't say what
algorithm will detect all possible errors or even all likely
errors. One of the most common design flaws is not understanding
the problem to be solved before designing a solution.

What is the missing word in the following semi-analogy?
  A ****, a fly;
  A bird, a meal.

> From: James Harris <james.harri...@googlemail.com>
> This will be a block of data in memory. At the beginning of the
> block will be an unknown number of garbage bytes which need to be
> skipped.

This problem is not well defined until and unless you define
precisely what you mean by "garbage bytes". For example, if the
"garbage bytes" are pseudo-random then the problem is unsolvable
because by pure chance some sub-sequence of the "garbage bytes"
might exactly match the key that indicates the start of good data
and furthermore sucessive "garbage bytes" after that might exactly
match a theoretically-possible block of good data. Contrarywise if
the "garbage bytes" consist of leftover contents after previous
use, not yet erased, then it's very likely that such left-over
memory could look exactly like good data and be mistaken for it.
Even worse, if "garbage bytes" consists of scratch memory used for
a network buffer, into which data from a virus/trojan could be
stored, odds are that your system will surely be taken over by said
malware.

P.S. I like Patricia Shanahan a lot better than I like you.

"Robert Maas, http://tinyurl.com/uh3t" <seeWebInstead@teh.intarweb.org> 
wrote in message news:REM-2009jan19-002@Yahoo.Com...


> What is the missing word in the following semi-analogy?
>  A ****, a fly;
>  A bird, a meal.

What's the answer? 

> > What is the missing word in the following semi-analogy?
> >  A ****, a fly;
> >  A bird, a meal.
> From: "Bartc" <ba...@freeuk.com>
> What's the answer?

bill

Explanation: A bird uses its bill to turn a fly into its meal.
Meta-explanation: Pun on a TV-ad brand-name I'm sick of hearing over and over.