1 /* 2 * @(#)Decompressor.java 1.7 06/10/30 3 * 4 * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. 5 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 6 * 7 * This code is free software; you can redistribute it and/or modify it 8 * under the terms of the GNU General Public License version 2 only, as 9 * published by the Free Software Foundation. Sun designates this 10 * particular file as subject to the "Classpath" exception as provided 11 * by Sun in the LICENSE file that accompanied this code. 12 * 13 * This code is distributed in the hope that it will be useful, but WITHOUT 14 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 15 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16 * version 2 for more details (a copy is included in the LICENSE file that 17 * accompanied this code). 18 * 19 * You should have received a copy of the GNU General Public License version 20 * 2 along with this work; if not, write to the Free Software Foundation, 21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 22 * 23 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 24 * CA 95054 USA or visit www.sun.com if you need additional information or 25 * have any questions. 26 */ 27 28 /** 29 * @date 1/13/98 30 * @author Jacek R. Ambroziak 31 * @group Sun Microsystems Laboratories 32 */ 33 34 package com.sun.java.help.search; 35 36 abstract class Decompressor 37 { 38 private static final int BitsInByte = 8; 39 private static final int NBits = 32; 40 41 private int _readByte; 42 private int _toRead = 0; 43 private int _path = 0; 44 getNextByte()45 abstract protected int getNextByte() throws Exception; 46 initReading()47 protected void initReading() { 48 _toRead = 0; 49 } 50 countZeroes()51 private int countZeroes() throws Exception 52 { 53 for (int count = 0;; _readByte = getNextByte(), _toRead = BitsInByte) 54 while (_toRead-- > 0) 55 if ((_readByte & (1 << _toRead)) != 0) 56 return count; 57 else 58 ++count; 59 } 60 61 // reads 1 bit; returns non-0 for bit "1" read()62 private int read() throws Exception 63 { 64 if (_toRead-- > 0) 65 return _readByte & (1 << _toRead); 66 else 67 { // get next word 68 _toRead = BitsInByte - 1; 69 return (_readByte = getNextByte()) & 0x80; 70 } 71 } 72 read(int kBits)73 public int read(int kBits) throws Exception 74 { 75 int shift = BitsInByte - _toRead; 76 if (kBits <= _toRead) 77 return ((_readByte<<shift) & 0xFF) >>> (shift + (_toRead-=kBits)); 78 else 79 { 80 int result = _toRead > 0 81 ? ((_readByte << shift) & 0xFF) >>> shift 82 : 0; 83 for (kBits -= _toRead; kBits >= BitsInByte; kBits -= BitsInByte) 84 result = (result << BitsInByte) | getNextByte(); 85 if (kBits > 0) 86 return (result << kBits) 87 | ((_readByte = getNextByte()) >>> (_toRead = BitsInByte - kBits)); 88 else 89 { 90 _toRead = 0; 91 return result; 92 } 93 } 94 } 95 beginIteration()96 public void beginIteration() { 97 _path = 0; 98 } 99 readNext(int k, CompressorIterator it)100 public boolean readNext(int k, CompressorIterator it) throws Exception 101 { 102 if (read() != 0) 103 { 104 it.value(_path | read(k)); 105 return true; 106 } 107 else 108 for (int count = 1;; _readByte = getNextByte(), _toRead = BitsInByte) 109 while (_toRead-- > 0) 110 if ((_readByte & (1 << _toRead)) != 0) 111 { 112 int saved = _path; 113 _path = ((_path >>> (k + count) << count) | read(count)) << k; 114 if (_path != saved) 115 { 116 it.value(_path | read(k)); 117 return true; 118 } 119 else 120 return false; 121 } 122 else 123 ++count; 124 } 125 decode(int k, IntegerArray array)126 public void decode(int k, IntegerArray array) throws Exception 127 { 128 for (int path = 0;;) 129 if (read() != 0) 130 array.add(path | read(k)); 131 else 132 { 133 int count = countZeroes() + 1; 134 int saved = path; 135 path = ((path >>> (k + count) << count) | read(count)) << k; 136 if (path != saved) // convention for end 137 array.add(path | read(k)); 138 else 139 break; 140 } 141 } 142 ascDecode(int k, IntegerArray array)143 public void ascDecode(int k, IntegerArray array) throws Exception 144 { 145 for (int path = 0, start = 0;;) 146 if (read() != 0) 147 array.add(start += path | read(k)); 148 else 149 { 150 int count = countZeroes() + 1; 151 int saved = path; 152 path = ((path >>> (k + count) << count) | read(count)) << k; 153 if (path != saved) // convention for end 154 array.add(start += path | read(k)); 155 else 156 break; 157 } 158 } 159 ascendingDecode(int k, int start, int[] array)160 public int ascendingDecode(int k, int start, int[] array) throws Exception 161 { 162 int path = 0, index = 0; 163 LOOP: 164 while (true) 165 if (read() != 0) 166 array[index++] = (start += path | read(k)); 167 else 168 for (int cnt = 0;; _readByte = getNextByte(), _toRead = BitsInByte) 169 while (_toRead-- > 0) 170 if ((_readByte & (1 << _toRead)) != 0) 171 { 172 ++cnt; 173 int Path = ((path >>> (k + cnt) << cnt) | read(cnt)) << k; 174 if (Path != path) 175 { 176 array[index++] = (start += (path = Path) | read(k)); 177 continue LOOP; 178 } 179 else 180 return index; 181 } 182 else 183 ++cnt; 184 } 185 } 186