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.

About these ads

4 Responses to My first Erlang module (part 1)

  1. wtfftw says:

    The Calculation overflow errors that you’re reporting are due to the fact that you are using Erlang’s built in arbitrary precision Integers, and not fixed width bitstrings like you want. An easy solution would be to replace the ints with bitstrings, or use bitstrings to lop off the proper number of digits. If you dig in the libs, you can probably find a encode/decode function pair to get the number of bytes you want out of an int.

  2. dsmith says:

    Hmm. It looks like the algorithm expects a fixed 16-bit register where the overflow bits are discarded.

    Erlang integers are arbitrary length and will not discard overflow bits. Did you try to band the result of calculate with with 16#FFFF?

  3. I fixed the overflow bug simply using band as in your code already:

    calculate(X) ->
    zcalculate(X) band 16#ffff.

    zcalculate(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).

  4. globalengineer says:

    dsmith:

    I tried assigning the output of inner_loop() to a variable Val, and then using “Val band 16#FFFF.” at the end of the function for the return vaule. However, I was still getting overflow.

    Rudi,

    Thank you very much, your solution did the trick in fixing the problem when using integers!

    wtfftw,

    That is a good solution too. I do plan to move this algorithm over to bitfields in the next stage. I need to read more about bitfields first. :-)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.