#1200 Split memory for compression

[Shell]

7-Zip cannot use all of the address space due to its fragmentation. Depending on the OS, the maximal dictionary for 32-bit 7-Zip may be 128M or 192M. This limit can be increased to 256M (or even to 384M for 64-bit systems) by enabling /3GT (7-Zip is already LARGEADDRESSAWARE) and allocating scattered buffers.

For example, on Vista x86 with SP2 the address space layout is as follows:
00000000 - 003FFFFF: stacks, heaps and other stuff
00400000 - 0044FFFF: 7z.exe
00450000 - 0199FFFF: heaps, locale data
019C0000 - 0FFFFFFF: free space (230M)
10000000 - 100FFFFF: 7z.dll
10100000 - 75A8FFFF: free space (1625M)
75A90000 - 7762FFFF: system DLLs and some free space
77630000 - 7F6EFFFF: free space (128M)
7F6F0000 - 7FFFFFFF: system reserved (TEBs, PEB, etc.)
80000000 - BFFFFFFF: free space (1024M)
7-Zip has about 3008M available, but due to contiguous allocation it can use only 1625M, which is not enough even for 192M dictionary. Another example, for XP x86 SP2, is shown in http://forall.ru-board.com/egor23/online/FAQ/Virtual_Memory/Limits_Virtual_Memory.html.

I suggest the following.

1. Change the base address of 7z.dll to something like 02000000 (or even 00400000, deliberately conflicting with 7z.exe, to force its relocation to the lowest available block). This will enable 192-MiB dictionary even without /3GT and it is extremely easy to implement. Dynamic DLL loading and removing unnecessary DLLs will also free some memory (for example, I find it impractical for 7z.exe to link to USER32 for the sake of the single call to CharUpper; the latter may be replaced with LCMapString from KERNEL32).
2. As a further step, allocate bigger memory blocks first. For example, when using a 128M dictionary, three allocations are made: for 64K, for 192M and eventually for 1152M. Extrapolating to 192M dictionary, these will be 64K, 288M and 1728M, the latter will not fit the address space. However, if 7z.dll were reallocated, then the request for 1728M might succeed when issued first (or, perhaps, straight after the 64K-one). Being the next, the 288M-request may fail without /3GT, but with /3GT it will succeed with a block on 80000000. This is also easy to implement (however, it may require more testing than simple rebasing).
3. Finally, I suggest to allocate workspace in more than 3 calls, which may overcome memory fragmentation. Does the 9-times-the-dictionary block really need to be contiguous? If not, it should be broken down into smaller allocation units to fully utilize the address space.

I understand that squeezing the rest from 32-bit systems is not a top-priority task, but 32-bit Windows do not seem to cease yet. Please, consider implementing a technique similar to those mentioned above.

[Shell]

I have succeeded in using a 192M dictionary in 7-Zip 15.01 on a 3GB-tuned x86 system by patching 7z.dll. The equivalent changes in source code are:
1) define kDicLogSizeMaxCompress in LzmaEnc.c as 0x0C000000;
2) patch BigAlloc (I think it is that function) in Alloc.c to include MEM_TOP_DOWN flag;
3) rebase 7z.dll to 0x02000000.
There are 4 allocations: 64K, 4M, 290M and 1792M. The first one seems to be made by unpatched MidAlloc and goes somewhere below 0x02000000. The next two allocations are made from the top of address space, leaving a big block below 2GB. Finally, the request for 1792M fits the contiguous block just below system DLLs.

Unfortunately, 256M dictionary requires a memory block exceeding 2GB, so split allocation is necessary on x86 systems.

[Igor Pavlov]

It will not work in most cases.
kNumLogBits must be changed in source code.
It cannot be patched in exe file. Some structure changes the size after changing kNumLogBits.

It's not difficult to support more than 128 MB dictionary in 32-bit version. But it can be useless for most users. So I don't implement it.

[chfakht]

What about working on an embedded target when ressources such as RAM are very small < 1Mb

[Shell]

I have already mentioned an idea of discarding the RAM buffer and reading back from flash memory, but other tricks may be impossible for some compression methods. In general, you should use completely different algoritm to achieve noticeable gain in speed or memory needs.

[chfakht]

What about RAM usage for decompression , i have found that it require just state size : 16kb + dictSize (4kb) right ? but i found in apost igor saying that it requires at least 1 mb of RAM doe decoding

[Shell]

it require just state size : 16kb + dictSize (4kb)

Technically, it is sufficient (if the state size is really 16k), but the implementation may require more RAM. Trace the allocation calls and you will find out how much RAM do you need. Some allocations can be avoided (e.g. file buffers), some cannot. Unfortunately, I don't know the details - find that out in your debugger.

[chfakht]

you'll right (that what i have found ) i'm the one working on reducing flashing time of an MCU :) i have start debugging code but it will require some time , thnanks a lot for your replies

[chfakht]

Yes the Decoder doesn't need much memory to work with. I have now a problem on applying multi-CALL decompression on streams since i cannot alocate a big static buffer to work with neither can allocate memory using malloc. The problem with multi-call decompression is that wa cannot predict how much compressed size it will be used to output X size (after decoder finishes)

[Shell]

Why don't you write your own malloc? You can allocate a big static array in 7zAlloc.c and modify the functions therein to use that array as a heap. You can find an example in Kernighan & Ritchie. Single-threaded code is straightforward, and in case of multithreading you should use critical sections.

[chfakht]

That what i have done for the decoder to work with a static buffer. But now i'm trying to do some sort of multi-call decompression to be able to allocate just the needed size like in defaut interface where we need to allocate input/output buffer only not using a big buffer for the whole file.
I have tried the following code that i have writen based on FILE version:
**
i'm doing decompression from Stream to stream**
My main function in LzmaUtil.c

The code worked fine if i decode the entire file but i couldn't make it work for just the desired size

In my situation, when using 2000 with default version i could get 3819 of decoded size with right result.However when with this method i have modified i get extra unwanted bytes for a size of 3822 (i can't find out why and the first 3819 are OK)

It's been a while since i'm in this blocking point and i wich you could help me out.I'm sure i'm doing something wrong !!!

#define _use_limitation   // Decode just the desired size

#ifndef _use_limitation
    #define real_size   8464  // original file size
    #define comp_size   3869  // size of the encoded file
#else
    #define real_size   4000   // size to be decoded
    #define comp_size   2000  // size to use from the encoded size 
#endif

int MY_CDECL main(int numArgs, const char *args[])
{
    struct stat info;
    const char *filename = args[1];
    int l = 0;
    if (stat(filename, &info) != 0) {
        /* error handling */
    }

    Byte content[comp_size];
    Byte header[13];
    FILE *fp = fopen(filename, "rb");
    size_t headerSize = 13;  
    fseek(fp, 0, SEEK_SET);
    size_t header_read = fread(header, headerSize, 1, fp);
    fseek(fp, 13, SEEK_SET); 
    size_t blocks_read = fread(content,comp_size - headerSize, 1, fp);
        fclose(fp);

    /* <---- Read encoded binary file to stream and start Decoding ---->  */

    Byte c;
    Byte xy[real_size];   
    size_t xyLen      = real_size; 
    size_t contentLen = comp_size - headerSize;

/* To be sure extraction went OK !!! */
    FILE *fc = fopen("EncodedContent", "wb+");
    for (l = 0; l < contentLen; l++)
    {
        fputc(content[l], fc);
    }
    fclose(fc);


    unsigned char outPropz[LZMA_PROPS_SIZE];
    size_t outPropsSize = LZMA_PROPS_SIZE;

 LzmaUncompress(xy, &xyLen, content, &contentLen, header, outPropsSize);

  printf("\nSaving decompressed stream to a file for testing .... \n All Done\n");

  FILE *fd = fopen("decompressedResult","wb+");

  for (l = 0; l < xyLen; l++)
  {
      fputc(xy[l], fd);
  }
  fclose(fd);

  return 0;
}

In LzmaDec.c (i have made some change from LzmaDecode to LzmaMultiDecode)

#define IN_BUF_SIZE  (1 << 8)
#define OUT_BUF_SIZE (1 << 8)

SRes LzmaMultiDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
    const Byte *header, unsigned propSize, ELzmaFinishMode finishMode,
    ELzmaStatus *status, ISzAlloc *alloc)
{
    UInt64 unpackSize = 0, sizeLimit = 0, iBuf=0;
    int i;
    SRes res = 0;
    FILE *fdec=NULL,*fenc=NULL,*fsrc=NULL;
    CLzmaDec state;
    int thereIsSize = (unpackSize != (UInt64)(Int64)-1);
    Byte inBuf[IN_BUF_SIZE];
    Byte outBuf[OUT_BUF_SIZE];
    size_t inPos = 0, inSize = 0, outPos = 0, cv = 0, lp = 0, psX = 0;

    for (i = 0; i < 8; i++)
        unpackSize += (UInt64)header[LZMA_PROPS_SIZE + i] << (i * 8);

    LzmaDec_Construct(&state);
    RINOK(LzmaDec_Allocate(&state, header, LZMA_PROPS_SIZE, &g_Alloc));
    printf("\nLzmaMultiDecode: Source Length is %d\n", *srcLen);

    /////////////////// Call to Decode2 //////////////////////////////
    LzmaDec_Init(&state);
    printf("\n srcLen: %d", *srcLen);

    fdec = fopen("fdec", "wb+");
    fenc = fopen("fencode","wb+");
    fsrc = fopen("fsrc", "wb+"); // w overwrite file / a to append

    /* We verify the encoded stream */
    for (cv = 0; cv < *srcLen; cv++){
        fputc(src[cv], fsrc);
    }
    for (;;)
    {
        printf("\nEnter for loop %d\n", lp++);
        if (inPos == inSize)
       {  // We enter only once at this condition
            printf("inPos: %d == inSize: %d \n",inPos,inSize);
            inSize = IN_BUF_SIZE; 
            memcpy(inBuf, src, inSize); // 
            src += inSize;
            inPos = 0;
            iBuf = 0;
       }
       {   
        SRes res;
        SizeT inProcessed = inSize - inPos;
        SizeT outProcessed = OUT_BUF_SIZE - outPos;
        ELzmaFinishMode finishMode = LZMA_FINISH_ANY;
        ELzmaStatus status;
        if (thereIsSize && outProcessed > unpackSize)
        {
            outProcessed = (SizeT)unpackSize;
            finishMode = LZMA_FINISH_END;
        }
        res = LzmaDec_DecodeToBuf(&state, outBuf + outPos, &outProcessed,
            inBuf + inPos, &inProcessed, finishMode, &status);
            inPos += inProcessed;
            outPos += outProcessed;
            unpackSize -= outProcessed;
            printf("\n outPos: %d |outProcessed: %d | inPos: %d |"
                  "inProcessed:%d \n", outPos, outProcessed, inPos, inProcessed);
        for (cv = 0; cv < inProcessed; cv++)
        {
            fputc(inBuf[iBuf], fenc);
            iBuf++;
        }

        memcpy(dest, outBuf,outProcessed);
        dest = dest + outProcessed;

        for (cv = 0; cv < outPos; cv++)
        {
            fputc(outBuf[cv], fdec);
            //dest[cv] = outBuf[cv];    
        }

         // instead of if (outStream->Write(outStream, outBuf, outPos) != outPos)

        outPos = 0;


        if (res != SZ_OK || (thereIsSize && unpackSize == 0))
            return res;

        if (inProcessed == 0 && outProcessed == 0)
        {
            if (thereIsSize || status != LZMA_STATUS_FINISHED_WITH_MARK)
                return SZ_ERROR_DATA;
            return res;
        }
        if (sizeLimit >= *srcLen) return res;   // Size limitation
       }
    }
    fclose(fdec);
    fclose(fenc);
    fclose(fsrc);
    ////>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<//////////



    LzmaDec_Free(&state, &g_Alloc);
    return res;
}

thanks a lot , you're helping me a lot :)

[chfakht]

OK for now static allocation has worked for me , i have also implmented successfully the multi-decompression on the MPC .... the objects file takes about 30 kb , i don't know id there is a way to optimize the LzmaDec.c more to reduce it size of 15 kb (in my case i use only the decoder and i have delete the encoder part) thanks again