lz_compress.h

/*
 * (c) Copyright 2019 Xilinx, Inc. All rights reserved.
 *
 * 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.
 *
 */
#ifndef _XFCOMPRESSION_LZ_COMPRESS_HPP_
#define _XFCOMPRESSION_LZ_COMPRESS_HPP_

/**
 * @file lz_compress.hpp
 * @brief Header for modules used in LZ4 and snappy compression kernels.
 *
 * This file is part of Vitis Data Compression Library.
 */
#include "hls_stream.h"

#include <ap_int.h>
#include <assert.h>
#include <stdint.h>
#include <stdio.h>

namespace xf {
namespace compression {

typedef ap_uint<32> compressd_dt;

/**
 * @brief This module reads input literals from stream and updates
 * match length and offset of each literal.
 *
 * @tparam MATCH_LEN match length
 * @tparam MATCH_LEVEL match level
 * @tparam LZ_DICT_SIZE dictionary size
 * @tparam BIT bit
 * @tparam MIN_OFFSET minimum offset
 * @tparam MIN_MATCH minimum match
 * @tparam LZ_MAX_OFFSET_LIMIT maximum offset limit
 *
 * @param inStream input stream
 * @param outStream output stream
 * @param input_size input size
 * @param left_bytes left bytes in block
 */
template <int MATCH_LEN,
          int MATCH_LEVEL,
          int LZ_DICT_SIZE,
          int BIT,
          int MIN_OFFSET,
          int MIN_MATCH,
          int LZ_MAX_OFFSET_LIMIT>
void lzCompress(hls::stream<ap_uint<BIT> >& inStream,
                hls::stream<compressd_dt>& outStream,
                uint32_t input_size,
                uint32_t left_bytes) {
    const int c_dictEleWidth = (MATCH_LEN * BIT + 24);
    typedef ap_uint<MATCH_LEVEL * c_dictEleWidth> uintDictV_t;
    typedef ap_uint<c_dictEleWidth> uintDict_t;

    if (input_size == 0) return;
    // Dictionary
    uintDictV_t dict[LZ_DICT_SIZE];
#pragma HLS RESOURCE variable = dict core = XPM_MEMORY uram

    uintDictV_t resetValue = 0;
    for (int i = 0; i < MATCH_LEVEL; i++) {
#pragma HLS UNROLL
        resetValue.range((i + 1) * c_dictEleWidth - 1, i * c_dictEleWidth + MATCH_LEN * BIT) = -1;
    }
// Initialization of Dictionary
dict_flush:
    for (int i = 0; i < LZ_DICT_SIZE; i++) {
#pragma HLS PIPELINE II = 1
#pragma HLS UNROLL FACTOR = 2
        dict[i] = resetValue;
    }

    uint8_t present_window[MATCH_LEN];
#pragma HLS ARRAY_PARTITION variable = present_window complete
    for (uint8_t i = 1; i < MATCH_LEN; i++) {
        present_window[i] = inStream.read();
    }
lz_compress:
    for (uint32_t i = MATCH_LEN - 1; i < input_size - left_bytes; i++) {
#pragma HLS PIPELINE II = 1
#pragma HLS dependence variable = dict inter false
        uint32_t currIdx = i - MATCH_LEN + 1;
        // shift present window and load next value
        for (int m = 0; m < MATCH_LEN - 1; m++) {
#pragma HLS UNROLL
            present_window[m] = present_window[m + 1];
        }
        present_window[MATCH_LEN - 1] = inStream.read();

        // Calculate Hash Value
        uint32_t hash =
            (present_window[0] << 4) ^ (present_window[1] << 3) ^ (present_window[2] << 3) ^ (present_window[3]);

        // Dictionary Lookup
        uintDictV_t dictReadValue = dict[hash];
        uintDictV_t dictWriteValue = dictReadValue << c_dictEleWidth;
        for (int m = 0; m < MATCH_LEN; m++) {
#pragma HLS UNROLL
            dictWriteValue.range((m + 1) * BIT - 1, m * BIT) = present_window[m];
        }
        dictWriteValue.range(c_dictEleWidth - 1, MATCH_LEN * BIT) = currIdx;
        // Dictionary Update
        dict[hash] = dictWriteValue;

        // Match search and Filtering
        // Comp dict pick
        uint8_t match_length = 0;
        uint32_t match_offset = 0;
        for (int l = 0; l < MATCH_LEVEL; l++) {
            uint8_t len = 0;
            bool done = 0;
            uintDict_t compareWith = dictReadValue.range((l + 1) * c_dictEleWidth - 1, l * c_dictEleWidth);
            uint32_t compareIdx = compareWith.range(c_dictEleWidth - 1, MATCH_LEN * BIT);
            for (int m = 0; m < MATCH_LEN; m++) {
                if (present_window[m] == compareWith.range((m + 1) * BIT - 1, m * BIT) && !done) {
                    len++;
                } else {
                    done = 1;
                }
            }
            if ((len >= MIN_MATCH) && (currIdx > compareIdx) && ((currIdx - compareIdx) < LZ_MAX_OFFSET_LIMIT) &&
                ((currIdx - compareIdx - 1) >= MIN_OFFSET)) {
                len = len;
            } else {
                len = 0;
            }
            if (len > match_length) {
                match_length = len;
                match_offset = currIdx - compareIdx - 1;
            }
        }
        compressd_dt outValue = 0;
        outValue.range(7, 0) = present_window[0];
        outValue.range(15, 8) = match_length;
        outValue.range(31, 16) = match_offset;
        outStream << outValue;
    }
lz_compress_leftover:
    for (int m = 1; m < MATCH_LEN; m++) {
#pragma HLS PIPELINE
        compressd_dt outValue = 0;
        outValue.range(7, 0) = present_window[m];
        outStream << outValue;
    }
lz_left_bytes:
    for (int l = 0; l < left_bytes; l++) {
#pragma HLS PIPELINE
        compressd_dt outValue = 0;
        outValue.range(7, 0) = inStream.read();
        outStream << outValue;
    }
}

} // namespace compression
} // namespace xf
#endif