State_Maschine - Page 4

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From Russian to

Threaded View
State_Maschine
Здравствуйте, Уважаемый Slav!

Fri Jul 07 2006 16:16, Slav Matveev wrote to Olga Nonova:

 ON>> .... (см. мой пример хранения кода состояния в
 ON>> регистре порта вывода).

 SM>     хотелось бы взглянуть на реальный проект, где код состояние
 SM>     хранится в регистре порта в/в, и как это можно перевести
 SM>     на предложенный (*f)();


Вспомнила! Видела у Phillips-а пример решения конечного автомата для ихнего
варианта I2C. Там статус-регистр I2C использовался напрямую в качестве
младшего байта адреса ветвления. Старщий назначался принудительно в свободной
странице кодов. Все это, естественно, на ассемблере (Metalink). Интересно, как
бы такое же реализовать на С ?

Всего Вам Хорошего
Ольга
 


Re: State_Maschine

Quoted text here. Click to load it

  http://www.softcraft.ru , раздел автоматы. Там ещё ссылки есть.

Quoted text here. Click to load it

  Афтары жжоте. При достаточно большом числе вариантов это реализуется
(опреатор switch) -- таблично.

Quoted text here. Click to load it

  А класс со всми насквозь виртуальнымми функциями -- это не проигрыш в
скорости. А то у некоторых архитектур ещё сложности с вызовом по
ссылке...


Re: State_Maschine

Quoted text here. Click to load it

  Ещё интересный вариант -- указатель на функцию-состояние. Впрочем, я
склоняюсь к тому, чтобы иметь состояние представимое в числовом виде
(как в случае с switch-case) и дополнительно указатель на функцию, для
быстрого выбора нужного состояния (первое нужно для просверки состояния
в других автоматах, а действия в разных состояниях могут быть объединены
в одну функцию). Плюс нужен какой-то планировщик для запуска автоматов.
Иначе неэффективно, тратится масса времени на бесполезные проверки
условий переходов.


Re: State_Maschine
Tue Jul 04 2006 22:47, Kirill Frolov wrote to Olga Nonova:

 >> Очень хочется узнать, как наиболее эффективно в С реализовать subj.
 >> Простейший  прием через оператор switch мне известен, но ведь он, похоже,
 >> работает

 KF>   Ещё интересный вариант -- указатель на функцию-состояние. Впрочем, я
 KF> склоняюсь к тому, чтобы иметь состояние представимое в числовом виде
 KF> (как в случае с switch-case) и дополнительно указатель на функцию, для
 KF> быстрого выбора нужного состояния (первое нужно для просверки состояния
 KF> в других автоматах, а действия в разных состояниях могут быть объединены
 KF> в одну функцию). Плюс нужен какой-то планировщик для запуска автоматов.
 KF> Иначе неэффективно, тратится масса времени на бесполезные проверки
 KF> условий переходов.

Беспокойство о времени выполнения switch-case означает или неправильный выбор
процессора под задачу, или неправильное структурирование программы.

Короче, увольнять за служебное несоответсвие.

"Resistance is futile"


Re: State_Maschine

Quoted text here. Click to load it

  Речь идёт не о времени switch-case, а о том, что оно всё в цикле, пока
добежит до нужного автомата -- оборот в несколько десятков миллисекунд.
Почему так долго -- а потому, что бесполезные проверки условий (и отнюдь
не switch-CASE), которые никогда (почти) не выполняются. Например,
проверки состоянийх других автоматов. Т.е. налицо отсутствие
эффективного механизма взаимодействия между автоматами. Почему я и
предлагаю организацию механизмов аналогичных используемым в типично
планировщике многозадачной/многопоточной ОС. Т.е. проверку условий,
например, заменить на сигнализацию семафором.


Re: State_Maschine
Hello Dmitry!

04 Jul 06 07:18, you wrote to Olga Nonova:

 ON>> Очень хочется узнать, как наиболее эффективно в С реализовать
 ON>> subj. Простейший прием через оператор switch мне известен, но
 ON>> ведь он, похоже, работает перебором всех case-ов.

 DO> Откройте для себя оператор break

Причем здесь break? break на уровне машинного языка заменяется на единственный
оператор перехода. А оператор switch в общем случае заменяется на цепочку
условных операторов перехода по одному на условие. Иначе говоря, на каждый case
N мы получаем movf state,w; xorlw N; btfsc status,z; bra next_case (Это я для
пика пишу - можно было бы поставить и любую другую машину) - и таких сравнений
много!



Anatoly


Re: State_Maschine

X-Virus-Scanned: amavisd-new at bezeqint.net

Hello, Anatoly Mashanov!
You wrote in conference fido7.ru.embedded to Dmitry Orlov on Tue, 04 Jul
2006 23:27:48 +0400:


 ON>>> Очень хочется узнать, как наиболее эффективно в С реализовать
 ON>>> subj. Простейший прием через оператор switch мне известен, но ведь
 ON>>> он, похоже, работает перебором всех case-ов.

 DO>> Откройте для себя оператор break

 AM> Причем здесь break?

Если не нужно все перебирать.

 AM> break на уровне машинного языка заменяется на единственный оператор
 AM> перехода. А оператор switch в общем случае заменяется на цепочку
 AM> условных операторов перехода по одному на условие.

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

 AM>  Иначе говоря, на каждый case N мы получаем movf state,w; xorlw N;
 AM> btfsc status,z; bra next_case (Это я для пика пишу - можно было бы
 AM> поставить и любую другую машину) - и таких сравнений много!

А вот что настоящий компилятор пишет для случая сравнений:

    46                           ;bits.c: 28: switch (c)
    47  07E3  2FED                      goto    l5
    48  07E4                     l6
    49                           ;bits.c: 29: {
    50  07E4  3002                      movlw   2
    51  07E5  2FEB                      goto    L3
    52  07E6                     l7
    53                           ;bits.c: 31: case 'c': f(5); break;
    54  07E6  3005                      movlw   5
    55  07E7  2FEB                      goto    L3
    56  07E8                     l8
    57                           ;bits.c: 32: case 'f': f(7); break;
    58  07E8  3007                      movlw   7
    59  07E9  2FEB                      goto    L3
    60  07EA                     l9
    61                           ;bits.c: 33: case 'd': f(3); break;
    62  07EA  3003                      movlw   3
    63  07EB                     L3
    64  07EB  27D7                      fcall   _f
    65  07EC  2FFC                      goto    l4
    66  07ED                     l5
    67  07ED  1283                      bcf     3,5
    68  07EE  1303                      bcf     3,6     ;carry unused
    69  07EF  0820                      movf    _c,w
    70  07F0  3A61                      xorlw   97
    71  07F1  1903                      btfsc   3,2
    72  07F2  2FE4                      goto    l6
    73  07F3  3A02                      xorlw   2
    74  07F4  1903                      btfsc   3,2
    75  07F5  2FE6                      goto    l7
    76  07F6  3A07                      xorlw   7
    77  07F7  1903                      btfsc   3,2
    78  07F8  2FEA                      goto    l9
    79  07F9  3A02                      xorlw   2
    80  07FA  1903                      btfsc   3,2
    81  07FB  2FE8                      goto    l8
    82  07FC                     l4

Вариант с таблицей слишком громоздкий для здесь.

dima
http://www.dorlov.no-ip.com
http://dimorlus.dynalias.com




State_Maschine
Привет, Anatoly !


 05 Jul 06 , 00:27  Anatoly Mashanov писал к Dmitry Orlov:

ON>>> Очень хочется узнать, как наиболее эффективно в С реализовать
ON>>> subj. Простейший прием через оператор switch мне известен, но
ON>>> ведь он, похоже, работает перебором всех case-ов.

DO>> Откройте для себя оператор break

AM> Причем здесь break? break на уровне машинного языка заменяется на
AM> единственный оператор перехода. А оператор switch в общем случае
AM> заменяется на цепочку условных операторов перехода по одному на
AM> условие. Иначе говоря, на каждый case N мы получаем movf state,w;
AM> xorlw N; btfsc status,z; bra next_case (Это я для пика пишу - можно
AM> было бы поставить и любую другую машину) - и таких сравнений много!

Поиск - не обязательно линейный. Даже без инструкции табличного перехода можно
вместо
cmp ax,0
je label_0
cmp ax,1
je label_1
....

сделать поиск половинным делением с o(log(n)) сравнениями вместо n.

.                                            С уважением, Hикита.
icq:240059686, lj-user:nicka_startcev
... Вигвам из слоновой кости

Re: State_Maschine
Hello Olga!

07 Jul 06 13:48, Olga Nonova wrote to Slav Matveev:


 SM>>     Вам шашечки или ехать?

 ON> Просто обращаю Ваше внимание на недостатки табличного метода, когда
 ON> выражение при switch дает хоть и целые, но не из натурального ряда
 ON> значения.

В смысле с пропусками.

 ON> И эта ситуация не высосана из пальца, как тут пытаются
 ON> представить некоторые- (см. мой пример хранения кода состояния в
 ON> регистре порта вывода).

А это безотносительно к языку программирования - в любом случае таблица будет с
"дырками". Hа асме, правда, можно эти дырки заюзать под какие-нибудь константы,
но это только в условиях жесточайшей экономии памяти и без расчета на
последующие изменения, т.е. по-хорошему так делать нельзя.

Впрочем, в таких случаях можно пользовать две таблицы: одна, 256 байт,
перекодирует условие ветвления в набор кодов от 0 до N без дырок, а вторая, по
которой делать switch, нормальная адресная. Тут уже язык без разницы: что на
асме сделать переход по одному из адресов, что хороший сишный оптимизатор так
switch отработает.



Всего доброго!

 А. Забайрацкий.



Re: State_Maschine
Привет, Olga !


 04 Jul 06 , 18:34  Olga Nonova писал к Alexandr Torres:

AT>> Дело не в ограничениях на тип в свитче, а на ДHК разработчика,
AT>> пишущего стей-машину.

ON> А как быть с ДHК авторов C++?

Hе пользоваться этим ДHК. Как же ещё?


.                                            С уважением, Hикита.
icq:240059686, lj-user:nicka_startcev
... Вигвам из слоновой кости

Re: State_Maschine
Hi Olga!

04 Jul 06 18:48, Olga Nonova wrote to Slav Matveev:

 ON> Проблема в другом. В С++ нормально, но неэффективно для ембеднутых
 ON> работает такая конструкция переключателя:

 ON> switch (SomeChar) {
 ON>   case 'A': Do_A(); break;
 ON>   case 'B': Do_B(); break;
 ON>   default: Dо_Default(); break;
 ON> }

 ON> Допустима в С (без плюсов) такая конструкция из значений case-ов? И
 ON> что компильнет компилятор- тоже очень интересно.

    сударыня! на www.openwatcom.com раздают забесплатно неплохой
    компилятор С/С++. Почему бы вам не заиметь себе компилятор и
    не поэкспериментировать в какой ассемблерный код какой
    исходный текст преобразуется?
    Может быть на понимание вас натолкнет ругань
    комплятора: case label does not reduce to an integer constant ?

    Ваш же детский лепет транслируется в код:

        movb    SomeChar, %al
        movsbl  %al,%eax
        movl    %eax, -4(%ebp)
        cmpl    $65, -4(%ebp)
        je      .L3
        cmpl    $66, -4(%ebp)
        je      .L4
        jmp     .L2
.L3:
        call    Do_A
        jmp     .L5
.L4:
        call    Do_B
        jmp     .L5
.L2:
        call    Do_Default
.L5:

    В случае с большим количеством case'ов в менее красивый код
    с jmp'ом по таблице. Если действительно только Do_A(), а не
    { ... } в ассемблере можно было бы обойтись call'ом по таблице.
    но никто не мешает вместо такого swtich'а сделать массив
    указателей на функции и вызывать функцию по индексу SomeChar-'A'.


    ps. указанный код сгенерирован gcc version 4.0.0 20050519 (Red Hat 4.0.0-8)


                                                   Slav.

State_Maschine
Здравствуйте, Уважаемый Slav!

Wed Jul 05 2006 12:48, Slav Matveev wrote to Olga Nonova:

 ON>> switch (SomeChar) {
 ON>>   case 'A': Do_A(); break;
 ON>>   case 'B': Do_B(); break;
 ON>>   default: Dо_Default(); break;
 ON>> }

 ON>> Допустима в С (без плюсов) такая конструкция из значений case-ов? И
 ON>> что компильнет компилятор- тоже очень интересно.

 SM>     сударыня! на www.openwatcom.com раздают забесплатно неплохой
 SM>     компилятор С/С++. Почему бы вам не заиметь себе компилятор и
 SM>     не поэкспериментировать в какой ассемблерный код какой
 SM>     исходный текст преобразуется?
 SM>     Может быть на понимание вас натолкнет ругань
 SM>     комплятора: case label does not reduce to an integer constant ?

 SM>     Ваш же детский лепет транслируется в код:

 SM>         movb    SomeChar, %al
 SM>         movsbl  %al,%eax
 SM>         movl    %eax, -4(%ebp)
 SM>         cmpl    $65, -4(%ebp)
 SM>         je      .L3
 SM>         cmpl    $66, -4(%ebp)
 SM>         je      .L4
 SM>         jmp     .L2
 SM> .L3:
 SM>         call    Do_A
 SM>         jmp     .L5
 SM> .L4:
 SM>         call    Do_B
 SM>         jmp     .L5
 SM> .L2:
 SM>         call    Do_Default
 SM> .L5:

Иными словами, видим полный перебор case-ов. Что и требовалось доказать.

 SM>     В случае с большим количеством case'ов в менее красивый код
 SM>     с jmp'ом по таблице.

Да-да, речь идет именно о количестве case-ов в районе десятка. И как же тогда
получить "красивый код" с таблицей jmp-ов, если выражение при switch не дает,
как я Вам представила на примере, регулярных значений из ряда 0,1,2...? Hикак
этого у Вас не получится, а по-прежнему будет тухлый перебор всех подряд.

 Если действительно только Do_A(), а не
 SM>     { ... } в ассемблере можно было бы обойтись call'ом по таблице.
 SM>     но никто не мешает вместо такого swtich'а сделать массив
 SM>     указателей на функции и вызывать функцию по индексу SomeChar-'A'.

Выношу на Ваш суд мое решение State_Machine, максимально приближенное к
оптимальному ассемблерному решению ветвления по указателям. Обращаю особое
внимание- мой вариант не требует ни целочисленных индексов, ни таблиц jmp-ов.
Ветвление производится максимально быстро и с фиксированной задержкой.

//Вот три макроса для построения любой State_Machine.

#define StateMachine(MyName) void(*MyName)()  
#define ExecStateOf(StateMachine) (*StateMachine)()  
#define SetState(StateMachine,NewState) StateMachine=NewState;

//Среди переменных задачи декларируете указатель

    StateMachine(SM);

//И пишете действия в состояниях в виде функций, например, их три штуки
void State3()
void State2()
void State1()

//Затем в исполняемых кодах инициализируете конечный автомат
    SetState(SM,State1);
// и приступаете к циклическим вызовам его действий
    ExecStateOf(SM);
//Внутри этих действий Вам не возбраняется переключать состояния
    SetState(SM,StateN);

У меня, к сожалению, не получается получить ассемблерный текст watcom-овского
компилятора. Может Вы попробуете оценить эффективность такого решения? Hиже
полный исходный текст консольного приложения для C++. Сколько в нем занимает
выполнение непосредственно ExecStateOf(SM)? Была бы чрезвычайно благодарна.

Всего Вам Хорошего
Ольга


#include <iostream>
#include <stdlib.h>

#define StateMachine(MyName) void(*MyName)()  
#define ExecStateOf(StateMachine) (*StateMachine)()  
#define SetState(StateMachine,NewState) StateMachine=NewState;

using namespace std;

   StateMachine(SM);

void State3() {cout << "3" << endl;}
void State2() {cout << "2" << endl; SetState(SM,State3);}
void State1() {cout << "1" << endl; SetState(SM,State2);}

int main(int argc, char *argv[])
{
   SetState(SM,State1);
   ExecStateOf(SM);
   ExecStateOf(SM);
   ExecStateOf(SM);

   system("PAUSE");    
   return 0;
}


Re: State_Maschine

Quoted text here. Click to load it

  Не полный, а до первого совпадения.  Что это доказывает -- я не знаю.
Но умаю, что ничего.

Quoted text here. Click to load it

  Компилятр в отличии от вас не дурак и понимает, что в случае
небольшого числа вариантов таблица -- неоптимальный вариант.

Quoted text here. Click to load it

  Думаешь, если Писать В дРеБезЖащёМ рГисТРе -- оно лучше заработает?
Вот что хуже -- точно. Я даже скажу почэему -- макрос не отличить от
функции.

Quoted text here. Click to load it

  Поная ерунда. В Keil для x51 замучаешься ручками (придётся тки скрипт
написать) линкерный файл править, догадайся для чего...  Плс я уже писал
-- числовой номер он важен и первичен. А это -- лишь мето д оптимизации.

Quoted text here. Click to load it

  Обязательно в дребезжащем регистре. А то не заработает!
И ещё незабудьте озаботиться вопросом области видимости переменных
вашего автомата.

Quoted text here. Click to load it

  При этом он уже выполняет переход из /неизвестного состояния/ в
первое. Ключевое слово -- неизвестного.

Quoted text here. Click to load it
                    ^^^^^^^^^^
Quoted text here. Click to load it

  Вас так беспокоил десяток-другой тактов на switch-case?

Quoted text here. Click to load it

  http://www.softcraft.ru . Там проделана достаточно большая работа.

Quoted text here. Click to load it


  Это не C++, это -- херня.


Re: State_Maschine
Здравствуйте, Уважаемый Kirill!

Wed Jul 05 2006 21:36, Kirill Frolov wrote to Olga Nonova:

 KF>   Это не C++, это -- херня.

Херня, оно может быть и херня. Hо, ведь прекрасно работает! Очень быстро и с
фиксированным временем на любое ветвление. Что кроет любые Ваши обсирания
вокруг да около.

Всего Вам Хорошего
Ольга


Re: State_Maschine

Quoted text here. Click to load it

  Awtory idioty, и любой спор с вами бессмысленен. Фиксированное время
не заключается в подсчёте тактов.


Re: State_Maschine
Здравствуйте, Уважаемый Kirill!

Thu Jul 06 2006 12:37, Kirill Frolov wrote to Olga Nonova:

 >> KF>   Это не C++, это -- херня.
 >> Херня, оно может быть и херня. Hо, ведь прекрасно работает! Очень быстро и
 >> с  фиксированным временем на любое ветвление. Что кроет любые Ваши
 >> обсирания  вокруг да около.

 KF>   Awtory idioty, и любой спор с вами бессмысленен. Фиксированное время
 KF> не заключается в подсчёте тактов.

Слив засчитан.

Всего Вам Хорошего
Ольга


Re: State_Maschine
Hello, Olga!
You wrote to Kirill Frolov on Thu, 6 Jul 2006 09:27:11 +0000 (UTC):

 ON> Здравствуйте, Уважаемый Kirill!

 ON> Thu Jul 06 2006 12:37, Kirill Frolov wrote to Olga Nonova:

 KF>>>>   Это не C++, это -- херня.
 ??>>> Херня, оно может быть и херня. Hо, ведь прекрасно работает! Очень
 ??>>> быстро и с  фиксированным временем на любое ветвление. Что кроет
 ??>>> любые Ваши обсирания  вокруг да около.

 KF>>   Awtory idioty, и любой спор с вами бессмысленен. Фиксированное время
 KF>> не заключается в подсчёте тактов.

 ON> Слив засчитан.

Возможно, когда как я уже гооворил, ваш коллектифф прочитает какую-нибудь
книжку по Си, и откроет для себя enum и разберется как работает switch -
наступит "озарение", и вместо сливов "колектифф" начнет учиться не просто
языкам программирования, но и как в эхотаге пришутся программы.


With best regards,
Alexandr Torres.  E-mail: snipped-for-privacy@yahoo.com
[ Жамству бой !]



Re: State_Maschine

Quoted text here. Click to load it

  С чего бы это?  Строковые константы представимы как целые с
соответствующим ASCII кодом...


Re: State_Maschine
Здравствуйте, Уважаемый Ruslan!

Wed Jul 05 2006 08:20, Ruslan Mohniuc wrote to Olga Nonova:

 RM> Комментарии, надеюсь, не нужны?

В данном случае не нужны. Попробуйте теперь:
case 'A':....
case 'ы':....
case '1':....
case 'Ж':....

Коментарии нужны?

Всего Вам Хорошего
Ольга


Re: State_Maschine
Hello, Olga!
You wrote to Ruslan Mohniuc on Wed, 5 Jul 2006 21:22:49 +0000 (UTC):

 ON> Здравствуйте, Уважаемый Ruslan!

 ON> Wed Jul 05 2006 08:20, Ruslan Mohniuc wrote to Olga Nonova:

 RM>> Комментарии, надеюсь, не нужны?

 ON> В данном случае не нужны. Попробуйте теперь:
 ON> case 'A':....
 ON> case 'ы':....
 ON> case '1':....
 ON> case 'Ж':....

 ON> Коментарии нужны?


Да.  коммунтарии нужны.
Желательно в виде анализа ДНК того программиста. который сделал такие
состояния в стейт-машине.
В крайнем случай - его IQ*100, не люблю дробные цифры с нулевым целым.


With best regards, Alexandr Torres.

[ Жамству бой ! ]

2:461/28, E-mail: snipped-for-privacy@yahoo.com
http://altor.sytes.net



Site Timeline