diff options
Diffstat (limited to 'decoder.h')
| -rw-r--r-- | decoder.h | 173 |
1 files changed, 107 insertions, 66 deletions
@@ -1,23 +1,23 @@ -/* Lzlib - Compression library for the lzip format - Copyright (C) 2009-2019 Antonio Diaz Diaz. +/* Lzlib - Compression library for the lzip format + Copyright (C) 2009-2024 Antonio Diaz Diaz. - This library is free software. Redistribution and use in source and - binary forms, with or without modification, are permitted provided - that the following conditions are met: + This library is free software. Redistribution and use in source and + binary forms, with or without modification, are permitted provided + that the following conditions are met: - 1. Redistributions of source code must retain the above copyright - notice, this list of conditions and the following disclaimer. + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions, and the following disclaimer. - 2. Redistributions in binary form must reproduce the above copyright - notice, this list of conditions and the following disclaimer in the - documentation and/or other materials provided with the distribution. + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions, and the following disclaimer in the + documentation and/or other materials provided with the distribution. - This library 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. + This library 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. */ -enum { rd_min_available_bytes = 8 }; +enum { rd_min_available_bytes = 10 }; struct Range_decoder { @@ -50,7 +50,7 @@ static inline void Rd_finish( struct Range_decoder * const rdec ) { rdec->at_stream_end = true; } static inline bool Rd_enough_available_bytes( const struct Range_decoder * const rdec ) - { return ( Cb_used_bytes( &rdec->cb ) >= rd_min_available_bytes ); } + { return Cb_used_bytes( &rdec->cb ) >= rd_min_available_bytes; } static inline unsigned Rd_available_bytes( const struct Range_decoder * const rdec ) { return Cb_used_bytes( &rdec->cb ); } @@ -72,8 +72,8 @@ static inline void Rd_reset( struct Range_decoder * const rdec ) rdec->member_position = 0; rdec->at_stream_end = false; } -/* Seeks a member header and updates 'get'. '*skippedp' is set to the - number of bytes skipped. Returns true if it finds a valid header. +/* Seek for a member header and update 'get'. Set '*skippedp' to the number + of bytes skipped. Return true if a valid header is found. */ static bool Rd_find_header( struct Range_decoder * const rdec, unsigned * const skippedp ) @@ -92,7 +92,7 @@ static bool Rd_find_header( struct Range_decoder * const rdec, header[i] = rdec->cb.buffer[get]; if( ++get >= rdec->cb.buffer_size ) get = 0; } - if( Lh_verify( header ) ) return true; + if( Lh_check( header ) ) return true; } if( ++rdec->cb.get >= rdec->cb.buffer_size ) rdec->cb.get = 0; ++*skippedp; @@ -133,18 +133,16 @@ static inline bool Rd_unread_data( struct Range_decoder * const rdec, return true; } -static bool Rd_try_reload( struct Range_decoder * const rdec, const bool force ) +static bool Rd_try_reload( struct Range_decoder * const rdec ) { - if( force ) rdec->reload_pending = true; if( rdec->reload_pending && Rd_available_bytes( rdec ) >= 5 ) { - int i; rdec->reload_pending = false; rdec->code = 0; - 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 */ + Rd_get_byte( rdec ); /* discard first byte of the LZMA stream */ + int i; for( i = 0; i < 4; ++i ) + rdec->code = (rdec->code << 8) | Rd_get_byte( rdec ); } return !rdec->reload_pending; } @@ -162,13 +160,12 @@ static inline unsigned Rd_decode( struct Range_decoder * const rdec, int i; for( i = num_bits; i > 0; --i ) { - bool bit; Rd_normalize( rdec ); rdec->range >>= 1; /* symbol <<= 1; */ /* if( rdec->code >= rdec->range ) { rdec->code -= rdec->range; symbol |= 1; } */ - bit = ( rdec->code >= rdec->range ); - symbol = ( symbol << 1 ) + bit; + const bool bit = ( rdec->code >= rdec->range ); + symbol <<= 1; symbol += bit; rdec->code -= rdec->range & ( 0U - bit ); } return symbol; @@ -177,44 +174,75 @@ static inline unsigned Rd_decode( struct Range_decoder * const rdec, static inline unsigned Rd_decode_bit( struct Range_decoder * const rdec, Bit_model * const probability ) { - uint32_t bound; Rd_normalize( rdec ); - bound = ( rdec->range >> bit_model_total_bits ) * *probability; + const uint32_t bound = ( rdec->range >> bit_model_total_bits ) * *probability; if( rdec->code < bound ) { rdec->range = bound; - *probability += (bit_model_total - *probability) >> bit_model_move_bits; + *probability += ( bit_model_total - *probability ) >> bit_model_move_bits; return 0; } else { - rdec->range -= bound; rdec->code -= bound; + rdec->range -= bound; *probability -= *probability >> bit_model_move_bits; return 1; } } -static inline unsigned Rd_decode_tree3( struct Range_decoder * const rdec, - Bit_model bm[] ) +static inline void Rd_decode_symbol_bit( struct Range_decoder * const rdec, + Bit_model * const probability, unsigned * symbol ) { - 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; + Rd_normalize( rdec ); + *symbol <<= 1; + const uint32_t bound = ( rdec->range >> bit_model_total_bits ) * *probability; + if( rdec->code < bound ) + { + rdec->range = bound; + *probability += ( bit_model_total - *probability ) >> bit_model_move_bits; + } + else + { + rdec->code -= bound; + rdec->range -= bound; + *probability -= *probability >> bit_model_move_bits; + *symbol |= 1; + } + } + +static inline void Rd_decode_symbol_bit_reversed( struct Range_decoder * const rdec, + Bit_model * const probability, unsigned * model, + unsigned * symbol, const int i ) + { + Rd_normalize( rdec ); + *model <<= 1; + const uint32_t bound = ( rdec->range >> bit_model_total_bits ) * *probability; + if( rdec->code < bound ) + { + rdec->range = bound; + *probability += ( bit_model_total - *probability ) >> bit_model_move_bits; + } + else + { + rdec->code -= bound; + rdec->range -= bound; + *probability -= *probability >> bit_model_move_bits; + *model |= 1; + *symbol |= 1 << i; + } } static inline unsigned Rd_decode_tree6( struct Range_decoder * const rdec, Bit_model bm[] ) { 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] ); - 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] ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); return symbol & 0x3F; } @@ -222,9 +250,14 @@ static inline unsigned Rd_decode_tree8( struct Range_decoder * const rdec, Bit_model bm[] ) { unsigned symbol = 1; - int i; - for( i = 0; i < 8; ++i ) - symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); return symbol & 0xFF; } @@ -236,24 +269,19 @@ Rd_decode_tree_reversed( struct Range_decoder * const rdec, unsigned symbol = 0; int i; for( i = 0; i < num_bits; ++i ) - { - const unsigned bit = Rd_decode_bit( rdec, &bm[model] ); - model = ( model << 1 ) + bit; - symbol |= ( bit << i ); - } + Rd_decode_symbol_bit_reversed( rdec, &bm[model], &model, &symbol, i ); return symbol; } static inline unsigned Rd_decode_tree_reversed4( struct Range_decoder * const rdec, Bit_model bm[] ) { - 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 ); - symbol |= ( Rd_decode_bit( rdec, &bm[model] ) << 3 ); + unsigned model = 1; + unsigned symbol = 0; + Rd_decode_symbol_bit_reversed( rdec, &bm[model], &model, &symbol, 0 ); + Rd_decode_symbol_bit_reversed( rdec, &bm[model], &model, &symbol, 1 ); + Rd_decode_symbol_bit_reversed( rdec, &bm[model], &model, &symbol, 2 ); + Rd_decode_symbol_bit_reversed( rdec, &bm[model], &model, &symbol, 3 ); return symbol; } @@ -266,7 +294,7 @@ static inline unsigned Rd_decode_matched( struct Range_decoder * const rdec, { const unsigned match_bit = ( match_byte <<= 1 ) & mask; const unsigned bit = Rd_decode_bit( rdec, &bm[symbol+match_bit+mask] ); - symbol = ( symbol << 1 ) + bit; + symbol <<= 1; symbol += bit; if( symbol > 0xFF ) return symbol & 0xFF; mask &= ~(match_bit ^ (bit << 8)); /* if( match_bit != bit ) mask = 0; */ } @@ -276,11 +304,24 @@ static inline unsigned Rd_decode_len( struct Range_decoder * const rdec, struct Len_model * const lm, const int pos_state ) { + Bit_model * bm; + unsigned mask, offset, symbol = 1; + if( Rd_decode_bit( rdec, &lm->choice1 ) == 0 ) - return Rd_decode_tree3( rdec, lm->bm_low[pos_state] ); + { bm = lm->bm_low[pos_state]; mask = 7; offset = 0; goto len3; } if( Rd_decode_bit( rdec, &lm->choice2 ) == 0 ) - 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 ); + { bm = lm->bm_mid[pos_state]; mask = 7; offset = len_low_symbols; goto len3; } + bm = lm->bm_high; mask = 0xFF; offset = len_low_symbols + len_mid_symbols; + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); +len3: + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); + return ( symbol & mask ) + min_match_len + offset; } @@ -293,8 +334,8 @@ struct LZ_decoder struct Range_decoder * rdec; unsigned dictionary_size; uint32_t crc; + bool check_trailer_pending; bool member_finished; - bool verify_trailer_pending; bool pos_wrapped; unsigned rep0; /* rep[0-3] latest four distances */ unsigned rep1; /* used for efficient coding of */ @@ -382,8 +423,8 @@ static inline bool LZd_init( struct LZ_decoder * const d, d->rdec = rde; d->dictionary_size = dict_size; d->crc = 0xFFFFFFFFU; + d->check_trailer_pending = false; d->member_finished = false; - d->verify_trailer_pending = false; d->pos_wrapped = false; /* prev_byte of first byte; also for LZd_peek( 0 ) on corrupt file */ d->cb.buffer[d->cb.buffer_size-1] = 0; @@ -412,7 +453,7 @@ static inline void LZd_free( struct LZ_decoder * const d ) { Cb_free( &d->cb ); } static inline bool LZd_member_finished( const struct LZ_decoder * const d ) - { return ( d->member_finished && Cb_empty( &d->cb ) ); } + { return d->member_finished && Cb_empty( &d->cb ); } static inline unsigned LZd_crc( const struct LZ_decoder * const d ) { return d->crc ^ 0xFFFFFFFFU; } |