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