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 PackedIntVector_h
27#define PackedIntVector_h
28
29#include <wtf/BitVector.h>
30
31namespace WTF {
32
33// This class allows you to create an array of integers, where those
34// integers have only a handful of bits each. It is not meant to be
35// efficient in time, but only in space. (Though making it efficient
36// in time for power-of-2 values of bitCount would not be difficult.)
37// Note that this does not work as expected for signed types, if you
38// are relying on the sign being preserved.
39
40template<typename T, unsigned bitCount>
41class PackedIntVector {
42public:
43    static_assert(bitCount, "bitCount must not be zero!");
44    static_assert(bitCount < sizeof(void*) * 8, "bitCount must not exceed the address space limit!");
45
46    PackedIntVector()
47    {
48    }
49
50    PackedIntVector(const PackedIntVector& other)
51        : m_bits(other.m_bits)
52    {
53    }
54
55    PackedIntVector& operator=(const PackedIntVector& other)
56    {
57        m_bits = other.m_bits;
58        return *this;
59    }
60
61    size_t size() const
62    {
63        return m_bits.size() / bitCount;
64    }
65
66    void ensureSize(size_t numInts)
67    {
68        m_bits.ensureSize(numInts * bitCount);
69    }
70
71    void resize(size_t numInts)
72    {
73        m_bits.resize(numInts * bitCount);
74    }
75
76    void clearAll()
77    {
78        m_bits.clearAll();
79    }
80
81    T get(size_t index) const
82    {
83        uintptr_t result = 0;
84        for (unsigned subIndex = 0; subIndex < bitCount; ++subIndex) {
85            result <<= 1;
86            result |= (m_bits.quickGet(index * bitCount + subIndex) ? 1 : 0);
87        }
88        return static_cast<T>(result);
89    }
90
91    void set(size_t index, T value)
92    {
93        // Do arithmetic using uintptr_t, because (1) we know what it is
94        // (T might be an enum) and (2) it's the largest integer type that
95        // is likely to perform decently well.
96        uintptr_t myValue = static_cast<uintptr_t>(value);
97
98        // Preliminary sanity check that the value is not out of range.
99        ASSERT((myValue & mask()) == myValue);
100
101        for (unsigned subIndex = bitCount; subIndex-- > 0;) {
102            m_bits.quickSet(index * bitCount + subIndex, !!(myValue & 1));
103            myValue >>= 1;
104        }
105
106        // Final sanity check that we stored what the user thought we
107        // stored.
108        ASSERT(get(index) == value);
109    }
110private:
111    // This returns the mask, and is careful to not step on the wrap-around
112    // semantics of the shift amount (1 << 32 is 1 since 32 wraps to 0). There
113    // is the separate question of why you would ever use this to store 32-bit
114    // or 64-bit values, but it's probably better to have this work as expected
115    // in such situations regardless.
116    static uintptr_t mask() { return (static_cast<uintptr_t>(2) << (bitCount - 1)) - 1; }
117
118    // Stores integers bit by bit in big endian.
119    BitVector m_bits;
120};
121
122} // namespace WTF
123
124using WTF::PackedIntVector;
125
126#endif // PackedIntVector_h
127
128