Nouveau framework et moteur 3D


26 août 2007

Schéma d'un moteur 3D simple à appréhender, fonctionnel (objets procéduraux - metaball, terrains -, effets type post-prod, rendus hiérarchiques - personnages -, GUI 3D, films en tant que textures, particules. Il faut rassembler toutes les idées qui surgissent.

Plusieurs Scene3D gérées par un moteur de gestion d'objets (faut-il plusieurs moteur 3D ?). Chaque objets à une interface de rendu qui prépare ses données spécifiquement pour un moteur de rendu, géré par Renderer appelé par le moteur. Un objet 3D est rattaché à une scène et un viewport est rattaché à un moteur 3D. Une scène peut être rattachée à plusieurs viewport. Un objet 3D contient sa description 3D qu'il peut communiquer sous certaines formes à son renderer via son interface de rendu. S'il y a n objets il y a approximativement log(n) interfaces de rendus présentes en run-time. Une interface de rendu peut être : objet classique (géo+topo+texture), objet procédural, moteur de particule etc. Des sous renderer pourront gérer les films au sein de textures. La hiérarchie est gérée par le moteur haut-niveau, la position et l'orientation d'un objet sont contenues dans l'objet lui-même.

Pour organiser un peu tout ce bordel, un tagage automatique semble être la bonne solution. ?a impose un contenu riche mais ça permet un classement automatique.
A faire de toute urgence donc.
Il me faut adapter de toute urgence mon parser XML sous Linux, j'ai besoin de faire des profiles au cas où des applications custom seraient nécessaires.

J'ai rassemblé ci-dessous des notes C++ représentant les axiomes de bases implémentées par le framework pour toutes les utilisations auxquelles je le destine.

class   BaseObject
{
    private:
            BaseObject();       //On ne peut pas faire de new Engine() par exemple
            ~BaseObject();      //Seul une factory peut effacer réellement un objet, sinon il est collecté lors d'un remove
            friend  class   Factory();

    public:
            //Fonctions génériques de (dé)sérialisations et d'import/export XML
            HCODE   toXML(XMLElement* dest);
            HCODE   toXML(String& dest);
            HCODE   fromXML(const XMLElement* obj);         //Initialise l'objet courant depuis une description XML
            HCODE   fromXML(const String& obj);             //Initialise l'objet courant depuis une description XML
            HCODE   serialize(Flow& output);
            HCODE   unserialize(Flow& input);
            //Fonctions communiquant avec d'autres objets
            HCODE   send(ObjectId dest, Message& msg)
            HCODE   getNextMessage(Message& msg);
            HCODE   flushMessage();
            //Thread management de l'objet
            //Gestion des propriétés de l'objet : ses données / champs, ses méthodes / actions
            HCODE   Get(const String& fieldName, Field& field);         //Récupère la valeur d'un champ de l'objet courant
            HCODE   Set(const String& fieldName, const Field& field);   //Fixe la valeur d'un champ de l'objet courant
            String  compName = type de l'objet
            //Références maintenues par l'objet : des références
            delete();           //Efface l'objet et les éventuels liens qu'il avait avec d'autres
            //.............
            //Ses champs
            Array<Field>    Fields;
            ObjectId        ObjectSchema;       //Référence du schéma (la structure) de l'objet
            uint            Id;                 //L'Id unique de l'objet courant
};

Objets utilitaires : Field, Array, String, HashTable, Flow (pour les flux de lecture ou d'écriture, sur disque, HTTP ou autres.).

//Tous les objets sont représentés par leur Id, unique, et gérées par un singleton : Objects
class   ObjectId
{
    operator->(const String& funcName);
};

//Une classe qui crée des composants
class   Objects
{
    HCODE       RegisterType()      //Enregistre un type connu et ses champs
    HCODE       FromType            //IDs de tous les objets d'un certain type
    HCODE       Select              //Requête complète (plus complexe mais adapté à des utilisations plus pointues que FromType)
    ObjectId    FromId()            //Renvoie l'ObjectId d'un objet donné

    ObjectId    createComponent(const String& compName)
    {
        BaseObject*     NewObject = new BaseObject();
        NewObject->ObjectSchema = Type[compName][\"schema\"];
    }
};

//Une fonction globale pour créer des composants
ObjectId    CreateComponent(const String& compName)
{
    ObjectId    Fact = Objects->getFactory();
    if (!Fact)      return LastError();
    return Fact->createComponent(compName);
};

Classe de base dont devrait hériter tous les composants

Selection d'objets

Il faut une méthode pour, avec une zone rectangulaire de sélection, sélectionner le plus rapidement possible les objets, 2D pour commencer, dont la bounding-box est interceptée. Je pense à deux range trees (ou des priority tree) pour le stockage des bbox (AABB) - un arbre pour chacune des dimensions considérées, et à deux hash-tables pour le parcours des deux arbres et l'instersection des 4 interrogations suivantes, si S est l'ensemble des objets de la scène :

L1 = { o de S tel que (o.bbox.x1 || o.bbox.x2) >= selectArea.y1 && !(o.bbox.x1 > selectArea.y2) }
L2 = L1 &#8745; { o de S tel que (o.bbox.x1 || o.bbox.x2) <= selectArea.y2 && !(o.bbox.x2 < selectArea.y1) }
L3 = L2 &#8745; { o de S tel que (o.bbox.y1 || o.bbox.y2) >= selectArea.y1 && !(o.bbox.y1 > selectArea.y2) }
L4 = L3 &#8745; { o de S tel que (o.bbox.y1 || o.bbox.y2) >= selectArea.y2 && !(o.bbox.y2 > selectArea.y1) }

Librairie de Math


19 août 2007

Librairie de math

La librairie que je suis en train de concevoir pour exécuter, entre autres choses, des calculs sur des polynômes, des vecteurs et des matrices.

#include <stdarg.h>
#include <math.h>

using namespace std;

class   QiXMath : public std::exception
{
    public:
        QiXMath(char* msg)      { _whatMsg = msg; }
        virtual const char* what() const throw()    {   return _whatMsg;    }
    protected:
        char*   _whatMsg;
};


//Pour représenter des fractions, ce qui est très utile pour les polynôme quand on veut des calculs exacts.
//Note : pour simplifier des nombres décimaux qui ont des séquences répétitives voir http://en.wikipedia.org/wiki/QiFraction_(mathematics)
//TOCHECK : l'opérateur /(int) ne doit pas être nécéssaire puisque j'ai un constructeur qui a un int en entrée, pourquoi dois-je en avoir un ???
template <class T>
class   QiFraction
{
    public:
        //Faire un constructeur avec un seul paramètre : le numérateur.
        QiFraction(T n, T d)        {   _n = n; _d = d; }
        QiFraction(T n=0)       {   _n = n; _d = 1; }
        QiFraction(float n) {   _n = (T) n; _d = 1; }
        QiFraction(int n)   {   _n = (T) n; _d = 1; }
        void    dump()      const
        {
            if (_n == 0 || _d == 1)     cout << _n;
            else    {
                if (_n == _d)       cout << "1";
                else    cout << _n << "/" << _d;
            }
        }
        QiFraction<T>&  operator+=(const QiFraction<T>& a)
        {
            T   P = pgcd(_d, a._d);
            T   NewD = (_d * a._d) / P;
            _n = _n * (NewD / _d) + a._n * (NewD / a._d);
            _d = NewD;
            return *this;
        }
        QiFraction<T>&  operator-=(const QiFraction<T>& a)
        {
            T   P = pgcd(_d, a._d);
            T   NewD = (_d * a._d) / P;
            _n = _n * (NewD / _d) - a._n * (NewD / a._d);
            _d = NewD;
            return *this;
        }
        QiFraction<T>&  operator*=(const QiFraction<T>& a)
        {
            _n *= a._n;
            _d *= a._d;
            //On simplifie la fraction
            T   Common = pgcd(_n, _d);
            _n /= Common;
            _d /= Common;
            return *this;
        }
        QiFraction<T>&  operator/=(const QiFraction<T>& a)
        {
            _n *= a._d;
            _d *= a._n;
            //On simplifie la fraction
            T   Common = pgcd(_n, _d);
            _n /= Common;
            _d /= Common;
            return *this;
        }
        QiFraction<T>   operator+(const QiFraction<T>& a)       const
        {
            QiFraction  Result(_n, _d);
            return Result += a;
        }
        QiFraction<T>   operator-(const QiFraction<T>& a)       const
        {
            QiFraction  Result(_n, _d);
            return Result -= a;
        }
        QiFraction<T>   operator*(const QiFraction<T>& a)       const
        {
            QiFraction  Result(_n, _d);
            return Result *= a;
        }
        QiFraction<T>   operator/(const QiFraction<T>& a)       const
        {
            QiFraction  Result(_n, _d);
            return Result /= a;
        }
        QiFraction<T>   operator/(T a)      const
        {
            QiFraction<T>   Result(_n, _d);
            return Result /= QiFraction<T>(a);
        }
        QiFraction<T>   operator/(int a)        const
        {
            QiFraction<T>   Result(_n, _d);
            return Result /= QiFraction<T>(a);
        }
        bool    operator>=(float t) const       {   return (float)_n/(float)_d > t;     }
        bool    operator==(float t) const       {   return (float)_n/(float)_d == t;    }
        operator float()    const   {   return (float)_n/(float)_d; }
        QiFraction<T>&  inverse()
        {
            T   Tmp = _n;
            _n = _d;
            _d = _n;
            return *this;
        }
        T   pgcd(T u, T v/*, int verbose=false*/)
        {
            T   M = 1;
            if (u<0)        u = (T)0-u;
            if (v<0)        v = (T)0-v;
            while (u && v)      {
//      if (verbose)        printf("pgcd(%d, %d)\n", u, v);
                if (!(u&1) && !(v&1))       { M <<= 1; u>>=1, v>>=1; }
                else    if (!(u&1) && v&1)      u>>=1;
                else    if (u&1 && !(v&1))      v>>=1;
                else    {       //Les deux nombres sont impairs
                    if (u>v)    u=(u-v)>>1;
                    else        v=(v-u)>>1;
                }
            }
            return M * (u ? u : v);
        }
//Note : ppcm(a,b) = (a*b)/pgcd(a,b)

    T   _n, _d;     //Numérateur et dénominateur
};


//###TODO (25%) : Exceptions
//###TODO : cacher l'évaluation du degré d'un polynôme
//###TODO : faire la factorisation simple d'un polynôme
//###TODO : faire des opérateurs pour QiMatrix et QiPolynomial
//###TODO : faire des opérateurs pour QiVector
template <class T>
class   QiPolynomial
{
    public:
        QiPolynomial(int rank)
        {
            _comps = NULL;
            _init(rank);
        }
        ~QiPolynomial()
        {
            DELETEARRAY(_comps);
        }
        QiPolynomial(const QiPolynomial<T>& original)
        {
            if (this != &original)      {
                _init(original.rank());
                int i;
                for(i=0; i<=rank(); i++)        _comps[i] = original.get(i);
            }
        }
    protected:
        void    _init(int rank)
        {
            if (rank<0)     return;
            _rank = rank;
            _comps = new T[_rank+1];
        }
        void    _expand(int nbWantedSlots)
        {
            int NewSize = nbWantedSlots;
            _comps = new T[NewSize];
            if (!_comps)        throw new QiXMath("QiPolynomial::_expand : NotImplemented");
//          memcpy();
        }
    public:
        //
        void    null()
        {
            int i;
            for(i=0; i<=rank(); i++)        _comps[i] = 0.0f;
        }
        void    primitive()
        {
            int Degree = degree();
            if (rank() < Degree+1)      _expand(Degree+1);
            int i, MaxIndex = degree();
            for(i=MaxIndex; i>=0; i--)      _comps[i+1] = _comps[i]/(i+1);
            _comps[0] = 0.0f;
        }
        void    add(const QiPolynomial<T>& op)
        {
            int i;
            int MaxIndex = op.rank();
            if (rank() < MaxIndex)      MaxIndex = rank();
            for(i=0; i<=MaxIndex; i++)          set(i, get(i) + op.get(i));
        }
        QiPolynomial<T>&    operator *= (const QiPolynomial<T>& a)
        {
            multiply(a);
            return *this;
        }
        bool    multiply(const QiPolynomial<T>& op)
        {
            if (degree() + op.degree() > rank())        return false;
            QiPolynomial    Temp(degree() + op.degree());
            int MaxIt = op.degree(), i, j;
            int CurrentDegree = degree();
            Temp.null();
            for(i=0; i<=MaxIt; i++)     {
                for(j=0; j<=CurrentDegree; j++)     {
                    T   CurrentValue = Temp.get(i+j);
                    T   NewInc = op.get(i) * get(j);
                    Temp.set(i+j, CurrentValue + NewInc);
                }
            }
            set(Temp);
            return true;
        }
        void    multiply(T coeff)
        {
            int i;
            int MaxIndex = degree();
            for(i=0; i<=MaxIndex; i++)      set(i, get(i)*coeff);
        }
        QiPolynomial<T>&    operator /= (const T& a)
        {
            int i;
            int MaxIndex = degree();
            for(i=0; i<=MaxIndex; i++)      {
                set(i, get(i) / a);
            }
            return *this;
        }
        void    set(const QiPolynomial& src)
        {
            int i;
            null();
            int MaxIndex = rank();
            if (MaxIndex>src.rank())        MaxIndex = src.rank();
            for(i=0; i<=MaxIndex; i++)      set(i, src.get(i));
//          _rank = src.rank();
        }
        void    setRaw(int maxDegree, ...)
        {
            if (maxDegree > rank())     return;
            va_list args;
            va_start(args, maxDegree);
            int i, j;
            for(i=maxDegree; i>=0; i--)     {
                float   Value = (float) va_arg(args, double);
                _comps[i] = Value;
            }
            va_end(args);
        }
        //On remplace la variable x du polynôme par un autre polynôme (x par x+1 par exemple).
        //On substitue donc Q(x) à x dans P(x), ce qui donne P(Q(x)), un autre polynôme en x.
        //La méthode :
        void    substitute(const QiPolynomial& newVar)
        {
            QiPolynomial    Value(newVar.degree() + degree()), Total(newVar.degree() + degree());
            QiPolynomial    Param(newVar.degree() + degree());
            int i;
            Param.null();
            Param.set(0, 1.0f);
            for(i=0; i<=degree(); i++)      {
                Value.set(Param);
                Value.multiply(get(i));
                Total.add(Value);
                Param.multiply(newVar);
            }
            set(Total);
        }
        T   get(int index)  const
        {
            if (index<0 || index>rank()+1)      throw new QiXMath("QiPolynomial::get out of bound");
            return _comps[index];
        }
        void    set(int index, T value)
        {
            if (index<0 || index>rank()+1)      throw new QiXMath("QiPolynomial::set out of bound");
            _comps[index] = value;
        }
        float   evaluate(T x)   const
        {
            int MaxIndex = degree();
            float   Current = 1.0f, Total = 0.0f;
            int i;
            for(i=0; i<=MaxIndex; i++)      {
                Total += Current * _comps[i];
                Current *= x;
            }
            return Total;
        }
        int     degree()    const       //Renvoie le degré du polynôme courant : l'indice du premier coefficient non-nul en partant des puissances élevées.
        {
            int i = rank();
            while (get(i) == 0.0f && i>0)       i--;
            return i;
        }
        void    dump()  const
        {
            int i, Degree = degree();
            for(i=Degree; i>=0; i--)        {
                if (i<Degree && get(i)>=0.0f)       printf("+");
                printf("%.10f", (float) get(i));
                if (!i)     continue;
                if (i==1)   printf("X");
                if (i>1)    printf("X^%d", i);
            }
            printf("\n");
        }
        void    dumpObjects()   const
        {
            int i, Degree = degree();
            for(i=Degree; i>=0; i--)        {
                T   CurValue = get(i);
                if (i<Degree && CurValue>=0.0f)     printf("+");
                if (CurValue != 0.0f)       {
                    get(i).dump();
                    if (!i)     continue;
                    if (i==1)   printf("X");
                    if (i>1)    printf("X^%d", i);
                }
            }
            printf("\n");
        }
        int     rank()  const   {   return _rank;   }
    protected:
        T*      _comps;
        int     _rank;
};

template <class T>
class   QiVector
{
    public:
        //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        class   ExQiVector : public std::exception
        {
            public:
                ExQiVector(char*)       {   }
        };
        //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        QiVector(int rank)      {   _comps = new T[rank];   _rank = rank;}
        ~QiVector()     {   DELETEARRAY(_comps) }
        void    null()  {
            int i;
            for(i=0; i<rank(); i++)     _comps[i] = 0.0f;
        }
        //On crée un vecteur de base
        void    base(int index)
        {
            if (index<0 || index>=rank())       return;
            null();
            set(index, 1.0f);
        }
        //###TODO : faire des exceptions pour les out of bounds.
        bool    set(int index, const T& value)  {
            if (index<0 || index >= rank())     return false;
            _comps[index] = value;
            return true;
        }
        bool    set(QiVector<T>& newValue)
        {
            if (rank() != newValue.rank())      return false;
            int i;
            for(i=0; i<rank(); i++)     _comps[i] = newValue.get(i);
            return true;
        }
        bool    add(int index, const T& value)
        {
            if (index<0 || index>=rank())       return false;
            return set(index, get(index) + value);
        }
        T   get(int index)      const
        {
            return _comps[index];
        }
        QiVector<T>& operator=(const QiVector<T>& original)
        {
            //###TODO : si les rangs sont différents on doit changer le rang de l'objet courant
            if (this != &original && rank() == original.rank())     {
                int i;
                for(i=0; i<rank(); i++)     _comps[i] = original.get(i);
            }
            return *this;
        }
        int     rank()  const   {   return _rank;   }
        void    dump()  const
        {
            int i;
            printf("(");
            for(i=0; i<rank(); i++)     {
                if(i)   printf(", ");
                printf("%f", _comps[i]);
            }
            printf(")\n");
        }
        void    dumpObjects()   const
        {
            int i;
            printf("(");
            for(i=0; i<rank(); i++)     {
                if(i)   printf(", ");
                _comps[i].dump();
            }
            printf(")\n");
        }
    protected:
        T*  _comps;
        int _rank;
};

//Matrice carrée constituée de vecteurs QiVector
template <class T>
class   QiMatrix
{
    public:
        //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        class   ExQiMatrix : public std::exception
        {
            public:
                ExQiMatrix(char*)       {   }
        };
        //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        QiMatrix(int rank)      {   _init(rank);    }
    protected:
        bool _init(int rank)
        {
            _comps = new QiVector<T>*[rank];
            int i;
            for(i=0; i<rank; i++)       _comps[i] = new QiVector<T>(rank);
            _rank = rank;
            return true;
        }
        bool _release()
        {
            int i;
            for(i=0; i<rank(); i++)         {
                DELETESINGLE(_comps[i]);
            }
            DELETEARRAY(_comps);
        }
        void    _count()    const
        {
            _nbUps = 0, _nbLows = 0, _nbDiags = 0;
            int i, j;
            for(i=0; i<rank(); i++)     {
                for(j=0; j<rank(); j++)     {
                    float   Value = get(i, j);
                    if (i>j && Value)       _nbLows++;
                    if (i<j && Value)       _nbUps++;
                    if (i==j && Value)      _nbDiags++;
                }
            }
            //
            _nbItemsInHalf = _rank*(_rank-1)/2 + _rank;
        }
    public:
        ~QiMatrix()     {   _release(); }

        void    null()      {   int i;  for(i=0; i<rank(); i++)     _comps[i]->null();  }
        void identity()
        {
            null();
            int i;
            for(i=0; i<rank(); i++)     _comps[i]->set(i, 1.0f);
        }
        T   get(int i, int j)       const
        {
            if (i<0 || j<0)     return 0.0f;
            if (i>=rank() || j>=rank())     return 0.0f;
            return _comps[i]->get(j);
        }
        QiVector<T>& get(int index) const
        {
            if (index<0 || index>=rank())       return *_comps[0];
            return *_comps[index];
        }
        bool    set(int i, int j, T value)
        {
            if (j<0 || j>=rank())   return false;
            _comps[i]->set(j, value);
            return true;
        }
        bool    setRaw(int setRank, ...)        {
            if (setRank != rank())  return false;
            va_list args;
            va_start(args, setRank);
            int i, j;
            for(i=0; i<rank(); i++)     {
                for(j=0; j<rank(); j++)     {
                    if (!_comps[i]->set(j, (float) va_arg(args, double)))       {
                        va_end(args);
                        return false;
                    }
                }
            }
            va_end(args);
            return true;
        }
        bool    setRow(int index, QiVector<T>& row)
        {
            if (rank() != row.rank())       return false;
            _comps[index]->set(row);
            return true;
        }
        //Multiplication matrice-matrice inplace
        QiMatrix<T>&    operator *= (const QiMatrix<T>& op)
        {
            multiply(op);
            return *this;
        }
        bool    multiply(const QiMatrix<T>& op)
        {
            if (rank() != op.rank())        return false;
            QiVector<T> Temp(rank());
            int i, j, k;
            for(i=0; i<rank(); i++)     {
                for(Temp.null(), j=0; j<rank(); j++)        {
                    for(k=0; k<rank(); k++)     {
                        Temp.add(j, get(i, k) * op.get(k, j));
                    }
                }
                setRow(i, Temp);
            }
            return true;
        }
        //
        QiVector<T> operator * (const QiVector<T>& op)      const
        {
            QiVector<T>     Result(op.rank());
            multiply(op, Result);
            return Result;
        }
        void    multiply(const QiVector<T>& op, QiVector<T>& result)    const
        {
            int i, j;
            for(i=0; i<rank(); i++)     {
                T   Total = 0.0f;
                for(j=0; j<rank(); j++)     {
                    Total += get(i, j) * op.get(j);
                }
                result.set(i, Total);
            }
        }
        //Copy constructor
        QiMatrix(const QiMatrix<T>& original)
        {
            _init(original.rank());
            int i;
            for(i=0; i<rank(); i++)     *_comps[i] = original.get(i);
        }
        bool    isLower()   const
        {
            _count();
            return _nbLows + _nbDiags == _nbItemsInHalf;
        }
        bool    isDiagonal()    const
        {
            _count();
            return _nbDiags == rank();
        }
        //Inverse la matrice courante "inplace"
        void    inverse()
        {
            if (isLower())      {
                //Cas pour les matrices triangulaires inférieures
                QiVector<T> Temp(rank());
                int i, j, k;
                T   Total;
                for(i=0; i<rank(); i++)     {
                    Temp.null();
                    for(j=0; j<=i; j++)     {
                        Total = 0.0f;
                        for(k=j; k<i; k++)      {
                            T   NormalIK = get(i, k);
                            T   InvKJ = get(k, j);
                            Total += NormalIK * InvKJ;
                        }
                        T   DeltaIJ = i == j ? 1.0f : 0.0f;
                        T   MainCoeff = get(i, i);
                        T   InverseCoeff = (DeltaIJ - Total) / MainCoeff;
                        Temp.set(j, InverseCoeff);
                    }
                    setRow(i, Temp);
                }
            }   else    if(isDiagonal())        {
                int i;
                for(i=0; i<rank(); i++)     set(i, i, 1.0f/get(i, i));
            }   else    throw new QiXMath("QiMatrix::inverse : not yet implemented.");
        }

        void    dump()  const
        {
            int i;
            for(i=0; i<rank(); i++)     _comps[i]->dump();
        }
        void    dumpObjects()   const
        {
            int i;
            for(i=0; i<rank(); i++)     _comps[i]->dumpObjects();
        }
        int     rank()  const   {   return _rank;   }
        //
        bool    isUpper()   const;
        bool    isInversible()  const;
    protected:
        QiVector<T>**   _comps;
        int _rank;
        //
        mutable     int _nbUps, _nbLows, _nbDiags, _nbItemsInHalf;
};

Bien se souvenir qu'ici je cherche plus à être exact que rapide, c'est sûr que pour un moteur 3D j'utiliserai les classes QiMatrix et QiVector avec beaucoup de pincettes !!!

Le pays d'une adresse IP


19 août 2007

Obtenir le pays correspondant à une adresse IP

Vous vous souvenez de GeoIp, produit de la société MaxMind ? Ils ont un exécutable à installer sur un serveur pour obtenir le pays correspondant à une adresse IP.

J'avais deux soucis quand j'utilisais ce produit :

  • d'une part j'avais affaire à un binaire dont je n'avais pas les sources, et faire tourner quelque chose d'opaque sur un serveur est une invitation au hack pour des escrocs russes et
  • d'autre part j'étais tributaire de leurs mises à jour des données également opaques.

Tout peut se résoudre en utilisant le site ip-to-country. Leur méthode ? Faire que le pays d'une adresse IP soit obtenu par une simple requête SQL, ce qui donne :

  • qu'il n'y a plus de binaire douteux à installer sur mon précieux serveur de prod
  • et que je bénéficie de toutes les facilités du language SQL et de ses implémentations de mon choix (MySQL et PosgreSQL).

Pour fixer les idées la requête en question est presque aussi simple que celle-ci :

select countryName from ip2Country where \$MonIP<=highLimitIP and \$MonIP>=lowLimitIP;

Malheureusement les opérateurs <= et >= ne fonctionnent pas nativement sur les bases de données entre adresse IPs classiques. On va donc devoir les convertir en adresses IP numériques, c'est-à-dire en simples nombres entiers. Ainsi l'adresse 192.168.1.1 deviendra 3 136 235 777 = 192*2^24 + 168*2^16 + 1*2^8 + 1*2^0.

La source des données

C'est un simple fichier CSV téléchargeable depuis le site principal et régulièrement mis à jour. Voici un extrait pour examiner le format d'une ligne type :

...
"202385408","202385919","PR","PRI","PUERTO RICO"
"202385920","202706431","US","USA","UNITED STATES"
"202706432","202706943","PR","PRI","PUERTO RICO"
"202706944","203197063","US","USA","UNITED STATES"
...

Les deux premiers champs définissent un intervalle d'adresses IP au format numérique (par opposition au format séparé par des points) tel qu'une IP comprise dans cet intervalle est réputée représenter une machine installée dans le pays indiqué par les champs qui suivent. Les trois champs en question sont : le code ISO 3166-1 alpha 2 à deux lettres du pays, son code ISO 3166-1 alpha 3 à trois lettres et son nom complet.

Avant d'insérer les données dans le moteur de base de données, il faut nettoyer le fichier d'entrée pour que MySQL puisse le traiter sans complications :

cat ip-to-country.csv | sed 's/\"//g;s/\r//g' > ip2Country.csv
On élimine les guillemets et \\r

Ensuite, à partir d'un prompt MySQL et avec le fichier csv nettoyé et dans le path, on peut créer la table qui va héberger nos données :

create table ip2Country
    (
        lowIP int unsigned,
        highIP int unsigned,
        code2 varchar(2),
        code3 varchar(3),
        name varchar(60),
        INDEX(lowIP)
    ) ENGINE=INNODB;
Attention : un int ne suffit pas pour les IPs numériques, il faut des int non-signés

On peut terminer cette phase d'installation en important les données du fichier transformé dans la table MySQL que l'on vient de créer avec la commande suivante :

load data local infile './ip2Country.csv' into table ip2Country
    fields terminated by ","
    lines terminated by "\n"
    (lowIP, highIP, code2, code3, name);

Le résultat

Il reste donc l'essentiel et le plus simple à faire : interroger la base de données avec une IP quelconque pour en déduire le pays dans lequel la machine correspondante est installée.

Ainsi, si on utilise PHP on peut donc avoir la fonction suivante et triviale qui renvoie le pays correspondant à une adresse IP passée en paramètre :

function    IPToCountry($IP)
{
    $NumIP = ip2long($IP);      //PHP possède une fonction de conversion pour les adresses IP
    $Result = mysql_query("select * from ip2Country where lowIP<=$NumIP and highIP>=$NumIP;");
    $Result = mysql_fetch_array($Result);
    return $Result[0];
}

Tant qu'on y est, puisque j'aime le Bash, voici un oneliner qui fait la même chose depuis la ligne de commande :

mysql --silent --execute
     "SELECT name FROM ip2Country WHERE lowIP<=inet_aton('$IP') AND highIP>=inet_aton('$IP')"

L'intérêt de cette solution réside donc à la fois dans la simplicité de sa mise en oeuvre et dans son ouverture totale. On a vu qu'en quelques minutes on dispose d'une solution fonctionnelle, duplicable, d'un niveau demandant de faibles compétences techniques et à moindre coût.

Transformation de Burrows-Wheeler


22 juillet 2007

J'avais besoin d'un programme qui réalisait la transformation de Burrows-Wheeler (TBW) sur de simples lignes de texte et non pas sur des énormes fichiers binaires comme c'est le cas d'habitude. J'ai donc pondu le code qui suit :

#include <iostream>

int LineLen;

int Cmp(const void* a,const void*b)
{
    return strncmp(*(const char**)a,*(const char**)b,LineLen);
}

int main()
{
    int i;
    char    *Line=new char[1000], **Rows=new char*[1000];
    while(gets(Line)){
        LineLen = strlen(Line);
        //On utilise un double buffer pour la ligne courante
        memcpy(Line+LineLen, Line, LineLen);
        //Les permutations en utilisant de simples pointeurs
        for(i=0; i<LineLen; i++)        Rows[i]=Line+i;
        //On trie les pointeurs en fonction de leurs données
        qsort(Rows, LineLen, 4, Cmp);
        //On cherche la ligne originale dans la liste triée.
        i=0;
        while (i<LineLen && strncmp(Rows[i], Line, LineLen))    i++;
        int OriginalIndex = i;
        //
        printf("%d\t",OriginalIndex);
        for(i=0; i<LineLen; i++)    printf("%c", Rows[i][LineLen-1]);
        printf("\n");
    }
    delete []Line;
    delete []Rows;
}

pour les données d'entrée suivante :

ABCABC
abracadabra
BurrowsWheelerTransform
gaattcctgggcctggggctgtggcagctgcctcgtccct
tcacctcctggcttattctctccctccatatcttagcaat
ctcatgcctgtaatcccagcattttggtaggccaaggcgg
gtcggatcacctgaggtcaggagttcgagggccagcctga
tgaccatggtgaaaccccatctctactaaaaatacaaaat
taatcgggcatggtggcacatgcctgtaatcccagctact
ctgaggcaggagaatcgcttaaacccaggaagtggaggtt
tcagtgagctgagattgtgccattgcactccagcctgggt
aacaagagcaaaactccatcaaaaaaaataatatatgtat
atatatattacaattttatatatatatacacattatgtaa
taccattttatatatatacattacgtaatggtaaatgttt
gatcgtctccctggagaataatccccaatgtgaaattact
ctaagtggtgggattacaggcgtgtgcccaacttttcctg
agccttttgaggctgacaccagaggtagaagcccagcctc
tccccactggccatgtggggagaggctccagcctgcagca
accagggatctggcctcaagtgatgccccaacagtgggcg
1001110010001111110101011101101110010100
1100111011000100110110010000011011100111
1000100001000001010101101000010110000011
0000000000111111000100100001011010100011
0011011000001111001010010001001011101111
0010110110101011100100010011000000010000
1101011110010100001000111001000100011001
0011001010001001001110100000101001001101
1110110100001001100110001010101001100100
1110001011101110110000110100011011100001

le programme renvoie :

0   CCAABB
2   rdarcaaaabb
0   mrsrhelsWerafreToruwnBo
16  gcagtgctgtccgccgtgtgagtggtgtctgtcccgccca
28  cctctatgtcttcatctctctgagttattcccctacccaa
17  ctctaacccctggctgggcagtggaacttgggcaatctta
31  cccgggggtctgagttcccttgggaacgaagaaagtgccg
37  tacgaaaaatgataccaacccacaatttttgcaccagtaa
31  ttctcaaccgcagctgtgcaggtatgcttggtcaaagacc
17  taggagccggaacgcattggagtggcaataaagtatcgcg
29  cgcgccggctctggagcttattaatgatgtccgtgctgaa
8   caaacaaatacataaagtaatcttgactaaataagaaaca
11  tacttctttttattttcaaaatgtaaaaataataaatata
25  ttatttttttaaccacaatgctggattaaataatatttga
25  ggtcatgaagaacccttcttactagttctatacaggccaa
13  cttacagcacgtggcagtgtgatttgaccttgcgggattc
7   ggctcaccggacctacgggcgcattaaaagaaggcctttc
35  cgccgcccgcgcctgctggcagatagaggtagttcaccga
3   ccagcacggctcacacgggctcgttgggtgataacagacg
21  1111100100111011001010010110111100010110
30  1010101011001100100011011111001110010010
30  1110100100000000001010111001001100000100
0   1000001010101000001010010101000100101110
8   1010101110010001010110010101010110111000
13  1010000010010010001010111100101010001000
35  1101110010011000010001000011101011010100
9   1010011101111110100000000000100010010100
39  1010101111110011000010011100010001000010
36  1110100000101001110111011110011010101000

Je voulais un code qui soit rapide à implémenter mais :

  • la limite de 1000 octets n'est pas terrible pour une routine généraliste.
  • j'utilise qsort qui n'est pas optimal par rapport à mon radix sort pour des données de taille importante.
  • J'utilise gets ce qui est déconseillé !
  • On n'a pas à dupliquer la ligne de données, en compliquant un peu le code ça devrait pouvoir marcher.
  • Le buffer Rows est de trop il faut trouver une astuce pour ne pas l'utiliser il prend une mémoire folle.

Tout ceci sera fixé plus loin, pour l'instant ce qui nous intéresse c'est d'avoir un outil de test à utiliser en conjonction avec d'autres compresseurs maison.

La transformation inverse

Maintenant que l'exécutable précédent (que j'ai appelé bwt) est fait et fonctionne, comment retrouver à partir de sa sortie les données originales ?

Le LZ* le plus intéressant : le LZSS


19 juillet 2007

J'apprécie depuis longtemps l'algorithme de compression sans perte LZSS et j'ai décidé de lui dédier une page de ce site pour l'illustrer et l'implémenter du mieux possible.

Pour faire vite et simple, l'algorithme compresse les données d'entrée en remplaçant des segments de caractères par des références vers des segments identiques déjà rencontrés. Ainsi Fulbert à la position 100 sera remplacé par Ful<25,4> si bert a déjà été rencontré à la position 25. Nous pouvons encoder la référence <position, taille> sur deux caractères, on verra plus tard comment et ainsi éliminer 4 - 2 = 2 caractères, d'où la compression. C'est, on s'en doute quelque chose qui fonctionne très bien pour le texte.

Voici venu le moment d'un exemple de code qui réalise cette compression dans des conditions idéales : on alloue un buffer suffisamment grand pour ne pas se poser la question du bouclage et on ne doit ni sauver les données ni les relire. Le but étant de tester le concept (qui marche depuis 1982 on ne fait donc pas là une grande découverte) et de fournir quelques statistiques :

getMatch(cursor)
    ... recherche ce qui se trouve à partir de la position <cursor> dans le dictionnaire.

store(position, len)
    ...stocke dans le dictionnaire <len> octets des données d'entrées à partir de <position>.

emitSegment(match)      output <match.offset, match.len>
emitChar(c)             output c

main()
{
    cursor = 0
    while (cursor != EOF)
        if (Match = getMatch(cursor))
            emitSegment(Match)
            store(cursor, Match.len)
            cursor += segment.length
        else
            emitChar(cursor)
            store(cursor, 1)
}

Le principe : on lit chaque caractère l'un après l'autre et soit on a déjà rencontré ce qui suit auquel cas on émet un segment, soit on n'a encore jamais rencontré ça et on émet le caractère tel quel. C'est extrèment simple et le code l'est également.

Tout ceci donne, une fois traduit, en C :

char*   Dic = NULL;
int     DicCursor = 0, DicLength = 0, DicStoredLength = 0;

void    addToDictionary(char c)
{
    Dic[DicCursor++] = c;
    DicStoredLength++;
}

bool    searchMatch(const char* strToCode, int cursor, int bufLn, int& longestMatchOffset, int& longestMatchLength)
{
    longestMatchLength = longestMatchOffset = 0;
    int DicPos = 0, i = 0;
    while (DicPos < DicStoredLength)        {
        while (DicPos+i<DicStoredLength && cursor+i<bufLn && strToCode[cursor+i] == Dic[DicPos+i])      i++;
        if (longestMatchLength<i)       {
            longestMatchOffset = DicPos;
            longestMatchLength = i;
        }
        DicPos++;
        i = 0;
    }
    return longestMatchLength != 0;
}


void    outputChar(char c)              {   printf("%c", c);    }
void    outputCode(int offset, int ln)  {   printf("<%d, %d>", offset, ln);     }

int main(int argc, char *argv[])
{
    DicLength = 2048;
    FILE*   FileToCode = fopen("../../config.h.in", "r");
    if (!FileToCode)        return EXIT_FAILURE;
    fseek(FileToCode, 0, SEEK_END);
    long    FileSize = ftell(FileToCode);
    char*   ToCode = new char[FileSize];
    rewind(FileToCode);
    fread(ToCode, 1, FileSize, FileToCode);
    fclose(FileToCode);
    //
    Dic = new char[DicLength];
    int Ln = FileSize;
    int i = 0, EncodedSize = 0;
    int NbRawChars = 0, NbBlocks = 0;
    int HeaderSize = 3, j;
    while (i<Ln)        {
        int MatchOffset, MatchLength;
        char    c = ToCode[i];
        if (searchMatch(ToCode, i, Ln, MatchOffset, MatchLength) && MatchLength>2)      {
            outputCode(MatchOffset, MatchLength);
            for(j=i; j<i+MatchLength; j++)      addToDictionary(ToCode[j]);
            i += MatchLength;
            EncodedSize += 2;
            NbBlocks++;
        }   else    {
            outputChar(c);
            i++;
            EncodedSize++;
            NbRawChars++;
            addToDictionary(c);
        }
    }
    delete []Dic;
    printf("\n");
    printf("Taille originale : %d\n", Ln);
    printf("Taille compressée hors header et flags : %d\n", EncodedSize);
    printf("Nombre de caractères émis de façon brute : %d\n", NbRawChars);
    printf("Nombre de blocs <offset,ln> : %d\n", NbBlocks);
    int TotalPackedSize = EncodedSize + HeaderSize + (NbRawChars>>3) + 1;
    printf("Taille totale compressée : %d\n", TotalPackedSize);
    printf("Ratio : %.3f %%\n", 100.0f * TotalPackedSize / Ln);
    return EXIT_SUCCESS;
}

Voyons ce que ça donne pour plusieurs sources d'entrée :

Taille originale : 35147
Taille compressée hors header et flags : 11621
Nombre de caractères émis de façon brute : 1933
Nombre de blocs <offset,ln> : 4844
Taille totale compressée : 11866
Ratio : 33.761 %", "Source : <a href='http://www.gnu.org/licenses/gpl-3.0.txt'>GPL v3</a>
Taille originale : 702748
Taille compressée hors header et flags : 174968
Nombre de caractères émis de façon brute : 3628
Nombre de blocs <offset,ln> : 85670
Taille totale compressée : 175425
Ratio : 24.963 %

Vous remarquerez que la taille compressée est inférieure de 80ko au fichier Zip référencé sur le site du Projet Gutenberg. C'est un bon début :)

Bien sûr tout ça n'est pas très sérieux : ça prend un temps fou (la méthode de comparaison est risible, au moins 3 minutes pour Pride and Prejudice...), le buffer s'adapte aux données d'entrées (je préfèrerai qu'il soit fixe) et il n'y a toujours pas de sauvegarde des données pour vérifier que ça fonctionne dans les deux sens. Mais ça n'est pas grave, c'est la première version et on a vérifié que le code est faisable (ouf c'était dur) (je plaisantais dans la dernière parenthèse, on est d'accord hein ?).

La première optimisation

En rajoutant trois petites lignes à la recherche on divise par 3 le temps passé dans la routine. Ces lignes sont là pour passer sur un caractère s'il n'est pas égal au premier recherché :

bool    searchMatch(const char* strToCode, int cursor, int bufLn, int& longestMatchOffset, int& longestMatchLength)
{
    longestMatchLength = longestMatchOffset = 0;
    //Recherche naïve
    int DicPos = 0, i = 0;
    while (DicPos < DicStoredLength)        {
        char    CharToLookFor = strToCode[cursor];
        while (DicPos<DicStoredLength &&  Dic[DicPos] != CharToLookFor)     DicPos++;
        i=1;
        while (DicPos+i<DicStoredLength && cursor+i<bufLn && strToCode[cursor+i] == Dic[DicPos+i])      i++;
        if (longestMatchLength<i)       {
            longestMatchOffset = DicPos;
            longestMatchLength = i;
        }
        DicPos++;
        i = 0;
    }
    return longestMatchLength != 0;
}

Deuxième optimisation : hash table et listes chaînées

Tout le monde connait le concept et l'intérêt des Hash Table, et bien pour le LZSS c'est impressionnant d'intérêt. Si on cherche une chaîne dans le dictionnaire on peut parcourir ce dernier comme précédemment ou bien demander à une fonction "donne-moi les emplacements du dictionnaire qui contiennent telle lettre". Plus de parcours ! On va directement au bon endroit. La lettre en question s'appelle la clé (de la requête).

Bien. Mais quelle est la structure de donnée qui permet de poser cette question efficacement, comprendre rapidement (en O(1) si possible) ? Et bien c'est une Hash Table, dont les clés sont les premières lettres hashées, combinée avec des listes chaînées contenant des pointeurs vers les emplacement dans le dictionnaire.

Tout ça économise énormément de temps sur la recherche d'un segment du dictionnaire intéressant mais c'est optimisable : il suffit non plus d'utiliser la première lettre mais plusieurs :) En fait je suis arrivé à une version qui utilise les 4 premières lettres des données d'entrées, les combine en un nombre qui représente un index dans ma Hash Table pour parcourir une liste de cellules chaînées pour trouver mon segment le plus intéressant. Les résultats ?

Un résultat intermédiaire m'a donné pour Pride & Prejudice 102 secondes pour une recherche naïve (qui utilise tout de même la première optimisation) et 3.37sec pour la version "Hash Table" avec un buffer illimité.

Si on est maintenant prêt à oublier un peu le taux de compression pour privilégier la vitesse d'encodage, en limitant la taille du dictionnaire à 32768 octets on passe à 13.7 secs pour la version naïve et à 0.27 secs pour la version utilisant une hash table.

Rien à dire ça commence à être praticable...

Reste à présent à implémenter la sérialisation (la sauvegarde et la relecture) et à améliorer l'occupation mémoire parce que pour arriver à presque 1/4 de seconde j'ai créé plein de choses dans la RAM du PC...

La moralité : quand on constate que j'ai un facteur 1000 entre cette optimisation et la recherche naïve on se dit que l'algo le plus intéressant de recherche de chaîne de caratères ne pourra jamais battre une indexation à 4 caractères ! Dommage, parce que ça veut dire que Jalut écrase Dāwūd, mais c'est logique. D'un autre côté si quelqu'un est arrivé à faire quelque chose avec KMP ou Boyer-Moore ça m'intéresse !

La suite...

on décode des données sauvées On compare toujours les temps des différentes méthodes pour savoir où l'on en est. L'usage de l'algo ? On utilise des fichiers de différents types : wav, dwg, txt & cpp, images raw. Les améliorations : - taille variable du stockage des segments (1, 2 ou 3 octets). - on sauve séparément les flux de caractères, de bits de contrôle et de segments (position et taille séparément également). - on compresse à nouveau les flux différemment en fonction de leurs contenus - stockage définitifs des segments à partir d'un certain seuil (ils ne sont plus supprimés du dico mais déplacés ailleurs)

1 2 3..... 9 10 11 12 13 14 15 16 17 18 19 20