Add ASSERT_WITH_SECURITY_IMPLICATION to detect out of bounds access
[WebKit-https.git] / Source / WTF / wtf / BitVector.h
1 /*
2  * Copyright (C) 2011 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #ifndef BitVector_h
27 #define BitVector_h
28
29 #include <stdio.h>
30 #include <wtf/Assertions.h>
31 #include <wtf/PrintStream.h>
32 #include <wtf/StdLibExtras.h>
33
34 namespace WTF {
35
36 // This is a space-efficient, resizeable bitvector class. In the common case it
37 // occupies one word, but if necessary, it will inflate this one word to point
38 // to a single chunk of out-of-line allocated storage to store an arbitrary number
39 // of bits.
40 //
41 // - The bitvector remembers the bound of how many bits can be stored, but this
42 //   may be slightly greater (by as much as some platform-specific constant)
43 //   than the last argument passed to ensureSize().
44 //
45 // - The bitvector can resize itself automatically (set, clear, get) or can be used
46 //   in a manual mode, which is faster (quickSet, quickClear, quickGet, ensureSize).
47 //
48 // - Accesses ASSERT that you are within bounds.
49 //
50 // - Bits are automatically initialized to zero.
51 //
52 // On the other hand, this BitVector class may not be the fastest around, since
53 // it does conditionals on every get/set/clear. But it is great if you need to
54 // juggle a lot of variable-length BitVectors and you're worried about wasting
55 // space.
56
57 class BitVector {
58 public: 
59     BitVector()
60         : m_bitsOrPointer(makeInlineBits(0))
61     {
62     }
63     
64     explicit BitVector(size_t numBits)
65         : m_bitsOrPointer(makeInlineBits(0))
66     {
67         ensureSize(numBits);
68     }
69     
70     BitVector(const BitVector& other)
71         : m_bitsOrPointer(makeInlineBits(0))
72     {
73         (*this) = other;
74     }
75
76     
77     ~BitVector()
78     {
79         if (isInline())
80             return;
81         OutOfLineBits::destroy(outOfLineBits());
82     }
83     
84     BitVector& operator=(const BitVector& other)
85     {
86         if (isInline() && other.isInline())
87             m_bitsOrPointer = other.m_bitsOrPointer;
88         else
89             setSlow(other);
90         return *this;
91     }
92
93     size_t size() const
94     {
95         if (isInline())
96             return maxInlineBits();
97         return outOfLineBits()->numBits();
98     }
99
100     void ensureSize(size_t numBits)
101     {
102         if (numBits <= size())
103             return;
104         resizeOutOfLine(numBits);
105     }
106     
107     // Like ensureSize(), but supports reducing the size of the bitvector.
108     WTF_EXPORT_PRIVATE void resize(size_t numBits);
109     
110     WTF_EXPORT_PRIVATE void clearAll();
111
112     bool quickGet(size_t bit) const
113     {
114         ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
115         return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
116     }
117     
118     void quickSet(size_t bit)
119     {
120         ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
121         bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
122     }
123     
124     void quickClear(size_t bit)
125     {
126         ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
127         bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
128     }
129     
130     void quickSet(size_t bit, bool value)
131     {
132         if (value)
133             quickSet(bit);
134         else
135             quickClear(bit);
136     }
137     
138     bool get(size_t bit) const
139     {
140         if (bit >= size())
141             return false;
142         return quickGet(bit);
143     }
144     
145     void set(size_t bit)
146     {
147         ensureSize(bit + 1);
148         quickSet(bit);
149     }
150
151     void ensureSizeAndSet(size_t bit, size_t size)
152     {
153         ensureSize(size);
154         quickSet(bit);
155     }
156
157     void clear(size_t bit)
158     {
159         if (bit >= size())
160             return;
161         quickClear(bit);
162     }
163     
164     void set(size_t bit, bool value)
165     {
166         if (value)
167             set(bit);
168         else
169             clear(bit);
170     }
171     
172     void dump(PrintStream& out);
173     
174 private:
175     static unsigned bitsInPointer()
176     {
177         return sizeof(void*) << 3;
178     }
179
180     static unsigned maxInlineBits()
181     {
182         return bitsInPointer() - 1;
183     }
184
185     static size_t byteCount(size_t bitCount)
186     {
187         return (bitCount + 7) >> 3;
188     }
189
190     static uintptr_t makeInlineBits(uintptr_t bits)
191     {
192         ASSERT(!(bits & (static_cast<uintptr_t>(1) << maxInlineBits())));
193         return bits | (static_cast<uintptr_t>(1) << maxInlineBits());
194     }
195     
196     class OutOfLineBits {
197     public:
198         size_t numBits() const { return m_numBits; }
199         size_t numWords() const { return (m_numBits + bitsInPointer() - 1) / bitsInPointer(); }
200         uintptr_t* bits() { return bitwise_cast<uintptr_t*>(this + 1); }
201         const uintptr_t* bits() const { return bitwise_cast<const uintptr_t*>(this + 1); }
202         
203         static WTF_EXPORT_PRIVATE OutOfLineBits* create(size_t numBits);
204         
205         static WTF_EXPORT_PRIVATE void destroy(OutOfLineBits*);
206
207     private:
208         OutOfLineBits(size_t numBits)
209             : m_numBits(numBits)
210         {
211         }
212         
213         size_t m_numBits;
214     };
215     
216     bool isInline() const { return m_bitsOrPointer >> maxInlineBits(); }
217     
218     const OutOfLineBits* outOfLineBits() const { return bitwise_cast<const OutOfLineBits*>(m_bitsOrPointer << 1); }
219     OutOfLineBits* outOfLineBits() { return bitwise_cast<OutOfLineBits*>(m_bitsOrPointer << 1); }
220     
221     WTF_EXPORT_PRIVATE void resizeOutOfLine(size_t numBits);
222     WTF_EXPORT_PRIVATE void setSlow(const BitVector& other);
223     
224     uintptr_t* bits()
225     {
226         if (isInline())
227             return &m_bitsOrPointer;
228         return outOfLineBits()->bits();
229     }
230     
231     const uintptr_t* bits() const
232     {
233         if (isInline())
234             return &m_bitsOrPointer;
235         return outOfLineBits()->bits();
236     }
237     
238     uintptr_t m_bitsOrPointer;
239 };
240
241 } // namespace WTF
242
243 using WTF::BitVector;
244
245 #endif // BitVector_h