1 files changed, 431 insertions, 0 deletions

diff --git a/src/plugin/regex/regex_block_lib.c b/src/plugin/regex/regex_block_lib.c
new file mode 100644
index 000000000..048d6d743
--- /dev/null
+++ b/src/plugin/regex/regex_block_lib.c
@@ -0,0 +1,431 @@
+/*
+     This file is part of GNUnet.
+     Copyright (C) 2012,2013 GNUnet e.V.
+
+     GNUnet is free software: you can redistribute it and/or modify it
+     under the terms of the GNU Affero General Public License as published
+     by the Free Software Foundation, either version 3 of the License,
+     or (at your option) any later version.
+
+     GNUnet 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
+     Affero General Public License for more details.
+
+     You should have received a copy of the GNU Affero General Public License
+     along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+     SPDX-License-Identifier: AGPL3.0-or-later
+ */
+/**
+ * @author Bartlomiej Polot
+ * @file regex/regex_block_lib.c
+ * @brief functions for manipulating non-accept blocks stored for
+ *        regex in the DHT
+ */
+#include "platform.h"
+#include "regex_block_lib.h"
+#include "gnunet_constants.h"
+
+#define LOG(kind, ...) GNUNET_log_from (kind, "regex-bck", __VA_ARGS__)
+
+GNUNET_NETWORK_STRUCT_BEGIN
+
+/**
+ * Information for each edge.
+ */
+struct EdgeInfo
+{
+  /**
+   * Index of the destination of this edge in the
+   * unique destinations array.
+   */
+  uint16_t destination_index GNUNET_PACKED;
+
+  /**
+   * Number of bytes the token for this edge takes in the
+   * token area.
+   */
+  uint16_t token_length GNUNET_PACKED;
+};
+
+
+/**
+ * @brief Block to announce a regex state.
+ */
+struct RegexBlock
+{
+  /**
+   * Length of the proof regex string.
+   */
+  uint16_t proof_len GNUNET_PACKED;
+
+  /**
+   * Is this state an accepting state?
+   */
+  int16_t is_accepting GNUNET_PACKED;
+
+  /**
+   * Number of edges parting from this state.
+   */
+  uint16_t num_edges GNUNET_PACKED;
+
+  /**
+   * Number of unique destinations reachable from this state.
+   */
+  uint16_t num_destinations GNUNET_PACKED;
+
+  /* followed by 'struct GNUNET_HashCode[num_destinations]' */
+
+  /* followed by 'struct EdgeInfo[edge_destination_indices]' */
+
+  /* followed by 'char proof[n_proof]', NOT 0-terminated */
+
+  /* followed by 'char tokens[num_edges][edge_info[k].token_length]';
+     essentially all of the tokens one after the other in the
+     order of the edges; tokens are NOT 0-terminated */
+};
+
+
+GNUNET_NETWORK_STRUCT_END
+
+
+/**
+ * Test if this block is marked as being an accept state.
+ *
+ * @param block block to test
+ * @param size number of bytes in block
+ * @return #GNUNET_YES if the block is accepting, #GNUNET_NO if not
+ */
+int
+GNUNET_BLOCK_is_accepting (const struct RegexBlock *block,
+                           size_t size)
+{
+  if (size < sizeof(struct RegexBlock))
+  {
+    GNUNET_break_op (0);
+    return GNUNET_SYSERR;
+  }
+  return ntohs (block->is_accepting);
+}
+
+
+int
+REGEX_BLOCK_check_proof (const char *proof,
+                         size_t proof_len,
+                         const struct GNUNET_HashCode *key)
+{
+  struct GNUNET_HashCode key_check;
+
+  if ((NULL == proof) || (NULL == key))
+  {
+    GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Proof check failed, was NULL.\n");
+    return GNUNET_NO;
+  }
+  GNUNET_CRYPTO_hash (proof, proof_len, &key_check);
+  return (0 ==
+          GNUNET_CRYPTO_hash_cmp (key, &key_check)) ? GNUNET_OK : GNUNET_NO;
+}
+
+
+/**
+ * Struct to keep track of the xquery while iterating all the edges in a block.
+ */
+struct CheckEdgeContext
+{
+  /**
+   * Xquery: string we are looking for.
+   */
+  const char *xquery;
+
+  /**
+   * Has any edge matched the xquery so far? (GNUNET_OK / GNUNET_NO)
+   */
+  int found;
+};
+
+
+/**
+ * Iterator over all edges in a block, checking for a presence of a given query.
+ *
+ * @param cls Closure, (xquery context).
+ * @param token Token that follows to next state.
+ * @param len Length of token.
+ * @param key Hash of next state.
+ *
+ * @return #GNUNET_YES, to keep iterating
+ */
+static int
+check_edge (void *cls,
+            const char *token,
+            size_t len,
+            const struct GNUNET_HashCode *key)
+{
+  struct CheckEdgeContext *ctx = cls;
+
+  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
+              "edge %.*s [%u]: %s\n",
+              (int) len,
+              token,
+              (unsigned int) len,
+              GNUNET_h2s (key));
+  if (NULL == ctx->xquery)
+    return GNUNET_YES;
+  if (strlen (ctx->xquery) < len)
+    return GNUNET_YES; /* too long */
+  if (0 == strncmp (ctx->xquery, token, len))
+    ctx->found = GNUNET_OK;
+  return GNUNET_YES; /* keep checking for malformed data! */
+}
+
+
+int
+REGEX_BLOCK_check (const struct RegexBlock *block,
+                   size_t size,
+                   const struct GNUNET_HashCode *query,
+                   const char *xquery)
+{
+  struct GNUNET_HashCode key;
+  struct CheckEdgeContext ctx;
+  int res;
+
+  LOG (GNUNET_ERROR_TYPE_DEBUG,
+       "Block check\n");
+  if (GNUNET_OK !=
+      REGEX_BLOCK_get_key (block, size,
+                           &key))
+  {
+    GNUNET_break_op (0);
+    return GNUNET_SYSERR;
+  }
+  if ((NULL != query) &&
+      (0 != GNUNET_memcmp (&key,
+                           query)) )
+  {
+    GNUNET_break_op (0);
+    return GNUNET_SYSERR;
+  }
+  if ((GNUNET_YES == ntohs (block->is_accepting)) &&
+      ((NULL == xquery) || ('\0' == xquery[0])))
+  {
+    LOG (GNUNET_ERROR_TYPE_DEBUG,
+         "  out! Is accepting: %u, xquery %p\n",
+         ntohs (block->is_accepting),
+         xquery);
+    return GNUNET_OK;
+  }
+  ctx.xquery = xquery;
+  ctx.found = GNUNET_NO;
+  res = REGEX_BLOCK_iterate (block, size, &check_edge, &ctx);
+  if (GNUNET_SYSERR == res)
+    return GNUNET_SYSERR;
+  if (NULL == xquery)
+    return GNUNET_YES;
+  LOG (GNUNET_ERROR_TYPE_DEBUG, "Result %d\n", ctx.found);
+  return ctx.found;
+}
+
+
+int
+REGEX_BLOCK_get_key (const struct RegexBlock *block,
+                     size_t block_len,
+                     struct GNUNET_HashCode *key)
+{
+  uint16_t len;
+  const struct GNUNET_HashCode *destinations;
+  const struct EdgeInfo *edges;
+  uint16_t num_destinations;
+  uint16_t num_edges;
+  size_t total;
+
+  if (block_len < sizeof(struct RegexBlock))
+  {
+    GNUNET_break_op (0);
+    return GNUNET_SYSERR;
+  }
+  num_destinations = ntohs (block->num_destinations);
+  num_edges = ntohs (block->num_edges);
+  len = ntohs (block->proof_len);
+  destinations = (const struct GNUNET_HashCode *) &block[1];
+  edges = (const struct EdgeInfo *) &destinations[num_destinations];
+  total = sizeof(struct RegexBlock) + num_destinations * sizeof(struct
+                                                                GNUNET_HashCode)
+          + num_edges * sizeof(struct EdgeInfo) + len;
+  if (block_len < total)
+  {
+    GNUNET_break_op (0);
+    return GNUNET_SYSERR;
+  }
+  GNUNET_CRYPTO_hash (&edges[num_edges], len, key);
+  return GNUNET_OK;
+}
+
+
+int
+REGEX_BLOCK_iterate (const struct RegexBlock *block,
+                     size_t size,
+                     REGEX_INTERNAL_EgdeIterator iterator,
+                     void *iter_cls)
+{
+  uint16_t len;
+  const struct GNUNET_HashCode *destinations;
+  const struct EdgeInfo *edges;
+  const char *aux;
+  uint16_t num_destinations;
+  uint16_t num_edges;
+  size_t total;
+  unsigned int n;
+  size_t off;
+
+  LOG (GNUNET_ERROR_TYPE_DEBUG, "Block iterate\n");
+  if (size < sizeof(struct RegexBlock))
+  {
+    GNUNET_break_op (0);
+    return GNUNET_SYSERR;
+  }
+  num_destinations = ntohs (block->num_destinations);
+  num_edges = ntohs (block->num_edges);
+  len = ntohs (block->proof_len);
+  destinations = (const struct GNUNET_HashCode *) &block[1];
+  edges = (const struct EdgeInfo *) &destinations[num_destinations];
+  aux = (const char *) &edges[num_edges];
+  total = sizeof(struct RegexBlock) + num_destinations * sizeof(struct
+                                                                GNUNET_HashCode)
+          + num_edges * sizeof(struct EdgeInfo) + len;
+  if (size < total)
+  {
+    GNUNET_break_op (0);
+    return GNUNET_SYSERR;
+  }
+  for (n = 0; n < num_edges; n++)
+    total += ntohs (edges[n].token_length);
+  if (size != total)
+  {
+    fprintf (stderr, "Expected %u, got %u\n",
+             (unsigned int) size,
+             (unsigned int) total);
+    GNUNET_break_op (0);
+    return GNUNET_SYSERR;
+  }
+  off = len;
+  LOG (GNUNET_ERROR_TYPE_DEBUG,
+       "Start iterating block of size %lu, proof %u, off %lu edges %u\n",
+       (unsigned long) size, len, (unsigned long) off, n);
+  /* &aux[off] always points to our token */
+  for (n = 0; n < num_edges; n++)
+  {
+    LOG (GNUNET_ERROR_TYPE_DEBUG,
+         "Edge %u/%u, off %lu tokenlen %u (%.*s)\n",
+         n + 1, num_edges, (unsigned long) off,
+         ntohs (edges[n].token_length), ntohs (edges[n].token_length),
+         &aux[off]);
+    if (NULL != iterator)
+      if (GNUNET_NO == iterator (iter_cls,
+                                 &aux[off],
+                                 ntohs (edges[n].token_length),
+                                 &destinations[ntohs (
+                                                 edges[n].destination_index)]))
+        return GNUNET_OK;
+    off += ntohs (edges[n].token_length);
+  }
+  return GNUNET_OK;
+}
+
+
+/**
+ * Construct a regex block to be stored in the DHT.
+ *
+ * @param proof proof string for the block
+ * @param num_edges number of edges in the block
+ * @param edges the edges of the block
+ * @param accepting is this an accepting state
+ * @param rsize set to the size of the returned block (OUT-only)
+ * @return the regex block, NULL on error
+ */
+struct RegexBlock *
+REGEX_BLOCK_create (const char *proof,
+                    unsigned int num_edges,
+                    const struct REGEX_BLOCK_Edge *edges,
+                    int accepting,
+                    size_t *rsize)
+{
+  struct RegexBlock *block;
+  struct GNUNET_HashCode destinations[1024]; /* 1024 = 64k/64 bytes/key == absolute MAX */
+  uint16_t destination_indices[num_edges];
+  struct GNUNET_HashCode *dests;
+  struct EdgeInfo *edgeinfos;
+  size_t off;
+  size_t len;
+  size_t total;
+  size_t slen;
+  unsigned int unique_destinations;
+  unsigned int j;
+  unsigned int i;
+  char *aux;
+
+  len = strlen (proof);
+  if (len > UINT16_MAX)
+  {
+    GNUNET_break (0);
+    return NULL;
+  }
+  unique_destinations = 0;
+  total = sizeof(struct RegexBlock) + len;
+  for (i = 0; i < num_edges; i++)
+  {
+    slen = strlen (edges[i].label);
+    if (slen > UINT16_MAX)
+    {
+      GNUNET_break (0);
+      return NULL;
+    }
+    total += slen;
+    for (j = 0; j < unique_destinations; j++)
+      if (0 == memcmp (&destinations[j],
+                       &edges[i].destination,
+                       sizeof(struct GNUNET_HashCode)))
+        break;
+    if (j >= 1024)
+    {
+      GNUNET_break (0);
+      return NULL;
+    }
+    destination_indices[i] = j;
+    if (j == unique_destinations)
+      destinations[unique_destinations++] = edges[i].destination;
+  }
+  total += num_edges * sizeof(struct EdgeInfo) + unique_destinations
+           * sizeof(struct GNUNET_HashCode);
+  if (total >= GNUNET_CONSTANTS_MAX_BLOCK_SIZE)
+  {
+    GNUNET_break (0);
+    return NULL;
+  }
+  block = GNUNET_malloc (total);
+  block->proof_len = htons (len);
+  block->is_accepting = htons (accepting);
+  block->num_edges = htons (num_edges);
+  block->num_destinations = htons (unique_destinations);
+  dests = (struct GNUNET_HashCode *) &block[1];
+  GNUNET_memcpy (dests, destinations, sizeof(struct GNUNET_HashCode)
+                 * unique_destinations);
+  edgeinfos = (struct EdgeInfo *) &dests[unique_destinations];
+  aux = (char *) &edgeinfos[num_edges];
+  off = len;
+  GNUNET_memcpy (aux, proof, len);
+  for (i = 0; i < num_edges; i++)
+  {
+    slen = strlen (edges[i].label);
+    edgeinfos[i].token_length = htons ((uint16_t) slen);
+    edgeinfos[i].destination_index = htons (destination_indices[i]);
+    GNUNET_memcpy (&aux[off],
+                   edges[i].label,
+                   slen);
+    off += slen;
+  }
+  *rsize = total;
+  return block;
+}
+
+
+/* end of regex_block_lib.c */