/*
 * Given a number of seconds, sec, and 2^64ths of a second, frac, we
 * want a number of ticks for a timeout:
 *
 *	timo = hz*(sec + frac/2^64)
 *	     = hz*sec + hz*frac/2^64
 *	     = hz*sec + hz*(frachi*2^32 + fraclo)/2^64
 *	     = hz*sec + hz*frachi/2^32 + hz*fraclo/2^64,
 *
 * where frachi is the high 32 bits of frac and fraclo is the
 * low 32 bits.
 *
 * We assume hz < INT_MAX/2 < UINT32_MAX, so
 *
 *	hz*fraclo/2^64 < fraclo*2^32/2^64 <= 1,
 *
 * since fraclo < 2^32.
 *
 * We clamp the result at INT_MAX/2 for a timeout in ticks, since we
 * can't represent timeouts higher than INT_MAX in cv_timedwait, and
 * spurious wakeup is OK.  Moreover, we don't want to wrap around,
 * because we compute end - start in ticks in order to compute the
 * remaining timeout, and that difference cannot wrap around, so we use
 * a timeout less than INT_MAX.  Using INT_MAX/2 provides plenty of
 * margin for paranoia and will exceed most waits in practice by far.
 */
static unsigned
bintime2timo(const struct bintime *bt)
{

	KASSERT(hz < INT_MAX/2);
	CTASSERT(INT_MAX/2 < UINT32_MAX);
	if (bt->sec > ((INT_MAX/2)/hz))
		return INT_MAX/2;
	if ((hz*(bt->frac >> 32) >> 32) > (INT_MAX/2 - hz*bt->sec))
		return INT_MAX/2;

	return hz*bt->sec + (hz*(bt->frac >> 32) >> 32);
}

/*
 * timo is in units of ticks.  We want units of seconds and 2^64ths of
 * a second.  We know hz = 1 sec/tick, and 2^64 = 1 sec/(2^64th of a
 * second), from which we can conclude 2^64 / hz = 1 (2^64th of a
 * second)/tick.  So for the fractional part, we compute
 *
 *	frac = rem * 2^64 / hz
 *	     = ((rem * 2^32) / hz) * 2^32
 *
 * Using truncating integer division instead of real division will
 * leave us with only about 32 bits of precision, which means about
 * 1/4-nanosecond resolution, which is good enough for our purposes.
 */
static void
timo2bintime(unsigned timo, struct bintime *bt)
{

	bt->sec = timo / hz;
	bt->frac = (((uint64_t)(timo % hz) << 32)/hz << 32);
}

/*
 * cv_timedwaitbt:
 *
 *	Wait on a condition variable until awoken or the specified
 *	timeout expires.  Returns zero if awoken normally or
 *	EWOULDBLOCK if the timeout expires.
 *
 *	On entry, bt is a timeout in bintime.  cv_timedwaitbt subtracts
 *	the time slept, so on exit, bt is the time remaining after
 *	sleeping.  No infinite timeout; use cv_wait instead.
 *
 *	epsilon is a requested maximum error in timeout (excluding
 *	spurious wakeups).  Currently not used, will be used in the
 *	future to choose between low- and high-resolution timers.
 */
int
cv_timedwaitbt(kcondvar_t *cv, kmutex_t *mtx, struct bintime *bt,
    const struct bintime *epsilon __unused)
{
	struct bintime slept;
	unsigned start, end;
	int error;

	/*
	 * hardclock_ticks is technically int, but nothing special
	 * happens instead of overflow, so we assume two's-complement
	 * wraparound and just treat it as unsigned.
	 */
	start = hardclock_ticks;
	error = cv_timedwait(cv, mtx, bintime2timo(bt));
	end = hardclock_ticks;

	timo2bintime(end - start, &slept);
	/* bt := bt - slept */
	bintime_sub(bt, &slept);

	return error;
}

/*
 * cv_timedwaitbt_sig:
 *
 *	Wait on a condition variable until awoken, the specified
 *	timeout expires, or interrupted by a signal.  Returns zero if
 *	awoken normally, EWOULDBLOCK if the timeout expires, or
 *	EINTR/ERESTART if interrupted by a signal.
 *
 *	On entry, bt is a timeout in bintime.  cv_timedwaitbt_sig
 *	subtracts the time slept, so on exit, bt is the time remaining
 *	after sleeping.  No infinite timeout; use cv_wait_sig instead.
 *
 *	epsilon is a requested maximum error in timeout (excluding
 *	spurious wakeups).  Currently not used, will be used in the
 *	future to choose between low- and high-resolution timers.
 */
int
cv_timedwaitbt_sig(kcondvar_t *cv, kmutex_t *mtx, struct bintime *bt,
    const struct bintime *epsilon __unused)
{
	struct bintime slept;
	unsigned start, end;
	int error;

	/*
	 * hardclock_ticks is technically int, but nothing special
	 * happens instead of overflow, so we assume two's-complement
	 * wraparound and just treat it as unsigned.
	 */
	start = hardclock_ticks;
	error = cv_timedwait_sig(cv, mtx, bintime2timo(bt));
	end = hardclock_ticks;

	timo2bintime(end - start, &slept);
	/* bt := bt - slept */
	bintime_sub(bt, &slept);

	return error;
}