#include <inttypes.h>

typedef struct {
	uint64_t hi;
	uint64_t lo;
} uint128_t;

void x2(uint128_t *);
void udiv256(uint128_t, uint128_t, uint128_t, uint128_t *, uint128_t *);

void x2(uint128_t *n)
{
	n->hi = n->hi << 1 | n->lo >> 63;
	n->lo <<= 1;
}

void udiv256(uint128_t a_low, uint128_t a_high, uint128_t b, uint128_t *quot, uint128_t *rem)
{
	uint128_t q, r;	// http://codereview.stackexchange.com/questions/67962

	q.hi = a_low.hi;
	q.lo = a_low.lo;
	x2(&q);
	r.hi = a_high.hi;
	r.lo = a_high.lo;
	uint64_t carry = a_low.hi >> 63;
	for (int i = 0; i < 128; i++) {
		uint64_t temp = r.hi >> 63;
		x2(&r);
		r.lo |= carry;
		carry = temp;
		if (carry == 0) {
			if (r.hi < b.hi || (r.hi == b.hi && r.lo < b.lo))
				goto shift;
			carry++;
		}
		r.hi -= b.hi;
		if (r.lo < b.lo)
			r.hi--;
		r.lo -= b.lo;
	shift:	temp = q.hi >> 63;
		x2(&q);
		q.lo |= carry;
		carry = temp;
	}
	rem->hi = r.hi;
	rem->lo = r.lo;
	quot->hi = q.hi;
	quot->lo = q.lo;
}