#include <cctype>
#include <chrono>
#include <cstdint>
#include <fstream>
#include <ios>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

#include <sys/types.h>
#include <sys/stat.h>

#include <x86intrin.h>

// https://stackoverflow.com/questions/3883993/how-could-these-case-conversion-functions-be-improved
inline void SIMD_128_tolower(char* inputData, uint64_t length)
{
    const __m128i data_65   = _mm_set1_epi8(65); // 'A'
    const __m128i data_26   = _mm_set1_epi8(26);
    const __m128i data_32   = _mm_set1_epi8(32);
    const __m128i clear_msb = _mm_set1_epi8(0x7F);
    
    char *dataPtr = inputData;
    char *dataStop = inputData + length;
    
    while (dataPtr < dataStop)
    {
        // Load data
        __m128i data = _mm_lddqu_si128(reinterpret_cast<__m128i *>(dataPtr));

        // Load copy of data into working register
        __m128i work_reg = _mm_lddqu_si128(&data);
        
        // Subtract 'A' from working register
        work_reg = _mm_sub_epi8(work_reg, data_65);
            
        // AND together packed "clear MSB" to simulate the cast to unsigned
        work_reg = _mm_and_si128(work_reg, clear_msb);
        
        // Compare work register less than 26 and store in work register
        work_reg = _mm_cmplt_epi8(work_reg, data_26);
        
        // AND together packed 32 data and work regiser
        work_reg = _mm_and_si128(work_reg, data_32);
        
        // Accumulate with work register
        data = _mm_add_epi8(data, work_reg);
        
        // Store converted values back to array
        _mm_storeu_si128(reinterpret_cast<__m128i *>(dataPtr), data);
        
        // Advance data pointer
        dataPtr += 16;
    }
}

inline void SIMD_256_tolower(char* inputData, uint64_t length)
{
    const __m256i data_65   = _mm256_set1_epi8(65); // 'A'
    const __m256i data_26   = _mm256_set1_epi8(26);
    const __m256i data_32   = _mm256_set1_epi8(32);
    const __m256i clear_msb = _mm256_set1_epi8(0x7F);
    
    char *dataPtr = inputData;
    char *dataStop = inputData + length;
    
    while (dataPtr < dataStop)
    {
        // Load data
        __m256i data = _mm256_lddqu_si256(reinterpret_cast<__m256i *>(dataPtr));
        
        // Load copy of data into working register
        __m256i work_reg = _mm256_lddqu_si256(&data);
        
        // Subtract 'A' from working register
        work_reg = _mm256_sub_epi8(work_reg, data_65);
            
        // AND together packed "clear MSB" to simulate the cast to unsigned
        work_reg = _mm256_and_si256(work_reg, clear_msb);
        
        // Compare 26 greater than work registerand store in work register
        // NOTE: AVX2 does not have cmplt intrinsic so compare is inverted
        work_reg = _mm256_cmpgt_epi8(data_26, work_reg);
        
        // AND together packed 32 data and work regiser
        work_reg = _mm256_and_si256(work_reg, data_32);
        
        // Accumulate with work register
        data = _mm256_add_epi8(data, work_reg);
        
        // Store converted values back to array
        _mm256_storeu_si256(reinterpret_cast<__m256i *>(dataPtr), data);
        
        // Advance data pointer
        dataPtr += 32;
    }
}

inline uint64_t align16(uint64_t size)
{
    return (size & 0xF) ? ((size + 0x10) & ~(0xF)) : size;
}

inline uint64_t align32(uint64_t size)
{
    return (size & 0x1F) ? ((size + 0x20) & ~(0x1F)) : size;
}

inline double speedup(double old, double new_)
{
    return (((old / new_) - 1) * 100);
}


// g++ -std=c++11 -O3 -msse2 lowercase_util.cc -o lowercase_util
int main(const int argc, char** argv)
{
    if (argc < 2)
    {
        std::cerr << "USAGE: " << argv[0] << " <filename>" << std::endl;
        return -1;
    }
    std::cout << "Lowercase Test Util\n" << std::endl;
    
    
    std::string filePath(argv[1]);

    // Stat the file path to get its size
    struct stat fs_stat;
    const int gotStatOK(stat(filePath.c_str(), &fs_stat));
    if (gotStatOK < 0)
    {
        perror("stat()");
        return -1;
    }

    uint64_t fileSize = fs_stat.st_size;
    std::cout << "File size: " << fileSize << "\n" << std::endl;
    
    // Read in file
    std::ifstream inFileStream(filePath, std::ios::in | std::ios::binary);
    if (! inFileStream)
    {
        std::cerr << "Unable to open specified file." << std::endl;
        return -1;
    }
    
    // Read file in then close stream
    std::vector<char> contents;
    contents.resize(fileSize);
    inFileStream.read(contents.data(), fileSize);
    inFileStream.close();
    
    // TEST1: regular standard library tolower() ------------------------------
    std::vector<char> copy1(contents);
    
    auto start = std::chrono::system_clock::now();
    
    for (uint32_t idx = 0; idx < fileSize; ++idx)
    {
        copy1[idx] = tolower(copy1[idx]);
    }
    
    auto end = std::chrono::system_clock::now();
    auto diff = end - start;
    double test1_duration = std::chrono::duration<double, std::milli>(diff).count();
    
    std::cout << "Test 1: STD lib tolower()                -- duration: " 
              << std::setw(10) << std::fixed << std::setprecision(3) << test1_duration 
              << " ms -- " << std::fixed << std::setprecision(2) << std::setw(7)
              << speedup(test1_duration, test1_duration) << "%" << std::endl;
    


    // TEST2: bit twiddle with comparison -------------------------------------
    std::vector<char> copy2(contents);
    
    start = std::chrono::system_clock::now();
    
    for (uint32_t idx = 0; idx < fileSize; ++idx)
    {
        // *c += (*c - 'A' < 26U) << 5;
        copy2[idx] += (copy2[idx] - 'A' < 26U) << 5;
    }
    
    end = std::chrono::system_clock::now();
    diff = end - start;
    double test2_duration = std::chrono::duration<double, std::milli>(diff).count();
    
    std::cout << "Test 2: bit twiddle with comparison      -- duration: " 
              << std::setw(10) << std::fixed << std::setprecision(3) << test2_duration
              << " ms -- " << std::fixed << std::setprecision(2) << std::setw(7)
              << speedup(test1_duration, test2_duration) << "%" << std::endl;
    
    #if 0
    // Verify copy2
    std::ofstream outStream1("output_copy2.txt", std::ios::out | std::ios::binary);
    outStream1.write(copy2.data(), fileSize);
    outStream1.close();
    #endif
    
   
   
    // TEST3: bit twiddle with no comparison ----------------------------------
    std::vector<char> copy3(contents);
    
    start = std::chrono::system_clock::now();
    
    for (uint32_t idx = 0; idx < fileSize; ++idx)
    {
        // *c += (64U - *c & *c - 91U) >> CHAR_BIT * sizeof(unsigned) - 1 << 5;
        // *c += ((64U - *c & *c - 91U) >> 31) << 5;
        copy3[idx] += ((64U - copy3[idx] & copy3[idx] - 91U) >> 31) << 5;
    }
    
    end = std::chrono::system_clock::now();
    diff = end - start;
    double test3_duration = std::chrono::duration<double, std::milli>(diff).count();
    
    std::cout << "Test 3: bit twiddle w/ no comparison     -- duration: " 
              << std::setw(10) << std::fixed << std::setprecision(3) << test3_duration
              << " ms -- " << std::fixed << std::setprecision(2) << std::setw(7)
              << speedup(test1_duration, test3_duration) << "%" << std::endl;
    
    
    
    // TEST 4: alternate bit twiddle with no comparison -----------------------
    std::vector<char> copy4(contents);
    
    start = std::chrono::system_clock::now();
    
    for (uint32_t idx = 0; idx < fileSize; ++idx)
    {
        // c += (((96-(int)c)&((int)c-123))>>9)&(-32);
        copy4[idx] += (((96 - (int)copy4[idx]) & ((int)copy4[idx] - 123)) >> 9) & (-32);
    }
    
    end = std::chrono::system_clock::now();
    diff = end - start;
    double test4_duration = std::chrono::duration<double, std::milli>(diff).count();
    
    std::cout << "Test 4: bit twiddle w/ no comp alt       -- duration: " 
              << std::setw(10) << std::fixed << std::setprecision(3) << test4_duration
              << " ms -- " << std::fixed << std::setprecision(2) << std::setw(7)
              << speedup(test1_duration, test4_duration) << "%" << std::endl;

    
    
    // TEST 5: optimized SIMD (16 bytes at a time) ----------------------------
    std::vector<char> copy5(contents);
    // NOTE: data buffer size MUST be 16 byte aligned
    copy5.reserve(align16(fileSize));
    
    start = std::chrono::system_clock::now();
    
    SIMD_128_tolower(copy5.data(), fileSize);
    
    end = std::chrono::system_clock::now();
    diff = end - start;
    double test5_duration = std::chrono::duration<double, std::milli>(diff).count();
    
    std::cout << "Test 5: optimized SIMD 128 bit (16 byte) -- duration: " 
              << std::setw(10) << std::fixed << std::setprecision(3) << test5_duration
              << " ms -- " << std::fixed << std::setprecision(2) << std::setw(7)
              << speedup(test1_duration, test5_duration) << "%" << std::endl;
    
    
    
    // TEST 6: optimized SIMD (32 bytes at a time) ----------------------------
    std::vector<char> copy6(contents);
    // NOTE: data buffer size MUST be 32 byte aligned
    copy6.reserve(align32(fileSize));
    
    start = std::chrono::system_clock::now();
    
    SIMD_256_tolower(copy6.data(), fileSize);
    
    end = std::chrono::system_clock::now();
    diff = end - start;
    double test6_duration = std::chrono::duration<double, std::milli>(diff).count();
    
    std::cout << "Test 6: optimized SIMD 256 bit (32 byte) -- duration: " 
              << std::setw(10) << std::fixed << std::setprecision(3) << test6_duration
              << " ms -- " << std::fixed << std::setprecision(2) << std::setw(7)
              << speedup(test1_duration, test6_duration) << "%" << std::endl;

    
    return 0;
}