Mercurial > vba-linux
view src/win32/7zip/7z/C/LzmaEnc.c @ 4:5f6f2134e8ce
apu appears to not be used
author | Robert McIntyre <rlm@mit.edu> |
---|---|
date | Sat, 03 Mar 2012 10:35:58 -0600 |
parents | f9f4f1b99eed |
children |
line wrap: on
line source
1 /* LzmaEnc.c -- LZMA Encoder2 2008-10-04 : Igor Pavlov : Public domain */4 #include <string.h>6 /* #define SHOW_STAT */7 /* #define SHOW_STAT2 */9 #if defined(SHOW_STAT) || defined(SHOW_STAT2)10 #include <stdio.h>11 #endif13 #include "LzmaEnc.h"15 #include "LzFind.h"16 #ifdef COMPRESS_MF_MT17 #include "LzFindMt.h"18 #endif20 #ifdef SHOW_STAT21 static int ttt = 0;22 #endif24 #define kBlockSizeMax ((1 << LZMA_NUM_BLOCK_SIZE_BITS) - 1)26 #define kBlockSize (9 << 10)27 #define kUnpackBlockSize (1 << 18)28 #define kMatchArraySize (1 << 21)29 #define kMatchRecordMaxSize ((LZMA_MATCH_LEN_MAX * 2 + 3) * LZMA_MATCH_LEN_MAX)31 #define kNumMaxDirectBits (31)33 #define kNumTopBits 2434 #define kTopValue ((UInt32)1 << kNumTopBits)36 #define kNumBitModelTotalBits 1137 #define kBitModelTotal (1 << kNumBitModelTotalBits)38 #define kNumMoveBits 539 #define kProbInitValue (kBitModelTotal >> 1)41 #define kNumMoveReducingBits 442 #define kNumBitPriceShiftBits 443 #define kBitPrice (1 << kNumBitPriceShiftBits)45 void LzmaEncProps_Init(CLzmaEncProps *p)46 {47 p->level = 5;48 p->dictSize = p->mc = 0;49 p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->numThreads = -1;50 p->writeEndMark = 0;51 }53 void LzmaEncProps_Normalize(CLzmaEncProps *p)54 {55 int level = p->level;56 if (level < 0) level = 5;57 p->level = level;58 if (p->dictSize == 0) p->dictSize = (level <= 5 ? (1 << (level * 2 + 14)) : (level == 6 ? (1 << 25) : (1 << 26)));59 if (p->lc < 0) p->lc = 3;60 if (p->lp < 0) p->lp = 0;61 if (p->pb < 0) p->pb = 2;62 if (p->algo < 0) p->algo = (level < 5 ? 0 : 1);63 if (p->fb < 0) p->fb = (level < 7 ? 32 : 64);64 if (p->btMode < 0) p->btMode = (p->algo == 0 ? 0 : 1);65 if (p->numHashBytes < 0) p->numHashBytes = 4;66 if (p->mc == 0) p->mc = (16 + (p->fb >> 1)) >> (p->btMode ? 0 : 1);67 if (p->numThreads < 0) p->numThreads = ((p->btMode && p->algo) ? 2 : 1);68 }70 UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2)71 {72 CLzmaEncProps props = *props2;73 LzmaEncProps_Normalize(&props);74 return props.dictSize;75 }77 /* #define LZMA_LOG_BSR */78 /* Define it for Intel's CPU */81 #ifdef LZMA_LOG_BSR83 #define kDicLogSizeMaxCompress 3085 #define BSR2_RET(pos, res) { unsigned long i; _BitScanReverse(&i, (pos)); res = (i + i) + ((pos >> (i - 1)) & 1); }87 UInt32 GetPosSlot1(UInt32 pos)88 {89 UInt32 res;90 BSR2_RET(pos, res);91 return res;92 }93 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }94 #define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res); }96 #else98 #define kNumLogBits (9 + (int)sizeof(size_t) / 2)99 #define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7)101 void LzmaEnc_FastPosInit(Byte *g_FastPos)102 {103 int c = 2, slotFast;104 g_FastPos[0] = 0;105 g_FastPos[1] = 1;107 for (slotFast = 2; slotFast < kNumLogBits * 2; slotFast++)108 {109 UInt32 k = (1 << ((slotFast >> 1) - 1));110 UInt32 j;111 for (j = 0; j < k; j++, c++)112 g_FastPos[c] = (Byte)slotFast;113 }114 }116 #define BSR2_RET(pos, res) { UInt32 i = 6 + ((kNumLogBits - 1) & \117 (0 - (((((UInt32)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \118 res = p->g_FastPos[pos >> i] + (i * 2); }119 /*120 #define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \121 p->g_FastPos[pos >> 6] + 12 : \122 p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; }123 */125 #define GetPosSlot1(pos) p->g_FastPos[pos]126 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }127 #define GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[pos]; else BSR2_RET(pos, res); }129 #endif132 #define LZMA_NUM_REPS 4134 typedef unsigned CState;136 typedef struct _COptimal137 {138 UInt32 price;140 CState state;141 int prev1IsChar;142 int prev2;144 UInt32 posPrev2;145 UInt32 backPrev2;147 UInt32 posPrev;148 UInt32 backPrev;149 UInt32 backs[LZMA_NUM_REPS];150 } COptimal;152 #define kNumOpts (1 << 12)154 #define kNumLenToPosStates 4155 #define kNumPosSlotBits 6156 #define kDicLogSizeMin 0157 #define kDicLogSizeMax 32158 #define kDistTableSizeMax (kDicLogSizeMax * 2)161 #define kNumAlignBits 4162 #define kAlignTableSize (1 << kNumAlignBits)163 #define kAlignMask (kAlignTableSize - 1)165 #define kStartPosModelIndex 4166 #define kEndPosModelIndex 14167 #define kNumPosModels (kEndPosModelIndex - kStartPosModelIndex)169 #define kNumFullDistances (1 << (kEndPosModelIndex / 2))171 #ifdef _LZMA_PROB32172 #define CLzmaProb UInt32173 #else174 #define CLzmaProb UInt16175 #endif177 #define LZMA_PB_MAX 4178 #define LZMA_LC_MAX 8179 #define LZMA_LP_MAX 4181 #define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX)184 #define kLenNumLowBits 3185 #define kLenNumLowSymbols (1 << kLenNumLowBits)186 #define kLenNumMidBits 3187 #define kLenNumMidSymbols (1 << kLenNumMidBits)188 #define kLenNumHighBits 8189 #define kLenNumHighSymbols (1 << kLenNumHighBits)191 #define kLenNumSymbolsTotal (kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)193 #define LZMA_MATCH_LEN_MIN 2194 #define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1)196 #define kNumStates 12198 typedef struct199 {200 CLzmaProb choice;201 CLzmaProb choice2;202 CLzmaProb low[LZMA_NUM_PB_STATES_MAX << kLenNumLowBits];203 CLzmaProb mid[LZMA_NUM_PB_STATES_MAX << kLenNumMidBits];204 CLzmaProb high[kLenNumHighSymbols];205 } CLenEnc;207 typedef struct208 {209 CLenEnc p;210 UInt32 prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal];211 UInt32 tableSize;212 UInt32 counters[LZMA_NUM_PB_STATES_MAX];213 } CLenPriceEnc;215 typedef struct _CRangeEnc216 {217 UInt32 range;218 Byte cache;219 UInt64 low;220 UInt64 cacheSize;221 Byte *buf;222 Byte *bufLim;223 Byte *bufBase;224 ISeqOutStream *outStream;225 UInt64 processed;226 SRes res;227 } CRangeEnc;229 typedef struct _CSeqInStreamBuf230 {231 ISeqInStream funcTable;232 const Byte *data;233 SizeT rem;234 } CSeqInStreamBuf;236 static SRes MyRead(void *pp, void *data, size_t *size)237 {238 size_t curSize = *size;239 CSeqInStreamBuf *p = (CSeqInStreamBuf *)pp;240 if (p->rem < curSize)241 curSize = p->rem;242 memcpy(data, p->data, curSize);243 p->rem -= curSize;244 p->data += curSize;245 *size = curSize;246 return SZ_OK;247 }249 typedef struct250 {251 CLzmaProb *litProbs;253 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];254 CLzmaProb isRep[kNumStates];255 CLzmaProb isRepG0[kNumStates];256 CLzmaProb isRepG1[kNumStates];257 CLzmaProb isRepG2[kNumStates];258 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];260 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];261 CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex];262 CLzmaProb posAlignEncoder[1 << kNumAlignBits];264 CLenPriceEnc lenEnc;265 CLenPriceEnc repLenEnc;267 UInt32 reps[LZMA_NUM_REPS];268 UInt32 state;269 } CSaveState;271 typedef struct _CLzmaEnc272 {273 IMatchFinder matchFinder;274 void *matchFinderObj;276 #ifdef COMPRESS_MF_MT277 Bool mtMode;278 CMatchFinderMt matchFinderMt;279 #endif281 CMatchFinder matchFinderBase;283 #ifdef COMPRESS_MF_MT284 Byte pad[128];285 #endif287 UInt32 optimumEndIndex;288 UInt32 optimumCurrentIndex;290 UInt32 longestMatchLength;291 UInt32 numPairs;292 UInt32 numAvail;293 COptimal opt[kNumOpts];295 #ifndef LZMA_LOG_BSR296 Byte g_FastPos[1 << kNumLogBits];297 #endif299 UInt32 ProbPrices[kBitModelTotal >> kNumMoveReducingBits];300 UInt32 matches[LZMA_MATCH_LEN_MAX * 2 + 2 + 1];301 UInt32 numFastBytes;302 UInt32 additionalOffset;303 UInt32 reps[LZMA_NUM_REPS];304 UInt32 state;306 UInt32 posSlotPrices[kNumLenToPosStates][kDistTableSizeMax];307 UInt32 distancesPrices[kNumLenToPosStates][kNumFullDistances];308 UInt32 alignPrices[kAlignTableSize];309 UInt32 alignPriceCount;311 UInt32 distTableSize;313 unsigned lc, lp, pb;314 unsigned lpMask, pbMask;316 CLzmaProb *litProbs;318 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];319 CLzmaProb isRep[kNumStates];320 CLzmaProb isRepG0[kNumStates];321 CLzmaProb isRepG1[kNumStates];322 CLzmaProb isRepG2[kNumStates];323 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];325 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];326 CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex];327 CLzmaProb posAlignEncoder[1 << kNumAlignBits];329 CLenPriceEnc lenEnc;330 CLenPriceEnc repLenEnc;332 unsigned lclp;334 Bool fastMode;336 CRangeEnc rc;338 Bool writeEndMark;339 UInt64 nowPos64;340 UInt32 matchPriceCount;341 Bool finished;342 Bool multiThread;344 SRes result;345 UInt32 dictSize;346 UInt32 matchFinderCycles;348 ISeqInStream *inStream;349 CSeqInStreamBuf seqBufInStream;351 CSaveState saveState;352 } CLzmaEnc;354 void LzmaEnc_SaveState(CLzmaEncHandle pp)355 {356 CLzmaEnc *p = (CLzmaEnc *)pp;357 CSaveState *dest = &p->saveState;358 int i;359 dest->lenEnc = p->lenEnc;360 dest->repLenEnc = p->repLenEnc;361 dest->state = p->state;363 for (i = 0; i < kNumStates; i++)364 {365 memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));366 memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));367 }368 for (i = 0; i < kNumLenToPosStates; i++)369 memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i]));370 memcpy(dest->isRep, p->isRep, sizeof(p->isRep));371 memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0));372 memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1));373 memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2));374 memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders));375 memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder));376 memcpy(dest->reps, p->reps, sizeof(p->reps));377 memcpy(dest->litProbs, p->litProbs, (0x300 << p->lclp) * sizeof(CLzmaProb));378 }380 void LzmaEnc_RestoreState(CLzmaEncHandle pp)381 {382 CLzmaEnc *dest = (CLzmaEnc *)pp;383 const CSaveState *p = &dest->saveState;384 int i;385 dest->lenEnc = p->lenEnc;386 dest->repLenEnc = p->repLenEnc;387 dest->state = p->state;389 for (i = 0; i < kNumStates; i++)390 {391 memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));392 memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));393 }394 for (i = 0; i < kNumLenToPosStates; i++)395 memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i]));396 memcpy(dest->isRep, p->isRep, sizeof(p->isRep));397 memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0));398 memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1));399 memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2));400 memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders));401 memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder));402 memcpy(dest->reps, p->reps, sizeof(p->reps));403 memcpy(dest->litProbs, p->litProbs, (0x300 << dest->lclp) * sizeof(CLzmaProb));404 }406 SRes LzmaEnc_SetProps(CLzmaEncHandle pp, const CLzmaEncProps *props2)407 {408 CLzmaEnc *p = (CLzmaEnc *)pp;409 CLzmaEncProps props = *props2;410 LzmaEncProps_Normalize(&props);412 if (props.lc > LZMA_LC_MAX || props.lp > LZMA_LP_MAX || props.pb > LZMA_PB_MAX ||413 props.dictSize > (1 << kDicLogSizeMaxCompress) || props.dictSize > (1 << 30))414 return SZ_ERROR_PARAM;415 p->dictSize = props.dictSize;416 p->matchFinderCycles = props.mc;417 {418 unsigned fb = props.fb;419 if (fb < 5)420 fb = 5;421 if (fb > LZMA_MATCH_LEN_MAX)422 fb = LZMA_MATCH_LEN_MAX;423 p->numFastBytes = fb;424 }425 p->lc = props.lc;426 p->lp = props.lp;427 p->pb = props.pb;428 p->fastMode = (props.algo == 0);429 p->matchFinderBase.btMode = props.btMode;430 {431 UInt32 numHashBytes = 4;432 if (props.btMode)433 {434 if (props.numHashBytes < 2)435 numHashBytes = 2;436 else if (props.numHashBytes < 4)437 numHashBytes = props.numHashBytes;438 }439 p->matchFinderBase.numHashBytes = numHashBytes;440 }442 p->matchFinderBase.cutValue = props.mc;444 p->writeEndMark = props.writeEndMark;446 #ifdef COMPRESS_MF_MT447 /*448 if (newMultiThread != _multiThread)449 {450 ReleaseMatchFinder();451 _multiThread = newMultiThread;452 }453 */454 p->multiThread = (props.numThreads > 1);455 #endif457 return SZ_OK;458 }460 static const int kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5};461 static const int kMatchNextStates[kNumStates] = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10};462 static const int kRepNextStates[kNumStates] = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11};463 static const int kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11};465 #define IsCharState(s) ((s) < 7)467 #define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1)469 #define kInfinityPrice (1 << 30)471 static void RangeEnc_Construct(CRangeEnc *p)472 {473 p->outStream = 0;474 p->bufBase = 0;475 }477 #define RangeEnc_GetProcessed(p) ((p)->processed + ((p)->buf - (p)->bufBase) + (p)->cacheSize)479 #define RC_BUF_SIZE (1 << 16)480 static int RangeEnc_Alloc(CRangeEnc *p, ISzAlloc *alloc)481 {482 if (p->bufBase == 0)483 {484 p->bufBase = (Byte *)alloc->Alloc(alloc, RC_BUF_SIZE);485 if (p->bufBase == 0)486 return 0;487 p->bufLim = p->bufBase + RC_BUF_SIZE;488 }489 return 1;490 }492 static void RangeEnc_Free(CRangeEnc *p, ISzAlloc *alloc)493 {494 alloc->Free(alloc, p->bufBase);495 p->bufBase = 0;496 }498 static void RangeEnc_Init(CRangeEnc *p)499 {500 /* Stream.Init(); */501 p->low = 0;502 p->range = 0xFFFFFFFF;503 p->cacheSize = 1;504 p->cache = 0;506 p->buf = p->bufBase;508 p->processed = 0;509 p->res = SZ_OK;510 }512 static void RangeEnc_FlushStream(CRangeEnc *p)513 {514 size_t num;515 if (p->res != SZ_OK)516 return;517 num = p->buf - p->bufBase;518 if (num != p->outStream->Write(p->outStream, p->bufBase, num))519 p->res = SZ_ERROR_WRITE;520 p->processed += num;521 p->buf = p->bufBase;522 }524 static void MY_FAST_CALL RangeEnc_ShiftLow(CRangeEnc *p)525 {526 if ((UInt32)p->low < (UInt32)0xFF000000 || (int)(p->low >> 32) != 0)527 {528 Byte temp = p->cache;529 do530 {531 Byte *buf = p->buf;532 *buf++ = (Byte)(temp + (Byte)(p->low >> 32));533 p->buf = buf;534 if (buf == p->bufLim)535 RangeEnc_FlushStream(p);536 temp = 0xFF;537 }538 while (--p->cacheSize != 0);539 p->cache = (Byte)((UInt32)p->low >> 24);540 }541 p->cacheSize++;542 p->low = (UInt32)p->low << 8;543 }545 static void RangeEnc_FlushData(CRangeEnc *p)546 {547 int i;548 for (i = 0; i < 5; i++)549 RangeEnc_ShiftLow(p);550 }552 static void RangeEnc_EncodeDirectBits(CRangeEnc *p, UInt32 value, int numBits)553 {554 do555 {556 p->range >>= 1;557 p->low += p->range & (0 - ((value >> --numBits) & 1));558 if (p->range < kTopValue)559 {560 p->range <<= 8;561 RangeEnc_ShiftLow(p);562 }563 }564 while (numBits != 0);565 }567 static void RangeEnc_EncodeBit(CRangeEnc *p, CLzmaProb *prob, UInt32 symbol)568 {569 UInt32 ttt = *prob;570 UInt32 newBound = (p->range >> kNumBitModelTotalBits) * ttt;571 if (symbol == 0)572 {573 p->range = newBound;574 ttt += (kBitModelTotal - ttt) >> kNumMoveBits;575 }576 else577 {578 p->low += newBound;579 p->range -= newBound;580 ttt -= ttt >> kNumMoveBits;581 }582 *prob = (CLzmaProb)ttt;583 if (p->range < kTopValue)584 {585 p->range <<= 8;586 RangeEnc_ShiftLow(p);587 }588 }590 static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol)591 {592 symbol |= 0x100;593 do594 {595 RangeEnc_EncodeBit(p, probs + (symbol >> 8), (symbol >> 7) & 1);596 symbol <<= 1;597 }598 while (symbol < 0x10000);599 }601 static void LitEnc_EncodeMatched(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol, UInt32 matchByte)602 {603 UInt32 offs = 0x100;604 symbol |= 0x100;605 do606 {607 matchByte <<= 1;608 RangeEnc_EncodeBit(p, probs + (offs + (matchByte & offs) + (symbol >> 8)), (symbol >> 7) & 1);609 symbol <<= 1;610 offs &= ~(matchByte ^ symbol);611 }612 while (symbol < 0x10000);613 }615 void LzmaEnc_InitPriceTables(UInt32 *ProbPrices)616 {617 UInt32 i;618 for (i = (1 << kNumMoveReducingBits) / 2; i < kBitModelTotal; i += (1 << kNumMoveReducingBits))619 {620 const int kCyclesBits = kNumBitPriceShiftBits;621 UInt32 w = i;622 UInt32 bitCount = 0;623 int j;624 for (j = 0; j < kCyclesBits; j++)625 {626 w = w * w;627 bitCount <<= 1;628 while (w >= ((UInt32)1 << 16))629 {630 w >>= 1;631 bitCount++;632 }633 }634 ProbPrices[i >> kNumMoveReducingBits] = ((kNumBitModelTotalBits << kCyclesBits) - 15 - bitCount);635 }636 }639 #define GET_PRICE(prob, symbol) \640 p->ProbPrices[((prob) ^ (((-(int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];642 #define GET_PRICEa(prob, symbol) \643 ProbPrices[((prob) ^ ((-((int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];645 #define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits]646 #define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]648 #define GET_PRICE_0a(prob) ProbPrices[(prob) >> kNumMoveReducingBits]649 #define GET_PRICE_1a(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]651 static UInt32 LitEnc_GetPrice(const CLzmaProb *probs, UInt32 symbol, UInt32 *ProbPrices)652 {653 UInt32 price = 0;654 symbol |= 0x100;655 do656 {657 price += GET_PRICEa(probs[symbol >> 8], (symbol >> 7) & 1);658 symbol <<= 1;659 }660 while (symbol < 0x10000);661 return price;662 }664 static UInt32 LitEnc_GetPriceMatched(const CLzmaProb *probs, UInt32 symbol, UInt32 matchByte, UInt32 *ProbPrices)665 {666 UInt32 price = 0;667 UInt32 offs = 0x100;668 symbol |= 0x100;669 do670 {671 matchByte <<= 1;672 price += GET_PRICEa(probs[offs + (matchByte & offs) + (symbol >> 8)], (symbol >> 7) & 1);673 symbol <<= 1;674 offs &= ~(matchByte ^ symbol);675 }676 while (symbol < 0x10000);677 return price;678 }681 static void RcTree_Encode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)682 {683 UInt32 m = 1;684 int i;685 for (i = numBitLevels; i != 0;)686 {687 UInt32 bit;688 i--;689 bit = (symbol >> i) & 1;690 RangeEnc_EncodeBit(rc, probs + m, bit);691 m = (m << 1) | bit;692 }693 }695 static void RcTree_ReverseEncode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)696 {697 UInt32 m = 1;698 int i;699 for (i = 0; i < numBitLevels; i++)700 {701 UInt32 bit = symbol & 1;702 RangeEnc_EncodeBit(rc, probs + m, bit);703 m = (m << 1) | bit;704 symbol >>= 1;705 }706 }708 static UInt32 RcTree_GetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, UInt32 *ProbPrices)709 {710 UInt32 price = 0;711 symbol |= (1 << numBitLevels);712 while (symbol != 1)713 {714 price += GET_PRICEa(probs[symbol >> 1], symbol & 1);715 symbol >>= 1;716 }717 return price;718 }720 static UInt32 RcTree_ReverseGetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, UInt32 *ProbPrices)721 {722 UInt32 price = 0;723 UInt32 m = 1;724 int i;725 for (i = numBitLevels; i != 0; i--)726 {727 UInt32 bit = symbol & 1;728 symbol >>= 1;729 price += GET_PRICEa(probs[m], bit);730 m = (m << 1) | bit;731 }732 return price;733 }736 static void LenEnc_Init(CLenEnc *p)737 {738 unsigned i;739 p->choice = p->choice2 = kProbInitValue;740 for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumLowBits); i++)741 p->low[i] = kProbInitValue;742 for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumMidBits); i++)743 p->mid[i] = kProbInitValue;744 for (i = 0; i < kLenNumHighSymbols; i++)745 p->high[i] = kProbInitValue;746 }748 static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState)749 {750 if (symbol < kLenNumLowSymbols)751 {752 RangeEnc_EncodeBit(rc, &p->choice, 0);753 RcTree_Encode(rc, p->low + (posState << kLenNumLowBits), kLenNumLowBits, symbol);754 }755 else756 {757 RangeEnc_EncodeBit(rc, &p->choice, 1);758 if (symbol < kLenNumLowSymbols + kLenNumMidSymbols)759 {760 RangeEnc_EncodeBit(rc, &p->choice2, 0);761 RcTree_Encode(rc, p->mid + (posState << kLenNumMidBits), kLenNumMidBits, symbol - kLenNumLowSymbols);762 }763 else764 {765 RangeEnc_EncodeBit(rc, &p->choice2, 1);766 RcTree_Encode(rc, p->high, kLenNumHighBits, symbol - kLenNumLowSymbols - kLenNumMidSymbols);767 }768 }769 }771 static void LenEnc_SetPrices(CLenEnc *p, UInt32 posState, UInt32 numSymbols, UInt32 *prices, UInt32 *ProbPrices)772 {773 UInt32 a0 = GET_PRICE_0a(p->choice);774 UInt32 a1 = GET_PRICE_1a(p->choice);775 UInt32 b0 = a1 + GET_PRICE_0a(p->choice2);776 UInt32 b1 = a1 + GET_PRICE_1a(p->choice2);777 UInt32 i = 0;778 for (i = 0; i < kLenNumLowSymbols; i++)779 {780 if (i >= numSymbols)781 return;782 prices[i] = a0 + RcTree_GetPrice(p->low + (posState << kLenNumLowBits), kLenNumLowBits, i, ProbPrices);783 }784 for (; i < kLenNumLowSymbols + kLenNumMidSymbols; i++)785 {786 if (i >= numSymbols)787 return;788 prices[i] = b0 + RcTree_GetPrice(p->mid + (posState << kLenNumMidBits), kLenNumMidBits, i - kLenNumLowSymbols, ProbPrices);789 }790 for (; i < numSymbols; i++)791 prices[i] = b1 + RcTree_GetPrice(p->high, kLenNumHighBits, i - kLenNumLowSymbols - kLenNumMidSymbols, ProbPrices);792 }794 static void MY_FAST_CALL LenPriceEnc_UpdateTable(CLenPriceEnc *p, UInt32 posState, UInt32 *ProbPrices)795 {796 LenEnc_SetPrices(&p->p, posState, p->tableSize, p->prices[posState], ProbPrices);797 p->counters[posState] = p->tableSize;798 }800 static void LenPriceEnc_UpdateTables(CLenPriceEnc *p, UInt32 numPosStates, UInt32 *ProbPrices)801 {802 UInt32 posState;803 for (posState = 0; posState < numPosStates; posState++)804 LenPriceEnc_UpdateTable(p, posState, ProbPrices);805 }807 static void LenEnc_Encode2(CLenPriceEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState, Bool updatePrice, UInt32 *ProbPrices)808 {809 LenEnc_Encode(&p->p, rc, symbol, posState);810 if (updatePrice)811 if (--p->counters[posState] == 0)812 LenPriceEnc_UpdateTable(p, posState, ProbPrices);813 }818 static void MovePos(CLzmaEnc *p, UInt32 num)819 {820 #ifdef SHOW_STAT821 ttt += num;822 printf("\n MovePos %d", num);823 #endif824 if (num != 0)825 {826 p->additionalOffset += num;827 p->matchFinder.Skip(p->matchFinderObj, num);828 }829 }831 static UInt32 ReadMatchDistances(CLzmaEnc *p, UInt32 *numDistancePairsRes)832 {833 UInt32 lenRes = 0, numPairs;834 p->numAvail = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);835 numPairs = p->matchFinder.GetMatches(p->matchFinderObj, p->matches);836 #ifdef SHOW_STAT837 printf("\n i = %d numPairs = %d ", ttt, numPairs / 2);838 ttt++;839 {840 UInt32 i;841 for (i = 0; i < numPairs; i += 2)842 printf("%2d %6d | ", p->matches[i], p->matches[i + 1]);843 }844 #endif845 if (numPairs > 0)846 {847 lenRes = p->matches[numPairs - 2];848 if (lenRes == p->numFastBytes)849 {850 const Byte *pby = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;851 UInt32 distance = p->matches[numPairs - 1] + 1;852 UInt32 numAvail = p->numAvail;853 if (numAvail > LZMA_MATCH_LEN_MAX)854 numAvail = LZMA_MATCH_LEN_MAX;855 {856 const Byte *pby2 = pby - distance;857 for (; lenRes < numAvail && pby[lenRes] == pby2[lenRes]; lenRes++);858 }859 }860 }861 p->additionalOffset++;862 *numDistancePairsRes = numPairs;863 return lenRes;864 }867 #define MakeAsChar(p) (p)->backPrev = (UInt32)(-1); (p)->prev1IsChar = False;868 #define MakeAsShortRep(p) (p)->backPrev = 0; (p)->prev1IsChar = False;869 #define IsShortRep(p) ((p)->backPrev == 0)871 static UInt32 GetRepLen1Price(CLzmaEnc *p, UInt32 state, UInt32 posState)872 {873 return874 GET_PRICE_0(p->isRepG0[state]) +875 GET_PRICE_0(p->isRep0Long[state][posState]);876 }878 static UInt32 GetPureRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 state, UInt32 posState)879 {880 UInt32 price;881 if (repIndex == 0)882 {883 price = GET_PRICE_0(p->isRepG0[state]);884 price += GET_PRICE_1(p->isRep0Long[state][posState]);885 }886 else887 {888 price = GET_PRICE_1(p->isRepG0[state]);889 if (repIndex == 1)890 price += GET_PRICE_0(p->isRepG1[state]);891 else892 {893 price += GET_PRICE_1(p->isRepG1[state]);894 price += GET_PRICE(p->isRepG2[state], repIndex - 2);895 }896 }897 return price;898 }900 static UInt32 GetRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 len, UInt32 state, UInt32 posState)901 {902 return p->repLenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN] +903 GetPureRepPrice(p, repIndex, state, posState);904 }906 static UInt32 Backward(CLzmaEnc *p, UInt32 *backRes, UInt32 cur)907 {908 UInt32 posMem = p->opt[cur].posPrev;909 UInt32 backMem = p->opt[cur].backPrev;910 p->optimumEndIndex = cur;911 do912 {913 if (p->opt[cur].prev1IsChar)914 {915 MakeAsChar(&p->opt[posMem])916 p->opt[posMem].posPrev = posMem - 1;917 if (p->opt[cur].prev2)918 {919 p->opt[posMem - 1].prev1IsChar = False;920 p->opt[posMem - 1].posPrev = p->opt[cur].posPrev2;921 p->opt[posMem - 1].backPrev = p->opt[cur].backPrev2;922 }923 }924 {925 UInt32 posPrev = posMem;926 UInt32 backCur = backMem;928 backMem = p->opt[posPrev].backPrev;929 posMem = p->opt[posPrev].posPrev;931 p->opt[posPrev].backPrev = backCur;932 p->opt[posPrev].posPrev = cur;933 cur = posPrev;934 }935 }936 while (cur != 0);937 *backRes = p->opt[0].backPrev;938 p->optimumCurrentIndex = p->opt[0].posPrev;939 return p->optimumCurrentIndex;940 }942 #define LIT_PROBS(pos, prevByte) (p->litProbs + ((((pos) & p->lpMask) << p->lc) + ((prevByte) >> (8 - p->lc))) * 0x300)944 static UInt32 GetOptimum(CLzmaEnc *p, UInt32 position, UInt32 *backRes)945 {946 UInt32 numAvail, mainLen, numPairs, repMaxIndex, i, posState, lenEnd, len, cur;947 UInt32 matchPrice, repMatchPrice, normalMatchPrice;948 UInt32 reps[LZMA_NUM_REPS], repLens[LZMA_NUM_REPS];949 UInt32 *matches;950 const Byte *data;951 Byte curByte, matchByte;952 if (p->optimumEndIndex != p->optimumCurrentIndex)953 {954 const COptimal *opt = &p->opt[p->optimumCurrentIndex];955 UInt32 lenRes = opt->posPrev - p->optimumCurrentIndex;956 *backRes = opt->backPrev;957 p->optimumCurrentIndex = opt->posPrev;958 return lenRes;959 }960 p->optimumCurrentIndex = p->optimumEndIndex = 0;962 if (p->additionalOffset == 0)963 mainLen = ReadMatchDistances(p, &numPairs);964 else965 {966 mainLen = p->longestMatchLength;967 numPairs = p->numPairs;968 }970 numAvail = p->numAvail;971 if (numAvail < 2)972 {973 *backRes = (UInt32)(-1);974 return 1;975 }976 if (numAvail > LZMA_MATCH_LEN_MAX)977 numAvail = LZMA_MATCH_LEN_MAX;979 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;980 repMaxIndex = 0;981 for (i = 0; i < LZMA_NUM_REPS; i++)982 {983 UInt32 lenTest;984 const Byte *data2;985 reps[i] = p->reps[i];986 data2 = data - (reps[i] + 1);987 if (data[0] != data2[0] || data[1] != data2[1])988 {989 repLens[i] = 0;990 continue;991 }992 for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++);993 repLens[i] = lenTest;994 if (lenTest > repLens[repMaxIndex])995 repMaxIndex = i;996 }997 if (repLens[repMaxIndex] >= p->numFastBytes)998 {999 UInt32 lenRes;1000 *backRes = repMaxIndex;1001 lenRes = repLens[repMaxIndex];1002 MovePos(p, lenRes - 1);1003 return lenRes;1004 }1006 matches = p->matches;1007 if (mainLen >= p->numFastBytes)1008 {1009 *backRes = matches[numPairs - 1] + LZMA_NUM_REPS;1010 MovePos(p, mainLen - 1);1011 return mainLen;1012 }1013 curByte = *data;1014 matchByte = *(data - (reps[0] + 1));1016 if (mainLen < 2 && curByte != matchByte && repLens[repMaxIndex] < 2)1017 {1018 *backRes = (UInt32)-1;1019 return 1;1020 }1022 p->opt[0].state = (CState)p->state;1024 posState = (position & p->pbMask);1026 {1027 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));1028 p->opt[1].price = GET_PRICE_0(p->isMatch[p->state][posState]) +1029 (!IsCharState(p->state) ?1030 LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) :1031 LitEnc_GetPrice(probs, curByte, p->ProbPrices));1032 }1034 MakeAsChar(&p->opt[1]);1036 matchPrice = GET_PRICE_1(p->isMatch[p->state][posState]);1037 repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[p->state]);1039 if (matchByte == curByte)1040 {1041 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, p->state, posState);1042 if (shortRepPrice < p->opt[1].price)1043 {1044 p->opt[1].price = shortRepPrice;1045 MakeAsShortRep(&p->opt[1]);1046 }1047 }1048 lenEnd = ((mainLen >= repLens[repMaxIndex]) ? mainLen : repLens[repMaxIndex]);1050 if (lenEnd < 2)1051 {1052 *backRes = p->opt[1].backPrev;1053 return 1;1054 }1056 p->opt[1].posPrev = 0;1057 for (i = 0; i < LZMA_NUM_REPS; i++)1058 p->opt[0].backs[i] = reps[i];1060 len = lenEnd;1061 do1062 p->opt[len--].price = kInfinityPrice;1063 while (len >= 2);1065 for (i = 0; i < LZMA_NUM_REPS; i++)1066 {1067 UInt32 repLen = repLens[i];1068 UInt32 price;1069 if (repLen < 2)1070 continue;1071 price = repMatchPrice + GetPureRepPrice(p, i, p->state, posState);1072 do1073 {1074 UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][repLen - 2];1075 COptimal *opt = &p->opt[repLen];1076 if (curAndLenPrice < opt->price)1077 {1078 opt->price = curAndLenPrice;1079 opt->posPrev = 0;1080 opt->backPrev = i;1081 opt->prev1IsChar = False;1082 }1083 }1084 while (--repLen >= 2);1085 }1087 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[p->state]);1089 len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2);1090 if (len <= mainLen)1091 {1092 UInt32 offs = 0;1093 while (len > matches[offs])1094 offs += 2;1095 for (; ; len++)1096 {1097 COptimal *opt;1098 UInt32 distance = matches[offs + 1];1100 UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN];1101 UInt32 lenToPosState = GetLenToPosState(len);1102 if (distance < kNumFullDistances)1103 curAndLenPrice += p->distancesPrices[lenToPosState][distance];1104 else1105 {1106 UInt32 slot;1107 GetPosSlot2(distance, slot);1108 curAndLenPrice += p->alignPrices[distance & kAlignMask] + p->posSlotPrices[lenToPosState][slot];1109 }1110 opt = &p->opt[len];1111 if (curAndLenPrice < opt->price)1112 {1113 opt->price = curAndLenPrice;1114 opt->posPrev = 0;1115 opt->backPrev = distance + LZMA_NUM_REPS;1116 opt->prev1IsChar = False;1117 }1118 if (len == matches[offs])1119 {1120 offs += 2;1121 if (offs == numPairs)1122 break;1123 }1124 }1125 }1127 cur = 0;1129 #ifdef SHOW_STAT21130 if (position >= 0)1131 {1132 unsigned i;1133 printf("\n pos = %4X", position);1134 for (i = cur; i <= lenEnd; i++)1135 printf("\nprice[%4X] = %d", position - cur + i, p->opt[i].price);1136 }1137 #endif1139 for (;;)1140 {1141 UInt32 numAvailFull, newLen, numPairs, posPrev, state, posState, startLen;1142 UInt32 curPrice, curAnd1Price, matchPrice, repMatchPrice;1143 Bool nextIsChar;1144 Byte curByte, matchByte;1145 const Byte *data;1146 COptimal *curOpt;1147 COptimal *nextOpt;1149 cur++;1150 if (cur == lenEnd)1151 return Backward(p, backRes, cur);1153 newLen = ReadMatchDistances(p, &numPairs);1154 if (newLen >= p->numFastBytes)1155 {1156 p->numPairs = numPairs;1157 p->longestMatchLength = newLen;1158 return Backward(p, backRes, cur);1159 }1160 position++;1161 curOpt = &p->opt[cur];1162 posPrev = curOpt->posPrev;1163 if (curOpt->prev1IsChar)1164 {1165 posPrev--;1166 if (curOpt->prev2)1167 {1168 state = p->opt[curOpt->posPrev2].state;1169 if (curOpt->backPrev2 < LZMA_NUM_REPS)1170 state = kRepNextStates[state];1171 else1172 state = kMatchNextStates[state];1173 }1174 else1175 state = p->opt[posPrev].state;1176 state = kLiteralNextStates[state];1177 }1178 else1179 state = p->opt[posPrev].state;1180 if (posPrev == cur - 1)1181 {1182 if (IsShortRep(curOpt))1183 state = kShortRepNextStates[state];1184 else1185 state = kLiteralNextStates[state];1186 }1187 else1188 {1189 UInt32 pos;1190 const COptimal *prevOpt;1191 if (curOpt->prev1IsChar && curOpt->prev2)1192 {1193 posPrev = curOpt->posPrev2;1194 pos = curOpt->backPrev2;1195 state = kRepNextStates[state];1196 }1197 else1198 {1199 pos = curOpt->backPrev;1200 if (pos < LZMA_NUM_REPS)1201 state = kRepNextStates[state];1202 else1203 state = kMatchNextStates[state];1204 }1205 prevOpt = &p->opt[posPrev];1206 if (pos < LZMA_NUM_REPS)1207 {1208 UInt32 i;1209 reps[0] = prevOpt->backs[pos];1210 for (i = 1; i <= pos; i++)1211 reps[i] = prevOpt->backs[i - 1];1212 for (; i < LZMA_NUM_REPS; i++)1213 reps[i] = prevOpt->backs[i];1214 }1215 else1216 {1217 UInt32 i;1218 reps[0] = (pos - LZMA_NUM_REPS);1219 for (i = 1; i < LZMA_NUM_REPS; i++)1220 reps[i] = prevOpt->backs[i - 1];1221 }1222 }1223 curOpt->state = (CState)state;1225 curOpt->backs[0] = reps[0];1226 curOpt->backs[1] = reps[1];1227 curOpt->backs[2] = reps[2];1228 curOpt->backs[3] = reps[3];1230 curPrice = curOpt->price;1231 nextIsChar = False;1232 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;1233 curByte = *data;1234 matchByte = *(data - (reps[0] + 1));1236 posState = (position & p->pbMask);1238 curAnd1Price = curPrice + GET_PRICE_0(p->isMatch[state][posState]);1239 {1240 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));1241 curAnd1Price +=1242 (!IsCharState(state) ?1243 LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) :1244 LitEnc_GetPrice(probs, curByte, p->ProbPrices));1245 }1247 nextOpt = &p->opt[cur + 1];1249 if (curAnd1Price < nextOpt->price)1250 {1251 nextOpt->price = curAnd1Price;1252 nextOpt->posPrev = cur;1253 MakeAsChar(nextOpt);1254 nextIsChar = True;1255 }1257 matchPrice = curPrice + GET_PRICE_1(p->isMatch[state][posState]);1258 repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[state]);1260 if (matchByte == curByte && !(nextOpt->posPrev < cur && nextOpt->backPrev == 0))1261 {1262 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, state, posState);1263 if (shortRepPrice <= nextOpt->price)1264 {1265 nextOpt->price = shortRepPrice;1266 nextOpt->posPrev = cur;1267 MakeAsShortRep(nextOpt);1268 nextIsChar = True;1269 }1270 }1271 numAvailFull = p->numAvail;1272 {1273 UInt32 temp = kNumOpts - 1 - cur;1274 if (temp < numAvailFull)1275 numAvailFull = temp;1276 }1278 if (numAvailFull < 2)1279 continue;1280 numAvail = (numAvailFull <= p->numFastBytes ? numAvailFull : p->numFastBytes);1282 if (!nextIsChar && matchByte != curByte) /* speed optimization */1283 {1284 /* try Literal + rep0 */1285 UInt32 temp;1286 UInt32 lenTest2;1287 const Byte *data2 = data - (reps[0] + 1);1288 UInt32 limit = p->numFastBytes + 1;1289 if (limit > numAvailFull)1290 limit = numAvailFull;1292 for (temp = 1; temp < limit && data[temp] == data2[temp]; temp++);1293 lenTest2 = temp - 1;1294 if (lenTest2 >= 2)1295 {1296 UInt32 state2 = kLiteralNextStates[state];1297 UInt32 posStateNext = (position + 1) & p->pbMask;1298 UInt32 nextRepMatchPrice = curAnd1Price +1299 GET_PRICE_1(p->isMatch[state2][posStateNext]) +1300 GET_PRICE_1(p->isRep[state2]);1301 /* for (; lenTest2 >= 2; lenTest2--) */1302 {1303 UInt32 curAndLenPrice;1304 COptimal *opt;1305 UInt32 offset = cur + 1 + lenTest2;1306 while (lenEnd < offset)1307 p->opt[++lenEnd].price = kInfinityPrice;1308 curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);1309 opt = &p->opt[offset];1310 if (curAndLenPrice < opt->price)1311 {1312 opt->price = curAndLenPrice;1313 opt->posPrev = cur + 1;1314 opt->backPrev = 0;1315 opt->prev1IsChar = True;1316 opt->prev2 = False;1317 }1318 }1319 }1320 }1322 startLen = 2; /* speed optimization */1323 {1324 UInt32 repIndex;1325 for (repIndex = 0; repIndex < LZMA_NUM_REPS; repIndex++)1326 {1327 UInt32 lenTest;1328 UInt32 lenTestTemp;1329 UInt32 price;1330 const Byte *data2 = data - (reps[repIndex] + 1);1331 if (data[0] != data2[0] || data[1] != data2[1])1332 continue;1333 for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++);1334 while (lenEnd < cur + lenTest)1335 p->opt[++lenEnd].price = kInfinityPrice;1336 lenTestTemp = lenTest;1337 price = repMatchPrice + GetPureRepPrice(p, repIndex, state, posState);1338 do1339 {1340 UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][lenTest - 2];1341 COptimal *opt = &p->opt[cur + lenTest];1342 if (curAndLenPrice < opt->price)1343 {1344 opt->price = curAndLenPrice;1345 opt->posPrev = cur;1346 opt->backPrev = repIndex;1347 opt->prev1IsChar = False;1348 }1349 }1350 while (--lenTest >= 2);1351 lenTest = lenTestTemp;1353 if (repIndex == 0)1354 startLen = lenTest + 1;1356 /* if (_maxMode) */1357 {1358 UInt32 lenTest2 = lenTest + 1;1359 UInt32 limit = lenTest2 + p->numFastBytes;1360 UInt32 nextRepMatchPrice;1361 if (limit > numAvailFull)1362 limit = numAvailFull;1363 for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++);1364 lenTest2 -= lenTest + 1;1365 if (lenTest2 >= 2)1366 {1367 UInt32 state2 = kRepNextStates[state];1368 UInt32 posStateNext = (position + lenTest) & p->pbMask;1369 UInt32 curAndLenCharPrice =1370 price + p->repLenEnc.prices[posState][lenTest - 2] +1371 GET_PRICE_0(p->isMatch[state2][posStateNext]) +1372 LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTest - 1]),1373 data[lenTest], data2[lenTest], p->ProbPrices);1374 state2 = kLiteralNextStates[state2];1375 posStateNext = (position + lenTest + 1) & p->pbMask;1376 nextRepMatchPrice = curAndLenCharPrice +1377 GET_PRICE_1(p->isMatch[state2][posStateNext]) +1378 GET_PRICE_1(p->isRep[state2]);1380 /* for (; lenTest2 >= 2; lenTest2--) */1381 {1382 UInt32 curAndLenPrice;1383 COptimal *opt;1384 UInt32 offset = cur + lenTest + 1 + lenTest2;1385 while (lenEnd < offset)1386 p->opt[++lenEnd].price = kInfinityPrice;1387 curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);1388 opt = &p->opt[offset];1389 if (curAndLenPrice < opt->price)1390 {1391 opt->price = curAndLenPrice;1392 opt->posPrev = cur + lenTest + 1;1393 opt->backPrev = 0;1394 opt->prev1IsChar = True;1395 opt->prev2 = True;1396 opt->posPrev2 = cur;1397 opt->backPrev2 = repIndex;1398 }1399 }1400 }1401 }1402 }1403 }1404 /* for (UInt32 lenTest = 2; lenTest <= newLen; lenTest++) */1405 if (newLen > numAvail)1406 {1407 newLen = numAvail;1408 for (numPairs = 0; newLen > matches[numPairs]; numPairs += 2);1409 matches[numPairs] = newLen;1410 numPairs += 2;1411 }1412 if (newLen >= startLen)1413 {1414 UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[state]);1415 UInt32 offs, curBack, posSlot;1416 UInt32 lenTest;1417 while (lenEnd < cur + newLen)1418 p->opt[++lenEnd].price = kInfinityPrice;1420 offs = 0;1421 while (startLen > matches[offs])1422 offs += 2;1423 curBack = matches[offs + 1];1424 GetPosSlot2(curBack, posSlot);1425 for (lenTest = /*2*/ startLen; ; lenTest++)1426 {1427 UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][lenTest - LZMA_MATCH_LEN_MIN];1428 UInt32 lenToPosState = GetLenToPosState(lenTest);1429 COptimal *opt;1430 if (curBack < kNumFullDistances)1431 curAndLenPrice += p->distancesPrices[lenToPosState][curBack];1432 else1433 curAndLenPrice += p->posSlotPrices[lenToPosState][posSlot] + p->alignPrices[curBack & kAlignMask];1435 opt = &p->opt[cur + lenTest];1436 if (curAndLenPrice < opt->price)1437 {1438 opt->price = curAndLenPrice;1439 opt->posPrev = cur;1440 opt->backPrev = curBack + LZMA_NUM_REPS;1441 opt->prev1IsChar = False;1442 }1444 if (/*_maxMode && */lenTest == matches[offs])1445 {1446 /* Try Match + Literal + Rep0 */1447 const Byte *data2 = data - (curBack + 1);1448 UInt32 lenTest2 = lenTest + 1;1449 UInt32 limit = lenTest2 + p->numFastBytes;1450 UInt32 nextRepMatchPrice;1451 if (limit > numAvailFull)1452 limit = numAvailFull;1453 for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++);1454 lenTest2 -= lenTest + 1;1455 if (lenTest2 >= 2)1456 {1457 UInt32 state2 = kMatchNextStates[state];1458 UInt32 posStateNext = (position + lenTest) & p->pbMask;1459 UInt32 curAndLenCharPrice = curAndLenPrice +1460 GET_PRICE_0(p->isMatch[state2][posStateNext]) +1461 LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTest - 1]),1462 data[lenTest], data2[lenTest], p->ProbPrices);1463 state2 = kLiteralNextStates[state2];1464 posStateNext = (posStateNext + 1) & p->pbMask;1465 nextRepMatchPrice = curAndLenCharPrice +1466 GET_PRICE_1(p->isMatch[state2][posStateNext]) +1467 GET_PRICE_1(p->isRep[state2]);1469 /* for (; lenTest2 >= 2; lenTest2--) */1470 {1471 UInt32 offset = cur + lenTest + 1 + lenTest2;1472 UInt32 curAndLenPrice;1473 COptimal *opt;1474 while (lenEnd < offset)1475 p->opt[++lenEnd].price = kInfinityPrice;1476 curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);1477 opt = &p->opt[offset];1478 if (curAndLenPrice < opt->price)1479 {1480 opt->price = curAndLenPrice;1481 opt->posPrev = cur + lenTest + 1;1482 opt->backPrev = 0;1483 opt->prev1IsChar = True;1484 opt->prev2 = True;1485 opt->posPrev2 = cur;1486 opt->backPrev2 = curBack + LZMA_NUM_REPS;1487 }1488 }1489 }1490 offs += 2;1491 if (offs == numPairs)1492 break;1493 curBack = matches[offs + 1];1494 if (curBack >= kNumFullDistances)1495 GetPosSlot2(curBack, posSlot);1496 }1497 }1498 }1499 }1500 }1502 #define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist))1504 static UInt32 GetOptimumFast(CLzmaEnc *p, UInt32 *backRes)1505 {1506 UInt32 numAvail, mainLen, mainDist, numPairs, repIndex, repLen, i;1507 const Byte *data;1508 const UInt32 *matches;1510 if (p->additionalOffset == 0)1511 mainLen = ReadMatchDistances(p, &numPairs);1512 else1513 {1514 mainLen = p->longestMatchLength;1515 numPairs = p->numPairs;1516 }1518 numAvail = p->numAvail;1519 *backRes = (UInt32)-1;1520 if (numAvail < 2)1521 return 1;1522 if (numAvail > LZMA_MATCH_LEN_MAX)1523 numAvail = LZMA_MATCH_LEN_MAX;1524 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;1526 repLen = repIndex = 0;1527 for (i = 0; i < LZMA_NUM_REPS; i++)1528 {1529 UInt32 len;1530 const Byte *data2 = data - (p->reps[i] + 1);1531 if (data[0] != data2[0] || data[1] != data2[1])1532 continue;1533 for (len = 2; len < numAvail && data[len] == data2[len]; len++);1534 if (len >= p->numFastBytes)1535 {1536 *backRes = i;1537 MovePos(p, len - 1);1538 return len;1539 }1540 if (len > repLen)1541 {1542 repIndex = i;1543 repLen = len;1544 }1545 }1547 matches = p->matches;1548 if (mainLen >= p->numFastBytes)1549 {1550 *backRes = matches[numPairs - 1] + LZMA_NUM_REPS;1551 MovePos(p, mainLen - 1);1552 return mainLen;1553 }1555 mainDist = 0; /* for GCC */1556 if (mainLen >= 2)1557 {1558 mainDist = matches[numPairs - 1];1559 while (numPairs > 2 && mainLen == matches[numPairs - 4] + 1)1560 {1561 if (!ChangePair(matches[numPairs - 3], mainDist))1562 break;1563 numPairs -= 2;1564 mainLen = matches[numPairs - 2];1565 mainDist = matches[numPairs - 1];1566 }1567 if (mainLen == 2 && mainDist >= 0x80)1568 mainLen = 1;1569 }1571 if (repLen >= 2 && (1572 (repLen + 1 >= mainLen) ||1573 (repLen + 2 >= mainLen && mainDist >= (1 << 9)) ||1574 (repLen + 3 >= mainLen && mainDist >= (1 << 15))))1575 {1576 *backRes = repIndex;1577 MovePos(p, repLen - 1);1578 return repLen;1579 }1581 if (mainLen < 2 || numAvail <= 2)1582 return 1;1584 p->longestMatchLength = ReadMatchDistances(p, &p->numPairs);1585 if (p->longestMatchLength >= 2)1586 {1587 UInt32 newDistance = matches[p->numPairs - 1];1588 if ((p->longestMatchLength >= mainLen && newDistance < mainDist) ||1589 (p->longestMatchLength == mainLen + 1 && !ChangePair(mainDist, newDistance)) ||1590 (p->longestMatchLength > mainLen + 1) ||1591 (p->longestMatchLength + 1 >= mainLen && mainLen >= 3 && ChangePair(newDistance, mainDist)))1592 return 1;1593 }1595 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;1596 for (i = 0; i < LZMA_NUM_REPS; i++)1597 {1598 UInt32 len, limit;1599 const Byte *data2 = data - (p->reps[i] + 1);1600 if (data[0] != data2[0] || data[1] != data2[1])1601 continue;1602 limit = mainLen - 1;1603 for (len = 2; len < limit && data[len] == data2[len]; len++);1604 if (len >= limit)1605 return 1;1606 }1607 *backRes = mainDist + LZMA_NUM_REPS;1608 MovePos(p, mainLen - 2);1609 return mainLen;1610 }1612 static void WriteEndMarker(CLzmaEnc *p, UInt32 posState)1613 {1614 UInt32 len;1615 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1);1616 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0);1617 p->state = kMatchNextStates[p->state];1618 len = LZMA_MATCH_LEN_MIN;1619 LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);1620 RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, (1 << kNumPosSlotBits) - 1);1621 RangeEnc_EncodeDirectBits(&p->rc, (((UInt32)1 << 30) - 1) >> kNumAlignBits, 30 - kNumAlignBits);1622 RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, kAlignMask);1623 }1625 static SRes CheckErrors(CLzmaEnc *p)1626 {1627 if (p->result != SZ_OK)1628 return p->result;1629 if (p->rc.res != SZ_OK)1630 p->result = SZ_ERROR_WRITE;1631 if (p->matchFinderBase.result != SZ_OK)1632 p->result = SZ_ERROR_READ;1633 if (p->result != SZ_OK)1634 p->finished = True;1635 return p->result;1636 }1638 static SRes Flush(CLzmaEnc *p, UInt32 nowPos)1639 {1640 /* ReleaseMFStream(); */1641 p->finished = True;1642 if (p->writeEndMark)1643 WriteEndMarker(p, nowPos & p->pbMask);1644 RangeEnc_FlushData(&p->rc);1645 RangeEnc_FlushStream(&p->rc);1646 return CheckErrors(p);1647 }1649 static void FillAlignPrices(CLzmaEnc *p)1650 {1651 UInt32 i;1652 for (i = 0; i < kAlignTableSize; i++)1653 p->alignPrices[i] = RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits, i, p->ProbPrices);1654 p->alignPriceCount = 0;1655 }1657 static void FillDistancesPrices(CLzmaEnc *p)1658 {1659 UInt32 tempPrices[kNumFullDistances];1660 UInt32 i, lenToPosState;1661 for (i = kStartPosModelIndex; i < kNumFullDistances; i++)1662 {1663 UInt32 posSlot = GetPosSlot1(i);1664 UInt32 footerBits = ((posSlot >> 1) - 1);1665 UInt32 base = ((2 | (posSlot & 1)) << footerBits);1666 tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base - posSlot - 1, footerBits, i - base, p->ProbPrices);1667 }1669 for (lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)1670 {1671 UInt32 posSlot;1672 const CLzmaProb *encoder = p->posSlotEncoder[lenToPosState];1673 UInt32 *posSlotPrices = p->posSlotPrices[lenToPosState];1674 for (posSlot = 0; posSlot < p->distTableSize; posSlot++)1675 posSlotPrices[posSlot] = RcTree_GetPrice(encoder, kNumPosSlotBits, posSlot, p->ProbPrices);1676 for (posSlot = kEndPosModelIndex; posSlot < p->distTableSize; posSlot++)1677 posSlotPrices[posSlot] += ((((posSlot >> 1) - 1) - kNumAlignBits) << kNumBitPriceShiftBits);1679 {1680 UInt32 *distancesPrices = p->distancesPrices[lenToPosState];1681 UInt32 i;1682 for (i = 0; i < kStartPosModelIndex; i++)1683 distancesPrices[i] = posSlotPrices[i];1684 for (; i < kNumFullDistances; i++)1685 distancesPrices[i] = posSlotPrices[GetPosSlot1(i)] + tempPrices[i];1686 }1687 }1688 p->matchPriceCount = 0;1689 }1691 void LzmaEnc_Construct(CLzmaEnc *p)1692 {1693 RangeEnc_Construct(&p->rc);1694 MatchFinder_Construct(&p->matchFinderBase);1695 #ifdef COMPRESS_MF_MT1696 MatchFinderMt_Construct(&p->matchFinderMt);1697 p->matchFinderMt.MatchFinder = &p->matchFinderBase;1698 #endif1700 {1701 CLzmaEncProps props;1702 LzmaEncProps_Init(&props);1703 LzmaEnc_SetProps(p, &props);1704 }1706 #ifndef LZMA_LOG_BSR1707 LzmaEnc_FastPosInit(p->g_FastPos);1708 #endif1710 LzmaEnc_InitPriceTables(p->ProbPrices);1711 p->litProbs = 0;1712 p->saveState.litProbs = 0;1713 }1715 CLzmaEncHandle LzmaEnc_Create(ISzAlloc *alloc)1716 {1717 void *p;1718 p = alloc->Alloc(alloc, sizeof(CLzmaEnc));1719 if (p != 0)1720 LzmaEnc_Construct((CLzmaEnc *)p);1721 return p;1722 }1724 void LzmaEnc_FreeLits(CLzmaEnc *p, ISzAlloc *alloc)1725 {1726 alloc->Free(alloc, p->litProbs);1727 alloc->Free(alloc, p->saveState.litProbs);1728 p->litProbs = 0;1729 p->saveState.litProbs = 0;1730 }1732 void LzmaEnc_Destruct(CLzmaEnc *p, ISzAlloc *alloc, ISzAlloc *allocBig)1733 {1734 #ifdef COMPRESS_MF_MT1735 MatchFinderMt_Destruct(&p->matchFinderMt, allocBig);1736 #endif1737 MatchFinder_Free(&p->matchFinderBase, allocBig);1738 LzmaEnc_FreeLits(p, alloc);1739 RangeEnc_Free(&p->rc, alloc);1740 }1742 void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAlloc *alloc, ISzAlloc *allocBig)1743 {1744 LzmaEnc_Destruct((CLzmaEnc *)p, alloc, allocBig);1745 alloc->Free(alloc, p);1746 }1748 static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, Bool useLimits, UInt32 maxPackSize, UInt32 maxUnpackSize)1749 {1750 UInt32 nowPos32, startPos32;1751 if (p->inStream != 0)1752 {1753 p->matchFinderBase.stream = p->inStream;1754 p->matchFinder.Init(p->matchFinderObj);1755 p->inStream = 0;1756 }1758 if (p->finished)1759 return p->result;1760 RINOK(CheckErrors(p));1762 nowPos32 = (UInt32)p->nowPos64;1763 startPos32 = nowPos32;1765 if (p->nowPos64 == 0)1766 {1767 UInt32 numPairs;1768 Byte curByte;1769 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)1770 return Flush(p, nowPos32);1771 ReadMatchDistances(p, &numPairs);1772 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][0], 0);1773 p->state = kLiteralNextStates[p->state];1774 curByte = p->matchFinder.GetIndexByte(p->matchFinderObj, 0 - p->additionalOffset);1775 LitEnc_Encode(&p->rc, p->litProbs, curByte);1776 p->additionalOffset--;1777 nowPos32++;1778 }1780 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) != 0)1781 for (;;)1782 {1783 UInt32 pos, len, posState;1785 if (p->fastMode)1786 len = GetOptimumFast(p, &pos);1787 else1788 len = GetOptimum(p, nowPos32, &pos);1790 #ifdef SHOW_STAT21791 printf("\n pos = %4X, len = %d pos = %d", nowPos32, len, pos);1792 #endif1794 posState = nowPos32 & p->pbMask;1795 if (len == 1 && pos == (UInt32)-1)1796 {1797 Byte curByte;1798 CLzmaProb *probs;1799 const Byte *data;1801 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 0);1802 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;1803 curByte = *data;1804 probs = LIT_PROBS(nowPos32, *(data - 1));1805 if (IsCharState(p->state))1806 LitEnc_Encode(&p->rc, probs, curByte);1807 else1808 LitEnc_EncodeMatched(&p->rc, probs, curByte, *(data - p->reps[0] - 1));1809 p->state = kLiteralNextStates[p->state];1810 }1811 else1812 {1813 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1);1814 if (pos < LZMA_NUM_REPS)1815 {1816 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 1);1817 if (pos == 0)1818 {1819 RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 0);1820 RangeEnc_EncodeBit(&p->rc, &p->isRep0Long[p->state][posState], ((len == 1) ? 0 : 1));1821 }1822 else1823 {1824 UInt32 distance = p->reps[pos];1825 RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 1);1826 if (pos == 1)1827 RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 0);1828 else1829 {1830 RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 1);1831 RangeEnc_EncodeBit(&p->rc, &p->isRepG2[p->state], pos - 2);1832 if (pos == 3)1833 p->reps[3] = p->reps[2];1834 p->reps[2] = p->reps[1];1835 }1836 p->reps[1] = p->reps[0];1837 p->reps[0] = distance;1838 }1839 if (len == 1)1840 p->state = kShortRepNextStates[p->state];1841 else1842 {1843 LenEnc_Encode2(&p->repLenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);1844 p->state = kRepNextStates[p->state];1845 }1846 }1847 else1848 {1849 UInt32 posSlot;1850 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0);1851 p->state = kMatchNextStates[p->state];1852 LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);1853 pos -= LZMA_NUM_REPS;1854 GetPosSlot(pos, posSlot);1855 RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, posSlot);1857 if (posSlot >= kStartPosModelIndex)1858 {1859 UInt32 footerBits = ((posSlot >> 1) - 1);1860 UInt32 base = ((2 | (posSlot & 1)) << footerBits);1861 UInt32 posReduced = pos - base;1863 if (posSlot < kEndPosModelIndex)1864 RcTree_ReverseEncode(&p->rc, p->posEncoders + base - posSlot - 1, footerBits, posReduced);1865 else1866 {1867 RangeEnc_EncodeDirectBits(&p->rc, posReduced >> kNumAlignBits, footerBits - kNumAlignBits);1868 RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, posReduced & kAlignMask);1869 p->alignPriceCount++;1870 }1871 }1872 p->reps[3] = p->reps[2];1873 p->reps[2] = p->reps[1];1874 p->reps[1] = p->reps[0];1875 p->reps[0] = pos;1876 p->matchPriceCount++;1877 }1878 }1879 p->additionalOffset -= len;1880 nowPos32 += len;1881 if (p->additionalOffset == 0)1882 {1883 UInt32 processed;1884 if (!p->fastMode)1885 {1886 if (p->matchPriceCount >= (1 << 7))1887 FillDistancesPrices(p);1888 if (p->alignPriceCount >= kAlignTableSize)1889 FillAlignPrices(p);1890 }1891 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)1892 break;1893 processed = nowPos32 - startPos32;1894 if (useLimits)1895 {1896 if (processed + kNumOpts + 300 >= maxUnpackSize ||1897 RangeEnc_GetProcessed(&p->rc) + kNumOpts * 2 >= maxPackSize)1898 break;1899 }1900 else if (processed >= (1 << 15))1901 {1902 p->nowPos64 += nowPos32 - startPos32;1903 return CheckErrors(p);1904 }1905 }1906 }1907 p->nowPos64 += nowPos32 - startPos32;1908 return Flush(p, nowPos32);1909 }1911 #define kBigHashDicLimit ((UInt32)1 << 24)1913 static SRes LzmaEnc_Alloc(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)1914 {1915 UInt32 beforeSize = kNumOpts;1916 Bool btMode;1917 if (!RangeEnc_Alloc(&p->rc, alloc))1918 return SZ_ERROR_MEM;1919 btMode = (p->matchFinderBase.btMode != 0);1920 #ifdef COMPRESS_MF_MT1921 p->mtMode = (p->multiThread && !p->fastMode && btMode);1922 #endif1924 {1925 unsigned lclp = p->lc + p->lp;1926 if (p->litProbs == 0 || p->saveState.litProbs == 0 || p->lclp != lclp)1927 {1928 LzmaEnc_FreeLits(p, alloc);1929 p->litProbs = (CLzmaProb *)alloc->Alloc(alloc, (0x300 << lclp) * sizeof(CLzmaProb));1930 p->saveState.litProbs = (CLzmaProb *)alloc->Alloc(alloc, (0x300 << lclp) * sizeof(CLzmaProb));1931 if (p->litProbs == 0 || p->saveState.litProbs == 0)1932 {1933 LzmaEnc_FreeLits(p, alloc);1934 return SZ_ERROR_MEM;1935 }1936 p->lclp = lclp;1937 }1938 }1940 p->matchFinderBase.bigHash = (p->dictSize > kBigHashDicLimit);1942 if (beforeSize + p->dictSize < keepWindowSize)1943 beforeSize = keepWindowSize - p->dictSize;1945 #ifdef COMPRESS_MF_MT1946 if (p->mtMode)1947 {1948 RINOK(MatchFinderMt_Create(&p->matchFinderMt, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig));1949 p->matchFinderObj = &p->matchFinderMt;1950 MatchFinderMt_CreateVTable(&p->matchFinderMt, &p->matchFinder);1951 }1952 else1953 #endif1954 {1955 if (!MatchFinder_Create(&p->matchFinderBase, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig))1956 return SZ_ERROR_MEM;1957 p->matchFinderObj = &p->matchFinderBase;1958 MatchFinder_CreateVTable(&p->matchFinderBase, &p->matchFinder);1959 }1960 return SZ_OK;1961 }1963 void LzmaEnc_Init(CLzmaEnc *p)1964 {1965 UInt32 i;1966 p->state = 0;1967 for (i = 0 ; i < LZMA_NUM_REPS; i++)1968 p->reps[i] = 0;1970 RangeEnc_Init(&p->rc);1973 for (i = 0; i < kNumStates; i++)1974 {1975 UInt32 j;1976 for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++)1977 {1978 p->isMatch[i][j] = kProbInitValue;1979 p->isRep0Long[i][j] = kProbInitValue;1980 }1981 p->isRep[i] = kProbInitValue;1982 p->isRepG0[i] = kProbInitValue;1983 p->isRepG1[i] = kProbInitValue;1984 p->isRepG2[i] = kProbInitValue;1985 }1987 {1988 UInt32 num = 0x300 << (p->lp + p->lc);1989 for (i = 0; i < num; i++)1990 p->litProbs[i] = kProbInitValue;1991 }1993 {1994 for (i = 0; i < kNumLenToPosStates; i++)1995 {1996 CLzmaProb *probs = p->posSlotEncoder[i];1997 UInt32 j;1998 for (j = 0; j < (1 << kNumPosSlotBits); j++)1999 probs[j] = kProbInitValue;2000 }2001 }2002 {2003 for (i = 0; i < kNumFullDistances - kEndPosModelIndex; i++)2004 p->posEncoders[i] = kProbInitValue;2005 }2007 LenEnc_Init(&p->lenEnc.p);2008 LenEnc_Init(&p->repLenEnc.p);2010 for (i = 0; i < (1 << kNumAlignBits); i++)2011 p->posAlignEncoder[i] = kProbInitValue;2013 p->optimumEndIndex = 0;2014 p->optimumCurrentIndex = 0;2015 p->additionalOffset = 0;2017 p->pbMask = (1 << p->pb) - 1;2018 p->lpMask = (1 << p->lp) - 1;2019 }2021 void LzmaEnc_InitPrices(CLzmaEnc *p)2022 {2023 if (!p->fastMode)2024 {2025 FillDistancesPrices(p);2026 FillAlignPrices(p);2027 }2029 p->lenEnc.tableSize =2030 p->repLenEnc.tableSize =2031 p->numFastBytes + 1 - LZMA_MATCH_LEN_MIN;2032 LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, p->ProbPrices);2033 LenPriceEnc_UpdateTables(&p->repLenEnc, 1 << p->pb, p->ProbPrices);2034 }2036 static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)2037 {2038 UInt32 i;2039 for (i = 0; i < (UInt32)kDicLogSizeMaxCompress; i++)2040 if (p->dictSize <= ((UInt32)1 << i))2041 break;2042 p->distTableSize = i * 2;2044 p->finished = False;2045 p->result = SZ_OK;2046 RINOK(LzmaEnc_Alloc(p, keepWindowSize, alloc, allocBig));2047 LzmaEnc_Init(p);2048 LzmaEnc_InitPrices(p);2049 p->nowPos64 = 0;2050 return SZ_OK;2051 }2053 static SRes LzmaEnc_Prepare(CLzmaEncHandle pp, ISeqInStream *inStream, ISeqOutStream *outStream,2054 ISzAlloc *alloc, ISzAlloc *allocBig)2055 {2056 CLzmaEnc *p = (CLzmaEnc *)pp;2057 p->inStream = inStream;2058 p->rc.outStream = outStream;2059 return LzmaEnc_AllocAndInit(p, 0, alloc, allocBig);2060 }2062 SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle pp,2063 ISeqInStream *inStream, UInt32 keepWindowSize,2064 ISzAlloc *alloc, ISzAlloc *allocBig)2065 {2066 CLzmaEnc *p = (CLzmaEnc *)pp;2067 p->inStream = inStream;2068 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);2069 }2071 static void LzmaEnc_SetInputBuf(CLzmaEnc *p, const Byte *src, SizeT srcLen)2072 {2073 p->seqBufInStream.funcTable.Read = MyRead;2074 p->seqBufInStream.data = src;2075 p->seqBufInStream.rem = srcLen;2076 }2078 SRes LzmaEnc_MemPrepare(CLzmaEncHandle pp, const Byte *src, SizeT srcLen,2079 UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)2080 {2081 CLzmaEnc *p = (CLzmaEnc *)pp;2082 LzmaEnc_SetInputBuf(p, src, srcLen);2083 p->inStream = &p->seqBufInStream.funcTable;2084 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);2085 }2087 void LzmaEnc_Finish(CLzmaEncHandle pp)2088 {2089 #ifdef COMPRESS_MF_MT2090 CLzmaEnc *p = (CLzmaEnc *)pp;2091 if (p->mtMode)2092 MatchFinderMt_ReleaseStream(&p->matchFinderMt);2093 #else2094 pp = pp;2095 #endif2096 }2098 typedef struct _CSeqOutStreamBuf2099 {2100 ISeqOutStream funcTable;2101 Byte *data;2102 SizeT rem;2103 Bool overflow;2104 } CSeqOutStreamBuf;2106 static size_t MyWrite(void *pp, const void *data, size_t size)2107 {2108 CSeqOutStreamBuf *p = (CSeqOutStreamBuf *)pp;2109 if (p->rem < size)2110 {2111 size = p->rem;2112 p->overflow = True;2113 }2114 memcpy(p->data, data, size);2115 p->rem -= size;2116 p->data += size;2117 return size;2118 }2121 UInt32 LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp)2122 {2123 const CLzmaEnc *p = (CLzmaEnc *)pp;2124 return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);2125 }2127 const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle pp)2128 {2129 const CLzmaEnc *p = (CLzmaEnc *)pp;2130 return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;2131 }2133 SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle pp, Bool reInit,2134 Byte *dest, size_t *destLen, UInt32 desiredPackSize, UInt32 *unpackSize)2135 {2136 CLzmaEnc *p = (CLzmaEnc *)pp;2137 UInt64 nowPos64;2138 SRes res;2139 CSeqOutStreamBuf outStream;2141 outStream.funcTable.Write = MyWrite;2142 outStream.data = dest;2143 outStream.rem = *destLen;2144 outStream.overflow = False;2146 p->writeEndMark = False;2147 p->finished = False;2148 p->result = SZ_OK;2150 if (reInit)2151 LzmaEnc_Init(p);2152 LzmaEnc_InitPrices(p);2153 nowPos64 = p->nowPos64;2154 RangeEnc_Init(&p->rc);2155 p->rc.outStream = &outStream.funcTable;2157 res = LzmaEnc_CodeOneBlock(p, True, desiredPackSize, *unpackSize);2159 *unpackSize = (UInt32)(p->nowPos64 - nowPos64);2160 *destLen -= outStream.rem;2161 if (outStream.overflow)2162 return SZ_ERROR_OUTPUT_EOF;2164 return res;2165 }2167 SRes LzmaEnc_Encode(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, ICompressProgress *progress,2168 ISzAlloc *alloc, ISzAlloc *allocBig)2169 {2170 CLzmaEnc *p = (CLzmaEnc *)pp;2171 SRes res = SZ_OK;2173 #ifdef COMPRESS_MF_MT2174 Byte allocaDummy[0x300];2175 int i = 0;2176 for (i = 0; i < 16; i++)2177 allocaDummy[i] = (Byte)i;2178 #endif2180 RINOK(LzmaEnc_Prepare(pp, inStream, outStream, alloc, allocBig));2182 for (;;)2183 {2184 res = LzmaEnc_CodeOneBlock(p, False, 0, 0);2185 if (res != SZ_OK || p->finished != 0)2186 break;2187 if (progress != 0)2188 {2189 res = progress->Progress(progress, p->nowPos64, RangeEnc_GetProcessed(&p->rc));2190 if (res != SZ_OK)2191 {2192 res = SZ_ERROR_PROGRESS;2193 break;2194 }2195 }2196 }2197 LzmaEnc_Finish(pp);2198 return res;2199 }2201 SRes LzmaEnc_WriteProperties(CLzmaEncHandle pp, Byte *props, SizeT *size)2202 {2203 CLzmaEnc *p = (CLzmaEnc *)pp;2204 int i;2205 UInt32 dictSize = p->dictSize;2206 if (*size < LZMA_PROPS_SIZE)2207 return SZ_ERROR_PARAM;2208 *size = LZMA_PROPS_SIZE;2209 props[0] = (Byte)((p->pb * 5 + p->lp) * 9 + p->lc);2211 for (i = 11; i <= 30; i++)2212 {2213 if (dictSize <= ((UInt32)2 << i))2214 {2215 dictSize = (2 << i);2216 break;2217 }2218 if (dictSize <= ((UInt32)3 << i))2219 {2220 dictSize = (3 << i);2221 break;2222 }2223 }2225 for (i = 0; i < 4; i++)2226 props[1 + i] = (Byte)(dictSize >> (8 * i));2227 return SZ_OK;2228 }2230 SRes LzmaEnc_MemEncode(CLzmaEncHandle pp, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,2231 int writeEndMark, ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig)2232 {2233 SRes res;2234 CLzmaEnc *p = (CLzmaEnc *)pp;2236 CSeqOutStreamBuf outStream;2238 LzmaEnc_SetInputBuf(p, src, srcLen);2240 outStream.funcTable.Write = MyWrite;2241 outStream.data = dest;2242 outStream.rem = *destLen;2243 outStream.overflow = False;2245 p->writeEndMark = writeEndMark;2246 res = LzmaEnc_Encode(pp, &outStream.funcTable, &p->seqBufInStream.funcTable,2247 progress, alloc, allocBig);2249 *destLen -= outStream.rem;2250 if (outStream.overflow)2251 return SZ_ERROR_OUTPUT_EOF;2252 return res;2253 }2255 SRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,2256 const CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeEndMark,2257 ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig)2258 {2259 CLzmaEnc *p = (CLzmaEnc *)LzmaEnc_Create(alloc);2260 SRes res;2261 if (p == 0)2262 return SZ_ERROR_MEM;2264 res = LzmaEnc_SetProps(p, props);2265 if (res == SZ_OK)2266 {2267 res = LzmaEnc_WriteProperties(p, propsEncoded, propsSize);2268 if (res == SZ_OK)2269 res = LzmaEnc_MemEncode(p, dest, destLen, src, srcLen,2270 writeEndMark, progress, alloc, allocBig);2271 }2273 LzmaEnc_Destroy(p, alloc, allocBig);2274 return res;2275 }