mtd-utils: update to 2.0.2
[openwrt/openwrt.git] / package / utils / mtd-utils / patches / 130-lzma_jffs2.patch
1 --- a/jffsX-utils/Makemodule.am
2 +++ b/jffsX-utils/Makemodule.am
3 @@ -4,11 +4,19 @@ mkfs_jffs2_SOURCES = \
4 jffsX-utils/compr_zlib.c \
5 jffsX-utils/compr.h \
6 jffsX-utils/rbtree.c \
7 - jffsX-utils/compr_lzo.c \
8 + jffsX-utils/compr_lzma.c \
9 + jffsX-utils/lzma/LzFind.c \
10 + jffsX-utils/lzma/LzmaEnc.c \
11 + jffsX-utils/lzma/LzmaDec.c \
12 jffsX-utils/compr.c \
13 jffsX-utils/compr_rtime.c
14 +
15 +if !WITHOUT_LZO
16 +mkfs_jffs2_SOURCES += jffsX-utils/compr_lzo.c
17 +endif
18 +
19 mkfs_jffs2_LDADD = libmtd.a $(ZLIB_LIBS) $(LZO_LIBS)
20 -mkfs_jffs2_CPPFLAGS = $(AM_CPPFLAGS) $(ZLIB_CFLAGS) $(LZO_CFLAGS)
21 +mkfs_jffs2_CPPFLAGS = $(AM_CPPFLAGS) $(ZLIB_CFLAGS) $(LZO_CFLAGS) -I./include/linux/lzma
22
23 jffs2reader_SOURCES = jffsX-utils/jffs2reader.c
24 jffs2reader_LDADD = libmtd.a $(ZLIB_LIBS) $(LZO_LIBS)
25 --- a/jffsX-utils/compr.c
26 +++ b/jffsX-utils/compr.c
27 @@ -520,6 +520,9 @@ int jffs2_compressors_init(void)
28 #ifdef CONFIG_JFFS2_LZO
29 jffs2_lzo_init();
30 #endif
31 +#ifdef CONFIG_JFFS2_LZMA
32 + jffs2_lzma_init();
33 +#endif
34 return 0;
35 }
36
37 @@ -534,5 +537,8 @@ int jffs2_compressors_exit(void)
38 #ifdef CONFIG_JFFS2_LZO
39 jffs2_lzo_exit();
40 #endif
41 +#ifdef CONFIG_JFFS2_LZMA
42 + jffs2_lzma_exit();
43 +#endif
44 return 0;
45 }
46 --- a/jffsX-utils/compr.h
47 +++ b/jffsX-utils/compr.h
48 @@ -18,13 +18,14 @@
49
50 #define CONFIG_JFFS2_ZLIB
51 #define CONFIG_JFFS2_RTIME
52 -#define CONFIG_JFFS2_LZO
53 +#define CONFIG_JFFS2_LZMA
54
55 #define JFFS2_RUBINMIPS_PRIORITY 10
56 #define JFFS2_DYNRUBIN_PRIORITY 20
57 #define JFFS2_RTIME_PRIORITY 50
58 -#define JFFS2_ZLIB_PRIORITY 60
59 -#define JFFS2_LZO_PRIORITY 80
60 +#define JFFS2_LZMA_PRIORITY 70
61 +#define JFFS2_ZLIB_PRIORITY 80
62 +#define JFFS2_LZO_PRIORITY 90
63
64 #define JFFS2_COMPR_MODE_NONE 0
65 #define JFFS2_COMPR_MODE_PRIORITY 1
66 @@ -115,5 +116,10 @@ void jffs2_rtime_exit(void);
67 int jffs2_lzo_init(void);
68 void jffs2_lzo_exit(void);
69 #endif
70 +#ifdef CONFIG_JFFS2_LZMA
71 +int jffs2_lzma_init(void);
72 +void jffs2_lzma_exit(void);
73 +#endif
74 +
75
76 #endif /* __JFFS2_COMPR_H__ */
77 --- /dev/null
78 +++ b/jffsX-utils/compr_lzma.c
79 @@ -0,0 +1,128 @@
80 +/*
81 + * JFFS2 -- Journalling Flash File System, Version 2.
82 + *
83 + * For licensing information, see the file 'LICENCE' in this directory.
84 + *
85 + * JFFS2 wrapper to the LZMA C SDK
86 + *
87 + */
88 +
89 +#include <linux/lzma.h>
90 +#include "compr.h"
91 +
92 +#ifdef __KERNEL__
93 + static DEFINE_MUTEX(deflate_mutex);
94 +#endif
95 +
96 +CLzmaEncHandle *p;
97 +Byte propsEncoded[LZMA_PROPS_SIZE];
98 +SizeT propsSize = sizeof(propsEncoded);
99 +
100 +STATIC void lzma_free_workspace(void)
101 +{
102 + LzmaEnc_Destroy(p, &lzma_alloc, &lzma_alloc);
103 +}
104 +
105 +STATIC int INIT lzma_alloc_workspace(CLzmaEncProps *props)
106 +{
107 + if ((p = (CLzmaEncHandle *)LzmaEnc_Create(&lzma_alloc)) == NULL)
108 + {
109 + PRINT_ERROR("Failed to allocate lzma deflate workspace\n");
110 + return -ENOMEM;
111 + }
112 +
113 + if (LzmaEnc_SetProps(p, props) != SZ_OK)
114 + {
115 + lzma_free_workspace();
116 + return -1;
117 + }
118 +
119 + if (LzmaEnc_WriteProperties(p, propsEncoded, &propsSize) != SZ_OK)
120 + {
121 + lzma_free_workspace();
122 + return -1;
123 + }
124 +
125 + return 0;
126 +}
127 +
128 +STATIC int jffs2_lzma_compress(unsigned char *data_in, unsigned char *cpage_out,
129 + uint32_t *sourcelen, uint32_t *dstlen)
130 +{
131 + SizeT compress_size = (SizeT)(*dstlen);
132 + int ret;
133 +
134 + #ifdef __KERNEL__
135 + mutex_lock(&deflate_mutex);
136 + #endif
137 +
138 + ret = LzmaEnc_MemEncode(p, cpage_out, &compress_size, data_in, *sourcelen,
139 + 0, NULL, &lzma_alloc, &lzma_alloc);
140 +
141 + #ifdef __KERNEL__
142 + mutex_unlock(&deflate_mutex);
143 + #endif
144 +
145 + if (ret != SZ_OK)
146 + return -1;
147 +
148 + *dstlen = (uint32_t)compress_size;
149 +
150 + return 0;
151 +}
152 +
153 +STATIC int jffs2_lzma_decompress(unsigned char *data_in, unsigned char *cpage_out,
154 + uint32_t srclen, uint32_t destlen)
155 +{
156 + int ret;
157 + SizeT dl = (SizeT)destlen;
158 + SizeT sl = (SizeT)srclen;
159 + ELzmaStatus status;
160 +
161 + ret = LzmaDecode(cpage_out, &dl, data_in, &sl, propsEncoded,
162 + propsSize, LZMA_FINISH_ANY, &status, &lzma_alloc);
163 +
164 + if (ret != SZ_OK || status == LZMA_STATUS_NOT_FINISHED || dl != (SizeT)destlen)
165 + return -1;
166 +
167 + return 0;
168 +}
169 +
170 +static struct jffs2_compressor jffs2_lzma_comp = {
171 + .priority = JFFS2_LZMA_PRIORITY,
172 + .name = "lzma",
173 + .compr = JFFS2_COMPR_LZMA,
174 + .compress = &jffs2_lzma_compress,
175 + .decompress = &jffs2_lzma_decompress,
176 + .disabled = 0,
177 +};
178 +
179 +int INIT jffs2_lzma_init(void)
180 +{
181 + int ret;
182 + CLzmaEncProps props;
183 + LzmaEncProps_Init(&props);
184 +
185 + props.dictSize = LZMA_BEST_DICT(0x2000);
186 + props.level = LZMA_BEST_LEVEL;
187 + props.lc = LZMA_BEST_LC;
188 + props.lp = LZMA_BEST_LP;
189 + props.pb = LZMA_BEST_PB;
190 + props.fb = LZMA_BEST_FB;
191 +
192 + ret = lzma_alloc_workspace(&props);
193 + if (ret < 0)
194 + return ret;
195 +
196 + ret = jffs2_register_compressor(&jffs2_lzma_comp);
197 + if (ret)
198 + lzma_free_workspace();
199 +
200 + return ret;
201 +}
202 +
203 +void jffs2_lzma_exit(void)
204 +{
205 + jffs2_unregister_compressor(&jffs2_lzma_comp);
206 + lzma_free_workspace();
207 +}
208 --- a/include/linux/jffs2.h
209 +++ b/include/linux/jffs2.h
210 @@ -47,6 +47,7 @@
211 #define JFFS2_COMPR_DYNRUBIN 0x05
212 #define JFFS2_COMPR_ZLIB 0x06
213 #define JFFS2_COMPR_LZO 0x07
214 +#define JFFS2_COMPR_LZMA 0x08
215 /* Compatibility flags. */
216 #define JFFS2_COMPAT_MASK 0xc000 /* What do to if an unknown nodetype is found */
217 #define JFFS2_NODE_ACCURATE 0x2000
218 --- /dev/null
219 +++ b/include/linux/lzma.h
220 @@ -0,0 +1,61 @@
221 +#ifndef __LZMA_H__
222 +#define __LZMA_H__
223 +
224 +#ifdef __KERNEL__
225 + #include <linux/kernel.h>
226 + #include <linux/sched.h>
227 + #include <linux/slab.h>
228 + #include <linux/vmalloc.h>
229 + #include <linux/init.h>
230 + #define LZMA_MALLOC vmalloc
231 + #define LZMA_FREE vfree
232 + #define PRINT_ERROR(msg) printk(KERN_WARNING #msg)
233 + #define INIT __init
234 + #define STATIC static
235 +#else
236 + #include <stdint.h>
237 + #include <stdlib.h>
238 + #include <stdio.h>
239 + #include <unistd.h>
240 + #include <string.h>
241 + #include <errno.h>
242 + #include <linux/jffs2.h>
243 + #ifndef PAGE_SIZE
244 + extern int page_size;
245 + #define PAGE_SIZE page_size
246 + #endif
247 + #define LZMA_MALLOC malloc
248 + #define LZMA_FREE free
249 + #define PRINT_ERROR(msg) fprintf(stderr, msg)
250 + #define INIT
251 + #define STATIC static
252 +#endif
253 +
254 +#include "lzma/LzmaDec.h"
255 +#include "lzma/LzmaEnc.h"
256 +
257 +#define LZMA_BEST_LEVEL (9)
258 +#define LZMA_BEST_LC (0)
259 +#define LZMA_BEST_LP (0)
260 +#define LZMA_BEST_PB (0)
261 +#define LZMA_BEST_FB (273)
262 +
263 +#define LZMA_BEST_DICT(n) (((int)((n) / 2)) * 2)
264 +
265 +static void *p_lzma_malloc(void *p, size_t size)
266 +{
267 + if (size == 0)
268 + return NULL;
269 +
270 + return LZMA_MALLOC(size);
271 +}
272 +
273 +static void p_lzma_free(void *p, void *address)
274 +{
275 + if (address != NULL)
276 + LZMA_FREE(address);
277 +}
278 +
279 +static ISzAlloc lzma_alloc = {p_lzma_malloc, p_lzma_free};
280 +
281 +#endif
282 --- /dev/null
283 +++ b/include/linux/lzma/LzFind.h
284 @@ -0,0 +1,116 @@
285 +/* LzFind.h -- Match finder for LZ algorithms
286 +2008-04-04
287 +Copyright (c) 1999-2008 Igor Pavlov
288 +You can use any of the following license options:
289 + 1) GNU Lesser General Public License (GNU LGPL)
290 + 2) Common Public License (CPL)
291 + 3) Common Development and Distribution License (CDDL) Version 1.0
292 + 4) Igor Pavlov, as the author of this code, expressly permits you to
293 + statically or dynamically link your code (or bind by name) to this file,
294 + while you keep this file unmodified.
295 +*/
296 +
297 +#ifndef __LZFIND_H
298 +#define __LZFIND_H
299 +
300 +#include "Types.h"
301 +
302 +typedef UInt32 CLzRef;
303 +
304 +typedef struct _CMatchFinder
305 +{
306 + Byte *buffer;
307 + UInt32 pos;
308 + UInt32 posLimit;
309 + UInt32 streamPos;
310 + UInt32 lenLimit;
311 +
312 + UInt32 cyclicBufferPos;
313 + UInt32 cyclicBufferSize; /* it must be = (historySize + 1) */
314 +
315 + UInt32 matchMaxLen;
316 + CLzRef *hash;
317 + CLzRef *son;
318 + UInt32 hashMask;
319 + UInt32 cutValue;
320 +
321 + Byte *bufferBase;
322 + ISeqInStream *stream;
323 + int streamEndWasReached;
324 +
325 + UInt32 blockSize;
326 + UInt32 keepSizeBefore;
327 + UInt32 keepSizeAfter;
328 +
329 + UInt32 numHashBytes;
330 + int directInput;
331 + int btMode;
332 + /* int skipModeBits; */
333 + int bigHash;
334 + UInt32 historySize;
335 + UInt32 fixedHashSize;
336 + UInt32 hashSizeSum;
337 + UInt32 numSons;
338 + SRes result;
339 + UInt32 crc[256];
340 +} CMatchFinder;
341 +
342 +#define Inline_MatchFinder_GetPointerToCurrentPos(p) ((p)->buffer)
343 +#define Inline_MatchFinder_GetIndexByte(p, index) ((p)->buffer[(Int32)(index)])
344 +
345 +#define Inline_MatchFinder_GetNumAvailableBytes(p) ((p)->streamPos - (p)->pos)
346 +
347 +int MatchFinder_NeedMove(CMatchFinder *p);
348 +Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p);
349 +void MatchFinder_MoveBlock(CMatchFinder *p);
350 +void MatchFinder_ReadIfRequired(CMatchFinder *p);
351 +
352 +void MatchFinder_Construct(CMatchFinder *p);
353 +
354 +/* Conditions:
355 + historySize <= 3 GB
356 + keepAddBufferBefore + matchMaxLen + keepAddBufferAfter < 511MB
357 +*/
358 +int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
359 + UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
360 + ISzAlloc *alloc);
361 +void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc);
362 +void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems);
363 +void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue);
364 +
365 +UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *buffer, CLzRef *son,
366 + UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 _cutValue,
367 + UInt32 *distances, UInt32 maxLen);
368 +
369 +/*
370 +Conditions:
371 + Mf_GetNumAvailableBytes_Func must be called before each Mf_GetMatchLen_Func.
372 + Mf_GetPointerToCurrentPos_Func's result must be used only before any other function
373 +*/
374 +
375 +typedef void (*Mf_Init_Func)(void *object);
376 +typedef Byte (*Mf_GetIndexByte_Func)(void *object, Int32 index);
377 +typedef UInt32 (*Mf_GetNumAvailableBytes_Func)(void *object);
378 +typedef const Byte * (*Mf_GetPointerToCurrentPos_Func)(void *object);
379 +typedef UInt32 (*Mf_GetMatches_Func)(void *object, UInt32 *distances);
380 +typedef void (*Mf_Skip_Func)(void *object, UInt32);
381 +
382 +typedef struct _IMatchFinder
383 +{
384 + Mf_Init_Func Init;
385 + Mf_GetIndexByte_Func GetIndexByte;
386 + Mf_GetNumAvailableBytes_Func GetNumAvailableBytes;
387 + Mf_GetPointerToCurrentPos_Func GetPointerToCurrentPos;
388 + Mf_GetMatches_Func GetMatches;
389 + Mf_Skip_Func Skip;
390 +} IMatchFinder;
391 +
392 +void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable);
393 +
394 +void MatchFinder_Init(CMatchFinder *p);
395 +UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances);
396 +UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances);
397 +void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num);
398 +void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num);
399 +
400 +#endif
401 --- /dev/null
402 +++ b/include/linux/lzma/LzHash.h
403 @@ -0,0 +1,56 @@
404 +/* LzHash.h -- HASH functions for LZ algorithms
405 +2008-03-26
406 +Copyright (c) 1999-2008 Igor Pavlov
407 +Read LzFind.h for license options */
408 +
409 +#ifndef __LZHASH_H
410 +#define __LZHASH_H
411 +
412 +#define kHash2Size (1 << 10)
413 +#define kHash3Size (1 << 16)
414 +#define kHash4Size (1 << 20)
415 +
416 +#define kFix3HashSize (kHash2Size)
417 +#define kFix4HashSize (kHash2Size + kHash3Size)
418 +#define kFix5HashSize (kHash2Size + kHash3Size + kHash4Size)
419 +
420 +#define HASH2_CALC hashValue = cur[0] | ((UInt32)cur[1] << 8);
421 +
422 +#define HASH3_CALC { \
423 + UInt32 temp = p->crc[cur[0]] ^ cur[1]; \
424 + hash2Value = temp & (kHash2Size - 1); \
425 + hashValue = (temp ^ ((UInt32)cur[2] << 8)) & p->hashMask; }
426 +
427 +#define HASH4_CALC { \
428 + UInt32 temp = p->crc[cur[0]] ^ cur[1]; \
429 + hash2Value = temp & (kHash2Size - 1); \
430 + hash3Value = (temp ^ ((UInt32)cur[2] << 8)) & (kHash3Size - 1); \
431 + hashValue = (temp ^ ((UInt32)cur[2] << 8) ^ (p->crc[cur[3]] << 5)) & p->hashMask; }
432 +
433 +#define HASH5_CALC { \
434 + UInt32 temp = p->crc[cur[0]] ^ cur[1]; \
435 + hash2Value = temp & (kHash2Size - 1); \
436 + hash3Value = (temp ^ ((UInt32)cur[2] << 8)) & (kHash3Size - 1); \
437 + hash4Value = (temp ^ ((UInt32)cur[2] << 8) ^ (p->crc[cur[3]] << 5)); \
438 + hashValue = (hash4Value ^ (p->crc[cur[4]] << 3)) & p->hashMask; \
439 + hash4Value &= (kHash4Size - 1); }
440 +
441 +/* #define HASH_ZIP_CALC hashValue = ((cur[0] | ((UInt32)cur[1] << 8)) ^ p->crc[cur[2]]) & 0xFFFF; */
442 +#define HASH_ZIP_CALC hashValue = ((cur[2] | ((UInt32)cur[0] << 8)) ^ p->crc[cur[1]]) & 0xFFFF;
443 +
444 +
445 +#define MT_HASH2_CALC \
446 + hash2Value = (p->crc[cur[0]] ^ cur[1]) & (kHash2Size - 1);
447 +
448 +#define MT_HASH3_CALC { \
449 + UInt32 temp = p->crc[cur[0]] ^ cur[1]; \
450 + hash2Value = temp & (kHash2Size - 1); \
451 + hash3Value = (temp ^ ((UInt32)cur[2] << 8)) & (kHash3Size - 1); }
452 +
453 +#define MT_HASH4_CALC { \
454 + UInt32 temp = p->crc[cur[0]] ^ cur[1]; \
455 + hash2Value = temp & (kHash2Size - 1); \
456 + hash3Value = (temp ^ ((UInt32)cur[2] << 8)) & (kHash3Size - 1); \
457 + hash4Value = (temp ^ ((UInt32)cur[2] << 8) ^ (p->crc[cur[3]] << 5)) & (kHash4Size - 1); }
458 +
459 +#endif
460 --- /dev/null
461 +++ b/include/linux/lzma/LzmaDec.h
462 @@ -0,0 +1,232 @@
463 +/* LzmaDec.h -- LZMA Decoder
464 +2008-04-29
465 +Copyright (c) 1999-2008 Igor Pavlov
466 +You can use any of the following license options:
467 + 1) GNU Lesser General Public License (GNU LGPL)
468 + 2) Common Public License (CPL)
469 + 3) Common Development and Distribution License (CDDL) Version 1.0
470 + 4) Igor Pavlov, as the author of this code, expressly permits you to
471 + statically or dynamically link your code (or bind by name) to this file,
472 + while you keep this file unmodified.
473 +*/
474 +
475 +#ifndef __LZMADEC_H
476 +#define __LZMADEC_H
477 +
478 +#include "Types.h"
479 +
480 +/* #define _LZMA_PROB32 */
481 +/* _LZMA_PROB32 can increase the speed on some CPUs,
482 + but memory usage for CLzmaDec::probs will be doubled in that case */
483 +
484 +#ifdef _LZMA_PROB32
485 +#define CLzmaProb UInt32
486 +#else
487 +#define CLzmaProb UInt16
488 +#endif
489 +
490 +
491 +/* ---------- LZMA Properties ---------- */
492 +
493 +#define LZMA_PROPS_SIZE 5
494 +
495 +typedef struct _CLzmaProps
496 +{
497 + unsigned lc, lp, pb;
498 + UInt32 dicSize;
499 +} CLzmaProps;
500 +
501 +/* LzmaProps_Decode - decodes properties
502 +Returns:
503 + SZ_OK
504 + SZ_ERROR_UNSUPPORTED - Unsupported properties
505 +*/
506 +
507 +SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size);
508 +
509 +
510 +/* ---------- LZMA Decoder state ---------- */
511 +
512 +/* LZMA_REQUIRED_INPUT_MAX = number of required input bytes for worst case.
513 + Num bits = log2((2^11 / 31) ^ 22) + 26 < 134 + 26 = 160; */
514 +
515 +#define LZMA_REQUIRED_INPUT_MAX 20
516 +
517 +typedef struct
518 +{
519 + CLzmaProps prop;
520 + CLzmaProb *probs;
521 + Byte *dic;
522 + const Byte *buf;
523 + UInt32 range, code;
524 + SizeT dicPos;
525 + SizeT dicBufSize;
526 + UInt32 processedPos;
527 + UInt32 checkDicSize;
528 + unsigned state;
529 + UInt32 reps[4];
530 + unsigned remainLen;
531 + int needFlush;
532 + int needInitState;
533 + UInt32 numProbs;
534 + unsigned tempBufSize;
535 + Byte tempBuf[LZMA_REQUIRED_INPUT_MAX];
536 +} CLzmaDec;
537 +
538 +#define LzmaDec_Construct(p) { (p)->dic = 0; (p)->probs = 0; }
539 +
540 +void LzmaDec_Init(CLzmaDec *p);
541 +
542 +/* There are two types of LZMA streams:
543 + 0) Stream with end mark. That end mark adds about 6 bytes to compressed size.
544 + 1) Stream without end mark. You must know exact uncompressed size to decompress such stream. */
545 +
546 +typedef enum
547 +{
548 + LZMA_FINISH_ANY, /* finish at any point */
549 + LZMA_FINISH_END /* block must be finished at the end */
550 +} ELzmaFinishMode;
551 +
552 +/* ELzmaFinishMode has meaning only if the decoding reaches output limit !!!
553 +
554 + You must use LZMA_FINISH_END, when you know that current output buffer
555 + covers last bytes of block. In other cases you must use LZMA_FINISH_ANY.
556 +
557 + If LZMA decoder sees end marker before reaching output limit, it returns SZ_OK,
558 + and output value of destLen will be less than output buffer size limit.
559 + You can check status result also.
560 +
561 + You can use multiple checks to test data integrity after full decompression:
562 + 1) Check Result and "status" variable.
563 + 2) Check that output(destLen) = uncompressedSize, if you know real uncompressedSize.
564 + 3) Check that output(srcLen) = compressedSize, if you know real compressedSize.
565 + You must use correct finish mode in that case. */
566 +
567 +typedef enum
568 +{
569 + LZMA_STATUS_NOT_SPECIFIED, /* use main error code instead */
570 + LZMA_STATUS_FINISHED_WITH_MARK, /* stream was finished with end mark. */
571 + LZMA_STATUS_NOT_FINISHED, /* stream was not finished */
572 + LZMA_STATUS_NEEDS_MORE_INPUT, /* you must provide more input bytes */
573 + LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK /* there is probability that stream was finished without end mark */
574 +} ELzmaStatus;
575 +
576 +/* ELzmaStatus is used only as output value for function call */
577 +
578 +
579 +/* ---------- Interfaces ---------- */
580 +
581 +/* There are 3 levels of interfaces:
582 + 1) Dictionary Interface
583 + 2) Buffer Interface
584 + 3) One Call Interface
585 + You can select any of these interfaces, but don't mix functions from different
586 + groups for same object. */
587 +
588 +
589 +/* There are two variants to allocate state for Dictionary Interface:
590 + 1) LzmaDec_Allocate / LzmaDec_Free
591 + 2) LzmaDec_AllocateProbs / LzmaDec_FreeProbs
592 + You can use variant 2, if you set dictionary buffer manually.
593 + For Buffer Interface you must always use variant 1.
594 +
595 +LzmaDec_Allocate* can return:
596 + SZ_OK
597 + SZ_ERROR_MEM - Memory allocation error
598 + SZ_ERROR_UNSUPPORTED - Unsupported properties
599 +*/
600 +
601 +SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc);
602 +void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc);
603 +
604 +SRes LzmaDec_Allocate(CLzmaDec *state, const Byte *prop, unsigned propsSize, ISzAlloc *alloc);
605 +void LzmaDec_Free(CLzmaDec *state, ISzAlloc *alloc);
606 +
607 +/* ---------- Dictionary Interface ---------- */
608 +
609 +/* You can use it, if you want to eliminate the overhead for data copying from
610 + dictionary to some other external buffer.
611 + You must work with CLzmaDec variables directly in this interface.
612 +
613 + STEPS:
614 + LzmaDec_Constr()
615 + LzmaDec_Allocate()
616 + for (each new stream)
617 + {
618 + LzmaDec_Init()
619 + while (it needs more decompression)
620 + {
621 + LzmaDec_DecodeToDic()
622 + use data from CLzmaDec::dic and update CLzmaDec::dicPos
623 + }
624 + }
625 + LzmaDec_Free()
626 +*/
627 +
628 +/* LzmaDec_DecodeToDic
629 +
630 + The decoding to internal dictionary buffer (CLzmaDec::dic).
631 + You must manually update CLzmaDec::dicPos, if it reaches CLzmaDec::dicBufSize !!!
632 +
633 +finishMode:
634 + It has meaning only if the decoding reaches output limit (dicLimit).
635 + LZMA_FINISH_ANY - Decode just dicLimit bytes.
636 + LZMA_FINISH_END - Stream must be finished after dicLimit.
637 +
638 +Returns:
639 + SZ_OK
640 + status:
641 + LZMA_STATUS_FINISHED_WITH_MARK
642 + LZMA_STATUS_NOT_FINISHED
643 + LZMA_STATUS_NEEDS_MORE_INPUT
644 + LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK
645 + SZ_ERROR_DATA - Data error
646 +*/
647 +
648 +SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit,
649 + const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status);
650 +
651 +
652 +/* ---------- Buffer Interface ---------- */
653 +
654 +/* It's zlib-like interface.
655 + See LzmaDec_DecodeToDic description for information about STEPS and return results,
656 + but you must use LzmaDec_DecodeToBuf instead of LzmaDec_DecodeToDic and you don't need
657 + to work with CLzmaDec variables manually.
658 +
659 +finishMode:
660 + It has meaning only if the decoding reaches output limit (*destLen).
661 + LZMA_FINISH_ANY - Decode just destLen bytes.
662 + LZMA_FINISH_END - Stream must be finished after (*destLen).
663 +*/
664 +
665 +SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen,
666 + const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status);
667 +
668 +
669 +/* ---------- One Call Interface ---------- */
670 +
671 +/* LzmaDecode
672 +
673 +finishMode:
674 + It has meaning only if the decoding reaches output limit (*destLen).
675 + LZMA_FINISH_ANY - Decode just destLen bytes.
676 + LZMA_FINISH_END - Stream must be finished after (*destLen).
677 +
678 +Returns:
679 + SZ_OK
680 + status:
681 + LZMA_STATUS_FINISHED_WITH_MARK
682 + LZMA_STATUS_NOT_FINISHED
683 + LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK
684 + SZ_ERROR_DATA - Data error
685 + SZ_ERROR_MEM - Memory allocation error
686 + SZ_ERROR_UNSUPPORTED - Unsupported properties
687 + SZ_ERROR_INPUT_EOF - It needs more bytes in input buffer (src).
688 +*/
689 +
690 +SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
691 + const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,
692 + ELzmaStatus *status, ISzAlloc *alloc);
693 +
694 +#endif
695 --- /dev/null
696 +++ b/include/linux/lzma/LzmaEnc.h
697 @@ -0,0 +1,74 @@
698 +/* LzmaEnc.h -- LZMA Encoder
699 +2008-04-27
700 +Copyright (c) 1999-2008 Igor Pavlov
701 +Read LzFind.h for license options */
702 +
703 +#ifndef __LZMAENC_H
704 +#define __LZMAENC_H
705 +
706 +#include "Types.h"
707 +
708 +#define LZMA_PROPS_SIZE 5
709 +
710 +typedef struct _CLzmaEncProps
711 +{
712 + int level; /* 0 <= level <= 9 */
713 + UInt32 dictSize; /* (1 << 12) <= dictSize <= (1 << 27) for 32-bit version
714 + (1 << 12) <= dictSize <= (1 << 30) for 64-bit version
715 + default = (1 << 24) */
716 + int lc; /* 0 <= lc <= 8, default = 3 */
717 + int lp; /* 0 <= lp <= 4, default = 0 */
718 + int pb; /* 0 <= pb <= 4, default = 2 */
719 + int algo; /* 0 - fast, 1 - normal, default = 1 */
720 + int fb; /* 5 <= fb <= 273, default = 32 */
721 + int btMode; /* 0 - hashChain Mode, 1 - binTree mode - normal, default = 1 */
722 + int numHashBytes; /* 2, 3 or 4, default = 4 */
723 + UInt32 mc; /* 1 <= mc <= (1 << 30), default = 32 */
724 + unsigned writeEndMark; /* 0 - do not write EOPM, 1 - write EOPM, default = 0 */
725 + int numThreads; /* 1 or 2, default = 2 */
726 +} CLzmaEncProps;
727 +
728 +void LzmaEncProps_Init(CLzmaEncProps *p);
729 +void LzmaEncProps_Normalize(CLzmaEncProps *p);
730 +UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2);
731 +
732 +
733 +/* ---------- CLzmaEncHandle Interface ---------- */
734 +
735 +/* LzmaEnc_* functions can return the following exit codes:
736 +Returns:
737 + SZ_OK - OK
738 + SZ_ERROR_MEM - Memory allocation error
739 + SZ_ERROR_PARAM - Incorrect paramater in props
740 + SZ_ERROR_WRITE - Write callback error.
741 + SZ_ERROR_PROGRESS - some break from progress callback
742 + SZ_ERROR_THREAD - errors in multithreading functions (only for Mt version)
743 +*/
744 +
745 +typedef void * CLzmaEncHandle;
746 +
747 +CLzmaEncHandle LzmaEnc_Create(ISzAlloc *alloc);
748 +void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAlloc *alloc, ISzAlloc *allocBig);
749 +SRes LzmaEnc_SetProps(CLzmaEncHandle p, const CLzmaEncProps *props);
750 +SRes LzmaEnc_WriteProperties(CLzmaEncHandle p, Byte *properties, SizeT *size);
751 +SRes LzmaEnc_Encode(CLzmaEncHandle p, ISeqOutStream *outStream, ISeqInStream *inStream,
752 + ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig);
753 +SRes LzmaEnc_MemEncode(CLzmaEncHandle p, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
754 + int writeEndMark, ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig);
755 +
756 +/* ---------- One Call Interface ---------- */
757 +
758 +/* LzmaEncode
759 +Return code:
760 + SZ_OK - OK
761 + SZ_ERROR_MEM - Memory allocation error
762 + SZ_ERROR_PARAM - Incorrect paramater
763 + SZ_ERROR_OUTPUT_EOF - output buffer overflow
764 + SZ_ERROR_THREAD - errors in multithreading functions (only for Mt version)
765 +*/
766 +
767 +SRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
768 + const CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeEndMark,
769 + ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig);
770 +
771 +#endif
772 --- /dev/null
773 +++ b/include/linux/lzma/Types.h
774 @@ -0,0 +1,130 @@
775 +/* Types.h -- Basic types
776 +2008-04-11
777 +Igor Pavlov
778 +Public domain */
779 +
780 +#ifndef __7Z_TYPES_H
781 +#define __7Z_TYPES_H
782 +
783 +#define SZ_OK 0
784 +
785 +#define SZ_ERROR_DATA 1
786 +#define SZ_ERROR_MEM 2
787 +#define SZ_ERROR_CRC 3
788 +#define SZ_ERROR_UNSUPPORTED 4
789 +#define SZ_ERROR_PARAM 5
790 +#define SZ_ERROR_INPUT_EOF 6
791 +#define SZ_ERROR_OUTPUT_EOF 7
792 +#define SZ_ERROR_READ 8
793 +#define SZ_ERROR_WRITE 9
794 +#define SZ_ERROR_PROGRESS 10
795 +#define SZ_ERROR_FAIL 11
796 +#define SZ_ERROR_THREAD 12
797 +
798 +#define SZ_ERROR_ARCHIVE 16
799 +#define SZ_ERROR_NO_ARCHIVE 17
800 +
801 +typedef int SRes;
802 +
803 +#ifndef RINOK
804 +#define RINOK(x) { int __result__ = (x); if (__result__ != 0) return __result__; }
805 +#endif
806 +
807 +typedef unsigned char Byte;
808 +typedef short Int16;
809 +typedef unsigned short UInt16;
810 +
811 +#ifdef _LZMA_UINT32_IS_ULONG
812 +typedef long Int32;
813 +typedef unsigned long UInt32;
814 +#else
815 +typedef int Int32;
816 +typedef unsigned int UInt32;
817 +#endif
818 +
819 +/* #define _SZ_NO_INT_64 */
820 +/* define it if your compiler doesn't support 64-bit integers */
821 +
822 +#ifdef _SZ_NO_INT_64
823 +
824 +typedef long Int64;
825 +typedef unsigned long UInt64;
826 +
827 +#else
828 +
829 +#if defined(_MSC_VER) || defined(__BORLANDC__)
830 +typedef __int64 Int64;
831 +typedef unsigned __int64 UInt64;
832 +#else
833 +typedef long long int Int64;
834 +typedef unsigned long long int UInt64;
835 +#endif
836 +
837 +#endif
838 +
839 +#ifdef _LZMA_NO_SYSTEM_SIZE_T
840 +typedef UInt32 SizeT;
841 +#else
842 +#include <stddef.h>
843 +typedef size_t SizeT;
844 +#endif
845 +
846 +typedef int Bool;
847 +#define True 1
848 +#define False 0
849 +
850 +
851 +#ifdef _MSC_VER
852 +
853 +#if _MSC_VER >= 1300
854 +#define MY_NO_INLINE __declspec(noinline)
855 +#else
856 +#define MY_NO_INLINE
857 +#endif
858 +
859 +#define MY_CDECL __cdecl
860 +#define MY_STD_CALL __stdcall
861 +#define MY_FAST_CALL MY_NO_INLINE __fastcall
862 +
863 +#else
864 +
865 +#define MY_CDECL
866 +#define MY_STD_CALL
867 +#define MY_FAST_CALL
868 +
869 +#endif
870 +
871 +
872 +/* The following interfaces use first parameter as pointer to structure */
873 +
874 +typedef struct
875 +{
876 + SRes (*Read)(void *p, void *buf, size_t *size);
877 + /* if (input(*size) != 0 && output(*size) == 0) means end_of_stream.
878 + (output(*size) < input(*size)) is allowed */
879 +} ISeqInStream;
880 +
881 +typedef struct
882 +{
883 + size_t (*Write)(void *p, const void *buf, size_t size);
884 + /* Returns: result - the number of actually written bytes.
885 + (result < size) means error */
886 +} ISeqOutStream;
887 +
888 +typedef struct
889 +{
890 + SRes (*Progress)(void *p, UInt64 inSize, UInt64 outSize);
891 + /* Returns: result. (result != SZ_OK) means break.
892 + Value (UInt64)(Int64)-1 for size means unknown value. */
893 +} ICompressProgress;
894 +
895 +typedef struct
896 +{
897 + void *(*Alloc)(void *p, size_t size);
898 + void (*Free)(void *p, void *address); /* address can be 0 */
899 +} ISzAlloc;
900 +
901 +#define IAlloc_Alloc(p, size) (p)->Alloc((p), size)
902 +#define IAlloc_Free(p, a) (p)->Free((p), a)
903 +
904 +#endif
905 --- /dev/null
906 +++ b/jffsX-utils/lzma/LzFind.c
907 @@ -0,0 +1,753 @@
908 +/* LzFind.c -- Match finder for LZ algorithms
909 +2008-04-04
910 +Copyright (c) 1999-2008 Igor Pavlov
911 +Read LzFind.h for license options */
912 +
913 +#include <string.h>
914 +
915 +#include "LzFind.h"
916 +#include "LzHash.h"
917 +
918 +#define kEmptyHashValue 0
919 +#define kMaxValForNormalize ((UInt32)0xFFFFFFFF)
920 +#define kNormalizeStepMin (1 << 10) /* it must be power of 2 */
921 +#define kNormalizeMask (~(kNormalizeStepMin - 1))
922 +#define kMaxHistorySize ((UInt32)3 << 30)
923 +
924 +#define kStartMaxLen 3
925 +
926 +static void LzInWindow_Free(CMatchFinder *p, ISzAlloc *alloc)
927 +{
928 + if (!p->directInput)
929 + {
930 + alloc->Free(alloc, p->bufferBase);
931 + p->bufferBase = 0;
932 + }
933 +}
934 +
935 +/* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */
936 +
937 +static int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAlloc *alloc)
938 +{
939 + UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;
940 + if (p->directInput)
941 + {
942 + p->blockSize = blockSize;
943 + return 1;
944 + }
945 + if (p->bufferBase == 0 || p->blockSize != blockSize)
946 + {
947 + LzInWindow_Free(p, alloc);
948 + p->blockSize = blockSize;
949 + p->bufferBase = (Byte *)alloc->Alloc(alloc, (size_t)blockSize);
950 + }
951 + return (p->bufferBase != 0);
952 +}
953 +
954 +Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }
955 +static Byte MatchFinder_GetIndexByte(CMatchFinder *p, Int32 index) { return p->buffer[index]; }
956 +
957 +static UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }
958 +
959 +void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)
960 +{
961 + p->posLimit -= subValue;
962 + p->pos -= subValue;
963 + p->streamPos -= subValue;
964 +}
965 +
966 +static void MatchFinder_ReadBlock(CMatchFinder *p)
967 +{
968 + if (p->streamEndWasReached || p->result != SZ_OK)
969 + return;
970 + for (;;)
971 + {
972 + Byte *dest = p->buffer + (p->streamPos - p->pos);
973 + size_t size = (p->bufferBase + p->blockSize - dest);
974 + if (size == 0)
975 + return;
976 + p->result = p->stream->Read(p->stream, dest, &size);
977 + if (p->result != SZ_OK)
978 + return;
979 + if (size == 0)
980 + {
981 + p->streamEndWasReached = 1;
982 + return;
983 + }
984 + p->streamPos += (UInt32)size;
985 + if (p->streamPos - p->pos > p->keepSizeAfter)
986 + return;
987 + }
988 +}
989 +
990 +void MatchFinder_MoveBlock(CMatchFinder *p)
991 +{
992 + memmove(p->bufferBase,
993 + p->buffer - p->keepSizeBefore,
994 + (size_t)(p->streamPos - p->pos + p->keepSizeBefore));
995 + p->buffer = p->bufferBase + p->keepSizeBefore;
996 +}
997 +
998 +int MatchFinder_NeedMove(CMatchFinder *p)
999 +{
1000 + /* if (p->streamEndWasReached) return 0; */
1001 + return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter);
1002 +}
1003 +
1004 +void MatchFinder_ReadIfRequired(CMatchFinder *p)
1005 +{
1006 + if (p->streamEndWasReached)
1007 + return;
1008 + if (p->keepSizeAfter >= p->streamPos - p->pos)
1009 + MatchFinder_ReadBlock(p);
1010 +}
1011 +
1012 +static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p)
1013 +{
1014 + if (MatchFinder_NeedMove(p))
1015 + MatchFinder_MoveBlock(p);
1016 + MatchFinder_ReadBlock(p);
1017 +}
1018 +
1019 +static void MatchFinder_SetDefaultSettings(CMatchFinder *p)
1020 +{
1021 + p->cutValue = 32;
1022 + p->btMode = 1;
1023 + p->numHashBytes = 4;
1024 + /* p->skipModeBits = 0; */
1025 + p->directInput = 0;
1026 + p->bigHash = 0;
1027 +}
1028 +
1029 +#define kCrcPoly 0xEDB88320
1030 +
1031 +void MatchFinder_Construct(CMatchFinder *p)
1032 +{
1033 + UInt32 i;
1034 + p->bufferBase = 0;
1035 + p->directInput = 0;
1036 + p->hash = 0;
1037 + MatchFinder_SetDefaultSettings(p);
1038 +
1039 + for (i = 0; i < 256; i++)
1040 + {
1041 + UInt32 r = i;
1042 + int j;
1043 + for (j = 0; j < 8; j++)
1044 + r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1));
1045 + p->crc[i] = r;
1046 + }
1047 +}
1048 +
1049 +static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc)
1050 +{
1051 + alloc->Free(alloc, p->hash);
1052 + p->hash = 0;
1053 +}
1054 +
1055 +void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc)
1056 +{
1057 + MatchFinder_FreeThisClassMemory(p, alloc);
1058 + LzInWindow_Free(p, alloc);
1059 +}
1060 +
1061 +static CLzRef* AllocRefs(UInt32 num, ISzAlloc *alloc)
1062 +{
1063 + size_t sizeInBytes = (size_t)num * sizeof(CLzRef);
1064 + if (sizeInBytes / sizeof(CLzRef) != num)
1065 + return 0;
1066 + return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);
1067 +}
1068 +
1069 +int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
1070 + UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
1071 + ISzAlloc *alloc)
1072 +{
1073 + UInt32 sizeReserv;
1074 + if (historySize > kMaxHistorySize)
1075 + {
1076 + MatchFinder_Free(p, alloc);
1077 + return 0;
1078 + }
1079 + sizeReserv = historySize >> 1;
1080 + if (historySize > ((UInt32)2 << 30))
1081 + sizeReserv = historySize >> 2;
1082 + sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);
1083 +
1084 + p->keepSizeBefore = historySize + keepAddBufferBefore + 1;
1085 + p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;
1086 + /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */
1087 + if (LzInWindow_Create(p, sizeReserv, alloc))
1088 + {
1089 + UInt32 newCyclicBufferSize = (historySize /* >> p->skipModeBits */) + 1;
1090 + UInt32 hs;
1091 + p->matchMaxLen = matchMaxLen;
1092 + {
1093 + p->fixedHashSize = 0;
1094 + if (p->numHashBytes == 2)
1095 + hs = (1 << 16) - 1;
1096 + else
1097 + {
1098 + hs = historySize - 1;
1099 + hs |= (hs >> 1);
1100 + hs |= (hs >> 2);
1101 + hs |= (hs >> 4);
1102 + hs |= (hs >> 8);
1103 + hs >>= 1;
1104 + /* hs >>= p->skipModeBits; */
1105 + hs |= 0xFFFF; /* don't change it! It's required for Deflate */
1106 + if (hs > (1 << 24))
1107 + {
1108 + if (p->numHashBytes == 3)
1109 + hs = (1 << 24) - 1;
1110 + else
1111 + hs >>= 1;
1112 + }
1113 + }
1114 + p->hashMask = hs;
1115 + hs++;
1116 + if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;
1117 + if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;
1118 + if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;
1119 + hs += p->fixedHashSize;
1120 + }
1121 +
1122 + {
1123 + UInt32 prevSize = p->hashSizeSum + p->numSons;
1124 + UInt32 newSize;
1125 + p->historySize = historySize;
1126 + p->hashSizeSum = hs;
1127 + p->cyclicBufferSize = newCyclicBufferSize;
1128 + p->numSons = (p->btMode ? newCyclicBufferSize * 2 : newCyclicBufferSize);
1129 + newSize = p->hashSizeSum + p->numSons;
1130 + if (p->hash != 0 && prevSize == newSize)
1131 + return 1;
1132 + MatchFinder_FreeThisClassMemory(p, alloc);
1133 + p->hash = AllocRefs(newSize, alloc);
1134 + if (p->hash != 0)
1135 + {
1136 + p->son = p->hash + p->hashSizeSum;
1137 + return 1;
1138 + }
1139 + }
1140 + }
1141 + MatchFinder_Free(p, alloc);
1142 + return 0;
1143 +}
1144 +
1145 +static void MatchFinder_SetLimits(CMatchFinder *p)
1146 +{
1147 + UInt32 limit = kMaxValForNormalize - p->pos;
1148 + UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;
1149 + if (limit2 < limit)
1150 + limit = limit2;
1151 + limit2 = p->streamPos - p->pos;
1152 + if (limit2 <= p->keepSizeAfter)
1153 + {
1154 + if (limit2 > 0)
1155 + limit2 = 1;
1156 + }
1157 + else
1158 + limit2 -= p->keepSizeAfter;
1159 + if (limit2 < limit)
1160 + limit = limit2;
1161 + {
1162 + UInt32 lenLimit = p->streamPos - p->pos;
1163 + if (lenLimit > p->matchMaxLen)
1164 + lenLimit = p->matchMaxLen;
1165 + p->lenLimit = lenLimit;
1166 + }
1167 + p->posLimit = p->pos + limit;
1168 +}
1169 +
1170 +void MatchFinder_Init(CMatchFinder *p)
1171 +{
1172 + UInt32 i;
1173 + for(i = 0; i < p->hashSizeSum; i++)
1174 + p->hash[i] = kEmptyHashValue;
1175 + p->cyclicBufferPos = 0;
1176 + p->buffer = p->bufferBase;
1177 + p->pos = p->streamPos = p->cyclicBufferSize;
1178 + p->result = SZ_OK;
1179 + p->streamEndWasReached = 0;
1180 + MatchFinder_ReadBlock(p);
1181 + MatchFinder_SetLimits(p);
1182 +}
1183 +
1184 +static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)
1185 +{
1186 + return (p->pos - p->historySize - 1) & kNormalizeMask;
1187 +}
1188 +
1189 +void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems)
1190 +{
1191 + UInt32 i;
1192 + for (i = 0; i < numItems; i++)
1193 + {
1194 + UInt32 value = items[i];
1195 + if (value <= subValue)
1196 + value = kEmptyHashValue;
1197 + else
1198 + value -= subValue;
1199 + items[i] = value;
1200 + }
1201 +}
1202 +
1203 +static void MatchFinder_Normalize(CMatchFinder *p)
1204 +{
1205 + UInt32 subValue = MatchFinder_GetSubValue(p);
1206 + MatchFinder_Normalize3(subValue, p->hash, p->hashSizeSum + p->numSons);
1207 + MatchFinder_ReduceOffsets(p, subValue);
1208 +}
1209 +
1210 +static void MatchFinder_CheckLimits(CMatchFinder *p)
1211 +{
1212 + if (p->pos == kMaxValForNormalize)
1213 + MatchFinder_Normalize(p);
1214 + if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)
1215 + MatchFinder_CheckAndMoveAndRead(p);
1216 + if (p->cyclicBufferPos == p->cyclicBufferSize)
1217 + p->cyclicBufferPos = 0;
1218 + MatchFinder_SetLimits(p);
1219 +}
1220 +
1221 +static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
1222 + UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
1223 + UInt32 *distances, UInt32 maxLen)
1224 +{
1225 + son[_cyclicBufferPos] = curMatch;
1226 + for (;;)
1227 + {
1228 + UInt32 delta = pos - curMatch;
1229 + if (cutValue-- == 0 || delta >= _cyclicBufferSize)
1230 + return distances;
1231 + {
1232 + const Byte *pb = cur - delta;
1233 + curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
1234 + if (pb[maxLen] == cur[maxLen] && *pb == *cur)
1235 + {
1236 + UInt32 len = 0;
1237 + while(++len != lenLimit)
1238 + if (pb[len] != cur[len])
1239 + break;
1240 + if (maxLen < len)
1241 + {
1242 + *distances++ = maxLen = len;
1243 + *distances++ = delta - 1;
1244 + if (len == lenLimit)
1245 + return distances;
1246 + }
1247 + }
1248 + }
1249 + }
1250 +}
1251 +
1252 +UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
1253 + UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
1254 + UInt32 *distances, UInt32 maxLen)
1255 +{
1256 + CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
1257 + CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
1258 + UInt32 len0 = 0, len1 = 0;
1259 + for (;;)
1260 + {
1261 + UInt32 delta = pos - curMatch;
1262 + if (cutValue-- == 0 || delta >= _cyclicBufferSize)
1263 + {
1264 + *ptr0 = *ptr1 = kEmptyHashValue;
1265 + return distances;
1266 + }
1267 + {
1268 + CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
1269 + const Byte *pb = cur - delta;
1270 + UInt32 len = (len0 < len1 ? len0 : len1);
1271 + if (pb[len] == cur[len])
1272 + {
1273 + if (++len != lenLimit && pb[len] == cur[len])
1274 + while(++len != lenLimit)
1275 + if (pb[len] != cur[len])
1276 + break;
1277 + if (maxLen < len)
1278 + {
1279 + *distances++ = maxLen = len;
1280 + *distances++ = delta - 1;
1281 + if (len == lenLimit)
1282 + {
1283 + *ptr1 = pair[0];
1284 + *ptr0 = pair[1];
1285 + return distances;
1286 + }
1287 + }
1288 + }
1289 + if (pb[len] < cur[len])
1290 + {
1291 + *ptr1 = curMatch;
1292 + ptr1 = pair + 1;
1293 + curMatch = *ptr1;
1294 + len1 = len;
1295 + }
1296 + else
1297 + {
1298 + *ptr0 = curMatch;
1299 + ptr0 = pair;
1300 + curMatch = *ptr0;
1301 + len0 = len;
1302 + }
1303 + }
1304 + }
1305 +}
1306 +
1307 +static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
1308 + UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)
1309 +{
1310 + CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
1311 + CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
1312 + UInt32 len0 = 0, len1 = 0;
1313 + for (;;)
1314 + {
1315 + UInt32 delta = pos - curMatch;
1316 + if (cutValue-- == 0 || delta >= _cyclicBufferSize)
1317 + {
1318 + *ptr0 = *ptr1 = kEmptyHashValue;
1319 + return;
1320 + }
1321 + {
1322 + CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
1323 + const Byte *pb = cur - delta;
1324 + UInt32 len = (len0 < len1 ? len0 : len1);
1325 + if (pb[len] == cur[len])
1326 + {
1327 + while(++len != lenLimit)
1328 + if (pb[len] != cur[len])
1329 + break;
1330 + {
1331 + if (len == lenLimit)
1332 + {
1333 + *ptr1 = pair[0];
1334 + *ptr0 = pair[1];
1335 + return;
1336 + }
1337 + }
1338 + }
1339 + if (pb[len] < cur[len])
1340 + {
1341 + *ptr1 = curMatch;
1342 + ptr1 = pair + 1;
1343 + curMatch = *ptr1;
1344 + len1 = len;
1345 + }
1346 + else
1347 + {
1348 + *ptr0 = curMatch;
1349 + ptr0 = pair;
1350 + curMatch = *ptr0;
1351 + len0 = len;
1352 + }
1353 + }
1354 + }
1355 +}
1356 +
1357 +#define MOVE_POS \
1358 + ++p->cyclicBufferPos; \
1359 + p->buffer++; \
1360 + if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);
1361 +
1362 +#define MOVE_POS_RET MOVE_POS return offset;
1363 +
1364 +static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }
1365 +
1366 +#define GET_MATCHES_HEADER2(minLen, ret_op) \
1367 + UInt32 lenLimit; UInt32 hashValue; const Byte *cur; UInt32 curMatch; \
1368 + lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \
1369 + cur = p->buffer;
1370 +
1371 +#define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)
1372 +#define SKIP_HEADER(minLen) GET_MATCHES_HEADER2(minLen, continue)
1373 +
1374 +#define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue
1375 +
1376 +#define GET_MATCHES_FOOTER(offset, maxLen) \
1377 + offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \
1378 + distances + offset, maxLen) - distances); MOVE_POS_RET;
1379 +
1380 +#define SKIP_FOOTER \
1381 + SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;
1382 +
1383 +static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
1384 +{
1385 + UInt32 offset;
1386 + GET_MATCHES_HEADER(2)
1387 + HASH2_CALC;
1388 + curMatch = p->hash[hashValue];
1389 + p->hash[hashValue] = p->pos;
1390 + offset = 0;
1391 + GET_MATCHES_FOOTER(offset, 1)
1392 +}
1393 +
1394 +UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
1395 +{
1396 + UInt32 offset;
1397 + GET_MATCHES_HEADER(3)
1398 + HASH_ZIP_CALC;
1399 + curMatch = p->hash[hashValue];
1400 + p->hash[hashValue] = p->pos;
1401 + offset = 0;
1402 + GET_MATCHES_FOOTER(offset, 2)
1403 +}
1404 +
1405 +static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
1406 +{
1407 + UInt32 hash2Value, delta2, maxLen, offset;
1408 + GET_MATCHES_HEADER(3)
1409 +
1410 + HASH3_CALC;
1411 +
1412 + delta2 = p->pos - p->hash[hash2Value];
1413 + curMatch = p->hash[kFix3HashSize + hashValue];
1414 +
1415 + p->hash[hash2Value] =
1416 + p->hash[kFix3HashSize + hashValue] = p->pos;
1417 +
1418 +
1419 + maxLen = 2;
1420 + offset = 0;
1421 + if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
1422 + {
1423 + for (; maxLen != lenLimit; maxLen++)
1424 + if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
1425 + break;
1426 + distances[0] = maxLen;
1427 + distances[1] = delta2 - 1;
1428 + offset = 2;
1429 + if (maxLen == lenLimit)
1430 + {
1431 + SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
1432 + MOVE_POS_RET;
1433 + }
1434 + }
1435 + GET_MATCHES_FOOTER(offset, maxLen)
1436 +}
1437 +
1438 +static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
1439 +{
1440 + UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
1441 + GET_MATCHES_HEADER(4)
1442 +
1443 + HASH4_CALC;
1444 +
1445 + delta2 = p->pos - p->hash[ hash2Value];
1446 + delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
1447 + curMatch = p->hash[kFix4HashSize + hashValue];
1448 +
1449 + p->hash[ hash2Value] =
1450 + p->hash[kFix3HashSize + hash3Value] =
1451 + p->hash[kFix4HashSize + hashValue] = p->pos;
1452 +
1453 + maxLen = 1;
1454 + offset = 0;
1455 + if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
1456 + {
1457 + distances[0] = maxLen = 2;
1458 + distances[1] = delta2 - 1;
1459 + offset = 2;
1460 + }
1461 + if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
1462 + {
1463 + maxLen = 3;
1464 + distances[offset + 1] = delta3 - 1;
1465 + offset += 2;
1466 + delta2 = delta3;
1467 + }
1468 + if (offset != 0)
1469 + {
1470 + for (; maxLen != lenLimit; maxLen++)
1471 + if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
1472 + break;
1473 + distances[offset - 2] = maxLen;
1474 + if (maxLen == lenLimit)
1475 + {
1476 + SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
1477 + MOVE_POS_RET;
1478 + }
1479 + }
1480 + if (maxLen < 3)
1481 + maxLen = 3;
1482 + GET_MATCHES_FOOTER(offset, maxLen)
1483 +}
1484 +
1485 +static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
1486 +{
1487 + UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
1488 + GET_MATCHES_HEADER(4)
1489 +
1490 + HASH4_CALC;
1491 +
1492 + delta2 = p->pos - p->hash[ hash2Value];
1493 + delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
1494 + curMatch = p->hash[kFix4HashSize + hashValue];
1495 +
1496 + p->hash[ hash2Value] =
1497 + p->hash[kFix3HashSize + hash3Value] =
1498 + p->hash[kFix4HashSize + hashValue] = p->pos;
1499 +
1500 + maxLen = 1;
1501 + offset = 0;
1502 + if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
1503 + {
1504 + distances[0] = maxLen = 2;
1505 + distances[1] = delta2 - 1;
1506 + offset = 2;
1507 + }
1508 + if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
1509 + {
1510 + maxLen = 3;
1511 + distances[offset + 1] = delta3 - 1;
1512 + offset += 2;
1513 + delta2 = delta3;
1514 + }
1515 + if (offset != 0)
1516 + {
1517 + for (; maxLen != lenLimit; maxLen++)
1518 + if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
1519 + break;
1520 + distances[offset - 2] = maxLen;
1521 + if (maxLen == lenLimit)
1522 + {
1523 + p->son[p->cyclicBufferPos] = curMatch;
1524 + MOVE_POS_RET;
1525 + }
1526 + }
1527 + if (maxLen < 3)
1528 + maxLen = 3;
1529 + offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
1530 + distances + offset, maxLen) - (distances));
1531 + MOVE_POS_RET
1532 +}
1533 +
1534 +UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
1535 +{
1536 + UInt32 offset;
1537 + GET_MATCHES_HEADER(3)
1538 + HASH_ZIP_CALC;
1539 + curMatch = p->hash[hashValue];
1540 + p->hash[hashValue] = p->pos;
1541 + offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
1542 + distances, 2) - (distances));
1543 + MOVE_POS_RET
1544 +}
1545 +
1546 +static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1547 +{
1548 + do
1549 + {
1550 + SKIP_HEADER(2)
1551 + HASH2_CALC;
1552 + curMatch = p->hash[hashValue];
1553 + p->hash[hashValue] = p->pos;
1554 + SKIP_FOOTER
1555 + }
1556 + while (--num != 0);
1557 +}
1558 +
1559 +void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1560 +{
1561 + do
1562 + {
1563 + SKIP_HEADER(3)
1564 + HASH_ZIP_CALC;
1565 + curMatch = p->hash[hashValue];
1566 + p->hash[hashValue] = p->pos;
1567 + SKIP_FOOTER
1568 + }
1569 + while (--num != 0);
1570 +}
1571 +
1572 +static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1573 +{
1574 + do
1575 + {
1576 + UInt32 hash2Value;
1577 + SKIP_HEADER(3)
1578 + HASH3_CALC;
1579 + curMatch = p->hash[kFix3HashSize + hashValue];
1580 + p->hash[hash2Value] =
1581 + p->hash[kFix3HashSize + hashValue] = p->pos;
1582 + SKIP_FOOTER
1583 + }
1584 + while (--num != 0);
1585 +}
1586 +
1587 +static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1588 +{
1589 + do
1590 + {
1591 + UInt32 hash2Value, hash3Value;
1592 + SKIP_HEADER(4)
1593 + HASH4_CALC;
1594 + curMatch = p->hash[kFix4HashSize + hashValue];
1595 + p->hash[ hash2Value] =
1596 + p->hash[kFix3HashSize + hash3Value] = p->pos;
1597 + p->hash[kFix4HashSize + hashValue] = p->pos;
1598 + SKIP_FOOTER
1599 + }
1600 + while (--num != 0);
1601 +}
1602 +
1603 +static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1604 +{
1605 + do
1606 + {
1607 + UInt32 hash2Value, hash3Value;
1608 + SKIP_HEADER(4)
1609 + HASH4_CALC;
1610 + curMatch = p->hash[kFix4HashSize + hashValue];
1611 + p->hash[ hash2Value] =
1612 + p->hash[kFix3HashSize + hash3Value] =
1613 + p->hash[kFix4HashSize + hashValue] = p->pos;
1614 + p->son[p->cyclicBufferPos] = curMatch;
1615 + MOVE_POS
1616 + }
1617 + while (--num != 0);
1618 +}
1619 +
1620 +void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1621 +{
1622 + do
1623 + {
1624 + SKIP_HEADER(3)
1625 + HASH_ZIP_CALC;
1626 + curMatch = p->hash[hashValue];
1627 + p->hash[hashValue] = p->pos;
1628 + p->son[p->cyclicBufferPos] = curMatch;
1629 + MOVE_POS
1630 + }
1631 + while (--num != 0);
1632 +}
1633 +
1634 +void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)
1635 +{
1636 + vTable->Init = (Mf_Init_Func)MatchFinder_Init;
1637 + vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinder_GetIndexByte;
1638 + vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;
1639 + vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
1640 + if (!p->btMode)
1641 + {
1642 + vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;
1643 + vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;
1644 + }
1645 + else if (p->numHashBytes == 2)
1646 + {
1647 + vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;
1648 + vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;
1649 + }
1650 + else if (p->numHashBytes == 3)
1651 + {
1652 + vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;
1653 + vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;
1654 + }
1655 + else
1656 + {
1657 + vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;
1658 + vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;
1659 + }
1660 +}
1661 --- /dev/null
1662 +++ b/jffsX-utils/lzma/LzmaDec.c
1663 @@ -0,0 +1,1014 @@
1664 +/* LzmaDec.c -- LZMA Decoder
1665 +2008-04-29
1666 +Copyright (c) 1999-2008 Igor Pavlov
1667 +Read LzmaDec.h for license options */
1668 +
1669 +#include "LzmaDec.h"
1670 +
1671 +#include <string.h>
1672 +
1673 +#define kNumTopBits 24
1674 +#define kTopValue ((UInt32)1 << kNumTopBits)
1675 +
1676 +#define kNumBitModelTotalBits 11
1677 +#define kBitModelTotal (1 << kNumBitModelTotalBits)
1678 +#define kNumMoveBits 5
1679 +
1680 +#define RC_INIT_SIZE 5
1681 +
1682 +#define NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | (*buf++); }
1683 +
1684 +#define IF_BIT_0(p) ttt = *(p); NORMALIZE; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)
1685 +#define UPDATE_0(p) range = bound; *(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));
1686 +#define UPDATE_1(p) range -= bound; code -= bound; *(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits));
1687 +#define GET_BIT2(p, i, A0, A1) IF_BIT_0(p) \
1688 + { UPDATE_0(p); i = (i + i); A0; } else \
1689 + { UPDATE_1(p); i = (i + i) + 1; A1; }
1690 +#define GET_BIT(p, i) GET_BIT2(p, i, ; , ;)
1691 +
1692 +#define TREE_GET_BIT(probs, i) { GET_BIT((probs + i), i); }
1693 +#define TREE_DECODE(probs, limit, i) \
1694 + { i = 1; do { TREE_GET_BIT(probs, i); } while (i < limit); i -= limit; }
1695 +
1696 +/* #define _LZMA_SIZE_OPT */
1697 +
1698 +#ifdef _LZMA_SIZE_OPT
1699 +#define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i)
1700 +#else
1701 +#define TREE_6_DECODE(probs, i) \
1702 + { i = 1; \
1703 + TREE_GET_BIT(probs, i); \
1704 + TREE_GET_BIT(probs, i); \
1705 + TREE_GET_BIT(probs, i); \
1706 + TREE_GET_BIT(probs, i); \
1707 + TREE_GET_BIT(probs, i); \
1708 + TREE_GET_BIT(probs, i); \
1709 + i -= 0x40; }
1710 +#endif
1711 +
1712 +#define NORMALIZE_CHECK if (range < kTopValue) { if (buf >= bufLimit) return DUMMY_ERROR; range <<= 8; code = (code << 8) | (*buf++); }
1713 +
1714 +#define IF_BIT_0_CHECK(p) ttt = *(p); NORMALIZE_CHECK; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)
1715 +#define UPDATE_0_CHECK range = bound;
1716 +#define UPDATE_1_CHECK range -= bound; code -= bound;
1717 +#define GET_BIT2_CHECK(p, i, A0, A1) IF_BIT_0_CHECK(p) \
1718 + { UPDATE_0_CHECK; i = (i + i); A0; } else \
1719 + { UPDATE_1_CHECK; i = (i + i) + 1; A1; }
1720 +#define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ; , ;)
1721 +#define TREE_DECODE_CHECK(probs, limit, i) \
1722 + { i = 1; do { GET_BIT_CHECK(probs + i, i) } while(i < limit); i -= limit; }
1723 +
1724 +
1725 +#define kNumPosBitsMax 4
1726 +#define kNumPosStatesMax (1 << kNumPosBitsMax)
1727 +
1728 +#define kLenNumLowBits 3
1729 +#define kLenNumLowSymbols (1 << kLenNumLowBits)
1730 +#define kLenNumMidBits 3
1731 +#define kLenNumMidSymbols (1 << kLenNumMidBits)
1732 +#define kLenNumHighBits 8
1733 +#define kLenNumHighSymbols (1 << kLenNumHighBits)
1734 +
1735 +#define LenChoice 0
1736 +#define LenChoice2 (LenChoice + 1)
1737 +#define LenLow (LenChoice2 + 1)
1738 +#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
1739 +#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
1740 +#define kNumLenProbs (LenHigh + kLenNumHighSymbols)
1741 +
1742 +
1743 +#define kNumStates 12
1744 +#define kNumLitStates 7
1745 +
1746 +#define kStartPosModelIndex 4
1747 +#define kEndPosModelIndex 14
1748 +#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
1749 +
1750 +#define kNumPosSlotBits 6
1751 +#define kNumLenToPosStates 4
1752 +
1753 +#define kNumAlignBits 4
1754 +#define kAlignTableSize (1 << kNumAlignBits)
1755 +
1756 +#define kMatchMinLen 2
1757 +#define kMatchSpecLenStart (kMatchMinLen + kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)
1758 +
1759 +#define IsMatch 0
1760 +#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
1761 +#define IsRepG0 (IsRep + kNumStates)
1762 +#define IsRepG1 (IsRepG0 + kNumStates)
1763 +#define IsRepG2 (IsRepG1 + kNumStates)
1764 +#define IsRep0Long (IsRepG2 + kNumStates)
1765 +#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
1766 +#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
1767 +#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
1768 +#define LenCoder (Align + kAlignTableSize)
1769 +#define RepLenCoder (LenCoder + kNumLenProbs)
1770 +#define Literal (RepLenCoder + kNumLenProbs)
1771 +
1772 +#define LZMA_BASE_SIZE 1846
1773 +#define LZMA_LIT_SIZE 768
1774 +
1775 +#define LzmaProps_GetNumProbs(p) ((UInt32)LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))
1776 +
1777 +#if Literal != LZMA_BASE_SIZE
1778 +StopCompilingDueBUG
1779 +#endif
1780 +
1781 +/*
1782 +#define LZMA_STREAM_WAS_FINISHED_ID (-1)
1783 +#define LZMA_SPEC_LEN_OFFSET (-3)
1784 +*/
1785 +
1786 +Byte kLiteralNextStates[kNumStates * 2] =
1787 +{
1788 + 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5,
1789 + 7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10
1790 +};
1791 +
1792 +#define LZMA_DIC_MIN (1 << 12)
1793 +
1794 +/* First LZMA-symbol is always decoded.
1795 +And it decodes new LZMA-symbols while (buf < bufLimit), but "buf" is without last normalization
1796 +Out:
1797 + Result:
1798 + 0 - OK
1799 + 1 - Error
1800 + p->remainLen:
1801 + < kMatchSpecLenStart : normal remain
1802 + = kMatchSpecLenStart : finished
1803 + = kMatchSpecLenStart + 1 : Flush marker
1804 + = kMatchSpecLenStart + 2 : State Init Marker
1805 +*/
1806 +
1807 +static int MY_FAST_CALL LzmaDec_DecodeReal(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
1808 +{
1809 + CLzmaProb *probs = p->probs;
1810 +
1811 + unsigned state = p->state;
1812 + UInt32 rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3];
1813 + unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1;
1814 + unsigned lpMask = ((unsigned)1 << (p->prop.lp)) - 1;
1815 + unsigned lc = p->prop.lc;
1816 +
1817 + Byte *dic = p->dic;
1818 + SizeT dicBufSize = p->dicBufSize;
1819 + SizeT dicPos = p->dicPos;
1820 +
1821 + UInt32 processedPos = p->processedPos;
1822 + UInt32 checkDicSize = p->checkDicSize;
1823 + unsigned len = 0;
1824 +
1825 + const Byte *buf = p->buf;
1826 + UInt32 range = p->range;
1827 + UInt32 code = p->code;
1828 +
1829 + do
1830 + {
1831 + CLzmaProb *prob;
1832 + UInt32 bound;
1833 + unsigned ttt;
1834 + unsigned posState = processedPos & pbMask;
1835 +
1836 + prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
1837 + IF_BIT_0(prob)
1838 + {
1839 + unsigned symbol;
1840 + UPDATE_0(prob);
1841 + prob = probs + Literal;
1842 + if (checkDicSize != 0 || processedPos != 0)
1843 + prob += (LZMA_LIT_SIZE * (((processedPos & lpMask) << lc) +
1844 + (dic[(dicPos == 0 ? dicBufSize : dicPos) - 1] >> (8 - lc))));
1845 +
1846 + if (state < kNumLitStates)
1847 + {
1848 + symbol = 1;
1849 + do { GET_BIT(prob + symbol, symbol) } while (symbol < 0x100);
1850 + }
1851 + else
1852 + {
1853 + unsigned matchByte = p->dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
1854 + unsigned offs = 0x100;
1855 + symbol = 1;
1856 + do
1857 + {
1858 + unsigned bit;
1859 + CLzmaProb *probLit;
1860 + matchByte <<= 1;
1861 + bit = (matchByte & offs);
1862 + probLit = prob + offs + bit + symbol;
1863 + GET_BIT2(probLit, symbol, offs &= ~bit, offs &= bit)
1864 + }
1865 + while (symbol < 0x100);
1866 + }
1867 + dic[dicPos++] = (Byte)symbol;
1868 + processedPos++;
1869 +
1870 + state = kLiteralNextStates[state];
1871 + /* if (state < 4) state = 0; else if (state < 10) state -= 3; else state -= 6; */
1872 + continue;
1873 + }
1874 + else
1875 + {
1876 + UPDATE_1(prob);
1877 + prob = probs + IsRep + state;
1878 + IF_BIT_0(prob)
1879 + {
1880 + UPDATE_0(prob);
1881 + state += kNumStates;
1882 + prob = probs + LenCoder;
1883 + }
1884 + else
1885 + {
1886 + UPDATE_1(prob);
1887 + if (checkDicSize == 0 && processedPos == 0)
1888 + return SZ_ERROR_DATA;
1889 + prob = probs + IsRepG0 + state;
1890 + IF_BIT_0(prob)
1891 + {
1892 + UPDATE_0(prob);
1893 + prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
1894 + IF_BIT_0(prob)
1895 + {
1896 + UPDATE_0(prob);
1897 + dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
1898 + dicPos++;
1899 + processedPos++;
1900 + state = state < kNumLitStates ? 9 : 11;
1901 + continue;
1902 + }
1903 + UPDATE_1(prob);
1904 + }
1905 + else
1906 + {
1907 + UInt32 distance;
1908 + UPDATE_1(prob);
1909 + prob = probs + IsRepG1 + state;
1910 + IF_BIT_0(prob)
1911 + {
1912 + UPDATE_0(prob);
1913 + distance = rep1;
1914 + }
1915 + else
1916 + {
1917 + UPDATE_1(prob);
1918 + prob = probs + IsRepG2 + state;
1919 + IF_BIT_0(prob)
1920 + {
1921 + UPDATE_0(prob);
1922 + distance = rep2;
1923 + }
1924 + else
1925 + {
1926 + UPDATE_1(prob);
1927 + distance = rep3;
1928 + rep3 = rep2;
1929 + }
1930 + rep2 = rep1;
1931 + }
1932 + rep1 = rep0;
1933 + rep0 = distance;
1934 + }
1935 + state = state < kNumLitStates ? 8 : 11;
1936 + prob = probs + RepLenCoder;
1937 + }
1938 + {
1939 + unsigned limit, offset;
1940 + CLzmaProb *probLen = prob + LenChoice;
1941 + IF_BIT_0(probLen)
1942 + {
1943 + UPDATE_0(probLen);
1944 + probLen = prob + LenLow + (posState << kLenNumLowBits);
1945 + offset = 0;
1946 + limit = (1 << kLenNumLowBits);
1947 + }
1948 + else
1949 + {
1950 + UPDATE_1(probLen);
1951 + probLen = prob + LenChoice2;
1952 + IF_BIT_0(probLen)
1953 + {
1954 + UPDATE_0(probLen);
1955 + probLen = prob + LenMid + (posState << kLenNumMidBits);
1956 + offset = kLenNumLowSymbols;
1957 + limit = (1 << kLenNumMidBits);
1958 + }
1959 + else
1960 + {
1961 + UPDATE_1(probLen);
1962 + probLen = prob + LenHigh;
1963 + offset = kLenNumLowSymbols + kLenNumMidSymbols;
1964 + limit = (1 << kLenNumHighBits);
1965 + }
1966 + }
1967 + TREE_DECODE(probLen, limit, len);
1968 + len += offset;
1969 + }
1970 +
1971 + if (state >= kNumStates)
1972 + {
1973 + UInt32 distance;
1974 + prob = probs + PosSlot +
1975 + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits);
1976 + TREE_6_DECODE(prob, distance);
1977 + if (distance >= kStartPosModelIndex)
1978 + {
1979 + unsigned posSlot = (unsigned)distance;
1980 + int numDirectBits = (int)(((distance >> 1) - 1));
1981 + distance = (2 | (distance & 1));
1982 + if (posSlot < kEndPosModelIndex)
1983 + {
1984 + distance <<= numDirectBits;
1985 + prob = probs + SpecPos + distance - posSlot - 1;
1986 + {
1987 + UInt32 mask = 1;
1988 + unsigned i = 1;
1989 + do
1990 + {
1991 + GET_BIT2(prob + i, i, ; , distance |= mask);
1992 + mask <<= 1;
1993 + }
1994 + while(--numDirectBits != 0);
1995 + }
1996 + }
1997 + else
1998 + {
1999 + numDirectBits -= kNumAlignBits;
2000 + do
2001 + {
2002 + NORMALIZE
2003 + range >>= 1;
2004 +
2005 + {
2006 + UInt32 t;
2007 + code -= range;
2008 + t = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */
2009 + distance = (distance << 1) + (t + 1);
2010 + code += range & t;
2011 + }
2012 + /*
2013 + distance <<= 1;
2014 + if (code >= range)
2015 + {
2016 + code -= range;
2017 + distance |= 1;
2018 + }
2019 + */
2020 + }
2021 + while (--numDirectBits != 0);
2022 + prob = probs + Align;
2023 + distance <<= kNumAlignBits;
2024 + {
2025 + unsigned i = 1;
2026 + GET_BIT2(prob + i, i, ; , distance |= 1);
2027 + GET_BIT2(prob + i, i, ; , distance |= 2);
2028 + GET_BIT2(prob + i, i, ; , distance |= 4);
2029 + GET_BIT2(prob + i, i, ; , distance |= 8);
2030 + }
2031 + if (distance == (UInt32)0xFFFFFFFF)
2032 + {
2033 + len += kMatchSpecLenStart;
2034 + state -= kNumStates;
2035 + break;
2036 + }
2037 + }
2038 + }
2039 + rep3 = rep2;
2040 + rep2 = rep1;
2041 + rep1 = rep0;
2042 + rep0 = distance + 1;
2043 + if (checkDicSize == 0)
2044 + {
2045 + if (distance >= processedPos)
2046 + return SZ_ERROR_DATA;
2047 + }
2048 + else if (distance >= checkDicSize)
2049 + return SZ_ERROR_DATA;
2050 + state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3;
2051 + /* state = kLiteralNextStates[state]; */
2052 + }
2053 +
2054 + len += kMatchMinLen;
2055 +
2056 + {
2057 + SizeT rem = limit - dicPos;
2058 + unsigned curLen = ((rem < len) ? (unsigned)rem : len);
2059 + SizeT pos = (dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0);
2060 +
2061 + processedPos += curLen;
2062 +
2063 + len -= curLen;
2064 + if (pos + curLen <= dicBufSize)
2065 + {
2066 + Byte *dest = dic + dicPos;
2067 + ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos;
2068 + const Byte *lim = dest + curLen;
2069 + dicPos += curLen;
2070 + do
2071 + *(dest) = (Byte)*(dest + src);
2072 + while (++dest != lim);
2073 + }
2074 + else
2075 + {
2076 + do
2077 + {
2078 + dic[dicPos++] = dic[pos];
2079 + if (++pos == dicBufSize)
2080 + pos = 0;
2081 + }
2082 + while (--curLen != 0);
2083 + }
2084 + }
2085 + }
2086 + }
2087 + while (dicPos < limit && buf < bufLimit);
2088 + NORMALIZE;
2089 + p->buf = buf;
2090 + p->range = range;
2091 + p->code = code;
2092 + p->remainLen = len;
2093 + p->dicPos = dicPos;
2094 + p->processedPos = processedPos;
2095 + p->reps[0] = rep0;
2096 + p->reps[1] = rep1;
2097 + p->reps[2] = rep2;
2098 + p->reps[3] = rep3;
2099 + p->state = state;
2100 +
2101 + return SZ_OK;
2102 +}
2103 +
2104 +static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit)
2105 +{
2106 + if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart)
2107 + {
2108 + Byte *dic = p->dic;
2109 + SizeT dicPos = p->dicPos;
2110 + SizeT dicBufSize = p->dicBufSize;
2111 + unsigned len = p->remainLen;
2112 + UInt32 rep0 = p->reps[0];
2113 + if (limit - dicPos < len)
2114 + len = (unsigned)(limit - dicPos);
2115 +
2116 + if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len)
2117 + p->checkDicSize = p->prop.dicSize;
2118 +
2119 + p->processedPos += len;
2120 + p->remainLen -= len;
2121 + while (len-- != 0)
2122 + {
2123 + dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
2124 + dicPos++;
2125 + }
2126 + p->dicPos = dicPos;
2127 + }
2128 +}
2129 +
2130 +/* LzmaDec_DecodeReal2 decodes LZMA-symbols and sets p->needFlush and p->needInit, if required. */
2131 +
2132 +static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
2133 +{
2134 + do
2135 + {
2136 + SizeT limit2 = limit;
2137 + if (p->checkDicSize == 0)
2138 + {
2139 + UInt32 rem = p->prop.dicSize - p->processedPos;
2140 + if (limit - p->dicPos > rem)
2141 + limit2 = p->dicPos + rem;
2142 + }
2143 + RINOK(LzmaDec_DecodeReal(p, limit2, bufLimit));
2144 + if (p->processedPos >= p->prop.dicSize)
2145 + p->checkDicSize = p->prop.dicSize;
2146 + LzmaDec_WriteRem(p, limit);
2147 + }
2148 + while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart);
2149 +
2150 + if (p->remainLen > kMatchSpecLenStart)
2151 + {
2152 + p->remainLen = kMatchSpecLenStart;
2153 + }
2154 + return 0;
2155 +}
2156 +
2157 +typedef enum
2158 +{
2159 + DUMMY_ERROR, /* unexpected end of input stream */
2160 + DUMMY_LIT,
2161 + DUMMY_MATCH,
2162 + DUMMY_REP
2163 +} ELzmaDummy;
2164 +
2165 +static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, SizeT inSize)
2166 +{
2167 + UInt32 range = p->range;
2168 + UInt32 code = p->code;
2169 + const Byte *bufLimit = buf + inSize;
2170 + CLzmaProb *probs = p->probs;
2171 + unsigned state = p->state;
2172 + ELzmaDummy res;
2173 +
2174 + {
2175 + CLzmaProb *prob;
2176 + UInt32 bound;
2177 + unsigned ttt;
2178 + unsigned posState = (p->processedPos) & ((1 << p->prop.pb) - 1);
2179 +
2180 + prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
2181 + IF_BIT_0_CHECK(prob)
2182 + {
2183 + UPDATE_0_CHECK
2184 +
2185 + /* if (bufLimit - buf >= 7) return DUMMY_LIT; */
2186 +
2187 + prob = probs + Literal;
2188 + if (p->checkDicSize != 0 || p->processedPos != 0)
2189 + prob += (LZMA_LIT_SIZE *
2190 + ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) +
2191 + (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc))));
2192 +
2193 + if (state < kNumLitStates)
2194 + {
2195 + unsigned symbol = 1;
2196 + do { GET_BIT_CHECK(prob + symbol, symbol) } while (symbol < 0x100);
2197 + }
2198 + else
2199 + {
2200 + unsigned matchByte = p->dic[p->dicPos - p->reps[0] +
2201 + ((p->dicPos < p->reps[0]) ? p->dicBufSize : 0)];
2202 + unsigned offs = 0x100;
2203 + unsigned symbol = 1;
2204 + do
2205 + {
2206 + unsigned bit;
2207 + CLzmaProb *probLit;
2208 + matchByte <<= 1;
2209 + bit = (matchByte & offs);
2210 + probLit = prob + offs + bit + symbol;
2211 + GET_BIT2_CHECK(probLit, symbol, offs &= ~bit, offs &= bit)
2212 + }
2213 + while (symbol < 0x100);
2214 + }
2215 + res = DUMMY_LIT;
2216 + }
2217 + else
2218 + {
2219 + unsigned len;
2220 + UPDATE_1_CHECK;
2221 +
2222 + prob = probs + IsRep + state;
2223 + IF_BIT_0_CHECK(prob)
2224 + {
2225 + UPDATE_0_CHECK;
2226 + state = 0;
2227 + prob = probs + LenCoder;
2228 + res = DUMMY_MATCH;
2229 + }
2230 + else
2231 + {
2232 + UPDATE_1_CHECK;
2233 + res = DUMMY_REP;
2234 + prob = probs + IsRepG0 + state;
2235 + IF_BIT_0_CHECK(prob)
2236 + {
2237 + UPDATE_0_CHECK;
2238 + prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
2239 + IF_BIT_0_CHECK(prob)
2240 + {
2241 + UPDATE_0_CHECK;
2242 + NORMALIZE_CHECK;
2243 + return DUMMY_REP;
2244 + }
2245 + else
2246 + {
2247 + UPDATE_1_CHECK;
2248 + }
2249 + }
2250 + else
2251 + {
2252 + UPDATE_1_CHECK;
2253 + prob = probs + IsRepG1 + state;
2254 + IF_BIT_0_CHECK(prob)
2255 + {
2256 + UPDATE_0_CHECK;
2257 + }
2258 + else
2259 + {
2260 + UPDATE_1_CHECK;
2261 + prob = probs + IsRepG2 + state;
2262 + IF_BIT_0_CHECK(prob)
2263 + {
2264 + UPDATE_0_CHECK;
2265 + }
2266 + else
2267 + {
2268 + UPDATE_1_CHECK;
2269 + }
2270 + }
2271 + }
2272 + state = kNumStates;
2273 + prob = probs + RepLenCoder;
2274 + }
2275 + {
2276 + unsigned limit, offset;
2277 + CLzmaProb *probLen = prob + LenChoice;
2278 + IF_BIT_0_CHECK(probLen)
2279 + {
2280 + UPDATE_0_CHECK;
2281 + probLen = prob + LenLow + (posState << kLenNumLowBits);
2282 + offset = 0;
2283 + limit = 1 << kLenNumLowBits;
2284 + }
2285 + else
2286 + {
2287 + UPDATE_1_CHECK;
2288 + probLen = prob + LenChoice2;
2289 + IF_BIT_0_CHECK(probLen)
2290 + {
2291 + UPDATE_0_CHECK;
2292 + probLen = prob + LenMid + (posState << kLenNumMidBits);
2293 + offset = kLenNumLowSymbols;
2294 + limit = 1 << kLenNumMidBits;
2295 + }
2296 + else
2297 + {
2298 + UPDATE_1_CHECK;
2299 + probLen = prob + LenHigh;
2300 + offset = kLenNumLowSymbols + kLenNumMidSymbols;
2301 + limit = 1 << kLenNumHighBits;
2302 + }
2303 + }
2304 + TREE_DECODE_CHECK(probLen, limit, len);
2305 + len += offset;
2306 + }
2307 +
2308 + if (state < 4)
2309 + {
2310 + unsigned posSlot;
2311 + prob = probs + PosSlot +
2312 + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
2313 + kNumPosSlotBits);
2314 + TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot);
2315 + if (posSlot >= kStartPosModelIndex)
2316 + {
2317 + int numDirectBits = ((posSlot >> 1) - 1);
2318 +
2319 + /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */
2320 +
2321 + if (posSlot < kEndPosModelIndex)
2322 + {
2323 + prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits) - posSlot - 1;
2324 + }
2325 + else
2326 + {
2327 + numDirectBits -= kNumAlignBits;
2328 + do
2329 + {
2330 + NORMALIZE_CHECK
2331 + range >>= 1;
2332 + code -= range & (((code - range) >> 31) - 1);
2333 + /* if (code >= range) code -= range; */
2334 + }
2335 + while (--numDirectBits != 0);
2336 + prob = probs + Align;
2337 + numDirectBits = kNumAlignBits;
2338 + }
2339 + {
2340 + unsigned i = 1;
2341 + do
2342 + {
2343 + GET_BIT_CHECK(prob + i, i);
2344 + }
2345 + while(--numDirectBits != 0);
2346 + }
2347 + }
2348 + }
2349 + }
2350 + }
2351 + NORMALIZE_CHECK;
2352 + return res;
2353 +}
2354 +
2355 +
2356 +static void LzmaDec_InitRc(CLzmaDec *p, const Byte *data)
2357 +{
2358 + p->code = ((UInt32)data[1] << 24) | ((UInt32)data[2] << 16) | ((UInt32)data[3] << 8) | ((UInt32)data[4]);
2359 + p->range = 0xFFFFFFFF;
2360 + p->needFlush = 0;
2361 +}
2362 +
2363 +static void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState)
2364 +{
2365 + p->needFlush = 1;
2366 + p->remainLen = 0;
2367 + p->tempBufSize = 0;
2368 +
2369 + if (initDic)
2370 + {
2371 + p->processedPos = 0;
2372 + p->checkDicSize = 0;
2373 + p->needInitState = 1;
2374 + }
2375 + if (initState)
2376 + p->needInitState = 1;
2377 +}
2378 +
2379 +void LzmaDec_Init(CLzmaDec *p)
2380 +{
2381 + p->dicPos = 0;
2382 + LzmaDec_InitDicAndState(p, True, True);
2383 +}
2384 +
2385 +static void LzmaDec_InitStateReal(CLzmaDec *p)
2386 +{
2387 + UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (p->prop.lc + p->prop.lp));
2388 + UInt32 i;
2389 + CLzmaProb *probs = p->probs;
2390 + for (i = 0; i < numProbs; i++)
2391 + probs[i] = kBitModelTotal >> 1;
2392 + p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1;
2393 + p->state = 0;
2394 + p->needInitState = 0;
2395 +}
2396 +
2397 +SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen,
2398 + ELzmaFinishMode finishMode, ELzmaStatus *status)
2399 +{
2400 + SizeT inSize = *srcLen;
2401 + (*srcLen) = 0;
2402 + LzmaDec_WriteRem(p, dicLimit);
2403 +
2404 + *status = LZMA_STATUS_NOT_SPECIFIED;
2405 +
2406 + while (p->remainLen != kMatchSpecLenStart)
2407 + {
2408 + int checkEndMarkNow;
2409 +
2410 + if (p->needFlush != 0)
2411 + {
2412 + for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--)
2413 + p->tempBuf[p->tempBufSize++] = *src++;
2414 + if (p->tempBufSize < RC_INIT_SIZE)
2415 + {
2416 + *status = LZMA_STATUS_NEEDS_MORE_INPUT;
2417 + return SZ_OK;
2418 + }
2419 + if (p->tempBuf[0] != 0)
2420 + return SZ_ERROR_DATA;
2421 +
2422 + LzmaDec_InitRc(p, p->tempBuf);
2423 + p->tempBufSize = 0;
2424 + }
2425 +
2426 + checkEndMarkNow = 0;
2427 + if (p->dicPos >= dicLimit)
2428 + {
2429 + if (p->remainLen == 0 && p->code == 0)
2430 + {
2431 + *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK;
2432 + return SZ_OK;
2433 + }
2434 + if (finishMode == LZMA_FINISH_ANY)
2435 + {
2436 + *status = LZMA_STATUS_NOT_FINISHED;
2437 + return SZ_OK;
2438 + }
2439 + if (p->remainLen != 0)
2440 + {
2441 + *status = LZMA_STATUS_NOT_FINISHED;
2442 + return SZ_ERROR_DATA;
2443 + }
2444 + checkEndMarkNow = 1;
2445 + }
2446 +
2447 + if (p->needInitState)
2448 + LzmaDec_InitStateReal(p);
2449 +
2450 + if (p->tempBufSize == 0)
2451 + {
2452 + SizeT processed;
2453 + const Byte *bufLimit;
2454 + if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
2455 + {
2456 + int dummyRes = LzmaDec_TryDummy(p, src, inSize);
2457 + if (dummyRes == DUMMY_ERROR)
2458 + {
2459 + memcpy(p->tempBuf, src, inSize);
2460 + p->tempBufSize = (unsigned)inSize;
2461 + (*srcLen) += inSize;
2462 + *status = LZMA_STATUS_NEEDS_MORE_INPUT;
2463 + return SZ_OK;
2464 + }
2465 + if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
2466 + {
2467 + *status = LZMA_STATUS_NOT_FINISHED;
2468 + return SZ_ERROR_DATA;
2469 + }
2470 + bufLimit = src;
2471 + }
2472 + else
2473 + bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX;
2474 + p->buf = src;
2475 + if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0)
2476 + return SZ_ERROR_DATA;
2477 + processed = p->buf - src;
2478 + (*srcLen) += processed;
2479 + src += processed;
2480 + inSize -= processed;
2481 + }
2482 + else
2483 + {
2484 + unsigned rem = p->tempBufSize, lookAhead = 0;
2485 + while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize)
2486 + p->tempBuf[rem++] = src[lookAhead++];
2487 + p->tempBufSize = rem;
2488 + if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
2489 + {
2490 + int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem);
2491 + if (dummyRes == DUMMY_ERROR)
2492 + {
2493 + (*srcLen) += lookAhead;
2494 + *status = LZMA_STATUS_NEEDS_MORE_INPUT;
2495 + return SZ_OK;
2496 + }
2497 + if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
2498 + {
2499 + *status = LZMA_STATUS_NOT_FINISHED;
2500 + return SZ_ERROR_DATA;
2501 + }
2502 + }
2503 + p->buf = p->tempBuf;
2504 + if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0)
2505 + return SZ_ERROR_DATA;
2506 + lookAhead -= (rem - (unsigned)(p->buf - p->tempBuf));
2507 + (*srcLen) += lookAhead;
2508 + src += lookAhead;
2509 + inSize -= lookAhead;
2510 + p->tempBufSize = 0;
2511 + }
2512 + }
2513 + if (p->code == 0)
2514 + *status = LZMA_STATUS_FINISHED_WITH_MARK;
2515 + return (p->code == 0) ? SZ_OK : SZ_ERROR_DATA;
2516 +}
2517 +
2518 +SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status)
2519 +{
2520 + SizeT outSize = *destLen;
2521 + SizeT inSize = *srcLen;
2522 + *srcLen = *destLen = 0;
2523 + for (;;)
2524 + {
2525 + SizeT inSizeCur = inSize, outSizeCur, dicPos;
2526 + ELzmaFinishMode curFinishMode;
2527 + SRes res;
2528 + if (p->dicPos == p->dicBufSize)
2529 + p->dicPos = 0;
2530 + dicPos = p->dicPos;
2531 + if (outSize > p->dicBufSize - dicPos)
2532 + {
2533 + outSizeCur = p->dicBufSize;
2534 + curFinishMode = LZMA_FINISH_ANY;
2535 + }
2536 + else
2537 + {
2538 + outSizeCur = dicPos + outSize;
2539 + curFinishMode = finishMode;
2540 + }
2541 +
2542 + res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status);
2543 + src += inSizeCur;
2544 + inSize -= inSizeCur;
2545 + *srcLen += inSizeCur;
2546 + outSizeCur = p->dicPos - dicPos;
2547 + memcpy(dest, p->dic + dicPos, outSizeCur);
2548 + dest += outSizeCur;
2549 + outSize -= outSizeCur;
2550 + *destLen += outSizeCur;
2551 + if (res != 0)
2552 + return res;
2553 + if (outSizeCur == 0 || outSize == 0)
2554 + return SZ_OK;
2555 + }
2556 +}
2557 +
2558 +void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc)
2559 +{
2560 + alloc->Free(alloc, p->probs);
2561 + p->probs = 0;
2562 +}
2563 +
2564 +static void LzmaDec_FreeDict(CLzmaDec *p, ISzAlloc *alloc)
2565 +{
2566 + alloc->Free(alloc, p->dic);
2567 + p->dic = 0;
2568 +}
2569 +
2570 +void LzmaDec_Free(CLzmaDec *p, ISzAlloc *alloc)
2571 +{
2572 + LzmaDec_FreeProbs(p, alloc);
2573 + LzmaDec_FreeDict(p, alloc);
2574 +}
2575 +
2576 +SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size)
2577 +{
2578 + UInt32 dicSize;
2579 + Byte d;
2580 +
2581 + if (size < LZMA_PROPS_SIZE)
2582 + return SZ_ERROR_UNSUPPORTED;
2583 + else
2584 + dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24);
2585 +
2586 + if (dicSize < LZMA_DIC_MIN)
2587 + dicSize = LZMA_DIC_MIN;
2588 + p->dicSize = dicSize;
2589 +
2590 + d = data[0];
2591 + if (d >= (9 * 5 * 5))
2592 + return SZ_ERROR_UNSUPPORTED;
2593 +
2594 + p->lc = d % 9;
2595 + d /= 9;
2596 + p->pb = d / 5;
2597 + p->lp = d % 5;
2598 +
2599 + return SZ_OK;
2600 +}
2601 +
2602 +static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAlloc *alloc)
2603 +{
2604 + UInt32 numProbs = LzmaProps_GetNumProbs(propNew);
2605 + if (p->probs == 0 || numProbs != p->numProbs)
2606 + {
2607 + LzmaDec_FreeProbs(p, alloc);
2608 + p->probs = (CLzmaProb *)alloc->Alloc(alloc, numProbs * sizeof(CLzmaProb));
2609 + p->numProbs = numProbs;
2610 + if (p->probs == 0)
2611 + return SZ_ERROR_MEM;
2612 + }
2613 + return SZ_OK;
2614 +}
2615 +
2616 +SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
2617 +{
2618 + CLzmaProps propNew;
2619 + RINOK(LzmaProps_Decode(&propNew, props, propsSize));
2620 + RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
2621 + p->prop = propNew;
2622 + return SZ_OK;
2623 +}
2624 +
2625 +SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
2626 +{
2627 + CLzmaProps propNew;
2628 + SizeT dicBufSize;
2629 + RINOK(LzmaProps_Decode(&propNew, props, propsSize));
2630 + RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
2631 + dicBufSize = propNew.dicSize;
2632 + if (p->dic == 0 || dicBufSize != p->dicBufSize)
2633 + {
2634 + LzmaDec_FreeDict(p, alloc);
2635 + p->dic = (Byte *)alloc->Alloc(alloc, dicBufSize);
2636 + if (p->dic == 0)
2637 + {
2638 + LzmaDec_FreeProbs(p, alloc);
2639 + return SZ_ERROR_MEM;
2640 + }
2641 + }
2642 + p->dicBufSize = dicBufSize;
2643 + p->prop = propNew;
2644 + return SZ_OK;
2645 +}
2646 +
2647 +SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
2648 + const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,
2649 + ELzmaStatus *status, ISzAlloc *alloc)
2650 +{
2651 + CLzmaDec p;
2652 + SRes res;
2653 + SizeT inSize = *srcLen;
2654 + SizeT outSize = *destLen;
2655 + *srcLen = *destLen = 0;
2656 + if (inSize < RC_INIT_SIZE)
2657 + return SZ_ERROR_INPUT_EOF;
2658 +
2659 + LzmaDec_Construct(&p);
2660 + res = LzmaDec_AllocateProbs(&p, propData, propSize, alloc);
2661 + if (res != 0)
2662 + return res;
2663 + p.dic = dest;
2664 + p.dicBufSize = outSize;
2665 +
2666 + LzmaDec_Init(&p);
2667 +
2668 + *srcLen = inSize;
2669 + res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status);
2670 +
2671 + if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT)
2672 + res = SZ_ERROR_INPUT_EOF;
2673 +
2674 + (*destLen) = p.dicPos;
2675 + LzmaDec_FreeProbs(&p, alloc);
2676 + return res;
2677 +}
2678 --- /dev/null
2679 +++ b/jffsX-utils/lzma/LzmaEnc.c
2680 @@ -0,0 +1,2335 @@
2681 +/* LzmaEnc.c -- LZMA Encoder
2682 +2008-04-28
2683 +Copyright (c) 1999-2008 Igor Pavlov
2684 +Read LzmaEnc.h for license options */
2685 +
2686 +#if defined(SHOW_STAT) || defined(SHOW_STAT2)
2687 +#include <stdio.h>
2688 +#endif
2689 +
2690 +#include <string.h>
2691 +
2692 +#include "LzmaEnc.h"
2693 +
2694 +#include "LzFind.h"
2695 +#ifdef COMPRESS_MF_MT
2696 +#include "LzFindMt.h"
2697 +#endif
2698 +
2699 +/* #define SHOW_STAT */
2700 +/* #define SHOW_STAT2 */
2701 +
2702 +#ifdef SHOW_STAT
2703 +static int ttt = 0;
2704 +#endif
2705 +
2706 +#define kBlockSizeMax ((1 << LZMA_NUM_BLOCK_SIZE_BITS) - 1)
2707 +
2708 +#define kBlockSize (9 << 10)
2709 +#define kUnpackBlockSize (1 << 18)
2710 +#define kMatchArraySize (1 << 21)
2711 +#define kMatchRecordMaxSize ((LZMA_MATCH_LEN_MAX * 2 + 3) * LZMA_MATCH_LEN_MAX)
2712 +
2713 +#define kNumMaxDirectBits (31)
2714 +
2715 +#define kNumTopBits 24
2716 +#define kTopValue ((UInt32)1 << kNumTopBits)
2717 +
2718 +#define kNumBitModelTotalBits 11
2719 +#define kBitModelTotal (1 << kNumBitModelTotalBits)
2720 +#define kNumMoveBits 5
2721 +#define kProbInitValue (kBitModelTotal >> 1)
2722 +
2723 +#define kNumMoveReducingBits 4
2724 +#define kNumBitPriceShiftBits 4
2725 +#define kBitPrice (1 << kNumBitPriceShiftBits)
2726 +
2727 +void LzmaEncProps_Init(CLzmaEncProps *p)
2728 +{
2729 + p->level = 5;
2730 + p->dictSize = p->mc = 0;
2731 + p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->numThreads = -1;
2732 + p->writeEndMark = 0;
2733 +}
2734 +
2735 +void LzmaEncProps_Normalize(CLzmaEncProps *p)
2736 +{
2737 + int level = p->level;
2738 + if (level < 0) level = 5;
2739 + p->level = level;
2740 + if (p->dictSize == 0) p->dictSize = (level <= 5 ? (1 << (level * 2 + 14)) : (level == 6 ? (1 << 25) : (1 << 26)));
2741 + if (p->lc < 0) p->lc = 3;
2742 + if (p->lp < 0) p->lp = 0;
2743 + if (p->pb < 0) p->pb = 2;
2744 + if (p->algo < 0) p->algo = (level < 5 ? 0 : 1);
2745 + if (p->fb < 0) p->fb = (level < 7 ? 32 : 64);
2746 + if (p->btMode < 0) p->btMode = (p->algo == 0 ? 0 : 1);
2747 + if (p->numHashBytes < 0) p->numHashBytes = 4;
2748 + if (p->mc == 0) p->mc = (16 + (p->fb >> 1)) >> (p->btMode ? 0 : 1);
2749 + if (p->numThreads < 0) p->numThreads = ((p->btMode && p->algo) ? 2 : 1);
2750 +}
2751 +
2752 +UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2)
2753 +{
2754 + CLzmaEncProps props = *props2;
2755 + LzmaEncProps_Normalize(&props);
2756 + return props.dictSize;
2757 +}
2758 +
2759 +/* #define LZMA_LOG_BSR */
2760 +/* Define it for Intel's CPU */
2761 +
2762 +
2763 +#ifdef LZMA_LOG_BSR
2764 +
2765 +#define kDicLogSizeMaxCompress 30
2766 +
2767 +#define BSR2_RET(pos, res) { unsigned long i; _BitScanReverse(&i, (pos)); res = (i + i) + ((pos >> (i - 1)) & 1); }
2768 +
2769 +UInt32 GetPosSlot1(UInt32 pos)
2770 +{
2771 + UInt32 res;
2772 + BSR2_RET(pos, res);
2773 + return res;
2774 +}
2775 +#define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
2776 +#define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res); }
2777 +
2778 +#else
2779 +
2780 +#define kNumLogBits (9 + (int)sizeof(size_t) / 2)
2781 +#define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7)
2782 +
2783 +static void LzmaEnc_FastPosInit(Byte *g_FastPos)
2784 +{
2785 + int c = 2, slotFast;
2786 + g_FastPos[0] = 0;
2787 + g_FastPos[1] = 1;
2788 +
2789 + for (slotFast = 2; slotFast < kNumLogBits * 2; slotFast++)
2790 + {
2791 + UInt32 k = (1 << ((slotFast >> 1) - 1));
2792 + UInt32 j;
2793 + for (j = 0; j < k; j++, c++)
2794 + g_FastPos[c] = (Byte)slotFast;
2795 + }
2796 +}
2797 +
2798 +#define BSR2_RET(pos, res) { UInt32 i = 6 + ((kNumLogBits - 1) & \
2799 + (0 - (((((UInt32)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \
2800 + res = p->g_FastPos[pos >> i] + (i * 2); }
2801 +/*
2802 +#define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \
2803 + p->g_FastPos[pos >> 6] + 12 : \
2804 + p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; }
2805 +*/
2806 +
2807 +#define GetPosSlot1(pos) p->g_FastPos[pos]
2808 +#define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
2809 +#define GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[pos]; else BSR2_RET(pos, res); }
2810 +
2811 +#endif
2812 +
2813 +
2814 +#define LZMA_NUM_REPS 4
2815 +
2816 +typedef unsigned CState;
2817 +
2818 +typedef struct _COptimal
2819 +{
2820 + UInt32 price;
2821 +
2822 + CState state;
2823 + int prev1IsChar;
2824 + int prev2;
2825 +
2826 + UInt32 posPrev2;
2827 + UInt32 backPrev2;
2828 +
2829 + UInt32 posPrev;
2830 + UInt32 backPrev;
2831 + UInt32 backs[LZMA_NUM_REPS];
2832 +} COptimal;
2833 +
2834 +#define kNumOpts (1 << 12)
2835 +
2836 +#define kNumLenToPosStates 4
2837 +#define kNumPosSlotBits 6
2838 +#define kDicLogSizeMin 0
2839 +#define kDicLogSizeMax 32
2840 +#define kDistTableSizeMax (kDicLogSizeMax * 2)
2841 +
2842 +
2843 +#define kNumAlignBits 4
2844 +#define kAlignTableSize (1 << kNumAlignBits)
2845 +#define kAlignMask (kAlignTableSize - 1)
2846 +
2847 +#define kStartPosModelIndex 4
2848 +#define kEndPosModelIndex 14
2849 +#define kNumPosModels (kEndPosModelIndex - kStartPosModelIndex)
2850 +
2851 +#define kNumFullDistances (1 << (kEndPosModelIndex / 2))
2852 +
2853 +#ifdef _LZMA_PROB32
2854 +#define CLzmaProb UInt32
2855 +#else
2856 +#define CLzmaProb UInt16
2857 +#endif
2858 +
2859 +#define LZMA_PB_MAX 4
2860 +#define LZMA_LC_MAX 8
2861 +#define LZMA_LP_MAX 4
2862 +
2863 +#define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX)
2864 +
2865 +
2866 +#define kLenNumLowBits 3
2867 +#define kLenNumLowSymbols (1 << kLenNumLowBits)
2868 +#define kLenNumMidBits 3
2869 +#define kLenNumMidSymbols (1 << kLenNumMidBits)
2870 +#define kLenNumHighBits 8
2871 +#define kLenNumHighSymbols (1 << kLenNumHighBits)
2872 +
2873 +#define kLenNumSymbolsTotal (kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)
2874 +
2875 +#define LZMA_MATCH_LEN_MIN 2
2876 +#define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1)
2877 +
2878 +#define kNumStates 12
2879 +
2880 +typedef struct
2881 +{
2882 + CLzmaProb choice;
2883 + CLzmaProb choice2;
2884 + CLzmaProb low[LZMA_NUM_PB_STATES_MAX << kLenNumLowBits];
2885 + CLzmaProb mid[LZMA_NUM_PB_STATES_MAX << kLenNumMidBits];
2886 + CLzmaProb high[kLenNumHighSymbols];
2887 +} CLenEnc;
2888 +
2889 +typedef struct
2890 +{
2891 + CLenEnc p;
2892 + UInt32 prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal];
2893 + UInt32 tableSize;
2894 + UInt32 counters[LZMA_NUM_PB_STATES_MAX];
2895 +} CLenPriceEnc;
2896 +
2897 +typedef struct _CRangeEnc
2898 +{
2899 + UInt32 range;
2900 + Byte cache;
2901 + UInt64 low;
2902 + UInt64 cacheSize;
2903 + Byte *buf;
2904 + Byte *bufLim;
2905 + Byte *bufBase;
2906 + ISeqOutStream *outStream;
2907 + UInt64 processed;
2908 + SRes res;
2909 +} CRangeEnc;
2910 +
2911 +typedef struct _CSeqInStreamBuf
2912 +{
2913 + ISeqInStream funcTable;
2914 + const Byte *data;
2915 + SizeT rem;
2916 +} CSeqInStreamBuf;
2917 +
2918 +static SRes MyRead(void *pp, void *data, size_t *size)
2919 +{
2920 + size_t curSize = *size;
2921 + CSeqInStreamBuf *p = (CSeqInStreamBuf *)pp;
2922 + if (p->rem < curSize)
2923 + curSize = p->rem;
2924 + memcpy(data, p->data, curSize);
2925 + p->rem -= curSize;
2926 + p->data += curSize;
2927 + *size = curSize;
2928 + return SZ_OK;
2929 +}
2930 +
2931 +typedef struct
2932 +{
2933 + CLzmaProb *litProbs;
2934 +
2935 + CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];
2936 + CLzmaProb isRep[kNumStates];
2937 + CLzmaProb isRepG0[kNumStates];
2938 + CLzmaProb isRepG1[kNumStates];
2939 + CLzmaProb isRepG2[kNumStates];
2940 + CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];
2941 +
2942 + CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];
2943 + CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex];
2944 + CLzmaProb posAlignEncoder[1 << kNumAlignBits];
2945 +
2946 + CLenPriceEnc lenEnc;
2947 + CLenPriceEnc repLenEnc;
2948 +
2949 + UInt32 reps[LZMA_NUM_REPS];
2950 + UInt32 state;
2951 +} CSaveState;
2952 +
2953 +typedef struct _CLzmaEnc
2954 +{
2955 + IMatchFinder matchFinder;
2956 + void *matchFinderObj;
2957 +
2958 + #ifdef COMPRESS_MF_MT
2959 + Bool mtMode;
2960 + CMatchFinderMt matchFinderMt;
2961 + #endif
2962 +
2963 + CMatchFinder matchFinderBase;
2964 +
2965 + #ifdef COMPRESS_MF_MT
2966 + Byte pad[128];
2967 + #endif
2968 +
2969 + UInt32 optimumEndIndex;
2970 + UInt32 optimumCurrentIndex;
2971 +
2972 + Bool longestMatchWasFound;
2973 + UInt32 longestMatchLength;
2974 + UInt32 numDistancePairs;
2975 +
2976 + COptimal opt[kNumOpts];
2977 +
2978 + #ifndef LZMA_LOG_BSR
2979 + Byte g_FastPos[1 << kNumLogBits];
2980 + #endif
2981 +
2982 + UInt32 ProbPrices[kBitModelTotal >> kNumMoveReducingBits];
2983 + UInt32 matchDistances[LZMA_MATCH_LEN_MAX * 2 + 2 + 1];
2984 + UInt32 numFastBytes;
2985 + UInt32 additionalOffset;
2986 + UInt32 reps[LZMA_NUM_REPS];
2987 + UInt32 state;
2988 +
2989 + UInt32 posSlotPrices[kNumLenToPosStates][kDistTableSizeMax];
2990 + UInt32 distancesPrices[kNumLenToPosStates][kNumFullDistances];
2991 + UInt32 alignPrices[kAlignTableSize];
2992 + UInt32 alignPriceCount;
2993 +
2994 + UInt32 distTableSize;
2995 +
2996 + unsigned lc, lp, pb;
2997 + unsigned lpMask, pbMask;
2998 +
2999 + CLzmaProb *litProbs;
3000 +
3001 + CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];
3002 + CLzmaProb isRep[kNumStates];
3003 + CLzmaProb isRepG0[kNumStates];
3004 + CLzmaProb isRepG1[kNumStates];
3005 + CLzmaProb isRepG2[kNumStates];
3006 + CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];
3007 +
3008 + CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];
3009 + CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex];
3010 + CLzmaProb posAlignEncoder[1 << kNumAlignBits];
3011 +
3012 + CLenPriceEnc lenEnc;
3013 + CLenPriceEnc repLenEnc;
3014 +
3015 + unsigned lclp;
3016 +
3017 + Bool fastMode;
3018 +
3019 + CRangeEnc rc;
3020 +
3021 + Bool writeEndMark;
3022 + UInt64 nowPos64;
3023 + UInt32 matchPriceCount;
3024 + Bool finished;
3025 + Bool multiThread;
3026 +
3027 + SRes result;
3028 + UInt32 dictSize;
3029 + UInt32 matchFinderCycles;
3030 +
3031 + ISeqInStream *inStream;
3032 + CSeqInStreamBuf seqBufInStream;
3033 +
3034 + CSaveState saveState;
3035 +} CLzmaEnc;
3036 +
3037 +static void LzmaEnc_SaveState(CLzmaEncHandle pp)
3038 +{
3039 + CLzmaEnc *p = (CLzmaEnc *)pp;
3040 + CSaveState *dest = &p->saveState;
3041 + int i;
3042 + dest->lenEnc = p->lenEnc;
3043 + dest->repLenEnc = p->repLenEnc;
3044 + dest->state = p->state;
3045 +
3046 + for (i = 0; i < kNumStates; i++)
3047 + {
3048 + memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));
3049 + memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));
3050 + }
3051 + for (i = 0; i < kNumLenToPosStates; i++)
3052 + memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i]));
3053 + memcpy(dest->isRep, p->isRep, sizeof(p->isRep));
3054 + memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0));
3055 + memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1));
3056 + memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2));
3057 + memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders));
3058 + memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder));
3059 + memcpy(dest->reps, p->reps, sizeof(p->reps));
3060 + memcpy(dest->litProbs, p->litProbs, (0x300 << p->lclp) * sizeof(CLzmaProb));
3061 +}
3062 +
3063 +static void LzmaEnc_RestoreState(CLzmaEncHandle pp)
3064 +{
3065 + CLzmaEnc *dest = (CLzmaEnc *)pp;
3066 + const CSaveState *p = &dest->saveState;
3067 + int i;
3068 + dest->lenEnc = p->lenEnc;
3069 + dest->repLenEnc = p->repLenEnc;
3070 + dest->state = p->state;
3071 +
3072 + for (i = 0; i < kNumStates; i++)
3073 + {
3074 + memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));
3075 + memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));
3076 + }
3077 + for (i = 0; i < kNumLenToPosStates; i++)
3078 + memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i]));
3079 + memcpy(dest->isRep, p->isRep, sizeof(p->isRep));
3080 + memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0));
3081 + memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1));
3082 + memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2));
3083 + memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders));
3084 + memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder));
3085 + memcpy(dest->reps, p->reps, sizeof(p->reps));
3086 + memcpy(dest->litProbs, p->litProbs, (0x300 << dest->lclp) * sizeof(CLzmaProb));
3087 +}
3088 +
3089 +SRes LzmaEnc_SetProps(CLzmaEncHandle pp, const CLzmaEncProps *props2)
3090 +{
3091 + CLzmaEnc *p = (CLzmaEnc *)pp;
3092 + CLzmaEncProps props = *props2;
3093 + LzmaEncProps_Normalize(&props);
3094 +
3095 + if (props.lc > LZMA_LC_MAX || props.lp > LZMA_LP_MAX || props.pb > LZMA_PB_MAX ||
3096 + props.dictSize > (1 << kDicLogSizeMaxCompress) || props.dictSize > (1 << 30))
3097 + return SZ_ERROR_PARAM;
3098 + p->dictSize = props.dictSize;
3099 + p->matchFinderCycles = props.mc;
3100 + {
3101 + unsigned fb = props.fb;
3102 + if (fb < 5)
3103 + fb = 5;
3104 + if (fb > LZMA_MATCH_LEN_MAX)
3105 + fb = LZMA_MATCH_LEN_MAX;
3106 + p->numFastBytes = fb;
3107 + }
3108 + p->lc = props.lc;
3109 + p->lp = props.lp;
3110 + p->pb = props.pb;
3111 + p->fastMode = (props.algo == 0);
3112 + p->matchFinderBase.btMode = props.btMode;
3113 + {
3114 + UInt32 numHashBytes = 4;
3115 + if (props.btMode)
3116 + {
3117 + if (props.numHashBytes < 2)
3118 + numHashBytes = 2;
3119 + else if (props.numHashBytes < 4)
3120 + numHashBytes = props.numHashBytes;
3121 + }
3122 + p->matchFinderBase.numHashBytes = numHashBytes;
3123 + }
3124 +
3125 + p->matchFinderBase.cutValue = props.mc;
3126 +
3127 + p->writeEndMark = props.writeEndMark;
3128 +
3129 + #ifdef COMPRESS_MF_MT
3130 + /*
3131 + if (newMultiThread != _multiThread)
3132 + {
3133 + ReleaseMatchFinder();
3134 + _multiThread = newMultiThread;
3135 + }
3136 + */
3137 + p->multiThread = (props.numThreads > 1);
3138 + #endif
3139 +
3140 + return SZ_OK;
3141 +}
3142 +
3143 +static const int kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5};
3144 +static const int kMatchNextStates[kNumStates] = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10};
3145 +static const int kRepNextStates[kNumStates] = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11};
3146 +static const int kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11};
3147 +
3148 +/*
3149 + void UpdateChar() { Index = kLiteralNextStates[Index]; }
3150 + void UpdateMatch() { Index = kMatchNextStates[Index]; }
3151 + void UpdateRep() { Index = kRepNextStates[Index]; }
3152 + void UpdateShortRep() { Index = kShortRepNextStates[Index]; }
3153 +*/
3154 +
3155 +#define IsCharState(s) ((s) < 7)
3156 +
3157 +
3158 +#define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1)
3159 +
3160 +#define kInfinityPrice (1 << 30)
3161 +
3162 +static void RangeEnc_Construct(CRangeEnc *p)
3163 +{
3164 + p->outStream = 0;
3165 + p->bufBase = 0;
3166 +}
3167 +
3168 +#define RangeEnc_GetProcessed(p) ((p)->processed + ((p)->buf - (p)->bufBase) + (p)->cacheSize)
3169 +
3170 +#define RC_BUF_SIZE (1 << 16)
3171 +static int RangeEnc_Alloc(CRangeEnc *p, ISzAlloc *alloc)
3172 +{
3173 + if (p->bufBase == 0)
3174 + {
3175 + p->bufBase = (Byte *)alloc->Alloc(alloc, RC_BUF_SIZE);
3176 + if (p->bufBase == 0)
3177 + return 0;
3178 + p->bufLim = p->bufBase + RC_BUF_SIZE;
3179 + }
3180 + return 1;
3181 +}
3182 +
3183 +static void RangeEnc_Free(CRangeEnc *p, ISzAlloc *alloc)
3184 +{
3185 + alloc->Free(alloc, p->bufBase);
3186 + p->bufBase = 0;
3187 +}
3188 +
3189 +static void RangeEnc_Init(CRangeEnc *p)
3190 +{
3191 + /* Stream.Init(); */
3192 + p->low = 0;
3193 + p->range = 0xFFFFFFFF;
3194 + p->cacheSize = 1;
3195 + p->cache = 0;
3196 +
3197 + p->buf = p->bufBase;
3198 +
3199 + p->processed = 0;
3200 + p->res = SZ_OK;
3201 +}
3202 +
3203 +static void RangeEnc_FlushStream(CRangeEnc *p)
3204 +{
3205 + size_t num;
3206 + if (p->res != SZ_OK)
3207 + return;
3208 + num = p->buf - p->bufBase;
3209 + if (num != p->outStream->Write(p->outStream, p->bufBase, num))
3210 + p->res = SZ_ERROR_WRITE;
3211 + p->processed += num;
3212 + p->buf = p->bufBase;
3213 +}
3214 +
3215 +static void MY_FAST_CALL RangeEnc_ShiftLow(CRangeEnc *p)
3216 +{
3217 + if ((UInt32)p->low < (UInt32)0xFF000000 || (int)(p->low >> 32) != 0)
3218 + {
3219 + Byte temp = p->cache;
3220 + do
3221 + {
3222 + Byte *buf = p->buf;
3223 + *buf++ = (Byte)(temp + (Byte)(p->low >> 32));
3224 + p->buf = buf;
3225 + if (buf == p->bufLim)
3226 + RangeEnc_FlushStream(p);
3227 + temp = 0xFF;
3228 + }
3229 + while (--p->cacheSize != 0);
3230 + p->cache = (Byte)((UInt32)p->low >> 24);
3231 + }
3232 + p->cacheSize++;
3233 + p->low = (UInt32)p->low << 8;
3234 +}
3235 +
3236 +static void RangeEnc_FlushData(CRangeEnc *p)
3237 +{
3238 + int i;
3239 + for (i = 0; i < 5; i++)
3240 + RangeEnc_ShiftLow(p);
3241 +}
3242 +
3243 +static void RangeEnc_EncodeDirectBits(CRangeEnc *p, UInt32 value, int numBits)
3244 +{
3245 + do
3246 + {
3247 + p->range >>= 1;
3248 + p->low += p->range & (0 - ((value >> --numBits) & 1));
3249 + if (p->range < kTopValue)
3250 + {
3251 + p->range <<= 8;
3252 + RangeEnc_ShiftLow(p);
3253 + }
3254 + }
3255 + while (numBits != 0);
3256 +}
3257 +
3258 +static void RangeEnc_EncodeBit(CRangeEnc *p, CLzmaProb *prob, UInt32 symbol)
3259 +{
3260 + UInt32 ttt = *prob;
3261 + UInt32 newBound = (p->range >> kNumBitModelTotalBits) * ttt;
3262 + if (symbol == 0)
3263 + {
3264 + p->range = newBound;
3265 + ttt += (kBitModelTotal - ttt) >> kNumMoveBits;
3266 + }
3267 + else
3268 + {
3269 + p->low += newBound;
3270 + p->range -= newBound;
3271 + ttt -= ttt >> kNumMoveBits;
3272 + }
3273 + *prob = (CLzmaProb)ttt;
3274 + if (p->range < kTopValue)
3275 + {
3276 + p->range <<= 8;
3277 + RangeEnc_ShiftLow(p);
3278 + }
3279 +}
3280 +
3281 +static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol)
3282 +{
3283 + symbol |= 0x100;
3284 + do
3285 + {
3286 + RangeEnc_EncodeBit(p, probs + (symbol >> 8), (symbol >> 7) & 1);
3287 + symbol <<= 1;
3288 + }
3289 + while (symbol < 0x10000);
3290 +}
3291 +
3292 +static void LitEnc_EncodeMatched(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol, UInt32 matchByte)
3293 +{
3294 + UInt32 offs = 0x100;
3295 + symbol |= 0x100;
3296 + do
3297 + {
3298 + matchByte <<= 1;
3299 + RangeEnc_EncodeBit(p, probs + (offs + (matchByte & offs) + (symbol >> 8)), (symbol >> 7) & 1);
3300 + symbol <<= 1;
3301 + offs &= ~(matchByte ^ symbol);
3302 + }
3303 + while (symbol < 0x10000);
3304 +}
3305 +
3306 +static void LzmaEnc_InitPriceTables(UInt32 *ProbPrices)
3307 +{
3308 + UInt32 i;
3309 + for (i = (1 << kNumMoveReducingBits) / 2; i < kBitModelTotal; i += (1 << kNumMoveReducingBits))
3310 + {
3311 + const int kCyclesBits = kNumBitPriceShiftBits;
3312 + UInt32 w = i;
3313 + UInt32 bitCount = 0;
3314 + int j;
3315 + for (j = 0; j < kCyclesBits; j++)
3316 + {
3317 + w = w * w;
3318 + bitCount <<= 1;
3319 + while (w >= ((UInt32)1 << 16))
3320 + {
3321 + w >>= 1;
3322 + bitCount++;
3323 + }
3324 + }
3325 + ProbPrices[i >> kNumMoveReducingBits] = ((kNumBitModelTotalBits << kCyclesBits) - 15 - bitCount);
3326 + }
3327 +}
3328 +
3329 +
3330 +#define GET_PRICE(prob, symbol) \
3331 + p->ProbPrices[((prob) ^ (((-(int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];
3332 +
3333 +#define GET_PRICEa(prob, symbol) \
3334 + ProbPrices[((prob) ^ ((-((int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];
3335 +
3336 +#define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits]
3337 +#define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
3338 +
3339 +#define GET_PRICE_0a(prob) ProbPrices[(prob) >> kNumMoveReducingBits]
3340 +#define GET_PRICE_1a(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
3341 +
3342 +static UInt32 LitEnc_GetPrice(const CLzmaProb *probs, UInt32 symbol, UInt32 *ProbPrices)
3343 +{
3344 + UInt32 price = 0;
3345 + symbol |= 0x100;
3346 + do
3347 + {
3348 + price += GET_PRICEa(probs[symbol >> 8], (symbol >> 7) & 1);
3349 + symbol <<= 1;
3350 + }
3351 + while (symbol < 0x10000);
3352 + return price;
3353 +};
3354 +
3355 +static UInt32 LitEnc_GetPriceMatched(const CLzmaProb *probs, UInt32 symbol, UInt32 matchByte, UInt32 *ProbPrices)
3356 +{
3357 + UInt32 price = 0;
3358 + UInt32 offs = 0x100;
3359 + symbol |= 0x100;
3360 + do
3361 + {
3362 + matchByte <<= 1;
3363 + price += GET_PRICEa(probs[offs + (matchByte & offs) + (symbol >> 8)], (symbol >> 7) & 1);
3364 + symbol <<= 1;
3365 + offs &= ~(matchByte ^ symbol);
3366 + }
3367 + while (symbol < 0x10000);
3368 + return price;
3369 +};
3370 +
3371 +
3372 +static void RcTree_Encode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)
3373 +{
3374 + UInt32 m = 1;
3375 + int i;
3376 + for (i = numBitLevels; i != 0 ;)
3377 + {
3378 + UInt32 bit;
3379 + i--;
3380 + bit = (symbol >> i) & 1;
3381 + RangeEnc_EncodeBit(rc, probs + m, bit);
3382 + m = (m << 1) | bit;
3383 + }
3384 +};
3385 +
3386 +static void RcTree_ReverseEncode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)
3387 +{
3388 + UInt32 m = 1;
3389 + int i;
3390 + for (i = 0; i < numBitLevels; i++)
3391 + {
3392 + UInt32 bit = symbol & 1;
3393 + RangeEnc_EncodeBit(rc, probs + m, bit);
3394 + m = (m << 1) | bit;
3395 + symbol >>= 1;
3396 + }
3397 +}
3398 +
3399 +static UInt32 RcTree_GetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, UInt32 *ProbPrices)
3400 +{
3401 + UInt32 price = 0;
3402 + symbol |= (1 << numBitLevels);
3403 + while (symbol != 1)
3404 + {
3405 + price += GET_PRICEa(probs[symbol >> 1], symbol & 1);
3406 + symbol >>= 1;
3407 + }
3408 + return price;
3409 +}
3410 +
3411 +static UInt32 RcTree_ReverseGetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, UInt32 *ProbPrices)
3412 +{
3413 + UInt32 price = 0;
3414 + UInt32 m = 1;
3415 + int i;
3416 + for (i = numBitLevels; i != 0; i--)
3417 + {
3418 + UInt32 bit = symbol & 1;
3419 + symbol >>= 1;
3420 + price += GET_PRICEa(probs[m], bit);
3421 + m = (m << 1) | bit;
3422 + }
3423 + return price;
3424 +}
3425 +
3426 +
3427 +static void LenEnc_Init(CLenEnc *p)
3428 +{
3429 + unsigned i;
3430 + p->choice = p->choice2 = kProbInitValue;
3431 + for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumLowBits); i++)
3432 + p->low[i] = kProbInitValue;
3433 + for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumMidBits); i++)
3434 + p->mid[i] = kProbInitValue;
3435 + for (i = 0; i < kLenNumHighSymbols; i++)
3436 + p->high[i] = kProbInitValue;
3437 +}
3438 +
3439 +static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState)
3440 +{
3441 + if (symbol < kLenNumLowSymbols)
3442 + {
3443 + RangeEnc_EncodeBit(rc, &p->choice, 0);
3444 + RcTree_Encode(rc, p->low + (posState << kLenNumLowBits), kLenNumLowBits, symbol);
3445 + }
3446 + else
3447 + {
3448 + RangeEnc_EncodeBit(rc, &p->choice, 1);
3449 + if (symbol < kLenNumLowSymbols + kLenNumMidSymbols)
3450 + {
3451 + RangeEnc_EncodeBit(rc, &p->choice2, 0);
3452 + RcTree_Encode(rc, p->mid + (posState << kLenNumMidBits), kLenNumMidBits, symbol - kLenNumLowSymbols);
3453 + }
3454 + else
3455 + {
3456 + RangeEnc_EncodeBit(rc, &p->choice2, 1);
3457 + RcTree_Encode(rc, p->high, kLenNumHighBits, symbol - kLenNumLowSymbols - kLenNumMidSymbols);
3458 + }
3459 + }
3460 +}
3461 +
3462 +static void LenEnc_SetPrices(CLenEnc *p, UInt32 posState, UInt32 numSymbols, UInt32 *prices, UInt32 *ProbPrices)
3463 +{
3464 + UInt32 a0 = GET_PRICE_0a(p->choice);
3465 + UInt32 a1 = GET_PRICE_1a(p->choice);
3466 + UInt32 b0 = a1 + GET_PRICE_0a(p->choice2);
3467 + UInt32 b1 = a1 + GET_PRICE_1a(p->choice2);
3468 + UInt32 i = 0;
3469 + for (i = 0; i < kLenNumLowSymbols; i++)
3470 + {
3471 + if (i >= numSymbols)
3472 + return;
3473 + prices[i] = a0 + RcTree_GetPrice(p->low + (posState << kLenNumLowBits), kLenNumLowBits, i, ProbPrices);
3474 + }
3475 + for (; i < kLenNumLowSymbols + kLenNumMidSymbols; i++)
3476 + {
3477 + if (i >= numSymbols)
3478 + return;
3479 + prices[i] = b0 + RcTree_GetPrice(p->mid + (posState << kLenNumMidBits), kLenNumMidBits, i - kLenNumLowSymbols, ProbPrices);
3480 + }
3481 + for (; i < numSymbols; i++)
3482 + prices[i] = b1 + RcTree_GetPrice(p->high, kLenNumHighBits, i - kLenNumLowSymbols - kLenNumMidSymbols, ProbPrices);
3483 +}
3484 +
3485 +static void MY_FAST_CALL LenPriceEnc_UpdateTable(CLenPriceEnc *p, UInt32 posState, UInt32 *ProbPrices)
3486 +{
3487 + LenEnc_SetPrices(&p->p, posState, p->tableSize, p->prices[posState], ProbPrices);
3488 + p->counters[posState] = p->tableSize;
3489 +}
3490 +
3491 +static void LenPriceEnc_UpdateTables(CLenPriceEnc *p, UInt32 numPosStates, UInt32 *ProbPrices)
3492 +{
3493 + UInt32 posState;
3494 + for (posState = 0; posState < numPosStates; posState++)
3495 + LenPriceEnc_UpdateTable(p, posState, ProbPrices);
3496 +}
3497 +
3498 +static void LenEnc_Encode2(CLenPriceEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState, Bool updatePrice, UInt32 *ProbPrices)
3499 +{
3500 + LenEnc_Encode(&p->p, rc, symbol, posState);
3501 + if (updatePrice)
3502 + if (--p->counters[posState] == 0)
3503 + LenPriceEnc_UpdateTable(p, posState, ProbPrices);
3504 +}
3505 +
3506 +
3507 +
3508 +
3509 +static void MovePos(CLzmaEnc *p, UInt32 num)
3510 +{
3511 + #ifdef SHOW_STAT
3512 + ttt += num;
3513 + printf("\n MovePos %d", num);
3514 + #endif
3515 + if (num != 0)
3516 + {
3517 + p->additionalOffset += num;
3518 + p->matchFinder.Skip(p->matchFinderObj, num);
3519 + }
3520 +}
3521 +
3522 +static UInt32 ReadMatchDistances(CLzmaEnc *p, UInt32 *numDistancePairsRes)
3523 +{
3524 + UInt32 lenRes = 0, numDistancePairs;
3525 + numDistancePairs = p->matchFinder.GetMatches(p->matchFinderObj, p->matchDistances);
3526 + #ifdef SHOW_STAT
3527 + printf("\n i = %d numPairs = %d ", ttt, numDistancePairs / 2);
3528 + if (ttt >= 61994)
3529 + ttt = ttt;
3530 +
3531 + ttt++;
3532 + {
3533 + UInt32 i;
3534 + for (i = 0; i < numDistancePairs; i += 2)
3535 + printf("%2d %6d | ", p->matchDistances[i], p->matchDistances[i + 1]);
3536 + }
3537 + #endif
3538 + if (numDistancePairs > 0)
3539 + {
3540 + lenRes = p->matchDistances[numDistancePairs - 2];
3541 + if (lenRes == p->numFastBytes)
3542 + {
3543 + UInt32 numAvail = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) + 1;
3544 + const Byte *pby = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
3545 + UInt32 distance = p->matchDistances[numDistancePairs - 1] + 1;
3546 + if (numAvail > LZMA_MATCH_LEN_MAX)
3547 + numAvail = LZMA_MATCH_LEN_MAX;
3548 +
3549 + {
3550 + const Byte *pby2 = pby - distance;
3551 + for (; lenRes < numAvail && pby[lenRes] == pby2[lenRes]; lenRes++);
3552 + }
3553 + }
3554 + }
3555 + p->additionalOffset++;
3556 + *numDistancePairsRes = numDistancePairs;
3557 + return lenRes;
3558 +}
3559 +
3560 +
3561 +#define MakeAsChar(p) (p)->backPrev = (UInt32)(-1); (p)->prev1IsChar = False;
3562 +#define MakeAsShortRep(p) (p)->backPrev = 0; (p)->prev1IsChar = False;
3563 +#define IsShortRep(p) ((p)->backPrev == 0)
3564 +
3565 +static UInt32 GetRepLen1Price(CLzmaEnc *p, UInt32 state, UInt32 posState)
3566 +{
3567 + return
3568 + GET_PRICE_0(p->isRepG0[state]) +
3569 + GET_PRICE_0(p->isRep0Long[state][posState]);
3570 +}
3571 +
3572 +static UInt32 GetPureRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 state, UInt32 posState)
3573 +{
3574 + UInt32 price;
3575 + if (repIndex == 0)
3576 + {
3577 + price = GET_PRICE_0(p->isRepG0[state]);
3578 + price += GET_PRICE_1(p->isRep0Long[state][posState]);
3579 + }
3580 + else
3581 + {
3582 + price = GET_PRICE_1(p->isRepG0[state]);
3583 + if (repIndex == 1)
3584 + price += GET_PRICE_0(p->isRepG1[state]);
3585 + else
3586 + {
3587 + price += GET_PRICE_1(p->isRepG1[state]);
3588 + price += GET_PRICE(p->isRepG2[state], repIndex - 2);
3589 + }
3590 + }
3591 + return price;
3592 +}
3593 +
3594 +static UInt32 GetRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 len, UInt32 state, UInt32 posState)
3595 +{
3596 + return p->repLenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN] +
3597 + GetPureRepPrice(p, repIndex, state, posState);
3598 +}
3599 +
3600 +static UInt32 Backward(CLzmaEnc *p, UInt32 *backRes, UInt32 cur)
3601 +{
3602 + UInt32 posMem = p->opt[cur].posPrev;
3603 + UInt32 backMem = p->opt[cur].backPrev;
3604 + p->optimumEndIndex = cur;
3605 + do
3606 + {
3607 + if (p->opt[cur].prev1IsChar)
3608 + {
3609 + MakeAsChar(&p->opt[posMem])
3610 + p->opt[posMem].posPrev = posMem - 1;
3611 + if (p->opt[cur].prev2)
3612 + {
3613 + p->opt[posMem - 1].prev1IsChar = False;
3614 + p->opt[posMem - 1].posPrev = p->opt[cur].posPrev2;
3615 + p->opt[posMem - 1].backPrev = p->opt[cur].backPrev2;
3616 + }
3617 + }
3618 + {
3619 + UInt32 posPrev = posMem;
3620 + UInt32 backCur = backMem;
3621 +
3622 + backMem = p->opt[posPrev].backPrev;
3623 + posMem = p->opt[posPrev].posPrev;
3624 +
3625 + p->opt[posPrev].backPrev = backCur;
3626 + p->opt[posPrev].posPrev = cur;
3627 + cur = posPrev;
3628 + }
3629 + }
3630 + while (cur != 0);
3631 + *backRes = p->opt[0].backPrev;
3632 + p->optimumCurrentIndex = p->opt[0].posPrev;
3633 + return p->optimumCurrentIndex;
3634 +}
3635 +
3636 +#define LIT_PROBS(pos, prevByte) (p->litProbs + ((((pos) & p->lpMask) << p->lc) + ((prevByte) >> (8 - p->lc))) * 0x300)
3637 +
3638 +static UInt32 GetOptimum(CLzmaEnc *p, UInt32 position, UInt32 *backRes)
3639 +{
3640 + UInt32 numAvailableBytes, lenMain, numDistancePairs;
3641 + const Byte *data;
3642 + UInt32 reps[LZMA_NUM_REPS];
3643 + UInt32 repLens[LZMA_NUM_REPS];
3644 + UInt32 repMaxIndex, i;
3645 + UInt32 *matchDistances;
3646 + Byte currentByte, matchByte;
3647 + UInt32 posState;
3648 + UInt32 matchPrice, repMatchPrice;
3649 + UInt32 lenEnd;
3650 + UInt32 len;
3651 + UInt32 normalMatchPrice;
3652 + UInt32 cur;
3653 + if (p->optimumEndIndex != p->optimumCurrentIndex)
3654 + {
3655 + const COptimal *opt = &p->opt[p->optimumCurrentIndex];
3656 + UInt32 lenRes = opt->posPrev - p->optimumCurrentIndex;
3657 + *backRes = opt->backPrev;
3658 + p->optimumCurrentIndex = opt->posPrev;
3659 + return lenRes;
3660 + }
3661 + p->optimumCurrentIndex = p->optimumEndIndex = 0;
3662 +
3663 + numAvailableBytes = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
3664 +
3665 + if (!p->longestMatchWasFound)
3666 + {
3667 + lenMain = ReadMatchDistances(p, &numDistancePairs);
3668 + }
3669 + else
3670 + {
3671 + lenMain = p->longestMatchLength;
3672 + numDistancePairs = p->numDistancePairs;
3673 + p->longestMatchWasFound = False;
3674 + }
3675 +
3676 + data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
3677 + if (numAvailableBytes < 2)
3678 + {
3679 + *backRes = (UInt32)(-1);
3680 + return 1;
3681 + }
3682 + if (numAvailableBytes > LZMA_MATCH_LEN_MAX)
3683 + numAvailableBytes = LZMA_MATCH_LEN_MAX;
3684 +
3685 + repMaxIndex = 0;
3686 + for (i = 0; i < LZMA_NUM_REPS; i++)
3687 + {
3688 + UInt32 lenTest;
3689 + const Byte *data2;
3690 + reps[i] = p->reps[i];
3691 + data2 = data - (reps[i] + 1);
3692 + if (data[0] != data2[0] || data[1] != data2[1])
3693 + {
3694 + repLens[i] = 0;
3695 + continue;
3696 + }
3697 + for (lenTest = 2; lenTest < numAvailableBytes && data[lenTest] == data2[lenTest]; lenTest++);
3698 + repLens[i] = lenTest;
3699 + if (lenTest > repLens[repMaxIndex])
3700 + repMaxIndex = i;
3701 + }
3702 + if (repLens[repMaxIndex] >= p->numFastBytes)
3703 + {
3704 + UInt32 lenRes;
3705 + *backRes = repMaxIndex;
3706 + lenRes = repLens[repMaxIndex];
3707 + MovePos(p, lenRes - 1);
3708 + return lenRes;
3709 + }
3710 +
3711 + matchDistances = p->matchDistances;
3712 + if (lenMain >= p->numFastBytes)
3713 + {
3714 + *backRes = matchDistances[numDistancePairs - 1] + LZMA_NUM_REPS;
3715 + MovePos(p, lenMain - 1);
3716 + return lenMain;
3717 + }
3718 + currentByte = *data;
3719 + matchByte = *(data - (reps[0] + 1));
3720 +
3721 + if (lenMain < 2 && currentByte != matchByte && repLens[repMaxIndex] < 2)
3722 + {
3723 + *backRes = (UInt32)-1;
3724 + return 1;
3725 + }
3726 +
3727 + p->opt[0].state = (CState)p->state;
3728 +
3729 + posState = (position & p->pbMask);
3730 +
3731 + {
3732 + const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));
3733 + p->opt[1].price = GET_PRICE_0(p->isMatch[p->state][posState]) +
3734 + (!IsCharState(p->state) ?
3735 + LitEnc_GetPriceMatched(probs, currentByte, matchByte, p->ProbPrices) :
3736 + LitEnc_GetPrice(probs, currentByte, p->ProbPrices));
3737 + }
3738 +
3739 + MakeAsChar(&p->opt[1]);
3740 +
3741 + matchPrice = GET_PRICE_1(p->isMatch[p->state][posState]);
3742 + repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[p->state]);
3743 +
3744 + if (matchByte == currentByte)
3745 + {
3746 + UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, p->state, posState);
3747 + if (shortRepPrice < p->opt[1].price)
3748 + {
3749 + p->opt[1].price = shortRepPrice;
3750 + MakeAsShortRep(&p->opt[1]);
3751 + }
3752 + }
3753 + lenEnd = ((lenMain >= repLens[repMaxIndex]) ? lenMain : repLens[repMaxIndex]);
3754 +
3755 + if (lenEnd < 2)
3756 + {
3757 + *backRes = p->opt[1].backPrev;
3758 + return 1;
3759 + }
3760 +
3761 + p->opt[1].posPrev = 0;
3762 + for (i = 0; i < LZMA_NUM_REPS; i++)
3763 + p->opt[0].backs[i] = reps[i];
3764 +
3765 + len = lenEnd;
3766 + do
3767 + p->opt[len--].price = kInfinityPrice;
3768 + while (len >= 2);
3769 +
3770 + for (i = 0; i < LZMA_NUM_REPS; i++)
3771 + {
3772 + UInt32 repLen = repLens[i];
3773 + UInt32 price;
3774 + if (repLen < 2)
3775 + continue;
3776 + price = repMatchPrice + GetPureRepPrice(p, i, p->state, posState);
3777 + do
3778 + {
3779 + UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][repLen - 2];
3780 + COptimal *opt = &p->opt[repLen];
3781 + if (curAndLenPrice < opt->price)
3782 + {
3783 + opt->price = curAndLenPrice;
3784 + opt->posPrev = 0;
3785 + opt->backPrev = i;
3786 + opt->prev1IsChar = False;
3787 + }
3788 + }
3789 + while (--repLen >= 2);
3790 + }
3791 +
3792 + normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[p->state]);
3793 +
3794 + len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2);
3795 + if (len <= lenMain)
3796 + {
3797 + UInt32 offs = 0;