1.23. LINEAR CONGRUENTIAL GENERATOR

; the LI instruction is coalesced by IDA from LUI and ORI
li $a0, 0x3C6EF35F
addu $v0, $a0
; store to rand_state:
sw $v0, (rand_state & 0xFFFF)($v1)
jr $ra
andi $v0, 0x7FFF ; branch delay slot

Wow, here we see only one constant (0x3C6EF35F or 1013904223). Where is the other one (1664525)?

It seems that multiplication by 1664525 is performed by just using shifts and additions! Let’s check this
assumption:

#define RNG_a 1664525

int f (int a)
{
return a*RNG_a;
}

Listing 1.323: Optimizing GCC 4.4.5 (IDA)

f:
sll $v1, $a0, 2
sll $v0, $a0, 4
addu $v0, $v1, $v0
sll $v1, $v0, 6
subu $v0, $v1, $v0
addu $v0, $a0
sll $v1, $v0, 5
addu $v0, $v1
sll $v0, 3
addu $a0, $v0, $a0
sll $v0, $a0, 2
jr $ra
addu $v0, $a0, $v0 ; branch delay slot

Indeed!

MIPS relocations

We will also focus on how such operations as load from memory and store to memory actually work.

The listings here are produced by IDA, which hides some details.

We’ll run objdump twice: to get a disassembled listing and also relocations list:

Listing 1.324: Optimizing GCC 4.4.5 (objdump)

objdump -D rand_O3.o

...

00000000 :
0: 3c020000 lui v0,0x0
4: 03e00008 jr ra
8: ac440000 sw a0,0(v0)

0000000c :
c: 3c030000 lui v1,0x0
10: 8c620000 lw v0,0(v1)
14: 00200825 move at,at
18: 00022880 sll a1,v0,0x2
1c: 00022100 sll a0,v0,0x4
20: 00a42021 addu a0,a1,a0
24: 00042980 sll a1,a0,0x6
28: 00a42023 subu a0,a1,a0
2c: 00822021 addu a0,a0,v0
30: 00042940 sll a1,a0,0x5
34: 00852021 addu a0,a0,a1