Wednesday, November 2, 2022

Implementing WHILE in a toy BASIC interpreter

While working on a toy BASIC implementation, I ran into an unexpected challenge implementing the WHILE instruction.

The implementation of this instruction seems simple. Here is an example :

10 X = 1
20 WHILE X <> 10
30 PRINT X
40 X = X + 1
50 WEND

This program is going to print the numbers from 1 to 9. The WHILE statement is really a combination of WHILE and WEND. The WEND statement indicates the end of the 'block'.

The first challenge is to create a relation between these statements. This relation is going to be used by the interpreter to identify where to 'jump' when evaluating WHILE and WEND. One interesting challenge is that BASIC (GWBASIC) supports `nested` WHILE blocks:

10 X = 10
20 Y = 10
30 WHILE X <> 0
40 PRINT "X = ", X
50 Y = 10
60 WHILE Y <> 0
70 PRINT "y =", Y
80 Y = Y - 1
90 WEND
100 X = X - 1
110 WEND

Since the source of the original GW-BASIC implementation is published in GitHub, we can take a look at it here: https://github.com/microsoft/GW-BASIC. There is code in GWMAIN.ASM used to search for the correspoing WEND of a WHILE (a code block called WNDSCN). This also seems to be used to locate the FOR=/=NEXT pair of instructions. It seems that the interpreter tries to find the matching instruction by scanning the instructions that follow the WHILE. A counter is used to keep track of nested WHILE/WEND blocks:

..
PUBLIC	WNDSCN
WNDSCN: MOV	CL,LOW OFFSET ERRWH	;SCAN FOR MATCHING WEND THIS IS ERROR IF FAIL
.
.
.
FORINC: INC	CH		;INCREMENT THE COUNT WHENEVER "FOR" IS SEEN
.
.
.
        JZ	SHORT NXTLOK	;FOR/NEXT SEARCHING
        CMP	AL,LOW OFFSET $WHILE	;ANOTHER WHILE/WEND NEST?
        JZ	SHORT FORINC
        CMP	AL,LOW OFFSET $WEND
        JNZ	SHORT FNLOP
        DEC	CH
.
.
.

1.2 Strategy

One way to start implementing this feature in the interpreter was to add a table (pair_instruction_table) to the interpreter context. This table is going to keep the relation between instructions. In particular it will be used to relate a WHILE and WEND pair. In the near future it will keep the relation between FOR and NEXT.

The evaluation context will now look like this:

pub struct EvaluationContext<'a> {
    pub variables: HashMap<String, ExpressionEvalResult>,
    pub array_variables: HashMap<String, GwArray>,
    pub jump_table: HashMap<i16, i16>,
    pub underlying_program: Option<&'a mut GwProgram>,   
    pub pair_instruction_table: HashMap<i16, i16>,
}

With this information we can create a search function that emulates the same behavior as WNDSCN . Something like this:

fn find_wend(line: i16, real_lines: &Vec<&Box<dyn GwInstruction>>) -> i16{
    let mut curr_line = line + 1;
    let mut while_end_balance = 0;
    loop {
        if curr_line >= real_lines.len() as i16 {
            break;
        } else if let Some(ref instr) = real_lines.get(curr_line as usize) {

            if instr.is_while() {
                while_end_balance += 1;
            }
            if instr.is_wend() {
                if while_end_balance  == 0 {
                    return curr_line as i16;
                } else {
                    while_end_balance -= 1;
                }
            }
        }
        curr_line += 1;
    }
    return -1;
}

Notice that we solve the problem of nested WHILE/WEND blocks by keeping a counter while_end_balance.

With this utility we can create the implementation of the WHILE statement with the following code:

impl GwInstruction for GwWhile {
    fn eval (&self, line: i16, context : &mut EvaluationContext) -> InstructionResult {
        let mut wend_line : i16 = 0;

        // Find the cached corresponding line for this WHILE statement
        if let Some(corresponding_wend) =  context.pair_instruction_table.get(&line) {      
            wend_line = *corresponding_wend;
        } else if let Some(ref real_lines) = context.real_lines {
            // Try to look for the WEND statement in the program lines
            let index_of_wend = find_wend(line, real_lines);
            if index_of_wend == -1 {
                return InstructionResult::EvaluateToError(String::from("WHILE WITHOUT WEND"));
            } else {
                context.pair_instruction_table.insert(line, index_of_wend);
                context.pair_instruction_table.insert(index_of_wend, line);
            }       
            wend_line = index_of_wend;
        }

        // Evaluate the condition and move the following line
        let condition_evaluation = self.condition.eval(context);
        match condition_evaluation {
            ExpressionEvalResult::IntegerResult(result) if result == 0 => {
                InstructionResult::EvaluateLine(wend_line + 1)
            }
            ExpressionEvalResult::IntegerResult(_) => {
                InstructionResult::EvaluateNext
            }       
            _ => {
                InstructionResult::EvaluateToError(String::from("Type mismatch"))
            }
        }
    }

1.3 Additional problems

While working in this implementation I found an additional problem. In BASIC you can have several statements in one line separated by colons (:) . For example you can have a complete WHILE block in just one line:

10 X = 1 : WHILE X < 10 : PRINT X : X = X + 1 :WEND

Or you can have a WHILE in one line and the WEND inside another line:

10  x = 1
20 WHILE x <> 5
30 print x
40 x = x + 1 : print "a" : WEND
50 print "END"

To support his scenario the program is "flattened" before executing it. For example, the previous snippet becomes is converted to:

0  x = 1
1 WHILE x <> 5
2 print x
3 x = x + 1 
4 print "a" 
5 WEND
6 print "END"

This way it is easy to implement a jump between instructions that didn't exist in as explicit lines in the original program. This transformation is performed before running the program:

...
   let real_lines = &mut context.real_lines.as_mut().expect("instr vector");
   for e in self.lines.iter() {
      real_lines.push(&e.instruction);
      if let Some(ref rest) = e.rest_instructions {
         for nested in rest {
            real_lines.push(&nested);
         }
      }	    
   }
...

Something that needs to be improved is the way to identify existing WHILE and WEND instructions. Sadly, right now this is implemented using a pair of methods is_while and is_wend. These methods are defined in the GwInstruction trait and overriden on GwWhile and GwWend. This is ugly since these methods are very specific to this problem. It doesn't seem right to have them in GwInstruction.

One alternative to solve this problem is to redesign the code representation to include a way to retrieve the original instruction from a GwInstruction. This is one of the things that will be implemented next.

Code for the interpreter is here: https://github.com/ldfallas/rgwbasic .

Saturday, April 16, 2022

Executing code from a buffer with Rust on Windows

Creating and executing code at runtime is an intriguing topic. It is one of the pieces that makes it possible to write JIT compilers for things like Java or C#.

Creating a byte array with executable instructions and “casting” that array to a function pointer is not enough . For security reasons, modern operating systems require you to specify which region of memory of your program is executable. On Windows the VirtualAlloc and VirtualProtect functions are used to do this.

There is a nice StackOverflow answer: https://stackoverflow.com/questions/40936534/how-to-alloc-a-executable-memory-buffer by user Christian Hackl on how to use these API functions. In this post I’m going to try to replicate the C++ example from the SO post in Rust .

The first is to be able to call VirtualAlloc and VirtualProtect from Rust. There are several ways to call “C” style functions in Rust. However to call these Win32 API functions I am going to use Rust for Windows. This package provides an easy way to call into Win32 API .

First we start by adding the the windows crate to our dependencies. And we also specify that we need a couple of features:

//Cargo.toml
...
[dependencies.windows]
version="0.35.0"
features = [
    "alloc",
    "Win32_Foundation",
    "Win32_System_Memory",
]

Here, the most important feature is “Win32_System_Memory” which allows us to call VirtualAlloc and VirtualProtect. You can see that in the "Required features" section of the documentation entry here https://microsoft.github.io/windows-docs-rs/doc/windows/Win32/System/Memory/fn.VirtualAlloc.html

Now that we have this functions we can rewrite the example from the StackOverflow question:

use windows::{
    core::*,
    Win32::Foundation::*,
    Win32::System::Memory::*,
};

fn main() -> Result<()> {
    unsafe {
        let buffer = VirtualAlloc(
            std::ptr::null(),
            4096,
            MEM_COMMIT | MEM_RESERVE,
            PAGE_READWRITE,
        );
        let buff_arr = std::mem::transmute::<*mut ::core::ffi::c_void, &mut [u8; 6]>(buffer);
        buff_arr[0] = 0xb8; // MOV opcode
        buff_arr[1] = 0x05; // '5' value
        buff_arr[2] = 0x00;
        buff_arr[3] = 0x00;
        buff_arr[4] = 0x00;
        buff_arr[5] = 0xc3; // RET
        let mut dummy: [PAGE_PROTECTION_FLAGS; 1] = [PAGE_PROTECTION_FLAGS::default()];
        let vpResult = VirtualProtect(buffer, 6, PAGE_EXECUTE_READ, dummy.as_mut_ptr());
        if !vpResult.as_bool() {
            GetLastError().to_hresult().ok()?;
        }
        let new_function = std::mem::transmute::<*mut ::core::ffi::c_void, fn() -> i32>(buffer);
        let result = new_function();
        println!("The result is {}", result);
        VirtualFree(buffer, 0, MEM_RELEASE);
    }
    Ok(())
}

After compiling and running this example we can see:

The result is 5

I was very happy the first time I saw that running!. Here the buff_array buffer has real x86 instructions equivalent to something like:

mov eax, 0x5
ret

Encoding this instructions is a very complex process. The documentation contains dense tables explaining the format for example for MOV or RET.

Also it is clear that we need unsafe Rust here since we are dealing with low level code.

The process of encoding the instructions is very complex. We can take a shortcut using the iced-x86 crate. This really cool library has a complete x86 assembler and dissembler. It was very easy (with my limited Rust knowledge) to adapt it to this little example.

For we include it in the Cargo.toml file:

[dependencies.iced-x86]
version = "1.17.0"
features = ["code_asm"]

Now we can create the code using the nice API that iced-x86 provides. Here I’m adding a call to a function defined in the same program.

fn print_hello() -> u32 {
    println!("Hello!!!");
    1
}

fn encode_small_program() -> ::core::result::Result<Vec<u8>, asm::IcedError> {
    let mut assembler = asm::CodeAssembler::new(64)?;
    unsafe {
        let print_hello_addr = std::mem::transmute::<fn() -> u32, u64>(print_hello);
        assembler.sub(asm::rsp, 0x28)?;
        assembler.mov(asm::rax, print_hello_addr)?;
        assembler.call(asm::rax)?;
        assembler.mov(asm::eax, 0x7)?;
        assembler.add(asm::rsp, 0x28)?;
        assembler.ret()?;
    }

    let instr = assembler.take_instructions();
    let block = InstructionBlock::new(&instr, 0);
    let res = BlockEncoder::encode(64, block, BlockEncoderOptions::NONE)?;
    Ok(res.code_buffer)
}

We can modify the make program to use this new function:

    let encoded_program = encode_small_program().unwrap();
    let p = encoded_program.as_ptr();

    unsafe {
        let buffer = VirtualAlloc(
            std::ptr::null(),
            4096,
            MEM_COMMIT | MEM_RESERVE,
            PAGE_READWRITE,
        );
        let buff_arr = std::mem::transmute::<*mut ::core::ffi::c_void, *mut u8>(buffer);

        std::ptr::copy_nonoverlapping(p, buff_arr, encoded_program.len());

        let mut dummy: [PAGE_PROTECTION_FLAGS; 1] = [PAGE_PROTECTION_FLAGS::default()];
        let vpResult = VirtualProtect(buffer, 6, PAGE_EXECUTE_READ, dummy.as_mut_ptr());
        if !vpResult.as_bool() {
            GetLastError().to_hresult().ok()?;
        }
        let new_function = std::mem::transmute::<*mut ::core::ffi::c_void, fn() -> i32>(buffer);
        let result = new_function();
        println!("The result is {}", result);
        VirtualFree(buffer, 0, MEM_RELEASE);
    }

Running this program now shows:

Hello!!!
The result is 7

This experiment bring intriguing possibilities for future posts!.

Friday, April 15, 2022

Exploring a Webpack stats file with Prolog

A couple of days ago I was reading about the Webpack statistics file created using the following command line options:

npx webpack --profile --json

This file contains a lot of information collected by Webpack about the project being processed. The information in this file is used by nice visualization tools like Webpack Bundle Analyzer.

The dependency graph is included in this file. That is, all the dependencies between modules of the project. Being able to perform queries on this data could be useful to get insights into the code.

There are many tools to process JSON, but I wanted to try to use SWI-Prolog to see if I can get information from this file.

The information I am looking for is the module dependency information. By taking a look at the Module Object we can get this information using the reasons property.

We can start by parsing the stats.json file using SWI-Prolog builtin library for reading JSON:


:- use_module(library(http/json)).

read_json_file(FileName, Terms) :-
    open(FileName, read, Stream),
    json_read(Stream, Terms),
    close(Stream).

For convenience, I'm adding the loaded file to the Prolog database using assert/1:


?- read_json_file('c:\\smallexample\\stats.json',F), assert(testfile(F)).
F = json([hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json(...), ... = ...|...]).

Now that we can load the stats file we can start by performing simple queries. For example we can start by looking at top-level properties:


?- testfile(json(Contents)), member(Name=_,Contents).
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = hash ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = version ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = time ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = builtAt ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = publicPath ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
...

Here notice, that I'm using member/2 to get the name of the properties in the main file.

By the way, as a side note, yesterday I learned that you can exclude variables from Prolog results using the following (Stack overflow question here) goal:


set_prolog_flag(toplevel_print_anon, false).

With this nice tip, we can exclude variables that start with underscore from the results:


?- testfile(json(_Contents)), member(Name=_, _Contents).
Name = hash ;
Name = version ;
Name = time ;
Name = builtAt ;
Name = publicPath ;
Name = outputPath ;
Name = assetsByChunkName ;
Name = assets ;
Name = chunks ;
Name = modules ;
Name = entrypoints ;
Name = namedChunkGroups ;
Name = errors ;
Name = errorsCount ;
Name = warnings ;
Name = warningsCount ;
Name = children.

Now I can access the modules section to extract the reasons property. This property has information on modules that depend on the current module. For example say that we have a small TypeScript program that have the following structure:

 



We can start the exploration of this project by looking at the contents of the modules objects.


?- testfile(json(_Contents)),
|    member( ('modules'=_Modules), _Contents),
|    member( json(_ModulePropsList), _Modules),
|    member( ('name'=ModuleName), _ModulePropsList).
ModuleName = './src/index.ts' ;
ModuleName = './src/parser.ts' ;
ModuleName = './src/FuncApply.ts' ;
ModuleName = './src/NumLiteral.ts' ;
ModuleName = './src/SymbolObj.ts' ;
ModuleName = './src/BaseObject.ts' ;
ModuleName = 'webpack/runtime/define property getters' ;
ModuleName = 'webpack/runtime/hasOwnProperty shorthand' ;
ModuleName = 'webpack/runtime/make namespace object' ;

We can create a new goal with the code above which we can use later:


module_name(json(ContentsList), Name) :-
    member(('modules'=Modules), ContentsList),
    member(json(ModulePropertiesList), Modules),
    member('name'=Name, ModulePropertiesList).


module_properties_by_name(json(ContentsList), Name, ModulePropertiesList) :-
    member(('modules'=Modules), ContentsList),
    member(json(ModulePropertiesList), Modules),
    member('name'=Name, ModulePropertiesList).

Now that we located the modules, we can get the contents of the reasons property.


?- testfile(_Json),
|    module_properties_by_name(_Json, './src/BaseObject.ts', _Props),
|    member((reasons=_Reasons), _Props),
|    member(json([_|[RefModName|_]]), _Reasons).
RefModName =  (module='./src/FuncApply.ts') ;
RefModName =  (module='./src/FuncApply.ts') ;
RefModName =  (module='./src/NumLiteral.ts') ;
RefModName =  (module='./src/NumLiteral.ts') ;
RefModName =  (module='./src/SymbolObj.ts') ;
RefModName =  (module='./src/SymbolObj.ts') ;
false.

(Repeated results seem to indicate different "reasons")

With this data we can generate Graphviz representation (for example the one used in the graph above).


name_modules([], [], _).
name_modules([ModName|Rest], [ModNamePair|RestResult], Counter) :-
    number_string(Counter, CounterStr),
    string_concat('M', CounterStr, ModuleId),
    ModNamePair = ModName - ModuleId,
    NewCounter is Counter + 1,
    name_modules(Rest, RestResult, NewCounter).

module_dependencies_by_reason(File, (Name-Referencer)) :-
    module_name(File, Name),
    module_properties_by_name(File, Name,Props),
    member((reasons=R), Props),
    member(json([_|[(module=Referencer)|_]]),R).

generate_node_descriptions([],Result, Result).
generate_node_descriptions([(Name-Id)|Rest],TmpResult, OutStr) :-
    format(atom(Tmp3), '~a[label="~a"];\n', [Id, Name]),
    string_concat(TmpResult, Tmp3, OutStrTmp),
    generate_node_descriptions(Rest, OutStrTmp, OutStr).

generate_node_relations([], _, Result, Result).
generate_node_relations([(Target-Src)|Rest], NodeIds, TmpResult, Result) :-
    get_assoc(Src, NodeIds , SrcCode),
    get_assoc(Target, NodeIds , TargetCode),
    format(atom(RelationStr), '~a -> ~a;\n', [SrcCode, TargetCode]),
    string_concat(TmpResult, RelationStr, NewTmpResult),
    generate_node_relations(Rest, NodeIds, NewTmpResult, Result), !.
generate_node_relations([_|Rest], NodeIds, TmpResult, Result) :-
    generate_node_relations(Rest, NodeIds, TmpResult, Result),!.


dot_file_from_reasons(File, DotFileStr) :-
    findall(Name, module_name(File, Name), NameList),
    name_modules(NameList, CodedList, 0),
    list_to_assoc(CodedList, AssocNameModList),!,
    setof(Pairs, module_dependencies_by_reason(File, Pairs), PairList),
    generate_node_descriptions(CodedList, 'digraph G {\n', DotFileStrTmp1),
    generate_node_relations(PairList, AssocNameModList, DotFileStrTmp1, DotFileStrTmp2),
    string_concat(DotFileStrTmp2, '}', DotFileStr).

I am impressed by the power of Prolog. I have always admired the way it works differently dependending on how you use it. For example the way member/2 was used above to extract internal elements from terms. One would assume that this predicate is only used to test list membership. However by the power of Prolog unification and backtracking we can used to explore the contents of a list.