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