]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
2 | // This source code is licensed under both the GPLv2 (found in the |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
7c673cae FG |
5 | // |
6 | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. | |
7 | // Use of this source code is governed by a BSD-style license that can be | |
8 | // found in the LICENSE file. See the AUTHORS file for names of contributors. | |
9 | // | |
20effc67 | 10 | // Encoding independent of machine byte order: |
7c673cae | 11 | // * Fixed-length numbers are encoded with least-significant byte first |
20effc67 | 12 | // (little endian, native order on Intel and others) |
7c673cae FG |
13 | // * In addition we support variable length "varint" encoding |
14 | // * Strings are encoded prefixed by their length in varint format | |
20effc67 TL |
15 | // |
16 | // Some related functions are provided in coding_lean.h | |
7c673cae FG |
17 | |
18 | #pragma once | |
19 | #include <algorithm> | |
7c673cae FG |
20 | #include <string> |
21 | ||
7c673cae | 22 | #include "port/port.h" |
20effc67 TL |
23 | #include "rocksdb/slice.h" |
24 | #include "util/coding_lean.h" | |
7c673cae FG |
25 | |
26 | // Some processors does not allow unaligned access to memory | |
27 | #if defined(__sparc) | |
1e59de90 | 28 | #define PLATFORM_UNALIGNED_ACCESS_NOT_ALLOWED |
7c673cae FG |
29 | #endif |
30 | ||
f67539c2 | 31 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
32 | |
33 | // The maximum length of a varint in bytes for 64-bit. | |
1e59de90 | 34 | const uint32_t kMaxVarint64Length = 10; |
7c673cae FG |
35 | |
36 | // Standard Put... routines append to a string | |
11fdf7f2 | 37 | extern void PutFixed16(std::string* dst, uint16_t value); |
7c673cae FG |
38 | extern void PutFixed32(std::string* dst, uint32_t value); |
39 | extern void PutFixed64(std::string* dst, uint64_t value); | |
40 | extern void PutVarint32(std::string* dst, uint32_t value); | |
41 | extern void PutVarint32Varint32(std::string* dst, uint32_t value1, | |
42 | uint32_t value2); | |
43 | extern void PutVarint32Varint32Varint32(std::string* dst, uint32_t value1, | |
44 | uint32_t value2, uint32_t value3); | |
45 | extern void PutVarint64(std::string* dst, uint64_t value); | |
46 | extern void PutVarint64Varint64(std::string* dst, uint64_t value1, | |
47 | uint64_t value2); | |
48 | extern void PutVarint32Varint64(std::string* dst, uint32_t value1, | |
49 | uint64_t value2); | |
50 | extern void PutVarint32Varint32Varint64(std::string* dst, uint32_t value1, | |
51 | uint32_t value2, uint64_t value3); | |
52 | extern void PutLengthPrefixedSlice(std::string* dst, const Slice& value); | |
53 | extern void PutLengthPrefixedSliceParts(std::string* dst, | |
54 | const SliceParts& slice_parts); | |
f67539c2 TL |
55 | extern void PutLengthPrefixedSlicePartsWithPadding( |
56 | std::string* dst, const SliceParts& slice_parts, size_t pad_sz); | |
7c673cae FG |
57 | |
58 | // Standard Get... routines parse a value from the beginning of a Slice | |
59 | // and advance the slice past the parsed value. | |
60 | extern bool GetFixed64(Slice* input, uint64_t* value); | |
61 | extern bool GetFixed32(Slice* input, uint32_t* value); | |
11fdf7f2 | 62 | extern bool GetFixed16(Slice* input, uint16_t* value); |
7c673cae FG |
63 | extern bool GetVarint32(Slice* input, uint32_t* value); |
64 | extern bool GetVarint64(Slice* input, uint64_t* value); | |
f67539c2 | 65 | extern bool GetVarsignedint64(Slice* input, int64_t* value); |
7c673cae FG |
66 | extern bool GetLengthPrefixedSlice(Slice* input, Slice* result); |
67 | // This function assumes data is well-formed. | |
68 | extern Slice GetLengthPrefixedSlice(const char* data); | |
69 | ||
70 | extern Slice GetSliceUntil(Slice* slice, char delimiter); | |
71 | ||
11fdf7f2 TL |
72 | // Borrowed from |
73 | // https://github.com/facebook/fbthrift/blob/449a5f77f9f9bae72c9eb5e78093247eef185c04/thrift/lib/cpp/util/VarintUtils-inl.h#L202-L208 | |
74 | constexpr inline uint64_t i64ToZigzag(const int64_t l) { | |
75 | return (static_cast<uint64_t>(l) << 1) ^ static_cast<uint64_t>(l >> 63); | |
76 | } | |
77 | inline int64_t zigzagToI64(uint64_t n) { | |
78 | return (n >> 1) ^ -static_cast<int64_t>(n & 1); | |
79 | } | |
80 | ||
7c673cae FG |
81 | // Pointer-based variants of GetVarint... These either store a value |
82 | // in *v and return a pointer just past the parsed value, or return | |
83 | // nullptr on error. These routines only look at bytes in the range | |
84 | // [p..limit-1] | |
1e59de90 TL |
85 | extern const char* GetVarint32Ptr(const char* p, const char* limit, |
86 | uint32_t* v); | |
87 | extern const char* GetVarint64Ptr(const char* p, const char* limit, | |
88 | uint64_t* v); | |
11fdf7f2 TL |
89 | inline const char* GetVarsignedint64Ptr(const char* p, const char* limit, |
90 | int64_t* value) { | |
91 | uint64_t u = 0; | |
92 | const char* ret = GetVarint64Ptr(p, limit, &u); | |
93 | *value = zigzagToI64(u); | |
94 | return ret; | |
95 | } | |
7c673cae FG |
96 | |
97 | // Returns the length of the varint32 or varint64 encoding of "v" | |
98 | extern int VarintLength(uint64_t v); | |
99 | ||
7c673cae FG |
100 | // Lower-level versions of Put... that write directly into a character buffer |
101 | // and return a pointer just past the last byte written. | |
102 | // REQUIRES: dst has enough space for the value being written | |
103 | extern char* EncodeVarint32(char* dst, uint32_t value); | |
104 | extern char* EncodeVarint64(char* dst, uint64_t value); | |
105 | ||
7c673cae | 106 | // Internal routine for use by fallback path of GetVarint32Ptr |
1e59de90 | 107 | extern const char* GetVarint32PtrFallback(const char* p, const char* limit, |
7c673cae | 108 | uint32_t* value); |
1e59de90 | 109 | inline const char* GetVarint32Ptr(const char* p, const char* limit, |
7c673cae FG |
110 | uint32_t* value) { |
111 | if (p < limit) { | |
112 | uint32_t result = *(reinterpret_cast<const unsigned char*>(p)); | |
113 | if ((result & 128) == 0) { | |
114 | *value = result; | |
115 | return p + 1; | |
116 | } | |
117 | } | |
118 | return GetVarint32PtrFallback(p, limit, value); | |
119 | } | |
120 | ||
7c673cae | 121 | // Pull the last 8 bits and cast it to a character |
11fdf7f2 TL |
122 | inline void PutFixed16(std::string* dst, uint16_t value) { |
123 | if (port::kLittleEndian) { | |
124 | dst->append(const_cast<const char*>(reinterpret_cast<char*>(&value)), | |
125 | sizeof(value)); | |
126 | } else { | |
127 | char buf[sizeof(value)]; | |
128 | EncodeFixed16(buf, value); | |
129 | dst->append(buf, sizeof(buf)); | |
130 | } | |
131 | } | |
132 | ||
7c673cae FG |
133 | inline void PutFixed32(std::string* dst, uint32_t value) { |
134 | if (port::kLittleEndian) { | |
135 | dst->append(const_cast<const char*>(reinterpret_cast<char*>(&value)), | |
1e59de90 | 136 | sizeof(value)); |
7c673cae FG |
137 | } else { |
138 | char buf[sizeof(value)]; | |
139 | EncodeFixed32(buf, value); | |
140 | dst->append(buf, sizeof(buf)); | |
141 | } | |
142 | } | |
143 | ||
144 | inline void PutFixed64(std::string* dst, uint64_t value) { | |
145 | if (port::kLittleEndian) { | |
146 | dst->append(const_cast<const char*>(reinterpret_cast<char*>(&value)), | |
1e59de90 | 147 | sizeof(value)); |
7c673cae FG |
148 | } else { |
149 | char buf[sizeof(value)]; | |
150 | EncodeFixed64(buf, value); | |
151 | dst->append(buf, sizeof(buf)); | |
152 | } | |
153 | } | |
154 | ||
155 | inline void PutVarint32(std::string* dst, uint32_t v) { | |
156 | char buf[5]; | |
157 | char* ptr = EncodeVarint32(buf, v); | |
158 | dst->append(buf, static_cast<size_t>(ptr - buf)); | |
159 | } | |
160 | ||
161 | inline void PutVarint32Varint32(std::string* dst, uint32_t v1, uint32_t v2) { | |
162 | char buf[10]; | |
163 | char* ptr = EncodeVarint32(buf, v1); | |
164 | ptr = EncodeVarint32(ptr, v2); | |
165 | dst->append(buf, static_cast<size_t>(ptr - buf)); | |
166 | } | |
167 | ||
168 | inline void PutVarint32Varint32Varint32(std::string* dst, uint32_t v1, | |
169 | uint32_t v2, uint32_t v3) { | |
170 | char buf[15]; | |
171 | char* ptr = EncodeVarint32(buf, v1); | |
172 | ptr = EncodeVarint32(ptr, v2); | |
173 | ptr = EncodeVarint32(ptr, v3); | |
174 | dst->append(buf, static_cast<size_t>(ptr - buf)); | |
175 | } | |
176 | ||
177 | inline char* EncodeVarint64(char* dst, uint64_t v) { | |
178 | static const unsigned int B = 128; | |
179 | unsigned char* ptr = reinterpret_cast<unsigned char*>(dst); | |
180 | while (v >= B) { | |
181 | *(ptr++) = (v & (B - 1)) | B; | |
182 | v >>= 7; | |
183 | } | |
184 | *(ptr++) = static_cast<unsigned char>(v); | |
185 | return reinterpret_cast<char*>(ptr); | |
186 | } | |
187 | ||
188 | inline void PutVarint64(std::string* dst, uint64_t v) { | |
11fdf7f2 | 189 | char buf[kMaxVarint64Length]; |
7c673cae FG |
190 | char* ptr = EncodeVarint64(buf, v); |
191 | dst->append(buf, static_cast<size_t>(ptr - buf)); | |
192 | } | |
193 | ||
11fdf7f2 TL |
194 | inline void PutVarsignedint64(std::string* dst, int64_t v) { |
195 | char buf[kMaxVarint64Length]; | |
196 | // Using Zigzag format to convert signed to unsigned | |
197 | char* ptr = EncodeVarint64(buf, i64ToZigzag(v)); | |
198 | dst->append(buf, static_cast<size_t>(ptr - buf)); | |
199 | } | |
200 | ||
7c673cae FG |
201 | inline void PutVarint64Varint64(std::string* dst, uint64_t v1, uint64_t v2) { |
202 | char buf[20]; | |
203 | char* ptr = EncodeVarint64(buf, v1); | |
204 | ptr = EncodeVarint64(ptr, v2); | |
205 | dst->append(buf, static_cast<size_t>(ptr - buf)); | |
206 | } | |
207 | ||
208 | inline void PutVarint32Varint64(std::string* dst, uint32_t v1, uint64_t v2) { | |
209 | char buf[15]; | |
210 | char* ptr = EncodeVarint32(buf, v1); | |
211 | ptr = EncodeVarint64(ptr, v2); | |
212 | dst->append(buf, static_cast<size_t>(ptr - buf)); | |
213 | } | |
214 | ||
215 | inline void PutVarint32Varint32Varint64(std::string* dst, uint32_t v1, | |
216 | uint32_t v2, uint64_t v3) { | |
217 | char buf[20]; | |
218 | char* ptr = EncodeVarint32(buf, v1); | |
219 | ptr = EncodeVarint32(ptr, v2); | |
220 | ptr = EncodeVarint64(ptr, v3); | |
221 | dst->append(buf, static_cast<size_t>(ptr - buf)); | |
222 | } | |
223 | ||
224 | inline void PutLengthPrefixedSlice(std::string* dst, const Slice& value) { | |
225 | PutVarint32(dst, static_cast<uint32_t>(value.size())); | |
226 | dst->append(value.data(), value.size()); | |
227 | } | |
228 | ||
f67539c2 | 229 | inline void PutLengthPrefixedSliceParts(std::string* dst, size_t total_bytes, |
7c673cae | 230 | const SliceParts& slice_parts) { |
7c673cae FG |
231 | for (int i = 0; i < slice_parts.num_parts; ++i) { |
232 | total_bytes += slice_parts.parts[i].size(); | |
233 | } | |
234 | PutVarint32(dst, static_cast<uint32_t>(total_bytes)); | |
235 | for (int i = 0; i < slice_parts.num_parts; ++i) { | |
236 | dst->append(slice_parts.parts[i].data(), slice_parts.parts[i].size()); | |
237 | } | |
238 | } | |
239 | ||
f67539c2 TL |
240 | inline void PutLengthPrefixedSliceParts(std::string* dst, |
241 | const SliceParts& slice_parts) { | |
242 | PutLengthPrefixedSliceParts(dst, /*total_bytes=*/0, slice_parts); | |
243 | } | |
244 | ||
245 | inline void PutLengthPrefixedSlicePartsWithPadding( | |
246 | std::string* dst, const SliceParts& slice_parts, size_t pad_sz) { | |
247 | PutLengthPrefixedSliceParts(dst, /*total_bytes=*/pad_sz, slice_parts); | |
248 | dst->append(pad_sz, '\0'); | |
249 | } | |
250 | ||
7c673cae FG |
251 | inline int VarintLength(uint64_t v) { |
252 | int len = 1; | |
253 | while (v >= 128) { | |
254 | v >>= 7; | |
255 | len++; | |
256 | } | |
257 | return len; | |
258 | } | |
259 | ||
260 | inline bool GetFixed64(Slice* input, uint64_t* value) { | |
261 | if (input->size() < sizeof(uint64_t)) { | |
262 | return false; | |
263 | } | |
264 | *value = DecodeFixed64(input->data()); | |
265 | input->remove_prefix(sizeof(uint64_t)); | |
266 | return true; | |
267 | } | |
268 | ||
269 | inline bool GetFixed32(Slice* input, uint32_t* value) { | |
270 | if (input->size() < sizeof(uint32_t)) { | |
271 | return false; | |
272 | } | |
273 | *value = DecodeFixed32(input->data()); | |
274 | input->remove_prefix(sizeof(uint32_t)); | |
275 | return true; | |
276 | } | |
277 | ||
11fdf7f2 TL |
278 | inline bool GetFixed16(Slice* input, uint16_t* value) { |
279 | if (input->size() < sizeof(uint16_t)) { | |
280 | return false; | |
281 | } | |
282 | *value = DecodeFixed16(input->data()); | |
283 | input->remove_prefix(sizeof(uint16_t)); | |
284 | return true; | |
285 | } | |
286 | ||
7c673cae FG |
287 | inline bool GetVarint32(Slice* input, uint32_t* value) { |
288 | const char* p = input->data(); | |
289 | const char* limit = p + input->size(); | |
290 | const char* q = GetVarint32Ptr(p, limit, value); | |
291 | if (q == nullptr) { | |
292 | return false; | |
293 | } else { | |
294 | *input = Slice(q, static_cast<size_t>(limit - q)); | |
295 | return true; | |
296 | } | |
297 | } | |
298 | ||
299 | inline bool GetVarint64(Slice* input, uint64_t* value) { | |
300 | const char* p = input->data(); | |
301 | const char* limit = p + input->size(); | |
302 | const char* q = GetVarint64Ptr(p, limit, value); | |
303 | if (q == nullptr) { | |
304 | return false; | |
305 | } else { | |
306 | *input = Slice(q, static_cast<size_t>(limit - q)); | |
307 | return true; | |
308 | } | |
309 | } | |
310 | ||
f67539c2 TL |
311 | inline bool GetVarsignedint64(Slice* input, int64_t* value) { |
312 | const char* p = input->data(); | |
313 | const char* limit = p + input->size(); | |
314 | const char* q = GetVarsignedint64Ptr(p, limit, value); | |
315 | if (q == nullptr) { | |
316 | return false; | |
317 | } else { | |
318 | *input = Slice(q, static_cast<size_t>(limit - q)); | |
319 | return true; | |
320 | } | |
321 | } | |
322 | ||
7c673cae FG |
323 | inline bool GetLengthPrefixedSlice(Slice* input, Slice* result) { |
324 | uint32_t len = 0; | |
325 | if (GetVarint32(input, &len) && input->size() >= len) { | |
326 | *result = Slice(input->data(), len); | |
327 | input->remove_prefix(len); | |
328 | return true; | |
329 | } else { | |
330 | return false; | |
331 | } | |
332 | } | |
333 | ||
334 | inline Slice GetLengthPrefixedSlice(const char* data) { | |
335 | uint32_t len = 0; | |
336 | // +5: we assume "data" is not corrupted | |
337 | // unsigned char is 7 bits, uint32_t is 32 bits, need 5 unsigned char | |
338 | auto p = GetVarint32Ptr(data, data + 5 /* limit */, &len); | |
339 | return Slice(p, len); | |
340 | } | |
341 | ||
342 | inline Slice GetSliceUntil(Slice* slice, char delimiter) { | |
343 | uint32_t len = 0; | |
344 | for (len = 0; len < slice->size() && slice->data()[len] != delimiter; ++len) { | |
345 | // nothing | |
346 | } | |
347 | ||
348 | Slice ret(slice->data(), len); | |
349 | slice->remove_prefix(len + ((len < slice->size()) ? 1 : 0)); | |
350 | return ret; | |
351 | } | |
352 | ||
1e59de90 | 353 | template <class T> |
11fdf7f2 TL |
354 | #ifdef ROCKSDB_UBSAN_RUN |
355 | #if defined(__clang__) | |
356 | __attribute__((__no_sanitize__("alignment"))) | |
357 | #elif defined(__GNUC__) | |
358 | __attribute__((__no_sanitize_undefined__)) | |
359 | #endif | |
360 | #endif | |
1e59de90 TL |
361 | inline void |
362 | PutUnaligned(T* memory, const T& value) { | |
7c673cae | 363 | #if defined(PLATFORM_UNALIGNED_ACCESS_NOT_ALLOWED) |
1e59de90 | 364 | char* nonAlignedMemory = reinterpret_cast<char*>(memory); |
7c673cae FG |
365 | memcpy(nonAlignedMemory, reinterpret_cast<const char*>(&value), sizeof(T)); |
366 | #else | |
367 | *memory = value; | |
368 | #endif | |
369 | } | |
370 | ||
1e59de90 | 371 | template <class T> |
11fdf7f2 TL |
372 | #ifdef ROCKSDB_UBSAN_RUN |
373 | #if defined(__clang__) | |
374 | __attribute__((__no_sanitize__("alignment"))) | |
375 | #elif defined(__GNUC__) | |
376 | __attribute__((__no_sanitize_undefined__)) | |
377 | #endif | |
378 | #endif | |
1e59de90 TL |
379 | inline void |
380 | GetUnaligned(const T* memory, T* value) { | |
7c673cae | 381 | #if defined(PLATFORM_UNALIGNED_ACCESS_NOT_ALLOWED) |
1e59de90 | 382 | char* nonAlignedMemory = reinterpret_cast<char*>(value); |
7c673cae FG |
383 | memcpy(nonAlignedMemory, reinterpret_cast<const char*>(memory), sizeof(T)); |
384 | #else | |
385 | *value = *memory; | |
386 | #endif | |
387 | } | |
388 | ||
f67539c2 | 389 | } // namespace ROCKSDB_NAMESPACE |