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