Archive for novembre, 2010

26

Machine à état fini, le retour

nov
No Comments   Posted by Etienne SOBOLE |  Category:Algorithmes, Divers

Chose promise chose due,

Je vous avais parlé de vous proposer une version plus évoluée d’automate. Effectivement dans mon précédent post, l’automate ne servait à rien si ce n’est reconnaitre une chaîne de caractère alphabétique. Je vous propose donc un automate amélioré qui dispose de deux nouvelles fonctionnalités:

  • La conversion de caractère
  • L’exécution d’une fonction a chaque traitement de caractère

Voici donc un automate qui permet de reconstruire une sorte de DOM (Document object model) à partir d’une chaîne de caractères.
L’automate doit donc trouver les TAGs dans fichier html, vérifier qu’il existent (conforme aux standard) puis créer un arbre à partir des TAGs trouvés.

more...
 | Tags:
26

Sélection de pages de test

nov
No Comments   Posted by Etienne SOBOLE |  Category:Non classé

Ca y est je me suis choisi 5 pages de test pour évaluer la progression de mon navigateur (qui pour l’instant comporte 0 ligne de code).

J’ai un peu choisi ces pages au pif, je l’avoue.:
- pulsar : Une page qui semble simple !!!
- tlkgames : Un peu plus compliqué. C’est en plus le site d’un ami.
- frandroid : J’ai bien ce site de news.
- facebook : Lorsque j’afficherai correctement cette page, j’aurai déjà bien progréssé.
- clubic : Là c’est du lourd, j’ai jamais vu un site qui moule autant sur un smartphone.

Afin de supprimer le Javascript des pages (vu que le moteur javascript n’est pas là d’exister), je me suis servi de Scrapbook, une extension Firefox vraiment bien utile. cette extension permet d’enregistrer une pages web sur votre disque dur afin de pouvoir la consulter ultérieurement sans connexion. L’extension a aussi la particularité de virer tous le code javascript, ce qui est exactement le but recherché en ce qui me concerne.

Bon l’objectif est tout de même d’afficher ces pages en moins de 20.000.000 de cycles (hors transfert de données), c’est a dire 1/50eme de seconde.
Autant dire que c’est pas gagné surtout que le décodage d’images jpeg est assez gourmand en temps de calcul.

On verra…

more...
22

BeagleBoard

nov

Salut.

Comme j’en avais un peu marre d’attendre ma pandaboard, j’ai fini par commander une beagleboard (deux en fait) sur le site de Watterott.
La BeagleBoard était annoncée comme disponible, et finalement je l’ai reçu 3 jours plus tard (aujourd’hui quoi !).

Malheureusement, j’ai été pris un peu de court, j’ai pas l’alim (ni rien d’autre d’ailleurs). Il va me falloir attendre un peu avant de pouvoir tester tout ça !!! C’est bien dommage.

En tout cas j’ai été surpris par la taille de l’engin, c’est vraiment tout petit ;)

more...
 | Tags:
20

Découverte des machines à états finis.

nov
No Comments   Posted by Etienne SOBOLE |  Category:Non classé

Ce qui est bien avec mon projet de navigateur Web, c’est que je découvre des tas d’algorithmes dont j’avais parfois entendu parlé, mais que je n’avais jamais eu l’occasion de mettre en pratique.

C’est le cas des machines à états finies (appelée aussi automate à états finis).

Ces machines sont utilisées pour parser un document. C’est l’exemple même de l’algorithme simple et puissant dont on se dit en les mettant en pratique qu’il ne peut pas exister mieux. Les expressions régulières sont (enfin je le suppose) au moment de leur compilations transformées en machines à états finis.

Les machines à états finis sont aux expressions régulières ce que l’assembleur est au C++
Elles sont:

  • La représentation compilé d’une expression régulière.
  • Plus puissantes que les expressions régulières (qui ne sont qu’un sous ensemble des machines à états possibles.)
  • Plus rapide si elles sont utilisée directement
  • Pas forcément plus complexe à manipuler, même si ce reste quand même plus long à programmer.
  • more...
    12

    Table de hachages et arbres de recherches

    nov
    No Comments   Posted by Etienne SOBOLE |  Category:Non classé

    Lors de la réalisation de mon navigateur je vais avoir besoin d’une solution pour traiter les chaîne de caractères: les reconnaître, les comparer, contrôler leur existence…

    Il s’agit ici d’implémenter “les collections”, a savoir un tableau dont les clés sont des chaines de caractères et non pas des entiers. Il existent plusieurs solutions pour implémenter les collections. J’en ai testé deux:

  • Les tables de hachage.
  • Les arbres de recherche.
  • more...
    10

    Petite visite des Cortex A8 et A9

    nov

    Tout développeur Assembleur se doit de connaitre au minimum les instructions de son processeur mais également leur temps d’exécution.
    Pourtant ici je vais plutôt vous parler des règles d’utilisation des propriétés superscalaire des Cortex.

    Les Cortex A8 et A9 disposent de 2 pipelines d’exécutions.
    Cela veut dire, en théorie, que le processeur va pouvoir exécuter deux instructions dans le même cycle.
    Toutes les instructions des Cortex A8 et A9 peuvent s’exécuter dans les deux pipelines à l’exception des cas suivants :

    more...