Mes documents/Visual Studio 2005/Projects/TES4ModTranslator/TES4ModTranslator/Zip/Compression/InflaterHuffmanTree.cs

Go to the documentation of this file.
00001 // InflaterHuffmanTree.cs
00002 // Copyright (C) 2001 Mike Krueger
00003 //
00004 // This file was translated from java, it was part of the GNU Classpath
00005 // Copyright (C) 2001 Free Software Foundation, Inc.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // This program is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 //
00017 // You should have received a copy of the GNU General Public License
00018 // along with this program; if not, write to the Free Software
00019 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
00020 //
00021 // Linking this library statically or dynamically with other modules is
00022 // making a combined work based on this library.  Thus, the terms and
00023 // conditions of the GNU General Public License cover the whole
00024 // combination.
00025 // 
00026 // As a special exception, the copyright holders of this library give you
00027 // permission to link this library with independent modules to produce an
00028 // executable, regardless of the license terms of these independent
00029 // modules, and to copy and distribute the resulting executable under
00030 // terms of your choice, provided that you also meet, for each linked
00031 // independent module, the terms and conditions of the license of that
00032 // module.  An independent module is a module which is not derived from
00033 // or based on this library.  If you modify this library, you may extend
00034 // this exception to your version of the library, but you are not
00035 // obligated to do so.  If you do not wish to do so, delete this
00036 // exception statement from your version.
00037 
00038 using System;
00039 
00040 using ICSharpCode.SharpZipLib.Zip.Compression.Streams;
00041 
00042 namespace ICSharpCode.SharpZipLib.Zip.Compression 
00043 {
00044         
00048         public class InflaterHuffmanTree 
00049         {
00050                 static int MAX_BITLEN = 15;
00051                 short[] tree;
00052                 
00056                 public static InflaterHuffmanTree defLitLenTree;
00057                 
00061                 public static InflaterHuffmanTree defDistTree;
00062                 
00063                 static InflaterHuffmanTree()
00064                 {
00065                         try {
00066                                 byte[] codeLengths = new byte[288];
00067                                 int i = 0;
00068                                 while (i < 144) {
00069                                         codeLengths[i++] = 8;
00070                                 }
00071                                 while (i < 256) {
00072                                         codeLengths[i++] = 9;
00073                                 }
00074                                 while (i < 280) {
00075                                         codeLengths[i++] = 7;
00076                                 }
00077                                 while (i < 288) {
00078                                         codeLengths[i++] = 8;
00079                                 }
00080                                 defLitLenTree = new InflaterHuffmanTree(codeLengths);
00081                                 
00082                                 codeLengths = new byte[32];
00083                                 i = 0;
00084                                 while (i < 32) {
00085                                         codeLengths[i++] = 5;
00086                                 }
00087                                 defDistTree = new InflaterHuffmanTree(codeLengths);
00088                         } catch (Exception) {
00089                                 throw new SharpZipBaseException("InflaterHuffmanTree: static tree length illegal");
00090                         }
00091                 }
00092                 
00099                 public InflaterHuffmanTree(byte[] codeLengths)
00100                 {
00101                         BuildTree(codeLengths);
00102                 }
00103                 
00104                 void BuildTree(byte[] codeLengths)
00105                 {
00106                         int[] blCount  = new int[MAX_BITLEN + 1];
00107                         int[] nextCode = new int[MAX_BITLEN + 1];
00108                         
00109                         for (int i = 0; i < codeLengths.Length; i++) {
00110                                 int bits = codeLengths[i];
00111                                 if (bits > 0) {
00112                                         blCount[bits]++;
00113                                 }
00114                         }
00115                         
00116                         int code = 0;
00117                         int treeSize = 512;
00118                         for (int bits = 1; bits <= MAX_BITLEN; bits++) {
00119                                 nextCode[bits] = code;
00120                                 code += blCount[bits] << (16 - bits);
00121                                 if (bits >= 10) {
00122                                         /* We need an extra table for bit lengths >= 10. */
00123                                         int start = nextCode[bits] & 0x1ff80;
00124                                         int end   = code & 0x1ff80;
00125                                         treeSize += (end - start) >> (16 - bits);
00126                                 }
00127                         }
00128                         
00129 /* -jr comment this out! doesnt work for dynamic trees and pkzip 2.04g
00130                         if (code != 65536) 
00131                         {
00132                                 throw new SharpZipBaseException("Code lengths don't add up properly.");
00133                         }
00134 */
00135                         /* Now create and fill the extra tables from longest to shortest
00136                         * bit len.  This way the sub trees will be aligned.
00137                         */
00138                         tree = new short[treeSize];
00139                         int treePtr = 512;
00140                         for (int bits = MAX_BITLEN; bits >= 10; bits--) {
00141                                 int end   = code & 0x1ff80;
00142                                 code -= blCount[bits] << (16 - bits);
00143                                 int start = code & 0x1ff80;
00144                                 for (int i = start; i < end; i += 1 << 7) {
00145                                         tree[DeflaterHuffman.BitReverse(i)] = (short) ((-treePtr << 4) | bits);
00146                                         treePtr += 1 << (bits-9);
00147                                 }
00148                         }
00149                         
00150                         for (int i = 0; i < codeLengths.Length; i++) {
00151                                 int bits = codeLengths[i];
00152                                 if (bits == 0) {
00153                                         continue;
00154                                 }
00155                                 code = nextCode[bits];
00156                                 int revcode = DeflaterHuffman.BitReverse(code);
00157                                 if (bits <= 9) {
00158                                         do {
00159                                                 tree[revcode] = (short) ((i << 4) | bits);
00160                                                 revcode += 1 << bits;
00161                                         } while (revcode < 512);
00162                                 } else {
00163                                         int subTree = tree[revcode & 511];
00164                                         int treeLen = 1 << (subTree & 15);
00165                                         subTree = -(subTree >> 4);
00166                                         do {
00167                                                 tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits);
00168                                                 revcode += 1 << bits;
00169                                         } while (revcode < treeLen);
00170                                 }
00171                                 nextCode[bits] = code + (1 << (16 - bits));
00172                         }
00173                         
00174                 }
00175                 
00186                 public int GetSymbol(StreamManipulator input)
00187                 {
00188                         int lookahead, symbol;
00189                         if ((lookahead = input.PeekBits(9)) >= 0) {
00190                                 if ((symbol = tree[lookahead]) >= 0) {
00191                                         input.DropBits(symbol & 15);
00192                                         return symbol >> 4;
00193                                 }
00194                                 int subtree = -(symbol >> 4);
00195                                 int bitlen = symbol & 15;
00196                                 if ((lookahead = input.PeekBits(bitlen)) >= 0) {
00197                                         symbol = tree[subtree | (lookahead >> 9)];
00198                                         input.DropBits(symbol & 15);
00199                                         return symbol >> 4;
00200                                 } else {
00201                                         int bits = input.AvailableBits;
00202                                         lookahead = input.PeekBits(bits);
00203                                         symbol = tree[subtree | (lookahead >> 9)];
00204                                         if ((symbol & 15) <= bits) {
00205                                                 input.DropBits(symbol & 15);
00206                                                 return symbol >> 4;
00207                                         } else {
00208                                                 return -1;
00209                                         }
00210                                 }
00211                         } else {
00212                                 int bits = input.AvailableBits;
00213                                 lookahead = input.PeekBits(bits);
00214                                 symbol = tree[lookahead];
00215                                 if (symbol >= 0 && (symbol & 15) <= bits) {
00216                                         input.DropBits(symbol & 15);
00217                                         return symbol >> 4;
00218                                 } else {
00219                                         return -1;
00220                                 }
00221                         }
00222                 }
00223         }
00224 }
00225 

Generated on Fri Jun 23 21:50:05 2006 for OblivionModTranslator by  doxygen 1.4.6-NO