My first Erlang module (part 2)

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 🙂
Advertisements

Erlang process spawning performance

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

Clarification on modules

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!

An advert you don’t see every day

I found an interesting advert in the back of the Economist newspaper this past week.  You might not see this in the American printing, but there is no trade embargo in Singapore where my subscription is printed (sorry for the image quality, but if you can read the title area it is plenty):

3G license up for sale in Iran
3G license up for sale in Iran

Iran is auctioning a 3G license and they are calling for expression of interest.  I found it very interesting because, 1) I’ve never seen such an add in a newspaper before, and 2) it costs €20,000 to submit an expression of interest! I guess this is why only the “big boys” of the telecom world can step up and bid for licenses.

My first Erlang module (part 1)

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 0x1021 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 0x1021.

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.

Joe Armstrong Interviews: Erlang and FPGAs

I’m trying to learn Erlang, so when I found MSDN’s interviews (part I, part II) with Joe Armstrong I could not wait to listen.  Anyone interested in listening to intelligent computer scientists have a casual conversation about functional programming concepts should definitely watch them both.  Listening to Mr. Armstrong talk about the concepts behind Erlang and the type of problems it addresses really helped me to understand some fundamental things about Erlang.  As Erik Meijer mentioned, after initially learning imperative programming styles with assembly language and C, trying to force my mind into the functional programming mode is not easy task. 

However, I was really impressed with Mr. Armstrong’s knowledge of FPGAs and reconfigurable computing.  FPGAs are wonderful tools and it was nice to see a computer scientist interested in the possibilities of FPGAs.  They are still really expensive devices though; in Japan, for small lots, Xilinx sells their Virtex5 FPGA for around US$4000, and Altera sells their Stratix-II FPGA for around US$6000.  As such, FPGAs are usually considered in the realm of hardware design prototyping and communications systems.  I mostly use them to bridging different components together such as DSPs, ADCs, DACs and the PCI bus.  These days you can even program PowerPC or ARM CPU cores into an FPGA, it is really amazing.  One day I hope I’ll get the chance to implement some DSP applications in an FPGA–someday I can escape from being a “bit plumber”!  

So what does this have to do with Erlang?  Programming FPGAs in VHDL or Verilog requires a different style of thinking compared to most modeling.  In fact, hardware modeling resembles Erlang in many respects now that I think of it: processes run in parallel and send data over buses to exchange data.  Check it out yourself if you don’t believe me.