path: root/src/include/intpack.i

/*-
 * Copyright (c) 2014-2015 MongoDB, Inc.
 * Copyright (c) 2008-2014 WiredTiger, Inc.
 *	All rights reserved.
 *
 * See the file LICENSE for redistribution information.
 */

/*
 * Variable-length integer encoding.
 * We need up to 64 bits, signed and unsigned.  Further, we want the packed
 * representation to have the same lexicographic ordering as the integer
 * values.  This avoids the need for special-purpose comparison code.
 *
 * Try hard to keep small values small (up to ~2 bytes): that gives the biggest
 * benefit for common cases storing small values.  After that, just encode the
 * length in the first byte: we could squeeze in a couple of extra bits, but
 * the marginal benefit is small, and we want this code to be relatively
 * easy to implement in client code or scripting APIs.
 *
 * First byte  | Next |                        |
 * byte        | bytes| Min Value              | Max Value
 * ------------+------+------------------------+--------------------------------
 * [00 00xxxx] | free | N/A                    | N/A
 * [00 01llll] | llll | -2^64                  | -2^13 - 2^6
 * [00 1xxxxx] | 1    | -2^13 - 2^6            | -2^6 - 1
 * [01 xxxxxx] | 0    | -2^6                   | -1
 * [10 xxxxxx] | 0    | 0                      | 2^6 - 1
 * [11 0xxxxx] | 1    | 2^6                    | 2^13 + 2^6 - 1
 * [11 10llll] | llll | 2^13 + 2^6             | 2^64 - 1
 * [11 11xxxx] | free | N/A                    | N/A
 */

#define	NEG_MULTI_MARKER (uint8_t)0x10
#define	NEG_2BYTE_MARKER (uint8_t)0x20
#define	NEG_1BYTE_MARKER (uint8_t)0x40
#define	POS_1BYTE_MARKER (uint8_t)0x80
#define	POS_2BYTE_MARKER (uint8_t)0xc0
#define	POS_MULTI_MARKER (uint8_t)0xe0

#define	NEG_1BYTE_MIN ((-1) << 6)
#define	NEG_2BYTE_MIN (((-1) << 13) + NEG_1BYTE_MIN)
#define	POS_1BYTE_MAX ((1 << 6) - 1)
#define	POS_2BYTE_MAX ((1 << 13) + POS_1BYTE_MAX)

/* Extract bits <start> to <end> from a value (counting from LSB == 0). */
#define	GET_BITS(x, start, end)                                         \
	(((uint64_t)(x) & ((1U << (start)) - 1U)) >> (end))

#define	WT_SIZE_CHECK(l, maxl)						\
	WT_RET_TEST((maxl) != 0 && (size_t)(l) > (maxl), ENOMEM)

/* Count the leading zero bytes. */
#if defined(__GNUC__)
#define	WT_LEADING_ZEROS(x, i)						\
	(i = (x == 0) ? (int)sizeof (x) : __builtin_clzll(x) >> 3)
#elif defined(_MSC_VER)
#define	WT_LEADING_ZEROS(x, i)	do {					\
	if (x == 0) i = (int)sizeof(x);				\
	else  { 							\
		unsigned long __index;					\
		_BitScanReverse64(&__index, x);				\
		__index = 63 ^ __index;					\
		i = (int)(__index >> 3); }				\
	} while (0)
#else
#define	WT_LEADING_ZEROS(x, i) do {					\
	uint64_t __x = (x);						\
	uint64_t __m = (uint64_t)0xff << 56;				\
	for (i = 0; !(__x & __m) && i != 8; i++)			\
		__m >>= 8;						\
} while (0)
#endif

/*
 * __wt_vpack_posint --
 *	Packs a positive variable-length integer in the specified location.
 */
static inline int
__wt_vpack_posint(uint8_t **pp, size_t maxlen, uint64_t x)
{
	uint8_t *p;
	int len, lz, shift;

	WT_LEADING_ZEROS(x, lz);
	len = (int)sizeof (x) - lz;
	WT_SIZE_CHECK(len + 1, maxlen);
	p = *pp;

	/* There are four bits we can use in the first byte. */
	*p++ |= (len & 0xf);

	for (shift = (len - 1) << 3; len != 0; --len, shift -= 8)
		*p++ = (uint8_t)(x >> shift);

	*pp = p;
	return (0);
}

/*
 * __wt_vpack_negint --
 *	Packs a negative variable-length integer in the specified location.
 */
static inline int
__wt_vpack_negint(uint8_t **pp, size_t maxlen, uint64_t x)
{
	uint8_t *p;
	int len, lz, shift;

	WT_LEADING_ZEROS(~x, lz);
	len = (int)sizeof (x) - lz;
	WT_SIZE_CHECK(len + 1, maxlen);
	p = *pp;

	/*
	 * There are four size bits we can use in the first byte.
	 * For negative numbers, we store the number of leading 0xff bytes
	 * to maintain ordering (if this is not obvious, it may help to
	 * remember that -1 is the largest negative number).
	 */
	*p++ |= (lz & 0xf);

	for (shift = (len - 1) << 3; len != 0; shift -= 8, --len)
		*p++ = (uint8_t)(x >> shift);

	*pp = p;
	return (0);
}

/*
 * __wt_vunpack_posint --
 *	Reads a variable-length positive integer from the specified location.
 */
static inline int
__wt_vunpack_posint(const uint8_t **pp, size_t maxlen, uint64_t *retp)
{
	uint64_t x;
	const uint8_t *p;
	uint8_t len;

	/* There are four length bits in the first byte. */
	p = *pp;
	len = (*p++ & 0xf);
	WT_SIZE_CHECK(len + 1, maxlen);

	for (x = 0; len != 0; --len)
		x = (x << 8) | *p++;

	*retp = x;
	*pp = p;
	return (0);
}

/*
 * __wt_vunpack_negint --
 *	Reads a variable-length negative integer from the specified location.
 */
static inline int
__wt_vunpack_negint(const uint8_t **pp, size_t maxlen, uint64_t *retp)
{
	uint64_t x;
	const uint8_t *p;
	uint8_t len;

	/* There are four length bits in the first byte. */
	p = *pp;
	len = (int)sizeof (x) - (*p++ & 0xf);
	WT_SIZE_CHECK(len + 1, maxlen);

	for (x = UINT64_MAX; len != 0; --len)
		x = (x << 8) | *p++;

	*retp = x;
	*pp = p;
	return (0);
}

/*
 * __wt_vpack_uint --
 *	Variable-sized packing for unsigned integers
 */
static inline int
__wt_vpack_uint(uint8_t **pp, size_t maxlen, uint64_t x)
{
	uint8_t *p;

	WT_SIZE_CHECK(1, maxlen);
	p = *pp;
	if (x <= POS_1BYTE_MAX)
		*p++ = POS_1BYTE_MARKER | GET_BITS(x, 6, 0);
	else if (x <= POS_2BYTE_MAX) {
		WT_SIZE_CHECK(2, maxlen);
		x -= POS_1BYTE_MAX + 1;
		*p++ = POS_2BYTE_MARKER | GET_BITS(x, 13, 8);
		*p++ = GET_BITS(x, 8, 0);
	} else if (x == POS_2BYTE_MAX + 1) {
		/*
		 * This is a special case where we could store the value with
		 * just a single byte, but we append a zero byte so that the
		 * encoding doesn't get shorter for this one value.
		 */
		*p++ = POS_MULTI_MARKER | 0x1;
		*p++ = 0;
	} else {
		x -= POS_2BYTE_MAX + 1;
		*p = POS_MULTI_MARKER;
		return (__wt_vpack_posint(pp, maxlen, x));
	}

	*pp = p;
	return (0);
}

/*
 * __wt_vpack_int --
 *	Variable-sized packing for signed integers
 */
static inline int
__wt_vpack_int(uint8_t **pp, size_t maxlen, int64_t x)
{
	uint8_t *p;

	WT_SIZE_CHECK(1, maxlen);
	p = *pp;
	if (x < NEG_2BYTE_MIN) {
		*p = NEG_MULTI_MARKER;
		return (__wt_vpack_negint(pp, maxlen, (uint64_t)x));
	} else if (x < NEG_1BYTE_MIN) {
		WT_SIZE_CHECK(2, maxlen);
		x -= NEG_2BYTE_MIN;
		*p++ = NEG_2BYTE_MARKER | GET_BITS(x, 13, 8);
		*p++ = GET_BITS(x, 8, 0);
	} else if (x < 0) {
		x -= NEG_1BYTE_MIN;
		*p++ = NEG_1BYTE_MARKER | GET_BITS(x, 6, 0);
	} else
		/* For non-negative values, use the unsigned code above. */
		return (__wt_vpack_uint(pp, maxlen, (uint64_t)x));

	*pp = p;
	return (0);
}

/*
 * __wt_vunpack_uint --
 *	Variable-sized unpacking for unsigned integers
 */
static inline int
__wt_vunpack_uint(const uint8_t **pp, size_t maxlen, uint64_t *xp)
{
	const uint8_t *p;

	WT_SIZE_CHECK(1, maxlen);
	p = *pp;
	switch (*p & 0xf0) {
	case POS_1BYTE_MARKER:
	case POS_1BYTE_MARKER | 0x10:
	case POS_1BYTE_MARKER | 0x20:
	case POS_1BYTE_MARKER | 0x30:
		*xp = GET_BITS(*p, 6, 0);
		p += 1;
		break;
	case POS_2BYTE_MARKER:
	case POS_2BYTE_MARKER | 0x10:
		WT_SIZE_CHECK(2, maxlen);
		*xp = GET_BITS(*p++, 5, 0) << 8;
		*xp |= *p++;
		*xp += POS_1BYTE_MAX + 1;
		break;
	case POS_MULTI_MARKER:
		WT_RET(__wt_vunpack_posint(pp, maxlen, xp));
		*xp += POS_2BYTE_MAX + 1;
		return (0);
	default:
		return (EINVAL);
	}

	*pp = p;
	return (0);
}

/*
 * __wt_vunpack_int --
 *	Variable-sized packing for signed integers
 */
static inline int
__wt_vunpack_int(const uint8_t **pp, size_t maxlen, int64_t *xp)
{
	const uint8_t *p;

	WT_SIZE_CHECK(1, maxlen);
	p = *pp;
	switch (*p & 0xf0) {
	case NEG_MULTI_MARKER:
		WT_RET(__wt_vunpack_negint(pp, maxlen, (uint64_t *)xp));
		return (0);
	case NEG_2BYTE_MARKER:
	case NEG_2BYTE_MARKER | 0x10:
		WT_SIZE_CHECK(2, maxlen);
		*xp = (int64_t)(GET_BITS(*p++, 5, 0) << 8);
		*xp |= *p++;
		*xp += NEG_2BYTE_MIN;
		p += 2;
		break;
	case NEG_1BYTE_MARKER:
	case NEG_1BYTE_MARKER | 0x10:
	case NEG_1BYTE_MARKER | 0x20:
	case NEG_1BYTE_MARKER | 0x30:
		*xp = NEG_1BYTE_MIN + (int64_t)GET_BITS(*p, 6, 0);
		p += 1;
		break;
	default:
		/* Identical to the unsigned case. */
		return (__wt_vunpack_uint(pp, maxlen, (uint64_t *)xp));
	}

	*pp = p;
	return (0);
}

/*
 * __wt_vsize_posint --
 *	Return the packed size of a positive variable-length integer.
 */
static inline size_t
__wt_vsize_posint(uint64_t x)
{
	int lz;

	WT_LEADING_ZEROS(x, lz);
	return ((size_t)(WT_INTPACK64_MAXSIZE - lz));
}

/*
 * __wt_vsize_negint --
 *	Return the packed size of a negative variable-length integer.
 */
static inline size_t
__wt_vsize_negint(uint64_t x)
{
	int lz;

	WT_LEADING_ZEROS(~x, lz);
	return (size_t)(WT_INTPACK64_MAXSIZE - lz);
}

/*
 * __wt_vsize_uint --
 *	Return the packed size of an unsigned integer.
 */
static inline size_t
__wt_vsize_uint(uint64_t x)
{
	if (x <= POS_1BYTE_MAX)
		return (1);
	else if (x <= POS_2BYTE_MAX + 1) {
		return (2);
	} else {
		x -= POS_2BYTE_MAX + 1;
		return (__wt_vsize_posint(x));
	}
}

/*
 * __wt_vsize_int --
 *	Return the packed size of a signed integer.
 */
static inline size_t
__wt_vsize_int(int64_t x)
{
	if (x < NEG_2BYTE_MIN) {
		return (__wt_vsize_negint((uint64_t)x));
	} else if (x < NEG_1BYTE_MIN) {
		return (2);
	} else if (x < 0) {
		return (1);
	} else
		/* For non-negative values, use the unsigned code above. */
		return (__wt_vsize_uint((uint64_t)x));
}