/*
 * loop_hash.c:
 * 
 * This program is used to verify brutally this problem:
 * We have a 32bit hash function f():
 * 	h=start=random_number
 * 	we take h=f(h); where `h' is a 32bit number.
 * In less than 2^32 steps is it possible that `h' is equal to `start'?
 *
 * Usage: 
 * 	gcc loop_hash.c -o lh
 * 	./lh `echo $RANDOM` 
 *
 * By AlpT (@freaknet.org)
 * Fri Nov 18 21:15:08 CET 2005
 */

#include <limits.h>
#include <sys/types.h>


#define FNV_32_PRIME ((u_long)0x01000193)
#define FNV1_32_INIT ((u_long)0x811c9dc5)

/*		Ripped 32bit Hash function 
 *
 * Fowler/Noll/Vo hash
 *
 * See  http://www.isthe.com/chongo/tech/comp/fnv/index.html
 * for more details as well as other forms of the FNV hash.
 *
 ***
 *
 * Use the recommended 32 bit FNV-1 hash, pass FNV1_32_INIT as the
 * u_long hashval argument to fnv_32_buf().
 *
 ***
 *
 * Please do not copyright this code.  This code is in the public domain.
 *
 * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
 * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
 * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
 * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 *
 * By:
 *	chongo <Landon Curt Noll> /\oo/\
 *      http://www.isthe.com/chongo/
 * Share and Enjoy!	:-)
 *
 * fnv_32_buf - perform a 32 bit Fowler/Noll/Vo hash on a buffer
 * `hval'	- previous hash value or 0 if first call
 * returns:
 *	32 bit hash as a static hash type
 */
u_long fnv_32_buf(void *buf, size_t len, u_long hval)
{
    u_char *bp = (u_char *)buf;	/* start of buffer */
    u_char *be = bp + len;		/* beyond end of buffer */

    /*
     * FNV-1 hash each octet in the buffer
     */
    while (bp < be) {

	/* multiply by the 32 bit FNV magic prime mod 2^32 */
	hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);

	/* xor the bottom with the current octet */
	hval ^= (u_long)*bp++;
    }

    /* return our new hash value */
    return hval;
}

/* Robert Jenkins's 32 bit Mix Function */
unsigned int inthash(unsigned int key)
{
	key += (key << 12);
	key ^= (key >> 22);
	key += (key << 4);
	key ^= (key >> 9);
	key += (key << 10);
	key ^= (key >> 2);
	key += (key << 7);
	key ^= (key >> 12);
	return key;
}

int main(int argc, char **argv) 
{
	unsigned int i, x, h, e, start, end;

	if(argc == 1)
		start=i=0;
	else
		start=i=atoi(argv[1]);
	if (argc > 2)
		end=atoi(argv[2]);
	else
		end=UINT_MAX;

	printf("Verifying rand %u - %u\n", start, end);
	
	for(; i <= end; i++) {
		printf("\r- %u", i);
		
		h=FNV1_32_INIT;	
		for(x=i, e=0; e <= UINT_MAX; e++) {
			//printf("\r- %u - %u", i, e);
			//x=inthash(x);
			x=fnv_32_buf(&x, sizeof(x), h);
			h=x;
			
			if(x == i) {
				printf("\nAaaaaah! Found! It is true, this happens! grgrg\n"
						"e: %u i: %u h(x): %u \n", e, i, x);
				exit(0);
			}
		}
		
	}
	
	printf("Ok, range %u - %u verified\n", start, end);
	return 0;
}