eval/eval-util.cpp

   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 #include "avmplus.h"
  41
  42 #ifdef VMCFG_EVAL
  43
  44 #include "eval.h"
  45
  46 namespace avmplus
  47 {
  48     namespace RTC
  49     {
  50         int Str::compareTo(Str* other)
  51         {
  52             uint32_t llen = this->length;
  53             uint32_t rlen = other->length;
  54             uint32_t len = llen < rlen ? llen : rlen;
  55             wchar* s = this->s;
  56             wchar* t = other->s;
  57             wchar* limit = s + len;
  58             while (s < limit && *s == *t)
  59                 s++, t++;
  60             if (s < limit)
  61                 return int(*s) - int(*t);
  62             if (llen < rlen)
  63                 return -1;
  64             if (llen > rlen)
  65                 return 1;
  66             return 0;
  67         }
  68
  69         Allocator::Allocator(Compiler* compiler)
  70             : compiler(compiler)
  71             , free_sbchunks(NULL)
  72             , current_chunk(NULL)
  73             , current_top(NULL)
  74             , current_limit(NULL)
  75         {
  76             AvmAssert(offsetof(Chunk, data) % 8 == 0);
  77             // Do not refill yet; the first allocation is likely to be the hashtable
  78             // and that's sometimes large, so the first segment would sometimes
  79             // simply be lost.
  80         }
  81
  82         Allocator::~Allocator()
  83         {
  84             while (current_chunk != NULL)
  85             {
  86                 Chunk* tmp = current_chunk;
  87                 current_chunk = current_chunk->prev;
  88                 delete [] tmp;
  89             }
  90         }
  91
  92         void Allocator::refill(size_t nbytes)
  93         {
  94             union {
  95                 uint8_t* c_8;
  96                 Chunk* c;
  97             };
  98             c_8 = new uint8_t[sizeof(Chunk) + nbytes - 1];
  99             c->prev = current_chunk;
 100             current_chunk = c;
 101             current_top = c->data;
 102             current_limit = c->data + nbytes;
 103         }
 104
 105         void* Allocator::allocSlow(size_t nbytes)
 106         {
 107             AvmAssert(nbytes % 8 == 0);
 108             if (current_top + nbytes > current_limit)
 109                 refill(nbytes);
 110             AvmAssert(current_top + nbytes <= current_limit);
 111             void *p = current_top;
 112             current_top += nbytes;
 113             return p;
 114         }
 115
 116         template<class T> void SeqBuilder<T>::addAtEnd(T item)
 117         {
 118             Seq<T>* e = ALLOC(Seq<T>, (item));
 119             if (last == NULL)
 120                 items = e;
 121             else
 122                 last->tl = e;
 123             last = e;
 124         }
 125
 126         template<class T> T SeqBuilder<T>::dequeue()
 127         {
 128             AvmAssert(items != NULL);
 129             T v = items->hd;
 130             items = items->tl;
 131             if (items == NULL)
 132                 last = NULL;
 133             return v;
 134         }
 135
 136         // At least Xcode requires explicit instantiation.
 137
 138         template class SeqBuilder<double>;
 139         template class SeqBuilder<int32_t>;
 140         template class SeqBuilder<uint32_t>;
 141
 142         template class SeqBuilder<ABCClassInfo*>;
 143         template class SeqBuilder<ABCExceptionInfo*>;
 144         template class SeqBuilder<ABCInstanceInfo*>;
 145         template class SeqBuilder<ABCMetadataInfo*>;
 146         template class SeqBuilder<ABCMethodInfo*>;
 147         template class SeqBuilder<ABCMethodBodyInfo*>;
 148         template class SeqBuilder<ABCMultinameInfo*>;
 149         template class SeqBuilder<ABCNamespaceInfo*>;
 150         template class SeqBuilder<ABCNamespaceSetInfo*>;
 151         template class SeqBuilder<ABCScriptInfo*>;
 152         template class SeqBuilder<ABCTrait*>;
 153         template class SeqBuilder<Binding*>;
 154         template class SeqBuilder<CaseClause*>;
 155         template class SeqBuilder<CatchClause*>;
 156         template class SeqBuilder<DefaultValue*>;
 157         template class SeqBuilder<Expr*>;
 158         template class SeqBuilder<FunctionDefn*>;
 159         template class SeqBuilder<FunctionParam*>;
 160         template class SeqBuilder<Label*>;
 161         template class SeqBuilder<LiteralField*>;
 162         template class SeqBuilder<Namespace*>;
 163         template class SeqBuilder<NamespaceDefn*>;
 164         template class SeqBuilder<Stmt*>;
 165         template class SeqBuilder<Str*>;
 166
 167         StringBuilder::StringBuilder(Compiler* compiler)
 168             : allocator(compiler->allocator)
 169             , chunk(NULL)
 170         {
 171             clear();
 172         }
 173
 174         StringBuilder::~StringBuilder()
 175         {
 176             while (chunk != NULL)
 177                 popChunk();
 178         }
 179
 180         void StringBuilder::clear()
 181         {
 182             len = 0;
 183             nextchar = 0;
 184             if (chunk == NULL)
 185                 pushChunk();
 186             while (chunk->next != NULL)
 187                 popChunk();
 188         }
 189
 190         void StringBuilder::append(StringBuilder* other)
 191         {
 192             append(other->chunk->next);
 193             append(other->chunk->data, other->chunk->data + other->nextchar);
 194         }
 195
 196         void StringBuilder::append(Str* other)
 197         {
 198             append(other->s, other->s + other->length);
 199         }
 200
 201         void StringBuilder::append(const char* other)
 202         {
 203             while (*other != 0)
 204                 append(*other++);
 205         }
 206
 207         void StringBuilder::append(const wchar* ptr, const wchar* lim)
 208         {
 209             if (lim == NULL) {
 210                 lim = ptr;
 211                 while (*lim != 0)
 212                     lim++;
 213             }
 214             while (ptr < lim) {
 215                 uint32_t avail = SBChunk::chunksize - nextchar;
 216                 uint32_t need = uint32_t(lim - ptr);
 217                 uint32_t k = min(need, avail);
 218                 VMPI_memcpy(chunk->data + nextchar, ptr, k*sizeof(wchar));
 219                 ptr += k;
 220                 nextchar += k;
 221                 len += k;
 222                 if (ptr < lim) {
 223                     pushChunk();
 224                     nextchar = 0;
 225                 }
 226             }
 227         }
 228
 229         void StringBuilder::append(int c)
 230         {
 231             wchar c2 = (wchar)c;
 232             append(&c2, (&c2) + 1);
 233         }
 234
 235         Str* StringBuilder::str()
 236         {
 237             if (chunk->next == NULL)
 238                 return allocator->compiler->intern(chunk->data, len);
 239
 240             wchar* buf = new wchar[len];
 241             wchar* p = copyInto(buf, chunk->next);
 242             VMPI_memcpy(p, chunk->data, nextchar*sizeof(wchar));
 243             Str* result = allocator->compiler->intern(buf, len);
 244             delete [] buf;
 245             return result;
 246         }
 247
 248         char* StringBuilder::chardata()
 249         {
 250             char *buf = (char*)allocator->alloc(len+1);
 251             char *p = copyInto(buf, chunk->next);
 252             for ( uint32_t i=0 ; i < nextchar ; i++ )
 253                 p[i] = (char)(chunk->data[i] & 127);
 254             p += nextchar;
 255             *p = 0;
 256             return buf;
 257         }
 258
 259         void StringBuilder::append(SBChunk* other)
 260         {
 261             if (other != NULL) {
 262                 append(other->next);
 263                 append(other->data, other->data + SBChunk::chunksize);
 264             }
 265         }
 266
 267         wchar* StringBuilder::copyInto(wchar* buf, SBChunk* c)
 268         {
 269             if (c == NULL)
 270                 return buf;
 271
 272             wchar *p = buf;
 273             if (c->next != NULL)
 274                 p = copyInto(buf, c->next);
 275             VMPI_memcpy(p, c->data, SBChunk::chunksize*sizeof(wchar));
 276             return p+SBChunk::chunksize;
 277         }
 278
 279         char* StringBuilder::copyInto(char* buf, SBChunk* c)
 280         {
 281             if (c == NULL)
 282                 return buf;
 283
 284             char *p = buf;
 285             if (c->next != NULL)
 286                 p = copyInto(buf, c->next);
 287             for ( int i=0 ; i < SBChunk::chunksize ; i++ )
 288                 p[i] = (char)(chunk->data[i] & 127);
 289             return p+SBChunk::chunksize;
 290         }
 291
 292         void StringBuilder::pushChunk()
 293         {
 294             SBChunk* c;
 295             if (allocator->free_sbchunks != NULL) {
 296                 c = allocator->free_sbchunks;
 297                 allocator->free_sbchunks = allocator->free_sbchunks->next;
 298             }
 299             else
 300                 c = ALLOC(SBChunk, ());
 301             c->next = chunk;
 302             chunk = c;
 303         }
 304
 305         void StringBuilder::popChunk()
 306         {
 307             SBChunk* c = chunk;
 308             chunk = chunk->next;
 309             c->next = allocator->free_sbchunks;
 310             allocator->free_sbchunks = c;
 311         }
 312
 313 #ifdef DEBUG
 314
 315         char* getn(char* buf, const Str* s, size_t limit)
 316         {
 317             int chars = int(s->length < limit-1 ? s->length : limit-1);
 318             const wchar* p;
 319             char* q;
 320             for ( p=s->s, q=buf ; chars >= 0 ; chars-- )
 321                 *q++ = (char)*p++;
 322             *q = 0;
 323             return buf;
 324         }
 325
 326 #endif
 327
 328         uint32_t hashString(const wchar* chars, uint32_t nchars)
 329         {
 330             // See http://www.cse.yorku.ca/~oz/hash.html; this is the djb2 algorithm
 331             uint32_t h = 5381;
 332             for ( uint32_t i=0 ; i < nchars ; i++ )
 333                 h = ((h << 5) + h) + chars[i];
 334             return h;
 335         }
 336
 337         uint32_t lenU30(uint32_t val)
 338         {
 339             if( val < 0x80 )
 340                 return 1;
 341             if ( val < 0x4000 )
 342                 return 2;
 343             if ( val < 0x200000 )
 344                 return 3;
 345             if ( val < 0x10000000 )
 346                 return 4;
 347             return 5;
 348         }
 349
 350         uint8_t* emitU32(uint8_t* out, uint32_t val)
 351         {
 352             if( val < 0x80 ) {
 353                 *out++ = val & 0x7F;
 354             }
 355             else if ( val < 0x4000 ) {
 356                 *out++ = (val & 0x7F) | 0x80;
 357                 *out++ = (val >> 7) & 0x7F;
 358             }
 359             else if ( val < 0x200000 ) {
 360                 *out++ = (val & 0x7F) | 0x80;
 361                 *out++ = ((val >> 7) & 0x7F) | 0x80;
 362                 *out++ = (val >> 14) & 0x7F;
 363             }
 364             else if ( val < 0x10000000 ) {
 365                 *out++ = (val & 0x7F) | 0x80;
 366                 *out++ = ((val >> 7) & 0x7F) | 0x80;
 367                 *out++ = ((val >> 14) & 0x7F) | 0x80;
 368                 *out++ = (val >> 21) & 0x7F;
 369             }
 370             else {
 371                 *out++ = (val & 0x7F) | 0x80;
 372                 *out++ = ((val >> 7) & 0x7F) | 0x80;
 373                 *out++ = ((val >> 14) & 0x7F) | 0x80;
 374                 *out++ = ((val >> 21) & 0x7F) | 0x80;
 375                 *out++ = (val >> 28) & 0x7F;
 376             }
 377             return out;
 378         }
 379
 380         uint8_t* emitDouble(uint8_t* out, double d)
 381         {
 382             double_overlay v(d);
 383             out[0] = uint8_t(v.words.lsw);
 384             out[1] = uint8_t(v.words.lsw >> 8);
 385             out[2] = uint8_t(v.words.lsw >> 16);
 386             out[3] = uint8_t(v.words.lsw >> 24);
 387             out[4] = uint8_t(v.words.msw);
 388             out[5] = uint8_t(v.words.msw >> 8);
 389             out[6] = uint8_t(v.words.msw >> 16);
 390             out[7] = uint8_t(v.words.msw >> 24);
 391             return out + 8;
 392         }
 393
 394         uint8_t* emitS24(uint8_t* out, int32_t s)
 395         {
 396             *out++ = (s & 255);
 397             *out++ = (s >> 8) & 255;
 398             *out++ = (s >> 16) & 255;
 399             return out;
 400         }
 401
 402         int32_t readS24(uint8_t* in)
 403         {
 404             return ((in[0] | (in[1] << 8) | (in[2] << 16)) << 8) >> 8;
 405         }
 406
 407         uint32_t utf8length(Str* str)
 408         {
 409             uint32_t len = 0;
 410
 411             for ( wchar *s=str->s, *l=str->s + str->length ; s < l ; s++ ) {
 412                 if (*s <= 0x7F)
 413                     len += 1;
 414                 else if (*s <= 0x7FF)
 415                     len += 2;
 416                 else
 417                     len += 3;
 418             }
 419             return len;
 420         }
 421
 422         // duplicates formatUtf8 below???
 423         uint8_t* emitUtf8(uint8_t* out, Str* str)
 424         {
 425             for ( wchar *s=str->s, *l=str->s + str->length ; s < l ; s++ ) {
 426                 wchar c = *s;
 427                 if (c <= 0x7F)
 428                     *out++ = (uint8_t)c;
 429                 else if (c <= 0x7FF) {
 430                     *out++ = 0xC0 | ((c >> 6) & 0x1F);
 431                     *out++ = 0x80 | (c & 0x3F);
 432                 }
 433                 else {
 434                     *out++ = 0xE0 | ((c >> 12) & 0x0F);
 435                     *out++ = 0x80 | ((c >> 6) & 0x3F);
 436                     *out++ = 0x80 | (c & 0x3F);
 437                 }
 438             }
 439             return out;
 440         }
 441
 442         ByteBuffer::ByteBuffer(Allocator* allocator, uint32_t increment)
 443             : allocator(allocator)
 444             , increment(increment)
 445             , out(NULL)
 446             , limit(NULL)
 447             , first(NULL)
 448             , last(NULL)
 449             , size_rest(0)
 450         {
 451         }
 452
 453         void ByteBuffer::makeRoomSlow(uint32_t nbytes)
 454         {
 455             if (last != NULL) {
 456                 size_rest = size();
 457                 last->end = out;
 458             }
 459             uint32_t k = nbytes > increment ? nbytes : increment;
 460             Chunk* c = (Chunk*)allocator->alloc(sizeof(Chunk) + k - 1);
 461             c->next = NULL;
 462             out = c->start;
 463             limit = c->start + k;
 464             AvmAssert( (uint32_t)(limit - out) >= nbytes );
 465             if (last != NULL)
 466                 last->next = c;
 467             else
 468                 first = c;
 469             last = c;
 470         }
 471
 472         void ByteBuffer::serialize(uint8_t* b) const
 473         {
 474             if (last != NULL) {
 475                 last->end = out;
 476                 for ( Chunk* c = first ; c != NULL ; c = c->next ) {
 477                     VMPI_memcpy( b, c->start, c->end - c->start );
 478                     b += c->end - c->start;
 479                 }
 480             }
 481         }
 482
 483         void formatUtf8(char *buf, size_t bufsiz, const wchar* s)
 484         {
 485             AvmAssert(bufsiz > 0);
 486             char *limit = buf + bufsiz;
 487             wchar c;
 488             while ((c = *s++) != 0)
 489             {
 490                 if (c < 0x80) {
 491                     if (buf+1 >= limit)
 492                         break;
 493                     *buf++ = (char)c;
 494                 }
 495                 else if (c < 0x800) {
 496                     if (buf+2 >= limit)
 497                         break;
 498                     *buf++ = 0xC0 | ((c >> 6) & 31);
 499                     *buf++ = 0x80 | (c & 63);
 500                 }
 501                 else if (c >= 0xD800 && c <= 0xDBFF) {
 502                     wchar d = *s++;
 503                     if (d >= 0xDC00 && d <= 0xDCFF) {
 504                         // surrogate pair
 505                         if (buf+4 >= limit)
 506                             break;
 507                         wchar u = ((c >> 6) & 15) + 1;
 508                         *buf++ = (char)(0xF0 | (u >> 2));
 509                         *buf++ = 0x80 | ((u & 3) << 4) | ((c >> 2) & 15);
 510                         *buf++ = 0x80 | ((c & 3) << 4) | ((d >> 6) & 15);
 511                         *buf++ = 0x80 | (d & 63);
 512                     }
 513                     else {
 514                         // error, really
 515                         if (buf+1 >= limit)
 516                             break;
 517                         *buf++ = '?';
 518                         s--;
 519                     }
 520                 }
 521                 else if (c >= 0xDC00 && c <= 0xDCFF) {
 522                     // error, really
 523                     if (buf+1 >= limit)
 524                         break;
 525                     *buf++ = '?';
 526                 }
 527                 else {
 528                     if (buf+3 >= limit)
 529                         break;
 530                     *buf++ = 0xE0 | ((c >> 12) & 15);
 531                     *buf++ = 0x80 | ((c >> 6) & 63);
 532                     *buf++ = 0x80 | (c & 63);
 533                 }
 534             }
 535             AvmAssert(buf < limit);
 536             *buf = 0;
 537         }
 538     }
 539 }
 540
 541 #endif // VMCFG_EVAL