C - BitArray Segmentation Fault

Question

I'm currently trying to implement the Sieve of Eratosthenes in C using a BitSet, but I get a segmentation fault, when I try to sieve the primes up to 1,000,000 (1 million) - 100,000 (100 thousand) is still working though and I can't figure out why I get the seg-fault.

This is the code I use (I marked the line, in which the error occurs):

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>

void eSieve(uint64_t upperLimit);
int main(int argc, char *argv[]) {
  uint64_t upperLimit;

  if (argc == 2) {
    upperLimit = (uint64_t) atoll(argv[1]);
    printf("Using custom limit: %" PRIu64 "\n", upperLimit);
  } else {
    upperLimit = 1000;
    printf("Using default limit: %" PRIu64 "\n", upperLimit);
  }

  eSieve(upperLimit);

  return 0;
}

typedef uint32_t prime_t;

void eSieve(uint64_t upperLimit) {
  if (upperLimit < 2) {
    printf("FAILURE: Bad upper limit.\n");
    return;
  }

  prime_t *sieve = calloc(1, (upperLimit + sizeof(prime_t) - 1)/sizeof(prime_t));

  if (!sieve) {
    printf("FAILURE: Could not initialize sieve.\n");
    return;
  }

  sieve[0] |= 3;    // Set first and second bit (representing 0 and 1)

  uint64_t prime, number;
  for (prime = 2; prime * prime < upperLimit; ) {
    for (number = prime * prime; number < upperLimit; number += prime) {
      // Segmentation fault for prime = 2 and number = 258048
      sieve[number/sizeof(prime_t)] |= (((prime_t) 1) << (number % sizeof(prime_t)));
    }

    while ((sieve[++prime/sizeof(prime_t)] & (prime_t)1 << (prime % sizeof(prime_t))) != 0)
      ;
  }

  number = upperLimit;
  while ((sieve[--number/sizeof(prime_t)] & (((prime_t)1) << (number % sizeof(prime_t)))) != 0)
    ;

  printf("Greatest prime-number below %" PRIu64 ": %" PRIu64 "\n", 
      upperLimit, number);
}

Does anybody know why the error occurs? I'm guessing that now enough space is allocated (somehow), but I can't see how this would be possible at the moment...

Answer 1

You're not getting the correct bit number:

sieve[number/sizeof(prime_t)] |= (((prime_t) 1) << (number % sizeof(prime_t)));

When you do the division and mod, you need to divide/mod by the number of bits, not the number of bytes:

sieve[number/(sizeof(prime_t)*8)] |= (((prime_t) 1) << (number % (sizeof(prime_t)*8)));

And similarly:

while ((sieve[++prime/(sizeof(prime_t)*8)] & (prime_t)1 << (prime % (sizeof(prime_t)*8))) != 0)

...

while ((sieve[--number/(sizeof(prime_t)*8)] & (((prime_t)1) << (number % (sizeof(prime_t)*8)))) != 0)

EDIT:

You're also not allocating the right amount of memory. You need a number of bytes equal to the limit divided by the number of bits, plus 1 sizeof(prime_t) to round up.

prime_t *sieve = calloc(1, (upperLimit / 8) + sizeof(prime_t));

As it right now, you're allocating twice the bytes you need.

Also, if you want to defend against cases where there are more or less than 8 bits to a byte, use CHAR_BIT in the above code in place of 8. Whatever sizeof(uint64_t) evaluates to shouldn't matter, as you'll still get the proper number of bits required.

Answer 2

You allocate X bytes with calloc, dividing the total by sizeof(prime_t), yet act as if you have room for X prime_t elements later on.

Edit: Or actually even, you are allocating an array of 1 element with size X.

If you want to do it the way you are using it now, you should do:

calloc(X, sizeof(prime_t)) instead.

Edit: The major other issue in your code is that you are using byte-level indexing instead of bit-level.

Note that there are sizeof(prime_t) * 8 bits in a prime_t, so in every byte you set exactly 1 bit, true. You divide by sizeof(prime_t) instead of (sizeof(prime_t) * 8) when indexing.