mcs/class/IKVM.Reflection/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.GetCompressedIntLength(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.WriteCompressedInt(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.GetCompressedIntLength(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.WriteCompressedInt(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 }