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