<commit_before>/*
 * mp_divexact.c
 * Copyright (C) 2002-2010 <NAME>. All rights reserved.
 *
 * $Id$
 */

#include "mp.h"
#include "mp_defs.h"

/* This routine implements Jebelean's algorithm for exact division. It will
 * divide u[usize] by d[dsize] and put the quotient in q[usize - dsize + 1]
 * when it is known in advance that u is a multiple of d. If u is NOT a
 * multiple of d, q's contents will not be anything meaningful. */
void
mp_divexact(const mp_digit *u, mp_size usize,
			const mp_digit *d, mp_size dsize, mp_digit *q)
{
	ASSERT(u);
	ASSERT(usize > 0);
	ASSERT(u[usize - 1] != 0);

	ASSERT(d);
	ASSERT(dsize > 0);
	ASSERT(d[dsize - 1] != 0);

	ASSERT(q);

	mp_zero(q, usize - dsize + 1);
	MP_NORMALIZE(u, usize);
	if (!usize) /* U is zero; we are done. */
		return;

#if 0
	if (usize == 1) {
		ASSERT(dsize == 1);
		ASSERT(u[0] % d[0] == 0);
		q[0] = u[0] / d[0];
		return;
	}
#endif

	/* Shift U and D right until D's least significant bit is set. Before
	 * starting, we can check if the index of U's lowest set bit is lower than
	 * D's lowest set bit; if this is the case then U cannot possibly be a
	 * multiple of D and the algorithm terminates unsuccessfully. */
	const unsigned d_shift = mp_odd_shift(d, dsize);
	if (mp_odd_shift(u, usize) < d_shift)
		return;
	const unsigned dd = d_shift / MP_DIGIT_BITS;
	const unsigned ds = d_shift % MP_DIGIT_BITS;
	u += dd, usize -= dd;
	d += dd, dsize -= dd;

	mp_digit *utmp = NULL;
	if (ds) {
		MP_TMP_ALLOC(utmp, usize);
		ASSERT(mp_rshift(u, usize, ds, utmp) == 0);
	} else {
		MP_TMP_COPY(utmp, u, usize);
	}

	mp_digit *dtmp = NULL;
	if (ds) {
		MP_TMP_ALLOC(dtmp, dsize);
		ASSERT(mp_rshift(d, dsize, ds, dtmp) == 0);
		d = dtmp;
	} else {
		dtmp = NULL;
	}

	ASSERT((d[0] & 1) == 1);
	const mp_digit d0_inv = mp_digit_invert(d[0]);

	const mp_size K = usize - dsize + 1;
	for (mp_size k = 0; k < K; k++) {
		q[k] = d0_inv * utmp[k];
		const mp_size size = MIN(dsize, K - k);
		mp_digit cy = mp_dmul_sub(d, size, q[k], &utmp[k]);
		if (cy) {
			ASSERT(usize > k + size);
			ASSERT(mp_dsubi(&utmp[k + size], usize - (k + size), cy) == 0);
		}
		ASSERT(utmp[k] == 0);
	}
	if (dtmp != NULL)
		MP_TMP_FREE(dtmp);
	MP_TMP_FREE(utmp);
}<commit_msg>Remove assertion of non-zero most significant dividend digit. Minor refactoring.<commit_after>/* mp_divexact.c
 * Copyright (C) 2002-2010 <NAME>. All rights reserved. */

#include "mp.h"
#include "mp_defs.h"

/* This routine implements Jebelean's algorithm for exact division. It will
 * divide u[usize] by d[dsize] and put the quotient in q[usize - dsize + 1]
 * when it is known in advance that u is a multiple of d. If u is NOT a
 * multiple of d, q's contents will not be anything meaningful. */
void
mp_divexact(const mp_digit *u, mp_size usize,
			const mp_digit *d, mp_size dsize, mp_digit *q)
{
	ASSERT(u);
	ASSERT(usize > 0);
	ASSERT(d);
	ASSERT(dsize > 0);
	ASSERT(d[dsize - 1] != 0);
	ASSERT(q);

	mp_zero(q, usize - dsize + 1);
	MP_NORMALIZE(u, usize);
	if (!usize) /* U is zero; we are done. */
		return;

#if 0
	if (usize == 1) {
		ASSERT(dsize == 1);
		ASSERT(u[0] % d[0] == 0);
		q[0] = u[0] / d[0];
		return;
	}
#endif

	/* Shift U and D right until D's least significant bit is set. Before
	 * starting, we can check if the index of U's lowest set bit is lower than
	 * D's lowest set bit; if this is the case then U cannot possibly be a
	 * multiple of D and the algorithm terminates unsuccessfully. */
	const unsigned d_shift = mp_odd_shift(d, dsize);
	if (mp_odd_shift(u, usize) < d_shift)
		return;
	const unsigned dd = d_shift / MP_DIGIT_BITS;
	const unsigned ds = d_shift % MP_DIGIT_BITS;
	u += dd, usize -= dd;
	d += dd, dsize -= dd;

	mp_digit *utmp = NULL, *dtmp = NULL;
	if (ds) {
		MP_TMP_ALLOC(utmp, usize);
		ASSERT(mp_rshift(u, usize, ds, utmp) == 0);
		MP_TMP_ALLOC(dtmp, dsize);
		ASSERT(mp_rshift(d, dsize, ds, dtmp) == 0);
		d = dtmp;
	} else {
		MP_TMP_COPY(utmp, u, usize);
	}

	ASSERT((d[0] & 1) == 1);
	const mp_digit d0_inv = mp_digit_invert(d[0]);

	const mp_size q_size = usize - dsize + 1;
	for (mp_size q_i = 0; q_i < q_size; q_i++) {
		q[q_i] = d0_inv * utmp[q_i];
		const mp_size size = MIN(dsize, q_size - q_i);
		mp_digit cy = mp_dmul_sub(d, size, q[q_i], &utmp[q_i]);
		if (cy) {
			ASSERT(usize > q_i + size);
			/* FIXME: this assert will fail if U is not a multiple of D. */
			ASSERT(mp_dsubi(&utmp[q_i + size], usize - (q_i + size), cy) == 0);
		}
		ASSERT(utmp[q_i] == 0);
	}
	if (dtmp != NULL)
		MP_TMP_FREE(dtmp);
	MP_TMP_FREE(utmp);
}
{'fraction_non_alphanumeric': 0.14995563442768411, 'fraction_numerical': 0.015971606033717833, 'mean_word_length': 3.4249263984298333, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2438205', 'n_tokens_mistral': 2020, 'n_tokens_neox': 1878, 'n_words': 586}