1 /* 2 * channel.cpp 3 * class representing a virtual connection to a peer. In addition, 4 * it contains generic functions for socket management (see sock_open 5 * class variable) 6 * 7 * Created by Victor Grishchenko on 3/6/09. 8 * Copyright 2009-2016 TECHNISCHE UNIVERSITEIT DELFT. All rights reserved. 9 * 10 */ 11 12 #include <cassert> 13 #include "compat.h" 14 #include "swift.h" 15 #include "bin_utils.h" 16 17 using namespace std; 18 using namespace swift; 19 20 /* 21 * Class variables 22 */ 23 24 swift::tint now_t::now = Channel::Time(); 25 tint Channel::start = now_t::now; 26 tint Channel::epoch = now_t::now/360000000LL*360000000LL; // make logs mergeable 27 uint64_t Channel::global_dgrams_up=0, Channel::global_dgrams_down=0, 28 Channel::global_raw_bytes_up=0, Channel::global_raw_bytes_down=0, 29 Channel::global_bytes_up=0, Channel::global_bytes_down=0; 30 sckrwecb_t Channel::sock_open[] = {}; 31 int Channel::sock_count = 0; 32 swift::tint Channel::last_tick = 0; 33 int Channel::MAX_REORDERING = 4; 34 bool Channel::SELF_CONN_OK = false; 35 swift::tint Channel::TIMEOUT = TINT_SEC*60; 36 channels_t Channel::channels(1); 37 std::string Channel::trackerurl; 38 FILE* Channel::debug_file = NULL; 39 // Only in dev: ledbat log file 40 FILE* Channel::debug_ledbat = NULL; 41 tint Channel::MIN_PEX_REQUEST_INTERVAL = TINT_SEC; 42 43 /* 44 * Instance methods 45 */ 46 47 Channel::Channel(ContentTransfer* transfer, int socket, Address peer_addr) : 48 // Arno, 2011-10-03: Reordered to avoid g++ Wall warning 49 peer_(peer_addr), socket_(socket==INVALID_SOCKET?default_socket():socket), // FIXME 50 transfer_(transfer), own_id_mentioned_(false), 51 ack_in_right_basebin_(bin_t::NONE), 52 data_in_(TINT_NEVER,bin_t::NONE), data_in_dbl_(bin_t::NONE), data_out_size_(0), 53 data_out_cap_(bin_t::ALL),hint_in_size_(0), hint_out_size_(0), hint_queue_out_size_(0), 54 // Gertjan fix 996e21e8abfc7d88db3f3f8158f2a2c4fc8a8d3f 55 // "Changed PEX rate limiting to per channel limiting" 56 pex_requested_(false), // Ric: init var that wasn't initialiazed 57 last_pex_request_time_(0), next_pex_request_time_(0), 58 pex_request_outstanding_(false), 59 useless_pex_count_(0), 60 rtt_avg_(TINT_SEC), dev_avg_(0), dip_avg_(TINT_SEC), 61 last_send_time_(0), last_recv_time_(0), last_data_out_time_(0), last_data_in_time_(0), 62 last_loss_time_(0), next_send_time_(0), open_time_(NOW), cwnd_(1), 63 cwnd_count1_(0), send_interval_(TINT_SEC), 64 send_control_(PING_PONG_CONTROL), sent_since_recv_(0), 65 lastrecvwaskeepalive_(false), lastsendwaskeepalive_(false), keepalivereason_(NONE), 66 live_have_no_hint_(false), // Arno: live speed opt 67 ack_rcvd_recent_(0), ack_not_rcvd_recent_(0), owd_min_bin_(0), owd_min_bin_start_(NOW-LEDBAT_ROLLOVER), 68 owd_cur_(TINT_NEVER), owd_min_(TINT_NEVER), 69 dgrams_sent_(0), dgrams_rcvd_(0), 70 raw_bytes_up_(0), raw_bytes_down_(0), bytes_up_(0), bytes_down_(0), 71 old_movingfwd_bytes_(0), 72 scheduled4del_(false), reschedule_delay_(0), 73 hs_out_(NULL), hs_in_(NULL), 74 last_sent_munro_(bin_t::NONE), 75 munro_ack_rcvd_(false), 76 rtt_hint_tintbin_() 77 { 78 // ARNOTODO: avoid infinitely growing vector 79 this->id_ = channels.size(); 80 channels.push_back(this); 81 82 for (int i=0; i<10; i++) { 83 owd_min_bins_[i] = TINT_NEVER; 84 } 85 86 evsend_ptr_ = new struct event; 87 evtimer_assign(evsend_ptr_,evbase,&Channel::LibeventSendCallback,this); 88 evtimer_add(evsend_ptr_,tint2tv(next_send_time_)); 89 90 //LIVE 91 evsendlive_ptr_ = NULL; 92 93 // RATELIMIT 94 transfer_->GetChannels()->push_back(this); 95 96 hs_out_ = new Handshake(transfer->GetDefaultHandshake()); 97 98 dprintf("%s #%" PRIu32 " init channel %s transfer %d\n",tintstr(),id_,peer_.str().c_str(), transfer_->td()); 99 //fprintf(stderr,"new Channel %d %s\n", id_, peer_.str().c_str() ); 100 } 101 102 103 Channel::~Channel() 104 { 105 dprintf("%s #%" PRIu32 " dealloc channel\n",tintstr(),id_); 106 channels[id_] = NULL; 107 ClearEvents(); 108 109 // RATELIMIT 110 if (transfer_ != NULL) { 111 channels_t::iterator iter; 112 channels_t *channels = transfer_->GetChannels(); 113 for (iter=channels->begin(); iter!=channels->end(); iter++) { 114 if (*iter == this) 115 break; 116 } 117 channels->erase(iter); 118 } 119 120 if (hs_in_ != NULL) { 121 delete hs_in_; 122 hs_in_ = NULL; 123 } 124 if (hs_out_ != NULL) { 125 delete hs_out_; 126 hs_out_ = NULL; 127 } 128 } 129 130 131 void Channel::ClearEvents() 132 { 133 // Arno, 2013-02-01: Be safer, _del not just on pending. 134 if (evsend_ptr_ != NULL) { 135 evtimer_del(evsend_ptr_); 136 delete evsend_ptr_; 137 evsend_ptr_ = NULL; 138 } 139 if (evsendlive_ptr_ != NULL) { 140 evtimer_del(evsendlive_ptr_); 141 delete evsendlive_ptr_; 142 evsendlive_ptr_ = NULL; 143 } 144 } 145 146 HashTree * Channel::hashtree() 147 { 148 return transfer()->hashtree(); 149 } 150 151 bool Channel::IsComplete() 152 { 153 154 if (transfer()->ttype() == LIVE_TRANSFER) 155 return PeerIsSource(); 156 157 // Check if peak hash bins are filled. 158 if (hashtree()->peak_count() == 0) 159 return false; 160 161 for (int i=0; i<hashtree()->peak_count(); i++) { 162 bin_t peak = hashtree()->peak(i); 163 if (!ack_in_.is_filled(peak)) 164 return false; 165 } 166 return true; 167 } 168 169 170 171 uint16_t Channel::GetMyPort() 172 { 173 Address addr; 174 // Arno, 2013-06-05: Retrieving addr, so use largest possible sockaddr 175 socklen_t addrlen = sizeof(struct sockaddr_storage); 176 if (getsockname(socket_, (struct sockaddr *)&addr.addr, &addrlen) < 0) { 177 print_error("error on getsockname"); 178 return 0; 179 } else 180 return addr.port(); 181 } 182 183 bool Channel::IsDiffSenderOrDuplicate(Address addr, uint32_t chid) 184 { 185 if (peer() != addr) { 186 // Got message from different address than I send to 187 // 188 if (!own_id_mentioned_ && addr.is_private()) { 189 // Arno, 2012-02-27: Got HANDSHAKE reply from IANA private address, 190 // check for duplicate connections: 191 // 192 // When two peers A and B are behind the same firewall, they will get 193 // extB, resp. extA addresses from the tracker. They will both 194 // connect to their counterpart but because the incoming packet 195 // will be from the intNAT address the duplicates are not 196 // recognized. 197 // 198 // Solution: when the second datagram comes in (HANDSHAKE reply), 199 // see if you have had a first datagram from the same addr 200 // (HANDSHAKE). If so, close the channel if his port number is 201 // larger than yours (such that one channel remains). 202 // 203 recv_peer_ = addr; 204 205 Channel *c = transfer()->FindChannel(addr,this); 206 if (c == NULL) 207 return false; 208 209 // I already initiated a connection to this peer, 210 // this new incoming message would establish a duplicate. 211 // One must break the connection, decide using port 212 // number: 213 dprintf("%s #%" PRIu32 " found duplicate channel to %s\n", 214 tintstr(),chid,addr.str().c_str()); 215 216 if (addr.port() > GetMyPort()) { 217 dprintf("%s #%" PRIu32 " closing duplicate channel to %s\n", 218 tintstr(),chid,addr.str().c_str()); 219 return true; 220 } 221 } else { 222 // Received HANDSHAKE reply from other address than I sent 223 // HANDSHAKE to, and the address is not an IANA private 224 // address (=no NAT in play), so close. 225 dprintf("%s #%" PRIu32 " invalid peer address %s!=%s\n", 226 tintstr(),chid,peer().str().c_str(),addr.str().c_str()); 227 return true; 228 } 229 } 230 return false; 231 } 232 233 234 235 236 237 238 239 /* 240 * Class methods 241 */ 242 tint Channel::Time() 243 { 244 //HiResTimeOfDay* tod = HiResTimeOfDay::Instance(); 245 //tint ret = tod->getTimeUSec(); 246 //DLOG(INFO)<<"now is "<<ret; 247 return now_t::now = usec_time(); 248 } 249 250 // SOCKMGMT 251 evutil_socket_t Channel::Bind(Address address, sckrwecb_t callbacks) 252 { 253 struct sockaddr_storage sa = address; 254 evutil_socket_t fd; 255 // Arno, 2013-06-05: MacOS X bind fails if sizeof(struct sockaddr_storage) is passed. 256 int len = address.get_family_sockaddr_length(), sndbuf=1<<20, rcvbuf=1<<20; 257 #define dbnd_ensure(x) { if (!(x)) { \ 258 print_error("binding fails"); close_socket(fd); return INVALID_SOCKET; } } 259 dbnd_ensure((fd = socket(address.get_family(), SOCK_DGRAM, 0)) >= 0); 260 dbnd_ensure(make_socket_nonblocking(fd)); // FIXME may remove this 261 int enable = true; 262 dbnd_ensure(setsockopt(fd, SOL_SOCKET, SO_SNDBUF, 263 (setsockoptptr_t)&sndbuf, sizeof(int)) == 0); 264 dbnd_ensure(setsockopt(fd, SOL_SOCKET, SO_RCVBUF, 265 (setsockoptptr_t)&rcvbuf, sizeof(int)) == 0); 266 //setsockopt(fd, SOL_SOCKET, SO_REUSEADDR, (setsockoptptr_t)&enable, sizeof(int)); 267 if (address.get_family() == AF_INET6) { 268 // Arno, 2012-12-04: Enable IPv4 on this IPv6 socket, addresses 269 // show up as IPv4-mapped IPv6. 270 int no = 0; 271 dbnd_ensure(setsockopt(fd, IPPROTO_IPV6, IPV6_V6ONLY, (setsockoptptr_t)&no, sizeof(no)) == 0); 272 } 273 dbnd_ensure(::bind(fd, (sockaddr*)&sa, len) == 0); 274 275 callbacks.sock = fd; 276 sock_open[sock_count++] = callbacks; 277 return fd; 278 } 279 280 Address Channel::BoundAddress(evutil_socket_t sock) 281 { 282 283 struct sockaddr_storage myaddr; 284 // Arno, 2013-06-05: Retrieving addr, so use largest possible sockaddr 285 socklen_t mylen = sizeof(struct sockaddr_storage); 286 int ret = getsockname(sock,(sockaddr*)&myaddr,&mylen); 287 if (ret >= 0) { 288 return Address(myaddr); 289 } else { 290 return Address(); 291 } 292 } 293 294 295 Address swift::BoundAddress(evutil_socket_t sock) 296 { 297 return Channel::BoundAddress(sock); 298 } 299 300 301 int Channel::SendTo(evutil_socket_t sock, const Address& addr, struct evbuffer *evb) 302 { 303 int length = evbuffer_get_length(evb); 304 int r = sendto(sock,(const char *)evbuffer_pullup(evb, length),length,0, 305 (struct sockaddr*)&(addr.addr),addr.get_family_sockaddr_length()); 306 // SCHAAP: 2012-06-16 - How about EAGAIN and EWOULDBLOCK? Do we just drop the packet then as well? 307 if (r<0) { 308 print_error("can't send"); 309 evbuffer_drain(evb, length); // Arno: behaviour is to pretend the packet got lost 310 } else { 311 evbuffer_drain(evb,r); 312 global_dgrams_up++; 313 global_raw_bytes_up+=length; 314 } 315 Time(); 316 return r; 317 } 318 319 int Channel::RecvFrom(evutil_socket_t sock, Address& addr, struct evbuffer *evb) 320 { 321 // Arno, 2013-06-05: Incoming addr, so use largest possible sockaddr 322 socklen_t addrlen = sizeof(struct sockaddr_storage); 323 struct evbuffer_iovec vec; 324 if (evbuffer_reserve_space(evb, SWIFT_MAX_RECV_DGRAM_SIZE, &vec, 1) < 0) { 325 print_error("error on evbuffer_reserve_space"); 326 return 0; 327 } 328 int length = recvfrom(sock, (char *)vec.iov_base, SWIFT_MAX_RECV_DGRAM_SIZE, 0, 329 (struct sockaddr*)&(addr.addr), &addrlen); 330 if (length<0) { 331 length = 0; 332 333 // Linux and Windows report "ICMP port unreachable" if the dest port could 334 // not be reached: 335 // http://support.microsoft.com/kb/260018 336 // http://www.faqs.org/faqs/unix-faq/socket/ 337 #ifdef _WIN32 338 if (WSAGetLastError() == 10054) // Sometimes errno == 2 ?! 339 #else 340 if (errno == ECONNREFUSED) 341 #endif 342 { 343 CloseChannelByAddress(addr); 344 } else 345 print_error("error on recv"); 346 } 347 vec.iov_len = length; 348 if (evbuffer_commit_space(evb, &vec, 1) < 0) { 349 length = 0; 350 print_error("error on evbuffer_commit_space"); 351 } 352 global_dgrams_down++; 353 global_raw_bytes_down+=length; 354 Time(); 355 return length; 356 } 357 358 359 void Channel::CloseSocket(evutil_socket_t sock) 360 { 361 for (int i=0; i<sock_count; i++) 362 if (sock_open[i].sock==sock) 363 sock_open[i] = sock_open[--sock_count]; 364 if (!close_socket(sock)) 365 print_error("on closing a socket"); 366 } 367 368 void Channel::Shutdown() 369 { 370 while (sock_count--) 371 CloseSocket(sock_open[sock_count].sock); 372 } 373 374 int Channel::DecodeID(int scrambled) 375 { 376 return scrambled ^ (int)start; 377 } 378 int Channel::EncodeID(int unscrambled) 379 { 380 return unscrambled ^ (int)start; 381 } 382 383 384 bool Channel::IsMovingForward() 385 { 386 if (transfer() == NULL) 387 return false; 388 389 bool fwd=false; 390 if (transfer()->ttype() == FILE_TRANSFER) { 391 //FileTranfer *ft=(FileTransfer *)transfer(); 392 if (swift::IsComplete(transfer()->td())) { 393 // Seeding peer, moving forward is uploading 394 if (bytes_up_ > old_movingfwd_bytes_) { 395 fwd=true; 396 } 397 old_movingfwd_bytes_ = bytes_up_; 398 } else { 399 // Leeching peer, moving forward is downloading 400 if (bytes_down_ > old_movingfwd_bytes_) { 401 fwd=true; 402 } 403 old_movingfwd_bytes_ = bytes_down_; 404 } 405 406 } else { 407 LiveTransfer *lt = (LiveTransfer *)transfer(); 408 if (lt->am_source()) { 409 fwd = true; // simplification 410 } else { 411 // Live peer, moving forward is downloading 412 if (bytes_down_ > old_movingfwd_bytes_) { 413 fwd=true; 414 } 415 old_movingfwd_bytes_ = bytes_down_; 416 } 417 } 418 return fwd; 419 } 420 421 bool Channel::is_established() 422 { 423 if (hs_in_ == NULL) 424 return false; 425 else 426 return (hs_in_->peer_channel_id_ && own_id_mentioned_); 427 } 428 429 430 bool Channel::PeerIsSource() 431 { 432 LiveTransfer *lt = (LiveTransfer *)transfer_; 433 return (lt->GetSourceAddress() != Address() && (peer_ == lt->GetSourceAddress() 434 || recv_peer_ == lt->GetSourceAddress())); 435 } 436 437 438 439 /* 440 * Utility methods 441 */ 442 443 const char* swift::tintstr(tint time) 444 { 445 if (time==0) 446 time = now_t::now; 447 static char ret_str[4][32]; // wow 448 static int i; 449 i = (i+1) & 3; 450 if (time==TINT_NEVER) 451 return "NEVER"; 452 time -= Channel::epoch; 453 assert(time>0); 454 int hours = time/TINT_HOUR; 455 time %= TINT_HOUR; 456 int mins = time/TINT_MIN; 457 time %= TINT_MIN; 458 int secs = time/TINT_SEC; 459 time %= TINT_SEC; 460 int msecs = time/TINT_MSEC; 461 time %= TINT_MSEC; 462 int usecs = time/TINT_uSEC; 463 sprintf(ret_str[i],"%i_%02i_%02i_%03i_%03i",hours,mins,secs,msecs,usecs); 464 return ret_str[i]; 465 } 466 467 468 int swift::evbuffer_add_string(struct evbuffer *evb, std::string str) 469 { 470 return evbuffer_add(evb, str.c_str(), str.size()); 471 } 472 473 int swift::evbuffer_add_8(struct evbuffer *evb, uint8_t b) 474 { 475 return evbuffer_add(evb, &b, 1); 476 } 477 478 int swift::evbuffer_add_16be(struct evbuffer *evb, uint16_t w) 479 { 480 uint16_t wbe = htons(w); 481 return evbuffer_add(evb, &wbe, 2); 482 } 483 484 int swift::evbuffer_add_32be(struct evbuffer *evb, uint32_t i) 485 { 486 uint32_t ibe = htonl(i); 487 return evbuffer_add(evb, &ibe, 4); 488 } 489 490 int swift::evbuffer_add_64be(struct evbuffer *evb, uint64_t l) 491 { 492 uint32_t lbe[2]; 493 lbe[0] = htonl((uint32_t)(l>>32)); 494 lbe[1] = htonl((uint32_t)(l&0xffffffff)); 495 return evbuffer_add(evb, lbe, 8); 496 } 497 498 int swift::evbuffer_add_hash(struct evbuffer *evb, const Sha1Hash& hash) 499 { 500 return evbuffer_add(evb, hash.bits, Sha1Hash::SIZE); 501 } 502 503 // PPSP 504 int swift::evbuffer_add_chunkaddr(struct evbuffer *evb, bin_t &b, popt_chunk_addr_t chunk_addr) 505 { 506 int ret = -1; 507 if (chunk_addr == POPT_CHUNK_ADDR_BIN32) 508 ret = evbuffer_add_32be(evb, bin_toUInt32(b)); 509 else if (chunk_addr == POPT_CHUNK_ADDR_CHUNK32) { 510 ret = evbuffer_add_32be(evb, (uint32_t)b.base_offset()); 511 ret = evbuffer_add_32be(evb, (uint32_t)(b.base_offset()+b.base_length()-1)); // end is inclusive 512 } 513 return ret; 514 } 515 516 int swift::evbuffer_add_pexaddr(struct evbuffer *evb, Address& a) 517 { 518 int ret = -1; 519 if (a.get_family() == AF_INET) { 520 ret = evbuffer_add_8(evb, SWIFT_PEX_RESv4); 521 ret = evbuffer_add_32be(evb, a.ipv4()); 522 ret = evbuffer_add_16be(evb, a.port()); 523 } else { 524 struct in6_addr ipv6 = a.ipv6(); 525 526 ret = evbuffer_add_8(evb, SWIFT_PEX_RESv6); 527 for (int i=0; i<16; i++) 528 ret = evbuffer_add_8(evb, ipv6.s6_addr[i]); 529 ret = evbuffer_add_16be(evb, a.port()); 530 } 531 return ret; 532 } 533 534 535 uint8_t swift::evbuffer_remove_8(struct evbuffer *evb) 536 { 537 uint8_t b; 538 if (evbuffer_remove(evb, &b, 1) < 1) 539 return 0; 540 return b; 541 } 542 543 uint16_t swift::evbuffer_remove_16be(struct evbuffer *evb) 544 { 545 uint16_t wbe; 546 if (evbuffer_remove(evb, &wbe, 2) < 2) 547 return 0; 548 return ntohs(wbe); 549 } 550 551 uint32_t swift::evbuffer_remove_32be(struct evbuffer *evb) 552 { 553 uint32_t ibe; 554 if (evbuffer_remove(evb, &ibe, 4) < 4) 555 return 0; 556 return ntohl(ibe); 557 } 558 559 uint64_t swift::evbuffer_remove_64be(struct evbuffer *evb) 560 { 561 uint32_t lbe[2]; 562 if (evbuffer_remove(evb, lbe, 8) < 8) 563 return 0; 564 uint64_t l = ntohl(lbe[0]); 565 l<<=32; 566 l |= ntohl(lbe[1]); 567 return l; 568 } 569 570 Sha1Hash swift::evbuffer_remove_hash(struct evbuffer* evb) 571 { 572 char bits[Sha1Hash::SIZE]; 573 if (evbuffer_remove(evb, bits, Sha1Hash::SIZE) < Sha1Hash::SIZE) 574 return Sha1Hash::ZERO; 575 return Sha1Hash(false, bits); 576 } 577 578 // PPSP 579 binvector swift::evbuffer_remove_chunkaddr(struct evbuffer *evb, popt_chunk_addr_t chunk_addr) 580 { 581 binvector bv; 582 if (chunk_addr == POPT_CHUNK_ADDR_BIN32) { 583 bin_t pos = bin_fromUInt32(evbuffer_remove_32be(evb)); 584 bv.push_back(pos); 585 } else if (chunk_addr == POPT_CHUNK_ADDR_CHUNK32) { 586 uint32_t schunk = evbuffer_remove_32be(evb); 587 uint32_t echunk = evbuffer_remove_32be(evb); 588 if (schunk <= echunk) // Bad input protection 589 swift::chunk32_to_bin32(schunk,echunk,&bv); 590 } 591 return bv; 592 } 593 594 Address swift::evbuffer_remove_pexaddr(struct evbuffer *evb, int family) 595 { 596 int ret = -1; 597 if (family == AF_INET) { 598 uint32_t ipv4 = evbuffer_remove_32be(evb); 599 uint16_t port = evbuffer_remove_16be(evb); 600 Address addr(ipv4,port); 601 return addr; 602 } else { 603 struct in6_addr ipv6; 604 for (int i=0; i<16; i++) 605 ipv6.s6_addr[i] = evbuffer_remove_8(evb); 606 uint16_t port = evbuffer_remove_16be(evb); 607 Address addr(ipv6,port); 608 return addr; 609 } 610 } 611 612 613 614 /** Convert a chunk32 chunk specification to a list of bins. A chunk32 spec is 615 * a (start chunk ID, end chunk ID) pair, where chunk ID is just a numbering 616 * from 0 to N of all chunks, equivalent to the leaves in a bin tree. This 617 * method finds which bins describe this range. 618 */ 619 void swift::chunk32_to_bin32(uint32_t schunk, uint32_t echunk, binvector *bvptr) 620 { 621 bin_t s(0,schunk); 622 bin_t e(0,echunk); 623 624 bin_t cur = s; 625 while (true) { 626 // Move up in tree till we exceed either start or end. If so, the 627 // previous node belongs to the range description. Next, we start at 628 // the left most chunk in the subtree next to the previous node, and see 629 // how far up we can go there. 630 //fprintf(stderr,"\ncur %s par left %s par right %s\n", cur.str().c_str(), cur.parent().base_left().str().c_str(), cur.parent().base_right().str().c_str()); 631 if (cur.parent().base_left() < s || cur.parent().base_right() > e) { 632 /*if (cur.parent().base_left() < s) 633 fprintf(stderr,"parent %s left %s before s, add %s\n", cur.parent().str().c_str(), cur.parent().base_left().str().c_str(), cur.str().c_str() ); 634 if (cur.parent().base_right() > e) 635 fprintf(stderr,"parent %s right %s exceeds e, add %s\n", cur.parent().str().c_str(), cur.parent().base_right().str().c_str(), cur.str().c_str() ); 636 */ 637 bvptr->push_back(cur); 638 639 if (cur.parent().base_left() < s) 640 cur = bin_t(0,cur.parent().base_right().layer_offset()+1); 641 else 642 cur = bin_t(0,cur.base_right().layer_offset()+1); 643 644 //fprintf(stderr,"newcur %s\n", cur.str().c_str() ); 645 646 if (cur >= e) { 647 if (cur == e) { 648 // fprintf(stderr,"adding e %s\n", cur.str().c_str() ); 649 bvptr->push_back(e); 650 } 651 break; 652 } 653 } else 654 cur = cur.parent(); 655 } 656 } 657 658 659 /* 660 * Calculate the complement of 2 bins, where origbin covers cancelbin. 661 * I.e., origbin is turned into a list of base bins that are covered by 662 * origbin but not by cancelbin. 663 */ 664 binvector swift::bin_fragment(bin_t &origbin, bin_t &cancelbin) 665 { 666 // origbin covers cancelbin 667 // Easy: just split into base bins 668 binvector bv; 669 bin_t origsbase = origbin.base_left(); 670 bin_t origebase = origbin.base_right(); 671 bin_t cansbase = cancelbin.base_left(); 672 bin_t canebase = cancelbin.base_right(); 673 bin_t curbin = origsbase; 674 while (curbin < cansbase) { 675 bv.push_back(curbin); 676 curbin = bin_t(0,curbin.base_offset()+1); 677 } 678 curbin = bin_t(0,canebase.base_offset()+1); 679 while (curbin <= origebase) { 680 bv.push_back(curbin); 681 curbin = bin_t(0,curbin.base_offset()+1); 682 } 683 684 return bv; 685 } 686