is a data compression library providing in-memory LZMA compression and decompression functions using the lzip format.
| decoder.h (lzlib-1.12.tar.lz) | : | decoder.h (lzlib-1.13.tar.lz) |
|---|
| /* Lzlib - Compression library for the lzip format | | /* Lzlib - Compression library for the lzip format |
|
| Copyright (C) 2009-2021 Antonio Diaz Diaz. | | Copyright (C) 2009-2022 Antonio Diaz Diaz. |
| | |
| This library is free software. Redistribution and use in source and | | This library is free software. Redistribution and use in source and |
| binary forms, with or without modification, are permitted provided | | binary forms, with or without modification, are permitted provided |
| that the following conditions are met: | | that the following conditions are met: |
| | |
| 1. Redistributions of source code must retain the above copyright | | 1. Redistributions of source code must retain the above copyright |
| notice, this list of conditions, and the following disclaimer. | | notice, this list of conditions, and the following disclaimer. |
| | |
| 2. Redistributions in binary form must reproduce the above copyright | | 2. Redistributions in binary form must reproduce the above copyright |
| notice, this list of conditions, and the following disclaimer in the | | notice, this list of conditions, and the following disclaimer in the |
| | |
| skipping to change at line 74 | | skipping to change at line 74 |
|---|
| rdec->member_position + Cb_used_bytes( &rdec->cb ); | | rdec->member_position + Cb_used_bytes( &rdec->cb ); |
| Cb_reset( &rdec->cb ); | | Cb_reset( &rdec->cb ); |
| rdec->member_position = 0; rdec->at_stream_end = true; | | rdec->member_position = 0; rdec->at_stream_end = true; |
| return size; | | return size; |
| } | | } |
| | |
| static inline void Rd_reset( struct Range_decoder * const rdec ) | | static inline void Rd_reset( struct Range_decoder * const rdec ) |
| { Cb_reset( &rdec->cb ); | | { Cb_reset( &rdec->cb ); |
| rdec->member_position = 0; rdec->at_stream_end = false; } | | rdec->member_position = 0; rdec->at_stream_end = false; } |
| | |
|
| /* Seeks a member header and updates 'get'. '*skippedp' is set to the | | /* Seek for a member header and update 'get'. Set '*skippedp' to the number |
| number of bytes skipped. Returns true if it finds a valid header. | | of bytes skipped. Return true if a valid header is found. |
| */ | | */ |
| static bool Rd_find_header( struct Range_decoder * const rdec, | | static bool Rd_find_header( struct Range_decoder * const rdec, |
| unsigned * const skippedp ) | | unsigned * const skippedp ) |
| { | | { |
| *skippedp = 0; | | *skippedp = 0; |
| while( rdec->cb.get != rdec->cb.put ) | | while( rdec->cb.get != rdec->cb.put ) |
| { | | { |
| if( rdec->cb.buffer[rdec->cb.get] == lzip_magic[0] ) | | if( rdec->cb.buffer[rdec->cb.get] == lzip_magic[0] ) |
| { | | { |
| unsigned get = rdec->cb.get; | | unsigned get = rdec->cb.get; |
| | |
| skipping to change at line 141 | | skipping to change at line 141 |
|---|
| return true; | | return true; |
| } | | } |
| | |
| static bool Rd_try_reload( struct Range_decoder * const rdec ) | | static bool Rd_try_reload( struct Range_decoder * const rdec ) |
| { | | { |
| if( rdec->reload_pending && Rd_available_bytes( rdec ) >= 5 ) | | if( rdec->reload_pending && Rd_available_bytes( rdec ) >= 5 ) |
| { | | { |
| int i; | | int i; |
| rdec->reload_pending = false; | | rdec->reload_pending = false; |
| rdec->code = 0; | | rdec->code = 0; |
|
| for( i = 0; i < 5; ++i ) | | for( i = 0; i < 5; ++i ) rdec->code = (rdec->code << 8) | Rd_get_byte( rdec |
| rdec->code = (rdec->code << 8) | Rd_get_byte( rdec ); | | ); |
| rdec->range = 0xFFFFFFFFU; | | rdec->range = 0xFFFFFFFFU; |
| rdec->code &= rdec->range; /* make sure that first byte is discarded */ | | rdec->code &= rdec->range; /* make sure that first byte is discarded */ |
| } | | } |
| return !rdec->reload_pending; | | return !rdec->reload_pending; |
| } | | } |
| | |
| static inline void Rd_normalize( struct Range_decoder * const rdec ) | | static inline void Rd_normalize( struct Range_decoder * const rdec ) |
| { | | { |
| if( rdec->range <= 0x00FFFFFFU ) | | 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 unsigned Rd_decode( struct Range_decoder * const rdec, | | static inline unsigned Rd_decode( struct Range_decoder * const rdec, |
| const int num_bits ) | | const int num_bits ) |
| { | | { |
| unsigned symbol = 0; | | unsigned symbol = 0; |
| int i; | | int i; |
| for( i = num_bits; i > 0; --i ) | | for( i = num_bits; i > 0; --i ) |
| { | | { |
|
| bool bit; | | |
| Rd_normalize( rdec ); | | Rd_normalize( rdec ); |
| rdec->range >>= 1; | | rdec->range >>= 1; |
| /* symbol <<= 1; */ | | /* symbol <<= 1; */ |
| /* if( rdec->code >= rdec->range ) { rdec->code -= rdec->range; symbol |= 1;
} */ | | /* if( rdec->code >= rdec->range ) { rdec->code -= rdec->range; symbol |= 1;
} */ |
|
| bit = ( rdec->code >= rdec->range ); | | const bool bit = ( rdec->code >= rdec->range ); |
| symbol <<= 1; symbol += bit; | | symbol <<= 1; symbol += bit; |
| rdec->code -= rdec->range & ( 0U - bit ); | | rdec->code -= rdec->range & ( 0U - bit ); |
| } | | } |
| return symbol; | | return symbol; |
| } | | } |
| | |
| static inline unsigned Rd_decode_bit( struct Range_decoder * const rdec, | | static inline unsigned Rd_decode_bit( struct Range_decoder * const rdec, |
| Bit_model * const probability ) | | Bit_model * const probability ) |
| { | | { |
|
| uint32_t bound; | | |
| Rd_normalize( rdec ); | | 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 ) | | if( rdec->code < bound ) |
| { | | { |
|
| *probability += (bit_model_total - *probability) >> bit_model_move_bits; | | |
| rdec->range = bound; | | rdec->range = bound; |
|
| | *probability += ( bit_model_total - *probability ) >> bit_model_move_bits; |
| return 0; | | return 0; |
| } | | } |
| else | | else |
| { | | { |
|
| *probability -= *probability >> bit_model_move_bits; | | |
| rdec->code -= bound; | | rdec->code -= bound; |
| rdec->range -= bound; | | rdec->range -= bound; |
|
| | *probability -= *probability >> bit_model_move_bits; |
| return 1; | | return 1; |
| } | | } |
| } | | } |
| | |
|
| static inline unsigned Rd_decode_tree3( struct Range_decoder * const rdec, | | static inline void Rd_decode_symbol_bit( struct Range_decoder * const rdec, |
| Bit_model bm[] ) | | Bit_model * const probability, unsigned * symbol ) |
| { | | { |
|
| unsigned symbol = 2 | Rd_decode_bit( rdec, &bm[1] ); | | Rd_normalize( rdec ); |
| symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); | | *symbol <<= 1; |
| symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); | | const uint32_t bound = ( rdec->range >> bit_model_total_bits ) * *probability; |
| return symbol & 7; | | 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 r |
| | dec, |
| | 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, | | static inline unsigned Rd_decode_tree6( struct Range_decoder * const rdec, |
| Bit_model bm[] ) | | Bit_model bm[] ) |
| { | | { |
|
| unsigned symbol = 2 | Rd_decode_bit( rdec, &bm[1] ); | | unsigned symbol = 1; |
| symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); | | Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); |
| symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); | | Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); |
| symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); | | Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); |
| symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] ); | | Rd_decode_symbol_bit( rdec, &bm[symbol], &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 ); |
| return symbol & 0x3F; | | return symbol & 0x3F; |
| } | | } |
| | |
| static inline unsigned Rd_decode_tree8( struct Range_decoder * const rdec, | | static inline unsigned Rd_decode_tree8( struct Range_decoder * const rdec, |
| Bit_model bm[] ) | | Bit_model bm[] ) |
| { | | { |
| unsigned symbol = 1; | | unsigned symbol = 1; |
|
| int i; | | Rd_decode_symbol_bit( rdec, &bm[symbol], &symbol ); |
| for( i = 0; i < 8; ++i ) | | Rd_decode_symbol_bit( rdec, &bm[symbol], &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 & 0xFF; | | return symbol & 0xFF; |
| } | | } |
| | |
| static inline unsigned | | static inline unsigned |
| Rd_decode_tree_reversed( struct Range_decoder * const rdec, | | Rd_decode_tree_reversed( struct Range_decoder * const rdec, |
| Bit_model bm[], const int num_bits ) | | Bit_model bm[], const int num_bits ) |
| { | | { |
| unsigned model = 1; | | unsigned model = 1; |
| unsigned symbol = 0; | | unsigned symbol = 0; |
| int i; | | int i; |
| for( i = 0; i < num_bits; ++i ) | | for( i = 0; i < num_bits; ++i ) |
|
| { | | Rd_decode_symbol_bit_reversed( rdec, &bm[model], &model, &symbol, i ); |
| const unsigned bit = Rd_decode_bit( rdec, &bm[model] ); | | |
| model <<= 1; model += bit; | | |
| symbol |= ( bit << i ); | | |
| } | | |
| return symbol; | | return symbol; |
| } | | } |
| | |
| static inline unsigned | | static inline unsigned |
| Rd_decode_tree_reversed4( struct Range_decoder * const rdec, Bit_model bm[] ) | | Rd_decode_tree_reversed4( struct Range_decoder * const rdec, Bit_model bm[] ) |
| { | | { |
|
| unsigned symbol = Rd_decode_bit( rdec, &bm[1] ); | | unsigned model = 1; |
| symbol += Rd_decode_bit( rdec, &bm[2+symbol] ) << 1; | | unsigned symbol = 0; |
| symbol += Rd_decode_bit( rdec, &bm[4+symbol] ) << 2; | | Rd_decode_symbol_bit_reversed( rdec, &bm[model], &model, &symbol, 0 ); |
| symbol += Rd_decode_bit( rdec, &bm[8+symbol] ) << 3; | | 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; | | return symbol; |
| } | | } |
| | |
| static inline unsigned Rd_decode_matched( struct Range_decoder * const rdec, | | static inline unsigned Rd_decode_matched( struct Range_decoder * const rdec, |
| Bit_model bm[], unsigned match_byte ) | | Bit_model bm[], unsigned match_byte ) |
| { | | { |
| unsigned symbol = 1; | | unsigned symbol = 1; |
| unsigned mask = 0x100; | | unsigned mask = 0x100; |
| while( true ) | | while( true ) |
| { | | { |
| | |
| skipping to change at line 271 | | skipping to change at line 305 |
|---|
| symbol <<= 1; symbol += bit; | | symbol <<= 1; symbol += bit; |
| if( symbol > 0xFF ) return symbol & 0xFF; | | if( symbol > 0xFF ) return symbol & 0xFF; |
| mask &= ~(match_bit ^ (bit << 8)); /* if( match_bit != bit ) mask = 0; */ | | mask &= ~(match_bit ^ (bit << 8)); /* if( match_bit != bit ) mask = 0; */ |
| } | | } |
| } | | } |
| | |
| static inline unsigned Rd_decode_len( struct Range_decoder * const rdec, | | static inline unsigned Rd_decode_len( struct Range_decoder * const rdec, |
| struct Len_model * const lm, | | struct Len_model * const lm, |
| const int pos_state ) | | const int pos_state ) |
| { | | { |
|
| | Bit_model * bm; |
| | unsigned mask, offset, symbol = 1; |
| | |
| if( Rd_decode_bit( rdec, &lm->choice1 ) == 0 ) | | 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 ) | | if( Rd_decode_bit( rdec, &lm->choice2 ) == 0 ) |
|
| return len_low_symbols + Rd_decode_tree3( rdec, lm->bm_mid[pos_state] ); | | { bm = lm->bm_mid[pos_state]; mask = 7; offset = len_low_symbols; goto len3; |
| return len_low_symbols + len_mid_symbols + Rd_decode_tree8( rdec, lm->bm_high | | } |
| ); | | 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; |
| } | | } |
| | |
| enum { lzd_min_free_bytes = max_match_len }; | | enum { lzd_min_free_bytes = max_match_len }; |
| | |
| struct LZ_decoder | | struct LZ_decoder |
| { | | { |
| struct Circular_buffer cb; | | struct Circular_buffer cb; |
| unsigned long long partial_data_pos; | | unsigned long long partial_data_pos; |
| struct Range_decoder * rdec; | | struct Range_decoder * rdec; |
| unsigned dictionary_size; | | unsigned dictionary_size; |
| | | |
| End of changes. 20 change blocks. |
|---|
| 39 lines changed or deleted | | 88 lines changed or added |
|---|
"Fossies" - the Fresh Open Source Software Archive 