Hi Douglas! I forgot to let you know that I tried out Schwarderer's Nybble oriented CRC16 idea and found it disappointing on this architecture. The Intel 8080/8085 just doesn't have easy ways to manipulate 4-bit nybbles. I figured out a few different ways to do it, but all of them were longer in bytes and ended up being much slower than the regular (1-bit, 8-bit) routines.
—b9 On Sun, Mar 29, 2026 at 1:14 AM B 9 <[email protected]> wrote: > On Sat, Mar 28, 2026 at 10:26 AM Douglas Quagliana <[email protected]> > wrote: > > b9 writes: >> >Let me know what you think and if you have any ideas for >> >ways to make it less expensive. >> >> Have you considered a compromise between single-bit-at-a-time >> CRC calculations and byte-at-a-time CRC lookup table? >> > Thank you, Douglas. I had not, yet, considered that possibility! I presume > you saw the crc16-8080 page, but for those following along at home, I > currently have three 8080 implementations: > Version Assembled Size Speed* Features > CRC-bytewise.asm > <https://github.com/hackerb9/crc16-8080/blob/main/crc16-bytewise.asm> 548 > bytes 4 seconds Fastest. Uses a 512 byte (256 word) lookup table. > Unsuitable for crcbas because it is too large to fit in a single BASIC > string. > CRC-bitwise.asm > <https://github.com/hackerb9/crc16-8080/blob/main/crc16-bitwise.asm> 110 > bytes 6 seconds Reasonable compromise. Has no table but it is still > rather large (over a hundred bytes) because it has unrolled the loop for > the bits in the byte. > CRC-pushpop.asm > <https://github.com/hackerb9/crc16-8080/blob/main/crc16-pushpop.asm> 34 > bytes 9 seconds Smallest. Same as bitwise, but uses a loop which is much > slower because it makes up for the lack of registers on the 8080 by using > PUSH/POP. (There probably is a smarter way to do this. I am still learning > 8080 assembly and only recently learned how to reserve space for a > variable.) > > > ** “Speed” is time to calculate the CRC-16 of the 72K ROM on a Tandy 200 > (8085 @2.4576 MHz).* > > > The push/pop version’s small size (34 bytes) made it the obvious choice > for crcbas.do <https://github.com/hackerb9/crcbas>, which is intended to > be inexpensive for people to include in their own BASIC programs. While a > 32 byte nybble lookup table would double the size of that program, I expect > the size would not be as bad as bitwise loop unrolling and the speed > increase may be significantly better. I'll have to give it a try. > > Currently the most expensive part of my CRC routine is the filesize which > is dominated by a BASIC loader that's ten times larger than the machine > language. I'm not an expert BASIC programmer, so my code > <https://github.com/hackerb9/crcbas> is probably woefully inefficient. > > > From Chapter 17 "CRC-CCITT and Minimum Look-Up Table Sizes" >> in C Programmers Guide to NetBIOS by W. David Schwaderer. >> ISBN 0-672-22638-3 : [...] >> > Yes, it is titled as a "NetBIOS" book, but it's got a lot to say >> about CRC calculations. >> > Certainly not where I would have thought to look, but darned if you aren’t > right. The entire third part of the book is entitled “A Cyclic Redundancy > Check (CRC) Treatise > <https://archive.org/details/cprogrammersguid00schw/page/167/mode/1up>”. > The different knowledge bases we all bring makes this a fun mailing list to > be on! (Also, *“Recall the pleasures of polynomial division,”* is an > objectively hilarious phrase.) > > For my crcbas code, I chose to implement CRC-16/XMODEM since the algorithm > was widely known and implemented on 8-bit CPUs so it could be easily > verified. XMODEM uses the following polynomial which I accepted without > questioning > <https://users.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf> > its fitness: > > 11021₁₆ = 1 0001 0000 0010 0001₂ = x¹⁶ + x¹² + x⁵ + x⁰ > > But where did XMODEM get that polynomial? I’m not sure, but it *may* have > come from our Pleasurable Polynomial friend, W. David Schwaderer! In 1985, > Schwaderer wrote an article for PC Tech Journal > <https://archive.org/details/PC_Tech_Journal_vol03_n04/page/n119/mode/2up> > that showed some of the flaws in the homespun checksum algorithm XMODEM had > been using since 1977 and suggested using CRC-16 instead. He cited the > above polynomial as being the best currently known. Not long after the > article was published, Ward Christiansen, the original author of XMODEM who > had famously resisted accepting any changes for years, wrote > <https://github.com/tehmaze/xmodem/blob/master/doc/ymodem.txt> that it > was time for him to propose an incremental extension to allow (among other > things) CRC-16 error checking. > > —b9 > > P.S. I found it amusing to see what PC Tech Journal had omitted from > Schwarderer’s writing that he later published in his CRC Treatise: > > *As an example of an error that XMODEM does not detect, consider one that > reverses the position of two adjacent bytes within a message. Here, “carp” > may erroneously become “crap.” Since the sum of the binary values of the > characters is the same, the error goes undetected with curious and > unpredictable social consequences.* >
