// SORTSTR      Bubble sort strings

// This program can read 100 or fewer strings (each <= SIZE
// characters) from the standard input, sort them using
// the bubble sort algorithm, and display the sorted list.
        SIZE    = 20              // Max size of a string
        SIZEQ   = ((SIZE+7)/8)*8  // Round up to quad words
        CASES   = 100             // Array length
        .global gets, puts
        .data                     // Declare storage
        .align  8                 // Desired alignment
ARRAY:  .skip   CASES*SIZEQ       // Room for 100 strings
PRMT:   stringz "Enter strings (null line to end)"
         .text                    // Section for code
        .align  32                // Desired alignment
        .global main              // These three lines
        .proc   main              //  mark the mandatory
main:                             //   'main' program entry
        .prologue 12,r32          // Mask for rp, ar.pfs only
        alloc   loc0 = ar.pfs,0,5,3,0  // ins, locals, outs
        .save   rp,loc1           // Must save return address
        mov     loc1 = b0;;       //  to our caller
        .body
first:  add     out0 = @gprel(PRMT),gp  // out0 -> prompt
        mov     loc2 = gp         // Save gp
        br.call.sptk.many b0 = puts  // Unformatted output
        mov     gp = loc2         // Restore gp
        cmp4.lt p6,p0 = ret0,r0   // If any error,
   (p6) br.cond.sptk.few stop0;;  //  go to handler (null)
        mov     loc3 = 0          // loc3 counts strings
        add     loc4 = @gprel(ARRAY),gp;; // loc4 -> store
line:   mov     out0 = loc4       // out0 -> buffer
        br.call.sptk.many b0 = gets  // Unformatted input
        mov     gp = loc2         // Restore gp
        cmp.eq p6,p0 = ret0,r0    // If any error,
   (p6) br.cond.sptk.few stop1;;  //  go to handler (null)
        ld1     r22 = [loc4],SIZEQ-1;; // Get 1st character
        cmp.eq  p6,p7 = 0,r22     // Null code marks end
   (p6) br.cond.spnt.few sort;;   //  of our work here
        add     loc3 = 1,loc3     // Count one line
        st1     [loc4] = r0,1;;   // Ensure null at end
        cmp.gt  p6,p0 = CASES-1,loc3 // If storage is ok,
   (p6) br.cond.sptk.many line    //  then look for more
sort:   add     r20 = -1,loc3;;   // r20 = outer count-down
o_loop: mov     r21 = r20         // r21 = inner count-down
        add     r20 = -1,r20      // Count down for o_loop
        add     r22 = @gprel(ARRAY),gp;; // r22 -> 1st
        add     r23 = SIZEQ,r22;; // r23 -> 2nd string
i_loop: mov     r2 = r22          // r2 -> 1st string (temp)
        mov     r3 = r23          // r3 -> 2nd string (temp)
        add     r21 = -1,r21;;    // Count down for i_loop
look:   ld1     r24 = [r2],1      // r24 = byte from 1st
        ld1     r25 = [r3],1;;    // r25 = byte from 2nd
        cmp.eq  p6,p0 = 0,r24     // Null code means
   (p6) br.cond.sptk.many adjust;;  //  1,2 order is ok
why:    cmp.eq  p6,p0 = r24,r25   // If equal at this byte,
   (p6) br.cond.spnt.few look;;   //  go look at the next
        cmp.ltu p6,p0 = r24,r25   // If 1,2 order is ok,
   (p6) br.cond.spnt.many adjust  //  go on to next strings
        mov     r2 = r22          // r2 -> 1st string (temp)
        mov     r3 = r23;;        // r3 -> 2nd string (temp)
        mov     r26 = (SIZEQ/8)-1 // r26 = quad word counter
swap:   ld8     r27 = [r2]        // Get a quad word
        ld8     r28 = [r3];;      //  from each string
        add     r26 = -1,r26;;    // Count down...
        st8     [r2] = r28,8      // Swap the data
        st8     [r3] = r27,8      //  between the locations
        cmp.gt  p6,p0 = r26,r0    //  ...until whole strings
   (p6) br.cond.spnt.few swap;;   //      have been swapped
adjust: add     r22 = SIZEQ,r22   // Advance to next 1st
        add     r23 = SIZEQ,r23   // Advance to next 2nd
        cmp.gt  p6,p0 = r21,r0    // Still more work
   (p6) br.cond.sptk.many i_loop;;  //  for inner loop to do?
        cmp.gt  p6,p0 = r20,r0    // Still more work
   (p6) br.cond.sptk.many o_loop  //  for outer loop to do?
        add     loc4 = @gprel(ARRAY-SIZEQ),gp;;
p_loop: add     loc4 = SIZEQ,loc4;; // loc4 -> string
        mov     out0 = loc4       // out1 -> what to print
        add     loc3 = -1,loc3    // Count down for p_loop
        br.call.sptk.many b0 = puts  // C output function
        mov     gp = loc2         // Restore gp
        cmp4.lt p6,p0 = ret0,r0   // If any error,
   (p6) br.cond.sptk.few stop0;;  //  go to handler (null)
        cmp.gt  p6,p0 = loc3,r0   // Still more work
   (p6) br.cond.sptk.few p_loop   //  for print loop to do?
stop0:                            // Output error
stop1:                            // EOF or input error
done:   mov     ret0 = 0          // Signal all is normal
        mov     b0 = loc1         // Restore return address
        mov     ar.pfs = loc0     // Restore caller's ar.pfs
        br.ret.sptk.many b0;;     // Back to command line
        .endp   main              // Mark end of procedure