lib/compression/lzxpress_huffman.h

   1 /*
   2  * Samba compression library - LGPLv3
   3  *
   4  * Copyright © Catalyst IT 2022
   5  *
   6  *  ** NOTE! The following LGPL license applies to this file.
   7  *  ** It does NOT imply that all of Samba is released under the LGPL
   8  *
   9  *  This library is free software; you can redistribute it and/or
  10  *  modify it under the terms of the GNU Lesser General Public
  11  *  License as published by the Free Software Foundation; either
  12  *  version 3 of the License, or (at your option) any later version.
  13  *
  14  *  This library is distributed in the hope that it will be useful,
  15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  *  Lesser General Public License for more details.
  18  *
  19  *  You should have received a copy of the GNU Lesser General Public
  20  *  License along with this library; if not, see <http://www.gnu.org/licenses/>.
  21  */
  22
  23 #ifndef HAVE_LZXPRESS_HUFFMAN_H
  24 #define HAVE_LZXPRESS_HUFFMAN_H
  25
  26
  27 struct huffman_node {
  28         struct huffman_node *left;
  29         struct huffman_node *right;
  30         uint32_t count;
  31         uint16_t symbol;
  32         int8_t depth;
  33 };
  34
  35
  36 /*
  37  * LZX_HUFF_COMP_HASH_BITS is how big to make the hash tables
  38  * (12 means 4096, etc).
  39  *
  40  * A larger number (up to 16) will be faster on long messages (fewer
  41  * collisions), but probably slower on short ones (more prep).
  42  */
  43 #define LZX_HUFF_COMP_HASH_BITS 14
  44
  45
  46 /*
  47  * This struct just coalesces all the memory you need for LZ77 + Huffman
  48  * compression together in one bundle.
  49  *
  50  * There are a few different things you want, you usually want them all, so
  51  * this makes it easy to allocate them all at once.
  52  */
  53
  54 struct lzxhuff_compressor_mem {
  55         struct huffman_node leaf_nodes[512];
  56         struct huffman_node internal_nodes[512];
  57         uint16_t symbol_values[512];
  58         uint16_t intermediate[65536 + 6];
  59         uint16_t hash_table1[1 << LZX_HUFF_COMP_HASH_BITS];
  60         uint16_t hash_table2[1 << LZX_HUFF_COMP_HASH_BITS];
  61 };
  62
  63
  64 ssize_t lzxpress_huffman_compress(struct lzxhuff_compressor_mem *cmp,
  65                                   const uint8_t *input_bytes,
  66                                   size_t input_size,
  67                                   uint8_t *output,
  68                                   size_t available_size);
  69
  70
  71 ssize_t lzxpress_huffman_compress_talloc(TALLOC_CTX *mem_ctx,
  72                                          const uint8_t *input_bytes,
  73                                          size_t input_size,
  74                                          uint8_t **output);
  75
  76 ssize_t lzxpress_huffman_decompress(const uint8_t *input,
  77                                     size_t input_size,
  78                                     uint8_t *output,
  79                                     size_t max_output_size);
  80
  81 uint8_t *lzxpress_huffman_decompress_talloc(TALLOC_CTX *mem_ctx,
  82                                             const uint8_t *input_bytes,
  83                                             size_t input_size,
  84                                             size_t output_size);
  85
  86 /*
  87  * lzxpress_huffman_max_compressed_size()
  88  *
  89  * Return the most bytes the compression can take, to allow
  90  * pre-allocation.
  91  */
  92 size_t lzxpress_huffman_max_compressed_size(size_t input_size);
  93
  94
  95 #endif /* HAVE_LZXPRESS_HUFFMAN_H */