#include <inttypes.h>

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

uint64_t udiv128(uint128_t, uint64_t, uint64_t *);

uint64_t udiv128(uint128_t a, uint64_t b, uint64_t *rem)
{
	// http://codereview.stackexchange.com/questions/67962
	uint64_t q = a.lo << 1;
	uint64_t r = a.hi;
	uint64_t carry = a.lo >> 63;
	for (int i = 0; i < 64; i++) {
		uint64_t temp = r >> 63;
		r = r << 1 | carry;
		carry = temp;
		if (carry == 0) {
			if (r < b)
				goto shift;
			carry++;
		}
		r -= b;
	shift:	temp = q >> 63;
		q = q << 1 | carry;
		carry = temp;
	}
	*rem = r;
	return q;
}