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