Coverage Report

Created: 2025-09-05 06:52

/src/serenity/AK/UFixedBigIntDivision.h
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright (c) 2023, Dan Klishch <danilklishch@gmail.com>
3
 *
4
 * SPDX-License-Identifier: BSD-2-Clause
5
 */
6
7
#pragma once
8
9
#include <AK/Diagnostics.h>
10
#include <AK/UFixedBigInt.h>
11
12
namespace AK::Detail {
13
14
template<size_t dividend_bit_size, size_t divisor_bit_size, bool restore_remainder>
15
constexpr void div_mod_internal(
16
    StaticStorage<false, dividend_bit_size> const& operand1,
17
    StaticStorage<false, divisor_bit_size> const& operand2,
18
    StaticStorage<false, dividend_bit_size>& quotient,
19
    StaticStorage<false, divisor_bit_size>& remainder)
20
0
{
21
0
    using Ops = StorageOperations<>;
22
23
0
    size_t dividend_len = operand1.size(), divisor_len = operand2.size();
24
0
    while (divisor_len > 0 && !operand2[divisor_len - 1])
25
0
        --divisor_len;
26
0
    while (dividend_len > 0 && !operand1[dividend_len - 1])
27
0
        --dividend_len;
28
29
    // FIXME: Should raise SIGFPE instead
30
0
    VERIFY(divisor_len); // VERIFY(divisor != 0)
31
32
    // Fast paths
33
0
    if (divisor_len == 1 && operand2[0] == 1) { // divisor == 1
34
0
        quotient = operand1;
35
        if constexpr (restore_remainder)
36
0
            Ops::set(0, remainder);
37
0
        return;
38
0
    }
39
40
0
    if (dividend_len < divisor_len) { // dividend < divisor
41
0
        Ops::set(0, quotient);
42
        if constexpr (restore_remainder)
43
0
            Ops::copy(operand1, remainder);
44
0
        return;
45
0
    }
46
47
0
    if (divisor_len == 1 && dividend_len == 1) { // NativeWord / NativeWord
48
0
        Ops::set(operand1[0] / operand2[0], quotient);
49
        if constexpr (restore_remainder)
50
0
            Ops::set(operand1[0] % operand2[0], remainder);
51
0
        return;
52
0
    }
53
54
0
    if (divisor_len == 1) { // BigInt by NativeWord
55
0
        auto u = (static_cast<NativeDoubleWord>(operand1[dividend_len - 1]) << native_word_size) + operand1[dividend_len - 2];
56
0
        auto divisor = operand2[0];
57
58
0
        auto top = u / divisor;
59
0
        quotient[dividend_len - 1] = static_cast<NativeWord>(top >> native_word_size);
60
0
        quotient[dividend_len - 2] = static_cast<NativeWord>(top);
61
62
0
        auto carry = static_cast<NativeWord>(u % divisor);
63
0
        for (size_t i = dividend_len - 2; i--;)
64
0
            quotient[i] = div_mod_words(operand1[i], carry, divisor, carry);
65
0
        for (size_t i = dividend_len; i < quotient.size(); ++i)
66
0
            quotient[i] = 0;
67
        if constexpr (restore_remainder)
68
0
            Ops::set(carry, remainder);
69
0
        return;
70
0
    }
71
72
    // Knuth's algorithm D
73
0
    StaticStorage<false, dividend_bit_size + native_word_size> dividend;
74
0
    Ops::copy(operand1, dividend);
75
0
    auto divisor = operand2;
76
77
0
    Ops::div_mod_internal<restore_remainder>(dividend, divisor, quotient, remainder, dividend_len, divisor_len);
78
0
}
Unexecuted instantiation: void AK::Detail::div_mod_internal<4096ul, 4096ul, false>(AK::Detail::StaticStorage<false, 4096ul> const&, AK::Detail::StaticStorage<false, 4096ul> const&, AK::Detail::StaticStorage<false, 4096ul>&, AK::Detail::StaticStorage<false, 4096ul>&)
Unexecuted instantiation: void AK::Detail::div_mod_internal<128ul, 128ul, true>(AK::Detail::StaticStorage<false, 128ul> const&, AK::Detail::StaticStorage<false, 128ul> const&, AK::Detail::StaticStorage<false, 128ul>&, AK::Detail::StaticStorage<false, 128ul>&)
Unexecuted instantiation: void AK::Detail::div_mod_internal<257ul, 257ul, true>(AK::Detail::StaticStorage<false, 257ul> const&, AK::Detail::StaticStorage<false, 257ul> const&, AK::Detail::StaticStorage<false, 257ul>&, AK::Detail::StaticStorage<false, 257ul>&)
Unexecuted instantiation: void AK::Detail::div_mod_internal<513ul, 256ul, true>(AK::Detail::StaticStorage<false, 513ul> const&, AK::Detail::StaticStorage<false, 256ul> const&, AK::Detail::StaticStorage<false, 513ul>&, AK::Detail::StaticStorage<false, 256ul>&)
Unexecuted instantiation: void AK::Detail::div_mod_internal<385ul, 385ul, true>(AK::Detail::StaticStorage<false, 385ul> const&, AK::Detail::StaticStorage<false, 385ul> const&, AK::Detail::StaticStorage<false, 385ul>&, AK::Detail::StaticStorage<false, 385ul>&)
Unexecuted instantiation: void AK::Detail::div_mod_internal<769ul, 384ul, true>(AK::Detail::StaticStorage<false, 769ul> const&, AK::Detail::StaticStorage<false, 384ul> const&, AK::Detail::StaticStorage<false, 769ul>&, AK::Detail::StaticStorage<false, 384ul>&)
79
80
}