[BitTorrent] Here's a post I would like forwarded... thanks! (fwd)

Justin Cormack justin at street-vision.com
Wed Feb 9 13:25:27 EST 2005


>From SRS0=Q2BZBw=QX=viasic.com=bill at yourhostingaccount.com  Wed Feb  9 18:23:23 2005
Return-Path: <SRS0=Q2BZBw=QX=viasic.com=bill at yourhostingaccount.com>
Received: from out-mail03.yourhostingaccount.com (mailrelay4.yourhostingaccount.com [38.113.1.63])
	by tench.street-vision.com (8.11.6/8.11.6) with ESMTP id j19INM404981
	for <justin at street-vision.com>; Wed, 9 Feb 2005 18:23:22 GMT
Resent-Date: Wed, 9 Feb 2005 18:23:22 GMT
Resent-Message-Id: <200502091823.j19INM404981 at tench.street-vision.com>
Received: from scan05.yourhostingaccount.com ([10.1.1.235] helo=scan05.yourhostingaccount.com)
	by mail03.yourhostingaccount.com with esmtp (Exim)
	id 1Cywbv-0005cE-Jp
	for justin at street-vision.com; Wed, 09 Feb 2005 13:30:47 -0500
Received: from mail01.yourhostingaccount.com ([10.1.1.72] ident=exim)
	by scan05.yourhostingaccount.com with spamscanlookuphost (Exim)
	id 1Cywbv-00016P-Sf
	for justin at street-vision.com; Wed, 09 Feb 2005 13:30:47 -0500
Received: from mail01.yourhostingaccount.com ([10.1.1.72] helo=inc-mail01.yourhostingaccount.com)
	by scan05.yourhostingaccount.com with esmtp (Exim)
	id 1Cywbu-000169-CV
	for justin at street-vision.com; Wed, 09 Feb 2005 13:30:46 -0500
Received: from 66-162-193-13.gen.twtelecom.net ([66.162.193.13] helo=192.168.1.104)
	by mail01.yourhostingaccount.com with esmtpsa (TLSv1:RC4-MD5:128)
	(Exim)
	id 1Cywbt-0007nO-1q
	for justin at street-vision.com; Wed, 09 Feb 2005 13:30:45 -0500
From: Bill Cox <bill at viasic.com>
To: "BitTorrent at yahoogroups.com" <BitTorrent at yahoogroups.com>
In-Reply-To: <ctug73+vbn2 at eGroups.com>
References: <ctug73+vbn2 at eGroups.com>
Content-Type: text/plain
Message-Id: <1107965792.4005.14.camel at swordfish>
Mime-Version: 1.0
Subject: Here's a post I would like forwarded... thanks!
Resent-From: Bill Cox <bill at viasic.com>
Resent-To: justin at street-vision.com
Organization: ViASIC
Date: Wed, 09 Feb 2005 13:30:39 -0500
X-Mailer: Evolution 2.0.2 (2.0.2-3) 
Content-Transfer-Encoding: 7bit

On Fri, 2005-02-04 at 00:38 +0000, sh4dowmatter wrote:
> 
> Not to beat a dead horse, but...
> 
> So I was re-reading the description of Merkle Hash Trees over at the
> THEX specification (see
> http://www.open-content.net/specs/draft-jchapweske-thex-02.html), and
> I was thinking of implementing an efficient, array-based version in C.

Hey, I got a post through!

Well, getting back to sh4dowmatter's original post, I think it's a good
idea.  It sounds like it needs a bit more explaining, so here's some
additional notes I've sent to Olaf on array based complete trees (the
last level can be incomplete).

Here's an example tree for a 9 piece torrent.  The numbers are the node
index for the nodes.  The nodes with dashes around them are leaves, and
represent pieces.

                    1
          |-----------------|
          2                 3
      |-------|         |---------|
      4       5         6         7
    |---|    |---|     |---|     |---|
    8  -9- -10- -11- -12- -13- -14- -15-
  |---|
-16- -17-

The root node has index 1.  It's children are 2 and 3.  In general, your
left child has index that's twice yours, and your right child is the
next node after that.

So, the first pieces's node index is 9, and they go up from there to 17.

To find your sibling, just xor your node index with 1.  For example,
9's sibling is 8.

In this example, the first piece (node 9) has an authentication path of
8-5-3.  The last piece (node 17) has 16-9-5-3.  The last piece listed to
the right (node 15), has authentication path 14-6-2.

So, here's some simple formulas for how to compute things, if there are
N pieces:

Root node index: 1 (not 0)
First piece node index: N
Last piece node index: (N << 1) - 1
Index of piece n (with 0 as the first piece): N + n
Node n's sibling: n ^ 1
Node n's parent: n >> 1
Node n's left child: n << 1
Node n's right child: (n << 1) + 1

There are other cool properties that shadowmatter talked about.  For
example, to perform a bottom-up recursion where we call function "func"
for on each node, but only after processing children, just use:

for(n = lastNodeIndex; n > 0; n--) {
    func(n);
}

Top down recursion is just:

for(n = 1; n <= lastNodeIndex; n++) {
    func(n);
}

The code winds up being fast and small.  It's also easy, once you get
use to it.

Bill




 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
 





More information about the BitTorrent mailing list