winhelp: bug fix in LZ77 decompressor

HolyLich lich at
Tue Aug 8 09:03:06 CDT 2006

On Tue, 8 Aug 2006 09:37:09 -0400, Kuba Ober <kuba at> 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