path: root/fs/smb/client/compress/lz77.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 * Copyright (C) 2024, SUSE LLC
 *
 * Authors: Enzo Matsumiya <ematsumiya@suse.de>
 *
 * Implementation of the LZ77 "plain" compression algorithm, as per MS-XCA spec.
 */
#include <linux/prefetch.h>
#include <linux/slab.h>
#include <linux/sizes.h>
#include <linux/count_zeros.h>
#include <asm/unaligned.h>

#include "lz77.h"

#ifdef CONFIG_CIFS_DEBUG2
# define LZ77_STATS_ENABLED
#endif

/*
 * Compression parameters.
 *
 * - finding closer and smaller matches is faster, but also compresses worse, e.g.
 *   match min len = 3, max dist = 1K compared to match min len = 8, max dist = 8K:
 *   the former is ~10% faster, but yields a ~5% bigger output
 * - we don't really care about a maximum match length -- it's simply much, much faster to compute
 *   a very long match length (e.g. 2M) and write only its encoded bytes than to write e.g. 500K
 *   of literals
 */
#define LZ77_MATCH_MIN_LEN	3
#define LZ77_MATCH_MAX_LEN	S32_MAX
#define LZ77_MATCH_MIN_DIST	1
#define LZ77_MATCH_MAX_DIST	SZ_1K
#define LZ77_HASH_LOG		15
#define LZ77_HASH_SIZE		(1 << LZ77_HASH_LOG)

#define lz77_read(nbits, _ptr)		get_unaligned((const u ## nbits *)(_ptr))
#define lz77_write(nbits, _ptr, _v)	put_unaligned_le ## nbits((_v), (typeof((_v)) *)(_ptr))

static __always_inline u16 lz77_read16(const u8 *ptr)
{
	return lz77_read(16, ptr);
}

static __always_inline u32 lz77_read32(const u8 *ptr)
{
	return lz77_read(32, ptr);
}

static __always_inline u64 lz77_read64(const u8 *ptr)
{
	return lz77_read(64, ptr);
}

static __always_inline void lz77_write8(u8 *ptr, u8 v)
{
	put_unaligned(v, ptr);
}

static __always_inline void lz77_write16(u8 *ptr, u16 v)
{
	lz77_write(16, ptr, v);
}

static __always_inline void lz77_write32(u8 *ptr, u32 v)
{
	lz77_write(32, ptr, v);
}

static __always_inline u64 lz77_hash_bytes(const u8 *ptr)
{
	/* A "hash function" -- simple, fast, and enough for our use-case. */
	return ((lz77_read64(ptr) << 24) * 889523592379ULL) >> (64 - LZ77_HASH_LOG);
}

/*
 * Count common bytes in @diff, where @diff is:
 *	(*(u64 *)bufA ^ *(u64)bufB)
 */
static __always_inline u32 lz77_count_common_bytes(const u64 diff)
{
	return count_trailing_zeros(diff) >> 3;
}

static __always_inline u32 lz77_match_len(const u8 *wnd, const u8 *cur, const u8 *end)
{
	const u8 *start = cur;
	const u32 step = sizeof(u64);
	u64 diff = lz77_read32(cur) ^ lz77_read32(wnd);

	if (diff)
		return 0;

	cur += sizeof(u32);
	wnd += sizeof(u32);

	if (cur + sizeof(u64) >= end)
		return (cur - start);

	while (likely(cur + step < end)) {
		diff = lz77_read64(cur) ^ lz77_read64(wnd);
		if (!diff) {
			cur += step;
			wnd += step;

			continue;
		}

		cur += lz77_count_common_bytes(diff);

		return (cur - start);
	}

	while (cur < end && *cur++ == *wnd++) { }

	return (cur - start);
}

static __always_inline u8 *lz77_write_match(u8 *dst, u8 **nib, u32 dist, u32 len)
{
	len -= 3;
	dist--;
	dist <<= 3;

	if (len < 7) {
		lz77_write16(dst, dist + len);

		return dst + 2;
	}

	dist |= 7;
	lz77_write16(dst, dist);
	dst += 2;
	len -= 7;

	if (!*nib) {
		lz77_write8(dst, umin(len, 15));
		*nib = dst;
		dst++;
	} else {
		**nib |= umin(len, 15) << 4;
		*nib = NULL;
	}

	if (len < 15)
		return dst;

	len -= 15;
	if (len < 255) {
		lz77_write8(dst, len);

		return dst + 1;
	}

	lz77_write8(dst, 0xff);
	dst++;
	len += 7 + 15;

	if (len <= 0xffff) {
		lz77_write16(dst, len);

		return dst + 2;
	}

	lz77_write16(dst, 0);
	dst += 2;
	lz77_write32(dst, len);

	return dst + 4;
}

static __always_inline void lz77_copy(u8 *dst, const u8 *src, size_t count)
{
	while (count > 8) {
		*(u64 *)dst = *(u64 *)src;
		count -= 8;
		src += 8;
		dst += 8;
	}

	while (count > 4) {
		*(u32 *)dst = *(u32 *)src;
		count -= 4;
		src += 4;
		dst += 4;
	}

	if (count)
		memcpy(dst, src, count);
}

noinline int lz77_compress(const u8 *src, u32 slen, u8 *dst, u32 *dlen)
{
	const u8 *srcp, *end;
	u8 *dstp, *nib, *flag_pos;
	u32 flag_count = 0;
	u64 *htable;
	long flag = 0;
	int i;
	unsigned long s, e;

	srcp = src;
	end = src + slen;

	dstp = dst;
	nib = NULL;
	flag_pos = dstp;
	dstp += 4;

	htable = kvcalloc(LZ77_HASH_SIZE, sizeof(*htable), GFP_KERNEL);
	if (!htable)
		return -ENOMEM;

	s = jiffies;

	for (i = 0; i < LZ77_MATCH_MIN_LEN; i++) {
		u64 hash = lz77_hash_bytes(srcp); 

		htable[hash] = i;
		*dstp++ = *srcp++;
		flag_count++;
	}

	/* Main loop. */
	do {
		u64 hash = lz77_hash_bytes(srcp);
		u32 offset = srcp - src;
		u32 dist = offset - htable[hash];
		u32 len = 0;

		/*
		 * Perf note:
		 * It's faster to compare (src + htable[hash]) when htable[hash] == 0 in
		 * lz77_match_len() than to add a check here.
		 */
		dist = offset - htable[hash];
		if (dist >= LZ77_MATCH_MIN_DIST && dist < LZ77_MATCH_MAX_DIST)
			len = lz77_match_len(src + htable[hash], srcp, end);

		htable[hash] = offset;

		if (len < LZ77_MATCH_MIN_LEN) {
			/*
			 * Perf note:
			 * It's faster to simply copy the literal byte than to accumulate it and
			 * write them in 32-byte chunks.
			 */
			lz77_write8(dstp++, *srcp++);
			flag <<= 1;
			flag_count++;
			if (flag_count == 32) {
				lz77_write32(flag_pos, flag);
				flag_count = 0;
				flag_pos = dstp;
				dstp += 4;
			}

			continue;
		}

		dstp = lz77_write_match(dstp, &nib, dist, len);
		srcp += len;

		flag = (flag << 1) | 1;
		flag_count++;
		if (flag_count == 32) {
			lz77_write32(flag_pos, flag);
			flag_count = 0;
			flag_pos = dstp;
			dstp += 4;
		}
	} while (likely(srcp + sizeof(u64) < end));

	//pr_err("%s: leftovers %zu, flag count %u\n", __func__, end - srcp, flag_count);
	while (srcp < end) {
		u32 c;

		if (unlikely((dstp - dst) + (end - srcp) > slen)) {
			*dlen = slen;
			goto out;
		}

		c = umin(end - srcp, 32 - flag_count);

		lz77_copy(dstp, srcp, c);

		dstp += c;
		srcp += c;

		flag <<= c;
		flag_count += c;
		if (flag_count == 32) {
			lz77_write32(flag_pos, flag);
			flag_count = 0;
			flag_pos = dstp;
			dstp += 4;
		}
	}

	kvfree(htable);

	flag <<= (32 - flag_count);
	flag |= (1 << (32 - flag_count)) - 1;
	lz77_write32(flag_pos, flag);

	*dlen = dstp - (u8 *)dst;
out:

	e = jiffies;
	pr_err("%s: (fast) took %ums to compress (slen=%u, dlen=%u)\n", __func__, jiffies_to_msecs(e - s), slen, *dlen);

	if (*dlen < slen)
		return 0;

	return -EMSGSIZE;
}