[Bro-Dev] [JIRA] (BIT-1424) Add power of 2 test to file(s) 'cq.c/cq.h' (revises BIT-1423)

[Bill Parker (JIRA)]

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)