summaryrefslogtreecommitdiffstats
path: root/bitops.h
blob: bb79979617423b5413d5bb6aa780274dc86378ad (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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/* ----------------------------------------------------------------------- *
 *   
 *   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.h
 *
 * Internals for LPSM: bitmap operations.  Not to be used by applications.
 */

#ifndef LPSM_BITOPS_H
#define LPSM_BITOPS_H

#include <inttypes.h>
#include "system.h"		/* System-specific constants */

/* The data type to use for bitfield scanning.  Typically should equal
   the "natural" size on the machine; defined in system.h. */
#if MACHINE_SIZE_LG2 == 6
  typedef uint64_t bitscan_t;
# define BITSCAN_C(X) UINT64_C(X)
#else
  typedef uint32_t bitscan_t;
# define BITSCAN_C(X) UINT32_C(X)
#endif
#define BITSCAN_SHIFT		MACHINE_SIZE_LG2
#define BITSCAN_BITS		(1 << BITSCAN_SHIFT)
#define BITSCAN_MASK		(BITSCAN_BITS-1)
#define BITSCAN_0		BITSCAN_C(0)
#define BITSCAN_1		BITSCAN_C(1)

/*
 * These should be revamped to be thread-safe at some point.  That
 * may mean doing things that are architecture-specific...
 *
 * Important: "bit" can be negative, and that needs to be handled
 * correctly!
 */
static inline int test_bit(const void *ptr, size_t bit)
{
#if defined(__GNUC__) && defined(__x86_64__)
  char rv;
  asm("btq %2,%1 ; setc %0"
      : "=rm" (rv) : "m" (*(const bitscan_t *)ptr), "r" (bit) : "cc");
  return rv;
#elif defined(__GNUC__) && defined(__i386__)
  char rv;
  asm("btl %2,%1 ; setc %0"
      : "=rm" (rv) : "m" (*(const bitscan_t *)ptr), "r" (bit) : "cc");
  return rv;
#else
  const bitscan_t *cp;

  cp = (const bitscan_t *)ptr + (bit >> BITSCAN_SHIFT);
  return (int)((*cp >> (bit & BITSCAN_MASK)) & BITSCAN_1);
#endif
}

static inline void set_bit(void *ptr, size_t bit)
{
#if defined(__GNUC__) && defined(__x86_64__)
  asm volatile("btsq %1,%0" : "+m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
#elif defined(__GNUC__) && defined(__i386__)
  asm volatile("btsl %1,%0" : "+m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
#else
  bitscan_t *cp;

  cp = (bitscan_t *)ptr + (bit >> BITSCAN_SHIFT);
  *cp |= (BITSCAN_1 << (bit & BITSCAN_MASK));
#endif
}

static inline void clr_bit(void *ptr, size_t bit)
{
#if defined(__GNUC__) && defined(__x86_64__)
  asm volatile("btcq %1,%0" : "+m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
#elif defined(__GNUC__) && defined(__i386__)
  asm volatile("btcl %1,%0" : "+m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
#else
  bitscan_t *cp;

  cp = (bitscan_t *)ptr + (bit >> BITSCAN_SHIFT);
  *cp &= ~(BITSCAN_1 << (bit & BITSCAN_MASK));
#endif
}

static inline int bitctz(bitscan_t x)
{
#if defined(__GNUC__) && __GNUC__ >= 4
  return __builtin_ctzl(x);
#else
  int r = 0;

# if MACHINE_SIZE_LG2 >= 6
  if (!(x & BITSCAN_C(0xffffffff))) {
    r += 32;
    x >>= 32;
  }
# endif
  if (!(x & BITSCAN_C(0xffff))) {
    r += 16;
    x >>= 16;
  }
  if (!(x & BITSCAN_C(0xff))) {
    r += 8;
    x >>= 8;
  }
  if (!(x & BITSCAN_C(0xf))) {
    r += 4;
    x >>= 4;
  }
  if (!(x & BITSCAN_C(0x3))) {
    r += 2;
    x >>= 2;
  }
  if (!(x & BITSCAN_C(0x1))) {
    r += 1;
    /* x >>= 1; */
  }
  return r;
#endif
}

size_t lpsm_find_set_bit(const void *ptr, size_t start, size_t count,
			 size_t err);

#endif /* LPSM_BITOPS_H */