Compress-Snappy

 view release on metacpan or  search on metacpan

src/csnappy_compress.c  view on Meta::CPAN

	return op + length;
}

static uint8_t* emit_copy(
	uint8_t *op,
	uint32_t offset,
	uint32_t len)
{
	DCHECK_GT(offset, 0);
	
	/* Emit 64 byte copies but make sure to keep at least four bytes
	 * reserved */
	while (unlikely(len >= 68)) {
		*op++ = COPY_2_BYTE_OFFSET | ((64 - 1) << 2);
		*op++ = offset & 255;
		*op++ = offset >> 8;
		len -= 64;
	}

	/* Emit an extra 60 byte copy if have too much data to fit in one
	 * copy */
	if (unlikely(len > 64)) {
		*op++ = COPY_2_BYTE_OFFSET | ((60 - 1) << 2);
		*op++ = offset & 255;
		*op++ = offset >> 8;
		len -= 60;
	}

	/* Emit remainder */
	DCHECK_GE(len, 4);
	if ((len < 12) && (offset < 2048)) {
		int len_minus_4 = len - 4;
		*op++ = COPY_1_BYTE_OFFSET   |
			((len_minus_4) << 2) |
			((offset >> 8) << 5);
		*op++ = offset & 0xff;
	} else {
		*op++ = COPY_2_BYTE_OFFSET | ((len-1) << 2);
		*op++ = offset & 255;
		*op++ = offset >> 8;
	}
	return op;
}

static uint32_t find_match_length(
	const uint8_t *s1,
	const uint8_t *s2,
	const uint8_t *s2_end)
{
	const uint8_t * const s2_start = s2;
	while (s2 < s2_end && *s1++ == *s2++) /*nothing*/;
	return s2 - s2_start - 1;
}

static uint32_t hash(uint32_t v)
{
	return v * UINT32_C(0x1e35a7bd);
}

char*
csnappy_compress_fragment(
	const char *input,
	const uint32_t input_size,
	char *dst,
	void *working_memory,
	const int workmem_bytes_power_of_two)
{
	const uint8_t * const src_start = (const uint8_t *)input;
	const uint8_t * const src_end_minus4 = src_start + input_size - 4;
	const uint8_t *src = src_start, *done_upto = src_start, *match;
	uint8_t *op = (uint8_t *)dst;
	uint16_t *wm = (uint16_t *)working_memory;
	int shift = 33 - workmem_bytes_power_of_two;
	uint32_t curr_val, curr_hash, match_val, offset, length;
	if (unlikely(input_size < 4))
		goto the_end;
	memset(wm, 0, 1 << workmem_bytes_power_of_two);
	for (;;) {
		curr_val = (src[1] << 8) | (src[2] << 16) | (src[3] << 24);
		do {
			src++;
			if (unlikely(src >= src_end_minus4))
				goto the_end;
			curr_val = (curr_val >> 8) | (src[3] << 24);
			DCHECK_EQ(curr_val, get_unaligned_le32(src));
			curr_hash = hash(curr_val) >> shift;
			match = src_start + wm[curr_hash];
			DCHECK_LT(match, src);
			wm[curr_hash] = src - src_start;
			match_val = get_unaligned_le32(match);
		} while (likely(curr_val != match_val));
		offset = src - match;
		length = 4 + find_match_length(
			match + 4, src + 4, src_end_minus4 + 4);
		DCHECK_EQ(memcmp(src, match, length), 0);
		op = emit_literal(op, done_upto, src);
		op = emit_copy(op, offset, length);
		done_upto = src + length;
		src = done_upto - 1;
	}
the_end:
	op = emit_literal(op, done_upto, src_end_minus4 + 4);
	return (char *)op;
}

#else /* !simple */

/*
 * Any hash function will produce a valid compressed bitstream, but a good
 * hash function reduces the number of collisions and thus yields better
 * compression for compressible input, and more speed for incompressible
 * input. Of course, it doesn't hurt if the hash function is reasonably fast
 * either, as it gets called a lot.
 */
static INLINE uint32_t HashBytes(uint32_t bytes, int shift)
{
	uint32_t kMul = 0x1e35a7bd;
	return (bytes * kMul) >> shift;
}
static INLINE uint32_t Hash(const char *p, int shift)
{

src/csnappy_compress.c  view on Meta::CPAN

	}

	/* Emit remainder */
	op = EmitCopyLessThan64(op, offset, len);
	return op;
}


/*
For 0 <= offset <= 4, GetUint32AtOffset(GetEightBytesAt(p), offset) will
equal UNALIGNED_LOAD32(p + offset).  Motivation: On x86-64 hardware we have
empirically found that overlapping loads such as
 UNALIGNED_LOAD32(p) ... UNALIGNED_LOAD32(p+1) ... UNALIGNED_LOAD32(p+2)
are slower than UNALIGNED_LOAD64(p) followed by shifts and casts to uint32.

We have different versions for 64- and 32-bit; ideally we would avoid the
two functions and just INLINE the UNALIGNED_LOAD64 call into
GetUint32AtOffset, but GCC (at least not as of 4.6) is seemingly not clever
enough to avoid loading the value multiple times then. For 64-bit, the load
is done when GetEightBytesAt() is called, whereas for 32-bit, the load is
done at GetUint32AtOffset() time.
*/

#if defined(__x86_64__) || (__SIZEOF_SIZE_T__ == 8)

typedef uint64_t EightBytesReference;

static INLINE EightBytesReference GetEightBytesAt(const char* ptr) {
	return UNALIGNED_LOAD64(ptr);
}

static INLINE uint32_t GetUint32AtOffset(uint64_t v, int offset) {
	DCHECK_GE(offset, 0);
	DCHECK_LE(offset, 4);
#if __BYTE_ORDER == __LITTLE_ENDIAN
	return v >> (8 * offset);
#else
	return v >> (32 - 8 * offset);
#endif
}

#else /* !ARCH_K8 */

typedef const char* EightBytesReference;

static INLINE EightBytesReference GetEightBytesAt(const char* ptr) {
	return ptr;
}

static INLINE uint32_t GetUint32AtOffset(const char* v, int offset) {
	DCHECK_GE(offset, 0);
	DCHECK_LE(offset, 4);
	return UNALIGNED_LOAD32(v + offset);
}

#endif /* !ARCH_K8 */


#define kInputMarginBytes 15
char*
csnappy_compress_fragment(
	const char *input,
	const uint32_t input_size,
	char *op,
	void *working_memory,
	const int workmem_bytes_power_of_two)
{
	const char *ip, *ip_end, *base_ip, *next_emit, *ip_limit, *next_ip,
			*candidate, *base;
	uint16_t *table = (uint16_t *)working_memory;
	EightBytesReference input_bytes;
	uint32_t hash, next_hash, prev_hash, cur_hash, skip, candidate_bytes;
	int shift, matched;

	DCHECK_GE(workmem_bytes_power_of_two, 9);
	DCHECK_LE(workmem_bytes_power_of_two, 15);
	/* Table of 2^X bytes, need (X-1) bits to address table of uint16_t.
	 * How many bits of 32bit hash function result are discarded? */
	shift = 33 - workmem_bytes_power_of_two;
	/* "ip" is the input pointer, and "op" is the output pointer. */
	ip = input;
	DCHECK_LE(input_size, kBlockSize);
	ip_end = input + input_size;
	base_ip = ip;
	/* Bytes in [next_emit, ip) will be emitted as literal bytes. Or
	   [next_emit, ip_end) after the main loop. */
	next_emit = ip;

	if (unlikely(input_size < kInputMarginBytes))
		goto emit_remainder;

	memset(working_memory, 0, 1 << workmem_bytes_power_of_two);

	ip_limit = input + input_size - kInputMarginBytes;
	next_hash = Hash(++ip, shift);

main_loop:
	DCHECK_LT(next_emit, ip);
	/*
	* The body of this loop calls EmitLiteral once and then EmitCopy one or
	* more times. (The exception is that when we're close to exhausting
	* the input we goto emit_remainder.)
	*
	* In the first iteration of this loop we're just starting, so
	* there's nothing to copy, so calling EmitLiteral once is
	* necessary. And we only start a new iteration when the
	* current iteration has determined that a call to EmitLiteral will
	* precede the next call to EmitCopy (if any).
	*
	* Step 1: Scan forward in the input looking for a 4-byte-long match.
	* If we get close to exhausting the input then goto emit_remainder.
	*
	* Heuristic match skipping: If 32 bytes are scanned with no matches
	* found, start looking only at every other byte. If 32 more bytes are
	* scanned, look at every third byte, etc.. When a match is found,
	* immediately go back to looking at every byte. This is a small loss
	* (~5% performance, ~0.1% density) for compressible data due to more
	* bookkeeping, but for non-compressible data (such as JPEG) it's a huge
	* win since the compressor quickly "realizes" the data is incompressible
	* and doesn't bother looking for matches everywhere.
	*

src/csnappy_compress.c  view on Meta::CPAN

		table[hash] = ip - base_ip;
	} while (likely(UNALIGNED_LOAD32(ip) !=
			UNALIGNED_LOAD32(candidate)));

	/*
	* Step 2: A 4-byte match has been found. We'll later see if more
	* than 4 bytes match. But, prior to the match, input
	* bytes [next_emit, ip) are unmatched. Emit them as "literal bytes."
	*/
	DCHECK_LE(next_emit + 16, ip_end);
	op = EmitLiteral(op, next_emit, ip - next_emit, 1);

	/*
	* Step 3: Call EmitCopy, and then see if another EmitCopy could
	* be our next move. Repeat until we find no match for the
	* input immediately after what was consumed by the last EmitCopy call.
	*
	* If we exit this loop normally then we need to call EmitLiteral next,
	* though we don't yet know how big the literal will be. We handle that
	* by proceeding to the next iteration of the main loop. We also can exit
	* this loop via goto if we get close to exhausting the input.
	*/
	candidate_bytes = 0;

	do {
		/* We have a 4-byte match at ip, and no need to emit any
		 "literal bytes" prior to ip. */
		base = ip;
		matched = 4 + FindMatchLength(candidate + 4, ip + 4, ip_end);
		ip += matched;
		DCHECK_EQ(0, memcmp(base, candidate, matched));
		op = EmitCopy(op, base - candidate, matched);
		/* We could immediately start working at ip now, but to improve
		 compression we first update table[Hash(ip - 1, ...)]. */
		next_emit = ip;
		if (unlikely(ip >= ip_limit))
			goto emit_remainder;
		input_bytes = GetEightBytesAt(ip - 1);
		prev_hash = HashBytes(GetUint32AtOffset(input_bytes, 0), shift);
		table[prev_hash] = ip - base_ip - 1;
		cur_hash = HashBytes(GetUint32AtOffset(input_bytes, 1), shift);
		candidate = base_ip + table[cur_hash];
		candidate_bytes = UNALIGNED_LOAD32(candidate);
		table[cur_hash] = ip - base_ip;
	} while (GetUint32AtOffset(input_bytes, 1) == candidate_bytes);

	next_hash = HashBytes(GetUint32AtOffset(input_bytes, 2), shift);
	++ip;
	goto main_loop;

emit_remainder:
	/* Emit the remaining bytes as a literal */
	if (next_emit < ip_end)
		op = EmitLiteral(op, next_emit, ip_end - next_emit, 0);

	return op;
}
#endif /* !simple */
#if defined(__KERNEL__) && !defined(STATIC)
EXPORT_SYMBOL(csnappy_compress_fragment);
#endif

uint32_t __attribute__((const))
csnappy_max_compressed_length(uint32_t source_len)
{
	return 32 + source_len + source_len/6;
}
#if defined(__KERNEL__) && !defined(STATIC)
EXPORT_SYMBOL(csnappy_max_compressed_length);
#endif

void
csnappy_compress(
	const char *input,
	uint32_t input_length,
	char *compressed,
	uint32_t *compressed_length,
	void *working_memory,
	const int workmem_bytes_power_of_two)
{
	int workmem_size;
	int num_to_read;
	uint32_t written = 0;
	char *p = encode_varint32(compressed, input_length);
	written += (p - compressed);
	compressed = p;
	while (input_length > 0) {
		num_to_read = min(input_length, (uint32_t)kBlockSize);
		workmem_size = workmem_bytes_power_of_two;
		if (unlikely(num_to_read < kBlockSize)) {
			for (workmem_size = 9;
			     workmem_size < workmem_bytes_power_of_two;
			     ++workmem_size) {
				if ((1 << (workmem_size-1)) >= num_to_read)
					break;
			}
		}
		p = csnappy_compress_fragment(
				input, num_to_read, compressed,
				working_memory, workmem_size);
		written += (p - compressed);
		compressed = p;
		input_length -= num_to_read;
		input += num_to_read;
	}
	*compressed_length = written;
}
#if defined(__KERNEL__) && !defined(STATIC)
EXPORT_SYMBOL(csnappy_compress);

MODULE_LICENSE("BSD");
MODULE_DESCRIPTION("Snappy Compressor");
#endif