fs/ntfs/compress.c

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

File Facts

System
Linux kernel
Corpus path
fs/ntfs/compress.c
Extension
.c
Size
43441 bytes
Lines
1579
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 compress_context {
	const unsigned char *inbuf;
	int bufsize;
	int size;
	int rel;
	int mxsz;
	s16 head[1 << HASH_SHIFT];
	s16 prev[NTFS_SB_SIZE];
};

/*
 * Hash the next 3-byte sequence in the input buffer
 */
static inline unsigned int ntfs_hash(const u8 *p)
{
	u32 str;
	u32 hash;

	/*
	 * Unaligned access allowed, and little endian CPU.
	 * Callers ensure that at least 4 (not 3) bytes are remaining.
	 */
	str = *(const u32 *)p & 0xFFFFFF;
	hash = str * HASH_MULTIPLIER;

	/* High bits are more random than the low bits.  */
	return hash >> (32 - HASH_SHIFT);
}

/*
 * Search for the longest sequence matching current position
 *
 * A hash table, each entry of which points to a chain of sequence
 * positions sharing the corresponding hash code, is maintained to speed up
 * searching for matches.  To maintain the hash table, either
 * ntfs_best_match() or ntfs_skip_position() has to be called for each
 * consecutive position.
 *
 * This function is heavily used; it has to be optimized carefully.
 *
 * This function sets pctx->size and pctx->rel to the length and offset,
 * respectively, of the longest match found.
 *
 * The minimum match length is assumed to be 3, and the maximum match
 * length is assumed to be pctx->mxsz.  If this function produces
 * pctx->size < 3, then no match was found.
 *
 * Note: for the following reasons, this function is not guaranteed to find
 * *the* longest match up to pctx->mxsz:
 *
 *      (1) If this function finds a match of NICE_MATCH_LEN bytes or greater,
 *          it ends early because a match this long is good enough and it's not
 *          worth spending more time searching.
 *
 *      (2) If this function considers MAX_SEARCH_DEPTH matches with a single
 *          position, it ends early and returns the longest match found so far.
 *          This saves a lot of time on degenerate inputs.
 */
static void ntfs_best_match(struct compress_context *pctx, const int i,
		int best_len)
{
	const u8 * const inbuf = pctx->inbuf;
	const u8 * const strptr = &inbuf[i]; /* String we're matching against */
	s16 * const prev = pctx->prev;
	const int max_len = min(pctx->bufsize - i, pctx->mxsz);
	const int nice_len = min(NICE_MATCH_LEN, max_len);
	int depth_remaining = MAX_SEARCH_DEPTH;
	const u8 *best_matchptr = strptr;
	unsigned int hash;
	s16 cur_match;
	const u8 *matchptr;
	int len;

	if (max_len < 4)
		goto out;

	/* Insert the current sequence into the appropriate hash chain. */
	hash = ntfs_hash(strptr);
	cur_match = pctx->head[hash];
	prev[i] = cur_match;
	pctx->head[hash] = i;

	if (best_len >= max_len) {
		/*
		 * Lazy match is being attempted, but there aren't enough length
		 * bits remaining to code a longer match.
		 */
		goto out;
	}

Annotation

Implementation Notes