fix_psi_list_shuffle.ccs

// fix_psi_list_shuffle.ccs
// This ensures that the cursor in the PSI list always starts at the top-left-most entry.
// This is done using `sort_menu_entries` which performs a sort of the items in the current menu.
// We call this from the `generate_psi_list` function in the original code.

// This patch is public domain, "as-is" with no warranty
// See https://unlicense.org/
// Author: cooprocks123e, 2021-05-19

import asm65816

// Patch routine to jump to our new "sort_menu_entries" function
// via a springboard

ROM[0xC1C84B] = "[{short 0xC80E}]"
ROM[0xC1C7FD] = {
    // Make space for our new code by optimizing routine
    /* $c1c7fd */ CLC
    /* $c1c7fe */ ADC_i(0xF112)
    /* $c1c801 */ STA_d(0x0E)
    /* $c1c803 */ LDA_i(0x00C3)
    /* $c1c806 */ STA_d(0x10)
    /* $c1c808 */ STZ_d(0x12)
    /* $c1c80a */ STZ_d(0x14)
    /* $c1c80c */ BRA(0x10)              // Continue with rest of logic, skipping past the JSL

    // New code
    /* $c1c80e */ JSL(sort_menu_entries)
    /* $c1c812 */ JMP(0x163C)            // This is a tail-call optimization, when $163c does a RTS it will return to where we were called
    /* $c1c815 */ WDM WDM                // \
    /* $c1c817 */ WDM WDM                //  | In case this gets executed somehow, break into debugger
    /* $c1c819 */ WDM WDM WDM            //  | with a WDM instruction
    /* $c1c81c */ WDM WDM                // /
}

// Defines for the sort_menu_entries code:
define CURRENT_FOCUS_WINDOW   = 0x7E8958
define WINDOW_EXISTENCE_TABLE = 0x7E88E4
define WINDOW_STATS_TABLE     = 0x7E8650
define WINDOW_STATS_TABLE_ARG = 0x7E867B
define MULT168                = 0xC08FF7
define SIZEOF_89D4_ENTRY      = 0x2D
define SIZEOF_89D4_ENTRY_M6   = 0x27

sort_menu_entries:
    REP(0x31) // Set A = 16bit, X = 16bit, Carry = 0
    PHD
    TDC
    ADC_i(0xFFF8) // Add 8 bytes to our stack, for local variables
    TCD

    LDA_a(CURRENT_FOCUS_WINDOW)
    CMP_i(-1)
    BEQ_a(return)
got_window:
    ASL
    TAX
    LDA_x(WINDOW_EXISTENCE_TABLE)
    LDY_i(0x0052)
    JSL(MULT168)
    TAY
    LDA_y(WINDOW_STATS_TABLE_ARG) // argument_memory_storage of the window
    STA_d(0x00) // Store 89D4 index in $00 during function call

    JSL(0xC10C49) // Call function to find the length of the menu
    // A will be the number of items in the menu, or 0 if the index is invalid
    // We want to find the number of swaps we need to do, which is num_items - 1
    DEC
    // Return if we shouldn't do anything (function returned 0 or num_items == 1)
    // Since num_items will be from 0 to 70, we know A can only be -'ve if
    //   the function returned 0.
    // Equivalent pseudo-code:
    //   int num_swaps = fn_C1138D(start_index) - 1;
    //   if (num_swaps <= 0) return -1;
    BNE(6)
    LDA_i(0xffff)
    JMP(return)
    BMI(-8)
    STA_d(0x02)
    
    // Calculate address of our first entry in $89d4
    LDA_d(0x00) // Get previously stored index
    LDY_i(SIZEOF_89D4_ENTRY)
    JSL(MULT168)
    CLC
    ADC_i(0x89D4)
    STA_d(0x04)

    // This code implements a selection sort on the items of the current menu.
    // In the inner loop, we iterate through the items and find the one
    //   with the lowest coordinates (lowest Y, and if Y's are equal, lowest X).
    // In the outer loop, we swap the item at ($04) with the lowest item, and then
    //   point $04 to the next item in the list.
    // $00 is used as a temporary variable during the swapping
    // $02 is used as an outer loop counter
    // $04 is a pointer to the list item we will be swapping after the inner loop
    // $06 is used as an inner loop counter
    // See the end of this file for C pseudocode
    LDX_d(0x04)
    TXA
selsort_outer:
    LDY_d(0x02)
    STY_d(0x06)
selsort_inner:
    // Vars: $04 = swap_destination, X = swap_current_lowest, A = swap_candidate
    // swap_candidate += 1;
    CLC
    ADC_i(SIZEOF_89D4_ENTRY)
    TAY
    // start compare
        LDA_x(10)
        CMP_y(10)
        BNE(6)    // compare_y_differ
        LDA_x(8)
        CMP_y(8)
    compare_y_differ:
    // end compare
    BCC(1)        // selsort_inner_noupdate
    TYX
selsort_inner_noupdate:
    TYA
    DEC_d(0x06)
    BNE(0xE5)     // selsort_inner

    CPX_d(0x04)
    BEQ_a(selsort_outer_no_swap)
    LDY_d(0x04)

    // start swapping
        SEP(0x20)
        LDA_8(SIZEOF_89D4_ENTRY_M6)
        STA_d(0x00)
    swap_loop:
        LDA_x(0x0006)
        XBA
        LDA_y(0x0006)
        STA_x(0x0006)
        XBA
        STA_y(0x0006)
        INX
        INY
        DEC_d(0x00)
        BNE(0xEC) // swap_loop
        REP(0x20)
    // end swapping
selsort_outer_no_swap:
    // swap_destination += 1;
    LDA_d(0x04)
    CLC
    ADC_i(SIZEOF_89D4_ENTRY)
    STA_d(0x04)
    // swap_current_lowest = swap_destination;
    TAX
    // } while(--outer_count > 0);
    DEC_d(0x02)
    BNE_a(selsort_outer)
selsort_done:
    LDA_i(0x0000)
return:
    PLD
    RTL

/* Pseudocode for the selection sort:
    void selection_sort(struct_u89D4 *base, int length) {
        int outer_count = length - 1;
        struct_u89D4 *swap_destination = base;
        struct_u89D4 *swap_current_lowest = base;
        do {
            struct_u89D4 *swap_candidate = swap_destination;

            int inner_count = outer_count;
            do {
                swap_candidate += 1;
                if (b_lessthan_a(swap_current_lowest,swap_candidate)) {
                    swap_current_lowest = swap_candidate;
                }
            } while(--inner_count > 0);

            if (swap_destination != swap_current_lowest) {
                swap(swap_destination, swap_current_lowest);
            }

            swap_destination += 1;
            swap_current_lowest = swap_destination;
        } while(--outer_count > 0);
    }
*/