Хитрые, необычные алгоритмы и код

[Kavka]

Предлагаю выкладывать в эту тему хитрые, необычные алгоритмы и код, хитрые варианты использования возможностей ассемблера и т.п.
Думаю, что захламлять тему громадными кусками кода смысла нет.
Поэтому предлагаю выкладывать только самые-самые кусочки кода с объяснениями.
Если код на ассемблере, то, думаю, надо указать для какой архитектуры или чипа приводимый код.
А на весь проект, где приведённый код используется, давать ссылочку, если есть.

Идея создать такую тему родилась после прочтения темы о синхронизации исполнения кода по таймеру на 8-ми битных AVR-ках.
Как оказалось, о такой задачке почти никто не задумывался, а многие и вообще смысла в ней не видят.
Тем не менее, потребность такой синхронизации в некоторых случаях имеется.
Получается, что задачка, как минимум, необычная.
Если точнее, задачка состоит в том, чтобы убрать "дрожание" задержки входа в прерывание величиной в несколько тактов
вызванное тем, что перед входом в прерывание микроконтроллер должен завершить выполнение текущей команды.
А команды могут выполняться от 1 до 4 тактов (до 5 тактов на МК с памятью 128-256кб).
Устранить дрожание можно если прерывание происходит от таймера работающего без делителя.
Если вход в прерывание произошёл слишком быстро, то основываясь на таймере доводим задержку до максимальной.

Фишка в том, что в этом коде выполняются абсолютно все команды, подряд, но время выполнения может быть разное.

Самое раннее что я видел, это обсуждение на форуме avrfreaks.net в 2007 году.
Вот проект того парня с форума avrfreaks.net, где это используется.

Спойлер

; !!!! SET TIMER1 TO CTC MODE WITH NO PRESCALE
.org oc1aaddr
rjmp VIDEO ;2

VIDEO:
; SAVE STATUS REGISTER
in r16,sreg ;1
push r16 ;2

; EQUALIZE INTERRUPT LATENCY
lds r16,tcnt1l ;2
cpi r16,10 ;1
brlo LATFIX1 ;1/2
LATFIX1:
cpi r16,11 ;1
brlo LATFIX2 ;1/2
LATFIX2:
cpi r16,12 ;1
brlo LATFIX3 ;1/2
LATFIX3:

[BOB51]

Тему не прочь поддержать, а вот пример не из лучших - просто надо по-другому подход к генератору сетки частот делать... (по принципу - сломал все и начал сначала)
Да и алгоритмы не в виде конкретных команд, а в виде именно алгоритмов, по возможности, без привязки к конкретному виду МК - так легче потом адаптировать под другой набор команд и ресурсов.

[Kavka]

Алгоритм, говоришь... Иногда достаточно словесного описания идеи, как в первом посте, чтобы понять смысл - очень простой алгоритм. А вот когда посложней, то - да, неплохо было бы и сам алгоритм описать и код.

[BOB51]

Алгоритм согласно правилам, принятым для алгоритмов - ромкбики. квадратики ...строчки описания... или чего-то как я тут сморозил... download/file.php?id=92771
Кстати, насчет первого поста я так нихрена толком и не понял, чего человеку от нещасного МК надобно было... Очень много значит правильно сформулированная задача (если б еще знать, как оно должно в конце получиться... иной раз делал одно, а получаеш совсем другое...)

[Kavka]

Алгоритм согласно правилам, принятым для алгоритмов - ромкбики. квадратики ...строчки описания...

Да хоть так, IMHO, главное чтобы понятно было и можно было разобраться.

Кстати, насчет первого поста я так нихрена толком и не понял, чего человеку от нещасного МК надобно было...

перед входом в прерывание микроконтроллер должен завершить выполнение текущей команды. А команды могут выполняться от 1 до 4 тактов (до 5 тактов на МК с памятью 128-256кб).

А если в прерывании программно генерируется какой-то сигнал на выводе МК, то фронты этого сигнала будут дрожать (jitter) на эти самые 4 такта. Чтобы этого не происходило и используется этот код.
Ну, например, чтобы избавиться вот от такого дрожания строк при выводе видео.

vgajitter_314.jpg

(107.74 КБ) 6656 скачиваний

[eufs]

Я писал когда-то вывод синхроимпульсов по прерыванию от таймера. Если надо, могу выложить. Там выравнивание основано в выполнении холостых операций, а не на таймере.

[Леонид Иванович]

У меня выравнивание джиттера прерывания сделано так (mega88):

Код: Выделить всё

.org   OC1Aaddr

                                ;4      address store
DDS:    lds     ZL,TCNT1L   ;2      TCNT1L = 5..8
        ldi     ZH,high(JmpTab) ;1
        ijmp                    ;2

.org   (PC + 0x100) & 0xFF00   ;align to page

JmpTab: nop                     ;       dummy
        nop                     ;       dummy
        nop                     ;       dummy
        nop                     ;       dummy
        nop                     ;       dummy
        nop                     ;0/1    TCNT1L = 5
        nop                     ;0/1    TCNT1L = 6
        nop                     ;0/1    TCNT1L = 7
                                ;       TCNT1L = 8

[Ser60]

Очень интересная и полезная тема. Но опасная! Вот выложишь тут, что тебе кажется трюком, а кто-то это давно использует или ему покажется это очевидным и запинают до смерти. Да и для себя самого это будет трюком в первый или во второй раз, потом становится рутиной... Но рискну.

Задача: имеется переключатель на 3 положения. На его контактах напряжения, скажем: + питания, половина питания и 0 (обший провод), но могут быть и любые другие фиксированные в области рабочих напряжений МК. Одно из них поступает на выход в зависимости от положения движка. Переключатель переключается пользователем. Задача отследить момент изменения положения переключателя при минимальном задействовании процессора и выставить бит в каком-то регистре. МК семейства MSP430.

Решение: напряжение на выходе переключателя периодически контролируется АЦП, который начинает измерение по переполнению одного из таймеров и непосредственно управляется последним. АЦП имеет цифровой компаратор проверки на принадлежность выходного кода одному из 3-х окон его значений и может быть сконфигурирован на генерацию прерывания при попадании сигнала в любое из окон. Пороги, определяющие окна, задаются при конфиграции АЦП в зависимости от напряжений на контактах переключателя. Все проверки кода АЦП пока происходят без участия процессора.

В начале программы, определяется исходное положние переключателя и окно, куда попадает его код, и разрешаются прерывания от АЦП при попадании его кода в любое из другх окон. В обработчике прерываний путем сложения его вектора с содержимым PC мы сразу попадаем в нужную ветку обработки кода окна. Допустим, движок переключателя переместился из среднего в верхнее положение. Тогда в обработчике прерываний мы разрешаем прерывания от нижнего и среднего окон и запрещаем прерывания для верхнего окна (и устанавливаем бит в упомянутом выше регистре). Аналогигно поступаем ив 2-х других случаях - запрещаем прерывания для окна вызвавшего его и разрешаем прерывания для других окон. Вот код обработчика прерываний. Переменная switch получает одно из 3-х значений 0,1,2 в зависимости от нового положения переключателя. Отмечу, что большую часть времени когда положение переключателя не меняется, процессор вообще не отвлекается не на активизацию АЦП не на проверку кода на принадлежность окнам.

Спойлер

Код: Выделить всё

ADC10_ISR: 
        add.w   &ADC10IV, PC            ; add offset to PC
        reti                            ; No Interrupt
        reti                            ; ADC10_B overflow
        reti                            ; ADC10_B timing overflow
        jmp     ADC_hi                  ; ADC10_B window comparator high
        jmp     ADC_lo                  ; ADC10_B window comparator low
        jmp     ADC_in                  ; ADC10_B window comparator in
        reti                                ; ADC conversion complete

ADC_fi: clr.w   &ADC10IFG               ; clear interrupt flags
        bic.w   #LPM0, 0(SP)            ; conversion complete, wake-up CPU 
        reti
ADC_hi: mov.b   #2, &switch             ; new state
        bis.b   #Switch, &event         ; set event
        mov.w   #ADC10LOIE+ADC10INIE+ADC10IFG0, &ADC10IE
        jmp     ADC_fi
ADC_lo: clr.b   &switch                 ; new state
        bis.b   #Switch, &event         ; set event
        mov.w   #ADC10HIIE+ADC10INIE+ADC10IFG0, &ADC10IE
        jmp     ADC_fi
ADC_in: mov.b   #1, &switch             ; new state
        bis.b   #Switch, &event         ; set event
        mov.w   #ADC10LOIE+ADC10HIIE+ADC10IFG0, &ADC10IE
        jmp     ADC_fi

[BOB51]

вот потому и нявчу - "копилка алгоритмов" - сам алгоритм можно куда угодно подтыкнуть, он лиш одно из возможных решений
для синхронизации в программе можно использовать передаточные флаги, да и аппаратных вариантов организации таймеров куча... в древние времена была такая пакость К580ВГ75... да и книжка...склероз... вроде "любительские телевизионные игры" называлась (мож как-нибудь в старом шкапчике сыщу)...
в последнем случае вроде как общий вид - "табличный селектор" - оччень полезная штука, он же применяется для обработчика кнопушек, менюшек и прочей вкусности...
кстати, вышеприведенный код от Леонид Ивановича - одна из вариаций на тему табличного селектора

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

[Ser60]

Рискну, пожалуй, здоровьем еще раз.

Задача: преобразовать 10-битное двоичное число N (например, значение кода 10-битного АЦП) из двоичного формата в двоично-десятичный. Иными словами, определить десятичные цифры числа (не более 4 десятичных цифр, соответствующих значениям N от 0 до 1023). Сделать это по-возможности быстро с минимумом используемой памяти. Процессор х51.

Решение: в этой архитектуре имеется аппаратный 8/8 бит делитель, вычисляющий целую часть деления и остаток 8-битных чисел за 8 машинных тактов. Однако, использовать этот делитель для определения цифр N напрямую не получится, т.к. делимое не должно превосходить 255.

Представим себе процесс деления в двоичной системе путем вычитания из N десятки со сдвигами. Пусть для примера N = 987, что в двоичной системе будет 11.1101.1011 (я разделил нибблы числа N точками для наглядности). Т.е. мы начимаем процесс двоичного деления путем вычитания из N десятки (двоичный код 1010) сдвинутой на 6 бит влево:

11.1101.1011
10.1000.0000

После чего десятка сдвигается на 1 бит вправо и процесс продолжается. Однако, первые 3 итерации этого процессa можно произвести быстрее, если поделить число, представленное первым и вторым нибблом (в нашем случае 11.1101 = 61) на 10 в аппаратном делителе и заменить эти нибблы на остаток от деления. В результате деления 61 / 10 получим частное N1 = 6 и остаток 1. Поместим этот остаток вместо первого и второго ниббла в исходное число, в результате получим

0001.1011

Так как остаток от деления на 10 состоит не более, чем из 4 бит, результат описанной операции будет максимум 8-битным. Поделив полученное число 0001.1011 (= 27) на 10 в аппаратном делителе получим остаток от деления N на 10, т.е. последнюю десятичную цифру числа. В нашем случае остаток 27 % 10 = 7 и частное N2 = 2. Нетрудно видеть, что для целой части числа N / 10 имеем: N / 10 = N1*16 + N2 и т.к. N не превосходит 1023, то N / 10 не превосходит 102, т.е. N / 10 будет 7-битным. В нашем примере N / 10 = 987 / 10 = 6*16 + 2 = 98. Для определения остальных цифр достаточно поделить 98 на 10 в аппаратном делителе и определить частное и остаток. Если частное окажется менее 10, вычисления закончены. В противном случае две старшие цифры числа будут 1 и 0.

Таким образом, для нахождения цифр числа использованы 3 деления 8-битных чисел в аппаратном делителе. Умножение на 16 при вычислении N / 10 заменяется манипуляциями с нибблами (или сдвигом на 4 бита влево). Ниже код на АСМе в предположении, что исходное число N находится в регистрах R1:R0 (R1 - старший байт, R0 - младший) и имеет не более 3 десятичных цифр (т.е. не превосходит 999), что имеет место на практике, например при работе с атмосферным давлением в мм.рт.ст. Цифры числа сохраняются в переменных digit1, digit2, digit3:

Спойлер

Код: Выделить всё

      mov   A, R0                   ; converting to BCD
      swap  A                       ; assuming that R1:R0
      anl   A, #0x0F                ; has 3 decimal digits
      mov   R2, A
      mov   A, R1
      swap  A
      add   A, R2
      mov   B, #10
      div   AB                     
      swap  A
      mov   R2, A                   ; R2 = high(R1:R0/10)
      mov   A, B
      swap  A
      mov   R1, A
      mov   A, R0
      anl   A, #0x0F
      add   A, R1
      mov   B, #10
      div   AB
      add   A, R2
      mov   bdig3, B                ; B = 3rd digit
   mov   digit3, B
      mov   B, #10
      div   AB                      ; A - 1st digit, B = 2nd digit
   mov   bdig1, A
   mov   digit1, A
   mov   bdig2, B
   mov   digit2, B

[BOB51]

вычитание блоками с записью результата в регистры-накопители
сначала 10000
затем 1000
100
10
в остатке единицы
получаем из двухбайтового двоичного 5 двоично-десятичных без аппаратного делителя
не слишком быстро, зато весьма просто и кушается на любом МК
ну это в общем виде, упуская подробности
по такому же принципу строится и обратный алгоритм, только с операцией сложения
двоичного эквивалента, а десятичные значения в качестве счетчиков количества сложений...

[Ser60]

Да, это стандартный способ преобразования, но вышеприведенный гораздо быстрее. Правда, наиболее эффективен он на х51 где есть аппаратный делитель. Но ранее я его также применял и на PIC-ах, реализовав деление байта на 10 таблицей на 256 байт. И так можно поступить на любом МК если нужна скорость и можно потратить разумное количество памяти (256 байт).

[Kavka]

У меня выравнивание джиттера прерывания сделано так (mega88):

Здорово! Такой вариант быстрее!

[Kavka]

Очень интересная и полезная тема. Но опасная! Вот выложишь тут, что тебе кажется трюком, а кто-то это давно использует или ему покажется это очевидным и запинают до смерти. Да и для себя самого это будет трюком в первый или во второй раз, потом становится рутиной... Но рискну.

А что сразу запинывать!? Предлагать свой вариант надо!!!
И, как мне кажется, интересные алгоритмы и код, написанные со знанием и умением, далеко не всегда очевидны. Особенно для тех, кому это занятие ещё не стало рутиной.

[BOB51]

частенько алгоритм не слишком удобный для одного вида МК становится оптимальным для другого - у нас минимум 4 разновидности в повседневной эксплуатации встречаются :
mcs51, atmega/attiny, pic10/12/16, pic18
отдельно следует выделить attiny4,5,9,10,20 и 40, atxmega и pic24
и порядком подзабытые, но с весьма неплохо проработанными решениями I8080 и Z80

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

[Kavka]

так что девиз темы - возьми лучшее от окружающих и интегрируй под свои нужды

Возможно оно так и есть. Только с небольшим уточнением - если только брать и вставлять интегрировать не разбираясь, то ничему не научишься. И когда кончится то лучшее у других, или просто его не будет для решения нужной задачи, то сам не сможешь решить поставленную задачу. Поэтому остаётся только учиться, постоянно. А учиться можно только тому чего не знаешь и у тех кто знает и умеет. В общем, это уже философия и она выходит за рамки топика этой темы.
Вот, то же на тему философии viewtopic.php?p=1409226#p1409226

[Леонид Иванович]

Здорово! Такой вариант быстрее!

На ATmega8 применял такой "выравниватель":

Код: Выделить всё

.org   OC1Aaddr

DDS:   in   XL,TCNT1L   ;TCNT1L = 4..7
   sbrs   XL,0
   rjmp   PC+1
   sbrs   XL,1
   lpm   XL,Z

Для преобразования в BCD на asm применял такой код:

Спойлер

Код: Выделить всё

;tempH:tempM:tempL convert to BCD Dig[0..6]
   
DisBCD:   ldy   Dig
   clr   temp
   ldi   Cnt,7
clrout: st   Y+,temp      ;output array clear
   dec   Cnt
   brne   clrout      

   ldi   Cnt,24      ;input bits count
   ldz   Dig
hloop:   lsl   tempL      ;input array shift left
   rol   tempM
   rol   tempH      
   ldy   Dig+7
sloop:   ld   temp,-Y
   rol   temp
   subi   temp,-0x06   ;temp+6, C=1
   sbrs   temp,4
   subi   temp,0x06   ;temp-6, C=0
   andi   temp,0x0f
   st   Y,temp
   cpse   YL,ZL      ;ZH:ZL = Dig+3
   rjmp   sloop
   cpse   YH,ZH
   rjmp   sloop
   dec   Cnt      ;YH:YL = Dig+3
   brne   hloop

На Си использую такой:

Спойлер

Код: Выделить всё

//---------- Преобразование Long2BCD: ----------

//Преобразование двоичного числа в двоично-десятичное:
//x - входное двоичное число (32 бита, без знака)
//buff - выходной массив (10 цифр)

void Long2BCD(unsigned long x, char *buff)
{
  for(char i = 0; i < 10; i++)
    buff[i] = 0;                      //очистка выходного буфера
  for(char i = 0; i < 32; i++)        //цикл по количеству входных бит
  {
    char c = (x >> 31) & 1;           //сохранение переноса
    x = x << 1;                       //сдвиг входного числа
    for(char p = 0; p < 10; p++)      //цикл по количеству цифр
    {
      char s = buff[p];               //чтение цифры
      s = (s << 1) | c; c = 0;        //сдвиг с учетом переноса
      if(s > 9) { s += 0x06; c = 1; } //коррекция цифры
      s &= 0x0F;                      //выделение ниббла
      buff[p] = s;                    //сохранение цифры
    }
  }
}

//---------- Преобразование Int2BCD: ----------

//Преобразование двоичного числа в двоично-десятичное:
//x - входное двоичное число (16 бит, без знака)
//buff - выходной массив (5 цифр)

void Int2BCD(int x, char *buff)
{
  for(char i = 0; i < 5; i++)
    buff[i] = 0;                      //очистка выходного буфера
  for(char i = 0; i < 16; i++)        //цикл по количеству входных бит
  {
    char c = (x >> 15) & 1;           //сохранение переноса
    x = x << 1;                       //сдвиг входного числа
    for(char p = 0; p < 5; p++)       //цикл по количеству цифр
    {
      char s = buff[p];               //чтение цифры
      s = (s << 1) | c; c = 0;        //сдвиг с учетом переноса
      if(s > 9) { s += 0x06; c = 1; } //коррекция цифры
      s &= 0x0F;                      //выделение ниббла
      buff[p] = s;                    //сохранение цифры
    }
  }
}

[Kavka]

Код: Выделить всё

.org   OC1Aaddr

DDS:   in   XL,TCNT1L   ;TCNT1L = 4..7
   sbrs   XL,0
   rjmp   PC+1
   sbrs   XL,1
   lpm   XL,Z

Так же быстро как с IJMP и просто супер компактно.
Вот это класс! Красиво!

[Gudd-Head]

Наверное, скажу банальную вещь, но в мелких МК можно экономить код, если при инициализации найти (почти) одинаковые засылаемые константы, например установка направления портов и выходные сигналы, периферия и т.п. и расположить их друг за другом (АВР):

Код: Выделить всё

ldi tmp, AB
out DDRB, tmp
out UART, tmp

Но тут, естессно, надо быть настороже и при изменении одного битика не запороть всю программу

Ну и у них же можно использовать незадействованные РВВ данных периферии как байты ОЗУ (Tiny13: OCR0A, EEDR, ...).

[YS]

Я обычно пишу вывод байта по битам в порт так:

Код: Выделить всё

  uint8_t msk;

  for (msk=0x80; msk; msk=msk >> 1)
  {
    if (b & msk)
   {
     PORT|=DS;
   }
   else
   {
     PORT&=~DS;
   }
  }

PORT - порт, DS - маска пина данных.

Переменная msk - и счетчик, и маска. Причем так же можно поступать и с 16-и битными числами, и с 32-х битными.

Сответственно, если дополнить этот код выдачей управляющих сигналов, можно получить SPI и тому подобное.