1; Copyright 2005-2013, Ingo Weinhold, ingo_weinhold@gmx.de. 2; Distributed under the terms of the MIT License. 3; 4; Stage 1 boot code for the good (?) old BIOS for use as boot block of HD 5; partitions. The offset of the partition in 512 byte blocks must be written at 6; position PARTITION_OFFSET_OFFSET (32 bit little endian; makebootable does 7; that) or otherwise the code can't find the partition. 8; The partition must be BFS formatted. The haiku_loader hpkg file must be located 9; at "system/packages/haiku_loader*" and the haiku_loader.bios_ia32 must be the 10; first file in the haiku_loader package. 11; 12; The bios_ia32 stage 2 boot loader is loaded into memory at 0x1000:0x0000 13; (linear address 0x10000) and entered at 0x:1000:0x0200 with parameters 14; eax - partition offset in 512 byte blocks and dl - BIOS ID of the boot drive. 15; 16; Compile via: 17; nasm -f bin -O5 -o stage1.bin stage1.S 18 19; 1 enables more informative error strings, that shouldn't be seen by the 20; normal user, though. 21%assign DEBUG 0 22 23 24; address/offset definitions 25 26%assign BOOT_BLOCK_START_ADDRESS 0x7c00 27%assign STACK_ADDRESS BOOT_BLOCK_START_ADDRESS 28%assign READ_BUFFER_STACK STACK_ADDRESS - 0x2000 29%assign PARTITION_OFFSET_OFFSET 506 30%assign BFS_SUPERBLOCK_OFFSET 512 31 32 33; BFS definitions 34 35%define SUPER_BLOCK_MAGIC1 '1SFB' ; nasm reverses '...' consts 36%assign SUPER_BLOCK_MAGIC2 0xdd121031 37%assign SUPER_BLOCK_MAGIC3 0x15b6830e 38 39%assign INODE_MAGIC1 0x3bbe0ad9 40 41%assign NUM_DIRECT_BLOCKS 12 42 43%assign S_IFMT 00000170000o 44%assign S_IFDIR 00000040000o 45 46 47; BIOS calls 48 49%assign BIOS_VIDEO_SERVICES 0x10 50%assign BIOS_DISK_SERVICES 0x13 51%assign BIOS_KEYBOARD_SERVICES 0X16 52%assign BIOS_REBOOT 0X19 53 54; video services 55%assign WRITE_CHAR 0x0e ; al - char 56 ; bh - page? 57 58; disk services 59%assign READ_DISK_SECTORS 0x02 ; dl - drive 60 ; es:bx - buffer 61 ; dh - head (0 - 15) 62 ; ch - track 7:0 (0 - 1023) 63 ; cl - track 9:8, 64 ; sector (1 - 17) 65 ; al - sector count 66 ; -> al - sectors read 67%assign READ_DRIVE_PARAMETERS 0x08 ; dl - drive 68 ; -> cl - max cylinder 9:8 69 ; - sectors per track 70 ; ch - max cylinder 7:0 71 ; dh - max head 72 ; dl - number of drives (?) 73%assign CHECK_DISK_EXTENSIONS_PRESENT 0x41 ; bx - 0x55aa 74 ; dl - drive 75 ; -> success: carry clear 76 ; ah - extension version 77 ; bx - 0xaa55 78 ; cx - support bit mask 79 ; -> error: carry set 80%assign EXTENDED_READ 0x42 ; dl - drive 81 ; ds:si - address packet 82 ; -> success: carry clear 83 ; -> error: carry set 84 85%assign FIXED_DISK_SUPPORT 0x1 ; flag indicating fixed disk 86 ; extension command subset 87 88; keyboard services 89%assign READ_CHAR 0x00 ; -> al - ASCII char 90 ; ah - scan code 91 92 93; nasm (0.98.38) doesn't seem to know pushad. popad works though. 94%define pushad db 0x66, 0x60 95 96 97; 16 bit code 98SECTION .text 99BITS 16 100ORG BOOT_BLOCK_START_ADDRESS ; start code at 0x7c00 101 102; nicer way to get the size of a structure 103%define sizeof(s) s %+ _size 104 105; using a structure in a another structure definition 106%macro nstruc 1-2 1 107 resb sizeof(%1) * %2 108%endmacro 109 110; 64 bit value 111struc quadword 112 .lower resd 1 113 .upper resd 1 114endstruc 115 116; address packet as required by the EXTENDED_READ BIOS call 117struc AddressPacket 118 .packet_size resb 1 119 .reserved1 resb 1 120 .block_count resb 1 121 .reserved2 resb 1 122 .buffer resd 1 123 .offset nstruc quadword 124; .long_buffer nstruc quadword 125 ; We don't need the 64 bit buffer pointer. The 32 bit .buffer is more 126 ; than sufficient. 127endstruc 128 129; BFS block run 130struc BlockRun 131 .allocation_group resd 1 132 .start resw 1 133 .length resw 1 134endstruc 135 136; BFS superblock 137struc SuperBlock 138 .name resb 32 139 .magic1 resd 1 140 .fs_byte_order resd 1 141 .block_size resd 1 142 .block_shift resd 1 143 .num_blocks nstruc quadword 144 .used_blocks nstruc quadword 145 .inode_size resd 1 146 .magic2 resd 1 147 .blocks_per_ag resd 1 148 .ag_shift resd 1 149 .num_args resd 1 150 .flags resd 1 151 .log_blocks nstruc BlockRun 152 .log_start nstruc quadword 153 .log_end nstruc quadword 154 .magic3 resd 1 155 .root_dir nstruc BlockRun 156 .indices nstruc BlockRun 157 .pad resd 8 158endstruc 159 160; BFS inode data stream 161struc DataStream 162 .direct nstruc BlockRun, NUM_DIRECT_BLOCKS 163 .max_direct_range nstruc quadword 164 .indirect nstruc BlockRun 165 .max_indirect_range nstruc quadword 166 .double_indirect nstruc BlockRun 167 .max_double_indirect_range nstruc quadword 168 .size nstruc quadword 169endstruc 170 171; BFS inode (shortened) 172struc BFSInode 173 .magic1 resd 1 174 .inode_num nstruc BlockRun 175 .uid resd 1 176 .gid resd 1 177 .mode resd 1 178 .flags resd 1 179 .create_time nstruc quadword 180 .last_modified_time nstruc quadword 181 .parent nstruc BlockRun 182 .attributes nstruc BlockRun 183 .type resd 1 184 .inode_size resd 1 185 .etc resd 1 186 .data nstruc DataStream 187 ; ... 188endstruc 189 190; BFS B+ tree node 191struc BPlusTreeNode 192 .left_link nstruc quadword 193 .right_link nstruc quadword 194 .overflow_link nstruc quadword 195 .all_key_count resw 1 196 .all_key_length resw 1 197endstruc 198 199; The beginning of a HPKG header 200struc HPKGHeader 201 .magic resd 1 202 .header_size resw 1 203 ; ... 204 205; That's what esp points to after a "pushad". 206struc PushadStack 207 .edi resd 1 208 .esi resd 1 209 .ebp resd 1 210 .tmp resd 1 ; esp 211 .ebx resd 1 212 .edx resd 1 213 .ecx resd 1 214 .eax resd 1 215endstruc 216 217; helper macro for defining static variables 218%macro define_static_var 1 219 %define %1 static_variables + StaticVariables. %+ %1 220%endmacro 221 222; Structure containing the static variables we use (the ones that don't need 223; pre-initialization at least). By using this structure we can easily place 224; them onto our "heap". 225struc StaticVariables 226 .bios_drive_id resd 1 227 .address_packet nstruc AddressPacket 228 .write_int32_buffer resb 32 229 .inode resb 512 230 .indirect_block resb 512 231 .buffer resb 1024 232endstruc 233 234; define short names for our static variables 235define_static_var bios_drive_id 236define_static_var write_int32_buffer 237define_static_var address_packet 238define_static_var inode 239define_static_var indirect_block 240define_static_var buffer 241 242; Macro for defining a string prefixed by a byte containing its length. Used 243; for the list of components of the path to the stage 2 boot loader. 244%macro pathComponent 1 245 %strlen .componentLen %1 246 db .componentLen 247 db %1 248%endmacro 249 250; macro to be invoked in case of error -- parameter is the error string 251%macro error 1 252 %if DEBUG 253 mov si, %1 254 %else 255 mov si, kErrorString 256 %endif 257 jmp _error 258%endmacro 259 260 261start: 262 ; set ds, es, ss to the value of cs (which is 0x0000) 263 push cs 264 pop ds 265 push cs 266 pop es 267 268 push cs ; setup stack 269 pop ss 270 mov sp, STACK_ADDRESS 271 272 cli ; disable interrupts 273 cld ; clear direction flag (for string ops) 274 275 ; save the BIOS drive ID 276 mov [bios_drive_id], dl 277 278 ; check for BIOS int 0x13 (disk services) extensions 279 mov ah, CHECK_DISK_EXTENSIONS_PRESENT 280 mov bx, 0x55aa 281 ; dl has not changed yet, still contains the drive ID 282 int BIOS_DISK_SERVICES 283 284 jc .no_disk_extensions ; error 285 286 cmp bx, 0xaa55 287 jne .no_disk_extensions ; call not supported? 288 289 test cl, FIXED_DISK_SUPPORT 290 jz .no_disk_extensions 291 292 ; we have disk extensions 293 mov byte [sHasDiskExtensions], 1 294 295.no_disk_extensions: 296 297 ; read in our second half 298 xor eax, eax ; block offset (1) to eax 299 inc ax 300 lea ebp, [second_boot_block] ; buffer to ebp 301 302 call readOneBlock 303 304 ; check superblock magic 305 cmp dword [superblock + SuperBlock.magic1], SUPER_BLOCK_MAGIC1 306 je .valid_superblock_magic 307 308 error kBadSuperBlockMagicString 309 310.valid_superblock_magic: 311 jmp continueMain 312 313 314; Jumped to in case of error. si must contain the pointer to the error string. 315_error: 316 call _writeString 317 318 ; wait for a key and reboot 319 mov ah, READ_CHAR 320 int BIOS_KEYBOARD_SERVICES 321 int BIOS_REBOOT 322 323 324; _writeString 325; Prints a string to the screen. 326; [entry] 327; si: pointer to null terminated string 328; [exit] 329; trashes: si, ax 330_writeString: 331.loop: 332 lodsb ; al <- [si++] 333 or al, al 334 jz .loopend 335 336 mov ah, WRITE_CHAR 337 int BIOS_VIDEO_SERVICES 338 339 jmp .loop 340.loopend: 341 342 ret 343 344 345; readOneBlock 346; Reads one disk block from the given offset into the specified buffer. 347; [entry] 348; eax: block offset 349; ebp: buffer address 350; [exit] 351; trashes: di 352readOneBlock: 353 mov di, 1 354 ; fall through ... 355 356 357; readBlocks 358; Reads one or more disk blocks from the given offset into the specified buffer. 359; [entry] 360; eax: block offset 361; di: block count 362; ebp: buffer address 363readBlocks: 364 pushad 365 366 ; add the partition offset 367 add dword eax, [kPartitionOffset] 368 369 ; drive ID to dl 370 mov dl, [bios_drive_id] 371 372 cmp byte [sHasDiskExtensions], 0 373 jz .no_extension_support 374 375 ; set packet size, block count, and buffer in the address packet 376 mov word [address_packet + AddressPacket.packet_size], \ 377 sizeof(AddressPacket) 378 mov [address_packet + AddressPacket.block_count], di 379 mov [address_packet + AddressPacket.buffer], ebp 380 381 ; write the block offset to the address packet 382 mov dword [address_packet + AddressPacket.offset + quadword.lower], eax 383 xor eax, eax 384 mov dword [address_packet + AddressPacket.offset + quadword.upper], eax 385 386 ; do the "extended read" call 387 ; address packet address in si 388 mov si, address_packet 389 mov ah, EXTENDED_READ 390 int BIOS_DISK_SERVICES 391 392 jnc .no_error ; error? 393 394.read_error: 395 error kReadErrorString 396 397.no_extension_support: 398 ; no fixed disk extension support 399 400 ; save parameters 401 push eax 402 403 ; read drive parameters 404 mov ah, READ_DRIVE_PARAMETERS 405 int BIOS_DISK_SERVICES 406 jc .read_error 407 408 ; -> cl - max cylinder 9:8 409 ; - sectors per track 410 ; ch - max cylinder 7:0 411 ; dh - max head 412 413 ; compute sectors 414 pop eax ; LBA 415 xchg dl, dh ; max head to dx 416 xor dh, dh ; 417 push dx ; save max head 418 xor edx, edx 419 and ecx, 0x3f ; filter sectors per track 420 div ecx ; divide by sectors per track 421 422 inc dl ; sector numbering starts with 1 423 pop cx ; restore max head 424 push dx ; save sector 425 426 ; compute heads and cylinders 427 xor dx, dx 428 xor ch, ch ; cl only 429 inc cx ; max head -> head count 430 div cx ; divide by head count 431 ; result: ax: cylinder, dx: head 432 433 ; we need to shuffle things a bit 434 or dh, dl ; head 435 436 mov cx, ax 437 xchg cl, ch ; ch: 7:0 cylinder 438 ror cl, 2 ; cl: 9:8 cylinder in bits 7:6 439 pop dx ; restore sector 440 or cl, dl ; cl: 9:8 cylinder, 5:0 sector 441 442 ; buffer address must be in es:bx 443 mov eax, ebp ; count 444 shr eax, 16 445 push es ; save es 446 push ax 447 pop es 448 mov bx, bp 449 450 ; block count to ax 451 mov ax, di ; count 452 453 mov dl, [bios_drive_id] 454 mov ah, READ_DISK_SECTORS 455 int BIOS_DISK_SERVICES 456 457 pop es ; restore es 458 459 cmp ax, di 460 jne .read_error 461 462.no_error: 463 popad 464 465 ret 466 467 468; readBuffer 469; Reads the next 1024 bytes from the data of the current inode (the one read 470; with the last call to readInode) into a buffer. The function uses an own stack 471; which it switches to at the beginning (switching back at the end). This 472; custom stack is initially in an "after pushad" state. The functions does a 473; popad at the beginning and pushad at the end, thus keeping its register 474; configuration between calls (see some lines below for the meaning of the 475; registers). readBufferInit must be called before the first call to readBuffer 476; for a node. After that manipulating the parameters (registers) of the 477; function can be done by accessing the respective values on the custom stack. 478; [exit] 479; ax: 0x0000 - nothing read (end of file/directory) 480; 0x0001 - read one buffer 481readBuffer: 482 xor ax, ax ; the default result (end) 483 pushad 484 485 ; set our custom stack and get our registers 486 xchg sp, [sReadBufferStack] 487 popad 488 489 ; registers: 490 ; eax - read offset 491 ; ecx - blocks left of the current block run 492 ; edx - max remaining block runs 493 ; ebp - pointer to the read buffer 494 ; si - pointer to the current block run 495 ; edi - index of the current indirect block 496 ; bx - remaining indirect blocks 497 498 and ecx, ecx 499 jg .blocks_left_valid 500 501 ; blocks_left <= 0: decrement remaining block run index 502 dec dl 503 jge .next_block_run 504 505.next_indirect_block: 506 ; no more block runs: decrement remaining indirect block count 507 dec bx 508 jl .nothing_read 509 510 ; there are more indirect blocks: read the next one 511 ; get the buffer address to esi first 512 xor esi, esi 513 lea si, [indirect_block] 514 515 ; read the block 516 pushad 517 xchg eax, edi ; block index to eax 518 mov ebp, esi ; buffer pointer to ebp 519 520 call readOneBlock 521 522 popad 523 524 ; increment the indirect block index 525 inc edi 526 527 ; maximal number of block runs in this block to edx 528 xor edx, edx 529 mov dl, 512 / sizeof(BlockRun) 530 531.next_block_run: 532 ; convert block run to disk block offset 533 call blockRunToDiskBlock 534 535 and eax, eax 536 jz .next_indirect_block 537 538.more_blocks: 539 ; compute blocks_left 540 xchg eax, ecx ; save eax 541 movzx eax, word [si + BlockRun.length] ; length to eax 542 call bfsBlockToDiskBlock ; convert 543 xchg eax, ecx ; blocks_left now in ecx 544 545 ; move to the next block run 546 add si, sizeof(BlockRun) 547 548.blocks_left_valid: 549 ; we'll read 2 disk blocks: so subtract 2 from blocks_left 550 sub ecx, 2 551 552 push edi ; save edi -- we use it for other stuff for the 553 ; moment 554 555 mov di, 2 556 557 call readBlocks 558 559 ; adjust read_offset 560 add eax, 2 561 562 ; success 563 mov di, [sReadBufferStack] 564 mov byte [di + PushadStack.eax], 1 565 566 pop edi ; restore edi 567 568.nothing_read: 569 pushad 570 xchg sp, [sReadBufferStack] 571 popad 572 ret 573 574 575; readBufferInit 576; Initializes readBuffer's context for the current inode (the one read with 577; the last call to readInode). Must be called before the first call to 578; readBuffer for an inode. 579readBufferInit: 580 ; switch to readBuffer context 581 pushad 582 xchg sp, [sReadBufferStack] 583 popad 584 585 ; clear the number of indirect blocks, for the case there aren't any 586 xor bx, bx 587 588 ; check whether there are indirect blocks (max_indirect_range != 0) 589 lea si, [inode + BFSInode.data + DataStream.max_indirect_range] 590 cmp dword [si], 0 591 jnz .has_indirect_blocks 592 cmp dword [si + 4], 0 593 jz .no_indirect_blocks 594 595.has_indirect_blocks: 596 ; get the first indirect block index 597 lea si, [inode + BFSInode.data + DataStream.indirect] 598 call blockRunToDiskBlock 599 600 and eax, eax 601 jz .no_indirect_blocks 602 603 ; indirect block index to edi 604 xchg edi, eax 605 606 ; get number of indirect blocks 607 movzx eax, word [si + BlockRun.length] 608 call bfsBlockToDiskBlock 609 xchg bx, ax ; number to bx 610 611.no_indirect_blocks: 612 613 ; blocks_left = 0, max_remaining_direct_block_runs = NUM_DIRECT_BLOCKS 614 xor ecx, ecx 615 mov dl, NUM_DIRECT_BLOCKS 616 617 ; position si at the 1st block run 618 lea si, [inode + BFSInode.data + DataStream.direct] 619 620 ; buffer address 621 xor ebp, ebp 622 mov bp, buffer 623 624 ; switch context back (use readBuffer's code) 625 jmp readBuffer.nothing_read 626 627 628; data 629 630; the custom stack for readBuffer 631sReadBufferStack dw READ_BUFFER_STACK - sizeof(PushadStack) 632 ; already start in "after pushad" state 633sHasDiskExtensions db 0 ; 1 if the drive supports the extended read 634 ; BIOS call. 635 636; error strings 637; If DEBUG is enabled, we use more descriptive ones. 638%if DEBUG 639kReadErrorString db "read error", 0 640kBadSuperBlockMagicString db "bad superblock", 0 641kNotADirectoryString db "not a directory", 0 642kBadInodeMagicString db "bad inode", 0 643kNoZbeosString db "no loader", 0 644%else 645kErrorString db "bios_ia32 stage1: Failed to load OS. Press any key to reboot..." 646 db 0 647%endif 648 649kPathComponents: 650pathComponent "system" 651pathComponent "packages" 652kLastPathComponent: 653pathComponent "haiku_loader" 654 db 0 655 656 657 658first_code_part_end: 659 660; The first (max) 512 - 4 -2 bytes of the boot code end here 661; --------------------------------------------------------------------------- 662 663 %if first_code_part_end - start > PARTITION_OFFSET_OFFSET 664 %error "Code exceeds first boot code block!" 665 %endif 666 667 ; pad to the partition offset 668 %rep start + PARTITION_OFFSET_OFFSET - first_code_part_end 669 db 0 670 %endrep 671 672kPartitionOffset dd 0 673kBootBlockSignature dw 0xaa55 674 675 676second_boot_block: 677 678; first comes the BFS superblock 679superblock: 680 %rep sizeof(SuperBlock) 681 db 0 682 %endrep 683 684 685; the second part of the boot block code 686 687; readBootLoader 688; Jumped to when all path components to the stage 2 boot loader have been 689; resolved and the current inode is the one of the boot loader. The boot 690; loader will be read into memory and jumped into. 691readBootLoader: 692 ; prepare for the first call to readBuffer 693 call readBufferInit 694 695 ; the destination address: start at the beginning of segment 0x1000 696 mov ecx, 0x10000000 697 mov edi, ecx ; 0x1000:0000 698 699 xor ebx, ebx 700 mov bx, [sReadBufferStack] 701 702.read_loop: 703 ; write destination address 704 mov [bx + PushadStack.ebp], edi 705 706 ; compute next destination address 707 add di, 1024 708 jnc .no_carry 709 add edi, ecx ; the lower 16 bit wrapped around: add 0x1000 710 ; (64 KB) to the segment selector 711.no_carry: 712 713 call readBuffer 714 715 ; loop as long as reading succeeds 716 and ax, ax 717 jnz .read_loop 718 719 ; We have successfully read the complete boot loader package. The actual 720 ; code is located at the beginning of the package file heap which starts 721 ; directly after the header. Since the boot loader code expects to be 722 ; located at a fixed address, we have to move it there. 723 724 ; First set up the source and target segment registers. We keep the current 725 ; value also in bx, since it is easier to do arithmetics with it. We keep 726 ; the increment value for the segment registers in dx. 727 mov bx, 0x1000 ; initial ds and es value 728 push bx 729 pop ds 730 push bx 731 pop es 732 mov dx, bx ; the increment value for the segment registers 733 734 ; Determine how much we have to copy and from where to where. si will be 735 ; the source and di the destination pointer (both segment relative) and 736 ; ecx is our byte count. To save instructions we only approximate the count. 737 ; It may be almost a full segment greater than necessary. But that doesn't 738 ; really harm. 739 mov ecx, edi 740 shr ecx, 12 ; byte count 741 xor di, di ; target 742 mov ax, [di + HPKGHeader.header_size] ; header size (big endian) 743 xchg ah, al 744 mov si, ax ; source 745 746.move_loop: 747 movsb 748 test si, si 749 jnz .move_no_source_overflow 750 add bx, dx 751 push bx 752 pop ds 753.move_no_source_overflow: 754 test di, di 755 jnz .move_no_destination_overflow 756 push bx 757 pop es 758 ; Using bx (the value of ds) is fine, since we assume that the 759 ; source is less than a segment ahead of the destination. 760.move_no_destination_overflow: 761 dec ecx 762 jnz .move_loop 763 764 ; We have successfully prepared the boot loader code. Set up the 765 ; environment for it. 766 ; eax - partition offset in sectors 767 push cs 768 pop ds 769 ; temporarily reset ds, so we can access our variables 770 mov dword eax, [kPartitionOffset] 771 772 ; dl - BIOS drive ID 773 xor edx, edx 774 mov dl, [bios_drive_id] 775 776 ; Note: We don't have to set ds and es, since the stage 2 sets them 777 ; anyway before accessing any data. 778 779 ; enter the boot loader 780 jmp 0x1000:0x200 781 782 783; continueMain 784; Continues the "main" function of the boot code. Mainly contains the loop that 785; resolves the path to the stage 2 boot loader, jumping to readBootLoader when 786; it was found. 787continueMain: 788 789 ; load root node 790 ; convert root node block run to block 791 lea si, [superblock + SuperBlock.root_dir] 792 call blockRunToDiskBlock 793 794 call readInode 795 796 ; stack: 797 ; word number of keys (in .key_loop) 798 ; word previous key length (in .key_loop) 799 800 ; registers: 801 ; di - path component (in .search_loop) 802 ; cx - path component length (in .search_loop) 803 ; ax - remaining key count (-1) (in .key_loop) 804 ; bx - key lengths array (current pos) (in .key_loop) 805 ; dx - previous absolute key length (in .key_loop) 806 ; si - current key (in .key_loop) 807 ; bp - current key length (in .key_loop) 808 809 lea di, [kPathComponents] 810 811.search_loop: 812 ; the path component we're looking for 813 xor cx, cx 814 mov cl, [di] ; the path component length 815 inc di ; the path component itself 816 and cl, cl 817 jz readBootLoader ; no more path components: We found the boot 818 ; loader! Now read it in. 819 820.continue_search: 821 ; is a directory? 822 mov eax, [inode + BFSInode.mode] 823 and eax, S_IFMT 824 cmp eax, S_IFDIR 825 je .is_directory 826 827 error kNotADirectoryString 828 829.is_directory: 830 ; prepare for the first call to readBuffer 831 call readBufferInit 832 833 ; we skip the first 1024 bytes (that's the b+tree header) 834 call readBuffer 835 and ax, ax 836 jnz .read_loop 837 838.not_found: 839 error kNoZbeosString 840 841.read_loop: 842 843 ; read the next B+ tree node 844 call readBuffer 845 and ax, ax 846 jz .not_found 847 848 ; we're only interested in leaf nodes (overflow_link == -1) 849 xor eax, eax 850 dec eax 851 cmp [buffer + BPlusTreeNode.overflow_link + quadword.lower], eax 852 jne .read_loop 853 cmp [buffer + BPlusTreeNode.overflow_link + quadword.upper], eax 854 jne .read_loop 855 856 ; get the keylengths and keys 857 858 ; the keys 859 lea si, [buffer + sizeof(BPlusTreeNode)] 860 861 ; the keylengths array 862 mov bx, [buffer + BPlusTreeNode.all_key_length] 863 add bx, sizeof(BPlusTreeNode) + 7 864 and bl, 0xf8 865 add bx, buffer 866 867 ; number of keys 868 mov ax, [buffer + BPlusTreeNode.all_key_count] 869 push ax 870 871 ; the "previous" key length 872 push word 0 873 874.key_loop: 875 ; while there are more keys 876 dec ax 877 jl .key_loop_end 878 879 ; get current key length 880 mov bp, [bx] 881 882 ; exchange previous key length on the stack and compute the actual 883 ; length (the key lengths array contains summed-up lengths) 884 pop dx 885 push bp 886 sub bp, dx 887 888 ; Compare the key length. For the last component we only want to check 889 ; whether the prefix matches. 890 cmp cx, bp 891 jg .skip_key 892 893 cmp di, kLastPathComponent + 1 894 je .compare_keys 895 896 cmp cx, bp 897 jne .skip_key 898 899 ; compare path component (di) with key (si), length cx (<= bp) 900.compare_keys: 901 pusha 902 repe cmpsb 903 popa 904 905 jne .skip_key 906 907 ; keys are equal 908 909 ; get the current index 910 pop dx ; pop previous key length 911 pop dx ; key count 912 inc ax ; ax is decremented already at the loop top 913 sub dx, ax ; the current index 914 915 ; get to the end of the key lengths array 916 shl ax, 1 ; number of bytes remaining in the array 917 add bx, ax 918 shl dx, 3 ; offset in the value (block number) array 919 add bx, dx ; bx now points to the block number of the inode 920 921 ; read the block offset and load the Inode 922 mov eax, [bx] 923 call bfsBlockToDiskBlock 924 925 call readInode 926 927 ; next path component 928 add di, cx 929 jmp .search_loop 930 931.skip_key: 932 inc bx ; next key length 933 inc bx 934 add si, bp ; next key 935 jmp .key_loop 936 937.key_loop_end: 938 ; all keys check, but nothing found: need to read in the next tree node 939 pop dx ; pop previous key length 940 pop dx ; pop key count 941 jmp .read_loop 942 943 944; readInode 945; Reads the inode at the specified disk block offset into the buffer "inode". 946; [entry] 947; eax: disk block offset 948readInode: 949 pushad 950 951 ; buffer address to ebp 952 xor ebp, ebp 953 mov bp, inode 954 955 ; An inode is actually one BFS block big, but we're interested only in the 956 ; administrative part (not the small data section), which easily fits into 957 ; one disk block. 958 call readOneBlock 959 960 cmp dword [inode + BFSInode.magic1], INODE_MAGIC1 961 je .no_error 962 963 error kBadInodeMagicString 964 965.no_error: 966 popad 967 968 ret 969 970 971; blockRunToDiskBlock 972; Computes the start address (in disk blocks) of a given BFS block run. 973; [entry] 974; si: pointer to the BlockRun 975; [exit] 976; eax: disk block number, where the block run begins 977blockRunToDiskBlock: 978 push ecx 979 980 ; run.allocation_group << superblock.ag_shift 981 mov cl, [superblock + SuperBlock.ag_shift] 982 mov eax, [si + BlockRun.allocation_group] 983 shl eax, cl 984 985 ; add run.start 986 xor ecx, ecx 987 mov cx, [si + BlockRun.start] 988 989 add eax, ecx 990 991 pop ecx 992 993 ; Fall through to bfsBlockToDiskBlock, which will convert the BFS block 994 ; number to a disk block number and return to our caller. 995 996 997; bfsBlockToDiskBlock 998; Converts a BFS block number to a disk block number. 999; [entry] 1000; eax: BFS block number 1001; [exit] 1002; eax: disk block number 1003bfsBlockToDiskBlock: 1004 push cx 1005 1006 ; 1 BFS block == superblock_block_size / 512 disk blocks 1007 mov byte cl, [superblock + SuperBlock.block_shift] 1008 sub cl, 9 1009 1010 shl eax, cl 1011 1012 pop cx 1013 ret 1014 1015 1016%if 0 1017; _writeInt32 1018; Writes the given number in 8 digit hexadecimal representation to screen. 1019; Used for debugging only. 1020; [entry] 1021; eax: The number to print. 1022_writeInt32: 1023 pushad 1024 1025 mov bx, write_int32_buffer 1026 mov byte [bx + 8], 0 ; terminating null 1027 mov di, 7 1028 1029.loop: 1030 ; get the lowest hex digit 1031 mov dx, ax 1032 and dl, 0xf 1033 1034 ; convert hex digit to character 1035 cmp dl, 10 1036 jl .digit 1037 add dl, 'a' - '0' - 10 1038 1039.digit: 1040 add dl, '0' 1041 1042 ; prepend the digit to the string 1043 mov [bx + di], dl 1044 1045 ; shift out lowest digit and loop, if there are more digits 1046 shr eax, 4 1047 dec di 1048 jge .loop 1049 1050 ; write the composed string 1051 xchg bx, si 1052 call _writeString 1053 1054 popad 1055 ret 1056%endif 1057 1058 1059; check whether we are small enough 1060end: 1061 %if end - start > 1024 1062 %error "Code exceeds second boot code block!" 1063 %endif 1064 1065; pad to 1024 bytes size 1066 %rep start + 1024 - end 1067 db 0 1068 %endrep 1069 1070; Base offset for static variables. 1071static_variables: 1072