Re: [stella] Clones

Subject: Re: [stella] Clones
From: tjentzsch@xxxxxx
Date: Sat, 28 Oct 2000 17:44:10 +0100
Piero Cavina <p.cavina@xxxxxxxxxxxxx> wrote:

>I'd like to know more details about the comparison algorithm.

It's something like the LZW-algorithm that is/was used in file-
compressors (ZIP, RAR, ARJ...). First i'm doing an RLE compression 
on both files that i want to compare, this eliminates long 
sequences of the same byte, because those could give wrong results. 
The main part is the dictionary based compression. First i'm 
building a dictionary for file A. This means all byte sequences are 
sorted into a binary search tree. Then i'll try to find matching 
sequences in this tree for file B. The more sequences i need, the 
lower is the identity. Then i'm doing the same thing for file B vs. 
file A and compute the average.

You have two files which only differ by one byte.
- after RLE compression both files have a size of 4000 bytes.
- we get three sequences (one before, one after the different byte 
and the different byte itself). Each sequence counts 2, except 
those that are only one byte long, which count 1. This gives a 
total of 5. Then we subract 2, because identical files consist of 
exactly one sequence, and we get 3. 
- the result is computed: (1-3/4000)*100 = 99.925% (my program 
would display 99 because i'm truncating the results)

It's a very simple approach, but the results are quite good.

It's interseting that Pac Man and Brick-Kick match that much, i 
guess they used the same (flickering) routine to display the 
ghost/penguins. Maybe it's (nearly) the same kernel. 
Btw: Which game was released first? If it was Brick-Kick, that 
would explain, how it was possible to finish Pac Man in six weeks, 
(and why it became that bad).

>And I didn't know that so many PAL carts had been dumped. It would 
>interesting to understand which are the differences with the NTSC 

You can find those dumps at:


Archives (includes files) at
Unsub & more at

Current Thread