BeniBela online

29. Aug 2010

I made a new version of my template based html parser. It is now probably thousand times slower and needs a magnitude more memory.
The old version used a NFA combined with a very clever heuristic, to match the template to the html page directly with O(1) memory and O(n) time, the new version uses simple backtracking on a DOM-like tree -- like everyone else does it -- with O(n) memory and I-don't-know-how-much time (perhaps O(k^n)?).
But it still runs in a few milliseconds, it is easier to understand the templates, and most important, the matcher/parser can now prove that a matching is possible or not. I also splitted it into three separate classes which makes it more easy to test.
Furthermore I had to change with the parser the bbutils (functions renamed or removed), the TreeListView and the search bar (A method removed to be LCL 27190 compatible).

26. Aug 2010

When I wanted to display the article below as "untranslated" on the German version, I noticed that JAXMLP did not support parentheses in if-conditions (perhaps because it would increase the implementation difficulty from trivial to easy). Anyways, I changed it and you can now use brackets there.

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

I just noticed that Andrey V. Sorokin's site regexpstudio.com does not exist anymore. His class TRegExpr was the best regular expression parser for Delphi and FPC. Because you need this class to use my internet tools, I created a mirror of TRegExpr.

10. Aug 2010

A Sirdslets update is there: 3 new levels, translations, accelerators and anaglyph rendering. The accelerators are like black holes, but independent of the ship position. The anaglyph rendering creates red/cyan images which you can see with 3d glasses. But they are a little bit confusing because most 3d glasses have a very bad channel separation and you will see everything three times.
And if you are interested in theoretical computer science and did not get the news: Deolalikar claims to have found a proof for P!=NP using a combination of graphical models, FO(LFP) logic and theoretical physics. If he is right, the third of the most famous problems is solved in just fifteen years (after Fermat and Poincaré), perhaps Riemann is going to be the next one.

28. May 2010

Today I uploaded my new SIRDSlets game which is one of the few games that you can play/see in real 3d without additional 3d glasses. It is also the first online game on this page, so you can play it without downloading it explicitely. However, although it is playable, it is not completely finished, but it is in that state since months and I don't have much time in the moment. Some things that are missing are additional levels and the opengl renderer from the last news, so it only has six levels that are software rendered.

16. Feb 2010

There is a new update of my Internettools: It fixes two small bugs that prevented the receiving of cookies without attributes and the creation of http connections over the 8080 port. It also add a global logging which is especially useful for debugging https. In the parser class the pseudo-XPath-expressions can now extract regex-matching data during the evaluation of the expression instead only afterwards like before. (real XPath-expressions does not support it at all)
Furthermore, some news have been moved in the archive and some uncompleted tools on the demo page.

07. Feb 2010

There is now a new demo page listing small program which are useless but demonstrate interesting techniques or show nice films.
Aside from some recategorizated old programs, there are two new ones on this page, both based on lecture exercises and rendering real 3d. The first draws hardware accelerated Single Image (Random Dot) Stereograms. SIRDS are flat pictures containing a 3d scene which you can only see by squinting. The other "Webcam-UCP" program creates traditional red/cyan anaglyphs. Furthermore it tracks the position of the 3d glasses via a webcam and renders the scene in user centered projection.

27. Jan 2010

06. Jan 2010

There are some minor changes in all the packets below, mostly I forgot to disable the unittests (and you probably don't want to have test log results everywhere). And the TreeListView won't flicker anymore on gtk when you scroll horizontally (I'm pretty sure that it also didn't flicker when I uploaded the last version...) and icons in the item tree will be clipped if the column is too short.

31. Dec 2009

And more updates: I merged the three packages with the template based html parser, the auto update and my Wininetwrapper into an Internet Tools-Package and made them platform-independent. (the main change is that the wininet wrapper is now also a Synapse wrapper). This new package requires/contains now my bbutils in which I fixed a crash on 64-Bit. (and probably renamed some functions since the last published version).
Furthermore I uploaded the pasdoc documentation from every (changed so far) package as online documentation and every archive has now a common structure. The root level of the zip contains a single directory named like the zip itself, which contains the data files, the changelog from Mercurial and, if available, the pasdoc documentation for that archive.

28. Dec 2009

So now I switched from Windows 32 bit to Linux 64 bit and need to update all the programs here which were theoretically platform-independent, but apparently didn't really work there.
The TreeListView is now a lot faster in LCL-GTK, because it will cache subsequent input events and draw all changes at once (actually it is a reported lcl bug that there are so many unnecessary events, but joining them is better anyways), and in every item you can now store a 64 bit value instead of a 32-bit value like before. I also changed the included SearchBar to set its size dependent on the currently used font. For both these components I created a Delphi and a Lazarus package, so you can place them on the form during the design time. Furthermore my JAXML parser can now create files in different encodings and \\-escaping works again (it seems I forgot to actually run the unit tests on the last release).

05. Okt 2009

16. Sep 2009

This week I finished and presented my bachelor thesis, so that I have now enough time to update this home page.
Today I added a java script that you can use to perform a Gaussian Elimination on a given matrix. Of course, there are already hundreds of such scripts online, but all of those I found, didn't work for the equations I wanted to solve, because they assumed that the matrix is quadratic and contains elements of a field instead of a ring. And most of them don't let you choose the order in which the operations are performed or allow neither import nor export of data. The only problem with my script is that java script is always a little bit slow, but anyways you don't solve equations with dozen variables step-by-step. And it seems that no one downloads anything in the web2.0 era.
An interesting fact I noticed while implementing this is that you can consider the Euclidean algorithm for finding the gcd as a special case of the Gaussian Elimination on a 2x1-matrix of integers.

15. Apr 2009

There is now a new program: Sun-Simulator which changes the brightness and shade of color of the monitor during the day and year, so that its light matches the sunlight.
Additional I wrote a diagram component for Lazarus which shows float points in multiple ways. It is based on a model/view system (because I use qt a lot at the moment) which can be used to create interesting effects very easily. E.g.: you can synchronize the data points across different windows and add some other points in one of them at the same time.

09. Apr 2009

A problem with writing open-source software is that you often receive patches which are completely useless, because they consists to 95 percent of changed whitespace. Therefore I wrote the command line tool Simplifydiff that removes all unnecessary data.
And all entries in the guestbook which are spam according to the heuristic are now removed without a backup. So far I received a copy as mail, but since the last thousand entries were really spam, this seems to be useless. (Actually the spam entries are also completely useless, because the guestbook has set the flags noindex, nofollow since the beginning!)

01. Mar 2009

Some time ago I started to write texts and even a book in LaTeX. Therefore I searched a platform-independent, open-source editor, and found only Texmaker.
But since he has some bugs, I created some small patches, which got bigger and bigger, until they finally lead to the fork TexMakerX (on Sourceforge). The most important features I added are, interactive spell checking, code folding and a text analysis.
On this web page I only updated the overview text below and corrected the date of the last news from 18.Okt to 27.Nov. (version control systems are really useful...) (correction: The date of the VCS was wrong, but my CMS got it right).