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 | */ |
20 | int bch2_varint_encode(u8 *out, u64 v) |
21 | { |
22 | unsigned bits = fls64(x: 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(val: v, p: 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 | */ |
48 | int 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(p: ++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 | */ |
81 | int bch2_varint_encode_fast(u8 *out, u64 v) |
82 | { |
83 | unsigned bits = fls64(x: 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(val: v, p: 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 | */ |
109 | int 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(p: 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(p: ++in); |
125 | } |
126 | |
127 | *out = v; |
128 | return bytes; |
129 | } |
130 | |