DEV Community: Vincent Corbee

HTTP Server in arm64 assembly Apple silicon M1

Vincent Corbee — Thu, 21 Aug 2025 18:34:06 +0000

How do you create a simple http server? If you are a node programmer you may simply respond with: Simple, just use the http module, create a server, listen on a port, and voila you have an http server. Ok, but can you do it in arm64 assembly? I you may respond with: Yeah… no.. why would I even want to know? And you have a valid point! But Isn’t it cool to know how you would actually instruct the cpu and os to do does things for you? If you are like me you would think it’s very cool! If not, you probably belong to the majority of programmers. So for the former, let’s build an http server in arm64 assembly.

Naming

Let’s start with preventing some confusion around names. You may have heard of ARM64 or AArch64 or even ARMv8. So what is the difference? Let’s clarify.

ARMv8 This is the architecture of the cpu. ARMv8 is used to describe the overall architecture.

AArch64 This is the name used to describe the 64-bit execution state of the ARMv8 architecture. ARMv8 also as 32-bit execution state named AArch32 but we won’t go into that.

ARM64 This is also used as an alias for AArch64.

In the rest of this article we will stick with the name arm64 when we talk about any of the above.

Gotchas

First caveat though, as the title says, we are going to be creating our server on an Apple silicon machine. You can build along on other arm64 machines or emulators but you have to adjust the system call numbers accordingly.

Another thing to keep in mind is that we will only cover what we will need in other to get the http server working, so this is not an in depth tutorial about arm64 assembly. Besides, I am not really qualified either way. Check out this excellent tutorial for a detailed look into arm64 or any of the resources in the reference section for that matter.

Something that was pretty frustrating is although macOS is based on FreeBSD, not all system calls — which we will get to later — are available. For example, recv which we want to use to read incoming messages, is not available as a system call on macOS, the same applies to timers, e.g. nanosleep and other thread related calls. As far as I know these are in the Mach part of the kernel. But I haven’t figured out how to use them, so we have to make do without them. You can find the signature of a mach system call here.

Finally, roughly speaking in an assembly file we work with two sections. One section for our instructions, which is called .text and is readonly. And a second sections which is called .data which is used for reading and writing data. Only on macOS we can’t use .data. This means that we can only define read only data in our .text section. Also we have to use a different instruction to load data.

Tools and what not

In order to compile our programs, we should have the latest xCode. To compile our program we are going to you as for our assembler and ld for our linker. These are not actually from GNU, underneath they use Clang.

The next tool that is pretty useful is a debugger. It lets us step through our program and look inside registers and memory addresses to see what data is stored. This is pretty handy since we don’t have for example a console.log to debug our program. We will be using lldb which should be installed on your mac.

Editor wise, I’m using VSCode but you can use any editor you like.

What will be of help when writing assembly code for macOS is to open /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX.sdk/usr in your editor if you can. This contains the header files for and has lots of useful information for us.

Another very useful source is de source browser. Here you can find the source for xnu, the kernel for macOS.

Call to Arm(s)64

I’m going to assume you know something about assembly language in general. If not, in the reference section are some good sources of information to get you going. So arm is a flavour of assembly language known as RISC meaning Reduced Instruction Set Computer as apposed too for example X86 which belongs to the CISC family meaning Complex Instruction Set Computer. So for one they try the use as few instructions as possible. This even means that not all instructions you use are actual instructions, they are aliases around other instructions.

Further, arm64 has a so called load store architecture which means that only load and store instructions can access memory directly. So a constraint is that you can only manipulate data via registers. Another thing is that every instruction is 4 bytes wide. This means that your data needs to be four bytes aligned or your program won’t work. Ok enough for now, let’s look at some code!

Hello world(ish)

So when creating program, the mandatory thing we need to do is create a Hello world program. A common thing to do is “print” Hello world! But in arm64 that is some next level shit! What we are going to is something much more exciting… Are you ready? We are going to run a program and.. exit with a status code 🤯. I know right? So let’s get typing.

Let start by creating a file called hello-world.s. We start of with the following lines:

.global main
.align 4
.text

First thing to note here is that things starting with a dot are not instructions, but are directives for the assembler. .global tells the assembler what symbol is visible to the linker program. In our case this is main. The next one is .text which defines readonly data where our instruction will reside. The next one is .align. Because arm64 needs to be 4 byte aligned, we use the value 4 here.

main:

First we jot down our main label to match our .global directive. You might ask, what is a label? A label is nothing more than an alias for an address. So in this case our .global directive points the address that this label represents.

Instructions

You might ask what the heck is an instruction? Wel an instruction is a way of “instructing” the cpu what to do. In arm64 an instruction is 32 bits long and is divided into fields of bits that mean certain things. Luckily we don’t have to set those bits our selfs, but let the assembler do it for us. So for us, an instruction can be broken down into an opcode and operands. The opcode is the command we want to use. We don’t use the code directly, we use a mnemonic. That instruction commands the cpu to “do” something. What that something is, is determined by the operands. I like to think in terms of the operator and the operands or function and function arguments. What the operands are, differs per instruction. But types of operands are: registers, immediate values, labels, memory addresses.

Now let’s write some instructions.

main:
  mov x0, #2          ; move immediate value 2 into register x0

Our first instruction is: mov x0, #2. So what does that instruction do? As you might expects, it is a move instruction. What it does is that is moves the value of the second operand in the register in the first operand. So you can think of the instruction as mov destination, source. In our case we move the value 2 into register x0. The # sign indicates that this is an immediate value, more specifically the decimal value 2. We could also have use hexadecimal or binary notation. In that case we have to prefix the number with 0x and 0b respectively. So we could have used 0x2. Great, our x0 register now contains the value 2.

A few thing to note here. First because an instruction is always 32 bits wide, there is a limit as to how big an immediate value can be. For the mov instruction that is 16 bits. Second, an instruction can have multiple signatures, just like for example a function can have multiple signatures. This also applies to the mov instruction.

Registers

A register can hold a 64 bit value and there are 31 general purpose registers x0 — x30. We can also use any of those register in a 32 bit mode as w0 — w30. In this case the high 32 bits will be zeroed out. Some of these register have a special meaning, these are:

x0 Is used as the return value from a subroutine — function.
x1 Is used if more than 64 bits needs to be returned.
x8 Is used to hold the system call number unless.
x16 Is used for the system call number on macOS because you know, Apple.

Note that on macOS register x18 is reserved and should not be used.

x29 / fp Is used for the frame pointer. Pointers to the bottom of the stack frame.
x30 / lr Is used to hold the location to the next instruction after a subroutine.

Next to the general purpose registers we have some special registers:

xzr | wzr This can be used as the zero register and can be used to set a register to zero.
sp The stack pointer, points to the current address in the stack.
pc The program counter, contains the location of the current instruction, which you cannot access it explicitly.
spsr Saved program status register, which you also cannot access explicitly.

There are also SIMD and Floating-Point Registers. But we won’t cover them here, since we won’t be using them.

Let’s get back to our code.

main:
  mov x0, #2          ; move immediate value 2 into register x0
  mov x16, #1         ; move the syscall number for exit into register x16

Our next instruction is similar: mov x16, #1. Here we move the value 1 into register x16.

main:
  mov x0, #2          ; move immediate value 2 into register x0
  mov x16, #1         ; move the syscall number for exit into register x16
  svc 0x80            ; make supervisor call

The last one is: svc 0x80. What does this do? Well we need a way to signal to the OS that we want to it to do something for us. So what this instruction does is, it makes a supervisor call. It lets the program communicate with the OS. We use the value 0x80 here because that is what macOS uses. In macOS this value is actually ignored. We can change it to another value and it still works fine.

System calls

Great we let the OS know that we want to do something, but how does it know “what” to do? That is where system calls come into play. You can find the list of system calls for mac os here. So in register x16 we used the value 1. What does that do? This is actually the system call number for the exit system call. Ok, what about the status code? Well, in x0 we put the value 2 which will be used as the status code. You can think of a system call as calling a function. For example to exit a program in Node you would use exit(2) to exit the program with a status code of 2. If we look at the system call for exit we see the following C function signature: void exit(int status). We can see that the return type is void and it takes a status as an argument. So in our case we call the function as exit(2).

The ABI for system calls on macOS is

ARM system call interface:

swi 0x80
args: r0-r6
return code: r0
on error, carry bit is set in the psr, otherwise carry bit is cleared.

Ok, let’s build and run this program. We are going to use as to build and ld to link the program.

as -o hello.o hello.s

As will output an object file, more precise a Mach-O object file for macOS. The first argument -o defines the name of the output file. The second argument defines the input file. So when we run this command, we will get hello.o as output. We now have to use the linker to turn in into an executable file.

ld -o hello hello.o -lSystem -syslibroot `xcrun -sdk macosx --show-sdk-path` -e main -arch arm64

As mentioned above, the linker will output an executable, more precise a Mach-O executable for macOS. The first argument -o hello defines the output file name. The second argument defines the source, that would be our newly created object file. The next argument -lSystem is needed for our program to work. This tells the linker to link with libSystem.dylib. To tell the linker where it can find this file, we use -syslibroot xcrun -sdk macosx — show-sdk-path. Remember that we used main as our global label? We have to tell the linker that this is our entry point with -e main. Lastly we the the linker which architecture to use with -arch arm64.

Now we when run.

./hello

Our program exits immediately. Now, to see if our program exited with our status code type.

echo $?

This will write the status code of the last run program to stdout. No if our program worked, we would have gotten 2. Dit you get it? If so congratulations, we have our hello world! This gives our output but we can’t really see what is going on. To look inside, we are going to run lldb with our hello program as the target.

In your terminal type.

lldb ./hello

You should see something like the following.

(lldb) target create "./hello"
Current executable set to '../hello' (arm64).
First we are going to define a break point where the program should stop when it run. We want to break at our main label. To do that type the following.

(lldb) b main

Then we run the program with the following.

(lldb) r

Now the program should stop at the specified label. Now we can step through our program and inspect registers. First we step through after our first mov instruction with the following.

(lldb) si

Remember that x0 is our status code. Now to read the contents type the following.

(lldb) re read x0

Now we should the value that is inside which is 2.

(lldb) re read x0
      x0 = 0x0000000000000002

To exit lldb type exit and then y.

Lets build a server

Alright, now let’s build a server! We will write our program in server.s. Next to our program we will write some macros which will reside in macros.s. We will also create a makefile to make it easier to compile our program. Let’s create the following file structure.

/src
- server.s
- macros.s
/obj
/bin
makefile

Our makefile will contain the following.

BIN = server

ASSEMBLER = as
LINKER = ld
ENTRYPOINT = main
ARCH = arm64
LIB_SEARCH_PATH = System -syslibroot `xcrun -sdk macosx --show-sdk-path`

ODIR = obj
BDIR = bin
SDIR = src

BINPATH = $(BDIR)/$(BIN)

SRCS = $(wildcard $(SDIR)/*.s)
OBJS = $(patsubst $(SDIR)/%.s, $(ODIR)/%.o, $(SRCS))

$(shell mkdir -p $(ODIR) $(BDIR))

$(ODIR)/%.o: $(SDIR)/%.s
 $(ASSEMBLER) -o $@ $< -g

$(BINPATH): $(OBJS)
 $(LINKER) -o $(BINPATH) ${OBJS} -l$(LIB_SEARCH_PATH) -e $(ENTRYPOINT) -arch $(ARCH)

.PHONY: clean

clean:
 rm -rf *~ $(ODIR) $(BDIR)

What this basically does is it first takes all our source files and passes them to the assembler. The assembler then outputs object files in obj folder. It then takes these object files and passes them to the linker. The linker then creates an executable and places it in our bin folder. Lastly we have a separate command clean which removes all the files from our obj and bin directory.

Now in server.s.

.global main
.align 4
.text

.include "./src/macros.s"

.equiv AF_INET, 0x2
.equiv SOCK_STREAM, 0x1
.equiv IPPROTO_IP, 0x0

.equiv STDOUT, 1

.equiv REQUEST_BUFFER_SIZE, 4096
.equiv ADDRESS_SIZE, 0x10
.equiv ADDRESS_LEN_SIZE, 0x10
.equiv STACK_SIZE_MAIN, REQUEST_BUFFER_SIZE + CLIENT_ADDRESS_SIZE + CLIENT_ADDRESS_LEN_SIZE

.equiv VAR_server_address, 0x10
.equiv VAR_client_address, 0x20
.equiv VAR_client_address_len, 0x30
.equiv VAR_request_buffer, 0x40

We start with the .global, .align, and .text directives. The we have a new directive, the .include directive. With this directive we tell the assembler to include the file at the specified path. In our case that is our macros. Next up we have another new directive .equiv. With this directive we can define constant values that we want to refer to by name throughout our application. You also have .equi which differs from .equiv in that it can be overridden. And since we don’t want that, we use .equiv. We have defined a bunch of constants. We will cover them ones we will use them. Some of them probably are already self explanatory.

After that we define our main label.

...

main:
  mov x12, VAR_stack_size_main
  stack.frame.create x12

  stack.frame.destroy x12

  sys.exit wzr

Now is a good time to talk about functions in assembly.

Functions / subroutines

In assembly we don’t have functions like in more high level languages. We also don’t call them functions but subroutines. But we do have similar concepts like caller, callee, stack frame, return address, return value and function arguments. Our main label can be seen as a function. We can define our main function signature as int main(void). It takes zero arguments and returns an integer. From here on we will just stick to the term function.

Stack

Just like any function we need a way to store data locally within the function. And how do we do this you might ask? What we can do is store this data on the stack. The stack is a region of memory that we have access to when the program runs and is of fixed size. We can add or remove things from the stack. The way data is added, is by pushing it to the stack. And to retrieve / remove, we pop data from the stack. When we push data to the stack it grows down to lower memory addresses.

So how do we work with the stack? Recall that we have a register called sp. This is called the stack pointer. Its value is the memory address of the top most item on the stack. We mentioned push and pop operations. Arm64 does not have a push and pop instruction like in arm32. The reason is that the stack pointer needs to be 16 byte aligned and a register is 8 byte. So how do we push and pop items onto / off the stack? There are two instructions that we can use to place registers onto the stack: str — store register and stp — store pair. And we have to corresponding instruction to retrieve items from the stack, ldr — load register and ldp — load pair.

Recall that we said earlier that arm64 has a load-store architecture. This means in order to work with data in memory, we need to load from and store into registers. To do this we can use the instructions above in combination with addressing modes.

Load / Store addressing modes

Arm64 has the following addressing modes in their simplest form. Let’s look at these modes with the str and ldr instruction and use the registers x0 and sp.

Simple register [base] Store
This stores the value of the x0 into or load from sp

str x0, [sp]
ldr x0, [sp]

Offset [base, #imm] [base, Xm]
This stores the value of the x0 from sp or loads from sp but with an offset. This can be an immediate value or a register.

str x0, [sp, #0x10]
ldr x0, [sp, #0x10]

Pre-indexed [base, #imm]!
This works the same as with an offset set except that after it calculates the address, it stores that back into sp.

// sp now contains the old address + 0x10
str x0, [sp, #0x10]!
ldr x0, [sp, #0x10]!

Post-indexed [base], #imm
This is just like the first mode but afwards it updates sp to contain the new address.

// sp now contains the old address + 0x10 after data is stored / retrieved
str x0, [sp], #0x10
ldr x0, [sp], #0x10

PC-relative load label
We don’t use this for the stack. It adds an offset to the program counter based on the label that is referenced and stores that in the destination register. As an example

adr x0, message

Stores the calculated address of pc — message into register x0.

Let’s get back to the stack.

With str we can push a register onto the stack as follows.

str x0, [sp, #-16]!

We use pre-index addressing mode to store x0 at the memory location of sp minus 16 bytes and afterwards subtract 16 from sp. But with this instruction we waste 8 bytes because sp needs to be 16 bytes aligned.

To pop a value from the stack into a register we use

ldr x0, [sp], #16

We use post-index addressing mode to load the value at the stack pointer and add 16 afterwards to the sp so that the stack pointer is restored to before pushing.

With stp we push two registers at once onto the stack like so

stp x0, x1, [sp, #-16]!

And popping them

ldp x0, x1 [sp], #16

Stack frame

In a function we usually don’t push and pop but most of the time we would access variables in random order. Luckily we are not limited to push and pop when operating on the stack. What we want is to allocate some same space on the stack that we can use within our function. To tie a piece of the stack to our function we can create what is called a stack frame. When you have a chain of multiple function calls, you can trace it back. In other words, you get a stack trace. And how do we make one? The way we do that is by decrementing the stack pointer with the space we need. But remember when we do this, the sp needs to be 16 byte aligned.

Ok, say we have three variables in our function var a, b and c which are 8 bytes each which gives us a total of 24 bytes. We need to round this total up so it meets the alignment criteria which will yield 32 bytes. We can now create our stack frame as follows

stp lr,fp, [sp, #-16]!
sub sp, sp, #32
mov fp, sp

We first store lr and fp onto the stack and use pre-indexing to subtract 16 bytes from sp. Then we subtract 32 bytes from sp and finally we move the value of sp into fp so our frame pointer and stack pointer align. This is also called the function prologue.

The way we store a variable, is by using an offset from the fp. Because the stack grows down, we use a positive offset. So we could store a, b and c as follows assuming the values are in registers x0, x1 and x2.

stp x0, x1, [fp, #32]
str x2, [fp, #16]

This way x0 is at the bottom and x2 is at the top. If we need them we simple load the values from the stack.

ldp x0, x1, [fp, #32]

Now at the end of the function we need to clean up our stack. The way we do this, is to restore registers we saved and increment de stack pointer.

add sp, #32
ldp fp, lr, [fp], #16

We first move the stack pointer up by 32 bytes. Next we restore lr and fp and move the stack pointer up by 16 bytes using post-indexing. This is also called the function epilogue.

Function arguments

So how do you pass function arguments to a function? The way that is usually done in arm64 is that registers x0 — x7 are used for function arguments. If you want to pass more arguments to a function they are stored on the stack. Registers x0 — x18 are called scratch registers in that these registers may be changed by the function. So if you want to preserve them, you have to store them before you call the function. Registers x19 — x30 are the responsibility of the callee to insure that the contents of these registers are preserved after the function finishes.

Return value

Functions can also return values. The way values are typically return from a function is by storing them in x0 and for values larger dan 64 bits x1 is also used.

Calling a function

So how do we call a function? Suppose we have the following code.

main:
  mov x0, #1
  mov x1, #2

  bl add_numbers

  ret

add_numbers:
  ...

  ret

We first setup two arguments to our function that are stored in x0 and x1. We then have the instruction bl add_numbers. The bl instructions is called branch with link. What it does is that it stores the memory address of the first instruction of the bl instruction in the link register(lr). It then branches to the memory location of our function add_numbers. When the return instruction is executed in the called function, it branches back to the value in the lr register. Which in our case is the ret instruction in our main function.

In our case we do that by using the macro stack.frame.create which we will write shortly.

At the end of our main function we also need to deallocate or destroy our stack frame. We do this with our macro stack.frame.destroy with the same size. At the end we exit the program with status code zero using our macro sys.exit.

So we need to write a macro. But first what is a macro? If you programmed in for example C, this will sound familiar. A macro is a way to generate code. Our assembler will replace every invocation of our macro with the code defined in that macros. This is help full when our code is repetitive or verbose and we don’t what to write it over and over again and we don’t want the overhead of a function call.

In macros.s add the following.

.ifndef __MACROS

.align 4

__MACROS:

.equiv SWI_SYSCALL, 0x80

.equiv SYS_exit, 1

.equiv STACK_entry_size, 0x10

/* Syscalls */

.macro sys.call
  svc SWI_SYSCALL
.endm

.macro sys.exit
  mov w16, SYS_exit
  sys.call
.endm

/* Stack */

.macro stack.frame.create $size
  sub sp, sp, STACK_entry_size
  sub sp, sp, \$size
  stp fp, lr, [sp]
  mov fp, sp
.endm

.macro stack.frame.destroy $size
  ldp fp, lr, [sp]
  add sp, sp, STACK_entry_size
  add sp, sp, \$size
.endm

.endif

We start with .ifndef __MACROS and and with .endif. We do this so that when this macro is includes a second time, it won’t load the contents if the __MACROS is already defined. That is because an include just loads the contents of the source into the destination file. ifndef only accepts a label so we have added it as a blank label which does not do anything.

We will include a macro for every system call we use. Why do we do this? Well for every system call we have some boiler plate. So instead of writing these instruction we simply use our macro. For example for the exit system call in stead of

mov x0, #0
mov x16, #1
svc 0x80

We will use

mov x0, #0
sys.exit

Not only do we write less instructions but also state more clearly which system call we use.

Server socket

In order to create a server, we need a socket that a client can connect too. We need a server socket. So let’s create one. Let’s add the following in server.s.

...

...

/* Error messages */

error_message_socket: .string "Could not create socket\n"
error_message_socket_len = . - error_message_socket
.align 2

main:
  ...
  mov w0, AF_INET                                       ; domain = AF_INET
  mov w1, SOCK_STREAM                                   ; type = SOCK_STREAM
  mov w2, IPPROTO_IP                                    ; protocol = IPPROTO_IP
  sys.socket

  b.cs error_socket                                     ; if carry flag is set, jump to error_socket

  mov w19, w0                                           ; store server_socket fd in x19

  mov w0, w19                                           ; sockfd = server_socket;
  sys.close

  ...

/* Error handling */

error_socket:
  mov w9, w0                                            ; store error code in w9

  mov w0, STDOUT
  adr x1, error_message_socket
  ldr x2, =error_message_socket_len
  sys.write

  mov w0, w9
  sys.exit

In our main function we create our server socket with the socket system call. We can find the definition here. It is defined as follows.

int socket(int domain, int type, int protocol);
The function takes a domain, type and protocal and it returns a file descriptor if successful.

mov w0, AF_INET                                       ; domain = AF_INET
mov w1, SOCK_STREAM                                   ; type = SOCK_STREAM
mov w2, IPPROTO_IP                                    ; protocol = IPPROTO_IP
sys.socket

We set up our arguments and call the system call with sys.socket. I all goes well we should return a file descriptor. But what if it fails? In that case it returns -1 and set’s errno to the error code. But, in our case the error code will be returned in x0, so how do we now if an error occurred? Well if an error occurred, the carry flag — can be found here — in the status register will be set. So we use the instruction

b.cs error_socket

What this does is that it jumps to the address of error_socket when the carry flag is set.

An overview of the error codes on MacOS can be found here.

In error_socket we use the write system call to write an error message to stdout.

ssize_t write(int fildes, const void *buf, size_t nbyte);

It takes a file descriptor, in our stdout, an in put buffer, in our case the address of error_message_socket and the number of bytes to write, in our case the length of our message.

mov w0, STDOUT
adr x1, error_message_socket
ldr x2, =error_message_socket_len
sys.write

Our buffer is loaded into x1 with the adr instruction. What this does is load the address of error_message_socket.

error_message_socket: .string "Could not create socket\n"
At this label we use the .string directive to define our error message. The string directives creates a null terminated ascii string.

ldr x2, =error_message_socket_len

In x2 we use the ldr to load the value of error_message_socket_len. The = let’s us load the value that is located at error_message_socket_len. Here we have defined

error_message_socket_len = . - error_message_socket

What this does is it takes the address of this location and subtracts the location of error_message_socket. What remains is the difference i.e. the length of our string.

After writing the error, we exit the program setting the status code with our error code. For this we use our macro sys.exit.

In our main code, when we are successful, we go ahead and close the server socket with sys.close. The definition of close is

int close(int fd)

The rest of our main function is going to be written before the close call.

In macros.s we add the following.

...

...
.equiv SYS_write, 4
.equiv SYS_close, 6
.equiv SYS_socket, 97

...

.macro sys.socket
  mov w16, SYS_socket
  sys.call
.endm

.macro sys.close
  mov w16, SYS_close
  sys.call
.endm

.macro sys.write
  mov w16, SYS_write
  sys.call
.endm

...

.endif

Bind

Next we need bind to our socket to an address. What we use for this is not surprisingly the bind system call.

...

/* Error messages */

...
error_message_bind: .string "Could not bind to port\n"
error_message_bind_len = . - error_message_bind
.align 2

main:
  ...

  mov  x3, #0x0200                                      ; sin_len = 0, sin_family = PF_INET
  movk x3, #0xD204, lsl #0x10                           ; sin_port = 1234
  movk x3, 0x0000, lsl #0x20                            ; sin_addr = INADDR_ANY
  movk x3, 0x0000, lsl #0x30                            ; ...

  stack.store x3, VAR_server_address                    ; store server_address to the stack

  mov w0, w19                                           ; sockfd = server_socket;
  stack.loadadr x1, VAR_server_address                  ; *sockaddr = server_address;
  mov w2, ADDRESS_LEN_SIZE                              ; socklen_t = sizeof(server_address) = 16 bytes
  sys.bind

  b.cs error_bind

  ...

/* Error handling */

...

error_bind:
  mov w19, w0
  mov w0, STDOUT
  adr x1, error_message_bind
  ldr x2, =error_message_bind_len
  sys.write

  mov w0, w19
  sys.exit

The function definition for bind is

int bind(int socket, const struct sockaddr *address, socklen_t address_len)

It takes a socket in our case our server socket, a pointer to an address, which will need to create and length of the address as an input. It returns 0 if it is successful. So we need to create a sockaddr struct. But what is it and how do we do that? We can find the struct in netinit/in.h.

struct sockaddr_in {
 __uint8_t       sin_len;
 sa_family_t     sin_family;
 in_port_t       sin_port;
 struct  in_addr sin_addr;
 char            sin_zero[8];
};

sin_len — uint8 This is not used, so we can just use 0.

sin_port — uint16 The port number we want to use, which is 1234.

sin_address — uint32 This is the address we want to bind to, because we don’t care, we use the value of INADDR_ANY.

sin_zero — char This is just padding of 8 bytes.

If we add of these bytes together, we get a total of 16 bytes. So we also know the address_len argument.

One thing to note is that this data needs to be stored in network byte order which is big endian. This means the most significant byte is stored at the smallest memory address. With little endian it is the other way around. Arm supports both. And on macOS little endian is used. Therefor we need to reverse the order of bytes.

mov  x3, #0x0200                                      ; sin_len = 0, sin_family = PF_INET
movk x3, #0xD204, lsl #0x10                           ; sin_port = 1234
movk x3, 0x0000, lsl #0x20                            ; sin_addr = INADDR_ANY
movk x3, 0x0000, lsl #0x30                            ; ...

The way we do that is as follows, we first move the sin_family, which is 0x02 and the length which is 0x00 in reverse order. We then use the instruction movk. With this instruction we preserve that is already in the register. So we first move our port number in reverse order and shift it over 16 bits. So now we have in our register 0xD2040200. Then we do the same for our sin_addr. And these are just zeros. So we end up with: 0x00000000D2040200. Because we must supply a pointer to the value, we store this value onto the stack with

stack.store x3, VAR_server_address

We can then make our call

mov w0, w19                                           ; sockfd = server_socket;
stack.loadadr x1, VAR_server_address                  ; *sockaddr = server_address;
mov w2, ADDRESS_LEN_SIZE                              ; socklen_t = sizeof(server_address) = 16 bytes
sys.bind

As you can see we load the address of server address with stack.loadadr.

Now if all goes well, the carry flag should not be set. If it is we use the same error mechanism we used previously.

In marcos.s add the following

...

...
.equiv SYS_bind, 104

...
.macro sys.bind
  mov w16, SYS_bind
  sys.call
.endm

/* Stack */

...

.macro stack.store $reg, $offset
  stp \$reg, xzr, [fp, \$offset]
.endm

.macro stack.loadadr $reg, $offset
  add \$reg, fp, \$offset
.endm

.endif

We have added a macro for storing a value onto the stack and one for retrieving the address from the stack which is an offset to the current frame pointer.

Listen

Next, we need to listen to the socket for incoming connections. For that we use listen.

int listen(int fd, int backlog)

It takes a file descriptor, our server socket and a backlog which is the maximum number of pending connections, which we set to 1.

...

/* Error messages */

...
error_message_listen: .string "Error while listening\n"
error_message_listen_len = . - error_message_listen
.align 2

/* Messages */

message_listen: .string "Listening for connections\n\n"
message_listen_len = . - message_listen
.align 2

main:
  ...

  mov w0, w19                                           ; sockfd = server_socket;
  mov w1, #1                                            ; backlog = 1
  sys.listen

  b.cs error_listen

  mov w0, STDOUT
  adr x1, message_listen
  ldr x2, =message_listen_len
  sys.write

  ...

/* Error handling */

...

error_listen:
  mov w19, w0
  mov w0, STDOUT
  adr x1, error_message_listen
  ldr x2, =error_message_listen_len
  sys.write

  mov w0, w19
  sys.exit

We use sys.listen to make the system call. If something goes wrong, we use the same routine we should be familiar with. If we don’t have an error, we print a message to stdout that we are listening for connections. 🎉

In marcos.s we add the following.

...

...
.equiv SYS_listen, 106

...

/* Syscalls */

...

.macro sys.listen
  mov w16, SYS_listen
  sys.call
.endm

...
.endif

Accept

When we get an incoming connection, we also need to accept that connection. The way we do that is surprise surprise, accept.

int accept(int socket, struct sockaddr *restrict address, socklen_t *restrict address_len);

The accept function takes in a socket, in our case our server socket, a pointer to a buffer where the accept call stores the client address and a pointer to a buffer where the length of the client address is stored.

...

/* Error messages */

...
error_message_accept: .string "Error while accepting\n"
error_message_accept_len = . - error_message_accept
.align 2

...

main:
  ...

  /* Our main loop where we listen and respond to incomming connections */
  loop:
    stack.loadadr x7, VAR_client_address                ; load *client_address

    mov w0, w19                                         ; sockfd = server_socket;
    mov x1, x7                                          ; *address = client_address;
    stack.loadadr x2, VAR_client_address_len            ; *address_len;
    sys.accept

    b.cs error_accept

    mov w10, w0                                         ; store client_socket fd in xw10

    b loop
  ...

/* Error handling */

...

error_accept:
  mov w19, w0
  mov w0, STDOUT
  adr x1, error_message_accept
  ldr x2, =error_message_accept_len
  sys.write

  mov w0, w19
  sys.exit

First we define a label loop. This loops keeps running until the program stops. We first load our client address pointer into x7. We then move our socket descripter for our server socket into x0, the first argument of accept. We then move our client address pointer into x1, the second argument. Finally we load our third argument into x2, our buffer for the client address length. Then we are ready to call accept with sys.accept. We then check to see if we have any errors.

Now if we don’t have any errors, accept wilt wait until there is a pending connection. We then go on and store our client socket descriptor in w10. When we reads the end of the loop, we branch back up.

In macro.s add the following.

...

...
.equiv SYS_accept, 30
...


/* Syscalls */

...

.macro sys.accept
  mov w16, SYS_accept
  sys.call
.endm

...

Read

Now when we have accepted an incoming connection, we need to read the data that it sends, i.e. the request. We will be using read.

ssize_t read(int fildes, void *buf, size_t nbyte);

The arguments we need is: a file descriptor, a pointer to a buffer we the data is going to be stored and the size of the buffer.

...

/* Error messages */

...
error_message_read: .string "Error while reading\n"
error_message_read_len = . - error_message_read
.align 2

...

main:
  ...

  /* Our main loop where we listen and respond to incomming connections */
  loop:
    ...

    mov w0, w10
    stack.loadadr x1, VAR_request_buffer                ; *buffer = buffer;
    mov x2, REQUEST_BUFFER_SIZE                         ; length = REQUEST_BUFFER_SIZE;
    sys.read

    b.cs error_read

    stack.loadadr x1, VAR_request_buffer
    mov x2, x0
    mov x0, STDOUT
    sys.write

    ...

    b loop

  ...

/* Error handling */

...

error_read:
  mov w19, w0
  mov w0, STDOUT
  adr x1, error_message_read
  ldr x2, =error_message_read_len
  sys.write

  mov w0, w19
  sys.exit

We first move our client socket descriptor from w10 to w0, the first argument. The second argument, the pointer to the buffer we load from the stack at the location of VAR_request buffer and store it in x1. We then move the buffer size into x2 which will be our final argument. Then we call read with sys.read. The first the we do again is check if there are errors and take care of that error. I we don’t have an error, we are going to write the request to STDOUT so we can see what was send.

In macro.s add the following.

...

...
.equiv SYS_read, 3
...

/* Syscalls */

...

.macro sys.read
  mov w16, SYS_read
  sys.call
.endm

.macro sys.close
  mov w16, SYS_close
  sys.call
.endm

...

Send

Now that we have processed request, we want to respond to that request. Because it would be rude not to right? We could use write for that, but we are not gonna, because we are rebels and because what I could get what I wanted to use which is send, to work. So we are going to use sendto.

ssize_t sendto(
  int socket, 
  const void *buffer, 
  size_t length,
  int flags, 
  const struct sockaddr *dest_addr, 
  socklen_t dest_len)

With this system call we can send a message to another socket. It takes as arguments: a socket descriptor, a pointer to a buffer containing the data to be send, the length of that buffer, additional flags — which we won’t be using — , a destination address and the length of that address. Because we have a connected socket which has an address, we don’t have to specify the destination address nor its length.

...

/* Error messages */

...
error_message_send: .string "Error while sending data\n"
error_message_send_len = . - error_message_send
.align 2

/* Messages */

...
response: .string "HTTP/1.1 200 OK\r\nContent-Type: text/html\r\nContent-Length: 15\r\n\r\nHello, world!\n"
response_len = . - response
.align 2

main:
  ...

  /* Our main loop where we listen and respond to incomming connections */
  loop:
    ...

    mov w0, w10                                         ; sockfd = client_socket;
    adr x1, response                                    ; *buffer = response;
    ldr x2, =response_len                               ; length = response_len;
    mov w3, wzr                                         ; flags = 0;
    mov w4, wzr                                         ; *dest_addr = 0;
    mov w5, wzr                                         ; dest_len = 0;
    sys.sendto

    b.cs error_send

    b loop

  ...

  ...

/* Error handling */ 

...

error_send:
  mov w19, w0
  mov w0, STDOUT
  adr x1, error_message_send
  ldr x2, =error_message_send_len
  sys.write

  mov w0, w19
  sys.exit

We start by moving our client socket descriptor w10 into w0 our first argument. Then we load the address of our response message into x1 which is our second argument a pointer to the buffer. Next we load the value at the address of response_len into x2 which is our third argument the length of the buffer. Since we won’t be using the last three arguments, we will simply set them to zero by moving wzr into w3, w4 and w5. With all our arguments set we can make the system call with sys.sendto.

Of course the last thing we need to do is our error checking and handling.

In macros.s add the following.

...

....
.equiv SYS_sendto, 133

...

/* Syscalls */

...
.macro sys.sendto
  mov w16, SYS_sendto
  sys.call
.endm

...

That was everything we needed for our http server! Our final program should look like the following.

.global main
.align 4
.text

.include "./src/macros.s"

.equiv AF_INET, 0x2
.equiv SOCK_STREAM, 0x1
.equiv IPPROTO_IP, 0x0

.equiv STDOUT, 1

.equiv REQUEST_BUFFER_SIZE, 4096
.equiv ADDRESS_SIZE, 0x10
.equiv ADDRESS_LEN_SIZE, 0x10

.equiv STACK_SIZE_MAIN, REQUEST_BUFFER_SIZE + ADDRESS_SIZE + ADDRESS_LEN_SIZE

.equiv VAR_server_address, 0x10
.equiv VAR_client_address, 0x20
.equiv VAR_client_address_len, 0x30
.equiv VAR_request_buffer, 0x40

/* Error messages */
error_message_socket: .string "Could not create socket\n"
error_message_socket_len = . - error_message_socket
.align 2
error_message_bind: .string "Could not bind to port\n"
error_message_bind_len = . - error_message_bind
.align 2
error_message_listen: .string "Error while listening\n"
error_message_listen_len = . - error_message_listen
.align 2
error_message_accept: .string "Error while accepting\n"
error_message_accept_len = . - error_message_accept
.align 2
error_message_read: .string "Error while reading\n"
error_message_read_len = . - error_message_read
.align 2
error_message_send: .string "Error while sending data\n"
error_message_send_len = . - error_message_send
.align 2

/* Messages */
message_listen: .string "Listening for connections\n\n"
message_listen_len = . - message_listen
.align 2
response: .string "HTTP/1.1 200 OK\r\nContent-Type: text/html\r\nContent-Length: 15\r\n\r\nHello, world!\n"
response_len = . - response
.align 2

main:
  mov x12, STACK_SIZE_MAIN
  stack.frame.create x12

  mov w0, AF_INET                                       ; domain = AF_INET
  mov w1, SOCK_STREAM                                   ; type = SOCK_STREAM
  mov w2, IPPROTO_IP                                    ; protocol = IPPROTO_IP
  sys.socket

  b.cs error_socket                                     ; if carry flag is set, jump to error_socket

  mov w19, w0                                           ; store server_socket fd in x19

  mov  x3, #0x0200                                      ; sin_len = 0, sin_family = PF_INET
  movk x3, #0xD204, lsl #0x10                           ; sin_port = 1234
  movk x3, 0x0000, lsl #0x20                            ; sin_addr = INADDR_ANY
  movk x3, 0x0000, lsl #0x30                            ; ...

  stack.store x3, VAR_server_address                    ; store server_address to the stack

  mov w0, w19                                           ; sockfd = server_socket;
  stack.loadadr x1, VAR_server_address                  ; *sockaddr = server_address;
  mov w2, ADDRESS_LEN_SIZE                              ; socklen_t = sizeof(server_address) = 16 bytes
  sys.bind

  cmp x0, xzr
  b.ne error_bind

  mov w0, w19                                           ; sockfd = server_socket;
  mov w1, #1                                            ; backlog = 1
  sys.listen

  b.cs error_listen

  mov w0, STDOUT
  adr x1, message_listen
  ldr x2, =message_listen_len
  sys.write

  /* Our main loop where we listen and respond to incoming connections */
  loop:
    stack.loadadr x7, VAR_client_address                ; load *client_address

    mov w0, w19                                         ; sockfd = server_socket;
    mov x1, x7                                          ; *address = client_address;
    stack.loadadr x2, VAR_client_address_len            ; *address_len;
    sys.accept

    b.cs error_accept

    mov w10, w0                                         ; store client_socket fd in w10

    mov w0, w10
    stack.loadadr x1, VAR_request_buffer                ; *buffer = buffer;
    mov x2, REQUEST_BUFFER_SIZE                         ; length = REQUEST_BUFFER_SIZE;
    sys.read

    b.cs error_read

    stack.loadadr x1, VAR_request_buffer
    mov x2, x0
    mov x0, STDOUT
    sys.write

    mov w0, w10                                         ; sockfd = client_socket;
    adr x1, response                                    ; *buffer = response;
    ldr x2, =response_len                               ; length = response_len;
    mov w3, #0                                          ; flags = 0;
    mov w4, wzr                                         ; *dest_addr = 0;
    mov w5, wzr                                         ; dest_len = 0;
    sys.sendto

    b.cs error_send

    b loop

  mov w0, w19                                           ; sockfd = server_socket;
  sys.close

  stack.frame.destroy x12

  mov w0, wzr
  sys.exit

  error_socket:
    mov w19, w0
    mov w0, STDOUT
    adr x1, error_message_socket
    ldr x2, =error_message_socket_len
    sys.write

    mov w0, w19
    sys.exit

  error_bind:
    mov w19, w0
    mov w0, STDOUT
    adr x1, error_message_bind
    ldr x2, =error_message_bind_len
    sys.write

    mov w0, w19
    sys.exit

  error_listen:
    mov w19, w0
    mov w0, STDOUT
    adr x1, error_message_listen
    ldr x2, =error_message_listen_len
    sys.write

    mov w0, w19
    sys.exit

  error_accept:
    mov w19, w0
    mov w0, STDOUT
    adr x1, error_message_accept
    ldr x2, =error_message_accept_len
    sys.write

    mov w0, w19
    sys.exit

  error_read:
    mov w19, w0
    mov w0, STDOUT
    adr x1, error_message_read
    ldr x2, =error_message_read_len
    sys.write

    mov w0, w19
    sys.exit

  error_send:
    mov w19, w0
    mov w0, STDOUT
    adr x1, error_message_send
    ldr x2, =error_message_send_len
    sys.write

    mov w0, w19
    sys.exit

And macros.s

.ifndef __MACROS

.align 4

__MACROS:

.equiv SWI_SYSCALL, 0x80

.equiv SYS_exit, 1
.equiv SYS_read, 3
.equiv SYS_write, 4
.equiv SYS_close, 6
.equiv SYS_accept, 30
.equiv SYS_socket, 97
.equiv SYS_bind, 104
.equiv SYS_listen, 106
.equiv SYS_sendto, 133

.equiv STACK_entry_size, 0x10

/* Syscalls */

.macro sys.call
  svc SWI_SYSCALL
.endm

.macro sys.exit
  mov w16, SYS_exit
  sys.call
.endm

.macro sys.socket
  mov w16, SYS_socket
  sys.call
.endm

.macro sys.close
  mov w16, SYS_close
  sys.call
.endm

.macro sys.write
  mov w16, SYS_write
  sys.call
.endm

.macro sys.bind
  mov w16, SYS_bind
  sys.call
.endm

.macro sys.listen
  mov w16, SYS_listen
  sys.call
.endm

.macro sys.accept
  mov w16, SYS_accept
  sys.call
.endm

.macro sys.read
  mov w16, SYS_read
  sys.call
.endm

.macro sys.sendto
  mov w16, SYS_sendto
  sys.call
.endm

/* Stack */

.macro stack.frame.create $size
  sub sp, sp, STACK_entry_size
  sub sp, sp, \$size
  stp fp, lr, [sp]
  mov fp, sp
.endm

.macro stack.frame.destroy $size
  ldp fp, lr, [sp]
  add sp, sp, STACK_entry_size
  add sp, sp, \$size
.endm

.macro stack.store $reg, $offset
  stp \$reg, xzr, [fp, \$offset]
.endm

.macro stack.loadadr $reg, $offset
  add \$reg, fp, \$offset
.endm

.endif

Now we can compile and run our program with.

make
./bin/server

We should see the following in our terminal.

Listening for connections

Now if we go to our browser and type in localhost:1234 we should get Hello world! printed to the screen. And in our terminal we should be able to see the request as follows.

GET / HTTP/1.1
Host: localhost:1234
Connection: keep-alive
Cache-Control: max-age=0
sec-ch-ua: "Not(A:Brand";v="24", "Chromium";v="122"
sec-ch-ua-mobile: ?0
sec-ch-ua-platform: "macOS"
DNT: 1
Upgrade-Insecure-Requests: 1
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.7
Sec-Fetch-Site: none
Sec-Fetch-Mode: navigate
Sec-Fetch-User: ?1
Sec-Fetch-Dest: document
Accept-Encoding: gzip, deflate, br
Accept-Language: en-US,en;q=0.9

And that’s it, we have created our http server in arm64 assembly for macOS! Isn’t that something.

Conclusion

And that wraps our how build a “HTTP Server in arm64 assembly Apple silicon M1”. I hope you learned something and I wish you good look on the rest of your arm64 assembly journey.

References

Smith 2020
S. Smith, Programming with 64-Bit ARM Assembly Language: Single Board
Computer Development for Raspberry Pi and Mobile Devices, New York: Apress 2020

‘Arm instruction set reference’, https://developer.arm.com/documentation/100076/0100/A64-Instruction-Set-Reference/A64-General-Instructions

‘Introduction to ARM64v8, https://book.hacktricks.xyz/macos-hardening/macos-security-and-privilege-escalation/macos-apps-inspecting-debugging-and-fuzzing/arm64-basic-assembly

‘Arm64 Tutorial’, https://mariokartwii.com/armv8/

‘MacOS system calls’, https://opensource.apple.com/source/xnu/xnu-1504.3.12/bsd/kern/syscalls.master

‘FreeBSD man pages’, https://man.freebsd.org/cgi/man.cgi?query=&apropos=0&sektion=2&manpath=macOS+14.3.1&arch=default&format=html

‘Linux system call table’, https://www.chromium.org/chromium-os/developer-library/reference/linux-constants/syscalls/

‘An introduction to arm64 assembly — macOS adaptations’, https://github.com/below/HelloSilicon?tab=readme-ov-file

‘Using the Stack in AArch64: Implementing Push and Pop’, https://community.arm.com/arm-community-blogs/b/architectures-and-processors-blog/posts/using-the-stack-in-aarch64-implementing-push-and-pop

‘Using the Stack in AArch32 and AArch64’, https://community.arm.com/arm-community-blogs/b/architectures-and-processors-blog/posts/using-the-stack-in-aarch32-and-aarch64

‘iOS ARM64 Syscalls’, https://stackoverflow.com/questions/56985859/ios-arm64-syscalls

‘xnu’, https://github.com/apple-oss-distributions/xnu

‘Writing ARM64 code for Apple platforms’, https://developer.apple.com/documentation/xcode/writing-arm64-code-for-apple-platforms

‘Application binary interface’, https://en.wikipedia.org/wiki/Application_binary_interface

‘Source browser’, https://opensource.apple.com/source/xnu/xnu-7195.81.3/

Huffman coding in Javascript

Vincent Corbee — Tue, 05 Aug 2025 11:21:55 +0000

Often I find my self fascinated by some piece of software or algorithm and get so excited that I think to my self: I‘m going to build that! And every time thinking: This can’t be so hard to build.. And then realising it is and see all my hopes and dreams shattered. 😭 Ok slight exaggeration for some extra drama. But most of the time what I found is when I embark on such an adventure, I have a hard time finding good sources, especially in Javascript, that I can understand. So with that in mind I decided to write this post, in the hope that someone else who is also interested in these esoteric topics might find this helpful.

When I was trying to figure out how to read a JPEG file in Javascript, there was a segment called DHT: Define Huffman Table. Not knowing what Huffman was, I of course professionally Googled it. It turned out to be a compression algorithm for compressing text. For example, Huffman encoding is also used in the deflate algorithm which in turn is used in, to most familiar, Gzip. Obviously the first thing I thought was, I have to build this in Javascript. I mean how hard could it be right? 🤓

So for anyone who is interested, the following is an exploration into how to implement Huffman coding in Javascript from scratch. At the end of this post we will, hopefully, have created a working library that is able to encode and decode a text with Huffman coding. 🥹

Fyi, I don’t use semicolons when I don’t have to. Hey, where talking about text compression, why waste the extra space. 🧐

Along the way we are also touching on the topic of how to work with binary data in Javascript because we will be needing it in implementing Huffman coding.

So the first question is, what is Huffman coding?

Huffman coding is a lossless compression method for compressing text.
What does this mean? It means that with Huffman coding the original text can be stored with fewer bits, at least most of the time, without the loss of information.

If we assume that we are working with text where are characters are stored as 8bits, 1 byte, then the total amount of bits required to store a text of n characters is n * 8 bits.

So For example if we want to store the text: abracadabra with a length of 11 characters we need 88 bits or 11 bytes. So how can we store the same information in fewer bits?

As the title implies, one way of doing this is through Huffman coding. The output that Huffman coding produces is a variable length code table. This code table maps characters to a code that are generated during the coding process. On average, these codes will be smaller than 8 bits required to store the actual character.

So how does Huffman coding work?

Creating the frequentie table

We first starts by creating a frequentie table. This is a table of the characters based on the occurrence. This table is then ordered based on the frequenties from highest to lowest.

If we take our previous text: abracadabra our frequentie table will look like this:

a: 5
b: 2
r: 2
c: 1
d: 1

Creating a Huffman tree

The next step is to convert this into what is called a Huffman tree.

We start by taking the characters with the lowest frequentie. In our case that is c and d and convert them into an intermediary node, which is the sum of both frequenties, and two leaf nodes with the respective character and frequentie.

                              dc:2

                          d:1    c:1

We then move this new intermediary node back in to the list based on the frequentie of the node. In our case that new node will be inserted after the r. So our new list will look like this:

a:  5
b:  2
r:  2
dc: 2 -> Which is the node we just created.

We then repeat this process until we are left with a single node in our list. The resulting list will look like this:

rdcba: 11
And our Huffman tree looks like this:

                            rdcba:11 

                       rdc:4        ba:7

                     r:2  dc:2    b:2  a:5 

                        d:1  c:1

Note that the root node’s frequentie is the sum of all characters.

Constructing the code table

Now from this binary tree we can construct our code table. So how do we do this? Well, we go down the tree and for every time we go right we wright down a 1 and when we go left we wright down a 0 until we reach a leaf node.

For the character a we first go left then right so we wright down 01.
If we do this for every character in the tree we end up with these codes:

a: 11
b: 10
r: 00
c: 011
d: 010

Compress the data

To compress the data, instead of storing the character as is, we store the code in the associated with the character in the encoding table above. In our example abracadabra we will end up with the following encoding:

11 10 00 11 011 11 010 11 10 00 11

But we can’t store only this compressed data because then we have no way to decompress is. You always need a certain “view” on the data, i.e. you need to know how to interpet it. So to be able to decompress this data, we need to store our encoding table along with te compressed data. Because we need to store this extra data, especially for shorter texts, we will actually expand our data instead of reducing it.

Note that the choice for 1 = right and 0 = left is arbitrary. You could also use 0 for right and 1 for left. Also observe that you could swap the second and third node and end up with different codes but with the same size code sizes for the same characters. Thus you can create more than one tree from the same input. For the end result is doesn’t matter because we add the encoding table along with the compressed data.

Decompress the data

To decompress the data we can simply look up a sequence of bits in the encoding table to see which character to use.

Now let’s implement it in Javascript

You can type along or clone the repo from here: https://github.com/vincentcorbee/Huffman

Fyi, this implementation is based on the premise that every character in the source text can be read as an unsigned 8 bit integer. So if you are feeling adventures, you can the ability to use multibyte characters. Further I try to be as descriptive as possible in my function and variable naming so hopefully the code itself can in large part be self explanatory.

So let’s get typing. First we create a new directory called huffman and initialise a new project. We are going to be making this without any dependencies. But since we are going to be using Typescript we are going to install typescript and ts-node and types/nodes a dev dependency.

touch huffman && cd huffman

npm init -y

npm i -D ts-node typescript @types/node

npx tsc --init

mkdir src && mkdir src/lib && mkdir src/modules && mkdir src/samples

touch src/lib/index.ts && touch src/modules/index.ts && touch src/index.ts && touch src/types.ts

In **index.ts **add the following.

export * from './encode'
export * from './decode'

In lib/index.ts add the following.

export * from './create-frequentie-table'
export * from './create-huffman-tree'
export * from './create-encoding-table'
export * from './encode-data'
export * from './to-array-buffer'
export * from './get-bit-count'

And in modules/index.ts add.

export * from './binary-reader'
export * from './binary-writer'

All of the above functionality we will be creating at the appropriate time.

In our src folder create a new file called encode.ts. In this file we are going to create a function that takes a string and outputs an array buffer with our compressed data along with the encoding table.

import { createFrequentieTable, createHuffmanTree, createEncodingTable, encodeData, toArrayBuffer } from './lib'

export const encode = (input: string) => {
  const frequentieTable = createFrequentieTable(input)
  const huffmanTree = createHuffmanTree(frequentieTable)
  const encodingTable = createEncodingTable(frequentieTable, huffmanTree)

  const encodedData = encodeData(encodingTable)(input)

  return toArrayBuffer(encodedData, encodingTable)
}

Inside our function encode we first create a frequentie table. Then we use this function to create our Huffman tree. With the frequentie table and Huffman tree we construct our encoding table. We can then proceed and encode our original data. The last thing we do is combine our encoded data and encoding table into an array buffer and return that.

So the first step is to create our frequentie tabel. In our lib folder we create a new file called create-frequentie-tabel.ts.

import { FrequentieTable } from '../types'

export const createFrequentieTable = (input: string) => {
  const frequentieTabel: FrequentieTable = {}

  for (let i = 0, l = input.length; i < l; i++) {
    const char = input.charAt(i)

    if (frequentieTabel[char] !== undefined) {
      frequentieTabel[char] ++
    } else {
      frequentieTabel[char] = 1
    }
  }

  return frequentieTabel
}

In types.ts we add the type we imported above.

export type FrequentieTable = Record<string, number>

In this function we first create an empty table. We then loop through every character and when it is in the table, we increment it’s value and if it is not in our table we add it and set it’s value to one. Once the entire input is processed, we return our table.

Next up, the huffman tree. Still in our lib folder, create a file called create-huffman-tree.ts.

import { FrequentieTable, HuffmanTree, IntermediaryNode, Node } from '../types'

const getNewIndex = (entries: Node[], count: number) => {
  let index = entries.length - 1

  while(index > 0) {
    if (count <= entries[index][1]) return index

    index--
  }

  return 0
}

const getSortedEntries = (frequentieTable: FrequentieTable): Node[] =>
  Object.entries(frequentieTable).sort((a, b) => b[1] - a[1])

export const createHuffmanTree = (frequentieTable: FrequentieTable): HuffmanTree => {
  const entries = getSortedEntries(frequentieTable)

  while(entries.length > 1) {
    const left = entries.pop() as Node
    const right = entries.pop() as Node

    const [charLeft, countLeft] = left
    const [charRight, countRight] = right

    const newCount = countLeft + countRight
    const newIndex = getNewIndex(entries, newCount)

    const intermediaryNode: IntermediaryNode = [`${charLeft}${charRight}`, newCount, [left, right]]

    entries.splice(newIndex, 0, intermediaryNode)
  }

  return entries as HuffmanTree
}

So this function needs some more explanation. Because we created our frequentie table as a simple hash map, it is not sorted on frequentie. So first we are going to converted it to a sorted array based on frequentie from greatest to lowest in the form of:
[ [ string, number] ]

Then we our going to loop through our list and on each iteration we create a new intermediary node and put it back in the list at the correct index based on the new frequentie of the new node. The intermediary node that we create is a tripple in the form of [ characters, frequentie, [ left node, right node]].

We continue this process until we end up with a single node, the root of our Huffman tree. When de loop terminates we return the Huffman tree.

We also need to add a few new types to types.ts.

// After previous types

export type IntermediaryNode = [string, number, [Node, Node]]

export type LeafNode = [string, number]

export type Node = IntermediaryNode | LeafNode

export type HuffmanTree = [IntermediaryNode]

No we have created the function for our Huffman tree, it is time to wright the function that constructs the encoding table. In our lib folder, create a new file called create-encoding-table.ts.

import { EncodingTable, HuffmanTree, Node, Encoding, FrequentieTable } from '../types'

const traverseHuffmanTree = (node: Node, char: string, encoding: Encoding = []): Encoding => {
  /* We don't need the count, so will only be using the characters and children */
  const [characters, _count, children] = node

  if (char === characters) return encoding

  if (children) {
    const [left, right] = children

    /* If left node matches go left and add 0 to the encoding */
    if (left[0].includes(char)) return traverseHuffmanTree(left, char, [...encoding, 0])

    /* If right node matches go right and add 1 to the encoding */
    if (right[0].includes(char)) return traverseHuffmanTree(right, char, [...encoding, 1])
  }

  throw Error(`No match found for: ${char}`)
}

const getCharacterEncoding = (huffmanTree: HuffmanTree) => (char: string) => {
  const [rootNode] = huffmanTree

  return traverseHuffmanTree(rootNode, char)
}

export const createEncodingTable = (frequentieTable: FrequentieTable, huffmanTree: HuffmanTree): EncodingTable =>
  Object.keys(frequentieTable).reduce((table, char) => {
    table[char] = getCharacterEncoding(huffmanTree)(char)

    return table
  }, {} as EncodingTable)

In this function we are going to map over our frequentie table and for every character in the table we are going to retrieve our new character code from our Huffman tree. This code is going to be an array of 1’s and 0’s. To do this we have to traverse the Huffman tree and look for a matching leaf node.

So for every character in the table we call getCharacterEncoding with our Huffman tree and the character we want the code for. This function then call traverseHuffmanTree with the root node and the character.

In traverseHuffmanTree, the first thing we do is check if the character matches the character in the node. If it matches we have found a matching leaf node and return the encoding, success. 🥳 Note that at this point we don’t care about the count.

If we don’t have a match, but we do have children, i.e. it is an intermediary node and we check if either the left or right node’s characters includes the character we want our code for.

If the left matches we traverse the left node and add a 0 to the encoding. And if the right matches we traverse the right node and add a 1 to the encoding.

If we don’t have a match and none of the children includes the character, we throw an error because our character does not exist in our Huffman tree and we burst into tears. 😭

In types.ts add the following types.

// After previous types

export type Encoding = number[]

export type EncodingTable = Record<string, Encoding>

So at this point, we have all we need to start encoding our data. We have created our frequentie table, we then used this to construct our Huffman tree and finally we have created our encoding table.

In our lib folder we will create a file called encode-data.ts.

import { EncodedData, EncodingTable } from '../types'

export const encodeData = (encodingTable: EncodingTable) => (input: string): EncodedData =>
  input
    .split('')
    .flatMap(char => encodingTable[char])

Also in types.ts add the following.

// After previous types

export type EncodedData = number[]

The function encodeData takes in an encoding table and returns a function that takes in a string, our input. We then split this string into separate characters and for every character we select our matching code, which is an array of 1’s and 0’s. We use flatMap because we are returning a single array of 1’s and 0's.

Now the last thing we need to do is take our encoded data and our encoding table and put them together. We are going to store our entire output in an ArrayBuffer.

We are going to create two modules to work more easily with our binary data. One is a reader and the other is a writer that extends from the reader. First we are gonna create the binary reader. In modules create a file called binary-reader.ts.

import { getBitCount } from "../lib"

export class BinaryReader {
  protected chunk: number
  protected pos: number
  protected bitPos: number
  protected bitCount: number

  view: DataView

  constructor(arrayBuffer: ArrayBuffer) {
    this.view = new DataView(arrayBuffer)
    this.pos = 0
    this.bitPos = -1
    this.chunk = 0
    this.bitCount = 0
  }

  protected getData(type = 'Uint8') {
    if (this.view.byteLength > this.pos) {
      this.bitPos = -1

      // @ts-ignore
      return this.view[`get${type}`](this.pos++)
    }

    throw new RangeError()
  }

  get buffer () {
    return this.view.buffer
  }

  getBytePosition() {
    return this.pos
  }

  seek(pos: number) {
    const oldPos = this.pos

    this.pos = pos

    return oldPos
  }

  peak(index = this.pos + 1) {
    if (this.view.byteLength > index && index > -1) {
      return this.view.getUint8(index)
    }

    return null
  }

  peakBit() {
    const chunk = this.chunk
    const pos = this.pos
    const bitPos = this.bitPos
    const bitCount = this.bitCount
    const bit = this.getBit()

    this.bitPos = bitPos
    this.chunk = chunk
    this.pos = pos
    this.bitCount = bitCount

    return bit
  }

  getPadSize() {
    if (this.chunk === null) {
      return 0
    } else {
      const bitCount = getBitCount(this.chunk)

      return 8 - bitCount
    }
  }

  getBitPos() {
    return getBitCount(this.chunk) - 1 + this.getPadSize()
  }

  getBit() {
    if (this.bitPos === -1) {
      this.chunk = this.getData()

      this.bitPos = this.getBitPos()
      this.bitCount = getBitCount(this.chunk)
    }

    if (this.chunk === null) return null

    const bitCount = this.bitCount
    const bit = this.bitPos >= bitCount ? 0 : (this.chunk >> this.bitPos) & 1

    this.bitPos--

    return bit
  }

  getUint32() {
    return (
      (this.getData() << 24) |
      (this.getData() << 16) |
      (this.getData() << 8) |
      this.getData()
    )
  }

  getUint16() {
    return (this.getData() << 8) | this.getData()
  }

  getUint8() {
    return this.getData()
  }
}

The constructor of BinaryReader takes an ArrayBuffer as input. What is an ArrayBuffer? It is a fixed length array that contains raw bytes. You can’t really do anything with it. It is simply a container. To read binary data, you need a specific window into your data. To see why you need this, consider the following. Let’s say you have the following sequence of bytes:

011000010110001001100011

How do you know what this means? This all depends on the context, without it you don’t know what to read. Let’s say the data above is part of a text which uses ASCII encoding. Then we know how to interpret it. We can read it as three blocks of unsigned 8 bit integers:

01100001|01100010|01100011

The three blocks would translate to 97 98 99 which represent the characters a b c.

But if a context dictates that we should read them as a unsigned 8 bit integer and a unsigned 16 bit integer we read the sequence as two blocks:

01100001|0110001001100011

The two blocks then translate to 97 and 25187. These two numbers then derive meaning further from the software in which it is used. This context is also what we will be providing for how to read and interpret our data.

In Javascript you use various arrays to get a window into the array buffer, e.g. Uint8Array for unsigned 8 bit integers, Uint16Array for unsigned 16 bit integers etc. Instead of using different types of array’s, our binary reader is going to use the DataView. This is a convenience class for reading and writing different types of numbers. Next to that, the DataView also handles endianness, i.e. the byte order.

Our class exposes methods to read bytes as uint8, uint16 and uint32. Also we have added the ability to read individual bits. Each of these methods internally call getData with the appropriate number type. This function in turns calls the appropriate function on our dataView with the right offset and then updates the internal position.

The reason we keep an internal position is that we can continuously read data without having to manually specify an offset as to where our view needs to look in our ArrayBuffer.

Note that instead of using dataView.getUint32 and dataView.getUint16, we are shift our result from getData by n bits and add the next result if any. The reason we do this is that we can used reuse getData and let our position be updated by that function for the number of bytes we have read.

Next to these reading methods we can also peak bits and peak bytes or go to a specific offset.

Now for our writer. In modules create a file called binary-writer.ts

import { BinaryReader } from './binary-reader'

export class BinaryWriter extends BinaryReader {
  constructor(length: number) {
    super(new ArrayBuffer(length))
  }

  private setData(data: number, type = 'Uint8') {
    let advance = 0

    switch(type) {
      case 'Uint16':
        advance = 2
        break;
      case 'Uint32':
        advance = 4
        break;
      default:
        advance = 1
    }

    if (this.view.byteLength > this.pos) {
      this.bitPos = -1

      // @ts-ignore
      this.view[`set${type}`](this.pos, data)

      this.pos += advance

      return this
    }

    return this
  }

  setUint32(data: number) {
    return this.setData(data, 'Uint32')
  }

  setUint16(data: number) {
    return this.setData(data, 'Uint16')
  }

  setUint8(data: number) {
    return this.setData(data)
  }
}

The constructor of this class takes a length and calls super with a new ArrayBuffer with that length into which we will be writing and or reading our data. This class extends the reader. So next to all the read operations we are also able to write uint8, uint16 and uint32 into the underlying ArrayBuffer. The setData method also advances our current position based on the number type we are writing.

No it’s time to wright the actual function that creates our output. So in our lib folder, create a file called to-array-buffer.ts.

import { BinaryWriter } from '../modules'
import { Encoding, EncodingTable, EncodedData } from '../types'

const getCharacterCode = (char: string) => char.charCodeAt(0)

const mapCodeToInteger = (code: Encoding) =>
  code.reduce((acc, bit) => (acc << 1) | bit, 0)

const getByteCount = (bitCount: number) => {
  const remainder = bitCount % 8

  /* Round to whole bytes*/

  return (bitCount + (remainder ? 8 - remainder : 0)) / 8
}

const mapEncodingTable = (encodingTable: EncodingTable) => {
  let lengthEncodingTable = 0

  const entries = Object.entries(encodingTable).map(([ char, code]) => {
    const { length } = code

    /*
      We add 2 bytes for the length and character and 1 or 2 for the code depending
      on wether it's code length is bigger then 8 bits
    */

    lengthEncodingTable += 2 + (length > 8 ? 2 : 1)

    /* For each code, return a triplet [ number, number, number ] */

    return [length, getCharacterCode(char), mapCodeToInteger(code)]
  })

  return [ entries, lengthEncodingTable ] as const
}

export const toArrayBuffer = (data: EncodedData, encodingTable: EncodingTable) => {
  const BYTE_COUNT_LENGTH_ENCODING_TABLE = 2
  const BYTE_COUNT_LENGTH_ENCODED_DATA = 4
  const PADDING_ENCODED_DATA = 1

  const [ entries, lengthEncodingTable ]= mapEncodingTable(encodingTable)

  const { length: bitCount } = data
  const byteCount = getByteCount(bitCount)
  const padCountEncodedData = bitCount % 8

  const binaryWriter = new BinaryWriter(
    byteCount +
    BYTE_COUNT_LENGTH_ENCODING_TABLE +
    BYTE_COUNT_LENGTH_ENCODED_DATA +
    PADDING_ENCODED_DATA +
    lengthEncodingTable)

  binaryWriter.setUint16(lengthEncodingTable)

  entries.forEach(([length, charCode, code]) => {
    binaryWriter.setUint8(length)
    binaryWriter.setUint8(charCode)

    if (length > 8) binaryWriter.setUint16(code)
    else binaryWriter.setUint8(code)
  })

  let chunk = 0
  let index = 0

  binaryWriter.setUint32(byteCount)
  binaryWriter.setUint8(padCountEncodedData)

  while (index < bitCount) {
    if (index % 8 === 0 && index !== 0) {
      binaryWriter.setUint8(chunk)

      chunk = 0
    }

    /* Shift chunk one bit to the left and add current bit */

    chunk = (chunk << 1) | data[index]

    index++
  }

  if (chunk) {
    /* We add padding to fill out the last chunk to a whole byte */

    for (let pad = 0; pad < padCountEncodedData; pad++) chunk = chunk << 1

    binaryWriter.setUint8(chunk)
  }

  return binaryWriter.buffer
}

The function toArrayBuffer takes as input our encoded data and the encoding table and outputs, as the function name suggests an ArrayBuffer.

As mentioned earlier, we need to store a couple of things in order to interpet our binary data later when we want to decompress it. So what we want to store in our ArrayBuffer is:

The encoding table
The length of the encoding table
The byte size of the source data
Number of pad bits if the length of our encoded data is not on a 8 bit boundary.
Our encoded data

So in order to be able to decode our encoded data, we need to store some meta data. This extra overhead means that, as we talked about in the beginning, that the size of the data expands. The example abracadabra that we have used in the beginning, actually expands from 11 bytes, the number of characters in the string, to 25 bytes.

Time to decode

Now that we have encoded our data, it is time to decode it again.

In our src folder, create a file called decode.ts. And add the following.

import { BinaryReader } from './modules'
import { HuffmanTree, IntermediaryNode, Node } from './types'

const getDecodedData = (binaryReader: BinaryReader) => (huffmanTree: HuffmanTree, bitCountEncodedData: number) => {
  const [root] = huffmanTree

  let bitsRead = 0

  const traverse = (node: Node, binaryReader: BinaryReader): string => {
    if (bitsRead > bitCountEncodedData) return ''

    const nodes = node[2]

    if (!nodes) return node[0]

    const bit = binaryReader.getBit()

    bitsRead++

    if (bit !== null) {
      if (nodes) return traverse(nodes[bit], binaryReader)
      else return node[0]
    } else {
      return ''
    }
  }

  let decodedData = '';

  while (bitsRead < bitCountEncodedData && binaryReader.peakBit() !== null) {
    decodedData += traverse(root, binaryReader)
  }

  return decodedData
}

const decodeHuffmanTree = (binaryReader: BinaryReader): HuffmanTree => {
  const root: IntermediaryNode = ['', 0, []]

  const huffmanTreeLength = binaryReader.getUint16()

  let indexHeader = 0

  while (indexHeader < huffmanTreeLength) {
    let lengthCode = binaryReader.getUint8()
    let indexCode = lengthCode - 1

    const char = String.fromCharCode(binaryReader.getUint8())
    const code = lengthCode > 8 ? binaryReader.getUint16() : binaryReader.getUint8()

    let entry: Node = root

    while (indexCode > -1) {
      const bit = (code >> indexCode) & 1

      entry[0] += char
      entry[1] += 1

      const nodes = entry[2] as Node[]
      const node = nodes[bit]

      if (node) {
        if (indexCode === 0) {
          nodes[bit] = [char, 1]
        } else {
          entry = node
        }
      } else if (indexCode === 0) {
        nodes[bit] = [char, 1]
      } else {
        const newEntry: IntermediaryNode = ['', 0, []]

        nodes[bit] = newEntry

        entry = newEntry
      }

      indexCode--
    }

    indexHeader += 2 + (lengthCode > 8 ? 2 : 1)
  }

  return [root]
}

const getBitCountEncodedData = (byteCountEncodedData: number, paddingSizeEncodedData: number) => byteCountEncodedData * 8 - paddingSizeEncodedData

export const decode = (buffer: ArrayBuffer) => {
  const binaryReader = new BinaryReader(buffer)

  const huffmanTree = decodeHuffmanTree(binaryReader)

  const byteCountEncodedData = binaryReader.getUint32()
  const paddingSizeEncodedData = binaryReader.getUint8()

  return getDecodedData(binaryReader)(huffmanTree, getBitCountEncodedData(byteCountEncodedData, paddingSizeEncodedData))
}

The decode function takes in an array buffer. We first instantiate a new BinaryReader with our ArrayBuffer. Then we can start decoding our data.

The first thing we are going to do is decode our Huffman tree. Inside decodeHuffmanTree, the first thing we do is extract our Huffman tree length as a uint16. When we have our length, we can read out the data from our buffer. Remember that we stored every entry in our table as a triplet [ length of code: uint8, character: uint8, code: uint8 | uint16 (depending on the size of the code)].

After we created our Huffman tree, we read out our byte count for the encoded data as a uint32 and our padding size as a uint8. Armed with that information, we can start decoding our encoded data.

Inside the function getEncodedData, we keep traversing the Huffman tree for ever bit that we read until we reach a leaf node. If we do, we return it. We continue to do this for as long as we have bits to read.

When all bits have been processed, we should have decoded our encoded data back into the original.

Moment of truth
Now it is time to see wether or not this actually works.

In our src folder create a file called test.ts. We import three samples from the samples directory. You can find these samples in the github repo: https://github.com/vincentcorbee/Huffman/tree/main/src/samples.

import assert from 'assert'

import { encode, decode } from './'
import { sampleOne, sampleTwo, sampleThree } from './samples'

const encodedDataSampleOne = encode(sampleOne)
const encodedDataSampleTwo = encode(sampleTwo)
const encodedDataSampleThree = encode(sampleThree)

const decodedSampleOne = decode(encodedDataSampleOne)
const decodedSampleTwo = decode(encodedDataSampleTwo)
const decodedSampleThree = decode(encodedDataSampleThree)

assert(decodedSampleOne === sampleOne)
assert(decodedSampleTwo === sampleTwo)
assert(decodedSampleThree === sampleThree)

console.log({
  encoded: encodedDataSampleOne.byteLength,
  decoded: decodedSampleOne.length,
  orignal: sampleOne.length
})

console.log({
  encoded: encodedDataSampleTwo.byteLength,
  decoded: decodedSampleTwo.length,
  orignal: sampleTwo.length
})

console.log({
  encoded: encodedDataSampleThree.byteLength,
  decoded: decodedSampleThree.length,
  orignal: sampleThree.length
})

Now if from our project root we run:

npx ts-node src/test.ts

{ encoded: 13268, decoded: 24543, orignal: 24543 }
{ encoded: 787, decoded: 1087, orignal: 1087 }
{ encoded: 25, decoded: 11, orignal: 11 }

Our assertions should pass and we should get the output above. 🎉 We verified that our original and decoded samples our still the same. Our output gives us the encoded, decoded and original sizes. 🥹

From our samples, we can see that the largest sample yields the biggest compression. The largest sample gives us ~46% compression, the second one ~26% compression and the last one, abracadabra, actually expands with ~127%.

Conclusion

I have found it an intriguing exercise in understanding the algorithm and implement it in Javascript. I hope that if you have gotten this far you might have found it useful and not have the feeling you have just wasted an our of your life.

UTF-16 to UTF-8 in Javascript

Vincent Corbee — Tue, 05 Aug 2025 10:59:35 +0000

How are strings in Javascript encoded? It might surprise some people that Javascript uses UTF-16 to encode strings. But if your are like me, you might be wondering: how can I convert this to UTF-8? Well today we are going to find out. 🧐

The main focus in this post is on how to convert a UTF-16 string to UTF-8 in Javascript. It is not about how to deal with strings in Javascript because that is a topic all on its own. We will shortly go over Unicode. Further we will discuss the UTF-16 and UTF-8 encoding scheme in so far as we will be needing it for our purpose.

Unicode

Unicode, not to be confused with unicorn — although the are both pretty magical 🦄 — is the de-facto encoding standard for symbols. You can even adopt a character🤘🏻. Unicode is everywhere. Unicode stores each character with a unique 21 bit scalar value for a total 1,114,112. To represent a Unicode character an encoding format is used called a Unicode transformation format UTF, not to be confused with WTF — although working with unicode you probably use it from time to time — for short.

To encode Unicode, one of three encoding forms are used: 32-bit (UTF-32), 16-bit form (UTF-16) and 8-bit (UTF-8). You might have noticed that you probable have seen different spellings. For example you will typically see UTF-8 written as utf8, utf-8 or UTF8. But the official writing is UTF followed by a hyphen followed by the encoding form.

The most widely used and probably known is UTF-8. It stores every unicode scalar value as a sequence of 8 bit unsigned integers from one up to four bytes. A single character can take more than four bytes since it can consist of more than one scalar value. For example the Australian flag 🇦🇺 takes two values U+1F1E6 and U+1F1FA and is stored in 8 bytes in UTF-8.

Unicode in Javascript

In Javascript strings are encoded in UTF-16. The string: “Hello world 💩” will be encoded as a sequences of 16 bit unsigned integers. If I asked you what is the length of this string, what would you answer? If you answered 14 you are correct. For the ones who didn’t know or pasted ‘Hello world 💩’.length in the console, you might have been surprised it was not 13. So what’s up with that? To answer that question what we have to see what the UTF-16 encoding scheme looks like.

UTF-16

In UTF-16 Unicode scalar values are either encoded in one or two unsigned 16 bit integers.

The encoding schema is as follows.

Scalar value                UTF-16 values

xxxxxxxxxxxxxxxx            xxxxxxxxxxxxxxxx
000uuuuuxxxxxxxxxxxxxxxx    110110wwwwxxxxxx    110111xxxxxxxxxx

Scalar values in the range of U+0000 — U+D7FF and U+E000 — U+FFFF are encoded as is in a single uint16.

Scalar values in the range of U+10000 — U+10FFFF are encoded as two uint16’s.

Surrogates

The code points U+10000 — U+10FFFF are encoded as a pair of surrogates. A high (leading) surrogate in the range U+D800 — U+DBFF and a low (trailing) surrogate in the range U+DC00 to U+DFFF. These surrogate values should always come in pairs. A single surrogate is not a unicode scalar value and thus makes the encoding ill formed. So how are the surrogates constructed from the scalar value?

First Subtract 0x10000 from the code point to account for the starting offset to the scalar value.

For the high surrogate shift the remainder unsigned right by 10 and add 0xD800.

For the low surrogate take the low 10 bits and add 0xDC200.

Let’s take 💩 as an example which has the value: U+1F4A9 and convert it in Javascript to a surrogate pair.

const remainder = 0x1f4a9 - 0x10000 /* 62633 0xf4a9 */
const high = (remainder >>> 10) + 0xd800 /* 55357 0xd83d */
const low = (remainder & 0x3ff) + 0xdc00 /* 56489  0xdca9 */

So 💩 is converted into the surrogate pair 0xD87D and 0xDCA9.

That’s why our initial example “Hello world 💩” has a length of 14 and not 13 because a pair of surrogates where used for our poop emoji.

And since 🇦🇺 consists of two scalar values which are both encoded as surrogate pair, we get a length of 2.

This is one the reasons if you don’t know what symbols are used in your string, you could get weird results with accessing an index in your string.
What further complicates things is that you can have composed characters. These are characters which are encoded with a base and one or more combining marks. For example the letter é — Latin Small Letter E with Acute — can be represented as one character code 0xe9 or as two 0x65 and 0x301.

UTF-8

Now let’s look at UTF-8. It assigns each Unicode scalar value to an unsigned 8 bit sequence of one to four bytes in length. This means that unlike with UTF-16 which uses surrogate pairs for U+10000 — U+10FFFF all scalar values are encoded in an 1–4 byte sequence.

Scalar value        Byte 1   Byte 2   Byte 3    Byte 4    Code points

U+0000  - U+007F    0xxxxxxx                                      128
U+0080  - U+07FF    110xxxxx 10xxxxxx                            1920
U+0800  - U+FFFF    1110xxxx 10xxxxxx 10xxxxxx                  61440
U+10000 - U+10FFFF  11110xxx 10xxxxxx 10xxxxxx  10xxxxxx      1048576

The encoding scheme looks like this.

Scalar Value                Byte 1    Byte 2    Byte 3    Byte 4

00000000 0xxxxxxx           0xxxxxxx
00000yyy yyxxxxxx           110yyyyy  10xxxxxx
zzzzyyyy yyxxxxxx           1110zzzz  10yyyyyy  10xxxxxx
000uuuuu zzzzyyyy yyxxxxxx  11110uuu  10uuzzzz  10yyyyyy  10xxxxxx

The symbols in the first range are encoded as is in 8 bits. The next three ranges are encoded with the most significants bits of the first byte set to the length of the byte sequence followed by a 0 i.e. 110, 1110 and 11110. And the following bytes have the first two most significants bits set to 10.

So how would we store 💩? Well we know the value is 0x1F4A9. This means that if we look at our encoding scheme we have to store it in four bytes.

If we overlay our schema, 0x1F4A9 looks like this: 000 00001 11110100 10101001.

We start with 1111 0000 then we add the first 3 bits of the 21 bit value which is 000 so we end up with 1111 0000. Then we start with 1000 0000 and add the next 6 bits which is 01 1111 and we and up with 1001 1111. We start again with 1000 0000 and add the next 6 bits which results in 100100 10. For the fourth byte we repeat the process and end up with 10101001.

The encoding for 💩 results in: F0, 9F, 92, A9.

In Javascript we could implement this as follows.

const codePoint = 0x1f4a9

const firstByte = 0xf0 | (codePoint >>> 18) /* 1111 0000 + first 3 bits */
const secondByte = 0x80 | (codePoint >>> 12 & 0x3f) /* 1000 0000 + next 6 bits */
const thirdByte = 0x80 | (codePoint >>> 6 & 0x3f) /* 1000 0000 + next 6 bits */
const fourthByte = 0x80 | (codePoint & 0x3f) /* 1000 0000 + next 6 bits */

Because the encoding is a variable length 8 bit sequence, it is impossible to access a character by an index without going forward and backward in the stream. So if you have an array of n 8 bit unsigned integers you can’t say give me the character at index 8 because you don’t know if that is an actual character or part of a sequence of bytes.

UTF-8 in Javascript

So now that we know more or less how UTF-16 and UTF-8 works, how would we implement UTF-16 to UTF-8 in Javascript? We are going to build two things an encoder and a decoder. The first one takes a UTF-16 string and converts into an Uint8Array. The decoder takes in a Uint8Array and outputs a UTF-16 string. You can type along but the full source code is also available on github: https://github.com/vincentcorbee/string-encoding.

Let’s get typing

We don’t need any dependencies for our actual implementation. But since we are going to be using Typescript we are going to install typescript, ts-node and types/nodes as dev dependencies. The following commands will setup the basic structure that we need for our project.

touch string-encoding && cd string-encoding

yarn init -y

yarn add -D ts-node typescript @types/node

npx tsc --init

mkdir src && mkdir src/lib && mkdir src/modules

touch src/lib/index.ts && touch src/index.ts && touch src/modules/index.ts

In index.ts add.

export * from './modules/string-encoder'
export * from './modules/string-decoder'

In lib/index.ts add.

export * from './is-leading-surrogate'
export * from './is-trailing-surrogate'
And finally in modules/index.ts add.

export * from './string-reader'
export * from './string-encoder'
export * from './string-decoder'

Encoder

We are going to start with our encoder. Create modules/string-encoder.ts.

import { isLeadingSurrogate, isTrailingSurrogate } from "../lib"
import { StringReader } from "./string-reader"

export class StringEncoder {
  readonly encoding = 'UTF-8'

  constructor() {}

  encode(source: string): Uint8Array {
    return StringEncoder.stringToUtf8(source)
  }

  static UTF16SurrogatePairToCodePoint(leading: number, trailing: number): number {
    return ((leading - 0xd800) * 0x400) + (trailing - 0xDC00) + 0x10000
  }

  static stringToUtf8(source: string): Uint8Array {
    const utf8codes: number[] = []

    const stringReader = new StringReader(source)

    let charCode: number | null

    while((charCode = stringReader.next()) !== null) {
      /* Character takes one byte in UTF-8 */
      if (charCode >= 0x0000&& charCode <= 0x007F) utf8codes.push(charCode)

      /* Character takes two bytes in UTF-8 */
      else if (charCode >= 0x0080 && charCode <=0x07FF) {
        const firstByte = 0xc0 | (charCode >>> 6)
        const secondByte = 0x80 | (charCode & 0x3f)

        utf8codes.push(firstByte, secondByte)
      }

      /* High surrogate */
      else if (isLeadingSurrogate(charCode))  {
        const leading = charCode

        /* Low surrogate */
        const trailing = stringReader.peak()

        if (trailing && isTrailingSurrogate(trailing)) {
          /* Surrogate pairs takes four bytes in UTF-8 */
          const codePoint  = StringEncoder.UTF16SurrogatePairToCodePoint(leading, trailing)

          const firstByte = 0xf0 | (codePoint >>> 18)
          const secondByte = 0x80 | (codePoint >>> 12 & 0x3f)
          const thirdByte = 0x80 | (codePoint >>> 6 & 0x3f)
          const fourthByte = 0x80 | (codePoint & 0x3f)

          utf8codes.push(firstByte, secondByte, thirdByte, fourthByte)

          stringReader.advance()
        }

         else { /* Isolated high surrogate */ }
      }

      /* Low surrogate */
      else if (isTrailingSurrogate(charCode)) { /* Isolated low surrogate */ }

      /* Character takes three bytes in UTF-8 */
      else if (charCode >= 0x0800 && 0xFFFF) {
        const firstByte = 0xe0 | (charCode >>> 12)
        const secondByte = 0x80 | (charCode >>> 6 & 0x3f)
        const thirdByte = 0x80 | (charCode & 0x3f)

        utf8codes.push(firstByte, secondByte, thirdByte)
      }
    }

    return new Uint8Array(utf8codes)
  }

  static typedArraytoString(typedArray: Uint8Array, radix = 16) {
    return `<${typedArray.reduce((acc: string, number: number, index: number) => {
      if (index > 0) acc += ', '

      acc += number.toString(radix)

      return acc
    }, '')}>`
  }
}

Our StringEncoder is instantiated without any arguments en has the encoding set to UTF-8. You could let the encoding take in an optional parameter for encoding and implement different encodings. Our class exposes a single method called encoding that has a string as its input.

Since we only encode UTF-8 we call the function stringToUtf8 with the string. The main loop in this functions runs until the entire string is processed. We have created a helper class called StringReader to read the string. Which this we can call next, peak and advance to walk through our string. It uses String.charCodeAt(0) to read a particular index in the string and gives back the character code which is the UTF-16 character code. So let’s create that first in modules/string-reader.ts.

export class StringReader {
  private position: number

  constructor(public source: string) {
    this.position = 0
  }

  private isInRange(position: number) {
    if (position > -1 && position < this.source.length) return true

    return false
  }

  next() {
    if (!this.isInRange(this.position)) return null

    return this.source[this.position++].charCodeAt(0)
  }

  previous() {
    if (!this.isInRange(this.position)) return null

    return this.source[this.position--].charCodeAt(0)
  }

  peak() {
    const oldPosition = this.position

    const character = this.next()

    this.position = oldPosition

    return character
  }

  seek(position: number) {
    if (!this.isInRange(position)) throw RangeError(`Offset: ${position} is out of range`)

    this.position = position

    return this
  }

  advance() {
    const position = this.position + 1

    if (!this.isInRange(position)) this.position = -1
    else this.position++

    return this
  }

  getPosition() {
    return this.position
  }
}

We are then going to check if we need to store the character as one, two, three or four bytes. In every case we will be outputting 8 bit unsigned integers.

If the character code can be represented as one, two or three bytes the character code in UTF-16 maps to the Unicode scalar value so we can just store these codes according to our schema. If the character code needs to be stored in four bytes we are dealing with surrogate pairs. So we peak the next code en check if it is in fact a low surrogate. If it is we construct the scalar value from the high and low surrogate. We simple reverse the process of encoding the the value. Once we have that we can encode the code point as we already have discussed above and advance are string reader.

Once we have processed the entire string we return a new Uint8Array with our new and shine UTF-8 encodings.

Decoder

Now that we have our decoder, we would also like to be able to decode a UTF-8 encoding into a UTF-16 string.

Let’s create modules/string-decoder.ts with the following.

export class StringDecoder {
  readonly encoding = 'UTF-8'

  constructor() {}

  static stringFromUTF16CharCode(charCodes: number[]): string {
    return String.fromCharCode(...charCodes)
  }

  static UTF8ToString(uint8Array: Uint8Array): string {
    const stringFromUTF16CharCode = StringDecoder.stringFromUTF16CharCode

    const charCodes: number[] = []

    for (let index = 0, length = uint8Array.byteLength; index < length; index++) {
      const charCode = uint8Array[index]

      /* Character takes one byte */
      if (charCode < 0xc0) charCodes.push(charCode)

      /* Character takes two bytes */
      else if (charCode < 0xe0) charCodes.push((charCode & 0x1f) << 6 | (uint8Array[++index] & 0x3f))

      /* Character takes three bytes */
      else if(charCode < 0xef) charCodes.push((charCode & 0xf) << 12 | ((uint8Array[++index] & 0x3f) << 6) | (uint8Array[++index] & 0x3f))

      /* Character takes four bytes */
      else {
        /* Character consists of high and low surrogate pair */
        const codePoint = ((charCode & 0x7) << 18 | ((uint8Array[++index] & 0x3f) << 12) | ((uint8Array[++index] & 0x3f) << 6) | (uint8Array[++index] & 0x3f)) - 0x10000

        charCodes.push((codePoint >>> 10) + 0xD800, (codePoint & 0x3ff) + 0xDC00)
      }
    }

    return stringFromUTF16CharCode(charCodes)
  }

  decode(typedArray: Uint8Array): string {
    return StringDecoder.UTF8ToString(typedArray)
  }
}

The decoder also does not take any arguments cause we are going to set the encoding fixed to UTF-8. And surprisingly we expose a public method called decode which takes in a typed array which in our case will be a Uint8Array because that is the only one we will be supporting. This functions calls UTF8ToString with the typed array.

The main loops runs over the length of the array. In this loop we check if the encoding will consists of one, two, three or four bytes and process them accordingly. If you recalled the encoding, we know that the first byte of a sequence tells us how many bytes we need to process to retrieve the scalar value. When we only have one byte we know we can just store the value as is. If we have two or three bytes we know we can use the stored scalar value as is because in UTF-16 they are stored in 2 bytes. To piece the code point back together we need to retrieve the stored code value from the byte sequence as shown in the schema. If we have a four byte sequence, we are dealing with surrogate pairs. In this case next to retrieving the scalar value, we will be transforming that scalar value into a surrogate pair.

When every byte is processed, call stringFromUTF16CharCode which calls String.fromCharCode with all of our UTF-16 character codes and returns a string.

If everything go’s well we should output a valid string.

Now let’s tests our new encoder and decoder. Create src/test.ts.

import { StringDecoder, StringEncoder } from "."

const stringA = '💩'
const stringB = '🇬🇧'
const stringC = 'abce'
const stringD = 'e\u0301'
const stringE = 'é'
const stringF = '𐐷€'
const stringG = '🫱🏿‍🫲🏻'
const stringH = 'Привет, мир!'

const input = stringA

const stringEncoder = new StringEncoder()
const stringDecoder = new StringDecoder()

const uint8Array = stringEncoder.encode(input)

console.log(StringEncoder.typedArraytoString(uint8Array))

const decoded = stringDecoder.decode(uint8Array)

console.log(decoded)

Now if we run

npx ts-node src/test.ts

from our root folder, we should see the UTF-8 encoded data in the console followed by the decoding which should equal our original string.

I did notice something though. If I were to encode and decode a multi scalar value for example the flag of Great Britain, I would get back GB in my terminal in VS Code. Which is not wrong since the flag uses REGIONAL INDICATOR SYMBOL LETTER G and REGIONAL INDICATOR SYMBOL LETTER B. But if I take the UTF-16 character codes that we produced and turn them into a symbol in the console I do get to see the flag symbol. Not really sure what is going on there. 🤔

Conclusion

I hope if you made it this far you have found it mildly interesting. At least I did. And I always learn something myself when I try to teach others something I learned.

LZ77 compression in Javascript

Vincent Corbee — Mon, 04 Aug 2025 11:37:39 +0000

When I was working on a library for creating pdf’s in Javascript, I wanted that the library was able to use compression filters in stream objects. One such filter that pdf supports is FlateDecode which uses the deflate compression algorithm. Deflate is also what is used in Gzip. So with fresh enthusiasm for the challenge ahead I looked for the rfc. There were a few parts in constructing the bit stream that stood out, Huffman encoding and LZ77. Since I already knew how Huffman coding works (kinda), I set my sights on LZ77. So what is LZ77 and how do you implement it from scratch in Javascript(ish)? Let’s find out.

Side note. The first fun fact I discovered is that deflate doesn’t use LZ77 compression at all.. 💩 It uses a derivation of that algorithm named LZSS- which I wrote about here. So the end result is useless for deflate, but hey, we learned something.🤓 The main difference is that while LZ77 outputs items as a triplet in the form of [offset, length, character]. LZSS outputs based ont he length of the match, either a literal or a tuple in the form of [offset, length]. I understand if this doesn’t make sense now, but it will, I promise — hopefully. 🤞🏻

So what is LZ77

LZ77 is a lossless compression algorithm created by Lempel and Ziv in 1977. The LZ77 algorithm compresses data by replacing duplicate sections of data with metadata in the form of a triplet [ offset, length, character ].

First some key terms need to be addressed:

coding position

This is the position in the input stream for the character currently being encoded

search buffer

The search buffer is a history of processed characters with a fixed length in which the algorithm searches to match for duplicate segments.

lookahead buffer

The lookahead buffer is a fixed length set af characters after the current character into which te algorithm looks to find the longest match possible. So for example if the current character being processed is a A after that comes the characters B C D E. If A matches, it will try and match as much characters as it can in the lookahead buffer.

sliding window

The three parts above are called the sliding window. It is called sliding because it moves over the input stream as more characters are processed.

So how does this process work?

Let’s use the following as our input: abcbbcbaaaaaa

First let’s define the size of our sliding window. Let’s say we have a search buffer of 6 characters and a lookahead buffer of 5 characters.

Then the algorithms starts with moving the coding position to the start of the input. This means that our search buffer is empty, our current coding position points at character a and our lookahead buffer contains babcb.

Thus our state looks like this: