Class: QuartzTorrent::Bitfield

Inherits:
Object
  • Object
show all
Defined in:
lib/quartz_torrent/bitfield.rb

Overview

A bitfield that allows querying and setting individual bits, as well as serializing and unserializing.

Direct Known Subclasses

EmptyBitfield

Constant Summary collapse

@@bitsSetInByteLookup =

Lookup table. The value at index i is the number of bits on in byte with value i.

[0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,
2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,
2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,
4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,
3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,
4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,
3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,
4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,
3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,
5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8]

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(length) ⇒ Bitfield

Create a bitfield of length ‘length’ in bits.



43
44
45
46
47
48
49
50
 
# File 'lib/quartz_torrent/bitfield.rb', line 43

def initialize(length)
  @length = length
  if @length == 0
    @data = Array.new(0)
  else
    @data = Array.new((length-1)/8+1, 0)
  end
end

Instance Attribute Details

#length ⇒ Object

Length of the Bitfield in bits.



53
54
55
 
# File 'lib/quartz_torrent/bitfield.rb', line 53

def length
  @length
end

Instance Method Details

#allClear? ⇒ Boolean

Are all bits in the Bitfield clear?

Returns:

  • (Boolean) 


114
115
116
117
118
119
120
121
122
123
124
125
126
 
# File 'lib/quartz_torrent/bitfield.rb', line 114

def allClear?
  # Check all but last byte quickly
  (@data.length-1).times do |i|
    return false if @data[i] != 0
  end
  # Check last byte slowly
  toCheck = @length % 8
  toCheck = 8 if toCheck == 0
  ((@length-toCheck)..(@length-1)).each do |i|
    return false if set?(i)
  end
  true
end

#allSet? ⇒ Boolean

Are all bits in the Bitfield set?

Returns:

  • (Boolean) 


99
100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/quartz_torrent/bitfield.rb', line 99

def allSet?
  # Check all but last byte quickly
  (@data.length-1).times do |i|
    return false if @data[i] != 0xff
  end
  # Check last byte slowly
  toCheck = @length % 8
  toCheck = 8 if toCheck == 0
  ((@length-toCheck)..(@length-1)).each do |i|
    return false if ! set?(i)
  end
  true
end

#byteLength ⇒ Object

Length of the Bitfield in bytes.



68
69
70
 
# File 'lib/quartz_torrent/bitfield.rb', line 68

def byteLength
  @data.length
end

#clear(bit) ⇒ Object

Clear the bit at index ‘bit’ to 0.



83
84
85
86
87
88
89
90
 
# File 'lib/quartz_torrent/bitfield.rb', line 83

def clear(bit)
  quotient = bit >> 3
  remainder = bit & 0x7
  mask = ~(0x80 >> remainder)
  
  raise "Bit #{bit} out of range of bitfield with length #{length}" if quotient >= @data.length
  @data[quotient] &= mask
end

#clearAll ⇒ Object

Clear all bits in the field to 0.



134
135
136
 
# File 'lib/quartz_torrent/bitfield.rb', line 134

def clearAll
  @data.fill(0x00)
end

#compliment ⇒ Object

Calculate the compliment of this bitfield, and return the result as a new bitfield.



184
185
186
187
188
 
# File 'lib/quartz_torrent/bitfield.rb', line 184

def compliment
  bitfield = Bitfield.new(length)
  bitfield.copyFrom(self)
  bitfield.compliment!
end

#compliment! ⇒ Object

Update this bitfield to be the compliment of itself.



191
192
193
194
 
# File 'lib/quartz_torrent/bitfield.rb', line 191

def compliment!
  @data.collect!{ |e| ~e }
  self
end

#copyFrom(bitfield) ⇒ Object

Set the contents of this bitfield to be the same as the passed bitfield. An exception is thrown if the passed bitfield is smaller than this.



175
176
177
178
179
180
 
# File 'lib/quartz_torrent/bitfield.rb', line 175

def copyFrom(bitfield)
  raise "Source bitfield is too small (#{bitfield.length} < #{length})" if bitfield.length < length
  (@data.length).times do |i|
    @data[i] = bitfield.data[i]
  end
end

#countSet ⇒ Object

Count the number of bits that are set.



218
219
220
 
# File 'lib/quartz_torrent/bitfield.rb', line 218

def countSet
  @data.reduce(0){ |memo, v| memo + @@bitsSetInByteLookup[v] }
end

#intersection(bitfield) ⇒ Object

Calculate the intersection of this bitfield and the passed bitfield, and return the result as a new bitfield.



153
154
155
156
157
158
159
160
 
# File 'lib/quartz_torrent/bitfield.rb', line 153

def intersection(bitfield)
  raise "That's not a bitfield" if ! bitfield.is_a?(Bitfield)
  raise "bitfield lengths must be equal" if ! bitfield.length == length

  newbitfield = Bitfield.new(length)
  newbitfield.copyFrom(self)
  newbitfield.intersection!(bitfield)
end

#intersection!(bitfield) ⇒ Object

Update this bitfield to be the intersection of this bitfield and the passed bitfield.



163
164
165
166
167
168
169
170
171
 
# File 'lib/quartz_torrent/bitfield.rb', line 163

def intersection!(bitfield)
  raise "That's not a bitfield" if ! bitfield.is_a?(Bitfield)
  raise "bitfield lengths must be equal" if ! bitfield.length == length
    
  (@data.length).times do |i|
    @data[i] = @data[i] & bitfield.data[i]
  end
  self
end

#serialize ⇒ Object

Serialize this bitfield as a string.



197
198
199
 
# File 'lib/quartz_torrent/bitfield.rb', line 197

def serialize
  @data.pack "C*"
end

#set(bit) ⇒ Object

Set the bit at index ‘bit’ to 1.



73
74
75
76
77
78
79
80
 
# File 'lib/quartz_torrent/bitfield.rb', line 73

def set(bit)
  quotient = bit >> 3
  remainder = bit & 0x7
  mask = 0x80 >> remainder

  raise "Bit #{bit} out of range of bitfield with length #{length}" if quotient >= @data.length
  @data[quotient] |= mask
end

#set?(bit) ⇒ Boolean

Returns true if the bit is set, false otherwise.

Returns:

  • (Boolean) 


93
94
95
96
 
# File 'lib/quartz_torrent/bitfield.rb', line 93

def set?(bit)
  #raise "Bit #{bit} out of range of bitfield with length #{length}" if quotient >= @data.length
  (@data[bit >> 3] << (bit & 0x7)) & 0x80 > 0
end

#setAll ⇒ Object

Set all bits in the field to 1.



129
130
131
 
# File 'lib/quartz_torrent/bitfield.rb', line 129

def setAll
  @data.fill(0xff)
end

#to_s(groupsOf = 8) ⇒ Object

Return a display string representing the bitfield.



207
208
209
210
211
212
213
214
215
 
# File 'lib/quartz_torrent/bitfield.rb', line 207

def to_s(groupsOf = 8)
  groupsOf = 8 if groupsOf == 0
  s = ""
  length.times do |i|
    s << (set?(i) ? "1" : "0")
    s << " " if i % groupsOf == 0
  end
  s
end

#union(bitfield) ⇒ Object

Calculate the union of this bitfield and the passed bitfield, and return the result as a new bitfield.



140
141
142
143
144
145
146
147
148
149
 
# File 'lib/quartz_torrent/bitfield.rb', line 140

def union(bitfield)
  raise "That's not a bitfield" if ! bitfield.is_a?(Bitfield)
  raise "bitfield lengths must be equal" if ! bitfield.length == length

  result = Bitfield.new(length)
  (@data.length).times do |i|
    result.data[i] = @data[i] | bitfield.data[i]
  end
  result
end

#unserialize(s) ⇒ Object

Unserialize this bitfield from a string.



202
203
204
 
# File 'lib/quartz_torrent/bitfield.rb', line 202

def unserialize(s)
  @data = s.unpack "C*"
end