diff options
Diffstat (limited to 'fs/bcachefs/varint.c')
-rw-r--r-- | fs/bcachefs/varint.c | 129 |
1 files changed, 129 insertions, 0 deletions
diff --git a/fs/bcachefs/varint.c b/fs/bcachefs/varint.c new file mode 100644 index 0000000000..cb4f33ed9a --- /dev/null +++ b/fs/bcachefs/varint.c @@ -0,0 +1,129 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include <linux/bitops.h> +#include <linux/math.h> +#include <linux/string.h> +#include <asm/unaligned.h> + +#ifdef CONFIG_VALGRIND +#include <valgrind/memcheck.h> +#endif + +#include "varint.h" + +/** + * bch2_varint_encode - encode a variable length integer + * @out: destination to encode to + * @v: unsigned integer to encode + * Returns: size in bytes of the encoded integer - at most 9 bytes + */ +int bch2_varint_encode(u8 *out, u64 v) +{ + unsigned bits = fls64(v|1); + unsigned bytes = DIV_ROUND_UP(bits, 7); + __le64 v_le; + + if (likely(bytes < 9)) { + v <<= bytes; + v |= ~(~0 << (bytes - 1)); + v_le = cpu_to_le64(v); + memcpy(out, &v_le, bytes); + } else { + *out++ = 255; + bytes = 9; + put_unaligned_le64(v, out); + } + + return bytes; +} + +/** + * bch2_varint_decode - encode a variable length integer + * @in: varint to decode + * @end: end of buffer to decode from + * @out: on success, decoded integer + * Returns: size in bytes of the decoded integer - or -1 on failure (would + * have read past the end of the buffer) + */ +int bch2_varint_decode(const u8 *in, const u8 *end, u64 *out) +{ + unsigned bytes = likely(in < end) + ? ffz(*in & 255) + 1 + : 1; + u64 v; + + if (unlikely(in + bytes > end)) + return -1; + + if (likely(bytes < 9)) { + __le64 v_le = 0; + + memcpy(&v_le, in, bytes); + v = le64_to_cpu(v_le); + v >>= bytes; + } else { + v = get_unaligned_le64(++in); + } + + *out = v; + return bytes; +} + +/** + * bch2_varint_encode_fast - fast version of bch2_varint_encode + * @out: destination to encode to + * @v: unsigned integer to encode + * Returns: size in bytes of the encoded integer - at most 9 bytes + * + * This version assumes it's always safe to write 8 bytes to @out, even if the + * encoded integer would be smaller. + */ +int bch2_varint_encode_fast(u8 *out, u64 v) +{ + unsigned bits = fls64(v|1); + unsigned bytes = DIV_ROUND_UP(bits, 7); + + if (likely(bytes < 9)) { + v <<= bytes; + v |= ~(~0 << (bytes - 1)); + } else { + *out++ = 255; + bytes = 9; + } + + put_unaligned_le64(v, out); + return bytes; +} + +/** + * bch2_varint_decode_fast - fast version of bch2_varint_decode + * @in: varint to decode + * @end: end of buffer to decode from + * @out: on success, decoded integer + * Returns: size in bytes of the decoded integer - or -1 on failure (would + * have read past the end of the buffer) + * + * This version assumes that it is safe to read at most 8 bytes past the end of + * @end (we still return an error if the varint extends past @end). + */ +int bch2_varint_decode_fast(const u8 *in, const u8 *end, u64 *out) +{ +#ifdef CONFIG_VALGRIND + VALGRIND_MAKE_MEM_DEFINED(in, 8); +#endif + u64 v = get_unaligned_le64(in); + unsigned bytes = ffz(*in) + 1; + + if (unlikely(in + bytes > end)) + return -1; + + if (likely(bytes < 9)) { + v >>= bytes; + v &= ~(~0ULL << (7 * bytes)); + } else { + v = get_unaligned_le64(++in); + } + + *out = v; + return bytes; +} |