src/lazy_bdecode.cpp

   1 /*
   2
   3 Copyright (c) 2008, 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/lazy_entry.hpp"
  34 #include <iostream>
  35 #include <iomanip>
  36 #include <cstring>
  37
  38 namespace
  39 {
  40         enum
  41         {
  42                 lazy_entry_grow_factor = 3,
  43                 lazy_entry_dict_init = 30,
  44                 lazy_entry_list_init = 50
  45         };
  46 }
  47
  48 namespace libtorrent
  49 {
  50         int fail_bdecode() { return -1; }
  51
  52         // fills in 'val' with what the string between start and the
  53         // first occurance of the delimiter is interpreted as an int.
  54         // return the pointer to the delimiter, or 0 if there is a
  55         // parse error. val should be initialized to zero
  56         char const* parse_int(char const* start, char const* end, char delimiter, boost::int64_t& val)
  57         {
  58                 while (start < end && *start != delimiter)
  59                 {
  60                         using namespace std;
  61                         if (!isdigit(*start)) { fail_bdecode(); return 0; }
  62                         val *= 10;
  63                         val += *start - '0';
  64                         ++start;
  65                 }
  66                 return start;
  67         }
  68
  69         char const* find_char(char const* start, char const* end, char delimiter)
  70         {
  71                 while (start < end && *start != delimiter) ++start;
  72                 return start;
  73         }
  74
  75         // return 0 = success
  76         int lazy_bdecode(char const* start, char const* end, lazy_entry& ret, int depth_limit)
  77         {
  78                 ret.clear();
  79                 if (start == end) return 0;
  80
  81                 std::vector<lazy_entry*> stack;
  82
  83                 stack.push_back(&ret);
  84                 while (start < end)
  85                 {
  86                         if (stack.empty()) break; // done!
  87
  88                         lazy_entry* top = stack.back();
  89
  90                         if (int(stack.size()) > depth_limit) return fail_bdecode();
  91                         if (start == end) return fail_bdecode();
  92                         char t = *start;
  93                         ++start;
  94                         if (start == end && t != 'e') return fail_bdecode();
  95
  96                         switch (top->type())
  97                         {
  98                                 case lazy_entry::dict_t:
  99                                 {
 100                                         if (t == 'e')
 101                                         {
 102                                                 top->set_end(start);
 103                                                 stack.pop_back();
 104                                                 continue;
 105                                         }
 106                                         boost::int64_t len = t - '0';
 107                                         start = parse_int(start, end, ':', len);
 108                                         if (start == 0 || start + len + 3 > end || *start != ':') return fail_bdecode();
 109                                         ++start;
 110                                         lazy_entry* ent = top->dict_append(start);
 111                                         start += len;
 112                                         stack.push_back(ent);
 113                                         t = *start;
 114                                         ++start;
 115                                         break;
 116                                 }
 117                                 case lazy_entry::list_t:
 118                                 {
 119                                         if (t == 'e')
 120                                         {
 121                                                 top->set_end(start);
 122                                                 stack.pop_back();
 123                                                 continue;
 124                                         }
 125                                         lazy_entry* ent = top->list_append();
 126                                         stack.push_back(ent);
 127                                         break;
 128                                 }
 129                                 default: break;
 130                         }
 131
 132                         top = stack.back();
 133                         switch (t)
 134                         {
 135                                 case 'd':
 136                                         top->construct_dict(start - 1);
 137                                         continue;
 138                                 case 'l':
 139                                         top->construct_list(start - 1);
 140                                         continue;
 141                                 case 'i':
 142                                 {
 143                                         char const* int_start = start;
 144                                         start = find_char(start, end, 'e');
 145                                         top->construct_int(int_start, start - int_start);
 146                                         if (start == end) return fail_bdecode();
 147                                         TORRENT_ASSERT(*start == 'e');
 148                                         ++start;
 149                                         stack.pop_back();
 150                                         continue;
 151                                 }
 152                                 default:
 153                                 {
 154                                         using namespace std;
 155                                         if (!isdigit(t)) return fail_bdecode();
 156
 157                                         boost::int64_t len = t - '0';
 158                                         start = parse_int(start, end, ':', len);
 159                                         if (start == 0 || start + len + 1 > end || *start != ':') return fail_bdecode();
 160                                         ++start;
 161                                         top->construct_string(start, int(len));
 162                                         stack.pop_back();
 163                                         start += len;
 164                                         continue;
 165                                 }
 166                         }
 167                         return 0;
 168                 }
 169                 return 0;
 170         }
 171
 172         size_type lazy_entry::int_value() const
 173         {
 174                 TORRENT_ASSERT(m_type == int_t);
 175                 boost::int64_t val = 0;
 176                 bool negative = false;
 177                 if (*m_data.start == '-') negative = true;
 178                 parse_int(negative?m_data.start+1:m_data.start, m_data.start + m_size, 'e', val);
 179                 if (negative) val = -val;
 180                 return val;
 181         }
 182
 183         lazy_entry* lazy_entry::dict_append(char const* name)
 184         {
 185                 TORRENT_ASSERT(m_type == dict_t);
 186                 TORRENT_ASSERT(m_size <= m_capacity);
 187                 if (m_capacity == 0)
 188                 {
 189                         int capacity = lazy_entry_dict_init;
 190                         m_data.dict = new (std::nothrow) std::pair<char const*, lazy_entry>[capacity];
 191                         if (m_data.dict == 0) return 0;
 192                         m_capacity = capacity;
 193                 }
 194                 else if (m_size == m_capacity)
 195                 {
 196                         int capacity = m_capacity * lazy_entry_grow_factor;
 197                         std::pair<char const*, lazy_entry>* tmp = new (std::nothrow) std::pair<char const*, lazy_entry>[capacity];
 198                         if (tmp == 0) return 0;
 199                         std::memcpy(tmp, m_data.dict, sizeof(std::pair<char const*, lazy_entry>) * m_size);
 200                         for (int i = 0; i < m_size; ++i) m_data.dict[i].second.release();
 201                         delete[] m_data.dict;
 202                         m_data.dict = tmp;
 203                         m_capacity = capacity;
 204                 }
 205
 206                 TORRENT_ASSERT(m_size < m_capacity);
 207                 std::pair<char const*, lazy_entry>& ret = m_data.dict[m_size++];
 208                 ret.first = name;
 209                 return &ret.second;
 210         }
 211
 212         namespace
 213         {
 214                 // the number of decimal digits needed
 215                 // to represent the given value
 216                 int num_digits(int val)
 217                 {
 218                         int ret = 1;
 219                         while (val >= 10)
 220                         {
 221                                 ++ret;
 222                                 val /= 10;
 223                         }
 224                         return ret;
 225                 }
 226         }
 227
 228         void lazy_entry::construct_string(char const* start, int length)
 229         {
 230                 TORRENT_ASSERT(m_type == none_t);
 231                 m_type = string_t;
 232                 m_data.start = start;
 233                 m_size = length;
 234                 m_begin = start - 1 - num_digits(length);
 235                 m_end = start + length;
 236         }
 237
 238         namespace
 239         {
 240                 // str1 is null-terminated
 241                 // str2 is not, str2 is len2 chars
 242                 bool string_equal(char const* str1, char const* str2, int len2)
 243                 {
 244                         while (len2 > 0)
 245                         {
 246                                 if (*str1 != *str2) return false;
 247                                 if (*str1 == 0) return false;
 248                                 ++str1;
 249                                 ++str2;
 250                                 --len2;
 251                         }
 252                         return *str1 == 0;
 253                 }
 254         }
 255
 256         std::string lazy_entry::dict_find_string_value(char const* name) const
 257         {
 258                 lazy_entry const* e = dict_find(name);
 259                 if (e == 0 || e->type() != lazy_entry::string_t) return std::string();
 260                 return e->string_value();
 261         }
 262
 263         lazy_entry const* lazy_entry::dict_find_string(char const* name) const
 264         {
 265                 lazy_entry const* e = dict_find(name);
 266                 if (e == 0 || e->type() != lazy_entry::string_t) return 0;
 267                 return e;
 268         }
 269
 270         size_type lazy_entry::dict_find_int_value(char const* name, size_type default_val) const
 271         {
 272                 lazy_entry const* e = dict_find(name);
 273                 if (e == 0 || e->type() != lazy_entry::int_t) return default_val;
 274                 return e->int_value();
 275         }
 276
 277         lazy_entry const* lazy_entry::dict_find_dict(char const* name) const
 278         {
 279                 lazy_entry const* e = dict_find(name);
 280                 if (e == 0 || e->type() != lazy_entry::dict_t) return 0;
 281                 return e;
 282         }
 283
 284         lazy_entry const* lazy_entry::dict_find_list(char const* name) const
 285         {
 286                 lazy_entry const* e = dict_find(name);
 287                 if (e == 0 || e->type() != lazy_entry::list_t) return 0;
 288                 return e;
 289         }
 290
 291         lazy_entry* lazy_entry::dict_find(char const* name)
 292         {
 293                 TORRENT_ASSERT(m_type == dict_t);
 294                 for (int i = 0; i < m_size; ++i)
 295                 {
 296                         std::pair<char const*, lazy_entry> const& e = m_data.dict[i];
 297                         if (string_equal(name, e.first, e.second.m_begin - e.first))
 298                                 return &m_data.dict[i].second;
 299                 }
 300                 return 0;
 301         }
 302
 303         lazy_entry* lazy_entry::list_append()
 304         {
 305                 TORRENT_ASSERT(m_type == list_t);
 306                 TORRENT_ASSERT(m_size <= m_capacity);
 307                 if (m_capacity == 0)
 308                 {
 309                         int capacity = lazy_entry_list_init;
 310                         m_data.list = new (std::nothrow) lazy_entry[capacity];
 311                         if (m_data.list == 0) return 0;
 312                         m_capacity = capacity;
 313                 }
 314                 else if (m_size == m_capacity)
 315                 {
 316                         int capacity = m_capacity * lazy_entry_grow_factor;
 317                         lazy_entry* tmp = new (std::nothrow) lazy_entry[capacity];
 318                         if (tmp == 0) return 0;
 319                         std::memcpy(tmp, m_data.list, sizeof(lazy_entry) * m_size);
 320                         for (int i = 0; i < m_size; ++i) m_data.list[i].release();
 321                         delete[] m_data.list;
 322                         m_data.list = tmp;
 323                         m_capacity = capacity;
 324                 }
 325
 326                 TORRENT_ASSERT(m_size < m_capacity);
 327                 return m_data.list + (m_size++);
 328         }
 329
 330         std::string lazy_entry::list_string_value_at(int i) const
 331         {
 332                 lazy_entry const* e = list_at(i);
 333                 if (e == 0 || e->type() != lazy_entry::string_t) return std::string();
 334                 return e->string_value();
 335         }
 336
 337         size_type lazy_entry::list_int_value_at(int i, size_type default_val) const
 338         {
 339                 lazy_entry const* e = list_at(i);
 340                 if (e == 0 || e->type() != lazy_entry::int_t) return default_val;
 341                 return e->int_value();
 342         }
 343
 344         void lazy_entry::clear()
 345         {
 346                 switch (m_type)
 347                 {
 348                         case list_t: delete[] m_data.list; break;
 349                         case dict_t: delete[] m_data.dict; break;
 350                         default: break;
 351                 }
 352                 m_data.start = 0;
 353                 m_size = 0;
 354                 m_capacity = 0;
 355                 m_type = none_t;
 356         }
 357
 358         std::pair<char const*, int> lazy_entry::data_section() const
 359         {
 360                 typedef std::pair<char const*, int> return_t;
 361                 return return_t(m_begin, m_end - m_begin);
 362         }
 363
 364         std::ostream& operator<<(std::ostream& os, lazy_entry const& e)
 365         {
 366                 switch (e.type())
 367                 {
 368                         case lazy_entry::none_t: return os << "none";
 369                         case lazy_entry::int_t: return os << std::dec << std::setw(0) << e.int_value();
 370                         case lazy_entry::string_t:
 371                         {
 372                                 bool printable = true;
 373                                 char const* str = e.string_ptr();
 374                                 for (int i = 0; i < e.string_length(); ++i)
 375                                 {
 376                                         using namespace std;
 377                                         if (isprint(str[i])) continue;
 378                                         printable = false;
 379                                         break;
 380                                 }
 381                                 os << "'";
 382                                 if (printable) return os << e.string_value() << "'";
 383                                 for (int i = 0; i < e.string_length(); ++i)
 384                                         os << std::hex << std::setfill('0') << std::setw(2)
 385                                         << int((unsigned char)(str[i]));
 386                                 return os << "'";
 387                         }
 388                         case lazy_entry::list_t:
 389                         {
 390                                 os << "[";
 391                                 bool one_liner = (e.list_size() == 0
 392                                         || e.list_at(0)->type() == lazy_entry::int_t
 393                                         || (e.list_at(0)->type() == lazy_entry::string_t
 394                                                 && (e.list_at(0)->string_length() < 10
 395                                                         || e.list_size() < 2)))
 396                                         && e.list_size() < 5;
 397                                 if (!one_liner) os << "\n";
 398                                 for (int i = 0; i < e.list_size(); ++i)
 399                                 {
 400                                         if (i == 0 && one_liner) os << " ";
 401                                         os << *e.list_at(i);
 402                                         if (i < e.list_size() - 1) os << (one_liner?", ":",\n");
 403                                         else os << (one_liner?" ":"\n");
 404                                 }
 405                                 return os << "]";
 406                         }
 407                         case lazy_entry::dict_t:
 408                         {
 409                                 os << "{";
 410                                 bool one_liner = (e.dict_size() == 0
 411                                         || e.dict_at(0).second->type() == lazy_entry::int_t
 412                                         || (e.dict_at(0).second->type() == lazy_entry::string_t
 413                                                 && e.dict_at(0).second->string_length() < 30)
 414                                         || e.dict_at(0).first.size() < 10)
 415                                         && e.dict_size() < 5;
 416
 417                                 if (!one_liner) os << "\n";
 418                                 for (int i = 0; i < e.dict_size(); ++i)
 419                                 {
 420                                         if (i == 0 && one_liner) os << " ";
 421                                         std::pair<std::string, lazy_entry const*> ent = e.dict_at(i);
 422                                         os << "'" << ent.first << "': " << *ent.second;
 423                                         if (i < e.dict_size() - 1) os << (one_liner?", ":",\n");
 424                                         else os << (one_liner?" ":"\n");
 425                                 }
 426                                 return os << "}";
 427                         }
 428                 }
 429                 return os;
 430         }
 431
 432 };
 433