Showing posts with label assembly. Show all posts
Showing posts with label assembly. Show all posts

Friday, April 1, 2022

llvm-mos SID player for Commodore 64

In my previous post I described llvm-mos, a new llvm backend which can generate code for 6502 CPU, and I presented a simple program for an 8-bit Atari. Today I want to show you how you can use assembly code in your C program by using a more complicated example. This time it will be a music player for Commodore 64.

The most popular C64 chiptune format is SID. It's basically a 6502 machine code which consists of two main routines: an init routine which sets up the sound chip, and a player routine which must be called once per screen frame. The biggest resource of SID tunes is the High Voltage SID Collection. There are many players which can play SID music files on modern devices, like ZXTune or VLC.

Preparing a SID file

In order to play a SID tune on a real Commodore 64 we must determine where it should be located in memory, and what are the addresses of the init and the player routines. This information can be found in the SID file header. Bytes 8 and 9 tell if the the data are in original C64 binary file format, i.e. the first two bytes of the data contain the little-endian load address (low byte, high byte), bytes 10 and 11 hold the init address, and bytes 12 and 13 contain the play address. Each tune can use different addresses, so it's necessary to check them carefully. For this project I'll be using one of my favourite C64 tunes, "Ginger" by Kristian Røstøen. When you analyze the header of this particular tune you'll notice that the init address is $1000, the play address is $1003, and the binary data, which begin at offset 124, already contain the load address $1000. We can use this information to extract the machine code from the SID file:
dd if=ginger.sid of=ginger.prg bs=1 skip=124
The resulting file ginger.prg can be put on a floppy disk and loaded on a Commodore 64 with the following command:
LOAD "GINGER",8,1

Loading a SID file

Instead of loading the file into memory by hand, we can write some code to do it for us. Unfortunately, llvm-mos does not have any library functions to do it at the moment, but fortunately Commodore 64 ROM does. The easiest way to use the ROM functions is through assembly, so let's try to write some assembly code in llvm:
char *fname = "GINGER";
unsigned char fnamelo = (unsigned int)fname & 0xFFFF;
unsigned char fnamehi = (unsigned int)fname >> 8;
unsigned char fnamelen = strlen(fname);

asm("JSR $FFBD" :: "a"(fnamelen), "x"(fnamelo), "y"(fnamehi));
The C part should be pretty much self-explanatory. We create variables which contain the lower and the higher byte of the file name pointer, and the file name length. You may think now that using strlen() function is an overkill. Well, in cc65 it probably is, but llvm-mos optimizer can translate the whole expression into a single CPU instruction:
LDA #$06
The assembly part of the code needs more explanation. Here we call SETNAM function located in ROM at address $FFBD. Before we call it, we need to put an address of the string containing the file name in two 8-bit CPU registers, X and Y, and the string length in register A. A pure assembly code would look like this:
LDA fnamelen
LDX fnamelo
LDY fnamehi
JSR $FFBD
However, in llvm-mos we cannot use C expressions in assembly code directly. But we can use so called input and output operands to transfer C variables to CPU registers and vice versa. In gcc syntax for inline assembly, which llvm also uses, operands are separated from assembly expresssions by colons. You can read more about using inline assembly and operands here.

After setting up the file name we need to provide some information about the device from which data should be loaded, and whether it should be loaded to an address pointed by the file header:
asm("LDA #$01\n\t"     // logical file number
    "LDX #$08\n\t"     // device number
    "LDY #$01\n\t"     // load to address found in file header
    "JSR $FFBA\n\t");  // SETLFS
Remember the LOAD "GINGER",8,1 command? This is the ",8,1" part, but written in assembly.

Now all that's left is to load the file into memory:
asm ("LDA #$00\n\t"     // load to memory
     "JSR $FFD5\n\t");  // LOAD

Playing a SID tune

It's time to play the music, then. Let's start with the init routine:
asm ("LDA #$00\n\t"
     "TAX\n\t"
     "TAY\n\t"
     "JSR $1000");
Now we have two ways of calling the play routine. The first one is fairly simple. We need to wait in a loop until the raster reaches a certain line on the screen, and when it happens, call the play routine. The line number can be any number from 0 to 263 (for NTSC machines) or 312 (for PAL machines), but because the raster line register $D012 is 8-bit, it means that it can only hold values from 0 to 255 and that values from 0 to 8 (NTSC) and 0 to 56 (PAL) appear in $D012 more than once per frame. A solution to this problem is to check the 7th bit of register $D011, which is 0 for lines from 0 to 255 and 1 for lines > 255, or use values bigger than 56, which never appear in register $D012 twice during one frame. In my example, I'm using 255:
#define rasterline (*((volatile unsigned char*)0xD012))

while (1) {
    if (rasterline == 255) {
        asm ("JSR $1003");
    }
}
Putting all the code snippets together, a complete program looks like this:
#include <string.h>

#define rasterline (*((volatile unsigned char*)0xD012))

int main() {
    char *fname = "GINGER";
    unsigned char fnamelo = (unsigned int)fname & 0xFFFF;
    unsigned char fnamehi = (unsigned int)fname >> 8;
    unsigned char fnamelen = strlen(fname);

    // Load SID file into memory
    asm("JSR $FFBD\n\t"  // SETNAM (A = fname lenght, XY = fname address)
        "LDA #$01\n\t"   // logical file number
        "LDX #$08\n\t"   // device number
        "LDY #$01\n\t"   // load to address found in file header
        "JSR $FFBA\n\t"  // SETLFS
        "LDA #$00\n\t"   // load to memory
        "JSR $FFD5\n\t"  // LOAD
        :: "a"(fnamelen), "x"(fnamelo), "y"(fnamehi));

    // Init SID player routine
    asm("LDA #$00\n\t"
        "TAX\n\t"
        "TAY\n\t"
        "JSR $1000");

    // Call SID refresh routine
    while (1) {
        if (rasterline == 255) {
            asm ("JSR $1003");
        }
    }

    return 0;
}

Playing a SID tune using interrupts

The second way of calling the play routine is to use raster interrupts. The principle is the same, we call the play routine every frame, but this time we don't have to wait in a loop for a given raster line. We only need to write a short function which will be called when an interrupt occurs, and tell the computer to generate the interrupt at a certain raster line. The addresses of the interrupt routines are stored at the beginning of the memory in a structure called vector table. We need to modify this table so that a raster interrupt vector now points to our function instead of the original one.

Let's write the function first:
void play() {
    asm ("ASL $D019\n\t"  // acknowledge interrupt (reset bit 0)
         "JSR $1003\n\t"  // call SID refresh routine
         "JMP $EA31");    // jump to default interrupt handler routine
}
When writing a raster interrupt function, we need to do two additional things. First, we need to let the computer know that the interrupt was handled properly. This is done by reading register $D019, zeroing it's first byte, and writing back to it. The easiest and fastest way to do it is by using Arithmetic Shift Left (ASL) instruction, which does exactly that. Second, because we hijacked the original interrupt vector, we want to call the original ROM routine when we finish executing our own code.

Now it's time to modify the system interrupts:
#define intctrl (*((volatile unsigned char*)0xDC0D))
#define screenctrl (*((volatile unsigned char*)0xD011))
#define rasterline (*((volatile unsigned char*)0xD012))
#define rasterintctrl (*((volatile unsigned char*)0xD01A))
#define rasterintlo (*((volatile unsigned char*)0x314))
#define rasterinthi (*((volatile unsigned char*)0x315))

void (* fun)(void) = &play;
unsigned char funlo = (unsigned int)fun & 0xFFFF;
unsigned char funhi = (unsigned int)fun >> 8;

asm("SEI");           // switch off interrupts
intctrl = 0x7F;       // disable CIA interrupts
rasterintctrl = 1;    // enable raster interrupts
rasterintlo = funlo;  // low byte of raster interrupt routine
rasterinthi = funhi;  // high byte of raster interrupt routine
rasterline = 127;     // trigger interrupt at raster line 127
screenctrl = screenctrl & 0x7F;
asm("CLI");           // switch on interrupts
First, we need to disable all interrupts with a CPU instruction SEI. We have to do it because there is a chance that an interrupt occurs after we modified some registers, but before we modified others, and it will cause the CPU to jump to a wrong place in memory and crash. Next, we ask the system to disable clock interrupts by zeroing the highest bit of $DC0D, and enable screen raster interrupts instead. Then we change addresses $314 and $315 in the vector table to point to the play() function. Finally, we indicate a raster line which will trigger the interrupt. After we finish modifying the system interrupts we can re-enable them with CLI.

Remember that rasterline register can hold only 8 bits, so you also need to set the highest bit of screenctrl register accordingly. For example, to generate an interrupt when line number 260 is drawn on the screen, you need to do the following:
screenctrl = screenctrl | 0x80;  // last bit equals 1 for lines > 255
rasterline = 4;                  // 260 - 256 = 4
You might look at it as if the rasterline register was 9-bit, with address $D012 holding the lowest 8 bits, and $D011 holding the highest bit in its own highest bit.

Now let's get back to our example. A complete program now looks like this:
#include <string.h>

#define intctrl (*((volatile unsigned char*)0xDC0D))
#define screenctrl (*((volatile unsigned char*)0xD011))
#define rasterline (*((volatile unsigned char*)0xD012))
#define rasterintctrl (*((volatile unsigned char*)0xD01A))
#define rasterintlo (*((volatile unsigned char*)0x314))
#define rasterinthi (*((volatile unsigned char*)0x315))

// SID refresh function
void play() {
    asm("ASL $D019\n\t"  // acknowledge interrupt (reset bit 0)
        "JSR $1003\n\t"  // call SID refresh routine
        "JMP $EA31");    // jump to default interrupt handler routine
}

int main() {
    char *fname = "GINGER";
    unsigned char fnamelo = (unsigned int)fname & 0xFFFF;
    unsigned char fnamehi = (unsigned int)fname >> 8;
    unsigned char fnamelen = strlen(fname);
    void (* fun)(void) = &play;
    unsigned char funlo = (unsigned int)fun & 0xFFFF;
    unsigned char funhi = (unsigned int)fun >> 8;

    // Load SID file into memory
    asm("JSR $FFBD\n\t"  // SETNAM (A = fname lenght, XY = fname address)
        "LDA #$01\n\t"   // logical file number
        "LDX #$08\n\t"   // device number
        "LDY #$01\n\t"   // load to address found in file header
        "JSR $FFBA\n\t"  // SETLFS
        "LDA #$00\n\t"   // load to memory
        "JSR $FFD5\n\t"  // LOAD
        :: "a"(fnamelen), "x"(fnamelo), "y"(fnamehi));

    // Init SID player routine
    asm("LDA #$00\n\t"
        "TAX\n\t"
        "TAY\n\t"
        "JSR $1000");

    // Set up raster interrupt
    asm("SEI");           // switch off interrupts
    intctrl = 0x7F;       // disable CIA interrupts
    rasterintctrl = 1;    // enable raster interrupts
    rasterintlo = funlo;  // low byte of raster interrupt routine
    rasterinthi = funhi;  // high byte of raster interrupt routine
    rasterline = 127;     // trigger interrupt at raster line 127
    screenctrl = screenctrl & 0x7F;
    asm("CLI");           // switch on interrupts

    return 0;
}
It's a bit longer than the first version, but a side effect of using interrupts instead of a loop is that we can still type on the screen and execute simple Basic commands while the music plays in the background.
If you want to try the program yourself, you can find the complete code on Github.

Friday, August 22, 2014

Pushing the limits

Today I'm not going to write about ultra fast Hadoop clusters or insanely scalable, globally-distributed databases. This time I want to take you on the journey in the totally opposite direction, straight into the rabbit hole.

Let's say you want to display a nice looking rainbow on the screen of you TV, like this one:
Because a static picture is a little boring, you also want to animate it, so that the rainbow moves up (or down) the screen. The question is: what hardware do you need for this and what will be the software requirements?

What if I tell you that all you need is a computer with 1.8 MHz CPU, 48 kilobytes of RAM and the program that takes 29 (twenty nine) bytes? Yes, bytes. Less than the number of letters in this sentence. If you don't believe me, you can download a zip archive containing the software from this location. Inside you will find a file rainbow.xex which you can run on any Atari 800/800XL emulator, or even on the real hardware if you still have one (you can use a device like SIO2SD to transfer files to the Atari). I have run it on a real Atari 800XL connected to a plasma TV through a composite video lead, and it works perfectly.

How is that possible? The secret lies in talking directly to hardware. 8-bit computers have very limited resources, so any software layer which is not absolutely necessary is just a waste of memory and CPU cycles. A simple example is a boolean value, which can have one of two states: true or false. Any computer in the world, no matter how simple or complicated, needs only one bit to understand boolean values: 1 for true and 0 for false. Since a byte consists of 8 bits, you can store 8 different boolean values in one byte. Yet, in today's software world, the Java boolean primitive takes entire byte, and the simplest Boolean class:
public final class Boolean
{
    public static final Boolean TRUE = new Boolean(true);
    public static final Boolean FALSE = new Boolean(false);
    private final boolean value;

    public Boolean(boolean value) {
        this.value = value;
    }

    public boolean booleanValue() {
        return value;
    }
}
compiles in Java 7 to 451 bytes of bytecode, not to mention it requires a few hundred megabytes runtime environment to load. This is the cost of having programmer friendly, enterprise grade, programming tools and languages.

Going back to the example, the algorithm to make Atari display the rainbow is quite simple:

1. Initialize graphic mode.
2. Read current scanline from Atari display chip - Antic. Antic creates image on a TV screen drawing it line by line, from left to right, 50 times (PAL) or 60 times (NTSC) per second. The horizontal resolution of an Atari screen is 240 pixels (including borders), which means that the scanline number can have values from 0 (first line) to 239 (last line).
3. If the line number is 0, increase the counter, which is used to calculate the colour palette shift. Increasing the counter on every new frame adds the animation effect to the rainbow picture.
3. Wait for Antic to finish drawing the current line on the screen (we don't want to change color in the middle of the line).
4. Change background colour to the value obtained from Antic (Atari has a total palette of 256 colors) summed up with the current shift value.
5. Repeat from point 2.

This algorithm can be easily translated into a C program:
#include <atari.h>

#define SDMCTL (*((unsigned char*)0x22F))

int main() {
  unsigned char line, counter = 0;

  SDMCTL = 0; // disable display in BASIC screen area
  while (1) {
    line = ANTIC.vcount;  // read current screen line
    if (!line) counter++; // increase color shift on new frame
    ANTIC.wsync = line;   // block CPU until vertical sync
    GTIA_WRITE.colbk = line + counter; //change background color
  }
  return 0;
}
To compile this program on a PC, you can use a cross-platform cc65 compiler:
cl65 -t atari -o rainbow.xex rainbow.c
However, the resulting executable is 1104 bytes long. Let's make the compiler to output the assembly code to see the CPU instruction list it produced:
cc65 -t atari rainbow.c
The assembly source code in the resulting rainbow.s file looks like this:
    jsr     decsp1
    lda     #$00
    jsr     pusha
    ldx     #$00
    lda     #$00
    sta     $022F
L0008:  ldx     #$00
    lda     $D40B
    ldy     #$01
    sta     (sp),y
    ldy     #$01
    ldx     #$00
    lda     (sp),y
    jsr     bnega
    jeq     L000E
    ldy     #$00
    ldx     #$00
    lda     (sp),y
    pha
    clc
    adc     #$01
    ldy     #$00
    sta     (sp),y
    pla
L000E:  ldy     #$01
    ldx     #$00
    lda     (sp),y
    sta     $D40A
    ldy     #$01
    ldx     #$00
    lda     (sp),y
    jsr     pushax
    ldy     #$02
    ldx     #$00
    lda     (sp),y
    jsr     tosaddax
    sta     $D01A
    jmp     L0008
    ldx     #$00
    lda     #$00
    jmp     L0002
L0002:  jsr     incsp2
    rts
Quite long, isn't it? If you understand the assembly language, you will probably notice a few problems here. First, the program jumps a few times to some strange subroutines (like pusha, bnega, tosaddax, etc.), which does not seem necessary. Second, it uses a lot of reads and writes to the stack (although the algorithm uses only two local variables (line and counter). Third, some instructions are completely unnecessary (like LDX, which loads data to never used CPU index register X).

Fortunately, the cc65 compiler provides some optimizations: you can use "‑Oi" and "‑Os" command line switches to inline all subroutines and get rid of jsr instructions, you can also make local variables to be stored under fixed memory address instead of the stack through "‑Cl". Also, using "‑Or" switch enables register variables, which is particularly interesting, because it does not make CPU use physical registers (since MOS 6502 processor used in the 8-bit Atari has only one general purpose register, called accumulator), but it makes variables to be stored in first 256 bytes of physical memory, called zero page. The advantage of using zero page is using less CPU cycles to access it: 8-bit memory addresses (from 0 to 255) are decoded faster by 8-bit processing unit than 16-bit addresses (from 0 to 65535 - the memory limit in Atari 800XL is 64KB).

Let's see what happens if we turn the optimizations on:
cc65 -Cl -Osir -t atari rainbow.c
The resulting assembly code is now much smaller:
    lda     #$00
    sta     L0004
    sta     $022F
L000A:  lda     $D40B
    sta     L0003
    lda     L0003
    bne     L0010
    lda     L0004
    clc
    adc     #$01
    sta     L0004
L0010:  lda     L0003
    sta     $D40A
    lda     L0003
    clc
    adc     L0004
    sta     $D01A
    jmp     L000A
To produce a working executable, we have to assemble and link it:
ca65 rainbow.s && cl65 -t atari -o rainbow.xex rainbow.o
Still, the resulting code is 630 bytes long. This is because the compiler still includes some Atari specific code from the standard library. We can work around this using an assembler (like xasm or MADS). But first, we need to clean up the assembly code a bit:
    org $2000  ; start address

    lda #$00  ; load accumulator with 0
    sta $cb   ; store it in memory
    sta $022f ; disable display in BASIC screen area
loop
    lda $d40b ; read current screen line into accumulator
    sta $cc   ; store it in zero page
    lda $cc   ; load current line number from memory
    bne skip  ; if it's not zero jump to code at 'skip' label
    lda $cb   ; load counter from memory into accumulator
    clc       ; clear carry flag
    adc #$01  ; add 1 to accumulator
    sta $cb   ; store counter in memory
skip
    lda $cc   ; load current line number from memory
    sta $d40a ; block CPU until vertical sync
    lda $cc   ; load current line number from memory
    clc       ; clear carry flag
    adc $cb   ; add counter to the line number
    sta $d01a ; change background colour
    jmp loop  ; repeat
I added some comments to make clear what's going on in the code. So, let's assemble it:
xasm rainbow.s /o:rainbow.xex
Now rainbow.xex is only 45 bytes long! Two first bytes are the executable file header ($FFFF) and the next two are memory address the program should be loaded into ($2000). The rest is pure CPU instruction list.

But we can still make it smaller, using some knowledge the compiler does not have. First, we don't need to init the counter stored at $cb memory address, because we don't care about it's initial value (it gets increased infinitely anyway), so we can get rid of "sta $cb" instruction. Second, we don't need "lda $cc" right after "sta $cc" and "sta $d40a", because the "sta" instruction doesn't change the accumulator state, so there's no need to reload it. We can also replace the whole procedure of loading counter from memory into accumulator, adding 1 and storing it back in memory, with only one instruction - "inc $cb" - which increases the memory value by 1. Finally, we don't need "clc" to clear the carry flag (the flag indicating that a mathematical operation resulted in value which does not fit in 8 bits) before adding line number and counter, because Atari colour palette can have only 256 values, so it doesn't matter if the addition result fits in 8 bits or not.

After making the changes, the code now looks as follows:
    org $2000 ; start address

    lda #$00  ; load accumulator with 0
    sta $022f ; disable display in BASIC screen area
loop
    lda $d40b ; read current screen line into accumulator
    sta $cc   ; store it in zero page
    bne skip  ; if it's not zero jump to code at 'skip' label
    inc $cb   ; increase counter in memory by 1
skip
    lda $cc   ; load current line number from memory
    sta $d40a ; block CPU until vertical sync
    adc $cb   ; add counter to the line number
    sta $d01a ; change background colour
    jmp loop  ; repeat
After assembling it with xasm, the resulting executable is now only 33 bytes long. However, we can still cut the instruction list down. You may notice that there is no need to load and store accumulator at $cc memory address, because its state doesn't change between "sta $cc" and "lda $cc" - so we can safely remove those instructions:
    org $2000 ; start address

    lda #$00  ; load accumulator with 0
    sta $022f ; disable display in BASIC screen area
loop
    lda $d40b ; read current screen line into accumulator
    bne skip  ; if it's not zero jump to code at 'skip' label
    inc $cc   ; increase counter in memory by 1
skip
    sta $d40a ; block CPU until vertical sync
    adc $cc   ; add counter to the line number
    sta $d01a ; change background colour
    jmp loop  ; repeat
As we got rid of another couple of bytes, rainbow.xex is now exactly 29 bytes after assembling.

Lessons learned:
1. Compilation with default compiler options sucks.
2. A smart compiler can do a really great job optimizing code.
3. There is always a way for a programmer to optimize it even more.
4. Programming old computers is fun.

Monday, May 28, 2012

The power of Software Design Patterns

The first day of GeeCON 2012 conference featured a presentation held by dr Ivar Jacobson. His speech called "Liberating the Essence from the Burden of the Whole: A Renaissance in Lean Thinking" made a huge impression on the audience, as it summarized in under an hour his enormous live-long experience in IT industry. It has been a great lesson to anybody who was lucky to attend it.

There was one point, however, I couldn't agree with. Dr Jacobson stated that despite years of its existance software design still lacks universal, solid foundations. Working as a coding architect I have seen a lot of really bad designed and ugly code, including my own. What's more, the abundance of different programming languages and coding styles seems to make things even worse.

There is no single solution that addresses all possible software design problems, but there are some that help solving a great number of those issues. Those universal solutions are called Software Design Patterns. The power of design patterns comes from their pragmatic nature - they are not another product of a software company, university or technical committee, but they are a collection of best practices used by the most skilled programmers to solve the most common programming challenges. The greatest value of software design patterns is that they are universal. It's a common mistake, made even by experienced programmers, to think that design patterns are related only to object oriented programming. They can be applied to any programming language and paradigm. Let me show you how it works.

One of the simplest and yet most powerful design patterns is the state pattern. It allows to easily implement even a very complicated state machine. In this pattern, each state is a separate entity (can be an object), and it is the current state which decides which state comes as the next step of the program. The main loop just holds a reference to the current state and requests it to take certain actions.

State pattern can be used for example to implement a simple ping-pong machine. In this scenario there are two states: ping and pong. Both implement only two functionalities - displaying "ping" or "pong" on the terminal and moving to the next step: in case of ping the next step is pong, and vice versa.

Below is a C++ implementation of a ping-pong state machine. Ping and pong are simple objects that implement two functions: show() and next(). The main program starts with the ping object and than starts to call both methods in a loop. The most crucial element is that the algorithm uses only one reference pointing to the current state. When a transition to the next step takes place, the reference to the previous state is replaced by the new one. This way the main program doesn't need to care about the logic of the state machine, the states take care about it themselves:
#include <iostream>

class State {
public:
    virtual void show() = 0;
    virtual State *next() = 0;
};

class StatePing: public State {
public:
    void show();
    State *next();
};

class StatePong: public State {
public:
    void show();
    State *next();
};

void StatePing::show() {
    std::cout << "ping" << std::endl;
}

void StatePong::show() {
    std::cout << "pong" << std::endl;
}

State *StatePing::next() {
    return new StatePong();
}

State *StatePong::next() {
    return new StatePing();
}

int main(int argc, char *argv[]) {
    State *st = new StatePing();
    for (int i = 0; i < 10; i++) {
        st->show();
        st = st->next();
    }
    return 0;
}
Now you may wonder how can you make use of the state pattern using a functional programming language like, let's say, Erlang? Well, as I sad before, design patterns are universal, so you can use actors instead of objects. Here is Erlang implementation of the state pattern:
-module(states).
-export([state/1, ping/0, pong/0, start/0]).

state(Pid) ->
    receive
        show ->
            Pid ! show,
            state(Pid);
        next ->
            Pid ! {next, self()},
            state(Pid);
        {new, From} ->
            state(From)
    end.

ping() ->
    receive
        show ->
            io:format("ping~n"),
            ping();
        {next, From} ->
            Pid = spawn(states, pong, []),
            From ! {new, Pid}
    end.

pong() ->
    receive
        show ->
            io:format("pong~n"),
            pong();
        {next, From} ->
            Pid = spawn(states, ping, []),
            From ! {new, Pid}
    end.

start() ->
    S1 = spawn(states, ping, []),
    spawn(states, state, [S1]).
"Ping", "pong" and "state" are actors. "State" actor acts as a current state reference - it holds the pid (process id) of the current actor. When you send message "next" to "state" it passes it to the current actor, which spawns a new actor and sends its pid back to "state". This way "state" always holds a pid of the current state represented by actor.
You can load this code into your erlang shell and use observe how it works:
S = states:start().
S ! show.
S ! next.
S ! show.
How about languages that don't support object oriented programming or actors? Have a look at this Scheme example:
(define ping
  (lambda (arg)
    (cond ((equal? arg "show") (display "ping\n") ping)
          ((equal? arg "next") pong))))

(define pong
  (lambda (arg)
    (cond ((equal? arg "show") (display "pong\n") pong)
          ((equal? arg "next") ping))))

(define state
  (let ((current-state ping))
    (lambda (arg)
      (set! current-state (current-state arg)))))

(define repeat
  (lambda (n)
    (let loop ((i 0))
      (cond ((< i n)
             (state "show")
             (state "next")
             (loop (+ i 1)))))))

(repeat 10)
In this example "ping" and "pong" are first class functions which can be passed as arguments to other expressions. Reference to ping or pong is stored in the "state" function, which acts as a closure. It means that the value of the current-state variable is being retained between subsequent calls of the "state" function.

But what if you are a real hardcore hacker who despises high level programming languages and codes only in assembly? Or maybe there are some cases when you may have to? Well, than I have somehing for you too - here is a short state machine written for 64-bit Linux in Intel x86 assembly using The Netwide Assembler:
global  _start

section .data
    ping_msg:  db  'ping', 0x0A
    ping_len:  equ $-ping_msg
    pong_msg:  db  'pong', 0x0A
    pong_len:  equ $-pong_msg

section .text

_start:
    ; init first state
    mov     rsi, _ping_show
    mov     rdi, _ping_next
    ; repeat 10 times
    mov     rcx, 10
_loop:
    push    rcx
    call    rsi            ; show
    call    rdi            ; next
    pop     rcx
    loop    _loop
    ; finish
    mov     rax, 60         ; sys_exit
    mov     rdi, 0          ; exit code
    syscall

_ping_show:
    mov     rax, 1          ; sys_write
    mov     rdi, 1          ; stdout
    mov     rsi, ping_msg
    mov     rdx, ping_len
    syscall
    mov     rsi, _ping_show
    mov     rdi, _ping_next
    ret

_ping_next:
    mov     rsi, _pong_show
    mov     rdi, _pong_next
    ret

_pong_show:
    mov     rax, 1          ; sys_write
    mov     rdi, 1          ; stdout
    mov     rsi, pong_msg
    mov     rdx, pong_len
    syscall
    mov     rsi, _pong_show
    mov     rdi, _pong_next
    ret

_pong_next:
    mov     rsi, _ping_show
    mov     rdi, _ping_next
    ret
To compile the assembly example in Linux use the following commands:
nasm -f elf64 -o states.o states.asm
ld -o states states.o
In this case index registers rsi and rdi are used to keep references to the current state. The main loop just calls "_show" and "_next" subsequently and the "ping" and "pong" states take responsibility for passing valid pointers to the CPU registers.

As you can see, you can use design patterns to properly implement soultions to some universal software desing problems. You only need to be aware of the strength and possibilities of your current programming language and use them wisely.