libavutil/fifo.c

   1 /*
   2  * a very simple circular buffer FIFO implementation
   3  * Copyright (c) 2000, 2001, 2002 Fabrice Bellard
   4  * Copyright (c) 2006 Roman Shaposhnik
   5  *
   6  * This file is part of FFmpeg.
   7  *
   8  * FFmpeg is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * FFmpeg is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with FFmpeg; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  21  */
  22
  23 #include <stdint.h>
  24 #include <string.h>
  25
  26 #include "avassert.h"
  27 #include "error.h"
  28 #include "fifo.h"
  29 #include "macros.h"
  30 #include "mem.h"
  31
  32 // by default the FIFO can be auto-grown to 1MB
  33 #define AUTO_GROW_DEFAULT_BYTES (1024 * 1024)
  34
  35 struct AVFifo {
  36     uint8_t *buffer;
  37
  38     size_t elem_size, nb_elems;
  39     size_t offset_r, offset_w;
  40     // distinguishes the ambiguous situation offset_r == offset_w
  41     int    is_empty;
  42
  43     unsigned int flags;
  44     size_t       auto_grow_limit;
  45 };
  46
  47 AVFifo *av_fifo_alloc2(size_t nb_elems, size_t elem_size,
  48                        unsigned int flags)
  49 {
  50     AVFifo *f;
  51     void *buffer = NULL;
  52
  53     if (!elem_size)
  54         return NULL;
  55
  56     if (nb_elems) {
  57         buffer = av_realloc_array(NULL, nb_elems, elem_size);
  58         if (!buffer)
  59             return NULL;
  60     }
  61     f = av_mallocz(sizeof(*f));
  62     if (!f) {
  63         av_free(buffer);
  64         return NULL;
  65     }
  66     f->buffer    = buffer;
  67     f->nb_elems  = nb_elems;
  68     f->elem_size = elem_size;
  69     f->is_empty  = 1;
  70
  71     f->flags           = flags;
  72     f->auto_grow_limit = FFMAX(AUTO_GROW_DEFAULT_BYTES / elem_size, 1);
  73
  74     return f;
  75 }
  76
  77 void av_fifo_auto_grow_limit(AVFifo *f, size_t max_elems)
  78 {
  79     f->auto_grow_limit = max_elems;
  80 }
  81
  82 size_t av_fifo_elem_size(const AVFifo *f)
  83 {
  84     return f->elem_size;
  85 }
  86
  87 size_t av_fifo_can_read(const AVFifo *f)
  88 {
  89     if (f->offset_w <= f->offset_r && !f->is_empty)
  90         return f->nb_elems - f->offset_r + f->offset_w;
  91     return f->offset_w - f->offset_r;
  92 }
  93
  94 size_t av_fifo_can_write(const AVFifo *f)
  95 {
  96     return f->nb_elems - av_fifo_can_read(f);
  97 }
  98
  99 int av_fifo_grow2(AVFifo *f, size_t inc)
 100 {
 101     uint8_t *tmp;
 102
 103     if (inc > SIZE_MAX - f->nb_elems)
 104         return AVERROR(EINVAL);
 105
 106     tmp = av_realloc_array(f->buffer, f->nb_elems + inc, f->elem_size);
 107     if (!tmp)
 108         return AVERROR(ENOMEM);
 109     f->buffer = tmp;
 110
 111     // move the data from the beginning of the ring buffer
 112     // to the newly allocated space
 113     if (f->offset_w <= f->offset_r && !f->is_empty) {
 114         const size_t copy = FFMIN(inc, f->offset_w);
 115         memcpy(tmp + f->nb_elems * f->elem_size, tmp, copy * f->elem_size);
 116         if (copy < f->offset_w) {
 117             memmove(tmp, tmp + copy * f->elem_size,
 118                     (f->offset_w - copy) * f->elem_size);
 119             f->offset_w -= copy;
 120         } else
 121             f->offset_w = copy == inc ? 0 : f->nb_elems + copy;
 122     }
 123
 124     f->nb_elems += inc;
 125
 126     return 0;
 127 }
 128
 129 static int fifo_check_space(AVFifo *f, size_t to_write)
 130 {
 131     const size_t can_write = av_fifo_can_write(f);
 132     const size_t need_grow = to_write > can_write ? to_write - can_write : 0;
 133     size_t can_grow;
 134
 135     if (!need_grow)
 136         return 0;
 137
 138     can_grow = f->auto_grow_limit > f->nb_elems ?
 139                f->auto_grow_limit - f->nb_elems : 0;
 140     if ((f->flags & AV_FIFO_FLAG_AUTO_GROW) && need_grow <= can_grow) {
 141         // allocate a bit more than necessary, if we can
 142         const size_t inc = (need_grow < can_grow / 2 ) ? need_grow * 2 : can_grow;
 143         return av_fifo_grow2(f, inc);
 144     }
 145
 146     return AVERROR(ENOSPC);
 147 }
 148
 149 static int fifo_write_common(AVFifo *f, const uint8_t *buf, size_t *nb_elems,
 150                              AVFifoCB read_cb, void *opaque)
 151 {
 152     size_t to_write = *nb_elems;
 153     size_t offset_w;
 154     int         ret = 0;
 155
 156     ret = fifo_check_space(f, to_write);
 157     if (ret < 0)
 158         return ret;
 159
 160     offset_w = f->offset_w;
 161
 162     while (to_write > 0) {
 163         size_t    len = FFMIN(f->nb_elems - offset_w, to_write);
 164         uint8_t *wptr = f->buffer + offset_w * f->elem_size;
 165
 166         if (read_cb) {
 167             ret = read_cb(opaque, wptr, &len);
 168             if (ret < 0 || len == 0)
 169                 break;
 170         } else {
 171             memcpy(wptr, buf, len * f->elem_size);
 172             buf += len * f->elem_size;
 173         }
 174         offset_w += len;
 175         if (offset_w >= f->nb_elems)
 176             offset_w = 0;
 177         to_write -= len;
 178     }
 179     f->offset_w = offset_w;
 180
 181     if (*nb_elems != to_write)
 182         f->is_empty = 0;
 183     *nb_elems -= to_write;
 184
 185     return ret;
 186 }
 187
 188 int av_fifo_write(AVFifo *f, const void *buf, size_t nb_elems)
 189 {
 190     return fifo_write_common(f, buf, &nb_elems, NULL, NULL);
 191 }
 192
 193 int av_fifo_write_from_cb(AVFifo *f, AVFifoCB read_cb,
 194                           void *opaque, size_t *nb_elems)
 195 {
 196     return fifo_write_common(f, NULL, nb_elems, read_cb, opaque);
 197 }
 198
 199 static int fifo_peek_common(const AVFifo *f, uint8_t *buf, size_t *nb_elems,
 200                             size_t offset, AVFifoCB write_cb, void *opaque)
 201 {
 202     size_t  to_read = *nb_elems;
 203     size_t offset_r = f->offset_r;
 204     size_t can_read = av_fifo_can_read(f);
 205     int         ret = 0;
 206
 207     if (offset > can_read || to_read > can_read - offset) {
 208         *nb_elems = 0;
 209         return AVERROR(EINVAL);
 210     }
 211
 212     if (offset_r >= f->nb_elems - offset)
 213         offset_r -= f->nb_elems - offset;
 214     else
 215         offset_r += offset;
 216
 217     while (to_read > 0) {
 218         size_t    len = FFMIN(f->nb_elems - offset_r, to_read);
 219         uint8_t *rptr = f->buffer + offset_r * f->elem_size;
 220
 221         if (write_cb) {
 222             ret = write_cb(opaque, rptr, &len);
 223             if (ret < 0 || len == 0)
 224                 break;
 225         } else {
 226             memcpy(buf, rptr, len * f->elem_size);
 227             buf += len * f->elem_size;
 228         }
 229         offset_r += len;
 230         if (offset_r >= f->nb_elems)
 231             offset_r = 0;
 232         to_read -= len;
 233     }
 234
 235     *nb_elems -= to_read;
 236
 237     return ret;
 238 }
 239
 240 int av_fifo_read(AVFifo *f, void *buf, size_t nb_elems)
 241 {
 242     int ret = fifo_peek_common(f, buf, &nb_elems, 0, NULL, NULL);
 243     av_fifo_drain2(f, nb_elems);
 244     return ret;
 245 }
 246
 247 int av_fifo_read_to_cb(AVFifo *f, AVFifoCB write_cb,
 248                        void *opaque, size_t *nb_elems)
 249 {
 250     int ret = fifo_peek_common(f, NULL, nb_elems, 0, write_cb, opaque);
 251     av_fifo_drain2(f, *nb_elems);
 252     return ret;
 253 }
 254
 255 int av_fifo_peek(const AVFifo *f, void *buf, size_t nb_elems, size_t offset)
 256 {
 257     return fifo_peek_common(f, buf, &nb_elems, offset, NULL, NULL);
 258 }
 259
 260 int av_fifo_peek_to_cb(const AVFifo *f, AVFifoCB write_cb, void *opaque,
 261                        size_t *nb_elems, size_t offset)
 262 {
 263     return fifo_peek_common(f, NULL, nb_elems, offset, write_cb, opaque);
 264 }
 265
 266 void av_fifo_drain2(AVFifo *f, size_t size)
 267 {
 268     const size_t cur_size = av_fifo_can_read(f);
 269
 270     av_assert0(cur_size >= size);
 271     if (cur_size == size)
 272         f->is_empty = 1;
 273
 274     if (f->offset_r >= f->nb_elems - size)
 275         f->offset_r -= f->nb_elems - size;
 276     else
 277         f->offset_r += size;
 278 }
 279
 280 void av_fifo_reset2(AVFifo *f)
 281 {
 282     f->offset_r = f->offset_w = 0;
 283     f->is_empty = 1;
 284 }
 285
 286 void av_fifo_freep2(AVFifo **f)
 287 {
 288     if (*f) {
 289         av_freep(&(*f)->buffer);
 290         av_freep(f);
 291     }
 292 }