Broo is a lossless compression algorithm. Enhancements

    A little more than six months have passed since the previous publication. Not all this time was spent on improving the algorithm, but there are results. So.


    Why is the name "Broo"?


    image



    There is a genus of small lizards called Brookesia . As you know, all lizards have a high speed of movement, and these are also small in size and, in addition, from the chameleon family.


    We made some analogies:


    • Chameleon family - not tied to file type.
    • Small size - the result of file compression is also not bad.
    • Fast moving speed - here, of course, with a small caveat, that only for the speed of unpacking.

    Yes and abbreviated coolelegant word broo .


    Brookesia ( lat. Brookesia ) is a genus of lizards from the chameleon family .

    Small chameleons. One of the smallest species of the genus, small brukesia ( Brookesia minima ), is also considered one of the smallest lizards. [1]

    They are characterized by a short, slightly twisting tail, as well as a double row of tubercles or spines along the ridge and jagged outgrowths over the eyes. The color is usually brown or brownish, masking under fallen leaves.

    Endemic to Madagascar and the surrounding small islands. They lead a secretive, mainly terrestrial way of life in the forest litter .

    Description of changes


    They were primarily oriented, and this continues to be the main goal, on the compression coefficient without loss in speed. The coefficient was improved, the speeds were kept, and they were brought to stable operation. And of course, they checked a bunch of different theories. In theory, the algorithm still provides enough room for improvements.


    PC specifications


    Processor DualCore Intel Core i3 550, 3200 MHz
    Memory GoodRam 8119 Mb DDR3-1333 DDR3 SDRAM
    OS Ubuntu 16.10 x64


    Tables with measurements


    For measurements, as before, we use lzbench .


    Silesia test files .


    A brief description of the test files and some of the algorithms that are given in the tables can be found in a previous publication .


    Recall only two:


    Zstandard (Zstd) is a lossless data compression algorithm developed since 2015 by Yann Collet with the support of Facebook. It combines a vocabulary data compression algorithm of the LZ77 type and efficient entropy coding of the tANS type (FSE - Finite State Entropy), a modification of the Huffman code that implements a non-integer number of bits for storing characters.

    Brotli - based on the modern version of the LZ77 algorithm , Huffman entropy coding and modeling of the 2nd order context.
    Designed to speed up the loading of web pages, it is supported in Chrome browsers based on Chromium and in Firefox.

    Further, 12 tables with measurements of each file from the silesia package . The current version of the Broo 1.1 algorithm .


    Test 1. Collection of works by Charles Dickens, dickens (txt).
    Algorithm Name
    Packing speed

    Decompression speed
    Compressed
    File Size , Bytes
    % of the
    original
    memcpy4029 MB / s4034 MB / s10192446100.00
    broo 1.15.30 MB / s298 MB / s3,779,71608/37
    lzlib 1.7 -07.76 MB / s34 MB / s381533537.43
    csc 2016-10-13 -118 MB / s31 MB / s402091639.45
    lzma 9.38 -013 MB / s38 MB / s404485039.68
    libdeflate 0.6 -185 MB / s435 MB / s423154341.52
    zstd 1.1.3 -1143 MB / s486 MB / s427927341.98
    xpack 2016-06-02 -183 MB / s359 MB / s428224542.01
    brotli 0.5.2 -0168 MB / s178 MB / s4,401,26943.18
    zlib 1.2.8 -150 MB / s195 MB / s458561844.99
    broo 1.06.03 MB / s265 MB / s475093646.61
    gipfeli 2016-07-13178 MB / s254 MB / s495563248.62
    yalz77 2015-09-19 -162 MB / s304 MB / s563410955.28
    quicklz 1.5.0 -1250 MB / s326 MB / s583135357.21
    lzsse2 2016-05-14 -018 MB / s1481 MB / s586570557.55
    yappy 2014-03-22 -091 MB / s1122 MB / s614185360.26
    snappy 1.1.3179 MB / s648 MB / s633783462.18
    lz4 1.7.5264 MB / s1652 MB / s642874263.07
    lz5 2.0 -10216 MB / s1855 MB / s643186963.10

    Test 2. Tar archive with executable files Mozilla 1.0, mozilla (exe).
    Algorithm Name
    Packing speed

    Decompression speed
    Compressed
    File Size , Bytes
    % of the
    original
    memcpy3986 MB / s4042 MB / s51220480100.00
    csc 2016-10-13 -111 MB / s41 MB / s1533119129.93
    lzma 9.38 -017 MB / s43 MB / s1642527207/32
    lzlib 1.7 -018 MB / s33 MB / s1647048432.16
    xpack 2016-06-02 -176 MB / s368 MB / s1839187435.91
    libdeflate 0.6 -192 MB / s396 MB / s1978012438.62
    zstd 1.1.3 -1209 MB / s542 MB / s2012045939.28
    zlib 1.2.8 -153 MB / s209 MB / s2057722640.17
    broo 1.12.66 MB / s325 MB / s2060428340.23
    brotli 0.5.2 -0217 MB / s186 MB / s2174012842.44
    broo 1.05.11 MB / s350 MB / s2317722045.25
    gipfeli 2016-07-13236 MB / s436 MB / s2438055847.60
    quicklz 1.5.0 -1315 MB / s368 MB / s2475681948.33
    yalz77 2015-09-19 -149 MB / s436 MB / s2545453249.70
    lzsse2 2016-05-14 -013 MB / s1493 MB / s2582664850.42
    lz4 1.7.5437 MB / s1876 ​​MB / s2643566751.61
    snappy 1.1.3303 MB / s1013 MB / s2646192451.66
    lz5 2.0 -10334 MB / s2097 MB / s2701624252.74
    yappy 2014-03-22 -0107 MB / s1749 MB / s2772821854.14

    Test 3. Image MRI, mr (image).
    Algorithm Name
    Packing speed

    Decompression speed
    Compressed
    File Size , Bytes
    % of the
    original
    memcpy4010 MB / s4042 MB / s9970564100.00
    lzlib 1.7 -020 MB / s34 MB / s313089731.40
    lzma 9.38 -016 MB / s44 MB / s315762631.67
    csc 2016-10-13 -112 MB / s40 MB / s328580532.96
    xpack 2016-06-02 -182 MB / s323 MB / s352682835.37
    libdeflate 0.6 -198 MB / s428 MB / s375098537.62
    zlib 1.2.8 -160 MB / s227 MB / s382836638.40
    zstd 1.1.3 -1191 MB / s637 MB / s382923138.41
    brotli 0.5.2 -0198 MB / s185 MB / s397564339.87
    broo 1.14.90 MB / s329 MB / s404290940.55
    gipfeli 2016-07-13220 MB / s395 MB / s470256147.16
    broo 1.05.94 MB / s305 MB / s474121947.55
    quicklz 1.5.0 -1410 MB / s363 MB / s477819447.92
    lzsse2 2016-05-14 -024 MB / s1523 MB / s512028951.35
    yalz77 2015-09-19 -158 MB / s396 MB / s526936852.85
    snappy 1.1.3302 MB / s912 MB / s541983154.36
    lz4 1.7.5422 MB / s2024 MB / s544093754.57
    yappy 2014-03-22 -0108 MB / s1609 MB / s645412064.73
    lz5 2.0 -10294 MB / s2248 MB / s697848669.99

    Test 4. Base chemical structures, nci (database).
    Algorithm Name
    Packing speed

    Decompression speed
    Compressed
    File Size , Bytes
    % of the
    original
    memcpy4042 MB / s4047 MB ​​/ s33553445100.00
    broo 1.18.57 MB / s982 MB / s23826237.10
    csc 2016-10-13 -139 MB / s156 MB / s24637737.34
    lzma 9.38 -043 MB / s153 MB / s27779978.28
    lzlib 1.7 -049 MB / s103 MB / s28687618.55
    zstd 1.1.3 -1435 MB / s915 MB / s28845308.60
    broo 1.08.65 MB / s1000 MB / s29819708.89
    xpack 2016-06-02 -1180 MB / s807 MB / s383884711.44
    brotli 0.5.2 -0539 MB / s575 MB / s398419911.87
    libdeflate 0.6 -1180 MB / s1165 MB / s406691312.12
    zlib 1.2.8 -1122 MB / s404 MB / s462459713.78
    yalz77 2015-09-19 -1197 MB / s695 MB / s505059615.05
    gipfeli 2016-07-13529 MB / s681 MB / s506382909/15
    lz4 1.7.5765 MB / s2496 MB / s553304016.49
    lz5 2.0 -10657 MB / s2644 MB / s554581016.53
    snappy 1.1.3560 MB / s1452 MB / s614684418.32
    quicklz 1.5.0 -1512 MB / s799 MB / s616063618.36
    lzsse2 2016-05-14 -015 MB / s2984 MB / s633980718.89
    yappy 2014-03-22 -0179 MB / s1941 MB / s896756226.73

    Test 5. Dll files from Open Office.org 1.01, ooffice (exe).
    Algorithm Name
    Packing speed

    Decompression speed
    Compressed
    File Size , Bytes
    % of the
    original
    memcpy4054 MB / s4102 MB / s6152192100.00
    csc 2016-10-13 -19.91 MB / s29 MB / s230152337.41
    lzma 9.38 -013 MB / s31 MB / s284157846.19
    lzlib 1.7 -014 MB / s24 MB / s287948946.80
    xpack 2016-06-02 -160 MB / s342 MB / s313796051.01
    libdeflate 0.6 -169 MB / s286 MB / s318743451.81
    zlib 1.2.8 -140 MB / s151 MB / s329053253.49
    broo 1.13.89 MB / s284 MB / s343624655.08
    brotli 0.5.2 -0154 MB / s143 MB / s353961557.53
    zstd 1.1.3 -1166 MB / s487 MB / s357989958.19
    broo 1.04.93 MB / s412 MB / s375720661.07
    gipfeli 2016-07-13163 MB / s354 MB / s392227663.75
    lzsse2 2016-05-14 -015 MB / s1205 MB / s399509164.94
    quicklz 1.5.0 -1234 MB / s264 MB / s401385965.24
    yalz77 2015-09-19 -135 MB / s398 MB / s412557067.06
    yappy 2014-03-22 -082 MB / s1718 MB / s423568768.85
    snappy 1.1.3222 MB / s889 MB / s427115069.42
    lz4 1.7.5337 MB / s1671 MB / s433891870.53
    lz5 2.0 -10251 MB / s1997 MB/s437007071.03

    Тест 6. Пример базы данных MySQL формата из Open Source Database Benchmark, osdb.
    Имя алгоритмаСкорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy4095 MB/s4073 MB/s10085684100.00
    csc 2016-10-13 -110 MB/s38 MB/s331780032.90
    lzlib 1.7 -019 MB/s33 MB/s334596533.18
    xpack 2016-06-02 -168 MB/s475 MB/s375287137.21
    zstd 1.1.3 -1194 MB/s585 MB/s377056637.39
    broo 1.13.33 MB/s486 MB/s386207338.29
    libdeflate 0.6 -190 MB/s470 MB/s389680338.64
    brotli 0.5.2 -0214 MB/s224 MB/s391050238.77
    lzma 9.38 -015 MB/s38 MB/s398882339.55
    zlib 1.2.8 -156 MB/s211 MB/s407639140.42
    broo 1.05.40 MB/s474 MB/s414746541.12
    lzsse2 2016-05-14 -012 MB/s1724 MB/s449255144.54
    gipfeli 2016-07-13232 MB/s530 MB/s451751744.79
    yalz77 2015-09-19 -151 MB/s596 MB/s457019345.31
    lz4 1.7.5359 MB/s1629 MB/s525666652.12
    lz5 2.0 -10278 MB/s1842 MB/s528673952.42
    snappy 1.1.3303 MB/s1110 MB/s532932152.84
    quicklz 1.5.0 -1277 MB/s330 MB/s549644354.50
    yappy 2014-03-22 -070 MB/s1794 MB/s751573574.52

    Тест 7. Текст книги Chłopi, польского писателя Радислава Реймонта, Polish, reymont (PDF).
    Имя алгоритмаСкорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy4123 MB/s4120 MB/s6627202100.00
    broo 1.16.90 MB/s470 MB/s184038727.77
    csc 2016-10-13 -115 MB/s47 MB/s187232428.25
    lzma 9.38 -015 MB/s49 MB/s192195429.00
    lzlib 1.7 -022 MB/s37 MB/s208229731.42
    zstd 1.1.3 -1157 MB/s486 MB/s216738532.70
    libdeflate 0.6 -1100 MB/s512 MB/s220693233.30
    xpack 2016-06-02 -197 MB/s389 MB/s227971634.40
    broo 1.05.10 MB/s423 MB/s228901934.54
    brotli 0.5.2 -0212 MB/s226 MB/s236073235.62
    zlib 1.2.8 -159 MB/s213 MB/s237643035.86
    gipfeli 2016-07-13222 MB/s318 MB/s264491639.91
    quicklz 1.5.0 -1284 MB/s399 MB/s300382545.33
    yalz77 2015-09-19 -176 MB/s347 MB/s301708345.53
    lzsse2 2016-05-14 -016 MB/s1735 MB/s303939245.86
    yappy 2014-03-22 -0119 MB/s1252 MB/s316134447.70
    lz4 1.7.5303 MB/s1611 MB/s318138748.00
    lz5 2.0 -10265 MB/s1626 MB/s318490148.06
    snappy 1.1.3208 MB/s729 MB/s323378748.80

    Тест 8. Tar архив исходников Samba 2-2.3, samba (src).
    Имя алгоритмаСкорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy4048 MB/s4033 MB/s21606400100.00
    csc 2016-10-13 -117 MB/s60 MB/s440724120.40
    broo 1.15.80 MB/s652 MB/s513703523.78
    lzlib 1.7 -026 MB/s46 MB/s517881923.97
    lzma 9.38 -021 MB/s59 MB/s533893524.71
    zstd 1.1.3 -1257 MB/s715 MB/s555063725.69
    xpack 2016-06-02 -1107 MB/s568 MB/s566929526.24
    libdeflate 0.6 -1113 MB/s615 MB/s592297327.41
    brotli 0.5.2 -0304 MB/s285 MB/s608432728.16
    broo 1.06.90 MB/s650 MB/s618604228.63
    zlib 1.2.8 -173 MB/s276 MB/s632945529.29
    gipfeli 2016-07-13323 MB/s426 MB/s681062331.52
    yalz77 2015-09-19 -181 MB/s512 MB/s709889932.86
    quicklz 1.5.0 -1366 MB/s497 MB/s730945233.83
    lzsse2 2016-05-14 -014 MB/s2144 MB/s739573734.23
    lz4 1.7.5486 MB/s2035 MB/s771683935.72
    lz5 2.0 -10398 MB/s2246 MB/s792717836.69
    snappy 1.1.3353 MB/s1089 MB/s800877437.07
    yappy 2014-03-22 -0123 MB/s1769 MB/s918327342.50

    Тест 9. Звездный каталог Смитсоновской астрофизической обсерватории, sao (bin).
    Имя алгоритмаСкорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy4096 MB/s4114 MB/s7251944100.00
    lzma 9.38 -09.47 MB/s22 MB/s492352967.89
    lzlib 1.7 -010 MB/s16 MB/s500557369.02
    csc 2016-10-13 -15.69 MB/s17 MB/s508284670.09
    xpack 2016-06-02 -147 MB/s312 MB/s525960672.53
    libdeflate 0.6 -160 MB/s258 MB/s549426875.76
    zlib 1.2.8 -131 MB/s158 MB/s556777476.78
    broo 1.12.18 MB/s365 MB/s571578378.82
    brotli 0.5.2 -0130 MB/s120 MB/s601984183.01
    gipfeli 2016-07-13146 MB/s422 MB/s604336183.33
    broo 1.03.55 MB/s496 MB/s608611883.92
    yappy 2014-03-22 -068 MB/s1709 MB/s620175285.52
    zstd 1.1.3 -1145 MB/s483 MB/s625428286.24
    yalz77 2015-09-19 -126 MB/s576 MB/s629903086.86
    snappy 1.1.3212 MB/s969 MB/s643526688.74
    quicklz 1.5.0 -1229 MB/s222 MB/s649830189.61
    lzsse2 2016-05-14 -015 MB/s941 MB/s671054292.53
    lz4 1.7.5337 MB/s2161 MB/s679027393.63
    lz5 2.0 -10236 MB/s2501 MB/s679272093.67

    Тест 10. Американский словарь английского языка Уэбстера, webster (html).
    Имя алгоритмаСкорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy3970 MB/s4008 MB/s41458703100.00
    csc 2016-10-13 -113 MB/s44 MB/s1036015524.99
    broo 1.14.83 MB/s288 MB/s1107615826.72
    lzma 9.38 -017 MB/s47 MB/s1270487830.64
    lzlib 1.7 -022 MB/s38 MB/s1272759630.70
    zstd 1.1.3 -1169 MB/s531 MB/s1373828433.14
    libdeflate 0.6 -199 MB/s524 MB/s1383919233.38
    broo 1.05.42 MB/s266 MB/s1385419533.42
    xpack 2016-06-02 -194 MB/s441 MB/s1400690733.79
    brotli 0.5.2 -0187 MB/s207 MB/s1455900735.12
    zlib 1.2.8 -160 MB/s211 MB/s1499124236.16
    gipfeli 2016-07-13209 MB/s281 MB/s1615231238.96
    lzsse2 2016-05-14 -014 MB/s1897 MB/s1745951742.11
    quicklz 1.5.0 -1276 MB/s369 MB/s1831581644.18
    yalz77 2015-09-19 -162 MB/s315 MB/s1843524844.47
    yappy 2014-03-22 -0107 MB/s1378 MB/s1989961048.00
    lz4 1.7.5317 MB/s1593 MB/s2013998848.58
    lz5 2.0 -10260 MB/s1790 MB/s2015354748.61
    snappy 1.1.3214 MB/s765 MB/s2020646648.74

    Тест 11. Коллекция xml файлов, xml.
    Имя алгоритмаСкорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy4118 MB/s4113 MB/s5345280100.00
    csc 2016-10-13 -127 MB/s99 MB/s60676311.35
    broo 1.19.33 MB/s1260 MB/s64441612.06
    lzma 9.38 -034 MB/s108 MB/s69123612.93
    zstd 1.1.3 -1363 MB/s887 MB/s70315113.15
    lzlib 1.7 -039 MB/s73 MB/s74153713.87
    broo 1.07.91 MB/s1277 MB/s80052614.98
    brotli 0.5.2 -0409 MB/s451 MB/s90575716.94
    libdeflate 0.6 -1143 MB/s856 MB/s94040917.59
    zlib 1.2.8 -1104 MB/s344 MB/s96524818.06
    xpack 2016-06-02 -1137 MB/s634 MB/s100000818.71
    yalz77 2015-09-19 -1157 MB/s666 MB/s106737819.97
    gipfeli 2016-07-13406 MB/s527 MB/s110053620.59
    quicklz 1.5.0 -1452 MB/s712 MB/s112470821.04
    lzsse2 2016-05-14 -018 MB/s2870 MB/s120112522.47
    lz4 1.7.5617 MB/s1991 MB/s122749522.96
    lz5 2.0 -10524 MB/s2231 MB/s124009823.20
    snappy 1.1.3414 MB/s1196 MB/s130837424.48
    yappy 2014-03-22 -0155 MB/s1915 MB/s160545930.04

    Тест 12. Рентген изображение, x-ray (image).
    Имя алгоритмаСкорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy4023 MB/s4106 MB/s8474240100.00
    csc 2016-10-13 -116 MB/s21 MB/s404963047.79
    lzlib 1.7 -09.85 MB/s18 MB/s507927459.94
    lzma 9.38 -010 MB/s23 MB/s519889461.35
    xpack 2016-06-02 -148 MB/s243 MB/s586336769.19
    libdeflate 0.6 -163 MB/s267 MB/s599975070.80
    zlib 1.2.8 -135 MB/s145 MB/s603393271.20
    brotli 0.5.2 -0139 MB/s121 MB/s660052377.89
    zstd 1.1.3 -1419 MB/s569 MB/s677228679.92
    broo 1.13.01 MB/s215 MB/s698453982.42
    lzsse2 2016-05-14 -017 MB/s883 MB/s729287686.06
    quicklz 1.5.0 -1264 MB/s219 MB/s744063287.80
    gipfeli 2016-07-13165 MB/s486 MB/s764139190.17
    broo 1.03.47 MB/s487 MB/s770271590.90
    yalz77 2015-09-19 -123 MB/s491 MB/s793365393.62
    snappy 1.1.3446 MB/s1869 MB/s820918096.87
    yappy 2014-03-22 -059 MB/s3200 MB/s832858298.28
    lz4 1.7.5852 MB/s3457 MB/s839019599.01
    lz5 2.0 -10540 MB/s4126 MB/s845968599.83

    Полное сжатие Silesia.tar только с версией алгоритма Broo 1.1


    Имя алгоритмаСкорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy3743 MB/s3816 MB/s211948032100.00
    csc 2016-10-13 -112 MB/s45 MB/s5617178426.50
    lzlib 1.8 -021 MB/s37 MB/s6363633730.02
    lzma 16.04 -017 MB/s48 MB/s6401381730.20
    broo 1.12.10 MB/s365 MB/s6951980232.80
    xpack 2016-06-02 -188 MB / s434 MB / s7107362233.53
    libdeflate 0.7 -197 MB / s494 MB / s7331912434.59
    zstd 1.3.1 -1228 MB / s591 MB / s7364013834.74
    zlib 1.2.11 -161 MB / s228 MB / s7725109836.45
    brotli 2017-03-10 -0222 MB / s215 MB / s7839796336.99
    gipfeli 2016-07-13239 MB / s408 MB / s8793735641.49
    yalz77 2015-09-19 -162 MB / s304 MB / s9394922544.33
    quicklz 1.5.0 -1319 MB / s391 MB / s9473226044.70
    lzsse2 2016-05-14 -00.85 MB / s1700 MB / s9474004944.70
    lz4 1.7.5139 MB / s1885 MB / s10088140847.60
    snappy 1.1.4332 MB / s997 MB / s10229561048.26
    yappy 2014-03-22 -0108 MB / s1626 MB / s10942807451.63

    Also popular now: