winhelp: bug fix in LZ77 decompressor

HolyLich lich at math.spbu.ru
Tue Aug 8 09:03:06 CDT 2006


On Tue, 8 Aug 2006 09:37:09 -0400, Kuba Ober <kuba at mareimbrium.org> wrote:

>> > >  Fix rather unusual bug in LZ77 decompressor. We cannot use
>> > >  memcpy
>> > > with overlapped areas because of unpredictable result. We must
>> > > copy byte-by-byte.
>
>> > Why don't you use memmove instead? The man page for memcpy says:
>> > Use memmove(3) if the memory areas do overlap.
>
>> We cannot use memmove. It provides different functionality. It moves
>> blocks, but LZ77 decompress algorithm copies bytes.
>>
>> Let's suppose:
>> 012
>> XYZ
>>
>> When we say 'memmove(1, 0, 2)' we will get:
>> 012
>> XXY
>>
>> But we (LZ77 algorithm) expect:
>> 012
>> XXX (three 'X').
>>
>> memcpy is rather clever (it optmizes process by coping INT instead of
>> BYTES). This optimization is fatal for LZ77.
>
> Why?
>
> Er, if the memcpy worked (or almost worked) and failed due to overlap
> problems, then memmove will do the trick. Did it ever work at all before?
> Either this code never worked, or you're either seeing a problem that doesn't
> exist/misunderstanding things.
>
> Cheers, Kuba

memmove provides OTHER functionality - it GUARANTEES, that if blocks overlaps,
then destination area will the same as source area before.
LZ77 decompress algorithms needs copiing byte-by-byte - of course, if areas overlap,
then dest area WILL NOT match the src area before. It IS correct for LZ77!

The simpliest version
of memcpy routine, like this:

void my_memcpy(char *dst, char *src, int len)
{
   while (len-->0) *dst++=*src++;
)

WILL work correctly for LZ77.

memcpy provided by gcc is optimized - it NOT copies byte-by-byte from beginning till end.

If you mediate over lz77 decompress algo (dlls/kernel/lzexpand.c) the things will be clean.



More information about the wine-devel mailing list