lzma.diff

Linux 下使用Lzma 替代gzip压缩

Index: LzmaDecode.c
===================================================================
--- LzmaDecode.c	(revision 8777)
+++ LzmaDecode.c	(working copy)
@@ -1,8 +1,8 @@
 /*
-  LzmaDecode.c
-  LZMA Decoder (optimized for Speed version)
+  LzmaDecodeSize.c
+  LZMA Decoder (optimized for Size version)
   
-  LZMA SDK 4.22 Copyright (c) 1999-2005 Igor Pavlov (2005-06-10)
+  LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01)
   http://www.7-zip.org/
 
   LZMA SDK is licensed under two licenses:
@@ -12,19 +12,15 @@
   follow rules of that license.
 
   SPECIAL EXCEPTION:
-  Igor Pavlov, as the author of this Code, expressly permits you to 
-  statically or dynamically link your Code (or bind by name) to the 
-  interfaces of this file without subjecting your linked Code to the 
+  Igor Pavlov, as the author of this code, expressly permits you to 
+  statically or dynamically link your code (or bind by name) to the 
+  interfaces of this file without subjecting your linked code to the 
   terms of the CPL or GNU LGPL. Any modifications or additions 
   to this file, however, are subject to the LGPL or CPL terms.
 */
 
 #include "LzmaDecode.h"
 
-#ifndef Byte
-#define Byte unsigned char
-#endif
-
 #define kNumTopBits 24
 #define kTopValue ((UInt32)1 << kNumTopBits)
 
@@ -32,45 +28,240 @@
 #define kBitModelTotal (1 << kNumBitModelTotalBits)
 #define kNumMoveBits 5
 
-#define RC_READ_BYTE (*Buffer++)
+typedef struct _CRangeDecoder
+{
+  const Byte *Buffer;
+  const Byte *BufferLim;
+  UInt32 Range;
+  UInt32 Code;
+  #ifdef _LZMA_IN_CB
+  ILzmaInCallback *InCallback;
+  int Result;
+  #endif
+  int ExtraBytes;
+} CRangeDecoder;
 
-#define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
-  { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}
+Byte RangeDecoderReadByte(CRangeDecoder *rd)
+{
+  if (rd->Buffer == rd->BufferLim)
+  {
+    #ifdef _LZMA_IN_CB
+    SizeT size;
+    rd->Result = rd->InCallback->Read(rd->InCallback, &rd->Buffer, &size);
+    rd->BufferLim = rd->Buffer + size;
+    if (size == 0)
+    #endif
+    {
+      rd->ExtraBytes = 1;
+      return 0xFF;
+    }
+  }
+  return (*rd->Buffer++);
+}
 
-#ifdef _LZMA_IN_CB
+/* #define ReadByte (*rd->Buffer++) */
+#define ReadByte (RangeDecoderReadByte(rd))
 
-#define RC_TEST { if (Buffer == BufferLim) \
-  { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \
-  BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }}
+void RangeDecoderInit(CRangeDecoder *rd
+  #ifndef _LZMA_IN_CB
+    , const Byte *stream, SizeT bufferSize
+  #endif
+    )
+{
+  int i;
+  #ifdef _LZMA_IN_CB
+  rd->Buffer = rd->BufferLim = 0;
+  #else
+  rd->Buffer = stream;
+  rd->BufferLim = stream + bufferSize;
+  #endif
+  rd->ExtraBytes = 0;
+  rd->Code = 0;
+  rd->Range = (0xFFFFFFFF);
+  for(i = 0; i < 5; i++)
+    rd->Code = (rd->Code << 8) | ReadByte;
+}
 
-#define RC_INIT Buffer = BufferLim = 0; RC_INIT2
+#define RC_INIT_VAR UInt32 range = rd->Range; UInt32 code = rd->Code;        
+#define RC_FLUSH_VAR rd->Range = range; rd->Code = code;
+#define RC_NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | ReadByte; }
 
-#else
+UInt32 RangeDecoderDecodeDirectBits(CRangeDecoder *rd, int numTotalBits)
+{
+  RC_INIT_VAR
+  UInt32 result = 0;
+  int i;
+  for (i = numTotalBits; i != 0; i--)
+  {
+    /* UInt32 t; */
+    range >>= 1;
 
-#define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
+    result <<= 1;
+    if (code >= range)
+    {
+      code -= range;
+      result |= 1;
+    }
+    /*
+    t = (code - range) >> 31;
+    t &= 1;
+    code -= range & (t - 1);
+    result = (result + result) | (1 - t);
+    */
+    RC_NORMALIZE
+  }
+  RC_FLUSH_VAR
+  return result;
+}
 
-#define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
- 
-#endif
+int RangeDecoderBitDecode(CProb *prob, CRangeDecoder *rd)
+{
+  UInt32 bound = (rd->Range >> kNumBitModelTotalBits) * *prob;
+  if (rd->Code < bound)
+  {
+    rd->Range = bound;
+    *prob += (kBitModelTotal - *prob) >> kNumMoveBits;
+    if (rd->Range < kTopValue)
+    {
+      rd->Code = (rd->Code << 8) | ReadByte;
+      rd->Range <<= 8;
+    }
+    return 0;
+  }
+  else
+  {
+    rd->Range -= bound;
+    rd->Code -= bound;
+    *prob -= (*prob) >> kNumMoveBits;
+    if (rd->Range < kTopValue)
+    {
+      rd->Code = (rd->Code << 8) | ReadByte;
+      rd->Range <<= 8;
+    }
+    return 1;
+  }
+}
 
-#define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
+#define RC_GET_BIT2(prob, mi, A0, A1) \
+  UInt32 bound = (range >> kNumBitModelTotalBits) * *prob; \
+  if (code < bound) \
+    { A0; range = bound; *prob += (kBitModelTotal - *prob) >> kNumMoveBits; mi <<= 1; } \
+  else \
+    { A1; range -= bound; code -= bound; *prob -= (*prob) >> kNumMoveBits; mi = (mi + mi) + 1; } \
+  RC_NORMALIZE
 
-#define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
-#define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
-#define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
+#define RC_GET_BIT(prob, mi) RC_GET_BIT2(prob, mi, ; , ;)               
 
-#define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
-  { UpdateBit0(p); mi <<= 1; A0; } else \
-  { UpdateBit1(p); mi = (mi + mi) + 1; A1; } 
-  
-#define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)               
+int RangeDecoderBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd)
+{
+  int mi = 1;
+  int i;
+  #ifdef _LZMA_LOC_OPT
+  RC_INIT_VAR
+  #endif
+  for(i = numLevels; i != 0; i--)
+  {
+    #ifdef _LZMA_LOC_OPT
+    CProb *prob = probs + mi;
+    RC_GET_BIT(prob, mi)
+    #else
+    mi = (mi + mi) + RangeDecoderBitDecode(probs + mi, rd);
+    #endif
+  }
+  #ifdef _LZMA_LOC_OPT
+  RC_FLUSH_VAR
+  #endif
+  return mi - (1 << numLevels);
+}
 
-#define RangeDecoderBitTreeDecode(probs, numLevels, res) \
-  { int i = numLevels; res = 1; \
-  do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \
-  res -= (1 << numLevels); }
+int RangeDecoderReverseBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd)
+{
+  int mi = 1;
+  int i;
+  int symbol = 0;
+  #ifdef _LZMA_LOC_OPT
+  RC_INIT_VAR
+  #endif
+  for(i = 0; i < numLevels; i++)
+  {
+    #ifdef _LZMA_LOC_OPT
+    CProb *prob = probs + mi;
+    RC_GET_BIT2(prob, mi, ; , symbol |= (1 << i))
+    #else
+    int bit = RangeDecoderBitDecode(probs + mi, rd);
+    mi = mi + mi + bit;
+    symbol |= (bit << i);
+    #endif
+  }
+  #ifdef _LZMA_LOC_OPT
+  RC_FLUSH_VAR
+  #endif
+  return symbol;
+}
 
+Byte LzmaLiteralDecode(CProb *probs, CRangeDecoder *rd)
+{ 
+  int symbol = 1;
+  #ifdef _LZMA_LOC_OPT
+  RC_INIT_VAR
+  #endif
+  do
+  {
+    #ifdef _LZMA_LOC_OPT
+    CProb *prob = probs + symbol;
+    RC_GET_BIT(prob, symbol)
+    #else
+    symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd);
+    #endif
+  }
+  while (symbol < 0x100);
+  #ifdef _LZMA_LOC_OPT
+  RC_FLUSH_VAR
+  #endif
+  return symbol;
+}
 
+Byte LzmaLiteralDecodeMatch(CProb *probs, CRangeDecoder *rd, Byte matchByte)
+{ 
+  int symbol = 1;
+  #ifdef _LZMA_LOC_OPT
+  RC_INIT_VAR
+  #endif
+  do
+  {
+    int bit;
+    int matchBit = (matchByte >> 7) & 1;
+    matchByte <<= 1;
+    #ifdef _LZMA_LOC_OPT
+    {
+      CProb *prob = probs + 0x100 + (matchBit << 8) + symbol;
+      RC_GET_BIT2(prob, symbol, bit = 0, bit = 1)
+    }
+    #else
+    bit = RangeDecoderBitDecode(probs + 0x100 + (matchBit << 8) + symbol, rd);
+    symbol = (symbol << 1) | bit;
+    #endif
+    if (matchBit != bit)
+    {
+      while (symbol < 0x100)
+      {
+        #ifdef _LZMA_LOC_OPT
+        CProb *prob = probs + symbol;
+        RC_GET_BIT(prob, symbol)
+        #else
+        symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd);
+        #endif
+      }
+      break;
+    }
+  }
+  while (symbol < 0x100);
+  #ifdef _LZMA_LOC_OPT
+  RC_FLUSH_VAR
+  #endif
+  return symbol;
+}
+
 #define kNumPosBitsMax 4
 #define kNumPosStatesMax (1 << kNumPosBitsMax)
 
@@ -88,6 +279,17 @@
 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
 #define kNumLenProbs (LenHigh + kLenNumHighSymbols) 
 
+int LzmaLenDecode(CProb *p, CRangeDecoder *rd, int posState)
+{
+  if(RangeDecoderBitDecode(p + LenChoice, rd) == 0)
+    return RangeDecoderBitTreeDecode(p + LenLow +
+        (posState << kLenNumLowBits), kLenNumLowBits, rd);
+  if(RangeDecoderBitDecode(p + LenChoice2, rd) == 0)
+    return kLenNumLowSymbols + RangeDecoderBitTreeDecode(p + LenMid +
+        (posState << kLenNumMidBits), kLenNumMidBits, rd);
+  return kLenNumLowSymbols + kLenNumMidSymbols + 
+      RangeDecoderBitTreeDecode(p + LenHigh, kLenNumHighBits, rd);
+}
 
 #define kNumStates 12
 #define kNumLitStates 7
@@ -121,7 +323,6 @@
 StopCompilingDueBUG
 #endif
 
-#if 0
 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
 {
   unsigned char prop0;
@@ -154,7 +355,6 @@
   #endif
   return LZMA_RESULT_OK;
 }
-#endif
 
 #define kLzmaStreamWasFinishedId (-1)
 
@@ -172,18 +372,10 @@
   UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
   UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
   int lc = vs->Properties.lc;
+  CRangeDecoder rd;
 
   #ifdef _LZMA_OUT_READ
   
-  UInt32 Range = vs->Range;
-  UInt32 Code = vs->Code;
-  #ifdef _LZMA_IN_CB
-  const Byte *Buffer = vs->Buffer;
-  const Byte *BufferLim = vs->BufferLim;
-  #else
-  const Byte *Buffer = inStream;
-  const Byte *BufferLim = inStream + inSize;
-  #endif
   int state = vs->State;
   UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
   int len = vs->RemainLen;
@@ -196,6 +388,17 @@
 
   Byte tempDictionary[4];
 
+  rd.Range = vs->Range;
+  rd.Code = vs->Code;
+  #ifdef _LZMA_IN_CB
+  rd.InCallback = InCallback;
+  rd.Buffer = vs->Buffer;
+  rd.BufferLim = vs->BufferLim;
+  #else
+  rd.Buffer = inStream;
+  rd.BufferLim = inStream + inSize;
+  #endif
+
   #ifndef _LZMA_IN_CB
   *inSizeProcessed = 0;
   #endif
@@ -223,11 +426,17 @@
       distanceLimit = 0;
       dictionaryPos = 0;
       dictionary[dictionarySize - 1] = 0;
+      RangeDecoderInit(&rd
+          #ifndef _LZMA_IN_CB
+          , inStream, inSize
+          #endif
+          );
       #ifdef _LZMA_IN_CB
-      RC_INIT;
-      #else
-      RC_INIT(inStream, inSize);
+      if (rd.Result != LZMA_RESULT_OK)
+        return rd.Result;
       #endif
+      if (rd.ExtraBytes != 0)
+        return LZMA_RESULT_DATA_ERROR;