1 // SPDX-License-Identifier: GPL-2.0 1 // SPDX-License-Identifier: GPL-2.0
2 2
3 #include <linux/bitops.h> 3 #include <linux/bitops.h>
4 #include <linux/math.h> 4 #include <linux/math.h>
5 #include <linux/string.h> 5 #include <linux/string.h>
6 #include <linux/unaligned.h> 6 #include <linux/unaligned.h>
7 7
8 #ifdef CONFIG_VALGRIND 8 #ifdef CONFIG_VALGRIND
9 #include <valgrind/memcheck.h> 9 #include <valgrind/memcheck.h>
10 #endif 10 #endif
11 11
12 #include "varint.h" 12 #include "varint.h"
13 13
14 /** 14 /**
15 * bch2_varint_encode - encode a variable leng 15 * bch2_varint_encode - encode a variable length integer
16 * @out: destination to encode to 16 * @out: destination to encode to
17 * @v: unsigned integer to encode 17 * @v: unsigned integer to encode
18 * Returns: size in bytes of the encoded i 18 * Returns: size in bytes of the encoded integer - at most 9 bytes
19 */ 19 */
20 int bch2_varint_encode(u8 *out, u64 v) 20 int bch2_varint_encode(u8 *out, u64 v)
21 { 21 {
22 unsigned bits = fls64(v|1); 22 unsigned bits = fls64(v|1);
23 unsigned bytes = DIV_ROUND_UP(bits, 7) 23 unsigned bytes = DIV_ROUND_UP(bits, 7);
24 __le64 v_le; 24 __le64 v_le;
25 25
26 if (likely(bytes < 9)) { 26 if (likely(bytes < 9)) {
27 v <<= bytes; 27 v <<= bytes;
28 v |= ~(~0 << (bytes - 1)); 28 v |= ~(~0 << (bytes - 1));
29 v_le = cpu_to_le64(v); 29 v_le = cpu_to_le64(v);
30 memcpy(out, &v_le, bytes); 30 memcpy(out, &v_le, bytes);
31 } else { 31 } else {
32 *out++ = 255; 32 *out++ = 255;
33 bytes = 9; 33 bytes = 9;
34 put_unaligned_le64(v, out); 34 put_unaligned_le64(v, out);
35 } 35 }
36 36
37 return bytes; 37 return bytes;
38 } 38 }
39 39
40 /** 40 /**
41 * bch2_varint_decode - encode a variable leng 41 * bch2_varint_decode - encode a variable length integer
42 * @in: varint to decode 42 * @in: varint to decode
43 * @end: end of buffer to decode from 43 * @end: end of buffer to decode from
44 * @out: on success, decoded integer 44 * @out: on success, decoded integer
45 * Returns: size in bytes of the decoded i 45 * Returns: size in bytes of the decoded integer - or -1 on failure (would
46 * have read past the end of the buffer) 46 * have read past the end of the buffer)
47 */ 47 */
48 int bch2_varint_decode(const u8 *in, const u8 48 int bch2_varint_decode(const u8 *in, const u8 *end, u64 *out)
49 { 49 {
50 unsigned bytes = likely(in < end) 50 unsigned bytes = likely(in < end)
51 ? ffz(*in & 255) + 1 51 ? ffz(*in & 255) + 1
52 : 1; 52 : 1;
53 u64 v; 53 u64 v;
54 54
55 if (unlikely(in + bytes > end)) 55 if (unlikely(in + bytes > end))
56 return -1; 56 return -1;
57 57
58 if (likely(bytes < 9)) { 58 if (likely(bytes < 9)) {
59 __le64 v_le = 0; 59 __le64 v_le = 0;
60 60
61 memcpy(&v_le, in, bytes); 61 memcpy(&v_le, in, bytes);
62 v = le64_to_cpu(v_le); 62 v = le64_to_cpu(v_le);
63 v >>= bytes; 63 v >>= bytes;
64 } else { 64 } else {
65 v = get_unaligned_le64(++in); 65 v = get_unaligned_le64(++in);
66 } 66 }
67 67
68 *out = v; 68 *out = v;
69 return bytes; 69 return bytes;
70 } 70 }
71 71
72 /** 72 /**
73 * bch2_varint_encode_fast - fast version of b 73 * bch2_varint_encode_fast - fast version of bch2_varint_encode
74 * @out: destination to encode to 74 * @out: destination to encode to
75 * @v: unsigned integer to encode 75 * @v: unsigned integer to encode
76 * Returns: size in bytes of the encoded i 76 * Returns: size in bytes of the encoded integer - at most 9 bytes
77 * 77 *
78 * This version assumes it's always safe to wr 78 * This version assumes it's always safe to write 8 bytes to @out, even if the
79 * encoded integer would be smaller. 79 * encoded integer would be smaller.
80 */ 80 */
81 int bch2_varint_encode_fast(u8 *out, u64 v) 81 int bch2_varint_encode_fast(u8 *out, u64 v)
82 { 82 {
83 unsigned bits = fls64(v|1); 83 unsigned bits = fls64(v|1);
84 unsigned bytes = DIV_ROUND_UP(bits, 7) 84 unsigned bytes = DIV_ROUND_UP(bits, 7);
85 85
86 if (likely(bytes < 9)) { 86 if (likely(bytes < 9)) {
87 v <<= bytes; 87 v <<= bytes;
88 v |= ~(~0U << (bytes - 1)); 88 v |= ~(~0U << (bytes - 1));
89 } else { 89 } else {
90 *out++ = 255; 90 *out++ = 255;
91 bytes = 9; 91 bytes = 9;
92 } 92 }
93 93
94 put_unaligned_le64(v, out); 94 put_unaligned_le64(v, out);
95 return bytes; 95 return bytes;
96 } 96 }
97 97
98 /** 98 /**
99 * bch2_varint_decode_fast - fast version of b 99 * bch2_varint_decode_fast - fast version of bch2_varint_decode
100 * @in: varint to decode 100 * @in: varint to decode
101 * @end: end of buffer to decode from 101 * @end: end of buffer to decode from
102 * @out: on success, decoded integer 102 * @out: on success, decoded integer
103 * Returns: size in bytes of the decoded i 103 * Returns: size in bytes of the decoded integer - or -1 on failure (would
104 * have read past the end of the buffer) 104 * have read past the end of the buffer)
105 * 105 *
106 * This version assumes that it is safe to rea 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 varin 107 * @end (we still return an error if the varint extends past @end).
108 */ 108 */
109 int bch2_varint_decode_fast(const u8 *in, cons 109 int bch2_varint_decode_fast(const u8 *in, const u8 *end, u64 *out)
110 { 110 {
111 #ifdef CONFIG_VALGRIND 111 #ifdef CONFIG_VALGRIND
112 VALGRIND_MAKE_MEM_DEFINED(in, 8); 112 VALGRIND_MAKE_MEM_DEFINED(in, 8);
113 #endif 113 #endif
114 u64 v = get_unaligned_le64(in); 114 u64 v = get_unaligned_le64(in);
115 unsigned bytes = ffz(*in) + 1; 115 unsigned bytes = ffz(*in) + 1;
116 116
117 if (unlikely(in + bytes > end)) 117 if (unlikely(in + bytes > end))
118 return -1; 118 return -1;
119 119
120 if (likely(bytes < 9)) { 120 if (likely(bytes < 9)) {
121 v >>= bytes; 121 v >>= bytes;
122 v &= ~(~0ULL << (7 * bytes)); 122 v &= ~(~0ULL << (7 * bytes));
123 } else { 123 } else {
124 v = get_unaligned_le64(++in); 124 v = get_unaligned_le64(++in);
125 } 125 }
126 126
127 *out = v; 127 *out = v;
128 return bytes; 128 return bytes;
129 } 129 }
130 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.