commit b4eda8d08f307dfc3cbd0d06baea4e6c581b70de
author Alexey Tourbin <alexey.tourbin@gmail.com> Mon Apr 23 08:37:44 2018 +0300
committer Alexey Tourbin <alexey.tourbin@gmail.com> Wed Apr 25 13:18:06 2018 +0300
tree 4f983e141b3c3651580272408d394161ad19f244
parent 62d7cdcc741480842a0c217df7cb26ad3946ab32

lz4.c: refactor the decoding routines

I noticed that LZ4_decompress_generic is sometimes instantiated with
identical set of parameters, or (what's worse) with a subtly different
sets of parameters.  For example, LZ4_decompress_fast_withPrefix64k is
instantiated as follows:

    return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize,
		full, 0, withPrefix64k, (BYTE*)dest - 64 KB, NULL, 64 KB);

while the equivalent withPrefix64k call in LZ4_decompress_usingDict_generic
passes 0 for the last argument instead of 64 KB.  It turns out that there
is no difference in this case: if you change 64 KB to 0 KB in
LZ4_decompress_fast_withPrefix64k, you get the same binary code.

Moreover, because it's been clarified that LZ4_decompress_fast doesn't
check match offsets, it is now obvious that both of these fast/withPrefix64k
instantiations are simply redundant.  Exactly because LZ4_decompress_fast
doesn't check offsets, it serves well with any prefixed dictionary.

There's a difference, though, with LZ4_decompress_safe_withPrefix64k.
It also passes 64 KB as the last argument, and if you change that to 0,
as in LZ4_decompress_usingDict_generic, you get a completely different
binary code.  It seems that passing 0 enables offset checking:

    const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB)));

However, the resulting code seems to run a bit faster.  How come
enabling extra checks can make the code run faster?  Curiouser and
curiouser!  This needs extra study.  Currently I take the view that
the dictSize should be set to non-zero when nothing else will do,
i.e. when passing the external dictionary via dictStart.  Otherwise,
lowPrefix betrays just enough information about the dictionary.

    * * *

Anyway, with this change, I instantiate all the necessary cases as
functions with distinctive names, which also take fewer arguments and
are therefore less error-prone.  I also make the functions non-inline.
(The compiler won't inline the functions because they are used more than
once.  Hence I attach LZ4_FORCE_O2_GCC_PPC64LE to the instances while
removing from the callers.)  The number of instances is now is reduced
from 18 (safe+fast+partial+4*continue+4*prefix+4*dict+2*prefix64+forceExtDict)
down to 7 (safe+fast+partial+2*prefix+2*dict).  The size of the code is
not the only issue here.  Separate helper function are much more
amenable to profile-guided optimization: it is enough to profile only
a few basic functions, while the other less-often used functions, such
as LZ4_decompress_*_continue, will benefit automatically.

This is the list of LZ4_decompress* functions in liblz4.so, sorted by size.
Exported functions are marked with a capital T.

$ nm -S lib/liblz4.so |grep -wi T |grep LZ4_decompress |sort -k2
0000000000016260 0000000000000005 T LZ4_decompress_fast_withPrefix64k
0000000000016dc0 0000000000000025 T LZ4_decompress_fast_usingDict
0000000000016d80 0000000000000040 T LZ4_decompress_safe_usingDict
0000000000016d10 000000000000006b T LZ4_decompress_fast_continue
0000000000016c70 000000000000009f T LZ4_decompress_safe_continue
00000000000156c0 000000000000059c T LZ4_decompress_fast
0000000000014a90 00000000000005fa T LZ4_decompress_safe
0000000000015c60 00000000000005fa T LZ4_decompress_safe_withPrefix64k
0000000000002280 00000000000005fa t LZ4_decompress_safe_withSmallPrefix
0000000000015090 000000000000062f T LZ4_decompress_safe_partial
0000000000002880 00000000000008ea t LZ4_decompress_fast_extDict
0000000000016270 0000000000000993 t LZ4_decompress_safe_forceExtDict