Если ваш вопрос не влез ни в одну из вышеперечисленных тем, вам сюда.
Ответить

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

Ср сен 19, 2012 13:30:22

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

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

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

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

Последний раз редактировалось ibiza11 Ср июн 25, 2014 14:42:14, всего редактировалось 2 раз(а).
Причина: Прикрепил тему

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

Ср сен 19, 2012 15:22:29

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

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

Ср сен 19, 2012 18:27:19

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

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

Ср сен 19, 2012 19:38:17

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

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

Ср сен 19, 2012 22:40:31

BOB51 писал(а):Алгоритм согласно правилам, принятым для алгоритмов - ромкбики. квадратики ...строчки описания...
Да хоть так, IMHO, главное чтобы понятно было и можно было разобраться.

BOB51 писал(а):Кстати, насчет первого поста я так нихрена толком и не понял, чего человеку от нещасного МК надобно было... :dont_know:
Kavka писал(а):перед входом в прерывание микроконтроллер должен завершить выполнение текущей команды. А команды могут выполняться от 1 до 4 тактов (до 5 тактов на МК с памятью 128-256кб).
А если в прерывании программно генерируется какой-то сигнал на выводе МК, то фронты этого сигнала будут дрожать (jitter) на эти самые 4 такта. Чтобы этого не происходило и используется этот код.
Ну, например, чтобы избавиться вот от такого дрожания строк при выводе видео.
Изображение

vgajitter_314.jpg
(107.74 KiB) Скачиваний: 5652

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

Ср сен 19, 2012 23:19:57

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

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

Чт сен 20, 2012 01:28:27

У меня выравнивание джиттера прерывания сделано так (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

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

Чт сен 20, 2012 03:37:38

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

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

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

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

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

Чт сен 20, 2012 05:46:02

вот потому и нявчу - "копилка алгоритмов" - сам алгоритм можно куда угодно подтыкнуть, он лиш одно из возможных решений 8)
для синхронизации в программе можно использовать передаточные флаги, да и аппаратных вариантов организации таймеров куча... в древние времена была такая пакость К580ВГ75... да и книжка...склероз... вроде "любительские телевизионные игры" называлась (мож как-нибудь в старом шкапчике сыщу)...
в последнем случае вроде как общий вид - "табличный селектор" - оччень полезная штука, он же применяется для обработчика кнопушек, менюшек и прочей вкусности...
кстати, вышеприведенный код от Леонид Ивановича - одна из вариаций на тему табличного селектора 8)
:beer:
кстати... на уровне асма чаще приходится мудрить, да и легче - сам можеш выбирать структуру и организацию памяти, правила доступа к ресурсам с наименьшими затратами... но мозги "шкварчать" и времени поболее надо! :beer:
Последний раз редактировалось BOB51 Чт сен 20, 2012 09:12:51, всего редактировалось 2 раз(а).

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

Чт сен 20, 2012 05:51:57

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

Задача: преобразовать 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:

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

Чт сен 20, 2012 06:08:41

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

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

Чт сен 20, 2012 06:15:41

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

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

Чт сен 20, 2012 06:33:01

Леонид Иванович писал(а):У меня выравнивание джиттера прерывания сделано так (mega88):
Здорово! Такой вариант быстрее!

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

Чт сен 20, 2012 07:36:37

Ser60 писал(а):Очень интересная и полезная тема. Но опасная! Вот выложишь тут, что тебе кажется трюком, а кто-то это давно использует или ему покажется это очевидным и запинают до смерти. Да и для себя самого это будет трюком в первый или во второй раз, потом становится рутиной... Но рискну.
А что сразу запинывать!? Предлагать свой вариант надо!!!
И, как мне кажется, интересные алгоритмы и код, написанные со знанием и умением, далеко не всегда очевидны. Особенно для тех, кому это занятие ещё не стало рутиной. :)

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

Чт сен 20, 2012 09:49:28

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

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

Чт сен 20, 2012 10:20:49

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

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

Чт сен 20, 2012 12:02:52

Kavka писал(а):Здорово! Такой вариант быстрее!


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

Код:
.org   OC1Aaddr

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


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



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

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

Чт сен 20, 2012 12:59:13

Леонид Иванович писал(а):
Код:
.org   OC1Aaddr

DDS:   in   XL,TCNT1L   ;TCNT1L = 4..7
   sbrs   XL,0
   rjmp   PC+1
   sbrs   XL,1
   lpm   XL,Z
Так же быстро как с IJMP и просто супер компактно.
Вот это класс! Красиво!

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

Чт сен 20, 2012 13:23:26

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

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

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

Чт сен 20, 2012 19:27:20

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

Код:
  uint8_t msk;

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


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

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

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