summaryrefslogtreecommitdiff
path: root/src/app
diff options
context:
space:
mode:
authorDaniel Friesel <derf@finalrewind.org>2021-01-18 21:11:10 +0100
committerDaniel Friesel <derf@finalrewind.org>2021-01-18 21:11:10 +0100
commite263dbe085fa3f627f707cc25451743809b2137e (patch)
treea8902de0f1fddd6787fc98d1eb7ef13be5acaaa8 /src/app
parent663462c20c3595fa2639c5c76cc53496da99be8b (diff)
deflatetest: add static huffman support
Diffstat (limited to 'src/app')
-rw-r--r--src/app/deflatetest/main.cc59
1 files changed, 54 insertions, 5 deletions
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;