deflaterhuffman.cs

P2P (peer to peer) file sharing program in C#. Supports Gnutella, Gnutella2, eDonkey, and OpenNap. w

			///
		public void CalcBLFreq(Tree blTree) 
			{
				int max_count;               /* max repeat count */
				int min_count;               /* min repeat count */
				int count;                   /* repeat count of the current code */
				int curlen = -1;             /* length of current code */
				
				int i = 0;
				while (i < numCodes) 
				{
					count = 1;
					int nextlen = length[i];
					if (nextlen == 0) 
					{
						max_count = 138;
						min_count = 3;
					} 
					else 
					{
						max_count = 6;
						min_count = 3;
						if (curlen != nextlen) 
						{
							blTree.freqs[nextlen]++;
							count = 0;
						}
					}
					curlen = nextlen;
					i++;
					
					while (i < numCodes && curlen == length[i]) 
					{
						i++;
						if (++count >= max_count) 
						{
							break;
						}
					}
					
					if (count < min_count) 
					{
						blTree.freqs[curlen] += (short)count;
					} 
					else if (curlen != 0) 
					{
						blTree.freqs[REP_3_6]++;
					} 
					else if (count <= 10) 
					{
						blTree.freqs[REP_3_10]++;
					} 
					else 
					{
						blTree.freqs[REP_11_138]++;
					}
				}
			}
			
			///
		public void WriteTree(Tree blTree)
			{
				int max_count;               /* max repeat count */
				int min_count;               /* min repeat count */
				int count;                   /* repeat count of the current code */
				int curlen = -1;             /* length of current code */
				
				int i = 0;
				while (i < numCodes) 
				{
					count = 1;
					int nextlen = length[i];
					if (nextlen == 0) 
					{
						max_count = 138;
						min_count = 3;
					} 
					else 
					{
						max_count = 6;
						min_count = 3;
						if (curlen != nextlen) 
						{
							blTree.WriteSymbol(nextlen);
							count = 0;
						}
					}
					curlen = nextlen;
					i++;
					
					while (i < numCodes && curlen == length[i]) 
					{
						i++;
						if (++count >= max_count) 
						{
							break;
						}
					}
					
					if (count < min_count) 
					{
						while (count-- > 0) 
						{
							blTree.WriteSymbol(curlen);
						}
					}
					else if (curlen != 0) 
					{
						blTree.WriteSymbol(REP_3_6);
						dh.pending.WriteBits(count - 3, 2);
					} 
					else if (count <= 10) 
					{
						blTree.WriteSymbol(REP_3_10);
						dh.pending.WriteBits(count - 3, 3);
					} 
					else 
					{
						blTree.WriteSymbol(REP_11_138);
						dh.pending.WriteBits(count - 11, 7);
					}
				}
			}
		}
		
		///
		public DeflaterPending pending;
		private Tree literalTree, distTree, blTree;
		
		private short[] d_buf;
		private byte[]  l_buf;
		private int last_lit;
		private int extra_bits;
		
		private static short[] staticLCodes;
		private static byte[]  staticLLength;
		private static short[] staticDCodes;
		private static byte[]  staticDLength;
		
		/// <summary>
		/// Reverse the bits of a 16 bit value.
		/// </summary>
		public static short BitReverse(int value) 
		{
			return (short) (bit4Reverse[value & 0xF] << 12
				| bit4Reverse[(value >> 4) & 0xF] << 8
				| bit4Reverse[(value >> 8) & 0xF] << 4
				| bit4Reverse[value >> 12]);
		}
		
		
		static DeflaterHuffman() 
		{
			/* See RFC 1951 3.2.6 */
			/* Literal codes */
			staticLCodes = new short[LITERAL_NUM];
			staticLLength = new byte[LITERAL_NUM];
			int i = 0;
			while (i < 144) 
			{
				staticLCodes[i] = BitReverse((0x030 + i) << 8);
				staticLLength[i++] = 8;
			}
			while (i < 256) 
			{
				staticLCodes[i] = BitReverse((0x190 - 144 + i) << 7);
				staticLLength[i++] = 9;
			}
			while (i < 280) 
			{
				staticLCodes[i] = BitReverse((0x000 - 256 + i) << 9);
				staticLLength[i++] = 7;
			}
			while (i < LITERAL_NUM) 
			{
				staticLCodes[i] = BitReverse((0x0c0 - 280 + i)  << 8);
				staticLLength[i++] = 8;
			}
			
			/* Distant codes */
			staticDCodes = new short[DIST_NUM];
			staticDLength = new byte[DIST_NUM];
			for (i = 0; i < DIST_NUM; i++) 
			{
				staticDCodes[i] = BitReverse(i << 11);
				staticDLength[i] = 5;
			}
		}
		///	
		public DeflaterHuffman(DeflaterPending pending)
		{
			this.pending = pending;
			
			literalTree = new Tree(this, LITERAL_NUM, 257, 15);
			distTree    = new Tree(this, DIST_NUM, 1, 15);
			blTree      = new Tree(this, BITLEN_NUM, 4, 7);
			
			d_buf = new short[BUFSIZE];
			l_buf = new byte [BUFSIZE];
		}
		
		///
		public void Reset() 
		{
			last_lit = 0;
			extra_bits = 0;
			literalTree.Reset();
			distTree.Reset();
			blTree.Reset();
		}
		
		private int L_code(int len) 
		{
			if (len == 255) 
			{
				return 285;
			}
			
			int code = 257;
			while (len >= 8) 
			{
				code += 4;
				len >>= 1;
			}
			return code + len;
		}
		
		private int D_code(int distance) 
		{
			int code = 0;
			while (distance >= 4) 
			{
				code += 2;
				distance >>= 1;
			}
			return code + distance;
		}
		
		///
		public void SendAllTrees(int blTreeCodes)
		{
			blTree.BuildCodes();
			literalTree.BuildCodes();
			distTree.BuildCodes();
			pending.WriteBits(literalTree.numCodes - 257, 5);
			pending.WriteBits(distTree.numCodes - 1, 5);
			pending.WriteBits(blTreeCodes - 4, 4);
			for (int rank = 0; rank < blTreeCodes; rank++) 
			{
				pending.WriteBits(blTree.length[BL_ORDER[rank]], 3);
			}
			literalTree.WriteTree(blTree);
			distTree.WriteTree(blTree);
			//			if (DeflaterConstants.DEBUGGING) {
			//				blTree.CheckEmpty();
			//			}
		}
		
		///
		public void CompressBlock()
		{
			for (int i = 0; i < last_lit; i++) 
			{
				int litlen = l_buf[i] & 0xff;
				int dist = d_buf[i];
				if (dist-- != 0) 
				{
					//					if (DeflaterConstants.DEBUGGING) {
					//						Console.Write("["+(dist+1)+","+(litlen+3)+"]: ");
					//					}
					
					int lc = L_code(litlen);
					literalTree.WriteSymbol(lc);
					
					int bits = (lc - 261) / 4;
					if (bits > 0 && bits <= 5) 
					{
						pending.WriteBits(litlen & ((1 << bits) - 1), bits);
					}
					
					int dc = D_code(dist);
					distTree.WriteSymbol(dc);
					
					bits = dc / 2 - 1;
					if (bits > 0) 
					{
						pending.WriteBits(dist & ((1 << bits) - 1), bits);
					}
				} 
				else 
				{
					//					if (DeflaterConstants.DEBUGGING) {
					//						if (litlen > 32 && litlen < 127) {
					//							Console.Write("("+(char)litlen+"): ");
					//						} else {
					//							Console.Write("{"+litlen+"}: ");
					//						}
					//					}
					literalTree.WriteSymbol(litlen);
				}
			}
			//			if (DeflaterConstants.DEBUGGING) {
			//				Console.Write("EOF: ");
			//			}
			literalTree.WriteSymbol(EOF_SYMBOL);
			//			if (DeflaterConstants.DEBUGGING) {
			//				literalTree.CheckEmpty();
			//				distTree.CheckEmpty();
			//			}
		}
		
		///
		public void FlushStoredBlock(byte[] stored, int stored_offset, int stored_len, bool lastBlock)
		{
			//			if (DeflaterConstants.DEBUGGING) {
			//				//Console.WriteLine("Flushing stored block "+ stored_len);
			//			}
			pending.WriteBits((DeflaterConstants.STORED_BLOCK << 1)
				+ (lastBlock ? 1 : 0), 3);
			pending.AlignToByte();
			pending.WriteShort(stored_len);
			pending.WriteShort(~stored_len);
			pending.WriteBlock(stored, stored_offset, stored_len);
			Reset();
		}
		
		///
		public void FlushBlock(byte[] stored, int stored_offset, int stored_len, bool lastBlock)
		{
			literalTree.freqs[EOF_SYMBOL]++;
			
			/* Build trees */
			literalTree.BuildTree();
			distTree.BuildTree();
			
			/* Calculate bitlen frequency */
			literalTree.CalcBLFreq(blTree);
			distTree.CalcBLFreq(blTree);
			
			/* Build bitlen tree */
			blTree.BuildTree();
			
			int blTreeCodes = 4;
			for (int i = 18; i > blTreeCodes; i--) 
			{
				if (blTree.length[BL_ORDER[i]] > 0) 
				{
					blTreeCodes = i+1;
				}
			}
			int opt_len = 14 + blTreeCodes * 3 + blTree.GetEncodedLength() + 
				literalTree.GetEncodedLength() + distTree.GetEncodedLength() + 
				extra_bits;
			
			int static_len = extra_bits;
			for (int i = 0; i < LITERAL_NUM; i++) 
			{
				static_len += literalTree.freqs[i] * staticLLength[i];
			}
			for (int i = 0; i < DIST_NUM; i++) 
			{
				static_len += distTree.freqs[i] * staticDLength[i];
			}
			if (opt_len >= static_len) 
			{
				/* Force static trees */
				opt_len = static_len;
			}
			
			if (stored_offset >= 0 && stored_len+4 < opt_len >> 3) 
			{
				/* Store Block */
				//				if (DeflaterConstants.DEBUGGING) {
				//					//Console.WriteLine("Storing, since " + stored_len + " < " + opt_len
				//					                  + " <= " + static_len);
				//				}
				FlushStoredBlock(stored, stored_offset, stored_len, lastBlock);
			} 
			else if (opt_len == static_len) 
			{
				/* Encode with static tree */
				pending.WriteBits((DeflaterConstants.STATIC_TREES << 1) + (lastBlock ? 1 : 0), 3);
				literalTree.SetStaticCodes(staticLCodes, staticLLength);
				distTree.SetStaticCodes(staticDCodes, staticDLength);
				CompressBlock();
				Reset();
			} 
			else 
			{
				/* Encode with dynamic tree */
				pending.WriteBits((DeflaterConstants.DYN_TREES << 1) + (lastBlock ? 1 : 0), 3);
				SendAllTrees(blTreeCodes);
				CompressBlock();
				Reset();
			}
		}
		
		///
		public bool IsFull()
		{
			return last_lit + 16 >= BUFSIZE; // HACK: This was == 'last_lit == BUFSIZE', but errors occured with DeflateFast
		}
		
		///
		public bool TallyLit(int lit)
		{
			//			if (DeflaterConstants.DEBUGGING) {
			//				if (lit > 32 && lit < 127) {
			//					//Console.WriteLine("("+(char)lit+")");
			//				} else {
			//					//Console.WriteLine("{"+lit+"}");
			//				}
			//			}
			d_buf[last_lit] = 0;
			l_buf[last_lit++] = (byte)lit;
			literalTree.freqs[lit]++;
			return IsFull();
		}
		
		///
		public bool TallyDist(int dist, int len)
		{
			//			if (DeflaterConstants.DEBUGGING) {
			//				//Console.WriteLine("["+dist+","+len+"]");
			//			}
			
			d_buf[last_lit]   = (short)dist;
			l_buf[last_lit++] = (byte)(len - 3);
			
			int lc = L_code(len - 3);
			literalTree.freqs[lc]++;
			if (lc >= 265 && lc < 285) 
			{
				extra_bits += (lc - 261) / 4;
			}
			
			int dc = D_code(dist - 1);
			distTree.freqs[dc]++;
			if (dc >= 4) 
			{
				extra_bits += dc / 2 - 1;
			}
			return IsFull();
		}
	}
}