fb55 / bitfield

A bitfield implementation using buffers, compliant with the BitTorrent spec.

bitfield

A simple bitfield, compliant with the BitTorrent spec.

npm install bitfield

Example

import Bitfield from "bitfield";

const field = new Bitfield(256); // Create a bitfield with 256 bits.

field.set(128); // Set the 128th bit.
field.set(128, true); // Same as above.

field.get(128); // `true`
field.get(200); // `false` (all values are initialised to `false`)
field.get(1e3); // `false` (out-of-bounds is also false)

field.set(128, false); // Set the 128th bit to 0 again.

field.buffer; // The buffer used by the bitfield.

Class: BitField

Constructors

• constructor

Properties

• buffer

Methods

• forEach
• get
• set

Constructors

constructor

+ new BitField(data?: number | Uint8Array, opts?: BitFieldOptions): BitField

Parameters:

Name	Type	Default value	Description
data	number | Uint8Array	0	Either a number representing the maximum number of supported bytes, or a Uint8Array.
opts?	{ grow: number }	{ grow: 0 }	grow: If you set an index that is out-of-bounds, the bitfield will automatically grow so that the bitfield is big enough to contain the given index, up to the given size (in bit). If you want the Bitfield to grow indefinitely, pass Infinity.

Returns: BitField

Properties

buffer

• buffer: Uint8Array

The internal storage of the bitfield.

Methods

forEach

▸ forEach(fn: (bit: boolean, index: number) => void, start?: number, end?: number): void

Loop through the bits in the bitfield.

Parameters:

Name	Type	Default value	Description
fn	(bit: boolean, index: number) => void	-	Function to be called with the bit value and index.
start	number	0	Index of the first bit to look at.
end	number	this.buffer.length * 8	Index of the first bit that should no longer be considered.

Returns: void

---

get

▸ get(i: number): boolean

Get a particular bit.

Parameters:

Name	Type	Description
i	number	Bit index to retrieve.

Returns: boolean

A boolean indicating whether the ith bit is set.

---

set

▸ set(i: number, value?: boolean): void

Set a particular bit.

Will grow the underlying array if the bit is out of bounds and the grow option is set.

Parameters:

Name	Type	Default value	Description
i	number	-	Bit index to set.
value	boolean	true	Value to set the bit to. Defaults to true.

Returns: void

---

setAll

▸ setAll(array: ArrayLike<boolean>, offset?: number): void

Set the bits in the bitfield to the values in the given array.

Parameters:

Name	Type	Default value	Description
array	ArrayLike<boolean>	-	Array of booleans to set the bits to.
offset	number	0	Index of the first bit to set.

Returns: void

License

MIT

bitfield's Issues

Idea: forEach loop

WebTorrent loops over bitfields a bunch of time to check what is done and what not, So I figure this piece could be improved with a smarter forEach loop

  get(i) {
    const j = i >> 3
    return (j < this.buffer.length) &&
      !!(this.buffer[j] & (128 >> (i % 8)))
  }

Solution:

  forEach(fn, start = 0, end = this.buffer.length) {
    for (
      let i = start, j = i >> 3, x = i % 8, y = 128 >> x, buffer = this.buffer, byte = buffer[j]; 
      i < end; 
      i++
    ) {
      fn(!!(byte & (y >> x)), i)

      y === 1
        ? (y = y << 7, x = 0, byte = buffer[++j])
        : (y = y >> 1, x++)
    }
  }

forEach loop: 0.944091796875ms
for loop: 1.72314453125ms

fiddle: http://jsfiddle.net/nbr5u3jk/3/

add length property

This could be handy because not always is the length the same as the buffer divised by 8

Review

bitfield/index.js

Lines 35 to 62 in 0ba8d2d

	BitField.prototype.set = function (i, b) {
	var j = i >> 3
	if (b || arguments.length === 1) {
	if (this.buffer.length < j + 1) {
	this._grow(Math.max(j + 1, Math.min(2 * this.buffer.length, this.grow)))
	}
	// Set
	this.buffer[j] |= 128 >> (i % 8)
	} else if (j < this.buffer.length) {
	// Clear
	this.buffer[j] &= ~(128 >> (i % 8))
	}
	}
	BitField.prototype._grow = function (length) {
	if (this.buffer.length < length && length <= this.grow) {
	var newBuffer = new Container(length) // eslint-disable-line node/no-deprecated-api
	if (newBuffer.fill) newBuffer.fill(0)
	if (this.buffer.copy) {
	this.buffer.copy(newBuffer, 0)
	} else {
	for (var i = 0; i < this.buffer.length; i++) {
	newBuffer[i] = this.buffer[i]
	}
	}
	this.buffer = newBuffer
	}
	}

@ line 50 this.buffer.length < length should not be necessary since, line 38 already dose this check

I'm curious also when you grow the buffer, why don't you use set?
e.g. like so:

BitField.prototype._grow = function (length) {
  if (length <= this.grow) {
    var newBuffer = new Container(length) // eslint-disable-line node/no-deprecated-api
    if (newBuffer.fill) newBuffer.fill(0)
    newBuffer.set(newBuffer)
    this.buffer = newBuffer
  }
}

Another thing: is Buffer really necessary? Can we not only use Uint8Array? A Buffer adds other overhead functionality that seems unnecessary. new Buffer(n) is also deprecated and i don't think we need fill(0) either if we just use Uint8Array...

bitfield/index.js

Lines 1 to 3 in 0ba8d2d

	var Container = typeof Buffer !== 'undefined'
	? Buffer // in node, use buffers
	: Uint8Array // in browsers, use typed arrays

BitField is shared between frontend or backend so can't we not just stick to using Uint8Array so we can expect the same thing in both environments.
Not having to worry about when buffer constructor is removed completely from Node and replaced with just an object

I also think _grow can be factored out of the class to just be a helper function that returns a value or simply be put inlined since it is only used at one place

if (this.buffer.length < j + 1) {
  // before:
  // this._grow(Math.max(j + 1, Math.min(2 * this.buffer.length, this.grow)))
  
  var buffer = new Uint8Array(Math.max(j + 1, Math.min(2 * this.buffer.length, this.grow)))
  buffer.set(this.buffer)
  this.buffer = buffer
}

es6 version

function getByteSize (num) {
  let out = num >> 3
  if (num % 8 !== 0) out++
  return out
}

class BitField {
  constructor (data = 0, {grow} = {}) {
    this.grow = (grow && isFinite(grow) && getByteSize(grow)) || 0
    this.buffer = typeof data === 'number' ? new Uint8Array(getByteSize(data)) : data
  }

  get (i) {
    const j = i >> 3
    return (j < this.buffer.length) &&
      !!(this.buffer[j] & (128 >> (i % 8)))
  }

  set (i, b = 1) {
    const j = i >> 3
    if (b) {
      if (this.buffer.length < j + 1) {
        const length = Math.max(j + 1, Math.min(2 * this.buffer.length, this.grow))
        if (length <= this.grow) {
          const newBuffer = new Uint8Array(length)
          newBuffer.set(this.buffer)
          this.buffer = newBuffer
        }
      }
      // Set
      this.buffer[j] |= 128 >> (i % 8)
    } else if (j < this.buffer.length) {
      // Clear
      this.buffer[j] &= ~(128 >> (i % 8))
    }
  }
}

if (typeof module !== 'undefined') module.exports = BitField

Built version on npm missing method

Version on npm seems to be missing the 'setAll' method, even though the version is '4.1.0', which should have that version. Downloaded and built from this repo, method makes it through the build, using that locally.

How to init a Bitfield starting from a binary?

I’d like to use this library to read a Transmission pieces bitfield, they provide a base64 encoded binary (pieces) and its pieces size (pieceSize), how would I go to use this library to read it?

Bitfield is not a constructor

I'm having issues getting this package to work. I've installed with "node install bitfield" and then created the sample program, directly from the readme:

import Bitfield from "bitfield";

const field = new Bitfield(256); // Create a bitfield with 256 bits.

field.set(128); // Set the 128th bit.
field.set(128, true); // Same as above.

field.get(128); // `true`
field.get(200); // `false` (all values are initialised to `false`)
field.get(1e3); // `false` (out-of-bounds is also false)

field.set(128, false); // Set the 128th bit to 0 again.

field.buffer; // The buffer used by the bitfield.

I created a package.json with {"type":"module"} in the working directory and executed, but I get this:

file:///home/myname/eclipse-workspace/myproject/buildTest.js:3
const field = new Bitfield(256); // Create a bitfield with 256 bits.
              ^

TypeError: Bitfield is not a constructor
    at file:///home/myname/eclipse-workspace/myproject/buildTest.js:3:15
    at ModuleJob.run (internal/modules/esm/module_job.js:152:23)
    at async Loader.import (internal/modules/esm/loader.js:166:24)
    at async Object.loadESM (internal/process/esm_loader.js:68:5)

I'm no node expert so it's entirely possible (probable?) that I'm doing something very obvious re: environment or what-have-you. Could someone give me an assist?

DOS vulnerability when passed large index

There should be some protection against spamming the RAM eg. by sending have messages with large indexes. I'm not sure whether this module is the right place to handle this, maybe just adding a note to the readme will suffice.

exporting bitfield state as 32 bits integers

I started using the module and it works fine but I have some issue while trying to use it with another language language (lua)

Programmers of the lua code asked me to export the bitfield (we need 128 values) as 4 integers and I have trouble doing this.

Seems like read from the buffer with readUInt32LE give unexpected results.

So I started investigating on this and notice there is a that trick : 128 >> (i % 8)

so creating a buffer of 128 bool and sending the index 0 to true give this :

var f = new bitfield(128)
f.set(0)
f.buffer
<Buffer 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00>

if you only set(1)

<Buffer 40 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00>

It makes sense if you read the code but I dont get the point of this trick and it s not easy to understand which bits are set if you looks at the buffer dump

I tried to find a way to export the data is the more easily undestable way but without success

for exemple lua programmers expect the output if I set the first bool to 1 only to be :

u32exports = [1,0,0,0]

Use tape and testling, for browser tests

Take a look at magnet-uri for an example of what this would look like.