Простое FIFO

Столкнулся с интересной реализацией циклического буфера на Си, поначалу даже подумал, что этот код не работает, но разобравшись, решил использовать в своих проектах.
Весь код реализован в виде defin’ов и содержится в одном заголовочном файле fifo.h

#ifndef FIFO__H
#define FIFO__H
 
//размер должен быть степенью двойки: 4,8,16,32...128
#define FIFO( size )\
  struct {\
    unsigned char buf[size];\
    unsigned char tail;\
    unsigned char head;\
  } 
 
//количество элементов в очереди
#define FIFO_COUNT(fifo)     (fifo.head-fifo.tail)
 
//размер fifo
#define FIFO_SIZE(fifo)      ( sizeof(fifo.buf)/sizeof(fifo.buf[0]) )
 
//fifo заполнено?
#define FIFO_IS_FULL(fifo)   (FIFO_COUNT(fifo)==FIFO_SIZE(fifo))
 
//fifo пусто?
#define FIFO_IS_EMPTY(fifo)  (fifo.tail==fifo.head)
 
//количество свободного места в fifo
#define FIFO_SPACE(fifo)     (FIFO_SIZE(fifo)-FIFO_COUNT(fifo))
 
//поместить элемент в fifo
#define FIFO_PUSH(fifo, byte) \
  {\
    fifo.buf[fifo.head & (FIFO_SIZE(fifo)-1)]=byte;\
    fifo.head++;\
  }
 
//взять первый элемент из fifo
#define FIFO_FRONT(fifo) (fifo.buf[fifo.tail & (FIFO_SIZE(fifo)-1)])
 
//уменьшить количество элементов в очереди
#define FIFO_POP(fifo)   \
  {\
      fifo.tail++; \
  }
 
//очистить fifo
#define FIFO_FLUSH(fifo)   \
  {\
    fifo.tail=0;\
    fifo.head=0;\
  } 
 
#endif //FIFO__H

Update:
Что бы использовать этот код для fifo c размером 256 и более, надо для head и tail поменять тип c unsigned char на unsigned short.

Запись опубликована в рубрике Великий и могучий Си с метками , . Добавьте в закладки постоянную ссылку.

Один комментарий: Простое FIFO

  1. Бурановский Дедушка говорит:

    Непонятно только почему:
    //размер должен быть степенью двойки: 4,8,16,32…256

  2. Артём Двинин говорит:

    Для того, что бы было проще вычислять остаток от деления ( в avr, к примеру, нет аппаратного деления ).

    Переменные tail и head изменяются от 0 до 255, что бы из них получить корректный индекс массива используется операция: head & (FIFO_BUF_SIZE-1)Если FIFO_BUF_SIZE равен 16, это 2^4, то вычтя единицу, получим 15, а это выставленные в 1 биты с 0-го по третий.
    В результате получаем:

    head ( head & 15 )
    0 0
    1 1
    2 2
    ……
    15 15
    16 0
    17 1
    и т.д.

  3. валерий говорит:

    к сожалению на сайте нет ваших контактов, мне нужна консультация по програмированию atmega 1280 и возможно заказ программы,не могли бы вы связаться со мной или оставить свои координаты для связи

  4. Артём Двинин говорит:

    Мой email artem_dvinin@mail.ru.
    Отправил вам письмо. Пишите, буду рад помочь :)

  5. Настя говорит:

    здравствуйте! максимальный размер массива 256? мне нужен 512…

  6. Артём Двинин говорит:

    Да, сейчас максимальный размер массива 256.
    Что бы увеличить максимальный размер до 512, а точнее до 2^16 надо изменить тип полей структуры head и tail с unsigned char на unsigend short.

    #define FIFO( size )
      struct {
        unsigned char buf[size];
        unsigned short tail;
        unsigned short head;
      }
  7. Настя говорит:

    Большое спасибо! :)

  8. Артём Двинин говорит:

    Пожалуйста ;)

  9. Павел говорит:

    head и tail это unsigned char, соответственно если складывать в буфер значения не доставая их произойдет ситуация когда head переполнится в FIFO_PUSH и станет равным 0, а не 256. И FIFO_IS_FULL будет возвращать некорректный результат, потому что (0-0) не равно sizeof(fifo.buf), хотя на самом деле буфер полон.

  10. Артём Двинин говорит:

    Спасибо, что сказали! Получается что этот баг проявляется только при размере fifo = 256 байт. И что бы можно было использовать такой размер fifo надо поменять тип у head и tail с unsigned char на unsigned short.

  11. Павел говорит:

    нет, этот баг проявляется при любом размере fifo, потому что счетчики head и tail идут от 0 до 255 не зависимо от выбранного размера.

  12. Артём Двинин говорит:

    Спасибо, за комментарий, но тут я готов поспорить :)
    предположим что размер fifo = 16. tail = 240, и в fifo положили 16 байт

    head должен быть равен 256, но т.к. используется unsigned char то head переполняется, что приводит к тому head = 0

    есть вычесть head — tail получим -240, но т.к. обе переменные unsigned char, то получаем 16
    соответственно равенство (sizeof( fifo.buf ) == 16 ) верно, и FIFO_IS_FULL работает корректно

    P/S:
    в качестве проверки попробуйте
    printf( «%u», (unsigned char)-240 )

  13. Павел говорит:

    а если tail равно 0?

  14. Павел говорит:

    прошу прощения, упустил из виду, что в предложенном вами случае tail не станет нулем, раньше чем переполнится head

  15. Артём Двинин говорит:

    Спасибо, Павел. Без Вас бы так никто и не узнал про ошибку с размером fifo = 256

  16. Евгений говорит:

    Всем привет!
    Использовал этот код несколько раз, не было никаких проблем. До тех пор пока мне не понадобилось использовать переменные не char типа в буффере. Эта штука напрочь отказывалась работать нужным образом с типами больше char, а все из-за того, что sizeof нельзя применять для вычисления размера массива, нужно использовать sizeof(массив)/sizeof(массив[0]). Соответственно, все функции где есть sizeof надо переписать под данные код, либо добавить в структуру переменную, куда просто записать размер вашего фифо.

  17. Артём Двинин говорит:

    Спасибо за замечание!
    Поправил код, так лучше? ;)

  18. Евгений говорит:

    Да, теперь все правильно, вы даже более грамотно написали чем я, везде переписав на функцию FIFO_SIZE =)

  19. Артём Двинин говорит:

    ;)

  20. Евгений говорит:

    В этой строчке

    //размер fifo
    #define FIFO_SIZE(fifo) ( sizeof(fifo.buf)/sizeof(fifo.buf[0] )

    не хватает скобки закрывающейся -)

  21. Артём Двинин говорит:

    О, точно, скобку потерял :)
    Спасибо! Поправил…

  22. Вячеслав Мезенцев говорит:

    Есть предложение поменять местами параметры структуры: tail и head поместить в начало, а буфер — в конец. При отладке удобно видеть параметры в начале структуры, чем в конце буфера с изменяемыми размерами. Кроме того, что будет, если случайно превысить размер буфера и перезаписать его параметры?

  23. Вячеслав Мезенцев говорит:

    С перезаписью буфера — это я загнул, конечно. Там же маска накладывается. Просто под вечер уже устал баг один искать. У меня командный интерпретатор построен на использовании этой реализации fifo, причём, исходники построены так, что компилируется в двух компиляторах: iar и gnu. При работе в терминале, когда я нажимаю Backspace и веду его обработку в контроллере, то прошивка gnu отрабатывает как надо, а iar’овская глючит так, что я не смог поймать место глюка, нужно под отладчиком прямо по ассемблеру идти (я в Proteus отлаживал). После неудачных попыток я решил поменять местами поля в структуре и всё заработало как надо в обеих версиях.
    Вот я и подумал, что при работе в ISR, если специально там что-то не отслеживать, могут возникнуть такого рода глюки. Ошибка-то, конечно, где-то моя, но она очень не очевидная (когда-нить найду время посмотрю в чём было дело).

    А что касается tail и head, то в Proteus удобно порою, когда эти поля в начале находятся, сразу видишь: конец, начало, содержимое буфера.

  24. Роман говорит:

    да, действительно это классический фифо, такой например используется в буфере клавиатуры
    хочу заметить один момент, вместимость фифо в в определенных случаях в действительности меньше его размера на 1 байт и это может приводить к проблемам.
    например, если размер фифо 256 байта (при типе uchar) и если индекс начала == индекс конца — буфер пуст, но если в буфер поместить 256 байта (что не противоречит коду), то индексы опять будут равны…

  25. Роман говорит:

    хм, смотрю меня уже опередили :)
    вообще если
    ((индекс конца — индекс начала) &маска) — 1 = получим сколько байт свободно в фифо
    (индекс начала — индекс конца) &маска = получим сколько байт находится в фифо

  26. Артём Двинин говорит:

    Роман, спасибо за комментарий! :)

  27. Дмитрий говорит:

    Спасибо за код.

  28. София говорит:

    Спасибо за код!
    Обнаружила, что он крашится, если количество циклов полной перезаписи массива >= максимальное значение типа tail разделить на размер массива. Короче, если хвост превысит максимальное значение своего типа. Видимо, нужно изредка его сбрасывать сложным образом и надеяться, что прерывание в этот момент не возникнет :)

  29. Артём Двинин говорит:

    София, пожалуйста!
    Код не должен крашится если размер меньше чем максимальное значение типа tail. Можете привести код в котором это происходит?

  30. dl говорит:

    Что бы использовать этот код для fifo c размером 256 и более, надо для head и tail поменять тип c unsigned char на unsigned short.
    Можно попробовать что-то вроде этого:

    #if size < 256
        unsigned char tail;
        unsigned char head;
    #else
        unsigned short tail;
        unsigned short head;
    #endif
  31. Артём Двинин говорит:

    Да, можно и условной компиляцией задавать тип. Спасибо!

  32. Apparatchik говорит:

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

    Как быть если FIFO должен быть виден из нескольких файлов?

  33. Артём Двинин говорит:

    Доброго времени суток!

    если в одном СИшном файле Вы написали

    FIFO(64) fifo;

    то в другом надо

    extern FIFO(64) fifo;

    А ещё лучше — вынести эту строку в заголовочный файл и включать где надо через #include;

  34. Apparatchik говорит:

    Спасибо.

    В заголовочном файле такая запись не прокатывает, если только не объявить тип структуры и саму структуру, а вот чисто на дефайнах прокатило extern в нужном сишном файле (и как я сразу недопер, привык в заголовочном файле). Есче раз спасибо.

  35. Владимир говорит:

    Доброго времени суток.

    Для удобства, предлагаю ввести:

    #define FIFO_MASK(fifo) (FIFO_SIZE(fifo)-1)
  36. Владимир Чехов говорит:

    Доброго времени суток.

    Пытаюсь использовать Ваш код.
    Данные в фифо ложатся корректно, а вот вычитывается из фифо только первый элемент, подскажите, что не так делаю?

    Вот так использую:

    FIFO(128) usart2RX_fifo;

    вот так ложу в фифо:

      cChar = 0;
     
        for ( i = 0; cChar != 0x0A; i++ )
        {
            cChar = buf[i];
            FIFO_PUSH ( usart2RX_fifo, cChar );
        }

    вот так вычитываю:

        cChar = 0;
        for ( i = 0; cChar != 0x0A; i++ )
        {
            cChar = FIFO_FRONT(usart2RX_fifo);
            buf_fifo[i] = cChar;
            buf_fifo_idx++;
        }
  37. Артём Двинин говорит:

    после FIFO_FRONT
    вызовите FIFO_POP

    должно помочь

  38. Евгений говорит:

    Здравствуйте! Я начинающий программист и мне не очень понятен смысл данной операции при чтении первого значения из буфера , а также при записи в буфер:
    & (FIFO_SIZE(fifo)-1)
    Если удалить эту операцию, то код все равно работает как надо…вроде бы

  39. Евгений говорит:

    Блин сам спросил, сам разобрался , это сделано на случай переполнения буфера!

  40. Andrew Ternity говорит:

    Вот тут расписано, что делать, если размер нужен не кратный 2ке
    http://www.avrki.ru/articles/content/cicle_buffer/

    Выжимка:

    #define BUFFER_SIZE 16 // Это мы задали длину буфера
    #define BUFFER_MASK (BUFFER_SIZE-1) // Это мы задали маску обнуления
    ...
    unsigned char InBuffer(unsigned char bite)
    {
        IndexEnd++; // Сдвигаем конец на шаг вперед для записи данных
        if(IndexEnd == IndexStart) return 1; // Если буфер переполнен, конец
    догнал начало, то все бросаем и возвращаем 1. Тем самым предотвращаем запись
    данных на начало еще не прочитанных данных.
        IndexEnd &amp;= BUFFER_MASK; // Накладываем маску для обнуления индекса если он
    перевалил за 16.
        buffer[IndexEnd] = bite; // Если все хорошо то записываем байт в буфер.
        return 0; // Возвращаем ноль сигнализируя что все хорошо прошло.
    }

    Немного расскажу про маску обнуления. Выше я писал про два разных варианта задачи длинны массива. Вот как раз при условии длинны массива заданным степенью двойки мы накладываем маску. Объясняю на пальцах. Мы задали длину массива равную 16. Маску задали 16-1 что стало равно 15. Теперь давайте взглянем на число 15 в бинаре 0b00001111. Теперь представим что индекс конца буфера стал равен 15, а данные еще можно записывать. Индекс гордо увеличивается на единицу и становится равным 16, а это уже за пределами длинны нашего массива. Что делать? А давайте посмотрим на число 16 в бинаре 0b00010000. Ни на что не наводит? Вот наша масочка 0b00010000 & 0b00001111 = 0b00000000. Теперь понятно почему длину лучше выбирать кратно степени двойки. А если например длина равна 256, то тогда вообще ничего делать не надо, само обнулится. Но, а что делать при длине например 135. А ничего. пишем if(IndexEnd == 136) IndexEnd = 0; Все.

  41. KentAVR говорит:

    У меня элементы после Pop не уходят, допилил код так:

    //уменьшить количество элементов в очереди
    #define FIFO_POP(fifo)   
    {
    	fifo.tail++; 
    	if (fifo.tail==FIFO_SIZE(fifo)) fifo.tail=0; 
    }//доработанная

Добавить комментарий

Ваш e-mail не будет опубликован.

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>