Alc/ringbuffer.c

   1 /**
   2  * OpenAL cross platform audio library
   3  * Copyright (C) 1999-2007 by authors.
   4  * This library is free software; you can redistribute it and/or
   5  *  modify it under the terms of the GNU Library General Public
   6  *  License as published by the Free Software Foundation; either
   7  *  version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  *  Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  *  License along with this library; if not, write to the
  16  *  Free Software Foundation, Inc.,
  17  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18  * Or go to http://www.gnu.org/copyleft/lgpl.html
  19  */
  20
  21 #include "config.h"
  22
  23 #include <string.h>
  24 #include <stdlib.h>
  25 #include <limits.h>
  26
  27 #include "ringbuffer.h"
  28 #include "align.h"
  29 #include "atomic.h"
  30 #include "threads.h"
  31 #include "almalloc.h"
  32 #include "compat.h"
  33
  34
  35 /* NOTE: This lockless ringbuffer implementation is copied from JACK, extended
  36  * to include an element size. Consequently, parameters and return values for a
  37  * size or count is in 'elements', not bytes. Additionally, it only supports
  38  * single-consumer/single-provider operation. */
  39 struct ll_ringbuffer {
  40     ATOMIC(size_t) write_ptr;
  41     ATOMIC(size_t) read_ptr;
  42     size_t size;
  43     size_t size_mask;
  44     size_t elem_size;
  45
  46     alignas(16) char buf[];
  47 };
  48
  49 /* Create a new ringbuffer to hold at least `sz' elements of `elem_sz' bytes.
  50  * The number of elements is rounded up to the next power of two. */
  51 ll_ringbuffer_t *ll_ringbuffer_create(size_t sz, size_t elem_sz)
  52 {
  53     ll_ringbuffer_t *rb;
  54     size_t power_of_two = 0;
  55
  56     if(sz > 0)
  57     {
  58         power_of_two = sz - 1;
  59         power_of_two |= power_of_two>>1;
  60         power_of_two |= power_of_two>>2;
  61         power_of_two |= power_of_two>>4;
  62         power_of_two |= power_of_two>>8;
  63         power_of_two |= power_of_two>>16;
  64 #if SIZE_MAX > UINT_MAX
  65         power_of_two |= power_of_two>>32;
  66 #endif
  67     }
  68     power_of_two++;
  69     if(power_of_two < sz) return NULL;
  70
  71     rb = al_malloc(16, sizeof(*rb) + power_of_two*elem_sz);
  72     if(!rb) return NULL;
  73
  74     ATOMIC_INIT(&rb->write_ptr, 0);
  75     ATOMIC_INIT(&rb->read_ptr, 0);
  76     rb->size = power_of_two;
  77     rb->size_mask = rb->size - 1;
  78     rb->elem_size = elem_sz;
  79     return rb;
  80 }
  81
  82 /* Free all data associated with the ringbuffer `rb'. */
  83 void ll_ringbuffer_free(ll_ringbuffer_t *rb)
  84 {
  85     al_free(rb);
  86 }
  87
  88 /* Reset the read and write pointers to zero. This is not thread safe. */
  89 void ll_ringbuffer_reset(ll_ringbuffer_t *rb)
  90 {
  91     ATOMIC_STORE(&rb->write_ptr, 0, almemory_order_release);
  92     ATOMIC_STORE(&rb->read_ptr, 0, almemory_order_release);
  93     memset(rb->buf, 0, rb->size*rb->elem_size);
  94 }
  95
  96 /* Return the number of elements available for reading. This is the number of
  97  * elements in front of the read pointer and behind the write pointer. */
  98 size_t ll_ringbuffer_read_space(const ll_ringbuffer_t *rb)
  99 {
 100     size_t w = ATOMIC_LOAD(&CONST_CAST(ll_ringbuffer_t*,rb)->write_ptr, almemory_order_acquire);
 101     size_t r = ATOMIC_LOAD(&CONST_CAST(ll_ringbuffer_t*,rb)->read_ptr, almemory_order_acquire);
 102     return (w-r) & rb->size_mask;
 103 }
 104 /* Return the number of elements available for writing. This is the number of
 105  * elements in front of the write pointer and behind the read pointer. */
 106 size_t ll_ringbuffer_write_space(const ll_ringbuffer_t *rb)
 107 {
 108     size_t w = ATOMIC_LOAD(&CONST_CAST(ll_ringbuffer_t*,rb)->write_ptr, almemory_order_acquire);
 109     size_t r = ATOMIC_LOAD(&CONST_CAST(ll_ringbuffer_t*,rb)->read_ptr, almemory_order_acquire);
 110     return (r-w-1) & rb->size_mask;
 111 }
 112
 113 /* The copying data reader. Copy at most `cnt' elements from `rb' to `dest'.
 114  * Returns the actual number of elements copied. */
 115 size_t ll_ringbuffer_read(ll_ringbuffer_t *rb, char *dest, size_t cnt)
 116 {
 117     size_t read_ptr;
 118     size_t free_cnt;
 119     size_t cnt2;
 120     size_t to_read;
 121     size_t n1, n2;
 122
 123     free_cnt = ll_ringbuffer_read_space(rb);
 124     if(free_cnt == 0) return 0;
 125
 126     to_read = (cnt > free_cnt) ? free_cnt : cnt;
 127     read_ptr = ATOMIC_LOAD(&rb->read_ptr, almemory_order_relaxed) & rb->size_mask;
 128
 129     cnt2 = read_ptr + to_read;
 130     if(cnt2 > rb->size)
 131     {
 132         n1 = rb->size - read_ptr;
 133         n2 = cnt2 & rb->size_mask;
 134     }
 135     else
 136     {
 137         n1 = to_read;
 138         n2 = 0;
 139     }
 140
 141     memcpy(dest, &rb->buf[read_ptr*rb->elem_size], n1*rb->elem_size);
 142     read_ptr += n1;
 143     if(n2)
 144     {
 145         memcpy(dest + n1*rb->elem_size, &rb->buf[(read_ptr&rb->size_mask)*rb->elem_size],
 146                n2*rb->elem_size);
 147         read_ptr += n2;
 148     }
 149     ATOMIC_STORE(&rb->read_ptr, read_ptr, almemory_order_release);
 150     return to_read;
 151 }
 152
 153 /* The copying data reader w/o read pointer advance. Copy at most `cnt'
 154  * elements from `rb' to `dest'. Returns the actual number of elements copied.
 155  */
 156 size_t ll_ringbuffer_peek(ll_ringbuffer_t *rb, char *dest, size_t cnt)
 157 {
 158     size_t free_cnt;
 159     size_t cnt2;
 160     size_t to_read;
 161     size_t n1, n2;
 162     size_t read_ptr;
 163
 164     free_cnt = ll_ringbuffer_read_space(rb);
 165     if(free_cnt == 0) return 0;
 166
 167     to_read = (cnt > free_cnt) ? free_cnt : cnt;
 168     read_ptr = ATOMIC_LOAD(&rb->read_ptr, almemory_order_relaxed) & rb->size_mask;
 169
 170     cnt2 = read_ptr + to_read;
 171     if(cnt2 > rb->size)
 172     {
 173         n1 = rb->size - read_ptr;
 174         n2 = cnt2 & rb->size_mask;
 175     }
 176     else
 177     {
 178         n1 = to_read;
 179         n2 = 0;
 180     }
 181
 182     memcpy(dest, &rb->buf[read_ptr*rb->elem_size], n1*rb->elem_size);
 183     if(n2)
 184     {
 185         read_ptr += n1;
 186         memcpy(dest + n1*rb->elem_size, &rb->buf[(read_ptr&rb->size_mask)*rb->elem_size],
 187                n2*rb->elem_size);
 188     }
 189     return to_read;
 190 }
 191
 192 /* The copying data writer. Copy at most `cnt' elements to `rb' from `src'.
 193  * Returns the actual number of elements copied. */
 194 size_t ll_ringbuffer_write(ll_ringbuffer_t *rb, const char *src, size_t cnt)
 195 {
 196     size_t write_ptr;
 197     size_t free_cnt;
 198     size_t cnt2;
 199     size_t to_write;
 200     size_t n1, n2;
 201
 202     free_cnt = ll_ringbuffer_write_space(rb);
 203     if(free_cnt == 0) return 0;
 204
 205     to_write = (cnt > free_cnt) ? free_cnt : cnt;
 206     write_ptr = ATOMIC_LOAD(&rb->write_ptr, almemory_order_relaxed) & rb->size_mask;
 207
 208     cnt2 = write_ptr + to_write;
 209     if(cnt2 > rb->size)
 210     {
 211         n1 = rb->size - write_ptr;
 212         n2 = cnt2 & rb->size_mask;
 213     }
 214     else
 215     {
 216         n1 = to_write;
 217         n2 = 0;
 218     }
 219
 220     memcpy(&rb->buf[write_ptr*rb->elem_size], src, n1*rb->elem_size);
 221     write_ptr += n1;
 222     if(n2)
 223     {
 224         memcpy(&rb->buf[(write_ptr&rb->size_mask)*rb->elem_size], src + n1*rb->elem_size,
 225                n2*rb->elem_size);
 226         write_ptr += n2;
 227     }
 228     ATOMIC_STORE(&rb->write_ptr, write_ptr, almemory_order_release);
 229     return to_write;
 230 }
 231
 232 /* Advance the read pointer `cnt' places. */
 233 void ll_ringbuffer_read_advance(ll_ringbuffer_t *rb, size_t cnt)
 234 {
 235     ATOMIC_ADD(&rb->read_ptr, cnt, almemory_order_acq_rel);
 236 }
 237
 238 /* Advance the write pointer `cnt' places. */
 239 void ll_ringbuffer_write_advance(ll_ringbuffer_t *rb, size_t cnt)
 240 {
 241     ATOMIC_ADD(&rb->write_ptr, cnt, almemory_order_acq_rel);
 242 }
 243
 244 /* The non-copying data reader. `vec' is an array of two places. Set the values
 245  * at `vec' to hold the current readable data at `rb'. If the readable data is
 246  * in one segment the second segment has zero length. */
 247 void ll_ringbuffer_get_read_vector(const ll_ringbuffer_t *rb, ll_ringbuffer_data_t * vec)
 248 {
 249     size_t free_cnt;
 250     size_t cnt2;
 251     size_t w, r;
 252
 253     w = ATOMIC_LOAD(&CONST_CAST(ll_ringbuffer_t*,rb)->write_ptr, almemory_order_acquire);
 254     r = ATOMIC_LOAD(&CONST_CAST(ll_ringbuffer_t*,rb)->read_ptr, almemory_order_acquire);
 255     w &= rb->size_mask;
 256     r &= rb->size_mask;
 257     free_cnt = (w-r) & rb->size_mask;
 258
 259     cnt2 = r + free_cnt;
 260     if(cnt2 > rb->size)
 261     {
 262         /* Two part vector: the rest of the buffer after the current write ptr,
 263          * plus some from the start of the buffer. */
 264         vec[0].buf = (char*)&rb->buf[r*rb->elem_size];
 265         vec[0].len = rb->size - r;
 266         vec[1].buf = (char*)rb->buf;
 267         vec[1].len = cnt2 & rb->size_mask;
 268     }
 269     else
 270     {
 271         /* Single part vector: just the rest of the buffer */
 272         vec[0].buf = (char*)&rb->buf[r*rb->elem_size];
 273         vec[0].len = free_cnt;
 274         vec[1].buf = NULL;
 275         vec[1].len = 0;
 276     }
 277 }
 278
 279 /* The non-copying data writer. `vec' is an array of two places. Set the values
 280  * at `vec' to hold the current writeable data at `rb'. If the writeable data
 281  * is in one segment the second segment has zero length. */
 282 void ll_ringbuffer_get_write_vector(const ll_ringbuffer_t *rb, ll_ringbuffer_data_t *vec)
 283 {
 284     size_t free_cnt;
 285     size_t cnt2;
 286     size_t w, r;
 287
 288     w = ATOMIC_LOAD(&CONST_CAST(ll_ringbuffer_t*,rb)->write_ptr, almemory_order_acquire);
 289     r = ATOMIC_LOAD(&CONST_CAST(ll_ringbuffer_t*,rb)->read_ptr, almemory_order_acquire);
 290     w &= rb->size_mask;
 291     r &= rb->size_mask;
 292     free_cnt = (r-w-1) & rb->size_mask;
 293
 294     cnt2 = w + free_cnt;
 295     if(cnt2 > rb->size)
 296     {
 297         /* Two part vector: the rest of the buffer after the current write ptr,
 298          * plus some from the start of the buffer. */
 299         vec[0].buf = (char*)&rb->buf[w*rb->elem_size];
 300         vec[0].len = rb->size - w;
 301         vec[1].buf = (char*)rb->buf;
 302         vec[1].len = cnt2 & rb->size_mask;
 303     }
 304     else
 305     {
 306         vec[0].buf = (char*)&rb->buf[w*rb->elem_size];
 307         vec[0].len = free_cnt;
 308         vec[1].buf = NULL;
 309         vec[1].len = 0;
 310     }
 311 }