From 70ce12dc055bfead28d61225ea9bcb5b11a6c242 Mon Sep 17 00:00:00 2001 From: Irene Knapp Date: Tue, 8 Sep 2026 15:41:37 -0700 Subject: bubblesort the metadata entries during postprocessing since we do this here, we no longer need to worry about doing it during initial entry creation, so that's good. that had been on the mental "maybe later" checklist for a while. the various innovations in entry processing now make it possible to pass through most of the formatting in hex.e, so that's done now (suffix comments that aren't instruction decodings still need to be made to work) there's also a new entry type which will be part of the comment parameter system. that's not fully working yet, but this was a bunch of really subtle debugging, so it makes a good spot to checkpoint at. Force-Push: yes Change-Id: I2aff7276368eaad7e5c280a58834605e294dcd74 --- hex.e | 72 ++++++++++++-------- transform.e | 219 ++++++++++++++++++++++++++++++++++++++++++++---------------- 2 files changed, 205 insertions(+), 86 deletions(-) diff --git a/hex.e b/hex.e index fd283ca..d1c4e31 100644 --- a/hex.e +++ b/hex.e @@ -21,88 +21,106 @@ ~ : This is the start routine, the first thing that runs when the ELF loads. ~ : indent current-offset L!' cold-start - ~ The basic registers preserved across syscalls are rbx, rsp, rbp. - ~ To avoid redundant moves, we store the buffer pointer in rbx just once, - ~ and keep it there. We've made sure our load origin fits in 32 bits, so we - ~ can use imm32 for that. We're going to want to do an indirect load from - ~ it, so we can't use rbp for this. + ~ : The basic registers preserved across syscalls are rbx, rsp, rbp. + ~ : To avoid redundant moves, we store the buffer pointer in rbx just once, + ~ : and keep it there. We've made sure our load origin fits in 32 bits, so + ~ : we can use imm32 for that. We're going to want to do an indirect load + ~ : from it, so we can't use rbp for this. L@' buffer L@' origin + :rbx mov-reg64-imm32 + ~ : blank-line current-offset L!' input-loop-start L@' read-byte call-rel-imm32-from-here + ~ : blank-line - ~ If the length is 0, we got EOF. If it's less than zero, we got a read - ~ error. Either way, we exit. This is a signed comparison, as it needs to - ~ be. + ~ : If the length is 0, we got EOF. If it's less than zero, we got a read + ~ : error. Either way, we exit. This is a signed comparison, as it needs to + ~ : be. 0 :rax cmp-reg64-imm8 L@' exit :cc-equal jmp-cc-rel-imm8-from-here L@' read-error :cc-less jmp-cc-rel-imm8-from-here + ~ : blank-line - ~ Now that the length is handled, retrieve the input byte. + ~ : Now that the length is handled, retrieve the input byte. :rbx :rax mov-reg64-indirect-reg64 + ~ : blank-line - ~ If it's space or linefeed, skip it (go back to the loop start). + ~ : If it's space or linefeed, skip it (go back to the loop start). 0x20 :rax cmp-reg64-imm8 ~ ASCII space L@' input-loop-start :cc-equal jmp-cc-rel-imm8-from-here 0x0a :rax cmp-reg64-imm8 ~ ASCII linefeed L@' input-loop-start :cc-equal jmp-cc-rel-imm8-from-here - ~ If it's a comment, skip the whole thing. + ~ : If it's a comment, skip the whole thing. 0x7e :rax cmp-reg64-imm8 ~ ASCII tilde L@' skip-comment :cc-equal jmp-cc-rel-imm8-from-here + ~ : blank-line - ~ Decode the value, or exit with an error. + ~ : Decode the value, or exit with an error. L@' decode-nibble call-rel-imm32-from-here + ~ : blank-line - ~ We use rbp as a place to stash the high nibble. + ~ : We use rbp as a place to stash the high nibble. :rax :rbp mov-reg64-reg64 4 :rbp rol-reg64-imm8 + ~ : blank-line - ~ Now we read another byte. + ~ : Now we read another byte. L@' read-byte call-rel-imm32-from-here + ~ : blank-line - ~ Handle the length. A second hex digit is required here. + ~ : Handle the length. A second hex digit is required here. 0 :rax cmp-reg64-imm8 L@' unexpected-eof :cc-equal jmp-cc-rel-imm8-from-here L@' read-error :cc-less jmp-cc-rel-imm8-from-here + ~ : blank-line - ~ Now that the length is handled, retrieve the input byte. + ~ : Now that the length is handled, retrieve the input byte. :rbx :rax mov-reg64-indirect-reg64 + ~ : blank-line - ~ Decode the value, or exit with an error. + ~ : Decode the value, or exit with an error. L@' decode-nibble call-rel-imm32-from-here + ~ : blank-line - ~ We OR in the low nibble. + ~ : We OR in the low nibble. :rax :rbp or-reg64-reg64 + ~ : blank-line - ~ Output the byte. We reuse the buffer as a place to store it. + ~ : Output the byte. We reuse the buffer as a place to store it. :rbp :rbx mov-indirect-reg64-reg64 :rbx :rsi mov-reg64-reg64 ~ buffer pointer 1 :rdx mov-reg64-imm32 ~ buffer length 1 :rax mov-reg64-imm32 ~ syscall number for sys-write 1 :rdi mov-reg64-imm32 ~ file descriptor 1 is stdout syscall + ~ : blank-line - ~ Back to the start of the loop. + ~ : Back to the start of the loop. L@' input-loop-start jmp-rel-imm8-from-here + ~ : blank-line current-offset L!' skip-comment - ~ Read a byte for the comment. + ~ : Read a byte for the comment. L@' read-byte call-rel-imm32-from-here + ~ : blank-line - ~ Handle the length. We're allowed to end in a comment. + ~ : Handle the length. We're allowed to end in a comment. 0 :rax cmp-reg64-imm8 L@' exit :cc-equal jmp-cc-rel-imm8-from-here L@' read-error :cc-less jmp-cc-rel-imm8-from-here + ~ : blank-line - ~ Now that the length is handled, retrieve the input byte. + ~ : Now that the length is handled, retrieve the input byte. :rbx :rax mov-reg64-indirect-reg64 + ~ : blank-line - ~ If it's linefeed, the comment is over. + ~ : If it's linefeed, the comment is over. 0x0a :rax cmp-reg64-imm8 ~ ASCII linefeed L@' input-loop-start :cc-equal jmp-cc-rel-imm8-from-here + ~ : blank-line - ~ We're still in the comment, keep handling it. + ~ : We're still in the comment, keep handling it. L@' skip-comment jmp-rel-imm8-from-here ~ : deindent ; @@ -119,11 +137,11 @@ ~ : This is the routine named "read-byte". ~ : indent current-offset L!' read-byte - ~ We use self-xor as a concise way to set registers to zero. + ~ : We use self-xor as a concise way to set registers to zero. :rax :rax xor-reg64-reg64 ~ syscall number for sys-read :rdi :rdi xor-reg64-reg64 ~ file descriptor 0 is stdin :rbx :rsi mov-reg64-reg64 ~ buffer pointer - ~ We read one byte at a time, because it makes the loop structure simple. + ~ : We read one byte at a time, because it makes the loop structure simple. 1 :rdx mov-reg64-imm32 ~ buffer length syscall ret diff --git a/transform.e b/transform.e index 7560752..ea93ec3 100644 --- a/transform.e +++ b/transform.e @@ -2738,6 +2738,7 @@ allocate-transformation-state s" transformation-state" variable : hex-output-metadata-entry-type-string-literal 5 ; : hex-output-metadata-entry-type-raw-string-literal 6 ; : hex-output-metadata-entry-type-alignment 7 ; +: hex-output-metadata-entry-type-provide-substring-hex64 8 ; ~ Initialize the contents of the output metadata to all zeroes. This is ~ called from hex-transform at its top level, at the very start, to make sure @@ -2982,6 +2983,16 @@ allocate-transformation-state s" transformation-state" variable s" swap" find entry-to-execution-token , ; +: is-comment-entry + hex-output-metadata-entry-type @ + dup hex-output-metadata-entry-type-line-comment = + swap hex-output-metadata-entry-type-suffix-comment = + || ; + +: is-provide-substring-entry + hex-output-metadata-entry-type @ + hex-output-metadata-entry-type-provide-substring-hex64 = ; + : is-fresh-line@ transformation-state transformation-state-output-metadata @ hex-output-metadata-is-fresh-line @ ; @@ -3018,66 +3029,134 @@ allocate-transformation-state s" transformation-state" variable ~ Any time output is performed, all existing entries are post-processed. ~ Therefore, the post-processing is required to be idempotent, and is. : postprocess-metadata-entries - transformation-state transformation-state-output-metadata @ - hex-output-metadata-first-entry - { dup @ } { - ~ (entry pointer) - - ~ Is the entry a suffix comment with a non-zero data length? - dup hex-output-metadata-entry-type @ - hex-output-metadata-entry-type-suffix-comment = - over hex-output-metadata-entry-data-length @ 0 != && { - ~ (entry pointer) - dup dup - - ~ Find all the remaining entries, and the final terminator, and slide - ~ them forward by the length of one entry. - { dup @ } { hex-output-metadata-next-entry } while 8 + - ~ (entry pointer, entry pointer, entry array end pointer) - swap - - ~ (entry pointer, entry array tail length) - swap dup dup hex-output-metadata-next-entry 4 roll - ~ (entry pointer, entry pointer, adjusted entry pointer, - ~ entry array tail length) - memmove - ~ (entry pointer) - - ~ We have a feature which lets a suffix comment be created with a - ~ negative length, which means it covers bytes before the current output - ~ point rather than after it. This logic here is the implementation of - ~ that feature. - dup hex-output-metadata-entry-data-start @ dup - 2 pick hex-output-metadata-entry-data-length @ + - 2dup min 3unroll max - ~ (entry pointer, low end of data, high end of data) - - ~ Now we have the original entry at the original location, and a copy - ~ of it at the next location. We modify the original one in-place to - ~ turn it into a fresh-line entry at the low end of the data... - 2 pick hex-output-metadata-entry-type - hex-output-metadata-entry-type-fresh-line swap ! - - 2 pick hex-output-metadata-entry-data-start 3roll swap ! - 2 pick hex-output-metadata-entry-data-length 0 swap ! - ~ (entry pointer, high end of data) - - ~ ... then we modify the next entry in-place to set its location to - ~ the end of the data instead of the beginning, and its length to zero. - over hex-output-metadata-next-entry - ~ (entry pointer, high end of data, next entry pointer) - - dup hex-output-metadata-entry-data-start 3roll swap ! - hex-output-metadata-entry-data-length 0 swap ! - ~ (entry pointer) - - ~ This rule won't fire again on the fresh-line entry because it's of a - ~ different type, and it won't fire on the modified suffix-comment entry - ~ because its data length is zero. There's no other rules either, so our - ~ idempotence requirement is satisfied. - } if + 1 { } { + 0 + ~ (did anything this iteration) + + transformation-state transformation-state-output-metadata @ + hex-output-metadata-first-entry + { dup @ } { + ~ (did anything, entry pointer) + + ~ Is the entry a suffix comment with a non-zero data length? + dup hex-output-metadata-entry-type @ + hex-output-metadata-entry-type-suffix-comment = + over hex-output-metadata-entry-data-length @ 0 != && { + ~ Split it into two entries so as not to rely on data length for + ~ formatting. + ~ (did anything, entry pointer) + + ~ Find all the remaining entries, and the final terminator, and slide + ~ them forward by the length of one entry. + dup dup + { dup @ } { hex-output-metadata-next-entry } while 8 + + ~ (..., entry pointer, entry pointer, entry array end pointer) + swap - + ~ (..., entry pointer, entry array tail length) + swap dup dup hex-output-metadata-next-entry 4 roll + ~ (..., entry pointer, entry pointer, adjusted entry pointer, + ~ entry array tail length) + memmove + ~ (..., entry pointer) + + ~ We have a feature which lets a suffix comment be created with a + ~ negative length, which means it covers bytes before the current output + ~ point rather than after it. This logic here is the implementation of + ~ that feature. + dup hex-output-metadata-entry-data-start @ dup + 2 pick hex-output-metadata-entry-data-length @ + + 2dup min 3unroll max + ~ (..., entry pointer, low end of data, high end of data) + + ~ Now we have the original entry at the original location, and a copy + ~ of it at the next location. We modify the original one in-place to + ~ turn it into a fresh-line entry at the low end of the data... + 2 pick hex-output-metadata-entry-type + hex-output-metadata-entry-type-fresh-line swap ! + ~ (..., entry pointer, low end of data, high end of data) + + 2 pick hex-output-metadata-entry-data-start 3roll swap ! + ~ (..., entry pointer, high end of data) + over hex-output-metadata-entry-data-length 0 swap ! + ~ (..., entry pointer, high end of data) + + ~ ... then we modify the next entry in-place to set its location to + ~ the end of the data instead of the beginning, and its length to zero. + over hex-output-metadata-next-entry + ~ (..., entry pointer, high end of data, next entry pointer) + + dup hex-output-metadata-entry-data-start 3roll swap ! + ~ (..., entry pointer, next entry pointer) + hex-output-metadata-entry-data-length 0 swap ! + ~ (..., entry pointer) + + ~ This rule won't fire again on the fresh-line entry because it's of a + ~ a different type, and it won't fire on the modified suffix-comment + ~ entry because its data length is zero. + ~ + ~ It's possible the bubble-sort rule will fire on either of them. + + ~ (did anything, entry pointer) + swap drop 1 swap + } if + + ~ Do this entry and the next entry both exist, and they're out of + ~ order based on their data starts? + dup hex-output-metadata-next-entry dup @ + { hex-output-metadata-entry-data-start @ + over hex-output-metadata-entry-data-start @ > } + { drop 0 } if-else + { + ~ Swap the order of the two entries. Since this whole thing is in a + ~ loop, this functions as a bubble sort. + ~ (did anything, entry pointer) + + ~ Copy the current entry to a scratch area. + dup dup dup hex-output-metadata-next-entry swap - + ~ (..., entry pointer, entry pointer, entry length) + swap-transform-variables here @ swap-transform-variables swap + ~ (..., entry pointer, entry pointer, scratch pointer, entry length) + memcopy + ~ (..., entry pointer) + + ~ Copy the next entry over the current entry. + dup dup hex-output-metadata-next-entry dup + ~ (..., entry pointer, entry pointer, next entry pointer, + ~ next entry pointer) + 3roll - + ~ (..., entry pointer, next entry pointer, entry length) + 2 pick swap + ~ (..., entry pointer, + ~ next entry pointer, entry pointer, entry length) + memcopy + ~ (entry pointer) + + ~ Copy the scratch area over the next entry. + dup hex-output-metadata-next-entry dup + ~ (..., entry pointer, next entry pointer, next entry pointer) + 2 pick - + ~ (..., entry pointer, next entry pointer, entry length) + swap-transform-variables here @ swap-transform-variables 3unroll + ~ (..., entry pointer, + ~ scratch pointer, next entry pointer, entry length) + memcopy + ~ (..., entry pointer) + + ~ This rule won't fire again on the same pair of entries because now + ~ they're in the correct order. It may fire again next iteration, + ~ but only until everything is sorted. + ~ + ~ This rule does nothing to alter whether the suffix-comment rule + ~ will fire on either of the entries it swapped, so there's no + ~ possibility of an infinite loop through that one. + + ~ (did anything, entry pointer) + swap drop 1 swap + } if - hex-output-metadata-next-entry - } while drop ; + hex-output-metadata-next-entry + } while drop + } while ; ~ This "replacement" is a little different from an alternate: When the code ~ under transformation attempts to compile its own version of sys-write, it @@ -3188,6 +3267,19 @@ allocate-transformation-state s" transformation-state" variable 0 current-column! } if + dup hex-output-metadata-entry-type @ + hex-output-metadata-entry-type-provide-substring-hex64 = { + fresh-line + indentation-depth@ dup indent advance-current-column + + ." ~ hex64 value 0x" + dup hex-output-metadata-entry-string @ .hex64 + + newline + 1 is-fresh-line! + 0 current-column! + } if + } if hex-output-metadata-next-entry } while @@ -4013,6 +4105,15 @@ allocate-transformation-state s" transformation-state" variable exit } if + dup s" provide-substring-hex64" stringcmp 0 = { + ~ Create a new "provide substring hex64" entry. Notice that we + ~ intentionally read one stack level deeper than anything of ours, which + ~ will be a value provided by the code the magic comment is embedded in. + drop 2 pick hex-output-metadata-entry-type-provide-substring-hex64 swap + add-hex-output-metadata-entry + exit + } if + ~ If it has a nonzero length, create a new suffix-comment entry. over 0 != { hex-output-metadata-entry-type-suffix-comment swap -- cgit 1.4.1