// Author: Pete Kirkham
// string match benchmark - block io, wide character match algorithm.

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <sstream>
#include <stdint.h>

#define BLOCK_SIZE 80960

// naive string search
size_t string_search (const char* pattern, size_t pattern_length, const char* string, size_t string_length)
{
    const char      first_char(pattern[0]);
    const uint64_t  first_char_wide(0x0101010101010101LL * (uint64_t(first_char) & 0xffLL));
    const size_t    last_index(string_length - pattern_length);
    size_t          start_pad(size_t(string)&7);

    if (start_pad == 0) start_pad = 8;

    const char* aligned_string(string - start_pad);

    // sequential scan until we are aligned
    for (size_t index(start_pad); index < 8; ++index)
        if ((first_char == aligned_string[index]) && (strncmp(pattern, aligned_string + index, pattern_length) == 0))
            return index - start_pad;

    // scan 8 chars at a time for first char in pattern
    for (size_t index(8 - start_pad); index < last_index; index += 8)
    {
        uint64_t  data(*((uint64_t*)(string+index)));

        data = (~(data ^ first_char_wide));
        data = (data & (data << 4)) & 0xf0f0f0f0f0f0f0f0LL;
        data = (data & (data << 2)) & 0xc0c0c0c0c0c0c0c0LL;
        data = (data & (data << 1)) & 0x8080808080808080LL;

        if (data)
        {
            // this time we can have GGGG so need to loop over every char in the word
            for (size_t j(0); j < 8; ++j)
            {
                if ((first_char == string[index + j]) &&
                    (strncmp(pattern, string + index + j, pattern_length) == 0))
                    return index + j;
            }
        }
    }

    return string_length;
}

// process a line of input
inline void process_line (size_t& matches, const char* pattern, size_t pattern_length, const char* line, size_t line_length)
{
    // index of start of match
    //  all lines start with x.x.x.x - - [DD/MMM/YYY:HH:MM:SS -0700] "GET
    //  so we could start 34 chars into the line
    size_t match(string_search(pattern, pattern_length, line, line_length) + pattern_length);
    size_t index(match);

    if (index >= line_length) return;

    if (line[index] < '0' || line[index] > '9') return;
    ++index;
    if (line[index] < '0' || line[index] > '9') return;
    ++index;
    if (line[index] < '0' || line[index] > '9') return;
    ++index;
    if (line[index] != 'x') return;
    ++index;
    if (line[index] != '/') return;
    ++index;
    if (line[index] < '0' || line[index] > '9') return;
    ++index;
    if (line[index] < '0' || line[index] > '9') return;
    ++index;
    if (line[index] < '0' || line[index] > '9') return;
    ++index;
    if (line[index] < '0' || line[index] > '9') return;
    ++index;
    if (line[index] != '/') return;
    ++index;
    if (line[index] < '0' || line[index] > '9') return;
    ++index;
    if (line[index] < '0' || line[index] > '9') return;
    ++index;
    if (line[index] != '/') return;
    ++index;
    if (line[index] < '0' || line[index] > '9') return;
    ++index;
    if (line[index] < '0' || line[index] > '9') return;
    ++index;
    if (line[index] != '/') return;
    ++index;

    while (index < line_length)
    {
        char ch(line[index]);

        if ((ch == '.') || (ch == '\n'))
            break;

        if (ch == ' ')
        {
            if (index > match + 16)
            {
                ++matches;
#ifdef LIST_MATCHES
                std::cout << std::string(line + match + 5, index - (match + 5)) << std::endl;
#endif
            }
            break;
        }

        ++index;
    }
}

// main
int main (int narg, char** argvp)
{
    if (narg < 2)
    {
        std::cout << "The name of the input file is required." << std::endl;
        return 1;
    }

    // open the file
    int file(open(argvp[1], O_RDONLY));

    if (!file)
    {
        std::cout << "failed to open " << argvp[1] << std::endl;
        return 2;
    }

    // pattern to find
    const char* pattern("GET /ongoing/When/");
    size_t      pattern_length(strlen(pattern));

    // block IO
    // for splitting lines, we move any trailing part line to the start of
    // memory then read data into the area following it
    uint64_t    mem[BLOCK_SIZE/4]; // use wider type to ensure alignment
    char*       buf((char*)mem);
    ssize_t     bytes_read;
    size_t      bytes_carried(0);

    // count of matching lines
    size_t      matches(0);

    while ((bytes_read = read(file, buf + bytes_carried, BLOCK_SIZE)) > 0)
    {
        size_t chunk_length(bytes_carried + bytes_read);
        size_t line_start(0);

        // scan for line breaks, 8 chars at a time - on x64, you can do 16,
        // IIRC on G5 32, using machine specific SIMD instructions, but this is
        // designed for portability between 64 bit unix variants.
        for (size_t i(0); i < chunk_length; i += 8)
        {
            uint64_t data(*((uint64_t*)(buf+i)));

            data = (~(data ^ 0x0a0a0a0a0a0a0a0aLL));
            data = (data & (data << 4)) & 0xf0f0f0f0f0f0f0f0LL;
            data = (data & (data << 2)) & 0xc0c0c0c0c0c0c0c0LL;
            data = (data & (data << 1)) & 0x8080808080808080LL;

            if (data)
            {
//                std::cout << to_hex(data) << std::endl;

                // you can do without this scan - if you know machine endianess, then
                // one of the eight non-zero values of data will give the index
                for (; i < chunk_length; ++i)
                {
                    if (buf[i] == '\n')
                    {
                        size_t line_length(i - line_start);
                        const char* line(buf + line_start);

#ifdef ECHO_LINES
                        buf[i] = '\0';

                        std::cout << buf + line_start << std::endl;
#endif

                        process_line(matches, pattern, pattern_length, line, line_length);

                        line_start = i+1;

                        i &= ~7;

                        break; // assumes there are no lines < 8 characters
                    }
                }
            }
        }

        // copy trailing data to start of alternate block
        //  assumes that a line is never more than half a block long
        bytes_carried = chunk_length - line_start;

        memcpy(buf, buf + line_start, bytes_carried);
    }

    // if there is any last line, process that
    if (bytes_carried)
    {
        process_line(matches, pattern, pattern_length, buf, bytes_carried);
    }

    close(file);

    std::cout << "matches: " << matches << std::endl;

    return 0;
}