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
EncodeFixed32(char * buf,uint32_t value)9 void EncodeFixed32(char* buf, uint32_t value) {
10 if (port::kLittleEndian) {
11 memcpy(buf, &value, sizeof(value));
12 } else {
13 buf[0] = value & 0xff;
14 buf[1] = (value >> 8) & 0xff;
15 buf[2] = (value >> 16) & 0xff;
16 buf[3] = (value >> 24) & 0xff;
17 }
18 }
19
EncodeFixed64(char * buf,uint64_t value)20 void EncodeFixed64(char* buf, uint64_t value) {
21 if (port::kLittleEndian) {
22 memcpy(buf, &value, sizeof(value));
23 } else {
24 buf[0] = value & 0xff;
25 buf[1] = (value >> 8) & 0xff;
26 buf[2] = (value >> 16) & 0xff;
27 buf[3] = (value >> 24) & 0xff;
28 buf[4] = (value >> 32) & 0xff;
29 buf[5] = (value >> 40) & 0xff;
30 buf[6] = (value >> 48) & 0xff;
31 buf[7] = (value >> 56) & 0xff;
32 }
33 }
34
PutFixed32(std::string * dst,uint32_t value)35 void PutFixed32(std::string* dst, uint32_t value) {
36 char buf[sizeof(value)];
37 EncodeFixed32(buf, value);
38 dst->append(buf, sizeof(buf));
39 }
40
PutFixed64(std::string * dst,uint64_t value)41 void PutFixed64(std::string* dst, uint64_t value) {
42 char buf[sizeof(value)];
43 EncodeFixed64(buf, value);
44 dst->append(buf, sizeof(buf));
45 }
46
EncodeVarint32(char * dst,uint32_t v)47 char* EncodeVarint32(char* dst, uint32_t v) {
48 // Operate on characters as unsigneds
49 unsigned char* ptr = reinterpret_cast<unsigned char*>(dst);
50 static const int B = 128;
51 if (v < (1<<7)) {
52 *(ptr++) = v;
53 } else if (v < (1<<14)) {
54 *(ptr++) = v | B;
55 *(ptr++) = v>>7;
56 } else if (v < (1<<21)) {
57 *(ptr++) = v | B;
58 *(ptr++) = (v>>7) | B;
59 *(ptr++) = v>>14;
60 } else if (v < (1<<28)) {
61 *(ptr++) = v | B;
62 *(ptr++) = (v>>7) | B;
63 *(ptr++) = (v>>14) | B;
64 *(ptr++) = v>>21;
65 } else {
66 *(ptr++) = v | B;
67 *(ptr++) = (v>>7) | B;
68 *(ptr++) = (v>>14) | B;
69 *(ptr++) = (v>>21) | B;
70 *(ptr++) = v>>28;
71 }
72 return reinterpret_cast<char*>(ptr);
73 }
74
PutVarint32(std::string * dst,uint32_t v)75 void PutVarint32(std::string* dst, uint32_t v) {
76 char buf[5];
77 char* ptr = EncodeVarint32(buf, v);
78 dst->append(buf, ptr - buf);
79 }
80
EncodeVarint64(char * dst,uint64_t v)81 char* EncodeVarint64(char* dst, uint64_t v) {
82 static const int B = 128;
83 unsigned char* ptr = reinterpret_cast<unsigned char*>(dst);
84 while (v >= B) {
85 *(ptr++) = (v & (B-1)) | B;
86 v >>= 7;
87 }
88 *(ptr++) = static_cast<unsigned char>(v);
89 return reinterpret_cast<char*>(ptr);
90 }
91
PutVarint64(std::string * dst,uint64_t v)92 void PutVarint64(std::string* dst, uint64_t v) {
93 char buf[10];
94 char* ptr = EncodeVarint64(buf, v);
95 dst->append(buf, ptr - buf);
96 }
97
PutLengthPrefixedSlice(std::string * dst,const Slice & value)98 void PutLengthPrefixedSlice(std::string* dst, const Slice& value) {
99 PutVarint32(dst, value.size());
100 dst->append(value.data(), value.size());
101 }
102
VarintLength(uint64_t v)103 int VarintLength(uint64_t v) {
104 int len = 1;
105 while (v >= 128) {
106 v >>= 7;
107 len++;
108 }
109 return len;
110 }
111
GetVarint32PtrFallback(const char * p,const char * limit,uint32_t * value)112 const char* GetVarint32PtrFallback(const char* p,
113 const char* limit,
114 uint32_t* value) {
115 uint32_t result = 0;
116 for (uint32_t shift = 0; shift <= 28 && p < limit; shift += 7) {
117 uint32_t byte = *(reinterpret_cast<const unsigned char*>(p));
118 p++;
119 if (byte & 128) {
120 // More bytes are present
121 result |= ((byte & 127) << shift);
122 } else {
123 result |= (byte << shift);
124 *value = result;
125 return reinterpret_cast<const char*>(p);
126 }
127 }
128 return NULL;
129 }
130
GetVarint32(Slice * input,uint32_t * value)131 bool GetVarint32(Slice* input, uint32_t* value) {
132 const char* p = input->data();
133 const char* limit = p + input->size();
134 const char* q = GetVarint32Ptr(p, limit, value);
135 if (q == NULL) {
136 return false;
137 } else {
138 *input = Slice(q, limit - q);
139 return true;
140 }
141 }
142
GetVarint64Ptr(const char * p,const char * limit,uint64_t * value)143 const char* GetVarint64Ptr(const char* p, const char* limit, uint64_t* value) {
144 uint64_t result = 0;
145 for (uint32_t shift = 0; shift <= 63 && p < limit; shift += 7) {
146 uint64_t byte = *(reinterpret_cast<const unsigned char*>(p));
147 p++;
148 if (byte & 128) {
149 // More bytes are present
150 result |= ((byte & 127) << shift);
151 } else {
152 result |= (byte << shift);
153 *value = result;
154 return reinterpret_cast<const char*>(p);
155 }
156 }
157 return NULL;
158 }
159
GetVarint64(Slice * input,uint64_t * value)160 bool GetVarint64(Slice* input, uint64_t* value) {
161 const char* p = input->data();
162 const char* limit = p + input->size();
163 const char* q = GetVarint64Ptr(p, limit, value);
164 if (q == NULL) {
165 return false;
166 } else {
167 *input = Slice(q, limit - q);
168 return true;
169 }
170 }
171
GetLengthPrefixedSlice(const char * p,const char * limit,Slice * result)172 const char* GetLengthPrefixedSlice(const char* p, const char* limit,
173 Slice* result) {
174 uint32_t len;
175 p = GetVarint32Ptr(p, limit, &len);
176 if (p == NULL) return NULL;
177 if (p + len > limit) return NULL;
178 *result = Slice(p, len);
179 return p + len;
180 }
181
GetLengthPrefixedSlice(Slice * input,Slice * result)182 bool GetLengthPrefixedSlice(Slice* input, Slice* result) {
183 uint32_t len;
184 if (GetVarint32(input, &len) &&
185 input->size() >= len) {
186 *result = Slice(input->data(), len);
187 input->remove_prefix(len);
188 return true;
189 } else {
190 return false;
191 }
192 }
193
194 } // namespace leveldb
195