A bit resistant to disruption
in [General Programming]
|
Prev: CFP: SAS'2010 - 17th International Static Analysis Symposium, Perpignan, France
Next: Get 101 Question on C, C++, C++ under Windows, MFC, DLL, COM/DOM
From: Mark Borgerson on 14 Feb 2010 00:28 In article <4b7740d3$0$65832$892e0abb(a)auth.newsreader.octanews.com>, ThadSmith(a)acm.org says... > Thad Smith wrote: > > Francois Grieu wrote: > >> /* > >> Disclaimer: This is a hard problem, only minimally disguised into > >> something on-topic for comp.lang.c > > > > comp.programming and comp.arch.embedded added to the list. > > > >> You are programming a C99 conforming freestanding implementation. > >> Disruption (reset or power off/on cycle) can occur at *ANY* time > >> without advance warning, and stops whatever operation is underway. The > >> program is re-executed from main() after a disruption. > >> > >> The objective is to implement a single bit resistant to disruption, > >> accessed using two procedures to be written: > >> int bRead(void); // Return 0 or 1 according to bit state. > >> void bToggle(void); // Change the state of the bit. > >> > >> These two properties shall be met: > >> a) The bit is stable in the absence of Toggle. That is, the result > >> given by any two undisrupted bRead() is the same unless bToggle() was > >> invoked in-between. > >> b) The bit is changed by Toggle. That is, the result given by any two > >> undisrupted bRead() is different if bToggle() was invoked exactly once > >> in-between and no disruption occurred during that execution of bToggle(). > > .... > >> An EEPROM cell can be left neither erased nor programmed by a disrupted > >> eErase unless that cell was already erased, or by a disrupted eProgram. > >> For a cell in such halfway state, eRead returns a value specified only > >> to be 0 or 1. That otherwise unspecified value may in particular change > >> after disruption (due e.g. to uncontrollable random noise and/or > >> temperature and/or voltage drift in the hardware used by eRead), even > >> though the sate of cells is unchanged by disruption or/and eRead. > >> > >> Note: if a cell is not erased (left in a halfway state or programmed), > >> an eProgram of that cell is prohibited. A workaround is to use the > > > > First, this is an uninteresting problem because if a power failure > > occurs during a toggle attempt, the restored state gives no information > > at all. > > I'm taking another stab at the problem, based on more analysis and an > understanding of possible use. Thanks to Daniel Giaimo for finding a problem in > the earlier proposal. > > Let's assume the variable has three state categories: s1, s2, and t. s1 and s2 > are stable states (will not change spontaneously). Other values are transition > values. If the variable is read in a state t, the variable is then changed to > s1 or s2. > > This can be used to perform a consistent database state update: > Assume initially database copy A is consistent and dbstate=s1 (database A is > valid). To update, make an updated copy B. At this point both A and B are > consistent. Set dbstate=s2 (database B is valid). Move B to A. Set dbstate=s1. > > If power is lost while dbstate is being changed, both database copies are valid, > so restoring the state to either stable state results in a consistent database. > We just need to make sure that s1 and s2 are always stable when an > modification is in progress on copy A or B. > > In the following list of sequential states, each of the four bits are > independently erasable and writable (normally implemented in separate bytes). > > Bit > dbstate dcba Stable bits > s1 0001 ca > t1a 0011 da > t1b 0111 db > t1c 0110 db > s2 0010 ba > t2a 1010 cb > t2b 1011 dc > t2c 1001 ca > (s1) 0001 ca > > To go from state s1 to s2 or s2 to s1, we first re-erase the last bit erased, > then sequentially write the variable to the following transition and stable > states, changing a single bit at a time. > > When reading dbstate, if value is s1 or s2, return the value. > If value is txa or txb, erase and rewrite the last bit set, then precede to the > next stable state. If value is txc, re-erase the last bit erased, then precede > to the next stable state. > > If power fails when in a transition state, a reading of the state with the above > rules will restore dbstate to a stable value. Multiple interrupts during a > restoration can cause the state values to go from t1b to t1a to s1, but it > doesn't revert any further (similar for t2b to t2a to s2). > > Assume power fails during the t1c-s2 or t2c-s1 transition such that the powerup > state reads s2 or s1 with a partially erased bit (d for s1, c for s2). If the > partially erased bit is read as zero, dbstate will be considered stable, even > though there is an unstable bit. The state may revert to the previous > transition state, which, when read, will be advanced to the same stable state. > Assume d is a weak zero in s1 when dbstate starts to advance. The first > operation on advance is to re-erase d, eliminating the weak state, then start > transition to s2. > > Wouldn't all this be simplified if you simply used a non-volatile memory with a single-cycle read and write? MRAM and FRAM come to mind. IIRC, they have mechanisms to prevent false writes at power-down and don't suffer from any awkward in-between states. Mark Borgerson
From: Thad Smith on 14 Feb 2010 01:55 Mark Borgerson wrote: > In article <4b7740d3$0$65832$892e0abb(a)auth.newsreader.octanews.com>, > ThadSmith(a)acm.org says... >> [Proposal for robust use of EEPROM through power outages] > Wouldn't all this be simplified if you simply used a non-volatile > memory with a single-cycle read and write? MRAM and FRAM come to > mind. IIRC, they have mechanisms to prevent false writes at > power-down and don't suffer from any awkward in-between states. It should be, assuming that there is brownout detection. The OP is apparently working with Smart Card hardware using EEPROM. Sometimes the hardware is dictated. -- Thad
From: Francois Grieu on 15 Feb 2010 15:54 Thad Smith wrote about the following problem [I added more notes, since the problem has been partially misunderstood by some] Disclaimer: This is a hard problem, only minimally disguised into something on-topic for comp.lang.c You are programming a C99 conforming freestanding implementation (e.g. a microprocessor device programmed in C, but we can't use <stdio.h> or otherwise store data on disk). Disruption (reset or power off/on cycle) can occur at *ANY* time without advance warning, and stops whatever operation is underway. The program is re-executed from main() after a disruption. The objective is to implement a single bit resistant to disruption, accessed using two procedures to be written: int bRead(void); // Return 0 or 1 according to bit state void bToggle(void); // Change the state of the bit and such that these two properties are met: a) The bit is stable in the absence of Toggle. That is, the result given by any two undisrupted bRead() is the same unless bToggle() was invoked in-between. b) The bit is changed by Toggle. That is, the result given by any two undisrupted bRead() is different if bToggle() was invoked exactly once in-between and no disruption occurred during that execution of bToggle(). Note: The bit is therefore unspecified from the invocation of bToggle() until the end of this bToggle() if it is undisrupted, or otherwise until the end of the next undisrupted bRead(). This is the only definition of "bit resistant to disruption" worth of interest. The only way to store information across disruptions is using a number of independent physical EEPROM cells, designated by index j. Access to the EEPROM cells is by the following three functions. The properties stated for theses functions apply for any fixed non-negative integer j less than the number of cells, and "for that cell" is implied everywhere. // Read a designated EEPROM cell; always returns 0 or 1. extern int eRead(int j); // Erase a designated EEPROM cell. // After undisrupted eErase, the cell is "erased" and eRead returns // 0 until eProgram is invoked (regardless of invocation of eErase // and disruptions) extern void eErase(int j); // Program a designated *ERASED* EEPROM cell. // After undisrupted eProgram, eRead returns 1 until eErase is invoked // (regardless of disruptions) // Programming a cell that is not "erased" cause undefined behavior. extern void eProgram(int j); An EEPROM cell can be left neither erased nor programmed by a disrupted eErase unless that cell was already erased, or by a disrupted eProgram. For a cell in such halfway state, eRead returns a value specified only to be 0 or 1. That otherwise unspecified value may in particular change after disruption (due e.g. to uncontrollable random noise and/or temperature and/or voltage drift in the hardware used by eRead), even though the sate of cells is unchanged by disruption or/and eRead. Note: if a cell is not erased (left in a halfway state or programmed), an eProgram of that cell is prohibited. A workaround is to use the following rather than eProgram(): void mySafeProgram(int j) { eErase(j); eProgram(j); } Before the first run, all EEPROM cells have been erased. eRead, eErase, and eProgram terminate unless a disruption occurs, assuming constraints on j and eProgram are met. bRead and bToggle must similarly terminate unless a disruption occurs. Can it be done? If yes, what is the minimum number of cells needed? Give a proof. Depending on the answer, try to minimize the expected failure rate or maximize the expected LED flash rate in the following use case: */ #define NCELLS 10 // number of cells extern void sLed(int x); // 0: LED on green then off // 1: LED on red then off. extern int eRead(int j); // Read a cell. extern void eErase(int j); // Erase a cell to 0. extern void eProgram(int j); // Program an erased cell to 1. int bRead(void); // Return 0 or 1 according to bit state. void bToggle(void); // Change the state of the bit. // Declarations, and the code for bRead/bToggle, go here int main(void) { int vState; vState = bRead(); while(1) { sLed(vState); bToggle(); vState = !vState; } return 0; } /* Assume eProgram, eErase, sLed each last 1 second; everything else is comparatively instant; a disruption occurs with odds p each second; unspecified eRead values are assigned at random with mean 0.5; the LED is off following disruption; a failure is a violation of the requirement: if a disruption occurs with the LED on in some color, then the first time the program lights a LED it must be with that color. Note: any bRead/bToggle conforming to a) b) works in this test program, and any bRead/bToggle making this test program working can be changed into bRead/bToggle2 conforming to a) b), by defining bToggle2 as: void bToggle2(void) { (void)bRead(); bToggle(); } Notice that disruption without warning is the standard under which most real-life hardware actually operates (with the exception of systems with physical protection against adversarial reset and a power reserve with means to sense imminent power loss), even though this is often left out of the specification. And that real disruption-surviving media (EEPROM, Flash, CDRW, though not battery-backed SRAM) do have the limitation that read after interrupted change of state sometime gives an unstable result. While "programming a cell that is not erased cause undefined behavior" is not the rule, it can exist due to a poorly specified API, an overcautious hardware specification, or in some cases due to tue hardware limitations. The problem is derived from actual requirements in a Smart Card. This is neither homework, nor an attempt to gather brainpower for free: I'm the author of the problem and have conclusively determined the feasibility, with a concise proof. A similar problem "A bit in bottles" is in rec.puzzles, some of the replies contain answers, and I committed mine. http://groups.google.com/group/rec.puzzles/browse_thread/thread/ab892b3cf88af0de Francois Grieu > First, this is an uninteresting problem because if a power failure > occurs during a toggle attempt, the restored state gives no > information at all. Is the prefix "UN" intended? Thad Smith shows continued INterest, and I'm grateful to him for that. > I'm taking another stab at the problem, based on more analysis and > an understanding of possible use. Thanks to Daniel Giaimo for > finding a problem in the earlier proposal. > > Let's assume the variable has three state categories: s1, s2, and t. > s1 and s2 are stable states (will not change spontaneously). > Other values are transition values. If the variable is read in a > state t, the variable is then changed to s1 or s2. > > This can be used to perform a consistent database state update: > Assume initially database copy A is consistent and dbstate=s1 > (database A is valid). To update, make an updated copy B. At > this point both A and B are consistent. Set dbstate=s2 (database B > is valid). Move B to A. Set dbstate=s1. > > If power is lost while dbstate is being changed, both database > copies are valid, so restoring the state to either stable state > results in a consistent database. > > We just need to make sure that s1 and s2 are always stable when > an modification is in progress on copy A or B. > > In the following list of sequential states, each of the four bits > are independently erasable and writable (normally implemented in > separate bytes). > > Bit > dbstate dcba Stable bits > s1 0001 ca > t1a 0011 da > t1b 0111 db > t1c 0110 db > s2 0010 ba > t2a 1010 cb > t2b 1011 dc > t2c 1001 ca > (s1) 0001 ca > > To go from state s1 to s2 or s2 to s1, we first re-erase the last > bit erased, then sequentially write the variable to the following > transition and stable states, changing a single bit at a time. > > When reading dbstate, if value is s1 or s2, return the value. > If value is txa or txb, erase and rewrite the last bit set, > pr*o*cede to the next stable state. If value is txc, re-erase the > last bit erased, then procede to the next stable state. Going from t2b to t2c, disruption occurs while we erase "b". On restart, state is "10?1". We read it as "1011" that is t2b. While we "erase the last bit set", that is "a", disruption occurs. On restart, state is "10??". We read it as "1010" that is t2a. [notice the "Stable bits: cb" condition is not met] While we "erase the last bit set", that is "d", disruption occurs. On restart, state is "?0??" [or maybe "?0?0" is we have been prudent and erased "a" right after seeing it as 0]. We read that as "0010" and assume state s2. Before we make any change/call to bToggle(), disruption occurs and we read the same state as "0001" and assume state s1, this is a violation of requirement a. [is we have erased "a" we will read "0000" and I guess we will next move to s1 and be equally busted] > If power fails when in a transition state, a reading of the state > with the above rules will restore dbstate to a stable value. Not so, see above. > Multiple interrupts during a restoration can cause the state values > to go from t1b to t1a to s1, but it doesn't revert any further Right, unless I err. > (similar for t2b to t2a to s2). I don't think so.. [snip] I plan to post my answer by the end of the week. Francois Grieu
From: Moi on 13 Mar 2010 12:04 On Fri, 12 Feb 2010 21:49:21 -0700, Thad Smith wrote: > Francois Grieu wrote: >> /* >> Disclaimer: This is a hard problem, only minimally disguised into >> something on-topic for comp.lang.c > > comp.programming and comp.arch.embedded added to the list. > >> You are programming a C99 conforming freestanding implementation. >> Disruption (reset or power off/on cycle) can occur at *ANY* time >> without advance warning, and stops whatever operation is underway. The >> program is re-executed from main() after a disruption. >> >> The objective is to implement a single bit resistant to disruption, >> accessed using two procedures to be written: >> int bRead(void); // Return 0 or 1 according to bit state. void >> bToggle(void); // Change the state of the bit. >> >> These two properties shall be met: >> a) The bit is stable in the absence of Toggle. That is, the result >> given by any two undisrupted bRead() is the same unless bToggle() was >> invoked in-between. >> b) The bit is changed by Toggle. That is, the result given by any two >> undisrupted bRead() is different if bToggle() was invoked exactly once >> in-between and no disruption occurred during that execution of >> bToggle(). > ... > > An EEPROM cell can be left neither erased nor programmed by a > > disrupted eErase unless that cell was already erased, or by a > > disrupted eProgram. For a cell in such halfway state, eRead returns a > > value specified only to be 0 or 1. That otherwise unspecified value > > may in particular change after disruption (due e.g. to uncontrollable > > random noise and/or temperature and/or voltage drift in the hardware > > used by eRead), even though the sate of cells is unchanged by > > disruption or/and eRead. > > > > Note: if a cell is not erased (left in a halfway state or > > programmed), an eProgram of that cell is prohibited. A workaround is > > to use the #include <stdio.h> #include <stdlib.h> /* EEprom, 20100313, Avk * * Encoding. * I use four bits. Two or three of these are ever set. * The two 1-bits walk from right to left: a two-bit pattern * grows a bit at it's left side; a three-bit pattern looses one * 1-bit at the right side. * A nice property of this encoding is, that for every * 'allowed' two bit pattern, the two 1-bits can be trusted; after * a crash+restart, only the 0-bits need to be re-reset. * For the patterns with three 1-bits, the middle 1-bit plus * the single 0-bit can be trusted; the outer two 1-bits are suspect. * * State table. * "trusted" bits are shown as 0 and 1; * "suspect" bits as . and ?; * -a / +a := clear / set bit 'a' * ... :+ continue with the normal state path. * * dcba dcba [ ... recovery path ... ] * 0011 ..11 [Off] -c .011 -d 0011 * 0111 0?1? -a 0?10 -c 0010 +c 0110 ... * 0110 .11. -a .110 -d 0110 ... * 1110 ?1?0 -d 01?0 -b 0100 +b 0110 ... * 1100 11.. [On] -a 11.0 -b 1100 * 1101 1?0? -a 1?00 -c 1000 +a 1001 ... * 1001 1..1 -b 1.01 -c 1001 ... * 1011 ?0?1 -b ?001 -d 0001 +b 0011 */ #define COMBINE4(d,c,b,a) (8*(d)+4*(c)+2*(b)+1*(a)) static char *states[16] = { "0000" , "0001" , "0010" , "0011" , "0100" , "0101" , "0110" , "0111" , "1000" , "1001" , "1010" , "1011" , "1100" , "1101" , "1110" , "1111" }; /* interface */ int restart(void); int getstate(void); int toggle(void); /* primitives */ static unsigned askbit(unsigned pos); static void bit_set(unsigned pos); static void bit_clr(unsigned pos); /* in core storage for the bits */ static unsigned char bits[4] = {0,0,0,0}; /* on disk storage for the bits */ static int bits_open(char *name); static void bits_flush(void); static unsigned getbits(void); int main(int argc, char **argv) { unsigned state; int rc, bit; char line[100]; rc = bits_open("bitsfile" ); fprintf (stderr, "Open := %d\n", rc ); bit = restart(); fprintf (stderr, "Restart : Bit=%d Rawbits=%02x %02x %02x %02x\n" , bit, bits[3], bits[2], bits[1], bits[0] ); while (fgets (line, sizeof line, stdin)) { switch (line[0]) { case 't': bit = toggle(); fprintf(stderr, "toggle() Bit=%d\n", bit ); case '?': state = getbits(); bit = getstate(); fprintf(stderr, "Getbits() = %s Bit=%d Rawbits=%02x %02x %02x %02x\n" , states[state], bit, bits[3], bits[2], bits[1], bits[0] ); break; case 'q': goto quit; } } quit: exit (0); } int restart(void) { unsigned state; while (1) { state = getbits(); fprintf(stderr, "Restart state = %s Rawbits=%02x %02x %02x %02x\n" , states[state] , bits[3], bits[2], bits[1], bits[0] ); switch (state) { case COMBINE4(0,0,0,0): /* before initialization */ bit_clr(2); bit_clr(1); bit_clr(0); bit_set(0); bit_set(1); bit_clr(3); return getstate(); case COMBINE4(0,0,1,1):/* ..11 [Off] */ bit_clr(2); bit_clr(3); return getstate(); case COMBINE4(0,1,1,1): /* 0?1? [Rising] */ bit_clr(0); /* 0110 0010 */ bit_clr(2); /* 0010 */ bit_set(2); /* 0110 */ return getstate(); case COMBINE4(0,1,1,0): /* .11. [Rising] */ bit_clr(0); /* .110 */ bit_clr(3); /* 0110 */ return getstate(); case COMBINE4(1,1,1,0): /* ?1?. [Rising] */ bit_clr(3); /* 0100 0110 */ bit_clr(1); /* 0100 */ bit_set(1); /* 0110 */ return getstate(); case COMBINE4(1,1,0,0):/* 11.. [On] */ bit_clr(0); /* 1100 1110 */ bit_clr(1); /* 1100 */ return getstate(); case COMBINE4(1,1,0,1): /* 1?0? [Falling] */ bit_clr(2); /* 1000 1001 */ bit_clr(0); /* 1000 */ bit_set(0); /* 1001 */ return getstate(); case COMBINE4(1,0,0,1): /* 1..1 [Falling] */ bit_clr(1); /* 1.01 */ bit_clr(2); /* 1001 */ return getstate(); case COMBINE4(1,0,1,1): /* ?0?1 [Falling] */ bit_clr(3); /* 0011 0001 */ bit_clr(1); /* 0001 */ bit_set(1); /* 0011 */ return getstate(); /*** The states below can only occur if we have crashed during recovery */ case COMBINE4(0,0,0,1): /* .0.? */ bit_clr(2); /* .0.? */ bit_clr(3); /* 00.? */ bit_set(3); /* 10.? */ bit_clr(1); /* 100? */ bit_clr(0); /* 1000 */ bit_set(0); /* 1001 */ continue; case COMBINE4(0,1,0,0): /* .?.0 */ bit_clr(0); /* .?.0 */ bit_clr(1); /* .?00 */ bit_set(1); /* .?10 */ bit_clr(3); /* 0?10 */ bit_clr(2); /* 0010 */ bit_set(2); /* 0110 */ continue; case COMBINE4(0,0,1,0): /* 0.?. */ bit_clr(3); /* 0.?. */ bit_clr(0); /* 0.?0 */ bit_clr(2); /* 00?0 */ bit_set(2); /* 01?0 */ bit_clr(1); /* 0100 */ bit_set(1); /* 0110 */ continue; case COMBINE4(1,0,0,0): /* ?.0. */ bit_clr(1); /* ?.0. */ bit_clr(2); /* ?00. */ bit_clr(0); /* ?000 */ bit_set(0); /* ?001 */ bit_clr(3); /* 0001 */ bit_set(3); /* 1001 */ continue; case COMBINE4(1,0,1,0): bit_clr(3); bit_clr(2); continue; case COMBINE4(0,1,0,1): bit_clr(0); bit_clr(3); continue; case COMBINE4(1,1,1,1): bit_clr(0); bit_clr(2); continue; default: fprintf(stderr, "Unwanted state = %s in recovery Rawbits=%02x %02x %02x %02x\n" , states[state] , bits[3], bits[2], bits[1], bits[0] ); return -1; } } return -1; } int getstate(void) { unsigned state; state = getbits(); switch (state) { case COMBINE4(1,1,0,1): bit_clr(2); case COMBINE4(1,0,0,1): bit_set(1); case COMBINE4(1,0,1,1): bit_clr(3); case COMBINE4(0,0,1,1): return 0; case COMBINE4(0,1,1,1): bit_clr(0); case COMBINE4(0,1,1,0): bit_set(3); case COMBINE4(1,1,1,0): bit_clr(1); case COMBINE4(1,1,0,0): return 1; case COMBINE4(0,0,0,0): case COMBINE4(0,0,0,1): case COMBINE4(0,0,1,0): case COMBINE4(0,1,0,0): case COMBINE4(1,0,0,0): case COMBINE4(0,1,0,1): case COMBINE4(1,0,1,0): case COMBINE4(1,1,1,1): default: break; } return -1; } int toggle(void) { unsigned state; state = getbits(); switch (state) { case COMBINE4(0,0,1,1): bit_set(2); case COMBINE4(0,1,1,1): bit_clr(0); case COMBINE4(0,1,1,0): bit_set(3); case COMBINE4(1,1,1,0): bit_clr(1); return 1; case COMBINE4(1,1,0,0): bit_set(0); case COMBINE4(1,1,0,1): bit_clr(2); case COMBINE4(1,0,0,1): bit_set(1); case COMBINE4(1,0,1,1): bit_clr(3); return 0; default: break; } return -1; } /************************************************************ * Low-level functions to simulate an eeprom using a diskfile * We use on byte per bit of storage * 0x00 := False * 0xff := True * All others := Indeterminate. * 1) write a random value * 2) sleep for 1 second (allowing us to kill the program ...) * 3) write the intended value. */ static void bit_clr(unsigned pos) { fprintf(stderr, "Bit_clr(%u) Oldval=%02x" , pos, bits[pos] ); /* crashing while in the act of clearing a "set" bit will cause it to be indeterminate */ if (bits[pos]) bits[pos] = 1+rand() % 0xFE; fprintf(stderr, " Tmpval=%02x" , bits[pos] ); bits_flush(); sleep(1); bits[pos] = 0; fprintf(stderr, " Final=%02x" , bits[pos] ); bits_flush(); fprintf(stderr, " Flushed\n" ); } static void bit_set(unsigned pos) { fprintf(stderr, "Bit_set(%u) Oldval=%02x" , pos, bits[pos] ); if (bits[pos]) { /* rewriting an already "set" bit will cause it to be indeterminate */ bits[pos] = 1+rand() % 0xFE; fprintf(stderr, " BadFinal=%02x" , bits[pos] ); bits_flush(); fprintf(stderr, " Crashed\n" ); exit(EXIT_FAILURE); } else { bits[pos] = 1+rand() % 0xFE; fprintf(stderr, " Tmpval=%02x" , bits[pos] ); bits_flush(); sleep(1); bits[pos] = 0xFF; fprintf(stderr, " Final=%02x" , bits[pos] ); bits_flush(); fprintf(stderr, " Flushed\n" ); } } static unsigned askbit(unsigned pos) { switch(bits[pos]) { case 0: return 0; case 0xff: return 1; default: return (1+rand() % 0xFE) > bits[pos] ? 0 : 1; } } static unsigned getbits(void) { #if 0 unsigned val; val =askbit(0) + 2 * askbit(1) + 4 * askbit(2) + 8 * askbit(3) ; return val; #else return COMBINE4( askbit(3), askbit(2), askbit(1), askbit(0)); #endif } static FILE *bitsfile = NULL; int bits_open(char *name) { int rc; bitsfile = fopen(name, "r+" ); if (!bitsfile) bitsfile = fopen(name, "w+" ); if (!bitsfile) return -1; rc = fread(bits, sizeof bits, 1, bitsfile); if (rc < 1) rc = fwrite(bits, sizeof bits, 1, bitsfile); return rc <1 ? -1 : 0; } static void bits_flush(void) { fseek (bitsfile, SEEK_SET, 0); fwrite(bits, sizeof bits, 1, bitsfile); fflush(bitsfile); } /*********** Eof **************/ AvK
From: Thad Smith on 14 Mar 2010 22:20
Moi wrote: > On Fri, 12 Feb 2010 21:49:21 -0700, Thad Smith wrote: > >> Francois Grieu wrote: >>> /* >>> Disclaimer: This is a hard problem, only minimally disguised into >>> something on-topic for comp.lang.c >> comp.programming and comp.arch.embedded added to the list. > * Encoding. > * I use four bits. Two or three of these are ever set. > * The two 1-bits walk from right to left: a two-bit pattern > * grows a bit at it's left side; a three-bit pattern looses one > * 1-bit at the right side. > * A nice property of this encoding is, that for every > * 'allowed' two bit pattern, the two 1-bits can be trusted; after > * a crash+restart, only the 0-bits need to be re-reset. > * For the patterns with three 1-bits, the middle 1-bit plus > * the single 0-bit can be trusted; the outer two 1-bits are suspect. > * > * State table. > * "trusted" bits are shown as 0 and 1; > * "suspect" bits as . and ?; > * -a / +a := clear / set bit 'a' > * ... :+ continue with the normal state path. > * > * dcba dcba [ ... recovery path ... ] > * 0011 ..11 [Off] -c .011 -d 0011 > * 0111 0?1? -a 0?10 -c 0010 +c 0110 ... > * 0110 .11. -a .110 -d 0110 ... > * 1110 ?1?0 -d 01?0 -b 0100 +b 0110 ... > * 1100 11.. [On] -a 11.0 -b 1100 > * 1101 1?0? -a 1?00 -c 1000 +a 1001 ... > * 1001 1..1 -b 1.01 -c 1001 ... > * 1011 ?0?1 -b ?001 -d 0001 +b 0011 > */ What is the recovery path for 0000, the initial state? -- Thad |