Forums

Crc16 on power failure

Started by maxt...@libero.it January 18, 2007
In article <45AFD9CF.EFBEEB7@yahoo.com>,
 CBFalconer <cbfalconer@yahoo.com> wrote:

> Just a day or so ago I posted something somewhere about fast > CCITCRC16 generation. There are basically two ways, one of which > is highly portable, and involves a table of 256 crc values, > pregenerated. The other uses the DAA instructions on the 8080 or > Z80, and probably many other chips with equivalent instructions. > This involves executing about 20 or so instructions per byte, but > takes very little code space.
Could we get a pointer, or repost? I'm dead curious about how DAA can help in CCIT-CRC16 A relevant message by CBFalconer (but old and without DAA) http://google.us/groups?selm=3F39BFE3.93240B50@yahoo.com&fwc=1 Francois Grieu
Francois Grieu wrote:
> CBFalconer <cbfalconer@yahoo.com> wrote: > >> Just a day or so ago I posted something somewhere about fast >> CCITCRC16 generation. There are basically two ways, one of which >> is highly portable, and involves a table of 256 crc values, >> pregenerated. The other uses the DAA instructions on the 8080 or >> Z80, and probably many other chips with equivalent instructions. >> This involves executing about 20 or so instructions per byte, but >> takes very little code space. > > Could we get a pointer, or repost? I'm dead curious about how DAA > can help in CCIT-CRC16
The source is lost here. I just spent a couple of hours searching some 25 year old listings. The routine wasn't originated by me, but I used it extensively. If you can find my old release of CCITCRC for CP/M the code will be in there. It was also included in some Turbo Pascal units I released way back when. If you do find any of these, please let me know. -- Chuck F (cbfalconer at maineline dot net) Available for consulting/temporary embedded and systems. <http://cbfalconer.home.att.net>
In article <45B0A226.9BDFE5C2@yahoo.com>,
 CBFalconer <cbfalconer@yahoo.com> wrote:

> If you can find my old release of CCITCRC > for CP/M the code will be in there. It was also included in some > Turbo Pascal units I released way back when. If you do find any of > these, please let me know.
The best I can find is what appears to be your object code http://www.e-tech.net/~pbetti/mirrors/www.retroarchive.org/cpm/cdrom/LAMBDA/SOUNDPOT/A/CCITCRC.LBR and some stuff apparently not related to your software nor using DAA http://www.df.lth.se/~pi/compis/files/ftp.mayn.de/pub/cpm/archive/filutl/citcrc11/ccitcrc.asm.txt http://www.df.lth.se/~pi/compis/files/ftp.mayn.de/pub/cpm/archive/filutl/citcrc11/ccitcrc.z80.txt Francois Grieu
On Thu, 18 Jan 2007 17:54:38 +0100, "Ignacio G.T."
<igtorque.remove@evomer.yahoo.es> wrote:
>I'd suggest using a simple checksum (perhaps complemented), instead of a >CRC. Usually, a checksum is faster to calculate than a CRC by software.
True, they are faster, but they are not nearly as good at detecting errors. 8-bit checksum, XOR-ing, or whatever can allow for a 1/256 chance of not detecting an error. A 16-bit checksum is better than an 8-bit, but not nearly as good at detecting single bit errors as a CRC-16. Jack Crenshaw states that a 16-bit CRC will detect: 100% of all single bit errors, 2-bit errors, odd numbers of bit errors, and all bursts less than 17 bits. 99.9969% of all bursts of 17 bits 99.9985% of all bursts more than 17 bits (same as a 16-bit checksum) So definitely use a 16-bit CRC. And definitely use the table lookup method of computation, it is MUCH faster.
>CRCs are better for detecting bursts of noise in communication lines. >Use the machine's word length for the checksum. Depending on the micro >and compiler, it could be a good idea to use assembler for that function.
You might be able to do as well in C as you can in assembly language. My C compiler for the MSP430 generates code that is just about as fast as hand-crafted assembly language code.
Mr. C wrote:
> On Thu, 18 Jan 2007 17:54:38 +0100, "Ignacio G.T." > <igtorque.remove@evomer.yahoo.es> wrote: > >I'd suggest using a simple checksum (perhaps complemented), instead of a > >CRC. Usually, a checksum is faster to calculate than a CRC by software. > > True, they are faster, but they are not nearly as good at detecting > errors. 8-bit checksum, XOR-ing, or whatever can allow for a 1/256 > chance of not detecting an error. A 16-bit checksum is better than an > 8-bit, but not nearly as good at detecting single bit errors as a > CRC-16. Jack Crenshaw states that a 16-bit CRC will detect:
It's clear CRC are much better at burst error detection. But since both methods contain the same number of possible check digits they have the same probability of any given random sequence matching a given check (1 in 64K for a 16bit check) it follows that a simple check should be better in non-burst conditions. It only remains to determine what kind of errors your memory system can give you ;) As well as a CRC and check sum you can also consider a Fletcher checksum. Also for storing backup values of operating parameters coonsider running an EEC on each parameter instead of a block check. National had an app note on a straightforward one I can look up. The EEC has the advantage of being per item and so likely faster if you only change an item or two, it will take up more room though. You could combine it with a simple checksum over a block to give a dual layer check. Robert
Mr. C <fakeemail@hotmail.com> wrote:

>On Thu, 18 Jan 2007 17:54:38 +0100, "Ignacio G.T." ><igtorque.remove@evomer.yahoo.es> wrote: >>I'd suggest using a simple checksum (perhaps complemented), instead of a >>CRC. Usually, a checksum is faster to calculate than a CRC by software. > >True, they are faster, but they are not nearly as good at detecting >errors. 8-bit checksum, XOR-ing, or whatever can allow for a 1/256 >chance of not detecting an error. A 16-bit checksum is better than an >8-bit, but not nearly as good at detecting single bit errors as a >CRC-16.
How does even the crudest of checksum schemes fail to detect a single bit error? 1 bit of parity will detect 100% of single bit errors.
>Jack Crenshaw states that a 16-bit CRC will detect: > >100% of all single bit errors, 2-bit errors, odd numbers of bit >errors, and all bursts less than 17 bits. >99.9969% of all bursts of 17 bits >99.9985% of all bursts more than 17 bits (same as a 16-bit checksum)
In the OP's application checking the integrity of 16kB of battery backed RAM why would one particularly expect single bit errors or bursts of errors? What is the concept of a burst when you can arbitrarily choose how to arrange this large array of bits into a stream? What I would particularly expect is complete corruption because the battery failed or was disconnected or the system crashed and never generated a checksum. I would consider the possibility of partial corruption perhaps from a failing battery to be pretty slim. IMO the OP would be better off using a larger simpler checksum, he should also guard against possible complete corruption states (all 0's, all 1', alternate 0/0xFF's ?) giving a valid checksum. He should probably include and check a 'magic' number in the data area and perhaps link this to firmware version as a firmware upgrade may render the RAM image corrupt despite a valid checksum. He should probably invalidate the checksum after use to reduce the possibility that partial non-random data changes followed by a crash leave the old checksum valid. --
Francois Grieu wrote:
> CBFalconer <cbfalconer@yahoo.com> wrote: > >> If you can find my old release of CCITCRC >> for CP/M the code will be in there. It was also included in some >> Turbo Pascal units I released way back when. If you do find any of >> these, please let me know. > > The best I can find is what appears to be your object code > http://www.e-tech.net/~pbetti/mirrors/www.retroarchive.org/cpm/cdrom/LAMBDA/SOUNDPOT/A/CCITCRC.LBR
That appears to be the object code and documentation in crunched and squeezed format. With some effort I can extract and disassemble parts of it, but not now. Why did people strip the source from the libraries! -- "A man who is right every time is not likely to do very much." -- Francis Crick, co-discover of DNA "There is nothing more amazing than stupidity in action." -- Thomas Matthews <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
maxthebaz@libero.it wrote:

> Our machines have this requirement: if power failure occurs, many > important variables are to be resumed from where they were interrupted > after the machine is restarted (power on in this case). In other words, > the basic idea is to keep a snapshot of the state machine before it is > interrupted. > The board is provided with: > - a 32-bit H8S/2633 Hitachi microprocessor; > - a battery-backed memory (BBM), where these variables are stored; BBM > area involved is about 16 Kbytes (the whole BBM has a 128KB capability) > - 2 big capacitors; if a blackout occurs, they guarantee a 400 msec > (Tsave) extra power supply time. > When power supply is going to fall down, a function is invoked by power > failure NMI. This function, within Tsave time, has to perform the > following main operations: > - it calculates CRC16 checksum for the BBM variable area (for our 16KB, > this requires a long time: 90 msec!). > - it saves the CRC16 checksum in BBM (of course, in a different BBM > address from the previous variable area). > Then, when machine is re-started, a new checksum of the interested BBM > area is performed: the result is compared with the previous stored one. > If they differ, a BBM corruption is assumed (error detection). > > Now I am seeking a better solution: the target is to reduce the 2 big > capacitors, i.e. to reduce Tsave time. The reason is to save space (and > money) by reducing them. I'm looking for a way to anticipate CRC16 > calculation in a safe and fast way, before power failure. > One solution could be a CRC16 computation invoked at every time a BBM > variable is changed, but this operation needs 90 msec (as I wrote > before), while main loop now is about 10 msec. That's why this solution > is not applicable at all.
You could divide your total variable area in a number of shorter blocks, say 512 bytes, or 1KB each, and perform a CRC16 only on the block where a variable has been updated. Of course, this won't work if you frequently change many variables throughout the entire memory. It does have an added advantage of better protection against errors, and in the case a CRC error is detected in a block you may still be able to use the other blocks.
CBFalconer wrote:
> Francois Grieu wrote: >> CBFalconer <cbfalconer@yahoo.com> wrote: >> >>> If you can find my old release of CCITCRC >>> for CP/M the code will be in there. It was also included in some >>> Turbo Pascal units I released way back when. If you do find any of >>> these, please let me know. >> The best I can find is what appears to be your object code >> http://www.e-tech.net/~pbetti/mirrors/www.retroarchive.org/cpm/cdrom/LAMBDA/SOUNDPOT/A/CCITCRC.LBR > > That appears to be the object code and documentation in crunched > and squeezed format. With some effort I can extract and > disassemble parts of it, but not now. Why did people strip the > source from the libraries! >
I've unpacked it to CCITCRC.CZM and CCITCRC.DZC (thanks, Z80EMU :) If anyone can tell me what the correct unpacker is for ?Z? files, I'll take it the rest of the way, & post the results. (I'm sure the relevant decompressor is on my Walnut Creek CD: I just forget which it is). I may even try running a Z80 disassembler on the .COM
David R Brooks wrote:
> CBFalconer wrote: >
... snip ...
>> >> That appears to be the object code and documentation in crunched >> and squeezed format. With some effort I can extract and >> disassemble parts of it, but not now. Why did people strip the >> source from the libraries! > > I've unpacked it to CCITCRC.CZM and CCITCRC.DZC (thanks, Z80EMU :) > If anyone can tell me what the correct unpacker is for ?Z? files, I'll > take it the rest of the way, & post the results. (I'm sure the relevant > decompressor is on my Walnut Creek CD: I just forget which it is). > > I may even try running a Z80 disassembler on the .COM
If you are running a CPeMulator, you can get LT31 from my page. It will unpack them all. <http://cbfalconer.home.att.net/download/cpm/> If you disassemble just search the results for the DAA instruction. I think it occurs twice in the subroutine, and nowhere else. -- <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt> "A man who is right every time is not likely to do very much." -- Francis Crick, co-discover of DNA "There is nothing more amazing than stupidity in action." -- Thomas Matthews