fs/bcachefs/varint.c

// SPDX-License-Identifier: GPL-2.0

#include <linux/bitops.h>
#include <linux/math.h>
#include <linux/string.h>
#include <linux/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 |= ~(~0U << (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;
}