summaryrefslogtreecommitdiffstats
path: root/bitops.c
blob: f9691369d829f99d6b43063aad3cd2f9e9b20402 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/* ----------------------------------------------------------------------- *
 *   
 *   Copyright 2000-2008 H. Peter Anvin - All Rights Reserved
 *
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU Lesser General Public License as
 *   published by the Free Software Foundation, Inc.,
 *   51 Franklin St, Fifth Floor, Boston MA 02110-1301, USA; version 2.1,
 *   incorporated herein by reference.
 *
 * ----------------------------------------------------------------------- */

/*
 * bitops.c
 *
 * Non-inline bitmap operations.
 */

#include <string.h>
#include <assert.h>
#include "bitops.h"

/* Finds a one bit somewhere between [start, start+count) bit indicies.
   Returns the index, or "err" if no such bit is found. */
size_t lpsm_find_set_bit(const void *ptr, size_t start, size_t count,
			 size_t err)
{
  const bitscan_t *cp, *ecp;
  bitscan_t val, smask, emask;
  size_t end, base;

  assert(count >= 1);

  end = start+count-1;		/* Inclusive! */

  cp  = (const bitscan_t *)ptr + (start >> BITSCAN_SHIFT);
  ecp = (const bitscan_t *)ptr + (end >> BITSCAN_SHIFT);

  base = start & ~BITSCAN_MASK;

  smask = ~BITSCAN_0 << (start & BITSCAN_MASK);
  emask = ~(~BITSCAN_1 << (end & BITSCAN_MASK));

  if (cp == ecp) {
    /* All falls within a single bitscan_t quantum */
    val = *cp & smask & emask;
    if ( !val )
      return err;
    else
      return bitctz(val) + base;
  }
  
  /* First quantum */
  val = *cp & smask;
  if (val)
    return bitctz(val) + base;
  cp++;
  base += BITSCAN_BITS;

  /* Whole quanta */
  while (cp < ecp) {
    val = *cp;
    if (val)
      return bitctz(val) + base;
    cp++;
    base += BITSCAN_BITS;
  }

  /* Final quantum */
  val = *cp & emask;
  if (val)
    return bitctz(val) + base;
  else
    return err;			/* Nothing found */
}