Bit Archive Format

[osmanturan]

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

[encode]

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

[encode]

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

[osmanturan]

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

[osmanturan]

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

[osmanturan]

@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

[encode]

- 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).

@encode:
Instead of hashing, do you benefit suffix trees?

LZPM v0.13 uses hash chains - i.e. no suffix trees.

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!

[encode]

The article on ROLZ (Russian) written by me:
http://ru.wikipedia.org/wiki/ROLZ

[Matt Mahoney]

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.

[Matt Mahoney]

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;

[encode]

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?

[Bulat Ziganshin]

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

[osmanturan]

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

[osmanturan]

@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

[encode]

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!

[Nania Francesco]

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!

[encode]

Same here!
bit.exe:
The system cannot execute the specified program.

[osmanturan]

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!)

[Nania Francesco]

Intel Core duo 2 E6600 2GB of Ram
TEST RESULTS

BIT COMPRESSOR

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

[osmanturan]

@nania:
Notice that given timing values are in microseconds!!! not seconds!!!

[Nania Francesco]

@Osmanturan
40.110 ms
are
40,110 sec.
or Not
Hi!

[LovePimple]

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!

[osmanturan]

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

[Shelwien]

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...

[osmanturan]

@Shelwien:
Well, you are right. What a pitty! I have forgotten that my range coder based on zero probabilities What a shame!

[encode]

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?

[osmanturan]

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

[encode]

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.

[osmanturan]

That's all? It is too short brief, isn't it?

[encode]

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!