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(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 */
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(++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(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_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(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
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.