1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/com/aurellem/capture/MicrosoftRLEEncoder.java	Tue Oct 25 11:55:55 2011 -0700
     1.3 @@ -0,0 +1,400 @@
     1.4 +/*
     1.5 + * @(#)AppleRLEEncoder.java  1.1.1  2011-01-17
     1.6 + *
     1.7 + * Copyright © 2011 Werner Randelshofer, Immensee, Switzerland.
     1.8 + * All rights reserved.
     1.9 + *
    1.10 + * You may not use, copy or modify this file, except in compliance with the
    1.11 + * license agreement you entered into with Werner Randelshofer.
    1.12 + * For details see accompanying license terms.
    1.13 + */
    1.14 +package com.aurellem.capture;
    1.15 +
    1.16 +import java.io.ByteArrayOutputStream;
    1.17 +import java.io.IOException;
    1.18 +import java.io.OutputStream;
    1.19 +import java.util.Arrays;
    1.20 +
    1.21 +/**
    1.22 + * Implements the run length encoding of the Microsoft RLE format.
    1.23 + * <p>
    1.24 + * Each line of a frame is compressed individually. A line consists of two-byte
    1.25 + * op-codes optionally followed by data. The end of the line is marked with
    1.26 + * the EOL op-code.
    1.27 + * <p>
    1.28 + * The following op-codes are supported:
    1.29 + * <ul>
    1.30 + * <li>{@code 0x00 0x00}
    1.31 + * <br>Marks the end of a line.</li>
    1.32 + *
    1.33 + * <li>{@code  0x00 0x01}
    1.34 + * <br>Marks the end of the bitmap.</li>
    1.35 + *
    1.36 + * <li>{@code 0x00 0x02 x y}
    1.37 + * <br> Marks a delta (skip). {@code x} and {@code y}
    1.38 + * indicate the horizontal and vertical offset from the current position.
    1.39 + * {@code x} and {@code y} are unsigned 8-bit values.</li>
    1.40 + *
    1.41 + * <li>{@code 0x00 n data{n} 0x00?}
    1.42 + * <br> Marks a literal run. {@code n}
    1.43 + * gives the number of data bytes that follow. {@code n} must be between 3 and
    1.44 + * 255. If n is odd, a pad byte with the value 0x00 must be added.
    1.45 + * </li>
    1.46 + * <li>{@code n data}
    1.47 + * <br> Marks a repetition. {@code n}
    1.48 + * gives the number of times the data byte is repeated. {@code n} must be
    1.49 + * between 1 and 255.
    1.50 + * </li>
    1.51 + * </ul>
    1.52 + * Example:
    1.53 + * <pre>
    1.54 + * Compressed data         Expanded data
    1.55 + *
    1.56 + * 03 04                   04 04 04
    1.57 + * 05 06                   06 06 06 06 06
    1.58 + * 00 03 45 56 67 00       45 56 67
    1.59 + * 02 78                   78 78
    1.60 + * 00 02 05 01             Move 5 right and 1 down
    1.61 + * 02 78                   78 78
    1.62 + * 00 00                   End of line
    1.63 + * 09 1E                   1E 1E 1E 1E 1E 1E 1E 1E 1E
    1.64 + * 00 01                   End of RLE bitmap
    1.65 + * </pre>
    1.66 + *
    1.67 + * References:<br/>
    1.68 + * <a href="http://wiki.multimedia.cx/index.php?title=Microsoft_RLE">http://wiki.multimedia.cx/index.php?title=Microsoft_RLE</a><br>
    1.69 + *
    1.70 + * @author Werner Randelshofer
    1.71 + * @version 1.1.1 2011-01-17 Removes unused imports.
    1.72 + * <br>1.1 2011-01-07 Improves performance.
    1.73 + * <br>1.0 2011-01-05 Created.
    1.74 + */
    1.75 +public class MicrosoftRLEEncoder {
    1.76 +
    1.77 +    private SeekableByteArrayOutputStream tempSeek=new SeekableByteArrayOutputStream();
    1.78 +    private DataChunkOutputStream temp=new DataChunkOutputStream(tempSeek);
    1.79 +
    1.80 +    /** Encodes a 8-bit key frame.
    1.81 +     *
    1.82 +     * @param temp The output stream. Must be set to Big-Endian.
    1.83 +     * @param data The image data.
    1.84 +     * @param offset The offset to the first pixel in the data array.
    1.85 +     * @param length The width of the image in data elements.
    1.86 +     * @param step The number to add to offset to get to the next scanline.
    1.87 +     */
    1.88 +    public void writeKey8(OutputStream out, byte[] data, int offset, int length, int step, int height)
    1.89 +            throws IOException {
    1.90 +        tempSeek.reset();
    1.91 +        int ymax = offset + height * step;
    1.92 +        int upsideDown = ymax-step+offset;
    1.93 +
    1.94 +        // Encode each scanline separately
    1.95 +        for (int y = offset; y < ymax; y += step) {
    1.96 +            int xy = upsideDown-y;
    1.97 +            int xymax = xy + length;
    1.98 +
    1.99 +            int literalCount = 0;
   1.100 +            int repeatCount = 0;
   1.101 +            for (; xy < xymax; ++xy) {
   1.102 +                // determine repeat count
   1.103 +                byte v = data[xy];
   1.104 +                for (repeatCount = 0; xy < xymax && repeatCount < 255; ++xy, ++repeatCount) {
   1.105 +                    if (data[xy] != v) {
   1.106 +                        break;
   1.107 +                    }
   1.108 +                }
   1.109 +                xy -= repeatCount;
   1.110 +                if (repeatCount < 3) {
   1.111 +                    literalCount++;
   1.112 +                    if (literalCount == 254) {
   1.113 +                        temp.write(0);temp.write(literalCount); // Literal OP-code
   1.114 +                        temp.write(data, xy - literalCount + 1, literalCount);
   1.115 +                        literalCount = 0;
   1.116 +                    }
   1.117 +                } else {
   1.118 +                    if (literalCount > 0) {
   1.119 +                        if (literalCount < 3) {
   1.120 +                            for (; literalCount > 0; --literalCount) {
   1.121 +                                temp.write(1); // Repeat OP-code
   1.122 +                                temp.write(data[xy - literalCount]);
   1.123 +                            }
   1.124 +                        } else {
   1.125 +                            temp.write(0);temp.write(literalCount); // Literal OP-code
   1.126 +                            temp.write(data, xy - literalCount, literalCount);
   1.127 +                            if (literalCount % 2 == 1) {
   1.128 +                                temp.write(0); // pad byte
   1.129 +                            }
   1.130 +                            literalCount = 0;
   1.131 +                        }
   1.132 +                    }
   1.133 +                    temp.write(repeatCount); // Repeat OP-code
   1.134 +                    temp.write(v);
   1.135 +                    xy += repeatCount - 1;
   1.136 +                }
   1.137 +            }
   1.138 +
   1.139 +            // flush literal run
   1.140 +            if (literalCount > 0) {
   1.141 +                if (literalCount < 3) {
   1.142 +                    for (; literalCount > 0; --literalCount) {
   1.143 +                        temp.write(1); // Repeat OP-code
   1.144 +                        temp.write(data[xy - literalCount]);
   1.145 +                    }
   1.146 +                } else {
   1.147 +                    temp.write(0);temp.write(literalCount);
   1.148 +                    temp.write(data, xy - literalCount, literalCount);
   1.149 +                    if (literalCount % 2 == 1) {
   1.150 +                        temp.write(0); // pad byte
   1.151 +                    }
   1.152 +                }
   1.153 +                literalCount = 0;
   1.154 +            }
   1.155 +
   1.156 +            temp.write(0);temp.write(0x0000);// End of line
   1.157 +        }
   1.158 +        temp.write(0);temp.write(0x0001);// End of bitmap
   1.159 +        tempSeek.toOutputStream(out);
   1.160 +    }
   1.161 +
   1.162 +    /** Encodes a 8-bit delta frame.
   1.163 +     *
   1.164 +     * @param temp The output stream. Must be set to Big-Endian.
   1.165 +     * @param data The image data.
   1.166 +     * @param prev The image data of the previous frame.
   1.167 +     * @param offset The offset to the first pixel in the data array.
   1.168 +     * @param length The width of the image in data elements.
   1.169 +     * @param step The number to add to offset to get to the next scanline.
   1.170 +     */
   1.171 +    public void writeDelta8(OutputStream out, byte[] data, byte[] prev, int offset, int length, int step, int height)
   1.172 +            throws IOException {
   1.173 +
   1.174 +tempSeek.reset();
   1.175 +        // Determine whether we can skip lines at the beginning
   1.176 +        int ymin;
   1.177 +        int ymax = offset + height * step;
   1.178 +        int upsideDown = ymax-step+offset;
   1.179 +        scanline:
   1.180 +        for (ymin = offset; ymin < ymax; ymin += step) {
   1.181 +            int xy = upsideDown-ymin;
   1.182 +            int xymax = xy + length;
   1.183 +            for (; xy < xymax; ++xy) {
   1.184 +                if (data[xy] != prev[xy]) {
   1.185 +                    break scanline;
   1.186 +                }
   1.187 +            }
   1.188 +        }
   1.189 +
   1.190 +        if (ymin == ymax) {
   1.191 +            // => Frame is identical to previous one
   1.192 +            temp.write(0);temp.write(0x0001); // end of bitmap
   1.193 +            return;
   1.194 +        }
   1.195 +
   1.196 +        if (ymin > offset) {
   1.197 +            int verticalOffset = ymin / step;
   1.198 +            while (verticalOffset > 255) {
   1.199 +                temp.write(0);temp.write(0x0002); // Skip OP-code
   1.200 +                temp.write(0); // horizontal offset
   1.201 +                temp.write(255); // vertical offset
   1.202 +                verticalOffset -= 255;
   1.203 +            }
   1.204 +            if (verticalOffset == 1) {
   1.205 +                temp.write(0);temp.write(0x0000); // End of line OP-code
   1.206 +            } else {
   1.207 +                temp.write(0);temp.write(0x0002); // Skip OP-code
   1.208 +                temp.write(0); // horizontal offset
   1.209 +                temp.write(verticalOffset); // vertical offset
   1.210 +            }
   1.211 +        }
   1.212 +
   1.213 +
   1.214 +        // Determine whether we can skip lines at the end
   1.215 +        scanline:
   1.216 +        for (; ymax > ymin; ymax -= step) {
   1.217 +            int xy = upsideDown-ymax+step;
   1.218 +            int xymax = xy + length;
   1.219 +            for (; xy < xymax; ++xy) {
   1.220 +                if (data[xy] != prev[xy]) {
   1.221 +                    break scanline;
   1.222 +                }
   1.223 +            }
   1.224 +        }
   1.225 +        //System.out.println("MicrosoftRLEEncoder ymin:" + ymin / step + " ymax" + ymax / step);
   1.226 +
   1.227 +
   1.228 +        // Encode each scanline
   1.229 +        int verticalOffset = 0;
   1.230 +        for (int y = ymin; y < ymax; y += step) {
   1.231 +            int xy = upsideDown-y;
   1.232 +            int xymax = xy + length;
   1.233 +
   1.234 +            // determine skip count
   1.235 +            int skipCount = 0;
   1.236 +            for (; xy < xymax; ++xy, ++skipCount) {
   1.237 +                if (data[xy] != prev[xy]) {
   1.238 +                    break;
   1.239 +                }
   1.240 +            }
   1.241 +            if (skipCount == length) {
   1.242 +                // => the entire line can be skipped
   1.243 +                ++verticalOffset;
   1.244 +                if (verticalOffset == 255) {
   1.245 +                    temp.write(0);temp.write(0x0002); // Skip OP-code
   1.246 +                    temp.write(0); // horizontal offset
   1.247 +                    temp.write(255); // vertical offset
   1.248 +                    verticalOffset = 0;
   1.249 +                }
   1.250 +                continue;
   1.251 +            }
   1.252 +
   1.253 +            if (verticalOffset > 0 || skipCount > 0) {
   1.254 +                if (verticalOffset == 1 && skipCount == 0) {
   1.255 +                    temp.write(0);temp.write(0x0000); // End of line OP-code
   1.256 +                } else {
   1.257 +                    temp.write(0);temp.write(0x0002); // Skip OP-code
   1.258 +                    temp.write(Math.min(255, skipCount)); // horizontal offset
   1.259 +                    skipCount -= 255;
   1.260 +                    temp.write(verticalOffset); // vertical offset
   1.261 +                }
   1.262 +                verticalOffset = 0;
   1.263 +            }
   1.264 +            while (skipCount > 0) {
   1.265 +                temp.write(0);temp.write(0x0002); // Skip OP-code
   1.266 +                temp.write(Math.min(255, skipCount)); // horizontal offset
   1.267 +                temp.write(0); // vertical offset
   1.268 +                skipCount -= 255;
   1.269 +            }
   1.270 +
   1.271 +            int literalCount = 0;
   1.272 +            int repeatCount = 0;
   1.273 +            for (; xy < xymax; ++xy) {
   1.274 +                // determine skip count
   1.275 +                for (skipCount = 0; xy < xymax; ++xy, ++skipCount) {
   1.276 +                    if (data[xy] != prev[xy]) {
   1.277 +                        break;
   1.278 +                    }
   1.279 +                }
   1.280 +                xy -= skipCount;
   1.281 +
   1.282 +                // determine repeat count
   1.283 +                byte v = data[xy];
   1.284 +                for (repeatCount = 0; xy < xymax && repeatCount < 255; ++xy, ++repeatCount) {
   1.285 +                    if (data[xy] != v) {
   1.286 +                        break;
   1.287 +                    }
   1.288 +                }
   1.289 +                xy -= repeatCount;
   1.290 +
   1.291 +                if (skipCount < 4 && xy + skipCount < xymax && repeatCount < 3) {
   1.292 +                    literalCount++;
   1.293 +                    if (literalCount == 254) {
   1.294 +                        temp.write(0);temp.write(literalCount); // Literal OP-code
   1.295 +                        temp.write(data, xy - literalCount + 1, literalCount);
   1.296 +                        literalCount = 0;
   1.297 +                    }
   1.298 +                } else {
   1.299 +                    if (literalCount > 0) {
   1.300 +                        if (literalCount < 3) {
   1.301 +                            for (; literalCount > 0; --literalCount) {
   1.302 +                                temp.write(1); // Repeat OP-code
   1.303 +                                temp.write(data[xy - literalCount]);
   1.304 +                            }
   1.305 +                        } else {
   1.306 +                            temp.write(0);temp.write(literalCount);
   1.307 +                            temp.write(data, xy - literalCount, literalCount);
   1.308 +                            if (literalCount % 2 == 1) {
   1.309 +                                temp.write(0); // pad byte
   1.310 +                            }
   1.311 +                        }
   1.312 +                        literalCount = 0;
   1.313 +                    }
   1.314 +                    if (xy + skipCount == xymax) {
   1.315 +                        // => we can skip until the end of the line without
   1.316 +                        //    having to write an op-code
   1.317 +                        xy += skipCount - 1;
   1.318 +                    } else if (skipCount >= repeatCount) {
   1.319 +                        while (skipCount > 255) {
   1.320 +                            temp.write(0);temp.write(0x0002); // Skip OP-code
   1.321 +                            temp.write(255);
   1.322 +                            temp.write(0);
   1.323 +                            xy += 255;
   1.324 +                            skipCount -= 255;
   1.325 +                        }
   1.326 +                        temp.write(0);temp.write(0x0002); // Skip OP-code
   1.327 +                        temp.write(skipCount);
   1.328 +                        temp.write(0);
   1.329 +                        xy += skipCount - 1;
   1.330 +                    } else {
   1.331 +                        temp.write(repeatCount); // Repeat OP-code
   1.332 +                        temp.write(v);
   1.333 +                        xy += repeatCount - 1;
   1.334 +                    }
   1.335 +                }
   1.336 +            }
   1.337 +
   1.338 +            // flush literal run
   1.339 +            if (literalCount > 0) {
   1.340 +                if (literalCount < 3) {
   1.341 +                    for (; literalCount > 0; --literalCount) {
   1.342 +                        temp.write(1); // Repeat OP-code
   1.343 +                        temp.write(data[xy - literalCount]);
   1.344 +                    }
   1.345 +                } else {
   1.346 +                    temp.write(0);temp.write(literalCount);
   1.347 +                    temp.write(data, xy - literalCount, literalCount);
   1.348 +                    if (literalCount % 2 == 1) {
   1.349 +                        temp.write(0); // pad byte
   1.350 +                    }
   1.351 +                }
   1.352 +            }
   1.353 +
   1.354 +            temp.write(0);temp.write(0x0000); // End of line OP-code
   1.355 +        }
   1.356 +
   1.357 +        temp.write(0);temp.write(0x0001);// End of bitmap
   1.358 +        tempSeek.toOutputStream(out);
   1.359 +    }
   1.360 +
   1.361 +    public static void main(String[] args) {
   1.362 +        byte[] data = {//
   1.363 +            8, 2, 3, 4, 4, 3,7,7,7, 8,//
   1.364 +            8, 1, 1, 1, 1, 2,7,7,7, 8,//
   1.365 +            8, 0, 2, 0, 0, 0,7,7,7, 8,//
   1.366 +            8, 2, 2, 3, 4, 4,7,7,7, 8,//
   1.367 +            8, 1, 4, 4, 4, 5,7,7,7, 8};
   1.368 +
   1.369 +
   1.370 +        byte[] prev = {//
   1.371 +            8, 3, 3, 3, 3, 3,7,7,7, 8,//
   1.372 +            8, 1, 1, 1, 1, 1,7,7,7, 8, //
   1.373 +            8, 5, 5, 5, 5, 0,7,7,7, 8,//
   1.374 +            8, 2, 2, 0, 0, 0,7,7,7, 8,//
   1.375 +            8, 2, 0, 0, 0, 5,7,7,7, 8};
   1.376 +        ByteArrayOutputStream buf = new ByteArrayOutputStream();
   1.377 +        DataChunkOutputStream out = new DataChunkOutputStream(buf);
   1.378 +        MicrosoftRLEEncoder enc = new MicrosoftRLEEncoder();
   1.379 +
   1.380 +        try {
   1.381 +            enc.writeDelta8(out, data, prev, 1, 8, 10, 5);
   1.382 +            //enc.writeKey8(out, data, 1, 8, 10,5);
   1.383 +            out.close();
   1.384 +
   1.385 +            byte[] result = buf.toByteArray();
   1.386 +            System.out.println("size:" + result.length);
   1.387 +            System.out.println(Arrays.toString(result));
   1.388 +            System.out.print("0x [");
   1.389 +
   1.390 +            for (int i = 0; i < result.length; i++) {
   1.391 +                if (i != 0) {
   1.392 +                    System.out.print(',');
   1.393 +                }
   1.394 +                String hex = "00" + Integer.toHexString(result[i]);
   1.395 +                System.out.print(hex.substring(hex.length() - 2));
   1.396 +            }
   1.397 +            System.out.println(']');
   1.398 +
   1.399 +        } catch (IOException ex) {
   1.400 +            ex.printStackTrace();
   1.401 +        }
   1.402 +    }
   1.403 +}