From: Enzo Matsumiya <ematsumiya@suse.de>
To: linux-cifs@vger.kernel.org
Cc: smfrench@gmail.com, pc@manguebit.com, ronniesahlberg@gmail.com,
sprasad@microsoft.com, tom@talpey.com, bharathsm@microsoft.com,
henrique.carvalho@suse.com
Subject: [PATCH 6/8] smb: client: compress: add code docs to lz77.c
Date: Mon, 13 Apr 2026 16:07:11 -0300 [thread overview]
Message-ID: <20260413190713.283939-6-ematsumiya@suse.de> (raw)
In-Reply-To: <20260413190713.283939-1-ematsumiya@suse.de>
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>
---
fs/smb/client/compress/lz77.c | 81 +++++++++++++++++++++++++++++++----
1 file changed, 73 insertions(+), 8 deletions(-)
diff --git a/fs/smb/client/compress/lz77.c b/fs/smb/client/compress/lz77.c
index 96744f52e364..7365d0f97396 100644
--- a/fs/smb/client/compress/lz77.c
+++ b/fs/smb/client/compress/lz77.c
@@ -15,6 +15,20 @@
/*
* Compression parameters.
+ *
+ * LZ77_MATCH_MAX_DIST: Farthest back a match can be from current position (can be 1 - 8K).
+ * LZ77_HASH_LOG:
+ * LZ77_HASH_SIZE: ilog2 hash size (recommended to be 13 - 18, default 15 (hash size
+ * 32k)).
+ * LZ77_RSTEP_SIZE: Number of bytes to read from input buffer for hashing and initial
+ * match check (default 4 bytes, this effectivelly makes this the min
+ * match len).
+ * LZ77_MSTEP_SIZE: Number of bytes to extend-compare a found match (default 8 bytes).
+ * LZ77_SKIP_TRIGGER: ilog2 value for adaptive skipping, i.e. to progressively skip input
+ * bytes when we can't find matches. Default is 4.
+ * Higher values (>0) will decrease compression time, but will result
+ * in worse compression ratio. Lower values will give better
+ * compression ratio (more matches found), but will increase time.
*/
#define LZ77_MATCH_MAX_DIST SZ_8K
#define LZ77_HASH_LOG 15
@@ -86,6 +100,19 @@ static __always_inline u32 lz77_match_len(const void *match, const void *cur, co
return (cur - start);
}
+/**
+ * lz77_encode_match() - Match encoding.
+ * @dst: compressed buffer
+ * @nib: pointer to an address in @dst
+ * @dist: match distance
+ * @len: match length
+ *
+ * Assumes all args were previously checked.
+ *
+ * Return: @dst advanced to new position
+ *
+ * Ref: MS-XCA 2.3.4 "Plain LZ77 Compression Algorithm Details" - "Processing"
+ */
static __always_inline void *lz77_encode_match(void *dst, void **nib, u16 dist, u32 len)
{
len -= 3;
@@ -95,12 +122,12 @@ static __always_inline void *lz77_encode_match(void *dst, void **nib, u16 dist,
if (len < 7) {
lz77_write16(dst, dist + len);
- return dst + 2;
+ return dst + sizeof(u16);
}
dist |= 7;
lz77_write16(dst, dist);
- dst += 2;
+ dst += sizeof(u16);
len -= 7;
if (!*nib) {
@@ -130,16 +157,32 @@ static __always_inline void *lz77_encode_match(void *dst, void **nib, u16 dist,
if (len <= 0xffff) {
lz77_write16(dst, len);
- return dst + 2;
+ return dst + sizeof(u16);
}
lz77_write16(dst, 0);
- dst += 2;
+ dst += sizeof(u16);
lz77_write32(dst, len);
- return dst + 4;
+ return dst + sizeof(u32);
}
+/**
+ * lz77_encode_literals() - Literals encoding.
+ * @start: where to start copying literals (uncompressed buffer)
+ * @end: when to stop copying (uncompressed buffer)
+ * @dst: compressed buffer
+ * @f: pointer to current flag value
+ * @fc: pointer to current flag count
+ * @fp: pointer to current flag address
+ *
+ * Batch copy literals from @start to @dst, updating flag values accordingly.
+ * Assumes all args were previously checked.
+ *
+ * Return: @dst advanced to new position
+ *
+ * MS-XCA 2.3.4 "Plain LZ77 Compression Algorithm Details" - "Processing"
+ */
static __always_inline void *lz77_encode_literals(const void *start, const void *end, void *dst,
long *f, u32 *fc, void **fp)
{
@@ -160,7 +203,7 @@ static __always_inline void *lz77_encode_literals(const void *start, const void
lz77_write32(*fp, *f);
*fc = 0;
*fp = dst;
- dst += 4;
+ dst += sizeof(u32);
}
} while (start < end);
@@ -188,7 +231,7 @@ noinline int lz77_compress(const void *src, const u32 slen, void *dst, u32 *dlen
rlim = end - LZ77_MSTEP_SIZE; /* read limit (for lz77_match_len()) */
dstp = dst;
flag_pos = dstp;
- dstp += 4;
+ dstp += sizeof(u32);
nib = NULL;
htable = kvcalloc(LZ77_HASH_SIZE, sizeof(*htable), GFP_KERNEL);
@@ -197,6 +240,10 @@ noinline int lz77_compress(const void *src, const u32 slen, void *dst, u32 *dlen
LZ77_PREFETCH(srcp + LZ77_RSTEP_SIZE);
+ /*
+ * Adjust @srcp so we don't get a false positive match on first iteration.
+ * Then prepare hash for first loop iteration (don't advance @srcp again).
+ */
hash = lz77_hash(lz77_read32(srcp++));
htable[hash] = 0;
hash = lz77_hash(lz77_read32(srcp));
@@ -219,6 +266,14 @@ noinline int lz77_compress(const void *src, const u32 slen, void *dst, u32 *dlen
srcp = next;
next += step;
+
+ /*
+ * Adaptive skipping.
+ *
+ * Increment @step every (1 << LZ77_SKIP_TRIGGER, 16 in our case) bytes
+ * without a match.
+ * Reset to 1 when a match is found.
+ */
step = (skip++ >> LZ77_SKIP_TRIGGER);
if (unlikely(next > rlim))
goto out;
@@ -229,6 +284,16 @@ noinline int lz77_compress(const void *src, const u32 slen, void *dst, u32 *dlen
} while (likely(match + LZ77_MATCH_MAX_DIST < srcp) ||
lz77_read32(match) != lz77_read32(srcp));
+ /*
+ * Match found. Warm/cold path; begin parsing @srcp and writing to @dstp:
+ * - flush literals
+ * - compute match length (*)
+ * - encode match
+ *
+ * (*) Current minimum match length is defined by the memory read size above, so
+ * here we already know that we have 4 matching bytes, but it's just faster to
+ * redundantly compute it again in lz77_match_len() than to adjust pointers/len.
+ */
dstp = lz77_encode_literals(anchor, srcp, dstp, &flag, &flag_count, &flag_pos);
len = lz77_match_len(match, srcp, end);
dstp = lz77_encode_match(dstp, &nib, srcp - match, len);
@@ -243,7 +308,7 @@ noinline int lz77_compress(const void *src, const u32 slen, void *dst, u32 *dlen
lz77_write32(flag_pos, flag);
flag_count = 0;
flag_pos = dstp;
- dstp += 4;
+ dstp += sizeof(u32);
}
if (unlikely(srcp > rlim))
--
2.53.0
next prev parent reply other threads:[~2026-04-13 19:08 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-04-13 19:07 [PATCH 1/8] smb: client: compress: fix buffer overrun in lz77_compress() Enzo Matsumiya
2026-04-13 19:07 ` [PATCH 2/8] smb: client: compress: fix bad encoding on last LZ77 flag Enzo Matsumiya
2026-04-19 1:35 ` Steve French
2026-04-13 19:07 ` [PATCH 3/8] smb: client: compress: fix counting in LZ77 match finding Enzo Matsumiya
2026-04-13 19:07 ` [PATCH 4/8] smb: client: compress: increase LZ77_MATCH_MAX_DIST Enzo Matsumiya
2026-04-13 19:07 ` [PATCH 5/8] smb: client: compress: LZ77 optimizations Enzo Matsumiya
2026-04-13 19:07 ` Enzo Matsumiya [this message]
2026-04-13 19:07 ` [PATCH 7/8] smb: client: compress: add compress/common.h Enzo Matsumiya
2026-04-20 21:24 ` Nathan Chancellor
2026-04-20 21:31 ` Steve French
2026-04-13 19:07 ` [PATCH 8/8] smb: common: add SMB3_COMPRESS_MAX_ALGS Enzo Matsumiya
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20260413190713.283939-6-ematsumiya@suse.de \
--to=ematsumiya@suse.de \
--cc=bharathsm@microsoft.com \
--cc=henrique.carvalho@suse.com \
--cc=linux-cifs@vger.kernel.org \
--cc=pc@manguebit.com \
--cc=ronniesahlberg@gmail.com \
--cc=smfrench@gmail.com \
--cc=sprasad@microsoft.com \
--cc=tom@talpey.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).