Search This Blog

Monday, September 12, 2011

Signed or Unsigned?

I found it confusing at times to understand signedness of integer and hence I have attempted to tackle some of these issues here. First, the task I want to discuss here is the internal representation of a given number in a signed and unsigned integer type and I think that this will help me to have a better understanding of signedness.
To illustrate the point, let us assume that we need to develop a function that should return the absolute value of input number. For this task, can we just return the same value but specify that the return type of unsigned as follows?

Unfortunately, this will not work properly. For example, if we pass a negative value to the above function and assign the returned value to the unsigned type of integer, we will see that the function somehow did the trick. However, if we assign the returned value to the signed type of integer, it will still display the negative value. Why is that? That is because we have not actually changed anything. Let me explain with an example. Say, we pass '-1' to unsigned_abs() function, this passed value is represented as 32 1's in a binary format. This value is interpreted as '-1' in a signed integer but that same value is interpreted as 0xffffffff in a unsigned integer.

So then what should we do? Here is one way to implement abs() function.


This will actually update the internal value of input value and return the real absolute value. To verify this, I wrote a function to display the binary value of an input integer as follows.

The above function simply uses STL stack to store binary values of the input value and prints out on the screen and when I executed the returned values from unsigned_abs() and signed_abs(), I could see that the returned value of unsigned_abs() is displayed as 32 1's but the returned value of signed_abs() is displayed as '1' when I called binaryrep().

In conclusion, we need to be careful of what's really taking place when we use either unsigned and signed and in my opinion, if we are not sure, I would recommend to just use signed integer.

Tuesday, August 23, 2011

Take advantage of chromium project!

This post is going to be very short. In this post I just wanted to share my experience with chromium browser project. Not that I have ever contributed to chromium project but as I read/study the code for my own edification, I found it very useful.


I found that there are many parts of code that I can use for my various needs and as we know the code quality must be good.
For instance, I recently found that how to dump stack trace on Windows. Earlier last year I tried to do the similar thing on Linux but I never knew that the similar API exists on Windows. But thanks to these projects, I found the working example code of stacktrace code. The list can go on and on and what's neat about this project is that it has the code that is doing the same thing on Linux, Windows, and Mac so if you need to write code for all these platforms in C/C++, check it out! Lastly, I hope that I will be able to contribute to the project in the near future.

Saturday, August 6, 2011

Breadth First Search and Backtracking

This week I had a chance to look at Topcoder.com tutorial and read about BFS/Backtracking. Sometimes it is not clear if we need to use BFS or Recursion/backtracking approach to solve a given problem and the following is the BFS description from Topcoder.com

Breadth First Search (BFS):
Problems that use BFS usually ask to find the fewest number of steps (or the shortest path) needed to reach a certain end point (state) from the starting one. Besides this, certain ways of passing from one point to another are offered, all of them having the same cost of 1 (sometimes it may be equal to another number). Often there is given a N x M table (formed of N lines and M columns) where certain cells are passable and others are impassable, and the target of the problem is to find the shortest time/path needed to reach the end point from the start one. Such tables may represent mazes, maps, cities, and other similar things. These may be considered as classical BFS problems. Because BFS complexity is in most cases linear (sometimes quadratic, or N logN), constraints of N (or M) could be high - even up to 1 million.

Having said that let me post two problems that sound somewhat similar but require different approach to solve. First question. We have a robot sitting somewhere in the matrix and we want to find the shortest path to get to a certain position. This is a kind of problem that needs BFS approach as described above. Whenever we see the shortest and the cost to move from one state to another is same, it is safe to assume that we can use BFS. As we know from graph theory, we use BFS to find the shortest path and hence we can apply BFS to solve the problem and the key to remember is that BFS requires us to use queue-like data structure. At each node, we need to enqueue the neighboring nodes for the future processing and we do this this until the queue is empty. When the queue is empty, we know that we have covered all the nodes that could be reached from the source node. Lastly, for this particular problem we want to keep the number of paths taken so far and use that to calculate the next one by simply adding one.

Second question. How do we find the possible number of paths from one node to another for a robot to take? In this problem, we do not concern the shortest path but would like to know how many paths exist from the source node to the destination node. This is somewhat simple problem in that we just need to recursively call ourselves until we get to the destination. For this particular problem, we need backtracking because we want to keep track of states between each call and thus, we will need to use backtracking technique.
Here is the better description of backtracking from Topcoder.com:

Backtracking:
This technique may be used in many types of problems. Just take a look at the limits (N, M and other main parameters). They serve as the main hint of a backtrack problem. If these are very small and you haven't found a solution that's easier to implement - then just don't waste your time on searching it and implement a straight-forward backtracking solution. 

Usually problems of this kind ask you to find (similarly to Brute Force):

  1. Every possible configuration (subset) of items. These configurations should respect some given rules.
  2. The "best" configuration (subset) that respects some given rules.
What does that mean? It means that we do not want to explore the path that we have already visited. In other words, we keep the states so far and add the next route and try the next route that's available. Why? In the next move, we normally want to know where we have visited to make a decision. However, when we come back from the next move, we want to take out the next move we just added and add another route that we have not tried yet.

Again, it is possible that the question may ask to calculate the shortest path but the cost for each move differs. For Backtracking problem, it normally asks for finding all the possible paths or some sorts so let us keep that in mind to differentiate.

So in conclusion, look for some keywords when we need to solve problems.
If it states the shortest path with the same cost for each move, try BFS. But if it asks us to find all possible paths or each cost differs, try to see if we can use Backtracking.

p.s. Let me add two samples: one for bfs and the other for backtracking for future reference.

Friday, July 22, 2011

WinHttpSendRequest is not so easy to use

The other day I tried to look up WinHttpSendRequest() API for more information and found that the second entry in google search result was my question that I posted at MSDN forum two years ago with regard to its usage example.
At that time I was trying to understand how to use WinHttpSendRequest() API to construct Http POST request and could not find any good example on the web and hence, I decided that I should write something about it in my blog.

Followings are the basic flow of WinHttp calls to create Http Post request.

  • Prepare WinHttp session handle and connection handle. We can reuse these two handles to send multiple requests. For this use WinHttpOpen and WinHttpConnect API
  • Create a specific WinHttp request handle. Once we have the request handle, we can associate certain options with this handle. Use WinHttpOpenRequest.
  • Construct POST request and details are as follows. This is where it gets real tricky.

In order to successfully send our Http Request, we need two APIs: WinHttpAddRequestHeaders() and WinHttpSendRequest()

First, I assume that we want to send multipart form HTTP Post request to upload a file along with some fields. For this task, we need to specify our intention but what's tricky is the fact that we need to specify the boundary of http header so that Web server knows where the header ends and how to parse our request. Here is an example of its usage.

WinHttpAddRequestHeaders(
    hRequest, 
    "Content-Type:multipart/form-data; boundary=----------ThIs_Is_tHe_bouNdaRY_$", 
    -1L, 
    WINHTTP_ADDREQ_FLAG_ADD
);

As you can see, we have put certain string such as "boundary=----------ThIs_Is_tHe_bouNdaRY_$" to inform the web server to look for these string to parse the request correctly.

Now, it is time to construct all the fields. Let me give you one example of form field.
Say we have a field called "username" and want to specify its value "ilho". Following is the sequence of string we need to construct and just to make it easy to read, I added 'new line' after '\r\n' but in reality you need to have all the strings together as one string. You need to add the same format for all the fields to the same string.

------------ThIs_Is_tHe_bouNdaRY_$\r\n
Content-Disposition: form-data; name="username"\r\n\r\n
ilho\r\n

For data file that we want to upload, we need special care. Now, assume that we want to upload some text file. Here is the string that you want to build.

------------ThIs_Is_tHe_bouNdaRY_$\r\n
Content-Disposition: form-data; name="personal_data";\r\n filename="personal.txt"\r\n
Content-Type: text/plain; charset=utf-8\r\n\r\n

Finally, you will need to end your request by specifying the ending as follows.

\r\n------------ThIs_Is_tHe_bouNdaRY_$--\r\n\r\n

I know that these look really ugly and I do not know if there is any better way to do this. Unless I am mistaken, I think for this specific part, I prefer to use curl because it is a lot easier to use curl to construct POST request than WinHttp.

But for now, let me throw out some code example to illustrate what we need.

StringCbPrintf(
    ffield,
    sizeof(ffield),
    "------------ThIs_Is_tHe_bouNdaRY_$\r\n"
    "Content-Disposition: form-data; name="username"\r\n\r\n"
    "ilho\r\n"
);

StringCbPrintf(
    filefield,
    sizeof(filefield),
    "------------ThIs_Is_tHe_bouNdaRY_$\r\n"
    "Content-Disposition: form-data; name=\"personal_data\"; filename=\"personal.txt\"\r\n"
    "Content-Type: text/xml; charset=utf-8\r\n\r\n"
);

StringCbPrintf(formdata, sizeof(formdata), "%s%s", ffield, filefield);

Once we have the form ready, we need to calculate the entire size of request which includes the actual text file. With all these information, here is WinHttpSendRequest.

total_length = strlen(formdata) + filesize + strlen("\r\n------------ThIs_Is_tHe_bouNdaRY_$--\r\n\r\n");


WinHttpSendRequest(
    hRequest,
    WINHTTP_NO_ADDITIONAL_HEADERS,
    0,
    (LPVOID)formdata,
    (DWORD)strlen(formdata),
    total_length,
    0
);

Once we send our HTTP request, we can start to send our text file using WinHttpWriteData followed by boundary string to finish the HTTP Post request. Hence, in minimum we need to call two WinHttpWriteData.

WinHttpWriteData(file content);
WinHttpWriteData("\r\n------------ThIs_Is_tHe_bouNdaRY_$--\r\n\r\n");  // boudary

At this point, we just need to receive the Web server response to your request by calling WinHttpReceiveResponse() API and we are pretty much done by now.

In the above example, I tried to present the steps in a rather raw format but in reality you may want to create either inline functions or macros to to reduce the typings and create a nice interface to work with WinHttp. Like I said, if you need to work on the similar code for both Windows and Linux, it is better off to use curl and I hope that MS will come up with better APIs or interfaces for the developers to work with Http requests.

Tuesday, July 12, 2011

Windows Startup Routine

It's has been a while since I looked at Windows startup routine and I realized that I don't remember the overview of it. So I grabbed Windows Internals and summarized it here for my future reference.

1. POST (Power On Self Test)

2. BIOS loads MBR into memory

3. MBR reads the first sector from the bootable partition and the code in the first sector loads the Bootmgr into memory

4. Bootmgr loads the boot loader, Winload.exe (Ntldr in the past)
Winload.exe
- loads the appropriate kernel and HAL images (Ntoskrnl.exe and Hal.dll)
- reads registry to determine boot device drivers and loads them.
- calls KiSystemStartup in Ntoskrnl.exe

Ntokrnl.exe
- phase 0
 prepares data structures for services to run in phase 1
 calls the object manager, security reference monitor, process
manager, user-mode debugging framework, and the Plug and Play manager initialization
- phase 1
 calls more initializations i.e. power manager, memory manager
 I/O manager initialization
 - creates I/O manager object types i.e. device, driver
 - perform boot-start drivers initialization and system-start device drivers are loaded and initialized
 - the Session manager(Smss) process is started. Smss is responsible for creating user-mode environment that provides the visible interface to Windows

Smss
 - start the Windows subsystem
 - start Csrss which is Client Server Runtime Process
  - CSRSS: user-mode portion of the Win32 subsystem; Win32.sys is the kernel-mode portion.
 - launches Windows Initialization Process (Wininit) and start the interactive   logon manager process (Winlogon)

Wininit
 - performs startup steps such as creating the initial window station and desktop objects
 - creates SCM which initializes auto-start services and drivers

Once Winlogon validates the logon, Winlogon sets up the user environment and starts the shell(explorer)



That's it for now and hopefully, in the future I will try to add some diagram to describe what I wrote in the above.

Sunday, July 3, 2011

global/static variables - where are they?

At church today I met a person who is also a programmer and he seems to be well versed in C++. As we talked, he asked me a question about C++ related questions but as for me, I just started to work on my C++ as I have been using C for the past few years. Hence, I could not answer to his question clearly. His question was that when we declare static variables inside the class, where they go in the process memory.
In the past, I worked on ELF and PE on Linux/Windows but that did not really help me much to answer his question so when I came home, I decided to first write a C code and verify the location of static/global variables. In theory, global variables that are not defined should go to 'data' section and those that are either defined to be zero should go to 'bss' section. But for those that are defined to be non-zero, I am not sure. So let me find out where they are.

So first let me show my C code.
int g_init_var1 = 3;
int g_init_var2 = 0;
int g_un_var;

int testfunc(int num)
{
int auto_var;
static int static_var_1 = 0;
static int static_var_2;

if (num == 1)
static_var_2 = num;
return 0;
}

int main(int argc, char *argv[])
{
int num;

scanf("%d", &num);
testfunc(num);

return 0;
}
I just declared two global variables and two static variables and after that I compiled the code with /FA option to produce assembly code.
C:\> cl /FApe.asm pe.c

When I looked at assembly code, I found the following.
PUBLIC  _g_init_var1
PUBLIC _g_init_var2
_DATA SEGMENT
COMM _g_un_var:DWORD
_DATA ENDS
_BSS SEGMENT
_g_init_var2 DD 01H DUP (?)
?static_var_1@?1??testfunc@@9@9 DD 01H DUP (?) ; `testfunc'::`2'::static_var_1
_BSS ENDS
_DATA SEGMENT
_g_init_var1 DD 03H
$SG2474 DB '%d', 00H
ORG $+1
$SG2475 DB '%d', 0aH, 00H
_DATA ENDS
_BSS SEGMENT
?static_var_2@?1??testfunc@@9@9 DD 01H DUP (?) ; `testfunc'::`2'::static_var_2
; Function compile flags: /Odtp
_BSS ENDS
As expected cl put g_un_var into 'data' segment because it is not defined. But I found it interesting to see what happens to the global variables that are defined. The global variables that are defined to be zero are actually located in 'bss' segment while the global variables that are defined to be non-zero are located in 'data' segment.
For static variables, we see the same pattern. The only thing I would comment is that g_init_var1/g_init_var2 is the type of PUBLIC but g_un_var is the type of COMM. Linker will concatenate all PUBLIC segments having the same name to form a single, contiguous segment. But with COMM, it creates a communal variable which behaves like external variables and communal variables are allocated by the linker. In a nutshell, they are just like global variables but we cannot assign them initial values and the only drawback of using communal variable is that they may not appear in consecutive memory locations.

After this exercise, I try the same on linux to see if there is any difference and the following is the result of objdump.
Disassembly of section .data:


00000000006008b8 <__data_start>:
6008b8: 00 00 add %al,(%rax)
...


00000000006008bc <g_init_var1>:
6008bc: 03 00 add (%rax),%eax
...


00000000006008c0 <static_var_1.2130>:
6008c0: 01 00 add %eax,(%rax)
...


Disassembly of section .bss:


00000000006008c8 <dtor_idx.6147>:
...


00000000006008d0 <completed.6145>:
6008d0: 00 00 add %al,(%rax
...


00000000006008d4 <g_init_var2>:
6008d4: 00 00 add %al,(%rax)
...


00000000006008d8 <static_var_2.2131>:
6008d8: 00 00 add %al,(%rax)
...


00000000006008dc <g_un_var>:
6008dc: 00 00 add %al,(%rax)
...


On Linux I found the similar principle applied. The global variable that is defined to be non-zero is located in 'data' segment but the global variable that is either undefined or defined to be zero is located in 'bss' segment. This is interesting part. If you remember, we saw uninitialized global variable was put in 'data' segment on Windows but on Linux they are located in 'bss' as Linux initialize them to be zero. The same applies to static variables on Linux. I also added the explanation on COMM directive in the above so please refer to it and the link below for more information.

So today's exercise helps me to visualize where the global/static variables go and let me finish my post with a couple of links that I referred to verify my theory.

- Paradigm Assembler User's guide : for communal variables