130 lines · c
1// SPDX-License-Identifier: GPL-2.02 3#include <linux/bitops.h>4#include <linux/math.h>5#include <linux/string.h>6#include <linux/unaligned.h>7 8#ifdef CONFIG_VALGRIND9#include <valgrind/memcheck.h>10#endif11 12#include "varint.h"13 14/**15 * bch2_varint_encode - encode a variable length integer16 * @out: destination to encode to17 * @v: unsigned integer to encode18 * Returns: size in bytes of the encoded integer - at most 9 bytes19 */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 integer42 * @in: varint to decode43 * @end: end of buffer to decode from44 * @out: on success, decoded integer45 * Returns: size in bytes of the decoded integer - or -1 on failure (would46 * 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) + 152 : 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_encode74 * @out: destination to encode to75 * @v: unsigned integer to encode76 * Returns: size in bytes of the encoded integer - at most 9 bytes77 *78 * This version assumes it's always safe to write 8 bytes to @out, even if the79 * 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 |= ~(~0U << (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_decode100 * @in: varint to decode101 * @end: end of buffer to decode from102 * @out: on success, decoded integer103 * Returns: size in bytes of the decoded integer - or -1 on failure (would104 * 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 of107 * @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_VALGRIND112 VALGRIND_MAKE_MEM_DEFINED(in, 8);113#endif114 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}130