Вычисления на ATmega88 Опции

[koluna]

Здравствуйте!

Использую WinAVR, ATmega88, сигнал синхронизации - внтутренняя RC-цепь (частота 8 МГц).
Необходимо как можно быстрее вычислить значение следующего выражения:

C = Y * C' / 255.
Причём:
C, Y, C' - unsigned char, т. е., действительные числа мне не нужны...

В данный момент вычисления производятся приблизительно за 92 мкс (в программе три выражения подряд).

Можно, конечно, кварц поставить на большую частоту, но хотелось бы пока без него

Фрагмент программы:

Код

...
OCR0A = n_red * dmx[0] / 255;
OCR0B = n_green * dmx[0]  / 255;
OCR2B = n_blue * dmx[0] / 255;
...

Спасибо заранее!

[Непомнящий Евген...]

а если поделить на 256? Компилер должен превратить такое деление в сдвиг (или можно руками написать >>8).
Разница будет довольно мала...

[Арк К]

А надо делить именно на 255? не на 256?
тогда было бы нужно просто выкинуть младший байт
Критичные ко времени места лучше делать на ассемблере.

[Непомнящий Евген...]

Критичные ко времени места лучше делать на ассемблере.

Тут засада будет скорее именно в делении. И если от него не избавиться - врядли на асме получится сильно быстрее...

[_Pasha]

Код

...
OCR0A = n_red * dmx[0] / 255;
OCR0B = n_green * dmx[0]  / 255;
OCR2B = n_blue * dmx[0] / 255;
...

Спасибо заранее!

Используйте предварительно посчитанные значения K=M*dmx[0]/255
где М выбирается таким, чтобы получалось то, что делается быстрее, т.е. умножение на К и взятие старшего байта произведения.
асмовый текст, раз уж заговорили про скорость

Код

  lds r24,K
  lds r25,n_red
  mul r24,r25
  out OCR0A,r1
  lds r25,n_green
  mul r24,r25
  out OCR0A,r1
  lds r25,n_blue
  sts OCR2A,r1

Надеюсь, принцип понятен.

[=GM=]

Необходимо как можно быстрее вычислить значение следующего выражения: C = Y * C' / 255

C=(Y*C1*257) >> 16;

Или совсем уж убыстрить

С2=Y*C1;
C=((C2 << 8)+С2) >> 16;

На асме просто взять два старших байта.

[Непомнящий Евген...]

C=(Y*C1*257) >> 16;

Тогда уж так

C=((unsigned long)Y*C1*257) >> 16;

- у топик стартера Y и С1 - unsigned char

Кстати, классное решение

[=GM=]

Тогда уж так C=((unsigned long)Y*C1*257) >> 16;
Кстати, классное решение

А то! Но всё-ж-таки, нормальный компилер должен сам типы приводить.

[Непомнящий Евген...]

Используйте предварительно посчитанные значения K=M*dmx[0]/255
где М выбирается таким, чтобы получалось то, что делается быстрее, т.е. умножение на К и взятие

Не могли бы вы пояснить эту мысль? К зависит от двух 1-байтных чисел, объем таблицы получится 65536 байт... Или я вас не так понял?

C=(Y*C1*257) >> 16;

Или совсем уж убыстрить

С2=Y*C1;
C=((C2 << 8)+С2) >> 16;

А кстати, нифига

(С2*257) >> 16 =( (С2 <<8) + C2)>>16 = ((C2<<8)>>16) + (C2>>16) = C2>>8 = C2 / 256 ...

сдвиг на 16 - это ж деление на 65536, а не на 65535

[_Pasha]

Не могли бы вы пояснить эту мысль? К зависит от двух 1-байтных чисел, объем таблицы получится 65536 байт... Или я вас не так понял?

Я обратил внимание на то, что эта часть dmx[0] / 255; должна быть вычислена один раз и больше не участвовать в окончательных выражениях. Таблицей, конечно, не получится
ЗЫ - наверное, автору все-таки нужно сразу делить на 256, потому что разница в 3 промилле, наверняка, не важна.

[LordVader]

Вот что нагуглилось: http://www.sharpthinking.net/cv/div255.pdf
Быстрое деление на 255. Вкратце: a/255 = ((a>>8)+a+128)>>8 с округлением к ближайшему целому.

[=GM=]

(С2*257) >> 16 =( (С2 <<8) + C2)>>16 = ((C2<<8)>>16) + (C2>>16) = C2>>8 = C2 / 256 ...
сдвиг на 16 - это ж деление на 65536, а не на 65535

Так и задумывалось, делить на 65536, чтобы был сдвиг на 16 бит, а не деление на 65535.

Вот здесь ошибочка у вас ((C2<<8)>>16) + (C2>>16) = C2>>8+(C2>>16).

Округление можно так сделать C=((C2 << 8)+С2+32768) >> 16;

[VDG]

Человек скорее всего управляет RGB-светодиодом, а деление на 255 - это соответственно "нормализация в восьмибитное число" после умножения на коэффициент яркости. В таком случае, деление на 255 - ошибка. На 256 надо делить, или как выше сказали - взять HIBYTE.

[Непомнящий Евген...]

Вот здесь ошибочка у вас ((C2<<8)>>16) + (C2>>16) = C2>>8+(C2>>16).

С2 = У * С1

У и С1 - unsigned char, т.е. их произведение <=65535. Сдвиг на 16 влево такого числа даст 0. Поэтому (C2>>16) == 0

Так и задумывалось, делить на 65536, чтобы был сдвиг на 16 бит, а не деление на 65535.

Ну просто это получается эквивалентно C2/256. Просто малость замаскировано

[koluna]

А надо делить именно на 255? не на 256?
тогда было бы нужно просто выкинуть младший байт
Критичные ко времени места лучше делать на ассемблере.

Понятно, что на ассемблере быстрее будет работать...
Но я не знаю как сопрячь WinAVR C и ассемблер

Используйте предварительно посчитанные значения K=M*dmx[0]/255
где М выбирается таким, чтобы получалось то, что делается быстрее, т.е. умножение на К и взятие старшего байта произведения.
асмовый текст, раз уж заговорили про скорость

Код

  lds r24,K
  lds r25,n_red
  mul r24,r25
  out OCR0A,r1
  lds r25,n_green
  mul r24,r25
  out OCR0A,r1
  lds r25,n_blue
  sts OCR2A,r1

Надеюсь, принцип понятен.

К сожалению принцип не понятен пока.
Сколько нужно памяти для предварительно посчитанных значений?

Я обратил внимание на то, что эта часть dmx[0] / 255; должна быть вычислена один раз и больше не участвовать в окончательных выражениях. Таблицей, конечно, не получится
ЗЫ - наверное, автору все-таки нужно сразу делить на 256, потому что разница в 3 промилле, наверняка, не важна.

f = dmx[0] / 255 делается действительно 1 раз.
Я вынес эту операцию в другое место.
Теперь делаю только С = C' * f.
Время выполнения сократилось приблизительно на 10 мкс (кстати, я ещё кварц на 20 МГц поставил).
Но хотелось бы ещё побыстрее...

Человек скорее всего управляет RGB-светодиодом, а деление на 255 - это соответственно "нормализация в восьмибитное число" после умножения на коэффициент яркости. В таком случае, деление на 255 - ошибка. На 256 надо делить, или как выше сказали - взять HIBYTE.

Ими и управляю. Поясню.

Регулирую яркость 8-битным ШИМом микроконтроллера.
Имеем 4 внешних контролла, от которых зависит результирующий цвет луча и его интенсивность.

1 - Общая световая интенсивность dmx[0].
2 - Интенсивность красного n_red.
3 - Интенсивность зелёного n_green.
4 - Интенсивность синего n_blue.

Т. е., моя задача - вычислить значение 8-битного регистра сравнения OCR микроконтроллера, которое зависит от dmx[0] и n_red/n_green/n_blue.

Придумал управлять так:

Код

OCR0A = n_red * dmx[0] / 255;
OCR0B = n_green * dmx[0]  / 255;
OCR2B = n_blue * dmx[0] / 255;

Но подвело меня деление...

Почему надо делить на 256?
Ясное дело, это сдвиг вправо на 8 - выполняется молниеносно, но почему 256?
Т. е., просто согласиться с появляющейся ошибкой?

Сообщение отредактировал n_bogoyavlensky - Dec 3 2008, 08:26

[_Pasha]

Т. е., просто согласиться с появляющейся ошибкой?

Я ж говорю 256/255 = 1.0039 Точнее - 4 промилле.

Но я не знаю как сопрячь WinAVR C и ассемблер

Сишка:

Код

uint8_t n_red,n_green,n_blue;
uint8_t precomputed;
extern void fast_out(void);

Добавляете в проект файл fast_out.S

Код

#include <avr/io.h>
.extern n_red,n_blue,n_green
.extern precomputed

fast_out:
  lds r24,precomputed
  lds r25,n_red
  mul r24,r25
  out OCR0A,r1
  lds r25,n_green
  mul r24,r25
  out OCR0B,r1
  lds r25,n_blue
  sts OCR2A,r1
  ret
// put the global declaration to export function name

.global fast_out

Уже в таком виде должно собраться.
В данном примере precomputed - это Ваше С'
Но, скорее всего, Вам придется эту часть, с предварительными вычислениями тоже в асм внести.
Успехов!

В догонку.
Деление на 255 в данном случае можно заменить делением на 256 и учетом одного исключения:

Код

if (c !=255) a = (b*c)/256; else a=b;

Просьба не воспринимать это как сишный текст

[koluna]

В догонку.
Деление на 255 в данном случае можно заменить делением на 256 и учетом одного исключения:

Код

if (c !=255) a = (b*c)/256; else a=b;

Просьба не воспринимать это как сишный текст

И как паскалевский, и как ассемблерный... ясен перец

За быстрое деление на 255 - всем спасибо.
Работает. Быстро работает

Сообщение отредактировал n_bogoyavlensky - Dec 3 2008, 09:47

[=GM=]

Ну просто это получается эквивалентно C2/256. Просто малость замаскировано

Вы не правы, это НЕ эквивалентно C2/256, это примерно эквивалентно C2/257. Судите сами, C2/255 = C2/(65536/257)=С2*257/65536=(С2*257)>>16. А примерно эквивалентно потому, что вы делите на 65536/257=255.0039, а не точно на 255.

Что касается вашей формулы (С2*257) >> 16 =( (С2 <<8) + C2)>>16 = ((C2<<8)>>16) + (C2>>16) = C2>>8 = C2/256, то она неверна. Два слагаемых перекрываются на 8 бит, и меньшее слагаемое нельзя просто отбросить, поскольку при суммировании оно может дать перенос в старший байт, который и будет окончательным результатом.

Вот пример. Пусть С2=0x8899=34969, тогда C2*256=0x889900,
C2*257=C2*256+C2=0x889900+0x8899=0x892199
и, наконец, С=C2*257>>16=0x89=137. Простая проверка: С=34969/255=137.1

По вашей формуле С=С2>>8=0x88=136

Вывод такой. Если хотите поделить на 255, то лучше делить на 255.0039, чем на 256. Всяко точнее будет. Вообще такой подход хорош при делении на константу.

[koluna]

Вот ещё одна задача.
Как аналогичным образом целочисленно поделить одно 8-битное число на другое 8-битное число?
Более конкретно - деление на 10.

[singlskv]

Дык все точно так же,
умножте на 26(~256/10) или на 6554(~65536/10) ну и если нужно скоректируйте...

[Александр Куличо...]

Вот ещё одна задача.
Как аналогичным образом целочисленно поделить одно 8-битное число на другое 8-битное число?
Более конкретно - деление на 10.

Для диапазона A=[0..255): (unsigned char)(А+1)*51>>9

Для диапазона A=[0..255] ((unsigned char)(А*51) + 51)>>9

или на асме соответственно

Код

    ldi    temp,51
    inc    A    
    mul    A,temp
    lsr    R1

и
    ldi    temp,51
    mul    A,temp
    add    R0,temp
    adc    R1,zero
    lsr    R1

[koluna]

Для диапазона A=[0..255): (unsigned char)(А+1)*51>>9

Для диапазона A=[0..255] ((unsigned char)(А*51) + 51)>>9

Спасибо!
Кстати, откуда вы с такой лёгкостью извлекаете эти волшебные выражения?
Они где-то перечислены или их можно достаточно просто придумать самому? Каков принцип?

А для диапазона A=[0..65535]?

Дык все точно так же,
умножте на 26(~256/10) или на 6554(~65536/10) ну и если нужно скоректируйте...

Всмысле?
Что умножить и как скорректировать?

[singlskv]

Всмысле?
Что умножить и как скорректировать?

Именно так как в посте №21

51 ~= 256 * 2 / 10

+ 51 корректировка

[koluna]

Именно так как в посте №21

51 ~= 256 * 2 / 10

+ 51 корректировка

Всё равно пока не пойму каков принцип?

[ae_]

x/10 = x*(1/10) = x*(205/2048) = (x*205)>>11
x/10 = x*(1/10) = x*(52429/524288) = (x*52429)>>19

[xemul]

Всё равно пока не пойму каков принцип?

x/10 ~= x*51/512 = (x*51)>>9
или x/10 ~= x*26/256 = (x*26)>>8
или ...
подберите что-нибудь, устраивающее по точности.
Для корректного целочисленного округления все-таки д.б. ((x*51)+51/2)>>9 ~= ((x*51)+26)>>9

[SSerge]

Всё равно пока не пойму каков принцип?

Дык, a/b преобразуется в a*(N/b) / N, при подходящем выборе N (степень двойки) выражение N/b вычисляется ещё на этапе компиляции, а умножение и последующее деление на N (сдвигами или отбрасыванием младших байтов результата) выполняется быстрее чем просто деление на b, особенно при наличии аппаратного умножителя.

Добавлю ещё, что если b не константа то подобный метод тоже срабатывает - есть достаточно эффективные алгоритмы вычисления 1/b (или N/b). Всё из-за того, что аппаратный делитель выходит заметно сложнее умножителя, вот на нём и экономят, даже в суперкомпьютерах.

[koluna]

x/10 ~= x*51/512 = (x*51)>>9
или x/10 ~= x*26/256 = (x*26)>>8
или ...
подберите что-нибудь, устраивающее по точности.
Для корректного целочисленного округления все-таки д.б. ((x*51)+51/2)>>9 ~= ((x*51)+26)>>9

С делением теперь понятно. Спасибо
С округлением до ближайшего целого не понятно...

[xemul]

С делением теперь понятно. Спасибо
С округлением до ближайшего целого не понятно...

Спасибо, был неправ. Вместо
((x*51) + 51/2) >> 9 ~= ((x*51)+26)>>9
читать
((x*51) + 1<<8) >> 9 = (x*51)>>9 + 0.5

Правила округления до целого предполагают, что (н-р, применительно к десятичной системе счисления) если дробная часть = [0.0..0.4(9)], то число округляется "вниз" (дробная часть просто отбрасывается), если дробная часть = [0.5..0.9(9)], то число округляется "вверх" (дробная часть отбрасывается, к целой части добавляется 1).
Контроллер при целочисленных операциях может только отбросить дробную часть. Чтобы заставить его округлять "по-человечески", нужно перед целочисленными операциями с потерей точности (типа деление/сдвиг) добавить к операнду половину разряда, который станет младшим значащим разрядом после выполнения операции (== половину делителя).

Округляем до целого в десятичной системе:
половина значащего разряда = 0.5
trunc(31.49 + 0.5) = 31
trunc(31.5 + 0.5) = 32

Округляем до целого в двоичной системе:
пусть 0b10100101 (= 165 дес.) хочется сдвинуть вправо на 3 разряда
половина делителя = 1 << (3 - 1) = 0b100
0b10100101 >> 3 = 0b10100 (= 20 дес.)
(0b10100101 + 0b100) >> 3 = 0b10101 (= 21 дес.)
165/8 = 20.625 ~= 21

[singlskv]

Спасибо, был неправ. Вместо
((x*51) + 51/2) >> 9 ~= ((x*51)+26)>>9
читать
((x*51) + 1<<8) >> 9 = (x*51)>>9 + 0.5

на самом деле рассчет коррекции проще всего делать так:
- пример с домножением на 51
- пусть коррекция = A, те ((x * 51) + A) / 512 ~= x / 10
- тогда д.б.:
1.) 0 * 51 +A >= 0
2.) 9 * 51 +A < 1 * 512
3.) 10 * 51 + A >= 1 * 512
4.)250 * 51 + A >= 25 * 512
5.)255 * 51 + A < 26 * 512
- преобразуем
1.) A >= 0
2.) A < 53
3.) A >= 2
4.) A >= 50
5.) A < 307

-итого: 50<= A < 53

то есть нам подойдут 50, 51, 52

выбор чисел 0, 9, 10, 250, 255 надеюсь понятен

[xemul]

на самом деле рассчет коррекции проще всего делать так:
...

Вы абсолютно правы - я забыл про исходную постановку задачи и плавно на простое округление.

[Александр Куличо...]

-итого: 50<= A < 53
то есть нам подойдут 50, 51, 52

выбор чисел 0, 9, 10, 250, 255 надеюсь понятен

Действительно, простой расчет .
Но A = [50..52] (как и приведенная мной формула, где А=51)- это для случая деления с отбрасыванием дробной части, т.е для выражения X div 10.

Для деления с округлением, воспользовавшись Вашей методикой, получаем
1.) 0 * 51 +A >= 0
2.) 4 * 51 +A < 1 * 512
3.) 5 * 51 + A >= 1 * 512
4.)254 * 51 + A < 26 * 512
5.)255 * 51 + A >= 26 * 512
- преобразуем
1.) A >= 0
2.) A < 308
3.) A >= 257
4.) A <358
5.) A >= 307

Откуда A = 307.

P.S. Существуют ли алгоритмы для быстрого получения остатка от деления на 10, 100 (кроме варианта X - (X div 10)*10 )?

Вместо
((x*51) + 51/2) >> 9 ~= ((x*51)+26)>>9
читать
((x*51) + 1<<8) >> 9 = (x*51)>>9 + 0.5

Здесь A = 1<<8 = 512. При x=11 получаем в результате 2.

[ae_]

Так, что бы во всём диапазоне 0...255 / 10 выполнялось с округлением правильно:

Код

0....4 / 10 = 0
5...14 / 10 = 1
15...24 / 10 = 2
25...34 / 10 = 3
35...44 / 10 = 4
45...54 / 10 = 5
55...64 / 10 = 6
65...74 / 10 = 7
75...84 / 10 = 8
85...94 / 10 = 9
95..104 / 10 = 10
105..114 / 10 = 11
115..124 / 10 = 12
125..134 / 10 = 13
135..144 / 10 = 14
145..154 / 10 = 15
155..164 / 10 = 16
165..174 / 10 = 17
175..184 / 10 = 18
185..194 / 10 = 19
195..204 / 10 = 20
205..214 / 10 = 21
215..224 / 10 = 22
225..234 / 10 = 23
235..244 / 10 = 24
245..254 / 10 = 25
     255 / 10 = 26

У меня получилось только с множителем >= 205 по формуле (1+(x*205)>>10)>>1

Тоже самое на асме:

Код

     ldi R16, 205
     mul DATA, R16
     lsr R1
     lsr R1
     inc R1
     lsr R1
     mov DATA, R1

[koluna]

Кстати, а что за метод в 11 посте?
Там логика другая...

Кстати, для делимого, находящегося в диапазоне unsigned long деление на 255 как будет выглядеть?

[SSerge]

Кстати, а что за метод в 11 посте?
Там логика другая...

Там используют известное разложение в ряд 1/(1+x) ~ 1-x для x много меньше 1.
Получается
a/(256-1) = a/256 * 1/(1-1/256) ~ a/256 * (1 + 1/256) = (a + a/256)/256,
а 128 там прибавляют для правильного округления до ближайшего целого.