/* java_utf8.cpp
   Copyright (C) 2005 Free Software Foundation, Inc.

This file is part of Mysaifu JVM

Mysaifu JVM is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; version 2 of the License.

Mysaifu JVM is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.
*/

#include "StdAfx.h"
#include "java_utf8.h"
#include "ClassFile.h"
#include "instruction.h"
#include "common_funcs.h"

/**
 * UTF-8文字列の保存に使用するハッシュテーブル要素
 */
struct hash_table_element {
	/**
	 * 文字列の長さ
	 */
	int length;

	/**
	 * 対応するStringオブジェクトの参照。存在しない場合はNULL
	 */
	jstring string_reference;

	/**
	 * 次の要素へのリンク
	 */
	hash_table_element* next;

    // この直後に文字列本体が格納される
};

/**
 * メモリ管理用構造体
 * hash_table_elementのメモリ領域は、以下のように管理される
 *
 * hash_element_pool
 *
   +-------+
   | next  |--------> +----+ 
   +-------+          |next| --> ...
   | limit |-----+    +----+
   +-------+     |    | 
   |current|-+   |
   +-------+ |   |
   |elem1  | |   |
   +-------+ |   |
   |elem2  | |   |
   +-------+ |   |
   | 空き  <-+   |
   |       |     |
   +-------+<----+

 * 基本的に header は1つしか存在せず、空き領域が順番に埋められていくが、空き領域に入らなかった場合は
 * 新たに header が作られ、チェーンされる。
 * チェーンが長くなるのを防ぐため、上限サイズを越える hash_table_element が要求された場合は、hash_table_element
 * のみの確保を行い、チェーンしない。
 * また、空き領域が指定値以下になったhash_table_element_poolは管理対象からはずされる。(もうその領域からメモリは確保しない）
 */
struct hash_table_element_pool {
	hash_table_element_pool* next;
	char* limit;
	char* current;
	// この直後に hash_table_elementのデータが格納されていく
};

/**
 * 先頭の hash_table_element_pool
 */
static hash_table_element_pool* g_hash_table_element_pool;

/**
 * ハッシュテーブルエレメントプールのデフォルトサイズ
 */
#define DEFAULT_HASH_TABLE_ELEMENT_POOL_SIZE (16*1024)

/**
 * ハッシュテーブルのサイズ。素数が望ましい。
 */
#define HASH_TABLE_SIZE	8191 

/**
 * ハッシュテーブル
 */
static hash_table_element* g_utf8_table[HASH_TABLE_SIZE];

/**
 * グローバルUTF-8文字列
 */
const java_utf8* CLASS_CLASS_NAME;
const java_utf8* STRING_CLASS_NAME;
const java_utf8* CLINIT_METHOD_NAME;
const java_utf8* INIT_METHOD_NAME;
const java_utf8* FINALIZE_METHOD_NAME;
const java_utf8* VOID_NOARG_METHOD_DESCRIPTOR;
const java_utf8* CLONE_METHOD_NAME;
const java_utf8* JAVA_LANG_OBJECT_CLASS_NAME;
const java_utf8* JAVA_LANG_CLONEABLE_CLASS_NAME;
const java_utf8* JAVA_IO_SERIALIZABLE_CLASS_NAME;
const java_utf8* BOOLEAN_ARRAY_CLASS_NAME;
const java_utf8* BYTE_ARRAY_CLASS_NAME;
const java_utf8* SHORT_ARRAY_CLASS_NAME;
const java_utf8* CHAR_ARRAY_CLASS_NAME;
const java_utf8* INT_ARRAY_CLASS_NAME;
const java_utf8* LONG_ARRAY_CLASS_NAME;
const java_utf8* FLOAT_ARRAY_CLASS_NAME;
const java_utf8* DOUBLE_ARRAY_CLASS_NAME;
const java_utf8* PRIMITIVE_ARRAY_CLASS_NAMES[12];

const java_utf8* JAVA_LANG_VMCLASS_CLASS_NAME;
const java_utf8* JAVA_LANG_CLASS_CONSTRUCTOR_DESCRIPTOR;
const java_utf8* STRING_ARG_CONSTRUCTOR_DESCRIPTOR;
const java_utf8* CHAR_ARRAY_ARG_CONSTRUCTOR_DESCRIPTOR;

/**
 * グローバルクリティカルセクション。
 * グローバル変数を操作する際には、必ずこのCRITICAL_SECTIONで保護する
 */
extern CRITICAL_SECTION g_global_critical_section;

static hash_table_element* intern_element(const java_utf8* utf8, int length);
static hash_table_element_pool* alloc_hash_table_element_pool(int pool_size);

#define CHAR_VALUE(elem) ((char*) (elem + 1))

/**
 * PermanentHeap
 */
static PermanentHeap* g_permanent_heap;

/**
 * UTF-8文字列関連処理を初期化する
 */
void init_utf8_settings() {
	// ハッシュテーブルを初期化する
	for (int i = 0; i < HASH_TABLE_SIZE; ++i) {
		g_utf8_table[i] = NULL;
	}

	g_permanent_heap = new PermanentHeap(DEFAULT_HASH_TABLE_ELEMENT_POOL_SIZE);
	g_permanent_heap->setMinimumAllocationSize(sizeof(hash_table_element) + 1);

	// 頻繁に使用する文字列を初期化する
	CLASS_CLASS_NAME = intern_utf8("java/lang/Class");

	STRING_CLASS_NAME = intern_utf8("java/lang/String");

	// <clinit>
	CLINIT_METHOD_NAME = intern_utf8("<clinit>");

	// <init>
	INIT_METHOD_NAME = intern_utf8("<init>");

	// "finalize()"メソッド名
	FINALIZE_METHOD_NAME = intern_utf8("finalize");

	// 返り値が void で引数を持たないメソッドのディスクリプタ
	VOID_NOARG_METHOD_DESCRIPTOR = intern_utf8("()V");

	// clone() メソッド名
	CLONE_METHOD_NAME = intern_utf8("clone");
	
	// java/lang/Object
	JAVA_LANG_OBJECT_CLASS_NAME = intern_utf8("java/lang/Object");

	JAVA_LANG_CLONEABLE_CLASS_NAME = intern_utf8("java/lang/Cloneable");
	JAVA_IO_SERIALIZABLE_CLASS_NAME = intern_utf8("java/io/Serializable");

	// 配列クラス名
	// boolean配列クラス名
	BOOLEAN_ARRAY_CLASS_NAME = intern_utf8("[Z");

	// byte配列クラス名
	BYTE_ARRAY_CLASS_NAME = intern_utf8("[B");

	// char配列クラス名
	CHAR_ARRAY_CLASS_NAME = intern_utf8("[C");
	
	// short配列クラス名
	SHORT_ARRAY_CLASS_NAME = intern_utf8("[S");
	
	// int配列クラス名
	INT_ARRAY_CLASS_NAME = intern_utf8("[I");
	
	// long配列クラス名
	LONG_ARRAY_CLASS_NAME = intern_utf8("[J");
	
	// float配列クラス名
	FLOAT_ARRAY_CLASS_NAME = intern_utf8("[F");
	
	// double配列クラス名
	DOUBLE_ARRAY_CLASS_NAME = intern_utf8("[D");
	
	PRIMITIVE_ARRAY_CLASS_NAMES[4] = BOOLEAN_ARRAY_CLASS_NAME;	// T_BOOLEAN = 4
	PRIMITIVE_ARRAY_CLASS_NAMES[5] = CHAR_ARRAY_CLASS_NAME;		// T_CHAR = 5
	PRIMITIVE_ARRAY_CLASS_NAMES[6] = FLOAT_ARRAY_CLASS_NAME;	// T_FLOAT = 6
	PRIMITIVE_ARRAY_CLASS_NAMES[7] = DOUBLE_ARRAY_CLASS_NAME;	// T_DOUBLE = 7
	PRIMITIVE_ARRAY_CLASS_NAMES[8] = BYTE_ARRAY_CLASS_NAME;		// T_BYTE = 8
	PRIMITIVE_ARRAY_CLASS_NAMES[9] = SHORT_ARRAY_CLASS_NAME;	// T_SHORT = 9
	PRIMITIVE_ARRAY_CLASS_NAMES[10] = INT_ARRAY_CLASS_NAME;		// T_INT = 10
	PRIMITIVE_ARRAY_CLASS_NAMES[11] = LONG_ARRAY_CLASS_NAME;	// T_INT = 11

	JAVA_LANG_VMCLASS_CLASS_NAME = intern_utf8("java/lang/VMClass");
	JAVA_LANG_CLASS_CONSTRUCTOR_DESCRIPTOR = intern_utf8("(Ljava/lang/Object;Ljava/security/ProtectionDomain;)V");
	STRING_ARG_CONSTRUCTOR_DESCRIPTOR = intern_utf8("(Ljava/lang/String;)V");
	CHAR_ARRAY_ARG_CONSTRUCTOR_DESCRIPTOR = intern_utf8("([C)V");

}

/**
 * ハッシュ値を計算する
 * java.lang.StringのhashCode()と同一の計算方法を用いる
 */
static inline unsigned int get_hash_table_index(java_utf8* utf8, int length) {
	unsigned int hash = 0;
	while (length--) {
		hash = hash * 137 + (unsigned int) *utf8++;
	}
	return hash % HASH_TABLE_SIZE;
}

/**
 * 新しいエレメントを作成する
 */
static hash_table_element* create_element(const char* utf8, int length) {
	int total_size = sizeof(hash_table_element) + length + 1;
	hash_table_element* elem = (hash_table_element*) g_permanent_heap->allocate(total_size);

	if (! elem) {
	  fatal_error(FATAL_ERROR_NO_MEMORY);
	}

	// 直後に文字列を格納する
	char* value = (char*) (elem + 1);

	strncpy(value, utf8, length);
	value[length] = '\0';
	elem->length = length;
	return elem;
}

/**
 * "インターン"処理を行う
 */
static hash_table_element* intern_element(const java_utf8* utf8, int length) {
	unsigned table_pos = get_hash_table_index(utf8, length);
	
	// 挿入する位置を検索する
	// （リンクは昇順に並んでいる）
	hash_table_element* elem = g_utf8_table[table_pos];
	java_utf8* intern = NULL;
	if (elem == NULL) {
		// 先頭に挿入する
		hash_table_element* newelem = create_element(utf8, length);
		g_utf8_table[table_pos] = newelem;
		return newelem;
	}
	// リスト先頭要素と比較する
	if (length == elem->length) {
		int cmp = strncmp(utf8, CHAR_VALUE(elem), length);
		if (cmp == 0) {
			// 先頭要素と一致
			return elem;
		}
	} else if (length < elem->length) {
		// 先頭に挿入する
		hash_table_element* newelem = create_element(utf8, length);
		g_utf8_table[table_pos] = newelem;
		newelem->next = elem;
		return newelem;
	}
	if (elem->next == NULL) {
		// リスト末尾に追加
		hash_table_element* newelem = create_element(utf8, length);
		elem->next = newelem;
		return newelem;
	} 

	// ハッシュコードが衝突しているので、リストを順番に検索していく
//	DBG(_T("intern_element():hash collision "));
//	DBG_INT(table_pos);
//	DBG(_T(" "));
//	DBG_UTF8(utf8);
//	DBG(_T("\n"));

	hash_table_element* newelem = NULL;
	while (elem->next != NULL) {
		if (length == elem->next->length) {
			int cmp =strncmp(utf8, CHAR_VALUE(elem->next), length);
			// リストの次の要素と比較する
			if (cmp == 0) {
				// 一致した
				return elem->next;
			}
		} else if (length < elem->next->length) {
			// 次の要素より、与えられた文字列が小さな場合
			// 新しく作成した要素を挿入する
			hash_table_element* newelem = create_element(utf8, length);
			newelem->next = elem->next;
			elem->next = newelem;
			return newelem;
		}
		elem = elem->next;
	}
	// ここまできた場合には、リストの末尾に追加する
	newelem = create_element(utf8, length);
	elem->next = newelem;
	return newelem;
}

/**
 * 指定されたUTF-8文字列を「インターン」する
 *
 * @param	utf8	対象となるjava_utf8 構造体
 * @return	インターンされた結果
 */
const java_utf8* intern_utf8(const char* utf8, int length) {
#if 0
	char* tmp = (char*) malloc(length + 1);
	if (tmp == NULL) {
		fatal_error(FATAL_ERROR_NO_MEMORY);
	}
	strncpy(tmp, utf8, length);
	tmp[length] = '\0';
	const java_utf8* result = intern_utf8(tmp);
	free(tmp);
#endif

	EnterCriticalSection(&g_global_critical_section);
	hash_table_element* elem = intern_element(utf8, length);
	LeaveCriticalSection(&g_global_critical_section);
	return CHAR_VALUE(elem);
}

/**
 * 指定されたUTF-8文字列を「インターン」する
 *
 * @param	utf8	対象となるjava_utf8 構造体
 * @return	インターンされた結果
 */
const java_utf8* intern_utf8(const char* utf8) {
	EnterCriticalSection(&g_global_critical_section);
	hash_table_element* elem = intern_element(utf8, strlen(utf8));
	LeaveCriticalSection(&g_global_critical_section);
	return CHAR_VALUE(elem);
}

/**
 * 指定されたUTF-8文字列を「インターン」し、対応するStringオブジェクトを返す
 */
jstring intern_string(const char* utf8, frame* frame) {
	EnterCriticalSection(&g_global_critical_section);
	hash_table_element* elem = intern_element(utf8, strlen(utf8));
	LeaveCriticalSection(&g_global_critical_section);

	if (elem->string_reference == NULL) {
		jstring permstr = permanent_utf8_string(frame, utf8);
		InterlockedCompareExchangePointer(&elem->string_reference, permstr, NULL);
		POP_DISCARD(frame);
		if (elem->string_reference != permstr) {
			assert(false);
			// 他スレッドと競合した結果、格納することができなかった
			// ごみになってしまったので、グローバル参照から削除する
			delete_global_reference(permstr);
		}
	}

	return elem->string_reference;
}

/**
 * TCHARとUTF-8との比較を行う。２つの表現が等しい場合はtrueを返す。
 */
bool equals(const TCHAR* str, const char* utf8) {
	int stridx = 0;
	u4 utf8idx = 0;
	u4 length = strlen(utf8);

	TCHAR c;
	while ((c = str[stridx++]) != 0) {
		// １バイト 0xxxxxxx
		if (c != 0 && (c & 0xff80) == 0) {
			if (utf8idx >= length) {
				// UTF-8バイトが終了してしまった
				return false;
			}
			if (utf8[utf8idx++] != (u1) c) {
				return false;
			}
		} else if ((c == 0) || ((c & 0xf800) == 0)) { // ２バイト 00000yyy:yyxxxxxx -> 110yyyyy + 10xxxxxx
			if (utf8idx+1 >= length) {
				// UTF-8を２バイト読み込むことができない
				return false;
			}
			if ((utf8[utf8idx++] != (0xc0 | c >> 6))
				|| (utf8[utf8idx++] != (0x80 | (c & 0x003f)))) {
				return false;
			}
		} else { // ３バイト zzzzyyyy:yyxxxxxx -> 1110zzzz + 10yyyyyy + 10xxxxxx
			if (utf8idx+2 >= length) {
				// UTF-8を3バイト読み込むことができない
				return false;
			}
			if ( utf8[utf8idx++] != (0xe0 | (c >> 12))
					|| utf8[utf8idx++] != (0x80 | ((c & 0x0fc0) >> 6)
					|| utf8[utf8idx++] != (0x80 | (c & 0x003f)))) {
				return false;
			}
		}
	}
	return true;
}

/**
 * java_utf8の内容を、TCHAR文字列に変換する
 *
 * @param	utf8	変換元
 * @param	buff	TCHAR文字列のバッファ
 * @param	bufflen TCHAR文字列バッファのサイズ
 * @return	コピーした文字数
 */
int convert_to_TCHAR(const java_utf8* utf8, TCHAR* buff, unsigned int bufflen) {
	unsigned int buffpos = 0;
	u4 bytepos = 0;
	u4 length = strlen(utf8);
	while (bytepos < length) {
		// バッファサイズを超える場合（終端文字分も含む）
		if (buffpos + 1 >= bufflen) {
			break;
		}
		u1 b = utf8[bytepos++];
		if ((b & 0x80) == 0) {
			// １バイト：0xxxxxxx
			buff[buffpos] = (TCHAR) b;
		} else if ((b & 0xe0) == 0xc0) {
			// ２バイト 110xxxxx : 10yyyyyy -> 00000xxxxxyyyyyy
			u1 b2 = utf8[bytepos++];
			buff[buffpos] = (TCHAR) (((b & 0x1f) << 6) | (b2 & 0x3f));
		} else if ((b & 0xf0) == 0xe0) {
			// ３バイト 1110xxxx:10yyyyyy:10zzzzzz -> xxxxyyyyyyzzzzzz
			u1 b2 = utf8[bytepos++];
			u1 b3 = utf8[bytepos++];
			buff[buffpos] = (TCHAR) (((b & 0x0f) << 12) | ((b2 & 0x3f) << 6) | (b3 & 0x3f));
		}
		buffpos++;
	}

	// 終端文字を入れる
	buff[buffpos] = _T('\0');

	// 文字列の長さを返す
	return buffpos;
}

/**
 * TCHAR文字列の内容を、UTF-8文字列に変換する
 * 変換後のUTF-8文字列は、必ず'\0'で終端される
 *
 * @param	src			TCHAR文字列のバッファ
 * @param	srclen		変換対象となる文字数。-1の場合には_T('\0')までを変換対象とする
 * @param	utf8buff	変換後ののデータが入るバッファ
 * @param	utf8bufflen	変換後のバッファサイズ
 * @return  コピーしたバイト数
 */
int convert_to_utf8(const TCHAR* src, int srclen, char* utf8buff, int utf8bufflen) {
	unsigned int srcpos = 0;
	int bytepos = 0;
	TCHAR c;
	for (;;) {
		c = src[srcpos++];
		if (srclen == -1) {
			if (c == _T('\0')) {
				break;
			}
		} else if (srclen-- <= 0) {
			break;
		}
		if (c >= 0x0001 && c <= 0x007f) {
			// １バイト 0xxxxxxx
			if (bytepos >= utf8bufflen - 1) {
				break;
			}
			utf8buff[bytepos++] = (u1) c;	// 単純に上位8ビットを捨てる
		} else if (c == 0x0000 || (c >= 0x0080 && c <= 0x07ff)) {
			// ２バイト 110xxxxx 10xxxxxx
			if (bytepos >= utf8bufflen - 2) {
				break;
			}
			utf8buff[bytepos++] = 0xc0 | ((c >> 6) & 0x3f);
			utf8buff[bytepos++] = 0x80 | (c & 0x3f);
		} else {
			// ３バイト 111xxxxx 10xxxxxx 10xxxxxx
			if (bytepos >= utf8bufflen - 3) {
				break;
			}
			utf8buff[bytepos++] = 0xe0 | ((c >> 12) & 0x0f);
			utf8buff[bytepos++] = 0x80 | ((c >> 6) & 0x003f);
			utf8buff[bytepos++] = 0x80 | (c & 0x3f);
		}
	}
	utf8buff[bytepos] = '\0';
	return bytepos;
}

/**
 * 指定されたTCHARをUTF-8に変換した場合のバイト数を返す
 *
 * @param	src		変換対象となる文字列
 * @param	srclen	変換する文字数
 */
int get_utf8_length_of(const TCHAR* src, int srclen) {
	int count = 0;
	while (srclen--) {
		_TCHAR c = *src++;
		if (c >= 0x0001 && c <= 0x007f) {
			count++;
		} else if (c == 0x0000 || (c >= 0x0080 && 0x07ff)) {
			count += 2;
		} else {
			count += 3;
		}
	}
	return count;
}


/**
 * 指定されたバイトが存在する位置を返す。
 */
int last_index_of(const java_utf8* utf8, u1 data) {
	u4 length = strlen(utf8);
	for (u4 i = length; i != 0; --i) {
		if (utf8[i - 1] == data) {
			return i;
		}
	}
	return -1;
}
