1 /*
2 * Copyright (c) 2012 by Farsight Security, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
18 //
19 // Redistribution and use in source and binary forms, with or without
20 // modification, are permitted provided that the following conditions are
21 // met:
22 //
23 // * Redistributions of source code must retain the above copyright
24 // notice, this list of conditions and the following disclaimer.
25 //
26 // * Redistributions in binary form must reproduce the above
27 // copyright notice, this list of conditions and the following disclaimer
28 // in the documentation and/or other materials provided with the
29 // distribution.
30 //
31 // * Neither the name of Google Inc. nor the names of its
32 // contributors may be used to endorse or promote products derived from
33 // this software without specific prior written permission.
34 //
35 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
36 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
37 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
38 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
39 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
41 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
42 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
43 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
44 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
45 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
46
47 /*
48 * Copyright 2008, Dave Benson.
49 *
50 * Licensed under the Apache License, Version 2.0 (the "License"); you
51 * may not use this file except in compliance with the License. You may
52 * obtain a copy of the License at
53 *
54 * http://www.apache.org/licenses/LICENSE-2.0.
55 *
56 * Unless required by applicable law or agreed to in writing, software
57 * distributed under the License is distributed on an "AS IS" BASIS,
58 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
59 * implied. See the License for the specific language governing
60 * permissions and limitations under the License.
61 */
62
63 #include "mtbl-private.h"
64
65 unsigned
mtbl_varint_length(uint64_t v)66 mtbl_varint_length(uint64_t v)
67 {
68 unsigned len = 1;
69 while (v >= 128) {
70 v >>= 7;
71 len++;
72 }
73 return (len);
74 }
75
76 unsigned
mtbl_varint_length_packed(const uint8_t * data,size_t len_data)77 mtbl_varint_length_packed(const uint8_t *data, size_t len_data)
78 {
79 unsigned i = 0;
80 size_t len = len_data;
81 while (len--) {
82 if ((data[i] & 0x80) == 0)
83 break;
84 i++;
85 }
86 if (i == len_data)
87 return (0);
88 return (i + 1);
89 }
90
91 size_t
mtbl_varint_encode32(uint8_t * src_ptr,uint32_t v)92 mtbl_varint_encode32(uint8_t *src_ptr, uint32_t v)
93 {
94 static const unsigned B = 128;
95 uint8_t *ptr = src_ptr;
96 if (v < (1 << 7)) {
97 *(ptr++) = v;
98 } else if (v < (1 << 14)) {
99 *(ptr++) = v | B;
100 *(ptr++) = v >> 7;
101 } else if (v < (1 << 21)) {
102 *(ptr++) = v | B;
103 *(ptr++) = (v >> 7) | B;
104 *(ptr++) = v >> 14;
105 } else if (v < (1 << 28)) {
106 *(ptr++) = v | B;
107 *(ptr++) = (v >> 7) | B;
108 *(ptr++) = (v >> 14) | B;
109 *(ptr++) = v >> 21;
110 } else {
111 *(ptr++) = v | B;
112 *(ptr++) = (v >> 7) | B;
113 *(ptr++) = (v >> 14) | B;
114 *(ptr++) = (v >> 21) | B;
115 *(ptr++) = v >> 28;
116 }
117 return ((size_t) (ptr - src_ptr));
118 }
119
120 size_t
mtbl_varint_encode64(uint8_t * src_ptr,uint64_t v)121 mtbl_varint_encode64(uint8_t *src_ptr, uint64_t v)
122 {
123 static const unsigned B = 128;
124 uint8_t *ptr = src_ptr;
125 while (v >= B) {
126 *(ptr++) = (v & (B - 1)) | B;
127 v >>= 7;
128 }
129 *(ptr++) = (uint8_t) v;
130 return ((size_t) (ptr - src_ptr));
131 }
132
133 size_t
mtbl_varint_decode32(const uint8_t * data,uint32_t * value)134 mtbl_varint_decode32(const uint8_t *data, uint32_t *value)
135 {
136 unsigned len = mtbl_varint_length_packed(data, 5);
137 uint32_t val = data[0] & 0x7f;
138 if (len > 1) {
139 val |= ((data[1] & 0x7f) << 7);
140 if (len > 2) {
141 val |= ((data[2] & 0x7f) << 14);
142 if (len > 3) {
143 val |= ((data[3] & 0x7f) << 21);
144 if (len > 4)
145 val |= (data[4] << 28);
146 }
147 }
148 }
149 *value = val;
150 return ((size_t) len);
151 }
152
153 size_t
mtbl_varint_decode64(const uint8_t * data,uint64_t * value)154 mtbl_varint_decode64(const uint8_t *data, uint64_t *value)
155 {
156 unsigned shift, i;
157 unsigned len = mtbl_varint_length_packed(data, 10);
158 uint64_t val;
159 if (len < 5) {
160 size_t tmp_len;
161 uint32_t tmp;
162 tmp_len = mtbl_varint_decode32(data, &tmp);
163 *value = tmp;
164 return (tmp_len);
165 }
166 val = ((data[0] & 0x7f))
167 | ((data[1] & 0x7f) << 7)
168 | ((data[2] & 0x7f) << 14)
169 | ((data[3] & 0x7f) << 21);
170 shift = 28;
171 for (i = 4; i < len; i++) {
172 val |= (((uint64_t)(data[i] & 0x7f)) << shift);
173 shift += 7;
174 }
175 *value = val;
176 return ((size_t) len);
177 }
178