#ifndef __INT128_H_
#define __INT128_H_

#include <cctype>
#include <limits>
#include <sstream>
#include <stdexcept>

// NOTE: These 128 bit types are GCC specific; see:
// https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html
typedef __int128 int128_t;
typedef unsigned __int128 uint128_t;


std::ostream& operator<<(std::ostream& dest, uint128_t value)
{
    std::ostream::sentry check(dest);
    if (check) 
    {
        char buffer[128];
        char* pos = std::end(buffer);
        do
        {
            --pos;
            *pos = "0123456789"[value % 10];
            value /= 10;
        } while (value != 0);
        int len = std::end(buffer) - pos;
        if (dest.rdbuf()->sputn(pos, len) != len) 
        {
            dest.setstate(std::ios_base::badbit);
        }
    }
    return dest;
}

std::ostream& operator<<(std::ostream& dest, int128_t value)
{
    std::ostream::sentry check(dest);
    if (check) 
    {
        uint128_t tmp = value < 0 ? -value : value;
        char buffer[128];
        char* pos = std::end(buffer);
        do
        {
            --pos;
            *pos = "0123456789"[tmp % 10];
            tmp /= 10;
        } while (tmp != 0);
        if (value < 0) 
        {
            --pos;
            *pos = '-';
        }
        int len = std::end(buffer) - pos;
        if (dest.rdbuf()->sputn(pos, len) != len) 
        {
            dest.setstate(std::ios_base::badbit);
        }
    }
    return dest;
}

constexpr uint128_t max_tab[]
{
    std::numeric_limits<uint128_t>::max() /  2,
    std::numeric_limits<uint128_t>::max() /  3,
    std::numeric_limits<uint128_t>::max() /  4,
    std::numeric_limits<uint128_t>::max() /  5,
    std::numeric_limits<uint128_t>::max() /  6,
    std::numeric_limits<uint128_t>::max() /  7,
    std::numeric_limits<uint128_t>::max() /  8,
    std::numeric_limits<uint128_t>::max() /  9,
    std::numeric_limits<uint128_t>::max() / 10,
    std::numeric_limits<uint128_t>::max() / 11,
    std::numeric_limits<uint128_t>::max() / 12,
    std::numeric_limits<uint128_t>::max() / 13,
    std::numeric_limits<uint128_t>::max() / 14,
    std::numeric_limits<uint128_t>::max() / 15,
    std::numeric_limits<uint128_t>::max() / 16,
    std::numeric_limits<uint128_t>::max() / 17,
    std::numeric_limits<uint128_t>::max() / 18,
    std::numeric_limits<uint128_t>::max() / 19,
    std::numeric_limits<uint128_t>::max() / 20,
    std::numeric_limits<uint128_t>::max() / 21,
    std::numeric_limits<uint128_t>::max() / 22,
    std::numeric_limits<uint128_t>::max() / 23,
    std::numeric_limits<uint128_t>::max() / 24,
    std::numeric_limits<uint128_t>::max() / 25,
    std::numeric_limits<uint128_t>::max() / 26,
    std::numeric_limits<uint128_t>::max() / 27,
    std::numeric_limits<uint128_t>::max() / 28,
    std::numeric_limits<uint128_t>::max() / 29,
    std::numeric_limits<uint128_t>::max() / 31,
    std::numeric_limits<uint128_t>::max() / 32,
    std::numeric_limits<uint128_t>::max() / 33,
    std::numeric_limits<uint128_t>::max() / 34,
    std::numeric_limits<uint128_t>::max() / 35,
    std::numeric_limits<uint128_t>::max() / 36
};

constexpr uint32_t rem_tab[]
{
    std::numeric_limits<uint128_t>::max() %  2,
    std::numeric_limits<uint128_t>::max() %  3,
    std::numeric_limits<uint128_t>::max() %  4,
    std::numeric_limits<uint128_t>::max() %  5,
    std::numeric_limits<uint128_t>::max() %  6,
    std::numeric_limits<uint128_t>::max() %  7,
    std::numeric_limits<uint128_t>::max() %  8,
    std::numeric_limits<uint128_t>::max() %  9,
    std::numeric_limits<uint128_t>::max() % 10,
    std::numeric_limits<uint128_t>::max() % 11,
    std::numeric_limits<uint128_t>::max() % 12,
    std::numeric_limits<uint128_t>::max() % 13,
    std::numeric_limits<uint128_t>::max() % 14,
    std::numeric_limits<uint128_t>::max() % 15,
    std::numeric_limits<uint128_t>::max() % 16,
    std::numeric_limits<uint128_t>::max() % 17,
    std::numeric_limits<uint128_t>::max() % 18,
    std::numeric_limits<uint128_t>::max() % 19,
    std::numeric_limits<uint128_t>::max() % 20,
    std::numeric_limits<uint128_t>::max() % 21,
    std::numeric_limits<uint128_t>::max() % 22,
    std::numeric_limits<uint128_t>::max() % 23,
    std::numeric_limits<uint128_t>::max() % 24,
    std::numeric_limits<uint128_t>::max() % 25,
    std::numeric_limits<uint128_t>::max() % 26,
    std::numeric_limits<uint128_t>::max() % 27,
    std::numeric_limits<uint128_t>::max() % 28,
    std::numeric_limits<uint128_t>::max() % 29,
    std::numeric_limits<uint128_t>::max() % 31,
    std::numeric_limits<uint128_t>::max() % 32,
    std::numeric_limits<uint128_t>::max() % 33,
    std::numeric_limits<uint128_t>::max() % 34,
    std::numeric_limits<uint128_t>::max() % 35,
    std::numeric_limits<uint128_t>::max() % 36
};

int128_t strtoll_128(const char* nptr, char** endptr, int base)
{
    bool negative = false;
    uint128_t cutoff = 0;
    uint32_t cutlim = 0;
    int128_t value = 0;
    const char* ptr;
    unsigned char chr;
    const char *save, *end;
    bool overflow = false;

    // Validate the base parameter
    if (base < 0 || base == 1 || base > 36)
    {
        std::ostringstream msg;
        msg << "Base value \"" << base << "\" is invalid; base must be "
            << "between 2-36 (inclusive).";
        throw std::out_of_range(msg.str());
    }
    
    save = ptr = nptr;
    
    // Skip any leading whitespace
    while (std::isspace(*ptr))
    {
        ++ptr;
    }
    
    // Check for end of string
    if (__builtin_expect((*ptr == '\0'), 0))
    {
        goto noconv;
    }
    
    // Parse -/+
    if (*ptr == '-')
    {
        negative = true;
        ++ptr;
    }
    else if (*ptr == '+')
    {
        ++ptr;
    }
    
    // Auto detect/validate base
    if (*ptr == '0')
    {
        if ((base == 0 || base == 16) && std::toupper(ptr[1])== 'X')
        {
            ptr += 2;
            base = 16;
        }
        else if (base == 0)
        {
            base = 8;
        }
    }
    else if (base == 0)
    {
        base = 10;
    }
    
    // Save start of digits
    save = ptr;
    end = nullptr;
    
    cutoff = max_tab[base - 2];;
    cutlim = rem_tab[base - 2];
    
    // Iterate over the characters
    chr = *ptr;
    for (; chr != '\0'; chr = *++ptr)
    {
        if (ptr == end)
        {
            break;
        }
        
        if (chr >= '0' && chr <= '9')
        {
            chr -= '0';
        }
        else if (std::isalpha(chr))
        {
            chr = std::toupper(chr) - 'A' + 10;
        }
        else
        {
            break;
        }
        
        if (static_cast<int>(chr) >= base)
        {
            break;
        }

        if (value > cutoff || (value == cutoff && chr > cutlim))
        {
            overflow = true;
            break;
        }
        else
        {   
            value *= static_cast<uint128_t>(base);
            value += (int)chr;
        }
    }
    
    // Check if no conversion was done
    if (ptr == save)
    {
        goto noconv;
    }
    
    // Store end if requested
    if (endptr != nullptr)
    {
        *endptr = const_cast<char*>(ptr);
    }
        
    // Check for overflow
    if (__builtin_expect((overflow), 0))
    {
        std::ostringstream msg;
        msg << "Overflow detected at input offset " << (ptr - nptr);
        throw std::overflow_error(msg.str());
    }
    
    // Regular return path
    return negative ? -value : value;
    
noconv:

    if (endptr != nullptr)
    {
        if (save - nptr >= 2 && std::toupper(save[-1]) == 'X' && save[-2] == '0')
        {
            *endptr = const_cast<char*>(&save[-1]);
        }
        else
        {
            *endptr = const_cast<char*>(nptr);
        }
    }

    return 0;
}


uint128_t strtoull_128(const char* nptr, char** endptr, int base)
{
    uint128_t cutoff = 0;
    uint32_t cutlim = 0;
    uint128_t value = 0;
    const char* ptr;
    unsigned char chr;
    const char *save, *end;
    bool overflow = false;

    // Validate the base parameter
    if (base < 0 || base == 1 || base > 36)
    {
        std::ostringstream msg;
        msg << "Base value \"" << base << "\" is invalid; base must be "
            << "between 2-36 (inclusive).";
        throw std::out_of_range(msg.str());
    }
    
    save = ptr = nptr;
    
    // Skip any leading whitespace
    while (std::isspace(*ptr))
    {
        ++ptr;
    }
    
    // Check for end of string
    if (__builtin_expect((*ptr == '\0'), 0))
    {
        goto noconv;
    }
    
    // Parse -/+
    if (*ptr == '-' || *ptr == '+')
    {
        ++ptr;
    }
    
    // Auto detect/validate base
    if (*ptr == '0')
    {
        if ((base == 0 || base == 16) && std::toupper(ptr[1])== 'X')
        {
            ptr += 2;
            base = 16;
        }
        else if (base == 0)
        {
            base = 8;
        }
    }
    else if (base == 0)
    {
        base = 10;
    }
    
    // Save start of digits
    save = ptr;
    end = nullptr;
    
    cutoff = max_tab[base - 2];;
    cutlim = rem_tab[base - 2];
    
    // Iterate over the characters
    chr = *ptr;
    for (; chr != '\0'; chr = *++ptr)
    {
        if (ptr == end)
        {
            break;
        }
        
        if (chr >= '0' && chr <= '9')
        {
            chr -= '0';
        }
        else if (std::isalpha(chr))
        {
            chr = std::toupper(chr) - 'A' + 10;
        }
        else
        {
            break;
        }
        
        if (static_cast<int>(chr) >= base)
        {
            break;
        }

        if (value > cutoff || (value == cutoff && chr > cutlim))
        {
            overflow = true;
            break;
        }
        else
        {   
            value *= static_cast<uint128_t>(base);
            value += (int)chr;
        }
    }
    
    // Check if no conversion was done
    if (ptr == save)
    {
        goto noconv;
    }
    
    // Store end if requested
    if (endptr != nullptr)
    {
        *endptr = const_cast<char*>(ptr);
    }
        
    // Check for overflow
    if (__builtin_expect((overflow), 0))
    {
        std::ostringstream msg;
        msg << "Overflow detected at input offset " << (ptr - nptr);
        throw std::overflow_error(msg.str());
    }
    
    // Regular return path
    return value;
    
noconv:

    if (endptr != nullptr)
    {
        if (save - nptr >= 2 && std::toupper(save[-1]) == 'X' && save[-2] == '0')
        {
            *endptr = const_cast<char*>(&save[-1]);
        }
        else
        {
            *endptr = const_cast<char*>(nptr);
        }
    }

    return 0;
}


int128_t strtoll_128_b10opt(const char* nptr, char** endptr, int base=10)
{
    bool negative = false;
    uint128_t cutoff = 0;
    uint32_t cutlim = 0;
    int128_t value = 0;
    const char* ptr;
    unsigned char chr;
    const char *save, *end;
    bool overflow = false;

    // Validate the base parameter
#if 0
    if (base < 0 || base == 1 || base > 36)
    {
        std::ostringstream msg;
        msg << "Base value \"" << base << "\" is invalid; base must be "
            << "between 2-36 (inclusive).";
        throw std::out_of_range(msg.str());
    }
#endif
    
    save = ptr = nptr;
    
    // Skip any leading whitespace
    while (std::isspace(*ptr))
    {
        ++ptr;
    }
    
    // Check for end of string
    if (__builtin_expect((*ptr == '\0'), 0))
    {
        goto noconv;
    }
    
    // Parse -/+
    if (*ptr == '-')
    {
        negative = true;
        ++ptr;
    }
    else if (*ptr == '+')
    {
        ++ptr;
    }
    
    // Save start of digits
    save = ptr;
    end = nullptr;
    
    cutoff = max_tab[8];    // base 10
    cutlim = rem_tab[8];
    
    // Iterate over the characters
    chr = *ptr;
    for (; chr != '\0'; chr = *++ptr)
    {
        if (ptr == end)
        {
            break;
        }
        
        if (chr >= '0' && chr <= '9')
        {
            chr -= '0';
        }
        else
        {
            break;
        }

        if (value > cutoff || (value == cutoff && chr > cutlim))
        {
            overflow = true;
            break;
        }
        else
        {   
            value *= static_cast<uint128_t>(10);
            value += (int)chr;
        }
    }
    
    // Check if no conversion was done
    if (ptr == save)
    {
        goto noconv;
    }
    
    // Store end if requested
    if (endptr != nullptr)
    {
        *endptr = const_cast<char*>(ptr);
    }
        
    // Check for overflow
    if (__builtin_expect((overflow), 0))
    {
        std::ostringstream msg;
        msg << "Overflow detected at input offset " << (ptr - nptr);
        throw std::overflow_error(msg.str());
    }
    
    // Regular return path
    return negative ? -value : value;
    
noconv:

    if (endptr != nullptr)
    {
        *endptr = const_cast<char*>(nptr);
    }

    return 0;
}


uint128_t strtoull_128_b10opt(const char* nptr, char** endptr, int base=10)
{
    uint128_t cutoff = 0;
    uint32_t cutlim = 0;
    uint128_t value = 0;
    const char* ptr;
    unsigned char chr;
    const char *save, *end;
    bool overflow = false;

    // Validate the base parameter
#if 0
    if (base < 0 || base == 1 || base > 36)
    {
        std::ostringstream msg;
        msg << "Base value \"" << base << "\" is invalid; base must be "
            << "between 2-36 (inclusive).";
        throw std::out_of_range(msg.str());
    }
#endif
    
    save = ptr = nptr;
    
    // Skip any leading whitespace
    while (std::isspace(*ptr))
    {
        ++ptr;
    }
    
    // Check for end of string
    if (__builtin_expect((*ptr == '\0'), 0))
    {
        goto noconv;
    }
    
    // Parse -/+
    if (*ptr == '-' || *ptr == '+')
    {
        ++ptr;
    }
    
    // Save start of digits
    save = ptr;
    end = nullptr;
    
    cutoff = max_tab[8];    // base 10
    cutlim = rem_tab[8];
    
    // Iterate over the characters
    chr = *ptr;
    for (; chr != '\0'; chr = *++ptr)
    {
        if (ptr == end)
        {
            break;
        }
        
        if (chr >= '0' && chr <= '9')
        {
            chr -= '0';
        }
        else
        {
            break;
        }
        
        if (value > cutoff || (value == cutoff && chr > cutlim))
        {
            overflow = true;
            break;
        }
        else
        {   
            value *= static_cast<uint128_t>(10);
            value += (int)chr;
        }
    }
    
    // Check if no conversion was done
    if (ptr == save)
    {
        goto noconv;
    }
    
    // Store end if requested
    if (endptr != nullptr)
    {
        *endptr = const_cast<char*>(ptr);
    }
        
    // Check for overflow
    if (__builtin_expect((overflow), 0))
    {
        std::ostringstream msg;
        msg << "Overflow detected at input offset " << (ptr - nptr);
        throw std::overflow_error(msg.str());
    }
    
    // Regular return path
    return value;
    
noconv:

    if (endptr != nullptr)
    {
        *endptr = const_cast<char*>(nptr);
    }

    return 0;
}

#endif