/*
    * Licensed to the Apache Software Foundation (ASF) under one
    * or more contributor license agreements.  See the NOTICE file
    * distributed with this work for additional information
    * regarding copyright ownership.  The ASF licenses this file
    * to you under the Apache License, Version 2.0 (the
    * "License"); you may not use this file except in compliance
    * with the License.  You may obtain a copy of the License at
    *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing,
   * software distributed under the License is distributed on an
   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
   * KIND, either express or implied.  See the License for the
   * specific language governing permissions and limitations
   * under the License.
   */
  package org.apache.commons.compress.compressors.lz77support;
  
  import java.io.IOException;
  import java.util.Objects;
  
  import org.apache.commons.lang3.ArrayFill;
  
  /**
   * Helper class for compression algorithms that use the ideas of LZ77.
   *
   * <p>
   * Most LZ77 derived algorithms split input data into blocks of uncompressed data (called literal blocks) and back-references (pairs of offsets and lengths)
   * that state "add {@code length} bytes that are the same as those already written starting {@code offset} bytes before the current position. The details of how
   * those blocks and back-references are encoded are quite different between the algorithms and some algorithms perform additional steps (Huffman encoding in the
   * case of DEFLATE for example).
   * </p>
   *
   * <p>
   * This class attempts to extract the core logic - finding back-references - so it can be re-used. It follows the algorithm explained in section 4 of RFC 1951
   * (DEFLATE) and currently doesn't implement the "lazy match" optimization. The three-byte hash function used in this class is the same as the one used by zlib
   * and InfoZIP's ZIP implementation of DEFLATE. The whole class is strongly inspired by InfoZIP's implementation.
   * </p>
   *
   * <p>
   * LZ77 is used vaguely here (as well as many other places that talk about it :-), LZSS would likely be closer to the truth but LZ77 has become the synonym for
   * a whole family of algorithms.
   * </p>
   *
   * <p>
   * The API consists of a compressor that is fed {@code byte}s and emits {@link Block}s to a registered callback where the blocks represent either
   * {@link LiteralBlock literal blocks}, {@link BackReference back-references} or {@link EOD end of data markers}. In order to ensure the callback receives all
   * information, the {@code #finish} method must be used once all data has been fed into the compressor.
   * </p>
   *
   * <p>
   * Several parameters influence the outcome of the "compression":
   * </p>
   * <dl>
   *
   * <dt>{@code windowSize}</dt>
   * <dd>the size of the sliding window, must be a power of two - this determines the maximum offset a back-reference can take. The compressor maintains a buffer
   * of twice of {@code windowSize} - real world values are in the area of 32k.</dd>
   *
   * <dt>{@code minBackReferenceLength}</dt>
   * <dd>Minimal length of a back-reference found. A true minimum of 3 is hard-coded inside of this implementation but bigger lengths can be configured.</dd>
   *
   * <dt>{@code maxBackReferenceLength}</dt>
   * <dd>Maximal length of a back-reference found.</dd>
   *
   * <dt>{@code maxOffset}</dt>
   * <dd>Maximal offset of a back-reference.</dd>
   *
   * <dt>{@code maxLiteralLength}</dt>
   * <dd>Maximal length of a literal block.</dd>
   * </dl>
   *
   * @see "https://tools.ietf.org/html/rfc1951#section-4"
   * @since 1.14
   * @NotThreadSafe
   */
  public class LZ77Compressor {
  
      /**
       * Represents a back-reference.
       */
      public static final class BackReference extends Block {
          private final int offset, length;
  
          public BackReference(final int offset, final int length) {
              this.offset = offset;
              this.length = length;
          }
  
          /**
           * Provides the length of the back-reference.
           *
           * @return the length
           */
          public int getLength() {
              return length;
          }
 
         /**
          * Provides the offset of the back-reference.
          *
          * @return the offset
          */
         public int getOffset() {
             return offset;
         }
 
         @Override
         public BlockType getType() {
             return BlockType.BACK_REFERENCE;
         }
 
         @Override
         public String toString() {
             return "BackReference with offset " + offset + " and length " + length;
         }
     }
 
     /**
      * Base class representing blocks the compressor may emit.
      *
      * <p>
      * This class is not supposed to be subclassed by classes outside of Commons Compress so it is considered internal and changed that would break subclasses
      * may get introduced with future releases.
      * </p>
      */
     public abstract static class Block {
         /** Enumeration of the block types the compressor may emit. */
         public enum BlockType {
             LITERAL, BACK_REFERENCE, EOD
         }
 
         public abstract BlockType getType();
     }
 
     /**
      * Callback invoked while the compressor processes data.
      *
      * <p>
      * The callback is invoked on the same thread that receives the bytes to compress and may be invoked multiple times during the execution of
      * {@link #compress} or {@link #finish}.
      * </p>
      */
     public interface Callback {
         /**
          * Consumes a block.
          *
          * @param b the block to consume
          * @throws IOException in case of an error
          */
         void accept(Block b) throws IOException;
     }
 
     /** A simple "we are done" marker. */
     public static final class EOD extends Block {
         @Override
         public BlockType getType() {
             return BlockType.EOD;
         }
     }
 
     /**
      * Represents a literal block of data.
      *
      * <p>
      * For performance reasons this encapsulates the real data, not a copy of it. Don't modify the data and process it inside of {@link Callback#accept}
      * immediately as it will get overwritten sooner or later.
      * </p>
      */
     public static final class LiteralBlock extends Block {
         private final byte[] data;
         private final int offset, length;
 
         public LiteralBlock(final byte[] data, final int offset, final int length) {
             this.data = data;
             this.offset = offset;
             this.length = length;
         }
 
         /**
          * The literal data.
          *
          * <p>
          * This returns a life view of the actual data in order to avoid copying, modify the array at your own risk.
          * </p>
          *
          * @return the data
          */
         public byte[] getData() {
             return data;
         }
 
         /**
          * Length of literal block.
          *
          * @return the length
          */
         public int getLength() {
             return length;
         }
 
         /**
          * Offset into data where the literal block starts.
          *
          * @return the offset
          */
         public int getOffset() {
             return offset;
         }
 
         @Override
         public BlockType getType() {
             return BlockType.LITERAL;
         }
 
         @Override
         public String toString() {
             return "LiteralBlock starting at " + offset + " with length " + length;
         }
     }
 
     private static final Block THE_EOD = new EOD();
 
     static final int NUMBER_OF_BYTES_IN_HASH = 3;
     private static final int NO_MATCH = -1;
 
     // we use a 15 bit hash code as calculated in updateHash
     private static final int HASH_SIZE = 1 << 15;
     private static final int HASH_MASK = HASH_SIZE - 1;
 
     private static final int H_SHIFT = 5;
     private final Parameters params;
     private final Callback callback;
 
     // the sliding window, twice as big as "windowSize" parameter
     private final byte[] window;
 
     // the head of hash-chain - indexed by hash-code, points to the
     // location inside of window of the latest sequence of bytes with
     // the given hash.
     private final int[] head;
     // for each window-location points to the latest earlier location
     // with the same hash. Only stores values for the latest
     // "windowSize" elements, the index is "window location modulo
     // windowSize".
     private final int[] prev;
     // bit mask used when indexing into prev
     private final int wMask;
     private boolean initialized;
     // the position inside of window that shall be encoded right now
     private int currentPosition;
     // the number of bytes available to compress including the one at
     // currentPosition
     private int lookahead;
     // the hash of the three bytes stating at the current position
     private int insertHash;
 
     // the position inside the window where the current literal
     // block starts (in case we are inside a literal block).
     private int blockStart;
 
     // position of the current match
     private int matchStart = NO_MATCH;
 
     // number of missed insertString calls for the up to three last
     // bytes of the last match that can only be performed once more
     // data has been read
     private int missedInserts;
 
     /**
      * Initializes a compressor with parameters and a callback.
      *
      * @param params   the parameters
      * @param callback the callback
      * @throws NullPointerException if either parameter is {@code null}
      */
     public LZ77Compressor(final Parameters params, final Callback callback) {
         Objects.requireNonNull(params, "params");
         Objects.requireNonNull(callback, "callback");
 
         this.params = params;
         this.callback = callback;
 
         final int wSize = params.getWindowSize();
         window = new byte[wSize * 2];
         wMask = wSize - 1;
         head = ArrayFill.fill(new int[HASH_SIZE], NO_MATCH);
         prev = new int[wSize];
     }
 
     private void catchUpMissedInserts() {
         while (missedInserts > 0) {
             insertString(currentPosition - missedInserts--);
         }
     }
 
     private void compress() throws IOException {
         final int minMatch = params.getMinBackReferenceLength();
         final boolean lazy = params.getLazyMatching();
         final int lazyThreshold = params.getLazyMatchingThreshold();
 
         while (lookahead >= minMatch) {
             catchUpMissedInserts();
             int matchLength = 0;
             final int hashHead = insertString(currentPosition);
             if (hashHead != NO_MATCH && hashHead - currentPosition <= params.getMaxOffset()) {
                 // sets matchStart as a side effect
                 matchLength = longestMatch(hashHead);
 
                 if (lazy && matchLength <= lazyThreshold && lookahead > minMatch) {
                     // try to find a longer match using the next position
                     matchLength = longestMatchForNextPosition(matchLength);
                 }
             }
             if (matchLength >= minMatch) {
                 if (blockStart != currentPosition) {
                     // emit preceding literal block
                     flushLiteralBlock();
                     blockStart = NO_MATCH;
                 }
                 flushBackReference(matchLength);
                 insertStringsInMatch(matchLength);
                 lookahead -= matchLength;
                 currentPosition += matchLength;
                 blockStart = currentPosition;
             } else {
                 // no match, append to current or start a new literal
                 lookahead--;
                 currentPosition++;
                 if (currentPosition - blockStart >= params.getMaxLiteralLength()) {
                     flushLiteralBlock();
                     blockStart = currentPosition;
                 }
             }
         }
     }
 
     /**
      * Feeds bytes into the compressor which in turn may emit zero or more blocks to the callback during the execution of this method.
      *
      * @param data the data to compress - must not be null
      * @throws IOException if the callback throws an exception
      */
     public void compress(final byte[] data) throws IOException {
         compress(data, 0, data.length);
     }
 
     /**
      * Feeds bytes into the compressor which in turn may emit zero or more blocks to the callback during the execution of this method.
      *
      * @param data the data to compress - must not be null
      * @param off  the start offset of the data
      * @param len  the number of bytes to compress
      * @throws IOException if the callback throws an exception
      */
     public void compress(final byte[] data, int off, int len) throws IOException {
         final int wSize = params.getWindowSize();
         while (len > wSize) { // chop into windowSize sized chunks
             doCompress(data, off, wSize);
             off += wSize;
             len -= wSize;
         }
         if (len > 0) {
             doCompress(data, off, len);
         }
     }
 
     // performs the actual algorithm with the pre-condition len <= windowSize
     private void doCompress(final byte[] data, final int off, final int len) throws IOException {
         final int spaceLeft = window.length - currentPosition - lookahead;
         if (len > spaceLeft) {
             slide();
         }
         System.arraycopy(data, off, window, currentPosition + lookahead, len);
         lookahead += len;
         if (!initialized && lookahead >= params.getMinBackReferenceLength()) {
             initialize();
         }
         if (initialized) {
             compress();
         }
     }
 
     /**
      * Tells the compressor to process all remaining data and signal end of data to the callback.
      *
      * <p>
      * The compressor will in turn emit at least one block ({@link EOD}) but potentially multiple blocks to the callback during the execution of this method.
      * </p>
      *
      * @throws IOException if the callback throws an exception
      */
     public void finish() throws IOException {
         if (blockStart != currentPosition || lookahead > 0) {
             currentPosition += lookahead;
             flushLiteralBlock();
         }
         callback.accept(THE_EOD);
     }
 
     private void flushBackReference(final int matchLength) throws IOException {
         callback.accept(new BackReference(currentPosition - matchStart, matchLength));
     }
 
     private void flushLiteralBlock() throws IOException {
         callback.accept(new LiteralBlock(window, blockStart, currentPosition - blockStart));
     }
 
     private void initialize() {
         for (int i = 0; i < NUMBER_OF_BYTES_IN_HASH - 1; i++) {
             insertHash = nextHash(insertHash, window[i]);
         }
         initialized = true;
     }
 
     /**
      * Inserts the current three byte sequence into the dictionary and returns the previous head of the hash-chain.
      *
      * <p>
      * Updates {@code insertHash} and {@code prev} as a side effect.
      * </p>
      */
     private int insertString(final int pos) {
         insertHash = nextHash(insertHash, window[pos - 1 + NUMBER_OF_BYTES_IN_HASH]);
         final int hashHead = head[insertHash];
         prev[pos & wMask] = hashHead;
         head[insertHash] = pos;
         return hashHead;
     }
 
     private void insertStringsInMatch(final int matchLength) {
         // inserts strings contained in current match
         // insertString inserts the byte 2 bytes after position, which may not yet be available -> missedInserts
         final int stop = Math.min(matchLength - 1, lookahead - NUMBER_OF_BYTES_IN_HASH);
         // currentPosition has been inserted already
         for (int i = 1; i <= stop; i++) {
             insertString(currentPosition + i);
         }
         missedInserts = matchLength - stop - 1;
     }
 
     /**
      * Searches the hash chain for real matches and returns the length of the longest match (0 if none were found) that isn't too far away (WRT maxOffset).
      *
      * <p>
      * Sets matchStart to the index of the start position of the longest match as a side effect.
      * </p>
      */
     private int longestMatch(int matchHead) {
         final int minLength = params.getMinBackReferenceLength();
         int longestMatchLength = minLength - 1;
         final int maxPossibleLength = Math.min(params.getMaxBackReferenceLength(), lookahead);
         final int minIndex = Math.max(0, currentPosition - params.getMaxOffset());
         final int niceBackReferenceLength = Math.min(maxPossibleLength, params.getNiceBackReferenceLength());
         final int maxCandidates = params.getMaxCandidates();
         for (int candidates = 0; candidates < maxCandidates && matchHead >= minIndex; candidates++) {
             int currentLength = 0;
             for (int i = 0; i < maxPossibleLength; i++) {
                 if (window[matchHead + i] != window[currentPosition + i]) {
                     break;
                 }
                 currentLength++;
             }
             if (currentLength > longestMatchLength) {
                 longestMatchLength = currentLength;
                 matchStart = matchHead;
                 if (currentLength >= niceBackReferenceLength) {
                     // no need to search any further
                     break;
                 }
             }
             matchHead = prev[matchHead & wMask];
         }
         return longestMatchLength; // < minLength if no matches have been found, will be ignored in compress()
     }
 
     private int longestMatchForNextPosition(final int prevMatchLength) {
         // save a bunch of values to restore them if the next match isn't better than the current one
         final int prevMatchStart = matchStart;
         final int prevInsertHash = insertHash;
 
         lookahead--;
         currentPosition++;
         final int hashHead = insertString(currentPosition);
         final int prevHashHead = prev[currentPosition & wMask];
         int matchLength = longestMatch(hashHead);
 
         if (matchLength <= prevMatchLength) {
             // use the first match, as the next one isn't any better
             matchLength = prevMatchLength;
             matchStart = prevMatchStart;
 
             // restore modified values
             head[insertHash] = prevHashHead;
             insertHash = prevInsertHash;
             currentPosition--;
             lookahead++;
         }
         return matchLength;
     }
 
     /**
      * Assumes we are calculating the hash for three consecutive bytes as a rolling hash, i.e. for bytes ABCD if H is the hash of ABC the new hash for BCD is
      * nextHash(H, D).
      *
      * <p>
      * The hash is shifted by five bits on each update so all effects of A have been swapped after the third update.
      * </p>
      */
     private int nextHash(final int oldHash, final byte nextByte) {
         final int nextVal = nextByte & 0xFF;
         return (oldHash << H_SHIFT ^ nextVal) & HASH_MASK;
     }
 
     /**
      * Adds some initial data to fill the window with.
      *
      * <p>
      * This is used if the stream has been cut into blocks and back-references of one block may refer to data of the previous block(s). One such example is the
      * LZ4 frame format using block dependency.
      * </p>
      *
      * @param data the data to fill the window with.
      * @throws IllegalStateException if the compressor has already started to accept data
      */
     public void prefill(final byte[] data) {
         if (currentPosition != 0 || lookahead != 0) {
             throw new IllegalStateException("The compressor has already started to accept data, can't prefill anymore");
         }
 
         // don't need more than windowSize for back-references
         final int len = Math.min(params.getWindowSize(), data.length);
         System.arraycopy(data, data.length - len, window, 0, len);
 
         if (len >= NUMBER_OF_BYTES_IN_HASH) {
             initialize();
             final int stop = len - NUMBER_OF_BYTES_IN_HASH + 1;
             for (int i = 0; i < stop; i++) {
                 insertString(i);
             }
             missedInserts = NUMBER_OF_BYTES_IN_HASH - 1;
         } else { // not enough data to hash anything
             missedInserts = len;
         }
         blockStart = currentPosition = len;
     }
 
     private void slide() throws IOException {
         final int wSize = params.getWindowSize();
         if (blockStart != currentPosition && blockStart < wSize) {
             flushLiteralBlock();
             blockStart = currentPosition;
         }
         System.arraycopy(window, wSize, window, 0, wSize);
         currentPosition -= wSize;
         matchStart -= wSize;
         blockStart -= wSize;
         for (int i = 0; i < HASH_SIZE; i++) {
             final int h = head[i];
             head[i] = h >= wSize ? h - wSize : NO_MATCH;
         }
         for (int i = 0; i < wSize; i++) {
             final int p = prev[i];
             prev[i] = p >= wSize ? p - wSize : NO_MATCH;
         }
     }
 }