Informatique

Division by 10

Wednesday, 27 September 2017
|
Écrit par
Grégory Soutadé

For a human, it's pretty simple to divide a number by ten because we used to calculate in ten base everyday. But ... a computer handle numbers in base 2. It doesn't means that it can't compute a division with a number that is not a power of 2, but operations are really faster in this base. Especially if you don't have floating point unit.

At work, I had to re implement the function "printf". To display decimal integers, I use an algorithm like :

while (value)
{
    *cur_ptr = '0' + (value%10);
    value = value/10;
    ...
}

This works fine, but two GCC builtin functions udivdi3 and umoddi3 are called which represent an amount of 3.5kB of code. So, I was looking for a code size optimized implementation on the Internet and didn't found my way.

Finally, I wrote my own. It's a basic one inspired from child learning method :

01. void div10(unsigned value, unsigned* _res, unsigned* _mod)
02. {
03.    unsigned res = value / 8;
04.    unsigned mod = value - (res*10);
05.
06.    while (mod > 10)
07.    {
08.        res -= 1;
09.        mod += 10;
10.    }
11.
12.    *_res = res;
13.    *_mod = mod;
14. }

This algorithm is a basic approach to division. It tries all numbers until it find the good one.

First thing : why I use variables instead of directly write values to pointers ? It's to indicate to GCC that they are temporary values which can be kept into registers and not written every loop into the memory (save instructions and memory accesses).

Line 3 is the begining. We will start at value / 8 which can be easily done by the computer because it is equivalent to a right shift of 3 bits (only one instruction). Note that 8 is the closest power of two to 10 and x/8 is greater than x/10 .

Line 4 is the computation of difference (distance) between my result multiplied by 10 and the current value. For the final result, this difference must be less than 10 (which correspond to the modulo).

Line 6 : while its not the case, we decrement result and increment modulo. Why incrementing modulo ? It's an optimization of the re computation of :

mod = value - (res*10);

If res is decremented, modulo is incremented as value is fixed. So, a simple addition is sufficient here.

There is another big trick in this code : the substract line 4 is done with UNSIGNED values and the result of line 4 is most of the time negative ! Which corresponds to big unsigned value (> 2147483648) that also implies > 10. We have to wait an integer overflow for mod to become positive and when it's done, we get the current modulo value (at least MAXLONGINT+10 = 9) !

If we does opposite operation ((res*10) - value), we have to decrement mod until it becomes less or equals to 0. But, in this case, all operations must be done in signed mode and the final modulo must be inverted at the end (more instructions) :

void div10(unsigned long value, unsigned long* _res, unsigned long* _mod)
{
    unsigned long res = value / 8;
    unsigned long mod = (res*10) - value;

    while (((signed long)mod) > 0)
    {
        res -= 1;
        mod -= 10;
    }

    *_res = res;
    *_mod = (unsigned long)-(signed long)mod;
}

Facts : the unsigned version of my algorithm is 15 instructions while udivdi3 + umoddi3 is 881 instructions. Wonderful !

Beware : this algorithm is slow. For small numbers it's not import because x/8 =~ x/10, but when x becomes bigger, the difference can be huge and requires one decrement, one increment and one test multiplied (x/8 - x/10)/10 times. For 32 bits numbers, it's 10 737 418 loops...

This algorithm can be extended to any divisor by replacing hardcoded divisor with a parameter and a function that finds the nearest and inferior power of 2.

void div(unsigned long value, unsigned long divisor, unsigned long* _res, unsigned long* _mod)
{
    unsigned long res, mod, tmp = divisor, power2 = 0;

    /* Nearest inferior power of 2 */
    while (tmp > 1)
    {
        tmp >>=1;
        power2++;
    }

    res = value >> power2;
    mod = value - (res*divisor);

    while (mod > divisor)
    {
        res -= 1;
        mod += divisor;
    }

    *_res = res;
    *_mod = mod;
}

gPass 0.8

Monday, 24 July 2017
|
Écrit par
Grégory Soutadé

Logo gPass

Voici la dernière mouture de gPass, le gestionnaire de mot de passe pour Firefox et Chrome ! Il s'agit là d'une fort belle version avec plein de nouveautés. La précédente date d'un an et demi déjà, plusieurs facteurs ont motivé le développement de celle-ci. Tout d'abord, Firefox abandonne le support des addons pour les remplacer par les webextensions. Ces webextensions utilisent la même API que les extensions Chrome de Google. Si cela facilite le travail du développeur, il place désormais Mozilla au rang des suiveurs dans le monde du web. Le support de l'addon gPass pour firefox est donc abandonné au profit du nouveau code de la webextension (quasi identique à celui de Chrome).

Le gros avantage de cette nouvelle API est le support de la cryptographie de manière (quasi) native. L'option SHADOW_LOGINS est donc activée par défaut. Le mode de chaînage ECB n'étant pas supporté par l'API, j'ai décidé de changer la façon dont sont chiffrées les données avec du CBC, ce qui est plus solide cryptographiquement parlant. J'ai aussi noté que si les mots de passes étaient salés, ils ne l'étaient pas correctement car ce dernier était ajouté à la fin et non au début, donc inutile lorsqu'il y a plus de 13 caractères (la longueur par défaut étant 16...). Le protocole d'échange avec le serveur a lui aussi évolué pour passer en version 4. D'autres modifications mineures ont été apportées sur la partie serveur :

  • Retour automatique en haut
  • Disposition de l'interface
  • Génération des mots de passe (plus facilement lisible pour les humains)
  • Les mots de passes en clair ne sont affichés que pendant 15 minutes
  • Ajout de tests unitaires

Autre fonctionnalité intéressante qui me trottait dans la tête depuis un certain temps : le blocage des connexions lorsque l'on détecte une clé maître en clair dans les paramètres de la requête. Malheureusement ce mécanisme ne fonctionne que sous Chrome.

L'ajout de la cryptographie native est un réel plus. Néanmoins c'est un véritable calvaire à programmer. En effet, les développeurs ont eu le bon goût de l'implémenter en utilisant des Promise, donc des appels de fonctions asynchrones (car en arrière plan le navigateur invoque un binaire OpenSSL), alors que nous avons besoin du résultat immédiatement ! Bref, il a fallu attendre l'arrivée de la version 53 et du support des directives await et async pour retrouver un semblant d'utilisabilité. Hélas, c'est la période choisie par Debian pour entrer dans sa phase de gel en vue de la sortie de la nouvelle version stable. Il y a donc eu 6 + 1 mois de retard car je ne voulais pas casser la compatibilité avec des serveurs alors que les addons seraient resté bloqués en v0.7. De plus, je ne pouvais pas tester directement.

Autre nouveauté pour ceux qui ne veulent pas ouvrir leur navigateur, il y a désormais une interface accessible en ligne de commandes (CLI/terminal) ! Cela permet également d'étendre le gestionnaire à autre chose que du pur web !

Les sources sont disponibles sur ma forge sous licence GPLv3.

Chrono v2

Monday, 17 July 2017
|
Écrit par
Grégory Soutadé

Chrono de face

La première version de mon chronomètre ne m'a pas pleinement satisfait : trop gros, trop lourd, afficheur parfois capricieux. Néanmoins, l'expérience acquise m'a permis d'entrevoir plusieurs pistes d'améliorations. Le critère principal pour une v2 était de pouvoir fabriquer un circuit imprimé d'une taille réduite pour pas trop cher. Après quelques recherches j'ai trouvé mon bonheur chez OSH Park. Il s'agit d'une association basée aux États-Unis dont le but est de regrouper les designs des particuliers afin de réduire les coûts. Cerise sur le gâteau : il n'y a pas de frais de port ! Leurs PCB sont facilement reconnaissables par leur couleur violette unique. De plus ils ont un site extrêmement bien fait qui permet de visualiser le résultat des masques avant de lancer la production. Encore mieux, ils acceptent toute sorte de formats en entrée (eagle, kicad...).

Comparaison ancien et nouveau chrono

Je me suis donc lancé pour une deuxième version de manière un peu plus autonome (mais toujours avec l'aide précieuse de Frédéric M.). Le nouveau schéma est basé sur des MOSFET et non plus des transistors. Il est double face. Les 4 piles rechargeables sont remplacées par une batterie Lithium-ion beaucoup plus petite et légère (mais avec la moitié d'autonomie, 1A contre 2A). Plus besoin d'ouvrir le boîtier pour assurer la recharge, grâce à une charge via câble USB. Fonction importante qui manquait : le boîtier aura un aimant sur sa face arrière.

Bref, le jour et la nuit par rapport à la première version. En volume, la v2 est 2,44 fois plus petite (5,6x7,5x2,9 contre 7,2x8,1x5,1) avec un poids de 126g (aimant compris) contre 258g.

Chrono de face

Un mois après avoir passé la commande, les 3 PCB arrivent. Ils sont de très bonne qualité, vernis, trous métallisés, marquage en surface. Seul bémol : il faut scier à la main les bouts qui dépassent (provenant de la plaque de production), alors que le reste de la carte est parfaitement découpée...

L'étape de la soudure se passe bien. Certains trous sont cependant un peu trop petits, et il faut forcer un peu pour rentrer l'afficheur et une LED. Première mise sous tension : il ne brûle pas, c'est une bonne nouvelle. Tentative de programmation avec MPLab. Rien ne se passe... C'est le moment où le doute s'installe : problème de soudure ? Problème de résistance ? Problème de niveau de tension au niveau des MOSFET ? ... La première erreur est dans le code, les MOSFET P fonctionnent en logique inverse (niveau bas pour qu'ils soient passants). Après correction l'afficheur reste éteint. Un petit tour avec le multimètre ainsi qu'une revue de schéma un peu plus poussée et l'on remarque que toutes les masses ne sont pas reliées. En effet, eagle fait une différence entre les pattes GND et VSS, il faut donc relier les deux mondes par un nouveau fil. Autre blague, le 7 segments HDSP-B03E n'était plus disponible. Bêtement, j'ai pris un B04E en pensant qu'ils étaient identiques. Sauf qu'en réalité la polarité des LED est inversée sur ce dernier. En prenant cela en compte, j'aurais pu faire baisser le prix global (les MOSFET P sont plus chers que les N).

Finalement le circuit fonctionne parfaitement. Une fois le programme optimisé, j'arrive à faire fonctionner le PIC à 2Mhz contre 4Mhz pour la première version (en gardant la même taille du binaire résultant), et, si j'avais regroupé les pattes des transistors N et P sur les blocs B et C sans les mélanger, je pense qu'il serait possible de descendre encore la fréquence.

La fabrication de la boîte fut une autre étape particulièrement longue. J'ai utilisé un générateur de boîtes sous inkscape, mais celui-ci ne crée pas les créneaux sur certains côtés, ce qui n'est pas pratique du tout. Obligé de faire une multitude de retouches à la main. De plus, la marge ajoutée n'est pas agréable, j'aurais dû la positionner à 0. Au final, je l'ai complètement re déssiné à la main. Petite blague qui m'a fait perdre beaucoup de temps : il y a une différence entre ma version Linux et la version Windows utilisée au fablab. Si on ne choisit pas la bonne option au lancement du logiciel, les dimensions sont faussées. Ça a donc été une vraie galère pour réaliser ce que je voulais, alors qu'il ne m'avait fallu que deux essais la fois précédente.

Chrono face arrière

J'ai donc pu faire une boîte très ajustée et y scotcher un aimant récupéré sur un vieux disque dur. Sauf que ce dernier a le bon goût de créer des perturbations électromagnétiques et vider la batterie pendant la nuit ! L'utilisation d'aimants neodymes plus petits et moins puissants suffit si on les place bien (mais ils coûtent plus cher).

Voilà, 6 mois d'agitation pour un petit chrono. Pour ceux que ça intéresse, je joins l'archive complète du projet avec les schémas, documentation et sources. Les problèmes de masses et de taille de trous sont réglés (v2.1), mais il faudrait pouvoir souder le connecteur JST de la batterie au lieu de le laisser en l'air (ça libérerait un connecteur de l'ICSP et des fils inutiles). Ou encore utiliser un connecteur USB traversant.

iMac stuck at boot

Friday, 26 May 2017
|
Écrit par
Grégory Soutadé

Update : Finally it seems that the GPU is dead. I installed Debian testing with XFCE UI which is very smooth even n software rendering

The last week I was given an iMac 27" to repair, with Yosemite installed on it. It boots fine but was stuck at about 1/3 of the progress bar. Booting in safe mode works (left shift key pressed at startup), so it's not an hardware issue. After trying a lot of things (booting in verbose mode (command + V), reset SMC/PRAM, reinstalling system in recovery mode (command + R)), I found the solution thanks to this thread.

You have to boot in single user mode (command + S), then type :

# mount - uw /
# system_profiler SPExtensionsDataType > /tmp/a
# less a

Then search for "Not Signed" with "/" comamnd and goto next found iteration with "n" command.

We can see "EPSONUSBPrinter" and "hp_fax_io" are not signed, so delete these extensions and reboot like this :

# cd /System/Library/Extensions
# rm -rf name_of_the_kext.kext
# rm -rf /System/Library/Caches/*
# reboot

Be careful to not delete some other non signed core extensions (JMicronATA...). Select only external peripherals drivers. A blocking module was my first diagnostic, but impossible to know which is responsible until there is no really verbose boot mode (thanks Apple).

Update

There is one way to have access to logs during boot :

  • Go in recovery mode
  • Launch a terminal
  • Type "resetpassword"
  • Reset root password
  • Reboot in safe mode
  • Login as root (other)
  • Enable SSH access
  • Reboot
  • Connect to your mac in SSH (ssh root@XXX)
  • Read the log in /var/log/system.log

Hex offsets

Saturday, 06 May 2017
|
Écrit par
Grégory Soutadé

Capture Hex Offsets

Voici un petit outils qui me manquait depuis fort longtemps (du moins quand j'en ai besoin). En apparence, rien d'extraordinaire : une simple calculatrice hexadécimale avec uniquement les opérations "plus" et "moins"... Pourtant elle est extrêmement pratique quand on travaille sur deux bases d'adresses différentes (avec un décalage d'offset).

Quelques options ont été rajoutées comme le fait de pouvoir facilement remettre une ligne à zéro, valider ou non l'entrée, copier-coller le résultat dans le presse-papier, tout effacer, régler le nombre d'entrées (jusqu'à 20) et convertir un nombre en décimal ou hexadécimal.

Le tout a été réalisé avec QtCreator (donc C++ et Qt) et est disponible sur ma forge sous licence GPLv3.