diff options
Diffstat (limited to 'crypto/src/util/bzip2/CBZip2InputStream.cs')
| -rw-r--r-- | crypto/src/util/bzip2/CBZip2InputStream.cs | 809 |
1 files changed, 809 insertions, 0 deletions
diff --git a/crypto/src/util/bzip2/CBZip2InputStream.cs b/crypto/src/util/bzip2/CBZip2InputStream.cs new file mode 100644 index 000000000..7879f28af --- /dev/null +++ b/crypto/src/util/bzip2/CBZip2InputStream.cs @@ -0,0 +1,809 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + */ + +/* + * This package is based on the work done by Keiron Liddle, Aftex Software + * <keiron@aftexsw.com> to whom the Ant project is very grateful for his + * great code. + */ + +using System; +using System.Diagnostics; +using System.IO; + +using Org.BouncyCastle.Utilities.IO; + +namespace Org.BouncyCastle.Utilities.Bzip2 +{ + /** + * An input stream that decompresses from the BZip2 format (with the file + * header chars) to be read as any other stream. + * + * @author <a href="mailto:keiron@aftexsw.com">Keiron Liddle</a> + * + * <b>NB:</b> note this class has been modified to read the leading BZ from the + * start of the BZIP2 stream to make it compatible with other PGP programs. + */ + public class CBZip2InputStream + : BaseInputStream + { + /* + index of the last char in the block, so + the block size == last + 1. + */ + private int last; + + /* + index in zptr[] of original string after sorting. + */ + private int origPtr; + + /* + always: in the range 0 .. 9. + The current block size is 100000 * this number. + */ + private int blockSize100k; + + private int bsBuff; + private int bsLive; + private readonly CRC m_blockCrc = new CRC(); + + private int nInUse; + + private byte[] seqToUnseq = new byte[256]; + + private byte[] m_selectors = new byte[BZip2Constants.MAX_SELECTORS]; + + private int[] tt; + private byte[] ll8; + + /* + freq table collected to save a pass over the data + during decompression. + */ + private int[] unzftab = new int[256]; + + 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 currentByte = -1; + + 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 = 0; + + private int m_expectedBlockCrc, m_expectedStreamCrc, m_streamCrc; + + int i2, count, chPrev, ch2; + int i, tPos; + int rNToGo = 0; + int rTPos = 0; + int j2; + int z; + + public CBZip2InputStream(Stream zStream) + { + ll8 = null; + tt = null; + bsStream = zStream; + bsLive = 0; + bsBuff = 0; + + int magic1 = bsStream.ReadByte(); + int magic2 = bsStream.ReadByte(); + int version = bsStream.ReadByte(); + int level = bsStream.ReadByte(); + if (level < 0) + throw new EndOfStreamException(); + + 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) + { + Streams.ValidateBufferArguments(buffer, offset, count); + + /* + * TODO The base class implementation allows to return partial data if/when ReadByte throws. That would be + * be preferable here too (so don't override), but it would require that exceptions cause this instance to + * permanently fail, and that needs review. + */ + int pos = 0; + while (pos < count) + { + int b = ReadByte(); + if (b < 0) + break; + + buffer[offset + pos++] = (byte)b; + } + return pos; + } + + public override int ReadByte() + { + if (streamEnd) + return -1; + + int result = currentByte; + switch (currentState) + { + case RAND_PART_B_STATE: + SetupRandPartB(); + break; + case RAND_PART_C_STATE: + SetupRandPartC(); + break; + case NO_RAND_PART_B_STATE: + SetupNoRandPartB(); + break; + case NO_RAND_PART_C_STATE: + SetupNoRandPartC(); + break; + default: + throw new InvalidOperationException(); + } + return result; + } + + private void BeginBlock() + { + long magic48 = BsGetLong48(); + if (magic48 != 0x314159265359L) + { + if (magic48 != 0x177245385090L) + throw new IOException("Block header error"); + + m_expectedStreamCrc = BsGetInt32(); + if (m_expectedStreamCrc != m_streamCrc) + throw new IOException("Stream CRC error"); + + BsFinishedWithStream(); + streamEnd = true; + return; + } + + m_expectedBlockCrc = BsGetInt32(); + + bool blockRandomised = BsGetBit() == 1; + + GetAndMoveToFrontDecode(); + + m_blockCrc.Initialise(); + + int[] cftab = new int[257]; + { + 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(); + } + + for (i = 0; i <= last; i++) + { + byte ch = ll8[i]; + tt[cftab[ch]++] = i; + } + + 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 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) + { + Platform.Dispose(this.bsStream); + this.bsStream = null; + } + } + catch + { + //ignore + } + } + + private int BsGetBit() + { + if (bsLive == 0) + { + bsBuff = RequireByte(); + bsLive = 7; + return (int)((uint)bsBuff >> 7); + } + + --bsLive; + + return (bsBuff >> bsLive) & 1; + } + + private int BsGetBits(int n) + { + Debug.Assert(1 <= n && n <= 24); + + while (bsLive < n) + { + bsBuff = (bsBuff << 8) | RequireByte(); + bsLive += 8; + } + + bsLive -= n; + + return (bsBuff >> bsLive) & ((1 << n) - 1); + } + + private int BsGetBitsSmall(int n) + { + 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 BsGetInt32() + { + int u = BsGetBits(16) << 16; + return u | BsGetBits(16); + } + + private long BsGetLong48() + { + 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) + { + Array.Clear(basev, 0, basev.Length); + Array.Clear(limit, 0, limit.Length); + + int pp = 0, baseVal = 0; + for (int i = minLen; i <= maxLen; i++) + { + for (int j = 0; j < alphaSize; j++) + { + if (length[j] == i) + { + perm[pp++] = j; + } + } + basev[i] = baseVal; + limit[i] = baseVal + pp; + baseVal += baseVal + pp; + } + } + + private int RecvDecodingTables() + { + int i, j; + + nInUse = 0; + + /* Receive the mapping table */ + int inUse16 = BsGetBits(16); + + for (i = 0; i < 16; ++i) + { + if ((inUse16 & (0x8000 >> i)) != 0) + { + int inUse = BsGetBits(16); + + int i16 = i * 16; + for (j = 0; j < 16; ++j) + { + if ((inUse & (0x8000 >> j)) != 0) + { + seqToUnseq[nInUse++] = (byte)(i16 + j); + } + } + } + } + + if (nInUse < 1) + throw new InvalidOperationException(); + + int alphaSize = nInUse + 2; + + /* Now the selectors */ + int nGroups = BsGetBitsSmall(3); + if (nGroups < 2 || nGroups > BZip2Constants.N_GROUPS) + throw new InvalidOperationException(); + + int nSelectors = BsGetBits(15); + if (nSelectors < 1) + throw new InvalidOperationException(); + + uint mtfGroups = 0x00543210U; + for (i = 0; i < nSelectors; i++) + { + int mtfSelector = 0; + while (BsGetBit() == 1) + { + if (++mtfSelector >= nGroups) + throw new InvalidOperationException(); + } + + // 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 (int t = 0; t < nGroups; t++) + { + 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++) + { + int markerBit = BsGetBit(); + while (markerBit != 0) + { + 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 */ + HbCreateDecodeTables(limit[t], basev[t], perm[t], len_t, minLen, maxLen, alphaSize); + minLens[t] = minLen; + } + + return nSelectors; + } + + private void GetAndMoveToFrontDecode() + { + int i, j, nextSym; + + int limitLast = BZip2Constants.baseBlockSize * blockSize100k; + + origPtr = BsGetBits(24); + if (origPtr > 10 + limitLast) + throw new InvalidOperationException(); + + int nSelectors = RecvDecodingTables(); + + int alphaSize = nInUse + 2; + int EOB = nInUse + 1; + + /* + Setting up the unzftab entries here is not strictly + necessary, but it does save having to do it later + in a separate pass, and so saves a block's worth of + cache misses. + */ + Array.Clear(unzftab, 0, unzftab.Length); + + byte[] yy = new byte[nInUse]; + for (i = 0; i < nInUse; ++i) + { + yy[i] = seqToUnseq[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 zn = groupMinLen; + int zvec = BsGetBits(groupMinLen); + while (zvec >= groupLimits[zn]) + { + if (++zn > BZip2Constants.MAX_CODE_LEN) + throw new InvalidOperationException(); + + zvec = (zvec << 1) | BsGetBit(); + } + 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.RUNB) + { + int n = 1, s = 0; + do + { + if (n > 1024 * 1024) + throw new InvalidOperationException(); + + s += n << nextSym; + n <<= 1; + + { + if (groupPos == 0) + { + 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--; + + int zn = groupMinLen; + int zvec = BsGetBits(groupMinLen); + while (zvec >= groupLimits[zn]) + { + if (++zn > BZip2Constants.MAX_CODE_LEN) + throw new InvalidOperationException(); + + zvec = (zvec << 1) | BsGetBit(); + } + int permIndex = zvec - groupBase[zn]; + if (permIndex >= alphaSize) + throw new InvalidOperationException(); + + nextSym = groupPerm[permIndex]; + } + } + //while (nextSym == BZip2Constants.RUNA || nextSym == BZip2Constants.RUNB); + while (nextSym <= BZip2Constants.RUNB); + + byte ch = yy[0]; + unzftab[ch] += s; + + if (last >= limitLast - s) + throw new InvalidOperationException("Block overrun"); + + while (--s >= 0) + { + ll8[++last] = ch; + } + + continue; + } + else + { + if (++last >= limitLast) + throw new InvalidOperationException("Block overrun"); + + byte tmp = yy[nextSym - 1]; + unzftab[tmp]++; + ll8[last] = tmp; + + /* + * This loop is hammered during decompression, hence avoid + * native method call overhead of Array.Copy for very + * small ranges to copy. + */ + if (nextSym <= 16) + { + for (j = nextSym - 1; j > 0; --j) + { + yy[j] = yy[j - 1]; + } + } + else + { + Array.Copy(yy, 0, yy, 1, nextSym - 1); + } + + yy[0] = tmp; + + { + if (groupPos == 0) + { + 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--; + + int zn = groupMinLen; + int zvec = BsGetBits(groupMinLen); + while (zvec >= groupLimits[zn]) + { + if (++zn > BZip2Constants.MAX_CODE_LEN) + throw new InvalidOperationException(); + + zvec = (zvec << 1) | BsGetBit(); + } + int permIndex = zvec - groupBase[zn]; + if (permIndex >= alphaSize) + throw new InvalidOperationException(); + + nextSym = groupPerm[permIndex]; + } + continue; + } + } + + if (origPtr > last) + throw new InvalidOperationException(); + + // Check unzftab entries are in range. + { + int nblock = last + 1; + int check = 0; + + for (i = 0; i <= 255; i++) + { + int t = unzftab[i]; + check |= t; + check |= nblock - t; + } + if (check < 0) + throw new InvalidOperationException(); + } + } + + private int RequireByte() + { + int b = bsStream.ReadByte(); + if (b < 0) + throw new EndOfStreamException(); + return b & 0xFF; + } + + private void SetupRandPartA() + { + if (i2 <= last) + { + chPrev = ch2; + ch2 = ll8[tPos]; + tPos = tt[tPos]; + if (rNToGo == 0) + { + rNToGo = CBZip2OutputStream.RNums[rTPos++]; + rTPos &= 0x1FF; + } + rNToGo--; + ch2 ^= rNToGo == 1 ? 1 : 0; + i2++; + + currentByte = ch2; + currentState = RAND_PART_B_STATE; + m_blockCrc.Update((byte)ch2); + } + else + { + EndBlock(); + BeginBlock(); + } + } + + private void SetupNoRandPartA() + { + if (i2 <= last) + { + chPrev = ch2; + ch2 = ll8[tPos]; + tPos = tt[tPos]; + i2++; + + currentByte = ch2; + currentState = NO_RAND_PART_B_STATE; + m_blockCrc.Update((byte)ch2); + } + else + { + EndBlock(); + BeginBlock(); + } + } + + private void SetupRandPartB() + { + if (ch2 != chPrev) + { + count = 1; + SetupRandPartA(); + } + 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) + { + count = 1; + SetupNoRandPartA(); + } + else if (++count < 4) + { + SetupNoRandPartA(); + } + else + { + z = ll8[tPos]; + tPos = tt[tPos]; + currentState = NO_RAND_PART_C_STATE; + j2 = 0; + SetupNoRandPartC(); + } + } + + private void SetupRandPartC() + { + if (j2 < z) + { + currentByte = ch2; + m_blockCrc.Update((byte)ch2); + j2++; + } + else + { + i2++; + count = 0; + SetupRandPartA(); + } + } + + private void SetupNoRandPartC() + { + if (j2 < z) + { + currentByte = ch2; + m_blockCrc.Update((byte)ch2); + j2++; + } + else + { + i2++; + count = 0; + SetupNoRandPartA(); + } + } + + 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; + } + } +} |