Posts filed under 'Programmation'
Avant hier un ami m’a filé un lien sur wikipedia expliquant la compression JPEG. J’ai trouvé ça plutôt amusant, et je me suis dit que ça serait rigolo de faire un format de compression d’images. Alors j’ai cherché un concept à appliquer, et puis je me suis souvenu d’un truc que j’avais pensé entre deux baillements pendant un cour de signal : admettons qu’on veuille stocker 15 valeurs comprises entre 1000000 et 1000100. Soit on stocke bêtement les chiffres, ce qui demande un entier de 16 bits pour chaque valeur, soit prend en compte le fait que toutes les valeurs sont supérieures à 1000000, et qu’on aura que 100 valeurs différentes au maximum. Donc il suffit de dire au début qu’on a un offset de 1000000 (donc là un entier de 16 bits), puis on peut stocker le reste avec du 8 bits. Donc pour nos 15 valeurs, on aurait 15 * 16 = 240 bits, ou alors 16 + 15*8 = 136. On a vite fait de voir qu’il y a un gros gain de place.
Donc je me suis dit qu’on pouvait appliquer un peu le même principe aux images : on découpe l’image en carrés de 8 pixels de côté, on passe l’image en HSV, puis on regarde le minimum et le maximum de chaque composante. Ensuite pour chaque pixel on calcule le pourcentage de chaque composante entre le min et le max : par exemple si on a une teinte entre 130 et 140, et que la valeur du pixel c’est 133, alors ça nous donne 30%. Ce pourcentage on peut l’encoder sur 3 bits (2 bits pour la saturation), ce qui permet de rentrer les 3 composantes sur 1 octet. Si on a de la chance et que l’écart entre le min et le max est faible, alors on peut restituer une couleur assez fidèle (sinon on a un bel artefact).
Avec cette technique, on a une moyenne de 1,2 octet/pixel, ce qui reste 10 fois plus que le JPEG, mais bon…
Pour ceux que ça intéresse, voici les “specs” du format de fichier, c’est complètement à l’arrache, comprendra celui qui pourra 
Trame du fichier
3 octets : "im1"
1 octet : version du standard
n octets : données insignifiantes
2 octets : 2x caractère nul
4 octets : taille x ( nombre de blocs b(x) = int((x+7)/8) )
4 octets : taille y ( nombre de blocs b(y) = int((y+7)/8) )
6+64 octets : bloc [b(x)⋅b(y)]
1 octet : hue min
1 octet : hue max
1 octet : saturation min
1 octet : saturation max
1 octet : value min
1 octet : value max
1 octet : pixel [8⋅8]
3 bits : scaled hue
2 bits : scaled saturation
3 bits : scaled value
Note : pour ce qui est des blocs au bord de l’image, ils ne font pas 8×8 mais s’arrêtent au bord (ce qui influe sur la taille du bloc).
Et puis comme je suis sympa j’ai même fait un programme qui permet de créer/voir/exporter des images au format im1 (abrégé de entroptymisator image 1), que vous pouvez télécharger en cliquant là, mais je vois préviens : c’est la première fois que je fais du C++, et c’est développé vite et à l’arrache, donc le code est assez ignoble et pas toujours commenté. J’ai fait une tentative d’indépendance au boutisme, mais j’ai eu la flemme d’aller jusqu’au bout, alors pour l’instant les images petitboutistes marcheront pas sur les systèmes grandboutiste et inversement, mais ça changera peut être un jour. Question librairies utilisées, c’est GD et SDL, donc ça devrai se compiler sans soucis sous windows, même si je n’ai testé que sous linux. D’ailleurs voici le fichier binaire pour linux 32 bits.
Et puis quand même, ce que vous attendez tous, c’est à dire un joli comparatif :
August 29th, 2008
Dans un monde où on utilise de plus en plus d’outils de recherche, dans différentes langues, il est important de pouvoir trouver ce que l’on cherche même si on n’utilise pas exactement la bonne orthographe du mot que l’on cherche. Face à ce genre de problèmes, on a vu l’apparition de certains algorithmes, comme le Soundex, qui commence à dater et est loin d’être parfait. C’est pour ça que le Metaphone a été créé, sauf qu’il ne comprend que l’anglais (tout comme le Soundex d’ailleurs), alors l’algorithme a évolué et donné naissance au Double Metaphone qui lui prend en compte les différents langages (principalement l’anglais, les langues slaves, germaniques, celtiques, le grec, le français, l’italien, l’espagnol, ou le chinois) de manière intelligente et qui permet de faire des rapprochements entre des chaines.
Comment ça marche ? C’est relativement simple (dans l’idée, par ce que en pratique c’est loin d’être le cas, d’ailleurs je crois que Lawrence Philips, l’auteur du double metaphone, mérite que la communauté du web se cotise pour lui rembourser ses frais en aspirine) : à partir des combinaisons de lettres et de leur fréquence (si je vous écris “verwandelt” vous vous doutez bien que c’est germanique) en peut savoir le genre de prononciation que ça a, ensuite il ne reste qu’à appliquer des règles sur la prononciation (”ba” se prononce presque comme “bha”), ce qui permet de créer une clef (en fait 2 dans le cas du double metaphone). Deux mots ayant la même prononciation auront la même clef.
On peut trouver diverses implantations de cet algorithme dans différents langages, dont celle ci en PHP.
March 14th, 2008
Comme j'en avais marre de devoir constament verrifier si les chemins avec lesquels je travaillais finissaient oui ou non par "/", j'ai décidé de faire une classe pour gérer ça de la manière la plus simple possible. Vous pouvez télécharger cette classe aux formats 7zip, Bzip2 ou Zip.
Voici l'exemple d'utilisation que j'ai fait :
PHP:
-
<?php
-
// First of all, we need to include the class
-
require_once "class.path.php";
-
-
// Then we'll create a new path, with all options
-
// In order, the options are : the path string, is the path pointing a
-
// directory, is there some string to put before the path, and what is the
-
// separator ?
-
$path = new Path("/some/path/to/test/", true, "http://", "/");
-
-
// Obviously, I want to output an URL, just look
-
echo "It's looking like an URL: $path\n";
-
-
// Now I create a new path with a completely different delimiter
-
$path2 = new Path("\a\file.php", false, null, "\\");
-
-
// And I can just append it to the previous one
-
$path->a($path2);
-
// We could have done $path->b($path2), but it would have returned a new object
-
// with $path2 appened instead of changing $path
-
-
// And turn this into a SMB share
-
$path->setHead("\\\\");
-
$path->setSeparator("\\");
-
echo "Now it's a SMB share: $path\n";
-
-
// You can also use new basename() and dirname()
-
// Note that dirname() returns a Path and not a string
-
echo "The parent directory is: " .
$path->
dirname() .
"\n";
-
echo "The pointed file is: " .
$path->
basename() .
"\n";
-
echo "But without its extension it would be: " .
$path->
basename(".php") .
"\n";
-
?>
March 12th, 2008
Voici une fonction écrite en D qui dit si oui ou non la chaine soumise en entrée est un code EAN correct : on verrifie le nombre de caractères, que tout les caractères sont bien des chiffres, et on regarde que la checksumm est bien la bonne.
C:
-
bool eanCheck(string ean) {
-
int summ = 0;
-
-
if(ean.length != 13 && ean.length !=8) return false;
-
-
int n = ean.length - 1;
-
for(int i=0; i<n; i+=2) {
-
if (ean[i] <48 || ean[i]> 57) return false;
-
summ += ean[i] - 48;
-
}
-
for(int i=1; i<n; i+=2) {
-
if (ean[i] <48 || ean[i]> 57) return false;
-
summ += 3 * (ean[i] - 48);
-
}
-
-
summ = 10 - (summ % 10);
-
-
if (summ == ean[n] - 48) return true;
-
else return false;
-
}
Note: pour fonctionner, ce programme requiet une entrée dans un charset compatible ASCII (iso-8859-* ou utf-8 par exemple)
March 6th, 2008
En cherchant à faire ce que j'ai marqué dans le titre de ce billet, je suis tombé sur ce howto qui me semble assez complet :
--> http://www.dwheeler.com/program-library
November 29th, 2007
Prenons la création d'un jeu : les studios du jeu doivent générer les textures, modèles 3D, etc... Ceci présente 2 inconvégnants : ça prend de la place sur le disque dur, et en plus on ne peut pas modifier ces modèles à la volée. On a donc inventé la génération procédurale, qui consiste à générer les données à partir de formules mathématiques et d'algorithmes au lieu de se baser sur des données pré enregistrées. Sans rentrer dans les détails (que vous trouverez sur wikipedia par exemple), je peut vous dire que cette technique donne des résultats assez impressionant : j'ai en tête l'incroyable .kkrieger, qui est un FPS complet d'une taille totale de 96ko !
Bluffant non ? À noter que l'outil qui leur sert à générer les textures et les modèles 3D est distribué gratuitement par le groupe ayant créé krigger (.theprodukkt).
November 10th, 2007
Dans des temps anciens et reculés, avant l'apparition du micro ordinateur personnel, il vivait un mathématicien du nom de Turing qui inventa la machine de Turing (comme c'est original vous ne trouvez pas ?). Cette machine se compose d'un ruban magnétique d'une longueur indéfinie (on suppose que quand on arrive au bout on peut l'allonger) et comportant des cases contenant la valeur d'un entier. Turing a démontré qu'il est possible d'adapter n'importe quel alogrithme pour sa machine. Il a par ailleurs été démontré que nos ordinateurs actuels sont équivalents à cette machine de Turing, ce qui leur confère aussi cette capacité d'executer n'importe quel algorithme. Enfin bref, de nos jours les ordinateurs utilisent des concepts bien plus évolués que la machine à ruban de Turing, ce qui fait que personne ne s'y est jamais intéressé... Sauf le suisse Urban Müller qui a inventé un langage de programmation qui permet de programmer un ordinateur comme on programmerai une machine de Turing. Ce langage est probablement le plus simple au mondre syntaxiquement parlant : il n'y a que 8 opérateurs :
- > déplace le ruban vers la droite
- < déplace le ruban vers la gauche
- + incrémente la case
- - décrémente la case
- [ début de la boucle
- ] fin de la boucle
- . affichage du carractère correspondant au numéro dans la case
- , demande d'un caractère à l'utilisateur et insertion de son numéro dans la case
Voici un exemple de programme (un hello world pour un peu d'originialité)
>+++++++++[<++++++++>-]<.>+++++++[
<++++>-]<+.+++++++..+++.>+++++++++
++++[<------>-]<-.>+++++++++++[<++
+++>-]<.>++++++[<++++>-]<.+++.----
--.--------.>+++++++++++[<------>-
]<--.+.>++++++++[<+++++++>-]<+++.>
++++++[<+++>-]<.
Vous pouvez d'ailleurs utiliser mon générateur de chaine (à utiliser depuis un shell linux). Pour de l'aide sur l'usage du convertisseur utilisez l'option -h.
Pour un complément d'informations, vous pouvez aller voir sur wikipedia ou alors sur ce très bon tutorial.
Bien qu'il existe un compilateur brainfuck, il est largement plus simple de l'interprêter. Sous linux, j'utilise le logiciel "bf" qui remplis parfaitement cette tâche et qui est intégré aux paquets ubuntu.
Sur ce, bon niquage de cerveau ! (c'est garanti si vous essayez de faire un programme un brin complexe...)
October 22nd, 2007
Voici un slide d'excellent conseil sur l'optimisation en PHP. Il regorge de tout un tas de tests que j'ai toujours voulu faire et que j'ai toujours eu la flemme de faire...
http://ilia.ws/files/phptek2007_performance.pdf
October 7th, 2007
Youpi J'ai gagné =D
October 1st, 2007
Les Easter Eggs (oeufs de pâques) ne se trouvent pas que le matin de Pâques dans le jardin : si on cherche bien, on peut en trouver dans certains applications telles que Firefox, Open Office ou Aptitude. Il s'agit la plupart du temps d'une blague, ou d'un mini jeu, comme dans Open Office. Voici donc une liste non exhaustive de ce que vous pourrez trouver :
Mozilla/Firefox
Au fil des versions de Mozilla et/ou Firefox, les développeurs ont pris soin d'écrire une "Bible" de Mozilla, dont un nouveau verset est ajouté à chaque version majeure. Pour lire le verset de votre version, tapez about:mozilla dans la barre d'addresse, et validez.
Apt-get et Aptitude
Les deux gestionnaires de paquet font décidément tout pareil... Même dans les easter eggs Il existe une opération non documentée et pourtant implémentée dans chacun des deux. Pour vous en convaincre, tapez dans un terminal :
apt-get moo
La même opération est possible sous aptitude, mais comme aptitude fait toujours mieux les choses, leur moo se déroule en plusieurs étapes. Pour l'étape 1 :
aptitude moo
L'étape 2 :
aptitude -v moo
L'étape 3 :
aptitude -vv moo
Et ainsi desuite jusqu'à ce que le message arrête de changer.
Note: testez le moo d'apt-get sous différentes distributions, il n'est pas le même partout !
PHP
Et oui, PHP posède aussi son (ou plutôt ses) Easter Eggs. Pour cela il suffit d'ajouter une variable dans l'URL de n'importe quel site fait en PHP. La variable en question c'est ?=PHPE9568F36-D428-11d2-A769-00AA001ACF42 ou ?=PHPB8B5F2A0-3C92-11d3-A3A9-4C7B08C10000 (les deux affichent quelquechose de différent). Par exemple, on passe de http://hyperthese.net/ à http://hyperthese.net/?=PHPB8B5F2A0-3C92-11d3-A3A9-4C7B08C10000
OpenOffice.org
Pour finir ce petit listing des Easter Eggs, voici celui d'OOo qui je crois mérite la palme du plus gros. Dans un premier temps, ouvrez un classeur. Dans une cellule, tapez =game()
Une fois validé, vous obtenez un joli message dans la cellule :
Là il ne vous reste plus qu'à rééditer la cellule, puis à appuyer sur "entrée"
Il parraitrait que ce n'est pas le seul je, visiblement vous pouvez aussi tester "Froggle" et "TicTacToe" mais personellement je n'ai jamais eu aucun résultat....
The End
Et voici donc la fin de cette petite liste... N'hésitez pas à faire tourner google, car il y a fort à parier que votre logiciel favoris posède son easter egg ! 
September 18th, 2007
Previous Posts
