bzip2outputstream.cs

C#开发的QQ,希望大家喜欢.献给大家作参考

		}
		
		void EndCompression()
		{
			/*--
			Now another magic 48-bit number, 0x177245385090, to
			indicate the end of the last block.  (sqrt(pi), if
			you want to know.  I did want to use e, but it contains
			too much repetition -- 27 18 28 18 28 46 -- for me
			to feel statistically comfortable.  Call me paranoid.)
			--*/
			BsPutUChar(0x17);
			BsPutUChar(0x72);
			BsPutUChar(0x45);
			BsPutUChar(0x38);
			BsPutUChar(0x50);
			BsPutUChar(0x90);
			
			BsPutint((int)combinedCRC);
			
			BsFinishedWithStream();
		}
		
		void HbAssignCodes (int[] code, char[] length, int minLen, int maxLen, int alphaSize) 
		{
			int vec = 0;
			for (int n = minLen; n <= maxLen; ++n) {
				for (int i = 0; i < alphaSize; ++i) {
					if (length[i] == n) {
						code[i] = vec;
						++vec;
					}
				}
				vec <<= 1;
			}
		}
		
		void BsSetStream(Stream f) 
		{
			baseStream = f;
			bsLive = 0;
			bsBuff = 0;
			bytesOut = 0;
		}
		
		void BsFinishedWithStream()
		{
			while (bsLive > 0) 
			{
				int ch = (bsBuff >> 24);
				baseStream.WriteByte((byte)ch); // write 8-bit
				bsBuff <<= 8;
				bsLive -= 8;
				bytesOut++;
			}
		}
		
		void BsW(int n, int v)
		{
			while (bsLive >= 8) {
				int ch = (bsBuff >> 24);
				baseStream.WriteByte((byte)ch); // write 8-bit
				bsBuff <<= 8;
				bsLive -= 8;
				++bytesOut;
			}
			bsBuff |= (v << (32 - bsLive - n));
			bsLive += n;
		}
		
		void BsPutUChar(int c)
		{
			BsW(8, c);
		}
		
		void BsPutint(int u)
		{
			BsW(8, (u >> 24) & 0xFF);
			BsW(8, (u >> 16) & 0xFF);
			BsW(8, (u >>  8) & 0xFF);
			BsW(8,  u        & 0xFF);
		}
		
		void BsPutIntVS(int numBits, int c)
		{
			BsW(numBits, c);
		}
		
		void SendMTFValues()
		{
			char[][] len = new char[BZip2Constants.N_GROUPS][];
			for (int i = 0; i < BZip2Constants.N_GROUPS; ++i) {
				len[i] = new char[BZip2Constants.MAX_ALPHA_SIZE];
			}
			
			int gs, ge, totc, bt, bc, iter;
			int nSelectors = 0, alphaSize, minLen, maxLen, selCtr;
			int nGroups, nBytes;
			
			alphaSize = nInUse + 2;
			for (int t = 0; t < BZip2Constants.N_GROUPS; t++) {
				for (int v = 0; v < alphaSize; v++) {
					len[t][v] = (char)GREATER_ICOST;
				}
			}
			
			/*--- Decide how many coding tables to use ---*/
			if (nMTF <= 0) {
				Panic();
			}
			
			if (nMTF < 200) {
				nGroups = 2;
			} else if (nMTF < 600) {
				nGroups = 3;
			} else if (nMTF < 1200) {
				nGroups = 4;
			} else if (nMTF < 2400) {
				nGroups = 5;
			} else {
				nGroups = 6;
			}
			
			/*--- Generate an initial set of coding tables ---*/ 
			int nPart = nGroups;
			int remF  = nMTF;
			gs = 0;
			while (nPart > 0) {
				int tFreq = remF / nPart;
				int aFreq = 0;
				ge = gs - 1;
				while (aFreq < tFreq && ge < alphaSize - 1) {
					ge++;
					aFreq += mtfFreq[ge];
				}
				
				if (ge > gs && nPart != nGroups && nPart != 1 && ((nGroups - nPart) % 2 == 1)) {
					aFreq -= mtfFreq[ge];
					ge--;
				}
				
				for (int v = 0; v < alphaSize; v++) {
					if (v >= gs && v <= ge) {
						len[nPart - 1][v] = (char)LESSER_ICOST;
					} else {
						len[nPart - 1][v] = (char)GREATER_ICOST;
					}
				}
				
				nPart--;
				gs = ge + 1;
				remF -= aFreq;
			}
			
			int[][] rfreq = new int[BZip2Constants.N_GROUPS][];
			for (int i = 0; i < BZip2Constants.N_GROUPS; ++i) {
				rfreq[i] = new int[BZip2Constants.MAX_ALPHA_SIZE];
			}
			
			int[]   fave = new int[BZip2Constants.N_GROUPS];
			short[] cost = new short[BZip2Constants.N_GROUPS];
			/*---
			Iterate up to N_ITERS times to improve the tables.
			---*/
			for (iter = 0; iter < BZip2Constants.N_ITERS; ++iter) {
				for (int t = 0; t < nGroups; ++t) {
					fave[t] = 0;
				}
				
				for (int t = 0; t < nGroups; ++t) {
					for (int v = 0; v < alphaSize; ++v) {
						rfreq[t][v] = 0;
					}
				}
				
				nSelectors = 0;
				totc = 0;
				gs   = 0;
				while (true) {
					/*--- Set group start & end marks. --*/
					if (gs >= nMTF) {
						break;
					}
					ge = gs + BZip2Constants.G_SIZE - 1;
					if (ge >= nMTF) {
						ge = nMTF - 1;
					}
					
					/*--
					Calculate the cost of this group as coded
					by each of the coding tables.
					--*/
					for (int t = 0; t < nGroups; t++) {
						cost[t] = 0;
					}
					
					if (nGroups == 6) {
						short cost0, cost1, cost2, cost3, cost4, cost5;
						cost0 = cost1 = cost2 = cost3 = cost4 = cost5 = 0;
						for (int i = gs; i <= ge; ++i) {
							short icv = szptr[i];
							cost0 += (short)len[0][icv];
							cost1 += (short)len[1][icv];
							cost2 += (short)len[2][icv];
							cost3 += (short)len[3][icv];
							cost4 += (short)len[4][icv];
							cost5 += (short)len[5][icv];
						}
						cost[0] = cost0;
						cost[1] = cost1;
						cost[2] = cost2;
						cost[3] = cost3;
						cost[4] = cost4;
						cost[5] = cost5;
					} else {
						for (int i = gs; i <= ge; ++i) {
							short icv = szptr[i];
							for (int t = 0; t < nGroups; t++) {
								cost[t] += (short)len[t][icv];
							}
						}
					}
					
					/*--
					Find the coding table which is best for this group,
					and record its identity in the selector table.
					--*/
					bc = 999999999;
					bt = -1;
					for (int t = 0; t < nGroups; ++t) {
						if (cost[t] < bc) {
							bc = cost[t];
							bt = t;
						}
					}
					totc += bc;
					fave[bt]++;
					selector[nSelectors] = (char)bt;
					nSelectors++;
					
					/*--
					Increment the symbol frequencies for the selected table.
					--*/
					for (int i = gs; i <= ge; ++i) {
						++rfreq[bt][szptr[i]];
					}
					
					gs = ge+1;
				}
				
				/*--
				Recompute the tables based on the accumulated frequencies.
				--*/
				for (int t = 0; t < nGroups; ++t) {
					HbMakeCodeLengths(len[t], rfreq[t], alphaSize, 20);
				}
			}
			
			rfreq = null;
			fave = null;
			cost = null;
			
			if (!(nGroups < 8)) {
				Panic();
			}
			if (!(nSelectors < 32768 && nSelectors <= (2 + (900000 / BZip2Constants.G_SIZE)))) {
				Panic();
			}
			
			/*--- Compute MTF values for the selectors. ---*/
			char[] pos = new char[BZip2Constants.N_GROUPS];
			char ll_i, tmp2, tmp;
			for (int i = 0; i < nGroups; i++) {
				pos[i] = (char)i;
			}
			for (int i = 0; i < nSelectors; i++) {
				ll_i = selector[i];
				int j = 0;
				tmp = pos[j];
				while (ll_i != tmp) {
					j++;
					tmp2 = tmp;
					tmp = pos[j];
					pos[j] = tmp2;
				}
				pos[0] = tmp;
				selectorMtf[i] = (char)j;
			}
			
			int[][] code = new int[BZip2Constants.N_GROUPS][];
			
			for (int i = 0; i < BZip2Constants.N_GROUPS; ++i) {
				code[i] = new int[BZip2Constants.MAX_ALPHA_SIZE];
			}
			
			/*--- Assign actual codes for the tables. --*/
			for (int t = 0; t < nGroups; t++) {
				minLen = 32;
				maxLen = 0;
				for (int i = 0; i < alphaSize; i++) {
					if (len[t][i] > maxLen) {
						maxLen = len[t][i];
					}
					if (len[t][i] < minLen) {
						minLen = len[t][i];
					}
				}
				if (maxLen > 20) {
					Panic();
				}
				if (minLen < 1) {
					Panic();
				}
				HbAssignCodes(code[t], len[t], minLen, maxLen, alphaSize);
			}
			
			/*--- Transmit the mapping table. ---*/
			bool[] inUse16 = new bool[16];
			for (int i = 0; i < 16; ++i) {
				inUse16[i] = false;
				for (int j = 0; j < 16; ++j) {
					if (inUse[i * 16 + j]) {
						inUse16[i] = true; 
					}
				}
			}
			
			nBytes = bytesOut;
			for (int i = 0; i < 16; ++i) {
				if (inUse16[i]) {
					BsW(1,1);
				} else {
					BsW(1,0);
				}
			}
			
			for (int i = 0; i < 16; ++i) {
				if (inUse16[i]) {
					for (int j = 0; j < 16; ++j) {
						if (inUse[i * 16 + j]) {
							BsW(1,1);
						} else {
							BsW(1,0);
						}
					}
				}
			}
			
			/*--- Now the selectors. ---*/
			nBytes = bytesOut;
			BsW(3, nGroups);
			BsW(15, nSelectors);
			for (int i = 0; i < nSelectors; ++i) {
				for (int j = 0; j < selectorMtf[i]; ++j) {
					BsW(1,1);
				}
				BsW(1,0);
			}
			
			/*--- Now the coding tables. ---*/
			nBytes = bytesOut;
			
			for (int t = 0; t < nGroups; ++t) {
				int curr = len[t][0];
				BsW(5, curr);
				for (int i = 0; i < alphaSize; ++i) {
					while (curr < len[t][i]) {
						BsW(2, 2);
						curr++; /* 10 */
					}
					while (curr > len[t][i]) {
						BsW(2, 3);
						curr--; /* 11 */
					}
					BsW (1, 0);
				}
			}
			
			/*--- And finally, the block data proper ---*/
			nBytes = bytesOut;
			selCtr = 0;
			gs = 0;
			while (true) {
				if (gs >= nMTF) {
					break;
				}
				ge = gs + BZip2Constants.G_SIZE - 1;
				if (ge >= nMTF) {
					ge = nMTF - 1;
				}
				
				for (int i = gs; i <= ge; i++) {
					BsW(len[selector[selCtr]][szptr[i]], code[selector[selCtr]][szptr[i]]);
				}
				
				gs = ge + 1;
				++selCtr;
			}
			if (!(selCtr == nSelectors)) {
				Panic();
			}
		}
		
		void MoveToFrontCodeAndSend () 
		{
			BsPutIntVS(24, origPtr);
			GenerateMTFValues();
			SendMTFValues();
		}
		
		Stream baseStream;
		
		void SimpleSort(int lo, int hi, int d) 
		{
			int i, j, h, bigN, hp;
			int v;
			
			bigN = hi - lo + 1;
			if (bigN < 2) {
				return;
			}
			
			hp = 0;
			while (incs[hp] < bigN) {
				hp++;
			}
			hp--;
			
			for (; hp >= 0; hp--) {
				h = incs[hp];
				
				i = lo + h;
				while (true) {
					/*-- copy 1 --*/
					if (i > hi)
						break;
					v = zptr[i];
					j = i;
					while (FullGtU(zptr[j-h]+d, v+d)) {
						zptr[j] = zptr[j-h];
						j = j - h;
						if (j <= (lo + h - 1))
							break;
					}
					zptr[j] = v;
					i++;
					
					/*-- copy 2 --*/
					if (i > hi) {
						break;
					}
					v = zptr[i];
					j = i;
					while (FullGtU ( zptr[j-h]+d, v+d )) {
						zptr[j] = zptr[j-h];
						j = j - h;
						if (j <= (lo + h - 1)) {
							break;
						}
					}
					zptr[j] = v;
					i++;
					
					/*-- copy 3 --*/
					if (i > hi) {
						break;
					}
					v = zptr[i];
					j = i;
					while (FullGtU ( zptr[j-h]+d, v+d)) {
						zptr[j] = zptr[j-h];
						j = j - h;
						if (j <= (lo + h - 1)) {
							break;
						}
					}
					zptr[j] = v;
					i++;
					
					if (workDone > workLimit && firstAttempt) {
						return;
					}
				}
			}
		}
		
		void Vswap(int p1, int p2, int n ) 
		{
			int temp = 0;
			while (n > 0) {
				temp = zptr[p1];
				zptr[p1] = zptr[p2];
				zptr[p2] = temp;
				p1++;
				p2++;
				n--;
			}
		}
		
		byte Med3(byte a, byte b, byte c ) 
		{
			byte t;
			if (a > b) {
				t = a;
				a = b;
				b = t;
			}
			if (b > c) {
				t = b;
				b = c;
				c = t;
			}
			if (a > b) {
				b = a;
			}
			return b;
		}
		
		class StackElem 
		{
			public int ll;
			public int hh;
			public int dd;
		}
		
		void QSort3(int loSt, int hiSt, int dSt) 
		{
			int unLo, unHi, ltLo, gtHi, med, n, m;
			int sp, lo, hi, d;
			StackElem[] stack = new StackElem[QSORT_STACK_SIZE];
			for (int count = 0; count < QSORT_STACK_SIZE; count++) {
				stack[count] = new StackElem();
			}
			
			sp = 0;
			
			stack[sp].ll = loSt;
			stack[sp].hh = hiSt;
			stack[sp].dd = dSt;
			sp++;
			
			while (sp > 0) {
				if (sp >= QSORT_STACK_SIZE) {
					Panic();
				}
				
				sp--;
				lo = stack[sp].ll;
				hi = stack[sp].hh;
				d = stack[sp].dd;
				
				if (hi - lo < SMALL_THRESH || d > DEPTH_THRESH) {
					SimpleSort(lo, hi, d);
					if (workDone > workLimit && firstAttempt) {
						return;
					}
					continue;
				}
				
				med = Med3(block[zptr[lo] + d + 1],
				           block[zptr[hi            ] + d  + 1],
				           block[zptr[(lo + hi) >> 1] + d + 1]);
				
				unLo = ltLo = lo;
				unHi = gtHi = hi;
				
				while (true) {
					while (true) {
						if (unLo > unHi) {
							break;
						}
						n = ((int)block[zptr[unLo]+d + 1]) - med;
						if (n == 0) {
							int temp = 0;
							temp = zptr[unLo];
							zptr[unLo] = zptr[ltLo];
							zptr[ltLo] = temp;
							ltLo++;
							unLo++;
							continue;
						}
						if (n >  0) {
							break;
						}
						unLo++;
					}
					while (true) {
						if (unLo > unHi) {
							break;
						}
						n = ((int)block[zptr[unHi]+d + 1]) - med;
						if (n == 0) {
							int temp = 0;
							temp = zptr[unHi];
							zptr[unHi] = zptr[gtHi];
							zptr[gtHi] = temp;
							gtHi--;
							unHi--;
							continue;
						}
						if (n <  0) {
							break;