// PŘIPRAVA TESTOVACǏHO VSTUPU // Pole [60, 30, 80, 10, 40, 20, 70, 50] // Oproti zadání jsme změnili vstupní adresu na 0x100000, aby // se kód dal spustit v~našem simulátoru. MOV r0, #0x100000 MOV r1, #8 // velikost pole STR r1, [r0], #4 MOV r1, #60 STR r1, [r0], #4 MOV r1, #30 STR r1, [r0], #4 MOV r1, #80 STR r1, [r0], #4 MOV r1, #10 STR r1, [r0], #4 MOV r1, #40 STR r1, [r0], #4 MOV r1, #20 STR r1, [r0], #4 MOV r1, #70 STR r1, [r0], #4 MOV r1, #50 STR r1, [r0], #4 // SAMOTNÉ TŘÍDĚNÍ trideni: MOV r0, #4 // velikost slučovaných bloků (v bajtech) MOV r10, #0x100000 LDR r9, [r10] // načti délku pole MOV r9, r9, lsl #2 // r9 = r9 * 4 (délka v bajtech) ADD r10, #4 MOV r11, #0x8000000 // pomocná paměť faze: MOV r1, r10 // Ukazatel na začátek a konec prvního bloku výstupu MOV r5, r11 blok: MOV r2, r1 // r2 = r1 + r0 ADD r2, r0 MOV r3, r2 // r3 = r2 + r0 MOV r4, r2 // r4 = r2 + 2*r0 ADD r4, r0 MOV r6, r5 // r6 = r5 + 2*r0 ADD r6, r0, lsl #1 prvek: // přidej jeden prvek do výstupního bloku // Pokud jsme v některém seznamu na konci... CMP r1, r2 BHS doberpravy CMP r3, r4 BHS doberlevy LDR r7, [r1] LDR r8, [r3] CMP r7, r8 // Pokud akt. prvek z levého bloku je menší, // přidáme ho na výstup a posuneme levý pointer STRLE r7, [r5], #4 ADDLE r1, #4 // Analogicky pro pravý STRGT r8, [r5], #4 ADDGT r3, #4 B prvek // pravý blok vyprázdněn, v levém něco zbylo doberlevy: CMP r1, r2 BHS konecmerge LDR r7, [r1], #4 STR r7, [r5], #4 B doberlevy // levý blok vyprázdněn, v pravém něco zbylo doberpravy: CMP r3, r4 BHS konecmerge LDR r8, [r3], #4 STR r8, [r5], #4 B doberpravy konecmerge: // dokončili jsme merge dvou bloků // Začátky následujících bloků jsou konce aktuálních MOV r1, r4 // Ověříme, jestli nejsme za koncem pole MOV r7, r10 // začátek pole ADD r7, r9 // + délka -> konec pole CMP r1, r7 BLO blok // pokračujeme slitím dalších 2 bloků konecfaze: // Prohodíme zdrojové a cílové pole (r10<->r11) MOV r7, r10 MOV r10, r11 MOV r11, r7 MOV r0, r0, lsl #1 // zdvojnásobí velikost bloku // Odkomentovat pro vypsání mezivýsledku po nějaké fázi // (v tomto případě když máme setříděné bloky velikosti 4) // CMP r0, #4 // BEQ vypis CMP r0, r9 BLO faze // ZOBRAZENÍ VÝSTUPU // načteme výsledné pole do registrů, které nám // simulátor zobrazí vypis: LDR r0, [r10], #4 LDR r1, [r10], #4 LDR r2, [r10], #4 LDR r3, [r10], #4 LDR r4, [r10], #4 LDR r5, [r10], #4 LDR r6, [r10], #4 LDR r7, [r10], #4 // V r0-r7 budou setřídění prvky