// LzwInputStream.cs
//
// Copyright (C) 2009 Gabriel Burca
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
//
// Linking this library statically or dynamically with other modules is
// making a combined work based on this library. Thus, the terms and
// conditions of the GNU General Public License cover the whole
// combination.
//
// As a special exception, the copyright holders of this library give you
// permission to link this library with independent modules to produce an
// executable, regardless of the license terms of these independent
// modules, and to copy and distribute the resulting executable under
// terms of your choice, provided that you also meet, for each linked
// independent module, the terms and conditions of the license of that
// module. An independent module is a module which is not derived from
// or based on this library. If you modify this library, you may extend
// this exception to your version of the library, but you are not
// obligated to do so. If you do not wish to do so, delete this
// exception statement from your version.
using System;
using System.IO;
namespace CommonMPQ.SharpZipLib.LZW
{
/// <summary>
/// This filter stream is used to decompress a LZW format stream.
/// Specifically, a stream that uses the LZC compression method.
/// This file format is usually associated with the .Z file extension.
///
/// See http://en.wikipedia.org/wiki/Compress
/// See http://wiki.wxwidgets.org/Development:_Z_File_Format
///
/// The file header consists of 3 (or optionally 4) bytes. The first two bytes
/// contain the magic marker "0x1f 0x9d", followed by a byte of flags.
///
/// Based on Java code by Ronald Tschalar, which in turn was based on the unlzw.c
/// code in the gzip package.
/// </summary>
/// <example> This sample shows how to unzip a compressed file
/// <code>
/// using System;
/// using System.IO;
///
/// using CommonMPQ.SharpZipLib.Core;
/// using CommonMPQ.SharpZipLib.LZW;
///
/// class MainClass
/// {
/// public static void Main(string[] args)
/// {
/// using (Stream inStream = new LzwInputStream(File.OpenRead(args[0])))
/// using (FileStream outStream = File.Create(Path.GetFileNameWithoutExtension(args[0]))) {
/// byte[] buffer = new byte[4096];
/// StreamUtils.Copy(inStream, outStream, buffer);
/// // OR
/// inStream.Read(buffer, 0, buffer.Length);
/// // now do something with the buffer
/// }
/// }
/// }
/// </code>
/// </example>
public class LzwInputStream : Stream
{
/// <summary>
/// Get/set flag indicating ownership of underlying stream.
/// When the flag is true <see cref="Close"/> will close the underlying stream also.
/// </summary>
/// <remarks>
/// The default value is true.
/// </remarks>
public bool IsStreamOwner
{
get { return isStreamOwner; }
set { isStreamOwner = value; }
}
/// <summary>
/// Creates a LzwInputStream
/// </summary>
/// <param name="baseInputStream">
/// The stream to read compressed data from (baseInputStream LZW format)
/// </param>
public LzwInputStream(Stream baseInputStream) {
this.baseInputStream = baseInputStream;
}
/// <summary>
/// See <see cref="System.IO.Stream.ReadByte"/>
/// </summary>
/// <returns></returns>
public override int ReadByte() {
int b = Read(one, 0, 1);
if (b == 1)
return (one[0] & 0xff);
return -1;
}
/// <summary>
/// Reads decompressed data into the provided buffer byte array
/// </summary>
/// <param name ="buffer">
/// The array to read and decompress data into
/// </param>
/// <param name ="offset">
/// The offset indicating where the data should be placed
/// </param>
/// <param name ="count">
/// The number of bytes to decompress
/// </param>
/// <returns>The number of bytes read. Zero signals the end of stream</returns>
public override int Read(byte[] buffer, int offset, int count) {
if (!headerParsed) ParseHeader();
if (eof) return 0;
int start = offset;
/* Using local copies of various variables speeds things up by as
* much as 30% in Java! Performance not tested in C#.
*/
int[] lTabPrefix = tabPrefix;
byte[] lTabSuffix = tabSuffix;
byte[] lStack = stack;
int lNBits = nBits;
int lMaxCode = maxCode;
int lMaxMaxCode = maxMaxCode;
int lBitMask = bitMask;
int lOldCode = oldCode;
byte lFinChar = finChar;
int lStackP = stackP;
int lFreeEnt = freeEnt;
byte[] lData = data;
int lBitPos = bitPos;
// empty stack if stuff still left
int sSize = lStack.Length - lStackP;
if (sSize > 0) {
int num = (sSize >= count) ? count : sSize;
Array.Copy(lStack, lStackP, buffer, offset, num);
offset += num;
count -= num;
lStackP += num;
}
if (count == 0) {
stackP = lStackP;
return offset - start;
}
// loop, filling local buffer until enough data has been decompressed
MainLoop: do {
if (end < EXTRA) {
Fill();
}
int bitIn = (got > 0) ? (end - end % lNBits) << 3 :
(end << 3) - (lNBits - 1);
while (lBitPos < bitIn) {
#region A
// handle 1-byte reads correctly
if (count == 0) {
nBits = lNBits;
maxCode = lMaxCode;
maxMaxCode = lMaxMaxCode;
bitMask = lBitMask;
oldCode = lOldCode;
finChar = lFinChar;
stackP = lStackP;
freeEnt = lFreeEnt;
bitPos = lBitPos;
return offset - start;
}
// check for code-width expansion
if (lFreeEnt > lMaxCode) {
int nBytes = lNBits << 3;
lBitPos = (lBitPos - 1) +
nBytes - (lBitPos - 1 + nBytes) % nBytes;
lNBits++;
lMaxCode = (lNBits == maxBits) ? lMaxMaxCode :
(1 << lNBits) - 1;
lBitMask = (1 << lNBits) - 1;
lBitPos = ResetBuf(lBitPos);
goto MainLoop;
}
#endregion
#region B
// read next code
int pos = lBitPos >> 3;
int code = (((lData[pos] & 0xFF) |
((lData[pos + 1] & 0xFF) << 8) |
((lData[pos + 2] & 0xFF) << 16)) >>
(lBitPos & 0x7)) & lBitMask;
lBitPos += lNBits;
// handle first iteration
if (lOldCode == -1) {
if (code >= 256) throw new LzwException("corrupt input: " + code + " > 255");
lFinChar = (byte) (lOldCode = code);
buffer[offset++] = lFinChar;
count--;
continue;
}
// handle CLEAR code
if (code == TBL_CLEAR && blockMode) {
Array.Copy(zeros, 0, lTabPrefix, 0, zeros.Length);
lFreeEnt = TBL_FIRST - 1;
int nBytes = lNBits << 3;
lBitPos = (lBitPos - 1) + nBytes - (lBitPos - 1 + nBytes) % nBytes;
lNBits = LzwConstants.INIT_BITS;
lMaxCode = (1 << lNBits) - 1;
lBitMask = lMaxCode;
// Code tables reset
lBitPos = ResetBuf(lBitPos);
goto MainLoop;
}
#endregion
#region C
// setup
int inCode = code;
lStackP = lStack.Length;
// Handle KwK case
if (code >= lFreeEnt) {
if (code > lFreeEnt) {
throw new LzwException("corrupt input: code=" + code +
", freeEnt=" + lFreeEnt);
}
lStack[--lStackP] = lFinChar;
code = lOldCode;
}
// Generate output characters in reverse order
while (code >= 256) {
lStack[--lStackP] = lTabSuffix[code];
code = lTabPrefix[code];
}
lFinChar = lTabSuffix[code];
buffer[offset++] = lFinChar;
count--;
// And put them out in forward order
sSize = lStack.Length - lStackP;
int num = (sSize >= count) ? count : sSize;
Array.Copy(lStack, lStackP, buffer, offset, num);
offset += num;
count -= num;
lStackP += num;
#endregion
#region D
// generate new entry in table
if (lFreeEnt < lMaxMaxCode) {
lTabPrefix[lFreeEnt] = lOldCode;
lTabSuffix[lFreeEnt] = lFinChar;
lFreeEnt++;
}
// Remember previous code
lOldCode = inCode;
// if output buffer full, then return
if (count == 0) {
nBits = lNBits;
maxCode = lMaxCode;
bitMask = lBitMask;
oldCode = lOldCode;
finChar = lFinChar;
stackP = lStackP;
freeEnt = lFreeEnt;
bitPos = lBitPos;
return offset - start;
}
#endregion
} // while
lBitPos = ResetBuf(lBitPos);
} while (got > 0); // do..while
nBits = lNBits;
maxCode = lMaxCode;
bitMask = lBitMask;
oldCode = lOldCode;
finChar = lFinChar;
stackP = lStackP;
freeEnt = lFreeEnt;
bitPos = lBitPos;
eof = true;
return offset - start;
}
/// <summary>
/// Moves the unread data in the buffer to the beginning and resets
/// the pointers.
/// </summary>
/// <param name="bitPosition"></param>
/// <returns></returns>
private int ResetBuf(int bitPosition) {
int pos = bitPosition >> 3;
Array.Copy(data, pos, data, 0, end - pos);
end -= pos;
return 0;
}
private void Fill() {
got = baseInputStream.Read(data, end, data.Length - 1 - end);
if (got > 0) {
end += got;
}
}
private void ParseHeader() {
headerParsed = true;
byte[] hdr = new byte[LzwConstants.HDR_SIZE];
int result = baseInputStream.Read(hdr, 0, hdr.Length);
// Check the magic marker
if (result < 0)
throw new LzwException("Failed to read LZW header");
if (hdr[0] != (LzwConstants.MAGIC >> 8) || hdr[1] != (LzwConstants.MAGIC & 0xff)) {
throw new LzwException(String.Format(
"Wrong LZW header. Magic bytes don't match. 0x{0:x2} 0x{1:x2}",
hdr[0], hdr[1]));
}
// Check the 3rd header byte
blockMode = (hdr[2] & LzwConstants.BLOCK_MODE_MASK) > 0;
maxBits = hdr[2] & LzwConstants.BIT_MASK;
if (maxBits > LzwConstants.MAX_BITS) {
throw new LzwException("Stream compressed with " + maxBits +
" bits, but decompression can only handle " +
LzwConstants.MAX_BITS + " bits.");
}
if ((hdr[2] & LzwConstants.RESERVED_MASK) > 0) {
throw new LzwException("Unsupported bits set in the header.");
}
// Initialize variables
maxMaxCode = 1 << maxBits;
nBits = LzwConstants.INIT_BITS;
maxCode = (1 << nBits) - 1;
bitMask = maxCode;
oldCode = -1;
finChar = 0;
freeEnt = blockMode ? TBL_FIRST : 256;
tabPrefix = new int[1 << maxBits];
tabSuffix = new byte[1 << maxBits];
stack = new byte[1 << maxBits];
stackP = stack.Length;
for (int idx = 255; idx >= 0; idx--)
tabSuffix[idx] = (byte)idx;
}
#region Stream Overrides
/// <summary>
/// Gets a value indicating whether the current stream supports reading
/// </summary>
public override bool CanRead
{
get
{
return baseInputStream.CanRead;
}
}
/// <summary>
/// Gets a value of false indicating seeking is not supported for this stream.
/// </summary>
public override bool CanSeek
{
get
{
return false;
}
}
/// <summary>
/// Gets a value of false indicating that this stream is not writeable.
/// </summary>
public override bool CanWrite
{
get
{
return false;
}
}
/// <summary>
/// A value representing the length of the stream in bytes.
/// </summary>
public override long Length
{
get
{
return got;
}
}
/// <summary>
/// The current position within the stream.
/// Throws a NotSupportedException when attempting to set the position
/// </summary>
/// <exception cref="NotSupportedException">Attempting to set the position</exception>
public override long Position
{
get
{
return baseInputStream.Position;
}
set
{
throw new NotSupportedException("InflaterInputStream Position not supported");
}
}
/// <summary>
/// Flushes the baseInputStream
/// </summary>
public override void Flush()
{
baseInputStream.Flush();
}
/// <summary>
/// Sets the position within the current stream
/// Always throws a NotSupportedException
/// </summary>
/// <param name="offset">The relative offset to seek to.</param>
/// <param name="origin">The <see cref="SeekOrigin"/> defining where to seek from.</param>
/// <returns>The new position in the stream.</returns>
/// <exception cref="NotSupportedException">Any access</exception>
public override long Seek(long offset, SeekOrigin origin)
{
throw new NotSupportedException("Seek not supported");
}
/// <summary>
/// Set the length of the current stream
/// Always throws a NotSupportedException
/// </summary>
/// <param name="value">The new length value for the stream.</param>
/// <exception cref="NotSupportedException">Any access</exception>
public override void SetLength(long value)
{
throw new NotSupportedException("InflaterInputStream SetLength not supported");
}
/// <summary>
/// Writes a sequence of bytes to stream and advances the current position
/// This method always throws a NotSupportedException
/// </summary>
/// <param name="buffer">Thew buffer containing data to write.</param>
/// <param name="offset">The offset of the first byte to write.</param>
/// <param name="count">The number of bytes to write.</param>
/// <exception cref="NotSupportedException">Any access</exception>
public override void Write(byte[] buffer, int offset, int count)
{
throw new NotSupportedException("InflaterInputStream Write not supported");
}
/// <summary>
/// Writes one byte to the current stream and advances the current position
/// Always throws a NotSupportedException
/// </summary>
/// <param name="value">The byte to write.</param>
/// <exception cref="NotSupportedException">Any access</exception>
public override void WriteByte(byte value)
{
throw new NotSupportedException("InflaterInputStream WriteByte not supported");
}
/// <summary>
/// Entry point to begin an asynchronous write. Always throws a NotSupportedException.
/// </summary>
/// <param name="buffer">The buffer to write data from</param>
/// <param name="offset">Offset of first byte to write</param>
/// <param name="count">The maximum number of bytes to write</param>
/// <param name="callback">The method to be called when the asynchronous write operation is completed</param>
/// <param name="state">A user-provided object that distinguishes this particular asynchronous write request from other requests</param>
/// <returns>An <see cref="System.IAsyncResult">IAsyncResult</see> that references the asynchronous write</returns>
/// <exception cref="NotSupportedException">Any access</exception>
public override IAsyncResult BeginWrite(byte[] buffer, int offset, int count, AsyncCallback callback, object state)
{
throw new NotSupportedException("InflaterInputStream BeginWrite not supported");
}
/// <summary>
/// Closes the input stream. When <see cref="IsStreamOwner"></see>
/// is true the underlying stream is also closed.
/// </summary>
public override void Close()
{
if (!isClosed)
{
isClosed = true;
if (isStreamOwner)
{
baseInputStream.Close();
}
}
}
#endregion
#region Instance Fields
Stream baseInputStream;
/// <summary>
/// Flag indicating wether this instance is designated the stream owner.
/// When closing if this flag is true the underlying stream is closed.
/// </summary>
bool isStreamOwner = true;
/// <summary>
/// Flag indicating wether this instance has been closed or not.
/// </summary>
bool isClosed;
readonly byte[] one = new byte[1];
bool headerParsed;
// string table stuff
private const int TBL_CLEAR = 0x100;
private const int TBL_FIRST = TBL_CLEAR + 1;
private int[] tabPrefix;
private byte[] tabSuffix;
private readonly int[] zeros = new int[256];
private byte[] stack;
// various state
private bool blockMode;
private int nBits;
private int maxBits;
private int maxMaxCode;
private int maxCode;
private int bitMask;
private int oldCode;
private byte finChar;
private int stackP;
private int freeEnt;
// input buffer
private readonly byte[] data = new byte[1024 * 8];
private int bitPos;
private int end;
int got;
private bool eof;
private const int EXTRA = 64;
#endregion
}
}