Mdcomp
From Sega Retro
mdcomp (also known as FW-KENSC) is a collection of software libraries and tools, made by Flamewing, which implement compressors and decompressors for various Mega Drive-related formats. It is notable for achieving optimal compression of LZSS-based formats by leveraging graph theory, and also achieving near-optimal compression of the Nemesis format.
Overview
mdcomp provides compressors and decompressors as a series of C++ classes, along with matching frontend programs, which are licensed under the terms of the LGPLv3. The frontend programs are to be used on the command line, and do not have a graphical interface. Also provided are several decompressors written in Motorola 68000 assembly, which are 0BSD-licensed.
mdcomp purposefully avoids naïve data compression techniques, favouring compression ratio over compression speed and RAM usage. Its LZSS compressor computes a graph that represents each byte of the uncompressed data as a node, and each possible LZSS match as an edge which connects two nodes. Each edge is assigned a cost (the number of bits that it would cost to encode the match), and a shortest-path algorithm is used to determine the combination of matches which produces the smallest possible data, thus achieving optimal compression.
