Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Закольцевать данные
Форум разработчиков электроники ELECTRONIX.ru > Сайт и форум > В помощь начинающему > Программирование
Dubov
Имеется буфер длины N
имеется подпрограмма, принимающая на вход указатель на блок данных длины N.

Буфер заполняется циклически (по заполнении буфера, новый отсчёт поступает в начало буфера).

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

Как закольцевать адресацию массива?

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

| (a) ( b ) (PTR) (...) (N) |

тогда подпрограмма должна "знать", что она оперирует с массивом | (PTR) (...) (N) (a) ( b ) |
menzoda
Вместе с указателем на данные передавать указатель на начало и конец массива?
mempfis_
Цитата(Dubov @ Jun 3 2014, 12:19) *
Имеется буфер длины N
имеется подпрограмма, принимающая на вход указатель на блок данных длины N.
Буфер заполняется циклически (по заполнении буфера, новый отсчёт поступает в начало буфера).
с каждым новым вызовом подпрограммы, получаемый указатель увеличивается на единицу.
Как закольцевать адресацию массива?


Может быть Вам стоит поступить немного иначе - организовать 2 функции putArray(data) и getarray()
putArray(data) закидывает данные в буффер, контролируя при этом переход через границу буффера и смещая позицию head (позицию куда необходимо закидывать следующие данные)
Код
void putarray(short data)
{
buff[head] = data;
head++;
if(head >= BUFF_SIZE) head = 0; //переход через границу буффера
}


Функция getArray() возвращает или-1 если нет данных, или данные
Код
signed int getArray(void)
{
signed int res = -1;
if(head == tail) return res; //нет данных - возвращаем -1
res = buff[tail];
tail++;
if(tail >= BUFF_SIZE) tail = 0;
return res; //возвращаем данные

}


Эти 2 процедуры позволяют организовать FIFO данных без проверки переполнения буффера.
Если Вам критично отслеживать переполнение, то всегда можно ввести переменную status, которой можно присваивать статусы empty/not_empty/full
Также довольно легко вместо данных, возвращать указатели на данные.
Dubov
Цитата(menzoda @ Jun 3 2014, 14:09) *
Вместе с указателем на данные передавать указатель на начало и конец массива?

допустим, функция кроме указателя на начало данных получила указатель на начало и конец массива. Как это обработать на Си, чтобы за концом массива, брались данные из начала?

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

Как то так:

j = count;

for(i = 0; i <= N-1; i++)
{
array_dest[i] = array_src[j];
j++;
if(j == N)
j = 0;
}



где count = это положение самого "свежего отсчёта" в массиве array_src. таким образом, мы получим в массиве array_dest всегда данные начиная с самого свежего элемента исходного массива.

Такой подход самый тупой и, что называется, в лоб.
мне думается, что он будет самым затратным из возможных, и для реалтаймовых задач нерациональным.

Цитата(mempfis_ @ Jun 3 2014, 14:12) *
Функция getArray() возвращает или-1 если нет данных, или данные
Код
signed int getArray(void)
{
signed int res = -1;
if(head == tail) return res; //нет данных - возвращаем -1
res = buff[tail];
tail++;
if(tail >= BUFF_SIZE) tail = 0;
return res; //возвращаем данные

}


Эти 2 процедуры позволяют организовать FIFO данных без проверки переполнения буффера.
Если Вам критично отслеживать переполнение, то всегда можно ввести переменную status, которой можно присваивать статусы empty/not_empty/full
Также довольно легко вместо данных, возвращать указатели на данные.


не понимаю, ну получил я указатель на данные в буфере. Функция обработки берёт по указателю N байт (по сути весь массив с началом в указателе) и если указатель пришёлся на конец буфера, то функция возьмёт данные где-то пределами массива.
В идеале мне нужна циклическая адресация, чтобы за концом массива шло начало в адресном пространстве.

rolleyes.gif
megajohn
Цитата(Dubov @ Jun 3 2014, 14:48) *
В идеале мне нужна циклическая адресация, чтобы за концом массива шло начало в адресном пространстве.


ну дык расположите буфер к примеру по адресу 0x1000, размер буфера кратный 2^n и обращайтесь по маске
Dubov
Цитата(megajohn @ Jun 3 2014, 14:52) *
ну дык расположите буфер к примеру по адресу 0x1000, размер буфера кратный 2^n и обращайтесь по маске

прошу прощения, можно по-подробнее об этом методе. А лучше ссылку на код (совсем наглость с моей стороны) rolleyes.gif rolleyes.gif
MaxiMuz
Цитата(mempfis_ @ Jun 3 2014, 13:12) *
Функция getArray() возвращает или-1 если нет данных, или данные
Код
signed int getArray(void)
{
signed int res = -1;
if(head == tail) return res; //нет данных - возвращаем -1
res = buff[tail];
tail++;
if(tail >= BUFF_SIZE) tail = 0;
return res; //возвращаем данные
}

Только в этой функции, я думаю , не увеличение tail а набоборот:
Код
signed int getArray(void)
{
signed int res = -1;
if(head == 0) return res; //нет данных - возвращаем -1
res = buff[tail];
tail--;
return res; //возвращаем данные
}
Voldemari4
Можно сделать указатель типом BYTE. Если размер массива 256 байт, то после значения указателя 255 автоматически следующим будет 0.
_pv
Цитата(Dubov @ Jun 3 2014, 17:57) *
прошу прощения, можно по-подробнее об этом методе. А лучше ссылку на код (совсем наглость с моей стороны) rolleyes.gif rolleyes.gif


data[i & (size-1)] = 0;
size дожен быть степенью двойки. при занулении старших разрядов автоматически получается закольцовывание массива.


но ничем это не лучше дополнительных проверок на выходы за границы массива.

Код
void func(double * data, int size, int i0, int num){
  while (num--){
    while (i0 >= size) i0 -= size;
    process(data[i0++]);
  }
}

num может быть даже в несколько раз больше size, при этом оно пройдётся по массиву несколько раз.
megajohn
Цитата(Dubov @ Jun 3 2014, 14:57) *
прошу прощения, можно по-подробнее об этом методе. А лучше ссылку на код (совсем наглость с моей стороны) rolleyes.gif rolleyes.gif


к примеру ваш буфер размещен по адресу #define BUFF_START 0x1000 и занимает #define BUFF_SIZE 512

void buff_add( u8* ptr )
{
*ptr++ = get_data();
ptr = (u8*) ( (int)ptr & ( BUFF_SIZE - 1 ) + BUFF_START ); // получится типо ptr = (u8*) ( (int)ptr & 0x1FF + BUFF_START );
}


p.s. на скорую руку набросал.
mempfis_
Цитата(MaxiMuz @ Jun 3 2014, 14:40) *
Только в этой функции, я думаю , не увеличение tail а набоборот:
Код
signed int getArray(void)
{
signed int res = -1;
if(head == 0) return res; //нет данных - возвращаем -1
res = buff[tail];
tail++;
return res; //возвращаем данные
}


Исходный код правильный - это кольцевой буффер FIFO.
По позици head ложим данные с инкрементом head.
Забираем данные по позиции tail с инкрементом tail.
При закидывании данных голова убегает от хвоста.
При извлечении - хвост догоняет голову.

Если Т.С. нужен кольцевой буффер с доступом по указателю, то megajohn уже подсказал решение.


Позволю себе также пояснить то, что предложил megajohn

Предположим у Вас есть буффер char-элементов buff расположенный по адресу 0x1000 и размер BUFF_SIZE = 256 байт
Тогда Ваш буффер будет занимать диапазон адресов 0xFF1000 - 0x001000
Маска для этого диапазона адресов ADDR_MSK = 0xFF<<12

Теперь мы хотим считать с любой позиции буффера через указатель 256 байт, но так, чтобы при достижении границы буффера адрес автоматически перешёл в начало
Код
unsigned char* pbuff = &buff[255];
for(unsigned int i=0; i<BUFF_SIZE; i++)
{
*((pbuff+i)&ADDR_MSK);
}


Сначала адрес pbuff+i = 0xff1000+0
Читаем с этого адреса значение из ячейки buff[255]
Далее инкремен i и адрес становится pbuff+i=0xff1000+1=0x1001000
Но мы накладываем маску адресов 0xff<<12 и получаем адрес 0x100010000&(0xff<<12) = 0x001000;
Т.е. новый адрес соответсвует ячейке buff[0];
при i == 1 адрес будет 0x1011000&(0xff<<12) = 0x001000
и так далее.
menzoda
Цитата(Dubov @ Jun 3 2014, 14:48) *
допустим, функция кроме указателя на начало данных получила указатель на начало и конец массива. Как это обработать на Си, чтобы за концом массива, брались данные из начала?

Так и обрабатывать. В цикле проверять не дошел ли текущий указатель до конца массива, если да, то сдвигаем его в начало массива.
Код
void foo(int *ptr, int count, int *start, int *end)
{
    while(count-- > 0)
    {
        if (ptr >= end)
        {
            ptr = start;
        }

        do_something_with(ptr);    
        ptr++;            
    }
}


Цитата(Dubov @ Jun 3 2014, 14:48) *
Такой подход самый тупой и, что называется, в лоб. Мне думается, что он будет самым затратным из возможных, и для реалтаймовых задач нерациональным.

Собственно других волшебных методов нет. Разве что использовать размер массива равный степени двойки. Тогда можно будет заменить условие на побитовую операцию и присвоение, но даже если это и даст выигрыш, то всего в пару тактов, что будет каплей в море.
mdmitry
Цитата(Dubov @ Jun 3 2014, 14:57) *
прошу прощения, можно по-подробнее об этом методе. А лучше ссылку на код (совсем наглость с моей стороны) rolleyes.gif rolleyes.gif

В коде scmrtos есть кольцевой буфер (файл usrlib.h), на писан на c++, легко адаптируется.
MaxiMuz
Цитата(mempfis_ @ Jun 3 2014, 15:23) *
Тогда Ваш буффер будет занимать диапазон адресов 0xFF1000 - 0x001000
Маска для этого диапазона адресов ADDR_MSK = 0xFF<<12

Принцип понял, но непонятен механизм.
Цитата(mempfis_ @ Jun 3 2014, 15:23) *
Сначала адрес pbuff+i = 0xff1000+0
Читаем с этого адреса значение из ячейки buff[255]
Далее инкремен i и адрес становится pbuff+i=0xff1000+1=0x1001000
Но мы накладываем маску адресов 0xff<<12 и получаем адрес 0x100010000&(0xff<<12) = 0x001000;
Т.е. новый адрес соответсвует ячейке buff[0];
при i == 1 адрес будет 0x1011000&(0xff<<12) = 0x001000
и так далее.

i=0 ,получаем адрес ((pbuff+i)&ADDR_MSK) = (0х00001000+0)&0x000FF000 = 0х00001000
i=1 : ((pbuff+i)&ADDR_MSK) = (0х00001000+1)&0x000FF000 = 0х00001000
тот же самый адрес, или я чего то не так понял ?
megajohn
Цитата(MaxiMuz @ Jun 5 2014, 16:25) *
тот же самый адрес, или я чего то не так понял ?


автар перепутал байт
вместо "Тогда Ваш буффер будет занимать диапазон адресов 0xFF1000 - 0x001000"
читать "Тогда Ваш буффер будет занимать диапазон адресов 0x0010FF - 0x001000"

и далее, сам же запутался (или HumanEndian путает с HardwareEndian ) =)
x893
а может просто код посмотреть ?
1. http://c.learncodethehardway.org/book/ex44.html
2. https://code.mythtv.org/doxygen/ringbuffer_8c_source.html
и еще примерно 5000000 примеров
mempfis_
Цитата(megajohn @ Jun 5 2014, 15:34) *
автар перепутал байт
вместо "Тогда Ваш буффер будет занимать диапазон адресов 0xFF1000 - 0x001000"
читать "Тогда Ваш буффер будет занимать диапазон адресов 0x0010FF - 0x001000"

и далее, сам же запутался (или HumanEndian путает с HardwareEndian ) =)


beer.gif
Сознаюсь что ступил.
Диапазон адресов и правда будет 0x0010FF - 0x001000
В этом случае маску адресов не надо сдвигать на 12 бит.
Она должна быть 0x001000 | 0xFF т.е. равна максимальному адресу 0x0010FF
Всё остальное остаётся в силе - при наложении маски адрес автоматически закольцуется при превышении границы буффера.

топикстартеру
Может быть Вам стоит пересмотреть организацию буффера и сделать его по типу FIFO.
Тогда в этих извращениях не будет необходимости и подпрограмма считывания данных будет извлекать данные до опустошения буффера, а контролем перехода через границу буффера будет заниматься процедура извлечения байта/слова данных.
menzoda
Цитата(mempfis_ @ Jun 5 2014, 17:44) *
Тогда в этих извращениях не будет необходимости.

Да в них и так нет необходимости. Что все прицепились к этим маскам, выгоды никакой.
alexeyv
Цитата
Да в них и так нет необходимости. Что все прицепились к этим маскам, выгоды никакой.

Видать Вы не программировали микроконтроллеры.
Например, в обработчике прерывания необходимо выполнить работу как можно быстрее. Использование маски приводит к меньшему количеству кода и более быстрому выполнению.
Сергей Борщ
Цитата(alexeyv @ Jun 9 2014, 08:24) *
Видать Вы не программировали микроконтроллеры.
Далеко не всегда даже в микроконтроллерах на счету каждый такт или байт. Зачастую сопровождаемый код или некратный степени двойки размер перевешивают.

Добавлено: знать такой прием, разумеется, полезно, но совать его везде "потому что микроконтроллер" абсолютно ни к чему.
alexeyv
Цитата
но совать его везде "потому что микроконтроллер" абсолютно ни к чему.

Я не сую везде, и размеры буфера в основном степени двойки.
Конечно зависит от задачи, но программист должен представлять в какие инструкции, хотя бы примерно, будет компилироваться его код и к чему это приведет.
Обработка по маске - это всегда одинаковое постоянное время обработки данного участка кода. Длительность обработки по условию меняется в зависимости от ветки по которой пройдет исполнение.
menzoda
Как раз таки я прекрасно представляю, что будет в моем случае (ARM). В случае использования маски получиться одна инструкция AND, в случае использования условия мы получим CMP, IT и MOV, это если у нас Thumb2. Если же у нас ARM набор инструкций, то IT не будет. Выходит для распространенных МК на базе Cortex-M и ARM7 использование условия в худшем случае увеличит время исполнения на два такта, при этом время выполнения в обоих случаях будет постоянным. Так вот, какие бы оптимизации мы не пытались сделать, два такта - это НИЧТО. Они потонут в тактах, требуемых на вызов функции, на работу со стеком, на обращение к переменной в RAM. В конце-концов у нас тут не DSP, где пару тактов может и сделали бы погоду. Более простые МК на базе других архитектур могут сгенерировать на месте условия какой-нибудь условный переход. Да, в этом случае тактов будет больше, но опять же не настолько больше, чтобы на это обращать внимание.

Это называется переоптимизация. Я сам раньше грешил этим, но теперь отношусь к таким вещам попроще. В конце концов, если от увеличения времени исполнения участка кода всего на пару тактов программа перестает работать, или работает не правильно - то это явные архитектурные проблемы, означающие, что вы рассматриваете микробов через молоток. Нужны такты - есть всякие FPGA и DSP.

Genadi Zawidowski
Цитата
Так и обрабатывать. В цикле проверять не дошел ли текущий указатель до конца массива, если да, то сдвигаем его в начало массива

Недавно решал такую же проблему, только "заворот" указателя при использовании данных был недопустимым по потерям производительности.
В результате родился такой код с двойным размером буфера и дублированием данных - где всегда есть непрерывная область отсчётов.
Оптимизатор современных версий GCC очень качественно разворачивает такие конструкции.
Код
static float32_t filter_fir_rx_AUDIO(float32_t NewSample, int_fast8_t reset)
{
    enum { Ntap = Ntap_rx_AUDIO, NtapHalf = Ntap / 2 };
    float32_t v = 0.0f;            //output sample
    // буфер с сохраненными значениями сэмплов
    static float32_t x [Ntap * 2] = { 0.0f, }; // заставить расположить буфер в CCM
    static uint_fast16_t fir_stage = 0;

    if (reset != 0)
    {
        fir_stage = 0;
        memset(x, 0, sizeof x);
        return NewSample;
    }
    //shift the old samples
    fir_stage = (fir_stage == 0) ? (Ntap - 1) : (fir_stage - 1);
    //Calculate the new output
    x [fir_stage] = NewSample;
    x [fir_stage + Ntap] = NewSample;

    uint_fast16_t bh = fir_stage;            // Начало обрабатываемой части буфера
    uint_fast16_t bt = fir_stage + Ntap;    // Позиция за концом обрабатываемого буфера
    uint_fast16_t n = 0;
    while (n < NtapHalf)
    {    
        v += FIRCoef_rx_AUDIO [n ++] * (x [bh ++] + x [-- bt]);
    }
    // Выборка в середине буфера
    v += FIRCoef_rx_AUDIO [n] * x [bh];
    // Обеспечиваем масштабирование к ранее расчитанному усилению фильтра (1.0)
    return v * FIRScale_rx_AUDIO;
}
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.