diff options
author | Kent Overstreet <kent.overstreet@gmail.com> | 2020-11-05 23:39:33 -0500 |
---|---|---|
committer | Kent Overstreet <kent.overstreet@linux.dev> | 2023-10-22 17:08:46 -0400 |
commit | a3e7226268b26f0976f64ce8b0644daae28cafff (patch) | |
tree | d7f5b2a8732d3167655dc28a29bfca45dea97904 /fs/bcachefs/varint.c | |
parent | b3d1e6cab2dfcdfef5fc35659a8f33a75ae5904e (diff) | |
download | linux-a3e7226268b26f0976f64ce8b0644daae28cafff.tar.gz linux-a3e7226268b26f0976f64ce8b0644daae28cafff.tar.bz2 linux-a3e7226268b26f0976f64ce8b0644daae28cafff.zip |
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>
Diffstat (limited to 'fs/bcachefs/varint.c')
-rw-r--r-- | fs/bcachefs/varint.c | 43 |
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; +} |