source: thirdparty/blosc/internal-complibs/snappy-1.1.1/snappy-stubs-internal.h @ 8ebc79b

Revision 8ebc79b, 15.0 KB checked in by Hal Finkel <hfinkel@…>, 8 years ago (diff)

Add the other internal compression libraries from blocs

  • Property mode set to 100644
Line 
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 UTIL_SNAPPY_OPENSOURCE_SNAPPY_STUBS_INTERNAL_H_
32#define UTIL_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.
64using 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
92namespace snappy {
93
94static const uint32 kuint32max = static_cast<uint32>(0xFFFFFFFF);
95static 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#elif defined(__arm__) && \
121      !defined(__ARM_ARCH_4__) && \
122      !defined(__ARM_ARCH_4T__) && \
123      !defined(__ARM_ARCH_5__) && \
124      !defined(__ARM_ARCH_5T__) && \
125      !defined(__ARM_ARCH_5TE__) && \
126      !defined(__ARM_ARCH_5TEJ__) && \
127      !defined(__ARM_ARCH_6__) && \
128      !defined(__ARM_ARCH_6J__) && \
129      !defined(__ARM_ARCH_6K__) && \
130      !defined(__ARM_ARCH_6Z__) && \
131      !defined(__ARM_ARCH_6ZK__) && \
132      !defined(__ARM_ARCH_6T2__)
133
134#define UNALIGNED_LOAD16(_p) (*reinterpret_cast<const uint16 *>(_p))
135#define UNALIGNED_LOAD32(_p) (*reinterpret_cast<const uint32 *>(_p))
136
137#define UNALIGNED_STORE16(_p, _val) (*reinterpret_cast<uint16 *>(_p) = (_val))
138#define UNALIGNED_STORE32(_p, _val) (*reinterpret_cast<uint32 *>(_p) = (_val))
139
140// TODO(user): NEON supports unaligned 64-bit loads and stores.
141// See if that would be more efficient on platforms supporting it,
142// at least for copies.
143
144inline uint64 UNALIGNED_LOAD64(const void *p) {
145  uint64 t;
146  memcpy(&t, p, sizeof t);
147  return t;
148}
149
150inline void UNALIGNED_STORE64(void *p, uint64 v) {
151  memcpy(p, &v, sizeof v);
152}
153
154#else
155
156// These functions are provided for architectures that don't support
157// unaligned loads and stores.
158
159inline uint16 UNALIGNED_LOAD16(const void *p) {
160  uint16 t;
161  memcpy(&t, p, sizeof t);
162  return t;
163}
164
165inline uint32 UNALIGNED_LOAD32(const void *p) {
166  uint32 t;
167  memcpy(&t, p, sizeof t);
168  return t;
169}
170
171inline uint64 UNALIGNED_LOAD64(const void *p) {
172  uint64 t;
173  memcpy(&t, p, sizeof t);
174  return t;
175}
176
177inline void UNALIGNED_STORE16(void *p, uint16 v) {
178  memcpy(p, &v, sizeof v);
179}
180
181inline void UNALIGNED_STORE32(void *p, uint32 v) {
182  memcpy(p, &v, sizeof v);
183}
184
185inline void UNALIGNED_STORE64(void *p, uint64 v) {
186  memcpy(p, &v, sizeof v);
187}
188
189#endif
190
191// This can be more efficient than UNALIGNED_LOAD64 + UNALIGNED_STORE64
192// on some platforms, in particular ARM.
193inline void UnalignedCopy64(const void *src, void *dst) {
194  if (sizeof(void *) == 8) {
195    UNALIGNED_STORE64(dst, UNALIGNED_LOAD64(src));
196  } else {
197    const char *src_char = reinterpret_cast<const char *>(src);
198    char *dst_char = reinterpret_cast<char *>(dst);
199
200    UNALIGNED_STORE32(dst_char, UNALIGNED_LOAD32(src_char));
201    UNALIGNED_STORE32(dst_char + 4, UNALIGNED_LOAD32(src_char + 4));
202  }
203}
204
205// The following guarantees declaration of the byte swap functions.
206#ifdef WORDS_BIGENDIAN
207
208#ifdef HAVE_SYS_BYTEORDER_H
209#include <sys/byteorder.h>
210#endif
211
212#ifdef HAVE_SYS_ENDIAN_H
213#include <sys/endian.h>
214#endif
215
216#ifdef _MSC_VER
217#include <stdlib.h>
218#define bswap_16(x) _byteswap_ushort(x)
219#define bswap_32(x) _byteswap_ulong(x)
220#define bswap_64(x) _byteswap_uint64(x)
221
222#elif defined(__APPLE__)
223// Mac OS X / Darwin features
224#include <libkern/OSByteOrder.h>
225#define bswap_16(x) OSSwapInt16(x)
226#define bswap_32(x) OSSwapInt32(x)
227#define bswap_64(x) OSSwapInt64(x)
228
229#elif defined(HAVE_BYTESWAP_H)
230#include <byteswap.h>
231
232#elif defined(bswap32)
233// FreeBSD defines bswap{16,32,64} in <sys/endian.h> (already #included).
234#define bswap_16(x) bswap16(x)
235#define bswap_32(x) bswap32(x)
236#define bswap_64(x) bswap64(x)
237
238#elif defined(BSWAP_64)
239// Solaris 10 defines BSWAP_{16,32,64} in <sys/byteorder.h> (already #included).
240#define bswap_16(x) BSWAP_16(x)
241#define bswap_32(x) BSWAP_32(x)
242#define bswap_64(x) BSWAP_64(x)
243
244#else
245
246inline uint16 bswap_16(uint16 x) {
247  return (x << 8) | (x >> 8);
248}
249
250inline uint32 bswap_32(uint32 x) {
251  x = ((x & 0xff00ff00UL) >> 8) | ((x & 0x00ff00ffUL) << 8);
252  return (x >> 16) | (x << 16);
253}
254
255inline uint64 bswap_64(uint64 x) {
256  x = ((x & 0xff00ff00ff00ff00ULL) >> 8) | ((x & 0x00ff00ff00ff00ffULL) << 8);
257  x = ((x & 0xffff0000ffff0000ULL) >> 16) | ((x & 0x0000ffff0000ffffULL) << 16);
258  return (x >> 32) | (x << 32);
259}
260
261#endif
262
263#endif  // WORDS_BIGENDIAN
264
265// Convert to little-endian storage, opposite of network format.
266// Convert x from host to little endian: x = LittleEndian.FromHost(x);
267// convert x from little endian to host: x = LittleEndian.ToHost(x);
268//
269//  Store values into unaligned memory converting to little endian order:
270//    LittleEndian.Store16(p, x);
271//
272//  Load unaligned values stored in little endian converting to host order:
273//    x = LittleEndian.Load16(p);
274class LittleEndian {
275 public:
276  // Conversion functions.
277#ifdef WORDS_BIGENDIAN
278
279  static uint16 FromHost16(uint16 x) { return bswap_16(x); }
280  static uint16 ToHost16(uint16 x) { return bswap_16(x); }
281
282  static uint32 FromHost32(uint32 x) { return bswap_32(x); }
283  static uint32 ToHost32(uint32 x) { return bswap_32(x); }
284
285  static bool IsLittleEndian() { return false; }
286
287#else  // !defined(WORDS_BIGENDIAN)
288
289  static uint16 FromHost16(uint16 x) { return x; }
290  static uint16 ToHost16(uint16 x) { return x; }
291
292  static uint32 FromHost32(uint32 x) { return x; }
293  static uint32 ToHost32(uint32 x) { return x; }
294
295  static bool IsLittleEndian() { return true; }
296
297#endif  // !defined(WORDS_BIGENDIAN)
298
299  // Functions to do unaligned loads and stores in little-endian order.
300  static uint16 Load16(const void *p) {
301    return ToHost16(UNALIGNED_LOAD16(p));
302  }
303
304  static void Store16(void *p, uint16 v) {
305    UNALIGNED_STORE16(p, FromHost16(v));
306  }
307
308  static uint32 Load32(const void *p) {
309    return ToHost32(UNALIGNED_LOAD32(p));
310  }
311
312  static void Store32(void *p, uint32 v) {
313    UNALIGNED_STORE32(p, FromHost32(v));
314  }
315};
316
317// Some bit-manipulation functions.
318class Bits {
319 public:
320  // Return floor(log2(n)) for positive integer n.  Returns -1 iff n == 0.
321  static int Log2Floor(uint32 n);
322
323  // Return the first set least / most significant bit, 0-indexed.  Returns an
324  // undefined value if n == 0.  FindLSBSetNonZero() is similar to ffs() except
325  // that it's 0-indexed.
326  static int FindLSBSetNonZero(uint32 n);
327  static int FindLSBSetNonZero64(uint64 n);
328
329 private:
330  DISALLOW_COPY_AND_ASSIGN(Bits);
331};
332
333#ifdef HAVE_BUILTIN_CTZ
334
335inline int Bits::Log2Floor(uint32 n) {
336  return n == 0 ? -1 : 31 ^ __builtin_clz(n);
337}
338
339inline int Bits::FindLSBSetNonZero(uint32 n) {
340  return __builtin_ctz(n);
341}
342
343inline int Bits::FindLSBSetNonZero64(uint64 n) {
344  return __builtin_ctzll(n);
345}
346
347#else  // Portable versions.
348
349inline int Bits::Log2Floor(uint32 n) {
350  if (n == 0)
351    return -1;
352  int log = 0;
353  uint32 value = n;
354  for (int i = 4; i >= 0; --i) {
355    int shift = (1 << i);
356    uint32 x = value >> shift;
357    if (x != 0) {
358      value = x;
359      log += shift;
360    }
361  }
362  assert(value == 1);
363  return log;
364}
365
366inline int Bits::FindLSBSetNonZero(uint32 n) {
367  int rc = 31;
368  for (int i = 4, shift = 1 << 4; i >= 0; --i) {
369    const uint32 x = n << shift;
370    if (x != 0) {
371      n = x;
372      rc -= shift;
373    }
374    shift >>= 1;
375  }
376  return rc;
377}
378
379// FindLSBSetNonZero64() is defined in terms of FindLSBSetNonZero().
380inline int Bits::FindLSBSetNonZero64(uint64 n) {
381  const uint32 bottombits = static_cast<uint32>(n);
382  if (bottombits == 0) {
383    // Bottom bits are zero, so scan in top bits
384    return 32 + FindLSBSetNonZero(static_cast<uint32>(n >> 32));
385  } else {
386    return FindLSBSetNonZero(bottombits);
387  }
388}
389
390#endif  // End portable versions.
391
392// Variable-length integer encoding.
393class Varint {
394 public:
395  // Maximum lengths of varint encoding of uint32.
396  static const int kMax32 = 5;
397
398  // Attempts to parse a varint32 from a prefix of the bytes in [ptr,limit-1].
399  // Never reads a character at or beyond limit.  If a valid/terminated varint32
400  // was found in the range, stores it in *OUTPUT and returns a pointer just
401  // past the last byte of the varint32. Else returns NULL.  On success,
402  // "result <= limit".
403  static const char* Parse32WithLimit(const char* ptr, const char* limit,
404                                      uint32* OUTPUT);
405
406  // REQUIRES   "ptr" points to a buffer of length sufficient to hold "v".
407  // EFFECTS    Encodes "v" into "ptr" and returns a pointer to the
408  //            byte just past the last encoded byte.
409  static char* Encode32(char* ptr, uint32 v);
410
411  // EFFECTS    Appends the varint representation of "value" to "*s".
412  static void Append32(string* s, uint32 value);
413};
414
415inline const char* Varint::Parse32WithLimit(const char* p,
416                                            const char* l,
417                                            uint32* OUTPUT) {
418  const unsigned char* ptr = reinterpret_cast<const unsigned char*>(p);
419  const unsigned char* limit = reinterpret_cast<const unsigned char*>(l);
420  uint32 b, result;
421  if (ptr >= limit) return NULL;
422  b = *(ptr++); result = b & 127;          if (b < 128) goto done;
423  if (ptr >= limit) return NULL;
424  b = *(ptr++); result |= (b & 127) <<  7; if (b < 128) goto done;
425  if (ptr >= limit) return NULL;
426  b = *(ptr++); result |= (b & 127) << 14; if (b < 128) goto done;
427  if (ptr >= limit) return NULL;
428  b = *(ptr++); result |= (b & 127) << 21; if (b < 128) goto done;
429  if (ptr >= limit) return NULL;
430  b = *(ptr++); result |= (b & 127) << 28; if (b < 16) goto done;
431  return NULL;       // Value is too long to be a varint32
432 done:
433  *OUTPUT = result;
434  return reinterpret_cast<const char*>(ptr);
435}
436
437inline char* Varint::Encode32(char* sptr, uint32 v) {
438  // Operate on characters as unsigneds
439  unsigned char* ptr = reinterpret_cast<unsigned char*>(sptr);
440  static const int B = 128;
441  if (v < (1<<7)) {
442    *(ptr++) = v;
443  } else if (v < (1<<14)) {
444    *(ptr++) = v | B;
445    *(ptr++) = v>>7;
446  } else if (v < (1<<21)) {
447    *(ptr++) = v | B;
448    *(ptr++) = (v>>7) | B;
449    *(ptr++) = v>>14;
450  } else if (v < (1<<28)) {
451    *(ptr++) = v | B;
452    *(ptr++) = (v>>7) | B;
453    *(ptr++) = (v>>14) | B;
454    *(ptr++) = v>>21;
455  } else {
456    *(ptr++) = v | B;
457    *(ptr++) = (v>>7) | B;
458    *(ptr++) = (v>>14) | B;
459    *(ptr++) = (v>>21) | B;
460    *(ptr++) = v>>28;
461  }
462  return reinterpret_cast<char*>(ptr);
463}
464
465// If you know the internal layout of the std::string in use, you can
466// replace this function with one that resizes the string without
467// filling the new space with zeros (if applicable) --
468// it will be non-portable but faster.
469inline void STLStringResizeUninitialized(string* s, size_t new_size) {
470  s->resize(new_size);
471}
472
473// Return a mutable char* pointing to a string's internal buffer,
474// which may not be null-terminated. Writing through this pointer will
475// modify the string.
476//
477// string_as_array(&str)[i] is valid for 0 <= i < str.size() until the
478// next call to a string method that invalidates iterators.
479//
480// As of 2006-04, there is no standard-blessed way of getting a
481// mutable reference to a string's internal buffer. However, issue 530
482// (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-defects.html#530)
483// proposes this as the method. It will officially be part of the standard
484// for C++0x. This should already work on all current implementations.
485inline char* string_as_array(string* str) {
486  return str->empty() ? NULL : &*str->begin();
487}
488
489}  // namespace snappy
490
491#endif  // UTIL_SNAPPY_OPENSOURCE_SNAPPY_STUBS_INTERNAL_H_
Note: See TracBrowser for help on using the repository browser.