1 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. See the AUTHORS file for names of contributors.
4
5 #include "util/coding.h"
6
7 namespace leveldb {
8
PutFixed32(std::string * dst,uint32_t value)9 void PutFixed32(std::string* dst, uint32_t value) {
10 char buf[sizeof(value)];
11 EncodeFixed32(buf, value);
12 dst->append(buf, sizeof(buf));
13 }
14
PutFixed64(std::string * dst,uint64_t value)15 void PutFixed64(std::string* dst, uint64_t value) {
16 char buf[sizeof(value)];
17 EncodeFixed64(buf, value);
18 dst->append(buf, sizeof(buf));
19 }
20
EncodeVarint32(char * dst,uint32_t v)21 char* EncodeVarint32(char* dst, uint32_t v) {
22 // Operate on characters as unsigneds
23 uint8_t* ptr = reinterpret_cast<uint8_t*>(dst);
24 static const int B = 128;
25 if (v < (1 << 7)) {
26 *(ptr++) = v;
27 } else if (v < (1 << 14)) {
28 *(ptr++) = v | B;
29 *(ptr++) = v >> 7;
30 } else if (v < (1 << 21)) {
31 *(ptr++) = v | B;
32 *(ptr++) = (v >> 7) | B;
33 *(ptr++) = v >> 14;
34 } else if (v < (1 << 28)) {
35 *(ptr++) = v | B;
36 *(ptr++) = (v >> 7) | B;
37 *(ptr++) = (v >> 14) | B;
38 *(ptr++) = v >> 21;
39 } else {
40 *(ptr++) = v | B;
41 *(ptr++) = (v >> 7) | B;
42 *(ptr++) = (v >> 14) | B;
43 *(ptr++) = (v >> 21) | B;
44 *(ptr++) = v >> 28;
45 }
46 return reinterpret_cast<char*>(ptr);
47 }
48
PutVarint32(std::string * dst,uint32_t v)49 void PutVarint32(std::string* dst, uint32_t v) {
50 char buf[5];
51 char* ptr = EncodeVarint32(buf, v);
52 dst->append(buf, ptr - buf);
53 }
54
EncodeVarint64(char * dst,uint64_t v)55 char* EncodeVarint64(char* dst, uint64_t v) {
56 static const int B = 128;
57 uint8_t* ptr = reinterpret_cast<uint8_t*>(dst);
58 while (v >= B) {
59 *(ptr++) = v | B;
60 v >>= 7;
61 }
62 *(ptr++) = static_cast<uint8_t>(v);
63 return reinterpret_cast<char*>(ptr);
64 }
65
PutVarint64(std::string * dst,uint64_t v)66 void PutVarint64(std::string* dst, uint64_t v) {
67 char buf[10];
68 char* ptr = EncodeVarint64(buf, v);
69 dst->append(buf, ptr - buf);
70 }
71
PutLengthPrefixedSlice(std::string * dst,const Slice & value)72 void PutLengthPrefixedSlice(std::string* dst, const Slice& value) {
73 PutVarint32(dst, value.size());
74 dst->append(value.data(), value.size());
75 }
76
VarintLength(uint64_t v)77 int VarintLength(uint64_t v) {
78 int len = 1;
79 while (v >= 128) {
80 v >>= 7;
81 len++;
82 }
83 return len;
84 }
85
GetVarint32PtrFallback(const char * p,const char * limit,uint32_t * value)86 const char* GetVarint32PtrFallback(const char* p, const char* limit,
87 uint32_t* value) {
88 uint32_t result = 0;
89 for (uint32_t shift = 0; shift <= 28 && p < limit; shift += 7) {
90 uint32_t byte = *(reinterpret_cast<const uint8_t*>(p));
91 p++;
92 if (byte & 128) {
93 // More bytes are present
94 result |= ((byte & 127) << shift);
95 } else {
96 result |= (byte << shift);
97 *value = result;
98 return reinterpret_cast<const char*>(p);
99 }
100 }
101 return nullptr;
102 }
103
GetVarint32(Slice * input,uint32_t * value)104 bool GetVarint32(Slice* input, uint32_t* value) {
105 const char* p = input->data();
106 const char* limit = p + input->size();
107 const char* q = GetVarint32Ptr(p, limit, value);
108 if (q == nullptr) {
109 return false;
110 } else {
111 *input = Slice(q, limit - q);
112 return true;
113 }
114 }
115
GetVarint64Ptr(const char * p,const char * limit,uint64_t * value)116 const char* GetVarint64Ptr(const char* p, const char* limit, uint64_t* value) {
117 uint64_t result = 0;
118 for (uint32_t shift = 0; shift <= 63 && p < limit; shift += 7) {
119 uint64_t byte = *(reinterpret_cast<const uint8_t*>(p));
120 p++;
121 if (byte & 128) {
122 // More bytes are present
123 result |= ((byte & 127) << shift);
124 } else {
125 result |= (byte << shift);
126 *value = result;
127 return reinterpret_cast<const char*>(p);
128 }
129 }
130 return nullptr;
131 }
132
GetVarint64(Slice * input,uint64_t * value)133 bool GetVarint64(Slice* input, uint64_t* value) {
134 const char* p = input->data();
135 const char* limit = p + input->size();
136 const char* q = GetVarint64Ptr(p, limit, value);
137 if (q == nullptr) {
138 return false;
139 } else {
140 *input = Slice(q, limit - q);
141 return true;
142 }
143 }
144
GetLengthPrefixedSlice(const char * p,const char * limit,Slice * result)145 const char* GetLengthPrefixedSlice(const char* p, const char* limit,
146 Slice* result) {
147 uint32_t len;
148 p = GetVarint32Ptr(p, limit, &len);
149 if (p == nullptr) return nullptr;
150 if (p + len > limit) return nullptr;
151 *result = Slice(p, len);
152 return p + len;
153 }
154
GetLengthPrefixedSlice(Slice * input,Slice * result)155 bool GetLengthPrefixedSlice(Slice* input, Slice* result) {
156 uint32_t len;
157 if (GetVarint32(input, &len) && input->size() >= len) {
158 *result = Slice(input->data(), len);
159 input->remove_prefix(len);
160 return true;
161 } else {
162 return false;
163 }
164 }
165
166 } // namespace leveldb
167