Насчет побитного вывода... Давеча нужно было реализовать побитную работу с буфером. Вот наделал разных вариантов. Однозначных лидеров нету, производительность каждого зависит от конкретного МК. Может кто добавит что-нибудь покрасивее/побыстрее?
Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
Добавлено: Чт сен 20, 2012 20:29:36
Держит паяльник хвостом
Карма: 15
Рейтинг сообщений: 70
Зарегистрирован: Ср мар 28, 2012 21:45:24 Сообщений: 906 Откуда: ВО
Рейтинг сообщения:0
Если уж очень лень , переводить BCD в Нех и что либо делать и переводить снова обратно , а порой и не выгодно то вот. Суммирование я уже выкладывал.
Код:
;************************************************ ;* ;;/Вычитание распакованных BCD;;* * ;************************************************ ldwi X,(VALUE1+3) ; Получаем значения ldwi Y,(VALUE1+6) ld temp,-X ld temp1,-Y sub temp,temp1 ; Вычитаем brpl SAVE_FORW ; Число положительное -это хорошо , меньше мороки sbr Flags,1<<fl_Cset ; Запоминаем флаг С neg temp ; Ивертируем полученую разницу ldi temp1,10 ; Вычитаем из 10 ,что получилось sub temp1,temp DIV_FORW: st Y,temp1 ; Здесь выход ; Ниже тоже что и выше но с учётом переноса ld temp1,-Y ld temp,-X sbrc Flags,fl_Cset sec cbr Flags,1<<fl_Cset sbc temp,temp1 brpl SAVE_FORW sbr Flags,1<<fl_Cset neg temp ldi temp1,10 sub temp1,temp rjmp DIV_FORW SAVE_FORW: mov temp1,temp rjmp DIV_FORW
Может кто добавит что-нибудь покрасивее/побыстрее?
Вот реализация побитного вывода содержимого ACC в порт P0.0 для процессора х51. В нем имеется возможность для прямой пересыкли C-бита в любой бит порта. Если не нужно сохранять содержимое ACC после отсылки, последнюю строчку можно исключить.
Код:
mov R0, #8 ; bits counter loop: rlc A ; get bit into C mov P0.0, C ; move C bit into port pin djnz R0, loop ; repeat 8 times rlc A ; preserve ACC
Посылка каждого бита занимает 6 циклов процессора. Если надо еще быстрее (т.е. за 2 цикла генератора), можно использовать аппаратный SPI драйвер.
Насчет операций (манипуляций) с отдельными битами (флаги пользователя/управления)) : В аврках также водится транзитный бит - подобие битового акумулятора... (флаг STATUS_T) через него много интересного можно примудрить... но зона воздействия только r16-r31 а операции с битами допустимы только для r16-r31 или для РСФ 0-31; У пикушек - побитовый анализ и изменение любого регистра ОЗУ (или РСФ как ОЗУ) без участия акумулятора; mcs51 операции с отдельными битами - акумулятор и область прямоадресуемых бит (регистры ОЗУ r20-r2F, а также указанные в документации на данный МК прямоадресуемые биты РСФ); А вот у Z80 - любой бит в доступной области, адресованной как ОЗУ Да вот еще для любителей асма viewtopic.php?f=20&t=68985 ежли кому пригодится иль чего добавить найдется Насчет "джиттера": почему процесс ждет прерывание , а не прерывание процесс? предварительный вывод данных в прот и стробирование аппаратным сигналом от таймера (OCxA/OCxB) с помощью внешнего элемента "И", а прерывание по таймеру всего лишь меняет выводимую информацию для следующего такта
Насчет "джиттера": почему процесс ждет прерывание , а не прерывание процесс? предварительный вывод данных в прот и стробирование аппаратным сигналом от таймера (OCxA/OCxB) с помощью внешнего элемента "И", а прерывание по таймеру всего лишь меняет выводимую информацию для следующего такта
Ну, элементом "И" дело не обойдётся, IMHO. Скорей нужен D-триггер. Ну, и, как всегда - это ж дополнительные компоненты, и если можно обойтись без них...
_________________ Когда уже ничего не помогает - прочтите, наконец, инструкцию. Лучший оптимизатор находится у вас между ушей. (Майкл Абраш, программист Quake и QuakeII) Избыток информации ведёт к оскудению души - Леонтьев А. (сказано в 1965 г.)
А я к "религиозным маньякам" не отношусь - для пользы дела не побрезгую и разного рода "рассыпухой"
Уважаемый BOB51, речь идёт всего лишь об одном способе из множества, как вы, наверное, понимаете. А выберет кто-то этот или другой способ, это его личное дело. Посему, предлагаю воздерживаться от обсуждения чьих бы то ни было "маниакальных" предпочтений.
Если кто-то считает, что какой-то код или алгоритм имеет некую "фишку" - пусть приведёт его здесь, опишет назначение, как работает и в чём "фишка".
Только давайте не будем перепечатывать правильные алгоритмы из книжек. Исключением, думаю, могут быть только случаи, когда в книжках есть что-то лучше, чем представленное тут.
_________________ Когда уже ничего не помогает - прочтите, наконец, инструкцию. Лучший оптимизатор находится у вас между ушей. (Майкл Абраш, программист Quake и QuakeII) Избыток информации ведёт к оскудению души - Леонтьев А. (сказано в 1965 г.)
Ага, когда первый раз пробегал мимо этой темы, то хотел линк именно на этот код дать, но сохранённые протухли. Потом вспомнил, что телесистемы переезжали когда-то, нашел одну тему по ключевым словам, а в другом линке уже просто поменял начало.
Так же быстро как с IJMP и просто супер компактно.
Эти два алгоритма писались для разных задач. Первичный вариант с IJMP легко растаскивается на большие времена, например, если в коде есть запрет прерывания на какое-то время (другое короткое прерывание или там запуск записи EEPROM). Надо выровнять до десятков тактов -- пожалуйста, константу нужную в MAX_JITTER и всё (это к коду по первому линку, там тоже под gnu-тый avr-as). Ну а с LPM — под конкретные условия разброса задержек в 3 такта, но на минимальную дополнительную задержку, что само дало и компактность.
_________________ Лень в виде мании величия: «ты гений, зачем стараться?». В виде комплекса: «всё равно не выйдет, зачем упираться?». Как логика: «если достаточно, зачем знать и уметь больше?». Цель одна: остановить. Не любит тепло работающих мышц и шум работающего мозга.
Насчет книжных поддерживаю, но не полностью - не мешает давать ссылки на литературу с интересной информацией и где взять, если имеется публикация в инете. Да и назвать что-либо абсолютно своим вряд-ли возможно, поэтому вводить абсолютную цензуру...как-то не слишком корректно - могут попасть и новички - сам выдумал, не прочитав предварительно умной книги того же Кнута (за 300 гривен одна штука из 5 возможных), или древнючие наставления по старинным МК которые не у всех-то и имеются по независящим от них причинам... Будет вернее давать к таким постам комментарий о прототипе, откуда взялся и возможные вариации (если конечно об этом более осведомленному Коту чего известно) Ну а прямое "дралово" с книжки безусловно не к месту, если не приведено в виде комента к сравнению с предлагаемым вариантом (цитаты)...хоша для цитат можно и ссылочку нацарапать...ежли источник всеобщего доступа... Кстати о ссылках: Каспер Э. Программирование на языке Ассемблера для микроконтроллеров семейства i8051. -М.:Горячая линия - Телеком, 2004.
Очень много интересного у Виктора Тимофеева на http://pic24.ru в частности, на http://pic24.ru/doku.php/articles/list . Одно из его решений я прикошачил в качестве макроса-псевдокоманды и для аврок: .macro xchrr ; псевдокоманда "обмен регистра/акумулятора/ с регистром" eor @0,@1 ; вызывается как xchrr rd,rs eor @1,@0 eor @0,@1 .endmacro
Однажды для одного проекта мне потребовалось быстро вычислять обратное значение заданного числа d (т.е. величину 1/d). Число d представлено в 32-битном формате с плавающей точкой IEEE-754 и соответствует типу данных float в языке С. Библиотечная реализация деления чисел с плавающей точкой не подошла по скорости. Алгоритм, который я реализовал был использован для реализации деления чисел с плавающей точкой в микрокоде одного из старых процессоров фирмы AMD и состоит в следующем (подробнее см. в статье http://www.cs.utexas.edu/users/moore/pu ... _paper.pdf).
Обратная величина x числа d, очевидно, удовлетворяет уравнению d•x - 1 = 0. Для нужд алгоритма это уравнение преобразовано в эквивалентное d•x•x – x = 0, которое на первый взгляд (и на второй тоже) сложнее исходного. Но в этом-то все и дело! Для решения уравнения использовался итерационный метод Ньютона – Рапсона для нахождения ненулевой фиксированной точки функции f(x) = d•x•x – x, т.е. числа x удовлетворяющего равенству x = x - f(x). Для данной f(x) это число x равно 1/d. Метод состоит в проведении итераций по формуле
с некоторым специально выбранным x_0. Казалось-бы к чему все эти сложности и школьный метод деления основанный на вычитании будет быстрее. Но нет - вся прелесть описываемого метода в том, что для достижения точности в +/- 1 lsb требудется всего 2 итерации!!! Таким образом, из арифметических операций для вычисления 1/d требуется произвести всего 4 умножения чисел с плавающей точкой и 2 вычитания. Ну не фантастика-ли? Просто гениально! Моя реализация этого метода работает более чем в 3 раза быстрее библиотечной процедуры обращения.
Реализация производилась на 16-битном процессоре семейства MSP430х5xxx. Это семейство оснащено аппаратным 32х32 бит перемножителем MPY32 с возможностью аккумулирования 64-битного результата. Попутно были использованы неколько приемов, позволяющих существенно сократить вычисления. Приведенная ниже программа вычисляет 1/d за 150 циклов процессора против около 500 циклов, требуемых для библиотечной.
Итак, нормализованное число d с плавающей точкой представимо в виде
d = s•(2^c)•m, где s – знак, c – двоичный порядок числа, а m – мантисса.
Для представления числа 1/d с плавающей точкой имеем
1/d = s•(2^(-c-1))•(1/m)
Отметим, что двоичный порядок в формате IEEE-754 представлен со смещением в 127 а мантисса m представлена только ее дробной частью. Целая часть мантиссы всегда равна 1 вследствии нормализации и явно не присутствует в представлении числа d. Так как для m имеем 1 < m < 2, то ½ < 1/m < 1. Поэтому для нормализации 1/m это число умножается на 2 и из его порядка в формуле выше вычитается 1. В приведенной программе вычисление порядка числа 1/d занимает 3 (хитрые!) операции в самом начале и порядок сохраняется в регистре R15. Оставлю этот момент без комментариев.
В качестве начального приближения x_0 для проведения итераций используется таблица в 128 байт. Подробнее о таблице см. в цитируемой статье. Ключем для таблицы являются старшие 7 бит мантиссы (отсюда и ее длина 2^7 = 128). Для вычисления произведения d•x_n первое число загружается в регистры OP2L и OP2H перемножителя, а второе после добавления к ней целой части – в регистры MPY32L и MPY32H. Это позволяет впоследствии не загружать x_n еще раз для второго умножения в каждой итерации. Полученное в результате умножения 48-битное число округляется до 24 бит.
Следующая хитрость в проведении вычитания результата из 2 согласно формуле. Теоретически надо было-бы выравнивать порядки 2 и d•x_n в соответствии с правилами арифметики с плавающей точкой. Однако, в нашем случае порядок x_n равен (-c-1) в то время как порядок d равен c. T.o. порядок произведения d•x_n равен -1 и, значит, после приведения порядка к 0 сдвигом десятичной точки на 1 бит влево из 48 бит числа d•x_n целая часть его представлена единственным битом (самым левым), который всегда равен 1 и, значит, его дробная часть состоит из 47 бит. Следовательно из двойки нужно вычитать число вида 1.ххххх где хххх – дробная часть. Нетрудно убедиться, что для вычитания просто следует инвертировать все биты произведения d•x_n и добавить к результату 1 (что будет 2-комплементарным двоичным представлением отрицательного числа -d•x_n). Таким образом, само вычитание в формате с плавающей точкой практически бесплатно и производится за 4 цикла ЦПУ.
В конце каждой из двух итераций в полученном 48-битном числе оставляются 24 бита сначала путем отбрасывания 16 младших битов (это делается бесплатно просто игнорированием младшего 16-битного слова в 64-битном регистре перемножителя) и последующего сдвига полученного 32-битного числа на 8 бит вправо. Вопрос к читателям как это сделать наиболее эффективно. Я просто переставлял байты и в результате сдвиг 32-битного значения в регистрах R9:R8 занял 10 циклов. За время работы алгоритма производится 4 таких сдвига, что занимает в общей сложности 40 циклов из 150, т.е. более, чем 25% времени. Ускорение реализации сдвига позволит ускорить всю процедуру в целом. При сдвиге использовалась следующая особенность MSP430: если производится байтовая операция над словом, то старший байт обнуляется. Таким образом для обнуления старшего байта, скажем, регистра R9 можно вместо традиционной инструкции типа
and.w #0x00FF, R9
которая занимает 5 байт в памяти и исполняется за 2 цикла использовать одно-цикловую и 2-х байтную команду
mov.b R9, R9
Вот код для сдвига:
Код:
swpb R8 ; shift R9:R8 8 bits right mov.b R8, R8 ; clear MSB mov.b R9, R10 swpb R9 mov.b R9, R9 swpb R10 add.w R10, R8 ; leave only 24 bits of the result
В самом конце процедуры из 24-битной мантиссы числа удаляется целая часть (всегда равная 1) и добавляется порядок. Все вышесказанное работает правильно если обращаемое число d не равно степени двойки. В противном случае x_0 будет отрицательная степень 2 и после нормализации на каждой итерации из 2 будет вычитаться 1 без дробной части и результат не будет строго меньше 1. Т.е. целая часть результата не будет равна 0 и для нормализации следует увеличить порядок на 1. Эта коррекция завершает всю процедуру.
Спойлер
Код:
mov.w #0x4000, R4 ; number to invert mov.w #0x443F, R5 ; 765.0
invert: mov.w R5, R15 ; R15=order add.w #0x4100, R15 ; extract the order xor.w #0x3F80, R15 ; adjust the order and.w #0x7F80, R15 ; clear the sign bit incd.w R15 ; R15[1:0] is the loop counter
and.b #0x7F, R5 ; leave only mantissa bits mov.w R4, R6 ; R7:R6 = copy of original mantissa d mov.w R5, R7 bis.b #0x80, R7 ; add hidden 1
mov.b rev(R5), R5 ; get table entry in eax clr.w R4 ; R5:R4 = x_0
dec.w R15 ; update the counter bit.b #1, R15 ; to perform 2 iterations of jnz nrl ; Newton - Raphson
and.b #0x7F, R5 ; get rid of hidden 1 jnz $+6 ; jump over the next line add.w #0x80, R15 ; correction for a power of 2 add.w R15, R5 ; add the order; R5:R4 = 1/d ret
rev: db 11111111b, 11111101b, 11111011b, 11111001b, 11110111b, 11110101b, 11110100b, 11110010b db 11110000b, 11101110b, 11101101b, 11101011b, 11101001b, 11101000b, 11100110b, 11100100b db 11100011b, 11100001b, 11100000b, 11011110b, 11011101b, 11011011b, 11011010b, 11011000b db 11010111b, 11010101b, 11010100b, 11010011b, 11010001b, 11010000b, 11001111b, 11001101b
db 11001100b, 11001011b, 11001010b, 11001000b, 11000111b, 11000110b, 11000101b, 11000100b db 11000010b, 11000001b, 11000000b, 10111111b, 10111110b, 10111101b, 10111100b, 10111011b db 10111010b, 10111001b, 10111000b, 10110111b, 10110110b, 10110101b, 10110100b, 10110011b db 10110010b, 10110001b, 10110000b, 10101111b, 10101110b, 10101101b, 10101100b, 10101011b
db 10101010b, 10101001b, 10101000b, 10101000b, 10100111b, 10100110b, 10100101b, 10100100b db 10100011b, 10100011b, 10100010b, 10100001b, 10100000b, 10011111b, 10011111b, 10011110b db 10011101b, 10011100b, 10011100b, 10011011b, 10011010b, 10011001b, 10011001b, 10011000b db 10010111b, 10010111b, 10010110b, 10010101b, 10010101b, 10010100b, 10010011b, 10010011b
db 10010010b, 10010001b, 10010001b, 10010000b, 10001111b, 10001111b, 10001110b, 10001110b db 10001101b, 10001100b, 10001100b, 10001011b, 10001011b, 10001010b, 10001001b, 10001001b db 10001000b, 10001000b, 10000111b, 10000111b, 10000110b, 10000101b, 10000101b, 10000100b db 10000100b, 10000011b, 10000011b, 10000010b, 10000010b, 10000001b, 10000001b, 10000000b
Одно из его решений я прикошачил в качестве макроса-псевдокоманды и для аврок: .macro xchrr ; псевдокоманда "обмен регистра/акумулятора/ с регистром" eor @0,@1 ; вызывается как xchrr rd,rs eor @1,@0 eor @0,@1 .endmacro
Эта штука тоже теряется в глубинах истории программизма. На С пишется как
Код:
a ^= b; b ^= a; a ^= b;
одно время, довольно давно (во всяком случае, до появления AVR ), когда компиляторы имели менее агрессивную оптимизацию, народ, забывая о точках следования, писал так:
Код:
a ^= b ^= a ^= b;
А ещё раньше, «в этих ваших фортранах» без операции XOR, писали как-то так:
Код:
a = a + b; b = a - b; a = a - b;
На асме без операции «обратного вычитания» для второй строки это будет неэффективно. На ЯВУ иначе только с третьей переменной, арифметика оказывалось эффективнее, так как компилятор всё в регистрах утаптывал. На асме pic16 эта операция тоже хороша, а в некоторых случаях она сокращается до двух операций, но делает больше, чем обмен!
Код:
xorwf prev_buttons, w ; в W -- маска кнопок, поменявиших своё значение xorwf prev_buttons, f ; в prev_buttons -- новое значение кнопок заменило старое ; а третий xorwf var, w , который восстановил бы в W старое значение, завершив обмен -- не делаем.
Соответственно, у меня было два мкроса, для обмена и более короткий для "обмена старого с новым и сравнения их с выбрасыванием старого"
_________________ Лень в виде мании величия: «ты гений, зачем стараться?». В виде комплекса: «всё равно не выйдет, зачем упираться?». Как логика: «если достаточно, зачем знать и уметь больше?». Цель одна: остановить. Не любит тепло работающих мышц и шум работающего мозга.
(/to,/pd) clrwdt sleep nop call goto retlw K <return> <retfie>
+----------+ | irp | rp1 | rp0 | /to | /pd | z | dc | c | +-----+-----+-----+-----+-----+-----+-----+-----+
---------- { set | clr | skp[n] } { c | dc | z } b[n]{ c | dc | z }
И ещё одна операция с применением XOR -- загрузка константы в переменную, не меняя содержимое W, это коллега придумал, а не я. Макрос под ASPIC by Don Lekei, но, думаю, суть понятна. Спойлер
Код:
; в зависимости от константы генерируется код минимальной длины movlfww .macro val,dst __tst_skip .switch (val) .case 0 clrf dst .else .case $FF clrf dst decf dst,f .else .case $01 clrf dst incf dst,f .else .case $FE clrf dst decf dst,f decf dst,f .else .case $02 clrf dst incf dst,f incf dst,f .else .case (other) xorlw val movwf dst xorlw val xorwf dst,f .endif .endm
Кроме того, у pic не выйдет сравнивать с разными константами и переходить, как у AVR при помощи CPI. Тут опять поможет XOR. switch-подобные макросы, только для маски не делался стек и вложенные switch недопустимы Спойлер
Код:
; обнуляем маску wswitch .macro * wswmsk .set 0 .endm ; каждый раз делаем xor с результатом xor из новой константы для сравнивания и ; xor-сборки всех предыдущих констант. ; ну а в W сидит xor исходного значения и всех предыдущих констант wcase .macro *val,lab __tst_skip xorlw (val^wswmsk) wswmsk .set val jz lab .endm ; если надо, то в конце, после всех несовпадений, восстанавливаем значение W wsrest .macro * xorlw wswmsk wswmsk .set 0 .endm ; Использовать как-то так wswitch wcase 'A', recv_a wcase 'B', recv_b wcase 'C', recv_c wrest ; только если нужно после всех несовпадений восстановить W ; обработка default ветки ...
recv_a: ...
recv_b: ...
Вставка битов из W в битовое поле в переменной dst Маска битов может быть константа (с префиксом #) или храниться в другой переменной mask После операции в W остаётся маска изменившихся битов в этом поле. Спойлер
Код:
; dst=(w&mask)|(dst&~mask) ; w =(w^dst)&mask InsBitsW .macro dst,mask __tst_skip xorwf dst,w .IF 'mask[0.1]'=='#' ; это аргумент разбирается, тут выделяется первый символ и проверка на # andlw mask[1.0] ; а тут все символы, кроме первого .ELSE andwf mask,w .ENDIF xorwf dst,f .endm
_________________ Лень в виде мании величия: «ты гений, зачем стараться?». В виде комплекса: «всё равно не выйдет, зачем упираться?». Как логика: «если достаточно, зачем знать и уметь больше?». Цель одна: остановить. Не любит тепло работающих мышц и шум работающего мозга.
Да, это отличный пример того, что оптимизация алгоритма должна идти до оптимизации кода и математику нужно знать
_________________ Лень в виде мании величия: «ты гений, зачем стараться?». В виде комплекса: «всё равно не выйдет, зачем упираться?». Как логика: «если достаточно, зачем знать и уметь больше?». Цель одна: остановить. Не любит тепло работающих мышц и шум работающего мозга.
Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
Добавлено: Сб сен 22, 2012 15:04:45
Цитата:
А вот у Z80 - любой бит в доступной области, адресованной как ОЗУ
Кроме всего прочего есть у него ещё недокументированные команды, которые местами сокращали код. Особенно прикольно было их использовать для защиты программ. Стандартными средствами не сразу подъехать можно . У меня был их полный список когда-то.
ну с картами на все доступные на момент их создания командами для Z80 несложно, жаль только, что это (в отличии от более поздних) отсканированная копия ручной работы весом 7, 3 мегабайта - ежли кого заинтересует - пишите куда скинуть
Заголовок сообщения: Re: Хитрые, необычные алгоритмы и код
Добавлено: Сб сен 22, 2012 22:55:09
Держит паяльник хвостом
Карма: 15
Рейтинг сообщений: 70
Зарегистрирован: Ср мар 28, 2012 21:45:24 Сообщений: 906 Откуда: ВО
Рейтинг сообщения:0
Предлагаю тему прекрипить. Предварительно почистив весь лишний трёп . Ну а далее всё таки соблюдать порядок предложеный ТС. А то эти рассуждения хорошо - плохо , скоро "убют" саму идею
_________________ Когда уже ничего не помогает - прочтите, наконец, инструкцию. Лучший оптимизатор находится у вас между ушей. (Майкл Абраш, программист Quake и QuakeII) Избыток информации ведёт к оскудению души - Леонтьев А. (сказано в 1965 г.)
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения