diff options
Diffstat (limited to 'src/third_party/wiredtiger/src/include/intpack.i')
| -rw-r--r-- | src/third_party/wiredtiger/src/include/intpack.i | 460 |
1 files changed, 229 insertions, 231 deletions
diff --git a/src/third_party/wiredtiger/src/include/intpack.i b/src/third_party/wiredtiger/src/include/intpack.i index aef94460262..e22adcd913a 100644 --- a/src/third_party/wiredtiger/src/include/intpack.i +++ b/src/third_party/wiredtiger/src/include/intpack.i @@ -31,353 +31,351 @@ * [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) +#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 GET_BITS(x, start, end) (((uint64_t)(x) & ((1U << (start)) - 1U)) >> (end)) /* - * Size checks: return ENOMEM if not enough room when writing, EINVAL if the - * length is wrong when reading (presumably the value is corrupted). + * Size checks: return ENOMEM if not enough room when writing, EINVAL if the length is wrong when + * reading (presumably the value is corrupted). */ -#define WT_SIZE_CHECK_PACK(l, maxl) \ - WT_RET_TEST((maxl) != 0 && (size_t)(l) > (maxl), ENOMEM) -#define WT_SIZE_CHECK_UNPACK(l, maxl) \ - WT_RET_TEST((maxl) != 0 && (size_t)(l) > (maxl), EINVAL) +#define WT_SIZE_CHECK_PACK(l, maxl) WT_RET_TEST((maxl) != 0 && (size_t)(l) > (maxl), ENOMEM) +#define WT_SIZE_CHECK_UNPACK(l, maxl) WT_RET_TEST((maxl) != 0 && (size_t)(l) > (maxl), EINVAL) /* Count the leading zero bytes. */ #if defined(__GNUC__) -#define WT_LEADING_ZEROS(x, i) \ - ((i) = ((x) == 0) ? (int)sizeof(x) : __builtin_clzll(x) >> 3) +#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) +#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) +#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. + * 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; + uint8_t *p; + int len, lz, shift; - WT_LEADING_ZEROS(x, lz); - len = (int)sizeof(x) - lz; - WT_SIZE_CHECK_PACK(len + 1, maxlen); - p = *pp; + WT_LEADING_ZEROS(x, lz); + len = (int)sizeof(x) - lz; + WT_SIZE_CHECK_PACK(len + 1, maxlen); + p = *pp; - /* There are four bits we can use in the first byte. */ - *p++ |= (len & 0xf); + /* 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); + for (shift = (len - 1) << 3; len != 0; --len, shift -= 8) + *p++ = (uint8_t)(x >> shift); - *pp = p; - return (0); + *pp = p; + return (0); } /* * __wt_vpack_negint -- - * Packs a negative variable-length integer in the specified location. + * 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_PACK(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); + uint8_t *p; + int len, lz, shift; + + WT_LEADING_ZEROS(~x, lz); + len = (int)sizeof(x) - lz; + WT_SIZE_CHECK_PACK(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. + * 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; - uint8_t len; - const uint8_t *p; + uint64_t x; + uint8_t len; + const uint8_t *p; - /* There are four length bits in the first byte. */ - p = *pp; - len = (*p++ & 0xf); - WT_SIZE_CHECK_UNPACK(len + 1, maxlen); + /* There are four length bits in the first byte. */ + p = *pp; + len = (*p++ & 0xf); + WT_SIZE_CHECK_UNPACK(len + 1, maxlen); - for (x = 0; len != 0; --len) - x = (x << 8) | *p++; + for (x = 0; len != 0; --len) + x = (x << 8) | *p++; - *retp = x; - *pp = p; - return (0); + *retp = x; + *pp = p; + return (0); } /* * __wt_vunpack_negint -- - * Reads a variable-length negative integer from the specified location. + * 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; - uint8_t len; - const uint8_t *p; + uint64_t x; + uint8_t len; + const uint8_t *p; - /* There are four length bits in the first byte. */ - p = *pp; - len = (int)sizeof(x) - (*p++ & 0xf); - WT_SIZE_CHECK_UNPACK(len + 1, maxlen); + /* There are four length bits in the first byte. */ + p = *pp; + len = (int)sizeof(x) - (*p++ & 0xf); + WT_SIZE_CHECK_UNPACK(len + 1, maxlen); - for (x = UINT64_MAX; len != 0; --len) - x = (x << 8) | *p++; + for (x = UINT64_MAX; len != 0; --len) + x = (x << 8) | *p++; - *retp = x; - *pp = p; - return (0); + *retp = x; + *pp = p; + return (0); } /* * __wt_vpack_uint -- - * Variable-sized packing for unsigned integers + * 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_PACK(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_PACK(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); + uint8_t *p; + + WT_SIZE_CHECK_PACK(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_PACK(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 + * 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_PACK(1, maxlen); - p = *pp; - if (x < NEG_2BYTE_MIN) { - *p = NEG_MULTI_MARKER; - return (__wt_vpack_negint(pp, maxlen, (uint64_t)x)); - } - if (x < NEG_1BYTE_MIN) { - WT_SIZE_CHECK_PACK(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); + uint8_t *p; + + WT_SIZE_CHECK_PACK(1, maxlen); + p = *pp; + if (x < NEG_2BYTE_MIN) { + *p = NEG_MULTI_MARKER; + return (__wt_vpack_negint(pp, maxlen, (uint64_t)x)); + } + if (x < NEG_1BYTE_MIN) { + WT_SIZE_CHECK_PACK(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 + * 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_UNPACK(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_UNPACK(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); + const uint8_t *p; + + WT_SIZE_CHECK_UNPACK(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_UNPACK(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 + * 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_UNPACK(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_UNPACK(2, maxlen); - *xp = (int64_t)(GET_BITS(*p++, 5, 0) << 8); - *xp |= *p++; - *xp += NEG_2BYTE_MIN; - 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); + const uint8_t *p; + + WT_SIZE_CHECK_UNPACK(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_UNPACK(2, maxlen); + *xp = (int64_t)(GET_BITS(*p++, 5, 0) << 8); + *xp |= *p++; + *xp += NEG_2BYTE_MIN; + 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. + * Return the packed size of a positive variable-length integer. */ static inline size_t __wt_vsize_posint(uint64_t x) { - int lz; + int lz; - WT_LEADING_ZEROS(x, lz); - return ((size_t)(WT_INTPACK64_MAXSIZE - 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. + * Return the packed size of a negative variable-length integer. */ static inline size_t __wt_vsize_negint(uint64_t x) { - int lz; + int lz; - WT_LEADING_ZEROS(~x, lz); - return (size_t)(WT_INTPACK64_MAXSIZE - lz); + WT_LEADING_ZEROS(~x, lz); + return (size_t)(WT_INTPACK64_MAXSIZE - lz); } /* * __wt_vsize_uint -- - * Return the packed size of an unsigned integer. + * 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); - if (x <= POS_2BYTE_MAX + 1) - return (2); - x -= POS_2BYTE_MAX + 1; - return (__wt_vsize_posint(x)); + if (x <= POS_1BYTE_MAX) + return (1); + if (x <= POS_2BYTE_MAX + 1) + return (2); + x -= POS_2BYTE_MAX + 1; + return (__wt_vsize_posint(x)); } /* * __wt_vsize_int -- - * Return the packed size of a signed integer. + * 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)); - if (x < NEG_1BYTE_MIN) - return (2); - if (x < 0) - return (1); - /* For non-negative values, use the unsigned code above. */ - return (__wt_vsize_uint((uint64_t)x)); + if (x < NEG_2BYTE_MIN) + return (__wt_vsize_negint((uint64_t)x)); + if (x < NEG_1BYTE_MIN) + return (2); + if (x < 0) + return (1); + /* For non-negative values, use the unsigned code above. */ + return (__wt_vsize_uint((uint64_t)x)); } |