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. Note: because of our application, I can't consider solutions like saving every second, i.e. loosing "only" last second changes. Thank you very much.
Crc16 on power failure
Started by ●January 18, 2007
Reply by ●January 18, 20072007-01-18
"maxthebaz@libero.it" <maxthebaz@libero.it> writes:> 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.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!
Reply by ●January 18, 20072007-01-18
Ben Pfaff ha scritto:> "maxthebaz@libero.it" <maxthebaz@libero.it> writes: > > > 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. > > 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!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
Reply by ●January 18, 20072007-01-18
maxthebaz@libero.it escribi�:> 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. > > Note: because of our application, I can't consider solutions like > saving every second, i.e. loosing "only" last second changes. >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...
Reply by ●January 18, 20072007-01-18
> - it calculates CRC16 checksum for the BBM variable area (for our 16KB, > this requires a long time: 90 msec!).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 http://www.tgi-sci.com ------------------------------------------------------ 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. > > Note: because of our application, I can't consider solutions like > saving every second, i.e. loosing "only" last second changes. > > Thank you very much.
Reply by ●January 18, 20072007-01-18
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. <maxthebaz@libero.it> wrote in message news:1169136383.738070.263090@11g2000cwr.googlegroups.com...> 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. > > Note: because of our application, I can't consider solutions like > saving every second, i.e. loosing "only" last second changes. > > Thank you very much. >
Reply by ●January 18, 20072007-01-18
In article <1169136383.738070.263090@11g2000cwr.googlegroups.com>, "maxthebaz@libero.it" <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!).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.> - 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. > > Note: because of our application, I can't consider solutions like > saving every second, i.e. loosing "only" last second changes.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<vOld)+vOld, vSum += (tu16)(vSum<vNew); Caveat: vSum will never be 0, which is replaced by 0xFFFF. Thus the initial value of vSum when computing vSum at initialization and reset must not be 0, else a wrong failure may be detected when the whole memory is zero. #define kBBMSize 16000 // must be even tu16 vSum,vTmp,vIdx,BBM[kBBMSize/2]; for (vSum = 0xFFFF, vIdx=0; vIdx<kBBMSize/2;) vSum += vNew = BBM[vIdx++], vSum += (tu16)(vSum<vNew); Note: the "addition with rollower carry" technique would make this asymptotically as fast as addition mod 0x10000 on most CPUs, but that can't be expressed in C. The only drawback of aritmetic modulo 0xFFFF is that the address of the updated data is not taken into account. A 16-bit CRC fixes this, and still allows fast update, using something in the tune of vSum ^= AFunction(((ArrayByteSize/2-vIdx)*16L)%65535,vOld^vNew), where AFunction is a simple function, not referencing BBM or it's size, with execution time mostly independent of inputs. I have no working code for AFunction and no time right now to write it. Basically, you want to quickly reduce second-input, shifted by first-input bits, by the constant reduction polynomial, assumed to be a degree-16 primitive polynomial. I beleive ((ArrayByteSize/2-vIdx)*16L)%65535 is correct for CRC computation by increasing address and any canonical CRC, that is with the proerty that appending the CRC after the message gives protection against any error of 16 consecutive bits, including at the frontier between message and CRC. Francois Grieu /* fcs_lib.h public domain This pure C library implements calculation and verification of the 16 bits Frame Check Sequence (FCS) specified in CCITT X25 section 2.2.7, and/or V42 sec.8.1.1.6.1, and/or ISO/IEC 14443-3:2001 for type B, and/or CSC communication; also designated 16-bit CRC CCITT. Examples: the frame 80 02 01 01 00 50 3F is valid (50 3F is the FCS/CRC) the frame 80 04 01 18 01 00 00 20 6D is valid (20 6D is the FCS/CRC) the frame 01 03 01 18 00 00 84 B1 is valid (84 B1 is the FCS/CRC) 2006-12-14 FGR added examples simplified comments more efficient computation formula This code works for data occuring in whole 8 bit bytes, and uses the convention that physical transmission of data occurs in increasing byte adresses. FCD/CRC computation occurs with least significant bit of each byte processed first. This also match physical serial transmission in many contexts (CITT X25, V42, ISO/IEC 14443-3:2001 type B, and serial asynchronous communication with a CSC) */ #ifndef FCS_LIB_INCLUDED /* avoid multiple includes */ #define FCS_LIB_INCLUDED /* Function : Compute the FCS of a frame, and add it at the end of the frame. Input : ioFrame = pointer to the start of a frame iLen = length of the frame in bytes (without the FCS) Output : Adds the two bytes of the FCS at the end of the frame buffer. Remark : The frame buffer must be at least len+2 bytes long, and IS MODIFIED by the addition of the two bytes of the FCS. */ void add_FCS(unsigned char *ioFrame, int iLen); /* Function : Check the FCS of a frame. Input : iFrame = pointer to the start of a frame iLen = length of the frame in bytes (including the two FCS bytes) Output : (none) Return : 1 if the FCS is correct 0 if the FCS is NOT correct Remark : The frame buffer must be at least iLen bytes long, and is not modified. */ int chk_FCS(unsigned char *iFrame, int iLen); #endif /* fcs_lib.c public domain (see the interface file fcl_lib.h for info and modification history) */ #include "fcs_lib.h" /* define a LOW8 macro that keeps the low 8 bits */ #include <limits.h> #if UCHAR_MAX==255 #define LOW8(x) ((unsigned char)(x)) /* normal, fast variant */ #else #define LOW8(x) ((unsigned char)((unsigned char)(x)&0xFF)) /* portable variant */ #endif /* Function : Compute the FCS of a frame, and add it at the end of the frame. Input : ioFrame = pointer to the start of a frame iLen = length of the frame in bytes (without the FCS) Output : Adds the two bytes of the FCS at the end of the frame buffer. Remark : The frame buffer must be at least len+2 bytes long, and IS MODIFIED by the addition of the two bytes of the FCS. */ void add_FCS(unsigned char *ioFrame, int iLen) { unsigned short vFCS; vFCS = 0xFFFF; /* init FCS to all ones */ /* process each byte in ioFrame */ while (--iLen>=0) { vFCS ^= LOW8(*ioFrame++); vFCS ^= LOW8(vFCS<<4); vFCS = (unsigned short)(vFCS>>8)^ (unsigned short)((unsigned short)LOW8(vFCS)<<8)^ (unsigned short)((unsigned short)LOW8(vFCS)<<3)^ (unsigned short)(LOW8(vFCS)>>4); } vFCS ^= 0xFFFF; /* finally invert vFCS */ /* add vFCS at the end of ioFrame */ *ioFrame++ = vFCS&0xFF; *ioFrame++ = vFCS>>8; } /* Function : Check the FCS of a frame. Input : iFrame = pointer to the start of a frame iLen = length of the frame in bytes (including the two FCS bytes) Output : (none) Return : 1 if the FCS is correct 0 if the FCS is NOT correct Remark : The frame buffer must be at least iLen bytes long, and is not modified. */ int chk_FCS(unsigned char *iFrame, int iLen) { unsigned short vFCS; vFCS = 0xFFFF; /* init FCS to all ones */ /* process each byte of iFrame, including the FCS */ while (--iLen>=0) { vFCS ^= LOW8(*iFrame++); vFCS ^= LOW8(vFCS<<4); vFCS = (unsigned short)(vFCS>>8)^ (unsigned short)((unsigned short)LOW8(vFCS)<<8)^ (unsigned short)((unsigned short)LOW8(vFCS)<<3)^ (unsigned short)(LOW8(vFCS)>>4); } return (vFCS==0xF0B8); /* true if the FCS is correct */ } /* end of fcs_lib.c */
Reply by ●January 18, 20072007-01-18
<maxthebaz@libero.it> wrote in message news:1169136383.738070.263090@11g2000cwr.googlegroups.com...> 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: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)
Reply by ●January 18, 20072007-01-18
maxthebaz@libero.it schrieb:> 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.I assume that some higher-level transaction/rollback system is implemented as well in your data structure?> 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!).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?> - 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.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<8; ++i) if (changes & (1<<i)) crc ^= pat<<i; for (int i=7; i>=0; --i) if (crc & (1<<(16+i))) crc ^= CRC16POLY << (i+1); // poor man's critical section, prevent optimizer from changing anything here global_index = index; global_NEW = NEW; global_dirty = true; global_CRC = crc; BBMbyte[index] = NEW; BBM_CRC = crc; global_dirty = false; } void NMIfunc() { if (global_dirty) { // NMI during critical section of SetBBMByte if (global_CRC != BBM_CRC) { // NMI after "global_CRC = crc", before "BBM_CRC = crc" BBMbyte[global_index] = global_NEW; BBM_CRC = global_crc; global_dirty = false; } //else SetBBMbyte was totally ignored or completed } // additional transaction protection code might be put here halt_cpu(); // must not return to running process!! } You can adapt this to handle words instead of bytes. However, with the variable names as above, you must have sizeof(crc) >= sizeof(NEW) +16/sizeof(char) where the 16 is the 16 from CRC16. SetBBMByte is much slower than a simple memory access, but you may halt the cpu almost immediately upon NMI.> > Note: because of our application, I can't consider solutions like > 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. ;)> Thank you very much.
Reply by ●January 18, 20072007-01-18
"maxthebaz@libero.it" wrote:> Ben Pfaff ha scritto: >> "maxthebaz@libero.it" <maxthebaz@libero.it> writes: >> >>> 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. >> >> 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. > > 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.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.
