Blog Archives

Using Function Pointers for Callbacks in C++

You plan to call some function func1, and at runtime you need it to invoke another function func2. For one reason or another, however, you cannot simply hardcode the name of func2 within func1. func2 may not be known definitively at compile time, or perhaps func1 belongs to a third-party API that you can’t change and recompile. In either case, you need a callback function.

In a situation such as that shown in below code, a function pointer is a good idea if updateProgress and longOperation shouldn’t knowanything about each other. For example, a function that updates the progress by displaying it to the user—either in a user interface (UI) dialog box, in a console window, or somewhere else—does not care about the context in which it is invoked. Similarly, the longOperation function may be part of some data loading API that doesn’t care whether it’s invoked from a graphical UI, a console window, or by a background process.

The first thing you will want to do is determine what the signature of the function is you plan to call and create a typedef for it. typedef is your friend when it comes to function pointers, because their syntax is ugly. Consider howyou would declare a function pointer variable f that contains the address of a function that takes a single integer argument and returns a boolean. It would look like this:
bool (*f)(int); // f is the variable name
One could argue, convincingly, that this is no big deal and that I’m just a whiner. But what if you want a vector of such function pointers?
vector<bool (*)(int)> vf;
Or an array of them?
bool (*af[10])(int);
Function pointers do not look like ordinary C++ variable declarations whose format is often a (qualified) type name followed by a variable name. This is why they can make for messy reading.
Thus, in below code, I used a typedef like this:
typedef bool (*FuncPtrBoolInt)(int);

Once that was out of the way, I was free to declare function pointers that have the signature of returning bool and accepting a single integer argument as I would any other sort of parameter, like so:

void longOperation(FuncPtrBoolInt f) {
// …
Now, all longOperation needs to do is call f like it would any function:
f (l/1000000);
In this way, f can be any function that accepts an integer argument and returns bool. Consider a caller of longOperation that doesn’t care about the progress. It can pass in a function pointer of a no-op function:
bool whoCares(int i) {return(true);}
//…
longOperation(whoCares);
More importantly, which function to pass to longOperation can be determined dynamically at runtime.


#include <iostream>
// An example of a callback function
bool updateProgress(int pct)

{
std::cout << pct << "% complete...\n";
return(true);
}

// A typedef to make for easier reading
typedef bool (*FuncPtrBoolInt)(int);
// A function that runs for a while
void longOperation(FuncPtrBoolInt f)

{
for (long l = 0; l < 100000000; l++)
if (l % 10000000 == 0)
f(l / 1000000);
}
int main( )

{
longOperation(updateProgress); // ok
}

 

Implementing Fixed-Point Numbers in C++

A fixed-point number, like a floating-point number, is an approximate representation of a real number. A floating-point number is stored as a mantissa (m), and an exponent (e), to form the equation m * be, where b is some constant. A fixed-point number is almost the same but the exponent is also a constant. This constant is passed to the basic_fixed_real in below class template as a template parameter.
By representing e as a constant, it allows fixed-point numbers to be represented internally as integers and for the arithmetic operations on them to be performed using integer arithmetic. This can often improve the speed of basic arithmetic operations
especially addition and subtraction. Fixed-point representations are less flexible than floating-point numbers, as they can only represent a narrow range of values. The fixed_real type in below function has a range that can only represent values from –2,097,151 to +2,097,151 with a precision of 1/1,024.
Implementing addition and subtraction of fixed-point numbers is straightforward enough: I simply add or subtract the underlying representation. To perform division and multiplication, I need an extra step of shifting the mantissa left or right to adjust for the binary point.

Below class template provides the implementation of a fixed-point real number, where the number of places to the right of the binary point is a template parameter. For instance basic_fixed_real<10> has 10 binary digits to the right of the binary point, allowing it to represent numbers up to a precision of 1/1,024.


#include <iostream>
using namespace std;

template<int E>
struct BasicFixedReal
{
typedef BasicFixedReal self;
static const int factor = 1 << (E - 1);
BasicFixedReal( ) : m(0) { }
BasicFixedReal(double d) : m(static_cast(d * factor)) { }
self& operator+=(const self& x) { m += x.m; return *this; }
self& operator-=(const self& x) { m -= x.m; return *this; }
self& operator*=(const self& x) { m *= x.m; m >>= E; return *this; }
self& operator/=(const self& x) { m /= x.m; m *= factor; return *this; }
self& operator*=(int x) { m *= x; return *this; }
self& operator/=(int x) { m /= x; return *this; }
self operator-( ) { return self(-m); }
double toDouble( ) const { return double(m) / factor; }
// friend functions
friend self operator+(self x, const self& y) { return x += y; }
friend self operator-(self x, const self& y) { return x -= y; }
friend self operator*(self x, const self& y) { return x *= y; }
friend self operator/(self x, const self& y) { return x /= y; }
// comparison operators
friend bool operator==(const self& x, const self& y) { return x.m == y.m; }
friend bool operator!=(const self& x, const self& y) { return x.m != y.m; }
friend bool operator>(const self& x, const self& y) { return x.m > y.m; }
friend bool operator<(const self& x, const self& y) { return x.m < y.m; }
friend bool operator>=(const self& x, const self& y) { return x.m >= y.m; }
friend bool operator<=(const self& x, const self& y) { return x.m <= y.m; }
private:
int m;
};
typedef BasicFixedReal<10> FixedReal;
int main( ) {
FixedReal x(0);
for (int i=0; i < 100; ++i) {

x += FixedReal(0.0625);
}
cout << x.toDouble( ) << endl;

}

The program outputs:
6.25

 

Representing Large Fixed-Width Integers in C++

Large integers are common in many applications. In cryptography, for example, integers of 1,000 bits and larger are not uncommon. The implementation I presented here is based on a binary representation of numbers using a bitset, at a cost of some performance. What I lost in performance I more than made up for in simplicity. A more efficient implementation of arbitrary precision numbers could easily fill the book.

The BigInt template below uses the bitset from the header to (from my last post) allow you to represent unsigned integers using a fixed number of bits specified as a template parameter.


//big_int.hpp
#ifndef BIG_INT_HPP
#define BIG_INT_HPP
#include <bitset>
#include "bitset_arithmetic.hpp" // from my last post of bitset manipulation.
template<unsigned int N>
class BigInt

{
typedef BigInt self;
public:
BigInt( ) : bits( ) { }
BigInt(const self& x) : bits(x.bits) { }
BigInt(unsigned long x) {
int n = 0;
while (x) {
bits[n++] = x & 0x1;
x >>= 1;
}
}
explicit BigInt(const std::bitset& x) : bits(x) { }
// public functions
bool operator[](int n) const { return bits[n]; }
unsigned long toUlong( ) const { return bits.to_ulong( ); }
// operators
self& operator<<=(unsigned int n) {
bits <<= n;
return *this;
}
self& operator>>=(unsigned int n) {
bits >>= n;
return *this;
}
self operator++(int) {
self i = *this;
operator++( );
return i;
}
self operator--(int) {
self i = *this;
operator--( );
return i;
}
self& operator++( ) {
bool carry = false;
bits[0] = fullAdder(bits[0], 1, carry);
for (int i = 1; i < N; i++) {
bits[i] = fullAdder(bits[i], 0, carry);
}
return *this;
}
self& operator--( ) {
bool borrow = false;
bits[0] = fullSubtractor(bits[0], 1, borrow);
for (int i = 1; i < N; i++) {
bits[i] = fullSubtractor(bits[i], 0, borrow);
}
return *this;
}
self& operator+=(const self& x) {
bitsetAdd(bits, x.bits);
return *this;
}
self& operator-=(const self& x) {
bitsetSubtract(bits, x.bits);
return *this;
}
self& operator*=(const self& x) {
bitsetMultiply(bits, x.bits);
return *this;
}
self& operator/=(const self& x) {
std::bitset tmp;
bitsetDivide(bits, x.bits, bits, tmp);
return *this;
}
self& operator%=(const self& x) {
std::bitset tmp;
bitsetDivide(bits, x.bits, tmp, bits);
return *this;
}
self operator~( ) const { return ~bits; }
self& operator&=(self x) { bits &= x.bits; return *this; }
self& operator|=(self x) { bits |= x.bits; return *this; }
self& operator^=(self x) { bits ^= x.bits; return *this; }
// friend functions
friend self operator<<(self x, unsigned int n) { return x <<= n; }
friend self operator>>(self x, unsigned int n) { return x >>= n; }
friend self operator+(self x, const self& y) { return x += y; }
friend self operator-(self x, const self& y) { return x -= y; }
friend self operator*(self x, const self& y) { return x *= y; }
friend self operator/(self x, const self& y) { return x /= y; }
friend self operator%(self x, const self& y) { return x %= y; }
friend self operator^(self x, const self& y) { return x ^= y; }
friend self operator&(self x, const self& y) { return x &= y; }
friend self operator|(self x, const self& y) { return x |= y; }
// comparison operators
friend bool operator==(const self& x, const self& y) {
return x.bits == y.bits;
}
friend bool operator!=(const self& x, const self& y) {
return x.bits != y.bits;
}
friend bool operator>(const self& x, const self& y) {
return bitsetGt(x.bits, y.bits);
}
friend bool operator<(const self& x, const self& y) {
return bitsetLt(x.bits, y.bits);
}
friend bool operator>=(const self& x, const self& y) {
return bitsetGtEq(x.bits, y.bits);
}
friend bool operator<=(const self& x, const self& y) {
return bitsetLtEq(x.bits, y.bits);
}
private:
std::bitset<N> bits;
};

The BigInt template class could be used to represent factorials, as shown below,


//Using the big_int class
#include "big_int.hpp"
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
void outputBigInt(BigInt<1024> x) {
vector<int> v;
if (x == 0) {
cout << 0;
return;
}
while (x > 0) {
v.push_back((x % 10).to_ulong( ));
x /= 10;
}
copy(v.rbegin( ), v.rend( ), ostream_iterator(cout, ""));
cout << endl;
}
int main( ) {
BigInt<1024> n(1);
// compute 32 factorial
for (int i=1; i <= 32; ++i) {
n *= i;
}
outputBigInt(n);
}

The program output is:
263130836933693530167218012160000000