smb: client: compress: add code docs to lz77.c

Document parts of the code, especially the apparently
non-sense parts.

Other:
- change pointer increment constants to sizeof() values

Signed-off-by:

smb: client: compress: add code docs to lz77.c

Document parts of the code, especially the apparently
non-sense parts.

Other:
- change pointer increment constants to sizeof() values

Signed-off-by: Enzo Matsumiya <ematsumiya@suse.de>
Signed-off-by: Steve French <stfrench@microsoft.com>

show more ...

smb: client: compress: LZ77 optimizations

This patch implements several micro-optimizations on lz77_compress()
with the goal of reducing the number of instructions per [input]
byte (a.k.a. IPB).

Ch

smb: client: compress: LZ77 optimizations

This patch implements several micro-optimizations on lz77_compress()
with the goal of reducing the number of instructions per [input]
byte (a.k.a. IPB).

Changes:
- change hashtable to be u32 (instead of u64) -- change the hash
function to reflect that (adds lz77_hash() and lz77_read32() helpers)
- batch-write literals instead of 1 by 1 -- now that we have a well
defined hot path (match finding) and a cold path (encode literals +
match), batch writing makes a significant difference
- implement adaptive skipping of input bytes -- skip input bytes more
aggressively if too few matches are being found
- name some constants for more meaningful context

Signed-off-by: Enzo Matsumiya <ematsumiya@suse.de>
Signed-off-by: Steve French <stfrench@microsoft.com>

show more ...

smb: client: compress: increase LZ77_MATCH_MAX_DIST

Increase max distance (i.e. window size) from 1k to 8k.
This allows better compression and is just as fast.

Other:
- drop LZ77_MATCH_MIN_DIST as

smb: client: compress: increase LZ77_MATCH_MAX_DIST

Increase max distance (i.e. window size) from 1k to 8k.
This allows better compression and is just as fast.

Other:
- drop LZ77_MATCH_MIN_DIST as it's nused -- main loop
already checks if dist > 0

Signed-off-by: Enzo Matsumiya <ematsumiya@suse.de>
Signed-off-by: Steve French <stfrench@microsoft.com>

show more ...

smb: client: compress: fix counting in LZ77 match finding

- lz77_match_len() increments @cur before checking for equality,
leading to off-by-one match len in some cases.

Fix by moving pointers

smb: client: compress: fix counting in LZ77 match finding

- lz77_match_len() increments @cur before checking for equality,
leading to off-by-one match len in some cases.

Fix by moving pointers increment to inside the loop.
Also rename @wnd arg to @match (more accurate name).
- both lz77_match_len() and lz77_compress() checked for
"buf + step < end" when the correct is "<=" for such cases.

Signed-off-by: Enzo Matsumiya <ematsumiya@suse.de>
Signed-off-by: Steve French <stfrench@microsoft.com>

show more ...

smb: client: compress: fix buffer overrun in lz77_compress()

@dst buffer is allocated with same size as @src, which, for good
compression cases, works fine.

However, when compression goes bad (e.g.

smb: client: compress: fix buffer overrun in lz77_compress()

@dst buffer is allocated with same size as @src, which, for good
compression cases, works fine.

However, when compression goes bad (e.g. random bytes payloads), the
compressed size can increase significantly, and even by stopping the
main loop at 7/8 of @slen, writing leftover literals could write past
the end of @dst because of LZ77 metadata.

To fix this, add lz77_compressed_alloc_size() helper to compute the
correct allocation size for @dst, accounting for metadata and worst
cast scenario (all literals).

While this is overprovisioning memory, it's not only correct, but also
allows lz77_compress() main loop to run without ever checking @dst
limits (i.e. a perf improvement).

Signed-off-by: Enzo Matsumiya <ematsumiya@suse.de>
Signed-off-by: Steve French <stfrench@microsoft.com>

show more ...

smb: client: compress: fix bad encoding on last LZ77 flag

End-of-stream flag could lead to UB because of int promotion
(overwriting signed bit).

Fix it by changing operand from '1' to '1UL'.

Signe

smb: client: compress: fix bad encoding on last LZ77 flag

End-of-stream flag could lead to UB because of int promotion
(overwriting signed bit).

Fix it by changing operand from '1' to '1UL'.

Signed-off-by: Enzo Matsumiya <ematsumiya@suse.de>
Signed-off-by: Steve French <stfrench@microsoft.com>

show more ...