1 /* 2 3 Copyright (c) 2008-2018, Arvid Norberg 4 All rights reserved. 5 6 Redistribution and use in source and binary forms, with or without 7 modification, are permitted provided that the following conditions 8 are met: 9 10 * Redistributions of source code must retain the above copyright 11 notice, this list of conditions and the following disclaimer. 12 * Redistributions in binary form must reproduce the above copyright 13 notice, this list of conditions and the following disclaimer in 14 the documentation and/or other materials provided with the distribution. 15 * Neither the name of the author nor the names of its 16 contributors may be used to endorse or promote products derived 17 from this software without specific prior written permission. 18 19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 23 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 POSSIBILITY OF SUCH DAMAGE. 30 31 */ 32 33 #include "libtorrent/config.hpp" 34 35 #if TORRENT_ABI_VERSION == 1 36 37 #include "libtorrent/lazy_entry.hpp" 38 #include "libtorrent/bdecode.hpp" // for error codes and escape_string 39 #include "libtorrent/string_util.hpp" // for is_digit 40 #include <algorithm> 41 #include <cstring> // for memset 42 #include <limits> // for numeric_limits 43 #include <cstdio> // for snprintf 44 #include <cinttypes> // for PRId64 et.al. 45 46 namespace { 47 48 const int lazy_entry_grow_factor = 150; // percent 49 const int lazy_entry_dict_init = 5; 50 const int lazy_entry_list_init = 5; 51 } 52 53 namespace libtorrent { 54 55 namespace { 56 fail(int * error_pos,std::vector<lazy_entry * > & stack,char const * start,char const * orig_start)57 int fail(int* error_pos 58 , std::vector<lazy_entry*>& stack 59 , char const* start 60 , char const* orig_start) 61 { 62 while (!stack.empty()) { 63 lazy_entry* top = stack.back(); 64 if (top->type() == lazy_entry::dict_t || top->type() == lazy_entry::list_t) 65 { 66 top->pop(); 67 break; 68 } 69 stack.pop_back(); 70 } 71 if (error_pos) *error_pos = int(start - orig_start); 72 return -1; 73 } 74 75 #define TORRENT_FAIL_BDECODE(code) do { ec = make_error_code(code); return fail(error_pos, stack, start, orig_start); } TORRENT_WHILE_0 76 find_char(char const * start,char const * end,char delimiter)77 char const* find_char(char const* start, char const* end, char delimiter) 78 { 79 while (start < end && *start != delimiter) ++start; 80 return start; 81 } 82 parse_string(char const * start,char const * end,bdecode_errors::error_code_enum & e,std::int64_t & len)83 char const* parse_string(char const* start, char const* end 84 , bdecode_errors::error_code_enum& e, std::int64_t& len) 85 { 86 start = parse_int(start, end, ':', len, e); 87 if (e) return start; 88 if (start == end) 89 { 90 e = bdecode_errors::expected_colon; 91 } 92 else 93 { 94 // remaining buffer size excluding ':' 95 const ptrdiff_t buff_size = end - start - 1; 96 if (len > buff_size) 97 { 98 e = bdecode_errors::unexpected_eof; 99 } 100 else if (len < 0) 101 { 102 e = bdecode_errors::overflow; 103 } 104 else 105 { 106 ++start; 107 if (start >= end) e = bdecode_errors::unexpected_eof; 108 } 109 } 110 return start; 111 } 112 113 } // anonymous namespace 114 115 #if TORRENT_ABI_VERSION == 1 lazy_bdecode(char const * start,char const * end,lazy_entry & ret,int depth_limit,int item_limit)116 int lazy_bdecode(char const* start, char const* end 117 , lazy_entry& ret, int depth_limit, int item_limit) 118 { 119 error_code ec; 120 int pos; 121 return lazy_bdecode(start, end, ret, ec, &pos, depth_limit, item_limit); 122 } 123 #endif 124 125 // return 0 = success lazy_bdecode(char const * start,char const * end,lazy_entry & ret,error_code & ec,int * error_pos,int depth_limit,int item_limit)126 int lazy_bdecode(char const* start, char const* end, lazy_entry& ret 127 , error_code& ec, int* error_pos, int depth_limit, int item_limit) 128 { 129 char const* const orig_start = start; 130 ret.clear(); 131 132 std::vector<lazy_entry*> stack; 133 134 if (start == end) 135 TORRENT_FAIL_BDECODE(bdecode_errors::unexpected_eof); 136 137 stack.push_back(&ret); 138 while (start <= end) 139 { 140 if (stack.empty()) break; // done! 141 142 lazy_entry* top = stack.back(); 143 144 if (int(stack.size()) > depth_limit) TORRENT_FAIL_BDECODE(bdecode_errors::depth_exceeded); 145 if (start >= end) TORRENT_FAIL_BDECODE(bdecode_errors::unexpected_eof); 146 char t = *start; 147 ++start; 148 if (start >= end && t != 'e') TORRENT_FAIL_BDECODE(bdecode_errors::unexpected_eof); 149 150 switch (top->type()) 151 { 152 case lazy_entry::dict_t: 153 { 154 if (t == 'e') 155 { 156 top->set_end(start); 157 stack.pop_back(); 158 continue; 159 } 160 if (!is_digit(t)) TORRENT_FAIL_BDECODE(bdecode_errors::expected_digit); 161 std::int64_t len = t - '0'; 162 bdecode_errors::error_code_enum e = bdecode_errors::no_error; 163 start = parse_string(start, end, e, len); 164 if (e) TORRENT_FAIL_BDECODE(e); 165 166 lazy_entry* ent = top->dict_append(start); 167 if (ent == nullptr) TORRENT_FAIL_BDECODE(boost::system::errc::not_enough_memory); 168 start += len; 169 if (start >= end) TORRENT_FAIL_BDECODE(bdecode_errors::unexpected_eof); 170 stack.push_back(ent); 171 t = *start; 172 ++start; 173 break; 174 } 175 case lazy_entry::list_t: 176 { 177 if (t == 'e') 178 { 179 top->set_end(start); 180 stack.pop_back(); 181 continue; 182 } 183 lazy_entry* ent = top->list_append(); 184 if (ent == nullptr) TORRENT_FAIL_BDECODE(boost::system::errc::not_enough_memory); 185 stack.push_back(ent); 186 break; 187 } 188 case lazy_entry::int_t: 189 case lazy_entry::string_t: 190 case lazy_entry::none_t: 191 break; 192 } 193 194 --item_limit; 195 if (item_limit <= 0) TORRENT_FAIL_BDECODE(bdecode_errors::limit_exceeded); 196 197 top = stack.back(); 198 switch (t) 199 { 200 case 'd': 201 top->construct_dict(start - 1); 202 break; 203 case 'l': 204 top->construct_list(start - 1); 205 break; 206 case 'i': 207 { 208 char const* int_start = start; 209 start = find_char(start, end, 'e'); 210 top->construct_int(int_start, int(start - int_start)); 211 if (start == end) TORRENT_FAIL_BDECODE(bdecode_errors::unexpected_eof); 212 TORRENT_ASSERT(*start == 'e'); 213 ++start; 214 stack.pop_back(); 215 break; 216 } 217 default: 218 { 219 220 if (!is_digit(t)) TORRENT_FAIL_BDECODE(bdecode_errors::expected_value); 221 std::int64_t len = t - '0'; 222 bdecode_errors::error_code_enum e = bdecode_errors::no_error; 223 start = parse_string(start, end, e, len); 224 if (e) TORRENT_FAIL_BDECODE(e); 225 226 top->construct_string(start, int(len)); 227 start += len; 228 stack.pop_back(); 229 break; 230 } 231 } 232 } 233 return 0; 234 } 235 capacity() const236 int lazy_entry::capacity() const 237 { 238 TORRENT_ASSERT(m_type == dict_t || m_type == list_t); 239 if (m_data.list == nullptr) return 0; 240 if (m_type == dict_t) 241 return int(m_data.dict[0].val.m_len); 242 else 243 return int(m_data.list[0].m_len); 244 } 245 int_value() const246 std::int64_t lazy_entry::int_value() const 247 { 248 TORRENT_ASSERT(m_type == int_t); 249 std::int64_t val = 0; 250 bool const negative = (*m_data.start == '-'); 251 bdecode_errors::error_code_enum ec = bdecode_errors::no_error; 252 parse_int(m_data.start + int(negative) 253 , m_data.start + m_size, 'e', val, ec); 254 if (ec) return 0; 255 if (negative) val = -val; 256 return val; 257 } 258 dict_append(char const * name)259 lazy_entry* lazy_entry::dict_append(char const* name) 260 { 261 TORRENT_ASSERT(m_type == dict_t); 262 TORRENT_ASSERT(int(m_size) <= this->capacity()); 263 if (m_data.dict == nullptr) 264 { 265 int const capacity = lazy_entry_dict_init; 266 m_data.dict = new (std::nothrow) lazy_dict_entry[capacity + 1]; 267 if (m_data.dict == nullptr) return nullptr; 268 m_data.dict[0].val.m_len = std::uint32_t(capacity); 269 } 270 else if (int(m_size) == this->capacity()) 271 { 272 std::size_t const capacity = std::size_t(this->capacity()) * lazy_entry_grow_factor / 100; 273 auto* tmp = new (std::nothrow) lazy_dict_entry[capacity + 1]; 274 if (tmp == nullptr) return nullptr; 275 std::move(m_data.dict, m_data.dict + m_size + 1, tmp); 276 277 delete[] m_data.dict; 278 m_data.dict = tmp; 279 m_data.dict[0].val.m_len = std::uint32_t(capacity); 280 } 281 282 TORRENT_ASSERT(int(m_size) < this->capacity()); 283 lazy_dict_entry& ret = m_data.dict[1 + m_size++]; 284 ret.name = name; 285 return &ret.val; 286 } 287 pop()288 void lazy_entry::pop() 289 { 290 if (m_size > 0) --m_size; 291 } 292 293 namespace { 294 295 // the number of decimal digits needed 296 // to represent the given value num_digits(int val)297 int num_digits(int val) 298 { 299 int ret = 1; 300 while (val >= 10) 301 { 302 ++ret; 303 val /= 10; 304 } 305 return ret; 306 } 307 } 308 construct_string(char const * start,int const length)309 void lazy_entry::construct_string(char const* start, int const length) 310 { 311 TORRENT_ASSERT(m_type == none_t); 312 TORRENT_ASSERT(length >= 0); 313 m_type = string_t; 314 m_data.start = start; 315 m_size = std::uint32_t(length); 316 m_begin = start - 1 - num_digits(length); 317 m_len = std::uint32_t(start - m_begin + length); 318 } 319 320 namespace { 321 322 // str1 is 0-terminated 323 // str2 is not, str2 is len2 chars string_equal(char const * str1,char const * str2,int len2)324 bool string_equal(char const* str1, char const* str2, int len2) 325 { 326 while (len2 > 0) 327 { 328 if (*str1 != *str2) return false; 329 if (*str1 == 0) return false; 330 ++str1; 331 ++str2; 332 --len2; 333 } 334 return *str1 == 0; 335 } 336 } 337 dict_at(int const i) const338 std::pair<std::string, lazy_entry const*> lazy_entry::dict_at(int const i) const 339 { 340 TORRENT_ASSERT(m_type == dict_t); 341 TORRENT_ASSERT(i < int(m_size)); 342 lazy_dict_entry const& e = m_data.dict[i + 1]; 343 TORRENT_ASSERT(e.val.m_begin >= e.name); 344 return std::make_pair(std::string(e.name, std::size_t(e.val.m_begin - e.name)), &e.val); 345 } 346 dict_find_string_value(char const * name) const347 std::string lazy_entry::dict_find_string_value(char const* name) const 348 { 349 lazy_entry const* e = dict_find(name); 350 if (e == nullptr || e->type() != lazy_entry::string_t) return std::string(); 351 return e->string_value(); 352 } 353 dict_find_pstr(char const * name) const354 pascal_string lazy_entry::dict_find_pstr(char const* name) const 355 { 356 lazy_entry const* e = dict_find(name); 357 if (e == nullptr || e->type() != lazy_entry::string_t) return {nullptr, 0}; 358 return e->string_pstr(); 359 } 360 dict_find_string(char const * name) const361 lazy_entry const* lazy_entry::dict_find_string(char const* name) const 362 { 363 lazy_entry const* e = dict_find(name); 364 if (e == nullptr || e->type() != lazy_entry::string_t) return nullptr; 365 return e; 366 } 367 dict_find_int(char const * name) const368 lazy_entry const* lazy_entry::dict_find_int(char const* name) const 369 { 370 lazy_entry const* e = dict_find(name); 371 if (e == nullptr || e->type() != lazy_entry::int_t) return nullptr; 372 return e; 373 } 374 dict_find_int_value(char const * name,std::int64_t default_val) const375 std::int64_t lazy_entry::dict_find_int_value(char const* name 376 , std::int64_t default_val) const 377 { 378 lazy_entry const* e = dict_find(name); 379 if (e == nullptr || e->type() != lazy_entry::int_t) return default_val; 380 return e->int_value(); 381 } 382 dict_find_dict(char const * name) const383 lazy_entry const* lazy_entry::dict_find_dict(char const* name) const 384 { 385 lazy_entry const* e = dict_find(name); 386 if (e == nullptr || e->type() != lazy_entry::dict_t) return nullptr; 387 return e; 388 } 389 dict_find_dict(std::string const & name) const390 lazy_entry const* lazy_entry::dict_find_dict(std::string const& name) const 391 { 392 lazy_entry const* e = dict_find(name); 393 if (e == nullptr || e->type() != lazy_entry::dict_t) return nullptr; 394 return e; 395 } 396 dict_find_list(char const * name) const397 lazy_entry const* lazy_entry::dict_find_list(char const* name) const 398 { 399 lazy_entry const* e = dict_find(name); 400 if (e == nullptr || e->type() != lazy_entry::list_t) return nullptr; 401 return e; 402 } 403 dict_find(char const * name)404 lazy_entry* lazy_entry::dict_find(char const* name) 405 { 406 TORRENT_ASSERT(m_type == dict_t); 407 for (int i = 0; i < int(m_size); ++i) 408 { 409 lazy_dict_entry& e = m_data.dict[i + 1]; 410 if (string_equal(name, e.name, int(e.val.m_begin - e.name))) 411 return &e.val; 412 } 413 return nullptr; 414 } 415 dict_find(std::string const & name)416 lazy_entry* lazy_entry::dict_find(std::string const& name) 417 { 418 TORRENT_ASSERT(m_type == dict_t); 419 for (int i = 0; i < int(m_size); ++i) 420 { 421 lazy_dict_entry& e = m_data.dict[i+1]; 422 if (int(name.size()) != e.val.m_begin - e.name) continue; 423 if (std::equal(name.begin(), name.end(), e.name)) 424 return &e.val; 425 } 426 return nullptr; 427 } 428 list_append()429 lazy_entry* lazy_entry::list_append() 430 { 431 TORRENT_ASSERT(m_type == list_t); 432 TORRENT_ASSERT(int(m_size) <= this->capacity()); 433 if (m_data.start == nullptr) 434 { 435 int const capacity = lazy_entry_list_init; 436 m_data.list = new (std::nothrow) lazy_entry[capacity + 1]; 437 if (m_data.list == nullptr) return nullptr; 438 m_data.list[0].m_len = std::uint32_t(capacity); 439 } 440 else if (int(m_size) == this->capacity()) 441 { 442 std::size_t const capacity = std::size_t(this->capacity()) * lazy_entry_grow_factor / 100; 443 lazy_entry* tmp = new (std::nothrow) lazy_entry[capacity + 1]; 444 if (tmp == nullptr) return nullptr; 445 std::move(m_data.list, m_data.list + m_size + 1, tmp); 446 447 delete[] m_data.list; 448 m_data.list = tmp; 449 m_data.list[0].m_len = std::uint32_t(capacity); 450 } 451 452 TORRENT_ASSERT(int(m_size) < this->capacity()); 453 return &m_data.list[1 + (m_size++)]; 454 } 455 list_string_value_at(int i) const456 std::string lazy_entry::list_string_value_at(int i) const 457 { 458 lazy_entry const* e = list_at(i); 459 if (e == nullptr || e->type() != lazy_entry::string_t) return std::string(); 460 return e->string_value(); 461 } 462 list_pstr_at(int i) const463 pascal_string lazy_entry::list_pstr_at(int i) const 464 { 465 lazy_entry const* e = list_at(i); 466 if (e == nullptr || e->type() != lazy_entry::string_t) return {nullptr, 0}; 467 return e->string_pstr(); 468 } 469 list_int_value_at(int i,std::int64_t default_val) const470 std::int64_t lazy_entry::list_int_value_at(int i, std::int64_t default_val) const 471 { 472 lazy_entry const* e = list_at(i); 473 if (e == nullptr || e->type() != lazy_entry::int_t) return default_val; 474 return e->int_value(); 475 } 476 clear()477 void lazy_entry::clear() 478 { 479 switch (m_type) 480 { 481 case list_t: 482 delete[] m_data.list; 483 break; 484 case dict_t: 485 delete[] m_data.dict; 486 break; 487 default: break; 488 } 489 m_data.start = nullptr; 490 m_size = 0; 491 m_type = none_t; 492 } 493 data_section() const494 std::pair<char const*, int> lazy_entry::data_section() const 495 { 496 return {m_begin, m_len}; 497 } 498 lazy_entry(lazy_entry && other)499 lazy_entry::lazy_entry(lazy_entry&& other) 500 : lazy_entry() 501 { 502 this->swap(other); 503 } 504 operator =(lazy_entry && other)505 lazy_entry& lazy_entry::operator=(lazy_entry&& other) 506 { 507 this->swap(other); 508 return *this; 509 } 510 511 namespace { 512 line_longer_than(lazy_entry const & e,int limit)513 int line_longer_than(lazy_entry const& e, int limit) 514 { 515 int line_len = 0; 516 switch (e.type()) 517 { 518 case lazy_entry::list_t: 519 line_len += 4; 520 if (line_len > limit) return -1; 521 for (int i = 0; i < e.list_size(); ++i) 522 { 523 int ret = line_longer_than(*e.list_at(i), limit - line_len); 524 if (ret == -1) return -1; 525 line_len += ret + 2; 526 } 527 break; 528 case lazy_entry::dict_t: 529 line_len += 4; 530 if (line_len > limit) return -1; 531 for (int i = 0; i < e.dict_size(); ++i) 532 { 533 line_len += 4 + int(e.dict_at(i).first.size()); 534 if (line_len > limit) return -1; 535 int ret = line_longer_than(*e.dict_at(i).second, limit - line_len); 536 if (ret == -1) return -1; 537 line_len += ret + 1; 538 } 539 break; 540 case lazy_entry::string_t: 541 line_len += 3 + e.string_length(); 542 break; 543 case lazy_entry::int_t: 544 { 545 std::int64_t val = e.int_value(); 546 while (val > 0) 547 { 548 ++line_len; 549 val /= 10; 550 } 551 line_len += 2; 552 } 553 break; 554 case lazy_entry::none_t: 555 line_len += 4; 556 break; 557 } 558 559 if (line_len > limit) return -1; 560 return line_len; 561 } 562 print_string(std::string & ret,char const * str,int const len,bool single_line)563 void print_string(std::string& ret, char const* str, int const len, bool single_line) 564 { 565 TORRENT_ASSERT(len >= 0); 566 bool printable = true; 567 for (int i = 0; i < len; ++i) 568 { 569 char c = str[i]; 570 if (c >= 32 && c < 127) continue; 571 printable = false; 572 break; 573 } 574 ret += "'"; 575 if (printable) 576 { 577 if (single_line && len > 30) 578 { 579 ret.append(str, 14); 580 ret += "..."; 581 ret.append(str + len - 14, 14); 582 } 583 else 584 ret.append(str, std::size_t(len)); 585 ret += "'"; 586 return; 587 } 588 if (single_line && len > 20) 589 { 590 detail::escape_string(ret, str, 9); 591 ret += "..."; 592 detail::escape_string(ret, str + len - 9, 9); 593 } 594 else 595 { 596 detail::escape_string(ret, str, len); 597 } 598 ret += "'"; 599 } 600 } // anonymous namespace 601 print_entry(lazy_entry const & e,bool single_line,int indent)602 std::string print_entry(lazy_entry const& e, bool single_line, int indent) 603 { 604 char indent_str[200]; 605 std::memset(indent_str, ' ', 200); 606 indent_str[0] = ','; 607 indent_str[1] = '\n'; 608 indent_str[199] = 0; 609 if (indent < 197 && indent >= 0) indent_str[indent + 2] = 0; 610 std::string ret; 611 switch (e.type()) 612 { 613 case lazy_entry::none_t: return "none"; 614 case lazy_entry::int_t: 615 { 616 char str[100]; 617 std::snprintf(str, sizeof(str), "%" PRId64, e.int_value()); 618 return str; 619 } 620 case lazy_entry::string_t: 621 { 622 print_string(ret, e.string_ptr(), e.string_length(), single_line); 623 return ret; 624 } 625 case lazy_entry::list_t: 626 { 627 ret += '['; 628 bool one_liner = line_longer_than(e, 200) != -1 || single_line; 629 630 if (!one_liner) ret += indent_str + 1; 631 for (int i = 0; i < e.list_size(); ++i) 632 { 633 if (i == 0 && one_liner) ret += " "; 634 ret += print_entry(*e.list_at(i), single_line, indent + 2); 635 if (i < e.list_size() - 1) ret += (one_liner?", ":indent_str); 636 else ret += (one_liner?" ":indent_str+1); 637 } 638 ret += ']'; 639 return ret; 640 } 641 case lazy_entry::dict_t: 642 { 643 ret += '{'; 644 bool one_liner = line_longer_than(e, 200) != -1 || single_line; 645 646 if (!one_liner) ret += indent_str+1; 647 for (int i = 0; i < e.dict_size(); ++i) 648 { 649 if (i == 0 && one_liner) ret += ' '; 650 std::pair<std::string, lazy_entry const*> ent = e.dict_at(i); 651 print_string(ret, ent.first.c_str(), int(ent.first.size()), true); 652 ret += ": "; 653 ret += print_entry(*ent.second, single_line, indent + 2); 654 if (i < e.dict_size() - 1) ret += (one_liner?", ":indent_str); 655 else ret += (one_liner?" ":indent_str+1); 656 } 657 ret += "}"; 658 return ret; 659 } 660 } 661 return ret; 662 } 663 } 664 665 #endif // TORRENT_ABI_VERSION 666