Phase 1 Projects

Two projects. Project 1 (dynamic string / strsplit) locks in your grasp of strings, memory, and the safe <string.h> patterns. Project 2 (bytecode VM) exercises structs, unions, switch dispatch, and gives you a small artifact you’ll keep referring back to for years. Both should be ASan/UBSan-clean; both go under Git with a proper README.

Do Project 1 in weeks 1-2, Project 2 in weeks 3-4. If Project 2 slips into M3, that’s acceptable — don’t compromise on quality to hit the deadline.

Project 1: dstr — Dynamic String + strsplit

Goal: implement a length-prefixed heap-allocated dynamic string type with the essential operations, plus a strsplit that returns an owned array of dynamic strings. Everything ASan-clean and no use of unsafe <string.h> functions.

API (include/dstr.h)

#ifndef DSTR_H
#define DSTR_H
#include <stddef.h>
#include <stdbool.h>

typedef struct dstr dstr;   // opaque; you decide the layout in dstr.c

dstr *dstr_new(void);                          // empty string
dstr *dstr_from_cstr(const char *cstr);        // copy of C string
void  dstr_free(dstr *s);

size_t dstr_len(const dstr *s);
const char *dstr_cstr(const dstr *s);          // null-terminated view

bool  dstr_append_cstr(dstr *s, const char *cstr);
bool  dstr_append_char(dstr *s, char c);
bool  dstr_appendf(dstr *s, const char *fmt, ...);   // snprintf-based

bool  dstr_eq(const dstr *a, const dstr *b);
int   dstr_cmp(const dstr *a, const dstr *b);

/* Splits input by `delim` character. Returns array of dstr* of length *n_out.
 * Caller frees the array via dstr_split_free(). */
dstr **dstr_split(const char *input, char delim, size_t *n_out);
void   dstr_split_free(dstr **arr, size_t n);

#endif

Implementation Constraints

1. No strcpy, strcat, sprintf, gets, strtok. Use snprintf, memcpy, and your own bounded copies.

2. Handle allocation failure. Every function returning a pointer or bool must correctly propagate OOM. dstr_append* returns false on failure; the string must remain in a valid state (either unchanged, or with the fields consistent so dstr_free works).

3. Grow the buffer geometrically (typically 2×) on append, capped by an implementation limit. Track cap separately from len.

4. Flexible array member is encouraged for the struct layout — that’s exactly the FAM pattern from 03_structs_unions_bitfields.md. Alternative: struct with char *data — also fine, more allocations.

5. The struct must be opaque — the type dstr should be forward-declared in the header and defined only in dstr.c. Users touch it only through the API.

Tests (tests/test_dstr.c)

Minimum coverage:

• dstr_new, dstr_free — no leak.

• dstr_from_cstr("hello") — length 5, cstr matches.

• Append 10000 characters one at a time — length correct.

• dstr_appendf("%d-%s", 42, "x") — produces "42-x".

• dstr_split("a,,b,c", ',', &n) — returns 4 strings including one empty. Free correctly.

• dstr_split("", ',', &n) — what should this return? Document and test.

• Trigger OOM by wrapping malloc (a #define malloc my_malloc in the test file that fails on a counter) — verify no leaks and no crashes.

Acceptance Criteria

1. make clean && make with the strict flag set + -fsanitize=address,undefined → zero warnings.

2. ./build/test_dstr prints test results, exits 0, ASan/UBSan clean.

3. README.md documents the API, the ownership rules, and one “design decision” section explaining your struct layout choice.

4. compile_commands.json present (via bear -- make or CMake).

5. dstr struct is opaque; nothing outside dstr.c reaches into its fields.

Time Estimate

10-15 hours across ~2 weeks. Move fast on the API, slower on the tests and edge cases.

Project 2: tinyvm — A Bytecode VM in <phone_number_or_numberic_id_or_random_id_15> LOC

Goal: build a tiny stack-based virtual machine that executes bytecode you hand-assemble. This exercises structs, tagged unions, switch dispatch, and file I/O in a coherent artifact. It also plants a seed for what you’ll do in Phase 8-9 (SIMD kernels and JITs).

The ISA (Instruction Set)

Stack-based, integer only. About 16 opcodes:

Opcode	Args	Stack effect	Description
HALT	—	—	Stop execution
PUSH_I	int32 imm	— → i	Push immediate
POP	—	v → —	Discard top
DUP	—	v → v v	Duplicate top
SWAP	—	a b → b a	Swap top two
ADD	—	a b → (a+b)	Signed add
SUB	—	a b → (a-b)
MUL	—	a b → (a*b)
DIV	—	a b → (a/b)	Trap on zero
NEG	—	a → -a
EQ	—	a b → (a==b)	Push 0 or 1
LT	—	a b → (a<b)
JMP	int32 offset	—	Unconditional jump
JZ	int32 offset	v → —	Jump if top is 0
PRINT	—	v → —	Print top as int
READ	—	— → v	Read int from stdin

Structure

tinyvm/
├── Makefile
├── include/
│   ├── vm.h
│   └── opcodes.h        # X-macro of opcodes
├── src/
│   ├── vm.c             # execution loop
│   ├── loader.c         # load a bytecode file
│   └── main.c
├── programs/
│   ├── fact.bc          # factorial
│   ├── fib.bc           # fibonacci
│   └── echo.bc          # read int, print it
├── tools/
│   └── assemble.py      # tiny assembler: text .asm → binary .bc
└── README.md

Core Data Types

Use the X-macro pattern from 04_preprocessor_and_macros.md:

// opcodes.h
#define OPCODES \
    X(HALT,   0) \
    X(PUSH_I, 4) \
    X(POP,    0) \
    X(DUP,    0) \
    /* ... */

typedef enum {
#define X(name, argsz) OP_##name,
    OPCODES
#undef X
    OP__COUNT
} opcode;

And for the VM:

typedef struct {
    const uint8_t *code;
    size_t         code_len;
    int32_t       *stack;
    size_t         sp;         // stack pointer (top-of-stack index)
    size_t         stack_cap;
    size_t         pc;         // program counter (byte offset)
} vm;

typedef enum {
    VM_OK, VM_HALT, VM_ERR_STACK_OVERFLOW, VM_ERR_STACK_UNDERFLOW,
    VM_ERR_DIV_ZERO, VM_ERR_BAD_OPCODE, VM_ERR_BAD_PC
} vm_result;

The Execution Loop (vm.c)

A switch on opcode inside a for loop. About 200-300 lines. The core:

for (;;) {
    if (vm->pc >= vm->code_len) return VM_ERR_BAD_PC;
    uint8_t op = vm->code[vm->pc++];
    switch (op) {
        case OP_HALT: return VM_HALT;
        case OP_PUSH_I: {
            if (vm->pc + 4 > vm->code_len) return VM_ERR_BAD_PC;
            int32_t v;
            memcpy(&v, vm->code + vm->pc, 4);   // avoid aliasing / alignment UB
            vm->pc += 4;
            if (vm->sp >= vm->stack_cap) return VM_ERR_STACK_OVERFLOW;
            vm->stack[vm->sp++] = v;
            break;
        }
        /* ... */
        default: return VM_ERR_BAD_OPCODE;
    }
}

The Assembler (tools/assemble.py)

A Python script (~50 lines) that reads .asm:

; factorial of 5
    PUSH_I 5
    PUSH_I 1     ; result = 1
loop:
    SWAP
    DUP
    JZ end
    SWAP
    DUP
    /* ... */
end:
    PRINT
    HALT

and writes a binary .bc. Python is allowed here because writing an assembler in C would double the project size for no learning gain.

Acceptance Criteria

1. make builds tinyvm with strict flags + ASan.

2. ./tinyvm programs/fact.bc prints 120 (factorial of 5) and exits 0.

3. ./tinyvm programs/fib.bc prints the 10th Fibonacci number.

4. ./tinyvm programs/echo.bc reads an int from stdin and prints it.

5. Feeding a malformed .bc file (truncated, bad opcode, out-of-range jump) produces a clean error message and non-zero exit; no crash, no ASan diagnostics.

6. Total C code excluding tests and comments is under 700 LOC (measure with cloc src/).

7. README.md documents the ISA, the file format, how to assemble and run, and one “what would I do differently” reflection paragraph.

Stretch

• Add local variables (LOAD_LOCAL k / STORE_LOCAL k with a frame pointer).

• Add function call/return (CALL / RET — requires a call stack).

• Write the VM tagged-union style with value supporting int + float + string.

• Benchmark: how many instructions per second? Compare -O0 vs -O2.

Time Estimate

15-20 hours. This is meaty. It’s also, per the community consensus, one of the highest-signal projects in intermediate C education — you touch memory, structs, dispatch, I/O, and error handling in one artifact.

What Most People Get Wrong About This Project

They try to be clever with computed-goto dispatch or JIT ideas before the basic switch-dispatch VM even works. Ship the boring version first, verify it runs three programs, then consider optimizations. The whole point is depth on the basics.

The second failure mode is ignoring the malformed-input case. Robust bytecode loaders check every jump target, every opcode, every immediate. Real VMs (LuaJIT, JVM, Wasm) have entire bytecode-verifier passes for this. You don’t need a verifier, but you do need to validate as you execute. That’s the muscle you’re building.

Definition of Done for Phase 1

• dstr project: API works, all tests pass, ASan/UBSan clean, opaque struct discipline held.

• tinyvm project: three sample programs run correctly, malformed inputs handled cleanly, under 700 LOC in src/.

• You can explain, in a five-minute whiteboard session, integer promotion, the padding of a mixed-size struct, the difference between UB and unspecified behavior, and why strncpy is not a safe strcpy.

Close Phase 1. Move to Phase 2 (pointers, memory, data structures).

---

Return to README.md · Next: ../03_pointers_and_memory/README.md (Phase 2, to be built by the M3-M4 agent)