AnachronautandClaude Opus 5
e20c9bac1f
labFind walked the index from the front, so every use of every label cost a scan of every label defined so far, each with a string compare. The cost grew with the program being built, which is what made it hurt: assembling CosmOS on the machine took 1,833,691,267 cycles against the assembler assembling itself at 57,257,133 - three times the source for thirty two times the time. Sorted and halved, the same build is 886,498,996. THE WALK WAS 52 PER CENT OF THE WHOLE ASSEMBLY, which settles a suspicion this project has carried unverified for weeks and puts a number on it. Eleven comparisons against two thousand entries where a walk averaged six hundred and seventy. The search hands back where a name WOULD go, which is what adding one needs and what a walk could never have offered, so labAdd gets its insertion point for nothing. sameText was already an ordering and did not have to change: Q is the difference at the first character that differed, and the Carry Flag from that same subtraction survives the return because nothing puts the Status register back. A name that runs out while the other carries on borrows against the other's character, which sorts the shorter first. Small programs pay about a tenth more - 57.3M to 63.5M for the assembler on itself - because adding a label now moves the tail of the index up and a short table was never expensive to walk. That is the right way round for a trade to fall. numHalve and numBack are new: a rotate right on a CIRCULAR sixteen bit register brings bit nought back in at the top, so halving means taking that bit off again, and the low half has to go down first because the mask wants B. WHICH END THE TABLE IS SORTED FROM DOES NOT MATTER. labAdd takes its insertion point from labFind, so the comparison that decides the order is the same one that searches it - turn it round and the table is built backwards and read backwards and no output changes. Tests/break.sh says so, correctly, by not noticing. Verified by CosmOS builds CosmOS and second generation staying byte identical. An indexing bug cannot hide behind a fixed point. Co-Authored-By: Claude Opus 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01E2JrLzFvuFX9fgi1LDRjrW
435 lines
11 KiB
NASM
435 lines
11 KiB
NASM
; The label table: the only thing that survives between the two passes.
|
|
;
|
|
; ---- KEPT IN ORDER, so that a lookup can halve it ----
|
|
;
|
|
; It used to be walked from the front, and that was most of the assembler. Every use of every
|
|
; label paid a scan of every label defined so far, so the cost grew with the program being
|
|
; built: assembling CosmOS on the machine took 1.83 billion cycles against the assembler's own
|
|
; 57 million - three times the source for thirty two times the time.
|
|
;
|
|
; Sorted and halved instead, it is 886 million: the walk was 52 per cent of the whole
|
|
; assembly. Small programs pay about a tenth more, because adding a label now moves the tail
|
|
; of the index up to make room and a short table was never expensive to walk. That is the
|
|
; right way round for a trade to fall.
|
|
;
|
|
; WHICH END IT IS SORTED FROM DOES NOT MATTER, and that is not carelessness. labAdd takes its
|
|
; insertion point from labFind, so the comparison that decides the order is the same one that
|
|
; searches it; turn it round and the table is built backwards and read backwards and nothing
|
|
; else can tell. Which is why breaking that comparison on purpose changes no output at all.
|
|
;
|
|
; Names are packed end to end in an arena and each index entry holds a pointer into it,
|
|
; rather than every entry carrying a field wide enough for the longest name. MEASURED on
|
|
; CosmOS, which is the biggest thing this will ever be asked to assemble: 453 labels
|
|
; averaging 11.3 characters. Packed they come to about 7,400 bytes; in 32 byte fields they
|
|
; would come to 15,400. The arena is worth the handful of extra instructions.
|
|
;
|
|
; Four bytes an index entry: two saying where the name is, two saying what it resolves to.
|
|
;
|
|
; A name is stored WITHOUT its colon, so that a definition and a use of it compare equal
|
|
; without either side having to know which it was looking at.
|
|
;
|
|
; The first pass fills this and the second only reads it. That is what makes a forward
|
|
; reference ordinary rather than special: by the time anything is emitted, every name in
|
|
; the program already has an address.
|
|
;
|
|
; Written by Anachronaut
|
|
|
|
#Program
|
|
|
|
; Empties the table.
|
|
labReset:
|
|
SETD.0 LabCount
|
|
CALL numZero
|
|
SETD.0 LabUsed
|
|
CALL numZero
|
|
SETD.0 LabNext
|
|
SETD.2 ScratchLabArena
|
|
CALL numSet
|
|
SETD.0 LabBase
|
|
SETD.2 ScratchLabIndex
|
|
CALL numSet
|
|
RET
|
|
|
|
; Adds the name at DP0, meaning the address in A and B. Q is zero if it went in.
|
|
;
|
|
; A name already in the table is refused rather than replaced: one name may mean one place,
|
|
; and quietly taking the second would move everything that referred to the first.
|
|
labAdd:
|
|
SETD.2 LabPutAddress
|
|
STA.2
|
|
INCD.2
|
|
STB.2
|
|
SETD.2 LabSubject
|
|
STD.0.2
|
|
|
|
CALL labFind
|
|
BNQ labAddFresh
|
|
SETD.0 LabTwice
|
|
CALL labComplain
|
|
BRI labAddNo
|
|
|
|
labAddFresh:
|
|
SETD.0 LabCount
|
|
SETD.2 LabLimit
|
|
CALL numCompare
|
|
BNC labAddFull ; The index is as full as it goes.
|
|
|
|
; And the arena, counting the zero that ends the name.
|
|
SETD.1 LabSubject
|
|
LDD.0.1
|
|
CALL labLength
|
|
SETD.0 LabEnd
|
|
SETD.2 LabUsed
|
|
CALL numSet
|
|
SETD.0 LabEnd
|
|
SETD.2 LabLength
|
|
CALL numAdd
|
|
SETD.0 LabRoom
|
|
SETD.2 LabEnd
|
|
CALL numCompare
|
|
BRC labAddCrowded ; The arena is smaller than where this name would end.
|
|
|
|
; ---- Room made for it where it belongs ----
|
|
;
|
|
; The index is kept in order so that looking a name up can halve the table instead of
|
|
; walking it, and labFind left LabLo at the place this name sorts to. Everything from there
|
|
; on moves up four bytes, from the END backwards so that nothing is written over before it
|
|
; has been read.
|
|
;
|
|
; It costs about a third of the table copied per label added, which against the walk it
|
|
; replaces is nothing: the walk was paid once per USE of a label and this is paid once per
|
|
; label, and there are several uses of each.
|
|
SETD.0 LabWhich
|
|
SETD.2 LabCount
|
|
CALL numSet
|
|
|
|
labAddShift:
|
|
SETD.0 LabWhich
|
|
SETD.2 LabLo
|
|
CALL numCompare
|
|
BRQ labAddPlace ; Down to where it goes, so there is nothing left to move.
|
|
|
|
; The one below this place, moved up into it.
|
|
CALL labEntryAt
|
|
SETD.1 LabEntry
|
|
LDD.1.1 ; DP1 is where it goes.
|
|
SETD.0 LabWhich
|
|
CALL numBack
|
|
CALL labEntryAt
|
|
SETD.0 LabEntry
|
|
LDD.0.0 ; DP0 is where it comes from.
|
|
|
|
INIB 0d4
|
|
labAddShiftByte:
|
|
LDA.0
|
|
STA.1
|
|
INCD.0
|
|
INCD.1
|
|
DECB
|
|
BNB labAddShiftByte
|
|
BRI labAddShift
|
|
|
|
labAddPlace:
|
|
SETD.0 LabWhich
|
|
SETD.2 LabLo
|
|
CALL numSet
|
|
CALL labEntryAt
|
|
|
|
SETD.1 LabEntry
|
|
LDD.0.1
|
|
SETD.1 LabNext
|
|
LDD.1.1
|
|
PSHD.1
|
|
POPB
|
|
POPA ; The low byte is on top, the way a pointer is pushed.
|
|
STA.0
|
|
INCD.0
|
|
STB.0
|
|
INCD.0
|
|
SETD.2 LabPutAddress
|
|
LDA.2
|
|
STA.0
|
|
INCD.0
|
|
INCD.2
|
|
LDA.2
|
|
STA.0
|
|
|
|
; And the name itself, into the arena.
|
|
SETD.1 LabNext
|
|
LDD.1.1
|
|
SETD.2 LabSubject
|
|
LDD.0.2
|
|
labAddLoop:
|
|
LDA.0
|
|
STA.1
|
|
BRA labAddCopied
|
|
INCD.0
|
|
INCD.1
|
|
BRI labAddLoop
|
|
labAddCopied:
|
|
INCD.1 ; Past the zero, which was copied with the rest.
|
|
SETD.0 LabNext
|
|
STD.1.0
|
|
|
|
SETD.0 LabUsed
|
|
SETD.2 LabLength
|
|
CALL numAdd
|
|
SETD.0 LabCount
|
|
CALL numStep
|
|
|
|
RSTA
|
|
RSTB
|
|
CCF
|
|
ADD
|
|
RET
|
|
|
|
labAddFull:
|
|
SETD.0 LabFull
|
|
CALL labComplain
|
|
BRI labAddNo
|
|
labAddCrowded:
|
|
SETD.0 LabNoRoom
|
|
CALL labComplain
|
|
labAddNo:
|
|
RSTA
|
|
INIB 0d1
|
|
CCF
|
|
ADD
|
|
RET
|
|
|
|
; Looks up the name at DP0. Q is zero if it is there, and then LabAddress is what it means.
|
|
;
|
|
; A straight walk from the front. With 453 labels and a few thousand uses of them that is
|
|
; the slowest thing the assembler does, and it is deliberately the simple version: sorting
|
|
; the table or bucketing it on the first character are both easy later, and neither is
|
|
; worth writing before anything has been measured.
|
|
labFind:
|
|
SETD.2 LabSought
|
|
STD.0.2
|
|
|
|
; ---- Halving the table rather than walking it ----
|
|
;
|
|
; The names are kept in order, so a lookup is eleven comparisons against two thousand
|
|
; entries where a walk was six hundred and seventy. THAT WAS MOST OF THE ASSEMBLER: every
|
|
; use of every label paid it, and it grew with the program being built, so assembling
|
|
; CosmOS on the machine cost 1.83 billion cycles against the assembler's own 57 million -
|
|
; three times the source for thirty two times the time.
|
|
;
|
|
; LabLo is left at the place the name WOULD go, which is what adding one needs and what a
|
|
; walk could never have handed back.
|
|
SETD.0 LabLo
|
|
CALL numZero
|
|
SETD.0 LabHi
|
|
SETD.2 LabCount
|
|
CALL numSet
|
|
|
|
labFindStep:
|
|
SETD.0 LabLo
|
|
SETD.2 LabHi
|
|
CALL numCompare
|
|
BNC labFindMissing ; Nothing left between them, so it is not here.
|
|
|
|
; The one in the middle. Adding two numbers under two thousand cannot overflow sixteen
|
|
; bits, so there is nothing to carry into.
|
|
SETD.0 LabWhich
|
|
SETD.2 LabLo
|
|
CALL numSet
|
|
SETD.0 LabWhich
|
|
SETD.2 LabHi
|
|
CALL numAdd
|
|
SETD.0 LabWhich
|
|
CALL numHalve
|
|
|
|
CALL labEntryAt
|
|
SETD.1 LabEntry
|
|
LDD.0.1
|
|
LDA.0
|
|
INCD.0
|
|
LDB.0
|
|
SETD.0 LabNamePointer
|
|
STA.0
|
|
INCD.0
|
|
STB.0
|
|
|
|
; ---- sameText is already an ordering ----
|
|
;
|
|
; Q is the difference at the first character that differed, so zero is a match - and the
|
|
; Carry Flag from that same subtraction says which way round they were, and survives the
|
|
; return because nothing puts the Status register back. A name that runs out while the
|
|
; other carries on borrows against the other's character, which sorts the shorter first,
|
|
; which is what anybody means by alphabetical.
|
|
SETD.1 LabNamePointer
|
|
LDD.0.1
|
|
SETD.1 LabSought
|
|
LDD.1.1
|
|
CALL sameText
|
|
BRQ labFindGot
|
|
BRC labFindAbove ; The one in the table is the smaller, so look above it.
|
|
|
|
SETD.0 LabHi
|
|
SETD.2 LabWhich
|
|
CALL numSet
|
|
BRI labFindStep
|
|
|
|
labFindAbove:
|
|
SETD.0 LabLo
|
|
SETD.2 LabWhich
|
|
CALL numSet
|
|
SETD.0 LabLo
|
|
CALL numStep
|
|
BRI labFindStep
|
|
|
|
labFindGot:
|
|
SETD.1 LabEntry
|
|
LDD.0.1
|
|
INCD.0
|
|
INCD.0
|
|
LDA.0
|
|
INCD.0
|
|
LDB.0
|
|
SETD.0 LabAddress
|
|
STA.0
|
|
INCD.0
|
|
STB.0
|
|
RSTA
|
|
RSTB
|
|
CCF
|
|
ADD
|
|
RET
|
|
|
|
labFindMissing:
|
|
RSTA
|
|
INIB 0d1
|
|
CCF
|
|
ADD
|
|
RET
|
|
|
|
; Where entry number LabWhich is, into LabEntry. Four bytes an entry, so the offset is the
|
|
; number doubled twice - there being no multiply on this machine, and none needed.
|
|
labEntryAt:
|
|
SETD.0 LabOffset
|
|
SETD.2 LabWhich
|
|
CALL numSet
|
|
SETD.0 LabOffset
|
|
SETD.2 LabOffset
|
|
CALL numAdd
|
|
SETD.0 LabOffset
|
|
SETD.2 LabOffset
|
|
CALL numAdd
|
|
SETD.0 LabEntry
|
|
SETD.2 LabBase
|
|
CALL numSet
|
|
SETD.0 LabEntry
|
|
SETD.2 LabOffset
|
|
CALL numAdd
|
|
RET
|
|
|
|
; How long the string at DP0 is, counting the zero on the end, into LabLength.
|
|
labLength:
|
|
SETD.1 LabLenWalk
|
|
STD.0.1
|
|
SETD.0 LabLength
|
|
CALL numZero
|
|
labLengthLoop:
|
|
SETD.0 LabLength
|
|
CALL numStep
|
|
SETD.1 LabLenWalk
|
|
LDD.0.1
|
|
LDA.0
|
|
BRA labLengthDone
|
|
SETD.0 LabLenWalk
|
|
CALL numStep
|
|
BRI labLengthLoop
|
|
labLengthDone:
|
|
RET
|
|
|
|
labComplain:
|
|
SWI osPrintString
|
|
SETD.0 LabNamed
|
|
SWI osPrintString
|
|
SETD.0 TokText
|
|
SWI osPrintString
|
|
SETD.0 LabAtLine
|
|
SWI osPrintString
|
|
SETD.0 TokLine
|
|
LDA.0
|
|
INCD.0
|
|
LDB.0
|
|
SWI osPrintNumber
|
|
SETD.0 LabNewLine
|
|
SWI osPrintString
|
|
RET
|
|
|
|
#Data
|
|
|
|
LabCount:
|
|
0x00 0x00
|
|
LabUsed:
|
|
0x00 0x00
|
|
LabNext:
|
|
0x00 0x00
|
|
LabBase:
|
|
0x00 0x00
|
|
LabAddress:
|
|
0x00 0x00
|
|
LabPutAddress:
|
|
0x00 0x00
|
|
LabNamePointer:
|
|
0x00 0x00
|
|
LabSought:
|
|
0x00 0x00
|
|
LabSubject:
|
|
0x00 0x00
|
|
LabEntry:
|
|
0x00 0x00
|
|
LabOffset:
|
|
0x00 0x00
|
|
; Where a halving search has got to, and where a name that is not there would go. LabLo is
|
|
; what labAdd makes room at, which is the whole reason the search hands it back.
|
|
LabLo:
|
|
0x00 0x00
|
|
LabHi:
|
|
0x00 0x00
|
|
LabWhich:
|
|
0x00 0x00
|
|
LabLength:
|
|
0x00 0x00
|
|
LabLenWalk:
|
|
0x00 0x00
|
|
LabEnd:
|
|
0x00 0x00
|
|
|
|
; How many labels there may be, and how many bytes of name between them.
|
|
;
|
|
; SIZED FOR THE ASSEMBLER ITSELF, which turns out to be the largest thing it is asked to
|
|
; build: the assembler is about 555 labels, against CosmOS's 1,341 and 16,758 bytes of name
|
|
; measured 2026-09-06 - CosmOS is much the bigger of the two now, and was the smaller when
|
|
; this was written. Running into either
|
|
; limit says so rather than writing past the end of the table, and that is what it did. The buffers live
|
|
; above the program rather than inside it - see the scratch map in Asm.asm.
|
|
; Two thousand and forty eight names, and twenty six kilobytes to hold them in. Both have
|
|
; now been doubled twice, and BOTH TIMES THE NAMES RAN OUT FIRST with the index a couple of
|
|
; hundred behind them - 8,081 of 8,192 the first time, 16,758 of 16,384 the second. A name
|
|
; is thirteen bytes on average and an index entry is four, so the arena will always be the
|
|
; one that speaks; raising it alone would buy a few hundred labels and then the other wall.
|
|
; THESE TWO MUST AGREE WITH THE SCRATCH MAP, which says where the room actually is.
|
|
LabLimit:
|
|
0x08 0x00
|
|
LabRoom:
|
|
0x68 0x00
|
|
|
|
LabNamed:
|
|
": "
|
|
LabAtLine:
|
|
", at line "
|
|
LabNewLine:
|
|
"
|
|
"
|
|
LabTwice:
|
|
"that label is defined twice"
|
|
LabFull:
|
|
"too many labels"
|
|
LabNoRoom:
|
|
"no room left for label names"
|
|
|