fs/ntfs3/lznt.c

Source file repositories/reference/linux-study-clean/fs/ntfs3/lznt.c

File Facts

System
Linux kernel
Corpus path
fs/ntfs3/lznt.c
Extension
.c
Size
9781 bytes
Lines
457
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 lznt_hash {
	const u8 *p1;
	const u8 *p2;
};

struct lznt {
	const u8 *unc;
	const u8 *unc_end;
	const u8 *best_match;
	size_t max_len;
	bool std;

	struct lznt_hash hash[LZNT_CHUNK_SIZE];
};

static inline size_t get_match_len(const u8 *ptr, const u8 *end, const u8 *prev,
				   size_t max_len)
{
	size_t len = 0;

	while (ptr + len < end && ptr[len] == prev[len] && ++len < max_len)
		;
	return len;
}

static size_t longest_match_std(const u8 *src, struct lznt *ctx)
{
	size_t hash_index;
	size_t len1 = 0, len2 = 0;
	const u8 **hash;

	hash_index =
		((40543U * ((((src[0] << 4) ^ src[1]) << 4) ^ src[2])) >> 4) &
		(LZNT_CHUNK_SIZE - 1);

	hash = &(ctx->hash[hash_index].p1);

	if (hash[0] >= ctx->unc && hash[0] < src && hash[0][0] == src[0] &&
	    hash[0][1] == src[1] && hash[0][2] == src[2]) {
		len1 = 3;
		if (ctx->max_len > 3)
			len1 += get_match_len(src + 3, ctx->unc_end,
					      hash[0] + 3, ctx->max_len - 3);
	}

	if (hash[1] >= ctx->unc && hash[1] < src && hash[1][0] == src[0] &&
	    hash[1][1] == src[1] && hash[1][2] == src[2]) {
		len2 = 3;
		if (ctx->max_len > 3)
			len2 += get_match_len(src + 3, ctx->unc_end,
					      hash[1] + 3, ctx->max_len - 3);
	}

	/* Compare two matches and select the best one. */
	if (len1 < len2) {
		ctx->best_match = hash[1];
		len1 = len2;
	} else {
		ctx->best_match = hash[0];
	}

	hash[1] = hash[0];
	hash[0] = src;
	return len1;
}

static size_t longest_match_best(const u8 *src, struct lznt *ctx)
{
	size_t max_len;
	const u8 *ptr;

	if (ctx->unc >= src || !ctx->max_len)
		return 0;

	max_len = 0;
	for (ptr = ctx->unc; ptr < src; ++ptr) {
		size_t len =
			get_match_len(src, ctx->unc_end, ptr, ctx->max_len);
		if (len >= max_len) {
			max_len = len;
			ctx->best_match = ptr;
		}
	}

	return max_len >= 3 ? max_len : 0;
}

static const size_t s_max_len[] = {
	0x1002, 0x802, 0x402, 0x202, 0x102, 0x82, 0x42, 0x22, 0x12,
};

Annotation

Implementation Notes