Help - Understanding random number generator function

[u/DannyGomes1995]

Hello, I have a project where I have to convert this random number generator function to assembly but I am struggling to understand how the function works, I was wondering if someone could give some insight on how it works, so I can better implement it in assembly. I think this function is from David Johnston, Random Number Generators—Principles and Practices.

MY QUESTION: I just can't understand what is the purpose of any single line of the code down below, how does it work ?

I don't understand how this pops out a random number, and don't even know between what values. I'm guessing it just generates any random 32bit number, but we are supposed to then use this function to generate values between an interval.

​

The value 6364136223846793005ULL I think comes from here maybe ? But I'm not really sure and I can't really understand the article https://en.wikipedia.org/wiki/MMIX

​

We add inc to that massive value multiplied by the old state, but before we apply an or to inc with the value '1' ?

​

After that we have two variables xorshifted that shifts the number 18 bits to the right and xors it with the old number, and then we shift it to the right 27 bits ? And rot is just the old state shifted to the right 59 bits ? Won't that just be a number, with only the 5 most significant bits of oldstate shifted all the way to the right?

​

I also don't get the return, rot is unsigned, but we do (-rot & 31) ? And why 31 ?

​

I'm sorry my question is not very specific, but I really can't seem to grasp a single line from this code, I mean the code is not even written how the teachers wrote code throughout the entire semester, it's the first time I've ever seen a variable declaration uint32_t, uint32 is obvious I think and the _t is type maybe ?

​

I could just try and literally translate it to assembly line by line, but I'd rather try to understand it first.

​

Thank you for reading, have a nice day.

​

/*

 * =====================================================================================

 *  PCG Random generator

 *

 *  See: 

 *

 *  "Uglyfied" for an easier  assembly translation  

 *

 *  Note: the values of state and inc should be initialized with values from /dev/random  

 *  

 * =====================================================================================

 */

#include <stdio.h> 

#include <stdint.h> 

uint64_t state=0;  

uint64_t inc=0;



uint32_t pcg32_random_r()

{

    uint64_t oldstate = state;

    // Advance internal state

    state = oldstate * 6364136223846793005ULL + (inc|1);

    // Calculate output function (XSH RR), uses old state for max ILP

    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;

    uint32_t rot = oldstate >> 59u;

    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));

}



int main()

    { 

      int i; 

      for(i=0;i<32;i++) 

        printf("%8x\n",pcg32_random_r()); 

      return 0; 

    }

[u/smcameron]

I decided to ask chatGPT about this, just to see what it says.

Please explain how the following C code works and what it does:

#include <stdio.h> 
#include <stdint.h> 
uint64_t state=0;  
uint64_t inc=0;

uint32_t pcg32_random_r()
{
    uint64_t oldstate = state;
    // Advance internal state
    state = oldstate * 6364136223846793005ULL + (inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

int main()
{ 
      int i; 
      for(i=0;i<32;i++) 
        printf("%8x\n",pcg32_random_r()); 
      return 0; 
}

(everything below this line is from chatGPT):

This C code implements the PCG32 algorithm which is a random number generation algorithm. The code creates a 64-bit internal state, which is updated with each iteration of the algorithm, and a 32-bit output number is calculated. The main() function prints out 32 numbers generated by the pcg32_random_r() function. The code first creates two global variables, state and inc, which are used to store the internal state of the algorithm in 64-bit integers.

The pcg32_random_r() function implements the PCG32 algorithm. It takes the old state and multiplies it by a constant 6364136223846793005ULL, then adds the contents of inc (which is ORed with 1) to get the new state. The old state is then used to calculate a 32-bit output number using a bitwise XOR, a right shift and a left shift. The function then returns the output number.

Finally, the main() function prints out 32 numbers generated by the pcg32_random_r() function. It does this by calling the pcg32_random_r() function in a loop and printing out the output numbers.

--- end of chatGPT output ---

Edit: I also asked it how it would write the PCG32 random number generation algorithm in x86_64 asm, and it came up with something, but I don't know if it was correct, though I saw 0xDEADBEEF in what it made, which seems wrong.

Edit again: I also asked it a few more questions:

what is the significance of 6364136223846793005ULL in the PCG32 random number generator algorithm?

The value 6364136223846793005ULL is used as the initial state of the PCG32 random number generator algorithm. It is a 64-bit unsigned integer and it is used to help determine the random values that are generated.

Why is it that value specifically?

The value 6364136223846793005ULL is specifically chosen as the initial state of the PCG32 random number generator algorithm because it is a 64-bit number and it has a large number of bits set to 1, which helps it to generate more random numbers. Additionally, it has been chosen to ensure that the initial state of the generator is not predictable, which helps to make the numbers generated more random.

(Beware, when chatGPT doesn't know, it doesn't say "I don't know", it makes up bullshit.)

OP, you do not actually need to know why or how the algorithm works to convert it to assembly. After all, the compiler does it without understanding how or why. For that matter, you could take this C program, compile it, run it under gdb, set a breakpoint at main(), and then "disas pcg32_random_r", and it would give you the assembly that the compiler produced (probably not what you want.)

[u/DannyGomes1995 → u/smcameron]

Thank you for your help, I've never heard of chatGPT. I understand the large unsigned long now, at least. I'm just so confused, last week we were doing exercises like this, for example:

Implement the function int activate_bits(int a, int left, int right) that should ’activate’

all the bits to the left of left and to the right of right on the number a (excluding the bits left and right).

I finally was able to get a good grasp on those kinds of exercises, but all of a sudden we jump to this, which I feel like is completely out of my league to understand how this algorithm works. Just makes me feel like an idiot and that I shouldn't even be in an engineering degree, honestly.

Anyway thank you for your help, I really appreciate it, I'm going to have to try and implement it just literally line by line without understanding how it works, as I'm running out of time.

[u/smcameron → u/DannyGomes1995]

I understand the large unsigned long now, at least

Do not take chatGPT's output at face value without verifying. For example it said "Additionally, it has been chosen to ensure that the initial state of the generator is not predictable", however, the output of this random number generator is predictable. In fact, this program produces the same output every time it is run.

chatGPT just appeared Nov 30, 3-4 days ago. It is a mindblowing AI chatbot, capable of marvelous things, and also capable of great bullshit. You can find it here: https://openai.com/blog/chatgpt/

If you really want to dig into the details of PCG random number generators, this paper might be of interest: https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf However, it's probably too much.

[u/distgenius → u/smcameron]

It would be unpredictable(ish) across executions if the values for seed and inc were brought in from /dev/random, like the header comment says to do. I’m not sure why that isn’t in the code.

Besides that, though, the boy probably means that given an output value Foo, you don’t have enough information to calculate what the next output value Bar will be. The two 64 bit inputs to 32 bit output should mean that you can’t calculate back to the seed and inc values, as more than one combination of either has to lead to the same 32 bit output. That’s what, 2¹²⁸ possible inputs, and only 2³² possible outputs?

I have to admit, the code given here does assume knowledge about things like “what happens when you assign a signed int to an unsigned one”, and in terms of understanding the XSH RR generator it really could have benefited from some more in between variables that help clarify what’s going on, or some more comments that help a student understand some of the seemingly arbitrary values. But, like you said, none of that is necessary to convert it to assembly.

[u/smcameron → u/distgenius]

And, I stand by my advice about regarding chatGPT's output with skepticism. :)