#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

/* Same "calling convention" as do_div:
 * - divide (n << 32) by base
 * - put result in n
 * - return remainder
 */
#define do_shl32_div32(n, base)					     \
        ({							     \
	    uint32_t __quot, __rem;				     \
            asm("divl %2" : "=a" (__quot), "=d" (__rem)		     \
                        : "rm" (base), "0" (0), "1" ((uint32_t) n)); \
            n = __quot;						     \
            __rem;						     \
	})


static uint32_t div_frac(uint32_t dividend, uint32_t divisor)
{
        do_shl32_div32(dividend, divisor);
        return dividend;
}

static void kvm_get_time_scale(uint64_t scaled_hz, uint64_t base_hz,
                               int8_t *pshift, uint32_t *pmultiplier)
{
        uint64_t scaled64;
        int32_t  shift = 0;
        uint64_t tps64;
        uint32_t tps32;

        tps64 = base_hz;
        scaled64 = scaled_hz;
        while (tps64 > scaled64*2 || tps64 & 0xffffffff00000000ULL) {
                tps64 >>= 1;
                shift--;
        }

        tps32 = (uint32_t)tps64;
        while (tps32 <= scaled64 || scaled64 & 0xffffffff00000000ULL) {
                if (scaled64 & 0xffffffff00000000ULL || tps32 & 0x80000000)
                        scaled64 >>= 1;
                else
                        tps32 <<= 1;
                shift++;
        }

        *pshift = shift;
        *pmultiplier = div_frac(scaled64, tps32);
}
/*
 * Scale a 64-bit delta by scaling and multiplying by a 32-bit fraction,
 * yielding a 64-bit result.
 */
static inline uint64_t pvclock_scale_delta(uint64_t delta, uint32_t mul_frac, int shift)
{
        uint64_t product;
#ifdef __i386__
        uint32_t tmp1, tmp2;
#else
        unsigned long tmp;
#endif

        if (shift < 0)
                delta >>= -shift;
        else
                delta <<= shift;

#ifdef __i386__
        __asm__ (
                "mul  %5       ; "
                "mov  %4,%%eax ; "
                "mov  %%edx,%4 ; "
                "mul  %5       ; "
                "xor  %5,%5    ; "
                "add  %4,%%eax ; "
                "adc  %5,%%edx ; "
                : "=A" (product), "=r" (tmp1), "=r" (tmp2)
                : "a" ((uint32_t)delta), "1" ((uint32_t)(delta >> 32)), "2" (mul_frac) );
#elif defined(__x86_64__)
        __asm__ (
                "mulq %[mul_frac] ; shrd $32, %[hi], %[lo]"
                : [lo]"=a"(product),
                  [hi]"=d"(tmp)
                : "0"(delta),
                  [mul_frac]"rm"((uint64_t)mul_frac));
#else
#error implement me!
#endif

        return product;
}

struct tscale {
	int8_t shift;
	uint32_t mul;
};

#define NSEC_PER_SEC 1000000000UL

struct tscale h2g;
struct tscale g2ns;
struct tscale h2ns;

int main(int argc, char **argv)
{
	uint64_t scaled, base;
	uint64_t host_tsc;

	if (argc < 3) {
		fprintf(stderr, "Usage: %s <scaled> <base>\n", argv[0]);
		exit(1);
	}

	scaled = strtoul(argv[1], NULL, 0);
	base = strtoul(argv[2], NULL, 0);

	kvm_get_time_scale(scaled, base, &h2g.shift, &h2g.mul);
	kvm_get_time_scale(NSEC_PER_SEC, scaled, &g2ns.shift, &g2ns.mul);
	kvm_get_time_scale(NSEC_PER_SEC, base, &h2ns.shift, &h2ns.mul);

	printf("Convert %lu → %lu, * %u >> %d\n",
	       base, scaled, h2g.mul , 32 - h2g.shift);
	printf("Convert %lu → %lu, * %u >> %d\n",
	       scaled, NSEC_PER_SEC, g2ns.mul , 32 - g2ns.shift);
	printf("Convert %lu → %lu, * %u >> %d\n",
	       base, NSEC_PER_SEC, h2ns.mul , 32 - h2ns.shift);


	for (host_tsc = 0; host_tsc <= base * 86400; host_tsc += (60 * base)) {
		uint64_t guest_tsc = pvclock_scale_delta(host_tsc, h2g.mul, h2g.shift);
		uint64_t guest_ns = pvclock_scale_delta(guest_tsc, g2ns.mul, g2ns.shift);
		uint64_t host_ns = pvclock_scale_delta(host_tsc, h2ns.mul, h2ns.shift);

		printf("TSC %lu, guest TSC %lu, guest ns %lu host ns %lu (delta %ld)\n",
		       host_tsc, guest_tsc, guest_ns, host_ns, guest_ns - host_ns);
	}
	return 0;

}