[ReAl 0]

А заинлайнить BitShift() и Butterfly() слабо? :)

Когда там запилят уже fixed point в gcc? В С11 уже ж вроде попало. Или в 4.8 уже есть?

Сюда

typedef int _Complex cmplx_t;

//cmplx_t a = 2 + 3I;
//cmplx_t b = -1 + 2I;

void foo(cmplx_t *px, cmplx_t *py, cmplx_t w, int len)
{
    while(len--) {
        cmplx_t temp = *px + *py * w;
        *py = *px - *py * w;
        *px = temp;
        ++px;
        ++py;
    }
}

arm-none-eabi-gcc -Os -S -mcpu=cortex-m3 -mthumb cmplx-int.c

foo:
push	{r4, r5, r6, r7, r8, lr}
ldr	r4, [sp, #24]
b	.L2
.L3:
ldmdb	r1, {r5, r8}
mul	r7, r2, r5
mls	r7, r3, r8, r7
mul	r8, r2, r8
mla	r5, r3, r5, r8
ldr	ip, [r0, #-8]
ldr	r6, [r0, #-4]
rsb	r8, r7, ip
str	r8, [r1, #-8]
add	r7, ip, r7
rsb	r8, r5, r6
adds	r5, r6, r5
str	r8, [r1, #-4]
str	r7, [r0, #-8]
str	r5, [r0, #-4]
.L2:
subs	r4, r4, #1
adds	r0, r0, #8
adds	r1, r1, #8
cmp	r4, #-1
bne	.L3
pop	{r4, r5, r6, r7, r8, pc}

ещё fixed point встроенный, так и вообще хорошо.

(правда это Cortex-M3, тут ещё mla/mls хорошо пошли)

 

 

 

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

#define FIXED_FACTOR (1<<12)

typedef int _Complex cmplx_t;

void foo(cmplx_t *px, cmplx_t *py, cmplx_t w, int len)
{
    while(len--) {
        cmplx_t temp = *py * w / FIXED_FACTOR;
        *px = *px + temp;
        *py = *px - temp;
        ++px;
        ++py;
    }
}

foo:
push	{r4, r5, r6, r7, r8, lr}
ldr	r4, [sp, #24]
b	.L2
.L5:
ldmdb	r1, {r5, r8}
mul	r6, r2, r5
mls	r6, r3, r8, r6
mul	r8, r2, r8
mla	r5, r3, r5, r8
cmp	r6, #0
itt	lt
addlt	r6, r6, #4064
addlt	r6, r6, #31
cmp	r5, #0
ldr	ip, [r0, #-8]
ldr	r7, [r0, #-4]
itt	lt
addlt	r5, r5, #4064
addlt	r5, r5, #31
add	r6, ip, r6, asr #12
add	r5, r7, r5, asr #12
str	r6, [r0, #-8]
str	r5, [r0, #-4]
str	ip, [r1, #-8]
str	r7, [r1, #-4]
.L2:
subs	r4, r4, #1
adds	r0, r0, #8
adds	r1, r1, #8
cmp	r4, #-1
bne	.L5
pop	{r4, r5, r6, r7, r8, pc}

 

(ой, ну по нормальному там не ++px; ++py; а раскрыв крыльев бабочки передавать надо)

[_Pasha 0]

Вроде ж давно есть fixed...

 

Да, пока не забыл - бит реверс по приснопамятному красивому трюку

Здесь

Т.е. вместо тяжеленького BitShift пишем хард-кодед вариант

b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;

 

Где там ошибка - сходу вроде нету. Мож, в представлении Q11 косяк? Не вникал, короче.

[hd44780 0]

По-моему, BitShift это мелочи :) , я сейчас пытаюсь основной цикл перекрутить ...

 

  // Main FFT loop
  for ( stc = 0; stc < NumOfStages; stc ++ )
  {
    NumOfButterflys = (1<<stc);
    NumOfBlocks = FFT_N>>(stc+1);

    for ( blc=0; blc < NumOfBlocks; blc ++ )
    {
     base = (1<<(stc+1))*blc;
     for ( bfc=0; bfc < NumOfButterflys; bfc ++ )
     {
      Butterfly ( X+base+bfc, X+base+bfc+NumOfButterflys, NumOfBlocks*bfc );
     } // for
    } // for
  } // for

 

Butterfly - самая тяжёлая вещь ...

 

http://www.embeddedsignals.com/ARM.htm - есть всё, но Cortex-M3 :(

[_Pasha 0]

Butterfly - самая тяжёлая вещь ...

Глянул - точно. Надо избавиться от complex.c - сразу инлайнами сделать операции над комплексными числами. Потом - сделать unroll для хотя бы внутреннего цикла. Оптимизация -О2 или -О3

[hd44780 0]

inline сделал, слегка видоизменил структуру вызовов кода - пошустрей пошёл, но недостаточно - сильно заметен рендеринг, хотя тот же рендер на осциллограмме летает.

 

_Pasha, с unroll непонятно - как я могу его сделать, ведь число оборотов циклов заранее неизвестно?

Возможно я не понял, что Вы имели в виду :( . Поясните пожалуйста.

[_Pasha 0]

_Pasha, с unroll непонятно - как я могу его сделать, ведь число оборотов циклов заранее неизвестно?

Возможно я не понял, что Вы имели в виду :( . Поясните пожалуйста.

Вы про unroll loops? Это - можно -O2 сделать - оно автоматом включится, там где выгоднее.

Про перестановку бит - я тут более артист разговорного жанра... надо еще посчитать, что лучше. Но может лучше - табличкой, для 256 отсчетов-то?

[hd44780 0]

Вы про unroll loops? Это - можно -O2 сделать - оно автоматом включится, там где выгоднее.

Спасибо, попробую.

 

может лучше - табличкой, для 256 отсчетов-то?

с этим вообще пока не разбирался почти. Гляну ещё.

 

Вот, сделал замеры времени одного прохода FFT через DBGU и COM-порт:

 

---> DoFFT start

Create complex data: 1 ms

Window function 0: 0 ms

FFT: 9 ms

Determine spektrum: 0 ms

--> DoFFT end

 

Window function 0 - прямоугольное окно, т.е. вообще там ничего нет.

FFT - скачет 8-9 ms.

Determine spektrum - всегда 0 - значит, меньше 1 ms.

 

Эти цифры вообще нормальные? Может там собака в другом месте зарыта ..

У меня сейчас отображает всё вместе - осциллограмму, FFT, ещё уровень рисует - просто максимум по каждому блоку данных АЦП. Еще и часиси рисует :).

Щас выкину всё, оставлю только FFT.

[hd44780 0]

_Pasha, спасибо.

 

Со скоростью вроде управился, работает довольно быстро.

Осталось, в общем-то главное - работает он как-то ненормально, рисует что-то странное..

Видимо, придётся перебирать разные реализации FFT :(

[GenaSPB 11]

Там очень проблемно с переполнением - я у себя переделал оригинальный проект (с потерей скорости - на 64 бит арифметику) для простоты.

 

[hd44780 0]

Спасибо.

Вечерком проверю вариант с заменой int на long.

Геннадий, а вы не копались, в каком месте алгоритма эти переполнения лезут? Главный цикл, последуэщий расчёт спектра, ещё что?

[hd44780 0]

Проверил. Особых тормозов от long int не заметил.

Полосок заметно больше стало, но всё равно WinAmp круче.

 

Сейчас другие реализации алгоритма буду пробовать ...

[esaulenka 5]

А какой должна быть разница от замены int на long в случае ARM-а ? :-)

[hd44780 0]

Медленнее. То же самое как на 8-битном проце складывать-вычитать 16-битные числа.

Ну и т.д. т.п.

[adnega 11]

Полосок заметно больше стало, но всё равно WinAmp круче.

Может, он в децибелах кажет?!

[DRUID3 0]

На Си нашёл, вставил в программу - тормозит оно. Конечно, гораздо лучше, чем на AVR, но всё равно не айс.

Надо сделать аудио-анализатор. Сделать-сделал, осциллограммы рисует великолепно, рендер быстрый для дисплея написал, а с FFT проблемы.

Вам нужен RealFFT и аппроксимация формулы для нахождения магнитуды (Р.Лайонс страница 475). По-поводу asm я где-то статью когда-то чью-то бросал сюда на форум. По поводу мегаоптимизаций - откажитесь от битреверса, примените RADIX4 и на асме вручную разверните внутренние циклы (не каскады бабочек). Вряд ли есть куда двигаться дальше в этом вопросе...

 

кстати раз уж пошли аппроксимации то набор IIR + блочное суммирование под частоту обновления экрана вполне претендует на спасение отца русской демократии. Ну а если уж совсем упростить - полосовые фильтры можно строить на основе фильтров скользящего среднего (можно ведь и в дифференцирующем включении их реализовать). Но результат будет... ммм... ну главное что он таки будет.