code.grnet.gr Git - pithos-ms-client/blob - trunk/hammock/src/net35/ICSharpCode.SharpZipLib.Silverlight/Zip/Compression/InflaterHuffmanTree.cs

   1 // InflaterHuffmanTree.cs
   2 // Copyright (C) 2001 Mike Krueger
   3 //
   4 // This file was translated from java, it was part of the GNU Classpath
   5 // Copyright (C) 2001 Free Software Foundation, Inc.
   6 //
   7 // This program is free software; you can redistribute it and/or
   8 // modify it under the terms of the GNU General Public License
   9 // as published by the Free Software Foundation; either version 2
  10 // of the License, or (at your option) any later version.
  11 //
  12 // This program is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16 //
  17 // You should have received a copy of the GNU General Public License
  18 // along with this program; if not, write to the Free Software
  19 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  20 //
  21 // Linking this library statically or dynamically with other modules is
  22 // making a combined work based on this library.  Thus, the terms and
  23 // conditions of the GNU General Public License cover the whole
  24 // combination.
  25 //
  26 // As a special exception, the copyright holders of this library give you
  27 // permission to link this library with independent modules to produce an
  28 // executable, regardless of the license terms of these independent
  29 // modules, and to copy and distribute the resulting executable under
  30 // terms of your choice, provided that you also meet, for each linked
  31 // independent module, the terms and conditions of the license of that
  32 // module.  An independent module is a module which is not derived from
  33 // or based on this library.  If you modify this library, you may extend
  34 // this exception to your version of the library, but you are not
  35 // obligated to do so.  If you do not wish to do so, delete this
  36 // exception statement from your version.
  37
  38 using System;
  39 using ICSharpCode.SharpZipLib.Silverlight.Zip.Compression;
  40 using ICSharpCode.SharpZipLib.Silverlight.Zip.Compression.Streams;
  41
  42 namespace ICSharpCode.SharpZipLib.Silverlight.Zip.Compression
  43 {
  44     /// <summary>
  45     /// Huffman tree used for inflation
  46     /// </summary>
  47     public class InflaterHuffmanTree
  48     {
  49         #region Constants
  50         const int MAX_BITLEN = 15;
  51         #endregion
  52
  53         #region Instance Fields
  54         short[] tree;
  55         #endregion
  56
  57         /// <summary>
  58         /// Literal length tree
  59         /// </summary>
  60         public static InflaterHuffmanTree defLitLenTree;
  61
  62         /// <summary>
  63         /// Distance tree
  64         /// </summary>
  65         public static InflaterHuffmanTree defDistTree;
  66
  67         static InflaterHuffmanTree()
  68         {
  69             try {
  70                 byte[] codeLengths = new byte[288];
  71                 int i = 0;
  72                 while (i < 144) {
  73                     codeLengths[i++] = 8;
  74                 }
  75                 while (i < 256) {
  76                     codeLengths[i++] = 9;
  77                 }
  78                 while (i < 280) {
  79                     codeLengths[i++] = 7;
  80                 }
  81                 while (i < 288) {
  82                     codeLengths[i++] = 8;
  83                 }
  84                 defLitLenTree = new InflaterHuffmanTree(codeLengths);
  85
  86                 codeLengths = new byte[32];
  87                 i = 0;
  88                 while (i < 32) {
  89                     codeLengths[i++] = 5;
  90                 }
  91                 defDistTree = new InflaterHuffmanTree(codeLengths);
  92             } catch (Exception) {
  93                 throw new SharpZipBaseException("InflaterHuffmanTree: static tree length illegal");
  94             }
  95         }
  96
  97         #region Constructors
  98         /// <summary>
  99         /// Constructs a Huffman tree from the array of code lengths.
 100         /// </summary>
 101         /// <param name = "codeLengths">
 102         /// the array of code lengths
 103         /// </param>
 104         public InflaterHuffmanTree(byte[] codeLengths)
 105         {
 106             BuildTree(codeLengths);
 107         }
 108         #endregion
 109
 110         void BuildTree(byte[] codeLengths)
 111         {
 112             int[] blCount  = new int[MAX_BITLEN + 1];
 113             int[] nextCode = new int[MAX_BITLEN + 1];
 114
 115             for (int i = 0; i < codeLengths.Length; i++) {
 116                 int bits = codeLengths[i];
 117                 if (bits > 0) {
 118                     blCount[bits]++;
 119                 }
 120             }
 121
 122             int code = 0;
 123             int treeSize = 512;
 124             for (int bits = 1; bits <= MAX_BITLEN; bits++) {
 125                 nextCode[bits] = code;
 126                 code += blCount[bits] << (16 - bits);
 127                 if (bits >= 10) {
 128                     /* We need an extra table for bit lengths >= 10. */
 129                     int start = nextCode[bits] & 0x1ff80;
 130                     int end   = code & 0x1ff80;
 131                     treeSize += (end - start) >> (16 - bits);
 132                 }
 133             }
 134
 135 /* -jr comment this out! doesnt work for dynamic trees and pkzip 2.04g
 136                         if (code != 65536)
 137                         {
 138                                 throw new SharpZipBaseException("Code lengths don't add up properly.");
 139                         }
 140 */
 141             /* Now create and fill the extra tables from longest to shortest
 142                         * bit len.  This way the sub trees will be aligned.
 143                         */
 144             tree = new short[treeSize];
 145             int treePtr = 512;
 146             for (int bits = MAX_BITLEN; bits >= 10; bits--) {
 147                 int end   = code & 0x1ff80;
 148                 code -= blCount[bits] << (16 - bits);
 149                 int start = code & 0x1ff80;
 150                 for (int i = start; i < end; i += 1 << 7) {
 151                     tree[DeflaterHuffman.BitReverse(i)] = (short) ((-treePtr << 4) | bits);
 152                     treePtr += 1 << (bits-9);
 153                 }
 154             }
 155
 156             for (int i = 0; i < codeLengths.Length; i++) {
 157                 int bits = codeLengths[i];
 158                 if (bits == 0) {
 159                     continue;
 160                 }
 161                 code = nextCode[bits];
 162                 int revcode = DeflaterHuffman.BitReverse(code);
 163                 if (bits <= 9) {
 164                     do {
 165                         tree[revcode] = (short) ((i << 4) | bits);
 166                         revcode += 1 << bits;
 167                     } while (revcode < 512);
 168                 } else {
 169                     int subTree = tree[revcode & 511];
 170                     int treeLen = 1 << (subTree & 15);
 171                     subTree = -(subTree >> 4);
 172                     do {
 173                         tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits);
 174                         revcode += 1 << bits;
 175                     } while (revcode < treeLen);
 176                 }
 177                 nextCode[bits] = code + (1 << (16 - bits));
 178             }
 179
 180         }
 181
 182         /// <summary>
 183         /// Reads the next symbol from input.  The symbol is encoded using the
 184         /// huffman tree.
 185         /// </summary>
 186         /// <param name="input">
 187         /// input the input source.
 188         /// </param>
 189         /// <returns>
 190         /// the next symbol, or -1 if not enough input is available.
 191         /// </returns>
 192         public int GetSymbol(StreamManipulator input)
 193         {
 194             int lookahead, symbol;
 195             if ((lookahead = input.PeekBits(9)) >= 0) {
 196                 if ((symbol = tree[lookahead]) >= 0) {
 197                     input.DropBits(symbol & 15);
 198                     return symbol >> 4;
 199                 }
 200                 int subtree = -(symbol >> 4);
 201                 int bitlen = symbol & 15;
 202                 if ((lookahead = input.PeekBits(bitlen)) >= 0) {
 203                     symbol = tree[subtree | (lookahead >> 9)];
 204                     input.DropBits(symbol & 15);
 205                     return symbol >> 4;
 206                 } else {
 207                     int bits = input.AvailableBits;
 208                     lookahead = input.PeekBits(bits);
 209                     symbol = tree[subtree | (lookahead >> 9)];
 210                     if ((symbol & 15) <= bits) {
 211                         input.DropBits(symbol & 15);
 212                         return symbol >> 4;
 213                     } else {
 214                         return -1;
 215                     }
 216                 }
 217             } else {
 218                 int bits = input.AvailableBits;
 219                 lookahead = input.PeekBits(bits);
 220                 symbol = tree[lookahead];
 221                 if (symbol >= 0 && (symbol & 15) <= bits) {
 222                     input.DropBits(symbol & 15);
 223                     return symbol >> 4;
 224                 } else {
 225                     return -1;
 226                 }
 227             }
 228         }
 229     }
 230 }