/* -*- mode: c; tab-width: 4; c-basic-offset: 4 -*- */
/****************************** tables.c ***************************************

	Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst

	See file COPYRIGHT for information on usage and disclaimer of warranties

	Contains support functions for:
		- Reading of Java class files
		- Unicode symbols
		- the heap
		- additional support functions

	Authors: Reinhard Grafl      EMAIL: cacao@complang.tuwien.ac.at
	Changes: Mark Probst         EMAIL: cacao@complang.tuwien.ac.at
	         Andreas  Krall      EMAIL: cacao@complang.tuwien.ac.at
	         	
	Last Change: 1998/03/24

*******************************************************************************/

#include <assert.h>
#include <sys/mman.h>
#include <unistd.h>
#include "global.h"
#include "tables.h"
#include "asmpart.h"
#include "callargs.h"

#include "threads/thread.h"                  /* schani */
#include "threads/locks.h"

bool runverbose = false;

/* statistics */
int count_utf_len = 0;         /* size of utf hash                  */
int count_utf_new = 0;         /* calls of utf_new                  */
int count_utf_new_found  = 0;  /* calls of utf_new with fast return */

hashtable utf_hash;     /* hashtable for utf8-symbols */
hashtable string_hash;  /* hashtable for javastrings  */
hashtable class_hash;   /* hashtable for classes      */

/******************************************************************************
 *********************** hashtable functions **********************************
 ******************************************************************************/

/* hashsize must be power of 2 */

#define UTF_HASHSTART   16384   /* initial size of utf-hash */    
#define HASHSTART        2048   /* initial size of javastring and class-hash */


/******************** function: init_hashtable ******************************

    Initializes a hashtable structure and allocates memory.
    The parameter size specifies the initial size of the hashtable.
	
*****************************************************************************/

void init_hashtable(hashtable *hash, u4 size)
{
	u4 i;

	hash->entries = 0;
	hash->size    = size;
	hash->ptr     = MNEW (void*, size);

	/* clear table */
	for (i=0; i<size; i++) hash->ptr[i] = NULL;
}

/*********************** function: tables_init  *****************************

    creates hashtables for symboltables 
	(called once at startup)			 
	
*****************************************************************************/

void tables_init ()
{
	init_hashtable(&utf_hash,    UTF_HASHSTART);  /* hashtable for utf8-symbols */
	init_hashtable(&string_hash, HASHSTART);      /* hashtable for javastrings */
	init_hashtable(&class_hash,  HASHSTART);      /* hashtable for classes */ 
	
#ifdef STATISTICS
	count_utf_len += sizeof(utf*) * utf_hash.size;
#endif

}

/********************** function: tables_close ******************************

        free memory for hashtables		      
	
*****************************************************************************/

void tables_close (stringdeleter del)
{
	utf *u;	
	literalstring *s;
	u4 i;
	
	/* dispose utf symbols */
	for (i=0; i<utf_hash.size; i++) {
	u = utf_hash.ptr[i];
		while (u) {
			/* process elements in external hash chain */
			utf *nextu = u->hashlink;
			MFREE (u->text, u1, u->blength);
			FREE (u, utf);
			u = nextu;
			}	
		}

	/* dispose javastrings */
	for (i=0; i<string_hash.size; i++) {
		s = string_hash.ptr[i];
		while (u) {
			/* process elements in external hash chain */
			literalstring *nexts = s->hashlink;
			del(s->string);
			FREE(s, literalstring);
			s = nexts;
			}	
		}

	/* dispose hashtable structures */
	MFREE (utf_hash.ptr,    void*, utf_hash.size);
	MFREE (string_hash.ptr, void*, string_hash.size);
	MFREE (class_hash.ptr,  void*, class_hash.size);
}

/********************* function: utf_display *********************************

	write utf symbol to stdout (debugging purposes)

******************************************************************************/

void utf_display (utf *u)
{
    char *endpos  = utf_end(u);  /* points behind utf string       */
    char *utf_ptr = u->text;     /* current position in utf text   */

    while (utf_ptr<endpos) {

		/* read next unicode character */                
		u2 c = utf_nextu2(&utf_ptr);				
		if (c>=32 && c<=127) printf ("%c",c);
		                else printf ("?");
	}

	fflush (stdout);
}

/************************ function: utf_sprint *******************************
	
    write utf symbol into c-string (debugging purposes)						 

******************************************************************************/ 

void utf_sprint (char *buffer, utf *u)
{
    char *endpos  = utf_end(u);  /* points behind utf string       */
    char *utf_ptr = u->text;     /* current position in utf text   */ 
    u2 pos = 0;                  /* position in c-string           */

    while (utf_ptr<endpos) 
		/* copy next unicode character */       
		buffer[pos++] = utf_nextu2(&utf_ptr);

    /* terminate string */
    buffer[pos] = '\0';
}


/********************* Funktion: utf_fprint **********************************
	
    write utf symbol into file		

******************************************************************************/ 

void utf_fprint (FILE *file, utf *u)
{
    char *endpos  = utf_end(u);  /* points behind utf string       */
    char *utf_ptr = u->text;     /* current position in utf text   */ 

    while (utf_ptr<endpos) 
		/* write next unicode character */       
		putc ( utf_nextu2(&utf_ptr), file );
} 


/****************** internal function: utf_hashkey ***************************

	The hashkey is computed from the utf-text by using up to 8 characters.
	For utf-symbols longer than 15 characters 3 characters are taken from
	the beginning and the end, 2 characters are taken from the middle.

******************************************************************************/ 

#define nbs(val) ((u4) *(++text) << val) /* get next byte, left shift by val  */
#define fbs(val) ((u4) *(  text) << val) /* get first byte, left shift by val */

static u4 utf_hashkey (char *text, u4 length)
{
	char *start_pos = text; /* pointer to utf text */
	u4 a;

	switch (length) {		
	        
	case 0: /* empty string */
		return 0;

	case 1: return fbs(0);
	case 2: return fbs(0) ^ nbs(3);
	case 3: return fbs(0) ^ nbs(3) ^ nbs(5);
	case 4: return fbs(0) ^ nbs(2) ^ nbs(4) ^ nbs(6);
	case 5: return fbs(0) ^ nbs(2) ^ nbs(3) ^ nbs(4) ^ nbs(6);
	case 6: return fbs(0) ^ nbs(1) ^ nbs(2) ^ nbs(3) ^ nbs(5) ^ nbs(6);
	case 7: return fbs(0) ^ nbs(1) ^ nbs(2) ^ nbs(3) ^ nbs(4) ^ nbs(5) ^ nbs(6);
	case 8: return fbs(0) ^ nbs(1) ^ nbs(2) ^ nbs(3) ^ nbs(4) ^ nbs(5) ^ nbs(6) ^ nbs(7);

	case 9: a = fbs(0) ^ nbs(1) ^ nbs(2);                
                text++; 
                return a ^ nbs(4) ^ nbs(5) ^ nbs(6) ^ nbs(7) ^ nbs(8);

	case 10: a = fbs(0);
                 text++;
                 a^= nbs(2) ^ nbs(3) ^ nbs(4);
                 text++;
                 return a ^ nbs(6) ^ nbs(7) ^ nbs(8) ^ nbs(9);

	case 11: a = fbs(0);
                 text++;
                 a^= nbs(2) ^ nbs(3) ^ nbs(4);
                 text++;
                 return a ^ nbs(6) ^ nbs(7) ^ nbs(8) ^ nbs(9) ^ nbs(10);

	case 12: a = fbs(0);
                 text+=2;
                 a^= nbs(2) ^ nbs(3);
                 text+=1;
                 a^= nbs(5) ^ nbs(6) ^ nbs(7);
                 text+=1;
                 return a ^ nbs(9) ^ nbs(10);	   

	case 13: a = fbs(0) ^ nbs(1);
                 text+=1;	
                 a^= nbs(3) ^ nbs(4);
                 text+=2;	
                 a^= nbs(7) ^ nbs(8);
                 text+=2;
                 return a ^ nbs(9) ^ nbs(10);

	case 14: a = fbs(0);
                 text+=2;	
                 a^= nbs(3) ^ nbs(4);
                 text+=2;	
                 a^= nbs(7) ^ nbs(8);
                 text+=2;
                 return a ^ nbs(9) ^ nbs(10) ^ nbs(11);

	case 15: a = fbs(0);
                 text+=2;	
                 a^= nbs(3) ^ nbs(4);
                 text+=2;	
                 a^= nbs(7) ^ nbs(8);
                 text+=2;
                 return a ^ nbs(9) ^ nbs(10) ^ nbs(11);

	default:  /* 3 characters from beginning */
                  a = fbs(0);
                  text+=2;
                  a^= nbs(3) ^ nbs(4);

                  /* 2 characters from middle */
                  text = start_pos + (length / 2);
                  a^= fbs(5);
                  text+=2;
                  a^= nbs(6);	

                  /* 3 characters from end */
                  text = start_pos + length - 4;

                  a^= fbs(7);
                  text+=1;

                  return a ^ nbs(10) ^ nbs(11);
    }
}


/*************************** function: utf_hashkey ***************************

    compute the hashkey of a unicode string

******************************************************************************/ 

u4 unicode_hashkey (u2 *text, u2 len)
{
	utf_hashkey((char*) text, len);
}

/************************ function: utf_new **********************************

	Creates a new utf-symbol, the text of the symbol is passed as a 
	u1-array. The function searches the utf-hashtable for a utf-symbol 
	with this text. On success the element returned, otherwise a new 
	hashtable element is created.

	If the number of entries in the hashtable exceeds twice the size of the
	hashtable slots a reorganization of the hashtable is done and the utf 
	symbols are copied to a new hashtable with doubled size.

******************************************************************************/

utf *utf_new (char *text, u2 length)
{
	u4 key;            /* hashkey computed from utf-text */
	u4 slot;           /* slot in hashtable */
	utf *u;            /* hashtable element */
	u2 i;
	
#ifdef STATISTICS
	count_utf_new++;
#endif

	key  = utf_hashkey (text, length);
	slot = key & (utf_hash.size-1);
	u    = utf_hash.ptr[slot];

	/* search external hash chain for utf-symbol */
	while (u) {
		if (u->blength == length) {

			/* compare text of hashtable elements */
			for (i=0; i<length; i++)
				if (text[i] != u->text[i]) goto nomatch;
			
#ifdef STATISTICS
			count_utf_new_found++;
#endif
			/* symbol found in hashtable */   				
			return u;
		}
		nomatch:
		u = u->hashlink; /* next element in external chain */
	}

#ifdef STATISTICS
	count_utf_len += sizeof(utf) + length;
#endif

	/* location in hashtable found, create new utf element */
	u = NEW (utf);
	u->blength  = length;             /* length in bytes of utfstring */
	u->hashlink = utf_hash.ptr[slot]; /* link in external hashchain   */		
	u->text     = mem_alloc(length);  /* allocate memory for utf-text */
	memcpy(u->text,text,length);      /* copy utf-text                */
	utf_hash.ptr[slot] = u;           /* insert symbol into table     */ 

	utf_hash.entries++;               /* update number of entries     */

	if ( utf_hash.entries > (utf_hash.size*2)) { 

        /* reorganization of hashtable, average length of 
           the external chains is approx. 2                */  

	  u4 i;
	  utf *u;
	  hashtable newhash; /* the new hashtable */

	  /* create new hashtable, double the size */
	  init_hashtable(&newhash, utf_hash.size*2);
	  newhash.entries=utf_hash.entries;

#ifdef STATISTICS
	  count_utf_len += sizeof(utf*) * utf_hash.size;
#endif

	  /* transfer elements to new hashtable */
	  for (i=0; i<utf_hash.size; i++) {
		u = (utf*) utf_hash.ptr[i];
		while (u) {
			utf *nextu = u -> hashlink;
			u4 slot = (utf_hashkey(u->text,u->blength)) & (newhash.size-1);
						
			u->hashlink = (utf*) newhash.ptr[slot];
			newhash.ptr[slot] = u;

			/* follow link in external hash chain */
			u = nextu;
			}
		}
	
	  /* dispose old table */
	  MFREE (utf_hash.ptr, void*, utf_hash.size);
	  utf_hash = newhash;
	}
	
	return u;
}


/********************* function: utf_new_char ********************************

    creates a new utf symbol, the text for this symbol is passed
    as a c-string ( = char* )

******************************************************************************/

utf *utf_new_char (char *text)
{
	return utf_new(text, strlen(text));
}

/************************** Funktion: utf_show ******************************

    writes the utf symbols in the utfhash to stdout and
    displays the number of external hash chains grouped 
    according to the chainlength
    (debugging purposes)

*****************************************************************************/

void utf_show ()
{

#define CHAIN_LIMIT 20               /* limit for seperated enumeration */

	u4 chain_count[CHAIN_LIMIT]; /* numbers of chains */
	u4 max_chainlength = 0;      /* maximum length of the chains */
	u4 sum_chainlength = 0;      /* sum of the chainlengths */
	u4 beyond_limit = 0;         /* number of utf-symbols in chains with length>=CHAIN_LIMIT-1 */
	u4 i;

	printf ("UTF-HASH:\n");

	/* show element of utf-hashtable */
	for (i=0; i<utf_hash.size; i++) {
		utf *u = utf_hash.ptr[i];
		if (u) {
			printf ("SLOT %d: ", (int) i);
			while (u) {
				printf ("'");
				utf_display (u);
				printf ("' ");
				u = u->hashlink;
				}	
			printf ("\n");
			}
		
		}

	printf ("UTF-HASH: %d slots for %d entries\n", 
	         (int) utf_hash.size, (int) utf_hash.entries );


	if (utf_hash.entries == 0)
		return;

	printf("chains:\n  chainlength    number of chains    %% of utfstrings\n");

	for (i=0;i<CHAIN_LIMIT;i++)
		chain_count[i]=0;

	/* count numbers of hashchains according to their length */
	for (i=0; i<utf_hash.size; i++) {
		  
		utf *u = (utf*) utf_hash.ptr[i];
		u4 chain_length = 0;

		/* determine chainlength */
		while (u) {
			u = u->hashlink;
			chain_length++;
			}

		/* update sum of all chainlengths */
		sum_chainlength+=chain_length;

		/* determine the maximum length of the chains */
		if (chain_length>max_chainlength)
			max_chainlength = chain_length;

		/* update number of utf-symbols in chains with length>=CHAIN_LIMIT-1 */
		if (chain_length>=CHAIN_LIMIT) {
			beyond_limit+=chain_length;
			chain_length=CHAIN_LIMIT-1;
		}

		/* update number of hashchains of current length */
		chain_count[chain_length]++;
		}

	/* display results */  
	for (i=1;i<CHAIN_LIMIT-1;i++) 
		printf("       %2d %17d %18.2f%%\n",i,chain_count[i],(((float) chain_count[i]*i*100)/utf_hash.entries));
	  
	printf("     >=%2d %17d %18.2f%%\n",CHAIN_LIMIT-1,chain_count[CHAIN_LIMIT-1],((float) beyond_limit*100)/utf_hash.entries);


	printf("max. chainlength:%5d\n",max_chainlength);

	/* avg. chainlength = sum of chainlengths / number of chains */
	printf("avg. chainlength:%5.2f\n",(float) sum_chainlength / (utf_hash.size-chain_count[0]));
}

/******************************************************************************
*********************** Misc support functions ********************************
******************************************************************************/


/******************** Function: desc_to_type **********************************
   
	Determines the corresponding Java base data type for a given type
	descriptor.
	
******************************************************************************/

u2 desc_to_type (utf *descriptor)
{
	char *utf_ptr = descriptor->text;  /* current position in utf text */

	if (descriptor->blength < 1) panic ("Type-Descriptor is empty string");
	
	switch (*utf_ptr++) {
	case 'B': 
	case 'C':
	case 'I':
	case 'S':  
	case 'Z':  return TYPE_INT;
	case 'D':  return TYPE_DOUBLE;
	case 'F':  return TYPE_FLOAT;
	case 'J':  return TYPE_LONG;
	case 'L':
	case '[':  return TYPE_ADDRESS;
	}
			
	sprintf (logtext, "Invalid Type-Descriptor: "); 
	utf_sprint (logtext+strlen(logtext), descriptor);
	error (); 
	return 0;
}


/********************** Function: desc_typesize *******************************

	Calculates the lenght in bytes needed for a data element of the type given
	by its type descriptor.
	
******************************************************************************/

u2 desc_typesize (utf *descriptor)
{
	switch (desc_to_type(descriptor)) {
	case TYPE_INT:     return 4;
	case TYPE_LONG:    return 8;
	case TYPE_FLOAT:   return 4;
	case TYPE_DOUBLE:  return 8;
	case TYPE_ADDRESS: return sizeof(voidptr);
	default:           return 0;
	}
}


/********************** function: utf_nextu2 *********************************

    read the next unicode character from the utf string and
    increment the utf-string pointer accordingly

******************************************************************************/

u2 utf_nextu2(char **utf_ptr) 
{
    /* uncompressed unicode character */
    u2 unicode_char;	
    /* current position in utf text */	
    unsigned char *utf = (unsigned char *) (*utf_ptr);  
    /* bytes representing the unicode character */
    unsigned char ch1, ch2, ch3;
    /* number of bytes used to represent the unicode character */
    int len;		
	
    switch ((ch1 = utf[0]) >> 4) {
      default: /* 1 byte */
               (*utf_ptr)++;
               return ch1;
       case 0xC: 
       case 0xD: /* 2 bytes */
                 if (((ch2 = utf[1]) & 0xC0) == 0x80) {
                   unsigned char high = ch1 & 0x1F;
                   unsigned char low  = ch2 & 0x3F;
                   unicode_char = (high << 6) + low;
                   len = 2;
                 } 
                 break;

       case 0xE: /* 2 or 3 bytes */
                 if (((ch2 = utf[1]) & 0xC0) == 0x80) {
                    if (((ch3 = utf[2]) & 0xC0) == 0x80) {
                       unsigned char low  = ch3 & 0x3f;
                       unsigned char mid  = ch2 & 0x3f;
                       unsigned char high = ch1 & 0x0f;
                       unicode_char = (((high << 6) + mid) << 6) + low;
                       len = 3;
                    } else
                       len = 2;					   
	         }
                 break;
    }

    /* update position in utf-text */
    *utf_ptr = (char *) (utf + len);
    return unicode_char;
}
 
/******************** Function: class_new **************************************

    searches for the class with the specified name in the classes hashtable,
    if there is no such class a new classinfo structure is created and inserted
    into the list of classes to be loaded

*******************************************************************************/

classinfo *class_new (utf *u)
{
	classinfo *c;     /* hashtable element */ 
	u4 key;           /* hashkey computed from classname */   
	u4 slot;          /* slot in hashtable */
	u2 i;

	key  = utf_hashkey (u->text, u->blength);
	slot = key & (class_hash.size-1);
	c    = class_hash.ptr[slot];

	/* search external hash chain for the class */
	while (c) {
		if (c->name->blength == u->blength) {
			for (i=0; i<u->blength; i++) 
				if (u->text[i] != c->name->text[i]) goto nomatch;
						
				/* class found in hashtable */									
				return c;
			}
			
		nomatch:
		c = c->hashlink; /* next element in external chain */
		}

	/* location in hashtable found, create new classinfo structure */

#ifdef STATISTICS
	count_class_infos += sizeof(classinfo);
#endif

	c = NEW (classinfo);
	c -> flags = 0;
	c -> name = u;
	c -> cpcount = 0;
	c -> cptags = NULL;
	c -> cpinfos = NULL;
	c -> super = NULL;
	c -> sub = NULL;
	c -> nextsub = NULL;
	c -> interfacescount = 0;
	c -> interfaces = NULL;
	c -> fieldscount = 0;
	c -> fields = NULL;
	c -> methodscount = 0;
	c -> methods = NULL;
	c -> linked = false;
	c -> index = 0;
	c -> instancesize = 0;
	c -> header.vftbl = NULL;
	c -> innerclasscount = 0;
	c -> innerclass = NULL;
	c -> vftbl = NULL;
	c -> initialized = false;
	
	/* prepare loading of the class */
	list_addlast (&unloadedclasses, c);

	/* insert class into the hashtable */
	c->hashlink = class_hash.ptr[slot];
	class_hash.ptr[slot] = c;

	/* update number of hashtable-entries */
	class_hash.entries++;

	if ( class_hash.entries > (class_hash.size*2)) {  

          /* reorganization of hashtable, average length of 
             the external chains is approx. 2                */  

	  u4 i;
	  classinfo *c;
	  hashtable newhash;  /* the new hashtable */

	  /* create new hashtable, double the size */
	  init_hashtable(&newhash, class_hash.size*2);
	  newhash.entries = class_hash.entries;

	  /* transfer elements to new hashtable */
	  for (i=0; i<class_hash.size; i++) {
		c = (classinfo*) class_hash.ptr[i];
		while (c) {
			classinfo *nextc = c -> hashlink;
			u4 slot = (utf_hashkey(c->name->text,c->name->blength)) & (newhash.size-1);
						
			c->hashlink = newhash.ptr[slot];
			newhash.ptr[slot] = c;

			c = nextc;
			}
		}
	
	  /* dispose old table */	
	  MFREE (class_hash.ptr, void*, class_hash.size);
	  class_hash = newhash;
	}
			
	return c;
}

/******************** Function: class_get **************************************

    searches for the class with the specified name in the classes hashtable
    if there is no such class NULL is returned

*******************************************************************************/

classinfo *class_get (utf *u)
{
	classinfo *c;  /* hashtable element */ 
	u4 key;        /* hashkey computed from classname */   
	u4 slot;       /* slot in hashtable */
	u2 i;  

	key  = utf_hashkey (u->text, u->blength);
	slot = key & (class_hash.size-1);
	c    = class_hash.ptr[slot];

	/* search external hash-chain */
	while (c) {
		if (c->name->blength == u->blength) {
			
			/* compare classnames */
			for (i=0; i<u->blength; i++) 
				if (u->text[i] != c->name->text[i]) goto nomatch;

			/* class found in hashtable */				
			return c;
			}
			
		nomatch:
		c = c->hashlink;
		}

	/* class not found */
	return NULL;
}


/************************** function: utf_strlen ******************************

    determine number of unicode characters in the utf string

*******************************************************************************/

u4 utf_strlen(utf *u) 
{
    char *endpos  = utf_end(u);  /* points behind utf string       */
    char *utf_ptr = u->text;     /* current position in utf text   */
    u4 len = 0;			 /* number of unicode characters   */

    while (utf_ptr<endpos) {
      len++;
      /* next unicode character */
      utf_nextu2(&utf_ptr);
    }

    if (utf_ptr!=endpos)
    	/* string ended abruptly */
	panic("illegal utf string"); 

    return len;
}