ceph/src/isa-l/include/igzip_lib.h

   1 /**********************************************************************
   2   Copyright(c) 2011-2016 Intel Corporation All rights reserved.
   3
   4   Redistribution and use in source and binary forms, with or without
   5   modification, are permitted provided that the following conditions
   6   are met:
   7     * Redistributions of source code must retain the above copyright
   8       notice, this list of conditions and the following disclaimer.
   9     * Redistributions in binary form must reproduce the above copyright
  10       notice, this list of conditions and the following disclaimer in
  11       the documentation and/or other materials provided with the
  12       distribution.
  13     * Neither the name of Intel Corporation nor the names of its
  14       contributors may be used to endorse or promote products derived
  15       from this software without specific prior written permission.
  16
  17   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  20   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  21   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  22   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  23   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28 **********************************************************************/
  29
  30 #ifndef _IGZIP_H
  31 #define _IGZIP_H
  32
  33 /**
  34  * @file igzip_lib.h
  35  *
  36  * @brief This file defines the igzip compression interface, a high performance
  37  * deflate compression interface for storage applications.
  38  *
  39  * Deflate is a widely used compression standard that can be used standalone, it
  40  * also forms the basis of gzip and zlib compression formats. Igzip supports the
  41  * following flush features:
  42  *
  43  * - No Flush: The default method where no flush is performed.
  44  *
  45  * - Sync flush: whereby isal_deflate() finishes the current deflate block at
  46  *   the end of each input buffer. The deflate block is byte aligned by
  47  *   appending an empty stored block.
  48  *
  49  * - Full flush: whereby isal_deflate() finishes and aligns the deflate block as
  50  *   in sync flush but also ensures that subsequent block's history does not
  51  *   look back beyond this point and new blocks are fully independent.
  52  *
  53  * Igzip's default configuration is:
  54  *
  55  * - 8K window size
  56  *
  57  * This option can be overridden to enable:
  58  *
  59  * - 32K window size, by adding \#define LARGE_WINDOW 1 in igzip_lib.h and
  60  *   \%define LARGE_WINDOW in options.asm, or via the command line with
  61  *   @verbatim gmake D="-D LARGE_WINDOW" @endverbatim on Linux and FreeBSD, or
  62  *   with @verbatim nmake -f Makefile.nmake D="-D LARGE_WINDOW" @endverbatim on
  63  *   Windows.
  64  *
  65  * KNOWN ISSUES:
  66  * - If building the code on Windows with the 32K window enabled, the
  67  *   /LARGEADDRESSAWARE:NO link option must be added.
  68  * - The 32K window isn't supported when used in a shared library.
  69  *
  70  */
  71 #include <stdint.h>
  72 #include "types.h"
  73
  74 #ifdef __cplusplus
  75 extern "C" {
  76 #endif
  77
  78 // Options:dir
  79 // m - reschedule mem reads
  80 // e b - bitbuff style
  81 // t s x - compare style
  82 // h - limit hash updates
  83 // l - use longer huffman table
  84 // f - fix cache read
  85
  86 #if defined(LARGE_WINDOW)
  87 # define HIST_SIZE 32
  88 #else
  89 # define HIST_SIZE 8
  90 #endif
  91
  92 /* bit buffer types
  93  * BITBUF8: (e) Always write 8 bytes of data
  94  * BITBUFB: (b) Always write data
  95  */
  96 #if !(defined(USE_BITBUFB) || defined(USE_BITBUF8) || defined(USE_BITBUF_ELSE))
  97 # define USE_BITBUFB
  98 #endif
  99
 100 /* compare types
 101  * 1: ( ) original
 102  * 2: (t) with CMOV
 103  * 3: (s) with sttni
 104  * 4: (x) with xmm / pmovbmsk
 105  * 5: (y) with ymm / pmovbmsk (32-bytes at a time)
 106  */
 107 # define LIMIT_HASH_UPDATE
 108
 109 /* (l) longer huffman table */
 110 #define LONGER_HUFFTABLE
 111
 112 /* (f) fix cache read problem */
 113 #define FIX_CACHE_READ
 114
 115 #if (HIST_SIZE > 8)
 116 # undef LONGER_HUFFTABLE
 117 #endif
 118
 119 #define IGZIP_K  1024
 120 #define IGZIP_D  (HIST_SIZE * IGZIP_K)  /* Amount of history */
 121 #define IGZIP_LA (17 * 16)              /* Max look-ahead, rounded up to 32 byte boundary */
 122 #define BSIZE  (2*IGZIP_D + IGZIP_LA)   /* Nominal buffer size */
 123
 124 #define HASH_SIZE  IGZIP_D
 125 #define HASH_MASK  (HASH_SIZE - 1)
 126
 127 #define SHORTEST_MATCH  3
 128
 129 #define IGZIP_MAX_DEF_HDR_SIZE 328
 130
 131 #ifdef LONGER_HUFFTABLE
 132 enum {DIST_TABLE_SIZE = 8*1024};
 133
 134 /* DECODE_OFFSET is dist code index corresponding to DIST_TABLE_SIZE + 1 */
 135 enum { DECODE_OFFSET = 26 };
 136 #else
 137 enum {DIST_TABLE_SIZE = 1024};
 138 /* DECODE_OFFSET is dist code index corresponding to DIST_TABLE_SIZE + 1 */
 139 enum { DECODE_OFFSET = 20 };
 140 #endif
 141 enum {LEN_TABLE_SIZE = 256};
 142 enum {LIT_TABLE_SIZE = 257};
 143
 144 #define IGZIP_LIT_LEN 286
 145 #define IGZIP_DIST_LEN 30
 146
 147 /* Flush Flags */
 148 #define NO_FLUSH        0       /* Default */
 149 #define SYNC_FLUSH      1
 150 #define FULL_FLUSH      2
 151 #define FINISH_FLUSH    0       /* Deprecated */
 152
 153 /* Return values */
 154 #define COMP_OK 0
 155 #define INVALID_FLUSH -7
 156 #define INVALID_PARAM -8
 157 #define STATELESS_OVERFLOW -1
 158 #define DEFLATE_HDR_LEN 3
 159 /**
 160  *  @enum isal_zstate
 161  *  @brief Compression State please note ZSTATE_TRL only applies for GZIP compression
 162  */
 163
 164
 165 /* When the state is set to ZSTATE_NEW_HDR or TMP_ZSTATE_NEW_HEADER, the
 166  * hufftable being used for compression may be swapped
 167  */
 168 enum isal_zstate_state {
 169         ZSTATE_NEW_HDR,  //!< Header to be written
 170         ZSTATE_HDR,     //!< Header state
 171         ZSTATE_BODY,    //!< Body state
 172         ZSTATE_FLUSH_READ_BUFFER, //!< Flush buffer
 173         ZSTATE_SYNC_FLUSH, //!< Write sync flush block
 174         ZSTATE_FLUSH_WRITE_BUFFER, //!< Flush bitbuf
 175         ZSTATE_TRL,     //!< Trailer state
 176         ZSTATE_END,     //!< End state
 177         ZSTATE_TMP_NEW_HDR, //!< Temporary Header to be written
 178         ZSTATE_TMP_HDR, //!< Temporary Header state
 179         ZSTATE_TMP_BODY,        //!< Temporary Body state
 180         ZSTATE_TMP_FLUSH_READ_BUFFER, //!< Flush buffer
 181         ZSTATE_TMP_SYNC_FLUSH, //!< Write sync flush block
 182         ZSTATE_TMP_FLUSH_WRITE_BUFFER, //!< Flush bitbuf
 183         ZSTATE_TMP_TRL, //!< Temporary Trailer state
 184         ZSTATE_TMP_END  //!< Temporary End state
 185 };
 186
 187 /* Offset used to switch between TMP states and non-tmp states */
 188 #define TMP_OFFSET_SIZE ZSTATE_TMP_HDR - ZSTATE_HDR
 189
 190 struct isal_huff_histogram {
 191         uint64_t lit_len_histogram[IGZIP_LIT_LEN];
 192         uint64_t dist_histogram[IGZIP_DIST_LEN];
 193 };
 194
 195 /** @brief Holds Bit Buffer information*/
 196 struct BitBuf2 {
 197         uint64_t m_bits;        //!< bits in the bit buffer
 198         uint32_t m_bit_count;   //!< number of valid bits in the bit buffer
 199         uint8_t *m_out_buf;     //!< current index of buffer to write to
 200         uint8_t *m_out_end;     //!< end of buffer to write to
 201         uint8_t *m_out_start;   //!< start of buffer to write to
 202 };
 203
 204 /* Variable prefixes:
 205  * b_ : Measured wrt the start of the buffer
 206  * f_ : Measured wrt the start of the file (aka file_start)
 207  */
 208
 209 /** @brief Holds the internal state information for input and output compression streams*/
 210 struct isal_zstate {
 211         uint32_t b_bytes_valid; //!< number of bytes of valid data in buffer
 212         uint32_t b_bytes_processed;     //!< keeps track of the number of bytes processed in isal_zstate.buffer
 213         uint8_t *file_start;    //!< pointer to where file would logically start
 214         DECLARE_ALIGNED(uint32_t crc[16], 16);  //!< actually 4 128-bit integers
 215         struct BitBuf2 bitbuf;  //!< Bit Buffer
 216         enum isal_zstate_state state;   //!< Current state in processing the data stream
 217         uint32_t count; //!< used for partial header/trailer writes
 218         uint8_t tmp_out_buff[16];       //!< temporary array
 219         uint32_t tmp_out_start; //!< temporary variable
 220         uint32_t tmp_out_end;   //!< temporary variable
 221         uint32_t last_flush;    //!< keeps track of last submitted flush
 222         uint32_t has_gzip_hdr;  //!< keeps track of if the gzip header has been written.
 223         uint32_t has_eob;       //!< keeps track of eob on the last deflate block
 224         uint32_t has_eob_hdr;   //!< keeps track of eob hdr (with BFINAL set)
 225         uint32_t left_over;     //!< keeps track of overflow bytes
 226
 227
 228
 229         DECLARE_ALIGNED(uint8_t buffer[BSIZE + 16], 32);        //!< Internal buffer
 230
 231         DECLARE_ALIGNED(uint16_t head[HASH_SIZE], 16);  //!< Hash array
 232
 233 };
 234
 235 /** @brief Holds the huffman tree used to huffman encode the input stream **/
 236 struct isal_hufftables {
 237
 238         uint8_t deflate_hdr[IGZIP_MAX_DEF_HDR_SIZE]; //!< deflate huffman tree header
 239         uint32_t deflate_hdr_count; //!< Number of whole bytes in deflate_huff_hdr
 240         uint32_t deflate_hdr_extra_bits; //!< Number of bits in the partial byte in header
 241         uint32_t dist_table[DIST_TABLE_SIZE]; //!< bits 4:0 are the code length, bits 31:5 are the code
 242         uint32_t len_table[LEN_TABLE_SIZE]; //!< bits 4:0 are the code length, bits 31:5 are the code
 243         uint16_t lit_table[LIT_TABLE_SIZE]; //!< literal code
 244         uint8_t lit_table_sizes[LIT_TABLE_SIZE]; //!< literal code length
 245         uint16_t dcodes[30 - DECODE_OFFSET]; //!< distance code
 246         uint8_t dcodes_sizes[30 - DECODE_OFFSET]; //!< distance code length
 247
 248 };
 249
 250 /** @brief Holds stream information*/
 251 struct isal_zstream {
 252         uint8_t *next_in;       //!< Next input byte
 253         uint32_t avail_in;      //!< number of bytes available at next_in
 254         uint32_t total_in;      //!< total number of bytes read so far
 255
 256         uint8_t *next_out;      //!< Next output byte
 257         uint32_t avail_out;     //!< number of bytes available at next_out
 258         uint32_t total_out;     //!< total number of bytes written so far
 259
 260         struct isal_hufftables *hufftables; //!< Huffman encoding used when compressing
 261         uint32_t end_of_stream; //!< non-zero if this is the last input buffer
 262         uint32_t flush; //!< Flush type can be NO_FLUSH or SYNC_FLUSH
 263
 264         struct isal_zstate internal_state;      //!< Internal state for this stream
 265 };
 266
 267
 268 /**
 269  * @brief Updates histograms to include the symbols found in the input
 270  * stream. Since this function only updates the histograms, it can be called on
 271  * multiple streams to get a histogram better representing the desired data
 272  * set. When first using histogram it must be initialized by zeroing the
 273  * structure.
 274  *
 275  * @param in_stream: Input stream of data.
 276  * @param length: The length of start_stream.
 277  * @param histogram: The returned histogram of lit/len/dist symbols.
 278  */
 279 void isal_update_histogram(uint8_t * in_stream, int length, struct isal_huff_histogram * histogram);
 280
 281
 282 /**
 283  * @brief Creates a custom huffman code for the given histograms in which
 284  *  every literal and repeat length is assigned a code and all possible lookback
 285  *  distances are assigned a code.
 286  *
 287  * @param hufftables: the output structure containing the huffman code
 288  * @param lit_histogram: histogram containing frequency of literal symbols and
 289  * repeat lengths
 290  * @param dist_histogram: histogram containing frequency of of lookback distances
 291  * @returns Returns a non zero value if an invalid huffman code was created.
 292  */
 293 int isal_create_hufftables(struct isal_hufftables * hufftables,
 294                         struct isal_huff_histogram * histogram);
 295
 296 /**
 297  * @brief Creates a custom huffman code for the given histograms like
 298  * isal_create_hufftables() except literals with 0 frequency in the histogram
 299  * are not assigned a code
 300  *
 301  * @param hufftables: the output structure containing the huffman code
 302  * @param lit_histogram: histogram containing frequency of literal symbols and
 303  * repeat lengths
 304  * @param dist_histogram: histogram containing frequency of of lookback distances
 305  * @returns Returns a non zero value if an invalid huffman code was created.
 306  */
 307 int isal_create_hufftables_subset(struct isal_hufftables * hufftables,
 308                                 struct isal_huff_histogram * histogram);
 309
 310 /**
 311  * @brief Initialize compression stream data structure
 312  *
 313  * @param stream Structure holding state information on the compression streams.
 314  * @returns none
 315  */
 316 void isal_deflate_init(struct isal_zstream *stream);
 317
 318
 319 /**
 320  * @brief Fast data (deflate) compression for storage applications.
 321  *
 322  * On entry to isal_deflate(), next_in points to an input buffer and avail_in
 323  * indicates the length of that buffer. Similarly next_out points to an empty
 324  * output buffer and avail_out indicates the size of that buffer.
 325  *
 326  * The fields total_in and total_out start at 0 and are updated by
 327  * isal_deflate(). These reflect the total number of bytes read or written so far.
 328  *
 329  * The call to isal_deflate() will take data from the input buffer (updating
 330  * next_in, avail_in and write a compressed stream to the output buffer
 331  * (updating next_out and avail_out). The function returns when either the input
 332  * buffer is empty or the output buffer is full.
 333  *
 334  * When the last input buffer is passed in, signaled by setting the
 335  * end_of_stream, the routine will complete compression at the end of the input
 336  * buffer, as long as the output buffer is big enough.
 337  *
 338  * The equivalent of the zlib FLUSH_SYNC operation is currently supported.
 339  * Flush types can be NO_FLUSH or SYNC_FLUSH. Default flush type is NO_FLUSH.
 340  * If SYNC_FLUSH is selected each input buffer is compressed and byte aligned
 341  * with a type 0 block appended to the end. Switching between NO_FLUSH and
 342  * SYNC_FLUSH is supported to select after which input buffer a SYNC_FLUSH is
 343  * performed.
 344  *
 345  * @param  stream Structure holding state information on the compression streams.
 346  * @return COMP_OK (if everything is ok),
 347  *         INVALID_FLUSH (if an invalid FLUSH is selected),
 348  */
 349 int isal_deflate(struct isal_zstream *stream);
 350
 351
 352 /**
 353  * @brief Fast data (deflate) stateless compression for storage applications.
 354  *
 355  * Stateless (one shot) compression routine with a similar interface to
 356  * isal_deflate() but operates on entire input buffer at one time. Parameter
 357  * avail_out must be large enough to fit the entire compressed output. Max
 358  * expansion is limited to the input size plus the header size of a stored/raw
 359  * block.
 360  *
 361  * @param  stream Structure holding state information on the compression streams.
 362  * @return COMP_OK (if everything is ok),
 363  *         STATELESS_OVERFLOW (if output buffer will not fit output).
 364  */
 365 int isal_deflate_stateless(struct isal_zstream *stream);
 366
 367
 368 #ifdef __cplusplus
 369 }
 370 #endif
 371 #endif  /* ifndef _IGZIP_H */