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