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