diff options
Diffstat (limited to 'crypto/bzip2/src/CBZip2OutputStream.cs')
| -rw-r--r-- | crypto/bzip2/src/CBZip2OutputStream.cs | 900 |
1 files changed, 478 insertions, 422 deletions
diff --git a/crypto/bzip2/src/CBZip2OutputStream.cs b/crypto/bzip2/src/CBZip2OutputStream.cs index 2a70b6856..e81f6ffc1 100644 --- a/crypto/bzip2/src/CBZip2OutputStream.cs +++ b/crypto/bzip2/src/CBZip2OutputStream.cs @@ -71,95 +71,96 @@ namespace Org.BouncyCastle.Apache.Bzip2 } } - protected static void HbMakeCodeLengths(char[] len, int[] freq, - int alphaSize, int maxLen) + protected static void HbMakeCodeLengths(byte[] len, int[] freq, int alphaSize, int maxLen) { /* Nodes and heap entries run from 1. Entry 0 for both the heap and nodes is a sentinel. */ - int nNodes, nHeap, n1, n2, i, j, k; - bool tooLong; - int[] heap = new int[BZip2Constants.MAX_ALPHA_SIZE + 2]; int[] weight = new int[BZip2Constants.MAX_ALPHA_SIZE * 2]; int[] parent = new int[BZip2Constants.MAX_ALPHA_SIZE * 2]; - for (i = 0; i < alphaSize; i++) { + for (int i = 0; i < alphaSize; i++) + { weight[i + 1] = (freq[i] == 0 ? 1 : freq[i]) << 8; } - while (true) { - nNodes = alphaSize; - nHeap = 0; + while (true) + { + int nNodes = alphaSize; + int nHeap = 0; heap[0] = 0; weight[0] = 0; parent[0] = -2; - for (i = 1; i <= alphaSize; i++) { + for (int i = 1; i <= alphaSize; i++) + { parent[i] = -1; - nHeap++; - heap[nHeap] = i; + heap[++nHeap] = i; { - int zz, tmp; - zz = nHeap; - tmp = heap[zz]; - while (weight[tmp] < weight[heap[zz >> 1]]) { + int zz = nHeap; + int tmp = heap[zz]; + while (weight[tmp] < weight[heap[zz >> 1]]) + { heap[zz] = heap[zz >> 1]; zz >>= 1; } heap[zz] = tmp; } } - if (!(nHeap < (BZip2Constants.MAX_ALPHA_SIZE + 2))) { + if (!(nHeap < (BZip2Constants.MAX_ALPHA_SIZE + 2))) + { Panic(); } - while (nHeap > 1) { - n1 = heap[1]; - heap[1] = heap[nHeap]; - nHeap--; + while (nHeap > 1) + { + int n1 = heap[1]; + heap[1] = heap[nHeap--]; { - int zz = 0, yy = 0, tmp = 0; - zz = 1; - tmp = heap[zz]; + int zz = 1; + int tmp = heap[zz]; while (true) { - yy = zz << 1; - if (yy > nHeap) { + int yy = zz << 1; + if (yy > nHeap) break; - } + if (yy < nHeap - && weight[heap[yy + 1]] < weight[heap[yy]]) { + && weight[heap[yy + 1]] < weight[heap[yy]]) + { yy++; } - if (weight[tmp] < weight[heap[yy]]) { + + if (weight[tmp] < weight[heap[yy]]) break; - } + heap[zz] = heap[yy]; zz = yy; } heap[zz] = tmp; } - n2 = heap[1]; - heap[1] = heap[nHeap]; - nHeap--; + int n2 = heap[1]; + heap[1] = heap[nHeap--]; { - int zz = 0, yy = 0, tmp = 0; - zz = 1; - tmp = heap[zz]; - while (true) { - yy = zz << 1; - if (yy > nHeap) { + int zz = 1; + int tmp = heap[zz]; + while (true) + { + int yy = zz << 1; + if (yy > nHeap) break; - } + if (yy < nHeap - && weight[heap[yy + 1]] < weight[heap[yy]]) { + && weight[heap[yy + 1]] < weight[heap[yy]]) + { yy++; } - if (weight[tmp] < weight[heap[yy]]) { + + if (weight[tmp] < weight[heap[yy]]) break; - } + heap[zz] = heap[yy]; zz = yy; } @@ -176,43 +177,46 @@ namespace Org.BouncyCastle.Apache.Bzip2 (weight[n2] & 0x000000ff)))); parent[nNodes] = -1; - nHeap++; - heap[nHeap] = nNodes; + heap[++nHeap] = nNodes; { - int zz = 0, tmp = 0; - zz = nHeap; - tmp = heap[zz]; - while (weight[tmp] < weight[heap[zz >> 1]]) { + int zz = nHeap; + int tmp = heap[zz]; + while (weight[tmp] < weight[heap[zz >> 1]]) + { heap[zz] = heap[zz >> 1]; zz >>= 1; } heap[zz] = tmp; } } - if (!(nNodes < (BZip2Constants.MAX_ALPHA_SIZE * 2))) { + if (!(nNodes < (BZip2Constants.MAX_ALPHA_SIZE * 2))) + { Panic(); } - tooLong = false; - for (i = 1; i <= alphaSize; i++) { - j = 0; - k = i; - while (parent[k] >= 0) { + bool tooLong = false; + for (int i = 1; i <= alphaSize; i++) + { + int j = 0; + int k = i; + while (parent[k] >= 0) + { k = parent[k]; j++; } - len[i - 1] = (char) j; - if (j > maxLen) { + len[i - 1] = (byte)j; + if (j > maxLen) + { tooLong = true; } } - if (!tooLong) { + if (!tooLong) break; - } - for (i = 1; i < alphaSize; i++) { - j = weight[i] >> 8; + for (int i = 1; i < alphaSize; i++) + { + int j = weight[i] >> 8; j = 1 + (j / 2); weight[i] = j << 8; } @@ -233,14 +237,15 @@ namespace Org.BouncyCastle.Apache.Bzip2 always: in the range 0 .. 9. The current block size is 100000 * this number. */ - int blockSize100k; + readonly int blockSize100k; + + private int allowableBlockSize; bool blockRandomised; - int bytesOut; int bsBuff; int bsLive; - CRC mCrc = new CRC(); + readonly CRC mCrc = new CRC(); private bool[] inUse = new bool[256]; private int nInUse; @@ -274,31 +279,31 @@ namespace Org.BouncyCastle.Apache.Bzip2 private int currentByte = -1; private int runLength = 0; - public CBZip2OutputStream(Stream inStream) - : this(inStream, 9) + public CBZip2OutputStream(Stream outStream) + : this(outStream, 9) { } - public CBZip2OutputStream(Stream inStream, int inBlockSize) + public CBZip2OutputStream(Stream outStream, int blockSize) { blockBytes = null; quadrantShorts = null; zptr = null; ftab = null; - inStream.WriteByte((byte)'B'); - inStream.WriteByte((byte)'Z'); + outStream.WriteByte((byte)'B'); + outStream.WriteByte((byte)'Z'); - BsSetStream(inStream); + BsSetStream(outStream); workFactor = 50; - if (inBlockSize > 9) { - inBlockSize = 9; + if (blockSize > 9) { + blockSize = 9; } - if (inBlockSize < 1) { - inBlockSize = 1; + if (blockSize < 1) { + blockSize = 1; } - blockSize100k = inBlockSize; + blockSize100k = blockSize; AllocateCompressStructures(); Initialize(); InitBlock(); @@ -395,7 +400,8 @@ namespace Org.BouncyCastle.Apache.Bzip2 base.Dispose(disposing); } #else - public override void Close() { + public override void Close() + { if (closed) return; @@ -408,12 +414,13 @@ namespace Org.BouncyCastle.Apache.Bzip2 } #endif - public void Finish() { - if (finished) { + public void Finish() + { + if (finished) return; - } - if (runLength > 0) { + if (runLength > 0) + { WriteRun(); } currentByte = -1; @@ -426,15 +433,15 @@ namespace Org.BouncyCastle.Apache.Bzip2 Flush(); } - public override void Flush() { + public override void Flush() + { bsStream.Flush(); } private int blockCRC, combinedCRC; - private void Initialize() { - bytesOut = 0; - + private void Initialize() + { /* Write `magic' bytes h indicating file-format == huffmanised, followed by a digit indicating blockSize100k. */ @@ -444,8 +451,6 @@ namespace Org.BouncyCastle.Apache.Bzip2 combinedCRC = 0; } - private int allowableBlockSize; - private void InitBlock() { mCrc.InitialiseCRC(); @@ -460,10 +465,10 @@ namespace Org.BouncyCastle.Apache.Bzip2 allowableBlockSize = BZip2Constants.baseBlockSize * blockSize100k - 20; } - private void EndBlock() { + private void EndBlock() + { blockCRC = mCrc.GetFinalCRC(); - combinedCRC = (combinedCRC << 1) | (int)(((uint)combinedCRC) >> 31); - combinedCRC ^= blockCRC; + combinedCRC = Integers.RotateLeft(combinedCRC, 1) ^ blockCRC; /* sort the block and establish posn of original string */ DoReversibleTransformation(); @@ -518,131 +523,150 @@ namespace Org.BouncyCastle.Apache.Bzip2 BsFinishedWithStream(); } - private void HbAssignCodes(int[] code, char[] length, int minLen, - int maxLen, int alphaSize) { - int n, vec, i; - - vec = 0; - for (n = minLen; n <= maxLen; n++) { - for (i = 0; i < alphaSize; i++) { - if (length[i] == n) { + private void HbAssignCodes(int[] code, byte[] 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; } } - private void BsSetStream(Stream f) { + private void BsSetStream(Stream f) + { bsStream = f; bsLive = 0; bsBuff = 0; - bytesOut = 0; } - private void BsFinishedWithStream() { - while (bsLive > 0) { - int ch = (bsBuff >> 24); - try { - bsStream.WriteByte((byte)ch); // write 8-bit - } catch (IOException e) { - throw e; - } + private void BsFinishedWithStream() + { + while (bsLive > 0) + { + bsStream.WriteByte((byte)(bsBuff >> 24)); // write 8-bit bsBuff <<= 8; bsLive -= 8; - bytesOut++; } } - private void BsW(int n, int v) { - while (bsLive >= 8) { - int ch = (bsBuff >> 24); - try { - bsStream.WriteByte((byte)ch); // write 8-bit - } catch (IOException e) { - throw e; - } + private void BsW(int n, int v) + { + while (bsLive >= 8) + { + bsStream.WriteByte((byte)(bsBuff >> 24)); // write 8-bit bsBuff <<= 8; bsLive -= 8; - bytesOut++; } - bsBuff |= (v << (32 - bsLive - n)); + bsBuff |= v << (32 - bsLive - n); bsLive += n; } - private void BsPutUChar(int c) { + private void BsPutUChar(int c) + { BsW(8, c); } - private void BsPutint(int u) { - BsW(8, (u >> 24) & 0xff); - BsW(8, (u >> 16) & 0xff); - BsW(8, (u >> 8) & 0xff); - BsW(8, u & 0xff); + private void BsPutint(int u) + { + //BsW(8, (u >> 24) & 0xff); + //BsW(8, (u >> 16) & 0xff); + //BsW(8, (u >> 8) & 0xff); + //BsW(8, u & 0xff); + BsW(16, (u >> 16) & 0xFFFF); + BsW(16, u & 0xFFFF); } - private void BsPutIntVS(int numBits, int c) { + private void BsPutIntVS(int numBits, int c) + { BsW(numBits, c); } - private void SendMTFValues() { - char[][] len = CBZip2InputStream.InitCharArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE); + private void SendMTFValues() + { + byte[][] len = CBZip2InputStream.InitByteArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE); int v, t, i, j, gs, ge, bt, bc, iter; int nSelectors = 0, alphaSize, minLen, maxLen, selCtr; int nGroups; alphaSize = nInUse + 2; - for (t = 0; t < BZip2Constants.N_GROUPS; t++) { - for (v = 0; v < alphaSize; v++) { - len[t][v] = (char) GREATER_ICOST; + for (t = 0; t < BZip2Constants.N_GROUPS; t++) + { + byte[] len_t = len[t]; + for (v = 0; v < alphaSize; v++) + { + len_t[v] = GREATER_ICOST; } } /* Decide how many coding tables to use */ - if (nMTF <= 0) { + if (nMTF <= 0) + { Panic(); } - if (nMTF < 200) { + if (nMTF < 200) + { nGroups = 2; - } else if (nMTF < 600) { + } + else if (nMTF < 600) + { nGroups = 3; - } else if (nMTF < 1200) { + } + else if (nMTF < 1200) + { nGroups = 4; - } else if (nMTF < 2400) { + } + else if (nMTF < 2400) + { nGroups = 5; - } else { + } + else + { nGroups = 6; } - /* Generate an initial set of coding tables */ { - int nPart, remF, tFreq, aFreq; + /* Generate an initial set of coding tables */ + { + int tFreq, aFreq; - nPart = nGroups; - remF = nMTF; + int nPart = nGroups; + int remF = nMTF; gs = 0; - while (nPart > 0) { + while (nPart > 0) + { tFreq = remF / nPart; ge = gs - 1; aFreq = 0; - while (aFreq < tFreq && ge < alphaSize - 1) { - ge++; - aFreq += mtfFreq[ge]; + while (aFreq < tFreq && ge < alphaSize - 1) + { + aFreq += mtfFreq[++ge]; } if (ge > gs && nPart != nGroups && nPart != 1 - && ((nGroups - nPart) % 2 == 1)) { - aFreq -= mtfFreq[ge]; - ge--; + && ((nGroups - nPart) % 2 == 1)) + { + aFreq -= mtfFreq[ge--]; } - for (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; + byte[] len_np = len[nPart - 1]; + for (v = 0; v < alphaSize; v++) + { + if (v >= gs && v <= ge) + { + len_np[v] = LESSER_ICOST; + } + else + { + len_np[v] = GREATER_ICOST; } } @@ -655,64 +679,76 @@ namespace Org.BouncyCastle.Apache.Bzip2 int[][] rfreq = CBZip2InputStream.InitIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE); int[] fave = new int[BZip2Constants.N_GROUPS]; short[] cost = new short[BZip2Constants.N_GROUPS]; + byte[] len_0 = len[0]; + byte[] len_1 = len[1]; + byte[] len_2 = len[2]; + byte[] len_3 = len[3]; + byte[] len_4 = len[4]; + byte[] len_5 = len[5]; + /* Iterate up to N_ITERS times to improve the tables. */ - for (iter = 0; iter < BZip2Constants.N_ITERS; iter++) { - for (t = 0; t < nGroups; t++) { + for (iter = 0; iter < BZip2Constants.N_ITERS; iter++) + { + for (t = 0; t < nGroups; t++) + { fave[t] = 0; - } - for (t = 0; t < nGroups; t++) { - for (v = 0; v < alphaSize; v++) { - rfreq[t][v] = 0; + int[] rfreq_t = rfreq[t]; + for (v = 0; v < alphaSize; v++) + { + rfreq_t[v] = 0; } } nSelectors = 0; gs = 0; - while (true) { - + while (gs < nMTF) + { /* 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 (t = 0; t < nGroups; t++) { - cost[t] = 0; - } + * Calculate the cost of this group as coded by each of the coding tables. + */ + + ge = System.Math.Min(gs + BZip2Constants.G_SIZE - 1, nMTF - 1); + + if (nGroups == 6) + { + short cost0 = 0, cost1 = 0, cost2 = 0, cost3 = 0, cost4 = 0, cost5 = 0; - if (nGroups == 6) { - short cost0, cost1, cost2, cost3, cost4, cost5; - cost0 = cost1 = cost2 = cost3 = cost4 = cost5 = 0; - for (i = gs; i <= ge; i++) { + for (i = gs; i <= ge; i++) + { int 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]; + cost0 += len_0[icv]; + cost1 += len_1[icv]; + cost2 += len_2[icv]; + cost3 += len_3[icv]; + cost4 += len_4[icv]; + cost5 += len_5[icv]; } + cost[0] = cost0; cost[1] = cost1; cost[2] = cost2; cost[3] = cost3; cost[4] = cost4; cost[5] = cost5; - } else { - for (i = gs; i <= ge; i++) { + } + else + { + for (t = 0; t < nGroups; t++) + { + cost[t] = 0; + } + + for (i = gs; i <= ge; i++) + { int icv = szptr[i]; - for (t = 0; t < nGroups; t++) { - cost[t] += (short)len[t][icv]; + for (t = 0; t < nGroups; t++) + { + cost[t] += len[t][icv]; } } } @@ -723,12 +759,14 @@ namespace Org.BouncyCastle.Apache.Bzip2 */ bc = 999999999; bt = -1; - for (t = 0; t < nGroups; t++) { - if (cost[t] < bc) { + for (t = 0; t < nGroups; t++) + { + if (cost[t] < bc) + { bc = cost[t]; bt = t; } - }; + } fave[bt]++; selector[nSelectors] = (char) bt; nSelectors++; @@ -736,8 +774,10 @@ namespace Org.BouncyCastle.Apache.Bzip2 /* Increment the symbol frequencies for the selected table. */ - for (i = gs; i <= ge; i++) { - rfreq[bt][szptr[i]]++; + int[] rfreq_bt = rfreq[bt]; + for (i = gs; i <= ge; i++) + { + rfreq_bt[szptr[i]]++; } gs = ge + 1; @@ -746,7 +786,8 @@ namespace Org.BouncyCastle.Apache.Bzip2 /* Recompute the tables based on the accumulated frequencies. */ - for (t = 0; t < nGroups; t++) { + for (t = 0; t < nGroups; t++) + { HbMakeCodeLengths(len[t], rfreq[t], alphaSize, 20); } } @@ -755,54 +796,66 @@ namespace Org.BouncyCastle.Apache.Bzip2 fave = null; cost = null; - if (!(nGroups < 8)) { + if (!(nGroups < 8)) + { Panic(); } - if (!(nSelectors < 32768 && nSelectors <= (2 + (900000 / BZip2Constants.G_SIZE)))) { + 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 (i = 0; i < nGroups; i++) { - pos[i] = (char) i; + for (i = 0; i < nGroups; i++) + { + pos[i] = (char)i; } - for (i = 0; i < nSelectors; i++) { + for (i = 0; i < nSelectors; i++) + { ll_i = selector[i]; j = 0; tmp = pos[j]; - while (ll_i != tmp) { + while (ll_i != tmp) + { j++; tmp2 = tmp; tmp = pos[j]; pos[j] = tmp2; } pos[0] = tmp; - selectorMtf[i] = (char) j; + selectorMtf[i] = (char)j; } } int[][] code = CBZip2InputStream.InitIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE); /* Assign actual codes for the tables. */ - for (t = 0; t < nGroups; t++) { + for (t = 0; t < nGroups; t++) + { minLen = 32; maxLen = 0; - for (i = 0; i < alphaSize; i++) { - if (len[t][i] > maxLen) { - maxLen = len[t][i]; + byte[] len_t = len[t]; + for (i = 0; i < alphaSize; i++) + { + int lti = len_t[i]; + if (lti > maxLen) + { + maxLen = lti; } - if (len[t][i] < minLen) { - minLen = len[t][i]; + if (lti < minLen) + { + minLen = lti; } } - if (maxLen > 20) { + if (maxLen > 20) + { Panic(); } - if (minLen < 1) { + if (minLen < 1) + { Panic(); } HbAssignCodes(code[t], len[t], minLen, maxLen, alphaSize); @@ -811,57 +864,73 @@ namespace Org.BouncyCastle.Apache.Bzip2 /* Transmit the mapping table. */ { bool[] inUse16 = new bool[16]; - for (i = 0; i < 16; i++) { + for (i = 0; i < 16; i++) + { inUse16[i] = false; - for (j = 0; j < 16; j++) { - if (inUse[i * 16 + j]) { + int i16 = i * 16; + for (j = 0; j < 16; j++) + { + if (inUse[i16 + j]) + { inUse16[i] = true; + break; } } } - for (i = 0; i < 16; i++) { - if (inUse16[i]) { - BsW(1, 1); - } else { - BsW(1, 0); - } + for (i = 0; i < 16; i++) + { + BsW(1, inUse16[i] ? 1 : 0); } - for (i = 0; i < 16; i++) { - if (inUse16[i]) { - for (j = 0; j < 16; j++) { - if (inUse[i * 16 + j]) { - BsW(1, 1); - } else { - BsW(1, 0); - } + for (i = 0; i < 16; i++) + { + if (inUse16[i]) + { + int i16 = i * 16; + for (j = 0; j < 16; j++) + { + BsW(1, inUse[i16 + j] ? 1 : 0); } } } - } /* Now the selectors. */ BsW(3, nGroups); BsW(15, nSelectors); - for (i = 0; i < nSelectors; i++) { - for (j = 0; j < selectorMtf[i]; j++) { - BsW(1, 1); + for (i = 0; i < nSelectors; i++) + { + int count = selectorMtf[i]; + //for (j = 0; j < count; j++) + //{ + // BsW(1, 1); + //} + //BsW(1, 0); + while (count >= 24) + { + BsW(24, 0xFFFFFF); + count -= 24; } - BsW(1, 0); + BsW(count + 1, (1 << (count + 1)) - 2); } /* Now the coding tables. */ - for (t = 0; t < nGroups; t++) { - int curr = len[t][0]; + for (t = 0; t < nGroups; t++) + { + byte[] len_t = len[t]; + int curr = len_t[0]; BsW(5, curr); - for (i = 0; i < alphaSize; i++) { - while (curr < len[t][i]) { + for (i = 0; i < alphaSize; i++) + { + int lti = len_t[i]; + while (curr < lti) + { BsW(2, 2); curr++; /* 10 */ } - while (curr > len[t][i]) { + while (curr > lti) + { BsW(2, 3); curr--; /* 11 */ } @@ -872,28 +941,31 @@ namespace Org.BouncyCastle.Apache.Bzip2 /* And finally, the block data proper */ selCtr = 0; gs = 0; - while (true) { - if (gs >= nMTF) { - break; - } - ge = gs + BZip2Constants.G_SIZE - 1; - if (ge >= nMTF) { - ge = nMTF - 1; - } - for (i = gs; i <= ge; i++) { - BsW(len[selector[selCtr]][szptr[i]], - code[selector[selCtr]][szptr[i]]); + while (gs < nMTF) + { + ge = System.Math.Min(gs + BZip2Constants.G_SIZE - 1, nMTF - 1); + + int selector_selCtr = selector[selCtr]; + byte[] len_selCtr = len[selector_selCtr]; + int[] code_selCtr = code[selector_selCtr]; + + for (i = gs; i <= ge; i++) + { + int sfmap_i = szptr[i]; + BsW(len_selCtr[sfmap_i], code_selCtr[sfmap_i]); } gs = ge + 1; selCtr++; } - if (!(selCtr == nSelectors)) { + if (!(selCtr == nSelectors)) + { Panic(); } } - private void MoveToFrontCodeAndSend() { + private void MoveToFrontCodeAndSend() + { BsPutIntVS(24, origPtr); GenerateMTFValues(); SendMTFValues(); @@ -901,101 +973,92 @@ namespace Org.BouncyCastle.Apache.Bzip2 private Stream bsStream; - private void SimpleSort(int lo, int hi, int d) { - int i, j, h, bigN, hp; - int v; + private void SimpleSort(int lo, int hi, int d) + { + int i, j, h, v; - bigN = hi - lo + 1; - if (bigN < 2) { + int bigN = hi - lo + 1; + if (bigN < 2) return; - } - hp = 0; - while (incs[hp] < bigN) { + int hp = 0; + while (incs[hp] < bigN) + { hp++; } hp--; - for (; hp >= 0; hp--) { + for (; hp >= 0; hp--) + { h = incs[hp]; i = lo + h; - while (true) { + while (i <= hi) + { /* copy 1 */ - if (i > hi) { - break; - } v = zptr[i]; j = i; - while (FullGtU(zptr[j - h] + d, v + d)) { + while (FullGtU(zptr[j - h] + d, v + d)) + { zptr[j] = zptr[j - h]; j = j - h; - if (j <= (lo + h - 1)) { + if (j <= (lo + h - 1)) break; - } } zptr[j] = v; - i++; /* copy 2 */ - if (i > hi) { + if (++i > hi) break; - } + v = zptr[i]; j = i; - while (FullGtU(zptr[j - h] + d, v + d)) { + while (FullGtU(zptr[j - h] + d, v + d)) + { zptr[j] = zptr[j - h]; j = j - h; - if (j <= (lo + h - 1)) { + if (j <= (lo + h - 1)) break; - } } zptr[j] = v; - i++; /* copy 3 */ - if (i > hi) { + if (++i > hi) break; - } + v = zptr[i]; j = i; - while (FullGtU(zptr[j - h] + d, v + d)) { + while (FullGtU(zptr[j - h] + d, v + d)) + { zptr[j] = zptr[j - h]; j = j - h; - if (j <= (lo + h - 1)) { + if (j <= (lo + h - 1)) break; - } } zptr[j] = v; i++; - if (workDone > workLimit && firstAttempt) { + if (workDone > workLimit && firstAttempt) return; - } } } } - private 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--; + private void Vswap(int p1, int p2, int n) + { + while (--n >= 0) + { + int t1 = zptr[p1], t2 = zptr[p2]; + zptr[p1++] = t2; + zptr[p2++] = t1; } } private int Med3(int a, int b, int c) { - if (a > b) - { - int t = a; a = b; b = t; - } - - return c < a ? a : c > b ? b : c; + return a > b + ? (c < b ? b : c > a ? a : c) + : (c < a ? a : c > b ? b : c); } internal class StackElem @@ -1041,9 +1104,8 @@ namespace Org.BouncyCastle.Apache.Bzip2 { SimpleSort(lo, hi, d); if (stackCount < 1 || (workDone > workLimit && firstAttempt)) - { return; - } + stackElem = (StackElem)stack[--stackCount]; lo = stackElem.ll; hi = stackElem.hh; @@ -1051,80 +1113,72 @@ namespace Org.BouncyCastle.Apache.Bzip2 continue; } - int med = Med3(blockBytes[zptr[lo] + d + 1], - blockBytes[zptr[hi] + d + 1], - blockBytes[zptr[(lo + hi) >> 1] + d + 1]); + int d1 = d + 1; + int med = Med3( + blockBytes[zptr[lo] + d1], + blockBytes[zptr[hi] + d1], + blockBytes[zptr[(lo + hi) >> 1] + d1]); unLo = ltLo = lo; unHi = gtHi = hi; - while (true) { - while (true) { - if (unLo > unHi) { + while (true) + { + while (unLo <= unHi) + { + int zUnLo = zptr[unLo]; + n = blockBytes[zUnLo + d1] - med; + if (n > 0) break; - } - n = (int)blockBytes[zptr[unLo] + d + 1] - med; - if (n == 0) { - int temp = 0; - temp = zptr[unLo]; + + if (n == 0) + { zptr[unLo] = zptr[ltLo]; - zptr[ltLo] = temp; - ltLo++; - unLo++; - continue; - }; - if (n > 0) { - break; + zptr[ltLo++] = zUnLo; } unLo++; } - while (true) { - if (unLo > unHi) { + while (unLo <= unHi) + { + int zUnHi = zptr[unHi]; + n = blockBytes[zUnHi + d1] - med; + if (n < 0) break; - } - n = (int)blockBytes[zptr[unHi] + d + 1] - med; - if (n == 0) { - int temp = 0; - temp = zptr[unHi]; + + if (n == 0) + { zptr[unHi] = zptr[gtHi]; - zptr[gtHi] = temp; - gtHi--; - unHi--; - continue; - }; - if (n < 0) { - break; + zptr[gtHi--] = zUnHi; } unHi--; } - if (unLo > unHi) { + if (unLo > unHi) break; - } - int tempx = zptr[unLo]; - zptr[unLo] = zptr[unHi]; - zptr[unHi] = tempx; - unLo++; - unHi--; + + int temp = zptr[unLo]; + zptr[unLo++] = zptr[unHi]; + zptr[unHi--] = temp; } if (gtHi < ltLo) { - ++d; + d = d1; continue; } - n = ((ltLo - lo) < (unLo - ltLo)) ? (ltLo - lo) : (unLo - ltLo); + n = System.Math.Min(ltLo - lo, unLo - ltLo); Vswap(lo, unLo - n, n); - m = ((hi - gtHi) < (gtHi - unHi)) ? (hi - gtHi) : (gtHi - unHi); + + m = System.Math.Min(hi - gtHi, gtHi - unHi); Vswap(unLo, hi - m + 1, m); - n = lo + unLo - ltLo - 1; - m = hi - (gtHi - unHi) + 1; + n = lo + (unLo - ltLo); + m = hi - (gtHi - unHi); - PushStackElem(stack, stackCount++, lo, n, d); - PushStackElem(stack, stackCount++, n + 1, m - 1, d + 1); + PushStackElem(stack, stackCount++, lo, n - 1, d); + PushStackElem(stack, stackCount++, n, m, d1); - lo = m; + lo = m + 1; } } @@ -1141,8 +1195,6 @@ namespace Org.BouncyCastle.Apache.Bzip2 from 0 to last+NUM_OVERSHOOT_BYTES inclusive. First, set up the overshoot area for block. */ - - // if (verbosity >= 4) fprintf ( stderr, " sort initialise ...\n" ); for (i = 0; i < BZip2Constants.NUM_OVERSHOOT_BYTES; i++) { blockBytes[count + i + 1] = blockBytes[(i % count) + 1]; @@ -1181,16 +1233,16 @@ namespace Org.BouncyCastle.Apache.Bzip2 } c1 = blockBytes[0]; - for (i = 0; i < count; i++) + for (i = 1; i <= count; i++) { - c2 = blockBytes[i + 1]; + c2 = blockBytes[i]; ftab[(c1 << 8) + c2]++; c1 = c2; } - for (i = 1; i <= 65536; i++) + for (i = 0; i < 65536; i++) { - ftab[i] += ftab[i - 1]; + ftab[i + 1] += ftab[i]; } c1 = blockBytes[1]; @@ -1219,36 +1271,38 @@ namespace Org.BouncyCastle.Apache.Bzip2 } { - int vv; int h = 1; - do { + do + { h = 3 * h + 1; } while (h <= 256); - do { + do + { h = h / 3; - for (i = h; i <= 255; i++) { - vv = runningOrder[i]; + for (i = h; i <= 255; i++) + { + int vv = runningOrder[i]; j = i; - while ((ftab[((runningOrder[j - h]) + 1) << 8] - - ftab[(runningOrder[j - h]) << 8]) > - (ftab[((vv) + 1) << 8] - ftab[(vv) << 8])) { + while ((ftab[(runningOrder[j - h] + 1) << 8] - ftab[runningOrder[j - h] << 8]) + > (ftab[(vv + 1) << 8] - ftab[vv << 8])) + { runningOrder[j] = runningOrder[j - h]; j = j - h; - if (j <= (h - 1)) { + if (j < h) break; - } } runningOrder[j] = vv; } - } while (h != 1); + } + while (h != 1); } /* The main sorting loop. */ - for (i = 0; i <= 255; i++) { - + for (i = 0; i <= 255; i++) + { /* Process big buckets, starting with the least full. */ @@ -1261,16 +1315,18 @@ namespace Org.BouncyCastle.Apache.Bzip2 completed many of the small buckets [ss, j], so we don't have to sort them at all. */ - for (j = 0; j <= 255; j++) { + for (j = 0; j <= 255; j++) + { sb = (ss << 8) + j; - if (!((ftab[sb] & SETMASK) == SETMASK)) { + if ((ftab[sb] & SETMASK) != SETMASK) + { int lo = ftab[sb] & CLEARMASK; int hi = (ftab[sb + 1] & CLEARMASK) - 1; - if (hi > lo) { + if (hi > lo) + { QSort3(lo, hi, 2); - if (workDone > workLimit && firstAttempt) { + if (workDone > workLimit && firstAttempt) return; - } } ftab[sb] |= SETMASK; } @@ -1288,10 +1344,10 @@ namespace Org.BouncyCastle.Apache.Bzip2 if (i < 255) { - int bbStart = ftab[ss << 8] & CLEARMASK; - int bbSize = (ftab[(ss + 1) << 8] & CLEARMASK) - bbStart; - int shifts = 0; + int bbStart = ftab[ss << 8] & CLEARMASK; + int bbSize = (ftab[(ss + 1) << 8] & CLEARMASK) - bbStart; + int shifts = 0; while ((bbSize >> shifts) > 65534) { shifts++; @@ -1318,17 +1374,19 @@ namespace Org.BouncyCastle.Apache.Bzip2 Now scan this big bucket so as to synthesise the sorted order for small buckets [t, ss] for all t != ss. */ - for (j = 0; j <= 255; j++) { + for (j = 0; j <= 255; j++) + { copy[j] = ftab[(j << 8) + ss] & CLEARMASK; } for (j = ftab[ss << 8] & CLEARMASK; j < (ftab[(ss + 1) << 8] & CLEARMASK); j++) { - c1 = blockBytes[zptr[j]]; + int zptr_j = zptr[j]; + c1 = blockBytes[zptr_j]; if (!bigDone[c1]) { - zptr[copy[c1]] = (zptr[j] == 0 ? count : zptr[j]) - 1; + zptr[copy[c1]] = (zptr_j == 0 ? count : zptr_j) - 1; copy[c1]++; } } @@ -1343,21 +1401,21 @@ namespace Org.BouncyCastle.Apache.Bzip2 private void RandomiseBlock() { - int i; - int rNToGo = 0; - int rTPos = 0; - for (i = 0; i < 256; i++) + for (int i = 0; i < 256; i++) { inUse[i] = false; } - for (i = 0; i < count; i++) + int rNToGo = 0; + int rTPos = 0; + + for (int i = 0; i < count; i++) { if (rNToGo == 0) { - rNToGo = (char) BZip2Constants.rNums[rTPos]; - rTPos++; - if (rTPos == 512) + rNToGo = BZip2Constants.rNums[rTPos]; + + if (++rTPos == 512) { rTPos = 0; } @@ -1395,7 +1453,7 @@ namespace Org.BouncyCastle.Apache.Bzip2 origPtr = i; break; } - }; + } if (origPtr == -1) { @@ -1505,9 +1563,8 @@ namespace Org.BouncyCastle.Apache.Bzip2 because the number of elems to sort is usually small, typically <= 20. */ - private int[] incs = { 1, 4, 13, 40, 121, 364, 1093, 3280, - 9841, 29524, 88573, 265720, - 797161, 2391484 }; + private static readonly int[] incs = { 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, + 2391484 }; private void AllocateCompressStructures() { @@ -1638,53 +1695,52 @@ namespace Org.BouncyCastle.Apache.Bzip2 nMTF = wr; } - public override int Read(byte[] buffer, int offset, int count) { + public override int Read(byte[] buffer, int offset, int count) + { return 0; } - - public override long Seek(long offset, SeekOrigin origin) { + + public override long Seek(long offset, SeekOrigin origin) + { return 0; } - - public override void SetLength(long value) { + + public override void SetLength(long value) + { } - - public override void Write(byte[] buffer, int offset, int count) { - for (int k = 0; k < count; ++k) { + + public override void Write(byte[] buffer, int offset, int count) + { + for (int k = 0; k < count; ++k) + { WriteByte(buffer[k + offset]); } } - - public override bool CanRead { - get { - return false; - } + + public override bool CanRead + { + get { return false; } } - - public override bool CanSeek { - get { - return false; - } + + public override bool CanSeek + { + get { return false; } } - - public override bool CanWrite { - get { - return true; - } + + public override bool CanWrite + { + get { return true; } } - - public override long Length { - get { - return 0; - } + + public override long Length + { + get { return 0; } } - - public override long Position { - get { - return 0; - } - set { - } + + public override long Position + { + get { return 0; } + set {} } } -} \ No newline at end of file +} |