Integer math

Integer math macros and helpers. More...

Macros
#define	MIN(a, b)   (((a) < (b)) ? (a) : (b))
	Get the smaller of two values.
#define	MAX(a, b)   (((a) > (b)) ? (a) : (b))
	Get the larger of two values.
#define	ABS(a)   (((a) > 0) ? (a) : -1 * (a))
	Get the absolute value.
#define	CLIP(n, min, max)   ((n) < (min) ? (min) : ((n) > (max) ? (max) : (n)))
	Clamp a value to a range.
#define	ROUND(num, denom)   (((num) + ((denom) / 2)) / (denom))
	Divide, rounding half up, for non-negative operands.
#define	WITHIN(n, min, max)   ((n) >= (min) && (n) <= (max))
	Check whether a value is within a closed range.
#define	RANGE_WITHIN(n_min, n_max, min, max)   ((n_min) >= (min) && (n_max) <= (max))
	Check whether a range is within another closed range.
#define	DIVIDE_CEIL(num, denom)   (((num) + ((denom) - 1)) / (denom))
	Divide, rounding up for positive results.
#define	ROUND_TO_MOD_CEIL(val, mod)
	Round a value away from zero to a multiple of a modulus.
#define	ROUND_TO_MOD_CEIL_U(val, mod)   ((((val) + ABS(ABS(mod) - 1)) / ABS(mod)) * ABS(mod))
	Round an unsigned value up to a multiple of a modulus.
#define	IS_SIGNED(var)
	Determine whether a variable is signed or not.

Functions
int32_t	sign_extend (uint32_t a, int bits)
	Sign-extend the low bits of a value.
int32_t	serial_distance32 (uint32_t start, uint32_t end)
	Compute the distance between two 32-bit serial numbers, handling wrap-around.
int32_t	serial_distance (uint32_t start, uint32_t end, int bits)
	Compute the distance between two serial numbers, handling wrap-around.
int	ceil_log_two (uint32_t n)
	Compute the base 2 logarithm, rounded up.
int32_t	integer_sqrt (int64_t x)
	Compute the integer square root with Newton's method.
static bool	pbl_u32_add_overflow (uint32_t a, uint32_t b, uint32_t *result)
	Add two 32-bit unsigned integers, detecting overflow.
static bool	pbl_u32_mul_overflow (uint32_t a, uint32_t b, uint32_t *result)
	Multiply two 32-bit unsigned integers, detecting overflow.
static bool	pbl_size_add_overflow (size_t a, size_t b, size_t *result)
	Add two sizes, detecting overflow.
static bool	pbl_size_mul_overflow (size_t a, size_t b, size_t *result)
	Multiply two sizes, detecting overflow.
static int	positive_modulo (int i, int n)
	Compute a modulo that is never negative.
static int	distance_to_mod_boundary (int32_t i, uint16_t n)
	Compute the distance from a value to the nearest multiple of a modulus.
uint32_t	next_exponential_backoff (uint32_t *attempt, uint32_t initial_value, uint32_t max_value)
	Compute the next interval of a bounded binary exponential backoff.
uint32_t	gcd (uint32_t a, uint32_t b)
	Compute the greatest common divisor of two numbers.

Detailed Description

Integer math macros and helpers.

The macros evaluate their arguments more than once; do not pass expressions with side effects.

int32_t clamped = CLIP(value, -100, 100);
uint32_t pages = DIVIDE_CEIL(len, PAGE_SIZE);
if (WITHIN(c, '0', '9')) {
  ...
}

Macro Definition Documentation

ABS

#define ABS

(

a

)

(((a) > 0) ? (a) : -1 * (a))

Get the absolute value.

Parameters

a

Value.

CLIP

#define CLIP	(		n,
			min,
			max
	)		((n) < (min) ? (min) : ((n) > (max) ? (max) : (n)))

Clamp a value to a range.

Parameters

n	Value.
min	Lower bound.
max	Upper bound.

DIVIDE_CEIL

#define DIVIDE_CEIL	(		num,
			denom
	)		(((num) + ((denom) - 1)) / (denom))

Divide, rounding up for positive results.

Negative results round towards zero: DIVIDE_CEIL(3, 4) is 1 and DIVIDE_CEIL(-3, 4) is 0.

Parameters

num	Numerator.
denom	Denominator, positive.

IS_SIGNED

#define IS_SIGNED

(

var

)

Value:

  (PBL_CHOOSE_EXPR(                                                                          \
      PBL_TYPES_COMPATIBLE(__typeof__(var), unsigned char), false,                           \
      PBL_CHOOSE_EXPR(                                                                       \
          PBL_TYPES_COMPATIBLE(__typeof__(var), unsigned short), false,                      \
          PBL_CHOOSE_EXPR(                                                                   \
              PBL_TYPES_COMPATIBLE(__typeof__(var), unsigned int), false,                    \
              PBL_CHOOSE_EXPR(                                                               \
                  PBL_TYPES_COMPATIBLE(__typeof__(var), unsigned long), false,               \
                  PBL_CHOOSE_EXPR(PBL_TYPES_COMPATIBLE(__typeof__(var), unsigned long long), \
                                  false, true))))))

Determine whether a variable is signed or not.

Parameters

var	The variable to evaluate.

Returns

true if the variable is signed.

MAX

#define MAX	(		a,
			b
	)		(((a) > (b)) ? (a) : (b))

Get the larger of two values.

Parameters

a	First value.
b	Second value.

MIN

#define MIN	(		a,
			b
	)		(((a) < (b)) ? (a) : (b))

Get the smaller of two values.

Parameters

a	First value.
b	Second value.

RANGE_WITHIN

#define RANGE_WITHIN	(		n_min,
			n_max,
			min,
			max
	)		((n_min) >= (min) && (n_max) <= (max))

Check whether a range is within another closed range.

Parameters

n_min	Lower bound of the inner range.
n_max	Upper bound of the inner range.
min	Lower bound of the outer range, included.
max	Upper bound of the outer range, included.

ROUND

#define ROUND	(		num,
			denom
	)		(((num) + ((denom) / 2)) / (denom))

Divide, rounding half up, for non-negative operands.

Parameters

num	Numerator.
denom	Denominator.

ROUND_TO_MOD_CEIL

#define ROUND_TO_MOD_CEIL	(		val,
			mod
	)

Value:

  (((val) >= 0) ? ((((val) + ABS(ABS(mod) - 1)) / ABS(mod)) * ABS(mod)) \
                : -((((-val) + ABS(ABS(mod) - 1)) / ABS(mod)) * ABS(mod)))

Round a value away from zero to a multiple of a modulus.

ROUND_TO_MOD_CEIL(152, 32) is 160 and ROUND_TO_MOD_CEIL(-32, 90) is -90.

Parameters

val	Value.
mod	Modulus; its sign is ignored.

ROUND_TO_MOD_CEIL_U

#define ROUND_TO_MOD_CEIL_U	(		val,
			mod
	)		((((val) + ABS(ABS(mod) - 1)) / ABS(mod)) * ABS(mod))

Round an unsigned value up to a multiple of a modulus.

ROUND_TO_MOD_CEIL_U(152, 32) is 160.

Parameters

val	Value.
mod	Modulus; its sign is ignored.

WITHIN

#define WITHIN	(		n,
			min,
			max
	)		((n) >= (min) && (n) <= (max))

Check whether a value is within a closed range.

Parameters

n	Value.
min	Lower bound, included.
max	Upper bound, included.

Function Documentation

ceil_log_two()

int ceil_log_two

(

uint32_t

n

)

Compute the base 2 logarithm, rounded up.

Parameters

n	Value, greater than 0.

Returns

ceil(log2(n)).

distance_to_mod_boundary()

static int distance_to_mod_boundary ( int32_t  i, uint16_t  n  )

inlinestatic

Compute the distance from a value to the nearest multiple of a modulus.

For angles, the smallest difference between two angles is distance_to_mod_boundary(a - b, 360).

Parameters

i	Value.
n	Modulus, positive.

Returns

Distance, 0 to n / 2.

References ABS, and positive_modulo().

gcd()

uint32_t gcd	(	uint32_t	a,
		uint32_t	b
	)

Compute the greatest common divisor of two numbers.

Parameters

a	First number.
b	Second number.

Returns

Greatest common divisor, 0 if either number is 0.

integer_sqrt()

int32_t integer_sqrt

(

int64_t

x

)

Compute the integer square root with Newton's method.

Parameters

x

Value.

Returns

floor(sqrt(x)), 0 for negative values.

next_exponential_backoff()

uint32_t next_exponential_backoff	(	uint32_t *	attempt,
		uint32_t	initial_value,
		uint32_t	max_value
	)

Compute the next interval of a bounded binary exponential backoff.

Parameters

[in,out]	attempt	Retries performed so far, incremented by the call.
	initial_value	First interval; later ones are this multiplied by a power of 2.
	max_value	Maximum interval returned.

Returns

Next interval, initial_value * 2^attempt capped to max_value.

pbl_size_add_overflow()

static bool pbl_size_add_overflow ( size_t  a, size_t  b, size_t *  result  )

inlinestatic

Add two sizes, detecting overflow.

Parameters

	a	First operand.
	b	Second operand.
[out]	result	Sum, wrapped around on overflow.

Returns

true if the sum overflowed.

References PBL_ADD_OVERFLOW.

pbl_size_mul_overflow()

static bool pbl_size_mul_overflow ( size_t  a, size_t  b, size_t *  result  )

inlinestatic

Multiply two sizes, detecting overflow.

Parameters

	a	First operand.
	b	Second operand.
[out]	result	Product, wrapped around on overflow.

Returns

true if the product overflowed.

References PBL_MUL_OVERFLOW.

pbl_u32_add_overflow()

static bool pbl_u32_add_overflow ( uint32_t  a, uint32_t  b, uint32_t *  result  )

inlinestatic

Add two 32-bit unsigned integers, detecting overflow.

Parameters

	a	First operand.
	b	Second operand.
[out]	result	Sum, wrapped around on overflow.

Returns

true if the sum overflowed.

References PBL_ADD_OVERFLOW.

pbl_u32_mul_overflow()

static bool pbl_u32_mul_overflow ( uint32_t  a, uint32_t  b, uint32_t *  result  )

inlinestatic

Multiply two 32-bit unsigned integers, detecting overflow.

Parameters

	a	First operand.
	b	Second operand.
[out]	result	Product, wrapped around on overflow.

Returns

true if the product overflowed.

References PBL_MUL_OVERFLOW.

positive_modulo()

static int positive_modulo ( int  i, int  n  )

inlinestatic

Compute a modulo that is never negative.

Parameters

i	Dividend.
n	Divisor, positive.

Returns

i mod n, in [0, n).

Referenced by distance_to_mod_boundary().

serial_distance()

int32_t serial_distance	(	uint32_t	start,
		uint32_t	end,
		int	bits
	)

Compute the distance between two serial numbers, handling wrap-around.

Parameters

start	Start value.
end	End value.
bits	Number of valid bits in start and end.

Returns

end - start, using serial number arithmetic (RFC 1982).

serial_distance32()

int32_t serial_distance32	(	uint32_t	start,
		uint32_t	end
	)

Compute the distance between two 32-bit serial numbers, handling wrap-around.

Parameters

start	Start value.
end	End value.

Returns

end - start, using serial number arithmetic (RFC 1982).

sign_extend()

int32_t sign_extend	(	uint32_t	a,
		int	bits
	)

Sign-extend the low bits of a value.

Parameters

a	Value; bits above bits are ignored.
bits	Width of the signed value, 1 to 32.

Returns

Sign-extended value.