rlm@3: /*
rlm@3:  * @(#)AppleRLEEncoder.java  1.1.1  2011-01-17
rlm@3:  *
rlm@3:  * Copyright © 2011 Werner Randelshofer, Immensee, Switzerland.
rlm@3:  * All rights reserved.
rlm@3:  *
rlm@3:  * You may not use, copy or modify this file, except in compliance with the
rlm@3:  * license agreement you entered into with Werner Randelshofer.
rlm@3:  * For details see accompanying license terms.
rlm@3:  */
rlm@3: package com.aurellem.capture;
rlm@3: 
rlm@3: import java.io.ByteArrayOutputStream;
rlm@3: import java.io.IOException;
rlm@3: import java.io.OutputStream;
rlm@3: import java.util.Arrays;
rlm@3: 
rlm@3: /**
rlm@3:  * Implements the run length encoding of the Microsoft RLE format.
rlm@3:  * <p>
rlm@3:  * Each line of a frame is compressed individually. A line consists of two-byte
rlm@3:  * op-codes optionally followed by data. The end of the line is marked with
rlm@3:  * the EOL op-code.
rlm@3:  * <p>
rlm@3:  * The following op-codes are supported:
rlm@3:  * <ul>
rlm@3:  * <li>{@code 0x00 0x00}
rlm@3:  * <br>Marks the end of a line.</li>
rlm@3:  *
rlm@3:  * <li>{@code  0x00 0x01}
rlm@3:  * <br>Marks the end of the bitmap.</li>
rlm@3:  *
rlm@3:  * <li>{@code 0x00 0x02 x y}
rlm@3:  * <br> Marks a delta (skip). {@code x} and {@code y}
rlm@3:  * indicate the horizontal and vertical offset from the current position.
rlm@3:  * {@code x} and {@code y} are unsigned 8-bit values.</li>
rlm@3:  *
rlm@3:  * <li>{@code 0x00 n data{n} 0x00?}
rlm@3:  * <br> Marks a literal run. {@code n}
rlm@3:  * gives the number of data bytes that follow. {@code n} must be between 3 and
rlm@3:  * 255. If n is odd, a pad byte with the value 0x00 must be added.
rlm@3:  * </li>
rlm@3:  * <li>{@code n data}
rlm@3:  * <br> Marks a repetition. {@code n}
rlm@3:  * gives the number of times the data byte is repeated. {@code n} must be
rlm@3:  * between 1 and 255.
rlm@3:  * </li>
rlm@3:  * </ul>
rlm@3:  * Example:
rlm@3:  * <pre>
rlm@3:  * Compressed data         Expanded data
rlm@3:  *
rlm@3:  * 03 04                   04 04 04
rlm@3:  * 05 06                   06 06 06 06 06
rlm@3:  * 00 03 45 56 67 00       45 56 67
rlm@3:  * 02 78                   78 78
rlm@3:  * 00 02 05 01             Move 5 right and 1 down
rlm@3:  * 02 78                   78 78
rlm@3:  * 00 00                   End of line
rlm@3:  * 09 1E                   1E 1E 1E 1E 1E 1E 1E 1E 1E
rlm@3:  * 00 01                   End of RLE bitmap
rlm@3:  * </pre>
rlm@3:  *
rlm@3:  * References:<br/>
rlm@3:  * <a href="http://wiki.multimedia.cx/index.php?title=Microsoft_RLE">http://wiki.multimedia.cx/index.php?title=Microsoft_RLE</a><br>
rlm@3:  *
rlm@3:  * @author Werner Randelshofer
rlm@3:  * @version 1.1.1 2011-01-17 Removes unused imports.
rlm@3:  * <br>1.1 2011-01-07 Improves performance.
rlm@3:  * <br>1.0 2011-01-05 Created.
rlm@3:  */
rlm@3: public class MicrosoftRLEEncoder {
rlm@3: 
rlm@3:     private SeekableByteArrayOutputStream tempSeek=new SeekableByteArrayOutputStream();
rlm@3:     private DataChunkOutputStream temp=new DataChunkOutputStream(tempSeek);
rlm@3: 
rlm@3:     /** Encodes a 8-bit key frame.
rlm@3:      *
rlm@3:      * @param temp The output stream. Must be set to Big-Endian.
rlm@3:      * @param data The image data.
rlm@3:      * @param offset The offset to the first pixel in the data array.
rlm@3:      * @param length The width of the image in data elements.
rlm@3:      * @param step The number to add to offset to get to the next scanline.
rlm@3:      */
rlm@3:     public void writeKey8(OutputStream out, byte[] data, int offset, int length, int step, int height)
rlm@3:             throws IOException {
rlm@3:         tempSeek.reset();
rlm@3:         int ymax = offset + height * step;
rlm@3:         int upsideDown = ymax-step+offset;
rlm@3: 
rlm@3:         // Encode each scanline separately
rlm@3:         for (int y = offset; y < ymax; y += step) {
rlm@3:             int xy = upsideDown-y;
rlm@3:             int xymax = xy + length;
rlm@3: 
rlm@3:             int literalCount = 0;
rlm@3:             int repeatCount = 0;
rlm@3:             for (; xy < xymax; ++xy) {
rlm@3:                 // determine repeat count
rlm@3:                 byte v = data[xy];
rlm@3:                 for (repeatCount = 0; xy < xymax && repeatCount < 255; ++xy, ++repeatCount) {
rlm@3:                     if (data[xy] != v) {
rlm@3:                         break;
rlm@3:                     }
rlm@3:                 }
rlm@3:                 xy -= repeatCount;
rlm@3:                 if (repeatCount < 3) {
rlm@3:                     literalCount++;
rlm@3:                     if (literalCount == 254) {
rlm@3:                         temp.write(0);temp.write(literalCount); // Literal OP-code
rlm@3:                         temp.write(data, xy - literalCount + 1, literalCount);
rlm@3:                         literalCount = 0;
rlm@3:                     }
rlm@3:                 } else {
rlm@3:                     if (literalCount > 0) {
rlm@3:                         if (literalCount < 3) {
rlm@3:                             for (; literalCount > 0; --literalCount) {
rlm@3:                                 temp.write(1); // Repeat OP-code
rlm@3:                                 temp.write(data[xy - literalCount]);
rlm@3:                             }
rlm@3:                         } else {
rlm@3:                             temp.write(0);temp.write(literalCount); // Literal OP-code
rlm@3:                             temp.write(data, xy - literalCount, literalCount);
rlm@3:                             if (literalCount % 2 == 1) {
rlm@3:                                 temp.write(0); // pad byte
rlm@3:                             }
rlm@3:                             literalCount = 0;
rlm@3:                         }
rlm@3:                     }
rlm@3:                     temp.write(repeatCount); // Repeat OP-code
rlm@3:                     temp.write(v);
rlm@3:                     xy += repeatCount - 1;
rlm@3:                 }
rlm@3:             }
rlm@3: 
rlm@3:             // flush literal run
rlm@3:             if (literalCount > 0) {
rlm@3:                 if (literalCount < 3) {
rlm@3:                     for (; literalCount > 0; --literalCount) {
rlm@3:                         temp.write(1); // Repeat OP-code
rlm@3:                         temp.write(data[xy - literalCount]);
rlm@3:                     }
rlm@3:                 } else {
rlm@3:                     temp.write(0);temp.write(literalCount);
rlm@3:                     temp.write(data, xy - literalCount, literalCount);
rlm@3:                     if (literalCount % 2 == 1) {
rlm@3:                         temp.write(0); // pad byte
rlm@3:                     }
rlm@3:                 }
rlm@3:                 literalCount = 0;
rlm@3:             }
rlm@3: 
rlm@3:             temp.write(0);temp.write(0x0000);// End of line
rlm@3:         }
rlm@3:         temp.write(0);temp.write(0x0001);// End of bitmap
rlm@3:         tempSeek.toOutputStream(out);
rlm@3:     }
rlm@3: 
rlm@3:     /** Encodes a 8-bit delta frame.
rlm@3:      *
rlm@3:      * @param temp The output stream. Must be set to Big-Endian.
rlm@3:      * @param data The image data.
rlm@3:      * @param prev The image data of the previous frame.
rlm@3:      * @param offset The offset to the first pixel in the data array.
rlm@3:      * @param length The width of the image in data elements.
rlm@3:      * @param step The number to add to offset to get to the next scanline.
rlm@3:      */
rlm@3:     public void writeDelta8(OutputStream out, byte[] data, byte[] prev, int offset, int length, int step, int height)
rlm@3:             throws IOException {
rlm@3: 
rlm@3: tempSeek.reset();
rlm@3:         // Determine whether we can skip lines at the beginning
rlm@3:         int ymin;
rlm@3:         int ymax = offset + height * step;
rlm@3:         int upsideDown = ymax-step+offset;
rlm@3:         scanline:
rlm@3:         for (ymin = offset; ymin < ymax; ymin += step) {
rlm@3:             int xy = upsideDown-ymin;
rlm@3:             int xymax = xy + length;
rlm@3:             for (; xy < xymax; ++xy) {
rlm@3:                 if (data[xy] != prev[xy]) {
rlm@3:                     break scanline;
rlm@3:                 }
rlm@3:             }
rlm@3:         }
rlm@3: 
rlm@3:         if (ymin == ymax) {
rlm@3:             // => Frame is identical to previous one
rlm@3:             temp.write(0);temp.write(0x0001); // end of bitmap
rlm@3:             return;
rlm@3:         }
rlm@3: 
rlm@3:         if (ymin > offset) {
rlm@3:             int verticalOffset = ymin / step;
rlm@3:             while (verticalOffset > 255) {
rlm@3:                 temp.write(0);temp.write(0x0002); // Skip OP-code
rlm@3:                 temp.write(0); // horizontal offset
rlm@3:                 temp.write(255); // vertical offset
rlm@3:                 verticalOffset -= 255;
rlm@3:             }
rlm@3:             if (verticalOffset == 1) {
rlm@3:                 temp.write(0);temp.write(0x0000); // End of line OP-code
rlm@3:             } else {
rlm@3:                 temp.write(0);temp.write(0x0002); // Skip OP-code
rlm@3:                 temp.write(0); // horizontal offset
rlm@3:                 temp.write(verticalOffset); // vertical offset
rlm@3:             }
rlm@3:         }
rlm@3: 
rlm@3: 
rlm@3:         // Determine whether we can skip lines at the end
rlm@3:         scanline:
rlm@3:         for (; ymax > ymin; ymax -= step) {
rlm@3:             int xy = upsideDown-ymax+step;
rlm@3:             int xymax = xy + length;
rlm@3:             for (; xy < xymax; ++xy) {
rlm@3:                 if (data[xy] != prev[xy]) {
rlm@3:                     break scanline;
rlm@3:                 }
rlm@3:             }
rlm@3:         }
rlm@3:         //System.out.println("MicrosoftRLEEncoder ymin:" + ymin / step + " ymax" + ymax / step);
rlm@3: 
rlm@3: 
rlm@3:         // Encode each scanline
rlm@3:         int verticalOffset = 0;
rlm@3:         for (int y = ymin; y < ymax; y += step) {
rlm@3:             int xy = upsideDown-y;
rlm@3:             int xymax = xy + length;
rlm@3: 
rlm@3:             // determine skip count
rlm@3:             int skipCount = 0;
rlm@3:             for (; xy < xymax; ++xy, ++skipCount) {
rlm@3:                 if (data[xy] != prev[xy]) {
rlm@3:                     break;
rlm@3:                 }
rlm@3:             }
rlm@3:             if (skipCount == length) {
rlm@3:                 // => the entire line can be skipped
rlm@3:                 ++verticalOffset;
rlm@3:                 if (verticalOffset == 255) {
rlm@3:                     temp.write(0);temp.write(0x0002); // Skip OP-code
rlm@3:                     temp.write(0); // horizontal offset
rlm@3:                     temp.write(255); // vertical offset
rlm@3:                     verticalOffset = 0;
rlm@3:                 }
rlm@3:                 continue;
rlm@3:             }
rlm@3: 
rlm@3:             if (verticalOffset > 0 || skipCount > 0) {
rlm@3:                 if (verticalOffset == 1 && skipCount == 0) {
rlm@3:                     temp.write(0);temp.write(0x0000); // End of line OP-code
rlm@3:                 } else {
rlm@3:                     temp.write(0);temp.write(0x0002); // Skip OP-code
rlm@3:                     temp.write(Math.min(255, skipCount)); // horizontal offset
rlm@3:                     skipCount -= 255;
rlm@3:                     temp.write(verticalOffset); // vertical offset
rlm@3:                 }
rlm@3:                 verticalOffset = 0;
rlm@3:             }
rlm@3:             while (skipCount > 0) {
rlm@3:                 temp.write(0);temp.write(0x0002); // Skip OP-code
rlm@3:                 temp.write(Math.min(255, skipCount)); // horizontal offset
rlm@3:                 temp.write(0); // vertical offset
rlm@3:                 skipCount -= 255;
rlm@3:             }
rlm@3: 
rlm@3:             int literalCount = 0;
rlm@3:             int repeatCount = 0;
rlm@3:             for (; xy < xymax; ++xy) {
rlm@3:                 // determine skip count
rlm@3:                 for (skipCount = 0; xy < xymax; ++xy, ++skipCount) {
rlm@3:                     if (data[xy] != prev[xy]) {
rlm@3:                         break;
rlm@3:                     }
rlm@3:                 }
rlm@3:                 xy -= skipCount;
rlm@3: 
rlm@3:                 // determine repeat count
rlm@3:                 byte v = data[xy];
rlm@3:                 for (repeatCount = 0; xy < xymax && repeatCount < 255; ++xy, ++repeatCount) {
rlm@3:                     if (data[xy] != v) {
rlm@3:                         break;
rlm@3:                     }
rlm@3:                 }
rlm@3:                 xy -= repeatCount;
rlm@3: 
rlm@3:                 if (skipCount < 4 && xy + skipCount < xymax && repeatCount < 3) {
rlm@3:                     literalCount++;
rlm@3:                     if (literalCount == 254) {
rlm@3:                         temp.write(0);temp.write(literalCount); // Literal OP-code
rlm@3:                         temp.write(data, xy - literalCount + 1, literalCount);
rlm@3:                         literalCount = 0;
rlm@3:                     }
rlm@3:                 } else {
rlm@3:                     if (literalCount > 0) {
rlm@3:                         if (literalCount < 3) {
rlm@3:                             for (; literalCount > 0; --literalCount) {
rlm@3:                                 temp.write(1); // Repeat OP-code
rlm@3:                                 temp.write(data[xy - literalCount]);
rlm@3:                             }
rlm@3:                         } else {
rlm@3:                             temp.write(0);temp.write(literalCount);
rlm@3:                             temp.write(data, xy - literalCount, literalCount);
rlm@3:                             if (literalCount % 2 == 1) {
rlm@3:                                 temp.write(0); // pad byte
rlm@3:                             }
rlm@3:                         }
rlm@3:                         literalCount = 0;
rlm@3:                     }
rlm@3:                     if (xy + skipCount == xymax) {
rlm@3:                         // => we can skip until the end of the line without
rlm@3:                         //    having to write an op-code
rlm@3:                         xy += skipCount - 1;
rlm@3:                     } else if (skipCount >= repeatCount) {
rlm@3:                         while (skipCount > 255) {
rlm@3:                             temp.write(0);temp.write(0x0002); // Skip OP-code
rlm@3:                             temp.write(255);
rlm@3:                             temp.write(0);
rlm@3:                             xy += 255;
rlm@3:                             skipCount -= 255;
rlm@3:                         }
rlm@3:                         temp.write(0);temp.write(0x0002); // Skip OP-code
rlm@3:                         temp.write(skipCount);
rlm@3:                         temp.write(0);
rlm@3:                         xy += skipCount - 1;
rlm@3:                     } else {
rlm@3:                         temp.write(repeatCount); // Repeat OP-code
rlm@3:                         temp.write(v);
rlm@3:                         xy += repeatCount - 1;
rlm@3:                     }
rlm@3:                 }
rlm@3:             }
rlm@3: 
rlm@3:             // flush literal run
rlm@3:             if (literalCount > 0) {
rlm@3:                 if (literalCount < 3) {
rlm@3:                     for (; literalCount > 0; --literalCount) {
rlm@3:                         temp.write(1); // Repeat OP-code
rlm@3:                         temp.write(data[xy - literalCount]);
rlm@3:                     }
rlm@3:                 } else {
rlm@3:                     temp.write(0);temp.write(literalCount);
rlm@3:                     temp.write(data, xy - literalCount, literalCount);
rlm@3:                     if (literalCount % 2 == 1) {
rlm@3:                         temp.write(0); // pad byte
rlm@3:                     }
rlm@3:                 }
rlm@3:             }
rlm@3: 
rlm@3:             temp.write(0);temp.write(0x0000); // End of line OP-code
rlm@3:         }
rlm@3: 
rlm@3:         temp.write(0);temp.write(0x0001);// End of bitmap
rlm@3:         tempSeek.toOutputStream(out);
rlm@3:     }
rlm@3: 
rlm@3:     public static void main(String[] args) {
rlm@3:         byte[] data = {//
rlm@3:             8, 2, 3, 4, 4, 3,7,7,7, 8,//
rlm@3:             8, 1, 1, 1, 1, 2,7,7,7, 8,//
rlm@3:             8, 0, 2, 0, 0, 0,7,7,7, 8,//
rlm@3:             8, 2, 2, 3, 4, 4,7,7,7, 8,//
rlm@3:             8, 1, 4, 4, 4, 5,7,7,7, 8};
rlm@3: 
rlm@3: 
rlm@3:         byte[] prev = {//
rlm@3:             8, 3, 3, 3, 3, 3,7,7,7, 8,//
rlm@3:             8, 1, 1, 1, 1, 1,7,7,7, 8, //
rlm@3:             8, 5, 5, 5, 5, 0,7,7,7, 8,//
rlm@3:             8, 2, 2, 0, 0, 0,7,7,7, 8,//
rlm@3:             8, 2, 0, 0, 0, 5,7,7,7, 8};
rlm@3:         ByteArrayOutputStream buf = new ByteArrayOutputStream();
rlm@3:         DataChunkOutputStream out = new DataChunkOutputStream(buf);
rlm@3:         MicrosoftRLEEncoder enc = new MicrosoftRLEEncoder();
rlm@3: 
rlm@3:         try {
rlm@3:             enc.writeDelta8(out, data, prev, 1, 8, 10, 5);
rlm@3:             //enc.writeKey8(out, data, 1, 8, 10,5);
rlm@3:             out.close();
rlm@3: 
rlm@3:             byte[] result = buf.toByteArray();
rlm@3:             System.out.println("size:" + result.length);
rlm@3:             System.out.println(Arrays.toString(result));
rlm@3:             System.out.print("0x [");
rlm@3: 
rlm@3:             for (int i = 0; i < result.length; i++) {
rlm@3:                 if (i != 0) {
rlm@3:                     System.out.print(',');
rlm@3:                 }
rlm@3:                 String hex = "00" + Integer.toHexString(result[i]);
rlm@3:                 System.out.print(hex.substring(hex.length() - 2));
rlm@3:             }
rlm@3:             System.out.println(']');
rlm@3: 
rlm@3:         } catch (IOException ex) {
rlm@3:             ex.printStackTrace();
rlm@3:         }
rlm@3:     }
rlm@3: }