"Fossies" - the Fresh Open Source Software Archive

Member "p7zip_16.02/CPP/7zip/Compress/LzmsDecoder.cpp" (20 May 2016, 13029 Bytes) of package /linux/misc/p7zip_16.02_src_all.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. See also the last Fossies "Diffs" side-by-side code changes report for "LzmsDecoder.cpp": 15.14.1_src_all_vs_16.02_src_all.

    1 // LzmsDecoder.cpp
    2 // The code is based on LZMS description from wimlib code
    3 
    4 #include "StdAfx.h"
    5 
    6 #include "../../../C/Alloc.h"
    7 
    8 #include "LzmsDecoder.h"
    9 
   10 namespace NCompress {
   11 namespace NLzms {
   12 
   13 static UInt32 g_PosBases[k_NumPosSyms /* + 1 */];
   14 
   15 static Byte g_PosDirectBits[k_NumPosSyms];
   16 
   17 static const Byte k_PosRuns[31] =
   18 {
   19   8, 0, 9, 7, 10, 15, 15, 20, 20, 30, 33, 40, 42, 45, 60, 73,
   20   80, 85, 95, 105, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
   21 };
   22 
   23 static UInt32 g_LenBases[k_NumLenSyms];
   24 
   25 static const Byte k_LenDirectBits[k_NumLenSyms] =
   26 {
   27   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
   28   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2,
   29   2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 6,
   30   7, 8, 9, 10, 16, 30,
   31 };
   32 
   33 static struct CInit
   34 {
   35   CInit()
   36   {
   37     {
   38       unsigned sum = 0;
   39       for (unsigned i = 0; i < sizeof(k_PosRuns); i++)
   40       {
   41         unsigned t = k_PosRuns[i];
   42         for (unsigned y = 0; y < t; y++)
   43           g_PosDirectBits[sum + y] = (Byte)i;
   44         sum += t;
   45       }
   46     }
   47     {
   48       UInt32 sum = 1;
   49       for (unsigned i = 0; i < k_NumPosSyms; i++)
   50       {
   51         g_PosBases[i] = sum;
   52         sum += (UInt32)1 << g_PosDirectBits[i];
   53       }
   54       // g_PosBases[k_NumPosSyms] = sum;
   55     }
   56     {
   57       UInt32 sum = 1;
   58       for (unsigned i = 0; i < k_NumLenSyms; i++)
   59       {
   60         g_LenBases[i] = sum;
   61         sum += (UInt32)1 << k_LenDirectBits[i];
   62       }
   63     }
   64   }
   65 } g_Init;
   66 
   67 static unsigned GetNumPosSlots(size_t size)
   68 {
   69   if (size < 2)
   70     return 0;
   71   
   72   size--;
   73 
   74   if (size >= g_PosBases[k_NumPosSyms - 1])
   75     return k_NumPosSyms;
   76   unsigned left = 0;
   77   unsigned right = k_NumPosSyms;
   78   for (;;)
   79   {
   80     unsigned m = (left + right) / 2;
   81     if (left == m)
   82       return m + 1;
   83     if (size >= g_PosBases[m])
   84       left = m;
   85     else
   86       right = m;
   87   }
   88 }
   89 
   90 
   91 static const Int32 k_x86_WindowSize = 65535;
   92 static const Int32 k_x86_TransOffset = 1023;
   93 
   94 static const size_t k_x86_HistorySize = (1 << 16);
   95 
   96 static void x86_Filter(Byte *data, UInt32 size, Int32 *history)
   97 {
   98   if (size <= 17)
   99     return;
  100 
  101   Byte isCode[256];
  102   memset(isCode, 0, 256);
  103   isCode[0x48] = 1;
  104   isCode[0x4C] = 1;
  105   isCode[0xE8] = 1;
  106   isCode[0xE9] = 1;
  107   isCode[0xF0] = 1;
  108   isCode[0xFF] = 1;
  109 
  110   {
  111     for (size_t i = 0; i < k_x86_HistorySize; i++)
  112       history[i] = -(Int32)k_x86_WindowSize - 1;
  113   }
  114 
  115   size -= 16;
  116   const unsigned kSave = 6;
  117   const Byte savedByte = data[size + kSave];
  118   data[size + kSave] = 0xE8;
  119   Int32 last_x86_pos = -k_x86_TransOffset - 1;
  120 
  121   // first byte is ignored
  122   Int32 i = 0;
  123   
  124   for (;;)
  125   {
  126     const Byte *p = data + (UInt32)i;
  127 
  128     for (;;)
  129     {
  130       if (isCode[*(++p)]) break;
  131       if (isCode[*(++p)]) break;
  132     }
  133     
  134     i = (Int32)(p - data);
  135     if ((UInt32)i >= size)
  136       break;
  137 
  138     UInt32 codeLen;
  139 
  140     Int32 maxTransOffset = k_x86_TransOffset;
  141     
  142     Byte b = p[0];
  143     
  144     if (b == 0x48)
  145     {
  146       if (p[1] == 0x8B)
  147       {
  148         if ((p[2] & 0xF7) != 0x5)
  149           continue;
  150         // MOV RAX / RCX, [RIP + disp32]
  151       }
  152       else if (p[1] == 0x8D) // LEA
  153       {
  154         if ((p[2] & 0x7) != 0x5)
  155           continue;
  156         // LEA R**, []
  157       }
  158       else
  159         continue;
  160       codeLen = 3;
  161     }
  162     else if (b == 0x4C)
  163     {
  164       if (p[1] != 0x8D || (p[2] & 0x7) != 0x5)
  165         continue;
  166       // LEA R*, []
  167       codeLen = 3;
  168     }
  169     else if (b == 0xE8)
  170     {
  171       // CALL
  172       codeLen = 1;
  173       maxTransOffset /= 2;
  174     }
  175     else if (b == 0xE9)
  176     {
  177       // JUMP
  178       i += 4;
  179       continue;
  180     }
  181     else if (b == 0xF0)
  182     {
  183       if (p[1] != 0x83 || p[2] != 0x05)
  184         continue;
  185       // LOCK ADD [RIP + disp32], imm8
  186       // LOCK ADD [disp32], imm8
  187       codeLen = 3;
  188     }
  189     else
  190     // if (b == 0xFF)
  191     {
  192       if (p[1] != 0x15)
  193         continue;
  194       // CALL [RIP + disp32];
  195       // CALL [disp32];
  196       codeLen = 2;
  197     }
  198 
  199     Int32 *target;
  200     {
  201       const Byte *p2 = p + codeLen;
  202       UInt32 n = GetUi32(p2);
  203       if (i - last_x86_pos <= maxTransOffset)
  204       {
  205         n -= i;
  206         SetUi32(p2, n);
  207       }
  208       target = history + (((UInt32)i + n) & 0xFFFF);
  209     }
  210 
  211     i += codeLen + sizeof(UInt32) - 1;
  212 
  213     if (i - *target <= k_x86_WindowSize)
  214       last_x86_pos = i;
  215     *target = i;
  216   }
  217 
  218   data[size + kSave] = savedByte;
  219 }
  220 
  221 
  222 
  223 static const int kLenIdNeedInit = -2;
  224 
  225 CDecoder::CDecoder():
  226   _x86_history(NULL)
  227 {
  228 }
  229 
  230 CDecoder::~CDecoder()
  231 {
  232   ::MidFree(_x86_history);
  233 }
  234 
  235 #define RIF(x) { if (!(x)) return false; }
  236 
  237 #define LIMIT_CHECK if (_bs._buf < _rc.cur) return S_FALSE;
  238 // #define LIMIT_CHECK
  239 
  240 #define READ_BITS_CHECK(numDirectBits) \
  241   if (_bs._buf < _rc.cur) return S_FALSE; \
  242   if ((size_t)(_bs._buf - _rc.cur) < (numDirectBits >> 3)) return S_FALSE;
  243 
  244 
  245 #define HUFF_DEC(sym, pp) \
  246     sym = pp.DecodeFull(&_bs); \
  247     pp.Freqs[sym]++; \
  248     if (--pp.RebuildRem == 0) pp.Rebuild();
  249 
  250 
  251 HRESULT CDecoder::CodeReal(const Byte *in, size_t inSize, Byte *_win, size_t outSize)
  252 {
  253   // size_t inSizeT = (size_t)(inSize);
  254   // Byte *_win;
  255   // size_t _pos;
  256   _pos = 0;
  257 
  258   CBitDecoder _bs;
  259   CRangeDecoder _rc;
  260  
  261   if (inSize < 8 || (inSize & 1) != 0)
  262     return S_FALSE;
  263   _rc.Init(in, inSize);
  264   if (_rc.code >= _rc.range)
  265     return S_FALSE;
  266   _bs.Init(in, inSize);
  267 
  268   {
  269     {
  270       {
  271         for (unsigned i = 0 ; i < k_NumReps + 1; i++)
  272           _reps[i] = i + 1;
  273       }
  274 
  275       {
  276         for (unsigned i = 0 ; i < k_NumReps + 1; i++)
  277           _deltaReps[i] = i + 1;
  278       }
  279 
  280       mainState = 0;
  281       matchState = 0;
  282 
  283       { for (size_t i = 0; i < k_NumMainProbs; i++) mainProbs[i].Init(); }
  284       { for (size_t i = 0; i < k_NumMatchProbs; i++) matchProbs[i].Init(); }
  285 
  286       {
  287         for (size_t k = 0; k < k_NumReps; k++)
  288         {
  289           lzRepStates[k] = 0;
  290           for (size_t i = 0; i < k_NumRepProbs; i++)
  291             lzRepProbs[k][i].Init();
  292         }
  293       }
  294       {
  295         for (size_t k = 0; k < k_NumReps; k++)
  296         {
  297           deltaRepStates[k] = 0;
  298           for (size_t i = 0; i < k_NumRepProbs; i++)
  299             deltaRepProbs[k][i].Init();
  300         }
  301       }
  302 
  303       m_LitDecoder.Init();
  304       m_LenDecoder.Init();
  305       m_PowerDecoder.Init();
  306       unsigned numPosSyms = GetNumPosSlots(outSize);
  307       if (numPosSyms < 2)
  308         numPosSyms = 2;
  309       m_PosDecoder.Init(numPosSyms);
  310       m_DeltaDecoder.Init(numPosSyms);
  311     }
  312   }
  313 
  314   {
  315     unsigned prevType = 0;
  316     
  317     while (_pos < outSize)
  318     {
  319       if (_rc.Decode(&mainState, k_NumMainProbs, mainProbs) == 0)
  320       {
  321         UInt32 number;
  322         HUFF_DEC(number, m_LitDecoder);
  323         LIMIT_CHECK
  324         _win[_pos++] = (Byte)number;
  325         prevType = 0;
  326       }
  327       else if (_rc.Decode(&matchState, k_NumMatchProbs, matchProbs) == 0)
  328       {
  329         UInt32 distance;
  330         
  331         if (_rc.Decode(&lzRepStates[0], k_NumRepProbs, lzRepProbs[0]) == 0)
  332         {
  333           UInt32 number;
  334           HUFF_DEC(number, m_PosDecoder);
  335           LIMIT_CHECK
  336 
  337           unsigned numDirectBits = g_PosDirectBits[number];
  338           distance = g_PosBases[number];
  339           READ_BITS_CHECK(numDirectBits);
  340           distance += _bs.ReadBits32(numDirectBits);
  341           // LIMIT_CHECK
  342           _reps[3] = _reps[2];
  343           _reps[2] = _reps[1];
  344           _reps[1] = _reps[0];
  345           _reps[0] = distance;
  346         }
  347         else
  348         {
  349           if (_rc.Decode(&lzRepStates[1], k_NumRepProbs, lzRepProbs[1]) == 0)
  350           {
  351             if (prevType != 1)
  352               distance = _reps[0];
  353             else
  354             {
  355               distance = _reps[1];
  356               _reps[1] = _reps[0];
  357               _reps[0] = distance;
  358             }
  359           }
  360           else if (_rc.Decode(&lzRepStates[2], k_NumRepProbs, lzRepProbs[2]) == 0)
  361           {
  362             if (prevType != 1)
  363             {
  364               distance = _reps[1];
  365               _reps[1] = _reps[0];
  366               _reps[0] = distance;
  367             }
  368             else
  369             {
  370               distance = _reps[2];
  371               _reps[2] = _reps[1];
  372               _reps[1] = _reps[0];
  373               _reps[0] = distance;
  374             }
  375           }
  376           else
  377           {
  378             if (prevType != 1)
  379             {
  380               distance = _reps[2];
  381               _reps[2] = _reps[1];
  382               _reps[1] = _reps[0];
  383               _reps[0] = distance;
  384             }
  385             else
  386             {
  387               distance = _reps[3];
  388               _reps[3] = _reps[2];
  389               _reps[2] = _reps[1];
  390               _reps[1] = _reps[0];
  391               _reps[0] = distance;
  392             }
  393           }
  394         }
  395 
  396         UInt32 lenSlot;
  397         HUFF_DEC(lenSlot, m_LenDecoder);
  398         LIMIT_CHECK
  399 
  400         UInt32 len = g_LenBases[lenSlot];
  401         {
  402           unsigned numDirectBits = k_LenDirectBits[lenSlot];
  403           READ_BITS_CHECK(numDirectBits);
  404           len += _bs.ReadBits32(numDirectBits);
  405         }
  406         // LIMIT_CHECK
  407 
  408         if (len > outSize - _pos)
  409           return S_FALSE;
  410 
  411         if (distance > _pos)
  412           return S_FALSE;
  413 
  414         Byte *dest = _win + _pos;
  415         const Byte *src = dest - distance;
  416         _pos += len;
  417         do
  418           *dest++ = *src++;
  419         while (--len);
  420 
  421         prevType = 1;
  422       }
  423       else
  424       {
  425         UInt64 distance;
  426 
  427         UInt32 power;
  428         UInt32 distance32;
  429         
  430         if (_rc.Decode(&deltaRepStates[0], k_NumRepProbs, deltaRepProbs[0]) == 0)
  431         {
  432           HUFF_DEC(power, m_PowerDecoder);
  433           LIMIT_CHECK
  434 
  435           UInt32 number;
  436           HUFF_DEC(number, m_DeltaDecoder);
  437           LIMIT_CHECK
  438 
  439           unsigned numDirectBits = g_PosDirectBits[number];
  440           distance32 = g_PosBases[number];
  441           READ_BITS_CHECK(numDirectBits);
  442           distance32 += _bs.ReadBits32(numDirectBits);
  443           // LIMIT_CHECK
  444 
  445           distance = ((UInt64)power << 32) | distance32;
  446 
  447           _deltaReps[3] = _deltaReps[2];
  448           _deltaReps[2] = _deltaReps[1];
  449           _deltaReps[1] = _deltaReps[0];
  450           _deltaReps[0] = distance;
  451         }
  452         else
  453         {
  454           if (_rc.Decode(&deltaRepStates[1], k_NumRepProbs, deltaRepProbs[1]) == 0)
  455           {
  456             if (prevType != 2)
  457               distance = _deltaReps[0];
  458             else
  459             {
  460               distance = _deltaReps[1];
  461               _deltaReps[1] = _deltaReps[0];
  462               _deltaReps[0] = distance;
  463             }
  464           }
  465           else if (_rc.Decode(&deltaRepStates[2], k_NumRepProbs, deltaRepProbs[2]) == 0)
  466           {
  467             if (prevType != 2)
  468             {
  469               distance = _deltaReps[1];
  470               _deltaReps[1] = _deltaReps[0];
  471               _deltaReps[0] = distance;
  472             }
  473             else
  474             {
  475               distance = _deltaReps[2];
  476               _deltaReps[2] = _deltaReps[1];
  477               _deltaReps[1] = _deltaReps[0];
  478               _deltaReps[0] = distance;
  479             }
  480           }
  481           else
  482           {
  483             if (prevType != 2)
  484             {
  485               distance = _deltaReps[2];
  486               _deltaReps[2] = _deltaReps[1];
  487               _deltaReps[1] = _deltaReps[0];
  488               _deltaReps[0] = distance;
  489             }
  490             else
  491             {
  492               distance = _deltaReps[3];
  493               _deltaReps[3] = _deltaReps[2];
  494               _deltaReps[2] = _deltaReps[1];
  495               _deltaReps[1] = _deltaReps[0];
  496               _deltaReps[0] = distance;
  497             }
  498           }
  499           distance32 = (UInt32)_deltaReps[0] & 0xFFFFFFFF;
  500           power = (UInt32)(_deltaReps[0] >> 32);
  501         }
  502 
  503         UInt32 dist = (distance32 << power);
  504         
  505         UInt32 lenSlot;
  506         HUFF_DEC(lenSlot, m_LenDecoder);
  507         LIMIT_CHECK
  508 
  509         UInt32 len = g_LenBases[lenSlot];
  510         {
  511           unsigned numDirectBits = k_LenDirectBits[lenSlot];
  512           READ_BITS_CHECK(numDirectBits);
  513           len += _bs.ReadBits32(numDirectBits);
  514         }
  515         // LIMIT_CHECK
  516 
  517         if (len > outSize - _pos)
  518           return S_FALSE;
  519 
  520         if (dist > _pos)
  521           return S_FALSE;
  522         size_t span = (size_t)1 << power;
  523         Byte *dest = _win + _pos - span;
  524         const Byte *src = dest - dist;
  525         _pos += len;
  526         do
  527         {
  528           *(dest + span) = (Byte)(*(dest) + *(src + span) - *(src));
  529           src++;
  530           dest++;
  531         }
  532         while (--len);
  533 
  534         prevType = 2;
  535       }
  536     }
  537   }
  538 
  539   _rc.Normalize();
  540   if (_rc.code != 0)
  541     return S_FALSE;
  542   if (_rc.cur > _bs._buf ||
  543       _rc.cur == _bs._buf && _bs._bitPos != 0)
  544     return S_FALSE;
  545 
  546   /*
  547   int delta = (int)(_bs._buf - _rc.cur);
  548   if (_bs._bitPos != 0)
  549     delta--;
  550   if ((delta & 1))
  551     delta--;
  552   printf("%d ", delta);
  553   */
  554 
  555   return S_OK;
  556 }
  557 
  558 HRESULT CDecoder::Code(const Byte *in, size_t inSize, Byte *out, size_t outSize)
  559 {
  560   if (!_x86_history)
  561   {
  562     _x86_history = (Int32 *)::MidAlloc(sizeof(Int32) * k_x86_HistorySize);
  563     if (!_x86_history)
  564       return E_OUTOFMEMORY;
  565   }
  566   HRESULT res;
  567   // try
  568   {
  569     res = CodeReal(in, inSize, out, outSize);
  570   }
  571   // catch (...) { res = S_FALSE; }
  572   x86_Filter(out, (UInt32)_pos, _x86_history);
  573   return res;
  574 }
  575 
  576 }}