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