Context Navigation

source: trunk/sources/HeuristicLab.ExtLibs/HeuristicLab.EPPlus/4.0.3/EPPlus-4.0.3/Packaging/DotNetZip/Zlib/Tree.cs @ 13401

Visit:

Last change on this file since 13401 was 12074, checked in by sraggl, 10 years ago
#2341: Added EPPlus-4.0.3 to ExtLibs
File size: 19.5 KB

Line
1	// Tree.cs
2	// ------------------------------------------------------------------
3	//
4	// Copyright (c) 2009 Dino Chiesa and Microsoft Corporation.
5	// All rights reserved.
6	//
7	// This code module is part of DotNetZip, a zipfile class library.
8	//
9	// ------------------------------------------------------------------
10	//
11	// This code is licensed under the Microsoft Public License.
12	// See the file License.txt for the license details.
13	// More info on: http://dotnetzip.codeplex.com
14	//
15	// ------------------------------------------------------------------
16	//
17	// last saved (in emacs):
18	// Time-stamp: <2009-October-28 13:29:50>
19	//
20	// ------------------------------------------------------------------
21	//
22	// This module defines classes for zlib compression and
23	// decompression. This code is derived from the jzlib implementation of
24	// zlib. In keeping with the license for jzlib, the copyright to that
25	// code is below.
26	//
27	// ------------------------------------------------------------------
28	//
29	// Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.
30	//
31	// Redistribution and use in source and binary forms, with or without
32	// modification, are permitted provided that the following conditions are met:
33	//
34	// 1. Redistributions of source code must retain the above copyright notice,
35	// this list of conditions and the following disclaimer.
36	//
37	// 2. Redistributions in binary form must reproduce the above copyright
38	// notice, this list of conditions and the following disclaimer in
39	// the documentation and/or other materials provided with the distribution.
40	//
41	// 3. The names of the authors may not be used to endorse or promote products
42	// derived from this software without specific prior written permission.
43	//
44	// THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
45	// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
46	// FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
47	// INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
48	// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
49	// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
50	// OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
51	// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
52	// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
53	// EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
54	//
55	// -----------------------------------------------------------------------
56	//
57	// This program is based on zlib-1.1.3; credit to authors
58	// Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
59	// and contributors of zlib.
60	//
61	// -----------------------------------------------------------------------
62
63
64	using System;
65
66	namespace OfficeOpenXml.Packaging.Ionic.Zlib
67	{
68	sealed class Tree
69	{
70	private static readonly int HEAP_SIZE = (2 * InternalConstants.L_CODES + 1);
71
72	// extra bits for each length code
73	internal static readonly int[] ExtraLengthBits = new int[]
74	{
75	0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
76	3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
77	};
78
79	// extra bits for each distance code
80	internal static readonly int[] ExtraDistanceBits = new int[]
81	{
82	0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
83	7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
84	};
85
86	// extra bits for each bit length code
87	internal static readonly int[] extra_blbits = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7};
88
89	internal static readonly sbyte[] bl_order = new sbyte[]{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
90
91
92	// The lengths of the bit length codes are sent in order of decreasing
93	// probability, to avoid transmitting the lengths for unused bit
94	// length codes.
95
96	internal const int Buf_size = 8 * 2;
97
98	// see definition of array dist_code below
99	//internal const int DIST_CODE_LEN = 512;
100
101	private static readonly sbyte[] _dist_code = new sbyte[]
102	{
103	0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
104	8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9,
105	10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
106	11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
107	12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
108	12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
109	13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
110	13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
111	14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
112	14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
113	14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
114	14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
115	15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
116	15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
117	15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
118	15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
119	0, 0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21,
120	22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
121	24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
122	25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
123	26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
124	26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
125	27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
126	27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
127	28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
128	28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
129	28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
130	28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
131	29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
132	29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
133	29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
134	29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29
135	};
136
137	internal static readonly sbyte[] LengthCode = new sbyte[]
138	{
139	0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11,
140	12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,
141	16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17,
142	18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19,
143	20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
144	21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
145	22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
146	23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
147	24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
148	24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
149	25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
150	25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
151	26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
152	26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
153	27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
154	27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28
155	};
156
157
158	internal static readonly int[] LengthBase = new int[]
159	{
160	0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28,
161	32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192, 224, 0
162	};
163
164
165	internal static readonly int[] DistanceBase = new int[]
166	{
167	0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192,
168	256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576
169	};
170
171
172	/// <summary>
173	/// Map from a distance to a distance code.
174	/// </summary>
175	/// <remarks>
176	/// No side effects. _dist_code[256] and _dist_code[257] are never used.
177	/// </remarks>
178	internal static int DistanceCode(int dist)
179	{
180	return (dist < 256)
181	? _dist_code[dist]
182	: _dist_code[256 + SharedUtils.URShift(dist, 7)];
183	}
184
185	internal short[] dyn_tree; // the dynamic tree
186	internal int max_code; // largest code with non zero frequency
187	internal StaticTree staticTree; // the corresponding static tree
188
189	// Compute the optimal bit lengths for a tree and update the total bit length
190	// for the current block.
191	// IN assertion: the fields freq and dad are set, heap[heap_max] and
192	// above are the tree nodes sorted by increasing frequency.
193	// OUT assertions: the field len is set to the optimal bit length, the
194	// array bl_count contains the frequencies for each bit length.
195	// The length opt_len is updated; static_len is also updated if stree is
196	// not null.
197	internal void gen_bitlen(DeflateManager s)
198	{
199	short[] tree = dyn_tree;
200	short[] stree = staticTree.treeCodes;
201	int[] extra = staticTree.extraBits;
202	int base_Renamed = staticTree.extraBase;
203	int max_length = staticTree.maxLength;
204	int h; // heap index
205	int n, m; // iterate over the tree elements
206	int bits; // bit length
207	int xbits; // extra bits
208	short f; // frequency
209	int overflow = 0; // number of elements with bit length too large
210
211	for (bits = 0; bits <= InternalConstants.MAX_BITS; bits++)
212	s.bl_count[bits] = 0;
213
214	// In a first pass, compute the optimal bit lengths (which may
215	// overflow in the case of the bit length tree).
216	tree[s.heap[s.heap_max] * 2 + 1] = 0; // root of the heap
217
218	for (h = s.heap_max + 1; h < HEAP_SIZE; h++)
219	{
220	n = s.heap[h];
221	bits = tree[tree[n * 2 + 1] * 2 + 1] + 1;
222	if (bits > max_length)
223	{
224	bits = max_length; overflow++;
225	}
226	tree[n * 2 + 1] = (short) bits;
227	// We overwrite tree[n*2+1] which is no longer needed
228
229	if (n > max_code)
230	continue; // not a leaf node
231
232	s.bl_count[bits]++;
233	xbits = 0;
234	if (n >= base_Renamed)
235	xbits = extra[n - base_Renamed];
236	f = tree[n * 2];
237	s.opt_len += f * (bits + xbits);
238	if (stree != null)
239	s.static_len += f * (stree[n * 2 + 1] + xbits);
240	}
241	if (overflow == 0)
242	return ;
243
244	// This happens for example on obj2 and pic of the Calgary corpus
245	// Find the first bit length which could increase:
246	do
247	{
248	bits = max_length - 1;
249	while (s.bl_count[bits] == 0)
250	bits--;
251	s.bl_count[bits]--; // move one leaf down the tree
252	s.bl_count[bits + 1] = (short) (s.bl_count[bits + 1] + 2); // move one overflow item as its brother
253	s.bl_count[max_length]--;
254	// The brother of the overflow item also moves one step up,
255	// but this does not affect bl_count[max_length]
256	overflow -= 2;
257	}
258	while (overflow > 0);
259
260	for (bits = max_length; bits != 0; bits--)
261	{
262	n = s.bl_count[bits];
263	while (n != 0)
264	{
265	m = s.heap[--h];
266	if (m > max_code)
267	continue;
268	if (tree[m * 2 + 1] != bits)
269	{
270	s.opt_len = (int) (s.opt_len + ((long) bits - (long) tree[m * 2 + 1]) * (long) tree[m * 2]);
271	tree[m * 2 + 1] = (short) bits;
272	}
273	n--;
274	}
275	}
276	}
277
278	// Construct one Huffman tree and assigns the code bit strings and lengths.
279	// Update the total bit length for the current block.
280	// IN assertion: the field freq is set for all tree elements.
281	// OUT assertions: the fields len and code are set to the optimal bit length
282	// and corresponding code. The length opt_len is updated; static_len is
283	// also updated if stree is not null. The field max_code is set.
284	internal void build_tree(DeflateManager s)
285	{
286	short[] tree = dyn_tree;
287	short[] stree = staticTree.treeCodes;
288	int elems = staticTree.elems;
289	int n, m; // iterate over heap elements
290	int max_code = -1; // largest code with non zero frequency
291	int node; // new node being created
292
293	// Construct the initial heap, with least frequent element in
294	// heap[1]. The sons of heap[n] are heap[2n] and heap[2n+1].
295	// heap[0] is not used.
296	s.heap_len = 0;
297	s.heap_max = HEAP_SIZE;
298
299	for (n = 0; n < elems; n++)
300	{
301	if (tree[n * 2] != 0)
302	{
303	s.heap[++s.heap_len] = max_code = n;
304	s.depth[n] = 0;
305	}
306	else
307	{
308	tree[n * 2 + 1] = 0;
309	}
310	}
311
312	// The pkzip format requires that at least one distance code exists,
313	// and that at least one bit should be sent even if there is only one
314	// possible code. So to avoid special checks later on we force at least
315	// two codes of non zero frequency.
316	while (s.heap_len < 2)
317	{
318	node = s.heap[++s.heap_len] = (max_code < 2?++max_code:0);
319	tree[node * 2] = 1;
320	s.depth[node] = 0;
321	s.opt_len--;
322	if (stree != null)
323	s.static_len -= stree[node * 2 + 1];
324	// node is 0 or 1 so it does not have extra bits
325	}
326	this.max_code = max_code;
327
328	// The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
329	// establish sub-heaps of increasing lengths:
330
331	for (n = s.heap_len / 2; n >= 1; n--)
332	s.pqdownheap(tree, n);
333
334	// Construct the Huffman tree by repeatedly combining the least two
335	// frequent nodes.
336
337	node = elems; // next internal node of the tree
338	do
339	{
340	// n = node of least frequency
341	n = s.heap[1];
342	s.heap[1] = s.heap[s.heap_len--];
343	s.pqdownheap(tree, 1);
344	m = s.heap[1]; // m = node of next least frequency
345
346	s.heap[--s.heap_max] = n; // keep the nodes sorted by frequency
347	s.heap[--s.heap_max] = m;
348
349	// Create a new node father of n and m
350	tree[node * 2] = unchecked((short) (tree[n * 2] + tree[m * 2]));
351	s.depth[node] = (sbyte) (System.Math.Max((byte) s.depth[n], (byte) s.depth[m]) + 1);
352	tree[n * 2 + 1] = tree[m * 2 + 1] = (short) node;
353
354	// and insert the new node in the heap
355	s.heap[1] = node++;
356	s.pqdownheap(tree, 1);
357	}
358	while (s.heap_len >= 2);
359
360	s.heap[--s.heap_max] = s.heap[1];
361
362	// At this point, the fields freq and dad are set. We can now
363	// generate the bit lengths.
364
365	gen_bitlen(s);
366
367	// The field len is now set, we can generate the bit codes
368	gen_codes(tree, max_code, s.bl_count);
369	}
370
371	// Generate the codes for a given tree and bit counts (which need not be
372	// optimal).
373	// IN assertion: the array bl_count contains the bit length statistics for
374	// the given tree and the field len is set for all tree elements.
375	// OUT assertion: the field code is set for all tree elements of non
376	// zero code length.
377	internal static void gen_codes(short[] tree, int max_code, short[] bl_count)
378	{
379	short[] next_code = new short[InternalConstants.MAX_BITS + 1]; // next code value for each bit length
380	short code = 0; // running code value
381	int bits; // bit index
382	int n; // code index
383
384	// The distribution counts are first used to generate the code values
385	// without bit reversal.
386	for (bits = 1; bits <= InternalConstants.MAX_BITS; bits++)
387	unchecked {
388	next_code[bits] = code = (short) ((code + bl_count[bits - 1]) << 1);
389	}
390
391	// Check that the bit counts in bl_count are consistent. The last code
392	// must be all ones.
393	//Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
394	// "inconsistent bit counts");
395	//Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
396
397	for (n = 0; n <= max_code; n++)
398	{
399	int len = tree[n * 2 + 1];
400	if (len == 0)
401	continue;
402	// Now reverse the bits
403	tree[n * 2] = unchecked((short) (bi_reverse(next_code[len]++, len)));
404	}
405	}
406
407	// Reverse the first len bits of a code, using straightforward code (a faster
408	// method would use a table)
409	// IN assertion: 1 <= len <= 15
410	internal static int bi_reverse(int code, int len)
411	{
412	int res = 0;
413	do
414	{
415	res \|= code & 1;
416	code >>= 1; //SharedUtils.URShift(code, 1);
417	res <<= 1;
418	}
419	while (--len > 0);
420	return res >> 1;
421	}
422	}
423	}

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Update cookies preferences