Contents

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

2 STL

2.0.1 Débuggage sous Windows

3 Débugger des dangglings pointers (pointeur utilisé alors que libéré/détruit)

4 Convertir un short en floattant entre -1 et 1 en n'utilisant que des calculs sur des entiers pour ne pas faire de Load-Hit-Store

5 Les conversions entiers/floats sont à proscrire.

5.1 Les opérations bits sur des flottants sont à proscrire

6 Utiliser un allocateur custom dans la STL

7 Spherical Harmonics

8 Réflexion C++

9 Multiplication de deux entiers 32 bits pour un résultat sur 64 bits

10 Radix Sorting

11 Mon IDE favori: Visual Studio + Vim + ...

12 Nant

13 DS

14 Remarques sur les habitudes de programmation

14.1 Généralités

14.2 Code lisible

15 Inversion rapide d'une matrice 4x3

16 Vecteur, matrices, classes mathématiques Vector et les opérateurs mathématiques

17 GCC et les PreCompiled Headers (PCH)

18 Bien gérer ses dépendances avec GCC/Makefile

19 Comment bien indenter avec des tabulations

20 Pour ceux qui adorent les opérations sur les bits

21 Switcher facilement d'un clavier Français à un clavier Us en appuyant sur Alt+Shift sous X11





Quelques astuces de programmation

Voici quelques petits astuces, liens, et conseils, de moi ou trouvés un peu partout sur le net.




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

From Sean Barrett
return (ab);

Permanent link STL   

Mauvais car réalloue souvent le vector :
for ( int i = 0; i<Nbr; ++i )
{
    vec.push_bask( stuff );
}
Bon :
vec.reserve(Nbr);
for ( int i = 0; i<Nbr; ++i )
{
    vec.push_bask( stuff );
}

Mauvais car créer des núuds inutiles dans l'arbre de la map :
if( hashmap[idx].second != NULL )
Bon :
std::map it = hashmap.find(idx);
if( it != hashmap.end() )

Débuggage sous Windows

Contenu d'un vecteur : m_vector._Myfirst

Permanent link Débugger des dangglings pointers (pointeur utilisé alors que libéré/détruit)   

Deux stratégies :

Permanent link Convertir un short en floattant entre -1 et 1 en n'utilisant que des calculs sur des entiers pour ne pas faire de 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; }
Precision :
Integer float(i)/32768.0f DecompressS16ToFloat Error
0 0.000000 0.000000 0.000000
32767 0.999969 0.999969 0.000000
16383 0.499969 0.499969 0.000000
8191 0.249969 0.249969 0.000000
-8191 -0.249969 -0.249969 0.000000
-16383 -0.499969 -0.499969 0.000000
-32768 -1.000000 -1.000000 0.000000
25735 aka π/4 0.785370 0.785370 0.000000
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; }
Precision :
Integer float(i)/32768.0f DecompressU8ToFloat Error
0 0.000000 0.000000 0.000000
63 0.246094 0.246094 0.000000
64 0.250000 0.250000 0.000000
127 0.496094 0.496094 0.000000
128 0.500000 0.500000 0.000000
200 0.781250 0.781250 0.000000
255 0.996094 0.996094 0.000000

Permanent link Les conversions entiers/floats sont à proscrire.   

Sur les CPUs modernes, les conversions entre float et entier sont très lentes. Il faut voir ces CPUs comme des assemblages de blocs indépendants : les blocs entiers, FPU et SSE ne peuvent s'échanger directement de valeur ; tout transfert doit se faire par la mémoire (au moins par le cache-mémoire).
Sur les processeurs Power, cela provoque un flush du cache avant relecture en mémoire : ce qu'on appelle un Load-Hit-Store ; c'est la seconde cause première de perte de performance au niveau local après les cache-miss sur le L2.
Vu dans notre moteur au travail (version ici simplifiée) :
for( uint i=0; i<GetNbrVertexes(); ++i )
{
    u8 &color = aCppArray[i];
    float colorF = (float)color;
    colorF *= ratio;
    color = (u8) colorf;
}

J'ai réécrit ce code ainsi, et il a été mesuré comme 20 fois plus performant :
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; }

Les opérations bits sur des flottants sont à proscrire

Ces codes sont invalides en C++ moderne :
uint floatInt = (uint) &floatValue;
union { float f; uint i; } conv; conv.f = floatValue; return conv.i;
La valeur retournée risque sur certains compilateurs (et de plus en plus à l'avenir) d'être complètement aléatoire. L'unité de calcul entier et la FPU ont chacun leur vue sur la mémoire, et ils peuvent croire avoir la bonne valeur en mémoire cache alors que l'autre l'a modifié.

Phénomène connu sous le nom d'aliasing mémoire.

Permanent link Utiliser un allocateur custom dans la STL   

	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; } };
Exemple d'utilisation :
	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   

Light to SH:
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); }
Additionnez le contenu du tableau sharm pour toutes les lumières éclairant votre objet ou prone.
Puis pour chaque pixel lors de l'affichage de l'objet :
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;
}
Source : Spherical Harmonics GDCE PPT97 - Tom Forsyth et son complément.

Permanent link Réflexion C++   

Jon Watte explique comment implémenter/générer des réflections en C++ de manière simple et automatisée.
Son code source.

Permanent link Multiplication de deux entiers 32 bits pour un résultat sur 64 bits   

Vu sur le site de Charles Bloom : VC++ a l'air très mauvais à optimiser une multiplication de deux entiers longs:
U64 product = (U64) a * b
Sauf si on utilse la macro Int32x32To64 qui fait exactement la même chose!
#define Int32x32To64(a, b) ((LONGLONG)((LONG)(a)) * (LONGLONG)((LONG)(b)))

Il a aussi vu dans le source d'OpenSSL que la stdlib Windows a une fonction pour les rotations d'octets dans des entiers, _lrotl et _lrotr.

Permanent link Radix Sorting   

Un algo de tri très rapide, en 0(kN) donc plus rapide que les algos standards en O(NlogN) tels que les qsort, bubble-sort...: le Radix Sort, une idée toute basique ; ici adaptée par Pierre Terdiman et Chris Hecker pour pouvoir travailler sur n'importe quels types de données, y compris des floats et des floats négatifs.

Permanent link Mon IDE favori: Visual Studio + Vim + ...   

24/01/2008
Mon environnement de travail favori actuel se compose de Visual C++ 2005 pour son débugger, Visual Assist pour sa colorisation et quelques uns de ses outils de refactoring, VsFileFinder pour s'y retrouver dans l'arborescence bordélique de VC++ représentant les projets, et surtout le plugin ViEmu pour retrouver à l'intérieur de VC++ mon éditeur favori, j'ai nommé Vim.

Permanent link Nant   

24/01/2008
Ayant travaillé avec Nant, je commence à avoir une image assez négative de ce build system.

Tout d'abord Nant est extrêmement lent, surtout pour les builds incrémentielles. Rien à voir avec un système à base de Makefiles. Un exemple : réécrire la gestion des dépendances des animations exportées en une tâche C# à la place d'une boucle dans le fichier XML configurant Nant a réduit la compilation des personnages d'un jeu de 60%, divisant par deux les temps de compilations des données d'un niveau.

Ensuite il se configure à travers des fichiers XML qui sont d'une verbosité affligeante. Il offre une grande liberté d'action, mais pas vraiment plus qu'un Makefile.

Et enfin il ne supporte toujours pas les builds multithreadées, alors que Make le supporte de base depuis longtemps.

Permanent link DS   

24/01/2008
Au premier aperçu d'un kit de dev DS et de sa doc, on se dit que ce matos est vraiment merdique.

Mais après quelques temps j'ai commencé à vraiment apprécié cette plateforme : elle fait peu de choses, mais elles les fait biens, et assez facilement. L'ensemble parait même assez équilibré ; par exemple la faible résolution de l'écran ne nécessite pas plus que la puissance très limitée du GPU pour afficher des graphismes corrects.

Un gros plus par rapport à la PSP : l'utilisation de mémoire flash/ROM à la place des disques optiques. Ce qui donne un temps d'accès minuscule. Adieu les écrans de chargements. Et cela permet de compenser la limite en nombres de polygones affichables, en streamant le niveau au fur et à mesure que l'on se promène dedans.

Il y a toutefois certaines limitations ; par exemple le stencil buffer à un bit par pixel ne permet pas d'afficher des ombres d'objets concaves comme des personnages, expliquant les blobs circulaires en guise d'ombres jusqu'à aujourd'hui - et je répète : jusqu'à aujourd'hui ;).

Par contre sur la PSP l'absence de clipping hardware est un gros inconvénient. Deux solutions possibles : n'avoir que des polygones très petits (donc bien plus nombreux ; ceci parce que le culling des polygones ne se fait pas sur le bord de l'écran mais un peu plu loin, donc on prie pour que les polygones partiellement visibles soient tous assez petits pour rester dans les limites du culling) ; ou implémenter un culling sur CPU et régénérer une liste de polygones pour chaque objet affichés et à clipper (ralentit pas mal le rendu). Et l'écran a une rémanence incroyablement élevée comparé à celui de la DS.

Permanent link Remarques sur les habitudes de programmation   

Généralités

Code lisible


Permanent link Inversion rapide d'une matrice 4x3   

Soit M = T * R, une matrice 4x3.
Normalement on utilise une méthode lourde en calcul comme Gauss, mais regardez ceci :
M-1=(T*R) -1=R -1*T -1=Rt*T -1

Donc on transpose la partie rotation, on créé T-1 qui est la translation opposée de la matrice originale, on multiplie ensemble ces deux matrices et voila! Pseudocode :
r.rot = transpose(M.rot);
r.pos = Vector(0,0,0);
t.rot.SetIdentity();
t.pos = -M.pos;
Minv = r*t;

Permanent link Vecteur, matrices, classes mathématiques Vector et les opérateurs mathématiques   

Souvent vous lirez qu'écrire une classe Vector utilisant naÔvement Vector operator +(const Vector&, const Vector& ) va créé un objet temporaire qui va être construit, copié puis détruit et que cela va ralentir votre code.

Et bien c'est... vrai.

Mais si on définit cet operator ainsi : inline const Vector operator +( const Vector &a, const Vector &b ) non seulement la plupart des compilateurs (testé sur PC et PSP) n'utilisent plus d'objet temporaire mais en plus cela sera plus rapide que réécrire une opération mathématique pour minimiser le nombre d'objet temporaire (10% plus rapide qu'utiliser des tableaux de flottants directement ou qu'utiliser des opérateurs non problématiques comme += pour arriver au même résultat selon mes tests sur gcc PSP). Notez comment l'objet retourné est constant. Cela est indispensable ; autrement l'objet retourné pourrait être modifié par un autre opérateur et ne sera pas optimisé.
Des débutants retournent parfois une référence, mais c'est une erreur de renvoyer une référence sur un objet temporaire car il sera détruit avant d'être utilisé, et ça ne fonctionnera pas tout le temps.


Permanent link GCC et les PreCompiled Headers (PCH)   

Et c'est fini, la compilation ira désormais deux fois plus vite!

Permanent link Bien gérer ses dépendances avec GCC/Makefile   

J'ai vu trop de projet avoir une compilation en deux passes : make dep suivi de make. Et si on oublie de relancer make dep de temps en temps, les dépendances ne sont plus à jour.

La bonne solution : rajouter -MD à CFLAGS ou CXXFLAGS. La recompilation d'un ficher va désormais recréer le fichier de dépendance de ce source. Et rajouter -include *.d à la fin du Makefile. Le make dep n'est alors nécessaire que lors d'effacement de fichiers headers.


Permanent link Comment bien indenter avec des tabulations   

Indenter avec des tabulations et des espaces mélangés.

Permanent link Pour ceux qui adorent les opérations sur les bits   

Source : Steve's 'Cute Code' collection et Sean Eron's Bit Twiddling Hacks

Permanent link Switcher facilement d'un clavier Français à un clavier Us en appuyant sur Alt+Shift sous X11   

A rajouter dans .xinitrc ou dans .xsession : setxkbmap -option grp:alt_shift_toggle fr,us
Main page Back

email : Sly