← Back to branch summary

~ubuntu-branches/ubuntu/trusty/monodevelop/trusty-proposed

« back to all changes in this revision

Viewing changes to external/ikvm/reflect/Writer/Heaps.cs

  • Committer: Package Import Robot
  • Author(s): Jo Shields
  • Date: 2013-05-12 09:46:03 UTC
  • mto: This revision was merged to the branch mainline in revision 29.
  • Revision ID: package-import@ubuntu.com-20130512094603-mad323bzcxvmcam0
Tags: upstream-4.0.5+dfsg
Import upstream version 4.0.5+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
external/ikvm/reflect/Writer/Heaps.cs
 
1
/*
 
2
  Copyright (C) 2008 Jeroen Frijters
 
3
 
 
4
  This software is provided 'as-is', without any express or implied
 
5
  warranty.  In no event will the authors be held liable for any damages
 
6
  arising from the use of this software.
 
7
 
 
8
  Permission is granted to anyone to use this software for any purpose,
 
9
  including commercial applications, and to alter it and redistribute it
 
10
  freely, subject to the following restrictions:
 
11
 
 
12
  1. The origin of this software must not be misrepresented; you must not
 
13
     claim that you wrote the original software. If you use this software
 
14
     in a product, an acknowledgment in the product documentation would be
 
15
     appreciated but is not required.
 
16
  2. Altered source versions must be plainly marked as such, and must not be
 
17
     misrepresented as being the original software.
 
18
  3. This notice may not be removed or altered from any source distribution.
 
19
 
 
20
  Jeroen Frijters
 
21
  jeroen@frijters.net
 
22
  
 
23
*/
 
24
using System;
 
25
using System.Collections.Generic;
 
26
using System.Text;
 
27
using System.Diagnostics;
 
28
using IKVM.Reflection.Metadata;
 
29
 
 
30
namespace IKVM.Reflection.Writer
 
31
{
 
32
        abstract class Heap
 
33
        {
 
34
                protected bool frozen;
 
35
                protected int unalignedlength;
 
36
 
 
37
                internal void Write(MetadataWriter mw)
 
38
                {
 
39
                        int pos = mw.Position;
 
40
                        WriteImpl(mw);
 
41
                        Debug.Assert(mw.Position == pos + unalignedlength);
 
42
                        int align = Length - unalignedlength;
 
43
                        for (int i = 0; i < align; i++)
 
44
                        {
 
45
                                mw.Write((byte)0);
 
46
                        }
 
47
                }
 
48
 
 
49
                internal bool IsBig
 
50
                {
 
51
                        get { return Length > 65535; }
 
52
                }
 
53
 
 
54
                internal int Length
 
55
                {
 
56
                        get
 
57
                        {
 
58
                                if (!frozen)
 
59
                                        throw new InvalidOperationException();
 
60
                                return (unalignedlength + 3) & ~3;
 
61
                        }
 
62
                }
 
63
 
 
64
                protected abstract void WriteImpl(MetadataWriter mw);
 
65
        }
 
66
 
 
67
        abstract class SimpleHeap : Heap
 
68
        {
 
69
                internal void Freeze()
 
70
                {
 
71
                        if (frozen)
 
72
                                throw new InvalidOperationException();
 
73
                        frozen = true;
 
74
                        unalignedlength = GetLength();
 
75
                }
 
76
 
 
77
                protected abstract int GetLength();
 
78
        }
 
79
 
 
80
        sealed class TableHeap : Heap
 
81
        {
 
82
                internal void Freeze(MetadataWriter mw)
 
83
                {
 
84
                        if (frozen)
 
85
                                throw new InvalidOperationException();
 
86
                        frozen = true;
 
87
                        unalignedlength = GetLength(mw);
 
88
                }
 
89
 
 
90
                protected override void WriteImpl(MetadataWriter mw)
 
91
                {
 
92
                        Table[] tables = mw.ModuleBuilder.GetTables();
 
93
                        // Header
 
94
                        mw.Write(0);            // Reserved
 
95
                        int ver = mw.ModuleBuilder.MDStreamVersion;
 
96
                        mw.Write((byte)(ver >> 16));    // MajorVersion
 
97
                        mw.Write((byte)ver);                    // MinorVersion
 
98
                        byte heapSizes = 0;
 
99
                        if (mw.ModuleBuilder.Strings.IsBig)
 
100
                        {
 
101
                                heapSizes |= 0x01;
 
102
                        }
 
103
                        if (mw.ModuleBuilder.Guids.IsBig)
 
104
                        {
 
105
                                heapSizes |= 0x02;
 
106
                        }
 
107
                        if (mw.ModuleBuilder.Blobs.IsBig)
 
108
                        {
 
109
                                heapSizes |= 0x04;
 
110
                        }
 
111
                        mw.Write(heapSizes);// HeapSizes
 
112
                        // LAMESPEC spec says reserved, but .NET 2.0 Ref.Emit sets it to 0x10
 
113
                        mw.Write((byte)0x10);   // Reserved
 
114
                        long bit = 1;
 
115
                        long valid = 0;
 
116
                        foreach (Table table in tables)
 
117
                        {
 
118
                                if (table != null && table.RowCount > 0)
 
119
                                {
 
120
                                        valid |= bit;
 
121
                                }
 
122
                                bit <<= 1;
 
123
                        }
 
124
                        mw.Write(valid);        // Valid
 
125
                        mw.Write(0x0016003301FA00L);    // Sorted
 
126
                        // Rows
 
127
                        foreach (Table table in tables)
 
128
                        {
 
129
                                if (table != null && table.RowCount > 0)
 
130
                                {
 
131
                                        mw.Write(table.RowCount);
 
132
                                }
 
133
                        }
 
134
                        // Tables
 
135
                        foreach (Table table in tables)
 
136
                        {
 
137
                                if (table != null && table.RowCount > 0)
 
138
                                {
 
139
                                        int pos = mw.Position;
 
140
                                        table.Write(mw);
 
141
                                        Debug.Assert(mw.Position - pos == table.GetLength(mw));
 
142
                                }
 
143
                        }
 
144
                        // unexplained extra padding
 
145
                        mw.Write((byte)0);
 
146
                }
 
147
 
 
148
                private static int GetLength(MetadataWriter mw)
 
149
                {
 
150
                        int len = 4 + 4 + 8 + 8;
 
151
                        foreach (Table table in mw.ModuleBuilder.GetTables())
 
152
                        {
 
153
                                if (table != null && table.RowCount > 0)
 
154
                                {
 
155
                                        len += 4;       // row count
 
156
                                        len += table.GetLength(mw);
 
157
                                }
 
158
                        }
 
159
                        // note that we pad one extra (unexplained) byte
 
160
                        return len + 1;
 
161
                }
 
162
        }
 
163
 
 
164
        sealed class StringHeap : SimpleHeap
 
165
        {
 
166
                private List<string> list = new List<string>();
 
167
                private Dictionary<string, int> strings = new Dictionary<string, int>();
 
168
                private int nextOffset;
 
169
 
 
170
                internal StringHeap()
 
171
                {
 
172
                        Add("");
 
173
                }
 
174
 
 
175
                internal int Add(string str)
 
176
                {
 
177
                        Debug.Assert(!frozen);
 
178
                        int offset;
 
179
                        if (!strings.TryGetValue(str, out offset))
 
180
                        {
 
181
                                offset = nextOffset;
 
182
                                nextOffset += System.Text.Encoding.UTF8.GetByteCount(str) + 1;
 
183
                                list.Add(str);
 
184
                                strings.Add(str, offset);
 
185
                        }
 
186
                        return offset;
 
187
                }
 
188
 
 
189
                internal string Find(int index)
 
190
                {
 
191
                        foreach (KeyValuePair<string, int> kv in strings)
 
192
                        {
 
193
                                if (kv.Value == index)
 
194
                                {
 
195
                                        return kv.Key;
 
196
                                }
 
197
                        }
 
198
                        return null;
 
199
                }
 
200
 
 
201
                protected override int GetLength()
 
202
                {
 
203
                        return nextOffset;
 
204
                }
 
205
 
 
206
                protected override void WriteImpl(MetadataWriter mw)
 
207
                {
 
208
                        foreach (string str in list)
 
209
                        {
 
210
                                mw.Write(System.Text.Encoding.UTF8.GetBytes(str));
 
211
                                mw.Write((byte)0);
 
212
                        }
 
213
                }
 
214
        }
 
215
 
 
216
        sealed class UserStringHeap : SimpleHeap
 
217
        {
 
218
                private List<string> list = new List<string>();
 
219
                private Dictionary<string, int> strings = new Dictionary<string, int>();
 
220
                private int nextOffset;
 
221
 
 
222
                internal UserStringHeap()
 
223
                {
 
224
                        nextOffset = 1;
 
225
                }
 
226
 
 
227
                internal bool IsEmpty
 
228
                {
 
229
                        get { return nextOffset == 1; }
 
230
                }
 
231
 
 
232
                internal int Add(string str)
 
233
                {
 
234
                        Debug.Assert(!frozen);
 
235
                        int offset;
 
236
                        if (!strings.TryGetValue(str, out offset))
 
237
                        {
 
238
                                int length = str.Length * 2 + 1 + MetadataWriter.GetCompressedUIntLength(str.Length * 2 + 1);
 
239
                                if (nextOffset + length > 0xFFFFFF)
 
240
                                {
 
241
                                        throw new FileFormatLimitationExceededException("No logical space left to create more user strings.", FileFormatLimitationExceededException.META_E_STRINGSPACE_FULL);
 
242
                                }
 
243
                                offset = nextOffset;
 
244
                                nextOffset += length;
 
245
                                list.Add(str);
 
246
                                strings.Add(str, offset);
 
247
                        }
 
248
                        return offset;
 
249
                }
 
250
 
 
251
                protected override int GetLength()
 
252
                {
 
253
                        return nextOffset;
 
254
                }
 
255
 
 
256
                protected override void WriteImpl(MetadataWriter mw)
 
257
                {
 
258
                        mw.Write((byte)0);
 
259
                        foreach (string str in list)
 
260
                        {
 
261
                                mw.WriteCompressedUInt(str.Length * 2 + 1);
 
262
                                byte hasSpecialChars = 0;
 
263
                                foreach (char ch in str)
 
264
                                {
 
265
                                        mw.Write((ushort)ch);
 
266
                                        if (hasSpecialChars == 0 && (ch < 0x20 || ch > 0x7E))
 
267
                                        {
 
268
                                                if (ch > 0x7E
 
269
                                                        || (ch >= 0x01 && ch <= 0x08)
 
270
                                                        || (ch >= 0x0E && ch <= 0x1F)
 
271
                                                        || ch == 0x27
 
272
                                                        || ch == 0x2D)
 
273
                                                {
 
274
                                                        hasSpecialChars = 1;
 
275
                                                }
 
276
                                        }
 
277
                                }
 
278
                                mw.Write(hasSpecialChars);
 
279
                        }
 
280
                }
 
281
        }
 
282
 
 
283
        sealed class GuidHeap : SimpleHeap
 
284
        {
 
285
                private List<Guid> list = new List<Guid>();
 
286
 
 
287
                internal GuidHeap()
 
288
                {
 
289
                }
 
290
 
 
291
                internal int Add(Guid guid)
 
292
                {
 
293
                        Debug.Assert(!frozen);
 
294
                        list.Add(guid);
 
295
                        return list.Count;
 
296
                }
 
297
 
 
298
                protected override int GetLength()
 
299
                {
 
300
                        return list.Count * 16;
 
301
                }
 
302
 
 
303
                protected override void WriteImpl(MetadataWriter mw)
 
304
                {
 
305
                        foreach (Guid guid in list)
 
306
                        {
 
307
                                mw.Write(guid.ToByteArray());
 
308
                        }
 
309
                }
 
310
        }
 
311
 
 
312
        sealed class BlobHeap : SimpleHeap
 
313
        {
 
314
                private Key[] map = new Key[8179];
 
315
                private readonly ByteBuffer buf = new ByteBuffer(32);
 
316
 
 
317
                private struct Key
 
318
                {
 
319
                        internal Key[] next;
 
320
                        internal int len;
 
321
                        internal int hash;
 
322
                        internal int offset;
 
323
                }
 
324
 
 
325
                internal BlobHeap()
 
326
                {
 
327
                        buf.Write((byte)0);
 
328
                }
 
329
 
 
330
                internal int Add(ByteBuffer bb)
 
331
                {
 
332
                        Debug.Assert(!frozen);
 
333
                        int bblen = bb.Length;
 
334
                        if (bblen == 0)
 
335
                        {
 
336
                                return 0;
 
337
                        }
 
338
                        int lenlen = MetadataWriter.GetCompressedUIntLength(bblen);
 
339
                        int hash = bb.Hash();
 
340
                        int index = (hash & 0x7FFFFFFF) % map.Length;
 
341
                        Key[] keys = map;
 
342
                        int last = index;
 
343
                        while (keys[index].offset != 0)
 
344
                        {
 
345
                                if (keys[index].hash == hash
 
346
                                        && keys[index].len == bblen
 
347
                                        && buf.Match(keys[index].offset + lenlen, bb, 0, bblen))
 
348
                                {
 
349
                                        return keys[index].offset;
 
350
                                }
 
351
                                if (index == last)
 
352
                                {
 
353
                                        if (keys[index].next == null)
 
354
                                        {
 
355
                                                keys[index].next = new Key[4];
 
356
                                                keys = keys[index].next;
 
357
                                                index = 0;
 
358
                                                break;
 
359
                                        }
 
360
                                        keys = keys[index].next;
 
361
                                        index = -1;
 
362
                                        last = keys.Length - 1;
 
363
                                }
 
364
                                index++;
 
365
                        }
 
366
                        int offset = buf.Position;
 
367
                        buf.WriteCompressedUInt(bblen);
 
368
                        buf.Write(bb);
 
369
                        keys[index].len = bblen;
 
370
                        keys[index].hash = hash;
 
371
                        keys[index].offset = offset;
 
372
                        return offset;
 
373
                }
 
374
 
 
375
                protected override int GetLength()
 
376
                {
 
377
                        return buf.Position;
 
378
                }
 
379
 
 
380
                protected override void WriteImpl(MetadataWriter mw)
 
381
                {
 
382
                        mw.Write(buf);
 
383
                }
 
384
 
 
385
                internal bool IsEmpty
 
386
                {
 
387
                        get { return buf.Position == 1; }
 
388
                }
 
389
 
 
390
                internal IKVM.Reflection.Reader.ByteReader GetBlob(int blobIndex)
 
391
                {
 
392
                        return buf.GetBlob(blobIndex);
 
393
                }
 
394
        }
 
395
}