]> git.cworth.org Git - apitrace/blob - thirdparty/snappy/snappy-stubs-internal.h
d3d9state: Upack D3DFMT_R5G6B5 too.
[apitrace] / thirdparty / snappy / snappy-stubs-internal.h
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 <iostream>
39 #include <string>
40
41 #include <assert.h>
42 #include <stdlib.h>
43 #include <string.h>
44
45 #ifdef HAVE_SYS_MMAN_H
46 #include <sys/mman.h>
47 #endif
48
49 #include "snappy-stubs-public.h"
50
51 #if defined(__x86_64__)
52
53 // Enable 64-bit optimized versions of some routines.
54 #define ARCH_K8 1
55
56 #endif
57
58 // Needed by OS X, among others.
59 #ifndef MAP_ANONYMOUS
60 #define MAP_ANONYMOUS MAP_ANON
61 #endif
62
63 // Pull in std::min, std::ostream, and the likes. This is safe because this
64 // header file is never used from any public header files.
65 using namespace std;
66
67 // The size of an array, if known at compile-time.
68 // Will give unexpected results if used on a pointer.
69 // We undefine it first, since some compilers already have a definition.
70 #ifdef ARRAYSIZE
71 #undef ARRAYSIZE
72 #endif
73 #define ARRAYSIZE(a) (sizeof(a) / sizeof(*(a)))
74
75 // Static prediction hints.
76 #ifdef HAVE_BUILTIN_EXPECT
77 #define PREDICT_FALSE(x) (__builtin_expect(x, 0))
78 #define PREDICT_TRUE(x) (__builtin_expect(!!(x), 1))
79 #else
80 #define PREDICT_FALSE(x) x
81 #define PREDICT_TRUE(x) x
82 #endif
83
84 // This is only used for recomputing the tag byte table used during
85 // decompression; for simplicity we just remove it from the open-source
86 // version (anyone who wants to regenerate it can just do the call
87 // themselves within main()).
88 #define DEFINE_bool(flag_name, default_value, description) \
89   bool FLAGS_ ## flag_name = default_value
90 #define DECLARE_bool(flag_name) \
91   extern bool FLAGS_ ## flag_name
92
93 namespace snappy {
94
95 static const uint32 kuint32max = static_cast<uint32>(0xFFFFFFFF);
96 static const int64 kint64max = static_cast<int64>(0x7FFFFFFFFFFFFFFFLL);
97
98 // Logging.
99
100 #define LOG(level) LogMessage()
101 #define VLOG(level) true ? (void)0 : \
102     snappy::LogMessageVoidify() & snappy::LogMessage()
103
104 class LogMessage {
105  public:
106   LogMessage() { }
107   ~LogMessage() {
108     cerr << endl;
109   }
110
111   LogMessage& operator<<(const std::string& msg) {
112     cerr << msg;
113     return *this;
114   }
115   LogMessage& operator<<(int x) {
116     cerr << x;
117     return *this;
118   }
119 };
120
121 // Asserts, both versions activated in debug mode only,
122 // and ones that are always active.
123
124 #define CRASH_UNLESS(condition) \
125     PREDICT_TRUE(condition) ? (void)0 : \
126     snappy::LogMessageVoidify() & snappy::LogMessageCrash()
127
128 class LogMessageCrash : public LogMessage {
129  public:
130   LogMessageCrash() { }
131   ~LogMessageCrash() {
132     cerr << endl;
133     abort();
134   }
135 };
136
137 // This class is used to explicitly ignore values in the conditional
138 // logging macros.  This avoids compiler warnings like "value computed
139 // is not used" and "statement has no effect".
140
141 class LogMessageVoidify {
142  public:
143   LogMessageVoidify() { }
144   // This has to be an operator with a precedence lower than << but
145   // higher than ?:
146   void operator&(const LogMessage&) { }
147 };
148
149 #define CHECK(cond) CRASH_UNLESS(cond)
150 #define CHECK_LE(a, b) CRASH_UNLESS((a) <= (b))
151 #define CHECK_GE(a, b) CRASH_UNLESS((a) >= (b))
152 #define CHECK_EQ(a, b) CRASH_UNLESS((a) == (b))
153 #define CHECK_NE(a, b) CRASH_UNLESS((a) != (b))
154 #define CHECK_LT(a, b) CRASH_UNLESS((a) < (b))
155 #define CHECK_GT(a, b) CRASH_UNLESS((a) > (b))
156
157 #ifdef NDEBUG
158
159 #define DCHECK(cond) CRASH_UNLESS(true)
160 #define DCHECK_LE(a, b) CRASH_UNLESS(true)
161 #define DCHECK_GE(a, b) CRASH_UNLESS(true)
162 #define DCHECK_EQ(a, b) CRASH_UNLESS(true)
163 #define DCHECK_NE(a, b) CRASH_UNLESS(true)
164 #define DCHECK_LT(a, b) CRASH_UNLESS(true)
165 #define DCHECK_GT(a, b) CRASH_UNLESS(true)
166
167 #else
168
169 #define DCHECK(cond) CHECK(cond)
170 #define DCHECK_LE(a, b) CHECK_LE(a, b)
171 #define DCHECK_GE(a, b) CHECK_GE(a, b)
172 #define DCHECK_EQ(a, b) CHECK_EQ(a, b)
173 #define DCHECK_NE(a, b) CHECK_NE(a, b)
174 #define DCHECK_LT(a, b) CHECK_LT(a, b)
175 #define DCHECK_GT(a, b) CHECK_GT(a, b)
176
177 #endif
178
179 // Potentially unaligned loads and stores.
180
181 // x86 and PowerPC can simply do these loads and stores native.
182
183 #if defined(__i386__) || defined(__x86_64__) || defined(__powerpc__)
184
185 #define UNALIGNED_LOAD16(_p) (*reinterpret_cast<const uint16 *>(_p))
186 #define UNALIGNED_LOAD32(_p) (*reinterpret_cast<const uint32 *>(_p))
187 #define UNALIGNED_LOAD64(_p) (*reinterpret_cast<const uint64 *>(_p))
188
189 #define UNALIGNED_STORE16(_p, _val) (*reinterpret_cast<uint16 *>(_p) = (_val))
190 #define UNALIGNED_STORE32(_p, _val) (*reinterpret_cast<uint32 *>(_p) = (_val))
191 #define UNALIGNED_STORE64(_p, _val) (*reinterpret_cast<uint64 *>(_p) = (_val))
192
193 // ARMv7 and newer support native unaligned accesses, but only of 16-bit
194 // and 32-bit values (not 64-bit); older versions either raise a fatal signal,
195 // do an unaligned read and rotate the words around a bit, or do the reads very
196 // slowly (trip through kernel mode). There's no simple #define that says just
197 // “ARMv7 or higher”, so we have to filter away all ARMv5 and ARMv6
198 // sub-architectures.
199 //
200 // This is a mess, but there's not much we can do about it.
201
202 #elif defined(__arm__) && \
203       !defined(__ARM_ARCH_5__) && \
204       !defined(__ARM_ARCH_5T__) && \
205       !defined(__ARM_ARCH_5TE__) && \
206       !defined(__ARM_ARCH_5TEJ__) && \
207       !defined(__ARM_ARCH_6__) && \
208       !defined(__ARM_ARCH_6J__) && \
209       !defined(__ARM_ARCH_6K__) && \
210       !defined(__ARM_ARCH_6Z__) && \
211       !defined(__ARM_ARCH_6ZK__) && \
212       !defined(__ARM_ARCH_6T2__)
213
214 #define UNALIGNED_LOAD16(_p) (*reinterpret_cast<const uint16 *>(_p))
215 #define UNALIGNED_LOAD32(_p) (*reinterpret_cast<const uint32 *>(_p))
216
217 #define UNALIGNED_STORE16(_p, _val) (*reinterpret_cast<uint16 *>(_p) = (_val))
218 #define UNALIGNED_STORE32(_p, _val) (*reinterpret_cast<uint32 *>(_p) = (_val))
219
220 // TODO(user): NEON supports unaligned 64-bit loads and stores.
221 // See if that would be more efficient on platforms supporting it,
222 // at least for copies.
223
224 inline uint64 UNALIGNED_LOAD64(const void *p) {
225   uint64 t;
226   memcpy(&t, p, sizeof t);
227   return t;
228 }
229
230 inline void UNALIGNED_STORE64(void *p, uint64 v) {
231   memcpy(p, &v, sizeof v);
232 }
233
234 #else
235
236 // These functions are provided for architectures that don't support
237 // unaligned loads and stores.
238
239 inline uint16 UNALIGNED_LOAD16(const void *p) {
240   uint16 t;
241   memcpy(&t, p, sizeof t);
242   return t;
243 }
244
245 inline uint32 UNALIGNED_LOAD32(const void *p) {
246   uint32 t;
247   memcpy(&t, p, sizeof t);
248   return t;
249 }
250
251 inline uint64 UNALIGNED_LOAD64(const void *p) {
252   uint64 t;
253   memcpy(&t, p, sizeof t);
254   return t;
255 }
256
257 inline void UNALIGNED_STORE16(void *p, uint16 v) {
258   memcpy(p, &v, sizeof v);
259 }
260
261 inline void UNALIGNED_STORE32(void *p, uint32 v) {
262   memcpy(p, &v, sizeof v);
263 }
264
265 inline void UNALIGNED_STORE64(void *p, uint64 v) {
266   memcpy(p, &v, sizeof v);
267 }
268
269 #endif
270
271 // This can be more efficient than UNALIGNED_LOAD64 + UNALIGNED_STORE64
272 // on some platforms, in particular ARM.
273 inline void UnalignedCopy64(const void *src, void *dst) {
274   if (sizeof(void *) == 8) {
275     UNALIGNED_STORE64(dst, UNALIGNED_LOAD64(src));
276   } else {
277     const char *src_char = reinterpret_cast<const char *>(src);
278     char *dst_char = reinterpret_cast<char *>(dst);
279
280     UNALIGNED_STORE32(dst_char, UNALIGNED_LOAD32(src_char));
281     UNALIGNED_STORE32(dst_char + 4, UNALIGNED_LOAD32(src_char + 4));
282   }
283 }
284
285 // The following guarantees declaration of the byte swap functions.
286 #ifdef WORDS_BIGENDIAN
287
288 #ifdef HAVE_SYS_BYTEORDER_H
289 #include <sys/byteorder.h>
290 #endif
291
292 #ifdef HAVE_SYS_ENDIAN_H
293 #include <sys/endian.h>
294 #endif
295
296 #ifdef _MSC_VER
297 #include <stdlib.h>
298 #define bswap_16(x) _byteswap_ushort(x)
299 #define bswap_32(x) _byteswap_ulong(x)
300 #define bswap_64(x) _byteswap_uint64(x)
301
302 #elif defined(__APPLE__)
303 // Mac OS X / Darwin features
304 #include <libkern/OSByteOrder.h>
305 #define bswap_16(x) OSSwapInt16(x)
306 #define bswap_32(x) OSSwapInt32(x)
307 #define bswap_64(x) OSSwapInt64(x)
308
309 #elif defined(HAVE_BYTESWAP_H)
310 #include <byteswap.h>
311
312 #elif defined(bswap32)
313 // FreeBSD defines bswap{16,32,64} in <sys/endian.h> (already #included).
314 #define bswap_16(x) bswap16(x)
315 #define bswap_32(x) bswap32(x)
316 #define bswap_64(x) bswap64(x)
317
318 #elif defined(BSWAP_64)
319 // Solaris 10 defines BSWAP_{16,32,64} in <sys/byteorder.h> (already #included).
320 #define bswap_16(x) BSWAP_16(x)
321 #define bswap_32(x) BSWAP_32(x)
322 #define bswap_64(x) BSWAP_64(x)
323
324 #else
325
326 inline uint16 bswap_16(uint16 x) {
327   return (x << 8) | (x >> 8);
328 }
329
330 inline uint32 bswap_32(uint32 x) {
331   x = ((x & 0xff00ff00UL) >> 8) | ((x & 0x00ff00ffUL) << 8);
332   return (x >> 16) | (x << 16);
333 }
334
335 inline uint64 bswap_64(uint64 x) {
336   x = ((x & 0xff00ff00ff00ff00ULL) >> 8) | ((x & 0x00ff00ff00ff00ffULL) << 8);
337   x = ((x & 0xffff0000ffff0000ULL) >> 16) | ((x & 0x0000ffff0000ffffULL) << 16);
338   return (x >> 32) | (x << 32);
339 }
340
341 #endif
342
343 #endif  // WORDS_BIGENDIAN
344
345 // Convert to little-endian storage, opposite of network format.
346 // Convert x from host to little endian: x = LittleEndian.FromHost(x);
347 // convert x from little endian to host: x = LittleEndian.ToHost(x);
348 //
349 //  Store values into unaligned memory converting to little endian order:
350 //    LittleEndian.Store16(p, x);
351 //
352 //  Load unaligned values stored in little endian converting to host order:
353 //    x = LittleEndian.Load16(p);
354 class LittleEndian {
355  public:
356   // Conversion functions.
357 #ifdef WORDS_BIGENDIAN
358
359   static uint16 FromHost16(uint16 x) { return bswap_16(x); }
360   static uint16 ToHost16(uint16 x) { return bswap_16(x); }
361
362   static uint32 FromHost32(uint32 x) { return bswap_32(x); }
363   static uint32 ToHost32(uint32 x) { return bswap_32(x); }
364
365   static bool IsLittleEndian() { return false; }
366
367 #else  // !defined(WORDS_BIGENDIAN)
368
369   static uint16 FromHost16(uint16 x) { return x; }
370   static uint16 ToHost16(uint16 x) { return x; }
371
372   static uint32 FromHost32(uint32 x) { return x; }
373   static uint32 ToHost32(uint32 x) { return x; }
374
375   static bool IsLittleEndian() { return true; }
376
377 #endif  // !defined(WORDS_BIGENDIAN)
378
379   // Functions to do unaligned loads and stores in little-endian order.
380   static uint16 Load16(const void *p) {
381     return ToHost16(UNALIGNED_LOAD16(p));
382   }
383
384   static void Store16(void *p, uint16 v) {
385     UNALIGNED_STORE16(p, FromHost16(v));
386   }
387
388   static uint32 Load32(const void *p) {
389     return ToHost32(UNALIGNED_LOAD32(p));
390   }
391
392   static void Store32(void *p, uint32 v) {
393     UNALIGNED_STORE32(p, FromHost32(v));
394   }
395 };
396
397 // Some bit-manipulation functions.
398 class Bits {
399  public:
400   // Return floor(log2(n)) for positive integer n.  Returns -1 iff n == 0.
401   static int Log2Floor(uint32 n);
402
403   // Return the first set least / most significant bit, 0-indexed.  Returns an
404   // undefined value if n == 0.  FindLSBSetNonZero() is similar to ffs() except
405   // that it's 0-indexed.
406   static int FindLSBSetNonZero(uint32 n);
407   static int FindLSBSetNonZero64(uint64 n);
408
409  private:
410   DISALLOW_COPY_AND_ASSIGN(Bits);
411 };
412
413 #ifdef HAVE_BUILTIN_CTZ
414
415 inline int Bits::Log2Floor(uint32 n) {
416   return n == 0 ? -1 : 31 ^ __builtin_clz(n);
417 }
418
419 inline int Bits::FindLSBSetNonZero(uint32 n) {
420   return __builtin_ctz(n);
421 }
422
423 inline int Bits::FindLSBSetNonZero64(uint64 n) {
424   return __builtin_ctzll(n);
425 }
426
427 #else  // Portable versions.
428
429 inline int Bits::Log2Floor(uint32 n) {
430   if (n == 0)
431     return -1;
432   int log = 0;
433   uint32 value = n;
434   for (int i = 4; i >= 0; --i) {
435     int shift = (1 << i);
436     uint32 x = value >> shift;
437     if (x != 0) {
438       value = x;
439       log += shift;
440     }
441   }
442   assert(value == 1);
443   return log;
444 }
445
446 inline int Bits::FindLSBSetNonZero(uint32 n) {
447   int rc = 31;
448   for (int i = 4, shift = 1 << 4; i >= 0; --i) {
449     const uint32 x = n << shift;
450     if (x != 0) {
451       n = x;
452       rc -= shift;
453     }
454     shift >>= 1;
455   }
456   return rc;
457 }
458
459 // FindLSBSetNonZero64() is defined in terms of FindLSBSetNonZero().
460 inline int Bits::FindLSBSetNonZero64(uint64 n) {
461   const uint32 bottombits = static_cast<uint32>(n);
462   if (bottombits == 0) {
463     // Bottom bits are zero, so scan in top bits
464     return 32 + FindLSBSetNonZero(static_cast<uint32>(n >> 32));
465   } else {
466     return FindLSBSetNonZero(bottombits);
467   }
468 }
469
470 #endif  // End portable versions.
471
472 // Variable-length integer encoding.
473 class Varint {
474  public:
475   // Maximum lengths of varint encoding of uint32.
476   static const int kMax32 = 5;
477
478   // Attempts to parse a varint32 from a prefix of the bytes in [ptr,limit-1].
479   // Never reads a character at or beyond limit.  If a valid/terminated varint32
480   // was found in the range, stores it in *OUTPUT and returns a pointer just
481   // past the last byte of the varint32. Else returns NULL.  On success,
482   // "result <= limit".
483   static const char* Parse32WithLimit(const char* ptr, const char* limit,
484                                       uint32* OUTPUT);
485
486   // REQUIRES   "ptr" points to a buffer of length sufficient to hold "v".
487   // EFFECTS    Encodes "v" into "ptr" and returns a pointer to the
488   //            byte just past the last encoded byte.
489   static char* Encode32(char* ptr, uint32 v);
490
491   // EFFECTS    Appends the varint representation of "value" to "*s".
492   static void Append32(string* s, uint32 value);
493 };
494
495 inline const char* Varint::Parse32WithLimit(const char* p,
496                                             const char* l,
497                                             uint32* OUTPUT) {
498   const unsigned char* ptr = reinterpret_cast<const unsigned char*>(p);
499   const unsigned char* limit = reinterpret_cast<const unsigned char*>(l);
500   uint32 b, result;
501   if (ptr >= limit) return NULL;
502   b = *(ptr++); result = b & 127;          if (b < 128) goto done;
503   if (ptr >= limit) return NULL;
504   b = *(ptr++); result |= (b & 127) <<  7; if (b < 128) goto done;
505   if (ptr >= limit) return NULL;
506   b = *(ptr++); result |= (b & 127) << 14; if (b < 128) goto done;
507   if (ptr >= limit) return NULL;
508   b = *(ptr++); result |= (b & 127) << 21; if (b < 128) goto done;
509   if (ptr >= limit) return NULL;
510   b = *(ptr++); result |= (b & 127) << 28; if (b < 16) goto done;
511   return NULL;       // Value is too long to be a varint32
512  done:
513   *OUTPUT = result;
514   return reinterpret_cast<const char*>(ptr);
515 }
516
517 inline char* Varint::Encode32(char* sptr, uint32 v) {
518   // Operate on characters as unsigneds
519   unsigned char* ptr = reinterpret_cast<unsigned char*>(sptr);
520   static const int B = 128;
521   if (v < (1<<7)) {
522     *(ptr++) = v;
523   } else if (v < (1<<14)) {
524     *(ptr++) = v | B;
525     *(ptr++) = v>>7;
526   } else if (v < (1<<21)) {
527     *(ptr++) = v | B;
528     *(ptr++) = (v>>7) | B;
529     *(ptr++) = v>>14;
530   } else if (v < (1<<28)) {
531     *(ptr++) = v | B;
532     *(ptr++) = (v>>7) | B;
533     *(ptr++) = (v>>14) | B;
534     *(ptr++) = v>>21;
535   } else {
536     *(ptr++) = v | B;
537     *(ptr++) = (v>>7) | B;
538     *(ptr++) = (v>>14) | B;
539     *(ptr++) = (v>>21) | B;
540     *(ptr++) = v>>28;
541   }
542   return reinterpret_cast<char*>(ptr);
543 }
544
545 // If you know the internal layout of the std::string in use, you can
546 // replace this function with one that resizes the string without
547 // filling the new space with zeros (if applicable) --
548 // it will be non-portable but faster.
549 inline void STLStringResizeUninitialized(string* s, size_t new_size) {
550   s->resize(new_size);
551 }
552
553 // Return a mutable char* pointing to a string's internal buffer,
554 // which may not be null-terminated. Writing through this pointer will
555 // modify the string.
556 //
557 // string_as_array(&str)[i] is valid for 0 <= i < str.size() until the
558 // next call to a string method that invalidates iterators.
559 //
560 // As of 2006-04, there is no standard-blessed way of getting a
561 // mutable reference to a string's internal buffer. However, issue 530
562 // (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-defects.html#530)
563 // proposes this as the method. It will officially be part of the standard
564 // for C++0x. This should already work on all current implementations.
565 inline char* string_as_array(string* str) {
566   return str->empty() ? NULL : &*str->begin();
567 }
568
569 }  // namespace snappy
570
571 #endif  // UTIL_SNAPPY_OPENSOURCE_SNAPPY_STUBS_INTERNAL_H_