Adding upstream version 1.4.upstream/1.4

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

1 files changed, 74 insertions, 92 deletions

diff --git a/decoder.h b/decoder.h
index 6445d1b..c18ccbe 100644
--- a/decoder.h
+++ b/decoder.h
@@ -1,5 +1,5 @@
 /*  Clzip - Data compressor based on the LZMA algorithm
-    Copyright (C) 2010, 2011, 2012 Antonio Diaz Diaz.
+    Copyright (C) 2010, 2011, 2012, 2013 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
@@ -19,7 +19,7 @@ enum { rd_buffer_size = 16384 };
 
 struct Range_decoder
   {
-  long long partial_member_pos;
+  unsigned long long partial_member_pos;
   uint8_t * buffer;		/* input buffer */
   int pos;			/* current pos in buffer */
   int stream_pos;		/* when reached, a new block must be read */
@@ -51,7 +51,8 @@ static inline void Rd_free( struct Range_decoder * const rdec )
 static inline bool Rd_finished( struct Range_decoder * const rdec )
   { return rdec->pos >= rdec->stream_pos && !Rd_read_block( rdec ); }
 
-static inline long long Rd_member_position( const struct Range_decoder * const rdec )
+static inline unsigned long long
+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 )
@@ -59,7 +60,7 @@ static inline void Rd_reset_member_position( struct Range_decoder * const rdec )
 
 static inline uint8_t Rd_get_byte( struct Range_decoder * const rdec )
   {
-  if( Rd_finished( rdec ) ) return 0x55;	/* make code != 0 */
+  if( Rd_finished( rdec ) ) return 0xAA;	/* make code != 0 */
   return rdec->buffer[rdec->pos++];
   }
 
@@ -74,16 +75,16 @@ static inline int Rd_read_data( struct Range_decoder * const rdec,
     rdec->pos += rd;
     rest -= rd;
     }
-  return ( rest > 0 ) ? size - rest : size;
+  return size - rest;
   }
 
 static inline void Rd_load( struct Range_decoder * const rdec )
   {
   int i;
   rdec->code = 0;
-  rdec->range = 0xFFFFFFFFU;
   for( i = 0; i < 5; ++i )
     rdec->code = (rdec->code << 8) | Rd_get_byte( rdec );
+  rdec->range = 0xFFFFFFFFU;
   }
 
 static inline void Rd_normalize( struct Range_decoder * const rdec )
@@ -102,20 +103,15 @@ static inline int Rd_decode( struct Range_decoder * const rdec,
   int i;
   for( i = num_bits; i > 0; --i )
     {
-    symbol <<= 1;
-    if( rdec->range <= 0x00FFFFFFU )
-      {
-      rdec->range <<= 7;
-      rdec->code = (rdec->code << 8) | Rd_get_byte( rdec );
-      if( rdec->code >= rdec->range )
-        { rdec->code -= rdec->range; symbol |= 1; }
-      }
-    else
-      {
-      rdec->range >>= 1;
-      if( rdec->code >= rdec->range )
-        { rdec->code -= rdec->range; symbol |= 1; }
-      }
+    uint32_t mask;
+    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);
     }
   return symbol;
   }
@@ -151,6 +147,19 @@ static inline int Rd_decode_tree( struct Range_decoder * const rdec,
   return model - (1 << num_bits);
   }
 
+static inline int Rd_decode_tree6( struct Range_decoder * const rdec,
+                                   Bit_model bm[] )
+  {
+  int model = 1;
+  model = ( model << 1 ) | Rd_decode_bit( rdec, &bm[model] );
+  model = ( model << 1 ) | Rd_decode_bit( rdec, &bm[model] );
+  model = ( model << 1 ) | Rd_decode_bit( rdec, &bm[model] );
+  model = ( model << 1 ) | Rd_decode_bit( rdec, &bm[model] );
+  model = ( model << 1 ) | Rd_decode_bit( rdec, &bm[model] );
+  model = ( model << 1 ) | Rd_decode_bit( rdec, &bm[model] );
+  return model - (1 << 6);
+  }
+
 static inline int Rd_decode_tree_reversed( struct Range_decoder * const rdec,
                                            Bit_model bm[], const int num_bits )
   {
@@ -159,32 +168,49 @@ static inline int Rd_decode_tree_reversed( struct Range_decoder * const rdec,
   int i;
   for( i = 0; i < num_bits; ++i )
     {
-    const int bit = Rd_decode_bit( rdec, &bm[model] );
+    const bool bit = Rd_decode_bit( rdec, &bm[model] );
     model <<= 1;
-    if( bit ) { model |= 1; symbol |= (1 << i); }
+    if( bit ) { ++model; symbol |= (1 << i); }
     }
   return symbol;
   }
 
+static inline int Rd_decode_tree_reversed4( struct Range_decoder * const rdec,
+                                            Bit_model bm[] )
+  {
+  int model = 1;
+  int symbol = 0;
+  int bit = Rd_decode_bit( rdec, &bm[model] );
+  model = (model << 1) + bit; symbol |= bit;
+  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;
+  return symbol;
+  }
+
 static inline int Rd_decode_matched( struct Range_decoder * const rdec,
-                                     Bit_model bm[], const int match_byte )
+                                     Bit_model bm[], int match_byte )
   {
   Bit_model * const bm1 = bm + 0x100;
   int symbol = 1;
   int i;
   for( i = 7; i >= 0; --i )
     {
-    const int match_bit = ( match_byte >> i ) & 1;
-    const int bit = Rd_decode_bit( rdec, &bm1[(match_bit<<8)+symbol] );
+    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 )
+    if( match_bit != bit << 8 )
       {
-      while( --i >= 0 )
+      while( symbol < 0x100 )
         symbol = ( symbol << 1 ) | Rd_decode_bit( rdec, &bm[symbol] );
       break;
       }
     }
-  return symbol & 0xFF;
+  return symbol - 0x100;
   }
 
 
@@ -199,17 +225,11 @@ struct Len_decoder
 
 static inline void Led_init( struct Len_decoder * const len_decoder )
   {
-  int i, j;
   Bm_init( &len_decoder->choice1 );
   Bm_init( &len_decoder->choice2 );
-  for( i = 0; i < pos_states; ++i )
-    for( j = 0; j < len_low_symbols; ++j )
-      Bm_init( &len_decoder->bm_low[i][j] );
-  for( i = 0; i < pos_states; ++i )
-    for( j = 0; j < len_mid_symbols; ++j )
-      Bm_init( &len_decoder->bm_mid[i][j] );
-  for( i = 0; i < len_high_symbols; ++i )
-    Bm_init( &len_decoder->bm_high[i] );
+  Bm_array_init( len_decoder->bm_low[0], pos_states * len_low_symbols );
+  Bm_array_init( len_decoder->bm_mid[0], pos_states * len_mid_symbols );
+  Bm_array_init( len_decoder->bm_high, len_high_symbols );
   }
 
 static inline int Led_decode( struct Len_decoder * const len_decoder,
@@ -226,37 +246,9 @@ static inline int Led_decode( struct Len_decoder * const len_decoder,
   }
 
 
-struct Literal_decoder
-  {
-  Bit_model bm_literal[1<<literal_context_bits][0x300];
-  };
-
-static inline void Lid_init( struct Literal_decoder * const lidec )
-  {
-  int i, j;
-  for( i = 0; i < 1<<literal_context_bits; ++i )
-    for( j = 0; j < 0x300; ++j )
-      Bm_init( &lidec->bm_literal[i][j] );
-  }
-
-static inline int Lid_state( const uint8_t prev_byte )
-  { return ( prev_byte >> ( 8 - literal_context_bits ) ); }
-
-static inline uint8_t Lid_decode( struct Literal_decoder * const lidec,
-                                  struct Range_decoder * const rdec,
-                                  const uint8_t prev_byte )
-  { return Rd_decode_tree( rdec, lidec->bm_literal[Lid_state(prev_byte)], 8 ); }
-
-static inline uint8_t Lid_decode_matched( struct Literal_decoder * const lidec,
-                                          struct Range_decoder * const rdec,
-                                          const uint8_t prev_byte,
-                                          const uint8_t match_byte )
-  { return Rd_decode_matched( rdec, lidec->bm_literal[Lid_state(prev_byte)], match_byte ); }
-
-
 struct LZ_decoder
   {
-  long long partial_data_pos;
+  unsigned long long partial_data_pos;
   int dictionary_size;
   int buffer_size;
   uint8_t * buffer;		/* output buffer */
@@ -266,6 +258,7 @@ struct LZ_decoder
   int outfd;			/* output file descriptor */
   int member_version;
 
+  Bit_model bm_literal[1<<literal_context_bits][0x300];
   Bit_model bm_match[states][pos_states];
   Bit_model bm_rep[states];
   Bit_model bm_rep0[states];
@@ -273,13 +266,12 @@ struct LZ_decoder
   Bit_model bm_rep2[states];
   Bit_model bm_len[states][pos_states];
   Bit_model bm_dis_slot[max_dis_states][1<<dis_slot_bits];
-  Bit_model bm_dis[modeled_distances-end_dis_model+1];
+  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 );
@@ -315,7 +307,7 @@ static inline void LZd_copy_block( struct LZ_decoder * const decoder,
   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 ) )
+      len <= abs( decoder->pos - i ) )		/* no wrap, no overlap */
     {
     memcpy( decoder->buffer + decoder->pos, decoder->buffer + i, len );
     decoder->pos += len;
@@ -332,7 +324,6 @@ static inline bool LZd_init( struct LZ_decoder * const decoder,
                              const File_header header,
                              struct Range_decoder * const rdec, const int ofd )
   {
-  int i, j;
   decoder->partial_data_pos = 0;
   decoder->dictionary_size = Fh_get_dictionary_size( header );
   decoder->buffer_size = max( 65536, decoder->dictionary_size );
@@ -344,30 +335,20 @@ static inline bool LZd_init( struct LZ_decoder * const decoder,
   decoder->outfd = ofd;
   decoder->member_version = Fh_version( header );
 
-  for( i = 0; i < states; ++i )
-    {
-    for( 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( i = 0; i < max_dis_states; ++i )
-    for( j = 0; j < 1<<dis_slot_bits; ++j )
-      Bm_init( &decoder->bm_dis_slot[i][j] );
-  for( i = 0; i < modeled_distances-end_dis_model+1; ++i )
-    Bm_init( &decoder->bm_dis[i] );
-  for( i = 0; i < dis_align_size; ++i )
-    Bm_init( &decoder->bm_align[i] );
+  Bm_array_init( decoder->bm_literal[0], (1 << literal_context_bits) * 0x300 );
+  Bm_array_init( decoder->bm_match[0], states * pos_states );
+  Bm_array_init( decoder->bm_rep, states );
+  Bm_array_init( decoder->bm_rep0, states );
+  Bm_array_init( decoder->bm_rep1, states );
+  Bm_array_init( decoder->bm_rep2, states );
+  Bm_array_init( decoder->bm_len[0], states * pos_states );
+  Bm_array_init( decoder->bm_dis_slot[0], max_dis_states * (1 << dis_slot_bits) );
+  Bm_array_init( decoder->bm_dis, modeled_distances - end_dis_model );
+  Bm_array_init( decoder->bm_align, dis_align_size );
 
   decoder->range_decoder = rdec;
   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 */
   return true;
   }
@@ -375,10 +356,11 @@ static inline bool LZd_init( struct LZ_decoder * const decoder,
 static inline void LZd_free( struct LZ_decoder * const decoder )
   { free( decoder->buffer ); }
 
-static inline uint32_t LZd_crc( const struct LZ_decoder * const decoder )
+static inline unsigned LZd_crc( const struct LZ_decoder * const decoder )
   { return decoder->crc ^ 0xFFFFFFFFU; }
 
-static inline long long LZd_data_position( const struct LZ_decoder * const decoder )
+static inline unsigned long long
+LZd_data_position( const struct LZ_decoder * const decoder )
   { return decoder->partial_data_pos + decoder->pos; }
 
 int LZd_decode_member( struct LZ_decoder * const decoder,