1 // Copyright 2008 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 // Internals shared between the Snappy implementation and its unittest.
30
31 #ifndef THIRD_PARTY_SNAPPY_SNAPPY_INTERNAL_H_
32 #define THIRD_PARTY_SNAPPY_SNAPPY_INTERNAL_H_
33
34 #include "snappy-stubs-internal.h"
35
36 namespace snappy {
37 namespace internal {
38
39 class WorkingMemory {
40 public:
WorkingMemory()41 WorkingMemory() : large_table_(NULL) { }
~WorkingMemory()42 ~WorkingMemory() { delete[] large_table_; }
43
44 // Allocates and clears a hash table using memory in "*this",
45 // stores the number of buckets in "*table_size" and returns a pointer to
46 // the base of the hash table.
47 uint16* GetHashTable(size_t input_size, int* table_size);
48
49 private:
50 uint16 small_table_[1<<10]; // 2KB
51 uint16* large_table_; // Allocated only when needed
52
53 // No copying
54 WorkingMemory(const WorkingMemory&);
55 void operator=(const WorkingMemory&);
56 };
57
58 // Flat array compression that does not emit the "uncompressed length"
59 // prefix. Compresses "input" string to the "*op" buffer.
60 //
61 // REQUIRES: "input_length <= kBlockSize"
62 // REQUIRES: "op" points to an array of memory that is at least
63 // "MaxCompressedLength(input_length)" in size.
64 // REQUIRES: All elements in "table[0..table_size-1]" are initialized to zero.
65 // REQUIRES: "table_size" is a power of two
66 //
67 // Returns an "end" pointer into "op" buffer.
68 // "end - op" is the compressed size of "input".
69 char* CompressFragment(const char* input,
70 size_t input_length,
71 char* op,
72 uint16* table,
73 const int table_size);
74
75 // Find the largest n such that
76 //
77 // s1[0,n-1] == s2[0,n-1]
78 // and n <= (s2_limit - s2).
79 //
80 // Return make_pair(n, n < 8).
81 // Does not read *s2_limit or beyond.
82 // Does not read *(s1 + (s2_limit - s2)) or beyond.
83 // Requires that s2_limit >= s2.
84 //
85 // Separate implementation for 64-bit, little-endian cpus.
86 #if !defined(SNAPPY_IS_BIG_ENDIAN) && \
87 (defined(ARCH_K8) || defined(ARCH_PPC) || defined(ARCH_ARM))
FindMatchLength(const char * s1,const char * s2,const char * s2_limit)88 static inline std::pair<size_t, bool> FindMatchLength(const char* s1,
89 const char* s2,
90 const char* s2_limit) {
91 assert(s2_limit >= s2);
92 size_t matched = 0;
93
94 // This block isn't necessary for correctness; we could just start looping
95 // immediately. As an optimization though, it is useful. It creates some not
96 // uncommon code paths that determine, without extra effort, whether the match
97 // length is less than 8. In short, we are hoping to avoid a conditional
98 // branch, and perhaps get better code layout from the C++ compiler.
99 if (SNAPPY_PREDICT_TRUE(s2 <= s2_limit - 8)) {
100 uint64 a1 = UNALIGNED_LOAD64(s1);
101 uint64 a2 = UNALIGNED_LOAD64(s2);
102 if (a1 != a2) {
103 return std::pair<size_t, bool>(Bits::FindLSBSetNonZero64(a1 ^ a2) >> 3,
104 true);
105 } else {
106 matched = 8;
107 s2 += 8;
108 }
109 }
110
111 // Find out how long the match is. We loop over the data 64 bits at a
112 // time until we find a 64-bit block that doesn't match; then we find
113 // the first non-matching bit and use that to calculate the total
114 // length of the match.
115 while (SNAPPY_PREDICT_TRUE(s2 <= s2_limit - 8)) {
116 if (UNALIGNED_LOAD64(s2) == UNALIGNED_LOAD64(s1 + matched)) {
117 s2 += 8;
118 matched += 8;
119 } else {
120 uint64 x = UNALIGNED_LOAD64(s2) ^ UNALIGNED_LOAD64(s1 + matched);
121 int matching_bits = Bits::FindLSBSetNonZero64(x);
122 matched += matching_bits >> 3;
123 assert(matched >= 8);
124 return std::pair<size_t, bool>(matched, false);
125 }
126 }
127 while (SNAPPY_PREDICT_TRUE(s2 < s2_limit)) {
128 if (s1[matched] == *s2) {
129 ++s2;
130 ++matched;
131 } else {
132 return std::pair<size_t, bool>(matched, matched < 8);
133 }
134 }
135 return std::pair<size_t, bool>(matched, matched < 8);
136 }
137 #else
FindMatchLength(const char * s1,const char * s2,const char * s2_limit)138 static inline std::pair<size_t, bool> FindMatchLength(const char* s1,
139 const char* s2,
140 const char* s2_limit) {
141 // Implementation based on the x86-64 version, above.
142 assert(s2_limit >= s2);
143 int matched = 0;
144
145 while (s2 <= s2_limit - 4 &&
146 UNALIGNED_LOAD32(s2) == UNALIGNED_LOAD32(s1 + matched)) {
147 s2 += 4;
148 matched += 4;
149 }
150 if (LittleEndian::IsLittleEndian() && s2 <= s2_limit - 4) {
151 uint32 x = UNALIGNED_LOAD32(s2) ^ UNALIGNED_LOAD32(s1 + matched);
152 int matching_bits = Bits::FindLSBSetNonZero(x);
153 matched += matching_bits >> 3;
154 } else {
155 while ((s2 < s2_limit) && (s1[matched] == *s2)) {
156 ++s2;
157 ++matched;
158 }
159 }
160 return std::pair<size_t, bool>(matched, matched < 8);
161 }
162 #endif
163
164 // Lookup tables for decompression code. Give --snappy_dump_decompression_table
165 // to the unit test to recompute char_table.
166
167 enum {
168 LITERAL = 0,
169 COPY_1_BYTE_OFFSET = 1, // 3 bit length + 3 bits of offset in opcode
170 COPY_2_BYTE_OFFSET = 2,
171 COPY_4_BYTE_OFFSET = 3
172 };
173 static const int kMaximumTagLength = 5; // COPY_4_BYTE_OFFSET plus the actual offset.
174
175 // Data stored per entry in lookup table:
176 // Range Bits-used Description
177 // ------------------------------------
178 // 1..64 0..7 Literal/copy length encoded in opcode byte
179 // 0..7 8..10 Copy offset encoded in opcode byte / 256
180 // 0..4 11..13 Extra bytes after opcode
181 //
182 // We use eight bits for the length even though 7 would have sufficed
183 // because of efficiency reasons:
184 // (1) Extracting a byte is faster than a bit-field
185 // (2) It properly aligns copy offset so we do not need a <<8
186 static const uint16 char_table[256] = {
187 0x0001, 0x0804, 0x1001, 0x2001, 0x0002, 0x0805, 0x1002, 0x2002,
188 0x0003, 0x0806, 0x1003, 0x2003, 0x0004, 0x0807, 0x1004, 0x2004,
189 0x0005, 0x0808, 0x1005, 0x2005, 0x0006, 0x0809, 0x1006, 0x2006,
190 0x0007, 0x080a, 0x1007, 0x2007, 0x0008, 0x080b, 0x1008, 0x2008,
191 0x0009, 0x0904, 0x1009, 0x2009, 0x000a, 0x0905, 0x100a, 0x200a,
192 0x000b, 0x0906, 0x100b, 0x200b, 0x000c, 0x0907, 0x100c, 0x200c,
193 0x000d, 0x0908, 0x100d, 0x200d, 0x000e, 0x0909, 0x100e, 0x200e,
194 0x000f, 0x090a, 0x100f, 0x200f, 0x0010, 0x090b, 0x1010, 0x2010,
195 0x0011, 0x0a04, 0x1011, 0x2011, 0x0012, 0x0a05, 0x1012, 0x2012,
196 0x0013, 0x0a06, 0x1013, 0x2013, 0x0014, 0x0a07, 0x1014, 0x2014,
197 0x0015, 0x0a08, 0x1015, 0x2015, 0x0016, 0x0a09, 0x1016, 0x2016,
198 0x0017, 0x0a0a, 0x1017, 0x2017, 0x0018, 0x0a0b, 0x1018, 0x2018,
199 0x0019, 0x0b04, 0x1019, 0x2019, 0x001a, 0x0b05, 0x101a, 0x201a,
200 0x001b, 0x0b06, 0x101b, 0x201b, 0x001c, 0x0b07, 0x101c, 0x201c,
201 0x001d, 0x0b08, 0x101d, 0x201d, 0x001e, 0x0b09, 0x101e, 0x201e,
202 0x001f, 0x0b0a, 0x101f, 0x201f, 0x0020, 0x0b0b, 0x1020, 0x2020,
203 0x0021, 0x0c04, 0x1021, 0x2021, 0x0022, 0x0c05, 0x1022, 0x2022,
204 0x0023, 0x0c06, 0x1023, 0x2023, 0x0024, 0x0c07, 0x1024, 0x2024,
205 0x0025, 0x0c08, 0x1025, 0x2025, 0x0026, 0x0c09, 0x1026, 0x2026,
206 0x0027, 0x0c0a, 0x1027, 0x2027, 0x0028, 0x0c0b, 0x1028, 0x2028,
207 0x0029, 0x0d04, 0x1029, 0x2029, 0x002a, 0x0d05, 0x102a, 0x202a,
208 0x002b, 0x0d06, 0x102b, 0x202b, 0x002c, 0x0d07, 0x102c, 0x202c,
209 0x002d, 0x0d08, 0x102d, 0x202d, 0x002e, 0x0d09, 0x102e, 0x202e,
210 0x002f, 0x0d0a, 0x102f, 0x202f, 0x0030, 0x0d0b, 0x1030, 0x2030,
211 0x0031, 0x0e04, 0x1031, 0x2031, 0x0032, 0x0e05, 0x1032, 0x2032,
212 0x0033, 0x0e06, 0x1033, 0x2033, 0x0034, 0x0e07, 0x1034, 0x2034,
213 0x0035, 0x0e08, 0x1035, 0x2035, 0x0036, 0x0e09, 0x1036, 0x2036,
214 0x0037, 0x0e0a, 0x1037, 0x2037, 0x0038, 0x0e0b, 0x1038, 0x2038,
215 0x0039, 0x0f04, 0x1039, 0x2039, 0x003a, 0x0f05, 0x103a, 0x203a,
216 0x003b, 0x0f06, 0x103b, 0x203b, 0x003c, 0x0f07, 0x103c, 0x203c,
217 0x0801, 0x0f08, 0x103d, 0x203d, 0x1001, 0x0f09, 0x103e, 0x203e,
218 0x1801, 0x0f0a, 0x103f, 0x203f, 0x2001, 0x0f0b, 0x1040, 0x2040
219 };
220
221 } // end namespace internal
222 } // end namespace snappy
223
224 #endif // THIRD_PARTY_SNAPPY_SNAPPY_INTERNAL_H_
225