fs/smb/client/compress.c

Source file repositories/reference/linux-study-clean/fs/smb/client/compress.c

File Facts

System
Linux kernel
Corpus path
fs/smb/client/compress.c
Extension
.c
Size
8819 bytes
Lines
373
Domain
Core OS
Bucket
VFS And Filesystem Core
Inferred role
Core OS: implementation source
Status
source implementation candidate

Why This File Exists

Core operating-system implementation surface: boot, tasks, memory, VFS, syscall-facing interfaces, synchronization, credentials, and isolation.

Dependency Surface

Detected Declarations

Annotated Snippet

struct bucket {
	unsigned int count;
};

static inline size_t pow4(size_t n)
{
	return n * n * n * n;
}

/*
 * has_low_entropy() - Compute Shannon entropy of the sampled data.
 * @bkt:	Bytes counts of the sample.
 * @slen:	Size of the sample.
 *
 * Return: true if the level (percentage of number of bits that would be required to
 *	   compress the data) is below the minimum threshold.
 *
 * Note:
 * There _is_ an entropy level here that's > 65 (minimum threshold) that would indicate a
 * possibility of compression, but compressing, or even further analysing, it would waste so much
 * resources that it's simply not worth it.
 *
 * Also Shannon entropy is the last computed heuristic; if we got this far and ended up
 * with uncertainty, just stay on the safe side and call it uncompressible.
 */
static bool has_low_entropy(struct bucket *bkt, size_t slen)
{
	const size_t threshold = 65, max_entropy = 8 * ilog2(16);
	size_t i, p, p2, len, sum = 0;

	len = ilog2(pow4(slen));

	for (i = 0; i < 256 && bkt[i].count > 0; i++) {
		p = bkt[i].count;
		p2 = ilog2(pow4(p));
		sum += p * (len - p2);
	}

	sum /= slen;

	return ((sum * 100 / max_entropy) <= threshold);
}

#define BYTE_DIST_BAD		0
#define BYTE_DIST_GOOD		1
#define BYTE_DIST_MAYBE		2
/*
 * calc_byte_distribution() - Compute byte distribution on the sampled data.
 * @bkt:	Byte counts of the sample.
 * @slen:	Size of the sample.
 *
 * Return:
 * BYTE_DIST_BAD:	A "hard no" for compression -- a computed uniform distribution of
 *			the bytes (e.g. random or encrypted data).
 * BYTE_DIST_GOOD:	High probability (normal (Gaussian) distribution) of the data being
 *			compressible.
 * BYTE_DIST_MAYBE:	When computed byte distribution resulted in "low > n < high"
 *			grounds.  has_low_entropy() should be used for a final decision.
 */
static int calc_byte_distribution(struct bucket *bkt, size_t slen)
{
	const size_t low = 64, high = 200, threshold = slen * 90 / 100;
	size_t sum = 0;
	int i;

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

	if (sum > threshold)
		return BYTE_DIST_BAD;

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

	if (i <= low)
		return BYTE_DIST_GOOD;

	if (i >= high)
		return BYTE_DIST_BAD;

	return BYTE_DIST_MAYBE;
}

static bool is_mostly_ascii(const struct bucket *bkt)
{
	size_t count = 0;
	int i;

Annotation

Implementation Notes