    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.mylzw;
    018
    019import java.io.ByteArrayOutputStream;
    020import java.io.IOException;
    021import java.nio.ByteOrder;
    022import java.util.HashMap;
    023import java.util.Map;
    024
    025public class MyLzwCompressor {
    026    private int codeSize;
    027    private final int initialCodeSize;
    028    private int codes = -1;
    029
    030    private final ByteOrder byteOrder;
    031    private final boolean earlyLimit;
    032    private final int clearCode;
    033    private final int eoiCode;
    034    private final Listener listener;
    035    private final Map<ByteArray, Integer> map = new HashMap<>();
    036
    037    public MyLzwCompressor(final int initialCodeSize, final ByteOrder byteOrder,
    038            final boolean earlyLimit) {
    039        this(initialCodeSize, byteOrder, earlyLimit, null);
    040    }
    041
    042    public MyLzwCompressor(final int initialCodeSize, final ByteOrder byteOrder,
    043            final boolean earlyLimit, final Listener listener) {
    044        this.listener = listener;
    045        this.byteOrder = byteOrder;
    046        this.earlyLimit = earlyLimit;
    047
    048        this.initialCodeSize = initialCodeSize;
    049
    050        clearCode = 1 << initialCodeSize;
    051        eoiCode = clearCode + 1;
    052
    053        if (null != listener) {
    054            listener.init(clearCode, eoiCode);
    055        }
    056
    057        initializeStringTable();
    058    }
    059
    060    private void initializeStringTable() {
    061        codeSize = initialCodeSize;
    062
    063        final int initialEntriesCount = (1 << codeSize) + 2;
    064
    065        map.clear();
    066        for (codes = 0; codes < initialEntriesCount; codes++) {
    067            if ((codes != clearCode) && (codes != eoiCode)) {
    068                final ByteArray key = arrayToKey((byte) codes);
    069
    070                map.put(key, codes);
    071            }
    072        }
    073    }
    074
    075    private void clearTable() {
    076        initializeStringTable();
    077        incrementCodeSize();
    078    }
    079
    080    private void incrementCodeSize() {
    081        if (codeSize != 12) {
    082            codeSize++;
    083        }
    084    }
    085
    086    private ByteArray arrayToKey(final byte b) {
    087        return arrayToKey(new byte[] { b, }, 0, 1);
    088    }
    089
    090    private static final class ByteArray {
    091        private final byte[] bytes;
    092        private final int start;
    093        private final int length;
    094        private final int hash;
    095
    096        ByteArray(final byte[] bytes, final int start, final int length) {
    097            this.bytes = bytes;
    098            this.start = start;
    099            this.length = length;
    100
    101            int tempHash = length;
    102
    103            for (int i = 0; i < length; i++) {
    104                final int b = 0xff & bytes[i + start];
    105                tempHash = tempHash + (tempHash << 8) ^ b ^ i;
    106            }
    107
    108            hash = tempHash;
    109        }
    110
    111        @Override
    112        public int hashCode() {
    113            return hash;
    114        }
    115
    116        @Override
    117        public boolean equals(final Object o) {
    118            if (o instanceof ByteArray) {
    119                final ByteArray other = (ByteArray) o;
    120                if (other.hash != hash) {
    121                    return false;
    122                }
    123                if (other.length != length) {
    124                    return false;
    125                }
    126
    127                for (int i = 0; i < length; i++) {
    128                    if (other.bytes[i + other.start] != bytes[i + start]) {
    129                        return false;
    130                    }
    131                }
    132
    133                return true;
    134            }
    135            return false;
    136        }
    137    }
    138
    139    private ByteArray arrayToKey(final byte[] bytes, final int start, final int length) {
    140        return new ByteArray(bytes, start, length);
    141    }
    142
    143    private void writeDataCode(final MyBitOutputStream bos, final int code)
    144            throws IOException {
    145        if (null != listener) {
    146            listener.dataCode(code);
    147        }
    148        writeCode(bos, code);
    149    }
    150
    151    private void writeClearCode(final MyBitOutputStream bos) throws IOException {
    152        if (null != listener) {
    153            listener.dataCode(clearCode);
    154        }
    155        writeCode(bos, clearCode);
    156    }
    157
    158    private void writeEoiCode(final MyBitOutputStream bos) throws IOException {
    159        if (null != listener) {
    160            listener.eoiCode(eoiCode);
    161        }
    162        writeCode(bos, eoiCode);
    163    }
    164
    165    private void writeCode(final MyBitOutputStream bos, final int code)
    166            throws IOException {
    167        bos.writeBits(code, codeSize);
    168    }
    169
    170    private boolean isInTable(final byte[] bytes, final int start, final int length) {
    171        final ByteArray key = arrayToKey(bytes, start, length);
    172
    173        return map.containsKey(key);
    174    }
    175
    176    private int codeFromString(final byte[] bytes, final int start, final int length)
    177            throws IOException {
    178        final ByteArray key = arrayToKey(bytes, start, length);
    179        final Integer code = map.get(key);
    180        if (code == null) {
    181            throw new IOException("CodeFromString");
    182        }
    183        return code;
    184    }
    185
    186    private boolean addTableEntry(final MyBitOutputStream bos, final byte[] bytes,
    187            final int start, final int length) throws IOException {
    188        final ByteArray key = arrayToKey(bytes, start, length);
    189        return addTableEntry(bos, key);
    190    }
    191
    192    private boolean addTableEntry(final MyBitOutputStream bos, final ByteArray key)
    193            throws IOException {
    194        boolean cleared = false;
    195
    196        int limit = (1 << codeSize);
    197        if (earlyLimit) {
    198            limit--;
    199        }
    200
    201        if (codes == limit) {
    202            if (codeSize < 12) {
    203                incrementCodeSize();
    204            } else {
    205                writeClearCode(bos);
    206                clearTable();
    207                cleared = true;
    208            }
    209        }
    210
    211        if (!cleared) {
    212            map.put(key, codes);
    213            codes++;
    214        }
    215
    216        return cleared;
    217    }
    218
    219    public interface Listener {
    220        void dataCode(int code);
    221
    222        void eoiCode(int code);
    223
    224        void clearCode(int code);
    225
    226        void init(int clearCode, int eoiCode);
    227    }
    228
    229    public byte[] compress(final byte[] bytes) throws IOException {
    230        final ByteArrayOutputStream baos = new ByteArrayOutputStream(bytes.length);
    231        final MyBitOutputStream bos = new MyBitOutputStream(baos, byteOrder);
    232
    233        initializeStringTable();
    234        clearTable();
    235        writeClearCode(bos);
    236
    237        int wStart = 0;
    238        int wLength = 0;
    239
    240        for (int i = 0; i < bytes.length; i++) {
    241            if (isInTable(bytes, wStart, wLength + 1)) {
    242                wLength++;
    243            } else {
    244                final int code = codeFromString(bytes, wStart, wLength);
    245                writeDataCode(bos, code);
    246                addTableEntry(bos, bytes, wStart, wLength + 1);
    247
    248                wStart = i;
    249                wLength = 1;
    250            }
    251        }
    252
    253        final int code = codeFromString(bytes, wStart, wLength);
    254        writeDataCode(bos, code);
    255
    256        writeEoiCode(bos);
    257
    258        bos.flushCache();
    259
    260        return baos.toByteArray();
    261    }
    262}