Trivial Solutions The LoseThos 64-bit PC Operating System File:/LT/OSMain/Hash1a.CPZ This, and all LoseThos files, are public domain. Do whatever you like. God is watching; God is just; God is never out-done in generosity. He talks! LoseThos code compiles with the 64-bit LoseThos compiler/assembler I wrote. Boot the LoseThos CD and you can compile it. Not in Kansas anymore! Click here for preliminary compiler information you need. Project: OSMain /**** <1>/* Graphics Not Rendered in HTML */ Tasks have symbol tables. If symbol not found, parent task's table is searched. Adam task has system-wide symbols. SYMBOL LOOK-UP (Especially, used by JIT compiler and Loader) 1) Symbol text name is hashed -- Adding the ASCII values of all chars with shifts. 2) Hash body array is indexed. 3) Linked-list is traversed until match of text and type-of-entry 4) If not found, next hash table is searched. Duplicate entries are allowed--they overshadow old entries. ADDRESS-TO-SYMBOL LOOK-UP (Slow because not important--could add tree) 1)PSect Cache is scanned. 2)"next_added,last_added" queue links are traversed. This speeds look-up instead of scanning hash table because hash table is so sparce. See PSectFind(). ****/ asm { USE64 // ************************************ // IN: RSI=Addr of string // OUT: RAX SYS_HASH_STR:: PUSH RSI PUSH RBX XOR RAX,RAX XOR RBX,RBX JMP @@10 @@05: SHL RBX,1 ADC RBX,RAX @@10: LODSB OR AL,AL JNZ @@05 MOV RAX,RBX SHR RBX,16 ADC RAX,RBX POP RBX POP RSI RET // ************************************ // IN: RAX=HASHED_STRING // RSI=STR // RBX=TYPE MASK // RDI=TABLE // RCX=INSTANCE, NOT ZERO // OUT: RAX=ENTRY OR ZERO NOT FOUND // RDX=POINTER TO POINTER TO ENTRY // RCX IF NOT FOUND ENOUGH, DECREMENTED BY NUM MATCHES // ZERO FLAG SET NOT FOUND SYS_HASH_SINGLE_TABLE_FIND1:: MOV RCX,1 SYS_HASH_SINGLE_TABLE_FIND:: OR RCX,RCX JNZ @@05 XOR RAX,RAX RET @@05: AND RAX,U64 HT_MASK[RDI] MOV RDX,U64 HT_BODY[RDI] LEA RDX,U64 [RDX+RAX*8] @@10: MOV RAX,U64 [RDX] OR RAX,RAX JNZ @@15 RET @@15: TEST U32 HTE_TYPE[RAX],EBX JZ @@30 PUSH RAX PUSH RDI PUSH RSI MOV RDI,U64 HTE_STR[RAX] @@20: LODSB CMP U8 [RDI],AL JNE @@25 INC RDI OR AL,AL JNZ @@20 POP RSI POP RDI POP RAX LOOP @@30 INC U32 HTE_USE_CNT[RAX] OR RAX,RAX RET @@25: POP RSI POP RDI POP RAX @@30: LEA RDX,U64 HTE_NEXT[RAX] JMP @@10 // ************************************ // IN: RSI=STR // RBX=TYPE MASK // RDI=TABLE // RCX=INSTANCE NUM // OUT: RAX=ENTRY OR ZERO NOT FOUND // ZERO FLAG SET NOT FOUND SYS_HASH_FIND1:: MOV RCX,1 SYS_HASH_FIND:: PUSH RDI CALL SYS_HASH_STR @@05: PUSH RAX CALL SYS_HASH_SINGLE_TABLE_FIND JNZ @@15 POP RAX @@10: MOV RDI,U64 HT_NEXT[RDI] OR RDI,RDI JNZ @@05 POP RDI XOR RAX,RAX RET @@15: ADD RSP,8 POP RDI OR RAX,RAX RET // ************************************ // IN: RSI=STR // RDI=TABLE // OUT: RAX=BUCKET SYS_HASH_BUCKET_FIND:: PUSH RDX CALL SYS_HASH_STR AND RAX,U64 HT_MASK[RDI] MOV RDX,U64 HT_BODY[RDI] LEA RAX,U64 [RDX+RAX*8] POP RDX RET // ************************************ //IN: RSI // RCX=INSTANCE //OUT: RAX // ZERO FLAG SET NOT FOUND SYS_EXT_FIND1:: MOV RCX,1 SYS_EXT_FIND:: PUSH RDI PUSH RBX XOR RAX,RAX MOV RDI,U64 FS:TASK_HASH_TABLE[RAX] MOV RBX,HTT_FUN|HTT_EXPORT_SYS_SYM CALL SYS_HASH_FIND JZ @@15 @@05: TEST U32 HTE_TYPE[RAX],HTT_FUN JZ @@10 MOV RAX,U64 offset(ClassStruct.executable_addr)[RAX] JMP @@15 @@10: MOV RAX,U64 HTE_VAL[RAX] @@15: POP RBX POP RDI OR RAX,RAX RET _EXT_FIND:: ENTER 0 PUSH RSI PUSH RDI XOR RAX,RAX MOV RDI,U64 FS:TASK_HASH_TABLE[RAX] MOV RSI,U64 SF_ARG1[RBP] MOV RCX,U64 SF_ARG2[RBP] MOV RBX,HTT_FUN|HTT_EXPORT_SYS_SYM CALL SYS_HASH_FIND JZ @@15 @@05: TEST U32 HTE_TYPE[RAX],HTT_FUN JZ @@10 MOV RAX,U64 offset(ClassStruct.executable_addr)[RAX] JMP @@15 @@10: MOV RAX,U64 HTE_VAL[RAX] @@15: POP RDI POP RSI LEAVE RET1 16 // ************************************ _HASH_STR:: ENTER 0 PUSH RSI MOV RSI,U64 SF_ARG1[RBP] CALL SYS_HASH_STR POP RSI LEAVE RET1 8 // ************************************ _HASH_FIND:: ENTER 0 PUSH RSI PUSH RDI MOV RSI,U64 SF_ARG1[RBP] MOV RDI,U64 SF_ARG2[RBP] MOV RBX,U64 SF_ARG3[RBP] MOV RCX,U64 SF_ARG4[RBP] CALL SYS_HASH_FIND POP RDI POP RSI LEAVE RET1 32 // ************************************ _HASH_SINGLE_TABLE_FIND:: ENTER 0 PUSH RSI PUSH RDI MOV RSI,U64 SF_ARG1[RBP] MOV RDI,U64 SF_ARG2[RBP] MOV RBX,U64 SF_ARG3[RBP] MOV RCX,U64 SF_ARG4[RBP] CALL SYS_HASH_STR CALL SYS_HASH_SINGLE_TABLE_FIND POP RDI POP RSI LEAVE RET1 32 // ************************************ _HASH_BUCKET_FIND:: ENTER 0 PUSH RSI PUSH RDI MOV RSI,U64 SF_ARG1[RBP] MOV RDI,U64 SF_ARG2[RBP] CALL SYS_HASH_BUCKET_FIND POP RDI POP RSI LEAVE RET1 16 // ************************************ _HASH_ADD:: ENTER 0 PUSH RSI PUSH RDI MOV RCX,U64 SF_ARG1[RBP] MOV RSI,U64 HTE_STR[RCX] MOV RDI,U64 SF_ARG2[RBP] CALL SYS_HASH_BUCKET_FIND MOV RCX,U64 SF_ARG1[RBP] PUSHFD CLI MOV RBX,U64 [RAX] MOV U64 HTE_NEXT[RCX],RBX MOV U64 [RAX],RCX //Insque MOV RBX,U64 HT_LAST_ADDED[RDI] MOV U64 HTE_LAST_ADDED[RCX],RBX MOV U64 HTE_NEXT_ADDED[RBX],RCX MOV U64 HT_LAST_ADDED[RDI],RCX MOV U64 HTE_NEXT_ADDED[RCX],RDI POPFD POP RDI POP RSI LEAVE RET1 16 // ************************************ _HASH_ADD_AFTER:: ENTER 0 PUSH RDI MOV RCX,U64 SF_ARG1[RBP] MOV RDI,U64 SF_ARG3[RBP] PUSHFD CLI MOV RAX,SF_ARG2[RBP] MOV RBX,U64 [RAX] MOV U64 HTE_NEXT[RCX],RBX MOV U64 [RAX],RCX //Insque MOV RBX,U64 HT_LAST_ADDED[RDI] MOV U64 HTE_LAST_ADDED[RCX],RBX MOV U64 HTE_NEXT_ADDED[RBX],RCX MOV U64 HT_LAST_ADDED[RDI],RCX MOV U64 HTE_NEXT_ADDED[RCX],RDI POPFD POP RDI LEAVE RET1 24 // ************************************ _HASH_REPLACE:: ENTER 0 PUSH RSI PUSH RDI MOV RCX,U64 SF_ARG1[RBP] OR RCX,RCX JZ @@15 MOV RSI,U64 HTE_STR[RCX] XOR RBX,RBX MOV EBX,U32 HTE_TYPE[RCX] AND EBX,~(HTT_PRIVATE|HTT_PUBLIC|HTT_EXPORT|HTT_IMPORT|HTT_LITERAL| HTT_UNRESOLVED_LOCAL|HTT_UNRESOLVED_GLBL)&0xFFFFFFFF MOV RDI,U64 SF_ARG2[RBP] MOV RCX,U64 SF_ARG3[RBP] CALL SYS_HASH_STR PUSHFD CLI CALL SYS_HASH_SINGLE_TABLE_FIND MOV RCX,U64 SF_ARG1[RBP] JZ @@05 //Z set by find //Remque/Insque MOV RBX,U64 HTE_NEXT_ADDED[RAX] MOV U64 HTE_NEXT_ADDED[RCX],RBX MOV U64 HTE_LAST_ADDED[RBX],RCX MOV RBX,U64 HTE_LAST_ADDED[RAX] MOV U64 HTE_LAST_ADDED[RCX],RBX MOV U64 HTE_NEXT_ADDED[RBX],RCX MOV RBX,U64 HTE_NEXT[RAX] JMP @@10 //Insque @@05: MOV RBX,U64 HT_LAST_ADDED[RDI] MOV U64 HTE_LAST_ADDED[RCX],RBX MOV U64 HTE_NEXT_ADDED[RBX],RCX MOV U64 HT_LAST_ADDED[RDI],RCX MOV U64 HTE_NEXT_ADDED[RCX],RDI MOV RBX,RAX @@10: MOV U64 HTE_NEXT[RCX],RBX MOV U64 [RDX],RCX POPFD OR RAX,RAX JZ @@15 PUSH_C_REGS PUSH RAX CALL &HashDel POP_C_REGS @@15: POP RDI POP RSI LEAVE RET1 24 // ************************************ _HASH_REM_DEL:: ENTER 0 PUSH RSI PUSH RDI MOV RCX,U64 SF_ARG1[RBP] OR RCX,RCX JZ @@10 MOV RSI,U64 HTE_STR[RCX] XOR RBX,RBX MOV EBX,U32 HTE_TYPE[RCX] AND EBX,~(HTT_PRIVATE|HTT_PUBLIC|HTT_EXPORT|HTT_IMPORT|HTT_LITERAL| HTT_UNRESOLVED_LOCAL|HTT_UNRESOLVED_GLBL)&0xFFFFFFFF MOV RDI,U64 SF_ARG2[RBP] MOV RCX,U64 SF_ARG3[RBP] CALL SYS_HASH_STR PUSHFD CLI CALL SYS_HASH_SINGLE_TABLE_FIND JZ @@05 CMP RAX,U64 SF_ARG1[RBP] JNE @@05 MOV RBX,U64 HTE_NEXT[RAX] MOV U64 [RDX],RBX //Remque MOV RBX,U64 HTE_NEXT_ADDED[RAX] MOV RDX,U64 HTE_LAST_ADDED[RAX] MOV U64 HTE_NEXT_ADDED[RDX],RBX MOV U64 HTE_LAST_ADDED[RBX],RDX POPFD PUSH_C_REGS PUSH RAX CALL &HashDel POP_C_REGS POP RDI POP RSI MOV RAX,1 LEAVE RET1 24 @@05: POPFD @@10: POP RDI POP RSI XOR RAX,RAX LEAVE RET1 24 } LTextern _HASH_STR U64 HashStr(U8 *st); LTextern _HASH_FIND SysHashEntry * HashFind(U8 *st,SysHashTable *table,U64 mask,U64 instance=1); LTextern _HASH_SINGLE_TABLE_FIND SysHashEntry * HashSingleTableFind(U8 *st,SysHashTable *table,U64 mask,U64 instance=1); LTextern _HASH_BUCKET_FIND SysHashEntry ** HashBucketFind(U8 *st,SysHashTable *table); LTextern _HASH_ADD U0 HashAdd(SysHashEntry *temph,SysHashTable *table); LTextern _HASH_REPLACE U0 HashReplace(SysHashEntry *temph,SysHashTable *table, U64 instance=1);//instance must match temph's LTextern _HASH_REM_DEL BoolI64 HashRemDel(SysHashEntry *temph,SysHashTable *table, U64 instance=1);//instance must match temph's SysHashTable *HashTableNew(U64 size,TaskStruct *mem_task=NULL) { SysHashTable *tempht; tempht=CAlloc(sizeof(SysHashTable),mem_task); tempht->body=CAlloc(size<<3,mem_task); tempht->mask=size-1; tempht->next_added=tempht->last_added=tempht; return tempht; } U0 HashDel(SrcSymHashEntry *temph) { if (!temph) return; if (!(temph->type&HTT_DICT_WORD)) Free(temph->str); if (temph->type & HTT_SRC_SYM) { Free(temph->src_link); Free(temph->index); Free(temph->import_name); LinkedListDel(temph->list); if (temph->type & (HTT_FUN | HTT_EXPORT_SYS_SYM)) { Free(temph->debug); Free(temph->indent); } if (temph->type & (HTT_FUN | HTT_CLASS)) //Assumes code not on heap, so doesn't Free. //MemberListDel() is an import to the OSMain module MemberListDel(temph); else if (temph->type&HTT_DEFINE_STR) Free(temph><(DefineStrHashEntry *)->data); else if (temph->type & HTT_GLBL_VAR) { if (!(temph><(GlblVarStruct *)->flags&GVAF_ALIAS)) Free(temph><(GlblVarStruct *)->data_addr); LinkedListDel(temph><(GlblVarStruct *)->dim.next); if (temph><(GlblVarStruct *)->fun_ptr) HashDel(temph><(GlblVarStruct *)->fun_ptr-temph><(GlblVarStruct *)->fun_ptr->ptr_cnt); } else if (temph->type & HTT_TYPEDEF) { LinkedListDel(temph><(GlblVarStruct *)->dim.next); if (temph><(GlblVarStruct *)->fun_ptr) HashDel(temph><(GlblVarStruct *)->fun_ptr-temph><(GlblVarStruct *)->fun_ptr->ptr_cnt); } } else if (temph->type & HTT_FILE) Free(temph><(GenericHashEntry *)->user_data0); Free(temph); } U0 HashTableDel(SysHashTable *tempht) { SrcSymHashEntry *temph,*temph1; if (!tempht) return; temph=tempht->next_added; while (temph!=tempht) { temph1=temph->next_added; HashDel(temph); temph=temph1; } Free(tempht->body); Free(tempht); } GenericHashEntry *HashGenericAdd(U8 *name,I64 type,I64 u0=0,I64 u1=0,I64 u2=0,TaskStruct *task=NULL) { GenericHashEntry *result; if (!task) task=Fs; result=CAlloc(sizeof(GenericHashEntry),task); result->type=type; result->user_data0=u0; result->user_data1=u1; result->user_data2=u2; result->str=StrNew(name,task); HashAdd(result,task->hash_table); return result; } I64 NamedFramePtr(U8 *name,TaskStruct *task=NULL) { GenericHashEntry *temph; if (!task) task=Fs; if (temph=HashFind(name,task->hash_table,HTT_NAMED_FRAME_PTR)) return temph->user_data0; else return 0; } GenericHashEntry *NamedFramePtrAdd(U8 *name,I64 u0,TaskStruct *task=NULL) { return HashGenericAdd(name,HTT_NAMED_FRAME_PTR,u0,0,0,task); } I64 NamedFramePtrSet(U8 *name,I64 u0,TaskStruct *task=NULL) { GenericHashEntry *temph; if (!task) task=Fs; if (temph=HashFind(name,task->hash_table,HTT_NAMED_FRAME_PTR)) return LXchgU64(&temph->user_data0,u0); else return 0; } I64 NamedFramePtrDel(U8 *name,TaskStruct *task=NULL) { I64 result=0; GenericHashEntry *temph; if (!task) task=Fs; if (temph=HashFind(name,task->hash_table,HTT_NAMED_FRAME_PTR)) { result=temph->user_data0; HashRemDel(temph,task->hash_table); } return result; } U0 LoadOneImport(U8 **_src,U8 *module_base,I64 ld_flags) { U8 *src=*_src,*ptr2,*st_ptr; I64 i,etype; ExportSysSymHashEntry *tempess=NULL; ImportSysSymHashEntry *tempiss; BoolI8 first=TRUE; ClassStruct *tempc; GlblVarStruct *tempg; while ((etype=*src++)!=EIE_END) { i=*src><(U32 *)++; st_ptr=src; src+=StrLen(st_ptr)+1; if (*st_ptr) { if (!first) { *_src=st_ptr-5; return; } else { first=FALSE; if (!(tempess=HashFind(st_ptr,Fs->hash_table,HTT_ALL-HTT_IMPORT_SYS_SYM))) { if (!(ld_flags & LDF_SILENT)) { PutDefine("ST_UNRESOLVED_REFERENCE"); "" st_ptr; NewLine; } tempiss=CAlloc(sizeof(ImportSysSymHashEntry)); tempiss->str=StrNew(st_ptr); tempiss->type=HTT_IMPORT_SYS_SYM; tempiss->module_header_entry=st_ptr-5; tempiss->module_base=module_base; HashAdd(tempiss,Fs->hash_table); } } } if (tempess) { ptr2=module_base+i; if (tempess->type & HTT_FUN) { tempc=tempess; if (etype & 1) i=tempc->executable_addr; else i=tempc->executable_addr-module_base; } else if (tempess->type & HTT_GLBL_VAR) { tempg=tempess; if (etype & 1) i=tempg->data_addr; else i=tempg->data_addr-module_base; } else { if (etype & 1) i=tempess->val; else i=tempess->val><(U8 *)-module_base; } if (etype<=EIE_LIT_U8) *ptr2><(U8 *)+=i; else if (etype<=EIE_LIT_U16) *ptr2><(U16 *)+=i; else if (etype<=EIE_LIT_U32) *ptr2><(U32 *)+=i; else if (etype<=EIE_LIT_U64) *ptr2><(U64 *)+=i; } } *_src=src-1; } U0 SysSymImportsResolve(U8 *st_ptr,I64 ld_flags) { ImportSysSymHashEntry *tempiss; U8 *ptr; while (tempiss=HashSingleTableFind(st_ptr,Fs->hash_table,HTT_IMPORT_SYS_SYM)) { ptr=tempiss->module_header_entry; LoadOneImport(&ptr,tempiss->module_base,ld_flags); tempiss->type=HTT_INVALID; } } U0 LoadPass1(U8 *src,U8 *module_base,I64 ld_flags) { U8 *ptr2,*ptr3; U8 *st_ptr; I64 i,j,cnt,etype; ExportSysSymHashEntry *tempess=NULL; while ((etype=*src++)!=EIE_END) { i=*src><(U32 *)++; st_ptr=src; src+=StrLen(st_ptr)+1; switch (etype) { case EIE_REL_EXPORT: case EIE_LIT_EXPORT: tempess=CAlloc(sizeof(ExportSysSymHashEntry)); tempess->str=StrNew(st_ptr); tempess->type=HTT_EXPORT_SYS_SYM|HTT_LITERAL; if (etype==EIE_LIT_EXPORT) tempess->val=i; else tempess->val=i+module_base; HashAdd(tempess,Fs->hash_table); SysSymImportsResolve(st_ptr,ld_flags); break; case EIE_REL_U8...EIE_LIT_U64: src=st_ptr-5; LoadOneImport(&src,module_base,ld_flags); break; case EIE_ABS_ADDR: if (ld_flags & LDF_NO_ABSS) src+=i*sizeof(U32); else { cnt=i; for (j=0;j<cnt;j++) { ptr2=module_base+*src><(U32 *)++; *ptr2><(U32 *)+=module_base; } } break; case EIE_HEAP_GLBL: ptr3=MAlloc(*src><(U64 *)++); if (*st_ptr) { tempess=CAlloc(sizeof(ExportSysSymHashEntry)); tempess->str=StrNew(st_ptr); tempess->type=HTT_EXPORT_SYS_SYM|HTT_LITERAL; tempess->val=ptr3; HashAdd(tempess,Fs->hash_table); } cnt=i; for (j=0;j<cnt;j++) { ptr2=module_base+*src><(U32 *)++; *ptr2><(U64 *)+=ptr3; } break; } } } U0 LoadPass2(U8 *src,U8 *module_base,I64 ld_flags) { nounusedwarn ld_flags; U8 *st_ptr; I64 i,etype; while ((etype=*src++)!=EIE_END) { i=*src><(U32 *)++; st_ptr=src; src+=StrLen(st_ptr)+1; switch (etype) { case EIE_MAIN: Call(i+module_base); break; case EIE_ABS_ADDR: src+=sizeof(U32)*i; break; case EIE_HEAP_GLBL: src+=8+sizeof(U32)*i; break; } } } U0 *Load(U8 *filename,U64 ld_flags=0,BinFileHeaderStruct *bfh_addr=-1) { //See BinRep(). //bfh_addr==-1 means don't care what load addr. U8 *fbuf; U8 *module_base; U8 *absname; U64 size,module_alignment; BinFileHeaderStruct *bfh2; fbuf=DftExt(filename,"BIZ"); if (!(bfh2=FileRead(fbuf,&size))) { Free(fbuf); return NULL; } //See Loader Patch Table Generation module_alignment=*(bfh2><(U8 *)+bfh2->loader_patch_table_offset+1)><(U32 *); if (!module_alignment || Bsf(module_alignment)!=Bsr(module_alignment)) throw(EXCEPT_BIN_MODULE); #assert sizeof(BinFileHeaderStruct)==16 if (bfh_addr==-1) { if (Fs->code_heap!=Fs->data_heap) { if (module_alignment<16) module_alignment=16; bfh_addr=MAllocAligned(size,module_alignment,Fs->code_heap,module_alignment-sizeof(BinFileHeaderStruct)); } else if (module_alignment>8) bfh_addr=MAllocAligned(size,module_alignment,NULL,module_alignment-sizeof(BinFileHeaderStruct)); else { bfh_addr=bfh2; goto lo_skip; } } MemCpy(bfh_addr,bfh2,size); Free(bfh2); lo_skip: module_base=bfh_addr><(U8 *)+sizeof(BinFileHeaderStruct); if (ArcXSum(bfh_addr,bfh_addr->file_size)!=LT_XSUM) throw(EXCEPT_ARC_XSUM); absname=FileNameAbs(fbuf); Free(fbuf); fbuf=StrNew(absname); FileExtRem(fbuf); if (fbuf[1]==':' && StrLen(fbuf)>2) HashGenericAdd(fbuf+2,HTT_MODULE|HTT_PUBLIC,bfh_addr); Free(fbuf); LoadPass1(bfh_addr><(U8 *)+bfh_addr->loader_patch_table_offset,module_base,ld_flags); if (!(ld_flags&LDF_JUST_LOAD)) LoadPass2(bfh_addr><(U8 *)+bfh_addr->loader_patch_table_offset,module_base,ld_flags); Free(absname); return bfh_addr; } U0 LoadOSMain() { HashGenericAdd(OSMAIN_MODULE_NAME,HTT_MODULE|HTT_PUBLIC,sys_boot_base-sizeof(BinFileHeaderStruct)); //Abs patches done here EIE_ABS_ADDR. LoadPass1(sys_boot_patch_table_base,sys_boot_base,LDF_NO_ABSS|LDF_SILENT); //No main routines // LoadPass2(sys_boot_patch_table_base,sys_boot_base,0); }