target/linux/generic/pending-4.9/530-jffs2_make_lzma_available.patch

   1 From: Alexandros C. Couloumbis <alex@ozo.com>
   2 Subject: fs: add jffs2/lzma support (not activated by default yet)
   3
   4 lede-commit: c2c88d315fa0e881f8b19da07b62859b915b11b2
   5 Signed-off-by: Alexandros C. Couloumbis <alex@ozo.com>
   6 ---
   7  fs/jffs2/Kconfig             |    9 +
   8  fs/jffs2/Makefile            |    3 +
   9  fs/jffs2/compr.c             |    6 +
  10  fs/jffs2/compr.h             |   10 +-
  11  fs/jffs2/compr_lzma.c        |  128 +++
  12  fs/jffs2/super.c             |   33 +-
  13  include/linux/lzma.h         |   62 ++
  14  include/linux/lzma/LzFind.h  |  115 +++
  15  include/linux/lzma/LzHash.h  |   54 +
  16  include/linux/lzma/LzmaDec.h |  231 +++++
  17  include/linux/lzma/LzmaEnc.h |   80 ++
  18  include/linux/lzma/Types.h   |  226 +++++
  19  include/uapi/linux/jffs2.h   |    1 +
  20  lib/Kconfig                  |    6 +
  21  lib/Makefile                 |   12 +
  22  lib/lzma/LzFind.c            |  761 ++++++++++++++
  23  lib/lzma/LzmaDec.c           |  999 +++++++++++++++++++
  24  lib/lzma/LzmaEnc.c           | 2271 ++++++++++++++++++++++++++++++++++++++++++
  25  lib/lzma/Makefile            |    7 +
  26  19 files changed, 5008 insertions(+), 6 deletions(-)
  27  create mode 100644 fs/jffs2/compr_lzma.c
  28  create mode 100644 include/linux/lzma.h
  29  create mode 100644 include/linux/lzma/LzFind.h
  30  create mode 100644 include/linux/lzma/LzHash.h
  31  create mode 100644 include/linux/lzma/LzmaDec.h
  32  create mode 100644 include/linux/lzma/LzmaEnc.h
  33  create mode 100644 include/linux/lzma/Types.h
  34  create mode 100644 lib/lzma/LzFind.c
  35  create mode 100644 lib/lzma/LzmaDec.c
  36  create mode 100644 lib/lzma/LzmaEnc.c
  37  create mode 100644 lib/lzma/Makefile
  38
  39 diff --git a/fs/jffs2/Kconfig b/fs/jffs2/Kconfig
  40 index d8bb6c411e96..74bf4b162e36 100644
  41 --- a/fs/jffs2/Kconfig
  42 +++ b/fs/jffs2/Kconfig
  43 @@ -139,6 +139,15 @@ config JFFS2_LZO
  44           This feature was added in July, 2007. Say 'N' if you need
  45           compatibility with older bootloaders or kernels.
  46
  47 +config JFFS2_LZMA
  48 +       bool "JFFS2 LZMA compression support" if JFFS2_COMPRESSION_OPTIONS
  49 +       select LZMA_COMPRESS
  50 +       select LZMA_DECOMPRESS
  51 +       depends on JFFS2_FS
  52 +       default n
  53 +       help
  54 +         JFFS2 wrapper to the LZMA C SDK
  55 +
  56  config JFFS2_RTIME
  57         bool "JFFS2 RTIME compression support" if JFFS2_COMPRESSION_OPTIONS
  58         depends on JFFS2_FS
  59 diff --git a/fs/jffs2/Makefile b/fs/jffs2/Makefile
  60 index 60e5d49ca03e..23ba6efd1f3f 100644
  61 --- a/fs/jffs2/Makefile
  62 +++ b/fs/jffs2/Makefile
  63 @@ -18,4 +18,7 @@ jffs2-$(CONFIG_JFFS2_RUBIN)   += compr_rubin.o
  64  jffs2-$(CONFIG_JFFS2_RTIME)    += compr_rtime.o
  65  jffs2-$(CONFIG_JFFS2_ZLIB)     += compr_zlib.o
  66  jffs2-$(CONFIG_JFFS2_LZO)      += compr_lzo.o
  67 +jffs2-$(CONFIG_JFFS2_LZMA)      += compr_lzma.o
  68  jffs2-$(CONFIG_JFFS2_SUMMARY)   += summary.o
  69 +
  70 +CFLAGS_compr_lzma.o += -Iinclude/linux -Ilib/lzma
  71 diff --git a/fs/jffs2/compr.c b/fs/jffs2/compr.c
  72 index 4849a4c9a0e2..6ec806abb7b9 100644
  73 --- a/fs/jffs2/compr.c
  74 +++ b/fs/jffs2/compr.c
  75 @@ -378,6 +378,9 @@ int __init jffs2_compressors_init(void)
  76  #ifdef CONFIG_JFFS2_LZO
  77         jffs2_lzo_init();
  78  #endif
  79 +#ifdef CONFIG_JFFS2_LZMA
  80 +        jffs2_lzma_init();
  81 +#endif
  82  /* Setting default compression mode */
  83  #ifdef CONFIG_JFFS2_CMODE_NONE
  84         jffs2_compression_mode = JFFS2_COMPR_MODE_NONE;
  85 @@ -401,6 +404,9 @@ int __init jffs2_compressors_init(void)
  86  int jffs2_compressors_exit(void)
  87  {
  88  /* Unregistering compressors */
  89 +#ifdef CONFIG_JFFS2_LZMA
  90 +        jffs2_lzma_exit();
  91 +#endif
  92  #ifdef CONFIG_JFFS2_LZO
  93         jffs2_lzo_exit();
  94  #endif
  95 diff --git a/fs/jffs2/compr.h b/fs/jffs2/compr.h
  96 index 5e91d578f4ed..32db2e1ec610 100644
  97 --- a/fs/jffs2/compr.h
  98 +++ b/fs/jffs2/compr.h
  99 @@ -29,9 +29,9 @@
 100  #define JFFS2_DYNRUBIN_PRIORITY  20
 101  #define JFFS2_LZARI_PRIORITY     30
 102  #define JFFS2_RTIME_PRIORITY     50
 103 -#define JFFS2_ZLIB_PRIORITY      60
 104 -#define JFFS2_LZO_PRIORITY       80
 105 -
 106 +#define JFFS2_LZMA_PRIORITY      70
 107 +#define JFFS2_ZLIB_PRIORITY      80
 108 +#define JFFS2_LZO_PRIORITY       90
 109
 110  #define JFFS2_RUBINMIPS_DISABLED /* RUBINs will be used only */
 111  #define JFFS2_DYNRUBIN_DISABLED  /*       for decompression */
 112 @@ -101,5 +101,9 @@ void jffs2_zlib_exit(void);
 113  int jffs2_lzo_init(void);
 114  void jffs2_lzo_exit(void);
 115  #endif
 116 +#ifdef CONFIG_JFFS2_LZMA
 117 +int jffs2_lzma_init(void);
 118 +void jffs2_lzma_exit(void);
 119 +#endif
 120
 121  #endif /* __JFFS2_COMPR_H__ */
 122 diff --git a/fs/jffs2/compr_lzma.c b/fs/jffs2/compr_lzma.c
 123 new file mode 100644
 124 index 000000000000..0fe3b75d7dcc
 125 --- /dev/null
 126 +++ b/fs/jffs2/compr_lzma.c
 127 @@ -0,0 +1,128 @@
 128 +/*
 129 + * JFFS2 -- Journalling Flash File System, Version 2.
 130 + *
 131 + * For licensing information, see the file 'LICENCE' in this directory.
 132 + *
 133 + * JFFS2 wrapper to the LZMA C SDK
 134 + *
 135 + */
 136 +
 137 +#include <linux/lzma.h>
 138 +#include "compr.h"
 139 +
 140 +#ifdef __KERNEL__
 141 +       static DEFINE_MUTEX(deflate_mutex);
 142 +#endif
 143 +
 144 +CLzmaEncHandle *p;
 145 +Byte propsEncoded[LZMA_PROPS_SIZE];
 146 +SizeT propsSize = sizeof(propsEncoded);
 147 +
 148 +STATIC void lzma_free_workspace(void)
 149 +{
 150 +       LzmaEnc_Destroy(p, &lzma_alloc, &lzma_alloc);
 151 +}
 152 +
 153 +STATIC int INIT lzma_alloc_workspace(CLzmaEncProps *props)
 154 +{
 155 +       if ((p = (CLzmaEncHandle *)LzmaEnc_Create(&lzma_alloc)) == NULL)
 156 +       {
 157 +               PRINT_ERROR("Failed to allocate lzma deflate workspace\n");
 158 +               return -ENOMEM;
 159 +       }
 160 +
 161 +       if (LzmaEnc_SetProps(p, props) != SZ_OK)
 162 +       {
 163 +               lzma_free_workspace();
 164 +               return -1;
 165 +       }
 166 +
 167 +       if (LzmaEnc_WriteProperties(p, propsEncoded, &propsSize) != SZ_OK)
 168 +       {
 169 +               lzma_free_workspace();
 170 +               return -1;
 171 +       }
 172 +
 173 +        return 0;
 174 +}
 175 +
 176 +STATIC int jffs2_lzma_compress(unsigned char *data_in, unsigned char *cpage_out,
 177 +                             uint32_t *sourcelen, uint32_t *dstlen)
 178 +{
 179 +       SizeT compress_size = (SizeT)(*dstlen);
 180 +       int ret;
 181 +
 182 +       #ifdef __KERNEL__
 183 +               mutex_lock(&deflate_mutex);
 184 +       #endif
 185 +
 186 +       ret = LzmaEnc_MemEncode(p, cpage_out, &compress_size, data_in, *sourcelen,
 187 +               0, NULL, &lzma_alloc, &lzma_alloc);
 188 +
 189 +       #ifdef __KERNEL__
 190 +               mutex_unlock(&deflate_mutex);
 191 +       #endif
 192 +
 193 +       if (ret != SZ_OK)
 194 +               return -1;
 195 +
 196 +       *dstlen = (uint32_t)compress_size;
 197 +
 198 +       return 0;
 199 +}
 200 +
 201 +STATIC int jffs2_lzma_decompress(unsigned char *data_in, unsigned char *cpage_out,
 202 +                                uint32_t srclen, uint32_t destlen)
 203 +{
 204 +       int ret;
 205 +       SizeT dl = (SizeT)destlen;
 206 +       SizeT sl = (SizeT)srclen;
 207 +       ELzmaStatus status;
 208 +
 209 +       ret = LzmaDecode(cpage_out, &dl, data_in, &sl, propsEncoded,
 210 +               propsSize, LZMA_FINISH_ANY, &status, &lzma_alloc);
 211 +
 212 +       if (ret != SZ_OK || status == LZMA_STATUS_NOT_FINISHED || dl != (SizeT)destlen)
 213 +               return -1;
 214 +
 215 +       return 0;
 216 +}
 217 +
 218 +static struct jffs2_compressor jffs2_lzma_comp = {
 219 +       .priority = JFFS2_LZMA_PRIORITY,
 220 +       .name = "lzma",
 221 +       .compr = JFFS2_COMPR_LZMA,
 222 +       .compress = &jffs2_lzma_compress,
 223 +       .decompress = &jffs2_lzma_decompress,
 224 +       .disabled = 0,
 225 +};
 226 +
 227 +int INIT jffs2_lzma_init(void)
 228 +{
 229 +        int ret;
 230 +       CLzmaEncProps props;
 231 +       LzmaEncProps_Init(&props);
 232 +
 233 +        props.dictSize = LZMA_BEST_DICT(0x2000);
 234 +        props.level = LZMA_BEST_LEVEL;
 235 +        props.lc = LZMA_BEST_LC;
 236 +        props.lp = LZMA_BEST_LP;
 237 +        props.pb = LZMA_BEST_PB;
 238 +        props.fb = LZMA_BEST_FB;
 239 +
 240 +       ret = lzma_alloc_workspace(&props);
 241 +        if (ret < 0)
 242 +                return ret;
 243 +
 244 +       ret = jffs2_register_compressor(&jffs2_lzma_comp);
 245 +       if (ret)
 246 +               lzma_free_workspace();
 247 +
 248 +        return ret;
 249 +}
 250 +
 251 +void jffs2_lzma_exit(void)
 252 +{
 253 +       jffs2_unregister_compressor(&jffs2_lzma_comp);
 254 +       lzma_free_workspace();
 255 +}
 256 diff --git a/fs/jffs2/super.c b/fs/jffs2/super.c
 257 index 5ef21f4c4c77..62e730216e7d 100644
 258 --- a/fs/jffs2/super.c
 259 +++ b/fs/jffs2/super.c
 260 @@ -372,14 +372,41 @@ static int __init init_jffs2_fs(void)
 261         BUILD_BUG_ON(sizeof(struct jffs2_raw_inode) != 68);
 262         BUILD_BUG_ON(sizeof(struct jffs2_raw_summary) != 32);
 263
 264 -       pr_info("version 2.2."
 265 +       pr_info("version 2.2"
 266  #ifdef CONFIG_JFFS2_FS_WRITEBUFFER
 267                " (NAND)"
 268  #endif
 269  #ifdef CONFIG_JFFS2_SUMMARY
 270 -              " (SUMMARY) "
 271 +              " (SUMMARY)"
 272  #endif
 273 -              " © 2001-2006 Red Hat, Inc.\n");
 274 +#ifdef CONFIG_JFFS2_ZLIB
 275 +              " (ZLIB)"
 276 +#endif
 277 +#ifdef CONFIG_JFFS2_LZO
 278 +              " (LZO)"
 279 +#endif
 280 +#ifdef CONFIG_JFFS2_LZMA
 281 +              " (LZMA)"
 282 +#endif
 283 +#ifdef CONFIG_JFFS2_RTIME
 284 +              " (RTIME)"
 285 +#endif
 286 +#ifdef CONFIG_JFFS2_RUBIN
 287 +              " (RUBIN)"
 288 +#endif
 289 +#ifdef  CONFIG_JFFS2_CMODE_NONE
 290 +              " (CMODE_NONE)"
 291 +#endif
 292 +#ifdef CONFIG_JFFS2_CMODE_PRIORITY
 293 +              " (CMODE_PRIORITY)"
 294 +#endif
 295 +#ifdef CONFIG_JFFS2_CMODE_SIZE
 296 +              " (CMODE_SIZE)"
 297 +#endif
 298 +#ifdef CONFIG_JFFS2_CMODE_FAVOURLZO
 299 +              " (CMODE_FAVOURLZO)"
 300 +#endif
 301 +              " (c) 2001-2006 Red Hat, Inc.\n");
 302
 303         jffs2_inode_cachep = kmem_cache_create("jffs2_i",
 304                                              sizeof(struct jffs2_inode_info),
 305 diff --git a/include/linux/lzma.h b/include/linux/lzma.h
 306 new file mode 100644
 307 index 000000000000..5f31334dfc31
 308 --- /dev/null
 309 +++ b/include/linux/lzma.h
 310 @@ -0,0 +1,62 @@
 311 +#ifndef __LZMA_H__
 312 +#define __LZMA_H__
 313 +
 314 +#ifdef __KERNEL__
 315 +       #include <linux/kernel.h>
 316 +       #include <linux/sched.h>
 317 +       #include <linux/slab.h>
 318 +       #include <linux/vmalloc.h>
 319 +       #include <linux/init.h>
 320 +       #define LZMA_MALLOC vmalloc
 321 +       #define LZMA_FREE vfree
 322 +       #define PRINT_ERROR(msg) printk(KERN_WARNING #msg)
 323 +       #define INIT __init
 324 +       #define STATIC static
 325 +#else
 326 +       #include <stdint.h>
 327 +       #include <stdlib.h>
 328 +       #include <stdio.h>
 329 +       #include <unistd.h>
 330 +       #include <string.h>
 331 +       #include <asm/types.h>
 332 +       #include <errno.h>
 333 +       #include <linux/jffs2.h>
 334 +       #ifndef PAGE_SIZE
 335 +               extern int page_size;
 336 +               #define PAGE_SIZE page_size
 337 +       #endif
 338 +       #define LZMA_MALLOC malloc
 339 +       #define LZMA_FREE free
 340 +       #define PRINT_ERROR(msg) fprintf(stderr, msg)
 341 +       #define INIT
 342 +       #define STATIC
 343 +#endif
 344 +
 345 +#include "lzma/LzmaDec.h"
 346 +#include "lzma/LzmaEnc.h"
 347 +
 348 +#define LZMA_BEST_LEVEL (9)
 349 +#define LZMA_BEST_LC    (0)
 350 +#define LZMA_BEST_LP    (0)
 351 +#define LZMA_BEST_PB    (0)
 352 +#define LZMA_BEST_FB  (273)
 353 +
 354 +#define LZMA_BEST_DICT(n) (((int)((n) / 2)) * 2)
 355 +
 356 +static void *p_lzma_malloc(void *p, size_t size)
 357 +{
 358 +        if (size == 0)
 359 +                return NULL;
 360 +
 361 +        return LZMA_MALLOC(size);
 362 +}
 363 +
 364 +static void p_lzma_free(void *p, void *address)
 365 +{
 366 +        if (address != NULL)
 367 +                LZMA_FREE(address);
 368 +}
 369 +
 370 +static ISzAlloc lzma_alloc = {p_lzma_malloc, p_lzma_free};
 371 +
 372 +#endif
 373 diff --git a/include/linux/lzma/LzFind.h b/include/linux/lzma/LzFind.h
 374 new file mode 100644
 375 index 000000000000..010c4b92ba33
 376 --- /dev/null
 377 +++ b/include/linux/lzma/LzFind.h
 378 @@ -0,0 +1,115 @@
 379 +/* LzFind.h -- Match finder for LZ algorithms
 380 +2009-04-22 : Igor Pavlov : Public domain */
 381 +
 382 +#ifndef __LZ_FIND_H
 383 +#define __LZ_FIND_H
 384 +
 385 +#include "Types.h"
 386 +
 387 +#ifdef __cplusplus
 388 +extern "C" {
 389 +#endif
 390 +
 391 +typedef UInt32 CLzRef;
 392 +
 393 +typedef struct _CMatchFinder
 394 +{
 395 +  Byte *buffer;
 396 +  UInt32 pos;
 397 +  UInt32 posLimit;
 398 +  UInt32 streamPos;
 399 +  UInt32 lenLimit;
 400 +
 401 +  UInt32 cyclicBufferPos;
 402 +  UInt32 cyclicBufferSize; /* it must be = (historySize + 1) */
 403 +
 404 +  UInt32 matchMaxLen;
 405 +  CLzRef *hash;
 406 +  CLzRef *son;
 407 +  UInt32 hashMask;
 408 +  UInt32 cutValue;
 409 +
 410 +  Byte *bufferBase;
 411 +  ISeqInStream *stream;
 412 +  int streamEndWasReached;
 413 +
 414 +  UInt32 blockSize;
 415 +  UInt32 keepSizeBefore;
 416 +  UInt32 keepSizeAfter;
 417 +
 418 +  UInt32 numHashBytes;
 419 +  int directInput;
 420 +  size_t directInputRem;
 421 +  int btMode;
 422 +  int bigHash;
 423 +  UInt32 historySize;
 424 +  UInt32 fixedHashSize;
 425 +  UInt32 hashSizeSum;
 426 +  UInt32 numSons;
 427 +  SRes result;
 428 +  UInt32 crc[256];
 429 +} CMatchFinder;
 430 +
 431 +#define Inline_MatchFinder_GetPointerToCurrentPos(p) ((p)->buffer)
 432 +#define Inline_MatchFinder_GetIndexByte(p, index) ((p)->buffer[(Int32)(index)])
 433 +
 434 +#define Inline_MatchFinder_GetNumAvailableBytes(p) ((p)->streamPos - (p)->pos)
 435 +
 436 +int MatchFinder_NeedMove(CMatchFinder *p);
 437 +Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p);
 438 +void MatchFinder_MoveBlock(CMatchFinder *p);
 439 +void MatchFinder_ReadIfRequired(CMatchFinder *p);
 440 +
 441 +void MatchFinder_Construct(CMatchFinder *p);
 442 +
 443 +/* Conditions:
 444 +     historySize <= 3 GB
 445 +     keepAddBufferBefore + matchMaxLen + keepAddBufferAfter < 511MB
 446 +*/
 447 +int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
 448 +    UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
 449 +    ISzAlloc *alloc);
 450 +void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc);
 451 +void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems);
 452 +void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue);
 453 +
 454 +UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *buffer, CLzRef *son,
 455 +    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 _cutValue,
 456 +    UInt32 *distances, UInt32 maxLen);
 457 +
 458 +/*
 459 +Conditions:
 460 +  Mf_GetNumAvailableBytes_Func must be called before each Mf_GetMatchLen_Func.
 461 +  Mf_GetPointerToCurrentPos_Func's result must be used only before any other function
 462 +*/
 463 +
 464 +typedef void (*Mf_Init_Func)(void *object);
 465 +typedef Byte (*Mf_GetIndexByte_Func)(void *object, Int32 index);
 466 +typedef UInt32 (*Mf_GetNumAvailableBytes_Func)(void *object);
 467 +typedef const Byte * (*Mf_GetPointerToCurrentPos_Func)(void *object);
 468 +typedef UInt32 (*Mf_GetMatches_Func)(void *object, UInt32 *distances);
 469 +typedef void (*Mf_Skip_Func)(void *object, UInt32);
 470 +
 471 +typedef struct _IMatchFinder
 472 +{
 473 +  Mf_Init_Func Init;
 474 +  Mf_GetIndexByte_Func GetIndexByte;
 475 +  Mf_GetNumAvailableBytes_Func GetNumAvailableBytes;
 476 +  Mf_GetPointerToCurrentPos_Func GetPointerToCurrentPos;
 477 +  Mf_GetMatches_Func GetMatches;
 478 +  Mf_Skip_Func Skip;
 479 +} IMatchFinder;
 480 +
 481 +void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable);
 482 +
 483 +void MatchFinder_Init(CMatchFinder *p);
 484 +UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances);
 485 +UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances);
 486 +void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num);
 487 +void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num);
 488 +
 489 +#ifdef __cplusplus
 490 +}
 491 +#endif
 492 +
 493 +#endif
 494 diff --git a/include/linux/lzma/LzHash.h b/include/linux/lzma/LzHash.h
 495 new file mode 100644
 496 index 000000000000..f3e89966cc70
 497 --- /dev/null
 498 +++ b/include/linux/lzma/LzHash.h
 499 @@ -0,0 +1,54 @@
 500 +/* LzHash.h -- HASH functions for LZ algorithms
 501 +2009-02-07 : Igor Pavlov : Public domain */
 502 +
 503 +#ifndef __LZ_HASH_H
 504 +#define __LZ_HASH_H
 505 +
 506 +#define kHash2Size (1 << 10)
 507 +#define kHash3Size (1 << 16)
 508 +#define kHash4Size (1 << 20)
 509 +
 510 +#define kFix3HashSize (kHash2Size)
 511 +#define kFix4HashSize (kHash2Size + kHash3Size)
 512 +#define kFix5HashSize (kHash2Size + kHash3Size + kHash4Size)
 513 +
 514 +#define HASH2_CALC hashValue = cur[0] | ((UInt32)cur[1] << 8);
 515 +
 516 +#define HASH3_CALC { \
 517 +  UInt32 temp = p->crc[cur[0]] ^ cur[1]; \
 518 +  hash2Value = temp & (kHash2Size - 1); \
 519 +  hashValue = (temp ^ ((UInt32)cur[2] << 8)) & p->hashMask; }
 520 +
 521 +#define HASH4_CALC { \
 522 +  UInt32 temp = p->crc[cur[0]] ^ cur[1]; \
 523 +  hash2Value = temp & (kHash2Size - 1); \
 524 +  hash3Value = (temp ^ ((UInt32)cur[2] << 8)) & (kHash3Size - 1); \
 525 +  hashValue = (temp ^ ((UInt32)cur[2] << 8) ^ (p->crc[cur[3]] << 5)) & p->hashMask; }
 526 +
 527 +#define HASH5_CALC { \
 528 +  UInt32 temp = p->crc[cur[0]] ^ cur[1]; \
 529 +  hash2Value = temp & (kHash2Size - 1); \
 530 +  hash3Value = (temp ^ ((UInt32)cur[2] << 8)) & (kHash3Size - 1); \
 531 +  hash4Value = (temp ^ ((UInt32)cur[2] << 8) ^ (p->crc[cur[3]] << 5)); \
 532 +  hashValue = (hash4Value ^ (p->crc[cur[4]] << 3)) & p->hashMask; \
 533 +  hash4Value &= (kHash4Size - 1); }
 534 +
 535 +/* #define HASH_ZIP_CALC hashValue = ((cur[0] | ((UInt32)cur[1] << 8)) ^ p->crc[cur[2]]) & 0xFFFF; */
 536 +#define HASH_ZIP_CALC hashValue = ((cur[2] | ((UInt32)cur[0] << 8)) ^ p->crc[cur[1]]) & 0xFFFF;
 537 +
 538 +
 539 +#define MT_HASH2_CALC \
 540 +  hash2Value = (p->crc[cur[0]] ^ cur[1]) & (kHash2Size - 1);
 541 +
 542 +#define MT_HASH3_CALC { \
 543 +  UInt32 temp = p->crc[cur[0]] ^ cur[1]; \
 544 +  hash2Value = temp & (kHash2Size - 1); \
 545 +  hash3Value = (temp ^ ((UInt32)cur[2] << 8)) & (kHash3Size - 1); }
 546 +
 547 +#define MT_HASH4_CALC { \
 548 +  UInt32 temp = p->crc[cur[0]] ^ cur[1]; \
 549 +  hash2Value = temp & (kHash2Size - 1); \
 550 +  hash3Value = (temp ^ ((UInt32)cur[2] << 8)) & (kHash3Size - 1); \
 551 +  hash4Value = (temp ^ ((UInt32)cur[2] << 8) ^ (p->crc[cur[3]] << 5)) & (kHash4Size - 1); }
 552 +
 553 +#endif
 554 diff --git a/include/linux/lzma/LzmaDec.h b/include/linux/lzma/LzmaDec.h
 555 new file mode 100644
 556 index 000000000000..bf7f084ba3dd
 557 --- /dev/null
 558 +++ b/include/linux/lzma/LzmaDec.h
 559 @@ -0,0 +1,231 @@
 560 +/* LzmaDec.h -- LZMA Decoder
 561 +2009-02-07 : Igor Pavlov : Public domain */
 562 +
 563 +#ifndef __LZMA_DEC_H
 564 +#define __LZMA_DEC_H
 565 +
 566 +#include "Types.h"
 567 +
 568 +#ifdef __cplusplus
 569 +extern "C" {
 570 +#endif
 571 +
 572 +/* #define _LZMA_PROB32 */
 573 +/* _LZMA_PROB32 can increase the speed on some CPUs,
 574 +   but memory usage for CLzmaDec::probs will be doubled in that case */
 575 +
 576 +#ifdef _LZMA_PROB32
 577 +#define CLzmaProb UInt32
 578 +#else
 579 +#define CLzmaProb UInt16
 580 +#endif
 581 +
 582 +
 583 +/* ---------- LZMA Properties ---------- */
 584 +
 585 +#define LZMA_PROPS_SIZE 5
 586 +
 587 +typedef struct _CLzmaProps
 588 +{
 589 +  unsigned lc, lp, pb;
 590 +  UInt32 dicSize;
 591 +} CLzmaProps;
 592 +
 593 +/* LzmaProps_Decode - decodes properties
 594 +Returns:
 595 +  SZ_OK
 596 +  SZ_ERROR_UNSUPPORTED - Unsupported properties
 597 +*/
 598 +
 599 +SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size);
 600 +
 601 +
 602 +/* ---------- LZMA Decoder state ---------- */
 603 +
 604 +/* LZMA_REQUIRED_INPUT_MAX = number of required input bytes for worst case.
 605 +   Num bits = log2((2^11 / 31) ^ 22) + 26 < 134 + 26 = 160; */
 606 +
 607 +#define LZMA_REQUIRED_INPUT_MAX 20
 608 +
 609 +typedef struct
 610 +{
 611 +  CLzmaProps prop;
 612 +  CLzmaProb *probs;
 613 +  Byte *dic;
 614 +  const Byte *buf;
 615 +  UInt32 range, code;
 616 +  SizeT dicPos;
 617 +  SizeT dicBufSize;
 618 +  UInt32 processedPos;
 619 +  UInt32 checkDicSize;
 620 +  unsigned state;
 621 +  UInt32 reps[4];
 622 +  unsigned remainLen;
 623 +  int needFlush;
 624 +  int needInitState;
 625 +  UInt32 numProbs;
 626 +  unsigned tempBufSize;
 627 +  Byte tempBuf[LZMA_REQUIRED_INPUT_MAX];
 628 +} CLzmaDec;
 629 +
 630 +#define LzmaDec_Construct(p) { (p)->dic = 0; (p)->probs = 0; }
 631 +
 632 +void LzmaDec_Init(CLzmaDec *p);
 633 +
 634 +/* There are two types of LZMA streams:
 635 +     0) Stream with end mark. That end mark adds about 6 bytes to compressed size.
 636 +     1) Stream without end mark. You must know exact uncompressed size to decompress such stream. */
 637 +
 638 +typedef enum
 639 +{
 640 +  LZMA_FINISH_ANY,   /* finish at any point */
 641 +  LZMA_FINISH_END    /* block must be finished at the end */
 642 +} ELzmaFinishMode;
 643 +
 644 +/* ELzmaFinishMode has meaning only if the decoding reaches output limit !!!
 645 +
 646 +   You must use LZMA_FINISH_END, when you know that current output buffer
 647 +   covers last bytes of block. In other cases you must use LZMA_FINISH_ANY.
 648 +
 649 +   If LZMA decoder sees end marker before reaching output limit, it returns SZ_OK,
 650 +   and output value of destLen will be less than output buffer size limit.
 651 +   You can check status result also.
 652 +
 653 +   You can use multiple checks to test data integrity after full decompression:
 654 +     1) Check Result and "status" variable.
 655 +     2) Check that output(destLen) = uncompressedSize, if you know real uncompressedSize.
 656 +     3) Check that output(srcLen) = compressedSize, if you know real compressedSize.
 657 +        You must use correct finish mode in that case. */
 658 +
 659 +typedef enum
 660 +{
 661 +  LZMA_STATUS_NOT_SPECIFIED,               /* use main error code instead */
 662 +  LZMA_STATUS_FINISHED_WITH_MARK,          /* stream was finished with end mark. */
 663 +  LZMA_STATUS_NOT_FINISHED,                /* stream was not finished */
 664 +  LZMA_STATUS_NEEDS_MORE_INPUT,            /* you must provide more input bytes */
 665 +  LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK  /* there is probability that stream was finished without end mark */
 666 +} ELzmaStatus;
 667 +
 668 +/* ELzmaStatus is used only as output value for function call */
 669 +
 670 +
 671 +/* ---------- Interfaces ---------- */
 672 +
 673 +/* There are 3 levels of interfaces:
 674 +     1) Dictionary Interface
 675 +     2) Buffer Interface
 676 +     3) One Call Interface
 677 +   You can select any of these interfaces, but don't mix functions from different
 678 +   groups for same object. */
 679 +
 680 +
 681 +/* There are two variants to allocate state for Dictionary Interface:
 682 +     1) LzmaDec_Allocate / LzmaDec_Free
 683 +     2) LzmaDec_AllocateProbs / LzmaDec_FreeProbs
 684 +   You can use variant 2, if you set dictionary buffer manually.
 685 +   For Buffer Interface you must always use variant 1.
 686 +
 687 +LzmaDec_Allocate* can return:
 688 +  SZ_OK
 689 +  SZ_ERROR_MEM         - Memory allocation error
 690 +  SZ_ERROR_UNSUPPORTED - Unsupported properties
 691 +*/
 692 +
 693 +SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc);
 694 +void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc);
 695 +
 696 +SRes LzmaDec_Allocate(CLzmaDec *state, const Byte *prop, unsigned propsSize, ISzAlloc *alloc);
 697 +void LzmaDec_Free(CLzmaDec *state, ISzAlloc *alloc);
 698 +
 699 +/* ---------- Dictionary Interface ---------- */
 700 +
 701 +/* You can use it, if you want to eliminate the overhead for data copying from
 702 +   dictionary to some other external buffer.
 703 +   You must work with CLzmaDec variables directly in this interface.
 704 +
 705 +   STEPS:
 706 +     LzmaDec_Constr()
 707 +     LzmaDec_Allocate()
 708 +     for (each new stream)
 709 +     {
 710 +       LzmaDec_Init()
 711 +       while (it needs more decompression)
 712 +       {
 713 +         LzmaDec_DecodeToDic()
 714 +         use data from CLzmaDec::dic and update CLzmaDec::dicPos
 715 +       }
 716 +     }
 717 +     LzmaDec_Free()
 718 +*/
 719 +
 720 +/* LzmaDec_DecodeToDic
 721 +
 722 +   The decoding to internal dictionary buffer (CLzmaDec::dic).
 723 +   You must manually update CLzmaDec::dicPos, if it reaches CLzmaDec::dicBufSize !!!
 724 +
 725 +finishMode:
 726 +  It has meaning only if the decoding reaches output limit (dicLimit).
 727 +  LZMA_FINISH_ANY - Decode just dicLimit bytes.
 728 +  LZMA_FINISH_END - Stream must be finished after dicLimit.
 729 +
 730 +Returns:
 731 +  SZ_OK
 732 +    status:
 733 +      LZMA_STATUS_FINISHED_WITH_MARK
 734 +      LZMA_STATUS_NOT_FINISHED
 735 +      LZMA_STATUS_NEEDS_MORE_INPUT
 736 +      LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK
 737 +  SZ_ERROR_DATA - Data error
 738 +*/
 739 +
 740 +SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit,
 741 +    const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status);
 742 +
 743 +
 744 +/* ---------- Buffer Interface ---------- */
 745 +
 746 +/* It's zlib-like interface.
 747 +   See LzmaDec_DecodeToDic description for information about STEPS and return results,
 748 +   but you must use LzmaDec_DecodeToBuf instead of LzmaDec_DecodeToDic and you don't need
 749 +   to work with CLzmaDec variables manually.
 750 +
 751 +finishMode:
 752 +  It has meaning only if the decoding reaches output limit (*destLen).
 753 +  LZMA_FINISH_ANY - Decode just destLen bytes.
 754 +  LZMA_FINISH_END - Stream must be finished after (*destLen).
 755 +*/
 756 +
 757 +SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen,
 758 +    const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status);
 759 +
 760 +
 761 +/* ---------- One Call Interface ---------- */
 762 +
 763 +/* LzmaDecode
 764 +
 765 +finishMode:
 766 +  It has meaning only if the decoding reaches output limit (*destLen).
 767 +  LZMA_FINISH_ANY - Decode just destLen bytes.
 768 +  LZMA_FINISH_END - Stream must be finished after (*destLen).
 769 +
 770 +Returns:
 771 +  SZ_OK
 772 +    status:
 773 +      LZMA_STATUS_FINISHED_WITH_MARK
 774 +      LZMA_STATUS_NOT_FINISHED
 775 +      LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK
 776 +  SZ_ERROR_DATA - Data error
 777 +  SZ_ERROR_MEM  - Memory allocation error
 778 +  SZ_ERROR_UNSUPPORTED - Unsupported properties
 779 +  SZ_ERROR_INPUT_EOF - It needs more bytes in input buffer (src).
 780 +*/
 781 +
 782 +SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
 783 +    const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,
 784 +    ELzmaStatus *status, ISzAlloc *alloc);
 785 +
 786 +#ifdef __cplusplus
 787 +}
 788 +#endif
 789 +
 790 +#endif
 791 diff --git a/include/linux/lzma/LzmaEnc.h b/include/linux/lzma/LzmaEnc.h
 792 new file mode 100644
 793 index 000000000000..200d60eb83cd
 794 --- /dev/null
 795 +++ b/include/linux/lzma/LzmaEnc.h
 796 @@ -0,0 +1,80 @@
 797 +/*  LzmaEnc.h -- LZMA Encoder
 798 +2009-02-07 : Igor Pavlov : Public domain */
 799 +
 800 +#ifndef __LZMA_ENC_H
 801 +#define __LZMA_ENC_H
 802 +
 803 +#include "Types.h"
 804 +
 805 +#ifdef __cplusplus
 806 +extern "C" {
 807 +#endif
 808 +
 809 +#define LZMA_PROPS_SIZE 5
 810 +
 811 +typedef struct _CLzmaEncProps
 812 +{
 813 +  int level;       /*  0 <= level <= 9 */
 814 +  UInt32 dictSize; /* (1 << 12) <= dictSize <= (1 << 27) for 32-bit version
 815 +                      (1 << 12) <= dictSize <= (1 << 30) for 64-bit version
 816 +                       default = (1 << 24) */
 817 +  int lc;          /* 0 <= lc <= 8, default = 3 */
 818 +  int lp;          /* 0 <= lp <= 4, default = 0 */
 819 +  int pb;          /* 0 <= pb <= 4, default = 2 */
 820 +  int algo;        /* 0 - fast, 1 - normal, default = 1 */
 821 +  int fb;          /* 5 <= fb <= 273, default = 32 */
 822 +  int btMode;      /* 0 - hashChain Mode, 1 - binTree mode - normal, default = 1 */
 823 +  int numHashBytes; /* 2, 3 or 4, default = 4 */
 824 +  UInt32 mc;        /* 1 <= mc <= (1 << 30), default = 32 */
 825 +  unsigned writeEndMark;  /* 0 - do not write EOPM, 1 - write EOPM, default = 0 */
 826 +  int numThreads;  /* 1 or 2, default = 2 */
 827 +} CLzmaEncProps;
 828 +
 829 +void LzmaEncProps_Init(CLzmaEncProps *p);
 830 +void LzmaEncProps_Normalize(CLzmaEncProps *p);
 831 +UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2);
 832 +
 833 +
 834 +/* ---------- CLzmaEncHandle Interface ---------- */
 835 +
 836 +/* LzmaEnc_* functions can return the following exit codes:
 837 +Returns:
 838 +  SZ_OK           - OK
 839 +  SZ_ERROR_MEM    - Memory allocation error
 840 +  SZ_ERROR_PARAM  - Incorrect paramater in props
 841 +  SZ_ERROR_WRITE  - Write callback error.
 842 +  SZ_ERROR_PROGRESS - some break from progress callback
 843 +  SZ_ERROR_THREAD - errors in multithreading functions (only for Mt version)
 844 +*/
 845 +
 846 +typedef void * CLzmaEncHandle;
 847 +
 848 +CLzmaEncHandle LzmaEnc_Create(ISzAlloc *alloc);
 849 +void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAlloc *alloc, ISzAlloc *allocBig);
 850 +SRes LzmaEnc_SetProps(CLzmaEncHandle p, const CLzmaEncProps *props);
 851 +SRes LzmaEnc_WriteProperties(CLzmaEncHandle p, Byte *properties, SizeT *size);
 852 +SRes LzmaEnc_Encode(CLzmaEncHandle p, ISeqOutStream *outStream, ISeqInStream *inStream,
 853 +    ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig);
 854 +SRes LzmaEnc_MemEncode(CLzmaEncHandle p, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
 855 +    int writeEndMark, ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig);
 856 +
 857 +/* ---------- One Call Interface ---------- */
 858 +
 859 +/* LzmaEncode
 860 +Return code:
 861 +  SZ_OK               - OK
 862 +  SZ_ERROR_MEM        - Memory allocation error
 863 +  SZ_ERROR_PARAM      - Incorrect paramater
 864 +  SZ_ERROR_OUTPUT_EOF - output buffer overflow
 865 +  SZ_ERROR_THREAD     - errors in multithreading functions (only for Mt version)
 866 +*/
 867 +
 868 +SRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
 869 +    const CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeEndMark,
 870 +    ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig);
 871 +
 872 +#ifdef __cplusplus
 873 +}
 874 +#endif
 875 +
 876 +#endif
 877 diff --git a/include/linux/lzma/Types.h b/include/linux/lzma/Types.h
 878 new file mode 100644
 879 index 000000000000..4751acde0722
 880 --- /dev/null
 881 +++ b/include/linux/lzma/Types.h
 882 @@ -0,0 +1,226 @@
 883 +/* Types.h -- Basic types
 884 +2009-11-23 : Igor Pavlov : Public domain */
 885 +
 886 +#ifndef __7Z_TYPES_H
 887 +#define __7Z_TYPES_H
 888 +
 889 +#include <stddef.h>
 890 +
 891 +#ifdef _WIN32
 892 +#include <windows.h>
 893 +#endif
 894 +
 895 +#ifndef EXTERN_C_BEGIN
 896 +#ifdef __cplusplus
 897 +#define EXTERN_C_BEGIN extern "C" {
 898 +#define EXTERN_C_END }
 899 +#else
 900 +#define EXTERN_C_BEGIN
 901 +#define EXTERN_C_END
 902 +#endif
 903 +#endif
 904 +
 905 +EXTERN_C_BEGIN
 906 +
 907 +#define SZ_OK 0
 908 +
 909 +#define SZ_ERROR_DATA 1
 910 +#define SZ_ERROR_MEM 2
 911 +#define SZ_ERROR_CRC 3
 912 +#define SZ_ERROR_UNSUPPORTED 4
 913 +#define SZ_ERROR_PARAM 5
 914 +#define SZ_ERROR_INPUT_EOF 6
 915 +#define SZ_ERROR_OUTPUT_EOF 7
 916 +#define SZ_ERROR_READ 8
 917 +#define SZ_ERROR_WRITE 9
 918 +#define SZ_ERROR_PROGRESS 10
 919 +#define SZ_ERROR_FAIL 11
 920 +#define SZ_ERROR_THREAD 12
 921 +
 922 +#define SZ_ERROR_ARCHIVE 16
 923 +#define SZ_ERROR_NO_ARCHIVE 17
 924 +
 925 +typedef int SRes;
 926 +
 927 +#ifdef _WIN32
 928 +typedef DWORD WRes;
 929 +#else
 930 +typedef int WRes;
 931 +#endif
 932 +
 933 +#ifndef RINOK
 934 +#define RINOK(x) { int __result__ = (x); if (__result__ != 0) return __result__; }
 935 +#endif
 936 +
 937 +typedef unsigned char Byte;
 938 +typedef short Int16;
 939 +typedef unsigned short UInt16;
 940 +
 941 +#ifdef _LZMA_UINT32_IS_ULONG
 942 +typedef long Int32;
 943 +typedef unsigned long UInt32;
 944 +#else
 945 +typedef int Int32;
 946 +typedef unsigned int UInt32;
 947 +#endif
 948 +
 949 +#ifdef _SZ_NO_INT_64
 950 +
 951 +/* define _SZ_NO_INT_64, if your compiler doesn't support 64-bit integers.
 952 +   NOTES: Some code will work incorrectly in that case! */
 953 +
 954 +typedef long Int64;
 955 +typedef unsigned long UInt64;
 956 +
 957 +#else
 958 +
 959 +#if defined(_MSC_VER) || defined(__BORLANDC__)
 960 +typedef __int64 Int64;
 961 +typedef unsigned __int64 UInt64;
 962 +#else
 963 +typedef long long int Int64;
 964 +typedef unsigned long long int UInt64;
 965 +#endif
 966 +
 967 +#endif
 968 +
 969 +#ifdef _LZMA_NO_SYSTEM_SIZE_T
 970 +typedef UInt32 SizeT;
 971 +#else
 972 +typedef size_t SizeT;
 973 +#endif
 974 +
 975 +typedef int Bool;
 976 +#define True 1
 977 +#define False 0
 978 +
 979 +
 980 +#ifdef _WIN32
 981 +#define MY_STD_CALL __stdcall
 982 +#else
 983 +#define MY_STD_CALL
 984 +#endif
 985 +
 986 +#ifdef _MSC_VER
 987 +
 988 +#if _MSC_VER >= 1300
 989 +#define MY_NO_INLINE __declspec(noinline)
 990 +#else
 991 +#define MY_NO_INLINE
 992 +#endif
 993 +
 994 +#define MY_CDECL __cdecl
 995 +#define MY_FAST_CALL __fastcall
 996 +
 997 +#else
 998 +
 999 +#define MY_CDECL
1000 +#define MY_FAST_CALL
1001 +
1002 +#endif
1003 +
1004 +
1005 +/* The following interfaces use first parameter as pointer to structure */
1006 +
1007 +typedef struct
1008 +{
1009 +  SRes (*Read)(void *p, void *buf, size_t *size);
1010 +    /* if (input(*size) != 0 && output(*size) == 0) means end_of_stream.
1011 +       (output(*size) < input(*size)) is allowed */
1012 +} ISeqInStream;
1013 +
1014 +/* it can return SZ_ERROR_INPUT_EOF */
1015 +SRes SeqInStream_Read(ISeqInStream *stream, void *buf, size_t size);
1016 +SRes SeqInStream_Read2(ISeqInStream *stream, void *buf, size_t size, SRes errorType);
1017 +SRes SeqInStream_ReadByte(ISeqInStream *stream, Byte *buf);
1018 +
1019 +typedef struct
1020 +{
1021 +  size_t (*Write)(void *p, const void *buf, size_t size);
1022 +    /* Returns: result - the number of actually written bytes.
1023 +       (result < size) means error */
1024 +} ISeqOutStream;
1025 +
1026 +typedef enum
1027 +{
1028 +  SZ_SEEK_SET = 0,
1029 +  SZ_SEEK_CUR = 1,
1030 +  SZ_SEEK_END = 2
1031 +} ESzSeek;
1032 +
1033 +typedef struct
1034 +{
1035 +  SRes (*Read)(void *p, void *buf, size_t *size);  /* same as ISeqInStream::Read */
1036 +  SRes (*Seek)(void *p, Int64 *pos, ESzSeek origin);
1037 +} ISeekInStream;
1038 +
1039 +typedef struct
1040 +{
1041 +  SRes (*Look)(void *p, void **buf, size_t *size);
1042 +    /* if (input(*size) != 0 && output(*size) == 0) means end_of_stream.
1043 +       (output(*size) > input(*size)) is not allowed
1044 +       (output(*size) < input(*size)) is allowed */
1045 +  SRes (*Skip)(void *p, size_t offset);
1046 +    /* offset must be <= output(*size) of Look */
1047 +
1048 +  SRes (*Read)(void *p, void *buf, size_t *size);
1049 +    /* reads directly (without buffer). It's same as ISeqInStream::Read */
1050 +  SRes (*Seek)(void *p, Int64 *pos, ESzSeek origin);
1051 +} ILookInStream;
1052 +
1053 +SRes LookInStream_LookRead(ILookInStream *stream, void *buf, size_t *size);
1054 +SRes LookInStream_SeekTo(ILookInStream *stream, UInt64 offset);
1055 +
1056 +/* reads via ILookInStream::Read */
1057 +SRes LookInStream_Read2(ILookInStream *stream, void *buf, size_t size, SRes errorType);
1058 +SRes LookInStream_Read(ILookInStream *stream, void *buf, size_t size);
1059 +
1060 +#define LookToRead_BUF_SIZE (1 << 14)
1061 +
1062 +typedef struct
1063 +{
1064 +  ILookInStream s;
1065 +  ISeekInStream *realStream;
1066 +  size_t pos;
1067 +  size_t size;
1068 +  Byte buf[LookToRead_BUF_SIZE];
1069 +} CLookToRead;
1070 +
1071 +void LookToRead_CreateVTable(CLookToRead *p, int lookahead);
1072 +void LookToRead_Init(CLookToRead *p);
1073 +
1074 +typedef struct
1075 +{
1076 +  ISeqInStream s;
1077 +  ILookInStream *realStream;
1078 +} CSecToLook;
1079 +
1080 +void SecToLook_CreateVTable(CSecToLook *p);
1081 +
1082 +typedef struct
1083 +{
1084 +  ISeqInStream s;
1085 +  ILookInStream *realStream;
1086 +} CSecToRead;
1087 +
1088 +void SecToRead_CreateVTable(CSecToRead *p);
1089 +
1090 +typedef struct
1091 +{
1092 +  SRes (*Progress)(void *p, UInt64 inSize, UInt64 outSize);
1093 +    /* Returns: result. (result != SZ_OK) means break.
1094 +       Value (UInt64)(Int64)-1 for size means unknown value. */
1095 +} ICompressProgress;
1096 +
1097 +typedef struct
1098 +{
1099 +  void *(*Alloc)(void *p, size_t size);
1100 +  void (*Free)(void *p, void *address); /* address can be 0 */
1101 +} ISzAlloc;
1102 +
1103 +#define IAlloc_Alloc(p, size) (p)->Alloc((p), size)
1104 +#define IAlloc_Free(p, a) (p)->Free((p), a)
1105 +
1106 +EXTERN_C_END
1107 +
1108 +#endif
1109 diff --git a/include/uapi/linux/jffs2.h b/include/uapi/linux/jffs2.h
1110 index a18b719f49d4..f3431a5ff4ff 100644
1111 --- a/include/uapi/linux/jffs2.h
1112 +++ b/include/uapi/linux/jffs2.h
1113 @@ -46,6 +46,7 @@
1114  #define JFFS2_COMPR_DYNRUBIN   0x05
1115  #define JFFS2_COMPR_ZLIB       0x06
1116  #define JFFS2_COMPR_LZO                0x07
1117 +#define JFFS2_COMPR_LZMA       0x08
1118  /* Compatibility flags. */
1119  #define JFFS2_COMPAT_MASK 0xc000      /* What do to if an unknown nodetype is found */
1120  #define JFFS2_NODE_ACCURATE 0x2000
1121 diff --git a/lib/Kconfig b/lib/Kconfig
1122 index 260a80e313b9..2e20b2b1ba02 100644
1123 --- a/lib/Kconfig
1124 +++ b/lib/Kconfig
1125 @@ -241,6 +241,12 @@ config LZ4_DECOMPRESS
1126
1127  source "lib/xz/Kconfig"
1128
1129 +config LZMA_COMPRESS
1130 +    tristate
1131 +
1132 +config LZMA_DECOMPRESS
1133 +    tristate
1134 +
1135  #
1136  # These all provide a common interface (hence the apparent duplication with
1137  # ZLIB_INFLATE; DECOMPRESS_GZIP is just a wrapper.)
1138 diff --git a/lib/Makefile b/lib/Makefile
1139 index 50144a3aeebd..603630df298d 100644
1140 --- a/lib/Makefile
1141 +++ b/lib/Makefile
1142 @@ -2,6 +2,16 @@
1143  # Makefile for some libs needed in the kernel.
1144  #
1145
1146 +ifdef CONFIG_JFFS2_ZLIB
1147 +       CONFIG_ZLIB_INFLATE:=y
1148 +       CONFIG_ZLIB_DEFLATE:=y
1149 +endif
1150 +
1151 +ifdef CONFIG_JFFS2_LZMA
1152 +       CONFIG_LZMA_DECOMPRESS:=y
1153 +       CONFIG_LZMA_COMPRESS:=y
1154 +endif
1155 +
1156  ifdef CONFIG_FUNCTION_TRACER
1157  ORIG_CFLAGS := $(KBUILD_CFLAGS)
1158  KBUILD_CFLAGS = $(subst $(CC_FLAGS_FTRACE),,$(ORIG_CFLAGS))
1159 @@ -108,6 +118,8 @@ obj-$(CONFIG_LZ4HC_COMPRESS) += lz4/
1160  obj-$(CONFIG_LZ4_DECOMPRESS) += lz4/
1161  obj-$(CONFIG_XZ_DEC) += xz/
1162  obj-$(CONFIG_RAID6_PQ) += raid6/
1163 +obj-$(CONFIG_LZMA_COMPRESS) += lzma/
1164 +obj-$(CONFIG_LZMA_DECOMPRESS) += lzma/
1165
1166  lib-$(CONFIG_DECOMPRESS_GZIP) += decompress_inflate.o
1167  lib-$(CONFIG_DECOMPRESS_BZIP2) += decompress_bunzip2.o
1168 diff --git a/lib/lzma/LzFind.c b/lib/lzma/LzFind.c
1169 new file mode 100644
1170 index 000000000000..e3ecb05420eb
1171 --- /dev/null
1172 +++ b/lib/lzma/LzFind.c
1173 @@ -0,0 +1,761 @@
1174 +/* LzFind.c -- Match finder for LZ algorithms
1175 +2009-04-22 : Igor Pavlov : Public domain */
1176 +
1177 +#include <string.h>
1178 +
1179 +#include "LzFind.h"
1180 +#include "LzHash.h"
1181 +
1182 +#define kEmptyHashValue 0
1183 +#define kMaxValForNormalize ((UInt32)0xFFFFFFFF)
1184 +#define kNormalizeStepMin (1 << 10) /* it must be power of 2 */
1185 +#define kNormalizeMask (~(kNormalizeStepMin - 1))
1186 +#define kMaxHistorySize ((UInt32)3 << 30)
1187 +
1188 +#define kStartMaxLen 3
1189 +
1190 +static void LzInWindow_Free(CMatchFinder *p, ISzAlloc *alloc)
1191 +{
1192 +  if (!p->directInput)
1193 +  {
1194 +    alloc->Free(alloc, p->bufferBase);
1195 +    p->bufferBase = 0;
1196 +  }
1197 +}
1198 +
1199 +/* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */
1200 +
1201 +static int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAlloc *alloc)
1202 +{
1203 +  UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;
1204 +  if (p->directInput)
1205 +  {
1206 +    p->blockSize = blockSize;
1207 +    return 1;
1208 +  }
1209 +  if (p->bufferBase == 0 || p->blockSize != blockSize)
1210 +  {
1211 +    LzInWindow_Free(p, alloc);
1212 +    p->blockSize = blockSize;
1213 +    p->bufferBase = (Byte *)alloc->Alloc(alloc, (size_t)blockSize);
1214 +  }
1215 +  return (p->bufferBase != 0);
1216 +}
1217 +
1218 +Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }
1219 +Byte MatchFinder_GetIndexByte(CMatchFinder *p, Int32 index) { return p->buffer[index]; }
1220 +
1221 +UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }
1222 +
1223 +void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)
1224 +{
1225 +  p->posLimit -= subValue;
1226 +  p->pos -= subValue;
1227 +  p->streamPos -= subValue;
1228 +}
1229 +
1230 +static void MatchFinder_ReadBlock(CMatchFinder *p)
1231 +{
1232 +  if (p->streamEndWasReached || p->result != SZ_OK)
1233 +    return;
1234 +  if (p->directInput)
1235 +  {
1236 +    UInt32 curSize = 0xFFFFFFFF - p->streamPos;
1237 +    if (curSize > p->directInputRem)
1238 +      curSize = (UInt32)p->directInputRem;
1239 +    p->directInputRem -= curSize;
1240 +    p->streamPos += curSize;
1241 +    if (p->directInputRem == 0)
1242 +      p->streamEndWasReached = 1;
1243 +    return;
1244 +  }
1245 +  for (;;)
1246 +  {
1247 +    Byte *dest = p->buffer + (p->streamPos - p->pos);
1248 +    size_t size = (p->bufferBase + p->blockSize - dest);
1249 +    if (size == 0)
1250 +      return;
1251 +    p->result = p->stream->Read(p->stream, dest, &size);
1252 +    if (p->result != SZ_OK)
1253 +      return;
1254 +    if (size == 0)
1255 +    {
1256 +      p->streamEndWasReached = 1;
1257 +      return;
1258 +    }
1259 +    p->streamPos += (UInt32)size;
1260 +    if (p->streamPos - p->pos > p->keepSizeAfter)
1261 +      return;
1262 +  }
1263 +}
1264 +
1265 +void MatchFinder_MoveBlock(CMatchFinder *p)
1266 +{
1267 +  memmove(p->bufferBase,
1268 +    p->buffer - p->keepSizeBefore,
1269 +    (size_t)(p->streamPos - p->pos + p->keepSizeBefore));
1270 +  p->buffer = p->bufferBase + p->keepSizeBefore;
1271 +}
1272 +
1273 +int MatchFinder_NeedMove(CMatchFinder *p)
1274 +{
1275 +  if (p->directInput)
1276 +    return 0;
1277 +  /* if (p->streamEndWasReached) return 0; */
1278 +  return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter);
1279 +}
1280 +
1281 +void MatchFinder_ReadIfRequired(CMatchFinder *p)
1282 +{
1283 +  if (p->streamEndWasReached)
1284 +    return;
1285 +  if (p->keepSizeAfter >= p->streamPos - p->pos)
1286 +    MatchFinder_ReadBlock(p);
1287 +}
1288 +
1289 +static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p)
1290 +{
1291 +  if (MatchFinder_NeedMove(p))
1292 +    MatchFinder_MoveBlock(p);
1293 +  MatchFinder_ReadBlock(p);
1294 +}
1295 +
1296 +static void MatchFinder_SetDefaultSettings(CMatchFinder *p)
1297 +{
1298 +  p->cutValue = 32;
1299 +  p->btMode = 1;
1300 +  p->numHashBytes = 4;
1301 +  p->bigHash = 0;
1302 +}
1303 +
1304 +#define kCrcPoly 0xEDB88320
1305 +
1306 +void MatchFinder_Construct(CMatchFinder *p)
1307 +{
1308 +  UInt32 i;
1309 +  p->bufferBase = 0;
1310 +  p->directInput = 0;
1311 +  p->hash = 0;
1312 +  MatchFinder_SetDefaultSettings(p);
1313 +
1314 +  for (i = 0; i < 256; i++)
1315 +  {
1316 +    UInt32 r = i;
1317 +    int j;
1318 +    for (j = 0; j < 8; j++)
1319 +      r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1));
1320 +    p->crc[i] = r;
1321 +  }
1322 +}
1323 +
1324 +static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc)
1325 +{
1326 +  alloc->Free(alloc, p->hash);
1327 +  p->hash = 0;
1328 +}
1329 +
1330 +void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc)
1331 +{
1332 +  MatchFinder_FreeThisClassMemory(p, alloc);
1333 +  LzInWindow_Free(p, alloc);
1334 +}
1335 +
1336 +static CLzRef* AllocRefs(UInt32 num, ISzAlloc *alloc)
1337 +{
1338 +  size_t sizeInBytes = (size_t)num * sizeof(CLzRef);
1339 +  if (sizeInBytes / sizeof(CLzRef) != num)
1340 +    return 0;
1341 +  return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);
1342 +}
1343 +
1344 +int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
1345 +    UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
1346 +    ISzAlloc *alloc)
1347 +{
1348 +  UInt32 sizeReserv;
1349 +  if (historySize > kMaxHistorySize)
1350 +  {
1351 +    MatchFinder_Free(p, alloc);
1352 +    return 0;
1353 +  }
1354 +  sizeReserv = historySize >> 1;
1355 +  if (historySize > ((UInt32)2 << 30))
1356 +    sizeReserv = historySize >> 2;
1357 +  sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);
1358 +
1359 +  p->keepSizeBefore = historySize + keepAddBufferBefore + 1;
1360 +  p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;
1361 +  /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */
1362 +  if (LzInWindow_Create(p, sizeReserv, alloc))
1363 +  {
1364 +    UInt32 newCyclicBufferSize = historySize + 1;
1365 +    UInt32 hs;
1366 +    p->matchMaxLen = matchMaxLen;
1367 +    {
1368 +      p->fixedHashSize = 0;
1369 +      if (p->numHashBytes == 2)
1370 +        hs = (1 << 16) - 1;
1371 +      else
1372 +      {
1373 +        hs = historySize - 1;
1374 +        hs |= (hs >> 1);
1375 +        hs |= (hs >> 2);
1376 +        hs |= (hs >> 4);
1377 +        hs |= (hs >> 8);
1378 +        hs >>= 1;
1379 +        hs |= 0xFFFF; /* don't change it! It's required for Deflate */
1380 +        if (hs > (1 << 24))
1381 +        {
1382 +          if (p->numHashBytes == 3)
1383 +            hs = (1 << 24) - 1;
1384 +          else
1385 +            hs >>= 1;
1386 +        }
1387 +      }
1388 +      p->hashMask = hs;
1389 +      hs++;
1390 +      if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;
1391 +      if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;
1392 +      if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;
1393 +      hs += p->fixedHashSize;
1394 +    }
1395 +
1396 +    {
1397 +      UInt32 prevSize = p->hashSizeSum + p->numSons;
1398 +      UInt32 newSize;
1399 +      p->historySize = historySize;
1400 +      p->hashSizeSum = hs;
1401 +      p->cyclicBufferSize = newCyclicBufferSize;
1402 +      p->numSons = (p->btMode ? newCyclicBufferSize * 2 : newCyclicBufferSize);
1403 +      newSize = p->hashSizeSum + p->numSons;
1404 +      if (p->hash != 0 && prevSize == newSize)
1405 +        return 1;
1406 +      MatchFinder_FreeThisClassMemory(p, alloc);
1407 +      p->hash = AllocRefs(newSize, alloc);
1408 +      if (p->hash != 0)
1409 +      {
1410 +        p->son = p->hash + p->hashSizeSum;
1411 +        return 1;
1412 +      }
1413 +    }
1414 +  }
1415 +  MatchFinder_Free(p, alloc);
1416 +  return 0;
1417 +}
1418 +
1419 +static void MatchFinder_SetLimits(CMatchFinder *p)
1420 +{
1421 +  UInt32 limit = kMaxValForNormalize - p->pos;
1422 +  UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;
1423 +  if (limit2 < limit)
1424 +    limit = limit2;
1425 +  limit2 = p->streamPos - p->pos;
1426 +  if (limit2 <= p->keepSizeAfter)
1427 +  {
1428 +    if (limit2 > 0)
1429 +      limit2 = 1;
1430 +  }
1431 +  else
1432 +    limit2 -= p->keepSizeAfter;
1433 +  if (limit2 < limit)
1434 +    limit = limit2;
1435 +  {
1436 +    UInt32 lenLimit = p->streamPos - p->pos;
1437 +    if (lenLimit > p->matchMaxLen)
1438 +      lenLimit = p->matchMaxLen;
1439 +    p->lenLimit = lenLimit;
1440 +  }
1441 +  p->posLimit = p->pos + limit;
1442 +}
1443 +
1444 +void MatchFinder_Init(CMatchFinder *p)
1445 +{
1446 +  UInt32 i;
1447 +  for (i = 0; i < p->hashSizeSum; i++)
1448 +    p->hash[i] = kEmptyHashValue;
1449 +  p->cyclicBufferPos = 0;
1450 +  p->buffer = p->bufferBase;
1451 +  p->pos = p->streamPos = p->cyclicBufferSize;
1452 +  p->result = SZ_OK;
1453 +  p->streamEndWasReached = 0;
1454 +  MatchFinder_ReadBlock(p);
1455 +  MatchFinder_SetLimits(p);
1456 +}
1457 +
1458 +static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)
1459 +{
1460 +  return (p->pos - p->historySize - 1) & kNormalizeMask;
1461 +}
1462 +
1463 +void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems)
1464 +{
1465 +  UInt32 i;
1466 +  for (i = 0; i < numItems; i++)
1467 +  {
1468 +    UInt32 value = items[i];
1469 +    if (value <= subValue)
1470 +      value = kEmptyHashValue;
1471 +    else
1472 +      value -= subValue;
1473 +    items[i] = value;
1474 +  }
1475 +}
1476 +
1477 +static void MatchFinder_Normalize(CMatchFinder *p)
1478 +{
1479 +  UInt32 subValue = MatchFinder_GetSubValue(p);
1480 +  MatchFinder_Normalize3(subValue, p->hash, p->hashSizeSum + p->numSons);
1481 +  MatchFinder_ReduceOffsets(p, subValue);
1482 +}
1483 +
1484 +static void MatchFinder_CheckLimits(CMatchFinder *p)
1485 +{
1486 +  if (p->pos == kMaxValForNormalize)
1487 +    MatchFinder_Normalize(p);
1488 +  if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)
1489 +    MatchFinder_CheckAndMoveAndRead(p);
1490 +  if (p->cyclicBufferPos == p->cyclicBufferSize)
1491 +    p->cyclicBufferPos = 0;
1492 +  MatchFinder_SetLimits(p);
1493 +}
1494 +
1495 +static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
1496 +    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
1497 +    UInt32 *distances, UInt32 maxLen)
1498 +{
1499 +  son[_cyclicBufferPos] = curMatch;
1500 +  for (;;)
1501 +  {
1502 +    UInt32 delta = pos - curMatch;
1503 +    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
1504 +      return distances;
1505 +    {
1506 +      const Byte *pb = cur - delta;
1507 +      curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
1508 +      if (pb[maxLen] == cur[maxLen] && *pb == *cur)
1509 +      {
1510 +        UInt32 len = 0;
1511 +        while (++len != lenLimit)
1512 +          if (pb[len] != cur[len])
1513 +            break;
1514 +        if (maxLen < len)
1515 +        {
1516 +          *distances++ = maxLen = len;
1517 +          *distances++ = delta - 1;
1518 +          if (len == lenLimit)
1519 +            return distances;
1520 +        }
1521 +      }
1522 +    }
1523 +  }
1524 +}
1525 +
1526 +UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
1527 +    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
1528 +    UInt32 *distances, UInt32 maxLen)
1529 +{
1530 +  CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
1531 +  CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
1532 +  UInt32 len0 = 0, len1 = 0;
1533 +  for (;;)
1534 +  {
1535 +    UInt32 delta = pos - curMatch;
1536 +    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
1537 +    {
1538 +      *ptr0 = *ptr1 = kEmptyHashValue;
1539 +      return distances;
1540 +    }
1541 +    {
1542 +      CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
1543 +      const Byte *pb = cur - delta;
1544 +      UInt32 len = (len0 < len1 ? len0 : len1);
1545 +      if (pb[len] == cur[len])
1546 +      {
1547 +        if (++len != lenLimit && pb[len] == cur[len])
1548 +          while (++len != lenLimit)
1549 +            if (pb[len] != cur[len])
1550 +              break;
1551 +        if (maxLen < len)
1552 +        {
1553 +          *distances++ = maxLen = len;
1554 +          *distances++ = delta - 1;
1555 +          if (len == lenLimit)
1556 +          {
1557 +            *ptr1 = pair[0];
1558 +            *ptr0 = pair[1];
1559 +            return distances;
1560 +          }
1561 +        }
1562 +      }
1563 +      if (pb[len] < cur[len])
1564 +      {
1565 +        *ptr1 = curMatch;
1566 +        ptr1 = pair + 1;
1567 +        curMatch = *ptr1;
1568 +        len1 = len;
1569 +      }
1570 +      else
1571 +      {
1572 +        *ptr0 = curMatch;
1573 +        ptr0 = pair;
1574 +        curMatch = *ptr0;
1575 +        len0 = len;
1576 +      }
1577 +    }
1578 +  }
1579 +}
1580 +
1581 +static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
1582 +    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)
1583 +{
1584 +  CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
1585 +  CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
1586 +  UInt32 len0 = 0, len1 = 0;
1587 +  for (;;)
1588 +  {
1589 +    UInt32 delta = pos - curMatch;
1590 +    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
1591 +    {
1592 +      *ptr0 = *ptr1 = kEmptyHashValue;
1593 +      return;
1594 +    }
1595 +    {
1596 +      CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
1597 +      const Byte *pb = cur - delta;
1598 +      UInt32 len = (len0 < len1 ? len0 : len1);
1599 +      if (pb[len] == cur[len])
1600 +      {
1601 +        while (++len != lenLimit)
1602 +          if (pb[len] != cur[len])
1603 +            break;
1604 +        {
1605 +          if (len == lenLimit)
1606 +          {
1607 +            *ptr1 = pair[0];
1608 +            *ptr0 = pair[1];
1609 +            return;
1610 +          }
1611 +        }
1612 +      }
1613 +      if (pb[len] < cur[len])
1614 +      {
1615 +        *ptr1 = curMatch;
1616 +        ptr1 = pair + 1;
1617 +        curMatch = *ptr1;
1618 +        len1 = len;
1619 +      }
1620 +      else
1621 +      {
1622 +        *ptr0 = curMatch;
1623 +        ptr0 = pair;
1624 +        curMatch = *ptr0;
1625 +        len0 = len;
1626 +      }
1627 +    }
1628 +  }
1629 +}
1630 +
1631 +#define MOVE_POS \
1632 +  ++p->cyclicBufferPos; \
1633 +  p->buffer++; \
1634 +  if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);
1635 +
1636 +#define MOVE_POS_RET MOVE_POS return offset;
1637 +
1638 +static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }
1639 +
1640 +#define GET_MATCHES_HEADER2(minLen, ret_op) \
1641 +  UInt32 lenLimit; UInt32 hashValue; const Byte *cur; UInt32 curMatch; \
1642 +  lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \
1643 +  cur = p->buffer;
1644 +
1645 +#define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)
1646 +#define SKIP_HEADER(minLen)        GET_MATCHES_HEADER2(minLen, continue)
1647 +
1648 +#define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue
1649 +
1650 +#define GET_MATCHES_FOOTER(offset, maxLen) \
1651 +  offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \
1652 +  distances + offset, maxLen) - distances); MOVE_POS_RET;
1653 +
1654 +#define SKIP_FOOTER \
1655 +  SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;
1656 +
1657 +static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
1658 +{
1659 +  UInt32 offset;
1660 +  GET_MATCHES_HEADER(2)
1661 +  HASH2_CALC;
1662 +  curMatch = p->hash[hashValue];
1663 +  p->hash[hashValue] = p->pos;
1664 +  offset = 0;
1665 +  GET_MATCHES_FOOTER(offset, 1)
1666 +}
1667 +
1668 +UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
1669 +{
1670 +  UInt32 offset;
1671 +  GET_MATCHES_HEADER(3)
1672 +  HASH_ZIP_CALC;
1673 +  curMatch = p->hash[hashValue];
1674 +  p->hash[hashValue] = p->pos;
1675 +  offset = 0;
1676 +  GET_MATCHES_FOOTER(offset, 2)
1677 +}
1678 +
1679 +static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
1680 +{
1681 +  UInt32 hash2Value, delta2, maxLen, offset;
1682 +  GET_MATCHES_HEADER(3)
1683 +
1684 +  HASH3_CALC;
1685 +
1686 +  delta2 = p->pos - p->hash[hash2Value];
1687 +  curMatch = p->hash[kFix3HashSize + hashValue];
1688 +
1689 +  p->hash[hash2Value] =
1690 +  p->hash[kFix3HashSize + hashValue] = p->pos;
1691 +
1692 +
1693 +  maxLen = 2;
1694 +  offset = 0;
1695 +  if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
1696 +  {
1697 +    for (; maxLen != lenLimit; maxLen++)
1698 +      if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
1699 +        break;
1700 +    distances[0] = maxLen;
1701 +    distances[1] = delta2 - 1;
1702 +    offset = 2;
1703 +    if (maxLen == lenLimit)
1704 +    {
1705 +      SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
1706 +      MOVE_POS_RET;
1707 +    }
1708 +  }
1709 +  GET_MATCHES_FOOTER(offset, maxLen)
1710 +}
1711 +
1712 +static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
1713 +{
1714 +  UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
1715 +  GET_MATCHES_HEADER(4)
1716 +
1717 +  HASH4_CALC;
1718 +
1719 +  delta2 = p->pos - p->hash[                hash2Value];
1720 +  delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
1721 +  curMatch = p->hash[kFix4HashSize + hashValue];
1722 +
1723 +  p->hash[                hash2Value] =
1724 +  p->hash[kFix3HashSize + hash3Value] =
1725 +  p->hash[kFix4HashSize + hashValue] = p->pos;
1726 +
1727 +  maxLen = 1;
1728 +  offset = 0;
1729 +  if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
1730 +  {
1731 +    distances[0] = maxLen = 2;
1732 +    distances[1] = delta2 - 1;
1733 +    offset = 2;
1734 +  }
1735 +  if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
1736 +  {
1737 +    maxLen = 3;
1738 +    distances[offset + 1] = delta3 - 1;
1739 +    offset += 2;
1740 +    delta2 = delta3;
1741 +  }
1742 +  if (offset != 0)
1743 +  {
1744 +    for (; maxLen != lenLimit; maxLen++)
1745 +      if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
1746 +        break;
1747 +    distances[offset - 2] = maxLen;
1748 +    if (maxLen == lenLimit)
1749 +    {
1750 +      SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
1751 +      MOVE_POS_RET;
1752 +    }
1753 +  }
1754 +  if (maxLen < 3)
1755 +    maxLen = 3;
1756 +  GET_MATCHES_FOOTER(offset, maxLen)
1757 +}
1758 +
1759 +static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
1760 +{
1761 +  UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
1762 +  GET_MATCHES_HEADER(4)
1763 +
1764 +  HASH4_CALC;
1765 +
1766 +  delta2 = p->pos - p->hash[                hash2Value];
1767 +  delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
1768 +  curMatch = p->hash[kFix4HashSize + hashValue];
1769 +
1770 +  p->hash[                hash2Value] =
1771 +  p->hash[kFix3HashSize + hash3Value] =
1772 +  p->hash[kFix4HashSize + hashValue] = p->pos;
1773 +
1774 +  maxLen = 1;
1775 +  offset = 0;
1776 +  if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
1777 +  {
1778 +    distances[0] = maxLen = 2;
1779 +    distances[1] = delta2 - 1;
1780 +    offset = 2;
1781 +  }
1782 +  if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
1783 +  {
1784 +    maxLen = 3;
1785 +    distances[offset + 1] = delta3 - 1;
1786 +    offset += 2;
1787 +    delta2 = delta3;
1788 +  }
1789 +  if (offset != 0)
1790 +  {
1791 +    for (; maxLen != lenLimit; maxLen++)
1792 +      if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
1793 +        break;
1794 +    distances[offset - 2] = maxLen;
1795 +    if (maxLen == lenLimit)
1796 +    {
1797 +      p->son[p->cyclicBufferPos] = curMatch;
1798 +      MOVE_POS_RET;
1799 +    }
1800 +  }
1801 +  if (maxLen < 3)
1802 +    maxLen = 3;
1803 +  offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
1804 +    distances + offset, maxLen) - (distances));
1805 +  MOVE_POS_RET
1806 +}
1807 +
1808 +UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
1809 +{
1810 +  UInt32 offset;
1811 +  GET_MATCHES_HEADER(3)
1812 +  HASH_ZIP_CALC;
1813 +  curMatch = p->hash[hashValue];
1814 +  p->hash[hashValue] = p->pos;
1815 +  offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
1816 +    distances, 2) - (distances));
1817 +  MOVE_POS_RET
1818 +}
1819 +
1820 +static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1821 +{
1822 +  do
1823 +  {
1824 +    SKIP_HEADER(2)
1825 +    HASH2_CALC;
1826 +    curMatch = p->hash[hashValue];
1827 +    p->hash[hashValue] = p->pos;
1828 +    SKIP_FOOTER
1829 +  }
1830 +  while (--num != 0);
1831 +}
1832 +
1833 +void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1834 +{
1835 +  do
1836 +  {
1837 +    SKIP_HEADER(3)
1838 +    HASH_ZIP_CALC;
1839 +    curMatch = p->hash[hashValue];
1840 +    p->hash[hashValue] = p->pos;
1841 +    SKIP_FOOTER
1842 +  }
1843 +  while (--num != 0);
1844 +}
1845 +
1846 +static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1847 +{
1848 +  do
1849 +  {
1850 +    UInt32 hash2Value;
1851 +    SKIP_HEADER(3)
1852 +    HASH3_CALC;
1853 +    curMatch = p->hash[kFix3HashSize + hashValue];
1854 +    p->hash[hash2Value] =
1855 +    p->hash[kFix3HashSize + hashValue] = p->pos;
1856 +    SKIP_FOOTER
1857 +  }
1858 +  while (--num != 0);
1859 +}
1860 +
1861 +static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1862 +{
1863 +  do
1864 +  {
1865 +    UInt32 hash2Value, hash3Value;
1866 +    SKIP_HEADER(4)
1867 +    HASH4_CALC;
1868 +    curMatch = p->hash[kFix4HashSize + hashValue];
1869 +    p->hash[                hash2Value] =
1870 +    p->hash[kFix3HashSize + hash3Value] = p->pos;
1871 +    p->hash[kFix4HashSize + hashValue] = p->pos;
1872 +    SKIP_FOOTER
1873 +  }
1874 +  while (--num != 0);
1875 +}
1876 +
1877 +static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1878 +{
1879 +  do
1880 +  {
1881 +    UInt32 hash2Value, hash3Value;
1882 +    SKIP_HEADER(4)
1883 +    HASH4_CALC;
1884 +    curMatch = p->hash[kFix4HashSize + hashValue];
1885 +    p->hash[                hash2Value] =
1886 +    p->hash[kFix3HashSize + hash3Value] =
1887 +    p->hash[kFix4HashSize + hashValue] = p->pos;
1888 +    p->son[p->cyclicBufferPos] = curMatch;
1889 +    MOVE_POS
1890 +  }
1891 +  while (--num != 0);
1892 +}
1893 +
1894 +void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1895 +{
1896 +  do
1897 +  {
1898 +    SKIP_HEADER(3)
1899 +    HASH_ZIP_CALC;
1900 +    curMatch = p->hash[hashValue];
1901 +    p->hash[hashValue] = p->pos;
1902 +    p->son[p->cyclicBufferPos] = curMatch;
1903 +    MOVE_POS
1904 +  }
1905 +  while (--num != 0);
1906 +}
1907 +
1908 +void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)
1909 +{
1910 +  vTable->Init = (Mf_Init_Func)MatchFinder_Init;
1911 +  vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinder_GetIndexByte;
1912 +  vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;
1913 +  vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
1914 +  if (!p->btMode)
1915 +  {
1916 +    vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;
1917 +    vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;
1918 +  }
1919 +  else if (p->numHashBytes == 2)
1920 +  {
1921 +    vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;
1922 +    vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;
1923 +  }
1924 +  else if (p->numHashBytes == 3)
1925 +  {
1926 +    vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;
1927 +    vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;
1928 +  }
1929 +  else
1930 +  {
1931 +    vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;
1932 +    vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;
1933 +  }
1934 +}
1935 diff --git a/lib/lzma/LzmaDec.c b/lib/lzma/LzmaDec.c
1936 new file mode 100644
1937 index 000000000000..2036761bf146
1938 --- /dev/null
1939 +++ b/lib/lzma/LzmaDec.c
1940 @@ -0,0 +1,999 @@
1941 +/* LzmaDec.c -- LZMA Decoder
1942 +2009-09-20 : Igor Pavlov : Public domain */
1943 +
1944 +#include "LzmaDec.h"
1945 +
1946 +#include <string.h>
1947 +
1948 +#define kNumTopBits 24
1949 +#define kTopValue ((UInt32)1 << kNumTopBits)
1950 +
1951 +#define kNumBitModelTotalBits 11
1952 +#define kBitModelTotal (1 << kNumBitModelTotalBits)
1953 +#define kNumMoveBits 5
1954 +
1955 +#define RC_INIT_SIZE 5
1956 +
1957 +#define NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | (*buf++); }
1958 +
1959 +#define IF_BIT_0(p) ttt = *(p); NORMALIZE; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)
1960 +#define UPDATE_0(p) range = bound; *(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));
1961 +#define UPDATE_1(p) range -= bound; code -= bound; *(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits));
1962 +#define GET_BIT2(p, i, A0, A1) IF_BIT_0(p) \
1963 +  { UPDATE_0(p); i = (i + i); A0; } else \
1964 +  { UPDATE_1(p); i = (i + i) + 1; A1; }
1965 +#define GET_BIT(p, i) GET_BIT2(p, i, ; , ;)
1966 +
1967 +#define TREE_GET_BIT(probs, i) { GET_BIT((probs + i), i); }
1968 +#define TREE_DECODE(probs, limit, i) \
1969 +  { i = 1; do { TREE_GET_BIT(probs, i); } while (i < limit); i -= limit; }
1970 +
1971 +/* #define _LZMA_SIZE_OPT */
1972 +
1973 +#ifdef _LZMA_SIZE_OPT
1974 +#define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i)
1975 +#else
1976 +#define TREE_6_DECODE(probs, i) \
1977 +  { i = 1; \
1978 +  TREE_GET_BIT(probs, i); \
1979 +  TREE_GET_BIT(probs, i); \
1980 +  TREE_GET_BIT(probs, i); \
1981 +  TREE_GET_BIT(probs, i); \
1982 +  TREE_GET_BIT(probs, i); \
1983 +  TREE_GET_BIT(probs, i); \
1984 +  i -= 0x40; }
1985 +#endif
1986 +
1987 +#define NORMALIZE_CHECK if (range < kTopValue) { if (buf >= bufLimit) return DUMMY_ERROR; range <<= 8; code = (code << 8) | (*buf++); }
1988 +
1989 +#define IF_BIT_0_CHECK(p) ttt = *(p); NORMALIZE_CHECK; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)
1990 +#define UPDATE_0_CHECK range = bound;
1991 +#define UPDATE_1_CHECK range -= bound; code -= bound;
1992 +#define GET_BIT2_CHECK(p, i, A0, A1) IF_BIT_0_CHECK(p) \
1993 +  { UPDATE_0_CHECK; i = (i + i); A0; } else \
1994 +  { UPDATE_1_CHECK; i = (i + i) + 1; A1; }
1995 +#define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ; , ;)
1996 +#define TREE_DECODE_CHECK(probs, limit, i) \
1997 +  { i = 1; do { GET_BIT_CHECK(probs + i, i) } while (i < limit); i -= limit; }
1998 +
1999 +
2000 +#define kNumPosBitsMax 4
2001 +#define kNumPosStatesMax (1 << kNumPosBitsMax)
2002 +
2003 +#define kLenNumLowBits 3
2004 +#define kLenNumLowSymbols (1 << kLenNumLowBits)
2005 +#define kLenNumMidBits 3
2006 +#define kLenNumMidSymbols (1 << kLenNumMidBits)
2007 +#define kLenNumHighBits 8
2008 +#define kLenNumHighSymbols (1 << kLenNumHighBits)
2009 +
2010 +#define LenChoice 0
2011 +#define LenChoice2 (LenChoice + 1)
2012 +#define LenLow (LenChoice2 + 1)
2013 +#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
2014 +#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
2015 +#define kNumLenProbs (LenHigh + kLenNumHighSymbols)
2016 +
2017 +
2018 +#define kNumStates 12
2019 +#define kNumLitStates 7
2020 +
2021 +#define kStartPosModelIndex 4
2022 +#define kEndPosModelIndex 14
2023 +#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
2024 +
2025 +#define kNumPosSlotBits 6
2026 +#define kNumLenToPosStates 4
2027 +
2028 +#define kNumAlignBits 4
2029 +#define kAlignTableSize (1 << kNumAlignBits)
2030 +
2031 +#define kMatchMinLen 2
2032 +#define kMatchSpecLenStart (kMatchMinLen + kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)
2033 +
2034 +#define IsMatch 0
2035 +#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
2036 +#define IsRepG0 (IsRep + kNumStates)
2037 +#define IsRepG1 (IsRepG0 + kNumStates)
2038 +#define IsRepG2 (IsRepG1 + kNumStates)
2039 +#define IsRep0Long (IsRepG2 + kNumStates)
2040 +#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
2041 +#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
2042 +#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
2043 +#define LenCoder (Align + kAlignTableSize)
2044 +#define RepLenCoder (LenCoder + kNumLenProbs)
2045 +#define Literal (RepLenCoder + kNumLenProbs)
2046 +
2047 +#define LZMA_BASE_SIZE 1846
2048 +#define LZMA_LIT_SIZE 768
2049 +
2050 +#define LzmaProps_GetNumProbs(p) ((UInt32)LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))
2051 +
2052 +#if Literal != LZMA_BASE_SIZE
2053 +StopCompilingDueBUG
2054 +#endif
2055 +
2056 +#define LZMA_DIC_MIN (1 << 12)
2057 +
2058 +/* First LZMA-symbol is always decoded.
2059 +And it decodes new LZMA-symbols while (buf < bufLimit), but "buf" is without last normalization
2060 +Out:
2061 +  Result:
2062 +    SZ_OK - OK
2063 +    SZ_ERROR_DATA - Error
2064 +  p->remainLen:
2065 +    < kMatchSpecLenStart : normal remain
2066 +    = kMatchSpecLenStart : finished
2067 +    = kMatchSpecLenStart + 1 : Flush marker
2068 +    = kMatchSpecLenStart + 2 : State Init Marker
2069 +*/
2070 +
2071 +static int MY_FAST_CALL LzmaDec_DecodeReal(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
2072 +{
2073 +  CLzmaProb *probs = p->probs;
2074 +
2075 +  unsigned state = p->state;
2076 +  UInt32 rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3];
2077 +  unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1;
2078 +  unsigned lpMask = ((unsigned)1 << (p->prop.lp)) - 1;
2079 +  unsigned lc = p->prop.lc;
2080 +
2081 +  Byte *dic = p->dic;
2082 +  SizeT dicBufSize = p->dicBufSize;
2083 +  SizeT dicPos = p->dicPos;
2084 +
2085 +  UInt32 processedPos = p->processedPos;
2086 +  UInt32 checkDicSize = p->checkDicSize;
2087 +  unsigned len = 0;
2088 +
2089 +  const Byte *buf = p->buf;
2090 +  UInt32 range = p->range;
2091 +  UInt32 code = p->code;
2092 +
2093 +  do
2094 +  {
2095 +    CLzmaProb *prob;
2096 +    UInt32 bound;
2097 +    unsigned ttt;
2098 +    unsigned posState = processedPos & pbMask;
2099 +
2100 +    prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
2101 +    IF_BIT_0(prob)
2102 +    {
2103 +      unsigned symbol;
2104 +      UPDATE_0(prob);
2105 +      prob = probs + Literal;
2106 +      if (checkDicSize != 0 || processedPos != 0)
2107 +        prob += (LZMA_LIT_SIZE * (((processedPos & lpMask) << lc) +
2108 +        (dic[(dicPos == 0 ? dicBufSize : dicPos) - 1] >> (8 - lc))));
2109 +
2110 +      if (state < kNumLitStates)
2111 +      {
2112 +        state -= (state < 4) ? state : 3;
2113 +        symbol = 1;
2114 +        do { GET_BIT(prob + symbol, symbol) } while (symbol < 0x100);
2115 +      }
2116 +      else
2117 +      {
2118 +        unsigned matchByte = p->dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
2119 +        unsigned offs = 0x100;
2120 +        state -= (state < 10) ? 3 : 6;
2121 +        symbol = 1;
2122 +        do
2123 +        {
2124 +          unsigned bit;
2125 +          CLzmaProb *probLit;
2126 +          matchByte <<= 1;
2127 +          bit = (matchByte & offs);
2128 +          probLit = prob + offs + bit + symbol;
2129 +          GET_BIT2(probLit, symbol, offs &= ~bit, offs &= bit)
2130 +        }
2131 +        while (symbol < 0x100);
2132 +      }
2133 +      dic[dicPos++] = (Byte)symbol;
2134 +      processedPos++;
2135 +      continue;
2136 +    }
2137 +    else
2138 +    {
2139 +      UPDATE_1(prob);
2140 +      prob = probs + IsRep + state;
2141 +      IF_BIT_0(prob)
2142 +      {
2143 +        UPDATE_0(prob);
2144 +        state += kNumStates;
2145 +        prob = probs + LenCoder;
2146 +      }
2147 +      else
2148 +      {
2149 +        UPDATE_1(prob);
2150 +        if (checkDicSize == 0 && processedPos == 0)
2151 +          return SZ_ERROR_DATA;
2152 +        prob = probs + IsRepG0 + state;
2153 +        IF_BIT_0(prob)
2154 +        {
2155 +          UPDATE_0(prob);
2156 +          prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
2157 +          IF_BIT_0(prob)
2158 +          {
2159 +            UPDATE_0(prob);
2160 +            dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
2161 +            dicPos++;
2162 +            processedPos++;
2163 +            state = state < kNumLitStates ? 9 : 11;
2164 +            continue;
2165 +          }
2166 +          UPDATE_1(prob);
2167 +        }
2168 +        else
2169 +        {
2170 +          UInt32 distance;
2171 +          UPDATE_1(prob);
2172 +          prob = probs + IsRepG1 + state;
2173 +          IF_BIT_0(prob)
2174 +          {
2175 +            UPDATE_0(prob);
2176 +            distance = rep1;
2177 +          }
2178 +          else
2179 +          {
2180 +            UPDATE_1(prob);
2181 +            prob = probs + IsRepG2 + state;
2182 +            IF_BIT_0(prob)
2183 +            {
2184 +              UPDATE_0(prob);
2185 +              distance = rep2;
2186 +            }
2187 +            else
2188 +            {
2189 +              UPDATE_1(prob);
2190 +              distance = rep3;
2191 +              rep3 = rep2;
2192 +            }
2193 +            rep2 = rep1;
2194 +          }
2195 +          rep1 = rep0;
2196 +          rep0 = distance;
2197 +        }
2198 +        state = state < kNumLitStates ? 8 : 11;
2199 +        prob = probs + RepLenCoder;
2200 +      }
2201 +      {
2202 +        unsigned limit, offset;
2203 +        CLzmaProb *probLen = prob + LenChoice;
2204 +        IF_BIT_0(probLen)
2205 +        {
2206 +          UPDATE_0(probLen);
2207 +          probLen = prob + LenLow + (posState << kLenNumLowBits);
2208 +          offset = 0;
2209 +          limit = (1 << kLenNumLowBits);
2210 +        }
2211 +        else
2212 +        {
2213 +          UPDATE_1(probLen);
2214 +          probLen = prob + LenChoice2;
2215 +          IF_BIT_0(probLen)
2216 +          {
2217 +            UPDATE_0(probLen);
2218 +            probLen = prob + LenMid + (posState << kLenNumMidBits);
2219 +            offset = kLenNumLowSymbols;
2220 +            limit = (1 << kLenNumMidBits);
2221 +          }
2222 +          else
2223 +          {
2224 +            UPDATE_1(probLen);
2225 +            probLen = prob + LenHigh;
2226 +            offset = kLenNumLowSymbols + kLenNumMidSymbols;
2227 +            limit = (1 << kLenNumHighBits);
2228 +          }
2229 +        }
2230 +        TREE_DECODE(probLen, limit, len);
2231 +        len += offset;
2232 +      }
2233 +
2234 +      if (state >= kNumStates)
2235 +      {
2236 +        UInt32 distance;
2237 +        prob = probs + PosSlot +
2238 +            ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits);
2239 +        TREE_6_DECODE(prob, distance);
2240 +        if (distance >= kStartPosModelIndex)
2241 +        {
2242 +          unsigned posSlot = (unsigned)distance;
2243 +          int numDirectBits = (int)(((distance >> 1) - 1));
2244 +          distance = (2 | (distance & 1));
2245 +          if (posSlot < kEndPosModelIndex)
2246 +          {
2247 +            distance <<= numDirectBits;
2248 +            prob = probs + SpecPos + distance - posSlot - 1;
2249 +            {
2250 +              UInt32 mask = 1;
2251 +              unsigned i = 1;
2252 +              do
2253 +              {
2254 +                GET_BIT2(prob + i, i, ; , distance |= mask);
2255 +                mask <<= 1;
2256 +              }
2257 +              while (--numDirectBits != 0);
2258 +            }
2259 +          }
2260 +          else
2261 +          {
2262 +            numDirectBits -= kNumAlignBits;
2263 +            do
2264 +            {
2265 +              NORMALIZE
2266 +              range >>= 1;
2267 +
2268 +              {
2269 +                UInt32 t;
2270 +                code -= range;
2271 +                t = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */
2272 +                distance = (distance << 1) + (t + 1);
2273 +                code += range & t;
2274 +              }
2275 +              /*
2276 +              distance <<= 1;
2277 +              if (code >= range)
2278 +              {
2279 +                code -= range;
2280 +                distance |= 1;
2281 +              }
2282 +              */
2283 +            }
2284 +            while (--numDirectBits != 0);
2285 +            prob = probs + Align;
2286 +            distance <<= kNumAlignBits;
2287 +            {
2288 +              unsigned i = 1;
2289 +              GET_BIT2(prob + i, i, ; , distance |= 1);
2290 +              GET_BIT2(prob + i, i, ; , distance |= 2);
2291 +              GET_BIT2(prob + i, i, ; , distance |= 4);
2292 +              GET_BIT2(prob + i, i, ; , distance |= 8);
2293 +            }
2294 +            if (distance == (UInt32)0xFFFFFFFF)
2295 +            {
2296 +              len += kMatchSpecLenStart;
2297 +              state -= kNumStates;
2298 +              break;
2299 +            }
2300 +          }
2301 +        }
2302 +        rep3 = rep2;
2303 +        rep2 = rep1;
2304 +        rep1 = rep0;
2305 +        rep0 = distance + 1;
2306 +        if (checkDicSize == 0)
2307 +        {
2308 +          if (distance >= processedPos)
2309 +            return SZ_ERROR_DATA;
2310 +        }
2311 +        else if (distance >= checkDicSize)
2312 +          return SZ_ERROR_DATA;
2313 +        state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3;
2314 +      }
2315 +
2316 +      len += kMatchMinLen;
2317 +
2318 +      if (limit == dicPos)
2319 +        return SZ_ERROR_DATA;
2320 +      {
2321 +        SizeT rem = limit - dicPos;
2322 +        unsigned curLen = ((rem < len) ? (unsigned)rem : len);
2323 +        SizeT pos = (dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0);
2324 +
2325 +        processedPos += curLen;
2326 +
2327 +        len -= curLen;
2328 +        if (pos + curLen <= dicBufSize)
2329 +        {
2330 +          Byte *dest = dic + dicPos;
2331 +          ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos;
2332 +          const Byte *lim = dest + curLen;
2333 +          dicPos += curLen;
2334 +          do
2335 +            *(dest) = (Byte)*(dest + src);
2336 +          while (++dest != lim);
2337 +        }
2338 +        else
2339 +        {
2340 +          do
2341 +          {
2342 +            dic[dicPos++] = dic[pos];
2343 +            if (++pos == dicBufSize)
2344 +              pos = 0;
2345 +          }
2346 +          while (--curLen != 0);
2347 +        }
2348 +      }
2349 +    }
2350 +  }
2351 +  while (dicPos < limit && buf < bufLimit);
2352 +  NORMALIZE;
2353 +  p->buf = buf;
2354 +  p->range = range;
2355 +  p->code = code;
2356 +  p->remainLen = len;
2357 +  p->dicPos = dicPos;
2358 +  p->processedPos = processedPos;
2359 +  p->reps[0] = rep0;
2360 +  p->reps[1] = rep1;
2361 +  p->reps[2] = rep2;
2362 +  p->reps[3] = rep3;
2363 +  p->state = state;
2364 +
2365 +  return SZ_OK;
2366 +}
2367 +
2368 +static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit)
2369 +{
2370 +  if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart)
2371 +  {
2372 +    Byte *dic = p->dic;
2373 +    SizeT dicPos = p->dicPos;
2374 +    SizeT dicBufSize = p->dicBufSize;
2375 +    unsigned len = p->remainLen;
2376 +    UInt32 rep0 = p->reps[0];
2377 +    if (limit - dicPos < len)
2378 +      len = (unsigned)(limit - dicPos);
2379 +
2380 +    if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len)
2381 +      p->checkDicSize = p->prop.dicSize;
2382 +
2383 +    p->processedPos += len;
2384 +    p->remainLen -= len;
2385 +    while (len-- != 0)
2386 +    {
2387 +      dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
2388 +      dicPos++;
2389 +    }
2390 +    p->dicPos = dicPos;
2391 +  }
2392 +}
2393 +
2394 +static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
2395 +{
2396 +  do
2397 +  {
2398 +    SizeT limit2 = limit;
2399 +    if (p->checkDicSize == 0)
2400 +    {
2401 +      UInt32 rem = p->prop.dicSize - p->processedPos;
2402 +      if (limit - p->dicPos > rem)
2403 +        limit2 = p->dicPos + rem;
2404 +    }
2405 +    RINOK(LzmaDec_DecodeReal(p, limit2, bufLimit));
2406 +    if (p->processedPos >= p->prop.dicSize)
2407 +      p->checkDicSize = p->prop.dicSize;
2408 +    LzmaDec_WriteRem(p, limit);
2409 +  }
2410 +  while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart);
2411 +
2412 +  if (p->remainLen > kMatchSpecLenStart)
2413 +  {
2414 +    p->remainLen = kMatchSpecLenStart;
2415 +  }
2416 +  return 0;
2417 +}
2418 +
2419 +typedef enum
2420 +{
2421 +  DUMMY_ERROR, /* unexpected end of input stream */
2422 +  DUMMY_LIT,
2423 +  DUMMY_MATCH,
2424 +  DUMMY_REP
2425 +} ELzmaDummy;
2426 +
2427 +static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, SizeT inSize)
2428 +{
2429 +  UInt32 range = p->range;
2430 +  UInt32 code = p->code;
2431 +  const Byte *bufLimit = buf + inSize;
2432 +  CLzmaProb *probs = p->probs;
2433 +  unsigned state = p->state;
2434 +  ELzmaDummy res;
2435 +
2436 +  {
2437 +    CLzmaProb *prob;
2438 +    UInt32 bound;
2439 +    unsigned ttt;
2440 +    unsigned posState = (p->processedPos) & ((1 << p->prop.pb) - 1);
2441 +
2442 +    prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
2443 +    IF_BIT_0_CHECK(prob)
2444 +    {
2445 +      UPDATE_0_CHECK
2446 +
2447 +      /* if (bufLimit - buf >= 7) return DUMMY_LIT; */
2448 +
2449 +      prob = probs + Literal;
2450 +      if (p->checkDicSize != 0 || p->processedPos != 0)
2451 +        prob += (LZMA_LIT_SIZE *
2452 +          ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) +
2453 +          (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc))));
2454 +
2455 +      if (state < kNumLitStates)
2456 +      {
2457 +        unsigned symbol = 1;
2458 +        do { GET_BIT_CHECK(prob + symbol, symbol) } while (symbol < 0x100);
2459 +      }
2460 +      else
2461 +      {
2462 +        unsigned matchByte = p->dic[p->dicPos - p->reps[0] +
2463 +            ((p->dicPos < p->reps[0]) ? p->dicBufSize : 0)];
2464 +        unsigned offs = 0x100;
2465 +        unsigned symbol = 1;
2466 +        do
2467 +        {
2468 +          unsigned bit;
2469 +          CLzmaProb *probLit;
2470 +          matchByte <<= 1;
2471 +          bit = (matchByte & offs);
2472 +          probLit = prob + offs + bit + symbol;
2473 +          GET_BIT2_CHECK(probLit, symbol, offs &= ~bit, offs &= bit)
2474 +        }
2475 +        while (symbol < 0x100);
2476 +      }
2477 +      res = DUMMY_LIT;
2478 +    }
2479 +    else
2480 +    {
2481 +      unsigned len;
2482 +      UPDATE_1_CHECK;
2483 +
2484 +      prob = probs + IsRep + state;
2485 +      IF_BIT_0_CHECK(prob)
2486 +      {
2487 +        UPDATE_0_CHECK;
2488 +        state = 0;
2489 +        prob = probs + LenCoder;
2490 +        res = DUMMY_MATCH;
2491 +      }
2492 +      else
2493 +      {
2494 +        UPDATE_1_CHECK;
2495 +        res = DUMMY_REP;
2496 +        prob = probs + IsRepG0 + state;
2497 +        IF_BIT_0_CHECK(prob)
2498 +        {
2499 +          UPDATE_0_CHECK;
2500 +          prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
2501 +          IF_BIT_0_CHECK(prob)
2502 +          {
2503 +            UPDATE_0_CHECK;
2504 +            NORMALIZE_CHECK;
2505 +            return DUMMY_REP;
2506 +          }
2507 +          else
2508 +          {
2509 +            UPDATE_1_CHECK;
2510 +          }
2511 +        }
2512 +        else
2513 +        {
2514 +          UPDATE_1_CHECK;
2515 +          prob = probs + IsRepG1 + state;
2516 +          IF_BIT_0_CHECK(prob)
2517 +          {
2518 +            UPDATE_0_CHECK;
2519 +          }
2520 +          else
2521 +          {
2522 +            UPDATE_1_CHECK;
2523 +            prob = probs + IsRepG2 + state;
2524 +            IF_BIT_0_CHECK(prob)
2525 +            {
2526 +              UPDATE_0_CHECK;
2527 +            }
2528 +            else
2529 +            {
2530 +              UPDATE_1_CHECK;
2531 +            }
2532 +          }
2533 +        }
2534 +        state = kNumStates;
2535 +        prob = probs + RepLenCoder;
2536 +      }
2537 +      {
2538 +        unsigned limit, offset;
2539 +        CLzmaProb *probLen = prob + LenChoice;
2540 +        IF_BIT_0_CHECK(probLen)
2541 +        {
2542 +          UPDATE_0_CHECK;
2543 +          probLen = prob + LenLow + (posState << kLenNumLowBits);
2544 +          offset = 0;
2545 +          limit = 1 << kLenNumLowBits;
2546 +        }
2547 +        else
2548 +        {
2549 +          UPDATE_1_CHECK;
2550 +          probLen = prob + LenChoice2;
2551 +          IF_BIT_0_CHECK(probLen)
2552 +          {
2553 +            UPDATE_0_CHECK;
2554 +            probLen = prob + LenMid + (posState << kLenNumMidBits);
2555 +            offset = kLenNumLowSymbols;
2556 +            limit = 1 << kLenNumMidBits;
2557 +          }
2558 +          else
2559 +          {
2560 +            UPDATE_1_CHECK;
2561 +            probLen = prob + LenHigh;
2562 +            offset = kLenNumLowSymbols + kLenNumMidSymbols;
2563 +            limit = 1 << kLenNumHighBits;
2564 +          }
2565 +        }
2566 +        TREE_DECODE_CHECK(probLen, limit, len);
2567 +        len += offset;
2568 +      }
2569 +
2570 +      if (state < 4)
2571 +      {
2572 +        unsigned posSlot;
2573 +        prob = probs + PosSlot +
2574 +            ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
2575 +            kNumPosSlotBits);
2576 +        TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot);
2577 +        if (posSlot >= kStartPosModelIndex)
2578 +        {
2579 +          int numDirectBits = ((posSlot >> 1) - 1);
2580 +
2581 +          /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */
2582 +
2583 +          if (posSlot < kEndPosModelIndex)
2584 +          {
2585 +            prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits) - posSlot - 1;
2586 +          }
2587 +          else
2588 +          {
2589 +            numDirectBits -= kNumAlignBits;
2590 +            do
2591 +            {
2592 +              NORMALIZE_CHECK
2593 +              range >>= 1;
2594 +              code -= range & (((code - range) >> 31) - 1);
2595 +              /* if (code >= range) code -= range; */
2596 +            }
2597 +            while (--numDirectBits != 0);
2598 +            prob = probs + Align;
2599 +            numDirectBits = kNumAlignBits;
2600 +          }
2601 +          {
2602 +            unsigned i = 1;
2603 +            do
2604 +            {
2605 +              GET_BIT_CHECK(prob + i, i);
2606 +            }
2607 +            while (--numDirectBits != 0);
2608 +          }
2609 +        }
2610 +      }
2611 +    }
2612 +  }
2613 +  NORMALIZE_CHECK;
2614 +  return res;
2615 +}
2616 +
2617 +
2618 +static void LzmaDec_InitRc(CLzmaDec *p, const Byte *data)
2619 +{
2620 +  p->code = ((UInt32)data[1] << 24) | ((UInt32)data[2] << 16) | ((UInt32)data[3] << 8) | ((UInt32)data[4]);
2621 +  p->range = 0xFFFFFFFF;
2622 +  p->needFlush = 0;
2623 +}
2624 +
2625 +void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState)
2626 +{
2627 +  p->needFlush = 1;
2628 +  p->remainLen = 0;
2629 +  p->tempBufSize = 0;
2630 +
2631 +  if (initDic)
2632 +  {
2633 +    p->processedPos = 0;
2634 +    p->checkDicSize = 0;
2635 +    p->needInitState = 1;
2636 +  }
2637 +  if (initState)
2638 +    p->needInitState = 1;
2639 +}
2640 +
2641 +void LzmaDec_Init(CLzmaDec *p)
2642 +{
2643 +  p->dicPos = 0;
2644 +  LzmaDec_InitDicAndState(p, True, True);
2645 +}
2646 +
2647 +static void LzmaDec_InitStateReal(CLzmaDec *p)
2648 +{
2649 +  UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (p->prop.lc + p->prop.lp));
2650 +  UInt32 i;
2651 +  CLzmaProb *probs = p->probs;
2652 +  for (i = 0; i < numProbs; i++)
2653 +    probs[i] = kBitModelTotal >> 1;
2654 +  p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1;
2655 +  p->state = 0;
2656 +  p->needInitState = 0;
2657 +}
2658 +
2659 +SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen,
2660 +    ELzmaFinishMode finishMode, ELzmaStatus *status)
2661 +{
2662 +  SizeT inSize = *srcLen;
2663 +  (*srcLen) = 0;
2664 +  LzmaDec_WriteRem(p, dicLimit);
2665 +
2666 +  *status = LZMA_STATUS_NOT_SPECIFIED;
2667 +
2668 +  while (p->remainLen != kMatchSpecLenStart)
2669 +  {
2670 +      int checkEndMarkNow;
2671 +
2672 +      if (p->needFlush != 0)
2673 +      {
2674 +        for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--)
2675 +          p->tempBuf[p->tempBufSize++] = *src++;
2676 +        if (p->tempBufSize < RC_INIT_SIZE)
2677 +        {
2678 +          *status = LZMA_STATUS_NEEDS_MORE_INPUT;
2679 +          return SZ_OK;
2680 +        }
2681 +        if (p->tempBuf[0] != 0)
2682 +          return SZ_ERROR_DATA;
2683 +
2684 +        LzmaDec_InitRc(p, p->tempBuf);
2685 +        p->tempBufSize = 0;
2686 +      }
2687 +
2688 +      checkEndMarkNow = 0;
2689 +      if (p->dicPos >= dicLimit)
2690 +      {
2691 +        if (p->remainLen == 0 && p->code == 0)
2692 +        {
2693 +          *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK;
2694 +          return SZ_OK;
2695 +        }
2696 +        if (finishMode == LZMA_FINISH_ANY)
2697 +        {
2698 +          *status = LZMA_STATUS_NOT_FINISHED;
2699 +          return SZ_OK;
2700 +        }
2701 +        if (p->remainLen != 0)
2702 +        {
2703 +          *status = LZMA_STATUS_NOT_FINISHED;
2704 +          return SZ_ERROR_DATA;
2705 +        }
2706 +        checkEndMarkNow = 1;
2707 +      }
2708 +
2709 +      if (p->needInitState)
2710 +        LzmaDec_InitStateReal(p);
2711 +
2712 +      if (p->tempBufSize == 0)
2713 +      {
2714 +        SizeT processed;
2715 +        const Byte *bufLimit;
2716 +        if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
2717 +        {
2718 +          int dummyRes = LzmaDec_TryDummy(p, src, inSize);
2719 +          if (dummyRes == DUMMY_ERROR)
2720 +          {
2721 +            memcpy(p->tempBuf, src, inSize);
2722 +            p->tempBufSize = (unsigned)inSize;
2723 +            (*srcLen) += inSize;
2724 +            *status = LZMA_STATUS_NEEDS_MORE_INPUT;
2725 +            return SZ_OK;
2726 +          }
2727 +          if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
2728 +          {
2729 +            *status = LZMA_STATUS_NOT_FINISHED;
2730 +            return SZ_ERROR_DATA;
2731 +          }
2732 +          bufLimit = src;
2733 +        }
2734 +        else
2735 +          bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX;
2736 +        p->buf = src;
2737 +        if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0)
2738 +          return SZ_ERROR_DATA;
2739 +        processed = (SizeT)(p->buf - src);
2740 +        (*srcLen) += processed;
2741 +        src += processed;
2742 +        inSize -= processed;
2743 +      }
2744 +      else
2745 +      {
2746 +        unsigned rem = p->tempBufSize, lookAhead = 0;
2747 +        while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize)
2748 +          p->tempBuf[rem++] = src[lookAhead++];
2749 +        p->tempBufSize = rem;
2750 +        if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
2751 +        {
2752 +          int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem);
2753 +          if (dummyRes == DUMMY_ERROR)
2754 +          {
2755 +            (*srcLen) += lookAhead;
2756 +            *status = LZMA_STATUS_NEEDS_MORE_INPUT;
2757 +            return SZ_OK;
2758 +          }
2759 +          if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
2760 +          {
2761 +            *status = LZMA_STATUS_NOT_FINISHED;
2762 +            return SZ_ERROR_DATA;
2763 +          }
2764 +        }
2765 +        p->buf = p->tempBuf;
2766 +        if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0)
2767 +          return SZ_ERROR_DATA;
2768 +        lookAhead -= (rem - (unsigned)(p->buf - p->tempBuf));
2769 +        (*srcLen) += lookAhead;
2770 +        src += lookAhead;
2771 +        inSize -= lookAhead;
2772 +        p->tempBufSize = 0;
2773 +      }
2774 +  }
2775 +  if (p->code == 0)
2776 +    *status = LZMA_STATUS_FINISHED_WITH_MARK;
2777 +  return (p->code == 0) ? SZ_OK : SZ_ERROR_DATA;
2778 +}
2779 +
2780 +SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status)
2781 +{
2782 +  SizeT outSize = *destLen;
2783 +  SizeT inSize = *srcLen;
2784 +  *srcLen = *destLen = 0;
2785 +  for (;;)
2786 +  {
2787 +    SizeT inSizeCur = inSize, outSizeCur, dicPos;
2788 +    ELzmaFinishMode curFinishMode;
2789 +    SRes res;
2790 +    if (p->dicPos == p->dicBufSize)
2791 +      p->dicPos = 0;
2792 +    dicPos = p->dicPos;
2793 +    if (outSize > p->dicBufSize - dicPos)
2794 +    {
2795 +      outSizeCur = p->dicBufSize;
2796 +      curFinishMode = LZMA_FINISH_ANY;
2797 +    }
2798 +    else
2799 +    {
2800 +      outSizeCur = dicPos + outSize;
2801 +      curFinishMode = finishMode;
2802 +    }
2803 +
2804 +    res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status);
2805 +    src += inSizeCur;
2806 +    inSize -= inSizeCur;
2807 +    *srcLen += inSizeCur;
2808 +    outSizeCur = p->dicPos - dicPos;
2809 +    memcpy(dest, p->dic + dicPos, outSizeCur);
2810 +    dest += outSizeCur;
2811 +    outSize -= outSizeCur;
2812 +    *destLen += outSizeCur;
2813 +    if (res != 0)
2814 +      return res;
2815 +    if (outSizeCur == 0 || outSize == 0)
2816 +      return SZ_OK;
2817 +  }
2818 +}
2819 +
2820 +void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc)
2821 +{
2822 +  alloc->Free(alloc, p->probs);
2823 +  p->probs = 0;
2824 +}
2825 +
2826 +static void LzmaDec_FreeDict(CLzmaDec *p, ISzAlloc *alloc)
2827 +{
2828 +  alloc->Free(alloc, p->dic);
2829 +  p->dic = 0;
2830 +}
2831 +
2832 +void LzmaDec_Free(CLzmaDec *p, ISzAlloc *alloc)
2833 +{
2834 +  LzmaDec_FreeProbs(p, alloc);
2835 +  LzmaDec_FreeDict(p, alloc);
2836 +}
2837 +
2838 +SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size)
2839 +{
2840 +  UInt32 dicSize;
2841 +  Byte d;
2842 +
2843 +  if (size < LZMA_PROPS_SIZE)
2844 +    return SZ_ERROR_UNSUPPORTED;
2845 +  else
2846 +    dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24);
2847 +
2848 +  if (dicSize < LZMA_DIC_MIN)
2849 +    dicSize = LZMA_DIC_MIN;
2850 +  p->dicSize = dicSize;
2851 +
2852 +  d = data[0];
2853 +  if (d >= (9 * 5 * 5))
2854 +    return SZ_ERROR_UNSUPPORTED;
2855 +
2856 +  p->lc = d % 9;
2857 +  d /= 9;
2858 +  p->pb = d / 5;
2859 +  p->lp = d % 5;
2860 +
2861 +  return SZ_OK;
2862 +}
2863 +
2864 +static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAlloc *alloc)
2865 +{
2866 +  UInt32 numProbs = LzmaProps_GetNumProbs(propNew);
2867 +  if (p->probs == 0 || numProbs != p->numProbs)
2868 +  {
2869 +    LzmaDec_FreeProbs(p, alloc);
2870 +    p->probs = (CLzmaProb *)alloc->Alloc(alloc, numProbs * sizeof(CLzmaProb));
2871 +    p->numProbs = numProbs;
2872 +    if (p->probs == 0)
2873 +      return SZ_ERROR_MEM;
2874 +  }
2875 +  return SZ_OK;
2876 +}
2877 +
2878 +SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
2879 +{
2880 +  CLzmaProps propNew;
2881 +  RINOK(LzmaProps_Decode(&propNew, props, propsSize));
2882 +  RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
2883 +  p->prop = propNew;
2884 +  return SZ_OK;
2885 +}
2886 +
2887 +SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
2888 +{
2889 +  CLzmaProps propNew;
2890 +  SizeT dicBufSize;
2891 +  RINOK(LzmaProps_Decode(&propNew, props, propsSize));
2892 +  RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
2893 +  dicBufSize = propNew.dicSize;
2894 +  if (p->dic == 0 || dicBufSize != p->dicBufSize)
2895 +  {
2896 +    LzmaDec_FreeDict(p, alloc);
2897 +    p->dic = (Byte *)alloc->Alloc(alloc, dicBufSize);
2898 +    if (p->dic == 0)
2899 +    {
2900 +      LzmaDec_FreeProbs(p, alloc);
2901 +      return SZ_ERROR_MEM;
2902 +    }
2903 +  }
2904 +  p->dicBufSize = dicBufSize;
2905 +  p->prop = propNew;
2906 +  return SZ_OK;
2907 +}
2908 +
2909 +SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
2910 +    const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,
2911 +    ELzmaStatus *status, ISzAlloc *alloc)
2912 +{
2913 +  CLzmaDec p;
2914 +  SRes res;
2915 +  SizeT inSize = *srcLen;
2916 +  SizeT outSize = *destLen;
2917 +  *srcLen = *destLen = 0;
2918 +  if (inSize < RC_INIT_SIZE)
2919 +    return SZ_ERROR_INPUT_EOF;
2920 +
2921 +  LzmaDec_Construct(&p);
2922 +  res = LzmaDec_AllocateProbs(&p, propData, propSize, alloc);
2923 +  if (res != 0)
2924 +    return res;
2925 +  p.dic = dest;
2926 +  p.dicBufSize = outSize;
2927 +
2928 +  LzmaDec_Init(&p);
2929 +
2930 +  *srcLen = inSize;
2931 +  res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status);
2932 +
2933 +  if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT)
2934 +    res = SZ_ERROR_INPUT_EOF;
2935 +
2936 +  (*destLen) = p.dicPos;
2937 +  LzmaDec_FreeProbs(&p, alloc);
2938 +  return res;
2939 +}
2940 diff --git a/lib/lzma/LzmaEnc.c b/lib/lzma/LzmaEnc.c
2941 new file mode 100644
2942 index 000000000000..6dadf00dfab2
2943 --- /dev/null
2944 +++ b/lib/lzma/LzmaEnc.c
2945 @@ -0,0 +1,2271 @@
2946 +/* LzmaEnc.c -- LZMA Encoder
2947 +2009-11-24 : Igor Pavlov : Public domain */
2948 +
2949 +#include <string.h>
2950 +
2951 +/* #define SHOW_STAT */
2952 +/* #define SHOW_STAT2 */
2953 +
2954 +#if defined(SHOW_STAT) || defined(SHOW_STAT2)
2955 +#include <stdio.h>
2956 +#endif
2957 +
2958 +#include "LzmaEnc.h"
2959 +
2960 +/* disable MT */
2961 +#define _7ZIP_ST
2962 +
2963 +#include "LzFind.h"
2964 +#ifndef _7ZIP_ST
2965 +#include "LzFindMt.h"
2966 +#endif
2967 +
2968 +#ifdef SHOW_STAT
2969 +static int ttt = 0;
2970 +#endif
2971 +
2972 +#define kBlockSizeMax ((1 << LZMA_NUM_BLOCK_SIZE_BITS) - 1)
2973 +
2974 +#define kBlockSize (9 << 10)
2975 +#define kUnpackBlockSize (1 << 18)
2976 +#define kMatchArraySize (1 << 21)
2977 +#define kMatchRecordMaxSize ((LZMA_MATCH_LEN_MAX * 2 + 3) * LZMA_MATCH_LEN_MAX)
2978 +
2979 +#define kNumMaxDirectBits (31)
2980 +
2981 +#define kNumTopBits 24
2982 +#define kTopValue ((UInt32)1 << kNumTopBits)
2983 +
2984 +#define kNumBitModelTotalBits 11
2985 +#define kBitModelTotal (1 << kNumBitModelTotalBits)
2986 +#define kNumMoveBits 5
2987 +#define kProbInitValue (kBitModelTotal >> 1)
2988 +
2989 +#define kNumMoveReducingBits 4
2990 +#define kNumBitPriceShiftBits 4
2991 +#define kBitPrice (1 << kNumBitPriceShiftBits)
2992 +
2993 +void LzmaEncProps_Init(CLzmaEncProps *p)
2994 +{
2995 +  p->level = 5;
2996 +  p->dictSize = p->mc = 0;
2997 +  p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->numThreads = -1;
2998 +  p->writeEndMark = 0;
2999 +}
3000 +
3001 +void LzmaEncProps_Normalize(CLzmaEncProps *p)
3002 +{
3003 +  int level = p->level;
3004 +  if (level < 0) level = 5;
3005 +  p->level = level;
3006 +  if (p->dictSize == 0) p->dictSize = (level <= 5 ? (1 << (level * 2 + 14)) : (level == 6 ? (1 << 25) : (1 << 26)));
3007 +  if (p->lc < 0) p->lc = 3;
3008 +  if (p->lp < 0) p->lp = 0;
3009 +  if (p->pb < 0) p->pb = 2;
3010 +  if (p->algo < 0) p->algo = (level < 5 ? 0 : 1);
3011 +  if (p->fb < 0) p->fb = (level < 7 ? 32 : 64);
3012 +  if (p->btMode < 0) p->btMode = (p->algo == 0 ? 0 : 1);
3013 +  if (p->numHashBytes < 0) p->numHashBytes = 4;
3014 +  if (p->mc == 0)  p->mc = (16 + (p->fb >> 1)) >> (p->btMode ? 0 : 1);
3015 +  if (p->numThreads < 0)
3016 +    p->numThreads =
3017 +      #ifndef _7ZIP_ST
3018 +      ((p->btMode && p->algo) ? 2 : 1);
3019 +      #else
3020 +      1;
3021 +      #endif
3022 +}
3023 +
3024 +UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2)
3025 +{
3026 +  CLzmaEncProps props = *props2;
3027 +  LzmaEncProps_Normalize(&props);
3028 +  return props.dictSize;
3029 +}
3030 +
3031 +/* #define LZMA_LOG_BSR */
3032 +/* Define it for Intel's CPU */
3033 +
3034 +
3035 +#ifdef LZMA_LOG_BSR
3036 +
3037 +#define kDicLogSizeMaxCompress 30
3038 +
3039 +#define BSR2_RET(pos, res) { unsigned long i; _BitScanReverse(&i, (pos)); res = (i + i) + ((pos >> (i - 1)) & 1); }
3040 +
3041 +UInt32 GetPosSlot1(UInt32 pos)
3042 +{
3043 +  UInt32 res;
3044 +  BSR2_RET(pos, res);
3045 +  return res;
3046 +}
3047 +#define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
3048 +#define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res); }
3049 +
3050 +#else
3051 +
3052 +#define kNumLogBits (9 + (int)sizeof(size_t) / 2)
3053 +#define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7)
3054 +
3055 +void LzmaEnc_FastPosInit(Byte *g_FastPos)
3056 +{
3057 +  int c = 2, slotFast;
3058 +  g_FastPos[0] = 0;
3059 +  g_FastPos[1] = 1;
3060 +
3061 +  for (slotFast = 2; slotFast < kNumLogBits * 2; slotFast++)
3062 +  {
3063 +    UInt32 k = (1 << ((slotFast >> 1) - 1));
3064 +    UInt32 j;
3065 +    for (j = 0; j < k; j++, c++)
3066 +      g_FastPos[c] = (Byte)slotFast;
3067 +  }
3068 +}
3069 +
3070 +#define BSR2_RET(pos, res) { UInt32 i = 6 + ((kNumLogBits - 1) & \
3071 +  (0 - (((((UInt32)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \
3072 +  res = p->g_FastPos[pos >> i] + (i * 2); }
3073 +/*
3074 +#define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \
3075 +  p->g_FastPos[pos >> 6] + 12 : \
3076 +  p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; }
3077 +*/
3078 +
3079 +#define GetPosSlot1(pos) p->g_FastPos[pos]
3080 +#define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
3081 +#define GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[pos]; else BSR2_RET(pos, res); }
3082 +
3083 +#endif
3084 +
3085 +
3086 +#define LZMA_NUM_REPS 4
3087 +
3088 +typedef unsigned CState;
3089 +
3090 +typedef struct
3091 +{
3092 +  UInt32 price;
3093 +
3094 +  CState state;
3095 +  int prev1IsChar;
3096 +  int prev2;
3097 +
3098 +  UInt32 posPrev2;
3099 +  UInt32 backPrev2;
3100 +
3101 +  UInt32 posPrev;
3102 +  UInt32 backPrev;
3103 +  UInt32 backs[LZMA_NUM_REPS];
3104 +} COptimal;
3105 +
3106 +#define kNumOpts (1 << 12)
3107 +
3108 +#define kNumLenToPosStates 4
3109 +#define kNumPosSlotBits 6
3110 +#define kDicLogSizeMin 0
3111 +#define kDicLogSizeMax 32
3112 +#define kDistTableSizeMax (kDicLogSizeMax * 2)
3113 +
3114 +
3115 +#define kNumAlignBits 4
3116 +#define kAlignTableSize (1 << kNumAlignBits)
3117 +#define kAlignMask (kAlignTableSize - 1)
3118 +
3119 +#define kStartPosModelIndex 4
3120 +#define kEndPosModelIndex 14
3121 +#define kNumPosModels (kEndPosModelIndex - kStartPosModelIndex)
3122 +
3123 +#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
3124 +
3125 +#ifdef _LZMA_PROB32
3126 +#define CLzmaProb UInt32
3127 +#else
3128 +#define CLzmaProb UInt16
3129 +#endif
3130 +
3131 +#define LZMA_PB_MAX 4
3132 +#define LZMA_LC_MAX 8
3133 +#define LZMA_LP_MAX 4
3134 +
3135 +#define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX)
3136 +
3137 +
3138 +#define kLenNumLowBits 3
3139 +#define kLenNumLowSymbols (1 << kLenNumLowBits)
3140 +#define kLenNumMidBits 3
3141 +#define kLenNumMidSymbols (1 << kLenNumMidBits)
3142 +#define kLenNumHighBits 8
3143 +#define kLenNumHighSymbols (1 << kLenNumHighBits)
3144 +
3145 +#define kLenNumSymbolsTotal (kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)
3146 +
3147 +#define LZMA_MATCH_LEN_MIN 2
3148 +#define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1)
3149 +
3150 +#define kNumStates 12
3151 +
3152 +typedef struct
3153 +{
3154 +  CLzmaProb choice;
3155 +  CLzmaProb choice2;
3156 +  CLzmaProb low[LZMA_NUM_PB_STATES_MAX << kLenNumLowBits];
3157 +  CLzmaProb mid[LZMA_NUM_PB_STATES_MAX << kLenNumMidBits];
3158 +  CLzmaProb high[kLenNumHighSymbols];
3159 +} CLenEnc;
3160 +
3161 +typedef struct
3162 +{
3163 +  CLenEnc p;
3164 +  UInt32 prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal];
3165 +  UInt32 tableSize;
3166 +  UInt32 counters[LZMA_NUM_PB_STATES_MAX];
3167 +} CLenPriceEnc;
3168 +
3169 +typedef struct
3170 +{
3171 +  UInt32 range;
3172 +  Byte cache;
3173 +  UInt64 low;
3174 +  UInt64 cacheSize;
3175 +  Byte *buf;
3176 +  Byte *bufLim;
3177 +  Byte *bufBase;
3178 +  ISeqOutStream *outStream;
3179 +  UInt64 processed;
3180 +  SRes res;
3181 +} CRangeEnc;
3182 +
3183 +typedef struct
3184 +{
3185 +  CLzmaProb *litProbs;
3186 +
3187 +  CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];
3188 +  CLzmaProb isRep[kNumStates];
3189 +  CLzmaProb isRepG0[kNumStates];
3190 +  CLzmaProb isRepG1[kNumStates];
3191 +  CLzmaProb isRepG2[kNumStates];
3192 +  CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];
3193 +
3194 +  CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];
3195 +  CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex];
3196 +  CLzmaProb posAlignEncoder[1 << kNumAlignBits];
3197 +
3198 +  CLenPriceEnc lenEnc;
3199 +  CLenPriceEnc repLenEnc;
3200 +
3201 +  UInt32 reps[LZMA_NUM_REPS];
3202 +  UInt32 state;
3203 +} CSaveState;
3204 +
3205 +typedef struct
3206 +{
3207 +  IMatchFinder matchFinder;
3208 +  void *matchFinderObj;
3209 +
3210 +  #ifndef _7ZIP_ST
3211 +  Bool mtMode;
3212 +  CMatchFinderMt matchFinderMt;
3213 +  #endif
3214 +
3215 +  CMatchFinder matchFinderBase;
3216 +
3217 +  #ifndef _7ZIP_ST
3218 +  Byte pad[128];
3219 +  #endif
3220 +
3221 +  UInt32 optimumEndIndex;
3222 +  UInt32 optimumCurrentIndex;
3223 +
3224 +  UInt32 longestMatchLength;
3225 +  UInt32 numPairs;
3226 +  UInt32 numAvail;
3227 +  COptimal opt[kNumOpts];
3228 +
3229 +  #ifndef LZMA_LOG_BSR
3230 +  Byte g_FastPos[1 << kNumLogBits];
3231 +  #endif
3232 +
3233 +  UInt32 ProbPrices[kBitModelTotal >> kNumMoveReducingBits];
3234 +  UInt32 matches[LZMA_MATCH_LEN_MAX * 2 + 2 + 1];
3235 +  UInt32 numFastBytes;
3236 +  UInt32 additionalOffset;
3237 +  UInt32 reps[LZMA_NUM_REPS];
3238 +  UInt32 state;
3239 +
3240 +  UInt32 posSlotPrices[kNumLenToPosStates][kDistTableSizeMax];
3241 +  UInt32 distancesPrices[kNumLenToPosStates][kNumFullDistances];
3242 +  UInt32 alignPrices[kAlignTableSize];
3243 +  UInt32 alignPriceCount;
3244 +
3245 +  UInt32 distTableSize;
3246 +
3247 +  unsigned lc, lp, pb;
3248 +  unsigned lpMask, pbMask;
3249 +
3250 +  CLzmaProb *litProbs;
3251 +
3252 +  CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];
3253 +  CLzmaProb isRep[kNumStates];
3254 +  CLzmaProb isRepG0[kNumStates];
3255 +  CLzmaProb isRepG1[kNumStates];
3256 +  CLzmaProb isRepG2[kNumStates];
3257 +  CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];
3258 +
3259 +  CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];
3260 +  CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex];
3261 +  CLzmaProb posAlignEncoder[1 << kNumAlignBits];
3262 +
3263 +  CLenPriceEnc lenEnc;
3264 +  CLenPriceEnc repLenEnc;
3265 +
3266 +  unsigned lclp;
3267 +
3268 +  Bool fastMode;
3269 +
3270 +  CRangeEnc rc;
3271 +
3272 +  Bool writeEndMark;
3273 +  UInt64 nowPos64;
3274 +  UInt32 matchPriceCount;
3275 +  Bool finished;
3276 +  Bool multiThread;
3277 +
3278 +  SRes result;
3279 +  UInt32 dictSize;
3280 +  UInt32 matchFinderCycles;
3281 +
3282 +  int needInit;
3283 +
3284 +  CSaveState saveState;
3285 +} CLzmaEnc;
3286 +
3287 +void LzmaEnc_SaveState(CLzmaEncHandle pp)
3288 +{
3289 +  CLzmaEnc *p = (CLzmaEnc *)pp;
3290 +  CSaveState *dest = &p->saveState;
3291 +  int i;
3292 +  dest->lenEnc = p->lenEnc;
3293 +  dest->repLenEnc = p->repLenEnc;
3294 +  dest->state = p->state;
3295 +
3296 +  for (i = 0; i < kNumStates; i++)
3297 +  {
3298 +    memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));
3299 +    memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));
3300 +  }
3301 +  for (i = 0; i < kNumLenToPosStates; i++)
3302 +    memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i]));
3303 +  memcpy(dest->isRep, p->isRep, sizeof(p->isRep));
3304 +  memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0));
3305 +  memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1));
3306 +  memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2));
3307 +  memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders));
3308 +  memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder));
3309 +  memcpy(dest->reps, p->reps, sizeof(p->reps));
3310 +  memcpy(dest->litProbs, p->litProbs, (0x300 << p->lclp) * sizeof(CLzmaProb));
3311 +}
3312 +
3313 +void LzmaEnc_RestoreState(CLzmaEncHandle pp)
3314 +{
3315 +  CLzmaEnc *dest = (CLzmaEnc *)pp;
3316 +  const CSaveState *p = &dest->saveState;
3317 +  int i;
3318 +  dest->lenEnc = p->lenEnc;
3319 +  dest->repLenEnc = p->repLenEnc;
3320 +  dest->state = p->state;
3321 +
3322 +  for (i = 0; i < kNumStates; i++)
3323 +  {
3324 +    memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));
3325 +    memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));
3326 +  }
3327 +  for (i = 0; i < kNumLenToPosStates; i++)
3328 +    memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i]));
3329 +  memcpy(dest->isRep, p->isRep, sizeof(p->isRep));
3330 +  memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0));
3331 +  memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1));
3332 +  memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2));
3333 +  memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders));
3334 +  memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder));
3335 +  memcpy(dest->reps, p->reps, sizeof(p->reps));
3336 +  memcpy(dest->litProbs, p->litProbs, (0x300 << dest->lclp) * sizeof(CLzmaProb));
3337 +}
3338 +
3339 +SRes LzmaEnc_SetProps(CLzmaEncHandle pp, const CLzmaEncProps *props2)
3340 +{
3341 +  CLzmaEnc *p = (CLzmaEnc *)pp;
3342 +  CLzmaEncProps props = *props2;
3343 +  LzmaEncProps_Normalize(&props);
3344 +
3345 +  if (props.lc > LZMA_LC_MAX || props.lp > LZMA_LP_MAX || props.pb > LZMA_PB_MAX ||
3346 +      props.dictSize > (1 << kDicLogSizeMaxCompress) || props.dictSize > (1 << 30))
3347 +    return SZ_ERROR_PARAM;
3348 +  p->dictSize = props.dictSize;
3349 +  p->matchFinderCycles = props.mc;
3350 +  {
3351 +    unsigned fb = props.fb;
3352 +    if (fb < 5)
3353 +      fb = 5;
3354 +    if (fb > LZMA_MATCH_LEN_MAX)
3355 +      fb = LZMA_MATCH_LEN_MAX;
3356 +    p->numFastBytes = fb;
3357 +  }
3358 +  p->lc = props.lc;
3359 +  p->lp = props.lp;
3360 +  p->pb = props.pb;
3361 +  p->fastMode = (props.algo == 0);
3362 +  p->matchFinderBase.btMode = props.btMode;
3363 +  {
3364 +    UInt32 numHashBytes = 4;
3365 +    if (props.btMode)
3366 +    {
3367 +      if (props.numHashBytes < 2)
3368 +        numHashBytes = 2;
3369 +      else if (props.numHashBytes < 4)
3370 +        numHashBytes = props.numHashBytes;
3371 +    }
3372 +    p->matchFinderBase.numHashBytes = numHashBytes;
3373 +  }
3374 +
3375 +  p->matchFinderBase.cutValue = props.mc;
3376 +
3377 +  p->writeEndMark = props.writeEndMark;
3378 +
3379 +  #ifndef _7ZIP_ST
3380 +  /*
3381 +  if (newMultiThread != _multiThread)
3382 +  {
3383 +    ReleaseMatchFinder();
3384 +    _multiThread = newMultiThread;
3385 +  }
3386 +  */
3387 +  p->multiThread = (props.numThreads > 1);
3388 +  #endif
3389 +
3390 +  return SZ_OK;
3391 +}
3392 +
3393 +static const int kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4,  5,  6,   4, 5};
3394 +static const int kMatchNextStates[kNumStates]   = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10};
3395 +static const int kRepNextStates[kNumStates]     = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11};
3396 +static const int kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11};
3397 +
3398 +#define IsCharState(s) ((s) < 7)
3399 +
3400 +#define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1)
3401 +
3402 +#define kInfinityPrice (1 << 30)
3403 +
3404 +static void RangeEnc_Construct(CRangeEnc *p)
3405 +{
3406 +  p->outStream = 0;
3407 +  p->bufBase = 0;
3408 +}
3409 +
3410 +#define RangeEnc_GetProcessed(p) ((p)->processed + ((p)->buf - (p)->bufBase) + (p)->cacheSize)
3411 +
3412 +#define RC_BUF_SIZE (1 << 16)
3413 +static int RangeEnc_Alloc(CRangeEnc *p, ISzAlloc *alloc)
3414 +{
3415 +  if (p->bufBase == 0)
3416 +  {
3417 +    p->bufBase = (Byte *)alloc->Alloc(alloc, RC_BUF_SIZE);
3418 +    if (p->bufBase == 0)
3419 +      return 0;
3420 +    p->bufLim = p->bufBase + RC_BUF_SIZE;
3421 +  }
3422 +  return 1;
3423 +}
3424 +
3425 +static void RangeEnc_Free(CRangeEnc *p, ISzAlloc *alloc)
3426 +{
3427 +  alloc->Free(alloc, p->bufBase);
3428 +  p->bufBase = 0;
3429 +}
3430 +
3431 +static void RangeEnc_Init(CRangeEnc *p)
3432 +{
3433 +  /* Stream.Init(); */
3434 +  p->low = 0;
3435 +  p->range = 0xFFFFFFFF;
3436 +  p->cacheSize = 1;
3437 +  p->cache = 0;
3438 +
3439 +  p->buf = p->bufBase;
3440 +
3441 +  p->processed = 0;
3442 +  p->res = SZ_OK;
3443 +}
3444 +
3445 +static void RangeEnc_FlushStream(CRangeEnc *p)
3446 +{
3447 +  size_t num;
3448 +  if (p->res != SZ_OK)
3449 +    return;
3450 +  num = p->buf - p->bufBase;
3451 +  if (num != p->outStream->Write(p->outStream, p->bufBase, num))
3452 +    p->res = SZ_ERROR_WRITE;
3453 +  p->processed += num;
3454 +  p->buf = p->bufBase;
3455 +}
3456 +
3457 +static void MY_FAST_CALL RangeEnc_ShiftLow(CRangeEnc *p)
3458 +{
3459 +  if ((UInt32)p->low < (UInt32)0xFF000000 || (int)(p->low >> 32) != 0)
3460 +  {
3461 +    Byte temp = p->cache;
3462 +    do
3463 +    {
3464 +      Byte *buf = p->buf;
3465 +      *buf++ = (Byte)(temp + (Byte)(p->low >> 32));
3466 +      p->buf = buf;
3467 +      if (buf == p->bufLim)
3468 +        RangeEnc_FlushStream(p);
3469 +      temp = 0xFF;
3470 +    }
3471 +    while (--p->cacheSize != 0);
3472 +    p->cache = (Byte)((UInt32)p->low >> 24);
3473 +  }
3474 +  p->cacheSize++;
3475 +  p->low = (UInt32)p->low << 8;
3476 +}
3477 +
3478 +static void RangeEnc_FlushData(CRangeEnc *p)
3479 +{
3480 +  int i;
3481 +  for (i = 0; i < 5; i++)
3482 +    RangeEnc_ShiftLow(p);
3483 +}
3484 +
3485 +static void RangeEnc_EncodeDirectBits(CRangeEnc *p, UInt32 value, int numBits)
3486 +{
3487 +  do
3488 +  {
3489 +    p->range >>= 1;
3490 +    p->low += p->range & (0 - ((value >> --numBits) & 1));
3491 +    if (p->range < kTopValue)
3492 +    {
3493 +      p->range <<= 8;
3494 +      RangeEnc_ShiftLow(p);
3495 +    }
3496 +  }
3497 +  while (numBits != 0);
3498 +}
3499 +
3500 +static void RangeEnc_EncodeBit(CRangeEnc *p, CLzmaProb *prob, UInt32 symbol)
3501 +{
3502 +  UInt32 ttt = *prob;
3503 +  UInt32 newBound = (p->range >> kNumBitModelTotalBits) * ttt;
3504 +  if (symbol == 0)
3505 +  {
3506 +    p->range = newBound;
3507 +    ttt += (kBitModelTotal - ttt) >> kNumMoveBits;
3508 +  }
3509 +  else
3510 +  {
3511 +    p->low += newBound;
3512 +    p->range -= newBound;
3513 +    ttt -= ttt >> kNumMoveBits;
3514 +  }
3515 +  *prob = (CLzmaProb)ttt;
3516 +  if (p->range < kTopValue)
3517 +  {
3518 +    p->range <<= 8;
3519 +    RangeEnc_ShiftLow(p);
3520 +  }
3521 +}
3522 +
3523 +static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol)
3524 +{
3525 +  symbol |= 0x100;
3526 +  do
3527 +  {
3528 +    RangeEnc_EncodeBit(p, probs + (symbol >> 8), (symbol >> 7) & 1);
3529 +    symbol <<= 1;
3530 +  }
3531 +  while (symbol < 0x10000);
3532 +}
3533 +
3534 +static void LitEnc_EncodeMatched(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol, UInt32 matchByte)
3535 +{
3536 +  UInt32 offs = 0x100;
3537 +  symbol |= 0x100;
3538 +  do
3539 +  {
3540 +    matchByte <<= 1;
3541 +    RangeEnc_EncodeBit(p, probs + (offs + (matchByte & offs) + (symbol >> 8)), (symbol >> 7) & 1);
3542 +    symbol <<= 1;
3543 +    offs &= ~(matchByte ^ symbol);
3544 +  }
3545 +  while (symbol < 0x10000);
3546 +}
3547 +
3548 +void LzmaEnc_InitPriceTables(UInt32 *ProbPrices)
3549 +{
3550 +  UInt32 i;
3551 +  for (i = (1 << kNumMoveReducingBits) / 2; i < kBitModelTotal; i += (1 << kNumMoveReducingBits))
3552 +  {
3553 +    const int kCyclesBits = kNumBitPriceShiftBits;
3554 +    UInt32 w = i;
3555 +    UInt32 bitCount = 0;
3556 +    int j;
3557 +    for (j = 0; j < kCyclesBits; j++)
3558 +    {
3559 +      w = w * w;
3560 +      bitCount <<= 1;
3561 +      while (w >= ((UInt32)1 << 16))
3562 +      {
3563 +        w >>= 1;
3564 +        bitCount++;
3565 +      }
3566 +    }
3567 +    ProbPrices[i >> kNumMoveReducingBits] = ((kNumBitModelTotalBits << kCyclesBits) - 15 - bitCount);
3568 +  }
3569 +}
3570 +
3571 +
3572 +#define GET_PRICE(prob, symbol) \
3573 +  p->ProbPrices[((prob) ^ (((-(int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];
3574 +
3575 +#define GET_PRICEa(prob, symbol) \
3576 +  ProbPrices[((prob) ^ ((-((int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];
3577 +
3578 +#define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits]
3579 +#define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
3580 +
3581 +#define GET_PRICE_0a(prob) ProbPrices[(prob) >> kNumMoveReducingBits]
3582 +#define GET_PRICE_1a(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
3583 +
3584 +static UInt32 LitEnc_GetPrice(const CLzmaProb *probs, UInt32 symbol, UInt32 *ProbPrices)
3585 +{
3586 +  UInt32 price = 0;
3587 +  symbol |= 0x100;
3588 +  do
3589 +  {
3590 +    price += GET_PRICEa(probs[symbol >> 8], (symbol >> 7) & 1);
3591 +    symbol <<= 1;
3592 +  }
3593 +  while (symbol < 0x10000);
3594 +  return price;
3595 +}
3596 +
3597 +static UInt32 LitEnc_GetPriceMatched(const CLzmaProb *probs, UInt32 symbol, UInt32 matchByte, UInt32 *ProbPrices)
3598 +{
3599 +  UInt32 price = 0;
3600 +  UInt32 offs = 0x100;
3601 +  symbol |= 0x100;
3602 +  do
3603 +  {
3604 +    matchByte <<= 1;
3605 +    price += GET_PRICEa(probs[offs + (matchByte & offs) + (symbol >> 8)], (symbol >> 7) & 1);
3606 +    symbol <<= 1;
3607 +    offs &= ~(matchByte ^ symbol);
3608 +  }
3609 +  while (symbol < 0x10000);
3610 +  return price;
3611 +}
3612 +
3613 +
3614 +static void RcTree_Encode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)
3615 +{
3616 +  UInt32 m = 1;
3617 +  int i;
3618 +  for (i = numBitLevels; i != 0;)
3619 +  {
3620 +    UInt32 bit;
3621 +    i--;
3622 +    bit = (symbol >> i) & 1;
3623 +    RangeEnc_EncodeBit(rc, probs + m, bit);
3624 +    m = (m << 1) | bit;
3625 +  }
3626 +}
3627 +
3628 +static void RcTree_ReverseEncode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)
3629 +{
3630 +  UInt32 m = 1;
3631 +  int i;
3632 +  for (i = 0; i < numBitLevels; i++)
3633 +  {
3634 +    UInt32 bit = symbol & 1;
3635 +    RangeEnc_EncodeBit(rc, probs + m, bit);
3636 +    m = (m << 1) | bit;
3637 +    symbol >>= 1;
3638 +  }
3639 +}
3640 +
3641 +static UInt32 RcTree_GetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, UInt32 *ProbPrices)
3642 +{
3643 +  UInt32 price = 0;
3644 +  symbol |= (1 << numBitLevels);
3645 +  while (symbol != 1)
3646 +  {
3647 +    price += GET_PRICEa(probs[symbol >> 1], symbol & 1);
3648 +    symbol >>= 1;
3649 +  }
3650 +  return price;
3651 +}
3652 +
3653 +static UInt32 RcTree_ReverseGetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, UInt32 *ProbPrices)
3654 +{
3655 +  UInt32 price = 0;
3656 +  UInt32 m = 1;
3657 +  int i;
3658 +  for (i = numBitLevels; i != 0; i--)
3659 +  {
3660 +    UInt32 bit = symbol & 1;
3661 +    symbol >>= 1;
3662 +    price += GET_PRICEa(probs[m], bit);
3663 +    m = (m << 1) | bit;
3664 +  }
3665 +  return price;
3666 +}
3667 +
3668 +
3669 +static void LenEnc_Init(CLenEnc *p)
3670 +{
3671 +  unsigned i;
3672 +  p->choice = p->choice2 = kProbInitValue;
3673 +  for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumLowBits); i++)
3674 +    p->low[i] = kProbInitValue;
3675 +  for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumMidBits); i++)
3676 +    p->mid[i] = kProbInitValue;
3677 +  for (i = 0; i < kLenNumHighSymbols; i++)
3678 +    p->high[i] = kProbInitValue;
3679 +}
3680 +
3681 +static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState)
3682 +{
3683 +  if (symbol < kLenNumLowSymbols)
3684 +  {
3685 +    RangeEnc_EncodeBit(rc, &p->choice, 0);
3686 +    RcTree_Encode(rc, p->low + (posState << kLenNumLowBits), kLenNumLowBits, symbol);
3687 +  }
3688 +  else
3689 +  {
3690 +    RangeEnc_EncodeBit(rc, &p->choice, 1);
3691 +    if (symbol < kLenNumLowSymbols + kLenNumMidSymbols)
3692 +    {
3693 +      RangeEnc_EncodeBit(rc, &p->choice2, 0);
3694 +      RcTree_Encode(rc, p->mid + (posState << kLenNumMidBits), kLenNumMidBits, symbol - kLenNumLowSymbols);
3695 +    }
3696 +    else
3697 +    {
3698 +      RangeEnc_EncodeBit(rc, &p->choice2, 1);
3699 +      RcTree_Encode(rc, p->high, kLenNumHighBits, symbol - kLenNumLowSymbols - kLenNumMidSymbols);
3700 +    }
3701 +  }
3702 +}
3703 +
3704 +static void LenEnc_SetPrices(CLenEnc *p, UInt32 posState, UInt32 numSymbols, UInt32 *prices, UInt32 *ProbPrices)
3705 +{
3706 +  UInt32 a0 = GET_PRICE_0a(p->choice);
3707 +  UInt32 a1 = GET_PRICE_1a(p->choice);
3708 +  UInt32 b0 = a1 + GET_PRICE_0a(p->choice2);
3709 +  UInt32 b1 = a1 + GET_PRICE_1a(p->choice2);
3710 +  UInt32 i = 0;
3711 +  for (i = 0; i < kLenNumLowSymbols; i++)
3712 +  {
3713 +    if (i >= numSymbols)
3714 +      return;
3715 +    prices[i] = a0 + RcTree_GetPrice(p->low + (posState << kLenNumLowBits), kLenNumLowBits, i, ProbPrices);
3716 +  }
3717 +  for (; i < kLenNumLowSymbols + kLenNumMidSymbols; i++)
3718 +  {
3719 +    if (i >= numSymbols)
3720 +      return;
3721 +    prices[i] = b0 + RcTree_GetPrice(p->mid + (posState << kLenNumMidBits), kLenNumMidBits, i - kLenNumLowSymbols, ProbPrices);
3722 +  }
3723 +  for (; i < numSymbols; i++)
3724 +    prices[i] = b1 + RcTree_GetPrice(p->high, kLenNumHighBits, i - kLenNumLowSymbols - kLenNumMidSymbols, ProbPrices);
3725 +}
3726 +
3727 +static void MY_FAST_CALL LenPriceEnc_UpdateTable(CLenPriceEnc *p, UInt32 posState, UInt32 *ProbPrices)
3728 +{
3729 +  LenEnc_SetPrices(&p->p, posState, p->tableSize, p->prices[posState], ProbPrices);
3730 +  p->counters[posState] = p->tableSize;
3731 +}
3732 +
3733 +static void LenPriceEnc_UpdateTables(CLenPriceEnc *p, UInt32 numPosStates, UInt32 *ProbPrices)
3734 +{
3735 +  UInt32 posState;
3736 +  for (posState = 0; posState < numPosStates; posState++)
3737 +    LenPriceEnc_UpdateTable(p, posState, ProbPrices);
3738 +}
3739 +
3740 +static void LenEnc_Encode2(CLenPriceEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState, Bool updatePrice, UInt32 *ProbPrices)
3741 +{
3742 +  LenEnc_Encode(&p->p, rc, symbol, posState);
3743 +  if (updatePrice)
3744 +    if (--p->counters[posState] == 0)
3745 +      LenPriceEnc_UpdateTable(p, posState, ProbPrices);
3746 +}
3747 +
3748 +
3749 +
3750 +
3751 +static void MovePos(CLzmaEnc *p, UInt32 num)
3752 +{
3753 +  #ifdef SHOW_STAT
3754 +  ttt += num;
3755 +  printf("\n MovePos %d", num);
3756 +  #endif
3757 +  if (num != 0)
3758 +  {
3759 +    p->additionalOffset += num;
3760 +    p->matchFinder.Skip(p->matchFinderObj, num);
3761 +  }
3762 +}
3763 +
3764 +static UInt32 ReadMatchDistances(CLzmaEnc *p, UInt32 *numDistancePairsRes)
3765 +{
3766 +  UInt32 lenRes = 0, numPairs;
3767 +  p->numAvail = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
3768 +  numPairs = p->matchFinder.GetMatches(p->matchFinderObj, p->matches);
3769 +  #ifdef SHOW_STAT
3770 +  printf("\n i = %d numPairs = %d    ", ttt, numPairs / 2);
3771 +  ttt++;
3772 +  {
3773 +    UInt32 i;
3774 +    for (i = 0; i < numPairs; i += 2)
3775 +      printf("%2d %6d   | ", p->matches[i], p->matches[i + 1]);
3776 +  }
3777 +  #endif
3778 +  if (numPairs > 0)
3779 +  {
3780 +    lenRes = p->matches[numPairs - 2];
3781 +    if (lenRes == p->numFastBytes)
3782 +    {
3783 +      const Byte *pby = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
3784 +      UInt32 distance = p->matches[numPairs - 1] + 1;
3785 +      UInt32 numAvail = p->numAvail;
3786 +      if (numAvail > LZMA_MATCH_LEN_MAX)
3787 +        numAvail = LZMA_MATCH_LEN_MAX;
3788 +      {
3789 +        const Byte *pby2 = pby - distance;
3790 +        for (; lenRes < numAvail && pby[lenRes] == pby2[lenRes]; lenRes++);
3791 +      }
3792 +    }
3793 +  }
3794 +  p->additionalOffset++;
3795 +  *numDistancePairsRes = numPairs;
3796 +  return lenRes;
3797 +}
3798 +
3799 +
3800 +#define MakeAsChar(p) (p)->backPrev = (UInt32)(-1); (p)->prev1IsChar = False;
3801 +#define MakeAsShortRep(p) (p)->backPrev = 0; (p)->prev1IsChar = False;
3802 +#define IsShortRep(p) ((p)->backPrev == 0)
3803 +
3804 +static UInt32 GetRepLen1Price(CLzmaEnc *p, UInt32 state, UInt32 posState)
3805 +{
3806 +  return
3807 +    GET_PRICE_0(p->isRepG0[state]) +
3808 +    GET_PRICE_0(p->isRep0Long[state][posState]);
3809 +}
3810 +
3811 +static UInt32 GetPureRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 state, UInt32 posState)
3812 +{
3813 +  UInt32 price;
3814 +  if (repIndex == 0)
3815 +  {
3816 +    price = GET_PRICE_0(p->isRepG0[state]);
3817 +    price += GET_PRICE_1(p->isRep0Long[state][posState]);
3818 +  }
3819 +  else
3820 +  {
3821 +    price = GET_PRICE_1(p->isRepG0[state]);
3822 +    if (repIndex == 1)
3823 +      price += GET_PRICE_0(p->isRepG1[state]);
3824 +    else
3825 +    {
3826 +      price += GET_PRICE_1(p->isRepG1[state]);
3827 +      price += GET_PRICE(p->isRepG2[state], repIndex - 2);
3828 +    }
3829 +  }
3830 +  return price;
3831 +}
3832 +
3833 +static UInt32 GetRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 len, UInt32 state, UInt32 posState)
3834 +{
3835 +  return p->repLenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN] +
3836 +    GetPureRepPrice(p, repIndex, state, posState);
3837 +}
3838 +
3839 +static UInt32 Backward(CLzmaEnc *p, UInt32 *backRes, UInt32 cur)
3840 +{
3841 +  UInt32 posMem = p->opt[cur].posPrev;
3842 +  UInt32 backMem = p->opt[cur].backPrev;
3843 +  p->optimumEndIndex = cur;
3844 +  do
3845 +  {
3846 +    if (p->opt[cur].prev1IsChar)
3847 +    {
3848 +      MakeAsChar(&p->opt[posMem])
3849 +      p->opt[posMem].posPrev = posMem - 1;
3850 +      if (p->opt[cur].prev2)
3851 +      {
3852 +        p->opt[posMem - 1].prev1IsChar = False;
3853 +        p->opt[posMem - 1].posPrev = p->opt[cur].posPrev2;
3854 +        p->opt[posMem - 1].backPrev = p->opt[cur].backPrev2;
3855 +      }
3856 +    }
3857 +    {
3858 +      UInt32 posPrev = posMem;
3859 +      UInt32 backCur = backMem;
3860 +
3861 +      backMem = p->opt[posPrev].backPrev;
3862 +      posMem = p->opt[posPrev].posPrev;
3863 +
3864 +      p->opt[posPrev].backPrev = backCur;
3865 +      p->opt[posPrev].posPrev = cur;
3866 +      cur = posPrev;
3867 +    }
3868 +  }
3869 +  while (cur != 0);
3870 +  *backRes = p->opt[0].backPrev;
3871 +  p->optimumCurrentIndex  = p->opt[0].posPrev;
3872 +  return p->optimumCurrentIndex;
3873 +}
3874 +
3875 +#define LIT_PROBS(pos, prevByte) (p->litProbs + ((((pos) & p->lpMask) << p->lc) + ((prevByte) >> (8 - p->lc))) * 0x300)
3876 +
3877 +static UInt32 GetOptimum(CLzmaEnc *p, UInt32 position, UInt32 *backRes)
3878 +{
3879 +  UInt32 numAvail, mainLen, numPairs, repMaxIndex, i, posState, lenEnd, len, cur;
3880 +  UInt32 matchPrice, repMatchPrice, normalMatchPrice;
3881 +  UInt32 reps[LZMA_NUM_REPS], repLens[LZMA_NUM_REPS];
3882 +  UInt32 *matches;
3883 +  const Byte *data;
3884 +  Byte curByte, matchByte;
3885 +  if (p->optimumEndIndex != p->optimumCurrentIndex)
3886 +  {
3887 +    const COptimal *opt = &p->opt[p->optimumCurrentIndex];
3888 +    UInt32 lenRes = opt->posPrev - p->optimumCurrentIndex;
3889 +    *backRes = opt->backPrev;
3890 +    p->optimumCurrentIndex = opt->posPrev;
3891 +    return lenRes;
3892 +  }
3893 +  p->optimumCurrentIndex = p->optimumEndIndex = 0;
3894 +
3895 +  if (p->additionalOffset == 0)
3896 +    mainLen = ReadMatchDistances(p, &numPairs);
3897 +  else
3898 +  {
3899 +    mainLen = p->longestMatchLength;
3900 +    numPairs = p->numPairs;
3901 +  }
3902 +
3903 +  numAvail = p->numAvail;
3904 +  if (numAvail < 2)
3905 +  {
3906 +    *backRes = (UInt32)(-1);
3907 +    return 1;
3908 +  }
3909 +  if (numAvail > LZMA_MATCH_LEN_MAX)
3910 +    numAvail = LZMA_MATCH_LEN_MAX;
3911 +
3912 +  data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
3913 +  repMaxIndex = 0;
3914 +  for (i = 0; i < LZMA_NUM_REPS; i++)
3915 +  {
3916 +    UInt32 lenTest;
3917 +    const Byte *data2;
3918 +    reps[i] = p->reps[i];
3919 +    data2 = data - (reps[i] + 1);
3920 +    if (data[0] != data2[0] || data[1] != data2[1])
3921 +    {
3922 +      repLens[i] = 0;
3923 +      continue;
3924 +    }
3925 +    for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++);
3926 +    repLens[i] = lenTest;
3927 +    if (lenTest > repLens[repMaxIndex])
3928 +      repMaxIndex = i;
3929 +  }
3930 +  if (repLens[repMaxIndex] >= p->numFastBytes)
3931 +  {
3932 +    UInt32 lenRes;
3933 +    *backRes = repMaxIndex;
3934 +    lenRes = repLens[repMaxIndex];
3935 +    MovePos(p, lenRes - 1);
3936 +    return lenRes;
3937 +  }
3938 +
3939 +  matches = p->matches;
3940 +  if (mainLen >= p->numFastBytes)
3941 +  {
3942 +    *backRes = matches[numPairs - 1] + LZMA_NUM_REPS;
3943 +    MovePos(p, mainLen - 1);
3944 +    return mainLen;
3945 +  }
3946 +  curByte = *data;
3947 +  matchByte = *(data - (reps[0] + 1));
3948 +
3949 +  if (mainLen < 2 && curByte != matchByte && repLens[repMaxIndex] < 2)
3950 +  {
3951 +    *backRes = (UInt32)-1;
3952 +    return 1;
3953 +  }
3954 +
3955 +  p->opt[0].state = (CState)p->state;
3956 +
3957 +  posState = (position & p->pbMask);
3958 +
3959 +  {
3960 +    const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));
3961 +    p->opt[1].price = GET_PRICE_0(p->isMatch[p->state][posState]) +
3962 +        (!IsCharState(p->state) ?
3963 +          LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) :
3964 +          LitEnc_GetPrice(probs, curByte, p->ProbPrices));
3965 +  }
3966 +
3967 +  MakeAsChar(&p->opt[1]);
3968 +
3969 +  matchPrice = GET_PRICE_1(p->isMatch[p->state][posState]);
3970 +  repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[p->state]);
3971 +
3972 +  if (matchByte == curByte)
3973 +  {
3974 +    UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, p->state, posState);
3975 +    if (shortRepPrice < p->opt[1].price)
3976 +    {
3977 +      p->opt[1].price = shortRepPrice;
3978 +      MakeAsShortRep(&p->opt[1]);
3979 +    }
3980 +  }
3981 +  lenEnd = ((mainLen >= repLens[repMaxIndex]) ? mainLen : repLens[repMaxIndex]);
3982 +
3983 +  if (lenEnd < 2)
3984 +  {
3985 +    *backRes = p->opt[1].backPrev;
3986 +    return 1;
3987 +  }
3988 +
3989 +  p->opt[1].posPrev = 0;
3990 +  for (i = 0; i < LZMA_NUM_REPS; i++)
3991 +    p->opt[0].backs[i] = reps[i];
3992 +
3993 +  len = lenEnd;
3994 +  do
3995 +    p->opt[len--].price = kInfinityPrice;
3996 +  while (len >= 2);
3997 +
3998 +  for (i = 0; i < LZMA_NUM_REPS; i++)
3999 +  {
4000 +    UInt32 repLen = repLens[i];
4001 +    UInt32 price;
4002 +    if (repLen < 2)
4003 +      continue;
4004 +    price = repMatchPrice + GetPureRepPrice(p, i, p->state, posState);
4005 +    do
4006 +    {
4007 +      UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][repLen - 2];
4008 +      COptimal *opt = &p->opt[repLen];
4009 +      if (curAndLenPrice < opt->price)
4010 +      {
4011 +        opt->price = curAndLenPrice;
4012 +        opt->posPrev = 0;
4013 +        opt->backPrev = i;
4014 +        opt->prev1IsChar = False;
4015 +      }
4016 +    }
4017 +    while (--repLen >= 2);
4018 +  }
4019 +
4020 +  normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[p->state]);
4021 +
4022 +  len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2);
4023 +  if (len <= mainLen)
4024 +  {
4025 +    UInt32 offs = 0;
4026 +    while (len > matches[offs])
4027 +      offs += 2;
4028 +    for (; ; len++)
4029 +    {
4030 +      COptimal *opt;
4031 +      UInt32 distance = matches[offs + 1];
4032 +
4033 +      UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN];
4034 +      UInt32 lenToPosState = GetLenToPosState(len);
4035 +      if (distance < kNumFullDistances)
4036 +        curAndLenPrice += p->distancesPrices[lenToPosState][distance];
4037 +      else
4038 +      {
4039 +        UInt32 slot;
4040 +        GetPosSlot2(distance, slot);
4041 +        curAndLenPrice += p->alignPrices[distance & kAlignMask] + p->posSlotPrices[lenToPosState][slot];
4042 +      }
4043 +      opt = &p->opt[len];
4044 +      if (curAndLenPrice < opt->price)
4045 +      {
4046 +        opt->price = curAndLenPrice;
4047 +        opt->posPrev = 0;
4048 +        opt->backPrev = distance + LZMA_NUM_REPS;
4049 +        opt->prev1IsChar = False;
4050 +      }
4051 +      if (len == matches[offs])
4052 +      {
4053 +        offs += 2;
4054 +        if (offs == numPairs)
4055 +          break;
4056 +      }
4057 +    }
4058 +  }
4059 +
4060 +  cur = 0;
4061 +
4062 +    #ifdef SHOW_STAT2
4063 +    if (position >= 0)
4064 +    {
4065 +      unsigned i;
4066 +      printf("\n pos = %4X", position);
4067 +      for (i = cur; i <= lenEnd; i++)
4068 +      printf("\nprice[%4X] = %d", position - cur + i, p->opt[i].price);
4069 +    }
4070 +    #endif
4071 +
4072 +  for (;;)
4073 +  {
4074 +    UInt32 numAvailFull, newLen, numPairs, posPrev, state, posState, startLen;
4075 +    UInt32 curPrice, curAnd1Price, matchPrice, repMatchPrice;
4076 +    Bool nextIsChar;
4077 +    Byte curByte, matchByte;
4078 +    const Byte *data;
4079 +    COptimal *curOpt;
4080 +    COptimal *nextOpt;
4081 +
4082 +    cur++;
4083 +    if (cur == lenEnd)
4084 +      return Backward(p, backRes, cur);
4085 +
4086 +    newLen = ReadMatchDistances(p, &numPairs);
4087 +    if (newLen >= p->numFastBytes)
4088 +    {
4089 +      p->numPairs = numPairs;
4090 +      p->longestMatchLength = newLen;
4091 +      return Backward(p, backRes, cur);
4092 +    }
4093 +    position++;
4094 +    curOpt = &p->opt[cur];
4095 +    posPrev = curOpt->posPrev;
4096 +    if (curOpt->prev1IsChar)
4097 +    {
4098 +      posPrev--;
4099 +      if (curOpt->prev2)
4100 +      {
4101 +        state = p->opt[curOpt->posPrev2].state;
4102 +        if (curOpt->backPrev2 < LZMA_NUM_REPS)
4103 +          state = kRepNextStates[state];
4104 +        else
4105 +          state = kMatchNextStates[state];
4106 +      }
4107 +      else
4108 +        state = p->opt[posPrev].state;
4109 +      state = kLiteralNextStates[state];
4110 +    }
4111 +    else
4112 +      state = p->opt[posPrev].state;
4113 +    if (posPrev == cur - 1)
4114 +    {
4115 +      if (IsShortRep(curOpt))
4116 +        state = kShortRepNextStates[state];
4117 +      else
4118 +        state = kLiteralNextStates[state];
4119 +    }
4120 +    else
4121 +    {
4122 +      UInt32 pos;
4123 +      const COptimal *prevOpt;
4124 +      if (curOpt->prev1IsChar && curOpt->prev2)
4125 +      {
4126 +        posPrev = curOpt->posPrev2;
4127 +        pos = curOpt->backPrev2;
4128 +        state = kRepNextStates[state];
4129 +      }
4130 +      else
4131 +      {
4132 +        pos = curOpt->backPrev;
4133 +        if (pos < LZMA_NUM_REPS)
4134 +          state = kRepNextStates[state];
4135 +        else
4136 +          state = kMatchNextStates[state];
4137 +      }
4138 +      prevOpt = &p->opt[posPrev];
4139 +      if (pos < LZMA_NUM_REPS)
4140 +      {
4141 +        UInt32 i;
4142 +        reps[0] = prevOpt->backs[pos];
4143 +        for (i = 1; i <= pos; i++)
4144 +          reps[i] = prevOpt->backs[i - 1];
4145 +        for (; i < LZMA_NUM_REPS; i++)
4146 +          reps[i] = prevOpt->backs[i];
4147 +      }
4148 +      else
4149 +      {
4150 +        UInt32 i;
4151 +        reps[0] = (pos - LZMA_NUM_REPS);
4152 +        for (i = 1; i < LZMA_NUM_REPS; i++)
4153 +          reps[i] = prevOpt->backs[i - 1];
4154 +      }
4155 +    }
4156 +    curOpt->state = (CState)state;
4157 +
4158 +    curOpt->backs[0] = reps[0];
4159 +    curOpt->backs[1] = reps[1];
4160 +    curOpt->backs[2] = reps[2];
4161 +    curOpt->backs[3] = reps[3];
4162 +
4163 +    curPrice = curOpt->price;
4164 +    nextIsChar = False;
4165 +    data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
4166 +    curByte = *data;
4167 +    matchByte = *(data - (reps[0] + 1));
4168 +
4169 +    posState = (position & p->pbMask);
4170 +
4171 +    curAnd1Price = curPrice + GET_PRICE_0(p->isMatch[state][posState]);
4172 +    {
4173 +      const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));
4174 +      curAnd1Price +=
4175 +        (!IsCharState(state) ?
4176 +          LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) :
4177 +          LitEnc_GetPrice(probs, curByte, p->ProbPrices));
4178 +    }
4179 +
4180 +    nextOpt = &p->opt[cur + 1];
4181 +
4182 +    if (curAnd1Price < nextOpt->price)
4183 +    {
4184 +      nextOpt->price = curAnd1Price;
4185 +      nextOpt->posPrev = cur;
4186 +      MakeAsChar(nextOpt);
4187 +      nextIsChar = True;
4188 +    }
4189 +
4190 +    matchPrice = curPrice + GET_PRICE_1(p->isMatch[state][posState]);
4191 +    repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[state]);
4192 +
4193 +    if (matchByte == curByte && !(nextOpt->posPrev < cur && nextOpt->backPrev == 0))
4194 +    {
4195 +      UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, state, posState);
4196 +      if (shortRepPrice <= nextOpt->price)
4197 +      {
4198 +        nextOpt->price = shortRepPrice;
4199 +        nextOpt->posPrev = cur;
4200 +        MakeAsShortRep(nextOpt);
4201 +        nextIsChar = True;
4202 +      }
4203 +    }
4204 +    numAvailFull = p->numAvail;
4205 +    {
4206 +      UInt32 temp = kNumOpts - 1 - cur;
4207 +      if (temp < numAvailFull)
4208 +        numAvailFull = temp;
4209 +    }
4210 +
4211 +    if (numAvailFull < 2)
4212 +      continue;
4213 +    numAvail = (numAvailFull <= p->numFastBytes ? numAvailFull : p->numFastBytes);
4214 +
4215 +    if (!nextIsChar && matchByte != curByte) /* speed optimization */
4216 +    {
4217 +      /* try Literal + rep0 */
4218 +      UInt32 temp;
4219 +      UInt32 lenTest2;
4220 +      const Byte *data2 = data - (reps[0] + 1);
4221 +      UInt32 limit = p->numFastBytes + 1;
4222 +      if (limit > numAvailFull)
4223 +        limit = numAvailFull;
4224 +
4225 +      for (temp = 1; temp < limit && data[temp] == data2[temp]; temp++);
4226 +      lenTest2 = temp - 1;
4227 +      if (lenTest2 >= 2)
4228 +      {
4229 +        UInt32 state2 = kLiteralNextStates[state];
4230 +        UInt32 posStateNext = (position + 1) & p->pbMask;
4231 +        UInt32 nextRepMatchPrice = curAnd1Price +
4232 +            GET_PRICE_1(p->isMatch[state2][posStateNext]) +
4233 +            GET_PRICE_1(p->isRep[state2]);
4234 +        /* for (; lenTest2 >= 2; lenTest2--) */
4235 +        {
4236 +          UInt32 curAndLenPrice;
4237 +          COptimal *opt;
4238 +          UInt32 offset = cur + 1 + lenTest2;
4239 +          while (lenEnd < offset)
4240 +            p->opt[++lenEnd].price = kInfinityPrice;
4241 +          curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);
4242 +          opt = &p->opt[offset];
4243 +          if (curAndLenPrice < opt->price)
4244 +          {
4245 +            opt->price = curAndLenPrice;
4246 +            opt->posPrev = cur + 1;
4247 +            opt->backPrev = 0;
4248 +            opt->prev1IsChar = True;
4249 +            opt->prev2 = False;
4250 +          }
4251 +        }
4252 +      }
4253 +    }
4254 +
4255 +    startLen = 2; /* speed optimization */
4256 +    {
4257 +    UInt32 repIndex;
4258 +    for (repIndex = 0; repIndex < LZMA_NUM_REPS; repIndex++)
4259 +    {
4260 +      UInt32 lenTest;
4261 +      UInt32 lenTestTemp;
4262 +      UInt32 price;
4263 +      const Byte *data2 = data - (reps[repIndex] + 1);
4264 +      if (data[0] != data2[0] || data[1] != data2[1])
4265 +        continue;
4266 +      for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++);
4267 +      while (lenEnd < cur + lenTest)
4268 +        p->opt[++lenEnd].price = kInfinityPrice;
4269 +      lenTestTemp = lenTest;
4270 +      price = repMatchPrice + GetPureRepPrice(p, repIndex, state, posState);
4271 +      do
4272 +      {
4273 +        UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][lenTest - 2];
4274 +        COptimal *opt = &p->opt[cur + lenTest];
4275 +        if (curAndLenPrice < opt->price)
4276 +        {
4277 +          opt->price = curAndLenPrice;
4278 +          opt->posPrev = cur;
4279 +          opt->backPrev = repIndex;
4280 +          opt->prev1IsChar = False;
4281 +        }
4282 +      }
4283 +      while (--lenTest >= 2);
4284 +      lenTest = lenTestTemp;
4285 +
4286 +      if (repIndex == 0)
4287 +        startLen = lenTest + 1;
4288 +
4289 +      /* if (_maxMode) */
4290 +        {
4291 +          UInt32 lenTest2 = lenTest + 1;
4292 +          UInt32 limit = lenTest2 + p->numFastBytes;
4293 +          UInt32 nextRepMatchPrice;
4294 +          if (limit > numAvailFull)
4295 +            limit = numAvailFull;
4296 +          for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++);
4297 +          lenTest2 -= lenTest + 1;
4298 +          if (lenTest2 >= 2)
4299 +          {
4300 +            UInt32 state2 = kRepNextStates[state];
4301 +            UInt32 posStateNext = (position + lenTest) & p->pbMask;
4302 +            UInt32 curAndLenCharPrice =
4303 +                price + p->repLenEnc.prices[posState][lenTest - 2] +
4304 +                GET_PRICE_0(p->isMatch[state2][posStateNext]) +
4305 +                LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTest - 1]),
4306 +                    data[lenTest], data2[lenTest], p->ProbPrices);
4307 +            state2 = kLiteralNextStates[state2];
4308 +            posStateNext = (position + lenTest + 1) & p->pbMask;
4309 +            nextRepMatchPrice = curAndLenCharPrice +
4310 +                GET_PRICE_1(p->isMatch[state2][posStateNext]) +
4311 +                GET_PRICE_1(p->isRep[state2]);
4312 +
4313 +            /* for (; lenTest2 >= 2; lenTest2--) */
4314 +            {
4315 +              UInt32 curAndLenPrice;
4316 +              COptimal *opt;
4317 +              UInt32 offset = cur + lenTest + 1 + lenTest2;
4318 +              while (lenEnd < offset)
4319 +                p->opt[++lenEnd].price = kInfinityPrice;
4320 +              curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);
4321 +              opt = &p->opt[offset];
4322 +              if (curAndLenPrice < opt->price)
4323 +              {
4324 +                opt->price = curAndLenPrice;
4325 +                opt->posPrev = cur + lenTest + 1;
4326 +                opt->backPrev = 0;
4327 +                opt->prev1IsChar = True;
4328 +                opt->prev2 = True;
4329 +                opt->posPrev2 = cur;
4330 +                opt->backPrev2 = repIndex;
4331 +              }
4332 +            }
4333 +          }
4334 +        }
4335 +    }
4336 +    }
4337 +    /* for (UInt32 lenTest = 2; lenTest <= newLen; lenTest++) */
4338 +    if (newLen > numAvail)
4339 +    {
4340 +      newLen = numAvail;
4341 +      for (numPairs = 0; newLen > matches[numPairs]; numPairs += 2);
4342 +      matches[numPairs] = newLen;
4343 +      numPairs += 2;
4344 +    }
4345 +    if (newLen >= startLen)
4346 +    {
4347 +      UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[state]);
4348 +      UInt32 offs, curBack, posSlot;
4349 +      UInt32 lenTest;
4350 +      while (lenEnd < cur + newLen)
4351 +        p->opt[++lenEnd].price = kInfinityPrice;
4352 +
4353 +      offs = 0;
4354 +      while (startLen > matches[offs])
4355 +        offs += 2;
4356 +      curBack = matches[offs + 1];
4357 +      GetPosSlot2(curBack, posSlot);
4358 +      for (lenTest = /*2*/ startLen; ; lenTest++)
4359 +      {
4360 +        UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][lenTest - LZMA_MATCH_LEN_MIN];
4361 +        UInt32 lenToPosState = GetLenToPosState(lenTest);
4362 +        COptimal *opt;
4363 +        if (curBack < kNumFullDistances)
4364 +          curAndLenPrice += p->distancesPrices[lenToPosState][curBack];
4365 +        else
4366 +          curAndLenPrice += p->posSlotPrices[lenToPosState][posSlot] + p->alignPrices[curBack & kAlignMask];
4367 +
4368 +        opt = &p->opt[cur + lenTest];
4369 +        if (curAndLenPrice < opt->price)
4370 +        {
4371 +          opt->price = curAndLenPrice;
4372 +          opt->posPrev = cur;
4373 +          opt->backPrev = curBack + LZMA_NUM_REPS;
4374 +          opt->prev1IsChar = False;
4375 +        }
4376 +
4377 +        if (/*_maxMode && */lenTest == matches[offs])
4378 +        {
4379 +          /* Try Match + Literal + Rep0 */
4380 +          const Byte *data2 = data - (curBack + 1);
4381 +          UInt32 lenTest2 = lenTest + 1;
4382 +          UInt32 limit = lenTest2 + p->numFastBytes;
4383 +          UInt32 nextRepMatchPrice;
4384 +          if (limit > numAvailFull)
4385 +            limit = numAvailFull;
4386 +          for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++);
4387 +          lenTest2 -= lenTest + 1;
4388 +          if (lenTest2 >= 2)
4389 +          {
4390 +            UInt32 state2 = kMatchNextStates[state];
4391 +            UInt32 posStateNext = (position + lenTest) & p->pbMask;
4392 +            UInt32 curAndLenCharPrice = curAndLenPrice +
4393 +                GET_PRICE_0(p->isMatch[state2][posStateNext]) +
4394 +                LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTest - 1]),
4395 +                    data[lenTest], data2[lenTest], p->ProbPrices);
4396 +            state2 = kLiteralNextStates[state2];
4397 +            posStateNext = (posStateNext + 1) & p->pbMask;
4398 +            nextRepMatchPrice = curAndLenCharPrice +
4399 +                GET_PRICE_1(p->isMatch[state2][posStateNext]) +
4400 +                GET_PRICE_1(p->isRep[state2]);
4401 +
4402 +            /* for (; lenTest2 >= 2; lenTest2--) */
4403 +            {
4404 +              UInt32 offset = cur + lenTest + 1 + lenTest2;
4405 +              UInt32 curAndLenPrice;
4406 +              COptimal *opt;
4407 +              while (lenEnd < offset)
4408 +                p->opt[++lenEnd].price = kInfinityPrice;
4409 +              curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);
4410 +              opt = &p->opt[offset];
4411 +              if (curAndLenPrice < opt->price)
4412 +              {
4413 +                opt->price = curAndLenPrice;
4414 +                opt->posPrev = cur + lenTest + 1;
4415 +                opt->backPrev = 0;
4416 +                opt->prev1IsChar = True;
4417 +                opt->prev2 = True;
4418 +                opt->posPrev2 = cur;
4419 +                opt->backPrev2 = curBack + LZMA_NUM_REPS;
4420 +              }
4421 +            }
4422 +          }
4423 +          offs += 2;
4424 +          if (offs == numPairs)
4425 +            break;
4426 +          curBack = matches[offs + 1];
4427 +          if (curBack >= kNumFullDistances)
4428 +            GetPosSlot2(curBack, posSlot);
4429 +        }
4430 +      }
4431 +    }
4432 +  }
4433 +}
4434 +
4435 +#define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist))
4436 +
4437 +static UInt32 GetOptimumFast(CLzmaEnc *p, UInt32 *backRes)
4438 +{
4439 +  UInt32 numAvail, mainLen, mainDist, numPairs, repIndex, repLen, i;
4440 +  const Byte *data;
4441 +  const UInt32 *matches;
4442 +
4443 +  if (p->additionalOffset == 0)
4444 +    mainLen = ReadMatchDistances(p, &numPairs);
4445 +  else
4446 +  {
4447 +    mainLen = p->longestMatchLength;
4448 +    numPairs = p->numPairs;
4449 +  }
4450 +
4451 +  numAvail = p->numAvail;
4452 +  *backRes = (UInt32)-1;
4453 +  if (numAvail < 2)
4454 +    return 1;
4455 +  if (numAvail > LZMA_MATCH_LEN_MAX)
4456 +    numAvail = LZMA_MATCH_LEN_MAX;
4457 +  data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
4458 +
4459 +  repLen = repIndex = 0;
4460 +  for (i = 0; i < LZMA_NUM_REPS; i++)
4461 +  {
4462 +    UInt32 len;
4463 +    const Byte *data2 = data - (p->reps[i] + 1);
4464 +    if (data[0] != data2[0] || data[1] != data2[1])
4465 +      continue;
4466 +    for (len = 2; len < numAvail && data[len] == data2[len]; len++);
4467 +    if (len >= p->numFastBytes)
4468 +    {
4469 +      *backRes = i;
4470 +      MovePos(p, len - 1);
4471 +      return len;
4472 +    }
4473 +    if (len > repLen)
4474 +    {
4475 +      repIndex = i;
4476 +      repLen = len;
4477 +    }
4478 +  }
4479 +
4480 +  matches = p->matches;
4481 +  if (mainLen >= p->numFastBytes)
4482 +  {
4483 +    *backRes = matches[numPairs - 1] + LZMA_NUM_REPS;
4484 +    MovePos(p, mainLen - 1);
4485 +    return mainLen;
4486 +  }
4487 +
4488 +  mainDist = 0; /* for GCC */
4489 +  if (mainLen >= 2)
4490 +  {
4491 +    mainDist = matches[numPairs - 1];
4492 +    while (numPairs > 2 && mainLen == matches[numPairs - 4] + 1)
4493 +    {
4494 +      if (!ChangePair(matches[numPairs - 3], mainDist))
4495 +        break;
4496 +      numPairs -= 2;
4497 +      mainLen = matches[numPairs - 2];
4498 +      mainDist = matches[numPairs - 1];
4499 +    }
4500 +    if (mainLen == 2 && mainDist >= 0x80)
4501 +      mainLen = 1;
4502 +  }
4503 +
4504 +  if (repLen >= 2 && (
4505 +        (repLen + 1 >= mainLen) ||
4506 +        (repLen + 2 >= mainLen && mainDist >= (1 << 9)) ||
4507 +        (repLen + 3 >= mainLen && mainDist >= (1 << 15))))
4508 +  {
4509 +    *backRes = repIndex;
4510 +    MovePos(p, repLen - 1);
4511 +    return repLen;
4512 +  }
4513 +
4514 +  if (mainLen < 2 || numAvail <= 2)
4515 +    return 1;
4516 +
4517 +  p->longestMatchLength = ReadMatchDistances(p, &p->numPairs);
4518 +  if (p->longestMatchLength >= 2)
4519 +  {
4520 +    UInt32 newDistance = matches[p->numPairs - 1];
4521 +    if ((p->longestMatchLength >= mainLen && newDistance < mainDist) ||
4522 +        (p->longestMatchLength == mainLen + 1 && !ChangePair(mainDist, newDistance)) ||
4523 +        (p->longestMatchLength > mainLen + 1) ||
4524 +        (p->longestMatchLength + 1 >= mainLen && mainLen >= 3 && ChangePair(newDistance, mainDist)))
4525 +      return 1;
4526 +  }
4527 +
4528 +  data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
4529 +  for (i = 0; i < LZMA_NUM_REPS; i++)
4530 +  {
4531 +    UInt32 len, limit;
4532 +    const Byte *data2 = data - (p->reps[i] + 1);
4533 +    if (data[0] != data2[0] || data[1] != data2[1])
4534 +      continue;
4535 +    limit = mainLen - 1;
4536 +    for (len = 2; len < limit && data[len] == data2[len]; len++);
4537 +    if (len >= limit)
4538 +      return 1;
4539 +  }
4540 +  *backRes = mainDist + LZMA_NUM_REPS;
4541 +  MovePos(p, mainLen - 2);
4542 +  return mainLen;
4543 +}
4544 +
4545 +static void WriteEndMarker(CLzmaEnc *p, UInt32 posState)
4546 +{
4547 +  UInt32 len;
4548 +  RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1);
4549 +  RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0);
4550 +  p->state = kMatchNextStates[p->state];
4551 +  len = LZMA_MATCH_LEN_MIN;
4552 +  LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
4553 +  RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, (1 << kNumPosSlotBits) - 1);
4554 +  RangeEnc_EncodeDirectBits(&p->rc, (((UInt32)1 << 30) - 1) >> kNumAlignBits, 30 - kNumAlignBits);
4555 +  RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, kAlignMask);
4556 +}
4557 +
4558 +static SRes CheckErrors(CLzmaEnc *p)
4559 +{
4560 +  if (p->result != SZ_OK)
4561 +    return p->result;
4562 +  if (p->rc.res != SZ_OK)
4563 +    p->result = SZ_ERROR_WRITE;
4564 +  if (p->matchFinderBase.result != SZ_OK)
4565 +    p->result = SZ_ERROR_READ;
4566 +  if (p->result != SZ_OK)
4567 +    p->finished = True;
4568 +  return p->result;
4569 +}
4570 +
4571 +static SRes Flush(CLzmaEnc *p, UInt32 nowPos)
4572 +{
4573 +  /* ReleaseMFStream(); */
4574 +  p->finished = True;
4575 +  if (p->writeEndMark)
4576 +    WriteEndMarker(p, nowPos & p->pbMask);
4577 +  RangeEnc_FlushData(&p->rc);
4578 +  RangeEnc_FlushStream(&p->rc);
4579 +  return CheckErrors(p);
4580 +}
4581 +
4582 +static void FillAlignPrices(CLzmaEnc *p)
4583 +{
4584 +  UInt32 i;
4585 +  for (i = 0; i < kAlignTableSize; i++)
4586 +    p->alignPrices[i] = RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits, i, p->ProbPrices);
4587 +  p->alignPriceCount = 0;
4588 +}
4589 +
4590 +static void FillDistancesPrices(CLzmaEnc *p)
4591 +{
4592 +  UInt32 tempPrices[kNumFullDistances];
4593 +  UInt32 i, lenToPosState;
4594 +  for (i = kStartPosModelIndex; i < kNumFullDistances; i++)
4595 +  {
4596 +    UInt32 posSlot = GetPosSlot1(i);
4597 +    UInt32 footerBits = ((posSlot >> 1) - 1);
4598 +    UInt32 base = ((2 | (posSlot & 1)) << footerBits);
4599 +    tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base - posSlot - 1, footerBits, i - base, p->ProbPrices);
4600 +  }
4601 +
4602 +  for (lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)
4603 +  {
4604 +    UInt32 posSlot;
4605 +    const CLzmaProb *encoder = p->posSlotEncoder[lenToPosState];
4606 +    UInt32 *posSlotPrices = p->posSlotPrices[lenToPosState];
4607 +    for (posSlot = 0; posSlot < p->distTableSize; posSlot++)
4608 +      posSlotPrices[posSlot] = RcTree_GetPrice(encoder, kNumPosSlotBits, posSlot, p->ProbPrices);
4609 +    for (posSlot = kEndPosModelIndex; posSlot < p->distTableSize; posSlot++)
4610 +      posSlotPrices[posSlot] += ((((posSlot >> 1) - 1) - kNumAlignBits) << kNumBitPriceShiftBits);
4611 +
4612 +    {
4613 +      UInt32 *distancesPrices = p->distancesPrices[lenToPosState];
4614 +      UInt32 i;
4615 +      for (i = 0; i < kStartPosModelIndex; i++)
4616 +        distancesPrices[i] = posSlotPrices[i];
4617 +      for (; i < kNumFullDistances; i++)
4618 +        distancesPrices[i] = posSlotPrices[GetPosSlot1(i)] + tempPrices[i];
4619 +    }
4620 +  }
4621 +  p->matchPriceCount = 0;
4622 +}
4623 +
4624 +void LzmaEnc_Construct(CLzmaEnc *p)
4625 +{
4626 +  RangeEnc_Construct(&p->rc);
4627 +  MatchFinder_Construct(&p->matchFinderBase);
4628 +  #ifndef _7ZIP_ST
4629 +  MatchFinderMt_Construct(&p->matchFinderMt);
4630 +  p->matchFinderMt.MatchFinder = &p->matchFinderBase;
4631 +  #endif
4632 +
4633 +  {
4634 +    CLzmaEncProps props;
4635 +    LzmaEncProps_Init(&props);
4636 +    LzmaEnc_SetProps(p, &props);
4637 +  }
4638 +
4639 +  #ifndef LZMA_LOG_BSR
4640 +  LzmaEnc_FastPosInit(p->g_FastPos);
4641 +  #endif
4642 +
4643 +  LzmaEnc_InitPriceTables(p->ProbPrices);
4644 +  p->litProbs = 0;
4645 +  p->saveState.litProbs = 0;
4646 +}
4647 +
4648 +CLzmaEncHandle LzmaEnc_Create(ISzAlloc *alloc)
4649 +{
4650 +  void *p;
4651 +  p = alloc->Alloc(alloc, sizeof(CLzmaEnc));
4652 +  if (p != 0)
4653 +    LzmaEnc_Construct((CLzmaEnc *)p);
4654 +  return p;
4655 +}
4656 +
4657 +void LzmaEnc_FreeLits(CLzmaEnc *p, ISzAlloc *alloc)
4658 +{
4659 +  alloc->Free(alloc, p->litProbs);
4660 +  alloc->Free(alloc, p->saveState.litProbs);
4661 +  p->litProbs = 0;
4662 +  p->saveState.litProbs = 0;
4663 +}
4664 +
4665 +void LzmaEnc_Destruct(CLzmaEnc *p, ISzAlloc *alloc, ISzAlloc *allocBig)
4666 +{
4667 +  #ifndef _7ZIP_ST
4668 +  MatchFinderMt_Destruct(&p->matchFinderMt, allocBig);
4669 +  #endif
4670 +  MatchFinder_Free(&p->matchFinderBase, allocBig);
4671 +  LzmaEnc_FreeLits(p, alloc);
4672 +  RangeEnc_Free(&p->rc, alloc);
4673 +}
4674 +
4675 +void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAlloc *alloc, ISzAlloc *allocBig)
4676 +{
4677 +  LzmaEnc_Destruct((CLzmaEnc *)p, alloc, allocBig);
4678 +  alloc->Free(alloc, p);
4679 +}
4680 +
4681 +static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, Bool useLimits, UInt32 maxPackSize, UInt32 maxUnpackSize)
4682 +{
4683 +  UInt32 nowPos32, startPos32;
4684 +  if (p->needInit)
4685 +  {
4686 +    p->matchFinder.Init(p->matchFinderObj);
4687 +    p->needInit = 0;
4688 +  }
4689 +
4690 +  if (p->finished)
4691 +    return p->result;
4692 +  RINOK(CheckErrors(p));
4693 +
4694 +  nowPos32 = (UInt32)p->nowPos64;
4695 +  startPos32 = nowPos32;
4696 +
4697 +  if (p->nowPos64 == 0)
4698 +  {
4699 +    UInt32 numPairs;
4700 +    Byte curByte;
4701 +    if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
4702 +      return Flush(p, nowPos32);
4703 +    ReadMatchDistances(p, &numPairs);
4704 +    RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][0], 0);
4705 +    p->state = kLiteralNextStates[p->state];
4706 +    curByte = p->matchFinder.GetIndexByte(p->matchFinderObj, 0 - p->additionalOffset);
4707 +    LitEnc_Encode(&p->rc, p->litProbs, curByte);
4708 +    p->additionalOffset--;
4709 +    nowPos32++;
4710 +  }
4711 +
4712 +  if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) != 0)
4713 +  for (;;)
4714 +  {
4715 +    UInt32 pos, len, posState;
4716 +
4717 +    if (p->fastMode)
4718 +      len = GetOptimumFast(p, &pos);
4719 +    else
4720 +      len = GetOptimum(p, nowPos32, &pos);
4721 +
4722 +    #ifdef SHOW_STAT2
4723 +    printf("\n pos = %4X,   len = %d   pos = %d", nowPos32, len, pos);
4724 +    #endif
4725 +
4726 +    posState = nowPos32 & p->pbMask;
4727 +    if (len == 1 && pos == (UInt32)-1)
4728 +    {
4729 +      Byte curByte;
4730 +      CLzmaProb *probs;
4731 +      const Byte *data;
4732 +
4733 +      RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 0);
4734 +      data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
4735 +      curByte = *data;
4736 +      probs = LIT_PROBS(nowPos32, *(data - 1));
4737 +      if (IsCharState(p->state))
4738 +        LitEnc_Encode(&p->rc, probs, curByte);
4739 +      else
4740 +        LitEnc_EncodeMatched(&p->rc, probs, curByte, *(data - p->reps[0] - 1));
4741 +      p->state = kLiteralNextStates[p->state];
4742 +    }
4743 +    else
4744 +    {
4745 +      RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1);
4746 +      if (pos < LZMA_NUM_REPS)
4747 +      {
4748 +        RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 1);
4749 +        if (pos == 0)
4750 +        {
4751 +          RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 0);
4752 +          RangeEnc_EncodeBit(&p->rc, &p->isRep0Long[p->state][posState], ((len == 1) ? 0 : 1));
4753 +        }
4754 +        else
4755 +        {
4756 +          UInt32 distance = p->reps[pos];
4757 +          RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 1);
4758 +          if (pos == 1)
4759 +            RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 0);
4760 +          else
4761 +          {
4762 +            RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 1);
4763 +            RangeEnc_EncodeBit(&p->rc, &p->isRepG2[p->state], pos - 2);
4764 +            if (pos == 3)
4765 +              p->reps[3] = p->reps[2];
4766 +            p->reps[2] = p->reps[1];
4767 +          }
4768 +          p->reps[1] = p->reps[0];
4769 +          p->reps[0] = distance;
4770 +        }
4771 +        if (len == 1)
4772 +          p->state = kShortRepNextStates[p->state];
4773 +        else
4774 +        {
4775 +          LenEnc_Encode2(&p->repLenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
4776 +          p->state = kRepNextStates[p->state];
4777 +        }
4778 +      }
4779 +      else
4780 +      {
4781 +        UInt32 posSlot;
4782 +        RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0);
4783 +        p->state = kMatchNextStates[p->state];
4784 +        LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
4785 +        pos -= LZMA_NUM_REPS;
4786 +        GetPosSlot(pos, posSlot);
4787 +        RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, posSlot);
4788 +
4789 +        if (posSlot >= kStartPosModelIndex)
4790 +        {
4791 +          UInt32 footerBits = ((posSlot >> 1) - 1);
4792 +          UInt32 base = ((2 | (posSlot & 1)) << footerBits);
4793 +          UInt32 posReduced = pos - base;
4794 +
4795 +          if (posSlot < kEndPosModelIndex)
4796 +            RcTree_ReverseEncode(&p->rc, p->posEncoders + base - posSlot - 1, footerBits, posReduced);
4797 +          else
4798 +          {
4799 +            RangeEnc_EncodeDirectBits(&p->rc, posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
4800 +            RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, posReduced & kAlignMask);
4801 +            p->alignPriceCount++;
4802 +          }
4803 +        }
4804 +        p->reps[3] = p->reps[2];
4805 +        p->reps[2] = p->reps[1];
4806 +        p->reps[1] = p->reps[0];
4807 +        p->reps[0] = pos;
4808 +        p->matchPriceCount++;
4809 +      }
4810 +    }
4811 +    p->additionalOffset -= len;
4812 +    nowPos32 += len;
4813 +    if (p->additionalOffset == 0)
4814 +    {
4815 +      UInt32 processed;
4816 +      if (!p->fastMode)
4817 +      {
4818 +        if (p->matchPriceCount >= (1 << 7))
4819 +          FillDistancesPrices(p);
4820 +        if (p->alignPriceCount >= kAlignTableSize)
4821 +          FillAlignPrices(p);
4822 +      }
4823 +      if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
4824 +        break;
4825 +      processed = nowPos32 - startPos32;
4826 +      if (useLimits)
4827 +      {
4828 +        if (processed + kNumOpts + 300 >= maxUnpackSize ||
4829 +            RangeEnc_GetProcessed(&p->rc) + kNumOpts * 2 >= maxPackSize)
4830 +          break;
4831 +      }
4832 +      else if (processed >= (1 << 15))
4833 +      {
4834 +        p->nowPos64 += nowPos32 - startPos32;
4835 +        return CheckErrors(p);
4836 +      }
4837 +    }
4838 +  }
4839 +  p->nowPos64 += nowPos32 - startPos32;
4840 +  return Flush(p, nowPos32);
4841 +}
4842 +
4843 +#define kBigHashDicLimit ((UInt32)1 << 24)
4844 +
4845 +static SRes LzmaEnc_Alloc(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
4846 +{
4847 +  UInt32 beforeSize = kNumOpts;
4848 +  Bool btMode;
4849 +  if (!RangeEnc_Alloc(&p->rc, alloc))
4850 +    return SZ_ERROR_MEM;
4851 +  btMode = (p->matchFinderBase.btMode != 0);
4852 +  #ifndef _7ZIP_ST
4853 +  p->mtMode = (p->multiThread && !p->fastMode && btMode);
4854 +  #endif
4855 +
4856 +  {
4857 +    unsigned lclp = p->lc + p->lp;
4858 +    if (p->litProbs == 0 || p->saveState.litProbs == 0 || p->lclp != lclp)
4859 +    {
4860 +      LzmaEnc_FreeLits(p, alloc);
4861 +      p->litProbs = (CLzmaProb *)alloc->Alloc(alloc, (0x300 << lclp) * sizeof(CLzmaProb));
4862 +      p->saveState.litProbs = (CLzmaProb *)alloc->Alloc(alloc, (0x300 << lclp) * sizeof(CLzmaProb));
4863 +      if (p->litProbs == 0 || p->saveState.litProbs == 0)
4864 +      {
4865 +        LzmaEnc_FreeLits(p, alloc);
4866 +        return SZ_ERROR_MEM;
4867 +      }
4868 +      p->lclp = lclp;
4869 +    }
4870 +  }
4871 +
4872 +  p->matchFinderBase.bigHash = (p->dictSize > kBigHashDicLimit);
4873 +
4874 +  if (beforeSize + p->dictSize < keepWindowSize)
4875 +    beforeSize = keepWindowSize - p->dictSize;
4876 +
4877 +  #ifndef _7ZIP_ST
4878 +  if (p->mtMode)
4879 +  {
4880 +    RINOK(MatchFinderMt_Create(&p->matchFinderMt, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig));
4881 +    p->matchFinderObj = &p->matchFinderMt;
4882 +    MatchFinderMt_CreateVTable(&p->matchFinderMt, &p->matchFinder);
4883 +  }
4884 +  else
4885 +  #endif
4886 +  {
4887 +    if (!MatchFinder_Create(&p->matchFinderBase, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig))
4888 +      return SZ_ERROR_MEM;
4889 +    p->matchFinderObj = &p->matchFinderBase;
4890 +    MatchFinder_CreateVTable(&p->matchFinderBase, &p->matchFinder);
4891 +  }
4892 +  return SZ_OK;
4893 +}
4894 +
4895 +void LzmaEnc_Init(CLzmaEnc *p)
4896 +{
4897 +  UInt32 i;
4898 +  p->state = 0;
4899 +  for (i = 0 ; i < LZMA_NUM_REPS; i++)
4900 +    p->reps[i] = 0;
4901 +
4902 +  RangeEnc_Init(&p->rc);
4903 +
4904 +
4905 +  for (i = 0; i < kNumStates; i++)
4906 +  {
4907 +    UInt32 j;
4908 +    for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++)
4909 +    {
4910 +      p->isMatch[i][j] = kProbInitValue;
4911 +      p->isRep0Long[i][j] = kProbInitValue;
4912 +    }
4913 +    p->isRep[i] = kProbInitValue;
4914 +    p->isRepG0[i] = kProbInitValue;
4915 +    p->isRepG1[i] = kProbInitValue;
4916 +    p->isRepG2[i] = kProbInitValue;
4917 +  }
4918 +
4919 +  {
4920 +    UInt32 num = 0x300 << (p->lp + p->lc);
4921 +    for (i = 0; i < num; i++)
4922 +      p->litProbs[i] = kProbInitValue;
4923 +  }
4924 +
4925 +  {
4926 +    for (i = 0; i < kNumLenToPosStates; i++)
4927 +    {
4928 +      CLzmaProb *probs = p->posSlotEncoder[i];
4929 +      UInt32 j;
4930 +      for (j = 0; j < (1 << kNumPosSlotBits); j++)
4931 +        probs[j] = kProbInitValue;
4932 +    }
4933 +  }
4934 +  {
4935 +    for (i = 0; i < kNumFullDistances - kEndPosModelIndex; i++)
4936 +      p->posEncoders[i] = kProbInitValue;
4937 +  }
4938 +
4939 +  LenEnc_Init(&p->lenEnc.p);
4940 +  LenEnc_Init(&p->repLenEnc.p);
4941 +
4942 +  for (i = 0; i < (1 << kNumAlignBits); i++)
4943 +    p->posAlignEncoder[i] = kProbInitValue;
4944 +
4945 +  p->optimumEndIndex = 0;
4946 +  p->optimumCurrentIndex = 0;
4947 +  p->additionalOffset = 0;
4948 +
4949 +  p->pbMask = (1 << p->pb) - 1;
4950 +  p->lpMask = (1 << p->lp) - 1;
4951 +}
4952 +
4953 +void LzmaEnc_InitPrices(CLzmaEnc *p)
4954 +{
4955 +  if (!p->fastMode)
4956 +  {
4957 +    FillDistancesPrices(p);
4958 +    FillAlignPrices(p);
4959 +  }
4960 +
4961 +  p->lenEnc.tableSize =
4962 +  p->repLenEnc.tableSize =
4963 +      p->numFastBytes + 1 - LZMA_MATCH_LEN_MIN;
4964 +  LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, p->ProbPrices);
4965 +  LenPriceEnc_UpdateTables(&p->repLenEnc, 1 << p->pb, p->ProbPrices);
4966 +}
4967 +
4968 +static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
4969 +{
4970 +  UInt32 i;
4971 +  for (i = 0; i < (UInt32)kDicLogSizeMaxCompress; i++)
4972 +    if (p->dictSize <= ((UInt32)1 << i))
4973 +      break;
4974 +  p->distTableSize = i * 2;
4975 +
4976 +  p->finished = False;
4977 +  p->result = SZ_OK;
4978 +  RINOK(LzmaEnc_Alloc(p, keepWindowSize, alloc, allocBig));
4979 +  LzmaEnc_Init(p);
4980 +  LzmaEnc_InitPrices(p);
4981 +  p->nowPos64 = 0;
4982 +  return SZ_OK;
4983 +}
4984 +
4985 +static SRes LzmaEnc_Prepare(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream,
4986 +    ISzAlloc *alloc, ISzAlloc *allocBig)
4987 +{
4988 +  CLzmaEnc *p = (CLzmaEnc *)pp;
4989 +  p->matchFinderBase.stream = inStream;
4990 +  p->needInit = 1;
4991 +  p->rc.outStream = outStream;
4992 +  return LzmaEnc_AllocAndInit(p, 0, alloc, allocBig);
4993 +}
4994 +
4995 +SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle pp,
4996 +    ISeqInStream *inStream, UInt32 keepWindowSize,
4997 +    ISzAlloc *alloc, ISzAlloc *allocBig)
4998 +{
4999 +  CLzmaEnc *p = (CLzmaEnc *)pp;
5000 +  p->matchFinderBase.stream = inStream;
5001 +  p->needInit = 1;
5002 +  return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
5003 +}
5004 +
5005 +static void LzmaEnc_SetInputBuf(CLzmaEnc *p, const Byte *src, SizeT srcLen)
5006 +{
5007 +  p->matchFinderBase.directInput = 1;
5008 +  p->matchFinderBase.bufferBase = (Byte *)src;
5009 +  p->matchFinderBase.directInputRem = srcLen;
5010 +}
5011 +
5012 +SRes LzmaEnc_MemPrepare(CLzmaEncHandle pp, const Byte *src, SizeT srcLen,
5013 +    UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
5014 +{
5015 +  CLzmaEnc *p = (CLzmaEnc *)pp;
5016 +  LzmaEnc_SetInputBuf(p, src, srcLen);
5017 +  p->needInit = 1;
5018 +
5019 +  return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
5020 +}
5021 +
5022 +void LzmaEnc_Finish(CLzmaEncHandle pp)
5023 +{
5024 +  #ifndef _7ZIP_ST
5025 +  CLzmaEnc *p = (CLzmaEnc *)pp;
5026 +  if (p->mtMode)
5027 +    MatchFinderMt_ReleaseStream(&p->matchFinderMt);
5028 +  #else
5029 +  pp = pp;
5030 +  #endif
5031 +}
5032 +
5033 +typedef struct
5034 +{
5035 +  ISeqOutStream funcTable;
5036 +  Byte *data;
5037 +  SizeT rem;
5038 +  Bool overflow;
5039 +} CSeqOutStreamBuf;
5040 +
5041 +static size_t MyWrite(void *pp, const void *data, size_t size)
5042 +{
5043 +  CSeqOutStreamBuf *p = (CSeqOutStreamBuf *)pp;
5044 +  if (p->rem < size)
5045 +  {
5046 +    size = p->rem;
5047 +    p->overflow = True;
5048 +  }
5049 +  memcpy(p->data, data, size);
5050 +  p->rem -= size;
5051 +  p->data += size;
5052 +  return size;
5053 +}
5054 +
5055 +
5056 +UInt32 LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp)
5057 +{
5058 +  const CLzmaEnc *p = (CLzmaEnc *)pp;
5059 +  return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
5060 +}
5061 +
5062 +const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle pp)
5063 +{
5064 +  const CLzmaEnc *p = (CLzmaEnc *)pp;
5065 +  return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
5066 +}
5067 +
5068 +SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle pp, Bool reInit,
5069 +    Byte *dest, size_t *destLen, UInt32 desiredPackSize, UInt32 *unpackSize)
5070 +{
5071 +  CLzmaEnc *p = (CLzmaEnc *)pp;
5072 +  UInt64 nowPos64;
5073 +  SRes res;
5074 +  CSeqOutStreamBuf outStream;
5075 +
5076 +  outStream.funcTable.Write = MyWrite;
5077 +  outStream.data = dest;
5078 +  outStream.rem = *destLen;
5079 +  outStream.overflow = False;
5080 +
5081 +  p->writeEndMark = False;
5082 +  p->finished = False;
5083 +  p->result = SZ_OK;
5084 +
5085 +  if (reInit)
5086 +    LzmaEnc_Init(p);
5087 +  LzmaEnc_InitPrices(p);
5088 +  nowPos64 = p->nowPos64;
5089 +  RangeEnc_Init(&p->rc);
5090 +  p->rc.outStream = &outStream.funcTable;
5091 +
5092 +  res = LzmaEnc_CodeOneBlock(p, True, desiredPackSize, *unpackSize);
5093 +
5094 +  *unpackSize = (UInt32)(p->nowPos64 - nowPos64);
5095 +  *destLen -= outStream.rem;
5096 +  if (outStream.overflow)
5097 +    return SZ_ERROR_OUTPUT_EOF;
5098 +
5099 +  return res;
5100 +}
5101 +
5102 +static SRes LzmaEnc_Encode2(CLzmaEnc *p, ICompressProgress *progress)
5103 +{
5104 +  SRes res = SZ_OK;
5105 +
5106 +  #ifndef _7ZIP_ST
5107 +  Byte allocaDummy[0x300];
5108 +  int i = 0;
5109 +  for (i = 0; i < 16; i++)
5110 +    allocaDummy[i] = (Byte)i;
5111 +  #endif
5112 +
5113 +  for (;;)
5114 +  {
5115 +    res = LzmaEnc_CodeOneBlock(p, False, 0, 0);
5116 +    if (res != SZ_OK || p->finished != 0)
5117 +      break;
5118 +    if (progress != 0)
5119 +    {
5120 +      res = progress->Progress(progress, p->nowPos64, RangeEnc_GetProcessed(&p->rc));
5121 +      if (res != SZ_OK)
5122 +      {
5123 +        res = SZ_ERROR_PROGRESS;
5124 +        break;
5125 +      }
5126 +    }
5127 +  }
5128 +  LzmaEnc_Finish(p);
5129 +  return res;
5130 +}
5131 +
5132 +SRes LzmaEnc_Encode(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, ICompressProgress *progress,
5133 +    ISzAlloc *alloc, ISzAlloc *allocBig)
5134 +{
5135 +  RINOK(LzmaEnc_Prepare(pp, outStream, inStream, alloc, allocBig));
5136 +  return LzmaEnc_Encode2((CLzmaEnc *)pp, progress);
5137 +}
5138 +
5139 +SRes LzmaEnc_WriteProperties(CLzmaEncHandle pp, Byte *props, SizeT *size)
5140 +{
5141 +  CLzmaEnc *p = (CLzmaEnc *)pp;
5142 +  int i;
5143 +  UInt32 dictSize = p->dictSize;
5144 +  if (*size < LZMA_PROPS_SIZE)
5145 +    return SZ_ERROR_PARAM;
5146 +  *size = LZMA_PROPS_SIZE;
5147 +  props[0] = (Byte)((p->pb * 5 + p->lp) * 9 + p->lc);
5148 +
5149 +  for (i = 11; i <= 30; i++)
5150 +  {
5151 +    if (dictSize <= ((UInt32)2 << i))
5152 +    {
5153 +      dictSize = (2 << i);
5154 +      break;
5155 +    }
5156 +    if (dictSize <= ((UInt32)3 << i))
5157 +    {
5158 +      dictSize = (3 << i);
5159 +      break;
5160 +    }
5161 +  }
5162 +
5163 +  for (i = 0; i < 4; i++)
5164 +    props[1 + i] = (Byte)(dictSize >> (8 * i));
5165 +  return SZ_OK;
5166 +}
5167 +
5168 +SRes LzmaEnc_MemEncode(CLzmaEncHandle pp, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
5169 +    int writeEndMark, ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig)
5170 +{
5171 +  SRes res;
5172 +  CLzmaEnc *p = (CLzmaEnc *)pp;
5173 +
5174 +  CSeqOutStreamBuf outStream;
5175 +
5176 +  LzmaEnc_SetInputBuf(p, src, srcLen);
5177 +
5178 +  outStream.funcTable.Write = MyWrite;
5179 +  outStream.data = dest;
5180 +  outStream.rem = *destLen;
5181 +  outStream.overflow = False;
5182 +
5183 +  p->writeEndMark = writeEndMark;
5184 +
5185 +  p->rc.outStream = &outStream.funcTable;
5186 +  res = LzmaEnc_MemPrepare(pp, src, srcLen, 0, alloc, allocBig);
5187 +  if (res == SZ_OK)
5188 +    res = LzmaEnc_Encode2(p, progress);
5189 +
5190 +  *destLen -= outStream.rem;
5191 +  if (outStream.overflow)
5192 +    return SZ_ERROR_OUTPUT_EOF;
5193 +  return res;
5194 +}
5195 +
5196 +SRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
5197 +    const CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeEndMark,
5198 +    ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig)
5199 +{
5200 +  CLzmaEnc *p = (CLzmaEnc *)LzmaEnc_Create(alloc);
5201 +  SRes res;
5202 +  if (p == 0)
5203 +    return SZ_ERROR_MEM;
5204 +
5205 +  res = LzmaEnc_SetProps(p, props);
5206 +  if (res == SZ_OK)
5207 +  {
5208 +    res = LzmaEnc_WriteProperties(p, propsEncoded, propsSize);
5209 +    if (res == SZ_OK)
5210 +      res = LzmaEnc_MemEncode(p, dest, destLen, src, srcLen,
5211 +          writeEndMark, progress, alloc, allocBig);
5212 +  }
5213 +
5214 +  LzmaEnc_Destroy(p, alloc, allocBig);
5215 +  return res;
5216 +}
5217 diff --git a/lib/lzma/Makefile b/lib/lzma/Makefile
5218 new file mode 100644
5219 index 000000000000..02e799c99381
5220 --- /dev/null
5221 +++ b/lib/lzma/Makefile
5222 @@ -0,0 +1,7 @@
5223 +lzma_compress-objs := LzFind.o LzmaEnc.o
5224 +lzma_decompress-objs := LzmaDec.o
5225 +
5226 +obj-$(CONFIG_LZMA_COMPRESS) += lzma_compress.o
5227 +obj-$(CONFIG_LZMA_DECOMPRESS) += lzma_decompress.o
5228 +
5229 +EXTRA_CFLAGS += -Iinclude/linux -Iinclude/linux/lzma -include types.h
5230 --
5231 2.11.0
5232