← Back to branch summary

~ubuntu-branches/ubuntu/trusty/pdfmod/trusty

« back to all changes in this revision

Viewing changes to lib/PdfSharp/PdfSharp.SharpZipLib/Zip/Compression/InflaterHuffmanTree.cs

  • Committer: Bazaar Package Importer
  • Author(s): Chow Loong Jin
  • Date: 2010-06-18 03:44:46 UTC
  • Revision ID: james.westby@ubuntu.com-20100618034446-bogifrsscpayp361
Tags: upstream-0.8.3
Import upstream version 0.8.3

Show diffs side-by-side

added added

removed removed

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