---
title: System programming 2
---
# System Programming
NTNU 系統程式
##### [Back to Note Overview](https://reurl.cc/XXeYaE)
##### [Back to System Programming](https://hackmd.io/@NTNUCSIE112/SP110-1)
{%hackmd @sophie8909/pink_theme %}
###### tags: `SystemProgramming` `110-1` `CSIE` `選修` `NTNU`
<!-- tag順序 [學校] [系 必選] or [學程 學程名(不含學程的 e.g. 大師創業)] [課程] [開課學期]-->
<!-- 網址名稱 SP110-1_[] -->
## Ch.02 Assemblers
### Introduction to Assemblers
- translator
- compiler
- assembler
- Fundamental functions
- Mechine dependency
### 2.1 Basic Assembler Functions
- 功能
- 將助記符操作碼轉換為與其機器語言等價的東西
- 將符號運算元轉換為等價於機器位置的東西
- 以正確的格式建構機器指令
- 將數據常數轉換為內部機器表示
- 編寫目標程式及彙編清單
#### 困難點:Forward reference(p.48)
使用在後面才宣告的 Label 時要怎麼計算位置
Label 分成 variable 跟 instruction
- Variable 可以往上移
- Instruction 不可能都往上移
> 一個程序中的 instruction 包含了 forward reference,也就是說我們無法逐行翻譯它,因為我們不知道它所代表的值是什麼。
因此大多數的組譯器會執行兩次,第一次主要是掃過整個程式,去定義 Label 的值和對應的位址,接著才是真的翻譯他。
#### Example program(Fig 2.1)
:::spoiler 點我打開 Figure 2.1
![](https://i.imgur.com/kSejIFZ.png)
:::
- 目的
- 從輸入裝置讀取紀錄(code F1)
- 將它們複製到輸出裝置(code 05)
- 在文件末端時在輸出裝置 EOF,之後 `RSUB` 回到作業系統
- Data transfer(`RD`, `WD`)
- a buffer is used to store record
- buffering is necessary for different I/O rates
- the end of each record is marked with a null character ( $00_{16}$ )
- the end of the rule is indicated by a zero-length record
- Subroutines(`JSUB`, `RSUB`)
- 巢狀跳轉前先保存連結暫存器
- `JSUB` 跳到對應的副程式
- `RSUB` 回到 `JSUB` 的下一行
<!-- p.47 -->
#### Assembler Directives(組譯器指引)
- Pseudo-Instructions
- 不會轉成機器碼
- 提供資訊給組譯器
- Basic assembler directives
- `START`, `END`, `BYTE`, `WORD`, `RESB`, `RESW`
#### Two Pass Assembler
- Pass 1
- **為程式中的所有 statement 分配位置**
- 保存分配給所有 label 的標籤以用於 Pass 2
- 對彙編指令(assembler directives)做一些處理
- Pass 2
- **Assemble instructions 組裝指令**
- Generate data values defined by `BYTE`, `WORD`
- Perform processing of assembler directives not done in Pass 1
- Write the object program and the assembly listing
:::warning
In pass 2, assembler generates **Object codes**.
:::
- Read from input line
- `LABLE`, `OPCODE`, `OPERAND`
-
#### Object Program
- **Header**
| Column | Content |
| ------ | --------------------------------------- |
| 1 | H |
| 2~7 | Program name |
| 8~13 | Starting address (hex) |
| 14~19 | Length of object program in bytes (hex) <br>(最後一個指令的 PC)-(第一個指令的 loc)|
- **Text**
| Column | Content |
| ------ | --------------------------------------------------- |
| 1 | T |
| 2~7 | Starting address in this record (hex) |
| 8~9 | Length of object code in this record in bytes (hex) |
| 10~69 | Object code (69-10+1)/6=10 instructions |
- End
| Column | Content |
| ------ | ---------------------------------------------------------------- |
| 1 | E |
| 2~7 | Address of first executable instruction (hex) (END program_name) |
- Fig. 2.3
```object=
H COPY 001000 00107A
T 001000 1E 141033 482039 001036 281030 301015 482061 ...
T 00101E 15 0C1036 482061 081044 4C0000 454F46 000003 000000 T 002039 1E 041030 001030 E0205D 30203F D8205D 281030 ...
T 002057 1C 101036 4C0000 F1 001000 041030 E02079 302064 ...
T 002073 07 382064 4C0000 05
E 001000
```
#### Data Structures
- Operation Code Table (OPTAB)
- 內容:助記符、機器碼(指令格式、長度)等...
- 特徵:靜態表格
- 實作:陣列或是雜湊表,方便尋找
- Symbol Table (SYMTAB)
- 內容:label 的名字、值、flag、
- 特徵:動態表格(insert, delete)
- 實作:雜湊表、
- Location Counter(LOCCTR)
- 內容:
- 特徵:
- 實作:
<!-- 教授的ppt被遮住嘞 我不知道怎麼辦QQ -->
### 2.2 Machine-Dependent Assembler Features
#### 2.2.1 Instruction Format and Addressing Modes
<!-- slide -->
- SIC/XE
- `op m`:PC 相對或是 Base 相對定址
- 如果沒有宣告 base,就會優先使用 pc 相對
如果 pc 相對無法使用才會用 base 相對
- `op @m`:間接定址
- `op #m`:立即數定址
- `+op m`:擴充格式(format 4)
- `op m, x`:索引定址
-
<!-- 待補 -->
<!-- p.57 第三段 -->
- 大多數的 register-to-memory instructions 由 PC-relative 和 base relative addressing 組成
##### 翻譯
+ 暫存器翻譯
+ 暫存器的名字(A, X, L, B, S, T, F, PC, SW)
跟他們的值(0,1, 2, 3, 4, 5, 6, 8, 9)
預裝在 SYMTAB 中
+ 地址轉換
+ 大多的指令使用 pc/base 相關定址法
+ format 3:12bits 定址區域
+ base relative:0~4095
+ pc relative:-2048~2047
+ format 4:20bits 定址區域
<!-- p.58 figure 2.6 slide 23-->
##### Calculation of LOC
- Line 10 `loc: 0000` `FIRST STL` `RETADR`<!-- 補手寫筆記圖 -->
- Line 15 `loc: 0006` `+JSUB` format 4 的指令(4 bytes)
- Line 20 `loc: 000A`
:::info
Location from **0006** + 4 bytes = **000A**(不是0009)
:::
##### PC-Relative Addressing Modes
- Line 40 `loc: 0017` `CLOOP`
![](https://i.imgur.com/0172bar.png)
<!--Line 105 `RESB 4096`-->
##### Base-Relative Addressing Modes
![](https://i.imgur.com/SHs2mOt.png)
因為BUFFER 的Loc 與 Line160 的 Loc 相差太多,因此不能用PC-Relative(disp 放不下)
`105` <font color="red">`0036`</font> `BUFFER RESB 4096`
$\vdots$
`160` <font color="red">`104E`</font> `STCH BUFFER,X 57C003`
因此設定一個BASE ADDRESS(低於 LDB #LENGTH)
`105` `0033` `LENGTH RESW 1`
:::warning
如果 PC-Relative 跟 Base-Relative 都算不出位置 assembler 就會出 warning
:::
##### Immediate Addressing Mode
![](https://i.imgur.com/tARswgC.png)
加上`#`來指定只要immediate 而非Address
- 當 immediate 大於等於4096時,要用format 4 而非 format 3
- 可以設定 `p` 成 1 來改成 PC-Relative mode
##### Indirect Addressing Mode
![](https://i.imgur.com/lkaF9OQ.png)
##### 如何計算Object Code
:::spoiler 計算```0006 CLOOP +JSUB RDREC```的 object code
1. 因為 ```+SUB``` 所以知道是 format 4
2. 因為 format 4(4 byte),所以可知 PC 此時是 ```000A```
3. TA 為 ```RDREC```(位置:1036)
<!-- 4. 待補 -->
:::
#### 2.2.2 Program Relocation
- 絕對位置程式
- 程式的起始地址在組譯的時候就已經決定好了,每次載入程式的時候執行的位置都相同
- 缺點:
- 記憶體無法有效的利用跟共享
- 記憶體中的目的碼不易辨識其值為位置還是資料
- 可重定位程式
- 程式的起始地點由載入時決定,每次載入的位置未必相同
- 包含由組譯器註明需做位址修正的資訊目的程式
- 組譯器產生可重定位程式之目的碼時,會加入一些資訊(修正記錄)供載入程式作為調整位址用(加入程式之起始位址)
##### Modification record(format 4 only)
|Col|Content|
|:-:|:-|
|1|M|
|2~7|修正欄的起始位置|
|8~9|修正欄的長度(in half byte)|
:::spoiler `0006 CLOOP +JSUB RDREC` 的 modification record
```
Loc | Source statement | Object Code
-------------------------------------
0006 CLOOP +JSUB RDREC 4B101036
```
M 000007 05
從第 7 個 byte 開始修改、修改 5 個 half bytes
:::
原理:將指定長度的half bytes 加上 START 的位置
### 2.3 Machine-Independent Assembler Features
#### 2.3.1 Literals(常值)
設計理念
- 讓工程師可以將常數操作數的值寫作作為他的指令的一部分
- 這可以讓我們可以不用
- 另外找地方宣告變數定義這些常量
- 在程序中的其他地方為它們組成標籤
##### 常量 v.s. 立即數
- 常量(literal)
- 由組譯器配予一個地址存放該常量,並將該常量的記憶體位置作為指令的目標地址
- 立即數(immediate operand)
- 操作數值作為機器指令的一部分來組裝
- 常數(constant)
- 一個不會變的東西
```
const float pi = 3.14 //這邊的 pi 會說是一個 constant
int a = 20 //這邊的 20 會說是一個 literal
```
##### 實作
- 常量池
- 程式中用到的常量會被集中到一個或多個 literal pools
- 通常在程式最後面
- 在一些情況下需要將文字放入對象程式中某個其他位置的池中
- 組譯指引:`LTORG`(將 `LTORG` 前用到的常量先集中在該指令之後)
- 原因:為了讓文字操作數接近指令
- 重複的常量
- 組譯器應該辨識重複的常量並只儲存指令中數據值的一份copy
- 定義表達式的比較
- 值不同但是名稱相同的東西。
e.g. `LOCCTR=*` 指的是當前 PC,在兩個不同地方宣告 =* 雖然表達式一樣但所帶入的值不同
- 生成數值的比較
- 使用生成數據值的好處通常不足以證明組譯器中的額外複雜性是合理的<!--這個我看不懂意思-->
- LITTAB
- 格式
- 常量、操作數數值、長度、地址
- pass 1
- 將掃描到的常量的其名字、值跟長度加入 LITTAB
- 每當掃到 `LTORG` 或到程式結尾時就產生一個 literal pool ,並將地址分配到 LITTAB 中
- pass 2
- 根據 LITTAB 中常量名字對應的地址產生機器指令
- 看要用 BYTE 還是 WORD 生成數值
- 產生 modification code (如果是以地址表式的)
#### 2.3.2 Symbol Defining Statement
設計理念
- 允許工程師可以自己定義自己的符號
- 指令或資料區上的標籤
- 這類 label 的值是賦值給 statement 的位置
- 定義符號
- `symbol EQU value`
- `value` 可以是常數、其他符號、表達式
- 讓原始碼更好讀
- 沒有 foward reference
- 常用於...
- 增加可讀性
```
MAXLEN EQU 4096
+LDT #MAXLEN
```
- 以數字替代暫存器的助記符
```
A EQU 0
X EQU 1
L EQU 2
```
#### ORG(Origin)
- 間接給符號賦值
- 將 PC 重製為指定值
- `ORG value`
- `value` 可以是常數、其他符號、表達式
- 沒有 foward reference
- e.g. 假設今天要宣告一個表格
- SYMBOL:6 bytes, VALUE:1 word, FLAG:2 bytes
![](https://i.imgur.com/rUbBbU8.png)
- 用一般方法
```
STAB RESB 1100
SYMBOL EQU STAB
VALUE EQU STAB+6
FLAG EQU STAB+9//每次都要根據STAB的位置+
```
- 用 `ORG`
```
STAB RESB 1100
ORG STAB //從 STAB開始算PC
SYMBOL RESB 6
VALUE RESW 1
FLAGS RESB 2
ORG STAB+1100 //校正回歸原來的PC
```
- 限制
- `EQU` 右手邊的符號一定要是定義過的東西,否則組譯器無法在 pass 1 將其位置記錄下來
#### Expression
> 允許 operand 可以用常量跟符號以外的東西表示,像是可以由多個符號或常量與 $+, -, *, /$ 等組合
e.g. `MAXLEN EQU BUFFEREND-BUFFER`
可以分成兩種
1. absolute expression
2. relative expression
- `BUFFER` 跟 `BUFFEREND` 都是 relative terms,表示程式內的位置
- 但是 `BUFFEREND-BUFFER` 代表一個絕對值
- 當兩正負號相反的 relative term 配對時,address剛好被抵銷,所以是 absolute value
- relative terms 都不能跟 $*, /$ 做組合
- 錯誤示範
```
BUFFEREND+BUFFER
100-BUFFER
3*BUFFER
```
- 記錄在 SYMTBL 成這樣
![](https://i.imgur.com/gqct9VH.png)
<!-- to p.44 -->
#### Program Blocks
> 重新排序 Object program unit 來讓有互相 reference 的程式碼靠進一點.
`USE [blockname]`
- 一開始的 statement 被預設為未命名(default)的一部分
- 如果沒有使用 `USE` 則整個程序屬於單個 block
- 每個 program block 可能包含數個分開的程序段
##### Implementation
- Pass 1
- 每個 block 都有一個**單獨的 location counter**(起始值為0)
- 每個 label 都分配了一個相對於包含該 label 的 block 的開始的位置
- 在 pass 1 最後,每個 block 最新的 location counter 值表示每個 block 的長度
- 接著組譯器就可以在目的碼中為每個 block 分配一個起始位置
- Pass 2
- 對一個 symbol 在 SYMTAB 中找到其相對於自己的 block 的位置
- 把它加上 working table 中該 block 的起始位置即為該 symbol 的 TA
-
> Forward reference must occur.
Therefore, 2 Pass is needed.
- **SYMTAB**
| name | block | Loc |
| ------ | ----- | ---- |
| Buffer | 1 | 1000 |
- **Block information**(在 pass 1 中產生出來的東西)
![](https://i.imgur.com/xyglN0Q.png)
- 在產生目的碼時,不需要重新安排整個目的碼的順序,只需要遇到不同的 block 時寫入不同的 T record 即可
#### Control Sections
- 常出現於程序的子程序或其他邏輯細分
- 讓我們可以分別組裝、加載、操作這些控制部分
- 一個 sectot 可能需要參考另一段 sectior 中的指令或是數據
- 所以有一些方法可以把他們連結在一起
`EXTDEF name[,name]` 宣告一些會在其他部分會被使用的東西
`EXTREF name[,name]` 宣告一些別處宣告的東西
##### 實作
define record(`EXTDEF name[,name]`)
|Col|Content|
|:-:|:-|
|1|D|
|2~7|外部符號名稱|
|8~13|跟此 control sector 的相對位置|
|14~73|重複2~13的東西(如果有其他的東西)|
refer record(`EXTREF name[,name]`)
|Col|Content|
|:-:|:-|
|1|R|
|2~7|外部參考的東西的名稱|
|8~73|重複 2~7 的東西|
Modification record
|Col|Content|
|:-:|:-|
|1|M|
|2~7|如上|
|8~9|如上|
|11~16|要在指定段中增加或是減去的外部符號|
### 2.4 Assembler Design Options
### 2.5 Implementation Examples]
### Class & Slide nodes
####
*[Object codes]: 機器用的程式碼(目的碼)