From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Sven Eckelmann Date: Mon, 28 Feb 2011 13:03:05 +0100 References: <201102241123.43797.sven@narfation.org> In-Reply-To: MIME-Version: 1.0 Content-Type: multipart/signed; boundary="nextPart6491252.mOOETj69o6"; protocol="application/pgp-signature"; micalg=pgp-sha512 Content-Transfer-Encoding: 7bit Message-Id: <201102281303.07122.sven@narfation.org> Subject: Re: [B.A.T.M.A.N.] BATMAN routing Reply-To: The list for a Better Approach To Mobile Ad-hoc Networking List-Id: The list for a Better Approach To Mobile Ad-hoc Networking List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: hlabishi kobo Cc: b.a.t.m.a.n@lists.open-mesh.org --nextPart6491252.mOOETj69o6 Content-Type: Text/Plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Small clarification at the beginning. In my example I said "received every = 8th=20 ogm". Of course this should have been every 64th ogm. I wanted to write a m= ore=20 detailed example using the 8 bytes but thrown that idea away quite early. I= n=20 the current setup you will have 64 bits in either a single unsigned long or= 64=20 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=20 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 =3D=3D Hamming weight for an unsigned long (sum of bits !=3D 0= ) [1] So what you want is to program it using bit shifts, ands and test operation= s.=20 This means that you will calculate for the maximum (all ogms received) usin= g=20 your current strategy 2016 ([n+(n-1)]/2; n =3D=3D number of bits). This of = course=20 is generated by looking at the bits and not at the bytes like your current= =20 implementation. The sum is even because you omit the last received ogm (in= =20 your version it has an index of 0). And it is even a bigger problem that yo= u=20 would give the ogms which are more recent a smaller weight than the ogms wh= ich=20 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=20 bit_packet_count. The weights are distributed over 64 slots (the bits) were= 1=20 is the weight for the oldest slot and 64 is the weight for the slot of newe= st=20 ogm. The weights are distributed in a linear fashion (second newest has wei= ght=20 63, ...). What would be the weighted sum (64 bit implementation) for=20 {0xCEED2866E2DEE707} and what would be the weighted sum (32 bit=20 implementation) of {3806258951, 3471648870}? Write a program which calculat= es=20 those sums. Proof that this can or cannot be implemented in less operations= =20 per long using clever bit operations which evaluate more than one bit per=20 round. Best regards, Sven --nextPart6491252.mOOETj69o6 Content-Type: application/pgp-signature; name=signature.asc Content-Description: This is a digitally signed message part. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) iQIcBAABCgAGBQJNa476AAoJEF2HCgfBJntGXJwP/iU6Q9rvi/4WkqMdI1u32SF/ xRlXt/VFqmufAB8nV+xhYWcl/+UJHN5BLnXhyiNkhfkkW6OGayjc24o9dKc1jUyX +5XTjFas0foxcvc/TaMdsovDKhqxfznqvIFIS7i9hfOZ3orzpYUCAoj3OG0y4GnT K23ww+cI8mgI10MLoRdI9dwrnxuh+OQCMg1V+6heccxv7DQ3lKClypfhCnJeA9pb yCpka0TZzjqMTmHlvvppsRE0YUpttgfMHw98QuP5FqzXL8CWOET47k9XXy4SaVNk 2CHRuf/cwyU4bdzZzincJsUqyXx9HiROgsOXj5rx6wxmWjzacYpAHEsmCo5DQHQV qiXi3bPlOorpcRkP8QCZ1GqG6CQBBvf6Fa2byEFFMrbCkM1NQIimMbCx+DFZ7BMy 9yxPCTr4cRyWWJ18ebQWorePATYOXzUVYuiP9qVaOVhRO7Ve+R2JZFr4B3vySfMA ZD8mi3LN6yssvqTbiDEuVbYxnaN+qwWObECSvC1gcWrI6R84yl33ZLlrK74Sld84 ek2/wiVLhE7+sXRgOPRZZbK/d89fPobGAeXDHmKVKPVgVCk2nrH7X92OVE6mdO+m sbkjTIIE9FegtfFMKXu4/EA1lPrkqLYy3fqZ53p/TugiA5cMQOIVZ5EOdV+2PNIZ wv3Y5ZLcKuZEqDiPdhRD =b4O2 -----END PGP SIGNATURE----- --nextPart6491252.mOOETj69o6--