Sorting Algorithms - Merge Sort

Now merge sort is based on the divide and conquer concept. Idea is to divide the problem into smaller sub problems and solve those sub problems. Once you are able to solve those sub problems, join them together to get the solution for the bigger problem. Now in case of merge sort we divide the problem into exactly two halves. Take that halves and again divide them into two halves again. Like this we will go until exactly one element is left in each of the sub problems. Now we start merging them by comparing each elements. The one having smaller element will be placed first and bigger one will be placed after that. Below diagram will help you to understand it.

First image is of division work. It shows how the problem is divided into smaller sub problem.

Once we are successful in dividing the problem into smaller sub problem now its time to conquer it that is to merge them. Below image shows how it will be merged.

For division purpose in coding we are using recursive function. Recursive functions are those which will call itself again and again with modified parameters until a predefined goal is met. Below is the code snippet for this

int MergeSortAlgo(int* pIntArray, int nStart, int nSize)
{
int nReturnValue = 0;
int nMid = -1;

nMid = nSize / 2;
if (nMid > 0)
{
//This is divide part of the algorithm. That is we are dividing the array into smaller sub arrays.
MergeSortAlgo(pIntArray, nStart, nMid);
MergeSortAlgo(pIntArray, nStart + nMid, nSize - nMid);
//This is conquering part of the algorithm. Here once after division of the array we are trying to merge them into one.
MergeArray(pIntArray, nStart, nSize);
}

return nReturnValue;
}

As you can see MergeSortAlgo is called repeatedly by itself with different parameters. It is dividing the problem into two which is done in step nSize/2.

Once all division is done it is going further to Merge those divided sub problems. Below is the code which is doing exactly that

int MergeArray(int *pIntArray, int nStart, int nSize)
{
int nReturnValue = 0;
int nMid = nSize / 2;
int nFirstStart = nStart;
int nSecondStart = nStart + nMid;
int nFirstEnd = nStart + nMid - 1;
int nSecondEnd = nStart + nSize - 1;

int i = nFirstStart, j = nSecondStart, k = 0;

int* pTempArray = 0;
pTempArray = (int*)malloc(nSize*sizeof(int));
if (pTempArray == 0)
{
//Error Dynamic memory not allocated.
return ERR_DYNAMICMEMNOTALLOC;
}
else
{
while (k < nSize && (i <= nFirstEnd && j <= nSecondEnd))
{
if (pIntArray[i] < pIntArray[j])
{
pTempArray[k++] = pIntArray[i++];
}
else
{
pTempArray[k++] = pIntArray[j++];
}
}

while (i <= nFirstEnd)
pTempArray[k++] = pIntArray[i++];

while (j <= nSecondEnd)
pTempArray[k++] = pIntArray[j++];

i = 0, j = 0, k = 0;

for (k = 0; k < nSize; k++)
pIntArray[nStart++] = pTempArray[k];

free(pTempArray);

}

return nReturnValue;
}

Nothing special here. First I have allocated a temporory space whose size is sum of arrays of sub problems. Then I comparing one element of Sub problem1 and one element of Sub problem2. Whichever is smaller will be placed in the temparory array. This is repeated for every elements.

Okay the order of growth of merge sort is Theta(nlogn) log base is 2. How do we get this well wait for my post on Masters Theorem.

Code is present in location https://github.com/harsha-kadekar/LibraryOfAlgorithms.git
I am learning from "Introduction to Algorithms" book 3rd edition. Authors - Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford  Stein.

Sorting Algorithms - Insertion Sort

Okay I know I am again writing one more blog for insertion sort. The first one I had written when I was trying to develop a assembly language library containing all the sorting algorithm functions. Now I am creating a library in C language which will have many sorting algorithm functions and much more other functions. So the first one I tried was Insertion Sort. My primary book reference is "Introduction to Algorithms - 3rd Edition: Authors - Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein". 

The way I wrote this function is first I read the concept of insertion sort from the above mentioned book. Then I tried to create a C function based on the read concept. Once done I read the actual pseudo code given in the book and if it is much better I rewrote it in my library. So my version of insertion sort was different than in the book and 99% book version will be better and it happened in my case as well so I changed my logic to match with the book.

Imagine that there is a room, and inside which there are exactly 100 students and each student has class ID. This class ID is any number from 1 to 100. Now you are asked to arrange those students in a line in front of class building in the ascending order of their class IDs. So how do you do it? You will ask students to come out one at a time. First student will stand at the front of line. Now second student comes out. You will check his class ID and compare with the already stood students class ID. If his class ID is smaller than you will ask the earlier student to go back one position and new student will stand infront now. If the new students class ID is greater than the already standing student then you will ask the new student to stand at the next position after the already standing student. This process will repeat until all the students have stood in the line. This is nothing but Insertion sort. You will take a number and try to find the position of this number in the already sorted list of number. Once you found the position you insert that number to that position in the sorted list of number.

My initial code was like this:

//Take each number and place it in correct position

for (int i = 1; i <= nSize; i++)

{

int nKey = arNumbers[i];

int nPos = i;

//Find the position of the new number to be placed

for (int j = 0; j < i; j++)

{

if (arNumbers[j] > nKey)

{

nPos = j;

break;

}

}

if (nPos != i)

{

//Move all the numbers to the right to make the position for new number

for (int k = i - 1; k > nPos; k--)

{

arNumbers[k + 1] = arNumbers[k];

}

arNumbers[nPos] = nKey;

}

}

The above program works fine. But just that I have one extra for loop. I have one FOR loop for finding position to insert key element and one FOR loop to insert the key in the found position. But rather these two loops can be merged into to single loop and we can do both tasks together. Now below code is based on the book and in that loop is merged.

for (int i = 1; i < nSize; i++)

{

int nKey = arNumbers[i];

int j = i - 1;

while (j >= 0)

{

if (arNumbers[j] > nKey)

{

arNumbers[j + 1] = arNumbers[j];

}

else

{

break;

}

j--;

}

arNumbers[j + 1] = nKey;

}

The worst case of the algorithm arises when the array is sorted in the opposite direction. The order of growth for Insertion sort algorithm is  THETA(n^2). I will not go in detail of the proof for this. You can see that there is a loop inside a loop. First loop has to iterate n times. Inside loop also has to iterate n times. Thats why its n*n = n^2..

Code is present at location https://github.com/harsha-kadekar/LibraryOfAlgorithms.git . 

CCRevEngCC

Initially after my training I had renewed interest in learning assembly language and try to develop a dissassembler. This is way back in 2011 or 2012. Sadly still disassembler development is going on. I started development of the dissassembler but abandoned it. But few months back I have again taken it up but with new design. So in those days we 3 of us - Me, Srivatsa, Shishir had created this google site. In this all the things we learnt about assembly language, and trails for developing assembly language are put up there. 

https://sites.google.com/site/ccrevengcc/

It has very useful resources.

And yeah you can see only Shishir was successful in creating disassembler. Hopefully I will do it as soon as possible.

List Files and Folders in Command Line interface

I was reading about File Systems in an Operating Systems book and suddenly thought of writing a tool which will list me all the files and folders of an OS. I had tried something similar to this previously with a GUI without much success. It is listed in my blog as List Files and Folders.

Well that previous attempt did helped me in getting an idea how not to start the development. First lesson learnt dont try to complete the design. First develop the basic and most simple stuff and then start adding on to it.

With this approach first thing I decided was I will not bother about GUI, rather it will be on Command Line interface. As a first iteration I will just list all the files and folders and their corresponding size. Later I added paths to this like absolute path, parent folder. Then show whether it is a file or a folder. Also try to show few attributes like is it hidden, is it readonly or is it system specific File/Folder. Once this is working fine, I latter added few other attributes like alternate name of the file/folder, creation time, last access time and last write time. This is display all this in a tab separated csv format.

Programming Aspect:

To represent a file or folder I have following structure -
typedef struct structFileFolder
{
WCHAR* strFileFolderName;
__int64 Size;
WCHAR* strAbsolutePath;
WCHAR* strParent;
WCHAR* strAlternameName;
SYSTEMTIME* sysTimeCreation;
SYSTEMTIME* sysTimeLastAccess;
SYSTEMTIME* sysTimeLastWrite;
DWORD dwAttributes;
bool isFolder;
bool isReadonly;
bool isHidden;
bool isSystem;
bool isEncrypted;
bool isCompressed;
bool isArchived;
}FileFolderInfo;

I have 3 main functions - 

extern "C" __declspec(dllexport) int ListFiles(char* strOption);
int ListFilesinPath(WCHAR* strPath, WCHAR* strParentPath);
int ListFilesOfDirectory(FileFolderInfo* folderInfo);

As you can see ListFiles function is exposed to outside world. This is the entry point for the file listing. strOption can be 3 things - ALL, a folder path, a file.
ALL means it will loop through all drives and list corresponding files and folders.
If it is not ALL it will check if it is a file or a folder. based on that it will take action.
It will actually call ListFilesinPath function. This intern will call ListFilesOfDirectory recursively to list all the files and folders. For iterating through the files I am using FindFirstFile, FindNextFile and FindFileData of Win32 API.

For creation time, last access time and write time, FindFileData has it in FILETIME structure. So I am converting to SYSTEMTIME when storing it in my FileFolderInfo structure. But when I am displaying I am converting it to a string format of type dd-MM-yyyy hh:mm:ss.

Also all the file attributes like isFolder, isReadOnly, isHidden, isSystem, isEncrypted, isCompressed, isArchived are derived from dwAttributes only.

To dynamically allocate memory and initialize FileFolder Info I have following function.
FileFolderInfo* GetFolderFileInfo();

Similarly to deallocate the memory for the same structure, I have following function
int CleanUpFolderFileInfo(FileFolderInfo* folderInfo);

For folders FindFileData does not provide you size. So we have to iterate through all the contents of the folder and add the size of each of these contents to get the size of the folder.

Following things are displayed about the file - it is similar to what structure is storing
File/Folder Name
Absolute Path of File/Folder
Parent Folder
Alternate Name of File/Folder
Is it a File of Folder
Is it Read Only
Is it Hidden
Is it System specific File/Folder
Is it Compressed
Is it Encrypted
Is it Archived
File/Folder Creation time
File/Folder Last access time
File/Folder Last Write time
File/Folder Attribute double word.

So code is present in the following github location -
https://github.com/harsha-kadekar/Disassembler.git

Actual code is present in two files - SystemStatistics.h and SystemStatistics.cpp of the project ProcessDissector.

These files will be later updated about other system statistics functions like listing process, services etc.

PE File of windows

PE file or Portable Executable File is a format of executables, dll and object files. In a high level this is a mixture of different structures. Each structure having specific information of that file. Also these structures will have information about where to look next for further information.

Some of the tutorials and articles which will explain about these PE files are

https://msdn.microsoft.com/en-us/magazine/ms809762.aspx

https://msdn.microsoft.com/en-us/magazine/bb985992.aspx

https://msdn.microsoft.com/en-us/magazine/cc301808.aspx

Iczelion's tutorial

I am trying to develop a disassembler and one of the model tool for disassembler is DumpBin. Among the different options there is an option called /ALL like DumpBin c:\testPE.exe /ALL 

This will go through the PE file read all the structures of that PE file and display the relevant information for you. I decided to write dll which will do the similar function. Anyways that would help me disassembler also like export functions, picking the code sections etc. While developing this tool learned a lot about PE file structures. I will go through it one by one. Before that I just prepared a high level image of the PE File hope it might help you to understand it

First thing to do is read the file, create the file mapping and obtain the view of that mapped file. This gives you the memory location of first structure of PE file - IMAGE_DOS_HEADER. This is nothing but MS-DOS stub. There are two important members of this structure. First one is e_magic. It should have value as IMAGE_DOS_SIGNATURE which is "MZ". Second one is e_lfanew. This is the offset, if you add this offset to the base image address you will get the address where IMAGE_NT_HEADERS is located. This image nt header is a collection of two headers (file header and optional header) and characteristics. Characteristic should have value IMAGE_NT_SIGNATURE that is "PE\0\0". File header has information like on which machine architecture this PE file will execute, whether this PE file is an executable or a dll, how many sections are present in this PE file, certain characteristics of the PE file like symbols is stripped or not like that. Optional Header has information like whether this is a 32bit or 64 bit application, what type of subsystem it needs like GUI or command line, then dll characteristics like can be relocated at run time, stack size, heap size, code size, then Data Directory array. There are 16 entries in the Data Directory array. Each one gives you two information - relative virtual address [RVA] of the directory location and size of the directory. Directories like export directory, import directory, resource directory, debug directory, etc. If you go to export directory you can find the information regarding functions which are exported by this PE file. similarly if you go to import directory you can find information related to all those functions which are imported by this PE file.

After NT Headers you will get IMAGE_SECTION_HEADERs. In the File Header it gives the information of number of section. Those many IMAGE_SECTION_HEADER structure will follow. Code section, initialized data section, uninitialized data section - these are the few sections. Each section header has information like name of section, virtual size, virtual address , size of raw data and pointer to raw data. Also each sections characteristics like whether it can be executed, or read or written to or even removed if not necessary are present in the Section Header.

Suppose I want to read the contents of that section from the PE File then do the following 3 steps
1. Open the file
2. In the Section header there is a field - PointerToRawData. Move your file pointer to the location which is pointed to by that field.
3. Read all the values upto the length mentioned by "SizeOfRawData" field present in Section header.

 Finding export function details -
0th element of the Data Directory will give you information regarding location and size of Export table. It gives a RVA and this needs to be converted to an offset with respect to base image. The offset is pointing to IMAGE_EXPORT_DIRECTORY which has information like module name, number of functions, address of functions, address of names, address of Name ordinals. Address of function is an RVA which is pointing to array of RVAs of function addresses. Address of Names is an RVA which is pointing to array of strings. Address of Name ordinals is an RVA which is pointing to array of words. Suppose I want to find a particular exported function abc then I will go through the array of strings of AddressOfNames. Let us assume that I found the function at index I in AddressOfNames. Using the same index pick the value present in AddressOfNameOrdinals array. This value will form the index for AddressOfFunctions.

Finding import Function details -
2nd element in the Data Directory [index is 1] will give you information about where to find Import Table.  This offset will point to array of IMAGE_IMPORT_DESCRIPTOR. One for each dll/PE file from which functions have been imported. Last element of the array is an empty image_import_descriptor. So to find how many dlls from which we have imported count till you find an empty image_import_descriptor. Each Image_import_descriptor has following information like library name, whether forward chaining is enabled or not then address of functions and name of functions. There are two fields both points to same thing initially OriginalFirstThunk and First Thunk both are RVAs which point to array of IMAGE_THUNK_DATA structures. Using the AddressOfData field we can identify whether the function was imported by name or through ordinal.  If IMAGE_ORDINAL_FLAG32 == (AddressOfData & IMAGE_ORDINAL_FLAG32) then it is through ordinal. AddressOfData & 0x7FFFFFFF will give you ordinal number. Else it is through function name. Function field is a RVA which points to IMAGE_IMPORT_BY_NAME structure. This has the name of the function.
Initially both OriginalFirstThunk and FirstThunk field of IMAGE_IMPORT_DESCRIPTOR will be pointing to same IMAGE_THUNK_DATA which intern has function names. As these functions are loaded I guess FirstThunk field afterwards will be having address of functions rather than function names.
IMPORT_TABLE link from First Thunk



SAME IMPORT TABLE link from Original First Thunk



IMPORT Table after PE file loaded (First Thunk) has been replaced.
  







My Code is present in Github - https://github.com/harsha-kadekar/Disassembler.git
In that solution of the dll can be found in folder ProcessDissector

Please note image has been taken from these following links -
http://www.codeproject.com/Articles/14360/Injective-Code-inside-Import-Table  - For import table
https://msdn.microsoft.com/en-IN/library/ms809762.aspx - For export table.
    

Listing Files and Folders

Recently my friend had developed a tool which will compare the files and try to list duplicate files also it will help the user to delete such files (http://www.shishirprasad.net/2014/09/learnings-from-diffing-tool.html) . So after reading his blog I also got motivated to develop my own tool for a practical problem.

I have created C drive with less hard disk space when compared to other drives. So now and then it gets filled up and goes to danger red mark. During those times I had to search for files and folders in C drive and delete unwanted among them. My search criteria will be finding those folders whose size is huge and try to delete files and folders inside them.

Currently UI of the tool is complete. It is having two stage. The first dialog will get the search criteria. When user presses OK in this dialog based on the user inputs it will form a Search Criteria structure -

typedef struct SearchFilesFolders
{
bool bHiddenFiles;
bool bReadOnlyFiles;
__int64 nMaxSize;
__int64 nMinSize;
bool bSearchForMaxSize;
bool bSearchForMinSize;
bool bCreationDateGreater;
bool bCreationDateLesser;
bool bModificationGreater;
bool bModificationLesser;
SYSTEMTIME systimeCreationDate;
SYSTEMTIME systimeModificationDate;
WCHAR* location;


}SEARCHFILEFOLDER;

User can form different conditions for searching files and folders like search only hidden files or search files whose size is greater than 100kb or search files whose size is lesser than 100 kb or find the files whose creation date is greater than or lesser than certain date. It can be combination of all of them or some of them.

The second UI is the dialog which will show the results based on the search condition set in the previous dialog. Dialog will have 2 sections 1st is a tree view of the files and folders, 2nd is a readonly edit box which will have the details of the files and folders which was selected in the tree view.

Now I am able to search the path select the folders and files which are meeting the condition. I am now able to display them in tree view. There are issues like I wanted to display 2 different icons for folder and file but currently it is not happening properly. Also it is crashing in many places. still displaying the details of the selection in Tree View at bottom readonly edit control has to be done.

Every File and Folder will have following structure -

typedef struct FileInfo
{
__int64 dwFileSize;
WCHAR* strFileName;
WCHAR* location;
DWORD dwFileAttributes;
bool bHidden;
bool bReadonly;
FILETIME ftCreationTime;
FILETIME ftModificationTime;
bool bIsFile;
bool bError;
struct FileInfo* ParentFolder;
struct LstFileInSubFolder* ChildElements;
PWIN32_FIND_DATA actualData;
}FILEINFO;

And I am forming a list of file folder structure with root as the "Search location folder" given in the previous UI.

typedef struct LstFileInSubFolder
{
FILEINFO* fileFolder;
struct LstFileInSubFolder* nextFileFolder;
}LSTFILEINSUBFOLDER;

Still lot of issues are there that needs to be fixed. I will come back soon.

Source code at this stage is - https://github.com/harsha-kadekar/ListFilesFolders.git

I will come back soon with the complete developed code.

Insertion Sort

I have started studying Design and Analysis of Algorithms. While going through, I encountered many sorting algorithms. As best way to learn anything is to implement it, I thought of developing a Dynamic link library of different algorithms. I have used assembly language for coding. Till now I have written 3 sorting algorithms
1. Insertion sort
2. Merge Sort
3 Bubble Sort.
I will give the code and also try to explain about the algorithms. I will also try to list the difficulties I faced while developing it.
1. Insertion Sort.


InsertionSort proc pArray:DWORD, nSize:DWORD

LOCAL temp:DWORD 

mov ecx, 1
mov esi, pArray
assume esi:ptr DWORD

START_WHILE:
mov eax, nSize
;dec eax
cmp ecx, eax
jge END_WHILE

mov eax, ecx
imul eax, 4
mov ebx, [esi + eax]
mov temp, ebx
mov edx, ecx
dec edx
mov eax, temp
mov ebx, edx
imul ebx, 4
;.while edx >= 0 && [esi+ebx] > eax
START_WHILE2:
cmp edx, 0
jl END_WHILE2
cmp [esi+ebx], eax
jle END_WHILE2

;mov eax, temp
;mov temp2, edx
;.if [esi+edx*4] >eax
mov ebx, edx
imul ebx,4
mov eax, [esi+ebx]
mov ebx, eax
mov eax, edx
inc eax
imul eax,4
mov [esi+eax], ebx
dec edx
mov ebx, edx
imul ebx,4
mov eax, temp
;.endif
jmp START_WHILE2
END_WHILE2:

mov eax, edx
inc eax
imul eax, 4
mov ebx, temp
mov [esi+eax], ebx
inc ecx
jmp START_WHILE
END_WHILE:

Ret
InsertionSort EndP


I could have written it in a much better form. Like i have calculated the index of the array first and placed it in the eax register. Instead of that i could have directly written as [esi + ecx*4].
Insertion sort takes Big Oh(n^2) and it sorts in place. For small number of elements its a good algorithm.
Insertion sort is like arranging a pile of cards. Take a single card from the table and find the correct position for that card among the cards you are holding in your hand. Suppose there are 6 elements in the order
4 7 2 9 1 3
Then I will first chose 4 as it is the first element, I will hold it, then I will pick 7 from set. As compared to 4 it should come after 4. So my ordered array is 4 7. Left random array is 2 9 1 3
Now I will pick 2, 2 should come before 4. So my ordered array would be now 2 4 7 and remaining are 9 1  3.  Similarly if we continue we get the ordered array 1 2 3 4 7 9
But important thing is that usually the unordered part and ordered part will be present in the single array. So the order of element movement will be like this
4 7 2 9 1 3
4 7 2 9 1 3
2 4 7 9 1 3
2 4 7 9 1 3
1 2 4 7 9 3
1 2 3 4 7 9

While writing the code, some of the mistakes I did was addressing. As it is a DWORD, it is 4 times the bytes. And addressing is always byte addressing. So we need to multiply the index each time by 4 and then I can add it to base address to get the actual address. I forgot to multiply it by 4. After 1st round of running the program I got to know my stupid mistake. Apart from that some logical mistakes in the algorithm I had done while coding. Another mistake is I forgot that in the mul instruction both eax and edx will be used. so if you have anything in edx after mul instruction it will be lost.

Well remaining algorithms details I will update it as soon as possible.