package org.apache.poi.hdgf.other_lzw;
/*
* LZW.java
*
* Created on 01 Dec 2005
*
* Implementation of LZW compression/decompression algorithm
*/
import java.io.* ;
import java.util.* ;
/**
*
* @author Moshe Fresko
* @course Algorithmic Programming 1
* @exercise 3
*/
public class LZW
{
boolean stopped = false ;
Dict dict ;
// The bits that should be written for each code
int numOfBits ;
// The previous string that we should remember
// in order to insert into the dictionary
final ByteArray emptyBA = new ByteArray() ;
ByteArray w=emptyBA ;
// Constructor gets the number of bits to be written for each code
public LZW()
{
numOfBits = 12 ;
// Create a new Limited Dictionary
// For maximum of 2^bits entries
dict = new LimitedDict(1<<numOfBits) ;
// Add all ascii characters to the dictionary
for (int i=0;i<256;++i)
dict.add(new ByteArray((byte)i)) ;
}
// Encodes the next character.
// If there is a code generated returns it.
// If not returns -1.
int encodeOneChar(int n) {
byte c = (byte) n ;
ByteArray nw = w.conc(c) ;
int code = dict.numFromStr(nw) ;
// if it exists then we continue to search for a longer string
if (code!=-1) {
w = nw ;
return -1 ;
} else {
dict.add(nw) ;
nw = w ;
w = new ByteArray(c) ;
return dict.numFromStr(nw) ;
}
}
// If there is something left in w, returns its code
int encodeLast() {
ByteArray nw = w ;
w = emptyBA ;
return dict.numFromStr(nw) ;
}
// Write the code in bits into output stream
void writeCode(OutputStream os, int code) throws IOException
{
for (int i=0;i<numOfBits;++i) {
os.write(code&1) ;
code /= 2 ;
}
}
int readCode(InputStream is) throws IOException
{
int num = 0 ;
for (int i=0;i<numOfBits;++i) {
int next = is.read() ;
if (next<0)
return -1 ;
num += next<<i ;
}
return num ;
}
ByteArray decodeOne(int code) {
// Either "ABA" or null, w="AB"
ByteArray str = dict.strFromNum(code) ;
if (str==null) {
str = w.conc(w.getAt(0)) ;
dict.add(str) ;
} else
if (! w.isEmpty())
dict.add(w.conc(str.getAt(0))) ;
w = str ;
return w ;
}
public void decompress(InputStream is, OutputStream os) throws IOException {
is = new BitInputStream(is) ;
ByteArray str ; // Next entry
int code ; // Next code to be read
while ((code=readCode(is))>=0) {
if (stopped)
break ;
str = decodeOne(code) ;
os.write(str.getBytes()) ;
}
}
public void stop()
{ stopped = true ; }
public static class LimitedDict extends Dict {
int maxSize ;
LimitedDict(int maxSize)
{ this.maxSize = maxSize ; }
public void add(ByteArray str)
{ if (size()<maxSize)
super.add(str) ; }
}
public static class Dict {
// mp keeps : Word => Index
// ls keeps : Index => Word
Map mp = new HashMap() ;
List ls = new ArrayList() ;
// Adds an element into the dictionary
public void add(ByteArray str)
{ mp.put(str,new Integer(ls.size())) ;
ls.add(str) ;
}
// Gets the number for the given string.
// If it does not exist, returns -1
public final int numFromStr(ByteArray str)
{ return ( mp.containsKey(str) ?
((Integer)mp.get(str)).intValue() :
-1 ) ; }
// Gets the string for the given number
// If the number does not exist, return null
public final ByteArray strFromNum(int i)
{ return ( i<ls.size() ?
(ByteArray) ls.get(i) :
null ) ; }
public final int size()
{ return ls.size() ; }
}
public static class ByteArray {
// The single member variable is a byte array kept inside, it is immutable
final byte[] arr ;
// Constructor with a byte arrays will clone it, since we dont want access from outside
ByteArray(byte[] b)
{ arr = (byte[]) b.clone() ; }
// Default Constructor, 0 length array
ByteArray()
{ arr = new byte[0] ; }
// Constructor with a single byte
ByteArray(byte b)
{ arr = new byte[] { b } ; }
// For the hash-table we need this
public boolean equals(Object o)
{ ByteArray ba = (ByteArray) o ;
return java.util.Arrays.equals(arr,ba.arr) ; }
// For the hash-table we need to give a hash code. (Change must be done for a better hash code)
public int hashCode()
{ int code = 0 ;
for (int i=0;i<arr.length;++i)
code = code*2+arr[i] ;
return code ; }
// returns the size of the byte array
public int size()
{ return arr.length ; }
// returns the byte in a given position
byte getAt(int i)
{ return arr[i] ; }
// concatenates another byte array into this one,
// and returns the concatenation in another newly created one. (ByteArray is immutable)
public ByteArray conc(ByteArray b2)
{ int sz = size()+b2.size() ;
byte[] b = new byte[sz] ;
for (int i=0;i<size();++i) b[i]=getAt(i) ;
for (int i=0;i<b2.size();++i) b[i+size()]=b2.getAt(i) ;
return new ByteArray(b) ; }
// Concatenates a byte into this ByteArray.
// The result is returned in a new ByteArray. (ByteArray is immutable)
public ByteArray conc(byte b2)
{ return conc(new ByteArray(b2)) ; }
// Returns a byte array of the copy of the inner byte arrays
public byte[] getBytes()
{ return (byte[]) arr.clone() ; }
// Checks if it is zero length
public boolean isEmpty()
{ return size()==0 ; }
// Drops the last character and returns it
public byte getLast()
{ return arr[size()-1] ; }
public ByteArray dropLast()
{ byte[] newarr = new byte[size()-1] ;
for (int i=0;i<newarr.length;++i)
newarr[i] = arr[i] ;
return new ByteArray(newarr) ; }
public String toString()
{ return new String(arr) ; }
}
public static class BitInputStream extends FilterInputStream
{
/** Constructor creates a new instance of BitInputStream,
A decarotor to InputStream, via FilterInputStream */
public BitInputStream(InputStream is)
{ super(is) ; }
class BitManager {
// Buffer to keep max of 7 bits (one byte)
private int[] buf = new int[8] ;
// Counter showing the bit number we are reading now
private int cnt = -1 ;
// If we are at the end of the stream
boolean atTheEnd()
{ return ((buf[7]==1)&&(cnt<0)) ; }
// Set the flag for the end of stream
void setTheEnd()
{ buf[7]=1; cnt=-1; }
// No more buffer, means we need to read the next byte
boolean noMoreBuffer()
{ return cnt<0 ; }
// set the buffer
void setNext(int next)
{ // put the bits of the byte into the array
for (cnt=0; cnt<8; ++cnt) {
buf[cnt] = next % 2 ;
next /= 2 ;
}
// if this was the last byte
if (buf[7]==1) {
for (cnt=7;cnt>=0;cnt--)
if (buf[cnt]==0)
break ;
cnt-- ;
} else {
cnt = 6 ;
}
}
// get the next bit
int getNext()
{ return buf[cnt--] ; }
// how many left
int left()
{ return cnt+1 ; }
} ;
BitManager bitManager = new BitManager() ;
byte[] tempBuf = null ;
int tempBufPtr = 0 ;
int tempBufLen = 0 ;
private int readNextByte() throws IOException
{ int val = -1 ;
if (tempBufPtr==tempBufLen)
val = super.read() ;
else {
byte b = tempBuf[tempBufPtr++] ;
if ((b&0x80)>0)
val = ((int)(b&0x7F))|0x80 ;
else
val = b ;
}
return val ;
}
/** Reads a single bit from the included stream.
Returns either 1 or 0, and at the end of stream returns -1. */
public int read() throws IOException {
// If we are already at the end, return -1
if (bitManager.atTheEnd())
return -1 ;
// If we are in the last bit, then refill the buffer
if (bitManager.noMoreBuffer()) {
int i = readNextByte() ;
if (i<0)
bitManager.setTheEnd() ;
else
bitManager.setNext(i) ;
return read() ;
}
// Return the specific bit
return bitManager.getNext() ;
}
/** Reads a list of bits given in the byte array as 0's and 1's*/
public int read(byte[] arr) throws IOException
{ return read(arr,0,arr.length) ; }
public int read(byte[] arr, int off, int len) throws IOException
{ int bytelen = ( (len-bitManager.left()) / 7 ) ;
tempBuf = new byte[bytelen] ;
tempBufLen = in.read(tempBuf) ;
tempBufPtr = 0 ;
for (int i=0;i<len;++i) {
int next = read() ;
if (next<0)
return i ;
arr[off+i]=(byte) next ;
}
return len ;
}
public static void main(String[] args)
{
if (args.length<2)
{
System.out.println("Usage: java BitInputStream FromFile ToFile") ;
System.out.println("where 'FromFile' is a file to be open as a Bit Stream") ;
System.out.println("and they are written as characters of '0's and '1's") ;
System.out.println("every line having one char") ;
System.exit(1) ;
}
try {
InputStream is = new BitInputStream(new BufferedInputStream(new FileInputStream(args[0]))) ;
PrintWriter os = new PrintWriter(new OutputStreamWriter(new FileOutputStream(args[1]))) ;
int next ;
while ((next=is.read())>=0)
os.println(next) ;
is.close() ;
os.close() ;
} catch (FileNotFoundException fnfe) {
System.out.println(args[0]+" file cannot be opened") ;
System.exit(1) ;
} catch (IOException ioe) {
System.out.println("Error in reading file "+args[0]+" or writing file "+args[1]) ;
System.exit(1) ;
}
}
}
} |
