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