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

// SPDX-License-Identifier: GPL-2.0-only
/*
 * Copyright (C) 2024, SUSE LLC
 *
 * Authors: Enzo Matsumiya <ematsumiya@suse.de>
 *
 * This file implements I/O compression support for SMB2 messages (SMB 3.1.1 only).
 * See compress/ for implementation details of each algorithm.
 *
 * References:
 * MS-SMB2 "3.1.4.4 Compressing the Message"
 * MS-SMB2 "3.1.5.3 Decompressing the Chained Message"
 * MS-XCA - for details of the supported algorithms
 */
#include <linux/slab.h>
#include <linux/kernel.h>
#include <linux/uio.h>

#include "../common/smb2pdu.h"
#include "cifsglob.h"
#include "cifs_debug.h"

#include "compress/lz77.h"
#include "compress.h"

#define SAMPLING_READ_SIZE	(16)
#define SAMPLING_INTERVAL	(256)
#define BUCKET_SIZE		(256)
/*
 * The size of the sample is based on a statistical sampling rule of thumb.
 * The common way is to perform sampling tests as long as the number of
 * elements in each cell is at least 5.
 *
 * Instead of 5, we choose 32 to obtain more accurate results.
 * If the data contain the maximum number of symbols, which is 256, we obtain a
 * sample size bound by 8192.
 *
 * For a sample of at most 8KB of data per data range: 16 consecutive bytes
 * from up to 512 locations.
 */
#define MAX_SAMPLE_SIZE		(8192 * SAMPLING_READ_SIZE / SAMPLING_INTERVAL)
//				  ^ == LZ77 window size

struct bucket_item {
	size_t count;
};

struct heuristic_ctx {
	/* Partial copy of input data */
	const u8 *sample;
	size_t sample_size;

	/* Buckets store counters for each byte value
	 *
	 * For statistical analysis of the input data we consider bytes that form a
	 * Galois Field of 256 objects. Each object has an attribute count, ie. how
	 * many times the object appeared in the sample.
	 */
	struct bucket_item bucket[BUCKET_SIZE];
	struct bucket_item aux_bucket[BUCKET_SIZE];

	struct list_head list;
};

/*
 * Shannon Entropy calculation.
 *
 * Pure byte distribution analysis fails to determine compressibility of data.
 * Try calculating entropy to estimate the average minimum number of bits
 * needed to encode the sampled data.
 *
 * For convenience, return the percentage of needed bits, instead of amount of
 * bits directly.
 *
 * @ENTROPY_LEVEL_OK - below that threshold, sample has low byte entropy
 *		       and can be compressible with high probability
 *
 * @ENTROPY_LEVEL_HIGH - data are not compressible with high probability
 *
 * Use of ilog2() decreases precision, we lower the LVL to 5 to compensate.
 */
#define ENTROPY_LEVEL_OK 65
#define ENTROPY_LEVEL_HIGH 80

/*
 * For increasead precision in shannon_entropy calculation,
 * let's do pow(n, M) to save more digits after comma:
 *
 * - maximum int bit length is 64
 * - ilog2(MAX_SAMPLE_SIZE) -> 13
 * - 13 * 4 = 52 < 64 -> M = 4
 *
 * So use pow(n, 4).
 */
static inline u32 ilog2_w(u64 n)
{
	return ilog2(n * n * n * n);
}

static u32 shannon_entropy(struct heuristic_ctx *ctx)
{
	const size_t max = 8 * ilog2_w(2);
	size_t i, p, p_base, sz_base, sum = 0;

	sz_base = ilog2_w(ctx->sample_size);

	for (i = 0; i < 256 && ctx->bucket[i].count > 0; i++) {
		p = ctx->bucket[i].count;
		p_base = ilog2_w(p);
		sum += p * (sz_base - p_base);
	}

	sum /= ctx->sample_size;

	return sum * 100 / max;
}

#define RADIX_BASE 4U
#define COUNTERS_SIZE (1U << RADIX_BASE)

static __always_inline u8 get4bits(u64 num, int shift)
{
	/* Reverse order */
	return ((COUNTERS_SIZE - 1) - ((num >> shift) % COUNTERS_SIZE));
}

/*
 * Use 4 bits as radix base
 * Use 16 u32 counters for calculating new position in buf array
 *
 * @array     - array that will be sorted
 * @aux	      - buffer array to store sorting results
 *              must be equal in size to @array
 * @num       - array size
 */
static void radix_sort(struct bucket_item *array, struct bucket_item *aux, int num)
{
	size_t buf_num, max_num, addr, new_addr, counters[COUNTERS_SIZE];
	int bitlen, shift, i;

	/*
	 * Try avoid useless loop iterations for small numbers stored in big
	 * counters.  Example: 48 33 4 ... in 64bit array
	 */
	max_num = array[0].count;
	for (i = 1; i < num; i++) {
		buf_num = array[i].count;

		if (buf_num > max_num)
			max_num = buf_num;
	}

	buf_num = ilog2(max_num);
	bitlen = ALIGN(buf_num, RADIX_BASE * 2);

	shift = 0;
	while (shift < bitlen) {
		memset(counters, 0, sizeof(counters));

		for (i = 0; i < num; i++) {
			buf_num = array[i].count;
			addr = get4bits(buf_num, shift);
			counters[addr]++;
		}

		for (i = 1; i < COUNTERS_SIZE; i++)
			counters[i] += counters[i - 1];

		for (i = num - 1; i >= 0; i--) {
			buf_num = array[i].count;
			addr = get4bits(buf_num, shift);
			counters[addr]--;
			new_addr = counters[addr];
			aux[new_addr] = array[i];
		}

		shift += RADIX_BASE;

		/*
		 * Normal radix expects to move data from a temporary array, to
		 * the main one.  But that requires some CPU time. Avoid that
		 * by doing another sort iteration to original array instead of
		 * memcpy()
		 */
		memset(counters, 0, sizeof(counters));

		for (i = 0; i < num; i ++) {
			buf_num = aux[i].count;
			addr = get4bits(buf_num, shift);
			counters[addr]++;
		}

		for (i = 1; i < COUNTERS_SIZE; i++)
			counters[i] += counters[i - 1];

		for (i = num - 1; i >= 0; i--) {
			buf_num = aux[i].count;
			addr = get4bits(buf_num, shift);
			counters[addr]--;
			new_addr = counters[addr];
			array[new_addr] = aux[i];
		}

		shift += RADIX_BASE;
	}
}

/*
 * Count how many bytes cover 90% of the sample.
 *
 * There are several types of structured binary data that use nearly all byte
 * values. The distribution can be uniform and counts in all buckets will be
 * nearly the same (eg. encrypted data). Unlikely to be compressible.
 *
 * Other possibility is normal (Gaussian) distribution, where the data could
 * be potentially compressible, but we have to take a few more steps to decide
 * how much.
 *
 * @BYTE_COVERAGE_LOW  - main part of byte values repeated frequently,
 *		      compression algo can easy fix that
 * @BYTE_COVERAGE_HIGH - data have uniform distribution and with high
 *                    probability is not compressible
 */
#define BYTE_COVERAGE_LOW 64
#define BYTE_COVERAGE_HIGH	200

static int byte_coverage(struct heuristic_ctx *ctx)
{
	const size_t threshold = ctx->sample_size * 90 / 100;
	struct bucket_item *bkt = &ctx->bucket[0];
	size_t sum = 0;
	int i;

	/* Sort in reverse order */
	radix_sort(ctx->bucket, ctx->aux_bucket, BUCKET_SIZE);

	for (i = 0; i < BYTE_COVERAGE_LOW; i++)
		sum += bkt[i].count;

	if (sum > threshold)
		return i;

	for (; i < BYTE_COVERAGE_HIGH && bkt[i].count > 0; i++) {
		sum += bkt[i].count;
		if (sum > threshold)
			break;
	}

	return i;
}

/*
 * Count ASCII bytes in buckets.
 *
 * This heuristic can detect textual data (configs, xml, json, html, etc).
 * Because in most text-like data byte set is restricted to limited number of
 * possible characters, and that restriction in most cases makes data easy to
 * compress.
 *
 * @ASCII_COUNT_THRESHOLD - consider all data within this byte set size:
 *	less - compressible
 *	more - need additional analysis
 */
#define ASCII_COUNT_THRESHOLD 64

static __always_inline u32 ascii_count(const struct heuristic_ctx *ctx)
{
	size_t count = 0;
	int i;

	for (i = 0; i < ASCII_COUNT_THRESHOLD; i++)
		if (ctx->bucket[i].count > 0)
			count++;

	/*
	 * Continue collecting count of byte values in buckets.  If the byte
	 * set size is bigger then the threshold, it's pointless to continue,
	 * the detection technique would fail for this type of data.
	 */
	for (; i < 256; i++) {
		if (ctx->bucket[i].count > 0) {
			count++;
			if (count > ASCII_COUNT_THRESHOLD)
				break;
		}
	}

	return count;
}

static __always_inline struct heuristic_ctx *heuristic_init(const u8 *buf, size_t len)
{
	struct heuristic_ctx *ctx = kzalloc(sizeof(*ctx), GFP_KERNEL);
	int i = 0, s = 0;

	if (!ctx)
		return ERR_PTR(-ENOMEM);

	ctx->sample = kzalloc(MAX_SAMPLE_SIZE, GFP_KERNEL);
	if (!ctx->sample) {
		kfree(ctx);
		return ERR_PTR(-ENOMEM);
	}

	if (len > MAX_SAMPLE_SIZE)
		len = MAX_SAMPLE_SIZE;

	while (i < len - SAMPLING_READ_SIZE) {
		memcpy((void *)&ctx->sample[s], &buf[i], SAMPLING_READ_SIZE);
		i += SAMPLING_INTERVAL;
		s += SAMPLING_INTERVAL;
	}

	ctx->sample_size = s;

	INIT_LIST_HEAD