oarust 0.9.0

GPU-first semantic computing engine written in Rust
// Public-data mixed-width division. No OA C++ BigInt donor exists.
// Mechanical extension of the qualified restoring-division body: the dividend
// and quotient have dividend_words limbs; the remainder keeps words plus its carry bit.
// Preconditions: 1 <= words <= 128, 1 <= dividend_words <= 256. Zero divisor yields zero outputs/false.
import bigint_words;
import bigint_modular;
import bigint_montgomery;
import wide_u32;

bool bigint_divide_mixed(
	uint dividend[256],
	uint divisor[128],
	uint dividend_words,
	uint words,
	out uint quotient[256],
	out uint remainder[128]
) {
	for (uint i = 0u; i < 256u; ++i) quotient[i] = 0u;
	bigint_zero(remainder);
	uint nonzero = 0u;
	for (uint i = 0u; i < words; ++i) nonzero |= divisor[i];
	if (nonzero == 0u) return false;
	for (uint bit = dividend_words * 32u; bit != 0u; --bit) {
		uint index = bit - 1u;
		uint carry = (dividend[index / 32u] >> (index % 32u)) & 1u;
		for (uint i = 0u; i < words; ++i) {
			uint next = remainder[i] >> 31u;
			remainder[i] = (remainder[i] << 1u) | carry;
			carry = next;
		}
		if (carry != 0u || bigint_compare(remainder, divisor, words) >= 0) {
			uint borrow = 0u;
			for (uint i = 0u; i < words; ++i) {
				uint difference = remainder[i] - divisor[i];
				uint borrow_ab = uint(remainder[i] < divisor[i]);
				uint value = difference - borrow;
				borrow = borrow_ab | uint(difference < borrow);
				remainder[i] = value;
			}
			quotient[index / 32u] |= 1u << (index % 32u);
		}
	}
	return true;
}

// REDC for a full double-width input. Public inputs need not satisfy T < m*R.
// Keep the extra accumulator carry, then canonically reduce the N+1-word
// candidate. For the customary bounded input, at most one subtraction is needed.
bool bigint_montgomery_reduce_wide(
	uint input[256],
	uint modulus[128],
	uint words,
	out uint result[128]
) {
	bigint_zero(result);
	if ((modulus[0] & 1u) == 0u) return false;
	uint accumulator[257];
	for (uint i = 0u; i < 257u; ++i) accumulator[i] = 0u;
	for (uint i = 0u; i < words * 2u; ++i) accumulator[i] = input[i];
	uint negative_inverse = bigint_montgomery_factor(modulus[0]);
	for (uint i = 0u; i < words; ++i) {
		uint factor = accumulator[i] * negative_inverse;
		uint carry = 0u;
		for (uint j = 0u; j < words; ++j) {
			uint2 product = mul32_wide(factor, modulus[j]);
			uint sum = product.x + accumulator[i + j];
			uint carry_product = uint(sum < product.x);
			uint value = sum + carry;
			carry = product.y + carry_product + uint(value < sum);
			accumulator[i + j] = value;
		}
		uint position = i + words;
		while (carry != 0u && position <= words * 2u) {
			uint previous = accumulator[position];
			accumulator[position] = previous + carry;
			carry = uint(accumulator[position] < previous);
			++position;
		}
	}
	uint candidate[256];
	for (uint i = 0u; i < 256u; ++i) candidate[i] = 0u;
	for (uint i = 0u; i <= words; ++i) candidate[i] = accumulator[i + words];
	return bigint_reduce_wide(candidate, words + 1u, modulus, words, result);
}