Henry's Points

The good way to know how TCP checksum works, is to dig into TCP/IP protocol source code. In brief, TCP checksum is a 16-bits segments in TCP header. At very beginning, checksum is reset to 0. Then, TCP pseudo header, TCP header and TCP data are broken into 16-bits chucks. All these 16 bit words are added together using 1’s complement arithmetic. The result will be loaded to TCP checksum field. After TCP segment is transmitted to the destination, it will be recalculated including TCP pseudo header, TCP header and TCP data. If checksum is oxffff, then, all the data have been transmitted successfully.

The following is checksum function.

unsigned short checkSum(unsigned short *szBUF,int iSize)

{
/* Set checksum to 0 */
unsigned long ckSum=0;

/* All 16-bits chucks are added except last chuck*/
for(;iSize>1;iSize-=sizeof(unsigned short))
ckSum+=*szBUF++;

/* Added the last chuck */
if(iSize==1)
ckSum+=*(unsigned char *)szBUF;

/* The carry over 16 bits should be calculated as well,
Which is hardly mentioned in the explanation.
Some other source code use while loop to realize:
while (ckSum >> 16)
ckSum = (ckSum&0xffff) + (ckSum >> 16);
The code is more matured for IPv6. */

ckSum=(ckSum>>16)+(ckSum&0xffff);
ckSum+=(ckSum>>16);

/* Return negation of checksum */
return(unsigned short )(~ckSum);
}

Share on Facebook

Tags: Coding, How-to, Networks by hengdu
No Comments »

Ethernet

Birth Year: 1973

Father: Robert M. Metcalfe

C Language

Birth Year: 1973

Father: Dennis Ritchie of Bell Laboratiries

C was developed from 1969 to 1973 by Dennis Ritchie of Bell Laboratories. The American National Standard Institute (ANSI) ratified the ANSI C standard in 1989. The standard defines the C language and a set of library functions known as the C standard library. Kernighan and Ritchie describe ANSI C in their classic book, which is known affectionately as “K&R”. In Ritchie’s words, C is “quirky, flawed, and an enormous success.”

GNU Project

Birth Year: 1984

Father: Richard Stallman

The GNU project is a tax-exempt charity started by Richard Stallman in 1984, with the ambitious goal of developing a complete Unix-like system whose source code is unencumbered by restrictions on how it can be modified or distributed. As of 2002, the GNU project has developed an environment with all the major components of a Unix operation system, except for the kernel, which was developed separately by the Linux project.

Linux

Birth Year: 1991

Father: Linus Torvalds

From:torvalds@klaava.Helsinki.FI (Linus Benedict Torvalds)
Newsgroup: comp.os.minix
Subject: What would you like to see most in minix?
Summary: small poll for my new operating system
Message-ID: 1991Aug25, 20578.9541@klaava.Helsinki.FI
Date: 25 Aug 91 20:57:08 GMT
Organization: University of Helsinki. 

Hello everybody out there using minix- 

I'm doing a (free) operating system (just a hobby, won't be big
and professional like gnu) for 386(486) AT clones. This has
been brewing since april, and is starting to get ready. I'd like
any feedback on things people like/dislike in minix; as my OS
resembles it somewhat (same physical layout of the file-sytem
due to practical reasons)among other things. 

I've currently ported bash (1.08) an gcc (1.40), and things seem to work.
This implies that i'll get something practical within a few months, and I'd
like to know what features most people want. Any suggestions are welcome,
but I won't promise I'll implement them   

Linus Torvalds torvalds@kruuna.helsinki.fi

Share on Facebook

Tags: Business, Coding, Linux by hengdu
No Comments »

Just browse my favorite book Thinking in C++. In the preface, it mentioned XP (Extreme Programing) approach.

Probably only someone who has experienced XP and non-XP can tell us what’s the benefits. I am the one of them. I used to work for two companies, which have different opinions according to XP. The first company adopted XP approach. When new feature has documented and begin coding, test cases will be documented as well and prototype is shown for the customers. Any enhancement and improvement will be easily implemented in the circle of three guys. The life circle of development will be short.

The second company didn’t adopt XP approach. Here is an example which will be interesting. Developer lead make a function specification. (I believe he just imagine what the feature looks like and put them to the document). Developer began to coding followed the function spec. After coding done, he/she check in branch build. QA begin to test after build is ready. There are bunch of bugs need to be fixed, some of them are just because QA has different opinion of how the feature works. Argument is obviously. Finally, the new feature can be released. However, the sales engineers, who represent the customers, are not satisfied with some part of new feature. So, again, customer requirement will be sent back. After argument, developers have to make changes for function spec and redo coding. That is the story. Normally, the life circle of development of one feature will be triple time of the first company. The following is a simple chart that you can compare.

Smart company can do the same thing by using few people and few cost. Other company, although very diligent, cannot achieve good result. That’s the benefit of XP.

Share on Facebook

Tags: Coding by hengdu
No Comments »

Probably to count set bits in a byte or in 4 bytes will be most frequent asked question in the interview. Fortunately, I found four solution.

1. The mask and shift approach.
2. The Brian Kernighan approach.
3. The index into an array approach.
4. The MIT HACKMEM approach.

Make and Shift

unsigned char countbits_shift_method (unsigned char b)
{
unsigned char mask, count;

for (count = 0, mask = 0×80; mask != 0; mask >>= 1)
{
if (b & mask)
count++;
}

return (count);
}

Brian Kernighan

unsigned char countbits_bk_method (unsigned char b)
{
unsigned char count;

for (count = 0; b != 0; count++)
{
b &= b – 1; // this clears the LSB-most set bit
}

return (count);
}

Index into an Array

unsigned char parity_array [256] =
{ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, … };
// Note that you need to fill-in this array

unsigned char countbits_array_method (unsigned char b)
{
return (parity_array [b]);
}

MIT Hack Memo

int BitCount(unsigned int u)

{
unsigned int uCount;

uCount = u
- ((u >> 1) & 033333333333)
- ((u >> 2) & 011111111111);
return
((uCount + (uCount >> 3))
& 030707070707) % 63;

}

Share on Facebook

Tags: Coding by hengdu
No Comments »