UProLa

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

Пишемо свою ОС. Ч.3 – По слідам Чака Мура

with 6 comments

Чарльз Мур сидів перед пультом і думав. Він уже давно працює в обсерваторії, проте досі не звик до жахливого керування телескопами. Для того, щоб спрямувати об’єктив в якусь точку на небосхилі доводилось писати окрему пограму на Фортані, компілювати її, виловлювати баги і тп і тп… (ви ж пам’ятаєте, які були комп’ютери у 70 роки). Чаку потрібна була така система, яка чекала би його команд, просто виконувала їх і не морочила голову додатковими опціями. Йому потрібна була зручна, швидка та невелика операційна система.

Чак мислив так: ця система повинна слухати мої команди, виконувати їх і потім дозволяти вводити нові команди. Хоч Чак і був астрономом, йому довелось залізти в програмування. Як уже згадувалось, Фортран і Лісп не годилися для розробки, оскільки вони були дуже громіздкі і своїми принципами не дозволяли нормально працювати – вони були завеликі. А більше ніяких мов програмування не було, окрім… асемблера. В ті часи Intel-івські процесори не були в моді (їх взагалі не було), проте була ціла низка різноманітного “каміння”, для кожного з яких асм був свій. Чак дістав потрібні мануали і почав штудіювати.

Він не одразу став хорошим програмістом. Перша версія його інтерпретатора була більше схожа на “Hello world!”. Проте це був необхідний досвід. Наступна версія уже виконувала те, що йому було потрібно – виконувала команди, написані заздалегідь на асемблері. Проте, зрозуміло, що вона була зовсім не придатня для щоденного використання. В часи програмування своєї системи Чак зрозумів, що асемблер – це хороша мова, проте організована дуже незрозуміло, ще й відрізняється синтаксисом для різних процесорів. Тому він вирішив зробити свою систему основану на асмі, проте вона не повинна залежати від конретного процесора. Насправді, так він думав уже багато пізніше, а поки-що він просто хотів покращити свої наробки. Верхом його мрій було заставити інтерпретатор виконувати команди типу:

  • 2 + 2 = ? (треба ж було мати підручний калькулятор)
  • ІНІЦІАЛІЗУВАТИ ТЕЛЕСКОП
  • ПОВЕРНУТИ ТЕЛЕСКОП НА 20 ГРАДУСІВ
  • ПОВЕРНУТИ ТЕЛЕСКОП НА 0.7 РАДІАН

Основні принципи

Існуюча його система стала основою для подальших наробок. Її принципи стали одними з основних. Як же вона працювала?

  1. Система чекала вводу користувача.
  2. Коли користувач тисне [ENTER], система переходить у режим пошуку введеного рядка
  3. Введений рядок шукається у словнику. Словник – це набір іменованих асемблерних процедур. Кожна процедура (іншими словами, слово) містить три основні частини: назву (у вигляді рядка з довжиною у нульовому байті), зв’язок (адреса попереднього слова в словнику) і власне код процедури.
    Існування поля зв’язку у процедури перетворює словник у структуру під назвою “однозв’язний список”, в якому можна зробити перебір усіх елементів (саме це і робить інтерпретатор)
  4. Коли слово знайдене, обчислюється адреса його коду і інтерпретатор робить call на цю адресу
  5. Після виконання слова інтерпретатор стрибає назад в перший пункт і все повторюється спочатку.

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

Виконати одразу кілька команд

Чак тут думав недовго. Кожна команда буде вводитись людиною, а отже не повинна бути дуже довгою (в усіх старих Форт-системах було обмеження слова на 31 символ. – Прим. ред.). І читатись повинна людиною, тому розділювачем
між словами повинен бути “прогалик”, ASCII 0x20. (власне, тут і виник термін “слово”). Отже, тепер інтерпретатор працює так:

  1. Система чекає вводу користувача.
  2. Коли користувач тисне [ENTER], система переходить у режим виконання введеного рядка
  3. Викликається GetToken, який витягує чергове слово з введеного користувачем рядка
  4. Слово порівнюється з кожним із словника. Якщо слово знайдене, обчислюється адреса його коду і інтерпретатор робить call на цю адресу
  5. Після виконання слова інтерпретатор стрибає назад в третій пункт і так поки не кінчаться слова у вхідному рядку.
  6. Якщо якесь вхідне слово не було знайдене, то система вивалюється з грізним повідомленням “ERRRORORROOROROR!!!!! Word NOT FOUND!!!!”
  7. Стрибок у перший пункт

Реалізація

GetToken

В процесі написання даної функції я зрозумів, наскільки непридатня для алгоритмів штука – АСЕМБЛЕР!!! Два дні писав першу версію GetToken, потім вирішив її переписати по новому принципу – ще 2 дні, потім вирішив написати вабще оху*нно – ще три дні відладки… Асм не для дітей, це точно…

Token db 0       ; сюди буде читатись чергове слово
times 32 db 0    ; так я колись резервував місце в пам'яті. Виявилось, можна зручніше
                 ; rb 32   ; (Reserve Bytes, а не Data Bytes)
 
; SI - adress of string
; CL - max symbol count
; word is written to Token
; SI points to end
GetToken:
        mov byte[Token], 0        ; обнулити довжину рядка
        mov di, Token + 1         ; нульовий байт - довжина, слово же почнаєтсья
                                  ; з першого байта
        mov ax, di
        push ax
            .skip_spaces:                ; пропускаємо "прогалики"
                cmp cl, 0                 ; Якщо нуль, то значить введений рядок уже кінчився
                  jz .end
                lodsb
                cmp al, 32
                  jnz .word
                dec cl
            jmp .skip_spaces
 
            .word:                       ; прогалики кінчились, читаємо слово
                cmp cl, 0
                  jz .finished
                stosb
                lodsb
                dec cl
                cmp al, 32                ; обмежуючий слово символ - прогалик
                  jz .finished
            jmp .word
 
      .finished:
        dec si                    ; махінації...
      .end:
        pop ax
        sub di, ax
        mov ax, di
        mov byte[Token], al
        ret

Колись, багато років назад ще на Паскалі я писав кілька разів уже функції типу Split, GetToken, GetAllTokens, Tokens, і навіть на С++ писав в якості учбового завдання. Тому я сподівався написати дану функцію на асемблері в раз. Ага… Хоч і алгоритм зрозумілий (пропустити прогалики, зчитати слово, встановити його довжину в нульовий байт), проте кодити його на асмі було однією морокою. Мало того, оскільки я вибрав шлях розробки системи з нуля, то у мене не було ніяких дебаггерів та інших по-step-них проходжувачів коду. Єдина тулза, якою я міг користуватись – мій мозок, і ця тулза мене постійно підводила. Вона виправляє код і одразу же вірить, що код запрацює правильно… Наївна…

GetString

Хто пробував мою попередню версію інтерпретатора, той знає, що там не працює ні клавіша [DELETE], ні [BACKSPACE]. А отже при невірному вводі доводиться набирати все заново. У новій версії така робота була би занадто неприємною, тому я переписав GetString так, щоб працював хоча б [BACKSPACE], ASCII 0x08

;-------------------------------------------------------------------------------
;--   GetString
; Зчитує з клавіатури рядок у вказане місце в пам'яті
;-------------------------------------------------------------------------------
;ВХІД
; DI - адреса, куди записати символ
;В�ХІД
GetString:
        mov bx, di                     ; записати нуль в перший байт DI (довжина
        mov byte[bx],0                 ;  рядка)
        inc di
            mitka:
                call  SimpleGetKey     ; зчитали клавішу в AL
                cmp al, 32             ; якщо клавіша - не друкований символ,
                  jb .notPrintable     ;  то перевіряємо її на контролюючі клавіші
                stosb
                call  SimplePutChar    ; виводимо на екран (ехо)
                inc   byte[bx]         ; збільшуємо довжину
            jmp mitka
              .notPrintable:
              .backspace:
                cmp al, 8              ; якщо це не BackSpace,
                  jnz .enter           ;    то перевіряємо далі
                cmp byte[bx], 0        ; а якщо довжина рядка нульова,
                  jz mitka             ;    то не обробляємо клавішу
                dec di                 ; зменшуємо довжину рядка на 1
                dec byte[bx]           ;
                call SimplePutChar     ; виводимо послідовність символів
                mov al, 32             ; BackSpace, Space, BackSpace
                call SimplePutChar     ; BackSpace - це всього лиш перевід курсору
                mov al, 8              ;   назад
                call SimplePutChar     ;
                jmp mitka
              .enter:
                cmp   al, 13           ; доки не натиснуто [ENTER]
            jnz mitka
        ret

Ядро

Основний цикл інтерпретатора збільшився з 20 рядків до 40 (це при тому, що можливості оптимізації на цей раз я не розглядав). Проте, його код викладати не буду – а раптом комусь захочеться самому доробити цю основну частину інтерпретатора. Благо інформації про його “начинку” і “затравку” я дав уже багацько.

Слова

Для перевірки працездатності програми я написав два тестових слова, АЛЕФ і БЕЙТ, які виводять по одній відповідній букві. Короткість слів була виправданою, – як я уже згадував 2 дні пішло на відладку процедури розбиття на слова вхідного рядка.

A:
       dw NOTFOUND
       db 1,'a'
          mov al, 'A'
          call SimplePutChar
          ret
B:
       dw A
       db 1,'b'
          mov al, 'B'
          call SimplePutChar
          ret

Тест-драйв

Після відладки весь механізм почав нарешті працювати. На вхід у вигляді

a b   b     a      

він видавав очікуванні “ABBA”. Проте основна радість від вибраної схеми роботи прийшла після того, як я додав ще два слова у словник:

TOKEN:
	dw B
	db 5, 'token'
	   call GetToken
	   pusha
	   mov si, Token
	   call PutPASCAL
	   popa
	   ret
SPACE:
	dw TOKEN
	db 5,'space'
	   mov al, ' '
	   call SimplePutChar
	   ret

Слово “token”, як видно по коду, бере наступне слово з вхідного рядка і потім його же і виводить. За рахунок того, що виклик слова з основного циклу інтерпретера ніяк не запам’ятовує значення регістрів до виклику, є можливість напряму зі слова змінювати регістри і цим контролювати потік коду (або потік текстового входу, що я і зробив у даному випадку). Існує таке писане уже правило, “програма ніколи не запрацює з першого разу так, як задумувалось”. Тому яке було моє здивування, коли я ввів слова і все запрацювало!

Written by danbst

Серпень 26, 2010 at 17:45

Оприлюднено в Програмування

Відповідей: 6

Subscribe to comments with RSS.

  1. P.S. Hell is other encodings: “В�ХІД”.

    Use English in code comments!

    bunyk

    Серпень 26, 2010 at 18:31

  2. Чем дальше, тем сложнее, и тем меньше я понимаю🙂
    Однако я как всегда подумал одну фишку, что если вдруг надо будет спасти человечество, твой мозг очень пригодится.

    Александр

    Серпень 26, 2010 at 20:50

    • >>>Чем дальше, тем сложнее, и тем меньше я понимаю
      далі – гірше, тому рекомендую все-таки зрозуміти, це ж основи.

      danbst

      Серпень 27, 2010 at 09:30

    • Рекомендую не читати ассемблерний код, тоді все зрозуміло. І далі буде веселіше.

      bunyk

      Серпень 30, 2010 at 23:38

  3. Интересно.
    Запасаюсь поп-корном🙂

    Icefall

    Серпень 29, 2010 at 10:12


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

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

Лого WordPress.com

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

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

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