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