Functions for fiddling with bits. More...

#include "binary.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

Functions
static int	nlz32 (uint32_t x)
	Number of leading zeroes in 32-bit unsigned integer.
uint32_t	rev32 (uint32_t x)
	Reverse bits in a 32-bit integer.
uint64_t	rev64 (uint64_t x)
	Reverse bits in a 64-bit integer.
int	nlz64 (uint64_t x)
	Number of leading zeroes in 64-bit unsigned integer.
tipId_t	low_bits_on (unsigned n)
int	nlz (tipId_t x)
	Number of leading zeroes in tipId_t variable.
void	printBits (size_t size, void const const ptr, FILE fp)
	Print the bits in an object of size "size", pointed to by "ptr".
int	getBits (tipId_t x, int maxbits, int bit[maxbits])
	Examine the bits in x.
void	printWhichBits (size_t const size, void const *const ptr)
	Print the (0-based) indices of the bits that are "on".
int	num1bits (tipId_t x)
	Count the number of 1 bits in x.
tipId_t	next_power_of_2 (tipId_t x)
	Round up to the next largest power of 2.
uint32_t	uint32Hash (uint32_t key)
	Hash function for a 32-bit integer.
uint32_t	uint64Hash (uint64_t key)
	Hash function for a 64-bit integer.
int	no_shared_bits (int n, const tipId_t *tid)
	Return 1 if the values in array share no bits; 0 otherwise.

Detailed Description

Functions for fiddling with bits.

Copyright: Copyright (c) 2016, Alan R. Rogers roger.nosp@m.s@an.nosp@m.thro..nosp@m.utah.nosp@m..edu. This file is released under the Internet Systems Consortium License, which can be found in file "LICENSE".

Function Documentation

◆ getBits()

int getBits	(	tipId_t	x,
		int	maxbits,
		int	bit[maxbits] )

Examine the bits in x.

If bit i equals 1, then add i to array bit. Return the number of nonzero bits. maxbits is the allocated length of array bit. It is an error if the number of nonzero bits exceeds maxbits.

Referenced by patLbl().

◆ nlz32()

int nlz32 ( uint32_t x )

static

Number of leading zeroes in 32-bit unsigned integer.

From p 99 of Hacker's Delight, 2nd edition.

Referenced by nlz().

◆ nlz64()

int nlz64 ( uint64_t x )

Number of leading zeroes in 64-bit unsigned integer.

64-bit version of algorithm on p 99 of Hacker's Delight, 2nd edition.

Referenced by nlz().

◆ no_shared_bits()

int no_shared_bits	(	int	n,
		const tipId_t *	tid )

Return 1 if the values in array share no bits; 0 otherwise.

Returns 1 if n==0.

Referenced by IdSet_join(), and Segment_sanityCheck().

◆ num1bits()

int num1bits ( tipId_t x )

Count the number of 1 bits in x.

From p 85 of Hacker's Delight, 2nd Edn, by Henry S. Warren, Jr. This algorithm is fast when the number of 1 bits is small, and it makes no assumption about the number of bits in x.

Returns: the number of bits.

Referenced by BranchTab_collapse(), BranchTab_rmPops(), compare_tipId(), comparePtrs(), LblNdx_collapse(), and RAFReader_multiNext().

◆ printBits()

void printBits	(	size_t	size,
		void const *const	ptr,
		FILE *	fp )

Print the bits in an object of size "size", pointed to by "ptr".

Assumes little endian

◆ printWhichBits()

void printWhichBits	(	size_t const	size,
		void const *const	ptr )

Print the (0-based) indices of the bits that are "on".

Parameters

[in]	ptr	points to the object whose bits will be examined
[in]	size	the size of the object in bytes

◆ rev32()

uint32_t rev32 ( uint32_t x )

Reverse bits in a 32-bit integer.

p 129 of Hacker's Delight, 2nd edn.

◆ rev64()

uint64_t rev64 ( uint64_t x )

Reverse bits in a 64-bit integer.

This just extends the pattern in rev32.

◆ uint32Hash()

uint32_t uint32Hash ( uint32_t key )

Hash function for a 32-bit integer.

From Thomas Wang's 1997 article: https://gist.github.com/badboy/6267743 This generates integer overflows, presumably by design.