Group Project 4: Random Number Generation

In this assignment you’ll use the bitwise operations, shifts, and rotates to implement the xoroshiro64** pseudo-random number generator. See http://xoshiro.di.unimi.it/ for the details on how it works, or read ahead for a description of the algorithm.

xoroshiro64** uses 64 bits of internal state, while generating 32-bits of random output per call. It’s internal state is split into two unsigned 32-bit values, s[0] and s[1]. These must be initialized to something other than 0s. To generate the next state in the RNG sequence, we perform run the following algorithm:

uint32_t next(void) 
{
    uint32_t s0 = s[0];
    uint32_t s1 = s[1];
    const uint32_t result = rol(s0 * 0x9E3779BB, 5) * 5;

    s1 ^= s0;
    s[0] = rol(s0, 26) ^ s1 ^ (s1 << 9); // a, b
    s[1] = rol(s1, 13); // c

    return result;
}

where rol(x,n) means rotate x left (logical, not arithmetic) by n bit positions.

All arithmetic is performed unsigned, on 32-bit (dword) values. You can find the above C/C++ implementation of the algorithm here. Note that because C/C++ do not expose bit rotations as an operation, the authors had to implement it manually as a function!

Here is a scaffold you can use to get started:

;;;; 
;;;; xoroshiro64.s
;;;;
section .data

s0:         dd      137546 
s1:         dd      729 

buffer:     dd      0            

section .text

global _start
_start:

    push rbp
    mov rbp, rsp

.loop:

    call next
    mov dword [buffer], eax ; Return value from next in eax

    mov rax, 1          ; Write syscall
    mov rdi, 1          ; Stdout
    mov rsi, buffer     ; Address 
    mov rdx, 4          ; Length
    syscall

    jmp .loop

    pop rbp

    mov rax, 60
    mov rdi, 0
    syscall

next: 
    ; Next function here. 




    ; Return results in eax.
    ret 

You shouldn’t run your executable directly to test it, as it will just print a bunch of garbage to the screen. (Use the command reset to clear the screen if you need to.) Instead, send its output to the RNG_test utility, installed on the server:

./xoroshiro64 | RNG_test stdin

That will continuously run statistical tests on the output of your program, telling you how “random” it’s output appears to be. (If the output is not random at all, RNGTest will quit with an error message.)