The bitfield tracks which pieces of the transfer are already downloaded, and which aren’t. We therefore only need a structure which can track two states per value, which is why we use a bitarray library. In fact, we use only a subset of these functions, and rename a few to make them more expressive.

We also need to be able to translate the bitfield from/to the network where the high bit (right-most in network order) in the first byte corresponds to piece index 0.

Signature

namespace BitTorrent

type Bitfield = Common.Bitarray

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module Bitfield =

  type t = Bitfield

  ///[create n] creates a new Bitfield representing [n] pieces.
  val create : numPieces:int -> t

  ///[length bitfield] returns the number of pieces handled by [bitfield].
  val length : bitfield:t -> int

  ///[put nth flag bitfield] sets the [nth] value of the [bitfield] to [flag].
  val put : n:int -> flag:bool -> bitfield:t -> unit

  ///[set nth bitfield] sets the [nth] value of the [bitfield] to [true].
  val set : n:int -> bitfield:t -> unit

  ///[unset nth bitfield] sets the [nth] value of the [bitfield] to [false].
  val unset : n:int -> bitfield:t -> unit

  val iteri : f:(int -> bool -> unit) -> bitfield:t -> unit

  ///[verifiedPieces bitfield] returns the indexes of the pieces which are set to true.
  val verifiedPieces : bitfield:t -> list<int>

  ///[unverifiedPieces bitfield] returns the indexes of the pieces which are set to false.
  val unverifiedPieces : bitfield:t -> list<int>

  ///[hasPiece nth bitfield] returns true if the [nth] piece is set to true.
  val hasPiece : n:int -> bitfield:t -> bool

  ///[isVirgin bitfield] returns true if no bit is set in the [bitfield].
  val isVirgin : bitfield:t -> bool

  ///[isSeeder bitfield] returns true if all bits are set in the [bitfield].
  val isSeeder : bitfield:t -> bool

  ///[( |Virgin|Leecher|Seeder| ) bitfield] returns Virgin if no piece is set to true,
  ///Seeder if they are all set to true, Leecher otherwise.
  val ( |Virgin|Leecher|Seeder| ) : bitfield:t -> Choice<unit,unit,unit>

  ///[toBytes bitfield] converts [bitfield] to a byte array ready to be sent over the network.
  ///The high bit in the first byte corresponds to piece index 0.
  ///Spare bits at the end are set to zero.
  val toBytes : bitfield:t -> byte[]

  ///[fromBytes bytes numPieces] converts [bytes] to a Bitfield. The high bit in the first byte
  ///corresponds to piece index 0. Spare bits at the end are set to zero.
  ///An exception is raised if [numPieces] is inconsistent with the number of bits encoded
  ///in [bytes].
  val fromBytes : bytes:byte[] -> numPieces:int -> t
  

Implementation

namespace BitTorrent

type Bitfield = Common.Bitarray

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module Bitfield =

  open Common

  type t = Bitfield

  let create n = Bitarray.create n

  let length bitfield = Bitarray.length bitfield

  let put i flag bitfield = Bitarray.put i flag bitfield

  let set i bitfield = Bitarray.set i bitfield

  let unset i bitfield = Bitarray.unset i bitfield

  let iteri f bitfield = Bitarray.iteri f bitfield

  let verifiedPieces bitfield = Bitarray.setBits bitfield

  let unverifiedPieces bitfield = Bitarray.unsetBits bitfield

  let hasPiece piece bitfield = Bitarray.isSet piece bitfield

  let isVirgin bitfield = Bitarray.areAllUnset bitfield

  let isSeeder bitfield = Bitarray.areAllSet bitfield

  let ( |Virgin|Leecher|Seeder| ) bitfield =
    if isVirgin bitfield then Virgin
    elif isSeeder bitfield then Seeder
    else Leecher

  //-----------------------------------------------------------
  // Convert the byte array representation of a bitfield between the
  // network-usable version and a bitarray-usable version.
  //-----------------------------------------------------------  

  //The bitfield message is variable length, where X is the length of the bitfield.
  //The payload is a bitfield representing the pieces that have been successfully downloaded.
  //The high bit (right-most in network order) in the first byte corresponds to piece index 0.
  //Bits that are cleared indicated a missing piece, and set bits indicate a valid and available piece.
  //Spare bits at the end are set to zero

  let isSetBit bits bit =
    bits &&& byte (1 <<< bit) <> 0uy

  let setBit bits bit =
    bits ||| byte (1 <<< (7 - bit))

  let toggleBits (data:byte[]) =
    let nBytes = Array.length data
    let convertedBytes = Array.create nBytes 0uy
    for currentByte in 0 .. nBytes - 1 do
      for currentBit in 0 .. 7 do
        if isSetBit data.[currentByte] currentBit then
          convertedBytes.[currentByte] <- setBit convertedBytes.[currentByte] currentBit
    convertedBytes 

  let toBytes bitfield =
    bitfield |> Bitarray.toBytes |> toggleBits

  let fromBytes data numBits =
    Bitarray.fromBytes (toggleBits data) numBits

Example

let test x =
  printfn "bitfield length : %d" (Bitfield.length x)
  printfn "bitfield has piece 0 : %A" (Bitfield.hasPiece 0 x)
  printfn "bitfield verified pieces: %A" (Bitfield.verifiedPieces x)
  printfn "bitfield unverified pieces: %A" (Bitfield.unverifiedPieces x)
  printfn "bitfield is virgin: %A" (Bitfield.isVirgin x)
  printfn "bitfield is seeder: %A" (Bitfield.isSeeder x)
  printfn "bitfield contais only [false] flags : %A" (Bitarray.areAllUnset x)
  printfn "bitfield contais only [true] flags : %A" (Bitarray.areAllSet x)
  printfn "bitfield to bytes : %A" (Bitfield.toBytes x)
  printfn "bitfield from bytes : %A" (Bitfield.fromBytes (Bitfield.toBytes x) (Bitfield.length x))
  printfn "================="

//no bit is set, thus the client is a virgin
let x = Bitfield.create 10
test x ;;

Bitfield.set 0 x
test x ;;

Bitfield.unset 0 x
test x ;;

//set all bits to true, i.e. when the client is seeding
x |> Bitfield.iteri (fun i e -> Bitfield.set i x)
test x;;