=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Date: Tue, 30 Nov 1999 23:17:06
From: Dwayne Reid
To: PICLIST@MITVMA.MIT.EDU
Subject: challenge - which number is higher
--------------------------------------------------------------------------------
I have an interesting problem that I'd like to throw to the gurus.
I am storing a number of records in eeprom - kind of a circular buffer
arrangement. Part of each record is a 1 byte number used as a 'sequence'
counter - its purpose is to tell me which record is the newest. The counter
will start at 00, increment to FF, then roll over back to 00.
This is the challenge: how to tell which number is highest. The records
are stored in a fixed sequence, with the oldest record being overwritten by
the current record. Again, the sequence number is part of the record being
stored.
When the system powers up, I need to retreive the newest record and stick it
into RAM.
Eg. Read the sequence number from 8 records and find the most recent record.
00 01 02 03 04 05 06 07 (easy)
F9 FA FB FC FD FE FF 00 (harder)
FE FF 00 01 02 03 04 05 (harder)
The problem is dealing with the wrap from FF to 00.
Thoughts, ideas?
dwayne
Dwayne Reid
Trinity Electronics Systems Ltd Edmonton, AB, CANADA
(780) 489-3199 voice (780) 487-6397 fax
Celebrating 15 years of Engineering Innovation (1984 - 1999)
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Do NOT send unsolicited commercial email to this email address.
My posting messages to Usenet neither grants consent to receive
unsolicited commercial email nor is intended to solicit commercial
email.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Date: Wed, 01 Dec 1999 09:01:31
From: "Nikolai Golovchenko"
To: "pic microcontroller discussion list"
Subject: Re: challenge - which number is higher
--------------------------------------------------------------------------------
Hello Dwayne.
>Eg. Read the sequence number from 8 records and find the most recent
record.
>
>00 01 02 03 04 05 06 07 (easy)
>F9 FA FB FC FD FE FF 00 (harder)
>FE FF 00 01 02 03 04 05 (harder)
>
>The problem is dealing with the wrap from FF to 00.
You can solve the problem by searching for negative difference between
consecutive records sequence numbers. 7 bit signed value should be used for
difference. The trick is that 0 - 255 = +1 in this case, i.e. transition
from 255 to 0 is treated as usual ascending of numbers.
For example, scanning records
1) 00 01 02 03 04 05 06 07 will give differences +1 and -7 (0 - 7 = -7, so 7
is more recent)
2) 08 01 02 03 04 05 06 07 " " " " " " (1 - 8 = -7. 8 -
recent)
3) F8 F9 FA FB FC FD FE FF " " " " " " (F8 - FF = -7. FF -
recent)
4) 00 F9 FA FB FC FD FE FF " " " " " " (F9 - 0 = -7. 0 -
recent)
5) 00 01 02 03 04 05 06 FF " " " " " " (FF - 6 = -7. 6 -
recent)
This method will work for 7 and 6 records too.
Regards.
_
Nikolai Golovchenko, Electrical Engineering Student
National Mining University of Ukraine www.nmuu.dp.ua
Dnepropetrovsk, Ukraine
E-mail: golovchenko@mail.ru
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Date: Thu, 02 Dec 1999 07:36:11
From: "Nikolai Golovchenko"
To: "pic microcontroller discussion list"
Subject: Re: challenge - which number is higher
--------------------------------------------------------------------------------
Hi Wagner
>Any other math solution doesn't work, since if your block ID's are also
>circular from 00 to FF, there is NO WAY to find out which one was the
>last, except in one condition:
>If your circular buffer size is not a perfect multiple of the (block
>data size + Id) * 256. In this case you can search for a disrupt in ID
Why should the block size be so restricted? You just have to know the block
size, whatever it is, to find IDs locations. The block size have to be fixed
though, because EEPROM failure may disrupt the whole sequence.
>sequence. For example, if you circular buffer is only 256 bytes long
>and your block size is 32 bytes:
>
>ID DATA (31Bytes)- - - - - - - ->
>01 00 01 02 03 04 ... 1E <--- begin of circular buffer
>FD 00 01 02 03 04 ... 1E
>FB 00 01 02 03 04 ... 1E
>FC 00 01 02 03 04 ... 1E
>FD 00 01 02 03 04 ... 1E
>FE 00 01 02 03 04 ... 1E
>FF 00 01 02 03 04 ... 1E.
>00 00 01 02 03 04 ... 1E <--- end of circular buffer
>
>If the block size is fixed, then you see that the difference between two
>block ID's is different than 1 it means the lower address block is the
>last one, if the circular buffer runs up address. In this example it is
>clear that the last register is the first on the buffer.
Because of the possible record failure, looking for difference different
from 1 may not work.
>Again, this technique will not works if your circular buffer holds only
>2 blocks,
But it will if you are looking for *negative* difference.
2 blocks example:
00 01 1 - 0 = 1, next, 0 - 1 = -1, bingo! 1 is last
02 01 1 - 2 = -1, 2 is last
02 03 3 - 2 = 1, next, 2 - 3 = -1, 3 is last
FE FF FF - FE = 1, next, FE - FF = -1, FF is last
00 FF FF - 0 = FF = -1, 0 is last
With this technique, all possible IDs make up a circle,
00 01
FF 02
FE 03
.
. 04
0A 05
09 06
08 07
where IDnext = IDprevious + 1. Because ID can overflow, this is not true
when IDprevious = FF. If you use for difference the same number of bits,
i.e. 8, then the difference will overflow too at the same place (00 - FF =
1). In this case, if you take any two consecutive numbers on the circle the
difference is *1* always. And different from 1 if distance between IDs is
greater than 1.
In Dwayne's case there is a possibility of EEPROM failure that may cause one
record to be bad (record writing cycle not finished in case of power down).
So difference may be 2 as well for ascending numbers. Value, different from
1 or 2, will indicate the end of sequence. This makes possible *254* length
of sequence!! Since Dwayne needs only 8 records I would suggest just test
the MSB of 8 bit difference.
Hope it helps :)
_
Nikolai Golovchenko, Electrical Engineering Student
National Mining University of Ukraine www.nmuu.dp.ua
Dnepropetrovsk, Ukraine
E-mail: golovchenko@mail.ru