Author: marek Date: 2010-07-22 17:32:00 +0200 (Thu, 22 Jul 2010) New Revision: 1740
Modified: trunk/batman-adv/bitarray.c trunk/batman-adv/bitarray.h Log: batman-adv: Calculate hamming weight using optimized kernel functions
The Kernighan algorithm is not able to calculate the number of set bits in parallel and the compiler cannot replace it with optimized instructions.
The kernel provides specialised functions for each cpu which can either use a software implementation or hardware instruction depending on the target cpu.
Reported-by: David S. Miller davem@davemloft.net Signed-off-by: Sven Eckelmann sven.eckelmann@gmx.de
Modified: trunk/batman-adv/bitarray.c =================================================================== --- trunk/batman-adv/bitarray.c 2010-07-22 15:31:59 UTC (rev 1739) +++ trunk/batman-adv/bitarray.c 2010-07-22 15:32:00 UTC (rev 1740) @@ -22,6 +22,8 @@ #include "main.h" #include "bitarray.h"
+#include <linux/bitops.h> + /* returns true if the corresponding bit in the given seq_bits indicates true * and curr_seqno is within range of last_seqno */ uint8_t get_bit_status(TYPE_OF_WORD *seq_bits, uint32_t last_seqno, @@ -187,21 +189,14 @@ }
/* count the hamming weight, how many good packets did we receive? just count - * the 1's. The inner loop uses the Kernighan algorithm, see - * http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan + * the 1's. */ int bit_packet_count(TYPE_OF_WORD *seq_bits) { int i, hamming = 0; - TYPE_OF_WORD word;
- for (i = 0; i < NUM_WORDS; i++) { - word = seq_bits[i]; + for (i = 0; i < NUM_WORDS; i++) + hamming += hweight_long(seq_bits[i]);
- while (word) { - word &= word-1; - hamming++; - } - } return hamming; }
Modified: trunk/batman-adv/bitarray.h =================================================================== --- trunk/batman-adv/bitarray.h 2010-07-22 15:31:59 UTC (rev 1739) +++ trunk/batman-adv/bitarray.h 2010-07-22 15:32:00 UTC (rev 1740) @@ -22,7 +22,8 @@ #ifndef _NET_BATMAN_ADV_BITARRAY_H_ #define _NET_BATMAN_ADV_BITARRAY_H_
-/* you should choose something big, if you don't want to waste cpu */ +/* you should choose something big, if you don't want to waste cpu + and keep the type in sync with bit_packet_count */ #define TYPE_OF_WORD unsigned long #define WORD_BIT_SIZE (sizeof(TYPE_OF_WORD) * 8)