001: /*
002: * $RCSfile: CompressionStreamElement.java,v $
003: *
004: * Copyright (c) 2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: *
010: * - Redistribution of source code must retain the above copyright
011: * notice, this list of conditions and the following disclaimer.
012: *
013: * - Redistribution in binary form must reproduce the above copyright
014: * notice, this list of conditions and the following disclaimer in
015: * the documentation and/or other materials provided with the
016: * distribution.
017: *
018: * Neither the name of Sun Microsystems, Inc. or the names of
019: * contributors may be used to endorse or promote products derived
020: * from this software without specific prior written permission.
021: *
022: * This software is provided "AS IS," without a warranty of any
023: * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND
024: * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY,
025: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY
026: * EXCLUDED. SUN MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL
027: * NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF
028: * USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
029: * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR
030: * ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL,
031: * CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND
032: * REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR
033: * INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
034: * POSSIBILITY OF SUCH DAMAGES.
035: *
036: * You acknowledge that this software is not designed, licensed or
037: * intended for use in the design, construction, operation or
038: * maintenance of any nuclear facility.
039: *
040: * $Revision: 1.3 $
041: * $Date: 2007/02/09 17:20:22 $
042: * $State: Exp $
043: */
044:
045: package com.sun.j3d.utils.geometry.compression;
046:
047: /**
048: * Instances of this class are used as elements in a CompressionStream.
049: * @see CompressionStream
050: */
051: abstract class CompressionStreamElement {
052: /**
053: * Bit length of quantized geometric components.
054: */
055: int length;
056:
057: /**
058: * Number of trailing zeros in quantized geometric components.
059: */
060: int shift;
061:
062: /**
063: * If false, geometric component values are represented as differences
064: * from those of the preceding element in the stream.
065: */
066: boolean absolute;
067:
068: /**
069: * Array with elements that can be used as masks to apply a quantization
070: * to the number of bits indicated by the referencing index [0..16].
071: */
072: static final int quantizationMask[] = { 0xFFFF0000, 0xFFFF8000,
073: 0xFFFFC000, 0xFFFFE000, 0xFFFFF000, 0xFFFFF800, 0xFFFFFC00,
074: 0xFFFFFE00, 0xFFFFFF00, 0xFFFFFF80, 0xFFFFFFC0, 0xFFFFFFE0,
075: 0xFFFFFFF0, 0xFFFFFFF8, 0xFFFFFFFC, 0xFFFFFFFE, 0xFFFFFFFF };
076:
077: /**
078: * Array with elements that can be used as masks to retain the number of
079: * trailing bits of data indicated by the referencing index [0..64]. Used
080: * to clear the leading sign bits of fixed-point 2's complement numbers
081: * and in building the compressed output stream.
082: */
083: static final long lengthMask[] = { 0x0000000000000000L,
084: 0x0000000000000001L, 0x0000000000000003L,
085: 0x0000000000000007L, 0x000000000000000FL,
086: 0x000000000000001FL, 0x000000000000003FL,
087: 0x000000000000007FL, 0x00000000000000FFL,
088: 0x00000000000001FFL, 0x00000000000003FFL,
089: 0x00000000000007FFL, 0x0000000000000FFFL,
090: 0x0000000000001FFFL, 0x0000000000003FFFL,
091: 0x0000000000007FFFL, 0x000000000000FFFFL,
092: 0x000000000001FFFFL, 0x000000000003FFFFL,
093: 0x000000000007FFFFL, 0x00000000000FFFFFL,
094: 0x00000000001FFFFFL, 0x00000000003FFFFFL,
095: 0x00000000007FFFFFL, 0x0000000000FFFFFFL,
096: 0x0000000001FFFFFFL, 0x0000000003FFFFFFL,
097: 0x0000000007FFFFFFL, 0x000000000FFFFFFFL,
098: 0x000000001FFFFFFFL, 0x000000003FFFFFFFL,
099: 0x000000007FFFFFFFL, 0x00000000FFFFFFFFL,
100: 0x00000001FFFFFFFFL, 0x00000003FFFFFFFFL,
101: 0x00000007FFFFFFFFL, 0x0000000FFFFFFFFFL,
102: 0x0000001FFFFFFFFFL, 0x0000003FFFFFFFFFL,
103: 0x0000007FFFFFFFFFL, 0x000000FFFFFFFFFFL,
104: 0x000001FFFFFFFFFFL, 0x000003FFFFFFFFFFL,
105: 0x000007FFFFFFFFFFL, 0x00000FFFFFFFFFFFL,
106: 0x00001FFFFFFFFFFFL, 0x00003FFFFFFFFFFFL,
107: 0x00007FFFFFFFFFFFL, 0x0000FFFFFFFFFFFFL,
108: 0x0001FFFFFFFFFFFFL, 0x0003FFFFFFFFFFFFL,
109: 0x0007FFFFFFFFFFFFL, 0x000FFFFFFFFFFFFFL,
110: 0x001FFFFFFFFFFFFFL, 0x003FFFFFFFFFFFFFL,
111: 0x007FFFFFFFFFFFFFL, 0x00FFFFFFFFFFFFFFL,
112: 0x01FFFFFFFFFFFFFFL, 0x03FFFFFFFFFFFFFFL,
113: 0x07FFFFFFFFFFFFFFL, 0x0FFFFFFFFFFFFFFFL,
114: 0x1FFFFFFFFFFFFFFFL, 0x3FFFFFFFFFFFFFFFL,
115: 0x7FFFFFFFFFFFFFFFL, 0xFFFFFFFFFFFFFFFFL };
116:
117: /**
118: * Computes the quantized representation of this stream element.
119: *
120: * @param stream CompressionStream associated with this element
121: * @param table HuffmanTable for collecting data about the quantized
122: * representation of this element
123: */
124: abstract void quantize(CompressionStream stream, HuffmanTable table);
125:
126: /**
127: * Outputs the compressed bits representing this stream element.
128: * Some instances of CompressionStreamElement don't require an
129: * implementation and will inherit the stub provided here.
130: *
131: * @param table HuffmanTable mapping quantized representations to
132: * compressed encodings
133: * @param output CommandStream for collecting compressed output
134: */
135: void outputCommand(HuffmanTable table, CommandStream output) {
136: }
137:
138: /**
139: * Finds the minimum bits needed to represent the given 16-bit signed 2's
140: * complement integer. For positive integers, this include the first
141: * 1 starting from the left, plus a 0 sign bit; for negative integers,
142: * this includes the first 0 starting from the left, plus a 1 sign bit.
143: * 0 is a special case returning 0; however, 0-length components are valid
144: * ONLY for normals.
145: *
146: * The decompressor uses the data length to determine how many bits of
147: * sign extension to add to the data coming in from the compressed stream
148: * in order to create a 16-bit signed 2's complement integer. E.g., a data
149: * length of 12 indicates that 16-12=4 bits of sign are to be extended.<p>
150: *
151: * @param number a signed 2's complement integer representable in 16 bits
152: * or less
153: * @return minimum number of bits to represent the number
154: */
155: private static final int getLength(int number) {
156: if (number == 0)
157: return 0;
158:
159: else if ((number & 0x8000) > 0) {
160: // negative numbers
161: if ((number & 0x4000) == 0)
162: return 16;
163: if ((number & 0x2000) == 0)
164: return 15;
165: if ((number & 0x1000) == 0)
166: return 14;
167: if ((number & 0x0800) == 0)
168: return 13;
169: if ((number & 0x0400) == 0)
170: return 12;
171: if ((number & 0x0200) == 0)
172: return 11;
173: if ((number & 0x0100) == 0)
174: return 10;
175: if ((number & 0x0080) == 0)
176: return 9;
177: if ((number & 0x0040) == 0)
178: return 8;
179: if ((number & 0x0020) == 0)
180: return 7;
181: if ((number & 0x0010) == 0)
182: return 6;
183: if ((number & 0x0008) == 0)
184: return 5;
185: if ((number & 0x0004) == 0)
186: return 4;
187: if ((number & 0x0002) == 0)
188: return 3;
189: if ((number & 0x0001) == 0)
190: return 2;
191:
192: return 1;
193:
194: } else {
195: // positive numbers
196: if ((number & 0x4000) > 0)
197: return 16;
198: if ((number & 0x2000) > 0)
199: return 15;
200: if ((number & 0x1000) > 0)
201: return 14;
202: if ((number & 0x0800) > 0)
203: return 13;
204: if ((number & 0x0400) > 0)
205: return 12;
206: if ((number & 0x0200) > 0)
207: return 11;
208: if ((number & 0x0100) > 0)
209: return 10;
210: if ((number & 0x0080) > 0)
211: return 9;
212: if ((number & 0x0040) > 0)
213: return 8;
214: if ((number & 0x0020) > 0)
215: return 7;
216: if ((number & 0x0010) > 0)
217: return 6;
218: if ((number & 0x0008) > 0)
219: return 5;
220: if ((number & 0x0004) > 0)
221: return 4;
222: if ((number & 0x0002) > 0)
223: return 3;
224:
225: return 2;
226: }
227: }
228:
229: /**
230: * Finds the rightmost 1 bit in the given 16-bit integer. This value is
231: * used by the decompressor to indicate the number of trailing zeros to be
232: * added to the end of the data coming in from the compressed stream,
233: * accomplished by left shifting the data by the indicated amount.
234: * 0 is a special case returning 0.<p>
235: *
236: * @param number an integer representable in 16 bits or less
237: * @return number of trailing zeros
238: */
239: private static final int getShift(int number) {
240: if (number == 0)
241: return 0;
242:
243: if ((number & 0x0001) > 0)
244: return 0;
245: if ((number & 0x0002) > 0)
246: return 1;
247: if ((number & 0x0004) > 0)
248: return 2;
249: if ((number & 0x0008) > 0)
250: return 3;
251: if ((number & 0x0010) > 0)
252: return 4;
253: if ((number & 0x0020) > 0)
254: return 5;
255: if ((number & 0x0040) > 0)
256: return 6;
257: if ((number & 0x0080) > 0)
258: return 7;
259: if ((number & 0x0100) > 0)
260: return 8;
261: if ((number & 0x0200) > 0)
262: return 9;
263: if ((number & 0x0400) > 0)
264: return 10;
265: if ((number & 0x0800) > 0)
266: return 11;
267: if ((number & 0x1000) > 0)
268: return 12;
269: if ((number & 0x2000) > 0)
270: return 13;
271: if ((number & 0x4000) > 0)
272: return 14;
273:
274: return 15;
275: }
276:
277: /**
278: * Computes common length and shift of 2 numbers.
279: */
280: final void computeLengthShift(int n0, int n1) {
281: int s0 = n0 & 0x8000;
282: int s1 = n1 & 0x8000;
283:
284: // equal sign optimization
285: if (s0 == s1)
286: if (s0 == 0)
287: this .length = getLength(n0 | n1);
288: else
289: this .length = getLength(n0 & n1);
290: else
291: this .length = getMaximum(getLength(n0), getLength(n1));
292:
293: this .shift = getShift(n0 | n1);
294: }
295:
296: /**
297: * Computes common length and shift of 3 numbers.
298: */
299: final void computeLengthShift(int n0, int n1, int n2) {
300: int s0 = n0 & 0x8000;
301: int s1 = n1 & 0x8000;
302: int s2 = n2 & 0x8000;
303:
304: // equal sign optimization
305: if (s0 == s1)
306: if (s1 == s2)
307: if (s2 == 0)
308: this .length = getLength(n0 | n1 | n2);
309: else
310: this .length = getLength(n0 & n1 & n2);
311: else if (s1 == 0)
312: this .length = getMaximum(getLength(n0 | n1),
313: getLength(n2));
314: else
315: this .length = getMaximum(getLength(n0 & n1),
316: getLength(n2));
317: else if (s1 == s2)
318: if (s2 == 0)
319: this .length = getMaximum(getLength(n1 | n2),
320: getLength(n0));
321: else
322: this .length = getMaximum(getLength(n1 & n2),
323: getLength(n0));
324: else if (s0 == 0)
325: this .length = getMaximum(getLength(n0 | n2), getLength(n1));
326: else
327: this .length = getMaximum(getLength(n0 & n2), getLength(n1));
328:
329: this .shift = getShift(n0 | n1 | n2);
330: }
331:
332: /**
333: * Computes common length and shift of 4 numbers.
334: */
335: final void computeLengthShift(int n0, int n1, int n2, int n3) {
336: this .length = getMaximum(getLength(n0), getLength(n1),
337: getLength(n2), getLength(n3));
338:
339: this .shift = getShift(n0 | n1 | n2 | n3);
340: }
341:
342: /**
343: * Finds the maximum of two integers.
344: */
345: private static final int getMaximum(int x, int y) {
346: if (x > y)
347: return x;
348: else
349: return y;
350: }
351:
352: /**
353: * Finds the maximum of three integers.
354: */
355: private static final int getMaximum(int x, int y, int z) {
356: if (x > y)
357: if (x > z)
358: return x;
359: else
360: return z;
361: else if (y > z)
362: return y;
363: else
364: return z;
365: }
366:
367: /**
368: * Finds the maximum of four integers.
369: */
370: private static final int getMaximum(int x, int y, int z, int w) {
371: int n0, n1;
372:
373: if (x > y)
374: n0 = x;
375: else
376: n0 = y;
377:
378: if (z > w)
379: n1 = z;
380: else
381: n1 = w;
382:
383: if (n0 > n1)
384: return n0;
385: else
386: return n1;
387: }
388: }
|