Skip to content

Instantly share code, notes, and snippets.

@chichur
Created May 9, 2022 11:44
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save chichur/88fe98659b9c561e6167e597217ad674 to your computer and use it in GitHub Desktop.
Save chichur/88fe98659b9c561e6167e597217ad674 to your computer and use it in GitHub Desktop.
#include <time.h>
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define C55 0x5555555555555555ULL
#define C33 0x3333333333333333ULL
#define C0F 0x0f0f0f0f0f0f0f0fULL
#define C01 0x0101010101010101ULL
int count_bytes(unsigned char byte) {
return (byte & 1) +
((byte & 2) >> 1) +
((byte & 4) >> 2) +
((byte & 8) >> 3) +
((byte & 16) >> 4) +
((byte & 32) >> 5) +
((byte & 64) >> 6) +
((byte & 128) >> 7);
}
int main(int argc, char *argv[]) {
FILE *fp;
char *line = (char *) malloc(17);
char *oct = (char *) malloc(4);
unsigned long long idx;
unsigned long long *bitmap = (unsigned long long *) calloc
(sizeof(unsigned long long) * 67108864, 1);
clock_t begin = clock();
fp = fopen(argv[1], "r");
while (fgets(line, 17, fp)) {
register char *temp = line;
register char *buf_oct = oct;
idx = 0;
while (*temp) {
if (*temp == '.') {
*buf_oct = '\0';
buf_oct = oct;
idx = (idx << 8) | (unsigned char) atoi(oct);
temp++;
}
*buf_oct++ = *temp++;
}
*buf_oct = '\0';
idx = (idx << 8) | (unsigned char) atoi(oct);
bitmap[idx / 64] |= (unsigned long long) 1 << (idx % 64);
}
int cnt = 0;
for (int i = 0; i < 67108864; ++i) {
unsigned long long chunk = bitmap[i];
chunk -= (chunk >> 1) & C55; // put count of each 2 bits into those 2 bits
chunk = (chunk & C33) + ((chunk >> 2) & C33);// put count of each 4 bits into those 4 bits
chunk = (chunk + (chunk >> 4)) & C0F; // put count of each 8 bits into those 8 bits
chunk = (chunk * C01) >> 56;
cnt += (int) chunk;
}
clock_t end = clock();
double time_spent = (double) (end - begin) / CLOCKS_PER_SEC;
printf("Time execution: %f seconds; ip: %d\n", time_spent, cnt);
free(line);
free(oct);
free(bitmap);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment