Lz4: Compress error

Created on 11 Jun 2019 · 3Comments · Source: lz4/lz4

We are porting lz4 to IOS. For some data, the compressed data can't be decompressing.
After some digging, We found below code:
/* Catch up */ while (((ip>anchor) & (match > lowLimit)) && (unlikely(ip[-1]==match[-1]))) { ip--; match--; }
The match is the first byte in the input buffer for our case. So match[-1] give incorrect result.
Beside, I do not understand why '&' used in first statement instead of '&&'.

question

Source

felix2ch

All 3 comments

Hi!

Some invariants that should be in effect when this loop is called:

anchor >= source
There are four possible buffer layouts:
- dictDirective == usingDictCtx:
- match can be in [dictionary, dictEnd): lowLimit is dictionary (ref).
- match can be in [source, ip): lowLimit is source (ref).
- dictDirective == usingExtDict:
- match can be in [dictionary, dictEnd): lowLimit is dictionary (ref).
- match can be in [source, ip): lowLimit is source (ref).
- dictDirective == withPrefix64k:
- match is in [source - dictSize, ip): lowLimit is source - dictSize (ref).
- dictDirective == noDict:
- match is in [source, ip): lowLimit is source (ref).

In all of these cases lowLimit points to the first valid byte of the buffer that match is in. This means that the first two conditions in the loop test, ip>anchor and match>lowLimit, check that the current input position (ip) and match position (match) are past the first byte in their respective buffers. Only if those tests pass do the subsequent accesses ip[-1] and match[-1] happen. They are therefore guaranteed to be valid.

To your second question: we use a bitwise and for the first two tests because && is lazy, and will not execute the right-hand argument if the left-hand argument is false (which is precisely the property we rely on to protect the [-1] accesses). Whereas & is not lazy, both arguments are always evaluated. It can seem like & does more work than && and is therefore less efficient, but in fact the independence of evaluating the two operands allows both tests to proceed in parallel, exploiting CPU instruction-level parallelism, whereas the lazy logical and (&&) has to finish evaluating the left-hand operand before deciding whether to proceed and evaluate the right-hand operand. See for example https://godbolt.org/z/OrWVos. This results in lower parallelism and two branches instead of one, which is harder for the CPU to predict. It turns out that changes the & to a && can meaningfully slow down LZ4!