| OLD | NEW |
|---|
| (Empty) |
| 1 /* LzmaEnc.c -- LZMA Encoder | |
| 2 2010-04-16 : Igor Pavlov : Public domain | |
| 3 in the public domain */ | |
| 4 | |
| 5 #include <string.h> | |
| 6 | |
| 7 /* #define SHOW_STAT */ | |
| 8 /* #define SHOW_STAT2 */ | |
| 9 | |
| 10 #if defined(SHOW_STAT) || defined(SHOW_STAT2) | |
| 11 #include <stdio.h> | |
| 12 #endif | |
| 13 | |
| 14 #include "LzmaEnc.h" | |
| 15 | |
| 16 #include "LzFind.h" | |
| 17 #ifndef _7ZIP_ST | |
| 18 #include "LzFindMt.h" | |
| 19 #endif | |
| 20 | |
| 21 #ifdef SHOW_STAT | |
| 22 static int ttt = 0; | |
| 23 #endif | |
| 24 | |
| 25 #define kBlockSizeMax ((1 << LZMA_NUM_BLOCK_SIZE_BITS) - 1) | |
| 26 | |
| 27 #define kBlockSize (9 << 10) | |
| 28 #define kUnpackBlockSize (1 << 18) | |
| 29 #define kMatchArraySize (1 << 21) | |
| 30 #define kMatchRecordMaxSize ((LZMA_MATCH_LEN_MAX * 2 + 3) * LZMA_MATCH_LEN_MAX) | |
| 31 | |
| 32 #define kNumMaxDirectBits (31) | |
| 33 | |
| 34 #define kNumTopBits 24 | |
| 35 #define kTopValue ((UInt32)1 << kNumTopBits) | |
| 36 | |
| 37 #define kNumBitModelTotalBits 11 | |
| 38 #define kBitModelTotal (1 << kNumBitModelTotalBits) | |
| 39 #define kNumMoveBits 5 | |
| 40 #define kProbInitValue (kBitModelTotal >> 1) | |
| 41 | |
| 42 #define kNumMoveReducingBits 4 | |
| 43 #define kNumBitPriceShiftBits 4 | |
| 44 #define kBitPrice (1 << kNumBitPriceShiftBits) | |
| 45 | |
| 46 void LzmaEncProps_Init(CLzmaEncProps *p) | |
| 47 { | |
| 48 p->level = 5; | |
| 49 p->dictSize = p->mc = 0; | |
| 50 p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->num
Threads = -1; | |
| 51 p->writeEndMark = 0; | |
| 52 } | |
| 53 | |
| 54 void LzmaEncProps_Normalize(CLzmaEncProps *p) | |
| 55 { | |
| 56 int level = p->level; | |
| 57 if (level < 0) level = 5; | |
| 58 p->level = level; | |
| 59 if (p->dictSize == 0) p->dictSize = (level <= 5 ? (1 << (level * 2 + 14)) : (l
evel == 6 ? (1 << 25) : (1 << 26))); | |
| 60 if (p->lc < 0) p->lc = 3; | |
| 61 if (p->lp < 0) p->lp = 0; | |
| 62 if (p->pb < 0) p->pb = 2; | |
| 63 if (p->algo < 0) p->algo = (level < 5 ? 0 : 1); | |
| 64 if (p->fb < 0) p->fb = (level < 7 ? 32 : 64); | |
| 65 if (p->btMode < 0) p->btMode = (p->algo == 0 ? 0 : 1); | |
| 66 if (p->numHashBytes < 0) p->numHashBytes = 4; | |
| 67 if (p->mc == 0) p->mc = (16 + (p->fb >> 1)) >> (p->btMode ? 0 : 1); | |
| 68 if (p->numThreads < 0) | |
| 69 p->numThreads = | |
| 70 #ifndef _7ZIP_ST | |
| 71 ((p->btMode && p->algo) ? 2 : 1); | |
| 72 #else | |
| 73 1; | |
| 74 #endif | |
| 75 } | |
| 76 | |
| 77 UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2) | |
| 78 { | |
| 79 CLzmaEncProps props = *props2; | |
| 80 LzmaEncProps_Normalize(&props); | |
| 81 return props.dictSize; | |
| 82 } | |
| 83 | |
| 84 /* #define LZMA_LOG_BSR */ | |
| 85 /* Define it for Intel's CPU */ | |
| 86 | |
| 87 | |
| 88 #ifdef LZMA_LOG_BSR | |
| 89 | |
| 90 #define kDicLogSizeMaxCompress 30 | |
| 91 | |
| 92 #define BSR2_RET(pos, res) { unsigned long i; _BitScanReverse(&i, (pos)); res =
(i + i) + ((pos >> (i - 1)) & 1); } | |
| 93 | |
| 94 UInt32 GetPosSlot1(UInt32 pos) | |
| 95 { | |
| 96 UInt32 res; | |
| 97 BSR2_RET(pos, res); | |
| 98 return res; | |
| 99 } | |
| 100 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); } | |
| 101 #define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res);
} | |
| 102 | |
| 103 #else | |
| 104 | |
| 105 #define kNumLogBits (9 + (int)sizeof(size_t) / 2) | |
| 106 #define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7) | |
| 107 | |
| 108 void LzmaEnc_FastPosInit(Byte *g_FastPos) | |
| 109 { | |
| 110 int c = 2, slotFast; | |
| 111 g_FastPos[0] = 0; | |
| 112 g_FastPos[1] = 1; | |
| 113 | |
| 114 for (slotFast = 2; slotFast < kNumLogBits * 2; slotFast++) | |
| 115 { | |
| 116 UInt32 k = (1 << ((slotFast >> 1) - 1)); | |
| 117 UInt32 j; | |
| 118 for (j = 0; j < k; j++, c++) | |
| 119 g_FastPos[c] = (Byte)slotFast; | |
| 120 } | |
| 121 } | |
| 122 | |
| 123 #define BSR2_RET(pos, res) { UInt32 i = 6 + ((kNumLogBits - 1) & \ | |
| 124 (0 - (((((UInt32)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \ | |
| 125 res = p->g_FastPos[pos >> i] + (i * 2); } | |
| 126 /* | |
| 127 #define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \ | |
| 128 p->g_FastPos[pos >> 6] + 12 : \ | |
| 129 p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; } | |
| 130 */ | |
| 131 | |
| 132 #define GetPosSlot1(pos) p->g_FastPos[pos] | |
| 133 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); } | |
| 134 #define GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[p
os]; else BSR2_RET(pos, res); } | |
| 135 | |
| 136 #endif | |
| 137 | |
| 138 | |
| 139 #define LZMA_NUM_REPS 4 | |
| 140 | |
| 141 typedef unsigned CState; | |
| 142 | |
| 143 typedef struct | |
| 144 { | |
| 145 UInt32 price; | |
| 146 | |
| 147 CState state; | |
| 148 int prev1IsChar; | |
| 149 int prev2; | |
| 150 | |
| 151 UInt32 posPrev2; | |
| 152 UInt32 backPrev2; | |
| 153 | |
| 154 UInt32 posPrev; | |
| 155 UInt32 backPrev; | |
| 156 UInt32 backs[LZMA_NUM_REPS]; | |
| 157 } COptimal; | |
| 158 | |
| 159 #define kNumOpts (1 << 12) | |
| 160 | |
| 161 #define kNumLenToPosStates 4 | |
| 162 #define kNumPosSlotBits 6 | |
| 163 #define kDicLogSizeMin 0 | |
| 164 #define kDicLogSizeMax 32 | |
| 165 #define kDistTableSizeMax (kDicLogSizeMax * 2) | |
| 166 | |
| 167 | |
| 168 #define kNumAlignBits 4 | |
| 169 #define kAlignTableSize (1 << kNumAlignBits) | |
| 170 #define kAlignMask (kAlignTableSize - 1) | |
| 171 | |
| 172 #define kStartPosModelIndex 4 | |
| 173 #define kEndPosModelIndex 14 | |
| 174 #define kNumPosModels (kEndPosModelIndex - kStartPosModelIndex) | |
| 175 | |
| 176 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1)) | |
| 177 | |
| 178 #ifdef _LZMA_PROB32 | |
| 179 #define CLzmaProb UInt32 | |
| 180 #else | |
| 181 #define CLzmaProb UInt16 | |
| 182 #endif | |
| 183 | |
| 184 #define LZMA_PB_MAX 4 | |
| 185 #define LZMA_LC_MAX 8 | |
| 186 #define LZMA_LP_MAX 4 | |
| 187 | |
| 188 #define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX) | |
| 189 | |
| 190 | |
| 191 #define kLenNumLowBits 3 | |
| 192 #define kLenNumLowSymbols (1 << kLenNumLowBits) | |
| 193 #define kLenNumMidBits 3 | |
| 194 #define kLenNumMidSymbols (1 << kLenNumMidBits) | |
| 195 #define kLenNumHighBits 8 | |
| 196 #define kLenNumHighSymbols (1 << kLenNumHighBits) | |
| 197 | |
| 198 #define kLenNumSymbolsTotal (kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHigh
Symbols) | |
| 199 | |
| 200 #define LZMA_MATCH_LEN_MIN 2 | |
| 201 #define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1) | |
| 202 | |
| 203 #define kNumStates 12 | |
| 204 | |
| 205 typedef struct | |
| 206 { | |
| 207 CLzmaProb choice; | |
| 208 CLzmaProb choice2; | |
| 209 CLzmaProb low[LZMA_NUM_PB_STATES_MAX << kLenNumLowBits]; | |
| 210 CLzmaProb mid[LZMA_NUM_PB_STATES_MAX << kLenNumMidBits]; | |
| 211 CLzmaProb high[kLenNumHighSymbols]; | |
| 212 } CLenEnc; | |
| 213 | |
| 214 typedef struct | |
| 215 { | |
| 216 CLenEnc p; | |
| 217 UInt32 prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal]; | |
| 218 UInt32 tableSize; | |
| 219 UInt32 counters[LZMA_NUM_PB_STATES_MAX]; | |
| 220 } CLenPriceEnc; | |
| 221 | |
| 222 typedef struct | |
| 223 { | |
| 224 UInt32 range; | |
| 225 Byte cache; | |
| 226 UInt64 low; | |
| 227 UInt64 cacheSize; | |
| 228 Byte *buf; | |
| 229 Byte *bufLim; | |
| 230 Byte *bufBase; | |
| 231 ISeqOutStream *outStream; | |
| 232 UInt64 processed; | |
| 233 SRes res; | |
| 234 } CRangeEnc; | |
| 235 | |
| 236 typedef struct | |
| 237 { | |
| 238 CLzmaProb *litProbs; | |
| 239 | |
| 240 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX]; | |
| 241 CLzmaProb isRep[kNumStates]; | |
| 242 CLzmaProb isRepG0[kNumStates]; | |
| 243 CLzmaProb isRepG1[kNumStates]; | |
| 244 CLzmaProb isRepG2[kNumStates]; | |
| 245 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX]; | |
| 246 | |
| 247 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits]; | |
| 248 CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex]; | |
| 249 CLzmaProb posAlignEncoder[1 << kNumAlignBits]; | |
| 250 | |
| 251 CLenPriceEnc lenEnc; | |
| 252 CLenPriceEnc repLenEnc; | |
| 253 | |
| 254 UInt32 reps[LZMA_NUM_REPS]; | |
| 255 UInt32 state; | |
| 256 } CSaveState; | |
| 257 | |
| 258 typedef struct | |
| 259 { | |
| 260 IMatchFinder matchFinder; | |
| 261 void *matchFinderObj; | |
| 262 | |
| 263 #ifndef _7ZIP_ST | |
| 264 Bool mtMode; | |
| 265 CMatchFinderMt matchFinderMt; | |
| 266 #endif | |
| 267 | |
| 268 CMatchFinder matchFinderBase; | |
| 269 | |
| 270 #ifndef _7ZIP_ST | |
| 271 Byte pad[128]; | |
| 272 #endif | |
| 273 | |
| 274 UInt32 optimumEndIndex; | |
| 275 UInt32 optimumCurrentIndex; | |
| 276 | |
| 277 UInt32 longestMatchLength; | |
| 278 UInt32 numPairs; | |
| 279 UInt32 numAvail; | |
| 280 COptimal opt[kNumOpts]; | |
| 281 | |
| 282 #ifndef LZMA_LOG_BSR | |
| 283 Byte g_FastPos[1 << kNumLogBits]; | |
| 284 #endif | |
| 285 | |
| 286 UInt32 ProbPrices[kBitModelTotal >> kNumMoveReducingBits]; | |
| 287 UInt32 matches[LZMA_MATCH_LEN_MAX * 2 + 2 + 1]; | |
| 288 UInt32 numFastBytes; | |
| 289 UInt32 additionalOffset; | |
| 290 UInt32 reps[LZMA_NUM_REPS]; | |
| 291 UInt32 state; | |
| 292 | |
| 293 UInt32 posSlotPrices[kNumLenToPosStates][kDistTableSizeMax]; | |
| 294 UInt32 distancesPrices[kNumLenToPosStates][kNumFullDistances]; | |
| 295 UInt32 alignPrices[kAlignTableSize]; | |
| 296 UInt32 alignPriceCount; | |
| 297 | |
| 298 UInt32 distTableSize; | |
| 299 | |
| 300 unsigned lc, lp, pb; | |
| 301 unsigned lpMask, pbMask; | |
| 302 | |
| 303 CLzmaProb *litProbs; | |
| 304 | |
| 305 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX]; | |
| 306 CLzmaProb isRep[kNumStates]; | |
| 307 CLzmaProb isRepG0[kNumStates]; | |
| 308 CLzmaProb isRepG1[kNumStates]; | |
| 309 CLzmaProb isRepG2[kNumStates]; | |
| 310 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX]; | |
| 311 | |
| 312 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits]; | |
| 313 CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex]; | |
| 314 CLzmaProb posAlignEncoder[1 << kNumAlignBits]; | |
| 315 | |
| 316 CLenPriceEnc lenEnc; | |
| 317 CLenPriceEnc repLenEnc; | |
| 318 | |
| 319 unsigned lclp; | |
| 320 | |
| 321 Bool fastMode; | |
| 322 | |
| 323 CRangeEnc rc; | |
| 324 | |
| 325 Bool writeEndMark; | |
| 326 UInt64 nowPos64; | |
| 327 UInt32 matchPriceCount; | |
| 328 Bool finished; | |
| 329 Bool multiThread; | |
| 330 | |
| 331 SRes result; | |
| 332 UInt32 dictSize; | |
| 333 UInt32 matchFinderCycles; | |
| 334 | |
| 335 int needInit; | |
| 336 | |
| 337 CSaveState saveState; | |
| 338 } CLzmaEnc; | |
| 339 | |
| 340 void LzmaEnc_SaveState(CLzmaEncHandle pp) | |
| 341 { | |
| 342 CLzmaEnc *p = (CLzmaEnc *)pp; | |
| 343 CSaveState *dest = &p->saveState; | |
| 344 int i; | |
| 345 dest->lenEnc = p->lenEnc; | |
| 346 dest->repLenEnc = p->repLenEnc; | |
| 347 dest->state = p->state; | |
| 348 | |
| 349 for (i = 0; i < kNumStates; i++) | |
| 350 { | |
| 351 memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i])); | |
| 352 memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i])); | |
| 353 } | |
| 354 for (i = 0; i < kNumLenToPosStates; i++) | |
| 355 memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncod
er[i])); | |
| 356 memcpy(dest->isRep, p->isRep, sizeof(p->isRep)); | |
| 357 memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0)); | |
| 358 memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1)); | |
| 359 memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2)); | |
| 360 memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders)); | |
| 361 memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder)); | |
| 362 memcpy(dest->reps, p->reps, sizeof(p->reps)); | |
| 363 memcpy(dest->litProbs, p->litProbs, (0x300 << p->lclp) * sizeof(CLzmaProb)); | |
| 364 } | |
| 365 | |
| 366 void LzmaEnc_RestoreState(CLzmaEncHandle pp) | |
| 367 { | |
| 368 CLzmaEnc *dest = (CLzmaEnc *)pp; | |
| 369 const CSaveState *p = &dest->saveState; | |
| 370 int i; | |
| 371 dest->lenEnc = p->lenEnc; | |
| 372 dest->repLenEnc = p->repLenEnc; | |
| 373 dest->state = p->state; | |
| 374 | |
| 375 for (i = 0; i < kNumStates; i++) | |
| 376 { | |
| 377 memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i])); | |
| 378 memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i])); | |
| 379 } | |
| 380 for (i = 0; i < kNumLenToPosStates; i++) | |
| 381 memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncod
er[i])); | |
| 382 memcpy(dest->isRep, p->isRep, sizeof(p->isRep)); | |
| 383 memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0)); | |
| 384 memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1)); | |
| 385 memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2)); | |
| 386 memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders)); | |
| 387 memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder)); | |
| 388 memcpy(dest->reps, p->reps, sizeof(p->reps)); | |
| 389 memcpy(dest->litProbs, p->litProbs, (0x300 << dest->lclp) * sizeof(CLzmaProb))
; | |
| 390 } | |
| 391 | |
| 392 SRes LzmaEnc_SetProps(CLzmaEncHandle pp, const CLzmaEncProps *props2) | |
| 393 { | |
| 394 CLzmaEnc *p = (CLzmaEnc *)pp; | |
| 395 CLzmaEncProps props = *props2; | |
| 396 LzmaEncProps_Normalize(&props); | |
| 397 | |
| 398 if (props.lc > LZMA_LC_MAX || props.lp > LZMA_LP_MAX || props.pb > LZMA_PB_MAX
|| | |
| 399 props.dictSize > ((UInt32)1 << kDicLogSizeMaxCompress) || props.dictSize >
((UInt32)1 << 30)) | |
| 400 return SZ_ERROR_PARAM; | |
| 401 p->dictSize = props.dictSize; | |
| 402 p->matchFinderCycles = props.mc; | |
| 403 { | |
| 404 unsigned fb = props.fb; | |
| 405 if (fb < 5) | |
| 406 fb = 5; | |
| 407 if (fb > LZMA_MATCH_LEN_MAX) | |
| 408 fb = LZMA_MATCH_LEN_MAX; | |
| 409 p->numFastBytes = fb; | |
| 410 } | |
| 411 p->lc = props.lc; | |
| 412 p->lp = props.lp; | |
| 413 p->pb = props.pb; | |
| 414 p->fastMode = (props.algo == 0); | |
| 415 p->matchFinderBase.btMode = props.btMode; | |
| 416 { | |
| 417 UInt32 numHashBytes = 4; | |
| 418 if (props.btMode) | |
| 419 { | |
| 420 if (props.numHashBytes < 2) | |
| 421 numHashBytes = 2; | |
| 422 else if (props.numHashBytes < 4) | |
| 423 numHashBytes = props.numHashBytes; | |
| 424 } | |
| 425 p->matchFinderBase.numHashBytes = numHashBytes; | |
| 426 } | |
| 427 | |
| 428 p->matchFinderBase.cutValue = props.mc; | |
| 429 | |
| 430 p->writeEndMark = props.writeEndMark; | |
| 431 | |
| 432 #ifndef _7ZIP_ST | |
| 433 /* | |
| 434 if (newMultiThread != _multiThread) | |
| 435 { | |
| 436 ReleaseMatchFinder(); | |
| 437 _multiThread = newMultiThread; | |
| 438 } | |
| 439 */ | |
| 440 p->multiThread = (props.numThreads > 1); | |
| 441 #endif | |
| 442 | |
| 443 return SZ_OK; | |
| 444 } | |
| 445 | |
| 446 static const int kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4, 5,
6, 4, 5}; | |
| 447 static const int kMatchNextStates[kNumStates] = {7, 7, 7, 7, 7, 7, 7, 10, 10,
10, 10, 10}; | |
| 448 static const int kRepNextStates[kNumStates] = {8, 8, 8, 8, 8, 8, 8, 11, 11,
11, 11, 11}; | |
| 449 static const int kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11,
11, 11, 11}; | |
| 450 | |
| 451 #define IsCharState(s) ((s) < 7) | |
| 452 | |
| 453 #define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kN
umLenToPosStates - 1) | |
| 454 | |
| 455 #define kInfinityPrice (1 << 30) | |
| 456 | |
| 457 static void RangeEnc_Construct(CRangeEnc *p) | |
| 458 { | |
| 459 p->outStream = 0; | |
| 460 p->bufBase = 0; | |
| 461 } | |
| 462 | |
| 463 #define RangeEnc_GetProcessed(p) ((p)->processed + ((p)->buf - (p)->bufBase) + (
p)->cacheSize) | |
| 464 | |
| 465 #define RC_BUF_SIZE (1 << 16) | |
| 466 static int RangeEnc_Alloc(CRangeEnc *p, ISzAlloc *alloc) | |
| 467 { | |
| 468 if (p->bufBase == 0) | |
| 469 { | |
| 470 p->bufBase = (Byte *)alloc->Alloc(alloc, RC_BUF_SIZE); | |
| 471 if (p->bufBase == 0) | |
| 472 return 0; | |
| 473 p->bufLim = p->bufBase + RC_BUF_SIZE; | |
| 474 } | |
| 475 return 1; | |
| 476 } | |
| 477 | |
| 478 static void RangeEnc_Free(CRangeEnc *p, ISzAlloc *alloc) | |
| 479 { | |
| 480 alloc->Free(alloc, p->bufBase); | |
| 481 p->bufBase = 0; | |
| 482 } | |
| 483 | |
| 484 static void RangeEnc_Init(CRangeEnc *p) | |
| 485 { | |
| 486 /* Stream.Init(); */ | |
| 487 p->low = 0; | |
| 488 p->range = 0xFFFFFFFF; | |
| 489 p->cacheSize = 1; | |
| 490 p->cache = 0; | |
| 491 | |
| 492 p->buf = p->bufBase; | |
| 493 | |
| 494 p->processed = 0; | |
| 495 p->res = SZ_OK; | |
| 496 } | |
| 497 | |
| 498 static void RangeEnc_FlushStream(CRangeEnc *p) | |
| 499 { | |
| 500 size_t num; | |
| 501 if (p->res != SZ_OK) | |
| 502 return; | |
| 503 num = p->buf - p->bufBase; | |
| 504 if (num != p->outStream->Write(p->outStream, p->bufBase, num)) | |
| 505 p->res = SZ_ERROR_WRITE; | |
| 506 p->processed += num; | |
| 507 p->buf = p->bufBase; | |
| 508 } | |
| 509 | |
| 510 static void MY_FAST_CALL RangeEnc_ShiftLow(CRangeEnc *p) | |
| 511 { | |
| 512 if ((UInt32)p->low < (UInt32)0xFF000000 || (int)(p->low >> 32) != 0) | |
| 513 { | |
| 514 Byte temp = p->cache; | |
| 515 do | |
| 516 { | |
| 517 Byte *buf = p->buf; | |
| 518 *buf++ = (Byte)(temp + (Byte)(p->low >> 32)); | |
| 519 p->buf = buf; | |
| 520 if (buf == p->bufLim) | |
| 521 RangeEnc_FlushStream(p); | |
| 522 temp = 0xFF; | |
| 523 } | |
| 524 while (--p->cacheSize != 0); | |
| 525 p->cache = (Byte)((UInt32)p->low >> 24); | |
| 526 } | |
| 527 p->cacheSize++; | |
| 528 p->low = (UInt32)p->low << 8; | |
| 529 } | |
| 530 | |
| 531 static void RangeEnc_FlushData(CRangeEnc *p) | |
| 532 { | |
| 533 int i; | |
| 534 for (i = 0; i < 5; i++) | |
| 535 RangeEnc_ShiftLow(p); | |
| 536 } | |
| 537 | |
| 538 static void RangeEnc_EncodeDirectBits(CRangeEnc *p, UInt32 value, int numBits) | |
| 539 { | |
| 540 do | |
| 541 { | |
| 542 p->range >>= 1; | |
| 543 p->low += p->range & (0 - ((value >> --numBits) & 1)); | |
| 544 if (p->range < kTopValue) | |
| 545 { | |
| 546 p->range <<= 8; | |
| 547 RangeEnc_ShiftLow(p); | |
| 548 } | |
| 549 } | |
| 550 while (numBits != 0); | |
| 551 } | |
| 552 | |
| 553 static void RangeEnc_EncodeBit(CRangeEnc *p, CLzmaProb *prob, UInt32 symbol) | |
| 554 { | |
| 555 UInt32 ttt = *prob; | |
| 556 UInt32 newBound = (p->range >> kNumBitModelTotalBits) * ttt; | |
| 557 if (symbol == 0) | |
| 558 { | |
| 559 p->range = newBound; | |
| 560 ttt += (kBitModelTotal - ttt) >> kNumMoveBits; | |
| 561 } | |
| 562 else | |
| 563 { | |
| 564 p->low += newBound; | |
| 565 p->range -= newBound; | |
| 566 ttt -= ttt >> kNumMoveBits; | |
| 567 } | |
| 568 *prob = (CLzmaProb)ttt; | |
| 569 if (p->range < kTopValue) | |
| 570 { | |
| 571 p->range <<= 8; | |
| 572 RangeEnc_ShiftLow(p); | |
| 573 } | |
| 574 } | |
| 575 | |
| 576 static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol) | |
| 577 { | |
| 578 symbol |= 0x100; | |
| 579 do | |
| 580 { | |
| 581 RangeEnc_EncodeBit(p, probs + (symbol >> 8), (symbol >> 7) & 1); | |
| 582 symbol <<= 1; | |
| 583 } | |
| 584 while (symbol < 0x10000); | |
| 585 } | |
| 586 | |
| 587 static void LitEnc_EncodeMatched(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol,
UInt32 matchByte) | |
| 588 { | |
| 589 UInt32 offs = 0x100; | |
| 590 symbol |= 0x100; | |
| 591 do | |
| 592 { | |
| 593 matchByte <<= 1; | |
| 594 RangeEnc_EncodeBit(p, probs + (offs + (matchByte & offs) + (symbol >> 8)), (
symbol >> 7) & 1); | |
| 595 symbol <<= 1; | |
| 596 offs &= ~(matchByte ^ symbol); | |
| 597 } | |
| 598 while (symbol < 0x10000); | |
| 599 } | |
| 600 | |
| 601 void LzmaEnc_InitPriceTables(UInt32 *ProbPrices) | |
| 602 { | |
| 603 UInt32 i; | |
| 604 for (i = (1 << kNumMoveReducingBits) / 2; i < kBitModelTotal; i += (1 << kNumM
oveReducingBits)) | |
| 605 { | |
| 606 const int kCyclesBits = kNumBitPriceShiftBits; | |
| 607 UInt32 w = i; | |
| 608 UInt32 bitCount = 0; | |
| 609 int j; | |
| 610 for (j = 0; j < kCyclesBits; j++) | |
| 611 { | |
| 612 w = w * w; | |
| 613 bitCount <<= 1; | |
| 614 while (w >= ((UInt32)1 << 16)) | |
| 615 { | |
| 616 w >>= 1; | |
| 617 bitCount++; | |
| 618 } | |
| 619 } | |
| 620 ProbPrices[i >> kNumMoveReducingBits] = ((kNumBitModelTotalBits << kCyclesBi
ts) - 15 - bitCount); | |
| 621 } | |
| 622 } | |
| 623 | |
| 624 | |
| 625 #define GET_PRICE(prob, symbol) \ | |
| 626 p->ProbPrices[((prob) ^ (((-(int)(symbol))) & (kBitModelTotal - 1))) >> kNumMo
veReducingBits]; | |
| 627 | |
| 628 #define GET_PRICEa(prob, symbol) \ | |
| 629 ProbPrices[((prob) ^ ((-((int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveR
educingBits]; | |
| 630 | |
| 631 #define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits] | |
| 632 #define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumM
oveReducingBits] | |
| 633 | |
| 634 #define GET_PRICE_0a(prob) ProbPrices[(prob) >> kNumMoveReducingBits] | |
| 635 #define GET_PRICE_1a(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMov
eReducingBits] | |
| 636 | |
| 637 static UInt32 LitEnc_GetPrice(const CLzmaProb *probs, UInt32 symbol, UInt32 *Pro
bPrices) | |
| 638 { | |
| 639 UInt32 price = 0; | |
| 640 symbol |= 0x100; | |
| 641 do | |
| 642 { | |
| 643 price += GET_PRICEa(probs[symbol >> 8], (symbol >> 7) & 1); | |
| 644 symbol <<= 1; | |
| 645 } | |
| 646 while (symbol < 0x10000); | |
| 647 return price; | |
| 648 } | |
| 649 | |
| 650 static UInt32 LitEnc_GetPriceMatched(const CLzmaProb *probs, UInt32 symbol, UInt
32 matchByte, UInt32 *ProbPrices) | |
| 651 { | |
| 652 UInt32 price = 0; | |
| 653 UInt32 offs = 0x100; | |
| 654 symbol |= 0x100; | |
| 655 do | |
| 656 { | |
| 657 matchByte <<= 1; | |
| 658 price += GET_PRICEa(probs[offs + (matchByte & offs) + (symbol >> 8)], (symbo
l >> 7) & 1); | |
| 659 symbol <<= 1; | |
| 660 offs &= ~(matchByte ^ symbol); | |
| 661 } | |
| 662 while (symbol < 0x10000); | |
| 663 return price; | |
| 664 } | |
| 665 | |
| 666 | |
| 667 static void RcTree_Encode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UIn
t32 symbol) | |
| 668 { | |
| 669 UInt32 m = 1; | |
| 670 int i; | |
| 671 for (i = numBitLevels; i != 0;) | |
| 672 { | |
| 673 UInt32 bit; | |
| 674 i--; | |
| 675 bit = (symbol >> i) & 1; | |
| 676 RangeEnc_EncodeBit(rc, probs + m, bit); | |
| 677 m = (m << 1) | bit; | |
| 678 } | |
| 679 } | |
| 680 | |
| 681 static void RcTree_ReverseEncode(CRangeEnc *rc, CLzmaProb *probs, int numBitLeve
ls, UInt32 symbol) | |
| 682 { | |
| 683 UInt32 m = 1; | |
| 684 int i; | |
| 685 for (i = 0; i < numBitLevels; i++) | |
| 686 { | |
| 687 UInt32 bit = symbol & 1; | |
| 688 RangeEnc_EncodeBit(rc, probs + m, bit); | |
| 689 m = (m << 1) | bit; | |
| 690 symbol >>= 1; | |
| 691 } | |
| 692 } | |
| 693 | |
| 694 static UInt32 RcTree_GetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 s
ymbol, UInt32 *ProbPrices) | |
| 695 { | |
| 696 UInt32 price = 0; | |
| 697 symbol |= (1 << numBitLevels); | |
| 698 while (symbol != 1) | |
| 699 { | |
| 700 price += GET_PRICEa(probs[symbol >> 1], symbol & 1); | |
| 701 symbol >>= 1; | |
| 702 } | |
| 703 return price; | |
| 704 } | |
| 705 | |
| 706 static UInt32 RcTree_ReverseGetPrice(const CLzmaProb *probs, int numBitLevels, U
Int32 symbol, UInt32 *ProbPrices) | |
| 707 { | |
| 708 UInt32 price = 0; | |
| 709 UInt32 m = 1; | |
| 710 int i; | |
| 711 for (i = numBitLevels; i != 0; i--) | |
| 712 { | |
| 713 UInt32 bit = symbol & 1; | |
| 714 symbol >>= 1; | |
| 715 price += GET_PRICEa(probs[m], bit); | |
| 716 m = (m << 1) | bit; | |
| 717 } | |
| 718 return price; | |
| 719 } | |
| 720 | |
| 721 | |
| 722 static void LenEnc_Init(CLenEnc *p) | |
| 723 { | |
| 724 unsigned i; | |
| 725 p->choice = p->choice2 = kProbInitValue; | |
| 726 for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumLowBits); i++) | |
| 727 p->low[i] = kProbInitValue; | |
| 728 for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumMidBits); i++) | |
| 729 p->mid[i] = kProbInitValue; | |
| 730 for (i = 0; i < kLenNumHighSymbols; i++) | |
| 731 p->high[i] = kProbInitValue; | |
| 732 } | |
| 733 | |
| 734 static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posSt
ate) | |
| 735 { | |
| 736 if (symbol < kLenNumLowSymbols) | |
| 737 { | |
| 738 RangeEnc_EncodeBit(rc, &p->choice, 0); | |
| 739 RcTree_Encode(rc, p->low + (posState << kLenNumLowBits), kLenNumLowBits, sym
bol); | |
| 740 } | |
| 741 else | |
| 742 { | |
| 743 RangeEnc_EncodeBit(rc, &p->choice, 1); | |
| 744 if (symbol < kLenNumLowSymbols + kLenNumMidSymbols) | |
| 745 { | |
| 746 RangeEnc_EncodeBit(rc, &p->choice2, 0); | |
| 747 RcTree_Encode(rc, p->mid + (posState << kLenNumMidBits), kLenNumMidBits, s
ymbol - kLenNumLowSymbols); | |
| 748 } | |
| 749 else | |
| 750 { | |
| 751 RangeEnc_EncodeBit(rc, &p->choice2, 1); | |
| 752 RcTree_Encode(rc, p->high, kLenNumHighBits, symbol - kLenNumLowSymbols - k
LenNumMidSymbols); | |
| 753 } | |
| 754 } | |
| 755 } | |
| 756 | |
| 757 static void LenEnc_SetPrices(CLenEnc *p, UInt32 posState, UInt32 numSymbols, UIn
t32 *prices, UInt32 *ProbPrices) | |
| 758 { | |
| 759 UInt32 a0 = GET_PRICE_0a(p->choice); | |
| 760 UInt32 a1 = GET_PRICE_1a(p->choice); | |
| 761 UInt32 b0 = a1 + GET_PRICE_0a(p->choice2); | |
| 762 UInt32 b1 = a1 + GET_PRICE_1a(p->choice2); | |
| 763 UInt32 i = 0; | |
| 764 for (i = 0; i < kLenNumLowSymbols; i++) | |
| 765 { | |
| 766 if (i >= numSymbols) | |
| 767 return; | |
| 768 prices[i] = a0 + RcTree_GetPrice(p->low + (posState << kLenNumLowBits), kLen
NumLowBits, i, ProbPrices); | |
| 769 } | |
| 770 for (; i < kLenNumLowSymbols + kLenNumMidSymbols; i++) | |
| 771 { | |
| 772 if (i >= numSymbols) | |
| 773 return; | |
| 774 prices[i] = b0 + RcTree_GetPrice(p->mid + (posState << kLenNumMidBits), kLen
NumMidBits, i - kLenNumLowSymbols, ProbPrices); | |
| 775 } | |
| 776 for (; i < numSymbols; i++) | |
| 777 prices[i] = b1 + RcTree_GetPrice(p->high, kLenNumHighBits, i - kLenNumLowSym
bols - kLenNumMidSymbols, ProbPrices); | |
| 778 } | |
| 779 | |
| 780 static void MY_FAST_CALL LenPriceEnc_UpdateTable(CLenPriceEnc *p, UInt32 posStat
e, UInt32 *ProbPrices) | |
| 781 { | |
| 782 LenEnc_SetPrices(&p->p, posState, p->tableSize, p->prices[posState], ProbPrice
s); | |
| 783 p->counters[posState] = p->tableSize; | |
| 784 } | |
| 785 | |
| 786 static void LenPriceEnc_UpdateTables(CLenPriceEnc *p, UInt32 numPosStates, UInt3
2 *ProbPrices) | |
| 787 { | |
| 788 UInt32 posState; | |
| 789 for (posState = 0; posState < numPosStates; posState++) | |
| 790 LenPriceEnc_UpdateTable(p, posState, ProbPrices); | |
| 791 } | |
| 792 | |
| 793 static void LenEnc_Encode2(CLenPriceEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32
posState, Bool updatePrice, UInt32 *ProbPrices) | |
| 794 { | |
| 795 LenEnc_Encode(&p->p, rc, symbol, posState); | |
| 796 if (updatePrice) | |
| 797 if (--p->counters[posState] == 0) | |
| 798 LenPriceEnc_UpdateTable(p, posState, ProbPrices); | |
| 799 } | |
| 800 | |
| 801 | |
| 802 | |
| 803 | |
| 804 static void MovePos(CLzmaEnc *p, UInt32 num) | |
| 805 { | |
| 806 #ifdef SHOW_STAT | |
| 807 ttt += num; | |
| 808 printf("\n MovePos %d", num); | |
| 809 #endif | |
| 810 if (num != 0) | |
| 811 { | |
| 812 p->additionalOffset += num; | |
| 813 p->matchFinder.Skip(p->matchFinderObj, num); | |
| 814 } | |
| 815 } | |
| 816 | |
| 817 static UInt32 ReadMatchDistances(CLzmaEnc *p, UInt32 *numDistancePairsRes) | |
| 818 { | |
| 819 UInt32 lenRes = 0, numPairs; | |
| 820 p->numAvail = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj); | |
| 821 numPairs = p->matchFinder.GetMatches(p->matchFinderObj, p->matches); | |
| 822 #ifdef SHOW_STAT | |
| 823 printf("\n i = %d numPairs = %d ", ttt, numPairs / 2); | |
| 824 ttt++; | |
| 825 { | |
| 826 UInt32 i; | |
| 827 for (i = 0; i < numPairs; i += 2) | |
| 828 printf("%2d %6d | ", p->matches[i], p->matches[i + 1]); | |
| 829 } | |
| 830 #endif | |
| 831 if (numPairs > 0) | |
| 832 { | |
| 833 lenRes = p->matches[numPairs - 2]; | |
| 834 if (lenRes == p->numFastBytes) | |
| 835 { | |
| 836 const Byte *pby = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj)
- 1; | |
| 837 UInt32 distance = p->matches[numPairs - 1] + 1; | |
| 838 UInt32 numAvail = p->numAvail; | |
| 839 if (numAvail > LZMA_MATCH_LEN_MAX) | |
| 840 numAvail = LZMA_MATCH_LEN_MAX; | |
| 841 { | |
| 842 const Byte *pby2 = pby - distance; | |
| 843 for (; lenRes < numAvail && pby[lenRes] == pby2[lenRes]; lenRes++); | |
| 844 } | |
| 845 } | |
| 846 } | |
| 847 p->additionalOffset++; | |
| 848 *numDistancePairsRes = numPairs; | |
| 849 return lenRes; | |
| 850 } | |
| 851 | |
| 852 | |
| 853 #define MakeAsChar(p) (p)->backPrev = (UInt32)(-1); (p)->prev1IsChar = False; | |
| 854 #define MakeAsShortRep(p) (p)->backPrev = 0; (p)->prev1IsChar = False; | |
| 855 #define IsShortRep(p) ((p)->backPrev == 0) | |
| 856 | |
| 857 static UInt32 GetRepLen1Price(CLzmaEnc *p, UInt32 state, UInt32 posState) | |
| 858 { | |
| 859 return | |
| 860 GET_PRICE_0(p->isRepG0[state]) + | |
| 861 GET_PRICE_0(p->isRep0Long[state][posState]); | |
| 862 } | |
| 863 | |
| 864 static UInt32 GetPureRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 state, UInt32
posState) | |
| 865 { | |
| 866 UInt32 price; | |
| 867 if (repIndex == 0) | |
| 868 { | |
| 869 price = GET_PRICE_0(p->isRepG0[state]); | |
| 870 price += GET_PRICE_1(p->isRep0Long[state][posState]); | |
| 871 } | |
| 872 else | |
| 873 { | |
| 874 price = GET_PRICE_1(p->isRepG0[state]); | |
| 875 if (repIndex == 1) | |
| 876 price += GET_PRICE_0(p->isRepG1[state]); | |
| 877 else | |
| 878 { | |
| 879 price += GET_PRICE_1(p->isRepG1[state]); | |
| 880 price += GET_PRICE(p->isRepG2[state], repIndex - 2); | |
| 881 } | |
| 882 } | |
| 883 return price; | |
| 884 } | |
| 885 | |
| 886 static UInt32 GetRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 len, UInt32 state
, UInt32 posState) | |
| 887 { | |
| 888 return p->repLenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN] + | |
| 889 GetPureRepPrice(p, repIndex, state, posState); | |
| 890 } | |
| 891 | |
| 892 static UInt32 Backward(CLzmaEnc *p, UInt32 *backRes, UInt32 cur) | |
| 893 { | |
| 894 UInt32 posMem = p->opt[cur].posPrev; | |
| 895 UInt32 backMem = p->opt[cur].backPrev; | |
| 896 p->optimumEndIndex = cur; | |
| 897 do | |
| 898 { | |
| 899 if (p->opt[cur].prev1IsChar) | |
| 900 { | |
| 901 MakeAsChar(&p->opt[posMem]) | |
| 902 p->opt[posMem].posPrev = posMem - 1; | |
| 903 if (p->opt[cur].prev2) | |
| 904 { | |
| 905 p->opt[posMem - 1].prev1IsChar = False; | |
| 906 p->opt[posMem - 1].posPrev = p->opt[cur].posPrev2; | |
| 907 p->opt[posMem - 1].backPrev = p->opt[cur].backPrev2; | |
| 908 } | |
| 909 } | |
| 910 { | |
| 911 UInt32 posPrev = posMem; | |
| 912 UInt32 backCur = backMem; | |
| 913 | |
| 914 backMem = p->opt[posPrev].backPrev; | |
| 915 posMem = p->opt[posPrev].posPrev; | |
| 916 | |
| 917 p->opt[posPrev].backPrev = backCur; | |
| 918 p->opt[posPrev].posPrev = cur; | |
| 919 cur = posPrev; | |
| 920 } | |
| 921 } | |
| 922 while (cur != 0); | |
| 923 *backRes = p->opt[0].backPrev; | |
| 924 p->optimumCurrentIndex = p->opt[0].posPrev; | |
| 925 return p->optimumCurrentIndex; | |
| 926 } | |
| 927 | |
| 928 #define LIT_PROBS(pos, prevByte) (p->litProbs + ((((pos) & p->lpMask) << p->lc)
+ ((prevByte) >> (8 - p->lc))) * 0x300) | |
| 929 | |
| 930 static UInt32 GetOptimum(CLzmaEnc *p, UInt32 position, UInt32 *backRes) | |
| 931 { | |
| 932 UInt32 numAvail, mainLen, numPairs, repMaxIndex, i, posState, lenEnd, len, cur
; | |
| 933 UInt32 matchPrice, repMatchPrice, normalMatchPrice; | |
| 934 UInt32 reps[LZMA_NUM_REPS], repLens[LZMA_NUM_REPS]; | |
| 935 UInt32 *matches; | |
| 936 const Byte *data; | |
| 937 Byte curByte, matchByte; | |
| 938 if (p->optimumEndIndex != p->optimumCurrentIndex) | |
| 939 { | |
| 940 const COptimal *opt = &p->opt[p->optimumCurrentIndex]; | |
| 941 UInt32 lenRes = opt->posPrev - p->optimumCurrentIndex; | |
| 942 *backRes = opt->backPrev; | |
| 943 p->optimumCurrentIndex = opt->posPrev; | |
| 944 return lenRes; | |
| 945 } | |
| 946 p->optimumCurrentIndex = p->optimumEndIndex = 0; | |
| 947 | |
| 948 if (p->additionalOffset == 0) | |
| 949 mainLen = ReadMatchDistances(p, &numPairs); | |
| 950 else | |
| 951 { | |
| 952 mainLen = p->longestMatchLength; | |
| 953 numPairs = p->numPairs; | |
| 954 } | |
| 955 | |
| 956 numAvail = p->numAvail; | |
| 957 if (numAvail < 2) | |
| 958 { | |
| 959 *backRes = (UInt32)(-1); | |
| 960 return 1; | |
| 961 } | |
| 962 if (numAvail > LZMA_MATCH_LEN_MAX) | |
| 963 numAvail = LZMA_MATCH_LEN_MAX; | |
| 964 | |
| 965 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; | |
| 966 repMaxIndex = 0; | |
| 967 for (i = 0; i < LZMA_NUM_REPS; i++) | |
| 968 { | |
| 969 UInt32 lenTest; | |
| 970 const Byte *data2; | |
| 971 reps[i] = p->reps[i]; | |
| 972 data2 = data - (reps[i] + 1); | |
| 973 if (data[0] != data2[0] || data[1] != data2[1]) | |
| 974 { | |
| 975 repLens[i] = 0; | |
| 976 continue; | |
| 977 } | |
| 978 for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; len
Test++); | |
| 979 repLens[i] = lenTest; | |
| 980 if (lenTest > repLens[repMaxIndex]) | |
| 981 repMaxIndex = i; | |
| 982 } | |
| 983 if (repLens[repMaxIndex] >= p->numFastBytes) | |
| 984 { | |
| 985 UInt32 lenRes; | |
| 986 *backRes = repMaxIndex; | |
| 987 lenRes = repLens[repMaxIndex]; | |
| 988 MovePos(p, lenRes - 1); | |
| 989 return lenRes; | |
| 990 } | |
| 991 | |
| 992 matches = p->matches; | |
| 993 if (mainLen >= p->numFastBytes) | |
| 994 { | |
| 995 *backRes = matches[numPairs - 1] + LZMA_NUM_REPS; | |
| 996 MovePos(p, mainLen - 1); | |
| 997 return mainLen; | |
| 998 } | |
| 999 curByte = *data; | |
| 1000 matchByte = *(data - (reps[0] + 1)); | |
| 1001 | |
| 1002 if (mainLen < 2 && curByte != matchByte && repLens[repMaxIndex] < 2) | |
| 1003 { | |
| 1004 *backRes = (UInt32)-1; | |
| 1005 return 1; | |
| 1006 } | |
| 1007 | |
| 1008 p->opt[0].state = (CState)p->state; | |
| 1009 | |
| 1010 posState = (position & p->pbMask); | |
| 1011 | |
| 1012 { | |
| 1013 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1)); | |
| 1014 p->opt[1].price = GET_PRICE_0(p->isMatch[p->state][posState]) + | |
| 1015 (!IsCharState(p->state) ? | |
| 1016 LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) : | |
| 1017 LitEnc_GetPrice(probs, curByte, p->ProbPrices)); | |
| 1018 } | |
| 1019 | |
| 1020 MakeAsChar(&p->opt[1]); | |
| 1021 | |
| 1022 matchPrice = GET_PRICE_1(p->isMatch[p->state][posState]); | |
| 1023 repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[p->state]); | |
| 1024 | |
| 1025 if (matchByte == curByte) | |
| 1026 { | |
| 1027 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, p->state, posState
); | |
| 1028 if (shortRepPrice < p->opt[1].price) | |
| 1029 { | |
| 1030 p->opt[1].price = shortRepPrice; | |
| 1031 MakeAsShortRep(&p->opt[1]); | |
| 1032 } | |
| 1033 } | |
| 1034 lenEnd = ((mainLen >= repLens[repMaxIndex]) ? mainLen : repLens[repMaxIndex]); | |
| 1035 | |
| 1036 if (lenEnd < 2) | |
| 1037 { | |
| 1038 *backRes = p->opt[1].backPrev; | |
| 1039 return 1; | |
| 1040 } | |
| 1041 | |
| 1042 p->opt[1].posPrev = 0; | |
| 1043 for (i = 0; i < LZMA_NUM_REPS; i++) | |
| 1044 p->opt[0].backs[i] = reps[i]; | |
| 1045 | |
| 1046 len = lenEnd; | |
| 1047 do | |
| 1048 p->opt[len--].price = kInfinityPrice; | |
| 1049 while (len >= 2); | |
| 1050 | |
| 1051 for (i = 0; i < LZMA_NUM_REPS; i++) | |
| 1052 { | |
| 1053 UInt32 repLen = repLens[i]; | |
| 1054 UInt32 price; | |
| 1055 if (repLen < 2) | |
| 1056 continue; | |
| 1057 price = repMatchPrice + GetPureRepPrice(p, i, p->state, posState); | |
| 1058 do | |
| 1059 { | |
| 1060 UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][repLen - 2]; | |
| 1061 COptimal *opt = &p->opt[repLen]; | |
| 1062 if (curAndLenPrice < opt->price) | |
| 1063 { | |
| 1064 opt->price = curAndLenPrice; | |
| 1065 opt->posPrev = 0; | |
| 1066 opt->backPrev = i; | |
| 1067 opt->prev1IsChar = False; | |
| 1068 } | |
| 1069 } | |
| 1070 while (--repLen >= 2); | |
| 1071 } | |
| 1072 | |
| 1073 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[p->state]); | |
| 1074 | |
| 1075 len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2); | |
| 1076 if (len <= mainLen) | |
| 1077 { | |
| 1078 UInt32 offs = 0; | |
| 1079 while (len > matches[offs]) | |
| 1080 offs += 2; | |
| 1081 for (; ; len++) | |
| 1082 { | |
| 1083 COptimal *opt; | |
| 1084 UInt32 distance = matches[offs + 1]; | |
| 1085 | |
| 1086 UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][len
- LZMA_MATCH_LEN_MIN]; | |
| 1087 UInt32 lenToPosState = GetLenToPosState(len); | |
| 1088 if (distance < kNumFullDistances) | |
| 1089 curAndLenPrice += p->distancesPrices[lenToPosState][distance]; | |
| 1090 else | |
| 1091 { | |
| 1092 UInt32 slot; | |
| 1093 GetPosSlot2(distance, slot); | |
| 1094 curAndLenPrice += p->alignPrices[distance & kAlignMask] + p->posSlotPric
es[lenToPosState][slot]; | |
| 1095 } | |
| 1096 opt = &p->opt[len]; | |
| 1097 if (curAndLenPrice < opt->price) | |
| 1098 { | |
| 1099 opt->price = curAndLenPrice; | |
| 1100 opt->posPrev = 0; | |
| 1101 opt->backPrev = distance + LZMA_NUM_REPS; | |
| 1102 opt->prev1IsChar = False; | |
| 1103 } | |
| 1104 if (len == matches[offs]) | |
| 1105 { | |
| 1106 offs += 2; | |
| 1107 if (offs == numPairs) | |
| 1108 break; | |
| 1109 } | |
| 1110 } | |
| 1111 } | |
| 1112 | |
| 1113 cur = 0; | |
| 1114 | |
| 1115 #ifdef SHOW_STAT2 | |
| 1116 if (position >= 0) | |
| 1117 { | |
| 1118 unsigned i; | |
| 1119 printf("\n pos = %4X", position); | |
| 1120 for (i = cur; i <= lenEnd; i++) | |
| 1121 printf("\nprice[%4X] = %d", position - cur + i, p->opt[i].price); | |
| 1122 } | |
| 1123 #endif | |
| 1124 | |
| 1125 for (;;) | |
| 1126 { | |
| 1127 UInt32 numAvailFull, newLen, numPairs, posPrev, state, posState, startLen; | |
| 1128 UInt32 curPrice, curAnd1Price, matchPrice, repMatchPrice; | |
| 1129 Bool nextIsChar; | |
| 1130 Byte curByte, matchByte; | |
| 1131 const Byte *data; | |
| 1132 COptimal *curOpt; | |
| 1133 COptimal *nextOpt; | |
| 1134 | |
| 1135 cur++; | |
| 1136 if (cur == lenEnd) | |
| 1137 return Backward(p, backRes, cur); | |
| 1138 | |
| 1139 newLen = ReadMatchDistances(p, &numPairs); | |
| 1140 if (newLen >= p->numFastBytes) | |
| 1141 { | |
| 1142 p->numPairs = numPairs; | |
| 1143 p->longestMatchLength = newLen; | |
| 1144 return Backward(p, backRes, cur); | |
| 1145 } | |
| 1146 position++; | |
| 1147 curOpt = &p->opt[cur]; | |
| 1148 posPrev = curOpt->posPrev; | |
| 1149 if (curOpt->prev1IsChar) | |
| 1150 { | |
| 1151 posPrev--; | |
| 1152 if (curOpt->prev2) | |
| 1153 { | |
| 1154 state = p->opt[curOpt->posPrev2].state; | |
| 1155 if (curOpt->backPrev2 < LZMA_NUM_REPS) | |
| 1156 state = kRepNextStates[state]; | |
| 1157 else | |
| 1158 state = kMatchNextStates[state]; | |
| 1159 } | |
| 1160 else | |
| 1161 state = p->opt[posPrev].state; | |
| 1162 state = kLiteralNextStates[state]; | |
| 1163 } | |
| 1164 else | |
| 1165 state = p->opt[posPrev].state; | |
| 1166 if (posPrev == cur - 1) | |
| 1167 { | |
| 1168 if (IsShortRep(curOpt)) | |
| 1169 state = kShortRepNextStates[state]; | |
| 1170 else | |
| 1171 state = kLiteralNextStates[state]; | |
| 1172 } | |
| 1173 else | |
| 1174 { | |
| 1175 UInt32 pos; | |
| 1176 const COptimal *prevOpt; | |
| 1177 if (curOpt->prev1IsChar && curOpt->prev2) | |
| 1178 { | |
| 1179 posPrev = curOpt->posPrev2; | |
| 1180 pos = curOpt->backPrev2; | |
| 1181 state = kRepNextStates[state]; | |
| 1182 } | |
| 1183 else | |
| 1184 { | |
| 1185 pos = curOpt->backPrev; | |
| 1186 if (pos < LZMA_NUM_REPS) | |
| 1187 state = kRepNextStates[state]; | |
| 1188 else | |
| 1189 state = kMatchNextStates[state]; | |
| 1190 } | |
| 1191 prevOpt = &p->opt[posPrev]; | |
| 1192 if (pos < LZMA_NUM_REPS) | |
| 1193 { | |
| 1194 UInt32 i; | |
| 1195 reps[0] = prevOpt->backs[pos]; | |
| 1196 for (i = 1; i <= pos; i++) | |
| 1197 reps[i] = prevOpt->backs[i - 1]; | |
| 1198 for (; i < LZMA_NUM_REPS; i++) | |
| 1199 reps[i] = prevOpt->backs[i]; | |
| 1200 } | |
| 1201 else | |
| 1202 { | |
| 1203 UInt32 i; | |
| 1204 reps[0] = (pos - LZMA_NUM_REPS); | |
| 1205 for (i = 1; i < LZMA_NUM_REPS; i++) | |
| 1206 reps[i] = prevOpt->backs[i - 1]; | |
| 1207 } | |
| 1208 } | |
| 1209 curOpt->state = (CState)state; | |
| 1210 | |
| 1211 curOpt->backs[0] = reps[0]; | |
| 1212 curOpt->backs[1] = reps[1]; | |
| 1213 curOpt->backs[2] = reps[2]; | |
| 1214 curOpt->backs[3] = reps[3]; | |
| 1215 | |
| 1216 curPrice = curOpt->price; | |
| 1217 nextIsChar = False; | |
| 1218 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; | |
| 1219 curByte = *data; | |
| 1220 matchByte = *(data - (reps[0] + 1)); | |
| 1221 | |
| 1222 posState = (position & p->pbMask); | |
| 1223 | |
| 1224 curAnd1Price = curPrice + GET_PRICE_0(p->isMatch[state][posState]); | |
| 1225 { | |
| 1226 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1)); | |
| 1227 curAnd1Price += | |
| 1228 (!IsCharState(state) ? | |
| 1229 LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) : | |
| 1230 LitEnc_GetPrice(probs, curByte, p->ProbPrices)); | |
| 1231 } | |
| 1232 | |
| 1233 nextOpt = &p->opt[cur + 1]; | |
| 1234 | |
| 1235 if (curAnd1Price < nextOpt->price) | |
| 1236 { | |
| 1237 nextOpt->price = curAnd1Price; | |
| 1238 nextOpt->posPrev = cur; | |
| 1239 MakeAsChar(nextOpt); | |
| 1240 nextIsChar = True; | |
| 1241 } | |
| 1242 | |
| 1243 matchPrice = curPrice + GET_PRICE_1(p->isMatch[state][posState]); | |
| 1244 repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[state]); | |
| 1245 | |
| 1246 if (matchByte == curByte && !(nextOpt->posPrev < cur && nextOpt->backPrev ==
0)) | |
| 1247 { | |
| 1248 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, state, posState)
; | |
| 1249 if (shortRepPrice <= nextOpt->price) | |
| 1250 { | |
| 1251 nextOpt->price = shortRepPrice; | |
| 1252 nextOpt->posPrev = cur; | |
| 1253 MakeAsShortRep(nextOpt); | |
| 1254 nextIsChar = True; | |
| 1255 } | |
| 1256 } | |
| 1257 numAvailFull = p->numAvail; | |
| 1258 { | |
| 1259 UInt32 temp = kNumOpts - 1 - cur; | |
| 1260 if (temp < numAvailFull) | |
| 1261 numAvailFull = temp; | |
| 1262 } | |
| 1263 | |
| 1264 if (numAvailFull < 2) | |
| 1265 continue; | |
| 1266 numAvail = (numAvailFull <= p->numFastBytes ? numAvailFull : p->numFastBytes
); | |
| 1267 | |
| 1268 if (!nextIsChar && matchByte != curByte) /* speed optimization */ | |
| 1269 { | |
| 1270 /* try Literal + rep0 */ | |
| 1271 UInt32 temp; | |
| 1272 UInt32 lenTest2; | |
| 1273 const Byte *data2 = data - (reps[0] + 1); | |
| 1274 UInt32 limit = p->numFastBytes + 1; | |
| 1275 if (limit > numAvailFull) | |
| 1276 limit = numAvailFull; | |
| 1277 | |
| 1278 for (temp = 1; temp < limit && data[temp] == data2[temp]; temp++); | |
| 1279 lenTest2 = temp - 1; | |
| 1280 if (lenTest2 >= 2) | |
| 1281 { | |
| 1282 UInt32 state2 = kLiteralNextStates[state]; | |
| 1283 UInt32 posStateNext = (position + 1) & p->pbMask; | |
| 1284 UInt32 nextRepMatchPrice = curAnd1Price + | |
| 1285 GET_PRICE_1(p->isMatch[state2][posStateNext]) + | |
| 1286 GET_PRICE_1(p->isRep[state2]); | |
| 1287 /* for (; lenTest2 >= 2; lenTest2--) */ | |
| 1288 { | |
| 1289 UInt32 curAndLenPrice; | |
| 1290 COptimal *opt; | |
| 1291 UInt32 offset = cur + 1 + lenTest2; | |
| 1292 while (lenEnd < offset) | |
| 1293 p->opt[++lenEnd].price = kInfinityPrice; | |
| 1294 curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state
2, posStateNext); | |
| 1295 opt = &p->opt[offset]; | |
| 1296 if (curAndLenPrice < opt->price) | |
| 1297 { | |
| 1298 opt->price = curAndLenPrice; | |
| 1299 opt->posPrev = cur + 1; | |
| 1300 opt->backPrev = 0; | |
| 1301 opt->prev1IsChar = True; | |
| 1302 opt->prev2 = False; | |
| 1303 } | |
| 1304 } | |
| 1305 } | |
| 1306 } | |
| 1307 | |
| 1308 startLen = 2; /* speed optimization */ | |
| 1309 { | |
| 1310 UInt32 repIndex; | |
| 1311 for (repIndex = 0; repIndex < LZMA_NUM_REPS; repIndex++) | |
| 1312 { | |
| 1313 UInt32 lenTest; | |
| 1314 UInt32 lenTestTemp; | |
| 1315 UInt32 price; | |
| 1316 const Byte *data2 = data - (reps[repIndex] + 1); | |
| 1317 if (data[0] != data2[0] || data[1] != data2[1]) | |
| 1318 continue; | |
| 1319 for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; l
enTest++); | |
| 1320 while (lenEnd < cur + lenTest) | |
| 1321 p->opt[++lenEnd].price = kInfinityPrice; | |
| 1322 lenTestTemp = lenTest; | |
| 1323 price = repMatchPrice + GetPureRepPrice(p, repIndex, state, posState); | |
| 1324 do | |
| 1325 { | |
| 1326 UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][lenTest -
2]; | |
| 1327 COptimal *opt = &p->opt[cur + lenTest]; | |
| 1328 if (curAndLenPrice < opt->price) | |
| 1329 { | |
| 1330 opt->price = curAndLenPrice; | |
| 1331 opt->posPrev = cur; | |
| 1332 opt->backPrev = repIndex; | |
| 1333 opt->prev1IsChar = False; | |
| 1334 } | |
| 1335 } | |
| 1336 while (--lenTest >= 2); | |
| 1337 lenTest = lenTestTemp; | |
| 1338 | |
| 1339 if (repIndex == 0) | |
| 1340 startLen = lenTest + 1; | |
| 1341 | |
| 1342 /* if (_maxMode) */ | |
| 1343 { | |
| 1344 UInt32 lenTest2 = lenTest + 1; | |
| 1345 UInt32 limit = lenTest2 + p->numFastBytes; | |
| 1346 UInt32 nextRepMatchPrice; | |
| 1347 if (limit > numAvailFull) | |
| 1348 limit = numAvailFull; | |
| 1349 for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2
++); | |
| 1350 lenTest2 -= lenTest + 1; | |
| 1351 if (lenTest2 >= 2) | |
| 1352 { | |
| 1353 UInt32 state2 = kRepNextStates[state]; | |
| 1354 UInt32 posStateNext = (position + lenTest) & p->pbMask; | |
| 1355 UInt32 curAndLenCharPrice = | |
| 1356 price + p->repLenEnc.prices[posState][lenTest - 2] + | |
| 1357 GET_PRICE_0(p->isMatch[state2][posStateNext]) + | |
| 1358 LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTes
t - 1]), | |
| 1359 data[lenTest], data2[lenTest], p->ProbPrices); | |
| 1360 state2 = kLiteralNextStates[state2]; | |
| 1361 posStateNext = (position + lenTest + 1) & p->pbMask; | |
| 1362 nextRepMatchPrice = curAndLenCharPrice + | |
| 1363 GET_PRICE_1(p->isMatch[state2][posStateNext]) + | |
| 1364 GET_PRICE_1(p->isRep[state2]); | |
| 1365 | |
| 1366 /* for (; lenTest2 >= 2; lenTest2--) */ | |
| 1367 { | |
| 1368 UInt32 curAndLenPrice; | |
| 1369 COptimal *opt; | |
| 1370 UInt32 offset = cur + lenTest + 1 + lenTest2; | |
| 1371 while (lenEnd < offset) | |
| 1372 p->opt[++lenEnd].price = kInfinityPrice; | |
| 1373 curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, s
tate2, posStateNext); | |
| 1374 opt = &p->opt[offset]; | |
| 1375 if (curAndLenPrice < opt->price) | |
| 1376 { | |
| 1377 opt->price = curAndLenPrice; | |
| 1378 opt->posPrev = cur + lenTest + 1; | |
| 1379 opt->backPrev = 0; | |
| 1380 opt->prev1IsChar = True; | |
| 1381 opt->prev2 = True; | |
| 1382 opt->posPrev2 = cur; | |
| 1383 opt->backPrev2 = repIndex; | |
| 1384 } | |
| 1385 } | |
| 1386 } | |
| 1387 } | |
| 1388 } | |
| 1389 } | |
| 1390 /* for (UInt32 lenTest = 2; lenTest <= newLen; lenTest++) */ | |
| 1391 if (newLen > numAvail) | |
| 1392 { | |
| 1393 newLen = numAvail; | |
| 1394 for (numPairs = 0; newLen > matches[numPairs]; numPairs += 2); | |
| 1395 matches[numPairs] = newLen; | |
| 1396 numPairs += 2; | |
| 1397 } | |
| 1398 if (newLen >= startLen) | |
| 1399 { | |
| 1400 UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[state]); | |
| 1401 UInt32 offs, curBack, posSlot; | |
| 1402 UInt32 lenTest; | |
| 1403 while (lenEnd < cur + newLen) | |
| 1404 p->opt[++lenEnd].price = kInfinityPrice; | |
| 1405 | |
| 1406 offs = 0; | |
| 1407 while (startLen > matches[offs]) | |
| 1408 offs += 2; | |
| 1409 curBack = matches[offs + 1]; | |
| 1410 GetPosSlot2(curBack, posSlot); | |
| 1411 for (lenTest = /*2*/ startLen; ; lenTest++) | |
| 1412 { | |
| 1413 UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][le
nTest - LZMA_MATCH_LEN_MIN]; | |
| 1414 UInt32 lenToPosState = GetLenToPosState(lenTest); | |
| 1415 COptimal *opt; | |
| 1416 if (curBack < kNumFullDistances) | |
| 1417 curAndLenPrice += p->distancesPrices[lenToPosState][curBack]; | |
| 1418 else | |
| 1419 curAndLenPrice += p->posSlotPrices[lenToPosState][posSlot] + p->alignP
rices[curBack & kAlignMask]; | |
| 1420 | |
| 1421 opt = &p->opt[cur + lenTest]; | |
| 1422 if (curAndLenPrice < opt->price) | |
| 1423 { | |
| 1424 opt->price = curAndLenPrice; | |
| 1425 opt->posPrev = cur; | |
| 1426 opt->backPrev = curBack + LZMA_NUM_REPS; | |
| 1427 opt->prev1IsChar = False; | |
| 1428 } | |
| 1429 | |
| 1430 if (/*_maxMode && */lenTest == matches[offs]) | |
| 1431 { | |
| 1432 /* Try Match + Literal + Rep0 */ | |
| 1433 const Byte *data2 = data - (curBack + 1); | |
| 1434 UInt32 lenTest2 = lenTest + 1; | |
| 1435 UInt32 limit = lenTest2 + p->numFastBytes; | |
| 1436 UInt32 nextRepMatchPrice; | |
| 1437 if (limit > numAvailFull) | |
| 1438 limit = numAvailFull; | |
| 1439 for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2
++); | |
| 1440 lenTest2 -= lenTest + 1; | |
| 1441 if (lenTest2 >= 2) | |
| 1442 { | |
| 1443 UInt32 state2 = kMatchNextStates[state]; | |
| 1444 UInt32 posStateNext = (position + lenTest) & p->pbMask; | |
| 1445 UInt32 curAndLenCharPrice = curAndLenPrice + | |
| 1446 GET_PRICE_0(p->isMatch[state2][posStateNext]) + | |
| 1447 LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTes
t - 1]), | |
| 1448 data[lenTest], data2[lenTest], p->ProbPrices); | |
| 1449 state2 = kLiteralNextStates[state2]; | |
| 1450 posStateNext = (posStateNext + 1) & p->pbMask; | |
| 1451 nextRepMatchPrice = curAndLenCharPrice + | |
| 1452 GET_PRICE_1(p->isMatch[state2][posStateNext]) + | |
| 1453 GET_PRICE_1(p->isRep[state2]); | |
| 1454 | |
| 1455 /* for (; lenTest2 >= 2; lenTest2--) */ | |
| 1456 { | |
| 1457 UInt32 offset = cur + lenTest + 1 + lenTest2; | |
| 1458 UInt32 curAndLenPrice; | |
| 1459 COptimal *opt; | |
| 1460 while (lenEnd < offset) | |
| 1461 p->opt[++lenEnd].price = kInfinityPrice; | |
| 1462 curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, s
tate2, posStateNext); | |
| 1463 opt = &p->opt[offset]; | |
| 1464 if (curAndLenPrice < opt->price) | |
| 1465 { | |
| 1466 opt->price = curAndLenPrice; | |
| 1467 opt->posPrev = cur + lenTest + 1; | |
| 1468 opt->backPrev = 0; | |
| 1469 opt->prev1IsChar = True; | |
| 1470 opt->prev2 = True; | |
| 1471 opt->posPrev2 = cur; | |
| 1472 opt->backPrev2 = curBack + LZMA_NUM_REPS; | |
| 1473 } | |
| 1474 } | |
| 1475 } | |
| 1476 offs += 2; | |
| 1477 if (offs == numPairs) | |
| 1478 break; | |
| 1479 curBack = matches[offs + 1]; | |
| 1480 if (curBack >= kNumFullDistances) | |
| 1481 GetPosSlot2(curBack, posSlot); | |
| 1482 } | |
| 1483 } | |
| 1484 } | |
| 1485 } | |
| 1486 } | |
| 1487 | |
| 1488 #define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist)) | |
| 1489 | |
| 1490 static UInt32 GetOptimumFast(CLzmaEnc *p, UInt32 *backRes) | |
| 1491 { | |
| 1492 UInt32 numAvail, mainLen, mainDist, numPairs, repIndex, repLen, i; | |
| 1493 const Byte *data; | |
| 1494 const UInt32 *matches; | |
| 1495 | |
| 1496 if (p->additionalOffset == 0) | |
| 1497 mainLen = ReadMatchDistances(p, &numPairs); | |
| 1498 else | |
| 1499 { | |
| 1500 mainLen = p->longestMatchLength; | |
| 1501 numPairs = p->numPairs; | |
| 1502 } | |
| 1503 | |
| 1504 numAvail = p->numAvail; | |
| 1505 *backRes = (UInt32)-1; | |
| 1506 if (numAvail < 2) | |
| 1507 return 1; | |
| 1508 if (numAvail > LZMA_MATCH_LEN_MAX) | |
| 1509 numAvail = LZMA_MATCH_LEN_MAX; | |
| 1510 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; | |
| 1511 | |
| 1512 repLen = repIndex = 0; | |
| 1513 for (i = 0; i < LZMA_NUM_REPS; i++) | |
| 1514 { | |
| 1515 UInt32 len; | |
| 1516 const Byte *data2 = data - (p->reps[i] + 1); | |
| 1517 if (data[0] != data2[0] || data[1] != data2[1]) | |
| 1518 continue; | |
| 1519 for (len = 2; len < numAvail && data[len] == data2[len]; len++); | |
| 1520 if (len >= p->numFastBytes) | |
| 1521 { | |
| 1522 *backRes = i; | |
| 1523 MovePos(p, len - 1); | |
| 1524 return len; | |
| 1525 } | |
| 1526 if (len > repLen) | |
| 1527 { | |
| 1528 repIndex = i; | |
| 1529 repLen = len; | |
| 1530 } | |
| 1531 } | |
| 1532 | |
| 1533 matches = p->matches; | |
| 1534 if (mainLen >= p->numFastBytes) | |
| 1535 { | |
| 1536 *backRes = matches[numPairs - 1] + LZMA_NUM_REPS; | |
| 1537 MovePos(p, mainLen - 1); | |
| 1538 return mainLen; | |
| 1539 } | |
| 1540 | |
| 1541 mainDist = 0; /* for GCC */ | |
| 1542 if (mainLen >= 2) | |
| 1543 { | |
| 1544 mainDist = matches[numPairs - 1]; | |
| 1545 while (numPairs > 2 && mainLen == matches[numPairs - 4] + 1) | |
| 1546 { | |
| 1547 if (!ChangePair(matches[numPairs - 3], mainDist)) | |
| 1548 break; | |
| 1549 numPairs -= 2; | |
| 1550 mainLen = matches[numPairs - 2]; | |
| 1551 mainDist = matches[numPairs - 1]; | |
| 1552 } | |
| 1553 if (mainLen == 2 && mainDist >= 0x80) | |
| 1554 mainLen = 1; | |
| 1555 } | |
| 1556 | |
| 1557 if (repLen >= 2 && ( | |
| 1558 (repLen + 1 >= mainLen) || | |
| 1559 (repLen + 2 >= mainLen && mainDist >= (1 << 9)) || | |
| 1560 (repLen + 3 >= mainLen && mainDist >= (1 << 15)))) | |
| 1561 { | |
| 1562 *backRes = repIndex; | |
| 1563 MovePos(p, repLen - 1); | |
| 1564 return repLen; | |
| 1565 } | |
| 1566 | |
| 1567 if (mainLen < 2 || numAvail <= 2) | |
| 1568 return 1; | |
| 1569 | |
| 1570 p->longestMatchLength = ReadMatchDistances(p, &p->numPairs); | |
| 1571 if (p->longestMatchLength >= 2) | |
| 1572 { | |
| 1573 UInt32 newDistance = matches[p->numPairs - 1]; | |
| 1574 if ((p->longestMatchLength >= mainLen && newDistance < mainDist) || | |
| 1575 (p->longestMatchLength == mainLen + 1 && !ChangePair(mainDist, newDistan
ce)) || | |
| 1576 (p->longestMatchLength > mainLen + 1) || | |
| 1577 (p->longestMatchLength + 1 >= mainLen && mainLen >= 3 && ChangePair(newD
istance, mainDist))) | |
| 1578 return 1; | |
| 1579 } | |
| 1580 | |
| 1581 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; | |
| 1582 for (i = 0; i < LZMA_NUM_REPS; i++) | |
| 1583 { | |
| 1584 UInt32 len, limit; | |
| 1585 const Byte *data2 = data - (p->reps[i] + 1); | |
| 1586 if (data[0] != data2[0] || data[1] != data2[1]) | |
| 1587 continue; | |
| 1588 limit = mainLen - 1; | |
| 1589 for (len = 2; len < limit && data[len] == data2[len]; len++); | |
| 1590 if (len >= limit) | |
| 1591 return 1; | |
| 1592 } | |
| 1593 *backRes = mainDist + LZMA_NUM_REPS; | |
| 1594 MovePos(p, mainLen - 2); | |
| 1595 return mainLen; | |
| 1596 } | |
| 1597 | |
| 1598 static void WriteEndMarker(CLzmaEnc *p, UInt32 posState) | |
| 1599 { | |
| 1600 UInt32 len; | |
| 1601 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1); | |
| 1602 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0); | |
| 1603 p->state = kMatchNextStates[p->state]; | |
| 1604 len = LZMA_MATCH_LEN_MIN; | |
| 1605 LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fas
tMode, p->ProbPrices); | |
| 1606 RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBit
s, (1 << kNumPosSlotBits) - 1); | |
| 1607 RangeEnc_EncodeDirectBits(&p->rc, (((UInt32)1 << 30) - 1) >> kNumAlignBits, 30
- kNumAlignBits); | |
| 1608 RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, kAlignMask); | |
| 1609 } | |
| 1610 | |
| 1611 static SRes CheckErrors(CLzmaEnc *p) | |
| 1612 { | |
| 1613 if (p->result != SZ_OK) | |
| 1614 return p->result; | |
| 1615 if (p->rc.res != SZ_OK) | |
| 1616 p->result = SZ_ERROR_WRITE; | |
| 1617 if (p->matchFinderBase.result != SZ_OK) | |
| 1618 p->result = SZ_ERROR_READ; | |
| 1619 if (p->result != SZ_OK) | |
| 1620 p->finished = True; | |
| 1621 return p->result; | |
| 1622 } | |
| 1623 | |
| 1624 static SRes Flush(CLzmaEnc *p, UInt32 nowPos) | |
| 1625 { | |
| 1626 /* ReleaseMFStream(); */ | |
| 1627 p->finished = True; | |
| 1628 if (p->writeEndMark) | |
| 1629 WriteEndMarker(p, nowPos & p->pbMask); | |
| 1630 RangeEnc_FlushData(&p->rc); | |
| 1631 RangeEnc_FlushStream(&p->rc); | |
| 1632 return CheckErrors(p); | |
| 1633 } | |
| 1634 | |
| 1635 static void FillAlignPrices(CLzmaEnc *p) | |
| 1636 { | |
| 1637 UInt32 i; | |
| 1638 for (i = 0; i < kAlignTableSize; i++) | |
| 1639 p->alignPrices[i] = RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits
, i, p->ProbPrices); | |
| 1640 p->alignPriceCount = 0; | |
| 1641 } | |
| 1642 | |
| 1643 static void FillDistancesPrices(CLzmaEnc *p) | |
| 1644 { | |
| 1645 UInt32 tempPrices[kNumFullDistances]; | |
| 1646 UInt32 i, lenToPosState; | |
| 1647 for (i = kStartPosModelIndex; i < kNumFullDistances; i++) | |
| 1648 { | |
| 1649 UInt32 posSlot = GetPosSlot1(i); | |
| 1650 UInt32 footerBits = ((posSlot >> 1) - 1); | |
| 1651 UInt32 base = ((2 | (posSlot & 1)) << footerBits); | |
| 1652 tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base - posSlot - 1,
footerBits, i - base, p->ProbPrices); | |
| 1653 } | |
| 1654 | |
| 1655 for (lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++) | |
| 1656 { | |
| 1657 UInt32 posSlot; | |
| 1658 const CLzmaProb *encoder = p->posSlotEncoder[lenToPosState]; | |
| 1659 UInt32 *posSlotPrices = p->posSlotPrices[lenToPosState]; | |
| 1660 for (posSlot = 0; posSlot < p->distTableSize; posSlot++) | |
| 1661 posSlotPrices[posSlot] = RcTree_GetPrice(encoder, kNumPosSlotBits, posSlot
, p->ProbPrices); | |
| 1662 for (posSlot = kEndPosModelIndex; posSlot < p->distTableSize; posSlot++) | |
| 1663 posSlotPrices[posSlot] += ((((posSlot >> 1) - 1) - kNumAlignBits) << kNumB
itPriceShiftBits); | |
| 1664 | |
| 1665 { | |
| 1666 UInt32 *distancesPrices = p->distancesPrices[lenToPosState]; | |
| 1667 UInt32 i; | |
| 1668 for (i = 0; i < kStartPosModelIndex; i++) | |
| 1669 distancesPrices[i] = posSlotPrices[i]; | |
| 1670 for (; i < kNumFullDistances; i++) | |
| 1671 distancesPrices[i] = posSlotPrices[GetPosSlot1(i)] + tempPrices[i]; | |
| 1672 } | |
| 1673 } | |
| 1674 p->matchPriceCount = 0; | |
| 1675 } | |
| 1676 | |
| 1677 void LzmaEnc_Construct(CLzmaEnc *p) | |
| 1678 { | |
| 1679 RangeEnc_Construct(&p->rc); | |
| 1680 MatchFinder_Construct(&p->matchFinderBase); | |
| 1681 #ifndef _7ZIP_ST | |
| 1682 MatchFinderMt_Construct(&p->matchFinderMt); | |
| 1683 p->matchFinderMt.MatchFinder = &p->matchFinderBase; | |
| 1684 #endif | |
| 1685 | |
| 1686 { | |
| 1687 CLzmaEncProps props; | |
| 1688 LzmaEncProps_Init(&props); | |
| 1689 LzmaEnc_SetProps(p, &props); | |
| 1690 } | |
| 1691 | |
| 1692 #ifndef LZMA_LOG_BSR | |
| 1693 LzmaEnc_FastPosInit(p->g_FastPos); | |
| 1694 #endif | |
| 1695 | |
| 1696 LzmaEnc_InitPriceTables(p->ProbPrices); | |
| 1697 p->litProbs = 0; | |
| 1698 p->saveState.litProbs = 0; | |
| 1699 } | |
| 1700 | |
| 1701 CLzmaEncHandle LzmaEnc_Create(ISzAlloc *alloc) | |
| 1702 { | |
| 1703 void *p; | |
| 1704 p = alloc->Alloc(alloc, sizeof(CLzmaEnc)); | |
| 1705 if (p != 0) | |
| 1706 LzmaEnc_Construct((CLzmaEnc *)p); | |
| 1707 return p; | |
| 1708 } | |
| 1709 | |
| 1710 void LzmaEnc_FreeLits(CLzmaEnc *p, ISzAlloc *alloc) | |
| 1711 { | |
| 1712 alloc->Free(alloc, p->litProbs); | |
| 1713 alloc->Free(alloc, p->saveState.litProbs); | |
| 1714 p->litProbs = 0; | |
| 1715 p->saveState.litProbs = 0; | |
| 1716 } | |
| 1717 | |
| 1718 void LzmaEnc_Destruct(CLzmaEnc *p, ISzAlloc *alloc, ISzAlloc *allocBig) | |
| 1719 { | |
| 1720 #ifndef _7ZIP_ST | |
| 1721 MatchFinderMt_Destruct(&p->matchFinderMt, allocBig); | |
| 1722 #endif | |
| 1723 MatchFinder_Free(&p->matchFinderBase, allocBig); | |
| 1724 LzmaEnc_FreeLits(p, alloc); | |
| 1725 RangeEnc_Free(&p->rc, alloc); | |
| 1726 } | |
| 1727 | |
| 1728 void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAlloc *alloc, ISzAlloc *allocBig) | |
| 1729 { | |
| 1730 LzmaEnc_Destruct((CLzmaEnc *)p, alloc, allocBig); | |
| 1731 alloc->Free(alloc, p); | |
| 1732 } | |
| 1733 | |
| 1734 static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, Bool useLimits, UInt32 maxPackSize
, UInt32 maxUnpackSize) | |
| 1735 { | |
| 1736 UInt32 nowPos32, startPos32; | |
| 1737 if (p->needInit) | |
| 1738 { | |
| 1739 p->matchFinder.Init(p->matchFinderObj); | |
| 1740 p->needInit = 0; | |
| 1741 } | |
| 1742 | |
| 1743 if (p->finished) | |
| 1744 return p->result; | |
| 1745 RINOK(CheckErrors(p)); | |
| 1746 | |
| 1747 nowPos32 = (UInt32)p->nowPos64; | |
| 1748 startPos32 = nowPos32; | |
| 1749 | |
| 1750 if (p->nowPos64 == 0) | |
| 1751 { | |
| 1752 UInt32 numPairs; | |
| 1753 Byte curByte; | |
| 1754 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0) | |
| 1755 return Flush(p, nowPos32); | |
| 1756 ReadMatchDistances(p, &numPairs); | |
| 1757 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][0], 0); | |
| 1758 p->state = kLiteralNextStates[p->state]; | |
| 1759 curByte = p->matchFinder.GetIndexByte(p->matchFinderObj, 0 - p->additionalOf
fset); | |
| 1760 LitEnc_Encode(&p->rc, p->litProbs, curByte); | |
| 1761 p->additionalOffset--; | |
| 1762 nowPos32++; | |
| 1763 } | |
| 1764 | |
| 1765 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) != 0) | |
| 1766 for (;;) | |
| 1767 { | |
| 1768 UInt32 pos, len, posState; | |
| 1769 | |
| 1770 if (p->fastMode) | |
| 1771 len = GetOptimumFast(p, &pos); | |
| 1772 else | |
| 1773 len = GetOptimum(p, nowPos32, &pos); | |
| 1774 | |
| 1775 #ifdef SHOW_STAT2 | |
| 1776 printf("\n pos = %4X, len = %d pos = %d", nowPos32, len, pos); | |
| 1777 #endif | |
| 1778 | |
| 1779 posState = nowPos32 & p->pbMask; | |
| 1780 if (len == 1 && pos == (UInt32)-1) | |
| 1781 { | |
| 1782 Byte curByte; | |
| 1783 CLzmaProb *probs; | |
| 1784 const Byte *data; | |
| 1785 | |
| 1786 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 0); | |
| 1787 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->addit
ionalOffset; | |
| 1788 curByte = *data; | |
| 1789 probs = LIT_PROBS(nowPos32, *(data - 1)); | |
| 1790 if (IsCharState(p->state)) | |
| 1791 LitEnc_Encode(&p->rc, probs, curByte); | |
| 1792 else | |
| 1793 LitEnc_EncodeMatched(&p->rc, probs, curByte, *(data - p->reps[0] - 1)); | |
| 1794 p->state = kLiteralNextStates[p->state]; | |
| 1795 } | |
| 1796 else | |
| 1797 { | |
| 1798 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1); | |
| 1799 if (pos < LZMA_NUM_REPS) | |
| 1800 { | |
| 1801 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 1); | |
| 1802 if (pos == 0) | |
| 1803 { | |
| 1804 RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 0); | |
| 1805 RangeEnc_EncodeBit(&p->rc, &p->isRep0Long[p->state][posState], ((len =
= 1) ? 0 : 1)); | |
| 1806 } | |
| 1807 else | |
| 1808 { | |
| 1809 UInt32 distance = p->reps[pos]; | |
| 1810 RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 1); | |
| 1811 if (pos == 1) | |
| 1812 RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 0); | |
| 1813 else | |
| 1814 { | |
| 1815 RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 1); | |
| 1816 RangeEnc_EncodeBit(&p->rc, &p->isRepG2[p->state], pos - 2); | |
| 1817 if (pos == 3) | |
| 1818 p->reps[3] = p->reps[2]; | |
| 1819 p->reps[2] = p->reps[1]; | |
| 1820 } | |
| 1821 p->reps[1] = p->reps[0]; | |
| 1822 p->reps[0] = distance; | |
| 1823 } | |
| 1824 if (len == 1) | |
| 1825 p->state = kShortRepNextStates[p->state]; | |
| 1826 else | |
| 1827 { | |
| 1828 LenEnc_Encode2(&p->repLenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posSta
te, !p->fastMode, p->ProbPrices); | |
| 1829 p->state = kRepNextStates[p->state]; | |
| 1830 } | |
| 1831 } | |
| 1832 else | |
| 1833 { | |
| 1834 UInt32 posSlot; | |
| 1835 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0); | |
| 1836 p->state = kMatchNextStates[p->state]; | |
| 1837 LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !
p->fastMode, p->ProbPrices); | |
| 1838 pos -= LZMA_NUM_REPS; | |
| 1839 GetPosSlot(pos, posSlot); | |
| 1840 RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosS
lotBits, posSlot); | |
| 1841 | |
| 1842 if (posSlot >= kStartPosModelIndex) | |
| 1843 { | |
| 1844 UInt32 footerBits = ((posSlot >> 1) - 1); | |
| 1845 UInt32 base = ((2 | (posSlot & 1)) << footerBits); | |
| 1846 UInt32 posReduced = pos - base; | |
| 1847 | |
| 1848 if (posSlot < kEndPosModelIndex) | |
| 1849 RcTree_ReverseEncode(&p->rc, p->posEncoders + base - posSlot - 1, fo
oterBits, posReduced); | |
| 1850 else | |
| 1851 { | |
| 1852 RangeEnc_EncodeDirectBits(&p->rc, posReduced >> kNumAlignBits, foote
rBits - kNumAlignBits); | |
| 1853 RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, posR
educed & kAlignMask); | |
| 1854 p->alignPriceCount++; | |
| 1855 } | |
| 1856 } | |
| 1857 p->reps[3] = p->reps[2]; | |
| 1858 p->reps[2] = p->reps[1]; | |
| 1859 p->reps[1] = p->reps[0]; | |
| 1860 p->reps[0] = pos; | |
| 1861 p->matchPriceCount++; | |
| 1862 } | |
| 1863 } | |
| 1864 p->additionalOffset -= len; | |
| 1865 nowPos32 += len; | |
| 1866 if (p->additionalOffset == 0) | |
| 1867 { | |
| 1868 UInt32 processed; | |
| 1869 if (!p->fastMode) | |
| 1870 { | |
| 1871 if (p->matchPriceCount >= (1 << 7)) | |
| 1872 FillDistancesPrices(p); | |
| 1873 if (p->alignPriceCount >= kAlignTableSize) | |
| 1874 FillAlignPrices(p); | |
| 1875 } | |
| 1876 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0) | |
| 1877 break; | |
| 1878 processed = nowPos32 - startPos32; | |
| 1879 if (useLimits) | |
| 1880 { | |
| 1881 if (processed + kNumOpts + 300 >= maxUnpackSize || | |
| 1882 RangeEnc_GetProcessed(&p->rc) + kNumOpts * 2 >= maxPackSize) | |
| 1883 break; | |
| 1884 } | |
| 1885 else if (processed >= (1 << 15)) | |
| 1886 { | |
| 1887 p->nowPos64 += nowPos32 - startPos32; | |
| 1888 return CheckErrors(p); | |
| 1889 } | |
| 1890 } | |
| 1891 } | |
| 1892 p->nowPos64 += nowPos32 - startPos32; | |
| 1893 return Flush(p, nowPos32); | |
| 1894 } | |
| 1895 | |
| 1896 #define kBigHashDicLimit ((UInt32)1 << 24) | |
| 1897 | |
| 1898 static SRes LzmaEnc_Alloc(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, I
SzAlloc *allocBig) | |
| 1899 { | |
| 1900 UInt32 beforeSize = kNumOpts; | |
| 1901 Bool btMode; | |
| 1902 if (!RangeEnc_Alloc(&p->rc, alloc)) | |
| 1903 return SZ_ERROR_MEM; | |
| 1904 btMode = (p->matchFinderBase.btMode != 0); | |
| 1905 #ifndef _7ZIP_ST | |
| 1906 p->mtMode = (p->multiThread && !p->fastMode && btMode); | |
| 1907 #endif | |
| 1908 | |
| 1909 { | |
| 1910 unsigned lclp = p->lc + p->lp; | |
| 1911 if (p->litProbs == 0 || p->saveState.litProbs == 0 || p->lclp != lclp) | |
| 1912 { | |
| 1913 LzmaEnc_FreeLits(p, alloc); | |
| 1914 p->litProbs = (CLzmaProb *)alloc->Alloc(alloc, (0x300 << lclp) * sizeof(CL
zmaProb)); | |
| 1915 p->saveState.litProbs = (CLzmaProb *)alloc->Alloc(alloc, (0x300 << lclp) *
sizeof(CLzmaProb)); | |
| 1916 if (p->litProbs == 0 || p->saveState.litProbs == 0) | |
| 1917 { | |
| 1918 LzmaEnc_FreeLits(p, alloc); | |
| 1919 return SZ_ERROR_MEM; | |
| 1920 } | |
| 1921 p->lclp = lclp; | |
| 1922 } | |
| 1923 } | |
| 1924 | |
| 1925 p->matchFinderBase.bigHash = (p->dictSize > kBigHashDicLimit); | |
| 1926 | |
| 1927 if (beforeSize + p->dictSize < keepWindowSize) | |
| 1928 beforeSize = keepWindowSize - p->dictSize; | |
| 1929 | |
| 1930 #ifndef _7ZIP_ST | |
| 1931 if (p->mtMode) | |
| 1932 { | |
| 1933 RINOK(MatchFinderMt_Create(&p->matchFinderMt, p->dictSize, beforeSize, p->nu
mFastBytes, LZMA_MATCH_LEN_MAX, allocBig)); | |
| 1934 p->matchFinderObj = &p->matchFinderMt; | |
| 1935 MatchFinderMt_CreateVTable(&p->matchFinderMt, &p->matchFinder); | |
| 1936 } | |
| 1937 else | |
| 1938 #endif | |
| 1939 { | |
| 1940 if (!MatchFinder_Create(&p->matchFinderBase, p->dictSize, beforeSize, p->num
FastBytes, LZMA_MATCH_LEN_MAX, allocBig)) | |
| 1941 return SZ_ERROR_MEM; | |
| 1942 p->matchFinderObj = &p->matchFinderBase; | |
| 1943 MatchFinder_CreateVTable(&p->matchFinderBase, &p->matchFinder); | |
| 1944 } | |
| 1945 return SZ_OK; | |
| 1946 } | |
| 1947 | |
| 1948 void LzmaEnc_Init(CLzmaEnc *p) | |
| 1949 { | |
| 1950 UInt32 i; | |
| 1951 p->state = 0; | |
| 1952 for (i = 0 ; i < LZMA_NUM_REPS; i++) | |
| 1953 p->reps[i] = 0; | |
| 1954 | |
| 1955 RangeEnc_Init(&p->rc); | |
| 1956 | |
| 1957 | |
| 1958 for (i = 0; i < kNumStates; i++) | |
| 1959 { | |
| 1960 UInt32 j; | |
| 1961 for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++) | |
| 1962 { | |
| 1963 p->isMatch[i][j] = kProbInitValue; | |
| 1964 p->isRep0Long[i][j] = kProbInitValue; | |
| 1965 } | |
| 1966 p->isRep[i] = kProbInitValue; | |
| 1967 p->isRepG0[i] = kProbInitValue; | |
| 1968 p->isRepG1[i] = kProbInitValue; | |
| 1969 p->isRepG2[i] = kProbInitValue; | |
| 1970 } | |
| 1971 | |
| 1972 { | |
| 1973 UInt32 num = 0x300 << (p->lp + p->lc); | |
| 1974 for (i = 0; i < num; i++) | |
| 1975 p->litProbs[i] = kProbInitValue; | |
| 1976 } | |
| 1977 | |
| 1978 { | |
| 1979 for (i = 0; i < kNumLenToPosStates; i++) | |
| 1980 { | |
| 1981 CLzmaProb *probs = p->posSlotEncoder[i]; | |
| 1982 UInt32 j; | |
| 1983 for (j = 0; j < (1 << kNumPosSlotBits); j++) | |
| 1984 probs[j] = kProbInitValue; | |
| 1985 } | |
| 1986 } | |
| 1987 { | |
| 1988 for (i = 0; i < kNumFullDistances - kEndPosModelIndex; i++) | |
| 1989 p->posEncoders[i] = kProbInitValue; | |
| 1990 } | |
| 1991 | |
| 1992 LenEnc_Init(&p->lenEnc.p); | |
| 1993 LenEnc_Init(&p->repLenEnc.p); | |
| 1994 | |
| 1995 for (i = 0; i < (1 << kNumAlignBits); i++) | |
| 1996 p->posAlignEncoder[i] = kProbInitValue; | |
| 1997 | |
| 1998 p->optimumEndIndex = 0; | |
| 1999 p->optimumCurrentIndex = 0; | |
| 2000 p->additionalOffset = 0; | |
| 2001 | |
| 2002 p->pbMask = (1 << p->pb) - 1; | |
| 2003 p->lpMask = (1 << p->lp) - 1; | |
| 2004 } | |
| 2005 | |
| 2006 void LzmaEnc_InitPrices(CLzmaEnc *p) | |
| 2007 { | |
| 2008 if (!p->fastMode) | |
| 2009 { | |
| 2010 FillDistancesPrices(p); | |
| 2011 FillAlignPrices(p); | |
| 2012 } | |
| 2013 | |
| 2014 p->lenEnc.tableSize = | |
| 2015 p->repLenEnc.tableSize = | |
| 2016 p->numFastBytes + 1 - LZMA_MATCH_LEN_MIN; | |
| 2017 LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, p->ProbPrices); | |
| 2018 LenPriceEnc_UpdateTables(&p->repLenEnc, 1 << p->pb, p->ProbPrices); | |
| 2019 } | |
| 2020 | |
| 2021 static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *a
lloc, ISzAlloc *allocBig) | |
| 2022 { | |
| 2023 UInt32 i; | |
| 2024 for (i = 0; i < (UInt32)kDicLogSizeMaxCompress; i++) | |
| 2025 if (p->dictSize <= ((UInt32)1 << i)) | |
| 2026 break; | |
| 2027 p->distTableSize = i * 2; | |
| 2028 | |
| 2029 p->finished = False; | |
| 2030 p->result = SZ_OK; | |
| 2031 RINOK(LzmaEnc_Alloc(p, keepWindowSize, alloc, allocBig)); | |
| 2032 LzmaEnc_Init(p); | |
| 2033 LzmaEnc_InitPrices(p); | |
| 2034 p->nowPos64 = 0; | |
| 2035 return SZ_OK; | |
| 2036 } | |
| 2037 | |
| 2038 static SRes LzmaEnc_Prepare(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInS
tream *inStream, | |
| 2039 ISzAlloc *alloc, ISzAlloc *allocBig) | |
| 2040 { | |
| 2041 CLzmaEnc *p = (CLzmaEnc *)pp; | |
| 2042 p->matchFinderBase.stream = inStream; | |
| 2043 p->needInit = 1; | |
| 2044 p->rc.outStream = outStream; | |
| 2045 return LzmaEnc_AllocAndInit(p, 0, alloc, allocBig); | |
| 2046 } | |
| 2047 | |
| 2048 SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle pp, | |
| 2049 ISeqInStream *inStream, UInt32 keepWindowSize, | |
| 2050 ISzAlloc *alloc, ISzAlloc *allocBig) | |
| 2051 { | |
| 2052 CLzmaEnc *p = (CLzmaEnc *)pp; | |
| 2053 p->matchFinderBase.stream = inStream; | |
| 2054 p->needInit = 1; | |
| 2055 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig); | |
| 2056 } | |
| 2057 | |
| 2058 static void LzmaEnc_SetInputBuf(CLzmaEnc *p, const Byte *src, SizeT srcLen) | |
| 2059 { | |
| 2060 p->matchFinderBase.directInput = 1; | |
| 2061 p->matchFinderBase.bufferBase = (Byte *)src; | |
| 2062 p->matchFinderBase.directInputRem = srcLen; | |
| 2063 } | |
| 2064 | |
| 2065 SRes LzmaEnc_MemPrepare(CLzmaEncHandle pp, const Byte *src, SizeT srcLen, | |
| 2066 UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig) | |
| 2067 { | |
| 2068 CLzmaEnc *p = (CLzmaEnc *)pp; | |
| 2069 LzmaEnc_SetInputBuf(p, src, srcLen); | |
| 2070 p->needInit = 1; | |
| 2071 | |
| 2072 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig); | |
| 2073 } | |
| 2074 | |
| 2075 void LzmaEnc_Finish(CLzmaEncHandle pp) | |
| 2076 { | |
| 2077 #ifndef _7ZIP_ST | |
| 2078 CLzmaEnc *p = (CLzmaEnc *)pp; | |
| 2079 if (p->mtMode) | |
| 2080 MatchFinderMt_ReleaseStream(&p->matchFinderMt); | |
| 2081 #else | |
| 2082 pp = pp; | |
| 2083 #endif | |
| 2084 } | |
| 2085 | |
| 2086 typedef struct | |
| 2087 { | |
| 2088 ISeqOutStream funcTable; | |
| 2089 Byte *data; | |
| 2090 SizeT rem; | |
| 2091 Bool overflow; | |
| 2092 } CSeqOutStreamBuf; | |
| 2093 | |
| 2094 static size_t MyWrite(void *pp, const void *data, size_t size) | |
| 2095 { | |
| 2096 CSeqOutStreamBuf *p = (CSeqOutStreamBuf *)pp; | |
| 2097 if (p->rem < size) | |
| 2098 { | |
| 2099 size = p->rem; | |
| 2100 p->overflow = True; | |
| 2101 } | |
| 2102 memcpy(p->data, data, size); | |
| 2103 p->rem -= size; | |
| 2104 p->data += size; | |
| 2105 return size; | |
| 2106 } | |
| 2107 | |
| 2108 | |
| 2109 UInt32 LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp) | |
| 2110 { | |
| 2111 const CLzmaEnc *p = (CLzmaEnc *)pp; | |
| 2112 return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj); | |
| 2113 } | |
| 2114 | |
| 2115 const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle pp) | |
| 2116 { | |
| 2117 const CLzmaEnc *p = (CLzmaEnc *)pp; | |
| 2118 return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additiona
lOffset; | |
| 2119 } | |
| 2120 | |
| 2121 SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle pp, Bool reInit, | |
| 2122 Byte *dest, size_t *destLen, UInt32 desiredPackSize, UInt32 *unpackSize) | |
| 2123 { | |
| 2124 CLzmaEnc *p = (CLzmaEnc *)pp; | |
| 2125 UInt64 nowPos64; | |
| 2126 SRes res; | |
| 2127 CSeqOutStreamBuf outStream; | |
| 2128 | |
| 2129 outStream.funcTable.Write = MyWrite; | |
| 2130 outStream.data = dest; | |
| 2131 outStream.rem = *destLen; | |
| 2132 outStream.overflow = False; | |
| 2133 | |
| 2134 p->writeEndMark = False; | |
| 2135 p->finished = False; | |
| 2136 p->result = SZ_OK; | |
| 2137 | |
| 2138 if (reInit) | |
| 2139 LzmaEnc_Init(p); | |
| 2140 LzmaEnc_InitPrices(p); | |
| 2141 nowPos64 = p->nowPos64; | |
| 2142 RangeEnc_Init(&p->rc); | |
| 2143 p->rc.outStream = &outStream.funcTable; | |
| 2144 | |
| 2145 res = LzmaEnc_CodeOneBlock(p, True, desiredPackSize, *unpackSize); | |
| 2146 | |
| 2147 *unpackSize = (UInt32)(p->nowPos64 - nowPos64); | |
| 2148 *destLen -= outStream.rem; | |
| 2149 if (outStream.overflow) | |
| 2150 return SZ_ERROR_OUTPUT_EOF; | |
| 2151 | |
| 2152 return res; | |
| 2153 } | |
| 2154 | |
| 2155 static SRes LzmaEnc_Encode2(CLzmaEnc *p, ICompressProgress *progress) | |
| 2156 { | |
| 2157 SRes res = SZ_OK; | |
| 2158 | |
| 2159 #ifndef _7ZIP_ST | |
| 2160 Byte allocaDummy[0x300]; | |
| 2161 int i = 0; | |
| 2162 for (i = 0; i < 16; i++) | |
| 2163 allocaDummy[i] = (Byte)i; | |
| 2164 #endif | |
| 2165 | |
| 2166 for (;;) | |
| 2167 { | |
| 2168 res = LzmaEnc_CodeOneBlock(p, False, 0, 0); | |
| 2169 if (res != SZ_OK || p->finished != 0) | |
| 2170 break; | |
| 2171 if (progress != 0) | |
| 2172 { | |
| 2173 res = progress->Progress(progress, p->nowPos64, RangeEnc_GetProcessed(&p->
rc)); | |
| 2174 if (res != SZ_OK) | |
| 2175 { | |
| 2176 res = SZ_ERROR_PROGRESS; | |
| 2177 break; | |
| 2178 } | |
| 2179 } | |
| 2180 } | |
| 2181 LzmaEnc_Finish(p); | |
| 2182 return res; | |
| 2183 } | |
| 2184 | |
| 2185 SRes LzmaEnc_Encode(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *i
nStream, ICompressProgress *progress, | |
| 2186 ISzAlloc *alloc, ISzAlloc *allocBig) | |
| 2187 { | |
| 2188 RINOK(LzmaEnc_Prepare(pp, outStream, inStream, alloc, allocBig)); | |
| 2189 return LzmaEnc_Encode2((CLzmaEnc *)pp, progress); | |
| 2190 } | |
| 2191 | |
| 2192 SRes LzmaEnc_WriteProperties(CLzmaEncHandle pp, Byte *props, SizeT *size) | |
| 2193 { | |
| 2194 CLzmaEnc *p = (CLzmaEnc *)pp; | |
| 2195 int i; | |
| 2196 UInt32 dictSize = p->dictSize; | |
| 2197 if (*size < LZMA_PROPS_SIZE) | |
| 2198 return SZ_ERROR_PARAM; | |
| 2199 *size = LZMA_PROPS_SIZE; | |
| 2200 props[0] = (Byte)((p->pb * 5 + p->lp) * 9 + p->lc); | |
| 2201 | |
| 2202 for (i = 11; i <= 30; i++) | |
| 2203 { | |
| 2204 if (dictSize <= ((UInt32)2 << i)) | |
| 2205 { | |
| 2206 dictSize = (2 << i); | |
| 2207 break; | |
| 2208 } | |
| 2209 if (dictSize <= ((UInt32)3 << i)) | |
| 2210 { | |
| 2211 dictSize = (3 << i); | |
| 2212 break; | |
| 2213 } | |
| 2214 } | |
| 2215 | |
| 2216 for (i = 0; i < 4; i++) | |
| 2217 props[1 + i] = (Byte)(dictSize >> (8 * i)); | |
| 2218 return SZ_OK; | |
| 2219 } | |
| 2220 | |
| 2221 SRes LzmaEnc_MemEncode(CLzmaEncHandle pp, Byte *dest, SizeT *destLen, const Byte
*src, SizeT srcLen, | |
| 2222 int writeEndMark, ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *al
locBig) | |
| 2223 { | |
| 2224 SRes res; | |
| 2225 CLzmaEnc *p = (CLzmaEnc *)pp; | |
| 2226 | |
| 2227 CSeqOutStreamBuf outStream; | |
| 2228 | |
| 2229 LzmaEnc_SetInputBuf(p, src, srcLen); | |
| 2230 | |
| 2231 outStream.funcTable.Write = MyWrite; | |
| 2232 outStream.data = dest; | |
| 2233 outStream.rem = *destLen; | |
| 2234 outStream.overflow = False; | |
| 2235 | |
| 2236 p->writeEndMark = writeEndMark; | |
| 2237 | |
| 2238 p->rc.outStream = &outStream.funcTable; | |
| 2239 res = LzmaEnc_MemPrepare(pp, src, srcLen, 0, alloc, allocBig); | |
| 2240 if (res == SZ_OK) | |
| 2241 res = LzmaEnc_Encode2(p, progress); | |
| 2242 | |
| 2243 *destLen -= outStream.rem; | |
| 2244 if (outStream.overflow) | |
| 2245 return SZ_ERROR_OUTPUT_EOF; | |
| 2246 return res; | |
| 2247 } | |
| 2248 | |
| 2249 SRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen, | |
| 2250 const CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeE
ndMark, | |
| 2251 ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig) | |
| 2252 { | |
| 2253 CLzmaEnc *p = (CLzmaEnc *)LzmaEnc_Create(alloc); | |
| 2254 SRes res; | |
| 2255 if (p == 0) | |
| 2256 return SZ_ERROR_MEM; | |
| 2257 | |
| 2258 res = LzmaEnc_SetProps(p, props); | |
| 2259 if (res == SZ_OK) | |
| 2260 { | |
| 2261 res = LzmaEnc_WriteProperties(p, propsEncoded, propsSize); | |
| 2262 if (res == SZ_OK) | |
| 2263 res = LzmaEnc_MemEncode(p, dest, destLen, src, srcLen, | |
| 2264 writeEndMark, progress, alloc, allocBig); | |
| 2265 } | |
| 2266 | |
| 2267 LzmaEnc_Destroy(p, alloc, allocBig); | |
| 2268 return res; | |
| 2269 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 658573004:
Updating to new OTS repo from https://github.com/khaledhosny/ots.git (Closed)
Base URL: https://chromium.googlesource.com/external/ots@master