Имеется буфер длины N
имеется подпрограмма, принимающая на вход указатель на блок данных длины N.
Буфер заполняется циклически (по заполнении буфера, новый отсчёт поступает в начало буфера).
с каждым новым вызовом подпрограммы, получаемый указатель увеличивается на единицу.
Как закольцевать адресацию массива?
Например, может получится ситуация когда указатель находится в произвольном месте массива:
| (a) ( b ) (PTR) (...) (N) |
тогда подпрограмма должна "знать", что она оперирует с массивом | (PTR) (...) (N) (a) ( b ) |
Полная версия этой страницы: Закольцевать данные
Форум разработчиков электроники ELECTRONIX.ru > Сайт и форум > В помощь начинающему > Программирование
Вместе с указателем на данные передавать указатель на начало и конец массива?
Цитата(Dubov @ Jun 3 2014, 12:19) 
Имеется буфер длины N
имеется подпрограмма, принимающая на вход указатель на блок данных длины N.
Буфер заполняется циклически (по заполнении буфера, новый отсчёт поступает в начало буфера).
с каждым новым вызовом подпрограммы, получаемый указатель увеличивается на единицу.
Как закольцевать адресацию массива?
имеется подпрограмма, принимающая на вход указатель на блок данных длины N.
Буфер заполняется циклически (по заполнении буфера, новый отсчёт поступает в начало буфера).
с каждым новым вызовом подпрограммы, получаемый указатель увеличивается на единицу.
Как закольцевать адресацию массива?
Может быть Вам стоит поступить немного иначе - организовать 2 функции putArray(data) и getarray()
putArray(data) закидывает данные в буффер, контролируя при этом переход через границу буффера и смещая позицию head (позицию куда необходимо закидывать следующие данные)
Код
void putarray(short data)
{
buff[head] = data;
head++;
if(head >= BUFF_SIZE) head = 0; //переход через границу буффера
}
{
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; //возвращаем данные
}
{
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
Также довольно легко вместо данных, возвращать указатели на данные.
Цитата(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 если нет данных, или данные
Эти 2 процедуры позволяют организовать FIFO данных без проверки переполнения буффера.
Если Вам критично отслеживать переполнение, то всегда можно ввести переменную status, которой можно присваивать статусы empty/not_empty/full
Также довольно легко вместо данных, возвращать указатели на данные.
Код
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; //возвращаем данные
}
{
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 байт (по сути весь массив с началом в указателе) и если указатель пришёлся на конец буфера, то функция возьмёт данные где-то пределами массива.
В идеале мне нужна циклическая адресация, чтобы за концом массива шло начало в адресном пространстве.
Цитата(Dubov @ Jun 3 2014, 14:48)
В идеале мне нужна циклическая адресация, чтобы за концом массива шло начало в адресном пространстве.
ну дык расположите буфер к примеру по адресу 0x1000, размер буфера кратный 2^n и обращайтесь по маске
Цитата(megajohn @ Jun 3 2014, 14:52)
ну дык расположите буфер к примеру по адресу 0x1000, размер буфера кратный 2^n и обращайтесь по маске
прошу прощения, можно по-подробнее об этом методе. А лучше ссылку на код (совсем наглость с моей стороны)
Цитата(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; //возвращаем данные
}
{
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; //возвращаем данные
}
{
signed int res = -1;
if(head == 0) return res; //нет данных - возвращаем -1
res = buff[tail];
tail--;
return res; //возвращаем данные
}
Можно сделать указатель типом BYTE. Если размер массива 256 байт, то после значения указателя 255 автоматически следующим будет 0.
Цитата(Dubov @ Jun 3 2014, 17:57)
прошу прощения, можно по-подробнее об этом методе. А лучше ссылку на код (совсем наглость с моей стороны)
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++]);
}
}
while (num--){
while (i0 >= size) i0 -= size;
process(data[i0++]);
}
}
num может быть даже в несколько раз больше size, при этом оно пройдётся по массиву несколько раз.
Цитата(Dubov @ Jun 3 2014, 14:57)
прошу прощения, можно по-подробнее об этом методе. А лучше ссылку на код (совсем наглость с моей стороны)
к примеру ваш буфер размещен по адресу #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. на скорую руку набросал.
Цитата(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; //возвращаем данные
}
{
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);
}
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
и так далее.
Цитата(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++;
}
}
{
while(count-- > 0)
{
if (ptr >= end)
{
ptr = start;
}
do_something_with(ptr);
ptr++;
}
}
Цитата(Dubov @ Jun 3 2014, 14:48)
Такой подход самый тупой и, что называется, в лоб. Мне думается, что он будет самым затратным из возможных, и для реалтаймовых задач нерациональным.
Собственно других волшебных методов нет. Разве что использовать размер массива равный степени двойки. Тогда можно будет заменить условие на побитовую операцию и присвоение, но даже если это и даст выигрыш, то всего в пару тактов, что будет каплей в море.
Цитата(Dubov @ Jun 3 2014, 14:57)
прошу прощения, можно по-подробнее об этом методе. А лучше ссылку на код (совсем наглость с моей стороны)
В коде scmrtos есть кольцевой буфер (файл usrlib.h), на писан на c++, легко адаптируется.
Цитата(mempfis_ @ Jun 3 2014, 15:23)
Тогда Ваш буффер будет занимать диапазон адресов 0xFF1000 - 0x001000
Маска для этого диапазона адресов ADDR_MSK = 0xFF<<12
Маска для этого диапазона адресов 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
и так далее.
Читаем с этого адреса значение из ячейки 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
тот же самый адрес, или я чего то не так понял ?
Цитата(MaxiMuz @ Jun 5 2014, 16:25)
тот же самый адрес, или я чего то не так понял ?
автар перепутал байт
вместо "Тогда Ваш буффер будет занимать диапазон адресов 0xFF1000 - 0x001000"
читать "Тогда Ваш буффер будет занимать диапазон адресов 0x0010FF - 0x001000"
и далее, сам же запутался (или HumanEndian путает с HardwareEndian ) =)
а может просто код посмотреть ?
1. http://c.learncodethehardway.org/book/ex44.html
2. https://code.mythtv.org/doxygen/ringbuffer_8c_source.html
и еще примерно 5000000 примеров
1. http://c.learncodethehardway.org/book/ex44.html
2. https://code.mythtv.org/doxygen/ringbuffer_8c_source.html
и еще примерно 5000000 примеров
Цитата(megajohn @ Jun 5 2014, 15:34)
автар перепутал байт
вместо "Тогда Ваш буффер будет занимать диапазон адресов 0xFF1000 - 0x001000"
читать "Тогда Ваш буффер будет занимать диапазон адресов 0x0010FF - 0x001000"
и далее, сам же запутался (или HumanEndian путает с HardwareEndian ) =)
вместо "Тогда Ваш буффер будет занимать диапазон адресов 0xFF1000 - 0x001000"
читать "Тогда Ваш буффер будет занимать диапазон адресов 0x0010FF - 0x001000"
и далее, сам же запутался (или HumanEndian путает с HardwareEndian ) =)
Сознаюсь что ступил.
Диапазон адресов и правда будет 0x0010FF - 0x001000
В этом случае маску адресов не надо сдвигать на 12 бит.
Она должна быть 0x001000 | 0xFF т.е. равна максимальному адресу 0x0010FF
Всё остальное остаётся в силе - при наложении маски адрес автоматически закольцуется при превышении границы буффера.
топикстартеру
Может быть Вам стоит пересмотреть организацию буффера и сделать его по типу FIFO.
Тогда в этих извращениях не будет необходимости и подпрограмма считывания данных будет извлекать данные до опустошения буффера, а контролем перехода через границу буффера будет заниматься процедура извлечения байта/слова данных.
Цитата(mempfis_ @ Jun 5 2014, 17:44)
Тогда в этих извращениях не будет необходимости.
Да в них и так нет необходимости. Что все прицепились к этим маскам, выгоды никакой.
Цитата
Да в них и так нет необходимости. Что все прицепились к этим маскам, выгоды никакой.
Видать Вы не программировали микроконтроллеры.
Например, в обработчике прерывания необходимо выполнить работу как можно быстрее. Использование маски приводит к меньшему количеству кода и более быстрому выполнению.
Цитата(alexeyv @ Jun 9 2014, 08:24)
Видать Вы не программировали микроконтроллеры.
Далеко не всегда даже в микроконтроллерах на счету каждый такт или байт. Зачастую сопровождаемый код или некратный степени двойки размер перевешивают.Добавлено: знать такой прием, разумеется, полезно, но совать его везде "потому что микроконтроллер" абсолютно ни к чему.
Цитата
но совать его везде "потому что микроконтроллер" абсолютно ни к чему.
Я не сую везде, и размеры буфера в основном степени двойки.
Конечно зависит от задачи, но программист должен представлять в какие инструкции, хотя бы примерно, будет компилироваться его код и к чему это приведет.
Обработка по маске - это всегда одинаковое постоянное время обработки данного участка кода. Длительность обработки по условию меняется в зависимости от ветки по которой пройдет исполнение.
Как раз таки я прекрасно представляю, что будет в моем случае (ARM). В случае использования маски получиться одна инструкция AND, в случае использования условия мы получим CMP, IT и MOV, это если у нас Thumb2. Если же у нас ARM набор инструкций, то IT не будет. Выходит для распространенных МК на базе Cortex-M и ARM7 использование условия в худшем случае увеличит время исполнения на два такта, при этом время выполнения в обоих случаях будет постоянным. Так вот, какие бы оптимизации мы не пытались сделать, два такта - это НИЧТО. Они потонут в тактах, требуемых на вызов функции, на работу со стеком, на обращение к переменной в RAM. В конце-концов у нас тут не DSP, где пару тактов может и сделали бы погоду. Более простые МК на базе других архитектур могут сгенерировать на месте условия какой-нибудь условный переход. Да, в этом случае тактов будет больше, но опять же не настолько больше, чтобы на это обращать внимание.
Это называется переоптимизация. Я сам раньше грешил этим, но теперь отношусь к таким вещам попроще. В конце концов, если от увеличения времени исполнения участка кода всего на пару тактов программа перестает работать, или работает не правильно - то это явные архитектурные проблемы, означающие, что вы рассматриваете микробов через молоток. Нужны такты - есть всякие FPGA и DSP.
Это называется переоптимизация. Я сам раньше грешил этим, но теперь отношусь к таким вещам попроще. В конце концов, если от увеличения времени исполнения участка кода всего на пару тактов программа перестает работать, или работает не правильно - то это явные архитектурные проблемы, означающие, что вы рассматриваете микробов через молоток. Нужны такты - есть всякие FPGA и DSP.
Цитата
Так и обрабатывать. В цикле проверять не дошел ли текущий указатель до конца массива, если да, то сдвигаем его в начало массива
Недавно решал такую же проблему, только "заворот" указателя при использовании данных был недопустимым по потерям производительности.
В результате родился такой код с двойным размером буфера и дублированием данных - где всегда есть непрерывная область отсчётов.
Оптимизатор современных версий 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;
}
{
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;
}
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.