001: /*
002: * $RCSfile: HuffmanTable.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:23 $
042: * $State: Exp $
043: */
044:
045: package com.sun.j3d.utils.geometry.compression;
046:
047: import java.util.Collection;
048: import java.util.Collections;
049: import java.util.Comparator;
050: import java.util.Iterator;
051: import java.util.LinkedList;
052: import java.util.ListIterator;
053:
054: /**
055: * This class maintains a map from compression stream elements (tokens) onto
056: * HuffmanNode objects. A HuffmanNode contains a tag describing the
057: * associated token's data length, right shift value, and absolute/relative
058: * status.<p>
059: *
060: * The tags are computed using Huffman's algorithm to build a binary tree with
061: * a minimal total weighted path length. The frequency of each token is
062: * used as its node's weight when building the tree. The path length from the
063: * root to the token's node then indicates the bit length that should be used
064: * for that token's tag in order to minimize the total size of the compressed
065: * stream.
066: */
067: class HuffmanTable {
068: private static final int MAX_TAG_LENGTH = 6;
069:
070: private HuffmanNode positions[];
071: private HuffmanNode normals[];
072: private HuffmanNode colors[];
073:
074: /**
075: * Create a new HuffmanTable with entries for all possible position,
076: * normal, and color tokens.
077: */
078: HuffmanTable() {
079: //
080: // Position and color components can have data lengths up to 16
081: // bits, with right shifts up to 15 bits. The position and color
082: // lookup tables are therefore 2*17*16=544 entries in length to
083: // account for all possible combinations of data lengths, shifts,
084: // and relative or absolute status.
085: //
086: colors = new HuffmanNode[544];
087: positions = new HuffmanNode[544];
088:
089: //
090: // Delta normals can have uv components up to 7 bits in length with
091: // right shifts up to 6 bits. Absolute normals can have uv components
092: // up to 6 bits in length with right shifts up to 5 bits. The normal
093: // lookup table is therefore 2*8*7=112 entries in length.
094: //
095: normals = new HuffmanNode[112];
096: }
097:
098: private final int getPositionIndex(int len, int shift,
099: boolean absolute) {
100: return (absolute ? 1 : 0) * 272 + len * 16 + shift;
101: }
102:
103: private final int getNormalIndex(int length, int shift,
104: boolean absolute) {
105: return (absolute ? 1 : 0) * 56 + length * 7 + shift;
106: }
107:
108: private final int getColorIndex(int length, int shift,
109: boolean absolute) {
110: return getPositionIndex(length, shift, absolute);
111: }
112:
113: /**
114: * Add a position entry with the given length, shift, and absolute
115: * status.
116: *
117: * @param length number of bits in each X, Y, and Z component
118: * @param shift number of trailing zeros in each component
119: * @param absolute if false, value represented is a delta from the
120: * previous vertex in the compression stream
121: */
122: void addPositionEntry(int length, int shift, boolean absolute) {
123: addEntry(positions, getPositionIndex(length, shift, absolute),
124: length, shift, absolute);
125: }
126:
127: /**
128: * Get the position entry associated with the specified length, shift, and
129: * absolute status. This will contain a tag indicating the actual
130: * encoding to be used in the compression command stream, not necessarily
131: * the same as the original length and shift with which the the entry was
132: * created.
133: *
134: * @param length number of bits in each X, Y, and Z component
135: * @param shift number of trailing zeros in each component
136: * @param absolute if false, value represented is a delta from the
137: * previous vertex in the compression stream
138: * @return HuffmanNode mapped to the specified parameters
139: */
140: HuffmanNode getPositionEntry(int length, int shift, boolean absolute) {
141: return getEntry(positions, getPositionIndex(length, shift,
142: absolute));
143: }
144:
145: /**
146: * Add a color entry with the given length, shift, and absolute
147: * status.
148: *
149: * @param length number of bits in each R, G, B, and A component
150: * @param shift number of trailing zeros in each component
151: * @param absolute if false, value represented is a delta from the
152: * previous color in the compression stream
153: */
154: void addColorEntry(int length, int shift, boolean absolute) {
155: addEntry(colors, getColorIndex(length, shift, absolute),
156: length, shift, absolute);
157: }
158:
159: /**
160: * Get the color entry associated with the specified length, shift, and
161: * absolute status. This will contain a tag indicating the actual
162: * encoding to be used in the compression command stream, not necessarily
163: * the same as the original length and shift with which the the entry was
164: * created.
165: *
166: * @param length number of bits in each R, G, B, and A component
167: * @param shift number of trailing zeros in each component
168: * @param absolute if false, value represented is a delta from the
169: * previous color in the compression stream
170: * @return HuffmanNode mapped to the specified parameters
171: */
172: HuffmanNode getColorEntry(int length, int shift, boolean absolute) {
173: return getEntry(colors, getColorIndex(length, shift, absolute));
174: }
175:
176: /**
177: * Add a normal entry with the given length, shift, and absolute
178: * status.
179: *
180: * @param length number of bits in each U and V component
181: * @param shift number of trailing zeros in each component
182: * @param absolute if false, value represented is a delta from the
183: * previous normal in the compression stream
184: */
185: void addNormalEntry(int length, int shift, boolean absolute) {
186: addEntry(normals, getNormalIndex(length, shift, absolute),
187: length, shift, absolute);
188: }
189:
190: /**
191: * Get the normal entry associated with the specified length, shift, and
192: * absolute status. This will contain a tag indicating the actual
193: * encoding to be used in the compression command stream, not necessarily
194: * the same as the original length and shift with which the the entry was
195: * created.
196: *
197: * @param length number of bits in each U and V component
198: * @param shift number of trailing zeros in each component
199: * @param absolute if false, value represented is a delta from the
200: * previous normal in the compression stream
201: * @return HuffmanNode mapped to the specified parameters
202: */
203: HuffmanNode getNormalEntry(int length, int shift, boolean absolute) {
204: return getEntry(normals,
205: getNormalIndex(length, shift, absolute));
206: }
207:
208: private void addEntry(HuffmanNode table[], int index, int length,
209: int shift, boolean absolute) {
210:
211: if (table[index] == null)
212: table[index] = new HuffmanNode(length, shift, absolute);
213:
214: else if (table[index].cleared())
215: table[index].set(length, shift, absolute);
216:
217: table[index].addCount();
218: }
219:
220: private HuffmanNode getEntry(HuffmanNode table[], int index) {
221: HuffmanNode t = table[index];
222:
223: while (t.merged())
224: t = t.getMergeNode();
225:
226: return t;
227: }
228:
229: private void getEntries(HuffmanNode table[], Collection c) {
230: for (int i = 0; i < table.length; i++)
231: if (table[i] != null && !table[i].cleared()
232: && table[i].hasCount() && !table[i].merged())
233: c.add(table[i]);
234: }
235:
236: /**
237: * Clear this HuffmanTable instance.
238: */
239: void clear() {
240: for (int i = 0; i < positions.length; i++)
241: if (positions[i] != null)
242: positions[i].clear();
243:
244: for (int i = 0; i < colors.length; i++)
245: if (colors[i] != null)
246: colors[i].clear();
247:
248: for (int i = 0; i < normals.length; i++)
249: if (normals[i] != null)
250: normals[i].clear();
251: }
252:
253: /**
254: * Compute optimized tags for each position, color, and normal entry.
255: */
256: void computeTags() {
257: LinkedList nodeList = new LinkedList();
258: getEntries(positions, nodeList);
259: computeTags(nodeList, 3);
260:
261: nodeList.clear();
262: getEntries(colors, nodeList);
263: computeTags(nodeList, 3);
264:
265: nodeList.clear();
266: getEntries(normals, nodeList);
267: computeTags(nodeList, 2);
268: }
269:
270: //
271: // Compute tags for a list of Huffman tokens.
272: //
273: private void computeTags(LinkedList nodes, int minComponentCount) {
274: HuffmanNode node0, node1, node2;
275:
276: // Return if there's nothing to do.
277: if (nodes.isEmpty())
278: return;
279:
280: while (true) {
281: // Sort the nodes in ascending order by frequency.
282: Collections.sort(nodes, HuffmanNode.frequencyComparator);
283:
284: // Apply Huffman's algorithm to construct a binary tree with a
285: // minimum total weighted path length.
286: node0 = (HuffmanNode) nodes.removeFirst();
287: while (nodes.size() > 0) {
288: node1 = (HuffmanNode) nodes.removeFirst();
289: node2 = new HuffmanNode();
290:
291: node2.addChildren(node0, node1);
292: addNodeInOrder(nodes, node2,
293: HuffmanNode.frequencyComparator);
294:
295: node0 = (HuffmanNode) nodes.removeFirst();
296: }
297:
298: // node0 is the root of the resulting binary tree. Traverse it
299: // assigning tags and lengths to the leaf nodes. The leaves are
300: // collected into the now empty node list.
301: node0.collectLeaves(0, 0, nodes);
302:
303: // Sort the nodes in descending order by tag length.
304: Collections.sort(nodes, HuffmanNode.tagLengthComparator);
305:
306: // Check for tag length overrun.
307: if (((HuffmanNode) nodes.getFirst()).tagLength > MAX_TAG_LENGTH) {
308: // Tokens need to be merged and the tree rebuilt with the new
309: // combined frequencies.
310: merge(nodes);
311:
312: } else {
313: // Increase tag length + data length if they're too small.
314: expand(nodes, minComponentCount);
315: break;
316: }
317: }
318: }
319:
320: //
321: // Merge a token with a long tag into some other token. The merged token
322: // will be removed from the list along with any duplicate node the merge
323: // created, reducing the size of the list by 1 or 2 elements until only
324: // unmergeable tokens are left.
325: //
326: private void merge(LinkedList nodes) {
327: ListIterator i = nodes.listIterator(0);
328: HuffmanNode node0, node1, node2;
329: int index = 0;
330:
331: while (i.hasNext()) {
332: // Get the node with the longest possibly mergeable tag.
333: node0 = (HuffmanNode) i.next();
334: if (node0.unmergeable())
335: continue;
336:
337: // Try to find a node that can be merged with node0. This is any
338: // node that matches its absolute/relative status.
339: i.remove();
340: while (i.hasNext()) {
341: node1 = (HuffmanNode) i.next();
342: if (node0.mergeInto(node1)) {
343: // Search for a duplicate of the possibly modified node1
344: // and merge into it so that node weights remain valid.
345: // If a duplicate exists it must be further in the list,
346: // otherwise node0 would have merged into it.
347: i.remove();
348: while (i.hasNext()) {
349: node2 = (HuffmanNode) i.next();
350: if (node1.tokenEquals(node2)) {
351: node1.mergeInto(node2);
352: return;
353: }
354: }
355: // node1 has no duplicate, so return it to the list.
356: i.add(node1);
357: return;
358: }
359: }
360:
361: // node0 can't be merged with any other node; it must be the only
362: // relative or absolute node in the list. Mark it as unmergeable
363: // to avoid unnecessary searches on subsequent calls to merge()
364: // and return it to the list.
365: node0.setUnmergeable();
366: i.add(node0);
367:
368: // Restart the iteration.
369: i = nodes.listIterator(0);
370: }
371: }
372:
373: //
374: // Empty bits within a compression command header are not allowed. If
375: // the tag length plus the total data length is less than 6 bits then
376: // the token's length must be increased.
377: //
378: private void expand(LinkedList nodes, int minComponentCount) {
379: Iterator i = nodes.iterator();
380:
381: while (i.hasNext()) {
382: HuffmanNode n = (HuffmanNode) i.next();
383:
384: while (n.tagLength
385: + (minComponentCount * (n.dataLength - n.shift)) < 6) {
386:
387: n.incrementLength();
388: }
389: }
390: }
391:
392: //
393: // Insert a node into the correct place in a sorted list of nodes.
394: //
395: private void addNodeInOrder(LinkedList l, HuffmanNode node,
396: Comparator c) {
397: ListIterator i = l.listIterator(0);
398:
399: while (i.hasNext()) {
400: HuffmanNode n = (HuffmanNode) i.next();
401: if (c.compare(n, node) > 0) {
402: n = (HuffmanNode) i.previous();
403: break;
404: }
405: }
406: i.add(node);
407: }
408:
409: /**
410: * Create compression stream commands for decompressors to use to set up
411: * their decompression tables.
412: *
413: * @param output CommandStream which receives the compression commands
414: */
415: void outputCommands(CommandStream output) {
416: LinkedList nodeList = new LinkedList();
417: getEntries(positions, nodeList);
418: outputCommands(nodeList, output, CommandStream.POSITION_TABLE);
419:
420: nodeList.clear();
421: getEntries(colors, nodeList);
422: outputCommands(nodeList, output, CommandStream.COLOR_TABLE);
423:
424: nodeList.clear();
425: getEntries(normals, nodeList);
426: outputCommands(nodeList, output, CommandStream.NORMAL_TABLE);
427: }
428:
429: //
430: // Output a setTable command for each unique token.
431: //
432: private void outputCommands(Collection nodes, CommandStream output,
433: int tableId) {
434:
435: Iterator i = nodes.iterator();
436: while (i.hasNext()) {
437: HuffmanNode n = (HuffmanNode) i.next();
438: int addressRange = (1 << n.tagLength) | n.tag;
439: int dataLength = (n.dataLength == 16 ? 0 : n.dataLength);
440:
441: int command = CommandStream.SET_TABLE | (tableId << 1)
442: | (addressRange >> 6);
443:
444: long body = ((addressRange & 0x3f) << 9)
445: | (dataLength << 5) | (n.absolute ? 0x10 : 0)
446: | n.shift;
447:
448: output.addCommand(command, 8, body, 15);
449: }
450: }
451:
452: /**
453: * Print a collection of HuffmanNode objects to standard out.
454: *
455: * @param header descriptive string
456: * @param nodes Collection of HuffmanNode objects to print
457: */
458: void print(String header, Collection nodes) {
459: System.out
460: .println(header + "\nentries: " + nodes.size() + "\n");
461:
462: Iterator i = nodes.iterator();
463: while (i.hasNext()) {
464: HuffmanNode n = (HuffmanNode) i.next();
465: System.out.println(n.toString() + "\n");
466: }
467: }
468:
469: /**
470: * Print the contents of this instance to standard out.
471: */
472: void print() {
473: LinkedList nodeList = new LinkedList();
474:
475: getEntries(positions, nodeList);
476: Collections.sort(nodeList, HuffmanNode.frequencyComparator);
477: print("\nposition tokens and tags", nodeList);
478:
479: nodeList.clear();
480: getEntries(colors, nodeList);
481: Collections.sort(nodeList, HuffmanNode.frequencyComparator);
482: print("\ncolor tokens and tags", nodeList);
483:
484: nodeList.clear();
485: getEntries(normals, nodeList);
486: Collections.sort(nodeList, HuffmanNode.frequencyComparator);
487: print("\nnormal tokens and tags", nodeList);
488: }
489: }
|