0

I'm making my own implementation of a bit array in C based on the java BitSet where they use 64 bit Long type, but in C we can't guarantee a 64 bit integer. I've defined an integer_t where I use it everywhere in my project:

typedef intmax_t integer_t;

The bit array is a buffer of integer_t and the following function will map a bit index to a buffer index:

static integer_t bit_buffer_index(integer_t bit_index)
{
    return bit_index >> bit_shifts;
}

Static because it is an implementation detail. Also bit_shifts is defined in the source file as:

static const integer_t bit_shifts =
          ((sizeof(integer_t) * 8) >> 6) > 0
        ? 6
        : ((sizeof(integer_t) * 8) >> 5) > 0
        ? 5
        : ((sizeof(integer_t) * 8) >> 4) > 0
        ? 4
        : 3; // One byte

But is this the correct approach to define bit_shifts? Is there a macro for this? How would you implement this? It seems like I'm missing something.

  • 3
    Any reason you're not using `uint64_t`? – dbush Dec 10 '18 at 15:05
  • @dbush Yes, I've been getting in a lot of trouble using unsigned values AND I'm using a signed integer to report errors when getting the maximum size of something or NULL references (returning -1). –  Dec 10 '18 at 15:07
  • 1
    be careful : [Arithmetic bit-shift on a signed integer](https://stackoverflow.com/questions/4009885/arithmetic-bit-shift-on-a-signed-integer) – Sander De Dycker Dec 10 '18 at 15:10
  • Thank you @SanderDeDycker. The `bit_buffer_index` is guarded by all functions using it from preventing negative values since a `bit_index` just like any index can't be negative :) –  Dec 10 '18 at 15:16
  • 1
    Have you seen http://c-faq.com/misc/bitsets.html – Jason Brown Dec 10 '18 at 15:25
  • 1
    The sane solution is otherwise to use an array of type `uint8_t [n]`. – Lundin Dec 10 '18 at 15:29
  • Using a signed integer to "report errors" is a super bad plan. The C way of doing this is to take a pointer argument, manipulate in-place, and return a separate error condition. The other approach is to fully embrace "garbage in, garbage out" and just do what you're told, so if invalid arguments are passed in, invalid values come out and it's not your problem. – tadman Dec 10 '18 at 15:33
  • Additionally, C is not in any way Java. In Java you have all these out-of-bounds protections, they're part of the language. In C you're expected to behave sensibly and test *before* calling *if* necessary and not in the call itself. Having these checks within the function and returning error codes for invalid data is often a waste of time and cycles. – tadman Dec 10 '18 at 15:37
  • @tadman How would it be a super bad plan? If I have a function to return the size of a list and if the parameter is NULL then return -1, otherwise return the size of the list. If there is one input parameter and one output, there is no reason to get the resulting size passed in the parameter with a function returning void. –  Dec 10 '18 at 15:42
  • The C way is if the parameter is `NULL` that's **not your problem** and you just let it play out as it will. If that results in a crash, good. Don't allow calling with `NULL`. Document it as undefined behaviour. This can dramatically simplify your code if you are more restrictive of what a valid input is defined as. It's not your job to anticipate all the wildly broken ways your function will be instantiated. If you try and do this you end up with a whole lot of *defensive code* which hides actual bugs. – tadman Dec 10 '18 at 15:43
  • 1
    @tadman I can only take your comment as an opinion if no references are given. –  Dec 10 '18 at 16:08
  • 1
    Understandable, yet it's hard to find a reference to cultural practices that are so ingrained it's like the fish-explaining-water situation. When programming C there's this understanding that you must be disciplined about your calls or you'll get the dreaded undefined behaviour. This is not so in Java where you'll get an exception. These two languages have an entirely different approach to surfacing errors. C++ leans more towards the Java model, it has exceptions, but it's also very much a product of C where you must code correctly or you can't expect it to work at all. – tadman Dec 10 '18 at 16:12

0 Answers0