/*
* Copyright 2009 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
/* LzmaEnc.c -- LZMA Encoder
2008-10-04 : 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
{
p->level = 5;
p->writeEndMark = 0;
}
{
if (p->dictSize == 0) p->dictSize = (level <= 5 ? (1 << (level * 2 + 14)) : (level == 6 ? (1 << 25) : (1 << 26)));
}
{
}
/* #define LZMA_LOG_BSR */
/* Define it for Intel's CPU */
#ifdef LZMA_LOG_BSR
#define BSR2_RET(pos, res) { unsigned long i; _BitScanReverse(&i, (pos)); res = (i + i) + ((pos >> (i - 1)) & 1); }
{
return res;
}
#else
{
g_FastPos[0] = 0;
{
UInt32 j;
for (j = 0; j < k; j++, c++)
}
}
/*
#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 GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[pos]; else BSR2_RET(pos, res); }
#endif
typedef unsigned CState;
typedef struct _COptimal
{
int prev1IsChar;
int prev2;
} COptimal;
#define kDicLogSizeMin 0
#ifdef _LZMA_PROB32
#else
#endif
typedef struct
{
} CLenEnc;
typedef struct
{
CLenEnc p;
} CLenPriceEnc;
typedef struct _CRangeEnc
{
} CRangeEnc;
typedef struct _CSeqInStreamBuf
{
{
return SZ_OK;
}
typedef struct
{
} CSaveState;
typedef struct _CLzmaEnc
{
void *matchFinderObj;
#ifdef COMPRESS_MF_MT
#endif
#ifdef COMPRESS_MF_MT
#endif
#ifndef LZMA_LOG_BSR
#endif
unsigned lclp;
} CLzmaEnc;
{
int i;
for (i = 0; i < kNumStates; i++)
{
}
for (i = 0; i < kNumLenToPosStates; i++)
}
{
int i;
for (i = 0; i < kNumStates; i++)
{
}
for (i = 0; i < kNumLenToPosStates; i++)
}
{
return SZ_ERROR_PARAM;
{
if (fb < 5)
fb = 5;
if (fb > LZMA_MATCH_LEN_MAX)
p->numFastBytes = fb;
}
{
{
numHashBytes = 2;
}
}
#ifdef COMPRESS_MF_MT
/*
if (newMultiThread != _multiThread)
{
ReleaseMatchFinder();
_multiThread = newMultiThread;
}
*/
#endif
return SZ_OK;
}
#define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1)
{
p->outStream = 0;
p->bufBase = 0;
}
{
if (p->bufBase == 0)
{
if (p->bufBase == 0)
return 0;
}
return 1;
}
{
p->bufBase = 0;
}
{
/* Stream.Init(); */
p->low = 0;
p->range = 0xFFFFFFFF;
p->cacheSize = 1;
p->cache = 0;
p->processed = 0;
}
{
return;
p->res = SZ_ERROR_WRITE;
}
{
{
do
{
temp = 0xFF;
}
while (--p->cacheSize != 0);
}
p->cacheSize++;
}
{
int i;
for (i = 0; i < 5; i++)
}
{
do
{
p->range >>= 1;
{
p->range <<= 8;
}
}
while (numBits != 0);
}
{
if (symbol == 0)
{
}
else
{
}
{
p->range <<= 8;
}
}
{
symbol |= 0x100;
do
{
symbol <<= 1;
}
while (symbol < 0x10000);
}
{
symbol |= 0x100;
do
{
matchByte <<= 1;
symbol <<= 1;
}
while (symbol < 0x10000);
}
{
UInt32 i;
{
UInt32 w = i;
int j;
for (j = 0; j < kCyclesBits; j++)
{
w = w * w;
bitCount <<= 1;
{
w >>= 1;
bitCount++;
}
}
}
}
{
symbol |= 0x100;
do
{
symbol <<= 1;
}
while (symbol < 0x10000);
return price;
}
static UInt32 LitEnc_GetPriceMatched(const CLzmaProb *probs, UInt32 symbol, UInt32 matchByte, UInt32 *ProbPrices)
{
symbol |= 0x100;
do
{
matchByte <<= 1;
symbol <<= 1;
}
while (symbol < 0x10000);
return price;
}
{
UInt32 m = 1;
int i;
for (i = numBitLevels; i != 0;)
{
i--;
m = (m << 1) | bit;
}
}
{
UInt32 m = 1;
int i;
for (i = 0; i < numBitLevels; i++)
{
m = (m << 1) | bit;
symbol >>= 1;
}
}
static UInt32 RcTree_GetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, UInt32 *ProbPrices)
{
while (symbol != 1)
{
symbol >>= 1;
}
return price;
}
static UInt32 RcTree_ReverseGetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, UInt32 *ProbPrices)
{
UInt32 m = 1;
int i;
for (i = numBitLevels; i != 0; i--)
{
symbol >>= 1;
m = (m << 1) | bit;
}
return price;
}
{
unsigned i;
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;
}
{
if (symbol < kLenNumLowSymbols)
{
}
else
{
{
RcTree_Encode(rc, p->mid + (posState << kLenNumMidBits), kLenNumMidBits, symbol - kLenNumLowSymbols);
}
else
{
}
}
}
static void LenEnc_SetPrices(CLenEnc *p, UInt32 posState, UInt32 numSymbols, UInt32 *prices, UInt32 *ProbPrices)
{
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)
{
}
{
}
static void LenEnc_Encode2(CLenPriceEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState, Bool updatePrice, UInt32 *ProbPrices)
{
if (updatePrice)
}
{
#ifdef SHOW_STAT
#endif
if (num != 0)
{
p->additionalOffset += num;
}
}
{
#ifdef SHOW_STAT
ttt++;
{
UInt32 i;
for (i = 0; i < numPairs; i += 2)
}
#endif
if (numPairs > 0)
{
if (lenRes == p->numFastBytes)
{
if (numAvail > LZMA_MATCH_LEN_MAX)
{
}
}
}
p->additionalOffset++;
return lenRes;
}
{
return
}
{
if (repIndex == 0)
{
}
else
{
if (repIndex == 1)
else
{
}
}
return price;
}
{
}
{
p->optimumEndIndex = cur;
do
{
{
{
}
}
{
}
}
while (cur != 0);
return p->optimumCurrentIndex;
}
#define LIT_PROBS(pos, prevByte) (p->litProbs + ((((pos) & p->lpMask) << p->lc) + ((prevByte) >> (8 - p->lc))) * 0x300)
{
if (p->optimumEndIndex != p->optimumCurrentIndex)
{
return lenRes;
}
p->optimumCurrentIndex = p->optimumEndIndex = 0;
if (p->additionalOffset == 0)
else
{
mainLen = p->longestMatchLength;
}
if (numAvail < 2)
{
return 1;
}
if (numAvail > LZMA_MATCH_LEN_MAX)
repMaxIndex = 0;
for (i = 0; i < LZMA_NUM_REPS; i++)
{
{
repLens[i] = 0;
continue;
}
repMaxIndex = i;
}
{
*backRes = repMaxIndex;
return lenRes;
}
if (mainLen >= p->numFastBytes)
{
return mainLen;
}
{
return 1;
}
{
(!IsCharState(p->state) ?
}
{
{
}
}
if (lenEnd < 2)
{
return 1;
}
for (i = 0; i < LZMA_NUM_REPS; i++)
do
while (len >= 2);
for (i = 0; i < LZMA_NUM_REPS; i++)
{
if (repLen < 2)
continue;
do
{
{
}
}
while (--repLen >= 2);
}
{
offs += 2;
for (; ; len++)
{
if (distance < kNumFullDistances)
else
{
}
{
}
{
offs += 2;
break;
}
}
}
cur = 0;
#ifdef SHOW_STAT2
if (position >= 0)
{
unsigned i;
}
#endif
for (;;)
{
cur++;
if (newLen >= p->numFastBytes)
{
p->longestMatchLength = newLen;
}
position++;
if (curOpt->prev1IsChar)
{
posPrev--;
{
else
}
else
}
else
{
if (IsShortRep(curOpt))
else
}
else
{
{
}
else
{
if (pos < LZMA_NUM_REPS)
else
}
if (pos < LZMA_NUM_REPS)
{
UInt32 i;
for (i = 1; i <= pos; i++)
for (; i < LZMA_NUM_REPS; i++)
}
else
{
UInt32 i;
for (i = 1; i < LZMA_NUM_REPS; i++)
}
}
nextIsChar = False;
{
curAnd1Price +=
(!IsCharState(state) ?
}
{
nextIsChar = True;
}
{
{
nextIsChar = True;
}
}
numAvailFull = p->numAvail;
{
if (temp < numAvailFull)
numAvailFull = temp;
}
if (numAvailFull < 2)
continue;
{
/* try Literal + rep0 */
if (limit > numAvailFull)
if (lenTest2 >= 2)
{
/* for (; lenTest2 >= 2; lenTest2--) */
{
{
}
}
}
}
{
{
continue;
do
{
{
}
}
while (--lenTest >= 2);
if (repIndex == 0)
/* if (_maxMode) */
{
if (limit > numAvailFull)
if (lenTest2 >= 2)
{
/* for (; lenTest2 >= 2; lenTest2--) */
{
{
}
}
}
}
}
}
/* for (UInt32 lenTest = 2; lenTest <= newLen; lenTest++) */
{
numPairs += 2;
}
{
offs = 0;
offs += 2;
{
UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][lenTest - LZMA_MATCH_LEN_MIN];
if (curBack < kNumFullDistances)
else
{
}
{
/* Try Match + Literal + Rep0 */
if (limit > numAvailFull)
if (lenTest2 >= 2)
{
/* for (; lenTest2 >= 2; lenTest2--) */
{
{
}
}
}
offs += 2;
break;
if (curBack >= kNumFullDistances)
}
}
}
}
}
{
if (p->additionalOffset == 0)
else
{
mainLen = p->longestMatchLength;
}
if (numAvail < 2)
return 1;
if (numAvail > LZMA_MATCH_LEN_MAX)
for (i = 0; i < LZMA_NUM_REPS; i++)
{
continue;
if (len >= p->numFastBytes)
{
*backRes = i;
return len;
}
{
repIndex = i;
}
}
if (mainLen >= p->numFastBytes)
{
return mainLen;
}
mainDist = 0; /* for GCC */
if (mainLen >= 2)
{
{
break;
numPairs -= 2;
}
mainLen = 1;
}
if (repLen >= 2 && (
{
return repLen;
}
return 1;
if (p->longestMatchLength >= 2)
{
return 1;
}
for (i = 0; i < LZMA_NUM_REPS; i++)
{
continue;
return 1;
}
return mainLen;
}
{
LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, (1 << kNumPosSlotBits) - 1);
}
{
return p->result;
p->result = SZ_ERROR_WRITE;
p->result = SZ_ERROR_READ;
return p->result;
}
{
/* ReleaseMFStream(); */
if (p->writeEndMark)
RangeEnc_FlushData(&p->rc);
RangeEnc_FlushStream(&p->rc);
return CheckErrors(p);
}
{
UInt32 i;
for (i = 0; i < kAlignTableSize; i++)
p->alignPriceCount = 0;
}
{
for (i = kStartPosModelIndex; i < kNumFullDistances; i++)
{
tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base - posSlot - 1, footerBits, i - base, p->ProbPrices);
}
{
{
UInt32 i;
for (i = 0; i < kStartPosModelIndex; i++)
distancesPrices[i] = posSlotPrices[i];
for (; i < kNumFullDistances; i++)
}
}
p->matchPriceCount = 0;
}
{
RangeEnc_Construct(&p->rc);
#ifdef COMPRESS_MF_MT
#endif
{
LzmaEnc_SetProps(p, &props);
}
#ifndef LZMA_LOG_BSR
#endif
p->litProbs = 0;
}
{
void *p;
if (p != 0)
LzmaEnc_Construct((CLzmaEnc *)p);
return p;
}
{
p->litProbs = 0;
}
{
#ifdef COMPRESS_MF_MT
#endif
LzmaEnc_FreeLits(p, alloc);
}
{
}
static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, Bool useLimits, UInt32 maxPackSize, UInt32 maxUnpackSize)
{
if (p->inStream != 0)
{
p->inStream = 0;
}
if (p->finished)
return p->result;
RINOK(CheckErrors(p));
if (p->nowPos64 == 0)
{
ReadMatchDistances(p, &numPairs);
p->additionalOffset--;
nowPos32++;
}
for (;;)
{
if (p->fastMode)
else
#ifdef SHOW_STAT2
#endif
{
if (IsCharState(p->state))
else
}
else
{
if (pos < LZMA_NUM_REPS)
{
if (pos == 0)
{
}
else
{
if (pos == 1)
else
{
if (pos == 3)
}
}
if (len == 1)
else
{
LenEnc_Encode2(&p->repLenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
}
}
else
{
LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
pos -= LZMA_NUM_REPS;
if (posSlot >= kStartPosModelIndex)
{
if (posSlot < kEndPosModelIndex)
else
{
p->alignPriceCount++;
}
}
p->matchPriceCount++;
}
}
p->additionalOffset -= len;
if (p->additionalOffset == 0)
{
if (!p->fastMode)
{
if (p->alignPriceCount >= kAlignTableSize)
FillAlignPrices(p);
}
break;
if (useLimits)
{
break;
}
{
return CheckErrors(p);
}
}
}
}
{
return SZ_ERROR_MEM;
#ifdef COMPRESS_MF_MT
#endif
{
{
LzmaEnc_FreeLits(p, alloc);
{
LzmaEnc_FreeLits(p, alloc);
return SZ_ERROR_MEM;
}
}
}
#ifdef COMPRESS_MF_MT
if (p->mtMode)
{
RINOK(MatchFinderMt_Create(&p->matchFinderMt, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig));
p->matchFinderObj = &p->matchFinderMt;
}
else
#endif
{
if (!MatchFinder_Create(&p->matchFinderBase, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig))
return SZ_ERROR_MEM;
p->matchFinderObj = &p->matchFinderBase;
}
return SZ_OK;
}
{
UInt32 i;
p->state = 0;
for (i = 0 ; i < LZMA_NUM_REPS; i++)
p->reps[i] = 0;
RangeEnc_Init(&p->rc);
for (i = 0; i < kNumStates; i++)
{
UInt32 j;
for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++)
{
p->isMatch[i][j] = kProbInitValue;
p->isRep0Long[i][j] = kProbInitValue;
}
p->isRep[i] = kProbInitValue;
p->isRepG0[i] = kProbInitValue;
p->isRepG1[i] = kProbInitValue;
p->isRepG2[i] = kProbInitValue;
}
{
for (i = 0; i < num; i++)
p->litProbs[i] = kProbInitValue;
}
{
for (i = 0; i < kNumLenToPosStates; i++)
{
UInt32 j;
for (j = 0; j < (1 << kNumPosSlotBits); j++)
probs[j] = kProbInitValue;
}
}
{
for (i = 0; i < kNumFullDistances - kEndPosModelIndex; i++)
p->posEncoders[i] = kProbInitValue;
}
LenEnc_Init(&p->lenEnc.p);
LenEnc_Init(&p->repLenEnc.p);
for (i = 0; i < (1 << kNumAlignBits); i++)
p->posAlignEncoder[i] = kProbInitValue;
p->optimumEndIndex = 0;
p->optimumCurrentIndex = 0;
p->additionalOffset = 0;
}
{
if (!p->fastMode)
{
FillAlignPrices(p);
}
}
static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
{
UInt32 i;
for (i = 0; i < (UInt32)kDicLogSizeMaxCompress; i++)
break;
p->distTableSize = i * 2;
LzmaEnc_Init(p);
p->nowPos64 = 0;
return SZ_OK;
}
{
}
{
}
{
}
{
}
{
#ifdef COMPRESS_MF_MT
if (p->mtMode)
#else
#endif
}
typedef struct _CSeqOutStreamBuf
{
{
{
}
return size;
}
{
}
{
}
{
p->writeEndMark = False;
if (reInit)
LzmaEnc_Init(p);
RangeEnc_Init(&p->rc);
return SZ_ERROR_OUTPUT_EOF;
return res;
}
SRes LzmaEnc_Encode(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, ICompressProgress *progress,
{
#ifdef COMPRESS_MF_MT
int i = 0;
for (i = 0; i < 16; i++)
allocaDummy[i] = (Byte)i;
#endif
for (;;)
{
break;
if (progress != 0)
{
{
break;
}
}
}
return res;
}
{
int i;
if (*size < LZMA_PROPS_SIZE)
return SZ_ERROR_PARAM;
*size = LZMA_PROPS_SIZE;
for (i = 11; i <= 30; i++)
{
{
dictSize = (2 << i);
break;
}
{
dictSize = (3 << i);
break;
}
}
for (i = 0; i < 4; i++)
return SZ_OK;
}
SRes LzmaEnc_MemEncode(CLzmaEncHandle pp, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
{
p->writeEndMark = writeEndMark;
return SZ_ERROR_OUTPUT_EOF;
return res;
}
{
if (p == 0)
return SZ_ERROR_MEM;
{
}
return res;
}