It’s certainly been a while,
This is the third part
in a series
I started back in September of 2015.
this part still doesn’t cover
what it was meant to,
so this is just part Ⅰ of part Ⅲ.
The real instruction, the best instruction
I’d like to introduce you
to my favourite x86 instruction:
This handy instruction loads
the 64-bit timestamp counter register
starts at zero
and is monotonically incremented
on each clock cycle.
It may not seem immediately useful,
but it can actually be put to
a couple fun/scary uses
in a constrained environment.
Quite possibly the worst random
To implement a Tetris game,
we’ll need to spawn tetrominoes,
and they need to spawn randomly.
The actual mechanic uses a
“shuffled bag” of the seven tetrominoes
To shuffle the bag,
we can use Fisher–Yates shuffle,
which will need an implementation of
Maybe you see where this is going.
rdtsc is clearly not random.
It is monotonically increasing!
The thing is,
processors are fast,
and reading the cycle count
at varying points should
produce somewhat unpredictable lower bits.
Those lower bits could certainly be used
to seed some sort of pseudo-random number generator,
but that’s more work than it’s worth.
Let’s just use modulo.
rand function will take
a double-word range parameter
and return a “random” number n,
where 0 ≤ n < range.
It won’t need to bother with
so can load the range directly from
[esp + 4].
xor edx, edx
div dword [esp + 4]
mov eax, edx
Before dividing the cycle count,
edx is zeroed to prevent overflow exceptions.
div instructions leaves the remainder in
so that is returned.
shuffle function will take two parameters.
The first will be a double-word address
of the first word in an array of words,
and the second will be the double-word length of the array.
It will shuffle arrays of words
since tetrominoes will later be represented as such.
The function begins by loading
the address of the array into
and the index of the last element into
mov ebp, esp
mov ebx, [ebp + 8]
mov ecx, [ebp + 12]
In a loop,
rand is used to get
a random index between 0
lea eax, [ecx + 1]
add esp, 4
In order to pass
ecx + 1 to
the “load effective address”
lea instruction is used.
This is a common trick for doing
certain arithmetic operations in a single instruction.
The values at the current index
and the random index
are then swapped,
dx as a temporary.
mov dx, [ebx + ecx * 2]
xchg dx, [ebx + eax * 2]
mov [ebx + ecx * 2], dx
The loop continues,
ecx each time.
When the loop completes,
the array has been shuffled in-place,
and the function simply returns.
mov esp, ebp
The full implementation can be found in random.asm.
Proof that it works
from previous parts of the series,
we can build a small test
that shuffles an array of 4 words
on each key event.
array dw 0xAAAA, 0xBBBB, 0xCCCC, 0xDDDD
push word BG.BLACK | ' '
test al, al
push dword 4
push word 0x1008
push dword [array]
push dword 0x0101 << 16 | FG.BRIGHT | FG.BLUE
push word 0x1008
push dword [array + 4]
push dword 0x0109 << 16 | FG.BRIGHT | FG.BLUE
add esp, 36
And hopefully the array
will be shuffled differently
In the distant future…
At some point,
there will be a post
covering actual timing
It will be terrible
and wonderful at the same time.
Oh, and eventually we’ll
make an actual Tetris game.