mcs/class/ICSharpCode.SharpZipLib/ICSharpCode.SharpZipLib/Zip/Compression/InflaterHuffmanTree.cs

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