// Synthetic speed comparison of "virtual", "switch", "if-else O(N)", "if-else O(logN)" and "static".
// Tests are done for different "types" count (i.e. "case branches" or count of derived classes, etc).
// NOTE: try different settings: MAX_TYPES_COUNT, N, try to play with compiler optimization options,
//       process affinity mask, etc
// NOTE: Calculations are simple, in "static" case they can be very efficently optimized (folded).
// Author: Evgeny Panasyuk
 
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <ios>
 
#include <boost/ptr_container/ptr_vector.hpp>
#include <boost/preprocessor/repetition.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/mpl/for_each.hpp>
#include <boost/mpl/list.hpp>
#include <boost/config/suffix.hpp>
#include <boost/timer.hpp>
#include <boost/foreach.hpp>
 
template<int types_cnt> struct dispatch_base_shuffle_indexed;
template<int types_cnt> struct dispatch_base_regular;
 
//------------------------------Settings---------------------------------
 
#define IDEONE_DOT_COM // Comment this line - it is only for ideone.com
 
 
// Max types count. Tests will be done for 1 to MAX_TYPES_COUNT types
#define MAX_TYPES_COUNT 128
 
// Work amount for one test
const int N=100000;//100000
 
// Outter loop iterations
const int OUTER_ITERS=16;
 
template<int T>
struct dispatch_base
{
    // Select one of indexing type below:
 
    typedef dispatch_base_shuffle_indexed<T> type;
    //typedef dispatch_base_regular<T> type;
};
 
//------------------------------Common stuff-----------------------------
 
#ifdef IDEONE_DOT_COM
    #undef BOOST_FORCEINLINE
    #define BOOST_FORCEINLINE inline __attribute__ ((always_inline))
    #undef MAX_TYPES_COUNT
    #define MAX_TYPES_COUNT 64
#else
    #include <boost/range/algorithm/random_shuffle.hpp>
#endif
 
struct dispatch_data
{
    double elapsed;
    int result;
    const char *name;
};
 
template<class T,int types_cnt,int iters_cnt=(MAX_TYPES_COUNT*N/types_cnt)>
struct dispatch: public T
{
    void do_test()
    {
        data.result=0;
        this->init();
        boost::timer t;
        for (int i = 0; i !=iters_cnt; ++i)
        {
            data.result+=this->iter(i);
        }
        data.elapsed = t.elapsed();
        data.name=this->get_name();
    }
    dispatch_data data;
    static const int types_count=types_cnt;
    static const int iterations_cnt=iters_cnt;
};
 
template<template<int>class T,int types_cnt>
struct dispatch_m
{
    typedef dispatch<T<types_cnt>,types_cnt> type;
};
 
template<int types_cnt>
struct dispatch_base_regular
{
    BOOST_FORCEINLINE int get_type_t(int i)
    {
        return i;
    }
};
 
template<int types_cnt>
struct dispatch_base_shuffle_indexed
{
    typedef std::vector<int> index_vector_t;
    dispatch_base_shuffle_indexed(): current_i(0)
    {
        for(int d=0;d!=deck_count;++d)
        {
            for(int i=0;i!=types_cnt;++i)
            {
                index.push_back(i);
            }
#ifndef IDEONE_DOT_COM
            boost::random_shuffle(boost::iterator_range<index_vector_t::iterator>(index.begin()+d*types_cnt,index.begin()+(d+1)*types_cnt));
#else
            std::random_shuffle(index.begin()+d*types_cnt,index.begin()+(d+1)*types_cnt);
#endif
        }
    }
    BOOST_FORCEINLINE int get_type_t(int i)
    {
        return index[(current_i++)%index.size()];
    }
private:
    static const int deck_count=128;
    index_vector_t index;
    int current_i;
};
 
template<int types_cnt,template<int,int>class T>
struct branch_dispatch_base: protected dispatch_base<types_cnt>::type
{
protected:
    std::vector<int> v;
public:
    void init()
    {
        for (int i = 0; i != types_cnt; ++i)
        {
            v.push_back(i);
        }
    }
    BOOST_FORCEINLINE int iter(int i)
    {
        int result=0;
        for(int t=0;t!=types_cnt;++t)
        {
            result+=T<types_cnt,types_cnt>::call(v[this->get_type_t(t)],i);
        }
        return result;
    }
};
 
#define CALC (x+p)
 
//------------------------Stuff for "switch" test------------------------
template<int p>
BOOST_FORCEINLINE int func(int x)
{
    return CALC;
};
 
#define CASE_MACRO(z, p, unused) case p:return func<p>(i);
 
template<int p,int>
struct test_switch;
 
#define SWITCH_FUNCS(z, p, unused) \
template<int types_cnt> \
struct test_switch<p+1,types_cnt> \
{ \
    BOOST_FORCEINLINE static int call(int x,int i) \
    { \
        switch(x) \
        { \
            BOOST_PP_REPEAT(BOOST_PP_ADD(p,1), CASE_MACRO, ~) \
            default:return -1; \
        } \
    } \
};
 
BOOST_PP_REPEAT(MAX_TYPES_COUNT, SWITCH_FUNCS, ~)
 
template<int types_cnt>
struct switch_dispatch: public branch_dispatch_base<types_cnt,test_switch>
{
    static const char * const get_name()
    {
        return "switch";
    };
};
 
//----------------------------Stuff for "if-else O(N)"-------------------
 
template<int p,int types_cnt>
struct test_ifelse_on
{
    BOOST_FORCEINLINE static int call(int x,int i)
    {
        if(x==(types_cnt-p))
            return func<types_cnt-p>(i);
        return test_ifelse_on<p-1,types_cnt>::call(x,i);
    }
};
 
template<int types_cnt>
struct test_ifelse_on<0,types_cnt>
{
    BOOST_FORCEINLINE static int call(int x,int i)
    {
        return -1;
    }
};
 
template<int types_cnt>
struct ifelse_on_dispatch: public branch_dispatch_base<types_cnt,test_ifelse_on>
{
    static const char * const get_name()
    {
        return "if-else_O(N)";
    };
};
 
//----------------------Stuff for "if-else O(logN)"----------------------
template<int lower,int upper/*,int level*/>
struct test_ifelse_ologn
{
    BOOST_FORCEINLINE static int call(int x,int i)
    {
        const int middle=(lower+upper)/2;
        if(x>middle)
            return test_ifelse_ologn<middle+1,upper/*,level-1*/>::call(x,i);
        else
            return test_ifelse_ologn<lower,middle/*,level-1*/>::call(x,i);
    }
};
 
template<int lower>
struct test_ifelse_ologn<lower,lower>
{
    BOOST_FORCEINLINE static int call(int x,int i)
    {
        return lower+i;
    }
};
 
template<int types_cnt,int>
struct test_ifelse_ologn_m: public test_ifelse_ologn<0,types_cnt-1>
{
};
 
template<int types_cnt>
struct ifelse_ologn_dispatch: public branch_dispatch_base<types_cnt,test_ifelse_ologn_m>
{
    static const char * const get_name()
    {
        return "if-else_O(log(N))";
    };
};
 
//---------------------Stuff for "virtual" call test---------------------
struct base
{
    virtual int call(int x)=0;
};
 
template<int p>
class derived: public base
{
    virtual int call(int x)
    {
        return CALC;
    };
};
 
template<int p>
struct fill_vector
{
    static void f(boost::ptr_vector<base> &v)
    {
        fill_vector<p-1>::f(v);
        v.push_back(new derived<p-1>());
    }
};
 
template<>
struct fill_vector<0>
{
    static void f(boost::ptr_vector<base> &v) {}
};
 
template<int types_cnt>
struct virtual_dispatch: protected dispatch_base<types_cnt>::type
{
    void init()
    {
        fill_vector<types_cnt>::f(v);
    }
    BOOST_FORCEINLINE int iter(int i)
    {
        int result=0;
        for(int t=0;t!=types_cnt;++t)
        {
            result+=v[this->get_type_t(t)].call(i);
        }
        return result;
    }
    static const char * const get_name()
    {
        return "virtual";
    };
private:
    boost::ptr_vector<base> v;
};
 
//---------------------Stuff for "static" call test----------------------
 
// It is possible to omit this struct, it just for "emulate" policies
// (for cases when compiler can't do good optimizations)
template<class T> 
struct static_call: public T
{
};
 
template<int p>
struct static_call_policy
{
    static BOOST_FORCEINLINE int static_func(int x)
    {
        return static_call_policy<p-1>::static_func(x)+CALC;
    };
};
 
template<>
struct static_call_policy<0>
{
    static BOOST_FORCEINLINE int static_func(int x)
    {
        return x;
    };
};
 
template<int types_cnt>
struct static_dispatch
{
    void init() {}
    BOOST_FORCEINLINE int iter(int i)
    {
        return static_call< static_call_policy<types_cnt-1> >::static_func(i);
    }
    static const char * const get_name()
    {
        return "static";
    };
};
//-----------------------------Testing stuff-----------------------------
 
template<int types_cnt>
struct dispatchers_t
{
    typedef boost::mpl::list
    <
        typename dispatch_m<static_dispatch,types_cnt>::type,
        typename dispatch_m<switch_dispatch,types_cnt>::type,
        typename dispatch_m<virtual_dispatch,types_cnt>::type,
        typename dispatch_m<ifelse_ologn_dispatch,types_cnt>::type,
        typename dispatch_m<ifelse_on_dispatch,types_cnt>::type
    > type;
};
 
struct test_elapsed
{
    template<class D>
    void operator()(D &d)
    {
        d.do_test();
        if((results.size()>0)&&(results[0].result!=d.data.result))
        {
            std::cerr << "results do not match" << std::endl;
        }
        std::cout << "\t" << d.data.name << " elapsed=" << (1.0e9*d.data.elapsed/(d.iterations_cnt*d.types_count)) /*<< " result=" << d.data.result*/ << std::endl;
        BOOST_FOREACH( dispatch_data data, results )
        {
            std::cout << "\t\t" << d.data.name << "/" << data.name << "=" << d.data.elapsed/data.elapsed << "x (elapsed)" << std::endl;
        }
        results.push_back(d.data);
    }
    std::vector<dispatch_data> results;
};
 
template<int types_cnt>
struct do_tests
{
    static void f()
    {
        do_tests<types_cnt-1>::f();
        std::cout << "Types count=" << types_cnt << std::endl;
        std::cout << "\tTypes count=" << types_cnt << std::endl;
        boost::mpl::for_each<typename dispatchers_t<types_cnt>::type>(test_elapsed());
        std::cout << std::endl;
    }
};
 
template<>
struct do_tests<0>
{
    static void f() {}
};
 
//-----------------------------------------------------------------------
int main(int argc,char **argv)
{
    std::cout.setf(std::ios_base::fixed, std::ios_base::floatfield);
    //std::cout.precision(3);
    for(int i=0;i!=OUTER_ITERS;++i)
    {
        std::cout << "I=" << i << std::endl;
        do_tests<MAX_TYPES_COUNT>::f();
    }
}
 
 

Ly8gU3ludGhldGljIHNwZWVkIGNvbXBhcmlzb24gb2YgInZpcnR1YWwiLCAic3dpdGNoIiwgImlmLWVsc2UgTyhOKSIsICJpZi1lbHNlIE8obG9nTikiIGFuZCAic3RhdGljIi4KLy8gVGVzdHMgYXJlIGRvbmUgZm9yIGRpZmZlcmVudCAidHlwZXMiIGNvdW50IChpLmUuICJjYXNlIGJyYW5jaGVzIiBvciBjb3VudCBvZiBkZXJpdmVkIGNsYXNzZXMsIGV0YykuCi8vIE5PVEU6IHRyeSBkaWZmZXJlbnQgc2V0dGluZ3M6IE1BWF9UWVBFU19DT1VOVCwgTiwgdHJ5IHRvIHBsYXkgd2l0aCBjb21waWxlciBvcHRpbWl6YXRpb24gb3B0aW9ucywKLy8gICAgICAgcHJvY2VzcyBhZmZpbml0eSBtYXNrLCBldGMKLy8gTk9URTogQ2FsY3VsYXRpb25zIGFyZSBzaW1wbGUsIGluICJzdGF0aWMiIGNhc2UgdGhleSBjYW4gYmUgdmVyeSBlZmZpY2VudGx5IG9wdGltaXplZCAoZm9sZGVkKS4KLy8gQXV0aG9yOiBFdmdlbnkgUGFuYXN5dWsKCiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGlvbWFuaXA+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxpb3M+CgojaW5jbHVkZSA8Ym9vc3QvcHRyX2NvbnRhaW5lci9wdHJfdmVjdG9yLmhwcD4KI2luY2x1ZGUgPGJvb3N0L3ByZXByb2Nlc3Nvci9yZXBldGl0aW9uLmhwcD4KI2luY2x1ZGUgPGJvb3N0L3JhbmdlL2l0ZXJhdG9yX3JhbmdlLmhwcD4KI2luY2x1ZGUgPGJvb3N0L21wbC9mb3JfZWFjaC5ocHA+CiNpbmNsdWRlIDxib29zdC9tcGwvbGlzdC5ocHA+CiNpbmNsdWRlIDxib29zdC9jb25maWcvc3VmZml4LmhwcD4KI2luY2x1ZGUgPGJvb3N0L3RpbWVyLmhwcD4KI2luY2x1ZGUgPGJvb3N0L2ZvcmVhY2guaHBwPgoKdGVtcGxhdGU8aW50IHR5cGVzX2NudD4gc3RydWN0IGRpc3BhdGNoX2Jhc2Vfc2h1ZmZsZV9pbmRleGVkOwp0ZW1wbGF0ZTxpbnQgdHlwZXNfY250PiBzdHJ1Y3QgZGlzcGF0Y2hfYmFzZV9yZWd1bGFyOwoKLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS1TZXR0aW5ncy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQoKI2RlZmluZSBJREVPTkVfRE9UX0NPTSAvLyBDb21tZW50IHRoaXMgbGluZSAtIGl0IGlzIG9ubHkgZm9yIGlkZW9uZS5jb20KCgovLyBNYXggdHlwZXMgY291bnQuIFRlc3RzIHdpbGwgYmUgZG9uZSBmb3IgMSB0byBNQVhfVFlQRVNfQ09VTlQgdHlwZXMKI2RlZmluZSBNQVhfVFlQRVNfQ09VTlQgMTI4CgovLyBXb3JrIGFtb3VudCBmb3Igb25lIHRlc3QKY29uc3QgaW50IE49MTAwMDAwOy8vMTAwMDAwCgovLyBPdXR0ZXIgbG9vcCBpdGVyYXRpb25zCmNvbnN0IGludCBPVVRFUl9JVEVSUz0xNjsKCnRlbXBsYXRlPGludCBUPgpzdHJ1Y3QgZGlzcGF0Y2hfYmFzZQp7CiAgICAvLyBTZWxlY3Qgb25lIG9mIGluZGV4aW5nIHR5cGUgYmVsb3c6CgogICAgdHlwZWRlZiBkaXNwYXRjaF9iYXNlX3NodWZmbGVfaW5kZXhlZDxUPiB0eXBlOwogICAgLy90eXBlZGVmIGRpc3BhdGNoX2Jhc2VfcmVndWxhcjxUPiB0eXBlOwp9OwoKLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS1Db21tb24gc3R1ZmYtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQoKI2lmZGVmIElERU9ORV9ET1RfQ09NCiAgICAjdW5kZWYgQk9PU1RfRk9SQ0VJTkxJTkUKICAgICNkZWZpbmUgQk9PU1RfRk9SQ0VJTkxJTkUgaW5saW5lIF9fYXR0cmlidXRlX18gKChhbHdheXNfaW5saW5lKSkKICAgICN1bmRlZiBNQVhfVFlQRVNfQ09VTlQKICAgICNkZWZpbmUgTUFYX1RZUEVTX0NPVU5UIDY0CiNlbHNlCiAgICAjaW5jbHVkZSA8Ym9vc3QvcmFuZ2UvYWxnb3JpdGhtL3JhbmRvbV9zaHVmZmxlLmhwcD4KI2VuZGlmCgpzdHJ1Y3QgZGlzcGF0Y2hfZGF0YQp7CiAgICBkb3VibGUgZWxhcHNlZDsKICAgIGludCByZXN1bHQ7CiAgICBjb25zdCBjaGFyICpuYW1lOwp9OwoKdGVtcGxhdGU8Y2xhc3MgVCxpbnQgdHlwZXNfY250LGludCBpdGVyc19jbnQ9KE1BWF9UWVBFU19DT1VOVCpOL3R5cGVzX2NudCk+CnN0cnVjdCBkaXNwYXRjaDogcHVibGljIFQKewogICAgdm9pZCBkb190ZXN0KCkKICAgIHsKICAgICAgICBkYXRhLnJlc3VsdD0wOwogICAgICAgIHRoaXMtPmluaXQoKTsKICAgICAgICBib29zdDo6dGltZXIgdDsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSAhPWl0ZXJzX2NudDsgKytpKQogICAgICAgIHsKICAgICAgICAgICAgZGF0YS5yZXN1bHQrPXRoaXMtPml0ZXIoaSk7CiAgICAgICAgfQogICAgICAgIGRhdGEuZWxhcHNlZCA9IHQuZWxhcHNlZCgpOwogICAgICAgIGRhdGEubmFtZT10aGlzLT5nZXRfbmFtZSgpOwogICAgfQogICAgZGlzcGF0Y2hfZGF0YSBkYXRhOwogICAgc3RhdGljIGNvbnN0IGludCB0eXBlc19jb3VudD10eXBlc19jbnQ7CiAgICBzdGF0aWMgY29uc3QgaW50IGl0ZXJhdGlvbnNfY250PWl0ZXJzX2NudDsKfTsKCnRlbXBsYXRlPHRlbXBsYXRlPGludD5jbGFzcyBULGludCB0eXBlc19jbnQ+CnN0cnVjdCBkaXNwYXRjaF9tCnsKICAgIHR5cGVkZWYgZGlzcGF0Y2g8VDx0eXBlc19jbnQ+LHR5cGVzX2NudD4gdHlwZTsKfTsKCnRlbXBsYXRlPGludCB0eXBlc19jbnQ+CnN0cnVjdCBkaXNwYXRjaF9iYXNlX3JlZ3VsYXIKewogICAgQk9PU1RfRk9SQ0VJTkxJTkUgaW50IGdldF90eXBlX3QoaW50IGkpCiAgICB7CiAgICAgICAgcmV0dXJuIGk7CiAgICB9Cn07Cgp0ZW1wbGF0ZTxpbnQgdHlwZXNfY250PgpzdHJ1Y3QgZGlzcGF0Y2hfYmFzZV9zaHVmZmxlX2luZGV4ZWQKewogICAgdHlwZWRlZiBzdGQ6OnZlY3RvcjxpbnQ+IGluZGV4X3ZlY3Rvcl90OwogICAgZGlzcGF0Y2hfYmFzZV9zaHVmZmxlX2luZGV4ZWQoKTogY3VycmVudF9pKDApCiAgICB7CiAgICAgICAgZm9yKGludCBkPTA7ZCE9ZGVja19jb3VudDsrK2QpCiAgICAgICAgewogICAgICAgICAgICBmb3IoaW50IGk9MDtpIT10eXBlc19jbnQ7KytpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpbmRleC5wdXNoX2JhY2soaSk7CiAgICAgICAgICAgIH0KI2lmbmRlZiBJREVPTkVfRE9UX0NPTQogICAgICAgICAgICBib29zdDo6cmFuZG9tX3NodWZmbGUoYm9vc3Q6Oml0ZXJhdG9yX3JhbmdlPGluZGV4X3ZlY3Rvcl90OjppdGVyYXRvcj4oaW5kZXguYmVnaW4oKStkKnR5cGVzX2NudCxpbmRleC5iZWdpbigpKyhkKzEpKnR5cGVzX2NudCkpOwojZWxzZQogICAgICAgICAgICBzdGQ6OnJhbmRvbV9zaHVmZmxlKGluZGV4LmJlZ2luKCkrZCp0eXBlc19jbnQsaW5kZXguYmVnaW4oKSsoZCsxKSp0eXBlc19jbnQpOwojZW5kaWYKICAgICAgICB9CiAgICB9CiAgICBCT09TVF9GT1JDRUlOTElORSBpbnQgZ2V0X3R5cGVfdChpbnQgaSkKICAgIHsKICAgICAgICByZXR1cm4gaW5kZXhbKGN1cnJlbnRfaSsrKSVpbmRleC5zaXplKCldOwogICAgfQpwcml2YXRlOgogICAgc3RhdGljIGNvbnN0IGludCBkZWNrX2NvdW50PTEyODsKICAgIGluZGV4X3ZlY3Rvcl90IGluZGV4OwogICAgaW50IGN1cnJlbnRfaTsKfTsKCnRlbXBsYXRlPGludCB0eXBlc19jbnQsdGVtcGxhdGU8aW50LGludD5jbGFzcyBUPgpzdHJ1Y3QgYnJhbmNoX2Rpc3BhdGNoX2Jhc2U6IHByb3RlY3RlZCBkaXNwYXRjaF9iYXNlPHR5cGVzX2NudD46OnR5cGUKewpwcm90ZWN0ZWQ6CiAgICBzdGQ6OnZlY3RvcjxpbnQ+IHY7CnB1YmxpYzoKICAgIHZvaWQgaW5pdCgpCiAgICB7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgIT0gdHlwZXNfY250OyArK2kpCiAgICAgICAgewogICAgICAgICAgICB2LnB1c2hfYmFjayhpKTsKICAgICAgICB9CiAgICB9CiAgICBCT09TVF9GT1JDRUlOTElORSBpbnQgaXRlcihpbnQgaSkKICAgIHsKICAgICAgICBpbnQgcmVzdWx0PTA7CiAgICAgICAgZm9yKGludCB0PTA7dCE9dHlwZXNfY250OysrdCkKICAgICAgICB7CiAgICAgICAgICAgIHJlc3VsdCs9VDx0eXBlc19jbnQsdHlwZXNfY250Pjo6Y2FsbCh2W3RoaXMtPmdldF90eXBlX3QodCldLGkpOwogICAgICAgIH0KICAgICAgICByZXR1cm4gcmVzdWx0OwogICAgfQp9OwoKI2RlZmluZSBDQUxDICh4K3ApCgovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLVN0dWZmIGZvciAic3dpdGNoIiB0ZXN0LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCnRlbXBsYXRlPGludCBwPgpCT09TVF9GT1JDRUlOTElORSBpbnQgZnVuYyhpbnQgeCkKewogICAgcmV0dXJuIENBTEM7Cn07CgojZGVmaW5lIENBU0VfTUFDUk8oeiwgcCwgdW51c2VkKSBjYXNlIHA6cmV0dXJuIGZ1bmM8cD4oaSk7Cgp0ZW1wbGF0ZTxpbnQgcCxpbnQ+CnN0cnVjdCB0ZXN0X3N3aXRjaDsKCiNkZWZpbmUgU1dJVENIX0ZVTkNTKHosIHAsIHVudXNlZCkgXAp0ZW1wbGF0ZTxpbnQgdHlwZXNfY250PiBcCnN0cnVjdCB0ZXN0X3N3aXRjaDxwKzEsdHlwZXNfY250PiBcCnsgXAogICAgQk9PU1RfRk9SQ0VJTkxJTkUgc3RhdGljIGludCBjYWxsKGludCB4LGludCBpKSBcCiAgICB7IFwKICAgICAgICBzd2l0Y2goeCkgXAogICAgICAgIHsgXAogICAgICAgICAgICBCT09TVF9QUF9SRVBFQVQoQk9PU1RfUFBfQUREKHAsMSksIENBU0VfTUFDUk8sIH4pIFwKICAgICAgICAgICAgZGVmYXVsdDpyZXR1cm4gLTE7IFwKICAgICAgICB9IFwKICAgIH0gXAp9OwoKQk9PU1RfUFBfUkVQRUFUKE1BWF9UWVBFU19DT1VOVCwgU1dJVENIX0ZVTkNTLCB+KQoKdGVtcGxhdGU8aW50IHR5cGVzX2NudD4Kc3RydWN0IHN3aXRjaF9kaXNwYXRjaDogcHVibGljIGJyYW5jaF9kaXNwYXRjaF9iYXNlPHR5cGVzX2NudCx0ZXN0X3N3aXRjaD4KewogICAgc3RhdGljIGNvbnN0IGNoYXIgKiBjb25zdCBnZXRfbmFtZSgpCiAgICB7CiAgICAgICAgcmV0dXJuICJzd2l0Y2giOwogICAgfTsKfTsKCi8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLVN0dWZmIGZvciAiaWYtZWxzZSBPKE4pIi0tLS0tLS0tLS0tLS0tLS0tLS0KCnRlbXBsYXRlPGludCBwLGludCB0eXBlc19jbnQ+CnN0cnVjdCB0ZXN0X2lmZWxzZV9vbgp7CiAgICBCT09TVF9GT1JDRUlOTElORSBzdGF0aWMgaW50IGNhbGwoaW50IHgsaW50IGkpCiAgICB7CiAgICAgICAgaWYoeD09KHR5cGVzX2NudC1wKSkKICAgICAgICAgICAgcmV0dXJuIGZ1bmM8dHlwZXNfY250LXA+KGkpOwogICAgICAgIHJldHVybiB0ZXN0X2lmZWxzZV9vbjxwLTEsdHlwZXNfY250Pjo6Y2FsbCh4LGkpOwogICAgfQp9OwoKdGVtcGxhdGU8aW50IHR5cGVzX2NudD4Kc3RydWN0IHRlc3RfaWZlbHNlX29uPDAsdHlwZXNfY250Pgp7CiAgICBCT09TVF9GT1JDRUlOTElORSBzdGF0aWMgaW50IGNhbGwoaW50IHgsaW50IGkpCiAgICB7CiAgICAgICAgcmV0dXJuIC0xOwogICAgfQp9OwoKdGVtcGxhdGU8aW50IHR5cGVzX2NudD4Kc3RydWN0IGlmZWxzZV9vbl9kaXNwYXRjaDogcHVibGljIGJyYW5jaF9kaXNwYXRjaF9iYXNlPHR5cGVzX2NudCx0ZXN0X2lmZWxzZV9vbj4KewogICAgc3RhdGljIGNvbnN0IGNoYXIgKiBjb25zdCBnZXRfbmFtZSgpCiAgICB7CiAgICAgICAgcmV0dXJuICJpZi1lbHNlX08oTikiOwogICAgfTsKfTsKCi8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLVN0dWZmIGZvciAiaWYtZWxzZSBPKGxvZ04pIi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KdGVtcGxhdGU8aW50IGxvd2VyLGludCB1cHBlci8qLGludCBsZXZlbCovPgpzdHJ1Y3QgdGVzdF9pZmVsc2Vfb2xvZ24KewogICAgQk9PU1RfRk9SQ0VJTkxJTkUgc3RhdGljIGludCBjYWxsKGludCB4LGludCBpKQogICAgewogICAgICAgIGNvbnN0IGludCBtaWRkbGU9KGxvd2VyK3VwcGVyKS8yOwogICAgICAgIGlmKHg+bWlkZGxlKQogICAgICAgICAgICByZXR1cm4gdGVzdF9pZmVsc2Vfb2xvZ248bWlkZGxlKzEsdXBwZXIvKixsZXZlbC0xKi8+OjpjYWxsKHgsaSk7CiAgICAgICAgZWxzZQogICAgICAgICAgICByZXR1cm4gdGVzdF9pZmVsc2Vfb2xvZ248bG93ZXIsbWlkZGxlLyosbGV2ZWwtMSovPjo6Y2FsbCh4LGkpOwogICAgfQp9OwoKdGVtcGxhdGU8aW50IGxvd2VyPgpzdHJ1Y3QgdGVzdF9pZmVsc2Vfb2xvZ248bG93ZXIsbG93ZXI+CnsKICAgIEJPT1NUX0ZPUkNFSU5MSU5FIHN0YXRpYyBpbnQgY2FsbChpbnQgeCxpbnQgaSkKICAgIHsKICAgICAgICByZXR1cm4gbG93ZXIraTsKICAgIH0KfTsKCnRlbXBsYXRlPGludCB0eXBlc19jbnQsaW50PgpzdHJ1Y3QgdGVzdF9pZmVsc2Vfb2xvZ25fbTogcHVibGljIHRlc3RfaWZlbHNlX29sb2duPDAsdHlwZXNfY250LTE+CnsKfTsKCnRlbXBsYXRlPGludCB0eXBlc19jbnQ+CnN0cnVjdCBpZmVsc2Vfb2xvZ25fZGlzcGF0Y2g6IHB1YmxpYyBicmFuY2hfZGlzcGF0Y2hfYmFzZTx0eXBlc19jbnQsdGVzdF9pZmVsc2Vfb2xvZ25fbT4KewogICAgc3RhdGljIGNvbnN0IGNoYXIgKiBjb25zdCBnZXRfbmFtZSgpCiAgICB7CiAgICAgICAgcmV0dXJuICJpZi1lbHNlX08obG9nKE4pKSI7CiAgICB9Owp9OwoKLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS1TdHVmZiBmb3IgInZpcnR1YWwiIGNhbGwgdGVzdC0tLS0tLS0tLS0tLS0tLS0tLS0tLQpzdHJ1Y3QgYmFzZQp7CiAgICB2aXJ0dWFsIGludCBjYWxsKGludCB4KT0wOwp9OwoKdGVtcGxhdGU8aW50IHA+CmNsYXNzIGRlcml2ZWQ6IHB1YmxpYyBiYXNlCnsKICAgIHZpcnR1YWwgaW50IGNhbGwoaW50IHgpCiAgICB7CiAgICAgICAgcmV0dXJuIENBTEM7CiAgICB9Owp9OwoKdGVtcGxhdGU8aW50IHA+CnN0cnVjdCBmaWxsX3ZlY3Rvcgp7CiAgICBzdGF0aWMgdm9pZCBmKGJvb3N0OjpwdHJfdmVjdG9yPGJhc2U+ICZ2KQogICAgewogICAgICAgIGZpbGxfdmVjdG9yPHAtMT46OmYodik7CiAgICAgICAgdi5wdXNoX2JhY2sobmV3IGRlcml2ZWQ8cC0xPigpKTsKICAgIH0KfTsKCnRlbXBsYXRlPD4Kc3RydWN0IGZpbGxfdmVjdG9yPDA+CnsKICAgIHN0YXRpYyB2b2lkIGYoYm9vc3Q6OnB0cl92ZWN0b3I8YmFzZT4gJnYpIHt9Cn07Cgp0ZW1wbGF0ZTxpbnQgdHlwZXNfY250PgpzdHJ1Y3QgdmlydHVhbF9kaXNwYXRjaDogcHJvdGVjdGVkIGRpc3BhdGNoX2Jhc2U8dHlwZXNfY250Pjo6dHlwZQp7CiAgICB2b2lkIGluaXQoKQogICAgewogICAgICAgIGZpbGxfdmVjdG9yPHR5cGVzX2NudD46OmYodik7CiAgICB9CiAgICBCT09TVF9GT1JDRUlOTElORSBpbnQgaXRlcihpbnQgaSkKICAgIHsKICAgICAgICBpbnQgcmVzdWx0PTA7CiAgICAgICAgZm9yKGludCB0PTA7dCE9dHlwZXNfY250OysrdCkKICAgICAgICB7CiAgICAgICAgICAgIHJlc3VsdCs9dlt0aGlzLT5nZXRfdHlwZV90KHQpXS5jYWxsKGkpOwogICAgICAgIH0KICAgICAgICByZXR1cm4gcmVzdWx0OwogICAgfQogICAgc3RhdGljIGNvbnN0IGNoYXIgKiBjb25zdCBnZXRfbmFtZSgpCiAgICB7CiAgICAgICAgcmV0dXJuICJ2aXJ0dWFsIjsKICAgIH07CnByaXZhdGU6CiAgICBib29zdDo6cHRyX3ZlY3RvcjxiYXNlPiB2Owp9OwoKLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS1TdHVmZiBmb3IgInN0YXRpYyIgY2FsbCB0ZXN0LS0tLS0tLS0tLS0tLS0tLS0tLS0tLQoKLy8gSXQgaXMgcG9zc2libGUgdG8gb21pdCB0aGlzIHN0cnVjdCwgaXQganVzdCBmb3IgImVtdWxhdGUiIHBvbGljaWVzCi8vIChmb3IgY2FzZXMgd2hlbiBjb21waWxlciBjYW4ndCBkbyBnb29kIG9wdGltaXphdGlvbnMpCnRlbXBsYXRlPGNsYXNzIFQ+IApzdHJ1Y3Qgc3RhdGljX2NhbGw6IHB1YmxpYyBUCnsKfTsKCnRlbXBsYXRlPGludCBwPgpzdHJ1Y3Qgc3RhdGljX2NhbGxfcG9saWN5CnsKICAgIHN0YXRpYyBCT09TVF9GT1JDRUlOTElORSBpbnQgc3RhdGljX2Z1bmMoaW50IHgpCiAgICB7CiAgICAgICAgcmV0dXJuIHN0YXRpY19jYWxsX3BvbGljeTxwLTE+OjpzdGF0aWNfZnVuYyh4KStDQUxDOwogICAgfTsKfTsKCnRlbXBsYXRlPD4Kc3RydWN0IHN0YXRpY19jYWxsX3BvbGljeTwwPgp7CiAgICBzdGF0aWMgQk9PU1RfRk9SQ0VJTkxJTkUgaW50IHN0YXRpY19mdW5jKGludCB4KQogICAgewogICAgICAgIHJldHVybiB4OwogICAgfTsKfTsKCnRlbXBsYXRlPGludCB0eXBlc19jbnQ+CnN0cnVjdCBzdGF0aWNfZGlzcGF0Y2gKewogICAgdm9pZCBpbml0KCkge30KICAgIEJPT1NUX0ZPUkNFSU5MSU5FIGludCBpdGVyKGludCBpKQogICAgewogICAgICAgIHJldHVybiBzdGF0aWNfY2FsbDwgc3RhdGljX2NhbGxfcG9saWN5PHR5cGVzX2NudC0xPiA+OjpzdGF0aWNfZnVuYyhpKTsKICAgIH0KICAgIHN0YXRpYyBjb25zdCBjaGFyICogY29uc3QgZ2V0X25hbWUoKQogICAgewogICAgICAgIHJldHVybiAic3RhdGljIjsKICAgIH07Cn07Ci8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS1UZXN0aW5nIHN0dWZmLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCnRlbXBsYXRlPGludCB0eXBlc19jbnQ+CnN0cnVjdCBkaXNwYXRjaGVyc190CnsKICAgIHR5cGVkZWYgYm9vc3Q6Om1wbDo6bGlzdAogICAgPAogICAgICAgIHR5cGVuYW1lIGRpc3BhdGNoX208c3RhdGljX2Rpc3BhdGNoLHR5cGVzX2NudD46OnR5cGUsCiAgICAgICAgdHlwZW5hbWUgZGlzcGF0Y2hfbTxzd2l0Y2hfZGlzcGF0Y2gsdHlwZXNfY250Pjo6dHlwZSwKICAgICAgICB0eXBlbmFtZSBkaXNwYXRjaF9tPHZpcnR1YWxfZGlzcGF0Y2gsdHlwZXNfY250Pjo6dHlwZSwKICAgICAgICB0eXBlbmFtZSBkaXNwYXRjaF9tPGlmZWxzZV9vbG9nbl9kaXNwYXRjaCx0eXBlc19jbnQ+Ojp0eXBlLAogICAgICAgIHR5cGVuYW1lIGRpc3BhdGNoX208aWZlbHNlX29uX2Rpc3BhdGNoLHR5cGVzX2NudD46OnR5cGUKICAgID4gdHlwZTsKfTsKCnN0cnVjdCB0ZXN0X2VsYXBzZWQKewogICAgdGVtcGxhdGU8Y2xhc3MgRD4KICAgIHZvaWQgb3BlcmF0b3IoKShEICZkKQogICAgewogICAgICAgIGQuZG9fdGVzdCgpOwogICAgICAgIGlmKChyZXN1bHRzLnNpemUoKT4wKSYmKHJlc3VsdHNbMF0ucmVzdWx0IT1kLmRhdGEucmVzdWx0KSkKICAgICAgICB7CiAgICAgICAgICAgIHN0ZDo6Y2VyciA8PCAicmVzdWx0cyBkbyBub3QgbWF0Y2giIDw8IHN0ZDo6ZW5kbDsKICAgICAgICB9CiAgICAgICAgc3RkOjpjb3V0IDw8ICJcdCIgPDwgZC5kYXRhLm5hbWUgPDwgIiBlbGFwc2VkPSIgPDwgKDEuMGU5KmQuZGF0YS5lbGFwc2VkLyhkLml0ZXJhdGlvbnNfY250KmQudHlwZXNfY291bnQpKSAvKjw8ICIgcmVzdWx0PSIgPDwgZC5kYXRhLnJlc3VsdCovIDw8IHN0ZDo6ZW5kbDsKICAgICAgICBCT09TVF9GT1JFQUNIKCBkaXNwYXRjaF9kYXRhIGRhdGEsIHJlc3VsdHMgKQogICAgICAgIHsKICAgICAgICAgICAgc3RkOjpjb3V0IDw8ICJcdFx0IiA8PCBkLmRhdGEubmFtZSA8PCAiLyIgPDwgZGF0YS5uYW1lIDw8ICI9IiA8PCBkLmRhdGEuZWxhcHNlZC9kYXRhLmVsYXBzZWQgPDwgInggKGVsYXBzZWQpIiA8PCBzdGQ6OmVuZGw7CiAgICAgICAgfQogICAgICAgIHJlc3VsdHMucHVzaF9iYWNrKGQuZGF0YSk7CiAgICB9CiAgICBzdGQ6OnZlY3RvcjxkaXNwYXRjaF9kYXRhPiByZXN1bHRzOwp9OwoKdGVtcGxhdGU8aW50IHR5cGVzX2NudD4Kc3RydWN0IGRvX3Rlc3RzCnsKICAgIHN0YXRpYyB2b2lkIGYoKQogICAgewogICAgICAgIGRvX3Rlc3RzPHR5cGVzX2NudC0xPjo6ZigpOwogICAgICAgIHN0ZDo6Y291dCA8PCAiVHlwZXMgY291bnQ9IiA8PCB0eXBlc19jbnQgPDwgc3RkOjplbmRsOwogICAgICAgIHN0ZDo6Y291dCA8PCAiXHRUeXBlcyBjb3VudD0iIDw8IHR5cGVzX2NudCA8PCBzdGQ6OmVuZGw7CiAgICAgICAgYm9vc3Q6Om1wbDo6Zm9yX2VhY2g8dHlwZW5hbWUgZGlzcGF0Y2hlcnNfdDx0eXBlc19jbnQ+Ojp0eXBlPih0ZXN0X2VsYXBzZWQoKSk7CiAgICAgICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKICAgIH0KfTsKCnRlbXBsYXRlPD4Kc3RydWN0IGRvX3Rlc3RzPDA+CnsKICAgIHN0YXRpYyB2b2lkIGYoKSB7fQp9OwoKLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQppbnQgbWFpbihpbnQgYXJnYyxjaGFyICoqYXJndikKewogICAgc3RkOjpjb3V0LnNldGYoc3RkOjppb3NfYmFzZTo6Zml4ZWQsIHN0ZDo6aW9zX2Jhc2U6OmZsb2F0ZmllbGQpOwogICAgLy9zdGQ6OmNvdXQucHJlY2lzaW9uKDMpOwogICAgZm9yKGludCBpPTA7aSE9T1VURVJfSVRFUlM7KytpKQogICAgewogICAgICAgIHN0ZDo6Y291dCA8PCAiST0iIDw8IGkgPDwgc3RkOjplbmRsOwogICAgICAgIGRvX3Rlc3RzPE1BWF9UWVBFU19DT1VOVD46OmYoKTsKICAgIH0KfQoK