Traversing a binary

Javier París Fernández <>
Tue Sep 21 23:22:04 CEST 2004


On Tue, Sep 21, 2004 at 10:52:09PM +0200, Erik Stenman wrote:
>    I'm no Tcp expert, but are you sure?
>    Is it not defined as the 16-bit 1's complement sum?
>    I.e. something like:
>    '+'(A,B) ->
>        S = A + B,
>        S band 16#ffff + (S bsr 16).

It is as you say. I didn't post all the code, only the part that looped
through the binary. I only add the carry at the end, as the result is
the same.

>    One problem with your code is that it generates bignums (heap-allocated
>    large integers),
>    but if it is the 16-bit 1's complement sum, then you don't need large
>    integers.

I assume that a bignum is an integer bigger than the word size of the
machine (Correct me if i'm wrong). I don't think i can have a checksum
bigger than 4Gb. The biggest packet i may have is 64Kb (Because of ip).
So, in the worst case there would be 2^15 two byte pairs. If all are
16#ffff that would add to 2^31, which fits in the 32 bits machine word.

>    You could also traverse the binary without creating new sub-binaries, by
>    keeping
>    track of how many byte-pairs you have seen (N):
> 
>    c(N,Bin,Csum) ->
>        case Bin of
>        <<_:N/binary, Num:16/integer,_/binary>> ->
>            c(N+2,Bin,'+'(Csum,Num));
>            <<_:N/binary, Num:8/integer>> ->
>            '+'(Csum,Num bsl 8);
>        _ -> Csum
>        end.

That's something i hadn't think about. Seems a good idea.

>    Unfortunately even with these two changes the code does not become much
>    faster...
>    I have attached a test program that calculates the checksum in 4 different
>    ways,
>    and prints the execution times in microseconds, but the function c/3 above
>    is the fastest.

I'll try it then. Maybe it's fast enough.

Thanks!




More information about the erlang-questions mailing list