diff options
Diffstat (limited to 'decoder.h')
| -rw-r--r-- | decoder.h | 393 |
1 files changed, 393 insertions, 0 deletions
diff --git a/decoder.h b/decoder.h new file mode 100644 index 0000000..7df68b9 --- /dev/null +++ b/decoder.h @@ -0,0 +1,393 @@ +/* Clzip - A data compressor based on the LZMA algorithm + Copyright (C) 2010 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 + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ + +enum { Ib_buffer_size = 65536 }; + +struct Input_buffer + { + uint8_t * buffer; + int pos; + int stream_pos; // when reached, a new block must be read + int infd_; // input file descriptor + bool at_stream_end; + }; + +bool Ib_read_block( struct Input_buffer * const ibuf ); + +static inline void Ib_init( struct Input_buffer * const ibuf, const int infd ) + { + ibuf->buffer = (uint8_t *)malloc( Ib_buffer_size ); + if( !ibuf->buffer ) + { + show_error( "not enough memory. Find a machine with more memory", 0, false ); + cleanup_and_fail( 1 ); + } + ibuf->pos = 0; + ibuf->stream_pos = 0; + ibuf->infd_ = infd; + ibuf->at_stream_end = false; + } + +static inline void Ib_free( struct Input_buffer * const ibuf ) + { free( ibuf->buffer ); ibuf->buffer = 0; } + +static inline bool Ib_finished( struct Input_buffer * const ibuf ) + { return ibuf->at_stream_end && ibuf->pos >= ibuf->stream_pos; } + +static inline uint8_t Ib_get_byte( struct Input_buffer * const ibuf ) + { + if( ibuf->pos >= ibuf->stream_pos && !Ib_read_block( ibuf ) ) + return 0; + return ibuf->buffer[ibuf->pos++]; + } + + +struct Range_decoder + { + long long member_pos; + uint32_t code; + uint32_t range; + struct Input_buffer * ibuf; + }; + +static inline uint8_t Rd_get_byte( struct Range_decoder * const range_decoder ) + { + ++range_decoder->member_pos; + return Ib_get_byte( range_decoder->ibuf ); + } + +static inline void Rd_init( struct Range_decoder * const range_decoder, + struct Input_buffer * const buf ) + { + range_decoder->member_pos = sizeof (File_header); + range_decoder->code = 0; + range_decoder->range = 0xFFFFFFFF; + range_decoder->ibuf = buf; + for( int i = 0; i < 5; ++i ) + range_decoder->code = (range_decoder->code << 8) | + Rd_get_byte( range_decoder ); + } + +static inline bool Rd_code_is_zero( struct Range_decoder * const range_decoder ) + { return ( range_decoder->code == 0 ); } +static inline bool Rd_finished( struct Range_decoder * const range_decoder ) + { return Ib_finished( range_decoder->ibuf ); } +static inline long long Rd_member_position( struct Range_decoder * const range_decoder ) + { return range_decoder->member_pos; } + +static inline void Rd_reload( struct Range_decoder * const range_decoder ) + { + range_decoder->code = 0; + range_decoder->range = 0xFFFFFFFF; + for( int i = 0; i < 5; ++i ) + range_decoder->code = (range_decoder->code << 8) | + Rd_get_byte( range_decoder ); + } + +static inline void Rd_normalize( struct Range_decoder * const range_decoder ) + { + if( range_decoder->range <= 0x00FFFFFF ) + { + range_decoder->range <<= 8; + range_decoder->code = (range_decoder->code << 8) | + Rd_get_byte( range_decoder ); + } + } + +static inline int Rd_decode( struct Range_decoder * const range_decoder, + const int num_bits ) + { + int symbol = 0; + for( int i = num_bits; i > 0; --i ) + { + symbol <<= 1; + if( range_decoder->range <= 0x00FFFFFF ) + { + range_decoder->range <<= 7; + range_decoder->code = (range_decoder->code << 8) | + Rd_get_byte( range_decoder ); + if( range_decoder->code >= range_decoder->range ) + { range_decoder->code -= range_decoder->range; symbol |= 1; } + } + else + { + range_decoder->range >>= 1; + if( range_decoder->code >= range_decoder->range ) + { range_decoder->code -= range_decoder->range; symbol |= 1; } + } + } + return symbol; + } + +static inline int Rd_decode_bit( struct Range_decoder * const range_decoder, + Bit_model * const probability ) + { + Rd_normalize( range_decoder ); + const uint32_t bound = ( range_decoder->range >> bit_model_total_bits ) * + *probability; + if( range_decoder->code < bound ) + { + range_decoder->range = bound; + *probability += (bit_model_total - *probability) >> bit_model_move_bits; + return 0; + } + else + { + range_decoder->range -= bound; + range_decoder->code -= bound; + *probability -= *probability >> bit_model_move_bits; + return 1; + } + } + +static inline int Rd_decode_tree( struct Range_decoder * const range_decoder, + Bit_model bm[], const int num_bits ) + { + int model = 1; + for( int i = num_bits; i > 0; --i ) + model = ( model << 1 ) | Rd_decode_bit( range_decoder, &bm[model] ); + return model - (1 << num_bits); + } + +static inline int Rd_decode_tree_reversed( struct Range_decoder * const range_decoder, + Bit_model bm[], const int num_bits ) + { + int model = 1; + int symbol = 0; + for( int i = 0; i < num_bits; ++i ) + { + const int bit = Rd_decode_bit( range_decoder, &bm[model] ); + model <<= 1; + if( bit ) { model |= 1; symbol |= (1 << i); } + } + return symbol; + } + +static inline int Rd_decode_matched( struct Range_decoder * const range_decoder, + Bit_model bm[], const int match_byte ) + { + Bit_model *bm1 = bm + 0x100; + int symbol = 1; + for( int i = 1; i <= 8; ++i ) + { + const int match_bit = ( match_byte << i ) & 0x100; + const int bit = Rd_decode_bit( range_decoder, &bm1[match_bit+symbol] ); + symbol = ( symbol << 1 ) | bit; + if( ( match_bit && !bit ) || ( !match_bit && bit ) ) + { + while( ++i <= 8 ) + symbol = ( symbol << 1 ) | Rd_decode_bit( range_decoder, &bm[symbol] ); + break; + } + } + return symbol & 0xFF; + } + + +struct Len_decoder + { + Bit_model choice1; + Bit_model choice2; + Bit_model bm_low[pos_states][len_low_symbols]; + Bit_model bm_mid[pos_states][len_mid_symbols]; + Bit_model bm_high[len_high_symbols]; + }; + +static inline void Led_init( struct Len_decoder * const len_decoder ) + { + Bm_init( &len_decoder->choice1 ); + Bm_init( &len_decoder->choice2 ); + for( int i = 0; i < pos_states; ++i ) + for( int j = 0; j < len_low_symbols; ++j ) + Bm_init( &len_decoder->bm_low[i][j] ); + for( int i = 0; i < pos_states; ++i ) + for( int j = 0; j < len_mid_symbols; ++j ) + Bm_init( &len_decoder->bm_mid[i][j] ); + for( int i = 0; i < len_high_symbols; ++i ) + Bm_init( &len_decoder->bm_high[i] ); + } + +static inline int Led_decode( struct Len_decoder * const len_decoder, + struct Range_decoder * const range_decoder, + const int pos_state ) + { + if( Rd_decode_bit( range_decoder, &len_decoder->choice1 ) == 0 ) + return Rd_decode_tree( range_decoder, len_decoder->bm_low[pos_state], + len_low_bits ); + if( Rd_decode_bit( range_decoder, &len_decoder->choice2 ) == 0 ) + return len_low_symbols + + Rd_decode_tree( range_decoder, len_decoder->bm_mid[pos_state], + len_mid_bits ); + return len_low_symbols + len_mid_symbols + + Rd_decode_tree( range_decoder, len_decoder->bm_high, len_high_bits ); + } + + +struct Literal_decoder + { + Bit_model bm_literal[1<<literal_context_bits][0x300]; + }; + +static inline void Lid_init( struct Literal_decoder * const literal_decoder ) + { + for( int i = 0; i < 1<<literal_context_bits; ++i ) + for( int j = 0; j < 0x300; ++j ) + Bm_init( &literal_decoder->bm_literal[i][j] ); + } + +static inline int Lid_state( const int prev_byte ) + { return ( prev_byte >> ( 8 - literal_context_bits ) ); } + +static inline uint8_t Lid_decode( struct Literal_decoder * const literal_decoder, + struct Range_decoder * const range_decoder, + const uint8_t prev_byte ) + { return Rd_decode_tree( range_decoder, literal_decoder->bm_literal[Lid_state(prev_byte)], 8 ); } + +static inline uint8_t Lid_decode_matched( struct Literal_decoder * const literal_decoder, + struct Range_decoder * const range_decoder, + const uint8_t prev_byte, + const uint8_t match_byte ) + { return Rd_decode_matched( range_decoder, literal_decoder->bm_literal[Lid_state(prev_byte)], match_byte ); } + + +struct LZ_decoder + { + long long partial_data_pos; + int format_version; + int dictionary_size; + int buffer_size; + uint8_t * buffer; + int pos; + int stream_pos; // first byte not yet written to file + uint32_t crc_; + int outfd_; // output file descriptor + + Bit_model bm_match[St_states][pos_states]; + Bit_model bm_rep[St_states]; + Bit_model bm_rep0[St_states]; + Bit_model bm_rep1[St_states]; + Bit_model bm_rep2[St_states]; + Bit_model bm_len[St_states][pos_states]; + Bit_model bm_dis_slot[max_dis_states][1<<dis_slot_bits]; + 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 ); + +static inline uint8_t LZd_get_byte( struct LZ_decoder * const decoder, + const int distance ) + { + int i = decoder->pos - distance - 1; + if( i < 0 ) i += decoder->buffer_size; + return decoder->buffer[i]; + } + +static inline void LZd_put_byte( struct LZ_decoder * const decoder, + const uint8_t b ) + { + decoder->buffer[decoder->pos] = b; + if( ++decoder->pos >= decoder->buffer_size ) + LZd_flush_data( decoder ); + } + +static inline void LZd_copy_block( struct LZ_decoder * const decoder, + const int distance, int len ) + { + 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 ) ) + { + memcpy( decoder->buffer + decoder->pos, decoder->buffer + i, len ); + decoder->pos += len; + } + else for( ; len > 0 ; --len ) + { + decoder->buffer[decoder->pos] = decoder->buffer[i]; + if( ++decoder->pos >= decoder->buffer_size ) + LZd_flush_data( decoder ); + if( ++i >= decoder->buffer_size ) i = 0; + } + } + +bool LZd_verify_trailer( struct LZ_decoder * const decoder, + struct Pretty_print * const pp ); + +static inline void LZd_init( struct LZ_decoder * const decoder, + const File_header header, + struct Input_buffer * const ibuf, const int outfd ) + { + decoder->partial_data_pos = 0; + decoder->format_version = Fh_version( header ); + decoder->dictionary_size = Fh_get_dictionary_size( header ); + decoder->buffer_size = max( 65536, decoder->dictionary_size ); + decoder->buffer = (uint8_t *)malloc( decoder->buffer_size ); + if( !decoder->buffer ) + { + show_error( "not enough memory. Find a machine with more memory", 0, false ); + cleanup_and_fail( 1 ); + } + decoder->pos = 0; + decoder->stream_pos = 0; + decoder->crc_ = 0xFFFFFFFF; + decoder->outfd_ = outfd; + + for( int i = 0; i < St_states; ++i ) + { + for( int 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( int i = 0; i < max_dis_states; ++i ) + for( int j = 0; j < 1<<dis_slot_bits; ++j ) + Bm_init( &decoder->bm_dis_slot[i][j] ); + for( int i = 0; i < modeled_distances-end_dis_model; ++i ) + Bm_init( &decoder->bm_dis[i] ); + for( int i = 0; i < dis_align_size; ++i ) + Bm_init( &decoder->bm_align[i] ); + + Rd_init( &decoder->range_decoder, ibuf ); + 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 + } + +static inline void LZd_free( struct LZ_decoder * const decoder ) + { free( decoder->buffer ); decoder->buffer = 0; } + +static inline uint32_t LZd_crc( struct LZ_decoder * const decoder ) + { return decoder->crc_ ^ 0xFFFFFFFF; } +int LZd_decode_member( struct LZ_decoder * const decoder, + struct Pretty_print * const pp ); + +static inline long long LZd_member_position( struct LZ_decoder * const decoder ) + { return Rd_member_position( &decoder->range_decoder ); } +static inline long long LZd_data_position( struct LZ_decoder * const decoder ) + { return decoder->partial_data_pos + decoder->pos; } |