Hash Table

Hash table data structure allows to realize an associative array (dictionary), with an average capacity of O (1) to insert, delete, search.

Below is an example of a simple implementation of a hash mapy on nodeJS:

How it works? Watching the hands:

  • Inside is an array of hash mapy
  • Inside the element of the array is a pointer to the first node of a linked list
  • Partitioning the memory to an array of pointers (e.g. 65,535 cells)
  • Implement the hash function, the input dictionary is the key, and at the outlet it can do just about anything, but in the end returns the array index

How does the record:

  • At the entrance there is a pair of key – value
  • The hash function returns the index on
  • Get node linked list from an array by index
  • Check whether it matches the key
  • If it matches, then replace the value
  • If it does not, then move on to the next node, until we find or do not find the node with the correct key.
  • If the node has not found, we create it at the end of a linked list

How does the search key:

  • At the entrance there is a pair of key – value
  • The hash function returns the index on
  • Get node linked list from an array by index
  • Check whether it matches the key
  • If it matches, the return value
  • If it does not, then move on to the next node, until we find or do not find the node with the correct key.

Why do we need a linked list in the array? Because of possible conflicts in the calculation of the hash function. In such a case several different key-value pairs will be located on the same index in the array, in such a case is carried out by extending the linked list with the search key necessary.

References

https://en.wikipedia.org/wiki/Hash_table
https://www.youtube.com/watch?v=wg8hZxMRwcw

Source Code

https://gitlab.com/demensdeum/datastructures

0

Resources access through NDK C++ Android

To work with resources in Android through ndk – C ++ there are several options:

  1. Use access to the resources of the apk file using AssetManager
  2. Download resources from the Internet and extract them in the application directory, used by standard methods C ++
  3. Combined method – to get access to the archive with resources apk through AssetManager, unpack them in the application directory, then use with standard C ++ techniques

Next, I will describe the combination of access methods using the game engine Flame Steel Engine.
When using SDL can facilitate access to the resources of the apk, library wraps the calls to AssetManager, offering a similar interface to the stdio (fopen, fread, fclose, etc.)


SDL_RWops *io = SDL_RWFromFile("files.fschest", "r");

After the file download from the apk to the buffer, you need to change the current working directory to the application directory, it is available to the application without additional permits. For this we use a wrapper on SDL:

 
chdir(SDL_AndroidGetInternalStoragePath());

Next, write down the file from the clipboard to the current working directory using fopen, fwrite, fclose. After the archive will be available in the directory for C ++, unpack it. Archives zip can extract a combination of two libraries – minizip and zlib, the first structure can work with files, the second decompresses the data.
For more control, simplicity, portability, I realized own archive format with zero compression called FSChest (Flame Steel Chest). This format supports the directory archiving files, and unpacking; Support folder hierarchy is missing, can work only with files.
Connecting the library header FSChest, unpack the archive:

 
#include "fschest.h" 
FSCHEST_extractChestToDirectory(archivePath, SDL_AndroidGetInternalStoragePath()); 

After unpacking, C / C ++ interfaces will be available files from the archive. So I did not have to rewrite all the work with the files in the engine, and add only unpacking files at startup.

References

https://developer.android.com/ndk/reference/group/asset

Source Code

https://gitlab.com/demensdeum/space-jaguar-action-rpg
https://gitlab.com/demensdeum/fschest

0

Stack Machine and RPN

Let’s say we need to implement a simple bytecode interpreter, which approach to the implementation of this task to choose?

Stack data structure provides an opportunity to implement a simple bytecode machine. Features and realization of machines stack described in numerous articles of Western and domestic Internet, just mention that the Java virtual machine is an example of a stack machine.

The principle of operation of the machine is simple, the input is a program containing data and opcodes (opcodes), using the stack manipulations performed realization of necessary operations. Consider the example of the program bytecode my stack machine:

 
пMVkcatS olleHП
 

At the output we get the string “Hello StackVM”. Stack machine reads the program from left to right, character by character by uploading data onto the stack, with the appearance of the opcode to symbol – performs implementation team using the stack.

An example of the implementation of the stack machine to nodejs:

Reverse polish notation (RPN)

Also, stacking machine is easy to use for the implementation of calculators, this is done using RPN (postfix notation).
An example of a conventional infix:
2*2+3*4

Converted into RPN:
22*34*+

To calculate postfix notation use a stack machine:
2 – at the top of the stack (stack 2)
2 – on top of the stack (Stack: 2.2)
* – get the top of the stack twice, multiply the result is sent to the top of the stack (stack of 4)
3 – on top of the stack (the stack 4, 3)
4 – on top of the stack (a stack of 4, 3, 4)
* – get the top of the stack twice, multiply the result is sent to the top of the stack (stack of 4, 12)
+ – get the top of the stack twice, add up the results, go to the top of the stack (stack 16)

As you can see – the result of operations 16 remains on the stack, it can be derived by implementing opcodes stack printing, for example:
п22*34*+П

П – print start opcode stack, n – opcode closure print stack and sending the final line in rendering.
For conversion from arithmetic operations in postfix infix used Edsger Dijkstra algorithm called “Shunting-yard algorithm”. An example implementation can be found above or in the project repository on the machine stack nodejs below.

References

https://tech.badoo.com/ru/article/579/interpretatory-bajt-kodov-svoimi-rukami/
https://ru.wikipedia.org/wiki/Обратная_польская_запись

Source Code

https://gitlab.com/demensdeum/stackvm/

0

Skeletal Animation (Part 2 – Node Hierarchy, Interpolation)

Algorithm goes on to describe skeletal animation, as its implementation in the game engine Flame Steel Engine.

Because the algorithm is the most complex of all that I implemented, in the notes on the process of development can occur errors. In the last article of this algorithm, I made a mistake, bone mass is passed to the shader for each mesh separately, rather than for the entire model.

Node Hierarchy

To work correctly you need to model the algorithm contained a link bones together (graph). Imagine a situation in which both played two animations – jumping and raising his right hand. Animation jump should raise the model on the Y axis, the animation show of hands should take this into account and to rise along with the model in a jump, otherwise the hand will remain on its own on the spot.

Describe the relationship of nodes in this case – the body contains a hand. In developing the algorithm will produce bone graph reading, all animations will be included with the correct connections. The memory model graph is stored separately from all animations, just to reflect the connectivity model bones.

Interpolation on CPU

In the last article, I described the principle of rendering skeletal animation – “transformation matrix are transferred from the CPU to the shader when rendering each frame.”

Rendering each frame is processed on the CPU, for each bone mesh engine receives a final transformation matrix by interpolation position, rotation, zoom. During the final interpolation bone matrix produced by extending the tree nodes for all active nodes animations, final matrix is ​​multiplied to the parent, is then sent to the rendering in the vertex shader.

For interpolation position and increasing use of the vector, quaternions are used to rotate because they are very easy interpolated (SLERP) in contrast to the Euler angles, as they are very easy to imagine a transformation matrix.

How to simplify the implementation of

To simplify debugging work vertex shader, I added the simulation work on the vertex shader CPU using FSGLOGLNEWAGERENDERER_CPU_BASED_VERTEX_MODS_ENABLED macro. At NVIDIA graphics cards manufacturer has a tool for debugging the shader code Nsight, perhaps she, too, can simplify the development of complex algorithms vertex / pixel shaders, however, test the functionality I have not had the opportunity, enough simulation on the CPU.

In the next article I plan to describe the mixing of multiple animations, supplement to fill the remaining gaps.

Sources

https://www.youtube.com/watch?v=f3Cr8Yx3GGA

0

Add JavaScript Support For C++

In this article I will describe a method of adding support for JavaScript scripts in C ++ application using the Tiny-JS library.

Tiny-JS is a library for embedding in C ++, provides the execution of JavaScript code, with support for bindings (the ability to call C ++ code from a script)

At first I wanted to use the popular ChaiScript library, Duktape or include the Lua, but due to dependencies and possible difficulties in porting to different platforms, it was decided to find a simple, minimal but powerful MIT JS lib, meets these criteria Tiny-JS. The only disadvantage of this library in the absence of support/development from the developer, but it is fairly simple code that allows you to take the support, if required.

Download Tiny-JS from the repository:
https://github.com/gfwilliams/tiny-js

Next, add Tiny-JS headers:

 
#include "tiny-js/TinyJS.h" 
#include "tiny-js/TinyJS_Functions.h" 

Add .cpp TinyJS files to build stage, then you can start writing load and run scripts.

Lib usage examples available in the repository:
https://github.com/gfwilliams/tiny-js/blob/master/Script.cpp
https://github.com/gfwilliams/tiny-js/blob/wiki/CodeExamples.md

An example of a class handler implementation can be found in the project SpaceJaguar:
https://gitlab.com/demensdeum/space-jaguar-action-rpg/-/blob/master/project/src/Controllers/SpaceJaguarScriptController/SpaceJaguarScriptController.h
https://gitlab.com/demensdeum/space-jaguar-action-rpg/-/blob/master/project/src/Controllers/SpaceJaguarScriptController/SpaceJaguarScriptController.cpp

Game script example integrated into application:
https://gitlab.com/demensdeum/space-jaguar-action-rpg/-/blob/master/project/resources/com.demensdeum.spacejaguaractionrpg.scripts.sceneController.js

References

https://github.com/gfwilliams/tiny-js
https://github.com/dbohdan/embedded-scripting-languages
https://github.com/AlexKotik/embeddable-scripting-languages

0

Linux to iOS C++ Cross Compile

In this article I will describe the build process of C++ SDL iOS app on Linux, resign ipa file without a paid subscription to Apple Developer Program and installation on a clean device (iPad) via macOS without Jailbreak.

First, install the build toolchain in Linux:
https://github.com/tpoechtrager/cctools-port

Toolchain needs to be downloaded from the repository, follow instructions on the site of Godot Engine to complete the installation:
https://docs.godotengine.org/ru/latest/development/compiling/cross-compiling_for_ios_on_linux.html

At this point you need to download Xcode dmg and copy ios sdk to build cctools-port. This stage is easier to pass on MacOS, simply copy of Xcode installed sdk necessary files. After successful build, the terminal will show a path to crosscompiler bin directory.

You can then proceed to the build of SDL applications for iOS. Open cmake and add the necessary changes for C ++ build code:


SET(CMAKE_SYSTEM_NAME Darwin)
SET(CMAKE_C_COMPILER arm-apple-darwin11-clang)
SET(CMAKE_CXX_COMPILER arm-apple-darwin11-clang++)
SET(CMAKE_LINKER arm-apple-darwin11-ld)

Now you can build using cmake and make, but do not forget to register to the $PATH of crosscompiler bin directory:



PATH=$PATH:~/Sources/cctools-port/usage_examples/ios_toolchain/target/bin

For correct linking with frameworks and SDL add them to cmake, Space Jaguar games depending for example:



target_link_libraries(
${FSEGT_PROJECT_NAME}
${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libclang_rt.ios.a
${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libSDL2.a
${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libSDL2_mixer.a
${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libSDL2_image.a
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreServices.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/ImageIO.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/Metal.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/AVFoundation.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/GameController.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreMotion.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreGraphics.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/AudioToolbox.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreAudio.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/QuartzCore.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/OpenGLES.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/UIKit.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/Foundation.framework"
)

In my case, SDL library, SDL_Image, SDL_mixer compiled in Xcode on macOS advance for static linking; Frameworks copied from Xcode. Also added libclang_rt.ios.a library, which includes specific runtime iOS calls, e.g. isOSVersionAtLeast. Enabled macros for working with OpenGL ES, disables unsupported features in the mobile platforms, similar to Android.

After the resolving build problems, you must get a binary compiled for the arm. Next, I will describe binary installation and run on the device without Jailbreak.

On macOS make Xcode installation, register on Apple’s website, without having to pay for the development of the program. Add account in Xcode -> Preferences -> Accounts, create an empty application and build for a real device. During assembly, device will be added to a free developer account. After building and running, you need to make an archive of the build, for this select Generic iOS Device and Product -> Archive. By the end of the archive build, copy files called embedded.mobileprovision, PkgInfo. From the build log on the device, find the line codesign with the correct key signature, the path to the file with the extension of entitlements app.xcent, copy it.

Copy the .app from the archive, replace binary in the archive created by cross-compiler in Linux (eg SpaceJaguar.app/SpaceJaguar), further adding to the .app necessary resources to check the safety and PkgInfo embedded.mobileprovision in the .app file from the archive, copy again if needed. Resign .app using codesign command – codesign requires the input argument of the key for the sign, the path to the entitlements file (can be renamed with the extension .plist)

After resign create Payload folder, move to the folder with the .app extension, create a zip file with the Payload directory, rename the file with the extension .ipa. After that, in Xcode, open the list of devices and Drag’n’Drop ipa in the list of device applications; Installation via Apple Configurator 2 for this process does not work. If resign made correctly, a new application is installed with correct binary on iOS device (e.g. iPad) with 7 day certificate for testing period that is sufficient.

References

https://github.com/tpoechtrager/cctools-port
https://docs.godotengine.org/ru/latest/development/compiling/cross-compiling_for_ios_on_linux.html
https://jonnyzzz.com/blog/2018/06/13/link-error-3/
https://stackoverflow.com/questions/6896029/re-sign-ipa-iphone
https://developer.apple.com/library/archive/documentation/Security/Conceptual/CodeSigningGuide/Procedures/Procedures.html

0

Fixing slow HDD Windows 10

This article is dedicated to all die hard hdd users.

Original (Mae Mu)

1.5 years of using HP Pavilion laptop HDD dualboot (Windows 10) and SSD (Ubuntu) I began to notice a very long loading of applications, a common interface unresponsive, hangs on simple operations in Windows 10. The problem has been minimized to the extent that the use of a laptop has become possible again. Next, I will describe the action that I have taken to correct the problem.

Diagnostics

For the study to be eliminated mystification of any order, first determine the root cause damage hard drives. What can go wrong when dealing with a hard drive? Problems can occur in the physical layer electronics and logical data software.
By electronics problems include such things as PC / Laptop power problems; Wear a hard disk component failure in the circuits and chips internal drive components, software, firmware error, the consequences of hit shock / disc falls, or similar problems with other devices that affect its operation.
Hard disk wear and tear is considered critical time of occurrence of the amount of such a large number of bad sectors (bad block) in which the further operation of the disc is not possible. These blocks are blocked by the hard drive firmware, the data is transferred to other sectors automatically and should not affect the disk performance to a certain critical point.
The problems include programming logic error in the file system due to incorrect operation of the application, a user action: off on the hot device, the completion of the recording process without properly stopping the application, errors in drivers, operating system services.
Not having a specialized electronic diagnostic tools, we only need to check the correct software level, already in the process of electronics may show problems that are usually eliminated by block repair (replacement of components / chips); Next, consider the software methods of diagnosis using diagnostic tools. It is worth noting that all utilities must be run on a system with the highest priority, as other applications may interfere with measurements of performance, lock the drive read / write, which will lead to incorrect results of diagnosis.

SMART

S.M.A.R.T. monitoring service for storage devices -. HDD, SDD, eMMC etc. It allows to evaluate the wear devices, view the number of bad blocks, based on the data to take further action. View SMART can be used in various applications for working with disks, I prefer to use tools from the manufacturer. For your hard drive Seagate SeaTools utility I used, output status as a GOOD for him, that is, drive firmware finds that all is well.

Manufacturer Tools

Disc producer utility provides tests to check his work. SeaTools has several types of tests, you can use them all to localize the problem. Quick and simple tests can not detect any problems, so I prefer for many tests. In my case only on the Long Test errors were found.

Slowride

To check the correctness of the reading, finding slow or dead blocks, I wrote an application slowride. It works on a very simple principle – opens a handle to a block device, with user-defined settings produces read data of the entire device, with measurements of time, slow output blocks. The program stops at the first error, would then have to go to more serious utility to remove the data as a simple data disc methods is not possible to read.
In my case, reading the entire disk it was carried out properly, with little drawdown speed – 90MB / s (5400rpm) in one second, in some areas of the disc. From which one could conclude that I am dealing with a software problem.

Acoustic Analysis

This method does not apply to software methods of diagnosis, however, it is important enough to fix the problem. For example, when the operating part supply unit, a hard disk may Freeze / hang emitting a loud click.
In my case, when dealing with the disc in Windows 10, I heard familiar to all owners of HDD, loud buzz run around the drive head when you try to do anything in the operating system, but the sound was almost constant, it made me think about too much disk fragmentation, disk reloading background service.

Fixing

Electronics problems during software diagnostics have not been found, chunked read the entire disc was completed correctly, but showed SeaTools errors Long Test verification.

Manufacturer Tools

Manufacturer disk diagnostic software in addition provides the error correction procedure. The SeaTools is responsible for this Fix All button, then agreed to accept the potential loss of data, it will start the process of correction. I did my case, this fix? No, the drive continued to work as loudly and slowly, but the Long Test error is no longer shown.

CHKDSK

CHKSDK is Microsoft’s tool to eliminate programming errors for Windows file systems. Over time, these errors accumulate on the disc and can greatly interfere with the work, including the result in the inability to read / write any data at all. Instructions on the use of tools you can find on the Microsoft site, I recommend to use all possible flags for error correction (at the time of this writing, is / r / b / f); Need to run a check with the administrator via the Windows terminal (cmd), for the system partition it will be held on the system boots, it may take a very long time, in my case took 12 hours.
I did this fix in my case? Not.

Disk Defragmenter

Working with the disk data blocks is carried out, large files typically stored in multiple blocks / fragments. Over time, a lot of deleted files create empty blocks that are not there, because of this when writing files to fill these voids, and disk head has to physically travel long distances. This problem is called fragmentation, and with her face only a user’s hard drive. At the time several fixes fragmentation of my hard drive was 41%, visually it looks like this:

That is bad. See fragmentation, to defragment, you can use Defragger utility or built defragmenter. You can also turn the service on “Optimize drives” in Windows 10, put down a defragmentation schedule in the control panel.Defragment only need the HDD, discs include undesirable for SSDAs this will lead to accelerated wear of the disc, probably for this reason that defragmentation is disabled by default.

Also known is an alternative embodiment of defragmentation – transferring data to another disk, the formatting of the disk, and copying the data back. In this case, data will be recorded on a completely empty sector, while maintaining the correct logical structure to run the system. This reset option is fraught with problems potentially critical metadata that may not move during normal copying.

Disable Services

With utility Mark Russinovich Process Monitor you can track the processes that load the hard drive their business, just include the column IO Write / Read. After the study of this column, I disabled the service Xbox Game Bar, a well-known service background acceleration Superfetch programs under the new name SysMain, through the panel of the control panel services. Superfetch should constantly analyze the application used by the user, and accelerate their launch using caching in memory, in my case it led to a background downloading the entire disc and the inability to work.

Clean the Drive

I also removed the old app, unwanted files, thus freeing up the sector to correct the fragmentation, simplifying the job of the operating system, reducing the number of useless, heavy services and programs.

Total

What helped the most? A marked difference in performance was achieved after a disk defrag, spontaneous hang persists by disabling services Xbox and Superfetch. It would not have these problems if I used the SSD? Problems with slow performance when fragmentation would definitely would not have been a problem with the services had to remove in any case, and software errors do not depend on the type of drive. In the near future I plan to complete the migration to the SSD, but for now, “Long live the pancakes, pancakes forever!”

References

http://www.outsidethebox.ms/why-windows-8-defragments-your-ssd-and-how-you-can-avoid-this/
https://channel9.msdn.com/Shows/The-Defrag-Show
https://www.seagate.com/ru/ru/support/downloads/seatools/
https://www.ccleaner.com/defraggler/download
https://docs.microsoft.com/en-us/windows-server/administration/windows-commands/chkdsk
https://gitlab.com/demensdeum/slowride/

1+

Backend server C++ FCGI

Quick note about how I wrote the backend for 3D Cube Art Project editor, the server needs to store and display the user work from web version, giving them a short URL on the save button. At first I wanted to use the Swift/PHP/Ruby/JS or some similar modern language for the backend, but looking at the characteristics of my VPS was decided to write a server on the C/C ++.
First you need to install on the server and libfcgi fcgi support module for your web server, for example Ubuntu and Apache:


sudo apt install libfcgi libapache2-mod-fcgid

Next, configure the module in the config file:

FcgidMaxProcessesPerClass – the maximum number of processes in the class, I put 1 process because it does not count on a big load.
AddHandler fcgid-script .fcgi – file extension which should start fcgi module.
Add in the config directory which will run cgi applications:

Next, write an application to the C/C ++ with fcgi support, collect it, and it is copied to the folder /var/www/html/cgi-bin.
Examples code and build script:
https://gitlab.com/demensdeum/cube-art-project-server/-/blob/master/src/cubeArtProjectServer.cpp
https://gitlab.com/demensdeum/cube-art-project-server/-/blob/master/src/build.sh
Then you need to restart your web server:


systemctl restart apache2

Next, put down the necessary rights for the execution of cgi-bin folder via chmod.
After that, your cgi program should work through the browser to the link, for example Cube Art Project Server:
http://192.243.103.70/cgi-bin/cubeArtProject/cubeArtProjectServer.fcgi
If something does not work, then see the web server logs, or connect the debugger to a running process, the debugging process should not differ from the usual process of debugging the client application.

References

https://habr.com/ru/post/154187/
http://chriswu.me/blog/writing-hello-world-in-fcgi-with-c-plus-plus/

Source Code

https://gitlab.com/demensdeum/cube-art-project-server

0