For this game, that codec was Cinepak. The Cinepak decoder has been in ScummVM since 2009 (I wrote it in late 2007 or so, so it's really even older). I refused to use some other dithering algorithm that would have been different and given different results. If I was going to implement this, I was going to do it to match the original 100%. That meant it was time to figure out what it does.
Basically, the algorithm is based on pre-dithered tables that are for a given hardcoded palette. For custom palettes, it finds the nearest (using a simple distance equation) color in it and maps from the Cinepak palette index to the custom one. It then uses the pre-dithered tables to generate 4x4 blocks based on the contents of the codebook which is then mapped to the custom palette.
I pushed the code for the curious.
QuickTime also does something similar (but with a different dithering algorithm in Cinepak, of course), which I'll be working on for Myst.
Here's the result, using one of the Cinepak samples from the MPlayer samples archive (in this case, the Lara Croft one):
|Normal decode to 24bpp
|Dither to 8bpp
The result looks pretty decent. I was mostly glad it wasn't a ridiculous amount of extra code.