// Copyright (C) 2026 Kiyotsugu Arai
// SPDX-License-Identifier: LGPL-3.0-or-later

// UInt128.hpp
// 128ビット符号なし整数型の定義
//
// このファイルでは、basic_types.hppから分離された128ビット符号なし整数型を提供します。

#ifndef CALX_UINT128_HPP
#define CALX_UINT128_HPP

#include <cstdint>
#include <utility>
#include <stdexcept>
#include <bit>
#include <math/core/mp/Int/compiler_intrinsics.hpp>

namespace calx {

    /**
     * @brief 128ビット符号なし整数型（コンパイラ非依存）
     *
     * この構造体は、どのコンパイラでも使用できる128ビット符号なし整数型を提供します。
     * GCCやClangの__uint128_tの代替として使用できます。
     */
    struct UInt128 {
        uint64_t low;   ///< 下位64ビット
        uint64_t high;  ///< 上位64ビット

        UInt128() : low(0), high(0) {}
        UInt128(uint64_t l) : low(l), high(0) {}
        UInt128(uint64_t h, uint64_t l) : low(l), high(h) {}

        /**
         * @brief 上位64ビットからUInt128を構築
         * @param high 上位64ビット値
         * @return 構築されたUInt128値
         */
        static UInt128 shift64(uint64_t high) {
            return UInt128(high, 0);
        }

        /**
         * @brief 加算
         * @param other 加算する値
         * @return 加算結果への参照
         */
        UInt128& operator+=(const UInt128& other) {
            uint64_t old_low = low;
            low += other.low;
            // キャリー計算：加算後の値が加算前より小さい場合はキャリーが発生
            high += other.high + (low < old_low ? 1 : 0);
            return *this;
        }

        /**
         * @brief uint64_t値との加算
         * @param value 加算する値
         * @return 加算結果への参照
         */
        UInt128& operator+=(uint64_t value) {
            uint64_t old_low = low;
            low += value;
            // キャリー計算：加算後の値が加算前より小さい場合はキャリーが発生
            if (low < old_low) {
                high++;
            }
            return *this;
        }

        /**
         * @brief 減算
         * @param other 減算する値
         * @return 減算結果への参照
         */
        UInt128& operator-=(const UInt128& other) {
            uint64_t old_low = low;
            low -= other.low;
            // ボロー計算：減算後の値が減算前より大きい場合はボローが発生
            high -= other.high + (low > old_low ? 1 : 0);
            return *this;
        }

        /**
         * @brief uint64_t値との減算
         * @param value 減算する値
         * @return 減算結果への参照
         */
        UInt128& operator-=(uint64_t value) {
            uint64_t old_low = low;
            low -= value;
            // ボロー計算：減算後の値が減算前より大きい場合はボローが発生
            if (low > old_low) {
                high--;
            }
            return *this;
        }

        /**
         * @brief 2つの64ビット整数の乗算
         * @param a 1つ目のオペランド
         * @param b 2つ目のオペランド
         * @return a * bの128ビット結果
         */
        /**
         * @brief 64bit × 64bit → 128bit 乗算
         *
         * MSVC: _umul128 intrinsic を使用（1命令）
         * GCC/Clang: __uint128_t または __builtin_umul_overflow を使用
         * Fallback: 32bitワードに分割して計算（従来実装）
         */
        static UInt128 multiply(uint64_t a, uint64_t b) {
#ifdef _MSC_VER
            // MSVC: _umul128 intrinsic を使用
            uint64_t high;
            uint64_t low = _umul128(a, b, &high);
            return UInt128(high, low);
#elif defined(__SIZEOF_INT128__)
            // GCC/Clang: __uint128_t を使用
            __uint128_t result = static_cast<__uint128_t>(a) * static_cast<__uint128_t>(b);
            return UInt128(static_cast<uint64_t>(result >> 64), static_cast<uint64_t>(result));
#else
            // Fallback: ソフトウェア実装（32bitワードに分割）
            constexpr uint64_t MASK32 = 0xFFFFFFFF;

            uint64_t a_low = a & MASK32;
            uint64_t a_high = a >> 32;
            uint64_t b_low = b & MASK32;
            uint64_t b_high = b >> 32;

            uint64_t ll = a_low * b_low;
            uint64_t lh = a_low * b_high;
            uint64_t hl = a_high * b_low;
            uint64_t hh = a_high * b_high;

            // mid = ll>>32 + (lh & MASK32) + (hl & MASK32)
            uint64_t mid = (ll >> 32) + (lh & MASK32) + (hl & MASK32);
            uint64_t low = (ll & MASK32) | (mid << 32);

            // 桁上がりを含めた high の構築
            uint64_t high = hh + (lh >> 32) + (hl >> 32) + (mid >> 32);

            return UInt128(high, low);
#endif
        }

        /**
         * @brief 除算（128ビット ÷ 64ビット）
         * @param dividend 被除数
         * @param divisor 除数
         * @return 商と余りのペア
         */
        static std::pair<uint64_t, uint64_t> divide(const UInt128& dividend, uint64_t divisor) {
            // divisorが0の場合は例外
            if (divisor == 0) {
                throw std::invalid_argument("Division by zero");
            }

            // dividendの上位ワードがdivisor以上の場合はオーバーフロー
            if (dividend.high >= divisor) {
                throw std::overflow_error("Division overflow");
            }

            // 通常の除算処理
            uint64_t q = 0;
            uint64_t r = 0;

            // 上位桁から処理
            for (int i = 63; i >= 0; --i) {
                // 余りを左シフト
                r = (r << 1) | ((dividend.high >> i) & 1);

                // 商の計算
                if (r >= divisor) {
                    r -= divisor;
                    q |= (1ULL << i);
                }
            }

            // 下位桁の処理
            for (int i = 63; i >= 0; --i) {
                // 余りを左シフト
                r = (r << 1) | ((dividend.low >> i) & 1);

                // 商の計算
                if (r >= divisor) {
                    r -= divisor;
                    q |= (1ULL << i);
                }
            }

            return std::make_pair(q, r); // 商と余り
        }

        /**
         * @brief 128ビット ÷ 64ビット = 商（64ビット）と余り（64ビット）の高速アルゴリズム
         *
         * MSVC: _udiv128 intrinsic を使用（1命令）
         * GCC/Clang: __uint128_t または手動実装
         * Fallback: ビット単位試し引き（従来実装）
         *
         * @param high 被除数の上位64ビット
         * @param low 被除数の下位64ビット
         * @param divisor 除数
         * @return 商と余りのペア
         */
        static std::pair<uint64_t, uint64_t> divmod_fast(uint64_t high, uint64_t low, uint64_t divisor) {
            // divisorが0の場合は例外
            if (divisor == 0) {
                throw std::invalid_argument("Division by zero");
            }

            // highがdivisor以上の場合はオーバーフロー
            if (high >= divisor) {
                throw std::overflow_error("Division overflow");
            }

#if defined(_MSC_VER) && defined(_M_X64)
            // MSVC x64: _udiv128 intrinsic を使用
            uint64_t remainder;
            uint64_t quotient = _udiv128(high, low, divisor, &remainder);
            return std::make_pair(quotient, remainder);
#elif defined(__SIZEOF_INT128__)
            // GCC/Clang: __uint128_t を使用
            __uint128_t dividend = (static_cast<__uint128_t>(high) << 64) | low;
            uint64_t quotient = static_cast<uint64_t>(dividend / divisor);
            uint64_t remainder = static_cast<uint64_t>(dividend % divisor);
            return std::make_pair(quotient, remainder);
#else
            // Fallback: ビット単位試し引き（ソフトウェア実装）
            uint64_t quotient = 0;
            uint64_t remainder = high;

            // 上位64ビットの処理
            for (int i = 0; i < 64; ++i) {
                // remainder の MSB がセットされている場合、左シフトでオーバーフローする。
                // その場合、シフト後の真値は 2^64 以上なので必ず divisor 以上。
                bool overflow = (remainder >> 63) & 1;

                // 余りを左シフトし、lowの最上位ビットを取り込む
                remainder = (remainder << 1) | ((low >> 63) & 1);
                low <<= 1;

                // 商のビットを計算
                quotient <<= 1;
                if (overflow || remainder >= divisor) {
                    remainder -= divisor;
                    quotient |= 1;
                }
            }

            return std::make_pair(quotient, remainder);
#endif
        }

        /**
         * @brief 比較（等値）
         * @param other 比較対象
         * @return 等しければtrue
         */
        bool operator==(const UInt128& other) const {
            return low == other.low && high == other.high;
        }

        /**
         * @brief 比較（不等）
         * @param other 比較対象
         * @return 等しくなければtrue
         */
        bool operator!=(const UInt128& other) const {
            return !(*this == other);
        }

        /**
         * @brief 比較（大小）
         * @param other 比較対象
         * @return 大きければtrue
         */
        bool operator>(const UInt128& other) const {
            return high > other.high || (high == other.high && low > other.low);
        }

        /**
         * @brief 比較（大小）
         * @param other 比較対象
         * @return 小さければtrue
         */
        bool operator<(const UInt128& other) const {
            return high < other.high || (high == other.high && low < other.low);
        }

        /**
         * @brief 比較（以上）
         * @param other 比較対象
         * @return 以上であればtrue
         */
        bool operator>=(const UInt128& other) const {
            return !(*this < other);
        }

        /**
         * @brief 比較（以下）
         * @param other 比較対象
         * @return 以下であればtrue
         */
        bool operator<=(const UInt128& other) const {
            return !(*this > other);
        }

        /**
         * @brief uint64_tとの比較（等値）
         * @param value 比較対象
         * @return 等しければtrue
         */
        bool operator==(uint64_t value) const {
            return high == 0 && low == value;
        }

        /**
         * @brief uint64_tとの比較（不等）
         * @param value 比較対象
         * @return 等しくなければtrue
         */
        bool operator!=(uint64_t value) const {
            return !(*this == value);
        }

        /**
         * @brief uint64_tとの比較（大小）
         * @param value 比較対象
         * @return 大きければtrue
         */
        bool operator>(uint64_t value) const {
            return high > 0 || low > value;
        }

        /**
         * @brief uint64_tとの比較（大小）
         * @param value 比較対象
         * @return 小さければtrue
         */
        bool operator<(uint64_t value) const {
            return high == 0 && low < value;
        }

        /**
         * @brief uint64_tとの比較（以上）
         * @param value 比較対象
         * @return 以上であればtrue
         */
        bool operator>=(uint64_t value) const {
            return !(*this < value);
        }

        /**
         * @brief uint64_tとの比較（以下）
         * @param value 比較対象
         * @return 以下であればtrue
         */
        bool operator<=(uint64_t value) const {
            return !(*this > value);
        }
    };

    // 非メンバー演算子オーバーロード

    /**
     * @brief 加算
     * @param lhs 左辺値
     * @param rhs 右辺値
     * @return 加算結果
     */
    inline UInt128 operator+(const UInt128& lhs, const UInt128& rhs) {
        UInt128 result = lhs;
        result += rhs;
        return result;
    }

    /**
     * @brief UInt128とuint64_tの加算
     * @param lhs 左辺値
     * @param rhs 右辺値
     * @return 加算結果
     */
    inline UInt128 operator+(const UInt128& lhs, uint64_t rhs) {
        UInt128 result = lhs;
        result += rhs;
        return result;
    }

    /**
     * @brief uint64_tとUInt128の加算
     * @param lhs 左辺値
     * @param rhs 右辺値
     * @return 加算結果
     */
    inline UInt128 operator+(uint64_t lhs, const UInt128& rhs) {
        UInt128 result(0, lhs);
        result += rhs;
        return result;
    }

    /**
     * @brief 減算
     * @param lhs 左辺値
     * @param rhs 右辺値
     * @return 減算結果
     */
    inline UInt128 operator-(const UInt128& lhs, const UInt128& rhs) {
        UInt128 result = lhs;
        result -= rhs;
        return result;
    }

    /**
     * @brief UInt128とuint64_tの減算
     * @param lhs 左辺値
     * @param rhs 右辺値
     * @return 減算結果
     */
    inline UInt128 operator-(const UInt128& lhs, uint64_t rhs) {
        UInt128 result = lhs;
        result -= rhs;
        return result;
    }

    /**
     * @brief uint64_tとUInt128の減算
     * @param lhs 左辺値
     * @param rhs 右辺値
     * @return 減算結果
     */
    inline UInt128 operator-(uint64_t lhs, const UInt128& rhs) {
        if (rhs.high > 0 || lhs < rhs.low) {
            throw std::underflow_error("Unsigned subtraction underflow");
        }
        return UInt128(0, lhs - rhs.low);
    }

} // namespace calx

#endif // CALX_UINT128_HPP