2 This file is part of GNUnet.
3 (C) 2009 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 2, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @brief Merkle-tree-ish-CHK file encoding for GNUnet
23 * @see http://gnunet.org/encoding.php3
24 * @author Krista Bennett
25 * @author Christian Grothoff
28 * - decide if this API should be made public (gnunet_fs_service.h)
29 * or remain "internal" (but with exported symbols?)
34 #define DEBUG_TREE GNUNET_NO
37 * Context for an ECRS-based file encoder that computes
38 * the Merkle-ish-CHK tree.
40 struct GNUNET_FS_TreeEncoder
46 struct GNUNET_FS_Handle *h;
49 * Closure for all callbacks.
54 * Function to call on encrypted blocks.
56 GNUNET_FS_TreeBlockProcessor proc;
59 * Function to call with progress information.
61 GNUNET_FS_TreeProgressCallback progress;
64 * Function to call to receive input data.
66 GNUNET_FS_DataReader reader;
69 * Function to call once we're done with processing.
71 GNUNET_SCHEDULER_Task cont;
74 * Set to an error message (if we had an error).
79 * Set to the URI (upon successful completion)
81 struct GNUNET_FS_Uri *uri;
91 uint64_t publish_offset;
96 unsigned int current_depth;
99 * How deep is the tree?
101 unsigned int chk_tree_depth;
104 * In-memory cache of the current CHK tree.
105 * This struct will contain the CHK values
106 * from the root to the currently processed
107 * node in the tree as identified by
108 * "current_depth" and "publish_offset".
109 * The "chktree" will be initially NULL,
110 * then allocated to a sufficient number of
111 * entries for the size of the file and
112 * finally freed once the upload is complete.
114 struct ContentHashKey *chk_tree;
120 * Compute the depth of the CHK tree.
122 * @param flen file length for which to compute the depth
123 * @return depth of the tree
126 GNUNET_FS_compute_depth (uint64_t flen)
128 unsigned int treeDepth;
136 if (fl * CHK_PER_INODE < fl)
138 /* integer overflow, this is a HUGE file... */
141 fl = fl * CHK_PER_INODE;
148 * Initialize a tree encoder. This function will call "proc" and
149 * "progress" on each block in the tree. Once all blocks have been
150 * processed, "cont" will be scheduled. The "reader" will be called
151 * to obtain the (plaintext) blocks for the file. Note that this
152 * function will not actually call "proc". The client must
153 * call "GNUNET_FS_tree_encoder_next" to trigger encryption (and
154 * calling of "proc") for the each block.
156 * @param h the global FS context
157 * @param size overall size of the file to encode
158 * @param cls closure for reader, proc, progress and cont
159 * @param reader function to call to read plaintext data
160 * @param proc function to call on each encrypted block
161 * @param progress function to call with progress information
162 * @param cont function to call when done
164 struct GNUNET_FS_TreeEncoder *
165 GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h,
168 GNUNET_FS_DataReader reader,
169 GNUNET_FS_TreeBlockProcessor proc,
170 GNUNET_FS_TreeProgressCallback progress,
171 GNUNET_SCHEDULER_Task cont)
173 struct GNUNET_FS_TreeEncoder *te;
175 GNUNET_assert (size > 0);
176 te = GNUNET_malloc (sizeof (struct GNUNET_FS_TreeEncoder));
182 te->progress = progress;
184 te->chk_tree_depth = GNUNET_FS_compute_depth (size);
185 te->current_depth = te->chk_tree_depth;
186 te->chk_tree = GNUNET_malloc (te->chk_tree_depth *
188 sizeof (struct ContentHashKey));
194 * Compute the size of the current IBlock.
196 * @param height height of the IBlock in the tree (aka overall
197 * number of tree levels minus depth); 0 == DBlock
198 * @param offset current offset in the overall file
199 * @return size of the corresponding IBlock
202 compute_iblock_size (unsigned int height,
210 GNUNET_assert (height > 0);
211 bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i"
213 for (i=0;i<height;i++)
214 bds *= CHK_PER_INODE;
218 /* we were triggered at the end of a full block */
223 /* we were triggered at the end of the file */
224 bds /= CHK_PER_INODE;
229 return (uint16_t) (ret * sizeof(struct ContentHashKey));
234 * Compute the offset of the CHK for the
235 * current block in the IBlock above.
237 * @param height height of the IBlock in the tree (aka overall
238 * number of tree levels minus depth); 0 == DBlock
239 * @param offset current offset in the overall file
240 * @return (array of CHKs') offset in the above IBlock
243 compute_chk_offset (unsigned int height,
250 bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i"
252 for (i=0;i<height;i++)
253 bds *= CHK_PER_INODE;
255 return ret % CHK_PER_INODE;
260 * Encrypt the next block of the file (and
261 * call proc and progress accordingly; or
262 * of course "cont" if we have already completed
263 * encoding of the entire file).
265 * @param te tree encoder to use
267 void GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te)
269 struct ContentHashKey *mychk;
270 const void *pt_block;
272 char iob[DBLOCK_SIZE];
273 char enc[DBLOCK_SIZE];
274 struct GNUNET_CRYPTO_AesSessionKey sk;
275 struct GNUNET_CRYPTO_AesInitializationVector iv;
278 if (te->current_depth == te->chk_tree_depth)
280 pt_size = GNUNET_MIN(DBLOCK_SIZE,
281 te->size - te->publish_offset);
289 GNUNET_SCHEDULER_add_continuation (te->h->sched,
292 GNUNET_SCHEDULER_REASON_TIMEOUT);
299 pt_size = compute_iblock_size (te->chk_tree_depth - te->current_depth,
301 pt_block = &te->chk_tree[te->current_depth *
304 if (0 == te->current_depth)
306 te->uri = GNUNET_malloc (sizeof(struct GNUNET_FS_Uri));
308 te->uri->data.chk.chk = te->chk_tree[0];
309 te->uri->data.chk.file_length = GNUNET_htonll (te->size);
310 GNUNET_SCHEDULER_add_continuation (te->h->sched,
313 GNUNET_SCHEDULER_REASON_PREREQ_DONE);
316 off = compute_chk_offset (te->chk_tree_depth - te->current_depth,
319 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
320 "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n",
321 (unsigned long long) te->publish_offset,
323 (unsigned int) pt_size,
326 mychk = &te->chk_tree[(te->current_depth-1)*CHK_PER_INODE+off];
327 GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
328 GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
329 GNUNET_CRYPTO_aes_encrypt (pt_block,
334 GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
336 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
337 "TE calculates query to be `%s'\n",
338 GNUNET_h2s (&mychk->query));
340 if (NULL != te->proc)
344 (te->current_depth == te->chk_tree_depth)
345 ? GNUNET_DATASTORE_BLOCKTYPE_DBLOCK
346 : GNUNET_DATASTORE_BLOCKTYPE_IBLOCK,
349 if (NULL != te->progress)
350 te->progress (te->cls,
355 if (te->current_depth == te->chk_tree_depth)
357 te->publish_offset += pt_size;
358 if ( (te->publish_offset == te->size) ||
359 (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE) ) )
364 if ( (off == CHK_PER_INODE) ||
365 (te->publish_offset == te->size) )
368 te->current_depth = te->chk_tree_depth;
374 * Clean up a tree encoder and return information
375 * about the resulting URI or an error message.
377 * @param te the tree encoder to clean up
378 * @param uri set to the resulting URI (if encoding finished)
379 * @param emsg set to an error message (if an error occured
380 * within the tree encoder; if this function is called
381 * prior to completion and prior to an internal error,
382 * both "*uri" and "*emsg" will be set to NULL).
384 void GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder * te,
385 struct GNUNET_FS_Uri **uri,
392 GNUNET_FS_uri_destroy (te->uri);
396 GNUNET_free_non_null (te->emsg);
397 GNUNET_free (te->chk_tree);
401 /* end of fs_tree.c */