/* LzmaEnc.c -- LZMA Encoder

2009-02-02 : Igor Pavlov : Public domain */

#include <string.h>

/* #define SHOW_STAT */

/* #define SHOW_STAT2 */

#if defined(SHOW_STAT) || defined(SHOW_STAT2)

#include <stdio.h>

#endif

#include "LzmaEnc.h"

#include "LzFind.h"

#ifdef COMPRESS_MF_MT

#include "LzFindMt.h"

#endif

#ifdef SHOW_STAT

static int ttt = 0;

#endif

#define kBlockSizeMax ((1 << LZMA_NUM_BLOCK_SIZE_BITS) - 1)

#define kBlockSize (9 << 10)

#define kUnpackBlockSize (1 << 18)

#define kMatchArraySize (1 << 21)

#define kMatchRecordMaxSize ((LZMA_MATCH_LEN_MAX * 2 + 3) * LZMA_MATCH_LEN_MAX)

#define kNumMaxDirectBits (31)

#define kNumTopBits 24

#define kTopValue ((UInt32)1 << kNumTopBits)

#define kNumBitModelTotalBits 11

#define kBitModelTotal (1 << kNumBitModelTotalBits)

#define kNumMoveBits 5

#define kProbInitValue (kBitModelTotal >> 1)

#define kNumMoveReducingBits 4

#define kNumBitPriceShiftBits 4

#define kBitPrice (1 << kNumBitPriceShiftBits)

void LzmaEncProps_Init(CLzmaEncProps *p)

{

p->level = 5;

p->dictSize = p->mc = 0;

p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->numThreads = -1;

p->writeEndMark = 0;

}

void LzmaEncProps_Normalize(CLzmaEncProps *p)

{

int level = p->level;

if (level < 0) level = 5;

p->level = level;

if (p->dictSize == 0) p->dictSize = (level <= 5 ? (1 << (level * 2 + 14)) : (level == 6 ? (1 << 25) : (1 << 26)));

if (p->lc < 0) p->lc = 3;

if (p->lp < 0) p->lp = 0;

if (p->pb < 0) p->pb = 2;

if (p->algo < 0) p->algo = (level < 5 ? 0 : 1);

if (p->fb < 0) p->fb = (level < 7 ? 32 : 64);

if (p->btMode < 0) p->btMode = (p->algo == 0 ? 0 : 1);

if (p->numHashBytes < 0) p->numHashBytes = 4;

if (p->mc == 0) p->mc = (16 + (p->fb >> 1)) >> (p->btMode ? 0 : 1);

if (p->numThreads < 0)

p->numThreads =

#ifdef COMPRESS_MF_MT

((p->btMode && p->algo) ? 2 : 1);

#else

1;

#endif

}

UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2)

{

CLzmaEncProps props = *props2;

LzmaEncProps_Normalize(&props);

return props.dictSize;

}

/* #define LZMA_LOG_BSR */

/* Define it for Intel's CPU */

#ifdef LZMA_LOG_BSR

#define kDicLogSizeMaxCompress 30

#define BSR2_RET(pos, res) { unsigned long i; _BitScanReverse(&i, (pos)); res = (i + i) + ((pos >> (i - 1)) & 1); }

UInt32 GetPosSlot1(UInt32 pos)

{

UInt32 res;

BSR2_RET(pos, res);

return res;

}

#define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }

#define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res); }

#else

#define kNumLogBits (9 + (int)sizeof(size_t) / 2)

#define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7)

void LzmaEnc_FastPosInit(Byte *g_FastPos)

{

int c = 2, slotFast;

g_FastPos[0] = 0;

g_FastPos[1] = 1;

for (slotFast = 2; slotFast < kNumLogBits * 2; slotFast++)

{

UInt32 k = (1 << ((slotFast >> 1) - 1));

UInt32 j;

for (j = 0; j < k; j++, c++)

g_FastPos[c] = (Byte)slotFast;

}

}

#define BSR2_RET(pos, res) { UInt32 i = 6 + ((kNumLogBits - 1) & \

(0 - (((((UInt32)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \

res = p->g_FastPos[pos >> i] + (i * 2); }

/*

#define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \

p->g_FastPos[pos >> 6] + 12 : \

p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; }

*/

#define GetPosSlot1(pos) p->g_FastPos[pos]

#define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }

#define GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[pos]; else BSR2_RET(pos, res); }

#endif

#define LZMA_NUM_REPS 4

typedef unsigned CState;

typedef struct _COptimal

{

UInt32 price;

CState state;

int prev1IsChar;

int prev2;

UInt32 posPrev2;

UInt32 backPrev2;

UInt32 posPrev;

UInt32 backPrev;

UInt32 backs[LZMA_NUM_REPS];

} COptimal;

#define kNumOpts (1 << 12)

#define kNumLenToPosStates 4

#define kNumPosSlotBits 6

#define kDicLogSizeMin 0

#define kDicLogSizeMax 32

#define kDistTableSizeMax (kDicLogSizeMax * 2)

#define kNumAlignBits 4

#define kAlignTableSize (1 << kNumAlignBits)

#define kAlignMask (kAlignTableSize - 1)

#define kStartPosModelIndex 4

#define kEndPosModelIndex 14

#define kNumPosModels (kEndPosModelIndex - kStartPosModelIndex)

#define kNumFullDistances (1 << (kEndPosModelIndex / 2))

#ifdef _LZMA_PROB32

#define CLzmaProb UInt32

#else

#define CLzmaProb UInt16

#endif

#define LZMA_PB_MAX 4

#define LZMA_LC_MAX 8

#define LZMA_LP_MAX 4

#define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX)

#define kLenNumLowBits 3

#define kLenNumLowSymbols (1 << kLenNumLowBits)

#define kLenNumMidBits 3

#define kLenNumMidSymbols (1 << kLenNumMidBits)

#define kLenNumHighBits 8

#define kLenNumHighSymbols (1 << kLenNumHighBits)

#define kLenNumSymbolsTotal (kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)

#define LZMA_MATCH_LEN_MIN 2

#define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1)

#define kNumStates 12

typedef struct

{

CLzmaProb choice;

CLzmaProb choice2;

CLzmaProb low[LZMA_NUM_PB_STATES_MAX << kLenNumLowBits];

CLzmaProb mid[LZMA_NUM_PB_STATES_MAX << kLenNumMidBits];

CLzmaProb high[kLenNumHighSymbols];

} CLenEnc;

typedef struct

{

CLenEnc p;

UInt32 prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal];

UInt32 tableSize;

UInt32 counters[LZMA_NUM_PB_STATES_MAX];

} CLenPriceEnc;

typedef struct _CRangeEnc

{

UInt32 range;

Byte cache;

UInt64 low;

UInt64 cacheSize;

Byte *buf;

Byte *bufLim;

Byte *bufBase;

ISeqOutStream *outStream;

UInt64 processed;

SRes res;

} CRangeEnc;

typedef struct _CSeqInStreamBuf

{

ISeqInStream funcTable;

const Byte *data;

SizeT rem;

} CSeqInStreamBuf;

static SRes MyRead(void *pp, void *data, size_t *size)

{

size_t curSize = *size;

CSeqInStreamBuf *p = (CSeqInStreamBuf *)pp;

if (p->rem < curSize)

curSize = p->rem;

memcpy(data, p->data, curSize);

p->rem -= curSize;

p->data += curSize;

*size = curSize;

return SZ_OK;

}

typedef struct

{

CLzmaProb *litProbs;

CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];

CLzmaProb isRep[kNumStates];

CLzmaProb isRepG0[kNumStates];

CLzmaProb isRepG1[kNumStates];

CLzmaProb isRepG2[kNumStates];

CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];

CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];

CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex];

CLzmaProb posAlignEncoder[1 << kNumAlignBits];

CLenPriceEnc lenEnc;

CLenPriceEnc repLenEnc;

UInt32 reps[LZMA_NUM_REPS];

UInt32 state;

} CSaveState;

typedef struct _CLzmaEnc

{

IMatchFinder matchFinder;

void *matchFinderObj;

#ifdef COMPRESS_MF_MT

Bool mtMode;

CMatchFinderMt matchFinderMt;

#endif

CMatchFinder matchFinderBase;

#ifdef COMPRESS_MF_MT

Byte pad[128];

#endif

UInt32 optimumEndIndex;

UInt32 optimumCurrentIndex;

UInt32 longestMatchLength;

UInt32 numPairs;

UInt32 numAvail;

COptimal opt[kNumOpts];

#ifndef LZMA_LOG_BSR

Byte g_FastPos[1 << kNumLogBits];

#endif

UInt32 ProbPrices[kBitModelTotal >> kNumMoveReducingBits];

UInt32 matches[LZMA_MATCH_LEN_MAX * 2 + 2 + 1];

UInt32 numFastBytes;

UInt32 additionalOffset;

UInt32 reps[LZMA_NUM_REPS];

UInt32 state;

UInt32 posSlotPrices[kNumLenToPosStates][kDistTableSizeMax];

UInt32 distancesPrices[kNumLenToPosStates][kNumFullDistances];

UInt32 alignPrices[kAlignTableSize];

UInt32 alignPriceCount;

UInt32 distTableSize;

unsigned lc, lp, pb;

unsigned lpMask, pbMask;

CLzmaProb *litProbs;

CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];

CLzmaProb isRep[kNumStates];

CLzmaProb isRepG0[kNumStates];

CLzmaProb isRepG1[kNumStates];

CLzmaProb isRepG2[kNumStates];

CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];

CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];

CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex];

CLzmaProb posAlignEncoder[1 << kNumAlignBits];

CLenPriceEnc lenEnc;

CLenPriceEnc repLenEnc;

unsigned lclp;

Bool fastMode;

CRangeEnc rc;

Bool writeEndMark;

UInt64 nowPos64;

UInt32 matchPriceCount;

Bool finished;

Bool multiThread;

SRes result;

UInt32 dictSize;

UInt32 matchFinderCycles;

ISeqInStream *inStream;

CSeqInStreamBuf seqBufInStream;

CSaveState saveState;

} CLzmaEnc;

void LzmaEnc_SaveState(CLzmaEncHandle pp)

{

CLzmaEnc *p = (CLzmaEnc *)pp;

CSaveState *dest = &p->saveState;

int i;

dest->lenEnc = p->lenEnc;

dest->repLenEnc = p->repLenEnc;

dest->state = p->state;

for (i = 0; i < kNumStates; i++)

{

memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));

memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));

}

for (i = 0; i < kNumLenToPosStates; i++)

memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i]));

memcpy(dest->isRep, p->isRep, sizeof(p->isRep));

memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0));

memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1));

memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2));

memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders));

memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder));

memcpy(dest->reps, p->reps, sizeof(p->reps));

memcpy(dest->litProbs, p->litProbs, (0x300 << p->lclp) * sizeof(CLzmaProb));

}

void LzmaEnc_RestoreState(CLzmaEncHandle pp)

{

CLzmaEnc *dest = (CLzmaEnc *)pp;

const CSaveState *p = &dest->saveState;

int i;

dest->lenEnc = p->lenEnc;

dest->repLenEnc = p->repLenEnc;

dest->state = p->state;

for (i = 0; i < kNumStates; i++)

{

memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));

memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));

}

for (i = 0; i < kNumLenToPosStates; i++)

memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i]));

memcpy(dest->isRep, p->isRep, sizeof(p->isRep));

memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0));

memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1));

memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2));

memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders));

memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder));

memcpy(dest->reps, p->reps, sizeof(p->reps));

memcpy(dest->litProbs, p->litProbs, (0x300 << dest->lclp) * sizeof(CLzmaProb));

}

SRes LzmaEnc_SetProps(CLzmaEncHandle pp, const CLzmaEncProps *props2)

{

CLzmaEnc *p = (CLzmaEnc *)pp;

CLzmaEncProps props = *props2;

LzmaEncProps_Normalize(&props);

if (props.lc > LZMA_LC_MAX || props.lp > LZMA_LP_MAX || props.pb > LZMA_PB_MAX ||

props.dictSize > (1 << kDicLogSizeMaxCompress) || props.dictSize > (1 << 30))

return SZ_ERROR_PARAM;

p->dictSize = props.dictSize;

p->matchFinderCycles = props.mc;

{

unsigned fb = props.fb;

if (fb < 5)

fb = 5;

if (fb > LZMA_MATCH_LEN_MAX)

fb = LZMA_MATCH_LEN_MAX;

p->numFastBytes = fb;

}

p->lc = props.lc;

p->lp = props.lp;

p->pb = props.pb;

p->fastMode = (props.algo == 0);

p->matchFinderBase.btMode = props.btMode;

{

UInt32 numHashBytes = 4;

if (props.btMode)

{

if (props.numHashBytes < 2)

numHashBytes = 2;

else if (props.numHashBytes < 4)

numHashBytes = props.numHashBytes;

}

p->matchFinderBase.numHashBytes = numHashBytes;

}

p->matchFinderBase.cutValue = props.mc;

p->writeEndMark = props.writeEndMark;

#ifdef COMPRESS_MF_MT

/*

if (newMultiThread != _multiThread)

{

ReleaseMatchFinder();

_multiThread = newMultiThread;

}

*/

p->multiThread = (props.numThreads > 1);

#endif

return SZ_OK;

}

static const int kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5};

static const int kMatchNextStates[kNumStates] = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10};

static const int kRepNextStates[kNumStates] = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11};

static const int kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11};

#define IsCharState(s) ((s) < 7)

#define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1)

#define kInfinityPrice (1 << 30)

static void RangeEnc_Construct(CRangeEnc *p)

{

p->outStream = 0;

p->bufBase = 0;

}

#define RangeEnc_GetProcessed(p) ((p)->processed + ((p)->buf - (p)->bufBase) + (p)->cacheSize)

#define RC_BUF_SIZE (1 << 16)

static int RangeEnc_Alloc(CRangeEnc *p, ISzAlloc *alloc)

{

if (p->bufBase == 0)

{

p->bufBase = (Byte *)alloc->Alloc(alloc, RC_BUF_SIZE);

if (p->bufBase == 0)

return 0;

p->bufLim = p->bufBase + RC_BUF_SIZE;

}

return 1;

}

static void RangeEnc_Free(CRangeEnc *p, ISzAlloc *alloc)

{

alloc->Free(alloc, p->bufBase);

p->bufBase = 0;

}

static void RangeEnc_Init(CRangeEnc *p)

{

/* Stream.Init(); */

p->low = 0;

p->range = 0xFFFFFFFF;

p->cacheSize = 1;

p->cache = 0;

p->buf = p->bufBase;

p->processed = 0;

p->res = SZ_OK;

}

static void RangeEnc_FlushStream(CRangeEnc *p)

{

size_t num;

if (p->res != SZ_OK)

return;

num = p->buf - p->bufBase;

if (num != p->outStream->Write(p->outStream, p->bufBase, num))

p->res = SZ_ERROR_WRITE;

p->processed += num;

p->buf = p->bufBase;

}

static void MY_FAST_CALL RangeEnc_ShiftLow(CRangeEnc *p)

{

if ((UInt32)p->low < (UInt32)0xFF000000 || (int)(p->low >> 32) != 0)

{

Byte temp = p->cache;

do

{

Byte *buf = p->buf;

*buf++ = (Byte)(temp + (Byte)(p->low >> 32));

p->buf = buf;

if (buf == p->bufLim)

RangeEnc_FlushStream(p);

temp = 0xFF;

}

while (--p->cacheSize != 0);

p->cache = (Byte)((UInt32)p->low >> 24);

}

p->cacheSize++;

p->low = (UInt32)p->low << 8;

}

static void RangeEnc_FlushData(CRangeEnc *p)

{

int i;

for (i = 0; i < 5; i++)

RangeEnc_ShiftLow(p);

}

static void RangeEnc_EncodeDirectBits(CRangeEnc *p, UInt32 value, int numBits)

{

do

{

p->range >>= 1;

p->low += p->range & (0 - ((value >> --numBits) & 1));

if (p->range < kTopValue)

{

p->range <<= 8;

RangeEnc_ShiftLow(p);

}

}

while (numBits != 0);

}

static void RangeEnc_EncodeBit(CRangeEnc *p, CLzmaProb *prob, UInt32 symbol)

{

UInt32 ttt = *prob;

UInt32 newBound = (p->range >> kNumBitModelTotalBits) * ttt;

if (symbol == 0)

{

p->range = newBound;

ttt += (kBitModelTotal - ttt) >> kNumMoveBits;

}

else

{

p->low += newBound;

p->range -= newBound;

ttt -= ttt >> kNumMoveBits;

}

*prob = (CLzmaProb)ttt;

if (p->range < kTopValue)

{

p->range <<= 8;

RangeEnc_ShiftLow(p);

}

}

static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol)

{

symbol |= 0x100;

do

{

RangeEnc_EncodeBit(p, probs + (symbol >> 8), (symbol >> 7) & 1);

symbol <<= 1;

}

while (symbol < 0x10000);

}

static void LitEnc_EncodeMatched(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol, UInt32 matchByte)

{

UInt32 offs = 0x100;

symbol |= 0x100;

do

{

matchByte <<= 1;

RangeEnc_EncodeBit(p, probs + (offs + (matchByte & offs) + (symbol >> 8)), (symbol >> 7) & 1);

symbol <<= 1;

offs &= ~(matchByte ^ symbol);

}

while (symbol < 0x10000);

}

void LzmaEnc_InitPriceTables(UInt32 *ProbPrices)

{

UInt32 i;

for (i = (1 << kNumMoveReducingBits) / 2; i < kBitModelTotal; i += (1 << kNumMoveReducingBits))

{

const int kCyclesBits = kNumBitPriceShiftBits;

UInt32 w = i;

UInt32 bitCount = 0;

int j;

for (j = 0; j < kCyclesBits; j++)

{

w = w * w;

bitCount <<= 1;

while (w >= ((UInt32)1 << 16))

{

w >>= 1;

bitCount++;

}

}

ProbPrices[i >> kNumMoveReducingBits] = ((kNumBitModelTotalBits << kCyclesBits) - 15 - bitCount);

}

}

#define GET_PRICE(prob, symbol) \

p->ProbPrices[((prob) ^ (((-(int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];

#define GET_PRICEa(prob, symbol) \

ProbPrices[((prob) ^ ((-((int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];

#define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits]

#define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]

#define GET_PRICE_0a(prob) ProbPrices[(prob) >> kNumMoveReducingBits]

#define GET_PRICE_1a(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]

static UInt32 LitEnc_GetPrice(const CLzmaProb *probs, UInt32 symbol, UInt32 *ProbPrices)

{

UInt32 price = 0;

symbol |= 0x100;

do

{

price += GET_PRICEa(probs[symbol >> 8], (symbol >> 7) & 1);

symbol <<= 1;

}

while (symbol < 0x10000);

return price;

}

static UInt32 LitEnc_GetPriceMatched(const CLzmaProb *probs, UInt32 symbol, UInt32 matchByte, UInt32 *ProbPrices)

{

UInt32 price = 0;

UInt32 offs = 0x100;

symbol |= 0x100;

do

{

matchByte <<= 1;

price += GET_PRICEa(probs[offs + (matchByte & offs) + (symbol >> 8)], (symbol >> 7) & 1);

symbol <<= 1;

offs &= ~(matchByte ^ symbol);

}

while (symbol < 0x10000);

return price;

}

static void RcTree_Encode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)

{

UInt32 m = 1;

int i;

for (i = numBitLevels; i != 0;)

{

UInt32 bit;

i--;

bit = (symbol >> i) & 1;

RangeEnc_EncodeBit(rc, probs + m, bit);

m = (m << 1) | bit;

}

}

static void RcTree_ReverseEncode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)

{

UInt32 m = 1;

int i;

for (i = 0; i < numBitLevels; i++)

{

UInt32 bit = symbol & 1;

RangeEnc_EncodeBit(rc, probs + m, bit);

m = (m << 1) | bit;

symbol >>= 1;

}

}

static UInt32 RcTree_GetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, UInt32 *ProbPrices)

{

UInt32 price = 0;

symbol |= (1 << numBitLevels);

while (symbol != 1)

{

price += GET_PRICEa(probs[symbol >> 1], symbol & 1);

symbol >>= 1;

}

return price;

}

static UInt32 RcTree_ReverseGetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, UInt32 *ProbPrices)

{

UInt32 price = 0;

UInt32 m = 1;

int i;

for (i = numBitLevels; i != 0; i--)

{

UInt32 bit = symbol & 1;

symbol >>= 1;

price += GET_PRICEa(probs[m], bit);

m = (m << 1) | bit;

}

return price;

}

static void LenEnc_Init(CLenEnc *p)

{

unsigned i;

p->choice = p->choice2 = kProbInitValue;

for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumLowBits); i++)

p->low[i] = kProbInitValue;

for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumMidBits); i++)

p->mid[i] = kProbInitValue;

for (i = 0; i < kLenNumHighSymbols; i++)

p->high[i] = kProbInitValue;

}

static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState)

{

if (symbol < kLenNumLowSymbols)

{

RangeEnc_EncodeBit(rc, &p->choice, 0);

RcTree_Encode(rc, p->low + (posState << kLenNumLowBits), kLenNumLowBits, symbol);

}

else

{

RangeEnc_EncodeBit(rc, &p->choice, 1);

if (symbol < kLenNumLowSymbols + kLenNumMidSymbols)

{

RangeEnc_EncodeBit(rc, &p->choice2, 0);

RcTree_Encode(rc, p->mid + (posState << kLenNumMidBits), kLenNumMidBits, symbol - kLenNumLowSymbols);

}

else

{

RangeEnc_EncodeBit(rc, &p->choice2, 1);

RcTree_Encode(rc, p->high, kLenNumHighBits, symbol - kLenNumLowSymbols - kLenNumMidSymbols);

}

}

}

static void LenEnc_SetPrices(CLenEnc *p, UInt32 posState, UInt32 numSymbols, UInt32 *prices, UInt32 *ProbPrices)

{

UInt32 a0 = GET_PRICE_0a(p->choice);

UInt32 a1 = GET_PRICE_1a(p->choice);

UInt32 b0 = a1 + GET_PRICE_0a(p->choice2);

UInt32 b1 = a1 + GET_PRICE_1a(p->choice2);

UInt32 i = 0;

for (i = 0; i < kLenNumLowSymbols; i++)

{

if (i >= numSymbols)

return;

prices[i] = a0 + RcTree_GetPrice(p->low + (posState << kLenNumLowBits), kLenNumLowBits, i, ProbPrices);

}

for (; i < kLenNumLowSymbols + kLenNumMidSymbols; i++)

{

if (i >= numSymbols)

return;

prices[i] = b0 + RcTree_GetPrice(p->mid + (posState << kLenNumMidBits), kLenNumMidBits, i - kLenNumLowSymbols, ProbPrices);

}

for (; i < numSymbols; i++)

prices[i] = b1 + RcTree_GetPrice(p->high, kLenNumHighBits, i - kLenNumLowSymbols - kLenNumMidSymbols, ProbPrices);

}

static void MY_FAST_CALL LenPriceEnc_UpdateTable(CLenPriceEnc *p, UInt32 posState, UInt32 *ProbPrices)

{

LenEnc_SetPrices(&p->p, posState, p->tableSize, p->prices[posState], ProbPrices);

p->counters[posState] = p->tableSize;

}

static void LenPriceEnc_UpdateTables(CLenPriceEnc *p, UInt32 numPosStates, UInt32 *ProbPrices)

{

UInt32 posState;

for (posState = 0; posState < numPosStates; posState++)

LenPriceEnc_UpdateTable(p, posState, ProbPrices);

}

static void LenEnc_Encode2(CLenPriceEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState, Bool updatePrice, UInt32 *ProbPrices)

{

LenEnc_Encode(&p->p, rc, symbol, posState);

if (updatePrice)

if (--p->counters[posState] == 0)

LenPriceEnc_UpdateTable(p, posState, ProbPrices);

}

static void MovePos(CLzmaEnc *p, UInt32 num)

{

#ifdef SHOW_STAT

ttt += num;

printf("\n MovePos %d", num);

#endif

if (num != 0)

{

p->additionalOffset += num;

p->matchFinder.Skip(p->matchFinderObj, num);

}

}

static UInt32 ReadMatchDistances(CLzmaEnc *p, UInt32 *numDistancePairsRes)

{

UInt32 lenRes = 0, numPairs;

p->numAvail = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);

numPairs = p->matchFinder.GetMatches(p->matchFinderObj, p->matches);

#ifdef SHOW_STAT

printf("\n i = %d numPairs = %d ", ttt, numPairs / 2);

ttt++;

{

UInt32 i;

for (i = 0; i < numPairs; i += 2)

printf("%2d %6d | ", p->matches[i], p->matches[i + 1]);

}

#endif

if (numPairs > 0)

{

lenRes = p->matches[numPairs - 2];

if (lenRes == p->numFastBytes)

{

const Byte *pby = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;

UInt32 distance = p->matches[numPairs - 1] + 1;

UInt32 numAvail = p->numAvail;

if (numAvail > LZMA_MATCH_LEN_MAX)

numAvail = LZMA_MATCH_LEN_MAX;

{

const Byte *pby2 = pby - distance;

for (; lenRes < numAvail && pby[lenRes] == pby2[lenRes]; lenRes++);

}

}

}

p->additionalOffset++;

*numDistancePairsRes = numPairs;

return lenRes;

}

#define MakeAsChar(p) (p)->backPrev = (UInt32)(-1); (p)->prev1IsChar = False;

#define MakeAsShortRep(p) (p)->backPrev = 0; (p)->prev1IsChar = False;

#define IsShortRep(p) ((p)->backPrev == 0)

static UInt32 GetRepLen1Price(CLzmaEnc *p, UInt32 state, UInt32 posState)

{

return

GET_PRICE_0(p->isRepG0[state]) +

GET_PRICE_0(p->isRep0Long[state][posState]);

}

static UInt32 GetPureRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 state, UInt32 posState)

{

UInt32 price;

if (repIndex == 0)

{

price = GET_PRICE_0(p->isRepG0[state]);

price += GET_PRICE_1(p->isRep0Long[state][posState]);

}

else

{

price = GET_PRICE_1(p->isRepG0[state]);

if (repIndex == 1)

price += GET_PRICE_0(p->isRepG1[state]);

else

{

price += GET_PRICE_1(p->isRepG1[state]);

price += GET_PRICE(p->isRepG2[state], repIndex - 2);

}

}

return price;

}

static UInt32 GetRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 len, UInt32 state, UInt32 posState)

{

return p->repLenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN] +

GetPureRepPrice(p, repIndex, state, posState);

}

static UInt32 Backward(CLzmaEnc *p, UInt32 *backRes, UInt32 cur)

{

UInt32 posMem = p->opt[cur].posPrev;

UInt32 backMem = p->opt[cur].backPrev;

p->optimumEndIndex = cur;

do

{

if (p->opt[cur].prev1IsChar)

{

MakeAsChar(&p->opt[posMem])

p->opt[posMem].posPrev = posMem - 1;

if (p->opt[cur].prev2)

{

p->opt[posMem - 1].prev1IsChar = False;

p->opt[posMem - 1].posPrev = p->opt[cur].posPrev2;

p->opt[posMem - 1].backPrev = p->opt[cur].backPrev2;

}

}

{

UInt32 posPrev = posMem;

UInt32 backCur = backMem;

backMem = p->opt[posPrev].backPrev;

posMem = p->opt[posPrev].posPrev;

p->opt[posPrev].backPrev = backCur;

p->opt[posPrev].posPrev = cur;

cur = posPrev;

}

}

while (cur != 0);

*backRes = p->opt[0].backPrev;

p->optimumCurrentIndex = p->opt[0].posPrev;

return p->optimumCurrentIndex;

}

#define LIT_PROBS(pos, prevByte) (p->litProbs + ((((pos) & p->lpMask) << p->lc) + ((prevByte) >> (8 - p->lc))) * 0x300)

static UInt32 GetOptimum(CLzmaEnc *p, UInt32 position, UInt32 *backRes)

{

UInt32 numAvail, mainLen, numPairs, repMaxIndex, i, posState, lenEnd, len, cur;

UInt32 matchPrice, repMatchPrice, normalMatchPrice;

UInt32 reps[LZMA_NUM_REPS], repLens[LZMA_NUM_REPS];

UInt32 *matches;

const Byte *data;

Byte curByte, matchByte;

if (p->optimumEndIndex != p->optimumCurrentIndex)

{

const COptimal *opt = &p->opt[p->optimumCurrentIndex];

UInt32 lenRes = opt->posPrev - p->optimumCurrentIndex;

*backRes = opt->backPrev;

p->optimumCurrentIndex = opt->posPrev;

return lenRes;

}

p->optimumCurrentIndex = p->optimumEndIndex = 0;

if (p->additionalOffset == 0)

mainLen = ReadMatchDistances(p, &numPairs);

else

{

mainLen = p->longestMatchLength;

numPairs = p->numPairs;

}

numAvail = p->numAvail;

if (numAvail < 2)

{

*backRes = (UInt32)(-1);

return 1;

}

if (numAvail > LZMA_MATCH_LEN_MAX)

numAvail = LZMA_MATCH_LEN_MAX;

data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;

repMaxIndex = 0;

for (i = 0; i < LZMA_NUM_REPS; i++)

{

UInt32 lenTest;

const Byte *data2;

reps[i] = p->reps[i];

data2 = data - (reps[i] + 1);

if (data[0] != data2[0] || data[1] != data2[1])

{

repLens[i] = 0;

continue;

}

for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++);

repLens[i] = lenTest;

if (lenTest > repLens[repMaxIndex])