5
\$\begingroup\$

I'm training a bit with C, and I'm trying to build a bit array. I would like to have some comments about my code, because I'm not sure that it's the best way to do it.

// BAL.c

#include <assert.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include "BAL.h"

#define BAL_Mask(n)     (1 << ((n) % CHAR_BIT))
#define BAL_Convert(n)      ((n) / CHAR_BIT)

void
BAL_And(BAL_Array *p, BAL_Array *q)
{
    assert(p != NULL);
    assert(q != NULL);

    for (size_t i = 0; i < p->nBits; ++i)
        p->pBits[i] &= q->pBits[i];
}

_Bool
BAL_Any(BAL_Array *p)
{
    assert(p != NULL);

    for (size_t i = 0; i < p->nBits; ++i) {
        if (BAL_Get(p, i) != 0)
            return 1;
    }
    return 0;
}

_Bool
BAL_Compar(BAL_Array *p, BAL_Array *q)
{
    assert(p != NULL);
    assert(q != NULL);

    if (p->nSize != q->nSize)   
        return 0;

    for (size_t i = p->nBits; i > 0; --i) {
        if (BAL_Get(p, i) != BAL_Get(q, i))
            return 0;
    }
    return 1;
}

size_t
BAL_Count(BAL_Array *p)
{
    assert(p != NULL);

    size_t n = 0;

    for (size_t i = 0; i < p->nBits; ++i) {
        if (BAL_Get(p, i) != 0)
            ++n;
    }
    return n;
}

void
BAL_End(BAL_Array *p)
{
    assert(p != NULL);  

    free(p->pBits);
    free(p);
}

inline unsigned char
BAL_Get(BAL_Array *p, size_t i)
{
    assert(p != NULL);
    assert(i <= p->nBits);

    return p->pBits[BAL_Convert(i)] & BAL_Mask(i);
}

inline size_t
BAL_GetSize(BAL_Array *p)
{
    assert(p != NULL);

    return p->nBits;
}

BAL_Array *
BAL_Init(size_t n)
{
    assert(n > 0);

    BAL_Array *p = malloc(sizeof *p);

    assert(p != NULL);

    p->nSize = BAL_Convert(n + CHAR_BIT - 1);
    p->pBits = calloc(p->nSize, 1);
    p->nBits = n;
    return p;
}

BAL_Array *
BAL_Load(const char *s)
{
    assert(s != NULL);

    size_t size     = strlen(s);
    BAL_Array *pRet = BAL_Init(size);

    for (size_t i = 0; i < size; ++i) {
        if (s[i] == '1')
            BAL_Set(pRet, i);
    }
    return pRet;
}

void
BAL_LShift(BAL_Array *p, size_t m)
{
    assert(p != NULL);

    for (size_t i = 0; i < p->nBits; ++i) {
        p->pBits[i] >>= m;
        p->pBits[i] |= BAL_Get(p, i + 1) ? 1 : 0;
    }
}

void
BAL_Not(BAL_Array *p)
{
    assert(p != NULL);

    for (size_t i = 0; i < p->nBits; ++i)
        p->pBits[i] = ~p->pBits[i]; 
}


void
BAL_Or(BAL_Array *p, BAL_Array *q)
{
    assert(p != NULL);
    assert(q != NULL);

    for (size_t i = 0; i < p->nBits; ++i)
        p->pBits[i] |= q->pBits[i]; 
}

void 
BAL_Print(BAL_Array *p, unsigned char *pOut, size_t nMax) 
{
    assert(p != NULL);
    assert(pOut != NULL);

    size_t i;

    for (i = 0; i < p->nBits && i < nMax; ++i)
        pOut[i] = BAL_Get(p, i) ? '1' : '0';
    pOut[i] = '\0';
}

inline void
BAL_Reset(BAL_Array *p, size_t i)
{
    assert(p != NULL);
    assert(i <= p->nBits);

    p->pBits[BAL_Convert(i)] &= ~BAL_Mask(i); 
}

void
BAL_RShift(BAL_Array *p, size_t m)
{
    assert(p != NULL);

    for (size_t i = 0; i < p->nSize; ++i) {
        p->pBits[i] <<= m;
        p->pBits[i] |= BAL_Get(p, i + 1) ? 1 : 0;
    }
}

inline void
BAL_Set(BAL_Array *p, size_t i)
{
    assert(p != NULL);
    assert(i <= p->nBits);

    p->pBits[BAL_Convert(i)] |= BAL_Mask(i);
}

void
BAL_Xor(BAL_Array *p, BAL_Array *q)
{
    assert(p != NULL);
    assert(q != NULL);

    for (size_t i = 0; i < p->nBits; ++i)
        p->pBits[i] ^= q->pBits[i]; 
}

Header file :

// BAL.h

#ifndef BAL_H
#define BAL_H

typedef struct {
    unsigned char   *pBits;
    size_t           nSize;
    size_t           nBits;
} BAL_Array;

void          BAL_And     (BAL_Array *, BAL_Array *);
_Bool         BAL_Any     (BAL_Array *);
_Bool         BAL_Compar  (BAL_Array *, BAL_Array *);
size_t        BAL_Count   (BAL_Array *);
void          BAL_End     (BAL_Array *);
unsigned char BAL_Get     (BAL_Array *, size_t);
size_t        BAL_GetSize (BAL_Array *);
BAL_Array    *BAL_Init    (size_t);
BAL_Array    *BAL_Load    (const char *);
void          BAL_LShift  (BAL_Array *, size_t);
void          BAL_Not     (BAL_Array *);
void          BAL_Or      (BAL_Array *, BAL_Array *);
void          BAL_Print   (BAL_Array *, unsigned char *, size_t);
void          BAL_Reset   (BAL_Array *, size_t);
void          BAL_RShift  (BAL_Array *, size_t);
void          BAL_Set     (BAL_Array *, size_t);
void          BAL_Xor     (BAL_Array *, BAL_Array *);

#endif /* BAL_H */
\$\endgroup\$
  • 2
    \$\begingroup\$ Sorry, I don't have the time to write a full review but I have one thing to say. Assertions are not a replacement for error checking. As these functions are being exported, you should not be using assert here. You should come up with a mechanism to indicate an error. Make your void methods return int (or _Bool in your case) returning "true" when successful or "false" on failure. Come up with an "error code" to indicate what problem comes up or something similar if you want to convey that information to the programmer. \$\endgroup\$ – Jeff Mercado Jun 23 '12 at 20:54
  • \$\begingroup\$ Assertions are useful here, because I'm not in the production phase. But I'm going to delete them soon. Thanks anyway for your comment. \$\endgroup\$ – Lucas Pesenti Jun 24 '12 at 8:30
5
\$\begingroup\$

Quite clean implementation, but some remarks:

  1. The header shouldn't compile. It references size_t, but doesn't include stdlib.h.

  2. BAL_Any can be faster if you just compare the characters in the pBits array to zero, you don't need to check each individual bit. Same with BAL_Compar.

  3. Any particular reason why you denied BAL_Compar that last 'e'?

  4. strlen is unsafe. Consider adding a size argument to BAL_Load so the user is responsible for passing the right size. This also enables the use of BAL_Load with substrings.

  5. Do you want BAL_Load to make "1000" from, say, "1337" and "1ABC"?

  6. As Jeff Mercado already said, asserts aren't the best way for error handling, especially for errors the caller didn't cause. Checking for null pointers is ok, but your BAL_Init and BAL_Load should return NULL if an error occured. That way, the caller can at least try to recover.

  7. I'm missing a BAL_Toggle.

  8. You should consider moving the struct definition into the implementation file. You only use pointers to it, so you can just as well make it opaque. That way, you can change the implementation (i.e. struct-layout) of the array without having to recompile everything that included the header.

\$\endgroup\$
3
\$\begingroup\$

Unless I'm misreading something (and there's a very good chance that I am), there's quite a nasty overflow:

void
BAL_And(BAL_Array *p, BAL_Array *q)
{
    assert(p != NULL);
    assert(q != NULL);

    //p->nSize is the number of bytes allocated (as shown in the calloc call)
    //and p->nBits is the number of bits present
    //So unless p->nBits == p->nSize this is an overflow
    for (size_t i = 0; i < p->nBits; ++i)
        p->pBits[i] &= q->pBits[i];
}

Also, there's an optimization opportunity in a lot of places if you're willing to make your code ugly in a few places. For example, in BAL_Compar, the individual bits only need to be compared for the last unsigned char. For all other unsigned char you can just compare them directly and save a bit of arithmetic.

\$\endgroup\$
0
\$\begingroup\$

Here:

void
BAL_And(BAL_Array *p, BAL_Array *q)
{
    assert(p != NULL);
    assert(q != NULL);

    for (size_t i = 0; i < p->nBits; ++i)
        p->pBits[i] &= q->pBits[i];
}

here:

void
BAL_Xor(BAL_Array *p, BAL_Array *q)

and here:

void
BAL_Or(BAL_Array *p, BAL_Array *q)

Here if p and q have different nSizes, and p is the bigger one, than you read from an unallocated memory/rest of the q struct.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.