From e263dbe085fa3f627f707cc25451743809b2137e Mon Sep 17 00:00:00 2001 From: Daniel Friesel Date: Mon, 18 Jan 2021 21:11:10 +0100 Subject: deflatetest: add static huffman support --- src/app/deflatetest/main.cc | 59 +++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 54 insertions(+), 5 deletions(-) (limited to 'src') diff --git a/src/app/deflatetest/main.cc b/src/app/deflatetest/main.cc index 221d881..6042efa 100644 --- a/src/app/deflatetest/main.cc +++ b/src/app/deflatetest/main.cc @@ -14,6 +14,12 @@ unsigned char const deflate_input[] = { 58, 195, 100, 137, 221, 124, 237, 195, 140, 141, 10, 197, 102, 191, 51, 79, 41, 23, 153, 255, 22, 11 }; +/* +unsigned char const deflate_input[] = { + 120, 1, 243, 72, 204, 201, 201, 215, 81, 8, 79, 205, 41, 81, 4, 0, 26, 155, 3, 250 +}; +*/ + unsigned char* udeflate_input_end; unsigned char* udeflate_input_now; @@ -48,7 +54,7 @@ uint8_t const udeflate_hclen_index[] = { }; uint8_t udeflate_hc_lengths[19]; -uint8_t udeflate_lld_lengths[337]; +uint8_t udeflate_lld_lengths[318]; static uint16_t udeflate_rev_word(uint16_t word, uint8_t bits) { @@ -76,7 +82,9 @@ static uint16_t udeflate_get_word() if (udeflate_bit_offset) { ret |= (uint16_t)(udeflate_input_now[2] & udeflate_bitmask(udeflate_bit_offset)) << (16 - udeflate_bit_offset); } +#ifdef UDEFLATE_DEBUG kout << "get_word = " << bin << ret << dec << endl; +#endif return ret; } @@ -132,12 +140,14 @@ static void udeflate_build_alphabet(uint8_t* lengths, uint16_t size, uint8_t* bl next_code[i] = code; } +#ifdef UDEFLATE_DEBUG for (i = 0; i < 12; i++) { kout << "bl_count[" << i << "] = " << bl_count[i] << endl; } for (i = 0; i < 12; i++) { kout << "next_code[" << i << "] = " << next_code[i] << endl; } +#endif } static uint16_t udeflate_huff(uint8_t* lengths, uint16_t size, uint8_t* bl_count, uint16_t* next_code) @@ -145,10 +155,10 @@ static uint16_t udeflate_huff(uint8_t* lengths, uint16_t size, uint8_t* bl_count uint16_t next_word = udeflate_get_word(); for (uint8_t num_bits = 1; num_bits < 12; num_bits++) { uint16_t next_bits = udeflate_rev_word(next_word, num_bits); - // TODO benötigt bit reversal bei der Abgleichung code <-> next_bits - // (geeignete is_bit_eq(next_bits, code_candidate, num_bits) Funktion?) if (bl_count[num_bits] && next_bits >= next_code[num_bits] && next_bits < next_code[num_bits] + bl_count[num_bits] ) { +#ifdef UDEFLATE_DEBUG kout << "found huffman code, length = " << num_bits << endl; +#endif udeflate_bit_offset += num_bits; while (udeflate_bit_offset >= 8) { udeflate_input_now++; @@ -176,7 +186,9 @@ static int8_t udeflate_huffman(uint8_t* ll_lengths, uint16_t ll_size, uint8_t* d uint16_t output_pos = 0; while (1) { code = udeflate_huff(ll_lengths, ll_size, udeflate_bl_count_ll, udeflate_next_code_ll); +#ifdef UDEFLATE_DEBUG kout << "code " << code << endl; +#endif if (code < 256) { deflate_output[output_pos] = code; output_pos++; @@ -202,15 +214,42 @@ static int8_t udeflate_huffman(uint8_t* ll_lengths, uint16_t ll_size, uint8_t* d } } +static int8_t udeflate_static_huffman() +{ + uint16_t i; + for (i = 0; i <= 143; i++) { + udeflate_lld_lengths[i] = 8; + } + for (i = 144; i <= 255; i++) { + udeflate_lld_lengths[i] = 9; + } + for (i = 256; i <= 279; i++) { + udeflate_lld_lengths[i] = 7; + } + for (i = 280; i <= 284; i++) { + udeflate_lld_lengths[i] = 8; + } + for (i = 285; i <= 285+29; i++) { + udeflate_lld_lengths[i] = 5; + } + + udeflate_build_alphabet(udeflate_lld_lengths, 285, udeflate_bl_count_ll, udeflate_next_code_ll); + udeflate_build_alphabet(udeflate_lld_lengths + 285, 29, udeflate_bl_count_d, udeflate_next_code_d); + return udeflate_huffman(udeflate_lld_lengths, 285, udeflate_lld_lengths + 285, 29); +} + static int8_t udeflate_dynamic_huffman() { uint8_t i; uint16_t hlit = 257 + udeflate_get_bits(5); - kout << "hlit=" << hlit << endl; uint8_t hdist = 1 + udeflate_get_bits(5); - kout << "hdist=" << hdist << endl; uint8_t hclen = 4 + udeflate_get_bits(4); + +#ifdef UDEFLATE_DEBUG + kout << "hlit=" << hlit << endl; + kout << "hdist=" << hdist << endl; kout << "hclen=" << hclen << endl; +#endif for (i = 0; i < hclen; i++) { udeflate_hc_lengths[udeflate_hclen_index[i]] = udeflate_get_bits(3); @@ -224,7 +263,9 @@ static int8_t udeflate_dynamic_huffman() uint16_t items_processed = 0; while (items_processed < hlit + hdist) { uint8_t code = udeflate_huff(udeflate_hc_lengths, 19, udeflate_bl_count_ll, udeflate_next_code_ll); +#ifdef UDEFLATE_DEBUG kout << "code = " << code << endl; +#endif if (code == 16) { uint8_t copy_count = 3 + udeflate_get_bits(2); for (uint8_t i = 0; i < copy_count; i++) { @@ -264,12 +305,17 @@ int8_t udeflate(unsigned char* buf, uint16_t buf_len) { uint8_t is_final = buf[0] & 0x01; uint8_t block_type = (buf[0] & 0x06) >> 1; +#ifdef UDEFLATE_DEBUG kout << "is_final=" << is_final << " block_type=" << block_type << endl; +#endif udeflate_input_now = buf; udeflate_input_end = buf + buf_len; udeflate_bit_offset = 3; + if (block_type == 1) { + return udeflate_static_huffman(); + } if (block_type == 2) { return udeflate_dynamic_huffman(); } @@ -285,8 +331,11 @@ int8_t udeflate_zlib(unsigned char* buf, uint16_t buf_len) uint8_t zlib_method = buf[0] & 0x0f; uint16_t zlib_window_size = 1 << (8 + ((buf[0] & 0xf0) >> 4)); uint8_t zlib_flags = buf[1]; + +#ifdef UDEFLATE_DEBUG kout << "zlib_method=" << zlib_method << endl; kout << "zlib_window_size=" << zlib_window_size << endl; +#endif if (zlib_method != 8) { return -2; -- cgit v1.2.3