Better random numbers in IntyBASIC

+DZ-Jay · August 14, 2021

As part of my P-Machinery 2.0 framework, I've implemented a Pseudo-Random Number Generator (PRNG) library, and I've prepared some "glue code" to allow integration with IntyBASIC programs.

Introduction

The PRNG uses a Galois implementation of a Linear Feedback Shift Register (LFSR), based on some optimized C code I found on the web. I translated the original code into CP-1610 Assembly Language and optimized it with the help of @intvnut and @Arnauld. The original C source code is posted below, for reference:

uint32_t lfsr = 1;
unsigned period = 0;

do {
  /* taps: 32 31 29 1; feedback polynomial: x^32 + x^31 + x^29 + x + 1 */
  lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) ? 0xD0000001u : 0);
  
  ++period;
} while(lfsr != 1u);


uint32_t lfsr2(uint32_t lfsr, uint32_t iters)
{
   while (iters-- != 0)
       lfsr = (lfsr >> 1) ^ (lfsr & 1u ? 0xD0000001u : 0);

   return lfsr;
}

IntyBASIC Integration

I've prepared a neat IntyBASIC SDK project folder with the library and sample usage. If you're using the IntyBASIC SDK (and why not?), you can just extract the contents of the ZIP and place the "rand" folder directly into the "Projects" folder; and you're ready to roll.

If you are not using the SDK, no worries, the package contains just standard IntyBASIC and Assembly modules, so it'll work in any IntyBASIC development environment.

The file "rand.bas" included in the package, can serve as a quick reference on the routines available, and how and when to use them. The PRNG library itself is contained within the "lib" folder.

The library files are:

prng.asm - Assembly Language routines implementing the PRNG.
alu.mac - A library of arithmetic and logic assembler macros employed by the PRNG library.
pow2.mac - A library of assembler "Power Of 2" macros employed by the PRNG library.
rand-basm.mac - The high-level Assembly Language interface to the PRNG, modified to support IntyBASIC integration.
bas-interface.bas - The IntyBASIC integration interface to use the PRNG library.
bas-library.bas - The IntyBASIC integration library to use the PRNG library.

You can safely ignore all other files.

To integrate into your program, you need to follow these steps, which are in turn illustrated in the "rand.bas" file:

Copy the "lib" folder into your own IntyBASIC program's project folder. This folder contains all the modules needed by the library.
Include the file "lib/bas-interface.bas" at the top of your program. This module is responsible for including the macro dependencies and defining the IntyBASIC native calling interface available to some of the library routines.
Include the file "lib/bas-library.bas" at the bottom of your program, or out of its way, wherever you typically include other libraries and modules. This module is responsible for defining the required RAM variables and including the Assembly Language code module.

For example, a simple program integration would look something like this:

OPTION EXPLICIT

' Include useful predefined constants
INCLUDE "constants.bas"

' Include the PRNG interface macro library.  This
' needs to be done at the top of the program.
INCLUDE "lib/bas-interface.bas"

' Your main game loop goes here ...
Main:
    ' ...
    ' Do some gamey stuff.
    ' ...
GOTO Main

' Include the PRNG IntyBASIC Interface library
' anywhere in your program, along with any other
' libraries you use.
INCLUDE "lib/bas-library.bas"

After that, it's all ready. You can randomize your game world with reckless abandon. ?

Calling Conventions

Some routines included in the library have IntyBASIC macro wrappers, making them easy to call from IntyBASIC as if they were native functions. Unfortunately, due to some limitations in the way that the assembler interfaces with IntyBASIC, not all routines have this, so they must be called using the ASM directive.

The library provides both interfaces, whenever possible, so you can decide whether you want to be consistent and always use the ASM interface, or mix and match to your satisfaction.

Moreover, some of the routines take IntyBASIC variables as arguments. Because of the way that the assembler accesses IntyBASIC variables, these need to be typed in upper-case, irrespective of the original capitalization of the variable names in the program.

In any case, the file "rand.asm" included in the package, serves as a guide to the available routines, as well as a reference documenting how to use them.

For example, consider the macro "RND.Seed()," which initializes the PRNG with a 32-bit seed. The documentation states:

	'   RND.Seed(seed):
	'     Seeds the PRNG with an initial 32-bit value.
	'
	'       Arguments:
	'           seed    A 32-bit value to seed the PRNG
	'
	'   IntyBASIC Alias:
	'       PRNG_Seed(seed)
	ASM RND.Seed(($0EA7 + ($DEAD * $BEEF)) OR $0D1E)

As illustrated, there are two calling methods: the ASM macro, and the IntyBASIC native alias. You can use whichever you like, and they both work identically. The example shows the ASM calling method, but if you prefer, you could just as well use the "IntyBASIC Alias" as shown below:

    ' Intialize the PRNG using the IntyBASIC native interface:
    PRNG_Seed($A6145D3E)

Another example is the "RND.GetRangedValue()" macro:

	'   RND.GetRangedValue(out, lo, hi)
	'     Returns a pseudo-random number between "lo" and
	'     "hi," inclusively, advancing the PRNG state.  The
	'     output value is stored in variable "out".
	'
	'     Range arguments can be constants or variables,
	'     and must be in the range of 0 to 255.
	'
	'       Arguments:
	'           out     IntyBASIC variable to store the output
	'           lo      Range lower bound constant or variable
	'           hi      Range upper bound constant or variable
	'
	'   IntyBASIC Alias:
	'       None
	MIN = 1
	MAX = 25
	ASM RND.GetRangedValue(RANDOMVALUE, MIN, MAX)
	ASM RND.GetRangedValue(RANDOMVALUE, 1, 25)

As shown above, you can either call it with constant arguments (which is optimal), or variables. In either case, it will generate the appropriate code, accordingly.

Unfortunately, this is one of those cases where there is no IntyBASIC native calling interface, so you're stuck with the ASM calling method.

Using The PRNG Library

Usage of the PRNG library is pretty straightfoward. The routines in the library are divided into three main functions described below. See the next section for information on the routines available in each category.

Initializing the seed
Before generating any random numbers, you must initialize the PRNG register with an initial seed. The seed can be any non-zero 32-bit value. You must do this once, at the the top of your program, during its initialization.
Generating random numbers
Once the PRNG has been initialized with a seed, it is ready to go. You just call one of the available routines for generating random values, and off you go.

In contrast to the native IntyBASIC RAND() function, the PRNG library advances the internal state on every use. This means you are always guaranteed a new random value on every call. In this way it is closer to how the native RANDOM() function works.
Adding entropy
Pseudo-random number generators in general offer a sequence of values within a particular number space, organized in an apparently random order. Generating new random numbers is a matter of applying a mathematical function to retrieve the next value in the sequence. Although the order may appear random, the sequence itself is deterministic, with the initial seed providing the starting point in the sequence. This means that a program starting from the same seed, will yield identical pseudo-random numbers unless the PRNG is affected in some non-deterministic fashion along the way.

Because of this, it may be useful to occasionally mix things up a bit by altering the internal state of the PRNG. This effect is called entropy, because it introduces some disorder into the system.

The library offers two main ways to add entropy to the PRNG state: You can advance the PRNG sequence periodically on every frame; or you can "corrupt" the internal PRNG register with data read from non-deterministic sources, such as user input, etc. You could also do both in your program for even more entropy.

PRNG Library Reference

Below is a description of all routines offered in the library, for reference. This is taken from the documentation included in the sample program "rand.bas".

Initializing The Seed

RND.Seed(seed)

Spoiler


'   RND.Seed(seed):
'     Seeds the PRNG with an initial 32-bit value.
'
'       Arguments:
'           seed    A 32-bit value to seed the PRNG
'
'   IntyBASIC Alias:
'       PRNG_Seed(seed)
ASM RND.Seed(($0EA7 + ($DEAD * $BEEF)) OR $0D1E)
PRNG_Seed($A6145D3E)

Generating Random Numbers

RND.GetByteValue(out)

Spoiler


'   RND.GetByteValue(out)
'     Returns a pseudo-random number between 0 and 255,
'     inclusively, advancing the PRNG state.  The output
'     value is stored in variable "out".
'
'       Arguments:
'           out     IntyBASIC variable to store the output
'
'   IntyBASIC Alias:
'       RANDOMVALUE = PRNG_GetByteValue
ASM RND.GetByteValue(RANDOMVALUE)

RND.GetRangedValue(out, lo, hi)

Spoiler


'   RND.GetRangedValue(out, lo, hi)
'     Returns a pseudo-random number between "lo" and
'     "hi," inclusively, advancing the PRNG state.  The
'     output value is stored in variable "out".
'
'     Range arguments can be constants or variables,
'     and must be in the range of 0 to 255.
'
'       Arguments:
'           out     IntyBASIC variable to store the output
'           lo      Range lower bound constant or variable
'           hi      Range upper bound constant or variable
'
'   IntyBASIC Alias:
'       None
MIN = 1
MAX = 25
ASM RND.GetRangedValue(RANDOMVALUE, MIN, MAX)
ASM RND.GetRangedValue(RANDOMVALUE, 1, 25)

Adding Entropy

RND.Advance

Spoiler


'   RND.Advance
'     Advances the PRNG state by a single bit, but
'     does not return any useful values. This could
'     be called periodically from the main loop, or
'     from an ON FRAME GOSUB event.
'
'     Range arguments can be constants or variables.
'
'       Arguments:
'           None
'
'   IntyBASIC Alias:
'       PRNG_Advance
ASM RND.Advance

RND.Randomize

Spoiler


'   RND.Randomize
'     Adds entropy to the PRNG by mixing in bits from
'     non-deterministic sources. This should be called
'     occasionally, but rarely, perhaps during the
'     initialization of game phases.
'
'       Arguments:
'           None
'
'   IntyBASIC Alias:
'       PRNG_Randomize
ASM RND.Randomize

BAS_PRNG_ADVANCE

Spoiler


'   BAS_PRNG_ADVANCE
'       Same as RND.Advance, but defined as a native
'       IntyBASIC procedure that can be called from
'       an ON FRAME GOSUB statement.
'
On Frame Gosub BAS_PRNG_ADVANCE

BAS_PRNG_RANDOMIZE

Spoiler


'   BAS_PRNG_RANDOMIZE
'       Same as RND.Randomize, but defined as a native
'       IntyBASIC procedure that can be called from
'       an ON FRAME GOSUB statement.
On Frame Gosub BAS_PRNG_RANDOMIZE

Download The Library

PRNG - BASM Library.zip - Revision #2 (2021-08-15)

Edited August 15, 2021 by DZ-Jay
Updated to revision #2: Added ON FRAME GOSUB wrappers

+DZ-Jay · August 14, 2021

@nanochess,

If you are interested in integrating the library into the compiler as a replacement to the current "RAND/RANDOM" implementation, please let me know what you need. I think the heavy-lifting that the macros do for code generation and optimization for constant or power-of-2 arguments, can be taken up by the compiler without much effort.

Those are the things I could not add to the IntyBASIC integration interface due to lack of access to the compiler or assembler pre-processor. The rest can be just a simple drop-in replacement for procedure "_next_random".

-dZ.

Edited August 15, 2021 by DZ-Jay

+DZ-Jay · August 15, 2021

One more thing about entropy. The utility of the built-in entropy functions is significant for generating even more random numbers.

Consider the "RND.Advance" function, which shifts the internal register by a single bit. Normally, when you get a random number, say a value between 0 and 255, the PRNG register is advanced by 8 bits. Essentially, you get the next 8-bit value in the pseudo-random sequence. By occasionally advancing the internal state by one bit in between your calls to get random values, you disturb this sequence considerably. The "RND.Advance" function is hand-optimized to do this as fast as possible.

The idea is then to advance the internal state of the PRNG an irregular number of times in between your calls, so that the pseudo-random sequence becomes unpredictable.

For example, consider the following code:

' Advance the PRNG by one bit
On Frame Gosub BAS_PRNG_ADVANCE


' Main Loop
Main:
    ' Do your normal gamey stuff here ...

    ' Get a random value
    RandomVal = PRNG_GetByteValue

    ' Do something with random value
    Gosub DoSomething

    ' Do more gamey stuff here ...

    Wait
Goto Main

In the above example, the PRNG will be advanced on every frame. Depending on how long your game loop takes to run, by the time you call the PRNG_GetByteValue function, the PRNG may have been advanced zero or more number of bits.

In that way, you don't necessarily get the next 8-bits in the sequence on every iteration, since the sequence may have been occasionally disturbed.

Ideally, you would advance the PRNG during idle times, like within the "WAIT" loop itself. However, my library has no direct access to that without further hacking the IntyBASIC epilogue itself. If Óscar were to include it in the compiler, it could be done then. Until then, calling on each frame should be sufficient.

The library includes two IntyBASIC native subroutines called:

BAS_PRNG_ADVANCE
BAS_PRNG_RANDOMIZE

These are IntyBASIC wrappers to their assembly language counterparts. This allows them to be used in "ON FRAME GOSUB" statements, since otherwise it doesn't support ASM or DEF FN macro calls.

-dZ.

Edited August 15, 2021 by DZ-Jay

First Spear · August 15, 2021

This needs recognition: THANK YOU!

This brings awesome randomness to everyone, so good it makes my teeth hurt.

Mik's Arcade · December 11, 2021

tagging this for later use

Sign In

Better random numbers in IntyBASIC

Recommended Posts

+DZ-Jay

Link to comment

Share on other sites

+DZ-Jay

Link to comment

Share on other sites

+DZ-Jay

Link to comment

Share on other sites

First Spear

Link to comment

Share on other sites

Mik's Arcade

Link to comment

Share on other sites

Join the conversation

Recently Browsing 0 members

Apps

My Activity Streams

More