C - BitArray 分段错误

Question

我目前正在尝试使用 BitSet 在 C 中实现埃拉托色尼筛法，但是当我尝试筛选高达 1,000,000（100 万）- 100,000（100,000）个素数时出现分段错误虽然仍在工作，但我不明白为什么会出现段错误。

这是我使用的代码（我标记了发生错误的行）：

#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);
}

有人知道为什么会出现这个错误吗？我猜现在已经分配了足够的 space（不知何故），但我现在看不出这是怎么可能的...

Answer 1

你用 calloc 分配 X bytes，将总数除以 sizeof(prime_t)，但表现得好像你有空间给 X prime_t 稍后的元素。

编辑：或者实际上，您正在分配一个大小为 X 的 1 元素数组。

如果你想像现在这样使用它，你应该这样做：

calloc(X, sizeof(prime_t)) 代替。

编辑：代码中的另一个主要问题是您使用的是字节级索引而不是位级索引。

请注意 prime_t 中有 sizeof(prime_t) * 8 位，因此在每个字节中您都设置了 1 位，为真。索引时除以 sizeof(prime_t) 而不是 (sizeof(prime_t) * 8)。

Answer 2

您没有得到正确的位数：

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

做除法和mod时，需要divide/mod位数，而不是位数字节:

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

同样地：

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)

编辑：

您也没有分配正确的内存量。您需要的字节数等于限制 除以位数 ，加上 1 sizeof(prime_t) 以向上舍入。

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

就像现在一样，您分配的字节数是您需要的两倍。

另外，如果你想防范一个字节多于或少于 8 位的情况，请在上面的代码中使用 CHAR_BIT 代替 8。 sizeof(uint64_t) 的计算结果无关紧要，因为您仍然可以获得所需的正确位数。

C - BitArray 分段错误

C - BitArray Segmentation Fault

c

segmentation-fault

sieve-of-eratosthenes

dynamic-memory-allocation

bit-fields