UProLa

Неокріпші думки

Продовжуємо писати свою ОС. Інтерпретатор у 279 байт

with one comment

Перша частина

Що таке операційна система?

Це така програма, яка дозволяє створювати та координувати дочірні програми. Розділяти між дочірними процесами пам”ять, ресурси, запускати та знищувати їх. Програма, яка дозволяє дочірним програмам абстрагуватись від HardWare або предоставляє свої інтерфейси для різних типових задач. Саме по цим параметрам і відрізняються існуючі ОСі. Можете переконатись.

Що таке інтерпретатор?

Це програма, яка

  1. дозволяє користувачу ввести рядок символів,
  2. потім аналізує його,
  3. проводить певні дії в зв”язку з результатами аналізу
  4. і повторює даний алгоритм знову, починаючи з першого пункту.

Конкретно, інтерпретатором є командний рядок. ( Але командний рядок не є операційною системою!)

Ну що ж, тепер я відаючий! Гайда кодити!

Почнемо з чогось простенького. Наприклад, такого:

;=============================
;--  Макроси FASM-у, для більшої структурності
;=============================
PUT_CHAR_FUNC = 0x0E
BIOS_VIDEO = 0x10

READ_KEY = 0x00
KEYBOARD = 0x16

;-----------------
;-- Simple routines for basic I/O
;-----------------
; they change AX

;MODIFIES
; AL - input char will be there
SimpleGetKey:
  mov ah, READ_KEY
  int KEYBOARD
ret

SimplePutChar:
  mov ah, PUT_CHAR_FUNC
  int BIOS_VIDEO
ret

;types EOL
SimplePutEnd:
  mov al, 10
  call SimplePutChar
  mov al, 13
  call SimplePutChar
ret

Тепер, наприклад, викликавши функцію SimpleGetKey (call SimpleGetKey), ми отримаємо в регістрі AL аскіі-код символу. А щодо останньої функції: виявляється, символ №13 виконує ту дію, яку повинна виконувати кнопка “стрілочка вниз”, а №10 – ту дію, яку виконує кнопка “Home”. Тому комбінація цих двох символів і буде являтись переводом каретки. Ось така особливість БІОСа…

Паскаль-рядки

В своїй програмі я буду використовувати Паскаль-рядки, а не ASCIIZ, оскільки недоліки останніх в загальному гірші для структурності та програмування. Паскаль-рядок – це такий масив символів, у якому довжина цього масиву задається у нульовому байті.

Вивід рядка на екран

Отже, ось три еквівалентні функції виводу паскаль-рядку на екран.

; Puts a string with length in zero-index byte to screen and types EOL
; USES
; SI - adress of string

; Мій особистий перший варіант ))
PutPASCAL:
  xor cx, cx            ; CH <- 0
  lodsb                 ; AL <- [SI]; SI++   // read first byte - string length
  mov cl, al            ; CL <- AL
  mov ah, PUT_CHAR_FUNC ; AH <- 0x0E
  nextpascalchar:
    lodsb                 ; AL <- [SI]; SI++
    int BIOS_VIDEO        ; put char in AL to screen
  loop nextpascalchar   ; loop this actions for CX symbols
ret

; Попитав я людей і написав такий оптимізованіший по розміру варіант
PutPASCAL_opt:
  movzx cx, byte[si]
  inc si
  mov ah, 0Eh
  next_pascal_char:
    lodsb
    int 10h
  loop next_pascal_char
ret

; МНР-подібний алгоритм. використав тільки MOV, INC, LOOP
PutPASCAL_algorithm:           ; Вивід рядка, алгоритм.
  mov ah, 0Eh                  ; AH <- 0x0E
  mov al, [si]                 ; AL <- mem[SI]
  inc si                       ; SI++
  mov cx, 0                    ; CX <- AL
  mov cl, al                   ;
  next_pascal_char_algo:       ;
    mov al, [si]               ; AL <- mem[SI]
    int 10h                    ; вивести символ в AL на екран
    inc si                     ; SI++
  loop next_pascal_char_algo   ; CX <- CX-1 / goto next_pascal_char_algo if CX=0
ret

Звісно, у своїй програмі я використаю ту, в якій менше коментарів ))) Насправді, бо вона найменша – всього лиш 12 байт в машинних кодах.

Зчитування рядка з екрану

Тут також приведу два алгоритми – один свій, інший чужий оптимізованіший.

;------------------
;-- GetString -----
; Gets an #13 ended string from input device (like readln in Pascal)
;------------------
;USES
; DI - destination, where to write string
;MODFIES
; AX - length of string
; DI - adress of first free memory (adress of string end+1)
; BX - adress of string start
GetString_:
  mov bx, di
  mov al, 0
  stosb
  loop_read:
    call SimpleGetKey
    cmp al, 13
    jz finish_input
    stosb
    call SimplePutChar
    jmp loop_read
  finish_input:
  mov ax, di
  sub ax, bx
  dec ax
  mov byte[bx], al
ret

GetString:
  mov bx, di
  mov byte[bx],-1
  inc di
 mitka:
    call  SimpleGetKey    ;считали клавишу в AL
    stosb
    call  SimplePutChar   ;также нужно вывести ее на екран, чтобы юзерь видел, что вводит
    inc   byte[bx]        ;длина строки
    cmp   al, 13          ;пока не нажмут Enter
 jnz mitka
ret

Звісно, чужу функцію використаю, 20 байт (мій варіант – 26 байт). Тепер у нас є функції вводу-виводу, ура! Можна приступати до структурної частини розробки ПЗ.

Алгоритм

1. Зчитали рядок
2. Шукаємо в зв”язному списку введений рядок
3.а Якщо знайшли, то переходимо до коду виконання і запускаємо його
3.б Якщо не знайшли, то запускаємо спеціальну ф-цію NOTFOUND (насправді, не така вона вже й спеціальна, адже знаходиться в нашому зв”язному списку).
4. Починаємо все спочатку

Структура зв”язного списку

Наш список (список зв”язаний з кінця) буде складатись з іменованих процедур, я їх буду називати “словами”. Кожне слово у собі містить:

  1. Адресу попереднього “слова” (2 байти). Якщо немає попереднього – то нуль.
  2. Паскаль-рядок – назва слова (у нульовому його байті довжина рядка)
  3. Повноцінний код на асемблері, який буде асоціюватись з даним словом
  4. Команда ret – вихід з “слова”

Власне, дивіться:

;---------------------------
;--   Different data -------
;---------------------------
; Дані для ядра.

last_word     dw HELLO     ; last_word вказує на останнє визначене слово

;---
; NOTFOUND - повинно бути першим. NotFound_code не видаляти. Інше можна змінити
NOTFOUND:
    dw 0
    db 8,'NOTFOUND'
    NotFound_code:
       nop
       mov si, nf_help
       call PutPASCAL_opt
       ret
       nf_help db 29,'Sorry Dave, I cannot do that.'
; Далі йдуть юзерські слова....
HELLO:
    dw NOTFOUND
    db 12,'Hello world!'
       mov si, hell_help
       call PutPASCAL_opt
       ret
       hell_help db 8,'Hi dude!'

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Всі юзерські функції повинні описуватись вище даного місця.
; Звідси починаються системні змінні, як наприклад ось ця
; Тимчасовий буфер при зчитуванні рядка з клавіатури.
InputBuffer db 0

Ядро

Нарешті ви готові подивитись на ядро мого інтерпретатора. Я коментував його, не шкодуючи символів, щоб не дай бог ніхто не сказав про мене, що я пишу незрозумілий код.

;--------------------------
;-- Console_GetString -----
; Gets an #13 ended string, but in console-like view. Sets SI to adress of input buffer
;--------------------------
;USES
; nothing
;MODIFES
; AX - trash
; DI - adress of last free memory
; SI - adress of current word, input buffer
Console_GetString:
 mov al, '>'
 call SimplePutChar
 mov al, ' '
 call SimplePutChar
 mov di, InputBuffer   ; Ось ядро цієї функції
 call GetString        ; Виділив його коментаріями серед купи декораторів
 call SimplePutEnd
 ret


;++++++++++++++++++++
;--   MAIN    -------
;++++++++++++++++++++

; Ядро операційної системи (інтерпретатора)
; Мінімізував як міг. Пожертвував зрозумілістю
main:                        ; Точка входу у вічний цикл інтерпретатора.  <--------
  call Console_GetString     ; Зчитуємо, що вводить юзер у InputBuffer             |
  mov bx, [last_word]        ; BX <- адресу останнього слова                       |
  search_loop:               ; Цикл пошуку слова серед інуючих  <----------------  |
      mov si, InputBuffer    ; Наступні 5 команд - перевірка на рівність рядків: | |
      mov di, bx             ; записаного у полі "Назва" існуючого слова і       | |
      add di, 2              ; введеного у InputBuffer                           | |
      movzx cx, byte[di]     ;                                                   | |
      repe cmpsb             ;                                                   | |
      jz EQUAL               ; Якщо ми знайшли слово, то виконати його!          | |
      mov bx, [bx]           ; BX <- попереднє слово                             | |
      or bx, bx              ; Якщо BX != 0 (тобто, слова ще присутні у списку), | |
  jnz search_loop            ;   то продовжити шукати    ------------------------  |
  mov di, NotFound_code      ; Ой! Уже кінець, а слово не знайдене                 |
                             ; ^[брудний хак] ))                                   |
  EQUAL:                     ;                                                     |
     inc di                  ; обчислюємо початок коду...                          |
     call di                 ; ... і запускаємо його                               |
     call SimplePutEnd       ; перевід рядка                                       |
jmp main                     ; і все спочатку -------------------------------------

Демонстрація роботи

Ну що? Будете дивитись, як воно працює? =)

Якщо чесно, я збрехав у назві теми. Мій інтерпретатор насправді можна зменшити ще на третину (або навіть половину!), але тоді він буде мего-неструктурованим, мего-захаченим, не буде вміти писати “Hi dude!” і, що найважливіше, НЕ БУДЕ ВМІТИ МАЛЮВАТИ ФРАКТАЛ МАНДЕЛЬБРОТА!!!

Дякую, що прочитали мій постик! Як винагорода –

Код повністю

;=============================
;--  Макроси для FASM-у, для більшої структурності
;=============================
PUT_CHAR_FUNC = 0x0E
BIOS_VIDEO = 0x10

READ_KEY = 0x00
KEYBOARD = 0x16

;-------------------------------------------------
; MBR clear
;-------------------------------------------------
ORG 7C00h
use16

;++++++++++++++++++++
;--   MAIN    -------
;++++++++++++++++++++

; Ядро операційної системи (інтерпретатора)
; Мінімізував як міг. Пожертвував зрозумілістю
main:                        ; Точка входу у вічний цикл інтерпретатора.  <--------
  call Console_GetString     ; Зчитуємо, що вводить юзер у InputBuffer             |
  mov bx, [last_word]        ; BX <- адресу останнього слова                       |
  search_loop:               ; Цикл пошуку слова серед інуючих  <----------------  |
      mov si, InputBuffer    ; Наступні 5 команд - перевірка на рівність рядків: | |
      mov di, bx             ; записаного у полі "Назва" існуючого слова і       | |
      add di, 2              ; введеного у InputBuffer                           | |
      movzx cx, byte[di]     ;                                                   | |
      repe cmpsb             ;                                                   | |
      jz EQUAL               ; Якщо ми знайшли слово, то виконати його!          | |
      mov bx, [bx]           ; BX <- попереднє слово                             | |
      or bx, bx              ; Якщо BX != 0 (тобто, слова ще присутні у списку), | |
  jnz search_loop            ;   то продовжити шукати    ------------------------  |
  mov di, NotFound_code      ; Ой! Уже кінець, а слово не знайдене                 |
                             ; ^[брудний хак] ))                                   |
  EQUAL:                     ;                                                     |
     inc di                  ; обчислюємо початок коду...                          |
     call di                 ; ... і запускаємо його                               |
     call SimplePutEnd       ; перевід рядка                                       |
jmp main                     ; і все спочатку -------------------------------------

;-----------------
;-- Simple routines for basic I/O
;-----------------
; they change AX

;MODIFIES
; AL - input char will be there
SimpleGetKey:
 mov ah, READ_KEY
 int KEYBOARD
 ret

SimplePutChar:
 mov ah, PUT_CHAR_FUNC
 int BIOS_VIDEO
 ret

;types EOL
SimplePutEnd:
 mov al, 10
 call SimplePutChar
 mov al, 13
 call SimplePutChar
 ret

;------------------
;-- GetString -----
; Gets an #13 ended string from input device (like readln in Pascal)
;------------------
;USES
; DI - destination, where to write string
GetString:
  mov bx, di
  mov byte[bx],-1
  inc di
 mitka:
    call  SimpleGetKey        ;считали клавишу в AL
    stosb
    call  SimplePutChar     ;также нужно вывести ее на екран, чтобы юзерь видел, что вводит
    inc   byte[bx]        ;длина строки
    cmp   al, 13        ;пока не нажмут Enter
 jnz mitka
ret

;--------------------------
;-- Console_GetString -----
; Gets an #13 ended string, but in console-like view. Sets SI to adress of input buffer
;--------------------------
;USES
; nothing
;MODIFES
; AX - trash
; DI - adress of last free memory
; SI - adress of current word, input buffer
Console_GetString:
 mov al, '>'
 call SimplePutChar
 mov al, ' '
 call SimplePutChar
 mov di, InputBuffer   ; Ось ядро цієї функції
 call GetString        ; Виділив його коментаріями серед купи декораторів
 call SimplePutEnd
 ret

;--------------------
;--   Console_PutPASCAL  -------
; Puts a string with length in zero-index byte to screen and types EOL
;--------------------
; USES
; SI - adress of string
; MODIFIES
; SI - end of string
; CX - 0
; AX - trash
PutPASCAL_opt:
 movzx cx, byte[si]
 inc si
 mov ah, PUT_CHAR_FUNC
 next_pascal_char:
     lodsb
     int BIOS_VIDEO
 loop next_pascal_char
 ret

;---------------------------
;--   Different data -------
;---------------------------
; Дані для ядра.

last_word     dw MAND         ; last_word вказує на останнє визначене слово

;---
; NOTFOUND - повинно бути першим. NotFound_code не видаляти. Інше можна змінити
NOTFOUND:
    dw 0
    db 8,'NOTFOUND'
    NotFound_code:
       nop
       mov si, nf_help
       call PutPASCAL_opt
       ret
       nf_help db 29,'Sorry Dave, I cannot do that.'
; Далі йдуть юзерські слова....
HELLO:
    dw NOTFOUND
    db 12,'Hello world!'
       mov si, hell_help
       call PutPASCAL_opt
       ret
       hell_help db 8,'Hi dude!'
; Mandelbrot plotter, 61 bytes - Tenie Remmel
; Надіюсь, вам сподобається )
MAND:
    dw HELLO
    db 4,'MAND'
    push es
    mov ax, 0
    mov di, 0fffeh
    push    0A000h
    pop    es
    mov    al, 013h    ; установка видеорежима
    int    10h        ; 320х200 256 цветов
    stosw            ; [es:di] <-- ax, di <-- di+2
    mov    cl, 200     ; cl <-- 200
  outer_loop:
    mov    si, 320     ; si <-- 320
    inner_loop:
    mov    bp, 79        ; bp <--- макс. число шагов
    xor    bx, bx        ; p <-- 0
    xor    dx, dx        ; q <-- 0
    complex_loop:
    push    dx        ; сохраняем q в стеке
    mov    ax, bx        ; ax <-- p
    sub    ax, dx        ; ax <-- p - q
    add    dx, bx        ; dx <-- q + p
    imul    dx        ; dx:ax <-- p^2 - q^2
    mov    al, ah
    mov    ah, dl        ; ax <-- (p^2 - q^2) / 256
    pop    dx        ; dx <-- q из стека
    xchg    bx, ax        ; bx <-- (p^2 - q^2)/256, ax <-- p
    sub    bx, si        ; bx <-- (p^2 - q^2)/256 + 256x
    imul    dx        ; dx:ax <-- p*q
    shld    dx, ax, 9    ; dx <-- p*q / 128
    sub    dx, cx        ; dx <-- p*q / 128 + 256*y
    test    dh, dh
    jg    plot_color    ; если q >= 256,  ----v
    dec    bp        ; bp--
    jne    complex_loop    ; если bp != 0, ----^
    plot_color:
    xchg    bp, ax
    stosb            ; экран <-- bp
    dec    si        ; si--
    jne    inner_loop    ; если si != 0, ----^
  loop      outer_loop        ; cx раз   ----^
  pop es

  call SimpleGetKey
  mov ax, 2
  int 10h
  ret

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Всі юзерські функції повинні описуватись вище даного місця.
; Звідси починаються системні змінні, як наприклад ось ця
; Це для того, щоб не створювати межі для вводу символів.
InputBuffer db 0


times (512-2-($-7C00h)) db 0
db 055H, 0AAH

Для підсвітки коду використав http://tohtml.com/asm/, стиль black.

Одна відповідь

Subscribe to comments with RSS.

  1. Опа. А я вже подумав що ти збацав інтерпретатор Форта на 279 байт. І на ньому ганяєш програмки для фракталу Мандельброта.

    Але все одно клас…

    bunyk

    Березень 1, 2010 at 19:55


Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: