bsc, new block sorting compressor

[Gribok]

bsc is a high performance file compressor based on Block Sorting, Lossless Data Compression Algorithm with following features:

• The source code is available under LGPL license.
• 64 bit and multi-core systems support.
• Highly optimized code and C++ interface for superior performance.
• Adjustable block size and multiple algorithms that allows software fine-tuning for maximum speed or compression efficiency.
• CRC-32 calculation routine for data integrity verification.
• Inplace compression and decompression to save memory.

Typically, bsc outperform other block-sorting compression programs like bzip2 by speed and/or compression. You can also find results of independent testing on www.compressionratings.com website where bsc is currently ranked in Top3 in Database1, Image1, Medical1, Medical2, PGN1, Source1, Text1 and Text2 tests.

Program memory usage = 5 * blocks size * number of cores.

Maximum compression mode:

libbsc:   enwik8 | 100000000 byte |  20774428(20.8%) byte | 19.505 sec |  8.339 sec
libbsc:  mozilla |  51220480 byte |  15844590(30.9%) byte |  8.037 sec |  4.984 sec
libbsc:  webster |  41458703 byte |   6424903(15.5%) byte |  7.057 sec |  2.800 sec
libbsc:      nci |  33553445 byte |   1188042(03.5%) byte |  3.648 sec |  1.373 sec
libbsc:    samba |  21606400 byte |   3867609(17.9%) byte |  2.434 sec |  1.289 sec
libbsc:  dickens |  10192446 byte |   2249282(22.1%) byte |  1.657 sec |  0.831 sec
libbsc:     osdb |  10085684 byte |   2205197(21.9%) byte |  1.693 sec |  0.971 sec
libbsc:       mr |   9970564 byte |   2199675(22.1%) byte |  1.367 sec |  0.767 sec
libbsc:    x-ray |   8474240 byte |   3749314(44.2%) byte |  1.672 sec |  1.044 sec
libbsc:      sao |   7251944 byte |   4671640(64.4%) byte |  1.646 sec |  1.175 sec
libbsc:  reymont |   6627202 byte |    978594(14.8%) byte |  0.895 sec |  0.442 sec
libbsc:  ooffice |   6152192 byte |   2549304(41.4%) byte |  0.951 sec |  0.720 sec
libbsc:      xml |   5345280 byte |    380586(07.1%) byte |  0.363 sec |  0.164 sec
libbsc: interrup |   5134954 byte |    779462(15.2%) byte |  0.506 sec |  0.291 sec
libbsc:   enwik5 |   5000000 byte |   1204507(24.1%) byte |  0.656 sec |  0.403 sec
libbsc:    book1 |    768771 byte |    212516(27.6%) byte |  0.094 sec |  0.051 sec

Optimal compression mode:

libbsc:   enwik8 | 100000000 byte |  22790295(22.8%) byte |  4.534 sec | 12.061 sec
libbsc:  mozilla |  51220480 byte |  15332607(29.9%) byte |  3.684 sec |  6.018 sec
libbsc:  webster |  41458703 byte |   7027109(16.9%) byte |  1.599 sec |  3.833 sec
libbsc:      nci |  33553445 byte |   1781051(05.3%) byte |  0.701 sec |  1.362 sec
libbsc:    samba |  21606400 byte |   4173647(19.3%) byte |  1.079 sec |  1.509 sec
libbsc:  dickens |  10192446 byte |   2383762(23.4%) byte |  0.483 sec |  0.936 sec
libbsc:     osdb |  10085684 byte |   2263085(22.4%) byte |  0.662 sec |  1.013 sec
libbsc:       mr |   9970564 byte |   2252895(22.6%) byte |  0.471 sec |  0.891 sec
libbsc:    x-ray |   8474240 byte |   3795320(44.8%) byte |  0.676 sec |  1.423 sec
libbsc:      sao |   7251944 byte |   4649176(64.1%) byte |  1.115 sec |  1.291 sec
libbsc:  reymont |   6627202 byte |   1199282(18.1%) byte |  0.260 sec |  0.413 sec
libbsc:  ooffice |   6152192 byte |   2557957(41.6%) byte |  0.495 sec |  0.749 sec
libbsc:      xml |   5345280 byte |    488624(09.1%) byte |  0.158 sec |  0.252 sec
libbsc: interrup |   5134954 byte |    817568(15.9%) byte |  0.197 sec |  0.334 sec
libbsc:   enwik5 |   5000000 byte |   1242560(24.9%) byte |  0.246 sec |  0.451 sec
libbsc:    book1 |    768771 byte |    217585(28.3%) byte |  0.056 sec |  0.055 sec

Fast compression mode:

libbsc:   enwik8 | 100000000 byte |  24258736(24.3%) byte |  3.578 sec |  9.165 sec
libbsc:  mozilla |  51220480 byte |  15397450(30.1%) byte |  2.625 sec |  5.274 sec
libbsc:  webster |  41458703 byte |   7619075(18.4%) byte |  1.211 sec |  3.040 sec
libbsc:      nci |  33553445 byte |   2045306(06.1%) byte |  0.662 sec |  1.472 sec
libbsc:    samba |  21606400 byte |   4284021(19.8%) byte |  0.755 sec |  1.485 sec
libbsc:  dickens |  10192446 byte |   2515218(24.7%) byte |  0.362 sec |  0.740 sec
libbsc:     osdb |  10085684 byte |   2285177(22.7%) byte |  0.455 sec |  0.915 sec
libbsc:       mr |   9970564 byte |   2257111(22.6%) byte |  0.394 sec |  0.700 sec
libbsc:    x-ray |   8474240 byte |   3795571(44.8%) byte |  0.555 sec |  1.399 sec
libbsc:      sao |   7251944 byte |   4639333(64.0%) byte |  0.709 sec |  1.080 sec
libbsc:  reymont |   6627202 byte |   1284154(19.4%) byte |  0.204 sec |  0.379 sec
libbsc:  ooffice |   6152192 byte |   2548158(41.4%) byte |  0.363 sec |  0.640 sec
libbsc:      xml |   5345280 byte |    528757(09.9%) byte |  0.113 sec |  0.234 sec
libbsc: interrup |   5134954 byte |    842613(16.4%) byte |  0.141 sec |  0.291 sec
libbsc:   enwik5 |   5000000 byte |   1289183(25.8%) byte |  0.187 sec |  0.356 sec
libbsc:    book1 |    768771 byte |    223980(29.1%) byte |  0.034 sec |  0.051 sec

* Tested on Core 2 Duo T9400 @ 2.5GHz with 4GB RAM running on Windows 7 x64.

[Black_Fox]

Tested x64 version a little. Used default settings, -b to match size of compressed file.

Q6600 -- comp -- decomp
enwik8 -- 25.356s -- 17.840s

enwik9 -b1000 uses 958MB of RAM and all four cores for some seconds, then bails out with "not enough memory!", even though at that moment there still is 1,6 GB of free RAM.

C:\Users\Black_Fox\Desktop\bsc>pextimer bsc.exe e enwik8 enwik8-b100 -b100
PexTimer v2.0
Copyright (c) 2007 by LovePimple

This is bsc, Block Sorting Compressor. Version 1.0.0, 05-Apr-2010.
Copyright (c) 2002-2010 Ilya Grebnov <Ilya.Grebnov@gmail.com>.

OMP: Warning #2: Cannot open message catalog "1029\libiomp5ui.dll":
OMP: System error #126: Uvedenř modul nebyl nalezen.
OMP: Info #3: Default messages will be used.
enwik8 compressed 100000000 into 20769950 in 25.356 seconds.

Elapsed Time:  00  00:00:25.491  (25.491 Seconds)

EDIT: Regarding the "not enough memory", x86 version fails immediatelly. OS: Win7 x64 Professional, 4 GB RAM.

[joerg]

i am using windows vista 32 bit with core 2 duo and 4 gbyte ram

first test:

bsc e db.dmp dbbsc

This is bsc, Block Sorting Compressor. Version 1.0.0, 05-Apr-2010.
Copyright (c) 2002-2010 Ilya Grebnov <Ilya.Grebnov@gmail.com>.

OMP: Warning #2: Cannot open message catalog "1031\libiomp5ui.dll":
OMP: System error #126: Das angegebene Modul wurde nicht gefunden.
OMP: Info #3: Default messages will be used.
db.dmp compressed 648331264 into 31481468 in 90.081 seconds.

---
in my test it compresses better then pbzip2 and a little bit faster

some error messages ... ???

fazit:

very good result for first release!

[Gribok]

enwik9 -b1000 uses 958MB of RAM and all four cores for some seconds, then bails out with "not enough memory!", even though at that moment there still is 1,6 GB of free RAM.

You need 6Gb of RAM to compress/decompress enwik9 in a single block. Actually I have machine with 8Gb of RAM, so for this case you will get something like "enwik9 compressed 1000000000 into 163882152 in 271.193 seconds."

[joerg]

@gribok
---
OMP: Warning #2: Cannot open message catalog "1031\libiomp5ui.dll":
OMP: System error #126: Das angegebene Modul wurde nicht gefunden.
OMP: Info #3: Default messages will be used.
---
have you any hints,
why this error messages and how to prevent this error messages ?

best regards

[Gribok]

@gribok
---
OMP: Warning #2: Cannot open message catalog "1031\libiomp5ui.dll":
OMP: System error #126: Das angegebene Modul wurde nicht gefunden.
OMP: Info #3: Default messages will be used.
---
have you any hints,
why this error messages and how to prevent this error messages ?

best regards

This is a warning from OpenMP run-time. I am using Intel C++ compiler with OpenMP statically linked to executable. You have this warning message because you have non English locale. So, I could build bsc using Visual Studio 2008. But Visual Studio doesn't have an option to embed OpenMP run-time to executable. So you will have to install VS redistribute package for this case.

[joerg]

would it be possible to statically link this
"libiomp5ui.dll" to the executable?

best regards

[Gribok]

would it be possible to statically link this
"libiomp5ui.dll" to the executable?

best regards

EN-US version of this file is already linked in. But I have mentioned yearly I have another option. I could build executable by VS 2008. But for this case you need to install VS redistribute package. Which I believe available for all locales.

[Matt Mahoney]

> "enwik9 compressed 1000000000 into 163882152 in 271.193 seconds."

What kind of machine? Decompression time?

[Gribok]

> "enwik9 compressed 1000000000 into 163882152 in 271.193 seconds."

What kind of machine? Decompression time?

So, I have 2 tests which I think you may be interested:

1. enwik9 is compressed to 163882152 bytes in 271.193 seconds and decompressed in 209 seconds on Intel Core 2 Duo E8500, 8GB RAM, Win7 x64 using "-p -b1000" command line options.
2. enwik9 is compressed to 200607811 bytes in 36.504 seconds and decompressed in 71.713 seconds on Intel Core 2 Quad Q9400, 8GB RAM, Win7 x64 using "-p -b79 -m2" command line options.

[Sportman]

>What kind of machine? Decompression time?

At system 34:

163,820,253 bytes bsc e enwik9 enwik.out -b1024 00:05:11.533 (311.533 Seconds)
bsc d enwik.out enwik9 00:03:32.148 (212.148 Seconds)
compare Ok

163,882,152 bytes bsc e enwik9 enwik.out -b1024p 00:04:41.135 (281.135 Seconds)
bsc d enwik.out enwik9 00:03:34.709 (214.709 Seconds)
compare Ok

[Matt Mahoney]

Thanks for test results. http://mattmahoney.net/dc/text.html#1640

[Gribok]

New 1.0.1 version is available for download:
1. Memory usage decreased to 5 times per block size per number of threads.
2. Binaries now compiled by Visual Studio 2008. OpenMP.dll file included in package. If Microsoft Visual C++ 2008 Redistributable Package is installed on your machine you do not need this file.

[Gribok]

New 1.0.2 version is available for testing.
1. Binaries compiled by Intel C++ Compiler.
2. Function kmp_set_warnings_off() added to suppress messages like "OMP: Warning #2: Cannot open message catalog "1031\libiomp5ui.dll""

To Black_Fox and joerg: could you please try this version and verify that issue with warning message is resolved now.

[joerg]

@gribok (Грибок ?)

thank you very much for the new release!

first: the resulting files for the 3 releases are identically - very good!

second: comparing the compression time

bsc 1.0.1 versus bsc 1.0.0 is 3 % slower

bsc 1.0.2 versus bsc 1.0.0 is 1 % faster

third: the error messages are gone - wonderful!

best regards

[encode]

@gribok (Грибок ?)

Грибок на ногах...

Hi Gribok!

First of all, good job! Results are good, except book1. Can you describe your QLFC? Anyway, you forcing me to improve BCM further, and BCM 0.11 will be KICK ASS!


P.S.
BWT, we have BSSC - the BWT compressor as well. The author of BSSC had a malfunctioning keyboard with the sticky 'S' key.

[joerg]

@Gribok

my big testfile has 2.917.707.776 bytes

Is here a 2GByte-filesize-limit for the input-file or another limit ?

best regards

---
bsc100 e dbbig.dmp dbbigbsc100
This is bsc, Block Sorting Compressor. Version 1.0.0, 05-Apr-2010.
Copyright (c) 2002-2010 Ilya Grebnov <Ilya.Grebnov@gmail.com>.

IO error on file: dbbig.dmp!

bsc101 e dbbig.dmp dbbigbsc101
This is bsc, Block Sorting Compressor. Version 1.0.1, 08-Apr-2010.
Copyright (c) 2002-2010 Ilya Grebnov <Ilya.Grebnov@gmail.com>.

IO error on file: dbbig.dmp!

bsc102 e dbbig.dmp dbbigbsc102
This is bsc, Block Sorting Compressor. Version 1.0.2, 08-Apr-2010.
Copyright (c) 2002-2010 Ilya Grebnov <Ilya.Grebnov@gmail.com>.

IO error on file: dbbig.dmp!

[Shelwien]

http://nishi.dreamhosters.com/u/et_b4.htm

[Gribok]

@Gribok

my big testfile has 2.917.707.776 bytes

Is here a 2GByte-filesize-limit for the input-file or another limit ?

Yes, there is a input-size limit for 2GB.

[Gribok]

Грибок на ногах...

Шутку юмора не понял

[Gribok]

First of all, good job! Results are good, except book1. Can you describe your QLFC? Anyway, you forcing me to improve BCM further, and BCM 0.11 will be KICK ASS!

I will release source code later. But in general it is the same RLE-EXP + rank coder like in GRZipII.

[encode]

Шутку юмора не понял

Sorry, it's the first thing that comes to mind (As example: http://www.gribok.ru)

[joerg]

@gribok "Yes, there is a input-size limit for 2GB." ...

is this a limit only for the win32-version
or is this valid for the win64-version too ?

would it be possible to solve this limit ?

bzip2 (7z) does not have such a limit ...

winrar 3.93 can handle the file too without problems ...

best regards

[Bulat Ziganshin]

Ilya, i can help with 64-bit filesizes if you need. you know my icq

[mindi]

Excellent compression / time ratio...!

[Gribok]

Block Sorting Compressor version 1.0.3 is available for testing:
[+]: Added support of large files(>2Gb long).
[+]: Fixed bug in ST reconstruction(some edge cases).

[Shelwien]

http://nishi.dreamhosters.com/u/et_rc1.htm

I tried merging the source and compiling as single program,
but unfortunately didn't succeed :)

[encode]

The source?

[joerg]

@gribok


1. thank you very much
for the new version without 2GByte-limit

wonderful!

i have done several tests ...

2.
---
-m<algo> Block sorting algorithm, default: -m3
-m1 Sort Transform of order 4
-m2 Sort Transform of order 5
-m3 Burrows Wheeler Transform
---
some times the method -m2 has better results then -m3

that means
- compression time is smaller
and the resulting filesize is smaller too

"Sort Transform of order 5" works great!

may be it does sense to
make the -m2 switch the default?

3.
---
-T|t Enable|Disable Multi-Threading, default: Enable
---
your compressor has the possibility
to use more then one thread

it seems that method -m3 = Burrows Wheeler Transform

runs at nearly double speed with Multi-Threading,
but does not profit if there are more then 2 cores
(my test computer has two xeons, which is shown
in the windows-taskmanger as 4 cpu)

is this true ?


thanks again for your great program

best regards

[Gribok]

@gribok


1. thank you very much
for the new version without 2GByte-limit

wonderful!

i have done several tests ...

2.
---
-m<algo> Block sorting algorithm, default: -m3
-m1 Sort Transform of order 4
-m2 Sort Transform of order 5
-m3 Burrows Wheeler Transform
---
some times the method -m2 has better results then -m3

Yes, sometimes for binary or heterogeneous data -m2 gives better results. But in average -m3 is still better and much better in text data like xml, html, etc..

that means
- compression time is smaller
and the resulting filesize is smaller too

"Sort Transform of order 5" works great!

may be it does sense to
make the -m2 switch the default?

3.
---
-T|t Enable|Disable Multi-Threading, default: Enable
---
your compressor has the possibility
to use more then one thread

it seems that method -m3 = Burrows Wheeler Transform

runs at nearly double speed with Multi-Threading,
but does not profit if there are more then 2 cores
(my test computer has two xeons, which is shown
in the windows-taskmanger as 4 cpu)

is this true ?

I doesn't have a multi CPU configuration. I have only multi core configuration. But in general bsc process data in parallel by blocks. So you should get a boost by number of cores/cpu you have. But please note that you have to select a blocks size in a such way so input file will be divided in multiple blocks. Additional to processing blocks in parallel bsc also have some optimizations for BWT transform. So even if you processing your file in single block by -m3 you should get a boost for 10%-15% on multi core CPU.

thanks again for your great program

best regards