1*ad9091c3Sragge/* $NetBSD: random.S,v 1.4 2007/01/14 13:26:18 ragge Exp $ */ 2*ad9091c3Sragge 3*ad9091c3Sragge/* 4*ad9091c3Sragge * Copyright (c) 1994 Ludd, University of Lule}, Sweden. All rights reserved. 5*ad9091c3Sragge * 6*ad9091c3Sragge * Redistribution and use in source and binary forms, with or without 7*ad9091c3Sragge * modification, are permitted provided that the following conditions 8*ad9091c3Sragge * are met: 9*ad9091c3Sragge * 1. Redistributions of source code must retain the above copyright 10*ad9091c3Sragge * notice, this list of conditions and the following disclaimer. 11*ad9091c3Sragge * 2. Redistributions in binary form must reproduce the above copyright 12*ad9091c3Sragge * notice, this list of conditions and the following disclaimer in the 13*ad9091c3Sragge * documentation and/or other materials provided with the distribution. 14*ad9091c3Sragge * 3. The name of the author may not be used to endorse or promote products 15*ad9091c3Sragge * derived from this software without specific prior written permission 16*ad9091c3Sragge * 17*ad9091c3Sragge * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18*ad9091c3Sragge * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19*ad9091c3Sragge * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20*ad9091c3Sragge * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21*ad9091c3Sragge * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22*ad9091c3Sragge * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23*ad9091c3Sragge * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24*ad9091c3Sragge * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25*ad9091c3Sragge * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26*ad9091c3Sragge * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27*ad9091c3Sragge */ 285ba0f1caSmycroft 295ba0f1caSmycroft/* 305ba0f1caSmycroft * Copyright (c) 1990,1993 The Regents of the University of California. 315ba0f1caSmycroft * All rights reserved. 325ba0f1caSmycroft * 335ba0f1caSmycroft * Redistribution and use in source and binary forms, with or without 345ba0f1caSmycroft * modification, are permitted provided that: (1) source code distributions 355ba0f1caSmycroft * retain the above copyright notice and this paragraph in its entirety, (2) 365ba0f1caSmycroft * distributions including binary code include the above copyright notice and 375ba0f1caSmycroft * this paragraph in its entirety in the documentation or other materials 385ba0f1caSmycroft * provided with the distribution, and (3) all advertising materials mentioning 395ba0f1caSmycroft * features or use of this software display the following acknowledgement: 405ba0f1caSmycroft * ``This product includes software developed by the University of California, 415ba0f1caSmycroft * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of 425ba0f1caSmycroft * the University nor the names of its contributors may be used to endorse 435ba0f1caSmycroft * or promote products derived from this software without specific prior 445ba0f1caSmycroft * written permission. 455ba0f1caSmycroft * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED 465ba0f1caSmycroft * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF 475ba0f1caSmycroft * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 485ba0f1caSmycroft * 495ba0f1caSmycroft * Here is a very good random number generator. This implementation is 505ba0f1caSmycroft * based on ``Two Fast Implementations of the "Minimal Standard" Random 515ba0f1caSmycroft * Number Generator'', David G. Carta, Communications of the ACM, Jan 1990, 525ba0f1caSmycroft * Vol 33 No 1. Do NOT modify this code unless you have a very thorough 535ba0f1caSmycroft * understanding of the algorithm. It's trickier than you think. If 545ba0f1caSmycroft * you do change it, make sure that its 10,000'th invocation returns 555ba0f1caSmycroft * 1043618065. 565ba0f1caSmycroft * 575ba0f1caSmycroft * Here is easier-to-decipher pseudocode: 585ba0f1caSmycroft * 595ba0f1caSmycroft * p = (16807*seed)<30:0> # e.g., the low 31 bits of the product 605ba0f1caSmycroft * q = (16807*seed)<62:31> # e.g., the high 31 bits starting at bit 32 615ba0f1caSmycroft * if (p + q < 2^31) 625ba0f1caSmycroft * seed = p + q 635ba0f1caSmycroft * else 645ba0f1caSmycroft * seed = ((p + q) & (2^31 - 1)) + 1 655ba0f1caSmycroft * return (seed); 665ba0f1caSmycroft * 675ba0f1caSmycroft * The result is in (0,2^31), e.g., it's always positive. 685ba0f1caSmycroft */ 695ba0f1caSmycroft 70237e7847Smatt#include <machine/asm.h> 71237e7847Smatt 725ba0f1caSmycroft .data 735ba0f1caSmycroftrandseed: 745ba0f1caSmycroft .long 1 75237e7847Smatt 76237e7847SmattENTRY(random, 0) 776cad4b79Smatt movl $16807,%r0 785ba0f1caSmycroft 796cad4b79Smatt movl randseed,%r1 # %r2=16807*loword(randseed) 806cad4b79Smatt bicl3 $0xffff0000,%r1,%r2 816cad4b79Smatt mull2 %r0,%r2 826cad4b79Smatt ashl $-16,%r1,%r1 # %r1=16807*hiword(randseed) 836cad4b79Smatt bicl2 $0xffff0000,%r1 846cad4b79Smatt mull2 %r0,%r1 856cad4b79Smatt bicl3 $0xffff0000,%r2,%r0 866cad4b79Smatt ashl $-16,%r2,%r2 # %r1+=(%r2>>16) 876cad4b79Smatt bicl2 $0xffff0000,%r2 886cad4b79Smatt addl2 %r2,%r1 896cad4b79Smatt ashl $16,%r1,%r2 # %r0|=%r1<<16 906cad4b79Smatt bisl2 %r2,%r0 916cad4b79Smatt ashl $-16,%r1,%r1 # %r1=%r1>>16 925ba0f1caSmycroft 936cad4b79Smatt ashl $1,%r1,%r1 946cad4b79Smatt movl %r0,%r2 956cad4b79Smatt rotl $1,%r0,%r0 966cad4b79Smatt bicl2 $0xfffffffe,%r0 976cad4b79Smatt bisl2 %r0,%r1 986cad4b79Smatt movl %r2,%r0 996cad4b79Smatt bicl2 $0x80000000,%r0 1006cad4b79Smatt addl2 %r1,%r0 1015ba0f1caSmycroft bgeq L1 1026cad4b79Smatt subl2 $0x7fffffff,%r0 1036cad4b79SmattL1: movl %r0,randseed 1045ba0f1caSmycroft ret 105