From 304bce58955a85485713d69ca378b5d0030d20a3 Mon Sep 17 00:00:00 2001 From: Kartik Agaram Date: Wed, 10 Jul 2019 11:32:46 -0700 Subject: start distinguishing table lookups from inserts --- subx/apps/assort | Bin 32242 -> 33060 bytes subx/apps/dquotes | Bin 38595 -> 39413 bytes subx/apps/pack | Bin 44608 -> 45426 bytes subx/apps/subx-common.subx | 370 +++++++++++++++++++++++++++++++++++++++++++++ subx/apps/survey | Bin 38746 -> 37973 bytes subx/apps/survey.subx | 24 +-- 6 files changed, 382 insertions(+), 12 deletions(-) diff --git a/subx/apps/assort b/subx/apps/assort index 83a063f0..ae3718ed 100755 Binary files a/subx/apps/assort and b/subx/apps/assort differ diff --git a/subx/apps/dquotes b/subx/apps/dquotes index e982690c..42a58de8 100755 Binary files a/subx/apps/dquotes and b/subx/apps/dquotes differ diff --git a/subx/apps/pack b/subx/apps/pack index 7ad19415..af4112aa 100755 Binary files a/subx/apps/pack and b/subx/apps/pack differ diff --git a/subx/apps/subx-common.subx b/subx/apps/subx-common.subx index 129c9821..083e6cc2 100644 --- a/subx/apps/subx-common.subx +++ b/subx/apps/subx-common.subx @@ -5,6 +5,376 @@ # . op subop mod rm32 base index scale r32 # . 1-3 bytes 3 bits 2 bits 3 bits 3 bits 3 bits 2 bits 2 bits 0/1/2/4 bytes 0/1/2/4 bytes +# - managing tables +# SubX has rudimentary support for tables. +# +# Each table is a stream of rows. +# +# Each row consists of a 4-byte row (address to a string) and a variable-size +# value. +# +# Accessing the table performs a linear scan for a key string, and always +# requires passing in the row size. +# +# Table primitives: +# get(stream, string, row-size) +# aborts if not found +# get-or-insert(stream, string, row-size) +# inserts if not found +# get-slice(stream, slice, row-size) +# aborts if not found +# get-or-insert-slice(stream, slice, row-size) +# inserts if not found + +# 'table' is a stream of (key, value) rows +# keys are always strings (addresses; size 4 bytes) +# values may be any type, but rows (key+value) always occupy 'row-size' bytes +# scan 'table' for a row with a key 'key' and return the address of the corresponding value +# if no row is found, abort +get: # table : (address stream {string, _}), key : (address string), row-size : int -> EAX : (address _) + # pseudocode: + # curr = table->data + # max = &table->data[table->write] + # while curr < max + # if string-equal?(key, *curr) + # return curr+4 + # curr += row-size + # abort + # + # . prolog + 55/push-EBP + 89/copy 3/mod/direct 5/rm32/EBP . . . 4/r32/ESP . . # copy ESP to EBP + # . save registers + 51/push-ECX + 52/push-EDX + 56/push-ESI + # ESI = table + 8b/copy 1/mod/*+disp8 5/rm32/EBP . . . 6/r32/ESI 8/disp8 . # copy *(EBP+8) to ESI + # curr/ECX = table->data + 8d/copy-address 1/mod/*+disp8 6/rm32/ESI . . . 1/r32/ECX 0xc/disp8 . # copy ESI+12 to ECX + # max/EDX = table->data + table->write + 8b/copy 0/mod/indirect 6/rm32/ESI . . . 2/r32/EDX . . # copy *ESI to EDX + 8d/copy-address 0/mod/indirect 4/rm32/sib 1/base/ECX 2/index/EDX . 2/r32/EDX . . # copy ECX+EDX to EDX +$get:search-loop: + # if (curr >= max) abort + 39/compare 3/mod/direct 1/rm32/ECX . . . 2/r32/EDX . . # compare ECX with EDX + 73/jump-if-greater-or-equal-unsigned $get:abort/disp8 + # if (string-equal?(key, *curr)) return curr+4 + # . EAX = string-equal?(key, *curr) + # . . push args + ff 6/subop/push 0/mod/indirect 1/rm32/ECX . . . . . . # push *ECX + ff 6/subop/push 1/mod/*+disp8 5/rm32/EBP . . . . 0xc/disp8 . # push *(EBP+12) + # . . call + e8/call string-equal?/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 8/imm32 # add to ESP + # . if (EAX != 0) return EAX = curr+4 + 3d/compare-EAX-and 0/imm32 + 74/jump-if-equal $get:mismatch/disp8 + 8d/copy-address 1/mod/*+disp8 1/rm32/ECX . . . 0/r32/EAX 4/disp8 . # copy ECX+4 to EAX + eb/jump $get:end/disp8 +$get:mismatch: + # curr += row-size + 03/add 1/mod/*+disp8 5/rm32/EBP . . . 1/r32/ECX 0x10/disp8 . # add *(EBP+16) to ECX + # loop + eb/jump $get:search-loop/disp8 +$get:end: + # . restore registers + 5e/pop-to-ESI + 5a/pop-to-EDX + 59/pop-to-ECX + # . epilog + 89/copy 3/mod/direct 4/rm32/ESP . . . 5/r32/EBP . . # copy EBP to ESP + 5d/pop-to-EBP + c3/return + +$get:abort: + # . _write(2/stderr, error) + # . . push args + 68/push "get: key not found: "/imm32 + 68/push 2/imm32/stderr + # . . call + e8/call _write/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 8/imm32 # add to ESP + # . _write(2/stderr, key) + # . . push args + ff 6/subop/push 1/mod/*+disp8 5/rm32/EBP . . . . 0xc/disp8 . # push *(EBP+12) + 68/push 2/imm32/stderr + # . . call + e8/call _write/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 8/imm32 # add to ESP + # . syscall(exit, 1) + bb/copy-to-EBX 1/imm32 + b8/copy-to-EAX 1/imm32/exit + cd/syscall 0x80/imm8 + # never gets here + +test-get: + # . prolog + 55/push-EBP + 89/copy 3/mod/direct 5/rm32/EBP . . . 4/r32/ESP . . # copy ESP to EBP + # - setup: create a table with a couple of keys + # var table/ECX : (address stream {string, number}) = stream(2 rows * 8 bytes) + 81 5/subop/subtract 3/mod/direct 4/rm32/ESP . . . . . 0x10/imm32 # subtract from ESP + 68/push 0x10/imm32/length + 68/push 0/imm32/read + 68/push 0/imm32/write + 89/copy 3/mod/direct 1/rm32/ECX . . . 4/r32/ESP . . # copy ESP to ECX + # insert(table, "code", 8 bytes per row) + # . . push args + 68/push 8/imm32/row-size + 68/push "code"/imm32 + 51/push-ECX + # . . call + e8/call get-or-insert/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP + # insert(table, "data", 8 bytes per row) + # . . push args + 68/push 8/imm32/row-size + 68/push "data"/imm32 + 51/push-ECX + # . . call + e8/call get-or-insert/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP +$test-get:check1: + # EAX = get(table, "code", 8 bytes per row) + # . . push args + 68/push 8/imm32/row-size + 68/push "code"/imm32 + 51/push-ECX + # . . call + e8/call get/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP + # check-ints-equal(EAX - table->data, 4, msg) + # . check-ints-equal(EAX - table, 16, msg) + # . . push args + 68/push "F - test-get/0"/imm32 + 68/push 0x10/imm32 + 29/subtract 3/mod/direct 0/rm32/EAX . . . 1/r32/ECX . . # subtract ECX from EAX + 50/push-EAX + # . . call + e8/call check-ints-equal/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP +$test-get:check2: + # EAX = get(table, "data", 8 bytes per row) + # . . push args + 68/push 8/imm32/row-size + 68/push "data"/imm32 + 51/push-ECX + # . . call + e8/call get/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP + # check-ints-equal(EAX - table->data, 12, msg) + # . check-ints-equal(EAX - table, 24, msg) + # . . push args + 68/push "F - test-get/1"/imm32 + 68/push 0x18/imm32 + 29/subtract 3/mod/direct 0/rm32/EAX . . . 1/r32/ECX . . # subtract ECX from EAX + 50/push-EAX + # . . call + e8/call check-ints-equal/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP +$test-get:end: + # . epilog + 89/copy 3/mod/direct 4/rm32/ESP . . . 5/r32/EBP . . # copy EBP to ESP + 5d/pop-to-EBP + c3/return + +# 'table' is a stream of (key, value) rows +# keys are always strings (addresses; size 4 bytes) +# values may be any type, but rows (key+value) always occupy 'row-size' bytes +# scan 'table' for a row with a key 'key' and return the address of the corresponding value +# if no row is found, abort +get-slice: # table : (address stream {string, _}), key : (address slice), row-size : int -> EAX : (address _) + # pseudocode: + # curr = table->data + # max = &table->data[table->write] + # while curr < max + # if slice-equal?(key, *curr) + # return curr+4 + # curr += row-size + # abort + # + # . prolog + 55/push-EBP + 89/copy 3/mod/direct 5/rm32/EBP . . . 4/r32/ESP . . # copy ESP to EBP + # . save registers + 51/push-ECX + 52/push-EDX + 56/push-ESI + # ESI = table + 8b/copy 1/mod/*+disp8 5/rm32/EBP . . . 6/r32/ESI 8/disp8 . # copy *(EBP+8) to ESI + # curr/ECX = table->data + 8d/copy-address 1/mod/*+disp8 6/rm32/ESI . . . 1/r32/ECX 0xc/disp8 . # copy ESI+12 to ECX + # max/EDX = table->data + table->write + 8b/copy 0/mod/indirect 6/rm32/ESI . . . 2/r32/EDX . . # copy *ESI to EDX + 8d/copy-address 0/mod/indirect 4/rm32/sib 1/base/ECX 2/index/EDX . 2/r32/EDX . . # copy ECX+EDX to EDX +$get-slice:search-loop: + # if (curr >= max) abort + 39/compare 3/mod/direct 1/rm32/ECX . . . 2/r32/EDX . . # compare ECX with EDX + 73/jump-if-greater-or-equal-unsigned $get-slice:abort/disp8 + # if (slice-equal?(key, *curr)) return curr+4 + # . EAX = slice-equal?(key, *curr) + # . . push args + ff 6/subop/push 0/mod/indirect 1/rm32/ECX . . . . . . # push *ECX + ff 6/subop/push 1/mod/*+disp8 5/rm32/EBP . . . . 0xc/disp8 . # push *(EBP+12) + # . . call + e8/call slice-equal?/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 8/imm32 # add to ESP + # . if (EAX != 0) return EAX = curr+4 + 3d/compare-EAX-and 0/imm32 + 74/jump-if-equal $get-slice:mismatch/disp8 + 8d/copy-address 1/mod/*+disp8 1/rm32/ECX . . . 0/r32/EAX 4/disp8 . # copy ECX+4 to EAX + eb/jump $get-slice:end/disp8 +$get-slice:mismatch: + # curr += row-size + 03/add 1/mod/*+disp8 5/rm32/EBP . . . 1/r32/ECX 0x10/disp8 . # add *(EBP+16) to ECX + # loop + eb/jump $get-slice:search-loop/disp8 +$get-slice:end: + # . restore registers + 5e/pop-to-ESI + 5a/pop-to-EDX + 59/pop-to-ECX + # . epilog + 89/copy 3/mod/direct 4/rm32/ESP . . . 5/r32/EBP . . # copy EBP to ESP + 5d/pop-to-EBP + c3/return + +$get-slice:abort: + # . _write(2/stderr, error) + # . . push args + 68/push "get-slice: key not found: "/imm32 + 68/push 2/imm32/stderr + # . . call + e8/call _write/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 8/imm32 # add to ESP + # . write-slice-buffered(Stderr, key) + # . . push args + ff 6/subop/push 1/mod/*+disp8 5/rm32/EBP . . . . 0xc/disp8 . # push *(EBP+12) + 68/push Stderr/imm32 + # . . call + e8/call write-slice-buffered/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 8/imm32 # add to ESP + # . flush(Stderr) + # . . push args + 68/push Stderr/imm32 + # . . call + e8/call flush/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 4/imm32 # add to ESP + # . syscall(exit, 1) + bb/copy-to-EBX 1/imm32 + b8/copy-to-EAX 1/imm32/exit + cd/syscall 0x80/imm8 + # never gets here + +test-get-slice: + # . prolog + 55/push-EBP + 89/copy 3/mod/direct 5/rm32/EBP . . . 4/r32/ESP . . # copy ESP to EBP + # - setup: create a table with a couple of keys + # var table/ECX : (address stream {string, number}) = stream(2 rows * 8 bytes) + 81 5/subop/subtract 3/mod/direct 4/rm32/ESP . . . . . 0x10/imm32 # subtract from ESP + 68/push 0x10/imm32/length + 68/push 0/imm32/read + 68/push 0/imm32/write + 89/copy 3/mod/direct 1/rm32/ECX . . . 4/r32/ESP . . # copy ESP to ECX + # insert(table, "code", 8 bytes per row) + # . . push args + 68/push 8/imm32/row-size + 68/push "code"/imm32 + 51/push-ECX + # . . call + e8/call get-or-insert/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP + # insert(table, "data", 8 bytes per row) + # . . push args + 68/push 8/imm32/row-size + 68/push "data"/imm32 + 51/push-ECX + # . . call + e8/call get-or-insert/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP +$test-get-slice:check1: + # (EAX..EDX) = "code" + b8/copy-to-EAX "code"/imm32 + 8b/copy 0/mod/indirect 0/rm32/EAX . . . 2/r32/EDX . . # copy *EAX to EDX + 8d/copy-address 1/mod/*+disp8 4/rm32/sib 0/base/EAX 2/index/EDX . 2/r32/EDX 4/disp8 . # copy EAX+EDX+4 to EDX + 05/add-to-EAX 4/imm32 + # var slice/EDX = {EAX, EDX} + 52/push-EDX + 50/push-EAX + 89/copy 3/mod/direct 2/rm32/EDX . . . 4/r32/ESP . . # copy ESP to EDX + # EAX = get-slice(table, "code", 8 bytes per row) + # . . push args + 68/push 8/imm32/row-size + 52/push-EDX + 51/push-ECX + # . . call + e8/call get-slice/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP + # check-ints-equal(EAX - table->data, 4, msg) # first row's value slot returned + # . check-ints-equal(EAX - table, 16, msg) + # . . push args + 68/push "F - test-get-slice/0"/imm32 + 68/push 0x10/imm32 + 29/subtract 3/mod/direct 0/rm32/EAX . . . 1/r32/ECX . . # subtract ECX from EAX + 50/push-EAX + # . . call + e8/call check-ints-equal/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP +$test-get-slice:check2: + # (EAX..EDX) = "data" + b8/copy-to-EAX "data"/imm32 + 8b/copy 0/mod/indirect 0/rm32/EAX . . . 2/r32/EDX . . # copy *EAX to EDX + 8d/copy-address 1/mod/*+disp8 4/rm32/sib 0/base/EAX 2/index/EDX . 2/r32/EDX 4/disp8 . # copy EAX+EDX+4 to EDX + 05/add-to-EAX 4/imm32 + # var slice/EDX = {EAX, EDX} + 52/push-EDX + 50/push-EAX + 89/copy 3/mod/direct 2/rm32/EDX . . . 4/r32/ESP . . # copy ESP to EDX + # EAX = get-slice(table, "data" slice, 8 bytes per row) + # . . push args + 68/push 8/imm32/row-size + 52/push-EDX + 51/push-ECX + # . . call + e8/call get-slice/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP + # check-ints-equal(EAX - table->data, 12, msg) + # . check-ints-equal(EAX - table, 24, msg) + # . . push args + 68/push "F - test-get-slice/1"/imm32 + 68/push 0x18/imm32 + 29/subtract 3/mod/direct 0/rm32/EAX . . . 1/r32/ECX . . # subtract ECX from EAX + 50/push-EAX + # . . call + e8/call check-ints-equal/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP +$test-get-slice:end: + # . epilog + 89/copy 3/mod/direct 4/rm32/ESP . . . 5/r32/EBP . . # copy EBP to ESP + 5d/pop-to-EBP + c3/return + # 'table' is a stream of (key, value) rows # keys are always strings (addresses; size 4 bytes) # values may be any type, but rows (key+value) always occupy 'row-size' bytes diff --git a/subx/apps/survey b/subx/apps/survey index 0c900562..177b5896 100755 Binary files a/subx/apps/survey and b/subx/apps/survey differ diff --git a/subx/apps/survey.subx b/subx/apps/survey.subx index e9cbe588..ea7e34ff 100644 --- a/subx/apps/survey.subx +++ b/subx/apps/survey.subx @@ -871,7 +871,7 @@ compute-addresses: # segments : (address stream {string, segment-info}), labels # while true # if (lrow >= max) break # seg-name : (address string) = lrow->segment-name - # label-seg : (address segment-info) = get-or-insert(segments, seg-name, row-size=16) + # label-seg : (address segment-info) = get(segments, seg-name, row-size=16) # lrow->address = label-seg->address + lrow->segment-offset # trace-sssns("label " lrow->key " is at address " lrow->address) # lrow += 16 # row-size @@ -947,16 +947,16 @@ $compute-addresses:label-loop: 73/jump-if-greater-or-equal-unsigned $compute-addresses:end/disp8 # seg-name/EDX = lrow->segment-name 8b/copy 1/mod/*+disp8 0/rm32/EAX . . . 2/r32/EDX 4/disp8 . # copy *EAX to EDX - # label-seg/EDX : (address segment-info) = get-or-insert(segments, seg-name, row-size=16) + # label-seg/EDX : (address segment-info) = get(segments, seg-name, row-size=16) # . save EAX 50/push-EAX - # . EAX = get-or-insert(segments, seg-name, row-size=16) + # . EAX = get(segments, seg-name, row-size=16) # . . push args 68/push 0x10/imm32/row-size 52/push-EDX ff 6/subop/push 1/mod/*+disp8 5/rm32/EBP . . . . 8/disp8 . # push *(EBP+8) # . . call - e8/call get-or-insert/disp32 + e8/call get/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP # . EDX = EAX @@ -1218,7 +1218,7 @@ emit-segments: # in : (address buffered-file), out : (address buffered-file), s # write-buffered(out, " ") # continue # datum = next-token-from-slice(word-slice->start, word-slice->end, "/") - # info = get-or-insert-slice(labels, datum) + # info = get-slice(labels, datum) # if has-metadata?(word-slice, "imm8") # abort # label should never go to imm8 # else if has-metadata?(word-slice, "imm32") @@ -1490,14 +1490,14 @@ $emit-segments:check-metadata: #? # . . discard args #? 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 8/imm32 # add to ESP #? # }}} - # info/ESI = get-or-insert-slice(labels, datum, row-size=16) - # . EAX = get-or-insert-slice(labels, datum, row-size=16) + # info/ESI = get-slice(labels, datum, row-size=16) + # . EAX = get-slice(labels, datum, row-size=16) # . . push args 68/push 0x10/imm32/row-size 57/push-EDI ff 6/subop/push 1/mod/*+disp8 5/rm32/EBP . . . . 0x14/disp8 . # push *(EBP+20) # . . call - e8/call get-or-insert-slice/disp32 + e8/call get-slice/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP # . ESI = EAX @@ -2008,7 +2008,7 @@ $emit-headers:end: emit-elf-header: # out : (address buffered-file), segments : (address stream {string, segment-info}), labels : (address stream {string, label-info}) # pseudocode - # *Elf_e_entry = get-or-insert(labels, "Entry")->address + # *Elf_e_entry = get(labels, "Entry")->address # *Elf_e_phnum = segments->write / 20 # size of a row # emit-hex-array(out, Elf_header) # @@ -2019,16 +2019,16 @@ emit-elf-header: # out : (address buffered-file), segments : (address stream {s 50/push-EAX 51/push-ECX 52/push-EDX # just because we need to call idiv - # *Elf_e_entry = get-or-insert(labels, "Entry")->address + # *Elf_e_entry = get(labels, "Entry")->address # . EAX = labels 8b/copy 1/mod/*+disp8 5/rm32/EBP . . . 0/r32/EAX 0x10/disp8 . # copy *(EBP+16) to EAX - # . label-info/EAX = get-or-insert(labels, "Entry", row-size=16) + # . label-info/EAX = get(labels, "Entry", row-size=16) # . . push args 68/push 0x10/imm32/row-size 68/push "Entry"/imm32 ff 6/subop/push 1/mod/*+disp8 5/rm32/EBP . . . . 0x10/disp8 . # push *(EBP+16) # . . call - e8/call get-or-insert/disp32 + e8/call get/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP # . EAX = label-info->address -- cgit 1.4.1-2-gfad0