slkern/bitarray.c

/* 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));
}