#include <stdio.h>
#include <stdint.h>

typedef uint64_t u64;

// 修改後的除法函數，返回商和餘數
void nvme_u64_div(u64 dividend, u64 divisor, u64* quotient, u64* remainder) {
    *quotient = 0;
    *remainder = 0;
    int i;
    for (i = 63; i >= 0; i--) {
        *remainder = (*remainder << 1) | ((dividend >> i) & 1);
        if (*remainder >= divisor) {
            *remainder -= divisor;
            *quotient |= (1ULL << i);
        }
    }
}

// 測試案例結構
typedef struct {
    u64 dividend;
    u64 divisor;
    u64 expected_quotient;
    u64 expected_remainder;
} TestCase;

// 執行測試並打印結果
void run_test_case(TestCase test) {
    u64 quotient, remainder;
    nvme_u64_div(test.dividend, test.divisor, &quotient, &remainder);
    
    printf("Dividend: %llu\n", test.dividend);
    printf("Divisor: %llu\n", test.divisor);
    printf("Expected Quotient: %llu\n", test.expected_quotient);
    printf("Actual Quotient: %llu\n", quotient);
    printf("Expected Remainder: %llu\n", test.expected_remainder);
    printf("Actual Remainder: %llu\n", remainder);
    printf("Test %s\n\n", 
           (quotient == test.expected_quotient && remainder == test.expected_remainder) 
           ? "PASSED" : "FAILED");
}

int main() {
    // 測試案例數組
    TestCase test_cases[] = {
        // 正常案例
        {1000000000000000000ULL, 3ULL, 333333333333333333ULL, 1ULL},
        {9223372036854775807ULL, 2ULL, 4611686018427387903ULL, 1ULL},
        {18446744073709551615ULL, 9223372036854775807ULL, 2ULL, 1ULL},

        // 邊界案例
        {18446744073709551615ULL, 1ULL, 18446744073709551615ULL, 0ULL},
        {18446744073709551615ULL, 18446744073709551615ULL, 1ULL, 0ULL},
        {0ULL, 18446744073709551615ULL, 0ULL, 0ULL},

        // 特殊案例
        {18446744073709551614ULL, 2ULL, 9223372036854775807ULL, 0ULL},
        {18446744073709551615ULL, 2ULL, 9223372036854775807ULL, 1ULL},
        {18446744073709551615ULL, 3ULL, 6148914691236517205ULL, 0ULL},

        // 質數案例
        {18446744073709551557ULL, 11ULL, 1676976734155413778ULL, 9ULL},
        {18446744073709551557ULL, 18446744073709551557ULL, 1ULL, 0ULL},

        // 2的冪次方案例
        {9223372036854775808ULL, 2ULL, 4611686018427387904ULL, 0ULL},
        // 注意：2^64 溢出了 u64，所以我們不包括這個案例
    };

    int num_tests = sizeof(test_cases) / sizeof(test_cases[0]);

    for (int i = 0; i < num_tests; i++) {
        printf("Test Case %d:\n", i + 1);
        run_test_case(test_cases[i]);
    }

    return 0;
}