Машина состояний

Машина состояний предполагает программу, которая может находиться в определенном состоянии из конечного набора состояний. Программа запоминает свое состояние и определяет действия для перехода из одного состояния в другое.

На уровне ассмеблера простейшая реализация машины состояний состоит в последовательном сравнении текущего состояния с состояниями из набора. Если сравнение успешно, два значения равны, то выполняются действия, определенные для этого состония. Если сравниваемые значения не равны, то сравниваем со следующим состоянием:

.data
    state byte 0        ; условное состояние
.code

state_machine proc
state_0:
    cmp state, 0    ; сраниваем состояние
    jne state_1
    add eax, ecx    ; состояние 0: складываем ECX и EAX и переключаемся на состояние 1
    inc state       ; изменяем состояние
    jmp exit
state_1:
    cmp state, 1
    jne state_2
    sub eax, ecx    ; состояние 1: вычитаем ECX из EAX и переключаемся на состояние 2
    inc state       ; изменяем состояние
    jmp exit
state_2: 
    cmp state, 2
    jne state_3
    imul eax, ecx   ; состояние 2: умножаем ECX на EAX и переключаемся на состояние 3
    inc state       ; изменяем состояние
    jmp exit
state_3:
    ; cmp state, 3  ; предположим, что это состояние будет в любом случае, но также можно сравнивать
    xor edx, edx    ; для деления расширяем нулями регистр EAX на EDX
    div ecx         ; состояние 3: делим EAX на ECX и переключаемся на состояние 0
    mov state, 0    ; изменяем состояние
exit: 
    ret
state_machine endp

main proc
    mov eax, 5
    mov ecx, 4
    call state_machine
    ret
main endp
end

Для данной программы предположим, что все возможные состояния описываются числами 0, 1, 2, 3, которые представляют определенную арифметическую операцию: сложение (0), вычитание (1), умножение (3) и деление (4). Для хранения состояния в программе определена переменная state. Для управления состоянием определена процедура state_machine, в которой мы сравниваем значение state с возможными состояниями. Если сравнение успешно, выполняем арифметическую операцию и изменяем состояние. Либо переходим к следующей метке для проверки нового состояния.

Через регистры EAX и ECX процедура state_machine получает значения:

mov eax, 5
mov ecx, 4
call state_machine

Таким образом, после выполнения процедуры будет выполняться операция сложения (так как переменная state на старте программы равна 0). В EAX окажется число 9, а переменная state получит значение 1.

Подобным образом мы могли бы несколько раз вызывать процедуру state_machine, передавая ей через RCX различные значения:

main proc
    mov eax, 5
    mov ecx, 4
    call state_machine  ; EAX = 9, state = 1

    mov ecx, 3
    call state_machine  ; EAX = 6, state = 2

    mov ecx, 4
    call state_machine  ; EAX = 24, state = 3

    mov ecx, 2
    call state_machine  ; EAX = 12, state = 0
    ret
main endp

Хотя этот пример представляет довольно простую схему для реализации состояний, но тем не менее последовательный поиск и сравнение значений не оцень эффективны. И в этом случае мы можем оптимизировать программу следующим образом:

.data
    state qword state_0     ; условное состояние
.code

option noscoped     ; делаем метки глобальными

state_machine proc
    jmp state
state_0:
    add eax, ecx    ; состояние 0: складываем ECX и EAX и переключаемся на состояние 1
    lea rcx, state_1
    mov state, rcx
    ret
state_1:
    sub eax, ecx    ; состояние 1: вычитаем ECX из EAX и переключаемся на состояние 2
    lea rcx, state_2
    mov state, rcx
    ret
state_2:
    imul eax, ecx   ; состояние 2: умножаем ECX на EAX и переключаемся на состояние 3
    lea rcx, state_3
    mov state, rcx
    ret
state_3:
    xor edx, edx    ; для деления расширяем нулями регистр EAX на EDX
    div ecx         ; состояние 3: делим EAX на ECX и переключаемся на состояние 0
    lea rcx, state_0
    mov state, rcx
    ret
state_machine endp

main proc
    mov eax, 5
    mov ecx, 4
    call state_machine  ; EAX = 9, state = state_1

    mov ecx, 3
    call state_machine  ; EAX = 6, state = state_2

    mov ecx, 4
    call state_machine  ; EAX = 24, state = state_3

    mov ecx, 2
    call state_machine  ; EAX = 12, state = state_0
    ret
main endp
end

Теперь состояния представляют метки state_N, на которые процецируются действия. Чтобы глобальная переменная state могла хранить адрес определенной метки внутри процедуры, перед процедурой указываем директиву option noscoped. В самой процедуре с помощью инструкции jmp сразу переходим к нужному состоянию:

jmp state