diff options
Diffstat (limited to 'decoder.h')
| -rw-r--r-- | decoder.h | 168 |
1 files changed, 75 insertions, 93 deletions
@@ -1,5 +1,5 @@ /* Lunzip - Decompressor for lzip files - Copyright (C) 2010, 2011, 2012 Antonio Diaz Diaz. + Copyright (C) 2010, 2011, 2012, 2013 Antonio Diaz Diaz. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -19,7 +19,7 @@ enum { rd_buffer_size = 16384 }; struct Range_decoder { - long long partial_member_pos; + unsigned long long partial_member_pos; uint8_t * buffer; /* input buffer */ int pos; /* current pos in buffer */ int stream_pos; /* when reached, a new block must be read */ @@ -51,7 +51,8 @@ static inline void Rd_free( struct Range_decoder * const rdec ) static inline bool Rd_finished( struct Range_decoder * const rdec ) { return rdec->pos >= rdec->stream_pos && !Rd_read_block( rdec ); } -static inline long long Rd_member_position( const struct Range_decoder * const rdec ) +static inline unsigned long long +Rd_member_position( const struct Range_decoder * const rdec ) { return rdec->partial_member_pos + rdec->pos; } static inline void Rd_reset_member_position( struct Range_decoder * const rdec ) @@ -59,7 +60,7 @@ static inline void Rd_reset_member_position( struct Range_decoder * const rdec ) static inline uint8_t Rd_get_byte( struct Range_decoder * const rdec ) { - if( Rd_finished( rdec ) ) return 0x55; /* make code != 0 */ + if( Rd_finished( rdec ) ) return 0xAA; /* make code != 0 */ return rdec->buffer[rdec->pos++]; } @@ -74,16 +75,16 @@ static inline int Rd_read_data( struct Range_decoder * const rdec, rdec->pos += rd; rest -= rd; } - return ( rest > 0 ) ? size - rest : size; + return size - rest; } static inline void Rd_load( struct Range_decoder * const rdec ) { int i; rdec->code = 0; - rdec->range = 0xFFFFFFFFU; for( i = 0; i < 5; ++i ) rdec->code = (rdec->code << 8) | Rd_get_byte( rdec ); + rdec->range = 0xFFFFFFFFU; } static inline void Rd_normalize( struct Range_decoder * const rdec ) @@ -102,20 +103,15 @@ static inline int Rd_decode( struct Range_decoder * const rdec, int i; for( i = num_bits; i > 0; --i ) { - symbol <<= 1; - if( rdec->range <= 0x00FFFFFFU ) - { - rdec->range <<= 7; - rdec->code = (rdec->code << 8) | Rd_get_byte( rdec ); - if( rdec->code >= rdec->range ) - { rdec->code -= rdec->range; symbol |= 1; } - } - else - { - rdec->range >>= 1; - if( rdec->code >= rdec->range ) - { rdec->code -= rdec->range; symbol |= 1; } - } + uint32_t mask; + Rd_normalize( rdec ); + rdec->range >>= 1; +/* symbol <<= 1; */ +/* if( rdec->code >= rdec->range ) { rdec->code -= rdec->range; symbol |= 1; } */ + mask = 0U - (rdec->code < rdec->range); + rdec->code -= rdec->range; + rdec->code += rdec->range & mask; + symbol = (symbol << 1) + (mask + 1); } return symbol; } @@ -151,6 +147,19 @@ static inline int Rd_decode_tree( struct Range_decoder * const rdec, return model - (1 << num_bits); } +static inline int Rd_decode_tree6( struct Range_decoder * const rdec, + Bit_model bm[] ) + { + int model = 1; + model = ( model << 1 ) | Rd_decode_bit( rdec, &bm[model] ); + model = ( model << 1 ) | Rd_decode_bit( rdec, &bm[model] ); + model = ( model << 1 ) | Rd_decode_bit( rdec, &bm[model] ); + model = ( model << 1 ) | Rd_decode_bit( rdec, &bm[model] ); + model = ( model << 1 ) | Rd_decode_bit( rdec, &bm[model] ); + model = ( model << 1 ) | Rd_decode_bit( rdec, &bm[model] ); + return model - (1 << 6); + } + static inline int Rd_decode_tree_reversed( struct Range_decoder * const rdec, Bit_model bm[], const int num_bits ) { @@ -159,32 +168,49 @@ static inline int Rd_decode_tree_reversed( struct Range_decoder * const rdec, int i; for( i = 0; i < num_bits; ++i ) { - const int bit = Rd_decode_bit( rdec, &bm[model] ); + const bool bit = Rd_decode_bit( rdec, &bm[model] ); model <<= 1; - if( bit ) { model |= 1; symbol |= (1 << i); } + if( bit ) { ++model; symbol |= (1 << i); } } return symbol; } +static inline int Rd_decode_tree_reversed4( struct Range_decoder * const rdec, + Bit_model bm[] ) + { + int model = 1; + int symbol = 0; + int bit = Rd_decode_bit( rdec, &bm[model] ); + model = (model << 1) + bit; symbol |= bit; + bit = Rd_decode_bit( rdec, &bm[model] ); + model = (model << 1) + bit; symbol |= (bit << 1); + bit = Rd_decode_bit( rdec, &bm[model] ); + model = (model << 1) + bit; symbol |= (bit << 2); + if( Rd_decode_bit( rdec, &bm[model] ) ) symbol |= 8; + return symbol; + } + static inline int Rd_decode_matched( struct Range_decoder * const rdec, - Bit_model bm[], const int match_byte ) + Bit_model bm[], int match_byte ) { Bit_model * const bm1 = bm + 0x100; int symbol = 1; int i; for( i = 7; i >= 0; --i ) { - const int match_bit = ( match_byte >> i ) & 1; - const int bit = Rd_decode_bit( rdec, &bm1[(match_bit<<8)+symbol] ); + int match_bit, bit; + match_byte <<= 1; + match_bit = match_byte & 0x100; + bit = Rd_decode_bit( rdec, &bm1[match_bit+symbol] ); symbol = ( symbol << 1 ) | bit; - if( match_bit != bit ) + if( match_bit != bit << 8 ) { - while( --i >= 0 ) + while( symbol < 0x100 ) symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); break; } } - return symbol & 0xFF; + return symbol - 0x100; } @@ -199,17 +225,11 @@ struct Len_decoder static inline void Led_init( struct Len_decoder * const len_decoder ) { - int i, j; Bm_init( &len_decoder->choice1 ); Bm_init( &len_decoder->choice2 ); - for( i = 0; i < pos_states; ++i ) - for( j = 0; j < len_low_symbols; ++j ) - Bm_init( &len_decoder->bm_low[i][j] ); - for( i = 0; i < pos_states; ++i ) - for( j = 0; j < len_mid_symbols; ++j ) - Bm_init( &len_decoder->bm_mid[i][j] ); - for( i = 0; i < len_high_symbols; ++i ) - Bm_init( &len_decoder->bm_high[i] ); + Bm_array_init( len_decoder->bm_low[0], pos_states * len_low_symbols ); + Bm_array_init( len_decoder->bm_mid[0], pos_states * len_mid_symbols ); + Bm_array_init( len_decoder->bm_high, len_high_symbols ); } static inline int Led_decode( struct Len_decoder * const len_decoder, @@ -226,37 +246,9 @@ static inline int Led_decode( struct Len_decoder * const len_decoder, } -struct Literal_decoder - { - Bit_model bm_literal[1<<literal_context_bits][0x300]; - }; - -static inline void Lid_init( struct Literal_decoder * const lidec ) - { - int i, j; - for( i = 0; i < 1<<literal_context_bits; ++i ) - for( j = 0; j < 0x300; ++j ) - Bm_init( &lidec->bm_literal[i][j] ); - } - -static inline int Lid_state( const uint8_t prev_byte ) - { return ( prev_byte >> ( 8 - literal_context_bits ) ); } - -static inline uint8_t Lid_decode( struct Literal_decoder * const lidec, - struct Range_decoder * const rdec, - const uint8_t prev_byte ) - { return Rd_decode_tree( rdec, lidec->bm_literal[Lid_state(prev_byte)], 8 ); } - -static inline uint8_t Lid_decode_matched( struct Literal_decoder * const lidec, - struct Range_decoder * const rdec, - const uint8_t prev_byte, - const uint8_t match_byte ) - { return Rd_decode_matched( rdec, lidec->bm_literal[Lid_state(prev_byte)], match_byte ); } - - struct LZ_decoder { - long long partial_data_pos; + unsigned long long partial_data_pos; int dictionary_size; int buffer_size; uint8_t * buffer; /* output buffer */ @@ -266,6 +258,7 @@ struct LZ_decoder int outfd; /* output file descriptor */ int member_version; + Bit_model bm_literal[1<<literal_context_bits][0x300]; Bit_model bm_match[states][pos_states]; Bit_model bm_rep[states]; Bit_model bm_rep0[states]; @@ -273,13 +266,12 @@ struct LZ_decoder Bit_model bm_rep2[states]; Bit_model bm_len[states][pos_states]; Bit_model bm_dis_slot[max_dis_states][1<<dis_slot_bits]; - Bit_model bm_dis[modeled_distances-end_dis_model+1]; + Bit_model bm_dis[modeled_distances-end_dis_model]; Bit_model bm_align[dis_align_size]; struct Range_decoder * range_decoder; struct Len_decoder len_decoder; struct Len_decoder rep_match_len_decoder; - struct Literal_decoder literal_decoder; }; void LZd_flush_data( struct LZ_decoder * const decoder ); @@ -315,12 +307,12 @@ static inline void LZd_copy_block( struct LZ_decoder * const decoder, int i = decoder->pos - distance - 1; if( i < 0 ) i += decoder->buffer_size; if( len < decoder->buffer_size - max( decoder->pos, i ) && - len <= abs( decoder->pos - i ) ) + len <= abs( decoder->pos - i ) ) /* no wrap, no overlap */ { memcpy( decoder->buffer + decoder->pos, decoder->buffer + i, len ); decoder->pos += len; } - else for( ; len > 0 ; --len ) + else for( ; len > 0; --len ) { decoder->buffer[decoder->pos] = decoder->buffer[i]; if( ++decoder->pos >= decoder->buffer_size ) LZd_flush_data( decoder ); @@ -332,7 +324,6 @@ static inline bool LZd_init( struct LZ_decoder * const decoder, const File_header header, struct Range_decoder * const rdec, const int ofd ) { - int i, j; decoder->partial_data_pos = 0; decoder->dictionary_size = Fh_get_dictionary_size( header ); decoder->buffer_size = max( 65536, decoder->dictionary_size ); @@ -344,30 +335,20 @@ static inline bool LZd_init( struct LZ_decoder * const decoder, decoder->outfd = ofd; decoder->member_version = Fh_version( header ); - for( i = 0; i < states; ++i ) - { - for( j = 0; j < pos_states; ++j ) - { - Bm_init( &decoder->bm_match[i][j] ); - Bm_init( &decoder->bm_len[i][j] ); - } - Bm_init( &decoder->bm_rep[i] ); - Bm_init( &decoder->bm_rep0[i] ); - Bm_init( &decoder->bm_rep1[i] ); - Bm_init( &decoder->bm_rep2[i] ); - } - for( i = 0; i < max_dis_states; ++i ) - for( j = 0; j < 1<<dis_slot_bits; ++j ) - Bm_init( &decoder->bm_dis_slot[i][j] ); - for( i = 0; i < modeled_distances-end_dis_model+1; ++i ) - Bm_init( &decoder->bm_dis[i] ); - for( i = 0; i < dis_align_size; ++i ) - Bm_init( &decoder->bm_align[i] ); + Bm_array_init( decoder->bm_literal[0], (1 << literal_context_bits) * 0x300 ); + Bm_array_init( decoder->bm_match[0], states * pos_states ); + Bm_array_init( decoder->bm_rep, states ); + Bm_array_init( decoder->bm_rep0, states ); + Bm_array_init( decoder->bm_rep1, states ); + Bm_array_init( decoder->bm_rep2, states ); + Bm_array_init( decoder->bm_len[0], states * pos_states ); + Bm_array_init( decoder->bm_dis_slot[0], max_dis_states * (1 << dis_slot_bits) ); + Bm_array_init( decoder->bm_dis, modeled_distances - end_dis_model ); + Bm_array_init( decoder->bm_align, dis_align_size ); decoder->range_decoder = rdec; Led_init( &decoder->len_decoder ); Led_init( &decoder->rep_match_len_decoder ); - Lid_init( &decoder->literal_decoder ); decoder->buffer[decoder->buffer_size-1] = 0; /* prev_byte of first_byte */ return true; } @@ -375,10 +356,11 @@ static inline bool LZd_init( struct LZ_decoder * const decoder, static inline void LZd_free( struct LZ_decoder * const decoder ) { free( decoder->buffer ); } -static inline uint32_t LZd_crc( const struct LZ_decoder * const decoder ) +static inline unsigned LZd_crc( const struct LZ_decoder * const decoder ) { return decoder->crc ^ 0xFFFFFFFFU; } -static inline long long LZd_data_position( const struct LZ_decoder * const decoder ) +static inline unsigned long long +LZd_data_position( const struct LZ_decoder * const decoder ) { return decoder->partial_data_pos + decoder->pos; } int LZd_decode_member( struct LZ_decoder * const decoder, |