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.