{

/// Match copies may overlap (src points into the already-decoded output).

/// When offset < 32, a 256-bit load reads bytes just written in the same

/// cache line, causing store-forwarding stalls. Two 128-bit copies halve

/// the stall window.

if constexpr (block_size == 32)

{

__builtin_memcpy(dst, src, 16);

__builtin_memcpy(dst + 16, src + 16, 16);

}

else

__builtin_memcpy(dst, src, block_size);

{

/// Unrolling with clang is doing >10% performance degrade on x86.

/// On ARM (Graviton 4) the pragma has no measurable effect.

size_t i = 0;

#pragma nounroll

do

{

__builtin_memcpy(dst, src, block_size);

dst += block_size;

src += block_size;

i += block_size;

} while (i < size);

{

/// Unrolling with clang is doing >10% performance degrade on x86.

/// On ARM (Graviton 4) the pragma has no measurable effect.

///

/// Same store-forwarding concern as `copyFromOutput`.

size_t i = 0;

#pragma nounroll

do

{

if constexpr (block_size == 32)

{

__builtin_memcpy(dst, src, 16);

__builtin_memcpy(dst + 16, src + 16, 16);

}

else

__builtin_memcpy(dst, src, block_size);

dst += block_size;

src += block_size;

i += block_size;

} while (i < size);

{

/// The inner dimension and the `pshufb` / `vqtbl1q_u8` shuffle it feeds are 16 bytes wide, so the

/// generated masks are only correct for a 16-byte copy. Only `boot_masks<16>` is ever used; guard

/// against a future `boot_masks<8>` / `<32>` silently getting wrong masks.

static_assert(copy_amount == 16, "BootMasks is only valid for a 16-byte copy amount");

alignas(16) UInt8 boot[copy_amount + 1][16];

UInt8 shift[copy_amount + 1];

constexpr BootMasks() : boot{}, shift{}

{

for (size_t idx = 1; idx <= copy_amount; ++idx)

{

for (size_t i = 0; i < 16; ++i)

boot[idx][i] = (idx == copy_amount) ? static_cast<UInt8>(i) : static_cast<UInt8>(i % idx);

shift[idx] = (idx == copy_amount)

? static_cast<UInt8>(copy_amount)

: static_cast<UInt8>((copy_amount % idx) ? (copy_amount % idx) : idx);

}

}

{

const UInt8 * ip = reinterpret_cast<const UInt8 *>(source);

UInt8 * op = reinterpret_cast<UInt8 *>(dest);

const UInt8 * const input_end = ip + source_size;

UInt8 * const output_begin = op;

UInt8 * const output_end = op + dest_size;

while (true)

{

size_t length = 0;

auto continue_read_length = [&]

{

unsigned s = 0;

do

{

s = *ip++;

length += s;

} while (unlikely(s == 255 && ip < input_end));

};

/// Get literal length.

if (unlikely(ip >= input_end))

return false;

const unsigned token = *ip++;

length = token >> 4;

UInt8 * copy_end = nullptr;

size_t real_length = 0;

/// It might be true fairly often for well-compressed columns.

/// ATST it may hurt performance in other cases because this condition is hard to predict (especially if the number of zeros is ~50%).

/// In such cases this `if` will significantly increase number of mispredicted instructions. But seems like it results in a

/// noticeable slowdown only for implementations with `copy_amount` > 8. Probably because they use havier instructions.

if constexpr (copy_amount == 8)

if (length == 0)

goto decompress_match;

if (length == 0x0F)

{

if (unlikely(ip + 1 >= input_end))

return false;

continue_read_length();

}

/// Copy literals.

copy_end = op + length;

/// input: Hello, world

/// ^-ip

/// output: xyz

/// ^-op ^-copy_end

/// output: xyzHello, w

/// ^- excessive copied bytes due to "wildCopy"

/// input: Hello, world

/// ^-ip

/// output: xyzHello, w

/// ^-op (we will overwrite excessive bytes on next iteration)

if (unlikely(copy_end > output_end))

return false;

// Due to implementation specifics the copy length is always a multiple of copy_amount

real_length = 0;

static_assert(copy_amount == 8 || copy_amount == 16 || copy_amount == 32);

if constexpr (copy_amount == 8)

real_length = (((length >> 3) + 1) * 8);

else if constexpr (copy_amount == 16)

real_length = (((length >> 4) + 1) * 16);

else if constexpr (copy_amount == 32)

real_length = (((length >> 5) + 1) * 32);

if (unlikely(ip + real_length >= input_end + ADDITIONAL_BYTES_AT_END_OF_BUFFER))

return false;

wildCopyFromInput<copy_amount>(op, ip, copy_end - op); /// Here we can write up to copy_amount - 1 bytes after buffer.

if (copy_end == output_end)

return true;

ip += length;

op = copy_end;

decompress_match:

if (unlikely(ip + 1 >= input_end))

return false;

/// Get match offset.

const size_t offset = LZ4_readLE16(ip);

ip += 2;

/// Reject a zero offset (invalid in LZ4 — the minimum match distance is 1) together with an

/// offset that reaches before the start of the output, in a single unsigned comparison that

/// adds no branch to the hot loop. For any `offset >= 1` this is exactly `match < output_begin`

/// (`match = op - offset`); for `offset == 0`, `offset - 1` wraps to `SIZE_MAX` and also fails,

/// so the overlap copy can no longer synthesize output from the destination and wrongly report

/// success. We fail closed here (the reference decoder is more lenient and returns garbage).

/// The check is done before forming `match`, so `op - offset` is never computed for a malformed

/// offset that would point before `output_begin` (which would be out-of-range pointer arithmetic).

const size_t produced = static_cast<size_t>(op - output_begin);

if (unlikely(offset - 1 >= produced))

return false;

UInt8 * match = op - offset;

/// Get match length.

length = token & 0x0F;

if (length == 0x0F)

{

if (unlikely(ip + 1 >= input_end))

return false;

continue_read_length();

}

length += 4;

/// Copy match within block, that produce overlapping pattern. Match may replicate itself.

copy_end = op + length;

if (unlikely(copy_end > output_end))

return false;

/** Here we can write up to copy_amount - 1 - 4 * 2 bytes after buffer.

#if defined(__SSSE3__) || (defined(__aarch64__) && defined(__ARM_NEON))

if constexpr (branchless && copy_amount == 16)

/// Unconditional branchless overlap copy: clamp the index here (one `cmov`) so that

/// `copyOverlap<16>` selects the identity shuffle for offset >= 16, dropping the

/// highly mispredicted `offset < 16` branch.

copyOverlap<copy_amount>(op, match, offset < copy_amount ? offset : copy_amount);

else if (offset < copy_amount)

#else

if (offset < copy_amount)

#endif

{

/// output: Hello

/// ^-op

/// ^-match; offset = 5

///

/// output: Hello

/// [------] - copy_amount bytes

/// [------] - copy them here

///

/// output: HelloHelloHel

/// ^-match ^-op

copyOverlap<copy_amount>(op, match, offset);

}

else

{

copyFromOutput<copy_amount>(op, match);

match += copy_amount;

}

op += copy_amount;

copyFromOutput<copy_amount>(op, match); /// copy_amount + copy_amount - 1 - 4 * 2 bytes after buffer.

if (length > copy_amount * 2)

{

if (unlikely(copy_end > output_end))

return false;

wildCopyFromOutput<copy_amount>(op + copy_amount, match + copy_amount, copy_end - (op + copy_amount));

}

op = copy_end;

}

const char * const source,

char * const dest,

size_t source_size,

size_t dest_size,

[[maybe_unused]] PerformanceStatistics & statistics)

{

if (dest_size == 0)

return true;

/// There is nothing to decompress from, but the caller expects `dest_size` bytes to be written,

/// and would otherwise hand out the previous contents of the destination buffer.

if (source_size == 0)

return false;

/// When a specific method is forced, always use it regardless of block size.

/// The size threshold below only applies to the adaptive bandit algorithm

/// where timing very small blocks would add too much noise.

if (statistics.choose_method >= 0 || dest_size >= 32768)

{

size_t variant_size = PerformanceStatistics::NUM_ELEMENTS;

size_t best_variant = statistics.select(variant_size);

Stopwatch watch;

bool success = false;

if (best_variant == 0)

success = decompressImpl<8>(source, dest, source_size, dest_size);

else if (best_variant == 1)

success = decompressImpl<16, true>(source, dest, source_size, dest_size);

else

success = decompressImpl<32>(source, dest, source_size, dest_size);

watch.stop();

statistics.data[best_variant].update(watch.elapsedSeconds(), static_cast<double>(dest_size)); // NOLINT(clang-analyzer-security.ArrayBound)

return success;

}

/// For small blocks (< 32 KiB), skip the bandit and always use variant 0 (8-byte copies).

/// Timing such small blocks would add too much noise to the bandit's statistics.

/// Variant 0 is the right default here: it has the lowest per-iteration overhead

/// and wins the majority of files (57% on test.hits), especially smaller ones.

/// Note: the exact threshold value is not performance-sensitive. On test.hits columns

/// (AMD 7950X3D), sweeping it from 0 to 32K changes the oracle total by only 0.003%,

/// because variant 0 is available in the bandit anyway and would be selected for

/// the same files. The threshold is purely a noise-reduction measure.

return decompressImpl<8>(source, dest, source_size, dest_size);