Some coding tricks

Permanent link Create mask -1 or 0 or +1 from 2 integers difference   

return (a<b) ? -1 : (a>b);

Permanent link STL   

for ( int i = 0; i<Nbr; ++i )
{
    vec.push_bask( stuff );
}

vec.reserve(Nbr);
for ( int i = 0; i<Nbr; ++i )
{
    vec.push_bask( stuff );
}

if( hashmap[idx].second != NULL )

std::map::const_iterator it = hashmap.find(idx);
if( it != hashmap.end() )

Permanent link How to debug danglings pointers (destructed pointers pointing to freed memory)   

• Having a tool checking allocated memory bloc's signature, do a dichotomy search by checking in several place of the code all allocated blocs.
• If a few classes are suspected, make all member functions virtual: after the class is destroyed, the pointer on the Virtual Methods Table is set to NULL, and any call to a virtual member function will crash (you mustn't have any public member variable: always use accessors/setters).

Permanent link Convert a short int to a float between -1 et 1 using only int computations no to do Load-Hit-Store   

static inline void DecompressS16ToFloat( short value, float &f ) // = float(value) / 32768.0f with exact precision
{
	enum { NbrFractionBits=23, LastFractionBitS16=14, ExponentZero = 127 };

	int absValue = abs(value);
	int log2;
	{
		int v = absValue;
		int shift=0;
		log2 =  (v > 0xFFFF) << 4; v >>= log2;
		shift = (v > 0xFF  ) << 3; v >>= shift; log2 |= shift;
		shift = (v > 0xF   ) << 2; v >>= shift; log2 |= shift;
		shift = (v > 0x3   ) << 1; v >>= shift; log2 |= shift;
		                                        log2 |= (v >> 1);
	}

	int maskHigherBit = 1 << log2;
	int maskFraction = maskHigherBit - 1;
	int fraction = absValue & maskFraction;

	long i = fraction << (NbrFractionBits - log2 - LastFractionBitS16 - 18); // Mantisse
	i |= ( (ExponentZero - 15 + log2) << NbrFractionBits) & ((0==value) - 1) ; // Exponent

	i |= (value & (1<<15)) << 16; // Sign bit

	(long&) f = i;
}

static inline void DecompressU8ToFloat( unsigned char value, float &f ) // = float(value) / 256.0f with exact precision
{
    enum { NbrFractionBits=23, ExponentZero = 127 };

    int absValue = value;
    int log2;
    {
        int v = absValue;
        int shift=0;
        log2  = (v > 0xF   ) << 2; v >>= log2;
        shift = (v > 0x3   ) << 1; v >>= shift; log2 |= shift;
                                                log2 |= (v >> 1);
    }

    int maskHigherBit = 1 << log2;
    int maskFraction = maskHigherBit - 1;
    int fraction = absValue & maskFraction;

    long i = fraction << (NbrFractionBits - log2); // Mantisse
    i |= ( (ExponentZero - 8 + log2) << NbrFractionBits); // Exponent
    i &= ((0==value) - 1);

    (long&) f = i;
}

Permanent link Don't do int/float conversions   

for( uint i=0; i<GetNbrVertexes(); ++i )
{
    u8 &color = aCppArray[i];
    float colorF = (float)color;
    colorF *= ratio;
    color = (u8) colorf;
}

const uint nbrVertexes = GetNbrVertexes();
const u32 ratioInt = u32(ratio*65536.0f);
u8 *aColors = &*aCppArray.Begin();

for( uint i=0; i<nbrVertexes; ++i )
{
    u8 &color = aColors[i];
    u32 clr = color;
    clr = (clr*ratioInt) >> 16;
    color = (u8)clr;
}

uint floatInt = (uint) &floatValue;

union { float f; uint i; } conv; conv.f = floatValue; return conv.i

Permanent link How to use a STL custom allocator   

	namespace pool_alloc {
		inline void destruct(char*) {}
		inline void destruct(wchar_t*) {}
		template <typename T>
		inline void destruct(T* t) { (void)t; t->~T(); }
	}

	template<typename T, typename MemMgr>
	class Yac3DeStlCustomAllocator
	{
		static const unsigned long MaxAllocation = 102410241024;

	public:
		typedef size_t    size_type;
		typedef ptrdiff_t difference_type;
		typedef T*        pointer;
		typedef const T*  const_pointer;
		typedef T&        reference;
		typedef const T&  const_reference;
		typedef T         value_type;
		template <class U> struct rebind { typedef Yac3DeStlCustomAllocator other; };

		Yac3DeStlCustomAllocator() throw() {}
		Yac3DeStlCustomAllocator(const Yac3DeStlCustomAllocator&) throw() {}
		template <class U> Yac3DeStlCustomAllocator(const Yac3DeStlCustomAllocator&) throw() {}
		~Yac3DeStlCustomAllocator() throw() {}

		pointer address(reference x) const { return &x; }
		const_pointer address(const_reference x) const { return &x; }

		pointer allocate(size_type size, const_pointer = 0)
		{
			if( size == 0 )
				return NULL;
			else
			{
				//T *p = (T*) malloc( size*sizeof(T) );
				T *p = (T*) MemMgr::Alloc( size*sizeof(T) );
				return p;
			}
		}
		void deallocate(pointer p, size_type /n/)
		{
			//free(p);
			MemMgr::Free(p);
		}
		size_type max_size() const throw() { return MaxAllocation; }

		void construct(pointer p, const T& val)
		{
			new(static_cast(p)) T(val);
		}

		void destroy(pointer p)
		{
			pool_alloc::destruct(p);
		}

		bool operator ==(const Yac3DeStlCustomAllocator<T,MemMgr> & /other/)
		{
			return true;
		}
	};

	template<typename T, typename MemMgr>
	class Vector : public std::vector<T, Yac3DeStlCustomAllocator<T,MemMgr>>
	{
	public:
		Vector() {}
		~Vector() {}
	};

	template<typename T, typename MemMgr>
	class List : public std::list<T, Yac3DeStlCustomAllocator<T,MemMgr>>
	{
	public:
		List() {}
		~List() {}
	};

Permanent link Spherical Harmonics   

fConst1 = 4/17
fConst2 = 8/17
fConst3 = 15/17
fConst4 = 5/68
fConst5 = 15/68

void AddLightToSH ( Colour *sharm, Colour &colour, Vector &dirn )
{
    sharm[0] += colour * fConst1;
    sharm[1] += colour * fConst2 * dirn.x;
    sharm[2] += colour * fConst2 * dirn.y;
    sharm[3] += colour * fConst2 * dirn.z;
    sharm[4] += colour * fConst3 * (dirn.x * dirn.z);
    sharm[5] += colour * fConst3 * (dirn.z * dirn.y);
    sharm[6] += colour * fConst3 * (dirn.y * dirn.x);
    sharm[7] += colour * fConst4 * (3.0f * dirn.z * dirn.z - 1.0f);
    sharm[8] += colour * fConst5 * (dirn.x * dirn.x - dirn.y * dirn.y);
}

Colour LightNormal ( Vector &dirn )
{
    Colour colour = sharm[0];
    colour += sharm[1] * dirn.x;
    colour += sharm[2] * dirn.y;
    colour += sharm[3] * dirn.z;
    colour += sharm[4] * (dirn.x * dirn.z);
    colour += sharm[5] * (dirn.z * dirn.y);
    colour += sharm[6] * (dirn.y * dirn.x);
    colour += sharm[7] * (3.0f * dirn.z * dirn.z - 1.0f);
    colour += sharm[8] * (dirn.x * dirn.x - dirn.y * dirn.y);
    return colour;
}

Permanent link Reflexion in C++   

Permanent link Multiplying two 32 bits integers into a 64 bits integer   

#define Int32x32To64(a, b) ((LONGLONG)((LONG)(a)) * (LONGLONG)((LONG)(b)))

Permanent link Radix Sorting   

Permanent link My favorite IDE: Visual Studio + Vim + ...   

Permanent link Nant   

Permanent link DS   

Permanent link About coding habits   

• Bad: early abstraction, before we actually know if, how and why it will have to be abstracted.
• Don't abuse polymorphism and heritage. Often a class with pointers to composants will be more generic and cleaner. Example: "shall BreakableSlidingDoor class derivate from BreakableDoor or from SlidingDoor?" ?" vs an Entity class containing pointers to several composants, which will be NULL if the component doesn't exist for a particular entity (movement, life points and stats, AI, physics, rendering...).
• "Premature optimization is the root of all evil" (by Sir Tony Hoare) is so wrong, as the true quote by Sir Tony Hoare (other page with the full quote) does prove:
  We should forget about small efficiencies, say about 97 of the time: premature optimization is the root of all evil.
  Early function-local optimization (like asm) is wrong. Early algorithm/application architecture optimization is good and it is a must do/have to be a good programmer. Doing it too late in the life of the project means it will be harder or impossible to do, plus it will slow down the project development.
• Extreme-programming: bad name for grouping ideas that already existed previously. What creating another marketing word and why using the so negative "extreme" word?
• Peer-programming: very good for specs.

• No too long functions (max ~ one screen / 40 lines).
• No too generic meaningless variable names: dirPlayerToTarget instead of dir.
• Don't reuse a local variable in a different way, always create a new one with an explicit name.
• Add a comment on each #else and #endif telling which #if it corresponds.
• Exit a function only at the very beginning in some inputs checking, or at the very end.
• No "C" prefix in class names. This habits comes from Microsoft to make a clear distinction between their classes and classes from other programmers. Unfortunately other programmers started using the same naming convention (in an extended Hungarian notation), making it both useless and counter-productive.
• Use standardized coding guidelines in your team, that will help sharing code. A few examples (but you'll meet lots of other conventions as each company or even each project has its own rules):
• I like the Pascal/Java notation for class and methods/functions names, and the Camel notation for variables: no '_' in the middle of the name, caps on each word of the name, except the first one in variable names: float speed, int GetSpeed().
• Member variable names should be obious. Either using a prefix (m or m_ ou autre), or a suffix. Don't use '_' prefix or suffix as C/C++ standard forbid that. Small advantage of suffixes: faster to (not) type with auto-completion ; but harder to read/catch for some people.
• Hungarian Notation: I like a very simplified notation stating only statics, globals, C arrays, and C string. No pointer/integer/float/... prefix. But each team you'll meat will have different habits, one is to changes his habits with every new job.

Permanent link Quick inversion of a 4x3 matrix   

r.rot = transpose(M.rot);
r.pos = Vector(0,0,0);
t.rot.SetIdentity();
t.pos = -M.pos;
Minv = r*t;

Permanent link Vector and matrix classes, math operators   

Permanent link GCC and the PreCompiled Headers (PCH)   

• Create a header file that includes all the system headers you use (stdio.h string gl.h glew.h sdl.h ...). Do not include your project headers as they may change too often!
• Add in your Makefile the following rule :

  my_pch_header.h.gch: my_pch_header.h
  	@echo Precompiled header...
  	@rm -f *.o my_pch_header.h.gch # Force recompiling
  	@$(CC) $(CXXFLAGS) my_pch_header.h
  
  pch_all.h:
  	@echo "Generating PCH header"
  	@echo "#ifndef _ALL_H_" >pch_all.h
  	@echo "#define _ALL_H_" >>pch_all.h
  	@echo "
  	@cat *.C |grep -- "
  	@echo "#endif" >>pch_all.h
  

• Add my_pch_header.h.gch at the beginning of the list of files to compile.
• Add in your Makefile : CXXFLAGS+=-include my_pch_header.h

Permanent link How to cleanly use dependencies with GCC/Makefile   

Permanent link How to correctly indent using tabs   

Permanent link For those who love bits tricks   

• Reverse all the bits in a 32 bit word:
  I found this one in the Linux fortune cookie program (!)
  

  n = ((n >>  1) & 0x55555555) | ((n <<  1) & 0xaaaaaaaa) ;
  n = ((n >>  2) & 0x33333333) | ((n <<  2) & 0xcccccccc) ;
  n = ((n >>  4) & 0x0f0f0f0f) | ((n <<  4) & 0xf0f0f0f0) ;
  n = ((n >>  8) & 0x00ff00ff) | ((n <<  8) & 0xff00ff00) ;
  n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000) ;

• Test to see if a number is an exact power of two:

  b = ((n&(n-1))==0) ;

• Zero the least significant '1' bit in a word:

  n&~(n-1)

• Create a mask when a value is not zero/when a test fails:

  mask = (i==0)-1

• Convert any not null number in 1, else in 0

  b = !!b;

• Duff's device to unroll a loop - indenting is primordial to understand what's going on:

  int a = some_number ;
  int n = ( a + 4 ) / 5 ;
  
  switch ( a  5 )
  {
     case 0: do
          {
              putchar ( '*' ) ;
    case 4:   putchar ( '*' ) ;
    case 3:   putchar ( '*' ) ;
    case 2:   putchar ( '*' ) ;
    case 1:   putchar ( '*' ) ;
          } while ( --n ) ;
  }

• Log 2:

  r =     (v > 0xFFFF) << 4; v >>= r;
  shift = (v > 0xFF  ) << 3; v >>= shift; r |= shift;
  shift = (v > 0xF   ) << 2; v >>= shift; r |= shift;
  shift = (v > 0x3   ) << 1; v >>= shift; r |= shift;
                                          r |= (v >> 1);