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? You can calculate the CRC a nibble-at-a-time using a much smaller table using two lookups. >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 : "This approach only requires 16 unsigned integers that occupy a mere 32 bytes in a typical machine. The only requirement is that two table look-ups are required for each byte instead of one table look-up. Clearly this is a classic trade-off between storage conservation versus conservation of machine cycles." -W. David Schwaderer Yes, it is titled as a "NetBIOS" book, but it's got a lot to say about CRC calculations. Listings in the book use the C programming language to both generate the lookup table and calculate the CRC. "Look at this Tiny CRC-CCITT Look-Up Table ... 0x00 - 0000 1081 2102 3183 4204 5285 6306 7387 0x08 - 8408 9489 A50A B58B C60C 0680 E70E F78F" -W. David Schwaderer Although my favorite quote from Schwaderer is earlier in the book when he first starts to discuss CRC calculations: "Recall the many pleasures of polynomial division." Regards, Douglas On Sat, Mar 28, 2026 at 1:58 AM B 9 <[email protected]> wrote: > On Fri, Mar 20, 2026 at 12:17 AM B 9 <[email protected]> wrote: > >> On Thu, Mar 12, 2026 at 10:49 AM Brian K. White <[email protected]> >> wrote: >> >> Oh yeah I switched to a rolling xor checksum too. >>> It only needs ints in basic and I think actually catches more errors. >>> Still kind of swiss cheese compared to real crc algorithms but those are >>> expensive and this is cheap. >>> >> Need a cheap CRC algorithm? Coincidentally, I made a 34-byte 8080 >> machine language <https://github.com/hackerb9/crc16-8080/> program which >> calculates CRC16/xmodem. Are you seeing many transmission errors? >> > I knew 34 bytes wasn't quite true since it wasn't usable directly from > BASIC. I created a longer, 55-byte CRC-16 program > <https://github.com/hackerb9/crcbas/blob/main/gencrc.asm> which has a > nicer BASIC interface via CALL with the varptr to an array of integers for > arguments. But, that's still not quite right, because it doesn't count the > BASIC loader program. This is certainly not the most efficient way of doing > it, but I created one that weighs in at about 400 or 500 bytes: > > https://github.com/hackerb9/crcbas > > It provides a general purpose machine language CRC-16 checksum, usable > from BASIC, that relocates itself to run from a string buffer so it doesn't > conflict with any .CO files. It's pretty fast and can be used > incrementally, if you like. > > Let me know what you think and if you have any ideas for ways to make it > less expensive. > > —b9 > >
