/* ex: set ts=8: */
/**
 * constraints:
 * 	* 16-bit embedded system
 * 	* low cpu and memory use outweigh quality of output... if we had more space we'd probably use a Mersenne Twister or an LFSR
 * 	* implementation will be in asm, so keep statements simple
 */

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

/**
 * @param n number of bits to randomly turn on (0-8)
 * @note use lagged Fibonacci generator (http://en.wikipedia.org/wiki/Lagged_Fibonacci_generator)
 */
unsigned short n_rand_bits(unsigned short n)
{
	static unsigned short y, j = 0xDECA, k = 0xFBAD; /* initialize with whatever */
	register unsigned short v = 0, bit, off = 0;
	if (n > 4) {
		off = 1;
		n = 8 - n;
	}
	while (n) {
	tryagain:
		y = j + k;
		k = j;
		j = y;
		bit = y >> 13;
		bit ^= y;
		bit &= 0x7;
		bit = 1 << bit;
		if (v & bit)
			goto tryagain;
		v |= bit;
		n--;
	}
	if (off)
		v = ~v & 0xFF;
	return v;
}

/**
 * count 1 bits, use for testing
 * @note use AMD's Efficient Implementation of Population-Count Function in 32-Bit Mode
 * (http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF)
 */
unsigned short bitcnt(unsigned short v)
{
	const unsigned short w = v - ((v >> 1) & 0x5555); /* sum 2 bit groups */
	const unsigned short x = (w & 0x3333) + ((w >> 2) & 0x3333); /* sum 4 bit groups */
	const unsigned short c = ((x + (x >> 4) & 0x0F0F) * 0x0101) >> 8; /* sum 8 bit groups, magic multiplier, shift */
	return c;
}

/**
 * use: ./n_rand_bits n
 * we generate 100 8-bit numbers with n bits on
 */
int main(int argc, char *argv[])
{
	unsigned int rnd, n = atoi(argv[1]) % 9, i = 1 << 21, cnt[256] = { 0 };
	while (i--) {
		rnd = n_rand_bits(n);
		if (bitcnt(rnd) != n) { /* check results */
			printf("bitcnt(%02X) == %u (expected %u)\n", n, bitcnt(rnd), n);
			abort();
		}
		cnt[rnd]++;
	}
	for (i = 0; i < sizeof cnt / sizeof cnt[0]; i++) /* print distribution */
		if (bitcnt(i) == n)
			printf("%u|%u\n", i, cnt[i]);
	return 0;
}