1 /* 2 * $RCSfile: HuffmanNode.java,v $ 3 * 4 * Copyright (c) 2007 Sun Microsystems, Inc. All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 10 * - Redistribution of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 13 * - Redistribution in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * 18 * Neither the name of Sun Microsystems, Inc. or the names of 19 * contributors may be used to endorse or promote products derived 20 * from this software without specific prior written permission. 21 * 22 * This software is provided "AS IS," without a warranty of any 23 * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND 24 * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, 25 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY 26 * EXCLUDED. SUN MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL 27 * NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF 28 * USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS 29 * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR 30 * ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, 31 * CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND 32 * REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR 33 * INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE 34 * POSSIBILITY OF SUCH DAMAGES. 35 * 36 * You acknowledge that this software is not designed, licensed or 37 * intended for use in the design, construction, operation or 38 * maintenance of any nuclear facility. 39 * 40 * $Revision: 1.5 $ 41 * $Date: 2007/02/09 17:20:17 $ 42 * $State: Exp $ 43 */ 44 45 package com.sun.j3d.utils.compression; 46 47 import java.util.Collection; 48 import java.util.Comparator; 49 50 /** 51 * Instances of this class are used as the nodes of binary trees representing 52 * mappings of tags to compression stream elements. Tags are descriptors 53 * inserted into the compression command stream that specify the encoding of 54 * immediately succeeding data elements.<p> 55 * 56 * The tag assignments in such a tree are computed from the paths taken from 57 * the root to the leaf nodes. Each leaf node represents the particular way 58 * one or more compression stream elements wound up being encoded with respect 59 * to various combinations of data lengths, shifts, and absolute/relative 60 * status.<p> 61 * 62 * Huffman's algorithm for constructing binary trees with minimal weighted 63 * path lengths can be used to optimize the bit lengths of the tags with 64 * respect to the frequency of occurrence of their associated data encodings 65 * in the compression stream. The weighted path length is the sum of the 66 * frequencies of all the leaf nodes times their path lengths to the root of 67 * the tree.<p> 68 * 69 * The length of the longest tag determines the size of the table mapping tags 70 * to data representations. The geometry compression specification limits the 71 * size of the table to 64 entries, so tags cannot be longer than 6 bits. The 72 * depth of the tree is reduced through a process of increasing the data 73 * lengths of less frequently occuring nodes so they can be merged with other 74 * more frequent nodes. 75 */ 76 class HuffmanNode { 77 int tag, tagLength ; 78 int shift, dataLength ; 79 boolean absolute ; 80 81 private int frequency ; 82 private HuffmanNode child0, child1, mergeNode ; 83 private boolean merged, unmergeable, cleared ; 84 clear()85 void clear() { 86 tag = -1 ; 87 tagLength = -1 ; 88 89 shift = -1 ; 90 dataLength = -1 ; 91 absolute = false ; 92 93 child0 = null ; 94 child1 = null ; 95 mergeNode = null ; 96 97 frequency = 0 ; 98 merged = false ; 99 unmergeable = false ; 100 cleared = true ; 101 } 102 HuffmanNode()103 HuffmanNode() { 104 clear() ; 105 } 106 HuffmanNode(int length, int shift, boolean absolute)107 HuffmanNode(int length, int shift, boolean absolute) { 108 this() ; 109 set(length, shift, absolute) ; 110 } 111 set(int length, int shift, boolean absolute)112 final void set(int length, int shift, boolean absolute) { 113 this.dataLength = length ; 114 this.shift = shift ; 115 this.absolute = absolute ; 116 this.cleared = false ; 117 } 118 cleared()119 final boolean cleared() { 120 return cleared ; 121 } 122 addCount()123 final void addCount() { 124 frequency++ ; 125 } 126 hasCount()127 final boolean hasCount() { 128 return frequency > 0 ; 129 } 130 tokenEquals(HuffmanNode node)131 final boolean tokenEquals(HuffmanNode node) { 132 return 133 this.absolute == node.absolute && 134 this.dataLength == node.dataLength && 135 this.shift == node.shift ; 136 } 137 addChildren(HuffmanNode child0, HuffmanNode child1)138 void addChildren(HuffmanNode child0, HuffmanNode child1) { 139 this.child0 = child0 ; 140 this.child1 = child1 ; 141 this.frequency = child0.frequency + child1.frequency ; 142 } 143 collectLeaves(int tag, int tagLength, Collection collection)144 void collectLeaves(int tag, int tagLength, Collection collection) { 145 if (child0 == null) { 146 this.tag = tag ; 147 this.tagLength = tagLength ; 148 collection.add(this) ; 149 } else { 150 child0.collectLeaves((tag << 1) | 0, tagLength + 1, collection) ; 151 child1.collectLeaves((tag << 1) | 1, tagLength + 1, collection) ; 152 } 153 } 154 mergeInto(HuffmanNode node)155 boolean mergeInto(HuffmanNode node) { 156 if (this.absolute == node.absolute) { 157 if (this.dataLength > node.dataLength) 158 node.dataLength = this.dataLength ; 159 160 if (this.shift < node.shift) 161 node.shift = this.shift ; 162 163 node.frequency += this.frequency ; 164 this.mergeNode = node ; 165 this.merged = true ; 166 return true ; 167 168 } else 169 return false ; 170 } 171 incrementLength()172 int incrementLength() { 173 if (shift > 0) 174 shift-- ; 175 else 176 dataLength++ ; 177 178 return dataLength - shift ; 179 } 180 merged()181 final boolean merged() { 182 return merged ; 183 } 184 getMergeNode()185 final HuffmanNode getMergeNode() { 186 return mergeNode ; 187 } 188 setUnmergeable()189 void setUnmergeable() { 190 unmergeable = true ; 191 } 192 unmergeable()193 final boolean unmergeable() { 194 return unmergeable ; 195 } 196 toString()197 public String toString() { 198 return 199 "shift " + shift + " data length " + dataLength + 200 (absolute? " absolute " : " relative ") + 201 "\ntag 0x" + Integer.toHexString(tag) + " tag length " + tagLength + 202 "\nfrequency: " + frequency ; 203 } 204 205 /** 206 * Sorts nodes in ascending order by frequency. 207 */ 208 static class FrequencyComparator implements Comparator { compare(Object o1, Object o2)209 public final int compare(Object o1, Object o2) { 210 return ((HuffmanNode)o1).frequency - ((HuffmanNode)o2).frequency ; 211 } 212 } 213 214 /** 215 * Sorts nodes in descending order by tag bit length. 216 */ 217 static class TagLengthComparator implements Comparator { compare(Object o1, Object o2)218 public final int compare(Object o1, Object o2) { 219 return ((HuffmanNode)o2).tagLength - ((HuffmanNode)o1).tagLength ; 220 } 221 } 222 223 static FrequencyComparator frequencyComparator = new FrequencyComparator() ; 224 static TagLengthComparator tagLengthComparator = new TagLengthComparator() ; 225 } 226