/* NEW CODE for optimised bit array. * Copyright (C) 2024 Zak Fenton * NO WARRANTY USE AT YOUR OWN RISK etc. under terms of UNLICENSE or MIT license */ #include "types.h" #include "param.h" #include "memlayout.h" #include "sched.h" #include "riscv.h" #include "proc.h" #include "bitarray.h" #include "defs.h" #include "kprintf.h" struct bitarray* bitarrayalloc(int nbits) { int i; if (nbits > 64*64) { panic("argument to bitarrayalloc is too large"); } if (sizeof(struct bitarray) >= PGSIZE) { panic("bitarray structure too large to fit in a page"); } struct bitarray* result = kalloc(); result->size = nbits; if (result == (void*)0ULL) { panic("failed to allocate bitarray structure"); } initlock(&(result->lock), "bitarray"); for (i = 0; i < 64; i++) { result->data[i] = 0ULL; } return result; } int bitarray_get(struct bitarray* a, int index) { if (index < 0 || index >= a->size) { return 0; } acquire(&(a->lock)); uint64 x = a->data[index>>6]; if ((x & (1ULL << (index & 63))) != 0) { //printf("Bit at %p # %d is ON\n", a, index); release(&(a->lock)); return 1; } //printf("Bit at %p # %d is OFF\n", a, index); release(&(a->lock)); return 0; } int bitarray_getnolock(struct bitarray* a, int index) { if (index < 0 || index >= a->size) { return 0; } uint64 x = a->data[index>>6]; if ((x & (1ULL << (index & 63))) != 0) { //printf("Bit at %p # %d is ON\n", a, index); return 1; } //printf("Bit at %p # %d is OFF\n", a, index); return 0; } /*#ifdef _ZCC int __naked bitarraylsb(uint64 x) __asm { ctz a1, a1 ret // addi a2, zero, 0 // addi a4, zero, 1 // .lsbloop: // and a3, a1, a4 // bne a3, zero, .lsbend // srli a1, a1, 1 // addi a2, a2, 1 // j .lsbloop // .lsbend: // addi a1, a2, 0 // ret } int __naked bitarraylsb2(uint64 i, uint64 x) __asm { srl a3, a2, a1 ctz a4, a3 add a1, a1, a4 ret addi a4, zero, 1 addi a6, zero, 64 .lsb2loop: srl a3, a2, a1 and a5, a4, a1 bne a5, zero, .lsb2end addi a1, a1, 1 beq a1, a6, .lsb2nope j .lsb2loop .lsb2nope: addi a1, zero, -1 .lsb2end: ret } #else*/ int bitarraylsb(uint64 x) { int i; for (i = 0; i < 64; i++) { if (x & (1ULL << i)) { return i; } } return -1; } int bitarraylsb2(int starti, uint64 x) { for (; starti < 64; starti++) { if (x & (1ULL << starti)) { return starti; } } return -1; } //#endif int bitarraynextnzw(uint64* w, int start, int lim) { int i; for (i = start; i < lim; i++) { if (w[i]) { return i; } } return -1; } void bitarray_setnolock(struct bitarray* a, int index, int val) { //printf("Setting %p # %d to %s\n", a, index, val ? "ON" : "OFF"); if (index < 0 || index >= a->size) { panic("invalid index argument to bitarray_setnolock"); } uint64 x = a->data[index>>6]; if (val) { a->data[index>>6] = x | (1ULL << (index & 63)); } else { a->data[index>>6] = x & ~(1ULL << (index & 63)); } } int bitarray_findlowest(struct bitarray* a, int startidx) { //printf("Finding lowest set bit in %p from # %d\n", a, startidx); if (startidx < 0 || startidx >= a->size) { return -1; //startidx = 0; } acquire(&(a->lock)); int i; //uartputc_sync('a'); i = bitarraylsb2(startidx & 63, a->data[startidx>>6]); if (i < 0) { i = ((startidx >> 6) + 1) << 6; //for (i = startidx; (i & 63) != 0 && i < a->size; i++) { /*if (bitarray_getnolock(a, i)) { release(&(a->lock)); return i; }*/ //} } else { //uartputc_sync('A'); release(&(a->lock)); //printf("Got %d (path 1)\n", i + ((startidx >> 6) << 6)); return i + ((startidx >> 6) << 6); } //uartputc_sync('b'); for (; i < a->size; i+=64) { uint64 x = a->data[i>>6]; if (x) { release(&(a->lock)); //printf("Got %d (path 2)\n", i+bitarraylsb(x)); return i+bitarraylsb(x); } } //uartputc_sync('c'); release(&(a->lock)); return -1; } int bitarray_poplowest(struct bitarray* a, int startidx) { if (startidx < 0 || startidx >= a->size) { startidx = 0; } acquire(&(a->lock)); int i; for (i = startidx; i < a->size; i++) { if ((i & 63) == 0) { uint64 x = a->data[i>>6]; if (x == 0ULL) { i += 63; } } if (bitarray_getnolock(a, i)) { bitarray_setnolock(a, i, 0); release(&(a->lock)); return i; } } release(&(a->lock)); return -1; } void bitarray_set(struct bitarray* a, int index, int val) { //printf("Setting %p # %d to %s\n", a, index, val ? "ON" : "OFF"); if (index < 0 || index >= a->size) { panic("invalid index argument to bitarray_set"); } acquire(&(a->lock)); uint64 x = a->data[index>>6]; if (val) { a->data[index>>6] = x | (1ULL << (index & 63)); } else { a->data[index>>6] = x & ~(1ULL << (index & 63)); } release(&(a->lock)); }