File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\compress\CompressLZF.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 *
6 * This code is based on the LZF algorithm from Marc Lehmann. It is a
7 * re-implementation of the C code:
8 * http://cvs.schmorp.de/liblzf/lzf_c.c?view=markup
9 * http://cvs.schmorp.de/liblzf/lzf_d.c?view=markup
10 *
11 * According to a mail from Marc Lehmann, it's OK to use his algorithm:
12 * Date: 2010-07-15 15:57
13 * Subject: Re: Question about LZF licensing
14 * ...
15 * The algorithm is not copyrighted (and cannot be copyrighted afaik) - as long
16 * as you wrote everything yourself, without copying my code, that's just fine
17 * (looking is of course fine too).
18 * ...
19 *
20 * Still I would like to keep his copyright info:
21 *
22 * Copyright (c) 2000-2005 Marc Alexander Lehmann <schmorp@schmorp.de>
23 * Copyright (c) 2005 Oren J. Maurice <oymaurice@hazorea.org.il>
24 *
25 * Redistribution and use in source and binary forms, with or without
26 * modification, are permitted provided that the following conditions are met:
27 *
28 * 1. Redistributions of source code must retain the above copyright notice,
29 * this list of conditions and the following disclaimer.
30 *
31 * 2. Redistributions in binary form must reproduce the above copyright
32 * notice, this list of conditions and the following disclaimer in the
33 * documentation and/or other materials provided with the distribution.
34 *
35 * 3. The name of the author may not be used to endorse or promote products
36 * derived from this software without specific prior written permission.
37 *
38 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ''AS IS'' AND ANY EXPRESS OR IMPLIED
39 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
40 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
41 * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
42 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
43 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
44 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
45 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
46 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
47 * OF THE POSSIBILITY OF SUCH DAMAGE.
48 */
49
50 package org.h2.compress;
51
52 /**
53 * <p>
54 * This class implements the LZF lossless data compression algorithm. LZF is a
55 * Lempel-Ziv variant with byte-aligned output, and optimized for speed.
56 * </p>
57 * <p>
58 * Safety/Use Notes:
59 * </p>
60 * <ul>
61 * <li>Each instance should be used by a single thread only.</li>
62 * <li>The data buffers should be smaller than 1 GB.</li>
63 * <li>For performance reasons, safety checks on expansion are omitted.</li>
64 * <li>Invalid compressed data can cause an ArrayIndexOutOfBoundsException.</li>
65 * </ul>
66 * <p>
67 * The LZF compressed format knows literal runs and back-references:
68 * </p>
69 * <ul>
70 * <li>Literal run: directly copy bytes from input to output.</li>
71 * <li>Back-reference: copy previous data to output stream, with specified
72 * offset from location and length. The length is at least 3 bytes.</li>
73 * </ul>
74 *<p>
75 * The first byte of the compressed stream is the control byte. For literal
76 * runs, the highest three bits of the control byte are not set, the the lower
77 * bits are the literal run length, and the next bytes are data to copy directly
78 * into the output. For back-references, the highest three bits of the control
79 * byte are the back-reference length. If all three bits are set, then the
80 * back-reference length is stored in the next byte. The lower bits of the
81 * control byte combined with the next byte form the offset for the
82 * back-reference.
83 * </p>
84 */
85 public final class CompressLZF implements Compressor {
86
87 /**
88 * The number of entries in the hash table. The size is a trade-off between
89 * hash collisions (reduced compression) and speed (amount that fits in CPU
90 * cache).
91 */
92 private static final int HASH_SIZE = 1 << 14;
93
94 /**
95 * The maximum number of literals in a chunk (32).
96 */
97 private static final int MAX_LITERAL = 1 << 5;
98
99 /**
100 * The maximum offset allowed for a back-reference (8192).
101 */
102 private static final int MAX_OFF = 1 << 13;
103
104 /**
105 * The maximum back-reference length (264).
106 */
107 private static final int MAX_REF = (1 << 8) + (1 << 3);
108
109 /**
110 * Hash table for matching byte sequences (reused for performance).
111 */
112 private int[] cachedHashTable;
113
114 public void setOptions(String options) {
115 // nothing to do
116 }
117
118 /**
119 * Return byte with lower 2 bytes being byte at index, then index+1.
120 */
121 private static int first(byte[] in, int inPos) {
122 return (in[inPos] << 8) | (in[inPos + 1] & 255);
123 }
124
125 /**
126 * Shift v 1 byte left, add value at index inPos+2.
127 */
128 private static int next(int v, byte[] in, int inPos) {
129 return (v << 8) | (in[inPos + 2] & 255);
130 }
131
132 /**
133 * Compute the address in the hash table.
134 */
135 private static int hash(int h) {
136 return ((h * 2777) >> 9) & (HASH_SIZE - 1);
137 }
138
139 public int compress(byte[] in, int inLen, byte[] out, int outPos) {
140 int inPos = 0;
141 if (cachedHashTable == null) {
142 cachedHashTable = new int[HASH_SIZE];
143 }
144 int[] hashTab = cachedHashTable;
145 int literals = 0;
146 outPos++;
147 int future = first(in, 0);
148 while (inPos < inLen - 4) {
149 byte p2 = in[inPos + 2];
150 // next
151 future = (future << 8) + (p2 & 255);
152 int off = hash(future);
153 int ref = hashTab[off];
154 hashTab[off] = inPos;
155 // if (ref < inPos
156 // && ref > 0
157 // && (off = inPos - ref - 1) < MAX_OFF
158 // && in[ref + 2] == p2
159 // && (((in[ref] & 255) << 8) | (in[ref + 1] & 255)) ==
160 // ((future >> 8) & 0xffff)) {
161 if (ref < inPos
162 && ref > 0
163 && (off = inPos - ref - 1) < MAX_OFF
164 && in[ref + 2] == p2
165 && in[ref + 1] == (byte) (future >> 8)
166 && in[ref] == (byte) (future >> 16)) {
167 // match
168 int maxLen = inLen - inPos - 2;
169 if (maxLen > MAX_REF) {
170 maxLen = MAX_REF;
171 }
172 if (literals == 0) {
173 // multiple back-references,
174 // so there is no literal run control byte
175 outPos--;
176 } else {
177 // set the control byte at the start of the literal run
178 // to store the number of literals
179 out[outPos - literals - 1] = (byte) (literals - 1);
180 literals = 0;
181 }
182 int len = 3;
183 while (len < maxLen && in[ref + len] == in[inPos + len]) {
184 len++;
185 }
186 len -= 2;
187 if (len < 7) {
188 out[outPos++] = (byte) ((off >> 8) + (len << 5));
189 } else {
190 out[outPos++] = (byte) ((off >> 8) + (7 << 5));
191 out[outPos++] = (byte) (len - 7);
192 }
193 out[outPos++] = (byte) off;
194 // move one byte forward to allow for a literal run control byte
195 outPos++;
196 inPos += len;
197 // rebuild the future, and store the last bytes to the hashtable.
198 // Storing hashes of the last bytes in back-reference improves
199 // the compression ratio and only reduces speed slightly.
200 future = first(in, inPos);
201 future = next(future, in, inPos);
202 hashTab[hash(future)] = inPos++;
203 future = next(future, in, inPos);
204 hashTab[hash(future)] = inPos++;
205 } else {
206 // copy one byte from input to output as part of literal
207 out[outPos++] = in[inPos++];
208 literals++;
209 // at the end of this literal chunk, write the length
210 // to the control byte and start a new chunk
211 if (literals == MAX_LITERAL) {
212 out[outPos - literals - 1] = (byte) (literals - 1);
213 literals = 0;
214 // move ahead one byte to allow for the
215 // literal run control byte
216 outPos++;
217 }
218 }
219 }
220 // write the remaining few bytes as literals
221 while (inPos < inLen) {
222 out[outPos++] = in[inPos++];
223 literals++;
224 if (literals == MAX_LITERAL) {
225 out[outPos - literals - 1] = (byte) (literals - 1);
226 literals = 0;
227 outPos++;
228 }
229 }
230 // writes the final literal run length to the control byte
231 out[outPos - literals - 1] = (byte) (literals - 1);
232 if (literals == 0) {
233 outPos--;
234 }
235 return outPos;
236 }
237
238 public void expand(byte[] in, int inPos, int inLen, byte[] out, int outPos, int outLen) {
239 // if ((inPos | outPos | outLen) < 0) {
240 if (inPos < 0 || outPos < 0 || outLen < 0) {
241 throw new IllegalArgumentException();
242 }
243 do {
244 int ctrl = in[inPos++] & 255;
245 if (ctrl < MAX_LITERAL) {
246 // literal run of length = ctrl + 1,
247 ctrl++;
248 // copy to output and move forward this many bytes
249 System.arraycopy(in, inPos, out, outPos, ctrl);
250 outPos += ctrl;
251 inPos += ctrl;
252 } else {
253 // back reference
254 // the highest 3 bits are the match length
255 int len = ctrl >> 5;
256 // if the length is maxed, add the next byte to the length
257 if (len == 7) {
258 len += in[inPos++] & 255;
259 }
260 // minimum back-reference is 3 bytes,
261 // so 2 was subtracted before storing size
262 len += 2;
263
264 // ctrl is now the offset for a back-reference...
265 // the logical AND operation removes the length bits
266 ctrl = -((ctrl & 0x1f) << 8) - 1;
267
268 // the next byte augments/increases the offset
269 ctrl -= in[inPos++] & 255;
270
271 // copy the back-reference bytes from the given
272 // location in output to current position
273 ctrl += outPos;
274 if (outPos + len >= out.length) {
275 // reduce array bounds checking
276 throw new ArrayIndexOutOfBoundsException();
277 }
278 for (int i = 0; i < len; i++) {
279 out[outPos++] = out[ctrl++];
280 }
281 }
282 } while (outPos < outLen);
283 }
284
285 public int getAlgorithm() {
286 return Compressor.LZF;
287 }
288
289 }