eval/eval-util.h

   1 /* -*- Mode: C++; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 4 -*- */
   2 /* vi: set ts=4 sw=4 expandtab: (add to ~/.vimrc: set modeline modelines=5) */
   3 /* ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is [Open Source Virtual Machine.].
  17  *
  18  * The Initial Developer of the Original Code is
  19  * Adobe System Incorporated.
  20  * Portions created by the Initial Developer are Copyright (C) 2008
  21  * the Initial Developer. All Rights Reserved.
  22  *
  23  * Contributor(s):
  24  *   Adobe AS3 Team
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either the GNU General Public License Version 2 or later (the "GPL"), or
  28  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 // This file is included into eval.h
  41 namespace avmplus {
  42 namespace RTC {
  43
  44 // Utility functions
  45
  46 /**
  47  * Simple string.  Always allocated inside an Allocator heap.  Always NUL-terminated
  48  * for debugging convenience.
  49  */
  50
  51 class Str {
  52 public:
  53     uint32_t    length;     // number of chars excluding NUL
  54     uint32_t    hash;       // hash code
  55     uint32_t    ident;      // ~0 or the index in the string pool
  56     Str*        next;       // next in hashtable bucket
  57     wchar       s[1];       // actually longer
  58
  59     // Returns < 0 if this < other, 0 if this == other, > 0 if this > other.
  60     // Don't use this for comparing for equality, just use == instead: a Str
  61     // is always interned.
  62     int compareTo(Str* other);
  63 };
  64
  65 uint32_t hashString(const wchar* chars, uint32_t nchars);
  66 uint32_t lenU30(uint32_t val);
  67 uint32_t utf8length(Str* str);
  68 uint8_t* emitU16(uint8_t* out, uint16_t val);
  69 uint8_t* emitU32(uint8_t* out, uint32_t val);
  70 uint8_t* emitU30(uint8_t* out, uint32_t val);
  71 uint8_t* emitS32(uint8_t* out, int32_t val);
  72 uint8_t* emitS24(uint8_t* out, int32_t val);
  73 uint8_t* emitDouble(uint8_t* out, double d);
  74 uint8_t* emitUtf8(uint8_t* out, Str* s);
  75
  76 int32_t readS24(uint8_t* in);
  77
  78 void formatUtf8(char* buf, size_t bufsiz, const wchar* s);
  79
  80 #ifdef DEBUG
  81 // Get up to limit-1 characters from s into buf, chop high bits, NUL-terminate, return buf
  82 char* getn(char* buf, const Str* s, size_t limit);
  83 #endif
  84
  85 inline uint32_t min(uint32_t a, uint32_t b) { return a < b ? a : b; }
  86 inline uint32_t max(uint32_t a, uint32_t b) { return a > b ? a : b; }
  87
  88 inline int32_t min(int32_t a, int32_t b) { return a < b ? a : b; }
  89 inline int32_t max(int32_t a, int32_t b) { return a > b ? a : b; }
  90
  91 /**
  92  * Convenience wrapper for accumulating string values for
  93  * identifiers, strings, regular expressions, xml text.
  94  */
  95
  96 class SBChunk {
  97 public:
  98     enum {
  99         chunksize = 100
 100     };
 101
 102     wchar data[chunksize];
 103     SBChunk* next;
 104 };
 105
 106 class StringBuilder {
 107 public:
 108     StringBuilder(Compiler* compiler);
 109     ~StringBuilder();
 110
 111     void clear();
 112     void append(Str* other);
 113     void append(const char* other);
 114     void append(StringBuilder* other);
 115     void append(const wchar* ptr, const wchar* lim);
 116     void append(int c);
 117     uint32_t length();
 118     Str* str();
 119     char *chardata();           // NUL-terminated array, freshly allocated on every call.  Data are chopped to 7 bits.
 120
 121 private:
 122     void append(SBChunk* other);
 123     wchar* copyInto(wchar* buf, SBChunk* c);
 124     char* copyInto(char* buf, SBChunk* c);
 125     void pushChunk();
 126     void popChunk();
 127
 128     Allocator* const allocator;
 129     SBChunk* chunk;             // current chunk
 130     uint32_t nextchar;          // next free char in chunk
 131     uint32_t len;               // total length
 132 };
 133
 134
 135 /**
 136  * Bump-a-pointer allocator.
 137  *
 138  * Used for all allocation by the run-time compiler except the allocation for the
 139  * final ABC bytevector.
 140  *
 141  * FIXME: The allocator is a little prone to internal fragmentation on the
 142  * block level.  This is because fairly large blocks at the end of a segment
 143  * may be lost if a large request comes in and causes a new segment to be allocated.
 144  * We can fix that with a simple free list of large blocks, if it turns out
 145  * to be a problem in practice, or we can make the growth increment relatively
 146  * larger.
 147  */
 148 class Allocator {
 149 public:
 150     Allocator(Compiler* compiler);
 151     ~Allocator();
 152
 153     void* alloc(size_t nbytes);
 154
 155     Compiler* const compiler;
 156     SBChunk* free_sbchunks; // shared among all StringBuilders working off this allocator
 157
 158 private:
 159     void* allocSlow(size_t nbytes);
 160     void refill(size_t nbytes);
 161
 162     class Chunk {
 163     public:
 164         Chunk* prev;
 165 #ifndef AVMPLUS_64BIT
 166         uintptr_t padding;
 167 #endif
 168         char data[1];
 169     };
 170
 171     Chunk* current_chunk;
 172     char* current_top;
 173     char* current_limit;
 174 };
 175
 176
 177 /**
 178  * Efficient accumulator for sequence of bytes.  check() checks for available
 179  * space and returns a valid output pointer for that many bytes; the number
 180  * of bytes requested may be larger than 'increment' but this should be the
 181  * exception, not the rule.  'increment' is the allocation quantum from the
 182  * underlying allocator; it should be a smallish fraction of the underlying
 183  * allocator's quantum.
 184  *
 185  * size() returns the number of bytes currently in the buffer.  serialize()
 186  * copies those into a sequential array starting at b.
 187  */
 188 class ByteBuffer {
 189 public:
 190     ByteBuffer(Allocator* allocator, uint32_t increment=100);
 191
 192     uint32_t size() const;
 193     void serialize(uint8_t* b) const;
 194
 195     void emitU8(uint8_t val);
 196     void emitS8(int8_t val);
 197     void emitU16(uint16_t val);
 198     void emitU32(uint32_t val);
 199     void emitU30(uint32_t val);
 200     void emitS32(int32_t val);
 201     void emitS24(int32_t val);
 202     void emitDouble(double d);
 203     void emitUtf8(uint32_t nbytes, Str* s);
 204
 205 private:
 206     class Chunk {
 207     public:
 208         uint8_t* end;
 209         Chunk* next;
 210         uint8_t start[1];       // actually longer
 211     };
 212
 213     Allocator * const allocator;
 214     const uint32_t increment;
 215     uint8_t* out;
 216     uint8_t* limit;
 217     Chunk* first;
 218     Chunk* last;
 219     uint32_t size_rest;     // collected size of the chunks not including last
 220
 221     void makeRoom(uint32_t nbytes);
 222     void makeRoomSlow(uint32_t nbytes);
 223 };
 224
 225 // This is useful if an allocator is in scope with the name "allocator"
 226 #define ALLOC(type, args)           \
 227     ::new (allocator->alloc(sizeof(type))) type args
 228
 229 template<class T> class Seq {
 230 public:
 231     Seq(T hd, Seq<T>* tl=NULL) : hd(hd), tl(tl) {}
 232     T       hd;
 233     Seq<T>* tl;
 234 };
 235
 236 template<class T> class SeqBuilder {
 237 public:
 238     SeqBuilder(Allocator* allocator) : allocator(allocator), items(NULL), last(NULL) {}
 239
 240     void addAtEnd(T item);  // enqueue
 241     T dequeue();            // drop and return the first element; queue must not be empty
 242     bool isEmpty();         // true iff queue is empty
 243     Seq<T>* get() const;    // return the elements in the queue, do not clear the queue
 244     void clear();           // reset the queue
 245
 246 private:
 247     Allocator* allocator;
 248     Seq<T>* items;
 249     Seq<T>* last;
 250 };
 251
 252 }}