bertos/struct/fifobuf.h

   1 /**
   2  * \file
   3  * <!--
   4  * This file is part of BeRTOS.
   5  *
   6  * Bertos is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  * As a special exception, you may use this file as part of a free software
  21  * library without restriction.  Specifically, if other files instantiate
  22  * templates or use macros or inline functions from this file, or you compile
  23  * this file and link it with other files to produce an executable, this
  24  * file does not by itself cause the resulting executable to be covered by
  25  * the GNU General Public License.  This exception does not however
  26  * invalidate any other reasons why the executable file might be covered by
  27  * the GNU General Public License.
  28  *
  29  * Copyright 2003, 2004 Develer S.r.l. (http://www.develer.com/)
  30  * Copyright 2001, 2008 Bernie Innocenti <bernie@codewiz.org>
  31  * -->
  32  *
  33  * \defgroup fifobuf FIFO buffer
  34  * \ingroup struct
  35  * \{
  36  *
  37  * \brief General pourpose FIFO buffer implemented with a ring buffer
  38  *
  39  * \li \c begin points to the first buffer element;
  40  * \li \c end points to the last buffer element (unlike the STL convention);
  41  * \li \c head points to the element to be extracted next;
  42  * \li \c tail points to the location following the last insertion;
  43  * \li when any of the pointers advances beyond \c end, it is reset
  44  *     back to \c begin.
  45  *
  46  * \code
  47  *
  48  *  +-----------------------------------+
  49  *  |  empty  |   valid data   |  empty |
  50  *  +-----------------------------------+
  51  *  ^         ^                ^        ^
  52  *  begin    head             tail     end
  53  *
  54  * \endcode
  55  *
  56  * The buffer is EMPTY when \c head and \c tail point to the same location:
  57  *              \code head == tail \endcode
  58  *
  59  * The buffer is FULL when \c tail points to the location immediately
  60  * after \c head:
  61  *              \code tail == head - 1 \endcode
  62  *
  63  * The buffer is also FULL when \c tail points to the last buffer
  64  * location and head points to the first one:
  65  *              \code head == begin && tail == end \endcode
  66  *
  67  * \author Bernie Innocenti <bernie@codewiz.org>
  68  */
  69
  70 #ifndef STRUCT_FIFO_H
  71 #define STRUCT_FIFO_H
  72
  73 #include <cpu/types.h>
  74 #include <cpu/irq.h>
  75 #include <cfg/debug.h>
  76
  77 typedef struct FIFOBuffer
  78 {
  79         unsigned char * volatile head;
  80         unsigned char * volatile tail;
  81         unsigned char *begin;
  82         unsigned char *end;
  83 } FIFOBuffer;
  84
  85
  86 #define ASSERT_VALID_FIFO(fifo) \
  87         ATOMIC( \
  88                 ASSERT((fifo)->head >= (fifo)->begin); \
  89                 ASSERT((fifo)->head <= (fifo)->end); \
  90                 ASSERT((fifo)->tail >= (fifo)->begin); \
  91                 ASSERT((fifo)->tail <= (fifo)->end); \
  92         )
  93
  94
  95 /**
  96  * Declare a static fifo buffer
  97  */
  98 #define DECLARE_FIFO(_name, _ptr, _size)                        \
  99         FIFOBuffer _name =                                      \
 100         {                                                       \
 101                 .head = (_ptr),                                 \
 102                 .tail = (_ptr),                                 \
 103                 .begin = (_ptr),                                \
 104                 .end = (_ptr) + (_size) - 1,                    \
 105         };                                                      \
 106         STATIC_ASSERT((_size) > 1)
 107
 108 /**
 109  * Check whether the fifo is empty
 110  *
 111  * \note Calling fifo_isempty() is safe while a concurrent
 112  *       execution context is calling fifo_push() or fifo_pop()
 113  *       only if the CPU can atomically update a pointer
 114  *       (which the AVR and other 8-bit processors can't do).
 115  *
 116  * \sa fifo_isempty_locked
 117  */
 118 INLINE bool fifo_isempty(const FIFOBuffer *fb)
 119 {
 120         //ASSERT_VALID_FIFO(fb);
 121         return fb->head == fb->tail;
 122 }
 123
 124
 125 /**
 126  * Check whether the fifo is full
 127  *
 128  * \note Calling fifo_isfull() is safe while a concurrent
 129  *       execution context is calling fifo_pop() and the
 130  *       CPU can update a pointer atomically.
 131  *       It is NOT safe when the other context calls
 132  *       fifo_push().
 133  *       This limitation is not usually problematic in a
 134  *       consumer/producer scenario because the
 135  *       fifo_isfull() and fifo_push() are usually called
 136  *       in the producer context.
 137  */
 138 INLINE bool fifo_isfull(const FIFOBuffer *fb)
 139 {
 140         //ASSERT_VALID_FIFO(fb);
 141         return
 142                 ((fb->head == fb->begin) && (fb->tail == fb->end))
 143                 || (fb->tail == fb->head - 1);
 144 }
 145
 146
 147 /**
 148  * Push a character on the fifo buffer.
 149  *
 150  * \note Calling \c fifo_push() on a full buffer is undefined.
 151  *       The caller must make sure the buffer has at least
 152  *       one free slot before calling this function.
 153  *
 154  * \note It is safe to call fifo_pop() and fifo_push() from
 155  *       concurrent contexts, unless the CPU can't update
 156  *       a pointer atomically (which the AVR and other 8-bit
 157  *       processors can't do).
 158  *
 159  * \sa fifo_push_locked
 160  */
 161 INLINE void fifo_push(FIFOBuffer *fb, unsigned char c)
 162 {
 163 #ifdef __MWERKS__
 164 #pragma interrupt called
 165 #endif
 166         //ASSERT_VALID_FIFO(fb);
 167
 168         /* Write at tail position */
 169         *(fb->tail) = c;
 170
 171         if (UNLIKELY(fb->tail == fb->end))
 172                 /* wrap tail around */
 173                 fb->tail = fb->begin;
 174         else
 175                 /* Move tail forward */
 176                 fb->tail++;
 177 }
 178
 179
 180 /**
 181  * Pop a character from the fifo buffer.
 182  *
 183  * \note Calling \c fifo_pop() on an empty buffer is undefined.
 184  *       The caller must make sure the buffer contains at least
 185  *       one character before calling this function.
 186  *
 187  * \note It is safe to call fifo_pop() and fifo_push() from
 188  *       concurrent contexts.
 189  */
 190 INLINE unsigned char fifo_pop(FIFOBuffer *fb)
 191 {
 192 #ifdef __MWERKS__
 193 #pragma interrupt called
 194 #endif
 195         //ASSERT_VALID_FIFO(fb);
 196
 197         if (UNLIKELY(fb->head == fb->end))
 198         {
 199                 /* wrap head around */
 200                 fb->head = fb->begin;
 201                 return *(fb->end);
 202         }
 203         else
 204                 /* move head forward */
 205                 return *(fb->head++);
 206 }
 207
 208
 209 /**
 210  * Make the fifo empty, discarding all its current contents.
 211  */
 212 INLINE void fifo_flush(FIFOBuffer *fb)
 213 {
 214         //ASSERT_VALID_FIFO(fb);
 215         fb->head = fb->tail;
 216 }
 217
 218
 219 #if CPU_REG_BITS >= CPU_BITS_PER_PTR
 220
 221         /*
 222          * 16/32bit CPUs that can update a pointer with a single write
 223          * operation, no need to disable interrupts.
 224          */
 225         #define fifo_isempty_locked(fb) fifo_isempty((fb))
 226         #define fifo_push_locked(fb, c) fifo_push((fb), (c))
 227         #define fifo_pop_locked(fb)     fifo_pop((fb))
 228         #define fifo_flush_locked(fb)   fifo_flush((fb))
 229
 230 #else /* CPU_REG_BITS < CPU_BITS_PER_PTR */
 231
 232         /**
 233          * Similar to fifo_isempty(), but with stronger guarantees for
 234          * concurrent access between user and interrupt code.
 235          *
 236          * \note This is actually only needed for 8-bit processors.
 237          *
 238          * \sa fifo_isempty()
 239          */
 240         INLINE bool fifo_isempty_locked(const FIFOBuffer *fb)
 241         {
 242                 bool result;
 243                 ATOMIC(result = fifo_isempty(fb));
 244                 return result;
 245         }
 246
 247
 248         /**
 249          * Similar to fifo_push(), but with stronger guarantees for
 250          * concurrent access between user and interrupt code.
 251          *
 252          * \note This is actually only needed for 8-bit processors.
 253          *
 254          * \sa fifo_push()
 255          */
 256         INLINE void fifo_push_locked(FIFOBuffer *fb, unsigned char c)
 257         {
 258                 ATOMIC(fifo_push(fb, c));
 259         }
 260
 261         /* Probably not really needed, but hard to prove. */
 262         INLINE unsigned char fifo_pop_locked(FIFOBuffer *fb)
 263         {
 264                 unsigned char c;
 265                 ATOMIC(c = fifo_pop(fb));
 266                 return c;
 267         }
 268
 269         /**
 270          * Similar to fifo_flush(), but with stronger guarantees for
 271          * concurrent access between user and interrupt code.
 272          *
 273          * \note This is actually only needed for 8-bit processors.
 274          *
 275          * \sa fifo_flush()
 276          */
 277         INLINE void fifo_flush_locked(FIFOBuffer *fb)
 278         {
 279                 ATOMIC(fifo_flush(fb));
 280         }
 281
 282 #endif /* CPU_REG_BITS < BITS_PER_PTR */
 283
 284
 285 /**
 286  * Thread safe version of fifo_isfull()
 287  */
 288 INLINE bool fifo_isfull_locked(const FIFOBuffer *_fb)
 289 {
 290         bool result;
 291         ATOMIC(result = fifo_isfull(_fb));
 292         return result;
 293 }
 294
 295
 296 /**
 297  * FIFO Initialization.
 298  */
 299 INLINE void fifo_init(FIFOBuffer *fb, unsigned char *buf, size_t size)
 300 {
 301         /* FIFO buffers have a known bug with 1-byte buffers. */
 302         ASSERT(size > 1);
 303
 304         fb->head = fb->tail = fb->begin = buf;
 305         fb->end = buf + size - 1;
 306 }
 307
 308 /**
 309  * \return Lenght of the FIFOBuffer \a fb.
 310  */
 311 INLINE size_t fifo_len(FIFOBuffer *fb)
 312 {
 313         return fb->end - fb->begin;
 314 }
 315
 316
 317 #if 0
 318
 319 /*
 320  * UNTESTED: if uncommented, to be moved in fifobuf.c
 321  */
 322 void fifo_pushblock(FIFOBuffer *fb, unsigned char *block, size_t len)
 323 {
 324         size_t freelen;
 325
 326         /* Se c'e' spazio da tail alla fine del buffer */
 327         if (fb->tail >= fb->head)
 328         {
 329                 freelen = fb->end - fb->tail + 1;
 330
 331                 /* C'e' abbastanza spazio per scrivere tutto il blocco? */
 332                 if (freelen < len)
 333                 {
 334                         /* Scrivi quello che entra fino alla fine del buffer */
 335                         memcpy(fb->tail, block, freelen);
 336                         block += freelen;
 337                         len -= freelen;
 338                         fb->tail = fb->begin;
 339                 }
 340                 else
 341                 {
 342                         /* Scrivi tutto il blocco */
 343                         memcpy(fb->tail, block, len);
 344                         fb->tail += len;
 345                         return;
 346                 }
 347         }
 348
 349         for(;;)
 350         {
 351                 while (!(freelen = fb->head - fb->tail - 1))
 352                         Delay(FIFO_POLLDELAY);
 353
 354                 /* C'e' abbastanza spazio per scrivere tutto il blocco? */
 355                 if (freelen < len)
 356                 {
 357                         /* Scrivi quello che entra fino alla fine del buffer */
 358                         memcpy(fb->tail, block, freelen);
 359                         block += freelen;
 360                         len -= freelen;
 361                         fb->tail += freelen;
 362                 }
 363                 else
 364                 {
 365                         /* Scrivi tutto il blocco */
 366                         memcpy(fb->tail, block, len);
 367                         fb->tail += len;
 368                         return;
 369                 }
 370         }
 371 }
 372 #endif
 373
 374 /** \} */ /* defgroup fifobuf */
 375
 376 #endif /* STRUCT_FIFO_H */