Support relocation of string address

15 files changed, 500 insertions, 251 deletions

diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGen.java b/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGen.java
index d65d25b5..8e8c2735 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGen.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGen.java
@@ -42,7 +42,7 @@ public class WasmCodeGen {
                 var offset = defineStringResult.value();
                 context = defineStringResult.context();
 
-                yield context.addInstruction(new WasmI32Const(offset));
+                yield context.addInstruction(offset);
             }
 
             case PushUnitInstruction pushUnit ->
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenContext.java b/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenContext.java
index 10f55c68..46756088 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenContext.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenContext.java
@@ -5,6 +5,7 @@ import org.pcollections.OrderedPMap;
 import org.pcollections.PMap;
 import org.pcollections.PVector;
 import org.shedlang.compiler.backends.llvm.NameAllocator;
+import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmMemoryAddress;
 import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmExpression;
 import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmInstruction;
 import org.shedlang.compiler.backends.wasm.structure.ast.modules.*;
@@ -27,7 +28,7 @@ public record WasmCodeGenContext(
         Empty.map()
     );
 
-    public WasmCodeGenResult<Integer> addData(
+    public WasmCodeGenResult<WasmMemoryAddress> addData(
         WasmCodeGenGlobalSpace space,
         byte[] data,
         WasmAlignment alignment
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenStrings.java b/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenStrings.java
index a2431e60..acf29b4d 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenStrings.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenStrings.java
@@ -1,5 +1,6 @@
 package org.shedlang.compiler.backends.wasm;
 
+import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmMemoryAddress;
 import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmAlignment;
 
 import java.nio.ByteBuffer;
@@ -9,7 +10,7 @@ public class WasmCodeGenStrings {
     private WasmCodeGenStrings() {
     }
 
-    public static WasmCodeGenResult<Integer> defineString(
+    public static WasmCodeGenResult<WasmMemoryAddress> defineString(
         String value,
         WasmCodeGenContext context
     ) {
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/WasmMemoryBuilder.java b/src/main/java/org/shedlang/compiler/backends/wasm/WasmMemoryBuilder.java
index 579fc586..d3dc728c 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/WasmMemoryBuilder.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/WasmMemoryBuilder.java
@@ -2,6 +2,7 @@ package org.shedlang.compiler.backends.wasm;
 
 import org.pcollections.OrderedPMap;
 import org.shedlang.compiler.backends.llvm.NameAllocator;
+import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmMemoryAddress;
 import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmExpression;
 import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmI32Const;
 import org.shedlang.compiler.backends.wasm.structure.ast.linking.WasmDataSegmentIndex;
@@ -20,6 +21,8 @@ import java.util.Optional;
 public class WasmMemoryBuilder {
     public static final WasmMemoryBuilder EMPTY = new WasmMemoryBuilder(OrderedPMap.empty(), 0);
 
+    private static final WasmDataSegmentIndex DATA_SEGMENT_INDEX = new WasmDataSegmentIndex(0);
+
     private final OrderedPMap<String, Entity> entities;
     private final int size;
 
@@ -48,7 +51,7 @@ public class WasmMemoryBuilder {
                     entities.values().stream()
                         .map(entity -> new WasmDataSymbol(
                             entity.name,
-                            new WasmDataSegmentIndex(0),
+                            DATA_SEGMENT_INDEX,
                             entity.offset,
                             entity.data.length
                         ))
@@ -59,7 +62,7 @@ public class WasmMemoryBuilder {
         return module;
     }
 
-    public record Result(int offset, WasmMemoryBuilder memory) {
+    public record Result(WasmMemoryAddress offset, WasmMemoryBuilder memory) {
     }
 
     public Result add(
@@ -82,8 +85,7 @@ public class WasmMemoryBuilder {
             entities.plus(fullName, new Entity(fullName, offset, data, alignment)),
             offset + data.length
         );
-        // TODO: return relocated offset
-        return new Result(offset, builder);
+        return new Result(new WasmMemoryAddress(DATA_SEGMENT_INDEX, offset), builder);
     }
 
     private record Entity(String name, int offset, byte[] data, WasmAlignment alignment) {
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmInstruction.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmInstruction.java
index 9467a9e7..4e1cc958 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmInstruction.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmInstruction.java
@@ -1,4 +1,4 @@
 package org.shedlang.compiler.backends.wasm.structure.ast.instructions;
 
-public sealed interface WasmInstruction permits WasmDrop, WasmI32Const, WasmI64Const, WasmLocalGet, WasmLocalSet, WasmReturn {
+public sealed interface WasmInstruction permits WasmDrop, WasmI32Const, WasmI64Const, WasmLocalGet, WasmLocalSet, WasmMemoryAddress, WasmReturn {
 }
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmMemoryAddress.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmMemoryAddress.java
new file mode 100644
index 00000000..704f7f16
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmMemoryAddress.java
@@ -0,0 +1,14 @@
+package org.shedlang.compiler.backends.wasm.structure.ast.instructions;
+
+import org.shedlang.compiler.backends.wasm.structure.ast.linking.WasmDataSegmentIndex;
+
+/**
+ * This is a fake instruction that corresponds to an i32.const instruction for
+ * an offset into a data segment. Encapsulating this in its own instruction
+ * avoids having to separately track relocation.
+ */
+public record WasmMemoryAddress(
+    WasmDataSegmentIndex dataSegmentIndex,
+    int dataSegmentOffset
+) implements WasmInstruction {
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatInstructions.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatInstructions.java
index 09161143..f58c396a 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatInstructions.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatInstructions.java
@@ -1,6 +1,5 @@
 package org.shedlang.compiler.backends.wasm.structure.binary;
 
-import org.shedlang.compiler.backends.wasm.structure.BinaryWriter;
 import org.shedlang.compiler.backends.wasm.structure.ast.instructions.*;
 
 import java.io.IOException;
@@ -13,7 +12,10 @@ public class WasmBinaryFormatInstructions {
     private WasmBinaryFormatInstructions() {
     }
 
-    private static void writeInstruction(WasmInstruction instruction, BinaryWriter writer) {
+    private static void writeInstruction(
+        WasmInstruction instruction,
+        WasmBinaryWriter writer
+    ) {
         switch (instruction) {
 
             // == Control Instructions ==
@@ -44,11 +46,18 @@ public class WasmBinaryFormatInstructions {
 
             case WasmI32Const i32Const -> {
                 writer.writeByte(0x41);
-                Leb128Encoding.encodeSignedInt32(i32Const.value(), writer);
+                writer.writeSignedInt32(i32Const.value());
             }
             case WasmI64Const i64Const -> {
                 writer.writeByte(0x42);
-                Leb128Encoding.encodeSignedInt64(i64Const.value(), writer);
+                writer.writeSignedInt64(i64Const.value());
+            }
+
+            // == Relocatable Instructions ==
+
+            case WasmMemoryAddress memoryAddress -> {
+                writer.writeByte(0x41);
+                writer.writeRelocatableUnsignedInt32(WasmRelocationType.MEMORY_ADDR_SLEB, memoryAddress);
             }
         }
     }
@@ -57,7 +66,7 @@ public class WasmBinaryFormatInstructions {
 
     static void writeExpression(
         WasmExpression expression,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) throws IOException  {
         for (var instruction : expression.instructions()) {
             writeInstruction(instruction, writer);
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatLinking.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatLinking.java
index ecc06f71..224508ec 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatLinking.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatLinking.java
@@ -1,6 +1,6 @@
 package org.shedlang.compiler.backends.wasm.structure.binary;
 
-import org.shedlang.compiler.backends.wasm.structure.BinaryWriter;
+import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmMemoryAddress;
 import org.shedlang.compiler.backends.wasm.structure.ast.linking.WasmDataSegmentIndex;
 import org.shedlang.compiler.backends.wasm.structure.ast.linking.WasmDataSymbol;
 import org.shedlang.compiler.backends.wasm.structure.ast.linking.WasmInitFunc;
@@ -11,14 +11,9 @@ import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmGlobalIndex
 import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmModule;
 
 import java.io.IOException;
-import java.util.Collection;
-import java.util.List;
-import java.util.stream.Stream;
+import java.util.*;
 
-import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatConventions.writeVec;
 import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatModules.*;
-import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatSize.writeSize;
-import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatValues.writeString;
 
 public class WasmBinaryFormatLinking {
     // Corresponds to https://github.com/WebAssembly/tool-conventions/blob/main/Linking.md
@@ -26,19 +21,74 @@ public class WasmBinaryFormatLinking {
     private WasmBinaryFormatLinking() {
     }
 
+    public static void writeLinkingSections(
+        WasmModule module,
+        WasmBinaryWriter writer
+    ) throws IOException {
+        var symbolTable = generateSymbolTable(module);
+
+        writeLinkingSection(module, symbolTable, writer);
+        writeRelocationSections(symbolTable, writer);
+    }
+
+    // == Relocation Sections ==
+
+    private static void writeRelocationSections(
+        SymbolTable symbolTable,
+        WasmBinaryWriter writer
+    ) throws IOException {
+        for (var relocationEntriesForSection : writer.relocationEntries().entrySet()) {
+            writeRelocationSection(
+                relocationEntriesForSection.getKey(),
+                relocationEntriesForSection.getValue(),
+                symbolTable,
+                writer
+            );
+        }
+    }
+
+    private static void writeRelocationSection(
+        int sectionIndex,
+        List<WasmRelocationEntry> relocationEntries,
+        SymbolTable symbolTable,
+        WasmBinaryWriter writer
+    ) throws IOException {
+        // TODO: don't assume CODE
+        writeCustomSection("reloc.CODE", writer, () -> {
+            writer.writeUnsignedInt32(sectionIndex);
+            writer.writeVec(
+                relocationEntries,
+                relocationEntry -> writeRelocationEntry(relocationEntry, symbolTable, writer)
+            );
+        });
+    }
+
+    private static void writeRelocationEntry(
+        WasmRelocationEntry relocationEntry,
+        SymbolTable symbolTable,
+        WasmBinaryWriter writer
+    ) {
+        var symbolIndex = symbolTable.memoryAddressToSymbolIndex(relocationEntry.index());
+
+        writer.writeByte(relocationEntry.type().id());
+        writer.writeUnsignedInt32(relocationEntry.sectionContentsOffset());
+        writer.writeUnsignedInt32(symbolIndex.value());
+
+        // TODO: handle types without addends
+        writer.writeSignedInt32(0);
+    }
+
     // == Linking Metadata Section ==
 
-    private static final int VERSION = 2;
+    private static final int LINKING_SECTION_VERSION = 2;
 
-    public static void writeLinkingSection(
+    private static void writeLinkingSection(
         WasmModule module,
-        WasmIndexTable indexTable,
-        BinaryWriter writer
+        SymbolTable symbolTable,
+        WasmBinaryWriter writer
     ) throws IOException {
         writeCustomSection("linking", writer, () -> {
-            Leb128Encoding.encodeUnsignedInt32(VERSION, writer);
-
-            var symbolTable = generateSymbolTable(module);
+            writer.writeUnsignedInt32(LINKING_SECTION_VERSION);
 
             writeSegmentInfoSubsection(module, writer);
             writeSymbolTableSubsection(symbolTable, writer);
@@ -48,11 +98,11 @@ public class WasmBinaryFormatLinking {
 
     private static void writeSubsection(
         SubsectionType type,
-        BinaryWriter writer,
+        WasmBinaryWriter writer,
         WasmBinaryFormatModules.Write writeContent
     ) throws IOException {
         writer.writeByte(type.id);
-        writeSize(writer, writeContent::write);
+        writer.writeSize(writeContent::write);
     }
 
     private enum SubsectionType {
@@ -70,18 +120,17 @@ public class WasmBinaryFormatLinking {
 
     private static void writeSegmentInfoSubsection(
         WasmModule module,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) throws IOException {
         if (module.dataSegments().size() > 0) {
             writeSubsection(SubsectionType.WASM_SEGMENT_INFO, writer, () -> {
-                writeVec(
+                writer.writeVec(
                     module.dataSegments(),
                     dataSegment -> {
-                        writeString(dataSegment.name(), writer);
+                        writer.writeString(dataSegment.name());
                         writeAlignment(dataSegment.alignment(), writer);
                         writeFlags(List.of(), writer);
-                    },
-                    writer
+                    }
                 );
             });
         }
@@ -90,16 +139,15 @@ public class WasmBinaryFormatLinking {
     private static void writeInitFuncsSubsection(
         WasmModule module,
         SymbolTable symbolTable,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) throws IOException {
         if (module.initFuncs().size() > 0) {
             writeSubsection(SubsectionType.WASM_INIT_FUNCS, writer, () -> {
-                writeVec(
+                writer.writeVec(
                     module.initFuncs(),
                     initFunc -> {
                         writeInitFunc(initFunc, symbolTable, writer);
-                    },
-                    writer
+                    }
                 );
             });
         }
@@ -108,49 +156,48 @@ public class WasmBinaryFormatLinking {
     private static void writeInitFunc(
         WasmInitFunc initFunc,
         SymbolTable symbolTable,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) {
-        Leb128Encoding.encodeUnsignedInt32(initFunc.priority(), writer);
+        writer.writeUnsignedInt32(initFunc.priority());
         var symbolIndex = symbolTable.funcIndexToSymbolIndex(initFunc.funcIndex());
         writeSymbolIndex(symbolIndex, writer);
     }
 
     private static void writeSymbolTableSubsection(
         SymbolTable symbolTable,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) throws IOException {
         if (symbolTable.symbolInfos.size() > 0) {
             writeSubsection(SubsectionType.WASM_SYMBOL_TABLE, writer, () -> {
-                writeVec(
+                writer.writeVec(
                     symbolTable.symbolInfos,
-                    symbolInfo -> writeSymbolInfo(symbolInfo, writer),
-                    writer
+                    symbolInfo -> writeSymbolInfo(symbolInfo, writer)
                 );
             });
         }
     }
 
-    private static void writeSymbolInfo(SymbolInfo symbolInfo, BinaryWriter writer) {
+    private static void writeSymbolInfo(SymbolInfo symbolInfo, WasmBinaryWriter writer) {
         switch (symbolInfo) {
             case SymbolInfo.Function function -> {
                 writer.writeByte(SymbolType.FUNCTION.id);
                 writeFlags(function.flags, writer);
                 writeFuncIndex(function.funcIndex, writer);
-                writeString(function.name(), writer);
+                writer.writeString(function.name());
             }
             case SymbolInfo.Data data -> {
                 writer.writeByte(SymbolType.DATA.id);
                 writeFlags(data.flags, writer);
-                writeString(data.dataSymbol.name(), writer);
+                writer.writeString(data.dataSymbol.name());
                 writeDataSegmentIndex(data.dataSymbol.dataSegmentIndex(), writer);
-                Leb128Encoding.encodeUnsignedInt32(data.dataSymbol.offset(), writer);
-                Leb128Encoding.encodeUnsignedInt32(data.dataSymbol.size(), writer);
+                writer.writeUnsignedInt32(data.dataSymbol.offset());
+                writer.writeUnsignedInt32(data.dataSymbol.size());
             }
             case SymbolInfo.Global global -> {
                 writer.writeByte(SymbolType.GLOBAL.id);
                 writeFlags(global.flags, writer);
                 writeGlobalIndex(global.globalIndex, writer);
-                writeString(global.name(), writer);
+                writer.writeString(global.name());
             }
         }
     }
@@ -173,62 +220,87 @@ public class WasmBinaryFormatLinking {
     private static class SymbolTable {
         private final List<SymbolInfo> symbolInfos;
         private final int functionSymbolIndexOffset;
+        private final Map<WasmMemoryAddress, WasmSymbolIndex> memoryAddressToSymbolIndex;
 
-        public SymbolTable(List<SymbolInfo> symbolInfos, int functionSymbolIndexOffset) {
+        public SymbolTable(
+            List<SymbolInfo> symbolInfos,
+            int functionSymbolIndexOffset,
+            Map<WasmMemoryAddress, WasmSymbolIndex> memoryAddressToSymbolIndex
+        ) {
             this.symbolInfos = symbolInfos;
             this.functionSymbolIndexOffset = functionSymbolIndexOffset;
+            this.memoryAddressToSymbolIndex = memoryAddressToSymbolIndex;
         }
 
         public WasmSymbolIndex funcIndexToSymbolIndex(WasmFuncIndex funcIndex) {
             return new WasmSymbolIndex(funcIndex.value() + functionSymbolIndexOffset);
         }
+
+        public WasmSymbolIndex memoryAddressToSymbolIndex(WasmMemoryAddress memoryAddress) {
+            var symbolIndex = memoryAddressToSymbolIndex.get(memoryAddress);
+            if (symbolIndex == null) {
+                // TODO: better error
+                throw new RuntimeException("could not find symbol index for " + memoryAddress);
+            } else {
+                return symbolIndex;
+            }
+
+        }
     }
     
     private static SymbolTable generateSymbolTable(WasmModule module) {
-        var functionSymbolIndexOffset = 0;
-        var functionSymbols = module.indexedFunctions().stream()
-            .map(function -> {
-                var flags = switch (function) {
-                    case WasmModule.IndexedFunction.Definition definition ->
-                        List.<SymbolFlag>of();
-
-                    case WasmModule.IndexedFunction.Import import_ ->
-                        List.of(SymbolFlag.UNDEFINED, SymbolFlag.EXPLICIT_NAME);
-                };
-                return new SymbolInfo.Function(
-                    flags,
-                    function.funcIndex(),
-                    function.name()
-                );
-            });
+        var symbolInfos = new ArrayList<SymbolInfo>();
+        var memoryAddressToSymbolIndex = new HashMap<WasmMemoryAddress, WasmSymbolIndex>();
 
-        var dataSymbols = module.dataSegments().stream()
-            .flatMap(dataSegment ->
-                dataSegment.symbols().stream()
-                    .map(dataSymbol -> new SymbolInfo.Data(List.of(), dataSymbol))
+        var functionSymbolIndexOffset = 0;
+        for (var function : module.indexedFunctions()) {
+            var flags = switch (function) {
+                case WasmModule.IndexedFunction.Definition definition ->
+                    List.<SymbolFlag>of();
+
+                case WasmModule.IndexedFunction.Import import_ ->
+                    List.of(SymbolFlag.UNDEFINED, SymbolFlag.EXPLICIT_NAME);
+            };
+            var symbolInfo = new SymbolInfo.Function(
+                flags,
+                function.funcIndex(),
+                function.name()
             );
+            symbolInfos.add(symbolInfo);
+        }
 
-        var globalSymbols = module.indexedGlobals().stream()
-            .map(global -> {
-                var flags = switch (global) {
-                    case WasmModule.IndexedGlobal.Definition definition ->
-                        List.<SymbolFlag>of();
-
-                    case WasmModule.IndexedGlobal.Import import_ ->
-                        List.of(SymbolFlag.UNDEFINED, SymbolFlag.EXPLICIT_NAME);
-                };
-                return new SymbolInfo.Global(
-                    flags,
-                    global.globalIndex(),
-                    global.name()
+        for (var dataSegment : module.dataSegments()) {
+            for (var dataSymbol : dataSegment.symbols()) {
+                var symbolInfo = new SymbolInfo.Data(List.of(), dataSymbol);
+                memoryAddressToSymbolIndex.put(
+                    new WasmMemoryAddress(dataSymbol.dataSegmentIndex(), dataSymbol.offset()),
+                    new WasmSymbolIndex(symbolInfos.size())
                 );
-            });
+                symbolInfos.add(symbolInfo);
+            }
+        }
 
-        var symbolInfos = Stream.<Stream<? extends SymbolInfo>>of(functionSymbols, dataSymbols, globalSymbols)
-            .<SymbolInfo>flatMap(x -> x)
-            .toList();
+        for (var global : module.indexedGlobals()) {
+            var flags = switch (global) {
+                case WasmModule.IndexedGlobal.Definition definition ->
+                    List.<SymbolFlag>of();
+
+                case WasmModule.IndexedGlobal.Import import_ ->
+                    List.of(SymbolFlag.UNDEFINED, SymbolFlag.EXPLICIT_NAME);
+            };
+            var symbolInfo = new SymbolInfo.Global(
+                flags,
+                global.globalIndex(),
+                global.name()
+            );
+            symbolInfos.add(symbolInfo);
+        }
 
-        return new SymbolTable(symbolInfos, functionSymbolIndexOffset);
+        return new SymbolTable(
+            symbolInfos,
+            functionSymbolIndexOffset,
+            memoryAddressToSymbolIndex
+        );
     }
 
     private sealed interface SymbolInfo {
@@ -268,19 +340,19 @@ public class WasmBinaryFormatLinking {
         return asInt;
     }
 
-    private static void writeFlags(List<SymbolFlag> flags, BinaryWriter writer) {
-        Leb128Encoding.encodeUnsignedInt32(flagsToInt(flags), writer);
+    private static void writeFlags(List<SymbolFlag> flags, WasmBinaryWriter writer) {
+        writer.writeUnsignedInt32(flagsToInt(flags));
     }
 
-    private static void writeDataSegmentIndex(WasmDataSegmentIndex dataSegmentIndex, BinaryWriter writer) {
-        Leb128Encoding.encodeUnsignedInt32(dataSegmentIndex.value(), writer);
+    private static void writeDataSegmentIndex(WasmDataSegmentIndex dataSegmentIndex, WasmBinaryWriter writer) {
+        writer.writeUnsignedInt32(dataSegmentIndex.value());
     }
 
-    private static void writeSymbolIndex(WasmSymbolIndex symbolIndex, BinaryWriter writer) {
-        Leb128Encoding.encodeUnsignedInt32(symbolIndex.value(), writer);
+    private static void writeSymbolIndex(WasmSymbolIndex symbolIndex, WasmBinaryWriter writer) {
+        writer.writeUnsignedInt32(symbolIndex.value());
     }
 
-    private static void writeAlignment(WasmAlignment alignment, BinaryWriter writer) {
-        Leb128Encoding.encodeUnsignedInt32(alignment.alignment(), writer);
+    private static void writeAlignment(WasmAlignment alignment, WasmBinaryWriter writer) {
+        writer.writeUnsignedInt32(alignment.alignment());
     }
 }
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatModules.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatModules.java
index f8a91ae3..b1b35c9d 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatModules.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatModules.java
@@ -12,13 +12,11 @@ import java.io.OutputStream;
 import java.util.HexFormat;
 import java.util.List;
 
-import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatConventions.writeVec;
 import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatInstructions.writeExpression;
-import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatLinking.writeLinkingSection;
+import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatLinking.*;
 import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatNameSection.writeNameSection;
 import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatSize.writeSize;
 import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatTypes.*;
-import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatValues.writeString;
 
 public class WasmBinaryFormatModules {
     // Corresponds to https://webassembly.github.io/spec/core/binary/modules.html
@@ -28,20 +26,20 @@ public class WasmBinaryFormatModules {
 
     // == Indices ==
 
-    static void writeTypeIndex(WasmTypeIndex typeIndex, BinaryWriter writer) {
-        Leb128Encoding.encodeUnsignedInt32(typeIndex.value(), writer);
+    static void writeTypeIndex(WasmTypeIndex typeIndex, WasmBinaryWriter writer) {
+        writer.writeUnsignedInt32(typeIndex.value());
     }
 
-    static void writeFuncIndex(WasmFuncIndex funcIndex, BinaryWriter writer) {
-        Leb128Encoding.encodeUnsignedInt32(funcIndex.value(), writer);
+    static void writeFuncIndex(WasmFuncIndex funcIndex, WasmBinaryWriter writer) {
+        writer.writeUnsignedInt32(funcIndex.value());
     }
 
-    static void writeGlobalIndex(WasmGlobalIndex globalIndex, BinaryWriter writer) {
-        Leb128Encoding.encodeUnsignedInt32(globalIndex.value(), writer);
+    static void writeGlobalIndex(WasmGlobalIndex globalIndex, WasmBinaryWriter writer) {
+        writer.writeUnsignedInt32(globalIndex.value());
     }
 
-    static void writeLocalIndex(WasmLocalIndex localIndex, BinaryWriter writer) {
-        Leb128Encoding.encodeUnsignedInt32(localIndex.value(), writer);
+    static void writeLocalIndex(WasmLocalIndex localIndex, WasmBinaryWriter writer) {
+        writer.writeUnsignedInt32(localIndex.value());
     }
 
     // == Sections ==
@@ -51,7 +49,7 @@ public class WasmBinaryFormatModules {
     }
 
     static void writeSection(
-        SectionId sectionId,
+        WasmSectionId sectionId,
         BinaryWriter writer,
         Write writeContent
     ) throws IOException {
@@ -61,43 +59,20 @@ public class WasmBinaryFormatModules {
         // * a one-byte section ID
         // * the u32 size of the contents, in bytes
         // * the actual contents
-        writer.writeByte(sectionId.id);
+        writer.writeByte(sectionId.id());
 
         writeSize(writer, writeContent::write);
     }
 
-    enum SectionId {
-        CUSTOM(0),
-        TYPE(1),
-        IMPORT(2),
-        FUNCTION(3),
-        TABLE(4),
-        MEMORY(5),
-        GLOBAL(6),
-        EXPORT(7),
-        START(8),
-        ELEMENT(9),
-        CODE(10),
-        DATA(11),
-        DATA_COUNT(12),
-        TAG(13);
-
-        private final byte id;
-
-        SectionId(int id) {
-            this.id = (byte) id;
-        }
-    }
-
     // == Custom Section ==
 
     static void writeCustomSection(
         String name,
-        BinaryWriter writer,
+        WasmBinaryWriter writer,
         Write writeContent
     ) throws IOException {
-        writeSection(SectionId.CUSTOM, writer, () -> {
-            writeString(name, writer);
+        writer.writeSection(WasmSectionId.CUSTOM, () -> {
+            writer.writeString(name);
             writeContent.write();
         });
     }
@@ -106,14 +81,13 @@ public class WasmBinaryFormatModules {
 
     private static void writeTypeSection(
         OrderedPSet<WasmFuncType> types,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) throws IOException {
         if (types.size() > 0) {
-            writeSection(SectionId.TYPE, writer, () -> {
-                writeVec(
+            writer.writeSection(WasmSectionId.TYPE, () -> {
+                writer.writeVec(
                     types,
-                    type -> writeFuncType(type, writer),
-                    writer
+                    type -> writeFuncType(type, writer)
                 );
             });
         }
@@ -124,14 +98,13 @@ public class WasmBinaryFormatModules {
     private static void writeImportSection(
         WasmModule module,
         WasmIndexTable indexTable,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) throws IOException {
         if (module.imports().size() > 0) {
-            writeSection(SectionId.IMPORT, writer, () -> {
-                writeVec(
+            writer.writeSection(WasmSectionId.IMPORT, () -> {
+                writer.writeVec(
                     module.imports(),
-                    import_ -> writeImport(import_, indexTable, writer),
-                    writer
+                    import_ -> writeImport(import_, indexTable, writer)
                 );
             });
         }
@@ -140,17 +113,17 @@ public class WasmBinaryFormatModules {
     private static void writeImport(
         WasmImport import_,
         WasmIndexTable indexTable,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) {
-        writeString(import_.moduleName(), writer);
-        writeString(import_.entityName(), writer);
+        writer.writeString(import_.moduleName());
+        writer.writeString(import_.entityName());
         writeImportDescriptor(import_.descriptor(), indexTable, writer);
     }
 
     private static void writeImportDescriptor(
         WasmImportDescriptor descriptor,
         WasmIndexTable indexTable,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) {
         switch (descriptor) {
             case WasmImportDescriptor.Func func -> {
@@ -178,17 +151,16 @@ public class WasmBinaryFormatModules {
     private static void writeFunctionSection(
         WasmModule module,
         WasmIndexTable indexTable,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) throws IOException {
         if (module.functions().size() > 0) {
-            writeSection(SectionId.FUNCTION, writer, () -> {
-                writeVec(
+            writer.writeSection(WasmSectionId.FUNCTION, () -> {
+                writer.writeVec(
                     module.functions(),
                     function -> writeTypeIndex(
                         indexTable.typeIndex(function.type()),
                         writer
-                    ),
-                    writer
+                    )
                 );
             });
         }
@@ -198,38 +170,36 @@ public class WasmBinaryFormatModules {
 
     private static void writeTableSection(
         WasmModule module,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     )  throws IOException {
         if (module.tables().size() > 0) {
-            writeSection(SectionId.TABLE, writer, () -> {
-                writeVec(
+            writer.writeSection(WasmSectionId.TABLE, () -> {
+                writer.writeVec(
                     module.tables(),
-                    table -> writeTable(table, writer),
-                    writer
+                    table -> writeTable(table, writer)
                 );
             });
         }
     }
 
-    private static void writeTable(WasmTable table, BinaryWriter writer) {
+    private static void writeTable(WasmTable table, WasmBinaryWriter writer) {
         writeTableType(table.type(), writer);
     }
 
     // == Memory Section ==
 
-    private static void writeMemorySection(WasmModule module, BinaryWriter writer) throws IOException {
+    private static void writeMemorySection(WasmModule module, WasmBinaryWriter writer) throws IOException {
         if (module.memories().size() > 0) {
-            writeSection(SectionId.MEMORY, writer, () -> {
-                writeVec(
+            writer.writeSection(WasmSectionId.MEMORY, () -> {
+                writer.writeVec(
                     module.memories(),
-                    memory -> writeMemory(memory, writer),
-                    writer
+                    memory -> writeMemory(memory, writer)
                 );
             });
         }
     }
 
-    private static void writeMemory(WasmMemory memory, BinaryWriter writer) {
+    private static void writeMemory(WasmMemory memory, WasmBinaryWriter writer) {
         writeMemoryType(memory.type(), writer);
     }
 
@@ -237,14 +207,13 @@ public class WasmBinaryFormatModules {
 
     private static void writeGlobalSection(
         WasmModule module,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) throws IOException {
         if (module.globals().size() > 0) {
-            writeSection(SectionId.GLOBAL, writer, () -> {
-                writeVec(
+            writer.writeSection(WasmSectionId.GLOBAL, () -> {
+                writer.writeVec(
                     module.globals(),
-                    global -> writeGlobal(global, writer),
-                    writer
+                    global -> writeGlobal(global, writer)
                 );
             });
         }
@@ -252,7 +221,7 @@ public class WasmBinaryFormatModules {
 
     private static void writeGlobal(
         WasmGlobal global,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) throws IOException {
         writeGlobalType(global.type(), writer);
         writeExpression(global.init(), writer);
@@ -262,14 +231,13 @@ public class WasmBinaryFormatModules {
 
     private static void writeElementSection(
         WasmModule module,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) throws IOException {
         if (module.elementSegments().size() > 0) {
-            writeSection(SectionId.ELEMENT, writer, () -> {
-                writeVec(
+            writer.writeSection(WasmSectionId.ELEMENT, () -> {
+                writer.writeVec(
                     module.elementSegments(),
-                    elementSegment -> writeElementSegment(elementSegment, writer),
-                    writer
+                    elementSegment -> writeElementSegment(elementSegment, writer)
                 );
             });
         }
@@ -277,62 +245,70 @@ public class WasmBinaryFormatModules {
 
     private static void writeElementSegment(
         WasmElementSegment elementSegment,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) throws IOException {
-        Leb128Encoding.encodeUnsignedInt32(0x00, writer);
+        writer.writeUnsignedInt32(0x00);
         writeExpression(new WasmExpression(List.of(new WasmI32Const(0))), writer);
-        writeVec(
+        writer.writeVec(
             elementSegment.elements(),
-            element -> writeFuncIndex(element, writer),
-            writer
+            element -> writeFuncIndex(element, writer)
         );
     }
 
     // == Code Section ==
 
-    private static void writeCodeSection(WasmModule module, BinaryWriter writer) throws IOException {
+    private static void writeCodeSection(
+        WasmModule module,
+        WasmBinaryWriter writer
+    ) throws IOException {
         if (module.functions().size() > 0) {
-            writeSection(SectionId.CODE, writer, () -> {
-                writeVec(
+            writer.writeSection(WasmSectionId.CODE, () -> {
+                writer.writeVec(
                     module.functions(),
-                    function -> writeCode(function, writer),
-                    writer
+                    function -> writeCode(function, writer)
                 );
             });
         }
     }
 
-    private static void writeCode(WasmFunction function, BinaryWriter writer) throws IOException {
-        writeSize(writer, () -> {
+    private static void writeCode(
+        WasmFunction function,
+        WasmBinaryWriter writer
+    ) throws IOException {
+        writer.writeSize(() -> {
             writeFunction(function, writer);
         });
     }
 
-    private static void writeFunction(WasmFunction function, BinaryWriter writer) throws IOException {
-        writeVec(
+    private static void writeFunction(
+        WasmFunction function,
+        WasmBinaryWriter writer
+    ) throws IOException {
+        writer.writeVec(
             function.locals(),
             local -> {
-                Leb128Encoding.encodeUnsignedInt32(1, writer);
+                writer.writeUnsignedInt32(1);
                 writeValueType(local.type(), writer);
-            },
-            writer
+            }
         );
         writeExpression(function.body(), writer);
     }
 
     // == Data Section ==
 
-    private static void writeDataSection(WasmModule module, BinaryWriter writer) throws IOException {
+    private static void writeDataSection(WasmModule module, WasmBinaryWriter writer) throws IOException {
         if (module.dataSegments().size() > 0) {
-            writeSection(SectionId.DATA, writer, () -> {
-                writeVec(
+            writer.writeSection(WasmSectionId.DATA, () -> {
+                writer.writeVec(
                     module.dataSegments(),
                     dataSegment -> {
-                        Leb128Encoding.encodeUnsignedInt32(0x00, writer);
-                        writeExpression(dataSegment.offset(), writer);
-                        writeVec(dataSegment.init(), writer);
-                    },
-                    writer
+                        writer.writeUnsignedInt32(0x00);
+                        writeExpression(
+                            dataSegment.offset(),
+                            writer
+                        );
+                        writer.writeVec(dataSegment.init());
+                    }
                 );
             });
         }
@@ -346,7 +322,7 @@ public class WasmBinaryFormatModules {
     public static void serializeModule(WasmModule module, OutputStream outputStream) throws IOException {
         var indexTable = WasmIndexTable.fromModule(module);
 
-        var writer = new BinaryWriter();
+        var writer = new WasmBinaryWriter();
         writer.writeBytes(WASM_MAGIC);
         writer.writeBytes(WASM_VERSION);
         writeTypeSection(module.types(), writer);
@@ -359,7 +335,7 @@ public class WasmBinaryFormatModules {
         writeCodeSection(module, writer);
         writeDataSection(module, writer);
         writeNameSection(module, indexTable, writer);
-        writeLinkingSection(module, indexTable, writer);
+        writeLinkingSections(module, writer);
 
         outputStream.write(writer.toBytes());
     }
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatNameSection.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatNameSection.java
index e233cb17..63672039 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatNameSection.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatNameSection.java
@@ -1,16 +1,12 @@
 package org.shedlang.compiler.backends.wasm.structure.binary;
 
-import org.shedlang.compiler.backends.wasm.structure.BinaryWriter;
 import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmLocal;
 import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmModule;
 
 import java.io.IOException;
 import java.util.stream.Stream;
 
-import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatConventions.writeVec;
 import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatModules.*;
-import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatSize.writeSize;
-import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatValues.writeString;
 
 public class WasmBinaryFormatNameSection {
     // Corresponds to https://webassembly.github.io/spec/core/appendix/custom.html#name-section
@@ -25,7 +21,7 @@ public class WasmBinaryFormatNameSection {
     static void writeNameSection(
         WasmModule module,
         WasmIndexTable indexTable,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) throws IOException {
         writeCustomSection("name", writer, () -> {
             writeFunctionNameSubsection(module, writer);
@@ -38,12 +34,12 @@ public class WasmBinaryFormatNameSection {
 
     private static void writeNameSubsection(
         NameSubsectionId sectionId,
-        BinaryWriter writer,
+        WasmBinaryWriter writer,
         WasmBinaryFormatModules.Write writeContent
     ) throws IOException {
         writer.writeByte(sectionId.id);
 
-        writeSize(writer, writeContent::write);
+        writer.writeSize(writeContent::write);
     }
 
     private enum NameSubsectionId {
@@ -61,15 +57,14 @@ public class WasmBinaryFormatNameSection {
 
     // == Function Names ==
 
-    private static void writeFunctionNameSubsection(WasmModule module, BinaryWriter writer) throws IOException {
+    private static void writeFunctionNameSubsection(WasmModule module, WasmBinaryWriter writer) throws IOException {
         writeNameSubsection(NameSubsectionId.FUNCTION_NAMES, writer, () -> {
-            writeVec(
+            writer.writeVec(
                 module.indexedFunctions(),
                 function -> {
                     writeFuncIndex(function.funcIndex(), writer);
-                    writeString(function.name(), writer);
-                },
-                writer
+                    writer.writeString(function.name());
+                }
             );
         });
     }
@@ -79,10 +74,10 @@ public class WasmBinaryFormatNameSection {
     private static void writeLocalNameSubsection(
         WasmModule module,
         WasmIndexTable indexTable,
-        BinaryWriter writer
+        WasmBinaryWriter writer
     ) throws IOException {
         writeNameSubsection(NameSubsectionId.LOCAL_NAMES, writer, () -> {
-            writeVec(
+            writer.writeVec(
                 module.indexedFunctionDefinitions(),
                 indexedFunction -> {
                     writeFuncIndex(indexedFunction.funcIndex(), writer);
@@ -94,31 +89,28 @@ public class WasmBinaryFormatNameSection {
                         function.locals().stream()
                     ).map(WasmLocal::name).toList();
 
-                    writeVec(
+                    writer.writeVec(
                         names,
                         (nameIndex, name) -> {
-                            Leb128Encoding.encodeUnsignedInt32(nameIndex, writer);
-                            writeString(name, writer);
-                        },
-                        writer
+                            writer.writeUnsignedInt32(nameIndex);
+                            writer.writeString(name);
+                        }
                     );
-                },
-                writer
+                }
             );
         });
     }
 
     // == Global Names ==
 
-    private static void writeGlobalNameSubsection(WasmModule module, BinaryWriter writer) throws IOException {
+    private static void writeGlobalNameSubsection(WasmModule module, WasmBinaryWriter writer) throws IOException {
         writeNameSubsection(NameSubsectionId.GLOBAL_NAMES, writer, () -> {
-            writeVec(
+            writer.writeVec(
                 module.indexedGlobals(),
                 global -> {
                     writeGlobalIndex(global.globalIndex(), writer);
-                    writeString(global.name(), writer);
-                },
-                writer
+                    writer.writeString(global.name());
+                }
             );
         });
     }
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatTypes.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatTypes.java
index 97a8e7db..2ec737f5 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatTypes.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatTypes.java
@@ -1,13 +1,10 @@
 package org.shedlang.compiler.backends.wasm.structure.binary;
 
-import org.shedlang.compiler.backends.wasm.structure.BinaryWriter;
 import org.shedlang.compiler.backends.wasm.structure.ast.types.*;
 
 import java.io.IOException;
 import java.util.List;
 
-import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatConventions.writeVec;
-
 public class WasmBinaryFormatTypes {
     // Corresponds to https://webassembly.github.io/spec/core/binary/types.html
 
@@ -16,19 +13,19 @@ public class WasmBinaryFormatTypes {
 
     // == Number Types ==
 
-    static void writeNumberType(WasmNumberType type, BinaryWriter writer) {
+    static void writeNumberType(WasmNumberType type, WasmBinaryWriter writer) {
         var encoding = switch (type) {
             case I32 -> 0x7f;
             case I64 -> 0x7e;
             case F32 -> 0x7d;
             case F64 -> 0x7c;
         };
-        writer.writeByte((byte) encoding);
+        writer.writeByte(encoding);
     }
 
     // == Reference Types ==
 
-    static void writeReferenceType(WasmReferenceType type, BinaryWriter writer) {
+    static void writeReferenceType(WasmReferenceType type, WasmBinaryWriter writer) {
         var encoding = switch (type) {
             case FUNC_REF -> 0x70;
             case EXTERN_REF -> 0x6f;
@@ -38,7 +35,7 @@ public class WasmBinaryFormatTypes {
 
     // == Value Types ==
 
-    static void writeValueType(WasmValueType type, BinaryWriter writer) {
+    static void writeValueType(WasmValueType type, WasmBinaryWriter writer) {
         switch (type) {
             case WasmValueType.Number number -> {
                 writeNumberType(number.type(), writer);
@@ -46,51 +43,50 @@ public class WasmBinaryFormatTypes {
         }
     }
 
-    private static void writeValueTypeVector(List<WasmValueType> types, BinaryWriter writer) throws IOException {
-        writeVec(
+    private static void writeValueTypeVector(List<WasmValueType> types, WasmBinaryWriter writer) throws IOException {
+        writer.writeVec(
             types,
-            type -> writeValueType(type, writer),
-            writer
+            type -> writeValueType(type, writer)
         );
     }
 
     // == Function Types ==
 
-    static void writeFuncType(WasmFuncType type, BinaryWriter writer) throws IOException {
-        writer.writeByte((byte) 0x60);
+    static void writeFuncType(WasmFuncType type, WasmBinaryWriter writer) throws IOException {
+        writer.writeByte(0x60);
         writeValueTypeVector(type.params(), writer);
         writeValueTypeVector(type.results(), writer);
     }
 
     // == Limits ==
 
-    static void writeLimits(WasmLimits limits, BinaryWriter writer) {
+    static void writeLimits(WasmLimits limits, WasmBinaryWriter writer) {
         if (limits.max().isPresent()) {
             writer.writeByte(0x01);
-            Leb128Encoding.encodeUnsignedInt32(limits.min(), writer);
-            Leb128Encoding.encodeUnsignedInt32(limits.max().getAsInt(), writer);
+            writer.writeUnsignedInt32(limits.min());
+            writer.writeUnsignedInt32(limits.max().getAsInt());
         } else {
             writer.writeByte(0x00);
-            Leb128Encoding.encodeUnsignedInt32(limits.min(), writer);
+            writer.writeUnsignedInt32(limits.min());
         }
     }
 
     // == Memory Types ==
 
-    static void writeMemoryType(WasmMemoryType type, BinaryWriter writer) {
+    static void writeMemoryType(WasmMemoryType type, WasmBinaryWriter writer) {
         writeLimits(type.limits(), writer);
     }
 
     // == Table Types ==
 
-    static void writeTableType(WasmTableType type, BinaryWriter writer) {
+    static void writeTableType(WasmTableType type, WasmBinaryWriter writer) {
         writeReferenceType(type.elementType(), writer);
         writeLimits(type.limits(), writer);
     }
 
     // == Global Types ==
 
-    static void writeGlobalType(WasmGlobalType type, BinaryWriter writer) {
+    static void writeGlobalType(WasmGlobalType type, WasmBinaryWriter writer) {
         writeValueType(type.valueType(), writer);
         var mutabilityEncoding = switch (type.mutability()) {
             case MUTABLE -> 0x01;
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryWriter.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryWriter.java
new file mode 100644
index 00000000..0857f4f7
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryWriter.java
@@ -0,0 +1,108 @@
+package org.shedlang.compiler.backends.wasm.structure.binary;
+
+import org.shedlang.compiler.backends.wasm.structure.BinaryWriter;
+import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmMemoryAddress;
+
+import java.io.IOException;
+import java.util.*;
+
+public class WasmBinaryWriter {
+    private final BinaryWriter writer = new BinaryWriter();
+    private final Map<Integer, List<WasmRelocationEntry>> relocationEntries = new HashMap<>();
+    private int sectionIndex = -1;
+    private int sectionContentsStart = -1;
+
+    public void writeByte(int value) {
+        writer.writeByte(value);
+    }
+
+    public void writeBytes(byte[] bytes) {
+        writer.writeBytes(bytes);
+    }
+
+    public void writeUnsignedInt32(int value) {
+        Leb128Encoding.encodeUnsignedInt32(value, writer);
+    }
+
+    public void writePaddedUnsignedInt32(int value) {
+        Leb128Encoding.encodePaddedUnsignedInt32(value, writer);
+    }
+
+    public void writeRelocatableUnsignedInt32(WasmRelocationType relocationType, WasmMemoryAddress index) {
+        // TODO: handle relocatable values in non-CODE sections
+
+        var sectionContentsOffset = writer.position() - sectionContentsStart;
+        writePaddedUnsignedInt32(0);
+
+        if (!relocationEntries.containsKey(sectionIndex)) {
+            relocationEntries.put(sectionIndex, new ArrayList<>());
+        }
+        relocationEntries.get(sectionIndex).add(new WasmRelocationEntry(
+            sectionIndex,
+            relocationType,
+            sectionContentsOffset,
+            index
+        ));
+    }
+
+    public void writeSignedInt32(int value) {
+        Leb128Encoding.encodeSignedInt32(value, writer);
+    }
+
+    public void writeSignedInt64(long value) {
+        Leb128Encoding.encodeSignedInt64(value, writer);
+    }
+
+    public void writeString(String value) {
+        WasmBinaryFormatValues.writeString(value, writer);
+    }
+
+    // TODO: extract write interface
+    public void writeSection(WasmSectionId sectionId, WasmBinaryFormatModules.Write writeContents) throws IOException {
+        sectionIndex++;
+        WasmBinaryFormatModules.writeSection(sectionId, writer, () -> {
+            sectionContentsStart = writer.position();
+            writeContents.write();
+        });
+    }
+
+    public <T> void writeVec(
+        Collection<T> vec,
+        WasmBinaryFormatConventions.WriteElement<T> writeElement
+    ) throws IOException {
+        WasmBinaryFormatConventions.writeVec(
+            vec,
+            writeElement,
+            writer
+        );
+    }
+
+    public <T> void writeVec(
+        List<T> vec,
+        WasmBinaryFormatConventions.WriteIndexedElement<T> writeElement
+    ) throws IOException {
+        WasmBinaryFormatConventions.writeVec(
+            vec,
+            writeElement,
+            writer
+        );
+    }
+
+    public void writeVec(byte[] vec) throws IOException {
+        WasmBinaryFormatConventions.writeVec(vec, writer);
+    }
+
+    public void writeSize(
+        WasmBinaryFormatSize.Write writeContents
+    ) throws IOException {
+        WasmBinaryFormatSize.writeSize(writer, writeContents);
+    }
+
+    public Map<Integer, List<WasmRelocationEntry>> relocationEntries() {
+        return relocationEntries;
+    }
+
+    public byte[] toBytes() {
+        return writer.toBytes();
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmRelocationEntry.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmRelocationEntry.java
new file mode 100644
index 00000000..fa854748
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmRelocationEntry.java
@@ -0,0 +1,11 @@
+package org.shedlang.compiler.backends.wasm.structure.binary;
+
+import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmMemoryAddress;
+
+public record WasmRelocationEntry(
+    int sectionIndex,
+    WasmRelocationType type,
+    int sectionContentsOffset,
+    WasmMemoryAddress index
+) {
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmRelocationType.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmRelocationType.java
new file mode 100644
index 00000000..1ae3b3dc
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmRelocationType.java
@@ -0,0 +1,39 @@
+package org.shedlang.compiler.backends.wasm.structure.binary;
+
+public enum WasmRelocationType {
+    FUNCTION_INDEX_LEB(0, false),
+    TABLE_INDEX_SLEB(1, true),
+    TABLE_INDEX_I32(2, true),
+    MEMORY_ADDR_LEB(3, false),
+    MEMORY_ADDR_SLEB(4, true),
+    MEMORY_ADDR_I32(5, true),
+    TYPE_INDEX_LEB(6, false),
+    GLOBAL_INDEX_LEB(7, false),
+    FUNCTION_OFFSET_I32(8, true),
+    SECTION_OFFSET_I32(9, true),
+    TAG_INDEX_LEB(10, false),
+    GLOBAL_INDEX_I32(13, true),
+    MEMORY_ADDR_LEB64(14, false),
+    MEMORY_ADDR_SLEB64(15, true),
+    MEMORY_ADDR_I64(16, true),
+    MEMORY_ADDR_REL_SLEB64(17, true),
+    TABLE_INDEX_SLEB64(18, true),
+    TABLE_INDEX_I64(19, true),
+    TABLE_NUMBER_LEB(20, false);
+
+    private final byte id;
+    private final boolean isSigned;
+
+    WasmRelocationType(int id, boolean isSigned) {
+        this.id = (byte) id;
+        this.isSigned = isSigned;
+    }
+
+    public byte id() {
+        return id;
+    }
+
+    public boolean isSigned() {
+        return isSigned;
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmSectionId.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmSectionId.java
new file mode 100644
index 00000000..8590d41f
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmSectionId.java
@@ -0,0 +1,28 @@
+package org.shedlang.compiler.backends.wasm.structure.binary;
+
+public enum WasmSectionId {
+    CUSTOM(0),
+    TYPE(1),
+    IMPORT(2),
+    FUNCTION(3),
+    TABLE(4),
+    MEMORY(5),
+    GLOBAL(6),
+    EXPORT(7),
+    START(8),
+    ELEMENT(9),
+    CODE(10),
+    DATA(11),
+    DATA_COUNT(12),
+    TAG(13);
+
+    private final byte id;
+
+    WasmSectionId(int id) {
+        this.id = (byte) id;
+    }
+
+    public byte id() {
+        return id;
+    }
+}