Line data Source code
1 : // Copyright 2011 Google Inc. All Rights Reserved.
2 : //
3 : // Redistribution and use in source and binary forms, with or without
4 : // modification, are permitted provided that the following conditions are
5 : // met:
6 : //
7 : // * Redistributions of source code must retain the above copyright
8 : // notice, this list of conditions and the following disclaimer.
9 : // * Redistributions in binary form must reproduce the above
10 : // copyright notice, this list of conditions and the following disclaimer
11 : // in the documentation and/or other materials provided with the
12 : // distribution.
13 : // * Neither the name of Google Inc. nor the names of its
14 : // contributors may be used to endorse or promote products derived from
15 : // this software without specific prior written permission.
16 : //
17 : // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 : // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 : // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 : // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 : // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 : // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 : // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 : // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 : // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 : // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 : // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 : //
29 : // Various stubs for the open-source version of Snappy.
30 :
31 : #ifndef THIRD_PARTY_SNAPPY_OPENSOURCE_SNAPPY_STUBS_INTERNAL_H_
32 : #define THIRD_PARTY_SNAPPY_OPENSOURCE_SNAPPY_STUBS_INTERNAL_H_
33 :
34 : #ifdef HAVE_CONFIG_H
35 : #include "config.h"
36 : #endif
37 :
38 : #include <string>
39 :
40 : #include <assert.h>
41 : #include <stdlib.h>
42 : #include <string.h>
43 :
44 : #ifdef HAVE_SYS_MMAN_H
45 : #include <sys/mman.h>
46 : #endif
47 :
48 : #include "snappy-stubs-public.h"
49 :
50 : #if defined(__x86_64__)
51 :
52 : // Enable 64-bit optimized versions of some routines.
53 : #define ARCH_K8 1
54 :
55 : #endif
56 :
57 : // Needed by OS X, among others.
58 : #ifndef MAP_ANONYMOUS
59 : #define MAP_ANONYMOUS MAP_ANON
60 : #endif
61 :
62 : // Pull in std::min, std::ostream, and the likes. This is safe because this
63 : // header file is never used from any public header files.
64 : using namespace std;
65 :
66 : // The size of an array, if known at compile-time.
67 : // Will give unexpected results if used on a pointer.
68 : // We undefine it first, since some compilers already have a definition.
69 : #ifdef ARRAYSIZE
70 : #undef ARRAYSIZE
71 : #endif
72 : #define ARRAYSIZE(a) (sizeof(a) / sizeof(*(a)))
73 :
74 : // Static prediction hints.
75 : #ifdef HAVE_BUILTIN_EXPECT
76 : #define PREDICT_FALSE(x) (__builtin_expect(x, 0))
77 : #define PREDICT_TRUE(x) (__builtin_expect(!!(x), 1))
78 : #else
79 : #define PREDICT_FALSE(x) x
80 : #define PREDICT_TRUE(x) x
81 : #endif
82 :
83 : // This is only used for recomputing the tag byte table used during
84 : // decompression; for simplicity we just remove it from the open-source
85 : // version (anyone who wants to regenerate it can just do the call
86 : // themselves within main()).
87 : #define DEFINE_bool(flag_name, default_value, description) \
88 : bool FLAGS_ ## flag_name = default_value
89 : #define DECLARE_bool(flag_name) \
90 : extern bool FLAGS_ ## flag_name
91 :
92 : namespace snappy {
93 :
94 : static const uint32 kuint32max = static_cast<uint32>(0xFFFFFFFF);
95 : static const int64 kint64max = static_cast<int64>(0x7FFFFFFFFFFFFFFFLL);
96 :
97 : // Potentially unaligned loads and stores.
98 :
99 : // x86 and PowerPC can simply do these loads and stores native.
100 :
101 : #if defined(__i386__) || defined(__x86_64__) || defined(__powerpc__)
102 :
103 : #define UNALIGNED_LOAD16(_p) (*reinterpret_cast<const uint16 *>(_p))
104 : #define UNALIGNED_LOAD32(_p) (*reinterpret_cast<const uint32 *>(_p))
105 : #define UNALIGNED_LOAD64(_p) (*reinterpret_cast<const uint64 *>(_p))
106 :
107 : #define UNALIGNED_STORE16(_p, _val) (*reinterpret_cast<uint16 *>(_p) = (_val))
108 : #define UNALIGNED_STORE32(_p, _val) (*reinterpret_cast<uint32 *>(_p) = (_val))
109 : #define UNALIGNED_STORE64(_p, _val) (*reinterpret_cast<uint64 *>(_p) = (_val))
110 :
111 : // ARMv7 and newer support native unaligned accesses, but only of 16-bit
112 : // and 32-bit values (not 64-bit); older versions either raise a fatal signal,
113 : // do an unaligned read and rotate the words around a bit, or do the reads very
114 : // slowly (trip through kernel mode). There's no simple #define that says just
115 : // “ARMv7 or higher”, so we have to filter away all ARMv5 and ARMv6
116 : // sub-architectures.
117 : //
118 : // This is a mess, but there's not much we can do about it.
119 : //
120 : // To further complicate matters, only LDR instructions (single reads) are
121 : // allowed to be unaligned, not LDRD (two reads) or LDM (many reads). Unless we
122 : // explicitly tell the compiler that these accesses can be unaligned, it can and
123 : // will combine accesses. On armcc, the way to signal this is done by accessing
124 : // through the type (uint32 __packed *), but GCC has no such attribute
125 : // (it ignores __attribute__((packed)) on individual variables). However,
126 : // we can tell it that a _struct_ is unaligned, which has the same effect,
127 : // so we do that.
128 :
129 : #elif defined(__arm__) && \
130 : !defined(__ARM_ARCH_4__) && \
131 : !defined(__ARM_ARCH_4T__) && \
132 : !defined(__ARM_ARCH_5__) && \
133 : !defined(__ARM_ARCH_5T__) && \
134 : !defined(__ARM_ARCH_5TE__) && \
135 : !defined(__ARM_ARCH_5TEJ__) && \
136 : !defined(__ARM_ARCH_6__) && \
137 : !defined(__ARM_ARCH_6J__) && \
138 : !defined(__ARM_ARCH_6K__) && \
139 : !defined(__ARM_ARCH_6Z__) && \
140 : !defined(__ARM_ARCH_6ZK__) && \
141 : !defined(__ARM_ARCH_6T2__)
142 :
143 : #if __GNUC__
144 : #define ATTRIBUTE_PACKED __attribute__((__packed__))
145 : #else
146 : #define ATTRIBUTE_PACKED
147 : #endif
148 :
149 : namespace base {
150 : namespace internal {
151 :
152 : struct Unaligned16Struct {
153 : uint16 value;
154 : uint8 dummy; // To make the size non-power-of-two.
155 : } ATTRIBUTE_PACKED;
156 :
157 : struct Unaligned32Struct {
158 : uint32 value;
159 : uint8 dummy; // To make the size non-power-of-two.
160 : } ATTRIBUTE_PACKED;
161 :
162 : } // namespace internal
163 : } // namespace base
164 :
165 : #define UNALIGNED_LOAD16(_p) \
166 : ((reinterpret_cast<const ::snappy::base::internal::Unaligned16Struct *>(_p))->value)
167 : #define UNALIGNED_LOAD32(_p) \
168 : ((reinterpret_cast<const ::snappy::base::internal::Unaligned32Struct *>(_p))->value)
169 :
170 : #define UNALIGNED_STORE16(_p, _val) \
171 : ((reinterpret_cast< ::snappy::base::internal::Unaligned16Struct *>(_p))->value = \
172 : (_val))
173 : #define UNALIGNED_STORE32(_p, _val) \
174 : ((reinterpret_cast< ::snappy::base::internal::Unaligned32Struct *>(_p))->value = \
175 : (_val))
176 :
177 : // TODO(user): NEON supports unaligned 64-bit loads and stores.
178 : // See if that would be more efficient on platforms supporting it,
179 : // at least for copies.
180 :
181 : inline uint64 UNALIGNED_LOAD64(const void *p) {
182 : uint64 t;
183 : memcpy(&t, p, sizeof t);
184 : return t;
185 : }
186 :
187 : inline void UNALIGNED_STORE64(void *p, uint64 v) {
188 : memcpy(p, &v, sizeof v);
189 : }
190 :
191 : #else
192 :
193 : // These functions are provided for architectures that don't support
194 : // unaligned loads and stores.
195 :
196 : inline uint16 UNALIGNED_LOAD16(const void *p) {
197 : uint16 t;
198 : memcpy(&t, p, sizeof t);
199 : return t;
200 : }
201 :
202 : inline uint32 UNALIGNED_LOAD32(const void *p) {
203 : uint32 t;
204 : memcpy(&t, p, sizeof t);
205 : return t;
206 : }
207 :
208 : inline uint64 UNALIGNED_LOAD64(const void *p) {
209 : uint64 t;
210 : memcpy(&t, p, sizeof t);
211 : return t;
212 : }
213 :
214 : inline void UNALIGNED_STORE16(void *p, uint16 v) {
215 : memcpy(p, &v, sizeof v);
216 : }
217 :
218 : inline void UNALIGNED_STORE32(void *p, uint32 v) {
219 : memcpy(p, &v, sizeof v);
220 : }
221 :
222 : inline void UNALIGNED_STORE64(void *p, uint64 v) {
223 : memcpy(p, &v, sizeof v);
224 : }
225 :
226 : #endif
227 :
228 : // This can be more efficient than UNALIGNED_LOAD64 + UNALIGNED_STORE64
229 : // on some platforms, in particular ARM.
230 0 : inline void UnalignedCopy64(const void *src, void *dst) {
231 : if (sizeof(void *) == 8) {
232 0 : UNALIGNED_STORE64(dst, UNALIGNED_LOAD64(src));
233 : } else {
234 : const char *src_char = reinterpret_cast<const char *>(src);
235 : char *dst_char = reinterpret_cast<char *>(dst);
236 :
237 : UNALIGNED_STORE32(dst_char, UNALIGNED_LOAD32(src_char));
238 : UNALIGNED_STORE32(dst_char + 4, UNALIGNED_LOAD32(src_char + 4));
239 : }
240 0 : }
241 :
242 : // The following guarantees declaration of the byte swap functions.
243 : #ifdef WORDS_BIGENDIAN
244 :
245 : #ifdef HAVE_SYS_BYTEORDER_H
246 : #include <sys/byteorder.h>
247 : #endif
248 :
249 : #ifdef HAVE_SYS_ENDIAN_H
250 : #include <sys/endian.h>
251 : #endif
252 :
253 : #ifdef _MSC_VER
254 : #include <stdlib.h>
255 : #define bswap_16(x) _byteswap_ushort(x)
256 : #define bswap_32(x) _byteswap_ulong(x)
257 : #define bswap_64(x) _byteswap_uint64(x)
258 :
259 : #elif defined(__APPLE__)
260 : // Mac OS X / Darwin features
261 : #include <libkern/OSByteOrder.h>
262 : #define bswap_16(x) OSSwapInt16(x)
263 : #define bswap_32(x) OSSwapInt32(x)
264 : #define bswap_64(x) OSSwapInt64(x)
265 :
266 : #elif defined(HAVE_BYTESWAP_H)
267 : #include <byteswap.h>
268 :
269 : #elif defined(bswap32)
270 : // FreeBSD defines bswap{16,32,64} in <sys/endian.h> (already #included).
271 : #define bswap_16(x) bswap16(x)
272 : #define bswap_32(x) bswap32(x)
273 : #define bswap_64(x) bswap64(x)
274 :
275 : #elif defined(BSWAP_64)
276 : // Solaris 10 defines BSWAP_{16,32,64} in <sys/byteorder.h> (already #included).
277 : #define bswap_16(x) BSWAP_16(x)
278 : #define bswap_32(x) BSWAP_32(x)
279 : #define bswap_64(x) BSWAP_64(x)
280 :
281 : #else
282 :
283 : inline uint16 bswap_16(uint16 x) {
284 : return (x << 8) | (x >> 8);
285 : }
286 :
287 : inline uint32 bswap_32(uint32 x) {
288 : x = ((x & 0xff00ff00UL) >> 8) | ((x & 0x00ff00ffUL) << 8);
289 : return (x >> 16) | (x << 16);
290 : }
291 :
292 : inline uint64 bswap_64(uint64 x) {
293 : x = ((x & 0xff00ff00ff00ff00ULL) >> 8) | ((x & 0x00ff00ff00ff00ffULL) << 8);
294 : x = ((x & 0xffff0000ffff0000ULL) >> 16) | ((x & 0x0000ffff0000ffffULL) << 16);
295 : return (x >> 32) | (x << 32);
296 : }
297 :
298 : #endif
299 :
300 : #endif // WORDS_BIGENDIAN
301 :
302 : // Convert to little-endian storage, opposite of network format.
303 : // Convert x from host to little endian: x = LittleEndian.FromHost(x);
304 : // convert x from little endian to host: x = LittleEndian.ToHost(x);
305 : //
306 : // Store values into unaligned memory converting to little endian order:
307 : // LittleEndian.Store16(p, x);
308 : //
309 : // Load unaligned values stored in little endian converting to host order:
310 : // x = LittleEndian.Load16(p);
311 : class LittleEndian {
312 : public:
313 : // Conversion functions.
314 : #ifdef WORDS_BIGENDIAN
315 :
316 : static uint16 FromHost16(uint16 x) { return bswap_16(x); }
317 : static uint16 ToHost16(uint16 x) { return bswap_16(x); }
318 :
319 : static uint32 FromHost32(uint32 x) { return bswap_32(x); }
320 : static uint32 ToHost32(uint32 x) { return bswap_32(x); }
321 :
322 : static bool IsLittleEndian() { return false; }
323 :
324 : #else // !defined(WORDS_BIGENDIAN)
325 :
326 0 : static uint16 FromHost16(uint16 x) { return x; }
327 : static uint16 ToHost16(uint16 x) { return x; }
328 :
329 : static uint32 FromHost32(uint32 x) { return x; }
330 0 : static uint32 ToHost32(uint32 x) { return x; }
331 :
332 0 : static bool IsLittleEndian() { return true; }
333 :
334 : #endif // !defined(WORDS_BIGENDIAN)
335 :
336 : // Functions to do unaligned loads and stores in little-endian order.
337 : static uint16 Load16(const void *p) {
338 : return ToHost16(UNALIGNED_LOAD16(p));
339 : }
340 :
341 0 : static void Store16(void *p, uint16 v) {
342 0 : UNALIGNED_STORE16(p, FromHost16(v));
343 0 : }
344 :
345 0 : static uint32 Load32(const void *p) {
346 0 : return ToHost32(UNALIGNED_LOAD32(p));
347 : }
348 :
349 : static void Store32(void *p, uint32 v) {
350 : UNALIGNED_STORE32(p, FromHost32(v));
351 : }
352 : };
353 :
354 : // Some bit-manipulation functions.
355 : class Bits {
356 : public:
357 : // Return floor(log2(n)) for positive integer n. Returns -1 iff n == 0.
358 : static int Log2Floor(uint32 n);
359 :
360 : // Return the first set least / most significant bit, 0-indexed. Returns an
361 : // undefined value if n == 0. FindLSBSetNonZero() is similar to ffs() except
362 : // that it's 0-indexed.
363 : static int FindLSBSetNonZero(uint32 n);
364 : static int FindLSBSetNonZero64(uint64 n);
365 :
366 : private:
367 : DISALLOW_COPY_AND_ASSIGN(Bits);
368 : };
369 :
370 : #ifdef HAVE_BUILTIN_CTZ
371 :
372 : inline int Bits::Log2Floor(uint32 n) {
373 : return n == 0 ? -1 : 31 ^ __builtin_clz(n);
374 : }
375 :
376 : inline int Bits::FindLSBSetNonZero(uint32 n) {
377 : return __builtin_ctz(n);
378 : }
379 :
380 : inline int Bits::FindLSBSetNonZero64(uint64 n) {
381 : return __builtin_ctzll(n);
382 : }
383 :
384 : #else // Portable versions.
385 :
386 0 : inline int Bits::Log2Floor(uint32 n) {
387 0 : if (n == 0)
388 0 : return -1;
389 0 : int log = 0;
390 0 : uint32 value = n;
391 0 : for (int i = 4; i >= 0; --i) {
392 0 : int shift = (1 << i);
393 0 : uint32 x = value >> shift;
394 0 : if (x != 0) {
395 0 : value = x;
396 0 : log += shift;
397 : }
398 : }
399 0 : assert(value == 1);
400 0 : return log;
401 : }
402 :
403 0 : inline int Bits::FindLSBSetNonZero(uint32 n) {
404 0 : int rc = 31;
405 0 : for (int i = 4, shift = 1 << 4; i >= 0; --i) {
406 0 : const uint32 x = n << shift;
407 0 : if (x != 0) {
408 0 : n = x;
409 0 : rc -= shift;
410 : }
411 0 : shift >>= 1;
412 : }
413 0 : return rc;
414 : }
415 :
416 : // FindLSBSetNonZero64() is defined in terms of FindLSBSetNonZero().
417 0 : inline int Bits::FindLSBSetNonZero64(uint64 n) {
418 0 : const uint32 bottombits = static_cast<uint32>(n);
419 0 : if (bottombits == 0) {
420 : // Bottom bits are zero, so scan in top bits
421 0 : return 32 + FindLSBSetNonZero(static_cast<uint32>(n >> 32));
422 : } else {
423 0 : return FindLSBSetNonZero(bottombits);
424 : }
425 : }
426 :
427 : #endif // End portable versions.
428 :
429 : // Variable-length integer encoding.
430 : class Varint {
431 : public:
432 : // Maximum lengths of varint encoding of uint32.
433 : static const int kMax32 = 5;
434 :
435 : // Attempts to parse a varint32 from a prefix of the bytes in [ptr,limit-1].
436 : // Never reads a character at or beyond limit. If a valid/terminated varint32
437 : // was found in the range, stores it in *OUTPUT and returns a pointer just
438 : // past the last byte of the varint32. Else returns NULL. On success,
439 : // "result <= limit".
440 : static const char* Parse32WithLimit(const char* ptr, const char* limit,
441 : uint32* OUTPUT);
442 :
443 : // REQUIRES "ptr" points to a buffer of length sufficient to hold "v".
444 : // EFFECTS Encodes "v" into "ptr" and returns a pointer to the
445 : // byte just past the last encoded byte.
446 : static char* Encode32(char* ptr, uint32 v);
447 :
448 : // EFFECTS Appends the varint representation of "value" to "*s".
449 : static void Append32(string* s, uint32 value);
450 : };
451 :
452 0 : inline const char* Varint::Parse32WithLimit(const char* p,
453 : const char* l,
454 : uint32* OUTPUT) {
455 0 : const unsigned char* ptr = reinterpret_cast<const unsigned char*>(p);
456 0 : const unsigned char* limit = reinterpret_cast<const unsigned char*>(l);
457 : uint32 b, result;
458 0 : if (ptr >= limit) return NULL;
459 0 : b = *(ptr++); result = b & 127; if (b < 128) goto done;
460 0 : if (ptr >= limit) return NULL;
461 0 : b = *(ptr++); result |= (b & 127) << 7; if (b < 128) goto done;
462 0 : if (ptr >= limit) return NULL;
463 0 : b = *(ptr++); result |= (b & 127) << 14; if (b < 128) goto done;
464 0 : if (ptr >= limit) return NULL;
465 0 : b = *(ptr++); result |= (b & 127) << 21; if (b < 128) goto done;
466 0 : if (ptr >= limit) return NULL;
467 0 : b = *(ptr++); result |= (b & 127) << 28; if (b < 16) goto done;
468 0 : return NULL; // Value is too long to be a varint32
469 : done:
470 0 : *OUTPUT = result;
471 0 : return reinterpret_cast<const char*>(ptr);
472 : }
473 :
474 0 : inline char* Varint::Encode32(char* sptr, uint32 v) {
475 : // Operate on characters as unsigneds
476 0 : unsigned char* ptr = reinterpret_cast<unsigned char*>(sptr);
477 : static const int B = 128;
478 0 : if (v < (1<<7)) {
479 0 : *(ptr++) = v;
480 0 : } else if (v < (1<<14)) {
481 0 : *(ptr++) = v | B;
482 0 : *(ptr++) = v>>7;
483 0 : } else if (v < (1<<21)) {
484 0 : *(ptr++) = v | B;
485 0 : *(ptr++) = (v>>7) | B;
486 0 : *(ptr++) = v>>14;
487 0 : } else if (v < (1<<28)) {
488 0 : *(ptr++) = v | B;
489 0 : *(ptr++) = (v>>7) | B;
490 0 : *(ptr++) = (v>>14) | B;
491 0 : *(ptr++) = v>>21;
492 : } else {
493 0 : *(ptr++) = v | B;
494 0 : *(ptr++) = (v>>7) | B;
495 0 : *(ptr++) = (v>>14) | B;
496 0 : *(ptr++) = (v>>21) | B;
497 0 : *(ptr++) = v>>28;
498 : }
499 0 : return reinterpret_cast<char*>(ptr);
500 : }
501 :
502 : // If you know the internal layout of the std::string in use, you can
503 : // replace this function with one that resizes the string without
504 : // filling the new space with zeros (if applicable) --
505 : // it will be non-portable but faster.
506 0 : inline void STLStringResizeUninitialized(string* s, size_t new_size) {
507 0 : s->resize(new_size);
508 0 : }
509 :
510 : // Return a mutable char* pointing to a string's internal buffer,
511 : // which may not be null-terminated. Writing through this pointer will
512 : // modify the string.
513 : //
514 : // string_as_array(&str)[i] is valid for 0 <= i < str.size() until the
515 : // next call to a string method that invalidates iterators.
516 : //
517 : // As of 2006-04, there is no standard-blessed way of getting a
518 : // mutable reference to a string's internal buffer. However, issue 530
519 : // (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-defects.html#530)
520 : // proposes this as the method. It will officially be part of the standard
521 : // for C++0x. This should already work on all current implementations.
522 0 : inline char* string_as_array(string* str) {
523 0 : return str->empty() ? NULL : &*str->begin();
524 : }
525 :
526 : } // namespace snappy
527 :
528 : #endif // THIRD_PARTY_SNAPPY_OPENSOURCE_SNAPPY_STUBS_INTERNAL_H_
|
