Membalik sebuah String

Secara tradisional, segmen yang ditujukan untuk instruksi mesin biasa disebut "Text". Nantinya dia akan menjadi sebuah proses jika sudah dieksekusi.

Berikut adalah contoh klasik dalam penggunaan stack. User memasukkan string dan program membalik string tersebut. Untuk memahami program ini bekerja silakan cermati diagram di bawah ini. String "Hello" di push ke dalam stack, character demi character dimulai dari 'H'. Kemudian string di pop out kembali ke dalam buffer string asli. Character terakhir yang di push adalah yang pertama di pop.

Quest 10: (Mengulang) Apa yang dilakukan oleh instruksi berikut ini? lbu $t0,string
Jawab: Meload sebuah byte ke dalam register $t0 dan extended zero

Runtime Stack

Ada kuota yang terbatas di dalam memory, walaupun di sistem komputer terbaik sekalipun. Biasanya ketika program pertama kali masuk, maka operating sistem akan memberikannya sejumlah besar ruang untuk stack.

Ditunjukkan di gambar di bawah bagaimana biasanya operating sistem merapikan memory saat pertama kali program masuk. Contohnya adalah 4GB memory virtual. Bagian memory dari 0x10000000 sampai 0x7FFFFFFF tersedia untuk data segmen dan stack segmen. Kalau dihitung sekitar 1.8GB ruang.

Saat program dimulai, stack pinter diinisialisasi dengan nilai 0x7FFFEFFC (address dari stack pertama sepanjang adalah 32bit atau 4 address). Setelah program berjalan stack akan tumbuh ke bawah. Data segmen juga tumbuh keatas saat program dijalankan.Tentu saja sebagaimana sebuah program yang dinamis, pertumbuhan ini bisa naik atau menyusut. Jika kedua kombinasi ini saling bertemu karena pertumbuha stack maupun data sehingga tidak ada ruang lagi maka inilah yang disebut dengan memory penuh.

Cara lain mungkin dengan membagi setengah kuota untuk stack dan setengah kuota untuk data, tapi untuk sekarang stack boleh melebihi setengah dari kuota ini meskipun ada sedikit data yang bermukin di sana.

Quest 9: manakah segmen yang diperuntukkan untuk instruksi mesin?
Jawab: Text segmen 0x00400000 sampai 0x10000000

Program Selesai

Berikut adalah prgogram yang telah diselesaikan. Jika kamu memiliki banyak register yang tersedia, kamu mungkin menggunakan register daripada stack. Tapi bagi program yang besar, register saja mungkin tidak cukup.

# Evaluate the expression ab - 12a + 18b - 7
#
# Settings: Load delays OFF; Branch delays OFF,
#           Trap file    ON; Pseudoinstructions ON   

        .globl  main

main:   
        lw      $t0,a          # get a
        lw      $t1,bb         # get b
        mul     $t0,$t0,$t1    # a*b
        subu    $sp,$sp,4      # push a*b onto stack
        sw      $t0,($sp)
        
        lw      $t0,a          # get a
        li      $t1,-12        # 
        mul     $t0,$t0,$t1    # -12a
        subu    $sp,$sp,4      # push -12a onto stack
        sw      $t0,($sp)
        
        lw      $t0,bb         # get b
        li      $t1,18         # 
        mul     $t0,$t0,$t1    # 18b
        subu    $sp,$sp,4      # push 18b onto stack
        sw      $t0,($sp)

        li      $t1,-7         # init sum to -7
        lw      $t0,($sp)      # pop 18b
        addu    $sp,$sp,4
        addu    $t1,$t1,$t0    # 18b -7
                
        lw      $t0,($sp)      # pop -12a
        addu    $sp,$sp,4
        addu    $t1,$t1,$t0    # -12a + 18b -7
                
        lw      $t0,($sp)      # pop ab
        addu    $sp,$sp,4
        addu    $t1,$t1,$t0    # ab - 12a + 18b -7
         
done:   li      $v0,1          # print sum
        move    $a0,$t1
        syscall
        li      $v0,10         # exit
        syscall   

        .data
a:      .word  0
bb:     .word  10

Quest 8: (pertanyaan mendalam) Apakah bisa kehabisan memory jika item yang dimasukkan ke dalam stack terlalu banyak?
Jawab: Bisa
Jawaban yang benar: Yes

Program Dilanjutkan

Nilai perkalian di push ke dalam stack dlu, kemudian secara berurutan dikeluarkan dari stack.

# Evaluate the expression ab - 12a + 18b - 7

        .globl  main
        lw      $t0,a          # get a
        lw      $t1,bb         # get b
        mul     $t0,$t0,$t1    # a*b
        subu    $sp,$sp,4      # push a*b onto stack
        sw      $t0,($sp)
        
        lw      $t0,a          # get a
        li      $t1,-12        # 
        mul     $t0,$t0,$t1    # -12a
        subu    $sp,$sp,4      # push -12a onto stack
        sw      $t0,($sp)
        
        lw      $t0,bb         # get b
        li      $t1,18         # 
        mul     $t0,$t0,$t1    # 18b
        subu    $sp,$sp,4      # push 18b onto stack
        sw      $t0,($sp)

        li      $t1,-7         # init sum to -7
        
        lw      $t0,      # pop 18b
        
        addu    $sp,$sp,
        
        addu    $t1,$t1,$t0    # 18b -7

        . . . .

Quest 7: Fill in the blank untuk mengeluarkan 18b dari stack

Contoh

Stack seringkali digunakan untuk menyimpan memory sementara, saat semua register sudah terpakai. Sebuah contoh dari hal ini adalah bagaimana sebuah compiler menerjemahkan ekspresi matematika kedalam kode mesin yang menggunakan stack. Katakanlah rumus matematikanya adalah sebagai berikut ab - 12a + 18b - 7 misal hanya register $t0 dan $t1 yang tersedia.

Sebelum SPIM memulai program maka dia akan menginisialisasi $sp dulu. Pada sebuah komputer yang memakai system operasi maka stack pointer diinisialisasi oleh operating system sebelum control diserahkan ke program user.

Berikut adalah programnya:

# Evaluate the expression ab - 12a + 18b - 7

main:   
        lw      $t0,a          # get a
        lw      $t1,bb         # get b
        mul     $t0,$t0,$t1    # a*b
        
        subu    $sp,$sp,  # push a*b onto stack
        
        sw      $t0,

        . . . . .

        .data
a:      2
bb:     3

Quest 6: Fill in the blank

Pop

Meremove item dari stack disebut operasi pop. Di dalam software, meremove item artinya menyalin isi dari item yang mau diremove ke suatu tempat dan stack pointer diatur.

Gambar di bawah menunjukkan operasi pop. Data pertama-tama dicopy dari atas stack ke alamat baru, kemudian stack pointer dinaikkan 4 nilai.

Untuk pop item di dalam stack, copy item yang ditunjuk oleh pointer kemudian add 4 ke stack pointer.

Berikut adalah contoh program, misal saja item yang mau dipop di salin taruh ke register $t0.

                    # POP the item into $t0:
lw   $t0,($sp)      #   Copy top the item to $t0.
addu $sp,$sp,4      #   Point to the item beneath the old top.

Quest 5: Saat sebuah software menge pop stack, apakah data yang dipop masih tertinggal di memory?
Jawab: Yes
Jawaban yang benar: Yes

Push

Dengan konvensi software $sp akan selalu menunjuk ke alamat terupdate dari stack pointer. Dan juga dengan konvensi maka stack akan tumbuh ke bawah (dalam hal address memory). Jadi klo dipikir-pikir menambahkan 1 item dengan panjang 32bit maka address yang berada di dalam $sp dikurangi 4 dan memasukkan item tadi ke address yang telah di update tersebut. Operasi ini disebut push.

untuk push item ke dalam stack, pertama-tama subtract 4 dari stack pointer, kemudian simpan item ke dalam addres stack pointer.

Berikut adalah jika diterjemahkan ke dalam kode, misal nilai yang mau di push ke dalam stak berada di register $v0.

                    # PUSH the item in $t0:
subu $sp,$sp,4      #   point to the place for the new item,
sw   $t0,($sp)      #   store the contents of $t0 as the new top.

Quest 4: Di stack jika satu item diremove apa yang akan terjadi?
Jawab: $sp add 4

Stack MIPS Upside-down

Stack biasanya suka dipanggil dengan nama MTKP "Masuk Terakhir Keluar Pertama" LIFO "Last In First Out".

Elemen-elemen data di stack merupakan 32bit atau 1word. Secara umum stack boleh digunakan untuk berbagai macam data. Tapi di bab ini kita akan menggunakan 32bit stack data.

Gambar di bawah ini menunjukkan stack dengan elemen 32bit. Register stack pointer $sp dengan konvensi point menunjukkan sebuah item di dalam stack. Nama register $sp adalah register $29 untuk basic register.

Cara yang biasa digunakan untuk menggambar stack adalah upside-down(kebalik). Di gambar secara analogi item terbawah stack adalah yang berisi -92 sementara yang berisi 81 adalah item teratas dari sebuah stack. Ini artinya jika kita menumpuk piring, maka piring akan tumbuh ke atas, sementara jika kita menumpuk address maka address akan tumbuh ke bawah.

Sebelum operating sistem berjalan, maka program harus memastikan bahwa ada range tertentu yang dianggap sebagai stack dan kemudian menginisialisai $sp dengan address dari stack tersebut.

Quest 3: Jika sebuah data atau item (misal berisi 103) ditaruh ke stack, maka dia ada dimana?
Jawab: berada di bawah 81

Stack

Stack adalah metode dalam mengorganisir data memory. Data di dalam memori dibayangkan seperti sebuah tumpukan-tumpukan barang. Seringkali stack dibayangkan seperi sebuah tumpukan piring. Data ditaruh atau diambil atau dihapus adalah dianalogikan seperti menaruh sebuah piring ke tumpukan piring atau menghapusnya.

Normalnya operasi stack dilakukan seperti kita menaruh piring ke tumpukan piring. Jika kamu membutuhkan stack maka kamu mengampil piring yang paling atas, dan jika kamu meletakkan stack maka kamu meletakkan piring ke tumpukan paling atas juga.

Quest 2: Manakah stack yang terakhir ditaruh dan manakah yang pertama kali diambil?
Jawab: Stack yang pertama terakhir ditaruh adalah stack yang paling atas, begitu juga stack yang pertama kali diambil adalah stack yang paling atas.

BAB 25 — Run-time Stack

Bab ini membahas run-time stack dan register stack pointer $sp.

Topik:

• Stack
• Register stack pointer $sp
• Operasi Push stack dan Pop stack
• MIPS runtime stack
• Compiler yang menggunakan stack
• Contoh pembalikan string

Quest 1: Katakanlah kamu sedang menggambil satu piring dari tumpukan piring di meja makan, manakah yang biasanya kamu ambil?

Jawab: Piring yang paling atas

Program Komplit

Di bawah ini adalah prgram komplitnya. Tidak jauh beda dari terjemahan bahasa "C" untuk loop.

        .globl  main

main:   
        li    $v1,0              # zero the sum
        li    $t1,0              # init index to 0
        li    $t2,0              # init loop counter
        
for:    beq   $t2,5,endfor       # for ( i=0; i < 5 ;i++ )
        lw    $v0,array($t1)
        addu  $v1,$v1,$v0        #     sum = sum+array[i]
        addi  $t1,$t1,4          #     increment index
        addi  $t2,$t2,1          #     increment counter
        b     for
 
endfor:
        li    $v0,10             # exit
        syscall   

        .data
array:  .word  1,2,3,-5,1

Quest 15: Beberapa bahasa (seprti PASCAL) boleh menjadikan angka sembarang untuk dijadikan index pertama dari sebuah array. Dapatkan bahasa seperti itu diterjemahkan ke dalam MIPS?
Jawab: Bisa

Array Integer

Berikut adalah program yang sama seperti sebelumnya, kecuali sekarang arraynya adalah menggunakan integer 32bit. Logikanya sama saja:

        .globl  main

main:   
        li    $v1,0              # zero the sum
        li    $t1,_____          # init index to ???
        
        li    $t2,0              # init loop counter
for:    beq   $t2,5,endfor       # for ( i=0; i < 5 ;i++ )

        l___  $v0,array($t1)
        
        addu  $v1,$v1,$v0        #     sum = sum+array[i]
        
        addi  $t1,$t1,_____      #     increment index
        
        addi  $t2,$t2,_____      #     increment counter
        b     for
 
endfor:
        li    $v0,10             # exit
        syscall   

        .data
array:  .word  1,2,3,-5,1

Quest 14: Fill in the blank

Index dimulai dari Zero

Pengalaman menunjukkan bahwa mengindex array dengan cara index zero adalah cara yang terbaik. Elemen pertama dari sebuah array menempati urutan ke zero dari sebuah barisan bilangan. Untuk menggerakkan address dimulai dari address + 0 sebagai elemen pertama sebuah array yang menempati urutan terdepan.

Berikut adalah contoh program yang menjumlahkan semua elemen array:

        li    $v1,0              # zero the sum
        li    $t1,0              # init index to 0
        li    $t2,0              # init loop counter
        
for:    beq   $t2,5,endfor       # for ( i=0; i < 5 ;i++ )
        lb    $v0,data($t1)
        addu  $v1,$v1,$v0        #     sum = sum+data[i]
        addi  $t1,$t1,1          #     increment index
        addi  $t2,$t2,1          #     increment counter
        b     for

endfor: 
        . . . 
      
data: .byte  6,34,12,-32, 90   

Quest 13: Jika arraynya menggunakan 32bit integer maka berapa langkah untuk menunjuk address dari elemen berikutnya?
Jawab: 4

Empat Level

Ide ini seperti "benar-benar ilmu komputer". Diperlukan pemikiran mendalam untuk bisa melihat apa yang sebenarnya terjadi. Berikut adalah tabelnya

Yang ditulis programmer	Terjemahan dari assembler exrended	Yang dilakukan basic assembler	Yang terjadi saat dijalankan
li $t1,2 lb $v0,data($t1)	ori $t1,$0,2 lui $at,4097 addu $at,$at,$t1 lb $v0,0($at) (4097 adalah 0x40970000 dari alamat)	Basic assembly menerjemahkan kedalam kode mesin 34090002 3c011001 00290821 80220000	Intruksi ketiga meletakkan address dari elemen array ketiga kedalam register $1. Instruksi keempat meletakkan isi dari address tersebut (elemen array ketiga) ke dalam register $2 ( $v0).

Quest 12: Index apa yang mengawali array di bahasa C dan Java?
Jawab: Index zero (yaitu elemen pertama dari sebuah array menempati indek zero)

Address yang Terindex

Dalam memperluas implementasi intruksi, assembler extended menggunakan mode pengalamatan baru. Yaitu Address yang terindex. Sebuah mode pengalamatan yang berguna untuk array.

li    $t1,2                 # index 2
      lb    $v0,data($t1)         # $v0 = data[$t1]
      . . . 
      
data: .byte  6,34,12,-32, 90      # index zero is first

Anggap data adalah array yang panjangnya 5 byte. Kemudian instruksi lb meload elemen array yang berada di index 2 (di dalam array elemen pertama disebut index 0 maka index 2 adalah elemen ketiga).

ori   $t1,$0,2           # index 2
      lui   $at,4097           # $at register gets address "data"
      addu  $at,$at,$t1        # add index to $at
      lb    $v0,0($at)         # $v0 = data[$t1]
      . . . 
      
data: .byte  6,34,12,-32, 90   

Extended assembler menggunakan nilai ini sebagai pointer