winhelp: bug fix in LZ77 decompressor
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:
>> When we say 'memmove(1, 0, 2)' we will get:
>> But we (LZ77 algorithm) expect:
>> XXX (three 'X').
>> memcpy is rather clever (it optmizes process by coping INT instead of
>> BYTES). This optimization is fatal for LZ77.
> 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