using System;
using System.IO;
// TODO: Move to namespace Compression
namespace DCSharp.Extras{
/// <summary>
/// Class for decoding NMDC file lists (of the form MyList.DcLst).
/// Encoding is not supported.
/// </summary>
/// <remarks>
/// Written by Paul Bartrum (paulbartrum@hotmail.com)
/// </remarks>
public class NMDCHuffmanStream : Stream
{
Stream baseStream;
BitReader bitReader;
//int precomputedParity;
int calculatedParity;
int dataLength; // Uncompressed data length.
class HuffmanNode
{
public HuffmanNode Zero;
public HuffmanNode One;
public byte Symbol;
}
HuffmanNode root;
int position;
public NMDCHuffmanStream(Stream baseStream)
{
this.baseStream = baseStream;
if(baseStream.CanRead)
{
InitReader();
}
else
{
throw new NotSupportedException("This stream supports read-access only.");
}
}
void InitReader()
{
BinaryReader reader = new BinaryReader(baseStream);
// Read magic bytes "HE3" + 13
byte[] magic = reader.ReadBytes(4);
if(magic[0] != (int)'H' || magic[1] != (int)'E' || magic[2] != (int)'3' || magic[3] != 13)
{
throw new IOException("The specified stream is not HE3 (huffman) compressed.");
}
// Read checksum byte. This is a XOR of every byte in the uncompressed file.
//precomputedParity = reader.ReadByte();
// Read the length of the uncompressed file.
dataLength = reader.ReadInt32();
// Read an array of [uncompressed byte, compressed code length (in bits)].
int numCouples = reader.ReadInt16();
byte[,] couples = new byte[numCouples,2];
for(int i = 0; i < numCouples; i++)
{
couples[i, 0] = reader.ReadByte(); // Uncompressed byte (symbol).
couples[i, 1] = reader.ReadByte(); // Compressed code length.
}
// Init the bit reader.
bitReader = new BitReader(baseStream);
bitReader.HighToLow = false; // Bits are read from least
// significant to most significant.
// Construct the huffman tree.
root = new HuffmanNode();
for(int i = 0; i < numCouples; i++)
{
HuffmanNode node = root;
for(int j = 0; j < couples[i, 1]; j++)
{
// Check the validity of the tree.
if(node.Symbol != 0)
{
throw new IOException("The huffman-compressed stream is corrupt.");
}
// Move the node to the zero or one nodes, depending on the value
// of the bit that is read.
if(bitReader.ReadBit())
{
if(node.One == null)
{
node.One = new HuffmanNode();
}
node = node.One;
}
else
{
if(node.Zero == null)
{
node.Zero = new HuffmanNode();
}
node = node.Zero;
}
}
// Check the validity of the tree.
if(node.Zero != null || node.One != null)
{
throw new IOException("The huffman-compressed stream is corrupt.");
}
// Store the uncompressed byte.
node.Symbol = couples[i, 0];
}
// Ignore the rest of the bits in this byte.
bitReader.ReadBits(8 - bitReader.BitPosition);
}
public Stream BaseStream
{
get
{
return baseStream;
}
}
public override void Close()
{
}
public override bool CanRead
{
get
{
return true;
}
}
public override bool CanSeek
{
get
{
return false;
}
}
public override bool CanWrite
{
get
{
return false;
}
}
public override long Length
{
get
{
return dataLength;
}
}
public override long Position
{
get
{
return position;
}
set
{
throw new NotSupportedException();
}
}
public override int Read(byte[] buffer, int offset, int count)
{
// Make sure we don't read past the end.
count = Math.Min(count, dataLength - position);
HuffmanNode node = root;
for(int i = offset; i < offset + count; i++)
{
// For each bit, branch to the left or right.
while(node.Symbol == 0)
{
if(bitReader.ReadBit())
{
node = node.One;
}
else
{
node = node.Zero;
}
}
// Store the uncompressed symbol in the supplied buffer.
buffer[i] = node.Symbol;
calculatedParity ^= node.Symbol; // Update the parity.
// Start at the beginning again.
node = root;
}
// Update the position and return the number of bytes that were read.
position += count;
return count;
}
public override void Write(byte[] buffer, int offset, int count)
{
throw new NotSupportedException();
}
public override void SetLength(long value)
{
throw new NotSupportedException();
}
public override void Flush()
{
}
public override long Seek(long offset, SeekOrigin origin)
{
throw new NotSupportedException();
}
}
/// <summary>
/// Reads bits from a stream.
/// </summary>
public class BitReader
{
Stream input;
// Settings.
bool highToLow;
bool throwOnEOF;
byte cachedByte;
int bitPos;
bool eof;
public BitReader(Stream input)
{
this.input = input;
highToLow = true;
throwOnEOF = true;
bitPos = 8;
}
public bool HighToLow
{
get
{
return highToLow;
}
set
{
highToLow = value;
}
}
public bool ThrowOnEOF
{
get
{
return throwOnEOF;
}
set
{
throwOnEOF = value;
}
}
// The position in the current byte (0 - 8).
// Zero means that none of the bits in the current byte have been read.
public int BitPosition
{
get
{
return bitPos;
}
}
public bool ReadBit()
{
return ReadBits(1) != 0;
}
public int ReadBits(int numBits)
{
if(numBits < 0 || numBits > 31)
{
throw new ArgumentOutOfRangeException("numBits");
}
if(eof)
{
return -1;
}
int result = 0;
while(numBits > 0)
{
if(bitPos == 8)
{
// Read another byte.
int b = input.ReadByte();
if(b == -1)
{
eof = true;
if(throwOnEOF)
{
throw new EndOfStreamException();
}
else
{
cachedByte = 0;
} // Pad with zeros.
}
else
{
cachedByte = (byte)b;
}
bitPos = 0;
}
int partialNumBits = Math.Min(numBits, 8 - bitPos);
result |= GetByteBits(cachedByte, bitPos, partialNumBits, highToLow) << (numBits - partialNumBits);
bitPos += partialNumBits;
numBits -= partialNumBits;
}
return result;
}
public static int GetByteBits(byte value, int start, int length, bool highToLow)
{
if(highToLow)
{
start = 8 - start - length;
} // Big-endian bit order.
return (value & (((1 << (start + length)) - 1) & ~((1 << start) - 1))) >> start;
}
}
}
|