lzmadecode.c
1 /* 2 LzmaDecode.c 3 LZMA Decoder (optimized for Speed 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 #if CONFIG(DECOMPRESS_OFAST) 23 #define __lzma_attribute_Ofast__ __attribute__((optimize("Ofast"))) 24 #else 25 #define __lzma_attribute_Ofast__ 26 #endif 27 28 #include "lzmadecode.h" 29 #include <types.h> 30 31 #define kNumTopBits 24 32 #define kTopValue ((UInt32)1 << kNumTopBits) 33 34 #define kNumBitModelTotalBits 11 35 #define kBitModelTotal (1 << kNumBitModelTotalBits) 36 #define kNumMoveBits 5 37 38 /* Use sizeof(SizeT) sized reads whenever possible to avoid bad flash performance. Fall back 39 * to byte reads for last sizeof(SizeT) bytes since RC_TEST returns an error when BufferLim 40 * is *reached* (not surpassed!), meaning we can't allow that to happen while 41 * there are still bytes to decode from the algorithm's point of view. */ 42 #define RC_READ_BYTE \ 43 (look_ahead_ptr < sizeof(SizeT) ? look_ahead.raw[look_ahead_ptr++] \ 44 : ((((uintptr_t) Buffer & (sizeof(SizeT) - 1)) \ 45 || ((SizeT) (BufferLim - Buffer) <= sizeof(SizeT))) ? (*Buffer++) \ 46 : ((look_ahead.dw = *(SizeT *)Buffer), (Buffer += sizeof(SizeT)), \ 47 (look_ahead_ptr = 1), look_ahead.raw[0]))) 48 49 #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \ 50 { \ 51 int i; \ 52 \ 53 for (i = 0; i < 5; i++) { \ 54 RC_TEST; \ 55 Code = (Code << 8) | RC_READ_BYTE; \ 56 } \ 57 } 58 59 60 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; } 61 62 #define RC_INIT(buffer, bufferSize) Buffer = buffer; \ 63 BufferLim = buffer + bufferSize; RC_INIT2 64 65 66 #define RC_NORMALIZE \ 67 if (Range < kTopValue) { \ 68 RC_TEST; \ 69 Range <<= 8; \ 70 Code = (Code << 8) | RC_READ_BYTE; \ 71 } 72 73 #define IfBit0(p) \ 74 RC_NORMALIZE; \ 75 bound = (Range >> kNumBitModelTotalBits) * *(p); \ 76 if (Code < bound) 77 78 #define UpdateBit0(p) \ 79 Range = bound; \ 80 *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits 81 82 #define UpdateBit1(p) \ 83 Range -= bound; \ 84 Code -= bound; \ 85 *(p) -= (*(p)) >> kNumMoveBits 86 87 #define RC_GET_BIT2(p, mi, A0, A1) \ 88 IfBit0(p) { \ 89 UpdateBit0(p); \ 90 mi <<= 1; \ 91 A0; \ 92 } else { \ 93 UpdateBit1(p); \ 94 mi = (mi + mi) + 1; \ 95 A1; \ 96 } 97 98 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ;, ;) 99 100 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \ 101 { \ 102 int i = numLevels; \ 103 \ 104 res = 1; \ 105 do { \ 106 CProb *cp = probs + res; \ 107 RC_GET_BIT(cp, res) \ 108 } while (--i != 0); \ 109 res -= (1 << numLevels); \ 110 } 111 112 113 #define kNumPosBitsMax 4 114 #define kNumPosStatesMax (1 << kNumPosBitsMax) 115 116 #define kLenNumLowBits 3 117 #define kLenNumLowSymbols (1 << kLenNumLowBits) 118 #define kLenNumMidBits 3 119 #define kLenNumMidSymbols (1 << kLenNumMidBits) 120 #define kLenNumHighBits 8 121 #define kLenNumHighSymbols (1 << kLenNumHighBits) 122 123 #define LenChoice 0 124 #define LenChoice2 (LenChoice + 1) 125 #define LenLow (LenChoice2 + 1) 126 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits)) 127 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits)) 128 #define kNumLenProbs (LenHigh + kLenNumHighSymbols) 129 130 131 #define kNumStates 12 132 #define kNumLitStates 7 133 134 #define kStartPosModelIndex 4 135 #define kEndPosModelIndex 14 136 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1)) 137 138 #define kNumPosSlotBits 6 139 #define kNumLenToPosStates 4 140 141 #define kNumAlignBits 4 142 #define kAlignTableSize (1 << kNumAlignBits) 143 144 #define kMatchMinLen 2 145 146 #define IsMatch 0 147 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax)) 148 #define IsRepG0 (IsRep + kNumStates) 149 #define IsRepG1 (IsRepG0 + kNumStates) 150 #define IsRepG2 (IsRepG1 + kNumStates) 151 #define IsRep0Long (IsRepG2 + kNumStates) 152 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax)) 153 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits)) 154 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex) 155 #define LenCoder (Align + kAlignTableSize) 156 #define RepLenCoder (LenCoder + kNumLenProbs) 157 #define Literal (RepLenCoder + kNumLenProbs) 158 159 #if Literal != LZMA_BASE_SIZE 160 StopCompilingDueBUG 161 #endif 162 163 int LzmaDecodeProperties(CLzmaProperties *propsRes, 164 const unsigned char *propsData, int size) 165 { 166 unsigned char prop0; 167 if (size < LZMA_PROPERTIES_SIZE) 168 return LZMA_RESULT_DATA_ERROR; 169 prop0 = propsData[0]; 170 if (prop0 >= (9 * 5 * 5)) 171 return LZMA_RESULT_DATA_ERROR; 172 { 173 for (propsRes->pb = 0; prop0 >= (9 * 5); 174 propsRes->pb++, prop0 -= (9 * 5)) 175 ; 176 for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9) 177 ; 178 propsRes->lc = prop0; 179 /* 180 * unsigned char remainder = (unsigned char)(prop0 / 9); 181 * propsRes->lc = prop0 % 9; 182 * propsRes->pb = remainder / 5; 183 * propsRes->lp = remainder % 5; 184 */ 185 } 186 187 return LZMA_RESULT_OK; 188 } 189 190 #define kLzmaStreamWasFinishedId (-1) 191 192 __lzma_attribute_Ofast__ 193 int LzmaDecode(CLzmaDecoderState *vs, 194 const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed, 195 unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed) 196 { 197 CProb *p = vs->Probs; 198 SizeT nowPos = 0; 199 Byte previousByte = 0; 200 UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1; 201 UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1; 202 int lc = vs->Properties.lc; 203 204 205 int state = 0; 206 UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1; 207 int len = 0; 208 const Byte *Buffer; 209 const Byte *BufferLim; 210 int look_ahead_ptr = sizeof(SizeT); 211 union { 212 Byte raw[sizeof(SizeT)]; 213 SizeT dw; 214 } look_ahead; 215 UInt32 Range; 216 UInt32 Code; 217 218 *inSizeProcessed = 0; 219 *outSizeProcessed = 0; 220 221 { 222 UInt32 i; 223 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc 224 + vs->Properties.lp)); 225 for (i = 0; i < numProbs; i++) 226 p[i] = kBitModelTotal >> 1; 227 } 228 229 RC_INIT(inStream, inSize); 230 231 232 while (nowPos < outSize) { 233 CProb *prob; 234 UInt32 bound; 235 int posState = (int)((nowPos)&posStateMask); 236 237 prob = p + IsMatch + (state << kNumPosBitsMax) + posState; 238 IfBit0(prob) { 239 int symbol = 1; 240 UpdateBit0(prob); 241 prob = p + Literal + (LZMA_LIT_SIZE * 242 ((((nowPos) & literalPosMask) << lc) 243 + (previousByte >> (8 - lc)))); 244 245 if (state >= kNumLitStates) { 246 int matchByte; 247 matchByte = outStream[nowPos - rep0]; 248 do { 249 int bit; 250 CProb *probLit; 251 matchByte <<= 1; 252 bit = (matchByte & 0x100); 253 probLit = prob + 0x100 + bit + symbol; 254 RC_GET_BIT2(probLit, symbol, 255 if (bit != 0) 256 break, 257 if (bit == 0) 258 break) 259 } while (symbol < 0x100); 260 } 261 while (symbol < 0x100) { 262 CProb *probLit = prob + symbol; 263 RC_GET_BIT(probLit, symbol) 264 } 265 previousByte = (Byte)symbol; 266 267 outStream[nowPos++] = previousByte; 268 if (state < 4) 269 state = 0; 270 else if (state < 10) 271 state -= 3; 272 else 273 state -= 6; 274 } else { 275 UpdateBit1(prob); 276 prob = p + IsRep + state; 277 IfBit0(prob) { 278 UpdateBit0(prob); 279 rep3 = rep2; 280 rep2 = rep1; 281 rep1 = rep0; 282 state = state < kNumLitStates ? 0 : 3; 283 prob = p + LenCoder; 284 } else { 285 UpdateBit1(prob); 286 prob = p + IsRepG0 + state; 287 IfBit0(prob) { 288 UpdateBit0(prob); 289 prob = p + IsRep0Long 290 + (state << kNumPosBitsMax) 291 + posState; 292 IfBit0(prob) { 293 UpdateBit0(prob); 294 295 if (nowPos == 0) 296 return LZMA_RESULT_DATA_ERROR; 297 298 state = state < kNumLitStates 299 ? 9 : 11; 300 previousByte = outStream[nowPos 301 - rep0]; 302 outStream[nowPos++] = 303 previousByte; 304 305 continue; 306 } else { 307 UpdateBit1(prob); 308 } 309 } else { 310 UInt32 distance; 311 UpdateBit1(prob); 312 prob = p + IsRepG1 + state; 313 IfBit0(prob) { 314 UpdateBit0(prob); 315 distance = rep1; 316 } else { 317 UpdateBit1(prob); 318 prob = p + IsRepG2 + state; 319 IfBit0(prob) { 320 UpdateBit0(prob); 321 distance = rep2; 322 } else { 323 UpdateBit1(prob); 324 distance = rep3; 325 rep3 = rep2; 326 } 327 rep2 = rep1; 328 } 329 rep1 = rep0; 330 rep0 = distance; 331 } 332 state = state < kNumLitStates ? 8 : 11; 333 prob = p + RepLenCoder; 334 } 335 { 336 int numBits, offset; 337 CProb *probLen = prob + LenChoice; 338 IfBit0(probLen) { 339 UpdateBit0(probLen); 340 probLen = prob + LenLow 341 + (posState << kLenNumLowBits); 342 offset = 0; 343 numBits = kLenNumLowBits; 344 } else { 345 UpdateBit1(probLen); 346 probLen = prob + LenChoice2; 347 IfBit0(probLen) { 348 UpdateBit0(probLen); 349 probLen = prob + LenMid 350 + (posState << 351 kLenNumMidBits); 352 offset = kLenNumLowSymbols; 353 numBits = kLenNumMidBits; 354 } else { 355 UpdateBit1(probLen); 356 probLen = prob + LenHigh; 357 offset = kLenNumLowSymbols 358 + kLenNumMidSymbols; 359 numBits = kLenNumHighBits; 360 } 361 } 362 RangeDecoderBitTreeDecode(probLen, numBits, 363 len); 364 len += offset; 365 } 366 367 if (state < 4) { 368 int posSlot; 369 state += kNumLitStates; 370 prob = p + PosSlot + 371 ((len < kNumLenToPosStates ? len : 372 kNumLenToPosStates - 1) << 373 kNumPosSlotBits); 374 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, 375 posSlot); 376 if (posSlot >= kStartPosModelIndex) { 377 int numDirectBits = ((posSlot >> 1) 378 - 1); 379 rep0 = (2 | ((UInt32)posSlot & 1)); 380 if (posSlot < kEndPosModelIndex) { 381 rep0 <<= numDirectBits; 382 prob = p + SpecPos + rep0 383 - posSlot - 1; 384 } else { 385 numDirectBits -= kNumAlignBits; 386 do { 387 RC_NORMALIZE 388 Range >>= 1; 389 rep0 <<= 1; 390 if (Code >= Range) { 391 Code -= Range; 392 rep0 |= 1; 393 } 394 } while (--numDirectBits != 0); 395 prob = p + Align; 396 rep0 <<= kNumAlignBits; 397 numDirectBits = kNumAlignBits; 398 } 399 { 400 int i = 1; 401 int mi = 1; 402 do { 403 CProb *prob3 = prob 404 + mi; 405 RC_GET_BIT2(prob3, mi, 406 ;, rep0 |= i); 407 i <<= 1; 408 } while (--numDirectBits != 0); 409 } 410 } else 411 rep0 = posSlot; 412 if (++rep0 == (UInt32)(0)) { 413 /* it's for stream version */ 414 len = kLzmaStreamWasFinishedId; 415 break; 416 } 417 } 418 419 len += kMatchMinLen; 420 if (rep0 > nowPos) 421 return LZMA_RESULT_DATA_ERROR; 422 423 424 do { 425 previousByte = outStream[nowPos - rep0]; 426 len--; 427 outStream[nowPos++] = previousByte; 428 } while (len != 0 && nowPos < outSize); 429 } 430 } 431 RC_NORMALIZE; 432 /* 433 * Tell static analysis we know len can have a dead assignment. 434 */ 435 (void)len; 436 437 438 *inSizeProcessed = (SizeT)(Buffer - inStream); 439 *outSizeProcessed = nowPos; 440 return LZMA_RESULT_OK; 441 }