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         public class InflaterHuffmanTree \r
  46         {\r
  47                 private static int MAX_BITLEN = 15;\r
  48                 private short[] tree;\r
  49                 \r
  50                 public static InflaterHuffmanTree defLitLenTree, defDistTree;\r
  51                 \r
  52                 static InflaterHuffmanTree()\r
  53                 {\r
  54                         try {\r
  55                                 byte[] codeLengths = new byte[288];\r
  56                                 int i = 0;\r
  57                                 while (i < 144) {\r
  58                                         codeLengths[i++] = 8;\r
  59                                 }\r
  60                                 while (i < 256) {\r
  61                                         codeLengths[i++] = 9;\r
  62                                 }\r
  63                                 while (i < 280) {\r
  64                                         codeLengths[i++] = 7;\r
  65                                 }\r
  66                                 while (i < 288) {\r
  67                                         codeLengths[i++] = 8;\r
  68                                 }\r
  69                                 defLitLenTree = new InflaterHuffmanTree(codeLengths);\r
  70                                 \r
  71                                 codeLengths = new byte[32];\r
  72                                 i = 0;\r
  73                                 while (i < 32) {\r
  74                                         codeLengths[i++] = 5;\r
  75                                 }\r
  76                                 defDistTree = new InflaterHuffmanTree(codeLengths);\r
  77                         } catch (Exception) {\r
  78                                 throw new ApplicationException("InflaterHuffmanTree: static tree length illegal");\r
  79                         }\r
  80                 }\r
  81                 \r
  82                 /// <summary>\r
  83                 /// Constructs a Huffman tree from the array of code lengths.\r
  84                 /// </summary>\r
  85                 /// <param name = "codeLengths">\r
  86                 /// the array of code lengths\r
  87                 /// </param>\r
  88                 public InflaterHuffmanTree(byte[] codeLengths)\r
  89                 {\r
  90                         BuildTree(codeLengths);\r
  91                 }\r
  92                 \r
  93                 private void BuildTree(byte[] codeLengths)\r
  94                 {\r
  95                         int[] blCount  = new int[MAX_BITLEN + 1];\r
  96                         int[] nextCode = new int[MAX_BITLEN + 1];\r
  97                         \r
  98                         for (int i = 0; i < codeLengths.Length; i++) {\r
  99                                 int bits = codeLengths[i];\r
 100                                 if (bits > 0) {\r
 101                                         blCount[bits]++;\r
 102                                 }\r
 103                         }\r
 104                         \r
 105                         int code = 0;\r
 106                         int treeSize = 512;\r
 107                         for (int bits = 1; bits <= MAX_BITLEN; bits++) {\r
 108                                 nextCode[bits] = code;\r
 109                                 code += blCount[bits] << (16 - bits);\r
 110                                 if (bits >= 10) {\r
 111                                         /* We need an extra table for bit lengths >= 10. */\r
 112                                         int start = nextCode[bits] & 0x1ff80;\r
 113                                         int end   = code & 0x1ff80;\r
 114                                         treeSize += (end - start) >> (16 - bits);\r
 115                                 }\r
 116                         }\r
 117 /* -jr comment this out! doesnt work for dynamic trees and pkzip 2.04g\r
 118                         if (code != 65536) \r
 119                         {\r
 120                                 throw new Exception("Code lengths don't add up properly.");\r
 121                         }\r
 122 */\r
 123                         /* Now create and fill the extra tables from longest to shortest\r
 124                         * bit len.  This way the sub trees will be aligned.\r
 125                         */\r
 126                         tree = new short[treeSize];\r
 127                         int treePtr = 512;\r
 128                         for (int bits = MAX_BITLEN; bits >= 10; bits--) {\r
 129                                 int end   = code & 0x1ff80;\r
 130                                 code -= blCount[bits] << (16 - bits);\r
 131                                 int start = code & 0x1ff80;\r
 132                                 for (int i = start; i < end; i += 1 << 7) {\r
 133                                         tree[DeflaterHuffman.BitReverse(i)] = (short) ((-treePtr << 4) | bits);\r
 134                                         treePtr += 1 << (bits-9);\r
 135                                 }\r
 136                         }\r
 137                         \r
 138                         for (int i = 0; i < codeLengths.Length; i++) {\r
 139                                 int bits = codeLengths[i];\r
 140                                 if (bits == 0) {\r
 141                                         continue;\r
 142                                 }\r
 143                                 code = nextCode[bits];\r
 144                                 int revcode = DeflaterHuffman.BitReverse(code);\r
 145                                 if (bits <= 9) {\r
 146                                         do {\r
 147                                                 tree[revcode] = (short) ((i << 4) | bits);\r
 148                                                 revcode += 1 << bits;\r
 149                                         } while (revcode < 512);\r
 150                                 } else {\r
 151                                         int subTree = tree[revcode & 511];\r
 152                                         int treeLen = 1 << (subTree & 15);\r
 153                                         subTree = -(subTree >> 4);\r
 154                                         do {\r
 155                                                 tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits);\r
 156                                                 revcode += 1 << bits;\r
 157                                         } while (revcode < treeLen);\r
 158                                 }\r
 159                                 nextCode[bits] = code + (1 << (16 - bits));\r
 160                         }\r
 161                         \r
 162                 }\r
 163                 \r
 164                 /// <summary>\r
 165                 /// Reads the next symbol from input.  The symbol is encoded using the\r
 166                 /// huffman tree.\r
 167                 /// </summary>\r
 168                 /// <param name="input">\r
 169                 /// input the input source.\r
 170                 /// </param>\r
 171                 /// <returns>\r
 172                 /// the next symbol, or -1 if not enough input is available.\r
 173                 /// </returns>\r
 174                 public int GetSymbol(StreamManipulator input)\r
 175                 {\r
 176                         int lookahead, symbol;\r
 177                         if ((lookahead = input.PeekBits(9)) >= 0) {\r
 178                                 if ((symbol = tree[lookahead]) >= 0) {\r
 179                                         input.DropBits(symbol & 15);\r
 180                                         return symbol >> 4;\r
 181                                 }\r
 182                                 int subtree = -(symbol >> 4);\r
 183                                 int bitlen = symbol & 15;\r
 184                                 if ((lookahead = input.PeekBits(bitlen)) >= 0) {\r
 185                                         symbol = tree[subtree | (lookahead >> 9)];\r
 186                                         input.DropBits(symbol & 15);\r
 187                                         return symbol >> 4;\r
 188                                 } else {\r
 189                                         int bits = input.AvailableBits;\r
 190                                         lookahead = input.PeekBits(bits);\r
 191                                         symbol = tree[subtree | (lookahead >> 9)];\r
 192                                         if ((symbol & 15) <= bits) {\r
 193                                                 input.DropBits(symbol & 15);\r
 194                                                 return symbol >> 4;\r
 195                                         } else {\r
 196                                                 return -1;\r
 197                                         }\r
 198                                 }\r
 199                         } else {\r
 200                                 int bits = input.AvailableBits;\r
 201                                 lookahead = input.PeekBits(bits);\r
 202                                 symbol = tree[lookahead];\r
 203                                 if (symbol >= 0 && (symbol & 15) <= bits) {\r
 204                                         input.DropBits(symbol & 15);\r
 205                                         return symbol >> 4;\r
 206                                 } else {\r
 207                                         return -1;\r
 208                                 }\r
 209                         }\r
 210                 }\r
 211         }\r
 212 }\r
 213 \r