Flib v3.4 - Page 2

Je l'ai dit pas mal de fois, notamment ici

J'utilise des tables de hachage pour indexer les fonctions de la lib et gagner en rapidité d'execution.
Tu peux aussi voir directement le code
Si t'as des questions je t'écoute

#maman#

A propos comment on fait une table de hachage en statique ? (flemme de regarder le code )

Hum ben tu crée un tableau de pointeurs sur les fonctions à appeller, pis tu te fais une fonction de hachage qui va bien et pis ben tu calcule le hash du nom de chaque instruction et tu saute directement à la bonne fonction grace à cette valeur.

La difficulté consiste en une bonne fonction de hashage bien entendu.
J'espère que j'ai été clair ^^

Comment éviter les collisions, sans pour autant avoir un tableau immense ?

k, merci
Alors c'est quoi ta fonction magique FpgForce ?

MD5 ?

Oula non pas de MD5

Alors moi j'ai utilisé la technique du flemmard en fait, j'ai d'abord tatonné pour essayer de construire la fonction de hachage à la main et finalement c'est super dur, surtout quand le nom des fonctions n'a pas été prévu à l'avance pour cet algo. J'ai donc utilisé un outil qui sert normalement pour les compilateurs / interpreteurs: gperf, qui génère des fonctions de hachage "parfaites".

Vous trouverez plus d'infos ici:
http://www.gnu.org/software/gperf/gperf.html

J'ai passé pas mal de temps à jouer sur les options du programme pour arriver à un tableau acceptable, j'ai modifié un peu le code résultant et vala:

la fonction:

unsigned int
hash (register const char *str, register unsigned int len)
{
	static const unsigned char asso_values[] =
	{
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51,  1, 51,  0, 51, 51, 51, 51,
		18, 51, 51, 51, 51, 51, 51, 51, 25, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 13, 11,  0,
		15,  9,  0,  8, 15,  1, 51, 14,  2,  8,
		 2, 14,  7, 51,  1,  0,  1, 51,  6,  7,
		22,  5, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
		51, 51, 51, 51, 51, 51
	} ;
	register int hval = len ;

	switch (hval)
	{
		default:
			hval += asso_values[(unsigned char)str[4]] ;
		case 4:
		case 3:
			hval += asso_values[(unsigned char)str[2]] ;
		case 2:
		case 1:
			hval += asso_values[(unsigned char)str[0]] ;
		break ;
	}
	return hval ;
}

Le tableau de pointeurs:

	void (*fctlist[])(unsigned short *, char *, char *, SCR_RECT, short *) =
	{
		dummy,
		minus,
		plus,
		dummy, dummy, dummy,
		slclr,
		fclrscr,
		slrcl,
		sprite,
		rclscr,
		filltri,
		fillrect,
		savscr,
		savpic,
		version,
		picsize,
		foff,
		fillpoly,
		map,
		msg,
		mkpic,
		slmsg,
		setcont,
		pretty,
		gray,
		ellipse,
		initdelay,
		delay,
		pinfo,
		getcont,
		frect,
		font,
		pix,
		line,
		plane,
		drawstr,
		drawstrv,
		wait,
		keywait,
		keylow,
		busy,
		breakoff,
		width,
		beep2,
		dummy,
		pixtest,
		dummy, dummy, dummy,
		beep
	} ;

Oui mais si on met un nom de fonction qui n'existe pas, ça donne quoi ?

(sauf erreur, le mot-clef register est inutile si tu ne précises pas le nom du registre en question avec TIGCC)

Godzil> ben ça appelle une fonction du tableau si son hash matche, c'est un effet secondaire des tables de hachage.
Ximoon> ok je prend note ^^

Bref, aucun moyen de savoir si l'utilisateur fait n'importe quoi

ben non

(je te rassure je découvre pas les hash table hein ^^)

Au moins ça a un avantage, ça plante pas si l'utilisateur fait n'imp ^^


A la limite ça pourrait etre interessant de savoir quelles sont les collisions les plus courtes poru les fonctions normales, comme ça on pourrais avoir des raccourcis utiles ^^

Ouai et puis ça le force à bien apprendre la syntaxe

Tu entend quoi par collision courte ?

la chaine la plus courte possible qui aurait la même clé de hachage qu'une fonction utile, pour économiser de la place ds l'appel à FLib, j'imagine

tres bonne vormulation de Zephyr ^^

ok merci
Ben en effet ça pourrait être sympa, mais vaut mieux eviter sachant que si on rajoute ou on enlève une fonction de la lib ya de grandes chances pour que la table et la fonction de hachage change aussi, donc que les raccourcis ne marchent plus.

Ouais, perso je dirais que c'est une assez mauvaise idée, parce que tu vas forcément te retrouver avec plein de programmes qui appellent des fonctions inexistantes, et il va falloir garder la rétrocompatibilité... (enfin ça peut tjs faire des possibilités d'obfuscation intéressantes, "déshabiller pingouin ministériel" correspond à "drawstr pinfo minus" )

Par contre ce que tu peux faire, c'est avoir une table des noms de fonctions et vérifier par la suite que la fonction que tu as trouvée correspond bien aux entrées de la table... Mais évidemment si le but était de gagner de la place et pas juste de la vitesse, c'est foutu (ou alors tu peux faire une fonction un peu moins sûre qui vérifierait juste un hash 32 bits du nom de la fonction)

Mouarf pour l'obfuscation

Vui je comptais gagner vitesse + place donc pour la verification avec un tableau de chaines ça va pas être top ^^
Pour la vérification par le hash 32bit ça serait une idée en effet

Godzil :
....#
Au moins ça a un avantage, ça plante pas si l'utilisateur fait n'imp ^^
....

Normallement c'est pas possible que ca plante puiqu'il doit verivier que le hash est dans un intervalle.
Apres si tu appelles une fonction avec des arguments invalides, c'est a la Librairie de gerer ca.

FpgForce ->

Donc pour les arguments, rien n'a change ; avec FliB , ca se passe toujours dans des chaines.

Si ce que tu cherches c'est l'optimisation taille :
- évite les tableaux de pointeurs vers des fonctions, utilise plutôt un switch, ça sera nettement plus petit, quand bien même l'overhead lié au fait d'écrire une fonction serait nul (ce qui est loin d'être le cas)
- asso_values est gigantesque, étant donné que l'ensemble de tous les noms fait 279 octets (c'est bien ça ?) ça ne vaut peut-être pas le coup d'avoir un truc aussi énorme (enfin on peut restreindre à l'ensemble des valeurs utiles, bien sûr, mais ça rajoute encore en taille)
- si le total fait bien 279 octets, même un hash 32 bits pour vérifier serait trop gros (la fonction de hash + 172 octets puisque tu as 43 fonctions, on va pas être loin de 279)
- tu gagnerais plus en faisant perdre 4 octets au code de chaque fonction qu'en essayant de te débarrasser à tout prix de la liste des noms de fonctions

Je vais rajouter un tableau avec le nom des fonctions pour vérifier que la fonction appellée est la bonne.

./45 > un des paramètres pris en compte par sa fonction de hachage étant la longueur de la chaîne, tu risques pas de pouvoir abréger, de toute façon ^^

Meme si la longueur est prise en compte, ta fonction sort une valeur, donc tu obtiendra toujours des collisions

Sally> ben si, une fonction de 4 caractères peut être exprimée en 3, et une fonction de 10 caractères en 5 ^^ (et puis si t'es vraiment motivé, étant donné que seuls les caractères pairs comptent tu peux te débrouiller pour interlacer deux suites d'instructions [une sur les caractères pairs, une sur les caractères impairs] )

Ah oui j'avais pas lu en détail ^^

Un peu de nouveau, j'ai recodé la méthode de selection d'une fonction en utilisant une fonction de recherche dichotomique réccurente, on y perd un peu en vitesse mais on économise pas mal en taille par rapport à la hash map, je pense que c'est un bon compromis.
Si vous avez des suggestions/remarques