It’s certainly been a while, hasn’t it? This is the third part in a series I started back in September of 2015. After months, this part still doesn’t cover what it was meant to, so this is just part Ⅰ of part Ⅲ. Enjoy.

The real instruction, the best instruction

First, I’d like to introduce you to my favourite x86 instruction: rdtsc¹. This handy instruction loads the 64-bit timestamp counter register into edx:eax. The 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 for balance.

To shuffle the bag, we can use Fisher–Yates shuffle, which will need an implementation of rand. Maybe you see where this is going.

I know, 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

The 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 ebp, so can load the range directly from [esp + 4].²

rand:
  rdtsc
  xor edx, edx
  div dword [esp + 4]
  mov eax, edx
  ret

Before dividing the cycle count, edx is zeroed to prevent overflow exceptions. The div instructions leaves the remainder in edx, so that is returned.

Shuffle

The 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 ebx, and the index of the last element into ecx.

shuffle:
  push ebp
  mov ebp, esp
  push ebx

  mov ebx, [ebp + 8]
  mov ecx, [ebp + 12]
  dec ecx

In a loop, rand is used to get a random index between 0 and ecx inclusive.

  .loop:
    lea eax, [ecx + 1]
    push eax
    call rand
    add esp, 4

In order to pass ecx + 1 to rand, 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 ecx and the random index eax are then swapped, using dx as a temporary.

    mov dx, [ebx + ecx * 2]
    xchg dx, [ebx + eax * 2]
    mov [ebx + ecx * 2], dx
    loop .loop

The loop continues, decrementing ecx each time. When the loop completes, the array has been shuffled in-place, and the function simply returns.

  pop ebx
  mov esp, ebp
  pop ebp
  ret

The full implementation can be found in random.asm.

Proof that it works

Using functions from previous parts of the series, we can build a small test that shuffles an array of 4 words on each key event.

section .data

array dw 0xAAAA, 0xBBBB, 0xCCCC, 0xDDDD

section .text

main:
  push word BG.BLACK | ' '
  call clear

  .loop:
    call scan
    test al, al
    jz .loop

    push dword 4
    push array
    call shuffle

    push word 0x1008
    push dword [array]
    call itoa
    push dword 0x0101 << 16 | FG.BRIGHT | FG.BLUE
    push eax
    call puts

    push word 0x1008
    push dword [array + 4]
    call itoa
    push dword 0x0109 << 16 | FG.BRIGHT | FG.BLUE
    push eax
    call puts

    add esp, 36
    jmp .loop

And hopefully the array will be shuffled differently each time.

In the distant future…

At some point, there will be a post covering actual timing using rdtsc. It will be terrible and wonderful at the same time. Oh, and eventually we’ll make an actual Tetris game. Almost forgot.