[pcsx_rearmed.git] / deps / lzma-16.04 / C / LzmaEnc.c

/* LzmaEnc.c -- LZMA Encoder\r
2016-05-16 : Igor Pavlov : Public domain */\r
\r
#include "Precomp.h"\r
\r
#include <string.h>\r
\r
/* #define SHOW_STAT */\r
/* #define SHOW_STAT2 */\r
\r
#if defined(SHOW_STAT) || defined(SHOW_STAT2)\r
#include <stdio.h>\r
#endif\r
\r
#include "LzmaEnc.h"\r
\r
#include "LzFind.h"\r
#ifndef _7ZIP_ST\r
#include "LzFindMt.h"\r
#endif\r
\r
#ifdef SHOW_STAT\r
static unsigned g_STAT_OFFSET = 0;\r
#endif\r
\r
#define kMaxHistorySize ((UInt32)3 << 29)\r
/* #define kMaxHistorySize ((UInt32)7 << 29) */\r
\r
#define kBlockSizeMax ((1 << LZMA_NUM_BLOCK_SIZE_BITS) - 1)\r
\r
#define kBlockSize (9 << 10)\r
#define kUnpackBlockSize (1 << 18)\r
#define kMatchArraySize (1 << 21)\r
#define kMatchRecordMaxSize ((LZMA_MATCH_LEN_MAX * 2 + 3) * LZMA_MATCH_LEN_MAX)\r
\r
#define kNumMaxDirectBits (31)\r
\r
#define kNumTopBits 24\r
#define kTopValue ((UInt32)1 << kNumTopBits)\r
\r
#define kNumBitModelTotalBits 11\r
#define kBitModelTotal (1 << kNumBitModelTotalBits)\r
#define kNumMoveBits 5\r
#define kProbInitValue (kBitModelTotal >> 1)\r
\r
#define kNumMoveReducingBits 4\r
#define kNumBitPriceShiftBits 4\r
#define kBitPrice (1 << kNumBitPriceShiftBits)\r
\r
void LzmaEncProps_Init(CLzmaEncProps *p)\r
{\r
  p->level = 5;\r
  p->dictSize = p->mc = 0;\r
  p->reduceSize = (UInt64)(Int64)-1;\r
  p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->numThreads = -1;\r
  p->writeEndMark = 0;\r
}\r
\r
void LzmaEncProps_Normalize(CLzmaEncProps *p)\r
{\r
  int level = p->level;\r
  if (level < 0) level = 5;\r
  p->level = level;\r
  \r
  if (p->dictSize == 0) p->dictSize = (level <= 5 ? (1 << (level * 2 + 14)) : (level == 6 ? (1 << 25) : (1 << 26)));\r
  if (p->dictSize > p->reduceSize)\r
  {\r
    unsigned i;\r
    for (i = 11; i <= 30; i++)\r
    {\r
      if ((UInt32)p->reduceSize <= ((UInt32)2 << i)) { p->dictSize = ((UInt32)2 << i); break; }\r
      if ((UInt32)p->reduceSize <= ((UInt32)3 << i)) { p->dictSize = ((UInt32)3 << i); break; }\r
    }\r
  }\r
\r
  if (p->lc < 0) p->lc = 3;\r
  if (p->lp < 0) p->lp = 0;\r
  if (p->pb < 0) p->pb = 2;\r
\r
  if (p->algo < 0) p->algo = (level < 5 ? 0 : 1);\r
  if (p->fb < 0) p->fb = (level < 7 ? 32 : 64);\r
  if (p->btMode < 0) p->btMode = (p->algo == 0 ? 0 : 1);\r
  if (p->numHashBytes < 0) p->numHashBytes = 4;\r
  if (p->mc == 0) p->mc = (16 + (p->fb >> 1)) >> (p->btMode ? 0 : 1);\r
  \r
  if (p->numThreads < 0)\r
    p->numThreads =\r
      #ifndef _7ZIP_ST\r
      ((p->btMode && p->algo) ? 2 : 1);\r
      #else\r
      1;\r
      #endif\r
}\r
\r
UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2)\r
{\r
  CLzmaEncProps props = *props2;\r
  LzmaEncProps_Normalize(&props);\r
  return props.dictSize;\r
}\r
\r
#if (_MSC_VER >= 1400)\r
/* BSR code is fast for some new CPUs */\r
/* #define LZMA_LOG_BSR */\r
#endif\r
\r
#ifdef LZMA_LOG_BSR\r
\r
#define kDicLogSizeMaxCompress 32\r
\r
#define BSR2_RET(pos, res) { unsigned long zz; _BitScanReverse(&zz, (pos)); res = (zz + zz) + ((pos >> (zz - 1)) & 1); }\r
\r
static UInt32 GetPosSlot1(UInt32 pos)\r
{\r
  UInt32 res;\r
  BSR2_RET(pos, res);\r
  return res;\r
}\r
#define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }\r
#define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res); }\r
\r
#else\r
\r
#define kNumLogBits (9 + sizeof(size_t) / 2)\r
/* #define kNumLogBits (11 + sizeof(size_t) / 8 * 3) */\r
\r
#define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7)\r
\r
static void LzmaEnc_FastPosInit(Byte *g_FastPos)\r
{\r
  unsigned slot;\r
  g_FastPos[0] = 0;\r
  g_FastPos[1] = 1;\r
  g_FastPos += 2;\r
  \r
  for (slot = 2; slot < kNumLogBits * 2; slot++)\r
  {\r
    size_t k = ((size_t)1 << ((slot >> 1) - 1));\r
    size_t j;\r
    for (j = 0; j < k; j++)\r
      g_FastPos[j] = (Byte)slot;\r
    g_FastPos += k;\r
  }\r
}\r
\r
/* we can use ((limit - pos) >> 31) only if (pos < ((UInt32)1 << 31)) */\r
/*\r
#define BSR2_RET(pos, res) { UInt32 zz = 6 + ((kNumLogBits - 1) & \\r
  (0 - (((((UInt32)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \\r
  res = p->g_FastPos[pos >> zz] + (zz * 2); }\r
*/\r
\r
/*\r
#define BSR2_RET(pos, res) { UInt32 zz = 6 + ((kNumLogBits - 1) & \\r
  (0 - (((((UInt32)1 << (kNumLogBits)) - 1) - (pos >> 6)) >> 31))); \\r
  res = p->g_FastPos[pos >> zz] + (zz * 2); }\r
*/\r
\r
#define BSR2_RET(pos, res) { UInt32 zz = (pos < (1 << (kNumLogBits + 6))) ? 6 : 6 + kNumLogBits - 1; \\r
  res = p->g_FastPos[pos >> zz] + (zz * 2); }\r
\r
/*\r
#define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \\r
  p->g_FastPos[pos >> 6] + 12 : \\r
  p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; }\r
*/\r
\r
#define GetPosSlot1(pos) p->g_FastPos[pos]\r
#define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }\r
#define GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[pos]; else BSR2_RET(pos, res); }\r
\r
#endif\r
\r
\r
#define LZMA_NUM_REPS 4\r
\r
typedef unsigned CState;\r
\r
typedef struct\r
{\r
  UInt32 price;\r
\r
  CState state;\r
  int prev1IsChar;\r
  int prev2;\r
\r
  UInt32 posPrev2;\r
  UInt32 backPrev2;\r
\r
  UInt32 posPrev;\r
  UInt32 backPrev;\r
  UInt32 backs[LZMA_NUM_REPS];\r
} COptimal;\r
\r
#define kNumOpts (1 << 12)\r
\r
#define kNumLenToPosStates 4\r
#define kNumPosSlotBits 6\r
#define kDicLogSizeMin 0\r
#define kDicLogSizeMax 32\r
#define kDistTableSizeMax (kDicLogSizeMax * 2)\r
\r
\r
#define kNumAlignBits 4\r
#define kAlignTableSize (1 << kNumAlignBits)\r
#define kAlignMask (kAlignTableSize - 1)\r
\r
#define kStartPosModelIndex 4\r
#define kEndPosModelIndex 14\r
#define kNumPosModels (kEndPosModelIndex - kStartPosModelIndex)\r
\r
#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))\r
\r
#ifdef _LZMA_PROB32\r
#define CLzmaProb UInt32\r
#else\r
#define CLzmaProb UInt16\r
#endif\r
\r
#define LZMA_PB_MAX 4\r
#define LZMA_LC_MAX 8\r
#define LZMA_LP_MAX 4\r
\r
#define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX)\r
\r
\r
#define kLenNumLowBits 3\r
#define kLenNumLowSymbols (1 << kLenNumLowBits)\r
#define kLenNumMidBits 3\r
#define kLenNumMidSymbols (1 << kLenNumMidBits)\r
#define kLenNumHighBits 8\r
#define kLenNumHighSymbols (1 << kLenNumHighBits)\r
\r
#define kLenNumSymbolsTotal (kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)\r
\r
#define LZMA_MATCH_LEN_MIN 2\r
#define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1)\r
\r
#define kNumStates 12\r
\r
\r
typedef struct\r
{\r
  CLzmaProb choice;\r
  CLzmaProb choice2;\r
  CLzmaProb low[LZMA_NUM_PB_STATES_MAX << kLenNumLowBits];\r
  CLzmaProb mid[LZMA_NUM_PB_STATES_MAX << kLenNumMidBits];\r
  CLzmaProb high[kLenNumHighSymbols];\r
} CLenEnc;\r
\r
\r
typedef struct\r
{\r
  CLenEnc p;\r
  UInt32 tableSize;\r
  UInt32 prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal];\r
  UInt32 counters[LZMA_NUM_PB_STATES_MAX];\r
} CLenPriceEnc;\r
\r
\r
typedef struct\r
{\r
  UInt32 range;\r
  Byte cache;\r
  UInt64 low;\r
  UInt64 cacheSize;\r
  Byte *buf;\r
  Byte *bufLim;\r
  Byte *bufBase;\r
  ISeqOutStream *outStream;\r
  UInt64 processed;\r
  SRes res;\r
} CRangeEnc;\r
\r
\r
typedef struct\r
{\r
  CLzmaProb *litProbs;\r
\r
  UInt32 state;\r
  UInt32 reps[LZMA_NUM_REPS];\r
\r
  CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];\r
  CLzmaProb isRep[kNumStates];\r
  CLzmaProb isRepG0[kNumStates];\r
  CLzmaProb isRepG1[kNumStates];\r
  CLzmaProb isRepG2[kNumStates];\r
  CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];\r
\r
  CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];\r
  CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex];\r
  CLzmaProb posAlignEncoder[1 << kNumAlignBits];\r
  \r
  CLenPriceEnc lenEnc;\r
  CLenPriceEnc repLenEnc;\r
} CSaveState;\r
\r
\r
typedef struct\r
{\r
  void *matchFinderObj;\r
  IMatchFinder matchFinder;\r
\r
  UInt32 optimumEndIndex;\r
  UInt32 optimumCurrentIndex;\r
\r
  UInt32 longestMatchLength;\r
  UInt32 numPairs;\r
  UInt32 numAvail;\r
\r
  UInt32 numFastBytes;\r
  UInt32 additionalOffset;\r
  UInt32 reps[LZMA_NUM_REPS];\r
  UInt32 state;\r
\r
  unsigned lc, lp, pb;\r
  unsigned lpMask, pbMask;\r
  unsigned lclp;\r
\r
  CLzmaProb *litProbs;\r
\r
  Bool fastMode;\r
  Bool writeEndMark;\r
  Bool finished;\r
  Bool multiThread;\r
  Bool needInit;\r
\r
  UInt64 nowPos64;\r
  \r
  UInt32 matchPriceCount;\r
  UInt32 alignPriceCount;\r
\r
  UInt32 distTableSize;\r
\r
  UInt32 dictSize;\r
  SRes result;\r
\r
  CRangeEnc rc;\r
\r
  #ifndef _7ZIP_ST\r
  Bool mtMode;\r
  CMatchFinderMt matchFinderMt;\r
  #endif\r
\r
  CMatchFinder matchFinderBase;\r
\r
  #ifndef _7ZIP_ST\r
  Byte pad[128];\r
  #endif\r
  \r
  COptimal opt[kNumOpts];\r
  \r
  #ifndef LZMA_LOG_BSR\r
  Byte g_FastPos[1 << kNumLogBits];\r
  #endif\r
\r
  UInt32 ProbPrices[kBitModelTotal >> kNumMoveReducingBits];\r
  UInt32 matches[LZMA_MATCH_LEN_MAX * 2 + 2 + 1];\r
\r
  UInt32 posSlotPrices[kNumLenToPosStates][kDistTableSizeMax];\r
  UInt32 distancesPrices[kNumLenToPosStates][kNumFullDistances];\r
  UInt32 alignPrices[kAlignTableSize];\r
\r
  CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];\r
  CLzmaProb isRep[kNumStates];\r
  CLzmaProb isRepG0[kNumStates];\r
  CLzmaProb isRepG1[kNumStates];\r
  CLzmaProb isRepG2[kNumStates];\r
  CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];\r
\r
  CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];\r
  CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex];\r
  CLzmaProb posAlignEncoder[1 << kNumAlignBits];\r
  \r
  CLenPriceEnc lenEnc;\r
  CLenPriceEnc repLenEnc;\r
\r
  CSaveState saveState;\r
\r
  #ifndef _7ZIP_ST\r
  Byte pad2[128];\r
  #endif\r
} CLzmaEnc;\r
\r
\r
void LzmaEnc_SaveState(CLzmaEncHandle pp)\r
{\r
  CLzmaEnc *p = (CLzmaEnc *)pp;\r
  CSaveState *dest = &p->saveState;\r
  int i;\r
  dest->lenEnc = p->lenEnc;\r
  dest->repLenEnc = p->repLenEnc;\r
  dest->state = p->state;\r
\r
  for (i = 0; i < kNumStates; i++)\r
  {\r
    memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));\r
    memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));\r
  }\r
  for (i = 0; i < kNumLenToPosStates; i++)\r
    memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i]));\r
  memcpy(dest->isRep, p->isRep, sizeof(p->isRep));\r
  memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0));\r
  memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1));\r
  memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2));\r
  memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders));\r
  memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder));\r
  memcpy(dest->reps, p->reps, sizeof(p->reps));\r
  memcpy(dest->litProbs, p->litProbs, ((UInt32)0x300 << p->lclp) * sizeof(CLzmaProb));\r
}\r
\r
void LzmaEnc_RestoreState(CLzmaEncHandle pp)\r
{\r
  CLzmaEnc *dest = (CLzmaEnc *)pp;\r
  const CSaveState *p = &dest->saveState;\r
  int i;\r
  dest->lenEnc = p->lenEnc;\r
  dest->repLenEnc = p->repLenEnc;\r
  dest->state = p->state;\r
\r
  for (i = 0; i < kNumStates; i++)\r
  {\r
    memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));\r
    memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));\r
  }\r
  for (i = 0; i < kNumLenToPosStates; i++)\r
    memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i]));\r
  memcpy(dest->isRep, p->isRep, sizeof(p->isRep));\r
  memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0));\r
  memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1));\r
  memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2));\r
  memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders));\r
  memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder));\r
  memcpy(dest->reps, p->reps, sizeof(p->reps));\r
  memcpy(dest->litProbs, p->litProbs, ((UInt32)0x300 << dest->lclp) * sizeof(CLzmaProb));\r
}\r
\r
SRes LzmaEnc_SetProps(CLzmaEncHandle pp, const CLzmaEncProps *props2)\r
{\r
  CLzmaEnc *p = (CLzmaEnc *)pp;\r
  CLzmaEncProps props = *props2;\r
  LzmaEncProps_Normalize(&props);\r
\r
  if (props.lc > LZMA_LC_MAX\r
      || props.lp > LZMA_LP_MAX\r
      || props.pb > LZMA_PB_MAX\r
      || props.dictSize > ((UInt64)1 << kDicLogSizeMaxCompress)\r
      || props.dictSize > kMaxHistorySize)\r
    return SZ_ERROR_PARAM;\r
\r
  p->dictSize = props.dictSize;\r
  {\r
    unsigned fb = props.fb;\r
    if (fb < 5)\r
      fb = 5;\r
    if (fb > LZMA_MATCH_LEN_MAX)\r
      fb = LZMA_MATCH_LEN_MAX;\r
    p->numFastBytes = fb;\r
  }\r
  p->lc = props.lc;\r
  p->lp = props.lp;\r
  p->pb = props.pb;\r
  p->fastMode = (props.algo == 0);\r
  p->matchFinderBase.btMode = (Byte)(props.btMode ? 1 : 0);\r
  {\r
    UInt32 numHashBytes = 4;\r
    if (props.btMode)\r
    {\r
      if (props.numHashBytes < 2)\r
        numHashBytes = 2;\r
      else if (props.numHashBytes < 4)\r
        numHashBytes = props.numHashBytes;\r
    }\r
    p->matchFinderBase.numHashBytes = numHashBytes;\r
  }\r
\r
  p->matchFinderBase.cutValue = props.mc;\r
\r
  p->writeEndMark = props.writeEndMark;\r
\r
  #ifndef _7ZIP_ST\r
  /*\r
  if (newMultiThread != _multiThread)\r
  {\r
    ReleaseMatchFinder();\r
    _multiThread = newMultiThread;\r
  }\r
  */\r
  p->multiThread = (props.numThreads > 1);\r
  #endif\r
\r
  return SZ_OK;\r
}\r
\r
static const int kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4,  5,  6,   4, 5};\r
static const int kMatchNextStates[kNumStates]   = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10};\r
static const int kRepNextStates[kNumStates]     = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11};\r
static const int kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11};\r
\r
#define IsCharState(s) ((s) < 7)\r
\r
#define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1)\r
\r
#define kInfinityPrice (1 << 30)\r
\r
static void RangeEnc_Construct(CRangeEnc *p)\r
{\r
  p->outStream = NULL;\r
  p->bufBase = NULL;\r
}\r
\r
#define RangeEnc_GetProcessed(p) ((p)->processed + ((p)->buf - (p)->bufBase) + (p)->cacheSize)\r
\r
#define RC_BUF_SIZE (1 << 16)\r
static int RangeEnc_Alloc(CRangeEnc *p, ISzAlloc *alloc)\r
{\r
  if (!p->bufBase)\r
  {\r
    p->bufBase = (Byte *)alloc->Alloc(alloc, RC_BUF_SIZE);\r
    if (!p->bufBase)\r
      return 0;\r
    p->bufLim = p->bufBase + RC_BUF_SIZE;\r
  }\r
  return 1;\r
}\r
\r
static void RangeEnc_Free(CRangeEnc *p, ISzAlloc *alloc)\r
{\r
  alloc->Free(alloc, p->bufBase);\r
  p->bufBase = 0;\r
}\r
\r
static void RangeEnc_Init(CRangeEnc *p)\r
{\r
  /* Stream.Init(); */\r
  p->low = 0;\r
  p->range = 0xFFFFFFFF;\r
  p->cacheSize = 1;\r
  p->cache = 0;\r
\r
  p->buf = p->bufBase;\r
\r
  p->processed = 0;\r
  p->res = SZ_OK;\r
}\r
\r
static void RangeEnc_FlushStream(CRangeEnc *p)\r
{\r
  size_t num;\r
  if (p->res != SZ_OK)\r
    return;\r
  num = p->buf - p->bufBase;\r
  if (num != p->outStream->Write(p->outStream, p->bufBase, num))\r
    p->res = SZ_ERROR_WRITE;\r
  p->processed += num;\r
  p->buf = p->bufBase;\r
}\r
\r
static void MY_FAST_CALL RangeEnc_ShiftLow(CRangeEnc *p)\r
{\r
  if ((UInt32)p->low < (UInt32)0xFF000000 || (unsigned)(p->low >> 32) != 0)\r
  {\r
    Byte temp = p->cache;\r
    do\r
    {\r
      Byte *buf = p->buf;\r
      *buf++ = (Byte)(temp + (Byte)(p->low >> 32));\r
      p->buf = buf;\r
      if (buf == p->bufLim)\r
        RangeEnc_FlushStream(p);\r
      temp = 0xFF;\r
    }\r
    while (--p->cacheSize != 0);\r
    p->cache = (Byte)((UInt32)p->low >> 24);\r
  }\r
  p->cacheSize++;\r
  p->low = (UInt32)p->low << 8;\r
}\r
\r
static void RangeEnc_FlushData(CRangeEnc *p)\r
{\r
  int i;\r
  for (i = 0; i < 5; i++)\r
    RangeEnc_ShiftLow(p);\r
}\r
\r
static void RangeEnc_EncodeDirectBits(CRangeEnc *p, UInt32 value, unsigned numBits)\r
{\r
  do\r
  {\r
    p->range >>= 1;\r
    p->low += p->range & (0 - ((value >> --numBits) & 1));\r
    if (p->range < kTopValue)\r
    {\r
      p->range <<= 8;\r
      RangeEnc_ShiftLow(p);\r
    }\r
  }\r
  while (numBits != 0);\r
}\r
\r
static void RangeEnc_EncodeBit(CRangeEnc *p, CLzmaProb *prob, UInt32 symbol)\r
{\r
  UInt32 ttt = *prob;\r
  UInt32 newBound = (p->range >> kNumBitModelTotalBits) * ttt;\r
  if (symbol == 0)\r
  {\r
    p->range = newBound;\r
    ttt += (kBitModelTotal - ttt) >> kNumMoveBits;\r
  }\r
  else\r
  {\r
    p->low += newBound;\r
    p->range -= newBound;\r
    ttt -= ttt >> kNumMoveBits;\r
  }\r
  *prob = (CLzmaProb)ttt;\r
  if (p->range < kTopValue)\r
  {\r
    p->range <<= 8;\r
    RangeEnc_ShiftLow(p);\r
  }\r
}\r
\r
static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol)\r
{\r
  symbol |= 0x100;\r
  do\r
  {\r
    RangeEnc_EncodeBit(p, probs + (symbol >> 8), (symbol >> 7) & 1);\r
    symbol <<= 1;\r
  }\r
  while (symbol < 0x10000);\r
}\r
\r
static void LitEnc_EncodeMatched(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol, UInt32 matchByte)\r
{\r
  UInt32 offs = 0x100;\r
  symbol |= 0x100;\r
  do\r
  {\r
    matchByte <<= 1;\r
    RangeEnc_EncodeBit(p, probs + (offs + (matchByte & offs) + (symbol >> 8)), (symbol >> 7) & 1);\r
    symbol <<= 1;\r
    offs &= ~(matchByte ^ symbol);\r
  }\r
  while (symbol < 0x10000);\r
}\r
\r
static void LzmaEnc_InitPriceTables(UInt32 *ProbPrices)\r
{\r
  UInt32 i;\r
  for (i = (1 << kNumMoveReducingBits) / 2; i < kBitModelTotal; i += (1 << kNumMoveReducingBits))\r
  {\r
    const int kCyclesBits = kNumBitPriceShiftBits;\r
    UInt32 w = i;\r
    UInt32 bitCount = 0;\r
    int j;\r
    for (j = 0; j < kCyclesBits; j++)\r
    {\r
      w = w * w;\r
      bitCount <<= 1;\r
      while (w >= ((UInt32)1 << 16))\r
      {\r
        w >>= 1;\r
        bitCount++;\r
      }\r
    }\r
    ProbPrices[i >> kNumMoveReducingBits] = ((kNumBitModelTotalBits << kCyclesBits) - 15 - bitCount);\r
  }\r
}\r
\r
\r
#define GET_PRICE(prob, symbol) \\r
  p->ProbPrices[((prob) ^ (((-(int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];\r
\r
#define GET_PRICEa(prob, symbol) \\r
  ProbPrices[((prob) ^ ((-((int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];\r
\r
#define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits]\r
#define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]\r
\r
#define GET_PRICE_0a(prob) ProbPrices[(prob) >> kNumMoveReducingBits]\r
#define GET_PRICE_1a(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]\r
\r
static UInt32 LitEnc_GetPrice(const CLzmaProb *probs, UInt32 symbol, const UInt32 *ProbPrices)\r
{\r
  UInt32 price = 0;\r
  symbol |= 0x100;\r
  do\r
  {\r
    price += GET_PRICEa(probs[symbol >> 8], (symbol >> 7) & 1);\r
    symbol <<= 1;\r
  }\r
  while (symbol < 0x10000);\r
  return price;\r
}\r
\r
static UInt32 LitEnc_GetPriceMatched(const CLzmaProb *probs, UInt32 symbol, UInt32 matchByte, const UInt32 *ProbPrices)\r
{\r
  UInt32 price = 0;\r
  UInt32 offs = 0x100;\r
  symbol |= 0x100;\r
  do\r
  {\r
    matchByte <<= 1;\r
    price += GET_PRICEa(probs[offs + (matchByte & offs) + (symbol >> 8)], (symbol >> 7) & 1);\r
    symbol <<= 1;\r
    offs &= ~(matchByte ^ symbol);\r
  }\r
  while (symbol < 0x10000);\r
  return price;\r
}\r
\r
\r
static void RcTree_Encode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)\r
{\r
  UInt32 m = 1;\r
  int i;\r
  for (i = numBitLevels; i != 0;)\r
  {\r
    UInt32 bit;\r
    i--;\r
    bit = (symbol >> i) & 1;\r
    RangeEnc_EncodeBit(rc, probs + m, bit);\r
    m = (m << 1) | bit;\r
  }\r
}\r
\r
static void RcTree_ReverseEncode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)\r
{\r
  UInt32 m = 1;\r
  int i;\r
  for (i = 0; i < numBitLevels; i++)\r
  {\r
    UInt32 bit = symbol & 1;\r
    RangeEnc_EncodeBit(rc, probs + m, bit);\r
    m = (m << 1) | bit;\r
    symbol >>= 1;\r
  }\r
}\r
\r
static UInt32 RcTree_GetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, const UInt32 *ProbPrices)\r
{\r
  UInt32 price = 0;\r
  symbol |= (1 << numBitLevels);\r
  while (symbol != 1)\r
  {\r
    price += GET_PRICEa(probs[symbol >> 1], symbol & 1);\r
    symbol >>= 1;\r
  }\r
  return price;\r
}\r
\r
static UInt32 RcTree_ReverseGetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, const UInt32 *ProbPrices)\r
{\r
  UInt32 price = 0;\r
  UInt32 m = 1;\r
  int i;\r
  for (i = numBitLevels; i != 0; i--)\r
  {\r
    UInt32 bit = symbol & 1;\r
    symbol >>= 1;\r
    price += GET_PRICEa(probs[m], bit);\r
    m = (m << 1) | bit;\r
  }\r
  return price;\r
}\r
\r
\r
static void LenEnc_Init(CLenEnc *p)\r
{\r
  unsigned i;\r
  p->choice = p->choice2 = kProbInitValue;\r
  for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumLowBits); i++)\r
    p->low[i] = kProbInitValue;\r
  for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumMidBits); i++)\r
    p->mid[i] = kProbInitValue;\r
  for (i = 0; i < kLenNumHighSymbols; i++)\r
    p->high[i] = kProbInitValue;\r
}\r
\r
static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState)\r
{\r
  if (symbol < kLenNumLowSymbols)\r
  {\r
    RangeEnc_EncodeBit(rc, &p->choice, 0);\r
    RcTree_Encode(rc, p->low + (posState << kLenNumLowBits), kLenNumLowBits, symbol);\r
  }\r
  else\r
  {\r
    RangeEnc_EncodeBit(rc, &p->choice, 1);\r
    if (symbol < kLenNumLowSymbols + kLenNumMidSymbols)\r
    {\r
      RangeEnc_EncodeBit(rc, &p->choice2, 0);\r
      RcTree_Encode(rc, p->mid + (posState << kLenNumMidBits), kLenNumMidBits, symbol - kLenNumLowSymbols);\r
    }\r
    else\r
    {\r
      RangeEnc_EncodeBit(rc, &p->choice2, 1);\r
      RcTree_Encode(rc, p->high, kLenNumHighBits, symbol - kLenNumLowSymbols - kLenNumMidSymbols);\r
    }\r
  }\r
}\r
\r
static void LenEnc_SetPrices(CLenEnc *p, UInt32 posState, UInt32 numSymbols, UInt32 *prices, const UInt32 *ProbPrices)\r
{\r
  UInt32 a0 = GET_PRICE_0a(p->choice);\r
  UInt32 a1 = GET_PRICE_1a(p->choice);\r
  UInt32 b0 = a1 + GET_PRICE_0a(p->choice2);\r
  UInt32 b1 = a1 + GET_PRICE_1a(p->choice2);\r
  UInt32 i = 0;\r
  for (i = 0; i < kLenNumLowSymbols; i++)\r
  {\r
    if (i >= numSymbols)\r
      return;\r
    prices[i] = a0 + RcTree_GetPrice(p->low + (posState << kLenNumLowBits), kLenNumLowBits, i, ProbPrices);\r
  }\r
  for (; i < kLenNumLowSymbols + kLenNumMidSymbols; i++)\r
  {\r
    if (i >= numSymbols)\r
      return;\r
    prices[i] = b0 + RcTree_GetPrice(p->mid + (posState << kLenNumMidBits), kLenNumMidBits, i - kLenNumLowSymbols, ProbPrices);\r
  }\r
  for (; i < numSymbols; i++)\r
    prices[i] = b1 + RcTree_GetPrice(p->high, kLenNumHighBits, i - kLenNumLowSymbols - kLenNumMidSymbols, ProbPrices);\r
}\r
\r
static void MY_FAST_CALL LenPriceEnc_UpdateTable(CLenPriceEnc *p, UInt32 posState, const UInt32 *ProbPrices)\r
{\r
  LenEnc_SetPrices(&p->p, posState, p->tableSize, p->prices[posState], ProbPrices);\r
  p->counters[posState] = p->tableSize;\r
}\r
\r
static void LenPriceEnc_UpdateTables(CLenPriceEnc *p, UInt32 numPosStates, const UInt32 *ProbPrices)\r
{\r
  UInt32 posState;\r
  for (posState = 0; posState < numPosStates; posState++)\r
    LenPriceEnc_UpdateTable(p, posState, ProbPrices);\r
}\r
\r
static void LenEnc_Encode2(CLenPriceEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState, Bool updatePrice, const UInt32 *ProbPrices)\r
{\r
  LenEnc_Encode(&p->p, rc, symbol, posState);\r
  if (updatePrice)\r
    if (--p->counters[posState] == 0)\r
      LenPriceEnc_UpdateTable(p, posState, ProbPrices);\r
}\r
\r
\r
\r
\r
static void MovePos(CLzmaEnc *p, UInt32 num)\r
{\r
  #ifdef SHOW_STAT\r
  g_STAT_OFFSET += num;\r
  printf("\n MovePos %u", num);\r
  #endif\r
  \r
  if (num != 0)\r
  {\r
    p->additionalOffset += num;\r
    p->matchFinder.Skip(p->matchFinderObj, num);\r
  }\r
}\r
\r
static UInt32 ReadMatchDistances(CLzmaEnc *p, UInt32 *numDistancePairsRes)\r
{\r
  UInt32 lenRes = 0, numPairs;\r
  p->numAvail = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);\r
  numPairs = p->matchFinder.GetMatches(p->matchFinderObj, p->matches);\r
  \r
  #ifdef SHOW_STAT\r
  printf("\n i = %u numPairs = %u    ", g_STAT_OFFSET, numPairs / 2);\r
  g_STAT_OFFSET++;\r
  {\r
    UInt32 i;\r
    for (i = 0; i < numPairs; i += 2)\r
      printf("%2u %6u   | ", p->matches[i], p->matches[i + 1]);\r
  }\r
  #endif\r
  \r
  if (numPairs > 0)\r
  {\r
    lenRes = p->matches[numPairs - 2];\r
    if (lenRes == p->numFastBytes)\r
    {\r
      UInt32 numAvail = p->numAvail;\r
      if (numAvail > LZMA_MATCH_LEN_MAX)\r
        numAvail = LZMA_MATCH_LEN_MAX;\r
      {\r
        const Byte *pbyCur = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;\r
        const Byte *pby = pbyCur + lenRes;\r
        ptrdiff_t dif = (ptrdiff_t)-1 - p->matches[numPairs - 1];\r
        const Byte *pbyLim = pbyCur + numAvail;\r
        for (; pby != pbyLim && *pby == pby[dif]; pby++);\r
        lenRes = (UInt32)(pby - pbyCur);\r
      }\r
    }\r
  }\r
  p->additionalOffset++;\r
  *numDistancePairsRes = numPairs;\r
  return lenRes;\r
}\r
\r
\r
#define MakeAsChar(p) (p)->backPrev = (UInt32)(-1); (p)->prev1IsChar = False;\r
#define MakeAsShortRep(p) (p)->backPrev = 0; (p)->prev1IsChar = False;\r
#define IsShortRep(p) ((p)->backPrev == 0)\r
\r
static UInt32 GetRepLen1Price(CLzmaEnc *p, UInt32 state, UInt32 posState)\r
{\r
  return\r
    GET_PRICE_0(p->isRepG0[state]) +\r
    GET_PRICE_0(p->isRep0Long[state][posState]);\r
}\r
\r
static UInt32 GetPureRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 state, UInt32 posState)\r
{\r
  UInt32 price;\r
  if (repIndex == 0)\r
  {\r
    price = GET_PRICE_0(p->isRepG0[state]);\r
    price += GET_PRICE_1(p->isRep0Long[state][posState]);\r
  }\r
  else\r
  {\r
    price = GET_PRICE_1(p->isRepG0[state]);\r
    if (repIndex == 1)\r
      price += GET_PRICE_0(p->isRepG1[state]);\r
    else\r
    {\r
      price += GET_PRICE_1(p->isRepG1[state]);\r
      price += GET_PRICE(p->isRepG2[state], repIndex - 2);\r
    }\r
  }\r
  return price;\r
}\r
\r
static UInt32 GetRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 len, UInt32 state, UInt32 posState)\r
{\r
  return p->repLenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN] +\r
    GetPureRepPrice(p, repIndex, state, posState);\r
}\r
\r
static UInt32 Backward(CLzmaEnc *p, UInt32 *backRes, UInt32 cur)\r
{\r
  UInt32 posMem = p->opt[cur].posPrev;\r
  UInt32 backMem = p->opt[cur].backPrev;\r
  p->optimumEndIndex = cur;\r
  do\r
  {\r
    if (p->opt[cur].prev1IsChar)\r
    {\r
      MakeAsChar(&p->opt[posMem])\r
      p->opt[posMem].posPrev = posMem - 1;\r
      if (p->opt[cur].prev2)\r
      {\r
        p->opt[posMem - 1].prev1IsChar = False;\r
        p->opt[posMem - 1].posPrev = p->opt[cur].posPrev2;\r
        p->opt[posMem - 1].backPrev = p->opt[cur].backPrev2;\r
      }\r
    }\r
    {\r
      UInt32 posPrev = posMem;\r
      UInt32 backCur = backMem;\r
      \r
      backMem = p->opt[posPrev].backPrev;\r
      posMem = p->opt[posPrev].posPrev;\r
      \r
      p->opt[posPrev].backPrev = backCur;\r
      p->opt[posPrev].posPrev = cur;\r
      cur = posPrev;\r
    }\r
  }\r
  while (cur != 0);\r
  *backRes = p->opt[0].backPrev;\r
  p->optimumCurrentIndex  = p->opt[0].posPrev;\r
  return p->optimumCurrentIndex;\r
}\r
\r
#define LIT_PROBS(pos, prevByte) (p->litProbs + ((((pos) & p->lpMask) << p->lc) + ((prevByte) >> (8 - p->lc))) * (UInt32)0x300)\r
\r
static UInt32 GetOptimum(CLzmaEnc *p, UInt32 position, UInt32 *backRes)\r
{\r
  UInt32 lenEnd, cur;\r
  UInt32 reps[LZMA_NUM_REPS], repLens[LZMA_NUM_REPS];\r
  UInt32 *matches;\r
\r
  {\r
\r
  UInt32 numAvail, mainLen, numPairs, repMaxIndex, i, posState, len;\r
  UInt32 matchPrice, repMatchPrice, normalMatchPrice;\r
  const Byte *data;\r
  Byte curByte, matchByte;\r
\r
  if (p->optimumEndIndex != p->optimumCurrentIndex)\r
  {\r
    const COptimal *opt = &p->opt[p->optimumCurrentIndex];\r
    UInt32 lenRes = opt->posPrev - p->optimumCurrentIndex;\r
    *backRes = opt->backPrev;\r
    p->optimumCurrentIndex = opt->posPrev;\r
    return lenRes;\r
  }\r
  p->optimumCurrentIndex = p->optimumEndIndex = 0;\r
  \r
  if (p->additionalOffset == 0)\r
    mainLen = ReadMatchDistances(p, &numPairs);\r
  else\r
  {\r
    mainLen = p->longestMatchLength;\r
    numPairs = p->numPairs;\r
  }\r
\r
  numAvail = p->numAvail;\r
  if (numAvail < 2)\r
  {\r
    *backRes = (UInt32)(-1);\r
    return 1;\r
  }\r
  if (numAvail > LZMA_MATCH_LEN_MAX)\r
    numAvail = LZMA_MATCH_LEN_MAX;\r
\r
  data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;\r
  repMaxIndex = 0;\r
  for (i = 0; i < LZMA_NUM_REPS; i++)\r
  {\r
    UInt32 lenTest;\r
    const Byte *data2;\r
    reps[i] = p->reps[i];\r
    data2 = data - reps[i] - 1;\r
    if (data[0] != data2[0] || data[1] != data2[1])\r
    {\r
      repLens[i] = 0;\r
      continue;\r
    }\r
    for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++);\r
    repLens[i] = lenTest;\r
    if (lenTest > repLens[repMaxIndex])\r
      repMaxIndex = i;\r
  }\r
  if (repLens[repMaxIndex] >= p->numFastBytes)\r
  {\r
    UInt32 lenRes;\r
    *backRes = repMaxIndex;\r
    lenRes = repLens[repMaxIndex];\r
    MovePos(p, lenRes - 1);\r
    return lenRes;\r
  }\r
\r
  matches = p->matches;\r
  if (mainLen >= p->numFastBytes)\r
  {\r
    *backRes = matches[numPairs - 1] + LZMA_NUM_REPS;\r
    MovePos(p, mainLen - 1);\r
    return mainLen;\r
  }\r
  curByte = *data;\r
  matchByte = *(data - (reps[0] + 1));\r
\r
  if (mainLen < 2 && curByte != matchByte && repLens[repMaxIndex] < 2)\r
  {\r
    *backRes = (UInt32)-1;\r
    return 1;\r
  }\r
\r
  p->opt[0].state = (CState)p->state;\r
\r
  posState = (position & p->pbMask);\r
\r
  {\r
    const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));\r
    p->opt[1].price = GET_PRICE_0(p->isMatch[p->state][posState]) +\r
        (!IsCharState(p->state) ?\r
          LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) :\r
          LitEnc_GetPrice(probs, curByte, p->ProbPrices));\r
  }\r
\r
  MakeAsChar(&p->opt[1]);\r
\r
  matchPrice = GET_PRICE_1(p->isMatch[p->state][posState]);\r
  repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[p->state]);\r
\r
  if (matchByte == curByte)\r
  {\r
    UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, p->state, posState);\r
    if (shortRepPrice < p->opt[1].price)\r
    {\r
      p->opt[1].price = shortRepPrice;\r
      MakeAsShortRep(&p->opt[1]);\r
    }\r
  }\r
  lenEnd = ((mainLen >= repLens[repMaxIndex]) ? mainLen : repLens[repMaxIndex]);\r
\r
  if (lenEnd < 2)\r
  {\r
    *backRes = p->opt[1].backPrev;\r
    return 1;\r
  }\r
\r
  p->opt[1].posPrev = 0;\r
  for (i = 0; i < LZMA_NUM_REPS; i++)\r
    p->opt[0].backs[i] = reps[i];\r
\r
  len = lenEnd;\r
  do\r
    p->opt[len--].price = kInfinityPrice;\r
  while (len >= 2);\r
\r
  for (i = 0; i < LZMA_NUM_REPS; i++)\r
  {\r
    UInt32 repLen = repLens[i];\r
    UInt32 price;\r
    if (repLen < 2)\r
      continue;\r
    price = repMatchPrice + GetPureRepPrice(p, i, p->state, posState);\r
    do\r
    {\r
      UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][repLen - 2];\r
      COptimal *opt = &p->opt[repLen];\r
      if (curAndLenPrice < opt->price)\r
      {\r
        opt->price = curAndLenPrice;\r
        opt->posPrev = 0;\r
        opt->backPrev = i;\r
        opt->prev1IsChar = False;\r
      }\r
    }\r
    while (--repLen >= 2);\r
  }\r
\r
  normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[p->state]);\r
\r
  len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2);\r
  if (len <= mainLen)\r
  {\r
    UInt32 offs = 0;\r
    while (len > matches[offs])\r
      offs += 2;\r
    for (; ; len++)\r
    {\r
      COptimal *opt;\r
      UInt32 distance = matches[offs + 1];\r
\r
      UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN];\r
      UInt32 lenToPosState = GetLenToPosState(len);\r
      if (distance < kNumFullDistances)\r
        curAndLenPrice += p->distancesPrices[lenToPosState][distance];\r
      else\r
      {\r
        UInt32 slot;\r
        GetPosSlot2(distance, slot);\r
        curAndLenPrice += p->alignPrices[distance & kAlignMask] + p->posSlotPrices[lenToPosState][slot];\r
      }\r
      opt = &p->opt[len];\r
      if (curAndLenPrice < opt->price)\r
      {\r
        opt->price = curAndLenPrice;\r
        opt->posPrev = 0;\r
        opt->backPrev = distance + LZMA_NUM_REPS;\r
        opt->prev1IsChar = False;\r
      }\r
      if (len == matches[offs])\r
      {\r
        offs += 2;\r
        if (offs == numPairs)\r
          break;\r
      }\r
    }\r
  }\r
\r
  cur = 0;\r
\r
    #ifdef SHOW_STAT2\r
    /* if (position >= 0) */\r
    {\r
      unsigned i;\r
      printf("\n pos = %4X", position);\r
      for (i = cur; i <= lenEnd; i++)\r
      printf("\nprice[%4X] = %u", position - cur + i, p->opt[i].price);\r
    }\r
    #endif\r
\r
  }\r
\r
  for (;;)\r
  {\r
    UInt32 numAvail;\r
    UInt32 numAvailFull, newLen, numPairs, posPrev, state, posState, startLen;\r
    UInt32 curPrice, curAnd1Price, matchPrice, repMatchPrice;\r
    Bool nextIsChar;\r
    Byte curByte, matchByte;\r
    const Byte *data;\r
    COptimal *curOpt;\r
    COptimal *nextOpt;\r
\r
    cur++;\r
    if (cur == lenEnd)\r
      return Backward(p, backRes, cur);\r
\r
    newLen = ReadMatchDistances(p, &numPairs);\r
    if (newLen >= p->numFastBytes)\r
    {\r
      p->numPairs = numPairs;\r
      p->longestMatchLength = newLen;\r
      return Backward(p, backRes, cur);\r
    }\r
    position++;\r
    curOpt = &p->opt[cur];\r
    posPrev = curOpt->posPrev;\r
    if (curOpt->prev1IsChar)\r
    {\r
      posPrev--;\r
      if (curOpt->prev2)\r
      {\r
        state = p->opt[curOpt->posPrev2].state;\r
        if (curOpt->backPrev2 < LZMA_NUM_REPS)\r
          state = kRepNextStates[state];\r
        else\r
          state = kMatchNextStates[state];\r
      }\r
      else\r
        state = p->opt[posPrev].state;\r
      state = kLiteralNextStates[state];\r
    }\r
    else\r
      state = p->opt[posPrev].state;\r
    if (posPrev == cur - 1)\r
    {\r
      if (IsShortRep(curOpt))\r
        state = kShortRepNextStates[state];\r
      else\r
        state = kLiteralNextStates[state];\r
    }\r
    else\r
    {\r
      UInt32 pos;\r
      const COptimal *prevOpt;\r
      if (curOpt->prev1IsChar && curOpt->prev2)\r
      {\r
        posPrev = curOpt->posPrev2;\r
        pos = curOpt->backPrev2;\r
        state = kRepNextStates[state];\r
      }\r
      else\r
      {\r
        pos = curOpt->backPrev;\r
        if (pos < LZMA_NUM_REPS)\r
          state = kRepNextStates[state];\r
        else\r
          state = kMatchNextStates[state];\r
      }\r
      prevOpt = &p->opt[posPrev];\r
      if (pos < LZMA_NUM_REPS)\r
      {\r
        UInt32 i;\r
        reps[0] = prevOpt->backs[pos];\r
        for (i = 1; i <= pos; i++)\r
          reps[i] = prevOpt->backs[i - 1];\r
        for (; i < LZMA_NUM_REPS; i++)\r
          reps[i] = prevOpt->backs[i];\r
      }\r
      else\r
      {\r
        UInt32 i;\r
        reps[0] = (pos - LZMA_NUM_REPS);\r
        for (i = 1; i < LZMA_NUM_REPS; i++)\r
          reps[i] = prevOpt->backs[i - 1];\r
      }\r
    }\r
    curOpt->state = (CState)state;\r
\r
    curOpt->backs[0] = reps[0];\r
    curOpt->backs[1] = reps[1];\r
    curOpt->backs[2] = reps[2];\r
    curOpt->backs[3] = reps[3];\r
\r
    curPrice = curOpt->price;\r
    nextIsChar = False;\r
    data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;\r
    curByte = *data;\r
    matchByte = *(data - (reps[0] + 1));\r
\r
    posState = (position & p->pbMask);\r
\r
    curAnd1Price = curPrice + GET_PRICE_0(p->isMatch[state][posState]);\r
    {\r
      const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));\r
      curAnd1Price +=\r
        (!IsCharState(state) ?\r
          LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) :\r
          LitEnc_GetPrice(probs, curByte, p->ProbPrices));\r
    }\r
\r
    nextOpt = &p->opt[cur + 1];\r
\r
    if (curAnd1Price < nextOpt->price)\r
    {\r
      nextOpt->price = curAnd1Price;\r
      nextOpt->posPrev = cur;\r
      MakeAsChar(nextOpt);\r
      nextIsChar = True;\r
    }\r
\r
    matchPrice = curPrice + GET_PRICE_1(p->isMatch[state][posState]);\r
    repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[state]);\r
    \r
    if (matchByte == curByte && !(nextOpt->posPrev < cur && nextOpt->backPrev == 0))\r
    {\r
      UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, state, posState);\r
      if (shortRepPrice <= nextOpt->price)\r
      {\r
        nextOpt->price = shortRepPrice;\r
        nextOpt->posPrev = cur;\r
        MakeAsShortRep(nextOpt);\r
        nextIsChar = True;\r
      }\r
    }\r
    numAvailFull = p->numAvail;\r
    {\r
      UInt32 temp = kNumOpts - 1 - cur;\r
      if (temp < numAvailFull)\r
        numAvailFull = temp;\r
    }\r
\r
    if (numAvailFull < 2)\r
      continue;\r
    numAvail = (numAvailFull <= p->numFastBytes ? numAvailFull : p->numFastBytes);\r
\r
    if (!nextIsChar && matchByte != curByte) /* speed optimization */\r
    {\r
      /* try Literal + rep0 */\r
      UInt32 temp;\r
      UInt32 lenTest2;\r
      const Byte *data2 = data - reps[0] - 1;\r
      UInt32 limit = p->numFastBytes + 1;\r
      if (limit > numAvailFull)\r
        limit = numAvailFull;\r
\r
      for (temp = 1; temp < limit && data[temp] == data2[temp]; temp++);\r
      lenTest2 = temp - 1;\r
      if (lenTest2 >= 2)\r
      {\r
        UInt32 state2 = kLiteralNextStates[state];\r
        UInt32 posStateNext = (position + 1) & p->pbMask;\r
        UInt32 nextRepMatchPrice = curAnd1Price +\r
            GET_PRICE_1(p->isMatch[state2][posStateNext]) +\r
            GET_PRICE_1(p->isRep[state2]);\r
        /* for (; lenTest2 >= 2; lenTest2--) */\r
        {\r
          UInt32 curAndLenPrice;\r
          COptimal *opt;\r
          UInt32 offset = cur + 1 + lenTest2;\r
          while (lenEnd < offset)\r
            p->opt[++lenEnd].price = kInfinityPrice;\r
          curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);\r
          opt = &p->opt[offset];\r
          if (curAndLenPrice < opt->price)\r
          {\r
            opt->price = curAndLenPrice;\r
            opt->posPrev = cur + 1;\r
            opt->backPrev = 0;\r
            opt->prev1IsChar = True;\r
            opt->prev2 = False;\r
          }\r
        }\r
      }\r
    }\r
    \r
    startLen = 2; /* speed optimization */\r
    {\r
    UInt32 repIndex;\r
    for (repIndex = 0; repIndex < LZMA_NUM_REPS; repIndex++)\r
    {\r
      UInt32 lenTest;\r
      UInt32 lenTestTemp;\r
      UInt32 price;\r
      const Byte *data2 = data - reps[repIndex] - 1;\r
      if (data[0] != data2[0] || data[1] != data2[1])\r
        continue;\r
      for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++);\r
      while (lenEnd < cur + lenTest)\r
        p->opt[++lenEnd].price = kInfinityPrice;\r
      lenTestTemp = lenTest;\r
      price = repMatchPrice + GetPureRepPrice(p, repIndex, state, posState);\r
      do\r
      {\r
        UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][lenTest - 2];\r
        COptimal *opt = &p->opt[cur + lenTest];\r
        if (curAndLenPrice < opt->price)\r
        {\r
          opt->price = curAndLenPrice;\r
          opt->posPrev = cur;\r
          opt->backPrev = repIndex;\r
          opt->prev1IsChar = False;\r
        }\r
      }\r
      while (--lenTest >= 2);\r
      lenTest = lenTestTemp;\r
      \r
      if (repIndex == 0)\r
        startLen = lenTest + 1;\r
        \r
      /* if (_maxMode) */\r
        {\r
          UInt32 lenTest2 = lenTest + 1;\r
          UInt32 limit = lenTest2 + p->numFastBytes;\r
          if (limit > numAvailFull)\r
            limit = numAvailFull;\r
          for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++);\r
          lenTest2 -= lenTest + 1;\r
          if (lenTest2 >= 2)\r
          {\r
            UInt32 nextRepMatchPrice;\r
            UInt32 state2 = kRepNextStates[state];\r
            UInt32 posStateNext = (position + lenTest) & p->pbMask;\r
            UInt32 curAndLenCharPrice =\r
                price + p->repLenEnc.prices[posState][lenTest - 2] +\r
                GET_PRICE_0(p->isMatch[state2][posStateNext]) +\r
                LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTest - 1]),\r
                    data[lenTest], data2[lenTest], p->ProbPrices);\r
            state2 = kLiteralNextStates[state2];\r
            posStateNext = (position + lenTest + 1) & p->pbMask;\r
            nextRepMatchPrice = curAndLenCharPrice +\r
                GET_PRICE_1(p->isMatch[state2][posStateNext]) +\r
                GET_PRICE_1(p->isRep[state2]);\r
            \r
            /* for (; lenTest2 >= 2; lenTest2--) */\r
            {\r
              UInt32 curAndLenPrice;\r
              COptimal *opt;\r
              UInt32 offset = cur + lenTest + 1 + lenTest2;\r
              while (lenEnd < offset)\r
                p->opt[++lenEnd].price = kInfinityPrice;\r
              curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);\r
              opt = &p->opt[offset];\r
              if (curAndLenPrice < opt->price)\r
              {\r
                opt->price = curAndLenPrice;\r
                opt->posPrev = cur + lenTest + 1;\r
                opt->backPrev = 0;\r
                opt->prev1IsChar = True;\r
                opt->prev2 = True;\r
                opt->posPrev2 = cur;\r
                opt->backPrev2 = repIndex;\r
              }\r
            }\r
          }\r
        }\r
    }\r
    }\r
    /* for (UInt32 lenTest = 2; lenTest <= newLen; lenTest++) */\r
    if (newLen > numAvail)\r
    {\r
      newLen = numAvail;\r
      for (numPairs = 0; newLen > matches[numPairs]; numPairs += 2);\r
      matches[numPairs] = newLen;\r
      numPairs += 2;\r
    }\r
    if (newLen >= startLen)\r
    {\r
      UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[state]);\r
      UInt32 offs, curBack, posSlot;\r
      UInt32 lenTest;\r
      while (lenEnd < cur + newLen)\r
        p->opt[++lenEnd].price = kInfinityPrice;\r
\r
      offs = 0;\r
      while (startLen > matches[offs])\r
        offs += 2;\r
      curBack = matches[offs + 1];\r
      GetPosSlot2(curBack, posSlot);\r
      for (lenTest = /*2*/ startLen; ; lenTest++)\r
      {\r
        UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][lenTest - LZMA_MATCH_LEN_MIN];\r
        {\r
        UInt32 lenToPosState = GetLenToPosState(lenTest);\r
        COptimal *opt;\r
        if (curBack < kNumFullDistances)\r
          curAndLenPrice += p->distancesPrices[lenToPosState][curBack];\r
        else\r
          curAndLenPrice += p->posSlotPrices[lenToPosState][posSlot] + p->alignPrices[curBack & kAlignMask];\r
        \r
        opt = &p->opt[cur + lenTest];\r
        if (curAndLenPrice < opt->price)\r
        {\r
          opt->price = curAndLenPrice;\r
          opt->posPrev = cur;\r
          opt->backPrev = curBack + LZMA_NUM_REPS;\r
          opt->prev1IsChar = False;\r
        }\r
        }\r
\r
        if (/*_maxMode && */lenTest == matches[offs])\r
        {\r
          /* Try Match + Literal + Rep0 */\r
          const Byte *data2 = data - curBack - 1;\r
          UInt32 lenTest2 = lenTest + 1;\r
          UInt32 limit = lenTest2 + p->numFastBytes;\r
          if (limit > numAvailFull)\r
            limit = numAvailFull;\r
          for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++);\r
          lenTest2 -= lenTest + 1;\r
          if (lenTest2 >= 2)\r
          {\r
            UInt32 nextRepMatchPrice;\r
            UInt32 state2 = kMatchNextStates[state];\r
            UInt32 posStateNext = (position + lenTest) & p->pbMask;\r
            UInt32 curAndLenCharPrice = curAndLenPrice +\r
                GET_PRICE_0(p->isMatch[state2][posStateNext]) +\r
                LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTest - 1]),\r
                    data[lenTest], data2[lenTest], p->ProbPrices);\r
            state2 = kLiteralNextStates[state2];\r
            posStateNext = (posStateNext + 1) & p->pbMask;\r
            nextRepMatchPrice = curAndLenCharPrice +\r
                GET_PRICE_1(p->isMatch[state2][posStateNext]) +\r
                GET_PRICE_1(p->isRep[state2]);\r
            \r
            /* for (; lenTest2 >= 2; lenTest2--) */\r
            {\r
              UInt32 offset = cur + lenTest + 1 + lenTest2;\r
              UInt32 curAndLenPrice2;\r
              COptimal *opt;\r
              while (lenEnd < offset)\r
                p->opt[++lenEnd].price = kInfinityPrice;\r
              curAndLenPrice2 = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);\r
              opt = &p->opt[offset];\r
              if (curAndLenPrice2 < opt->price)\r
              {\r
                opt->price = curAndLenPrice2;\r
                opt->posPrev = cur + lenTest + 1;\r
                opt->backPrev = 0;\r
                opt->prev1IsChar = True;\r
                opt->prev2 = True;\r
                opt->posPrev2 = cur;\r
                opt->backPrev2 = curBack + LZMA_NUM_REPS;\r
              }\r
            }\r
          }\r
          offs += 2;\r
          if (offs == numPairs)\r
            break;\r
          curBack = matches[offs + 1];\r
          if (curBack >= kNumFullDistances)\r
            GetPosSlot2(curBack, posSlot);\r
        }\r
      }\r
    }\r
  }\r
}\r
\r
#define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist))\r
\r
static UInt32 GetOptimumFast(CLzmaEnc *p, UInt32 *backRes)\r
{\r
  UInt32 numAvail, mainLen, mainDist, numPairs, repIndex, repLen, i;\r
  const Byte *data;\r
  const UInt32 *matches;\r
\r
  if (p->additionalOffset == 0)\r
    mainLen = ReadMatchDistances(p, &numPairs);\r
  else\r
  {\r
    mainLen = p->longestMatchLength;\r
    numPairs = p->numPairs;\r
  }\r
\r
  numAvail = p->numAvail;\r
  *backRes = (UInt32)-1;\r
  if (numAvail < 2)\r
    return 1;\r
  if (numAvail > LZMA_MATCH_LEN_MAX)\r
    numAvail = LZMA_MATCH_LEN_MAX;\r
  data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;\r
\r
  repLen = repIndex = 0;\r
  for (i = 0; i < LZMA_NUM_REPS; i++)\r
  {\r
    UInt32 len;\r
    const Byte *data2 = data - p->reps[i] - 1;\r
    if (data[0] != data2[0] || data[1] != data2[1])\r
      continue;\r
    for (len = 2; len < numAvail && data[len] == data2[len]; len++);\r
    if (len >= p->numFastBytes)\r
    {\r
      *backRes = i;\r
      MovePos(p, len - 1);\r
      return len;\r
    }\r
    if (len > repLen)\r
    {\r
      repIndex = i;\r
      repLen = len;\r
    }\r
  }\r
\r
  matches = p->matches;\r
  if (mainLen >= p->numFastBytes)\r
  {\r
    *backRes = matches[numPairs - 1] + LZMA_NUM_REPS;\r
    MovePos(p, mainLen - 1);\r
    return mainLen;\r
  }\r
\r
  mainDist = 0; /* for GCC */\r
  if (mainLen >= 2)\r
  {\r
    mainDist = matches[numPairs - 1];\r
    while (numPairs > 2 && mainLen == matches[numPairs - 4] + 1)\r
    {\r
      if (!ChangePair(matches[numPairs - 3], mainDist))\r
        break;\r
      numPairs -= 2;\r
      mainLen = matches[numPairs - 2];\r
      mainDist = matches[numPairs - 1];\r
    }\r
    if (mainLen == 2 && mainDist >= 0x80)\r
      mainLen = 1;\r
  }\r
\r
  if (repLen >= 2 && (\r
        (repLen + 1 >= mainLen) ||\r
        (repLen + 2 >= mainLen && mainDist >= (1 << 9)) ||\r
        (repLen + 3 >= mainLen && mainDist >= (1 << 15))))\r
  {\r
    *backRes = repIndex;\r
    MovePos(p, repLen - 1);\r
    return repLen;\r
  }\r
  \r
  if (mainLen < 2 || numAvail <= 2)\r
    return 1;\r
\r
  p->longestMatchLength = ReadMatchDistances(p, &p->numPairs);\r
  if (p->longestMatchLength >= 2)\r
  {\r
    UInt32 newDistance = matches[p->numPairs - 1];\r
    if ((p->longestMatchLength >= mainLen && newDistance < mainDist) ||\r
        (p->longestMatchLength == mainLen + 1 && !ChangePair(mainDist, newDistance)) ||\r
        (p->longestMatchLength > mainLen + 1) ||\r
        (p->longestMatchLength + 1 >= mainLen && mainLen >= 3 && ChangePair(newDistance, mainDist)))\r
      return 1;\r
  }\r
  \r
  data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;\r
  for (i = 0; i < LZMA_NUM_REPS; i++)\r
  {\r
    UInt32 len, limit;\r
    const Byte *data2 = data - p->reps[i] - 1;\r
    if (data[0] != data2[0] || data[1] != data2[1])\r
      continue;\r
    limit = mainLen - 1;\r
    for (len = 2; len < limit && data[len] == data2[len]; len++);\r
    if (len >= limit)\r
      return 1;\r
  }\r
  *backRes = mainDist + LZMA_NUM_REPS;\r
  MovePos(p, mainLen - 2);\r
  return mainLen;\r
}\r
\r
static void WriteEndMarker(CLzmaEnc *p, UInt32 posState)\r
{\r
  UInt32 len;\r
  RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1);\r
  RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0);\r
  p->state = kMatchNextStates[p->state];\r
  len = LZMA_MATCH_LEN_MIN;\r
  LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);\r
  RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, (1 << kNumPosSlotBits) - 1);\r
  RangeEnc_EncodeDirectBits(&p->rc, (((UInt32)1 << 30) - 1) >> kNumAlignBits, 30 - kNumAlignBits);\r
  RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, kAlignMask);\r
}\r
\r
static SRes CheckErrors(CLzmaEnc *p)\r
{\r
  if (p->result != SZ_OK)\r
    return p->result;\r
  if (p->rc.res != SZ_OK)\r
    p->result = SZ_ERROR_WRITE;\r
  if (p->matchFinderBase.result != SZ_OK)\r
    p->result = SZ_ERROR_READ;\r
  if (p->result != SZ_OK)\r
    p->finished = True;\r
  return p->result;\r
}\r
\r
static SRes Flush(CLzmaEnc *p, UInt32 nowPos)\r
{\r
  /* ReleaseMFStream(); */\r
  p->finished = True;\r
  if (p->writeEndMark)\r
    WriteEndMarker(p, nowPos & p->pbMask);\r
  RangeEnc_FlushData(&p->rc);\r
  RangeEnc_FlushStream(&p->rc);\r
  return CheckErrors(p);\r
}\r
\r
static void FillAlignPrices(CLzmaEnc *p)\r
{\r
  UInt32 i;\r
  for (i = 0; i < kAlignTableSize; i++)\r
    p->alignPrices[i] = RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits, i, p->ProbPrices);\r
  p->alignPriceCount = 0;\r
}\r
\r
static void FillDistancesPrices(CLzmaEnc *p)\r
{\r
  UInt32 tempPrices[kNumFullDistances];\r
  UInt32 i, lenToPosState;\r
  for (i = kStartPosModelIndex; i < kNumFullDistances; i++)\r
  {\r
    UInt32 posSlot = GetPosSlot1(i);\r
    UInt32 footerBits = ((posSlot >> 1) - 1);\r
    UInt32 base = ((2 | (posSlot & 1)) << footerBits);\r
    tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base - posSlot - 1, footerBits, i - base, p->ProbPrices);\r
  }\r
\r
  for (lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)\r
  {\r
    UInt32 posSlot;\r
    const CLzmaProb *encoder = p->posSlotEncoder[lenToPosState];\r
    UInt32 *posSlotPrices = p->posSlotPrices[lenToPosState];\r
    for (posSlot = 0; posSlot < p->distTableSize; posSlot++)\r
      posSlotPrices[posSlot] = RcTree_GetPrice(encoder, kNumPosSlotBits, posSlot, p->ProbPrices);\r
    for (posSlot = kEndPosModelIndex; posSlot < p->distTableSize; posSlot++)\r
      posSlotPrices[posSlot] += ((((posSlot >> 1) - 1) - kNumAlignBits) << kNumBitPriceShiftBits);\r
\r
    {\r
      UInt32 *distancesPrices = p->distancesPrices[lenToPosState];\r
      for (i = 0; i < kStartPosModelIndex; i++)\r
        distancesPrices[i] = posSlotPrices[i];\r
      for (; i < kNumFullDistances; i++)\r
        distancesPrices[i] = posSlotPrices[GetPosSlot1(i)] + tempPrices[i];\r
    }\r
  }\r
  p->matchPriceCount = 0;\r
}\r
\r
void LzmaEnc_Construct(CLzmaEnc *p)\r
{\r
  RangeEnc_Construct(&p->rc);\r
  MatchFinder_Construct(&p->matchFinderBase);\r
  \r
  #ifndef _7ZIP_ST\r
  MatchFinderMt_Construct(&p->matchFinderMt);\r
  p->matchFinderMt.MatchFinder = &p->matchFinderBase;\r
  #endif\r
\r
  {\r
    CLzmaEncProps props;\r
    LzmaEncProps_Init(&props);\r
    LzmaEnc_SetProps(p, &props);\r
  }\r
\r
  #ifndef LZMA_LOG_BSR\r
  LzmaEnc_FastPosInit(p->g_FastPos);\r
  #endif\r
\r
  LzmaEnc_InitPriceTables(p->ProbPrices);\r
  p->litProbs = NULL;\r
  p->saveState.litProbs = NULL;\r
}\r
\r
CLzmaEncHandle LzmaEnc_Create(ISzAlloc *alloc)\r
{\r
  void *p;\r
  p = alloc->Alloc(alloc, sizeof(CLzmaEnc));\r
  if (p)\r
    LzmaEnc_Construct((CLzmaEnc *)p);\r
  return p;\r
}\r
\r
void LzmaEnc_FreeLits(CLzmaEnc *p, ISzAlloc *alloc)\r
{\r
  alloc->Free(alloc, p->litProbs);\r
  alloc->Free(alloc, p->saveState.litProbs);\r
  p->litProbs = NULL;\r
  p->saveState.litProbs = NULL;\r
}\r
\r
void LzmaEnc_Destruct(CLzmaEnc *p, ISzAlloc *alloc, ISzAlloc *allocBig)\r
{\r
  #ifndef _7ZIP_ST\r
  MatchFinderMt_Destruct(&p->matchFinderMt, allocBig);\r
  #endif\r
  \r
  MatchFinder_Free(&p->matchFinderBase, allocBig);\r
  LzmaEnc_FreeLits(p, alloc);\r
  RangeEnc_Free(&p->rc, alloc);\r
}\r
\r
void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAlloc *alloc, ISzAlloc *allocBig)\r
{\r
  LzmaEnc_Destruct((CLzmaEnc *)p, alloc, allocBig);\r
  alloc->Free(alloc, p);\r
}\r
\r
static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, Bool useLimits, UInt32 maxPackSize, UInt32 maxUnpackSize)\r
{\r
  UInt32 nowPos32, startPos32;\r
  if (p->needInit)\r
  {\r
    p->matchFinder.Init(p->matchFinderObj);\r
    p->needInit = 0;\r
  }\r
\r
  if (p->finished)\r
    return p->result;\r
  RINOK(CheckErrors(p));\r
\r
  nowPos32 = (UInt32)p->nowPos64;\r
  startPos32 = nowPos32;\r
\r
  if (p->nowPos64 == 0)\r
  {\r
    UInt32 numPairs;\r
    Byte curByte;\r
    if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)\r
      return Flush(p, nowPos32);\r
    ReadMatchDistances(p, &numPairs);\r
    RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][0], 0);\r
    p->state = kLiteralNextStates[p->state];\r
    curByte = *(p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset);\r
    LitEnc_Encode(&p->rc, p->litProbs, curByte);\r
    p->additionalOffset--;\r
    nowPos32++;\r
  }\r
\r
  if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) != 0)\r
  for (;;)\r
  {\r
    UInt32 pos, len, posState;\r
\r
    if (p->fastMode)\r
      len = GetOptimumFast(p, &pos);\r
    else\r
      len = GetOptimum(p, nowPos32, &pos);\r
\r
    #ifdef SHOW_STAT2\r
    printf("\n pos = %4X,   len = %u   pos = %u", nowPos32, len, pos);\r
    #endif\r
\r
    posState = nowPos32 & p->pbMask;\r
    if (len == 1 && pos == (UInt32)-1)\r
    {\r
      Byte curByte;\r
      CLzmaProb *probs;\r
      const Byte *data;\r
\r
      RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 0);\r
      data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;\r
      curByte = *data;\r
      probs = LIT_PROBS(nowPos32, *(data - 1));\r
      if (IsCharState(p->state))\r
        LitEnc_Encode(&p->rc, probs, curByte);\r
      else\r
        LitEnc_EncodeMatched(&p->rc, probs, curByte, *(data - p->reps[0] - 1));\r
      p->state = kLiteralNextStates[p->state];\r
    }\r
    else\r
    {\r
      RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1);\r
      if (pos < LZMA_NUM_REPS)\r
      {\r
        RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 1);\r
        if (pos == 0)\r
        {\r
          RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 0);\r
          RangeEnc_EncodeBit(&p->rc, &p->isRep0Long[p->state][posState], ((len == 1) ? 0 : 1));\r
        }\r
        else\r
        {\r
          UInt32 distance = p->reps[pos];\r
          RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 1);\r
          if (pos == 1)\r
            RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 0);\r
          else\r
          {\r
            RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 1);\r
            RangeEnc_EncodeBit(&p->rc, &p->isRepG2[p->state], pos - 2);\r
            if (pos == 3)\r
              p->reps[3] = p->reps[2];\r
            p->reps[2] = p->reps[1];\r
          }\r
          p->reps[1] = p->reps[0];\r
          p->reps[0] = distance;\r
        }\r
        if (len == 1)\r
          p->state = kShortRepNextStates[p->state];\r
        else\r
        {\r
          LenEnc_Encode2(&p->repLenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);\r
          p->state = kRepNextStates[p->state];\r
        }\r
      }\r
      else\r
      {\r
        UInt32 posSlot;\r
        RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0);\r
        p->state = kMatchNextStates[p->state];\r
        LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);\r
        pos -= LZMA_NUM_REPS;\r
        GetPosSlot(pos, posSlot);\r
        RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, posSlot);\r
        \r
        if (posSlot >= kStartPosModelIndex)\r
        {\r
          UInt32 footerBits = ((posSlot >> 1) - 1);\r
          UInt32 base = ((2 | (posSlot & 1)) << footerBits);\r
          UInt32 posReduced = pos - base;\r
\r
          if (posSlot < kEndPosModelIndex)\r
            RcTree_ReverseEncode(&p->rc, p->posEncoders + base - posSlot - 1, footerBits, posReduced);\r
          else\r
          {\r
            RangeEnc_EncodeDirectBits(&p->rc, posReduced >> kNumAlignBits, footerBits - kNumAlignBits);\r
            RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, posReduced & kAlignMask);\r
            p->alignPriceCount++;\r
          }\r
        }\r
        p->reps[3] = p->reps[2];\r
        p->reps[2] = p->reps[1];\r
        p->reps[1] = p->reps[0];\r
        p->reps[0] = pos;\r
        p->matchPriceCount++;\r
      }\r
    }\r
    p->additionalOffset -= len;\r
    nowPos32 += len;\r
    if (p->additionalOffset == 0)\r
    {\r
      UInt32 processed;\r
      if (!p->fastMode)\r
      {\r
        if (p->matchPriceCount >= (1 << 7))\r
          FillDistancesPrices(p);\r
        if (p->alignPriceCount >= kAlignTableSize)\r
          FillAlignPrices(p);\r
      }\r
      if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)\r
        break;\r
      processed = nowPos32 - startPos32;\r
      if (useLimits)\r
      {\r
        if (processed + kNumOpts + 300 >= maxUnpackSize ||\r
            RangeEnc_GetProcessed(&p->rc) + kNumOpts * 2 >= maxPackSize)\r
          break;\r
      }\r
      else if (processed >= (1 << 17))\r
      {\r
        p->nowPos64 += nowPos32 - startPos32;\r
        return CheckErrors(p);\r
      }\r
    }\r
  }\r
  p->nowPos64 += nowPos32 - startPos32;\r
  return Flush(p, nowPos32);\r
}\r
\r
#define kBigHashDicLimit ((UInt32)1 << 24)\r
\r
static SRes LzmaEnc_Alloc(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)\r
{\r
  UInt32 beforeSize = kNumOpts;\r
  if (!RangeEnc_Alloc(&p->rc, alloc))\r
    return SZ_ERROR_MEM;\r
\r
  #ifndef _7ZIP_ST\r
  p->mtMode = (p->multiThread && !p->fastMode && (p->matchFinderBase.btMode != 0));\r
  #endif\r
\r
  {\r
    unsigned lclp = p->lc + p->lp;\r
    if (!p->litProbs || !p->saveState.litProbs || p->lclp != lclp)\r
    {\r
      LzmaEnc_FreeLits(p, alloc);\r
      p->litProbs = (CLzmaProb *)alloc->Alloc(alloc, ((UInt32)0x300 << lclp) * sizeof(CLzmaProb));\r
      p->saveState.litProbs = (CLzmaProb *)alloc->Alloc(alloc, ((UInt32)0x300 << lclp) * sizeof(CLzmaProb));\r
      if (!p->litProbs || !p->saveState.litProbs)\r
      {\r
        LzmaEnc_FreeLits(p, alloc);\r
        return SZ_ERROR_MEM;\r
      }\r
      p->lclp = lclp;\r
    }\r
  }\r
\r
  p->matchFinderBase.bigHash = (Byte)(p->dictSize > kBigHashDicLimit ? 1 : 0);\r
\r
  if (beforeSize + p->dictSize < keepWindowSize)\r
    beforeSize = keepWindowSize - p->dictSize;\r
\r
  #ifndef _7ZIP_ST\r
  if (p->mtMode)\r
  {\r
    RINOK(MatchFinderMt_Create(&p->matchFinderMt, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig));\r
    p->matchFinderObj = &p->matchFinderMt;\r
    MatchFinderMt_CreateVTable(&p->matchFinderMt, &p->matchFinder);\r
  }\r
  else\r
  #endif\r
  {\r
    if (!MatchFinder_Create(&p->matchFinderBase, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig))\r
      return SZ_ERROR_MEM;\r
    p->matchFinderObj = &p->matchFinderBase;\r
    MatchFinder_CreateVTable(&p->matchFinderBase, &p->matchFinder);\r
  }\r
  \r
  return SZ_OK;\r
}\r
\r
void LzmaEnc_Init(CLzmaEnc *p)\r
{\r
  UInt32 i;\r
  p->state = 0;\r
  for (i = 0 ; i < LZMA_NUM_REPS; i++)\r
    p->reps[i] = 0;\r
\r
  RangeEnc_Init(&p->rc);\r
\r
\r
  for (i = 0; i < kNumStates; i++)\r
  {\r
    UInt32 j;\r
    for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++)\r
    {\r
      p->isMatch[i][j] = kProbInitValue;\r
      p->isRep0Long[i][j] = kProbInitValue;\r
    }\r
    p->isRep[i] = kProbInitValue;\r
    p->isRepG0[i] = kProbInitValue;\r
    p->isRepG1[i] = kProbInitValue;\r
    p->isRepG2[i] = kProbInitValue;\r
  }\r
\r
  {\r
    UInt32 num = (UInt32)0x300 << (p->lp + p->lc);\r
    CLzmaProb *probs = p->litProbs;\r
    for (i = 0; i < num; i++)\r
      probs[i] = kProbInitValue;\r
  }\r
\r
  {\r
    for (i = 0; i < kNumLenToPosStates; i++)\r
    {\r
      CLzmaProb *probs = p->posSlotEncoder[i];\r
      UInt32 j;\r
      for (j = 0; j < (1 << kNumPosSlotBits); j++)\r
        probs[j] = kProbInitValue;\r
    }\r
  }\r
  {\r
    for (i = 0; i < kNumFullDistances - kEndPosModelIndex; i++)\r
      p->posEncoders[i] = kProbInitValue;\r
  }\r
\r
  LenEnc_Init(&p->lenEnc.p);\r
  LenEnc_Init(&p->repLenEnc.p);\r
\r
  for (i = 0; i < (1 << kNumAlignBits); i++)\r
    p->posAlignEncoder[i] = kProbInitValue;\r
\r
  p->optimumEndIndex = 0;\r
  p->optimumCurrentIndex = 0;\r
  p->additionalOffset = 0;\r
\r
  p->pbMask = (1 << p->pb) - 1;\r
  p->lpMask = (1 << p->lp) - 1;\r
}\r
\r
void LzmaEnc_InitPrices(CLzmaEnc *p)\r
{\r
  if (!p->fastMode)\r
  {\r
    FillDistancesPrices(p);\r
    FillAlignPrices(p);\r
  }\r
\r
  p->lenEnc.tableSize =\r
  p->repLenEnc.tableSize =\r
      p->numFastBytes + 1 - LZMA_MATCH_LEN_MIN;\r
  LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, p->ProbPrices);\r
  LenPriceEnc_UpdateTables(&p->repLenEnc, 1 << p->pb, p->ProbPrices);\r
}\r
\r
static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)\r
{\r
  UInt32 i;\r
  for (i = 0; i < (UInt32)kDicLogSizeMaxCompress; i++)\r
    if (p->dictSize <= ((UInt32)1 << i))\r
      break;\r
  p->distTableSize = i * 2;\r
\r
  p->finished = False;\r
  p->result = SZ_OK;\r
  RINOK(LzmaEnc_Alloc(p, keepWindowSize, alloc, allocBig));\r
  LzmaEnc_Init(p);\r
  LzmaEnc_InitPrices(p);\r
  p->nowPos64 = 0;\r
  return SZ_OK;\r
}\r
\r
static SRes LzmaEnc_Prepare(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream,\r
    ISzAlloc *alloc, ISzAlloc *allocBig)\r
{\r
  CLzmaEnc *p = (CLzmaEnc *)pp;\r
  p->matchFinderBase.stream = inStream;\r
  p->needInit = 1;\r
  p->rc.outStream = outStream;\r
  return LzmaEnc_AllocAndInit(p, 0, alloc, allocBig);\r
}\r
\r
SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle pp,\r
    ISeqInStream *inStream, UInt32 keepWindowSize,\r
    ISzAlloc *alloc, ISzAlloc *allocBig)\r
{\r
  CLzmaEnc *p = (CLzmaEnc *)pp;\r
  p->matchFinderBase.stream = inStream;\r
  p->needInit = 1;\r
  return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);\r
}\r
\r
static void LzmaEnc_SetInputBuf(CLzmaEnc *p, const Byte *src, SizeT srcLen)\r
{\r
  p->matchFinderBase.directInput = 1;\r
  p->matchFinderBase.bufferBase = (Byte *)src;\r
  p->matchFinderBase.directInputRem = srcLen;\r
}\r
\r
SRes LzmaEnc_MemPrepare(CLzmaEncHandle pp, const Byte *src, SizeT srcLen,\r
    UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)\r
{\r
  CLzmaEnc *p = (CLzmaEnc *)pp;\r
  LzmaEnc_SetInputBuf(p, src, srcLen);\r
  p->needInit = 1;\r
\r
  return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);\r
}\r
\r
void LzmaEnc_Finish(CLzmaEncHandle pp)\r
{\r
  #ifndef _7ZIP_ST\r
  CLzmaEnc *p = (CLzmaEnc *)pp;\r
  if (p->mtMode)\r
    MatchFinderMt_ReleaseStream(&p->matchFinderMt);\r
  #else\r
  UNUSED_VAR(pp);\r
  #endif\r
}\r
\r
\r
typedef struct\r
{\r
  ISeqOutStream funcTable;\r
  Byte *data;\r
  SizeT rem;\r
  Bool overflow;\r
} CSeqOutStreamBuf;\r
\r
static size_t MyWrite(void *pp, const void *data, size_t size)\r
{\r
  CSeqOutStreamBuf *p = (CSeqOutStreamBuf *)pp;\r
  if (p->rem < size)\r
  {\r
    size = p->rem;\r
    p->overflow = True;\r
  }\r
  memcpy(p->data, data, size);\r
  p->rem -= size;\r
  p->data += size;\r
  return size;\r
}\r
\r
\r
UInt32 LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp)\r
{\r
  const CLzmaEnc *p = (CLzmaEnc *)pp;\r
  return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);\r
}\r
\r
\r
const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle pp)\r
{\r
  const CLzmaEnc *p = (CLzmaEnc *)pp;\r
  return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;\r
}\r
\r
\r
SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle pp, Bool reInit,\r
    Byte *dest, size_t *destLen, UInt32 desiredPackSize, UInt32 *unpackSize)\r
{\r
  CLzmaEnc *p = (CLzmaEnc *)pp;\r
  UInt64 nowPos64;\r
  SRes res;\r
  CSeqOutStreamBuf outStream;\r
\r
  outStream.funcTable.Write = MyWrite;\r
  outStream.data = dest;\r
  outStream.rem = *destLen;\r
  outStream.overflow = False;\r
\r
  p->writeEndMark = False;\r
  p->finished = False;\r
  p->result = SZ_OK;\r
\r
  if (reInit)\r
    LzmaEnc_Init(p);\r
  LzmaEnc_InitPrices(p);\r
  nowPos64 = p->nowPos64;\r
  RangeEnc_Init(&p->rc);\r
  p->rc.outStream = &outStream.funcTable;\r
\r
  res = LzmaEnc_CodeOneBlock(p, True, desiredPackSize, *unpackSize);\r
  \r
  *unpackSize = (UInt32)(p->nowPos64 - nowPos64);\r
  *destLen -= outStream.rem;\r
  if (outStream.overflow)\r
    return SZ_ERROR_OUTPUT_EOF;\r
\r
  return res;\r
}\r
\r
\r
static SRes LzmaEnc_Encode2(CLzmaEnc *p, ICompressProgress *progress)\r
{\r
  SRes res = SZ_OK;\r
\r
  #ifndef _7ZIP_ST\r
  Byte allocaDummy[0x300];\r
  allocaDummy[0] = 0;\r
  allocaDummy[1] = allocaDummy[0];\r
  #endif\r
\r
  for (;;)\r
  {\r
    res = LzmaEnc_CodeOneBlock(p, False, 0, 0);\r
    if (res != SZ_OK || p->finished)\r
      break;\r
    if (progress)\r
    {\r
      res = progress->Progress(progress, p->nowPos64, RangeEnc_GetProcessed(&p->rc));\r
      if (res != SZ_OK)\r
      {\r
        res = SZ_ERROR_PROGRESS;\r
        break;\r
      }\r
    }\r
  }\r
  \r
  LzmaEnc_Finish(p);\r
\r
  /*\r
  if (res == S_OK && !Inline_MatchFinder_IsFinishedOK(&p->matchFinderBase))\r
    res = SZ_ERROR_FAIL;\r
  }\r
  */\r
\r
  return res;\r
}\r
\r
\r
SRes LzmaEnc_Encode(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, ICompressProgress *progress,\r
    ISzAlloc *alloc, ISzAlloc *allocBig)\r
{\r
  RINOK(LzmaEnc_Prepare(pp, outStream, inStream, alloc, allocBig));\r
  return LzmaEnc_Encode2((CLzmaEnc *)pp, progress);\r
}\r
\r
\r
SRes LzmaEnc_WriteProperties(CLzmaEncHandle pp, Byte *props, SizeT *size)\r
{\r
  CLzmaEnc *p = (CLzmaEnc *)pp;\r
  unsigned i;\r
  UInt32 dictSize = p->dictSize;\r
  if (*size < LZMA_PROPS_SIZE)\r
    return SZ_ERROR_PARAM;\r
  *size = LZMA_PROPS_SIZE;\r
  props[0] = (Byte)((p->pb * 5 + p->lp) * 9 + p->lc);\r
\r
  if (dictSize >= ((UInt32)1 << 22))\r
  {\r
    UInt32 kDictMask = ((UInt32)1 << 20) - 1;\r
    if (dictSize < (UInt32)0xFFFFFFFF - kDictMask)\r
      dictSize = (dictSize + kDictMask) & ~kDictMask;\r
  }\r
  else for (i = 11; i <= 30; i++)\r
  {\r
    if (dictSize <= ((UInt32)2 << i)) { dictSize = (2 << i); break; }\r
    if (dictSize <= ((UInt32)3 << i)) { dictSize = (3 << i); break; }\r
  }\r
\r
  for (i = 0; i < 4; i++)\r
    props[1 + i] = (Byte)(dictSize >> (8 * i));\r
  return SZ_OK;\r
}\r
\r
\r
SRes LzmaEnc_MemEncode(CLzmaEncHandle pp, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,\r
    int writeEndMark, ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig)\r
{\r
  SRes res;\r
  CLzmaEnc *p = (CLzmaEnc *)pp;\r
\r
  CSeqOutStreamBuf outStream;\r
\r
  outStream.funcTable.Write = MyWrite;\r
  outStream.data = dest;\r
  outStream.rem = *destLen;\r
  outStream.overflow = False;\r
\r
  p->writeEndMark = writeEndMark;\r
  p->rc.outStream = &outStream.funcTable;\r
\r
  res = LzmaEnc_MemPrepare(pp, src, srcLen, 0, alloc, allocBig);\r
  \r
  if (res == SZ_OK)\r
  {\r
    res = LzmaEnc_Encode2(p, progress);\r
    if (res == SZ_OK && p->nowPos64 != srcLen)\r
      res = SZ_ERROR_FAIL;\r
  }\r
\r
  *destLen -= outStream.rem;\r
  if (outStream.overflow)\r
    return SZ_ERROR_OUTPUT_EOF;\r
  return res;\r
}\r
\r
\r
SRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,\r
    const CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeEndMark,\r
    ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig)\r
{\r
  CLzmaEnc *p = (CLzmaEnc *)LzmaEnc_Create(alloc);\r
  SRes res;\r
  if (!p)\r
    return SZ_ERROR_MEM;\r
\r
  res = LzmaEnc_SetProps(p, props);\r
  if (res == SZ_OK)\r
  {\r
    res = LzmaEnc_WriteProperties(p, propsEncoded, propsSize);\r
    if (res == SZ_OK)\r
      res = LzmaEnc_MemEncode(p, dest, destLen, src, srcLen,\r
          writeEndMark, progress, alloc, allocBig);\r
  }\r
\r
  LzmaEnc_Destroy(p, alloc, allocBig);\r
  return res;\r
}\r