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