## Sunday, August 14, 2011

### Rounding up!

Right shifting of positive integers leads to truncation:

9 >> 149 >> 22

Interestingly, right shift for negative integers also leads to truncation:

-9 >> 1-5-9 >> 2-3

If we combine the effects, we can get rounding up during right shift for positive integers:

-(-9 >> 1)5-(-9 >> 2)3

So here is a C function for rounding up while shifting:

int rightShiftRoundUp(int x, int n){    return - ( -x >> n);}

Voila!

## Friday, August 12, 2011

### Safe bool idiom

Note: This is just a rewrite of The Safe Bool Idiom by Bjorn Karlsson in my own words.

How do you provide for boolean tests for your classes in C++?

It is trivial for raw pointers:

if (T* p = get_some_value()){
// p is valid and not null we can use it here
}
else{
// p is null/invalid.
}
Any rvalue of arithmetic, enumeration, pointer, or pointer to member type, can be implicitly converted to an rvalue of type bool.

#### May be you have a smart pointer class:

typedef smart_ptr<T> TPtr;
TPtr p(get_some_value());
You might have a member function for testing in boolean contexts:
if(p.is_valid()){
// p is valid, use it
}
else{
// p is not valid. Take proper action.
}

Cons

• Verbose
• p must be declared outside the if block (the scope in which it is really used).
• The name is_valid may be different for different smart ptr like classes.

Objective

• It should be possible to convert existing code to make use of smart pointers from raw pointers with minimum change in code base.

#### We will use a class Testable in following.

May be you would code something like this:

class Testable {
bool ok_;
public:
explicit Testable(bool b=true):ok_(b) {}

operator bool() const {
return ok_;
}
};

We can use like following:

Testable test;
if (test)
std::cout << "Yes, test is working!\n";
else
std::cout << "No, test is not working!\n";

Bravo!

test << 1;
int i=test;
• A bool operator introduces nonsense operations which are legal and allowed by C++ compiler.
• All thanx to implicit conversion.

Take more side effects:

Testable a;
AnotherTestable b;

if (a==b) {
}

if (a<b) {
}

A possible enhancement here:

class Testable {
bool ok_;
private int () const ;
public:
explicit Testable(bool b=true):ok_(b) {}

operator bool() const {
return ok_;
}
};

#### Next comes operator !

Remember the old C trick?

int x = !! y; // maps y to 0 or 1.

We can do something like this in C++:

class Testable {
bool ok_;
public:
explicit Testable(bool b=true):ok_(b) {}

bool operator!() const {
return !ok_;
}
};

Now we can write:

Testable test;
if (!!test)
std::cout << "Yes, test is working!\n";
if (!test2) {
std::cout << "No, test2 is not working!\n";

Pros:

• No more implicit conversions
• Known as double-bang trick

Cons:

• Not as straight-forward as if(test)

#### The innocent void*

We can off course write a conversion function to void*:

class Testable {
bool ok_;
public:
explicit Testable(bool b=true):ok_(b) {}

operator void*() const {
return ok_==true ? this : 0;
}
};

This can be safely used in if(test).

Testable test;
delete test;
• The idiom is flawed
• It is possible to compare objects of different types as all have implicit conversion to void*.

#### Lets go for a nested class

Courtesy Don Box 1996, C++ Report:

class Testable {
bool ok_;
public:
explicit Testable(bool b=true):ok_(b) {}

class nested_class;

operator const nested_class*() const {
return ok_ ? reinterpret_cast<const nested_class*>(this) : 0;
}
};

Pros

• Rather than using a void* we are using a nested class.
• It won’t be possible to compare objects of different types.
• There is no need to define the nested class.

Cons:

Testable b1,b2;

if (b1==b2) {
}

if (b1<b2) {
}

#### The safe bool idiom

Lets declare an unspecified nested function type:

class Testable {
bool ok_;
typedef void (Testable::*bool_type)() const;
void this_type_does_not_support_comparisons() const {}
public:
explicit Testable(bool b=true):ok_(b) {}

operator bool_type() const {
return ok_==true ?
&Testable::this_type_does_not_support_comparisons : 0;
}
};
• Testable::*bool_type is typedef for a pointer to a const member function of Testable.
• this_type_does_not_support_comparisons is a private function with same signature as bool_type.
• We introduce a conversion operator to bool_type. We return 0 if Testable is invalid. We return pointer tothis_type_does_not_support_comparisons if Testable is valid.

The above code still allows following:

Testable test;
Testable test2;
if (test1==test2) {}
if (test!=test2) {}

Lets close the loop as follows:

template <typename T>
bool operator!=(const Testable& lhs,const T& rhs) {
lhs.this_type_does_not_support_comparisons();
return false;
}
template <typename T>
bool operator==(const Testable& lhs,const T& rhs) {
lhs.this_type_does_not_support_comparisons();
return false;
}
• this_type_does_not_support_comparisons is private
• operator== and operator!= are now non-members
• Any attemp to call them will result in compiler error.
• The error will be generated only if there is an attempt to instantiate these templates. So no extra code is going to be added in the executable.
Assignments
• Write a base class which can implement this idiom as a reusable component.
• Study the implementation of boost::scoped_ptr especially boost/smart_ptr/detail/operator_bool.hpp.
References

## Tuesday, August 9, 2011

### How to force your fellow members to use your version of a library function

So you designed your own powerful and scalable and efficient version of malloc and named it my_malloc. Now you wish to make sure that everybody in your team uses this version of malloc rather than calling the standard C library version. How would you enforce that?

#undef  malloc#define malloc use_my_malloc_please

You just put the above code in a common header file for your project which gets included everywhere. Anybody who tries to use standard library malloc, will get a compilation error. Hmm, this is only if  you are a C style programmer. In C++ off course you can override new and delete operators for a class as well as introduce your own new handlers.

### Offset of an attribute within a structure

Sometimes we may need to find out the offset of a particular attribute F of a structure T in C. Here is a simple one line macro to achieve the same:
  1: # define offsetof(T, F) ((unsigned int)((char *)&((T *)0)->F))

To understand, we are typecasting address NULL to type T and then computing the address of field F. Since the compiler knows about the layout of type T, hence it can compute this value during compilation and fill in wherever this is required. This is not computed at run-time.

## Monday, August 8, 2011

### Clamping short to unsigned char

Here is a standard video processing problems. Your 8-bit pixel values are typically in the range 0-255. If you do some processing on them which lead their values of this range you need to bring them down to this range. Negative values are clamped to 0 while positive values greater than 255 are clamped to 255.

A typical unoptimized implementation looks like follows.

  1: unsigned char clamp(short value){  2:   if (value < 0) return 0;  3:   if (value > 0xff) return 0xff;  4:   return value;  5: }

After long time, today I ended up seeing a much nicer implementation in FFmpeg code base which basically looks like:.

  1: const unsigned char clamp(int a)  2: {  3:   if (a&(~0xFF)) return (-a)>>31;  4:   else return a;  5: }

And I think, with a single if statement, its wonderful!

## Sunday, August 7, 2011

### A do while in a Macro

Looks like I know very little of C. So I never thought I would ever need to use a do while loop in a Macro.

Now consider this. A typical swap function looks like following:
  1: template void swap(T& a, T& b){  2:   T tmp;  3:   tmp = a;  4:   a = b;  5:   b = a;  6: }

As you can see that there are three different things on which the function depends, the type T and the variables a and b. How can I write a C Macro which does exactly the same thing?

  1: #define FFSWAP(T,a,b) do{T SWAP_tmp= b; b= a; a= SWAP_tmp;}while(0)

This is taken liberally from common.h in FFmpeg source code.

So we are writing a do,while loop which runs exactly once. Inside the loop we have a temporary variable created of type T (we choose a name for the temporary variable which is not expected to be taken by other variables inside the function). And rest is essentially the same 3 statements to achieve swapping.I still don't fully understand why did we need to add the do/while with this Macro. It might work without do/while also.

Please note that I don't want to say that macros are better than function templates. I just want to say that, I never knew about this macro magic.

### Functional programming and GCC

I was surprised to find that its possible in GCC to specify whether a function is pure or not at compile time. A pure function is a function which has no side effects. i.e. Its output depends solely on its input arguments and it doesn't affect any other resource in the system.

GCC allows one to specify function attributes. There is a specific attribute "pure" to specify pure function. E.g.: Publish Post

int square (int) __attribute__ ((pure));
Essentially this helps in doing specific compiler optimization (common sub-expression elimination). E.g. If a piece of code calls square(2)*square(2), compiler can rewrite it in such a way that square(2) is called once and the computed value is reused in place of second call to square(2).

Functions like strlen and memcpy are very good examples of pure functions. While flose(), feof() [in a multi-threading environment], a function which may lead to an infinite loop are all examples of non-pure functions.

This is covered in detail at Function Attributes in GCC.