my first simple PPM compressor

[RichSelian]

recently I read a series of PPM articles by yeye55 (written in Chinese, detailed and easy to understand: http://yeye55blog.blog.163.com/blog/...01110715759577) and started to implement my own PPM compressor..
this is the very beginning version. highest order is o4, with an simple LZP preprocessor, no more tricks.

https://github.com/richox/zmolly

compile with:
g++ -std=c++11 -Wall -O3 -pthread zmolly.cpp -o zmolly

[Jarek]

I see you use range coding - if you want a few times speedup (e.g. one multiplication/symbol instead of two): https://github.com/rygorous/ryg_rans

[xezz]

Please attach executable or single thread version.
Because I can't compile the source.
Compiler reports error: 'thread' is not a member of 'std'.

[Kennon Conrad]

Please attach executable or single thread version.
Because I can't compile the source.
Compiler reports error: 'thread' is not a member of 'std'.

I compiled with gcc -O2 -o zmolly zmolly.cpp -static -lpthread -std=c++11 and it worked.

[xezz]

Thanks, but not works. Is it for win64?

[RichSelian]

Please attach executable or single thread version.
Because I can't compile the source.
Compiler reports error: 'thread' is not a member of 'std'.

I don't have a windows development environment. but I believe the newest mingw-gcc can compile it.

[a902cd23]

Compiled with http://tdm-gcc.tdragon.net/ v5.1.0 - both win32/64

[a902cd23]

Did a quick test of a DVD-movie. zMolly worked for almost 1 hour and got almost smallest, with -b99.

4.692.514.816 2014.DVDR.iso
4.437.031.413 2014.DVDR.rar (1GB)
4.436.714.366 2014.DVDR.7z (1GB)
4.283.536.592 2014.DVDR.iso.zmolly
4.238.629.548 2014.DVDR.iso.b512.m6.bsc

Of course decompression was okey with CRC32 matched.

[RichSelian]

binary release is here:
https://github.com/richox/zmolly/raw...molly-i686.exe
https://github.com/richox/zmolly/raw...lly-x86_64.exe

built using mingw32-w64-gcc under archlinux

[xezz]

implemented lazy matching.

enwik7:
original 2451810
lazy     2450699

-b34 enwik8:
original 23537042
lazy     23523497

calgary.tar:
original 822839
lazy     822245

[Gonzalo]

Hello Rich. I was hoping you can help me out with the last version of zmolly on Github. I cannot compile it due to numerous errors. Is it working? Maybe you can pass us the compile options you are using. I changed the standard to c++14 just in case but the errors still appeared.

Thank you in advance!

[przemoc]

First I can confirm that zmolly source code does assume C++14 support.

GCC supports C++14 since version 5. GNU's dialect of it is the default one since version 6.1 (so called gnu++14), so you need to build with --std=c++14 if your GCC is older (or --std=c++1y if it's very old, < 4.9).
Clang suppots C++14 since version 3.4 sans few very minor library things that got in 3.5. You need to build with --std=c++14 (or --std=c++1y if it's very old, < 3.5).

It builds fine on:
- g++ 6.3.0, clang++ 4.0.0 @ Linux (Alpine Linux 3.6.2),
- g++ 7.3.0, clang++ 5.0.1 @ Windows (MSYS2 MinGW-w64).

Gonzalo, maybe you use very old compiler?

[Gonzalo]

Yes, I use an old compiler, but also a new one.
GCC 4.9 (because of my distro's versioning hell) and the very latest clang downloaded from their web.

$ g++ -std=c++14 -Wall -O3 -pthread zmolly.cpp -o zmolly

zmolly.cpp: In member function ‘void sparse_model_t::update(dense_model_t*, int)’:
zmolly.cpp:418:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (auto i = 0; i + n < m_symbols.size(); i++) {
                                    ^
zmolly.cpp: In member function ‘uint32_t matcher_t::lookup(unsigned char*, uint32_t, uint32_t, int, int)’:
zmolly.cpp:674:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (match_len + 1 < next_match_len) {
                               ^
zmolly.cpp: In function ‘void zmolly_encode(std::istream&, std::ostream&)’:
zmolly.cpp:746:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (orig_pos < orig_size) {
                         ^
zmolly.cpp: In function ‘int main(int, char**)’:
zmolly.cpp:859:86: error: use of deleted function ‘std::basic_ifstream<char>::basic_ifstream(const std::basic_ifstream<char>&)’
     auto fin = std::ifstream(std::string() + argv[2], std::ios::in | std::ios::binary);
                                                                                      ^
In file included from zmolly.cpp:33:0:
/usr/include/c++/4.9/fstream:430:11: note: ‘std::basic_ifstream<char>::basic_ifstream(const std::basic_ifstream<char>&)’ is implicitly deleted because the default definition would be ill-formed:
     class basic_ifstream : public basic_istream<_CharT, _Traits>
           ^
/usr/include/c++/4.9/fstream:430:11: error: use of deleted function ‘std::basic_istream<char>::basic_istream(const std::basic_istream<char>&)’
In file included from /usr/include/c++/4.9/fstream:38:0,
                 from zmolly.cpp:33:
/usr/include/c++/4.9/istream:58:11: note: ‘std::basic_istream<char>::basic_istream(const std::basic_istream<char>&)’ is implicitly deleted because the default definition would be ill-formed:
     class basic_istream : virtual public basic_ios<_CharT, _Traits>
           ^
/usr/include/c++/4.9/istream:58:11: error: use of deleted function ‘std::basic_ios<char>::basic_ios(const std::basic_ios<char>&)’
In file included from /usr/include/c++/4.9/ios:44:0,
                 from /usr/include/c++/4.9/istream:38,
                 from /usr/include/c++/4.9/fstream:38,
                 from zmolly.cpp:33:
/usr/include/c++/4.9/bits/basic_ios.h:66:11: note: ‘std::basic_ios<char>::basic_ios(const std::basic_ios<char>&)’ is implicitly deleted because the default definition would be ill-formed:
     class basic_ios : public ios_base
           ^
In file included from /usr/include/c++/4.9/ios:42:0,
                 from /usr/include/c++/4.9/istream:38,
                 from /usr/include/c++/4.9/fstream:38,
                 from zmolly.cpp:33:
/usr/include/c++/4.9/bits/ios_base.h:786:5: error: ‘std::ios_base::ios_base(const std::ios_base&)’ is private
     ios_base(const ios_base&);
     ^
In file included from /usr/include/c++/4.9/ios:44:0,
                 from /usr/include/c++/4.9/istream:38,
                 from /usr/include/c++/4.9/fstream:38,
                 from zmolly.cpp:33:
/usr/include/c++/4.9/bits/basic_ios.h:66:11: error: within this context
     class basic_ios : public ios_base
           ^
In file included from zmolly.cpp:33:0:
/usr/include/c++/4.9/fstream:430:11: error: use of deleted function ‘std::basic_ios<char>::basic_ios(const std::basic_ios<char>&)’
     class basic_ifstream : public basic_istream<_CharT, _Traits>
           ^
/usr/include/c++/4.9/fstream:430:11: error: use of deleted function ‘std::basic_filebuf<char>::basic_filebuf(const std::basic_filebuf<char>&)’
/usr/include/c++/4.9/fstream:72:11: note: ‘std::basic_filebuf<char>::basic_filebuf(const std::basic_filebuf<char>&)’ is implicitly deleted because the default definition would be ill-formed:
     class basic_filebuf : public basic_streambuf<_CharT, _Traits>
           ^
In file included from /usr/include/c++/4.9/ios:43:0,
                 from /usr/include/c++/4.9/istream:38,
                 from /usr/include/c++/4.9/fstream:38,
                 from zmolly.cpp:33:
/usr/include/c++/4.9/streambuf:802:7: error: ‘std::basic_streambuf<_CharT, _Traits>::basic_streambuf(const std::basic_streambuf<_CharT, _Traits>&) [with _CharT = char; _Traits = std::char_traits<char>]’ is private
       basic_streambuf(const basic_streambuf& __sb)
       ^
In file included from zmolly.cpp:33:0:
/usr/include/c++/4.9/fstream:72:11: error: within this context
     class basic_filebuf : public basic_streambuf<_CharT, _Traits>
           ^
zmolly.cpp:866:72: error: use of deleted function ‘std::basic_ofstream<char>::basic_ofstream(const std::basic_ofstream<char>&)’
     auto fout = std::ofstream(argv[3], std::ios::out | std::ios::binary);
                                                                        ^
In file included from zmolly.cpp:33:0:
/usr/include/c++/4.9/fstream:602:11: note: ‘std::basic_ofstream<char>::basic_ofstream(const std::basic_ofstream<char>&)’ is implicitly deleted because the default definition would be ill-formed:
     class basic_ofstream : public basic_ostream<_CharT,_Traits>
           ^
/usr/include/c++/4.9/fstream:602:11: error: use of deleted function ‘std::basic_ostream<char>::basic_ostream(const std::basic_ostream<char>&)’
In file included from /usr/include/c++/4.9/istream:39:0,
                 from /usr/include/c++/4.9/fstream:38,
                 from zmolly.cpp:33:
/usr/include/c++/4.9/ostream:58:11: note: ‘std::basic_ostream<char>::basic_ostream(const std::basic_ostream<char>&)’ is implicitly deleted because the default definition would be ill-formed:
     class basic_ostream : virtual public basic_ios<_CharT, _Traits>
           ^
/usr/include/c++/4.9/ostream:58:11: error: use of deleted function ‘std::basic_ios<char>::basic_ios(const std::basic_ios<char>&)’
In file included from zmolly.cpp:33:0:
/usr/include/c++/4.9/fstream:602:11: error: use of deleted function ‘std::basic_ios<char>::basic_ios(const std::basic_ios<char>&)’
     class basic_ofstream : public basic_ostream<_CharT,_Traits>
           ^
/usr/include/c++/4.9/fstream:602:11: error: use of deleted function ‘std::basic_filebuf<char>::basic_filebuf(const std::basic_filebuf<char>&)’
zmolly.cpp: In instantiation of ‘zmolly_encode(std::istream&, std::ostream&)::<lambda(auto:1)> [with auto:1 = int*]’:
/usr/include/c++/4.9/type_traits:2195:25:   required by substitution of ‘template<class _Fn, class ... _Args> static std::__success_type<decltype (declval<_Fn>()((declval<_Args>)()...))> std::__result_of_other_impl::_S_test(int) [with _Fn = zmolly_encode(std::istream&, std::ostream&)::<lambda(auto:1)>; _Args = {int*}]’
/usr/include/c++/4.9/type_traits:2206:57:   required from ‘struct std::__result_of_impl<false, false, zmolly_encode(std::istream&, std::ostream&)::<lambda(auto:1)>, int*>’
/usr/include/c++/4.9/type_traits:2210:12:   required from ‘class std::result_of<zmolly_encode(std::istream&, std::ostream&)::<lambda(auto:1)>(int*)>’
/usr/include/c++/4.9/functional:1665:61:   required from ‘struct std::_Bind_simple<zmolly_encode(std::istream&, std::ostream&)::<lambda(auto:1)>(int*)>’
/usr/include/c++/4.9/thread:140:47:   required from ‘std::thread::thread(_Callable&&, _Args&& ...) [with _Callable = zmolly_encode(std::istream&, std::ostream&)::<lambda(auto:1)>&; _Args = {int*}]’
zmolly.cpp:743:67:   required from here
zmolly.cpp:734:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (auto i = 0; i < match_len; i++) {
                                    ^

$ clang++ -std=c++14 -Wall -O3 -pthread zmolly.cpp -o zmolly

zmolly.cpp:859:10: error: call to implicitly-deleted copy constructor of 'std::basic_ifstream<char>'
    auto fin = std::ifstream(std::string() + argv[2], std::ios::in | std::ios::binary);
         ^     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/../lib/gcc/x86_64-linux-gnu/4.9/../../../../include/c++/4.9/fstream:430:28: note: copy constructor of 'basic_ifstream<char, std::char_traits<char> >' is implicitly deleted
      because base class 'basic_istream<char, std::char_traits<char> >' has a deleted copy constructor
    class basic_ifstream : public basic_istream<_CharT, _Traits>
                           ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/4.9/../../../../include/c++/4.9/istream:58:27: note: copy constructor of 'basic_istream<char, std::char_traits<char> >' is implicitly deleted
      because base class 'basic_ios<char, std::char_traits<char> >' has a deleted copy constructor
    class basic_istream : virtual public basic_ios<_CharT, _Traits>
                          ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/4.9/../../../../include/c++/4.9/bits/basic_ios.h:66:23: note: copy constructor of 'basic_ios<char, std::char_traits<char> >' is implicitly
      deleted because base class 'std::ios_base' has an inaccessible copy constructor
    class basic_ios : public ios_base
                      ^
zmolly.cpp:866:10: error: call to implicitly-deleted copy constructor of 'std::basic_ofstream<char>'
    auto fout = std::ofstream(argv[3], std::ios::out | std::ios::binary);
         ^      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/../lib/gcc/x86_64-linux-gnu/4.9/../../../../include/c++/4.9/fstream:602:28: note: copy constructor of 'basic_ofstream<char, std::char_traits<char> >' is implicitly deleted
      because base class 'basic_ostream<char, std::char_traits<char> >' has a deleted copy constructor
    class basic_ofstream : public basic_ostream<_CharT,_Traits>
                           ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/4.9/../../../../include/c++/4.9/ostream:58:27: note: copy constructor of 'basic_ostream<char, std::char_traits<char> >' is implicitly deleted
      because base class 'basic_ios<char, std::char_traits<char> >' has a deleted copy constructor
    class basic_ostream : virtual public basic_ios<_CharT, _Traits>
                          ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/4.9/../../../../include/c++/4.9/bits/basic_ios.h:66:23: note: copy constructor of 'basic_ios<char, std::char_traits<char> >' is implicitly
      deleted because base class 'std::ios_base' has an inaccessible copy constructor
    class basic_ios : public ios_base
                      ^
2 errors generated.

[przemoc]

Gonzalo, I think you'll be able to build it with my patch:
https://github.com/richox/zmolly/pull/3

EDIT:
Using recent clang didn't help in your case, because you were still using system default GCC's libstdc++. If you want to use clang without patching the source, you'll need to have libc++ too and build the source with it (-stdlib=libc++). You can read more details here:
https://libcxx.llvm.org/docs/UsingLibcxx.html

[Gonzalo]

Gonzalo, I think you'll be able to build it with my patch:
https://github.com/richox/zmolly/pull/3

EDIT:
Using recent clang didn't help in your case, because you were still using system default GCC's libstdc++. If you want to use clang without patching the source, you'll need to have libc++ too and build the source with it (-stdlib=libc++). You can read more details here:
https://libcxx.llvm.org/docs/UsingLibcxx.html

I just wanted to let you know that your patch went through. It compiled, now all is left is start testing it. Thank you!