Программирование без условных переходов

Думая над структурой очередной программы, понял что ветвления это зло (для AVR это brcc, sbic и т.д.). Ветвление это принятие решение. Если входное данное такое, то идем туда. Если другое, то туда. Когда анализируешь работу программы, самое сложное это понимание участков с ветвлениями. Понял что возможно писать по другому принципу. Без использования операторов сравнений-ветвлений.

Суть такая. Входной байт данных не надо сравнивать с чем-то. А надо прогонять через последовательность заграждений или заборов. Каждое заграждение расчитано на свой байт. То есть если заграждение подготовлено для байта 0x0A, то по проходу этого байта выставляется 1 в соответствующем месте Идентификатора. Если заграждение прошел любой другой байт, выставляется 0 в Идентификаторе.

Например нам надо отслеживать команды 0x0A, 0x0B. И выполнять для них соответствующие процедуры.

Мы приняли байт 0x0A.

Прогоняем 0x0A чере заграждение_A. Здесь установится бит Идентификатора_А

Прогоняем 0x0A через заграждение_B. Ничего не установится

На выходе Идентификатор указывает адрес процедуры_А для выполнения.

Как это выглядит в коде в среде VMLAB:

.equ  mA = 0x41;    маска для A
.equ  mB = 0x42;    маска для B


vrRX_OK:

      CLR  output;
      IN   data,UDR;

      ;-------------
       ;Заграждение А

        MOV  temp,data;
        LDI  mask,mA;              загружаем маску для байта А, равную А
        EOR  temp,mask;            если принятый байт и маска совпали, то в temp будет 0
         SUBI temp,1;               при отнимании от нуля единицы, устанавливается флаг переноса С
                                        ;(если принятый байт и маска не совпали,
                                        ; то в temp будет не ноль и при отнимании единицы, переноса не будет)

         CLR  temp;                 обнуляем temp
         ROL  temp;                 помещаем флаг переноса в нулевой бит temp
         BST  temp,0;               копируем бит в T
         BLD  output,0;             и кидаем его в значащее место переменной output

         ;-------------
         ;Заграждение B

         MOV  temp,data;
         LDI  mask,mB;              загружаем маску для байта B, равную B
         EOR  temp,mask;            если принятый байт и маска совпали, то в temp будет 0
         SUBI temp,1;               при отнимании от нуля единицы, устанавливается флаг переноса С
                                        ;(если принятый байт и маска не совпали,
                                        ; то в temp будет не ноль и при отнимании единицы, переноса не будет)

         CLR  temp;                 обнуляем temp
         ROL  temp;                 помещаем флаг переноса в нулевой бит temp
         BST  temp,0;               копируем бит в T
         BLD  output,1;             и кидаем его в значащее место переменной output

         RETI;

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

Еще один пример программирования без условных переходов:

Задача. При нажатой кнопке светодиод должен гореть, при отпущенной гаснуть.
Кнопка PORTB,1 вход с подтяжкой
Светодиод PORTB,2 выход. Катод на земле.

Стандартное решение

                 Start:

                          SBIC  PINB,1;        если кнопка прижата пропускаем следующую команду
                          CBI     PORTB,2;   выключить светодиод
                          SBIS  PINB,1;        если кнопка отпущена пропускаем следующую команду
                          SBI     PORTB,2;   включить светодиод

                          RJMP  Start;


Решение без условных переходов

Определяем логическую зависимость Светодиод — Кнопка. Светодиод = Не (Кнопка)
Таблица истинности      Светодиод       Кнопка
                             1                 0
                             0                 1


Тогда берем значение кнопки, инвертируем его и помещаем в светодиод.

                     Start:                                                                             

                          IN        temp,PINB;        копируем значение пинов в первую переменную
                          IN        temp2,PINB;      сохраняем во вторую
                          COM  temp;                   инвертируем все биты, хотя нам нужен только бит 1
                          BST    temp,1;               сохраняем инвертированный бит кнопки в T
                          BLD    temp2,0;            выдаем этот бит во вторую переменную на место светодиода
                          OUT    PORTB,temp2; выдаем эту переменную в порт В
                          
                          RJMP Start;      


Это принцип мышления при программировании без проверки условий. Идее 2 дня отроду. Может быть ее можно развить во что-то реально удобное. Команды ветвления повторяют логику мышления человека, налево пойдешь...., направо пойдешь… А у процессора ног много пусть он все направления объединит в одну линию и последовательно их проходит. А на выходе будет видно что он вынесет.

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

Комментарии (39)

RSS свернуть / развернуть
cut!!!
0
И код в специальный тег засунуть не помешает.
0
да так лучше будет. первый раз просто пишу.
0
На простых решения канает, а такой вариант:

При нажатии кнопки PORTB1 выполнять функцию А
При нажатии кнопки PORTB2 выполнять функцию Б
0

.equ  mask_knopka1 = 0b11111101 для кнопки B.1
.equ  mask_knopka2 = 0b11111011 для кнопки B.2

clr   output;      смещение в списке  процедур

допустим нажата кнопка 1

IN   temp,PINB;
EOR  temp,mask_knopka1     будет 0
SUBI temp,1;               будет перенос
CLR  temp;
ROL  temp;                 будет 1 
MUL  temp,Nomer_Procedury_1;   1*номер = номер
ADD  output,R0;             смещение в списке процедур будет равно номеру процедуры          

IN   temp,PINB;
EOR  temp,mask_knopka2     будет не 0
SUBI temp,1;               переноса не будет
CLR  temp;
ROL  temp;                 будет 0 
MUL  temp,Nomer_Procedury_1;   0*номер = 0
ADD  output,R0;                смещение не изменится

таким образом можно найти смещение процедуры в списке процедур.

Достаточно сложно находу придумывать приемы работы 
в другом стиле программирования. Я сюда писал чтоб народ тоже
 попробовал что-то написать по такому принципу. Ну и это 
интересно заставить мозги думать по другому.

То что в порту B включены все подтяжки я взял для простоты. 
Возникает задача разработки приема для заграждения не всего
порта а только битов где висят кнопки, вот и задача для народа.



0
Просто накладные расходы получаются слишком высоки, а программа нечитабельной. Но в этом тоже иной раз есть плюс — команда перехода выполняется за разное число тактов, иногда это критично и дико обламывает.
0
В этом плане у 51 красиво получается, непосредственно с битами портов.
Типа:
mov c, KEY
cpl c
mov LED1, c
А в случае множественных состояний — через jmp @a+dptr и таблицу переходов.
Фишка в том, что время выполнения можно сделать одинаковым, независимо от значения, считанного с порта, с цепочкой сравнений это не так. Для кнопок-светодиодов, конечно, неактуально. :)
0
  • avatar
  • Katz
  • 14 января 2012, 17:21
Такое делали на gpu когда они не умели настоящие ветвления. Ещё на эту тему есть, OISC, move machine.
0
OUT PORTB,temp2; выдаем эту переменную в порт В
Я бы добавил:… и убираем подтяжку у нажатой кнопки :)
+1
зачем?
0
Павел, операцией IN temp2, PINB, Вы считали с бита кнопки нолик (в temp2.1)и, вывели этот нолик последующей операцией OUT в PORTB.1. Теперь у кнопки не будет подтяжки. Внимательней надо быть.
0
Мне кажется, медленно будет при большом количестве условий. И уж очень громоздко. Ветвление — наоборот классная фишка. Проц — не человек, его не мучает совесть, лень и т.п., потому он спокойно принимает решения.
0
во реально какие выгоды это даёт?
легкочитаемый ассемблерный листинг?
сомнительное преимущество, хотите более читаемый код — используйте язык более высокого уровня
у вас же с усложнением кода увеличиваются и накладные расходы — представьте свои заборы для 20 функций — тут уже и не рад будешь отсутствию переходов
0
Для обработки 20 команд принимаемых по UART например. Надо составить список всех команд, список номеров процедур для команд, список адресов процедур. Когда байт пришел, ищем его в списке команд и по его номеру находим номер процедуры. По номеру процедуры находим ее адрес и IJMP.


scKomandy:          .DB 0x0A, 0x0B, 0x09, 0x10, 0x11, 0x12, 
scNomerProcedury:   .DB    5,    6,    9,    0,    1,    2,

scAdresaProcedur:   .DW  Pr_N0, Pr_N1, Pr_N2, Pr_N3, Pr_N4,

Заборы надо использовать в местах где используются команды сравнения.
А обработка команд этого не требует
0
Если много команд сравнения, то поможет индексный переоход через вычисление адреса по таблице. Адреса таблицы можно подобрать таким образом, чтобы они в два счета вычислялись из варианта пришедшего на развилку.
0
Когда-то приходилось пользоваться алгоритмом без ветвления. Требовалось 2 таймера, а в МК был только один. Вместо второго таймера использовал алгоритм без ветвлений с постоянным количеством тактов. Пользоваться этим можно, но не всегда удобно.
0
А я всегда думал, что вред ветвления в том, что оно сбивает конвейер, из за чего следующая команда выполняется на такт дольше.
0
… А то и заметно больше, чем на один такт…
0
Ну это уже от архитектуры зависит и конвейера.
0
На первый взгляд это бред писать в таком стиле, но когда программа растет, то основные силы уходят на то чтоб держать в голове структуру программы. И возможно проще будет писать программу линейно. Задача то поставлена глобальная, разработать приемы работы без использования условных переходов. Единственное место где нельзя отказываться от условных переходов это цикличные операции.
0
Используйте ДРАКОН! =)
0
Так структура то никуда не девается. Ветви остаются, только они выстроены друг за другом. Получается как в арме — есть префикс команды, выполнять или не выполнять. В зависимости от условий. А тут префикс получается на целый кусок кода.
0
Я понимаю ветви как места в которых осуществляется переход от текущей строчки кода, к дальней, с пропуском ближайших строчек кода. Эти места являются трудными для восприятия и следовательно здесь легко сделать ошибку.
Предлагаю делать адресный переход на процедуру в конце блока кода. А в теле блока ставить именные заграждения для входного данного. Допустим у нас на входе в UART могут зайти три команды, для каждой команды надо выполнить процедуру. Мы просто ставим заграждение_А, заграждение_B, заграждение_С. Если влетела команда B, то на заграждении B она оставит свои яйца и в конце блока мы делаем адресный переход на процедуру B. В выше написаном коде про кнопки это видно. Данный принцип позволит масштабировать программу.

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


;  Приветствие на дисплей. CR - перевод строки. 0x00 - конец строки

prLcd_Print_A:

				   LDI   ZH,HIGH(2*Ref_TXT);           Загружаем адрес строки
					LDI   ZL,LOW(2*Ref_TXT);
					
Ref_A1:
               LPM   temp,Z+;                  Загружаем символ, увеличиваем адрес
               STS   pParam,temp;              Сохраняем символ
               TST   temp;                     если символ 0, выходим
               BRNE  Ref_A2;
               RET;

Ref_A2:
               CPI   temp,LCD_CR;              Если символ CR, то переходим на вторую строку
               BRNE  Ref_A3;
               LDI   temp2,LCD_Start2Line;     Курсор в начало второй строки
               STS   pParam,temp2;
               RCALL prLcd_Cmd_B;
               RJMP  Ref_A1;

Ref_A3:
               RCALL prLcd_Data;
               RJMP  Ref_A1;

               RET;

Ref_TXT:
               .DB   "Type in TTY",0x0D;      Must contain    an even
               .DB   ">",0x00;                number of bytes per line
0
Адреса переходов пусть компилятор считает. Это его задача. Расставил метки и внес их в таблицу переходов.
0
У меня раньше была идея реализации вычисляемого перехода на основе арифметических преобразований
допустим приходит по уарту команда 0x01 мы к ней прибавляем/умножаем/или более сложная ф-ция и вычисляем адрес подпрограммы куда надо бы перейти. Но так как пишу на С то там с этим гемор, выкрутился без подпрограмм.
0
С чего бы в С был гемор с этим? Разве что гораздо удобнее будет сложить все точки входа в массив и вычислять индекс в массиве.
0
я так и сделал через массив, но как программу вызывать из массива так и не нашел способа, там как-то наверно надо линкер настраивать
0
Вам, вероятно, стоит почитать учебник по С, в частности об указателях на функции.
0
Вот вам пример обработки функции через массив указателей:


void (*KeyPress[48]) (uint8_t num);
//...................................

// инициализация массива указателей
	for (iii=0; iii<48; iii++)
	{
		if ((iii == 12) || (iii == 39))
		{
			KeyPress[iii] = ChangeMode;
		}	
		else
		{	
			if ((iii > 15) && (iii < 24))
			{
				KeyPress[iii] = Engine_op;
			} 
			else
			{
				KeyPress[iii] = Common_op;
			};
		};
	};

//......................


// обработка в нутри цикла:
if (((pTumbler_switch->Inp_registers[ii])&(1<<aa))==(1<<aa)) (*KeyPress[((ii*8)+aa)]) (((ii*8)+aa));


Данная тема гуглится в течении 5ти минут…
0
думаете этот код заработает на контроллере? допустим MSP? среда ССS?
0
А что такого особенного в MSP, что этот код может не заработать?
0
На STM32 работает вполне нормально. Код из рабочего проекта.
0
какая среда разработки?
Когда хотел сделать в CCS, полез за информацией в User Guide к компилеру и там ссылались на линкер, что его требуется настроить под эти самые ф-ции, какие-то адресса задать и как-то тогда желание отпало
0
Keil
0
Смотрю изобретение велосипедов (в данном случае — простейшей реализации примитивного конечного автомата) продолжается… Раньше таким страдали (каюсь, и сам грешен) от недостатка информации, но сейчас-то чего…
0
  • avatar
  • evsi
  • 15 января 2012, 22:29
ну я например про конечный автомат знаю. идея хороша ограничить количество состояний, а реализация меня не вдохновила. мой стиль программирования это адресно табличный, когда глянешь на код и все понятно сразу


   scKomandy:          .DB 0x0A, 0x0B, 0x09, 0x10, 0x11, 0x12, 0x13, 0x14, 0x20, 0x21, 0x22, 0x23, 0x24, 0x30, 0x31, 0x32, 0x33, 0x34, 0x40, 0x41, 0x42, 0x43, 0x44, 0x50, 0x51, 0x52, 0x53, 0x54, 0x16, 0x17, 0x26, 0x27, 0x36, 0x37, 0x46, 0x47, 0x56, 0x57, 0x1C, 0x2C, 0x3C, 0x4C, 0x5C, 0x6C, 0x1D, 0x2D, 0x3D, 0x4D, 0x5D, 0x6D, 0x1E, 0x2E, 0x3E, 0x4E, 0x5E, 0x1F, 0x2F, 0x3F, 0x4F, 0x5F, 0xFF, 0xFF;   60 + 0xFF,  0xFF
   scKanaly:           .DB    6,    7,  255,    0,    0,    0,    0,    0,    1,    1,    1,    1,    1,    2,    2,    2,    2,    2,    3,    3,    3,    3,    3,    4,    4,    4,    4,    4,    0,    0,    1,    1,    2,    2,    3,    3,    4,    4,    0,    1,    2,    3,    4,    5,    0,    1,    2,    3,    4,    5,    0,    1,    2,    3,    4,    0,    1,    2,    3,    4, 0xFF, 0xFF;                 +0xFF
   scProcedury:        .DB    5,    6,    9,    0,    1,    2,    3,    4,    0,    1,    2,    3,    4,    0,    1,    2,    3,    4,    0,    1,    2,    3,    4,    0,    1,    2,    3,    4,   10,   11,   10,   11,   10,   11,   10,   11,   10,   11,    7,    7,    7,    7,    7,    7,    8,    8,    8,    8,    8,    8,    9,    9,    9,    9,    9,    9,    9,    9,    9,    9, 0xFF, 0xFF;
   scChislo_Koef:      .DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,   40,   40,   40,   40,   40,    4,   40,   40,   40,   40,   40,    4, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF;

   scProcedurList:     .DW  Pr_N0, Pr_N1, Pr_N2, Pr_N3, Pr_N4, Pr_N5, Pr_N6, Pr_N7, Pr_N8, Pr_N9, Pr_N10, Pr_N11;


Если получиться моя задумка избавиться от ветвлений, тогда вобще на код одним глазом можно будет смотреть. Это вобще ТРИЗом попахивает — стандартизация, избавление от случайных методов работы.
0
Для конечного автомата табличное представление — вполне разумный и часто используемый метод. Реализация описанная в топике, подозреваю, вызвана как раз незнанием того, что это такое, откуда берется и как правильно реализуется. Что, вобщем, удивительно, учитывая то, что как раз во встраиваемых устройствах конечные автоматы — азбука, IMHO.
0
Здесь у человека такие же мысли появились только раньше habrahabr.ru/blogs/crazydev/124878/
0
Продолжая тему. Взял вот эту технику и избавился от условнух переходов:
const int Channels = 2;
static volatile uint8_t _value[Channels];
static uint8_t _x1, _x2;
static inline uint8_t Detect(uint8_t x1, uint8_t x2, uint8_t y1, uint8_t y2) 
{
   return (x2 ^ y1) & ~(x1 ^ y2);
}
static inline  void CaptureHandler()
{
   uint8_t y1 = ReadY1();
   uint8_t y2 = ReadY2();
   uint8_t fwd  = Detect(_x1, _x2, y1, y2);
   uint8_t back = Detect(_x2, _x1, y2, y1);
   _x1 = y1;
   _x2 = y2;

   volatile uint8_t * ptr = _value;
   for(uint8_t i = Channels; i; --i)
   {
     //if(fwd & 1)
     //	 (*ptr) ++;
     //else 
     //if(back & 1)
     //	(*ptr) --;
     //ptr++;
     *ptr++ = *ptr + (fwd & 1) - (back & 1);
     fwd >>= 1;
     back >>= 1;
   }
}
Если компилятор разворачивает цикл, а он его разворачивает, то получается совершенно линейный машинный код. Причем эффективнее, чем с условными переходами.
0
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.