No speed improvement to speak of, but this allows further experiments
#define ROUNDUP(x,y) ((((x)+(y)-1)/(y))*(y))
#define ROUNDUP(x,y) ((((x)+(y)-1)/(y))*(y))
+
+typedef __uint32_t bitfield_type;
+
#define BIT_SET(set, d) \
#define BIT_SET(set, d) \
- ( (void) ( set[d >> 3] |= (1 << (d & 7)) ) )
+ ( (void) ( set[d >> 5] |= (1 << (d & 31)) ) )
#define BIT_ISSET(set, d) \
#define BIT_ISSET(set, d) \
- (!(! ( set[d >> 3] & (1 << (d & 7)) ) ))
+ (!(! ( set[d >> 5] & (1 << (d & 31)) ) ))
-int ANY_BITS_SET(unsigned char *set, size_t bytes)
+int ANY_BITS_SET(bitfield_type *set, size_t elems)
- for (i = 0; i < bytes; i++)
+ for (i = 0; i < elems; i++)
if (set[i] != 0)
return 1;
if (set[i] != 0)
return 1;
- unsigned char *titles_seen;
- unsigned char *titles_prev_round;
- unsigned char *titles_this_round;
- size_t titles_bitfield_len;
+ bitfield_type *titles_seen;
+ bitfield_type *titles_prev_round;
+ bitfield_type *titles_this_round;
+ size_t titles_bitfield_elems;
+ size_t titles_bitfield_bytes;
printf("\n\n\n\nBuilding table of distances...\n\n");
printf("\n\n\n\nBuilding table of distances...\n\n");
- titles_bitfield_len = ROUNDUP(titles / 8, sizeof(size_t));
+ titles_bitfield_elems = ROUNDUP(titles / 8 / sizeof(bitfield_type), sizeof(bitfield_type));
+ titles_bitfield_bytes = titles_bitfield_elems * sizeof(bitfield_type);
- titles_seen = calloc(titles_bitfield_len, 1);
+ titles_seen = calloc(titles_bitfield_bytes, 1);
titles_prev_round = NULL;
titles_prev_round = NULL;
- titles_this_round = calloc(titles_bitfield_len, 1);
+ titles_this_round = calloc(titles_bitfield_bytes, 1);
cur_dist = 0;
BIT_SET(titles_seen, title_id);
BIT_SET(titles_this_round, title_id);
cur_dist = 0;
BIT_SET(titles_seen, title_id);
BIT_SET(titles_this_round, title_id);
- while (ANY_BITS_SET(titles_this_round, titles_bitfield_len)) {
+ while (ANY_BITS_SET(titles_this_round, titles_bitfield_elems)) {
free(titles_prev_round); /* free is safe to call on NULL */
titles_prev_round = titles_this_round;
free(titles_prev_round); /* free is safe to call on NULL */
titles_prev_round = titles_this_round;
- titles_this_round = calloc(titles_bitfield_len, 1);
+ titles_this_round = calloc(titles_bitfield_bytes, 1);
for (i = 0; i < titles; i++) {
int j;
for (i = 0; i < titles; i++) {
int j;
- for (i = 0; i < titles_bitfield_len; i++) {
+ for (i = 0; i < titles_bitfield_elems; i++) {
titles_this_round[i] &= ~titles_seen[i];
titles_seen[i] |= titles_this_round[i];
}
titles_this_round[i] &= ~titles_seen[i];
titles_seen[i] |= titles_this_round[i];
}