Elixir #28 – Bencode

Kontynuujemy przygodę z ElTorrento – klientem BitTorrent napisanym w elixir. Dziś skoncentruje się na implementacji Bencode – kodowanie użyte w BitTorrent do przechowywania i przesyłania struktur danych. Nie jest to skomplikowane, ale jest podstawą  jeżeli chcemy napisać klienta. Chociażby po to by przeczytać plik torrent. A więc nie ważne jakie kroki dalej będziemy mieć i co będziemy pisać, Bencode będzie nam potrzebny by ruszyć z tematem.

Moja implementacja Bencode nie będzie jedyną w elixir, ale stwierdziłem, że akurat tę część będę chciał napisać zamiast wykorzystać już istniejącą implementację. Jeżeli jednak absolutnie nie interesuję Cię ten fragment :) to dostępne są następujące implementacje:

• Bento
• bencode
• Bencodex
• bencoder
• exbencode
• elixir_bencode

Dużo jest tego, ale to dobrze, będzie łatwiej znaleźć rozwiązanie na problem jeżeli na ów natrafimy pisząc kod! :)

Co to jest Bencode?

Bencode to nic innego jak kodowanie znaków. Można by powiedzieć, że kodowanie w user readble format, który wpiera jedynie 4 typy danych: liczby, stringy, listy i mapy. To co jest wspólne pomiędzy typami kodowania to, to, że każde kodowanie zaczyna się od określonej litery i kończy na określonej literze, zaś wszystko co pomiędzy jest daną albo już z deserializowaną, albo daną zawierającą dane, które trzeba z deserializować.

Wyrózniamy następujące typy (wszystkie dane są ograniczone przez ASCII):

• Liczby, liczba znajduje się pomiędzy i i e: iNUMe. Liczby ujemne zawierają minus, 0 lub brak liczby to liczba 0. Dla przykładu i-10e, i10e.
• Ciągi, mają postać LICZBA_ZNAKÓW:ciąg – na przykład 0: lub 1:a lub 2:ab.
• Listy, znajdują się między znakami l i e i mają postać lCIĄG_DANYCHe. Przy czym CIĄG_DANYCH może zawierać kolejne dane serializowane takie jak liczba czy nawet ciąg znaków. Problem polega na tym że nie ma tutaj  żadnego rozdzielenie wartości, dla przykładu l3:abci3ee, to lista składająca się z abc i liczby 3.
• Słowniki, znajdują się miedzy znakami d i e i mają postać  dSŁOWNIKe, gdzie SŁOWNIK to zbiór klucz i zaraz po niej występująca wartość przy czym klucze są posortowane leksykograficznie i też są kodowane. Czyli para klucz1 i wartośc 5 mają postać 6:klucz1i5e. Jakbyśmy mieli do tego dodać klucz2 i zamknąć to w słowniku to: d6:klucz1i5e6:klucz24:teste

Ogólnie nie jest to ciężkie kodowanie i elixir się idealnie nadaje do implementacji dzięki pattern maching.

Implementacja

Można było do tematu podejść na dwa sposoby. Mógłbym stworzyć protokół i poszczególne implementacje. Mógłbym też to zamknąć w jednym module. Długo się zastanawiałem jaką opcję wybrać i w końcu wybrałem opcję drugą – jeden moduł. Protokół traktuję jako coś co można rozszerzać o nowe typy. Specyfikacja jednak nie zmieniła się od wielu lat więc raczej nie liczę na to, że to się zmieni w przyszłości.

Oczywiście protokół dałby czystszą implementację – w sensie, mały moduł robiący tylko jedną rzecz ale to by była sztuka dla sztuki i nic by pozytywnego nie wnosiła. Może też w unit testach było by przejrzyściej ale… jakoś naprawdę mi ten protokół tutaj nie pasował.

Zaczynamy wszystko o stworzenia pod-projektu w naszym projekcie głównym:

el_torrento/apps$ mix new bencode

Następnie w pliku el_torrento/apps/bencode/lib/bencode.ex dodajemy dwie metody które będą nam potrzebne:

defmodule Bencode do
  @moduledoc """

  Bencode (pronounced like B encode) is the encoding used by the peer-to-peer file sharing system BitTorrent for storing and transmitting loosely structured data.

  It supports four different types of values:
   * `byte strings`,
   * `integers`,
   * `lists`, and
   * `dictionnaries`  (associative arrays)

  """

  @doc """

  Decode bencoded into Elixir data structures

  ## Examples

      iex> Bencode.decode("i1e")
      1
      iex> Bencode.decode("4:test")
      "test""
      iex> Bencode.decode("li1e4:teste")
      [1, "test"]
      iex> Bencode.decode("d4:testi1ee")
      %{"test" => 1}
  """
  def decode (input) do
    {:error, "not implemented"}
  end

  @doc """

  Encode Elixir data structure into bencode

  ## Examples

      iex> Bencode.encode(1)
      "i1e"
      iex> Bencode.encode("test"")
      "4:test"
      iex> Bencode.encode([1, "test"])
      "li1e4:teste"
      iex> Bencode.encode(%{"test" => 1})
      "d4:testi1ee"

  """
  def encode (input) do
    {:error, "not implemented"}
  end
end

Na razie nic skomplikowanego, dwie metody, dwie zwracające not implemented. Dwie zawierające dziwne @doc. Wytłumaczenie @doc pozostawię sobie na kiedy indziej (pewnie przyszły tydzień lub dopiero za dwa tygodnie). To co możemy zrobić i to co jest proste i szybkie do zrealizowanie to encode. Spróbujmy więc to zaimplementować.

def encode (input) do
  do_encode(input)
end

defp do_encode(input) when is_integer(input), do: "i#{input}e"
defp do_encode(input) when is_binary(input), do: "#{byte_size(input)}:#{input}"

defp do_encode([]]), do: "le"
defp do_encode(input) when is_list(input) do
  input 
  |> Enum.reduce("", fn(x, acc) -> acc <> encode(x) end)
  |> (&("l#{&1}e")).()
end

defp do_encode(input) when is_map(input) and map_size(input) == 0, do: "de"
defp do_encode(input) when is_map(input) do
  input
  |> Map.keys
  |> Enum.reduce("", fn(x, acc) -> acc <> encode(x) <> encode(Map.get(input, x)) end)
  |> (&("d#{&1}e")).()
end

# do nothing if we can't handle it
defp do_encode(_input) do

end

Jak widać nie jest to rocket sience, trzeba jednak znać API. Moim zdaniem i tak tego optymalnie nie zrobiłem. Na pewno coś da się tutaj poprawić, ktoś coś? :)

Podsumowanie

Cały kod oczywiście znajduje się na github. W przyszłym tygodniu zajmiemy się decode jak i testowaniem tego kodu gdyż warto zapoznać i zaprzyjaźnić się ze wsparciem do testów jednostkowych w elixir. Cały kolejny kod będzie już zawierał testy normalnie, więc też by się przydało byśmy potrafili to czytać ze zrozumieniem :) Choć jak tak teraz myślę to może się okazać, że będzie zbyt dużo kodu i z testami się za tydzień nie wyrobię. Zobaczymy. Niezależnie od tego wciąż obowiązuje u mnie zasada – 1h tygodniowo. Więc i tak super, że tyle się udało co dzisiaj :)

To czego nie poruszyłem w ogóle to komponenty BitTorrent i tym pewnie zajmę się też jakoś osobnym postem. Komponenty  – czyli wszystko to co, co powinno zostać zaimplementowane :)