meow5

1 I left myself a nice easy one to start this log: 2 3 [x] Make all words take params from the stack, not 4 from pre-defined registers. 5 6 Which ought to be simple: just push the values 7 I need before calling the function. Then have 8 the function pop the values into the registers 9 and off we go. 10 11 +----------------------------------------------------+ 12 | NOTE: I'm still using call/ret to use the | 13 | 'find' and 'inline' words when the program | 14 | initially runs. I've got a bit of a | 15 | chicken-and-egg problem here because without a | 16 | return, these won't seamlessly move on to the | 17 | next instructions when they're done and I | 18 | can't find or inline them because THEY are | 19 | 'find' and 'inline'! | 20 | | 21 | I feel like that will be solved when I've got | 22 | more of the interpreter or REPL in place. If | 23 | not, I've got a puzzle on my hands. For the | 24 | moment, things are just a bit...messy. | 25 +----------------------------------------------------+ 26 27 Well, I thought that was going to be easy. I mean, it is 28 pretty easy. But it has a few snags I hadn't yet 29 considered. 30 31 It turns out, using the same stack for call/ret return 32 address storage AND for passing values between functions 33 in a truly concatenative manner gets real complicated 34 real quick. And since I was using call/ret temporarily 35 anyway, I have zero desire to do anything fancy to make 36 it work. 37 38 So I'm going to basically do my own return by storing a 39 return address and jumping to it at the end of both 40 'inline' and 'find'. 41 42 I'm making a new variable in BSS to hold my return 43 address. I only need one, not a stack, because I'm not 44 making any nested calls. 45 46 temp_return_addr: resb 4 47 48 I'll put in a mockup of the code to get the assembled 49 instruction lengths right (I hope) so I can figure out 50 the address we just jump back to as a "return". (I'm 51 pretty sure I can't just store the instruction pointer 52 register because that'll be a point before the "call" 53 jump and then I'll have an infinite loop, right?) 54 55 I'll use NASM's listing feature for that. It comes out 56 super wide (well, compared to the 60 columns I give 57 myself on my little split screen setup!), so I'll see if 58 I can reformat it enough to fit here: 59 60 152 00DA 68[0600] push temp_meow_name 61 153 00DD 66C706[0904]- mov dword [temp_return_addr], $ 62 153 00E2 [DD000000] 63 154 00E6 EB8A jmp find 64 155 00E8 6650 push eax 65 66 The listing is so fun to look at and I find it almost 67 fetishisticly beautiful. I mean, I've had all of these 68 _questions_ about how all of this actually works and 69 here, if you can read them, are all of the _answers_. I 70 mean, I know the CPU still has secrets down below even 71 this machine code layer. But for the application 72 programmer, this is _it_. This is the bedrock upon which 73 we lay all of our hopes and dreams. In the hex column on 74 the left are the real instructions, no longer hidden by 75 mnemonics or symbols. 76 77 Anyway, where was I? 78 79 Oh, yeah, so '$' is NASM for "the address at the 80 beginning of this line". Which is very handy. And that's 81 exactly what's gonna be put into temp_return_addr: 82 83 0904 is little-endian for temp_return_addr at 0409 84 (which I could see further up my listing) 85 86 DD000000 is the address returned by $ 87 (again, in little-endian) 88 89 And assuming the assembled code won't change, it looks 90 like I want my return address to be an additional... 91 92 E8 - DD 93 94 ...bytes. Which, uh, I'll ask my cat to subtract for me. 95 96 Hmm. No, he purred, but was not forthcoming with the 97 answer. Okay, how about dc? 98 99 $ dc 100 16 i 101 e8 dd - p 102 dc: 'e' (0145) unimplemented 103 E8 DD - p 104 11 105 106 Okay, so dc hissed at me once for not entering the hex 107 values in upper case. So score one point for my cat. But 108 then it gave me the correct answer after that, so score 109 one point for dc. Looks like this match is even. 110 111 So I wanna add 11 bytes to my return addresses. 112 113 Here's the new listing: 114 115 153 00DD 66C706[0904]- mov dword [temp_return_addr], ($ + 11) 116 153 00E2 [E8000000] 117 154 00E6 EB8A jmp find 118 155 00E8 6650 push eax 119 120 Looks right to me, we want to jump ("ret") back to 00E8 121 after the jump ("call") to find. 122 123 Of course, this seems super fragile, but it's also super 124 temporary. Let's just see if it works... 125 126 Okay, dang it, a segfault. My changes have required 127 another change and now the addresses are a little 128 different, but the 11 bytes should still be the same: 129 130 154 000000DF 66C706[0904]- mov dword [temp_return_addr], ($ + 11) 131 154 000000E4 [EA000000] 132 155 000000E8 EB88 jmp find 133 156 000000EA 6650 push eax 134 135 Let's try it now: 136 137 (gdb) break find.found_it 138 Breakpoint 1, find.found_it () at meow5.asm:116 139 116 mov eax, edx ; pointer to tail of dictionary word 140 (gdb) p/a $edx 141 $1 = 0x8049030 <meow_tail> 142 143 So far so good. Now the return jump? 144 145 (gdb) s 146 117 jmp [temp_return_addr] 147 (gdb) p/a (int)temp_return_addr 148 $2 = 0x80490df <inline_a_meow+16> 149 150 And just where might that be, exactly? 151 152 153 0x080490d4 <+5>: c7 05 19 a4 04 08 df 90 04 08 movl 154 $0x80490df, 0x804a419 155 0x080490de <+15>: eb 88 jmp 0x8049068 <find> 156 0x080490e0 <+17>: 50 push %eax 157 0x080490e1 <+18>: e8 57 ff ff ff call 0x804903d <inline> 158 159 Hmmm...looks off by 1. 0x80490df points to the second 160 byte of the jmp find instruction... 161 162 Program received signal SIGSEGV, Segmentation fault. 163 0x080490df in inline_a_meow () at meow5.asm:155 164 155 jmp find ; answer will be in eax 165 166 Yeah. So... 12 bytes? 167 168 And to think, I waxed all poetic about the NASM listing. 169 I don't know how to explain the byte discrepancy. Let's 170 see if this works: 171 172 (gdb) break find.found_it 173 Breakpoint 1, find.found_it () at meow5.asm:116 174 116 mov eax, edx ; pointer to tail of dictionary word 175 (gdb) s 176 117 jmp [temp_return_addr] 177 (gdb) s 178 inline_a_meow () at meow5.asm:156 179 156 push eax ; put it on the stack for inline 180 181 Yes! But that was evidently even _more_ fragile than I'd 182 expected. So I'll just bit the bullet and hold my nose 183 and use some temporary labels. It's still quite 184 compact, so I'll just paste it here: 185 186 push temp_meow_name ; the name string to find 187 mov dword [temp_return_addr], t1 188 jmp find ; answer will be in eax 189 t1: push eax ; put it on the stack for inline 190 mov dword [temp_return_addr], t2 191 jmp inline 192 t2: dec byte [meow_counter] 193 jnz inline_a_meow 194 195 ; inline exit 196 push temp_exit_name ; the name string to find 197 mov dword [temp_return_addr], t3 198 jmp find ; answer will be in eax 199 t3: push eax ; put it on the stack for inline 200 mov dword [temp_return_addr], t4 201 jmp inline 202 t4: 203 ; Run! 204 push 0 ; push exit code to stack for exit 205 jmp data_segment ; jump to the "compiled" program 206 207 Does it work? 208 209 dave@cygnus~/meow5$ mr 210 Meow. 211 Meow. 212 Meow. 213 Meow. 214 Meow. 215 216 Yes! 217 218 One last thing, now - 'find' is still leaving its answer 219 in the eax register. If I have it push the answer to the 220 stack instead, 'inline' will pop it and have what it 221 needs - no need for that "push eax" beween the two 222 functions/words (at labels t1 and t3 above). 223 224 Now find.not_found and find.found_it push their return 225 values on the stack: 226 227 .not_found: 228 push 0 ; return 0 to indicate not found 229 jmp [temp_return_addr] 230 231 .found_it: 232 push edx ; return pointer to tail of dictionary word 233 jmp [temp_return_addr] 234 235 And the calls simply flow one after the other without 236 any explicit data passing: 237 238 jmp find 239 t1: mov dword [temp_return_addr], t2 240 jmp inline 241 t2: ... 242 243 And does _that_ work? 244 245 dave@cygnus~/meow5$ mr 246 Meow. 247 Meow. 248 Meow. 249 Meow. 250 Meow. 251 252 Yes, and now I can check that little box at the top of 253 this log. We're doing pure stack-based concatenative 254 programming now. 255 256 Next step: 257 258 [x] Parse the string "meow meow meow meow meow exit" 259 as a program (pretend we're already in "compile 260 mode" and we're gathering word tokens and 261 compiling them) and execute it. 262 263 It begins! Here's the string in the .data segment: 264 265 input_buffer_start: 266 db 'meow meow meow meow meow exit', 0 267 input_buffer_end: 268 269 And here's the .bss segment "variables": 270 271 token_buffer: resb 32 ; For get_token 272 input_buffer_pos: resb 4 ; Save position of read tokens 273 274 Yup, just 32 chars for token names (well, 31 because I'm 275 null-terminating the string). Hey, it's my language. Ha 276 ha, I can always bump this up later. But 31 is actually 277 quite long, you know? 278 279 abcdefghijklmnopqrstuvwxyz01234 280 281 I've created a word called 'get_token' which will do the 282 job of both 'WORD' and 'KEY' in Forth. And I was just 283 about to 'call' it to test it, but I can't bear to put 284 in another manual temporary label 285 286 So, it's macro time! 287 288 %macro CALLWORD 1 289 mov dword [return_addr], %%return_to 290 jmp %1 291 %%return_to: 292 %endmacro 293 294 And it should be super easy to use. First, I'll test my 295 temporary "manual" 'meow' and 'exit' inlines to make 296 sure it works. They're about to go away, but they'll 297 make a good test. 298 299 Look at how clean the 'exit' one is: 300 301 push temp_exit_name ; the name string to find 302 CALLWORD find 303 CALLWORD inline 304 305 But does it work? 306 307 dave@cygnus~/meow5$ mr 308 Meow. 309 Meow. 310 Meow. 311 Meow. 312 Meow. 313 314 First try! No way. I mean, of _course_ it worked first 315 try and I never doubted it would. 316 317 Okay, now let's get into this get_token function: 318 319 (gdb) break get_next_token 320 Breakpoint 1 at 0x804912e: file meow5.asm, line 189. 321 (gdb) r 322 Starting program: /home/dave/meow5/meow5 323 324 Breakpoint 1, get_next_token () at meow5.asm:189 325 189 mov dword [return_addr], %%return_to ; CALLWORD 326 190 jmp %1 ; CALLWORD 327 150 mov ebx, [input_buffer_pos] ; set input read addr 328 151 mov edx, token_buffer ; set output write addr 329 152 mov ecx, 0 ; position index 330 154 mov al, [ebx + ecx] ; input addr + position index 331 155 cmp al, 0 ; end of input? 332 (gdb) p/c $al 333 $2 = 109 'm' 334 335 Nice! So the 'm' from the first 'meow' has been 336 collected so far. Now the rest of the token... 337 338 (gdb) break 155 339 Breakpoint 2 at 0x80490c7: file meow5.asm, line 155. 340 (gdb) c 341 155 cmp al, 0 ; end of input? 342 (gdb) p/c $al 343 $3 = 101 'e' 344 ... 345 $4 = 111 'o' 346 $5 = 119 'w' 347 $6 = 32 ' ' 348 349 We have 'meow' and the space should be our token 350 separator. 351 352 155 cmp al, 0 ; end of input? 353 156 je .end_of_input ; yes 354 157 cmp al, ' ' ; token separator? (space) 355 158 je .return_token ; yes 356 170 add [input_buffer_pos], ecx ; save input position 357 171 mov [edx + ecx], byte 0 ; terminate str null 358 359 Looks good. Did we collect 4 characters as expected? 360 361 (gdb) p $ecx 362 $7 = 4 363 364 Yup. Then get_token will "return" the token string 365 address so 'find' can use it to find the 'meow' word: 366 367 172 push DWORD token_buffer ; return str address 368 173 jmp [return_addr] 369 219 cmp DWORD [esp], 0 ; check return without popping 370 220 je run_it ; all out of tokens! 371 189 mov dword [return_addr], %%return_to ; CALLWORD 372 190 jmp %1 ; CALLWORD 373 96 pop ebp ; first param from stack! 374 find () at meow5.asm:99 375 99 mov edx, [last] 376 377 Okay, the execution looks right. And did we pass the 378 address correctly on the stack? 379 380 (gdb) p $ebp 381 $9 = (void *) 0x804a43d <token_buffer> 382 383 Yup! And does it contain the expected 'meow' token? 384 385 (gdb) x/s $ebp 386 0x804a43d <token_buffer>: "meow" 387 388 Nice! 389 390 I'm going to assume 'find' and 'inline' will work 391 correctly. Let's see if we can get the next token from 392 the input string: 393 394 (gdb) c 395 Continuing. 396 Breakpoint 2, get_token.get_char () at meow5.asm:155 397 155 cmp al, 0 ; end of input? 398 399 Alright, we're back in get_token. This should be the 400 first character of the second 'meow' token: 401 402 (gdb) p/c $al 403 $10 = 32 ' ' 404 405 Uh oh. That doesn't look right. I'll continue anyway... 406 407 (gdb) c 408 Continuing. 409 410 Program received signal SIGSEGV, Segmentation fault. 411 inline () at meow5.asm:76 412 76 mov ecx, [esi + 4] ; get len into ecx 413 414 Yeah, that makes sense. 'find' will have 415 failed to find the '' token and then 'inline' crashes when 416 trying to read from address 0 (the null pointer return 417 value from 'find'). 418 419 The best way to handle this is probably to ignore any 420 leading spaces - that will not only be useful later, it 421 will take care of this current character problem. 422 423 In a higher-level language, I might choose to do this 424 with nested logic, like so: 425 426 if (char === ' ') 427 if (token.len > 0) 428 'eat' space (move to next input char) 429 else 430 return the token 431 end 432 end 433 434 But in assembly, this all gets flattened. It's a 435 surprisingly interesting exercise to formulate the logic 436 in terms of jumps. (At least at first. I'm sure the 437 novelty wears off after a while.) 438 439 Anyway, here's my solution: 440 441 cmp al, ' ' ; token separator? (space) 442 jne .add_char ; nope! get char 443 cmp ecx, 0 ; yup! do we have a token yet? 444 je .eat_space ; no 445 jmp .return_token ; yes, return it 446 .eat_space: 447 inc ebx ; 'eat' space by advancing input 448 jmp .get_char 449 450 I'll make sure that works in GDB. I changed the input 451 string to: 452 453 db ' meow meow meow meow meow exit', 0 454 455 with a leading space and two spaces before the second 456 meow token. That'll make it easy to test: 457 458 155 cmp al, 0 ; end of input? 459 (gdb) p/c $al 460 $1 = 32 ' ' 461 157 cmp al, ' ' ; token separator? (space) 462 158 jne .add_char ; nope! get char 463 162 cmp ecx, 0 464 163 je .eat_space 465 171 inc ebx 466 172 jmp .get_char 467 468 Yup! That line 171 is my "eat the leading space" action 469 and now we should get the 'm' in "meow" and store it: 470 471 154 mov al, [ebx + ecx] ; input addr + position index 472 155 cmp al, 0 ; end of input? 473 156 je .end_of_input ; yes 474 (gdb) p/c $al 475 $2 = 109 'm' 476 157 cmp al, ' ' ; token separator? (space) 477 158 jne .add_char ; nope! get char 478 175 mov [edx + ecx], al ; write character 479 480 Yeah. This is looking good. 481 482 You know what? I'm just gonna go for it: 483 484 dave@cygnus~/meow5$ mr 485 Meow. 486 Meow. 487 Meow. 488 Meow. 489 Meow. 490 491 Yes! So that's another item checked off! 492 493 This is really coming along. 494 495 At nearly 500 lines, this log is complete. I'll see you 496 in the next one, log04.txt. :-)