Crc16 on power failure

You didn't state a question about the C programming language anywhere, so I'm going to suggest that further followups should go only to comp.arch.embedded.

--
Here's a tip: null pointers don't have to be *dull* pointers!

Ben Pfaff ha scritto:

Thank you, you're right (and this is my first post...). I used also this gruop because maybe a solution could be

- a faster CRC16 C implementation

- or, instead of CRC16, the use of a faster checksum C algorithm.

Anyhow, thank you again for your suggestion. Max

snipped-for-privacy@libero.it escribió:

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. 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 could also group the variables and use a different checksum for each group. The smaller the group, the faster the computation of the checksum (and more room needed for the checksums).

Ultimately, you could just duplicate each variable. This is the same as using checksums for groups of only one variable...

I don't know the CPU you are using, but apr. 10 uS per 16 bits sounds like there may be room for improvement just of the code (using that now widely popular algorithm which includes table lookup etc., you can find it in the one of the PPP related RFC-s, I _think_ it was described in sufficient detail either in rfc1661 or in rfc1662. (OK, just checked, it really is inside RFC1662, not bad for over 2 years not having to deal with it :-). How fast is the CPU you are using (I mean clock frequency)?

Another possibility might be to split the 16K in several pieces and calculate the CRC only for the piece which has been modified, if the nature of the data and the application would allow that.

Dimiter

------------------------------------------------------ Dimiter Popoff Transgalactic Instruments

------------------------------------------------------

snipped-for-privacy@libero.it wrote:

You need to use a better implementation of the CRC16. Even performing the calculation one bit at a time you could probably do better than 90ms.

Unless access to the BBM is slow (e.g. SPI), that 5.6us per byte figure would be reasonable for a 5 MIPS 8-bit CPU. Are you using at least a byte-by-byte algorithm, using a table of 256

16-bit values? Or maybe better, depending on the CPU and/or memory size constraints, something like the working code pasted at the end of this post? It EXACLTY implements the 16-bit CRC in CCITT X25, V42, and ISO/IEC 14443-3 type B, is reasonably fast, and use no table.

A most efficient solution would be to replace the CRC16 with a 16-bit XOR checksum; then it is trivial to update the checksum (when updating a 16-bit word, XOR the CRC with the XOR of that word before and after the update). But a 16-bit XOR checksum is not nearly as good as a CRC in term of integrity check.

You could use addition mod 0x10000, but it still gives poor protection against failures that affect the high bit(s) only.

You could also use addition modulo 0xFFFF which provides good real-life protection, and where update is still fast; in C, the update of vSum could be:

typedef unsigned short tu16; // assumed to be 16 bits tu16 vSum,vOld,vNew; vSum += vNew -= (tu16)(vNew

Snip.

Please redirect this question to:

comp.arch.embedded

--
David T. Ashley              (dta@e3ft.com)
http://www.e3ft.com          (Consulting Home Page)
http://www.dtashley.com      (Personal Home Page)
http://gpl.e3ft.com          (GPL Publications and Projects)

snipped-for-privacy@libero.it schrieb:

I assume that some higher-level transaction/rollback system is implemented as well in your data structure?

There are specialized CRC chips. Might this help? I assume that BBM is somewhat slow in access. How much of the 90ms is pure reading time?

CRC should be possible incremental. If you change Byte[k] from OLD to NEW, the CRC should change by TABLE8[k,OLD] ^ TABLE8[k,NEW] This requires 256*n words of precalculated tables for n bytes of memory, so here it's 8MB, which might be too much.

Here's a slower but less memory demanding idea of mine (n words, i.e.

32KB):

// the battery-backed-memory. // 1) byte array for the main variables byte BBMbyte[BBM_ByteCount]; // 2) the saved checksum uint16 BBM_CRC;

// precalculated table of influence of lowest bit at index const uint16 TABLE1[BBM_ByteCount] = { .... };

// for protection against NMI during SetBBMByte int global_index; uint16 global_CRC; byte global_NEW; bool global_dirty;

void SetBBMByte(int index, byte NEW) { byte OLD = BBMbyte[index]; if (OLD==NEW) return;

unsigned int crc = global_CRC;

int pat = TABLE1[index]; int changes = NEW ^ OLD; for (int i=0; i saving every second, i.e. loosing "only" last second changes.

A) What is the cost of loosing last second changes? B) What is the cost of the capacitors? It sounds like A is much bigger than B, hence keep the capacitors. ;)

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.

--
 Sending unsolicited commercial e-mail to
     cbfalconer at maineline dot net
 incurs a fee of 500 USD per message, and
 acknowledges the legality of this contract.

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)

snipped-for-privacy@yahoo.com&fwc=1

Francois Grieu

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.

The best I can find is what appears to be your object code

and some stuff apparently not related to your software nor using DAA

Francois Grieu

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.

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.

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

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.

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.

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

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.

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

... snip ...

If you are running a CPeMulator, you can get LT31 from my page. It will unpack them all.

If you disassemble just search the results for the DAA instruction. I think it occurs twice in the subroutine, and nowhere else.

--
 

 "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