6.8. BACKWARD: Using Byte Manipulations
We now develop a somewhat more complex program that uses the capability just illustrated to obtain and print characters. The BACKWARD program (Figure 6-8) obtains and stores a line of text. It then accesses the stored bytes in such a way as to reverse their order completely. Input such as evil will be printed as live.
Figure 6-8. BACKWARD: An illustration of accessing bytes
// BACKWARD Print a string backwards
// This program pauses for the user to enter a line
// of text, and prints that text backwards.
NL = 0xa // Newline character
LEN = 96 // Line length allowed
.global chrget,chrput // External references
.type chrget,@function // and their
.type chrput,@function // types
.data // Declare storage
.align 8 // Desired alignment
text: .skip LEN // Storage size (<=2^^13)
.text // Section for code
.align 32 // Desired alignment
.global main // These three lines
.proc main // mark the mandatory
main: // 'main' program entry
.prologue 12,r33 // rp, ar.pfs @r33+
.save ar.pfs,r34 // Previous function state
alloc r34 = ar.pfs,0,6,1,0 // 6 locals, 1 out
.save rp,r33 // Say where we store
mov r33 = b0 // the return address
.body // End of prologue
first: // Now we really begin...
addl r35 = @gprel(text),gp;; // r35 -> 1st byte
add r37 = (LEN-1),r35// r37 -> last byte
mov r36 = r35 // r36 = moving pointer
iloop: mov r32 = r1 // Save gp across calls
br.call.sptk.many b0=chrget // Get one character
mov r1 = r32 // Restore gp
cmp.ne p6,p0 = NL,r8;; // Store unless NL char
(p6) cmp.leu.unc p7,p0 = r36,r37;; // Space remaining?
(p7) st1 [r36] = r8,1 // Store; bump pointer
(p7) br.cond.sptk.few iloop;; // Go get next character
add r36 = -1,r36;; // Decrement the pointer
br.cond.sptk.few otest // First-time test
oloop: ld1 r38 = [r36],-1 // r38 = character to send
br.call.sptk.many b0=chrput;; // Put one character
mov r1 = r32 // Restore gp
otest: cmp.geu p6,p0 = r36,r35 // If more chars remain,
(p6) br.cond.sptk.few oloop // go get next character
mov r38 = NL // r39 = newline to send
br.call.sptk.many b0=chrput // Put one character
mov r1 = r32 // Restore gp
done: mov r8 = 0 // Signal all is normal
mov ar.pfs = r34 // Restore previous state
mov b0 = r33 // Restore exit address
br.ret.sptk.many b0;; // Back to command line
.endp main // Mark end of procedure
|
Command lines for assembling, linking, and running this program are the same as those for the IO_C program (Section 6.7). BACKWARD must be linked with the encapsulated single-character I/O routines in getput.c.
Unlike the simple sequential IO_C program, BACKWARD contains an input loop (starting at iloop) and an output loop (starting at oloop). More complex programs might include additional processing between the loops. BACKWARD simply passes from input directly to output.
The alloc instruction arranges for the use of seven general registers, Gr32–Gr38, from the register stack whose contents will be preserved across the external function calls. Chapter 7 will explain how using Gr38 for the outbound character passed to chrput from the caller BACKWARD, instead of Gr35 from IO_C, makes sense from the viewpoint of the called function chrput.
The algorithm in this program is quite simple. In the input loop, register r36 acts as the storage pointer, each step increasing the address. Register r36 in the output loop is the retrieval pointer, decrementing the address with each step.
This example explains why the word for computer in the French language is ordinateur, a device capable of arranging information, not just performing numerical calculations. Moreover, it shows that a rearrangement can be logical instead of physical. The BACKWARD program does not move a string such as evil into the reversed order of letters for live; rather, it accesses the stored string from the other end with a suitable pointer strategy.
The input loop terminates on the newline character passed from the operating system through chrget. Then predicate register p6 will be false and the subsequent unconditional compare instruction will set predicate register p7 false. The newline character will not be stored, the branch at the bottom of the input loop will not execute, and program flow continues to the output loop. Such predication avoids introducing another branch instruction.
Good programs never expect valid input data and thus implement appropriate “sanity checks.” The BACKWARD program avoids overrunning its data storage by using the unconditional compare instruction inside the input loop. Predicate register p6 will be true for any input character except a newline. If the latest character will not fit in the allocation of LEN bytes at label text, that unconditional compare instruction sets predicate register p7 false. The unwanted character is not stored, and the branch back to iloop cannot occur. Program flow passes to the output loop, where we might consider issuing an error message in a production environment.
We should draw attention to another aspect of this program: We decided to control the output loop using an address limit (unsigned cmp instruction). The output loop might instead have been implemented using a down-counter, since the total number of characters would then be calculable (how?). Nevertheless, using similar address comparisons in the two loops makes the program internally consistent.
People have long had a certain fascination with optical mirroring (for example, the notebooks of Leonardo da Vinci) and with letter and word reversals. Test examples for BACKWARDS could include:
123456789
abracadabra
Erewhon (Samuel Butler, 1872)
Emit no star spin mood
Sore spots lived on
Perhaps you can devise additional illustrations as a pastime.