001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017: package org.apache.harmony.pack200;
018:
019: import java.io.EOFException;
020: import java.io.IOException;
021: import java.io.InputStream;
022: import java.util.ArrayList;
023: import java.util.List;
024:
025: /**
026: * TODO Comment -- quite a lot can be nicked from Codec, since this was created
027: * from it
028: *
029: */
030: public final class BHSDCodec extends Codec {
031:
032: /**
033: * The maximum number of bytes in each coding word
034: */
035: private int b;
036:
037: /**
038: * Whether delta encoding is used (0=false,1=true)
039: */
040: private int d;
041:
042: /**
043: * The radix of the encoding
044: */
045: private int h;
046:
047: /**
048: * The co-parameter of h; h-256
049: */
050: private int l;
051:
052: /**
053: * Represents signed numbers or not (0=unsigned,1/2=signed)
054: */
055: private int s;
056:
057: private long cardinality;
058:
059: /**
060: * Constructs an unsigned, non-delta Codec with the given B and H values.
061: *
062: * @param b
063: * the maximum number of bytes that a value can be encoded as
064: * [1..5]
065: * @param h
066: * the radix of the encoding [1..256]
067: */
068: public BHSDCodec(int b, int h) {
069: this (b, h, 0);
070: }
071:
072: /**
073: * Constructs a non-delta Codec with the given B, H and S values.
074: *
075: * @param b
076: * the maximum number of bytes that a value can be encoded as
077: * [1..5]
078: * @param h
079: * the radix of the encoding [1..256]
080: * @param s
081: * whether the encoding represents signed numbers (s=0 is
082: * unsigned; s=1 is signed with 1s complement; s=2 is signed with ?)
083: */
084: public BHSDCodec(int b, int h, int s) {
085: this (b, h, s, 0);
086: }
087:
088: /**
089: * Constructs a Codec with the given B, H, S and D values.
090: *
091: * @param b
092: * the maximum number of bytes that a value can be encoded as
093: * [1..5]
094: * @param h
095: * the radix of the encoding [1..256]
096: * @param s
097: * whether the encoding represents signed numbers (s=0 is
098: * unsigned; s=1 is signed with 1s complement; s=2 is signed with ?)
099: * @param d
100: * whether this is a delta encoding (d=0 is non-delta; d=1 is
101: * delta)
102: */
103: public BHSDCodec(int b, int h, int s, int d) {
104: if (b < 1 || b > 5)
105: throw new IllegalArgumentException("1<=b<=5");
106: if (h < 1 || h > 256)
107: throw new IllegalArgumentException("1<=h<=256");
108: if (s < 0 || s > 2)
109: throw new IllegalArgumentException("0<=s<=2");
110: if (d < 0 || d > 1)
111: throw new IllegalArgumentException("0<=d<=1");
112: if (b == 1 && h != 256)
113: throw new IllegalArgumentException("b=1 -> h=256");
114: if (h == 256 && b == 5)
115: throw new IllegalArgumentException("h=256 -> b!=5");
116: this .b = b;
117: this .h = h;
118: this .s = s;
119: this .d = d;
120: this .l = 256 - h;
121: if (h == 1) {
122: cardinality = b * 255 + 1;
123: } else {
124: cardinality = (long) ((long) (l * (1 - Math.pow(h, b)) / (1 - h)) + Math
125: .pow(h, b));
126: }
127: }
128:
129: /**
130: * Returns the cardinality of this codec; that is, the number of distinct
131: * values that it can contain.
132: *
133: * @return the cardinality of this codec
134: */
135: public long cardinality() {
136: return cardinality;
137: }
138:
139: public long decode(InputStream in) throws IOException,
140: Pack200Exception {
141: if (d != 0)
142: throw new Pack200Exception(
143: "Delta encoding used without passing in last value; this is a coding error");
144: return decode(in, 0);
145: }
146:
147: public long decode(InputStream in, long last) throws IOException,
148: Pack200Exception {
149: int n = 0;
150: long z = 0;
151: long x;
152: do {
153: x = in.read();
154: if (x == -1)
155: throw new EOFException(
156: "End of stream reached whilst decoding");
157: z += x * Math.pow(h, n);
158: n++;
159: } while (n < b & isHigh(x));
160:
161: // TODO: Decide whether to use this algorithm instead (neater, possibly quicker but less easy to understand)
162: // if (isSigned()) {
163: // int u = ((1 << s) - 1);
164: // if ((z & u) == u) {
165: // z = z >>> s ^ -1L;
166: // } else {
167: // z = z - (z >>> s);
168: // }
169: // }
170: if (isSigned()) {
171: long u = z;
172: long twoPowS = (long) Math.pow(2, s);
173: double twoPowSMinusOne = twoPowS - 1;
174: if (u % twoPowS < twoPowSMinusOne) {
175: if (cardinality < Math.pow(2, 32)) {
176: z = (long) (u - (Math.floor(u / twoPowS)));
177: } else {
178: z = cast32((long) (u - (Math.floor(u / twoPowS))));
179: }
180: } else {
181: z = (long) (-Math.floor(u / twoPowS) - 1);
182: }
183: }
184: if (isDelta())
185: z += last;
186: return z;
187: }
188:
189: private long cast32(long u) {
190: u = (long) ((long) ((u + Math.pow(2, 31)) % Math.pow(2, 32)) - Math
191: .pow(2, 31));
192: return u;
193: }
194:
195: private boolean isHigh(long x) {
196: return x >= l;
197: }
198:
199: /**
200: * True if this encoding can code the given value
201: *
202: * @param value
203: * the value to check
204: * @return <code>true</code> if the encoding can encode this value
205: */
206: public boolean encodes(long value) {
207: return (value >= smallest() && value <= largest());
208: }
209:
210: public byte[] encode(long value, long last) throws Pack200Exception {
211: if (isDelta()) {
212: value -= last;
213: }
214: if (!encodes(value)) {
215: throw new Pack200Exception("The codec " + toString()
216: + " does not encode the value " + value);
217: }
218: long z = value;
219: if (isSigned()) {
220: if (z < 0) {
221: z = (-z << s) - 1;
222: } else {
223: if (s == 1) {
224: z = z << s;
225: } else {
226: z += (z - z % 3) / 3;
227: }
228: }
229: }
230: List byteList = new ArrayList();
231: for (int n = 0; n < b; n++) {
232: long byteN;
233: if (z < l) {
234: byteN = z;
235: } else {
236: byteN = z % h;
237: while (byteN < l)
238: byteN += h;
239: }
240: byteList.add(new Byte((byte) byteN));
241: if (byteN < l) {
242: break;
243: }
244: z -= byteN;
245: z /= h;
246: }
247: byte[] bytes = new byte[byteList.size()];
248: for (int i = 0; i < bytes.length; i++) {
249: bytes[i] = ((Byte) byteList.get(i)).byteValue();
250: }
251: return bytes;
252: }
253:
254: /**
255: * Returns true if this codec is a delta codec
256: * @return true if this codec is a delta codec
257: */
258: public boolean isDelta() {
259: return d != 0;
260: }
261:
262: /**
263: * Returns true if this codec is a signed codec
264: * @return true if this codec is a signed codec
265: */
266: public boolean isSigned() {
267: return s != 0;
268: }
269:
270: /**
271: * Returns the largest value that this codec can represent.
272: *
273: * @return the largest value that this codec can represent.
274: */
275: public long largest() {
276: long result;
277: // TODO This can probably be optimized into a better mathematical statement
278: if (s == 0) {
279: result = cardinality() - 1;
280: } else if (s == 1) {
281: result = cardinality() / 2 - 1;
282: } else if (s == 2) {
283: result = (3L * cardinality()) / 4 - 1;
284: } else {
285: throw new Error("Unknown s value");
286: }
287: return Math.min((s == 0 ? ((long) Integer.MAX_VALUE) << 1
288: : Integer.MAX_VALUE) - 1, result);
289: }
290:
291: /**
292: * Returns the smallest value that this codec can represent.
293: *
294: * @return the smallest value that this codec can represent.
295: */
296: public long smallest() {
297: long result;
298: if (isSigned()) {
299: result = -cardinality() / (1 << s);
300: } else {
301: result = 0;
302: }
303: return Math.max(Integer.MIN_VALUE, result);
304: }
305:
306: /**
307: * Returns the codec in the form (1,256) or (1,64,1,1). Note that trailing
308: * zero fields are not shown.
309: */
310: public String toString() {
311: StringBuffer buffer = new StringBuffer(11);
312: buffer.append('(');
313: buffer.append(b);
314: buffer.append(',');
315: buffer.append(h);
316: if (s != 0 || d != 0) {
317: buffer.append(',');
318: buffer.append(s);
319: }
320: if (d != 0) {
321: buffer.append(',');
322: buffer.append(d);
323: }
324: buffer.append(')');
325: return buffer.toString();
326: }
327:
328: /**
329: * @return the b
330: */
331: public int getB() {
332: return b;
333: }
334:
335: /**
336: * @return the h
337: */
338: public int getH() {
339: return h;
340: }
341:
342: /**
343: * @return the l
344: */
345: public int getL() {
346: return l;
347: }
348: }
|