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