A software engineer's blog

About this Blog

Welcome to my blog! My name is Nikos and I am an engineer. In this blog I will post algorithms and software related stuff that I find interesting or I had a hard time to find online.

Monday, October 3, 2022

FreeBasic implementation of the Brute Force Algorithm



This is my single threaded implementation of the Brute Force algorithm for FreeBasic. The following algorithm uses the StringUtils.Join method of the Kiwi framework. Kiwi can be found on GitHub at https://github.com/nsiatras/kiwi

I transferred this algorithm from Java. The Java algorithm can be found here

/'
    Brute Force Algorithm for FreeBasic 

    Author: Nikos Siatras
    https://github.com/nsiatras
'/

#include once "kiwi\kiwi.bi" ' Kiwi framework is used only for the StringUtils.Join method

Dim Shared fCharList(...) as String * 1  = {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"}
Dim Shared fCharactersListLength as Integer = ubound(fCharList)

/'
	The OnBruteForceWordGenerated sub is called everytime a new word
	is generated from the BruteForce algorithm.
	For this example I choose only to write to word on the screen
'/
Sub OnBruteForceWordGenerated(word as String)
	print word
End Sub

/'
	Change characters to each other and generate BruteForce words
'/
Sub ChangeCharacter(position as Integer, sb(any) as String, wordLength as Integer)

	Dim i as Integer
	Dim x as Integer
	Dim generatedWord as String
	
	for i = 0 to fCharactersListLength
		sb(position) = fCharList(i)
		if position = wordLength - 1 then
			generatedWord = StringUtils.Join(sb(), "")
			OnBruteForceWordGenerated(generatedWord)
		else
		 ChangeCharacter(position + 1, sb(), wordLength)
		end if
	next i	
		
End Sub

/'
	Start Brute Force Generation
	@wordLength is the word's length (how many characters a word can have)
'/
Sub StartBruteForce(wordLength as Integer)

	Dim stringBuilder(wordLength) as String 
	Dim currentChar as String = fCharList(0)
	
	for i as Integer = 1 to wordLength
		 stringBuilder(i-1) = currentChar
	next i 
	
    ChangeCharacter(0, stringBuilder(), wordLength)

End Sub


' Begin Brute Force from 1 to 18 characters
for i as Integer = 1 to 18
	StartBruteForce(i)
next i

Friday, September 9, 2022

Split String Algorithm for FreeBasic


I often use string expressions to pass data between web services, microcontrollers and desktop Applications and the Split algorithm is something I often use to parse them. 

Unfortunately, this algorithm is missing from the FreeBasic programming language, so I decided to publish my implementation of the Split string algorithm.

Hope you find it useful !

/'
    Split Text Algorithm v2.1 for FreeBasic 

    Author: Nikos Siatras
    https://github.com/nsiatras
'/

' Splits the textToSplit string into multiple Strings, given the delimiter 
' that separates them and adds them to the result array
Sub Split(byref stringToSplit as const String, byref delimeter as const String, result() as String)
	
    Dim lengthOfDelimeter as Integer = len(delimeter)
    Dim indexOfDelimeter as Integer = 1
    Dim delimeterCount as Integer = 0
    Dim offset as Integer
    Dim lastDelimeterIndex as Integer
    
    ' Find how many times the delimeter exists in the stringToSplit
    Do
	indexOfDelimeter = InStr(indexOfDelimeter, stringToSplit, delimeter)
	if indexOfDelimeter >0 then
	    delimeterCount += 1
	    indexOfDelimeter = indexOfDelimeter + lengthOfDelimeter
	else
	    Exit Do ' Exit Do Loop
	endif
    Loop
    
    ' The delimeter wasn't found in the string
    if delimeterCount = 0 then
	ReDim result(0)
	result(0) = stringToSplit
	return
    endif
    
    ' Resize the result array according to delimeter size
    ReDim result(delimeterCount)

    ' Serial search inside the stringToSplit in order to find the parts 
    ' separated by the delimeter and push them to the result() array
    delimeterCount = 0
    offset = 1
    indexOfDelimeter = 1 
    Do
	indexOfDelimeter = InStr(offset, stringToSplit, delimeter)
	if indexOfDelimeter > 0 then
		result(delimeterCount) = Mid(stringToSplit, offset, indexOfDelimeter - offset)
	else
	    if lastDelimeterIndex < len (stringToSplit) then
                result(delimeterCount) = Mid(stringToSplit, lastDelimeterIndex + lengthOfDelimeter)
	    endif
		
            return 'Exit the Do Loop and return!
	endif
	lastDelimeterIndex = indexOfDelimeter
        offset = indexOfDelimeter + lengthOfDelimeter
	delimeterCount += 1
    Loop
    
End Sub

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' Test Code
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Dim fStringToSplit as String
Dim fSplitParts () as String, tmp as String
Dim i as Integer

fStringToSplit = ",Welcome,to,Free,Basic,!"
Split(fStringToSplit,",",fSplitParts())
     
' Print the fSplitParts
for i = 0 to ubound(fSplitParts)
    print "Part #" & i & " " & fSplitParts(i)
next

print ""

fStringToSplit = "Now<>you<>know<>how<>to<>split<>strings<>!"
Split(fStringToSplit,"<>",fSplitParts())
     
' Print the fSplitParts
for i = 0 to ubound(fSplitParts)
    print "Part #" & i & " " & fSplitParts(i)
next

Wednesday, September 7, 2022

FreePascal implementation of the Brute Force Algorithm



This is my single threaded implementation of the Brute Force algorithm for FreePascal / Delphi. I transferred this algorithm from Java. The Java algorithm can be found here 

program Pascal_BruteForce;

(*
  Brute Force Algorithm for FreePascal

  Author: Nikos Siatras
  https://github.com/nsiatras
*)

uses
  SysUtils;

// Global Variables
var
  fCharactersStr: string;
  fCharList: TStringArray;
  fCharactersListLength: integer;

{*
  The OnBruteForceWordGenerated procedure is called everytime a new word
  is generated from the BruteForce algorithm
  For this example I choose only to write to word on the screen
*}
  procedure OnBruteForceWordGenerated(word: string);

  begin
    WriteLn(word);
  end;

(*
  Change characters to each other and generate BruteForce words :)
*)
  procedure ChangeCharacter(pos: integer; sb: array of string; wordLength: integer);
  var
    i, x: integer;
    generatedWord: string;
  begin

    for i := 0 to fCharactersListLength - 1 do
    begin

      sb[pos] := fCharList[i];

      if pos = wordLength - 1 then
      begin
        // Pass the BruteForce generated word to the OnBruteForceWordGenerated
        // procedure
        generatedWord := string.Join('', sb);
        OnBruteForceWordGenerated(generatedWord);
      end

      else
      begin
        ChangeCharacter(pos + 1, sb, wordLength);
      end;

    end;

  end;

(*
  Start Brute Force Generation
  @wordLength is the word's length (how many characters a word can have)
*)
  procedure StartBruteForce(wordLength: integer);
  var
    stringBuilder: array of string;
    currentChar: string;
    i: integer;
  begin

    SetLength(stringBuilder, wordLength);
    currentChar := fCharList[0];

    for i := 1 to wordLength do
    begin
      stringBuilder[i - 1] := currentChar;
    end;

    ChangeCharacter(0, stringBuilder, wordLength);

  end;


  // Main Program
var
  i: integer;

begin

  //Initialize fCharList array
  //For this example I will use all lowercase english alphabet characters.
  fCharactersStr := 'a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z';
  fCharList := fCharactersStr.split(',');

  //Find the length of the fCharList array
  fCharactersListLength := Length(fCharList);

  // Generate all words with total length from 1 to 16 characters
  // This will generate all words from 'a' to 'zzzzzzzzzzzzzzzz'
  for i := 1 to 16 do
  begin
    StartBruteForce(i);
  end;

end.

Tuesday, September 6, 2022

A performance comparison between various programming languages


The first programming language I ever write code was Microsoft's QBasic. After QBasic I moved to Visual Basic 6.0 and some Pascal and when I grew up and I had to work my life I wrote in C#, Java, ASP, ASP .NET, ActionScript and later PHP. The last decade I write in Java, PHP, some JavaScript and some C for the Arduino framework on a daily basis.

I also got involved with Python but I soon realized that Python is a horrible programming language. It has horrible syntax and its horrible performance makes you often wonder if it is worth having a computer to do tasks for you. Python also makes me wonder why the programming community stopped using Basic and Pascal after 90s, these 2 languages have an amazing performance similar to C and where much easier to read than Python. Anyway...  #python_is_horrible and at the end of the day we all realize that.

Yesterday I decided to do a performance test for several programming languages. I decided to write a matrix multiplication algorithm in Java and then transfer this algorithm to other programming languages I know. I also uploaded all code to a new GitHub repository (https://github.com/nsiatras/programming-languages-benchmark). 

The matrices of my "matrix multiplication benchmark" are of size 1024x1024 (1.073.741.824 multiplication and addition operations) and I populated them with random values between 0.0 and 1.0. Each experiment is run 5 times and the total time it took to complete is displayed as a result.

The results

LanguageElapsed Time(Seconds)Notes
FreePascal21.0020Free Pascal Compiler (FPC) 3.2.2
Java22.1462GraalVM 22.2 Community Edition
(OpenJDK version 17.0.4)
FreeBasic25.8051FreeBASIC 1.09.0
C28.0330gcc.exe (x86_64-posix-seh-rev0,
Built by MinGW-W64 project) 8.1.0
(No optimization)
C#56.1140.NET Framework 6.0
Python4426.7331Python 3.10.7

I wasn't shocked or even surprised by the results. Ok... I was a bit surprised seen FreePascal in the first row instead of C, but I want to tell you that to compile the C code I used GCC without optimization.

FreePascal is 1.05 times faster than Java, Java is 1.26 times faster than C and Python proves that pencil and paper is way faster to perform calculations.

The reason Java can compete with C, FreePascal, FreeBasic and other compiled language that converts the code directly into machine language is the Java JIT (Just-In-Time) compiler. JIT compiler optimizes performance of programs running on the JVM (Java Virtual Machine) through unique approaches to code analysis and optimization. JIT is like a very talented software engineer optimizing your code.

For C# I have to say I was expecting more. I was expecting to be close to Java or even beat Java but C# was 2.53 slower this time. This has to do with the way .NET framework handles floating point values.

Python is an interpreted language and like any other interpreted languages (PHP!!!) is horribly slow. Interpreting code is many times slower than running the compiled code because the interpreter must analyze each statement in the program each time it is executed and then perform the desired action.

Sunday, September 4, 2022

Pure Java implementation of MD5 Algorithm


The following Java algorithm generates MD5 hashes from String, Byte array and File.

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

/**
 *
 * @author Nikos Siatras
 */
public class MD5
{

    public MD5()
    {

    }

    /**
     * Return the MD5 string representation of the given string
     *
     * @param str is the string to get the MD5
     * @return
     * @throws NoSuchAlgorithmException
     */
    public String getMD5FromString(String str) throws NoSuchAlgorithmException
    {
        MessageDigest md = MessageDigest.getInstance("MD5");
        byte[] array = md.digest(str.getBytes());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < array.length; ++i)
        {
            sb.append(Integer.toHexString((array[i] & 0xFF) | 0x100).substring(1, 3));
        }
        return sb.toString().toUpperCase();
    }

    /**
     * Return the MD5 string representation of the given byte array
     *
     * @param bytes is the byte array to get the MD5
     * @return
     * @throws NoSuchAlgorithmException
     */
    public String getMD5FromByteArray(byte[] bytes) throws NoSuchAlgorithmException
    {
        MessageDigest md = MessageDigest.getInstance("MD5");
        byte[] array = md.digest(bytes);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < array.length; ++i)
        {
            sb.append(Integer.toHexString((array[i] & 0xFF) | 0x100).substring(1, 3));
        }
        return sb.toString().toUpperCase();
    }

    /**
     * Return the MD5 string representation of the given file
     *
     * @param file is the file to get the MD5
     * @return
     * @throws NoSuchAlgorithmException
     * @throws IOException
     */
    public String getMD5FromFile(File file) throws NoSuchAlgorithmException, IOException
    {
        MessageDigest md = MessageDigest.getInstance("MD5"); // SHA or MD5
        String hash = "";

        byte[] data = new byte[(int) file.length()];
        FileInputStream fis = new FileInputStream(file);
        fis.read(data);
        fis.close();

        // Reads it all at one go. Might be better to chunk it.
        md.update(data);

        byte[] digest = md.digest();

        for (int i = 0; i < digest.length; i++)
        {
            String hex = Integer.toHexString(digest[i]);
            if (hex.length() == 1)
            {
                hex = "0" + hex;
            }
            hex = hex.substring(hex.length() - 2);
            hash += hex;
        }

        return hash.toUpperCase();
    }
}

Java implementation of the Brute Force Algorithm



This is my single threaded implementation of the Brute Force algorithm for Java. I build this algorithm purely for scientific purposes.

A brief code explanation:

The fCharList array holds the characters involved in the algorithm. You can add or remove characters according to your needs.

The StartBruteForce method starts a brute force word generation. The length parameter of this method determins how many characters a word can have.

The OnBruteForceWordGenerated  is called for every Brute-Force generated word.

Example #1: For a length of 4 the StartBruteForce method  will generate the following words "aaaa","aaab","aaac".....,"zzzz"

Example #2: For a length of 8 the StartBruteForce method  will generate the following words "aaaaaaaa","aaaaaaab","aaaaaaac".....,"zzzzzzzz"

/**
 *
 * @author Nikos Siatras
 */
public class BruteForce
{

    private static final char[] fCharList =
    {
        'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
    };

    public static void main(String[] args)
    {
        for (int i = 1; i < 17; i++)
        {
            StartBruteForce(i);
        }
    }

    /**
     * This method is called every time a new word is generated
     *
     * @param word is the brute force generated word
     */
    private static void OnBruteForceWordGenerated(String word)
    {
        System.out.println(word);
    }

    /**
     * Start a new Brute Force
     *
     * @param length is the words length (how many characters a word can have)
     */
    private static void StartBruteForce(int length)
    {
        StringBuffer sb = new StringBuffer(length);
        char currentChar = fCharList[0];

        for (int i = 1; i <= length; i++)
        {
            sb.append(currentChar);
        }

        ChangeCharacters(0, sb, length);
    }

    private static StringBuffer ChangeCharacters(int pos, StringBuffer sb, int length)
    {
        for (int i = 0; i <= fCharList.length - 1; i++)
        {
            sb.setCharAt(pos, fCharList[i]);
            if (pos == length - 1)
            {
                // Write the Brute Force generated word.
                OnBruteForceWordGenerated(sb.toString());
            }
            else
            {
                ChangeCharacters(pos + 1, sb, length);
            }
        }

        return sb;
    }
}

Wednesday, October 19, 2016

Java: Generate Bitcoin & Ethereum Target from Difficulty


The other day I was making a small CPU miner for Ethereum using Java. I decided to implement the stratum protocol and I came to the following... difficulty.

Stratum does not send the target directly to the miner as the Getwork protocol does. Stratum sends a double data type that holds the difficulty and the miner have to generate the target from that.

Stratum example message of mining difficulty:

{ 
  "id": null, 
  "method": "mining.set_difficulty", 
  "params": [
    0.5
  ]
}\n

The Java Solution!

As I read online the conversion between difficulty and target is done the same way as with Bitcoin but it is not very clear how can someone do that so... I decided to post my code and maybe make the life of others a bit easier.

The code is written in simple Java and does not need any external libraries.

    public static void main(String[] args)
    {
        String target = GetTargetFromDifficulty(1);
        System.out.println("Target for difficulty 1 is " + target);
    }

    private static String GetTargetFromDifficulty(double difficulty)
    {
        // Note: difficulty of 1 is transformed to target being in HEX:
        // 00000000ffff0000000000000000000000000000000000000000000000000000

        long m;
        int k;
        byte[] target = new byte[8 * 4];
        for (k = 6; k > 0 && difficulty > 1.0; k--)
        {
            difficulty /= 4294967296.0;
        }
        m = (long) (4294901760.0 / difficulty);
        if (m == 0 && k == 6)
        {
            Arrays.fill(target, (byte) 0xff);
        }
        else
        {
            Arrays.fill(target, (byte) 0);
            for (int i = 0; i < 8; i++)
            {
                target[k * 4 + i] = (byte) ((m >> (i * 8)) & 0xff);
            }
        }

        String tmp = toHexString(target);
        String reverse = new StringBuffer(tmp).reverse().toString();
        return reverse;
    }

    private static String toHexString(byte[] b)
    {
        StringBuilder sb = new StringBuilder(80);
        for (int i = 0; i < b.length; i++)
        {
            sb.append(Integer.toString((b[i] & 0xff) + 0x100, 16).substring(1));
        }
        return sb.toString();
    }