[tor-bugs] #6538 [Tor Client]: Use bit-twiddling tricks to make choose-by-bandwith algorithm even more time-invairant

[Tor Bug Tracker & Wiki]

#6538: Use bit-twiddling tricks to make choose-by-bandwith algorithm even more
time-invairant
-------------------------+--------------------------------------------------
 Reporter:  nickm        |          Owner:                    
     Type:  enhancement  |         Status:  new               
 Priority:  normal       |      Milestone:  Tor: 0.2.3.x-final
Component:  Tor Client   |        Version:                    
 Keywords:               |         Parent:                    
   Points:               |   Actualpoints:                    
-------------------------+--------------------------------------------------
 See #6537 for discussion.  There's a branch in the middle of our node
 selection algorithm, which is bad for time-invariance.  Furthermore, a
 sufficiently clever compiler might decide to reinsert the break statement
 that 6537 so carefully removed.  (I have not yet found a compiler this
 clever, but better safe than sorry!)

 We can probably do better by using a bit-twiddling approach to setting
 i_chosen.  For example, rransom wrote:
 {{{
   i_chosen = 0;
   i_hasnt_been_chosen = ~0;
   for (...) {
      int64_t choose_this_i;
      tmp += int_bandwidths[i];
     choose_this_i = rand_bw - (tmp+1);
     choose_this_i = choose_this_i >> 63;
     /* choose_this_i = -1 if rand_bw < (tmp+1); choose_this_i = 0
 otherwise */
     i_chosen |= (i & choose_this_i & i_hasnt_been_chosen);
     i_hasnt_been_chosen &= ~choose_this_i;
  }
  i = i_chosen;
 }}}

 This looks okay to me; more eyes are needed here, though.

-- 
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/6538>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online