Page 1 of 2 12 LastLast
Results 1 to 30 of 40

Thread: Bit Archive Format

  1. #1
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hi everyone,
    I've decided to develop a new archive format: Bit Archive Format. The design goals are:

    1-Store "only" suffience data which needed by decompressing process. File timestamps/flags, encryption, large file support (>2GB), unicode characters, archive splitting etc. not necessary. We only need filename, file size, compressor identity and a data validation hash key (can be CRC32).

    2-Optimize archive format for DVD like media. The decompressor should read the archive by sequential access (not required any seeking). Also, file list should be fetched very quickly with squential access (ZIP like approach is not acceptable).

    3-Very extreme conditions "are not" a problem for the compression process. It can eat too large memory and too much CPU horsepower. But, the decompression process is very sensitive. It must not be very slow. The memory usage can be reach 100-150mb at decompression process. On the other hand, the compression should be better than ZIP at most cases.

    4-Patent issues are very big problem. So, arithmetic coding is not acceptable for entropy coding process. Range encoder is more suitable. The code itself can be open source or not (this is not very clear at this time)

    5-Executable, JPEG, Wave etc. prefilters "are not" necessary.

    A careful reader can guess why this kind format is needed. The answer is simple: for game development. A game or a simulation software will store all of the data such as collision maps, textures, videos, audio files in this format. Notice that, most files are in binary format.

    I think, ROLZ+Context Mixing+Range Coding based approach is the best choice at compression schema side. Because, ROLZ is highly asymmetric (slow compression / high decompression speed) and effective compression, Context Mixing is "very" effective compression, Range Coding is fast and patent free.

    QUAD seems very good place to start. I like it's fast and effective implementation. But, I would like to add context mixing instead of PPM. So, PAQ seems very bright at this point. But, new versions use extremely large memory. Also, they are highly symmetric. The decompression time can be very long

    I would like to thank Ilia Muraviev and Matt Mahoney for their excellent works.

    Do you have any idea about this work?

    P.S. : I'm not an expert at compression algorithms.

    Osman Turan
    BIT Archiver homepage: www.osmanturan.com

  2. #2
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Hi! Choosing the compression algorithm is up to you - there are many good open source projects! You may look at PPMd by Dmitry Shkarin - very good algorithm, but symmetric. With some options it has fast enough compression/decompression. LZMA is OK, however the source is too large and fat. Of course, you may use QUAD too, in addition it is possible to add some changes, for example, if target data has no x86 code (no EXE, DLL, OCX, etc. files) you may remove e8/e9 preprocessor from QUAD. Also with some extra changes you may change the buffer size and so on.

    With archive format there are many possibilities. You can look at Quake/Quake II source code to see how to organize very simple TAR-like archives. PIM archiver uses very simple archive format developed by me. Summarizing, the basic and simple archive formats are:

    [FILE HEADER 1]
    [COMPRESSED DATA 2]
    [FILE HEADER 2]
    [COMPRESSED DATA 2]
    ...

    As PIM archiver use - first, file header, after compressed file, and so on. Although, requires seeking.

    [ARCHIVE HEADER WITH FILE LIST]
    [COMPRESSED DATA]

    As PAQ archiver use.

    [ARCHIVE ID, POSITION OF A FILE LIST]
    [COMPRESSED/STORED DATA]
    [FILE LIST]

    As with .PAK (Quake) archives.

    Hope this helps.

    -- Ilia Muraviev

  3. #3
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Quote Originally Posted by osmanturan
    I think, ROLZ+Context Mixing+Range Coding based approach is the best choice at compression schema side. Because, ROLZ is highly asymmetric (slow compression / high decompression speed) and effective compression, Context Mixing is "very" effective compression, Range Coding is fast and patent free.

    QUAD seems very good place to start. I like its fast and effective implementation. But, I would like to add context mixing instead of PPM. So, PAQ seems very bright at this point. But, new versions use extremely large memory. Also, they are highly symmetric. The decompression time can be very long
    I already implemented ROLZ+CM - an older TC file compressor uses such thing. Having said that low order CM that you should use with ROLZ is not so efficient in terms of gained compression vs. speed. ROLZ by itself works pretty well, CM even better but much slower. Combining two algorithms you should perfectly balance two things, so they will work with each other and fit in each other. The LZP+CM scheme at some point is more efficient, LZP not kills the contexts needed for CM and also compresses much faster.
    Anyway, with my latest project LZPM, I kept the latest version of my ROLZ+simple order-1 arithmetic coding - i.e. no CM, no PPM and other things. Overall, LZPM has a higher compression than QUAD, needs less memory for decompression, and has a MUCH faster decompression. However, LZPM is NOT open source and still under development.

    -- Ilia Muraviev


  4. #4
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by encode
    You may look at PPMd by Dmitry Shkarin - very good algorithm, but symmetric. With some options it has fast enough compression/decompression. LZMA is OK, however the source is too large and fat. Of course, you may use QUAD too, in addition it is possible to add some changes, for example, if target data has no x86 code (no EXE, DLL, OCX, etc. files) you may remove e8/e9 preprocessor from QUAD. Also with some extra changes you may change the buffer size and so on.
    I think, you are able to read my mind! Because, I have looked at PPMd and PPMz 2. They are not good enough (highly symmetric). LZMA is good for most cases. But, the code is very fat. QUAD is good and had a very compact code. But, sometimes its worse than ZIP. Ive played with QUAD source. First of all, I had removed the E8/E9 transform. Also, I had notice that matching algorithm is not very optimal (maybe Im wrong at this point). Instead of PPM, I had decided to use PAQ like CM approach.

    So, I tried to figure out PAQ implementation details. While playing with FPAQ0 source, I had a trouble. I combined PAQ predictor with simple range encoder (for patent issues). The range coder is very similar to LZMA and QUAD implementations. But, I noticed, sometimes FPAQ0s predictor can produces zero probability. This value causes entering infinite loop in range coder. Matt, can you help me?

    By combining all of them, I may use LZPM like approach. Because, I dont want to use too much messy things.

    On archive side, this structure seems good enough:

    [Archive Header]
    [File List]
    [File #0 Data]
    [File #1 Data]
    ...
    [File #n] Data]

    Ive decided to compress File List chunk. This can be very good for games. Because, they may consist too much files in an archive.

    @encode: Thanks for fast reply!

    Osman Turan
    BIT Archiver homepage: www.osmanturan.com

  5. #5
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hi again!
    I've played at all with ROLZ + bit oriented range coding. The compression seems superior (better than ZIP at almost any cases!!!). But, the decoding phase has not been implemented completely. So, these results can be wrong.

    Anyway, let me ask some question:
    - Any "pre" or "post" processing can help compression for ROLZ + Range Coding? Previously, I have written a small program which implements BWT or BWT+MTF transform in 16-1024 kB chunks. I preprocess a binary file with BWT and BWT+MTF before ROLZ + Range Coding. But, lower compression was achived Maybe, we can encode ROLZ's literal symbols with BWT+MTF before range coding. How you got any idea about "pre" or "post" processing for ROLZ?

    - If I'm not wrong, order-n means consider with n symbols. Isn't it? So, does "order-n bit oriented range coding" mean that?

    [i]// SymbolBitCount -> Maximum used bits by any symbol (eg. 8bits)
    // MaxOrder -> order-n (n=MaxOrder)
    // _context -> Current context index
    // _order -> Current order index

    template <int SymbolBitCount, int MaxOrder>
    class OrderNthEncoder
    {
    private:
    BitModelEncoder _models[(1 << (SymbolBitCount * (MaxOrder + 1) + 1))];
    UInt32 _context;
    UInt32 _order;
    UInt32 _modelCount;
    public:
    OrderNthEncoder()
    {
    Init();
    }

    void Init()
    {
    _context = 1;
    _order = 0;
    _modelCount = (UInt32)(1 << (SymbolBitCount * (MaxOrder + 1) + 1));

    for (int i=0; i < _modelCount; i++)
    _models.Init();
    }

    void EncodeSymbol(RangeEncoder* encoder, UInt32 symbol)
    {
    for (int i = SymbolBitCount-1; i >= 0; i--)
    {
    Byte bit = (Byte)((symbol >> i) & 1);
    _models[_context].Encode(encoder, bit);
    _context = (_context << 1) | bit;
    }

    _order++;

    if (_order > MaxOrder)
    {
    _order = 0;
    _context = 1;
    }
    }
    };


    This code seems a bit hungry For 9-bits literal symbols at order-1 needs ~2 MB.

    Thanks a lot

    Osman Turan
    BIT Archiver homepage: www.osmanturan.com

  6. #6
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @encode:
    Instead of hashing, do you benefit suffix trees? What is the advantages for ROLZ side? Can be fast enough? Sorry for lots of question about ROLZ. But, as you know there isn't any good place for playing with ROLZ (no article, almost no source code)

    Thanks again
    BIT Archiver homepage: www.osmanturan.com

  7. #7
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Quote Originally Posted by osmanturan
    - If Im not wrong, order-n means consider with n symbols. Isnt it? So, does "order-n bit oriented range coding" mean that?
    Yep. It means previous N bytes + part of the current coded byte. Look at the PAQ source code (PAQ1 for example).

    Quote Originally Posted by osmanturan
    @encode:
    Instead of hashing, do you benefit suffix trees?
    LZPM v0.13 uses hash chains - i.e. no suffix trees.

    Quote Originally Posted by osmanturan
    What is the advantages for ROLZ side? Can be fast enough?
    One of the advantages is a fast compression. Using greedy parsing or lazy matching ROLZ based compressors can be fairly fast. However, if we consider optimal or near optimal parsing we may face with the slow and very slow compression. Im talking about my implementations. Why faster? Its due to we search initially longer strings. With LZ77 we start searching for previous 2 or 3-byte strings, with ROLZ we start searching for 3 or 4-byte ones. In addition, the advantage of ROLZ is that we achieve more optimal parsing even without any optimizations of a parsing. Better read papers about LZRW4, LZ77-PM, etc.

    Good luck!

  8. #8
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    The article on ROLZ (Russian) written by me:
    http://ru.wikipedia.org/wiki/ROLZ


  9. #9
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    Quote Originally Posted by osmanturan
    4-Patent issues are very big problem. So, arithmetic coding is not acceptable for entropy coding process. Range encoder is more suitable. The code itself can be open source or not (this is not very clear at this time)
    Arithmetic coding and range coding are the same thing. In any case the original patent is expired. Some speedup tricks like the Q, MQ and QM coders by IBM are still patented, but you would not want to use them anyway because the compression is not as good.

    Another alternative is Jarek Dudas asymmetric binary coder which he described on comp.compression
    http://groups.google.com/group/comp.compression/br owse_thread/thread/fdc61014c8a3a971#

    He says it is not patented. Yesterday I posted the very first implementation, fpaqa at http://cs.fit.edu/~mmahoney/compression/#fpaq0 , but my code is about twice as slow as an equivalent arithmetic coder. Otherwise it could replace the coder in PAQ, LPAQ, BBB, SR2, and the dozens of other programs that use the arithmetic coders from these programs. In theory it should be faster because it uses lookup tables instead of multiplication and division, and the tables fit in L2 cache. So I need to solve the performance problems before I put it in my other programs.

  10. #10
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    Quote Originally Posted by osmanturan
    So, I tried to figure out PAQ implementation details. While playing with FPAQ0 source, I had a trouble. I combined PAQ predictor with simple range encoder (for patent issues). The range coder is very similar to LZMA and QUAD implementations. But, I noticed, sometimes FPAQ0s predictor can produces zero probability. This value causes entering infinite loop in range coder. Matt, can you help me?
    The model returns a 12 bit number p in the range 0 to 4095. Try,

    p += (p < 204;

  11. #11
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    By the way, Matt, in your opinion what probability update rule is the best:

    1.
    if (y) pr += ((4096 - pr) >> 5);
    else pr -= (pr >> 5);

    2.
    pr += (((y << 12) - pr) >> 5);
    // or
    pr += ((((y << 12) - pr) >> 5) + (pr < 204);

    3.
    if (y) pr += ((65536 - pr) >> 5);
    else pr -= (pr >> 5);
    // (P() = pr >> 4)

    Do you think in third case the probability is more precise?


  12. #12
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts
    Quote Originally Posted by Matt Mahoney
    In theory it should be faster because it uses lookup tables instead of multiplication and division
    thats amazing! it will change half of freearc compression algorithms

  13. #13
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hi again,
    Finally, I've figured out my funny mistake in decompression code. By the way, I've published on my site:

    http://www.osmanturan.com/bit.zip (8 kB)


    Some Notes about Bit Compressor:
    -------------------------------------------------- ----------
    + Optimized for game binary files. So, doesn't includes any special filters such as E8/E9, JPEG, PDF etc.
    + Optimized buffered file access
    + ROLZ + Range Coding

    Planned for Next Version
    -------------------------------------------------- ----------
    + Unrolled copy for matched literals (simply means faster decompression)
    + Optimizing for order-4 context (most of game binaries coded in 32-bits integers/floats. I think, this would bring better compression. Have you got any idea?)


    Test #1 File (Taken from "Enemy Territory: Quake Wars" game)
    -------------------------------------------------- ----------
    valley.cmb (Binary Collision Map): 19.776.230 bytes


    Test #2 File:
    -------------------------------------------------- ----------
    Calgary Corpus (TAR version): 3.152.896 bytes


    Test Platform (Asus based Laptop):
    -------------------------------------------------- ----------
    Intel Core 2 Duo T7500 @ 2.20 GHz
    2 GB RAM
    Vista Business x64 Edition
    (Took 4,7 Windows Experience Index)

    Test #1 (valley.cmb)
    -------------------------------------------------- ----------
    1 - 7zip (LZMA-Ultra) -> 7.507.360 bytes
    2 - WinRK (ROLZ3-Best) -> 7.552.372 bytes
    3 - WinRAR (RAR-Max) -> 8.511.238 bytes
    4 - LZPM 0.13 (9) -> 9.487.875 bytes
    5 - BIT 0.1 -> 9.569.057 bytes
    6 - PIM -> 9.633.796 bytes
    7 - WinRAR (ZIP-Max) -> 9.887.176 bytes
    8 - QUAD (-x) -> 10.017.449 bytes
    9 - SR2 -> 11.570.404 bytes
    10 - P12 -> 11.925.115 bytes

    Bit Compressor Timing
    Compression: 13,7 seconds
    Decompression: 4,4 seconds

    Test #2 (Calgary Corpus)
    -------------------------------------------------- ----------
    1 - WinRK (ROLZ3-Best) -> 707.151 bytes
    2 - WinRAR (RAR-Max) -> 762.171 bytes
    3 - 7Zip (LZMA-Ultra) -> 822.483 bytes
    4 - P12 -> 832.036 bytes
    5 - PIM -> 857.700 bytes
    6 - LZPM 0.13 (9) -> 862.762 bytes
    7 - QUAD (-x) -> 873.681 bytes
    8 - Bit 0.1 -> 952.156 bytes
    9 - SR2 -> 979.349 bytes
    10 - WinRAR (ZIP-Max) -> 1.021.959 bytes

    Bit Compressor Timing
    Compression: 2,2 seconds
    Decompression: 0,5 seconds


    As you see, on binary files compression ratio is much better (this is main target). I don't mind text compression.


    Thanks everyone

    Osman Turan
    BIT Archiver homepage: www.osmanturan.com

  14. #14
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @Matt Mahoney:
    I'm aware of Q, MQ and QM coders. They roughly mean approximated arithmetic coders if I'm not wrong. Although, they are fast. Especially suitable for image processing (JPEG2000 uses MQ coder). Firstly, I have played with Mark Nelson order-0 arithmetic coder. It's slow for me. Then I promoted to FastAC. It's very fast but the code are very messy (I like simple codes). I've heard arithmetic coding patents are not clear. Also, I heard lots of people using range coding instead of arithmetic coding. I found range coding enough simple besides about twice fast arithmetic coding. So, I want to use range coding.

    @Encode & Matt Mahoney
    For 32-bits aligned data structure (lots of integer and floats), do you benefit order-4 context for ROLZ coding? Or do you have any practical idea? I mean usable for real-life situations (good compression / fast decompression)

    Thanks again
    BIT Archiver homepage: www.osmanturan.com

  15. #15
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Quote Originally Posted by osmanturan
    For 32-bits aligned data structure (lots of integer and floats), do you benefit order-4 context for ROLZ coding? Or do you have any practical idea? I mean usable for real-life situations (good compression / fast decompression)
    Some papers described that order-1 is the best, Malcolm Taylor also found that with ROLZ order-1 context works the best. QUAD uses order-2 context along with order-2-0 PPMC with Full Exclusions. LZPM with order-1 context and simple order-1 arithmetic coder outperforms QUAD. So I think a higher order will not work!


  16. #16
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,565
    Thanks
    220
    Thanked 146 Times in 83 Posts
    Intel Core duo 2 E6600 2GB of Ram
    The Bit compressor not works and me from the following message :
    "Impossible to execute the specified program"
    Help me! Hi!

  17. #17
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Same here!
    bit.exe:
    The system cannot execute the specified program.


  18. #18
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    I've compiled with Visual Studio 2008 Beta 2. It can requires Visual Studio 9 Run-time Library. So, I've embedded the the library and recompiled it. It must be run now. Can you download same link again? Also, I was changed the code a bit. So, compression results can be different! (New Link 36kB!)
    BIT Archiver homepage: www.osmanturan.com

  19. #19
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,565
    Thanks
    220
    Thanked 146 Times in 83 Posts
    Intel Core duo 2 E6600 2GB of Ram
    TEST RESULTS

    BIT COMPRESSOR

    ENWIK8: 31.186.930 in 40,110 SEC.
    SFC: 13.409.054

  20. #20
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @nania:
    Notice that given timing values are in microseconds!!! not seconds!!!
    BIT Archiver homepage: www.osmanturan.com

  21. #21
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,565
    Thanks
    220
    Thanked 146 Times in 83 Posts
    @Osmanturan
    40.110 ms
    are
    40,110 sec.
    or Not
    Hi!

  22. #22
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Quote Originally Posted by osmanturan
    Hi again,
    Finally, Ive figured out my funny mistake in decompression code. By the way, Ive published on my site:

    http://www.osmanturan.com/bit.zip (8 kB)
    Thanks Osman!

  23. #23
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Ive done some experiments based on Shelwien and Ilias valuable ideas. Thanks a lot again. Ive played with literal / match length encoding phase in my compressor. But, the results are "strange" Ive compressed two binary game files in one archive (not solid archived). These are part of a map in ETQW game (Valley). Here is the file details:

    valley.cmb: 19.776.230 bytes (Collision map)
    valley.procb: 30.252.762 bytes (Rendering map)
    Total: 50.028.992 bytes
    Here is the test results:

    1-Low Precision (12 bits) Simple Order-1: 18.127.557 bytes
    2-Low Precision (12 bits) Static-Mixed Rate Order-0 (a): 18.208.081 bytes
    3-Low Precision (12 bits) Static-Mixed Rate Order-0 (b): 44.256.268 bytes
    4-High Precision (16 bits) Static-Mixed Order-0 (a): 18.205.126 bytes
    5-High Precision (16 bits) Static-Mixed Order-0 (b): 50.656.170 bytes
    6-High Precision (16 bits) Static Mixed Order-1 (a): 18.337.811 bytes
    In "a" marked tests have done with following lines (following example for just high precision):

    if (y == 0)
    {
    _p1 += ((65536 - _p1) >> 4);
    _p2 += ((65536 - _p2) >> 6);
    }
    else
    {
    _p1 -= (_p1 >> 4);
    _p2 -= (_p2 >> 6);
    }

    _prob = (_p1 + _p2) >> 5;
    In "b" marked tests only following line has changed:
    if (y != 0)
    ...
    I think, these results are very strange for me. I nearly get crazy Can anybody explain what was happened? Only left thing for me just using Shelwiens brillant dynamic mixer with order 1-0.

    Osman Turan
    BIT Archiver homepage: www.osmanturan.com

  24. #24
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    Well, in your first quote p1 and p2 look like probabilities of zero.
    So if its in the end encoded like a probability of 0 too, no wonder
    that you get large files from using inverse probability for encoding...

  25. #25
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @Shelwien:
    Well, you are right. What a pitty! I have forgotten that my range coder based on zero probabilities What a shame!
    BIT Archiver homepage: www.osmanturan.com

  26. #26
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    2 osmanturan:
    By the way, can you explain some details about your ROLZ implementation:
    + What kind of a context do you use with ROLZ match finder?
    + How do you encode the LZ output (literals, match lengths, etc.)?
    + What kind of parsing do you use?


  27. #27
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    There isnt any "real" changes in ROLZ implementation with yours (QUAD). Currently, Im focusing on literals / match lengths and match index. After that, I will focus on ROLZ part. Currently, match index seems very crazy. They cannot be modelled easily. So, order-0 seems good for now. Literals / match lengths encoded with simple order-1. I tried "tricky" way of changing probability rate. But, it was no good. So, next time Ill try Shelwien dynamic mixer with order-1-0 for literal / match lengths. Also, when I change ROLZ index 1024 instead of 64. Its very slow. So, bit tree like approach become very necessary. I think, I havent understood ROLZ algorithm completely. This is the answer for why Im playing entropy coding currently.

    Note that, Im not an expert on data compression. On the other hand, I believe that I can highly optimize some programs (espacially simulation / renderers). But, for long time Ive played with delphi. Its code generation is seems perfect! When I moved C/C++, it was like watching horror film at midnight for me! Untyped pointers, tons of unnecessary states, very low level string manipulation etc etc. Also, I noticed that Visual C++ compiler is extremely awful! For example, I notice decompression can be faster in your implementation by optimizing memory block copying. Ive noticed your simple copy code:

    while (--s >= 0)
    _buffer[i++] = _buffer[p++];
    Firstly, I have changed this code with my previous implementation of unrolled memory copying with assembly code. It was highly optimized for common CPUs. Also, there are MMX and pure delphi version, too. But, they are very slow in Visual C++ compiler!!! So, I changed my pure delphi code (which is very similar approach for raw assembly version) to pure C code. The code is:

    int remain = s & 3;
    switch (remain)
    {
    case 3: _buffer[i++] = _buffer[p++];
    case 2: _buffer[i++] = _buffer[p++];
    case 1: _buffer[i++] = _buffer[p++];
    }

    s -= remain;

    // copy 4 byte per iteration
    if (s > 0)
    {
    UInt32* pSrc = (UInt32*)&_buffer[p];
    UInt32* pDst = (UInt32*)&_buffer[i];
    i+=s;
    p+=s;
    s>>=2;

    while (--s >= 0)
    *pDst = *pSrc;
    }
    When I disassembled my code, I noticed that Visual C++ extremely bad handling of my code. Very bad "switch" handling, tons of unnecessary moves etc. When I changed this algorithm in optimized assembly, compiler became panic! The program run slower

    What about your implementation details?

    Osman Turan
    BIT Archiver homepage: www.osmanturan.com

  28. #28
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Quote Originally Posted by osmanturan
    What about your implementation details?
    Actually, LZPM is a next step. You can see how I progressed from LZPX thru QUAD and other compressors to the LZPM.
    LZPM has the near optimal parsing, its still not the optimal, but really better than QUADs one. LZPM also combines dozens of new ideas, from string searching to parsing and other things. By the way, LZPM 0.14 will have another improvements, making even further step.
    I try to optimize what is really necessary to optimize. Not rushing with optimizations but keeping an eye on optimized C++ code.


  29. #29
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    That's all? It is too short brief, isn't it?
    BIT Archiver homepage: www.osmanturan.com

  30. #30
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Quote Originally Posted by osmanturan
    It is too short brief, isnt it?
    Well, describing the LZPM can take as much space as "War and Peace" with French comments... Having said you can search thru this forum as well as comp.compression group for LOTS of stuff!

Page 1 of 2 12 LastLast

Similar Threads

  1. BIT Archiver
    By osmanturan in forum Data Compression
    Replies: 137
    Last Post: 16th January 2009, 20:19
  2. StuffIt X Format
    By maadjordan in forum Data Compression
    Replies: 19
    Last Post: 9th August 2008, 13:03
  3. Universal Archive Format
    By Bulat Ziganshin in forum Data Compression
    Replies: 1
    Last Post: 9th July 2008, 00:54
  4. New archive format
    By Matt Mahoney in forum Forum Archive
    Replies: 9
    Last Post: 25th December 2007, 12:22
  5. UZ2 file format
    By encode in forum Forum Archive
    Replies: 0
    Last Post: 12th July 2007, 23:00

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •