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