/*
    * This file is part of Waarp Project (named also Waarp or GG).
    *
    *  Copyright (c) 2019, Waarp SAS, and individual contributors by the @author
    *  tags. See the COPYRIGHT.txt in the distribution for a full listing of
    * individual contributors.
    *
    *  All Waarp Project is free software: you can redistribute it and/or
    * modify it under the terms of the GNU General Public License as published by
   * the Free Software Foundation, either version 3 of the License, or (at your
   * option) any later version.
   *
   * Waarp is distributed in the hope that it will be useful, but WITHOUT ANY
   * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
   * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
   *
   *  You should have received a copy of the GNU General Public License along with
   * Waarp . If not, see <http://www.gnu.org/licenses/>.
   */
  
  /*
   * Licensed 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.waarp.compress.zstdsafe;
  
  import static org.waarp.compress.zstdsafe.Constants.*;
  import static org.waarp.compress.zstdsafe.Huffman.*;
  import static org.waarp.compress.zstdsafe.UnsafeUtil.*;
  import static org.waarp.compress.zstdsafe.Util.*;
  
  class ZstdFrameCompressor {
    static final int MAX_FRAME_HEADER_SIZE = 14;
  
    private static final int CHECKSUM_FLAG = 0x4;
    private static final int SINGLE_SEGMENT_FLAG = 0x20;
  
    private static final int MINIMUM_LITERALS_SIZE = 63;
  
    // the maximum table log allowed for literal encoding per RFC 8478, section 4.2.1
    private static final int MAX_HUFFMAN_TABLE_LOG = 11;
    public static final String OUTPUT_BUFFER_TOO_SMALL =
        "Output buffer too small";
  
    private ZstdFrameCompressor() {
    }
  
    // visible for testing
    static int writeMagic(final byte[] outputBase, final int outputAddress,
                          final int outputLimit) {
      checkArgument(outputLimit - outputAddress >= SIZE_OF_INT,
                    OUTPUT_BUFFER_TOO_SMALL);
  
      putInt(outputBase, outputAddress, MAGIC_NUMBER);
      return SIZE_OF_INT;
    }
  
    // visible for testing
    static int writeFrameHeader(final byte[] outputBase, final int outputAddress,
                                final int outputLimit, final int inputSize,
                                final int windowSize) {
      checkArgument(outputLimit - outputAddress >= MAX_FRAME_HEADER_SIZE,
                    OUTPUT_BUFFER_TOO_SMALL);
  
      int output = outputAddress;
  
      final int contentSizeDescriptor =
          (inputSize >= 256? 1 : 0) + (inputSize >= 65536 + 256? 1 : 0);
      int frameHeaderDescriptor =
          (contentSizeDescriptor << 6) | CHECKSUM_FLAG; // dictionary ID missing
  
      final boolean singleSegment = windowSize >= inputSize;
      if (singleSegment) {
        frameHeaderDescriptor |= SINGLE_SEGMENT_FLAG;
      }
  
      outputBase[output] = (byte) frameHeaderDescriptor;
      output++;
  
      if (!singleSegment) {
        final int base = Integer.highestOneBit(windowSize);
  
        final int exponent = 32 - Integer.numberOfLeadingZeros(base) - 1;
        if (exponent < MIN_WINDOW_LOG) {
          throw new IllegalArgumentException(
              "Minimum window size is " + (1 << MIN_WINDOW_LOG));
        }
  
        final int remainder = windowSize - base;
        if (remainder % (base / 8) != 0) {
         throw new IllegalArgumentException(
             "Window size of magnitude 2^" + exponent + " must be multiple of " +
             (base / 8));
       }
 
       // mantissa is guaranteed to be between 0-7
       final int mantissa = remainder / (base / 8);
       final int encoded = ((exponent - MIN_WINDOW_LOG) << 3) | mantissa;
 
       outputBase[output] = (byte) encoded;
       output++;
     }
 
     switch (contentSizeDescriptor) {
       case 0:
         if (singleSegment) {
           outputBase[output++] = (byte) inputSize;
         }
         break;
       case 1:
         putShort(outputBase, output, (short) (inputSize - 256));
         output += SIZE_OF_SHORT;
         break;
       case 2:
         putInt(outputBase, output, inputSize);
         output += SIZE_OF_INT;
         break;
       default:
         throw new AssertionError();
     }
 
     return output - outputAddress;
   }
 
   // visible for testing
   static int writeChecksum(final byte[] outputBase, final int outputAddress,
                            final int outputLimit, final byte[] inputBase,
                            final int inputAddress, final int inputLimit) {
     checkArgument(outputLimit - outputAddress >= SIZE_OF_INT,
                   OUTPUT_BUFFER_TOO_SMALL);
 
     final int inputSize = inputLimit - inputAddress;
 
     final long hash = XxHash64.hash(0, inputBase, inputAddress, inputSize);
 
     putInt(outputBase, outputAddress, (int) hash);
 
     return SIZE_OF_INT;
   }
 
   public static int compress(final byte[] inputBase, final int inputAddress,
                              final int inputLimit, final byte[] outputBase,
                              final int outputAddress, final int outputLimit,
                              final int compressionLevel) {
     final int inputSize = inputLimit - inputAddress;
 
     final CompressionParameters parameters =
         CompressionParameters.compute(compressionLevel, inputSize);
 
     int output = outputAddress;
 
     output += writeMagic(outputBase, output, outputLimit);
     output += writeFrameHeader(outputBase, output, outputLimit, inputSize,
                                1 << parameters.getWindowLog());
     output +=
         compressFrame(inputBase, inputAddress, inputLimit, outputBase, output,
                       outputLimit, parameters);
     output +=
         writeChecksum(outputBase, output, outputLimit, inputBase, inputAddress,
                       inputLimit);
 
     return output - outputAddress;
   }
 
   private static int compressFrame(final byte[] inputBase,
                                    final int inputAddress, final int inputLimit,
                                    final byte[] outputBase,
                                    final int outputAddress,
                                    final int outputLimit,
                                    final CompressionParameters parameters) {
     final int windowSize = 1 <<
                            parameters.getWindowLog(); // TODO: store window size in parameters directly?
     int blockSize = Math.min(MAX_BLOCK_SIZE, windowSize);
 
     int outputSize = outputLimit - outputAddress;
     int remaining = inputLimit - inputAddress;
 
     int output = outputAddress;
     int input = inputAddress;
 
     final CompressionContext context =
         new CompressionContext(parameters, inputAddress, remaining);
 
     do {
       checkArgument(outputSize >= SIZE_OF_BLOCK_HEADER + MIN_BLOCK_SIZE,
                     OUTPUT_BUFFER_TOO_SMALL);
 
       final int lastBlockFlag = blockSize >= remaining? 1 : 0;
       blockSize = Math.min(blockSize, remaining);
 
       int compressedSize = 0;
       if (remaining > 0) {
         compressedSize = compressBlock(inputBase, input, blockSize, outputBase,
                                        output + SIZE_OF_BLOCK_HEADER,
                                        outputSize - SIZE_OF_BLOCK_HEADER,
                                        context, parameters);
       }
 
       if (compressedSize == 0) { // block is not compressible
         checkArgument(blockSize + SIZE_OF_BLOCK_HEADER <= outputSize,
                       "Output size too small");
 
         final int blockHeader =
             lastBlockFlag | (RAW_BLOCK << 1) | (blockSize << 3);
         put24BitLittleEndian(outputBase, output, blockHeader);
         copyMemory(inputBase, input, outputBase, output + SIZE_OF_BLOCK_HEADER,
                    blockSize);
         compressedSize = SIZE_OF_BLOCK_HEADER + blockSize;
       } else {
         final int blockHeader =
             lastBlockFlag | (COMPRESSED_BLOCK << 1) | (compressedSize << 3);
         put24BitLittleEndian(outputBase, output, blockHeader);
         compressedSize += SIZE_OF_BLOCK_HEADER;
       }
 
       input += blockSize;
       remaining -= blockSize;
       output += compressedSize;
       outputSize -= compressedSize;
     } while (remaining > 0);
 
     return output - outputAddress;
   }
 
   private static int compressBlock(final byte[] inputBase,
                                    final int inputAddress, final int inputSize,
                                    final byte[] outputBase,
                                    final int outputAddress,
                                    final int outputSize,
                                    final CompressionContext context,
                                    final CompressionParameters parameters) {
     if (inputSize < MIN_BLOCK_SIZE + SIZE_OF_BLOCK_HEADER + 1) {
       //  don't even attempt compression below a certain input size
       return 0;
     }
 
     context.blockCompressionState.enforceMaxDistance(inputAddress + inputSize,
                                                      1 <<
                                                      parameters.getWindowLog());
     context.sequenceStore.reset();
 
     final int lastLiteralsSize = parameters.getStrategy().getCompressor()
                                            .compressBlock(inputBase,
                                                           inputAddress,
                                                           inputSize,
                                                           context.sequenceStore,
                                                           context.blockCompressionState,
                                                           context.offsets,
                                                           parameters);
 
     final int lastLiteralsAddress = inputAddress + inputSize - lastLiteralsSize;
 
     // append [lastLiteralsAddress .. lastLiteralsSize] to sequenceStore literals buffer
     context.sequenceStore.appendLiterals(inputBase, lastLiteralsAddress,
                                          lastLiteralsSize);
 
     // convert length/offsets into codes
     context.sequenceStore.generateCodes();
 
     final int outputLimit = outputAddress + outputSize;
     int output = outputAddress;
 
     final int compressedLiteralsSize =
         encodeLiterals(context.huffmanContext, parameters, outputBase, output,
                        outputLimit - output,
                        context.sequenceStore.literalsBuffer,
                        context.sequenceStore.literalsLength);
     output += compressedLiteralsSize;
 
     final int compressedSequencesSize =
         SequenceEncoder.compressSequences(outputBase, output,
                                           outputLimit - output,
                                           context.sequenceStore,
                                           parameters.getStrategy(),
                                           context.sequenceEncodingContext);
 
     final int compressedSize = compressedLiteralsSize + compressedSequencesSize;
     if (compressedSize == 0) {
       // not compressible
       return compressedSize;
     }
 
     // Check compressibility
     final int maxCompressedSize =
         inputSize - calculateMinimumGain(inputSize, parameters.getStrategy());
     if (compressedSize > maxCompressedSize) {
       return 0; // not compressed
     }
 
     // confirm repeated offsets and entropy tables
     context.commit();
 
     return compressedSize;
   }
 
   private static int encodeLiterals(final HuffmanCompressionContext context,
                                     final CompressionParameters parameters,
                                     final byte[] outputBase,
                                     final int outputAddress,
                                     final int outputSize, final byte[] literals,
                                     final int literalsSize) {
     // TODO: move this to Strategy
     final boolean bypassCompression =
         (parameters.getStrategy() == CompressionParameters.Strategy.FAST) &&
         (parameters.getTargetLength() > 0);
     if (bypassCompression || literalsSize <= MINIMUM_LITERALS_SIZE) {
       return rawLiterals(outputBase, outputAddress, outputSize, literals,
                          literalsSize);
     }
 
     final int headerSize =
         3 + (literalsSize >= 1024? 1 : 0) + (literalsSize >= 16384? 1 : 0);
 
     checkArgument(headerSize + 1 <= outputSize, OUTPUT_BUFFER_TOO_SMALL);
 
     final int[] counts = new int[MAX_SYMBOL_COUNT]; // TODO: preallocate
     Histogram.count(literals, literalsSize, counts);
     final int maxSymbol = Histogram.findMaxSymbol(counts, MAX_SYMBOL);
     final int largestCount = Histogram.findLargestCount(counts, maxSymbol);
 
     final int literalsAddress = 0;
     if (largestCount == literalsSize) {
       // all bytes in input are equal
       return rleLiterals(outputBase, outputAddress, literals, literalsSize);
     } else if (largestCount <= (literalsSize >>> 7) + 4) {
       // heuristic: probably not compressible enough
       return rawLiterals(outputBase, outputAddress, outputSize, literals,
                          literalsSize);
     }
 
     final HuffmanCompressionTable previousTable = context.getPreviousTable();
     final HuffmanCompressionTable table;
     int serializedTableSize;
     final boolean reuseTable;
 
     final boolean canReuse = previousTable.isValid(counts, maxSymbol);
 
     // heuristic: use existing table for small inputs if valid
     // TODO: move to Strategy
     final boolean preferReuse = parameters.getStrategy().ordinal() <
                                 CompressionParameters.Strategy.LAZY.ordinal() &&
                                 literalsSize <= 1024;
     if (preferReuse && canReuse) {
       table = previousTable;
       reuseTable = true;
       serializedTableSize = 0;
     } else {
       final HuffmanCompressionTable newTable = context.borrowTemporaryTable();
 
       newTable.initialize(counts, maxSymbol,
                           HuffmanCompressionTable.optimalNumberOfBits(
                               MAX_HUFFMAN_TABLE_LOG, literalsSize, maxSymbol),
                           context.getCompressionTableWorkspace());
 
       serializedTableSize =
           newTable.write(outputBase, outputAddress + headerSize,
                          outputSize - headerSize,
                          context.getTableWriterWorkspace());
 
       // Check if using previous huffman table is beneficial
       if (canReuse && previousTable.estimateCompressedSize(counts, maxSymbol) <=
                       serializedTableSize +
                       newTable.estimateCompressedSize(counts, maxSymbol)) {
         table = previousTable;
         reuseTable = true;
         serializedTableSize = 0;
         context.discardTemporaryTable();
       } else {
         table = newTable;
         reuseTable = false;
       }
     }
 
     final int compressedSize;
     final boolean singleStream = literalsSize < 256;
     if (singleStream) {
       compressedSize = HuffmanCompressor.compressSingleStream(outputBase,
                                                               outputAddress +
                                                               headerSize +
                                                               serializedTableSize,
                                                               outputSize -
                                                               headerSize -
                                                               serializedTableSize,
                                                               literals,
                                                               literalsAddress,
                                                               literalsSize,
                                                               table);
     } else {
       compressedSize = HuffmanCompressor.compress4streams(outputBase,
                                                           outputAddress +
                                                           headerSize +
                                                           serializedTableSize,
                                                           outputSize -
                                                           headerSize -
                                                           serializedTableSize,
                                                           literals,
                                                           literalsAddress,
                                                           literalsSize, table);
     }
 
     final int totalSize = serializedTableSize + compressedSize;
     final int minimumGain =
         calculateMinimumGain(literalsSize, parameters.getStrategy());
 
     if (compressedSize == 0 || totalSize >= literalsSize - minimumGain) {
       // incompressible or no savings
 
       // discard any temporary table we might have borrowed above
       context.discardTemporaryTable();
 
       return rawLiterals(outputBase, outputAddress, outputSize, literals,
                          literalsSize);
     }
 
     final int encodingType =
         reuseTable? TREELESS_LITERALS_BLOCK : COMPRESSED_LITERALS_BLOCK;
 
     // Build header
     switch (headerSize) {
       case 3: { // 2 - 2 - 10 - 10
         final int header =
             encodingType | ((singleStream? 0 : 1) << 2) | (literalsSize << 4) |
             (totalSize << 14);
         put24BitLittleEndian(outputBase, outputAddress, header);
         break;
       }
       case 4: { // 2 - 2 - 14 - 14
         final int header =
             encodingType | (2 << 2) | (literalsSize << 4) | (totalSize << 18);
         putInt(outputBase, outputAddress, header);
         break;
       }
       case 5: { // 2 - 2 - 18 - 18
         final int header =
             encodingType | (3 << 2) | (literalsSize << 4) | (totalSize << 22);
         putInt(outputBase, outputAddress, header);
         outputBase[outputAddress + SIZE_OF_INT] = (byte) (totalSize >>> 10);
         break;
       }
       default:  // not possible : headerSize is {3,4,5}
         throw new IllegalStateException();
     }
 
     return headerSize + totalSize;
   }
 
   private static int rleLiterals(final byte[] outputBase,
                                  final int outputAddress,
                                  final byte[] inputBase, final int inputSize) {
     final int headerSize =
         1 + (inputSize > 31? 1 : 0) + (inputSize > 4095? 1 : 0);
 
     switch (headerSize) {
       case 1: // 2 - 1 - 5
         outputBase[outputAddress] =
             (byte) (RLE_LITERALS_BLOCK | (inputSize << 3));
         break;
       case 2: // 2 - 2 - 12
         putShort(outputBase, outputAddress,
                  (short) (RLE_LITERALS_BLOCK | (1 << 2) | (inputSize << 4)));
         break;
       case 3: // 2 - 2 - 20
         putInt(outputBase, outputAddress,
                RLE_LITERALS_BLOCK | 3 << 2 | inputSize << 4);
         break;
       default:   // impossible. headerSize is {1,2,3}
         throw new IllegalStateException();
     }
 
     outputBase[outputAddress + headerSize] = inputBase[0];
 
     return headerSize + 1;
   }
 
   private static int calculateMinimumGain(final int inputSize,
                                           final CompressionParameters.Strategy strategy) {
     // TODO: move this to Strategy to avoid hardcoding a specific strategy here
     final int minLog =
         strategy == CompressionParameters.Strategy.BTULTRA? 7 : 6;
     return (inputSize >>> minLog) + 2;
   }
 
   private static int rawLiterals(final byte[] outputBase,
                                  final int outputAddress, final int outputSize,
                                  final byte[] inputBase, final int inputSize) {
     int headerSize = 1;
     if (inputSize >= 32) {
       headerSize++;
     }
     if (inputSize >= 4096) {
       headerSize++;
     }
 
     checkArgument(inputSize + headerSize <= outputSize,
                   OUTPUT_BUFFER_TOO_SMALL);
 
     switch (headerSize) {
       case 1:
         outputBase[outputAddress] =
             (byte) (RAW_LITERALS_BLOCK | (inputSize << 3));
         break;
       case 2:
         putShort(outputBase, outputAddress,
                  (short) (RAW_LITERALS_BLOCK | (1 << 2) | (inputSize << 4)));
         break;
       case 3:
         put24BitLittleEndian(outputBase, outputAddress,
                              RAW_LITERALS_BLOCK | (3 << 2) | (inputSize << 4));
         break;
       default:
         throw new AssertionError();
     }
 
     // TODO: ensure this test is correct
     checkArgument(inputSize + 1 <= outputSize, OUTPUT_BUFFER_TOO_SMALL);
 
     copyMemory(inputBase, 0, outputBase, outputAddress + headerSize, inputSize);
 
     return headerSize + inputSize;
   }
 }