Форум РадиоКот https://radiokot.ru/forum/ |
|
Хитрые, необычные алгоритмы и код https://radiokot.ru/forum/viewtopic.php?f=62&t=78185 |
Страница 1 из 19 |
Автор: | Kavka [ Ср сен 19, 2012 13:30:22 ] |
Заголовок сообщения: | Хитрые, необычные алгоритмы и код |
Предлагаю выкладывать в эту тему хитрые, необычные алгоритмы и код, хитрые варианты использования возможностей ассемблера и т.п. Думаю, что захламлять тему громадными кусками кода смысла нет. Поэтому предлагаю выкладывать только самые-самые кусочки кода с объяснениями. Если код на ассемблере, то, думаю, надо указать для какой архитектуры или чипа приводимый код. А на весь проект, где приведённый код используется, давать ссылочку, если есть. Идея создать такую тему родилась после прочтения темы о синхронизации исполнения кода по таймеру на 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 [ Ср сен 19, 2012 15:22:29 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
Тему не прочь поддержать, а вот пример не из лучших - просто надо по-другому подход к генератору сетки частот делать... (по принципу - сломал все и начал сначала) ![]() Да и алгоритмы не в виде конкретных команд, а в виде именно алгоритмов, по возможности, без привязки к конкретному виду МК - так легче потом адаптировать под другой набор команд и ресурсов. ![]() |
Автор: | Kavka [ Ср сен 19, 2012 18:27:19 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
Алгоритм, говоришь... Иногда достаточно словесного описания идеи, как в первом посте, чтобы понять смысл - очень простой алгоритм. А вот когда посложней, то - да, неплохо было бы и сам алгоритм описать и код. |
Автор: | BOB51 [ Ср сен 19, 2012 19:38:17 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
Алгоритм согласно правилам, принятым для алгоритмов - ромкбики. квадратики ...строчки описания... или чего-то как я тут сморозил... download/file.php?id=92771 Кстати, насчет первого поста я так нихрена толком и не понял, чего человеку от нещасного МК надобно было... ![]() ![]() |
Автор: | Kavka [ Ср сен 19, 2012 22:40:31 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
BOB51 писал(а): Алгоритм согласно правилам, принятым для алгоритмов - ромкбики. квадратики ...строчки описания... Да хоть так, IMHO, главное чтобы понятно было и можно было разобраться.BOB51 писал(а): Кстати, насчет первого поста я так нихрена толком и не понял, чего человеку от нещасного МК надобно было... ![]() Kavka писал(а): перед входом в прерывание микроконтроллер должен завершить выполнение текущей команды. А команды могут выполняться от 1 до 4 тактов (до 5 тактов на МК с памятью 128-256кб). А если в прерывании программно генерируется какой-то сигнал на выводе МК, то фронты этого сигнала будут дрожать (jitter) на эти самые 4 такта. Чтобы этого не происходило и используется этот код.Ну, например, чтобы избавиться вот от такого дрожания строк при выводе видео. Вложение:
|
Автор: | eufs [ Ср сен 19, 2012 23:19:57 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
Я писал когда-то вывод синхроимпульсов по прерыванию от таймера. Если надо, могу выложить. Там выравнивание основано в выполнении холостых операций, а не на таймере. |
Автор: | Леонид Иванович [ Чт сен 20, 2012 01:28:27 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
У меня выравнивание джиттера прерывания сделано так (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 [ Чт сен 20, 2012 03:37:38 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
Очень интересная и полезная тема. Но опасная! Вот выложишь тут, что тебе кажется трюком, а кто-то это давно использует или ему покажется это очевидным и запинают до смерти. Да и для себя самого это будет трюком в первый или во второй раз, потом становится рутиной... Но рискну. Задача: имеется переключатель на 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 [ Чт сен 20, 2012 05:46:02 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
вот потому и нявчу - "копилка алгоритмов" - сам алгоритм можно куда угодно подтыкнуть, он лиш одно из возможных решений ![]() для синхронизации в программе можно использовать передаточные флаги, да и аппаратных вариантов организации таймеров куча... в древние времена была такая пакость К580ВГ75... да и книжка...склероз... вроде "любительские телевизионные игры" называлась (мож как-нибудь в старом шкапчике сыщу)... в последнем случае вроде как общий вид - "табличный селектор" - оччень полезная штука, он же применяется для обработчика кнопушек, менюшек и прочей вкусности... кстати, вышеприведенный код от Леонид Ивановича - одна из вариаций на тему табличного селектора ![]() ![]() кстати... на уровне асма чаще приходится мудрить, да и легче - сам можеш выбирать структуру и организацию памяти, правила доступа к ресурсам с наименьшими затратами... но мозги "шкварчать" и времени поболее надо! ![]() |
Автор: | Ser60 [ Чт сен 20, 2012 05:51:57 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
Рискну, пожалуй, здоровьем еще раз. Задача: преобразовать 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 [ Чт сен 20, 2012 06:08:41 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
вычитание блоками с записью результата в регистры-накопители сначала 10000 затем 1000 100 10 в остатке единицы получаем из двухбайтового двоичного 5 двоично-десятичных без аппаратного делителя не слишком быстро, зато весьма просто и кушается на любом МК ну это в общем виде, упуская подробности ![]() по такому же принципу строится и обратный алгоритм, только с операцией сложения двоичного эквивалента, а десятичные значения в качестве счетчиков количества сложений... |
Автор: | Ser60 [ Чт сен 20, 2012 06:15:41 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
Да, это стандартный способ преобразования, но вышеприведенный гораздо быстрее. Правда, наиболее эффективен он на х51 где есть аппаратный делитель. Но ранее я его также применял и на PIC-ах, реализовав деление байта на 10 таблицей на 256 байт. И так можно поступить на любом МК если нужна скорость и можно потратить разумное количество памяти (256 байт). |
Автор: | Kavka [ Чт сен 20, 2012 06:33:01 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
Леонид Иванович писал(а): У меня выравнивание джиттера прерывания сделано так (mega88): Здорово! Такой вариант быстрее!
|
Автор: | Kavka [ Чт сен 20, 2012 07:36:37 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
Ser60 писал(а): Очень интересная и полезная тема. Но опасная! Вот выложишь тут, что тебе кажется трюком, а кто-то это давно использует или ему покажется это очевидным и запинают до смерти. Да и для себя самого это будет трюком в первый или во второй раз, потом становится рутиной... Но рискну. А что сразу запинывать!? Предлагать свой вариант надо!!!И, как мне кажется, интересные алгоритмы и код, написанные со знанием и умением, далеко не всегда очевидны. Особенно для тех, кому это занятие ещё не стало рутиной. ![]() |
Автор: | BOB51 [ Чт сен 20, 2012 09:49:28 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
частенько алгоритм не слишком удобный для одного вида МК становится оптимальным для другого - у нас минимум 4 разновидности в повседневной эксплуатации встречаются : mcs51, atmega/attiny, pic10/12/16, pic18 отдельно следует выделить attiny4,5,9,10,20 и 40, atxmega и pic24 и порядком подзабытые, но с весьма неплохо проработанными решениями I8080 и Z80 ![]() за армы... это не для ассемблера игрушки... а может пока я их не очень готовить умею... ![]() так что девиз темы - возьми лучшее от окружающих и интегрируй под свои нужды ![]() |
Автор: | Kavka [ Чт сен 20, 2012 10:20:49 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
BOB51 писал(а): так что девиз темы - возьми лучшее от окружающих и интегрируй под свои нужды Возможно оно так и есть. Только с небольшим уточнением - если только брать и вставлять интегрировать не разбираясь, то ничему не научишься. И когда кончится то лучшее у других, или просто его не будет для решения нужной задачи, то сам не сможешь решить поставленную задачу. Поэтому остаётся только учиться, постоянно. А учиться можно только тому чего не знаешь и у тех кто знает и умеет. В общем, это уже философия и она выходит за рамки топика этой темы.![]() Вот, то же на тему философии viewtopic.php?p=1409226#p1409226 |
Автор: | Леонид Иванович [ Чт сен 20, 2012 12:02:52 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
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 применял такой код: СпойлерКод: ;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 [ Чт сен 20, 2012 12:59:13 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
Леонид Иванович писал(а): Код: .org OC1Aaddr DDS: in XL,TCNT1L ;TCNT1L = 4..7 sbrs XL,0 rjmp PC+1 sbrs XL,1 lpm XL,Z Вот это класс! Красиво! |
Автор: | Gudd-Head [ Чт сен 20, 2012 13:23:26 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
Наверное, скажу банальную вещь, но в мелких МК можно экономить код, если при инициализации найти (почти) одинаковые засылаемые константы, например установка направления портов и выходные сигналы, периферия и т.п. и расположить их друг за другом (АВР): Код: ldi tmp, AB Но тут, естессно, надо быть настороже и при изменении одного битика не запороть всю программу out DDRB, tmp out UART, tmp ![]() Ну и у них же можно использовать незадействованные РВВ данных периферии как байты ОЗУ (Tiny13: OCR0A, EEDR, ...). |
Автор: | YS [ Чт сен 20, 2012 19:27:20 ] |
Заголовок сообщения: | Re: Хитрые, необычные алгоритмы и код |
Я обычно пишу вывод байта по битам в порт так: Код: uint8_t msk; for (msk=0x80; msk; msk=msk >> 1) { if (b & msk) { PORT|=DS; } else { PORT&=~DS; } } PORT - порт, DS - маска пина данных. Переменная msk - и счетчик, и маска. Причем так же можно поступать и с 16-и битными числами, и с 32-х битными. Сответственно, если дополнить этот код выдачей управляющих сигналов, можно получить SPI и тому подобное. |
Страница 1 из 19 | Часовой пояс: UTC + 3 часа |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |