mware/fifobuf.h

   1 /*!
   2  * \file
   3  * <!--
   4  * Copyright 2003, 2004 Develer S.r.l. (http://www.develer.com/)
   5  * Copyright 2001 Bernardo Innocenti <bernie@develer.com>
   6  * This file is part of DevLib - See devlib/README for information.
   7  * -->
   8  *
   9  * \version $Id$
  10  *
  11  * \author Bernardo Innocenti <bernie@develer.com>
  12  *
  13  * \brief General pourpose FIFO buffer implemented with a ring buffer
  14  *
  15  * \li \c begin points to the first buffer element;
  16  * \li \c end points to the last buffer element (unlike the STL convention);
  17  * \li \c head points to the element to be extracted next;
  18  * \li \c tail points to the location following the last insertion;
  19  * \li when any of the pointers advances beyond \c end, it is reset
  20  *     back to \c begin.
  21  *
  22  * \code
  23  *
  24  *  +-----------------------------------+
  25  *  |  empty  |   valid data   |  empty |
  26  *  +-----------------------------------+
  27  *  ^         ^                ^        ^
  28  *  begin    head             tail     end
  29  *
  30  * \endcode
  31  *
  32  * The buffer is EMPTY when \c head and \c tail point to the same location:
  33  *              \code head == tail \endcode
  34  *
  35  * The buffer is FULL when \c tail points to the location immediately
  36  * after \c head:
  37  *              \code tail == head - 1 \endcode
  38  *
  39  * The buffer is also FULL when \c tail points to the last buffer
  40  * location and head points to the first one:
  41  *              \code head == begin && tail == end \endcode
  42  */
  43
  44 /*#*
  45  *#* $Log$
  46  *#* Revision 1.16  2004/09/06 21:39:08  bernie
  47  *#* Simplify code using ATOMIC().
  48  *#*
  49  *#* Revision 1.15  2004/08/29 22:05:16  bernie
  50  *#* Rename BITS_PER_PTR to CPU_BITS_PER_PTR.
  51  *#*
  52  *#* Revision 1.14  2004/08/25 14:12:09  rasky
  53  *#* Aggiornato il comment block dei log RCS
  54  *#*
  55  *#* Revision 1.13  2004/08/24 13:16:11  bernie
  56  *#* Add type-size definitions for preprocessor.
  57  *#*
  58  *#* Revision 1.12  2004/08/02 20:20:29  aleph
  59  *#* Merge from project_ks
  60  *#*
  61  *#* Revision 1.11  2004/07/30 14:15:53  rasky
  62  *#* Nuovo supporto unificato per detect della CPU
  63  *#*
  64  *#* Revision 1.10  2004/07/29 22:57:09  bernie
  65  *#* Doxygen fix.
  66  *#*
  67  *#* Revision 1.9  2004/07/20 23:54:27  bernie
  68  *#* fifo_flush_locked(): New function;
  69  *#* Revamp documentation.
  70  *#*
  71  *#* Revision 1.8  2004/07/20 23:47:39  bernie
  72  *#* Finally remove redundant protos.
  73  *#*
  74  *#* Revision 1.7  2004/07/20 23:46:29  bernie
  75  *#* Finally remove redundant protos.
  76  *#*
  77  *#* Revision 1.6  2004/06/06 17:18:04  bernie
  78  *#* Remove redundant declaration of fifo_isempty_locked().
  79  *#*
  80  *#* Revision 1.5  2004/06/06 16:50:35  bernie
  81  *#* Import fixes for race conditions from project_ks.
  82  *#*
  83  *#* Revision 1.4  2004/06/06 16:11:17  bernie
  84  *#* Protect MetroWerks specific pragmas with #ifdef's
  85  *#*/
  86
  87 #ifndef MWARE_FIFO_H
  88 #define MWARE_FIFO_H
  89
  90 #include <cpu.h>
  91 #include <drv/kdebug.h>
  92
  93 typedef struct FIFOBuffer
  94 {
  95         unsigned char * volatile head;
  96         unsigned char * volatile tail;
  97         unsigned char *begin;
  98         unsigned char *end;
  99 } FIFOBuffer;
 100
 101
 102 #define ASSERT_VALID_FIFO(fifo) \
 103         ATOMIC( \
 104                 ASSERT((fifo)->head >= (fifo)->begin); \
 105                 ASSERT((fifo)->head <= (fifo)->end); \
 106                 ASSERT((fifo)->tail >= (fifo)->begin); \
 107                 ASSERT((fifo)->tail <= (fifo)->end); \
 108         )
 109
 110
 111 /*!
 112  * Check whether the fifo is empty
 113  *
 114  * \note Calling fifo_isempty() is safe while a concurrent
 115  *       execution context is calling fifo_push() or fifo_pop()
 116  *       only if the CPU can atomically update a pointer
 117  *       (which the AVR and other 8-bit processors can't do).
 118  *
 119  * \sa fifo_isempty_locked
 120  */
 121 INLINE bool fifo_isempty(const FIFOBuffer *fb)
 122 {
 123         //ASSERT_VALID_FIFO(fb);
 124         return fb->head == fb->tail;
 125 }
 126
 127
 128 /*!
 129  * Check whether the fifo is full
 130  *
 131  * \note Calling fifo_isfull() is safe while a concurrent
 132  *       execution context is calling fifo_pop() and the
 133  *       CPU can update a pointer atomically.
 134  *       It is NOT safe when the other context calls
 135  *       fifo_push().
 136  *       This limitation is not usually problematic in a
 137  *       consumer/producer scenario because the
 138  *       fifo_isfull() and fifo_push() are usually called
 139  *       in the producer context.
 140  */
 141 INLINE bool fifo_isfull(const FIFOBuffer *fb)
 142 {
 143         //ASSERT_VALID_FIFO(fb);
 144         return
 145                 ((fb->head == fb->begin) && (fb->tail == fb->end))
 146                 || (fb->tail == fb->head - 1);
 147 }
 148
 149
 150 /*!
 151  * Pop a character from the fifo buffer.
 152  *
 153  * \note Calling \c fifo_push() on a full buffer is undefined.
 154  *       The caller must make sure the buffer has at least
 155  *       one free slot before calling this function.
 156  *
 157  * \note It is safe to call fifo_pop() and fifo_push() from
 158  *       concurrent contexts, unless the CPU can't update
 159  *       a pointer atomically (which the AVR and other 8-bit
 160  *       processors can't do).
 161  *
 162  * \sa fifo_push_locked
 163  */
 164 INLINE void fifo_push(FIFOBuffer *fb, unsigned char c)
 165 {
 166 #ifdef __MWERKS__
 167 #pragma interrupt called
 168 #endif
 169         //ASSERT_VALID_FIFO(fb);
 170
 171         /* Write at tail position */
 172         *(fb->tail) = c;
 173
 174         if (UNLIKELY(fb->tail == fb->end))
 175                 /* wrap tail around */
 176                 fb->tail = fb->begin;
 177         else
 178                 /* Move tail forward */
 179                 fb->tail++;
 180 }
 181
 182
 183 /*!
 184  * Pop a character from the fifo buffer.
 185  *
 186  * \note Calling \c fifo_pop() on an empty buffer is undefined.
 187  *       The caller must make sure the buffer contains at least
 188  *       one character before calling this function.
 189  *
 190  * \note It is safe to call fifo_pop() and fifo_push() from
 191  *       concurrent contexts.
 192  */
 193 INLINE unsigned char fifo_pop(FIFOBuffer *fb)
 194 {
 195 #ifdef __MWERKS__
 196 #pragma interrupt called
 197 #endif
 198         //ASSERT_VALID_FIFO(fb);
 199
 200         if (UNLIKELY(fb->head == fb->end))
 201         {
 202                 /* wrap head around */
 203                 fb->head = fb->begin;
 204                 return *(fb->end);
 205         }
 206         else
 207                 /* move head forward */
 208                 return *(fb->head++);
 209 }
 210
 211
 212 /*!
 213  * Make the fifo empty, discarding all its current contents.
 214  */
 215 INLINE void fifo_flush(FIFOBuffer *fb)
 216 {
 217         //ASSERT_VALID_FIFO(fb);
 218         fb->head = fb->tail;
 219 }
 220
 221
 222 #if CPU_REG_BITS >= CPU_BITS_PER_PTR
 223
 224         /*
 225          * 16/32bit CPUs that can update a pointer with a single write
 226          * operation, no need to disable interrupts.
 227          */
 228         #define fifo_isempty_locked(fb) fifo_isempty((fb))
 229         #define fifo_push_locked(fb, c) fifo_push((fb), (c))
 230         #define fifo_pop_locked(fb)     fifo_pop((fb))
 231         #define fifo_flush_locked(fb)   fifo_flush((fb))
 232
 233 #else /* CPU_REG_BITS < CPU_BITS_PER_PTR */
 234
 235         /*!
 236          * Similar to fifo_isempty(), but with stronger guarantees for
 237          * concurrent access between user and interrupt code.
 238          *
 239          * \note This is actually only needed for 8-bit processors.
 240          *
 241          * \sa fifo_isempty()
 242          */
 243         INLINE bool fifo_isempty_locked(const FIFOBuffer *fb)
 244         {
 245                 bool result;
 246                 ATOMIC(result = fifo_isempty(fb));
 247                 return result;
 248         }
 249
 250
 251         /*!
 252          * Similar to fifo_push(), but with stronger guarantees for
 253          * concurrent access between user and interrupt code.
 254          *
 255          * \note This is actually only needed for 8-bit processors.
 256          *
 257          * \sa fifo_push()
 258          */
 259         INLINE void fifo_push_locked(FIFOBuffer *fb, unsigned char c)
 260         {
 261                 ATOMIC(fifo_push(fb, c));
 262         }
 263
 264         /* Probably not really needed, but hard to prove. */
 265         INLINE unsigned char fifo_pop_locked(FIFOBuffer *fb)
 266         {
 267                 unsigned char c;
 268                 ATOMIC(c = fifo_pop(fb));
 269                 return c;
 270         }
 271
 272         /*!
 273          * Similar to fifo_flush(), but with stronger guarantees for
 274          * concurrent access between user and interrupt code.
 275          *
 276          * \note This is actually only needed for 8-bit processors.
 277          *
 278          * \sa fifo_flush()
 279          */
 280         INLINE void fifo_flush_locked(FIFOBuffer *fb)
 281         {
 282                 ATOMIC(fifo_flush(fb));
 283         }
 284
 285 #endif /* CPU_REG_BITS < BITS_PER_PTR */
 286
 287
 288 /*!
 289  * Thread safe version of fifo_isfull()
 290  */
 291 INLINE bool fifo_isfull_locked(const FIFOBuffer *_fb)
 292 {
 293         bool result;
 294         ATOMIC(result = fifo_isfull(_fb));
 295         return result;
 296 }
 297
 298
 299 /*!
 300  * FIFO Initialization.
 301  */
 302 INLINE void fifo_init(FIFOBuffer *fb, unsigned char *buf, size_t size)
 303 {
 304         fb->head = fb->tail = fb->begin = buf;
 305         fb->end = buf + size - 1;
 306 }
 307
 308
 309 #if 0
 310
 311 /*
 312  * UNTESTED: if uncommented, to be moved in fifobuf.c
 313  */
 314 void fifo_pushblock(FIFOBuffer *fb, unsigned char *block, size_t len)
 315 {
 316         size_t freelen;
 317
 318         /* Se c'e' spazio da tail alla fine del buffer */
 319         if (fb->tail >= fb->head)
 320         {
 321                 freelen = fb->end - fb->tail + 1;
 322
 323                 /* C'e' abbastanza spazio per scrivere tutto il blocco? */
 324                 if (freelen < len)
 325                 {
 326                         /* Scrivi quello che entra fino alla fine del buffer */
 327                         memcpy(fb->tail, block, freelen);
 328                         block += freelen;
 329                         len -= freelen;
 330                         fb->tail = fb->begin;
 331                 }
 332                 else
 333                 {
 334                         /* Scrivi tutto il blocco */
 335                         memcpy(fb->tail, block, len);
 336                         fb->tail += len;
 337                         return;
 338                 }
 339         }
 340
 341         for(;;)
 342         {
 343                 while (!(freelen = fb->head - fb->tail - 1))
 344                         Delay(FIFO_POLLDELAY);
 345
 346                 /* C'e' abbastanza spazio per scrivere tutto il blocco? */
 347                 if (freelen < len)
 348                 {
 349                         /* Scrivi quello che entra fino alla fine del buffer */
 350                         memcpy(fb->tail, block, freelen);
 351                         block += freelen;
 352                         len -= freelen;
 353                         fb->tail += freelen;
 354                 }
 355                 else
 356                 {
 357                         /* Scrivi tutto il blocco */
 358                         memcpy(fb->tail, block, len);
 359                         fb->tail += len;
 360                         return;
 361                 }
 362         }
 363 }
 364 #endif
 365
 366 #endif /* MWARE_FIFO_H */
 367