How to divide a 128-bit dividend by a 64-bit divisor, where the dividend's bits are all 1's, and where I only need the 64 LSBs of the quotient?

I need to calculate (2¹²⁸ - 1) / x. The divisor, x, is an unsigned 64-bit number. The dividend is composed of two unsigned 64-bit numbers (high and low), where both numbers are UINT64_MAX. I can only use 64-bit arithmetic and need it to be portable (no use of GNU's __int128, MSCV's _udiv128, assembly, or anything like that). I don't need the high part of the quotient, I only need the lower 64 bits.

How can I do this operation?

Also: x >= 3, x is not a power of 2.

Edit: I created my own solution (answer below). But I welcome any other solution that performs better :)

This is what I ended up coding. I'm sure there are much faster alternatives, but at least this is functional.

Based on: https://en.wikipedia.org/wiki/Division_algorithm#Integer_division_(unsigned)_with_remainder. Adapted for for this particular use-case.

// q = (2^128 - 1) / d, where q is the 64 LSBs of the quotient
uint64_t two_pow_128_minus_1_div_d(uint64_t d) {
    uint64_t q = 0, r_hi = 0, r_lo = 0;

    for (int i = 127; i >= 0; --i) {
        r_hi = (r_hi << 1) | (r_lo >> 63);
        r_lo <<= 1;

        r_lo |= 1UL;

        if (r_hi || r_lo >= d) {
            const uint64_t borrow = d > r_lo;
            r_lo -= d;
            r_hi -= borrow;

            if (i < 64)
                q |= 1UL << i;
        }
    }
    return q;
}