Microsoft PowerPoint - 系統程式 PDF Free Download

TAMKANG UNIVERSITY SOFTWARE ENGINEERING GROUP 系統程式淡江大學資訊工程系教授王英宏 2010/2/23 授課方式與成績考核上課方式板書為主投影片相輔隨堂作業與小考, 隨堂作業為主隨時自備 A4 紙上課規定手機請改設震動或關機不要私下講話鼓勵提問教材教科本 System Software Beck 台北圖書 02-23625376 成績考核出席 :15% 助教 :20% 作業 :30% 期中考試 :15% 期末考試 :20% 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 2 1

授課方式與成績考核成績評定出席 : 15% 實習課 : 20% 作業 + 程式 : 30% 期中考 : 15% 期末考 : 20% 點名成績係用以區隔同學每週出席與否的成績, 故不接受各種形式未出席的原因, 但每人可以有三次的緩衝機會, 以因應不可抗拒的情況缺席超過三次者, 才開始扣分, 反之, 缺席少於三次者, 可以獲得加分每週點名一次, 點名超過一次者, 即為加分點名, 不在前述 100% 內累計正規點名可以接受補點, 加分點名則不接受補點期末考比校訂時間提前一週指派聆聽演講之出席, 每場加一分 ( 採外加計分 ) 除隨堂作業與上機驗收作業外, 其餘作業可接受補交, 自繳交截止時間點起, 每 24 小時內補交者扣 10 分, 扣至 0 分為止請助教作業每次發還後隨即公佈登錄資料以供核對, 有疑義者須於一週內完成補正, 逾期不再受理 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 3 課程內容正課部份 Introduction Platform Architecture Assembler Loader and Linker Macro Processor 助教部份作業系統 (Operating System) 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 4 2

哈佛大學圖書館自習室座右銘此刻打盹, 你將做夢 ; 此刻學習, 你將圓夢學習時的苦痛是暫時的, 未學到的痛苦是終生的現在睡覺流的口水, 將成為明天的眼淚 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 5 課程結構 Assembly Programs Assembler High Level Language Programs Complier or Interpreter Executable Programs or Instructions Linker and Loader Operating System and Drivers Hardware Platform 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 6 3

Introduction What is System Software(System Programming) Assembler Loader Macro processor Compiler Operating System Data Base Management System User Interface Shell 本課程目的在於介紹上述軟體的各型態類別與設計方法 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 7 系統軟體的共同特徵 What is the difference between System Software and Application Software Machine Dependent Reason How to learn those various types of System Software 異中求同 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 8 4

Platform Architecture SIC Simple Instructional Computer A standard Model 具有一般電腦大部分的 Hardware features and concepts 類似典型的 Microcomputer SIC/XE extra Equipment model of SIC a extended model 由 SIC 的標準 Model 加以功能擴充, 藉以了解系統軟體在面臨硬體差異時, 設計上的調整 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 9 SIC 的硬體特徵 Memory Structure 8-bits Byte 3-bytes Word Max. Memory size: 2 15 = 32,768 bytes Byte address: memory address 是以一個 byte 為單位, 每個 byte 賦予一個位址編號 Word address 是以三個連續 bytes 中最低的 byte, 亦即位址最小的 byte address 為 word 的 address 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 10 5

SIC 的硬體特徵 ( 續 ) Register 5 個特定用途的暫存器每個 Register 容量為 24 bits (3 bytes, one word) 助憶符號編號及功能如下 : M nem onic N um ber Special U se A 0 A ccum ulator; used for arithm etic operations X 1 Index register; used for addressing L 2 Linkage register; used for the JSU B instruction stores the return address PC 8 Program Counter; contains the address of next instruction SW 9 Status W ord; conatins a variety of inform ation 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 11 SIC 的硬體特徵 ( 續 ) Data Format Integer: 24-bit binary number 負數 :2 s complement Character: 8-bit ASCII codes No floating -point number Instruction Format Only one format: two types of addressing 8 Opcode 1 15 X Address X: is used to indicate indexed -addressing mode; 0: direct, 1: indexed 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 12 6

SIC 的硬體特徵 ( 續 ) Addressing Mode Direct: TA = address of Instruction Format Indexed: TA = address + (X) TA: Target address Instruction Set Register s Load & Store: LDA, STA,, LDX, STX,.etc. Integer Arithmetic: ADD, SUB, MUL, DIV, etc. Compare register A with a Word in memory: COMP Conditional Jump: JLT, JEQ, JGT, etc. Subroutine Call and Return: JSUB and RSUB 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 13 SIC 的硬體特徵 ( 續 ) Input/Output 只允許一次一個 byte 的輸入輸出 TD: Test Device RD: Read Data from Device WD: Write Data to Device Complete Instruction Set of SIC and SIC/XE Appendix A, page 496 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 14 7

SIC/XE 的硬體特徵 Memory Structure Same as SIC Max. memory size is 2 20 = 1M bytes Registers: Five registers are same as SIC Four another register as following: M nem onic N um ber Special U se B 3 B ase reg ister; u sed fo r ad d ressin g S 4 G e n e r a l d a t a r e g i s t e r ; n o s p e c i a l u s e T 5 G e n e r a l d a t a r e g i s t e r ; n o s p e c i a l u s e F 6 F lo a tin g p o in t a c c u m u la to r (4 8 b its) 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 15 SIC/XE 的硬體特徵 ( 續 ) Data Format Integer data type, Negative representation, Character data type are same as SIC Floating-point data type: 48 bits, format is shown as following: 1 11 36 S Exponent Fraction The range is ±.F 2 (E 1024), where bit S = 0 means positive, else means negative. F is the value of Fraction, E is the value of Exponent 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 16 8

SIC/XE 的硬體特徵 ( 續 ) Instruction Formats There are Four types of instruction format of SIC/XE 8 Format 1: (1 byte) OP Format 2: (2 bytes) Format 3: (3 bytes) Format 4: (4 bytes) 8 OP 6 OP 6 OP 4 4 r1 n 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 17 r2 1 1 1 1 1 1 12 n i x b p e Disp 1 1 1 1 1 1 20 i x b p e address Bit e presents format 3 or 4, when e=0 is format 3, e=1 is format 4 SIC/XE 的硬體特徵 ( 續 ) Addressing modes There are Four types of addressing mode, they are Relative addressing mode, they can divide into three categories: Index relative: TA = (X) + Disp Base relative: TA = (B) + Disp, (0 Disp 4095) Program counter relative: TA = (PC) + Disp (-2048 Disp 2047) Where Index relative can be combined with Base relative or Program counter relative. However, Base relative and Program counter relative are mutual exclusive Direct addressing mode: TA = address Immediate addressing mode: (TA) = Disp or address Indirect addressing mode: TA = (address) 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 18 9

SIC/XE 的硬體特徵 ( 續 ) The relationship between Addressing modes and bits n, i, x, b, p, e n = 1, i = 1, for relative or direct addressing modes Index relative: x = 1 Base relative: b = 1, and p = 0 Program counter relative: b = 0, and p = 1 Direct addressing mode: b = 0, and p = 0 Immediate addressing mode: n = 0, and i = 1 Indirect addressing mode: n = 1, and i = 0 Immediate / Indirect addressing mode can combine with relative addressing mode n = 0 and i = 0 means this is a instruction belongs to SIC, not SIC/XE 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 19 Examples of addressing modes of SIC/XE Memory Address 3030 3600 Contents 003600 103000 6390 C303 Machine Instruction Value Loaded Hex Binary Target Addr. in reg. A OP n i x b p e Disp/address 032600 000000 1 1 0 0 1 0 0110 0000 0000 3600 103000 03C300 000000 1 1 1 1 0 0 0011 0000 0000 6390 00C303 022030 000000 1 0 0 0 1 0 0000 0011 0000 (3030) 103000 010030 000000 0 1 0 0 0 0 0000 0011 0000 000030 003600 000000 0 0 0 0 1 1 0110 0000 0000 3600 103000 0310C303 000000 1 1 0 0 0 1 0000 1100 0011 0000 0011 C303 003030 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 20 00C303 003030 Register Content (B) = 006000 (PC) = 003000 (X) = 000090 10

SIC/XE 的硬體特徵 ( 續 ) Instruction Set of SIC/XE All instructions present in SIC Another new instruction set includes New Register load and store operations: LDB, STS, etc. Floating-point arithmetic: ADDF, SUBF, DIVF, MULF Register to Register moving: RMO Register to register arithmetic: ADDR, SUBR, MULR, DIVR Supervisor Call: SVC Input/Output Using byte stream is same as SIC SIC/XE provides I/O instructions for I/O channel, they are SIO: start I/O channel, TIO: Test I/O channel, and HIO: Halt I/O channel 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 21 Example Shown as Figure 1.5 (a) and (b) present the difference that are written by the instructions of SIC and SIC/XE, respectively. Figure 1.5 (b) is shorter and more clear than Figure 1.5 (a). 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 22 11

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 23 Hardware Platform 實例探討 Pentium Pro Memory Structure Physical Level 8-bit bytes Half Word 1 byte Full Word 2 consecutive bytes Double Word 4 consecutive bytes (dword) 處理 dword 時,dword address 若能從 4 的倍數開始, 處理速度會更快 Byte addresses word/dword address 是以連續 bytes 中最低的 byte, 亦即位址最小的 byte address 為 word/dword 的 address Programmer View Memory 由數個 Segment 組成一個 Memory address 分成 Segment No. + Offset 每個 Segment 的 Size 可以不同一個 Segment 可以再分成數個 Pages 同一個 Segment 的 Pages 可以不必同時存在於 Memory 中, 只要正在執行指令所屬的 Page 在 Memory 中即可, 其他的 Page 可以暫存於 Disk 中 MMU(Memory Management Unit) 負責將 Segment/offset 的邏輯位址轉換成實際的 Physical address. 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 24 12

Hardware Platform 實例探討 Pentium Pro Registers 8 general-purpose registers, they are EAX, EBX, ECX, EDX, EDI, ESI, EBP, ESP, each of them are 32-bit length In general, EAX, EBX, ECX, and EDX are used to store data. The ESI, EDI, EBP and ESP are used to store address, of course, they can store data. All of EAX, EBX, ECX, EDX can be separated into four of one byte, two of one full word, or one dword All of these general-purpose registers can be used as Base register. They can also be used as Index register, ESP is exception EIP use to store the address of next instruction that will be executed. It has 32- bit length FLAGS includes many various flag bits. Its length is 32 bits too. 6 segment registers, they are CS, DS, SS, ES, FS, GS. All of them are 16-bit length There is a Floating-Point Unit (FPU) for floating-point operations. It has eight 80-bit data register and some registers for control and status. 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 25 Hardware Platform 實例探討 Pentium Pro Data Format 8-, 16-, 32-bits binary integer They can represent as signed or unsigned binary integer They can also use 2 s complement to represent negative number FPU can process the operations of 64-bit length integer Little-endian byte ordering: 整數的儲存必須是低有效位數 (Least Significant part) 存在同一 word 或 dword 最低編號的記憶體位址 Integer 亦可用 BCD(Binary Coded Decimal) 表示, 包括 Unpacked ( 或稱 Zoned) 與 Packed 兩種 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 26 13

Hardware Platform 實例探討 Pentium Pro Floating-point 有下列三種格式表示法 : 格式一單精確度 ; 32bits 格式二雙精確度 ; 64bits 1 7 24 S Exponent Fraction(Significant) 1 10 53 S Exponent Fraction (Significant) 格式三擴增精確度 (Extended);80bits 1 15 64 S Exponent Fraction (Significant) 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 27 Hardware Platform 實例探討 Pentium Pro Character: 8-bit ASCII String: 由 bits, bytes, words, 或 dwords 組成的 code 均視為 string Instruction Format 如下所示 : 每個 field 的長度都不固定, 其中 Opcode 至少為 1 個 byte, 其他 field 可以是 0 個 byte Prefix Opcode Operand Address mode 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 28 14

Hardware Platform 實例探討 Pentium Pro Addressing Mode Immediate mode Register mode EIP relative mode Direct mode TA = (base) + (index) * scale-factor + disp Where scale-factor may be 1, 2, 4, or 8 Disp may be 8-, 16-, or 32-bit binary value 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 29 Chap. 2 Assembler Basic Function of Assembler Machine-Dependent Features of Assembler Machine-Independent Features of Assembler Optional Features of Assembler 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 30 15

Basic Functions This chapter will introduce How to design and Implement an Assembler Assembler 的基本工作配置實際的記憶體位址給每一個指令及 Programmer 所用到的 Symbolic label 將助憶指令 ( 即 Assembly instruction) 轉換成相對的機器語言指令 (Machine Language/Machine Code/Object code) 由於 Assembly language 是 Machine dependent, 因此 Assembler 也是 Machine dependent 的故首先以 SIC 與 SIC/XE 為範本, 了解 Assembler 的設計與製作, 再探討其他 Assembler 應具有的特性 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 31 解讀 SIC Assembly 程式首先以 SIC 的 Assembly 為例, 因為 SIC 只提供 Direct 與 Indexed 兩種定址模式, 因此在 Figure 2.1 的組合語言程式範例中, 指令中包含有, X 的表示使用 Indexed 定址模式, 否則為 Direct 定址模式 Figure 2.1 的程式碼中, 每一指令列由 Line No., Source statement, 及 Comments 組成其中 Source statement 又由下列三部份組成 : [LABEL] [OPCODE] [OPERAND] 其中 [LABEL] 與 [OPERAND] 可以是 null,[opcode] 不為 null 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 32 16

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 33 解讀 SIC Assembly 程式 (Cont.) 此外, 由所引出的指令列為整列的註解 (Comments),Assembler 不需處理另外,START END BYTE WORD RESB RESW 等指令只是用來指示 Assembler 執行一些對應的工作, 並沒有實際的機器指令與之對應故稱為 Assembler directives, 或稱為 Pseudo Instructions, 或稱為 Virtual Instructions Figure 2.1 經 SIC Assembler 處理後, 每個指令與 Symbolic label 的記憶體位址配置及對應的機器碼 (Machine code/object code) 應如 Figure 2.2 所示 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 34 17

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 35 Basic functions of SIC Assembler 1 Convert mnemonic operation codes to their machine language equivalents-e.g., translate STL to 14 (shown as line 10 of Figure 2.2) 2 Convert symbolic operands to their equivalent machine addresses -e.g., translate RETADR to 1033 (shown as line 10 of Figure 2.2) 3 Build the machine instructions in the proper format 4 Convert the data constants specified in the source program into their internal machine representations-e.g., translate EOF to 454F46 (shown as line 80 of Figure 2.2) 5 Write the object program (Obj file) and the assembly listing (LST file) 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 36 18

Basic functions of SIC Assembler (Cont.) 一般而言, 為了處理如 Line No. 10 這種延後方定義位址的 symbol,assembler 的處理方式都會分成 Two Passes (2 回合 ) 的處理 1Pass One: 執行原始程式的 Scan, 並賦予每個指令及 Label definition 的 address 2Pass Two: 執行主要的 Translation 工作 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 37 Basic functions of SIC Assembler (Cont.) Assembler 的 Output Object File (Object Program): 為了說明方便, 以 record 的型式表示與說明 SIC Assembler 所 Output 的 Object file 檔案格式分別由三種 Record type 組成 Header Record:Object file 的第一個 Record, 一個 Object file 僅一個,Record 的組成如下 : Col. 1 H Col. 2-7 Program Name Col. 8-13 Starting address of object program (with Hexadecimal) Col. 14-19 Length of object program in bytes (with Hexadecimal) Text Record: 包含程式 Object codes 的 Record, 一個 Object file 含有一個以上的 Text record,record 的組成如下 : 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 38 19

Basic functions of SIC Assembler (Cont.) Col. 1 T Col. 2-7 Starting address for object codes in this record(with Hexadecimal) Col. 8-9 Length of object codes in this record in bytes (with Hexadecimal) Col. 10-69 Object codes, represented in Hexadecimal (Two column per byte of object code) End Record: 指示 Object program 結束, 一個 Object file 只有一個 End record, Record 的組成如下 : Col. 1 E Col. 2-7 Address of first executable instruction in object program(with Hexadecimal) Example of Object Program corresponding to Figure 2.2 is shown as Figure 2.3 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 39 Object Program (Object File) 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 40 20

Detail Processes of the Two Passes of Assembler Pass One (Define Symbols): Assign addresses to all statements in the program Save the values (addresses) assigned to all labels for use in Pass Two Perform some processing of assembler directives (This includes processing that affects address assignment, such as determining the length of data areas defined by BYTE, RESW, etc.) Pass Two (Assemble instructions and generate object program): Assemble instructions (Translating operation codes and looking up addresses) Generate data values defined by BYTE, WORD, etc. Perform processing of assembler directives not done during Pass One Write the object program and the assembly listing 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 41 Data Structure that Assembler need to Operation Code Table: 簡稱 OPTAB Assembler 用來對照助憶指令轉換成機器指令應至少包含下列四欄位助憶指令對應的機器指令指令之 Format 指令的 Length OPTAB 於 Pass One 之功用, 供查詢 Source program 中的每一指令是否正確 OPTAB 於 Pass Two 的功用, 用以對照每一助憶指令並轉換成對應的機器指令應以 Hash Table 為其設計結構, 並以助憶指令為 Search Key 屬於 Static Table 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 42 21

Data Structure that Assembler need to Symbol Table: 簡稱 SYMTAB Assembler 用來對照程式中的 Symbol 轉換成其值 (Value) 應至少包含下列四欄位 Symbol 的名稱 Symbol 所對應的值或 Address Symbol 之 Type Symbol 的 Length SYMTAB 於 Pass One 之功用, 填入出現在 Source program 中位於 [LABEL] 之 symbol, 及其對應之 LOCCTR 的值或其對應之內部表示值 SYMTAB 於 Pass Two 的功用, 用以對照每一 Symbol 的值或 Address 並填入對應的 Object code 應以 Hash Table 為其設計結構, 並以 Symbol 的名稱為 Search Key Hashing function 可以用整個 Table length 除 Search key 的內碼值 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 43 Data Structure that Assembler need to LOCCTR:data type unsigned integer 用來 count 下一個指令或變數的記憶體位址 Starting address:data type unsigned long 記錄程式被分配的起始位址 Program Length:data type unsigned integer 記錄整個程式的總長度 (byte 數 ) Source file: Intermediate file: 包含 address, error indicator Object file: Assembly listing: 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 44 22

Examples of OPTAB and SYMTAB OPTAB SYMTAB Name Opcode Type Length Name Value Type Length LDA 00 3/4 3/4 BUFFER 1039 R 5 (nibble) ADDF 58 3/4 3/4 ZERO 1030 R 5 (nibble) COMPR A0 2 2 LENGTH 1000 A 6 (nibble) FIX C4 1 1 RDREC 2039 R 6 (nibble) 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 45 Algorithm of SIC Assembler Pass One shown as Fig.2.4 (a) Part one: from read first input line to else initialize LOCCTR to 0 that assign the start address of this program and setup the value of LOCCTR Part two: from while OPCODE <> END do to end {while} that process the location assignment of assembly instructions and symbolic labels, create SYMTAB contents Part three: last two commands create the intermediate file and find the program length Pass Two shown as Fig. 2.4 (b) Part one: from read first input line to write Header record that generate the object program and its first record, Header record Part two: from initialize first Text record to write last Text record to that process the object code and Text records generation based on OPTAB and SYMTAB Part three: last two commands creates the last record, End record, of object program and the assembly listing 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 46 23

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 47 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 48 24

Machine Dependent Assembler Features Extends the functionalities of SIC assembler to SIC/XE How to represent the addressing mode on the assembly programs @: indirect addressing mode #: immediate addressing mode +: extended format (four bytes of this instruction) BASE: a pseudo instruction, inform the Assembler to understand what value of the Base register Example of assembly program running on SIC/XE, Fig. 2.5 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 49 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 50 25

Machine Dependent Assembler Features Compare the two programs shown as Fig.2.1 with Fig. 2.5 Line 150 COMP ZERO COMP A, S (r-r) Line 165 TIX MAXLEN TIXR T (r-r) Line 25 COMP ZERO COMP #0 (immediate) Line 55 LDA THREE LDA #3 (immediate) Line 70~75 LDL RETADR RSUB J @RETADR (indirect) The assembly listing is shown as Fig. 2.6 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 51 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 52 26

What functionality need to be changed and extended from SIC Assembler START 0:it is not really to indicate the beginning address of this program from 0, but means this program is a relocatable Translate r-r instruction:register name need to be transferred to the identified number. In usual, the register name and register number are stored in the SYMTAB Calculate the displacement of general r-m instruction. In usual, they are program-counter relative, a few base relative. That is calculate from TA and content of (PC) or (B) and (X) if it is included Process the immediate, indirect and direct (Format 4) instruction 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 53 What functionality need to be changed and extended from SIC Assembler The rules of displacement calculating First priority is PC-relative When overflow happened, change to Base-relative Some examples: Line 10 0000 FIRST STL RETADR When this instruction being executed, the content of Program Counter (PC) is 0003 According the SYMTAB, the TA of RETADR is 0030 Thus, disp = 0030-0003 = 002D Because it use PC to calculate, p=1 and b=0 The Opcode of STL is 14 and combine bits n and i, thus it is 17 000101 1 1 0 0 1 0 0000 0010 1101 17202D is got. 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 54 27

What functionality need to be changed and extended from SIC Assembler Some examples (Continues): Line 40 0017 J CLOOP When this instruction being executed, the content of Program Counter (PC) is 001A According the SYMTAB, the TA of CLOOP is 0006 Thus, disp = 0006-001A = 014 16 = FEC 16 (2 s complement) 014 16 = 000000010100 2 =111111101100 2 Because it use PC to calculate, p=1 and b=0 The Opcode of J is 3C and combine bits n and i, thus it is 3F 3F2FEC is got. It means that go back offset 001111 1 1 0 0 1 0 1111 1110 1100 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 55 What functionality need to be changed and extended from SIC Assembler Some examples (Continues): Line 160 104E STCH BUFFER, X When this instruction being executed, the content of Program Counter (PC) is 1051 According the SYMTAB, the TA of BUFFER is 0036 Thus, disp = 0036-1051 = 101B 16 < -2048 10 = -0FFD 16 (Range of PC-relative) Thus, change to Base-relative. Due to BASE LENGTH, therefore (B) = 0033 and TA = 0036. So disp = 0036 0033 = 0003 Because it use Base and includes X to calculate, p=0, b=1, x = 1 The Opcode of STCH is54 and combine bits n and i, thus it is 57 57C003 is got. 010101 1 1 1 1 0 0 0000 0000 0011 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 56 28

What functionality need to be changed and extended from SIC Assembler Some examples (Continues): Compare Line 20 000A LDA LENGTH To Line 175 1056 EXIT STX LENGTH According the SYMTAB, both of them the TA of LENGTH is 0033 However, in the Line 20, the (PC) = 000D and the displacement of PCrelative, disp = 0033-000D = 0026, thus the object code of Line 20 is 000000 1 1 0 0 1 0 0000 0010 0101 In the line 175, the (PC) = 1059 and the displacement of PCrelative, disp = 0033-1059 = -1026 16 < -2048 10 (0FFD 16 ). Change to BASE-relative, the displacement, disp = 0033 0033 = 0 Thus the object code of Line 175 is 000100 1 1 0 1 0 0 0000 0000 0000 disp disp = 0033 0033 --1059 1059 = -1026 16 < 16-2048 10 (-0FFD_16 10 16 進位進位 )) -2048(-FFD -2048(-FFD 16 ) 16 ) < disp disp < 2047(7FF 2047(7FF 16 ) 16 ) 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 57 What functionality need to be changed and extended from SIC Assembler Some examples (Continues): Line55 0020 LDA #3 Immediate addressing mode, n=0, i=1, operand = 3, i.e. disp = 003 000000 0 1 0 0 0 0 0000 0000 0011 Line 133 103C +LDT #4096 When this instruction being executed, it is immediate addressing mode and extended format So disp = 4096 n = 0, i = 1, p=0, b=0, e = 1 The Opcode of LDT is 74 and combine bits n and i, thus it is 75 75101000 is got. 使用使用 format format 4 011101 0 1 0 0 0 1 0000 0001 0000 0000 0000 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 58 29

What functionality need to be changed and extended from SIC Assembler Some examples (Continues): Combine immediate + PC-relative addressing mode Line 12 0003 LDB #LENGTH According to the SYMTAB, the TA of LENGTH is 0033 and the (PC) = 0006, So disp = 0033 0006 = 002D. By the way, it indicates immediate addressing mode, therefore, n = 0, i = 1, x=0, p=1, b=0, e = 0 The Opcode of LDB is 68 and combine bits n and i, thus it is 69 69202D is got. 011010 0 1 0 0 1 0 0000 0010 1101 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 59 What functionality need to be changed and extended from SIC Assembler Some examples (Continues): Another example is Combining indirect + PC-relative addressing mode Line 70 002A J @RETADR According to the SYMTAB, the TA of RETADR is 0030 and the (PC) = 002D, So disp = 0030 002D= 0003. By the way, it indicates indirect addressing mode, therefore, n = 1, i = 0, x=0, p=1, b=0, e = 0 The Opcode of J is 3C and combine bits n and i, thus it is 3E 3E2003 is got. 001111 1 0 0 0 1 0 0000 0000 0011 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 60 30

What functionality need to be changed and extended from SIC Assembler Some examples (Continues): Another format examples Line 150 1049 COMPR A, S It is a instruction followed FORMAT 2 The Opcode of COMPR is A0, the id no. of A is 0, of S is 4 1010 0000 0000 0400 Line165 1051 TIXR T It is a instruction followed FORMAT 2 The Opcode of TIXR is B8, the id no. of T is 5, only one register 1011 1000 0101 0000 S 的編號是的編號是 4 4 0100 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 61 Program Relocation Absolute Program (Absolute Assembly) 之缺點位置固定無法共用 Resource ( 如 Memory) 調整位置時 (Change Starting Address), 需全部重新組譯 (Re-Assembling) 改進之道 Relocated Program Assembler 不能直接 assign memory address Assembler 仍可以算出相對位址並留下 Information 通知 Loader 哪一部份需要修改此 Information 留在 Assembler 所 Output 的 Object program 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 62 31

Program Relocation Fig. 2.7 則指出 Fig. 2.5 的 Object codes 被 relocate 在不同 memory address 時,object codes 的變化範例其中如 +JSUB RDREC 的指令, 其對應的 object code 一直隨著 RDREC 所配置的記憶體位址而改變 Assembler 對 REREC 的位址是依據 starting address 為 0 時所計算出來的相對位址, 而 +JSUB RDREC 則是使用直接定址法 (Direct Addressing mode) 指定 RDREC 的位址因此, 當程式碼被安排在 starting address 非為 0 時,+JSUB RDREC 所對應的 object code 就會指到不正確的位址!! 因此,Assembler 必須告訴 Loader, 當它在 loading time 時負責載入 Object code 到 memory 時, 要更改哪些記憶體位址的內容, 將其加上真正的 starting address 以調整為正確的位址反之, 非 direct addressing mode 的指令, 其 object code 完全不需隨著 starting address 的不同而有所改變, 這就是相對定址法的優點 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 63 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 64 32

Program Relocation Assembler 如何通知 Loader 所需要的 information Answer: 在 Object program 中留下 Modification record Modification record 的格式如下 Col. 1 M Col. 2~7 Starting location of the address field to be modified, relative to the beginning of the program (hexadecimal) Col. 8~9 Length of the address field to be modified, in halfbytes (hexadecimal) Why half-bytes? 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 65 Program Relocation Object program included modification records shown as Fig. 2.8 for source program Fig. 2.5 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 66 33

Machine Independent Assembler Features 本節將討論一些與 machine 結構無關, 但是在大部分 Assembler 會共通的特性 Literals Symbol Defining statement Expression Program Blocks Control Sections & Program Linking 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 67 Literals Literals 是 Assembler 提供 programmer 以 constant operand 的 value 作為指令的一部份, 省去為這些 constant 定義 label, 這樣的 operand 稱為 literal Programmer 在 assembly 程式中, 必須在 operand 之前加上 = 的符號指明是 literal, 如 : 45 ENDFIL LDA =C EOF 215 WLOOP TD =X 05 其中 C 表示 character,x 表十六進位值 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 68 34

Literals Literal 與 immediate operand 是不同的 : Immediate operand 的 operand 在 assembled 之後會變成機器指令的一部份, 而 literal operand 則是由 assembler 自動配予一個 address 存放這個 constant, 並將這個 constant 的 memory address 作為指令的 target address 比較 Fig 2.10 的 45 001A ENDFIL LDA =C EOF 032010 及 55 0020 LDA #3 010003 詳細請先參考 Fig 2.9 及 Fig 2.10 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 69 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 70 35

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 71 Literals 通常在程式中所用到的 literals 會被集中形成一或多個 literal pools, 而 literal pools 則置於程式最後面, 但如果程式中有宣告 LTORG 者, 則 LTORG 之前用到的 literals 則先集中於 LTORG 之後, 如 Fig 2.9,2.10 LTORG 的用意是在預防萬一程式太大, 前面使用的 literals 在程式最後分配到的 address, 會變成 large format, 因此,LTORG 可使 literals 比較接近用到它的指令. 如何辨別 duplicate literals: 比較 string of literal, 例如 C EOF ;X 05 比較產生的值, 如 C EOF 及 X 454F46 其實是相同的, 可以只存一個另外, 這種辨別 duplicate literals 會產生一種問題為 : 假設我們允許 literal 使用 current value of location counter( 記為 * ),LDB =*, 表示要將目前 location counter 的值存到 Base register. 但是若 line 13 用到 LDB =* 及 line 55 用到的 LDA =*, 這時 * 所代表的 location counter 的 value 是不同的, 分別為 0003 及 0020, 但同樣是 literal * 所表示, 這樣情況也必須要在 literal pool 表示出來. 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 72 36

Literals 最後, 討論 assembler 如何 handle literals 首先,assembler 必須 create 一個 literal table (LITTAB) LITTAB 的結構為 : literal name operand valve length Address LITTAB 以 hash table 的方式組成, 以 literal name 為 key 或以 value 為 key LITTAB 在 Pass1 時產生,Pass1 紀錄,scan 到的 literal name 及對應的 value 及 length, 如果 LITTAB 內沒有則 add 進去當 Pass1 scan 到 LTORG 或程式最後時, 則要產生 literal pool, 並將 address 分配給 LITTAB 中的 literal, 此時 location counter 必須跟隨著 literal 的 length 改變, 以維持 address 的正確性 Pass2 則是根據 LITTAB 中 literal name 對應的 address 產生適當的機器指令 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 73 Symbol Defining Statement 允許 Programmer 自行定義自己的 Symbol User-defined symbols 除了用在 label 或 data area 外, 大多的 Assembler 均會提供 programmer 自己定義 Symbol 及指定其 value 的功能一般的格式如下 : Symbol EQU value EQU 常用的情形為 : A. 提高程式的可讀性 (readability) +LDA #4096 改成 +LDA #MAXLEN MAXLEN EQU 4096 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 74 37

Symbol Defining Statement EQU 常用的情形為 : B. 用來以 number 代替 register 的助憶名稱 A EQU 0 X EQU 1 L EQU 2 以便讓如 RMO 這類的指令, 需要以 reg.number 作 operand 的指令可以用 RMO A,X 代替 RMO 0,1 再由 assembler 從 SYMTAB 中找到 A,X 的 Value 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 75 Symbol Defining Statement 另一種 assembler directive 是用來 reset LOCCTR, 格式如下 : ORG value ORG 是 origin 的意思, 所以, 以下的 location 改由指定的 value 開始 count ORG 另一個應用則是用在 Table define, 如下例 : 假設 programmer 要定義一個 symbol table 的 structure 如下 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 76 38

Symbol Defining Statement STAB (100entries) symbol valve flags 6 個 bytes 1 word 2 byte programmer 可能會用這種方式來描述 STAB RESB 1100 SYMBOL EQU STAB VALUE EQU STAB+6 FLAGS EQU STAB+9 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 77 Symbol Defining Statement 之後程式中只要用 LDA VALUE, X 即可透過 register X 的 content indicate table entry 而取得 VALUE field 上述的例子亦可用 ORG 完成, 方式如下 : STAB RESB 1100 ORG STAB SYMBOL RESB 6 VALUE RESW 1 FLAGS RESB 2 ORG STAB+1100 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 78 39

Symbol Defining Statement 有些 assembler 允許用 ORG 代替 ORG STAB+1000, 這是 assembler 自動記憶先前的 LOCCTR 的值另外, EQU right-hand side 的 Symbol 必須是一個已定義的 Symbol, 例如 : ALPHA RESW 1 BETA EQU ALPHA 若寫成 BETA EQU ALPHA ALPHA EQU 1 則不允許因為依照 Assembler 的處理,Pass1 在 Scan BETA 時, 就必須記住其 address, 但這種情形,BETA 值無法得知 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 79 Symbol Defining Statement 同樣地,ORG 亦不允許這種情形, 例如 : BYTE1 RESB 1 BYTE2 RESB 1 BYTE3 RESB 1 ORG ALPHA RESW 1 亦是不允許的更一般性的問題如 : ALPHA EQU BETA BETA EQU DELTA DELTA EQU 1 稱為 forward-definition problem 或稱 forward-reference problem, 是 2-pass assembler 所無法容易解決的, 因此一般的 assembler 會加以限制 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 80 40

Expression Expression 的用法是允許 operand 的表示不只是 Symbol 或 literal, 而是由多個 symbol 或 literal 與 +, _, *, / 等組合而成的, 例 : MAXLEN EQU BUFEND-BUFFER 其中 BUFEND-BUFFER, 就是一個 expression 由於一般的 operand 有 absolute 與 relative 之分, 因此, expression 因其結果也可分成 absolute 與 relative 兩種 expression, 上例即為一個 absolute expression, 而 BUFEND+BUFFER 100-BUFFER 3*BUFFER 則為 relative expression 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 81 Expression 為了能夠告知 loader 哪些 Symbol 是 relative, 哪些是 absolute, 必須在 SYMTAB 中註明以 Fig2.10 的 SYMTBL 如下 Symbol Type Value RETADR BUFFER BUFFEND MAXLEN R R R A 0030 0036 1036 1000 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 82 41

Program Block 前述的 Assembler 所處理的 program 包含 subroutines data area 等, 均屬於同一的 entity, 亦即 Assembler 產生的 object program 的順序與 source program 的順序是一樣的為了使 Source & object program 的處理更有彈性, assembler 必須在提供某些 features, 如 : Some features for 允許產生的 machine instruction 及 data 與 source program 中的順序是不同的 ( 本書稱為 Program block) Some features for 讓 object program 產生的是一些相互獨立的部分, 這些 parts 再由 loader 分開 handle 及 maintain ( 本書稱為 Control Section) 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 83 Program blocks Program Block and Control Section Assembler 可以提供某些 features 給 Programmer 允許實際上產生的 object program(object file) 之機器碼可以分成數個 Code Segment, 且 Code Segment 的順序與 source program 之原始指令的順序不同 Program Blocks 表示 Object program 內的 Object codes 會被重新安排在單一 object program unit 的不同 code Segment Control section 則是表示 Object program 內的 Object codes 會被轉換互相獨立之 object program units 的 Code Segment Control Section 於下一節介紹 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 84 42

Program blocks Fig2.11 即為一個以 Program block 寫成的例子本程式共有 3 個 Program block, 第一個 block 為 unnamed block 包含可執行指令第二個 block 為 CDATA block 包含全部的 DATA area 第三個 block 為 CBLKS block 包含大的記憶體區塊 Programmer 在編撰本程式時被允許交錯安排各個 Block, 以求可讀性的便利, 讓屬於 main routine 的 data 與 buffer 出現在 main routine;rdrec routine 所用到的 data 出現在 RDREC routine;wrrec routine 亦同但是 Assembler 則需在產生 Object file 時, 將 Object code 重新安排, 以便讓程式指令的集中在一起變數資料的集中在一起暫存區在另外一區類似 Intel 80X 系列的 code segment data segment stack segment 與 extra segment 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 85 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 86 43

Program blocks How to do Assembler 應提供一個 Assembler directive 供 programmer 指明 block 名稱及程式中的歸類本書的範例是使用 USE 這個 Assembler 指令 USE 指令可以用來指明與前一個相同名稱的 block 之連續性由此可知一個 program block 在一個程式中可能被分成數不同的 Code segment(program Block) Assembler 必須將這些 Code segment 重新安排這些重新安排的工作在 Pass1 完成 logical 的部分 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 87 Program blocks How to do ( 續 ) 每一個 Program block 給予一個 location counter(locctr i ) 起始值均 set 為 0, 處理不同 block 時就用各自的 counter 累計,Block 的編號也隨之紀錄到 SYMTAB 的 value 中在 Pass1 最後, 各個 location counter 的值即為各 block 之 length, 根據這些資料 Pass1 可以產生一個 Working table 如下 : Block Name No. Start Address Length (unnamed) 0 0000 0066 CDATA 1 0066 000B CBLKS 2 0071 1000 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 88 44

Program blocks How to do ( 續 ) 這個 Table 再供 Pass2 用來產生 Object Code 對一個 Symbol,Pass2 只需從 SYMTAB 找到它相對於自己的 block 的位址再加上 working table 中該 block 的起始位址即為此 symbol 的 TA 再由此 TA 來計算 operand 的 disp 值例如 line 20 的 displacement 係由 LENGTH 在 SYMTAB 中所找到值 0003, 1, 再由 LENGTH 的 block(no.1) 知道 block 的 start address 為 0066, 故 TA 為 0069 (0003 + 0066) 又本指令為 pc-relative, 而 (PC)=0009, 故得 disp = 0069-0009, 故 disp= 0060, 由此產生 object code 為 032060 Fig 2.12 即為 fig 2.11 的 assembly-listing file 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 89 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 90 45

Program blocks Program block 的優點 : Reduces our addressing problems, because large buffer area is moved to the end of the object program Base register is no longer necessary (no more Base-relative) The problem of placement of literals in the program is easily solved 實際上 Assembler 在產生 Object File 時, 並不需要重新安排整個 object code 的順序為各個 code segment (Program Block) 的順序只需逢不同 block 時,write 不同 text record 即可, 如 fig 2.13 前兩個 text records 為 line 5 to line 70 的 object codes 當新的 use 指令出現後, 就準備一個新的 text record 來存對應的起始位址與 object code 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 91 Object Program for Program Block 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 92 46

Program blocks Fig 2.14 則是說明 source program,object program, and memory 配置的 block 順序其中 CDATA(1) 與 CBLKS(1) 因為沒有 object code, 所以在 object program 中並不存在但是 CDATA(1) 與 CBLKS(1) 在 memory 中仍保有記憶體區塊因為它們的原始指令是要求 Reserve 記憶體空間 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 93 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 94 47

Control Section 讓 Assembler 產生的 object program 是一些相互獨立的部分 (parts 或 code segments), 這些 code segments 再由 loader 分開 handle 及 maintain 本書將這種 code segments 稱為 control sections 將 programs 分成多個 control section 可以分別地 load 及 relocate, 這樣的好處使得 programming 更有彈性既然不同的 control system 有各自的 loading 及 relocating 時間, 但這些不同的 sections 又在一個 program 中形成 logical 上相關, 這表示實際上需要將它們 linking 在一起 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 95 Control Section 可是, 每個 Section 有自己的 loading & relocating time, 表示每個 section 在執行時的 location 無法得知那表示 Assembler 對一個 section 中有 reference 到別的 section 的 symbol 就無法取得其 value 了, 這種 reference 稱為 external reference ( 外部參用 ) 因此,Assembler 必需對每個 external reference 產生一些 information 以便 loader 執行必要的 linking 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 96 48

Control Section Fig 2.15 有三個 control sections, 主程式及每個 subroutine 各為一個 section 這三個 section 可以分別組譯與載入這表示 main program 被組譯時,line 15 及 line 35 的 RDREC & WEREC 均是未知對於未在該程式碼中定義卻要直接使用的變數 ( 或 Symbol), 稱為 External Reference( 外部參用 ) 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 97 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 98 49

Control Section 為了指明那些是 external reference 以便 loader 處理,SIC/XE 的 Assembler 增加了兩個 assembler directives 分別為 EXTDEF & EXTREF EXTDEF (External Definition) 用來指明哪些 symbols 在本 section (Control Section) 中被 definition, 可供其他 section 使用 (reference) 的 EXTREF (External Reference) 用來指明那些 symbols 在本 section 會 reference, 但是其他 section 中 definition Fig 2.16 就是 fig 2.15 的 Assembly-listing file 其中 line 15, line 160, line 190 均因 symbol 未知, 故 assembler 暫以 0 代入 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 99 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 100 50

Control Section Assembler 為了提供 Control Section 這種 feature, SIC/XE 的 Assembler 要新增的工作如下 Remember 那個 Symbol 是由那一個 control section 所 define 一個 control section 若沒有宣告 EXTREF 就欲 refer to another control section 的 SYMBOL, 則必須 Set error flag 若經 EXTREF 宣告, 則 Assembler 必須允許相同的 Symbol 用在不同的 Control sections 例如 MAXLEN 的定義, 在 fig 2.15 的 line 107 及 190 不會造成問題 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 101 Control Section 為了保留 object code 的空間給 external reference, 也必須在 object program 中包含 information 以便 loader 再為 external reference 填入適當值 SIC/XE 需要增加 2 種 record type 如下 : Define record: Col. 1 D Col. 2-7 Name of external symbol defined in this control section Col. 8-13 Relative address of symbol within this control section(hexadecimal) Col. 14-73 Repeat information in Col. 2-13 for other external symbols Refer record: Col. 1 R Col. 2-7 Name of external symbol referred to in this control section Col. 8-73 Names of others external reference symbols 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 102 51

Control Section 並且修改 Modification record 為 Modification record (revised): Col. 1 M Col. 2-7 Starting address of the field to be modified, relative to the beginning of the control section (hexadecimal) Col. 8-9 Length of the field to be modified, in half-bytes(hexadecimal) Col. 10 Modification flag (+ or -) Col. 11-16 External symbol whose value is to be added to or subtracted from the indicated field 而 fig2.15 因為分成 3 個 control sections, 因此 object Files 也分成三個, 如 fig2.17 所示 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 103 Object Program for Control Section 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 104 52

Control Section 其中 main program section 的部分, 如 line15 +JSUB RDREC 該指令本身相對於 begin address 為 0004, 但 operand REREC 的 address 先暫設為 0 並在 COPY 這個 Control section 設定 Modification record M00000405+RDREC 另外, 像 line 190 的 BUFFEND-BUFFER 在 Assembler 的組譯時間已無法計算, 故須留在 Loader 時才計算, 故設定 Modification records 二筆 M00002806+BUFFEND M00002806-BUFFER 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 105 Control Section 對於 relocation 需要配合修改的部分至要留在下一章再討論另外, 對於 expression 的處理, 為了 relocating, 必須限制 expression 中所用的 symbol 必須在同一 section 內如 BUFFEND-BUFFER 但 RDREC-COPY 則屬不同 section, 因為分屬不同 section, 則其結果是無法預測的, 因為 locating 的地方每次可能都不同 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 106 53

Assembler Design Options Two Passes Assembler with Overlay Structure One Pass Assembler Multi-passes Assembler 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 107 Two Passes Assembler with Overlay Structure 為何要 Overlay Structure Internal subroutines & Tables of Pass1 are no longer needed after the pass 1 is completed Routines & tables of pass 1 & pass 2 are never required at same time With overlay structure can reduce memory requirement Overlay Structure 整個 Two-Pass Assembler structure 有 Three segments, 以 Tree structure 表示其中 root segment 含有一 simple driver 以便 call 另外兩個 segment, 並包含了共用的 tables 及 routines, 如 SYMTAB 及 searching/inserting SYMTAB routines 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 108 54

Overlay Structure of Two Passes Assembler Dispatcher/Driver Common Tables & Routines Root Segment Pass One Routines & Tables Pass one segment Pass Two Routines & Tables Pass two segment 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 109 Overlay Structure of Two Passes Assembler Main() Main() Main() Pass1 Pass1 Pass2 Pass2 Unused Source Reserved Memory Area 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 110 55

One-pass assembler Two-Passes Assembler 中用了一個 pass 來處理 symbol definition after symbol using 如果規定,symbol definition 必須在 symbol 被 use 之前, 則可以去掉一個 Pass 的工作 ( 如 fig. 2-18 的 Line 1-6) 但, 這畢竟不是 friendly design, 例如 jump 的方向總不能只能往回跳, 副程式一定要先寫 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 111 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 112 56

One-pass assembler 以下將介紹兩種 One-Pass assembler types, 並保有 Twopasses assembler 的提供之 functions 這兩種 One-Pass assembler 的一項共同方法是改變 SYMTAB 的結構, 允許 symbol 可以在未 definition 前 ( 卻先要 use 時 ) 就先紀錄到 SYMTAB, 方法如圖例所示第一種 :Load-and-go assembler: 直接將 object code 產生並置於 memory 中, 並隨即執行優 : 簡單缺 : 限於 absolute loader, 每次執行均需 assemble 適用環境 : 教學練習,absolute addressing 如 fig 2-19a-b 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 113 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 114 57

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 115 One-pass assembler 第二種 : 會產生一個 object file, 以便稍後執行 object file 較 two-passes assembler 所產生的大, 其他功效與 Two-pass assembler 相同方式與第一種類似,SYMTAB 的結構也相同但將產生的 object code 寫到 Text record 但因為是寫到 file 去, 所以不能像第一種方法一樣, 隨時回頭去改記憶體內容因此, 遇到 forward defined Symbol 時,operand 的部分先以 0000 代入, 並記錄此位置及 Symbol name 當 Symbol 被 defined 之後, 就 Symbol 被 use 的位置, 長度及 Symbol 的值來產生新的 Text record, 因此 Text record 數會變多因此, Fig2.18 以第二種方法產生的之 object file 如下 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 116 58

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 117 Multi-Passes Assembler 使用 Multi-Passes Assembler 可以解決 forwardreference problem ( 如圖 2-21a) 但是隨著 forward 的級數就需要相對的 Passes 數, 很難給于一個定額的 passes 個數所以在此介紹一種用 Two-pass assembler 處理 forward-reference problems 的設計方法是對 SYMTAB 的結構加以設計 ( 如圖 2-21b), 在 Two Passes Assembler 的 Pass One 允許 Used Symbol without Definition 可以先存到 SYMTAB 中, 並紀錄對應的 Reference 的位置 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 118 59

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 119 Multi-Passes Assembler 如圖 2.21b-f 的 Symbol table structure 其中,&? 是表示 define 此 Symbol 中的 Expression 裡, 尚有幾個 Symbol 仍是 undefined Value 欄位則先填入已知的 Expression Link 則是連結到受此 Symbol name 影響而 undefined 的 Symbol, 以便未來此 Symbol 被 define 以後, 可以沿著此 Link 去修訂一連串未被 defined 的 symbol 過程如圖 2.21b 到 2.21f 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 120 60

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 121 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 122 61

Chap. 3 Loader & Linker Basic Loader Functions Machine-Dependent Loader Features Machine-Independent Loader Features Loader Design Options 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 123 Loader & Linker 本章介紹重點是 3 個 Processes Loading Relocation Linking Loader : 基本上是執行 Loading function 但大多數的 Loader 包含有 Relocation 及 Linking 的 functions Linker : 單純執行 linking 的工作, 此時的 Loader 則執行 Loading & relocation Loader 最基本的功能 : Loading 一個 Object Program 到 memory, 並開始執行該程式 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 124 62

Loader & Linker 本章介紹的 Loader & Linker 主要有下列幾種 Absolute loader: only with Loading function Relocating loader: with Loading & Relocation function Linking loader: with Loading, Relation, and Linking Linkage editor: it is a Linker, only has Linking function Dynamic linking loader: it is a Linking Loader that run the loading, relation, and linking functions in execution time of loaded program Basic Functions of Loader Bringing an object program into memory Starting its execution 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 125 Design an absolute loader Absolute loader 可以用 one pass 完成所有功能請先參閱 Fig. 3-1a 與 Fig. 3-1b Figure3.1(b) 是表示 Figure3.1(a) 的 Object program 放到 memory 的結果其中 xxx, 屬於 Reserved Area,Object Program 未提供 Object code, 故 loader 不改變原 memory 的內容 Figure3.2 則是一個 Absolute Loader 的 Algorithm 其中 SIC 假設 Object file 中每個十六進位的 Digit ( 理論上只有 4 個 Bits) 都是一個 Character 來呈現而實際上在 Object file 的一對 Character( 佔 2 bytes), 放到 memory 時要轉成一個 Byte 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 126 63

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 127 Algorithm of Absolute Loader 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 128 64

Design an absolute loader 因此,loader 必須要注意轉換工作 (Algorithm 的 if object code is in character form ) 更一般的做法是 Assembler 的 output 就以 binary 表示但, 這種做法也須注意另一件事 ;Object file 中的 byte 是否和某些 device 的 control code 相同, 若是, 可能會在 file 的 r/w 時, 造成系統其他行為, 而 object file 本身卻不完整 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 129 A Simple Bootstrap Loader 一般電腦上有一支更簡單, 具特定用途的 absolute Loader 稱為 Bootstrap Loader Bootstrap Loader 是一部 Computer 起始執行的第一個 program 其的工作負責 load O.S. 到 memory & run 或 load 某一特定程式, 當 computer 是一特定用途之電腦 Fig3.3 是 SIC/XE Bootstrap Loader 之 Source Code 其中 Bootstrap 自己在 address 0 開始而 operating system 自 80 位址開始,O.S. 的 object file 則是從 device F1 read in 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 130 65

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 131 Machine Dependent Loader Features Absolute loader 的缺點在 object file 放到記憶體之前,programmer 必須指定好起始位址 Absolute program 難以有效地使用 subroutine libraries 本 section 則探討一個 more complex loader 的 design & implementation, 此 loader provides for program relocation and linking 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 132 66

Relocation Relocating loader/relative loader Loader 允許 program relocation 者, 稱之兩種方法來完成 program relocation 均需憑藉 Assembler 在 output object file 時留下必要資訊的幫助 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 133 Relocation 利用 Modification record 在 modification record 中每一個值在 relocation 時,Load 均須依據真正的起始位址改變其實際值, 如 Figure3.4 之 program 及 Figure3.5 之 object file 但是, 若是 program 是一個 SIC program 或用了許多 direct addressing mode 時, 那 modification record 將會相當多, 這時, 必須用第二種方法解決利用 Modification Bits 每個 Text record 最多可容納 10 個 word, 每個 word 用一個 relocation bit 來標明是否要調整 ( relocation ) 因此, 每個 record 加上 3 個 nibble ( half-byte ) 來指示下列 word 中, 哪些要 relocation 如 Figure3.6 是一個 standard SIC program, 若要提供 relocation function 則 assembler output 必須如 Figure3.7 所示,loader 才能完成 relocating function 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 134 67

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 135 利用 Modification Record 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 136 68

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 137 利用 Modification Bits 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 138 69

Program Linking Programmer 自然地將相關的 control sections 合併在一個 Source Program 但就 loader 觀點而言, 只要知道 control sections 要被 linked, relocated 及 loaded 而不會 ( 也不需要 ) 知道那些 control section 在同一時間內要被組合在一起以 Figure3.8 的 3 個 control sections 為例 3 個 control section 功能相似指令不同每個 section 各擁有一個 list 及同性質的 REF1~REF3,REF4~REF8 在此要強調的是 relocation 及 linking 處理的關係 Figure3.8 之 object program 如 Figure3.9 所示 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 139 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 140 70

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 141 Object Programs of Fig. 3.8 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 142 71

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 143 Program Linking Figure3.10(a) 則表示 Figure3.9 的 object program 被放置到 memory location 4000 的地方以及 REF1~REF8 相關的 contents 被計算出來後的結果 Figure3.10(b) 則是說明 PROGA 中 REF4 被 relocation 及 link 的執行過程 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 144 72

Relocation and Link of Fig 3.9 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 145 Memory Map of Fig 3.9 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 146 73

Tables & Logic for Linking Loader Linking loader 分成 2 個 Passes: Pass1 : Assigns address to all external symbol Pass2 : Performs the actual loading, relocation and linking 主要的 Data Structure 有 : ESTAB : External Symbol TABle 包含 : Symbol name Address in its control section Control section defined the symbol 可以使用 Hash 方法組織此 table PROGADDR : 紀錄 program load address CSADDR : 紀錄目前處理之 control section 所 assign 的起始位址 CSLTH : 紀錄目前處理之 control section 的長度 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 147 Tables & Logic for Linking Loader Linking loader 的演算法如下 : Pass1 的工作 : Allocate Memory 建立 ESTAB Allocate 每個 control section 在 memory 的起始位址如 Fig 3.11(a) Pass2 的工作 : 依 ESTAB 及 object file 內容將 object code 放到 memory 的適合位置如 Fig 3.11(b) Pass1 所 concern 的是 Header 及 Define Record 並且把 control section name 也建入 ESTAB 內, 並存入相對應之起始位址 Pass2 所 concern 的是 Text record 及 Modification record 是實際執行 object file 的 loading,relocation 及 linking 的工作 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 148 74

2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 149 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 150 75

Tables & Logic for Linking Loader 有許多 Loader 會再由 ESTAB 衍生出一個 Load Map 專門記錄每個 Control section 的起始位址及每個 Control section 中 define 的 External Definition symbol 之位址如下表, 即為 Fig3.9 及 3.10 的 Load Map 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 151 Tables & Logic for Linking Loader 若要再提高此演算法效能可以將 object file 中 External Reference symbol 改用 Reference number 來代替如此一來, 在 loading 一個 control section 時相同的 symbol 就可以在 ESTAB 上避免 multiple search 如 Fig3.8 的 object file 即可改用 reference number 改成 Fig. 3.12 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 152 76

External Reference Number for Fig. 3.8 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 153 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 154 77

Machine-Independent Loader Features Automatic Library Search 配合 Linking Loader 的鏈結功能, 如果 Programmer 在程式中用到 System Library 所提供的函式與變數原始程式不必宣告 System Library 所定義的 Symbols 此時,Loader 雖然無法自原程式找到這些 Symbols 的定義與位址, 但是尚不會立即判定有 Undefined Symbol 而是開啟 System Library, 搜尋尚未被定義的 Symbols, 並 Assign 屬於 System Library 所指定的 Symbols 與對應的值只有在原程式與 System Library 都找不到 Symbol Definition 時, 才判定 Undefinied symbol 的 Error 通常 Loader 搜尋 External Symbol 的定義時是優先搜尋原程式各 Control Sections, 找不到才搜尋 System Library 這樣的搜尋順序才能允許 Programmer definition function override System library 的定義 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 155 Machine-Independent Loader Features Loader Options 本功能允許 Loader 再執行載入程式時, 接受使用者的要求, 經由參數指定載入的內容與變化範例如下 : INCLUDE READ(UTLIB) INCLUDE WRITE(UTLIB) DELETE RDREC, WRREC CHANGE RDREC, READ CHANGE WRREC, WRITE LIBRARY MYLIB NOCALL STDDEV, PLOT, CORREL 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 156 78

Loader Design Options Linkage Editor It is a Linker It only has linking function The output of Linkage Editor is a Linked Program, often called load module or executable image 與 Linking Loader 的比較 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 157 Loader Design Options 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 158 79

Loader Design Options Dynamic Linking 又稱為 Dynamic loading Load on call 提供 Control Section ( 或稱為 Program Module) 在被呼叫時, 才執行 Linking Relocation and Loading 工作優點是需要時才被載入, 不佔記憶體空間缺點是執行效率慢執行方式如圖 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 159 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 160 80

Loader Design Options Dynamic Linking 比較幾種 Loader 的 Relocation Linking 的時間點 Absolute Loader 無須 Relocate 與 Link, 在 Assemble Time 已決定一切 Relocating Loader 無須 Link, 在 Loading Time 決定 Relocation Linking Loader 在 Loading Time 決定 Relocation 與 Linking Linkage Editor 在 Assemble Time 之後,Loading Time 之前決定 Linking 與部分的 Relocation Dynamic Linking 在 Execution Time 才決定 Relocation Linking 以及 Loading 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 161 Macro Processors 2010/2/23 Ying-Hong Wang; http://inhon.tkse.tku.edu.tw 162 81

Microsoft PowerPoint - 系統程式2010