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

static inline uint64_t widen_32_to_64(uint32_t narrow, uint64_t near)
{
	return near + (int32_t) (narrow - (uint32_t) near);
}

uint64_t
random_u64(void) {
	assert(sizeof (long int) == 8);
	return (uint32_t) mrand48() | (((uint64_t) (uint32_t) mrand48()) << 32);
}

uint32_t
random_u32(int bits) {
	return random_u64() & ((1UL << bits) - 1);
}

int32_t
random_s32(int bits) {
	int32_t	value = (int32_t) random_u32(bits);

	return value << (32 - bits) >> (32 - bits);
}

int
main(int argc, char **argv) {
	int bits;
	int tries;

	/* Validate random number generators */
	for (bits = 1; bits <= 32; bits++) {
		int64_t	max = ((1L << (bits-1)) - 1);
		int32_t min = -max - 1;
		int32_t range_min = INT32_MAX;
		int32_t range_max = INT32_MIN;

		for (tries = 0; tries < 100000; tries++) {
			int32_t	i = random_s32(bits);

			if (i < min || max < i) {
				printf ("min %d i %d max %d\n", min, i, max);
				exit(1);
			}
			if (i < range_min)
				range_min = i;
			if (i > range_max)
				range_max = i;
		}
		if (range_min >= min/2 || (range_max <= max/2 && max != 0)) {
			printf ("bits %d min %d max %d range min %d range max %d\n",
				bits, min, max, range_min, range_max);
			exit(1);
		}
	}

	/* Check to make sure the 'widen' function generates the right answer */
	for (bits = 1; bits < 32; bits++) {
		for (tries = 0; tries < 100000; tries++) {

			/* A random 64-bit value */
			uint64_t	near = random_u64();

			/* Compute a nearby value, within a 32-bit delta of the target*/
			int32_t		delta = random_s32(bits);
			uint64_t	value = near + delta;

			/* Narrow the value to 32-bits */
			uint32_t	narrow = (uint32_t) (value);

			/* Use our 'widen' function to reconstruct the wider value */
			uint64_t	wide = widen_32_to_64(narrow, near);

			/* Make sure the reconstruction worked */
			if (wide != value)
				printf ("widen failed near %ld value %ld wide %ld\n",
					near, value, wide);
		}
	}
}