Nawigacja

DeflaterHuffman.cs @ 876

Odwiedź:

Wersja 597, 25.2 KB (wprowadzona przez marek, 17 years temu)
re #165

Line
1	// DeflaterHuffman.cs
2	//
3	// Copyright (C) 2001 Mike Krueger
4	// Copyright (C) 2004 John Reilly
5	//
6	// This file was translated from java, it was part of the GNU Classpath
7	// Copyright (C) 2001 Free Software Foundation, Inc.
8	//
9	// This program is free software; you can redistribute it and/or
10	// modify it under the terms of the GNU General Public License
11	// as published by the Free Software Foundation; either version 2
12	// of the License, or (at your option) any later version.
13	//
14	// This program is distributed in the hope that it will be useful,
15	// but WITHOUT ANY WARRANTY; without even the implied warranty of
16	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17	// GNU General Public License for more details.
18	//
19	// You should have received a copy of the GNU General Public License
20	// along with this program; if not, write to the Free Software
21	// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
22	//
23	// Linking this library statically or dynamically with other modules is
24	// making a combined work based on this library. Thus, the terms and
25	// conditions of the GNU General Public License cover the whole
26	// combination.
27	//
28	// As a special exception, the copyright holders of this library give you
29	// permission to link this library with independent modules to produce an
30	// executable, regardless of the license terms of these independent
31	// modules, and to copy and distribute the resulting executable under
32	// terms of your choice, provided that you also meet, for each linked
33	// independent module, the terms and conditions of the license of that
34	// module. An independent module is a module which is not derived from
35	// or based on this library. If you modify this library, you may extend
36	// this exception to your version of the library, but you are not
37	// obligated to do so. If you do not wish to do so, delete this
38	// exception statement from your version.
39
40	using System;
41
42	namespace ICSharpCode.SharpZipLib.Zip.Compression
43	{
44
45	/// <summary>
46	/// This is the DeflaterHuffman class.
47	///
48	/// This class is <i>not</i> thread safe. This is inherent in the API, due
49	/// to the split of Deflate and SetInput.
50	///
51	/// author of the original java version : Jochen Hoenicke
52	/// </summary>
53	public class DeflaterHuffman
54	{
55	const int BUFSIZE = 1 << (DeflaterConstants.DEFAULT_MEM_LEVEL + 6);
56	const int LITERAL_NUM = 286;
57
58	// Number of distance codes
59	const int DIST_NUM = 30;
60	// Number of codes used to transfer bit lengths
61	const int BITLEN_NUM = 19;
62
63	// repeat previous bit length 3-6 times (2 bits of repeat count)
64	const int REP_3_6 = 16;
65	// repeat a zero length 3-10 times (3 bits of repeat count)
66	const int REP_3_10 = 17;
67	// repeat a zero length 11-138 times (7 bits of repeat count)
68	const int REP_11_138 = 18;
69
70	const int EOF_SYMBOL = 256;
71
72	// The lengths of the bit length codes are sent in order of decreasing
73	// probability, to avoid transmitting the lengths for unused bit length codes.
74	static readonly int[] BL_ORDER = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
75
76	static readonly byte[] bit4Reverse = {
77	0,
78	8,
79	4,
80	12,
81	2,
82	10,
83	6,
84	14,
85	1,
86	9,
87	5,
88	13,
89	3,
90	11,
91	7,
92	15
93	};
94
95	static short[] staticLCodes;
96	static byte[] staticLLength;
97	static short[] staticDCodes;
98	static byte[] staticDLength;
99
100	class Tree
101	{
102	#region Instance Fields
103	public short[] freqs;
104
105	public byte[] length;
106
107	public int minNumCodes;
108
109	public int numCodes;
110
111	short[] codes;
112	int[] bl_counts;
113	int maxLength;
114	DeflaterHuffman dh;
115	#endregion
116
117	#region Constructors
118	public Tree(DeflaterHuffman dh, int elems, int minCodes, int maxLength)
119	{
120	this.dh = dh;
121	this.minNumCodes = minCodes;
122	this.maxLength = maxLength;
123	freqs = new short[elems];
124	bl_counts = new int[maxLength];
125	}
126
127	#endregion
128
129	/// <summary>
130	/// Resets the internal state of the tree
131	/// </summary>
132	public void Reset()
133	{
134	for (int i = 0; i < freqs.Length; i++) {
135	freqs[i] = 0;
136	}
137	codes = null;
138	length = null;
139	}
140
141	public void WriteSymbol(int code)
142	{
143	// if (DeflaterConstants.DEBUGGING) {
144	// freqs[code]--;
145	// // Console.Write("writeSymbol("+freqs.length+","+code+"): ");
146	// }
147	dh.pending.WriteBits(codes[code] & 0xffff, length[code]);
148	}
149
150	/// <summary>
151	/// Check that all frequencies are zero
152	/// </summary>
153	/// <exception cref="SharpZipBaseException">
154	/// At least one frequency is non-zero
155	/// </exception>
156	public void CheckEmpty()
157	{
158	bool empty = true;
159	for (int i = 0; i < freqs.Length; i++) {
160	if (freqs[i] != 0) {
161	//Console.WriteLine("freqs[" + i + "] == " + freqs[i]);
162	empty = false;
163	}
164	}
165
166	if (!empty) {
167	throw new SharpZipBaseException("!Empty");
168	}
169	}
170
171	/// <summary>
172	/// Set static codes and length
173	/// </summary>
174	/// <param name="staticCodes">new codes</param>
175	/// <param name="staticLengths">length for new codes</param>
176	public void SetStaticCodes(short[] staticCodes, byte[] staticLengths)
177	{
178	codes = staticCodes;
179	length = staticLengths;
180	}
181
182	/// <summary>
183	/// Build dynamic codes and lengths
184	/// </summary>
185	public void BuildCodes()
186	{
187	int numSymbols = freqs.Length;
188	int[] nextCode = new int[maxLength];
189	int code = 0;
190
191	codes = new short[freqs.Length];
192
193	// if (DeflaterConstants.DEBUGGING) {
194	// //Console.WriteLine("buildCodes: "+freqs.Length);
195	// }
196
197	for (int bits = 0; bits < maxLength; bits++) {
198	nextCode[bits] = code;
199	code += bl_counts[bits] << (15 - bits);
200
201	// if (DeflaterConstants.DEBUGGING) {
202	// //Console.WriteLine("bits: " + ( bits + 1) + " count: " + bl_counts[bits]
203	// +" nextCode: "+code);
204	// }
205	}
206
207	#if DebugDeflation
208	if ( DeflaterConstants.DEBUGGING && (code != 65536) )
209	{
210	throw new SharpZipBaseException("Inconsistent bl_counts!");
211	}
212	#endif
213	for (int i=0; i < numCodes; i++) {
214	int bits = length[i];
215	if (bits > 0) {
216
217	// if (DeflaterConstants.DEBUGGING) {
218	// //Console.WriteLine("codes["+i+"] = rev(" + nextCode[bits-1]+"),
219	// +bits);
220	// }
221
222	codes[i] = BitReverse(nextCode[bits-1]);
223	nextCode[bits-1] += 1 << (16 - bits);
224	}
225	}
226	}
227
228	public void BuildTree()
229	{
230	int numSymbols = freqs.Length;
231
232	/* heap is a priority queue, sorted by frequency, least frequent
233	* nodes first. The heap is a binary tree, with the property, that
234	* the parent node is smaller than both child nodes. This assures
235	* that the smallest node is the first parent.
236	*
237	* The binary tree is encoded in an array: 0 is root node and
238	* the nodes 2n+1, 2n+2 are the child nodes of node n.
239	*/
240	int[] heap = new int[numSymbols];
241	int heapLen = 0;
242	int maxCode = 0;
243	for (int n = 0; n < numSymbols; n++) {
244	int freq = freqs[n];
245	if (freq != 0) {
246	// Insert n into heap
247	int pos = heapLen++;
248	int ppos;
249	while (pos > 0 && freqs[heap[ppos = (pos - 1) / 2]] > freq) {
250	heap[pos] = heap[ppos];
251	pos = ppos;
252	}
253	heap[pos] = n;
254
255	maxCode = n;
256	}
257	}
258
259	/* We could encode a single literal with 0 bits but then we
260	* don't see the literals. Therefore we force at least two
261	* literals to avoid this case. We don't care about order in
262	* this case, both literals get a 1 bit code.
263	*/
264	while (heapLen < 2) {
265	int node = maxCode < 2 ? ++maxCode : 0;
266	heap[heapLen++] = node;
267	}
268
269	numCodes = Math.Max(maxCode + 1, minNumCodes);
270
271	int numLeafs = heapLen;
272	int[] childs = new int[4 * heapLen - 2];
273	int[] values = new int[2 * heapLen - 1];
274	int numNodes = numLeafs;
275	for (int i = 0; i < heapLen; i++) {
276	int node = heap[i];
277	childs[2 * i] = node;
278	childs[2 * i + 1] = -1;
279	values[i] = freqs[node] << 8;
280	heap[i] = i;
281	}
282
283	/* Construct the Huffman tree by repeatedly combining the least two
284	* frequent nodes.
285	*/
286	do {
287	int first = heap[0];
288	int last = heap[--heapLen];
289
290	// Propagate the hole to the leafs of the heap
291	int ppos = 0;
292	int path = 1;
293
294	while (path < heapLen) {
295	if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
296	path++;
297	}
298
299	heap[ppos] = heap[path];
300	ppos = path;
301	path = path * 2 + 1;
302	}
303
304	/* Now propagate the last element down along path. Normally
305	* it shouldn't go too deep.
306	*/
307	int lastVal = values[last];
308	while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
309	heap[path] = heap[ppos];
310	}
311	heap[path] = last;
312
313
314	int second = heap[0];
315
316	// Create a new node father of first and second
317	last = numNodes++;
318	childs[2 * last] = first;
319	childs[2 * last + 1] = second;
320	int mindepth = Math.Min(values[first] & 0xff, values[second] & 0xff);
321	values[last] = lastVal = values[first] + values[second] - mindepth + 1;
322
323	// Again, propagate the hole to the leafs
324	ppos = 0;
325	path = 1;
326
327	while (path < heapLen) {
328	if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
329	path++;
330	}
331
332	heap[ppos] = heap[path];
333	ppos = path;
334	path = ppos * 2 + 1;
335	}
336
337	// Now propagate the new element down along path
338	while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
339	heap[path] = heap[ppos];
340	}
341	heap[path] = last;
342	} while (heapLen > 1);
343
344	if (heap[0] != childs.Length / 2 - 1) {
345	throw new SharpZipBaseException("Heap invariant violated");
346	}
347
348	BuildLength(childs);
349	}
350
351	/// <summary>
352	/// Get encoded length
353	/// </summary>
354	/// <returns>Encoded length, the sum of frequencies * lengths</returns>
355	public int GetEncodedLength()
356	{
357	int len = 0;
358	for (int i = 0; i < freqs.Length; i++) {
359	len += freqs[i] * length[i];
360	}
361	return len;
362	}
363
364	/// <summary>
365	/// Scan a literal or distance tree to determine the frequencies of the codes
366	/// in the bit length tree.
367	/// </summary>
368	public void CalcBLFreq(Tree blTree)
369	{
370	int max_count; /* max repeat count */
371	int min_count; /* min repeat count */
372	int count; /* repeat count of the current code */
373	int curlen = -1; /* length of current code */
374
375	int i = 0;
376	while (i < numCodes) {
377	count = 1;
378	int nextlen = length[i];
379	if (nextlen == 0) {
380	max_count = 138;
381	min_count = 3;
382	} else {
383	max_count = 6;
384	min_count = 3;
385	if (curlen != nextlen) {
386	blTree.freqs[nextlen]++;
387	count = 0;
388	}
389	}
390	curlen = nextlen;
391	i++;
392
393	while (i < numCodes && curlen == length[i]) {
394	i++;
395	if (++count >= max_count) {
396	break;
397	}
398	}
399
400	if (count < min_count) {
401	blTree.freqs[curlen] += (short)count;
402	} else if (curlen != 0) {
403	blTree.freqs[REP_3_6]++;
404	} else if (count <= 10) {
405	blTree.freqs[REP_3_10]++;
406	} else {
407	blTree.freqs[REP_11_138]++;
408	}
409	}
410	}
411
412	/// <summary>
413	/// Write tree values
414	/// </summary>
415	/// <param name="blTree">Tree to write</param>
416	public void WriteTree(Tree blTree)
417	{
418	int max_count; // max repeat count
419	int min_count; // min repeat count
420	int count; // repeat count of the current code
421	int curlen = -1; // length of current code
422
423	int i = 0;
424	while (i < numCodes) {
425	count = 1;
426	int nextlen = length[i];
427	if (nextlen == 0) {
428	max_count = 138;
429	min_count = 3;
430	} else {
431	max_count = 6;
432	min_count = 3;
433	if (curlen != nextlen) {
434	blTree.WriteSymbol(nextlen);
435	count = 0;
436	}
437	}
438	curlen = nextlen;
439	i++;
440
441	while (i < numCodes && curlen == length[i]) {
442	i++;
443	if (++count >= max_count) {
444	break;
445	}
446	}
447
448	if (count < min_count) {
449	while (count-- > 0) {
450	blTree.WriteSymbol(curlen);
451	}
452	} else if (curlen != 0) {
453	blTree.WriteSymbol(REP_3_6);
454	dh.pending.WriteBits(count - 3, 2);
455	} else if (count <= 10) {
456	blTree.WriteSymbol(REP_3_10);
457	dh.pending.WriteBits(count - 3, 3);
458	} else {
459	blTree.WriteSymbol(REP_11_138);
460	dh.pending.WriteBits(count - 11, 7);
461	}
462	}
463	}
464
465	void BuildLength(int[] childs)
466	{
467	this.length = new byte [freqs.Length];
468	int numNodes = childs.Length / 2;
469	int numLeafs = (numNodes + 1) / 2;
470	int overflow = 0;
471
472	for (int i = 0; i < maxLength; i++) {
473	bl_counts[i] = 0;
474	}
475
476	// First calculate optimal bit lengths
477	int[] lengths = new int[numNodes];
478	lengths[numNodes-1] = 0;
479
480	for (int i = numNodes - 1; i >= 0; i--) {
481	if (childs[2 * i + 1] != -1) {
482	int bitLength = lengths[i] + 1;
483	if (bitLength > maxLength) {
484	bitLength = maxLength;
485	overflow++;
486	}
487	lengths[childs[2 * i]] = lengths[childs[2 * i + 1]] = bitLength;
488	} else {
489	// A leaf node
490	int bitLength = lengths[i];
491	bl_counts[bitLength - 1]++;
492	this.length[childs[2*i]] = (byte) lengths[i];
493	}
494	}
495
496	// if (DeflaterConstants.DEBUGGING) {
497	// //Console.WriteLine("Tree "+freqs.Length+" lengths:");
498	// for (int i=0; i < numLeafs; i++) {
499	// //Console.WriteLine("Node "+childs[2i]+" freq: "+freqs[childs[2i]]
500	// + " len: "+length[childs[2*i]]);
501	// }
502	// }
503
504	if (overflow == 0) {
505	return;
506	}
507
508	int incrBitLen = maxLength - 1;
509	do {
510	// Find the first bit length which could increase:
511	while (bl_counts[--incrBitLen] == 0)
512	;
513
514	// Move this node one down and remove a corresponding
515	// number of overflow nodes.
516	do {
517	bl_counts[incrBitLen]--;
518	bl_counts[++incrBitLen]++;
519	overflow -= 1 << (maxLength - 1 - incrBitLen);
520	} while (overflow > 0 && incrBitLen < maxLength - 1);
521	} while (overflow > 0);
522
523	/* We may have overshot above. Move some nodes from maxLength to
524	* maxLength-1 in that case.
525	*/
526	bl_counts[maxLength-1] += overflow;
527	bl_counts[maxLength-2] -= overflow;
528
529	/* Now recompute all bit lengths, scanning in increasing
530	* frequency. It is simpler to reconstruct all lengths instead of
531	* fixing only the wrong ones. This idea is taken from 'ar'
532	* written by Haruhiko Okumura.
533	*
534	* The nodes were inserted with decreasing frequency into the childs
535	* array.
536	*/
537	int nodePtr = 2 * numLeafs;
538	for (int bits = maxLength; bits != 0; bits--) {
539	int n = bl_counts[bits-1];
540	while (n > 0) {
541	int childPtr = 2*childs[nodePtr++];
542	if (childs[childPtr + 1] == -1) {
543	// We found another leaf
544	length[childs[childPtr]] = (byte) bits;
545	n--;
546	}
547	}
548	}
549	// if (DeflaterConstants.DEBUGGING) {
550	// //Console.WriteLine("* After overflow elimination. *");
551	// for (int i=0; i < numLeafs; i++) {
552	// //Console.WriteLine("Node "+childs[2i]+" freq: "+freqs[childs[2i]]
553	// + " len: "+length[childs[2*i]]);
554	// }
555	// }
556	}
557
558	}
559
560	#region Instance Fields
561	/// <summary>
562	/// Pending buffer to use
563	/// </summary>
564	public DeflaterPending pending;
565
566	Tree literalTree;
567	Tree distTree;
568	Tree blTree;
569
570	// Buffer for distances
571	short[] d_buf;
572	byte[] l_buf;
573	int last_lit;
574	int extra_bits;
575	#endregion
576
577	static DeflaterHuffman()
578	{
579	// See RFC 1951 3.2.6
580	// Literal codes
581	staticLCodes = new short[LITERAL_NUM];
582	staticLLength = new byte[LITERAL_NUM];
583
584	int i = 0;
585	while (i < 144) {
586	staticLCodes[i] = BitReverse((0x030 + i) << 8);
587	staticLLength[i++] = 8;
588	}
589
590	while (i < 256) {
591	staticLCodes[i] = BitReverse((0x190 - 144 + i) << 7);
592	staticLLength[i++] = 9;
593	}
594
595	while (i < 280) {
596	staticLCodes[i] = BitReverse((0x000 - 256 + i) << 9);
597	staticLLength[i++] = 7;
598	}
599
600	while (i < LITERAL_NUM) {
601	staticLCodes[i] = BitReverse((0x0c0 - 280 + i) << 8);
602	staticLLength[i++] = 8;
603	}
604
605	// Distance codes
606	staticDCodes = new short[DIST_NUM];
607	staticDLength = new byte[DIST_NUM];
608	for (i = 0; i < DIST_NUM; i++) {
609	staticDCodes[i] = BitReverse(i << 11);
610	staticDLength[i] = 5;
611	}
612	}
613
614	/// <summary>
615	/// Construct instance with pending buffer
616	/// </summary>
617	/// <param name="pending">Pending buffer to use</param>
618	public DeflaterHuffman(DeflaterPending pending)
619	{
620	this.pending = pending;
621
622	literalTree = new Tree(this, LITERAL_NUM, 257, 15);
623	distTree = new Tree(this, DIST_NUM, 1, 15);
624	blTree = new Tree(this, BITLEN_NUM, 4, 7);
625
626	d_buf = new short[BUFSIZE];
627	l_buf = new byte [BUFSIZE];
628	}
629
630	/// <summary>
631	/// Reset internal state
632	/// </summary>
633	public void Reset()
634	{
635	last_lit = 0;
636	extra_bits = 0;
637	literalTree.Reset();
638	distTree.Reset();
639	blTree.Reset();
640	}
641
642	/// <summary>
643	/// Write all trees to pending buffer
644	/// </summary>
645	/// <param name="blTreeCodes">The number/rank of treecodes to send.</param>
646	public void SendAllTrees(int blTreeCodes)
647	{
648	blTree.BuildCodes();
649	literalTree.BuildCodes();
650	distTree.BuildCodes();
651	pending.WriteBits(literalTree.numCodes - 257, 5);
652	pending.WriteBits(distTree.numCodes - 1, 5);
653	pending.WriteBits(blTreeCodes - 4, 4);
654	for (int rank = 0; rank < blTreeCodes; rank++) {
655	pending.WriteBits(blTree.length[BL_ORDER[rank]], 3);
656	}
657	literalTree.WriteTree(blTree);
658	distTree.WriteTree(blTree);
659
660	#if DebugDeflation
661	if (DeflaterConstants.DEBUGGING) {
662	blTree.CheckEmpty();
663	}
664	#endif
665	}
666
667	/// <summary>
668	/// Compress current buffer writing data to pending buffer
669	/// </summary>
670	public void CompressBlock()
671	{
672	for (int i = 0; i < last_lit; i++) {
673	int litlen = l_buf[i] & 0xff;
674	int dist = d_buf[i];
675	if (dist-- != 0) {
676	// if (DeflaterConstants.DEBUGGING) {
677	// Console.Write("["+(dist+1)+","+(litlen+3)+"]: ");
678	// }
679
680	int lc = Lcode(litlen);
681	literalTree.WriteSymbol(lc);
682
683	int bits = (lc - 261) / 4;
684	if (bits > 0 && bits <= 5) {
685	pending.WriteBits(litlen & ((1 << bits) - 1), bits);
686	}
687
688	int dc = Dcode(dist);
689	distTree.WriteSymbol(dc);
690
691	bits = dc / 2 - 1;
692	if (bits > 0) {
693	pending.WriteBits(dist & ((1 << bits) - 1), bits);
694	}
695	} else {
696	// if (DeflaterConstants.DEBUGGING) {
697	// if (litlen > 32 && litlen < 127) {
698	// Console.Write("("+(char)litlen+"): ");
699	// } else {
700	// Console.Write("{"+litlen+"}: ");
701	// }
702	// }
703	literalTree.WriteSymbol(litlen);
704	}
705	}
706
707	#if DebugDeflation
708	if (DeflaterConstants.DEBUGGING) {
709	Console.Write("EOF: ");
710	}
711	#endif
712	literalTree.WriteSymbol(EOF_SYMBOL);
713
714	#if DebugDeflation
715	if (DeflaterConstants.DEBUGGING) {
716	literalTree.CheckEmpty();
717	distTree.CheckEmpty();
718	}
719	#endif
720	}
721
722	/// <summary>
723	/// Flush block to output with no compression
724	/// </summary>
725	/// <param name="stored">Data to write</param>
726	/// <param name="storedOffset">Index of first byte to write</param>
727	/// <param name="storedLength">Count of bytes to write</param>
728	/// <param name="lastBlock">True if this is the last block</param>
729	public void FlushStoredBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock)
730	{
731	#if DebugDeflation
732	// if (DeflaterConstants.DEBUGGING) {
733	// //Console.WriteLine("Flushing stored block "+ storedLength);
734	// }
735	#endif
736	pending.WriteBits((DeflaterConstants.STORED_BLOCK << 1) + (lastBlock ? 1 : 0), 3);
737	pending.AlignToByte();
738	pending.WriteShort(storedLength);
739	pending.WriteShort(~storedLength);
740	pending.WriteBlock(stored, storedOffset, storedLength);
741	Reset();
742	}
743
744	/// <summary>
745	/// Flush block to output with compression
746	/// </summary>
747	/// <param name="stored">Data to flush</param>
748	/// <param name="storedOffset">Index of first byte to flush</param>
749	/// <param name="storedLength">Count of bytes to flush</param>
750	/// <param name="lastBlock">True if this is the last block</param>
751	public void FlushBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock)
752	{
753	literalTree.freqs[EOF_SYMBOL]++;
754
755	// Build trees
756	literalTree.BuildTree();
757	distTree.BuildTree();
758
759	// Calculate bitlen frequency
760	literalTree.CalcBLFreq(blTree);
761	distTree.CalcBLFreq(blTree);
762
763	// Build bitlen tree
764	blTree.BuildTree();
765
766	int blTreeCodes = 4;
767	for (int i = 18; i > blTreeCodes; i--) {
768	if (blTree.length[BL_ORDER[i]] > 0) {
769	blTreeCodes = i+1;
770	}
771	}
772	int opt_len = 14 + blTreeCodes * 3 + blTree.GetEncodedLength() +
773	literalTree.GetEncodedLength() + distTree.GetEncodedLength() +
774	extra_bits;
775
776	int static_len = extra_bits;
777	for (int i = 0; i < LITERAL_NUM; i++) {
778	static_len += literalTree.freqs[i] * staticLLength[i];
779	}
780	for (int i = 0; i < DIST_NUM; i++) {
781	static_len += distTree.freqs[i] * staticDLength[i];
782	}
783	if (opt_len >= static_len) {
784	// Force static trees
785	opt_len = static_len;
786	}
787
788	if (storedOffset >= 0 && storedLength + 4 < opt_len >> 3) {
789	// Store Block
790
791	// if (DeflaterConstants.DEBUGGING) {
792	// //Console.WriteLine("Storing, since " + storedLength + " < " + opt_len
793	// + " <= " + static_len);
794	// }
795	FlushStoredBlock(stored, storedOffset, storedLength, lastBlock);
796	} else if (opt_len == static_len) {
797	// Encode with static tree
798	pending.WriteBits((DeflaterConstants.STATIC_TREES << 1) + (lastBlock ? 1 : 0), 3);
799	literalTree.SetStaticCodes(staticLCodes, staticLLength);
800	distTree.SetStaticCodes(staticDCodes, staticDLength);
801	CompressBlock();
802	Reset();
803	} else {
804	// Encode with dynamic tree
805	pending.WriteBits((DeflaterConstants.DYN_TREES << 1) + (lastBlock ? 1 : 0), 3);
806	SendAllTrees(blTreeCodes);
807	CompressBlock();
808	Reset();
809	}
810	}
811
812	/// <summary>
813	/// Get value indicating if internal buffer is full
814	/// </summary>
815	/// <returns>true if buffer is full</returns>
816	public bool IsFull()
817	{
818	return last_lit >= BUFSIZE;
819	}
820
821	/// <summary>
822	/// Add literal to buffer
823	/// </summary>
824	/// <param name="literal">Literal value to add to buffer.</param>
825	/// <returns>Value indicating internal buffer is full</returns>
826	public bool TallyLit(int literal)
827	{
828	// if (DeflaterConstants.DEBUGGING) {
829	// if (lit > 32 && lit < 127) {
830	// //Console.WriteLine("("+(char)lit+")");
831	// } else {
832	// //Console.WriteLine("{"+lit+"}");
833	// }
834	// }
835	d_buf[last_lit] = 0;
836	l_buf[last_lit++] = (byte)literal;
837	literalTree.freqs[literal]++;
838	return IsFull();
839	}
840
841	/// <summary>
842	/// Add distance code and length to literal and distance trees
843	/// </summary>
844	/// <param name="distance">Distance code</param>
845	/// <param name="length">Length</param>
846	/// <returns>Value indicating if internal buffer is full</returns>
847	public bool TallyDist(int distance, int length)
848	{
849	// if (DeflaterConstants.DEBUGGING) {
850	// //Console.WriteLine("[" + distance + "," + length + "]");
851	// }
852
853	d_buf[last_lit] = (short)distance;
854	l_buf[last_lit++] = (byte)(length - 3);
855
856	int lc = Lcode(length - 3);
857	literalTree.freqs[lc]++;
858	if (lc >= 265 && lc < 285) {
859	extra_bits += (lc - 261) / 4;
860	}
861
862	int dc = Dcode(distance - 1);
863	distTree.freqs[dc]++;
864	if (dc >= 4) {
865	extra_bits += dc / 2 - 1;
866	}
867	return IsFull();
868	}
869
870
871	/// <summary>
872	/// Reverse the bits of a 16 bit value.
873	/// </summary>
874	/// <param name="toReverse">Value to reverse bits</param>
875	/// <returns>Value with bits reversed</returns>
876	public static short BitReverse(int toReverse)
877	{
878	return (short) (bit4Reverse[toReverse & 0xF] << 12 \|
879	bit4Reverse[(toReverse >> 4) & 0xF] << 8 \|
880	bit4Reverse[(toReverse >> 8) & 0xF] << 4 \|
881	bit4Reverse[toReverse >> 12]);
882	}
883
884	static int Lcode(int length)
885	{
886	if (length == 255) {
887	return 285;
888	}
889
890	int code = 257;
891	while (length >= 8) {
892	code += 4;
893	length >>= 1;
894	}
895	return code + length;
896	}
897
898	static int Dcode(int distance)
899	{
900	int code = 0;
901	while (distance >= 4) {
902	code += 2;
903	distance >>= 1;
904	}
905	return code + distance;
906	}
907	}
908	}

Notatka: Zobacz TracBrowser aby uzyskać więcej informacji.

Nawigacja

root/branches/Abonament/BazaReklam.Updater/ICSharpCode.SharpZipLib/Zip/Compression/DeflaterHuffman.cs @ 876

Pobierz w innym formacie: