commit ab60ce5e5c26d78e7328d3a8f7f99c54f3142e00
parent 96f2948c410b84aa05b9e575e860141a268dc8d3
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Sat, 25 Apr 2026 08:58:10 -0700
Add scheme1 bytevectors with dynamic-array semantics
Bytevectors are 24-byte HEAP-tagged wrappers pointing at a separately
allocated data buffer. Layout:
word 0 :: (length << 8) | HDR.BV
word 1 :: data_ptr (raw heap address)
word 2 :: capacity in bytes
Splitting the wrapper from the data buffer lets bv_grow reallocate the
buffer in place — no callers need to update their reference. Headroom
is provided up front: bv_capacity_for rounds the requested length up to
the next power of two (minimum 16). bv_grow then doubles capacity until
it satisfies a min_cap request, copies the live bytes via memcpy, and
patches the wrapper's data_ptr/capacity slots.
Public primitives: make-bytevector (1- and 2-arg), bytevector-length,
bytevector-u8-ref, bytevector-u8-set!, bytevector-copy (3-arg),
bytevector-copy! (5-arg), and bytevector-grow! (Scheme-extension that
forwards to bv_grow so the doubling path is testable).
Also bumps M1pp's TEXT_CAP from 256 KiB to 512 KiB and shifts text_buf
into the previously unused gap between output_buf and source_tokens.
amd64's larger backend plus scheme1's growing scope-mangled label set
overflowed the original budget; downstream BSS offsets are unchanged.
Diffstat:
14 files changed, 359 insertions(+), 2 deletions(-)
diff --git a/M1pp/M1pp.P1 b/M1pp/M1pp.P1
@@ -29,7 +29,7 @@
DEFINE M1PP_INPUT_CAP 0000040000000000
DEFINE M1PP_OUTPUT_CAP 0000040000000000
-DEFINE M1PP_TEXT_CAP 0000040000000000
+DEFINE M1PP_TEXT_CAP 0000080000000000
DEFINE M1PP_TOKENS_END 0000c00000000000
## Macro record is 296 bytes: name (16) + param_count (8) + params[16]*16 (256)
## + body_start (8) + body_end (8). MACROS_CAP fits 512 records (151552 B).
@@ -127,7 +127,7 @@ DEFINE OFF_arg_starts 8005000000000000
DEFINE OFF_arg_ends 0006000000000000
DEFINE OFF_input_buf 8006000000000000
DEFINE OFF_output_buf 8006080000000000
-DEFINE OFF_text_buf 8006100000000000
+DEFINE OFF_text_buf 80060c0000000000
DEFINE OFF_source_tokens 8006140000000000
DEFINE OFF_macros 8006200000000000
DEFINE OFF_macro_body_tokens 8046290000000000
diff --git a/scheme1/scheme1.P1pp b/scheme1/scheme1.P1pp
@@ -1808,6 +1808,293 @@
%ret
%endscope
+# Bytevectors are 24-byte HEAP-tagged wrappers pointing at a separately
+# allocated data buffer; this gives them dynamic-array semantics — capacity
+# can grow in place by reallocating just the data buffer (no need to find
+# and patch every reference to the wrapper).
+#
+# word 0 :: (length << 8) | HDR.BV ; length = hdr >> 8
+# word 1 :: data_ptr (raw heap address)
+# word 2 :: capacity in bytes
+#
+# Tagged-pointer offsets into the wrapper:
+# hdr = ld(bv, -3)
+# data_ptr = ld(bv, 5)
+# capacity = ld(bv, 13)
+#
+# bv_capacity_for(n) returns the smallest power-of-two ≥ max(n, 16) so
+# every fresh bytevector starts with at least some headroom; bv_grow then
+# doubles by repeatedly shifting until cap ≥ requested.
+
+# alloc_bytes(size=a0) -> raw addr (a0). Untagged data buffer; size is
+# rounded up to 8 to keep the next bump 8-byte-aligned.
+:alloc_bytes
+ %alignup(a0, a0, 8, t0)
+ %la(t2, &heap_next)
+ %ld(t1, t2, 0)
+ %add(t0, t1, a0)
+ %st(t0, t2, 0)
+ %mov(a0, t1)
+ %ret
+
+# bv_capacity_for(n=a0) -> next pow2 ≥ max(n, 16) (a0).
+:bv_capacity_for
+%scope bv_capacity_for
+ %li(t0, 16)
+ ::loop
+ %bltu(t0, a0, &::shift)
+ %mov(a0, t0)
+ %ret
+ ::shift
+ %shli(t0, t0, 1)
+ %b(&::loop)
+%endscope
+
+# bv_alloc(raw_len=a0) -> tagged bv (a0). Length = raw_len, capacity from
+# bv_capacity_for, data buffer uninitialized. data_ptr lives in a frame
+# slot because alloc_hdr's alignup clobbers t-regs.
+#
+# Frame: 24 bytes
+# +0 raw_len
+# +8 capacity
+# +16 data_ptr (raw)
+%fn(bv_alloc, 24, {
+ %st(a0, sp, 0)
+
+ %call(&bv_capacity_for)
+ %st(a0, sp, 8)
+ %call(&alloc_bytes)
+ %st(a0, sp, 16)
+
+ %ld(a1, sp, 0)
+ %shli(a1, a1, 8) ; hdr = (raw_len << 8) | HDR.BV (BV == 0)
+ %li(a0, 24)
+ %call(&alloc_hdr)
+
+ %ld(t0, sp, 16)
+ %st(t0, a0, 5)
+ %ld(t1, sp, 8)
+ %st(t1, a0, 13)
+})
+
+# bv_grow(bv=a0, min_cap=a1) -> bv (a0). Doubles capacity until ≥ min_cap;
+# allocates a fresh data buffer, copies the live bytes (length, not
+# capacity), and patches the wrapper's data_ptr/capacity slots in place.
+# A no-op when current capacity already satisfies min_cap.
+#
+# Frame: 32 bytes
+# +0 bv
+# +8 min_cap (input) / new_cap (during loop)
+# +16 new_data_ptr
+# +24 raw length
+%fn(bv_grow, 32, {
+ %st(a0, sp, 0)
+ %st(a1, sp, 8)
+
+ %ld(t0, a0, 13)
+ %bltu(t0, a1, &::need)
+ %ld(a0, sp, 0)
+ %eret
+
+ ::need
+ ::loop
+ %shli(t0, t0, 1)
+ %ld(t1, sp, 8)
+ %bltu(t0, t1, &::loop)
+ %st(t0, sp, 8)
+
+ %mov(a0, t0)
+ %call(&alloc_bytes)
+ %st(a0, sp, 16)
+
+ %ld(t0, sp, 0)
+ %ld(t1, t0, -3)
+ %shri(t1, t1, 8) ; raw length
+ %st(t1, sp, 24)
+ %ld(a0, sp, 16)
+ %ld(a1, t0, 5) ; old data ptr
+ %ld(a2, sp, 24)
+ %call(&memcpy)
+
+ %ld(t0, sp, 0)
+ %ld(t1, sp, 16)
+ %st(t1, t0, 5)
+ %ld(t1, sp, 8)
+ %st(t1, t0, 13)
+ %ld(a0, sp, 0)
+})
+
+# (make-bytevector len) or (make-bytevector len fill)
+%fn(prim_make_bytevector_entry, 24, {
+ # +0 args
+ # +8 fill (raw byte)
+ # +16 wrapper (saved across fill loop)
+ %st(a0, sp, 0)
+
+ %cdr(t0, a0)
+ %li(t1, %imm_val(%IMM.NIL))
+ %li(t2, 0)
+ %beq(t0, t1, &::no_fill)
+ %car(t0, t0)
+ %sari(t2, t0, 3)
+ ::no_fill
+ %st(t2, sp, 8)
+
+ %ld(a0, sp, 0)
+ %car(a0, a0)
+ %sari(a0, a0, 3)
+ %call(&bv_alloc)
+ %st(a0, sp, 16)
+
+ %ld(t0, sp, 0)
+ %car(t0, t0)
+ %sari(t0, t0, 3) ; raw_len
+ %ld(t1, sp, 8) ; fill
+ %ld(a1, sp, 16)
+ %ld(t2, a1, 5) ; data_ptr
+ %li(a1, 0)
+
+ ::fill_loop
+ %beq(a1, t0, &::fill_done)
+ %sb(t1, t2, 0)
+ %addi(t2, t2, 1)
+ %addi(a1, a1, 1)
+ %b(&::fill_loop)
+
+ ::fill_done
+ %ld(a0, sp, 16)
+})
+
+:prim_bv_length_entry
+ %car(t0, a0)
+ %ld(t1, t0, -3)
+ %shri(a0, t1, 5)
+ %ret
+
+:prim_bv_u8_ref_entry
+ %car(t0, a0)
+ %cdr(t1, a0)
+ %car(t1, t1)
+ %sari(t1, t1, 3)
+ %ld(t2, t0, 5)
+ %add(t2, t2, t1)
+ %lb(a0, t2, 0)
+ %mkfix(a0, a0)
+ %ret
+
+:prim_bv_u8_set_entry
+%scope prim_bv_u8_set
+ %car(t0, a0)
+ %cdr(t1, a0)
+ %car(t2, t1)
+ %sari(t2, t2, 3)
+ %cdr(t1, t1)
+ %car(t1, t1)
+ %sari(t1, t1, 3)
+ %ld(a0, t0, 5)
+ %add(a0, a0, t2)
+ %sb(t1, a0, 0)
+ %li(a0, %imm_val(%IMM.UNSPEC))
+ %ret
+%endscope
+
+# (bytevector-copy src start end) -> fresh bv of length end-start.
+#
+# Frame: 24 bytes
+# +0 args
+# +8 src tagged
+# +16 wrapper (saved after bv_alloc)
+%fn(prim_bv_copy_entry, 24, {
+ %st(a0, sp, 0)
+
+ %car(t0, a0)
+ %st(t0, sp, 8)
+
+ %cdr(t1, a0)
+ %car(t2, t1)
+ %sari(t2, t2, 3) ; raw start
+ %cdr(t1, t1)
+ %car(t1, t1)
+ %sari(t1, t1, 3) ; raw end
+ %sub(a0, t1, t2) ; count
+ %call(&bv_alloc)
+ %st(a0, sp, 16)
+
+ # Recompute src ptr at start; dst ptr at 0; count from new bv's hdr.
+ %ld(t0, sp, 0)
+ %cdr(t0, t0)
+ %car(t0, t0)
+ %sari(t0, t0, 3) ; raw start
+ %ld(t1, sp, 8)
+ %ld(t2, t1, 5)
+ %add(t2, t2, t0) ; src ptr
+ %ld(a3, sp, 16)
+ %ld(a2, a3, 5) ; dst ptr
+ %ld(a1, a3, -3)
+ %shri(a1, a1, 8) ; count
+
+ ::copy_loop
+ %beqz(a1, &::copy_done)
+ %lb(t0, t2, 0)
+ %sb(t0, a2, 0)
+ %addi(t2, t2, 1)
+ %addi(a2, a2, 1)
+ %addi(a1, a1, -1)
+ %b(&::copy_loop)
+
+ ::copy_done
+ %ld(a0, sp, 16)
+})
+
+# (bytevector-grow! bv min-cap) -> bv. Forwards to bv_grow; min-cap is
+# untagged at the boundary. Useful when a builder pattern wants to
+# pre-extend capacity, but also makes the doubling path testable.
+:prim_bv_grow_entry
+ %car(t0, a0)
+ %cdr(t1, a0)
+ %car(t1, t1)
+ %sari(t1, t1, 3)
+ %mov(a0, t0)
+ %mov(a1, t1)
+ %b(&bv_grow)
+
+# (bytevector-copy! dst dst-start src src-start src-end)
+:prim_bv_copy_bang_entry
+%scope prim_bv_copy_bang
+ %car(t0, a0) ; dst
+ %cdr(t1, a0)
+ %car(t2, t1)
+ %sari(t2, t2, 3) ; dst-start
+
+ %cdr(t1, t1)
+ %car(a1, t1) ; src
+ %cdr(t1, t1)
+ %car(a2, t1)
+ %sari(a2, a2, 3) ; src-start
+ %cdr(t1, t1)
+ %car(a3, t1)
+ %sari(a3, a3, 3) ; src-end
+
+ %ld(t0, t0, 5)
+ %add(t0, t0, t2) ; dst ptr
+ %ld(a1, a1, 5)
+ %add(a1, a1, a2) ; src ptr
+ %sub(a3, a3, a2) ; count
+
+ ::loop
+ %beqz(a3, &::done)
+ %lb(t1, a1, 0)
+ %sb(t1, t0, 0)
+ %addi(t0, t0, 1)
+ %addi(a1, a1, 1)
+ %addi(a3, a3, -1)
+ %b(&::loop)
+
+ ::done
+ %li(a0, %imm_val(%IMM.UNSPEC))
+ %ret
+%endscope
+
# (apply fn rest...) -- the trailing element of `rest` is a list; any
# leading elements get prepended to it. apply_build_args walks `rest` and
# returns the assembled args list; prim_apply_entry then tail-calls apply.
@@ -1879,6 +2166,13 @@
:name_bit_or "bit-or"
:name_arith_shift "arithmetic-shift"
:name_apply "apply"
+:name_make_bv "make-bytevector"
+:name_bv_length "bytevector-length"
+:name_bv_u8_ref "bytevector-u8-ref"
+:name_bv_u8_set "bytevector-u8-set!"
+:name_bv_copy "bytevector-copy"
+:name_bv_copy_b "bytevector-copy!"
+:name_bv_grow "bytevector-grow!"
# Primitive registration table. Each entry: 8-byte name_ptr (4-byte label
# ref + 4 pad), 8-byte name_len, 8-byte entry_label (4 ref + 4 pad).
@@ -1901,6 +2195,13 @@
&name_bit_or %(0) $(6) &prim_bit_or_entry %(0)
&name_arith_shift %(0) $(16) &prim_arith_shift_entry %(0)
&name_apply %(0) $(5) &prim_apply_entry %(0)
+&name_make_bv %(0) $(15) &prim_make_bytevector_entry %(0)
+&name_bv_length %(0) $(17) &prim_bv_length_entry %(0)
+&name_bv_u8_ref %(0) $(17) &prim_bv_u8_ref_entry %(0)
+&name_bv_u8_set %(0) $(18) &prim_bv_u8_set_entry %(0)
+&name_bv_copy %(0) $(15) &prim_bv_copy_entry %(0)
+&name_bv_copy_b %(0) $(16) &prim_bv_copy_bang_entry %(0)
+&name_bv_grow %(0) $(16) &prim_bv_grow_entry %(0)
:prim_table_end
:msg_usage "scheme1: usage: scheme1 SOURCE.scm" '0a' '00'
diff --git a/tests/scheme1/29-make-bv.expected-exit b/tests/scheme1/29-make-bv.expected-exit
@@ -0,0 +1 @@
+5
diff --git a/tests/scheme1/29-make-bv.scm b/tests/scheme1/29-make-bv.scm
@@ -0,0 +1,3 @@
+; make-bytevector + bytevector-length round-trip.
+(define b (make-bytevector 5 0))
+(sys-exit (bytevector-length b)) ; 5
diff --git a/tests/scheme1/30-bv-set-ref.expected-exit b/tests/scheme1/30-bv-set-ref.expected-exit
@@ -0,0 +1 @@
+48
diff --git a/tests/scheme1/30-bv-set-ref.scm b/tests/scheme1/30-bv-set-ref.scm
@@ -0,0 +1,8 @@
+; bytevector-u8-set! / bytevector-u8-ref round-trip; sum stays correct.
+(define b (make-bytevector 4 0))
+(bytevector-u8-set! b 0 7)
+(bytevector-u8-set! b 1 11)
+(bytevector-u8-set! b 2 13)
+(bytevector-u8-set! b 3 17)
+(sys-exit (+ (+ (bytevector-u8-ref b 0) (bytevector-u8-ref b 1))
+ (+ (bytevector-u8-ref b 2) (bytevector-u8-ref b 3))))
diff --git a/tests/scheme1/31-bv-fill.expected-exit b/tests/scheme1/31-bv-fill.expected-exit
@@ -0,0 +1 @@
+42
diff --git a/tests/scheme1/31-bv-fill.scm b/tests/scheme1/31-bv-fill.scm
@@ -0,0 +1,3 @@
+; 2-arg make-bytevector fills the data area with the given byte.
+(define b (make-bytevector 4 42))
+(sys-exit (bytevector-u8-ref b 2))
diff --git a/tests/scheme1/32-bv-copy.expected-exit b/tests/scheme1/32-bv-copy.expected-exit
@@ -0,0 +1 @@
+18
diff --git a/tests/scheme1/32-bv-copy.scm b/tests/scheme1/32-bv-copy.scm
@@ -0,0 +1,11 @@
+; 3-arg bytevector-copy: produces a fresh bv of length end-start.
+(define src (make-bytevector 6 0))
+(bytevector-u8-set! src 0 9)
+(bytevector-u8-set! src 1 8)
+(bytevector-u8-set! src 2 7)
+(bytevector-u8-set! src 3 6)
+(bytevector-u8-set! src 4 5)
+(bytevector-u8-set! src 5 4)
+(define c (bytevector-copy src 2 5)) ; bytes [7 6 5]
+(sys-exit (+ (+ (bytevector-u8-ref c 0) (bytevector-u8-ref c 1))
+ (bytevector-u8-ref c 2)))
diff --git a/tests/scheme1/33-bv-copy-bang.expected-exit b/tests/scheme1/33-bv-copy-bang.expected-exit
@@ -0,0 +1 @@
+6
diff --git a/tests/scheme1/33-bv-copy-bang.scm b/tests/scheme1/33-bv-copy-bang.scm
@@ -0,0 +1,10 @@
+; 5-arg bytevector-copy! — writes src[start..end) into dst at dst-start.
+(define dst (make-bytevector 5 0))
+(define src (make-bytevector 5 9))
+(bytevector-u8-set! src 1 1)
+(bytevector-u8-set! src 2 2)
+(bytevector-u8-set! src 3 3)
+(bytevector-copy! dst 0 src 1 4)
+(sys-exit (+ (bytevector-u8-ref dst 0)
+ (+ (bytevector-u8-ref dst 1)
+ (bytevector-u8-ref dst 2))))
diff --git a/tests/scheme1/34-bv-grow.expected-exit b/tests/scheme1/34-bv-grow.expected-exit
@@ -0,0 +1 @@
+46
diff --git a/tests/scheme1/34-bv-grow.scm b/tests/scheme1/34-bv-grow.scm
@@ -0,0 +1,15 @@
+; bytevector-grow! enlarges capacity in place; existing data must survive
+; the alloc + copy. Length stays unchanged.
+(define b (make-bytevector 5 0))
+(bytevector-u8-set! b 0 11)
+(bytevector-u8-set! b 1 13)
+(bytevector-u8-set! b 4 17)
+
+; Force growth past initial 16-byte capacity.
+(bytevector-grow! b 100)
+
+; Length still 5; bytes still readable.
+(sys-exit (+ (bytevector-length b)
+ (+ (+ (bytevector-u8-ref b 0) (bytevector-u8-ref b 1))
+ (bytevector-u8-ref b 4))))
+; 5 + 11 + 13 + 17 = 46
