Post by thread:[PIC:] Much better 16 bit checksum.--Piclist versi

Hi- I have been following this with half an ear. Looking in the Piclist archives http://www.piclist.com/techref/microchip/crcs.htm finds this code: http://www.piclist.com/techref/microchip/crc16-aw.htm for the CRC algorithm. Takes 64 cycles per byte, so might be too slow. But check the first url, too, as there are other implementations. David -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.

David P Harris wrote: > Hi- > I have been following this with half an ear. Looking in the Piclist > archives http://www.piclist.com/techref/microchip/crcs.htm finds this > code: http://www.piclist.com/techref/microchip/crc16-aw.htm for the CRC > algorithm. Takes 64 cycles per byte, so might be too slow. But check > the first url, too, as there are other implementations. > David > > -- > http://www.piclist.com hint: The PICList is archived three different > ways. See http://www.piclist.com/#archives for details. > As an addendum, I found this reference to Fletcher's: en.wikipedia.org/wiki/Fletcher%27s_checksum and it also has an url to a paper on comparing methods. They claim that checksums on real data perform more poorly thatn on random test data. They also make the claim that it is much better to checksum over a longer block than over multiple smaller blocks. Therefore, perhaps the btloader should checksum over the entire program, rather that individual bocks. David -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.

On Sun, 27 Jun 2004, David P Harris wrote: > Hi- > I have been following this with half an ear. Looking in the Piclist > archives http://www.piclist.com/techref/microchip/crcs.htm finds this > code: http://www.piclist.com/techref/microchip/crc16-aw.htm for the CRC > algorithm. Takes 64 cycles per byte, so might be too slow. But check > the first url, too, as there are other implementations. Here are some other implementations as well: http://www.dattalo.com/technical/software/pic/crc.php There are several CRC polynomials implemented. I think the most efficient is the 17-cycle/byte implementation of the 0x1021 polynomial. Scott -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.

Scott Dattalo wrote: {Quote hidden}> On Sun, 27 Jun 2004, David P Harris wrote: > >> Hi- >> I have been following this with half an ear. Looking in the Piclist >> archives http://www.piclist.com/techref/microchip/crcs.htm finds this >> code: http://www.piclist.com/techref/microchip/crc16-aw.htm for the CRC >> algorithm. Takes 64 cycles per byte, so might be too slow. But check >> the first url, too, as there are other implementations. > > > Here are some other implementations as well: > > http://www.dattalo.com/technical/software/pic/crc.php > > There are several CRC polynomials implemented. I think the most efficient > is the 17-cycle/byte implementation of the 0x1021 polynomial. > > Scott > > -- > http://www.piclist.com hint: The PICList is archived three different > ways. See http://www.piclist.com/#archives for details. > I suspect that, althought these are relatively fast, they involve look-up tables, which will blow away the quota for space in a bootloader :-( David -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.

Many many many years ago (probably 1970s) Wireless World magazine published an article on a checksum system which distributed the check bits longitudinally and vertically across many bytes of data. AFAIR a patent was applied for for the method. The memory thereof is dim but I think they claimed ease of computation and great resistance to error. A literature search may be worthwhile? RM -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.

On Sun, 27 Jun 2004, David P Harris wrote: > Scott Dattalo wrote: >> >> Here are some other implementations as well: >> >> www.dattalo.com/technical/software/pic/crc.php >> >> There are several CRC polynomials implemented. I think the most efficient >> is the 17-cycle/byte implementation of the 0x1021 polynomial. <snip> > I suspect that, althought these are relatively fast, they involve > look-up tables, which will blow away the quota for space in a bootloader :-( Why would you suspect such a thing? Perhaps I should've written 17-cycles/byte, 17 words total. All of the routines on my page are unlooped. The others take more than 17 words. The lookup tables that you may see there (if you bother to look) are the inefficient implementations that serve as an invariance check. Scott -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.

Scott Dattalo wrote: {Quote hidden}> On Sun, 27 Jun 2004, David P Harris wrote: > >> Scott Dattalo wrote: >> >>> >>> Here are some other implementations as well: >>> >>> www.dattalo.com/technical/software/pic/crc.php >>> >>> There are several CRC polynomials implemented. I think the most >>> efficient >>> is the 17-cycle/byte implementation of the 0x1021 polynomial. >> > > <snip> > >> I suspect that, althought these are relatively fast, they involve >> look-up tables, which will blow away the quota for space in a >> bootloader :-( > > > Why would you suspect such a thing? Perhaps I should've written > 17-cycles/byte, 17 words total. All of the routines on my page are > unlooped. The others take more than 17 words. The lookup tables that you > may see there (if you bother to look) are the inefficient implementations > that serve as an invariance check. > > Scott > > -- > http://www.piclist.com hint: The PICList is archived three different > ways. See http://www.piclist.com/#archives for details. > Oh. I'm sorry, I thought they were part of the algorithm... well 17 cycles/17 words sounds very good! David -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.