001: /*
002: This source file is part of Smyle, a database library.
003: For up-to-date information, see http://www.drjava.de/smyle
004: Copyright (C) 2001 Stefan Reich (doc@drjava.de)
005:
006: This library is free software; you can redistribute it and/or
007: modify it under the terms of the GNU Lesser General Public
008: License as published by the Free Software Foundation; either
009: version 2.1 of the License, or (at your option) any later version.
010:
011: This library is distributed in the hope that it will be useful,
012: but WITHOUT ANY WARRANTY; without even the implied warranty of
013: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: Lesser General Public License for more details.
015:
016: You should have received a copy of the GNU Lesser General Public
017: License along with this library; if not, write to the Free Software
018: Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
019:
020: For full license text, see doc/license/lgpl.txt in this distribution
021: */
022:
023: package drjava.smyle.core;
024:
025: import org.artsProject.mcop.*;
026: import drjava.smyle.*;
027:
028: public class Compression {
029: static final byte NOCOMPRESSION = 0, ZEROS = 1, DOUBLEZEROS = 2,
030: XOR5 = 3, HIGHNIBBLE026 = 4, HIGHNIBBLE067 = 5,
031: HIGHNIBBLE267 = 6;
032:
033: public static int estimateXOR(byte[] chunk, int m) {
034: int bits = 0, last = 0;
035: for (int i = 1; i < chunk.length; i++) {
036: int d = chunk[i] ^ last;
037: last = chunk[i];
038: bits += (d == (d & ((1 << m) - 1))) ? 1 + m : 1 + 8;
039: }
040: return (bits + 7) / 8;
041: }
042:
043: static void compressXOR(Buffer src, BitBuffer dest, int m) {
044: int mask = (1 << m) - 1;
045: byte last = 0;
046: while (src.remaining() != 0) {
047: byte s = src.readByte();
048: byte d = (byte) (last ^ s);
049: last = s;
050: if (d == (d & mask)) {
051: dest.writeBits(((s & mask) << 1) | 1, m + 1);
052: } else {
053: dest.writeBits(0, 1);
054: dest.writeOffstreamByte(s);
055: }
056: }
057: dest.close();
058: }
059:
060: static void decompressXOR(BitBuffer src, Buffer dest, int m) {
061: int mask = (1 << m) - 1;
062: int last = 0;
063: while (true) {
064: // read tag
065: int tag = src.readBits(1);
066: if (tag < 0)
067: return;
068: //System.out.println("tag="+tag+", bit="+(bit-1));
069:
070: if (tag != 0) {
071: dest.writeByte((byte) (last = (last & ~mask)
072: | src.readBits(m)));
073: } else {
074: last = src.readOffstreamByte();
075: if (last < 0)
076: return;
077: dest.writeByte((byte) last);
078: }
079: }
080: }
081:
082: /** stores one bit per byte: 0 = zero; 1 = not zero */
083: public static int estimateZeros(byte[] chunk) {
084: int bits = 0;
085: for (int i = 0; i < chunk.length; i++) {
086: bits += chunk[i] != 0 ? 1 + 8 : 1;
087: }
088: return (bits + 7) / 8;
089: }
090:
091: static void compressZeros(Buffer src, BitBuffer dest) {
092: while (src.remaining() != 0) {
093: byte s = src.readByte();
094: if (s == 0)
095: dest.writeBits(1, 1);
096: else {
097: dest.writeBits(0, 1);
098: dest.writeOffstreamByte(s);
099: }
100: }
101: dest.close();
102: }
103:
104: static void decompressZeros(BitBuffer src, Buffer dest) {
105: while (true) {
106: int tag = src.readBits(1);
107: if (tag < 0)
108: return;
109: if (tag != 0)
110: dest.writeByte((byte) 0);
111: else {
112: int s = src.readOffstreamByte();
113: if (s < 0)
114: return;
115: dest.writeByte((byte) s);
116: }
117: }
118: }
119:
120: /** stores every 0000 in one bit */
121: public static int estimateDoubleZeros(byte[] chunk) {
122: int bits = 0, i;
123: for (i = 0; i + 1 < chunk.length; i += 2) {
124: bits += chunk[i] != 0 || chunk[i + 1] != 0 ? 1 + 16 : 1;
125: }
126: bits += (chunk.length - i) * 8;
127: return (bits + 7) / 8;
128: }
129:
130: static void compressDoubleZeros(Buffer src, BitBuffer dest) {
131: while (src.remaining() >= 2) {
132: byte s = src.readByte(), s2 = src.readByte();
133: if (s == 0 && s2 == 0)
134: dest.writeBits(1, 1);
135: else {
136: dest.writeBits(0, 1);
137: dest.writeOffstreamByte(s);
138: dest.writeOffstreamByte(s2);
139: }
140: }
141: if (src.remaining() != 0) {
142: dest.writeBits(0, 1);
143: dest.writeOffstreamByte(src.readByte());
144: }
145: dest.close();
146: }
147:
148: static void decompressDoubleZeros(BitBuffer src, Buffer dest) {
149: while (true) {
150: int tag = src.readBits(1);
151: if (tag < 0)
152: return;
153: if (tag != 0) {
154: dest.writeByte((byte) 0);
155: dest.writeByte((byte) 0);
156: } else {
157: int s = src.readOffstreamByte();
158: if (s < 0)
159: return;
160: dest.writeByte((byte) s);
161: s = src.readOffstreamByte();
162: if (s < 0)
163: return;
164: dest.writeByte((byte) s);
165: }
166: }
167: }
168:
169: /** compresses the most common higher-nibble of characters */
170: public static int estimateHighNibble(byte[] chunk, int a, int b,
171: int c) {
172: int bits = 0;
173: for (int i = 0; i < chunk.length; i++) {
174: int nib = (chunk[i] >> 4) & 15;
175: //bits += (nib == 0 || nib == 2 || nib == 6 || nib == 7 ? 1+2 : 1+4)+4;
176: bits += (nib == a || nib == b || nib == c ? 2 : 2 + 4) + 4;
177: }
178: return (bits + 7) / 8;
179: }
180:
181: static void compressHighNibble(Buffer src, BitBuffer dest, int a,
182: int b, int c) {
183: while (src.remaining() != 0) {
184: int s = src.readByte(), nib = (s >> 4) & 15;
185: if (nib == a)
186: dest.writeBits(((s & 15) << 2) | 1, 6);
187: else if (nib == b)
188: dest.writeBits(((s & 15) << 2) | 2, 6);
189: else if (nib == c)
190: dest.writeBits(((s & 15) << 2) | 3, 6);
191: else {
192: dest.writeBits(0, 2);
193: dest.writeOffstreamByte((byte) s);
194: }
195: }
196: dest.close();
197: }
198:
199: static void decompressHighNibble(BitBuffer src, Buffer dest, int a,
200: int b, int c) {
201: while (true) {
202: int tag = src.readBits(2);
203: switch (tag) {
204: case 1:
205: dest.writeByte((byte) ((a << 4) | src.readBits(4)));
206: break;
207: case 2:
208: dest.writeByte((byte) ((b << 4) | src.readBits(4)));
209: break;
210: case 3:
211: dest.writeByte((byte) ((c << 4) | src.readBits(4)));
212: break;
213: default:
214: int s = src.readOffstreamByte();
215: if (s < 0)
216: return;
217: dest.writeByte((byte) s);
218: }
219: }
220: }
221:
222: public static void compress(Buffer src, Buffer dest) {
223: byte[] data = src.toByteArray();
224: int[] est = new int[7];
225: est[NOCOMPRESSION] = data.length;
226: est[ZEROS] = estimateZeros(data);
227: est[DOUBLEZEROS] = estimateDoubleZeros(data);
228: est[XOR5] = estimateXOR(data, 5);
229: est[HIGHNIBBLE026] = estimateHighNibble(data, 0, 2, 6);
230: est[HIGHNIBBLE067] = estimateHighNibble(data, 0, 6, 7);
231: est[HIGHNIBBLE267] = estimateHighNibble(data, 2, 6, 7);
232: int method = 0;
233: for (int i = 1; i < est.length; i++)
234: if (est[i] < est[method])
235: method = i;
236:
237: dest.writeByte((byte) method);
238: switch (method) {
239: case NOCOMPRESSION:
240: dest.writeBytes(data);
241: break;
242: case ZEROS:
243: compressZeros(src, new BitBuffer(dest));
244: break;
245: case DOUBLEZEROS:
246: compressDoubleZeros(src, new BitBuffer(dest));
247: break;
248: //case XOR1: compressXOR (src, new BitBuffer(dest), 1); break;
249: case XOR5:
250: compressXOR(src, new BitBuffer(dest), 5);
251: break;
252: case HIGHNIBBLE026:
253: compressHighNibble(src, new BitBuffer(dest), 0, 2, 6);
254: break;
255: case HIGHNIBBLE067:
256: compressHighNibble(src, new BitBuffer(dest), 0, 6, 7);
257: break;
258: case HIGHNIBBLE267:
259: compressHighNibble(src, new BitBuffer(dest), 2, 6, 7);
260: break;
261: }
262: }
263:
264: public static void decompress(Buffer src, Buffer dest) {
265: byte method = src.readByte();
266: switch (method) {
267: case NOCOMPRESSION:
268: dest.writeBuffer(src);
269: break;
270: case ZEROS:
271: decompressZeros(new BitBuffer(src), dest);
272: break;
273: case DOUBLEZEROS:
274: decompressDoubleZeros(new BitBuffer(src), dest);
275: break;
276: //case XOR1: decompressXOR(new BitBuffer(src), dest, 1); break;
277: case XOR5:
278: decompressXOR(new BitBuffer(src), dest, 5);
279: break;
280: case HIGHNIBBLE026:
281: decompressHighNibble(new BitBuffer(src), dest, 0, 2, 6);
282: break;
283: case HIGHNIBBLE067:
284: decompressHighNibble(new BitBuffer(src), dest, 0, 6, 7);
285: break;
286: case HIGHNIBBLE267:
287: decompressHighNibble(new BitBuffer(src), dest, 2, 6, 7);
288: break;
289: default:
290: throw new InternalSmyleError("Unknown compression method "
291: + method);
292: }
293: }
294: }
|