Bill Parker created BIT-1424: -------------------------------- Summary: Add power of 2 test to file(s) 'cq.c/cq.h' (revises BIT-1423) Key: BIT-1424 URL: https://bro-tracker.atlassian.net/browse/BIT-1424 Project: Bro Issue Tracker Issue Type: New Feature Components: Bro Affects Versions: 2.3 Environment: Enhancement Request in file cq.c Reporter: Bill Parker Attachments: cq.c.patch, cq.h.patch
Subj: Add power of 2 test to file(s) 'cq.c/cq.h' (revised) *This replaces the cq.c code/patch in BIT-1423..*. Hello All, Here is a hunk of code which is a FIXME to the following statement: /* XXX could check that nbuckets is a power of 2 */ In directory 'src', file 'cq.c' The patch file which adds this test is below: --- cq.c.orig 2015-06-06 19:01:58.220926680 -0700 +++ cq.c 2015-06-08 18:36:37.323755402 -0700 @@ -414,6 +414,15 @@ return hp->max_qlen; } +int cq_IsPowerOfTwo(unsigned int x) +{ + /* This function returns one (1) if val is a power of 2, i.e. */ + /* 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024...2^31 */ + /* or zero (0) if it isn't a power of two */ + + return ((x != 0) && ((x & (~x + 1)) == x)); +} + /* Return without doing anything if we fail to allocate a new bucket array */ static int cq_resize(register struct cq_handle *hp, register int grow) @@ -422,6 +431,7 @@ register size_t size; register struct cq_bucket *bp, *bp2, *buckets, *oldbuckets; struct cq_handle savedhandle; + int power_of_2_result; /* for power of two call */ if (hp->noresize) return (0); @@ -444,6 +454,11 @@ /* XXX could check that nbuckets is a power of 2 */ + power_of_2_result = cq_IsPowerOfTwo((unsigned int)nbuckets); + + if (power_of_2_result == 0) /* If this is zero, nbuckets is NOT a power of 2 */ + return (-1); /* do we need to print a warning/error here as well? */ + size = sizeof(*buckets) * nbuckets; buckets = (struct cq_bucket *)malloc(size); memory_allocation += size; ==================================================================== The function above is a one-liner that can be found on the Web. The first half of the expression ensures that x is a positive integer. The second half of the expression, (x & (~x + 1)) == x, is true only when x is a power of two. It compares x with its two’s complement. The two’s complement of x is computed with ~x + 1, which inverts the bits of x and adds 1 (~x + 1 is equivalent to -x, but negation is technically illegal for an unsigned integer). Let n be the position of the leftmost 1 bit if x. If x is a power of two, its lone 1 bit is in position n. This means ~x has a 0 in position n and 1s everywhere else. When 1 is added to ~x, all positions below n become 0 and the 0 at position n becomes 1. In other words, the carry propagates all the way to position n. So what happens is this: negating x inverts all its bits, but adding 1 inverts them back, from position n on down. So, (x & (~x + 1)) == x is true. ==================================================================== Here is the modification to file 'cq.h' which adds the function prototype for cq_IsPowerOfTwo: --- cq.h.orig 2015-06-09 08:35:29.001007785 -0700 +++ cq.h 2015-06-09 08:36:08.194989138 -0700 @@ -5,6 +5,7 @@ void *cq_remove(struct cq_handle *, double, void *); int cq_size(struct cq_handle *); int cq_max_size(struct cq_handle *); +int cq_IsPowerOfTwo(unsigned int); unsigned int cq_memory_allocation(void); #ifdef DEBUG void cq_debug(struct cq_handle *, int); ==================================================================== I am attaching the patch file(s) to this bug report Bill Parker (wp02855 at gmail dot com) -- This message was sent by Atlassian JIRA (v6.5-OD-05-041#65001) _______________________________________________ bro-dev mailing list bro-dev@bro.org http://mailman.icsi.berkeley.edu/mailman/listinfo/bro-dev