/***************************************************************************
 *                               Compression.cs
 *                            -------------------
 *   begin                : May 1, 2002
 *   copyright            : (C) The RunUO Software Team
 *   email                : info@runuo.com
 *
 *   $Id: Compression.cs,v 1.3 2005/01/22 04:25:04 krrios Exp $
 *   $Author: krrios $
 *   $Date: 2005/01/22 04:25:04 $
 *
 *
 ***************************************************************************/

/***************************************************************************
 *
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 ***************************************************************************/

using System;
using System.IO;

namespace Server.Network
{
	/// <summary>
	/// Handles outgoing packet compression for the network.
	/// </summary>
	public class Compression
	{
		private static int[] m_Table = new int[514]
		{
			0x2, 0x000,	0x5, 0x01F,	0x6, 0x022,	0x7, 0x034,	0x7, 0x075,	0x6, 0x028,	0x6, 0x03B,	0x7, 0x032,
			0x8, 0x0E0,	0x8, 0x062,	0x7, 0x056,	0x8, 0x079,	0x9, 0x19D,	0x8, 0x097,	0x6, 0x02A,	0x7, 0x057,
			0x8, 0x071,	0x8, 0x05B,	0x9, 0x1CC,	0x8, 0x0A7,	0x7, 0x025,	0x7, 0x04F,	0x8, 0x066,	0x8, 0x07D,
			0x9, 0x191,	0x9, 0x1CE,	0x7, 0x03F,	0x9, 0x090,	0x8, 0x059,	0x8, 0x07B,	0x8, 0x091,	0x8, 0x0C6,
			0x6, 0x02D,	0x9, 0x186,	0x8, 0x06F,	0x9, 0x093,	0xA, 0x1CC,	0x8, 0x05A,	0xA, 0x1AE,	0xA, 0x1C0,
			0x9, 0x148,	0x9, 0x14A,	0x9, 0x082,	0xA, 0x19F,	0x9, 0x171,	0x9, 0x120,	0x9, 0x0E7,	0xA, 0x1F3,
			0x9, 0x14B,	0x9, 0x100,	0x9, 0x190,	0x6, 0x013,	0x9, 0x161,	0x9, 0x125,	0x9, 0x133,	0x9, 0x195,
			0x9, 0x173,	0x9, 0x1CA,	0x9, 0x086,	0x9, 0x1E9,	0x9, 0x0DB,	0x9, 0x1EC,	0x9, 0x08B,	0x9, 0x085,
			0x5, 0x00A,	0x8, 0x096,	0x8, 0x09C,	0x9, 0x1C3,	0x9, 0x19C,	0x9, 0x08F,	0x9, 0x18F,	0x9, 0x091,
			0x9, 0x087,	0x9, 0x0C6,	0x9, 0x177,	0x9, 0x089,	0x9, 0x0D6,	0x9, 0x08C,	0x9, 0x1EE,	0x9, 0x1EB,
			0x9, 0x084,	0x9, 0x164,	0x9, 0x175,	0x9, 0x1CD,	0x8, 0x05E,	0x9, 0x088,	0x9, 0x12B,	0x9, 0x172,
			0x9, 0x10A,	0x9, 0x08D,	0x9, 0x13A,	0x9, 0x11C,	0xA, 0x1E1,	0xA, 0x1E0,	0x9, 0x187,	0xA, 0x1DC,
			0xA, 0x1DF,	0x7, 0x074,	0x9, 0x19F,	0x8, 0x08D,	0x8, 0x0E4,	0x7, 0x079,	0x9, 0x0EA,	0x9, 0x0E1,
			0x8, 0x040,	0x7, 0x041,	0x9, 0x10B,	0x9, 0x0B0,	0x8, 0x06A,	0x8, 0x0C1,	0x7, 0x071,	0x7, 0x078,
			0x8, 0x0B1,	0x9, 0x14C,	0x7, 0x043,	0x8, 0x076,	0x7, 0x066,	0x7, 0x04D,	0x9, 0x08A,	0x6, 0x02F,
			0x8, 0x0C9,	0x9, 0x0CE,	0x9, 0x149,	0x9, 0x160,	0xA, 0x1BA,	0xA, 0x19E,	0xA, 0x39F,	0x9, 0x0E5,
			0x9, 0x194,	0x9, 0x184,	0x9, 0x126,	0x7, 0x030,	0x8, 0x06C,	0x9, 0x121,	0x9, 0x1E8,	0xA, 0x1C1,
			0xA, 0x11D,	0xA, 0x163,	0xA, 0x385,	0xA, 0x3DB,	0xA, 0x17D,	0xA, 0x106,	0xA, 0x397,	0xA, 0x24E,
			0x7, 0x02E,	0x8, 0x098,	0xA, 0x33C,	0xA, 0x32E,	0xA, 0x1E9,	0x9, 0x0BF,	0xA, 0x3DF,	0xA, 0x1DD,
			0xA, 0x32D,	0xA, 0x2ED,	0xA, 0x30B,	0xA, 0x107,	0xA, 0x2E8,	0xA, 0x3DE,	0xA, 0x125,	0xA, 0x1E8,
			0x9, 0x0E9,	0xA, 0x1CD,	0xA, 0x1B5,	0x9, 0x165,	0xA, 0x232,	0xA, 0x2E1,	0xB, 0x3AE,	0xB, 0x3C6,
			0xB, 0x3E2,	0xA, 0x205,	0xA, 0x29A,	0xA, 0x248,	0xA, 0x2CD,	0xA, 0x23B,	0xB, 0x3C5,	0xA, 0x251,
			0xA, 0x2E9,	0xA, 0x252,	0x9, 0x1EA,	0xB, 0x3A0,	0xB, 0x391,	0xA, 0x23C,	0xB, 0x392,	0xB, 0x3D5,
			0xA, 0x233,	0xA, 0x2CC,	0xB, 0x390,	0xA, 0x1BB,	0xB, 0x3A1,	0xB, 0x3C4,	0xA, 0x211,	0xA, 0x203,
			0x9, 0x12A,	0xA, 0x231,	0xB, 0x3E0,	0xA, 0x29B,	0xB, 0x3D7,	0xA, 0x202,	0xB, 0x3AD,	0xA, 0x213,
			0xA, 0x253,	0xA, 0x32C,	0xA, 0x23D,	0xA, 0x23F,	0xA, 0x32F,	0xA, 0x11C,	0xA, 0x384,	0xA, 0x31C,
			0xA, 0x17C,	0xA, 0x30A,	0xA, 0x2E0,	0xA, 0x276,	0xA, 0x250,	0xB, 0x3E3,	0xA, 0x396,	0xA, 0x18F,
			0xA, 0x204,	0xA, 0x206,	0xA, 0x230,	0xA, 0x265,	0xA, 0x212,	0xA, 0x23E,	0xB, 0x3AC,	0xB, 0x393,
			0xB, 0x3E1,	0xA, 0x1DE,	0xB, 0x3D6,	0xA, 0x31D,	0xB, 0x3E5,	0xB, 0x3E4,	0xA, 0x207,	0xB, 0x3C7,
			0xA, 0x277,	0xB, 0x3D4,	0x8, 0x0C0,	0xA, 0x162,	0xA, 0x3DA,	0xA, 0x124,	0xA, 0x1B4,	0xA, 0x264,
			0xA, 0x33D,	0xA, 0x1D1,	0xA, 0x1AF,	0xA, 0x39E,	0xA, 0x24F,	0xB, 0x373,	0xA, 0x249,	0xB, 0x372,
			0x9, 0x167,	0xA, 0x210,	0xA, 0x23A,	0xA, 0x1B8,	0xB, 0x3AF,	0xA, 0x18E,	0xA, 0x2EC,	0x7, 0x062,
			0x4, 0x00D
		};

		private static byte[] m_OutputBuffer = new byte[0x40000];
		private static object m_SyncRoot = new object();

		public unsafe static void Compress( byte[] input, int length, out byte[] output, out int outputLength )
		{
			lock ( m_SyncRoot )
			{
				int holdCount = 0;
				int holdValue = 0;

				int packCount = 0;
				int packValue = 0;

				int byteValue = 0;

				int inputLength = length;
				int inputIndex = 0;

				int outputCount = 0;

				fixed ( int *pTable = m_Table )
				{
					fixed ( byte *pOutputBuffer = m_OutputBuffer )
					{
						while ( inputIndex < inputLength )
						{
							byteValue = input[inputIndex++] << 1;

							packCount = pTable[byteValue];
							packValue = pTable[byteValue | 1];

							holdValue <<= packCount;
							holdValue  |= packValue;
							holdCount  += packCount;

							while ( holdCount >= 8 )
							{
								holdCount -= 8;

								pOutputBuffer[outputCount++] = (byte)(holdValue >> holdCount);
							}
						}

						packCount = pTable[0x200];
						packValue = pTable[0x201];

						holdValue <<= packCount;
						holdValue  |= packValue;
						holdCount  += packCount;

						while ( holdCount >= 8 )
						{
							holdCount -= 8;

							pOutputBuffer[outputCount++] = (byte)(holdValue >> holdCount);
						}

						if ( holdCount > 0 )
							pOutputBuffer[outputCount++] = (byte)(holdValue << (8 - holdCount));
					}
				}

				output = m_OutputBuffer;
				outputLength = outputCount;
			}
		}
	}
}

最初由 paragui 发布
这lock, fixed相当c++的什么,
代码粗看简单,
易搞定.

		private static int[] d_Table = new int[512] 
		{
			-1, -111,  0, -2,  -3, -38,  -4, -27,  -5, -21,
			-6, -13,  -7, -10,  104, -8,  42, -9,  141, 155,
			-11, -12,  80, 63,  58, 72,  -14, -17,  -15, -16,
			85, 75,  118, 62,  -18, -19,  77, 89,  -20, 69,
			205, 136,  -22, 51,  -23, 20,  -24, -25,  27, 71,
			-26, 35,  237, 158,  64, -28,  -29, -34,  -30, -33,
			-31, 28,  107, -32,  235, 137,  37, 17,  144, -35,
			84, -36,  -37, 149,  208, 140,  -39, -63,  -40, -49,
			-41, -45,  131, -42,  9, -43,  73, -44,  253, 215,
			7, -46,  22, -47,  121, -48,  125, 43,  -50, -54,
			3, -51,  108, -52,  76, -53,  38, 242,  -55, -58,
			132, -56,  -57, 60,  238, 162,  -59, 34,  -60, -62,
			251, -61,  247, 245,  124, 187,  -64, -89,  -65, -76,
			-66, -69,  -67, 16,  -68, 103,  39, 135,  -70, -74,
			-71, 127,  -72, -73,  186, 180,  182, 223,  -75, 46,
			36, 161,  -77, -85,  -78, -81,  -79, 160,  -80, 241,
			179, 188,  102, -82,  -83, -84,  222, 198,  166, 252,
			115, -86,  -87, -88,  95, 151,  225, 96,  -90, -103,
			-91, -97,  -92, 11,  -93, -94,  93, 92,  -95, -96,
			189, 174,  167, 231,  -98, 29,  -99, -100,  159, 148,
			-101, -102,  233, 183,  226, 196,  -104, 26,  -105, 23,
			-106, -109,  -107, -108,  194, 224,  168, 213,  -110, 47,
			229, 228,  -112, -199,  -113, -167,  -114, -141,  -115, -129,
			-116, -123,  -117, 105,  -118, -120,  49, -119,  197, 191,
			-121, -122,  216, 169,  217, 230,  -124, 114,  -125, -128,
			-126, -127,  249, 190,  220, 199,  88, 106,  2, -130,
			-131, -135,  -132, 99,  -133, -134,  218, 193,  164, 184,
			-136, -138,  91, -137,  250, 173,  -139, -140,  181, 202,
			221, 203,  -142, -158,  -143, -151,  -144, -146,  -145, 30,
			45, 133,  -147, -149,  -148, 53,  171, 246,  130, -150,
			143, 244,  -152, -157,  -153, -156,  -154, -155,  212, 175,
			177, 200,  192, 86,  65, 13,  -159, -163,  -160, 117,
			145, -161,  -162, 54,  239, 219,  -164, 21,  66, -165,
			90, -166,  211, 232,  -168, -179,  -169, -177,  5, -170,
			-171, -174,  -172, -173,  40, 122,  41, 48,  -175, 19,
			113, -176,  170, 195,  14, -178,  10, 15,  -180, -188,
			-181, 32,  -182, -184,  -183, 112,  123, 52,  -185, -186,
			81, 163,  -187, 248,  185, 172,  -189, 119,  -190, -194,
			-191, -193,  -192, 44,  210, 165,  87, 56,  -195, -197,
			-196, 82,  156, 176,  -198, 74,  254, 153,  -200, -227,
			-201, 256,  -202, -213,  -203, -209,  -204, -205,  234, 109,
			-206, -208,  129, -207,  209, 154,  33, 94,  255, -210,
			31, -211,  -212, 70,  207, 227,  -214, -222,  -215, -217,
			-216, 120,  50, 24,  -218, -219,  128, 55,  -220, -221,
			201, 152,  147, 204,  116, -223,  -224, -225,  68, 12,
			-226, 98,  146, 240,  -228, -244,  -229, -242,  -230, -234,
			-231, 110,  8, -232,  -233, 67,  206, 138,  -235, -238,
			100, -236,  57, -237,  214, 142,  -239, -240,  18, 83,
			25, -241,  243, 126,  -243, 6,  97, 4,  -245, 1,
			-246, -247,  111, 101,  -248, -251,  -249, -250,  134, 59,
			178, 79,  -252, -254,  61, -253,  236, 139,  78, -255,
			157, 150
		};

		public static void Decompress(byte[] input, int length, out byte[] output, out int outputLength) 
		{
			int bitmask, i;
			int outlen = 0;
			int f = 0;
			byte[] m_OutputBuffer = new byte[0x40000];
			for (i = 0; i < length; i++) 
			{
				for (bitmask = 1<<7; bitmask > 0; bitmask >>= 1) 
				{
					int offset = (-f) << 1;
					if ((bitmask & input[i]) == 0)
						f = d_Table[offset];
					else
						f = d_Table[offset | 1];
					if (f >= 0) 
					{
						m_OutputBuffer[outlen++] = (byte) f;
						f = 0;
					}
				}
			}
			output = m_OutputBuffer;
			outputLength = outlen;
		}

		static void Main(string[] args)
		{
			byte[] a, b, c;
			a = new byte[1024];
			int i;
			for (i = 0; i < 256; i++) a[i] = (byte) (i);
			int blen, clen;
			Compress(a,256, out b, out blen);
			//ConvertTree();
			Decompress(b, blen, out c, out clen);
			for (i = 0; i < 256; i++) 
			{
				if (c[i] != a[i]) Console.WriteLine("Decode Error! output is {0}, but should be {1}", c[i], a[i]);
				else Console.WriteLine("OK");
			}
		}

最初由 henryouly 发布
ps

这个算法的时间复杂度是O(n)，n为待解码的byte stream的bit的数目，原子操作是数组寻址和赋值。

		//定义huffman tree的结点，我懒得去写property了，通通public member
		class Node 
		{
			public int val, pos, len;
			public Node left, right, parent;
		}

		//先构造huffman tree，然后转换成d_Table输出
		public static void ConvertTree() 
		{
			int i;
			root = new Node();
			root.val = -1;
			root.left = root.right = root.parent = null;
			for (i = 0; i < 257; i++) 
			{
				Node node = new Node();
				node.val = m_Table[i*2+1];
				node.len = m_Table[i*2];
				node.pos = i;
				node.left = node.right = node.parent = null;
				AddToTree(node);
			}

			visit(root);
			Console.WriteLine(seq);
			for (i = 0; i < seq; i++) 
			{
				Console.Write("{0}, {1},  ", d_Table[i*2], d_Table[i*2+1]);
				if (i % 5 == 4) Console.WriteLine();
			}
		}

		//向huffman树添加一个结点
		private static Node root;
		private static void AddToTree(Node node) 
		{
			Node parent = root, last;
			int bitmask = 1 << (node.len - 1);
			while (true) 
			{
				last = parent;
				if ((bitmask & node.val) == 0) 
				{
					parent = parent.left;
				} 
				else 
				{
					parent = parent.right;
				}

				if (parent == null) 
				{
					Node tmp = new Node();
					if (bitmask == 1) tmp = node;
					else 
					{
						tmp.left = tmp.right = null;
						tmp.parent = last;
						tmp.val = -1;
						tmp.len = 0;
					}
					if ((bitmask & node.val) == 0) 
					{
						last.left = tmp;
					} 
					else 
					{
						last.right = tmp;
					}
					parent = tmp;
				}
				bitmask >>= 1;
				if (bitmask == 0) break;
			}
		}

		//转换成d_Table的形式
		private static int seq=0;
		private static int visit(Node node) 
		{
			if (node.left == null && node.right == null) return -1;

			int save_seq = seq++;
			int t;
			t = visit(node.left);

			if (t == -1) 
			{
				d_Table[save_seq*2] = node.left.pos;
			} 
			else 
			{
				d_Table[save_seq*2] = -t;
			}

			t = visit(node.right);
			if (t == -1) 
			{
				d_Table[save_seq*2+1] = node.right.pos;
			} 
			else 
			{
				d_Table[save_seq*2+1] = -t;
			}

			return save_seq;
		}

最初由 寒江雪 发布
初学者不会，高手不愿意花时间