# Introduction

Super Mario 64 has a heavily overcomplicated RNG, ably explained here by Pannenkoek.

I thought it might be interesting to implement it.

# Challenge

Implement the RNG function, except for the two special cases. (Not part of the below description; everything below is what you should implement.)

Input and output are both 16-bit integers.

The standard C implementation is as follows. & is bitwise-AND, ^ is bitwise-XOR. Shifts have higher precedence than bitwise operations, so (s0 & 0xFF)<<1 ^ input does the left-shift before XORing with input.

rng(input) {
s0 = (input & 0xFF) << 8;                       // shift low byte to high
s0 = s0 ^ input;
input = (s0 & 0xFF) << 8 | (s0 & 0xFF00) >> 8;  // swap 8-bit halves
s0 = (s0 & 0xFF) << 1 ^ input;
s1 = s0 >> 1 ^ 0xFF80;
if(s0 & 1) input = s1 ^ 0x8180;              // XOR with one of 2 constants
else       input = s1 ^ 0x1FF4;              // depending on s0 odd or even
return input;
}


In math notation, where $$\\oplus\$$ is bitwise XOR and $$\x_L\$$ is $$\x\$$ mod 256:

$$$$\text{rng}(a):= \text{let } \begin{array}{l} b = (256\times a_L) \oplus a \\ c = (256\times b_L) \oplus \lfloor b/256 \rfloor \\ d = 32256 \text{ if c odd, } 57460 \text{ otherwise}\end{array} \text{ in } b_L \oplus \lfloor c/2 \rfloor \oplus d.$$$$

# Example input and output

Any given start point for a PRNG leads to a sequence of random numbers if you do seed = rng(seed). These are the starts of some sample sequences. And one seed that ends up bouncing between two numbers.

12567 -> 60400 -> 1789 -> 0 -> 57460 -> 55882 -> 50550
64917 -> 43605 -> 21674 -> 46497 -> 45151
22026 <-> 58704


# Rules

Shortest code wins.
Standard loopholes apply.

• challenges should be self contained; a youtube link and sample implementation aren't a substitute for a solid spec. Make sure you're sandboxing challenges to catch stuff like this ahead of time. Jul 22 at 0:40
• I'd suggest rewriting the spec to be slightly less "C", to make it a little more agnostic. For example, removing the types would make it a lot simpler to understand, without significantly detracting from the code. As would outright removing the commented lines - if it doesn't need to be implemented, don't even include it in the spec Jul 22 at 0:53
• I can't read that specification. Could you please re-state it in either English or mathematical formulas?
Jul 22 at 8:00
• I also can't read that specification, but also not mathematical formulas. Could you re-state it in English, please? Jul 22 at 10:17
• What is unreadable about the C code? most languages use similar operators
– qwr
Jul 22 at 23:08

# x86 32-bit machine code, 21 bytes

89 C8 30 C4 86 C4 D1 E8 73 04 66 35 74 9E 66 35 74 E0 30 C8 C3


Try it online!

Uses the fastcall calling convention – argument in ECX, result in EAX.

In assembly:

f:  mov eax, ecx
xor ah, al
xchg ah, al
shr eax, 1
jnc s
xor ax, 0x8180^0x1FF4
s:  xor ax, 0xFF80^0x1FF4
xor al, cl
ret


Simplifications used:

• The XOR constants are combined.
• The << 1 cancels out with the later >> 1.
• The check s0 & 1 is the same as the bit shifted out by the >> 1.

# x86 16-bit machine code, 18 bytes

89 C8 30 C4 C1 C8 09 73 04 35 74 1E 35 74 E0 30 C8 C3


In assembly:

f:  mov ax, cx
xor ah, al
ror ax, 9
jnc s
xor ax, 0x8180^0x1FF4^0x8000
s:  xor ax, 0xFF80^0x1FF4
xor al, cl
ret


Compared to the 32-bit program, this one saves two bytes by not needing operand-size prefixes.

One more byte is saved by combining the "swap bytes" and "shift right by 1" parts into a rotation right by 9 bits. This leaves [the bit that the original program would shift out] at the top of the register instead; fortunately, that is the same bit that is used to choose between the XOR constants, so it can be corrected for by adjusting those constants.

• Nice. I found it non-obvious how the shift-cancelling worked, but I think the idea is that the 8-bit s0&0xFF gets left and right shifted as part of something extended to 16-bit, so we're not knocking bits off either end of it. After separating out the XORing, there's still a input >> 1 that does need to happen as part of s1 = s0 >> 1 ^ 0xFF80;, and that's what the shr is doing. (As well as setting CF= low bit of s0, since after that point in the source we only need s1 which involves input>>1) Jul 22 at 15:06
• I wonder, would 8080 or 8086 machine code (16-bit) result in even shorter code? Sep 29 at 20:30
• @NoLongerBreathedIn Indeed it does. Added.
– m90
2 days ago

# JavaScript (ES6), 45 bytes

n=>(q=n>>8^(n&=255))/2^n<<7^n^57460^q%2*40564


Try it online!

# 05AB1E, 3423 22 bytes

₁‰Ðr^‚₁β2‰Ž$×*Žâ∊α^^  -12 bytes thanks to @CommandMaster Explanation: 05AB1E lacks bitshift builtins, so instead we'll use modulo/multiply where applicable. ₁‰ # Divmod the (implicit) input-integer by 256 # (since the input is guaranteed to be a 16-bit integer)  # Pop and push both the quotient and remainder to the stack Ð # Triplicate the remainder r # Reverse the stack from q,r,r,r to r,r,r,q ^ # Bitwise-XOR the remainder and quotient together ‚ # Pair the r and r^q together ₁β # Convert it from a base-256 list to a (base-10) integer 2‰ # Divmod it by 2  # Pop and push quotient and remainder separated to the stack Ž$×       # Push compressed integer 25204
*      # Multiply it to the remainder
Žâ∊   # Push compressed integer 57460
α  # Take the absolute difference of the two values
^ # Bitwise-XOR it to the quotient
^            # Bitwise-XOR it to third remainder-copy that was still on the stack
# (after which the result is output implicitly)


See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ž$× is 25204 and Žâ∊ is 57460. • I don't believe *256 should be to the quotient - quotient*256+remainder is the original number. 27 bytes by not calculating s1 Jul 22 at 8:59 • 23 bytes by adding to that a more efficient method of calculating the first part Jul 22 at 9:29 • @CommandMaster Thanks for the golf. After seeing m90's I had the feeling my port of the original C-code implementation could be simplified. Jul 22 at 11:00 • This solution is actually wrong - the в has to be ‰, otherwise it fails on numbers between 1 to 255 Jul 22 at 16:28 • 22 bytes Jul 23 at 12:04 # C (gcc), 53 bytes q;f(n){q=n>>8^(n&=255);n=q/2^n<<7^n^57460^q%2*40564;}  Try it online! Port of Arnauld's JavaScript answer. # Retina 0.8.2, 173 bytes .+ 16$*0$&$*
+(1+)\1
$+0 01 1 .*(.{8})(.{8})$2$1 (?<=1.{7})(1|(0))$#2
1$11001111001110100 ^((.{8}).{7}).$+0${1}1110000001110100 +1(.{15})(1|(0)) 0$1$#3 1 01 +10 011 1  Try it online! Link includes less slow test cases. Explanation: .+ 16$*0$&$*


Convert to unary, but also prefix 16 0s, so the binary value below has at least 16 digits.

+(1+)\1
$+0 01 1  Convert to binary. .*(.{8})(.{8})$2$1  Swap the bottom eight bits with the next eight, and discard any remaining zeros. (?<=1.{7})(1|(0))$#2


XOR the top eight bits into the bottom eight bits, i.e. toggle any digit seven digits after a 1.

1$11001111001110100  Append 0x8180 ^ 0x1FF4 if the value ends in a 1. ^((.{8}).{7}).$+0${1}1110000001110100  Replace the value with two copies shifted eight bits and one bit right and also append 0xFF80 ^ 0x1FF4. +1(.{15})(1|(0)) 0$1$#3  (Destructively) XOR all of the values together. 1 01 +10 011 1  Convert to decimal. Note that this takes O(n²) time, which makes the test cases take up to 25 seconds each on TIO, so I've also written a Retina 1 port but using fast binary to decimal conversion: Try it online! Link includes test cases. • You didn't have to use decimal I/O. I'd have suggested hexadecimal. Sep 28 at 17:43 • @NoLongerBreathedIn Retina only has built-in base conversions between decimal and unary. You can slowly do base conversions for bases in between that use decimal digits as I have done here, but It will really struggle with bases higher than 10; the best I could do for hexadecimal to binary is a whopping 75 bytes, that compares to 30 for decimal to binary. – Neil Sep 28 at 18:49 • That's amazing, given that hex to binary is just "s/0/0000/; s/1/0001/; s/2/0010/" etc. Sep 29 at 20:27 • @NoLongerBreathedIn Each substitution is 2 bytes (newlines) plus 1 byte (digit) plus 4 bytes (bits); multiply that by 16 and you get a total of 112 bytes. – Neil Sep 29 at 20:40 • Heck, I'd even be willing to allow binary I/O. 17 hours ago # MIPS III, 68 60 bytes 308800ff 00084200 00884026 00084a02 310a00ff 000a5a00 01695825 000b1042 004a1026 316c0001 15800002 38427e00 38429e74 03e00008 00000000  Assembly: rng: # a0 = seed andi$t0, $a0, 0xFF sll$t0, $t0, 8 xor$t0, $a0,$t0           # b = seed xor shifted seed_lo

srl     $t1,$t0, 8             # shifted b_hi
andi    $t2,$t0, 0xFF          # b_lo
sll     $t3,$t2, 8             # shifted b_lo
or      $t3,$t3, $t1 # c = swap b hi and lo bytes srl$v0, $t3, 1 # c / 2 xor$v0, $v0,$t2           # xor with b_lo

andi    $t4,$t3, 1             # xor branch based on c odd
bne     $t4,$0, exit
xori    $v0,$v0, 0x7E00

xori    $v0,$v0, 0x9E74        # xor const combines delay slot
exit:
jr      $ra nop  Well I had to, didn't I? Even if MIPS is a terrible golfing language as far as assembly languages go, due to every single instruction being 4 bytes (wasting instruction encoding bits) and wasting even more due to branch delay slots (silly 8 bytes to return, though no return is necessary if code snippets are allowed). It still beats out whatever actually was on the game ROM since I didn't have all of the mentioned Nintendo's extraneous / unreachable code. -8 bytes from combining left and right shifts as in the math notation in the question. Also rewrote the comments to be much easier to follow. • Nintendo 64 uses MIPS, and a rabbit in the game is called MIPS Jul 23 at 20:49 • Yeah, I said so in my code discussion – qwr Jul 23 at 21:23 • The calculation of $t2 is the same as the first calculation of $t0; reusing the value should save one instruction. I think another instruction can be saved by, instead of shifting and XORing seed_lo into the high part, waiting until after swapping the bytes, at which point it can be XORed into the low part without a shift. – m90 Jul 29 at 10:29 ## Batch, 58 bytes @cmd/cset/a"q=%1>>8^(n=%1&255),q/2^n<<7^n^57460^q%%2*40564  Another port of @Arnauld's JavaScript answer. # Python, 55 bytes lambda n:(q:=n>>8^(n:=n&255))//2^n<<7^n^57460^q%2*40564 Attempt This Online! I'm late to the party, but yet another port of @Arnauld's JavaScript answer. # SM83/Z80, 24 bytes Input in bc, output in bc. (For Z80, change the 8th byte to 0A; this is because Z80 jr is measured from just before the instruction and SM83 jr is measured from just after). 79 A8 41 CB 19 1F 38 08 EE 74 F5 80 EE 9E 4F F1 A8 41 4F 78 EE 7E 47 C9  Explanation and disassembly: First, here's the pseudocode I used for this. s0 = r << 8; s0 ^= r; r = swab(s0); // A s1 = r & 1; r >>= 1; // B if(!$1) r ^= 0x9E74;
r ^= s0 & 0xff          // C
r ^= 0x7E00             // D


Now the assembly:

sm64rng:
;; r starts in bc
ld a,c          ;; 79
xor b           ;; A8
ld b,c          ;; 41
;; now s0 in ab, r in ca, after line A.
rr c            ;; CB 19
rra             ;; 1F
;; now s0 & 0xff in b, r in ca, s1 in cf, after line B.
jr c, ifodd     ;; 38 08/0A
xor $74 ;; EE 74 push af ;; F5 ld a,c ;; 79 xor$9E         ;; EE 9E
ld c,a          ;; 4F
pop af          ;; F1
ifodd:
;; now s0 & 0xff in b, r in ca, before line C.
xor b           ;; A8
;; now after line C.
ld b,c          ;; 41
ld c,a          ;; 4F
ld a,b          ;; 78
;; r now in ac
xor \$7E         ;; EE 7E
;; now after line D
ld b,a          ;; 47
;; r now in bc
ret             ;; C9


Note that this doesn't work on Z80studio, because the bit instructions are currently badly broken and rr c doesn't work properly, because it messes up the flags. But after some fixing of the Javascript, it can be tested!