deflate implementation More...

#include <deflate.h>
#include <utils.h>
#include <quicksort.h>
#include <logging.h>

Classes
struct	deflate_match_t

struct	deflate_hashtable_t

struct	bit_buffer_t

struct	huffman_decode_table_t

struct	huffman_encode_table_t

struct	huffman_encode_freq_t

struct	huffman_symbol_freq_t

struct	huffman_bit_level_info_t

Macros
#define	DEFLATE_MAX_MATCH (258)

#define	DEFLATE_MIN_MATCH (3)

#define	DEFLATE_WINDOW_SIZE 32768

#define	DEFLATE_HASHTABLE_SIZE 15

#define	DEFLATE_HASHTABLE_MUL 2654435761U

#define	DEFLATE_HASHTABLE_PREV_SIZE 32765

#define	DEFLATE_NO_POS (-1)

#define	DEFLATE_MAX_BLOCK_SIZE 65535

#define	DEFLATE_MAX_BITS_LIMIT 16

#define	HUFFMAN_LEAF_COUNT(x, y) leaf_counts[(x) * DEFLATE_MAX_BITS_LIMIT + (y)]

Typedefs
typedef struct deflate_match_t	deflate_match_t

typedef struct deflate_hashtable_t	deflate_hashtable_t

typedef struct bit_buffer_t	bit_buffer_t

typedef struct huffman_decode_table_t	huffman_decode_table_t

typedef struct huffman_encode_table_t	huffman_encode_table_t

typedef struct huffman_encode_freq_t	huffman_encode_freq_t

typedef struct huffman_symbol_freq_t	huffman_symbol_freq_t

typedef struct huffman_bit_level_info_t	huffman_bit_level_info_t

Functions
	MODULE ("turnstone.lib")

	_Static_assert (sizeof(huffman_length_base)/sizeof(huffman_length_base[0])==29, "huffman_length_base must have 29 elements")

	_Static_assert (sizeof(huffman_length_extra_bits)/sizeof(huffman_length_extra_bits[0])==29, "huffman_length_extra_bits must have 29 elements")

static int16_t	huffman_find_length_index (uint16_t length)

	_Static_assert (sizeof(huffman_distance_base)/sizeof(huffman_distance_base[0])==30, "huffman_distance_base must have 30 elements")

	_Static_assert (sizeof(huffman_distance_extra_bits)/sizeof(huffman_distance_extra_bits[0])==30, "huffman_distance_extra_bits must have 30 elements")

static int16_t	huffman_find_distance_index (uint16_t distance)

int8_t	deflate_inflate_uncompressed_block (bit_buffer_t bit_buffer, buffer_t out)

int8_t	deflate_inflate_block (bit_buffer_t bit_buffer, buffer_t out, huffman_decode_table_t lengths, huffman_decode_table_t distances)

int8_t	huffman_decode_table_decode (bit_buffer_t bit_buffer, huffman_decode_table_t huffman_lengths, huffman_decode_table_t *huffman_distances)

static int64_t	bit_buffer_get (bit_buffer_t *bit_buffer, uint8_t bit_count)

static int8_t	bit_buffer_put (bit_buffer_t *bit_buffer, uint8_t bit_count, uint64_t bits)

static int8_t	bit_buffer_push (bit_buffer_t *bit_buffer)

static void	bitbuffer_discard (bit_buffer_t *bit_buffer)

static int16_t	bit_buffer_get_16le (bit_buffer_t *bit_buffer)

static int32_t	huffman_decode (bit_buffer_t bit_buffer, huffman_decode_table_t huffman_decode_table, int32_t max_symbol)

static int8_t	huffman_decode_table_build (uint8_t lengths, size_t size, struct huffman_decode_table_t out, uint32_t max_length)

static uint32_t	deflate_hash4 (uint32_t data)

static void	deflate_hash_insert (int64_t pos, uint32_t h, deflate_hashtable_t *ht)

static deflate_match_t	deflate_find_bestmatch (buffer_t in, int64_t in_len, int64_t in_p, deflate_hashtable_t ht)

static buffer_t *	deflate_deflate_lz77 (buffer_t in_block, huffman_encode_freq_t freqs)

static int8_t	deflate_deflate_no_compress (buffer_t in_block, bit_buffer_t bit_buffer, boolean_t is_last_block)

static int64_t	deflate_deflate_calculate_out_size (huffman_encode_freq_t freqs, const huffman_encode_table_t symbols, const huffman_encode_table_t *distances)

static int8_t	deflate_deflate_block (buffer_t lz77_block, bit_buffer_t bit_buffer, const huffman_encode_table_t symbols, const huffman_encode_table_t distances)

int8_t	huffman_sort_by_freq (const void a, const void b)

int8_t	huffman_sort_by_symbol (const void a, const void b)

static boolean_t	huffman_encode_build_table_internal (huffman_symbol_freq_t *symbol_freqs, int32_t count, int32_t max_bits, huffman_encode_table_t huffman_table)

static boolean_t	huffman_encode_build_table (huffman_encode_freq_t freqs, boolean_t for_literal, huffman_encode_table_t huffman_table, int32_t max_bits, int32_t *max_used_symbol)

static bit_buffer_t *	huffman_encode_build_tables_and_code (huffman_encode_freq_t freqs, huffman_encode_table_t symbols, huffman_encode_table_t distances, int64_t header_bit_count)
	Builds a huffman tree from the given frequencies and also returns the header for the tree. More...

int8_t	deflate_deflate (buffer_t in, buffer_t out)

int8_t	deflate_inflate (buffer_t in, buffer_t out)

Variables
const huffman_encode_table_t	huffman_encode_fixed

const huffman_encode_table_t	huffman_encode_distance_fixed

const huffman_decode_table_t	huffman_decode_fixed_lengths

const huffman_decode_table_t	huffman_decode_fixed_distances

const uint16_t	huffman_length_base []

const uint16_t	huffman_length_extra_bits []

const uint16_t	huffman_distance_base []

const uint16_t	huffman_distance_extra_bits []

const uint8_t	huffman_code_lengths []

Detailed Description

deflate implementation

This work is licensed under TURNSTONE OS Public License. Please read and understand latest version of Licence.

Function Documentation

◆ huffman_encode_build_tables_and_code()

static bit_buffer_t * huffman_encode_build_tables_and_code	(	huffman_encode_freq_t *	freqs,
		huffman_encode_table_t **	symbols,
		huffman_encode_table_t **	distances,
		int64_t *	header_bit_count
	)

static

Builds a huffman tree from the given frequencies and also returns the header for the tree.

Parameters

[in]	freqs	The frequencies to build the tree from
[out]	symbols	The huffman tree
[out]	distances	The huffman tree

Returns: The header for the tree

Variable Documentation

◆ huffman_code_lengths

const uint8_t huffman_code_lengths[]

Initial value:

= {
    16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15,
}

◆ huffman_decode_fixed_distances

const huffman_decode_table_t huffman_decode_fixed_distances

Initial value:

= {
    {
        0, 0, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    },
    {
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    }
}

◆ huffman_decode_fixed_lengths

const huffman_decode_table_t huffman_decode_fixed_lengths

Initial value:

= {
    {
        0, 0, 0, 0, 0, 0, 0, 24, 152, 112, 0, 0, 0, 0, 0, 0,
    },
    {
        256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271,
        272, 273, 274, 275, 276, 277, 278, 279, 0, 1, 2, 3, 4, 5, 6, 7,
        8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
        24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
        40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55,
        56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71,
        72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87,
        88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103,
        104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119,
        120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135,
        136, 137, 138, 139, 140, 141, 142, 143, 280, 281, 282, 283, 284, 285, 286, 287,
        144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
        160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,
        176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
        192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,
        208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,
        224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
        240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255,
    }
}

◆ huffman_distance_base

const uint16_t huffman_distance_base[]

Initial value:

= {
    1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577,
}

◆ huffman_distance_extra_bits

const uint16_t huffman_distance_extra_bits[]

Initial value:

= {
    0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13,
}

◆ huffman_encode_distance_fixed

const huffman_encode_table_t huffman_encode_distance_fixed

Initial value:

= {
    {
        0x00, 0x10, 0x08, 0x18, 0x04, 0x14, 0x0c, 0x1c, 0x02, 0x12, 0x0a, 0x1a, 0x06, 0x16, 0x0e, 0x1e, 
        0x01, 0x11, 0x09, 0x19, 0x05, 0x15, 0x0d, 0x1d, 0x03, 0x13, 0x0b, 0x1b, 0x07, 0x17, 0x0f, 0x1f, 
    },
    {
        0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
        0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
    },
}

◆ huffman_length_base

const uint16_t huffman_length_base[]

Initial value:

= {
    3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258,
}

◆ huffman_length_extra_bits

const uint16_t huffman_length_extra_bits[]

Initial value:

= {
    0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0,
}

Classes

Macros

Typedefs

Functions

Variables

Detailed Description

Function Documentation

◆ huffman_encode_build_tables_and_code()

Variable Documentation

◆ huffman_code_lengths

◆ huffman_decode_fixed_distances

◆ huffman_decode_fixed_lengths

◆ huffman_distance_base

◆ huffman_distance_extra_bits

◆ huffman_encode_distance_fixed

◆ huffman_length_base

◆ huffman_length_extra_bits