diff options
| -rw-r--r-- | crypto/bzip2/src/BZip2Constants.cs | 66 | ||||
| -rw-r--r-- | crypto/bzip2/src/CBZip2InputStream.cs | 1002 | ||||
| -rw-r--r-- | crypto/bzip2/src/CBZip2OutputStream.cs | 561 | ||||
| -rw-r--r-- | crypto/bzip2/src/CRC.cs | 182 |
4 files changed, 820 insertions, 991 deletions
diff --git a/crypto/bzip2/src/BZip2Constants.cs b/crypto/bzip2/src/BZip2Constants.cs index 4a5442d8b..d238c5b76 100644 --- a/crypto/bzip2/src/BZip2Constants.cs +++ b/crypto/bzip2/src/BZip2Constants.cs @@ -32,72 +32,18 @@ namespace Org.BouncyCastle.Apache.Bzip2 * * @author <a href="mailto:keiron@aftexsw.com">Keiron Liddle</a> */ - public class BZip2Constants { - + public class BZip2Constants + { public const int baseBlockSize = 100000; public const int MAX_ALPHA_SIZE = 258; - public const int MAX_CODE_LEN = 23; + public const int MAX_CODE_LEN = 20; + public const int MAX_CODE_LEN_GEN = 17; public const int RUNA = 0; public const int RUNB = 1; public const int N_GROUPS = 6; public const int G_SIZE = 50; public const int N_ITERS = 4; - public const int MAX_SELECTORS = (2 + (900000 / G_SIZE)); + public const int MAX_SELECTORS = 2 + (900000 / G_SIZE); public const int NUM_OVERSHOOT_BYTES = 20; - - public static readonly int[] rNums = { - 619, 720, 127, 481, 931, 816, 813, 233, 566, 247, - 985, 724, 205, 454, 863, 491, 741, 242, 949, 214, - 733, 859, 335, 708, 621, 574, 73, 654, 730, 472, - 419, 436, 278, 496, 867, 210, 399, 680, 480, 51, - 878, 465, 811, 169, 869, 675, 611, 697, 867, 561, - 862, 687, 507, 283, 482, 129, 807, 591, 733, 623, - 150, 238, 59, 379, 684, 877, 625, 169, 643, 105, - 170, 607, 520, 932, 727, 476, 693, 425, 174, 647, - 73, 122, 335, 530, 442, 853, 695, 249, 445, 515, - 909, 545, 703, 919, 874, 474, 882, 500, 594, 612, - 641, 801, 220, 162, 819, 984, 589, 513, 495, 799, - 161, 604, 958, 533, 221, 400, 386, 867, 600, 782, - 382, 596, 414, 171, 516, 375, 682, 485, 911, 276, - 98, 553, 163, 354, 666, 933, 424, 341, 533, 870, - 227, 730, 475, 186, 263, 647, 537, 686, 600, 224, - 469, 68, 770, 919, 190, 373, 294, 822, 808, 206, - 184, 943, 795, 384, 383, 461, 404, 758, 839, 887, - 715, 67, 618, 276, 204, 918, 873, 777, 604, 560, - 951, 160, 578, 722, 79, 804, 96, 409, 713, 940, - 652, 934, 970, 447, 318, 353, 859, 672, 112, 785, - 645, 863, 803, 350, 139, 93, 354, 99, 820, 908, - 609, 772, 154, 274, 580, 184, 79, 626, 630, 742, - 653, 282, 762, 623, 680, 81, 927, 626, 789, 125, - 411, 521, 938, 300, 821, 78, 343, 175, 128, 250, - 170, 774, 972, 275, 999, 639, 495, 78, 352, 126, - 857, 956, 358, 619, 580, 124, 737, 594, 701, 612, - 669, 112, 134, 694, 363, 992, 809, 743, 168, 974, - 944, 375, 748, 52, 600, 747, 642, 182, 862, 81, - 344, 805, 988, 739, 511, 655, 814, 334, 249, 515, - 897, 955, 664, 981, 649, 113, 974, 459, 893, 228, - 433, 837, 553, 268, 926, 240, 102, 654, 459, 51, - 686, 754, 806, 760, 493, 403, 415, 394, 687, 700, - 946, 670, 656, 610, 738, 392, 760, 799, 887, 653, - 978, 321, 576, 617, 626, 502, 894, 679, 243, 440, - 680, 879, 194, 572, 640, 724, 926, 56, 204, 700, - 707, 151, 457, 449, 797, 195, 791, 558, 945, 679, - 297, 59, 87, 824, 713, 663, 412, 693, 342, 606, - 134, 108, 571, 364, 631, 212, 174, 643, 304, 329, - 343, 97, 430, 751, 497, 314, 983, 374, 822, 928, - 140, 206, 73, 263, 980, 736, 876, 478, 430, 305, - 170, 514, 364, 692, 829, 82, 855, 953, 676, 246, - 369, 970, 294, 750, 807, 827, 150, 790, 288, 923, - 804, 378, 215, 828, 592, 281, 565, 555, 710, 82, - 896, 831, 547, 261, 524, 462, 293, 465, 502, 56, - 661, 821, 976, 991, 658, 869, 905, 758, 745, 193, - 768, 550, 608, 933, 378, 286, 215, 979, 792, 961, - 61, 688, 793, 644, 986, 403, 106, 366, 905, 644, - 372, 567, 466, 434, 645, 210, 389, 550, 919, 135, - 780, 773, 635, 389, 707, 100, 626, 958, 165, 504, - 920, 176, 193, 713, 857, 265, 203, 50, 668, 108, - 645, 990, 626, 197, 510, 357, 358, 850, 858, 364, - 936, 638 - }; } -} \ No newline at end of file +} diff --git a/crypto/bzip2/src/CBZip2InputStream.cs b/crypto/bzip2/src/CBZip2InputStream.cs index 09d39d145..f1d31a0ab 100644 --- a/crypto/bzip2/src/CBZip2InputStream.cs +++ b/crypto/bzip2/src/CBZip2InputStream.cs @@ -23,6 +23,7 @@ */ using System; +using System.Diagnostics; using System.IO; using Org.BouncyCastle.Utilities; @@ -42,30 +43,6 @@ namespace Org.BouncyCastle.Apache.Bzip2 public class CBZip2InputStream : BaseInputStream { - private static void Cadvise() - { - throw new InvalidOperationException(); - } - - private static void CompressedStreamEOF() - { - Cadvise(); - } - - private void MakeMaps() - { - nInUse = 0; - for (int i = 0; i < 256; i++) - { - if (inUse[i]) - { - seqToUnseq[nInUse] = (char)i; - unseqToSeq[i] = (char)nInUse; - nInUse++; - } - } - } - /* index of the last char in the block, so the block size == last + 1. @@ -83,23 +60,18 @@ namespace Org.BouncyCastle.Apache.Bzip2 */ private int blockSize100k; - private bool blockRandomised; - private int bsBuff; private int bsLive; - private CRC mCrc = new CRC(); + private readonly CRC m_blockCrc = new CRC(); - private bool[] inUse = new bool[256]; private int nInUse; - private char[] seqToUnseq = new char[256]; - private char[] unseqToSeq = new char[256]; + private byte[] seqToUnseq = new byte[256]; - private char[] selector = new char[BZip2Constants.MAX_SELECTORS]; - private char[] selectorMtf = new char[BZip2Constants.MAX_SELECTORS]; + private byte[] m_selectors = new byte[BZip2Constants.MAX_SELECTORS]; private int[] tt; - private char[] ll8; + private byte[] ll8; /* freq table collected to save a pass over the data @@ -107,63 +79,60 @@ namespace Org.BouncyCastle.Apache.Bzip2 */ private int[] unzftab = new int[256]; - private int[][] limit = InitIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE); - private int[][] basev = InitIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE); - private int[][] perm = InitIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE); + private int[][] limit = CreateIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_CODE_LEN + 1); + private int[][] basev = CreateIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_CODE_LEN + 1); + private int[][] perm = CreateIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE); private int[] minLens = new int[BZip2Constants.N_GROUPS]; private Stream bsStream; private bool streamEnd = false; - private int currentChar = -1; + private int currentByte = -1; - private const int START_BLOCK_STATE = 1; - private const int RAND_PART_A_STATE = 2; - private const int RAND_PART_B_STATE = 3; - private const int RAND_PART_C_STATE = 4; - private const int NO_RAND_PART_A_STATE = 5; - private const int NO_RAND_PART_B_STATE = 6; - private const int NO_RAND_PART_C_STATE = 7; + private const int RAND_PART_B_STATE = 1; + private const int RAND_PART_C_STATE = 2; + private const int NO_RAND_PART_B_STATE = 3; + private const int NO_RAND_PART_C_STATE = 4; - private int currentState = START_BLOCK_STATE; + private int currentState = 0; - private int storedBlockCRC, storedCombinedCRC, computedCombinedCRC; + private int m_expectedBlockCrc, m_expectedStreamCrc, m_streamCrc; int i2, count, chPrev, ch2; int i, tPos; int rNToGo = 0; int rTPos = 0; int j2; - char z; + int z; - public CBZip2InputStream(Stream zStream) { + public CBZip2InputStream(Stream zStream) + { ll8 = null; tt = null; - BsSetStream(zStream); - Initialize(); - InitBlock(); - SetupBlock(); - } + bsStream = zStream; + bsLive = 0; + bsBuff = 0; - internal static int[][] InitIntArray(int n1, int n2) - { - int[][] a = new int[n1][]; - for (int k = 0; k < n1; ++k) - { - a[k] = new int[n2]; - } - return a; - } + int magic1 = bsStream.ReadByte(); + int magic2 = bsStream.ReadByte(); + int version = bsStream.ReadByte(); + int level = bsStream.ReadByte(); + if (level < 0) + throw new EndOfStreamException(); - internal static byte[][] InitByteArray(int n1, int n2) - { - byte[][] a = new byte[n1][]; - for (int k = 0; k < n1; ++k) - { - a[k] = new byte[n2]; - } - return a; + if (magic1 != 'B' | magic2 != 'Z' | version != 'h' | level < '1' | level > '9') + throw new IOException("Invalid stream header"); + + blockSize100k = level - '0'; + + int n = BZip2Constants.baseBlockSize * blockSize100k; + ll8 = new byte[n]; + tt = new int[n]; + + m_streamCrc = 0; + + BeginBlock(); } public override int Read(byte[] buffer, int offset, int count) @@ -192,21 +161,15 @@ namespace Org.BouncyCastle.Apache.Bzip2 if (streamEnd) return -1; - int retChar = currentChar; + int result = currentByte; switch (currentState) { - case START_BLOCK_STATE: - break; - case RAND_PART_A_STATE: - break; case RAND_PART_B_STATE: SetupRandPartB(); break; case RAND_PART_C_STATE: SetupRandPartC(); break; - case NO_RAND_PART_A_STATE: - break; case NO_RAND_PART_B_STATE: SetupNoRandPartB(); break; @@ -214,329 +177,307 @@ namespace Org.BouncyCastle.Apache.Bzip2 SetupNoRandPartC(); break; default: - break; + throw new InvalidOperationException(); } - return retChar; + return result; } - private void Initialize() { - char magic3, magic4; - magic3 = BsGetUChar(); - magic4 = BsGetUChar(); - if (magic3 != 'B' && magic4 != 'Z') + private void BeginBlock() + { + long magic48 = BsGetLong48(); + if (magic48 != 0x314159265359L) { - throw new IOException("Not a BZIP2 marked stream"); - } - magic3 = BsGetUChar(); - magic4 = BsGetUChar(); - if (magic3 != 'h' || magic4 < '1' || magic4 > '9') { - BsFinishedWithStream(); - streamEnd = true; - return; - } + if (magic48 != 0x177245385090L) + throw new IOException("Block header error"); - SetDecompressStructureSizes(magic4 - '0'); - computedCombinedCRC = 0; - } + m_expectedStreamCrc = BsGetInt32(); + if (m_expectedStreamCrc != m_streamCrc) + throw new IOException("Stream CRC error"); - private void InitBlock() { - char magic1, magic2, magic3, magic4; - char magic5, magic6; - magic1 = BsGetUChar(); - magic2 = BsGetUChar(); - magic3 = BsGetUChar(); - magic4 = BsGetUChar(); - magic5 = BsGetUChar(); - magic6 = BsGetUChar(); - if (magic1 == 0x17 && magic2 == 0x72 && magic3 == 0x45 - && magic4 == 0x38 && magic5 == 0x50 && magic6 == 0x90) { - Complete(); - return; - } - - if (magic1 != 0x31 || magic2 != 0x41 || magic3 != 0x59 - || magic4 != 0x26 || magic5 != 0x53 || magic6 != 0x59) { - BadBlockHeader(); + BsFinishedWithStream(); streamEnd = true; return; } - storedBlockCRC = BsGetInt32(); + m_expectedBlockCrc = BsGetInt32(); - blockRandomised = BsR(1) == 1; + bool blockRandomised = BsGetBit() == 1; GetAndMoveToFrontDecode(); - mCrc.InitialiseCRC(); - currentState = START_BLOCK_STATE; - } + m_blockCrc.Initialise(); - private void EndBlock() - { - int computedBlockCRC = mCrc.GetFinalCRC(); - /* A bad CRC is considered a fatal error. */ - if (storedBlockCRC != computedBlockCRC) + int[] cftab = new int[257]; { - CrcError(); + int accum = 0; + cftab[0] = 0; + for (i = 0; i < 256; ++i) + { + accum += unzftab[i]; + cftab[i + 1] = accum; + } + if (accum != (last + 1)) + throw new InvalidOperationException(); } - computedCombinedCRC = Integers.RotateLeft(computedCombinedCRC, 1) ^ computedBlockCRC; - } - - private void Complete() { - storedCombinedCRC = BsGetInt32(); - if (storedCombinedCRC != computedCombinedCRC) { - CrcError(); + for (i = 0; i <= last; i++) + { + byte ch = ll8[i]; + tt[cftab[ch]++] = i; } - BsFinishedWithStream(); - streamEnd = true; - } + tPos = tt[origPtr]; - private static void BlockOverrun() { - Cadvise(); - } + count = 0; + i2 = 0; + ch2 = 256; /* not a char and not EOF */ - private static void BadBlockHeader() { - Cadvise(); + if (blockRandomised) + { + rNToGo = 0; + rTPos = 0; + SetupRandPartA(); + } + else + { + SetupNoRandPartA(); + } } - private static void CrcError() { - Cadvise(); + private void EndBlock() + { + int blockFinalCrc = m_blockCrc.GetFinal(); + if (m_expectedBlockCrc != blockFinalCrc) + throw new IOException("Block CRC error"); + + m_streamCrc = Integers.RotateLeft(m_streamCrc, 1) ^ blockFinalCrc; } - private void BsFinishedWithStream() { - try { - if (this.bsStream != null) { + private void BsFinishedWithStream() + { + try + { + if (this.bsStream != null) + { Platform.Dispose(this.bsStream); this.bsStream = null; } - } catch { + } + catch + { //ignore } } - private void BsSetStream(Stream f) { - bsStream = f; - bsLive = 0; - bsBuff = 0; + private int BsGetBit() + { + if (bsLive == 0) + { + bsBuff = RequireByte(); + bsLive = 7; + return (int)((uint)bsBuff >> 7); + } + + --bsLive; + + return (bsBuff >> bsLive) & 1; } - private int BsR(int n) { - int v; - while (bsLive < n) { - int zzi; - char thech = '\0'; - try { - thech = (char)bsStream.ReadByte(); - } catch (IOException) { - CompressedStreamEOF(); - } - if (thech == '\uffff') { - CompressedStreamEOF(); - } - zzi = thech; - bsBuff = (bsBuff << 8) | (zzi & 0xff); + private int BsGetBits(int n) + { + Debug.Assert(1 <= n && n <= 24); + + while (bsLive < n) + { + bsBuff = (bsBuff << 8) | RequireByte(); bsLive += 8; } - v = (bsBuff >> (bsLive - n)) & ((1 << n) - 1); bsLive -= n; - return v; - } - private char BsGetUChar() - { - return (char)BsR(8); + return (bsBuff >> bsLive) & ((1 << n) - 1); } - private int BsGetint() + private int BsGetBitsSmall(int n) { - //int u = 0; - //u = (u << 8) | BsR(8); - //u = (u << 8) | BsR(8); - //u = (u << 8) | BsR(8); - //u = (u << 8) | BsR(8); - //return u; - int u = BsR(16) << 16; - return u | BsR(16); + Debug.Assert(1 <= n && n <= 8); + + if (bsLive < n) + { + bsBuff = (bsBuff << 8) | RequireByte(); + bsLive += 8; + } + + bsLive -= n; + + return (bsBuff >> bsLive) & ((1 << n) - 1); } - private int BsGetIntVS(int numBits) + private int BsGetInt32() { - return BsR(numBits); + int u = BsGetBits(16) << 16; + return u | BsGetBits(16); } - private int BsGetInt32() + private long BsGetLong48() { - return BsGetint(); + long u = (long)BsGetBits(24) << 24; + return u | (long)BsGetBits(24); } private void HbCreateDecodeTables(int[] limit, int[] basev, int[] perm, byte[] length, int minLen, int maxLen, int alphaSize) { - int i, j, vec; - - int pp = 0; - for (i = minLen; i <= maxLen; i++) { - for (j = 0; j < alphaSize; j++) { - if (length[j] == i) { - perm[pp] = j; - pp++; + Array.Clear(basev, 0, basev.Length); + Array.Clear(limit, 0, limit.Length); + + int pp = 0, baseVal = 0; + for (int i = minLen; i <= maxLen; i++) + { + basev[i] = baseVal; + for (int j = 0; j < alphaSize; j++) + { + if (length[j] == i) + { + perm[pp++] = j; } } - } - - for (i = 0; i < BZip2Constants.MAX_CODE_LEN; i++) { - basev[i] = 0; - } - for (i = 0; i < alphaSize; i++) { - basev[length[i] + 1]++; - } - - for (i = 1; i < BZip2Constants.MAX_CODE_LEN; i++) { - basev[i] += basev[i - 1]; - } - - for (i = 0; i < BZip2Constants.MAX_CODE_LEN; i++) { - limit[i] = 0; - } - vec = 0; - - for (i = minLen; i <= maxLen; i++) { - vec += (basev[i + 1] - basev[i]); - limit[i] = vec - 1; - vec <<= 1; - } - for (i = minLen + 1; i <= maxLen; i++) { - basev[i] = ((limit[i - 1] + 1) << 1) - basev[i]; + limit[i] = baseVal + pp; + baseVal += limit[i]; } } - private void RecvDecodingTables() + private int RecvDecodingTables() { - byte[][] len = InitByteArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE); - int i, j, t, nGroups, nSelectors, alphaSize; - int minLen, maxLen; - bool[] inUse16 = new bool[16]; + int i, j; + + nInUse = 0; /* Receive the mapping table */ - for (i = 0; i < 16; i++) - { - inUse16[i] = BsR(1) == 1; - } + int inUse16 = BsGetBits(16); - for (i = 0; i < 16; i++) + for (i = 0; i < 16; ++i) { - int i16 = i * 16; - if (inUse16[i]) + if ((inUse16 & (0x8000 >> i)) != 0) { - for (j = 0; j < 16; j++) - { - inUse[i16 + j] = BsR(1) == 1; - } - } - else - { - for (j = 0; j < 16; j++) + int inUse = BsGetBits(16); + + int i16 = i * 16; + for (j = 0; j < 16; ++j) { - inUse[i16 + j] = false; + if ((inUse & (0x8000 >> j)) != 0) + { + seqToUnseq[nInUse++] = (byte)(i16 + j); + } } } } - MakeMaps(); - alphaSize = nInUse + 2; + if (nInUse < 1) + throw new InvalidOperationException(); + + int alphaSize = nInUse + 2; /* Now the selectors */ - nGroups = BsR(3); - nSelectors = BsR(15); - for (i = 0; i < nSelectors; i++) { - j = 0; - while (BsR(1) == 1) { - j++; - } - selectorMtf[i] = (char)j; - } + int nGroups = BsGetBitsSmall(3); + if (nGroups < 2 || nGroups > BZip2Constants.N_GROUPS) + throw new InvalidOperationException(); - /* Undo the MTF values for the selectors. */ + int nSelectors = BsGetBits(15); + if (nSelectors < 1) + throw new InvalidOperationException(); + + uint mtfGroups = 0x00543210U; + for (i = 0; i < nSelectors; i++) { - char[] pos = new char[BZip2Constants.N_GROUPS]; - char tmp, v; - for (v = '\0'; v < nGroups; v++) { - pos[v] = v; + int mtfSelector = 0; + while (BsGetBit() == 1) + { + if (++mtfSelector >= nGroups) + throw new InvalidOperationException(); } - for (i = 0; i < nSelectors; i++) { - v = selectorMtf[i]; - tmp = pos[v]; - while (v > 0) { - pos[v] = pos[v - 1]; - v--; - } - pos[0] = tmp; - selector[i] = tmp; + // Ignore declared selectors in excess of the maximum usable number + if (i >= BZip2Constants.MAX_SELECTORS) + continue; + + // Undo the MTF value for the selector. + switch (mtfSelector) + { + case 0: + break; + case 1: + mtfGroups = (mtfGroups >> 4) & 0x00000FU | (mtfGroups << 4) & 0x0000F0U | mtfGroups & 0xFFFF00U; + break; + case 2: + mtfGroups = (mtfGroups >> 8) & 0x00000FU | (mtfGroups << 4) & 0x000FF0U | mtfGroups & 0xFFF000U; + break; + case 3: + mtfGroups = (mtfGroups >> 12) & 0x00000FU | (mtfGroups << 4) & 0x00FFF0U | mtfGroups & 0xFF0000U; + break; + case 4: + mtfGroups = (mtfGroups >> 16) & 0x00000FU | (mtfGroups << 4) & 0x0FFFF0U | mtfGroups & 0xF00000U; + break; + case 5: + mtfGroups = (mtfGroups >> 20) & 0x00000FU | (mtfGroups << 4) & 0xFFFFF0U; + break; + default: + throw new InvalidOperationException(); } + + m_selectors[i] = (byte)(mtfGroups & 0xF); } + byte[] len_t = new byte[alphaSize]; + /* Now the coding tables */ - for (t = 0; t < nGroups; t++) + for (int t = 0; t < nGroups; t++) { - byte[] len_t = len[t]; - int curr = BsR(5); + int maxLen = 0, minLen = 32; + int curr = BsGetBitsSmall(5); + if ((curr < 1) | (curr > BZip2Constants.MAX_CODE_LEN)) + throw new InvalidOperationException(); + for (i = 0; i < alphaSize; i++) { - while (BsR(1) == 1) + int markerBit = BsGetBit(); + while (markerBit != 0) { - if (BsR(1) == 0) - { - curr++; - } - else - { - curr--; - } + int nextTwoBits = BsGetBitsSmall(2); + curr += 1 - (nextTwoBits & 2); + if ((curr < 1) | (curr > BZip2Constants.MAX_CODE_LEN)) + throw new InvalidOperationException(); + markerBit = nextTwoBits & 1; } + len_t[i] = (byte)curr; + maxLen = System.Math.Max(maxLen, curr); + minLen = System.Math.Min(minLen, curr); } - } - /* Create the Huffman decoding tables */ - for (t = 0; t < nGroups; t++) - { - minLen = 32; - maxLen = 0; - byte[] len_t = len[t]; - for (i = 0; i < alphaSize; i++) - { - int lti = len_t[i]; - if (lti > maxLen) - { - maxLen = lti; - } - if (lti < minLen) - { - minLen = lti; - } - } + /* Create the Huffman decoding tables */ HbCreateDecodeTables(limit[t], basev[t], perm[t], len_t, minLen, maxLen, alphaSize); minLens[t] = minLen; } + + return nSelectors; } private void GetAndMoveToFrontDecode() { - char[] yy = new char[256]; - int i, j, nextSym, limitLast; - int EOB, groupNo, groupPos; + byte[] yy = new byte[256]; + int i, j, nextSym; + + int limitLast = BZip2Constants.baseBlockSize * blockSize100k; - limitLast = BZip2Constants.baseBlockSize * blockSize100k; - origPtr = BsGetIntVS(24); + origPtr = BsGetBits(24); + if (origPtr > 10 + limitLast) + throw new InvalidOperationException(); - RecvDecodingTables(); - EOB = nInUse + 1; - groupNo = -1; - groupPos = 0; + int nSelectors = RecvDecodingTables(); + + int alphaSize = nInUse + 2; + int EOB = nInUse + 1; /* Setting up the unzftab entries here is not strictly @@ -544,153 +485,107 @@ namespace Org.BouncyCastle.Apache.Bzip2 in a separate pass, and so saves a block's worth of cache misses. */ - for (i = 0; i <= 255; i++) - { - unzftab[i] = 0; - } + Array.Clear(unzftab, 0, unzftab.Length); for (i = 0; i <= 255; i++) { - yy[i] = (char)i; + yy[i] = (byte)i; } last = -1; + int groupNo = 0; + int groupPos = BZip2Constants.G_SIZE - 1; + int groupSel = m_selectors[groupNo]; + int groupMinLen = minLens[groupSel]; + int[] groupLimits = limit[groupSel]; + int[] groupPerm = perm[groupSel]; + int[] groupBase = basev[groupSel]; + { - int zt, zn, zvec, zj; - if (groupPos == 0) - { - groupNo++; - groupPos = BZip2Constants.G_SIZE; - } - groupPos--; - zt = selector[groupNo]; - zn = minLens[zt]; - zvec = BsR(zn); - while (zvec > limit[zt][zn]) + int zn = groupMinLen; + int zvec = BsGetBits(groupMinLen); + while (zvec >= groupLimits[zn]) { - zn++; - { - { - while (bsLive < 1) - { - int zzi; - char thech = '\0'; - try - { - thech = (char)bsStream.ReadByte(); - } - catch (IOException) - { - CompressedStreamEOF(); - } - if (thech == '\uffff') - { - CompressedStreamEOF(); - } - zzi = thech; - bsBuff = (bsBuff << 8) | (zzi & 0xff); - bsLive += 8; - } - } - zj = (bsBuff >> (bsLive - 1)) & 1; - bsLive--; - } - zvec = (zvec << 1) | zj; + if (++zn > BZip2Constants.MAX_CODE_LEN) + throw new InvalidOperationException(); + + zvec = (zvec << 1) | BsGetBit(); } - nextSym = perm[zt][zvec - basev[zt][zn]]; + int permIndex = zvec - groupBase[zn]; + if (permIndex >= alphaSize) + throw new InvalidOperationException(); + + nextSym = groupPerm[permIndex]; } while (nextSym != EOB) { - if (nextSym == BZip2Constants.RUNA || nextSym == BZip2Constants.RUNB) + //if (nextSym == BZip2Constants.RUNA || nextSym == BZip2Constants.RUNB) + if (nextSym <= BZip2Constants.RUNB) { - char ch; - int s = -1; - int N = 1; + int n = 1, s = 0; do { - if (nextSym == BZip2Constants.RUNA) - { - s += (0 + 1) * N; - } - else if (nextSym == BZip2Constants.RUNB) - { - s += (1 + 1) * N; - } - N = N * 2; + if (n > 1024 * 1024) + throw new InvalidOperationException(); + + s += n << nextSym; + n <<= 1; + { - int zt, zn, zvec, zj; if (groupPos == 0) { - groupNo++; + if (++groupNo >= nSelectors) + throw new InvalidOperationException(); + groupPos = BZip2Constants.G_SIZE; + groupSel = m_selectors[groupNo]; + groupMinLen = minLens[groupSel]; + groupLimits = limit[groupSel]; + groupPerm = perm[groupSel]; + groupBase = basev[groupSel]; } groupPos--; - zt = selector[groupNo]; - zn = minLens[zt]; - zvec = BsR(zn); - while (zvec > limit[zt][zn]) + + int zn = groupMinLen; + int zvec = BsGetBits(groupMinLen); + while (zvec >= groupLimits[zn]) { - zn++; - { - { - while (bsLive < 1) - { - int zzi; - char thech = '\0'; - try - { - thech = (char)bsStream.ReadByte(); - } - catch (IOException) - { - CompressedStreamEOF(); - } - if (thech == '\uffff') - { - CompressedStreamEOF(); - } - zzi = thech; - bsBuff = (bsBuff << 8) | (zzi & 0xff); - bsLive += 8; - } - } - zj = (bsBuff >> (bsLive - 1)) & 1; - bsLive--; - } - zvec = (zvec << 1) | zj; + if (++zn > BZip2Constants.MAX_CODE_LEN) + throw new InvalidOperationException(); + + zvec = (zvec << 1) | BsGetBit(); } - nextSym = perm[zt][zvec - basev[zt][zn]]; + int permIndex = zvec - groupBase[zn]; + if (permIndex >= alphaSize) + throw new InvalidOperationException(); + + nextSym = groupPerm[permIndex]; } } - while (nextSym == BZip2Constants.RUNA || nextSym == BZip2Constants.RUNB); + //while (nextSym == BZip2Constants.RUNA || nextSym == BZip2Constants.RUNB); + while (nextSym <= BZip2Constants.RUNB); - s++; - ch = seqToUnseq[yy[0]]; + byte ch = seqToUnseq[yy[0]]; unzftab[ch] += s; - while (s > 0) - { - last++; - ll8[last] = ch; - s--; - } + if (last >= limitLast - s) + throw new InvalidOperationException("Block overrun"); - if (last >= limitLast) + while (--s >= 0) { - BlockOverrun(); + ll8[++last] = ch; } + continue; } else { if (++last >= limitLast) - { - BlockOverrun(); - } + throw new InvalidOperationException("Block overrun"); - char tmp = yy[nextSym - 1]; + byte tmp = yy[nextSym - 1]; unzftab[seqToUnseq[tmp]]++; ll8[last] = seqToUnseq[tmp]; @@ -714,217 +609,202 @@ namespace Org.BouncyCastle.Apache.Bzip2 yy[0] = tmp; { - int zt, zn, zvec, zj; if (groupPos == 0) { - groupNo++; + if (++groupNo >= nSelectors) + throw new InvalidOperationException(); + groupPos = BZip2Constants.G_SIZE; + groupSel = m_selectors[groupNo]; + groupMinLen = minLens[groupSel]; + groupLimits = limit[groupSel]; + groupPerm = perm[groupSel]; + groupBase = basev[groupSel]; } groupPos--; - zt = selector[groupNo]; - zn = minLens[zt]; - zvec = BsR(zn); - while (zvec > limit[zt][zn]) + + int zn = groupMinLen; + int zvec = BsGetBits(groupMinLen); + while (zvec >= groupLimits[zn]) { - zn++; - { - { - while (bsLive < 1) - { - int zzi; - char thech = '\0'; - try - { - thech = (char)bsStream.ReadByte(); - } - catch (IOException) - { - CompressedStreamEOF(); - } - zzi = thech; - bsBuff = (bsBuff << 8) | (zzi & 0xff); - bsLive += 8; - } - } - zj = (bsBuff >> (bsLive - 1)) & 1; - bsLive--; - } - zvec = (zvec << 1) | zj; + if (++zn > BZip2Constants.MAX_CODE_LEN) + throw new InvalidOperationException(); + + zvec = (zvec << 1) | BsGetBit(); } - nextSym = perm[zt][zvec - basev[zt][zn]]; + int permIndex = zvec - groupBase[zn]; + if (permIndex >= alphaSize) + throw new InvalidOperationException(); + + nextSym = groupPerm[permIndex]; } continue; } } - } - private void SetupBlock() { - int[] cftab = new int[257]; - char ch; + if (origPtr > last) + throw new InvalidOperationException(); - cftab[0] = 0; - for (i = 1; i <= 256; i++) { - cftab[i] = unzftab[i - 1]; - } - for (i = 1; i <= 256; i++) { - cftab[i] += cftab[i - 1]; - } + // Check unzftab entries are in range. + { + int nblock = last + 1; + int check = 0; - for (i = 0; i <= last; i++) { - ch = ll8[i]; - tt[cftab[ch]] = i; - cftab[ch]++; + for (i = 0; i <= 255; i++) + { + int t = unzftab[i]; + check |= t; + check |= nblock - t; + } + if (check < 0) + throw new InvalidOperationException(); } - cftab = null; - - tPos = tt[origPtr]; - - count = 0; - i2 = 0; - ch2 = 256; /* not a char and not EOF */ + } - if (blockRandomised) { - rNToGo = 0; - rTPos = 0; - SetupRandPartA(); - } else { - SetupNoRandPartA(); - } + private int RequireByte() + { + int b = bsStream.ReadByte(); + if (b < 0) + throw new EndOfStreamException(); + return b & 0xFF; } - private void SetupRandPartA() { - if (i2 <= last) { + private void SetupRandPartA() + { + if (i2 <= last) + { chPrev = ch2; ch2 = ll8[tPos]; tPos = tt[tPos]; - if (rNToGo == 0) { - rNToGo = BZip2Constants.rNums[rTPos]; - rTPos++; - if (rTPos == 512) { - rTPos = 0; - } + if (rNToGo == 0) + { + rNToGo = CBZip2OutputStream.RNums[rTPos++]; + rTPos &= 0x1FF; } rNToGo--; - ch2 ^= (rNToGo == 1) ? 1 : 0; + ch2 ^= rNToGo == 1 ? 1 : 0; i2++; - currentChar = ch2; + currentByte = ch2; currentState = RAND_PART_B_STATE; - mCrc.UpdateCRC((byte)ch2); - } else { + m_blockCrc.Update((byte)ch2); + } + else + { EndBlock(); - InitBlock(); - SetupBlock(); + BeginBlock(); } } - private void SetupNoRandPartA() { - if (i2 <= last) { + private void SetupNoRandPartA() + { + if (i2 <= last) + { chPrev = ch2; ch2 = ll8[tPos]; tPos = tt[tPos]; i2++; - currentChar = ch2; + currentByte = ch2; currentState = NO_RAND_PART_B_STATE; - mCrc.UpdateCRC((byte)ch2); - } else { + m_blockCrc.Update((byte)ch2); + } + else + { EndBlock(); - InitBlock(); - SetupBlock(); + BeginBlock(); } } - private void SetupRandPartB() { - if (ch2 != chPrev) { - currentState = RAND_PART_A_STATE; + private void SetupRandPartB() + { + if (ch2 != chPrev) + { count = 1; SetupRandPartA(); - } else { - count++; - if (count >= 4) { - z = ll8[tPos]; - tPos = tt[tPos]; - if (rNToGo == 0) { - rNToGo = BZip2Constants.rNums[rTPos]; - rTPos++; - if (rTPos == 512) { - rTPos = 0; - } - } - rNToGo--; - z ^= (char)((rNToGo == 1) ? 1 : 0); - j2 = 0; - currentState = RAND_PART_C_STATE; - SetupRandPartC(); - } else { - currentState = RAND_PART_A_STATE; - SetupRandPartA(); - } } - } - - private void SetupRandPartC() { - if (j2 < z) { - currentChar = ch2; - mCrc.UpdateCRC((byte)ch2); - j2++; - } else { - currentState = RAND_PART_A_STATE; - i2++; - count = 0; + else if (++count < 4) + { SetupRandPartA(); } + else + { + z = ll8[tPos]; + tPos = tt[tPos]; + if (rNToGo == 0) + { + rNToGo = CBZip2OutputStream.RNums[rTPos++]; + rTPos &= 0x1FF; + } + rNToGo--; + z ^= rNToGo == 1 ? 1 : 0; + j2 = 0; + currentState = RAND_PART_C_STATE; + SetupRandPartC(); + } } - private void SetupNoRandPartB() { - if (ch2 != chPrev) { - currentState = NO_RAND_PART_A_STATE; + private void SetupNoRandPartB() + { + if (ch2 != chPrev) + { count = 1; SetupNoRandPartA(); - } else { - count++; - if (count >= 4) { - z = ll8[tPos]; - tPos = tt[tPos]; - currentState = NO_RAND_PART_C_STATE; - j2 = 0; - SetupNoRandPartC(); - } else { - currentState = NO_RAND_PART_A_STATE; - SetupNoRandPartA(); - } + } + else if (++count < 4) + { + SetupNoRandPartA(); + } + else + { + z = ll8[tPos]; + tPos = tt[tPos]; + currentState = NO_RAND_PART_C_STATE; + j2 = 0; + SetupNoRandPartC(); } } - private void SetupNoRandPartC() { - if (j2 < z) { - currentChar = ch2; - mCrc.UpdateCRC((byte)ch2); + private void SetupRandPartC() + { + if (j2 < z) + { + currentByte = ch2; + m_blockCrc.Update((byte)ch2); j2++; - } else { - currentState = NO_RAND_PART_A_STATE; + } + else + { i2++; count = 0; - SetupNoRandPartA(); + SetupRandPartA(); } } - private void SetDecompressStructureSizes(int newSize100k) { - if (!(0 <= newSize100k && newSize100k <= 9 && 0 <= blockSize100k - && blockSize100k <= 9)) { - // throw new IOException("Invalid block size"); + private void SetupNoRandPartC() + { + if (j2 < z) + { + currentByte = ch2; + m_blockCrc.Update((byte)ch2); + j2++; } - - blockSize100k = newSize100k; - - if (newSize100k == 0) { - return; + else + { + i2++; + count = 0; + SetupNoRandPartA(); } + } - int n = BZip2Constants.baseBlockSize * newSize100k; - ll8 = new char[n]; - tt = new int[n]; + internal static int[][] CreateIntArray(int n1, int n2) + { + int[][] a = new int[n1][]; + for (int k = 0; k < n1; ++k) + { + a[k] = new int[n2]; + } + return a; } } } diff --git a/crypto/bzip2/src/CBZip2OutputStream.cs b/crypto/bzip2/src/CBZip2OutputStream.cs index 307f59cd0..156c32e3e 100644 --- a/crypto/bzip2/src/CBZip2OutputStream.cs +++ b/crypto/bzip2/src/CBZip2OutputStream.cs @@ -24,6 +24,7 @@ using System; using System.Collections; +using System.Diagnostics; using System.IO; using Org.BouncyCastle.Utilities; @@ -51,27 +52,33 @@ namespace Org.BouncyCastle.Apache.Bzip2 protected const int SMALL_THRESH = 20; protected const int DEPTH_THRESH = 10; - private bool finished; - - private static void Panic() - { - throw new InvalidOperationException(); - } + internal static readonly ushort[] RNums = { + 619, 720, 127, 481, 931, 816, 813, 233, 566, 247, 985, 724, 205, 454, 863, 491, 741, 242, 949, 214, 733, + 859, 335, 708, 621, 574, 73, 654, 730, 472, 419, 436, 278, 496, 867, 210, 399, 680, 480, 51, 878, 465, 811, + 169, 869, 675, 611, 697, 867, 561, 862, 687, 507, 283, 482, 129, 807, 591, 733, 623, 150, 238, 59, 379, 684, + 877, 625, 169, 643, 105, 170, 607, 520, 932, 727, 476, 693, 425, 174, 647, 73, 122, 335, 530, 442, 853, 695, + 249, 445, 515, 909, 545, 703, 919, 874, 474, 882, 500, 594, 612, 641, 801, 220, 162, 819, 984, 589, 513, + 495, 799, 161, 604, 958, 533, 221, 400, 386, 867, 600, 782, 382, 596, 414, 171, 516, 375, 682, 485, 911, + 276, 98, 553, 163, 354, 666, 933, 424, 341, 533, 870, 227, 730, 475, 186, 263, 647, 537, 686, 600, 224, 469, + 68, 770, 919, 190, 373, 294, 822, 808, 206, 184, 943, 795, 384, 383, 461, 404, 758, 839, 887, 715, 67, 618, + 276, 204, 918, 873, 777, 604, 560, 951, 160, 578, 722, 79, 804, 96, 409, 713, 940, 652, 934, 970, 447, 318, + 353, 859, 672, 112, 785, 645, 863, 803, 350, 139, 93, 354, 99, 820, 908, 609, 772, 154, 274, 580, 184, 79, + 626, 630, 742, 653, 282, 762, 623, 680, 81, 927, 626, 789, 125, 411, 521, 938, 300, 821, 78, 343, 175, 128, + 250, 170, 774, 972, 275, 999, 639, 495, 78, 352, 126, 857, 956, 358, 619, 580, 124, 737, 594, 701, 612, 669, + 112, 134, 694, 363, 992, 809, 743, 168, 974, 944, 375, 748, 52, 600, 747, 642, 182, 862, 81, 344, 805, 988, + 739, 511, 655, 814, 334, 249, 515, 897, 955, 664, 981, 649, 113, 974, 459, 893, 228, 433, 837, 553, 268, + 926, 240, 102, 654, 459, 51, 686, 754, 806, 760, 493, 403, 415, 394, 687, 700, 946, 670, 656, 610, 738, 392, + 760, 799, 887, 653, 978, 321, 576, 617, 626, 502, 894, 679, 243, 440, 680, 879, 194, 572, 640, 724, 926, 56, + 204, 700, 707, 151, 457, 449, 797, 195, 791, 558, 945, 679, 297, 59, 87, 824, 713, 663, 412, 693, 342, 606, + 134, 108, 571, 364, 631, 212, 174, 643, 304, 329, 343, 97, 430, 751, 497, 314, 983, 374, 822, 928, 140, 206, + 73, 263, 980, 736, 876, 478, 430, 305, 170, 514, 364, 692, 829, 82, 855, 953, 676, 246, 369, 970, 294, 750, + 807, 827, 150, 790, 288, 923, 804, 378, 215, 828, 592, 281, 565, 555, 710, 82, 896, 831, 547, 261, 524, 462, + 293, 465, 502, 56, 661, 821, 976, 991, 658, 869, 905, 758, 745, 193, 768, 550, 608, 933, 378, 286, 215, 979, + 792, 961, 61, 688, 793, 644, 986, 403, 106, 366, 905, 644, 372, 567, 466, 434, 645, 210, 389, 550, 919, 135, + 780, 773, 635, 389, 707, 100, 626, 958, 165, 504, 920, 176, 193, 713, 857, 265, 203, 50, 668, 108, 645, 990, + 626, 197, 510, 357, 358, 850, 858, 364, 936, 638 }; - private void MakeMaps() - { - int i; - nInUse = 0; - for (i = 0; i < 256; i++) - { - if (inUse[i]) - { - seqToUnseq[nInUse] = (byte)i; - unseqToSeq[i] = (byte)nInUse; - nInUse++; - } - } - } + private bool finished; protected static void HbMakeCodeLengths(byte[] len, int[] freq, int alphaSize, int maxLen) { @@ -113,9 +120,7 @@ namespace Org.BouncyCastle.Apache.Bzip2 } } if (!(nHeap < (BZip2Constants.MAX_ALPHA_SIZE + 2))) - { - Panic(); - } + throw new InvalidOperationException(); while (nHeap > 1) { @@ -124,7 +129,8 @@ namespace Org.BouncyCastle.Apache.Bzip2 { int zz = 1; int tmp = heap[zz]; - while (true) { + while (true) + { int yy = zz << 1; if (yy > nHeap) break; @@ -192,11 +198,10 @@ namespace Org.BouncyCastle.Apache.Bzip2 } } if (!(nNodes < (BZip2Constants.MAX_ALPHA_SIZE * 2))) - { - Panic(); - } + throw new InvalidOperationException(); - bool tooLong = false; + //bool tooLong = false; + int tooLongBits = 0; for (int i = 1; i <= alphaSize; i++) { int j = 0; @@ -207,16 +212,15 @@ namespace Org.BouncyCastle.Apache.Bzip2 j++; } len[i - 1] = (byte)j; - if (j > maxLen) - { - tooLong = true; - } + //tooLong |= j > maxLen; + tooLongBits |= maxLen - j; } - if (!tooLong) + //if (!tooLong) + if (tooLongBits >= 0) break; - for (int i = 1; i < alphaSize; i++) + for (int i = 1; i <= alphaSize; i++) { int j = weight[i] >> 8; j = 1 + (j / 2); @@ -239,24 +243,22 @@ namespace Org.BouncyCastle.Apache.Bzip2 always: in the range 0 .. 9. The current block size is 100000 * this number. */ - readonly int blockSize100k; - - private int allowableBlockSize; + private readonly int blockSize100k; + private readonly int allowableBlockSize; bool blockRandomised; + IList blocksortStack = Platform.CreateArrayList(); int bsBuff; - int bsLive; - readonly CRC mCrc = new CRC(); + int bsLivePos; + private readonly CRC m_blockCrc = new CRC(); private bool[] inUse = new bool[256]; private int nInUse; - private byte[] seqToUnseq = new byte[256]; private byte[] unseqToSeq = new byte[256]; - private char[] selector = new char[BZip2Constants.MAX_SELECTORS]; - private char[] selectorMtf = new char[BZip2Constants.MAX_SELECTORS]; + private byte[] m_selectors = new byte[BZip2Constants.MAX_SELECTORS]; private byte[] blockBytes; private ushort[] quadrantShorts; @@ -280,6 +282,7 @@ namespace Org.BouncyCastle.Apache.Bzip2 private int currentByte = -1; private int runLength = 0; + private int m_streamCrc; public CBZip2OutputStream(Stream outStream) : this(outStream, 9) @@ -296,18 +299,49 @@ namespace Org.BouncyCastle.Apache.Bzip2 outStream.WriteByte((byte)'B'); outStream.WriteByte((byte)'Z'); - BsSetStream(outStream); + bsStream = outStream; + bsBuff = 0; + bsLivePos = 32; workFactor = 50; - if (blockSize > 9) { + if (blockSize > 9) + { blockSize = 9; } - if (blockSize < 1) { + else if (blockSize < 1) + { blockSize = 1; } blockSize100k = blockSize; - AllocateCompressStructures(); - Initialize(); + + /* 20 is just a paranoia constant */ + allowableBlockSize = BZip2Constants.baseBlockSize * blockSize100k - 20; + + int n = BZip2Constants.baseBlockSize * blockSize100k; + blockBytes = new byte[(n + 1 + BZip2Constants.NUM_OVERSHOOT_BYTES)]; + quadrantShorts = new ushort[(n + 1 + BZip2Constants.NUM_OVERSHOOT_BYTES)]; + zptr = new int[n]; + ftab = new int[65537]; + + /* + The back end needs a place to store the MTF values + whilst it calculates the coding tables. We could + put them in the zptr array. However, these values + will fit in a short, so we overlay szptr at the + start of zptr, in the hope of reducing the number + of cache misses induced by the multiple traversals + of the MTF values when calculating coding tables. + Seems to improve compression speed by about 1%. + */ + // NOTE: We can't "overlay" in C#, so we just share zptr + szptr = zptr; + + // Write `magic' bytes h indicating file-format == huffmanised, followed by a digit indicating blockSize100k + outStream.WriteByte((byte)'h'); + outStream.WriteByte((byte)('0' + blockSize100k)); + + m_streamCrc = 0; + InitBlock(); } @@ -320,25 +354,22 @@ namespace Org.BouncyCastle.Apache.Bzip2 { if (currentByte == value) { - runLength++; - if (runLength > 254) + if (++runLength > 254) { WriteRun(); currentByte = -1; runLength = 0; } + return; } - else if (currentByte == -1) - { - currentByte = value; - runLength++; - } - else + + if (currentByte >= 0) { WriteRun(); - runLength = 1; - currentByte = value; } + + currentByte = value; + runLength = 1; } private void WriteRun() @@ -351,39 +382,42 @@ namespace Org.BouncyCastle.Apache.Bzip2 inUse[currentByte] = true; - for (int i = 0; i < runLength; i++) - { - mCrc.UpdateCRC((byte)currentByte); - } - switch (runLength) { case 1: blockBytes[++count] = (byte)currentByte; + m_blockCrc.Update((byte)currentByte); break; case 2: blockBytes[++count] = (byte)currentByte; blockBytes[++count] = (byte)currentByte; + m_blockCrc.Update((byte)currentByte); + m_blockCrc.Update((byte)currentByte); break; case 3: blockBytes[++count] = (byte)currentByte; blockBytes[++count] = (byte)currentByte; blockBytes[++count] = (byte)currentByte; + m_blockCrc.Update((byte)currentByte); + m_blockCrc.Update((byte)currentByte); + m_blockCrc.Update((byte)currentByte); break; default: - inUse[runLength - 4] = true; blockBytes[++count] = (byte)currentByte; blockBytes[++count] = (byte)currentByte; blockBytes[++count] = (byte)currentByte; blockBytes[++count] = (byte)currentByte; blockBytes[++count] = (byte)(runLength - 4); + inUse[runLength - 4] = true; + m_blockCrc.UpdateRun((byte)currentByte, runLength); break; } } bool closed = false; -// protected void Finalize() { +// protected void Finalize() +// { // Close(); // } @@ -440,37 +474,21 @@ namespace Org.BouncyCastle.Apache.Bzip2 bsStream.Flush(); } - private int combinedCRC; - - private void Initialize() - { - /* Write `magic' bytes h indicating file-format == huffmanised, - followed by a digit indicating blockSize100k. - */ - BsPutUChar('h'); - BsPutUChar('0' + blockSize100k); - - combinedCRC = 0; - } - private void InitBlock() { - mCrc.InitialiseCRC(); + m_blockCrc.Initialise(); count = 0; for (int i = 0; i < 256; i++) { inUse[i] = false; } - - /* 20 is just a paranoia constant */ - allowableBlockSize = BZip2Constants.baseBlockSize * blockSize100k - 20; } private void EndBlock() { - int blockCRC = mCrc.GetFinalCRC(); - combinedCRC = Integers.RotateLeft(combinedCRC, 1) ^ blockCRC; + int blockFinalCrc = m_blockCrc.GetFinal(); + m_streamCrc = Integers.RotateLeft(m_streamCrc, 1) ^ blockFinalCrc; /* sort the block and establish posn of original string */ DoReversibleTransformation(); @@ -488,24 +506,20 @@ namespace Org.BouncyCastle.Apache.Bzip2 They are only important when trying to recover blocks from damaged files. */ - BsPutUChar(0x31); - BsPutUChar(0x41); - BsPutUChar(0x59); - BsPutUChar(0x26); - BsPutUChar(0x53); - BsPutUChar(0x59); + BsPutLong48(0x314159265359L); /* Now the block's CRC, so it is in a known place. */ - BsPutint(blockCRC); + BsPutInt32(blockFinalCrc); /* Now a single bit indicating randomisation. */ - BsW(1, blockRandomised ? 1 : 0); + BsPutBit(blockRandomised ? 1 : 0); /* Finally, block's contents proper. */ MoveToFrontCodeAndSend(); } - private void EndCompression() { + private void EndCompression() + { /* Now another magic 48-bit number, 0x177245385090, to indicate the end of the last block. (Sqrt(pi), if @@ -513,14 +527,9 @@ namespace Org.BouncyCastle.Apache.Bzip2 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); + BsPutLong48(0x177245385090L); - BsPutint(combinedCRC); + BsPutInt32(m_streamCrc); BsFinishedWithStream(); } @@ -534,72 +543,85 @@ namespace Org.BouncyCastle.Apache.Bzip2 { if (length[i] == n) { - code[i] = vec; - vec++; + code[i] = vec++; } } vec <<= 1; } } - private void BsSetStream(Stream f) + private void BsFinishedWithStream() { - bsStream = f; - bsLive = 0; - bsBuff = 0; + if (bsLivePos < 32) + { + bsStream.WriteByte((byte)(bsBuff >> 24)); + bsBuff = 0; + bsLivePos = 32; + } } - private void BsFinishedWithStream() + private void BsPutBit(int v) { - while (bsLive > 0) + --bsLivePos; + bsBuff |= v << bsLivePos; + + if (bsLivePos <= 24) { - bsStream.WriteByte((byte)(bsBuff >> 24)); // write 8-bit + bsStream.WriteByte((byte)(bsBuff >> 24)); bsBuff <<= 8; - bsLive -= 8; + bsLivePos += 8; } } - private void BsW(int n, int v) + private void BsPutBits(int n, int v) { - while (bsLive >= 8) + Debug.Assert(1 <= n && n <= 24); + + bsLivePos -= n; + bsBuff |= v << bsLivePos; + + while (bsLivePos <= 24) { - bsStream.WriteByte((byte)(bsBuff >> 24)); // write 8-bit + bsStream.WriteByte((byte)(bsBuff >> 24)); bsBuff <<= 8; - bsLive -= 8; + bsLivePos += 8; } - bsBuff |= v << (32 - bsLive - n); - bsLive += n; } - private void BsPutUChar(int c) + private void BsPutBitsSmall(int n, int v) { - BsW(8, c); + Debug.Assert(1 <= n && n <= 8); + + bsLivePos -= n; + bsBuff |= v << bsLivePos; + + if (bsLivePos <= 24) + { + bsStream.WriteByte((byte)(bsBuff >> 24)); + bsBuff <<= 8; + bsLivePos += 8; + } } - private void BsPutint(int u) + private void BsPutInt32(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); + BsPutBits(16, (u >> 16) & 0xFFFF); + BsPutBits(16, u & 0xFFFF); } - private void BsPutIntVS(int numBits, int c) + private void BsPutLong48(long u) { - BsW(numBits, c); + BsPutBits(24, (int)(u >> 24) & 0xFFFFFF); + BsPutBits(24, (int)u & 0xFFFFFF); } - private void SendMTFValues() + private void SendMtfValues() { - byte[][] len = CBZip2InputStream.InitByteArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE); + byte[][] len = 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; + int v, t, i, j, bt, bc, iter; - alphaSize = nInUse + 2; + int alphaSize = nInUse + 2; for (t = 0; t < BZip2Constants.N_GROUPS; t++) { byte[] len_t = len[t]; @@ -611,10 +633,9 @@ namespace Org.BouncyCastle.Apache.Bzip2 /* Decide how many coding tables to use */ if (nMTF <= 0) - { - Panic(); - } + throw new InvalidOperationException(); + int nGroups; if (nMTF < 200) { nGroups = 2; @@ -638,16 +659,13 @@ namespace Org.BouncyCastle.Apache.Bzip2 /* Generate an initial set of coding tables */ { - int tFreq, aFreq; - int nPart = nGroups; - int remF = nMTF; - gs = 0; + int remF = nMTF; + int ge = -1; while (nPart > 0) { - tFreq = remF / nPart; - ge = gs - 1; - aFreq = 0; + int gs = ge + 1; + int aFreq = 0, tFreq = remF / nPart; while (aFreq < tFreq && ge < alphaSize - 1) { aFreq += mtfFreq[++ge]; @@ -673,12 +691,11 @@ namespace Org.BouncyCastle.Apache.Bzip2 } nPart--; - gs = ge + 1; remF -= aFreq; } } - int[][] rfreq = CBZip2InputStream.InitIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE); + int[][] rfreq = CBZip2InputStream.CreateIntArray(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]; @@ -688,9 +705,8 @@ namespace Org.BouncyCastle.Apache.Bzip2 byte[] len_4 = len[4]; byte[] len_5 = len[5]; - /* - Iterate up to N_ITERS times to improve the tables. - */ + // Iterate up to N_ITERS times to improve the tables. + int nSelectors = 0; for (iter = 0; iter < BZip2Constants.N_ITERS; iter++) { for (t = 0; t < nGroups; t++) @@ -705,7 +721,7 @@ namespace Org.BouncyCastle.Apache.Bzip2 } nSelectors = 0; - gs = 0; + int gs = 0; while (gs < nMTF) { /* Set group start & end marks. */ @@ -714,7 +730,7 @@ namespace Org.BouncyCastle.Apache.Bzip2 * 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); + int ge = System.Math.Min(gs + BZip2Constants.G_SIZE - 1, nMTF - 1); if (nGroups == 6) { @@ -759,18 +775,19 @@ namespace Org.BouncyCastle.Apache.Bzip2 Find the coding table which is best for this group, and record its identity in the selector table. */ - bc = 999999999; - bt = -1; - for (t = 0; t < nGroups; t++) + bc = cost[0]; + bt = 0; + for (t = 1; t < nGroups; t++) { - if (cost[t] < bc) + short cost_t = cost[t]; + if (cost_t < bc) { - bc = cost[t]; + bc = cost_t; bt = t; } } fave[bt]++; - selector[nSelectors] = (char) bt; + m_selectors[nSelectors] = (byte)bt; nSelectors++; /* @@ -790,77 +807,32 @@ namespace Org.BouncyCastle.Apache.Bzip2 */ for (t = 0; t < nGroups; t++) { - HbMakeCodeLengths(len[t], rfreq[t], alphaSize, 20); + HbMakeCodeLengths(len[t], rfreq[t], alphaSize, BZip2Constants.MAX_CODE_LEN_GEN); } } - rfreq = null; - fave = null; - cost = null; + if (nGroups >= 8 || nGroups > BZip2Constants.N_GROUPS) + throw new InvalidOperationException(); + if (nSelectors >= 32768 || nSelectors > BZip2Constants.MAX_SELECTORS) + throw new InvalidOperationException(); - 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 (i = 0; i < nGroups; i++) - { - pos[i] = (char)i; - } - for (i = 0; i < nSelectors; i++) - { - ll_i = selector[i]; - 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 = CBZip2InputStream.InitIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE); + int[][] code = CBZip2InputStream.CreateIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE); /* Assign actual codes for the tables. */ for (t = 0; t < nGroups; t++) { - minLen = 32; - maxLen = 0; + int maxLen = 0, minLen = 32; byte[] len_t = len[t]; for (i = 0; i < alphaSize; i++) { int lti = len_t[i]; - if (lti > maxLen) - { - maxLen = lti; - } - if (lti < minLen) - { - minLen = lti; - } - } - if (maxLen > 20) - { - Panic(); + maxLen = System.Math.Max(maxLen, lti); + minLen = System.Math.Min(minLen, lti); } - if (minLen < 1) - { - Panic(); - } - HbAssignCodes(code[t], len[t], minLen, maxLen, alphaSize); + if (minLen < 1 | maxLen > BZip2Constants.MAX_CODE_LEN_GEN) + throw new InvalidOperationException(); + + HbAssignCodes(code[t], len_t, minLen, maxLen, alphaSize); } /* Transmit the mapping table. */ @@ -882,7 +854,7 @@ namespace Org.BouncyCastle.Apache.Bzip2 for (i = 0; i < 16; i++) { - BsW(1, inUse16[i] ? 1 : 0); + BsPutBit(inUse16[i] ? 1 : 0); } for (i = 0; i < 16; i++) @@ -892,29 +864,38 @@ namespace Org.BouncyCastle.Apache.Bzip2 int i16 = i * 16; for (j = 0; j < 16; j++) { - BsW(1, inUse[i16 + j] ? 1 : 0); + BsPutBit(inUse[i16 + j] ? 1 : 0); } } } } /* Now the selectors. */ - BsW(3, nGroups); - BsW(15, nSelectors); - for (i = 0; i < nSelectors; i++) + BsPutBitsSmall(3, nGroups); + BsPutBits(15, nSelectors); { - int count = selectorMtf[i]; - //for (j = 0; j < count; j++) - //{ - // BsW(1, 1); - //} - //BsW(1, 0); - while (count >= 24) + byte[] pos = new byte[BZip2Constants.N_GROUPS]; + for (i = 0; i < nGroups; i++) { - BsW(24, 0xFFFFFF); - count -= 24; + pos[i] = (byte)i; + } + + for (i = 0; i < nSelectors; i++) + { + // Compute MTF values for the selector. + byte ll_i = m_selectors[i]; + int mtfSelector = 1; + byte tmp = pos[0]; + while (ll_i != tmp) + { + byte tmp2 = tmp; + tmp = pos[mtfSelector]; + pos[mtfSelector++] = tmp2; + } + pos[0] = tmp; + + BsPutBitsSmall(mtfSelector, (1 << mtfSelector) - 2); } - BsW(count + 1, (1 << (count + 1)) - 2); } /* Now the coding tables. */ @@ -922,55 +903,55 @@ namespace Org.BouncyCastle.Apache.Bzip2 { byte[] len_t = len[t]; int curr = len_t[0]; - BsW(5, curr); - for (i = 0; i < alphaSize; i++) + BsPutBitsSmall(6, curr << 1); + for (i = 1; i < alphaSize; i++) { int lti = len_t[i]; while (curr < lti) { - BsW(2, 2); + BsPutBitsSmall(2, 2); curr++; /* 10 */ } while (curr > lti) { - BsW(2, 3); + BsPutBitsSmall(2, 3); curr--; /* 11 */ } - BsW(1, 0); + BsPutBit(0); } } /* And finally, the block data proper */ - selCtr = 0; - gs = 0; - while (gs < nMTF) { - ge = System.Math.Min(gs + BZip2Constants.G_SIZE - 1, nMTF - 1); + int selCtr = 0; + int gs = 0; + while (gs < nMTF) + { + int 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]; + int selector_selCtr = m_selectors[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]); - } + for (i = gs; i <= ge; i++) + { + int sfmap_i = szptr[i]; + BsPutBits(len_selCtr[sfmap_i], code_selCtr[sfmap_i]); + } - gs = ge + 1; - selCtr++; - } - if (!(selCtr == nSelectors)) - { - Panic(); + gs = ge + 1; + selCtr++; + } + if (selCtr != nSelectors) + throw new InvalidOperationException(); } } private void MoveToFrontCodeAndSend() { - BsPutIntVS(24, origPtr); - GenerateMTFValues(); - SendMTFValues(); + BsPutBits(24, origPtr); + GenerateMtfValues(); + SendMtfValues(); } private Stream bsStream; @@ -1092,7 +1073,7 @@ namespace Org.BouncyCastle.Apache.Bzip2 { int unLo, unHi, ltLo, gtHi, n, m; - IList stack = Platform.CreateArrayList(); + IList stack = blocksortStack; int stackCount = 0; StackElem stackElem; @@ -1367,9 +1348,7 @@ namespace Org.BouncyCastle.Apache.Bzip2 } if (!(((bbSize - 1) >> shifts) <= 65535)) - { - Panic(); - } + throw new InvalidOperationException(); } /* @@ -1408,24 +1387,19 @@ namespace Org.BouncyCastle.Apache.Bzip2 inUse[i] = false; } - int rNToGo = 0; - int rTPos = 0; + int rNToGo = 0, rTPos = 0; - for (int i = 0; i < count; i++) + for (int i = 1; i <= count; i++) { if (rNToGo == 0) { - rNToGo = BZip2Constants.rNums[rTPos]; - - if (++rTPos == 512) - { - rTPos = 0; - } + rNToGo = RNums[rTPos++]; + rTPos &= 0x1FF; } rNToGo--; - blockBytes[i + 1] ^= (byte)((rNToGo == 1) ? 1 : 0); + blockBytes[i] ^= (byte)(rNToGo == 1 ? 1 : 0); - inUse[blockBytes[i + 1]] = true; + inUse[blockBytes[i]] = true; } } @@ -1458,9 +1432,7 @@ namespace Org.BouncyCastle.Apache.Bzip2 } if (origPtr == -1) - { - Panic(); - } + throw new InvalidOperationException(); } private bool FullGtU(int i1, int i2) @@ -1568,29 +1540,7 @@ namespace Org.BouncyCastle.Apache.Bzip2 private static readonly int[] incs = { 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484 }; - private void AllocateCompressStructures() - { - int n = BZip2Constants.baseBlockSize * blockSize100k; - blockBytes = new byte[(n + 1 + BZip2Constants.NUM_OVERSHOOT_BYTES)]; - quadrantShorts = new ushort[(n + 1 + BZip2Constants.NUM_OVERSHOOT_BYTES)]; - zptr = new int[n]; - ftab = new int[65537]; - - /* - The back end needs a place to store the MTF values - whilst it calculates the coding tables. We could - put them in the zptr array. However, these values - will fit in a short, so we overlay szptr at the - start of zptr, in the hope of reducing the number - of cache misses induced by the multiple traversals - of the MTF values when calculating coding tables. - Seems to improve compression speed by about 1%. - */ - // NOTE: We can't "overlay" in C#, so we just share zptr - szptr = zptr; - } - - private void GenerateMTFValues() + private void GenerateMtfValues() { byte[] yy = new byte[256]; int i, j; @@ -1598,7 +1548,16 @@ namespace Org.BouncyCastle.Apache.Bzip2 int wr; int EOB; - MakeMaps(); + nInUse = 0; + + for (i = 0; i < 256; i++) + { + if (inUse[i]) + { + unseqToSeq[i] = (byte)nInUse++; + } + } + EOB = nInUse + 1; for (i = 0; i <= EOB; i++) @@ -1679,5 +1638,15 @@ namespace Org.BouncyCastle.Apache.Bzip2 nMTF = wr; } + + internal static byte[][] InitByteArray(int n1, int n2) + { + byte[][] a = new byte[n1][]; + for (int k = 0; k < n1; ++k) + { + a[k] = new byte[n2]; + } + return a; + } } } diff --git a/crypto/bzip2/src/CRC.cs b/crypto/bzip2/src/CRC.cs index ac2db776a..a66340e22 100644 --- a/crypto/bzip2/src/CRC.cs +++ b/crypto/bzip2/src/CRC.cs @@ -23,6 +23,9 @@ */ using System; +using System.Diagnostics; + +using Org.BouncyCastle.Utilities; namespace Org.BouncyCastle.Apache.Bzip2 { @@ -34,94 +37,125 @@ namespace Org.BouncyCastle.Apache.Bzip2 */ internal class CRC { + // Values are byte-reversed private static readonly uint[] Crc32Table = { - 0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9, - 0x130476dc, 0x17c56b6b, 0x1a864db2, 0x1e475005, - 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61, - 0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd, - 0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9, - 0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75, - 0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011, - 0x791d4014, 0x7ddc5da3, 0x709f7b7a, 0x745e66cd, - 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039, - 0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5, - 0xbe2b5b58, 0xbaea46ef, 0xb7a96036, 0xb3687d81, - 0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d, - 0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49, - 0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95, - 0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1, - 0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d, - 0x34867077, 0x30476dc0, 0x3d044b19, 0x39c556ae, - 0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072, - 0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16, - 0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca, - 0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde, - 0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02, - 0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1, 0x53dc6066, - 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba, - 0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e, - 0xbfa1b04b, 0xbb60adfc, 0xb6238b25, 0xb2e29692, - 0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6, - 0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a, - 0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e, - 0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2, - 0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686, - 0xd5b88683, 0xd1799b34, 0xdc3abded, 0xd8fba05a, - 0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637, - 0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb, - 0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f, - 0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53, - 0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47, - 0x36194d42, 0x32d850f5, 0x3f9b762c, 0x3b5a6b9b, - 0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff, - 0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623, - 0xf12f560e, 0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7, - 0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b, - 0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f, - 0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3, - 0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7, - 0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b, - 0x9b3660c6, 0x9ff77d71, 0x92b45ba8, 0x9675461f, - 0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3, - 0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640, - 0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c, - 0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8, - 0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24, - 0x119b4be9, 0x155a565e, 0x18197087, 0x1cd86d30, - 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec, - 0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088, - 0x2497d08d, 0x2056cd3a, 0x2d15ebe3, 0x29d4f654, - 0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0, - 0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c, - 0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18, - 0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4, - 0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0, - 0x9abc8bd5, 0x9e7d9662, 0x933eb0bb, 0x97ffad0c, - 0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668, - 0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4 + 0x00000000, 0xB71DC104, 0x6E3B8209, 0xD926430D, + 0xDC760413, 0x6B6BC517, 0xB24D861A, 0x0550471E, + 0xB8ED0826, 0x0FF0C922, 0xD6D68A2F, 0x61CB4B2B, + 0x649B0C35, 0xD386CD31, 0x0AA08E3C, 0xBDBD4F38, + 0x70DB114C, 0xC7C6D048, 0x1EE09345, 0xA9FD5241, + 0xACAD155F, 0x1BB0D45B, 0xC2969756, 0x758B5652, + 0xC836196A, 0x7F2BD86E, 0xA60D9B63, 0x11105A67, + 0x14401D79, 0xA35DDC7D, 0x7A7B9F70, 0xCD665E74, + 0xE0B62398, 0x57ABE29C, 0x8E8DA191, 0x39906095, + 0x3CC0278B, 0x8BDDE68F, 0x52FBA582, 0xE5E66486, + 0x585B2BBE, 0xEF46EABA, 0x3660A9B7, 0x817D68B3, + 0x842D2FAD, 0x3330EEA9, 0xEA16ADA4, 0x5D0B6CA0, + 0x906D32D4, 0x2770F3D0, 0xFE56B0DD, 0x494B71D9, + 0x4C1B36C7, 0xFB06F7C3, 0x2220B4CE, 0x953D75CA, + 0x28803AF2, 0x9F9DFBF6, 0x46BBB8FB, 0xF1A679FF, + 0xF4F63EE1, 0x43EBFFE5, 0x9ACDBCE8, 0x2DD07DEC, + 0x77708634, 0xC06D4730, 0x194B043D, 0xAE56C539, + 0xAB068227, 0x1C1B4323, 0xC53D002E, 0x7220C12A, + 0xCF9D8E12, 0x78804F16, 0xA1A60C1B, 0x16BBCD1F, + 0x13EB8A01, 0xA4F64B05, 0x7DD00808, 0xCACDC90C, + 0x07AB9778, 0xB0B6567C, 0x69901571, 0xDE8DD475, + 0xDBDD936B, 0x6CC0526F, 0xB5E61162, 0x02FBD066, + 0xBF469F5E, 0x085B5E5A, 0xD17D1D57, 0x6660DC53, + 0x63309B4D, 0xD42D5A49, 0x0D0B1944, 0xBA16D840, + 0x97C6A5AC, 0x20DB64A8, 0xF9FD27A5, 0x4EE0E6A1, + 0x4BB0A1BF, 0xFCAD60BB, 0x258B23B6, 0x9296E2B2, + 0x2F2BAD8A, 0x98366C8E, 0x41102F83, 0xF60DEE87, + 0xF35DA999, 0x4440689D, 0x9D662B90, 0x2A7BEA94, + 0xE71DB4E0, 0x500075E4, 0x892636E9, 0x3E3BF7ED, + 0x3B6BB0F3, 0x8C7671F7, 0x555032FA, 0xE24DF3FE, + 0x5FF0BCC6, 0xE8ED7DC2, 0x31CB3ECF, 0x86D6FFCB, + 0x8386B8D5, 0x349B79D1, 0xEDBD3ADC, 0x5AA0FBD8, + 0xEEE00C69, 0x59FDCD6D, 0x80DB8E60, 0x37C64F64, + 0x3296087A, 0x858BC97E, 0x5CAD8A73, 0xEBB04B77, + 0x560D044F, 0xE110C54B, 0x38368646, 0x8F2B4742, + 0x8A7B005C, 0x3D66C158, 0xE4408255, 0x535D4351, + 0x9E3B1D25, 0x2926DC21, 0xF0009F2C, 0x471D5E28, + 0x424D1936, 0xF550D832, 0x2C769B3F, 0x9B6B5A3B, + 0x26D61503, 0x91CBD407, 0x48ED970A, 0xFFF0560E, + 0xFAA01110, 0x4DBDD014, 0x949B9319, 0x2386521D, + 0x0E562FF1, 0xB94BEEF5, 0x606DADF8, 0xD7706CFC, + 0xD2202BE2, 0x653DEAE6, 0xBC1BA9EB, 0x0B0668EF, + 0xB6BB27D7, 0x01A6E6D3, 0xD880A5DE, 0x6F9D64DA, + 0x6ACD23C4, 0xDDD0E2C0, 0x04F6A1CD, 0xB3EB60C9, + 0x7E8D3EBD, 0xC990FFB9, 0x10B6BCB4, 0xA7AB7DB0, + 0xA2FB3AAE, 0x15E6FBAA, 0xCCC0B8A7, 0x7BDD79A3, + 0xC660369B, 0x717DF79F, 0xA85BB492, 0x1F467596, + 0x1A163288, 0xAD0BF38C, 0x742DB081, 0xC3307185, + 0x99908A5D, 0x2E8D4B59, 0xF7AB0854, 0x40B6C950, + 0x45E68E4E, 0xF2FB4F4A, 0x2BDD0C47, 0x9CC0CD43, + 0x217D827B, 0x9660437F, 0x4F460072, 0xF85BC176, + 0xFD0B8668, 0x4A16476C, 0x93300461, 0x242DC565, + 0xE94B9B11, 0x5E565A15, 0x87701918, 0x306DD81C, + 0x353D9F02, 0x82205E06, 0x5B061D0B, 0xEC1BDC0F, + 0x51A69337, 0xE6BB5233, 0x3F9D113E, 0x8880D03A, + 0x8DD09724, 0x3ACD5620, 0xE3EB152D, 0x54F6D429, + 0x7926A9C5, 0xCE3B68C1, 0x171D2BCC, 0xA000EAC8, + 0xA550ADD6, 0x124D6CD2, 0xCB6B2FDF, 0x7C76EEDB, + 0xC1CBA1E3, 0x76D660E7, 0xAFF023EA, 0x18EDE2EE, + 0x1DBDA5F0, 0xAAA064F4, 0x738627F9, 0xC49BE6FD, + 0x09FDB889, 0xBEE0798D, 0x67C63A80, 0xD0DBFB84, + 0xD58BBC9A, 0x62967D9E, 0xBBB03E93, 0x0CADFF97, + 0xB110B0AF, 0x060D71AB, 0xDF2B32A6, 0x6836F3A2, + 0x6D66B4BC, 0xDA7B75B8, 0x035D36B5, 0xB440F7B1, }; - private uint m_globalCrc; + private uint m_value = 0U; - internal CRC() + internal void Initialise() { - InitialiseCRC(); + m_value = 0xFFFFFFFF; } - internal void InitialiseCRC() + internal int GetFinal() { - m_globalCrc = 0xffffffff; + return (int)~Integers.ReverseBytes(m_value); } - internal int GetFinalCRC() + internal void Update(byte inCh) { - return (int)~m_globalCrc; + m_value = (m_value >> 8) ^ Crc32Table[(byte)(m_value ^ inCh)]; } - internal void UpdateCRC(byte inCh) + internal void UpdateRun(byte inCh, int runLength) { - uint index = (m_globalCrc >> 24) ^ inCh; - m_globalCrc = (m_globalCrc << 8) ^ Crc32Table[index]; + Debug.Assert(runLength >= 4); + + uint inCh2 = (uint)inCh << 8 | inCh; + uint inCh4 = inCh2 << 16 | inCh2; + + do + { + m_value ^= inCh4; + m_value = (m_value >> 8) ^ Crc32Table[(byte)m_value]; + m_value = (m_value >> 8) ^ Crc32Table[(byte)m_value]; + m_value = (m_value >> 8) ^ Crc32Table[(byte)m_value]; + m_value = (m_value >> 8) ^ Crc32Table[(byte)m_value]; + } + while ((runLength -= 4) >= 4); + + switch (runLength & 3) + { + case 0: + break; + case 1: + Update(inCh); + break; + case 2: + Update(inCh); + Update(inCh); + break; + case 3: + Update(inCh); + Update(inCh); + Update(inCh); + break; + } } } } |