2 This file is part of GNUnet.
3 (C) 2009-2011 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 3, 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
32 * Context for an ECRS-based file encoder that computes
33 * the Merkle-ish-CHK tree.
35 struct GNUNET_FS_TreeEncoder
41 struct GNUNET_FS_Handle *h;
44 * Closure for all callbacks.
49 * Function to call on encrypted blocks.
51 GNUNET_FS_TreeBlockProcessor proc;
54 * Function to call with progress information.
56 GNUNET_FS_TreeProgressCallback progress;
59 * Function to call to receive input data.
61 GNUNET_FS_DataReader reader;
64 * Function to call once we're done with processing.
66 GNUNET_SCHEDULER_Task cont;
69 * Set to an error message (if we had an error).
74 * Set to the URI (upon successful completion)
76 struct GNUNET_FS_Uri *uri;
86 uint64_t publish_offset;
89 * How deep are we? Depth 0 is for the DBLOCKs.
91 unsigned int current_depth;
94 * How deep is the tree? Always > 0.
96 unsigned int chk_tree_depth;
99 * In-memory cache of the current CHK tree.
100 * This struct will contain the CHK values
101 * from the root to the currently processed
102 * node in the tree as identified by
103 * "current_depth" and "publish_offset".
104 * The "chktree" will be initially NULL,
105 * then allocated to a sufficient number of
106 * entries for the size of the file and
107 * finally freed once the upload is complete.
109 struct ContentHashKey *chk_tree;
112 * Are we currently in 'GNUNET_FS_tree_encoder_next'?
113 * Flag used to prevent recursion.
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, always > 0. A depth of 1 means only a DBLOCK.
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 * Calculate how many bytes of payload a block tree of the given
149 * depth MAY correspond to at most (this function ignores the fact that
150 * some blocks will only be present partially due to the total file
151 * size cutting some blocks off at the end).
153 * @param depth depth of the block. depth==0 is a DBLOCK.
154 * @return number of bytes of payload a subtree of this depth may correspond to
157 GNUNET_FS_tree_compute_tree_size (unsigned int depth)
163 for (i = 0; i < depth; i++)
164 rsize *= CHK_PER_INODE;
170 * Compute the size of the current IBLOCK. The encoder is
171 * triggering the calculation of the size of an IBLOCK at the
172 * *end* (hence end_offset) of its construction. The IBLOCK
173 * maybe a full or a partial IBLOCK, and this function is to
174 * calculate how long it should be.
176 * @param depth depth of the IBlock in the tree, 0 would be a DBLOCK,
177 * must be > 0 (this function is for IBLOCKs only!)
178 * @param end_offset current offset in the payload (!) of the overall file,
179 * must be > 0 (since this function is called at the
181 * @return size of the corresponding IBlock
184 GNUNET_FS_tree_compute_iblock_size (unsigned int depth, uint64_t end_offset)
190 GNUNET_assert (depth > 0);
191 GNUNET_assert (end_offset > 0);
192 bds = GNUNET_FS_tree_compute_tree_size (depth);
193 mod = end_offset % bds;
196 /* we were triggered at the end of a full block */
201 /* we were triggered at the end of the file */
202 bds /= CHK_PER_INODE;
207 return (uint16_t) (ret * sizeof (struct ContentHashKey));
212 * Compute how many bytes of data should be stored in
213 * the specified block.
215 * @param fsize overall file size, must be > 0.
216 * @param offset offset in the original data corresponding
217 * to the beginning of the tree induced by the block;
219 * @param depth depth of the node in the tree, 0 for DBLOCK
220 * @return number of bytes stored in this node
223 GNUNET_FS_tree_calculate_block_size (uint64_t fsize, uint64_t offset,
231 GNUNET_assert (fsize > 0);
232 GNUNET_assert (offset <= fsize);
236 if ((offset + ret > fsize) || (offset + ret < offset))
237 ret = (size_t) (fsize - offset);
241 rsize = GNUNET_FS_tree_compute_tree_size (depth - 1);
242 epos = offset + rsize * CHK_PER_INODE;
243 if ((epos < offset) || (epos > fsize))
245 /* round up when computing #CHKs in our IBlock */
246 chks = (epos - offset + rsize - 1) / rsize;
247 GNUNET_assert (chks <= CHK_PER_INODE);
248 return chks * sizeof (struct ContentHashKey);
253 * Initialize a tree encoder. This function will call @a proc and
254 * "progress" on each block in the tree. Once all blocks have been
255 * processed, "cont" will be scheduled. The @a reader will be called
256 * to obtain the (plaintext) blocks for the file. Note that this
257 * function will not actually call @a proc. The client must
258 * call #GNUNET_FS_tree_encoder_next to trigger encryption (and
259 * calling of @a proc) for the each block.
261 * @param h the global FS context
262 * @param size overall size of the file to encode
263 * @param cls closure for reader, proc, progress and cont
264 * @param reader function to call to read plaintext data
265 * @param proc function to call on each encrypted block
266 * @param progress function to call with progress information
267 * @param cont function to call when done
269 struct GNUNET_FS_TreeEncoder *
270 GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h, uint64_t size,
272 GNUNET_FS_DataReader reader,
273 GNUNET_FS_TreeBlockProcessor proc,
274 GNUNET_FS_TreeProgressCallback progress,
275 GNUNET_SCHEDULER_Task cont)
277 struct GNUNET_FS_TreeEncoder *te;
279 te = GNUNET_malloc (sizeof (struct GNUNET_FS_TreeEncoder));
285 te->progress = progress;
287 te->chk_tree_depth = GNUNET_FS_compute_depth (size);
289 GNUNET_malloc (te->chk_tree_depth * CHK_PER_INODE *
290 sizeof (struct ContentHashKey));
291 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
292 "Created tree encoder for file with %llu bytes and depth %u\n",
293 (unsigned long long) size,
300 * Compute the offset of the CHK for the
301 * current block in the IBlock above.
303 * @param depth depth of the IBlock in the tree (aka overall
304 * number of tree levels minus depth); 0 == DBlock
305 * @param end_offset current offset in the overall file,
306 * at the *beginning* of the block for DBLOCKs (depth==0),
307 * otherwise at the *end* of the block (exclusive)
308 * @return (array of CHKs') offset in the above IBlock
311 compute_chk_offset (unsigned int depth, uint64_t end_offset)
316 bds = GNUNET_FS_tree_compute_tree_size (depth);
318 end_offset--; /* round down since for depth > 0 offset is at the END of the block */
319 ret = end_offset / bds;
320 return ret % CHK_PER_INODE;
325 * Encrypt the next block of the file (and call proc and progress
326 * accordingly; or of course "cont" if we have already completed
327 * encoding of the entire file).
329 * @param te tree encoder to use
332 GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder *te)
334 struct ContentHashKey *mychk;
335 const void *pt_block;
337 char iob[DBLOCK_SIZE];
338 char enc[DBLOCK_SIZE];
339 struct GNUNET_CRYPTO_SymmetricSessionKey sk;
340 struct GNUNET_CRYPTO_SymmetricInitializationVector iv;
343 GNUNET_assert (GNUNET_NO == te->in_next);
344 te->in_next = GNUNET_YES;
345 if (te->chk_tree_depth == te->current_depth)
347 off = CHK_PER_INODE * (te->chk_tree_depth - 1);
348 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TE done, reading CHK `%s' from %u\n",
349 GNUNET_h2s (&te->chk_tree[off].query), off);
350 te->uri = GNUNET_malloc (sizeof (struct GNUNET_FS_Uri));
351 te->uri->type = GNUNET_FS_URI_CHK;
352 te->uri->data.chk.chk = te->chk_tree[off];
353 te->uri->data.chk.file_length = GNUNET_htonll (te->size);
354 te->in_next = GNUNET_NO;
355 te->cont (te->cls, NULL);
358 if (0 == te->current_depth)
361 pt_size = GNUNET_MIN (DBLOCK_SIZE, te->size - te->publish_offset);
363 te->reader (te->cls, te->publish_offset, pt_size, iob, &te->emsg))
365 te->in_next = GNUNET_NO;
366 te->cont (te->cls, NULL);
374 GNUNET_FS_tree_compute_iblock_size (te->current_depth,
376 pt_block = &te->chk_tree[(te->current_depth - 1) * CHK_PER_INODE];
378 off = compute_chk_offset (te->current_depth, te->publish_offset);
379 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
380 "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n",
381 (unsigned long long) te->publish_offset, te->current_depth,
382 (unsigned int) pt_size, (unsigned int) off);
383 mychk = &te->chk_tree[te->current_depth * CHK_PER_INODE + off];
384 GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
385 GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
386 GNUNET_CRYPTO_symmetric_encrypt (pt_block, pt_size, &sk, &iv, enc);
387 GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
388 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
389 "TE calculates query to be `%s', stored at %u\n",
390 GNUNET_h2s (&mychk->query),
391 te->current_depth * CHK_PER_INODE + off);
392 if (NULL != te->proc)
393 te->proc (te->cls, mychk, te->publish_offset, te->current_depth,
395 te->current_depth) ? GNUNET_BLOCK_TYPE_FS_DBLOCK :
396 GNUNET_BLOCK_TYPE_FS_IBLOCK, enc, pt_size);
397 if (NULL != te->progress)
398 te->progress (te->cls, te->publish_offset, pt_block, pt_size,
400 if (0 == te->current_depth)
402 te->publish_offset += pt_size;
403 if ((te->publish_offset == te->size) ||
404 (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE)))
409 if ((off == CHK_PER_INODE) || (te->publish_offset == te->size))
412 te->current_depth = 0;
414 te->in_next = GNUNET_NO;
419 * Get the resulting URI from the encoding.
421 * @param te the tree encoder to clean up
422 * @return uri set to the resulting URI (if encoding finished), NULL otherwise
424 struct GNUNET_FS_Uri *
425 GNUNET_FS_tree_encoder_get_uri (struct GNUNET_FS_TreeEncoder *te)
428 return GNUNET_FS_uri_dup (te->uri);
434 * Clean up a tree encoder and return information
435 * about possible errors.
437 * @param te the tree encoder to clean up
438 * @param emsg set to an error message (if an error occured
439 * within the tree encoder; if this function is called
440 * prior to completion and prior to an internal error,
441 * both "*emsg" will be set to NULL).
444 GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder *te,
447 if (NULL != te->reader)
449 (void) te->reader (te->cls, UINT64_MAX, 0, 0, NULL);
452 GNUNET_assert (GNUNET_NO == te->in_next);
454 GNUNET_FS_uri_destroy (te->uri);
458 GNUNET_free_non_null (te->emsg);
459 GNUNET_free (te->chk_tree);
463 /* end of fs_tree.c */