A bit resistant to disruption

T

Thad Smith

Francois said:
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.

After having two previous attempts shot down, I have two more proposals. Today
I am describing the "game" solution. The game solution is optimized for minimum
number of bits and fastest execution, ignoring power cycle wear factor, a
concern with real EEPROM in high power cycle uses.

State ba Powerup sequence
p1 00 p1, p2, s1
p2 01 p2, p1, p2, s1
s1 11 s1, p2, p1, p2, s1
s2 10 erase a (a=0)

On powerup, perform the indicated powerup sequence. Powerup in s2 erases a, all
others erase both bits and return to s1. With power on, toggle bit a to go from
s1 to s2. Going from s2 to s1 is a program without erase.

The toggle cost is one erase or program time.
 
F

Francois Grieu

Thad Smith wrote :
After having two previous attempts shot down, I have two more
proposals. Today I am describing the "game" solution. The game
solution is optimized for minimum number of bits and fastest execution,
ignoring power cycle wear factor, a concern with real EEPROM in high
power cycle uses.

Very right. However EEPROM wear is easy to solve with one extra cell,
at some cost in time.
State ba Powerup sequence
p1 00 p1, p2, s1
p2 01 p2, p1, p2, s1
s1 11 s1, p2, p1, p2, s1
s2 10 erase a (a=0)

On powerup, perform the indicated powerup sequence. Powerup in s2
erases a, all others erase both bits and return to s1. With power on,
toggle bit a to go from s1 to s2. Going from s2 to s1 is a program
without erase.

Well, let's attack that..

We are moving from s1 to s2, thus erase a;
disruption occurs, cells are left 1?

On power-up we read 11, that is s1, and proceed to move to p2
that is erase b; disruption, cells are left ??

On power-up we read 10, and erase a (that's during bRead);
cells are now ?0; we believe we are in state s2 (the test
program lights in some color)

Disruption occurs outside bRead/bToggle (with the light on),
after bRead, thus with the bit supposedly stable.

On power-up we read 00, and proceed to s1 without disruption;
we believe we are in state s1 (the test program lights in
some other color). This breaks the stability rule, bust.


If there is a solution with two cells, I quit programming.

The toggle cost is one erase or program time.

At the expense of correctness! I went down the same pitfall.
Someone on rec.puzzles broke my nearly-published version,
optimized for fastest execution [the only one I committed
with a hash :-( ]. Now I need time to recheck the baseline
3-cells solution, and it won't be as fast as I claimed.

I'll post my C version (or admit defeat on my own problem)
this week, promised.


Francois Grieu
 
T

Thad Smith

Francois said:
Thad Smith wrote :

Well, let's attack that..

We are moving from s1 to s2, thus erase a;
disruption occurs, cells are left 1?

On power-up we read 11, that is s1, and proceed to move to p2
that is erase b; disruption, cells are left ?? ....
> If there is a solution with two cells, I quit programming.

I'm batting 0 for 3 here. Here is another "game" trial solution, this time with
3 bits.

State cba Powerup sequence
p1 000 erase cba, s1
s1 001 (no change)
t1 101 erase b, s1, p1, s1
t2 100 erase ba, p1, s1
t3 110 erase a, t2, p1, s1
s2 010 erase c


s1 to s2: erase c, t1, t2, t3, s2.
s2 to s1: t3, t2, t1, s2.

State s1 has no change on powerup. If interrupted during p1-s1 or s1-t1 we may
read s1 for an arbitrary duration, then later read p1, t1, or t2, all which
transition to s1 on powerup or proceed to s1 with the given s1-s2 transition.
s2 must be refreshed on powerup by erasing c.
 
F

Francois Grieu

Thad said:
I'm batting 0 for 3 here. Here is another "game" trial solution, this
time with 3 bits.

State cba Powerup sequence
p1 000 erase cba, s1
s1 001 (no change)
t1 101 erase b, s1, p1, s1
t2 100 erase ba, p1, s1
t3 110 erase a, t2, p1, s1
s2 010 erase c


s1 to s2: erase c, t1, t2, t3, s2.
s2 to s1: t3, t2, t1, s2.

State s1 has no change on powerup. If interrupted during p1-s1 or s1-t1
we may read s1 for an arbitrary duration, then later read p1, t1, or t2,
all which transition to s1 on powerup or proceed to s1 with the given
s1-s2 transition. s2 must be refreshed on powerup by erasing c.

At first I thought this could work; it would have been more efficient
than my solution by a mile. But on second look..

We are at the last step of moving from s1 to s2, disruption occurs
while we erase c; cells are [?10].
On power-up we get 110, and thus erase a, then attempt to proceed to
t2, disruption occurs while we erase b; cells are [??0].
On powerup we get 010, and thus erase c; we act as if we are at s2,
but cells are [0?0]. The test program turns the light in some color.
Disruption occurs.
On power-up we get 000, and proceed to s1. The test program turns the
light in the other color. Bust.

My solution is *nearly* ready to post.

Francois Grieu
 
T

Thad Smith

Francois said:
Thad Smith wrote :

Well, let's attack that..

We are moving from s1 to s2, thus erase a;
disruption occurs, cells are left 1?

On power-up we read 11, that is s1, and proceed to move to p2
that is erase b; disruption, cells are left ??

On power-up we read 10, and erase a (that's during bRead);
cells are now ?0; we believe we are in state s2 (the test
program lights in some color)

Disruption occurs outside bRead/bToggle (with the light on),
after bRead, thus with the bit supposedly stable.

On power-up we read 00, and proceed to s1 without disruption;
we believe we are in state s1 (the test program lights in
some other color). This breaks the stability rule, bust.

If there is a solution with two cells, I quit programming.

It's been a while now. Here is another attempt at minimal bit implementation.
This is another "game" solution (powerup activity for both resting states). The
powerup operations can be done on the first call to read the non-volatile bit.

State ba Powerup sequence
s0 00 erase b,a
s1 01 erase b, p3, p2, p3, s1
p2 10 erase a, p3, s1
p3 11 s1, p3, p2, p3, p1

The resting states are s0 and s1.
Programmed transitions:
s0 to s1: s0, s1
s1 to s0: s1, s0

The programmed transitions are a bit erase or program on "a". After the powerup
sequence is done both bits are stable.
 
M

Moi

comp.programming and comp.arch.embedded added to the list.



#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
 
T

Thad Smith

* 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?
 
T

Thad Smith

Thad said:
Moi said:
On Fri, 12 Feb 2010 21:49:21 -0700, Thad Smith wrote:
* 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?

It would be best to specify the recovery path for all possible startup states.
How about startup in 0, 1, 2, 4, 5, 8, a, f, interpreting bit combination as
hexadecimal?

I assume that resting states are 3, 6, c, 9, where 3, 6 are global off, while c
and 9 are global on. Is this correct?
 
M

Moi

It would be best to specify the recovery path for all possible startup
states. How about startup in 0, 1, 2, 4, 5, 8, a, f, interpreting bit
combination as hexadecimal?

I assume that resting states are 3, 6, c, 9, where 3, 6 are global off,
while c and 9 are global on. Is this correct?

It is in the code. The comment at the top of the
file only describes the normal flow of state.

**********/

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] */

/*************

et cetera.

AvK
 
T

Thad Smith

Moi said:
It would be best to specify the recovery path for all possible startup
states. How about startup in 0, 1, 2, 4, 5, 8, a, f, interpreting bit
combination as hexadecimal?

I assume that resting states are 3, 6, c, 9, where 3, 6 are global off,
while c and 9 are global on. Is this correct?

It is in the code. The comment at the top of the
file only describes the normal flow of state.

**********/

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] */

/*************

et cetera.

Since Francois hasn't posted in a while, I'll do the analysis.
The initial state, before the program runs is 0000. Run the initialization for
that state and interrupt during bit_set(1), producing 00?1.

On subsequent powerup, bits 2 and 3 are erased, not changing the state and
resting at 00?1. It can be read as either global state 0 or global state -1
without intervening toggle.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top