Follow me down the optimization rabbit hole

Intro In a previous article, I wrote about my low memory GIF decoder and how I optimized it to run on embedded/Arduino devices. For this article, we're going in the opposite direction. What if you had all the memory you needed, what could be done to speed up LZW decoding? I asked myself this question many years ago and found some ideas that I refined and then optimized further. The Traditional Way The basis of LZW compression is that a dictionary of repeated strings is built dynamically as you encode and decode the code stream. In the traditional implementation, this dictionary is a data structure with a linked-list connecting each color/symbol to the previous in order to represent the different repeating patterns that are compressed in the data stream. When a codeword is encountered that represents a 'string' of colors/symbols, the output is generating by walking down the linked-list. The list is generated in reverse order (the last entry points to the previous), so the p...

Intro I believe Arduino's software development IDE has been one of the biggest reasons for their success. Combined with their core API that "just works" across multiple MCU architectures, these two elements have made embedded software development accessible to everyone. If you've ever ventured outside of the Arduino 'bubble' and tried to do embedded software development on other vendor's IDEs, then you know what I mean. They routinely involve complex setup procedures, poor documentation, custom APIs, external interface hardware, and sometimes even licensing fees. For my work, one of the most valuable features of the Arduino system is the homogeneity of working with different target processors. I use a wide selection of boards and switching between radically different MCUs usually just involves selecting the target and recompiling. One thing that was missing from the Arduino IDE was the ability to do 'live debugging' of embedded boards. On our PCs w...