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

[Kavka]

*Trigger*, способ получить ещё одно внешнее прерывание, конечно, не "прямой" , но интересный.
Однако, в вашем случае больше ни для чего нельзя использовать таймер. Что может быть весьма неудобно.
Я бы сказал, есть путь "прямее" и, к тому же, таймер можно использовать для чего-то другого.
Цитата из спека на мегу8:

Bit 6 – ICES1: Input Capture Edge Select
This bit selects which edge on the Input Capture Pin (ICP1) that is used to trigger a capture
event. When the ICES1 bit is written to zero, a falling (negative) edge is used as trigger, and
when the ICES1 bit is written to one, a rising (positive) edge will trigger the capture.
When a capture is triggered according to the ICES1 setting, the counter value is copied into the
Input Capture Register (ICR1). The event will also set the Input Capture Flag (ICF1), and this
can be used to cause an Input Capture Interrupt, if this interrupt is enabled.

Т.е. на основе Input Capture можно получить ещё одно внешнее прерывание с сохранением, так сказать, таймера.
Прерывание будет Timer/Counter1 Capture Event (TIMER1 CAPT).

[*Trigger*]

Да, действительно. Что-то я про захват забыл. Но можно использовать их одновременно, получив ещё два прерывания.

[akl]

Месяц прошёл - можно поднять тему На неделе понадобился большой-пребольшой линейный счётчик с выводом на индикатор. Как нельзя лучше подошёл алгоритм ILYAUL приведённый в этой теме. Может ещё кому понадобится.

count_bcd.asm

[akl]

Здравствуйте. Недавно, на соседнем форуме был задан вопрос о быстром умножении 24-разрядных чисел. Было предложено использование алгоритма Дональда Кнута. В результате появился код, который выполняет
Умножение 24р*24р=48р выполняется за 75 тактов и занимает 65 слов
Умножение 32р*32р=64р выполняется за 134 такта и занимает 117 слов
Формат представления чисел старший-младший

MULT_KNUTH.zip

[Gudd-Head]

Задумался я о выводе текста на графическом дисплее (например, WS0010).
Например, нарисовали шрифты 5×8 точек (5 байт на символ) — 32 буквы (без "ё") или 31 (без "ё" и "ъ", но с пробелом) чтобы уложиться в 5 бит.
Или нарисовать весь алфавит, цифры и символы — всего 64 знака, т.е. 6 бит кодируют символ. Куда применить остальные 2 или 3 бита?

Спойлер

Можно, конечно, извратиться и кодировать текст, пихая биты подряд, не привязываясь к байтам:
0b11111122 0b22223333 0b33444444
Но это сложно как с точки зрения кодирования, так и с т.з. реализации функции вывода. Очевидно, проще так:
0b00111111 0b00222222 0b00333333 0b00444444,
где 1, 2, 3 и 4 — соответственно первый, второй, третий и четвёртый символ (буква)

Ответ прост: «архивировать» (кодировать) ещё один символ! Но не любой, а только 3 или 7 наиболее часто встречающихся. В русском языке (согласно http://ru.wikipedia.org/wiki/Частотность ) это (в порядке убывания частоты) «О», «Е», «А», «И», «Н», «Т», «С».
Например, сделаем в таблице шрифтов (32 символа, т.е. 5 информационных бит и 3 дополнительных) так, чтобы у буквы «О» было условное смещение в таблице = 1, у «Е» = 2 и т.д., т.е. вынесем их в начало таблицы. Тогда слово «НЕТ» в памяти программ без «архивации» будет занимать 3 байта:
0b00000101 0b00000010 0b00000110,
а с данным алгоритмом — всего 2:
0b01000101 0b00000110,
здесь буква «Е» переехала в старшие 2 бита буквы «Н». Экономия места в памяти программ (ПП)!
Причём сама функция вывода усложнилась совсем чуть-чуть. Если раньше было (5+3 бит)

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

1. считали байт из ПП
2. вызвали процедуру печати символа
3. уменьшили (декремент) счётчик
4. переход к п.1, если не ноль

, то стало

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

1. считали байт из ПП
2. скопировали его
3. маскируем его (лог. «И») с 0b00011111 
4. вызвали процедуру печати символа
5. проверили копию на наличие ещё одного символа
// если все 3 старшие биты нулевые — второго символа в данном байте нет
// проще всего организовать через сравнение с константой 0b00011111
6. переход к п.10, если второго символа нет
7. иначе переместили старшие 3 бита в младшие
// например, через обмен тетрадами и сдвиг вправо
8. маскировали его (лог. «И») с 0b00000111 
9. вызвали процедуру печати символа
10. уменьшили (декремент) счётчик
11. переход к п.1, если не ноль

[kisssko]

Рисование линий. Улучшенный алгоритм Брезенхема. В зависимости от направления рисования код делится на восемь подалгоритмов. Но сами по себе они проще, чем у Брезенхема, операций в цикле меньше, а значит, должно работать быстрее. Функцию plot() реализуем сами, как хочется.

Спойлер

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

#define DIR_LRTB   0   // LEFT  to RIGHT, TOP    to BOTTOM
#define DIR_RLTB   1   // RIGHT to LEFT,  TOP    to BOTTOM
#define DIR_LRBT   2   // LEFT  to RIGHT, BOTTOM to TOP
#define DIR_RLBT   3   // RIGHT to LEFT,  BOTTOM to TOP

void draw_line(int x0, int y0, int x1, int y1, int c)
{
   int x,y,dx,dy,s;
   char d=0;
   x=x0; y=y0;
   if(x0>x1){d|=1;dx=x0-x1;}else{dx=x1-x0;}
   if(y0>y1){d|=2;dy=y0-y1;}else{dy=y1-y0;}
   switch(d)
   {
   case DIR_LRTB:
         if(dy>dx)
         {
            for(s=dx;y<=y1;y++)
            {
               plot(x,y,c);
               s+=dx;
               if(s>=dy){x++;s-=dy;}
            }
         } else
         {
            for(s=dy;x<=x1;x++)
            {
               plot(x,y,c);
               s+=dy;
               if(s>=dx){y++;s-=dx;}
            }
         }
         break;
   case DIR_RLTB:
         if(dy>dx)
         {
            for(s=dx;y<=y1;y++)
            {
               plot(x,y,c);
               s+=dx;
               if(s>=dy){x--;s-=dy;}
            }
         } else
         {
            for(s=dy;x>=x0;x--)
            {
               plot(x,y,c);
               s+=dy;
               if(s>=dx){y++;s-=dx;}
            }
         }
         break;
   case DIR_LRBT:
         if(dy>dx)
         {
            for(s=dx;y>=y0;y--)
            {
               plot(x,y,c);
               s+=dx;
               if(s>=dy){x++;s-=dy;}
            }
         } else
         {
            for(s=dy;x<=x1;x++)
            {
               plot(x,y,c);
               s+=dy;
               if(s>=dx){y--;s-=dx;}
            }
         }
         break;
   case DIR_RLBT:
         if(dy>dx)
         {
            for(s=dx;y>=y0;y--)
            {
               plot(x,y,c);
               s+=dx;
               if(s>=dy){x--;s-=dy;}
            }
         } else
         {
            for(s=dy;x>=x0;x--)
            {
               plot(x,y,c);
               s+=dy;
               if(s>=dx){y--;s-=dx;}
            }
         }
         break;
   }
}

P.S. Код ещё будет дорабатываться.

[B@R5uk]

Небольшое исхищрение на тему экономии регистров МК.

Идея возникла в связи вот с какой задачей. Есть внешний цикл на 12 итераций (12 = 0x0C). Счётчик итераций умещается в пол-байта. И есть внутренний цикл на чуть более, чем 256 итераций (в моём случае 484 = 0x01E4). Счётчик итераций внутреннего цикла в байт ну никак не умещается, а второй регистр заводить для него жаба давит. Какой выход? Правильно! Уместить неуместившиеся разряды внутреннего счётчика в свободные разряды внешнего счётчика.

Сначала вариант "цивилизованного" кода, использующего все 3 регистра для счётчиков:

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

;               {...}
;               {делаем что-нибудь}
;               {...}
                ldi     r20,    0x0C    ;   Инициализация внешнего счётчика
outer_loop:
;               {...}
;               {содержимое внешнего цикла}
;               {...}
                ldi     r18,    0xE4    ;   Инициализация внутреннего счётчика
                ldi     r19,    0x01    ;   То, что не поместилось в байт
inner_loop:
;               {...}
;               {содержимое внутреннего цикла}
;               {...}
                dec     r18             ;   Уменьшаем внутренний счётчик
                brne    inner_loop
                dec     r19             ;   Тоже внутренний счётчик
                brne    inner_loop
                dec     r20             ;   Уменьшаем внешний счётчик
                brne    outer_loop
;               {...}
;               {делаем ещё что-нибудь}
;               {...}

А теперь экономный вариант с использованием всего 2-х регистров:

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

;               {...}
;               {делаем что-нибудь}
;               {...}
                ldi     r19,    0x0C    ;   Инициализация внешнего счётчика
outer_loop:
;               {...}
;               {содержимое внешнего цикла}
;               {...}
                ldi     r18,    0xE4    ;   Инициализация внутреннего счётчика
                ori     r19,    0xE0    ;   То, что не поместилось в байт
                                        ;   Величина, помещаемая в старший полубайт
                                        ;   вычисляется по формуле y = 0xF - x
                                        ;   В моём случае x=0x1, поэтому y=0xE
inner_loop:
;               {...}
;               {содержимое внутреннего цикла}
;               {...}
                dec     r18             ;   Уменьшаем внутренний счётчик
                brne    inner_loop
                subi    r19,    0xF0    ;   Тоже внутренний счётчик
                                        ;   Выполнение этой команды увеличивает
                                        ;   старший полубайт регистра r16 на 0x1,
                                        ;   при этом флаг переноса уставлен, кроме случая,
                                        ;   когда старший полубайт оказывается равным 0x0
                brcs    inner_loop
                dec     r19             ;   Уменьшаем внешний счётчик
                brne    outer_loop
;               {...}
;               {делаем ещё что-нибудь}
;               {...}

Как можно заметить, количество инструкций не увеличилось, за то уменьшилось число используемых разрядов. Правда, достигнуто это ценой усложнения программы для понимания. Однако, есть и другая, эстетическая сторона: разнообразился состав используемых инструкций МК. То была связка ldi / dec / brne, а теперь к ним добавились команды ori / subi / brcs.

Это ухищрение обладает достаточно большой гибкостью. Если бы количество итераций внешнего цикла умещалось бы в 3 бита, то целых 13 бит можно было бы использовать для счётчика внутреннего цикла. С другой стороны, если когда для внутреннего цикла требуется 9 бит как в моём случае, то для счётчика внешнего цикла можно использовать целых 7 бит сдвоенного регистра. Модификация требует всего лишь правильно задать значения констант.

Более того, в случае 7/9 (как у меня) можно сэкономить ещё и на одной инструкции МК — на инициализации самого старшего бита внутреннего счётчика, так как его инвертированное значение на входе во внутренний цикл всегда равно нулю, что и требуется. Я же в своей программе этого делать не стал, так как у меня может возникнуть необходимость увеличить число итераций внутреннего цикла.

Вот ещё один, чуть более человечный вариант:

Спойлер

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

;               {...}
;               {делаем что-нибудь}
;               {...}
                ldi     r19,    0x0C    ;   Инициализация внешнего счётчика
outer_loop:
;               {...}
;               {содержимое внешнего цикла}
;               {...}
                ldi     r18,    0xE4    ;   Инициализация внутреннего счётчика
                ori     r19,    0x10    ;   То, что не поместилось в байт
inner_loop:
;               {...}
;               {содержимое внутреннего цикла}
;               {...}
                dec     r18             ;   Уменьшаем внутренний счётчик
                brne    inner_loop
                subi    r19,    0x10    ;   Тоже внутренний счётчик
                brcс    inner_loop
                subi    r19,    0xF1    ;   Уменьшаем внешний счётчик
                brne    outer_loop
;               {...}
;               {делаем ещё что-нибудь}
;               {...}

Интересно, а компилятор Си умеет делать такую оптимизацию?

[ua1arn]

внутренний цикл на чуть более, чем 256 итераций (в моём случае 484 = 0x01E4).

Расположить две итерации внутреннего цикла друг за другом, тем более что у Вас количество чётное. Счетчик станет 242.

[DX168B]

Когда нужно вернуться из процедуры или прерывания в другую точку программы,
можно сделать так:

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

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; STACK HACK FOR AVR                                      ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
.include "m8def.inc"
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
.dseg
.org         (RAMEND - 1)
st_ret_h:    .byte     1
st_ret_l:    .byte     1
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
.cseg
.org 0x0000
            rjmp    RESET

.org         INT_VECTORS_SIZE
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
RESET:        ldi        r16,            Low(RAMEND)
            ldi        r17,            High(RAMEND)
            out        SPL,            r16
            out        SPH,            r17

            rcall    TEST

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
LX:            rjmp    LX

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
LOOP:        rjmp    LOOP

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
TEST:        ldi     r16,             Low(LOOP)
            sts     st_ret_l,         r16
            ldi        r16,            High(LOOP)
            sts        st_ret_h,        r16
            ret

После возвращения из процедуры TEST, мы должны попасть в цикл LX, если не шаманить со стеком.
Но мы попадаем в цикл LOOP, так как переписали в стеке адрес возврата напрямую.
То есть, без использования инструкций PUSH / POP. Единственное, что не надо забывать при таком
приеме, это вытащить предварительно все данные, вручную помещенные в стек.

[ARV]

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

[Engineer_Keen]

...причем в случае с AVR можно задать 7 различных делителей тактовой для АЦП и получить "нестандартные" для обычных таймеров (кроме режимов CTC) периоды в 13, 26, 52, 104, 208, 416, 832 и 1664 такта.

[Gudd-Head]

АЦП отлично может функционировать в качестве дополнительного таймера с фиксированным периодом счета...

Хм... А какой-нить УАРТ/И²С/СПИ тоже ведь так можно настроить?

[ARV]

АЦП отлично может функционировать в качестве дополнительного таймера с фиксированным периодом счета...

Хм... А какой-нить УАРТ/И²С/СПИ тоже ведь так можно настроить?

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

[Gudd-Head]

...это будет "однократный" таймер, который в обработчике прерываний придется перезапускать

Ну, 1-2 команды для запуска, думаю, не критично.

...этот "таймер" будет гадить на внешних линиях ввода-вывода

Это да. А вот у АЦП, если мультиплексором выбрать такую комбинацию бит, которым ничего не соответствует в ДШ будет нормально работать? И не задействует никакую ногу? (напр., MUX3:0 = 1000...1101 для 8-й меги). Если так, то это преимущество использования АЦП.

Зато УАРТ более гибкий в плане временного периода прерывания: ≈ Fтакт/(16*UBRR), где UBRR 12 бит у 8-й меги, т.е. можно получить частоту Fтакт/32 000.

[Engineer_Keen]

А вот у АЦП, если мультиплексором выбрать такую комбинацию бит, которым ничего не соответствует в ДШ будет нормально работать? И не задействует никакую ногу?

Практически у всех AVR (ну может кроме t13) есть комбинации для подключения мультиплексора на землю/опорное напряжение/внутренний термодатчик, так что думаю прокатит. Хотя я, как раз когда использовал этот прием в t13 тупо скоммутировал ногу, которая была цифровым входом...

[ARV]

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

[DX168B]

Еще один прием.
Допустим, у нас есть 100 команд и 100 действий.
Команды идут подряд (от нуля до 99)
К примеру приняли пакет по UART с адресом, командой, данными и CRC.
Команду надо как-то обработать. Длинный swith в Си или cpi r16, CMDx не канает, так как ест много тактов и памяти.
Но есть другое решение.

Вариант на Си:

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

#include <avr\io.h>
#include <util\delay.h>
#include <avr\pgmspace.h>

typedef int(*myFunc)(void);

int func1(void);
int func2(void);
int func3(void);

myFunc fArr[3] = {func1, func2, func3};

//----------
int main()
    {
        while(1)
        {
            for(int i = 0; i < 3; i++)
            {
                fArr[i]();
            }
        }
    }
//----------
int func1(void)
{
    PORTB=0x01;
    return 0;
}

int func2(void)
{
    PORTB=0x02;
    return 0;
}

int func3(void)
{
    PORTB=0x04;
    return 0;
}
 

В данном примере вызываются три функции по очереди. Если вместо индекса i
подставить значение команды, то вызовется соответствующая функция.

То же самое на АСМе: (выдран из рабочего проекта)

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

;---------- Адреса процедур
HANDLERS:
.dw MPT, RSTCFG, OPNCFG, MENUCFG, LIGHT_CFG, US_OV, STAT_CFG, SENS_CFG, CLR_CFG, MASTERCFG


;---------- конфигурации
CONFIG:
rcall         KEYREQ ;Опрос клавиатуры
cpi           temp0,            _NO_BT ; ничего не нажато (0xFF)
breq          CONFIG
cpi           temp0,            _CLR ;нажата кнопка "Сброс" (0x0F)
breq          CFGEND
cpi           temp0,            _A ; нажаты кнопки от А до Enter (всего 16 кнопок. 0...9, A, B, C, D, Enter, CLR) = (0x00...0x0F)
brsh          CFGERR
ldi           ZL,               Low(HANDLERS*2) ; нажаты кнопки от 0 до 9
ldi           ZH,               High(HANDLERS*2) ; соответственно, выбран один из пунктов меню. Загружаем адрес начала массива адресов процедур
lsl           temp0 ; Из-за типичной для AVR организации памяти, приходится домножать номер процедуры на два простым сдвигом влево.
clr           temp1
add           ZL,               temp0 ;смещаемся до нужного элемента массива
adc           ZH,               temp1
lpm           dx2,              Z ; грузим адрес из массива
adiw          Z,                0x01
lpm           dx3,              Z
mov           ZL,               dx2
mov           ZH,               dx3
icall ; вызываем процедуру
rjmp          CONFIG
CFGERR:
rcall         ERR ; индикация ошибки
rjmp          CONFIG
;---------- Выход из меню
CFGEND:
rcall         INIT
ret

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;----------
MPT:
;процедура номер ноль
ret

;---------- 
RSTCFG:
;процедура номер раз
ret

;----------
OPNCFG:
;процедура номер два
ret

;----------
MENUCFG:
; процедура номер три
ret

;----------
LIGHT_CFG:
;процедура номер четыре
ret

;----------
US_OV:
;процедура номер пять
ret

;----------
STAT_CFG:
;процедура номер шесть
ret

;----------
SENS_CFG:
;процедура номер семь
ret

;----------
CLR_CFG:
;процедура номер восемь
ret

;----------
MASTERCFG:
;процедура номер девять
ret

В семействе MEGA код можно упростить, но этот пример писался для семейства TINY с урезанными набором инструкций.

Данные приемы экономят как память, так и такты.

[menzoda]

Скорее, предыдущий совет - это то, как не надо делать. Точнее так. Использования обработчиков и таблицы переходов само по себе не плохо, но не в случае оптимизации switch, потому что:
1. Мы экономим на семечках. В подавляющем большинстве случаев обработка команд происходит в фоне и выигрыш в несколько тактов не стоит усложнения кода. Иначе стоит задуматься об архитектуре приложения, а не заниматься бесполезной оптимизацией.
2. Конструкция switch с более-менее равномерным диапазоном значений с большой долей вероятности преобразуется компилятором в ту же самую таблицу переходов. Зачем делать за компилятор то, что он может сделать лучше?

[menzoda]

Намного проще и правильней выглядит вот такой вариант:

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

void Handle(Command cmd)
{
    case Command1: Handle1(); break;
    case Command2: Handle2(); break;
    case Command3: Handle3(); break;
    case Command4: Handle4(); break;
    case Command5: Handle5(); break;
    case Command6: Handle6(); break;
    case Command7: Handle7(); break;
    case Command8: Handle8(); break;
    case Command9: Handle9(); break;
    case CommandA: HandleA(); break;
    case CommandB: HandleB(); break;
    case CommandC: HandleC(); break;
    case CommandD: HandleD(); break;
    case CommandE: HandleE(); break;
    case CommandF: HandleF(); break;

    default: Handle0(); break;
}

Весь код из switch так же выносится в обработчики. Ориентироваться в таком switch очень легко, даже если он длинный. Не надо смотреть в таблицу, чтобы понять какая команда какому обработчику соответствует. Не надо шерстить таблицу, чтобы заменить один на другой, удалить, или добавить обработчик. Легко реализуется обработчик по умолчанию. Нет проблем, если команды имеют большие номера. Нет проблем, если номера команд стоят далеко друг от друга. Компилятор оперирует на уровне отдельных инструкций, у него гораздо больше возможностей оптимизировать всё это.

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

[DX168B]

mezonda ладно. Пусть пример на Си останется для тех, кто плохо понимает ассемблер или только начал изучать его (но уже был знаком с Си).
То есть, пример на Си описывает принцип работы примера на ассемблере.
Но на АСМе оно пригодится. У меня так в одном девайсе клавиатуная менюшка реализована. По примеру охранных устройств от компаний DSC и Cerber.
У крупных ППКОП от DSC количество пунктов в главном меню достигает нескольких сотен, а в качестве "мозга" стоит PIC средней паршивости. (на некоторых моделях видел даже Z80)
Там наверняка такая реализация.