Back to Questions
2.2k
views3
comments
BitTorrent Fast Peers algorithm issue
f#

Hi, I have a question regarding an algorithm used in BitTorrent's Fast Peers Extension (see [link:www.bittorrent.org] )whose C++ version is given as :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

void generate_fast_set(
  uint32 k,     // number of pieces in set
  uint32 sz,    // number of pieces in torrent
  const char infohash[20], // infohash of torrent
  uint32 ip, // in host byte order, ie localhost is 0x7f000001
  std::vector<uint32> &a) // generated set of piece indices
{
   a.clear();
   std::string x;
   char buf[4];
   *(uint32*)buf = htonl(ip & 0xffffff00);
   x.assign(buf, 4);
   x.append(infohash, 20); // (3)
   while (a.size()<k) {
     x = SHA1(x); // (4)
     for ( int i=0 ; i<5 && a.size()<k ; i++ ) { // (5)
       int j = i*4; // (6)
       uint32 y = ntohl(*(uint32*)(x.data()+j)); // (7)
       uint32 index = y % sz; // (8)
       if (std::find(a.begin(), a.end(), index)==a.end()) { // (9)
         a.push_back(index); // (10)
       }
     }
   }
}

Example results generated by this function: 

1
2
3
4
5
6
7
8
9
10
11
12

7 piece allowed fast set for torrent with 1313 pieces and hex infohash

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200:

  1059,431,808,1217,287,376,1188

9 piece allowed fast set for torrent with 1313 pieces and hex infohash

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200:

  1059,431,808,1217,287,376,1188,353,508

The info hash is thus [|for i in 0 .. 19 -> 170uy |] in the following example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

 
#light

open System

type SHA1 () =
  static member hash = 
    let csp = new System.Security.Cryptography.SHA1CryptoServiceProvider()
    fun (bytes : byte[]) -> csp.ComputeHash bytes

//F# version of the algorithm : expectedly yields the same result as the C++ version
//seems to be __very__ slow beyond 5 pieces...
let standard_generate_fast_set n  = 
  let allowed = HashSet<int>.Create()
  let x = 
    let ip = [|80uy;4uy;4uy;0uy|]
    Array.append ip [|for i in 0 .. 19 -> 170uy|]
  let count_pieces = 1313u
  let a,b,c = 256u*256u*256u, 256u*256u, 256u
  while allowed.Count < n do
    let x = SHA1.hash x
    for i in 0 .. 4 .. 19 do
      let  y = uint32 x.[ i] * a + uint32 x.[i+1]* b + uint32 x.[i+2]* c + uint32 x.[i+3]
      let idx = y % count_pieces
      allowed.Add(int idx)
  allowed

//different but much faster algorithm however not appropriate since
//two clients should yield the same sequence when asked for the same number of pieces...
let generate_fast_set n = 
  let allowed = HashSet<int>.Create()
  let rnd = 
    let ip = [|80uy;4uy;4uy;0uy|]
    let seed = Array.append ip [|for i in 0 .. 19 -> 170uy|] |> SHA1.hash |> Array.fold_left (+) 0uy |> int  
    new Random(seed)
  let count_pieces = 1313
  while allowed.Count < n do
    let idx = rnd.Next() % count_pieces
    allowed.Add(idx)
  allowed


Any idea of what could be wrong and explain such slowness ?

Thank you very much

.

Hi Julien,

You have an optimistic idea of 'very slow' because the F# code never terminates. [:)]

The problem is with this line

1

let x = SHA1.hash x

In C++ this code assigns to the variable x. However in F#, since variables are immutable, this line creates a new variable x that shadows the old variable x. Since you're copying C++ code it would seem reasonable to use a mutable local variable here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

let standard_generate_fast_set n  = 
  let allowed = HashSet<int>.Create()
  let mutable x = 
    let ip = [|80uy;4uy;4uy;0uy|]
    Array.append ip [|for i in 0 .. 19 -> 170uy|]
  let count_pieces = 1313u
  let a,b,c = 256u*256u*256u, 256u*256u, 256u
  while allowed.Count < n do
    x <- SHA1.hash x
    for i in 0 .. 4 .. 19 do
      let  y = uint32 x.[ i] * a + uint32 x.[i+1]* b + uint32 x.[i+2]* c + uint32 x.[i+3]
      let idx = y % count_pieces
      allowed.Add(int idx)
  allowed
By on 12/12/2007 4:38 AM ()

Thank you! I have tried your version and it indeed works gnice and fast.

====

In C++ this code assigns to the variable x. However in F#, since variables are immutable, this line creates a new variable x that shadows the old variable x. Since you're copying C++ code it would seem reasonable to use a mutable local variable here.

However, I don't understand why shadowing the "x" variable prevents the function from "ending". The resulting hash that is used afterwards should be the same in both cases (ie whether overwriting the old variable by creating a new one, or by using the mutable assignment) shouldn't it ?

Many thanks,

Julien

By on 12/12/2007 5:52 AM ()

It doesn't overwrite the old variable. There are two immutable variables that happen to have the same name but they are still distinct. 

1

let x = SHA1.hash x

The x on the right-side refers to the x that was previously declared. The x on the left-side defines a new variable. Any occurance of x in the scope of this let will refer to this newly defined x and not the outer x.

It is like in C# how in a method you can declare a local variable that has the same name as a field of the class. The local variable shadows the field but they are still separate and unrelated variables.

By on 12/12/2007 6:16 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper