include/libtorrent/bencode.hpp

   1 /*
   2
   3 Copyright (c) 2003, 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
  34 #ifndef TORRENT_BENCODE_HPP_INCLUDED
  35 #define TORRENT_BENCODE_HPP_INCLUDED
  36
  37
  38
  39 /*
  40  * This file declares the following functions:
  41  *
  42  *----------------------------------
  43  * template<class OutIt>
  44  * void libtorrent::bencode(OutIt out, const libtorrent::entry& e);
  45  *
  46  * Encodes a message entry with bencoding into the output
  47  * iterator given. The bencoding is described in the BitTorrent
  48  * protocol description document OutIt must be an OutputIterator
  49  * of type char. This may throw libtorrent::invalid_encoding if
  50  * the entry contains invalid nodes (undefined_t for example).
  51  *
  52  *----------------------------------
  53  * template<class InIt>
  54  * libtorrent::entry libtorrent::bdecode(InIt start, InIt end);
  55  *
  56  * Decodes the buffer given by the start and end iterators
  57  * and returns the decoded entry. InIt must be an InputIterator
  58  * of type char. May throw libtorrent::invalid_encoding if
  59  * the string is not correctly bencoded.
  60  *
  61  */
  62
  63
  64
  65
  66 #include <cstdlib>
  67
  68 #ifdef _MSC_VER
  69 #pragma warning(push, 1)
  70 #endif
  71
  72 #include <boost/lexical_cast.hpp>
  73 #include <boost/static_assert.hpp>
  74
  75 #ifdef _MSC_VER
  76 #pragma warning(pop)
  77 #endif
  78
  79 #include "libtorrent/entry.hpp"
  80 #include "libtorrent/config.hpp"
  81
  82 #include "libtorrent/assert.hpp"
  83
  84 #if defined(_MSC_VER)
  85 namespace std
  86 {
  87         using ::isdigit;
  88         using ::atoi;
  89 };
  90
  91 #define for if (false) {}  else for
  92 #endif
  93
  94
  95 namespace libtorrent
  96 {
  97
  98         struct TORRENT_EXPORT invalid_encoding: std::exception
  99         {
 100                 virtual const char* what() const throw() { return "invalid bencoding"; }
 101         };
 102
 103         namespace detail
 104         {
 105                 template <class OutIt>
 106                 int write_string(OutIt& out, const std::string& val)
 107                 {
 108                         int ret = val.length();
 109                         std::string::const_iterator end = val.begin() + ret;
 110                         for (std::string::const_iterator i = val.begin()
 111                                 , end(val.begin() + ret); i != end; ++i)
 112                                 *out++ = *i;
 113                         return ret;
 114                 }
 115
 116                 TORRENT_EXPORT char const* integer_to_str(char* buf, int size, entry::integer_type val);
 117
 118                 template <class OutIt>
 119                 int write_integer(OutIt& out, entry::integer_type val)
 120                 {
 121                         // the stack allocated buffer for keeping the
 122                         // decimal representation of the number can
 123                         // not hold number bigger than this:
 124                         BOOST_STATIC_ASSERT(sizeof(entry::integer_type) <= 8);
 125                         char buf[21];
 126                         int ret = 0;
 127                         for (char const* str = integer_to_str(buf, 21, val);
 128                                 *str != 0; ++str)
 129                         {
 130                                 *out = *str;
 131                                 ++out;
 132                                 ++ret;
 133                         }
 134                         return ret;
 135                 }
 136
 137                 template <class OutIt>
 138                 void write_char(OutIt& out, char c)
 139                 {
 140                         *out = c;
 141                         ++out;
 142                 }
 143
 144                 template <class InIt>
 145                 std::string read_until(InIt& in, InIt end, char end_token, bool& err)
 146                 {
 147                         std::string ret;
 148                         if (in == end)
 149                         {
 150                                 err = true;
 151                                 return ret;
 152                         }
 153                         while (*in != end_token)
 154                         {
 155                                 ret += *in;
 156                                 ++in;
 157                                 if (in == end)
 158                                 {
 159                                         err = true;
 160                                         return ret;
 161                                 }
 162                         }
 163                         return ret;
 164                 }
 165
 166                 template<class InIt>
 167                 void read_string(InIt& in, InIt end, int len, std::string& str, bool& err)
 168                 {
 169                         TORRENT_ASSERT(len >= 0);
 170                         for (int i = 0; i < len; ++i)
 171                         {
 172                                 if (in == end)
 173                                 {
 174                                         err = true;
 175                                         return;
 176                                 }
 177                                 str += *in;
 178                                 ++in;
 179                         }
 180                 }
 181
 182                 // returns the number of bytes written
 183                 template<class OutIt>
 184                 int bencode_recursive(OutIt& out, const entry& e)
 185                 {
 186                         int ret = 0;
 187                         switch(e.type())
 188                         {
 189                         case entry::int_t:
 190                                 write_char(out, 'i');
 191                                 ret += write_integer(out, e.integer());
 192                                 write_char(out, 'e');
 193                                 ret += 2;
 194                                 break;
 195                         case entry::string_t:
 196                                 ret += write_integer(out, e.string().length());
 197                                 write_char(out, ':');
 198                                 ret += write_string(out, e.string());
 199                                 ret += 1;
 200                                 break;
 201                         case entry::list_t:
 202                                 write_char(out, 'l');
 203                                 for (entry::list_type::const_iterator i = e.list().begin(); i != e.list().end(); ++i)
 204                                         ret += bencode_recursive(out, *i);
 205                                 write_char(out, 'e');
 206                                 ret += 2;
 207                                 break;
 208                         case entry::dictionary_t:
 209                                 write_char(out, 'd');
 210                                 for (entry::dictionary_type::const_iterator i = e.dict().begin();
 211                                         i != e.dict().end(); ++i)
 212                                 {
 213                                         // write key
 214                                         ret += write_integer(out, i->first.length());
 215                                         write_char(out, ':');
 216                                         ret += write_string(out, i->first);
 217                                         // write value
 218                                         ret += bencode_recursive(out, i->second);
 219                                         ret += 1;
 220                                 }
 221                                 write_char(out, 'e');
 222                                 ret += 2;
 223                                 break;
 224                         default:
 225                                 // do nothing
 226                                 break;
 227                         }
 228                         return ret;
 229                 }
 230
 231                 template<class InIt>
 232                 void bdecode_recursive(InIt& in, InIt end, entry& ret, bool& err, int depth)
 233                 {
 234                         if (depth >= 100)
 235                         {
 236                                 err = true;
 237                                 return;
 238                         }
 239
 240                         if (in == end)
 241                         {
 242                                 err = true;
 243 #ifndef NDEBUG
 244                                 ret.m_type_queried = false;
 245 #endif
 246                                 return;
 247                         }
 248                         switch (*in)
 249                         {
 250
 251                         // ----------------------------------------------
 252                         // integer
 253                         case 'i':
 254                                 {
 255                                 ++in; // 'i'
 256                                 std::string val = read_until(in, end, 'e', err);
 257                                 if (err) return;
 258                                 TORRENT_ASSERT(*in == 'e');
 259                                 ++in; // 'e'
 260                                 ret = entry(entry::int_t);
 261                                 ret.integer() = boost::lexical_cast<entry::integer_type>(val);
 262 #ifndef NDEBUG
 263                                 ret.m_type_queried = false;
 264 #endif
 265                                 } break;
 266
 267                         // ----------------------------------------------
 268                         // list
 269                         case 'l':
 270                                 {
 271                                 ret = entry(entry::list_t);
 272                                 ++in; // 'l'
 273                                 while (*in != 'e')
 274                                 {
 275                                         ret.list().push_back(entry());
 276                                         entry& e = ret.list().back();
 277                                         bdecode_recursive(in, end, e, err, depth + 1);
 278                                         if (err)
 279                                         {
 280 #ifndef NDEBUG
 281                                                 ret.m_type_queried = false;
 282 #endif
 283                                                 return;
 284                                         }
 285                                         if (in == end)
 286                                         {
 287                                                 err = true;
 288 #ifndef NDEBUG
 289                                                 ret.m_type_queried = false;
 290 #endif
 291                                                 return;
 292                                         }
 293                                 }
 294 #ifndef NDEBUG
 295                                 ret.m_type_queried = false;
 296 #endif
 297                                 TORRENT_ASSERT(*in == 'e');
 298                                 ++in; // 'e'
 299                                 } break;
 300
 301                         // ----------------------------------------------
 302                         // dictionary
 303                         case 'd':
 304                                 {
 305                                 ret = entry(entry::dictionary_t);
 306                                 ++in; // 'd'
 307                                 while (*in != 'e')
 308                                 {
 309                                         entry key;
 310                                         bdecode_recursive(in, end, key, err, depth + 1);
 311                                         if (err || key.type() != entry::string_t)
 312                                         {
 313 #ifndef NDEBUG
 314                                                 ret.m_type_queried = false;
 315 #endif
 316                                                 return;
 317                                         }
 318                                         entry& e = ret[key.string()];
 319                                         bdecode_recursive(in, end, e, err, depth + 1);
 320                                         if (err)
 321                                         {
 322 #ifndef NDEBUG
 323                                                 ret.m_type_queried = false;
 324 #endif
 325                                                 return;
 326                                         }
 327                                         if (in == end)
 328                                         {
 329                                                 err = true;
 330 #ifndef NDEBUG
 331                                                 ret.m_type_queried = false;
 332 #endif
 333                                                 return;
 334                                         }
 335                                 }
 336 #ifndef NDEBUG
 337                                 ret.m_type_queried = false;
 338 #endif
 339                                 TORRENT_ASSERT(*in == 'e');
 340                                 ++in; // 'e'
 341                                 } break;
 342
 343                         // ----------------------------------------------
 344                         // string
 345                         default:
 346                                 if (isdigit((unsigned char)*in))
 347                                 {
 348                                         std::string len_s = read_until(in, end, ':', err);
 349                                         if (err)
 350                                         {
 351 #ifndef NDEBUG
 352                                                 ret.m_type_queried = false;
 353 #endif
 354                                                 return;
 355                                         }
 356                                         TORRENT_ASSERT(*in == ':');
 357                                         ++in; // ':'
 358                                         int len = std::atoi(len_s.c_str());
 359                                         ret = entry(entry::string_t);
 360                                         read_string(in, end, len, ret.string(), err);
 361                                         if (err)
 362                                         {
 363 #ifndef NDEBUG
 364                                                 ret.m_type_queried = false;
 365 #endif
 366                                                 return;
 367                                         }
 368                                 }
 369                                 else
 370                                 {
 371                                         err = true;
 372 #ifndef NDEBUG
 373                                         ret.m_type_queried = false;
 374 #endif
 375                                         return;
 376                                 }
 377 #ifndef NDEBUG
 378                                 ret.m_type_queried = false;
 379 #endif
 380                         }
 381                 }
 382         }
 383
 384         template<class OutIt>
 385         int bencode(OutIt out, const entry& e)
 386         {
 387                 return detail::bencode_recursive(out, e);
 388         }
 389
 390         template<class InIt>
 391         entry bdecode(InIt start, InIt end)
 392         {
 393                 entry e;
 394                 bool err = false;
 395                 detail::bdecode_recursive(start, end, e, err, 0);
 396                 TORRENT_ASSERT(e.m_type_queried == false);
 397                 if (err) return entry();
 398                 return e;
 399         }
 400
 401         template<class InIt>
 402         entry bdecode(InIt start, InIt end, int& len)
 403         {
 404                 entry e;
 405                 bool err = false;
 406                 InIt s = start;
 407                 detail::bdecode_recursive(start, end, e, err, 0);
 408                 len = std::distance(s, start);
 409                 TORRENT_ASSERT(len >= 0);
 410                 if (err) return entry();
 411                 return e;
 412         }
 413 }
 414
 415 #endif // TORRENT_BENCODE_HPP_INCLUDED