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