src/vm/tables.c

   1 /* tables.c -
   2
   3    Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003
   4    R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser,
   5    M. Probst, S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck,
   6    P. Tomsich, J. Wenninger
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Reinhard Grafl
  28
  29    Changes: Mark Probst
  30             Andreas Krall
  31
  32    Contains support functions for:
  33        - Reading of Java class files
  34        - Unicode symbols
  35        - the heap
  36        - additional support functions
  37
  38    $Id: tables.c 753 2003-12-13 22:22:09Z twisti $
  39
  40 */
  41
  42 #include <string.h>
  43 #include <assert.h>
  44 #include <sys/types.h>
  45 #include <sys/mman.h>
  46 #include <unistd.h>
  47 #include "types.h"
  48 #include "global.h"
  49 #include "tables.h"
  50 #include "loader.h"
  51 #include "asmpart.h"
  52 #include "threads/thread.h"
  53 #include "threads/locks.h"
  54 #include "toolbox/loging.h"
  55 #include "toolbox/memory.h"
  56
  57
  58 /* statistics */
  59 int count_utf_len = 0;         /* size of utf hash                  */
  60 int count_utf_new = 0;         /* calls of utf_new                  */
  61 int count_utf_new_found  = 0;  /* calls of utf_new with fast return */
  62
  63 hashtable utf_hash;     /* hashtable for utf8-symbols */
  64 hashtable string_hash;  /* hashtable for javastrings  */
  65 hashtable class_hash;   /* hashtable for classes      */
  66
  67 /******************************************************************************
  68  *********************** hashtable functions **********************************
  69  ******************************************************************************/
  70
  71 /* hashsize must be power of 2 */
  72
  73 #define UTF_HASHSTART   16384   /* initial size of utf-hash */
  74 #define HASHSTART        2048   /* initial size of javastring and class-hash */
  75
  76
  77 /******************** function: init_hashtable ******************************
  78
  79     Initializes a hashtable structure and allocates memory.
  80     The parameter size specifies the initial size of the hashtable.
  81
  82 *****************************************************************************/
  83
  84 void init_hashtable(hashtable *hash, u4 size)
  85 {
  86         u4 i;
  87
  88         hash->entries = 0;
  89         hash->size    = size;
  90         hash->ptr     = MNEW(void*, size);
  91
  92         /* clear table */
  93         for (i = 0; i < size; i++) hash->ptr[i] = NULL;
  94 }
  95
  96 /*********************** function: tables_init  *****************************
  97
  98     creates hashtables for symboltables
  99         (called once at startup)
 100
 101 *****************************************************************************/
 102
 103 void tables_init ()
 104 {
 105         init_hashtable(&utf_hash,    UTF_HASHSTART);  /* hashtable for utf8-symbols */
 106         init_hashtable(&string_hash, HASHSTART);      /* hashtable for javastrings */
 107         init_hashtable(&class_hash,  HASHSTART);      /* hashtable for classes */
 108
 109 #ifdef STATISTICS
 110         count_utf_len += sizeof(utf*) * utf_hash.size;
 111 #endif
 112
 113 }
 114
 115 /********************** function: tables_close ******************************
 116
 117         free memory for hashtables
 118
 119 *****************************************************************************/
 120
 121 void tables_close (stringdeleter del)
 122 {
 123         utf *u;
 124         literalstring *s;
 125         u4 i;
 126
 127         /* dispose utf symbols */
 128         for (i=0; i<utf_hash.size; i++) {
 129                 u = utf_hash.ptr[i];
 130                 while (u) {
 131                         /* process elements in external hash chain */
 132                         utf *nextu = u->hashlink;
 133                         MFREE (u->text, u1, u->blength);
 134                         FREE (u, utf);
 135                         u = nextu;
 136                 }
 137         }
 138
 139         /* dispose javastrings */
 140         for (i=0; i<string_hash.size; i++) {
 141                 s = string_hash.ptr[i];
 142                 while (u) {
 143                         /* process elements in external hash chain */
 144                         literalstring *nexts = s->hashlink;
 145                         del(s->string);
 146                         FREE(s, literalstring);
 147                         s = nexts;
 148                 }
 149         }
 150
 151         /* dispose hashtable structures */
 152         MFREE (utf_hash.ptr,    void*, utf_hash.size);
 153         MFREE (string_hash.ptr, void*, string_hash.size);
 154         MFREE (class_hash.ptr,  void*, class_hash.size);
 155 }
 156
 157
 158 /********************* function: utf_display *********************************
 159
 160         write utf symbol to stdout (debugging purposes)
 161
 162 ******************************************************************************/
 163
 164 void utf_display(utf *u)
 165 {
 166     char *endpos  = utf_end(u);  /* points behind utf string       */
 167     char *utf_ptr = u->text;     /* current position in utf text   */
 168
 169         if (u == NULL)
 170                 return;
 171
 172     while (utf_ptr < endpos) {
 173                 /* read next unicode character */
 174                 u2 c = utf_nextu2(&utf_ptr);
 175                 if (c >= 32 && c <= 127) printf("%c", c);
 176                 else printf("?");
 177         }
 178
 179         fflush(stdout);
 180 }
 181
 182
 183 /************************* function: log_utf *********************************
 184
 185         log utf symbol
 186
 187 ******************************************************************************/
 188
 189 void log_utf(utf *u)
 190 {
 191         char buf[MAXLOGTEXT];
 192         utf_sprint(buf,u);
 193         dolog("%s",buf);
 194 }
 195
 196 /********************** function: log_plain_utf ******************************
 197
 198         log utf symbol (without printing "LOG: " and newline)
 199
 200 ******************************************************************************/
 201
 202 void log_plain_utf(utf *u)
 203 {
 204         char buf[MAXLOGTEXT];
 205         utf_sprint(buf,u);
 206         dolog_plain("%s",buf);
 207 }
 208
 209 /************************ function: utf_sprint *******************************
 210
 211     write utf symbol into c-string (debugging purposes)
 212
 213 ******************************************************************************/
 214
 215 void utf_sprint (char *buffer, utf *u)
 216 {
 217     char *endpos  = utf_end(u);  /* points behind utf string       */
 218     char *utf_ptr = u->text;     /* current position in utf text   */
 219     u2 pos = 0;                  /* position in c-string           */
 220
 221     while (utf_ptr<endpos)
 222                 /* copy next unicode character */
 223                 buffer[pos++] = utf_nextu2(&utf_ptr);
 224
 225     /* terminate string */
 226     buffer[pos] = '\0';
 227 }
 228
 229
 230 /********************* Funktion: utf_fprint **********************************
 231
 232     write utf symbol into file
 233
 234 ******************************************************************************/
 235
 236 void utf_fprint (FILE *file, utf *u)
 237 {
 238     char *endpos  = utf_end(u);  /* points behind utf string       */
 239     char *utf_ptr = u->text;     /* current position in utf text   */
 240     if (u==NULL) return;
 241     while (utf_ptr<endpos) {
 242                 /* read next unicode character */
 243                 u2 c = utf_nextu2(&utf_ptr);
 244
 245                 if (c>=32 && c<=127) fprintf (file,"%c",c);
 246                 else fprintf (file,"?");
 247         }
 248 }
 249
 250
 251 /****************** internal function: utf_hashkey ***************************
 252
 253         The hashkey is computed from the utf-text by using up to 8 characters.
 254         For utf-symbols longer than 15 characters 3 characters are taken from
 255         the beginning and the end, 2 characters are taken from the middle.
 256
 257 ******************************************************************************/
 258
 259 #define nbs(val) ((u4) *(++text) << val) /* get next byte, left shift by val  */
 260 #define fbs(val) ((u4) *(  text) << val) /* get first byte, left shift by val */
 261
 262 static u4 utf_hashkey (char *text, u4 length)
 263 {
 264         char *start_pos = text; /* pointer to utf text */
 265         u4 a;
 266
 267         switch (length) {
 268
 269         case 0: /* empty string */
 270                 return 0;
 271
 272         case 1: return fbs(0);
 273         case 2: return fbs(0) ^ nbs(3);
 274         case 3: return fbs(0) ^ nbs(3) ^ nbs(5);
 275         case 4: return fbs(0) ^ nbs(2) ^ nbs(4) ^ nbs(6);
 276         case 5: return fbs(0) ^ nbs(2) ^ nbs(3) ^ nbs(4) ^ nbs(6);
 277         case 6: return fbs(0) ^ nbs(1) ^ nbs(2) ^ nbs(3) ^ nbs(5) ^ nbs(6);
 278         case 7: return fbs(0) ^ nbs(1) ^ nbs(2) ^ nbs(3) ^ nbs(4) ^ nbs(5) ^ nbs(6);
 279         case 8: return fbs(0) ^ nbs(1) ^ nbs(2) ^ nbs(3) ^ nbs(4) ^ nbs(5) ^ nbs(6) ^ nbs(7);
 280
 281         case 9: a = fbs(0) ^ nbs(1) ^ nbs(2);
 282                 text++;
 283                 return a ^ nbs(4) ^ nbs(5) ^ nbs(6) ^ nbs(7) ^ nbs(8);
 284
 285         case 10: a = fbs(0);
 286                 text++;
 287                 a^= nbs(2) ^ nbs(3) ^ nbs(4);
 288                 text++;
 289                 return a ^ nbs(6) ^ nbs(7) ^ nbs(8) ^ nbs(9);
 290
 291         case 11: a = fbs(0);
 292                 text++;
 293                 a^= nbs(2) ^ nbs(3) ^ nbs(4);
 294                 text++;
 295                 return a ^ nbs(6) ^ nbs(7) ^ nbs(8) ^ nbs(9) ^ nbs(10);
 296
 297         case 12: a = fbs(0);
 298                 text+=2;
 299                 a^= nbs(2) ^ nbs(3);
 300                 text+=1;
 301                 a^= nbs(5) ^ nbs(6) ^ nbs(7);
 302                 text+=1;
 303                 return a ^ nbs(9) ^ nbs(10);
 304
 305         case 13: a = fbs(0) ^ nbs(1);
 306                 text+=1;
 307                 a^= nbs(3) ^ nbs(4);
 308                 text+=2;
 309                 a^= nbs(7) ^ nbs(8);
 310                 text+=2;
 311                 return a ^ nbs(9) ^ nbs(10);
 312
 313         case 14: a = fbs(0);
 314                 text+=2;
 315                 a^= nbs(3) ^ nbs(4);
 316                 text+=2;
 317                 a^= nbs(7) ^ nbs(8);
 318                 text+=2;
 319                 return a ^ nbs(9) ^ nbs(10) ^ nbs(11);
 320
 321         case 15: a = fbs(0);
 322                 text+=2;
 323                 a^= nbs(3) ^ nbs(4);
 324                 text+=2;
 325                 a^= nbs(7) ^ nbs(8);
 326                 text+=2;
 327                 return a ^ nbs(9) ^ nbs(10) ^ nbs(11);
 328
 329         default:  /* 3 characters from beginning */
 330                 a = fbs(0);
 331                 text+=2;
 332                 a^= nbs(3) ^ nbs(4);
 333
 334                 /* 2 characters from middle */
 335                 text = start_pos + (length / 2);
 336                 a^= fbs(5);
 337                 text+=2;
 338                 a^= nbs(6);
 339
 340                 /* 3 characters from end */
 341                 text = start_pos + length - 4;
 342
 343                 a^= fbs(7);
 344                 text+=1;
 345
 346                 return a ^ nbs(10) ^ nbs(11);
 347     }
 348 }
 349
 350
 351 /*************************** function: utf_hashkey ***************************
 352
 353     compute the hashkey of a unicode string
 354
 355 ******************************************************************************/
 356
 357 u4 unicode_hashkey (u2 *text, u2 len)
 358 {
 359         return utf_hashkey((char*) text, len);
 360 }
 361
 362 /************************ function: utf_new **********************************
 363
 364         Creates a new utf-symbol, the text of the symbol is passed as a
 365         u1-array. The function searches the utf-hashtable for a utf-symbol
 366         with this text. On success the element returned, otherwise a new
 367         hashtable element is created.
 368
 369         If the number of entries in the hashtable exceeds twice the size of the
 370         hashtable slots a reorganization of the hashtable is done and the utf
 371         symbols are copied to a new hashtable with doubled size.
 372
 373 ******************************************************************************/
 374
 375 utf *utf_new (char *text, u2 length)
 376 {
 377         u4 key;            /* hashkey computed from utf-text */
 378         u4 slot;           /* slot in hashtable */
 379         utf *u;            /* hashtable element */
 380         u2 i;
 381
 382 /*      log_text("utf_new entered");*/
 383 #ifdef STATISTICS
 384         count_utf_new++;
 385 #endif
 386
 387         key  = utf_hashkey (text, length);
 388         slot = key & (utf_hash.size-1);
 389         u    = utf_hash.ptr[slot];
 390
 391         /* search external hash chain for utf-symbol */
 392         while (u) {
 393                 if (u->blength == length) {
 394
 395                         /* compare text of hashtable elements */
 396                         for (i=0; i<length; i++)
 397                                 if (text[i] != u->text[i]) goto nomatch;
 398
 399 #ifdef STATISTICS
 400                         count_utf_new_found++;
 401 #endif
 402 /*                      log_text("symbol found in hash table");*/
 403                         /* symbol found in hashtable */
 404 /*                                      utf_display(u);
 405                                         {
 406                                                 utf blup;
 407                                                 blup.blength=length;
 408                                                 blup.text=text;
 409                                                 utf_display(&blup);
 410                                         }*/
 411                         return u;
 412                 }
 413         nomatch:
 414                 u = u->hashlink; /* next element in external chain */
 415         }
 416
 417 #ifdef STATISTICS
 418         count_utf_len += sizeof(utf) + length;
 419 #endif
 420
 421         /* location in hashtable found, create new utf element */
 422         u = NEW (utf);
 423         u->blength  = length;             /* length in bytes of utfstring */
 424         u->hashlink = utf_hash.ptr[slot]; /* link in external hashchain   */
 425         u->text     = mem_alloc(length/*JOWENN*/+1);  /* allocate memory for utf-text */
 426         memcpy(u->text,text,length);      /* copy utf-text                */
 427         u->text[length]='\0';/*JOWENN*/
 428         utf_hash.ptr[slot] = u;           /* insert symbol into table     */
 429
 430         utf_hash.entries++;               /* update number of entries     */
 431
 432         if ( utf_hash.entries > (utf_hash.size*2)) {
 433
 434         /* reorganization of hashtable, average length of
 435            the external chains is approx. 2                */
 436
 437                 u4 i;
 438                 utf *u;
 439                 hashtable newhash; /* the new hashtable */
 440
 441                 /* create new hashtable, double the size */
 442                 init_hashtable(&newhash, utf_hash.size*2);
 443                 newhash.entries=utf_hash.entries;
 444
 445 #ifdef STATISTICS
 446                 count_utf_len += sizeof(utf*) * utf_hash.size;
 447 #endif
 448
 449                 /* transfer elements to new hashtable */
 450                 for (i=0; i<utf_hash.size; i++) {
 451                         u = (utf*) utf_hash.ptr[i];
 452                         while (u) {
 453                                 utf *nextu = u -> hashlink;
 454                                 u4 slot = (utf_hashkey(u->text,u->blength)) & (newhash.size-1);
 455
 456                                 u->hashlink = (utf*) newhash.ptr[slot];
 457                                 newhash.ptr[slot] = u;
 458
 459                                 /* follow link in external hash chain */
 460                                 u = nextu;
 461                         }
 462                 }
 463
 464                 /* dispose old table */
 465                 MFREE (utf_hash.ptr, void*, utf_hash.size);
 466                 utf_hash = newhash;
 467         }
 468                 /*utf_display(u);*/
 469         return u;
 470 }
 471
 472
 473 /********************* function: utf_new_char ********************************
 474
 475     creates a new utf symbol, the text for this symbol is passed
 476     as a c-string ( = char* )
 477
 478 ******************************************************************************/
 479
 480 utf *utf_new_char (char *text)
 481 {
 482         return utf_new(text, strlen(text));
 483 }
 484
 485
 486 /********************* function: utf_new_char ********************************
 487
 488     creates a new utf symbol, the text for this symbol is passed
 489     as a c-string ( = char* )
 490     "." characters are going to be replaced by "/". since the above function is
 491     used often, this is a separte function, instead of an if
 492
 493 ******************************************************************************/
 494
 495 utf *utf_new_char_classname (char *text)
 496 {
 497         if (strchr(text,'.')) {
 498                 char *txt=strdup(text);
 499                 char *end=txt+strlen(txt);
 500                 char *c;
 501                 utf *tmpRes;
 502                 for (c=txt;c<end;c++)
 503                         if (*c=='.') *c='/';
 504                 tmpRes=utf_new(txt,strlen(txt));
 505                 free(txt);
 506                 return tmpRes;
 507         }
 508         else
 509         return utf_new(text, strlen(text));
 510 }
 511
 512 /************************** Funktion: utf_show ******************************
 513
 514     writes the utf symbols in the utfhash to stdout and
 515     displays the number of external hash chains grouped
 516     according to the chainlength
 517     (debugging purposes)
 518
 519 *****************************************************************************/
 520
 521 void utf_show ()
 522 {
 523
 524 #define CHAIN_LIMIT 20               /* limit for seperated enumeration */
 525
 526         u4 chain_count[CHAIN_LIMIT]; /* numbers of chains */
 527         u4 max_chainlength = 0;      /* maximum length of the chains */
 528         u4 sum_chainlength = 0;      /* sum of the chainlengths */
 529         u4 beyond_limit = 0;         /* number of utf-symbols in chains with length>=CHAIN_LIMIT-1 */
 530         u4 i;
 531
 532         printf ("UTF-HASH:\n");
 533
 534         /* show element of utf-hashtable */
 535         for (i=0; i<utf_hash.size; i++) {
 536                 utf *u = utf_hash.ptr[i];
 537                 if (u) {
 538                         printf ("SLOT %d: ", (int) i);
 539                         while (u) {
 540                                 printf ("'");
 541                                 utf_display (u);
 542                                 printf ("' ");
 543                                 u = u->hashlink;
 544                         }
 545                         printf ("\n");
 546                 }
 547
 548         }
 549
 550         printf ("UTF-HASH: %d slots for %d entries\n",
 551                         (int) utf_hash.size, (int) utf_hash.entries );
 552
 553
 554         if (utf_hash.entries == 0)
 555                 return;
 556
 557         printf("chains:\n  chainlength    number of chains    %% of utfstrings\n");
 558
 559         for (i=0;i<CHAIN_LIMIT;i++)
 560                 chain_count[i]=0;
 561
 562         /* count numbers of hashchains according to their length */
 563         for (i=0; i<utf_hash.size; i++) {
 564
 565                 utf *u = (utf*) utf_hash.ptr[i];
 566                 u4 chain_length = 0;
 567
 568                 /* determine chainlength */
 569                 while (u) {
 570                         u = u->hashlink;
 571                         chain_length++;
 572                 }
 573
 574                 /* update sum of all chainlengths */
 575                 sum_chainlength+=chain_length;
 576
 577                 /* determine the maximum length of the chains */
 578                 if (chain_length>max_chainlength)
 579                         max_chainlength = chain_length;
 580
 581                 /* update number of utf-symbols in chains with length>=CHAIN_LIMIT-1 */
 582                 if (chain_length>=CHAIN_LIMIT) {
 583                         beyond_limit+=chain_length;
 584                         chain_length=CHAIN_LIMIT-1;
 585                 }
 586
 587                 /* update number of hashchains of current length */
 588                 chain_count[chain_length]++;
 589         }
 590
 591         /* display results */
 592         for (i=1;i<CHAIN_LIMIT-1;i++)
 593                 printf("       %2d %17d %18.2f%%\n",i,chain_count[i],(((float) chain_count[i]*i*100)/utf_hash.entries));
 594
 595         printf("     >=%2d %17d %18.2f%%\n",CHAIN_LIMIT-1,chain_count[CHAIN_LIMIT-1],((float) beyond_limit*100)/utf_hash.entries);
 596
 597
 598         printf("max. chainlength:%5d\n",max_chainlength);
 599
 600         /* avg. chainlength = sum of chainlengths / number of chains */
 601         printf("avg. chainlength:%5.2f\n",(float) sum_chainlength / (utf_hash.size-chain_count[0]));
 602 }
 603
 604 /******************************************************************************
 605 *********************** Misc support functions ********************************
 606 ******************************************************************************/
 607
 608
 609 /******************** Function: desc_to_type **********************************
 610
 611         Determines the corresponding Java base data type for a given type
 612         descriptor.
 613
 614 ******************************************************************************/
 615
 616 u2 desc_to_type(utf *descriptor)
 617 {
 618         char *utf_ptr = descriptor->text;  /* current position in utf text */
 619         char logtext[MAXLOGTEXT];
 620
 621         if (descriptor->blength < 1) panic("Type-Descriptor is empty string");
 622
 623         switch (*utf_ptr++) {
 624         case 'B':
 625         case 'C':
 626         case 'I':
 627         case 'S':
 628         case 'Z':  return TYPE_INT;
 629         case 'D':  return TYPE_DOUBLE;
 630         case 'F':  return TYPE_FLOAT;
 631         case 'J':  return TYPE_LONG;
 632         case 'L':
 633         case '[':  return TYPE_ADDRESS;
 634         }
 635
 636         sprintf(logtext, "Invalid Type-Descriptor: ");
 637         utf_sprint(logtext+strlen(logtext), descriptor);
 638         error(logtext);
 639
 640         return 0;
 641 }
 642
 643
 644 /********************** Function: desc_typesize *******************************
 645
 646         Calculates the lenght in bytes needed for a data element of the type given
 647         by its type descriptor.
 648
 649 ******************************************************************************/
 650
 651 u2 desc_typesize (utf *descriptor)
 652 {
 653         switch (desc_to_type(descriptor)) {
 654         case TYPE_INT:     return 4;
 655         case TYPE_LONG:    return 8;
 656         case TYPE_FLOAT:   return 4;
 657         case TYPE_DOUBLE:  return 8;
 658         case TYPE_ADDRESS: return sizeof(voidptr);
 659         default:           return 0;
 660         }
 661 }
 662
 663
 664 /********************** function: utf_nextu2 *********************************
 665
 666     read the next unicode character from the utf string and
 667     increment the utf-string pointer accordingly
 668
 669 ******************************************************************************/
 670
 671 u2 utf_nextu2(char **utf_ptr)
 672 {
 673     /* uncompressed unicode character */
 674     u2 unicode_char;
 675     /* current position in utf text */
 676     unsigned char *utf = (unsigned char *) (*utf_ptr);
 677     /* bytes representing the unicode character */
 678     unsigned char ch1, ch2, ch3;
 679     /* number of bytes used to represent the unicode character */
 680     int len;
 681
 682     switch ((ch1 = utf[0]) >> 4) {
 683         default: /* 1 byte */
 684                 (*utf_ptr)++;
 685                 return ch1;
 686         case 0xC:
 687         case 0xD: /* 2 bytes */
 688                 if (((ch2 = utf[1]) & 0xC0) == 0x80) {
 689                         unsigned char high = ch1 & 0x1F;
 690                         unsigned char low  = ch2 & 0x3F;
 691                         unicode_char = (high << 6) + low;
 692                         len = 2;
 693                 }
 694                 break;
 695
 696         case 0xE: /* 2 or 3 bytes */
 697                 if (((ch2 = utf[1]) & 0xC0) == 0x80) {
 698                         if (((ch3 = utf[2]) & 0xC0) == 0x80) {
 699                                 unsigned char low  = ch3 & 0x3f;
 700                                 unsigned char mid  = ch2 & 0x3f;
 701                                 unsigned char high = ch1 & 0x0f;
 702                                 unicode_char = (((high << 6) + mid) << 6) + low;
 703                                 len = 3;
 704                         } else
 705                                 len = 2;
 706                 }
 707                 break;
 708     }
 709
 710     /* update position in utf-text */
 711     *utf_ptr = (char *) (utf + len);
 712     return unicode_char;
 713 }
 714
 715 /********************* function: is_valid_utf ********************************
 716
 717     return true if the given string is a valid UTF-8 string
 718
 719     utf_ptr...points to first character
 720     end_pos...points after last character
 721
 722 ******************************************************************************/
 723
 724 static unsigned long min_codepoint[6] = {0,1L<<7,1L<<11,1L<<16,1L<<21,1L<<26};
 725
 726 bool
 727 is_valid_utf(char *utf_ptr,char *end_pos)
 728 {
 729         int bytes;
 730         int len,i;
 731         char c;
 732         unsigned long v;
 733
 734         if (end_pos < utf_ptr) return false;
 735         bytes = end_pos - utf_ptr;
 736         while (bytes--) {
 737                 c = *utf_ptr++;
 738                 /*dolog("%c %02x",c,c);*/
 739                 if (!c) return false;                     /* 0x00 is not allowed */
 740                 if ((c & 0x80) == 0) continue;            /* ASCII */
 741
 742                 if      ((c & 0xe0) == 0xc0) len = 1;     /* 110x xxxx */
 743                 else if ((c & 0xf0) == 0xe0) len = 2;     /* 1110 xxxx */
 744                 else if ((c & 0xf8) == 0xf0) len = 3;     /* 1111 0xxx */
 745                 else if ((c & 0xfc) == 0xf8) len = 4;     /* 1111 10xx */
 746                 else if ((c & 0xfe) == 0xfc) len = 5;     /* 1111 110x */
 747                 else return false;                        /* invalid leading byte */
 748
 749                 if (len > 2) return false;                /* Java limitation */
 750
 751                 v = (unsigned long)c & (0x3f >> len);
 752
 753                 if ((bytes -= len) < 0) return false;     /* missing bytes */
 754
 755                 for (i = len; i--; ) {
 756                         c = *utf_ptr++;
 757                         /*dolog("    %c %02x",c,c);*/
 758                         if ((c & 0xc0) != 0x80)               /* 10xx xxxx */
 759                                 return false;
 760                         v = (v<<6) | (c & 0x3f);
 761                 }
 762
 763                 /*              dolog("v=%d",v);*/
 764
 765                 if (v == 0) {
 766                         if (len != 1) return false;           /* Java special */
 767                 }
 768                 else {
 769                         if (v < min_codepoint[len]) return false; /* overlong UTF-8 */
 770                 }
 771
 772                 /* surrogates in UTF-8 seem to be allowed in Java classfiles */
 773                 /* if (v >= 0xd800 && v <= 0xdfff) return false; */ /* surrogates */
 774
 775                 /* even these seem to be allowed */
 776                 /* if (v == 0xfffe || v == 0xffff) return false; */ /* invalid codepoints */
 777         }
 778
 779         return true;
 780 }
 781
 782 /******************** Function: class_new **************************************
 783
 784     searches for the class with the specified name in the classes hashtable,
 785     if there is no such class a new classinfo structure is created and inserted
 786     into the list of classes to be loaded
 787
 788 *******************************************************************************/
 789
 790 classinfo *class_new(utf *u)
 791 {
 792         classinfo *c;     /* hashtable element */
 793         u4 key;           /* hashkey computed from classname */
 794         u4 slot;          /* slot in hashtable */
 795         u2 i;
 796
 797         key  = utf_hashkey (u->text, u->blength);
 798         slot = key & (class_hash.size-1);
 799         c    = class_hash.ptr[slot];
 800
 801         /* search external hash chain for the class */
 802         while (c) {
 803                 if (c->name->blength == u->blength) {
 804                         for (i=0; i<u->blength; i++)
 805                                 if (u->text[i] != c->name->text[i]) goto nomatch;
 806
 807                         /* class found in hashtable */
 808                         return c;
 809                 }
 810
 811         nomatch:
 812                 c = c->hashlink; /* next element in external chain */
 813         }
 814
 815         /* location in hashtable found, create new classinfo structure */
 816
 817 #ifdef STATISTICS
 818         count_class_infos += sizeof(classinfo);
 819 #endif
 820
 821         c = GCNEW(classinfo, 1); /*JOWENN: NEW*/
 822         c->vmClass = 0;
 823         c->flags = 0;
 824         c->name = u;
 825         c->cpcount = 0;
 826         c->cptags = NULL;
 827         c->cpinfos = NULL;
 828         c->super = NULL;
 829         c->sub = NULL;
 830         c->nextsub = NULL;
 831         c->interfacescount = 0;
 832         c->interfaces = NULL;
 833         c->fieldscount = 0;
 834         c->fields = NULL;
 835         c->methodscount = 0;
 836         c->methods = NULL;
 837         c->linked = false;
 838         c->loaded = false;
 839         c->index = 0;
 840         c->instancesize = 0;
 841         c->header.vftbl = NULL;
 842         c->innerclasscount = 0;
 843         c->innerclass = NULL;
 844         c->vftbl = NULL;
 845         c->initialized = false;
 846         c->classvftbl = false;
 847     c->classUsed = 0;
 848     c->impldBy = NULL;
 849
 850         /* prepare loading of the class */
 851         list_addlast(&unloadedclasses, c);
 852
 853         /* insert class into the hashtable */
 854         c->hashlink = class_hash.ptr[slot];
 855         class_hash.ptr[slot] = c;
 856
 857         /* update number of hashtable-entries */
 858         class_hash.entries++;
 859
 860         if (class_hash.entries > (class_hash.size*2)) {
 861
 862                 /* reorganization of hashtable, average length of
 863                    the external chains is approx. 2                */
 864
 865                 u4 i;
 866                 classinfo *c;
 867                 hashtable newhash;  /* the new hashtable */
 868
 869                 /* create new hashtable, double the size */
 870                 init_hashtable(&newhash, class_hash.size * 2);
 871                 newhash.entries = class_hash.entries;
 872
 873                 /* transfer elements to new hashtable */
 874                 for (i = 0; i < class_hash.size; i++) {
 875                         c = (classinfo*) class_hash.ptr[i];
 876                         while (c) {
 877                                 classinfo *nextc = c->hashlink;
 878                                 u4 slot = (utf_hashkey(c->name->text, c->name->blength)) & (newhash.size - 1);
 879
 880                                 c->hashlink = newhash.ptr[slot];
 881                                 newhash.ptr[slot] = c;
 882
 883                                 c = nextc;
 884                         }
 885                 }
 886
 887                 /* dispose old table */
 888                 MFREE(class_hash.ptr, void*, class_hash.size);
 889                 class_hash = newhash;
 890         }
 891
 892     /* Array classes need further initialization. */
 893     if (u->text[0] == '[')
 894         class_new_array(c);
 895
 896         return c;
 897 }
 898
 899 /******************** Function: class_get **************************************
 900
 901     searches for the class with the specified name in the classes hashtable
 902     if there is no such class NULL is returned
 903
 904 *******************************************************************************/
 905
 906 classinfo *class_get(utf *u)
 907 {
 908         classinfo *c;  /* hashtable element */
 909         u4 key;        /* hashkey computed from classname */
 910         u4 slot;       /* slot in hashtable */
 911         u2 i;
 912
 913         key  = utf_hashkey (u->text, u->blength);
 914         slot = key & (class_hash.size-1);
 915         c    = class_hash.ptr[slot];
 916
 917 /*
 918         log_text("class_get: looking for class:");
 919         utf_display(u); */
 920         /* search external hash-chain */
 921         while (c) {
 922                 if (c->name->blength == u->blength) {
 923
 924                         /* compare classnames */
 925                         for (i=0; i<u->blength; i++)
 926                                 if (u->text[i] != c->name->text[i]) goto nomatch;
 927 /*
 928                         log_text("class_get: class found");
 929                         utf_display(u);
 930                         log_text("");
 931                         utf_display(c->name); */
 932                         /* class found in hashtable */
 933                         return c;
 934                 }
 935
 936         nomatch:
 937                 c = c->hashlink;
 938         }
 939
 940         /* class not found */
 941         return NULL;
 942 }
 943
 944 /***************** Function: class_array_of ***********************************
 945
 946     Returns an array class with the given component class.
 947     The array class is dynamically created if neccessary.
 948
 949 *******************************************************************************/
 950
 951 classinfo *class_array_of(classinfo *component)
 952 {
 953     int namelen;
 954     char *namebuf;
 955
 956     /* Assemble the array class name */
 957     namelen = component->name->blength;
 958
 959     if (component->name->text[0] == '[') {
 960         /* the component is itself an array */
 961         namebuf = DMNEW(char,namelen+1);
 962         namebuf[0] = '[';
 963         memcpy(namebuf+1,component->name->text,namelen);
 964         namelen++;
 965     }
 966     else {
 967         /* the component is a non-array class */
 968         namebuf = DMNEW(char,namelen+3);
 969         namebuf[0] = '[';
 970         namebuf[1] = 'L';
 971         memcpy(namebuf+2,component->name->text,namelen);
 972         namebuf[2+namelen] = ';';
 973         namelen+=3;
 974     }
 975
 976     return class_new( utf_new(namebuf,namelen) );
 977 }
 978
 979 /*************** Function: class_multiarray_of ********************************
 980
 981     Returns an array class with the given dimension and element class.
 982     The array class is dynamically created if neccessary.
 983
 984 *******************************************************************************/
 985
 986 classinfo *class_multiarray_of(int dim,classinfo *element)
 987 {
 988     int namelen;
 989     char *namebuf;
 990
 991         if (dim<1)
 992                 panic("Invalid array dimension requested");
 993
 994     /* Assemble the array class name */
 995     namelen = element->name->blength;
 996
 997     if (element->name->text[0] == '[') {
 998         /* the element is itself an array */
 999         namebuf = DMNEW(char,namelen+dim);
1000         memcpy(namebuf+dim,element->name->text,namelen);
1001         namelen += dim;
1002     }
1003     else {
1004         /* the element is a non-array class */
1005         namebuf = DMNEW(char,namelen+2+dim);
1006         namebuf[dim] = 'L';
1007         memcpy(namebuf+dim+1,element->name->text,namelen);
1008         namelen += (2+dim);
1009         namebuf[namelen-1] = ';';
1010     }
1011         memset(namebuf,'[',dim);
1012
1013     return class_new( utf_new(namebuf,namelen) );
1014 }
1015
1016 /************************** function: utf_strlen ******************************
1017
1018     determine number of unicode characters in the utf string
1019
1020 *******************************************************************************/
1021
1022 u4 utf_strlen(utf *u)
1023 {
1024     char *endpos  = utf_end(u);  /* points behind utf string       */
1025     char *utf_ptr = u->text;     /* current position in utf text   */
1026     u4 len = 0;                  /* number of unicode characters   */
1027
1028     while (utf_ptr<endpos) {
1029                 len++;
1030                 /* next unicode character */
1031                 utf_nextu2(&utf_ptr);
1032     }
1033
1034     if (utf_ptr!=endpos)
1035         /* string ended abruptly */
1036                 panic("illegal utf string");
1037
1038     return len;
1039 }
1040
1041
1042 /*
1043  * These are local overrides for various environment variables in Emacs.
1044  * Please do not remove this and leave it at the end of the file, where
1045  * Emacs will automagically detect them.
1046  * ---------------------------------------------------------------------
1047  * Local variables:
1048  * mode: c
1049  * indent-tabs-mode: t
1050  * c-basic-offset: 4
1051  * tab-width: 4
1052  * End:
1053  */