001: /*
002: * Copyright 2004-2008 H2 Group. Licensed under the H2 License, Version 1.0
003: * (http://h2database.com/html/license.html).
004: * Copyright (c) 2000-2005 Marc Alexander Lehmann <schmorp@schmorp.de>
005: * Copyright (c) 2005 Oren J. Maurice <oymaurice@hazorea.org.il>
006: *
007: * Redistribution and use in source and binary forms, with or without
008: * modification, are permitted provided that the following conditions are met:
009: *
010: * 1. Redistributions of source code must retain the above copyright notice,
011: * this list of conditions and the following disclaimer.
012: *
013: * 2. Redistributions in binary form must reproduce the above copyright
014: * notice, this list of conditions and the following disclaimer in the
015: * documentation and/or other materials provided with the distribution.
016: *
017: * 3. The name of the author may not be used to endorse or promote products
018: * derived from this software without specific prior written permission.
019: *
020: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ''AS IS'' AND ANY EXPRESS OR IMPLIED
021: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
022: * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
023: * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
024: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
025: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
026: * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
027: * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
028: * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
029: * OF THE POSSIBILITY OF SUCH DAMAGE.
030: *
031: */
032:
033: package org.h2.compress;
034:
035: /**
036: * This class implements the LZF lossless data compression algorithm.
037: * LZF is optimized for speed.
038: */
039: public class CompressLZF implements Compressor {
040:
041: public void setOptions(String options) {
042: }
043:
044: public int getAlgorithm() {
045: return Compressor.LZF;
046: }
047:
048: private static final int HASH_SIZE = (1 << 14);
049: private static final int MAX_LITERAL = (1 << 5);
050: private static final int MAX_OFF = (1 << 13);
051: private static final int MAX_REF = ((1 << 8) + (1 << 3));
052:
053: int first(byte[] in, int inPos) {
054: return (in[inPos] << 8) + (in[inPos + 1] & 255);
055: }
056:
057: int next(int v, byte[] in, int inPos) {
058: return (v << 8) + (in[inPos + 2] & 255);
059: }
060:
061: int hash(int h) {
062: // or 57321
063: return ((h * 184117) >> 9) & (HASH_SIZE - 1);
064: }
065:
066: private int[] hashTab;
067: private static int[] empty = new int[HASH_SIZE];
068:
069: public int compress(byte[] in, int inLen, byte[] out, int outPos) {
070: int inPos = 0;
071: if (hashTab == null) {
072: hashTab = new int[HASH_SIZE];
073: } else {
074: System.arraycopy(empty, 0, hashTab, 0, HASH_SIZE);
075: }
076: int literals = 0;
077: int hash = first(in, inPos);
078: while (true) {
079: if (inPos < inLen - 4) {
080: hash = next(hash, in, inPos);
081: int off = hash(hash);
082: int ref = hashTab[off];
083: hashTab[off] = inPos;
084: off = inPos - ref - 1;
085: if (off < MAX_OFF && ref > 0
086: && in[ref + 2] == in[inPos + 2]
087: && in[ref + 1] == in[inPos + 1]
088: && in[ref] == in[inPos]) {
089: int maxlen = inLen - inPos - 2;
090: maxlen = maxlen > MAX_REF ? MAX_REF : maxlen;
091: int len = 3;
092: while (len < maxlen
093: && in[ref + len] == in[inPos + len]) {
094: len++;
095: }
096: len -= 2;
097: if (literals != 0) {
098: out[outPos++] = (byte) (literals - 1);
099: literals = -literals;
100: do {
101: out[outPos++] = in[inPos + literals++];
102: } while (literals != 0);
103: }
104: if (len < 7) {
105: out[outPos++] = (byte) ((off >> 8) + (len << 5));
106: } else {
107: out[outPos++] = (byte) ((off >> 8) + (7 << 5));
108: out[outPos++] = (byte) (len - 7);
109: }
110: out[outPos++] = (byte) off;
111: inPos += len;
112: hash = first(in, inPos);
113: hash = next(hash, in, inPos);
114: hashTab[hash(hash)] = inPos++;
115: hash = next(hash, in, inPos);
116: hashTab[hash(hash)] = inPos++;
117: continue;
118: }
119: } else if (inPos == inLen) {
120: break;
121: }
122: inPos++;
123: literals++;
124: if (literals == MAX_LITERAL) {
125: out[outPos++] = (byte) (literals - 1);
126: literals = -literals;
127: do {
128: out[outPos++] = in[inPos + literals++];
129: } while (literals != 0);
130: }
131: }
132: if (literals != 0) {
133: out[outPos++] = (byte) (literals - 1);
134: literals = -literals;
135: do {
136: out[outPos++] = in[inPos + literals++];
137: } while (literals != 0);
138: }
139: return outPos;
140: }
141:
142: public void expand(byte[] in, int inPos, int inLen, byte[] out,
143: int outPos, int outLen) {
144: do {
145: int ctrl = in[inPos++] & 255;
146: if (ctrl < (1 << 5)) {
147: // literal run
148: ctrl += inPos;
149: do {
150: out[outPos++] = in[inPos];
151: } while (inPos++ < ctrl);
152: } else {
153: // back reference
154: int len = ctrl >> 5;
155: ctrl = -((ctrl & 0x1f) << 8) - 1;
156: if (len == 7) {
157: len += in[inPos++] & 255;
158: }
159: ctrl -= in[inPos++] & 255;
160: len += outPos + 2;
161: out[outPos] = out[outPos++ + ctrl];
162: out[outPos] = out[outPos++ + ctrl];
163: while (outPos < len - 8) {
164: out[outPos] = out[outPos++ + ctrl];
165: out[outPos] = out[outPos++ + ctrl];
166: out[outPos] = out[outPos++ + ctrl];
167: out[outPos] = out[outPos++ + ctrl];
168: out[outPos] = out[outPos++ + ctrl];
169: out[outPos] = out[outPos++ + ctrl];
170: out[outPos] = out[outPos++ + ctrl];
171: out[outPos] = out[outPos++ + ctrl];
172: }
173: while (outPos < len) {
174: out[outPos] = out[outPos++ + ctrl];
175: }
176: }
177: } while (outPos < outLen);
178: }
179: }
|