tag:linuxfr.org,2005:/tags/dos/publicLinuxFr.org : les contenus étiquetés avec « dos »2023-11-13T23:31:51+01:00/favicon.pngtag:linuxfr.org,2005:Bookmark/74822023-11-10T07:59:55+01:002023-11-10T07:59:55+01:00DOS Subsystem for Linux: allowing users to make use of both DOS and Linux applications from DOS<a href="https://github.com/haileys/doslinux">https://github.com/haileys/doslinux</a> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/133869/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/psychofox/liens/dos-subsystem-for-linux-allowing-users-to-make-use-of-both-dos-and-linux-applications-from-dos#comments">ouvrir dans le navigateur</a>
</p>
Psychofoxhttps://linuxfr.org/nodes/133869/comments.atomtag:linuxfr.org,2005:Post/433592022-12-26T23:49:17+01:002022-12-27T18:24:23+01:00This program cannot be run in DOS mode<p>Bonjour 'run</p>
<p>Comme <a href="//linuxfr.org/forums/linux-general/posts/resolu-operation-system-not-found">tu le sais</a>, je chipote un peu sur mon Dell Inspiron 17R N7110 de dernière génération (humour, je précise).</p>
<p>Ma dernière idée est de mettre à jour le BIOS. Comme le support de Dell est bien fait, je trouve facilement <a href="https://www.dell.com/support/home/fr-be/drivers/driversdetails?driverid=fwjtd&oscode=biosa&productcode=inspiron-17r-n7110">les fichiers nécessaires et le mode d'emploi</a> pour les appareils sous Linux :</p>
<blockquote>
<ol>
<li>Copy the downloaded file to a bootable DOS USB key.</li>
<li>Power on the system, then Press F12 key and Select "USB Storage Device" and Boot to DOS prompt.</li>
<li>Run the file by typing copied file name where the executable is located.</li>
<li>After BIOS update finished, system will auto reboot to take effect.</li>
</ol>
</blockquote>
<p>Bon, DOS, on trouve cela où ? Toujours <a href="https://www.dell.com/support/kbdoc/fr-be/000131486/update-the-dell-bios-in-a-linux-or-ubuntu-environment#Creating%20a%20USB%20Bootable%20Storage%20Device">Dell donne une piste de solution</a> : utiliser <a href="http://freedos.org/">FreeDOS</a>.</p>
<p>Après avoir mis quelque temps à comprendre (oui, je ne suis pas toujours très intelligent) que pour faire une <em>USB_Live</em> il valait mieux télécharger l'image <em>FullUSB</em> (ou <em>LiteUSB</em>) que l'image <em>LiveCD</em>, je me suis retrouvé avec une belle clé USB bootable en FreeDOS.</p>
<p>J'y ai ajouté le fichier <code>N7110A13.exe</code> et j'ai lancé avec succès mon flamboyant Dell sous FreeDOS.<br>
Un petit coup de <code>DIR</code> pour vérifier que <code>N7110A13.exe</code> était bien présent et je me lance un petit<br>
<code>C:>N7110A13.exe</code></p>
<p>Mais au lieu d'obtenir une triomphale mise à jour de mon BIOS, j'obtiens un pitoyable<br>
<code>This program cannot be run in DOS mode</code></p>
<p>Est-ce de la faute de mon FreeDOS ? En tout cas, il arrive à lancer d'autre .exe sans grand souci.</p>
<p>Est-ce un problème de corruption du fichier téléchargé ? A priori non vu que les sommes de contrôle sont correctes (ou bien je mélange tout ?)</p>
<p>Mes recherches internet n'ont pas été fructueuses si ce n'est pour me confirmer que je ne suis pas le seul à avoir rencontrer ce problème mais pour les solutions, hormis passer par un Windows, rien de bien convaincant sachant que passer par Windows ne m'excite pas énormément pour plein de raisons.</p>
<p>Quel est ton avis ?</p>
<div><a href="https://linuxfr.org/forums/astucesdivers/posts/this-program-cannot-be-run-in-dos-mode.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/129789/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/forums/astucesdivers/posts/this-program-cannot-be-run-in-dos-mode#comments">ouvrir dans le navigateur</a>
</p>
tisaachttps://linuxfr.org/nodes/129789/comments.atomtag:linuxfr.org,2005:Bookmark/40722022-01-05T10:39:19+01:002022-01-05T10:39:19+01:00MicroWeb: un brouteur pour DOS<a href="https://github.com/jhhoward/MicroWeb">https://github.com/jhhoward/MicroWeb</a> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/126463/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/devnewton/liens/microweb-un-brouteur-pour-dos#comments">ouvrir dans le navigateur</a>
</p>
devnewton 🍺https://linuxfr.org/nodes/126463/comments.atomtag:linuxfr.org,2005:News/388212019-08-06T22:22:32+02:002019-10-12T18:19:08+02:00Retour sur la libération du code source de MS-DOS 1.25 et 2.0 par MicrosoftLicence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<div><p>Microsoft a décidé le 28 septembre 2018 de <strong>libérer</strong> les sources des versions 1.25 et 2.0 de MS-DOS sous licence MIT et de les publier sur GitHub.</p>
<p><a href="https://github.com/Microsoft/MS-DOS/blob/master/msdos-logo.png"><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f6d6963726f736f66742f4d532d444f532f6d61737465722f6d73646f732d6c6f676f5f323530783235302e706e67/msdos-logo_250x250.png" alt="MS-DOS Logo" title="Source : https://raw.githubusercontent.com/microsoft/MS-DOS/master/msdos-logo_250x250.png"></a></p>
<p>Il s’agit des mêmes versions données au Computer History Museum (<a href="https://fr.wikipedia.org/wiki/Mus%C3%A9e_de_l%27histoire_de_l%27ordinateur">Musée de l’histoire de l’ordinateur</a>) le 25 mars 2014, comme le précise Microsoft dans le fichier <a href="https://github.com/microsoft/MS-DOS/blob/master/README.fr-FR.md"><code>README.md</code></a>.<br>
Microsoft précise aussi dans son billet de blog que les deux versions (1.25 et 2.0) ont été écrites avec l’assembleur de l’Intel 8086, le premier processeur de la famille <a href="https://fr.wikipedia.org/wiki/x86" title="Définition Wikipédia">x86</a>.</p>
<p>L’entreprise indique que beaucoup de fichiers de documentation d’extension <code>.TXT</code> et <code>.DOC</code> intercalés entre les fichiers sources sont intéressants à lire, tout comme de nombreux commentaires directement dans le code source.</p>
<p>On ne peut que se réjouir de cette libération, bien qu’elle soit tardive. Mais à quand la libération de <code>NTKRPAMP.EXE</code>, le noyau de Windows NT pour un système multiprocesseur ?</p>
</div><ul><li>lien nᵒ 1 : <a title="https://github.com/Microsoft/MS-DOS" hreflang="fr" href="https://linuxfr.org/redirect/103774">Dépot sur GitHub</a></li><li>lien nᵒ 2 : <a title="https://devblogs.microsoft.com/commandline/re-open-sourcing-ms-dos-1-25-and-2-0/" hreflang="fr" href="https://linuxfr.org/redirect/103775">Billet de blog de Microsoft</a></li><li>lien nᵒ 3 : <a title="https://www.phoronix.com/scan.php?page=news_item&px=Microsoft-MS-DOS-GitHub" hreflang="fr" href="https://linuxfr.org/redirect/103776">L’annonce sur Phoronix</a></li></ul><div><h2 class="sommaire">Sommaire</h2>
<ul class="toc">
<li><a href="#toc-petit-historique-de-ms-dos">Petit historique de MS-DOS</a></li>
<li><a href="#toc-limpact-de-ms-dos-sur-lindustrie-et-laculture">L’impact de MS-DOS sur l’industrie et la culture</a></li>
<li>
<a href="#toc-les-versions-de-microsoft-dos">Les versions de Microsoft DOS</a><ul>
<li><a href="#toc-version100-1981">Version 1.00 (1981)</a></li>
<li><a href="#toc-version125-1982">Version 1.25 (1982)</a></li>
<li><a href="#toc-version20-1983">Version 2.0 (1983)</a></li>
<li><a href="#toc-version30-1984">Version 3.0 (1984)</a></li>
<li><a href="#toc-version622-1994">Version 6.22 (1994)</a></li>
</ul>
</li>
<li>
<a href="#toc-les-divers-projets-libres-autour-de-ms-dos">Les divers projets libres autour de MS-DOS</a><ul>
<li>
<a href="#toc-toujours-en-d%C3%A9veloppement">Toujours en développement</a><ul>
<li><a href="#toc-freedos">FreeDOS</a></li>
<li><a href="#toc-dosbox">DOSBox</a></li>
</ul>
</li>
<li>
<a href="#toc-projets-abandonn%C3%A9s">Projets abandonnés</a><ul>
<li><a href="#toc-pc-mos386">PC-MOS/386</a></li>
<li><a href="#toc-cpm">CP/M</a></li>
<li><a href="#toc-dosemu">DOSEMU</a></li>
</ul>
</li>
</ul>
</li>
<li><a href="#toc-cette-lib%C3%A9ration-peutelle-profiter-au-projet-freedos">Cette libération peut‐elle profiter au projet FreeDOS ?</a></li>
<li>
<a href="#toc-quel-int%C3%A9r%C3%AAt-y-trouver">Quel intérêt y trouver ?</a><ul>
<li><a href="#toc-lint%C3%A9r%C3%AAt-acad%C3%A9mique">L’intérêt académique</a></li>
<li><a href="#toc-lint%C3%A9r%C3%AAt-historiquearchivistique">L’intérêt historique / archivistique</a></li>
<li><a href="#toc-lint%C3%A9r%C3%AAt-s%C3%A9curitaire">L’intérêt sécuritaire</a></li>
<li><a href="#toc-lint%C3%A9r%C3%AAt-pratique">L’intérêt pratique</a></li>
</ul>
</li>
</ul>
<h2 id="toc-petit-historique-de-ms-dos">Petit historique de MS-DOS</h2>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f622f62362f5374617274696e674d73646f732e706e67/StartingMsdos.png" alt="MS-DOS" title="Source : https://upload.wikimedia.org/wikipedia/commons/b/b6/StartingMsdos.png"></p>
<p>Le système d’exploitation MS-DOS (<em>Microsoft Disk Operating System</em>) s’appelait à l’origine <em>QDOS</em> (<em>Quick and Dirty OS</em>) ou <em>86-DOS</em> et fut développé par Tim Patterson de l’entreprise SCP (<em>Seattle Computer Products</em>) comme un clone de CP/M, un système d’exploitation développé en 1974 par Gary Kidall de chez Digital Research. CP/M était conçu pour les processeurs Intel 8080 / Zilog Z80, <em>86-DOS</em> visait donc à fournir un environnement familier sur la nouvelle architecture matérielle 8086 d’Intel. QDOS a pris le nom de MS-DOS à la suite de son rachat par Bill Gates.</p>
<p>Le système CP/M (<em>Control Program/Monitor</em>) devait être initialement le système d’exploitation de l’IBM PC, mais alors que CP/M-86 était en développement les relations entre Digital Research et IBM se sont dégradées autour des questions de facturation (le premier préférant un achat unique de licence quand le second désirait une redevance), et parce que les accords de non‐divulgation (NDA — <em>non‐disclosure agreement</em>) demandés par IBM ne convenaient pas à Digital Research.</p>
<p>Bill Gates a saisi l’occasion et conclu un accord commercial avec IBM pour que celui‐ci fonde son PC-DOS sur MS-DOS. C’est ainsi que PC-DOS, fut distribué avec les premières livraisons de l’IBM PC à l’automne 1981. La version de CP/M compatible avec le processeur 8086 fut disponible dès le printemps 1982 (à peine six mois plus tard) mais ce système d’exploitation fut un échec commercial, pris de vitesse par PC-DOS. Découvrant l’affaire, Digital Research menaça IBM d’une action en justice pour contrefaçon de propriété intellectuelle et obtint d’IBM que CP/M-86 soit proposé comme une alternative à PC-DOS, mais cela ne pu infléchir la route de PC-DOS / MS-DOS et le succès de Microsoft.</p>
<p>Tandis que les premiers clones de l’IBM PC apparaissait, Microsoft conclut des accords avec les autres fabricants pour distribuer MS-DOS. MS-DOS devint le système majoritaire en prenant le pas sur PC-DOS, et les deux branches étant développées séparément, des incompatibilités furent parfois introduites.</p>
<p>La famille CP/M est différente de la famille UNIX en termes de fonctionnement architectural. De plus, MS-DOS est un système mono‐utilisateur, car Microsoft réservait cette fonctionnalité pour son UNIX maison nommé <a href="https://fr.wikipedia.org/wiki/Xenix" title="Définition Wikipédia">Xenix</a>.</p>
<h2 id="toc-limpact-de-ms-dos-sur-lindustrie-et-laculture">L’impact de MS-DOS sur l’industrie et la culture</h2>
<p>MS-DOS a conservé de CP/M le concept de BIOS qui permet d’abstraire le matériel afin de faire fonctionner une version unique du système d’exploitation sur différents modèles de machines. L’accord commercial entre Microsoft et IBM autour de MS-DOS et de l’IBM PC a rendu très populaire ce concept au cœur du développement de l’informatique personnelle, facilitant plus tard l’essor d’un certain noyau <em>Freax</em> visant le processeur i386 (renommé rapidement en <em>Linux</em>)…</p>
<p>Microsoft Windows utilise toujours aujourd’hui le caractère <code>\</code> comme séparateur de chemin d’accès, bien que le reste de l’industrie utilise <code>/</code>. Cela vient du fait que DOS a hérité de CP/M le caractère <code>/</code> comme préfixe d’option (qu’il semble avoir hérité lui‐même de VMS). Larry Osterman, un ingénieur de Microsoft <a href="https://blogs.msdn.microsoft.com/larryosterman/2005/06/24/why-is-the-dos-path-character/">a raconté</a> que, parce que les employés de Microsoft développaient DOS sur Xenix, ils étaient habitués à utiliser le caractère <code>/</code> comme séparateur de chemin et <code>-</code> comme préfixe d’option. Ceux‐ci implémentèrent donc dans certaines parties de DOS (N. D. L. R. : mais pas toutes) la capacité de décoder les caractères <code>/</code> et <code>\</code> indifféremment dans les chemins d’accès, et ajoutèrent une variable <code>SWITCHAR</code> à mettre dans le fichier <code>config.sys</code> pour changer le préfixe d’option de <code>/</code> en <code>-</code>. Larry Osterman dit dans son billet que l’option a disparu depuis longtemps, mais nous pouvons cependant <a href="https://github.com/microsoft/MS-DOS/search?q=SWITCHAR&unscoped_q=SWITCHAR">la retrouver</a> dans le code de DOS 2.0 qui vient d’être libéré.</p>
<p>MS-DOS fut plusieurs fois adapté sous licence par des tiers (PC-DOS, Compaq DOS…) et des projets complètements indépendants ont été développés pour être compatible avec lui : DR-DOS, FreeDOS (on en parle après), ou encore PTS-DOS, une version russe certifiée par le Ministère de la Défense de la Fédération de Russie.</p>
<p>MS-DOS ou ses clones furent très souvent utilisés au cœur de systèmes industriels ayant une grande longévité, ce qui rend parfois nécessaire sa maintenance aujourd’hui. MS-DOS fut souvent utilisé comme système autonome pour des utilitaires sur disquette (ancêtres des CD autonomes sous GNU/Linux et autres clefs USB autonomes) mais son usage a largement dépassé le cadre de l’ordinateur personnel.</p>
<p>Tout comme nous trouvons aujourd’hui GNU/Linux dans de nombreux appareils du quotidien comme nos téléphones Android, nos box Internet, des télévisions ou même des réfrigérateurs, MS-DOS ou ses clones se sont retrouvés dans certains objets parfois inattendus, comme le téléphone <a href="https://en.wikipedia.org/wiki/Nokia_9000_Communicator#9110">Nokia 9110 <em>Communicator</em></a> ou la calculatrice graphique <a href="https://fr.wikipedia.org/wiki/Casio_Graph_100%2B">Casio Graph 100+</a> qui exécutent un ROM-DOS de Datalight (équivalent à MS-DOS 2) sur un processeur AMD dérivé du i486, pour le premier, et un processeur Nec dérivé du 80286, pour la seconde. Ceci permit à des enthousiastes de développer leurs propres programmes pour cette calculatrice en utilisant, par exemple, la suite Turbo C 3 de Borland (C, C++ et assembleur), le compilateur C de Digital Mars ou encore <a href="https://fr.wikipedia.org/wiki/QuickBASIC" title="Définition Wikipédia">QuickBASIC</a> de Microsoft.</p>
<p>DOS est aussi devenu, à l’instar du jeu <em>DOOM</em>, un défi pour beaucoup de développeurs : celui de le porter sur le plus d’architectures possibles (ou aussi, dans le cas de DOS, de mettre en œuvre des clones). On peut citer par exemple la <a href="https://www.magiclantern.fm/forum/index.php?topic=14853.0">version de FreeDOS</a> conçue pour tourner sur les appareils photos Canon EOS (comme module de l’extension non officielle Magic Lantern), la très récente inclusion de DosCard (une version incorporable de DOSBox, voir ci‐après) <a href="https://www.youtube.com/watch?v=m3_be5weKW8">dans le moteur OpenMW</a> permettant d’avoir un environnement de travail DOS dans l’univers virtuel du jeu <em>Morrowind</em>. Microsoft lui‐même s’est prêté à ce jeu lorsque le 1<sup>er</sup> avril 2015 l’entreprise a publié une application appelée « MS-DOS Mobile » présentée comme un nouveau système d’exploitation mobile, et qui fournissait une interface similaire à MS-DOS sur leurs téléphones sous Windows.</p>
<p>Enfin, le clone libre FreeDOS (dont nous parlons juste après) est parfois installé sur certaines machines vendues sans Windows ou sans GNU/Linux, afin de livrer la machine avec un fonctionnement minimal. Certaines machines vendues « sans système d’exploitation » ont donc parfois bien un système d’exploitation quand même !</p>
<h2 id="toc-les-versions-de-microsoft-dos">Les versions de Microsoft DOS</h2>
<h3 id="toc-version100-1981">Version 1.00 (1981)</h3>
<p>La première version sortie sur l’IBM PC.</p>
<p>Elle ne prend en charge que les disquettes 5″¼ simple face de 160 Kio.<br>
<img src="//img.linuxfr.org/img/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f7468756d622f612f61612f466c6f7070795f6469736b5f323030395f47312e6a70672f36343070782d466c6f7070795f6469736b5f323030395f47312e6a7067/640px-Floppy_disk_2009_G1.jpg" alt="Disquette" title="Source : https://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Floppy_disk_2009_G1.jpg/640px-Floppy_disk_2009_G1.jpg"></p>
<p>Les répertoires n’existaient pas sur cette version et on ne pouvait mettre que 64 fichiers sur une disquette.</p>
<h3 id="toc-version125-1982">Version 1.25 (1982)</h3>
<p>C’est <a href="https://github.com/microsoft/MS-DOS/tree/master/v1.25">une des versions qui ont été libérées</a>. Une légère évolution de la 1.24. Elle fut la première version vendue par Microsoft et, plus généralement, c’est la première version utilisée par tous les fabricants de clones des ordinateurs d’IBM.</p>
<p>Pour les disquettes 5″¼, on passe sur une gestion du double face avec une plus grande capacité (320 Kio).</p>
<p>Microsoft précise que le code source de cette version ne contient que sept fichiers en assembleur, comme on peut le voir sur le dépôt GitHub.</p>
<h3 id="toc-version20-1983">Version 2.0 (1983)</h3>
<p>Deuxième version <a href="https://github.com/microsoft/MS-DOS/tree/master/v2.0">libérée</a> par Microsoft.</p>
<p>Elle introduit la gestion des disques durs avec un système de fichiers FAT12, ainsi que les répertoires. Les disquettes 5″¼ simple face gagnent en capacité, passant de 160 Kio à 180 Kio, tandis que les disquettes double face passent de 320 Kio à 360 Kio.</p>
<p>Par rapport à la 1.25, dans le code source on passe de sept fichiers à cent fichiers en assembleur ; presque quinze fois plus, augmentant la sophistication du code et la taille de l’équipe de développement, comme le précise Microsoft.</p>
<h3 id="toc-version30-1984">Version 3.0 (1984)</h3>
<p>Cette version introduit la prise en charge des disquettes de 1 200 Kio et les disques durs de 15 360 Kio.</p>
<h3 id="toc-version622-1994">Version 6.22 (1994)</h3>
<p><em>La question qui se pose est : pourquoi ne pas avoir libéré le code de la dernière version commercialisée, la 6.22 ? Peut‐être pour ne pas afficher les <a href="https://en.wikipedia.org/wiki/MS-DOS#Use_of_undocumented_APIs">pratiques controversées</a> de ralentissement des concurrents ?</em> [N. D. M. : il s’agit de la dernière version commercialisée séparément]</p>
<p>L’<a href="https://fr.m.wikipedia.org/wiki/MS-DOS">historique des versions sur la page Wikipédia</a> évoque une version 7 avec Windows 95 et une 8 avec Windows ME en 2000 (avant une fin de prise en charge en 2001). Sont aussi mentionnés les problèmes rencontrés avec les versions 6.2x à cause des brevets logiciels. Ce pourrait être une explication, du moins pour la 6.22 (pas forcément pour la 3.0).</p>
<h2 id="toc-les-divers-projets-libres-autour-de-ms-dos">Les divers projets libres autour de MS-DOS</h2>
<p>Wikipédia possède des listes très détaillées de <a href="https://en.wikipedia.org/wiki/List_of_disk_operating_systems">systèmes compatibles DOS ou similaires à DOS</a>, ainsi que des <a href="https://en.wikipedia.org/wiki/Comparison_of_DOS_operating_systems">comparaisons</a> ou des informations très intéressantes sur les <a href="https://en.wikipedia.org/wiki/Virtual_DOS_machine">couches de compatibilité</a> permettant d’exécuter des programmes DOS sur des systèmes plus récents. Mais <em>LinuxFr.org</em> oblige, nous nous concentrons sur les projets libres continuant à entretenir l’environnement DOS.</p>
<p>À noter qu’il existait un système d’exploitation nommé OpenDOS, un descendant de DR-DOS de Digital Research (et donc de CP/M-86 via la branche <em>Concurrent PC-DOS</em>, sa version multi‐utilisateur). Mais bien que ce système s’appelle OpenDOS et que le source ait été distribué, celui‐ci n’a rien de libre. En effet, <a href="https://web.archive.org/web/19961018220910/http://caldera.com/news/pr002.html">selon les termes de Caldera</a>, le source aurait été rendu disponible pour une utilisation personnelle à coût nul, et une redistribution commerciale d’OpenDOS nécessitait une licence payante. L’annonce disait également que les sources de certains composants de tierces parties de Novell DOS 7 ne seraient pas publiés, ce qui fait d’OpenDOS une forme d’<em><a href="https://fr.wikipedia.org/wiki/Open_core">open core</a></em> dont même le cœur n’est pas libre car soumis à une clause non commerciale.</p>
<p>Le logiciel <a href="http://rpix86.patrickaalto.com/">rpix86</a> est similaire à DOSBox, que nous présentons ci‐après, et permet d’exécuter des jeux DOS sur un Raspberry Pi. Mais il n’est malheureusement pas libre, et le seul interpréteur qu’il est capable d’exécuter est <a href="https://www.4dos.info/">4DOS</a> qui, bien que le source soit disponible, est malheureusement couvert par une licence MIT modifiée qui n’est pas reconnue comme libre ni par l’<a href="https://fr.wikipedia.org/wiki/Open_Source_Initiative">OSI</a>, ni par la <a href="https://fr.wikipedia.org/wiki/Free_Software_Foundation">FSF</a>, une clause interdisant l’usage commercial. Le programme <em>rpix86</em> tournant sous GNU/Linux, on peut donc tout de même le citer, parce que dans <em>LinuxFr.org</em> il y a « Linux »…</p>
<h3 id="toc-toujours-en-développement">Toujours en développement</h3>
<h4 id="toc-freedos">FreeDOS</h4>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f7468756d622f332f33642f46726565444f535f6c6f676f345f323031302e7376672f35303070782d46726565444f535f6c6f676f345f323031302e7376672e706e67/500px-FreeDOS_logo4_2010.svg.png" alt="FreeDOS" title="Source : https://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/FreeDOS_logo4_2010.svg/500px-FreeDOS_logo4_2010.svg.png"></p>
<p><a href="https://www.freedos.org/">FreeDOS</a>, une alternative libre qui a été créée en 1994 du fait de l’arrêt du support par Microsoft.</p>
<p>Il est intéressant de voir que la version stable (1.0) de FreeDOS, sortie en 2006, a mis douze ans à arriver, chose rare dans le développement logiciel mais qui s’explique aisément par les faibles moyens à disposition. Il a fallu aux développeurs une bonne dose de ténacité pour ne pas abandonner.</p>
<p>FreeDOS est souvent comparé à <a href="https://reactos.org/">ReactOS</a>, qui vise à être une alternative libre à Microsoft Windows ; il peut aussi être comparé à <a href="https://www.haiku-os.org/">Haiku</a>, clone de BeOS compatible avec celui‐ci.</p>
<h4 id="toc-dosbox">DOSBox</h4>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f642f64642f444f53426f785f69636f6e2e706e67/DOSBox_icon.png" alt="DOSBox" title="Source : https://upload.wikimedia.org/wikipedia/commons/d/dd/DOSBox_icon.png"></p>
<p><a href="https://www.dosbox.com/">DOSBox</a> est un émulateur simulant un environnement compatible MS-DOS dans le but d’exécuter notamment des jeux vidéo développés autrefois pour ce système. Il est aussi possible de l’utiliser pour lancer tout type de logiciels. Ce projet est toujours dynamique et permet d’accéder à la culture du jeu vidéo sur PC de la fin des années 80 et du début des années 90, sans avoir à dénicher une vieille machine compatible. Bien que DOSBox soit capable de faire tourner FreeDOS, il fournit sa propre implémentation et son propre interpréteur de commandes DOS.</p>
<p>DOSBox permet aux particuliers d’exécuter leurs vielles applications et vieux jeux DOS, mais il permet également à des sociétés de redistribuer leurs anciens jeux pour de nouveaux systèmes en empaquetant DOSBox avec leurs jeux, de très <a href="https://en.wikipedia.org/wiki/Category:Games_commercially_released_with_DOSBox">nombreux titres</a> ont été distribués officiellement ainsi.</p>
<h3 id="toc-projets-abandonnés">Projets abandonnés</h3>
<h4 id="toc-pc-mos386">PC-MOS/386</h4>
<p>PC-MOS/386 était un système d’exploitation compatible DOS multi‐utilisateur et multi‐tâche développé par une entreprise américaine du nom de <em>The Software Link</em> et qui fut distribué pour la première fois en 1987, et fut <a href="https://github.com/roelandjansen/pcmos386v501">libéré</a> en 2017 sous licence GPL v3. Comme son nom l’indique, PC-MOS/386 visait les processeurs i386 qui ont une architecture bien plus récente que celles prises en charges par les premières versions de DOS dont nous parlons dans cet article. La dernière version de PC-MOS/386, la version 5.01, était compatible avec MS-DOS 5 et requiert une MMU (<a href="https://fr.wikipedia.org/wiki/unit%C3%A9%20de%20gestion%20m%C3%A9moire" title="Définition Wikipédia">unité de gestion mémoire</a>) ce qui la rend de fait incompatible avec les processeurs 8086. Pour le cas d’un processeur 80286, il était cependant possible d’installer une extension matérielle entre le processeur et son support (<em>socket</em>) pour rendre l’ordinateur compatible avec le système.</p>
<h4 id="toc-cpm">CP/M</h4>
<p>Ce n’est pas tout à fait DOS, mais étant donné le lien étroit entre DOS et CP/M, il serait dommage de ne pas le citer. Le code source de CP/M <a href="https://www.theregister.co.uk/2001/11/26/cp_m_collection_is_back/">a été libéré en 2001</a> par l’ayant droit du moment (l’entreprise Lineo). Le code source peut être <a href="https://www.computerhistory.org/atchm/early-digital-research-cpm-source-code/#code">retrouvé sur le site du Computer History Museum</a> et <a href="http://www.cpm.z80.de/source.html">sur le site de passionnés <em>The Unofficial CP/M Web Site</em></a>. Toutes les versions ne sont pas disponibles (1.1, 1.3, 1.4 et 2.0 sont incluses) et certaines sont incomplètes. Certaines parties ont été obtenues par <a href="https://fr.wikipedia.org/wiki/d%C3%A9sassemblage" title="Définition Wikipédia">désassemblage</a>. Initialement, CP/M était surtout programmé en langage <a href="https://fr.wikipedia.org/wiki/PL/M" title="Définition Wikipédia">PL/M</a> et fut réécrit en assembleur. Sont disponibles également des numérisations de <em>listings</em> originaux. Selon l’<a href="https://en.wikipedia.org/wiki/CP/M-86">article Wikipédia anglophone</a>, le code serait couvert par une licence similaire aux licences BSD.</p>
<h4 id="toc-dosemu">DOSEMU</h4>
<p>Un peu comme DOSBox, DOSEMU visait à permettre d’exécuter des applications DOS sous GNU/Linux. DOSEMU réalisait ceci en fournissant une couche de compatibilité pour un véritable système d’exploitation comme FreeDOS. Bien que pleinement fonctionnel et toujours disponible dans certaines distributions GNU/Linux aujourd’hui, le développement semble s’être arrêté en 2012.</p>
<h2 id="toc-cette-libération-peutelle-profiter-au-projet-freedos">Cette libération peut‐elle profiter au projet FreeDOS ?</h2>
<p>Pas directement, le code libéré (version 1.25 et 2.0) est entièrement écrit en assembleur alors que FreeDOS <a href="https://sourceforge.net/p/freedos/svn/HEAD/tree/kernel/trunk/kernel/">combine du code C et de l’assembleur</a>. Cependant cela évite la rétro‐ingénierie pour comprendre le fonctionnement… Sauf que c’est un peu trop tard : le projet FreeDOS a déjà un peu désossé tout DOS pour en comprendre le comportement. Le code source permet cependant de vérifier que cela a été fait correctement. De plus, FreeDOS ayant pour objectif d’être compatible mais pas de refaire forcément à l’identique, s’il peut faire mieux que MS-DOS, il le fera.</p>
<h2 id="toc-quel-intérêt-y-trouver">Quel intérêt y trouver ?</h2>
<h3 id="toc-lintérêt-académique">L’intérêt académique</h3>
<p>L’intérêt académique se situe à la fois sur le plan de la recherche et le plan de l’enseignement. Cela permet aux élèves d’étudier et comprendre comment fonctionnaient les premiers systèmes d’exploitation et donc de mieux appréhender les nouveaux. Cela peut constituer une première étape d’apprentissage de par la relative simplicité de ces systèmes. Il existe aussi d’autres solutions comme <a href="https://fr.wikipedia.org/wiki/Minix">Minix</a>, mais un système comme MS-DOS constitue aussi un cas d’école des avantages et faiblesses de ce type de système.</p>
<h3 id="toc-lintérêt-historiquearchivistique">L’intérêt historique / archivistique</h3>
<p>L’intérêt historique / archivistique réside dans le fait de pouvoir aisément présenter et manipuler un système ancien sans avoir à entretenir un matériel délicat dont les pièces seraient de plus en plus difficiles à trouver. Cela apporte une stabilité qui dépend moins de l’environnement. On peut comparer cet intérêt avec celui de savoir reproduire un objet du Moyen‐Âge pour explorer son usage sans avoir à utiliser l’original et le mettre en danger.</p>
<h3 id="toc-lintérêt-sécuritaire">L’intérêt sécuritaire</h3>
<p>L’intérêt sécuritaire est sans doute l’intérêt le plus susceptible de motiver un travail, voire un travail rémunéré (même si cela devient rare et minoritaire car très spécialisé). Outre les passionnés qui ont besoin d’une machine sans trop de failles de sécurité (et stable) pour jouer, il y a encore bien des organisations (de grosses sociétés ou des états) qui ont de très vieux logiciels souvent critiques qui tournent toujours. Parfois les spécifications sont perdues et il est donc bien plus économique de les faire durer ainsi. L’entreprise Microsoft elle‐même a déjà été réduite à modifier un ancien exécutable pour corriger un problème de sécurité… Modification opérée directement sur le binaire, donc sans recompilation depuis le source. Il existe donc nombre de composants qu’il faut « conserver ainsi », parfois même chez les éditeurs de ces composants…</p>
<h3 id="toc-lintérêt-pratique">L’intérêt pratique</h3>
<p>L’intérêt pratique est donc minime et ne vaut pas le travail qu’il demande. Ce qui motive avant tout c’est la passion de l’informatique. La passion de faire revivre un système d’exploitation qui a connu son heure de gloire. C’est un peu comme rouler avec une voiture de collection : c’est inconfortable mais cela évoque un autre monde qui, avec le temps, est enchanté…</p>
<p>Nous pouvons comparer cela, dans un autre contexte, au langage de programmation <a href="https://fr.wikipedia.org/wiki/Cobol">Cobol</a> crée en 1959. Parce qu’il a toujours été confidentiel et réservé à des clients fortunés, aucune communauté de passionnés ne l’avait adapté à du matériel moderne. C’est seulement très récemment qu’ont été développées des alternatives à base de logiciels libres pseudo‐compatibles pour faire tourner les logiciels Cobol sur des systèmes GNU/Linux plus accessibles financièrement. Mais en attendant, les banques ont dû dépenser des sommes considérables pour maintenir ces logiciels en fonction…</p>
<p>Se pose une dernière question : quels outils pour <s>compiler</s> assembler ?</p>
</div><div><a href="https://linuxfr.org/news/retour-sur-la-liberation-du-code-source-de-ms-dos-1-25-et-2-0-par-microsoft.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/115381/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/news/retour-sur-la-liberation-du-code-source-de-ms-dos-1-25-et-2-0-par-microsoft#comments">ouvrir dans le navigateur</a>
</p>
Thomas Debessegusterhackpalm123Benoît SibaudabriotdePierre JarillonInfoLibreDavy DefaudBAudtheojouedubanjoZeroHeureYsabeau 🧶 🧦David MarecCeteraʭ ☯ collinmraphjyeahmanhttps://linuxfr.org/nodes/115381/comments.atomtag:linuxfr.org,2005:Post/348142014-12-29T10:44:58+01:002014-12-29T10:44:58+01:00Créer un boot CD ubuntu pour installer depuis MS-DOS<p>Bonjour à tous.<br>
Je suis tout nouveau ici, j'utilise ubuntu 12.10 sur mon vieux pc portable, mais je voudrais installer ubuntu ou une variante sur une vieille machine qui fonctionnait sous windows XP. Ladite machine a été formatée totalement, si bien qu'il ne reste que le MS-DOS. Je voudrais donc:<br>
1) soit créer un boot CD reconnu par le DOS pour installer Ubuntu<br>
2) Soit mettre mon disque dur en externe sur mon pc portable pour faire l'installation dessus.<br>
Comment dois je procéder? <br>
Merci d'avance pour votre aide.<br>
Jerem</p><div><a href="https://linuxfr.org/forums/linux-debian-ubuntu/posts/creer-un-boot-cd-ubuntu-pour-installer-depuis-ms-dos.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/104330/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/forums/linux-debian-ubuntu/posts/creer-un-boot-cd-ubuntu-pour-installer-depuis-ms-dos#comments">ouvrir dans le navigateur</a>
</p>
jeremdeffhttps://linuxfr.org/nodes/104330/comments.atomtag:linuxfr.org,2005:Diary/349442014-05-04T09:54:41+02:002014-05-05T13:28:40+02:00OpenJDK JEP 180: HashMap, collisions & attaques par la complexitéLicence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<h2 class="sommaire">Sommaire</h2>
<ul class="toc">
<li><ul>
<li><a href="#pr%C3%A9sentation-des-tables-de-hachage">Présentation des tables de hachage</a></li>
<li><a href="#attaques-par-la-complexit%C3%A9">Attaques par la complexité</a></li>
<li><a href="#java-7u6--alternative-string-hashing">Java 7u6 & "alternative string-hashing"</a></li>
<li><a href="#attaques-par-la-complexit%C3%A9-bis">Attaques par la complexité (bis)</a></li>
<li><a href="#jep-180-une-solution-int%C3%A9ressante">JEP 180: Une solution intéressante</a></li>
<li><a href="#conclusion">Conclusion</a></li>
</ul></li>
</ul><p>Dans ce journal, je vais parler de la <a href="http://openjdk.java.net/jeps/180">JEP 180</a> d'OpenJDK 8 qui propose une solution intéressante aux problèmes d'attaques sur la complexité que rencontrent les tables de hachage.</p>
<p>On a déjà parlé de ce sujet <a href="//linuxfr.org/users/alenvers/journaux/des-tables-de-hachage-en-milieu-hostile">ici même</a> à <a href="//linuxfr.org/news/le-colonel-moutarde-sur-la-table-de-hachage-avec-un-livre-de-maths">plusieurs reprises</a>. Je vais cependant rapidement représenter le problème et l'évolution des discutions. Le lecteur averti sur le sujet ira directement au dernier paragraphe pour voir la proposition de la JEP 180.</p>
<h3 id="présentation-des-tables-de-hachage">Présentation des tables de hachage</h3>
<p>Une table de hachage est une implémentation du type abstrait tableau associatif. Un <a href="http://fr.wikipedia.org/wiki/Tableau_associatif">tableau associatif</a> permet d'associer une clé à une ou plusieurs valeurs, on le nomme aussi parfois dictionnaire. Il fait partie des types abstraits les plus utilisé avec les listes.</p>
<p>Une table de hachage est une implémentation particulière d'un tableau associatif. Elle est aussi la plus courante. Basiquement il s'agit d'un tableau dont les cases contiennent un pointeur vers nil, un élément ou une liste d'élément. On détermine la case à utiliser en appliquant une fonction de hachage à la clé. Idéalement, chaque case ne pointera que vers un unique élément. Dans ce cas les opérations d'insertion, de consultation et de suppression se font en temps constant, noté <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMzEiIHN0cm9rZS13aWR0%0AaD0iMTAiIGQ9Ik0zOTQgMGgtMjc2djE1Yzc0IDQgOTUgMjUgOTUgODB2NDQ5%0AYzAgMzQgLTkgNDkgLTMwIDQ5Yy0xMCAwIC0yNyAtNSAtNDUgLTEybC0yNyAt%0AMTB2MTRsMTc5IDkxbDkgLTN2LTU5N2MwIC00MyAyMCAtNjEgOTUgLTYxdi0x%0ANVoiPjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMjkiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik0yOSA2NjBsMTIgMTZjMTUzIC05MiAyNDQgLTI1OSAy%0ANDQgLTQyOWMwIC0xODUgLTg4IC0zMjcgLTI0NyAtNDI0bC05IDE2YzE0MiAx%0AMTcgMTcwIDIxMSAxNzAgNDA1YzAgMTg3IC0yNSAzMDIgLTE3MCA0MTZaIj48%0AL3BhdGg+PC9kZWZzPjxnIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBz%0AdHJva2Utd2lkdGg9IjAiIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAg%0AMCkiPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS00RiIgeGxpbms6aHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RiI+PC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1B%0ASU4tMjgiIHg9IjcyNyIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlO%0ALTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTi0zMSIgeD0iMTA2%0ANSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOLTMxIj48L3VzZT48%0AdXNlIGhyZWY9IiNTVElYV0VCTUFJTi0yOSIgeD0iMTU3MCIgeT0iMCIgeGxp%0Abms6aHJlZj0iI1NUSVhXRUJNQUlOLTI5Ij48L3VzZT48L2c+PC9zdmc+%0A" alt="O(1)">, c'est à dire qui ne dépend pas du nombre d'élément présent dans la table de hachage. Cependant si la fonction de hachage retourne deux fois la même valeur pour deux clés différentes, ce que l'on nomme collision, alors les deux valeurs sont généralement stockées comme une liste. C'est à dire que maintenant il va falloir parcourir toute cette liste. Dans le pire cas, la fonction de hachage retourne toujours la même valeur, toutes les valeurs vont donc être stockées dans la même case et l'on va devoir parcourir la liste pour chaque opération. La complexité est alors linéaire par rapport au nombre d'éléments dans la structure, noté <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZFIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDYwIDExN2wxNCAtMTNjLTY4IC05MyAtOTMgLTExMyAt%0AMTQwIC0xMTNjLTI1IDAgLTQ3IDE2IC00NyA1NGMwIDEwIDIgMjMgMTYgNzVs%0ANDQgMTYyYzggMzEgMTQgNjcgMTQgNzljMCAxOCAtOSAyOSAtMjQgMjljLTQw%0AIDAgLTg1IC00OSAtMTQ4IC0xNDJjLTQ1IC02NyAtNTMgLTkwIC0xMDAgLTI0%0AOGgtNzVsOTYgMzUwYzEgNSAyIDExIDIgMTdjMCAyMCAtMTQgMjYgLTY1IDI3%0AdjE2YzgxIDE2IDEwOSAyMCAxNjIgMzFsNCAtMmwtNjcgLTIxOCBjMTAwIDE2%0AMCAxNjcgMjIwIDIzMSAyMjBjNDMgMCA2NSAtMjUgNjUgLTYxYzAgLTE4IC00%0AIC0zOSAtMTAgLTYwbC01NiAtMjAzYy0xMCAtMzYgLTE0IC01MyAtMTQgLTYx%0AYzAgLTkgNCAtMTggMTYgLTE4YzE0IDAgMzIgMTYgNjEgNTNjNyA4IDE0IDE3%0AIDIxIDI2WiI+PC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOSIgc3Ry%0Ab2tlLXdpZHRoPSIxMCIgZD0iTTI5IDY2MGwxMiAxNmMxNTMgLTkyIDI0NCAt%0AMjU5IDI0NCAtNDI5YzAgLTE4NSAtODggLTMyNyAtMjQ3IC00MjRsLTkgMTZj%0AMTQyIDExNyAxNzAgMjExIDE3MCA0MDVjMCAxODcgLTI1IDMwMiAtMTcwIDQx%0ANloiPjwvcGF0aD48L2RlZnM+PGcgc3Ryb2tlPSJibGFjayIgZmlsbD0iYmxh%0AY2siIHN0cm9rZS13aWR0aD0iMCIgdHJhbnNmb3JtPSJtYXRyaXgoMSAwIDAg%0ALTEgMCAwKSI+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU5JLTRGIiB4bGluazpo%0AcmVmPSIjU1RJWFdFQk1BSU5JLTRGIj48L3VzZT48dXNlIGhyZWY9IiNTVElY%0AV0VCTUFJTi0yOCIgeD0iNzI3IiB5PSIwIiB4bGluazpocmVmPSIjU1RJWFdF%0AQk1BSU4tMjgiPjwvdXNlPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS02RSIg%0AeD0iMTA2NSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS02RSI+%0APC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU4tMjkiIHg9IjE1NzAiIHk9%0AIjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTi0yOSI+PC91c2U+PC9nPjwv%0Ac3ZnPg==%0A" alt="O(n)">, ce qui est très peu performant. Une table de hachage a donc une complexité moyenne d'<img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMzEiIHN0cm9rZS13aWR0%0AaD0iMTAiIGQ9Ik0zOTQgMGgtMjc2djE1Yzc0IDQgOTUgMjUgOTUgODB2NDQ5%0AYzAgMzQgLTkgNDkgLTMwIDQ5Yy0xMCAwIC0yNyAtNSAtNDUgLTEybC0yNyAt%0AMTB2MTRsMTc5IDkxbDkgLTN2LTU5N2MwIC00MyAyMCAtNjEgOTUgLTYxdi0x%0ANVoiPjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMjkiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik0yOSA2NjBsMTIgMTZjMTUzIC05MiAyNDQgLTI1OSAy%0ANDQgLTQyOWMwIC0xODUgLTg4IC0zMjcgLTI0NyAtNDI0bC05IDE2YzE0MiAx%0AMTcgMTcwIDIxMSAxNzAgNDA1YzAgMTg3IC0yNSAzMDIgLTE3MCA0MTZaIj48%0AL3BhdGg+PC9kZWZzPjxnIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBz%0AdHJva2Utd2lkdGg9IjAiIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAg%0AMCkiPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS00RiIgeGxpbms6aHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RiI+PC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1B%0ASU4tMjgiIHg9IjcyNyIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlO%0ALTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTi0zMSIgeD0iMTA2%0ANSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOLTMxIj48L3VzZT48%0AdXNlIGhyZWY9IiNTVElYV0VCTUFJTi0yOSIgeD0iMTU3MCIgeT0iMCIgeGxp%0Abms6aHJlZj0iI1NUSVhXRUJNQUlOLTI5Ij48L3VzZT48L2c+PC9zdmc+%0A" alt="O(1)"> mais un pire cas en <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZFIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDYwIDExN2wxNCAtMTNjLTY4IC05MyAtOTMgLTExMyAt%0AMTQwIC0xMTNjLTI1IDAgLTQ3IDE2IC00NyA1NGMwIDEwIDIgMjMgMTYgNzVs%0ANDQgMTYyYzggMzEgMTQgNjcgMTQgNzljMCAxOCAtOSAyOSAtMjQgMjljLTQw%0AIDAgLTg1IC00OSAtMTQ4IC0xNDJjLTQ1IC02NyAtNTMgLTkwIC0xMDAgLTI0%0AOGgtNzVsOTYgMzUwYzEgNSAyIDExIDIgMTdjMCAyMCAtMTQgMjYgLTY1IDI3%0AdjE2YzgxIDE2IDEwOSAyMCAxNjIgMzFsNCAtMmwtNjcgLTIxOCBjMTAwIDE2%0AMCAxNjcgMjIwIDIzMSAyMjBjNDMgMCA2NSAtMjUgNjUgLTYxYzAgLTE4IC00%0AIC0zOSAtMTAgLTYwbC01NiAtMjAzYy0xMCAtMzYgLTE0IC01MyAtMTQgLTYx%0AYzAgLTkgNCAtMTggMTYgLTE4YzE0IDAgMzIgMTYgNjEgNTNjNyA4IDE0IDE3%0AIDIxIDI2WiI+PC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOSIgc3Ry%0Ab2tlLXdpZHRoPSIxMCIgZD0iTTI5IDY2MGwxMiAxNmMxNTMgLTkyIDI0NCAt%0AMjU5IDI0NCAtNDI5YzAgLTE4NSAtODggLTMyNyAtMjQ3IC00MjRsLTkgMTZj%0AMTQyIDExNyAxNzAgMjExIDE3MCA0MDVjMCAxODcgLTI1IDMwMiAtMTcwIDQx%0ANloiPjwvcGF0aD48L2RlZnM+PGcgc3Ryb2tlPSJibGFjayIgZmlsbD0iYmxh%0AY2siIHN0cm9rZS13aWR0aD0iMCIgdHJhbnNmb3JtPSJtYXRyaXgoMSAwIDAg%0ALTEgMCAwKSI+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU5JLTRGIiB4bGluazpo%0AcmVmPSIjU1RJWFdFQk1BSU5JLTRGIj48L3VzZT48dXNlIGhyZWY9IiNTVElY%0AV0VCTUFJTi0yOCIgeD0iNzI3IiB5PSIwIiB4bGluazpocmVmPSIjU1RJWFdF%0AQk1BSU4tMjgiPjwvdXNlPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS02RSIg%0AeD0iMTA2NSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS02RSI+%0APC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU4tMjkiIHg9IjE1NzAiIHk9%0AIjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTi0yOSI+PC91c2U+PC9nPjwv%0Ac3ZnPg==%0A" alt="O(n)">. Il est donc crucial d'avoir une fonction de hachage performante. Les personnes n'étant pas à l'aise avec l'implémentation d'une table de hachage ou les concepts précédant auront tout intérêt à consulter la page <a href="http://fr.wikipedia.org/wiki/Table_de_hachage">Wikipédia</a> qui est assez complète.</p>
<p>Cet article s'accompagne d'un benchmark écrit avec <a href="http://openjdk.java.net/projects/code-tools/jmh/">JMH</a> qui va nous permettre d'observer comment se comporte la classe <a href="http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html">HashMap</a> de Java dans différentes circonstances. Le code de ce benchmark est extrêmement simple:</p>
<pre><code class="java"> <span class="nd">@GenerateMicroBenchmark</span>
<span class="kd">public</span> <span class="kt">int</span> <span class="nf">put</span><span class="o">()</span> <span class="o">{</span>
<span class="n">HashMap</span><span class="o"><</span><span class="n">String</span><span class="o">,</span> <span class="n">Object</span><span class="o">></span> <span class="n">map</span> <span class="o">=</span> <span class="k">new</span> <span class="n">HashMap</span><span class="o"><</span><span class="n">String</span><span class="o">,</span> <span class="n">Object</span><span class="o">>();</span>
<span class="k">for</span> <span class="o">(</span><span class="n">String</span> <span class="nl">s:</span> <span class="n">strings</span><span class="o">)</span> <span class="o">{</span>
<span class="n">map</span><span class="o">.</span><span class="na">put</span><span class="o">(</span><span class="n">s</span><span class="o">,</span> <span class="n">s</span><span class="o">);</span>
<span class="o">}</span>
<span class="k">return</span> <span class="n">map</span><span class="o">.</span><span class="na">size</span><span class="o">();</span>
<span class="o">}</span></code></pre>
<p>Nous insérons une collection de chaîne de caractère dans une HashMap et nous mesurons le temps moyen de cette opération. Mesurer l'insertion est une métrique correcte pour ce que nous souhaitons mesurer car lors d'une insertion, dans le cas où la clé existe déjà il faut remplacer la valeur existante. Il faut donc rechercher parmi toutes les clés déjà existantes dans cette case. Les comportements en consultation et en suppressions seront similaires à celui que nous observons. Dans tous les cas, en cas de collision, il faudra traverser toutes les valeurs de cette case. Exemple du code de la méthode <em>put()</em>:</p>
<pre><code class="java"> <span class="kd">public</span> <span class="n">V</span> <span class="nf">put</span><span class="o">(</span><span class="n">K</span> <span class="n">key</span><span class="o">,</span> <span class="n">V</span> <span class="n">value</span><span class="o">)</span> <span class="o">{</span>
<span class="k">if</span> <span class="o">(</span><span class="n">key</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
<span class="k">return</span> <span class="nf">putForNullKey</span><span class="o">(</span><span class="n">value</span><span class="o">);</span>
<span class="kt">int</span> <span class="n">hash</span> <span class="o">=</span> <span class="n">hash</span><span class="o">(</span><span class="n">key</span><span class="o">.</span><span class="na">hashCode</span><span class="o">());</span>
<span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">indexFor</span><span class="o">(</span><span class="n">hash</span><span class="o">,</span> <span class="n">table</span><span class="o">.</span><span class="na">length</span><span class="o">);</span>
<span class="k">for</span> <span class="o">(</span><span class="n">Entry</span><span class="o"><</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">></span> <span class="n">e</span> <span class="o">=</span> <span class="n">table</span><span class="o">[</span><span class="n">i</span><span class="o">];</span> <span class="n">e</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">;</span> <span class="n">e</span> <span class="o">=</span> <span class="n">e</span><span class="o">.</span><span class="na">next</span><span class="o">)</span> <span class="o">{</span>
<span class="n">Object</span> <span class="n">k</span><span class="o">;</span>
<span class="k">if</span> <span class="o">(</span><span class="n">e</span><span class="o">.</span><span class="na">hash</span> <span class="o">==</span> <span class="n">hash</span> <span class="o">&&</span> <span class="o">((</span><span class="n">k</span> <span class="o">=</span> <span class="n">e</span><span class="o">.</span><span class="na">key</span><span class="o">)</span> <span class="o">==</span> <span class="n">key</span> <span class="o">||</span> <span class="n">key</span><span class="o">.</span><span class="na">equals</span><span class="o">(</span><span class="n">k</span><span class="o">)))</span> <span class="o">{</span>
<span class="n">V</span> <span class="n">oldValue</span> <span class="o">=</span> <span class="n">e</span><span class="o">.</span><span class="na">value</span><span class="o">;</span>
<span class="n">e</span><span class="o">.</span><span class="na">value</span> <span class="o">=</span> <span class="n">value</span><span class="o">;</span>
<span class="n">e</span><span class="o">.</span><span class="na">recordAccess</span><span class="o">(</span><span class="k">this</span><span class="o">);</span>
<span class="k">return</span> <span class="n">oldValue</span><span class="o">;</span>
<span class="o">}</span>
<span class="o">}</span>
<span class="n">modCount</span><span class="o">++;</span>
<span class="n">addEntry</span><span class="o">(</span><span class="n">hash</span><span class="o">,</span> <span class="n">key</span><span class="o">,</span> <span class="n">value</span><span class="o">,</span> <span class="n">i</span><span class="o">);</span>
<span class="k">return</span> <span class="kc">null</span><span class="o">;</span>
<span class="o">}</span></code></pre>
<p>On peut clairement y voir les étapes suivantes:</p>
<ul>
<li>On calcule le <code>hash</code> de la clé, qui va déterminer la case <code>i</code>
</li>
<li>On itère sur toutes les clés présente dans la case <code>i</code> pour regarder si une correspond à <code>key</code>
<ul>
<li>Si oui, alors on remplace la valeur existante par <code>value</code>
</li>
<li>Sinon, on ajoute un nouvel élément pour cette clé à la fin de la liste</li>
</ul>
</li>
</ul><p>Comme on le voit avec la ligne suivante <code>int hash = hash(key.hashCode());</code>, en java la case est calculée à partir de la valeur retourné par <code>hashCode()</code>. On applique en plus la fonction <code>hash()</code> afin d'améliorer un peu la distribution des clés. En effet, <code>i</code> est calculé modulo la taille de la table qui est une puissance de deux, et il est facile d'avoir des effets néfastes:</p>
<pre><code class="java"> <span class="cm">/**</span>
<span class="cm"> * Applies a supplemental hash function to a given hashCode, which</span>
<span class="cm"> * defends against poor quality hash functions. This is critical</span>
<span class="cm"> * because HashMap uses power-of-two length hash tables, that</span>
<span class="cm"> * otherwise encounter collisions for hashCodes that do not differ</span>
<span class="cm"> * in lower bits. Note: Null keys always map to hash 0, thus index 0.</span>
<span class="cm"> */</span>
<span class="kd">static</span> <span class="kt">int</span> <span class="nf">hash</span><span class="o">(</span><span class="kt">int</span> <span class="n">h</span><span class="o">)</span> <span class="o">{</span>
<span class="c1">// This function ensures that hashCodes that differ only by</span>
<span class="c1">// constant multiples at each bit position have a bounded</span>
<span class="c1">// number of collisions (approximately 8 at default load factor).</span>
<span class="n">h</span> <span class="o">^=</span> <span class="o">(</span><span class="n">h</span> <span class="o">>>></span> <span class="mi">20</span><span class="o">)</span> <span class="o">^</span> <span class="o">(</span><span class="n">h</span> <span class="o">>>></span> <span class="mi">12</span><span class="o">);</span>
<span class="k">return</span> <span class="n">h</span> <span class="o">^</span> <span class="o">(</span><span class="n">h</span> <span class="o">>>></span> <span class="mi">7</span><span class="o">)</span> <span class="o">^</span> <span class="o">(</span><span class="n">h</span> <span class="o">>>></span> <span class="mi">4</span><span class="o">);</span>
<span class="o">}</span></code></pre>
<p>Enfin le cas qui va nous intéresser particulièrement ici est celui des chaines de caractères comme clé car c'est une utilisation extrêmement courante et exposée aux attaques. Souvent les données fournis par l'utilisateur sont des chaînes de caractères plutôt que des objets complexes. Par exemple les en-tête HTTP sont souvent stocké dans un tableau associatif.</p>
<p>Regardons donc comment est implémenté le <code>hashCode</code> de la classe <code>String</code>:</p>
<pre><code class="java"> <span class="cm">/**</span>
<span class="cm"> * Returns a hash code for this string. The hash code for a</span>
<span class="cm"> * <code>String</code> object is computed as</span>
<span class="cm"> * <blockquote><pre></span>
<span class="cm"> * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]</span>
<span class="cm"> * </pre></blockquote></span>
<span class="cm"> * using <code>int</code> arithmetic, where <code>s[i]</code> is the</span>
<span class="cm"> * <i>i</i>th character of the string, <code>n</code> is the length of</span>
<span class="cm"> * the string, and <code>^</code> indicates exponentiation.</span>
<span class="cm"> * (The hash value of the empty string is zero.)</span>
<span class="cm"> *</span>
<span class="cm"> * @return a hash code value for this object.</span>
<span class="cm"> */</span>
<span class="kd">public</span> <span class="kt">int</span> <span class="nf">hashCode</span><span class="o">()</span> <span class="o">{</span>
<span class="kt">int</span> <span class="n">h</span> <span class="o">=</span> <span class="n">hash</span><span class="o">;</span>
<span class="kt">int</span> <span class="n">len</span> <span class="o">=</span> <span class="n">count</span><span class="o">;</span>
<span class="k">if</span> <span class="o">(</span><span class="n">h</span> <span class="o">==</span> <span class="mi">0</span> <span class="o">&&</span> <span class="n">len</span> <span class="o">></span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
<span class="kt">int</span> <span class="n">off</span> <span class="o">=</span> <span class="n">offset</span><span class="o">;</span>
<span class="kt">char</span> <span class="n">val</span><span class="o">[]</span> <span class="o">=</span> <span class="n">value</span><span class="o">;</span>
<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">len</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
<span class="n">h</span> <span class="o">=</span> <span class="mi">31</span><span class="o">*</span><span class="n">h</span> <span class="o">+</span> <span class="n">val</span><span class="o">[</span><span class="n">off</span><span class="o">++];</span>
<span class="o">}</span>
<span class="n">hash</span> <span class="o">=</span> <span class="n">h</span><span class="o">;</span>
<span class="o">}</span>
<span class="k">return</span> <span class="n">h</span><span class="o">;</span>
<span class="o">}</span></code></pre>
<p>Cela correspond à une fonction de hachage non cryptographique très courante pour les chaînes de caractères. C'est une variante du <em>Bernstein hash</em>, aussi appelé djb2. Elle a ceci d'intéressant qu'elle est utilisée par beaucoup plateformes et qu'expliquer pourquoi elle marche et comment et pourquoi ont été choisi les valeurs est assez difficile. Les gens intéressés pourront découvrir d'<a href="http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx">autres fonctions</a> ainsi que passer beaucoup de temps à chercher les réponses à la question précédente.</p>
<p>Dans tous les cas nous appellerons cette variante de dbj2 sous le doux nom de DJBX31A.</p>
<p>Maintenant exécutons notre benchmark en utilisant Java 6u45 avec des chaines aléatoires de taille constante, 15 caractères, pour des collections allant de 10 à 30.000 éléments. Le résultat est le suivant:</p>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f756e706f7274616e742d74686f75676874732f3230313430355f4a45505f3138302f6d61737465722f4a45505f3138305f616e616c797369735f66696c65732f4a45505f3138305f616e616c797369735f31305f312e706e673f7261773d74727565/JEP_180_analysis_10_1.png?raw=true" alt="png" title="Source : https://raw.githubusercontent.com/unportant-thoughts/201405_JEP_180/master/JEP_180_analysis_files/JEP_180_analysis_10_1.png?raw=true"></p>
<p>Dans ce cas nous avons le comportement normal attendu. Il y a peu de collisions. En moyenne le temps d'insertion est constant et ne dépend pas de la taille de la collection, <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMzEiIHN0cm9rZS13aWR0%0AaD0iMTAiIGQ9Ik0zOTQgMGgtMjc2djE1Yzc0IDQgOTUgMjUgOTUgODB2NDQ5%0AYzAgMzQgLTkgNDkgLTMwIDQ5Yy0xMCAwIC0yNyAtNSAtNDUgLTEybC0yNyAt%0AMTB2MTRsMTc5IDkxbDkgLTN2LTU5N2MwIC00MyAyMCAtNjEgOTUgLTYxdi0x%0ANVoiPjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMjkiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik0yOSA2NjBsMTIgMTZjMTUzIC05MiAyNDQgLTI1OSAy%0ANDQgLTQyOWMwIC0xODUgLTg4IC0zMjcgLTI0NyAtNDI0bC05IDE2YzE0MiAx%0AMTcgMTcwIDIxMSAxNzAgNDA1YzAgMTg3IC0yNSAzMDIgLTE3MCA0MTZaIj48%0AL3BhdGg+PC9kZWZzPjxnIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBz%0AdHJva2Utd2lkdGg9IjAiIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAg%0AMCkiPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS00RiIgeGxpbms6aHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RiI+PC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1B%0ASU4tMjgiIHg9IjcyNyIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlO%0ALTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTi0zMSIgeD0iMTA2%0ANSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOLTMxIj48L3VzZT48%0AdXNlIGhyZWY9IiNTVElYV0VCTUFJTi0yOSIgeD0iMTU3MCIgeT0iMCIgeGxp%0Abms6aHJlZj0iI1NUSVhXRUJNQUlOLTI5Ij48L3VzZT48L2c+PC9zdmc+%0A" alt="O(1)">. Nous voyons donc que la courbe est linéaire puisque nous répétons <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiAxLjcxNGV4OyBoZWlnaHQ6IDEuNzE0ZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC4xNDNleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9Ii0xNSAtNjc5%0ALjI1ODEyMzI1NTE1NDkgNzQ3IDcyMC41MTYyNDY1MTAzMSIgeG1sbnM9Imh0%0AdHA6Ly93d3cudzMub3JnLzIwMDAvc3ZnIj48ZGVmcyBpZD0iTWF0aEpheF9T%0AVkdfZ2x5cGhzIj48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTRFIiBzdHJva2Ut%0Ad2lkdGg9IjEwIiBkPSJNNzI3IDY1M3YtMTZjLTYzIC0xNCAtNjUgLTE2IC0x%0AMDIgLTE0NWwtMTQ2IC01MDdoLTE4bC0yMzAgNTUwbC0xMTQgLTQyMmMtNiAt%0AMjEgLTkgLTQxIC05IC01NGMwIC0yOCAxOCAtMzkgNzAgLTQzdi0xNmgtMTk4%0AdjE2YzU2IDggNzAgMjQgMTA2IDE1MmwxMTcgNDE1Yy0xNSAzNSAtMzkgNTQg%0ALTg2IDU0djE2aDE2MGwyMDcgLTQ5OWwxMDYgMzg4YzYgMjEgOCAzMiA4IDQ0%0AYzAgMzYgLTEyIDQ2IC02OSA1MXYxNmgxOThaIj48L3BhdGg+PC9kZWZzPjxn%0AIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBzdHJva2Utd2lkdGg9IjAi%0AIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAgMCkiPjx1c2UgaHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RSIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS00%0ARSI+PC91c2U+PC9nPjwvc3ZnPg==%0A" alt="N"> fois une opération prenant un temps donné. Nous voyons aussi que nous arrivons à insérer environ 20 000 éléments par milliseconde.</p>
<h3 id="attaques-par-la-complexité">Attaques par la complexité</h3>
<p>Si vous avez bien suivi la première partie, vous savez que la performance d'une table de hachage dépend du nombre de collisions et donc de la qualité de sa fonction de hachage. Par nature une table de hachage ne permet pas de garantir que les opérations seront en <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMzEiIHN0cm9rZS13aWR0%0AaD0iMTAiIGQ9Ik0zOTQgMGgtMjc2djE1Yzc0IDQgOTUgMjUgOTUgODB2NDQ5%0AYzAgMzQgLTkgNDkgLTMwIDQ5Yy0xMCAwIC0yNyAtNSAtNDUgLTEybC0yNyAt%0AMTB2MTRsMTc5IDkxbDkgLTN2LTU5N2MwIC00MyAyMCAtNjEgOTUgLTYxdi0x%0ANVoiPjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMjkiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik0yOSA2NjBsMTIgMTZjMTUzIC05MiAyNDQgLTI1OSAy%0ANDQgLTQyOWMwIC0xODUgLTg4IC0zMjcgLTI0NyAtNDI0bC05IDE2YzE0MiAx%0AMTcgMTcwIDIxMSAxNzAgNDA1YzAgMTg3IC0yNSAzMDIgLTE3MCA0MTZaIj48%0AL3BhdGg+PC9kZWZzPjxnIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBz%0AdHJva2Utd2lkdGg9IjAiIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAg%0AMCkiPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS00RiIgeGxpbms6aHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RiI+PC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1B%0ASU4tMjgiIHg9IjcyNyIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlO%0ALTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTi0zMSIgeD0iMTA2%0ANSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOLTMxIj48L3VzZT48%0AdXNlIGhyZWY9IiNTVElYV0VCTUFJTi0yOSIgeD0iMTU3MCIgeT0iMCIgeGxp%0Abms6aHJlZj0iI1NUSVhXRUJNQUlOLTI5Ij48L3VzZT48L2c+PC9zdmc+%0A" alt="O(1)">, il s'agit seulement du cas moyen quand tout se passe bien. La performance au pire cas est <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZFIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDYwIDExN2wxNCAtMTNjLTY4IC05MyAtOTMgLTExMyAt%0AMTQwIC0xMTNjLTI1IDAgLTQ3IDE2IC00NyA1NGMwIDEwIDIgMjMgMTYgNzVs%0ANDQgMTYyYzggMzEgMTQgNjcgMTQgNzljMCAxOCAtOSAyOSAtMjQgMjljLTQw%0AIDAgLTg1IC00OSAtMTQ4IC0xNDJjLTQ1IC02NyAtNTMgLTkwIC0xMDAgLTI0%0AOGgtNzVsOTYgMzUwYzEgNSAyIDExIDIgMTdjMCAyMCAtMTQgMjYgLTY1IDI3%0AdjE2YzgxIDE2IDEwOSAyMCAxNjIgMzFsNCAtMmwtNjcgLTIxOCBjMTAwIDE2%0AMCAxNjcgMjIwIDIzMSAyMjBjNDMgMCA2NSAtMjUgNjUgLTYxYzAgLTE4IC00%0AIC0zOSAtMTAgLTYwbC01NiAtMjAzYy0xMCAtMzYgLTE0IC01MyAtMTQgLTYx%0AYzAgLTkgNCAtMTggMTYgLTE4YzE0IDAgMzIgMTYgNjEgNTNjNyA4IDE0IDE3%0AIDIxIDI2WiI+PC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOSIgc3Ry%0Ab2tlLXdpZHRoPSIxMCIgZD0iTTI5IDY2MGwxMiAxNmMxNTMgLTkyIDI0NCAt%0AMjU5IDI0NCAtNDI5YzAgLTE4NSAtODggLTMyNyAtMjQ3IC00MjRsLTkgMTZj%0AMTQyIDExNyAxNzAgMjExIDE3MCA0MDVjMCAxODcgLTI1IDMwMiAtMTcwIDQx%0ANloiPjwvcGF0aD48L2RlZnM+PGcgc3Ryb2tlPSJibGFjayIgZmlsbD0iYmxh%0AY2siIHN0cm9rZS13aWR0aD0iMCIgdHJhbnNmb3JtPSJtYXRyaXgoMSAwIDAg%0ALTEgMCAwKSI+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU5JLTRGIiB4bGluazpo%0AcmVmPSIjU1RJWFdFQk1BSU5JLTRGIj48L3VzZT48dXNlIGhyZWY9IiNTVElY%0AV0VCTUFJTi0yOCIgeD0iNzI3IiB5PSIwIiB4bGluazpocmVmPSIjU1RJWFdF%0AQk1BSU4tMjgiPjwvdXNlPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS02RSIg%0AeD0iMTA2NSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS02RSI+%0APC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU4tMjkiIHg9IjE1NzAiIHk9%0AIjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTi0yOSI+PC91c2U+PC9nPjwv%0Ac3ZnPg==%0A" alt="O(n)">.</p>
<p>Ce fait est connu de tout étudiant ayant suivi une introduction à l'algorithmique. Seulement il y a quelques années certains ont eu l'idée d'utiliser ce pire cas pour faire des dénis de service. C'est une attaque par la complexité. L'idée est simple, beaucoup d'application stockent en mémoire des chaînes de caractères fournies par un utilisateur dans une table de hachage. S'il arrive à fournir des chaînes qui vont systématiquement créer des collisions, alors il va pouvoir ralentir très fortement le système.</p>
<p>L'idée n'est pas nouvelle, elle a été parfaitement <a href="http://madchat.fr/reseau/dos/CrosbyWallach_UsenixSec2003.pdf">documentée</a> en 2003 par Scott A. Crosby et Dan S. Wallach lors de l'Usenix-Sec. Ils avaient alors étudié Perl, qui avait réagi et fourni un correctif. Tout le monde a alors oublié cette histoire pendant quelques années.</p>
<p>En 2011, Alexander Klink et Julian Wälde se souviennent de cette histoire et partent alors explorer ce qu'il est possible de faire avec presque 10 ans après. Les <a href="http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf">slides</a> du 28C3 décrivent très bien ce qu'ils trouvent. En gros presque toutes les plateformes majeures sont vulnérable de PHP à Java en passant par Python puisque tout le monde ou presque utilise une variante de djb2, pour lequel il est très facile de générer des collisions. Le résultat c'est qu'on peut faire un déni de service sur a peu près n'importe quoi avec très peu de données. Avec 2MB de données ils arrivent à occuper un processeur pendant plus d'une demi-heure.</p>
<p>Le benchmark suivant compare la courbe précédente avec une où toutes les clés se retrouvent dans la même case car on génère spécialement les clés pour que DJBX31A retourne toujours la même valeur bien que les chaînes soient différentes.</p>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f756e706f7274616e742d74686f75676874732f3230313430355f4a45505f3138302f6d61737465722f4a45505f3138305f616e616c797369735f66696c65732f4a45505f3138305f616e616c797369735f31355f312e706e673f7261773d74727565/JEP_180_analysis_15_1.png?raw=true" alt="png" title="Source : https://raw.githubusercontent.com/unportant-thoughts/201405_JEP_180/master/JEP_180_analysis_files/JEP_180_analysis_15_1.png?raw=true"></p>
<p>Comme on peut le voir l'effet est plutôt dramatique. Chaque insertion dépend donc maintenant du nombre d'éléments dans la table de hachage. Si vous vous rappelez du code de la méthode <em>put()</em>, nous avons à parcourir tous les éléments à chaque fois. Puisque nous allons insérer un nouvel élément, il faut vérifier tous les autres. La courbe devient donc quadratique. Pour 20 000 éléments on peut voir que l'on est déjà 1000 fois plus lent. Vous pouvez facilement extrapoler pour 50 000 ou 100 000.</p>
<h3 id="java-7u6--alternative-string-hashing">Java 7u6 & "alternative string-hashing"</h3>
<p>Comme la plupart des plateformes impactées par cette découverte, Java cherche une solution. Et beaucoup vont choisir une solution similaire. L'idée est qu'il faut empêcher à un utilisateur de pouvoir générer des collisions. Une solution est d'utiliser des fonctions de hachage cryptographique qui sont conçues pour cela. En pratique ce n'est pas possible car elles sont beaucoup trop lentes (grossièrement il y a minimum un ordre de grandeur d'écart). Le consensus est alors de migrer vers une autre fonction de hachage: <a href="http://en.wikipedia.org/wiki/MurmurHash">Murmur</a> 2 ou 3. Murmur est une bonne fonction de hachage non cryptographique, elle est rapide et fournie de bons résultats. En plus on peut l'initialiser avec une graine qui va conditionner la valeur de sortie. L'idée est donc de générer la graine à l'exécution. Il devient alors compliqué à l'utilisateur de générer des collisions car il a besoin de la graine et qu'il n'y a pas accès.</p>
<p>Python utilise cette solution et décide de <a href="http://bugs.python.org/issue13703">changer sa fonction de hachage pour Murmur</a>.</p>
<p>Java veut faire de même mais a un problème supplémentaire. La Javadoc de la méthode <code>hashCode</code> de String documente l'implémentation sous-jacente:</p>
<pre><code class="java"> <span class="cm">/**</span>
<span class="cm"> * Returns a hash code for this string. The hash code for a</span>
<span class="cm"> * <code>String</code> object is computed as</span>
<span class="cm"> * <blockquote><pre></span>
<span class="cm"> * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]</span>
<span class="cm"> * </pre></blockquote></span>
<span class="cm"> * using <code>int</code> arithmetic, where <code>s[i]</code> is the</span>
<span class="cm"> * <i>i</i>th character of the string, <code>n</code> is the length of</span>
<span class="cm"> * the string, and <code>^</code> indicates exponentiation.</span>
<span class="cm"> * (The hash value of the empty string is zero.)</span>
<span class="cm"> *</span>
<span class="cm"> * @return a hash code value for this object.</span>
<span class="cm"> */</span></code></pre>
<p>DJBX31A fait donc partie du contrat de la classe, et on ne peut pas le changer sans risque de casser la compatibilité et le comportement des applications. C'est une règle stricte du côté de Java.</p>
<p>Pour cette raison on imagine donc ce qui est pour moi l'un des patchs les plus dégueulasses de l'histoire du JDK qui a été livré en Java <a href="http://www.oracle.com/technetwork/java/javase/7u6-relnotes-1729681.html">7u6</a>. En gros on ne touche à rien de ce qui existe. On rajoute une nouvelle méthode <code>hash32</code> à la classe String qui repose sur Murmur.</p>
<pre><code class="java"> <span class="kt">int</span> <span class="nf">hash32</span><span class="o">()</span> <span class="o">{</span>
<span class="kt">int</span> <span class="n">h</span> <span class="o">=</span> <span class="n">hash32</span><span class="o">;</span>
<span class="k">if</span> <span class="o">(</span><span class="mi">0</span> <span class="o">==</span> <span class="n">h</span><span class="o">)</span> <span class="o">{</span>
<span class="c1">// harmless data race on hash32 here.</span>
<span class="n">h</span> <span class="o">=</span> <span class="n">sun</span><span class="o">.</span><span class="na">misc</span><span class="o">.</span><span class="na">Hashing</span><span class="o">.</span><span class="na">murmur3_32</span><span class="o">(</span><span class="n">HASHING_SEED</span><span class="o">,</span> <span class="n">value</span><span class="o">,</span> <span class="mi">0</span><span class="o">,</span>
<span class="n">value</span><span class="o">.</span><span class="na">length</span><span class="o">);</span>
<span class="c1">// ensure result is not zero to avoid recalcing</span>
<span class="n">h</span> <span class="o">=</span> <span class="o">(</span><span class="mi">0</span> <span class="o">!=</span> <span class="n">h</span><span class="o">)</span> <span class="o">?</span> <span class="n">h</span> <span class="o">:</span> <span class="mi">1</span><span class="o">;</span>
<span class="n">hash32</span> <span class="o">=</span> <span class="n">h</span><span class="o">;</span>
<span class="o">}</span>
<span class="k">return</span> <span class="n">h</span><span class="o">;</span>
<span class="o">}</span></code></pre>
<p>Maintenant on patch les collections utilisant des fonctions de hachage pour faire la chose suivante: On regarde le type de l'élément, si c'est String alors on invoque <code>hash32</code> par une introspection dédiée car la méthode n'est pas publique, sinon on invoque <code>hashCode</code>. Seulement les String sont immutables, et la valeur de <code>hashCode</code> était cachée pour éviter de le recalculer à chaque fois. On doit donc faire de même avec <code>hash32</code> qui impose donc 4 octets supplémentaire à chaque instance de String. Pour finir on initialise <code>HASHING_SEED</code> dynamiquement à l'initialisation pour empêcher les collisions.</p>
<p>C'est cool on n'a pas touché à <code>hashCode</code> ! Seulement voilà le comportement des applications peut toujours changer même en remplaçant la fonction de hachage uniquement dans les collections. Alors on rajoute un flag pour décider si on veut oui ou non utiliser le <em>alternative string-hash</em> dans les collections.</p>
<p>Voir <a href="http://permalink.gmane.org/gmane.comp.java.openjdk.core-%20libs.devel/10361">le mail</a> sur la mailing list d'OpenJDK ainsi que le <a href="http://cr.openjdk.java.net/%7Emduigou/althashing7/8/webrev/">patch</a>.</p>
<p>Voilà ça pique les yeux mais ça fait le job ! Refaisons tourner le même benchmark avec Java 7u55:</p>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f756e706f7274616e742d74686f75676874732f3230313430355f4a45505f3138302f6d61737465722f4a45505f3138305f616e616c797369735f66696c65732f4a45505f3138305f616e616c797369735f31395f312e706e673f7261773d74727565/JEP_180_analysis_19_1.png?raw=true" alt="png" title="Source : https://raw.githubusercontent.com/unportant-thoughts/201405_JEP_180/master/JEP_180_analysis_files/JEP_180_analysis_19_1.png?raw=true"></p>
<p>Ah oui j'ai dit qu'il y avait une option pour <em>l'alternative string-hashing</em> mais j'ai pas dit qu'elle était activée par défaut… Recommençons avec <code>-Djdk.map.althashing.threshold=1</code></p>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f756e706f7274616e742d74686f75676874732f3230313430355f4a45505f3138302f6d61737465722f4a45505f3138305f616e616c797369735f66696c65732f4a45505f3138305f616e616c797369735f32315f312e706e673f7261773d74727565/JEP_180_analysis_21_1.png?raw=true" alt="png" title="Source : https://raw.githubusercontent.com/unportant-thoughts/201405_JEP_180/master/JEP_180_analysis_files/JEP_180_analysis_21_1.png?raw=true"></p>
<p>C'est mieux non ? Bon OK par défaut on est toujours vulnérable trois ans après…</p>
<h3 id="attaques-par-la-complexité-bis">Attaques par la complexité (bis)</h3>
<p>Seulement voilà, entre temps quelques-uns ont commencés à creuser le problème. Ils ont attaqué Murmur3 avec graine qui n'a pas <a href="http://www.eng.tau.ac.il/%7Eyash/C2_039_Wool.pdf">tenu</a> très longtemps. Ca a d'ailleurs été <a href="http://www.youtube.com/watch?v=wGYj8fhhUVA">présenté au 29c3</a>. Dans les speakers on notera DJB, oui c'est le même.</p>
<p>Rebelote, tous ceux qui sont passés à Murmur sont impactés ainsi que quelques copains dont les fonctions ont aussi été cassées. C'est un peu mois trivial de générer des collisions avec Murmur mais le travail difficile a été fait pour nous. On n'a qu'à écrire le code…</p>
<p>Essayons de refaire tourner notre benchmark en générant des collisions contre Murmur:</p>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f756e706f7274616e742d74686f75676874732f3230313430355f4a45505f3138302f6d61737465722f4a45505f3138305f616e616c797369735f66696c65732f4a45505f3138305f616e616c797369735f32355f312e706e673f7261773d74727565/JEP_180_analysis_25_1.png?raw=true" alt="png" title="Source : https://raw.githubusercontent.com/unportant-thoughts/201405_JEP_180/master/JEP_180_analysis_files/JEP_180_analysis_25_1.png?raw=true"></p>
<p>Cette fois nous comparons le comportement usuel avec:</p>
<ul>
<li>Des collisions contre DJBX31A sans <em>l'alternative string-hashing</em>
</li>
<li>Des collisions contre Murmur3 avec <em>l'alternative string-hashing</em>
</li>
</ul><p>(Je n'ai pas investigué les deux points à 15k et 25k qui sont très étranges. Le générateur passe les tests unitaires et les résultats eux sont stables…)</p>
<p>C'est grosso modo la même chose. On a donc fait un patch moche qui ne sert plus à rien puisque dans les deux cas on est vulnérable…</p>
<h3 id="jep-180-une-solution-intéressante">JEP 180: Une solution intéressante</h3>
<p>Maintenant qu'est-ce qu'on fait ?</p>
<p>En même temps qu'ils ont cassé Murmur avec graine, DJB et ses potes ont proposé une nouvelle fonction de hachage: <a href="http://en.wikipedia.org/wiki/SipHash">SipHash</a>. Elle est vendue comme étant aussi rapide que les précédentes mais résistante aux attaques par collisions.</p>
<p>La plupart des plateformes ont migré vers SipHash. Python par exemple. Et comme on s'est déjà fait avoir une fois on en profite pour faire la <a href="http://legacy.python.org/dev/peps/pep-0456/">PEP 456</a> qui permet d'avoir des fonctions de hash interchangeable pour les chaîne de caractères et tableaux d'octets. On bascule à SipHash mais comme on sait que ca risque de recommencer, on prévoit le coup…</p>
<p>Du côté de Java on a toujours le même problème avec <code>hashCode</code>, rechanger hash32 fait prendre quelques risque aussi et le patch initial étant "crado" on aimerait bien s'en débarrasser. On choisit donc une approche radicalement différente. Plutôt que de chercher une fonction de hachage parfaite, on rebascule sur DJBX31A. On s'applique plutôt à résoudre le problème du <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZFIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDYwIDExN2wxNCAtMTNjLTY4IC05MyAtOTMgLTExMyAt%0AMTQwIC0xMTNjLTI1IDAgLTQ3IDE2IC00NyA1NGMwIDEwIDIgMjMgMTYgNzVs%0ANDQgMTYyYzggMzEgMTQgNjcgMTQgNzljMCAxOCAtOSAyOSAtMjQgMjljLTQw%0AIDAgLTg1IC00OSAtMTQ4IC0xNDJjLTQ1IC02NyAtNTMgLTkwIC0xMDAgLTI0%0AOGgtNzVsOTYgMzUwYzEgNSAyIDExIDIgMTdjMCAyMCAtMTQgMjYgLTY1IDI3%0AdjE2YzgxIDE2IDEwOSAyMCAxNjIgMzFsNCAtMmwtNjcgLTIxOCBjMTAwIDE2%0AMCAxNjcgMjIwIDIzMSAyMjBjNDMgMCA2NSAtMjUgNjUgLTYxYzAgLTE4IC00%0AIC0zOSAtMTAgLTYwbC01NiAtMjAzYy0xMCAtMzYgLTE0IC01MyAtMTQgLTYx%0AYzAgLTkgNCAtMTggMTYgLTE4YzE0IDAgMzIgMTYgNjEgNTNjNyA4IDE0IDE3%0AIDIxIDI2WiI+PC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOSIgc3Ry%0Ab2tlLXdpZHRoPSIxMCIgZD0iTTI5IDY2MGwxMiAxNmMxNTMgLTkyIDI0NCAt%0AMjU5IDI0NCAtNDI5YzAgLTE4NSAtODggLTMyNyAtMjQ3IC00MjRsLTkgMTZj%0AMTQyIDExNyAxNzAgMjExIDE3MCA0MDVjMCAxODcgLTI1IDMwMiAtMTcwIDQx%0ANloiPjwvcGF0aD48L2RlZnM+PGcgc3Ryb2tlPSJibGFjayIgZmlsbD0iYmxh%0AY2siIHN0cm9rZS13aWR0aD0iMCIgdHJhbnNmb3JtPSJtYXRyaXgoMSAwIDAg%0ALTEgMCAwKSI+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU5JLTRGIiB4bGluazpo%0AcmVmPSIjU1RJWFdFQk1BSU5JLTRGIj48L3VzZT48dXNlIGhyZWY9IiNTVElY%0AV0VCTUFJTi0yOCIgeD0iNzI3IiB5PSIwIiB4bGluazpocmVmPSIjU1RJWFdF%0AQk1BSU4tMjgiPjwvdXNlPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS02RSIg%0AeD0iMTA2NSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS02RSI+%0APC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU4tMjkiIHg9IjE1NzAiIHk9%0AIjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTi0yOSI+PC91c2U+PC9nPjwv%0Ac3ZnPg==%0A" alt="O(n)"> au pire cas. Le <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZFIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDYwIDExN2wxNCAtMTNjLTY4IC05MyAtOTMgLTExMyAt%0AMTQwIC0xMTNjLTI1IDAgLTQ3IDE2IC00NyA1NGMwIDEwIDIgMjMgMTYgNzVs%0ANDQgMTYyYzggMzEgMTQgNjcgMTQgNzljMCAxOCAtOSAyOSAtMjQgMjljLTQw%0AIDAgLTg1IC00OSAtMTQ4IC0xNDJjLTQ1IC02NyAtNTMgLTkwIC0xMDAgLTI0%0AOGgtNzVsOTYgMzUwYzEgNSAyIDExIDIgMTdjMCAyMCAtMTQgMjYgLTY1IDI3%0AdjE2YzgxIDE2IDEwOSAyMCAxNjIgMzFsNCAtMmwtNjcgLTIxOCBjMTAwIDE2%0AMCAxNjcgMjIwIDIzMSAyMjBjNDMgMCA2NSAtMjUgNjUgLTYxYzAgLTE4IC00%0AIC0zOSAtMTAgLTYwbC01NiAtMjAzYy0xMCAtMzYgLTE0IC01MyAtMTQgLTYx%0AYzAgLTkgNCAtMTggMTYgLTE4YzE0IDAgMzIgMTYgNjEgNTNjNyA4IDE0IDE3%0AIDIxIDI2WiI+PC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOSIgc3Ry%0Ab2tlLXdpZHRoPSIxMCIgZD0iTTI5IDY2MGwxMiAxNmMxNTMgLTkyIDI0NCAt%0AMjU5IDI0NCAtNDI5YzAgLTE4NSAtODggLTMyNyAtMjQ3IC00MjRsLTkgMTZj%0AMTQyIDExNyAxNzAgMjExIDE3MCA0MDVjMCAxODcgLTI1IDMwMiAtMTcwIDQx%0ANloiPjwvcGF0aD48L2RlZnM+PGcgc3Ryb2tlPSJibGFjayIgZmlsbD0iYmxh%0AY2siIHN0cm9rZS13aWR0aD0iMCIgdHJhbnNmb3JtPSJtYXRyaXgoMSAwIDAg%0ALTEgMCAwKSI+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU5JLTRGIiB4bGluazpo%0AcmVmPSIjU1RJWFdFQk1BSU5JLTRGIj48L3VzZT48dXNlIGhyZWY9IiNTVElY%0AV0VCTUFJTi0yOCIgeD0iNzI3IiB5PSIwIiB4bGluazpocmVmPSIjU1RJWFdF%0AQk1BSU4tMjgiPjwvdXNlPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS02RSIg%0AeD0iMTA2NSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS02RSI+%0APC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU4tMjkiIHg9IjE1NzAiIHk9%0AIjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTi0yOSI+PC91c2U+PC9nPjwv%0Ac3ZnPg==%0A" alt="O(n)"> vient du fait que les collisions sont gérées avec une liste chaînée. Si on utilise un arbre balancé plutôt qu'une liste on passe en <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA5ZXg7IGhlaWdodDogMi4xNDNleDsgdmVydGlj%0AYWwtYWxpZ246IC0wLjU3MWV4OyBtYXJnaW4tdG9wOiAxcHg7IG1hcmdpbi1y%0AaWdodDogMHB4OyBtYXJnaW4tYm90dG9tOiAxcHg7IG1hcmdpbi1sZWZ0OiAw%0AcHg7IHBvc2l0aW9uOiBzdGF0aWM7ICIgdmlld0JveD0iMCAtNzA5LjI1ODEy%0AMzI1NTE1NDkgMzg3OCA5NDEuNTE2MjQ2NTEwMzEiIHhtbG5zPSJodHRwOi8v%0Ad3d3LnczLm9yZy8yMDAwL3N2ZyI+PGRlZnMgaWQ9Ik1hdGhKYXhfU1ZHX2ds%0AeXBocyI+PHBhdGggaWQ9IlNUSVhXRUJNQUlOSS00RiIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTY5OSA0MThjMCAtMTQ2IC04OCAtMjg1IC0yMDcgLTM2NWMt%0ANjUgLTQ0IC0xNDAgLTcxIC0yMTQgLTcxYy0xMzAgMCAtMjE4IDg1IC0yMTgg%0AMjM0YzAgMTIyIDczIDI2MiAxNzcgMzUzYzY5IDYwIDE1MiA5NyAyMzcgOTdj%0AMTQ0IDEgMjI1IC05NiAyMjUgLTI0OHpNNTk0IDQ4MWMwIDk0IC00OSAxNTIg%0ALTEyOSAxNTJjLTc0IDAgLTEzNyAtNTEgLTE4NiAtMTE3Yy03MyAtOTkgLTEx%0ANCAtMjMyIC0xMTQgLTMzMiBjMCAtMTA5IDQ2IC0xNjkgMTMwIC0xNjljNjcg%0AMCAxMjQgMzkgMTcwIDk1Yzg0IDEwNCAxMjkgMjY5IDEyOSAzNzFaIj48L3Bh%0AdGg+PHBhdGggaWQ9IlNUSVhXRUJNQUlOLTI4IiBzdHJva2Utd2lkdGg9IjEw%0AIiBkPSJNMzA0IC0xNjFsLTEyIC0xNmMtMTU4IDkwIC0yNDQgMjU5IC0yNDQg%0ANDI5YzAgMTg1IDg3IDMyOSAyNDcgNDI0bDkgLTE2Yy0xMzkgLTExOSAtMTcw%0AIC0yMTIgLTE3MCAtNDA1YzAgLTE4NiAzMCAtMjk5IDE3MCAtNDE2WiI+PC9w%0AYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNkMiIHN0cm9rZS13aWR0aD0i%0AMTAiIGQ9Ik0yNzkgNjc4bC0xNTMgLTU4NWMtNSAtMTggLTggLTM1IC04IC00%0AM2MwIC0xMiA3IC0xOCAxNyAtMThjMTUgMCAzOCAxNiA2NyA1N2wyNSAzNWwx%0ANCAtMTBjLTYwIC05NSAtOTcgLTEyNSAtMTUxIC0xMjVjLTMyIDAgLTQ5IDE5%0AIC00OSA1NmMwIDggMSAyMCA0IDMwbDEzNyA1MjRjMyAxMCAzIDE2IDMgMTlj%0AMCAxMiAtMTcgMjIgLTQ5IDIyaC0xOHYxNmM1OSA3IDk2IDE0IDE1NSAyN1oi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZGIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDY4IDMwMWMwIC03NiAtNDAgLTE2NCAtMTA2IC0yMjlj%0ALTU4IC01OCAtMTIyIC04MyAtMTg4IC04M2MtOTQgMCAtMTQ3IDUyIC0xNDcg%0AMTM5YzAgMTEyIDc1IDIyNyAxODAgMjgzYzM5IDIxIDc5IDMwIDEyMCAzMGM4%0AMSAwIDE0MSAtNTIgMTQxIC0xNDB6TTM4NCAzMjZjMCA2MSAtMjggOTQgLTcx%0AIDk0Yy00NCAwIC04OCAtMzEgLTEyOCAtOTFjLTQ2IC03MCAtNzQgLTE0OSAt%0ANzQgLTIyOGMwIC02MCAzMSAtOTEgNzggLTkxIGM0NCAwIDgyIDI5IDEyMSA4%0AM2M0NiA2MyA3NCAxNTcgNzQgMjMzWiI+PC9wYXRoPjxwYXRoIGlkPSJTVElY%0AV0VCTUFJTkktNjciIHN0cm9rZS13aWR0aD0iMTAiIGQ9Ik00NzEgMzY2aC00%0AOWM5IC0xOCA5IC0zNCA5IC01MWMwIC04NCAtOTIgLTE2NCAtMTg1IC0xNjRj%0ALTExIDAgLTIyIDEgLTMxIDNjLTMgMSAtNSAxIC03IDFjLTE3IDAgLTM2IC0y%0AMCAtMzYgLTQxYzAgLTE4IDI3IC0zMSA3MSAtNDJjOTYgLTIzIDE0MiAtNjcg%0AMTQyIC0xMjdjMCAtODcgLTc3IC0xNTEgLTIxMCAtMTUxYy0xMDIgMCAtMTY3%0AIDM2IC0xNjcgMTA4YzAgNTEgMTkgNzggMTE3IDEzN2MtMTggMTEgLTI3IDI2%0AIC0yNyAzOSBjMCAyOSAyMyA1OSA3NyA4NGMtNTYgMjAgLTc5IDU2IC03OSAx%0AMDhjMCAxMDIgMTAwIDE3MSAyMDEgMTcxYzM4IDAgNzEgLTkgOTggLTI4Yzgg%0ALTYgMTMgLTggMTYgLThoNjB2LTM5ek0zNTIgMzQ4YzAgNTMgLTE5IDcxIC01%0ANiA3MWMtNjIgMCAtMTIyIC03MyAtMTIyIC0xNzJjMCAtNDcgMjIgLTc1IDYw%0AIC03NWMzNCAwIDYxIDE4IDg1IDU5YzIwIDM0IDMzIDc1IDMzIDExN3pNMzI1%0AIC05MGMwIDQ2IC0zNiA3NCAtMTQzIDEwNyBjLTEzIDQgLTIzIDcgLTM0IDEx%0AYy05IDAgLTUxIC0zNCAtNjUgLTUyYy0xNSAtMTkgLTIwIC0zNSAtMjAgLTU4%0AYzAgLTcwIDQ3IC0xMDIgMTI3IC0xMDJjODEgMCAxMzUgNDMgMTM1IDk0WiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZFIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDYwIDExN2wxNCAtMTNjLTY4IC05MyAtOTMgLTExMyAt%0AMTQwIC0xMTNjLTI1IDAgLTQ3IDE2IC00NyA1NGMwIDEwIDIgMjMgMTYgNzVs%0ANDQgMTYyYzggMzEgMTQgNjcgMTQgNzljMCAxOCAtOSAyOSAtMjQgMjljLTQw%0AIDAgLTg1IC00OSAtMTQ4IC0xNDJjLTQ1IC02NyAtNTMgLTkwIC0xMDAgLTI0%0AOGgtNzVsOTYgMzUwYzEgNSAyIDExIDIgMTdjMCAyMCAtMTQgMjYgLTY1IDI3%0AdjE2YzgxIDE2IDEwOSAyMCAxNjIgMzFsNCAtMmwtNjcgLTIxOCBjMTAwIDE2%0AMCAxNjcgMjIwIDIzMSAyMjBjNDMgMCA2NSAtMjUgNjUgLTYxYzAgLTE4IC00%0AIC0zOSAtMTAgLTYwbC01NiAtMjAzYy0xMCAtMzYgLTE0IC01MyAtMTQgLTYx%0AYzAgLTkgNCAtMTggMTYgLTE4YzE0IDAgMzIgMTYgNjEgNTNjNyA4IDE0IDE3%0AIDIxIDI2WiI+PC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOSIgc3Ry%0Ab2tlLXdpZHRoPSIxMCIgZD0iTTI5IDY2MGwxMiAxNmMxNTMgLTkyIDI0NCAt%0AMjU5IDI0NCAtNDI5YzAgLTE4NSAtODggLTMyNyAtMjQ3IC00MjRsLTkgMTZj%0AMTQyIDExNyAxNzAgMjExIDE3MCA0MDVjMCAxODcgLTI1IDMwMiAtMTcwIDQx%0ANloiPjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMjkiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik0yOSA2NjBsMTIgMTZjMTUzIC05MiAyNDQgLTI1OSAy%0ANDQgLTQyOWMwIC0xODUgLTg4IC0zMjcgLTI0NyAtNDI0bC05IDE2YzE0MiAx%0AMTcgMTcwIDIxMSAxNzAgNDA1YzAgMTg3IC0yNSAzMDIgLTE3MCA0MTZaIj48%0AL3BhdGg+PC9kZWZzPjxnIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBz%0AdHJva2Utd2lkdGg9IjAiIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAg%0AMCkiPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS00RiIgeGxpbms6aHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RiI+PC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1B%0ASU4tMjgiIHg9IjcyNyIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlO%0ALTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTkktNkMiIHg9IjEw%0ANjUiIHk9IjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTkktNkMiPjwvdXNl%0APjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS02RiIgeD0iMTM0OSIgeT0iMCIg%0AeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS02RiI+PC91c2U+PHVzZSBocmVm%0APSIjU1RJWFdFQk1BSU5JLTY3IiB4PSIxODU0IiB5PSIwIiB4bGluazpocmVm%0APSIjU1RJWFdFQk1BSU5JLTY3Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VC%0ATUFJTi0yOCIgeD0iMjM1OSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJN%0AQUlOLTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTkktNkUiIHg9%0AIjI2OTciIHk9IjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTkktNkUiPjwv%0AdXNlPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOLTI5IiB4PSIzMjAyIiB5PSIw%0AIiB4bGluazpocmVmPSIjU1RJWFdFQk1BSU4tMjkiPjwvdXNlPjx1c2UgaHJl%0AZj0iI1NUSVhXRUJNQUlOLTI5IiB4PSIzNTQwIiB5PSIwIiB4bGluazpocmVm%0APSIjU1RJWFdFQk1BSU4tMjkiPjwvdXNlPjwvZz48L3N2Zz4=%0A" alt="O(log(n))"> ce qui réduit drastiquement le problème.</p>
<p>C'est ce que propose la <a href="http://openjdk.java.net/jeps/180">JEP 180</a> et qui a été implémenté dans OpenJDK 8.</p>
<p>Refaisons tourner notre benchmark sur OpenJDK 8:</p>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f756e706f7274616e742d74686f75676874732f3230313430355f4a45505f3138302f6d61737465722f4a45505f3138305f616e616c797369735f66696c65732f4a45505f3138305f616e616c797369735f32395f312e706e673f7261773d74727565/JEP_180_analysis_29_1.png?raw=true" alt="png" title="Source : https://raw.githubusercontent.com/unportant-thoughts/201405_JEP_180/master/JEP_180_analysis_files/JEP_180_analysis_29_1.png?raw=true"></p>
<p>Cette fois ci nous comparons le comportement normal d'OpenJDK 8 et Java 7u55 ainsi que le comportement d'OpenJDK8 avec des collisions.</p>
<p>Tout d'abord nous constatons que les performances dans le cas normal n'ont pas régressé. Ensuite nous voyons que contrairement à une solution qui vise a prévenir entièrement les collisions, l'utilisation d'arbre balancé a tout de même un coût. Les opérations passent de <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMzEiIHN0cm9rZS13aWR0%0AaD0iMTAiIGQ9Ik0zOTQgMGgtMjc2djE1Yzc0IDQgOTUgMjUgOTUgODB2NDQ5%0AYzAgMzQgLTkgNDkgLTMwIDQ5Yy0xMCAwIC0yNyAtNSAtNDUgLTEybC0yNyAt%0AMTB2MTRsMTc5IDkxbDkgLTN2LTU5N2MwIC00MyAyMCAtNjEgOTUgLTYxdi0x%0ANVoiPjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMjkiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik0yOSA2NjBsMTIgMTZjMTUzIC05MiAyNDQgLTI1OSAy%0ANDQgLTQyOWMwIC0xODUgLTg4IC0zMjcgLTI0NyAtNDI0bC05IDE2YzE0MiAx%0AMTcgMTcwIDIxMSAxNzAgNDA1YzAgMTg3IC0yNSAzMDIgLTE3MCA0MTZaIj48%0AL3BhdGg+PC9kZWZzPjxnIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBz%0AdHJva2Utd2lkdGg9IjAiIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAg%0AMCkiPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS00RiIgeGxpbms6aHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RiI+PC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1B%0ASU4tMjgiIHg9IjcyNyIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlO%0ALTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTi0zMSIgeD0iMTA2%0ANSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOLTMxIj48L3VzZT48%0AdXNlIGhyZWY9IiNTVElYV0VCTUFJTi0yOSIgeD0iMTU3MCIgeT0iMCIgeGxp%0Abms6aHJlZj0iI1NUSVhXRUJNQUlOLTI5Ij48L3VzZT48L2c+PC9zdmc+%0A" alt="O(1)"> à <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA5ZXg7IGhlaWdodDogMi4xNDNleDsgdmVydGlj%0AYWwtYWxpZ246IC0wLjU3MWV4OyBtYXJnaW4tdG9wOiAxcHg7IG1hcmdpbi1y%0AaWdodDogMHB4OyBtYXJnaW4tYm90dG9tOiAxcHg7IG1hcmdpbi1sZWZ0OiAw%0AcHg7IHBvc2l0aW9uOiBzdGF0aWM7ICIgdmlld0JveD0iMCAtNzA5LjI1ODEy%0AMzI1NTE1NDkgMzg3OCA5NDEuNTE2MjQ2NTEwMzEiIHhtbG5zPSJodHRwOi8v%0Ad3d3LnczLm9yZy8yMDAwL3N2ZyI+PGRlZnMgaWQ9Ik1hdGhKYXhfU1ZHX2ds%0AeXBocyI+PHBhdGggaWQ9IlNUSVhXRUJNQUlOSS00RiIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTY5OSA0MThjMCAtMTQ2IC04OCAtMjg1IC0yMDcgLTM2NWMt%0ANjUgLTQ0IC0xNDAgLTcxIC0yMTQgLTcxYy0xMzAgMCAtMjE4IDg1IC0yMTgg%0AMjM0YzAgMTIyIDczIDI2MiAxNzcgMzUzYzY5IDYwIDE1MiA5NyAyMzcgOTdj%0AMTQ0IDEgMjI1IC05NiAyMjUgLTI0OHpNNTk0IDQ4MWMwIDk0IC00OSAxNTIg%0ALTEyOSAxNTJjLTc0IDAgLTEzNyAtNTEgLTE4NiAtMTE3Yy03MyAtOTkgLTEx%0ANCAtMjMyIC0xMTQgLTMzMiBjMCAtMTA5IDQ2IC0xNjkgMTMwIC0xNjljNjcg%0AMCAxMjQgMzkgMTcwIDk1Yzg0IDEwNCAxMjkgMjY5IDEyOSAzNzFaIj48L3Bh%0AdGg+PHBhdGggaWQ9IlNUSVhXRUJNQUlOLTI4IiBzdHJva2Utd2lkdGg9IjEw%0AIiBkPSJNMzA0IC0xNjFsLTEyIC0xNmMtMTU4IDkwIC0yNDQgMjU5IC0yNDQg%0ANDI5YzAgMTg1IDg3IDMyOSAyNDcgNDI0bDkgLTE2Yy0xMzkgLTExOSAtMTcw%0AIC0yMTIgLTE3MCAtNDA1YzAgLTE4NiAzMCAtMjk5IDE3MCAtNDE2WiI+PC9w%0AYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNkMiIHN0cm9rZS13aWR0aD0i%0AMTAiIGQ9Ik0yNzkgNjc4bC0xNTMgLTU4NWMtNSAtMTggLTggLTM1IC04IC00%0AM2MwIC0xMiA3IC0xOCAxNyAtMThjMTUgMCAzOCAxNiA2NyA1N2wyNSAzNWwx%0ANCAtMTBjLTYwIC05NSAtOTcgLTEyNSAtMTUxIC0xMjVjLTMyIDAgLTQ5IDE5%0AIC00OSA1NmMwIDggMSAyMCA0IDMwbDEzNyA1MjRjMyAxMCAzIDE2IDMgMTlj%0AMCAxMiAtMTcgMjIgLTQ5IDIyaC0xOHYxNmM1OSA3IDk2IDE0IDE1NSAyN1oi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZGIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDY4IDMwMWMwIC03NiAtNDAgLTE2NCAtMTA2IC0yMjlj%0ALTU4IC01OCAtMTIyIC04MyAtMTg4IC04M2MtOTQgMCAtMTQ3IDUyIC0xNDcg%0AMTM5YzAgMTEyIDc1IDIyNyAxODAgMjgzYzM5IDIxIDc5IDMwIDEyMCAzMGM4%0AMSAwIDE0MSAtNTIgMTQxIC0xNDB6TTM4NCAzMjZjMCA2MSAtMjggOTQgLTcx%0AIDk0Yy00NCAwIC04OCAtMzEgLTEyOCAtOTFjLTQ2IC03MCAtNzQgLTE0OSAt%0ANzQgLTIyOGMwIC02MCAzMSAtOTEgNzggLTkxIGM0NCAwIDgyIDI5IDEyMSA4%0AM2M0NiA2MyA3NCAxNTcgNzQgMjMzWiI+PC9wYXRoPjxwYXRoIGlkPSJTVElY%0AV0VCTUFJTkktNjciIHN0cm9rZS13aWR0aD0iMTAiIGQ9Ik00NzEgMzY2aC00%0AOWM5IC0xOCA5IC0zNCA5IC01MWMwIC04NCAtOTIgLTE2NCAtMTg1IC0xNjRj%0ALTExIDAgLTIyIDEgLTMxIDNjLTMgMSAtNSAxIC03IDFjLTE3IDAgLTM2IC0y%0AMCAtMzYgLTQxYzAgLTE4IDI3IC0zMSA3MSAtNDJjOTYgLTIzIDE0MiAtNjcg%0AMTQyIC0xMjdjMCAtODcgLTc3IC0xNTEgLTIxMCAtMTUxYy0xMDIgMCAtMTY3%0AIDM2IC0xNjcgMTA4YzAgNTEgMTkgNzggMTE3IDEzN2MtMTggMTEgLTI3IDI2%0AIC0yNyAzOSBjMCAyOSAyMyA1OSA3NyA4NGMtNTYgMjAgLTc5IDU2IC03OSAx%0AMDhjMCAxMDIgMTAwIDE3MSAyMDEgMTcxYzM4IDAgNzEgLTkgOTggLTI4Yzgg%0ALTYgMTMgLTggMTYgLThoNjB2LTM5ek0zNTIgMzQ4YzAgNTMgLTE5IDcxIC01%0ANiA3MWMtNjIgMCAtMTIyIC03MyAtMTIyIC0xNzJjMCAtNDcgMjIgLTc1IDYw%0AIC03NWMzNCAwIDYxIDE4IDg1IDU5YzIwIDM0IDMzIDc1IDMzIDExN3pNMzI1%0AIC05MGMwIDQ2IC0zNiA3NCAtMTQzIDEwNyBjLTEzIDQgLTIzIDcgLTM0IDEx%0AYy05IDAgLTUxIC0zNCAtNjUgLTUyYy0xNSAtMTkgLTIwIC0zNSAtMjAgLTU4%0AYzAgLTcwIDQ3IC0xMDIgMTI3IC0xMDJjODEgMCAxMzUgNDMgMTM1IDk0WiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZFIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDYwIDExN2wxNCAtMTNjLTY4IC05MyAtOTMgLTExMyAt%0AMTQwIC0xMTNjLTI1IDAgLTQ3IDE2IC00NyA1NGMwIDEwIDIgMjMgMTYgNzVs%0ANDQgMTYyYzggMzEgMTQgNjcgMTQgNzljMCAxOCAtOSAyOSAtMjQgMjljLTQw%0AIDAgLTg1IC00OSAtMTQ4IC0xNDJjLTQ1IC02NyAtNTMgLTkwIC0xMDAgLTI0%0AOGgtNzVsOTYgMzUwYzEgNSAyIDExIDIgMTdjMCAyMCAtMTQgMjYgLTY1IDI3%0AdjE2YzgxIDE2IDEwOSAyMCAxNjIgMzFsNCAtMmwtNjcgLTIxOCBjMTAwIDE2%0AMCAxNjcgMjIwIDIzMSAyMjBjNDMgMCA2NSAtMjUgNjUgLTYxYzAgLTE4IC00%0AIC0zOSAtMTAgLTYwbC01NiAtMjAzYy0xMCAtMzYgLTE0IC01MyAtMTQgLTYx%0AYzAgLTkgNCAtMTggMTYgLTE4YzE0IDAgMzIgMTYgNjEgNTNjNyA4IDE0IDE3%0AIDIxIDI2WiI+PC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOSIgc3Ry%0Ab2tlLXdpZHRoPSIxMCIgZD0iTTI5IDY2MGwxMiAxNmMxNTMgLTkyIDI0NCAt%0AMjU5IDI0NCAtNDI5YzAgLTE4NSAtODggLTMyNyAtMjQ3IC00MjRsLTkgMTZj%0AMTQyIDExNyAxNzAgMjExIDE3MCA0MDVjMCAxODcgLTI1IDMwMiAtMTcwIDQx%0ANloiPjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMjkiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik0yOSA2NjBsMTIgMTZjMTUzIC05MiAyNDQgLTI1OSAy%0ANDQgLTQyOWMwIC0xODUgLTg4IC0zMjcgLTI0NyAtNDI0bC05IDE2YzE0MiAx%0AMTcgMTcwIDIxMSAxNzAgNDA1YzAgMTg3IC0yNSAzMDIgLTE3MCA0MTZaIj48%0AL3BhdGg+PC9kZWZzPjxnIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBz%0AdHJva2Utd2lkdGg9IjAiIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAg%0AMCkiPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS00RiIgeGxpbms6aHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RiI+PC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1B%0ASU4tMjgiIHg9IjcyNyIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlO%0ALTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTkktNkMiIHg9IjEw%0ANjUiIHk9IjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTkktNkMiPjwvdXNl%0APjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS02RiIgeD0iMTM0OSIgeT0iMCIg%0AeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS02RiI+PC91c2U+PHVzZSBocmVm%0APSIjU1RJWFdFQk1BSU5JLTY3IiB4PSIxODU0IiB5PSIwIiB4bGluazpocmVm%0APSIjU1RJWFdFQk1BSU5JLTY3Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VC%0ATUFJTi0yOCIgeD0iMjM1OSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJN%0AQUlOLTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTkktNkUiIHg9%0AIjI2OTciIHk9IjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTkktNkUiPjwv%0AdXNlPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOLTI5IiB4PSIzMjAyIiB5PSIw%0AIiB4bGluazpocmVmPSIjU1RJWFdFQk1BSU4tMjkiPjwvdXNlPjx1c2UgaHJl%0AZj0iI1NUSVhXRUJNQUlOLTI5IiB4PSIzNTQwIiB5PSIwIiB4bGluazpocmVm%0APSIjU1RJWFdFQk1BSU4tMjkiPjwvdXNlPjwvZz48L3N2Zz4=%0A" alt="O(log(n))">. Cependant si on regarde les chiffres ce n'est pas dramatique. À 20 000 éléments nous sommes maintenant à ~10ms plutôt que ~1ms loin de la seconde initiale.</p>
<p>Nous avons regardé le point de vue performance, cependant utiliser des arbres balancés a aussi un impact non négligeable sur la consommation mémoire. En effet au lieu d'avoir à stocker un bête pointeur sur l'élément suivant, on se retrouve avec quatre pointeurs et un booléen. Ce qui pourrait faire exploser la consommation mémoire. Cependant par défaut on utilise toujours une liste chaînée. Quand le nombre de collisions augmente dans une case et dépasse un seuil, on convertit tout ou une partie de la liste en arbre balancé pour optimiser le ratio consommation mémoire/performance. Cette technique est appliqué à chaque feuille de l'arbre. On démarre avec une liste, puis on convertit la feuille en arbre quand elle devient trop grande. Quand on supprime des éléments on peut rebasculer vers une liste chaînée. Les seuils de conversion étant respectivement à 8 et 6 éléments.</p>
<p>Si l'on observe la consommation mémoire avec <a href="http://openjdk.java.net/projects/code-tools/jol/">Jol</a> on peut voir que ça marche très bien:</p>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f756e706f7274616e742d74686f75676874732f3230313430355f4a45505f3138302f6d61737465722f4a45505f3138305f616e616c797369735f66696c65732f4a45505f3138305f616e616c797369735f33315f312e706e673f7261773d74727565/JEP_180_analysis_31_1.png?raw=true" alt="png" title="Source : https://raw.githubusercontent.com/unportant-thoughts/201405_JEP_180/master/JEP_180_analysis_files/JEP_180_analysis_31_1.png?raw=true"></p>
<p>Ici on a fait attention à ce que les chaînes aient toujours la même taille dans les deux cas.</p>
<p>En pratique dans une utilisation courante avec une fonction de hachage correcte, les collisions seront rares et les arbres balancés ne seront jamais utilisés. Par contre quand ils rentrent en action cela permet d'éviter les DOS ou simplement d'avoir de bonnes performances quand la fonction <code>hashCode</code> de l'utilisateur est biaisée.</p>
<p>J'invite le lecteur intéressé à aller regarder <a href="http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java#l38">le code</a>. Le commentaire initial explique extrêmement clairement comment ça fonctionne et c'est plutôt rigolo à lire.</p>
<h3 id="conclusion">Conclusion</h3>
<p>L'approche d'OpenJDK 8 est intéressante et différente des autres plateformes puisqu'elle ne cherche pas à résoudre le problème des collisions mais à améliorer le pire cas. Changer de fonction de hachage pour les String étant compliqué on peut comprendre ce choix. Ils ont fait le pari que les performances offertes par les arbres balancés suffiront à se protéger et à offrir une bonne robustesse aux mauvaises fonctions de hachage. En pratique, au pire cas on observe un ralentissement constant de ~10x quelque soit la taille de la collection.</p>
<p>De l'autre côté beaucoup de plateformes ont changé de fonction de hachage pour éviter le pire cas mais n'ont pas chercher à l'améliorer et sont restés aux listes chainées. Ils se protègent donc des dénis de service selon les connaissances actuelles mais ne cherchent pas à se protéger pour le futur ni à offrir une réponse performante aux fonctions de hachage qui pourraient être légèrement biaisés pour certains autres type de données car implémentées par l'utilisateur.</p>
<p>Dans l'idéal les deux techniques devraient être appliquées mais je ne connais pas de plateforme qui le fasse. Et vous les outils que vous utilisez ils ont fait quoi ?</p>
<p>Voilà c'est un problème pas nouveau mais on en attendra certainement à nouveau parler. Dès qu'on lit une valeur du monde extérieur, celui-ci va s'arranger pour trouver un moyen de faire des choses "sympas". Les attaques algorithmiques permettent de varier un peu les plaisirs et forcent à s'interroger longuement à chaque fois qu'on stock une valeur que l'on ne contrôle pas.</p>
<p>Note: Tout le matériel créé pour écrire l'article est <a href="https://github.com/unportant-thoughts/201405_JEP_180">en ligne</a></p>
<p>NdM : <em>Le journal a été édité pour corriger plusieurs liens.</em></p><div><a href="https://linuxfr.org/users/cykl/journaux/openjdk-jep-180-hashmap-collisions-attaques-par-la-complexite.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/102078/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/cykl/journaux/openjdk-jep-180-hashmap-collisions-attaques-par-la-complexite#comments">ouvrir dans le navigateur</a>
</p>
ckylhttps://linuxfr.org/nodes/102078/comments.atomtag:linuxfr.org,2005:News/352392014-04-02T20:48:37+02:002014-04-03T14:24:44+02:00Les codes sources de Microsoft Word 1.1a et DOS 1.1 et 2.0 publiésLicence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<div><p>Le 25 mars dernier, le code source de Microsoft Word 1.1a (1990) a été publiquement publié via le <em>Computer History Museum</em>. Ne rêvez pas trop, ce n’est pas libre et tout code dérivé n’est pas autorisé à être diffusé :</p>
<blockquote>
<p><em>You may not distribute or publish the software or Derivative Works. You may not use or test the software to provide a commercial service unless Microsoft permits you to do so under another agreement.</em></p>
</blockquote>
<p>N’espérez donc pas trop avoir ce splendide logiciel ergonomique qu’est Microsoft Word for Windows version 1.1a sous GNU/Linux prochainement (les polémistes habituels vont sans doute prétendre que LibreOffice n’arrive pas à la cheville de cette merveille).</p>
<p>Accessoirement, vous pouvez obtenir également le code de Microsoft DOS v1.1 (1982) & v2.0 (1983).</p>
<p><abbr title="Note des modérateurs">NdM</abbr> : <em>merci à fravashyo pour son journal. Sinon, vous pouvez aussi lire du vieux code libre, comme <a href="ftp://ftp.gnu.org/pub/pub/gnu/gcc/gcc-1.42.tar.gz">GCC 1.42 de 1990</a>, <a href="ftp://ftp.tug.org/historic/macros/latex-saildart/latex-0.90/">LaTeX 0.90 de 1983</a>, etc.</em> </p></div><ul><li>lien nᵒ 1 : <a title="http://linuxfr.org/users/fravashyo/journaux/show-us-the-code-les-sources-de-microsoft-word-enfin-dispo" hreflang="fr" href="https://linuxfr.org/redirect/89962">Journal à l’origine de la dépêche</a></li><li>lien nᵒ 2 : <a title="https://blogs.technet.com/b/microsoft_blog/archive/2014/03/25/microsoft-makes-source-code-for-ms-dos-and-word-for-windows-available-to-public.aspx" hreflang="en" href="https://linuxfr.org/redirect/89963">Annonce de la mise à disposition du code en lecture seule</a></li><li>lien nᵒ 3 : <a title="http://www.computerhistory.org/atchm/microsoft-word-for-windows-1-1a-source-code/" hreflang="en" href="https://linuxfr.org/redirect/89964">Histoire de Word et code source (en lecture seule)</a></li><li>lien nᵒ 4 : <a title="http://www.computerhistory.org/atchm/microsoft-ms-dos-early-source-code/" hreflang="en" href="https://linuxfr.org/redirect/89965">CHM: Microsoft MS-DOS early source code</a></li><li>lien nᵒ 5 : <a title="http://www.computerhistory.org/atchm/microsoft-word-for-windows-1-1a-source-code/" hreflang="en" href="https://linuxfr.org/redirect/89966">CHM: Microsoft Word for Windows Version 1.1a Source Code</a></li></ul><div></div><div><a href="https://linuxfr.org/news/les-codes-sources-de-microsoft-word-1-1a-et-dos-1-1-et-2-0-publies.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/101756/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/news/les-codes-sources-de-microsoft-word-1-1a-et-dos-1-1-et-2-0-publies#comments">ouvrir dans le navigateur</a>
</p>
fravashyoBenoît SibaudDavy DefaudFlorent ZaraZeroHeurehttps://linuxfr.org/nodes/101756/comments.atomtag:linuxfr.org,2005:Diary/347352014-02-13T10:55:19+01:002014-02-13T10:55:19+01:00L'Internet en feu (merci à Jules Verne)Licence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<p>Peut-être pour faire de la publicité au prochain numéro de MISC qui est consacré aux attaques par déni de service (DoS), l'Internet vit en ce moment au rythme des nombreuses attaques par réflexion+amplification utilisant le protocole NTP. Ces attaques ont atteint des nouveaux sommets (des victimes signalent <a href="https://twitter.com/olesovhcom/status/433631778620702721">du 350</a>, voire <a href="https://twitter.com/eastdakota/status/433002992694874112">du 400 Gb/s</a> mais rappelez-vous qu'il n'y a pas d'enquêtes indépendantes sur les attaques DoS). </p>
<p>Le principe de l'attaque est connu depuis longtemps, il est le même que pour les attaques réflexion+amplification utilisant le DNS, simplement NTP fournit typiquement un meilleur rapport d'amplification. La première alarme de la nouvelle utilisation de NTP avait été donnée par <a href="http://blog.cloudflare.com/understanding-and-mitigating-ntp-based-ddos-attacks">CloudFlare</a> et par <a href="https://cert.litnet.lt/en/docs/ntp-distributed-reflection-dos-attacks">le CERT lituanien</a>. Il y a un avis officiel <br><a href="http://www.us-cert.gov/ncas/alerts/TA14-013A">du CERT états-unien</a> et <a href="http://www.cert.ssi.gouv.fr/site/CERTA-2014-ACT-003/index.html">du français</a>.</p>
<p>Un exemple de récit de l'attaque contre CloudFlare dans la presse est <a href="http://www.bfmtv.com/high-tech/attaques-deni-service-dune-ampleur-inegalee-secouent-web-709404.html">sur BFMTV</a> (article tout à fait sérieux) ou, en anglais, <a href="http://www.itnews.com.au/News/372033,worlds-largest-ddos-strikes-us-europe.aspx">donné par ITnews</a> (attention, semble bloqué depuis Free, cela marche depuis les autres opérateurs) ou <a href="http://www.bbc.co.uk/news/technology-26136774">par la BBC</a>.</p>
<p>Certains opérateurs ont pris <a href="http://travaux.ovh.net/?do=details&id=10222">des mesures spécifiques</a> ou bien avertissent leurs clients (cas d'Online).</p>
<p>Si vous gérez des serveurs, vérifiez qu'ils ne sont <strong>pas</strong> amplificateurs NTP, avec <a href="http://www.openntpproject.org/">le projet OpenNTPproject</a>.</p><div><a href="https://linuxfr.org/users/bortzmeyer/journaux/l-internet-en-feu-merci-a-jules-verne.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/101254/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/bortzmeyer/journaux/l-internet-en-feu-merci-a-jules-verne#comments">ouvrir dans le navigateur</a>
</p>
Stéphane Bortzmeyerhttps://linuxfr.org/nodes/101254/comments.atomtag:linuxfr.org,2005:Diary/201902005-12-06T23:37:37+01:002005-12-06T23:37:37+01:00EUCD.INFO victime d'un DOSOn le savait déjà, la directive EUCD et sa transposition en France 'DADVSI' provoquent des réactions passionnées entre pro et anti DADVSI, même si je n'ai pas eu l'occasion de voir beaucoup de monde défendre le projet de loi et que j'ai surtout vu une très grosse majorité opposé à cette transposition.<br />
<br />
Un nouveau pas a été franchi puisque le site EUCD.INFO a été victime de DOS[1] toute la journée d'hier provoquant des indisponibilités périodiques, comme vous l'avez peut être remarqué.<br />
<br />
Il faut croire que c'est une bonne chose : La pétition dérange et c'est une bonne chose IHMO. Même si les moyens employés sont plus que limites.<br />
<br />
<br />
"Mais à qui profite le crime"(TM) ?<br />
Vu que c'est un DOS et pas un DDOS, l(es)'attaquant(s) devrai(en)t être facile à localiser, non ? (À moins d'utiliser un proxy ou un tor, mais ça limite pas mal la charge à envoyer au serveur).<br />
<br />
Pour terminer sur une note positive : Il y a maintenant plus de 22000 signataires et déjà 290 signature collectives.<br />
<br />
[1] <a href="http://www.eucd.info/index.php?2005/12/05/204-eucdinfo-attaque">http://www.eucd.info/index.php?2005/12/05/204-eucdinfo-attaq(...)</a><div><a href="https://linuxfr.org/users/theocrite/journaux/eucdinfo-victime-dun-dos.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/46699/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/theocrite/journaux/eucdinfo-victime-dun-dos#comments">ouvrir dans le navigateur</a>
</p>
theocritehttps://linuxfr.org/nodes/46699/comments.atomtag:linuxfr.org,2005:News/124232003-05-15T14:21:06+02:002003-05-15T14:21:06+02:00DOSBox, l'émulateur DOS<div>DOSBox (NdM : sous GPL) est capable d'émuler le système d'exploitation DOS (système de fichiers, mémoire, carte son), tout comme Dosemu, sous différents OS tels que Windows, BeOS, Linux, Mac OS X. L'objectif de cet émulateur est de pouvoir rejouer à nos bons vieux jeux en 2D, qui, il faut bien l'avouer, n'ont jamais été égalés depuis. ;-) Près de 700 titres sont actuellement supportés !
<br />
<br />
J'en profite pour mettre un lien vers un site recensant quelques uns de ces vieux jeux (appelés abandonware). Attention : les récupérer sans disposer de la licence d'utilisation est illégal. Cependant, dans la pratique, le procédé est toléré voire soutenu par certains éditeurs.
<br />
<br />
NdM : Attention également à ne pas confondre logiciel libre et abandonware ; le premier est légal et respectueux du droit d'auteur, alors que le second ne relève souvent que de la tolérance.</div><ul><li>lien nᵒ 1 : <a title="http://dosbox.sourceforge.net/" hreflang="en" href="https://linuxfr.org/redirect/24416">DOSBox</a></li><li>lien nᵒ 2 : <a title="http://dosbox.sourceforge.net/comp_list.php?orderby=name&letter=a" hreflang="en" href="https://linuxfr.org/redirect/24417">La liste des jeux supportés</a></li><li>lien nᵒ 3 : <a title="http://www.abandonware-france.org/" hreflang="fr" href="https://linuxfr.org/redirect/24418">Lost Treasure FR</a></li><li>lien nᵒ 4 : <a title="http://definition.abandonware-france.org/" hreflang="fr" href="https://linuxfr.org/redirect/24419">Qu'est-ce que l'abandonware et est-ce légal ?</a></li></ul><div></div><div><a href="https://linuxfr.org/news/dosbox-lemulateur-dos.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/11758/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/news/dosbox-lemulateur-dos#comments">ouvrir dans le navigateur</a>
</p>
ilaiouluihttps://linuxfr.org/nodes/11758/comments.atom