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 *
8 * 1.  Redistributions of source code must retain the above copyright
9 *     notice, this list of conditions and the following disclaimer.
10 * 2.  Redistributions in binary form must reproduce the above copyright
11 *     notice, this list of conditions and the following disclaimer in the
12 *     documentation and/or other materials provided with the distribution.
13 * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
14 *     its contributors may be used to endorse or promote products derived
15 *     from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef CompactJITCodeMap_h
30#define CompactJITCodeMap_h
31
32#include <wtf/Assertions.h>
33#include <wtf/FastAllocBase.h>
34#include <wtf/FastMalloc.h>
35#include <wtf/OwnPtr.h>
36#include <wtf/PassOwnPtr.h>
37#include <wtf/Vector.h>
38
39namespace JSC {
40
41// Gives you a compressed map between between bytecode indices and machine code
42// entry points. The compression simply tries to use either 1, 2, or 4 bytes for
43// any given offset. The largest offset that can be stored is 2^30.
44
45// Example use:
46//
47// CompactJITCodeMap::Encoder encoder(map);
48// encoder.append(a, b);
49// encoder.append(c, d); // preconditions: c >= a, d >= b
50// OwnPtr<CompactJITCodeMap> map = encoder.finish();
51//
52// At some later time:
53//
54// Vector<BytecodeAndMachineOffset> decoded;
55// map->decode(decoded);
56
57struct BytecodeAndMachineOffset {
58    BytecodeAndMachineOffset() { }
59
60    BytecodeAndMachineOffset(unsigned bytecodeIndex, unsigned machineCodeOffset)
61        : m_bytecodeIndex(bytecodeIndex)
62        , m_machineCodeOffset(machineCodeOffset)
63    {
64    }
65
66    unsigned m_bytecodeIndex;
67    unsigned m_machineCodeOffset;
68
69    static inline unsigned getBytecodeIndex(BytecodeAndMachineOffset* mapping)
70    {
71        return mapping->m_bytecodeIndex;
72    }
73
74    static inline unsigned getMachineCodeOffset(BytecodeAndMachineOffset* mapping)
75    {
76        return mapping->m_machineCodeOffset;
77    }
78};
79
80class CompactJITCodeMap {
81    WTF_MAKE_FAST_ALLOCATED;
82public:
83    ~CompactJITCodeMap()
84    {
85        if (m_buffer)
86            fastFree(m_buffer);
87    }
88
89    unsigned numberOfEntries() const
90    {
91        return m_numberOfEntries;
92    }
93
94    void decode(Vector<BytecodeAndMachineOffset>& result) const;
95
96private:
97    CompactJITCodeMap(uint8_t* buffer, unsigned size, unsigned numberOfEntries)
98        : m_buffer(buffer)
99#if !ASSERT_DISABLED
100        , m_size(size)
101#endif
102        , m_numberOfEntries(numberOfEntries)
103    {
104        UNUSED_PARAM(size);
105    }
106
107    uint8_t at(unsigned index) const
108    {
109        ASSERT(index < m_size);
110        return m_buffer[index];
111    }
112
113    unsigned decodeNumber(unsigned& index) const
114    {
115        uint8_t headValue = at(index++);
116        if (!(headValue & 128))
117            return headValue;
118        if (!(headValue & 64))
119            return (static_cast<unsigned>(headValue & ~128) << 8) | at(index++);
120        unsigned second = at(index++);
121        unsigned third  = at(index++);
122        unsigned fourth = at(index++);
123        return (static_cast<unsigned>(headValue & ~(128 + 64)) << 24) | (second << 16) | (third << 8) | fourth;
124    }
125
126    uint8_t* m_buffer;
127#if !ASSERT_DISABLED
128    unsigned m_size;
129#endif
130    unsigned m_numberOfEntries;
131
132public:
133    class Encoder {
134        WTF_MAKE_NONCOPYABLE(Encoder);
135    public:
136        Encoder();
137        ~Encoder();
138
139        void ensureCapacityFor(unsigned numberOfEntriesToAdd);
140        void append(unsigned bytecodeIndex, unsigned machineCodeOffset);
141        PassOwnPtr<CompactJITCodeMap> finish();
142
143    private:
144        void appendByte(uint8_t value);
145        void encodeNumber(uint32_t value);
146
147        uint8_t* m_buffer;
148        unsigned m_size;
149        unsigned m_capacity;
150        unsigned m_numberOfEntries;
151
152        unsigned m_previousBytecodeIndex;
153        unsigned m_previousMachineCodeOffset;
154    };
155
156    class Decoder {
157        WTF_MAKE_NONCOPYABLE(Decoder);
158    public:
159        Decoder(const CompactJITCodeMap*);
160
161        unsigned numberOfEntriesRemaining() const;
162        void read(unsigned& bytecodeIndex, unsigned& machineCodeOffset);
163
164    private:
165        const CompactJITCodeMap* m_jitCodeMap;
166        unsigned m_previousBytecodeIndex;
167        unsigned m_previousMachineCodeOffset;
168        unsigned m_numberOfEntriesRemaining;
169        unsigned m_bufferIndex;
170    };
171
172private:
173    friend class Encoder;
174    friend class Decoder;
175};
176
177inline void CompactJITCodeMap::decode(Vector<BytecodeAndMachineOffset>& result) const
178{
179    Decoder decoder(this);
180    result.resize(decoder.numberOfEntriesRemaining());
181    for (unsigned i = 0; i < result.size(); ++i)
182        decoder.read(result[i].m_bytecodeIndex, result[i].m_machineCodeOffset);
183
184    ASSERT(!decoder.numberOfEntriesRemaining());
185}
186
187inline CompactJITCodeMap::Encoder::Encoder()
188    : m_buffer(0)
189    , m_size(0)
190    , m_capacity(0)
191    , m_numberOfEntries(0)
192    , m_previousBytecodeIndex(0)
193    , m_previousMachineCodeOffset(0)
194{
195}
196
197inline CompactJITCodeMap::Encoder::~Encoder()
198{
199    if (m_buffer)
200        fastFree(m_buffer);
201}
202
203inline void CompactJITCodeMap::Encoder::append(unsigned bytecodeIndex, unsigned machineCodeOffset)
204{
205    ASSERT(bytecodeIndex >= m_previousBytecodeIndex);
206    ASSERT(machineCodeOffset >= m_previousMachineCodeOffset);
207    ensureCapacityFor(1);
208    encodeNumber(bytecodeIndex - m_previousBytecodeIndex);
209    encodeNumber(machineCodeOffset - m_previousMachineCodeOffset);
210    m_previousBytecodeIndex = bytecodeIndex;
211    m_previousMachineCodeOffset = machineCodeOffset;
212    m_numberOfEntries++;
213}
214
215inline PassOwnPtr<CompactJITCodeMap> CompactJITCodeMap::Encoder::finish()
216{
217    m_capacity = m_size;
218    m_buffer = static_cast<uint8_t*>(fastRealloc(m_buffer, m_capacity));
219    OwnPtr<CompactJITCodeMap> result = adoptPtr(new CompactJITCodeMap(m_buffer, m_size, m_numberOfEntries));
220    m_buffer = 0;
221    m_size = 0;
222    m_capacity = 0;
223    m_numberOfEntries = 0;
224    m_previousBytecodeIndex = 0;
225    m_previousMachineCodeOffset = 0;
226    return result.release();
227}
228
229inline void CompactJITCodeMap::Encoder::appendByte(uint8_t value)
230{
231    ASSERT(m_size + 1 <= m_capacity);
232    m_buffer[m_size++] = value;
233}
234
235inline void CompactJITCodeMap::Encoder::encodeNumber(uint32_t value)
236{
237    ASSERT(m_size + 4 <= m_capacity);
238    ASSERT(value < (1 << 30));
239    if (value <= 127) {
240        uint8_t headValue = static_cast<uint8_t>(value);
241        ASSERT(!(headValue & 128));
242        appendByte(headValue);
243    } else if (value <= 16383) {
244        uint8_t headValue = static_cast<uint8_t>(value >> 8);
245        ASSERT(!(headValue & 128));
246        ASSERT(!(headValue & 64));
247        appendByte(headValue | 128);
248        appendByte(static_cast<uint8_t>(value));
249    } else {
250        uint8_t headValue = static_cast<uint8_t>(value >> 24);
251        ASSERT(!(headValue & 128));
252        ASSERT(!(headValue & 64));
253        appendByte(headValue | 128 | 64);
254        appendByte(static_cast<uint8_t>(value >> 16));
255        appendByte(static_cast<uint8_t>(value >> 8));
256        appendByte(static_cast<uint8_t>(value));
257    }
258}
259
260inline void CompactJITCodeMap::Encoder::ensureCapacityFor(unsigned numberOfEntriesToAdd)
261{
262    unsigned capacityNeeded = m_size + numberOfEntriesToAdd * 2 * 4;
263    if (capacityNeeded > m_capacity) {
264        m_capacity = capacityNeeded * 2;
265        m_buffer = static_cast<uint8_t*>(fastRealloc(m_buffer, m_capacity));
266    }
267}
268
269inline CompactJITCodeMap::Decoder::Decoder(const CompactJITCodeMap* jitCodeMap)
270    : m_jitCodeMap(jitCodeMap)
271    , m_previousBytecodeIndex(0)
272    , m_previousMachineCodeOffset(0)
273    , m_numberOfEntriesRemaining(jitCodeMap->m_numberOfEntries)
274    , m_bufferIndex(0)
275{
276}
277
278inline unsigned CompactJITCodeMap::Decoder::numberOfEntriesRemaining() const
279{
280    ASSERT(m_numberOfEntriesRemaining || m_bufferIndex == m_jitCodeMap->m_size);
281    return m_numberOfEntriesRemaining;
282}
283
284inline void CompactJITCodeMap::Decoder::read(unsigned& bytecodeIndex, unsigned& machineCodeOffset)
285{
286    ASSERT(numberOfEntriesRemaining());
287
288    m_previousBytecodeIndex += m_jitCodeMap->decodeNumber(m_bufferIndex);
289    m_previousMachineCodeOffset += m_jitCodeMap->decodeNumber(m_bufferIndex);
290    bytecodeIndex = m_previousBytecodeIndex;
291    machineCodeOffset = m_previousMachineCodeOffset;
292    m_numberOfEntriesRemaining--;
293}
294
295} // namespace JSC
296
297#endif // CompactJITCodeMap_h
298