BeniBela online

29. Aug 2010

Jetzt gibt es einen neue Version vom HTML-Templatematcher. Er läuft jetzt tausendmal langsamer mit tausendmal höherem Speicherverbrauch.
Die alte Version hat einen NFA mit einer cleveren Heuristik verwendet, um das Template mit der Textdarstellung einer HTML-Datei in O(1) zusätzlichem Speicher und Linearzeit zu vergleichen, die neue Version verwendet wie alle anderen HTML-Parser eine Baumdarstellungen, die O(n) Speicher erfordert und darauf Backtracking mit einer Laufzeit von vielleicht O(k^n).
Das ist genau das, was ich eigentlich nicht machen wollte, aber es hat sich rausgestellt, dass die Templates dadurch sehr viel leichter zu verstehen und zu schreiben sind, weil es keinerlei Seiteneffekte mehr gibt. Außerdem benötigt es immer noch nicht mehr als ein paar Millisekunden für das Verarbeiten einer Datei (schneller als das Runterladen der Datei), und der Matcher beweist nun, ob das Template der HTML-Datei entspricht oder nicht. Er ist jetzt auch in drei unabhängige Klassen zerlegt, die sich separat verwenden und leichter testen lassen.
Ansonsten haben sich dabei auch die bbutils (Funktionen umbenannt oder entfernt), das TreeListView und die Suchleiste (eine Methode entfernt, um LCL 27190 kompatibel zu sein) geändert.

26. Aug 2010

Als ich gerade den vorherigen Artikel auf "unübersetzt" setzen wollte (was ich dann aber doch nicht gemacht habe, da die Textfarbe dadurch grau wird, und das nicht zu den bunten Tabellen passt), habe ich gemerkt, dass JAXMLP überhaupt keine Klammern in den If-Bedingungen erlaubt hat, warum auch immer, vielleicht weil es den Schwierigkeitsgrad fürs Parsen von trivial auf einfach erhöht. Die neue Version unterstützt sie jetzt aber.

26. Aug 2010

I just started to rewrite my fpc html template parser (which of course involves hours of debugging and patching Lazarus, before I can start to program anything else) and found two bugs due to an invalid string->pchar conversion. And although this is an absolutely trivial conversion, no one seems to have examined and described, how to do it best. So, here is a detailed analysis:

Converting ansistring to pchar

Converting a ansistring to pchar should be pretty simple, because the text itself is stored in almost the same way in both cases. If you have a variable str: string, there are three popular ways to convert it to a pchar: pchar(str), @str[1] and pchar(pointer(str)), but it is not obvious which is the best way to do the conversion.

If you don't want to bother with the technical details, you can always use pchar(str) and treat the result as a read-only pchar. But this is not the most efficient way to convert the string, and the following table summarizes the advantages (always green) and disadvantages (always red) of the other methods:

	Example	No copy	Branch free	Nil aware	Range safe	$H- safe
Explicit	p := pchar(str)	yes	no	yes	yes	yes
Array like	p := @str[1]	yes	without $R	no	no	no
Indirect	p := pchar(pointer(str))	yes	yes	no	yes	yes

The meaning of the columns is:

• No copy: None of the methods above copies the content of the string.
• Branch free: yes, iff the conversion works without branching instructions (hidden ifs). Branching is always very slow and even if modern computers are fast enough that it usually does not matter, you sometimes have/want to make something as fast as possible.
• Nil aware: yes, if it works if str=nil.
• Range safe: no, iff the conversion can fail if you enable range checking with the $R+ or -Cr option.
  @str[1] will raise a range checking error if the string is empty, because s[1] doesn't exist then.
• $H- safe: no, if it also compiles with shortstrings. This section is only about conversion of ansistrings to pchars and none of the methods supports shortstrings. However, sometimes you forget to enable the $H+ option and every string becomes a shortstring. If you then use @str[1], it can randomly crash, because shortstrings are not null-terminated. The other two methods are safe, because they will not compile.

So you should never use @str[1] to convert it to a pchar, and pchar(pointer(str)) only if you understand what nil aware means.
It is said that every ansistring is null-terminated, but this is not exactly true. There is one (and only one!) case in which a ansistring str is not null-terminated: If str is empty (str = ''). Then str is nil.
pchar(str) will detect this case and returns a pointer to a global #0 character, but pchar(pointer(str)) will return nil. So you can always use pchar(str), and pchar(pointer(str)) only if your string is not empty and you can prove this.
(and as a remark: if you ever get a string which is not '' and not null-terminated, you probably forget to enable $H+ or - less probably - something wrote to a wrong pointer. )

So why should you not always use pchar(str)?
Because it is much slower than the two other methods, since pchar(str) checks for the nil-case, and this is often unnecessary.

Some people also say pchar(str) calls UniqueString to reset the reference count of the string, but this is wrong. pchar(str) does not call any function. To see how worse the check is, you have to look at the assembly of the program (generated with fpc2.4 on amd64, not affected by optimization levels (which is strange because the assignment to rax was duplicated)):

pchar(str):

1    mov    rax,QWORD PTR string variable
2    test   rax,rax
3    jne    to 5
4    mov    rax, global #0 address
5    mov    QWORD PTR pchar variable,rax

p := pchar(pointer(str)) or p := @str[1] with $R-:

1    mov    rax,QWORD PTR string variable
2    mov    QWORD PTR pchar variable,rax

So the check requires three additional instructions, and one is a jump instruction which will be executed iff the string is not empty. Benchmarking (100000000 * 8 times repeated) results in:

	non-empty string		empty string
	$R-	$R+	$R-	$R+
pchar(str)	894 ms		496 ms
pchar(pointer(str))	325 ms		325 ms, but wrong result
@str[1]	325 ms	4616 ms	325 ms, but wrong result	crash

This shows pchar(pointer(str)) is more than twice as fast than pchar(str) in the more common use case of non-empty strings.

And for completeness, also the $R+ @s[1] assembly:

1    mov    rbx, string variable
2    mov    rdi,rbx
3    call   0x421668 <fpc_ansistr_checkzero>
4    mov    rsi,0x1
5    mov    rdi, string variable
6    call   0x421680 <fpc_ansistr_checkrange>
7    mov    pchar variable,rbx

In all cases is possible to modify the resulting pchar, but if you do that you will modify all copies of the string (unless you call UniqueString before):

var s,t:string;
    p:pchar;
begin
    s:='Hallo'; 
    t:=s;
    p:=pchar(s); 
    p^:='h';
    assert(s='hallo');
    assert(t='hallo');
end.

So only modify the pchar of an converted string if you created that string or have modified it before with string functions (so reference count = 1).

20. Aug 2010

Langsam sterben alle Seite weg, die ich im Internet kenne. Heute habe ich gemerkt, dass regexpstudio.com mit der TRegExpr-Klasse verschwunden ist, die früher als bester Delphi regexp-Parser galt. (die alten Delphiforen, in denen sie bewundert wurde, finde ich auch nicht mehr...)
Da man die Klasse für meine Internettools braucht, gibt es hier jetzt einen TRegExpr-Mirror.

10. Aug 2010

Und weiter geht es mit den SIRDSlets: Es gibt jetzt drei neue Level, Übersetzungen, Beschleuniger und Anaglyphenrendering. Die Beschleuniger sind wie schwarze Löcher, aber unabhängig von der Schiffsposition. Mit dem Anaglyphenrendering kann man es nun auch dreidimensional sehen, wenn man nicht schielen kann. Damit ist allerdings verwirrender, da die meisten 3D-Brillen eine miserabel Kanaltrennung haben.
Und falls es jemand noch nicht mitgekriegt hat: Deolalikar hat einen Beweis für P!=NP mit graphischen Modellen, FO(LFP)-Logik und theoretischer Physik veröffentlicht. Wenn der Beweis stimmt, wurden drei der berühmtesten Probleme in nur fünfzehn Jahren gelöst, mal sehen, wann Riemann drankommt.

28. May 2010

Heute habe ich mein neues SIRDSlets Spiel hochgeladen, dass eines der wenigen Spiele ist, die man in echtem 3D spielen/sehen kann. Es ist außerdem das erste Browserspiel auf dieser Seite und muss nicht wie die anderen explizit heruntergeladen werden. Allerdings ist es noch nicht ganz fertig, aber es ist schon seit Monaten spielbar und ich habe im Moment zu wenig Zeit, es zu vollenden. So fehlt zum Beispiel eine deutsche Übersetzung, mehr als sechs Level, und der Hardware-beschleunigte SIRDS-Renderer aus der vorherigen News (wobei es aber zweifelhaft ist, ob ich den jemals einbaue, da der Softwarerenderer schnell genug zu sein scheint, und es Applets nicht leicht fällt OpenGL zu verwenden).

16. Feb 2010

Heute gibt es abermals ein Videlibri-Update, das die unten erwähnten Probleme mit der FHB Düsseldorf und den beiden Aachener Bibliotheken löst. Außerdem läuft es jetzt wieder unter Windows (und weiterhin unter Linux).
Dazu habe ich auch meine Internettools aktualisiert: Der Wininet-Wrapper unterstützt nun auch Cookies ohne Attribute und http-Verbindungen über andere Ports als 80. Außerdem gibt es ein globales Logging (was man insbesondere für https braucht). Die Parserklasse ist ebenfalls flexibler geworden und man kann in den Pseudo-XPath-Ausdrücken nun auch Regex-Filter vor dem Ausführen anderer Funktionen anwenden, statt nur nachträglich wie bisher. (echte XPath-Ausdrücke können es dagegen übrigens gar nicht)
Zudem habe ich ein paar News ins Archiv und einige unfertige Tools auf die Demoseite verschoben.

07. Feb 2010

Ab jetzt gibt es eine extra Demo-Unterseite für kleine Programme, die eigentlich nutzlos sind, aber interessante Techniken oder hübsche Filme zeigen. Dazu habe ich zum einen ein paar Programme verschoben, zum anderen gibt es zwei neue, die ich an der Uni aus den Übungsprogrammen der VR- und Computergrafikvorlesungen programmiert habe.
Beide zeigen eine echte 3D-Darstellung, das eine rendert hardware beschleunigte Single Image (Random Dot) Stereograms, also Bilder, in denen man ein 3D-Bild durch Schielen sehen kann. Das andere "Webcam-UCP" Programm verwendet die klassische rot/cyan-Trennung, um Bilder für 3D-Brillen zu erstellen. Zusätzlich wird aber mittels einer Webcam, die Brillenposition getrackt und die Szene betrachterzentriert gerendert.
Außerdem funktioniert in Videlibri jetzt wieder die StB Aachen (FHB Düsseldorf vermutlich auch), ich lade die neue Version aber erst hoch, wenn ich die FHB noch getestet habe, da es ja sowieso niemand nutzt.

27. Jan 2010

Von VideLibri gibt es nun eine neue Version, die auch die Hochschulbibliothekk der RWTH Aachen unterstützt und vollständig Linux-kompatible ist, inklusive Menüeinträge und integrierte Autostartkonfiguration.
Nun die schlechten Nachrichten: Bei der BTH Aachen gibt es noch keine integrierte Verlängerung, da man nicht gleich nach einer Ausleihe verlängern darf, und ich somit weiß nicht feststellen kann, wie es funktioniert. Außerden haben alle Libero-Büchereien mal wieder eine neue Software installiert. Das heißt:
Sowohl die Aachener Stadtbibliothek wie auch die FHB Düsseldorf gehen vermutlich nicht mehr. Testen kann ich es nicht, weil ich momentan nicht in die Bibliothek kann. (und genau DAS ist der Grund, warum mal endlich jemand die Software benutzen sollte. Wenn mich jemand darauf hinweist und die neue Seite per Mail schickt, kann ich solche Fehler nämlich in einer Viertelstunde beseitigen, statt in zwei Wochen!)
Zumindest in der alten Windowsversion funktionieren die beiden definitiv nicht (Stb Aachen war da nie drin und die FHB ist umgezogen). Sollten sie in der Linuxversion funktionieren, kann man aber einfach die Dateien der Linuxversion in das Installationverzeichnis in Windows kopieren, dann läuft es dort genauso gut/schlecht.
Zudem habe ich die FHB Bochum gestrichen, da sie nicht mehr unter ihrer alten Internetadresse zu finden ist, ich die neue nirgends finden kann und sie sowieso nur im Programm war, weil sie einen gemeinsamen Server mit der FHB Düsseldorf hatte.

06. Jan 2010

So jetzt gibt es eine neue Version von allen in der letzten News erwähnten Paketen, hauptsächlich, weil ich vergessen hatte, die Unittest auszuschalten. Beim TreeListView gab es noch einige andere Änderungen: Beim horizontalen Scrollen flackert es nicht mehr unter GTK (früher hat es das auch nicht, aber bei der Änderung letzter Woche gab es wohl irgendwelche Kompatibilitätsprobleme) und die Icons im Baum werden nun geclippt, wenn die Spalte zu klein ist.
Außerdem gibt es jetzt eine neue Version von meinem Büchereiverwaltungsprogramm Videlibri (das übrigens auf allen diesen anderen Paketen basiert). Zur Abwechslung setzt es diesmal nicht Windows sondern Debian 64-Bit voraus und kann auch die Bücher der Aachener Stadtbibliothek verwalten. Die Windowsversion kommt später, wenn ich sichergestellt habe, dass das Crosscompiling zuverlässig funktioniert. Das Programm verwendet allerdings immer noch ein Windowsverzeichnislayout (alle Dateien in einem Programmordner statt wie unter Linux üblich überall verstreut) und der Autostart muss manuell unter der gnome/KDE-Konfiguration eingetragen werden (videlibri-Pfad mit --autostart als Parameter), wenn man die Autostartfunktionalität benutzen will.

31. Dec 2009

Und weiter geht's. Ich habe jetzt drei der bisherigen Packages mit HTML-Templateparser, Autoupdate und Wininetwrapper zu einem Internet Tools-Package zusammengefügt und platform-unabhängig gemacht (der Hauptunterschied ist, dass der Wininetwrapper nun auch Synapse unterstützt). Das Package benötigt/enthält auch meine bbutils, bei denen ich noch einen Absturz unter 64-Bit beseitigt habe (und vermutlich seit dem letzten Release auch einige Funktionen umbenannt).
Außerdem gibt es jetzt für alle der geänderten Pascalkomponenten eine Onlinedokumentation, für die ich einfach nur die sowieso in den zip-Dateien vorhandenen pasdoc-Dateien unkomprimiert hochgeladen habe.

28. Dec 2009

So nun bin ich von Windows 32-Bit auf Linux 64-Bit gewechselt, und jetzt geht das große Updaten los. Die alten Programme dieser Seite waren zwar theoretisch schon alle platform-unabhängig, praktisch gab es aber noch einige Macken.
Mein TreeListView läuft in der neuen Version unter LCL-GTK sehr viel schneller/flüssiger als früher, da mehrere Benutzereingaben hintereinander zusammengefasst angezeigt werden (wobei es eigentlich ein gemeldeter LCL-Bug ist, dass so viele überflüssige Nachrichten überhaupt weitergeleitet werden), außerdem kann jetzt in jedem Item ein Datenwert mit 64-Bit gespeichert werden und die Komponente steht in einem Designzeitpackage zur Verfügung. Die dazugehörige Suchleiste passt sich nun der Schriftgröße an und hat ebenfalls ein Package bekommen. Zudem kann mein JAXML-Parser jetzt auch Dateien mit unterschiedlichen Zeichensätzen erstellen und die \\-Form funktioniert wieder richtig.

05. Okt 2009

Ich habe jetzt mal meine Bachelorarbeit hochgeladen. Im Wesentlichen geht es darum, wie man aus mehreren gegebenen, sortierten Listen von gleichen Ereignissen herausfinden kann, welches dieselben sind.

16. Sep 2009

Diese Woche habe ich meine Bachelorarbeit/prüfung abgelegt , so dass ich mich wieder etwas um meine Homepage kümmern kann.
Heute gibt es ein neues Java-Script, mit dem man das gaußsche Eliminationsverfahren auf eine Matrix anwenden kann. Es gibt zwar schon hunderte solche Programme im Internet, aber alle, die ich finden konnte, waren für mein Gleichungssystem unbrauchbar, da sie verlangen, dass die Matrix quadratisch ist und Elemente eines Körpers statt eines Ringes enthält.
Übrigens ist interessante Tatsache, die ich bei der Implementierung festgestellt habe, dass man den euklidischen Algorithmus zur ggT-Berechnung als Spezialfall des gaußschen Eliminationsverfahren auf einer 2x1-Matrix der natürlichen Zahlen betrachten kann.

15. Apr 2009

Es gibt nun wieder ein neues Programm: Einen Sonnensimulator, der die Helligkeit und den Farbton des Monitors zeitlich ändert, so dass dessen Licht dem Sonnenlicht entspricht.
Außerdem habe ich dafür eine Diagrammkomponente geschrieben, die Gleitkommazahlen-Reihen unterschiedlich darstellen kann. Sie benutzt ein Model/View-System (da ich mich viel mit QT beschäftig habe), das im ersten Moment ziemlich verblüffend wirkt. Z.B.: Kann man in zwei unterschiedlichen Fenstern immer dieselben Punkte synchronisiert anzeigen und in einem noch eine weitere Reihe hinzufügen.

09. Apr 2009

Ein Problem, wenn man Opensource-Software schreibt ist, dass man häufig Patches erhält, die ziemlich unbrauchbar sind, weil sie zu 95% aus Whitspaceänderungen bestehen. Daher habe ich ein (unter Linux und Windows laufendes) Kommandozeilentool namens Simplifydiff geschrieben, welches alle unnötigen Daten entfernt.
Außerdem werden ab jetzt alle Gästebucheintrag, welche von der Heuristik als Spam erkannt werden ohne Backup gelöscht. Bisher habe ich zur Sicherheit immer noch eine Kopie per Mail erhalten, aber da unter den letzten tausend Einträgen sowieso kein echter Beitrag war, ist das wohl unnötig. (Ebenfalls unnötig sind übrigens die Spameinträge, das Gästebuch hat nämlich schon immer noindex, nofollow gesetzt!)

01. Mar 2009

Vor einiger Zeit habe ich angefangen Texte und ein Buch mit LaTeX zu schreiben und habe dafür den Editor Texmaker genommen, da es der einzige platform-unabhängige, open-source Editor war, den ich finde konnte. Da der einige Fehler enthält, habe ich in einige kleine Patch erstellt, die dann immer größer wurden, bis sie schließlich zu dem Fork TexMakerX (auf Sourceforge) geführt haben. Zu den wichtigsten Feature, die ich hinzugefügt habe, gehört interaktive Rechtschreibprüfung, Codefaltung und eine Textanalyse.
Auf dieser Seite hier habe ich dagegen nur den Übersichtstext unten mal wieder aktualisiert und, dank eines Versionskontrollsystems, das Datum der Newsnachricht vor dieser richtig gestellt. (da stand nämlich noch 18. Okt) (Korrektur: Das VCS lag falsch, aber glücklicherweise hatte ich noch mein CMS)