[Question]
  [
# Introduction
Super Mario 64 has a heavily overcomplicated RNG, ably explained [here](http://youtu.be/MiuLeTE2MeQ) 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:
\begin{equation}
\text{rng}(a):= \text{let } \begin{array}{l} b = 256a\_L \oplus a \\
 c = 256b\_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.
\end{equation}
# Example input and output
The number just before an arrow should be taken to the number just after it, so \$f(1789)\$ should be \$0\$, and \$f(0)\$ should be \$57460\$.
\$22026\$ and \$58704\$ map to each other.
```
12567 -> 60400 -> 1789 -> 0 -> 57460 -> 55882 -> 50550
64917 -> 43605 -> 21674 -> 46497 -> 45151
22026 <-> 58704
```
# Rules
Shortest code wins.  
[Standard loopholes](https://codegolf.meta.stackexchange.com/questions/1061/loopholes-that-are-forbidden-by-default) apply.
  
[Answer]
# 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!](https://tio.run/##ZVFfT8MgHHwun@JnjQlsnWk3p8tqfTHZmy8@mThdGKUthlJT2kmz7Ktbwbn57@UXuDvuDmCjnLG@PxWKyTblcK2bVFTnxQ36BUmx/ovVQuX/dEI1DkOrFW2sYt02fLXCOKO6YVRKQsAqIMNuUhIjqkvA9z5G2dwrqw1wagLgzCDPVDXQIgAq7ZoV@XGji3ovi5D3ohjoL61FQjOLZuFzaKLF4gLp@Q9isfgm9rAMgFm7mjeI@LYKcp1KKtS@XJ0zKyhoDYOB3WwI2iLPMQYSiMbTy6sAuhh5aQWv9imaDPtnAvwATJJhQ0gMb4WQHLCBkwSm4XQa2hAPeQf1Ut1RVgjFgVUpn7sKnvMO96bbgw7OwvGD9e0SjFulRa54@llsQDLyaIbDJxLvDmGdCwvN7cS5HR2wbbbuGq7JUrmGjrT3bmvl0nao799ZJmmu@1E5GdthvyWxZ7n8AA "C (gcc) – 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.
[Answer]
# JavaScript (ES6), 45 bytes
```
n=>(q=n>>8^(n&=255))/2^n<<7^n^57460^q%2*40564
```
[Try it online!](https://tio.run/##JcrBjoIwGATgu08xl9XWAGKlRYPtbZ@CtEmDICr5q6JejM@O3extvpk5@5cfm/vp@kgpHNqp0xNpw26ajNk6RnMtpOR8JRzt96UjJ8tC5e72I5ZFLlUxVTVqrIVUZYISNolSxW4dJf8lRC5Ugg0s7Czrwv3XNz1jNSjBBZZDG7xnwNA@4KFR2yoq/liFS5pWoFh2jDiHz67PsY/x79EEGsPQZkM4Mp@dw4nYAqnBgsf5w6cv "JavaScript (Node.js) – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~34~~ ~~23~~ 22 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
₁‰`Ðr^‚₁β2‰`Ž$×*Žâ∊α^^
```
-12 bytes thanks to *@CommandMaster*
[Try it online](https://tio.run/##yy9OTMpM/f//UVPjo4YNCYcnFMU9apgF5J3bZAQSOLpX5fB0raN7Dy961NF1bmNc3P//hkamZuYA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfeX/R02Njxo2JByeUBT3qGEWkHdukxFI4OhelcPTtY7uPbzoUUfXuY1xcf91/kcbGpmameuYGZgYGOgYmltY6hjomJqbmAFJUwsLIx0zE0tDcx0TYzMDUx0jQzNzEx0ToJC5jpGRgZGZjqmFuYFJLAA).
**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?*)](https://codegolf.stackexchange.com/a/166851/52210) to understand why `Ž$×` is `25204` and `Žâ∊` is `57460`.
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~53~~ 52 bytes
```
q;f(n){q=n>>8^(n&=255);n=q/2^n<<7^n^57460-q%2*'bt';}
```
[Try it online!](https://tio.run/##fVBhb4IwEP3ur7iQOEEhlkoBg/hl2a@YkLhaHNlWhTYZmeGvj53Qkblka9L2@u7de73j3pHzrquSwpbOpUrldhvntrxLKWNOItNqSXO52US5zFkUhMSrpnQ@e9KzpO1KqeFtX0rbgcsEcF0BLZRWjxmkcPEpCyMXQhIQ4oIfxWsXMOh18GJxTDEbrH0kBauQMBeoH0YBvhBFkFJCQ2TGEQnaZLQQzVlwLQ6Dy//yjDBG/pAPmM98I2/MjAs/SaWBP@/rOZ6Cv4h6MLN2zQPdNet73Mxy4ed7ZZnq4lSDff1oKQ@iwTKSmHADqvwQp8L@bsFZGmA@IgksFj3b6cWGyY7TRbVhwj0lS26yCrOFrZ1bVCA6jux32blGSmFb0wN4W8BzqnYSG9MuKHfsXaWpyIxsO2m7T1687o@q896/AA "C (gcc) – Try It Online")
*Saved a byte thanks to [ceilingcat](https://codegolf.stackexchange.com/users/52904/ceilingcat)!!!*
Port of [Arnauld](https://codegolf.stackexchange.com/users/58563/arnauld)'s [JavaScript answer](https://codegolf.stackexchange.com/a/250175/9481).
[Answer]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), 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!](https://tio.run/##RY69CsJAEIT7eY2scsnBsZO/i6BY@hIisbCwsRC7mGc/9xLFLWZh9tthnrfX/XFNG3caU/BgL5XKVir40dGXZ0K8QgkiVC5Mw1yuCqmFcMf9gWGK5vLttDS7qEEBqUp@VW3h4tbHhQ45VibOC5Lnh/mRxrH7J6pQisYKWAu75jZWJ6VeW@MZhx3aptcO3RC1/QA "Retina 0.8.2 – Try It Online") Link includes less slow test cases. Explanation:
```
.+
16$*0$&$*
```
Convert to unary, but also prefix 16 `0`s, 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!](https://tio.run/##RY07TgNBEETzuoYba3ZGanWN52cJyyGXQGYJCEgIgGy9PhYH4GLLrA2ig2qp9Pr1@8vn69szlzv3MC4awOJNtp4Io2MYHgmZOBuMINQ7ndo83BIShXDH@wN1qr3l2dnQ600EBaQZ@ZvWF07udniltYvjbKv9Cq3zB4aPkR1l/peaUDY7qDsenPr1i9KLi@IH2Yp/wmU8QcP3l4i6ZWHMpaJY6jbWtoch11R65tYiStqzIu2KZUSWmpB6VRGjxYLcqqUf "Retina – Try It Online") Link includes test cases.
[Answer]
# [MIPS III](https://n64brew.dev/wiki/MIPS_III_instructions), ~~68~~ ~~60~~ ~~52~~ 48 bytes
```
308800ff
00044a02
01285026
00085a00
016a5825
000b1042
00481026
316c0001
15800000
38429e74
03e00008
38427e00
```
Source:
```
rng:                                    # a0 = seed     
        andi    $t0, $a0, 0xFF          # s_lo
        srl     $t1, $a0, 8             # s_hi
        xor     $t2, $t1, $t0           # s_lo ^ s_hi
        sll     $t3, $t0, 8             # s_lo << 8
        or      $t3, $t3, $t2           # c = (s_lo << 8) | (s_lo ^ s_hi)
        
        srl     $v0, $t3, 1             # c / 2
        xor     $v0, $v0, $t0           # xor with s_lo
        
        andi    $t4, $t3, 1             # c odd
        bne     $t4,  $0, exit          
exit:   xori    $v0, $v0, 0x9E74        # xor twice if branch taken, eff. nop
                                        # 7E00 ^ E074
        jr      $ra
        xori    $v0, $v0, 0x7E00             
```
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](https://student.cs.uwaterloo.ca/%7Eisg/res/mips/opcodes)) and requiring unintuitive instruction re-ordering to not waste branch delay slots. 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](https://github.com/n64decomp/sm64/blob/1372ae1bb7cbedc03df366393188f4f05dcfc422/src/engine/behavior_script.c#L39-L66).
-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.
-8 bytes from being smarter about `c` calculation thanks to m90.
-4 bytes from [rearranging instructions](https://n64brew.dev/wiki/MIPS_Assembly#Branch_Delay_Slot) to avoid a `nop` in the return jump branch delay slot. Here the control flow is weird: the branch (with offset 0) to a label at the delay slot causes the xor instruction to be executed twice if the branch is taken, once as part of the delay slot and again after branching, acting effectively as a no-op. AFAICT this is the intended behavior (at least supported by the MARS simulator).
[Answer]
## 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.
[Answer]
# [Python](https://www.python.org), 55 bytes
```
lambda n:(q:=n>>8^(n:=n&255))//2^n<<7^n^57460^q%2*40564
```
[Attempt This Online!](https://ato.pxeger.com/run?1=LY1BDoIwFETXeoofE02rIFhpi41wEWwTjKI1-tGKiZ7FDYnRO3kbIbia9xYz8_ycH9W-xPpVJKv3rSr8-CuP-Wm9yQEVuagE0zQ2BBsYMc4pDQJmcLmUBg2XkQjNZcjGUchF9K_fitKB9RAsQpbBjHEhPZCgPchARItZY7wzxkImPJiD1qrfOzuLFRmAn8JgeigtkuxaOWKpnnSgkqIxCu3BvZ13Oe62BKmmtDuv6y5_)
I'm late to the party, but yet another port of @Arnauld's JavaScript answer.
[Answer]
# SM83/Z80, 24 bytes
Input in `bc`, output in `bc`.
```
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
    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 (and taken jumps go to the place two bytes before they should). But after some fixing of the Javascript, it can be tested!
[Answer]
# [Rust](https://www.rust-lang.org/), ~~141~~ ~~90~~ ~~79~~ ~~75~~ 74 bytes
Saved 67 bytes thanks to [@ceilingcat](https://codegolf.stackexchange.com/users/52904/ceilingcat)
---
Golfed version. [Try it online!](https://tio.run/##rVDBcoIwFLz7Fa/OtIMO1CQlAYt66xf02NEO0oiZQmQg1HaQb6ePoON46K05JO/t2@xuUtaV6XYa8lhpZwLNCCCTBkqdwhK6U14b0M81FSdvhXujN0t9z7hYLMJID@WUbfRjdYyL9@2PkZUzifSMbXjgC@IhYco4I37bRagMMJvBy3ecF5mEuopTCUdl9pCqL6lB6aI2laX1EYaWYow3ijaBC4L4hLhAg3DuAhbWAw8ehgwPwjlZRwBWYXco4cFKoNC5QrHGDvtVlEqbTN8546YFbwVNO3YHT7d/vWPLyWSI3Y5urpzRa0rWpxT@nGJK/0kQ7gKjIvCxQ7QHOeV0Hf0djf1vNPzn10ImKs4giSsJ5gDJXiafsFXehyplYtRB4zCPi0Lp9FZjzBhhAhYX697TQhfPK5OHAfFvmRbqmW33Cw)
```
|mut n:u16|->u16{n^=n%256<<8;n=n%256*2^n.swap_bytes();n/2^57460-n%2*25204}
```
Ungolfed version. [Try it online!](https://tio.run/##rVJNj5swEL3nV7zNYRUkorUpELYkuTXXSu2lUrUrETBglRgUO5ut0vz2dIzzQar2Vi62Z96892aY7U6b06lU2KpqstkZSNXtzEfseOxhurQnDiPQ1wgDC9Csz6bXoObnQB/RDAtMehY8gr2vVh7mcyQpnp6ga1kaNO0e659GwLSoZVVf6l4XTt1ROwriosyQCL8GIcY8LJcX9n3WIZmupUGdNW9CDwzdk3C8DqU0JwghiMlmLCxhZxcl@lKOhwUYDrBCheiEKqSq0CqbbosC7RbiTSgf3z5/wV6amnICbYkAeau0yZRxfoa9aSeXcJJDnz1CNFqcR/4XKF@twgv0NqbRcTSif7jJpJp4rpZsfnrPNl0jsNNZJZynSpJHV6OvP9A97Qy@8yCKZz5iFjLmg8@SZx90iWZhbI8oSQI6WBSxlxTORkmdPzqXUp1vRHbroNtKZRr1MBkfjnalDsex7zT9fuv6q@elg6auJV76h8vAuozDZ04uww8xi3wEPJ6F9KKoDUY84i/pv60F/9cazflrJ3KZNcgz3e90Xov8B9ZyWsityI1sFSU3WdfRxtxzjIOABTHmF2mr2YcumjdklMxYeI/sQxZ5PJ1@Aw)
```
fn rng(mut input: u16) -> u16 {
    let mut s0: u16;
    let s1: u16;
    s0 = (input & 0xFF) << 8; // shift low byte to high
    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 != 0 {  // depending on s0 odd or even, XOR with one of 2 constants
        input = s1 ^ 0x8180; 
    } else {
        input = s1 ^ 0x1FF4; 
    }
    input
}
fn main(){
    // Example usage with given inputs
    let inputs1 = [12567, 60400, 1789, 0, 57460, 55882, 50550];  
    for &input in &inputs1 {
        println!("{} -> {}", input, rng(input));
    }
    println!();
    let inputs2 = [64917, 43605, 21674, 46497, 45151];
    for &input in &inputs2 {
        println!("{} -> {}", input, rng(input));
    }
    println!();
    // Special case to check bi-directional mapping
    println!("22026 <-> {}", rng(22026));
    println!("58704 <-> {}", rng(58704));
}
```
[Answer]
# [Perl 5](https://www.perl.org/) `-p`, 51 bytes
It's a direct port of [Arnauld's Javascript answer.](https://codegolf.stackexchange.com/a/250175/72767)
```
$_=($t=$_>>8^($_&=255))/2^$_<<7^$_^57460^$t%2*40564
```
[Try it online!](https://tio.run/##NY5BDsIgEEX3XENswKQ6QxlAA/UEXgFWLkwa2ygbE88ugqmbn5@8efmzXB8TlcJTEDwHnsbRRcFTFxSRlAcVefLe1oxktYHI81btNJDRZbNKQvBXaE5TvHf1WK4dY4N/8G7dkHIg64ysgdGQhraYOzwPA5I6Oay8oCJjmQENwNC6IwP2e4AROac@85Jv8/1Z@gvtAaH0y/QF "Perl 5 – Try It Online")
]