Jump to content

    
Sign in to follow this  
Dubov

Закольцевать данные

Recommended Posts

Имеется буфер длины N

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

 

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

 

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

 

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

 

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

 

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

 

тогда подпрограмма должна "знать", что она оперирует с массивом | (PTR) (...) (N) (a) ( b ) |

Edited by Dubov

Share this post


Link to post
Share on other sites
Имеется буфер длины 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

Также довольно легко вместо данных, возвращать указатели на данные.

Share this post


Link to post
Share on other sites
Вместе с указателем на данные передавать указатель на начало и конец массива?

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

 

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

 

Как то так:

 

j = count;

 

for(i = 0; i <= N-1; i++)

{

array_dest = array_src[j];

j++;

if(j == N)

j = 0;

}

 

 

 

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

 

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

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

 

Функция 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:

Edited by Dubov

Share this post


Link to post
Share on other sites
В идеале мне нужна циклическая адресация, чтобы за концом массива шло начало в адресном пространстве.

 

ну дык расположите буфер к примеру по адресу 0x1000, размер буфера кратный 2^n и обращайтесь по маске

 

Share this post


Link to post
Share on other sites
ну дык расположите буфер к примеру по адресу 0x1000, размер буфера кратный 2^n и обращайтесь по маске

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

Edited by Dubov

Share this post


Link to post
Share on other sites
Функция 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; //возвращаем данные
}

Share this post


Link to post
Share on other sites

Можно сделать указатель типом BYTE. Если размер массива 256 байт, то после значения указателя 255 автоматически следующим будет 0.

Share this post


Link to post
Share on other sites
прошу прощения, можно по-подробнее об этом методе. А лучше ссылку на код (совсем наглость с моей стороны) :rolleyes: :rolleyes:

 

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, при этом оно пройдётся по массиву несколько раз.

Share this post


Link to post
Share on other sites
прошу прощения, можно по-подробнее об этом методе. А лучше ссылку на код (совсем наглость с моей стороны) :rolleyes: :rolleyes:

 

к примеру ваш буфер размещен по адресу #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. на скорую руку набросал.

Share this post


Link to post
Share on other sites
Только в этой функции, я думаю , не увеличение 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

и так далее.

Share this post


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

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

void foo(int *ptr, int count, int *start, int *end)
{
    while(count-- > 0)
    {
        if (ptr >= end)
        {
            ptr = start;
        }

        do_something_with(ptr);    
        ptr++;            
    }
}

 

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

Собственно других волшебных методов нет. Разве что использовать размер массива равный степени двойки. Тогда можно будет заменить условие на побитовую операцию и присвоение, но даже если это и даст выигрыш, то всего в пару тактов, что будет каплей в море.

 

Share this post


Link to post
Share on other sites
прошу прощения, можно по-подробнее об этом методе. А лучше ссылку на код (совсем наглость с моей стороны) :rolleyes: :rolleyes:

В коде scmrtos есть кольцевой буфер (файл usrlib.h), на писан на c++, легко адаптируется.

Share this post


Link to post
Share on other sites
Тогда Ваш буффер будет занимать диапазон адресов 0xFF1000 - 0x001000

Маска для этого диапазона адресов ADDR_MSK = 0xFF<<12

Принцип понял, но непонятен механизм.

Сначала адрес 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

тот же самый адрес, или я чего то не так понял ?

Share this post


Link to post
Share on other sites
тот же самый адрес, или я чего то не так понял ?

 

автар перепутал байт

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

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

 

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

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this