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.*
