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         size_type lazy_entry::dict_find_int_value(char const* name, size_type default_val) const
 264         {
 265                 lazy_entry const* e = dict_find(name);
 266                 if (e == 0 || e->type() != lazy_entry::int_t) return default_val;
 267                 return e->int_value();
 268         }
 269
 270         lazy_entry const* lazy_entry::dict_find_dict(char const* name) const
 271         {
 272                 lazy_entry const* e = dict_find(name);
 273                 if (e == 0 || e->type() != lazy_entry::dict_t) return 0;
 274                 return e;
 275         }
 276
 277         lazy_entry const* lazy_entry::dict_find_list(char const* name) const
 278         {
 279                 lazy_entry const* e = dict_find(name);
 280                 if (e == 0 || e->type() != lazy_entry::list_t) return 0;
 281                 return e;
 282         }
 283
 284         lazy_entry* lazy_entry::dict_find(char const* name)
 285         {
 286                 TORRENT_ASSERT(m_type == dict_t);
 287                 for (int i = 0; i < m_size; ++i)
 288                 {
 289                         std::pair<char const*, lazy_entry> const& e = m_data.dict[i];
 290                         if (string_equal(name, e.first, e.second.m_begin - e.first))
 291                                 return &m_data.dict[i].second;
 292                 }
 293                 return 0;
 294         }
 295
 296         lazy_entry* lazy_entry::list_append()
 297         {
 298                 TORRENT_ASSERT(m_type == list_t);
 299                 TORRENT_ASSERT(m_size <= m_capacity);
 300                 if (m_capacity == 0)
 301                 {
 302                         int capacity = lazy_entry_list_init;
 303                         m_data.list = new (std::nothrow) lazy_entry[capacity];
 304                         if (m_data.list == 0) return 0;
 305                         m_capacity = capacity;
 306                 }
 307                 else if (m_size == m_capacity)
 308                 {
 309                         int capacity = m_capacity * lazy_entry_grow_factor;
 310                         lazy_entry* tmp = new (std::nothrow) lazy_entry[capacity];
 311                         if (tmp == 0) return 0;
 312                         std::memcpy(tmp, m_data.list, sizeof(lazy_entry) * m_size);
 313                         for (int i = 0; i < m_size; ++i) m_data.list[i].release();
 314                         delete[] m_data.list;
 315                         m_data.list = tmp;
 316                         m_capacity = capacity;
 317                 }
 318
 319                 TORRENT_ASSERT(m_size < m_capacity);
 320                 return m_data.list + (m_size++);
 321         }
 322
 323         std::string lazy_entry::list_string_value_at(int i) const
 324         {
 325                 lazy_entry const* e = list_at(i);
 326                 if (e == 0 || e->type() != lazy_entry::string_t) return std::string();
 327                 return e->string_value();
 328         }
 329
 330         size_type lazy_entry::list_int_value_at(int i, size_type default_val) const
 331         {
 332                 lazy_entry const* e = list_at(i);
 333                 if (e == 0 || e->type() != lazy_entry::int_t) return default_val;
 334                 return e->int_value();
 335         }
 336
 337         void lazy_entry::clear()
 338         {
 339                 switch (m_type)
 340                 {
 341                         case list_t: delete[] m_data.list; break;
 342                         case dict_t: delete[] m_data.dict; break;
 343                         default: break;
 344                 }
 345                 m_data.start = 0;
 346                 m_size = 0;
 347                 m_capacity = 0;
 348                 m_type = none_t;
 349         }
 350
 351         std::pair<char const*, int> lazy_entry::data_section() const
 352         {
 353                 typedef std::pair<char const*, int> return_t;
 354                 return return_t(m_begin, m_end - m_begin);
 355         }
 356
 357         std::ostream& operator<<(std::ostream& os, lazy_entry const& e)
 358         {
 359                 switch (e.type())
 360                 {
 361                         case lazy_entry::none_t: return os << "none";
 362                         case lazy_entry::int_t: return os << e.int_value();
 363                         case lazy_entry::string_t:
 364                         {
 365                                 bool printable = true;
 366                                 char const* str = e.string_ptr();
 367                                 for (int i = 0; i < e.string_length(); ++i)
 368                                 {
 369                                         using namespace std;
 370                                         if (isprint(str[i])) continue;
 371                                         printable = false;
 372                                         break;
 373                                 }
 374                                 os << "'";
 375                                 if (printable) return os << e.string_value() << "'";
 376                                 for (int i = 0; i < e.string_length(); ++i)
 377                                         os << std::hex << int((unsigned char)(str[i]));
 378                                 return os << "'";
 379                         }
 380                         case lazy_entry::list_t:
 381                         {
 382                                 os << "[";
 383                                 bool one_liner = (e.list_size() == 0
 384                                         || e.list_at(0)->type() == lazy_entry::int_t
 385                                         || (e.list_at(0)->type() == lazy_entry::string_t
 386                                                 && (e.list_at(0)->string_length() < 10
 387                                                         || e.list_size() < 2)))
 388                                         && e.list_size() < 5;
 389                                 if (!one_liner) os << "\n";
 390                                 for (int i = 0; i < e.list_size(); ++i)
 391                                 {
 392                                         if (i == 0 && one_liner) os << " ";
 393                                         os << *e.list_at(i);
 394                                         if (i < e.list_size() - 1) os << (one_liner?", ":",\n");
 395                                         else os << (one_liner?" ":"\n");
 396                                 }
 397                                 return os << "]";
 398                         }
 399                         case lazy_entry::dict_t:
 400                         {
 401                                 os << "{";
 402                                 bool one_liner = (e.dict_size() == 0
 403                                         || e.dict_at(0).second->type() == lazy_entry::int_t
 404                                         || (e.dict_at(0).second->type() == lazy_entry::string_t
 405                                                 && e.dict_at(0).second->string_length() < 30)
 406                                         || e.dict_at(0).first.size() < 10)
 407                                         && e.dict_size() < 5;
 408
 409                                 if (!one_liner) os << "\n";
 410                                 for (int i = 0; i < e.dict_size(); ++i)
 411                                 {
 412                                         if (i == 0 && one_liner) os << " ";
 413                                         std::pair<std::string, lazy_entry const*> ent = e.dict_at(i);
 414                                         os << "'" << ent.first << "': " << *ent.second;
 415                                         if (i < e.dict_size() - 1) os << (one_liner?", ":",\n");
 416                                         else os << (one_liner?" ":"\n");
 417                                 }
 418                                 return os << "}";
 419                         }
 420                 }
 421                 return os;
 422         }
 423
 424 };
 425