Usermode/Libraries/libspiderscript.so_src/bytecode_gen.c

   1 /*
   2  * SpiderScript Library
   3  * by John Hodge (thePowersGang)
   4  *
   5  * bytecode_gen.c
   6  * - Generate bytecode
   7  */
   8 #include <stdlib.h>
   9 #include <stdint.h>
  10 #include "bytecode_ops.h"
  11 #include <stdio.h>
  12 #include "bytecode_gen.h"
  13 #include <string.h>
  14 #include "bytecode.h"
  15
  16 // === IMPORTS ===
  17
  18 // === STRUCTURES ===
  19
  20 // === PROTOTYPES ===
  21 tBC_Op  *Bytecode_int_AllocateOp(int Operation, int ExtraBytes);
  22  int    Bytecode_int_AddVariable(tBC_Function *Handle, const char *Name);
  23
  24 // === GLOBALS ===
  25
  26 // === CODE ===
  27 tBC_Op *Bytecode_int_AllocateOp(int Operation, int ExtraBytes)
  28 {
  29         tBC_Op  *ret;
  30
  31         ret = malloc(sizeof(tBC_Op) + ExtraBytes);
  32         if(!ret)        return NULL;
  33
  34         ret->Next = NULL;
  35         ret->Operation = Operation;
  36         ret->bUseInteger = 0;
  37         ret->bUseString = (ExtraBytes > 0);
  38
  39         return ret;
  40 }
  41
  42 tBC_Function *Bytecode_CreateFunction(tScript_Function *Fcn)
  43 {
  44         tBC_Function *ret;
  45          int    i;
  46
  47         ret = malloc(sizeof(tBC_Function));
  48         if(!ret)        return NULL;
  49
  50         ret->LabelSpace = ret->LabelCount = 0;
  51         ret->Labels = NULL;
  52
  53         ret->MaxVariableCount = 0;
  54         ret->CurContextDepth = 0;
  55         ret->VariableCount = ret->VariableSpace = 0;
  56         ret->VariableNames = NULL;
  57
  58         ret->OperationCount = 0;
  59         ret->Operations = NULL;
  60         ret->OperationsEnd = (void*)&ret->Operations;
  61
  62         for( i = 0; i < Fcn->ArgumentCount; i ++ )
  63         {
  64                 Bytecode_int_AddVariable(ret, Fcn->Arguments[i].Name);
  65         }
  66
  67         return ret;
  68 }
  69
  70 void Bytecode_DeleteFunction(tBC_Function *Fcn)
  71 {
  72         tBC_Op  *op;
  73         for( op = Fcn->Operations; op; )
  74         {
  75                 tBC_Op  *nextop = op->Next;
  76                 free(op);
  77                 op = nextop;
  78         }
  79         free(Fcn->VariableNames);
  80         free(Fcn->Labels);
  81         free(Fcn);
  82 }
  83
  84 int StringList_GetString(tStringList *List, const char *String, int Length)
  85 {
  86          int    strIdx = 0;
  87         tString *ent;
  88         for(ent = List->Head; ent; ent = ent->Next, strIdx ++)
  89         {
  90                 if(ent->Length == Length && memcmp(ent->Data, String, Length) == 0)     break;
  91         }
  92         if( ent ) {
  93                 ent->RefCount ++;
  94         }
  95         else {
  96                 ent = malloc(sizeof(tString) + Length + 1);
  97                 if(!ent)        return -1;
  98                 ent->Next = NULL;
  99                 ent->Length = Length;
 100                 ent->RefCount = 1;
 101                 memcpy(ent->Data, String, Length);
 102                 ent->Data[Length] = '\0';
 103
 104                 if(List->Head)
 105                         List->Tail->Next = ent;
 106                 else
 107                         List->Head = ent;
 108                 List->Tail = ent;
 109                 List->Count ++;
 110         }
 111         return strIdx;
 112 }
 113
 114 int Bytecode_int_Serialize(const tBC_Function *Function, void *Output, int *LabelOffsets, tStringList *Strings)
 115 {
 116         tBC_Op  *op;
 117          int    len = 0, idx = 0;
 118          int    i;
 119
 120         void _put_byte(uint8_t byte)
 121         {
 122                 uint8_t *buf = Output;
 123                 if(Output)      buf[len] = byte;
 124                 len ++;
 125         }
 126
 127         void _put_dword(uint32_t value)
 128         {
 129                 uint8_t *buf = Output;
 130                 if(Output) {
 131                         buf[len+0] = value & 0xFF;
 132                         buf[len+1] = value >> 8;
 133                         buf[len+2] = value >> 16;
 134                         buf[len+3] = value >> 24;
 135                 }
 136                 len += 4;
 137         }
 138
 139         void _put_index(uint32_t value)
 140         {
 141                 if( !Output && !value ) {
 142                         len += 5;
 143                         return ;
 144                 }
 145                 if( value < 0x8000 ) {
 146                         _put_byte(value >> 8);
 147                         _put_byte(value & 0xFF);
 148                 }
 149                 else if( value < 0x400000 ) {
 150                         _put_byte( (value >> 16) | 0x80 );
 151                         _put_byte(value >> 8);
 152                         _put_byte(value & 0xFF);
 153                 }
 154                 else {
 155                         _put_byte( 0xC0 );
 156                         _put_byte(value >> 24);
 157                         _put_byte(value >> 16);
 158                         _put_byte(value >> 8 );
 159                         _put_byte(value & 0xFF);
 160                 }
 161         }
 162
 163         void _put_qword(uint64_t value)
 164         {
 165                 if( value < 0x80 ) {    // 7 bits into 1 byte
 166                         _put_byte(value);
 167                 }
 168                 else if( !(value >> (8+6)) ) {  // 14 bits packed into 2 bytes
 169                         _put_byte( 0x80 | ((value >> 8) & 0x3F) );
 170                         _put_byte( value & 0xFF );
 171                 }
 172                 else if( !(value >> (32+5)) ) { // 37 bits into 5 bytes
 173                         _put_byte( 0xC0 | ((value >> 32) & 0x1F) );
 174                         _put_dword(value & 0xFFFFFFFF);
 175                 }
 176                 else {
 177                         _put_byte( 0xE0 );      // 64 (actually 68) bits into 9 bytes
 178                         _put_dword(value & 0xFFFFFFFF);
 179                         _put_dword(value >> 32);
 180                 }
 181         }
 182
 183         void _put_double(double value)
 184         {
 185                 // TODO: Machine agnostic
 186                 if(Output) {
 187                         *(double*)( (char*)Output + len ) = value;
 188                 }
 189                 len += sizeof(double);
 190         }
 191
 192         void _put_string(const char *str, int len)
 193         {
 194                  int    strIdx = 0;
 195                 if( Output ) {
 196                         strIdx = StringList_GetString(Strings, str, len);
 197                 }
 198
 199                 // TODO: Relocations
 200                 _put_index(strIdx);
 201         }
 202
 203         for( op = Function->Operations; op; op = op->Next, idx ++ )
 204         {
 205                 // If first run, convert labels into byte offsets
 206                 if( !Output )
 207                 {
 208                         for( i = 0; i < Function->LabelCount; i ++ )
 209                         {
 210                                 if(LabelOffsets[i])     continue;
 211                                 if(op != Function->Labels[i])   continue;
 212
 213                                 LabelOffsets[i] = len;
 214                         }
 215                 }
 216
 217                 _put_byte(op->Operation);
 218                 switch(op->Operation)
 219                 {
 220                 // Relocate jumps (the value only matters if `Output` is non-NULL)
 221                 case BC_OP_JUMP:
 222                 case BC_OP_JUMPIF:
 223                 case BC_OP_JUMPIFNOT:
 224                         // TODO: Relocations?
 225                         _put_index( LabelOffsets[op->Content.StringInt.Integer] );
 226                         break;
 227                 // Special case for inline values
 228                 case BC_OP_LOADINT:
 229                         _put_qword(op->Content.Integer);
 230                         break;
 231                 case BC_OP_LOADREAL:
 232                         _put_double(op->Content.Real);
 233                         break;
 234                 case BC_OP_LOADSTR:
 235                         _put_string(op->Content.StringInt.String, op->Content.StringInt.Integer);
 236                         break;
 237                 // Everthing else just gets handled nicely
 238                 default:
 239                         if( op->bUseString )
 240                                 _put_string(op->Content.StringInt.String, strlen(op->Content.StringInt.String));
 241                         if( op->bUseInteger )
 242                                 _put_index(op->Content.StringInt.Integer);
 243                         break;
 244                 }
 245         }
 246
 247         return len;
 248 }
 249
 250 char *Bytecode_SerialiseFunction(const tBC_Function *Function, int *Length, tStringList *Strings)
 251 {
 252          int    len;
 253          int    *label_offsets;
 254         char    *code;
 255
 256         label_offsets = calloc( sizeof(int), Function->LabelCount );
 257         if(!label_offsets)      return NULL;
 258
 259         len = Bytecode_int_Serialize(Function, NULL, label_offsets, Strings);
 260
 261         code = malloc(len);
 262
 263         // Update length to the correct length (may decrease due to encoding)
 264         len = Bytecode_int_Serialize(Function, code, label_offsets, Strings);
 265
 266         free(label_offsets);
 267
 268         *Length = len;
 269
 270         return code;
 271 }
 272
 273 int Bytecode_AllocateLabel(tBC_Function *Handle)
 274 {
 275          int    ret;
 276
 277         if( Handle->LabelCount == Handle->LabelSpace ) {
 278                 void *tmp;
 279                 Handle->LabelSpace += 20;       // TODO: Don't hardcode increment
 280                 tmp = realloc(Handle->Labels, Handle->LabelSpace * sizeof(Handle->Labels[0]));
 281                 if( !tmp ) {
 282                         Handle->LabelSpace -= 20;
 283                         return -1;
 284                 }
 285                 Handle->Labels = tmp;
 286         }
 287         ret = Handle->LabelCount ++;
 288         Handle->Labels[ret] = 0;
 289         return ret;
 290 }
 291
 292 void Bytecode_SetLabel(tBC_Function *Handle, int Label)
 293 {
 294         if(Label < 0)   return ;
 295
 296         if(Label >= Handle->LabelCount) return ;
 297
 298         Handle->Labels[Label] = Handle->OperationsEnd;
 299         return ;
 300 }
 301
 302 void Bytecode_int_AppendOp(tBC_Function *Fcn, tBC_Op *Op)
 303 {
 304         Op->Next = NULL;
 305         if( Fcn->Operations )
 306                 Fcn->OperationsEnd->Next = Op;
 307         else
 308                 Fcn->Operations = Op;
 309         Fcn->OperationsEnd = Op;
 310 }
 311
 312 int Bytecode_int_AddVariable(tBC_Function *Handle, const char *Name)
 313 {
 314         if(Handle->VariableCount == Handle->VariableSpace) {
 315                 void    *tmp;
 316                 Handle->VariableSpace += 10;
 317                 tmp = realloc(Handle->VariableNames, Handle->VariableSpace * sizeof(Handle->VariableNames[0]));
 318                 if(!tmp)        return -1;      // TODO: Error
 319                 Handle->VariableNames = tmp;
 320         }
 321         Handle->VariableNames[Handle->VariableCount] = Name;
 322         Handle->VariableCount ++;
 323         // Get max count (used when executing to get the frame size)
 324         if(Handle->VariableCount - Handle->CurContextDepth >= Handle->MaxVariableCount)
 325                 Handle->MaxVariableCount = Handle->VariableCount - Handle->CurContextDepth;
 326 //      printf("_AddVariable: %s given %i\n", Name, Handle->VariableCount - Handle->CurContextDepth - 1);
 327         return Handle->VariableCount - Handle->CurContextDepth - 1;
 328 }
 329
 330 int Bytecode_int_GetVarIndex(tBC_Function *Handle, const char *Name)
 331 {
 332          int    i, context_depth = Handle->CurContextDepth;
 333         // Get the start of this context
 334         for( i = Handle->VariableCount; i --; )
 335         {
 336                 if( !Handle->VariableNames[i] ) {
 337                         context_depth --;
 338                         continue ;
 339                 }
 340                 if( strcmp(Name, Handle->VariableNames[i]) == 0 )
 341                         return i - context_depth;
 342         }
 343         return -1;
 344 }
 345
 346 #define DEF_BC_NONE(_op) { \
 347         tBC_Op *op = Bytecode_int_AllocateOp(_op, 0); \
 348         op->Content.Integer = 0; \
 349         op->bUseInteger = 0; \
 350         Bytecode_int_AppendOp(Handle, op);\
 351 }
 352
 353 #define DEF_BC_INT(_op, _int) {\
 354         tBC_Op *op = Bytecode_int_AllocateOp(_op, 0);\
 355         op->Content.StringInt.Integer = _int;\
 356         op->bUseInteger = 1;\
 357         op->bUseString = 0;\
 358         Bytecode_int_AppendOp(Handle, op);\
 359 }
 360
 361 #define DEF_BC_STRINT(_op, _str, _int) { \
 362         tBC_Op *op = Bytecode_int_AllocateOp(_op, strlen(_str));\
 363         op->Content.StringInt.Integer = _int;\
 364         strcpy(op->Content.StringInt.String, _str);\
 365         op->bUseInteger = 1;\
 366         op->bUseString = 1;\
 367         Bytecode_int_AppendOp(Handle, op);\
 368 }
 369 #define DEF_BC_STR(_op, _str) {\
 370         tBC_Op *op = Bytecode_int_AllocateOp(_op, strlen(_str));\
 371         strcpy(op->Content.StringInt.String, _str);\
 372         op->bUseInteger = 0;\
 373         Bytecode_int_AppendOp(Handle, op);\
 374 }
 375
 376 // --- Flow Control
 377 void Bytecode_AppendJump(tBC_Function *Handle, int Label)
 378         DEF_BC_INT(BC_OP_JUMP, Label)
 379 void Bytecode_AppendCondJump(tBC_Function *Handle, int Label)
 380         DEF_BC_INT(BC_OP_JUMPIF, Label)
 381 void Bytecode_AppendCondJumpNot(tBC_Function *Handle, int Label)
 382         DEF_BC_INT(BC_OP_JUMPIFNOT, Label)
 383 void Bytecode_AppendReturn(tBC_Function *Handle)
 384         DEF_BC_NONE(BC_OP_RETURN);
 385
 386 // --- Variables
 387 void Bytecode_AppendLoadVar(tBC_Function *Handle, const char *Name)
 388         DEF_BC_INT(BC_OP_LOADVAR, Bytecode_int_GetVarIndex(Handle, Name))
 389 //      DEF_BC_STR(BC_OP_LOADVAR, Name)
 390 void Bytecode_AppendSaveVar(tBC_Function *Handle, const char *Name)     // (Obj->)?var =
 391         DEF_BC_INT(BC_OP_SAVEVAR, Bytecode_int_GetVarIndex(Handle, Name))
 392 //      DEF_BC_STR(BC_OP_SAVEVAR, Name)
 393
 394 // --- Constants
 395 void Bytecode_AppendConstInt(tBC_Function *Handle, uint64_t Value)
 396 {
 397         tBC_Op *op = Bytecode_int_AllocateOp(BC_OP_LOADINT, 0);
 398         op->Content.Integer = Value;
 399         Bytecode_int_AppendOp(Handle, op);
 400 }
 401 void Bytecode_AppendConstReal(tBC_Function *Handle, double Value)
 402 {
 403         tBC_Op *op = Bytecode_int_AllocateOp(BC_OP_LOADREAL, 0);
 404         op->Content.Real = Value;
 405         Bytecode_int_AppendOp(Handle, op);
 406 }
 407 void Bytecode_AppendConstString(tBC_Function *Handle, const void *Data, size_t Length)
 408 {
 409         tBC_Op *op = Bytecode_int_AllocateOp(BC_OP_LOADSTR, Length+1);
 410         op->Content.StringInt.Integer = Length;
 411         memcpy(op->Content.StringInt.String, Data, Length);
 412         op->Content.StringInt.String[Length] = 0;
 413         Bytecode_int_AppendOp(Handle, op);
 414 }
 415 void Bytecode_AppendConstNull(tBC_Function *Handle)
 416         DEF_BC_NONE(BC_OP_LOADNULL)
 417
 418 // --- Indexing / Scoping
 419 void Bytecode_AppendElement(tBC_Function *Handle, const char *Name)
 420         DEF_BC_STR(BC_OP_ELEMENT, Name)
 421 void Bytecode_AppendSetElement(tBC_Function *Handle, const char *Name)
 422         DEF_BC_STR(BC_OP_SETELEMENT, Name)
 423 void Bytecode_AppendIndex(tBC_Function *Handle)
 424         DEF_BC_NONE(BC_OP_INDEX)
 425 void Bytecode_AppendSetIndex(tBC_Function *Handle)
 426         DEF_BC_NONE(BC_OP_SETINDEX);
 427
 428 void Bytecode_AppendCreateObj(tBC_Function *Handle, const char *Name, int ArgumentCount)
 429         DEF_BC_STRINT(BC_OP_CREATEOBJ, Name, ArgumentCount)
 430 void Bytecode_AppendMethodCall(tBC_Function *Handle, const char *Name, int ArgumentCount)
 431         DEF_BC_STRINT(BC_OP_CALLMETHOD, Name, ArgumentCount)
 432 void Bytecode_AppendFunctionCall(tBC_Function *Handle, const char *Name, int ArgumentCount)
 433         DEF_BC_STRINT(BC_OP_CALLFUNCTION, Name, ArgumentCount)
 434
 435 void Bytecode_AppendBinOp(tBC_Function *Handle, int Operation)
 436         DEF_BC_NONE(Operation)
 437 void Bytecode_AppendUniOp(tBC_Function *Handle, int Operation)
 438         DEF_BC_NONE(Operation)
 439 void Bytecode_AppendCast(tBC_Function *Handle, int Type)
 440         DEF_BC_INT(BC_OP_CAST, Type)
 441 void Bytecode_AppendDuplicate(tBC_Function *Handle)
 442         DEF_BC_NONE(BC_OP_DUPSTACK);
 443 void Bytecode_AppendDelete(tBC_Function *Handle)
 444         DEF_BC_NONE(BC_OP_DELSTACK);
 445
 446 // Does some bookeeping to allocate variable slots at compile time
 447 void Bytecode_AppendEnterContext(tBC_Function *Handle)
 448 {
 449         Handle->CurContextDepth ++;
 450         Bytecode_int_AddVariable(Handle, NULL); // NULL to record the extent of this
 451
 452         DEF_BC_NONE(BC_OP_ENTERCONTEXT)
 453 }
 454 void Bytecode_AppendLeaveContext(tBC_Function *Handle)
 455 {
 456          int    i;
 457         for( i = Handle->VariableCount; i --; )
 458         {
 459                 if( Handle->VariableNames[i] == NULL )  break;
 460         }
 461         Handle->CurContextDepth --;
 462         Handle->VariableCount = i;
 463
 464         DEF_BC_NONE(BC_OP_LEAVECONTEXT);
 465 }
 466 //void Bytecode_AppendImportNamespace(tBC_Function *Handle, const char *Name);
 467 //      DEF_BC_STRINT(BC_OP_IMPORTNS, Name, 0)
 468 void Bytecode_AppendDefineVar(tBC_Function *Handle, const char *Name, int Type)
 469 {
 470          int    i;
 471         #if 1
 472         // Get the start of this context
 473         for( i = Handle->VariableCount; i --; )
 474         {
 475                 if( Handle->VariableNames[i] == NULL )  break;
 476         }
 477         // Check for duplicate allocation
 478         for( i ++; i < Handle->VariableCount; i ++ )
 479         {
 480                 if( strcmp(Name, Handle->VariableNames[i]) == 0 )
 481                         return ;
 482         }
 483         #endif
 484
 485         i = Bytecode_int_AddVariable(Handle, Name);
 486 //      printf("Variable %s given slot %i\n", Name, i);
 487
 488         DEF_BC_STRINT(BC_OP_DEFINEVAR, Name, (Type&0xFFFF) | (i << 16))
 489 }