summaryrefslogtreecommitdiff
path: root/cesar/lib/src
diff options
context:
space:
mode:
Diffstat (limited to 'cesar/lib/src')
-rw-r--r--cesar/lib/src/aatree.c312
-rw-r--r--cesar/lib/src/atox.c383
-rw-r--r--cesar/lib/src/bitstream.c394
-rw-r--r--cesar/lib/src/blk.c244
-rw-r--r--cesar/lib/src/circular_buffer.c101
-rw-r--r--cesar/lib/src/crc.c193
-rw-r--r--cesar/lib/src/dbg.c71
-rw-r--r--cesar/lib/src/heap.c62
-rw-r--r--cesar/lib/src/leftheap.c159
-rw-r--r--cesar/lib/src/list.c181
-rw-r--r--cesar/lib/src/mt19937ar.c260
-rw-r--r--cesar/lib/src/read_word.c129
-rw-r--r--cesar/lib/src/restrack.c353
-rw-r--r--cesar/lib/src/skewheap.c138
-rw-r--r--cesar/lib/src/swap.c31
-rw-r--r--cesar/lib/src/test.c138
-rw-r--r--cesar/lib/src/trace.c655
-rw-r--r--cesar/lib/src/try.c17
18 files changed, 3821 insertions, 0 deletions
diff --git a/cesar/lib/src/aatree.c b/cesar/lib/src/aatree.c
new file mode 100644
index 0000000000..d58085a1f8
--- /dev/null
+++ b/cesar/lib/src/aatree.c
@@ -0,0 +1,312 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/aatree.c
+ * \brief Arne Andersson Trees.
+ * \ingroup lib
+ */
+#include "common/std.h"
+
+#include "lib/set.h"
+
+/** The NIL node, which loops to itself. */
+static set_node_t aatree_nil =
+{
+ NULL, &aatree_nil, &aatree_nil, 0
+};
+
+/** Pointer to the NIL node. */
+#define NIL (&aatree_nil)
+
+/**
+ * Skew operation, eliminate horizontal left edge, non recursive.
+ * \param nodep upper node pointer
+ */
+extern inline void
+aatree_skew (set_node_t **nodep)
+{
+ /*
+ * If l.level == r.level, they are the same pseudo-node and r left link is
+ * horizontal. This is forbidden.
+ *
+ * \ \
+ * r l
+ * / \ => / \
+ * l 3 1 r
+ * / \ / \
+ * 1 2 2 3
+ */
+ set_node_t *r, *l;
+ r = *nodep;
+ l = r->left;
+ if (l->level == r->level)
+ {
+ *nodep = l;
+ l->father = r->father;
+ r->left = l->right;
+ if (r->left != NIL)
+ r->left->father = r;
+ l->right = r;
+ r->father = l;
+ }
+}
+
+/**
+ * Split operation, split a too large pseudo-node.
+ * \param nodep upper node pointer
+ */
+extern inline void
+aatree_split (set_node_t **nodep)
+{
+ /*
+ * If l.level == r.level, the pseudo-node is too large, slit it.
+ *
+ * \ \
+ * l m
+ * / \ _/ \_
+ * 1 m => l r
+ * / \ / \ / \
+ * 2 r 1 2 3 4
+ * / \
+ * 3 4
+ */
+ set_node_t *r, *m, *l;
+ l = *nodep;
+ m = l->right;
+ r = m->right;
+ if (l->level == r->level)
+ {
+ *nodep = m;
+ m->father = l->father;
+ l->right = m->left;
+ if (l->right != NIL)
+ l->right->father = l;
+ m->left = l;
+ l->father = m;
+ m->level++;
+ }
+}
+
+void
+set_init (set_t *set, set_node_less_t less)
+{
+ dbg_assert (set);
+ set->root = NIL;
+ set->less = less;
+}
+
+void
+set_node_init (set_node_t *node)
+{
+ dbg_assert (node);
+ node->father = NULL;
+ node->left = node->right = NULL;
+ node->level = 0;
+}
+
+set_node_t *
+set_find (set_t *set, set_node_t *node)
+{
+ /* Use the two-way comparison optimisation from "A. Andersson. A note on
+ * searching in a binary search tree". */
+ set_node_t *p, *candidate;
+ dbg_assert (set);
+ dbg_assert (node && node->level == 0);
+ p = set->root;
+ candidate = NULL;
+ while (p != NIL)
+ {
+ if (set->less (node, p))
+ {
+ p = p->left;
+ }
+ else
+ {
+ candidate = p;
+ p = p->right;
+ }
+ }
+ if (candidate && !set->less (candidate, node))
+ return candidate;
+ else
+ return NULL;
+}
+
+bool
+set_insert (set_t *set, set_node_t *node)
+{
+ set_node_t *father, *candidate, **np, *up;
+ dbg_assert (set);
+ dbg_assert (node && node->level == 0);
+ /* Go down, from root. */
+ father = NULL;
+ np = &set->root;
+ candidate = NULL;
+ while (*np != NIL)
+ {
+ father = *np;
+ dbg_assert_print (father != node, "node is in the set yet");
+ if (set->less (node, father))
+ {
+ np = &father->left;
+ }
+ else
+ {
+ candidate = father;
+ np = &father->right;
+ }
+ }
+ /* Refuse to add a node equal to another node. */
+ if (candidate && !set->less (candidate, node))
+ return false;
+ /* Add the new node in np. */
+ *np = node;
+ node->father = father;
+ node->left = node->right = NIL;
+ node->level = 1;
+ /* Go up. */
+ while (father)
+ {
+ up = father->father;
+ if (!up)
+ np = &set->root;
+ else if (up->right == father)
+ np = &up->right;
+ else
+ np = &up->left;
+ father = up;
+ aatree_skew (np);
+ aatree_split (np);
+ }
+ return true;
+}
+
+void
+set_remove (set_t *set, set_node_t *node)
+{
+ set_node_t *heir, **np, *up;
+ dbg_assert (set);
+ dbg_assert (node && node != NIL && node->level != 0);
+ /* Find node pointer. */
+ if (!node->father)
+ np = &set->root;
+ else if (node->father->left == node)
+ np = &node->father->left;
+ else
+ np = &node->father->right;
+ /* Find the heir node (the leaf node which will replace the removed node
+ * in the tree). */
+ if (node->left == NIL)
+ {
+ *np = node->right;
+ up = node->father;
+ if (node->right != NIL)
+ node->right->father = up;
+ }
+ else if (node->right == NIL)
+ {
+ dbg_assert (node->left == NIL && node->level == 1);
+ *np = NIL;
+ up = node->father;
+ }
+ else
+ {
+ for (heir = node->left; heir->right != NIL; heir = heir->right)
+ ;
+ /* The heir node can not have a left child because it does not have a
+ * right child. Why:
+ * heir->right == NIL => heir->right->level == 0 => heir->level = 1
+ * heir->left != NIL => heir->left->level >= 1 => horizontal left link
+ * forbidden! */
+ dbg_assert (heir->left == NIL && heir->level == 1);
+ if (heir != node->left)
+ {
+ heir->father->right = NIL;
+ up = heir->father;
+ heir->left = node->left;
+ heir->left->father = heir;
+ }
+ else
+ {
+ up = heir;
+ }
+ heir->father = node->father;
+ heir->right = node->right;
+ heir->right->father = heir;
+ heir->level = node->level;
+ *np = heir;
+ }
+ /* Go up and rebalance. */
+ while (up)
+ {
+ if (!up->father)
+ np = &set->root;
+ else if (up->father->right == up)
+ np = &up->father->right;
+ else
+ np = &up->father->left;
+ /* Rebalance. */
+ if (up->left->level < up->level - 1
+ || up->right->level < up->level - 1)
+ {
+ up->level--;
+ if (up->right->level > up->level)
+ up->right->level = up->level;
+ aatree_skew (np);
+ if ((*np)->right != NIL)
+ aatree_skew (&(*np)->right);
+ if ((*np)->right->right != NIL)
+ aatree_skew (&(*np)->right->right);
+ aatree_split (np);
+ if ((*np)->right != NIL)
+ aatree_split (&(*np)->right);
+ }
+ /* Next. */
+ up = up->father;
+ }
+ node->father = NULL;
+ node->left = node->right = NULL;
+ node->level = 0;
+}
+
+set_node_t *
+set_begin (set_t *set)
+{
+ set_node_t *n;
+ dbg_assert (set);
+ /* First node is far on the left. */
+ for (n = set->root; n->left != NIL; n = n->left)
+ ;
+ return n != NIL ? n : NULL;
+}
+
+set_node_t *
+set_next (set_t *set, set_node_t *node)
+{
+ set_node_t *n, *nc;
+ dbg_assert (set);
+ dbg_assert (node && node != NIL && node->level != 0);
+ n = node;
+ if (n->right != NIL)
+ {
+ /* If there is a right subtree, find its minimal node. */
+ for (n = n->right; n->left != NIL; n = n->left)
+ ;
+ }
+ else
+ {
+ /* Else, go up until we come from left. */
+ do
+ {
+ nc = n;
+ n = n->father;
+ } while (n && n->right == nc);
+ }
+ return n;
+}
+
diff --git a/cesar/lib/src/atox.c b/cesar/lib/src/atox.c
new file mode 100644
index 0000000000..9dd8160710
--- /dev/null
+++ b/cesar/lib/src/atox.c
@@ -0,0 +1,383 @@
+/**{{{
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of
+ * the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston,
+ * MA 02111-1307 USA
+ }}}*/
+/**
+ * \file lib/src/atox.c
+ * \brief ASCII string convertions
+ * \ingroup lib
+ */
+#include "lib/atox.h"
+
+#define LONG_MAX 2147483647L
+#define LONG_MIN (-LONG_MAX-1)
+#define LONG_LONG_MAX 9223372036854775807LL
+#define LONG_LONG_MIN (-LONG_LONG_MAX-1)
+#define ULONG_MAX (LONG_MAX * 2UL + 1)
+#define ULONG_LONG_MAX (LONG_LONG_MAX * 2ULL + 1)
+
+static inline int isupper(int c)
+{
+ return (('A' <= c) && (c <= 'Z'));
+} //isupper
+
+static inline int islower(int c)
+{
+ return (('a' <= c) && (c <= 'z'));
+} //islower
+
+static inline int isalpha(int c)
+{
+ return ( islower(c) || isupper(c) );
+} //isalpha
+
+static inline int isdigit(int c)
+{
+ return ( ('0' <= c) && (c <= '9') );
+} //isdigit
+
+static inline int isspace(int c)
+{
+ return ( (c == ' ') || (c == '\f') || (c == '\n') || (c == '\r') ||
+ (c == '\t') || (c == '\v') );
+} //isspace
+
+static unsigned long long strtoull(const char *nptr, char **endptr, int base)
+{
+ const char *s = nptr;
+ unsigned long long acc;
+ int c;
+ unsigned long long cutoff;
+ int neg = 0, any, cutlim;
+
+ if (endptr != 0)
+ return -1;
+ //
+ // See strtoll for comments as to the logic used.
+ //
+ do {
+ c = *s++;
+ } while (isspace(c));
+ if (c == '-') {
+ neg = 1;
+ c = *s++;
+ } else if (c == '+')
+ c = *s++;
+ if ((base == 0 || base == 16) &&
+ c == '0' && (*s == 'x' || *s == 'X')) {
+ c = s[1];
+ s += 2;
+ base = 16;
+ }
+ if (base == 0)
+ base = c == '0' ? 8 : 10;
+ cutoff = (unsigned long long)ULONG_LONG_MAX / (unsigned long long)base;
+ cutlim = (unsigned long long)ULONG_LONG_MAX % (unsigned long long)base;
+ for (acc = 0, any = 0;; c = *s++) {
+ if (isdigit(c))
+ c -= '0';
+ else if (isalpha(c))
+ c -= isupper(c) ? 'A' - 10 : 'a' - 10;
+ else
+ break;
+ if (c >= base)
+ break;
+ if ((any < 0) || (acc > cutoff) || ((acc == cutoff) && (c > cutlim)))
+ any = -1;
+ else {
+ any = 1;
+ acc *= base;
+ acc += c;
+ }
+ }
+ if (any < 0) {
+ acc = ULONG_LONG_MAX;
+ } else if (neg)
+ acc = -acc;
+ if (endptr != 0)
+ *endptr = (char *) (any ? s - 1 : nptr);
+
+ return acc;
+} //strtoull
+
+unsigned long strtoul(const char *nptr, char **endptr, int base)
+{
+ const char *s = nptr;
+ unsigned long acc;
+ int c;
+ unsigned long cutoff;
+ int neg = 0, any, cutlim;
+
+ if (endptr != 0)
+ return -1;
+ //
+ // See strtol for comments as to the logic used.
+ //
+ do {
+ c = *s++;
+ } while (isspace(c));
+ if (c == '-') {
+ neg = 1;
+ c = *s++;
+ } else if (c == '+')
+ c = *s++;
+ if ((base == 0 || base == 16) &&
+ c == '0' && (*s == 'x' || *s == 'X')) {
+ c = s[1];
+ s += 2;
+ base = 16;
+ }
+ if (base == 0)
+ base = c == '0' ? 8 : 10;
+ cutoff = (unsigned long)ULONG_MAX / (unsigned long)base;
+ cutlim = (unsigned long)ULONG_MAX % (unsigned long)base;
+ for (acc = 0, any = 0;; c = *s++) {
+ if (isdigit(c))
+ c -= '0';
+ else if (isalpha(c))
+ c -= isupper(c) ? 'A' - 10 : 'a' - 10;
+ else
+ break;
+ if (c >= base)
+ break;
+ if ((any < 0) || (acc > cutoff) || ((acc == cutoff) && (c > cutlim)))
+ any = -1;
+ else {
+ any = 1;
+ acc *= base;
+ acc += c;
+ }
+ }
+ if (any < 0) {
+ acc = ULONG_MAX;
+ } else if (neg)
+ acc = -acc;
+ if (endptr != 0)
+ *endptr = (char *) (any ? s - 1 : nptr);
+
+ return acc;
+} //strtoul
+
+long long strtoll(const char *nptr, char **endptr, int base)
+{
+ const char *s = nptr;
+ unsigned long long acc;
+ int c;
+ unsigned long long cutoff;
+ int neg = 0, any, cutlim;
+
+ if (endptr != 0)
+ return -1;
+
+ //
+ // Skip white space and pick up leading +/- sign if any.
+ // If base is 0, allow 0x for hex and 0 for octal, else
+ // assume decimal; if base is already 16, allow 0x.
+ //
+
+ do {
+ c = *s++;
+ } while (isspace(c));
+ if (c == '-') {
+ neg = 1;
+ c = *s++;
+ } else if (c == '+')
+ c = *s++;
+ if ((base == 0 || base == 16) &&
+ c == '0' && (*s == 'x' || *s == 'X')) {
+ c = s[1];
+ s += 2;
+ base = 16;
+ }
+ if (base == 0)
+ base = c == '0' ? 8 : 10;
+
+ //
+ // Compute the cutoff value between legal numbers and illegal
+ // numbers. That is the largest legal value, divided by the
+ // base. An input number that is greater than this value, if
+ // followed by a legal input character, is too big. One that
+ // is equal to this value may be valid or not; the limit
+ // between valid and invalid numbers is then based on the last
+ // digit. For instance, if the range for long longs is
+ // [-2147483648..2147483647] and the input base is 10,
+ // cutoff will be set to 214748364 and cutlim to either
+ // 7 (neg==0) or 8 (neg==1), meaning that if we have accumulated
+ // a value > 214748364, or equal but the next digit is > 7 (or 8),
+ // the number is too big, and we will return a range error.
+ //
+ // Set any if any `digits' consumed; make it negative to indicate
+ // overflow.
+ //
+
+ cutoff = neg ? -(unsigned long long)LONG_LONG_MIN : LONG_LONG_MAX;
+ cutlim = cutoff % (unsigned long long)base;
+ cutoff /= (unsigned long long)base;
+ for (acc = 0, any = 0;; c = *s++) {
+ if (isdigit(c))
+ c -= '0';
+ else if (isalpha(c))
+ c -= isupper(c) ? 'A' - 10 : 'a' - 10;
+ else
+ break;
+ if (c >= base)
+ break;
+ if ((any < 0) || (acc > cutoff) || ((acc == cutoff) && (c > cutlim)))
+ any = -1;
+ else {
+ any = 1;
+ acc *= base;
+ acc += c;
+ }
+ }
+ if (any < 0) {
+ acc = neg ? LONG_LONG_MIN : LONG_LONG_MAX;
+ } else if (neg)
+ acc = -acc;
+ if (endptr != 0)
+ *endptr = (char *) (any ? s - 1 : nptr);
+
+ return acc;
+} // strtoll()
+
+static long strtol(const char *nptr, char **endptr, int base)
+{
+ const char *s = nptr;
+ unsigned long acc;
+ int c;
+ unsigned long cutoff;
+ int neg = 0, any, cutlim;
+
+ if (endptr != 0)
+ return -1;
+
+ //
+ // Skip white space and pick up leading +/- sign if any.
+ // If base is 0, allow 0x for hex and 0 for octal, else
+ // assume decimal; if base is already 16, allow 0x.
+ //
+
+ do {
+ c = *s++;
+ } while (isspace(c));
+ if (c == '-') {
+ neg = 1;
+ c = *s++;
+ } else if (c == '+')
+ c = *s++;
+ if ((base == 0 || base == 16) &&
+ c == '0' && (*s == 'x' || *s == 'X')) {
+ c = s[1];
+ s += 2;
+ base = 16;
+ }
+ if (base == 0)
+ base = c == '0' ? 8 : 10;
+
+ //
+ // Compute the cutoff value between legal numbers and illegal
+ // numbers. That is the largest legal value, divided by the
+ // base. An input number that is greater than this value, if
+ // followed by a legal input character, is too big. One that
+ // is equal to this value may be valid or not; the limit
+ // between valid and invalid numbers is then based on the last
+ // digit. For instance, if the range for longs is
+ // [-2147483648..2147483647] and the input base is 10,
+ // cutoff will be set to 214748364 and cutlim to either
+ // 7 (neg==0) or 8 (neg==1), meaning that if we have accumulated
+ // a value > 214748364, or equal but the next digit is > 7 (or 8),
+ // the number is too big, and we will return a range error.
+ //
+ // Set any if any `digits' consumed; make it negative to indicate
+ // overflow.
+ //
+
+ cutoff = neg ? -(unsigned long)LONG_MIN : LONG_MAX;
+ cutlim = cutoff % (unsigned long)base;
+ cutoff /= (unsigned long)base;
+ for (acc = 0, any = 0;; c = *s++) {
+ if (isdigit(c))
+ c -= '0';
+ else if (isalpha(c))
+ c -= isupper(c) ? 'A' - 10 : 'a' - 10;
+ else
+ break;
+ if (c >= base)
+ break;
+ if ((any < 0) || (acc > cutoff) || ((acc == cutoff) && (c > cutlim)))
+ any = -1;
+ else {
+ any = 1;
+ acc *= base;
+ acc += c;
+ }
+ }
+ if (any < 0) {
+ acc = neg ? LONG_MIN : LONG_MAX;
+ } else if (neg)
+ acc = -acc;
+ if (endptr != 0)
+ *endptr = (char *) (any ? s - 1 : nptr);
+
+ return acc;
+} //strtol
+
+int atoi(const char *nptr)
+{
+ int retval;
+
+ retval = (int) strtol(nptr, (char **)0, 10);
+
+ return retval;
+} //atoi
+
+
+long atol(const char *nptr)
+{
+ long retval;
+
+ retval = strtol(nptr, (char **)0, 10);
+
+ return retval;
+} //atol
+
+long long atoll(const char *nptr)
+{
+ long long retval;
+
+ retval = strtoll(nptr, (char **)0, 10);
+
+ return retval;
+} //atoll
+
+unsigned long atoul(const char *nptr)
+{
+ unsigned long retval;
+
+ retval = strtoul(nptr, (char **)0, 10);
+
+ return retval;
+} //atoul
+
+unsigned long long atoull(const char *nptr)
+{
+ unsigned long long retval;
+
+ retval = strtoull(nptr, (char **)0, 10);
+
+ return retval;
+} //atoull
+
diff --git a/cesar/lib/src/bitstream.c b/cesar/lib/src/bitstream.c
new file mode 100644
index 0000000000..b6d783fc6a
--- /dev/null
+++ b/cesar/lib/src/bitstream.c
@@ -0,0 +1,394 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/bitstream.c
+ * \brief Bit stream access using word access.
+ * \ingroup lib
+ */
+#include "common/std.h"
+
+#include "lib/bitstream.h"
+#include "lib/swap.h"
+
+static u32
+bitstream_rol32 (u32 val, uint n)
+{
+ return (n == bitsizeof (u32) ? 0x0 : (val << n));
+}
+
+static uint
+bitstream_read (bitstream_t *ctx, u32 *value, uint nb_bit)
+{
+ uint ret = 0;
+ u32 buf, mask, x;
+
+ for(buf = 0; nb_bit; nb_bit -= x, ret += x)
+ {
+ /* x is bits_left_in_ctx_buf or nb_bit */
+ x = MIN ((bitsizeof(ctx->buf) - ctx->bit_offset), nb_bit);
+ /* create bitmask */
+ mask = bitstream_rol32 (1ul, x) - 1;
+ /* fill local buf */
+ buf |= (((ctx->buf >> ctx->bit_offset) & mask) << ret);
+
+ if(x < nb_bit)
+ {
+ /* not enough bits in ctx->buf, get next word */
+ ctx->buf = *ctx->stream++;
+ ctx->bit_offset = 0;
+ /* if no more bits are available */
+ if(!bitstream_available_bits (ctx))
+ break;
+ }else
+ /* move ctx bit offset forward */
+ ctx->bit_offset += x;
+ }
+
+ *value = buf;
+ return ret;
+}
+
+static uint
+bitstream_write (bitstream_t *ctx, u32 *value, uint nb_bit)
+{
+ u32 mask, x;
+ uint ret = 0;
+
+ for(; nb_bit; nb_bit -= x, ret += x)
+ {
+ /* x is bits_left_in_ctx_buf or nb_bit */
+ x = MIN ((bitsizeof(ctx->buf) - ctx->bit_offset), nb_bit);
+ /* create bitmask */
+ mask = bitstream_rol32 (1ul, x) - 1;
+ /* fill ctx buf */
+ ctx->buf |= (((*value >> ret) & mask) << ctx->bit_offset);
+
+ if(x < nb_bit)
+ {
+ /* Write ctx buf to stream */
+ *ctx->stream++ = ctx->buf;
+ ctx->bit_offset = 0;
+ ctx->buf = 0;
+ /* if no more bits are available */
+ if(!bitstream_available_bits (ctx))
+ break;
+ }
+ else
+ /* move ctx bit offset forward */
+ ctx->bit_offset += x;
+ }
+
+ return ret;
+}
+
+void
+bitstream_init (bitstream_t *ctx, void *data, uint nb_bytes,
+ bitstream_type_t type)
+{
+ ctx->start = (u8*)data;
+
+ /* ensure 32-bit alignment */
+ ctx->stream = (u32*)((u8*)data - ((u32)data & 0x03));
+ ctx->bit_offset = ((u32)data & 0x03) * 8;
+ ctx->buf = ((1ul << ctx->bit_offset) - 1) & *ctx->stream;
+
+ ctx->nb_bytes = nb_bytes;
+ ctx->type = type;
+
+ /* In read mode, load first word */
+ if(ctx->type == BITSTREAM_READ)
+ ctx->buf = *ctx->stream++;
+}
+
+uint
+bitstream_finalise (bitstream_t *ctx)
+{
+ if(ctx->type == BITSTREAM_WRITE
+ && ctx->bit_offset)
+ {
+ /* In write mode, write last buffered word */
+ /* create bitmask */
+ u32 mask = ~(bitstream_rol32 (1ul, ctx->bit_offset) - 1);
+ /* write last word */
+ *ctx->stream = (*ctx->stream & mask) | ctx->buf;
+ return ctx->bit_offset;
+ }
+
+ return 0;
+}
+
+uint
+bitstream_available_bits (bitstream_t *ctx)
+{
+ dbg_assert (ctx);
+
+ uint n = (((u32)ctx->stream <= ((u32)ctx->start + ctx->nb_bytes))
+ ? ((((u32)ctx->start + ctx->nb_bytes) - (u32)(ctx->stream)) * 8)
+ : 0x00000000);
+
+ return (ctx->type == BITSTREAM_READ
+ ? n + (bitsizeof(ctx->buf) - ctx->bit_offset)
+ : n - ctx->bit_offset);
+}
+
+uint
+bitstream_access_8 (bitstream_t *ctx, void *value, uint nb_bit)
+{
+ dbg_assert (ctx);
+ dbg_assert (nb_bit <= 8);
+
+ u32 buf;
+ uint ret;
+
+ if(ctx->type == BITSTREAM_READ)
+ {
+ ret = bitstream_read (ctx, &buf, nb_bit);
+ *(u8*)value = 0xff & buf;
+ return ret;
+ }
+ else
+ {
+ buf = *(u8*)value;
+ return bitstream_write (ctx, &buf, nb_bit);
+ }
+}
+
+uint
+bitstream_access_16 (bitstream_t *ctx, void *value, uint nb_bit)
+{
+ dbg_assert (ctx);
+ dbg_assert (nb_bit <= 16);
+
+ u32 buf;
+ uint ret;
+
+ if(ctx->type == BITSTREAM_READ)
+ {
+ ret = bitstream_read (ctx, &buf, nb_bit);
+ *(u16*)value = 0xffff & buf;
+ return ret;
+ }
+ else
+ {
+ buf = *(u16*)value;
+ return bitstream_write (ctx, &buf, nb_bit);
+ }
+}
+
+uint
+bitstream_access_32 (bitstream_t *ctx, void *value, uint nb_bit)
+{
+ dbg_assert (ctx);
+ dbg_assert (nb_bit <= 32);
+
+ u32 buf;
+ uint ret;
+
+ if(ctx->type == BITSTREAM_READ)
+ {
+ ret = bitstream_read (ctx, &buf, nb_bit);
+ *(u32*)value = buf;
+ return ret;
+ }
+ else
+ {
+ buf = *(u32*)value;
+ return bitstream_write (ctx, &buf, nb_bit);
+ }
+}
+
+uint
+bitstream_access_64 (bitstream_t *ctx, void *value, uint nb_bit)
+{
+ dbg_assert (ctx);
+ dbg_assert (nb_bit <= 64);
+
+ u64 val;
+ u32 buf = 0;
+ uint ret = 0, x;
+
+ if(ctx->type == BITSTREAM_READ)
+ {
+ for(val = 0; nb_bit; nb_bit -= x, ret += x)
+ {
+ x = MIN (bitsizeof(buf), nb_bit);
+ bitstream_read (ctx, &buf, x);
+ val |= (u64)buf << ret;
+ }
+
+ *(u64*)value = val;
+ }
+ else
+ {
+ for(val = *(u64*)value; nb_bit; nb_bit -= x, ret += x)
+ {
+ x = MIN (bitsizeof(buf), nb_bit);
+ buf = (0xffffffff & (val >> ret));
+ bitstream_write (ctx, &buf, x);
+ }
+ }
+
+ return ret;
+}
+
+/* Direct access ops */
+
+uint
+bitstream_direct_read (void *data, uint bit_offset, uint nb_bit)
+{
+ u32 *stream;
+ uint ret = 0;
+ u32 buf, mask, x, y = 0;
+
+ /* ensure 32-bit alignment */
+ data = (u32*)data + (bit_offset >> 5);
+ stream = (u32*)((u8*)data - ((u32)data & 0x03));
+ bit_offset = ((u32)data & 0x03) * 8 + (bit_offset & 0x1f);
+
+ dbg_assert (nb_bit <= 32);
+
+ for(; nb_bit; nb_bit -= x, y += x, bit_offset += x)
+ {
+ /* bit_offset mod bitsizeof (buf) */
+ bit_offset &= (bitsizeof (buf) - 1);
+ /* direct access to buf */
+ buf = *stream++;
+ /* x is bits_left_in_local_buf or nb_bit */
+ x = MIN ((bitsizeof(buf) - bit_offset), nb_bit);
+ /* create bitmask */
+ mask = bitstream_rol32 (1ul, x) - 1;
+ /* set return value */
+ ret |= ((((buf >> bit_offset) & mask) << y));
+ }
+
+ return ret;
+}
+
+u64
+bitstream_direct_read_large (u8 *data, uint bit_offset, uint nb_bit)
+{
+ u64 ret;
+ u32 buf, x, y = 0;
+
+ dbg_assert (nb_bit <= 64);
+
+ for(ret = 0; nb_bit; nb_bit -= x, bit_offset += x, y += x)
+ {
+ x = MIN (bitsizeof(buf), nb_bit);
+ buf = bitstream_direct_read (data, bit_offset, x);
+ ret |= (u64)buf << y;
+ }
+
+ return ret;
+}
+
+void
+bitstream_direct_write (void *data, uint bit_offset, uint value, uint nb_bit)
+{
+ u32 *stream;
+ u32 buf, mask, x, y = 0;
+
+ dbg_assert (nb_bit <= 32);
+
+ /* ensure 32-bit alignment */
+ data = (u32*)data + (bit_offset >> 5);
+ stream = (u32*)((u8*)data - ((u32)data & 0x03));
+ bit_offset = ((u32)data & 0x03) * 8 + (bit_offset & 0x1f);
+
+ for(buf = 0; nb_bit; nb_bit -= x, y += x, bit_offset += x)
+ {
+ /* bit_offset mod bitsizeof (buf) */
+ bit_offset &= (bitsizeof (buf) - 1);
+ /* x is bits_left_in_local_buf or nb_bit */
+ x = MIN ((bitsizeof(buf) - bit_offset), nb_bit);
+ /* create bitmask */
+ mask = bitstream_rol32 (1ul, x) - 1;
+ /* fill local buf */
+ buf |= (((value >> y) & mask) << bit_offset);
+
+ /* direct access to stream */
+ *stream = (*stream & ~(mask << bit_offset)) | buf;
+ stream++;
+ buf = 0;
+ }
+}
+
+void
+bitstream_direct_write_large (u8 *data, uint bit_offset, u64 value,
+ uint nb_bit)
+{
+ u32 buf, x, y = 0;
+
+ dbg_assert (nb_bit <= 64);
+
+ for(buf = 0; nb_bit; nb_bit -= x, bit_offset += x, y += x)
+ {
+ x = MIN (bitsizeof(buf), nb_bit);
+ buf = 0xffffffff & (value >> y);
+ bitstream_direct_write (data, bit_offset, buf, x);
+ }
+}
+
+
+void*
+bitstream_memcpy (void *dest, void *src, size_t len)
+{
+ u32 tmp, x = 0;
+ bitstream_t ctx_r, ctx_w;
+
+ bitstream_init (&ctx_r, src, len, BITSTREAM_READ);
+ bitstream_init (&ctx_w, dest, len, BITSTREAM_WRITE);
+
+ for(len *= 8; len; len -= x)
+ {
+ x = MIN (bitsizeof (tmp), len);
+ bitstream_access (&ctx_r, &tmp, x);
+ bitstream_access (&ctx_w, &tmp, x);
+ }
+
+ bitstream_finalise (&ctx_r);
+ bitstream_finalise (&ctx_w);
+ return dest;
+}
+
+/**
+ * Compare two buffers and return true if the buffers are equals
+ * \param s1 the first buffer to compare.
+ * \param s2 the second buffer to compare.
+ * \param len the length in bytes to compare the buffers.
+ * \return true if equal, false otherwise.
+ */
+bool
+bitstream_memcmp (void *s1, void *s2, size_t len)
+{
+ u32 x = 0;
+ uint s1_data, s2_data;
+ bitstream_t ctx_r1, ctx_r2;
+
+ bitstream_init (&ctx_r1, s1, len, BITSTREAM_READ);
+ bitstream_init (&ctx_r2, s2, len, BITSTREAM_READ);
+
+ for(len *= 8; len; len -= x)
+ {
+ x = MIN (bitsizeof (s1_data), len);
+ bitstream_access (&ctx_r1, &s1_data, x);
+ bitstream_access (&ctx_r2, &s2_data, x);
+
+ if (s1_data != s2_data)
+ {
+ bitstream_finalise (&ctx_r1);
+ bitstream_finalise (&ctx_r2);
+
+ return false;
+ }
+ }
+
+ bitstream_finalise (&ctx_r1);
+ bitstream_finalise (&ctx_r2);
+ return true;
+}
diff --git a/cesar/lib/src/blk.c b/cesar/lib/src/blk.c
new file mode 100644
index 0000000000..069bde958a
--- /dev/null
+++ b/cesar/lib/src/blk.c
@@ -0,0 +1,244 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/blk.c
+ * \brief 512 byte memory blocks.
+ * \ingroup lib
+ *
+ * \todo This is a temporary implementation using malloc and no optimisations.
+ */
+#include "common/std.h"
+
+#include "lib/blk.h"
+#include "hal/arch/arch.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define REFCNT(blk) ((int *) ((u8 *) (blk) - BLK_REFCNT_SIZE))
+#define TO_BLK(data) ((blk_t *) ((u8 *) (data) + BLK_SIZE + BLK_REFCNT_SIZE))
+
+/** Structure to accumulate the several actions type on blocks. */
+struct blocks_t
+{
+ /** Incremented when a new blocks has been allocated. */
+ uint allocated;
+ /** Incremented when a block has been freed. */
+ uint freed;
+ /** Incremented when a new reference on a block has been added. */
+ uint referenced;
+ /** Incremented when a release action on a block has been done. */
+ uint released;
+};
+typedef struct blocks_t blocks_t;
+
+blocks_t blocks;
+
+enum {
+ /** Magic code used for destructor-less allocations.
+ * 'o', 'b', 'j', <odd number>. This magic should be odd to not collide
+ * with a pointer. */
+ BLK_OBJ_MAGIC = 0x6f626aa5
+};
+
+/** Block descriptor for descriptor-less allocations. */
+struct blk_obj_t
+{
+ /** Magic code in place of next pointer. */
+ u32 magic;
+ /** Pointer to data. */
+ u8 *data;
+ /** Destructor function pointer or NULL. */
+ blk_destructor_t destructor;
+ /** Reserved for future usage. */
+ u32 reserved;
+};
+typedef struct blk_obj_t blk_obj_t;
+
+blk_t *
+blk_alloc_desc_ (void_FL)
+{
+ u8 *data = malloc (BLK_SIZE + BLK_REFCNT_SIZE + BLK_DESC_SIZE);
+ if (!data)
+ dbg_fatal ("exhausted virtual memory");
+ blk_t *blk = TO_BLK (data);
+ dbg_invalid_ptr (blk->next);
+ blk->data = data;
+ *REFCNT(blk) = 1;
+ blocks.allocated++;
+ blocks.referenced++;
+ restrack_create (NULL, blk, _fl_, 1);
+ return blk;
+}
+
+blk_t *
+blk_alloc_desc_range_ (uint n, blk_t **last __FL)
+{
+ blk_t *first, *b;
+ dbg_assert (n);
+ dbg_assert_ptr (last);
+ first = b = blk_alloc_desc_ (_fl);
+ for (n--; n; n--)
+ {
+ b->next = blk_alloc_desc_ (_fl);
+ b = b->next;
+ }
+ *last = b;
+ return first;
+}
+
+static void
+blk_free_desc_ (blk_t *blk __FL)
+{
+ dbg_assert_ptr (blk);
+ dbg_assert (TO_BLK (blk->data) == blk);
+ restrack_destroy (NULL, blk, _fl_, 0);
+ blocks.freed++;
+ free (blk->data);
+}
+
+void
+blk_addref_desc_ (blk_t *blk __FL)
+{
+ dbg_assert_ptr (blk);
+ dbg_assert (TO_BLK (blk->data) == blk);
+ arch_atomic_add (REFCNT (blk), 1);
+ restrack_update (NULL, blk, _fl_, 1);
+ blocks.referenced++;
+}
+
+void
+blk_addref_desc_range_ (blk_t *first, blk_t *last __FL)
+{
+ blk_t *b;
+ for (b = first; b != last; b = b->next)
+ {
+ blk_addref_desc_ (b __fl);
+ }
+ blk_addref_desc_ (b __fl);
+}
+
+void
+blk_addref_desc_range_nb_ (blk_t *first, uint n __FL)
+{
+ dbg_assert (n);
+ blk_t *b;
+ uint i;
+ for (b = first, i = n; i; b = b->next, i--)
+ {
+ blk_addref_desc_ (b __fl);
+ }
+}
+
+void
+blk_release_desc_ (blk_t *blk __FL)
+{
+ dbg_assert_ptr (blk);
+ dbg_assert (TO_BLK (blk->data) == blk);
+ dbg_assert (((blk_obj_t *) blk)->magic != BLK_OBJ_MAGIC);
+ dbg_assert (REFCNT (blk) != 0);
+ restrack_update (NULL, blk, _fl_, -1);
+ blocks.released++;
+ if (arch_atomic_add (REFCNT (blk), -1) == 0)
+ {
+ blk_free_desc_ (blk __fl);
+ }
+}
+
+void
+blk_release_desc_range_ (blk_t *first, blk_t *last __FL)
+{
+ blk_t *b, *bn;
+ for (b = first; b != last; b = bn)
+ {
+ bn = b->next;
+ blk_release_desc_ (b __fl);
+ }
+ blk_release_desc_ (b __fl);
+}
+
+void
+blk_release_desc_range_nb_ (blk_t *first, uint n __FL)
+{
+ dbg_assert (n);
+ blk_t *b, *bn;
+ uint i;
+ for (b = first, i = n; i; b = bn, i--)
+ {
+ bn = b->next;
+ blk_release_desc_ (b __fl);
+ }
+}
+
+void *
+blk_alloc_ (void_FL)
+{
+ return blk_new_ (NULL __fl);
+}
+
+void *
+blk_new_ (blk_destructor_t destructor __FL)
+{
+ blk_t *blk = blk_alloc_desc_ (_fl);
+ blk_obj_t *obj = (blk_obj_t *) blk;
+ obj->magic = BLK_OBJ_MAGIC;
+ obj->destructor = destructor;
+ return blk->data;
+}
+
+void *
+blk_alloc_zero_ (void_FL)
+{
+ void *data = blk_alloc_ (_fl);
+ memset (data, 0, BLK_SIZE);
+ return data;
+}
+
+void
+blk_addref_ (void *data __FL)
+{
+ dbg_assert_ptr (data);
+ blk_t *blk = TO_BLK (data);
+ dbg_assert (((blk_obj_t *) blk)->magic == BLK_OBJ_MAGIC);
+ blk_addref_desc_ (blk __fl);
+}
+
+void
+blk_release_ (void *data __FL)
+{
+ dbg_assert_ptr (data);
+ blk_obj_t *obj = (blk_obj_t *) TO_BLK (data);
+ dbg_assert_ptr (obj);
+ dbg_assert (obj->magic == BLK_OBJ_MAGIC);
+ restrack_update (NULL, obj, _fl_, -1);
+ blocks.released++;
+ if (arch_atomic_add (REFCNT (obj), -1) == 0)
+ {
+ if (obj->destructor)
+ obj->destructor (data);
+ blk_free_desc_ ((blk_t *) obj __fl);
+ }
+}
+
+bool
+blk_check_memory (void)
+{
+ return restrack_check ()
+ && blocks.allocated == blocks.freed
+ && blocks.referenced == blocks.released;
+}
+
+void
+blk_print_memory (void)
+{
+ fprintf (stderr, "[MEM STATE] Allocated : %d\t Freed : %d\t Referenced : %d\t Released : %d\n",
+ blocks.allocated, blocks.freed,
+ blocks.referenced, blocks.released
+ );
+}
diff --git a/cesar/lib/src/circular_buffer.c b/cesar/lib/src/circular_buffer.c
new file mode 100644
index 0000000000..1f5a1851e9
--- /dev/null
+++ b/cesar/lib/src/circular_buffer.c
@@ -0,0 +1,101 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2008 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/circular_buffer.c
+ * \brief Circular buffer list.
+ * \ingroup lib
+ *
+ * Provides a circular buffer list API.
+ * Reserve the real size of the buffer just after the declaration of the
+ * circular buffer to not have some memory problems.
+ */
+#include "common/std.h"
+#include "lib/circular_buffer.h"
+
+/**
+ * Initialize the buffer address list
+ *
+ * \param list the buffer address list to initiliaze
+ * \param buffer the circular buffer to use.
+ * \param number_slots the quantity of slots.
+ */
+void
+circular_buffer_init (circular_buffer_t *list, void *buffer, uint number_slots)
+{
+ dbg_assert (list);
+
+ list->num_slots = number_slots;
+ list->buffer = buffer;
+ list->head = 0;
+ list->tail = 0;
+ list->nb_elements = 0;
+}
+
+/**
+ * Add an address to the buffer address buffer list
+ *
+ * \param ctx the ctx containing the list.
+ * \param address the address to add to the list
+ * \param number_of_slots the quantity of address it can keep in the list.
+ *
+ * \return true if the buffer had been added, false otherwise
+ */
+bool
+circular_buffer_add (circular_buffer_t *ctx, void *address)
+{
+ dbg_assert (ctx);
+
+ if (ctx->nb_elements < ctx->num_slots)
+ {
+ ctx->buffer[ctx->tail] = address;
+ ctx->tail ++;
+ ctx->nb_elements ++;
+ if (ctx->tail > ctx->num_slots - 1)
+ {
+ ctx->tail = 0;
+ }
+ return true;
+ }
+ return false;
+}
+
+/**
+ * Peek the first element of the list without removing it.
+ *
+ * \param ctx the context.
+ */
+void*
+circular_buffer_peek (circular_buffer_t *ctx)
+{
+ return ctx->buffer[ctx->head];
+}
+
+/**
+ * Get the current address and go to the next one.
+ *
+ * \param ctx the ctx containing the list.
+ * \param number_of_slots the quantity of address it can keep in the list.
+ */
+void*
+circular_buffer_get (circular_buffer_t *ctx)
+{
+ void *buffer = NULL;
+
+ if (ctx->nb_elements != 0)
+ {
+ buffer = ctx->buffer[ctx->head];
+ ctx->head ++;
+ ctx->nb_elements --;
+ if (ctx->head > ctx->num_slots - 1)
+ {
+ ctx->head = 0;
+ }
+ }
+ return buffer;
+}
+
diff --git a/cesar/lib/src/crc.c b/cesar/lib/src/crc.c
new file mode 100644
index 0000000000..df509c4d38
--- /dev/null
+++ b/cesar/lib/src/crc.c
@@ -0,0 +1,193 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/crc.c
+ * \brief General Cyclic Redundancy Code utilities.
+ * \ingroup lib
+ */
+#include "common/std.h"
+
+#include "lib/crc.h"
+
+/**
+ * Reflect the width lowest significant bits in word.
+ * \param word the word to reflect
+ * \param width the number of bits
+ * \return the reflected word
+ */
+extern inline
+u32
+crc_reflect (u32 word, uint width)
+{
+ u32 newword;
+ uint i;
+ /* Please compiler, optimise and inline this or I will have to do it
+ * myself: */
+ newword = 0;
+ for (i = 0; i < width; i++)
+ {
+ if (word & (1 << i))
+ newword |= 1 << (width - i - 1);
+ }
+ return newword;
+}
+
+void
+crc_init (crc_t *ctx)
+{
+ /* OK, for the moment, only support a subset of the general model. */
+ dbg_assert_print ((ctx->width == 32 || ctx->width == 24
+ || ctx->width == 16 || ctx->width == 8)
+ && (ctx->refin == true || ctx->refin == false)
+ && (ctx->refout == true || ctx->refout == false),
+ "unsupported model values");
+ dbg_assert (ctx->generator);
+ dbg_assert (ctx->table.t32);
+ /* Compute initial register value. */
+ u32 generator = ctx->generator;
+ u32 reg_init = ctx->init;
+ if (ctx->refin)
+ {
+ generator = crc_reflect (generator, ctx->width);
+ reg_init = crc_reflect (reg_init, ctx->width);
+ }
+ ctx->reg_init = reg_init;
+ /* Generate table. */
+ uint i, b;
+ u32 reg;
+ u32 top = 1 << (ctx->width - 1);
+ for (i = 0; i < 256; i++)
+ {
+ if (ctx->refin)
+ {
+ reg = i;
+ for (b = 0; b < 8; b++)
+ {
+ if (reg & 1)
+ reg = (reg >> 1) ^ generator;
+ else
+ reg >>= 1;
+ }
+ }
+ else
+ {
+ reg = i << (ctx->width - 8);
+ for (b = 0; b < 8; b++)
+ {
+ if (reg & top)
+ reg = (reg << 1) ^ generator;
+ else
+ reg <<= 1;
+ }
+ reg &= (1 << (ctx->width - 1) << 1) - 1;
+ }
+ switch (ctx->width)
+ {
+ case 32:
+ case 24:
+ ctx->table.t32[i] = reg;
+ break;
+ case 16:
+ ctx->table.t16[i] = reg;
+ break;
+ case 8:
+ ctx->table.t8[i] = reg;
+ break;
+ }
+ }
+}
+
+u32
+crc_compute_block (const crc_t *ctx, const u8 *block, uint block_size)
+{
+ dbg_assert (ctx);
+ dbg_assert (block || block_size == 0);
+ u32 reg;
+ reg = crc_compute_begin (ctx);
+ reg = crc_compute_continue_block (ctx, reg, block, block_size);
+ reg = crc_compute_end (ctx, reg);
+ return reg;
+}
+
+u32
+crc_compute_begin (const crc_t *ctx)
+{
+ dbg_assert (ctx);
+ return ctx->reg_init;
+}
+
+u32
+crc_compute_continue_block (const crc_t *ctx, u32 reg, const u8 *block,
+ uint block_size)
+{
+ const u32 *t32;
+ const u16 *t16;
+ const u8 *t8;
+ dbg_assert (ctx);
+ dbg_assert (block || block_size == 0);
+ if (ctx->refin)
+ {
+ switch (ctx->width)
+ {
+ case 32:
+ case 24:
+ t32 = ctx->table.t32;
+ while (block_size--)
+ reg = (reg >> 8) ^ t32[(reg ^ *block++) & 0xff];
+ break;
+ case 16:
+ t16 = ctx->table.t16;
+ while (block_size--)
+ reg = ((reg >> 8) ^ t16[(reg ^ *block++) & 0xff]) & 0xffff;
+ break;
+ case 8:
+ t8 = ctx->table.t8;
+ while (block_size--)
+ reg = t8[reg ^ *block++];
+ break;
+ }
+ }
+ else
+ {
+ switch (ctx->width)
+ {
+ case 32:
+ t32 = ctx->table.t32;
+ while (block_size--)
+ reg = (reg << 8) ^ t32[(reg >> 24) ^ *block++];
+ break;
+ case 24:
+ t32 = ctx->table.t32;
+ while (block_size--)
+ reg = ((reg << 8) ^ t32[(reg >> 16) ^ *block++]) & 0xffffff;
+ break;
+ case 16:
+ t16 = ctx->table.t16;
+ while (block_size--)
+ reg = ((reg << 8) ^ t16[(reg >> 8) ^ *block++]) & 0xffff;
+ break;
+ case 8:
+ t8 = ctx->table.t8;
+ while (block_size--)
+ reg = t8[reg ^ *block++];
+ break;
+ }
+ }
+ return reg;
+}
+
+u32
+crc_compute_end (const crc_t *ctx, u32 reg)
+{
+ dbg_assert (ctx);
+ if (ctx->refin != ctx->refout)
+ return crc_reflect (reg, ctx->width) ^ ctx->xorout;
+ else
+ return reg ^ ctx->xorout;
+}
+
diff --git a/cesar/lib/src/dbg.c b/cesar/lib/src/dbg.c
new file mode 100644
index 0000000000..f4a932dc38
--- /dev/null
+++ b/cesar/lib/src/dbg.c
@@ -0,0 +1,71 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/dbg.c
+ * \brief Debug functions.
+ * \ingroup lib
+ */
+#include "common/std.h"
+
+#include <stdio.h>
+#include <stdarg.h>
+#include <stdlib.h>
+
+#if DEBUG
+
+# if CONFIG_DEBUG_FATAL_CATCH
+int dbg_fatal_try_level_;
+char dbg_fatal_text_[2048];
+# endif
+
+void
+dbg_assert_fail (const char *assertion, const char *file, uint line,
+ const char *function)
+{
+ dbg_fatal (DBG_ASSERT_FMT_ "%s", file, line, function,
+ assertion);
+}
+
+void
+dbg_assert_print_fail (const char *fmt, ...)
+{
+ va_list ap;
+ va_start (ap, fmt);
+ dbg_vfatal (fmt, ap);
+ va_end (ap);
+}
+
+#endif /* DEBUG */
+
+void
+dbg_fatal (const char *fmt, ...)
+{
+ va_list ap;
+ va_start (ap, fmt);
+ dbg_vfatal (fmt, ap);
+ va_end (ap);
+}
+
+void
+dbg_vfatal (const char *fmt, va_list ap)
+{
+#if DEBUG && CONFIG_DEBUG_FATAL_CATCH
+ if (dbg_fatal_try_level_)
+ {
+ vsnprintf (dbg_fatal_text_, sizeof (dbg_fatal_text_), fmt, ap);
+ try_throw (TRY_CODE_FATAL);
+ }
+ else
+#endif
+ {
+ vfprintf (stderr, fmt, ap);
+ fputc ('\n', stderr);
+ abort ();
+ }
+}
+
diff --git a/cesar/lib/src/heap.c b/cesar/lib/src/heap.c
new file mode 100644
index 0000000000..af8c83f2ca
--- /dev/null
+++ b/cesar/lib/src/heap.c
@@ -0,0 +1,62 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/heap.c
+ * \brief Heap common functions.
+ * \ingroup lib
+ *
+ * Provide common utilities functions for heaps.
+ */
+#include "common/std.h"
+
+#include "lib/heap.h"
+
+void
+heap_init (heap_t *heap, heap_node_less_t less)
+{
+ dbg_assert (heap);
+ heap->root = NULL;
+ heap->less = less;
+}
+
+void
+heap_adjust (heap_t *heap, heap_node_t *node)
+{
+ dbg_assert (heap);
+ dbg_assert (node);
+ /* If position should actually change. */
+ if ((node->left && heap->less (node->left, node))
+ || (node->right && heap->less (node->right, node))
+ || (node->father && heap->less (node, node->father)))
+ {
+ heap_remove (heap, node);
+ heap_insert (heap, node);
+ }
+}
+
+void
+heap_merge (heap_t *heap_to, heap_t *heap_from)
+{
+ dbg_assert (heap_to && heap_to->less);
+ dbg_assert (heap_from && heap_from->less);
+ dbg_assert_print (heap_to->less == heap_from->less, "incompatible heaps");
+ heap_to->root = heap_node_merge (heap_to->root, heap_from->root,
+ heap_to->less);
+ heap_from->root = NULL;
+}
+
+bool
+heap_node_u32_less_mod2p32 (heap_node_t *left, heap_node_t *right)
+{
+ dbg_assert (left);
+ dbg_assert (right);
+ heap_node_u32_t *l = PARENT_OF (heap_node_u32_t, node, left);
+ heap_node_u32_t *r = PARENT_OF (heap_node_u32_t, node, right);
+ return less_mod2p32 (l->key, r->key);
+}
+
diff --git a/cesar/lib/src/leftheap.c b/cesar/lib/src/leftheap.c
new file mode 100644
index 0000000000..8f7c6d3ad8
--- /dev/null
+++ b/cesar/lib/src/leftheap.c
@@ -0,0 +1,159 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/leftheap.c
+ * \brief Leftist heaps.
+ * \ingroup lib
+ */
+#include "common/std.h"
+
+#include "lib/heap.h"
+
+void
+heap_node_init (heap_node_t *node)
+{
+ node->father = NULL;
+ node->left = node->right = NULL;
+ node->null_path_length = 1;
+}
+
+heap_node_t *
+heap_node_merge (heap_node_t *root1, heap_node_t *root2,
+ heap_node_less_t less)
+{
+ heap_node_t *h, *h2, *root;
+ dbg_assert (!root1 || !root1->father);
+ dbg_assert (!root2 || !root2->father);
+ dbg_assert (less);
+ /* Trivial cases. */
+ if (!root1)
+ return root2;
+ else if (!root2)
+ return root1;
+ /* Initialise. */
+ if (less (root1, root2))
+ {
+ h = root1;
+ h2 = root2;
+ }
+ else
+ {
+ h = root2;
+ h2 = root1;
+ }
+ root = h;
+ /* Merge along the right paths. */
+ while (h2)
+ {
+ if (!h->right || less (h2, h->right))
+ {
+ XCH (h2, h->right);
+ h->right->father = h;
+ }
+ h = h->right;
+ }
+ /* Now walk up the path to fix balance. */
+ dbg_assert (h);
+ for (; h; h = h->father)
+ {
+ uint lnpl = h->left ? h->left->null_path_length : 0;
+ uint rnpl = h->right ? h->right->null_path_length : 0;
+ if (lnpl < rnpl)
+ {
+ XCH (h->left, h->right);
+ }
+ h->null_path_length = 1 + MIN (lnpl, rnpl);
+ }
+ return root;
+}
+
+void
+heap_insert (heap_t *heap, heap_node_t *node)
+{
+ dbg_assert (heap);
+ dbg_assert (node);
+ heap->root = heap_node_merge (heap->root, node, heap->less);
+}
+
+void
+heap_remove_root (heap_t *heap)
+{
+ heap_node_t *root;
+ dbg_assert (heap);
+ dbg_assert (!heap_empty (heap));
+ root = heap->root;
+ if (root->left)
+ root->left->father = NULL;
+ if (root->right)
+ root->right->father = NULL;
+ heap->root = heap_node_merge (root->left, root->right, heap->less);
+ root->father = root->left = root->right = NULL;
+ root->null_path_length = 1;
+}
+
+void
+heap_remove (heap_t *heap, heap_node_t *node)
+{
+ heap_node_t **r;
+ dbg_assert (heap);
+ dbg_assert (!heap_empty (heap));
+ dbg_assert (node);
+ /* Where to store the merged tree? */
+ if (!node->father)
+ {
+ dbg_assert (node == heap->root);
+ r = &heap->root;
+ }
+ else if (node->father->right == node)
+ {
+ r = &node->father->right;
+ }
+ else
+ {
+ dbg_assert (node->father->left == node);
+ r = &node->father->left;
+ }
+ /* Need NULL father pointer. */
+ if (node->left)
+ node->left->father = NULL;
+ if (node->right)
+ node->right->father = NULL;
+ /* Merge left and right subtree. */
+ *r = heap_node_merge (node->left, node->right, heap->less);
+ if (*r)
+ (*r)->father = node->father;
+ /**
+ * We can not just replace the removed node with a merge of its right and
+ * left subtrees because this may change null_path_length. There is
+ * several solutions:
+ * - walk up the tree to fix balance,
+ * - instead of one merge, do two merges, first with left subtree, then
+ * right subtree,
+ * - ignore this structure break...
+ *
+ * Here the first solution is chosen.
+ */
+ heap_node_t *h;
+ for (h = node->father; h; h = h->father)
+ {
+ uint lnpl = h->left ? h->left->null_path_length : 0;
+ uint rnpl = h->right ? h->right->null_path_length : 0;
+ if (lnpl < rnpl)
+ {
+ XCH (h->left, h->right);
+ }
+ uint nnpl = 1 + MIN (lnpl, rnpl);
+ if (h->null_path_length == nnpl)
+ break;
+ h->null_path_length = nnpl;
+ }
+ /* Detach the removed node. */
+ node->father = node->left = node->right = NULL;
+ node->null_path_length = 1;
+}
+
diff --git a/cesar/lib/src/list.c b/cesar/lib/src/list.c
new file mode 100644
index 0000000000..61771b2c53
--- /dev/null
+++ b/cesar/lib/src/list.c
@@ -0,0 +1,181 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/list.c
+ * \brief Double linked list.
+ * \ingroup lib
+ */
+#include "common/std.h"
+#include "lib/list.h"
+
+void
+list_init (list_t *list)
+{
+ dbg_assert (list);
+ list_init_node (&list->nil);
+}
+
+void
+list_init_node (list_node_t *node)
+{
+ dbg_assert (node);
+ node->next = node->prev = node;
+}
+
+list_node_t *
+list_begin (list_t *list)
+{
+ dbg_assert (list);
+ return list->nil.next;
+}
+
+list_node_t *
+list_end (list_t *list)
+{
+ dbg_assert (list);
+ return &list->nil;
+}
+
+list_node_t *
+list_rbegin (list_t *list)
+{
+ dbg_assert (list);
+ return list->nil.prev;
+}
+
+list_node_t *
+list_rend (list_t *list)
+{
+ dbg_assert (list);
+ return &list->nil;
+}
+
+list_node_t *
+list_next (list_node_t *node)
+{
+ dbg_assert (node);
+ return node->next;
+}
+
+list_node_t *
+list_prev (list_node_t *node)
+{
+ dbg_assert (node);
+ return node->prev;
+}
+
+bool
+list_empty (list_t *list)
+{
+ dbg_assert (list);
+ return list->nil.next == &list->nil;
+}
+
+void
+list_push (list_t *list, list_node_t *node)
+{
+ dbg_assert (list);
+ dbg_assert (node && node->next == node && node->prev == node);
+ node->prev = list->nil.prev;
+ node->next = &list->nil;
+ list->nil.prev->next = node;
+ list->nil.prev = node;
+}
+
+void
+list_unshift (list_t *list, list_node_t *node)
+{
+ dbg_assert (list);
+ dbg_assert (node && node->next == node && node->prev == node);
+ node->next = list->nil.next;
+ node->prev = &list->nil;
+ list->nil.next->prev = node;
+ list->nil.next = node;
+}
+
+list_node_t *
+list_pop (list_t *list)
+{
+ list_node_t *node;
+ dbg_assert (list && !list_empty (list));
+ node = list->nil.prev;
+ dbg_assert (node && node->prev && node->next == &list->nil);
+ list->nil.prev = node->prev;
+ node->prev->next = &list->nil;
+ node->next = node->prev = node;
+ return node;
+}
+
+list_node_t *
+list_shift (list_t *list)
+{
+ list_node_t *node;
+ dbg_assert (list && !list_empty (list));
+ node = list->nil.next;
+ dbg_assert (node && node->next && node->prev == &list->nil);
+ list->nil.next = node->next;
+ node->next->prev = &list->nil;
+ node->next = node->prev = node;
+ return node;
+}
+
+void
+list_remove (list_t *list, list_node_t *node)
+{
+ dbg_assert (list && !list_empty (list));
+ dbg_assert (node && node->next && node->next != node
+ && node->prev && node->prev != node);
+ node->prev->next = node->next;
+ node->next->prev = node->prev;
+ node->next = node->prev = node;
+}
+
+void
+list_insert (list_t *list, list_node_t *before, list_node_t *node)
+{
+ dbg_assert (list);
+ dbg_assert (before && before->prev);
+ dbg_assert (node && node->next == node && node->prev == node);
+ node->next = before;
+ node->prev = before->prev;
+ before->prev->next = node;
+ before->prev = node;
+}
+
+void
+list_push_range (list_t *to, list_t *from,
+ list_node_t *first, list_node_t *last)
+{
+ dbg_assert (to);
+ list_insert_range (to, from, &to->nil, first, last);
+}
+
+void
+list_unshift_range (list_t *to, list_t *from,
+ list_node_t *first, list_node_t *last)
+{
+ dbg_assert (to);
+ list_insert_range (to, from, to->nil.next, first, last);
+}
+
+void
+list_insert_range (list_t *to, list_t *from, list_node_t *before,
+ list_node_t *first, list_node_t *last)
+{
+ list_node_t *before_last;
+ dbg_assert (to && from && !list_empty (from));
+ dbg_assert (before && first && last);
+ first->prev->next = last;
+ before_last = last->prev;
+ last->prev = first->prev;
+ first->prev = before->prev;
+ before_last->next = before;
+ before->prev->next = first;
+ before->prev = before_last;
+}
+
diff --git a/cesar/lib/src/mt19937ar.c b/cesar/lib/src/mt19937ar.c
new file mode 100644
index 0000000000..2268a6ed2d
--- /dev/null
+++ b/cesar/lib/src/mt19937ar.c
@@ -0,0 +1,260 @@
+/* Cesar project {{{
+ *
+ * THIS FILE is Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji
+ * Nishimura. Please see below for more information.
+ *
+ * Include modification by Spidcom for constant time calls.
+ *
+ * }}} */
+/**
+ * \file lib/src/mt19937ar.c
+ * \brief Random Number Generator implemented by MT19937.
+ * \ingroup lib
+ *
+ * Please do not update formating or indent so that diffing is easy.
+ */
+
+/*
+ A C-program for MT19937, with initialization improved 2002/1/26.
+ Coded by Takuji Nishimura and Makoto Matsumoto.
+
+ Before using, initialize the state by using init_genrand(seed)
+ or init_by_array(init_key, key_length).
+
+ Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
+ All rights reserved.
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions
+ are met:
+
+ 1. Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+
+ 2. Redistributions in binary form must reproduce the above copyright
+ notice, this list of conditions and the following disclaimer in the
+ documentation and/or other materials provided with the distribution.
+
+ 3. The names of its contributors may not be used to endorse or promote
+ products derived from this software without specific prior written
+ permission.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+
+ Any feedback is very welcome.
+ http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
+ email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
+*/
+#include "common/std.h"
+#include "lib/rnd.h"
+
+/* Do not generate N words at one time in order to limit maximum latency. */
+#define LIB_MT_BURST 0
+
+/* Period parameters */
+#define N LIB_MT_N
+#define M 397
+#define MATRIX_A 0x9908b0dfUL /* constant vector a */
+#define UPPER_MASK 0x80000000UL /* most significant w-r bits */
+#define LOWER_MASK 0x7fffffffUL /* least significant r bits */
+
+/* Use context instead of global variables. */
+#define mt (ctx->state)
+#define mti (ctx->state_index)
+
+/**
+ * Initialise a random number generator context.
+ * \param ctx the rnd context to initialise.
+ * \param seed 32 bit random seed.
+ */
+void
+lib_rnd_init (lib_rnd_t *ctx, u32 seed)
+{
+ dbg_assert (ctx);
+ mt[0]= seed & 0xffffffffUL;
+ for (mti=1; mti<N; mti++) {
+ mt[mti] =
+ (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
+ /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
+ /* In the previous versions, MSBs of the seed affect */
+ /* only MSBs of the array mt[]. */
+ /* 2002/01/09 modified by Makoto Matsumoto */
+ mt[mti] &= 0xffffffffUL;
+ /* for >32 bit machines */
+ }
+}
+
+/**
+ * Initialise a random number generator context using an array in order to
+ * use a greater initialisation space.
+ * \param ctx the rnd context to initialise.
+ * \param init_key the array.
+ * \param key_length the array length.
+ */
+void
+lib_rnd_init_by_array (lib_rnd_t *ctx, const u32 init_key[], int key_length)
+{
+ int i, j, k;
+ dbg_assert (ctx);
+ dbg_assert (init_key);
+ dbg_assert (key_length > 0);
+ lib_rnd_init(ctx, 19650218UL);
+ i=1; j=0;
+ k = (N>key_length ? N : key_length);
+ for (; k; k--) {
+ mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))
+ + init_key[j] + j; /* non linear */
+ mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
+ i++; j++;
+ if (i>=N) { mt[0] = mt[N-1]; i=1; }
+ if (j>=key_length) j=0;
+ }
+ for (k=N-1; k; k--) {
+ mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL))
+ - i; /* non linear */
+ mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
+ i++;
+ if (i>=N) { mt[0] = mt[N-1]; i=1; }
+ }
+
+ mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */
+}
+
+/**
+ * Generates a random number on [0,0xffffffff]-interval.
+ * \param ctx the rnd context.
+ * \return the random number.
+ */
+u32
+lib_rnd32 (lib_rnd_t *ctx)
+{
+ unsigned long y;
+ static const unsigned long mag01[2]={0x0UL, MATRIX_A};
+ /* mag01[x] = x * MATRIX_A for x=0,1 */
+
+ dbg_assert (ctx);
+
+#if LIB_MT_BURST
+ if (mti >= N) { /* generate N words at one time */
+ int kk;
+
+ if (mti == N+1) /* if init_genrand() has not been called, */
+ init_genrand(5489UL); /* a default initial seed is used */
+
+ for (kk=0;kk<N-M;kk++) {
+ y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
+ mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
+ }
+ for (;kk<N-1;kk++) {
+ y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
+ mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
+ }
+ y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
+ mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
+
+ mti = 0;
+ }
+#else
+ if (mti >= N)
+ mti = 0;
+ if (mti < N - M)
+ {
+ y = (mt[mti]&UPPER_MASK)|(mt[mti+1]&LOWER_MASK);
+ mt[mti] = mt[mti+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
+ }
+ else if (mti < N - 1)
+ {
+ y = (mt[mti]&UPPER_MASK)|(mt[mti+1]&LOWER_MASK);
+ mt[mti] = mt[mti+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
+ }
+ else
+ {
+ y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
+ mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
+ }
+#endif
+
+ y = mt[mti++];
+
+ /* Tempering */
+ y ^= (y >> 11);
+ y ^= (y << 7) & 0x9d2c5680UL;
+ y ^= (y << 15) & 0xefc60000UL;
+ y ^= (y >> 18);
+
+ return y;
+}
+
+/* End of MT19937 code. */
+#include "config/rnd/buffer/optimise.h"
+
+/**
+ * Generates a random number on [0,bound-1]-interval.
+ * \param ctx the rnd context.
+ * \param bound upper bound.
+ * \return the random number.
+ */
+uint
+lib_rnd_uniform (lib_rnd_t *ctx, uint bound)
+{
+ uint up;
+ uint n;
+ dbg_assert (ctx);
+ dbg_assert (bound != 0);
+ /* This is not optimal if bound is a power of two, but it is harder to
+ * divide 2^32. */
+ up = 0xffffffff - (0xffffffff % bound);
+ do {
+ n = lib_rnd32 (ctx);
+ } while (n > up);
+ return n % bound;
+}
+
+/**
+ * Fill a buffer with random data.
+ * \param ctx the rnd context
+ * \param buf buffer to fill
+ * \param buf_size buffer size
+ *
+ * The buffer need not to be word aligned.
+ *
+ * This will generate a reproducible buffer over big and little endian
+ * machines.
+ */
+void
+lib_rnd_buffer (lib_rnd_t *ctx, u8 *buf, uint buf_size)
+{
+ dbg_assert (ctx);
+ dbg_assert_ptr (buf);
+#if CONFIG_RND_BUFFER_OPTIMISE && !DEFS_BIG_ENDIAN
+ /* Not needed yet. */
+ dbg_assert_print (0, "not implemented");
+#else /* !(CONFIG_RND_BUFFER_OPTIMISE && !DEFS_BIG_ENDIAN) */
+ u32 r = 0;
+ uint rb = 0;
+ u8 *p = buf;
+ u8 *pend = buf + buf_size;
+ while (p != pend)
+ {
+ if (rb == 0)
+ {
+ r = lib_rnd32 (ctx);
+ rb = 4;
+ }
+ *p++ = r & 0xff;
+ r >>= 8;
+ rb--;
+ }
+#endif /* !(CONFIG_RND_BUFFER_OPTIMISE && !DEFS_BIG_ENDIAN) */
+}
diff --git a/cesar/lib/src/read_word.c b/cesar/lib/src/read_word.c
new file mode 100644
index 0000000000..27145c91af
--- /dev/null
+++ b/cesar/lib/src/read_word.c
@@ -0,0 +1,129 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/read_word.c
+ * \brief Read a word from the memory aligned on an integer address.
+ * \ingroup lib
+ *
+ * Allows the system to get a value from the memory reading it word by word
+ * and returning the value request from the user.
+ *
+ * Exemple : we need to get a 4 bytes word from the address 503 on the
+ * memory it will calculate the address from the one it should start reading
+ * the data to be aligned.
+ * So it will read a word from the address 500 and the next one from the @
+ * 504, it will take the last byte of the first word and concatante it with
+ * the three bytes in the last word.
+ * result = word2 << 24 | word1
+ *
+ */
+
+/**
+ * Read the necessary words from the memory and return the data requested.
+ * Aware : if less than a word is request, it will need to be masqued to
+ * desable the bytes which are note necessary.
+ * Example : if you only need the two first bytes you should request:
+ * read_bytes_from_word (addr, 2) & 0xFFFF
+ */
+
+#include "common/std.h"
+#include "lib/read_word.h"
+
+/**
+ * Read u64 from two words.
+ *
+ * \param addr the address to read the next two 48 bits.
+ * \return u64 masked on 48 bits.
+ */
+u64 read_u64_from_word (u8 *addr)
+{
+ u64 data;
+
+ data = read_u32_from_word (addr)
+ | ((u64)read_u32_from_word(addr + sizeof(uint)) << 32);
+
+ return data;
+}
+
+
+/**
+ * Read u56 from two words.
+ *
+ * \param addr the address to read the next two 48 bits.
+ * \return u64 masked on 48 bits.
+ */
+u64 read_u56_from_word (u8 *addr)
+{
+ u64 data;
+
+ data = read_u32_from_word (addr)
+ | ((u64)read_u24_from_word(addr + sizeof(uint)) << 32);
+
+ return data;
+}
+
+
+/**
+ * Read u48 from two words.
+ *
+ * \param addr the address to read the next two 48 bits.
+ * \return u64 masked on 48 bits.
+ */
+u64 read_u48_from_word (u8 *addr)
+{
+ u64 data;
+
+ data = read_u32_from_word (addr)
+ | ((u64)read_u16_from_word(addr + sizeof(uint)) << 32);
+
+ return data;
+}
+
+/**
+ * Read 32 bits from the word.
+ *
+ * \param addr the address from the one the value should be read.
+ * \return the u32
+ */
+uint read_u32_from_word (u8 *addr)
+{
+ return read_bytes_from_word(addr, 4);
+}
+
+/**
+ * Reads 24 bits from the word.
+ *
+ * \param addr the address from the one the value should be read.
+ * \return the u32 with the last byte set to 0
+ */
+uint read_u24_from_word (u8 *addr)
+{
+ return read_bytes_from_word (addr, 3) & 0x00FFFFFF;
+}
+
+/**
+ * Read 16 bits from the word.
+ *
+ * \param addr the address from the one the value should be read.
+ * \return the u32 with the last byte set to 0
+ */
+uint read_u16_from_word (u8 *addr)
+{
+ return read_bytes_from_word (addr, 2) & 0x0000FFFF;
+}
+
+/**
+ * Read 8 bits from the word.
+ *
+ * \param addr the address from the one the value should be read.
+ * \return uint with only one byte filled.
+ */
+uint read_u8_from_word (u8 *addr)
+{
+ return read_bytes_from_word (addr, 1) & 0x000000FF;
+}
diff --git a/cesar/lib/src/restrack.c b/cesar/lib/src/restrack.c
new file mode 100644
index 0000000000..2c85e66172
--- /dev/null
+++ b/cesar/lib/src/restrack.c
@@ -0,0 +1,353 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/restrack.c
+ * \brief Resources tracker implementation.
+ * \ingroup lib
+ */
+#include "common/std.h"
+
+#include "lib/restrack.h"
+#include "lib/set.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+
+/** Recorded change for a resource. */
+struct restrack_resource_change_t
+{
+ /** Set node for set of change. */
+ set_node_t node;
+ /** Function doing the change. */
+ const char *function;
+ /** Corresponding source line. */
+ int line;
+ /** Accumulated change. */
+ int change;
+};
+typedef struct restrack_resource_change_t restrack_resource_change_t;
+
+/** Information about a resource. */
+struct restrack_resource_t
+{
+ /** Set node for set of resources. */
+ set_node_t node;
+ /** Resource pointer. */
+ void *resource;
+ /** Current reference counter value. */
+ int references;
+ /** Creator function. */
+ const char *creator_function;
+ /** Creator corresponding source line. */
+ int creator_line;
+ /** Set of recorded changes. */
+ set_t changes_set;
+};
+typedef struct restrack_resource_t restrack_resource_t;
+
+/** Resources tracker context. */
+struct restrack_t
+{
+ /** Set of tracked resources. */
+ set_t resources_set;
+ /** Automatic initialisation depends on this to be initialised to zero by
+ * the compiler. */
+ bool inited;
+ /** Should the clean up function be registered? */
+ bool atexit_done;
+};
+typedef struct restrack_t restrack_t;
+
+/** Global context. */
+restrack_t restrack_global;
+
+/** Set node comparison function for changes. */
+static bool
+restrack_resource_change_less (set_node_t *left, set_node_t *right)
+{
+ dbg_assert_ptr (left);
+ dbg_assert_ptr (right);
+ restrack_resource_change_t *l, *r;
+ l = PARENT_OF (restrack_resource_change_t, node, left);
+ r = PARENT_OF (restrack_resource_change_t, node, right);
+ /* Function strings are compared by address. This is a feature as the
+ * provided function string is supposed to always have the same address at
+ * each call. */
+ return l->function == r->function
+ ? l->line < r->line
+ : l->function < r->function;
+}
+
+/** Set node comparison function for resources. */
+static bool
+restrack_resource_less (set_node_t *left, set_node_t *right)
+{
+ dbg_assert_ptr (left);
+ dbg_assert_ptr (right);
+ restrack_resource_t *l, *r;
+ l = PARENT_OF (restrack_resource_t, node, left);
+ r = PARENT_OF (restrack_resource_t, node, right);
+ return l->resource < r->resource;
+}
+
+/**
+ * Get and eventually initialise global context.
+ * \return unique instance pointer
+ */
+static restrack_t *
+restrack_get_instance (void)
+{
+ restrack_t *ctx = &restrack_global;
+ if (!ctx->inited)
+ {
+ set_init (&ctx->resources_set, restrack_resource_less);
+ ctx->inited = true;
+ }
+ if (!ctx->atexit_done)
+ {
+ atexit (restrack_uninit);
+ ctx->atexit_done = true;
+ }
+ return ctx;
+}
+
+static restrack_resource_t *
+restrack_resource_new (void *resource, const char *function, int line)
+{
+ dbg_assert_ptr (resource);
+ restrack_resource_t *r;
+ /* Malloc should be replaced with a slab allocator. */
+ r = malloc (sizeof (*r));
+ if (!r)
+ dbg_fatal ("exhausted virtual memory");
+ set_node_init (&r->node);
+ r->resource = resource;
+ r->references = 0;
+ r->creator_function = function;
+ r->creator_line = line;
+ set_init (&r->changes_set, restrack_resource_change_less);
+ return r;
+}
+
+static void
+restrack_resource_delete (restrack_resource_t *r)
+{
+ dbg_assert_ptr (r);
+ set_node_t *i, *last, *in;
+ /* Remove all changes node. */
+ for (i = set_begin (&r->changes_set), last = set_end (&r->changes_set);
+ i != last;
+ i = in)
+ {
+ in = set_next (&r->changes_set, i);
+ set_remove (&r->changes_set, i);
+ free (PARENT_OF (restrack_resource_t, node, i));
+ }
+ dbg_assert (set_empty (&r->changes_set));
+ free (r);
+}
+
+/**
+ * Dump a resource.
+ * \param r resource information structure
+ */
+static void
+restrack_resource_dump (restrack_resource_t *r)
+{
+ dbg_assert_ptr (r);
+ fprintf (stderr, "[%#8x] %3d (created: %s:%d)\n", (u32) r->resource,
+ r->references, r->creator_function, r->creator_line);
+ set_node_t *i, *last;
+ for (i = set_begin (&r->changes_set), last = set_end (&r->changes_set);
+ i != last;
+ i = set_next (&r->changes_set, i))
+ {
+ restrack_resource_change_t *c =
+ PARENT_OF (restrack_resource_change_t, node, i);
+ fprintf (stderr, " %s:%d: %3d\n", c->function, c->line, c->change);
+ }
+}
+
+void
+restrack_create (void *owner, void *resource, const char *function, int line,
+ int initial)
+{
+ dbg_assert_ptr (resource);
+ restrack_t *ctx = restrack_get_instance ();
+ restrack_resource_t *r;
+ set_node_t *n;
+ /* Check for duplicates. */
+ r = restrack_resource_new (resource, function, line);
+ n = set_find (&ctx->resources_set, &r->node);
+ if (n)
+ {
+ fprintf (stderr, "!! Duplicate resource creation\n");
+ restrack_resource_dump (PARENT_OF (restrack_resource_t, node, n));
+ fputc ('\n', stderr);
+ restrack_resource_delete (r);
+ }
+ else
+ {
+ /* No duplicates, insert the new node. */
+ dbg_check (set_insert (&ctx->resources_set, &r->node));
+ }
+ /* In all cases, update the node. */
+ restrack_update (owner, resource, function, line, initial);
+}
+
+void
+restrack_update (void *owner, void *resource, const char *function, int line,
+ int change)
+{
+ dbg_assert_ptr (resource);
+ if (change == 0)
+ return;
+ restrack_t *ctx = restrack_get_instance ();
+ set_node_t *n;
+ /* Look up the specified resource. */
+ restrack_resource_t k;
+ set_node_init (&k.node);
+ k.resource = resource;
+ n = set_find (&ctx->resources_set, &k.node);
+ /* If not found, this is a fatal error. */
+ if (!n)
+ {
+ dbg_fatal ("!! Unknown resource update\n"
+ " %s:%d: %3d\n", function, line, change);
+ }
+ else
+ {
+ /* Else, update. */
+ restrack_resource_t *r = PARENT_OF (restrack_resource_t, node, n);
+ r->references += change;
+ restrack_resource_change_t ck;
+ set_node_init (&ck.node);
+ ck.function = function;
+ ck.line = line;
+ n = set_find (&r->changes_set, &ck.node);
+ /* Update an entry or create a new one. */
+ if (n)
+ {
+ PARENT_OF (restrack_resource_change_t, node, n)->change += change;
+ }
+ else
+ {
+ restrack_resource_change_t *c;
+ /* Malloc should be replaced with a slab allocator. */
+ c = malloc (sizeof (*c));
+ if (!c)
+ dbg_fatal ("exhausted virtual memory");
+ set_node_init (&c->node);
+ c->function = function;
+ c->line = line;
+ c->change = change;
+ dbg_check (set_insert (&r->changes_set, &c->node));
+ }
+ /* Test for too many releases. */
+ if (r->references < 0)
+ {
+ fprintf (stderr, "!! Negative resource reference count\n"
+ " %s:%d: %3d\n", function, line, change);
+ restrack_resource_dump (r);
+ fputc ('\n', stderr);
+ }
+ }
+}
+
+void
+restrack_destroy (void *owner, void *resource, const char *function, int line,
+ int change)
+{
+ dbg_assert_ptr (resource);
+ restrack_t *ctx = restrack_get_instance ();
+ set_node_t *n;
+ /* Look up the specified resource. */
+ restrack_resource_t k;
+ set_node_init (&k.node);
+ k.resource = resource;
+ n = set_find (&ctx->resources_set, &k.node);
+ /* If not found, this is a fatal error. */
+ if (!n)
+ {
+ dbg_fatal ("!! Unknown resource destruction\n"
+ " %s:%d: %3d\n", function, line, change);
+ }
+ else
+ {
+ /* Else, update the entry... */
+ restrack_update (owner, resource, function, line, change);
+#if !CONFIG_RESTRACK_KEEP
+ /* ...and remove it. */
+ set_remove (&ctx->resources_set, n);
+ restrack_resource_t *r = PARENT_OF (restrack_resource_t, node, n);
+ if (r->references != 0)
+ {
+ fprintf (stderr, "!! Unbalanced resource destructed\n"
+ " %s:%d: %3d\n", function, line, change);
+ restrack_resource_dump (r);
+ fputc ('\n', stderr);
+ }
+ restrack_resource_delete (r);
+#endif /* !CONFIG_RESTRACK_KEEP */
+ }
+}
+
+bool
+restrack_check (void)
+{
+ restrack_t *ctx = restrack_get_instance ();
+ set_node_t *i, *last;
+ bool errors = false;
+ /* Travel the resources set and bark if unbalanced resources are found. */
+ for (i = set_begin (&ctx->resources_set),
+ last = set_end (&ctx->resources_set);
+ i != last;
+ i = set_next (&ctx->resources_set, i))
+ {
+ restrack_resource_t *r = PARENT_OF (restrack_resource_t, node, i);
+ if (r->references != 0)
+ {
+ if (!errors)
+ {
+ errors = true;
+ fprintf (stderr, "!! Unbalanced resources follow:\n");
+ }
+ restrack_resource_dump (r);
+ }
+ }
+ if (errors)
+ fputc ('\n', stderr);
+ return !errors;
+}
+
+void
+restrack_uninit (void)
+{
+ restrack_t *ctx = &restrack_global;
+ if (ctx->inited)
+ {
+ /* First check for leaks. */
+ restrack_check ();
+ /* Remove all resources nodes. */
+ set_node_t *i, *last, *in;
+ for (i = set_begin (&ctx->resources_set),
+ last = set_end (&ctx->resources_set);
+ i != last;
+ i = in)
+ {
+ in = set_next (&ctx->resources_set, i);
+ set_remove (&ctx->resources_set, i);
+ restrack_resource_t *r = PARENT_OF (restrack_resource_t, node, i);
+ restrack_resource_delete (r);
+ }
+ /* Prepare for an eventual reinitialisation. */
+ dbg_assert (set_empty (&ctx->resources_set));
+ ctx->inited = false;
+ }
+}
+
diff --git a/cesar/lib/src/skewheap.c b/cesar/lib/src/skewheap.c
new file mode 100644
index 0000000000..6da16d597e
--- /dev/null
+++ b/cesar/lib/src/skewheap.c
@@ -0,0 +1,138 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/skewheap.c
+ * \brief Skew heaps.
+ * \ingroup lib
+ */
+#include "common/std.h"
+
+#include "lib/heap.h"
+
+void
+heap_node_init (heap_node_t *node)
+{
+ node->father = NULL;
+ node->left = node->right = NULL;
+}
+
+heap_node_t *
+heap_node_merge (heap_node_t *root1, heap_node_t *root2,
+ heap_node_less_t less)
+{
+ heap_node_t *h1, *h2, *h, *root;
+ dbg_assert (!root1 || !root1->father);
+ dbg_assert (!root2 || !root2->father);
+ dbg_assert (less);
+ /* Trivial cases. */
+ if (!root1)
+ return root2;
+ else if (!root2)
+ return root1;
+ h1 = root1;
+ h2 = root2;
+ /* Skew merge root.
+ * h1 and h2: current "read" node.
+ * h: current "write" node.
+ * h->left: where the next node will be put. */
+ if (less (h1, h2))
+ {
+ h = h1;
+ h1 = h1->right;
+ }
+ else
+ {
+ h = h2;
+ h2 = h2->right;
+ }
+ root = h;
+ h->right = h->left;
+ /* Skew merge loop. */
+ while (h1 || h2)
+ {
+ if (!h2 || (h1 && less (h1, h2)))
+ {
+ h1->father = h;
+ h->left = h1;
+ h = h1;
+ h1 = h1->right;
+ }
+ else
+ {
+ h2->father = h;
+ h->left = h2;
+ h = h2;
+ h2 = h2->right;
+ }
+ h->right = h->left;
+ }
+ h->left = NULL;
+ return root;
+}
+
+void
+heap_insert (heap_t *heap, heap_node_t *node)
+{
+ dbg_assert (heap && heap->less);
+ dbg_assert (node);
+ heap->root = heap_node_merge (heap->root, node, heap->less);
+}
+
+void
+heap_remove_root (heap_t *heap)
+{
+ heap_node_t *root;
+ dbg_assert (heap);
+ dbg_assert (!heap_empty (heap));
+ root = heap->root;
+ if (root->left)
+ root->left->father = NULL;
+ if (root->right)
+ root->right->father = NULL;
+ heap->root = heap_node_merge (root->left, root->right, heap->less);
+ root->father = root->left = root->right = NULL;
+}
+
+void
+heap_remove (heap_t *heap, heap_node_t *node)
+{
+ heap_node_t **r;
+ dbg_assert (heap);
+ dbg_assert (!heap_empty (heap));
+ dbg_assert (node);
+ /* Where to store the merged tree? */
+ if (!node->father)
+ {
+ dbg_assert (node == heap->root);
+ r = &heap->root;
+ }
+ else if (node->father->right == node)
+ {
+ r = &node->father->right;
+ }
+ else
+ {
+ dbg_assert (node->father->left == node);
+ r = &node->father->left;
+ }
+ /* Need NULL father pointer. */
+ if (node->left)
+ node->left->father = NULL;
+ if (node->right)
+ node->right->father = NULL;
+ /* Merge left and right subtree. */
+ *r = heap_node_merge (node->left, node->right, heap->less);
+ if (*r)
+ (*r)->father = node->father;
+ /* Swap father children. */
+ if (node->father)
+ XCH (node->father->left, node->father->right);
+ /* Detach the removed node. */
+ node->father = node->left = node->right = NULL;
+}
+
diff --git a/cesar/lib/src/swap.c b/cesar/lib/src/swap.c
new file mode 100644
index 0000000000..cff0a9473f
--- /dev/null
+++ b/cesar/lib/src/swap.c
@@ -0,0 +1,31 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/swap.c
+ * \brief generic swap functions
+ * \ingroup lib
+ */
+#include "common/std.h"
+#include "lib/swap.h"
+
+/** swap an unsigned short */
+u16 swap16(u16 x)
+{
+ return (u16)( (((u16)(x) & (u16)0x00ff) << 8) |
+ (((u16)(x) & (u16)0xff00) >> 8) );
+}
+
+/** swap an unsigned long */
+u32 swap32(u32 x)
+{
+ return (u32)( (((u32)(x) & (u32)0x000000ff) << 24) |
+ (((u32)(x) & (u32)0x0000ff00) << 8) |
+ (((u32)(x) & (u32)0x00ff0000) >> 8) |
+ (((u32)(x) & (u32)0xff000000) >> 24) );
+}
+
diff --git a/cesar/lib/src/test.c b/cesar/lib/src/test.c
new file mode 100644
index 0000000000..13a14f3b19
--- /dev/null
+++ b/cesar/lib/src/test.c
@@ -0,0 +1,138 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/test.c
+ * \brief Test infrastructure.
+ * \ingroup lib
+ *
+ * For the moment, only stdio implementation.
+ */
+#include "common/std.h"
+
+#include "lib/test.h"
+
+#include <stdio.h>
+#include <stdarg.h>
+#include <signal.h>
+
+void
+test_sig_handler (int sig)
+{
+ signal (sig, test_sig_handler);
+ dbg_fatal ("Caught signal %d", sig);
+}
+
+void
+test_init (test_t t, int argc, char **argv)
+{
+ int i;
+ test_init_basic (t, 2);
+ /* Parse command line. */
+ for (i = 1; i < argc; i++)
+ {
+ if (argv[i][0] == '-')
+ {
+ const char *s = argv[i] + 1;
+ while (*s)
+ {
+ if (*s == 'v')
+ t->verbose++;
+ else if (*s == 'q')
+ t->verbose = 0;
+ s++;
+ }
+ }
+ }
+ /* Install signal handler. */
+ signal (SIGBUS, test_sig_handler);
+ signal (SIGILL, test_sig_handler);
+ signal (SIGFPE, test_sig_handler);
+ signal (SIGSEGV, test_sig_handler);
+}
+
+void
+test_init_basic (test_t t, uint verbose)
+{
+ t->current_test_suite = NULL;
+ t->current_test_case = NULL;
+ t->current_test = NULL;
+ t->test_nb = 0;
+ t->fail_nb = 0;
+ t->verbose = verbose;
+}
+
+void
+test_result (test_t t)
+{
+ int percent;
+ if (t->verbose >= 1)
+ {
+ percent = t->test_nb == 0 ? 100
+ : 100 * (t->test_nb - t->fail_nb) / t->test_nb;
+ fprintf (stderr, "%d%%, tests: %d, failures: %d\n", percent,
+ t->test_nb, t->fail_nb);
+ }
+}
+
+void
+test_suite_begin (test_t t, const char *name)
+{
+ t->current_test_suite = name;
+ if (t->verbose >= 2)
+ fprintf (stderr, "running suite: %s\n", name);
+}
+
+void
+test_case_begin (test_t t, const char *name)
+{
+ t->current_test_case = name;
+}
+
+void
+test_failled (void)
+{
+}
+
+void
+test_format_ (test_t t, const char *file, int line, char type,
+ const char *ufmt, const char *fmt, ...)
+{
+ if (type == 'F')
+ test_failled ();
+ if (t->verbose >= 4
+ || (t->verbose >= 3 && type == 'P')
+ || (t->verbose >= 2 && type == 'F'))
+ {
+ fprintf (stderr, "%s:%d:%c:%s:%s: ", file, line, type,
+ t->current_test_case ? t->current_test_case : "unknown",
+ t->current_test);
+ if (fmt)
+ {
+ va_list ap;
+ va_start (ap, fmt);
+ vfprintf (stderr, fmt, ap);
+ va_end (ap);
+ fputc ('\n', stderr);
+ }
+ else
+ {
+ fprintf (stderr, "%s\n", ufmt);
+ }
+ }
+}
+
+void
+test_debug_print (const char *msg, ...)
+{
+ va_list ap;
+ va_start (ap, msg);
+ vfprintf (stderr, msg, ap);
+ va_end (ap);
+ fputc ('\n', stderr);
+}
+
diff --git a/cesar/lib/src/trace.c b/cesar/lib/src/trace.c
new file mode 100644
index 0000000000..48cca1fa73
--- /dev/null
+++ b/cesar/lib/src/trace.c
@@ -0,0 +1,655 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/trace.c
+ * \brief Trace system.
+ * \ingroup lib
+ */
+#include "common/std.h"
+
+#include "lib/trace.h"
+#include "hal/arch/arch.h"
+#include "hal/arch/io.h"
+
+#include <stdio.h>
+
+#define TRACE_ALIGN (sizeof (u32))
+
+/** Trace system context. */
+struct trace_t
+{
+ /** List of buffers. */
+ list_t buffers;
+};
+
+static trace_t trace_global;
+
+void
+trace_init (void)
+{
+ trace_t * const ctx = &trace_global;
+ list_init (&ctx->buffers);
+}
+
+void
+trace_uninit (void)
+{
+ trace_t * const ctx = &trace_global;
+ dbg_assert (list_empty (&ctx->buffers));
+}
+
+bool
+trace_drop_chunks (uint n)
+{
+ dbg_assert (n > 0);
+ trace_t * const ctx = &trace_global;
+ /* Can not help if no trace buffers. */
+ if (list_empty (&ctx->buffers))
+ return false;
+ while (n)
+ {
+ /* Search the biggest buffer, taking drop level into account. */
+ trace_buffer_t *bigest_buf = NULL;
+ uint bigest_buf_size = 0, second_buf_size = 0;
+ list_node_t *i, *end;
+ i = list_begin (&ctx->buffers);
+ end = list_end (&ctx->buffers);
+ for (; i != end; i = list_next (i))
+ {
+ trace_buffer_t *buf = PARENT_OF (trace_buffer_t, node, i);
+ if (!buf->locked)
+ {
+ uint buf_size_shifted = buf->chunks_nb > buf->preload
+ ? (buf->chunks_nb - buf->preload) << buf->drop_level
+ : 0;
+ if (buf_size_shifted > bigest_buf_size)
+ {
+ second_buf_size = bigest_buf_size;
+ bigest_buf_size = buf_size_shifted;
+ bigest_buf = buf;
+ }
+ }
+ }
+ /* Drop as many block as possible to satisfy drop request. */
+ if (bigest_buf_size == 0)
+ return false;
+ uint i_can_drop = MIN (n, ((bigest_buf_size - second_buf_size +
+ (1 << bigest_buf->drop_level) - 1)
+ >> bigest_buf->drop_level));
+ trace_chunk_t *hdrop, *tdrop;
+ hdrop = bigest_buf->head;
+ tdrop = hdrop;
+ n -= i_can_drop;
+ arch_atomic_add ((int *) &bigest_buf->chunks_nb, -i_can_drop);
+ while (--i_can_drop)
+ tdrop = tdrop->next;
+ bigest_buf->head = tdrop->next;
+ blk_release_desc_range ((blk_t *) hdrop, (blk_t *) tdrop);
+ }
+ return true;
+}
+
+static int
+trace_format_bool (char *text, uint text_size, int data)
+{
+ const char *t;
+ uint ts;
+ if (!data)
+ {
+ t = "false"; ts = 5;
+ }
+ else
+ {
+ t = "true"; ts = 4;
+ }
+ if (ts > text_size)
+ return -1;
+ else
+ {
+ memcpy (text, t, ts);
+ return ts;
+ }
+}
+
+static int
+trace_format_decimal (char *text, uint text_size, int data)
+{
+ int ret = snprintf (text, text_size, "%d", data);
+ return ret < (int) text_size ? ret : -1;
+}
+
+static int
+trace_format_unsigned (char *text, uint text_size, int data)
+{
+ int ret = snprintf (text, text_size, "%u", data);
+ return ret < (int) text_size ? ret : -1;
+}
+
+static int
+trace_format_hexa (char *text, uint text_size, int data)
+{
+ int ret = snprintf (text, text_size, "0x%08x", data);
+ return ret < (int) text_size ? ret : -1;
+}
+
+static const char trace_format_hexdigits[] = "0123456789abcdef";
+
+static int
+trace_format_mac (char *text, uint text_size, u64 data)
+{
+ const uint size = 3 * 6 - 1;
+ if (text_size < size)
+ return -1;
+ else
+ {
+ uint i;
+ u64 v;
+ v = data;
+ for (i = 5; i; i--)
+ {
+ *text++ = trace_format_hexdigits[(v >> 1*4) & 0xf];
+ *text++ = trace_format_hexdigits[(v >> 0*4) & 0xf];
+ *text++ = ':';
+ v >>= 8;
+ }
+ *text++ = trace_format_hexdigits[(v >> 1*4) & 0xf];
+ *text++ = trace_format_hexdigits[(v >> 0*4) & 0xf];
+ return size;
+ }
+}
+
+void
+trace_namespace_init (trace_namespace_t *ns,
+ const trace_event_id_t *event_ids, uint event_ids_nb)
+{
+ uint i;
+ dbg_assert (ns);
+ /* Initialise fields. */
+ ns->event_ids = event_ids;
+ ns->event_ids_nb = event_ids_nb;
+ for (i = 0; i < COUNT (ns->formats); i++)
+ ns->formats[i].size = 0;
+ /* Provide default useful formats. */
+ trace_namespace_register_format (ns, 'b', trace_format_bool);
+ trace_namespace_register_format (ns, 'd', trace_format_decimal);
+ trace_namespace_register_format (ns, 'u', trace_format_unsigned);
+ trace_namespace_register_format (ns, 'x', trace_format_hexa);
+ trace_namespace_register_format_u64 (ns, 'm', trace_format_mac);
+}
+
+void
+trace_namespace_register_format (trace_namespace_t *ns, char code,
+ trace_format_u32_t callback)
+{
+ dbg_assert (ns);
+ dbg_assert ((code >= 'A' && code <= 'Z') || (code >= 'a' && code <= 'z'));
+ dbg_assert (callback);
+ ns->formats[code - 'A'].callback.format_u32 = callback;
+ ns->formats[code - 'A'].size = 1;
+}
+
+void
+trace_namespace_register_format_u64 (trace_namespace_t *ns, char code,
+ trace_format_u64_t callback)
+{
+ dbg_assert (ns);
+ dbg_assert ((code >= 'A' && code <= 'Z') || (code >= 'a' && code <= 'z'));
+ dbg_assert (callback);
+ ns->formats[code - 'A'].callback.format_u64 = callback;
+ ns->formats[code - 'A'].size = 2;
+}
+
+void
+trace_buffer_add (trace_buffer_t *buf, const char *name, uint drop_level,
+ uint preload, bool locked, trace_namespace_t *namespace)
+{
+ dbg_assert (buf);
+ dbg_assert (name);
+ dbg_assert (preload > 0);
+ trace_t * const ctx = &trace_global;
+ /* Initialise trace buffer. */
+ list_init_node (&buf->node);
+ buf->chunks_nb = preload;
+ buf->drop_level = drop_level;
+ buf->preload = preload;
+ buf->locked = locked;
+ buf->namespace = namespace;
+ /* Allocate chunks. */
+ blk_t *tail;
+ buf->head = (trace_chunk_t *) blk_alloc_desc_range (preload, &tail);
+ buf->tail = (trace_chunk_t *) tail;
+ /* Initialise chunks. */
+ trace_chunk_t *i = buf->head;
+ do
+ {
+ i->data_end = i->data;
+ i->chunk_end = i->data + BLK_SIZE / TRACE_ALIGN;
+ if (i == buf->tail)
+ break;
+ i = i->next;
+ } while (1);
+ /* Add it to context. */
+ list_push (&ctx->buffers, &buf->node);
+}
+
+void
+trace_buffer_remove (trace_buffer_t *buf)
+{
+ dbg_assert (buf);
+ trace_t * const ctx = &trace_global;
+ /* Remove from context. */
+ list_remove (&ctx->buffers, &buf->node);
+ /* Release chunks. */
+ blk_release_desc_range ((blk_t *) buf->head, (blk_t *) buf->tail);
+}
+
+static int
+trace_buffer_dump_event (char *text, char *text_end,
+ trace_namespace_t *namespace,
+ uint **data, uint *data_end)
+{
+ dbg_assert (text && text_end && text < text_end);
+ dbg_assert (namespace);
+ dbg_assert (data && *data && data_end && *data < data_end);
+ /* Read event ID. */
+ uint id = **data;
+ uint args = id & 0xff;
+ id >>= 8;
+ uint oargs = args;
+ int *parg = (int *) *data + 1;
+ dbg_assert (parg + args <= (int *) data_end);
+ dbg_assert (id < namespace->event_ids_nb);
+ const trace_event_id_t *ei = &namespace->event_ids[id];
+ dbg_assert (ei->format_string);
+ char *p = text;
+ /* Print time stamp. */
+ if (ei->timestamp)
+ {
+ dbg_assert (args);
+ args--;
+ int ret = snprintf (p, text_end - p, "[0x%08x] ", *parg++);
+ if (ret >= text_end - p)
+ return -1;
+ p += ret;
+ }
+ else
+ {
+ int ret = snprintf (p, text_end - p, "[.] ");
+ if (ret >= text_end - p)
+ return -1;
+ p += ret;
+ }
+ /* Decode format string. */
+ const char *fp;
+ for (fp = ei->format_string; *fp; fp++)
+ {
+ if (*fp == '%' && *++fp != '%')
+ {
+ dbg_assert (((*fp >= 'A' && *fp <= 'Z')
+ || (*fp >= 'a' && *fp <= 'z'))
+ && namespace->formats[*fp - 'A'].size);
+ int ret;
+ if (namespace->formats[*fp - 'A'].size == 1)
+ {
+ dbg_assert (args);
+ args--;
+ ret = namespace->formats[*fp - 'A'].callback.format_u32 (
+ p, text_end - p, *parg++);
+ }
+ else
+ {
+ dbg_assert (args >= 2);
+ args -= 2;
+ u64 arg = (u64) parg[1] << 32 | parg[0];
+ ret = namespace->formats[*fp - 'A'].callback.format_u64 (
+ p, text_end - p, arg);
+ parg += 2;
+ }
+ if (ret == -1)
+ return -1;
+ p += ret;
+ }
+ else
+ {
+ /* No room left, cancel the dump of this event. */
+ if (p == text_end)
+ return -1;
+ *p++ = *fp;
+ }
+ }
+ dbg_assert (args == 0);
+ /* No room left for the trailing new line, cancel the dump of this
+ * event. */
+ if (p == text_end)
+ return -1;
+ *p++ = '\n';
+ *data += 1 + oargs;
+ return p - text;
+}
+
+int
+trace_buffer_dump (trace_buffer_t *buf, trace_dump_callback_t cb, void *user)
+{
+#define DUMP_TEXT_SLACK 20
+ char text[2000];
+ int text_size = 0;
+ trace_chunk_t *head, *tail;
+ u32 *data, *data_end;
+ int sum = 0;
+ /* TODO: acquire lock, increment reference counter. */
+ tail = buf->tail;
+ head = buf->head;
+ /* Loop for each chunks. */
+ do
+ {
+ data = head->data;
+ data_end = head->data_end;
+ /* Loop on this chunk. */
+ while (data < data_end)
+ {
+ int ret = trace_buffer_dump_event (
+ text + text_size, text + COUNT (text),
+ buf->namespace, &data, data_end);
+ if (ret != -1)
+ text_size += ret;
+ if (ret == -1
+ || text_size + DUMP_TEXT_SLACK >= (int) COUNT (text))
+ {
+ dbg_assert (text_size != 0);
+ if (cb (user, text, text_size) != text_size)
+ {
+ /* Get out. */
+ sum = -1;
+ break;
+ }
+ sum += text_size;
+ text_size = 0;
+ }
+ }
+ if (sum == -1 || head == tail)
+ break;
+ head = head->next;
+ } while (1);
+ /* Final text. */
+ if (sum != -1 && text_size)
+ {
+ if (cb (user, text, text_size) != text_size)
+ sum = -1;
+ else
+ sum += text_size;
+ }
+ return sum;
+}
+
+static int
+trace_buffer_dbg_dump_callback (void *user, char *text, uint text_size)
+{
+ dbg_assert (text && text_size);
+ arch_io_write (text, text_size);
+ return text_size;
+}
+
+void
+trace_buffer_dbg_dump (trace_buffer_t *buf)
+{
+ trace_buffer_dump (buf, trace_buffer_dbg_dump_callback, NULL);
+}
+
+static void
+trace_printn_prepare (trace_buffer_t *buf, uint count)
+{
+ dbg_assert (buf && buf->tail);
+ trace_chunk_t *tail = buf->tail;
+ if (DEBUG_MORE)
+ dbg_assert (tail->data <= tail->data_end
+ && tail->data_end <= tail->chunk_end);
+ if (tail->data_end + count > tail->chunk_end)
+ {
+ /* No room left, allocate a new chunk. */
+ dbg_assert (!buf->locked);
+ trace_chunk_t *c = (trace_chunk_t *) blk_alloc_desc ();
+ c->data_end = c->data;
+ c->chunk_end = c->data + BLK_SIZE / TRACE_ALIGN;
+ tail->next = c;
+ REORDER_BARRIER ();
+ buf->tail = c;
+ REORDER_BARRIER ();
+ arch_atomic_add ((int *) &buf->chunks_nb, 1);
+ REORDER_BARRIER ();
+ }
+}
+
+void
+trace_print0 (trace_buffer_t *buf, uint id)
+{
+ trace_printn_prepare (buf, 1);
+ trace_fast_print0 (buf, id);
+}
+
+void
+trace_print1 (trace_buffer_t *buf, uint id, int arg0)
+{
+ trace_printn_prepare (buf, 2);
+ trace_fast_print1 (buf, id, arg0);
+}
+
+void
+trace_print2 (trace_buffer_t *buf, uint id, int arg0, int arg1)
+{
+ trace_printn_prepare (buf, 3);
+ trace_fast_print2 (buf, id, arg0, arg1);
+}
+
+void
+trace_print3 (trace_buffer_t *buf, uint id, int arg0, int arg1, int arg2)
+{
+ trace_printn_prepare (buf, 4);
+ trace_fast_print3 (buf, id, arg0, arg1, arg2);
+}
+
+void
+trace_print4 (trace_buffer_t *buf, uint id, int arg0, int arg1, int arg2,
+ int arg3)
+{
+ trace_printn_prepare (buf, 5);
+ trace_fast_print4 (buf, id, arg0, arg1, arg2, arg3);
+}
+
+void
+trace_print5 (trace_buffer_t *buf, uint id, int arg0, int arg1, int arg2,
+ int arg3, int arg4)
+{
+ trace_printn_prepare (buf, 6);
+ trace_fast_print5 (buf, id, arg0, arg1, arg2, arg3, arg4);
+}
+
+void
+trace_print6 (trace_buffer_t *buf, uint id, int arg0, int arg1, int arg2,
+ int arg3, int arg4, int arg5)
+{
+ trace_printn_prepare (buf, 7);
+ trace_fast_print6 (buf, id, arg0, arg1, arg2, arg3, arg4, arg5);
+}
+
+void
+trace_print7 (trace_buffer_t *buf, uint id, int arg0, int arg1, int arg2,
+ int arg3, int arg4, int arg5, int arg6)
+{
+ trace_printn_prepare (buf, 8);
+ trace_fast_print7 (buf, id, arg0, arg1, arg2, arg3, arg4, arg5, arg6);
+}
+
+void
+trace_print8 (trace_buffer_t *buf, uint id, int arg0, int arg1, int arg2,
+ int arg3, int arg4, int arg5, int arg6, int arg7)
+{
+ trace_printn_prepare (buf, 9);
+ trace_fast_print8 (buf, id, arg0, arg1, arg2, arg3, arg4, arg5, arg6,
+ arg7);
+}
+
+extern inline u32 *
+trace_fast_printn_prepare (trace_buffer_t *buf, uint count)
+{
+ /* "Fast" means no allocation. */
+ if (DEBUG_MORE)
+ dbg_assert (buf && buf->tail);
+ trace_chunk_t *tail = buf->tail;
+ if (DEBUG_MORE)
+ dbg_assert (tail->data <= tail->data_end
+ && tail->data_end <= tail->chunk_end);
+ u32 *data_end = tail->data_end;
+ if (data_end + count > tail->chunk_end)
+ {
+ /* No room left, use the oldest chunk for the new chunk. */
+ if (DEBUG_MORE)
+ dbg_assert (buf->head && buf->locked);
+ trace_chunk_t *head = buf->head;
+ tail->next = head;
+ buf->tail = head;
+ buf->head = head->next;
+ tail = head;
+ data_end = tail->data;
+ tail->data_end = data_end;
+ tail->chunk_end = data_end + BLK_SIZE / TRACE_ALIGN;
+ }
+ /* Dump to buffer. */
+ return data_end;
+}
+
+void
+trace_fast_print0 (trace_buffer_t *buf, uint id)
+{
+ u32 *p = trace_fast_printn_prepare (buf, 1);
+ *p++ = id << 8 | 0;
+ trace_chunk_t *tail = buf->tail;
+ REORDER_BARRIER ();
+ tail->data_end = p;
+}
+
+void
+trace_fast_print1 (trace_buffer_t *buf, uint id, int arg0)
+{
+ u32 *p = trace_fast_printn_prepare (buf, 2);
+ *p++ = id << 8 | 1;
+ *p++ = arg0;
+ trace_chunk_t *tail = buf->tail;
+ REORDER_BARRIER ();
+ tail->data_end = p;
+}
+
+void
+trace_fast_print2 (trace_buffer_t *buf, uint id, int arg0, int arg1)
+{
+ u32 *p = trace_fast_printn_prepare (buf, 3);
+ *p++ = id << 8 | 2;
+ *p++ = arg0;
+ *p++ = arg1;
+ trace_chunk_t *tail = buf->tail;
+ REORDER_BARRIER ();
+ tail->data_end = p;
+}
+
+void
+trace_fast_print3 (trace_buffer_t *buf, uint id, int arg0, int arg1, int arg2)
+{
+ u32 *p = trace_fast_printn_prepare (buf, 4);
+ *p++ = id << 8 | 3;
+ *p++ = arg0;
+ *p++ = arg1;
+ *p++ = arg2;
+ trace_chunk_t *tail = buf->tail;
+ REORDER_BARRIER ();
+ tail->data_end = p;
+}
+
+void
+trace_fast_print4 (trace_buffer_t *buf, uint id, int arg0, int arg1, int arg2,
+ int arg3)
+{
+ u32 *p = trace_fast_printn_prepare (buf, 5);
+ *p++ = id << 8 | 4;
+ *p++ = arg0;
+ *p++ = arg1;
+ *p++ = arg2;
+ *p++ = arg3;
+ trace_chunk_t *tail = buf->tail;
+ REORDER_BARRIER ();
+ tail->data_end = p;
+}
+
+void
+trace_fast_print5 (trace_buffer_t *buf, uint id, int arg0, int arg1, int arg2,
+ int arg3, int arg4)
+{
+ u32 *p = trace_fast_printn_prepare (buf, 6);
+ *p++ = id << 8 | 5;
+ *p++ = arg0;
+ *p++ = arg1;
+ *p++ = arg2;
+ *p++ = arg3;
+ *p++ = arg4;
+ trace_chunk_t *tail = buf->tail;
+ REORDER_BARRIER ();
+ tail->data_end = p;
+}
+
+void
+trace_fast_print6 (trace_buffer_t *buf, uint id, int arg0, int arg1, int arg2,
+ int arg3, int arg4, int arg5)
+{
+ u32 *p = trace_fast_printn_prepare (buf, 7);
+ *p++ = id << 8 | 6;
+ *p++ = arg0;
+ *p++ = arg1;
+ *p++ = arg2;
+ *p++ = arg3;
+ *p++ = arg4;
+ *p++ = arg5;
+ trace_chunk_t *tail = buf->tail;
+ REORDER_BARRIER ();
+ tail->data_end = p;
+}
+
+void
+trace_fast_print7 (trace_buffer_t *buf, uint id, int arg0, int arg1, int arg2,
+ int arg3, int arg4, int arg5, int arg6)
+{
+ u32 *p = trace_fast_printn_prepare (buf, 8);
+ *p++ = id << 8 | 7;
+ *p++ = arg0;
+ *p++ = arg1;
+ *p++ = arg2;
+ *p++ = arg3;
+ *p++ = arg4;
+ *p++ = arg5;
+ *p++ = arg6;
+ trace_chunk_t *tail = buf->tail;
+ REORDER_BARRIER ();
+ tail->data_end = p;
+}
+
+void
+trace_fast_print8 (trace_buffer_t *buf, uint id, int arg0, int arg1, int arg2,
+ int arg3, int arg4, int arg5, int arg6, int arg7)
+{
+ u32 *p = trace_fast_printn_prepare (buf, 9);
+ *p++ = id << 8 | 8;
+ *p++ = arg0;
+ *p++ = arg1;
+ *p++ = arg2;
+ *p++ = arg3;
+ *p++ = arg4;
+ *p++ = arg5;
+ *p++ = arg6;
+ *p++ = arg7;
+ trace_chunk_t *tail = buf->tail;
+ REORDER_BARRIER ();
+ tail->data_end = p;
+}
+
diff --git a/cesar/lib/src/try.c b/cesar/lib/src/try.c
new file mode 100644
index 0000000000..37e8a398d5
--- /dev/null
+++ b/cesar/lib/src/try.c
@@ -0,0 +1,17 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/src/try.c
+ * \brief Light exception system.
+ * \ingroup lib
+ */
+#include "common/std.h"
+
+#include "lib/try.h"
+
+jmp_buf *try_state_;