001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.imaging.common;
018
019import java.io.ByteArrayOutputStream;
020import java.io.IOException;
021
022import org.apache.commons.imaging.ImagingException;
023import org.apache.commons.io.output.UnsynchronizedByteArrayOutputStream;
024
025public final class PackBits {
026
027    public static byte[] compress(final byte[] bytes) throws IOException {
028        // max length 1 extra byte for every 128
029        try (UnsynchronizedByteArrayOutputStream baos = UnsynchronizedByteArrayOutputStream.builder().setBufferSize(Allocator.checkByteArray(bytes.length * 2))
030                .get()) {
031            int ptr = 0;
032            while (ptr < bytes.length) {
033                int dup = findNextDuplicate(bytes, ptr);
034
035                if (dup == ptr) {
036                    // write run length
037                    final int len = findRunLength(bytes, dup);
038                    final int actualLen = Math.min(len, 128);
039                    baos.write(-(actualLen - 1));
040                    baos.write(bytes[ptr]);
041                    ptr += actualLen;
042                } else {
043                    // write literals
044                    int len = dup - ptr;
045
046                    if (dup > 0) {
047                        final int runlen = findRunLength(bytes, dup);
048                        if (runlen < 3) {
049                            // may want to discard next run.
050                            final int nextptr = ptr + len + runlen;
051                            final int nextdup = findNextDuplicate(bytes, nextptr);
052                            if (nextdup != nextptr) {
053                                // discard 2-byte run
054                                dup = nextdup;
055                                len = dup - ptr;
056                            }
057                        }
058                    }
059
060                    if (dup < 0) {
061                        len = bytes.length - ptr;
062                    }
063                    final int actualLen = Math.min(len, 128);
064
065                    baos.write(actualLen - 1);
066                    for (int i = 0; i < actualLen; i++) {
067                        baos.write(bytes[ptr]);
068                        ptr++;
069                    }
070                }
071            }
072            return baos.toByteArray();
073        }
074    }
075
076    public static byte[] decompress(final byte[] bytes, final int expected) throws ImagingException {
077        int total = 0;
078
079        final ByteArrayOutputStream baos = new ByteArrayOutputStream();
080
081        // Loop until you get the number of unpacked bytes you are expecting:
082        int i = 0;
083        while (total < expected) {
084            // Read the next source byte into n.
085            if (i >= bytes.length) {
086                throw new ImagingException("Tiff: Unpack bits source exhausted: " + i + ", done + " + total + ", expected + " + expected);
087            }
088
089            final int n = bytes[i++];
090            if (n >= 0 && n <= 127) {
091                // If n is between 0 and 127 inclusive, copy the next n+1 bytes
092                // literally.
093                final int count = n + 1;
094
095                total += count;
096                for (int j = 0; j < count; j++) {
097                    baos.write(bytes[i++]);
098                }
099            } else if (n >= -127 && n <= -1) {
100                // Else if n is between -127 and -1 inclusive, copy the next byte
101                // -n+1 times.
102
103                final int b = bytes[i++];
104                final int count = -n + 1;
105
106                total += count;
107                for (int j = 0; j < count; j++) {
108                    baos.write(b);
109                }
110            } else if (n == -128) {
111                // Else if n is -128, noop.
112                throw new ImagingException("Packbits: " + n);
113            }
114        }
115
116        return baos.toByteArray();
117
118    }
119
120    private static int findNextDuplicate(final byte[] bytes, final int start) {
121        // int last = -1;
122        if (start >= bytes.length) {
123            return -1;
124        }
125
126        byte prev = bytes[start];
127
128        for (int i = start + 1; i < bytes.length; i++) {
129            final byte b = bytes[i];
130
131            if (b == prev) {
132                return i - 1;
133            }
134
135            prev = b;
136        }
137
138        return -1;
139    }
140
141    private static int findRunLength(final byte[] bytes, final int start) {
142        final byte b = bytes[start];
143
144        int i;
145
146        for (i = start + 1; i < bytes.length && bytes[i] == b; i++) {
147            // do nothing
148        }
149
150        return i - start;
151    }
152
153    private PackBits() {
154        // empty
155    }
156}