Re: [B.A.T.M.A.N.] BATMAN routing

[Sven Eckelmann <sven@narfation.org>]

[-- Attachment #1: Type: Text/Plain, Size: 2170 bytes --]

Small clarification at the beginning. In my example I said "received every 8th 
ogm". Of course this should have been every 64th ogm. I wanted to write a more 
detailed example using the 8 bytes but thrown that idea away quite early. In 
the current setup you will have 64 bits in either a single unsigned long or 64 
bits in 2 32-bit unsigned longs. This depends on the target architecture.

Please keep in mind that this can easily increased to 256 or more bits for the 
TQ_LOCAL_WINDOW_SIZE

hlabishi kobo wrote:
> Thanks for the reply, what does hweight_long does? i tried to search
> it but i cant find a clear description of it. My intention is to count
> and add the indexes where an OGM was recorded (where there is a '1' ).

hweight_long == Hamming weight for an unsigned long (sum of bits != 0) [1]

So what you want is to program it using bit shifts, ands and test operations. 
This means that you will calculate for the maximum (all ogms received) using 
your current strategy 2016 ([n+(n-1)]/2; n == number of bits). This of course 
is generated by looking at the bits and not at the bytes like your current 
implementation. The sum is even because you omit the last received ogm (in 
your version it has an index of 0). And it is even a bigger problem that you 
would give the ogms which are more recent a smaller weight than the ogms which 
are received in the past.

I hope that these are enough hints for you.

So lets assume that you implemented a correct weighted version of 
bit_packet_count. The weights are distributed over 64 slots (the bits) were 1 
is the weight for the oldest slot and 64 is the weight for the slot of newest 
ogm. The weights are distributed in a linear fashion (second newest has weight 
63, ...).

What would be the weighted sum (64 bit implementation) for 
{0xCEED2866E2DEE707} and what would be the weighted sum (32 bit 
implementation) of {3806258951, 3471648870}? Write a program which calculates 
those sums. Proof that this can or cannot be implemented in less operations 
per long using clever bit operations which evaluate more than one bit per 
round.

Best regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]