Fix bug in schro_buflist_extract where bytes equal in length to the
previous parse unit were being skipped when using the autoparse API.
schro_buflist_peekbytes already invokes schro_buflist_internal_seek to
skip buflist->offset bytes so we don't need to pass an offset to it when
the parse unit spans several buffers.
Regards,
Anu
On Tue, 2009-01-20 at 23:48 +0000, [email protected] wrote:
> 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
diff --git a/schroedinger/schrobufferlist.c b/schroedinger/schrobufferlist.c
index e8664e2..2caa8f1 100644
--- a/schroedinger/schrobufferlist.c
+++ b/schroedinger/schrobufferlist.c
@@ -260,7 +260,7 @@ schro_buflist_extract (SchroBufferList *buflist, unsigned start, unsigned len)
}
buf = schro_buffer_new_and_alloc (len);
- schro_buflist_peekbytes (buf->data, len, buflist, start);
+ schro_buflist_peekbytes (buf->data, len, buflist, 0);
return buf;
}
------------------------------------------------------------------------------
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
