bitutil

Documentation

Overview

Package bitutil implements fast bitwise operations and compression/decompressions.

Bitwise Operations

Following operations are supported

• AND, OR, XOR operations
• Provides both safe version and fast version of above operations `Safe` means it can be performed on all architectures `Fast` means it only can be performed on architecture which supports unaligned read/write

Compression and Decompression

Following operations are supported

• CompressBytes
• DecompressBytes

How compression works

The compression algorithm implemented by CompressBytes and DecompressBytes is optimized for sparse input data which contains a lot of zero bytes. Decompression requires knowledge of the decompressed data length.

Compression works as follows:

  if data only contains zeroes,
	  CompressBytes(data) == nil
  otherwise if len(data) <= 1,
	  CompressBytes(data) == data
  otherwise:
	  CompressBytes(data) == append(CompressBytes(nonZeroBitset(data)), nonZeroBytes(data)...)
	  where
		nonZeroBitset(data) is a bit vector with len(data) bits (MSB first):
			nonZeroBitset(data)[i/8] && (1 << (7-i%8)) != 0  if data[i] != 0
			len(nonZeroBitset(data)) == (len(data)+7)/8
		nonZeroBytes(data) contains the non-zero bytes of data in the same order

Index

• func ANDBytes(dst, a, b []byte) int
• func CompressBytes(data []byte) []byte
• func DecompressBytes(data []byte, target int) ([]byte, error)
• func ORBytes(dst, a, b []byte) int
• func TestBytes(p []byte) bool
• func XORBytes(dst, a, b []byte) int

Functions

func ANDBytes

func ANDBytes(dst, a, b []byte) int

ANDBytes ands the bytes in a and b. The destination is assumed to have enough space. Returns the number of bytes and'd.

func CompressBytes

func CompressBytes(data []byte) []byte

CompressBytes compresses the input byte slice according to the sparse bitset representation algorithm. If the result is bigger than the original input, no compression is done.

func DecompressBytes

func DecompressBytes(data []byte, target int) ([]byte, error)

DecompressBytes decompresses data with a known target size. If the input data matches the size of the target, it means no compression was done in the first place.

func ORBytes

func ORBytes(dst, a, b []byte) int

ORBytes ors the bytes in a and b. The destination is assumed to have enough space. Returns the number of bytes or'd.

func TestBytes

func TestBytes(p []byte) bool

TestBytes tests whether any bit is set in the input byte slice.

func XORBytes

func XORBytes(dst, a, b []byte) int

XORBytes xors the bytes in a and b. The destination is assumed to have enough space. Returns the number of bytes xor'd.