From 9fee0ec4ca0c5b7a334cc29dbb58e76c7a4c736e Mon Sep 17 00:00:00 2001 From: Michiel Van Der Kolk Date: Mon, 11 Jul 2005 15:42:37 +0000 Subject: Songdb java version, source. only 1.5 compatible git-svn-id: svn://svn.rockbox.org/rockbox/trunk@7101 a1c6a512-1295-4272-9138-f99709370657 --- songdbj/de/jarnbjo/util/io/BitInputStream.java | 185 +++++++++++ .../jarnbjo/util/io/ByteArrayBitInputStream.java | 352 +++++++++++++++++++++ songdbj/de/jarnbjo/util/io/HuffmanNode.java | 144 +++++++++ 3 files changed, 681 insertions(+) create mode 100644 songdbj/de/jarnbjo/util/io/BitInputStream.java create mode 100644 songdbj/de/jarnbjo/util/io/ByteArrayBitInputStream.java create mode 100644 songdbj/de/jarnbjo/util/io/HuffmanNode.java (limited to 'songdbj/de/jarnbjo/util/io') diff --git a/songdbj/de/jarnbjo/util/io/BitInputStream.java b/songdbj/de/jarnbjo/util/io/BitInputStream.java new file mode 100644 index 0000000000..89cadb8380 --- /dev/null +++ b/songdbj/de/jarnbjo/util/io/BitInputStream.java @@ -0,0 +1,185 @@ +/* + * $ProjectName$ + * $ProjectRevision$ + * ----------------------------------------------------------- + * $Id$ + * ----------------------------------------------------------- + * + * $Author$ + * + * Description: + * + * Copyright 2002-2003 Tor-Einar Jarnbjo + * ----------------------------------------------------------- + * + * Change History + * ----------------------------------------------------------- + * $Log$ + * Revision 1.1 2005/07/11 15:42:36 hcl + * Songdb java version, source. only 1.5 compatible + * + * Revision 1.1.1.1 2004/04/04 22:09:12 shred + * First Import + * + * Revision 1.5 2003/04/10 19:48:31 jarnbjo + * no message + * + * Revision 1.4 2003/03/16 20:57:06 jarnbjo + * no message + * + * Revision 1.3 2003/03/16 20:56:56 jarnbjo + * no message + * + * Revision 1.2 2003/03/16 01:11:39 jarnbjo + * no message + * + * Revision 1.1 2003/03/03 21:02:20 jarnbjo + * no message + * + */ + +package de.jarnbjo.util.io; + +import java.io.IOException; + +/** + * An interface with methods allowing bit-wise reading from + * an input stream. All methods in this interface are optional + * and an implementation not support a method or a specific state + * (e.g. endian) will throw an UnspportedOperationException if + * such a method is being called. This should be speicified in + * the implementation documentation. + */ + +public interface BitInputStream { + + /** + * constant for setting this stream's mode to little endian + * + * @see #setEndian(int) + */ + + public static final int LITTLE_ENDIAN = 0; + + /** + * constant for setting this stream's mode to big endian + * + * @see #setEndian(int) + */ + + public static final int BIG_ENDIAN = 1; + + /** + * reads one bit (as a boolean) from the input stream + * + * @return true if the next bit is 1, + * false otherwise + * + * @throws IOException if an I/O error occurs + * @throws UnsupportedOperationException if the method is not supported by the implementation + */ + + public boolean getBit() throws IOException; + + /** + * reads bits number of bits from the input + * stream + * + * @return the unsigned integer value read from the stream + * + * @throws IOException if an I/O error occurs + * @throws UnsupportedOperationException if the method is not supported by the implementation + */ + + public int getInt(int bits) throws IOException; + + /** + * reads bits number of bits from the input + * stream + * + * @return the signed integer value read from the stream + * + * @throws IOException if an I/O error occurs + * @throws UnsupportedOperationException if the method is not supported by the implementation + */ + + public int getSignedInt(int bits) throws IOException; + + /** + * reads a huffman codeword based on the root + * parameter and returns the decoded value + * + * @param root the root of the Huffman tree used to decode the codeword + * @return the decoded unsigned integer value read from the stream + * + * @throws IOException if an I/O error occurs + * @throws UnsupportedOperationException if the method is not supported by the implementation + */ + + public int getInt(HuffmanNode root) throws IOException; + + /** + * reads an integer encoded as "signed rice" as described in + * the FLAC audio format specification + * + * @param order + * @return the decoded integer value read from the stream + * + * @throws IOException if an I/O error occurs + * @throws UnsupportedOperationException if the method is not supported by the implementation + */ + + public int readSignedRice(int order) throws IOException; + + /** + * fills the array from offset with len + * integers encoded as "signed rice" as described in + * the FLAC audio format specification + * + * @param order + * @param buffer + * @param offset + * @param len + * @return the decoded integer value read from the stream + * + * @throws IOException if an I/O error occurs + * @throws UnsupportedOperationException if the method is not supported by the implementation + */ + + public void readSignedRice(int order, int[] buffer, int offset, int len) throws IOException; + + /** + * reads bits number of bits from the input + * stream + * + * @return the unsigned long value read from the stream + * + * @throws IOException if an I/O error occurs + * @throws UnsupportedOperationException if the method is not supported by the implementation + */ + + public long getLong(int bits) throws IOException; + + /** + * causes the read pointer to be moved to the beginning + * of the next byte, remaining bits in the current byte + * are discarded + * + * @throws UnsupportedOperationException if the method is not supported by the implementation + */ + + public void align(); + + /** + * changes the endian mode used when reading bit-wise from + * the stream, changing the mode mid-stream will cause the + * read cursor to move to the beginning of the next byte + * (as if calling the allign method + * + * @see #align() + * + * @throws UnsupportedOperationException if the method is not supported by the implementation + */ + + public void setEndian(int endian); +} \ No newline at end of file diff --git a/songdbj/de/jarnbjo/util/io/ByteArrayBitInputStream.java b/songdbj/de/jarnbjo/util/io/ByteArrayBitInputStream.java new file mode 100644 index 0000000000..9c84c7daca --- /dev/null +++ b/songdbj/de/jarnbjo/util/io/ByteArrayBitInputStream.java @@ -0,0 +1,352 @@ +/* + * $ProjectName$ + * $ProjectRevision$ + * ----------------------------------------------------------- + * $Id$ + * ----------------------------------------------------------- + * + * $Author$ + * + * Description: + * + * Copyright 2002-2003 Tor-Einar Jarnbjo + * ----------------------------------------------------------- + * + * Change History + * ----------------------------------------------------------- + * $Log$ + * Revision 1.1 2005/07/11 15:42:36 hcl + * Songdb java version, source. only 1.5 compatible + * + * Revision 1.1.1.1 2004/04/04 22:09:12 shred + * First Import + * + * Revision 1.3 2003/04/10 19:48:31 jarnbjo + * no message + * + * Revision 1.2 2003/03/16 01:11:39 jarnbjo + * no message + * + * Revision 1.1 2003/03/03 21:02:20 jarnbjo + * no message + * + */ + +package de.jarnbjo.util.io; + +import java.io.IOException; + +/** + * Implementation of the BitInputStream interface, + * using a byte array as data source. +*/ + +public class ByteArrayBitInputStream implements BitInputStream { + + private byte[] source; + private byte currentByte; + + private int endian; + + private int byteIndex=0; + private int bitIndex=0; + + public ByteArrayBitInputStream(byte[] source) { + this(source, LITTLE_ENDIAN); + } + + public ByteArrayBitInputStream(byte[] source, int endian) { + this.endian=endian; + this.source=source; + currentByte=source[0]; + bitIndex=(endian==LITTLE_ENDIAN)?0:7; + } + + public boolean getBit() throws IOException { + if(endian==LITTLE_ENDIAN) { + if(bitIndex>7) { + bitIndex=0; + currentByte=source[++byteIndex]; + } + return (currentByte&(1<<(bitIndex++)))!=0; + } + else { + if(bitIndex<0) { + bitIndex=7; + currentByte=source[++byteIndex]; + } + return (currentByte&(1<<(bitIndex--)))!=0; + } + } + + public int getInt(int bits) throws IOException { + if(bits>32) { + throw new IllegalArgumentException("Argument \"bits\" must be <= 32"); + } + int res=0; + if(endian==LITTLE_ENDIAN) { + for(int i=0; i>offset; + bitIndex-=bits; + } + else { + res=(((int)currentByte)&0xff&((1<<(bitIndex+1))-1))<<(bits-bitIndex-1); + bits-=bitIndex+1; + currentByte=source[++byteIndex]; + while(bits>=8) { + bits-=8; + res|=(((int)source[byteIndex])&0xff)<0) { + int ci=((int)source[byteIndex])&0xff; + res|=(ci>>(8-bits))&((1<=1<<(bits-1)) { + raw-=1<7) { + bitIndex=0; + currentByte=source[++byteIndex]; + } + root=(currentByte&(1<<(bitIndex++)))!=0?root.o1:root.o0; + } + return root.value.intValue(); + } + + public long getLong(int bits) throws IOException { + if(bits>64) { + throw new IllegalArgumentException("Argument \"bits\" must be <= 64"); + } + long res=0; + if(endian==LITTLE_ENDIAN) { + for(int i=0; i=0; i--) { + if(getBit()) { + res|=(1L<reads an integer encoded as "signed rice" as described in + * the FLAC audio format specification

+ * + *

not supported for little endian

+ * + * @param order + * @return the decoded integer value read from the stream + * + * @throws IOException if an I/O error occurs + * @throws UnsupportedOperationException if the method is not supported by the implementation + */ + + public int readSignedRice(int order) throws IOException { + + int msbs=-1, lsbs=0, res=0; + + if(endian==LITTLE_ENDIAN) { + // little endian + throw new UnsupportedOperationException("ByteArrayBitInputStream.readSignedRice() is only supported in big endian mode"); + } + else { + // big endian + + byte cb=source[byteIndex]; + do { + msbs++; + if(bitIndex<0) { + bitIndex=7; + byteIndex++; + cb=source[byteIndex]; + } + } while((cb&(1<>offset; + bitIndex-=bits; + } + else { + lsbs=(((int)source[byteIndex])&0xff&((1<<(bitIndex+1))-1))<<(bits-bitIndex-1); + bits-=bitIndex+1; + byteIndex++; + while(bits>=8) { + bits-=8; + lsbs|=(((int)source[byteIndex])&0xff)<0) { + int ci=((int)source[byteIndex])&0xff; + lsbs|=(ci>>(8-bits))&((1<>1)-1:(res>>1); + } + + /** + *

fills the array from offset with len + * integers encoded as "signed rice" as described in + * the FLAC audio format specification

+ * + *

not supported for little endian

+ * + * @param order + * @param buffer + * @param offset + * @param len + * @return the decoded integer value read from the stream + * + * @throws IOException if an I/O error occurs + * @throws UnsupportedOperationException if the method is not supported by the implementation + */ + + public void readSignedRice(int order, int[] buffer, int off, int len) throws IOException { + + if(endian==LITTLE_ENDIAN) { + // little endian + throw new UnsupportedOperationException("ByteArrayBitInputStream.readSignedRice() is only supported in big endian mode"); + } + else { + // big endian + for(int i=off; i>offset; + bitIndex-=bits; + } + else { + lsbs=(((int)source[byteIndex])&0xff&((1<<(bitIndex+1))-1))<<(bits-bitIndex-1); + bits-=bitIndex+1; + byteIndex++; + while(bits>=8) { + bits-=8; + lsbs|=(((int)source[byteIndex])&0xff)<0) { + int ci=((int)source[byteIndex])&0xff; + lsbs|=(ci>>(8-bits))&((1<>1)-1:(res>>1); + } + } + } + + public void align() { + if(endian==BIG_ENDIAN && bitIndex>=0) { + bitIndex=7; + byteIndex++; + } + else if(endian==LITTLE_ENDIAN && bitIndex<=7) { + bitIndex=0; + byteIndex++; + } + } + + public void setEndian(int endian) { + if(this.endian==BIG_ENDIAN && endian==LITTLE_ENDIAN) { + bitIndex=0; + byteIndex++; + } + else if(this.endian==LITTLE_ENDIAN && endian==BIG_ENDIAN) { + bitIndex=7; + byteIndex++; + } + this.endian=endian; + } + + /** + * @return the byte array used as a source for this instance + */ + + public byte[] getSource() { + return source; + } +} \ No newline at end of file diff --git a/songdbj/de/jarnbjo/util/io/HuffmanNode.java b/songdbj/de/jarnbjo/util/io/HuffmanNode.java new file mode 100644 index 0000000000..88600a4ddd --- /dev/null +++ b/songdbj/de/jarnbjo/util/io/HuffmanNode.java @@ -0,0 +1,144 @@ +/* + * $ProjectName$ + * $ProjectRevision$ + * ----------------------------------------------------------- + * $Id$ + * ----------------------------------------------------------- + * + * $Author$ + * + * Description: + * + * Copyright 2002-2003 Tor-Einar Jarnbjo + * ----------------------------------------------------------- + * + * Change History + * ----------------------------------------------------------- + * $Log$ + * Revision 1.1 2005/07/11 15:42:36 hcl + * Songdb java version, source. only 1.5 compatible + * + * Revision 1.1.1.1 2004/04/04 22:09:12 shred + * First Import + * + * Revision 1.2 2003/04/10 19:48:31 jarnbjo + * no message + * + */ + +package de.jarnbjo.util.io; + +import java.io.IOException; +import de.jarnbjo.util.io.BitInputStream; + +/** + * Representation of a node in a Huffman tree, used to read + * Huffman compressed codewords from e.g. a Vorbis stream. + */ + +final public class HuffmanNode { + + private HuffmanNode parent; + private int depth=0; + protected HuffmanNode o0, o1; + protected Integer value; + private boolean full=false; + + /** + * creates a new Huffman tree root node + */ + + public HuffmanNode() { + this(null); + } + + protected HuffmanNode(HuffmanNode parent) { + this.parent=parent; + if(parent!=null) { + depth=parent.getDepth()+1; + } + } + + protected HuffmanNode(HuffmanNode parent, int value) { + this(parent); + this.value=new Integer(value); + full=true; + } + + protected int read(BitInputStream bis) throws IOException { + HuffmanNode iter=this; + while(iter.value==null) { + iter=bis.getBit()?iter.o1:iter.o0; + } + return iter.value.intValue(); + } + + protected HuffmanNode get0() { + return o0==null?set0(new HuffmanNode(this)):o0; + } + + protected HuffmanNode get1() { + return o1==null?set1(new HuffmanNode(this)):o1; + } + + protected Integer getValue() { + return value; + } + + private HuffmanNode getParent() { + return parent; + } + + protected int getDepth() { + return depth; + } + + private boolean isFull() { + return full?true:(full=o0!=null&&o0.isFull()&&o1!=null&&o1.isFull()); + } + + private HuffmanNode set0(HuffmanNode value) { + return o0=value; + } + + private HuffmanNode set1(HuffmanNode value) { + return o1=value; + } + + private void setValue(Integer value) { + full=true; + this.value=value; + } + + /** + * creates a new tree node at the first free location at the given + * depth, and assigns the value to it + * + * @param depth the tree depth of the new node (codeword length in bits) + * @param value the node's new value + */ + + public boolean setNewValue(int depth, int value) { + if(isFull()) { + return false; + } + if(depth==1) { + if(o0==null) { + set0(new HuffmanNode(this, value)); + return true; + } + else if(o1==null) { + set1(new HuffmanNode(this, value)); + return true; + } + else { + return false; + } + } + else { + return get0().setNewValue(depth-1, value)? + true: + get1().setNewValue(depth-1, value); + } + } +} -- cgit v1.2.3