| Author |
Message |
< Erlang ~ Bit Syntax and restricting size |
| doctorwatson |
 Posted: Mon Sep 22, 2008 11:50 am |
 |
|
|
Joined: 29 Apr 2008
Posts: 5
|
I'm trying to write code that operates on 16-bit data and I think it just comes down to the fact that I don't understand how to use the bit syntax.
I understand that <<Field:16>> defines a 16-bit value and that "Field" takes up the entire 16-bits. And I understand that I have to define Field as a numerical value first as well. But how can I tell a function to take only sixteen-bit types?
If I have a chain of computations to do that depend on a previous value, how can I make sure that the value coming out of each part is limited to sixteen bits so that I don't get overflow bugs?
I'm coming from C++ where I'm used to defining the data sizes and I'm hitting my head on the wall here. Any help would be GREATLY appreciated. Thank you! |
|
|
| Back to top |
 
|
| dsmith |
| Posted: Mon Sep 22, 2008 11:32 pm |
|
|
|
User
Joined: 08 Aug 2007
Posts: 41
Location: Toronto
|
No, I think this is just the way it works. High order bits are discarded when packing an integer into a binary that is too small. I'm not sure what the rationale was for this. But there have been other who have raised the issue...
http://www.erlang.org/pipermail/erlang-questions/2007-July/027657.html
One way to get this condition to throw is to use an if expression as below.
Code:
1> N=16#10000.
65536
2> if N =< 16#FFFF -> <<N:16>> end.
** exception error: no true branch found when evaluating ...
Or write a function...
Code:
pack16(N) when N =< 16#FFFF ->
<<N:16>>;
pack16(N) ->
throw(overflow).
You say have a chain of operations; do you have more details. The bit-syntax is great for packing and unpacking binaries, but typically I would do my chain of operations on an integer, and then pack it into a binary at the end. What kind of operations are you doing? |
|
|
| Back to top |
|
| doctorwatson |
| Posted: Tue Sep 23, 2008 2:25 am |
|
|
|
Joined: 29 Apr 2008
Posts: 5
|
I'm doing some CRC16 CCITT calculations for a simulator I'm working on for learning purposes.
Here is the code actually:
Code:
%
% CRC16 CCITT implementation based on a lookup table
%
%
-module(crc16).
-export([maketable/0]).
-export([crc16/1]).
-export([test/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).
crc16(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),
crc16(TheRest, UpdatedAcc).
test(X) -> lists:nth(X, ?CRC16LUT).
I have built the equivalent code in C++ and verified it extensively. If I execute crc16([1]), I should be getting back 0xF1D1. With my equivalent Erlang code I get the decimal equivalent of 0xFFE1F. I want to restrict this algorithm to work on only 16 bits but I'm stumped at how to do so.
Eventually I'd like to hand it binary input of a certain bit length and have it do the entire calculation on the block of data. For now, however, I'm just trying to get it to work correctly with regular integer types.
Any pointers and advice would be really helpful. Thanks! |
|
|
| Back to top |
|
| dsmith |
| Posted: Tue Sep 23, 2008 3:33 pm |
|
|
|
User
Joined: 08 Aug 2007
Posts: 41
Location: Toronto
|
I remember seeing this code (at lease the table generating portion) on another blog last week.
The solution is the same as in the table generating case. For any calculation that might cause an overflow (bsl, arithmetic operations) that we want to discard, we need to take the value, say V, and apply V band 16#FFFF.
So your crc16/2 function would look like this...
Code:
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 haven't tried it, and I'm not as familiar with the algorithm as you, but this is the right concept.
Your original post here suggested you are using binaries, whereas the code you posted uses none. I suppose you were just looking at binaries as an alternative to integer. I do think the integer approach as you posted is the right way to go.
One other thing I should point out is that the index lookup won't be quite as efficient as for a C array. Erlang lists are O(N) on lookups and C arrays are O(1). However, your list is relatively small, so it may may be a problem. If performance is a real concern you might want to consider using the array module.
http://www.erlang.org/doc/man/array.html
If you do use the array, you should construct the data structure upfront and pass it through the accumulator function as a parameter. This would avoid reconstructing it each time. Also be aware that the array uses 0 based indexing, whereas the list lookup in 1 based. |
|
|
| Back to top |
|
| doctorwatson |
| Posted: Wed Sep 24, 2008 12:24 am |
|
|
|
Joined: 29 Apr 2008
Posts: 5
|
Yes, that was my blog. And once again your solution does the trick.  Thank you. I recognize your handle now, thanks for your comment on my blog too.
My original goal was to write the code to work with integers and verify the logic and calculations. I was then going to try to convert it to bit-fields as a way of limiting the size. However, from the link you shared as well as further investigation and experimentation, it seems that bit fields are most useful for importing and exporting data through interfaces. Like you said, it seems integers are the best thing for use inside of Erlang modules.
I will look into Erlang arrays, thanks for the information. CRC operations should be quickly performed so O(1) would definitely be preferable. I think that, as well as error handling code, is the next step in developing this module. |
|
|
| Back to top |
|
| wuji |
| Posted: Mon Sep 17, 2012 1:50 am |
|
|
|
User
Joined: 10 Aug 2012
Posts: 654
|
the expense of our villain, Rex, and not at the the cheap authentic jordans the expense of those suffering from the disease."The joke, "From
man to another, I hope you get Lou Gehrig's disease," disease," cheap replica designer *beep* disease," shocked movie-going patients and advocates, who say it crossed
line."I didn't expect to go to a movie and sit sit cheap authentic jordans sit with an audience laughing at the expense of people
ALS," said Randy Pipkin, who was diagnosed in 2005. "I "I [h4]replica designer bags for sale[/h4] "I think the message this film sends out is a
slap in the face to people dying from this horrific horrific [h4]authentic jordans[/h4] horrific disease."Lou Gehrig's disease, also known as ALS, progressively robs
of their ability to move, speak, eat and breathe. There There authentic jordans There is currently no cure.The punch line prompted an online |
|
|
| Back to top |
|
| dongdongwu |
| Posted: Wed Sep 19, 2012 7:38 am |
|
|
|
User
Joined: 19 Sep 2012
Posts: 236
|
| Girls would refuse to even leave their replicas behind. specifically when the product beats the complete meaning of the Christian Louboutin men outlet; in conditions of good quality and detailing.If Cinderella was residing in your twenty primary century as opposed to the aged a single then there would not be any 'Happy actually after'. properly appears like girls nowadays are as well fond of the strong;Christian Louboutin Men Shoes to leave them in your center of nowhere.Christian Louboutin for men Shoes would arrive true handy being a excellent handbag using the glimpse and really feel belonging to the authentic but at a very much lesser price tag adding as very much as types picture in your process. |
|
|
| Back to top |
|
|
|
All times are GMT
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum
|
|
|
Digg It
Del.icio.us
Reddit
Facebook
Stumble Upon
Technorati
