Request for code review

[tomas-nestorovic]

Hi,

I yesterday ran into a problem that my diff implementation (adopted from the internet) in some cases actually doesn't work reliably.

Suppose I have a bit stream of zeros and ones, called simply "mine" (99658 bits) and "theirs" (99655 bits). These represent low-level magnetic information of two full revolutions of one and the same track on a 2DD floppy (nominally 100,000 bits).

Apart from being of different lengths (theirs being by three bits shorter than mine), there is also a difference in the middle - 34,425-th bit is different, thanks to magnetic deterioration. Otherwise, the two bit streams are identical.

My implementation of the diff algorithm produces the following script that transforms mine into theirs (unlike the numbering in OpenOffice Calc, the numbering of bits is zero-based, hence off by 1). The first two seem to successfully deal with the difference in the middle. The latter two fail to remove the tail three extra bits in mine.

• insertion of 1 bit from theirs at 34424 into mine at 34424,
• deletion of 1 bit from mine at 34424,
• deletion of 1 bit from mine at 99646,
• deletion of 1 bit from mine at 99650.

Because I've exhausted all my skills, I would like to ask if anyone could check my implementation of the diff algorithm and eventually fix the bug that's inside. Although I read Mr.Myers's paper "An O(ND) Difference Algorithm and its Variations," I'm not much more clever than before. The diff algorithm is implemented here (circa 100 lines of actual code):
https://github.com/tomas-nestorovic/RIDE/blob/master/Main/src/Diff.h

Edit: Attached mine.txt and theirs.txt with respective bit streams.
theirs.txt
mine.txt

MANY THANKS IN ADVANCE FOR ANY RESPONSES! :-)

[tekwizz123]

@tomas-nestorovic This would probably be better in a form post or similar, as this isn't an issue within diff-match-patch per say but rather a request for feedback on your own project.