Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(25)

Side by Side Diff: third_party/lzma/v4_43/LzmaStateDecode.c

Issue 624713003: Keep only base/extractor.[cc|h]. (Closed) Base URL: https://chromium.googlesource.com/external/omaha.git@master
Patch Set: Created 6 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « third_party/lzma/v4_43/LzmaStateDecode.h ('k') | third_party/lzma/v4_43/LzmaTypes.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
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)) >> kNumMove Bits;
40 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveB its;
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
101 StopCompilingDueBUG
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_NORMA LIZE)
108 */
109
110 #define kRequiredInBufferSize ((23 * (kNumBitModelTotalBits - kNumMoveBits + 1) + 26 + 9) / 8)
111
112 #define kLzmaStreamWasFinishedId (-1)
113
114 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsDa ta, 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
145 int 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 //BEGIN_GOOGLE_ADDITION(jeanluc)
175 int usesInternalTempDictionary = (dictionarySize == 0);
176 //END_GOOGLE_ADDITION(jeanluc)
177
178 (*inSizeProcessed) = 0;
179 (*outSizeProcessed) = 0;
180 if (len == kLzmaStreamWasFinishedId)
181 return LZMA_RESULT_OK;
182
183 if (dictionarySize == 0)
184 {
185 dictionary = tempDictionary;
186 dictionarySize = 1;
187 tempDictionary[0] = vs->TempDictionary[0];
188 }
189
190 if (len == kLzmaNeedInitId)
191 {
192 while (inSize > 0 && BufferSize < kLzmaInBufferSize)
193 {
194 Buffer[BufferSize++] = *inStream++;
195 (*inSizeProcessed)++;
196 inSize--;
197 }
198 if (BufferSize < 5)
199 {
200 vs->BufferSize = BufferSize;
201 return finishDecoding ? LZMA_RESULT_DATA_ERROR : LZMA_RESULT_OK;
202 }
203 {
204 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties .lp));
205 UInt32 i;
206 for (i = 0; i < numProbs; i++)
207 p[i] = kBitModelTotal >> 1;
208 rep0 = rep1 = rep2 = rep3 = 1;
209 state = 0;
210 globalPos = 0;
211 distanceLimit = 0;
212 dictionaryPos = 0;
213 dictionary[dictionarySize - 1] = 0;
214 RC_INIT;
215 }
216 len = 0;
217 }
218 while(len != 0 && nowPos < outSize)
219 {
220 UInt32 pos = dictionaryPos - rep0;
221 if (pos >= dictionarySize)
222 pos += dictionarySize;
223 outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
224 if (++dictionaryPos == dictionarySize)
225 dictionaryPos = 0;
226 len--;
227 }
228 if (dictionaryPos == 0)
229 previousByte = dictionary[dictionarySize - 1];
230 else
231 previousByte = dictionary[dictionaryPos - 1];
232
233 while(1)
234 {
235 int bufferPos = (int)(Buffer - vs->Buffer);
236 if (BufferSize - bufferPos < kRequiredInBufferSize)
237 {
238 int i;
239 BufferSize -= bufferPos;
240 if (BufferSize < 0)
241 return LZMA_RESULT_DATA_ERROR;
242 for (i = 0; i < BufferSize; i++)
243 vs->Buffer[i] = Buffer[i];
244 Buffer = vs->Buffer;
245 while (inSize > 0 && BufferSize < kLzmaInBufferSize)
246 {
247 Buffer[BufferSize++] = *inStream++;
248 (*inSizeProcessed)++;
249 inSize--;
250 }
251 if (BufferSize < kRequiredInBufferSize && !finishDecoding)
252 break;
253 }
254 if (nowPos >= outSize)
255 break;
256 {
257 CProb *prob;
258 UInt32 bound;
259 int posState = (int)((nowPos + globalPos) & posStateMask);
260
261 prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
262 IfBit0(prob)
263 {
264 int symbol = 1;
265 UpdateBit0(prob)
266 prob = p + Literal + (LZMA_LIT_SIZE *
267 ((((nowPos + globalPos)& literalPosMask) << lc) + (previousByte >> (8 - lc))));
268
269 if (state >= kNumLitStates)
270 {
271 int matchByte;
272 UInt32 pos = dictionaryPos - rep0;
273 if (pos >= dictionarySize)
274 pos += dictionarySize;
275 matchByte = dictionary[pos];
276 do
277 {
278 int bit;
279 CProb *probLit;
280 matchByte <<= 1;
281 bit = (matchByte & 0x100);
282 probLit = prob + 0x100 + bit + symbol;
283 RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
284 }
285 while (symbol < 0x100);
286 }
287 while (symbol < 0x100)
288 {
289 CProb *probLit = prob + symbol;
290 RC_GET_BIT(probLit, symbol)
291 }
292 previousByte = (unsigned char)symbol;
293
294 outStream[nowPos++] = previousByte;
295 if (distanceLimit < dictionarySize)
296 distanceLimit++;
297
298 dictionary[dictionaryPos] = previousByte;
299 if (++dictionaryPos == dictionarySize)
300 dictionaryPos = 0;
301 if (state < 4) state = 0;
302 else if (state < 10) state -= 3;
303 else state -= 6;
304 }
305 else
306 {
307 UpdateBit1(prob);
308 prob = p + IsRep + state;
309 IfBit0(prob)
310 {
311 UpdateBit0(prob);
312 rep3 = rep2;
313 rep2 = rep1;
314 rep1 = rep0;
315 state = state < kNumLitStates ? 0 : 3;
316 prob = p + LenCoder;
317 }
318 else
319 {
320 UpdateBit1(prob);
321 prob = p + IsRepG0 + state;
322 IfBit0(prob)
323 {
324 UpdateBit0(prob);
325 prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
326 IfBit0(prob)
327 {
328 UInt32 pos;
329 UpdateBit0(prob);
330 if (distanceLimit == 0)
331 return LZMA_RESULT_DATA_ERROR;
332 if (distanceLimit < dictionarySize)
333 distanceLimit++;
334 state = state < kNumLitStates ? 9 : 11;
335 pos = dictionaryPos - rep0;
336 if (pos >= dictionarySize)
337 pos += dictionarySize;
338 previousByte = dictionary[pos];
339 dictionary[dictionaryPos] = previousByte;
340 if (++dictionaryPos == dictionarySize)
341 dictionaryPos = 0;
342 outStream[nowPos++] = previousByte;
343 continue;
344 }
345 else
346 {
347 UpdateBit1(prob);
348 }
349 }
350 else
351 {
352 UInt32 distance;
353 UpdateBit1(prob);
354 prob = p + IsRepG1 + state;
355 IfBit0(prob)
356 {
357 UpdateBit0(prob);
358 distance = rep1;
359 }
360 else
361 {
362 UpdateBit1(prob);
363 prob = p + IsRepG2 + state;
364 IfBit0(prob)
365 {
366 UpdateBit0(prob);
367 distance = rep2;
368 }
369 else
370 {
371 UpdateBit1(prob);
372 distance = rep3;
373 rep3 = rep2;
374 }
375 rep2 = rep1;
376 }
377 rep1 = rep0;
378 rep0 = distance;
379 }
380 state = state < kNumLitStates ? 8 : 11;
381 prob = p + RepLenCoder;
382 }
383 {
384 int numBits, offset;
385 CProb *probLen = prob + LenChoice;
386 IfBit0(probLen)
387 {
388 UpdateBit0(probLen);
389 probLen = prob + LenLow + (posState << kLenNumLowBits);
390 offset = 0;
391 numBits = kLenNumLowBits;
392 }
393 else
394 {
395 UpdateBit1(probLen);
396 probLen = prob + LenChoice2;
397 IfBit0(probLen)
398 {
399 UpdateBit0(probLen);
400 probLen = prob + LenMid + (posState << kLenNumMidBits);
401 offset = kLenNumLowSymbols;
402 numBits = kLenNumMidBits;
403 }
404 else
405 {
406 UpdateBit1(probLen);
407 probLen = prob + LenHigh;
408 offset = kLenNumLowSymbols + kLenNumMidSymbols;
409 numBits = kLenNumHighBits;
410 }
411 }
412 RangeDecoderBitTreeDecode(probLen, numBits, len);
413 len += offset;
414 }
415
416 if (state < 4)
417 {
418 int posSlot;
419 state += kNumLitStates;
420 prob = p + PosSlot +
421 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
422 kNumPosSlotBits);
423 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
424 if (posSlot >= kStartPosModelIndex)
425 {
426 int numDirectBits = ((posSlot >> 1) - 1);
427 rep0 = (2 | ((UInt32)posSlot & 1));
428 if (posSlot < kEndPosModelIndex)
429 {
430 rep0 <<= numDirectBits;
431 prob = p + SpecPos + rep0 - posSlot - 1;
432 }
433 else
434 {
435 numDirectBits -= kNumAlignBits;
436 do
437 {
438 RC_NORMALIZE
439 Range >>= 1;
440 rep0 <<= 1;
441 if (Code >= Range)
442 {
443 Code -= Range;
444 rep0 |= 1;
445 }
446 }
447 while (--numDirectBits != 0);
448 prob = p + Align;
449 rep0 <<= kNumAlignBits;
450 numDirectBits = kNumAlignBits;
451 }
452 {
453 int i = 1;
454 int mi = 1;
455 do
456 {
457 CProb *prob3 = prob + mi;
458 RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
459 i <<= 1;
460 }
461 while(--numDirectBits != 0);
462 }
463 }
464 else
465 rep0 = posSlot;
466 if (++rep0 == (UInt32)(0))
467 {
468 /* it's for stream version */
469 len = kLzmaStreamWasFinishedId;
470 break;
471 }
472 }
473
474 len += kMatchMinLen;
475 if (rep0 > distanceLimit)
476 return LZMA_RESULT_DATA_ERROR;
477 if (dictionarySize - distanceLimit > (UInt32)len)
478 distanceLimit += len;
479 else
480 distanceLimit = dictionarySize;
481
482 do
483 {
484 UInt32 pos = dictionaryPos - rep0;
485 if (pos >= dictionarySize)
486 pos += dictionarySize;
487 previousByte = dictionary[pos];
488 dictionary[dictionaryPos] = previousByte;
489 if (++dictionaryPos == dictionarySize)
490 dictionaryPos = 0;
491 len--;
492 outStream[nowPos++] = previousByte;
493 }
494 while(len != 0 && nowPos < outSize);
495 }
496 }
497 }
498 RC_NORMALIZE;
499
500 BufferSize -= (int)(Buffer - vs->Buffer);
501 if (BufferSize < 0)
502 return LZMA_RESULT_DATA_ERROR;
503 {
504 int i;
505 for (i = 0; i < BufferSize; i++)
506 vs->Buffer[i] = Buffer[i];
507 }
508 vs->BufferSize = BufferSize;
509 vs->Range = Range;
510 vs->Code = Code;
511 vs->DictionaryPos = dictionaryPos;
512 vs->GlobalPos = (UInt32)(globalPos + nowPos);
513 vs->DistanceLimit = distanceLimit;
514 vs->Reps[0] = rep0;
515 vs->Reps[1] = rep1;
516 vs->Reps[2] = rep2;
517 vs->Reps[3] = rep3;
518 vs->State = state;
519 vs->RemainLen = len;
520 //BEGIN_GOOGLE_ADDITION(jeanluc)
521 if (usesInternalTempDictionary)
522 //END_GOOGLE_ADDITION(jeanluc)
523 vs->TempDictionary[0] = tempDictionary[0];
524
525 (*outSizeProcessed) = nowPos;
526 return LZMA_RESULT_OK;
527 }
OLDNEW
« no previous file with comments | « third_party/lzma/v4_43/LzmaStateDecode.h ('k') | third_party/lzma/v4_43/LzmaTypes.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698