11.6Sriastrad/*	$NetBSD: random.S,v 1.6 2014/03/18 18:20:43 riastradh Exp $	*/
21.1Smycroft
31.1Smycroft/*
41.1Smycroft * Copyright (c) 1990,1993 The Regents of the University of California.
51.1Smycroft * All rights reserved.
61.1Smycroft *
71.1Smycroft * Redistribution and use in source and binary forms, with or without
81.1Smycroft * modification, are permitted provided that: (1) source code distributions
91.1Smycroft * retain the above copyright notice and this paragraph in its entirety, (2)
101.1Smycroft * distributions including binary code include the above copyright notice and
111.1Smycroft * this paragraph in its entirety in the documentation or other materials
121.1Smycroft * provided with the distribution, and (3) all advertising materials mentioning
131.1Smycroft * features or use of this software display the following acknowledgement:
141.1Smycroft * ``This product includes software developed by the University of California,
151.1Smycroft * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of
161.1Smycroft * the University nor the names of its contributors may be used to endorse
171.1Smycroft * or promote products derived from this software without specific prior
181.1Smycroft * written permission.
191.1Smycroft * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
201.1Smycroft * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
211.1Smycroft * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
221.1Smycroft *
231.1Smycroft * Here is a very good random number generator.  This implementation is
241.1Smycroft * based on ``Two Fast Implementations of the "Minimal Standard" Random
251.1Smycroft * Number Generator'', David G. Carta, Communications of the ACM, Jan 1990,
261.1Smycroft * Vol 33 No 1.  Do NOT modify this code unless you have a very thorough
271.1Smycroft * understanding of the algorithm.  It's trickier than you think.  If
281.1Smycroft * you do change it, make sure that its 10,000'th invocation returns
291.1Smycroft * 1043618065.
301.1Smycroft *
311.1Smycroft * Here is easier-to-decipher pseudocode:
321.1Smycroft *
331.1Smycroft * p = (16807*seed)<30:0>	# e.g., the low 31 bits of the product
341.1Smycroft * q = (16807*seed)<62:31>	# e.g., the high 31 bits starting at bit 32
351.1Smycroft * if (p + q < 2^31)
361.1Smycroft * 	seed = p + q
371.1Smycroft * else
381.1Smycroft *	seed = ((p + q) & (2^31 - 1)) + 1
391.1Smycroft * return (seed);
401.1Smycroft *
411.1Smycroft * The result is in (0,2^31), e.g., it's always positive.
421.1Smycroft */
431.1Smycroft#include <machine/asm.h>
441.1Smycroft
451.1Smycroft	.data
461.1SmycroftASLOCAL(randseed)
471.1Smycroft	.long	1
481.1Smycroft
491.1SmycroftENTRY(random)
501.2Sthorpej	movl	#16807, %d0
511.5Smatt	LEA_LCL(_ASM_LABEL(randseed),%a0)
521.5Smatt	mulsl	(%a0), %d1:%d0
531.2Sthorpej	lsll	#1, %d0
541.2Sthorpej	roxll	#2, %d1
551.2Sthorpej	addl	%d1, %d0
561.2Sthorpej	moveql	#1, %d1
571.2Sthorpej	addxl	%d1, %d0
581.2Sthorpej	lsrl	#1, %d0
591.5Smatt	movl	%d0, (%a0)
601.1Smycroft	rts
611.5SmattEND(random)
62