TAOCP 1.3.2 Exercise 8

Chương trình được đặt tên là "MYSTERY PROGRAM" chứa một chuỗi lệnh MIXAL, và yêu cầu là xác định chức năng của chương trình bằng cách phân tích từng lệnh theo tay.

taocpmathematicsalgorithmsvolume-1medium

Section 1.3.2: The MIX Assembly Language

Exercise 8. ▶ [24] What does the following program do? (Do not run it on a computer, figure it out by hand!)

* MYSTERY PROGRAM
BUF   ORIG  *+3000
1H    ENT1  1
      ENT2  0
      LDX   4F
2H    ENT3  0,1
3H    STZ   BUF,2
      INC2  1
      DEC3  1
      J3P   3B
      STX   BUF,2
      INC2  1
      INC1  1
      CMP1  =75=
      JL    2B
      ENN2  2400
      OUT   BUF+2400,2(18)
      INC2  24
      J2N   *-2
      HLT
4H    ALF   AAAAA
      END   1B

Exercises

These exercises are short programming problems, representing typical computer applications and covering a wide range of techniques. Every reader is encouraged to choose a few of these problems, in order to get some experience using MIX as well as a good review of basic programming skills. If desired, these exercises may be worked concurrently as the rest of Chapter 1 is being read.

The following list indicates the types of programming techniques that are involved:

The use of switching tables for multiway decisions: exercises 9, 13, and 23.

The use of index registers with two-dimensional arrays: exercises 10, 21, and 23.

Unpacking characters: exercises 13 and 23.

Integer and scaled decimal arithmetic: exercises 14, 16, and 18.

The use of subroutines: exercises 14 and 20.

Input buffering: exercise 13.

Output buffering: exercises 21 and 23.

List processing: exercise 22.

Real-time control: exercise 20.

Graphical display: exercise 23.

Whenever an exercise in this book says, "write a MIX program" or "write a MIX subroutine," you need only write symbolic MIXAL code for what is asked. This code will not be complete in itself, it will merely be a fragment of a (hypothetical) complete program. No input or output need be done in a code fragment, if the data is to be supplied externally; one need write only LOC, OP, and ADDRESS fields of MIXAL lines, together with appropriate remarks. The numeric machine language, line number, and "times" columns (see Program M) are not required unless specifically requested, nor will there be an END line.

On the other hand, if an exercise says, "write a complete MIX program," it implies that an executable program should be written in MIXAL, including in particular the final END line. Assemblers and MIX simulators on which such complete programs can be tested are widely available.

Verified: yes
Solve time: 1m31s

Solution

Chương trình được đặt tên là "MYSTERY PROGRAM" chứa một chuỗi lệnh MIXAL, và yêu cầu là xác định chức năng của chương trình bằng cách phân tích từng lệnh theo tay. Ta tiến hành tuần tự.

Bước 1. Khởi tạo các thanh ghi và địa chỉ bộ nhớ.

  • BUF ORIG *+3000 định nghĩa địa chỉ cơ sở của mảng BUF cách dòng hiện tại 3000 từ tương đối hiện tại.
  • 1H ENT1 1 gán rI1 \leftarrow 1. Đây sẽ là biến đếm cho số ký tự đã ghi hoặc số lần lặp.
  • ENT2 0 gán rI2 \leftarrow 0. Thanh ghi này sẽ được sử dụng để đánh chỉ số hoặc lưu tạm giá trị.
  • LDX 4F nạp giá trị từ địa chỉ BUF+4 vào thanh ghi X; giá trị này chưa xác định từ dữ liệu, nhưng có thể coi là địa chỉ đích cho lưu trữ sau này.

Bước 2. Thiết lập vòng lặp chính.

  • ENT3 0,1 gán rI3 \leftarrow 1. Thanh ghi I3 dùng để làm bộ đếm lặp trong vòng lặp nội bộ.
  • STZ BUF,2 lưu 0 vào BUF[rI2] với phần mở rộng 2; tức là xóa ô nhớ hiện tại.
  • INC2 1 tăng rI2 \leftarrow rI2 + 1 để trỏ sang ô tiếp theo.
  • DEC3 1 giảm rI3 \leftarrow rI3 - 1. Sau đó J3P 3B kiểm tra nếu rI3 > 0 quay lại nhãn 3H; hiện tại rI3 = 0 nên vòng lặp này chỉ thực hiện một lần, tức chỉ xóa một ô và chuẩn bị bộ nhớ.
  • STX BUF,2 lưu giá trị trong X vào BUF[rI2] (địa chỉ đích đã được nạp ở bước 1). Tương ứng với việc sao chép một giá trị từ thanh ghi X vào mảng.
  • INC2 1 tăng rI2 thêm 1, trỏ sang ô tiếp theo.
  • INC1 1 tăng rI1 \leftarrow rI1 + 1. Thanh ghi I1 giữ số lượng ký tự hoặc số dòng.
  • CMP1 =75= so sánh rI1 với 75. Đây có thể là giới hạn cho số lần lặp, ví dụ 75 ký tự trên một dòng.
  • JL 2B nếu rI1 < 75 nhảy về nhãn 2H; tức là vòng lặp bên ngoài sẽ lặp lại cho đến khi rI1 = 75.

Bước 3. Xử lý in ra thiết bị.

  • ENN2 2400 nạp giá trị 2400 vào thanh ghi E hoặc tương đương với phép cộng địa chỉ. Mục đích là tính địa chỉ in.
  • OUT BUF+2400,2(18) in từ BUF + 2400 ra thiết bị số 18 (theo PRINTER trong ví dụ chương trước) với độ dài 2 từ. Đây là bước in ra máy in.
  • INC2 24 tăng chỉ số bộ đệm để chuẩn bị lần in tiếp theo.
  • J2N *-2 nếu rI2 < 0 nhảy trở lại 2 dòng trước, nhưng rI2 đang tăng; vòng lặp này tiếp tục in các đoạn bộ nhớ cho đến hết.
  • HLT kết thúc chương trình.

Bước 4. Nội dung dữ liệu.

  • ALF AAAAA tại nhãn 4H chỉ định nội dung ký tự A lưu vào bộ nhớ, phục vụ như dữ liệu mẫu hoặc chữ cái để in.

Bước 5. Tổng hợp hành vi.

  1. Chuỗi lệnh thiết lập bộ đếm rI1 và rI2 cho số lần lặp, chuẩn bị bộ nhớ tại BUF.
  2. Vòng lặp từ nhãn 2H đến 3H thực hiện việc sao chép hoặc xóa các ô nhớ và tăng bộ đếm.
  3. Sau khi rI1 = 75, chương trình in dữ liệu từ BUF ra thiết bị số 18 với kích thước 2 từ, sau đó tăng chỉ số để in tiếp.
  4. Dữ liệu gốc (AAAAA) được lưu tại BUF hoặc chỉ để minh họa cách nạp ký tự.
  5. Vòng lặp tổng thể đảm bảo rằng các ô bộ nhớ từ BUF được lấp đầy bằng các ký tự hoặc dữ liệu từ thanh ghi X, rồi in ra theo từng khối 75 ký tự, tương tự như một output buffer.

Chương trình mô phỏng việc tạo ra một bộ đệm, ghi dữ liệu ký tự vào bộ đệm, đếm số ký tự, và in ra từng phần cho máy in. Cấu trúc này gần giống với phần in bảng primes trong Program P, nhưng dữ liệu là ký tự mẫu thay vì số nguyên.

Bước 6. Kết luận.

Chương trình "MYSTERY PROGRAM" xây dựng một bộ đệm ký tự, lặp ghi các ký tự vào bộ đệm cho đến khi đạt 75 ký tự, sau đó in ra thiết bị số 18 theo từng khối 2 từ, và tiếp tục lặp. Đây là một ví dụ điển hình của output buffering trong MIXAL.

Answer: Chương trình thực hiện việc ghi dữ liệu vào bộ đệm ký tự và in ra máy in theo từng khối, với giới hạn 75 ký tự mỗi lần.

$\boxed{\text{Ghi và in dữ liệu ký tự theo khối, dùng output buffer}}$