Increment And Decrement Wrapping Values
Mike Acton
July 11, 2006
July 11, 2006
Small code, big impact
Occasionally you have a set of values that you want to wrap around as you increment and decrement them. For example, in a GUI where the user keys right or left and you want to wrap around the menu.A typical implementation:
static inline int wrap_inc( int value, int min, int max )
{
return ( value == max ) ? min : value + 1;
}
static inline int wrap_dec( int value, int min, int max )
{
return ( value == min ) ? max : value - 1;
}
But on processors (such as the PowerPC) where compare and branch is very costly these small one-liners can have a significant impact on performance when used in critical code. They also make optimization more difficult for the compiler for the surrounding code. For more information read: Better Performance Through Branch Elimination
Breakdown
Store the desired result:
const type result_inc = val + 1;
This value may overflow if val == INT(SIZE)_MAX, but in that case the correct value will still be selected.Get the different between the max (or min) value and the current value:
const type max_diff = max - val;
It's only important if this value is zero or not zero. If it's zero, we know we are at the max (or min) value; otherwise we can increment (or decrement).Create a mask based on the difference:
const type max_diff_nz = (type)( (stype)( max_diff | -max_diff ) >> bit_mask );
i.e.
max_diff_nz = ( max_diff != 0 ) ? (type)-1 : (type)0;
(Remember that -1 is all bits on in two's complement.)Complement the mask:
const type max_diff_eqz = ~max_diff_nz;
Select the correct result based on the masks:
const type result = ( result_inc & max_diff_nz ) | ( min & max_diff_eqz );
Only one of the two values can possibly be selected.i.e.
result = ( val == max ) ? min : val + 1;
Final Code
//
// wrap_int.h
//
#ifndef WRAP_INT_H
#define WRAP_INT_H
//
// Increment wrapping value
//
// val = { ( val == max ), min
// = { otherwise, val + 1
//
// uint8_t wrap_inc_u8 ( const uint8_t val, const uint8_t min, const uint8_t max );
// uint16_t wrap_inc_u16( const uint16_t val, const uint16_t min, const uint16_t max );
// uint32_t wrap_inc_u32( const uint32_t val, const uint32_t min, const uint32_t max );
// uint64_t wrap_inc_u64( const uint64_t val, const uint64_t min, const uint64_t max );
// int8_t wrap_inc_s8 ( const int8_t val, const int8_t min, const int8_t max );
// int16_t wrap_inc_s16( const int16_t val, const int16_t min, const int16_t max );
// int32_t wrap_inc_s32( const int32_t val, const int32_t min, const int32_t max );
// int64_t wrap_inc_s64( const int64_t val, const int64_t min, const int64_t max );
#define DECL_WRAP_INC( type_name, type, stype, bit_mask ) \
static inline type wrap_inc_##type_name( const type val, const type min, const type max ) \
{ \
const type result_inc = val + 1; \
const type max_diff = max - val; \
const type max_diff_nz = (type)( (stype)( max_diff | -max_diff ) >> bit_mask ); \
const type max_diff_eqz = ~max_diff_nz; \
const type result = ( result_inc & max_diff_nz ) | ( min & max_diff_eqz ); \
\
return (result); \
}
DECL_WRAP_INC( u8, uint8_t, int8_t, 7 );
DECL_WRAP_INC( u16, uint16_t, int16_t, 15 );
DECL_WRAP_INC( u32, uint32_t, int32_t, 31 );
DECL_WRAP_INC( u64, uint64_t, int64_t, 63 );
DECL_WRAP_INC( s8, int8_t, int8_t, 7 );
DECL_WRAP_INC( s16, int16_t, int16_t, 15 );
DECL_WRAP_INC( s32, int32_t, int32_t, 31 );
DECL_WRAP_INC( s64, int64_t, int64_t, 63 );
//
// Decrementing wrapping value
//
// val = { ( val == min ), max
// = { otherwise, val - 1
//
// uint8_t wrap_dec_u8 ( const uint8_t val, const uint8_t min, const uint8_t max );
// uint16_t wrap_dec_u16( const uint16_t val, const uint16_t min, const uint16_t max );
// uint32_t wrap_dec_u32( const uint32_t val, const uint32_t min, const uint32_t max );
// uint64_t wrap_dec_u64( const uint64_t val, const uint64_t min, const uint64_t max );
// int8_t wrap_dec_s8 ( const int8_t val, const int8_t min, const int8_t max );
// int16_t wrap_dec_s16( const int16_t val, const int16_t min, const int16_t max );
// int32_t wrap_dec_s32( const int32_t val, const int32_t min, const int32_t max );
// int64_t wrap_dec_s64( const int64_t val, const int64_t min, const int64_t max );
#define DECL_WRAP_DEC( type_name, type, stype, bit_mask ) \
static inline type wrap_dec_##type_name( const type val, const type min, const type max ) \
{ \
const type result_dec = val - 1; \
const type min_diff = min - val; \
const type min_diff_nz = (type)( (stype)( min_diff | -min_diff ) >> bit_mask ); \
const type min_diff_eqz = ~min_diff_nz; \
const type result = ( result_dec & min_diff_nz ) | ( max & min_diff_eqz ); \
\
return (result); \
}
DECL_WRAP_DEC( u8, uint8_t, int8_t, 7 );
DECL_WRAP_DEC( u16, uint16_t, int16_t, 15 );
DECL_WRAP_DEC( u32, uint32_t, int32_t, 31 );
DECL_WRAP_DEC( u64, uint64_t, int64_t, 63 );
DECL_WRAP_DEC( s8, int8_t, int8_t, 7 );
DECL_WRAP_DEC( s16, int16_t, int16_t, 15 );
DECL_WRAP_DEC( s32, int32_t, int32_t, 31 );
DECL_WRAP_DEC( s64, int64_t, int64_t, 63 );
#endif /* #ifndef WRAP_INT_H */