home *** CD-ROM | disk | FTP | other *** search
/ Media Share 9 / MEDIASHARE_09.ISO / progmisc / tde221.zip / SORT.C < prev    next >
C/C++ Source or Header  |  1993-04-01  |  24KB  |  724 lines
  1. /*
  2.  * These functions sort lines according to keys in a marked BOX block.
  3.  *
  4.  * Being that the data structure was changed from a big text buffer to a
  5.  * linked list, we can replace the simple insertion sort algorithm with a
  6.  * much faster sort algorithm.  The classic search and sort reference is by
  7.  * Donald E. Knuth, _The Art of Computer Programming; Volume 3:  Sorting and
  8.  * Searching_.  One of the fastest and most widely used general purpose
  9.  * sorting algorithms is the "Quicksort" algorithm.
  10.  *
  11.  * For implementation hints and guidelines on the Quicksort algorithm, one
  12.  * might read the original Quicksort paper by C. A. R. Hoare or anything
  13.  * by Robert Sedgewick.  Although Dr. Sedgewick includes a chapter on
  14.  * Quicksort in his intro computer science textbooks, _Algorithms in X_,
  15.  * I prefer the detailed hints and guidelines in his 1978 CACM paper.
  16.  * Incidentally, Dr. Sedgewick's Ph.D. dissertation was on the modification
  17.  * and mathematical analysis of the Quicksort algorithm.
  18.  *
  19.  *
  20.  * See:
  21.  *
  22.  *   Charles Antony Richard Hoare, "Algorithm 63: Partition."  _Communications
  23.  *      of the ACM_, 4 (No. 7): 321, 1961.
  24.  *
  25.  *   Charles Antony Richard Hoare, "Algorithm 64: Quicksort."  _Communications
  26.  *      of the ACM_, 4 (No. 7): 321, 1961.
  27.  *
  28.  *   Charles Antony Richard Hoare, "Quicksort."  _The Computer Journal_,
  29.  *      5 (April 1962 - January 1963): 10-15, 1962.
  30.  *
  31.  * See also:
  32.  *
  33.  *   Donald Ervin Knuth, _The Art of Computer Programming; Volume 3:  Sorting
  34.  *     and Searching_, Addison-Wesley, Reading, Mass., 1973, Chapter 5,
  35.  *     Sorting, pp 114-123.  ISBN 0-201-03803-X.
  36.  *
  37.  *   Robert Sedgewick, "Implementing Quicksort Programs."  _Communications
  38.  *      of the ACM_, 21 (No. 10): 847-857, 1978.
  39.  *
  40.  *
  41.  *                           Quicksort in TDE
  42.  *
  43.  * Quicksort in TDE is a stable, non-recursive implementation based on
  44.  * Program 2, page 851, CACM, 21 (No. 10), 1978, by Robert Sedgewick.  My
  45.  * partition algorithm finds the median-of-three.  Then, it walks from the
  46.  * head of the list, comparing nodes, and uses the first occurrence of the
  47.  * key of the median-of-three as the partition node.  Mostly by accident
  48.  * and partly by design, my partition routine uses a "fat pivot" to keep
  49.  * equal nodes in the same relative order as they appear in the file (the
  50.  * definition of a stable sort).  By using the first median-of-three node
  51.  * as the partitioning node, 1) sorting a sorted list is fairly fast and
  52.  * 2) encountering a worst case is very unlikely.  TDE will sort, fairly
  53.  * fast, multiple keys ascending or descending, ignore or match case, and
  54.  * preserve order in the file, while using a custom sort sequence for your
  55.  * favorite domestic or foreign language.
  56.  *
  57.  *
  58.  * New editor name:  TDE, the Thomson-Davis Editor.
  59.  * Author:           Frank Davis
  60.  * Date:             June 5, 1991, version 1.0
  61.  * Date:             July 29, 1991, version 1.1
  62.  * Date:             October 5, 1991, version 1.2
  63.  * Date:             January 20, 1992, version 1.3
  64.  * Date:             February 17, 1992, version 1.4
  65.  * Date:             April 1, 1992, version 1.5
  66.  * Date:             June 5, 1992, version 2.0
  67.  * Date:             October 31, 1992, version 2.1
  68.  * Date:             April 1, 1993, version 2.2
  69.  *
  70.  * This code is released into the public domain, Frank Davis.
  71.  * You may use and distribute it freely.
  72.  */
  73.  
  74. #include "tdestr.h"
  75. #include "common.h"
  76. #include "tdefunc.h"
  77. #include "define.h"
  78.  
  79.  
  80. /*
  81.  * Name:    sort_box_block
  82.  * Purpose: sort lines according to text in marked BOX block
  83.  * Date:    June 5, 1992
  84.  * Passed:  window:  pointer to current window
  85.  * Notes:   quick sort and insertion sort the lines in the BOX buff according
  86.  *           to stuff in a box block.
  87.  */
  88. int  sort_box_block( WINDOW *window )
  89. {
  90. int  prompt_line;
  91. int  block_type;
  92. line_list_ptr ll;
  93. register file_infos *file;
  94. WINDOW *sw;
  95. int  rc;
  96. char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
  97.  
  98.    /*
  99.     * make sure block is marked OK
  100.     */
  101.    rc = OK;
  102.    prompt_line = window->bottom_line;
  103.    entab_linebuff( );
  104.    if (un_copy_line( window->ll, window, TRUE ) == ERROR)
  105.       return( ERROR );
  106.    check_block( );
  107.    if (g_status.marked == TRUE) {
  108.       file  = g_status.marked_file;
  109.       block_type = file->block_type;
  110.       if (block_type == BOX) {
  111.          /*
  112.           * sort ascending or descending?
  113.           */
  114.          rc = get_sort_order( window );
  115.          if (rc != ERROR) {
  116.             file->modified = TRUE;
  117.             if (mode.do_backups == TRUE) {
  118.                sw = g_status.window_list;
  119.                for (; ptoul( sw->file_info ) != ptoul( file );)
  120.                   sw = sw->next;
  121.                backup_file( sw );
  122.             }
  123.  
  124.             /*
  125.              * figure the width of the block.
  126.              */
  127.             sort.block_len = file->block_ec + 1 - file->block_bc;
  128.  
  129.             /*
  130.              * save the prompt line and print the quicksort message.
  131.              */
  132.             save_screen_line( 0, prompt_line, line_buff );
  133.             eol_clear( 0, prompt_line, g_display.text_color );
  134.             set_prompt( block22a, prompt_line );
  135.  
  136.             /*
  137.              * set up the sort structure.
  138.              */
  139.             sort.bc  = g_status.marked_file->block_bc;
  140.             sort.ec  = g_status.marked_file->block_ec;
  141.             sort.order_array = (mode.search_case == IGNORE) ?
  142.                                     sort_order.ignore : sort_order.match;
  143.  
  144.             /*
  145.              * save the previous node for use with insertion sort.
  146.              */
  147.             ll = file->block_start->prev;
  148.             quick_sort_block( file->block_br, file->block_er,
  149.                               file->block_start, file->block_end );
  150.  
  151.             /*
  152.              * get back previous node and clean up list with insertion
  153.              *   sort.
  154.              */
  155.             if (ll == NULL)
  156.                ll = file->line_list;
  157.             else
  158.                ll = ll->next;
  159.             set_prompt( block22b, prompt_line );
  160.             insertion_sort_block( file->block_br, file->block_er, ll );
  161.  
  162.             /*
  163.              * housekeeping.  mark the file as dirty and restore the
  164.              *   cursors, which are scrambled during the sort.
  165.              */
  166.             file->dirty = GLOBAL;
  167.             restore_cursors( file );
  168.             restore_screen_line( 0, prompt_line, line_buff );
  169.          }
  170.       } else {
  171.          /*
  172.           * can only sort box blocks
  173.           */
  174.          error( WARNING, prompt_line, block23 );
  175.          rc = ERROR;
  176.       }
  177.    } else {
  178.       /*
  179.        * box not marked
  180.        */
  181.       error( WARNING, prompt_line, block24 );
  182.       rc = ERROR;
  183.    }
  184.    return( rc );
  185. }
  186.  
  187.  
  188. /*
  189.  * Name:    quick_sort_block
  190.  * Purpose: sort lines according to text in marked BOX block
  191.  * Date:    Jaunary 10, 1993
  192.  * Passed:  low:        starting line in box block
  193.  *          high:       ending line in a box block
  194.  *          low_node:   starting node in box block
  195.  *          high_node:  ending node in box block
  196.  * Notes:   Quicksort lines in the BOX block according to keys in
  197.  *           a box block.
  198.  *          because the median of three method is used to find the partion
  199.  *           node,  high - low  should be greater than or equal to 2.
  200.  *          with end recursion removal and sorting the smallest sublist
  201.  *           first, our stack only needs room for log2 N nodes.  a stack
  202.  *           size of 32 can reliably handle several billion lines.
  203.  */
  204. void quick_sort_block( long low, long high, line_list_ptr low_node,
  205.                        line_list_ptr high_node )
  206. {
  207. long low_rline_stack[32];
  208. long high_rline_stack[32];
  209. line_list_ptr low_node_stack[32];
  210. line_list_ptr high_node_stack[32];
  211. long low_count;
  212. long high_count;
  213. long count;
  214. line_list_ptr low_start;
  215. line_list_ptr low_head;
  216. line_list_ptr low_tail;
  217. line_list_ptr high_end;
  218. line_list_ptr high_head;
  219. line_list_ptr high_tail;
  220. line_list_ptr equal_head;
  221. line_list_ptr equal_tail;
  222. line_list_ptr walk_node;
  223. line_list_ptr median_node;
  224. int  i;
  225. int  stack_pointer;
  226.  
  227.    assert( low_node->len != EOF);
  228.    assert( high_node->len != EOF);
  229.  
  230.    stack_pointer = 0;
  231.    while (TRUE) {
  232.  
  233.       /*
  234.        * being that a median-of-three is used as the partition algorithm,
  235.        *  we probably need to have at least 2 nodes in each sublist.  I
  236.        *  chose a minimum of 25 nodes as a SWAG (scientific wild ass guess).
  237.        *  a simple insertion sort mops the list after quicksort finishes.
  238.        */
  239.       while (high - low > 25) {
  240.  
  241.          assert( high >= 1 );
  242.          assert( low  >= 1 );
  243.          assert( low  <= high );
  244.  
  245.          /*
  246.           * start the walk node at the head of the list and walk to the
  247.           *  middle of the sublist.
  248.           */
  249.          walk_node  = low_node;
  250.          count = (high - low) / 2;
  251.          for (; count > 0; count--)
  252.             walk_node = walk_node->next;
  253.  
  254.          /*
  255.           * now, find the median of the low, middle, and high node.
  256.           *
  257.           * being that I am subject to error, let's assert that we really
  258.           *  did find the median-of-three.
  259.           */
  260.          load_pivot( low_node );
  261.          if (compare_pivot( walk_node ) < 0) {
  262.             low_head   = walk_node;
  263.             median_node = low_node;
  264.          } else {
  265.             low_head   = low_node;
  266.             median_node = walk_node;
  267.          }
  268.          high_head = high_node;
  269.          load_pivot( median_node );
  270.          if (compare_pivot( high_node ) < 0) {
  271.             high_head   = median_node;
  272.             median_node = high_node;
  273.          }
  274.          load_pivot( median_node );
  275.          if (compare_pivot( low_head ) > 0) {
  276.             low_tail    = median_node;
  277.             median_node = low_head;
  278.             low_head    = low_tail;
  279.          }
  280.  
  281.          load_pivot( median_node );
  282.  
  283.          assert( compare_pivot( low_head ) <= 0 );
  284.          assert( compare_pivot( high_head ) >= 0 );
  285.  
  286.          /*
  287.           * now, walk again from the head of the list comparing nodes and
  288.           *  use the first occurrence of the median node as the partition.
  289.           */
  290.          walk_node = low_node;
  291.          for (i = 0; ; walk_node = walk_node->next) {
  292.             if (compare_pivot( walk_node ) == 0)
  293.                break;
  294.             i = 1;
  295.          }
  296.  
  297.          /*
  298.           * initialize pointers and counters for this partition.
  299.           */
  300.          low_start  = low_node->prev;
  301.          high_end   = high_node->next;
  302.          low_head   = low_tail  = NULL;
  303.          high_head  = high_tail = NULL;
  304.          low_count  = high_count = 0;
  305.  
  306.          /*
  307.           * setup the first occurrence of the median node as a "fat pivot"
  308.           *  sublist.  there are two cases to consider 1) the first
  309.           *  occurrence of the median node is the first element in the
  310.           *  sublist, i == 0, or 2) the first occurrence of the median node
  311.           *  is somewhere in the sublist.
  312.           */
  313.          if (i == 0)
  314.             walk_node = equal_head = equal_tail = low_node;
  315.          else {
  316.             equal_head = equal_tail = walk_node;
  317.             equal_head->next->prev = equal_head->prev;
  318.             equal_head->prev->next = equal_head->next;
  319.             equal_head->next = low_node;
  320.             walk_node = equal_head;
  321.          }
  322.          load_pivot( equal_head );
  323.  
  324.          /*
  325.           * PARTITION:
  326.           *  put all nodes less than the pivot on the end of the low list.
  327.           *  put all nodes equal to the pivot on the end of the equal list.
  328.           *  put all nodes greater than the pivot on the end of the high list.
  329.           */
  330.          for (count=low+1; count <= high; count++) {
  331.             walk_node = walk_node->next;
  332.             i = compare_pivot( walk_node );
  333.             if (i > 0) {
  334.                if (high_head == NULL)
  335.                   high_head = high_tail = walk_node;
  336.                else {
  337.                   high_tail->next = walk_node;
  338.                   walk_node->prev = high_tail;
  339.                   high_tail = walk_node;
  340.                }
  341.  
  342.                /*
  343.                 * keep a count of the number of nodes in the high list.
  344.                 */
  345.                ++high_count;
  346.             } else if (i < 0) {
  347.                if (low_head == NULL)
  348.                   low_head = low_tail = walk_node;
  349.                else {
  350.                   low_tail->next = walk_node;
  351.                   walk_node->prev = low_tail;
  352.                   low_tail = walk_node;
  353.                }
  354.  
  355.                /*
  356.                 * keep a count of the number of nodes in the low list
  357.                 */
  358.                ++low_count;
  359.             } else {
  360.                equal_tail->next = walk_node;
  361.                walk_node->prev = equal_tail;
  362.                equal_tail = walk_node;
  363.             }
  364.          }
  365.  
  366.          assert( low_count >= 0 );
  367.          assert( low_count < high - low );
  368.          assert( high_count >= 0 );
  369.          assert( high_count < high - low );
  370.  
  371.          /*
  372.           * we just partitioned the sublist into low, equal, and high
  373.           *  sublists.  now, let's put the lists back together.
  374.           */
  375.          if (low_count > 0) {
  376.             low_head->prev = low_start;
  377.             if (low_start != NULL)
  378.                low_start->next = low_head;
  379.             else
  380.                g_status.marked_file->line_list = low_head;
  381.             low_tail->next = equal_head;
  382.             equal_head->prev = low_tail;
  383.          } else {
  384.             equal_head->prev = low_start;
  385.             if (low_start != NULL)
  386.                low_start->next = equal_head;
  387.             else
  388.                g_status.marked_file->line_list = equal_head;
  389.          }
  390.          if (high_count > 0) {
  391.             high_head->prev = equal_tail;
  392.             equal_tail->next = high_head;
  393.             high_tail->next = high_end;
  394.             high_end->prev  = high_tail;
  395.          } else {
  396.             equal_tail->next = high_end;
  397.             high_end->prev   = equal_tail;
  398.          }
  399.  
  400.          /*
  401.           * now, lets look at the low list and the high list.  save the node
  402.           *  pointers and counters of the longest sublist on the stack.
  403.           *  then, quicksort the shortest sublist.
  404.           */
  405.          if (low_count > high_count) {
  406.  
  407.             /*
  408.              * if fewer than 25 nodes in the high count, don't bother to
  409.              *  push the stack -- sort the low list.
  410.              */
  411.             if (high_count > 25) {
  412.                low_rline_stack[stack_pointer]  = low;
  413.                high_rline_stack[stack_pointer] = low + low_count - 1;
  414.                low_node_stack[stack_pointer]   = low_head;
  415.                high_node_stack[stack_pointer]  = low_tail;
  416.                ++stack_pointer;
  417.                low       = high - high_count + 1;
  418.                high      = high;
  419.                low_node  = high_head;
  420.                high_node = high_tail;
  421.             } else {
  422.                low       = low;
  423.                high      = low + low_count - 1;
  424.                low_node  = low_head;
  425.                high_node = low_tail;
  426.             }
  427.          } else {
  428.  
  429.             /*
  430.              * if fewer than 25 nodes in the low count, don't bother to
  431.              *  push the stack -- sort the high list.
  432.              */
  433.             if (low_count > 25) {
  434.                low_rline_stack[stack_pointer]  = high - high_count + 1;
  435.                high_rline_stack[stack_pointer] = high;
  436.                low_node_stack[stack_pointer]   = high_head;
  437.                high_node_stack[stack_pointer]  = high_tail;
  438.                ++stack_pointer;
  439.                low       = low;
  440.                high      = low + low_count - 1;
  441.                low_node  = low_head;
  442.                high_node = low_tail;
  443.             } else {
  444.                low       = high - high_count + 1;
  445.                high      = high;
  446.                low_node  = high_head;
  447.                high_node = high_tail;
  448.             }
  449.          }
  450.  
  451.          assert( stack_pointer < 32 );
  452.       }
  453.  
  454.       /*
  455.        * now that we have sorted the smallest sublist, we need to pop
  456.        *  the long sublist(s) that were pushed on the stack.
  457.        */
  458.       --stack_pointer;
  459.       if (stack_pointer < 0)
  460.          break;
  461.       low       = low_rline_stack[stack_pointer];
  462.       high      = high_rline_stack[stack_pointer];
  463.       low_node  = low_node_stack[stack_pointer];
  464.       high_node = high_node_stack[stack_pointer];
  465.    }
  466. }
  467.  
  468.  
  469. /*
  470.  * Name:    insertion_sort_block
  471.  * Purpose: sort small partitions passed in by qsort
  472.  * Date:    January 10, 1993
  473.  * Passed:  low:          starting line in box block
  474.  *          high:         ending line in a box block
  475.  *          first_node:   first linked list node to sort
  476.  * Notes:   Insertion sort the lines in the BOX buff according to stuff in
  477.  *           a box block.
  478.  */
  479. void insertion_sort_block( long low, long high, line_list_ptr first_node )
  480. {
  481. long down;                      /* relative line number for insertion sort */
  482. long pivot;                     /* relative line number of pivot in block */
  483. long count;
  484. line_list_ptr pivot_node;       /* pointer to actual text in block */
  485. line_list_ptr down_node;        /* pointer used to compare text */
  486. text_ptr key;
  487. int  dirty_flag;
  488. int  len;
  489.  
  490.    /*
  491.     * make sure we have more than 1 line to sort.
  492.     */
  493.    if (low < high) {
  494.  
  495.       count = (int)(high - low) + 1;
  496.       pivot_node = first_node->next;
  497.       for (pivot=1; pivot < count; pivot++) {
  498.          load_pivot( pivot_node );
  499.          key = pivot_node->line;
  500.          len = pivot_node->len;
  501.          dirty_flag = pivot_node->dirty;
  502.          down_node = pivot_node;
  503.          for (down=pivot-1; down >= 0; down--) {
  504.             /*
  505.              * lets keep comparing the keys until we find the hole for
  506.              *  pivot.
  507.              */
  508.             if (compare_pivot( down_node->prev ) > 0) {
  509.                down_node->line = down_node->prev->line;
  510.                down_node->len = down_node->prev->len;
  511.                down_node->dirty = down_node->prev->dirty;
  512.             } else
  513.                break;
  514.             down_node = down_node->prev;
  515.          }
  516.          down_node->line = key;
  517.          down_node->len  = len;
  518.          down_node->dirty = (char)dirty_flag;
  519.          pivot_node = pivot_node->next;
  520.       }
  521.    }
  522. }
  523.  
  524.  
  525. /*
  526.  * Name:    load_pivot
  527.  * Purpose: load pivot point for insertion sort
  528.  * Date:    June 5, 1992
  529.  * Passed:  text:  line that contains the pivot
  530.  */
  531. void load_pivot( line_list_ptr node )
  532. {
  533.    sort.pivot_ptr = node->line;
  534.    sort.pivot_len = node->len;
  535. }
  536.  
  537.  
  538. /*
  539.  * Name:    compare_pivot
  540.  * Purpose: compare pivot string with text string
  541.  * Date:    June 5, 1992
  542.  * Passed:  text:  pointer to current line
  543.  * Notes:   the sort structure keeps track of the pointer to the pivot line
  544.  *           and the pivot line length.
  545.  */
  546. int  compare_pivot( line_list_ptr node )
  547. {
  548. register int len;
  549. register int bc;
  550. int  rc;
  551. int  left_over;
  552.  
  553.    len = node->len;
  554.    bc  = sort.bc;
  555.  
  556.    assert( bc >= 0 );
  557.    assert( len >= 0 );
  558.  
  559.    /*
  560.     * is the current line length less than beginning column?  if so, just
  561.     *  look at the length of the pivot line.  no need to compare keys.
  562.     */
  563.    if (len < bc+1) {
  564.       if (sort.pivot_len < bc+1)
  565.          return( 0 );
  566.       else
  567.          return( sort.direction == ASCENDING ?  -1 : 1 );
  568.  
  569.    /*
  570.     * is the pivot line length less than beginning column?  if so, just
  571.     *  look at the length of the current line.  no need to compare keys.
  572.     */
  573.    } else if (sort.pivot_len < bc+1) {
  574.       if (len < bc+1)
  575.          return( 0 );
  576.       else
  577.          return( sort.direction == ASCENDING ?  1 : -1 );
  578.    } else {
  579.  
  580.       /*
  581.        * if lines are of equal length or greater than the ending column,
  582.        *  then lets consider them equal.
  583.        */
  584.       if (len == sort.pivot_len)
  585.          left_over = 0;
  586.       else if (len >= sort.ec  &&  sort.pivot_len >= sort.ec)
  587.          left_over = 0;
  588.       else {
  589.  
  590.          /*
  591.           * if one line does not extend thru the ending column, give
  592.           *  preference to the longest key.
  593.           */
  594.          if (sort.direction == ASCENDING)
  595.             left_over =  len > sort.pivot_len ? 1 : -1;
  596.          else
  597.             left_over =  len > sort.pivot_len ? -1 : 1;
  598.       }
  599.  
  600.       /*
  601.        * only need to compare up to length of the key in the pivot line.
  602.        */
  603.       if (len > sort.pivot_len)
  604.          len = sort.pivot_len;
  605.       len = len - bc;
  606.       if (len > sort.block_len)
  607.          len = sort.block_len;
  608.  
  609.       assert( len > 0 );
  610.  
  611.       if (sort.direction == ASCENDING)
  612.          rc = my_memcmp( node->line + bc, sort.pivot_ptr + bc, len );
  613.       else
  614.          rc = my_memcmp( sort.pivot_ptr + bc, node->line + bc, len );
  615.  
  616.       /*
  617.        * if keys are equal, let's see if one key is longer than the other.
  618.        */
  619.       if (rc == 0)
  620.          rc = left_over;
  621.       return( rc );
  622.    }
  623. }
  624.  
  625.  
  626. /*
  627.  * Name:    my_memcmp
  628.  * Purpose: compare strings using ignore or match case sort order
  629.  * Date:    October 31, 1992
  630.  * Passed:  s1:  pointer to string 1
  631.  *          s2:  pointer to string 2
  632.  *          len: number of characters to compare
  633.  * Notes:   let's do our own memcmp, so we can sort languages that use
  634.  *           extended characters as part of their alphabet.
  635.  */
  636. int  my_memcmp( text_ptr s1, text_ptr s2, int len )
  637. {
  638. unsigned char *p;
  639. register int c;
  640.  
  641.    assert( len >= 0 );
  642.    assert( len < MAX_LINE_LENGTH );
  643.    assert( s1 != NULL );
  644.    assert( s2 != NULL );
  645.  
  646.    if (len == 0)
  647.       return( 0 );
  648.  
  649.    p = sort.order_array;
  650.  
  651.    /*
  652.     * the C comparison function is equivalent to the assembly version;
  653.     *  however, once the assembly routine initializes, it is much faster
  654.     *  than the C version.
  655.     */
  656.    if (len < 10) {
  657.       for (;(c = (int)p[*s1] - (int)p[*s2]) == 0  &&  len > 0;
  658.                                               s1++, s2++, len--);
  659.       return( c );
  660.    } else {
  661.  
  662.       ASSEMBLE {
  663.  
  664.    /*
  665.    ; Register strategy:
  666.    ;   ax  == *s1
  667.    ;   dx  == *s2
  668.    ;   ds:[si]  == s1
  669.    ;   es:[bx]  == s2
  670.    ;   bp       == sort.order_array
  671.    ;   [bp+di]  == p[*s1]  or  p[*s2]
  672.    ;   cx       == len
  673.    ;
  674.    ;  CAVEAT:  sort.order_array is assumed to be located in the stack segment
  675.    */
  676.  
  677.         push    ds                      /* push required registers */
  678.         push    si
  679.         push    di
  680.         push    bp
  681.  
  682.         xor     ax, ax                  /* zero ax */
  683.         mov     cx, WORD PTR len        /* keep len in cx */
  684.         cmp     cx, 0                   /* len <= 0? */
  685.         jle     get_out                 /* yes, get out */
  686.  
  687.         mov     bx, WORD PTR s2         /* load our registers */
  688.         mov     ax, WORD PTR s2+2
  689.         mov     es, ax                  /* es:[bx] = s2 */
  690.         mov     si, WORD PTR s1
  691.         mov     ax, WORD PTR s1+2
  692.         mov     ds, ax                  /* ds:[si] = s1 */
  693.         mov     bp, p                   /* [bp] = p */
  694.         xor     ax, ax                  /* zero out ax */
  695.         xor     dx, dx                  /* zero out dx */
  696.       }
  697. top:
  698.  
  699.    ASSEMBLE {
  700.         mov     al, BYTE PTR ds:[si]    /* al == *s1 */
  701.         mov     di, ax
  702.         mov     al, BYTE PTR [bp+di]    /* al == p[*s1] */
  703.         mov     dl, BYTE PTR es:[bx]    /* dl == *s2 */
  704.         mov     di, dx
  705.         mov     dl, BYTE PTR [bp+di]    /* dl == p[*s2] */
  706.         sub     ax, dx                  /* ax == p[*s1] - p[*s2] */
  707.         jne     get_out
  708.         inc     bx
  709.         inc     si
  710.         dec     cx
  711.         cmp     cx, 0
  712.         jg      top                     /* ax keeps the return value */
  713.       }
  714. get_out:
  715.  
  716.    ASSEMBLE {
  717.         pop     bp                      /* pop the registers we pushed */
  718.         pop     di
  719.         pop     si
  720.         pop     ds                      /* ax keeps the return value */
  721.       }
  722.    }
  723. }
  724.