From c3bc07039aef7d65e309400a1ed304e6ee6ea070 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 May 2017 17:50:41 +0200 Subject: Merging upstream version 1.9. Signed-off-by: Daniel Baumann --- decoder.h | 245 ++++++++++++++++++++++++++++---------------------------------- 1 file changed, 112 insertions(+), 133 deletions(-) (limited to 'decoder.h') diff --git a/decoder.h b/decoder.h index 922426c..e3a4f1c 100644 --- a/decoder.h +++ b/decoder.h @@ -1,5 +1,5 @@ /* Lunzip - Decompressor for the lzip format - Copyright (C) 2010-2016 Antonio Diaz Diaz. + Copyright (C) 2010-2017 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 @@ -56,7 +56,7 @@ 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 ) - { rdec->partial_member_pos = -rdec->pos; } + { rdec->partial_member_pos = 0; rdec->partial_member_pos -= rdec->pos; } static inline uint8_t Rd_get_byte( struct Range_decoder * const rdec ) { @@ -68,23 +68,22 @@ static inline uint8_t Rd_get_byte( struct Range_decoder * const rdec ) static inline int Rd_read_data( struct Range_decoder * const rdec, uint8_t * const outbuf, const int size ) { - int rest = size; - while( rest > 0 && !Rd_finished( rdec ) ) + int sz = 0; + while( sz < size && !Rd_finished( rdec ) ) { - const int rd = min( rest, rdec->stream_pos - rdec->pos ); - memcpy( outbuf + size - rest, rdec->buffer + rdec->pos, rd ); + const int rd = min( size - sz, rdec->stream_pos - rdec->pos ); + memcpy( outbuf + sz, rdec->buffer + rdec->pos, rd ); rdec->pos += rd; - rest -= rd; + sz += rd; } - return size - rest; + return sz; } static inline void Rd_load( struct Range_decoder * const rdec ) { int i; rdec->code = 0; - for( i = 0; i < 5; ++i ) - rdec->code = (rdec->code << 8) | Rd_get_byte( rdec ); + for( i = 0; i < 5; ++i ) rdec->code = (rdec->code << 8) | Rd_get_byte( rdec ); rdec->range = 0xFFFFFFFFU; rdec->code &= rdec->range; /* make sure that first byte is discarded */ } @@ -92,34 +91,30 @@ static inline void Rd_load( struct Range_decoder * const rdec ) static inline void Rd_normalize( struct Range_decoder * const rdec ) { if( rdec->range <= 0x00FFFFFFU ) - { - rdec->range <<= 8; - rdec->code = (rdec->code << 8) | Rd_get_byte( rdec ); - } + { rdec->range <<= 8; rdec->code = (rdec->code << 8) | Rd_get_byte( rdec ); } } -static inline int Rd_decode( struct Range_decoder * const rdec, - const int num_bits ) +static inline unsigned Rd_decode( struct Range_decoder * const rdec, + const int num_bits ) { - int symbol = 0; + unsigned symbol = 0; int i; for( i = num_bits; i > 0; --i ) { - uint32_t mask; + bool bit; 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); + bit = ( rdec->code >= rdec->range ); + symbol = ( symbol << 1 ) + bit; + rdec->code -= rdec->range & ( 0U - bit ); } return symbol; } -static inline int Rd_decode_bit( struct Range_decoder * const rdec, - Bit_model * const probability ) +static inline unsigned Rd_decode_bit( struct Range_decoder * const rdec, + Bit_model * const probability ) { uint32_t bound; Rd_normalize( rdec ); @@ -139,20 +134,20 @@ static inline int Rd_decode_bit( struct Range_decoder * const rdec, } } -static inline int Rd_decode_tree( struct Range_decoder * const rdec, - Bit_model bm[], const int num_bits ) +static inline unsigned Rd_decode_tree3( struct Range_decoder * const rdec, + Bit_model bm[] ) { - int symbol = 1; - int i; - for( i = num_bits; i > 0; --i ) - symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); - return symbol - (1 << num_bits); + unsigned symbol = 1; + symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); + symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); + symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); + return symbol & 7; } -static inline int Rd_decode_tree6( struct Range_decoder * const rdec, - Bit_model bm[] ) +static inline unsigned Rd_decode_tree6( struct Range_decoder * const rdec, + Bit_model bm[] ) { - int symbol = 1; + unsigned symbol = 1; symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); @@ -162,69 +157,69 @@ static inline int Rd_decode_tree6( struct Range_decoder * const rdec, return symbol & 0x3F; } -static inline int Rd_decode_tree_reversed( struct Range_decoder * const rdec, - Bit_model bm[], const int num_bits ) +static inline unsigned Rd_decode_tree8( struct Range_decoder * const rdec, + Bit_model bm[] ) { - int model = 1; - int symbol = 0; + unsigned symbol = 1; + int i; + for( i = 0; i < 8; ++i ) + symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); + return symbol & 0xFF; + } + +static inline unsigned +Rd_decode_tree_reversed( struct Range_decoder * const rdec, + Bit_model bm[], const int num_bits ) + { + unsigned model = 1; + unsigned symbol = 0; int i; for( i = 0; i < num_bits; ++i ) { - const bool bit = Rd_decode_bit( rdec, &bm[model] ); - model <<= 1; - if( bit ) { ++model; symbol |= (1 << i); } + const unsigned bit = Rd_decode_bit( rdec, &bm[model] ); + model = ( model << 1 ) + bit; + symbol |= ( bit << i ); } return symbol; } -static inline int Rd_decode_tree_reversed4( struct Range_decoder * const rdec, - Bit_model bm[] ) +static inline unsigned +Rd_decode_tree_reversed4( struct Range_decoder * const rdec, Bit_model bm[] ) { - int model = 1; - int symbol = Rd_decode_bit( rdec, &bm[model] ); - int bit; - model = (model << 1) + symbol; - bit = Rd_decode_bit( rdec, &bm[model] ); - model = (model << 1) + bit; symbol |= (bit << 1); + unsigned symbol = Rd_decode_bit( rdec, &bm[1] ); + unsigned model = 2 + symbol; + unsigned 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; + model = ( model << 1 ) + bit; symbol |= ( bit << 2 ); + symbol |= ( Rd_decode_bit( rdec, &bm[model] ) << 3 ); return symbol; } -static inline int Rd_decode_matched( struct Range_decoder * const rdec, - Bit_model bm[], int match_byte ) +static inline unsigned Rd_decode_matched( struct Range_decoder * const rdec, + Bit_model bm[], unsigned match_byte ) { - Bit_model * const bm1 = bm + 0x100; - int symbol = 1; - while( symbol < 0x100 ) + unsigned symbol = 1; + unsigned mask = 0x100; + while( true ) { - 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 << 8 ) - { - while( symbol < 0x100 ) - symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); - break; - } + const unsigned match_bit = ( match_byte <<= 1 ) & mask; + const unsigned bit = Rd_decode_bit( rdec, &bm[symbol+match_bit+mask] ); + symbol = ( symbol << 1 ) + bit; + if( symbol > 0xFF ) return symbol & 0xFF; + mask &= ~(match_bit ^ (bit << 8)); /* if( match_bit != bit ) mask = 0; */ } - return symbol & 0xFF; } -static inline int Rd_decode_len( struct Range_decoder * const rdec, - struct Len_model * const lm, - const int pos_state ) +static inline unsigned Rd_decode_len( struct Range_decoder * const rdec, + struct Len_model * const lm, + const int pos_state ) { if( Rd_decode_bit( rdec, &lm->choice1 ) == 0 ) - return Rd_decode_tree( rdec, lm->bm_low[pos_state], len_low_bits ); + return Rd_decode_tree3( rdec, lm->bm_low[pos_state] ); if( Rd_decode_bit( rdec, &lm->choice2 ) == 0 ) - return len_low_symbols + - Rd_decode_tree( rdec, lm->bm_mid[pos_state], len_mid_bits ); - return len_low_symbols + len_mid_symbols + - Rd_decode_tree( rdec, lm->bm_high, len_high_bits ); + return len_low_symbols + Rd_decode_tree3( rdec, lm->bm_mid[pos_state] ); + return len_low_symbols + len_mid_symbols + Rd_decode_tree8( rdec, lm->bm_high ); } @@ -233,49 +228,37 @@ struct LZ_decoder unsigned long long partial_data_pos; struct Range_decoder * rdec; unsigned dictionary_size; - int buffer_size; + unsigned buffer_size; uint8_t * buffer; /* output buffer */ - int pos; /* current pos in buffer */ - int stream_pos; /* first byte not yet written to file */ + unsigned pos; /* current pos in buffer */ + unsigned stream_pos; /* first byte not yet written to file */ uint32_t crc; int outfd; /* output file descriptor */ bool pos_wrapped; - - Bit_model bm_literal[1<pos > 0 ) ? d->pos : d->buffer_size ) - 1; - return d->buffer[i]; + if( d->pos > 0 ) return d->buffer[d->pos-1]; + if( d->pos_wrapped ) return d->buffer[d->buffer_size-1]; + return 0; /* prev_byte of first byte */ } static inline uint8_t LZd_peek( const struct LZ_decoder * const d, - const int distance ) + const unsigned distance ) { uint8_t b; - const int i = d->pos - distance - 1; - if( i >= 0 ) b = d->buffer[i]; - else if( i + d->buffer_size >= d->pos ) - b = d->buffer[i+d->buffer_size]; - else if( seek_read( d->outfd, &b, 1, i - d->stream_pos ) != 1 ) + if( d->pos > distance ) b = d->buffer[d->pos-distance-1]; + else if( d->buffer_size > distance ) + b = d->buffer[d->buffer_size+d->pos-distance-1]; + else if( seek_read_back( d->outfd, &b, 1, + distance + 1 + d->stream_pos - d->pos ) != 1 ) { show_error( "Seek error", errno, false ); cleanup_and_fail( 1 ); } return b; } @@ -287,19 +270,28 @@ static inline void LZd_put_byte( struct LZ_decoder * const d, const uint8_t b ) } static inline void LZd_copy_block( struct LZ_decoder * const d, - const int distance, int len ) + const unsigned distance, unsigned len ) { - int i = d->pos - distance - 1; - bool fast; - if( i < 0 ) - { i += d->buffer_size; - fast = ( len <= d->buffer_size - i && len <= i - d->pos ); } + unsigned lpos = d->pos, i = lpos - distance - 1; + bool fast, fast2; + if( lpos > distance ) + { + fast = ( len < d->buffer_size - lpos ); + fast2 = ( fast && len <= lpos - i ); + } else - fast = ( len < d->buffer_size - d->pos && len <= d->pos - i ); - if( fast ) /* no wrap, no overlap */ { - memcpy( d->buffer + d->pos, d->buffer + i, len ); + i += d->buffer_size; + fast = ( len < d->buffer_size - i ); /* (i == pos) may happen */ + fast2 = ( fast && len <= i - lpos ); + } + if( fast ) /* no wrap */ + { d->pos += len; + if( fast2 ) /* no wrap, no overlap */ + memcpy( d->buffer + lpos, d->buffer + i, len ); + else + for( ; len > 0; --len ) d->buffer[lpos++] = d->buffer[i++]; } else for( ; len > 0; --len ) { @@ -310,16 +302,16 @@ static inline void LZd_copy_block( struct LZ_decoder * const d, } static inline void LZd_copy_block2( struct LZ_decoder * const d, - const int distance, int len ) + const unsigned distance, unsigned len ) { - if( distance < d->buffer_size ) /* block is in buffer */ + if( d->buffer_size > distance ) /* block is in buffer */ { LZd_copy_block( d, distance, len ); return; } if( len < d->buffer_size - d->pos ) /* no wrap */ { - const int offset = d->pos - d->stream_pos - distance - 1; - if( len <= -offset ) /* block is in file */ + const unsigned offset = distance + 1 + d->stream_pos - d->pos; + if( len <= offset ) /* block is in file */ { - if( seek_read( d->outfd, d->buffer + d->pos, len, offset ) != len ) + if( seek_read_back( d->outfd, d->buffer + d->pos, len, offset ) != len ) { show_error( "Seek error", errno, false ); cleanup_and_fail( 1 ); } d->pos += len; return; @@ -331,8 +323,8 @@ static inline void LZd_copy_block2( struct LZ_decoder * const d, static inline bool LZd_init( struct LZ_decoder * const d, struct Range_decoder * const rde, - const int buffer_size, - const int dict_size, const int ofd ) + const unsigned buffer_size, + const unsigned dict_size, const int ofd ) { d->partial_data_pos = 0; d->rdec = rde; @@ -345,20 +337,7 @@ static inline bool LZd_init( struct LZ_decoder * const d, d->crc = 0xFFFFFFFFU; d->outfd = ofd; d->pos_wrapped = false; - - Bm_array_init( d->bm_literal[0], (1 << literal_context_bits) * 0x300 ); - Bm_array_init( d->bm_match[0], states * pos_states ); - Bm_array_init( d->bm_rep, states ); - Bm_array_init( d->bm_rep0, states ); - Bm_array_init( d->bm_rep1, states ); - Bm_array_init( d->bm_rep2, states ); - Bm_array_init( d->bm_len[0], states * pos_states ); - Bm_array_init( d->bm_dis_slot[0], len_states * (1 << dis_slot_bits) ); - Bm_array_init( d->bm_dis, modeled_distances - end_dis_model ); - Bm_array_init( d->bm_align, dis_align_size ); - Lm_init( &d->match_len_model ); - Lm_init( &d->rep_len_model ); - d->buffer[d->buffer_size-1] = 0; /* prev_byte of first byte */ + d->pos_wrapped_dic = false; return true; } -- cgit v1.2.3