memmemtest.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cassert>
#include <cstring>
#include <vector>
#include <chrono>
#include "muslmemmem.h"

static double monotonicSeconds()
{
    const auto now = std::chrono::steady_clock::now();
    const auto usec = std::chrono::time_point_cast<std::chrono::microseconds>(now);
    return usec.time_since_epoch().count() / 1'000'000.0;
}

static const void * mymemmem1(const void * h, size_t hs, const void * n, size_t ns)
{
    if(ns == 0u)
        return h;

    while(ns <= hs)
    {
        if(0 == std::memcmp(h, n, ns))
            return h;

        --hs;
        h = static_cast<const char*>(h) + 1;
    }//while

    return 0x0;
}

static const void * mymemmem2(const void * h, size_t hs, const void * n, size_t ns)
{
    if(ns == 0u)
        return h;

    const unsigned char * hh = static_cast<const unsigned char*>(h);
    const unsigned char firstbyte = *static_cast<const unsigned char*>(n);
    while(ns <= hs)
    {
        if(*hh == firstbyte && 0 == std::memcmp(hh, n, ns))
            return hh;

        --hs;
        ++hh;
    }//while

    return 0x0;
}

static bool samewithbit5set(const void * a, const void * b, size_t c)
{
    const unsigned char * aa = static_cast<const unsigned char*>(a);
    const unsigned char * bb = static_cast<const unsigned char*>(b);
    while(c)
    {
        if((32 | *aa) != (32 | *bb))
            return false;

        ++aa;
        ++bb;
        --c;
    }//while

    return true;
}

static unsigned char lower(unsigned char c)
{
    if('A' <= c && c <= 'Z')
        return c | 32;

    return c;
}

static bool sameasciilowercase(const void * a, const void * b, size_t c)
{
    const unsigned char * aa = static_cast<const unsigned char*>(a);
    const unsigned char * bb = static_cast<const unsigned char*>(b);
    while(c)
    {
        if(lower(*aa) != lower(*bb))
            return false;

        ++aa;
        ++bb;
        --c;
    }//while

    return true;
}

static const void * mymemmem3nocase1(const void * h, size_t hs, const void * n, size_t ns)
{
    if(ns == 0u)
        return h;

    const unsigned char * hh = static_cast<const unsigned char*>(h);
    const unsigned char firstbyte = 32 | *static_cast<const unsigned char*>(n);
    while(ns <= hs)
    {
        if((32 | *hh) == firstbyte && sameasciilowercase(hh, n, ns))
            return hh;

        --hs;
        ++hh;
    }//while

    return 0x0;
}

static const void * mymemmem3nocase2(const void * h, size_t hs, const void * n, size_t ns)
{
    if(ns == 0u)
        return h;

    const unsigned char * hh = static_cast<const unsigned char*>(h);
    const unsigned char firstbyte = lower(*static_cast<const unsigned char*>(n));
    while(ns <= hs)
    {
        if(lower(*hh) == firstbyte && sameasciilowercase(hh, n, ns))
            return hh;

        --hs;
        ++hh;
    }//while

    return 0x0;
}

typedef const void*(*MemmemFunc)(const void *, size_t, const void*, size_t);

static int test(const char * s, MemmemFunc f, const void * h, size_t hs, const void * n, size_t ns)
{
    const double a = monotonicSeconds();
    const void * ret = f(h, hs, n, ns);
    const double b = monotonicSeconds();
    const double mib = static_cast<double>(hs) / ((b - a) * 1024.0 * 1024.0);
    printf("%21s: %f MiB/s\n", s, mib);
    assert(ret != 0x0);
    return !!ret;
}

int main()
{
    size_t hs = 1024 * 1024 * 1024;
    void * h = std::malloc(hs);
    std::memset(h, 0x0, hs);
    const std::string nn = "needleneedleneedle";
    std::strcpy(static_cast<char*>(h) + hs - nn.size(), nn.c_str());

    //lots of partial matches
    for(int i = 1; i < 9999; ++i)
    {
        std::string nn2 = nn;
        nn2.pop_back();
        std::strcpy(static_cast<char*>(h) + i * 1024, nn2.c_str());
    }//for

    int ret = 0;

    ret += test("mymemmem1", mymemmem1, h, hs, nn.c_str(), nn.size());
    ret += test("mymemmem2", mymemmem2, h, hs, nn.c_str(), nn.size());
    ret += test("muslmemmem", muslmemmem, h, hs, nn.c_str(), nn.size());
    ret += test("mymemmem3nocase1", mymemmem3nocase1, h, hs, nn.c_str(), nn.size());
    ret += test("mymemmem3nocase2", mymemmem3nocase2, h, hs, nn.c_str(), nn.size());

    return ret;
}