=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- 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