B编码与BT种子文件分析，以及模仿json-cpp写一个B编码解析器

编程入门行业动态更新时间:2024-10-28 16:29:35

B编码与BT种子文件分析，以及模仿json-cpp写一个B编码解析器

1、什么是B编码
2、B编码格式
3、种子文件结构
- 3.1、主文件结构
- 3.2、info结构
4、简单的例子了解一下种子文件和B编码
5、分析JSON-CPP的设计
- 5.1、分析Json::Value::CZString的设计
- 5.2、分析Json::Value的设计
- - 5.2.1、类成员设计
  - 5.2.2、类方法设计
- 5.3、迭代器的设计
- - 5.3.1、Json::ValueIteratorBase
  - 5.3.2、Json::ValueConstIterator
  - 5.3.3、Json::ValueIterator
- 5.4、总结
6、B编码解析器设计
- 6.1、BEncode::Value
- 6.2、BEncode::ValueIteratorBase
- 6.3、BEncode::ValueConstIterator
- 6.4、BEncode::ValueIterator
- 6.5、解析函数
7、总结并附上本文源代码

1、什么是B编码

B编码是种子文件以及tracker服务器返回信息的编码格式，DHT协议和BT协议传输的格式都是经过B编码压缩的

2、B编码格式

B编码有以下4种数据类型：

字符串：编码格式为<十进制ASCII编码的长度>:<字符串>，需要注意的是字符串没有开始结束符。如4:span，表示字符串span。
整数：编码格式为i<十进制ASCII编码的整数>e，以i开头，e结尾，中间的数值可以是负数，如i-3e是有效的。
列表：编码格式为l<编码值>e，以l开头，e结尾，<编码值>可以是任意的B编码的字符串、整数、字典或者其他列表。如l4:info3:path，表示由字符串info、path组成的列表。
字典：编码格式为d<字符串><编码元素>e，以d开头，e结尾。需要注意的是<字符串>必须是B编码的字符串，<编码元素>可以是任意的B编码的字符串、整数、列表或者其他字典。

3、种子文件结构

种子文件里的内容其实就是文本，是经过B编码之后的文本。它主要包含以下字段

3.1、主文件结构

info：必须，一个描述torrent文件的字典，有两种可能形式，一种是没有目录结构的“单一文件”，一种是有目录结构的“多文件”
announce：可选，tracker服务器的地址URL（字符串）
announce-list：可选，tracker服务器列表，这是官方规范的一个扩展，向后兼容，用来存储备用服务器列表
creation date：可选，torrent文件的创建时间，为Unix时间戳
comment：可选，备注信息
created by：可选，说明torrent文件是由哪个程序创建的
encoding：可选，种子文件的默认编码
nodes：可选，这个字段包含一系列ip和相应端口的列表，用于连接DHT初始node

3.2、info结构

所有关于下载的文件的信息都在这个字段里，它包括多个子字段，而且根据下载的是单个文件还是多个文件，子字段会有所不同

单文件结构如下：

name：必须，文件名（字符串）
name.utf-8：可选，内容同上，区别在于使用了UTF-8编码
length：文件长度，单位字节(整数)
piece length：必须，每个块的大小，单位字节(整数)
pieces：必须，文件的特征信息，该字段比较大，实际上是种子内包含所有的文件段的SHA1的校验值的连接，即将所有文件按照piece length的字节大小分成块，每块计算一个SHA1值，然后将这些值连接起来就形成了pieces字段，由于SHA1的校验值为20Byte，所以该字段的大小始终为20的整数倍字节。该字段是种子文件中体积最大的部分，可见如果大文件分块很小，会造成种子文件体积十分庞大
publisher：可选，发布者的名字
publisher.utf-8：可选，发布者的名字的utf-8编码
publisher-url：可选，发布者的网址
publisher-url.utf-8：可选，发布者网址的utf-8编码。

多文件结构如下：

files：必须，是一个列表，存储文件的名字与大小信息，该字段包含以下三个子字段：

  length：必须，文件的大小（字节）
  path：必须，是一个列表，从上到下识别，最末尾的字段是文件名，前面的是文件路径。内容在下载时不允许更改
  path.utf-8：可选，内容同上，区别在于使用了UTF-8编码

name：必须，推荐的文件夹名，此项可于下载时更改（字符串）
name.utf-8：可选，内容同上，区别在于使用了UTF-8编码
piece length：必须，每个块的大小，单位字节(整数)
pieces：必须，文件的特征信息，该字段比较大，实际上是种子内包含所有的文件段的SHA1的校验值的连接，即将所有文件按照piece length的字节大小分成块，每块计算一个SHA1值，然后将这些值连接起来就形成了pieces字段，由于SHA1的校验值为20Byte，所以该字段的大小始终为20的整数倍字节。该字段是种子文件中体积最大的部分，可见如果大文件分块很小，会造成种子文件体积十分庞大
publisher：可选，发布者的名字
publisher.utf-8：可选，发布者的名字的utf-8编码
publisher-url：可选，发布者的网址
publisher-url.utf-8：可选，发布者网址的utf-8编码。

当种子里包含单个文件时，name字段描述的是资源的名称了，此时name字段在下载时不允许更改

4、简单的例子了解一下种子文件和B编码

工欲善其事，必先利其器，要想更好地了解B编码，就需要拿一个种子文件来分析其中的内容。我们可以自己去随便一个网站下载一个种子文件下来，下载的话使用用迅雷之类的软件就行了。然后使用BEncode Editor这个软件打开种子，可以看到类似下面的内容，和我们之前描述的差不多

5、分析JSON-CPP的设计

解析器是参考JSON-CPP来写的，大家可以自行去网上下载JSON-CPP的源码，或者点击这里下载bifang框架源码，里面src/json/里面就是JSON-CPP的源码了

5.1、分析Json::Value::CZString的设计

Json::Value里面有一个CZString类，是为了用于统一管理数组类型和对象类型的，如下所示

class CZString {
  public:
    enum DuplicationPolicy { noDuplication = 0, duplicate, duplicateOnCopy };
    CZString(ArrayIndex index);
    CZString(char const* str, unsigned length, DuplicationPolicy allocate);
    CZString(CZString const& other);
    CZString(CZString&& other) noexcept;
    ~CZString();
    CZString& operator=(const CZString& other);
    CZString& operator=(CZString&& other) noexcept;

    bool operator<(CZString const& other) const;
    bool operator==(CZString const& other) const;
    ArrayIndex index() const;
    // const char* c_str() const; ///< \deprecated
    char const* data() const;
    unsigned length() const;
    bool isStaticString() const;

  private:
    void swap(CZString& other);

    struct StringStorage {
      unsigned policy_ : 2;
      unsigned length_ : 30; // 1GB max
    };

    char const* cstr_; // actually, a prefixed string, unless policy is noDup
    union {
      ArrayIndex index_;
      StringStorage storage_;
    };
  };

从类成员中可以看到，该类可以存储整型和字符串类型的数据，我们设计时可以简单粗暴地使用std::string来存储字符串类型就行。从后面的代码中我们可以看到这个类是作为std::map的键值来使用的，这样数组类型和对象类型都可以用map来表示了，要实现这点，关键的一点就是要实现比较运算符的重载，如下所示，可以看到，当CZString表示的是数组类型时，使用index_去作比较运算，表示的是对象时使用的是cstr_去作比较运算，完美解决问题。

bool Value::CZString::operator<(const CZString& other) const {
  if (!cstr_)
    return index_ < other.index_;
  // return strcmp(cstr_, other.cstr_) < 0;
  // Assume both are strings.
  unsigned this_len = this->storage_.length_;
  unsigned other_len = other.storage_.length_;
  unsigned min_len = std::min<unsigned>(this_len, other_len);
  JSON_ASSERT(this->cstr_ && other.cstr_);
  int comp = memcmp(this->cstr_, other.cstr_, min_len);
  if (comp < 0)
    return true;
  if (comp > 0)
    return false;
  return (this_len < other_len);
}

bool Value::CZString::operator==(const CZString& other) const {
  if (!cstr_)
    return index_ == other.index_;
  // return strcmp(cstr_, other.cstr_) == 0;
  // Assume both are strings.
  unsigned this_len = this->storage_.length_;
  unsigned other_len = other.storage_.length_;
  if (this_len != other_len)
    return false;
  JSON_ASSERT(this->cstr_ && other.cstr_);
  int comp = memcmp(this->cstr_, other.cstr_, this_len);
  return comp == 0;
}

5.2、分析Json::Value的设计

5.2.1、类成员设计

可以看到Json::Value是使用了一个联合体来作为类成员使用的，由于每个Json::Value只可能代表一种类型（总不能又代表数组类型又代表对象类型吧。。。），所以使用联合体可以最大程度地节省空间，比较巧妙的做法，我们平时也可以在特定的场合使用这种技巧

using LargestInt = int;
using LargestUInt = unsigned int;
typedef std::map<CZString, Value> ObjectValues;
union ValueHolder {
  LargestInt int_;
  LargestUInt uint_;
  double real_;
  bool bool_;
  char* string_; // if allocated_, ptr to { unsigned, char[] }.
  ObjectValues* map_;
} value_;

5.2.2、类方法设计

这里看几个典型的方法设计就行，大部分比较简单大家可以自己去看看

append方法的实现如下，可以看到由于append是给数组类型的数据使用的，所以每次插入数据之后不需要让map重新排序啥的，可以直接在指定位置构造元素即可，所以使用了std::map的emplace方法（size方法的返回值是ArrayIndex，如果不理解ArrayIndex为什么可以替代CZString的得自行去补一下C++的基础。。。）

Value& Value::append(const Value& value) { return append(Value(value)); }

Value& Value::append(Value&& value) {
  JSON_ASSERT_MESSAGE(type() == nullValue || type() == arrayValue,
                      "in Json::Value::append: requires arrayValue");
  if (type() == nullValue) {
    *this = Value(arrayValue);
  }
  return this->value_.map_->emplace(size(), std::move(value)).first->second;
}

find方法的实现如下，没什么特别的，就是使用了std::map的find而已，重载的operator[](const char* key)之类的方法中也是使用了这个find来实现的，难度不大，大家自己看一遍就明白了

Value const* Value::find(char const* begin, char const* end) const {
  JSON_ASSERT_MESSAGE(type() == nullValue || type() == objectValue,
                      "in Json::Value::find(begin, end): requires "
                      "objectValue or nullValue");
  if (type() == nullValue)
    return nullptr;
  CZString actualKey(begin, static_cast<unsigned>(end - begin),
                     CZString::noDuplication);
  ObjectValues::const_iterator it = value_.map_->find(actualKey);
  if (it == value_.map_->end())
    return nullptr;
  return &(*it).second;
}

const Value& Value::operator[](const char* key) const {
  Value const* found = find(key, key + strlen(key));
  if (!found)
    return nullSingleton();
  return *found;
}

5.3、迭代器的设计

5.3.1、Json::ValueIteratorBase

迭代器基类设计如下，可以看到类成员的定义为 Value::ObjectValues::iterator current_，这只是简单托管了Json::Value中**map_**的迭代器而已，没有什么特殊的地方。

class JSON_API ValueIteratorBase {
public:
  using iterator_category = std::bidirectional_iterator_tag;
  using size_t = unsigned int;
  using difference_type = int;
  using SelfType = ValueIteratorBase;

  bool operator==(const SelfType& other) const { return isEqual(other); }

  bool operator!=(const SelfType& other) const { return !isEqual(other); }

  difference_type operator-(const SelfType& other) const {
    return other.computeDistance(*this);
  }

  /// Return either the index or the member name of the referenced value as a
  /// Value.
  Value key() const;

  /// Return the index of the referenced Value, or -1 if it is not an
  /// arrayValue.
  UInt index() const;

  /// Return the member name of the referenced Value, or "" if it is not an
  /// objectValue.
  /// \note Avoid `c_str()` on result, as embedded zeroes are possible.
  String name() const;

  /// Return the member name of the referenced Value. "" if it is not an
  /// objectValue.
  /// \deprecated This cannot be used for UTF-8 strings, since there can be
  /// embedded nulls.
  JSONCPP_DEPRECATED("Use `key = name();` instead.")
  char const* memberName() const;
  /// Return the member name of the referenced Value, or NULL if it is not an
  /// objectValue.
  /// \note Better version than memberName(). Allows embedded nulls.
  char const* memberName(char const** end) const;

protected:
  /*! Internal utility functions to assist with implementing
   *   other iterator functions. The const and non-const versions
   *   of the "deref" protected methods expose the protected
   *   current_ member variable in a way that can often be
   *   optimized away by the compiler.
   */
  const Value& deref() const;
  Value& deref();

  void increment();

  void decrement();

  difference_type computeDistance(const SelfType& other) const;

  bool isEqual(const SelfType& other) const;

  void copy(const SelfType& other);

private:
  Value::ObjectValues::iterator current_;
  // Indicates that iterator is for a null value.
  bool isNull_{true};

public:
  // For some reason, BORLAND needs these at the end, rather
  // than earlier. No idea why.
  ValueIteratorBase();
  explicit ValueIteratorBase(const Value::ObjectValues::iterator& current);
};

设计上是没有什么特别的，因为是利用std::map的迭代器进行封装的，下面简单看一下几个方法的实现就行，我们封装B编码的也采用差不多的方法

Value& ValueIteratorBase::deref() { return current_->second; }
const Value& ValueIteratorBase::deref() const { return current_->second; }
void ValueIteratorBase::increment() { ++current_; }
void ValueIteratorBase::decrement() { --current_; }

5.3.2、Json::ValueConstIterator

继承于迭代器基类，非常简单，大家自行看一下就行

class JSON_API ValueIterator : public ValueIteratorBase {
  friend class Value;

public:
  using value_type = Value;
  using size_t = unsigned int;
  using difference_type = int;
  using reference = Value&;
  using pointer = Value*;
  using SelfType = ValueIterator;

  ValueIterator();
  explicit ValueIterator(const ValueConstIterator& other);
  ValueIterator(const ValueIterator& other);

private:
  /*! \internal Use by Value to create an iterator.
   */
  explicit ValueIterator(const Value::ObjectValues::iterator& current);

public:
  SelfType& operator=(const SelfType& other);

  SelfType operator++(int) {
    SelfType temp(*this);
    ++*this;
    return temp;
  }

  SelfType operator--(int) {
    SelfType temp(*this);
    --*this;
    return temp;
  }

  SelfType& operator--() {
    decrement();
    return *this;
  }

  SelfType& operator++() {
    increment();
    return *this;
  }

  /*! The return value of non-const iterators can be
   *  changed, so the these functions are not const
   *  because the returned references/pointers can be used
   *  to change state of the base class.
   */
  reference operator*() { return deref(); }
  pointer operator->() { return &deref(); }
};

5.3.3、Json::ValueIterator

继承于迭代器基类，非常简单，大家自行看一下就行

class JSON_API ValueIterator : public ValueIteratorBase {
  friend class Value;

public:
  using value_type = Value;
  using size_t = unsigned int;
  using difference_type = int;
  using reference = Value&;
  using pointer = Value*;
  using SelfType = ValueIterator;

  ValueIterator();
  explicit ValueIterator(const ValueConstIterator& other);
  ValueIterator(const ValueIterator& other);

private:
  /*! \internal Use by Value to create an iterator.
   */
  explicit ValueIterator(const Value::ObjectValues::iterator& current);

public:
  SelfType& operator=(const SelfType& other);

  SelfType operator++(int) {
    SelfType temp(*this);
    ++*this;
    return temp;
  }

  SelfType operator--(int) {
    SelfType temp(*this);
    --*this;
    return temp;
  }

  SelfType& operator--() {
    decrement();
    return *this;
  }

  SelfType& operator++() {
    increment();
    return *this;
  }

  /*! The return value of non-const iterators can be
   *  changed, so the these functions are not const
   *  because the returned references/pointers can be used
   *  to change state of the base class.
   */
  reference operator*() { return deref(); }
  pointer operator->() { return &deref(); }
};

5.4、总结

JSON-CPP的实现还是非常巧妙的，里面的很多设计和stl很相似，类提供的包括迭代器的设计也是这样的，这也是JSON-CPP使用起来很简单的一个原因.我们可以很轻易地借鉴这些优秀的代码来设计出一个B编码的解析器

6、B编码解析器设计

6.1、BEncode::Value

和JSON-CPP的实现差不多，舍弃了一些没用的功能，简化了代码，如下所示

class Value
{
friend class ValueIteratorBase;

private:
    class CZString
    {
    public:
        CZString(size_t index);
        CZString(const std::string& str);
        CZString(const CZString& other);
        ~CZString();

        CZString& operator=(const CZString& other);
        
        bool operator<(const CZString& other) const;
        bool operator==(const CZString& other) const;

        std::string* data() const { return m_str;   }
        size_t index()      const { return m_index; }

    private:
        std::string* m_str;
        size_t m_index;
    };

public:
    typedef std::map<CZString, Value> DictionaryValues;
    using const_iterator = ValueConstIterator;
    using iterator = ValueIterator;

    enum Type
    {
        BCODE_INTEGER = 0,
        BCODE_STRING,
        BCODE_LIST,
        BCODE_DICTIONARY,
    };

    Value(Type type = BCODE_INTEGER);
    Value(int64_t value);
    Value(const std::string& value);
    Value(const Value& other);
    ~Value();

    Type getType()      const { return m_type;                     }
    bool isInteger()    const { return m_type == BCODE_INTEGER;    }
    bool isString()     const { return m_type == BCODE_STRING;     }
    bool isList()       const { return m_type == BCODE_LIST;       }
    bool isDictionary() const { return m_type == BCODE_DICTIONARY; }
    size_t size() const;
    bool empty() const;
    std::string typeToString() const;

    void setType(Type type);
    void clear();
    void resize(size_t newSize);

    /**
     * brief: You may need to say 'value[0u]' to get your compiler to distinguish
     *        this from the operator[] which takes a string
     */
    Value& operator[](size_t index);
    Value& operator[](const std::string& key);

    void swap(Value& other);
    Value& operator=(const Value& other);

    bool operator<(const Value& other) const;
    bool operator>(const Value& other) const;
    bool operator<=(const Value& other) const;
    bool operator>=(const Value& other) const;
    bool operator==(const Value& other) const;
    bool operator!=(const Value& other) const;

    int64_t asInt() const;
    std::string asString() const;

    Value& append(const Value& value);
    bool insert(size_t index, const Value& newValue);

    Value get(size_t index, const Value& defaultValue) const;
    Value get(const std::string& key, const Value& defaultValue) const;

    const_iterator find(const std::string& key) const;
    iterator find(const std::string& key);

    bool isMember(const std::string& key) const;
    void removeMember(const std::string& key);
    bool removeMember(const std::string& key, Value* removed);
    bool removeIndex(size_t index, Value* removed);
    std::vector<std::string> getMemberNames() const;

    const_iterator begin() const;
    const_iterator end() const;

    iterator begin();
    iterator end();

private:
    void free();

private:
    Type m_type;
    union ValueHolder
    {
        int64_t m_int;
        std::string* m_string;
        DictionaryValues* m_map;
    } m_value;
};

6.2、BEncode::ValueIteratorBase

class ValueIteratorBase
{
public:
    using SelfType = ValueIteratorBase;

    ValueIteratorBase();
    explicit ValueIteratorBase(const Value::DictionaryValues::iterator& current);

public:
    bool operator==(const SelfType& other) const { return isEqual(other);  }
    bool operator!=(const SelfType& other) const { return !isEqual(other); }
    int64_t operator-(const SelfType& other) const { return other.computeDistance(*this); }

    Value key() const;

    size_t index() const;

    std::string name() const;

protected:
    Value& deref() { return m_current->second; }
    const Value& deref() const { return m_current->second; }

    void increment() { m_current++; }
    void decrement() { m_current--; }

    int64_t computeDistance(const SelfType& other) const;

    bool isEqual(const SelfType& other) const;

    void copy(const SelfType& other);

private:
    Value::DictionaryValues::iterator m_current;
    bool m_isNull = true;
};

6.3、BEncode::ValueConstIterator

class ValueConstIterator : public ValueIteratorBase
{
friend class Value;

public:
    using value_type = const Value;
    using reference = const Value&;
    using pointer = const Value*;
    using SelfType = ValueConstIterator;

    ValueConstIterator();
    ValueConstIterator(const ValueIterator & other);

private:
    explicit ValueConstIterator(const Value::DictionaryValues::iterator& current);

public:
    SelfType& operator=(const ValueIteratorBase& other)
    {
        copy(other);
        return *this;
    }

    SelfType operator++(int)
    {
        SelfType temp(*this);
        ++*this;
        return temp;
    }

    SelfType operator--(int)
    {
        SelfType temp(*this);
        --*this;
        return temp;
    }

    SelfType& operator--()
    {
        decrement();
        return *this;
    }

    SelfType& operator++()
    {
        increment();
        return *this;
    }

    reference operator*() const { return deref(); }

    pointer operator->() const { return &deref(); }
};

6.4、BEncode::ValueIterator

class ValueIterator : public ValueIteratorBase
{
friend class Value;

public:
    using value_type = Value;
    using reference = Value&;
    using pointer = Value*;
    using SelfType = ValueIterator;

    ValueIterator();
    ValueIterator(const SelfType& other);
    explicit ValueIterator(const ValueConstIterator& other);

private:
    explicit ValueIterator(const Value::DictionaryValues::iterator& current);

public:
    SelfType& operator=(const SelfType& other)
    {
        copy(other);
        return *this;
    }

    SelfType operator++(int)
    {
        SelfType temp(*this);
        ++*this;
        return temp;
    }

    SelfType operator--(int)
    {
        SelfType temp(*this);
        --*this;
        return temp;
    }

    SelfType& operator--()
    {
        decrement();
        return *this;
    }

    SelfType& operator++()
    {
        increment();
        return *this;
    }

    reference operator*() { return deref(); }

    pointer operator->() { return &deref(); }
};