1/* 2 LzmaStateDecode.c 3 LZMA Decoder (State version) 4 5 LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01) 6 http://www.7-zip.org/ 7 8 LZMA SDK is licensed under two licenses: 9 1) GNU Lesser General Public License (GNU LGPL) 10 2) Common Public License (CPL) 11 It means that you can select one of these two licenses and 12 follow rules of that license. 13 14 SPECIAL EXCEPTION: 15 Igor Pavlov, as the author of this Code, expressly permits you to 16 statically or dynamically link your Code (or bind by name) to the 17 interfaces of this file without subjecting your linked Code to the 18 terms of the CPL or GNU LGPL. Any modifications or additions 19 to this file, however, are subject to the LGPL or CPL terms. 20*/ 21 22#include "LzmaStateDecode.h" 23 24#define kNumTopBits 24 25#define kTopValue ((UInt32)1 << kNumTopBits) 26 27#define kNumBitModelTotalBits 11 28#define kBitModelTotal (1 << kNumBitModelTotalBits) 29#define kNumMoveBits 5 30 31#define RC_READ_BYTE (*Buffer++) 32 33#define RC_INIT Code = 0; Range = 0xFFFFFFFF; \ 34 { int i; for(i = 0; i < 5; i++) { Code = (Code << 8) | RC_READ_BYTE; }} 35 36#define RC_NORMALIZE if (Range < kTopValue) { Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; } 37 38#define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound) 39#define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits; 40#define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits; 41 42#define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \ 43 { UpdateBit0(p); mi <<= 1; A0; } else \ 44 { UpdateBit1(p); mi = (mi + mi) + 1; A1; } 45 46#define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;) 47 48#define RangeDecoderBitTreeDecode(probs, numLevels, res) \ 49 { int i = numLevels; res = 1; \ 50 do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \ 51 res -= (1 << numLevels); } 52 53 54#define kNumPosBitsMax 4 55#define kNumPosStatesMax (1 << kNumPosBitsMax) 56 57#define kLenNumLowBits 3 58#define kLenNumLowSymbols (1 << kLenNumLowBits) 59#define kLenNumMidBits 3 60#define kLenNumMidSymbols (1 << kLenNumMidBits) 61#define kLenNumHighBits 8 62#define kLenNumHighSymbols (1 << kLenNumHighBits) 63 64#define LenChoice 0 65#define LenChoice2 (LenChoice + 1) 66#define LenLow (LenChoice2 + 1) 67#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits)) 68#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits)) 69#define kNumLenProbs (LenHigh + kLenNumHighSymbols) 70 71 72#define kNumStates 12 73#define kNumLitStates 7 74 75#define kStartPosModelIndex 4 76#define kEndPosModelIndex 14 77#define kNumFullDistances (1 << (kEndPosModelIndex >> 1)) 78 79#define kNumPosSlotBits 6 80#define kNumLenToPosStates 4 81 82#define kNumAlignBits 4 83#define kAlignTableSize (1 << kNumAlignBits) 84 85#define kMatchMinLen 2 86 87#define IsMatch 0 88#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax)) 89#define IsRepG0 (IsRep + kNumStates) 90#define IsRepG1 (IsRepG0 + kNumStates) 91#define IsRepG2 (IsRepG1 + kNumStates) 92#define IsRep0Long (IsRepG2 + kNumStates) 93#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax)) 94#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits)) 95#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex) 96#define LenCoder (Align + kAlignTableSize) 97#define RepLenCoder (LenCoder + kNumLenProbs) 98#define Literal (RepLenCoder + kNumLenProbs) 99 100#if Literal != LZMA_BASE_SIZE 101StopCompilingDueBUG 102#endif 103 104/* kRequiredInBufferSize = number of required input bytes for worst case: 105 longest match with longest distance. 106 kLzmaInBufferSize must be larger than kRequiredInBufferSize 107 23 bits = 2 (match select) + 10 (len) + 6 (distance) + 4(align) + 1 (RC_NORMALIZE) 108*/ 109 110#define kRequiredInBufferSize ((23 * (kNumBitModelTotalBits - kNumMoveBits + 1) + 26 + 9) / 8) 111 112#define kLzmaStreamWasFinishedId (-1) 113 114int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size) 115{ 116 unsigned char prop0; 117 if (size < LZMA_PROPERTIES_SIZE) 118 return LZMA_RESULT_DATA_ERROR; 119 prop0 = propsData[0]; 120 if (prop0 >= (9 * 5 * 5)) 121 return LZMA_RESULT_DATA_ERROR; 122 { 123 for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5)); 124 for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9); 125 propsRes->lc = prop0; 126 /* 127 unsigned char remainder = (unsigned char)(prop0 / 9); 128 propsRes->lc = prop0 % 9; 129 propsRes->pb = remainder / 5; 130 propsRes->lp = remainder % 5; 131 */ 132 } 133 134 { 135 int i; 136 propsRes->DictionarySize = 0; 137 for (i = 0; i < 4; i++) 138 propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8); 139 if (propsRes->DictionarySize == 0) 140 propsRes->DictionarySize = 1; 141 return LZMA_RESULT_OK; 142 } 143} 144 145int LzmaDecode( 146 CLzmaDecoderState *vs, 147 const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed, 148 unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed, 149 int finishDecoding) 150{ 151 UInt32 Range = vs->Range; 152 UInt32 Code = vs->Code; 153 154 unsigned char *Buffer = vs->Buffer; 155 int BufferSize = vs->BufferSize; /* don't change it to unsigned int */ 156 CProb *p = vs->Probs; 157 158 int state = vs->State; 159 unsigned char previousByte; 160 UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3]; 161 SizeT nowPos = 0; 162 UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1; 163 UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1; 164 int lc = vs->Properties.lc; 165 int len = vs->RemainLen; 166 UInt32 globalPos = vs->GlobalPos; 167 UInt32 distanceLimit = vs->DistanceLimit; 168 169 unsigned char *dictionary = vs->Dictionary; 170 UInt32 dictionarySize = vs->Properties.DictionarySize; 171 UInt32 dictionaryPos = vs->DictionaryPos; 172 173 unsigned char tempDictionary[4]; 174 175 (*inSizeProcessed) = 0; 176 (*outSizeProcessed) = 0; 177 if (len == kLzmaStreamWasFinishedId) 178 return LZMA_RESULT_OK; 179 180 if (dictionarySize == 0) 181 { 182 dictionary = tempDictionary; 183 dictionarySize = 1; 184 tempDictionary[0] = vs->TempDictionary[0]; 185 } 186 187 if (len == kLzmaNeedInitId) 188 { 189 while (inSize > 0 && BufferSize < kLzmaInBufferSize) 190 { 191 Buffer[BufferSize++] = *inStream++; 192 (*inSizeProcessed)++; 193 inSize--; 194 } 195 if (BufferSize < 5) 196 { 197 vs->BufferSize = BufferSize; 198 return finishDecoding ? LZMA_RESULT_DATA_ERROR : LZMA_RESULT_OK; 199 } 200 { 201 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp)); 202 UInt32 i; 203 for (i = 0; i < numProbs; i++) 204 p[i] = kBitModelTotal >> 1; 205 rep0 = rep1 = rep2 = rep3 = 1; 206 state = 0; 207 globalPos = 0; 208 distanceLimit = 0; 209 dictionaryPos = 0; 210 dictionary[dictionarySize - 1] = 0; 211 RC_INIT; 212 } 213 len = 0; 214 } 215 while(len != 0 && nowPos < outSize) 216 { 217 UInt32 pos = dictionaryPos - rep0; 218 if (pos >= dictionarySize) 219 pos += dictionarySize; 220 outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos]; 221 if (++dictionaryPos == dictionarySize) 222 dictionaryPos = 0; 223 len--; 224 } 225 if (dictionaryPos == 0) 226 previousByte = dictionary[dictionarySize - 1]; 227 else 228 previousByte = dictionary[dictionaryPos - 1]; 229 230 for (;;) 231 { 232 int bufferPos = (int)(Buffer - vs->Buffer); 233 if (BufferSize - bufferPos < kRequiredInBufferSize) 234 { 235 int i; 236 BufferSize -= bufferPos; 237 if (BufferSize < 0) 238 return LZMA_RESULT_DATA_ERROR; 239 for (i = 0; i < BufferSize; i++) 240 vs->Buffer[i] = Buffer[i]; 241 Buffer = vs->Buffer; 242 while (inSize > 0 && BufferSize < kLzmaInBufferSize) 243 { 244 Buffer[BufferSize++] = *inStream++; 245 (*inSizeProcessed)++; 246 inSize--; 247 } 248 if (BufferSize < kRequiredInBufferSize && !finishDecoding) 249 break; 250 } 251 if (nowPos >= outSize) 252 break; 253 { 254 CProb *prob; 255 UInt32 bound; 256 int posState = (int)((nowPos + globalPos) & posStateMask); 257 258 prob = p + IsMatch + (state << kNumPosBitsMax) + posState; 259 IfBit0(prob) 260 { 261 int symbol = 1; 262 UpdateBit0(prob) 263 prob = p + Literal + (LZMA_LIT_SIZE * 264 ((((nowPos + globalPos)& literalPosMask) << lc) + (previousByte >> (8 - lc)))); 265 266 if (state >= kNumLitStates) 267 { 268 int matchByte; 269 UInt32 pos = dictionaryPos - rep0; 270 if (pos >= dictionarySize) 271 pos += dictionarySize; 272 matchByte = dictionary[pos]; 273 do 274 { 275 int bit; 276 CProb *probLit; 277 matchByte <<= 1; 278 bit = (matchByte & 0x100); 279 probLit = prob + 0x100 + bit + symbol; 280 RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break) 281 } 282 while (symbol < 0x100); 283 } 284 while (symbol < 0x100) 285 { 286 CProb *probLit = prob + symbol; 287 RC_GET_BIT(probLit, symbol) 288 } 289 previousByte = (unsigned char)symbol; 290 291 outStream[nowPos++] = previousByte; 292 if (distanceLimit < dictionarySize) 293 distanceLimit++; 294 295 dictionary[dictionaryPos] = previousByte; 296 if (++dictionaryPos == dictionarySize) 297 dictionaryPos = 0; 298 if (state < 4) state = 0; 299 else if (state < 10) state -= 3; 300 else state -= 6; 301 } 302 else 303 { 304 UpdateBit1(prob); 305 prob = p + IsRep + state; 306 IfBit0(prob) 307 { 308 UpdateBit0(prob); 309 rep3 = rep2; 310 rep2 = rep1; 311 rep1 = rep0; 312 state = state < kNumLitStates ? 0 : 3; 313 prob = p + LenCoder; 314 } 315 else 316 { 317 UpdateBit1(prob); 318 prob = p + IsRepG0 + state; 319 IfBit0(prob) 320 { 321 UpdateBit0(prob); 322 prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState; 323 IfBit0(prob) 324 { 325 UInt32 pos; 326 UpdateBit0(prob); 327 if (distanceLimit == 0) 328 return LZMA_RESULT_DATA_ERROR; 329 if (distanceLimit < dictionarySize) 330 distanceLimit++; 331 state = state < kNumLitStates ? 9 : 11; 332 pos = dictionaryPos - rep0; 333 if (pos >= dictionarySize) 334 pos += dictionarySize; 335 previousByte = dictionary[pos]; 336 dictionary[dictionaryPos] = previousByte; 337 if (++dictionaryPos == dictionarySize) 338 dictionaryPos = 0; 339 outStream[nowPos++] = previousByte; 340 continue; 341 } 342 else 343 { 344 UpdateBit1(prob); 345 } 346 } 347 else 348 { 349 UInt32 distance; 350 UpdateBit1(prob); 351 prob = p + IsRepG1 + state; 352 IfBit0(prob) 353 { 354 UpdateBit0(prob); 355 distance = rep1; 356 } 357 else 358 { 359 UpdateBit1(prob); 360 prob = p + IsRepG2 + state; 361 IfBit0(prob) 362 { 363 UpdateBit0(prob); 364 distance = rep2; 365 } 366 else 367 { 368 UpdateBit1(prob); 369 distance = rep3; 370 rep3 = rep2; 371 } 372 rep2 = rep1; 373 } 374 rep1 = rep0; 375 rep0 = distance; 376 } 377 state = state < kNumLitStates ? 8 : 11; 378 prob = p + RepLenCoder; 379 } 380 { 381 int numBits, offset; 382 CProb *probLen = prob + LenChoice; 383 IfBit0(probLen) 384 { 385 UpdateBit0(probLen); 386 probLen = prob + LenLow + (posState << kLenNumLowBits); 387 offset = 0; 388 numBits = kLenNumLowBits; 389 } 390 else 391 { 392 UpdateBit1(probLen); 393 probLen = prob + LenChoice2; 394 IfBit0(probLen) 395 { 396 UpdateBit0(probLen); 397 probLen = prob + LenMid + (posState << kLenNumMidBits); 398 offset = kLenNumLowSymbols; 399 numBits = kLenNumMidBits; 400 } 401 else 402 { 403 UpdateBit1(probLen); 404 probLen = prob + LenHigh; 405 offset = kLenNumLowSymbols + kLenNumMidSymbols; 406 numBits = kLenNumHighBits; 407 } 408 } 409 RangeDecoderBitTreeDecode(probLen, numBits, len); 410 len += offset; 411 } 412 413 if (state < 4) 414 { 415 int posSlot; 416 state += kNumLitStates; 417 prob = p + PosSlot + 418 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << 419 kNumPosSlotBits); 420 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot); 421 if (posSlot >= kStartPosModelIndex) 422 { 423 int numDirectBits = ((posSlot >> 1) - 1); 424 rep0 = (2 | ((UInt32)posSlot & 1)); 425 if (posSlot < kEndPosModelIndex) 426 { 427 rep0 <<= numDirectBits; 428 prob = p + SpecPos + rep0 - posSlot - 1; 429 } 430 else 431 { 432 numDirectBits -= kNumAlignBits; 433 do 434 { 435 RC_NORMALIZE 436 Range >>= 1; 437 rep0 <<= 1; 438 if (Code >= Range) 439 { 440 Code -= Range; 441 rep0 |= 1; 442 } 443 } 444 while (--numDirectBits != 0); 445 prob = p + Align; 446 rep0 <<= kNumAlignBits; 447 numDirectBits = kNumAlignBits; 448 } 449 { 450 int i = 1; 451 int mi = 1; 452 do 453 { 454 CProb *prob3 = prob + mi; 455 RC_GET_BIT2(prob3, mi, ; , rep0 |= i); 456 i <<= 1; 457 } 458 while(--numDirectBits != 0); 459 } 460 } 461 else 462 rep0 = posSlot; 463 if (++rep0 == (UInt32)(0)) 464 { 465 /* it's for stream version */ 466 len = kLzmaStreamWasFinishedId; 467 break; 468 } 469 } 470 471 len += kMatchMinLen; 472 if (rep0 > distanceLimit) 473 return LZMA_RESULT_DATA_ERROR; 474 if (dictionarySize - distanceLimit > (UInt32)len) 475 distanceLimit += len; 476 else 477 distanceLimit = dictionarySize; 478 479 do 480 { 481 UInt32 pos = dictionaryPos - rep0; 482 if (pos >= dictionarySize) 483 pos += dictionarySize; 484 previousByte = dictionary[pos]; 485 dictionary[dictionaryPos] = previousByte; 486 if (++dictionaryPos == dictionarySize) 487 dictionaryPos = 0; 488 len--; 489 outStream[nowPos++] = previousByte; 490 } 491 while(len != 0 && nowPos < outSize); 492 } 493 } 494 } 495 RC_NORMALIZE; 496 497 BufferSize -= (int)(Buffer - vs->Buffer); 498 if (BufferSize < 0) 499 return LZMA_RESULT_DATA_ERROR; 500 { 501 int i; 502 for (i = 0; i < BufferSize; i++) 503 vs->Buffer[i] = Buffer[i]; 504 } 505 vs->BufferSize = BufferSize; 506 vs->Range = Range; 507 vs->Code = Code; 508 vs->DictionaryPos = dictionaryPos; 509 vs->GlobalPos = (UInt32)(globalPos + nowPos); 510 vs->DistanceLimit = distanceLimit; 511 vs->Reps[0] = rep0; 512 vs->Reps[1] = rep1; 513 vs->Reps[2] = rep2; 514 vs->Reps[3] = rep3; 515 vs->State = state; 516 vs->RemainLen = len; 517 vs->TempDictionary[0] = tempDictionary[0]; 518 519 (*outSizeProcessed) = nowPos; 520 return LZMA_RESULT_OK; 521} 522