Modified stdlib to use stack rotations to timeshare heap registers.

[vvhitespace] / stdlib / heap.pvvs

diff --git a/stdlib/heap.pvvs b/stdlib/heap.pvvs
index e72ee40..2c5eb79 100644 (file)
--- a/stdlib/heap.pvvs
+++ b/stdlib/heap.pvvs
@@ -2,9 +2,10 @@
 #define VVS_STDLIB_HEAP
 
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 #define VVS_STDLIB_HEAP
 
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

+@ Name:
+@   memset (11000)

 @ Description:
 @ Description:

-@   This function writes pattern into the memory locations:
-@     startaddr -> startaddr+count
+@   Writes 'pattern' in memory locations 'startaddr' to 'startaddr+count'.

 @ Call Stack:
 @   pattern
 @   startaddr
 @ Call Stack:
 @   pattern
 @   startaddr


@@ -14,53 +15,36 @@
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 NSSVTTSSSN              | Mark: 11000 (memset)
 
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 NSSVTTSSSN              | Mark: 11000 (memset)
 

-@ Prepare the stack for computation.
-@ Addr | Contents
-@    0 | count
-@    1 | startaddr
-@    2 | pattern
-
-SSSSN                   | PUSH 0 (ptr)
-SNT                     | SWAP
-TTS                     | STORE
-SSSTN                   | PUSH 1 (ptr)
-SNT                     | SWAP
-TTS                     | STORE
-SSSTSN                  | PUSH 2 (ptr)
-SNT                     | SWAP
-TTS                     | STORE
-
-@ Store pattern into one memory location on each pass through this loop.
+@ Store 'pattern' into one memory location on each pass through this loop.

 NSSVSSSTTSSSSSSSSSSSN   | Mark: 00011000 00000000
 NSSVSSSTTSSSSSSSSSSSN   | Mark: 00011000 00000000

-SSSSN                   | PUSH 0 (ptr)
-TTT                     | LOAD
-SSSTN                   | PUSH 1 (ptr)
-TTT                     | LOAD
+SNS                     | DUP
+SSSTTN                  | PUSH 3
+NSTTTSSN                | JSR > 1100 (deepdup)

 TSSS                    | ADD
 TSSS                    | ADD

-SSSTSN                  | PUSH 2 (ptr)
-TTT                     | LOAD
+SSSTSSN                 | PUSH 4
+NSTTTSSN                | JSR > 1100 (deepdup)

 TTS                     | STORE
 
 TTS                     | STORE
 

-@ Decrement and check for loop end condition count == 0.
-SSSSN                   | PUSH 0 (ptr)
-TTT                     | LOAD
+@ Check for loop end condition 'count == 0'.

 SNS                     | DUP
 NTSSSSTTSSSSSSSSSSTN    | BRZ > 00011000 00000001
 SNS                     | DUP
 NTSSSSTTSSSSSSSSSSTN    | BRZ > 00011000 00000001

+@ Decrement and loop again.

 SSSTN                   | PUSH 1
 TSST                    | SUBTRACT
 SSSTN                   | PUSH 1
 TSST                    | SUBTRACT

-SSSSN                   | PUSH 0 (ptr)
-SNT                     | SWAP
-TTS                     | STORE

 NSNSSSTTSSSSSSSSSSSN    | JMP > 00011000 00000000
 
 @ Clean up and return
 NSSVSSSTTSSSSSSSSSSTN   | Mark: 00011000 00000001
 SNN                     | DROP
 NSNSSSTTSSSSSSSSSSSN    | JMP > 00011000 00000000
 
 @ Clean up and return
 NSSVSSSTTSSSSSSSSSSTN   | Mark: 00011000 00000001
 SNN                     | DROP

+SNN                     | DROP
+SNN                     | DROP

 NTN                     | RTS
 
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 NTN                     | RTS
 
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

+@ Name:
+@   memcpy (11001)

 @ Description:
 @ Description:

-@   This function copies count+1 words from source to destination.
+@   Copies 'count+1' words from 'source' to 'destination'.

 @ Call Stack:
 @   source
 @   destination
 @ Call Stack:
 @   source
 @   destination


@@ -70,93 +54,77 @@ NTN                     | RTS
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 NSSVTTSSTN              | Mark: 11001 (memcpy)
 
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 NSSVTTSSTN              | Mark: 11001 (memcpy)
 

-@ Prepare the stack for computation.
-@ Addr | Contents
-@    0 | count
-@    1 | destination
-@    2 | source
-
-SSSSN                   | PUSH 0 (ptr)
-SNT                     | SWAP
-TTS                     | STORE
-SSSTN                   | PUSH 1 (ptr)
-SNT                     | SWAP
-TTS                     | STORE
-SSSTSN                  | PUSH 2 (ptr)
-SNT                     | SWAP
-TTS                     | STORE
-

 @ Copy one word on each pass through this loop.
 NSSVSSSTTSSTSSSSSSSSN   | Mark: 00011001 00000000
 @ Copy one word on each pass through this loop.
 NSSVSSSTTSSTSSSSSSSSN   | Mark: 00011001 00000000

-SSSTN                   | PUSH 1 (ptr)
-TTT                     | LOAD
-SSSSN                   | PUSH 0 (ptr)
-TTT                     | LOAD
+SNS                     | DUP
+SSSTTN                  | PUSH 3
+NSTTTSSN                | JSR > 1100 (deepdup)

 TSSS                    | ADD
 TSSS                    | ADD

-SSSTSN                  | PUSH 2 (ptr)
-TTT                     | LOAD
-SSSSN                   | PUSH 0 (ptr)
-TTT                     | LOAD
+SSSTSN                  | PUSH 2
+NSTTTSSN                | JSR > 1100 (deepdup)
+SSSTSTN                 | PUSH 5
+NSTTTSSN                | JSR > 1100 (deepdup)

 TSSS                    | ADD
 TTT                     | LOAD
 TTS                     | STORE
 
 TSSS                    | ADD
 TTT                     | LOAD
 TTS                     | STORE
 

-@ Decrement and check for loop end conditions.
-SSSSN                   | PUSH 0 (ptr)
-TTT                     | LOAD
+@ Check for loop end conditions and decrement.

 SNS                     | DUP
 NTSSSSTTSSTSSSSSSSTN    | BRZ > 00011001 00000001
 SSSTN                   | PUSH 1
 TSST                    | SUBTRACT
 SNS                     | DUP
 NTSSSSTTSSTSSSSSSSTN    | BRZ > 00011001 00000001
 SSSTN                   | PUSH 1
 TSST                    | SUBTRACT

-SSSSN                   | PUSH 0 (ptr)
-SNT                     | SWAP
-TTS                     | STORE

 NSNSSSTTSSTSSSSSSSSN    | JMP > 00011001 00000000
 
 @ Clean up and return
 NSSVSSSTTSSTSSSSSSSTN   | Mark: 00011001 00000001
 SNN                     | DROP
 NSNSSSTTSSTSSSSSSSSN    | JMP > 00011001 00000000
 
 @ Clean up and return
 NSSVSSSTTSSTSSSSSSSTN   | Mark: 00011001 00000001
 SNN                     | DROP

+SNN                     | DROP
+SNN                     | DROP

 NTN                     | RTS
 
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 NTN                     | RTS
 
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

+@ Name:
+@   memrand (11010)

 @ Description:
 @ Description:

-@   This function writes random words into the memory locations:
-@     startaddr -> startaddr+count
+@   Writes random words into memory locations 'startaddr' to 'startaddr+count'.

 @ Call Stack:
 @   count
 @   startaddr  <-- TOS
 @ Return Stack:
 @   <empty>
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 @ Call Stack:
 @   count
 @   startaddr  <-- TOS
 @ Return Stack:
 @   <empty>
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

+#include <math.pvvs>

 NSSVTTSTSN              | Mark: 11010 (memrand)
 NSSVTTSTSN              | Mark: 11010 (memrand)

-SSSSN                   | PUSH 0 (ptr)
-SNT                     | SWAP
-TTS                     | STORE

 
 @ Store random word into one memory location on each pass through this loop.
 NSSVSSSTTSTSSSSSSSSSN   | Mark: 00011010 00000000
 SNS                     | DUP
 
 @ Store random word into one memory location on each pass through this loop.
 NSSVSSSTTSTSSSSSSSSSN   | Mark: 00011010 00000000
 SNS                     | DUP

-SSSSN                   | PUSH 0 (ptr)
-TTT                     | LOAD
+SSSTTN                  | PUSH 3
+NSTTTSSN                | JSR > 1100 (deepdup)

 TSSS                    | ADD
 NSTTSSSSN               | JSR > 10000 (random)
 TTS                     | STORE
 
 @ Decrement and check loop end conditions
 TSSS                    | ADD
 NSTTSSSSN               | JSR > 10000 (random)
 TTS                     | STORE
 
 @ Decrement and check loop end conditions

+SNT                     | SWAP

 SNS                     | DUP
 NTSSSSTTSTSSSSSSSSTN    | BRZ > 00011010 00000001
 SSSTN                   | PUSH 1
 TSST                    | SUBTRACT
 SNS                     | DUP
 NTSSSSTTSTSSSSSSSSTN    | BRZ > 00011010 00000001
 SSSTN                   | PUSH 1
 TSST                    | SUBTRACT

+SNT                     | SWAP

 NSNSSSTTSTSSSSSSSSSN    | JMP > 00011010 00000000
 
 @ Clean up and return
 NSSVSSSTTSTSSSSSSSSTN   | Mark: 00011010 00000001
 SNN                     | DROP
 NSNSSSTTSTSSSSSSSSSN    | JMP > 00011010 00000000
 
 @ Clean up and return
 NSSVSSSTTSTSSSSSSSSTN   | Mark: 00011010 00000001
 SNN                     | DROP

+SNN                     | DROP

 NTN                     | RTS
 
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 NTN                     | RTS
 
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

+@ Name:
+@   memcmp (11011)

 @ Description:
 @ Description:

-@   This function compares two blocks of memory:
+@   Compares two blocks of memory:

 @     blk1ptr -> blk1ptr+count
 @       -- versus --
 @     blk2ptr -> blk2ptr+count
 @     blk1ptr -> blk1ptr+count
 @       -- versus --
 @     blk2ptr -> blk2ptr+count


@@ -170,53 +138,223 @@ NTN                     | RTS
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 NSSVTTSTTN              | Mark: 11011 (memcmp)
 
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 NSSVTTSTTN              | Mark: 11011 (memcmp)
 

-@ Prepare the stack for computation.
-@ Addr | Contents
-@    0 | blk2ptr
-@    1 | blk1ptr
-
-SSSSN                   | PUSH 0 (ptr)
-SNT                     | SWAP
-TTS                     | STORE
-SSSTN                   | PUSH 1 (ptr)
-SNT                     | SWAP
-TTS                     | STORE
-

 @ Compare one word on each pass through this loop.
 @ Compare one word on each pass through this loop.

+@ TOS> blk2ptr, blk1ptr, count

 NSSVSSSTTSTTSSSSSSSSN   | Mark: 00011011 00000000
 NSSVSSSTTSTTSSSSSSSSN   | Mark: 00011011 00000000

+@ Retrieve *blk2ptr

 SNS                     | DUP
 SNS                     | DUP

-SNS                     | DUP
-SSSSN                   | PUSH 0 (ptr)
-TTT                     | LOAD
+SSSTSSN                 | PUSH 4
+NSTTTSSN                | JSR > 1100 (deepdup)

 TSSS                    | ADD
 TTT                     | LOAD
 TSSS                    | ADD
 TTT                     | LOAD

-SNT                     | SWAP
-SSSTN                   | PUSH 1 (ptr)
-TTT                     | LOAD
+@ Retrieve *blk1ptr
+SSSTTN                  | PUSH 3
+NSTTTSSN                | JSR > 1100 (deepdup)
+SSSTSTN                 | PUSH 5
+NSTTTSSN                | JSR > 1100 (deepdup)

 TSSS                    | ADD
 TTT                     | LOAD
 TSSS                    | ADD
 TTT                     | LOAD

+@ Compare

 TSST                    | SUBTRACT
 TSST                    | SUBTRACT

+@ TOS> *blk2ptr-*blk1ptr, blk2ptr, blk1ptr, count

 NTSSSSTTSTTSSSSSSTSN    | BRZ > 00011011 00000010 (jump if words match)
 
 @ Return 'match? = false'
 SNN                     | DROP
 NTSSSSTTSTTSSSSSSTSN    | BRZ > 00011011 00000010 (jump if words match)
 
 @ Return 'match? = false'
 SNN                     | DROP

+SNN                     | DROP
+SNN                     | DROP

 SSSTN                   | PUSH 1
 NTN                     | RTS
 
 SSSTN                   | PUSH 1
 NTN                     | RTS
 

-@ Decrement and loop again if loop isn't complete.
+@ Decrement and loop again if loop is not complete.

 NSSVSSSTTSTTSSSSSSTSN   | Mark: 00011011 00000010
 NSSVSSSTTSTTSSSSSSTSN   | Mark: 00011011 00000010

-SNS                     | DUP
+SSSTTN                  | PUSH 3
+NSTTTSSN                | JSR > 1100 (deepdup)
+@ TOS> count, blk2ptr, blk1ptr, count

 NTSSSSTTSTTSSSSSSSTN    | BRZ > 00011011 00000001 (jump if loop is complete)
 NTSSSSTTSTTSSSSSSSTN    | BRZ > 00011011 00000001 (jump if loop is complete)

+SSSTTN                  | PUSH 3
+NSTTSTTN                | JSR > 1011 (stackrotatereverse)

 SSSTN                   | PUSH 1
 SSSTN                   | PUSH 1

-TSST                    | SUBTRACT
+TSSS                    | ADD
+SSSTTN                  | PUSH 3
+NSTTSTSN                | JSR > 1010 (stackrotate)

 NSNSSSTTSTTSSSSSSSSN    | JMP > 00011011 00000000
 
 @ Return 'match? = true'
 NSSVSSSTTSTTSSSSSSSTN   | Mark: 00011011 00000001
 SNN                     | DROP
 NSNSSSTTSTTSSSSSSSSN    | JMP > 00011011 00000000
 
 @ Return 'match? = true'
 NSSVSSSTTSTTSSSSSSSTN   | Mark: 00011011 00000001
 SNN                     | DROP

+SNN                     | DROP
+SNN                     | DROP

 SSSSN                   | PUSH 0
 NTN                     | RTS
 
 SSSSN                   | PUSH 0
 NTN                     | RTS
 

-#include <math.pvvs>
+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
+@ Name:
+@   memsrch (11100)
+@ Description:
+@   Searches the heap from 'address' to 'address+count'.
+@   If 'pattern' is found, the return value is a pointer to the matching word.
+@   If not found, the return value is a null pointer.
+@ Call Stack:
+@   pattern
+@   count
+@   address <-- TOS
+@ Return Stack:
+@   pointer <-- TOS
+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
+NSSVTTTSSN              | Mark: 11100 (memsrch)
+
+@ Setup an 'offset counter' on the stack.
+SSSSN                   | PUSH 0
+
+@ Compare one word on each pass through this loop.
+@ TOS> counter, address, count, pattern
+NSSVSSSTTTSSSSSSSSSSN   | Mark: 00011100 00000000
+SNT                     | SWAP
+SNS                     | DUP
+SSSTTN                  | PUSH 3
+NSTTSTTN                | JSR > 1011 (stackrotatereverse)
+SNS                     | DUP
+SSSTTN                  | PUSH 3
+NSTTSTTN                | JSR > 1011 (stackrotatereverse)
+TSSS                    | ADD
+TTT                     | LOAD
+SSSTSTN                 | PUSH 5
+NSTTTSSN                | JSR > 1100 (deepdup)
+TSST                    | SUBTRACT
+@ TOS> pattern-(address+counter), counter, address, count, pattern
+NTSSSSTTTSSSSSSSSSTN    | BRZ > 00011100 00000001
+
+@ Test for end of loop by comparing 'counter' and 'count'.
+SNS                     | DUP
+SSSTSSN                 | PUSH 4
+NSTTTSSN                | JSR > 1100 (deepdup)
+TSST                    | SUBTRACT
+@ TOS> counter-count, counter, address, count, pattern
+NTSSSSTTTSSSSSSSSTSN    | BRZ > 00011100 00000010
+
+@ Increment 'counter' and loop again.
+SSSTN                   | PUSH 1
+TSSS                    | ADD
+NSNSSSTTTSSSSSSSSSSN    | JMP > 00011100 00000000
+
+@ Found a match. Clean up and return.
+NSSVSSSTTTSSSSSSSSSTN   | Mark: 00011100 00000001
+TSSS                    | ADD
+SNT                     | SWAP
+SNN                     | DROP
+SNT                     | SWAP
+SNN                     | DROP
+NTN                     | RTS
+
+@ No match found. Clean up and return.
+NSSVSSSTTTSSSSSSSSTSN   | Mark: 00011100 00000010
+SNN                     | DROP
+SNN                     | DROP
+SNN                     | DROP
+SNN                     | DROP
+SSSSN                   | PUSH 0
+NTN                     | RTS
+
+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
+@ Name:
+@   slurp (11110)
+@ Description:
+@   Reads values from heap to stack in complementary order to 'spew'.
+@ Call Stack:
+@   address
+@   count  <-- TOS
+@ Return Stack:
+@   heap[address+count]
+@   ...
+@   heap[address+1]
+@   heap[address]  <-- TOS
+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
+#include <stack.pvvs>
+NSSVTTTTSN              | Mark: 11110 (slurp)
+
+@ Load one word from heap on each pass.
+SNS                     | DUP
+SSSTTN                  | PUSH 3
+NSTTSTSN                | JSR > 1010 (stackrotate)
+SNT                     | SWAP
+SNS                     | DUP
+SSSTTN                  | PUSH 3
+NSTTSTSN                | JSR > 1010 (stackrotate)
+TSSS                    | ADD
+TTT                     | LOAD
+SSSTTN                  | PUSH 3
+NSTTSTSN                | JSR > 1010 (stackrotate)
+SNT                     | SWAP
+
+@ Check for loop completion.
+SNS                     | DUP
+NTSSSSTTTTSSSSSSSSSN    | BRZ > 00011110 00000000
+SSSTN                   | PUSH 1
+TSST                    | SUBTRACT
+NSNTTTTSN               | JMP > 11110 (slurp)
+
+@ Clean up and return.
+NSSVSSSTTTTSSSSSSSSSN   | Mark: 00011110 00000000
+SNN                     | DROP
+SNN                     | DROP
+NTN                     | RTS
+
+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
+@ Name:
+@   spew (11111)
+@ Description:
+@   Writes values from stack to heap in this order:
+@     TOS   -> heap[address]
+@     TOS+1 -> heap[address+1]
+@     ...
+@     TOS+n -> heap[address+count]
+@ Call Stack:
+@   data-words
+@   ...
+@   data-words
+@   address
+@   count  <-- TOS
+@ Return Stack:
+@   <empty>
+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
+#include <stack.pvvs>
+NSSVTTTTTN              | Mark: 11111 (spew)
+
+@ Create a counter that doubles as a dest. pointer offset generator.
+SSSSN                   | PUSH 0
+
+@ Store one word to heap on each pass.
+NSSVSSSTTTTTSSSSSSSSN   | Mark: 00011111 00000000
+SNS                     | DUP
+SSSTSSN                 | PUSH 4
+NSTTTSSN                | JSR > 1100 (deepdup)
+TSSS                    | ADD
+SSSTSTN                 | PUSH 5
+NSTTSTTN                | JSR > 1011 (stackrotatereverse)
+TTS                     | STORE
+
+@ Check for loop completion.
+SNT                     | SWAP
+SNS                     | DUP
+SSSTTN                  | PUSH 3
+NSTTSTTN                | JSR > 1011 (stackrotatereverse)
+SNS                     | DUP
+SSSTTN                  | PUSH 3
+NSTTSTTN                | JSR > 1011 (stackrotatereverse)
+TSST                    | SUBTRACT
+NTSSSSTTTTTSSSSSSSTN    | BRZ > 00011111 00000001
+
+@ Increment counter.
+SSSTN                  | PUSH 1
+TSSS                    | ADD
+NSNSSSTTTTTSSSSSSSSN    | JMP > 00011111 00000000
+
+@ Clean up and return.
+NSSVSSSTTTTTSSSSSSSTN   | Mark: 00011111 00000001
+SNN                     | DROP
+SNN                     | DROP
+SNN                     | DROP
+NTN                     | RTS

 
 #endif
 
 #endif