J’ai décidé de faire un nouveau blog, en anglais cette fois ci. Ce blog-ci s’est donc fait remplacé, et a changé d’adresse. Il restera disponible mais ne sera plus mis à jour.
Rendez vous sur http://hyperthese.net/ pour la suite 
Leave a Comment October 9, 2011
Dans mon école, les 1ère année doivent coder un projet de C qui consiste à chercher des anagrammes dans un texte. Outre le fait que j’ai depuis longtemps passé la 1ère année et rendu mon projet, je m’amuse régulièrement à le re-coder pour aider les petits nouveaux ou encore pouvoir si je ferais mieux que la dernière fois.
Entre temps, j’ai découvert une librairie assez géniale, la APR (Apache Portable Runtime de son petit nom). Elle est à la base du serveur web bien connu, et propose des fonctions très intéressantes. Pour résumer grossièrement, il s’agit d’une libc améliorée, disponible sur plusieures plateformes (Linux, *BSD, Windows par exemple). Elle a comme avantage de proposer des fonctionalités plus poussées que la libc de base, comme des mmap, des threads, ou des hashtables. Mais surtout, elle a un mécanisme de gestion de la mémoire par pools très efficace, en ce sens qu’elle permet de n’oublier aucun free, ou encore d’avoir un équivalement de sprintf qui alloue tout seul la chaîne de destination.
Donc l’idée c’était de re-coder mon bidule de B23 (le projet des 1ère années) en utilisant cette librairie pour voir ce que ça donnerait. Et au passage j’ai cassé quelques consignes pour gagner un chouilla en perfs quand même. Assez bavardé, le code :
/***
* B23 Anagrams
*
* Author: Rémy Sanchez <remy.sanchez@hyperthese.net>
* Licence: WTFPL
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <ctype.h>
#include <apr-1.0/apr_general.h>
#include <apr-1.0/apr_pools.h>
#include <apr-1.0/apr_file_info.h>
#include <apr-1.0/apr_mmap.h>
#define apr_assert(expr) if((expr) != APR_SUCCESS) abort();
struct word {
char *orig;
char *sort;
size_t len;
};
typedef struct word word_t;
struct anagram {
char *word;
size_t len;
apr_array_header_t *l;
};
typedef struct anagram anagram_t;
struct dictionary {
struct anagram a;
struct dictionary *left;
struct dictionary *right;
};
typedef struct dictionary dictionary_t;
/*
* Returns the minimum between a and b
*/
size_t min(size_t a, size_t b) {
return (a < b) ? a : b;
}
/*
* mmap the specific file
*/
void map_to_mem(const char *file, apr_mmap_t **mem, apr_pool_t *mp) {
apr_finfo_t finfo;
apr_file_t *fd;
// Get file infos
apr_assert(apr_stat(&finfo, file, APR_FINFO_SIZE, mp));
// Open the file
apr_assert(apr_file_open(&fd, file, APR_READ | APR_BINARY, APR_OS_DEFAULT, mp));
// Map the thing
apr_assert(apr_mmap_create(mem, fd, 0, finfo.size, APR_MMAP_READ, mp));
}
/*
* Copy a string while sorting its letters
*/
void sortcpy(unsigned char *orig, unsigned char *sort, size_t len) {
unsigned char min = 0xff, last_min = 0;
size_t idx = -1, last_idx = -1, re_idx = -1, left = 0, right = len;
// For each letter in the destination string
for(size_t i = 0; i < len; i++) {
min = 0xff;
re_idx = -1;
// For each letter in the source string
for(size_t j = left; j < right; j++) {
// "Normalize" the character
char c = tolower(orig[j]);
// If you found a new smallest charcter
if(c > last_min && c <= min) {
min = c;
idx = j;
}
// If you detect a repetition of the previous
// smallest character
if(c == last_min && j < last_idx) {
re_idx = j;
}
}
// Was there a repetition ?
if(re_idx == -1) {
// If the character was in the extremities,
// reduce the boundary of search for next time.
if(idx == left) {
left++;
} else if(idx == right) {
right--;
}
// Copy the caracter to the destination string
sort[i] = min;
// Reset values
last_min = min;
last_idx = idx;
} else {
// Same thing as before, but in the case of a
// repetition
if(re_idx == left) {
left++;
} else if(re_idx == right) {
right--;
}
sort[i] = tolower(last_min);
last_idx = re_idx;
}
}
// It's a C standard string, so finish it with a null character
sort[len] = '\0';
}
/*
* Insert a word into a dictionary.
*/
dictionary_t *tree_insert(dictionary_t *dict, word_t word, apr_pool_t *mp) {
// Don't have to create a node
if(dict != NULL) {
// Compare the given word to this node's word
int cmp = strcmp(dict->a.word, word.sort);
if(cmp > 0) {
// If smaller put left
dict->left = tree_insert(dict->left, word, mp);
} else if(cmp < 0) {
// If greater put right
dict->right = tree_insert(dict->right, word, mp);
} else {
// If identical, then maybe we have found a new
// anagram
int found = 0;
char **arr = (char**)dict->a.l->elts;
// For each element already in the array
for(size_t i = 0; i < dict->a.l->nelts; i++) {
if(!strncmp(arr[i], word.orig, min(word.len, dict->a.len))) {
// We found a matching string,
// so you only have a double
found = 1;
break;
}
}
// No matching word was found
if(!found) {
// Push the word at the end of the
// anagram's list
*(char**)apr_array_push(dict->a.l) = word.orig;
}
}
// Return the dictionary
return dict;
} else {
// A null dictionary was given, so you have to create
// this node
dictionary_t *new = apr_palloc(mp, sizeof(dictionary_t));
// Initialize leaves
new->left = NULL;
new->right = NULL;
// Input basic data
new->a.word = word.sort;
new->a.len = word.len;
// And push current word
new->a.l = apr_array_make(mp, 10, sizeof(char*));
*(char**)apr_array_push(new->a.l) = word.orig;
// Return the new dictionary
return new;
}
}
/*
* Print a tree in a hierarchical manner.
*/
void tree_print(dictionary_t *dict, int n) {
// Print identation
for(int i = 0; i < n; i++) {
printf(" ");
}
// Print current node
printf("- %s\n", dict->a.word);
// Print child nodes
if(dict->left != NULL) tree_print(dict->left, n+1);
if(dict->right != NULL) tree_print(dict->right, n+1);
}
/*
* Print a tree in a flat manner.
*/
void tree_print_flat(dictionary_t *dict) {
// If the dictionnary is null, give up here
if(dict == NULL) return;
// You print data in alphabetical order, so you begin by
// printing what's in the left node.
tree_print_flat(dict->left);
// Only print this node if there is more than 1 word matching
// the anagram
if(dict->a.l->nelts > 1) {
char **words;
words = (char**)dict->a.l->elts;
// Print the sorted word
printf("* %s\n", dict->a.word);
// Print each matching word
for(int i = 0; i < dict->a.l->nelts; i++) {
printf("\t- ");
fwrite(words[i], sizeof(char), dict->a.len, stdout);
printf("\n");
}
}
// And finish by printing what's in the right node
tree_print_flat(dict->right);
}
// Builds the tree from a string
void make_tree(dictionary_t **dict, char *text, apr_pool_t *mp) {
char *start = NULL, was_letter = 0;
size_t len = 0;
do {
if(isalpha(*text)) {
// You are in a word
if(!was_letter) {
// If you were not in a word at the
// previous character, reset values and
// start a new word
was_letter = 1;
len = 0;
start = text;
}
// Increment the string's length
len++;
} else {
// You are not in a letter
if(was_letter) {
// It's the end of a word
// If the word is long enough to be
// intersting
if(len > 2) {
// Allocate the new word structure
word_t *word = apr_palloc(mp, sizeof(word_t));
// Copy what we can
word->orig = start;
word->len = len;
// Allocate the memory for
// sorted string
word->sort = apr_palloc(mp,
sizeof(char) * (len + 1));
// Copy/sort the string
sortcpy(start, word->sort, len);
// And insert the node
*dict = tree_insert(*dict, *word, mp);
}
// You're not in a word anymore
was_letter = 0;
}
}
} while(*(++text)); // Loop for each character
}
/*
* Main function, does the thing
*/
int main(int argc, const char *argv[]) {
apr_status_t rv;
apr_pool_t *mp = NULL;
apr_mmap_t *mem = NULL;
dictionary_t *dict;
char *str = NULL;
// Check input
if(argc != 2) {
printf("%s: analyze a text to find anagrams\n", argv[0]);
printf("Usage: %s FILE\n", argv[0]);
exit(1);
}
// Initialize APR
apr_assert(apr_initialize());
// Create the pool
apr_assert(apr_pool_create(&mp, NULL));
// Map the thing
map_to_mem(argv[1], &mem, mp);
str = mem->mm;
// Do the work
make_tree(&dict, str, mp);
tree_print_flat(dict);
// Cleanup
apr_pool_destroy(mp);
apr_terminate();
// Everything went fine
return 0;
}
Donc ici je n’utilise que la gestion de la mémoire, et les tableaux dynamiques proposés par APR, mais il y a bien sûr une multitude de choses proposées. Comme source d’information, on notera avant tout le site officiel, avec une doc pas trop mal, et on peut aussi s’aider d’un des seuls tutos APR qui existent sur le net.
En bref, APR est magique et très agréable à utiliser, car elle permet d’éliminer les problèmes majeurs du C. De plus, un petit coup d’œil au code d’Apache permettra de remarquer à quel point elle permet d’écrire un code propre et maintenable. Par contre étrangement cette librairie est utilisée par très peu de projets, probablement à cause de la non-communication autour… En tout cas, c’est une librairie que je recommande vivement !
1 Comment June 26, 2011
En ce moment à l’école, on a 2 grands thèmes en parallèle : du signal et de l’informatique. Ça inclu d’enchaîner un cours sur la théorie de l’information avec un cours de javascript. Et comme l’un comme l’autre sont rigolos, j’me suis dit que je pouvais mixer les deux, tant qu’à y être.
Donc, vous avez tous un jour créé une archive autoextractible pour pouvoir faire rentrer tous vos gros fichiers sur une disquette et en plus pouvoir la donner à quelqu’un qui n’a pas winzip sur son PC. L’idée est donc d’appliquer le même principe, mais au Javascript. On sait bien que les fichiers statiques d’un site web sont lourds et qu’il faut utiliser diverses techniques pour leur faire prendre moins de place. Comme bien entendu il serait trop simple et performant d’utiliser la compression gzip du HTTP, je me suis dit qu’il serait assez amusant de créer un générateur de javascript autoextractible.
D’un point de vue performances, j’ai pris comme base le fichier minifié de jquery, qui fait 84kio. Une fois passé à la moulinette il ne pèse plus que 52kio. Le seul problème, c’est qu’il faut environ 200ms pour décompresser le fichier, ce qui est plus que le temps de chargement dans la majorité des cas. De toute façon, c’est un proof of concept, ça n’est pas sensé être utile
D’un point de vue réalisation, on a d’un côté un programme en python qui va prendre le fichier JS à compresser, le mouliner, et générer du code javascript qui une fois exécuté restitue le fichier JS de base. Le plus gros problème aura été un petit gag sur l’incapacité du JS à gérer les chaînes binaires. Du coup, j’ai dû faire un peu de hack… Attention aux âmes sensibles Après, question compatibilité avec les navigateurs, d’après mes tests ça passe très bien. En gros, c’est géré par tous les navitateurs sérieux.
J’ai créé un dépôt github pour mettre le code en ligne. Pour l’instant c’est pas très documenté, mais peut être que ça viendra. Si quelqu’un teste j’suis intéressé d’avoir des retours :-° Si j’ai pas trop la flemme je ferais un setup.py ou peut être même un paquet debian (oh le ouf).
Un petit apperçu vite fait de comment ça s’utilise :
./jsz.py -i tests/jquery-1.5.1.min.js -o out.js
Comprendra qui pourra
Sur ce, il est l’heure pour moi d’aller faire dodo…
Leave a Comment March 27, 2011
Je suis en train de configurer un peu le réseau chez moi, et je vais utiliser comme routeur une carte Alix. Ces petites bêtes ont comme stockage une carte CompactFlash, ce qui est sympa mais pas quand on veut faire serveur. Par exemple, là je m’attaque à la mise en place d’un serveur de mails.
Donc forcément pour ne pas niquer ma carte flash avec mes mails abondants, j’ai acheté un disque dur USB pour y foutre tout le bazar dessus. Donc je fais un joli LVM, je formate tout ça (en XFS si ça intéresse quelqu’un), et je reboot pour tester.
Là, c’est le drame : rien de monté alors que c’est bien spécifié dans le fstab qu’il faut les monter. Pire, un lvscan me dit que mes volumes sont inactifs.
Solution : c’est udev qui fait la détection de disque, mais le fait en mode “non bloquant”, ce qui veut dire que lvm se charge avant que les disques durs USB soient détectés. Petit workaround pour l’occasion, un script /etc/init.d/sleep
#!/bin/sh
### BEGIN INIT INFO
# Provides: sleep
# Required-Start:
# Required-Stop:
# X-Start-Before: lvm2
# Default-Start: S
# Default-Stop: 0 6
### END INIT INFO
if [ "$1" = "start" ]; then
sleep 10
fi
Le tout activé par la commande magique
update-rc.d sleep start S S . stop S 0 6
Et voilà, c’est moche mais mon LVM est monté au boot
Leave a Comment February 13, 2011
Et oui, c’est la fin du monde (enfin, pas celle annoncée en entête de ce blog, une autre encore). Ce matin, les deux dernier blocs d’IPv4 ont été donné !
https://www.apnic.net/publications/news/2011/delegation
Alors maintenant, qu’est-ce qu’il se passe ? Dans 6 mois, les américains n’auront plus d’adresses, notre tour viendra dans 2 ans, et dans 4 ou 5 pour les africains. Globalement, d’ici 3 à 5 ans il sera devenu totalement impossible d’obtenir une nouvelle adresse IPv4. Seule solution : passer à IPv6.
Bon sur cette note joyeuse, je m’en retourne travailler, *+£%#!
Leave a Comment February 1, 2011
J’annonce officiellement le plus gros record de temps mort de ce blog…
Pour ceux que ça intéresse, une petite fonction Python pour retrouver l’IPv4 d’un freenaute à partir de son IPv6 :
import IPy
def free_6rd_to_v4(ip):
return IPy.IPint((IPy.IP(ip).int() >> 68 & 0xffffffff), 4)
Flemme d’expliquer, pour plus d’infos y’a une conf de Free intéressante à ce sujet
Leave a Comment November 25, 2010
J’ai trouvé le très intéressant site http://gs.statcounter.com/
Il propose des statistiques d’usage des navigateurs, que l’on peut facilement recouper en fonction des pays. On a l’habitude de voir les stats françaises ou américaines, mais certains pays moins occidentaux ont des graphes assez particulier… Prennez par exemple le Tajikistan, l’Antarctique, l’Arménie ou encore la Biélorussie, chez qui on voit des graphes pas habituels. Par contre on peut remarquer qu’en règle générale si il y en a un qui ne bouge pas trop, c’est chrome…
Leave a Comment June 14, 2010
Quand on fait un peu de programmation système, on se rend compte que la fonction qui sert à éteindre/redémarrer la machine sous Linux, la fonction reboot(), prends 2 arguments un peu bizarre nommés magic1 et magic2.
La valeur de magic1 est 0xfee1dead, soit feel dead, “se sentir mort”. La valeur de magic2, peut être 672274793, 85072278, 369367448 ou 537993216. La manpage nous informe que ces valeurs ont un sens en hexa… Voyons voir la première : hex(672274793) = 0×28121969. Rien… Ah… Attendez… Oh tiens, 28/12/1969, la date d’anniversaire de Linus ! Les autres dates étant les dates de naissance de ses filles…
Mon regret est que la libc fournisse cette fonction en occultant les arguements magic :’(
Leave a Comment June 5, 2010
Comme vous pourrez peut être le remarquer, sur la page de recherche de Google anglophone, les unités de recherche sont devenue un peu étranges… J’ai fait une petite liste de ce qu’on trouve :
). En l’occurence, j’ai pas réussi à trouver de quelle epoch il s’agit… .(à noter que la plupart des valeurs sont vraiment proportionnelles au temps de recherche)
Leave a Comment April 1, 2010
Tout content avec mon nouveau PC, j’ai pu tester VDPAU sous Debian (mon mplayer vient de debian multimedia). Par défaut, le support est compilé (dans sid), par contre il y a quelques options à régler dans smplayer avant que ça fonctionne.
Déjà, il faut choisir la sortie video “vdpau”, choisir le bon codec pour le fichier dans les infos et propriétés (par exemple ffh264vdpau au lieu de ffh264).
Ensuite, il faut éviter les options pas compatibles. Par exemple les screenshots (pour les désactiver, faire pointer le répertoire de screenshot vers un répertoire qui n’existe pas), ou le postprocessing.
Happy HD
Leave a Comment September 22, 2009
| M | T | W | T | F | S | S |
|---|---|---|---|---|---|---|
| « Oct | ||||||
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | ||||