Adding upstream version 1.0~rc2.upstream/1.0_rc2

Signed-off-by: Daniel Baumann <mail@daniel-baumann.ch>

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; }