From: David Flynn <[email protected]> Bufferlists are lists of buffers, intended for doing synchronisation and extraction operations over multiple buffers
includes: - fix pessimistic off by one error in find (comment was correct, code not) - fix case when find on empty list wraps offset Signed-off-by: David Flynn <[email protected]> --- schroedinger/Makefile.am | 2 + schroedinger/schrobufferlist.c | 230 ++++++++++++++++++++++++++++++++++++++++ schroedinger/schrobufferlist.h | 51 +++++++++ 3 files changed, 283 insertions(+), 0 deletions(-) create mode 100644 schroedinger/schrobufferlist.c create mode 100644 schroedinger/schrobufferlist.h diff --git a/schroedinger/Makefile.am b/schroedinger/Makefile.am index 020d26d..1d22f09 100644 --- a/schroedinger/Makefile.am +++ b/schroedinger/Makefile.am @@ -20,6 +20,7 @@ EXTRA_DIST = schroarith-i386.c \ pkginclude_HEADERS = \ schro.h \ schrobuffer.h \ + schrobufferlist.h \ schrocog.h \ schrodecoder.h \ schroencoder.h \ @@ -84,6 +85,7 @@ libschroeding...@schro_majorminor@_la_SOURCES = \ schroframe.c \ schrohistogram.c \ schrobuffer.c \ + schrobufferlist.c \ schrolowdelay.c \ schromotion.c \ schrooil.c \ diff --git a/schroedinger/schrobufferlist.c b/schroedinger/schrobufferlist.c new file mode 100644 index 0000000..39dd21e --- /dev/null +++ b/schroedinger/schrobufferlist.c @@ -0,0 +1,230 @@ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <schroedinger/schrobufferlist.h> +#include <schroedinger/schrodebug.h> +#include <string.h> + +#ifndef _MIN +#define _MIN(x,y) (((x) < (y)) ? (x) : (y)) +#endif + +#ifndef _MAX +#define _MAX(x,y) (((x) > (y)) ? (x) : (y)) +#endif + +SchroBufferList * +schro_buflist_new (void) +{ + SchroList *list = schro_list_new_full ((SchroListFreeFunc)schro_buffer_unref, NULL); + SchroBufferList *buflist = realloc (list, sizeof(*buflist)); + + buflist->offset = 0; + return buflist; +} + +int +schro_buflist_peekbytes (uint8_t *dst, unsigned len, SchroBufferList *buflist, unsigned offset) +{ + SchroBuffer *buf; + int bufidx = 0; + int coppied = 0; + + if (!dst || !len) { + return 0; + } + + /* skip over any discarded data at start of buflist */ + offset += buflist->offset; + + /* find buffer offset starts in */ + for (bufidx = 0; bufidx < buflist->list.n; bufidx++) { + buf = buflist->list.members[bufidx]; + if( offset < buf->length ) { + /* found */ + break; + } + offset -= buf->length; + } + + /* copy out upto len worth of bytes. NB, this may cross + * buffer boundries */ + for (; bufidx < buflist->list.n; bufidx++) { + buf = buflist->list.members[bufidx]; + unsigned size = _MIN(len, buf->length - offset); + memcpy(dst + coppied, buf->data + offset, size); + offset = 0; + coppied += size; + len -= size; + if (!len) { + break; + } + } + + return coppied; +} + +int +schro_buflist_findbytes (SchroBufferList *buflist, unsigned *start, const uint8_t *needle, unsigned needle_len) +{ + SchroBuffer *buf; + unsigned bufidx = 0; + unsigned where = *start; + unsigned offset; + unsigned n = 0; + unsigned backtrack_bufidx = 0, backtrack_where = 0, backtrack_i = 0; + + if (!needle || !needle_len) { + return 0; + } + + /* skip over any discarded data at start of buflist */ + offset = buflist->offset + *start; + + /* find buffer offset starts in */ + for (bufidx = 0; bufidx < buflist->list.n; bufidx++) { + buf = buflist->list.members[bufidx]; + if( offset < buf->length ) { + /* found */ + break; + } + offset -= buf->length; + } + + /* search for what[], NB this may span multiple buffers */ + /* NB, if a search fails, it must be backtracked */ + for (; bufidx < buflist->list.n; bufidx++) { + /* todo, maybe add memmem call ? */ +#if 0 + if (!n) { + /* not in the middle of a search that spans buffers */ + uint8_t *pos = memmem(buf->data + offset + ,buf->length - offset + ,needle, needle_len); + if (pos) { + /* found */ + where += pos - buf->data - offset; + return where; + } + offset = _MAX(offset, buf->length - needle_len); + /* ^^^ +1 required ? */ + } +#endif + unsigned i = offset; + buf = buflist->list.members[bufidx]; + for (; i < buf->length; i++) { + if (needle[n] == buf->data[i]) { + if (!n) { + /* save back tracking point */ + backtrack_where = where; + backtrack_i = i; + backtrack_bufidx = bufidx; + } + n++; + if (n == needle_len) { + *start = backtrack_where; + return 1; + } + } + else if (n) { + n = 0; + /* restore backtracking point */ + i = backtrack_i; + where = backtrack_where; + bufidx = backtrack_bufidx; + } + } + where += buf->length - offset; + offset = 0; + } + + /* not found */ + /* NB, to make it possible to resume a search where this failed, + * must move where back by (needle_len-1), but don't go past start */ + /* but avoid unsigned wraparound */ + if (needle_len <= where) + *start = _MAX(where - needle_len + 1, *start); + return 0; +} + +void +schro_buflist_flush (SchroBufferList *buflist, unsigned amount) +{ + SchroBuffer *buf; + int bufidx = 0; + + /* include any discarded data at start of buflist */ + buflist->offset += amount; + + /* pop and unref all buffers that end before ammount */ + for (bufidx = 0; bufidx < buflist->list.n; bufidx++) { + buf = buflist->list.members[bufidx]; + if( buflist->offset < buf->length ) { + /* found */ + break; + } + buflist->offset -= buf->length; + schro_list_delete (&buflist->list, 0); + bufidx--; + } +} + +SchroBuffer * +schro_buflist_extract (SchroBufferList *buflist, unsigned start, unsigned len) +{ + SchroBuffer *buf, *dst; + int bufidx = 0; + uint8_t tmp; + int done = 0; + + SCHRO_ASSERT(buflist); + + if (!len) { + return NULL; + } + + /* first check that the (start + len)th byte is avaliable */ + if (!schro_buflist_peekbytes (&tmp, 1, buflist, start + len -1)) { + return NULL; + } + + /* skip over any discarded data at start of buflist */ + start += buflist->offset; + + /* find buffer offset starts in */ + /* guaranteed that we wont run off the list of buffers */ + for (bufidx = 0; bufidx < buflist->list.n; bufidx++) { + buf = buflist->list.members[bufidx]; + if (start < buf->length) { + /* found */ + break; + } + start -= buf->length; + } + + SCHRO_ASSERT(bufidx < buflist->list.n); + + if (start + len <= buf->length) { + /* Special case, if the requested range is contained within a single + * buffer, then use a subbuffer */ + return schro_buffer_new_subbuffer (buf, start, len); + } + + dst = schro_buffer_new_and_alloc (len); + for (; bufidx < buflist->list.n; bufidx++) { + buf = buflist->list.members[bufidx]; + int size = _MIN(len, buf->length - start); + memcpy(dst->data + done, buf->data + start, size); + start = 0; + done += size; + len -= size; + if (!len) + return dst; + } + + /* not reachable */ + SCHRO_ASSERT(!len); + return NULL; +} diff --git a/schroedinger/schrobufferlist.h b/schroedinger/schrobufferlist.h new file mode 100644 index 0000000..13d0b59 --- /dev/null +++ b/schroedinger/schrobufferlist.h @@ -0,0 +1,51 @@ +#ifndef __SCHRO_BUFFERLIST_H__ +#define __SCHRO_BUFFERLIST_H__ + +#include <schroedinger/schroutils.h> +#include <schroedinger/schrobuffer.h> +#include <schroedinger/schrolist.h> + +SCHRO_BEGIN_DECLS + +#ifdef SCHRO_ENABLE_UNSTABLE_API + +typedef struct _SchroBufferList SchroBufferList; + +struct _SchroBufferList +{ + SchroList list; + /* private */ + unsigned offset; +}; + +SchroBufferList *schro_buflist_new (void); +int schro_buflist_peekbytes (uint8_t *dst, unsigned len, SchroBufferList *buflist, unsigned offset); +int schro_buflist_findbytes (SchroBufferList *buflist, unsigned *start, const uint8_t *needle, unsigned needle_len); +void schro_buflist_flush (SchroBufferList *buflist, unsigned amount); +SchroBuffer * schro_buflist_extract (SchroBufferList *buflist, unsigned start, unsigned len); + +static inline +void schro_buflist_free (SchroBufferList *buflist) +{ + schro_list_free (&buflist->list); +} + +static inline +void schro_buflist_append (SchroBufferList *buflist, SchroBuffer *buf) +{ + schro_list_append (&buflist->list, buf); +} + +#if 0 +static inline +SchroBuffer *schro_buflist_remove_head (SchroBufferList *buflist) +{ + return schro_list_remove(&buflist->list, 0); +} +#endif + +#endif + +SCHRO_END_DECLS + +#endif -- 1.5.6.5 ------------------------------------------------------------------------------ This SF.net email is sponsored by: SourcForge Community SourceForge wants to tell your story. http://p.sf.net/sfu/sf-spreadtheword _______________________________________________ Schrodinger-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/schrodinger-devel
