1// SPDX-License-Identifier: GPL-2.0
  2
  3#include <linux/bitops.h>
  4#include <linux/math.h>
  5#include <linux/string.h>
  6#include <asm/unaligned.h>
  7
  8#ifdef CONFIG_VALGRIND
  9#include <valgrind/memcheck.h>
 10#endif
 11
 12#include "varint.h"
 13
 14/**
 15 * bch2_varint_encode - encode a variable length integer
 16 * @out:	destination to encode to
 17 * @v:		unsigned integer to encode
 18 * Returns:	size in bytes of the encoded integer - at most 9 bytes
 19 */
 20int bch2_varint_encode(u8 *out, u64 v)
 21{
 22	unsigned bits = fls64(v|1);
 23	unsigned bytes = DIV_ROUND_UP(bits, 7);
 24	__le64 v_le;
 25
 26	if (likely(bytes < 9)) {
 27		v <<= bytes;
 28		v |= ~(~0 << (bytes - 1));
 29		v_le = cpu_to_le64(v);
 30		memcpy(out, &v_le, bytes);
 31	} else {
 32		*out++ = 255;
 33		bytes = 9;
 34		put_unaligned_le64(v, out);
 35	}
 36
 37	return bytes;
 38}
 39
 40/**
 41 * bch2_varint_decode - encode a variable length integer
 42 * @in:		varint to decode
 43 * @end:	end of buffer to decode from
 44 * @out:	on success, decoded integer
 45 * Returns:	size in bytes of the decoded integer - or -1 on failure (would
 46 * have read past the end of the buffer)
 47 */
 48int bch2_varint_decode(const u8 *in, const u8 *end, u64 *out)
 49{
 50	unsigned bytes = likely(in < end)
 51		? ffz(*in & 255) + 1
 52		: 1;
 53	u64 v;
 54
 55	if (unlikely(in + bytes > end))
 56		return -1;
 57
 58	if (likely(bytes < 9)) {
 59		__le64 v_le = 0;
 60
 61		memcpy(&v_le, in, bytes);
 62		v = le64_to_cpu(v_le);
 63		v >>= bytes;
 64	} else {
 65		v = get_unaligned_le64(++in);
 66	}
 67
 68	*out = v;
 69	return bytes;
 70}
 71
 72/**
 73 * bch2_varint_encode_fast - fast version of bch2_varint_encode
 74 * @out:	destination to encode to
 75 * @v:		unsigned integer to encode
 76 * Returns:	size in bytes of the encoded integer - at most 9 bytes
 77 *
 78 * This version assumes it's always safe to write 8 bytes to @out, even if the
 79 * encoded integer would be smaller.
 80 */
 81int bch2_varint_encode_fast(u8 *out, u64 v)
 82{
 83	unsigned bits = fls64(v|1);
 84	unsigned bytes = DIV_ROUND_UP(bits, 7);
 85
 86	if (likely(bytes < 9)) {
 87		v <<= bytes;
 88		v |= ~(~0 << (bytes - 1));
 89	} else {
 90		*out++ = 255;
 91		bytes = 9;
 92	}
 93
 94	put_unaligned_le64(v, out);
 95	return bytes;
 96}
 97
 98/**
 99 * bch2_varint_decode_fast - fast version of bch2_varint_decode
100 * @in:		varint to decode
101 * @end:	end of buffer to decode from
102 * @out:	on success, decoded integer
103 * Returns:	size in bytes of the decoded integer - or -1 on failure (would
104 * have read past the end of the buffer)
105 *
106 * This version assumes that it is safe to read at most 8 bytes past the end of
107 * @end (we still return an error if the varint extends past @end).
108 */
109int bch2_varint_decode_fast(const u8 *in, const u8 *end, u64 *out)
110{
111#ifdef CONFIG_VALGRIND
112	VALGRIND_MAKE_MEM_DEFINED(in, 8);
113#endif
114	u64 v = get_unaligned_le64(in);
115	unsigned bytes = ffz(*in) + 1;
116
117	if (unlikely(in + bytes > end))
118		return -1;
119
120	if (likely(bytes < 9)) {
121		v >>= bytes;
122		v &= ~(~0ULL << (7 * bytes));
123	} else {
124		v = get_unaligned_le64(++in);
125	}
126
127	*out = v;
128	return bytes;
129}