dlib C++ Library - lz77_buffer.cpp

    // Copyright (C) 2004  Davis E. King (davisking@users.sourceforge.net)
    // License: Boost Software License   See LICENSE.txt for the full license.

    #include <sstream>
    #include <string>
    #include <ctime>
    #include <cstdlib>
    #include <dlib/sliding_buffer.h>

    #include <dlib/lz77_buffer.h>

    #include "tester.h"

    namespace
    {
        using namespace test;
        using namespace std;
        using namespace dlib;

        logger dlog("test.lz77_buffer");

        template <
            typename buf
            >
        void lz77_buffer_kernel_test (
        )
        /*!
            requires
                - buf is an implementation of lz77_buffer/lz77_buffer_kernel_abstract.h
            ensures
                - runs tests on buf for compliance with the specs
        !*/
        {
            typedef dlib::sliding_buffer<unsigned char>::kernel_1a sbuf;

            buf test(8,20);
            srand(static_cast<unsigned int>(time(0)));

            DLIB_CASSERT(test.get_lookahead_buffer_size() == 0,"");
            DLIB_CASSERT(test.get_history_buffer_size() == 0,"");
            DLIB_CASSERT(test.get_history_buffer_limit() == 256-20,test.get_history_buffer_limit());
            DLIB_CASSERT(test.get_lookahead_buffer_limit() == 20,"");

            for (int g = 0; g < 2; ++g)
            {
                test.clear();

                for (int i = 0; i < 1000; ++i)
                {
                    test.add('a');
                }
                DLIB_CASSERT(test.get_lookahead_buffer_size() == 20,"");

                test.shift_buffers(5);

                DLIB_CASSERT(test.get_lookahead_buffer_size() == 15,"");

                unsigned long index, length, temp;
                temp = test.get_lookahead_buffer_size();
                test.find_match(index,length,5);

                DLIB_CASSERT(length <= temp,
                             "length: " << length <<
                             "\ntemp: " << temp);
                DLIB_CASSERT(test.get_lookahead_buffer_size() <= 15,"");

            }

            for (int g = 0; g < 2; ++g)
            {

                test.clear();

                DLIB_CASSERT(test.get_lookahead_buffer_size() == 0,"");
                DLIB_CASSERT(test.get_history_buffer_size() == 0,"");
                DLIB_CASSERT(test.get_history_buffer_limit() == 256-20,"");
                DLIB_CASSERT(test.get_lookahead_buffer_limit() == 20,"");

                unsigned long a,b, temp = test.get_lookahead_buffer_size();
                test.find_match(a,b,0);
                DLIB_CASSERT(b <= temp,"");
                DLIB_CASSERT(b == 0,"");

                test.find_match(a,b,5);
                DLIB_CASSERT(b == 0,"");

                DLIB_CASSERT(test.get_lookahead_buffer_size() == 0,"");
                DLIB_CASSERT(test.get_history_buffer_size() == 0,"");
                DLIB_CASSERT(test.get_history_buffer_limit() == 256-20,"");
                DLIB_CASSERT(test.get_lookahead_buffer_limit() == 20,"");

                ostringstream sout;
                sout << "DLIB_CASSERT(test.get_lookahead_buffer_size() == 0,);\n";
                sout << "DLIB_CASSERT(test.get_history_buffer_size() == 0,);\n";
                sout << "DLIB_CASSERT(test.get_history_buffer_limit() == 256-20,);\n";
                sout << "DLIB_CASSERT(test.get_lookahead_buffer_limit() == 20,);\n";
                sout << "DLIB_CASSERT(test.get_lookahead_buffer_size() == 0,);\n";
                sout << "DLIB_CASSERT(test.get_history_buffer_size() == 0,);\n";
                sout << "DLIB_CASSERT(test.get_history_buffer_limit() == 256-20,);\n";
                sout << "DLIB_CASSERT(test.get_lookahead_buffer_limit() == 20,);\n";
                istringstream sin(sout.str());

                sout.str("");
                sout.clear();

                unsigned char ch;
                sbuf sbuffer;
                sbuffer.set_size(8);

                ch = sin.get();
                sbuffer[0] = ch; sbuffer.rotate_left(1);
                test.add(ch);
                DLIB_CASSERT(test.lookahead_buffer(test.get_lookahead_buffer_size()-1) == ch,"");
                DLIB_CASSERT(test.get_lookahead_buffer_size() == 1,"");
                DLIB_CASSERT(test.get_history_buffer_size() == 0,"");
                DLIB_CASSERT(test.get_lookahead_buffer_limit() == 20,"");

                ch = sin.get();
                sbuffer[0] = ch; sbuffer.rotate_left(1);
                test.add(ch);
                DLIB_CASSERT(test.lookahead_buffer(test.get_lookahead_buffer_size()-1) == ch,"");
                DLIB_CASSERT(test.get_lookahead_buffer_size() == 2,"");
                DLIB_CASSERT(test.get_history_buffer_size() == 0,"");
                DLIB_CASSERT(test.get_lookahead_buffer_limit() == 20,"");

                ch = sin.get();
                sbuffer[0] = ch; sbuffer.rotate_left(1);
                test.add(ch);
                DLIB_CASSERT(test.lookahead_buffer(test.get_lookahead_buffer_size()-1) == ch,"");
                DLIB_CASSERT(test.get_lookahead_buffer_size() == 3,"");
                DLIB_CASSERT(test.get_history_buffer_size() == 0,"");

                // add 17 chars to test so that the lookahead buffer will be full
                for (int i = 0; i < 17; ++i)
                {
                    ch = sin.get();
                    sbuffer[0] = ch; sbuffer.rotate_left(1);
                    test.add(ch);
                    DLIB_CASSERT(test.lookahead_buffer(test.get_lookahead_buffer_size()-1) == ch,"");
                }

                DLIB_CASSERT(test.get_lookahead_buffer_size() == 20,"");
                DLIB_CASSERT(test.get_history_buffer_size() == 0,"");
                DLIB_CASSERT(test.lookahead_buffer(0) == sbuffer[20],"");

                ch = sin.get();
                sbuffer[0] = ch; sbuffer.rotate_left(1);
                test.add(ch);
                DLIB_CASSERT(test.lookahead_buffer(test.get_lookahead_buffer_size()-1) == ch,"");
                DLIB_CASSERT(test.get_lookahead_buffer_size() == 20,"");
                DLIB_CASSERT(test.get_history_buffer_size() == 1,"");

                // add the above text to test and make sure it gives the correct results
                ch = sin.get();
                while (sin)
                {
                    sbuffer[0] = ch; sbuffer.rotate_left(1);
                    test.add(ch);
                    DLIB_CASSERT(test.lookahead_buffer(test.get_lookahead_buffer_size()-1) == ch,"");
                    DLIB_CASSERT(test.history_buffer(0) == sbuffer[21],"");
                    DLIB_CASSERT(test.history_buffer(1) == sbuffer[22],"");

                    ch = sin.get();
                }

                // make sure the contents of lookahead_buffer and history_buffer
                // match what is in sbuffer
                sbuffer.rotate_right(1);
                for (unsigned int i = 0; i < test.get_history_buffer_size(); ++i)
                {
                    DLIB_CASSERT(sbuffer[test.get_lookahead_buffer_limit()+i] == test.history_buffer(i),"");
                }
                for (unsigned int i = 0; i < test.get_lookahead_buffer_size(); ++i)
                {
                    DLIB_CASSERT(sbuffer[test.get_lookahead_buffer_limit()-1-i] == test.lookahead_buffer(i),"");
                }
                sbuffer.rotate_left(1);

                sbuffer.rotate_right(1);  // do this because we never put anything in sbuffer[0]

                unsigned long match_index, match_length;
                unsigned long ltemp = test.get_lookahead_buffer_size();
                test.find_match(match_index,match_length,0);
                DLIB_CASSERT(match_length <= ltemp,"");

                // verify the match with sbuffer
                for (unsigned int i = 0; i < match_length; ++i)
                {
                    DLIB_CASSERT(sbuffer[19-i] == sbuffer[match_index+20-i],i);
                }

                sin.str("");
                sin.clear();

            } // for (int g = 0; g < 2; ++g)

            for (int g = 0; g < 8; ++g)
            {
                test.clear();

                DLIB_CASSERT(test.get_lookahead_buffer_size() == 0,"");
                DLIB_CASSERT(test.get_history_buffer_size() == 0,"");
                DLIB_CASSERT(test.get_history_buffer_limit() == 256-20,"");
                DLIB_CASSERT(test.get_lookahead_buffer_limit() == 20,"");

                sbuf sbuffer;
                sbuffer.set_size(8);

                ostringstream sout;
                sout << "DLIB_CASSERT(test.get_lookahead_buffer_size() == 0,);\n";
                sout << "DLIB_CASSERT(test.get_history_buffer_size() == 0,);\n";
                sout << "DLIB_CASSERT(test.get_history_buffer_limit() == 256-20,);\n";
                sout << "DLIB_CASSERT(test.get_lookahead_buffer_limit() == 20,);\n";
                sout << "DLIB_CASSERT(test.get_lookahead_buffer_size() == 0,);\n";
                sout << "DLIB_CASSERT(test.get_history_buffer_limit() == 256-20,);\n";
                sout << "DLIB_CASSERT(test.get_lookahead_buffer_limit() == 20,);\n";
                sout << "DLIB_CASSERT(test.get_history_buffer_limit() == 256-20,);\n";
                sout << "DLIB_CASSERT(test.get_lookahead_buffer_size() == 0,);\n";
                sout << "DLIB_CASSERT(test.get_history_buffer_limit() == 256-20,);\n";
                sout << "DLIB_CASSERT(test.get_history_buffer_limit() == 256-20,);\n";
                istringstream sin(sout.str());

                unsigned char ch;
                for (int i = 0; i < 100; ++i)
                {
                    ch = sin.get();
                    sbuffer[0] = ch; sbuffer.rotate_left(1);
                    test.add(ch);
                }

                // make sure the contents of lookahead_buffer and history_buffer
                // match what is in sbuffer
                sbuffer.rotate_right(1);
                for (unsigned int i = 0; i < test.get_history_buffer_size(); ++i)
                {
                    DLIB_CASSERT(sbuffer[test.get_lookahead_buffer_limit()+i] == test.history_buffer(i),"");
                }
                for (unsigned int i = 0; i < test.get_lookahead_buffer_size(); ++i)
                {
                    DLIB_CASSERT(sbuffer[test.get_lookahead_buffer_limit()-1-i] == test.lookahead_buffer(i),"");
                }
                sbuffer.rotate_left(1);

                unsigned long match_index, match_length;
                unsigned long ltemp = test.get_lookahead_buffer_size();
                test.find_match(match_index,match_length,0);
                DLIB_CASSERT(match_length <= ltemp,"");

                DLIB_CASSERT(test.get_lookahead_buffer_size() == 20-match_length,"");

                sbuffer.rotate_right(1);  // do this because we never put anything in sbuffer[0]
                // verify the match with sbuffer
                for (unsigned int i = 0; i < match_length; ++i)
                {
                    DLIB_CASSERT(sbuffer[i+20-match_length] == sbuffer[i+1+match_index+20-match_length],"");
                }
                sbuffer.rotate_left(1);  // free up sbuffer[0] for new data

                for (int i = 0; i < 7+g*2; ++i)
                {
                    ch = sin.get();
                    sbuffer[0] = ch; sbuffer.rotate_left(1);
                    test.add(ch);
                }

                ch = '?';
                sbuffer[0] = ch; sbuffer.rotate_left(1);
                test.add(ch);
                ch = 'a';
                sbuffer[0] = ch; sbuffer.rotate_left(1);
                test.add(ch);
                ch = 'v';
                sbuffer[0] = ch; sbuffer.rotate_left(1);
                test.add(ch);
                ch = 'i';
                sbuffer[0] = ch; sbuffer.rotate_left(1);
                test.add(ch);
                ch = 's';
                sbuffer[0] = ch; sbuffer.rotate_left(1);
                test.add(ch);

                // adjust sbuffer due to the last call to test.find_match()
                // but only if we haven't already added enough (20 or more) chars
                // to fill the lookahead buffer already.
                if (match_length > static_cast<unsigned int>(12+g*2))
                    sbuffer.rotate_left(match_length-(12+g*2));

                // make sure the contents of lookahead_buffer and history_buffer
                // match what is in sbuffer
                sbuffer.rotate_right(1);
                for (unsigned int i = 0; i < test.get_history_buffer_size(); ++i)
                {
                    DLIB_CASSERT(sbuffer[test.get_lookahead_buffer_limit()+i] == test.history_buffer(i),"");
                }
                for (unsigned int i = 0; i < test.get_lookahead_buffer_size(); ++i)
                {
                    DLIB_CASSERT(sbuffer[test.get_lookahead_buffer_limit()-1-i] == test.lookahead_buffer(i),"");
                }
                sbuffer.rotate_left(1);

                test.find_match(match_index,match_length,10+g);

                if (match_length > 0)
                    DLIB_CASSERT(match_length >= static_cast<unsigned int>(10+g) , "");

                sbuffer.rotate_right(1);  // do this because we never put anything in sbuffer[0]
                // verify the match with sbuffer
                for (unsigned int i = 0; i < match_length; ++i)
                {
                    DLIB_CASSERT(sbuffer[i+20-match_length] == sbuffer[i+1+match_index+20-match_length],"");
                }
                sbuffer.rotate_left(1);  // free up sbuffer[0] for new data

            } // for (int g = 0; g < 8; ++g)

            srand(static_cast<unsigned int>(time(0)));

            for (int g = 0; g < 200; ++g)
            {
                test.clear();

                DLIB_CASSERT(test.get_lookahead_buffer_size() == 0,"");
                DLIB_CASSERT(test.get_history_buffer_size() == 0,"");
                DLIB_CASSERT(test.get_history_buffer_limit() == 256-20,"");
                DLIB_CASSERT(test.get_lookahead_buffer_limit() == 20,"");

                sbuf sbuffer;
                sbuffer.set_size(8);

                ostringstream sout;
                int l = ::rand()%500;
                for (int i = 0; i < l; ++i)
                {
                    char temp = static_cast<char>(::rand()%256);
                    sout << temp;
                }
                istringstream sin(sout.str());

                unsigned char ch;
                for (int i = 0; i < l; ++i)
                {
                    ch = sin.get();
                    sbuffer[0] = ch; sbuffer.rotate_left(1);
                    test.add(ch);
                }

                // make sure the contents of lookahead_buffer and history_buffer
                // match what is in sbuffer
                sbuffer.rotate_right(1);

                // adjust so that sbuffer[19] is the same as lookahead_buffer[0]
                if (test.get_lookahead_buffer_size() < 20)
                    sbuffer.rotate_left(20-test.get_lookahead_buffer_size());

                for (unsigned int i = 0; i < test.get_history_buffer_size(); ++i)
                {
                    DLIB_CASSERT(sbuffer[test.get_lookahead_buffer_limit()+i] == test.history_buffer(i),"");
                }
                for (unsigned int i = 0; i < test.get_lookahead_buffer_size(); ++i)
                {
                    DLIB_CASSERT(sbuffer[test.get_lookahead_buffer_limit()-1-i] == test.lookahead_buffer(i),"");
                }
                sbuffer.rotate_left(1);

                unsigned long match_index, match_length;
                unsigned long lookahead_size_before = test.get_lookahead_buffer_size();
                test.find_match(match_index,match_length,0);
                DLIB_CASSERT(match_length <= lookahead_size_before,"");

                DLIB_CASSERT(test.get_lookahead_buffer_size() == lookahead_size_before-match_length,"");

                sbuffer.rotate_right(1);  // do this because we never put anything in sbuffer[0]
                // verify the match with sbuffer
                for (unsigned int i = 0; i < match_length; ++i)
                {
                    DLIB_CASSERT(sbuffer[19-i] == sbuffer[match_index+20-i],i);
                }
                sbuffer.rotate_left(1);  // free up sbuffer[0] for new data

            } // for (int g = 0; g < 200; ++g)

            srand(static_cast<unsigned int>(time(0)));

            for (int g = 0; g < 300; ++g)
            {
                test.clear();

                DLIB_CASSERT(test.get_lookahead_buffer_size() == 0,"");
                DLIB_CASSERT(test.get_history_buffer_size() == 0,"");
                DLIB_CASSERT(test.get_history_buffer_limit() == 256-20,"");
                DLIB_CASSERT(test.get_lookahead_buffer_limit() == 20,"");

                sbuf sbuffer;
                sbuffer.set_size(8);

                ostringstream sout;
                int l = ::rand()%500;
                for (int i = 0; i < l; ++i)
                {
                    char temp = static_cast<char>(::rand()%20);
                    sout << temp;
                    sout << temp;
                    sout << temp;
                    sout << temp;
                    sout << temp;
                    sout << temp;
                }
                istringstream sin(sout.str());

                unsigned char ch;
                for (int i = 0; i < l; ++i)
                {
                    ch = sin.get();
                    sbuffer[0] = ch; sbuffer.rotate_left(1);
                    test.add(ch);
                }

                // make sure the contents of lookahead_buffer and history_buffer
                // match what is in sbuffer
                sbuffer.rotate_right(1);

                // adjust so that sbuffer[19] is the same as lookahead_buffer[0]
                if (test.get_lookahead_buffer_size() < 20)
                    sbuffer.rotate_left(20-test.get_lookahead_buffer_size());

                for (unsigned int i = 0; i < test.get_history_buffer_size(); ++i)
                {
                    DLIB_CASSERT(sbuffer[test.get_lookahead_buffer_limit()+i] == test.history_buffer(i),"");
                }
                for (unsigned int i = 0; i < test.get_lookahead_buffer_size(); ++i)
                {
                    DLIB_CASSERT(sbuffer[test.get_lookahead_buffer_limit()-1-i] == test.lookahead_buffer(i),"");
                }
                sbuffer.rotate_left(1);

                unsigned long match_index, match_length;
                unsigned long lookahead_size_before = test.get_lookahead_buffer_size();
                unsigned long history_size_before = test.get_history_buffer_size();
                test.find_match(match_index,match_length,2);

                if (match_length != 0)
                {
                    DLIB_CASSERT(match_index < history_size_before,
                                 "match_index: " << match_index <<
                                 "\nhistory_size_before: " << history_size_before);

                }

                DLIB_CASSERT(test.get_lookahead_buffer_size() == lookahead_size_before-match_length,"");

                sbuffer.rotate_right(1);  // do this because we never put anything in sbuffer[0]
                // verify the match with sbuffer
                for (unsigned int i = 0; i < match_length; ++i)
                {
                    DLIB_CASSERT(sbuffer[19-i] == sbuffer[match_index+20-i],i);
                }
                sbuffer.rotate_left(1);  // free up sbuffer[0] for new data

            } // for (int g = 0; g < 300; ++g)

        }

        class lz77_buffer_tester : public tester
        {
        public:
            lz77_buffer_tester (
            ) :
                tester ("test_lz77_buffer",
                        "Runs tests on the lz77_buffer component.")
            {}

            void perform_test (
            )
            {
                dlog << LINFO << "testing kernel_1a";
                lz77_buffer_kernel_test<lz77_buffer::kernel_1a>  ();
                dlog << LINFO << "testing kernel_1a_c";
                lz77_buffer_kernel_test<lz77_buffer::kernel_1a_c>();
                dlog << LINFO << "testing kernel_2a";
                lz77_buffer_kernel_test<lz77_buffer::kernel_2a>  ();
                dlog << LINFO << "testing kernel_2a_c";
                lz77_buffer_kernel_test<lz77_buffer::kernel_2a_c>();
            }
        } a;

    }