# Devlog 1: The Assembler - Building a Self-Hosting Web Assembly Toolchain from Scratch

# Introduction

Have you ever thought of how programming languages came to be? I thought that too before starting this project. I wanted to replicate the journey from binary and opcodes → Low Level Assembly → Higher Level C-Type language. This project directly replicates this. Follow along my journey and you might learn a few things with me along the way! I decided to not overcomplicate this project and chose Web Assembly in favor of x86 assembly because it is easier to use and more portable across systems (also every time I've tried to use assembly on my windows machine, I've had a stroke it's so hard).

This is part 1, just focusing on the Assembler. You can view the project on GitHub [JBrosDevelopment/WebAsmCompiler](https://github.com/JBrosDevelopment/WebAsmCompiler) and keep up with its progress. Any contributions are welcome!

**A list of all the binary opcodes used in the WAL Assembler** [**WEB ASSEMBLY OPCODES**](https://github.com/JBrosDevelopment/WebAsmCompiler/blob/main/OpCodes.md)

# Setting Up WebAsm

## First Program

First thing I did was set up a JavaScript file that would load a `wasm` file and run it. I also had to create a function to create the file and fill it with the binary data. With the help of ChatGPT to guide me, I was able to make a simple program that would run and I used Node JS for fast console output.

I created a program that would add two numbers and print the result. I used the `print_i32` function from the `env` module to print the result. The program is very simple, but it was a good starting point for me to learn how to create a web assembly binary file.

Here is the Binary that I used to create the `program.wasm` file.

```js
// HEADER
0x00, 0x61, 0x73, 0x6D, // magic number
0x01, 0x00, 0x00, 0x00, // version

// TYPE
0x01, 0x08,  // 01 = Type Section, 08= length of section in `8` bytes
0x02, // There are 2 function types

0x60, 0x01, 0x7F, 0x00, // 60=function type, 01=1 parameter, 7F=i32, 00=0 return values
0x60, 0x00, 0x00, // 60=function type, 00=0 parameters, 00=0 return values

// IMPORT
0x02, 0x11, // 02 = Import Section, 11= length of section in `17` bytes
0x01, // 01 = 1 import
0x03, 0x65, 0x6E, 0x76, // 03 = length of module name, "env"; rest = "env"
0x09, 0x70, 0x72, 0x69, 0x6E, 0x74, 0x5F, 0x69, 0x33, 0x32, // 09= length of function name, 
0x00, 0x00, // 00 = import kind (function), 00 = type index (0)

// FUNCTION
0x03, 0x02, // 03 = Function Section, 02= length of section in `2` bytes
0x01, // 01 = 1 function
0x01, // 01 = type index (1)

// EXPORT
0x07, 0x08, // 07 = Export Section, 08= length of section in `8` bytes
0x01, // 01 = 1 export
0x04, 0x6D, 0x61, 0x69, 0x6E, // 04 = length of export name, "main"; rest = "main"
0x00, 0x01, // 00 = export kind (function), 01 = function index (1)

// CODE SECTION
0x0A, 0x0B, // 0A = Code Section, 0B= length of section in `11` bytes
0x01, // 01 = number of function bodies
0x09, // 09 = size of function body in `9` bytes
0x00, // 00 = local variable count (0)
0x41, 0x06, // 41 = i32.const, 06 = value 6
0x41, 0x07, // 41 = i32.const, 07 = value 7
0x6A, // 6A = i32.add
0x10, 0x00, // 10 = call, 00 = function index (print_i32)
0x0B // 0B = end
```

And it sure enough outputted:

```plaintext
13
```

The pseudo-code for the program is as follows:

```js
import from "env" function print_i32(i32) -> void

function main() -> void {
    print_i32(add(6, 7))
}
```

## Insert Data into Program

Okay we're going to try to affect the output with some input from the JavaScript file. I will create a file named, `input.wal` (WASM Assembly Language), then I will read this file in JavaScript and convert it into binary and feed it into the wasm program. I will do this by exporting a memory page inside the `program.wasm` file.

To do this, I added a memory output to the wasm `program.wasm` file.

```js
// MEMORY
0x05, 0x03, // 05 = Memory Section, 03= length of section in `3` bytes
0x01, // 01 = 1 page of memory (65,536 bytes)
0x00, 0x01, // 00 = limit flags (0 = no max), 01 = minumum size (1)

// ... later in the program.wasm file:

// export "memory"
0x06, 0x6D, 0x65, 0x6D, 0x6F, 0x72, 0x79, // 06 = length of export name, "memory"; rest = "memory"
0x02, 0x00, // 02 = export kind (memory), 00 = memory index (0)
```

I also wanted to pass `byteLength` as a parameter into the main function. I needed to update the Type section in the `program.wasm` file.

```js
// main(i32) -> void
0x60, 0x01, 0x7F, 0x00, // 60=function type, 00=1 parameters, 7F=i32, 00=0 return values
```

And then after I added it as an export to the JavaScript part so that I could access it.

```js
const memory = instance.exports.memory;
const bytes = new Uint8Array(memory.buffer);
const byteLength = 3;
// test bytes
bytes[0] = 10;
bytes[1] = 20;
bytes[2] = 30;

// Start the program and pass the byteLength parameter into the function
instance.exports.main(byteLength);
```

To access the memory, I used `i32.load8_u` (`0x2D`) to load a single byte from memory. Then I made a loop using `loop` (`0x03`). After a bit of time figuring out how that all works and counting the amount of bytes in the program again and again, I ended with the opcode version using 39 bytes for the new main function with a working loop:

```js
// This is the pseudo code version of the opcode for the updated main function taking a total of 39 bytes
function main(byteLength: i32) -> void {
    var index: i32 = 0
    var sum: i32 = 0
    block loop:
        sum = (memory[index] as i32) + sum
        print_i32(memory[index])
        index = index + 1
        if index < byteLength {
            goto loop
        }
    end
    print_i32(sum)
}
```

The above code is coded really weird with the `block` and the `goto` statement, but that is closest way of writing this code in a more readable format. The way Web Assembly works, there is no exact loop that then loops back to the beginning. it does use an opcode named loop, but it is more of a block than a loop. It also has a branch `br` (`0x0C`) and a conditional branch `br_if` (`0x0D`), and these will return to a depth defined, or can also break if you return to a surrounding block. But also, if the code reaches the `end` of the loop, it breaks instead of looping back. It's interesting the way it works but once you understand it makes sense.

# Assembler

## First Step, Replacing Characters

So, for the assembler, we're going to start with replacing characters from the input and then converting that into the opcode. Say `add` has the shorthand of `a` and `i32.const` has the shorthand of `i`. If the character is not in the list, it will just ignore it. This way we can start making the assembler and then later have this a little bit more usable assembler and integrate on top of it.

Here is the pseudo code version of the opcode binary in the `program.wasm`

```js
import from "env" function print_i32(i32) -> void
import from "env" function write_char(i32) -> void

function main() -> void {
    var bytes: i32 = 0
    var char: i32 = 0
    var lastWasEOF: i32 = 0

    block loop:
        char = memory[bytes]
        bytes = bytes + 1

        // commonly used opcodes
        if char == 97 { // unicode for `a`
            char = 0x6A // opcode for `add`
        } if char == 105 { // unicode for `i`
            char = 0x41 // opcode for `i32.const`
        } if char == 99 { // unicode for `c`
            char = 0x10 // opcode for `call`
        } if char == 103 { // unicode for `g`
            char = 0x20 // opcode for `i32.get`
        } if char == 115 { // unicode for `s`
            char = 0x21 // opcode for `i32.set`
        } if char == 108 { // unicode for `l`
            char = 0x2D // opcode for `i32.load8_u`
        }

        if lastWasEOF == 1 && char == ENDOFFILEBYTE {
            break // technically branches out of depth
        }
        
        lastWasEOF = if char == ENDOFFILEBYTE {
            1
        } else {
            0
        }

        write_char(char)

        goto loop
    end
    
    print_i32(bytes)
}
```

This ended up working and made the project promising! Here is an example that adds `6 + 7`: `i 6 i 7 a`. Again, this is promising for the future of this project and getting Web Assembly to run from straight opcodes, but this is really just a proof of concept. The next step of this assembler scraps this test that we just made.

## Second Step, Input is Text and Output is bytes

Okay so the next step is to make the Input a text file and the output bytes. Right now, it has no idea when a byte is an instruction and when a byte is a number or such. Unfortunately, we cannot use the program from the first step to work on this, because any number input will just be the byte value and not the ASCI code for the number. For example, `6` would be `0x06` but in ASCII that is not the number 6, which is `0x36` in ASCII.

Here is a pseudo code representation of the new program we're trying to make. Again, this program will be made with opcodes and not in JavaScript. I did make a helper function in JavaScript to make this easier. So instead of it looking like a large list of bytes, it's now a large list of `cmd('<CMD NAME>')` where `CMD_NAME` is any valid opcode. This makes the list look more like a readable program.

```js
import from "env" function print_i32(i32) -> void
import from "env" function write_char(i32) -> void

function main() -> void {
    var bytes: i32 = 0
    var char: i32 = 0
    var cmd: i32 = 0
    var number: i32 = 0
    var startWord: i32 = 0
    var wordLength: i32 = 0
    var stateCMD: i32 = 1 // 0=not command byte, 1=next byte is command, 2=byte is command

    block loop:
        char = memory[bytes]
        bytes = bytes + 1

        if char == ENDOFFILEBYTE {
            break
        }

        if char == '\n' as i32 {
            stateCMD = 1 // next byte is command
            startWord = bytes + 1
        }

        else if char == ' ' as i32 || char == '\t' as i32 || char == ';' as i32 {
            if stateCMD == 2 { // End Of Command
                stateCMD = 0
                cmd = WordToCMD(startWord, wordLength)

                if cmd == 0xFB { // check for error
                    print_i32(0xFB)
                    return
                }
                
                write_char(cmd)
            }
            else if stateCMD == 0 { // End Of Argument
                number = WordToI32(startWord, wordLength)

                if number == 0xFC { // check for error
                    print_i32(0xFC)
                    return
                }

                writeULEB128(number)
            }
            startWord = bytes + 1 // next byte is start of word
            wordLength = 0
            goto loop
        }

        // if valid char
        else if (char >= 'a' && char <= 'z') || (char >= 'A' && char <= 'Z') || (char >= '0' && char <= '9') || char == '_' {
            if stateCMD == 1 {
                stateCMD = 2
            }
            wordLength = wordLength + 1
        } else {
            print_i32(0xFD) // error code invalid char
            return
        }

        goto loop
    end

    // END OF FILE SEQUENCE
    write_char(0xFE)
    
    print_i32(bytes)
}

function WordToCMD(startWord: i32, wordLength: i32) -> i32 {
    if wordLength == 3 && memory[startWord] == 'a' && memory[startWord + 1] == 'd' && memory[startWord + 2] == 'd' {
        return 0x6A // opcode for `i32.add`
    }
    if wordLength == 3 && memory[startWord] == 'm' && memory[startWord + 1] == 'u' && memory[startWord + 2] == 'l' {
        return 0x6C // opcode for `i32.mul`
    }
    if wordLength == 3 && memory[startWord] == 's' && memory[startWord + 1] == 'u' && memory[startWord + 2] == 'b' {
        return 0x6B // opcode for `i32.sub`
    }
    if wordLength == 3 && memory[startWord] == 'a' && memory[startWord + 1] == 'n' && memory[startWord + 2] == 'd' {
        return 0x71 // opcode for `i32.and`
    }
    // check for the rest of opcodes...
}

function WordToI32(startWord: i32, wordLength) -> i32 {
    var char: i32 = 0
    var digit: i32 = 0
    var product: i32 = 0
    var index: i32 = 0
    loop: // no block because no need to break out, instead code reaches 'end' and breaks
        char = memory[startWord + index]

        if char < '0' as i32 || char > '9' {
            return 0xFC
        }

        digit = char - 48
        product = product * 10 + digit

        index = index + 1
        if index < wordLength {
            goto loop
        } // else, reaches 'end' and breaks
    end

    return product
}

function IntoULEB128(number: i32) -> i32 {
    var byte: i32 = number & 0x7F

    if number >= 128 {
        byte = byte | 0x80
    }

    return byte
}

function WriteULEB128(number: i32) -> void {
    var byte: i32 = 0

    loop: // no block because no need to break out, instead code reaches 'end' and breaks
        byte = IntoULEB128(number)
        write_char(byte)

        number = number >> 7

        if number > 0 {
            goto loop
        } // else, reaches 'end' and breaks
    end
}

/*
example input code:
const 1
load 0 0
const 3
add
call 0 
*/
```

Surprisingly, after a lot of work, it worked! This is not the end goal though. This assembler is extremely limited, and only really works with the CODE section of the Web Assembly binary. Even though I worked so hard to get this one to work, I'm going to scrap it for now and start going over what I want the assembly language to look like.

The rest of the assembler's code is built off of the pseudo-code above.

## Third Step, Define the Assembly Language

The assembly language needs to have the following goals:

- [x] Be extremely simple to map to binary
- [x] Assemble all Web Assembly sections, not just the CODE section
  - This includes importing and exporting functions, defining memory, and defining functions
- [x] Be able to look at the assembly language and understand what the program is doing. This is especially true with the other Sections, when defining functions or memory
- [x] Be relatively easy to program the assembler in the wasm binary
- [x] Does not need to have complete mapping of WebAsm opcodes, just enough to be able to write a simple program

Some of these goals are simple enough; others are more complex.

### Encoding Bytes

Right now, we want to be able to encode number and bytes in a bunch of different ways for simplicity. We'll use prefixes to define how the number or byte is encoded.

Below is a list of the supported prefixes and encoding types made for this project as of the writing of this article. Only the first 4 were added in the first version of this assembler.

- `hex` - Hexadecimal, 2 hexadecimal digits per byte, e.g. `hex FF` = 255
- `bin` - Binary, 8 binary digits per byte, e.g. `bin 11111111` = 255
- `uleb` - Unsigned LEB128, e.g. `uleb 255` = 255
- `str` - String, e.g. `str Hello` = \[72 101 108 108 111\](tel:72 101 108 108 111)
  - Remember usually the length of strings is required before the string, so use `uleb 3 str abc` to encode the string "abc" with the length of 3 before it.
- `ascii` [*\[Added in assembler.0.4\]*](#assembler04-adding-ascii-keyword) - Encodes a single ASCII character as a positive signed LEB128 value for instructions: `ascii a` = `97` but the bytes are `0xE1 0x00`.
  - ASCII values below 64 use one byte; values from 64 through 127 require two bytes to preserve the positive sign.
  - `str` writes raw bytes. For example, `str a` emits `0x61`, which `i32.const` interprets as `-31` because its immediate uses signed LEB128.
  - Use `ascii` for character constants and `str` for raw string data, such as import and export names.
- `sleb` [*\[Added in assembler.0.5\]*](#assembler05-adding-sleb-keyword-adding-the-data-section-and-optimizing-assembler) - Encodes in Signed LEB128, e.g. `sleb -50`
  - This is useful for the CODE section especially with `i32.const` which expects its immediate to be in SLEB 128 format.
- `float32` [*\[Added in assembler.0.7\]*](#assembler07-encoding-floating-points-numbers) - Encodes 4 byte floating point numbers: `float32 1.5` = `00 00 C0 3F`
  - This data type is only useful for operands that expect floating point numbers like `f32.const`
- `float64` [*\[Added in assembler.0.7\]*](#assembler07-encoding-floating-points-numbers) - Encodes 8 byte floating point numbers: `float 1.5` = `00 00 00 00 00 00 F8 3F`
  - This data type is only useful for operands that expect floating point numbers like `f64.const`

### Comments

I think comments would be a nice touch and not hard to add so the `;` will start a comment and will continue until the end of the line. The assembler will ignore everything after the `;` on that line.

### Assembler Variables

The `$` will be used to access a variable that can be used later in the program. The `#` will be used to define it. The variable will be replaced with the value of the variable when the assembler sees it. The value is required to be in integer format. The following is an example of how to define and use a variable:

```plaintext
; define
#<variable_name> <value>
; access
$<variable_name>
```

This can be anywhere in a line, for example `FUNCTION uleb 1 i32 #main_type 0` is valid and will replace `$main_type` with `0` when the assembler sees it in the future. In this line, `const $main_type` is the same as `const 0`.

### Defining Sections

To define a section, we will use the following syntax:

```plaintext
SECTION <section_name> 
; contents
SECTION_END
```

This will allow the assembler to start counting bytes when it sees the `SECTION` keyword, and stop counting when it sees the `SECTION_END` keyword. The section name will be a predefined that will convert to the binary section name. The following are the section names that will be used:

- `SECTION_HEADER` - Header Section -> Converts to `0x00, 0x61, 0x73, 0x6D, 0x01, 0x00, 0x00, 0x00`
- `SECTION_TYPE` - Type Section -> Converts to `0x01`
- `SECTION_IMPORT` - Import Section -> Converts to `0x02`
- `SECTION_FUNCTION` - Function Section -> Converts to `0x03`
- `SECTION_MEMORY` - Memory Section -> Converts to `0x05`
- `SECTION_EXPORT` - Export Section -> Converts to `0x07`
- `SECTION_CODE` - Code Section -> Converts to `0x0A`
- `SECTION_DATA` *\[Added in assembler.0.5\]* - Data Section -> Converts to `0x0B`
- `SECTION_CUSTOM` \[Added in assembler.1.1\] - Custom Section -> Converts to `0x00`

More might come later but these are the main sections we'll use for now.

### TYPE Section

The Type Section will translate directly into bytes, but it will be easier to read and write than just straight bytes because terms like `FUNCTION` -> `0x60` and `i32` -> `0x7F` will be used. The following is an example of how to define a function type in the TYPE section:

```plaintext
SECTION SECTION_TYPE
FUNCTION uleb 3 i32 i32 i32 uleb 1 i32 #three_in_1_out 0
FUNCTION uleb 1 i32 uleb 0 #print_i32_type 1
SECTION_END
```

The `uleb 3 i32 i32 i32` are the parameters of the function, and the `i32` is the return type of the function.

The `$three_in_1_out` and `$print_i32_type` are the labels that can be used to reference this type later. If `$three_in_1_out` is used later in the program, it will be replaced with the index -> `0` because it's the first type defined.

### IMPORT Section

The Import sections will also directly translate into bytes. These use strings so the `str` encoding will be used for the module and function names. The following is an example of how to define an import in the IMPORT section:

```plaintext
SECTION SECTION_IMPORT
uleb 3 str env uleb 9 str print_i32 FUNCTION_KIND $print_i32_type
SECTION_END
```

`FUNCTION_KIND` is a predefined that will convert to `0x00` for the import kind. The `$print_i32_type` is the label that was defined in the TYPE section, and it will be replaced with the index of the type when the assembler sees it.

### FUNCTION Section

The Function section is pretty simple, it just defines the functions that will be used in the CODE section.

```plaintext
SECTION SECTION_FUNCTION
#main 0 $main_type
#other_func 1 $three_in_1_out
SECTION_END
```

The `#main` and `#other_func` are labels defined in the TYPE_SECTION and they translate to the index of the type that corresponds to the function. The `$main_type` and `$three_in_1_out` are the labels that were defined in the TYPE section, and they will be replaced with the index of the type when the assembler sees them.

### MEMORY Section

The memory section won't be used much in the beginning, so for now I will just keep it simple and it translates directly into bytes. The following is an example of how to define a memory in the MEMORY section:

```plaintext
SECTION SECTION_MEMORY
; 1 page of memory, no max, min size 1 page. Define variable for memory index 0
uleb 1 uleb 0 uleb 1 #memory 0
SECTION_END
```

### EXPORT Section

The export section is also pretty simple, it just defines the functions that will be exported from the program. The following is an example of how to define an export in the EXPORT section:

```plaintext
SECTION SECTION_EXPORT
uleb 2 
uleb 4 str main FUNCTION_KIND $main
uleb 6 str memory MEMORY_KIND $memory
SECTION_END
```

### CODE Section

The CODE section is where the main program code will be defined. This is where the bulk of the assembly language will be used. Every opcode that will be supported will have a defined keyword that will translate to the opcode. `FUNCTION_START` and `FUNCTION_END` will be used to track how many bytes are in the function declaration.. The following is an example of how to define a function in the CODE section:

```plaintext
SECTION SECTION_CODE
uleb 2

FUNCTION_START ; main function
    uleb 0 ; declaration group
    i32.const uleb 6
    i32.const uleb 7
    i32.add
    call $print_i32
    end
FUNCTION_END

FUNCTION_START ; other_func function
    uleb 1 ; declaration group
    uleb 3 i32 #x 0 #y 1 #z 2 ; local variables
    
    block NO_RETURN @block1
        loop NO_RETURN @loop1
            local.get $x
            local.get $y
            i32.mul
            local.get $z
            i32.mul
            local.set $x
            
            local.get $x
            i32.const uleb 500
            i32.lt_s
            br_if ^block1
        end
    end
    local.get $x
    return
    end
FUNCTION_END

SECTION_END
```

You can view the opcodes for the above code in the [Opcodes.md](https://github.com/JBrosDevelopment/WebAsmCompiler/blob/main/OpCodes.md) file.

The `@` and the `^` are used to define and reference labels for the `block`, `loop`, and `br_if` opcodes. The `@block1` and `@loop1` are labels that can be used to reference the block and loop, and the `^block1` is used to reference the block when using the `br_if` opcode. This is to make it easier to use branches in the language instead of counting the depth.

### DATA Section [*\[Added in Assembler.0.5\]*](#assembler05-adding-sleb-keyword-adding-the-data-section-and-optimizing-assembler)

This section was added in assembler.0.5 update. In this section you can define values to be stored in memory during initialization before the code gets executed. This is useful especially for strings.

```plaintext
SECTION SECTION_DATA
	<count>

	<0 = active, 1 = passive>
	<destination address defined through `i32.const` and `end`>
	<bytes length>
	<data raw bytes>
	
    ; example
    uleb 0
	i32.const $destination end
	uleb 12
	str Hello hex 20 str World!

SECTION_END
```

### CUSTOM Section [*\[Added in Assembler.1.1\]*](#assembler11-define-directives)

This section will be assembled into the binary but is ignored by the Web Assembly core execution process. This means any data in this section will not affect the output of the wasm file but can be used to store symbols or specific data for tools to read.

```plaintext
SECTION SECTION_CUSTOM
    uleb 8 str compiler ; Custom section name: "compiler"
    uleb 17 str WebAsmCompiler1.2
SECTION_END
```

### NOTE

> The extent of the assembler has increased since this documentation was written. All of the specs above are valid ways to write code in WAL but better ways were created, especially with the `define_<type>` keywords.

### Python Assembler Equivalent

Before I try to implement this in Web Assembly, I want to write the assembler in python. The finished version is [PythonTesting/Assembler.py](https://github.com/JBrosDevelopment/WebAsmCompiler/blob/main/PythonTesting/Assembler.py). What is discouraging is that the final assembler is **880 lines** of python code. This will be a LOT of Web Assembly code when I get to converting it.

Here is an example of the python assembler working:

```shell
PS D:\WebAsmCompiler> python .\PythonTesting\Assembler.py
/* ... output ... */ 
PS D:\WebAsmCompiler> node .\PythonTesting\bin\run_program_wasm.js
42
```

The output is `42` because the finished program is a simple program that doubles a number `21` and prints it to the console. It can be seen below:

```plaintext
SECTION_HEADER

SECTION SECTION_TYPE
uleb 3 ; type count
FUNCTION uleb 1 i32 uleb 0 #print_i32_type 0
FUNCTION uleb 0 uleb 0 #main_type 1
FUNCTION uleb 1 i32 uleb 1 i32 #double_type 2
SECTION_END

SECTION SECTION_IMPORT
uleb 1 ; import count
uleb 3 str env uleb 9 str print_i32 FUNCTION_KIND $print_i32_type
SECTION_END

SECTION SECTION_FUNCTION
uleb 2 ; function count
#main 1 $main_type
#double 2 $double_type
SECTION_END

SECTION SECTION_EXPORT
uleb 1 ; export count
uleb 4 str main FUNCTION_KIND $main
SECTION_END

SECTION SECTION_CODE
uleb 2 ; function count

FUNCTION_START ; main()
    uleb 0
    i32.const uleb 21
    call $double
    call $print_i32_type
    end
FUNCTION_END

FUNCTION_START ; double(i32) -> i32
    uleb 0
    local.get uleb 0
    local.get uleb 0
    i32.add
    end
FUNCTION_END

SECTION_END
```

And this assembles into:

```plaintext
0x00, 0x61, 0x73, 0x6d, 0x01, 0x00, 0x00, 0x00,  
0x01, 0x0c, 0x60, 0x01, 0x7f, 0x00, 0x60, 0x00,  
0x00, 0x60, 0x01, 0x7f, 0x01, 0x7f, 0x02, 0x11,  
0x01, 0x03, 0x65, 0x6e, 0x76, 0x09, 0x70, 0x72,  
0x69, 0x6e, 0x74, 0x5f, 0x69, 0x33, 0x32, 0x00,  
0x00, 0x03, 0x03, 0x02, 0x01, 0x02, 0x07, 0x08,  
0x01, 0x04, 0x6d, 0x61, 0x69, 0x6e, 0x00, 0x01,  
0x0a, 0x12, 0x02, 0x08, 0x00, 0x41, 0x15, 0x10,  
0x02, 0x10, 0x00, 0x0b, 0x07, 0x00, 0x20, 0x00,  
0x20, 0x00, 0x6a, 0x0b,  
```

Some cool things I ran into is that `i32`, `i64`, `f32`, and `f64` each have their own `add`, `sub`, etc. opcodes, so instead of checking each one, there are shortcuts. For example, `i32.add` is `0x6A`, `i64.add` is `0x7C`, `f32.add` is `0x92`, and `f64.add` is `0xA0`. So instead of checking for each one, I can just check for the type and then add the offset to the base opcode. Small things like these were some cool things I ran into while making the assembler. I also had to use multiple memory variables to store the section bytes, so that at the end of the section I can check the difference between the start and the end of section to get the byte count and then write the byte count at the start of the section followed by the section contents. This was a little tricky to figure out, but I got it working in the end. I had to do the same thing with `FUNCTION_START` and `FUNCTION_END` to get the byte count of the function body. I also had to use a variable to store the current section, so that when I see a `SECTION_END` I can write the byte count at the start of the section.

### Implementing the Assembler in WebAsm

Because of how large the python file came out to be (800 lines), instead of implementing the assembler in Web Assembly, I will use the python assembler only to create the first iteration of the WebAsm assembler. This means I will use the python WebAsm assembler to assemble my input assembly program that does the same thing as the python assembler. This is better than trying to implement the assembler in the bytecode because of how much effort it would take. I know it is a drawback, but the [Replacing Assembler](#second-step-input-is-text-and-output-is-bytes) took so long to implement, and that was just 120 lines of python code. The full assembler is 880 lines of python code, and that would be a nightmare to implement in WebAsm. So, for now, I will use the python assembler to create the first iteration of the Web Assembly assembler.

I actually don't want to lose interest in this project, and I know making this first iteration would be easier in the Assembly language, but it would still take a lot of time in effort. So I have decided to get Chat GPT (6.1 Sol) to make the assembler in the Assembly language. Chat GPT will make the assembler in the [assembler.0.1.wal](https://github.com/JBrosDevelopment/WebAsmCompiler/blob/main/Assembler/assembler.0.1.wal) (.wal = WebAsm Assembly Language) file.

For full transparency this is the entire message I sent to Chat GPT (6.1 Sol) to make the assembler in the Assembly language:

```plaintext
Here are the parameters:
- create an assembler in .wal format (this is a custom web assembly I made (WebAsm Assembly Language))
- Base this assembler DIRECTLY off of the python file: Assembler/assembler.0.0.py
- In the end, the python file will assemble your wal program and this new program will be used instead of the python file
- Please ask if you have any questions, and if you find any bugs in the python file, please stop and alert me to it and offer the fix. DO NOT edit the python file without asking my permission first.
- Please directly convert the python file into the wal program the best you can. Provide comments on each line that is converted.
- Read README.md to figure out how the wal assembly syntax looks like. Also you can look at the example at the top of the python file.
- Your entire code should stay limited to Assembler/assembler.0.1.wal
```

Besides showing me many bug fixes for my python assembler, it did in fact create the assembler in the Assembly language. The assembler is in the [assembler.0.1.wal](https://github.com/JBrosDevelopment/WebAsmCompiler/blob/main/Assembler/assembler.0.1.wal) file. I will be using this assembler to assemble my input assembly program that does the same thing as the python assembler. This is a huge step forward in this project, and I am excited to see what I can do with this new assembler. It is crazy how it just did it, and if you open up the file you will see it is 9000 lines long, which is insane. It works perfectly, very surprisingly. The final `bin/assembler.0.1.wasm` file is **14.5 KB** (14,879 Bytes).

I then created an [assembler.0.2.wal](https://github.com/JBrosDevelopment/WebAsmCompiler/blob/main/Assembler/assembler.0.2.wal) file that adds `MEMORY_KIND` and `COUNT` keywords. I made the changes myself and put them in the [Assembler.py](https://github.com/JBrosDevelopment/WebAsmCompiler/blob/main/PythonTesting/Assembler.py) and made the changes in the [assembler.0.2.wal](https://github.com/JBrosDevelopment/WebAsmCompiler/blob/main/Assembler/assembler.0.2.wal) file. I had Chat GPT then make the file easier to read and formatted it better, as well as using the `$`, `#`, `@`, and `^` symbols for variables and labels making the code more readable. The changes I made in the file also had bugs and Chat GPT was able to catch the bugs and help me fix them. The final file reached 7939 lines of code 11,860 Bytes. The reason it is smaller is because the way Chat GPT was matching character and tokens made no sense to me, and I suggested using `str A` and then adding `uleb 128` instead of using a `i32.shl` and other weird things. This really optimized the code by a significant amount.

For example, assembler.0.1.wal does this, taking 8 bytes per adding a character to the stack:

```plaintext
i32.const uleb 1
i32.const uleb 6
i32.shl
i32.const uleb 6
i32.or
```

And assembler.0.2.wal does this, taking 5 bytes per adding character to the stack:

```plaintext
i32.const uleb 128
i32.const str F
i32.add
```

Saving 3 bytes or %37 smaller. When I was going through the code I was confused on why Chat GPT did this so when I was able to make it easier to read and saving space it was a no-brainer.

I later found an easier way to do this by adding the `ascii` keyword to just encode the right value from the get-go

```plaintext
i32.const ascii [CHAR]
```

This being just 2 bytes. 8 -> 2 bytes for checking every character saved an enormous amount of space in this binary.

| Version | Binary size | Milestone |
| --- | --- | --- |
| 0.1 | 14,879 bytes | First self-hosting assembler |
| 0.2 | 11,860 bytes | Simplified character encoding |
| 0.5 | 17,218 bytes | New encoding features |
| 0.6 | 12,287 bytes | Data section and signed LEB128 optimizations |

### Bootstrapping and Adding Versions

> Bootstrapping is definitely my favorite part of this project. The ability to make the assembler assemble itself is just an insane thought. The ability to make the code entirely rely on the WAL source code and no longer depend on the original python file was such an achievement for me.

Bootstrapping in this sense is making a program that can compile itself. So, if I made `assembler.0.1.wasm` assemble `assembler.0.1.wal`, it would output `assembler.0.1.wasm2` identical to the original wasm file. You can check this by comparing the file hashes of each file:

```shell
$hash1 = (Get-FileHash "D:\WebAsmCompiler\Assembler\bin\assembler.0.1.wasm").Hash
$hash2 = (Get-FileHash "D:\WebAsmCompiler\Assembler\bin\assembler.0.1.wasm2").Hash

$hash1 -eq $hash2 
```

It was actually able to successfully bootstrap first try and both files were identical. I did the same thing with 0.2 and now versions 0.1 and 0.2 both fully work and are valid assemblers. Version 0.2 has a couple more features, is a lot easier to read the code, and is more optimized.

Below is the `run.js` code used to run the web assemblers and bootstrap

```js
// to run the assembler.0.1 wasm and input the same program (assembler.0.1.wal) and output assembler.0.1.wasm2, which should be equal to the original
// node ./Assembler/bin/runner.js ./Assembler/assembler.0.1.wal ./Assembler/bin/assembler.0.1.wal.wasm2
// to assemble assembler.0.2.wal into assembler.0.2.wal.wasm from the assembler.0.1.wal.wasm assembler
// node ./Assembler/bin/runner.js ./Assembler/assembler.0.2.wal ./Assembler/bin/assembler.0.2.wal.wasm

import { readFileSync, writeFileSync } from 'fs';

const inputFile = 'Assembler/bin/assembler.0.2.wal.wasm';

const sourcePath = process.argv[2];
const outputPath = process.argv[3];

if (!sourcePath || !outputPath) 
    throw new Error('Supply input WAL and output WASM paths');

const text = readFileSync(sourcePath, 'utf8').replace(/\r\n?/g, '\n');
if (/[^\x00-\x7f]/.test(text)) 
    throw new Error('This assembler accepts ASCII source');

const source = Buffer.from(text, 'ascii');
if (source.length + 17 >= 4194304) 
    throw new Error('Input exceeds 4 MiB source region');

const output = [];

const module = new WebAssembly.Module(readFileSync(inputFile));

const instance = new WebAssembly.Instance(module, {
  env: {
    print_i32: n => process.stdout.write(String(n)),
    print_char: n => process.stdout.write(String.fromCharCode(n)),
    write_char: n => output.push(n),
    exit_program: n => {
      throw new Error('Assembler error ' + n);
    }
  }
});

const memory = new Uint8Array(instance.exports.memory.buffer);

memory.set(source); 
memory.fill(0, source.length, source.length + 17);

instance.exports.main();

writeFileSync(outputPath, Buffer.from(output));
```

This is the only JavaScript necessary to use the WebAsm Assembler, and the Python code has been completely separated and is no longer apart of the tool chain. Each iteration I make upon the assembler will come from the previous assembler itself and not from any outside code.

#### assembler.0.3 - Error Handling

For any program, error handling and error messages are necessary for ease of development. To do this, the program will need to have premade strings saved to memory. This will also add the need for `print_string` as another JavaScript import. The import will look like this: `function print_string(pointer: i32, length: i32) -> void`. Because strings will be passed as memory pointers, all strings will have to be set in memory before the program starts. So, in the `main` entry function of the Assembly program, I will store all the strings and save their locations as variables using the `#` and `$` syntax in the assembler.

Here is an example error message:

```plaintext
PS D:\WebAsmCompiler> node Assembler/bin/run_wasm.js program.wasm
Error: Variable `print_i32` does not exist.
Occured in Section `CODE`.
Error occured on line `56`:
call $print_i32
     ~~~~~~~~~~
Program Fault.
```

This increases the size of the program significantly, especially the main function because it has to save each string to memory character by character. I did this before the `ascii` keyword so encoding each letter was 3 instructions.

#### assembler.0.4 - Adding ascii keyword

So, the current implementation for pushing a string character to the stack is as so:

```plaintext
i32.const uleb 128
i32.const str [CHAR]
i32.add
```

This is because of the way the `str` keyword is implemented. It was designed for the name of functions or exports in other sections, but when pushing to the stack in the CODE section, it doesn't give the correct value because of ULEB encoding. To encode the correct character, 128 needs to be added to it. This wastes a lot of space, and I don't know why I didn't think of this earlier but adding the new `ascii` keyword will keep it from having to add 128 each time:

```plaintext
i32.const ascii [CHAR]
```

Also this updated optimized the assembler binary by removing unreachable code left over from assembler.0.1 made by ChatGPT.

#### assembler.0.5 - Adding sleb keyword, adding the DATA section, and optimizing assembler

The `sleb` keyword will encode a value according to the Signed LEB128 format. This will be necessary for when operations like `i32.const` which expect the value to be in Signed LEB 128 format. This just makes everything more convenient and it should have been implemented earlier.

The way strings are implemented is a bunch of addresses and in the main function setting the values in these addresses to their corresponding characters. This is unnecessary and the better thing to do is to set these strings in memory. To fix this I'll add the DATA Section to the assembler. The [specs of this section can be found above](#data-section-added-in-assembler05). The next update I'll make it actually add the strings to the DATA section. This update will be for the implementation of it.

The next thing is implementing the `ascii` keyword into the assembler to optimize the binary, saving a lot of space (19kb -> 17kb).

#### assembler.0.6 - Added Strings to Data Section, Fixed Bug by adding Error Message, and optimized assembler with `sleb`

This update is implementing the changes brought up in the previous updates into the assembler. Moving Strings to the DATA section to optimize the size of the binary and the efficiency of the `main` function. I will also change the strings to be null terminated instead of printing by length. This means changing `print_string(ptr, length)` to `print_string(ptr)`. This function will print characters until it reaches the `\0` character.

Currently when encoding a ULEB-128 number, if the input is not a combination of digits (0-9) there is no error warning, and it will crash at runtime. To fix this, in the `writeFromUleb`, check to make sure the input is within the digits 0-9.

There are a few times in the code when trying to encode a specific value. Instructions like `i32.const` expect a value in Signed LEB-128 format. This has caused me to do stuff like this to get the value that I want to get:

```plaintext
i32.const uleb 128
i32.const uleb 52
i32.sub
```

could be shortened to:

```plaintext
i32.const sleb 76
```

To encode the correct number. This was another feature I wish I would've thought of before

The binary is 12,287 bytes, down from 17,218 bytes for 0.5. The smallest assembler yet! The DATA section for strings along with the `sleb` keyword for encoding saved a lot more space than I thought it would.

#### assembler.0.7 - Encoding Floating Points Numbers

This is the last major update to finish the beta version of this assembler. The update allows a way to encode Floating Point numbers. This is to start experimenting with f32 and f64 operations and for future work with the compiler supporting floats. I wanted to make one encoding keyword `float`, but I don't think there's a way to do this when differentiating between 4 and 8 byte floats. This is because `f64.const` expects 8 immediate bytes, while `f32.const` expects 4 immediate bytes.

It turns out floating point arithmetic is a beast. It was not easy for me to understand. [This article](https://eryktr.github.io/2022/06/representation-of-numbers-in-computer-memory-iee754.html) by [Eryk Trzeciakiewicz](https://eryktr.github.io/author/eryktr/) was a very helpful source in trying to understand how this works. After even learning how it worked I tried my best to implement these functions into the [Assembler.py](https://github.com/JBrosDevelopment/WebAsmCompiler/blob/main/PythonTesting/Assembler.py) file, but I had ChatGPT check it to make sure I did it correct and unsurprisingly its version was far better than mine. I ended up just using ChatGPT's version so I didn't have to worry about my code breaking.

Here is an example of using the new `float32` and `float64` keywords

```plaintext
f32.const float32 -50.31
f32.const float32 1.1
f32.add

f64.const float64 400.0001
f64.floor
```

This update also adds new error messages around encoding floats

#### assembler.0.8 - Increased Symbol Memory

This update just adds more memory for the symbol section of memory having to store `$`, `#`, `^`, and `@` labels/variables.

The size of the section grows from 4,096 to 16,384 slots (64 KiB)

This update concludes the assembler.0.x versions, the next step is to start the main versions of the assembler with assembler.1.x.

## Finalizing the Assembler

Right now the assembler requires a JavaScript host to run the WebAsm binary and supply the imported functions. This is makes sense but there is a better way this could be done, and that is to introduce WASI (Web Assembly System Interface) to this assembler. This will allow the JavaScript host to not have to worry about supplying the imported function, putting the input file into memory, or outputting the results. This can be done with the `wasi` npm package making a universal host for the assembler. This will also allow the assembler to be run in a terminal without having to use node.js with the `wasmtime`. This will be a huge step forward in making this assembler more user friendly and easier to use.

### WASI

[WASI](https://github.com/WebAssembly/WASI) is a system interface for Web Assembly that allows Web Assembly modules to interact with the host environment in a standardized way. It provides a set of APIs for performing common tasks such as file I/O, networking, and process management. By using WASI, I can make the assembler more portable and easier to use across different platforms.

Here is a simple snippet of using `wasmtime` to host the wasm file instead of using JavaScript.

```plaintext
wasmtime run Assembler/bin/hello-wasi.wasm
```

I could still use JavaScript to host this program, but I would just need to include WASI to the JavaScript file: [run-wasi.mjs](https://github.com/JBrosDevelopment/WebAsmCompiler/blob/main/Assembler/run-wasi.mjs).

### Adding WASI to the Assembler

First I needed to install `wasi` and `wasmtime` from the [GitHub Repo](https://github.com/bytecodealliance/wasmtime/releases/tag/v50.0.1). Then I tested the hello world program above and it worked perfectly. Then I used the python `PythonTesting/Assembler.py` to modify the assembler to use `fd_read` and `fd_write` to read and write the input and output files. I also made the CLI for the assembler to be able to run the assembler with command line arguments. I also added runtime error handling and the `_start` function to the assembler. After adding all this in the python file, which was no small feat, I worked on converting the changes to the new assembler.1.0.wal file.

This whole transition was a difficult process and took me a minute to wrap my head around it. Chat GPT very much helped me with this update, and I was able to verify a lot of its code and for it to verify a lot of my code.

#### assembler.1.0 - Adding WASI to the Assembler

Version 1.0 adds WASI support to the assembler.\
The following host functions will be reimplemented in WAL:

| Existing function | New implementation |
| --- | --- |
| print_string(pointer) | Find the terminator, then write the bytes to stderr |
| print_char(value) | Store one byte in scratch memory and write it to stderr |
| print_i32(value) | Format decimal digits in memory, then write them to stderr |
| write_char(value) | Append a byte to an output buffer |
| exit_program(status) | Exit through WASI proc_exit |

They use these WASI functions and values to replace the JavaScript hosted functions:

- `fd_read(i32, i32, i32, i32) -> i32`
- `fd_write(i32, i32, i32, i32) -> i32`
- `proc_exit(i32) -> void`

* `args_sizes_get`: Determine argument count and storage requirements
* `args_get`: Copy argument pointers and strings into memory
* `fd_prestat_get`: Inspect host-provided directory descriptors
* `fd_prestat_dir_name`: Read their guest-visible names
* `path_open`: Open source and output files
* `fd_close`: Close opened files

This update also added a CLI (Command Line Interface) no longer relying on JavaScript to load the file into memory for it. So now when running the assembler, it expects an input and output file in the command line.

When done the assembler interface could look like this:

```plaintext
> wasmtime --dir . assembler.wasm input.wal output.wasm
```

To be transparent I used Chat GPT to make assembler.1.0.wal based off of assembler.0.8.wal but with the changes implemented in the [Assembler.py](https://github.com/JBrosDevelopment/WebAsmCompiler/blob/main/PythonTesting/Assembler.py). Because of the scale of assembler.0.8 and the scale of the changes made in this update this seemed like the best use of time so I don't get stuck on this for too long of a time.

#### assembler.1.1 - `define` directives

This update was another beast. I made all the updates in the [Assembler.py](https://github.com/JBrosDevelopment/WebAsmCompiler/blob/main/PythonTesting/Assembler.py) myself, and then got ChatGPT to implement the changes in the assembler.1.1.wal file. In this update, I added the following keywords:

- `define_type`
- `define_import`
- `define_function`
- `define_memory`
- `define_export`
- `define_code`
- `code_end`
- `define_locals`
- `define_data`
- `SECTION_CUSTOM`

The `define_<type>` keywords are the biggest addition to this assembler in this update. This allows a much easier way to encode sections. Below is an example on how to use these keywords in a program.

I also made it so that when a variable `#<name> <value>` is set multiple times, they all point to the same variable instead of multiple variables with the same name. This will keep the symbol stack smaller and prevent potential errors.

I also made local variables and parameters defined in the `define_code` and `define_locals` keywords be local to the function itself. This means when entering a function it saves the current stack pointer before adding any locals or parameters. This is so when exiting the function it returns to that saved stack position and any new variables made are forgotten allowing future functions to share the same local variable name.

I added the `SECTION_CUSTOM` for any debugging or future need of this section. This section is assembled into the wasm binary but is ignored by the wasm runtime host.

The define keywords are a feature I've been wanting to add for a while. I have a feeling only 1 more update is needed before moving onto the compiler! Yeah this update was definitely a leap forward for this project.

```plaintext
SECTION_HEADER

SECTION SECTION_TYPE
define_type FUNCTION void -> void
define_type FUNCTION f64 -> void
define_type FUNCTION f64 f64 -> f64
SECTION_END

SECTION SECTION_IMPORT
define_import env print_f64 FUNCTION_KIND $t_f64__void
SECTION_END

SECTION SECTION_FUNCTION
define_function $t_void__void main
define_function $t_f64_f64__f64 something
SECTION_END

SECTION SECTION_EXPORT
define_export main FUNCTION_KIND $f_main
SECTION_END

SECTION SECTION_CODE
    define_code none
        define_locals none
        f64.const float64 1.55
        f64.const float64 7.99
        call $f_something
        call $f_env_print_f64
    code_end

    define_code f64 a f64 b
        define_locals 
            f64 c
            f64 d
        local.get $a
        local.get $b
        f64.mul
        local.set $c
        local.get $a
        local.get $b
        f64.div
        local.tee $d
        
        local.get $c
        f64.add
    code_end
SECTION_END
```

#### assembler.1.2 - Updated assembler codebase

Updated the codebase to use DEFINE syntax for types, imports, functions, memory, exports, function bodies, locals, and data segments.\
Locals use scoped names such as `$index` and `$result` instead of function prefixes or numeric local indices

# Outro

This concludes the wasm Assembler for this project. The next step is the compiler. Part 2 will this process more in depth, but the main idea is to have a C-type language that is a subset of C that can be compiled into the WAL formatted assembly. This can then be assembled by the assembler created in this part and then this project would have the entire toolchain.

Some future goals of this project would be that this C-type language could be compiled by the C compiler. Meaning this C-type language can be compiled by C, but not every C file can be compiled by my custom compiler. This would allow greater use for this project and expand this project beyond just a cool trinket. This system would be a lot more useful if I included a linker into the toolchain to allow multiple files to be brought into 1 wasm file. I could even make a small lightweight wasm interpreter and attach that to the wasm file so that after the file goes through the toolchain a working executable could be made. I can even make a build system and port it to other languages so I can make a programming language in rust or C that compiles into my language through this build system. This project could entirely take the place of using a system like LLVM and make it all myself. There's so much potential for this project and I can't wait to see where it goes! Stay tuned for part 2.

Overall, this project has also shown me how crazy modern compilers and programming languages are, and the long journey it took to get there. It was hard to write that first assembler I made byte by byte, I can't imagine how long it took for the first real assembler to be made. This project has been so much fun, and I can't wait to see where it takes me.