1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/other-licenses/snappy/src/snappy-internal.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,150 @@
1.4 +// Copyright 2008 Google Inc. All Rights Reserved.
1.5 +//
1.6 +// Redistribution and use in source and binary forms, with or without
1.7 +// modification, are permitted provided that the following conditions are
1.8 +// met:
1.9 +//
1.10 +// * Redistributions of source code must retain the above copyright
1.11 +// notice, this list of conditions and the following disclaimer.
1.12 +// * Redistributions in binary form must reproduce the above
1.13 +// copyright notice, this list of conditions and the following disclaimer
1.14 +// in the documentation and/or other materials provided with the
1.15 +// distribution.
1.16 +// * Neither the name of Google Inc. nor the names of its
1.17 +// contributors may be used to endorse or promote products derived from
1.18 +// this software without specific prior written permission.
1.19 +//
1.20 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.21 +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.22 +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.23 +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1.24 +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.25 +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.26 +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.27 +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.28 +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.29 +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.30 +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.31 +//
1.32 +// Internals shared between the Snappy implementation and its unittest.
1.33 +
1.34 +#ifndef UTIL_SNAPPY_SNAPPY_INTERNAL_H_
1.35 +#define UTIL_SNAPPY_SNAPPY_INTERNAL_H_
1.36 +
1.37 +#include "snappy-stubs-internal.h"
1.38 +
1.39 +namespace snappy {
1.40 +namespace internal {
1.41 +
1.42 +class WorkingMemory {
1.43 + public:
1.44 + WorkingMemory() : large_table_(NULL) { }
1.45 + ~WorkingMemory() { delete[] large_table_; }
1.46 +
1.47 + // Allocates and clears a hash table using memory in "*this",
1.48 + // stores the number of buckets in "*table_size" and returns a pointer to
1.49 + // the base of the hash table.
1.50 + uint16* GetHashTable(size_t input_size, int* table_size);
1.51 +
1.52 + private:
1.53 + uint16 small_table_[1<<10]; // 2KB
1.54 + uint16* large_table_; // Allocated only when needed
1.55 +
1.56 + DISALLOW_COPY_AND_ASSIGN(WorkingMemory);
1.57 +};
1.58 +
1.59 +// Flat array compression that does not emit the "uncompressed length"
1.60 +// prefix. Compresses "input" string to the "*op" buffer.
1.61 +//
1.62 +// REQUIRES: "input_length <= kBlockSize"
1.63 +// REQUIRES: "op" points to an array of memory that is at least
1.64 +// "MaxCompressedLength(input_length)" in size.
1.65 +// REQUIRES: All elements in "table[0..table_size-1]" are initialized to zero.
1.66 +// REQUIRES: "table_size" is a power of two
1.67 +//
1.68 +// Returns an "end" pointer into "op" buffer.
1.69 +// "end - op" is the compressed size of "input".
1.70 +char* CompressFragment(const char* input,
1.71 + size_t input_length,
1.72 + char* op,
1.73 + uint16* table,
1.74 + const int table_size);
1.75 +
1.76 +// Return the largest n such that
1.77 +//
1.78 +// s1[0,n-1] == s2[0,n-1]
1.79 +// and n <= (s2_limit - s2).
1.80 +//
1.81 +// Does not read *s2_limit or beyond.
1.82 +// Does not read *(s1 + (s2_limit - s2)) or beyond.
1.83 +// Requires that s2_limit >= s2.
1.84 +//
1.85 +// Separate implementation for x86_64, for speed. Uses the fact that
1.86 +// x86_64 is little endian.
1.87 +#if defined(ARCH_K8)
1.88 +static inline int FindMatchLength(const char* s1,
1.89 + const char* s2,
1.90 + const char* s2_limit) {
1.91 + DCHECK_GE(s2_limit, s2);
1.92 + int matched = 0;
1.93 +
1.94 + // Find out how long the match is. We loop over the data 64 bits at a
1.95 + // time until we find a 64-bit block that doesn't match; then we find
1.96 + // the first non-matching bit and use that to calculate the total
1.97 + // length of the match.
1.98 + while (PREDICT_TRUE(s2 <= s2_limit - 8)) {
1.99 + if (PREDICT_FALSE(UNALIGNED_LOAD64(s2) == UNALIGNED_LOAD64(s1 + matched))) {
1.100 + s2 += 8;
1.101 + matched += 8;
1.102 + } else {
1.103 + // On current (mid-2008) Opteron models there is a 3% more
1.104 + // efficient code sequence to find the first non-matching byte.
1.105 + // However, what follows is ~10% better on Intel Core 2 and newer,
1.106 + // and we expect AMD's bsf instruction to improve.
1.107 + uint64 x = UNALIGNED_LOAD64(s2) ^ UNALIGNED_LOAD64(s1 + matched);
1.108 + int matching_bits = Bits::FindLSBSetNonZero64(x);
1.109 + matched += matching_bits >> 3;
1.110 + return matched;
1.111 + }
1.112 + }
1.113 + while (PREDICT_TRUE(s2 < s2_limit)) {
1.114 + if (PREDICT_TRUE(s1[matched] == *s2)) {
1.115 + ++s2;
1.116 + ++matched;
1.117 + } else {
1.118 + return matched;
1.119 + }
1.120 + }
1.121 + return matched;
1.122 +}
1.123 +#else
1.124 +static inline int FindMatchLength(const char* s1,
1.125 + const char* s2,
1.126 + const char* s2_limit) {
1.127 + // Implementation based on the x86-64 version, above.
1.128 + DCHECK_GE(s2_limit, s2);
1.129 + int matched = 0;
1.130 +
1.131 + while (s2 <= s2_limit - 4 &&
1.132 + UNALIGNED_LOAD32(s2) == UNALIGNED_LOAD32(s1 + matched)) {
1.133 + s2 += 4;
1.134 + matched += 4;
1.135 + }
1.136 + if (LittleEndian::IsLittleEndian() && s2 <= s2_limit - 4) {
1.137 + uint32 x = UNALIGNED_LOAD32(s2) ^ UNALIGNED_LOAD32(s1 + matched);
1.138 + int matching_bits = Bits::FindLSBSetNonZero(x);
1.139 + matched += matching_bits >> 3;
1.140 + } else {
1.141 + while ((s2 < s2_limit) && (s1[matched] == *s2)) {
1.142 + ++s2;
1.143 + ++matched;
1.144 + }
1.145 + }
1.146 + return matched;
1.147 +}
1.148 +#endif
1.149 +
1.150 +} // end namespace internal
1.151 +} // end namespace snappy
1.152 +
1.153 +#endif // UTIL_SNAPPY_SNAPPY_INTERNAL_H_
