fs/ntfs3/lib/decompress_common.c

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

File Facts

System
Linux kernel
Corpus path
fs/ntfs3/lib/decompress_common.c
Extension
.c
Size
11991 bytes
Lines
320
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

if (left < 0) {
			/* The lengths overflow the codespace; that is, the code
			 * is over-subscribed.
			 */
			return -1;
		}
	}

	if (left) {
		/* The lengths do not fill the codespace; that is, they form an
		 * incomplete set.
		 */
		if (left == (1 << max_codeword_len)) {
			/* The code is completely empty.  This is arguably
			 * invalid, but in fact it is valid in LZX and XPRESS,
			 * so we must allow it.  By definition, no symbols can
			 * be decoded with an empty code.  Consequently, we
			 * technically don't even need to fill in the decode
			 * table.  However, to avoid accessing uninitialized
			 * memory if the algorithm nevertheless attempts to
			 * decode symbols using such a code, we zero out the
			 * decode table.
			 */
			memset(decode_table, 0,
			       table_num_entries * sizeof(decode_table[0]));
			return 0;
		}
		return -1;
	}

	/* Sort the symbols primarily by length and secondarily by symbol order.
	 */

	/* Initialize 'offsets' so that offsets[len] for 1 <= len <=
	 * max_codeword_len is the number of codewords shorter than 'len' bits.
	 */
	offsets[1] = 0;
	for (len = 1; len < max_codeword_len; len++)
		offsets[len + 1] = offsets[len] + len_counts[len];

	/* Use the 'offsets' array to sort the symbols.  Note that we do not
	 * include symbols that are not used in the code.  Consequently, fewer
	 * than 'num_syms' entries in 'sorted_syms' may be filled.
	 */
	for (sym = 0; sym < num_syms; sym++)
		if (lens[sym])
			sorted_syms[offsets[lens[sym]]++] = sym;

	/* Fill entries for codewords with length <= table_bits
	 * --- that is, those short enough for a direct mapping.
	 *
	 * The table will start with entries for the shortest codeword(s), which
	 * have the most entries.  From there, the number of entries per
	 * codeword will decrease.
	 */
	decode_table_ptr = decode_table;
	sym_idx = 0;
	codeword_len = 1;
	stores_per_loop = (1 << (table_bits - codeword_len));
	for (; stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1) {
		u32 end_sym_idx = sym_idx + len_counts[codeword_len];

		for (; sym_idx < end_sym_idx; sym_idx++) {
			u16 entry;
			u16 *p;
			u32 n;

			entry = ((u32)codeword_len << 11) | sorted_syms[sym_idx];
			p = (u16 *)decode_table_ptr;
			n = stores_per_loop;

			do {
				*p++ = entry;
			} while (--n);

			decode_table_ptr = p;
		}
	}

	/* If we've filled in the entire table, we are done.  Otherwise,
	 * there are codewords longer than table_bits for which we must
	 * generate binary trees.
	 */
	decode_table_pos = (u16 *)decode_table_ptr - decode_table;
	if (decode_table_pos != table_num_entries) {
		u32 j;
		u32 next_free_tree_slot;
		u32 cur_codeword;

		/* First, zero out the remaining entries.  This is

Annotation

Implementation Notes