sys/lib/libkern/arch/m68k/random.S

   1 /*      $NetBSD: random.S,v 1.3 2009/01/04 17:10:46 pooka Exp $ */
   2
   3 /*
   4  * Copyright (c) 1990,1993 The Regents of the University of California.
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that: (1) source code distributions
   9  * retain the above copyright notice and this paragraph in its entirety, (2)
  10  * distributions including binary code include the above copyright notice and
  11  * this paragraph in its entirety in the documentation or other materials
  12  * provided with the distribution, and (3) all advertising materials mentioning
  13  * features or use of this software display the following acknowledgement:
  14  * ``This product includes software developed by the University of California,
  15  * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of
  16  * the University nor the names of its contributors may be used to endorse
  17  * or promote products derived from this software without specific prior
  18  * written permission.
  19  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  20  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  21  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  22  *
  23  * Here is a very good random number generator.  This implementation is
  24  * based on ``Two Fast Implementations of the "Minimal Standard" Random
  25  * Number Generator'', David G. Carta, Communications of the ACM, Jan 1990,
  26  * Vol 33 No 1.  Do NOT modify this code unless you have a very thorough
  27  * understanding of the algorithm.  It's trickier than you think.  If
  28  * you do change it, make sure that its 10,000'th invocation returns
  29  * 1043618065.
  30  *
  31  * Here is easier-to-decipher pseudocode:
  32  *
  33  * p = (16807*seed)<30:0>       # e.g., the low 31 bits of the product
  34  * q = (16807*seed)<62:31>      # e.g., the high 31 bits starting at bit 32
  35  * if (p + q < 2^31)
  36  *      seed = p + q
  37  * else
  38  *      seed = ((p + q) & (2^31 - 1)) + 1
  39  * return (seed);
  40  *
  41  * The result is in (0,2^31), e.g., it's always positive.
  42  */
  43 #include <machine/asm.h>
  44
  45         .data
  46 ASLOCAL(randseed)
  47         .long   1
  48
  49 ENTRY(random)
  50         movl    #16807, %d0
  51 #ifdef PIC
  52         lea     %pc@(_GLOBAL_OFFSET_TABLE_@GOTPC), %a0
  53         movl    _ASM_LABEL(randseed)@GOT(%a0), %d2
  54         mulsl   (%d2), %d1:%d0
  55 #else
  56         mulsl   _ASM_LABEL(randseed), %d1:%d0
  57 #endif
  58         lsll    #1, %d0
  59         roxll   #2, %d1
  60         addl    %d1, %d0
  61         moveql  #1, %d1
  62         addxl   %d1, %d0
  63         lsrl    #1, %d0
  64 #ifdef PIC
  65         movl    %d0, (%d2)
  66 #else
  67         movl    %d0, _ASM_LABEL(randseed)
  68 #endif
  69         rts