Source Code Cross Referenced for HuffmanTable.java in  » 6.0-JDK-Modules » java-3d » com » sun » j3d » utils » compression » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » 6.0 JDK Modules » java 3d » com.sun.j3d.utils.compression 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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.5 $
041:         * $Date: 2007/02/09 17:20:17 $
042:         * $State: Exp $
043:         */
044:
045:        package com.sun.j3d.utils.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:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.