En fait, l'instruction qui approxime la table n'est pas le compte du nombre de bit mais le compte du nombre de 1 au début de l'octet:
si x est un octet pour 0<= x < 0xfe
on peut calculer les valeurs de la table tres rapidement par count_leading_1(0x80 | x), ce qui doit se traduire sur les archis ayant count_leading_1 par deux/trois instructions assembleurs s'exécutant chacune en un cycle (difficile de faire mieux!).
Le probleme c'est pour associer 1 a 0xfe et 0xff.
En théorie c'est simple:
(x >= 0xfe) || count_leading_1(0x80 | x)
Mais le || par court-circuit n'est pas forcément efficace, c'est la ou je sèche pour trouver une formule efficace de manière "portable" (enfin efficace pour les archi qui ont count_leading_1, je ne sais pas si elles ont toutes CMOV)..
J'avais envisagé aussi count_leading_1(0x81 | x) %7 mais le modulo ce n'est pas efficace non plus.
count-leading-1 (ou count-leading-0, c'est la même chose a un non-binaire pres) existe sur PPC, ARMv5+, MIPS32, Alpha avec CIX, mais pas les x86 mais bon "x86 sucks" comme d'habitude :-(
Voila, c'est de mémoire, je ne garanti pas qu'il n'y ait pas d'erreur..
Tu peux m'envoyer un mail si tu veux discuter du sujet.
[^] # Re: Bravo mais..
Posté par reno . En réponse à la dépêche La quintessence des algorithmes bit à bit. Évalué à 3.
si x est un octet pour 0<= x < 0xfe
on peut calculer les valeurs de la table tres rapidement par count_leading_1(0x80 | x), ce qui doit se traduire sur les archis ayant count_leading_1 par deux/trois instructions assembleurs s'exécutant chacune en un cycle (difficile de faire mieux!).
Le probleme c'est pour associer 1 a 0xfe et 0xff.
En théorie c'est simple:
(x >= 0xfe) || count_leading_1(0x80 | x)
Mais le || par court-circuit n'est pas forcément efficace, c'est la ou je sèche pour trouver une formule efficace de manière "portable" (enfin efficace pour les archi qui ont count_leading_1, je ne sais pas si elles ont toutes CMOV)..
J'avais envisagé aussi count_leading_1(0x81 | x) %7 mais le modulo ce n'est pas efficace non plus.
count-leading-1 (ou count-leading-0, c'est la même chose a un non-binaire pres) existe sur PPC, ARMv5+, MIPS32, Alpha avec CIX, mais pas les x86 mais bon "x86 sucks" comme d'habitude :-(
Voila, c'est de mémoire, je ne garanti pas qu'il n'y ait pas d'erreur..
Tu peux m'envoyer un mail si tu veux discuter du sujet.