bcachefs: New varints

Previous varint implementation used by the inode code was not nearly as
fast as it could have been; partly because it was attempting to encode
integers up to 96 bits (for timestamps) but this meant that encoding and
decoding the length required a table lookup.

Instead, we'll just encode timestamps greater than 64 bits as two
separate varints; this will make decoding/encoding of inodes
significantly faster overall.

Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

1 files changed, 43 insertions, 0 deletions

diff --git a/fs/bcachefs/varint.c b/fs/bcachefs/varint.c
new file mode 100644
index 000000000000..0f3d06a6a685
--- /dev/null
+++ b/fs/bcachefs/varint.c
@@ -0,0 +1,43 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bitops.h>
+#include <linux/math.h>
+#include <asm/unaligned.h>
+
+#include "varint.h"
+
+int bch2_varint_encode(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;
+}
+
+int bch2_varint_decode(const u8 *in, const u8 *end, u64 *out)
+{
+	u64 v = get_unaligned_le64(in);
+	unsigned bytes = ffz(v & 255) + 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;
+}