refactoring publishing code

6 files changed, 751 insertions, 263 deletions

diff --git a/src/fs/Makefile.am b/src/fs/Makefile.am
index ebe6790c9..d4da86e6d 100644
--- a/src/fs/Makefile.am
+++ b/src/fs/Makefile.am
@@ -23,6 +23,7 @@ libgnunetfs_la_SOURCES = \
   fs_publish.c \
   fs_namespace.c \
   fs_search.c \
+  fs_tree.c fs_tree.h \
   fs_unindex.c \
   fs_uri.c 
 
diff --git a/src/fs/fs.h b/src/fs/fs.h
index 956048cc5..c8712b492 100644
--- a/src/fs/fs.h
+++ b/src/fs/fs.h
@@ -250,7 +250,12 @@ struct GNUNET_FS_FileInformation
    * entries for the size of the file and
    * finally freed once the upload is complete.
    */
-  struct ContentHashKey *chk_tree;
+  // struct ContentHashKey *chk_tree;
+  
+  /**
+   * Encoder being used to publish this file.
+   */
+  struct GNUNET_FS_TreeEncoder *te;
 
   /**
    * Error message (non-NULL if this operation
@@ -261,20 +266,20 @@ struct GNUNET_FS_FileInformation
   /**
    * Number of entries in "chk_tree".
    */
-  unsigned int chk_tree_depth;
+  // unsigned int chk_tree_depth;
 
   /**
    * Depth in the CHK-tree at which we are
    * currently publishing.  0 is the root
    * of the tree.
    */
-  unsigned int current_depth;
+  // unsigned int current_depth;
 
   /**
    * How many bytes of this file or directory have been
    * published so far?
    */
-  uint64_t publish_offset;
+  // uint64_t publish_offset;
 
   /**
    * Data describing either the file or the directory.
diff --git a/src/fs/fs_file_information.c b/src/fs/fs_file_information.c
index 984d56f30..5de9cbeb8 100644
--- a/src/fs/fs_file_information.c
+++ b/src/fs/fs_file_information.c
@@ -701,7 +701,6 @@ GNUNET_FS_file_information_add (struct GNUNET_FS_FileInformation *dir,
   ent->next = dir->data.dir.entries;
   dir->data.dir.entries = ent;
   dir->data.dir.dir_size = 0;
-  dir->publish_offset = 0;
   GNUNET_FS_file_information_sync (ent);
   GNUNET_FS_file_information_sync (dir);
   return GNUNET_OK;
@@ -824,7 +823,6 @@ GNUNET_FS_file_information_destroy (struct GNUNET_FS_FileInformation *fi,
                &fi->client_info);
     }
   GNUNET_free_non_null (fi->emsg);
-  GNUNET_free_non_null (fi->chk_tree);
   /* clean up serialization */
   if (0 != UNLINK (fi->serialization))
     GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_WARNING,
diff --git a/src/fs/fs_publish.c b/src/fs/fs_publish.c
index 0c950f38a..6080fae03 100644
--- a/src/fs/fs_publish.c
+++ b/src/fs/fs_publish.c
@@ -26,8 +26,8 @@
  * @author Christian Grothoff
  *
  * TODO:
+ * - code-sharing with unindex (write unindex code, clean up new FIXME's)
  * - indexing cleanup: unindex on failure (can wait)
- * - code-sharing with unindex (can wait)
  * - persistence support (can wait)
  * - datastore reservation support (optimization)
  * - location URIs (publish with anonymity-level zero)
@@ -39,6 +39,7 @@
 #include "gnunet_util_lib.h"
 #include "gnunet_fs_service.h"
 #include "fs.h"
+#include "fs_tree.h"
 
 #define DEBUG_PUBLISH GNUNET_YES
 
@@ -110,12 +111,14 @@ make_publish_status (struct GNUNET_FS_ProgressInfo *pi,
     = (NULL == p->dir) ? NULL : p->dir->client_info;
   pi->value.publish.size
     = (p->is_directory) ? p->data.dir.dir_size : p->data.file.file_size;
+#if FIXME
   pi->value.publish.eta 
     = GNUNET_TIME_calculate_eta (p->start_time,
                                  p->publish_offset,
                                  pi->value.publish.size);
-  pi->value.publish.duration = GNUNET_TIME_absolute_get_duration (p->start_time);
   pi->value.publish.completed = p->publish_offset;
+#endif
+  pi->value.publish.duration = GNUNET_TIME_absolute_get_duration (p->start_time);
   pi->value.publish.anonymity = p->anonymity;
 }
 
@@ -302,7 +305,8 @@ publish_sblock (struct GNUNET_FS_PublishContext *sc)
  * the result and continue the larger
  * upload.
  *
- * @param cls the "struct GNUNET_FS_PublishContext*" of the larger upload
+ * @param cls the "struct GNUNET_FS_PublishContext*"
+ *        of the larger upload
  * @param uri URI of the published blocks
  * @param emsg NULL on success, otherwise error message
  */
@@ -346,98 +350,198 @@ publish_kblocks_cont (void *cls,
 }
 
 
-/**
- * Compute the depth of the CHK tree.
- *
- * @param flen file length for which to compute the depth
- * @return depth of the tree
- */
-static unsigned int
-compute_depth (uint64_t flen)
+// FIXME: document
+static size_t
+block_reader (void *cls,
+              uint64_t offset,
+              size_t max, 
+              void *buf,
+              char **emsg)
 {
-  unsigned int treeDepth;
-  uint64_t fl;
+  struct GNUNET_FS_PublishContext *sc = cls;
+  struct GNUNET_FS_FileInformation *p;
+  uint16_t pt_size;
+  const char *dd;
+
+  p = sc->fi_pos;
+  if (p->is_directory)
+    {
+      pt_size = GNUNET_MIN(max,
+                           p->data.dir.dir_size - offset);
+      dd = p->data.dir.dir_data;
+      memcpy (&buf,
+              &dd[offset],
+              pt_size);
+    }
+  else
+    {
+      pt_size = GNUNET_MIN(max,
+                           p->data.file.file_size - offset);
+      if (pt_size !=
+          p->data.file.reader (p->data.file.reader_cls,
+                               offset,
+                               pt_size,
+                               buf,
+                               emsg))
+        return 0;
+    }
+  return pt_size;
+}
 
-  treeDepth = 1;
-  fl = DBLOCK_SIZE;
-  while (fl < flen)
+
+// FIXME: document
+static void 
+encode_cont (void *cls,
+             const struct GNUNET_SCHEDULER_TaskContext *tc)
+{
+  struct GNUNET_FS_PublishContext *sc = cls;
+  struct GNUNET_FS_FileInformation *p;
+  struct GNUNET_FS_ProgressInfo pi;
+  char *emsg;
+  
+  p = sc->fi_pos;
+  GNUNET_FS_tree_encoder_finish (p->te,
+                                 &p->chk_uri,
+                                 &emsg);
+  p->te = NULL;
+  if (NULL != emsg)
     {
-      treeDepth++;
-      if (fl * CHK_PER_INODE < fl)
-        {
-          /* integer overflow, this is a HUGE file... */
-          return treeDepth;
-        }
-      fl = fl * CHK_PER_INODE;
+      GNUNET_asprintf (&p->emsg, 
+                       _("Upload failed: %s"),
+                       emsg);
+      GNUNET_free (emsg);
+      GNUNET_FS_file_information_sync (p);
+      pi.status = GNUNET_FS_STATUS_PUBLISH_ERROR;
+      make_publish_status (&pi, sc, p);
+      pi.value.publish.eta = GNUNET_TIME_UNIT_FOREVER_REL;
+      pi.value.publish.specifics.error.message = p->emsg;
+      p->client_info
+        = sc->h->upcb (sc->h->upcb_cls,
+                       &pi);
     }
-  return treeDepth;
+  /* continue with main */
+  sc->upload_task 
+    = GNUNET_SCHEDULER_add_delayed (sc->h->sched,
+                                    GNUNET_NO,
+                                    GNUNET_SCHEDULER_PRIORITY_BACKGROUND,
+                                    GNUNET_SCHEDULER_NO_TASK,
+                                    GNUNET_TIME_UNIT_ZERO,
+                                    &do_upload,
+                                    sc);
 }
 
 
 /**
- * Compute the size of the current IBlock.
+ * Function called asking for the current (encoded)
+ * block to be processed.  After processing the
+ * client should either call "GNUNET_FS_tree_encode_next"
+ * or (on error) "GNUNET_FS_tree_encode_finish".
  *
- * @param height height of the IBlock in the tree (aka overall
- *               number of tree levels minus depth); 0 == DBlock
- * @param offset current offset in the overall file
- * @return size of the corresponding IBlock
+ * @param cls closure
+ * @param query the query for the block (key for lookup in the datastore)
+ * @param type type of the block (IBLOCK or DBLOCK)
+ * @param block the (encrypted) block
+ * @param block_size size of block (in bytes)
  */
-static uint16_t 
-compute_iblock_size (unsigned int height,
-                     uint64_t offset)
+static void 
+block_proc (void *cls,
+            const GNUNET_HashCode *query,
+            uint64_t offset,
+            unsigned int type,
+            const void *block,
+            uint16_t block_size)
 {
-  unsigned int ret;
-  unsigned int i;
-  uint64_t mod;
-  uint64_t bds;
-
-  GNUNET_assert (height > 0);
-  bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i"
-                                  corresponds to */
-  for (i=0;i<height;i++)
-    bds *= CHK_PER_INODE;
-  mod = offset % bds;
-  if (0 == mod)
+  struct GNUNET_FS_PublishContext *sc = cls;
+  struct GNUNET_FS_FileInformation *p;
+  struct PutContCtx * dpc_cls;
+  struct OnDemandBlock odb;
+
+  p = sc->fi_pos;
+  if (NULL == sc->dsh)
     {
-      /* we were triggered at the end of a full block */
-      ret = CHK_PER_INODE;
+      sc->upload_task
+        = GNUNET_SCHEDULER_add_delayed (sc->h->sched,
+                                        GNUNET_NO,
+                                        GNUNET_SCHEDULER_PRIORITY_BACKGROUND,
+                                        GNUNET_SCHEDULER_NO_TASK,
+                                        GNUNET_TIME_UNIT_ZERO,
+                                        &do_upload,
+                                        sc);
+      return;
     }
-  else
+  
+  GNUNET_assert (GNUNET_NO == sc->in_network_wait);
+  sc->in_network_wait = GNUNET_YES;
+  dpc_cls = GNUNET_malloc(sizeof(struct PutContCtx));
+  dpc_cls->cont = &do_upload;
+  dpc_cls->cont_cls = sc;
+  dpc_cls->p = p;
+  if ( (p->is_directory) &&
+       (p->data.file.do_index) &&
+       (type == GNUNET_DATASTORE_BLOCKTYPE_DBLOCK) )
     {
-      /* we were triggered at the end of the file */
-      bds /= CHK_PER_INODE;
-      ret = mod / bds;
-      if (0 != mod % bds)
-        ret++; 
+      odb.offset = offset;
+      odb.file_id = p->data.file.file_id;
+      GNUNET_DATASTORE_put (sc->dsh,
+                            sc->rid,
+                            query,
+                            sizeof(struct OnDemandBlock),
+                            &odb,
+                            GNUNET_DATASTORE_BLOCKTYPE_ONDEMAND,
+                            p->priority,
+                            p->anonymity,
+                            p->expirationTime,
+                            GNUNET_CONSTANTS_SERVICE_TIMEOUT,
+                            &ds_put_cont,
+                            dpc_cls);     
+      return;
     }
-  return (uint16_t) (ret * sizeof(struct ContentHashKey));
+  GNUNET_DATASTORE_put (sc->dsh,
+                        sc->rid,
+                        query,
+                        block_size,
+                        block,
+                        type,
+                        p->priority,
+                        p->anonymity,
+                        p->expirationTime,
+                        GNUNET_CONSTANTS_SERVICE_TIMEOUT,
+                        &ds_put_cont,
+                        dpc_cls);
 }
 
 
 /**
- * Compute the offset of the CHK for the
- * current block in the IBlock above.
+ * Function called with information about our
+ * progress in computing the tree encoding.
  *
- * @param height height of the IBlock in the tree (aka overall
- *               number of tree levels minus depth); 0 == DBlock
- * @param offset current offset in the overall file
- * @return (array of CHKs') offset in the above IBlock
+ * @param cls closure
+ * @param offset where are we in the file
+ * @param pt_block plaintext of the currently processed block
+ * @param pt_size size of pt_block
+ * @param depth depth of the block in the tree
  */
-static unsigned int
-compute_chk_offset (unsigned int height,
-                    uint64_t offset)
-{
-  uint64_t bds;
-  unsigned int ret;
-  unsigned int i;
+static void 
+progress_proc (void *cls,
+               uint64_t offset,
+               const void *pt_block,
+               size_t pt_size,
+               unsigned int depth)
+{                      
+  struct GNUNET_FS_PublishContext *sc = cls;
+  struct GNUNET_FS_FileInformation *p;
+  struct GNUNET_FS_ProgressInfo pi;
 
-  bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i"
-                                  corresponds to */
-  for (i=0;i<height;i++)
-    bds *= CHK_PER_INODE;
-  GNUNET_assert (0 == (offset % bds));
-  ret = offset / bds;
-  return ret % CHK_PER_INODE; 
+  p = sc->fi_pos;
+  pi.status = GNUNET_FS_STATUS_PUBLISH_PROGRESS;
+  make_publish_status (&pi, sc, p);
+  pi.value.publish.specifics.progress.data = pt_block;
+  pi.value.publish.specifics.progress.offset = offset;
+  pi.value.publish.specifics.progress.data_len = pt_size;
+  // FIXME: add depth to pi
+  p->client_info 
+    = sc->h->upcb (sc->h->upcb_cls,
+                   &pi);
 }
 
 
@@ -450,32 +554,18 @@ compute_chk_offset (unsigned int height,
  * @param p specific file or directory for which kblocks
  *          should be created
  */
+// FIXME: "p" argument is not needed!
 static void
 publish_content (struct GNUNET_FS_PublishContext *sc,
                  struct GNUNET_FS_FileInformation *p)
 {
-  struct GNUNET_FS_ProgressInfo pi;
-  struct ContentHashKey *mychk;
-  const void *pt_block;
-  uint16_t pt_size;
   char *emsg;
-  char iob[DBLOCK_SIZE];
-  char enc[DBLOCK_SIZE];
-  struct GNUNET_CRYPTO_AesSessionKey sk;
-  struct GNUNET_CRYPTO_AesInitializationVector iv;
-  uint64_t size;
-  unsigned int off;
   struct GNUNET_FS_DirectoryBuilder *db;
   struct GNUNET_FS_FileInformation *dirpos;
   void *raw_data;
-  char *dd;
-  struct PutContCtx * dpc_cls;
-  struct OnDemandBlock odb;
+  uint64_t size;
 
-  // FIXME: figure out how to share this code
-  // with unindex!
-  size = (p->is_directory) ? p->data.dir.dir_size : p->data.file.file_size;
-  if (NULL == p->chk_tree)
+  if (NULL == p->te)
     {
       if (p->is_directory)
         {
@@ -509,7 +599,7 @@ publish_content (struct GNUNET_FS_PublishContext *sc,
                         } 
                     }
                 }
-      GNUNET_FS_directory_builder_add (db,
+              GNUNET_FS_directory_builder_add (db,
                                                dirpos->chk_uri,
                                                dirpos->meta,
                                                raw_data);
@@ -519,177 +609,23 @@ publish_content (struct GNUNET_FS_PublishContext *sc,
           GNUNET_FS_directory_builder_finish (db,
                                               &p->data.dir.dir_size,
                                               &p->data.dir.dir_data);
-          size = p->data.dir.dir_size;
-        }
-      p->chk_tree_depth = compute_depth (size);
-      p->chk_tree = GNUNET_malloc (p->chk_tree_depth * 
-                                   sizeof (struct ContentHashKey) *
-                                   CHK_PER_INODE);
-      p->current_depth = p->chk_tree_depth;
-    }
-  if (p->current_depth == p->chk_tree_depth)
-    {
-      if (p->is_directory)
-        {
-          pt_size = GNUNET_MIN(DBLOCK_SIZE,
-                               p->data.dir.dir_size - p->publish_offset);
-          dd = p->data.dir.dir_data;
-          pt_block = &dd[p->publish_offset];
-        }
-      else
-        {
-          pt_size = GNUNET_MIN(DBLOCK_SIZE,
-                               p->data.file.file_size - p->publish_offset);
-          emsg = NULL;
-          if (pt_size !=
-              p->data.file.reader (p->data.file.reader_cls,
-                                   p->publish_offset,
-                                   pt_size,
-                                   iob,
-                                   &emsg))
-            {
-              GNUNET_asprintf (&p->emsg, 
-                               _("Upload failed: %s"),
-                               emsg);
-              GNUNET_free (emsg);
-              GNUNET_FS_file_information_sync (p);
-              pi.status = GNUNET_FS_STATUS_PUBLISH_ERROR;
-              make_publish_status (&pi, sc, p);
-              pi.value.publish.eta = GNUNET_TIME_UNIT_FOREVER_REL;
-              pi.value.publish.specifics.error.message = p->emsg;
-              p->client_info
-                = sc->h->upcb (sc->h->upcb_cls,
-                               &pi);
-              /* continue with main (to propagate error up) */
-              sc->upload_task 
-                = GNUNET_SCHEDULER_add_delayed (sc->h->sched,
-                                                GNUNET_NO,
-                                                GNUNET_SCHEDULER_PRIORITY_BACKGROUND,
-                                                GNUNET_SCHEDULER_NO_TASK,
-                                                GNUNET_TIME_UNIT_ZERO,
-                                                &do_upload,
-                                                sc);
-              return;
-            }
-          pt_block = iob;
         }
+      size = (p->is_directory) 
+        ? p->data.dir.dir_size 
+        : p->data.file.file_size;
+      p->te = GNUNET_FS_tree_encoder_create (sc->h,
+                                             size,
+                                             sc,
+                                             &block_reader,
+                                             &block_proc,
+                                             &progress_proc,
+                                             &encode_cont);
+
     }
-  else
-    {
-      pt_size = compute_iblock_size (p->chk_tree_depth - p->current_depth,
-                                     p->publish_offset); 
-      pt_block = &p->chk_tree[p->current_depth *
-                              CHK_PER_INODE];
-    }
-  off = compute_chk_offset (p->chk_tree_depth - p->current_depth,
-                            p->publish_offset);
-  mychk = &p->chk_tree[(p->current_depth-1)*CHK_PER_INODE+off];
-  GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
-  GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
-  GNUNET_CRYPTO_aes_encrypt (pt_block,
-                             pt_size,
-                             &sk,
-                             &iv,
-                             enc);
-  // NOTE: this block below is all that really differs
-  // between publish/unindex!  Parameterize & move this code!
-  if (NULL == sc->dsh)
-    {
-      sc->upload_task
-        = GNUNET_SCHEDULER_add_delayed (sc->h->sched,
-                                        GNUNET_NO,
-                                        GNUNET_SCHEDULER_PRIORITY_BACKGROUND,
-                                        GNUNET_SCHEDULER_NO_TASK,
-                                        GNUNET_TIME_UNIT_ZERO,
-                                        &do_upload,
-                                        sc);
-    }
-  else
-    {
-      GNUNET_assert (GNUNET_NO == sc->in_network_wait);
-      sc->in_network_wait = GNUNET_YES;
-      dpc_cls = GNUNET_malloc(sizeof(struct PutContCtx));
-      dpc_cls->cont = &do_upload;
-      dpc_cls->cont_cls = sc;
-      dpc_cls->p = p;
-      if ( (p->is_directory) &&
-           (p->data.file.do_index) &&
-           (p->current_depth == p->chk_tree_depth) )
-        {
-          odb.offset = p->publish_offset;
-          odb.file_id = p->data.file.file_id;
-          GNUNET_DATASTORE_put (sc->dsh,
-                                sc->rid,
-                                &mychk->query,
-                                sizeof(struct OnDemandBlock),
-                                &odb,
-                                GNUNET_DATASTORE_BLOCKTYPE_ONDEMAND,
-                                p->priority,
-                                p->anonymity,
-                                p->expirationTime,
-                                GNUNET_CONSTANTS_SERVICE_TIMEOUT,
-                                &ds_put_cont,
-                                dpc_cls);         
-        }
-      else
-        {
-          GNUNET_DATASTORE_put (sc->dsh,
-                                sc->rid,
-                                &mychk->query,
-                                pt_size,
-                                enc,
-                                (p->current_depth == p->chk_tree_depth) 
-                                ? GNUNET_DATASTORE_BLOCKTYPE_DBLOCK 
-                                : GNUNET_DATASTORE_BLOCKTYPE_IBLOCK,
-                                p->priority,
-                                p->anonymity,
-                                p->expirationTime,
-                                GNUNET_CONSTANTS_SERVICE_TIMEOUT,
-                                &ds_put_cont,
-                                dpc_cls);
-        }
-    }
-  if (p->current_depth == p->chk_tree_depth)
-    {
-      pi.status = GNUNET_FS_STATUS_PUBLISH_PROGRESS;
-      make_publish_status (&pi, sc, p);
-      pi.value.publish.specifics.progress.data = pt_block;
-      pi.value.publish.specifics.progress.offset = p->publish_offset;
-      pi.value.publish.specifics.progress.data_len = pt_size;
-      p->client_info 
-        = sc->h->upcb (sc->h->upcb_cls,
-                       &pi);
-    }
-  GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
-  if (p->current_depth == p->chk_tree_depth) 
-    { 
-      p->publish_offset += pt_size;
-      if ( (p->publish_offset == size) ||
-           (0 == p->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE) ) )
-        p->current_depth--;
-    }
-  else
-    {
-      if ( (off == CHK_PER_INODE) ||
-           (p->publish_offset == size) )
-        p->current_depth--;
-      else
-        p->current_depth = p->chk_tree_depth;
-    }
-  if (0 == p->current_depth)
-    {
-      p->chk_uri = GNUNET_malloc (sizeof(struct GNUNET_FS_Uri));
-      p->chk_uri->type = chk;
-      p->chk_uri->data.chk.chk = p->chk_tree[0];
-      p->chk_uri->data.chk.file_length = size;
-      GNUNET_free (p->chk_tree);
-      p->chk_tree = NULL;
-    }
+  GNUNET_FS_tree_encoder_next (p->te);
 }
 
 
-
-
 /**
  * Process the response (or lack thereof) from
  * the "fs" service to our 'start index' request.
diff --git a/src/fs/fs_tree.c b/src/fs/fs_tree.c
new file mode 100644
index 000000000..5d6a4f1d9
--- /dev/null
+++ b/src/fs/fs_tree.c
@@ -0,0 +1,381 @@
+/*
+     This file is part of GNUnet.
+     (C) 2009 Christian Grothoff (and other contributing authors)
+
+     GNUnet 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, 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
+     General Public License for more details.
+
+     You should have received a copy of the GNU General Public License
+     along with GNUnet; see the file COPYING.  If not, write to the
+     Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+     Boston, MA 02111-1307, USA.
+*/
+/**
+ * @file fs/fs_tree.c
+ * @brief Merkle-tree-ish-CHK file encoding for GNUnet
+ * @see http://gnunet.org/encoding.php3
+ * @author Krista Bennett
+ * @author Christian Grothoff
+ *
+ * TODO:
+ * - decide if this API should be made public (gnunet_fs_service.h)
+ *   or remain "internal" (but with exported symbols?)
+ */
+#include "platform.h"
+#include "fs_tree.h"
+
+
+/**
+ * Context for an ECRS-based file encoder that computes
+ * the Merkle-ish-CHK tree.
+ */
+struct GNUNET_FS_TreeEncoder
+{
+
+  /**
+   * Global FS context.
+   */
+  struct GNUNET_FS_Handle *h;
+  
+  /**
+   * Closure for all callbacks.
+   */
+  void *cls;
+
+  /**
+   * Function to call on encrypted blocks.
+   */
+  GNUNET_FS_TreeBlockProcessor proc;
+
+  /**
+   * Function to call with progress information.
+   */
+  GNUNET_FS_TreeProgressCallback progress;
+
+  /**
+   * Function to call to receive input data.
+   */
+  GNUNET_FS_DataReader reader;
+
+  /**
+   * Function to call once we're done with processing.
+   */
+  GNUNET_SCHEDULER_Task cont;
+  
+  /**
+   * Set to an error message (if we had an error).
+   */
+  char *emsg;
+
+  /**
+   * Set to the URI (upon successful completion)
+   */
+  struct GNUNET_FS_Uri *uri;
+  
+  /**
+   * Overall file size.
+   */
+  uint64_t size;
+
+  /**
+   * How far are we?
+   */
+  uint64_t publish_offset;
+
+  /**
+   * How deep are we?
+   */
+  unsigned int current_depth;
+
+  /**
+   * How deep is the tree?
+   */
+  unsigned int chk_tree_depth;
+
+  /**
+   * In-memory cache of the current CHK tree.
+   * This struct will contain the CHK values
+   * from the root to the currently processed
+   * node in the tree as identified by 
+   * "current_depth" and "publish_offset".
+   * The "chktree" will be initially NULL,
+   * then allocated to a sufficient number of
+   * entries for the size of the file and
+   * finally freed once the upload is complete.
+   */
+  struct ContentHashKey *chk_tree;
+
+};
+
+
+/**
+ * Compute the depth of the CHK tree.
+ *
+ * @param flen file length for which to compute the depth
+ * @return depth of the tree
+ */
+static unsigned int
+compute_depth (uint64_t flen)
+{
+  unsigned int treeDepth;
+  uint64_t fl;
+
+  treeDepth = 1;
+  fl = DBLOCK_SIZE;
+  while (fl < flen)
+    {
+      treeDepth++;
+      if (fl * CHK_PER_INODE < fl)
+        {
+          /* integer overflow, this is a HUGE file... */
+          return treeDepth;
+        }
+      fl = fl * CHK_PER_INODE;
+    }
+  return treeDepth;
+}
+
+
+/**
+ * Initialize a tree encoder.  This function will call "proc" and
+ * "progress" on each block in the tree.  Once all blocks have been
+ * processed, "cont" will be scheduled.  The "reader" will be called
+ * to obtain the (plaintext) blocks for the file.  Note that this
+ * function will not actually call "proc".  The client must
+ * call "GNUNET_FS_tree_encoder_next" to trigger encryption (and
+ * calling of "proc") for the each block.
+ *
+ * @param h the global FS context
+ * @param size overall size of the file to encode
+ * @param cls closure for reader, proc, progress and cont
+ * @param reader function to call to read plaintext data
+ * @param proc function to call on each encrypted block
+ * @param progress function to call with progress information 
+ * @param cont function to call when done
+ */
+struct GNUNET_FS_TreeEncoder *
+GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h,
+                               uint64_t size,
+                               void *cls,
+                               GNUNET_FS_DataReader reader,
+                               GNUNET_FS_TreeBlockProcessor proc,
+                               GNUNET_FS_TreeProgressCallback progress,
+                               GNUNET_SCHEDULER_Task cont)
+{
+  struct GNUNET_FS_TreeEncoder *te;
+  
+  te = GNUNET_malloc (sizeof (struct GNUNET_FS_TreeEncoder));
+  te->h = h;
+  te->size = size;
+  te->cls = cls;
+  te->reader = reader;
+  te->proc = proc;
+  te->progress = progress;
+  te->cont = cont;
+  te->chk_tree_depth = compute_depth (size);
+  te->current_depth = te->chk_tree_depth;
+  te->chk_tree = GNUNET_malloc (te->chk_tree_depth *
+                                CHK_PER_INODE *
+                                sizeof (struct ContentHashKey));
+  return te;
+}
+
+
+/**
+ * Compute the size of the current IBlock.
+ *
+ * @param height height of the IBlock in the tree (aka overall
+ *               number of tree levels minus depth); 0 == DBlock
+ * @param offset current offset in the overall file
+ * @return size of the corresponding IBlock
+ */
+static uint16_t 
+compute_iblock_size (unsigned int height,
+                     uint64_t offset)
+{
+  unsigned int ret;
+  unsigned int i;
+  uint64_t mod;
+  uint64_t bds;
+
+  GNUNET_assert (height > 0);
+  bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i"
+                                  corresponds to */
+  for (i=0;i<height;i++)
+    bds *= CHK_PER_INODE;
+  mod = offset % bds;
+  if (0 == mod)
+    {
+      /* we were triggered at the end of a full block */
+      ret = CHK_PER_INODE;
+    }
+  else
+    {
+      /* we were triggered at the end of the file */
+      bds /= CHK_PER_INODE;
+      ret = mod / bds;
+      if (0 != mod % bds)
+        ret++; 
+    }
+  return (uint16_t) (ret * sizeof(struct ContentHashKey));
+}
+
+
+/**
+ * Compute the offset of the CHK for the
+ * current block in the IBlock above.
+ *
+ * @param height height of the IBlock in the tree (aka overall
+ *               number of tree levels minus depth); 0 == DBlock
+ * @param offset current offset in the overall file
+ * @return (array of CHKs') offset in the above IBlock
+ */
+static unsigned int
+compute_chk_offset (unsigned int height,
+                    uint64_t offset)
+{
+  uint64_t bds;
+  unsigned int ret;
+  unsigned int i;
+
+  bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i"
+                                  corresponds to */
+  for (i=0;i<height;i++)
+    bds *= CHK_PER_INODE;
+  GNUNET_assert (0 == (offset % bds));
+  ret = offset / bds;
+  return ret % CHK_PER_INODE; 
+}
+
+
+/**
+ * Encrypt the next block of the file (and 
+ * call proc and progress accordingly; or 
+ * of course "cont" if we have already completed
+ * encoding of the entire file).
+ *
+ * @param te tree encoder to use
+ */
+void GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te)
+{
+  struct ContentHashKey *mychk;
+  const void *pt_block;
+  uint16_t pt_size;
+  char iob[DBLOCK_SIZE];
+  char enc[DBLOCK_SIZE];
+  struct GNUNET_CRYPTO_AesSessionKey sk;
+  struct GNUNET_CRYPTO_AesInitializationVector iv;
+  unsigned int off;
+
+  if (te->current_depth == te->chk_tree_depth)
+    {
+      pt_size = GNUNET_MIN(DBLOCK_SIZE,
+                           te->size - te->publish_offset);
+      if (pt_size !=
+          te->reader (te->cls,
+                      te->publish_offset,
+                      pt_size,
+                      iob,
+                      &te->emsg))
+        {
+          GNUNET_SCHEDULER_add_continuation (te->h->sched,
+                                             GNUNET_NO,
+                                             te->cont,
+                                             te->cls,
+                                             GNUNET_SCHEDULER_REASON_TIMEOUT);
+          return;
+        }
+      pt_block = iob;
+    }
+  else
+    {
+      pt_size = compute_iblock_size (te->chk_tree_depth - te->current_depth,
+                                     te->publish_offset); 
+      pt_block = &te->chk_tree[te->current_depth *
+                               CHK_PER_INODE];
+    }
+  off = compute_chk_offset (te->chk_tree_depth - te->current_depth,
+                            te->publish_offset);
+  mychk = &te->chk_tree[(te->current_depth-1)*CHK_PER_INODE+off];
+  GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
+  GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
+  GNUNET_CRYPTO_aes_encrypt (pt_block,
+                             pt_size,
+                             &sk,
+                             &iv,
+                             enc);
+  if (NULL != te->proc)
+    te->proc (te->cls,
+              &mychk->query,
+              te->publish_offset,
+              pt_size,
+              enc,
+              (te->current_depth == te->chk_tree_depth) 
+              ? GNUNET_DATASTORE_BLOCKTYPE_DBLOCK 
+              : GNUNET_DATASTORE_BLOCKTYPE_IBLOCK);
+  if (NULL != te->progress)
+    te->progress (te->cls,
+                  te->publish_offset,
+                  pt_block,
+                  pt_size,
+                  te->current_depth);
+  GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
+  if (te->current_depth == te->chk_tree_depth) 
+    { 
+      te->publish_offset += pt_size;
+      if ( (te->publish_offset == te->size) ||
+           (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE) ) )
+        te->current_depth--;
+    }
+  else
+    {
+      if ( (off == CHK_PER_INODE) ||
+           (te->publish_offset == te->size) )
+        te->current_depth--;
+      else
+        te->current_depth = te->chk_tree_depth;
+    }
+  if (0 == te->current_depth)
+    {
+      te->uri = GNUNET_malloc (sizeof(struct GNUNET_FS_Uri));
+      te->uri->type = chk;
+      te->uri->data.chk.chk = te->chk_tree[0];
+      te->uri->data.chk.file_length = te->size;
+      GNUNET_SCHEDULER_add_continuation (te->h->sched,
+                                         GNUNET_NO,
+                                         te->cont,
+                                         te->cls,
+                                         GNUNET_SCHEDULER_REASON_PREREQ_DONE);
+    }
+}
+
+
+/**
+ * Clean up a tree encoder and return information
+ * about the resulting URI or an error message.
+ * 
+ * @param te the tree encoder to clean up
+ * @param uri set to the resulting URI (if encoding finished)
+ * @param emsg set to an error message (if an error occured
+ *        within the tree encoder; if this function is called
+ *        prior to completion and prior to an internal error,
+ *        both "*uri" and "*emsg" will be set to NULL).
+ */
+void GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder * te,
+                                    struct GNUNET_FS_Uri **uri,
+                                    char **emsg)
+{
+  *uri = te->uri;
+  *emsg = te->emsg;
+  GNUNET_free (te->chk_tree);
+  GNUNET_free (te);
+}
+
+/* end of fs_tree.c */
diff --git a/src/fs/fs_tree.h b/src/fs/fs_tree.h
new file mode 100644
index 000000000..f24130a3c
--- /dev/null
+++ b/src/fs/fs_tree.h
@@ -0,0 +1,167 @@
+/*
+     This file is part of GNUnet.
+     (C) 2009 Christian Grothoff (and other contributing authors)
+
+     GNUnet 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, 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
+     General Public License for more details.
+
+     You should have received a copy of the GNU General Public License
+     along with GNUnet; see the file COPYING.  If not, write to the
+     Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+     Boston, MA 02111-1307, USA.
+*/
+
+/**
+ * @file fs/fs_tree.h
+ * @brief Merkle-tree-ish-CHK file encoding for GNUnet
+ * @see http://gnunet.org/encoding.php3
+ * @author Krista Bennett
+ * @author Christian Grothoff
+ *
+ * TODO:
+ * - decide if this API should be made public (gnunet_fs_service.h)
+ *   or remain "internal" (but with exported symbols?)
+ */
+#ifndef GNUNET_FS_TREE_H
+#define GNUNET_FS_TREE_H
+
+#include "fs.h"
+
+/**
+ * Context for an ECRS-based file encoder that computes
+ * the Merkle-ish-CHK tree.
+ */
+struct GNUNET_FS_TreeEncoder;
+
+
+/**
+ * Function called asking for the current (encoded)
+ * block to be processed.  After processing the
+ * client should either call "GNUNET_FS_tree_encode_next"
+ * or (on error) "GNUNET_FS_tree_encode_finish".
+ *
+ * @param cls closure
+ * @param query the query for the block (key for lookup in the datastore)
+ * @param offset offset of the block
+ * @param type type of the block (IBLOCK or DBLOCK)
+ * @param block the (encrypted) block
+ * @param block_size size of block (in bytes)
+ */
+typedef void (*GNUNET_FS_TreeBlockProcessor)(void *cls,
+                                             const GNUNET_HashCode *query,
+                                             uint64_t offset,
+                                             unsigned int type,
+                                             const void *block,
+                                             uint16_t block_size);
+                                             
+
+/**
+ * Function called with information about our
+ * progress in computing the tree encoding.
+ *
+ * @param cls closure
+ * @param offset where are we in the file
+ * @param pt_block plaintext of the currently processed block
+ * @param pt_size size of pt_block
+ * @param depth depth of the block in the tree
+ */
+typedef void (*GNUNET_FS_TreeProgressCallback)(void *cls,
+                                               uint64_t offset,
+                                               const void *pt_block,
+                                               size_t pt_size,
+                                               unsigned int depth);
+                                               
+
+/**
+ * Initialize a tree encoder.  This function will call "proc" and
+ * "progress" on each block in the tree.  Once all blocks have been
+ * processed, "cont" will be scheduled.  The "reader" will be called
+ * to obtain the (plaintext) blocks for the file.  Note that this
+ * function will actually never call "proc"; the "proc" function must
+ * be triggered by calling "GNUNET_FS_tree_encoder_next" to trigger
+ * encryption (and calling of "proc") for each block.
+ *
+ * @param h the global FS context
+ * @param size overall size of the file to encode
+ * @param cls closure for reader, proc, progress and cont
+ * @param reader function to call to read plaintext data
+ * @param proc function to call on each encrypted block
+ * @param progress function to call with progress information 
+ * @param cont function to call when done
+ */
+struct GNUNET_FS_TreeEncoder *
+GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h,
+                               uint64_t size,
+                               void *cls,
+                               GNUNET_FS_DataReader reader,
+                               GNUNET_FS_TreeBlockProcessor proc,
+                               GNUNET_FS_TreeProgressCallback progress,
+                               GNUNET_SCHEDULER_Task cont);
+
+
+/**
+ * Encrypt the next block of the file (and 
+ * call proc and progress accordingly; or 
+ * of course "cont" if we have already completed
+ * encoding of the entire file).
+ *
+ * @param te tree encoder to use
+ */
+void GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te);
+
+
+/**
+ * Clean up a tree encoder and return information
+ * about the resulting URI or an error message.
+ * 
+ * @param te the tree encoder to clean up
+ * @param uri set to the resulting URI (if encoding finished)
+ * @param emsg set to an error message (if an error occured
+ *        within the tree encoder; if this function is called
+ *        prior to completion and prior to an internal error,
+ *        both "*uri" and "*emsg" will be set to NULL).
+ */
+void GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder * te,
+                                    struct GNUNET_FS_Uri **uri,
+                                    char **emsg);
+
+
+#if 0
+/* the functions below will be needed for persistence
+   but are not yet implemented -- FIXME... */
+/**
+ * Get data that would be needed to resume
+ * the encoding later.
+ * 
+ * @param te encoding to resume
+ * @param data set to the resume data
+ * @param size set to the size of the resume data
+ */
+void GNUNET_FS_tree_encoder_resume_get_data (const struct GNUNET_FS_TreeEncoder * te,
+                                             void **data,
+                                             size_t *size);
+
+
+/**
+ * Reset tree encoder to point previously
+ * obtained for resuming.
+ * 
+ * @param te encoding to resume
+ * @param data the resume data
+ * @param size the size of the resume data
+ */
+void GNUNET_FS_tree_encoder_resume (struct GNUNET_FS_TreeEncoder * te,
+                                    const void *data,
+                                    size_t size);
+#endif
+
+#endif
+
+/* end of fs_tree.h */