Flipped World

To develop a new project Cube Art Project has adopted a methodology for the development of Test Driven Development. In this approach, implemented first test for a particular functional application, and then implemented this functionality. A great advantage in this approach, I believe the final implementation of the interfaces, the most uninitiated in the details of implementation, prior to the development of the functional. With this approach, the test dictates the further implementation, added to all the advantages of contract programming when interfaces are contracts for the implementation.

Cube Art Project – 3D editor in which the user builds the shape of cubes, not so long ago, this genre was very popular. Since this graphic application, I decided to add tests to the validation of screenshots.

For screenshot validation you need to get them from OpenGL context first, it is done with the help of glReadPixels function. Description of function arguments are simple – the starting position, width, height, format (. RGB / RGBA / etc.), a pointer to the output buffer, anyone working with SDL or having experience with data buffers in C will simply substitute the correct arguments. However consider it necessary to describe an interesting feature of the output buffer glReadPixels, the pixels stored therein upwards and in SDL_Surface all basic operations taking place downwards.

That is, the reference by uploading a screenshot from the png file, I could not compare the two buffers in the forehead, as one of them upside down.

To flip the output buffer of OpenGL you need to fill it up taking away the height of the screenshot to coordinate Y. However, cost to take into account that there is a chance to go beyond the buffer limits, if not take the unit to fill the time, which will lead to memory corruption.

Since I’m all over the place trying to use OOP paradigm “programming interfaces”, instead of a direct C-like memory access at the sign, when you try to write data outside of the buffer object I reported it to the method of borders through validation.

Final code method of obtaining screenshots in the style of top-down:

    auto width = params->width;
    auto height = params->height;

    auto colorComponentsCount = 3;
    GLubyte *bytes = (GLubyte *)malloc(colorComponentsCount * width * height);
    glReadPixels(0, 0, width, height, GL_RGB, GL_UNSIGNED_BYTE, bytes);

    auto screenshot = make_shared(width, height);

    for (auto y = 0; y(redColorByte, greenColorByte, blueColorByte, 255);
            screenshot->setColorAtXY(color, x, height - y - 1);




Source Code



Longest Common Substring

In this article I will describe an algorithm for solving the longest common substring. Suppose we try to decipher the encrypted binary data, first try to find the common patterns by searching the largest substring.
The input string for example: adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
We are looking for a line repeated twice: DATAHEADER??


To begin write method for comparing prefixes of two rows, let returns the resulting string in which a left prefix symbols are the symbols of the right prefix.
For example, for strings:

        val lhs = "asdfWUKI"
        val rhs = "asdfIKUW"

The resulting string – asdf
Example of Kotlin:

fun longestPrefix(lhs: String, rhs: String): String {
        val maximalLength = min(lhs.length-1, rhs.length -1)
        for (i in 0..maximalLength) {
            val xChar = lhs.take(i)
            val yChar = rhs.take(i)
                if (xChar != yChar) {
                    return lhs.substring(0, i-1)
        return lhs.substring(0,maximalLength)

Brute Force

When it is impossible for a good, should resort to brute force. Using the method longestPrefix pass on row two cycles, the first line takes from i to the end of the second i + 1 to the end, transmits them to the search for the largest prefix. The time complexity of the algorithm is approximately equal to O (n ^ 2) ~ O (n * ^ 3).
Example of Kotlin:

fun searchLongestRepeatedSubstring(searchString: String): String {
        var longestRepeatedSubstring = ""
        for (x in 0..searchString.length-1) {
            val lhs = searchString.substring(x)
            for (y in x+1..searchString.length-1) {
                val rhs = searchString.substring(y)
                val longestPrefix = longestPrefix(lhs, rhs)
                if (longestRepeatedSubstring.length < longestPrefix.length) {
                    longestRepeatedSubstring = longestPrefix
        return longestRepeatedSubstring

Suffix array

For a more elegant solution, we need a tool - a data structure called "suffix array." This data structure is an array of substrings filled in a loop, where every substring starts the next character string to the end.
For example for a row:


Suffix array looks like this:


Solve sorting

Sort the suffix array, and then go through all the elements of the cycle where the left hand (lhs) the current item on the right (rhs) and calculate the next longest prefix using longestPrefix method.
Example of Kotlin:

fun searchLongestRepeatedSubstring(searchString: String): String {
    val suffixTree = suffixArray(searchString)
    val sortedSuffixTree = suffixTree.sorted()

    var longestRepeatedSubstring = ""
    for (i in 0..sortedSuffixTree.count() - 2) {
        val lhs = sortedSuffixTree[i]
        val rhs = sortedSuffixTree[i+1]
        val longestPrefix = longestPrefix(lhs, rhs)
        if (longestRepeatedSubstring.length < longestPrefix.length) {
            longestRepeatedSubstring = longestPrefix
    return longestRepeatedSubstring

Time complexity O (N log N), which is much better than brute force algorithm.



Source Code



Insertion Sort, Merge Sort

Insertion Sort

Insertion sort – each element is compared to the previous item in the list and inserted in place of more. Since the items are sorted from first to last, then each successive element is compared with pre-sorted list that *might* reduce the total time. Time complexity O(n^2), that is identical to the bubble sort.

Merge Sort

Merge sort – the list is divided into groups of one element, then the group “merge” in pairs with simultaneous comparison. In my implementation at the merge of pairs elements to the left compared with the right elements, and then moved to the result list, if the items in left are over, then right list elements added to resulting list (their extra comparison is unnecessary, since all the elements in the groups are sorted by iterations)
The operation of this algorithm is very easy to parallelize, pairs merging step can be performed in threads, with thread dispatcher wait.
Algorithm output for single-threaded performance:

["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["Alice", "John"], ["#1", "Mike"], ["20", "Артем"], ["60", "60"], ["DoubleTrouble"]]
[["#1", "Alice", "John", "Mike"], ["20", "60", "60", "Артем"], ["DoubleTrouble"]]
[["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"], ["DoubleTrouble"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Algorithm output for multithreaded execution:

["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["20", "Артем"], ["Alice", "John"], ["60", "60"], ["#1", "Mike"], ["DoubleTrouble"]]
[["#1", "60", "60", "Mike"], ["20", "Alice", "John", "Артем"], ["DoubleTrouble"]]
[["DoubleTrouble"], ["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Time complexity O (n * log (n)), which is slightly better than O (n ^ 2)



Source Code



Bubble Sort in Erlang

Bubble sort is quite boring, but it becomes more interesting if you try to implement it in a functional language for telecom – Erlang.

We have a list of numbers, we need to sort it. bubble sort algorithm runs through the whole list, iterating, and comparing the number of pairs. Upon verification of the following occurs: a smaller number is added to the output list, or change the number of places in this list if the right is smaller bust continues with the next iteration number. This bypass is repeated as long as the list will no longer be replaced.

In practice it is not necessary to use due to the large time complexity – O (n ^ 2); I implemented it in Erlang language in an imperative style, but if you’re interested you can look for the best options:


startBubbleSort([CurrentHead|Tail]) ->
    compareHeads(CurrentHead, Tail, [], [CurrentHead|Tail]).

compareHeads(CurrentHead, [NextHead|Tail], [], OriginalList) ->   
        CurrentHead < NextHead ->
            compareHeads(NextHead, Tail, [CurrentHead], OriginalList);
        true ->
            compareHeads(CurrentHead, Tail, [NextHead], OriginalList)
compareHeads(CurrentHead, [NextHead|Tail], OriginalOutputList, OriginalList) ->
        CurrentHead < NextHead ->
            OutputList = OriginalOutputList ++ [CurrentHead],
            compareHeads(NextHead, Tail, OutputList, OriginalList);
        true ->
            OutputList = OriginalOutputList ++ [NextHead],
            compareHeads(CurrentHead, Tail, OutputList, OriginalList)
compareHeads(CurrentHead, [], OriginalOutputList, OriginalList) ->
    OutputList = OriginalOutputList ++ [CurrentHead],
        OriginalList == OutputList ->
            io:format("OutputList: ~w~n", [OutputList]);
        true ->
main(_) ->
    UnsortedList = [69,7,4,44,2,9,10,6,26,1],

Install and run

In Erlang Ubuntu install is easy, just enter the following command in a terminal sudo apt install erlang. In this language, each file must be of a module (module), a list of functions that can be used outside – export. The interesting features of the language is the lack of variables, only constants, there is no standard syntax for the PLO (which does not prevent the use of OOP techniques), and of course the parallel computing without locks based on actor model.

Start module can be either through an interactive console erl, running one command after another, either through easier escript bubbleSort.erl; For different cases the file will look different, for example escript necessary to make the main function, from which it will start.




Source Code



Lexicographical comparison

lexicographic comparisons rows algorithm works very simple loop compares the character codes and the result is returned if the symbols are not equal.

An example for the C language can be found here:

Keep in mind that you need to compare the characters in a single static encoding, such as Swift, I used the comparison character by character to UTF-32. Array sorting option using memcmp work exactly for single-byte character, otherwise (variable length coding) may order is incorrect. I do not rule out the possibility of implementation on the basis of a variable-length encoding, but is likely to be much more complicated.

Time complexity at most O(1), the average and worst-O(n)



Source Code



Write in C (ZX Spectrum) GameDev

This ne’er-do note is devoted to the development of games for the ZX Spectrum old computer to C. Let’s take a look at the handsome:

He began producing in 1982, and was produced until 1992. Technical data: 8-bit processor Z80, 16-128kb memory and other are extensions such as audio chipAY-3-8910.

The competition Yandex Retro Games Battle 2019 for this machine I wrote a game called Interceptor 2020. Since learning assembler for the Z80 did not have time, I decided to develop it in C language. As tulcheyna I chose the Quick Set – z88dk, which includes C compilers, and many support libraries to accelerate the implementation of applications for the Spectrum. It also supports many other Z80 machines, such as MSX, Texas Instruments calculators.

Next I will describe his flight over the surface computer architecture tulcheynom z88dk, show how it was possible to implement OOP approach is to use design patterns.

Special features

z88dk installation should be performed by a manual from the repository, but for Ubuntu users, I would like to mention feature – if you have already installed compilers for Z80 from the deb package, you should remove them as z88dk will default to access them from the bin folder of the -this version incompatibility tulcheyn compiler, you probably will not be able to collect anything.

Hello World

Write Hello World is very simple:

#include void main()
    printf("Hello World");

Assemble the tap in the file is even easier:

zcc +zx -lndos -create-app -o helloworld helloworld.c

To start using any emulator ZX Spectrum tap supporting files, such as Online:


Draw on the image to full screen

tl; dr Pictures drawn tiles, tiles 8×8 pixels size, the tiles themselves are embedded in the font Spectrum, then the string of index picture is printed.

O library sprites and tiles sp1 displays tiles using UDG. The picture is translated into a set of separate UDG (tiles) is then collected on the screen using the indices. It should be remembered that UDG is used to display the text, and if your image contains very large set of tiles (eg more than 128 tiles), you have to go beyond the set boundaries and to erase the default font Spectrum. To work around this limitation, I used a base of 128 – 255 using the simplified representation, leaving the original font on the spot. On simplification of the pictures below.

To draw a full-screen images you need to arm the three utilities:

There is a way ZX real men, real retro warriors is to open the editing palette using Spectrum, especially knowing the output image, prepare it and manually unload using png2c-z88dk or png2scr.

Way easier – take a 32-bit image, switch to Gimp colors to 3-4, slightly to edit, then import into img2spec not to work by hand with color restrictions, export png and transferred to the C array with png2c-z88dk.

It should be remembered that successful export each tile can not contain more than two colors.

As a result, you get the h file that contains a number of unique tiles, if more than ~ 128, simplify the Gimp in a picture (increase repeatability) and spend on a new procedure for export.

After exporting, you literally download a “Font” from the tiles and typing “text” of the indices of tiles on the screen. Here is an example of the “class” of the rendering:

// loading font into memory
    unsigned char *pt = fullscreenImage->tiles;

    for (i = 0; i < fullscreenImage->tilesLength; i++, pt += 8) {
            sp1_TileEntry(fullscreenImage->tilesBase + i, pt);

    // set cursor into 0,0
    sp1_SetPrintPos(&ps0, 0, 0);

    // print string
    sp1_PrintString(&ps0, fullscreenImage->ptiles);

Drawing sprites on the screen

Next, I will describe a way of drawing sprites of 16×16 pixels on the screen. Before the animation and change colors I came because corny at this stage, I guess I ran out of memory. Therefore, in the game there are only transparent monochrome sprites.

Draw in Gimp monochrome png image 16×16, etc. using png2sp1sprite translate it into assembly asm file in C code declare arrays of the assembly file, add the file at build time.

After the declaration of a resource of the sprite, it is necessary to add the screen to the desired position, then the sample code “class” game object:

    struct sp1_ss *bubble_sprite = sp1_CreateSpr(SP1_DRAW_MASK2LB, SP1_TYPE_2BYTE, 3, 0, 0);
    sp1_AddColSpr(bubble_sprite, SP1_DRAW_MASK2,    SP1_TYPE_2BYTE, col2-col1, 0);
    sp1_AddColSpr(bubble_sprite, SP1_DRAW_MASK2RB,  SP1_TYPE_2BYTE, 0, 0);
    sp1_IterateSprChar(bubble_sprite, initialiseColour);

From the names of some functions can understand the meaning – allotsiruem memory sprite, add two columns 8×8, add color for a sprite.

Each frame is affixed position of the sprite:

sp1_MoveSprPix(gameObject->gameObjectSprite, Renderer_fullScreenRect, gameObject->sprite_col, gameObject->x, gameObject->y);

OOP simulations

In C, there is no syntax for OOP, what do you do if you still really want to? It is necessary to connect the Dumka and illumined thought that such a thing as the PLO equipment does not exist, everything eventually comes to a machine architectures in which there is simply no concept of the object and other related abstractions.

This fact bothered me for a long time to understand why do you need the PLO, why you need to use it if in the end everything comes to machine code.

However, having worked in the product development, I opened the charm of this programming paradigms, primarily of course the development of the flexibility mechanisms of the protective code, with the right approach entropy reduction, simplification of teamwork. All of these advantages derive from the three pillars – polymorphism, encapsulation, inheritance.

Also worth noting is the simplification of addressing issues related to the architecture of the application, because 80% of architectural problems were solved by computer-scientists in the last century and described in the literature devoted to the design pattern. Next, I will describe how to add like OOP syntax in C.

For instance data storage more convenient to take the basis of class C structure. Of course, you can use a byte buffer to create its own structure for the classes, methods, but why reinvent the wheel? After all, we already reinventing syntax.

These classes

An example of the data fields “class” GameObject:

struct GameObjectStruct {
    struct sp1_ss *gameObjectSprite;
    unsigned char *sprite_col;
    unsigned char x;
    unsigned char y;
    unsigned char referenceCount;
    unsigned char beforeHideX;
    unsigned char beforeHideY;
typedef struct GameObjectStruct GameObject;

We maintain our class as “GameObject.h” do #include “GameObject.h” in the right place and use.

Class methods

Take into service experience Objective-C language development, the signature method of the class will be from a function in the global osprey, the first argument will always transmitted data structure, method arguments go further. Next, an example of “the method” “class” GameObject:

void GameObject_hide(GameObject *gameObject) {
    gameObject->beforeHideX = gameObject->x;
    gameObject->beforeHideY = gameObject->y;
    gameObject->y = 200;

Method call is as follows:


Constructors and destructors are implemented in the same manner. It can be implemented as an allocator constructor and field initializers, but I prefer separate methods for that,

Working with memory

Manual memory management type using malloc and free macros wrapped in new and delete operators for compliance with C ++:

#define new(X) (X*)malloc(sizeof(X))
#define delete(X) free(X)

For objects that are used by multiple classes at once, realized semi-manual memory management based on reference counting, in the image of the old mechanism of Objective-C Runtime ARC:

void GameObject_retain(GameObject *gameObject) {

void GameObject_release(GameObject *gameObject) {

    if (gameObject->referenceCount < 1) { sp1_MoveSprAbs(gameObject->gameObjectSprite, &Renderer_fullScreenRect, NULL, 0, 34, 0, 0);

Thus, each class must declare the use of a common object using the retain, release the possession through release. In the modern version of ARC uses an automatic affixing call retain / release.

I sound!

Spectrum has a tweeter capable of reproducing 1-bit music, the composers of the time were able to play on it for up to 4 audio channels simultaneously. Spectrum 128k comprises a separate sound chip AY-3-8910, which can reproduce music tracker. To use the Tweeters in z88dk proposed library sound.h

What is to be learned

I was interested to read the Spectrum, to realize the game z88dk means, learn a lot of interesting things. I much remains to be explored, such as the assembler Z80, as it allows you to use the full power of Spectrum, the work of memory banks, working with the sound chip AY-3-8910. I hope to participate in the competition for next year!



Source Code



Binary Search

Suppose we need to find out whether the email address “ demensdeum@gmail.com ” belongs to the list of allowed email addresses for receiving letters.

We sort through the entire list from the first to the last element, checking whether the element is equal to the specified address – we implement the linear search algorithm. But will it be long or not?

To answer this question, use the “Temporary complexity of the algorithms”, “O” notation. In the worst case, the linear search operation time is equal to the nth number of array elements, we write this in the “O” notation – O (n). Next, you need to clarify that for any known algorithm, there are three performance indicators – execution time in the best, worst, and average cases. For example, the mail address “ demensdeum@gmail.com ” is in the first index of the array, then it will be found in the first step of the algorithm, it follows that the execution time in at best, O (1); and if at the end of the list, then this is the worst case – O (n)

But what about the details of the software implementation, the performance of the hardware, should they affect big O? Now exhale and imagine that the calculation of time complexity is calculated for some abstract ideal machine, in which there is only this algorithm and nothing more.


Ok, it turns out that the linear search is rather slow, let’s try using the binary search. To begin with, it should be clarified that we will not work with binary data, this name was given to this method because of the features of its work. Initially, we sort the array into lexicographically , then the algorithm takes the range of the entire array, gets the middle element of the range, compares it lexicographically , and depending on the result comparison decides what range to take to search for more – the top half of the current or lower. That is, at each step of the search, a decision is made of two possible ones – binary logic. This step is repeated until either the word is found or not found (the intersection of the lower and upper indices of the range will occur).

The performance of this algorithm is the best case when an element is immediately found in the middle of the O (1) array, the worst case is O (log n)


When implementing binary search, I came across not only the interesting problem of the lack of standardization of lexicographic comparison in programming language libraries, but I even found that there is no single standard for implementing localeCompare inside JavaScript . The ECMAScript standard allows different implementations of this function, because of this, when sorting using localeCompare, absolutely different results can be observed on different JavaScript engines.

Therefore, for the algorithm to work correctly, you must sort and use only the same lexicographic comparison algorithm in your work, otherwise nothing will work. So, for example, if you try to sort an array in Scala, and search using nodejs without realizing your own sorting / sorting of one implementation, then you will not expect anything other than disappointment in humanity.



Source Code



Facade Pattern

Facade belongs to structural design patterns. It provides a single interface that provides interaction between client and complex systems. GoF has a good example of the Facade – a compiler of programming languages ​​that provides different clients with different goals, the ability to build code through a single interface of the compiler facade.