sequencecompression.java

是内存受限系统设计的代码。

 
/* ***************************************************
   Sequence Compression example
   Run Length Encoding and Delta compression
   Each sequence is encoded:
   Full values: ESC (0xff) hibyte lowbyte count
   Deltas: byte in range -127 to + 127
   ***************************************************
   */

import  java.io.*;
import java.util.*;

class SequenceCompression
    // StringCompressions each line in a file
{
    public static void main( String args[] )
    {
        SequenceCompression self=new SequenceCompression();

        short [][] tests = {
            { 42 } , 
            { 4067, 4069, 4072, 4062, 4064, 4064, 4064, 4064, 4064, 4064, 
              4066, 4066, 4059, 4061, 4062, 4061},
            { 0, 0, 0, 4067, 4069 },
            { 0, 0, 0 },
            { 0 }, 
            { (short) 0xffff, (short) 0xfffe } 
        };
        
        for (int i = 0; i < tests.length; i++ ) {
            System.out.println("Test " + i);
            self.test(tests[i]);            
        };
    }

    protected void test(short[] input) {
        byte[] intermediate = encodeSequence(input);
        for ( int i=0; i< Math.min( intermediate.length, 20 ); i++ )
            System.out.print( " " + Integer.toString( intermediate[i] & 0xff, 16 ) );
        System.out.println( "" );
        short[] output = decodeSequence(intermediate);

        for ( int i=0; i< input.length; i++ )
            if (input[i] != output[i])
                {
                    System.err.println( "Error: Output and input differ at " + i + 
                                        ": " + input[i] + "!=" + output[i] );
                }

        System.out.println( intermediate.length + "/" + (input.length * 2) + " " + 
                            (float) intermediate.length * 50.0 / input.length + "%");
    }
    

    protected ByteArrayOutputStream outStream;
    protected ByteArrayInputStream inStream;

    protected final int SequenceEscape =  0xff;
    protected final int MaxSequenceLength =  3;
    protected short lastShort;  // the last value read
    protected short runLength;  // how many of that value received

    protected byte[] encodeSequence(short []inputSequence) {
        outStream = new ByteArrayOutputStream();
        lastShort = 0;
        runLength = 0;

        for (int i = 0; i < inputSequence.length; i++) {
            encodeShort(inputSequence[i]);
        }
        flushSequence();

        byte [] result = outStream.toByteArray();
        outStream = null;
        return result;
    }

    protected void encodeShort(short s) {
        if (s == lastShort) {
            runLength++;
            if (runLength >= MaxSequenceLength) {
                flushSequence();
            }
        } else if (Math.abs(s - lastShort) < 128 ) {
            flushSequence();
            writeEncodedByte(s - lastShort + 128);
        } else {
            flushSequence();
            runLength++;
        }
        lastShort = s;
    }
    
    protected void flushSequence() {
        if (runLength == 0) return;
        writeEncodedByte(SequenceEscape);
        writeEncodedByte(lastShort >>> 8);
        writeEncodedByte(lastShort & 0xff);
        writeEncodedByte(runLength);
        runLength = 0;
    }

    protected void writeEncodedByte( int b ) {
        outStream.write( b );
    }

    Vector out;

    protected void writeDecodedShort(short s) {
        out.addElement(new Short(s));
    }

    protected short [] decodeSequence(byte [] s) {
        inStream = new ByteArrayInputStream(s);
        out = new Vector(s.length);
        int byteRead;
        lastShort = 0;
        
        while( (byteRead = inStream.read()) != -1) {
            byteRead = byteRead & 0xff;
            
            if (byteRead == SequenceEscape) {
                lastShort = (short) (((inStream.read() &0xff ) << 8) +
                                     (inStream.read() & 0xff)); 
                for (int c = inStream.read(); c > 0; c--) {
                    writeDecodedShort(lastShort);
                }
            } else {
                writeDecodedShort(lastShort += byteRead -128);
            }
        }
        // Java typing makes programmers vomit
        short[] result = new short[out.size()];
        for (int i=0; i < out.size(); i++) {
            result[i] = ((Short)out.elementAt(i)).shortValue();
        };
        return result;
    }
    
};