source: trunk/source/lisp-kernel/bits.h @ 9899

Last change on this file since 9899 was 9899, checked in by gb, 11 years ago

Add a comment, describing builtin_clz lossage. (I believe that
all lisp uses of count_leading_zeros involve arguments known to be non-zero.)

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 4.4 KB
Line 
1/*
2   Copyright (C) 1994-2001 Digitool, Inc
3   This file is part of OpenMCL. 
4
5   OpenMCL is licensed under the terms of the Lisp Lesser GNU Public
6   License , known as the LLGPL and distributed with OpenMCL as the
7   file "LICENSE".  The LLGPL consists of a preamble and the LGPL,
8   which is distributed with OpenMCL as the file "LGPL".  Where these
9   conflict, the preamble takes precedence. 
10
11   OpenMCL is referenced in the preamble as the "LIBRARY."
12
13   The LLGPL is also available online at
14   http://opensource.franz.com/preamble.html
15*/
16
17
18
19#ifndef __bits_h__
20#define __bits_h__ 1
21
22#include <string.h>
23
24typedef natural *bitvector;
25
26#if WORD_SIZE == 64
27#define bitmap_shift 6
28#define BIT0_MASK 0x8000000000000000ULL
29#define ALL_ONES  0xffffffffffffffffULL
30#else
31#define bitmap_shift 5
32#define BIT0_MASK 0x80000000U
33#define ALL_ONES  0xFFFFFFFFU
34#endif
35
36#define bitmap_shift_count_mask ((1<<bitmap_shift)-1)
37
38static inline int
39set_bit(bitvector bits,natural bitnum)  __attribute__((always_inline));
40
41static inline int
42set_bit(bitvector bits,natural bitnum)
43{
44  natural
45    windex = bitnum>>bitmap_shift, 
46    old = bits[windex],
47    new = old | (BIT0_MASK >> (bitnum & bitmap_shift_count_mask));
48  if (new == old) {
49    return 1;                   /* Was set */
50  } else {
51    bits[windex] = new;
52    return 0;                   /* Was clear */
53  }
54}
55
56static inline int 
57atomic_set_bit(bitvector bits ,natural bitnum)
58{
59  extern natural atomic_ior(bitvector, natural);
60  natural
61    windex = bitnum>>bitmap_shift,
62    mask = (BIT0_MASK >> (bitnum & bitmap_shift_count_mask));
63
64  return atomic_ior(bits + windex, mask);
65}
66
67void set_n_bits(bitvector,natural,natural);
68
69static inline int
70clr_bit(bitvector bits, natural bitnum)
71{
72  unsigned 
73    windex = bitnum>>bitmap_shift, 
74    old = bits[windex],
75    new = old & ~(BIT0_MASK >> (bitnum & bitmap_shift_count_mask));
76  if (new == old) {
77    return 0;   /* Was clear */
78  } else {
79    bits[windex] = new;
80    return 1;   /* Was set */
81  }
82}
83
84
85static inline unsigned
86ref_bit(bitvector bits,natural bitnum) __attribute__((always_inline));
87
88static inline unsigned
89ref_bit(bitvector bits,natural bitnum)
90{
91  return ((bits[bitnum>>bitmap_shift] & (BIT0_MASK >> (bitnum & bitmap_shift_count_mask))) != 0);
92}
93
94void zero_bits(bitvector, natural);
95void ior_bits(bitvector,bitvector,natural);
96
97#define bits_word_index(bitnum) (((natural)(bitnum)) >> bitmap_shift)
98#define bits_bit_index(bitnum) (((natural)(bitnum)) & bitmap_shift_count_mask)
99#define bits_word_ptr(bits,bitnum) \
100  ((natural*) (((natural*) bits) + ((natural) (bits_word_index(bitnum)))))
101#define bits_word_mask(bitnum) ((BIT0_MASK) >> bits_bit_index(bitnum))
102#define bits_indexed_word(bitv,indexw) ((((natural*)(bitv))[indexw]))
103#define bits_word(bitv,bitnum) bits_indexed_word(bits,bits_word_index(bitnum))
104
105/* Evaluates some arguments twice */
106
107#define set_bits_vars(BITVvar,BITNUMvar,BITPvar,BITWvar,MASKvar) \
108{ BITPvar = bits_word_ptr(BITVvar,BITNUMvar); BITWvar = *BITPvar; MASKvar = bits_word_mask(BITNUMvar); }
109
110#define set_bitidx_vars(BITVvar,BITNUMvar,BITPvar,BITWvar,BITIDXvar) \
111{ BITPvar = bits_word_ptr(BITVvar,BITNUMvar); BITIDXvar = bits_bit_index(BITNUMvar); \
112    BITWvar = (*BITPvar << BITIDXvar) >> BITIDXvar; }
113
114#ifdef __GNUC__
115static __inline__ natural
116current_stack_pointer(void) __attribute__((always_inline));
117
118static __inline__ natural
119current_stack_pointer(void)
120{
121#ifdef PPC
122  register natural _sp __asm__("r1");
123#endif
124#ifdef X8664
125  register natural _sp __asm__("%rsp");
126#endif
127  return _sp;
128}
129#else
130natural
131current_stack_pointer(void);
132#endif
133
134#ifdef __GNUC__
135static __inline__ unsigned
136count_leading_zeros(natural w) __attribute__((always_inline));
137
138
139/* Beware: on some platforms, __builtin_clz[ll](0) returns an undefined
140   result */
141
142static __inline__ unsigned
143count_leading_zeros(natural w)
144{
145#if __GNUC__ >= 4
146#if WORD_SIZE == 64
147  return __builtin_clzll(w); 
148#else
149  return __builtin_clz(w); 
150#endif
151#else /* __GNUC__ < 4 */
152  natural lz;
153#ifdef PPC
154#ifdef PPC64
155  __asm__  ("cntlzd %0,%1" : "=r" (lz) : "r" (w));
156#else
157  __asm__  ("cntlzw %0,%1" : "=r" (lz) : "r" (w));
158#endif
159#endif /* PPC */
160#ifdef X86
161#ifdef X8664
162  __asm__ ("bsr %1,%0" : "=r" (lz) : "r" (w));
163  __asm__ ("xor $63,%0" : "=r" (lz));
164#else
165  __asm__ ("bsr %1,%0" : "=r" (lz) : "r" (w));
166  __asm__ ("xor $31,%0" : "=r" (lz));
167#endif
168#endif
169  return lz;
170#endif
171}
172#else /* not __GNUC__ */
173unsigned
174count_leading_zeros(natural);
175#endif
176                                       
177#endif /* __bits_h__ */
Note: See TracBrowser for help on using the repository browser.