Як робити парсинг тексту голим хардвером, без процесора і без софтвера

Хтось парсирует текстовий файл програмою на Пітоні, інший пише скрипт з регулярними виразами на Перлі, Сі-програміст сором'язливо возиться з буферами і покажчиками, іноді застосовуючи Yacc і Lex.

А можна парсировать текст голим залізом? Взагалі без програми?

— А як це?, — запитав мене знайомий, — З допомогою Ардуїнов?

— Всередині Ардуїнов варто цілком фон-неймановский процесор і працює програма, — відповів я, — Ні, ще більш голе залізо.

— А-а-а-а, цей, мікрокод?, — здогадався мій товариш і глянув на мене переможно.

— Ні, термін «мікрокод» використовувався для специфічної організації процесорів в 1970-е роки, потім його використання зійшло нанівець, — відповів я і додав, — Правда є ще мікрооперації в интеловских процесорів, які перекодовується x86, але це теж інше. Ні, я маю на увазі парсинг тексту пристроєм, що складається з логічних елементів І-АБО-НЕ і Д-тригерів, як на картинці нижче.

— Неможливо! — вигукнув мій приятель, — в такому пристрої десь збоку повинен сидіти процесор і хитро підморгувати!

— Чому це неможливо?, — парирував я, — Ось машину Тюрінга знаєш? Парсирует текст на стрічці, а збоку ніякі интелы і ардуїнов не підморгують.

— Нуу, машина Тюрінга, — простягнув приятель, — це абстракція, типу Демона Максвелла.

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

mfp_srec_parser_fragment

1. Навіщо мені знадобилося парсировать текст хардвером без софтвера

В минулому році я брав участь як один з організаторів серії семінарів MIPSfpga. MIPSfpga — це пакет, який містить процесорне ядро в исходниках на Verilog, яке можна змінювати, додавати нові інструкції, будувати багатопроцесорні системи, змінювати одночасно софтвер і хардвер і т. д. Систему MIPSfpga можна симулювати в симуляторі верилога, синтезувати і реалізувати на платі ПЛІС, або при великому бажанні виготовити з нею мікросхему на фабриці.

ПЛІС/FPGA-плату з MIPSfpga потрібно програмувати двічі — спершу залити в неї c PC конфігурацію хардвера (визначити логічну функцію кожної клітинки ПЛІС і з'єднання між ними), а потім залити (теж з PC) софтвер (послідовність команд процесора) в пам'ять синтезованої хардверной системи (в яку входить процесорне ядро MIPS microAptiv UP, інтерконнект, два блоки пам'яті і блок вводу-виводу).

З заливкою хардвера проблем немає — і Xilinx ISE/Vivado, і Altera Quartus II містять софтвер, що дозволяє заливати конфігурацію хардвера в плати, з якими я працюю, з допомогою простого USB кабелю без жодних доповнень з боку користувача. До таких плат відносяться Digilent Basys 3, Nexys 4 DDR, Terasic DE0-CV та інші.

На відміну від конфігурації хардвера, софтвер в стандартному пакеті MIPSfpga Getting Started заливається через текстовий інтерфейс EJTAG, використовуючи додаткову плату, яка називається BusBlasterу комбінації з софтвером, який називається OpenOCD. На жаль, комбінація BusBlaster / Open OCD є досить сирий — у неї можуть бути проблеми з драйверами в деяких версіях Windows і Linux-а. Крім цього, BusBlaster нетривіально купити в Росії. Тому перед семінарами я задумався про те, як заливати софтверну частина системи в MIPSfpga без BusBlaster/OpenOCD.

mipsfpga_setup_on_de0_cv_for_seminars_in_russia_20151018_114617

2. Який саме файл потрібно распарсировать і залити в пам'ять системи

Софтвер, яку потрібно залити в MIPSfpga — це звичайна програма на Сі або асемблері, яка компілюється і лінкуются звичайним GCC файл у форматі ELF. Пакет GNU також містить програму objcopy, яка вміє перетворювати ELF в різноманітні формати, в тому числі текстові — Intel HEX, Motorola S-record формат, який розуміє вбудована підпрограма $readmemh в мові опису апаратури Verilog. Спочатку я хотів використовувати формат Intel HEX, але виявив, що його не підтримує той з варіантів objcopy для MIPS, який я використовував. Другим варіантом було використовувати формат
Motorola S-record, і з ними все вийшло добре. Ось шпаргалка з цього формату:

Motorola_SREC_Chart

3. Чим заливати і як — варіанти інженерних рішень

3.1. Найпростіший спосіб уникнути заливки софтвера через BusBlaster — це просто помістити його в систему MIPSfpga під час її синтезу — процесу, при якому код на мові опису апаратури Verilog перетворюється в граф з логічних елементів і тригерів. Як програма-синтезатор Xilinx ISE/Vivado, так і Altera Quartus II розпізнають під час синтезу конструкцію мови Verilog $readmemh, і створюють пам'ять, яка ініціалізується даних з текстового файлу. На жаль таке рішення дуже непрактично, якщо користувач збирається часто перекомпілювати софтвер, так як кожен раз йому доведеться ще й пересинтезировать хардвер, що може займати від 15 до 30 хвилин.

3.1.1. Варіант можливості 3.1 — часткова переконфігурація ПЛІС. Я її не досліджував, так як дізнався, що і в такому разі чекати доведеться довго, а я хочу чекати не більше декількох секунд. Крім цього, я хотів що-небудь, не залежне від виробника ПЛІС-ів.

3.2. Найбільш інтуїтивно очікуваний спосіб для програмістів вбудованих систем — це частина програми фіксованої, яка поміщається в систему під час її синтезу (завантажувач), а іншу частину програми — завантажується з пк через послідовний порт. Завантажувальна програма мала б ініціювати трансфер завантажується програми з PC, отримувати цю програму у вигляді даних, які потім записувати в пам'ять. Такий метод описав @Frantony в замітці на Хабре «MIPSfpga: поза канону»

3.2.1. Метод 3.2. є дві варіації — передавати завантажену програму у вигляді текстового файлу в форматі типу Motorola S-record парсировать цей файл у завантажувачі на платі, або, альтернативно, парсировать текстовий файл на PC і передавати дані на плату в бінарному вигляді.

3.3. Метод, який я використовував весь прийом даних, парсирование і розпихування даних з пам'яті зроблено повністю в хардвере, реалізованому в ПЛІС-тобто Перевага цього методу — софтвер на платі взагалі не знає про існування хардверного завантажувача. Коли хардверный завантажувач зауважує дані, що йдуть з PC, він ставить процесор на скидання (reset), отримує і розміщує в пам'яті всі дані, знімає процесор з скидання, після чого процесор починає читати і виконувати код обробника виключення скидання.

3.3.1. В процесі обговорення завдання з іншими користувачами і розробниками MIPSfpga також висловлювалася ідея зробити повноцінний DMA-порт для запису даних з PC в пам'ять одночасно з роботою процесора з пам'яттю (а не коли процесор стоїть на reset-е), але вона була відкинута як дуже складна і за великим рахунком безглузда для типів задач, в яких передбачалося використовувати MIPSfpga під час семінарів в Росії.

4. Як відбувається з'єднання з PC?

Послідовний порт, — це дуже давнє винахід. UART / RS-232C з'явився ще в кінці 1960-х років. Все PC в 1980-ті були з COM-портами, які можна було писати як у файл. Ви не повірите, але це пережило MS-DOS і залишилося в Windows досі. Так, так, щоб передати файл з PC на зовнішній послідовний порт, ви і зараз можете написати в командному рядку «type ім'я файлу COMномер порту»:



В Лінуксі таке з'єднання теж є (хоча MIPSfpga приєднаний до Лінукс я ще не пробував, але це пробував один товариш в Італії, який надіслав мені про це емейл). Користувач Лінукса, який копіює дані в файл, відповідний COM-порту, повинен входити в групу dialup:

stty -F /dev/ttyUSB0 raw 115200
cat srec program.rec > /dev/ttyUSB0

При цьому стародавні порти RS-232C в сучасні PC не ставлять, замість цього роблять «віртуальний COM-порт» через USB, використовуючи ось такий перехідник на основі чіпа FT232RL від компанії FTDI (Увага! У цього чіпа є багато глюкавых підробок) Також звертаю увагу, що для роботи з ПЛІС перемикач 3.3/5V на перехіднику потрібно поставити на 3.3 V, інакше теоретично можна пошкодити піни/висновки ПЛІС-а, які як правило ніжніше, ніж наприклад у мікроконтролерів:

IMG_1423

Крім перехідника, що зображено на фотографії вище, для з'єднання PC і UART на FPGA можна використовувати кабель під назвою PL2303TA USB TTL to RS232 Converter Serial Cable module for win XP/VISTA/7/8/8.1. Це кабель зручно використовувати для невеликих плат типу Terasic DE0-Nano з male GPIO висновками. На сайтах типу AliExpress також продається більш дешевий кабель, заснований на чіпі PL2303HXале у цього чіпа були якісь проблеми сумісності з Windows 8.x, тому краще все-таки використовувати кабелі на основі PL2303TA:

IMG_0099

5. Куди треба було залити отримані дані з PC?

До того, як я вставив модулі завантаження завантажується програми з PC в пам'ять синтезованої системи MIPSfpga+ (так я назвав свій варіант MIPSfpga), її модульна структура виглядала так:



Що знаходиться в кожному модулі:

  • de0_cv — зовнішній модуль, специфічний для кожного типу FPGA-плати. Висновки цього модуля відповідають фізичним висновків на самій мікросхемі. Конкретний модуль de0_cv написаний для плати Terasic DE0-CV з ПЛІС Altera Cyclone V
  • mfp_single_digit_seven_segment_display display_0, display_1, ... — драйвери семисегментного індикатора для альтеровских плат (по одному на цифру)
  • mfp_system — системний модуль, однаковий для всіх FPGA плат
    • m14k_top — верхній модуль мікропроцесорного ядра MIPS microAptiv UP (також званих MIPS microAptiv MPU) назва m14k залишилося від попередньої версії процесора MIPS M14Kc
    • mfp_ejtag_reset — допоміжний модуль для скидання налагоджувального інтерфейсу EJTAG
    • mfp_ahb_lite_matrix — модуль, який об'єднує в себе блоки пам'яті, схемотехническую реалізацію логіки шини AHB-Lite і логіку вводу-виводу. Остання пов'язує адреси на шині, що приходять від софтвера, з сигналами хардверных пристроїв вводу-виводу — кнопками, LED-індикаторами і т. д.
      • mfp_ahb_lite_decoder — модуль, який декодує адресу на шині AHB-Lite і визначає, який з ведених пристроїв (блоків пам'яті або модуль логіки вводу-виводу) повинен обробляти транзакцію на шині
      • mfp_ahb_ram_slave reset_ram — оболонка блоків пам'яті, що реалізує протокол веденого пристрою шини AHB-Lite. Дана група блоків (reset_ram) призначена для частини програми, яка стартує відразу після виходу процесора зі стану скидання / reset
        • mfp_dual_port_ram i0-i3 — модулі, код на верилоге в яких синтезатор розпізнає як вказівку створити блокову пам'ять всередині ПЛІС. Щоб синтезатор правильно сприймав цей код, його потрібно писати певним чином. Блоків чотири з шириною пам'яті 8 біт (замість 1 блоку шириною 32 біта) щоб можна було робити запис одного байта з шини AHB-Lite шириною 4 байти (синтезатор не розуміє пам'ять з маскою)
      • mfp_ahb_ram_slave ram — ще одна оболонка блоків пам'яті, що реалізує протокол веденого пристрою шини AHB-Lite. Дана група блоків (ram) призначена для основної частини програми, яка працює на кешованої пам'яті
        • mfp_dual_port_ram i0-i3 — див. аналогічні чотири блоки вище
      • mfp_ahb_gpio_slave — модуль веденого пристрою для вводу-виводу загального призначення (GPIO — General Purpose Input / Output). Відображає на шині адреси, що приходять від софтвера на сигнали хардверных пристроїв вводу-виводу — кнопки, LED-індикатори і т. д.
      • mfp_ahb_lite_response_mux — допоміжний модуль для роботи шини AHB-Lite — мультиплексор, щоб направити провідного пристрою (мікропроцесорному ядру) дані читання з правильного блоку пам'яті або модуля вводу-виводу
    • mfp_pmod_als_spi_receiver — модуль, який реалізує варіант протоколу SPI для датчика освітлення Digilent PmodALS, одного з прикладів пристроїв, під'єднаних до системи MIPSfpga+. В цьому пості даний модуль не обговорюється, можливо я напишу окремий пост про інтеграцію датчика освітлення з MIPSfpga+


6. Як змінилася ієрархія системи, коли я вставив у неї хардверный завантажувач?



Чотири нових модуля:

  • mfp_ahb_lite_matrix_with_loader — ставиться на місце модуля mfp_ahb_lite_matrix з попередньої ієрархії. mfp_ahb_lite_matrix_with_loader містить модуль mfp_ahb_lite_matrix, так і три модуля з новою функціональністю:
    • mfp_uart_receiver — отримує дані з PC через UART і перетворює їх в потік байтів / алфавітно-цифрових символів
    • mfp_srec_parser — парсирует ланцюжка байтів, отриманих від модуля mfp_uart_receiver як текст у форматі Motorola S-Record і генерує послідовність транзаций (адреса/дані) щоб наповнити пам'ять синтезованої системи заданими в тексті даними
    • mfp_srec_parser_to_ahb_lite_bridge — перетворює транзакції, отримані від модуля mfp_srec_parser в транзакції, які відповідають протоколу шини AHB-Lite. Також перетворює віртуальні адреси, які використовує софтвер, у фізичні адреси, які використовує хардвер, з допомогою простого фіксованого відображення.


Нижче наведена схема на рівні ієрархії модуля mfp_ahb_lite_matrix_with_loader, отримана після компіляції коду на верилоге, але до повного синтезу (оптимізації, відображення на ПЛІС-специфічні елементи, розміщення та трасування). Зверніть увагу на мультиплексор між mfp_srec_parser_to_ahb_lite_bridge mfp_ahb_lite_matrix, він направляє до підсистеми пам'яті і введення-виводу або транзакції від мікропроцесорного ядра, або транзакції від хардверного завантажувача:

mfp_ahb_lite_matrix_with_loader

7. Пару слів про послідовний порт, UART

Тема UART обговорювалася на Хабре багато разів, в тому числі зовсім недавно, тому я не буду затримуватися на ній в подробицях. Моя реалізація приймача використовує найпростіший варіант протоколу UART, без контрольних сигналів, з одним початковий бітом, без перевірок парності, з фіксованою швидкістю передачі і для фіксованої частоти синхросигналу / сигналу тактової частоти / clock. Модуль mfp_uart_receiver отримує дані з сигналу RX послідовно і виводить 8-бітний байт паралельно, коли він готовий. Модуль містить кінцевий автомат, який чекає негативного фронту сигналу RX (таким чином визначаючи початковий біт), після чого зчитує біти даних в правильні моменти часу, які визначає, вважаючи такти з допомогою лічильника. Так як кількість тактів на кожен біт досить велике, 50,000,000 Hz / 115,200 baud = 434 тактів (або 217 тактів для 25 MHz), прийом даних відбувається досить надійно. Ось інтерфейс модуля:



Повний код модуля — http://github.com/MIPSfpga/mipsfpga-plus/blob/master/mfp_uart_receiver.v.

Схема модуля mfp_uart_receiver після первинної компіляції:

mfp_uart_receiver

8. І нарешті обіцяне: парсер тексту у форматі Motorola S-Record голим хардвером, без процесора і без софтвера

Модуль mfp_srec_parser отримує байти з модуля mfp_uart_receiver і парсирует їх як текст у форматі Motorola S-record, використовуючи кінцевий автомат. Під час парсирования відбувається також формування транзакцій до пам'яті синтезованої системи MIPSfpga+; ці транзакції заповнюють пам'ять байтами, заданими з парсированного тексту по заданим у тексті ж адресами. Інтерфейс модуля:



Визначаємо ідентифікаторів констант для кінцевого станів автомата і використовуваних ASCII символів:



Комбінаційна логіка для перетворення символьних констант '0', '1',… '9', 'A', 'B',… 'F' четырехбитовые числа 0, 1, 2,… 9, 10, 11,… 15.



Змінні для кінцевого автомата. Зліва — нове значення, що створюється в поточному циклі/такті, праворуч — записане в регістр / D-тригер / D-flip-flop значення, сформований у попередньому циклі. Зауважу, що з верилоговского «reg» синтезатор далеко не завжди робить D-тригер / регістр в хардверном сенсі. Ключове слово «reg» потрібно сприймати тільки як вид змінної, якій можна робити присвоювання всередині «always»-блоків:

Присвоювання після визначення змінних — це присвоювання висновків модуля згенерованих адрес (які до цього записуються в регістри):



Логіка кінцевого автомата складається з комбінаційної частини і последовательностной частини. Якщо ви не знайомі з цими концепціями, ви можете прочитати їх у безкоштовному підручнику Харріс & Харріс.

У комбінаційної частини ми обчислюємо значення для наступного стану, причому під словом «стан» мається на увазі не тільки група D-тригерів, в яку перетворюється мінлива reg_state, але і взагалі всі D-тригери / D-flip-flop / хардверные регістри в схемі (всі три терміна в контексті цього поста взаємозамінні). Є туристи, які кажуть що це «кінцевий автомат», а «кінцевий автомат з даними», але ми залишимо цих схоластів і їх чортів на кінчику голки в спокої.

Ось початок комбінаційної частини. Для того, щоб не стежити за небажаним у методології синхронного дизайну появою засувок (D-latch), присвоїмо усім обчислюється змінним значення за замовчуванням в самому початку комбінаційного always-блоку:



Будь-які зміни відбуваються тільки коли ми отримуємо нову літеру від UART-приймача («if (char_ready)»). У нашому кінцевому автоматі спочатку ми чекаємо появи літери 'S', після чого парсируем тип запису (нас цікавить тип '3') та адресу, за якою ми будемо записувати наступні байти:



Тепер починаємо парсировать дані і одночасно генерувати транзакції адреса/дане на виведення з модуля:



На позитивному фронті генератора тактового сигналу записуємо обчислені раніше значення в регістри, які не вимагають скидання:



А тепер робимо запис у регістри, які вимагають скидання — небудь щоб почати роботу кінцевого автомата з однозначної стану, або регістри, які визначають контролюючі сигнали на виході з модуля:



Сигнал in_progress («в процесі») включений з моменту розпізнавання першого запису з адресою (типу S3) і вимикається, коли модуль розпізнає останній запис у файлі (типу S7). Цей сигнал може виводитися на зовнішній індикатор на платі, він також використовується для мультиплексора mfp_ahb_lite_matrix_with_loader і визначає, пише в пам'ять мікропроцесорне ядро або хардверный завантажувач. Крім цього, in_progress використовується для скидання мікропроцесорного ядра, щоб воно було «вирубано», поки хардверный завантажувач пише в пам'ять. Коли софтвер в пам'ять записаний, мікропроцесор «прокидається» і починає читати інструкції (з фіксованого фізичної адреси 1FC0_0000).



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



Логіка для обчислення контрольних сум і порівняння їх з контрольними сумами з S-Record тексту. Працює паралельно з головним кінцевим автоматом і використовує його стану:



Генерація сигналу помилки. Хардверный парсер навіть повідомляє користувачеві, на якому рядку трапилася помилка:



Повний код модуля — http://github.com/MIPSfpga/mipsfpga-plus/blob/master/mfp_srec_parser.v

9. Пару слів про міст до шині AHB-Lite

Модуль mfp_srec_parser_to_ahb_lite_bridge перетворює транзакції адреса/дане, отримані з модуля mfp_srec_parser в транзакції шини AHB-Lite, яку використовує MIPSfpga.

Модуль також редагує адреси — перетворює віртуальні адреси, які використовує софтвер, у фізичні адреси, які використовує хардвер. Хоча у процесора MIPS microAptiv UP є MMU TLB, яке дозволяє гнучке і складне відображення віртуальних адрес у фізичні, але в моїх прикладах використання MIPSfpga перетворення просте і фіксоване — просте обнулення трьох верхніх бітів адреси. Якщо вас цікавить робота пристрою керування віртуальною пам'яттю в MIPSfpga, ви можете подивитися презентацію російською мовою «Пристрій управління пам'яттю в процесори MIPS».

Код мосту mfp_srec_parser_to_ahb_lite_bridge:

http://github.com/MIPSfpga/mipsfpga-plus/blob/master/mfp_srec_parser_to_ahb_lite_bridge.v



Схема модуля mfp_srec_parser_to_ahb_lite_bridge після первинної компіляції:

mfp_srec_parser_to_ahb_lite_bridge

І нарешті про саму шину AHB-Lite, яка використовується для з'єднання пристроїв в системах на кристалі.

Нижче — уривок з документації від Imagination Technologies, яку можна завантажити по наступній інструкції.



Зокрема, ви можете побачити, чому передачу даних доводиться затримувати на один такт по відношенню до передачі адреси. У протоколі AHB-Lite адресу нової транзакції викладається на шині одночасно з даними з попередньої операції:



Схема модуля mfp_ahb_lite_matrix після первинної компіляції. Цей модуль містить у собі три ведених (slave) модуля — два блоки пам'яті і модуль, який відображає звернення до пам'яті софтвера на роботу вводу-виводу загального призначення — GPIO (General Purpose IO):

mfp_ahb_lite_matrix

10. І що тепер? Продовження, доповнення і пропозиції

У цьому пості я описав лише один з аспектів проекту MIPSfpga і його поліпшення MIPSfpga+, яке я зробив, щоб не мучитися з проблемами Bus Blaster / Open OCD під час подорожі по Росії наприкінці минулого року. Зауважу, що якщо ви хочете використовувати відладчик на основі GDB з MIPSfpga, то вам все одно доведеться використовувати Bus Blaster або інший налагоджувальний адаптер, що підтримує EJTAG.

Але тематика MIPSfpga набагато більше. Адже пакет містить індустріальний процесор, який використовується в нових продуктах від Samsung, Microchip і інших компаній — і ви, дорогі читачі, можете експериментувати з його структурою, використовуючи той же код, який використовують і інженери в цих компаніях. Ви можете написати свій модуль кешу з іншою політикою виштовхування рядків, розробляти багатоядерні системи, прикручувати до MIPSfpga різну периферію. Якщо вам цікаво зробити проект з MIPSfpga і ви при цьому працює в якомусь провінційному вузі, у якого важко отримати бюджет на покупку FPGA плат — ви можете отримати одну плату безкоштовно, правда їх залишилося мало — подробиці в «Роздача слонів: FPGA плати для освітніх проектів з MIPSfpga».

Також на Хабре вже була замітка про те, як прикрутити до MIPSfpga співпроцесор — див. https://habrahabr.ru/post/276205/.

Які з тем, порушених у цьому пості ви хотіли б повніше розкрити?

/>
/>


<input type=«checkbox» id=«vv71807»
class=«checkbox js-field-data»
name=«variant[]»
value=«71807» />
Покрокове пояснення, як кодувати найпростіший кінцевий автомат на Verilog та/або VHDL
<input type=«checkbox» id=«vv71809»
class=«checkbox js-field-data»
name=«variant[]»
value=«71809» />
Покрокове пояснення, як під'єднати до системи MIPSfpga яке-небудь периферійний пристрій
<input type=«checkbox» id=«vv71811»
class=«checkbox js-field-data»
name=«variant[]»
value=«71811» />
Як спостерігати роботу кеша в «сповільненій зйомці» роботи процесора на частоті 1 такт в секунду
<input type=«checkbox» id=«vv71813»
class=«checkbox js-field-data»
name=«variant[]»
value=«71813» />
Як спостерігати в «сповільненій зйомці» роботу конвеєра процесора і його байпаси
<input type=«checkbox» id=«vv71815»
class=«checkbox js-field-data»
name=«variant[]»
value=«71815» />
Використання MIPSfpga для ілюстрації роботи переривань
<input type=«checkbox» id=«vv71817»
class=«checkbox js-field-data»
name=«variant[]»
value=«71817» />
Використання MIPSfpga для створення багатоядерних систем
<input type=«checkbox» id=«vv71819»
class=«checkbox js-field-data»
name=«variant[]»
value=«71819» />
У мене є інша ідея (пояснити в коментарях)

Проголосувало 2 людини. Утримався 1 людина.


Тільки зареєстровані користувачі можуть брати участь в опитуванні. Увійдіть, будь ласка.


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.