Forem: johnfound

AsmBB v3.0 has been released.

johnfound — Sun, 11 Jun 2023 13:31:24 +0000

AsmBB is very fast and lightweight web forum engine.

AsmBB is fully written in assembly language and uses SQLite as a database back-end. That is why it can work on really weak hosting and in the same time serve huge amount of visitors without lags and delays.

AsmBB is very secure web application, because of the internal design and the reduced dependencies. But it also supports encrypted databases, for even higher security.

There are mainly security updates in this release.

Read the details (and test the engine):https://board.asm32.info/asmbb-v3-0-has-been-released.401/

AsmBB v2.9 has been released. With new beautiful theme and emoji!!!111 🏆🥇

johnfound — Thu, 28 May 2020 11:53:38 +0000

The official v2.9 of AsmBB has been released.

The main and most important new feature of the engine is the new theme "Urban Sunrise" which (besides its very beautiful appearance) has advanced post editor and supports Unicode emoji both for the forum posts and the chat conversations.

Here is a screenshot from inside the admin account:

Touch and feel it by yourself: https://board.asm32.info/asmbb-v2-9-has-been-released.328/

Any criticism on the web design and UX is highly appreciated!

The negative feedback is preferred. 😂

AsmBB v2.7 has been released. Now encrypted databases are supported.

johnfound — Fri, 04 Oct 2019 08:01:22 +0000

Has been released the next, v2.7 of the assembly language written forum engine AsmBB.

The major new feature (besides several minor bug fixes) is the support for fully encrypted database.

The encryption is provided by the SQLite extension SQLeet.

The implemented encryption seriously increases the security and privacy level of AsmBB. Now even leaking of the database or serious breach in the server will not compromise the security of the forum database.

The encryption is of course optional and the implementation is fully backward compatible with the existing non-encrypted databases.

P.S. The project still is looking for the contributors, especially about the design and the front-end issues.

Unfortunately, the most of the complaints of the users is about the forum "ugliness". :D

Interesting hash tree implementation

johnfound — Tue, 16 Jul 2019 19:19:11 +0000

The hash tables are great when we need to search a string in a big set of strings.

They provide O(1) complexity this way making our algorithms very fast.

Unfortunately, the hash tables have one big disadvantage, especially when we are talking about huge sets of strings.

Because it is important to keep the hash collisions as low as possible, the size of the hash table must be at least twice the count of the strings we need to put inside.

This way, on a very big set of strings, the memory waste can be really huge. And if we fill the table more, the speed of the search degrades very fast down to simple linear search with O(n).

There are different ways to counteract these problems. For one of them I am writing here.

The author of the algorithm is Tomasz Grysztar, the author of FlatAssembler.

FlatAssembler uses this algorithm in order to handle huge number of label names during compilation.

The algorithm is slower than the classic hash table, but still will keep the complexity to O(log k) where k is the size of the hash, not the size of the set.

This way, the search time will remain constant regardless of the strings count in the set and can be assumed to be O(1).

Considering the much lower number of collisions, on large sets it can be faster than a classic hash table with smaller hash size.

Adding strings to the tree.

At first we need to compute the hash of the string. It is good idea to use relatively big hash, for example 32bit, in order to minimize the collisions.

I am usually using the FNV-1b hash, but the hash algorithm is not very important for the understanding of the algorithm.

Then we need a linear memory area, where elements of the following type will be allocated consecutively:

struct THashTreeNode
  .bit0 dd ?
  .bit1 dd ?
ends

Then starting from the first array element and shifting the hash one bit right at a time, we put in the .bit0 or .bit1 fields (depending on the value of the bit shifted) the offset to the next element of the array where to continue the scan.

The next element is allocated at the end of the array, just after the last used element. (like in a queue or linear list).

When we reach the 32nd bit of the hash, the last index will point to the element with the payload (or the leaf of the tree if you prefer) - it can occupy random space, but it is more convenient if the size of the leaf structure is multiple of the size of the node structure.

In my implementation it occupies two consecutive elements of of the array:

struct THashTreeLeaf
  .hString dd ?         ; a handle of the string stored.
  .next    dd ?         ; the next element in the cases of collisions.
  .lparam  dd ?         ; user defined parameter.
  .wparam  dd ?         ; user defined parameter.
ends

The field .hString contains a pointer or a handle to the string we put in the tree. (in the library I use, the strings are dynamic and are represented by a handles, not pointers. But the difference is not important)

The field .next contains an offset to the next THashTreeLeaf in the rare cases if we have two different strings with the same hash (a collision).

Searching the string in the set.

The searching algorithm is almost the same as when we are adding strings to the set.

Starting from the beginning of the array, we are shifting the searched string hash one bit at a time and jumping to the offsets from the .bit0 and .bit1 fields. If on some step the offset is 0 this means the string is not in the tree.

If after 32 steps, we find a leaf element, a direct string comparison with the stored string is needed in order to resolve the possible collision.

Then if the strings does not match, we need to follow the offsets from the THashTreeLeaf.next fields until 0 (the string is not in the tree) or string match - the string is in the tree.

You can see that in the later case, the search deteriorates to a simple and slow linked list search. Fortunately, when the hash is 32 bit such collisions are really rare.

Advantages

The algorithm is memory friendly.

The whole tree is in one contiguous memory area, which is good for the CPU caches and additionally improve the performance.

The algorithm is relatively simple, at least for assembly language implementation.

I am not sure how it will be implemented in higher level languages, but at least for C/C++/Pascal there should be no problems, except for some possible code readability issues...

Notice, that the same algorithm can be implemented as an usual tree with separately allocated nodes and leafs. But such implementation will be slower, because of the heap allocations of multiply small chunks of memory and because of the cache issues.

The quiz

In order to make the things even more clear, here is the full code of the procedure that can add strings to the tree and also to search the tree for a string without adding it.

Because the searching and adding algorithms are very similar, it is possible to provide both functions in a single procedure.

As a little quiz to the readers I will not put detailed line-by-line explanations of the code. It is published in the same form it exists in the production library.

I will give only a little reference to the external procedures used at the end of the article.

So, that is all. Here is the code. Try to analyze and understand it! :)

If something is not clear ask in the comments.

I will explain it in details, but let give some fun time for the puzzle solvers.

; Searches the hash tree for the given string.
; if [.fAdd] is TRUE and if the string is not in the tree it will be added.
;
; Arguments:
;   .pHashTree - pointer to TArray with elements size sizeof.THashTreeNode (8 bytes)
;   .hString - handle/pointer to the string to be searched/added. Notice, that exactly this
;              string will be added to the THashTreeLeaf element. The caller is responsible
;              to not free this string until the hash tree is needed.
;   .fAdd - flag indicating whether to add the string to the tree if is not included.
;
; Returns:
;   edx - pointer to the array. Can be reallocated!
;   eax - index in the TArray of the THashTreeLeaf of the string.
;   CF = 1: the string is already in the tree.
;   CF = 0: the string is not in the tree.
;     [.fAdd] <> 0: eax contains a pointer to the new added leaf.
;                   eax == 0 means there is an out of memory error on
;                   the attempt to add the string.
;     [.fAdd] = 0: eax == 0

proc SearchHashTree, .pHashTree, .hString, .fAdd
.hash dd ?
begin
        pushad

        mov     edx, [.pHashTree]

        stdcall StrHash, [.hString]
        mov     [.hash], eax

        mov     ecx, 32              
        mov     ebx, TArray.array

        cmp     [edx+TArray.count], 0
        jne     .treeseek

        stdcall AddArrayItems, edx, 1
        and     dword [eax+THashTreeNode.bit0], 0
        and     dword [eax+THashTreeNode.bit1], 0

.treeseek:
        xor     edi, edi
        ror     [.hash], 1
        adc     edi, edi
        lea     edi, [ebx+4*edi]

        cmp     dword [edx + edi], 0 ; edi is offset from the beginning
                                     ; of the array.
        je      .notfound

        mov     ebx, [edx + edi]
        loop    .treeseek

; The hash exists in the hash tree. Process the possible collisions.
; here ebx is the offset to the THashTreeLeaf !

.cmp_loop:
        stdcall StrCompCase, [.hString], [edx+ebx+THashTreeLeaf.hString]
        jc      .finish      ; the string is already in the hash tree!!!

        lea     edi, [ebx + THashTreeLeaf.next]

        cmp     dword [edx + edi], 0
        je      .add_in_list

        mov     ebx, [edx + edi]
        jmp     .cmp_loop

.add_in_list:
        cmp     [.fAdd], 0
        je      .finish_zero

        stdcall AddArrayItems, edx, 2
        jc      .finish_zero

        sub     eax, edx
        jmp     .do_add


.notfound:
        cmp     [.fAdd], 0
        je      .finish_zero

; edx - pointer to the tree array,  ebx - offset of the last 
;       found element.
; eax - 0 or 1 depending of the last bit checked. 
; ecx - remaining bits count.
; edi - the offset to the [.bitX] field of the last node.

.add_remaining:

        lea     eax, [ecx+1]
        stdcall AddArrayItems, edx, eax  ; add all needed (THashTreeNode) + THashTreeLeaf
        jc      .finish_zero

        sub     eax, edx

        dec     ecx
        jz      .do_add

.addloop:
        mov     [edx + edi], eax
        and     dword [edx + eax + THashTreeNode.bit0], 0
        and     dword [edx + eax + THashTreeNode.bit1], 0

        xor     edi, edi
        ror     [.hash], 1
        adc     edi, edi

        lea     edi, [eax + 4*edi]
        add     eax, sizeof.THashTreeNode
        loop    .addloop

.do_add:
        mov     [edx + edi], eax
        lea     ebx, [edx+eax]

        mov     ecx, [.hString]
        xor     eax, eax

        mov     [ebx+THashTreeLeaf.hString], ecx
        mov     [ebx+THashTreeLeaf.next], eax
        mov     [ebx+THashTreeLeaf.lparam], eax
        mov     [ebx+THashTreeLeaf.wparam], eax

        clc

.finish:
        mov     [esp+4*regEAX], ebx
        mov     [esp+4*regEDX], edx
        popad
        return


.finish_zero:
        xor     ebx, ebx
        clc
        jmp     .finish
endp

Very small cheat sheet:

TArray is a structure of a dynamic array that can be resized when needed. (the source)

The procedure AddArrayElements adds new elements at the end of TArray and returns in EAX a pointer to these new elements and in EDX the pointer to the array that can be reallocated because of the resizing.

The procedure StrHash computes 32bit hash of a string and returns it in EAX

The procedure StrCompCase compares two strings, case sensitive and returns Boolean result in CF flag. 1 if the string match and 0 if not.

Quick assembly instruction reference for the absolute beginners: here

NB: The above implementation is far from optimal. It is written in order to be readable and correct. The optimizations will be made later. The bug fixes as well.

Fresh IDE v2.7.0 has been released

johnfound — Tue, 09 Jul 2019 11:29:37 +0000

Fresh IDE v2.7.0 has been released.

Fresh IDE is an advanced IDE for assembly language programming (FASM).

It is fully written in assembly language, self hosting and is especially designed for comfortable programming of very big assembly language projects.

The current release highlights:

The main change in this release is the final transition of the FreshLib to the new GUI architecture. Not finished, but on the right path now.
FlatAssembler compiler has been updated to the version 1.73.12.
The syntax highlighting of the editor is improved to support user defined keywords for coloring.
Two builtin fonts, especially suitable for assembly programming has been added to the editor themes.
More extended tests has been provided on Windows 10. As a result, the editor rendering and the overall stability has been improved.
The included examples has been revised and fixed to compile with the latest FreshLib libraries.
Of course the usual bug fixing and new bug introduction has been made as well.

Contributors wanted for unusual project.

johnfound — Wed, 26 Jun 2019 11:48:22 +0000

I am looking for contributors for my project AsmBB.

What is this project about?

AsmBB is a forum engine, written in assembly language. It uses FastCGI as a server protocol and SQLite as a database engine.

In addition, the FastCGI framework of the project can be used for other web projects in assembly language.

The main goals of the project are:

Performance - the back-end is ultimately fast and lightweight. It can handle huge amount of visitors simultaneously without slow down or faults, even on very small and cheap VPS or shared hosting accounts.
Virtually no external dependencies - the engine needs only a working web server and Linux OS. It does not need any other libraries installed or special server configuration.
Internationalization - the engine has UI translated to different languages and every user can set whatever of the language he prefer.
Easy for customization - the engine supports multiple skins simultaneously and the users can change their skin, according to their preferences. In addition, automatic switching to a mobile skins is available.

The skins are entirely based on a text templates and css/less files and can be easily edited and created without messing with the back-end code.
Security - On contrary of the commonly accepted opinion, the engine is extremely secure. The low number of abstraction layers and the missing dependencies greatly decrease the possible attack vectors.

What is wrong?

The front-end and the design!

Regardless of that the engine supports multiple skins and I have created several of them, my front-end and designers skills are very low and most of the visitors complain that the front-end is not what it needs to be in 2019.

Contributors out there?

So, I am looking for contributors that to turn the front-end of the forum in what is supposed to be in 2019 year.

Both, creating new skins and fixing the existing is possible and desirable.

But in the same time, it is good to make it in a most lightweight way, because, well, a website that pretend to be the fastest forum in the world, should stay fastest at the browser side as well.

It is good also to keep the forum working without JS, at least for the parts where it is possible. (for example, the real-time chat is impossible to be implemented without JS).

Of course, if someone wants to contribute to the back-end, he is welcome as well. There are many features that need to be implemented there.

BTW, this is a wonderful way to perfect your assembly language skills outside of the school problems: "two numbers are given in registers ax and bx, compute the sum in cx".

And also, your SQLite query optimization skills.

What technologies?

On the back-end the project uses FASM assembly language. Also some C code is used in unmodified form: SQLite and MUSL C libraries.

On the front-end there is a template engine, CSS and vanilla JS.

The version control used is Fossil scm which is the best DVCS for small projects.

So, the contributors will have the chance to work with a technology stack that is not widespread.

This can be an interesting trip off the beaten paths for a curious developer wanting to experiment with the technologies and searching for the best possible solutions.

Video of one hour of assembly programming.

johnfound — Sat, 22 Jun 2019 17:55:29 +0000

Here is a video of one hour of my assembly language programming session.

Very often, when I am discussing about assembly language programming, I have some feeling, that the opponents simply can't imagine the whole process and think that it is some kind of very different (and very hard!) from other languages.

So, I decided to make a screencast of my programming process in order to give a general idea about what programming I am writing in my posts.

This video shows implementation of multiple files open through the file open dialog in Fresh IDE v3.x project.

Actually it is a work on two projects simultaneously: The GUI toolkit of FreshLib (the file dialog and the components TGrid and TListView) and the Fresh IDE itself (which is in very early stage and I am using it mainly as a test project for the GUI toolkit.

The GUI toolkit uses OOP macro library of FreshLib, so, some of the instructions used may look a little bit strange.

Unfortunately, a lot of the process remains behind the camera - in my head. So, some of you can find the video a little bit boring. But hope you will like the music if not the video.

Your powerful dev computer is your weakness.

johnfound — Thu, 20 Jun 2019 12:01:41 +0000

Usually the developers like to use powerful computers.

They can explain this with many reasons, but the truth is that it is easy to work on a faster computer and the developers are usually rich enough to be able to buy a high-end machine. Or their employers are.

But, come on! Today, even the slowest low-end netbook has huge (I mean HUGE!) computational power.

If we, the experts, can't setup our processes to work great on this extremely fast hardware, how we can ask our users to use our software on their slow, old, cheap machines?

In addition, my experience clearly shows that the programmers improve their software only until it works acceptably fast on their own computer.

Beyond this point the programmer will cook up thousand excuses and explanations, but will not optimize further.

Will claim it is impossible, will talk about "premature optimizations" and will threaten about very expensive and hard support.

The truth is that the optimization is tedious process and when you can't feel the acceleration, you will never understand why you should make this work instead of programming something funny.

So, working on the slower machine, the programmer will always create software of higher quality. This effect works automatically and unconsciously.

That is why I am using for programming, the slowest possible computer I was able to buy (and that has more or less modern hardware, supporting the latest CPU extensions).

It is ASUS X102BA netbook with AMD A4-1200 CPU (2 cores, working on 1GHz), 4GB of RAM and 500GB HDD;

It is running Manjaro Linux with XFCE.

When I am in the office, I am connecting external HDMI display (2560x1440) and good mechanical keyboard.

In addition to the very high positive effect on the quality of my programs, the netbook has additional advantage - it is pretty mobile - very small (266x185x23 mm) and very lightweight (1.1 kg). I am carrying it always with me and can start to program instantly in every moment.

What you think about such point of view?

How I am partitioning the HDD for Linux setup.

johnfound — Wed, 19 Jun 2019 14:21:25 +0000

The bellow described workflow is not commonly accepted. Even more, I am not sure it can be defined as a "good practice" or "unix way".

Nevertheless, it is very convenient and helps to save my working files during disasters.

Notice that this method is suitable and convenient only for computers that are used by a single user. But well, we are working on "personal computers" after all.

So, I usually have two Linux distributions installed simultaneously. At first for easy disaster recovery and also for experiments when I want to test some distro, or to test my software on different distribution.

At first I am creating the boot and swap partitions if needed.

Then, I am creating two relatively small partitions (20..50GB) for installation of two Linux distributions.

On the whole remaining space on the HDD I am creating a single huge partition labeled "work".

Then, when I am installing Linux, I am mounting this partition as a /work directory (yes, on the root of the file system) and later I am placing all my working files in this partition, leaving the /home/USERNAME directory to the OS to make inside whatever it wants.

This approach has several big advantages:

You can use your files in every of the installed OSes on the same path. Even if you are booting from an USB thumb drive or CD, you still can mount the work partition and have access to all your important files.
The OS knows nothing about this path, so it will never put its files inside. (in contrast with /home/USERNAME that Linux owns in all possible ways).
The paths to your working files will be always very short and the same.
You can always format one or both of the OS partitions and install different Linux distribution, without need to backup your working files somewhere.

Someone may say that you can mount this working partition on /home or /home/USERNAME, but this is really bad idea.

Mainly because booting from different Linux instances will instantly ruin your personal configuration files placed in your home directory. Simply because the different Linux distributions often differs in the way they create and use configuration files.

Lightning fast installation of AsmBB forum.

johnfound — Tue, 18 Jun 2019 08:20:50 +0000

The web applications are often complex for installation. Mainly because of the dependencies and complex configuration.

Here is how it should be done:

AsmBB web forum engine has very few dependencies. It needs only Linux and some web server.

In the bellow video, the fastest, assembly language written web server RWASA is used.

So, less talks, more action! Look how to install AsmBB forum and make a post for less than two minutes:

P.S.: Of course, this is not a production installation. But on a real server you will need only to make the programs to start automatically.

Here is an article about how to install AsmBB on a production server with systemd and nginx. You can see it is almost as easy and quick.

Why assembly programs are faster than HLL programs, despite that the compilers are so advanced?

johnfound — Mon, 17 Jun 2019 16:06:13 +0000

The paradox.

The hand written assembly language programs are faster and use less memory than the programs with the same features, but written in high level languages (HLL).

I will give below some examples from the real life. In addition I have made several artificial experiments that show the same.

This looks like a paradox, because the HLL compilers are very effective these days and for big programs generate more optimal code, than the hand written assembly language.

Yes, it can be formally proven the following theorem:

The hand written assembly language code, is always more optimal or equal to the compiler generated code.

This statement is easily proved by the fact, that the programmer can always read the compiler output and optimize it further, while the compiler can't do the same with the programmers code.

But this theorem is not very helpful in the real life. Simply because the compilers generate huge amount of code, that can not be manually read, analyzed and optimized by a human.

Fortunately, the assembly language programmer, does not need to compete with the compiler in the platform specific optimizations, in order to beat it.

The fastest assembler today is FlatAssembler. It is written in assembly language and is "optimized" for 80386 CPU, if this can be qualified as optimization at all. The competitors are written in C/C++ and are slower, despite of the more optimal code generated by the C/C++ compiler.

The fastest OS I know is KolibriOS written in assembly language. It boots for less than 2 seconds to the GUI desktop. Even the BIOS startup is slower. And the GUI is instantly responsive even on very slow and old machines.

The fastest web server is RWASA and it is the only of the above examples that is really optimized for speed. But it still uses less memory than its competitors. (I mean, the speed optimizations in HLL, often leads to increased memory use)

Actually, in most cases, writing programs in assembly language, the programmers put more effort in writing smaller and readable code, than in writing faster code. But as a result, these programs always perform faster than their HLL counterparts.

Why?

Let see the so called "Jevons paradox". This is an economics paradox, but actually it can be applied to the programming as well.

In economics, the Jevons paradox occurs when technological progress increases the efficiency with which a resource is used (reducing the amount necessary for any one use), but the rate of consumption of that resource rises due to increasing demand.

If we apply this definition to the programming, we can see, the direct analogy. The compilers actually increases the efficiency with which the computer resources are used by the programmers. With one line of code in HLL the programmer can use more resources than with one line of code in assembly language.

The same way more efficient car have greater mileage with a liter of fuel.

As a result, the use of the computer resources CPU and RAM increases. Because of increased demand.

The same way the traveled kilometers and the total fuel consumption increases with more efficient cars.

Notice, that the increased efficiency of the compilers is not the only increased efficiency in the IT. The efficiency of the hardware also increases with the time. Now the RAM is faster and bigger than ever, the CPUs are also pretty efficient.

But all these improvements, lead only to increased consumption of the resources. In full accordance with Jevons paradox.

As simple as that.

How to counteract?

In economics, there are tools to counteract the Jevons paradox. For example, the increased taxes can stop the demand raise and neutralize the effect if the goal is to reduce the resource consumption.

All other possible countermeasures are always related to some forced restrictions.

But there is no taxes or other regulations for "CPU cycles" or "RAM usage".

The only way for the programmers is to consciously limit themselves from using this increased effectiveness of the HLL compilers and hardware improvements.

Someone will probably ask here "Why we should limit the resource use? The RAM is cheap and the CPU is fast."

The answer is simple and straightforward: Because we will need these resources in order to develop our programs further.

In addition, the programmers time is of course important, but the programmers often forget that the program is written once, but executed sometimes millions of times. One saved second by writing faster program, can result in millions of saved seconds for the users of the program.

Yes, the program needs maintenance and further development, but who said, more optimal program needs more effort for the maintenance?

Мy experience with the development of assembly language projects clearly shows that maintenance efforts practically do not depend on the programming language.

For example, the mentioned above FlatAssembler is developed and maintained for almost 20 years by a single person. I didn't noticed some enormously great effort for this program to be maintained, regardless of the fact it is written entirely in assembly language. Sometimes the reported bugs are fixed for hours or even minutes.

Of course, the programs in HLL also can be written in efficient manner. There are many examples of C/C++ projects written this way and really performing excellent.

But the higher is the level of the language, it is harder to write efficient code. For me, languages like C++, Pascal or Fortran are the higher level language that allows somehow to counteract the Jevons paradox.

Languages like Java, C# or Python are totally affected by the paradox and it seems that any counteract is impossible by design.

The future

Fortunately or not, but the overgrowth of the computer performance, actually ended. There will be no exponential growth anymore. Nor even close. We can expect some slow linear growth, or even some decline (the mobile devices, lower energy consumption, recently revealed CPU and DRAM bugs) of the computers performance and resources.

So, now the programmers have the time to put their code in order and to start to pay this giant technological debt they accumulated during the big bang of the hardware.

If during the exponential growth the technical progress provided the RAM and CPU for the next program version, now this time ended.

If someone have a program that uses all resources of the computer and want to implement new features, he will be forced first to optimize the existing features to use less memory and CPU and to use the released resources for the new features of the program.

And I have some strong suspicions that this process is already silently (and probably unconsciously) running in most of the software companies and big open source projects.

But for the new projects, the economical use of the resources from the day one, seems to be better strategy, simply because it is easier to write resource friendly code from the beginning, than to rewrite it later.

BTW, more and more people start to call for more resource friendly code. I am reading such articles every day on different blogs and social networks.

So, interesting times are coming. The era of deep software optimization.