Project

General

Profile

« Previous | Next » 

Revision 949f122a

Added by David Sorber over 10 years ago

Added a third bit position approach and created a script for making sparse vectors.

View differences:

software/misc/bit_position/bit_position.c
int timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y)
{
/* Perform the carry for the later subtraction by updating y. */
// Perform the carry for the later subtraction by updating yy
if (x->tv_usec < y->tv_usec) {
int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;
y->tv_usec -= 1000000 * nsec;
......
y->tv_usec += 1000000 * nsec;
y->tv_sec -= nsec;
}
/* Compute the time remaining to wait.
tv_usec is certainly positive. */
// Compute the time remaining to wait. tv_usec is certainly positive.
result->tv_sec = x->tv_sec - y->tv_sec;
result->tv_usec = x->tv_usec - y->tv_usec;
/* Return 1 if result is negative. */
// Return 1 if result is negative.
return x->tv_sec < y->tv_sec;
}
......
for (uint32_t idx = 0; idx < count; idx++) {
uint64_t copy = vectors[idx];
printf("Index: %" PRIu32 "\n", idx);
//~ printf("Index: %" PRIu32 "\n", idx);
uint64_t compare = 1;
uint64_t position = 0;
for (uint32_t ctr = 0; ctr < 64; ctr++)
{
if (compare & copy)
{
printf("%" PRIu32 " ", ctr);
uint64_t position = ctr;
//~ printf("%" PRIu32 " ", ctr);
}
compare = (compare << 1);
}
printf("\n\n");
//~ printf("\n\n");
}
}
......
for (uint32_t idx = 0; idx < count; idx++) {
uint64_t copy = vectors[idx];
printf("Index: %" PRIu32 "\n", idx);
//~ printf("Index: %" PRIu32 "\n", idx);
uint64_t position = 0;
while (copy) {
position = __builtin_ctzll(copy);
printf("%" PRIu64 " ", position);
//~ printf("%" PRIu64 " ", position);
copy &= ~((uint64_t)1 << position);
}
printf("\n\n");
//~ printf("\n\n");
}
}
......
for (uint32_t idx = 0; idx < count; idx++) {
uint64_t copy = vectors[idx];
printf("Index: %" PRIu32 "\n", idx);
//~ printf("Index: %" PRIu32 "\n", idx);
uint64_t position = 0;
while (copy) {
position = __builtin_ctzll(copy);
printf("%" PRIu64 " ", position);
//~ printf("%" PRIu64 " ", position);
copy &= masks[position];
}
printf("\n\n");
//~ printf("\n\n");
}
}
// Approach 3: use intrinsic and 2's complement trick
void approach3(uint32_t count, uint64_t* vectors)
{
for (uint32_t idx = 0; idx < I wcount; idx++) {
uint64_t copy = vectors[idx];
uint64_t vector = copy & (~copy + 1);
//~ printf("Index: %" PRIu32 "\n", idx);
uint64_t position = 0;
while (vector) {
position = __builtin_ffsll(vector);
//~ printf("%" PRIu64 " ", position);
copy = ~vector & copy;
vector = copy & (~copy + 1);
}
//~ printf("\n\n");
}
}
......
// was specified
if (argc < 3) {
fprintf(stderr, "Please specify file containing vectors and approach "
"index (0-2)\n");
"index (0-3)\n");
return -1;
}
......
case '2':
approach2(count, vectors);
break;
case '3':
approach3(count, vectors);
break;
default:
fprintf(stderr, "ERROR: invalid approach index\n");
}
software/misc/bit_position/make_sparse_vectors.py
#!/usr/bin/python3
import random
import sys
def main():
if len(sys.argv) < 3:
print('ERROR: must specify sparsity and number of output vectors')
return 1
sparsity = 0
try:
sparsity = int(sys.argv[1])
except ValueError:
print('ERROR: sparsity argument must be an integer')
return 1
num_vectors = 0
try:
num_vectors = int(sys.argv[2])
except ValueError:
print('ERROR: number of vectors argument must be an integer')
return 1
random.seed()
for idx in range(num_vectors):
vector = 0
for num_bits in range(random.randint(0, sparsity)):
vector |= (1 << random.randint(0, 63));
print('{:016X}'.format(vector))
if __name__ == '__main__':
sys.exit(main())
software/misc/bit_position/make_vectors.py
#!/usr/bin/python3
import sys
def main():

Also available in: Unified diff