The Global Engineer’s Notebook

I”ll building my first non-trivial Erlang application, a server using the gen_tcp library, and I was left scratching my head for awhile with a problem today.  When I tried to connect to the server and send data with a really simple Python script, no data was being received by the server.  The incoming connection was handled by accept/1 properly, and the Python script didn’t seem to be reporting any errors.

I have to admit that I know next to nothing of Python, and I still consider myself a beginner in Erlang, so I was a bit concerned.  I wasn’t quit sure where the problem was being caused, so I switched the test client over to Erlang first.  I still could not receive any data at the server, so the problem seemed to be server-side.  Next I fired up the Erlang debugger to follow the execution of the server.  Sure enough, the server accepted the incoming connection and was blocking in the receive area.

The next step, which in hindsight I should have done first,  was to check all of the parameters to the listen/2.  Everything looked good, but I was unsure about the packet parameter and what it is used for.

gen_tcp:listen(
 PortNum,
 [list,
 {backlog, MaxCon},
 {active, once}, 
 {packet, 2},
 {reuseaddr, true}
])

Defines the type of packets to use for a socket. The following values are valid:

raw | 0

No packaging is done.

1 | 2 | 4

Packets consist of a header specifying the number of bytes in the packet, followed by that number of bytes. The length of header can be one, two, or four bytes; the order of the bytes is big-endian. Each send operation will generate the header, and the header will be stripped off on each receive operation. 

 What I did not realize, however, is that this parameter is not simply internal to Erlang.  If the client and the server don’t have the same settings, no data will flow between the two.  I changed the packet value to 0 in the server, and after rerunning the test client script, sure enough, data flowed from the client to the server.

I really felt like an idiot for missing this.

It has been awhile since I updated my blog.  I attribute it to work–the never ending stream of things to do kind of weights me down and I lose interest in all things technical from time to time.  I’m on a new project at work now, and I’m quite keen for it.  It’s still the same old low level C/Assembly firmware development, but I get to work with serial RapidIO technology and that has been quite interesting.  3.125 Gbps links!  I like this better than the former project working on MAC-layer software for a communication protocol.  I either want to be working at the PHY level directly accessing or working with the hardware, or I want to be up higher on the application level solving interesting problems.

Speaking of the application level, in late December I picked up my Erlang studies again, and I’m making good progress in understanding how to use it.  I’m implementing a simple chat server so I can wrap my mind around Erlang processes, file I/O and TCP sockets.  Having programmed a server in C/C++ before I can really appreciate how great Erlang is for network computing.  The code is so much more concise than the multithreaded C++ server I wrote in the past.  I’m not using the Erlang OTP libraries yet, I’m working with the gen_tcp library since it is familiar to BSD-style socket programming.  I’ve even dabled in a some Python scripts for testing the server.  Like how Perl has become my tool of choice for “glueing” things together, I can see myself using Python more often for testing in the future.  

Progress has been good, but I feel really shaky with strings at the moment.  Manipulating text is something any software has to do, but I find that the first thing that pops to my mind is the C++ STL string library, so I go searching for a similar library in the Erlang man pages.  I suppose that this must be expected–I just don’t know which libraries to use yet and it will take time to get the hang of them.  It took me awhile to master the use of the C++ STL string library and its algorithms, and I’m just going to have to figure out which Erlang libraries have the functions I need.  Perhaps I’ll draft a tutorial on Erlang string processing if I learn enough?

The good news is that my confidence with the language is increasing, tail recursion doesn’t seem that awkward, and immutable variables make complete sense now.  I won’t be using Erlang at work any time soon (not the right problem domain), but for personal enrichment and for learning new ways of doing things I’m quite pleased with Erlang. If I ever get into application network programming (or network services), I know what tool I’ll be choosing.

Before I start, I just want to give a shout out to dsmith and Joe Armstrong (at his book’s discussion forum) for all of the help in getting this module to work correctly.  The Erlang community is very helpful and kind to beginners!

So at this point I have both a proper table generation function as well as a function to calculate the CRC16 CCITT checksum for a list of integers.  To generate a table, you can call the maketable/0 function and it will return a list with the entire LUT.  To calculate the checksum on a list of integers, call ccitt/1 and pass the list as the parameter.  At this time the module has a static look-up table (LUT) that is used by the ccitt function for simplicity in using the module.  The LUT generation was really just an exercise for me to learn Erlang.  Here is the latest version of the code:

%
%
% CRC16 CCITT implementation based on a lookup table
%
%
%

-module(crc16).
-export([maketable/0]).
-export([ccitt/1]).

% ITU CRC16 CCITT Normalized Polynomial
-define(POLYNOMIAL, 16#1021). % for left-shifts

% ITU CRC16 CCITT Initial Value
-define(INITIAL_VALUE, 16#FFFF).

% ITU CRC16 CCITT Look-up Table (LUT) based on left-shifts
-define(CRC16LUT,
[ 16#0000, 16#1021, 16#2042, 16#3063, 16#4084, 16#50a5, 16#60c6, 16#70e7,
16#8108, 16#9129, 16#a14a, 16#b16b, 16#c18c, 16#d1ad, 16#e1ce, 16#f1ef,
16#1231, 16#0210, 16#3273, 16#2252, 16#52b5, 16#4294, 16#72f7, 16#62d6,
16#9339, 16#8318, 16#b37b, 16#a35a, 16#d3bd, 16#c39c, 16#f3ff, 16#e3de,
16#2462, 16#3443, 16#0420, 16#1401, 16#64e6, 16#74c7, 16#44a4, 16#5485,
16#a56a, 16#b54b, 16#8528, 16#9509, 16#e5ee, 16#f5cf, 16#c5ac, 16#d58d,
16#3653, 16#2672, 16#1611, 16#0630, 16#76d7, 16#66f6, 16#5695, 16#46b4,
16#b75b, 16#a77a, 16#9719, 16#8738, 16#f7df, 16#e7fe, 16#d79d, 16#c7bc,
16#48c4, 16#58e5, 16#6886, 16#78a7, 16#0840, 16#1861, 16#2802, 16#3823,
16#c9cc, 16#d9ed, 16#e98e, 16#f9af, 16#8948, 16#9969, 16#a90a, 16#b92b,
16#5af5, 16#4ad4, 16#7ab7, 16#6a96, 16#1a71, 16#0a50, 16#3a33, 16#2a12,
16#dbfd, 16#cbdc, 16#fbbf, 16#eb9e, 16#9b79, 16#8b58, 16#bb3b, 16#ab1a,
16#6ca6, 16#7c87, 16#4ce4, 16#5cc5, 16#2c22, 16#3c03, 16#0c60, 16#1c41,
16#edae, 16#fd8f, 16#cdec, 16#ddcd, 16#ad2a, 16#bd0b, 16#8d68, 16#9d49,
16#7e97, 16#6eb6, 16#5ed5, 16#4ef4, 16#3e13, 16#2e32, 16#1e51, 16#0e70,
16#ff9f, 16#efbe, 16#dfdd, 16#cffc, 16#bf1b, 16#af3a, 16#9f59, 16#8f78,
16#9188, 16#81a9, 16#b1ca, 16#a1eb, 16#d10c, 16#c12d, 16#f14e, 16#e16f,
16#1080, 16#00a1, 16#30c2, 16#20e3, 16#5004, 16#4025, 16#7046, 16#6067,
16#83b9, 16#9398, 16#a3fb, 16#b3da, 16#c33d, 16#d31c, 16#e37f, 16#f35e,
16#02b1, 16#1290, 16#22f3, 16#32d2, 16#4235, 16#5214, 16#6277, 16#7256,
16#b5ea, 16#a5cb, 16#95a8, 16#8589, 16#f56e, 16#e54f, 16#d52c, 16#c50d,
16#34e2, 16#24c3, 16#14a0, 16#0481, 16#7466, 16#6447, 16#5424, 16#4405,
16#a7db, 16#b7fa, 16#8799, 16#97b8, 16#e75f, 16#f77e, 16#c71d, 16#d73c,
16#26d3, 16#36f2, 16#0691, 16#16b0, 16#6657, 16#7676, 16#4615, 16#5634,
16#d94c, 16#c96d, 16#f90e, 16#e92f, 16#99c8, 16#89e9, 16#b98a, 16#a9ab,
16#5844, 16#4865, 16#7806, 16#6827, 16#18c0, 16#08e1, 16#3882, 16#28a3,
16#cb7d, 16#db5c, 16#eb3f, 16#fb1e, 16#8bf9, 16#9bd8, 16#abbb, 16#bb9a,
16#4a75, 16#5a54, 16#6a37, 16#7a16, 16#0af1, 16#1ad0, 16#2ab3, 16#3a92,
16#fd2e, 16#ed0f, 16#dd6c, 16#cd4d, 16#bdaa, 16#ad8b, 16#9de8, 16#8dc9,
16#7c26, 16#6c07, 16#5c64, 16#4c45, 16#3ca2, 16#2c83, 16#1ce0, 16#0cc1,
16#ef1f, 16#ff3e, 16#cf5d, 16#df7c, 16#af9b, 16#bfba, 16#8fd9, 16#9ff8,
16#6e17, 16#7e36, 16#4e55, 16#5e74, 16#2e93, 16#3eb2, 16#0ed1, 16#1ef0 ]).

%
% exported functions
%
maketable() -> outer_loop(0,255, fun tablevalue/1).
ccitt(Data) -> crc16(Data, ?INITIAL_VALUE).

%
% internal functions
%
inner_loop(0, X, _) -> X;
inner_loop(N, X, F) -> inner_loop(N-1, F(X), F).

outer_loop(Max, Max, F) -> [F(Max)];
outer_loop(I, Max, F)   -> [F(I)|outer_loop(I+1, Max, F)].

calculate(X) when X =< 255 ->
Reg = X bsl 8,
inner_loop(8, Reg, fun(Y) ->
if Y band 16#8000 /= 16#0000 -> ?POLYNOMIAL bxor (Y bsl 1);
Y band 16#8000 == 16#0000 -> Y bsl 1
end
end).

tablevalue(X) ->
calculate(X) band 16#FFFF.

crc16([], Acc) -> Acc;
crc16([Byte|TheRest], Acc) when Byte =< 16#FF ->
TableIndex = (Acc bsr 8 ) bxor Byte,
UpdatedAcc = ((Acc bsl 8 ) bxor lists:nth(TableIndex+1, ?CRC16LUT)) band 16#FFFF,
crc16(TheRest, UpdatedAcc).

I pleased with the results thus far; the output matches that of my C++ code.  I also feel much more confident with Erlang now and I think I’m ready to get to work with concurrency.  To summarize what I have learned from wrirting this module:

• a better understanding of recursive function design
• looping in Erlang, especially looping with accumulation
• how to control overflow in binary arithmetic
• a better understanding of functions and funs

I suspect this module will still evolve along the way.  For further investigation:

• error and exception handling for invalid input
• switching from a list look-up to an array look-up to improve performace [dsmith pointed out to me that Erlang list look-ups are O(n)]
• controlling the display of output on the screen — I’d like to be able to display hex, if possible

In Chapter 8 of Programming Erlang, there is a short example that performs a rough measurement of the time it takes to spawn a given number of processes.  Check the book if you want to see the code that genereates the test, but I just wanted to share the results from two different architectures.

I first ran the test on an Intel Core2 Duo @ 2.40 GHz, 1.0 GB RAM with Windows XP SP2.  I first spawned 5,000 processes, then 10,000 and finally 20,000.  The results are not bad on this machine.

4> processes:max(5000).
Maximum allowed processes:32768
Process spawn time=3.0 (3.2) microseconds

5> processes:max(10000).
Maximum allowed processes:32768
Process spawn time=4.7 (4.7) microseconds

6> processes:max(20000).
Maximum allowed processes:32768
Process spawn time=4.7 (4.7) microseconds

I then ran the same test on my Sun Blade 100 system.  The system runs Solaris 10 and the base architecture is a UltraSparc IIe processor with 512 MB of RAM.  The results are below.

2> processes:max(5000).
Maximum allowed processes:32768
Process spawn time=18.0 (28.2) microseconds

3> processes:max(10000).
Maximum allowed processes:32768
Process spawn time=18.0 (26.0) microseconds

4> processes:max(20000).
Maximum allowed processes:32768
Process spawn time=17.5 (25.75) microseconds

I was really impressed with performance.  Even though the Blade 100 is just a single CPU and it has half the memory, the performance was not bad at all compared with the Core 2 Duo.  

[sigh] One day I’d love to write heavy duty server software running on one of these beasts:

Sun Netra 1290

In my last post about Erlang I made a note to myself to find out if it is possible to declare funs in the top level of a module.  According to this page,

… modules can only define functions. It is an error to assign to a variable at the top level of a module.

At least I know now.  I’m sure it is in the Erlang book but I it is hard to search through paper books when you’re looking for info.  I’ve been spoiled by search PDFs!

In order to better learn Erlang, aside from following the examples in Programming Erlang, I have been trying to get my first Erlang programming project working.  Being in telecoms, I’d go crazy without bit manipulation, so my first project was to implement CRC16 CCITT, as CRC algorithm commonly used in communications systems such as XGPHS or WiMAX.  I thought this would be an easy task, but it turned out to be more challenging than I thought.

So before I present the module, here is some initial advice to fellow beginners: unless you’re an experienced functional programmer, spend a lot of time on chapters 3 through 5 (sequential programming).  When I was working through the book examples, it all seemed easy enough, but when I needed to actually sit down and write something of my own, I ran into walls really quickly.  The hardest part was trying to convert my program design and thought process from iterative looping to tail-recursion.  I’m still not absolutely confident with Erlang yet, but this CRC16 project allowed me to get more practice with looping, funs, and other basic Erlang structures.  I just need to keep it up and I think I’ll get a better grasp on this language.

Note: I actually appreciate that the author devoted more space in the book to intermediate issues.  I recall when I was first learning C++ how frustrating it was to go from beginner to intermediate skill-level in the language.  These days there are better C++ texts, but I still remember feeling hopeless.

Back to my module though! The first part of the module generates a look-up table that holds all of the CRC16 CCITT values for a given eight-bit value.  The second part of the moduble will be responsible for running the CRC algorithm on a block of 8-bit vaules.  So here it was I have so far:

%
%
% CRC16 CCITT implementation based on a lookup table
%
%

-module(crctable).
-export([maketable/0]).

% ITU CRC16 CCITT Normalized Polynomial
-define(POLYNOMIAL,   16#1021).    % for left-shifts
-define(REVERSE_POLY, 16#8408).    % for right-shifts

% ITU CRC16 CCITT Initial Value
-define(INITIAL_VALUE, 16#FFFF).

inner_loop(0, X, _) -> X;
inner_loop(N, X, F) -> inner_loop(N-1, F(X), F).

outer_loop(Max, Max, F) -> [F(Max)];
outer_loop(I, Max, F) -> [F(I)|outer_loop(I+1, Max, F)].

calculate(X) ->
Reg = X bsl 8,
inner_loop(8, Reg, fun(Y) ->
if Y band 16#8000 /= 16#0000 -> ?POLYNOMIAL bxor (Y bsl 1);
Y band 16#8000 == 16#0000 -> Y bsl 1
end
end).

maketable() -> outer_loop(0,255, fun calculate/1).

This code does have a very critical error that I have not figured out how to fix yet.  If you run “crctable:maketable().” in the Erlang shell, you’ll notice that the value of the second element in the list is 69665.  Right away this should be an indicator of error; a CRC16 mask can only be sixteen bits, and the maximum integer value is 2^16 -1, or 65535.  What we have is “ye olde overflow” bug!  The value for the second element in the list should be 0×1021 in hex**, which is 4129 in decimal.  Using the original output, f I adjust for overflow, we get 69665 – 2^16 = 4129, the value we want.  I must find a way to restrict the output of the calculate() function to sixteen bits.  Any suggestions?

Solution: Rudi in the comments provided a simply fix.  Check it out if interested.  I tried implementing something such as:

………
Val = inner_loop(8, Reg, fun(Y)-> ……. ,
Val band 16#FFFF.

However, this returned the same output as my original code.  Rudi’s solution works though.  Thank you!

** I know this because I have C++ code that calculated CRC16 CCITT correctly, and the second value in the look-up table is 0×1021.

While developing this simple module, I came across an issue that I was not sure how to solve at first.  The answer is in chapter five of Programming Erlang in the Miscellaneous Short Topics section, by the way.  In the function outer_loop(), I wanted to call another function, calculate().  If I just put the function name as the parameter, I had an error like this in the Erlang shell:

** exception error: bad function calculate
in function  crctable:outer_loop/3

At first I believed that perhaps all functions that are passed as parameters must be funs rather than functions.  This was distrubing to me because if one has nested looping, such as in my CRC16 example, the fun syntax starts to make the code very difficult to read.  The solution is to use a function reference as the paramter rather than directly passing the function.

Notes to self:  Look into the following

Is it possible to assign a fun freely in a module along with regular functions, such as:

function1(X) -> X*0.5.
Z = fun(X) -> X*2 end.
function2(X) -> X:X.

Erlang is the tech news more and more these days as a possible tool for designing software to run on multiple core machines.  I’m very interested in servers and high-end server software so I have been following the news to see if Erlang will take off like other languages.  I must admit that I’m not the type to jump onto new languages at a whim.  I’m more intersted in building systems than I am in fancy frameworks or nifty syntax or what not.  Though I’ve considered devoting some time to messing with Eiffel or Ada or Smalltalk or Python, I don’t really have a reason to devote my free (which I prefer to spend on foreign language study) time to them.  C++ and Perl do everything I have ever needed, and I”m already very familiar with the Standard Template Library, POSIX API, Win32 API, and other standard interfaces.  Ultimately when I try a new language, the reason I give up on it is that it takes a lot of time to master new APIs and frameworks.  No matter how many times I tried to do something with Python, it was faster to simply hack it out in C++ even if the code size was much larger.

Erlang does offer something that C++ cannot offer me though: a unique concurrency model without shared memory.  Writing multi-threaded software in C++ is always an exercise in syntax rules, debugging and humility.  Win32 Threads and PThreads are C APIs that force one to battle with static object behavior in your OOP applications.  You might remark that Python and many other languages have threads, why Erlang?  For me, it is all about doing away with shared memory and simplifying the system design.  What’s more, Joe Armstrong, the author of the language, has provided lots of data on the performance of Erlang.  I am also impressed that Ericsson and Nortel, two big cmpanies in the telecom industry I work in, employ Erlang in network telecom equipment that is used in massive telecom systems.  Telecom software is some of the most robust software operating in the wild!

I picked up Joe Armstrong’s text, the only text on Erlang, at this time, and I’ve made it to chapter eight when the concurrency discussion begins and you dive into Erlang’s message passing constructs.  I have to say that so far I am struggling with the language though.  I understand the concepts, it is just hard to apply them to real software.  The idea that you cannot have variables is really messing with my brain.  Once you assign a value to a variable it remains that way forever–everything is “const”.  To communicate with another process, send a message.  It is going to take some time to really get the ideas burnt into my brain.

Perhaps another issue is that the basic syntax is so different from the C-language syntax that is common amongst all of the programming languages I use:  C++, Perl, Obj-C, Assembler, and Verilog.  (Well I guess Assembler is different, but it ties right in their with C with the memory layout.)  I really need to dive in and solve a problem that I’ve solved in C++ so that I can see the bigger picture.  All of the talk about “funs” and pattern-matching and what not is not helping.  The section on dealing with binary data is mind blowing in its own way.  Bit vectors can be 9 bits in length!  I don’t think I’ve ever really considered anything but multiples of eight.  I just need to be patient and keep reading until I get to TCP sockets.

It has certainly been a very enlightening way to look at writing software thus far.  It is interesting to see a totally different approach to what I have grown accustomed to with OOP and imperative programming styles.  More to come in the future, I hope!