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