API tools faq
paste
Advertisement
Guest User

MergeSort para ARM

a guest
Oct 21st, 2019
283
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
ASM (NASM) 12.33 KB | None | 0 0
raw download clone embed print report
  1. /*
  2.  * main.s
  3.  *
  4.  * Programa en esnsamblador ARM para Raspberry Pi
  5.  * Genera 1024 bytes aleatorios
  6.  * Y posteriormente los ordena con el algoritmo Merge Sort
  7.  *
  8.  *
  9.  *  Creado          : 18 octubre 2019
  10.  *  Autor           : tranki
  11.  *  Licencia        : haced lo que os de la gana con este código
  12.  *  Responsabilidad : ninguna
  13.  */
  14.  
  15. /*  Funciones globales */
  16. .global main, rand, printArray, mergeSort, merge
  17.  
  18. /* Funciones externas */
  19. .global printf, putchar
  20.  
  21. /* Constantes */
  22. .equ ARRAY_LEN, 1024
  23.  
  24. /* Area de datos */
  25. .data
  26.  
  27. .balign 4
  28. mensaje: .asciz "Esto es la ostia \n"
  29.  
  30. .balign 4
  31. mascara: .asciz "%3d "
  32.  
  33. /* array de 1024 bytes para almacenar los números aleatorios */
  34. .balign 4
  35. array: .skip (ARRAY_LEN * 4)
  36.  
  37. .balign 4
  38. auxarr: .skip (ARRAY_LEN * 4)
  39.  
  40. .balign 4
  41. index:  .word 0
  42.  
  43. /* area de código */
  44. .text
  45.  
  46. /*
  47. -------------------------------------------------------------
  48.  *  Función main
  49.  *  Entrada principal del programa
  50.  -------------------------------------------------------------
  51. */
  52. main:
  53.     push {lr}
  54.  
  55.     ldr r1, =array          /* dirección del array */
  56.     mov r2, #0              /* R2 como contador */
  57. /*
  58. * Aquí generamos los 1024 enteros aleatorios
  59. * y los almacenamos en el bloque "array"
  60. */
  61. carga:
  62.     cmp r2, #ARRAY_LEN      /* ¿tenemos los 1024 bytes? */
  63.     beq fincarga            /* si, salimos del bucle */
  64.     bl rand                 /* extraemos un número aleatorio en R0 */
  65.     add r3, r1, r2, LSL #2  /* Actualizamos el índice R3 = R1 + (R2*4) */
  66.     str r0, [r3]            /* almacenamos el número en el array *R3 ← R0 */
  67.     add r2, r2, #1          /* R2 = R2 + 1 */
  68.     b carga                 /* cerramos el bucle */
  69.  
  70. fincarga:
  71.     bl printArray           /* muestra el array aleatorio por consola */
  72.  
  73.     ldr r0, =array
  74.     mov r1, #0
  75.     mov r2, #ARRAY_LEN
  76.     sub r2, r2, #1
  77.     bl mergeSort            /* ordena el array */
  78.  
  79.     mov r0, #0x0A           /* añadimos un retorno de carro */
  80.     bl putchar              /* con la función putchar */
  81.     bl putchar              /* con la función putchar otra vez*/
  82.  
  83.     bl printArray           /* muestra el array ordenado por consola */
  84.     mov r0, #0x0A           /* añadimos un retorno de carro */
  85.     bl putchar              /* con la función putchar */
  86.  
  87.     ldr r0, =mensaje
  88.     bl printf
  89.  
  90.     mov r0, #0
  91.  
  92.     pop {lr}
  93.     bx lr                   /* Return de main */
  94.  
  95. /*
  96. -------------------------------------------------------------
  97. * Función mergeSort
  98. * Ordena un array de enteros
  99. * Valores de entrada:
  100. *   r0 = dirección del array
  101. *   r1 = índice de inicio de los datos en el array = p
  102. *   r2 = longitud de los datos = r
  103. * retorna: nada
  104. -------------------------------------------------------------
  105. */
  106. mergeSort:
  107.     push {lr}
  108.  
  109.     cmp r1, r2          /* (p < r) ? */
  110.     blt sigueMerge
  111.     b outMerge
  112.  
  113. sigueMerge:
  114.     add r3, r1, r2      /* q = p + r */
  115.     asr r3, r3, #1      /* q = q / 2 */
  116.  
  117.     push {r0, r1, r2, r3}   //mergeSort(a, p, q);
  118.     ldr r0, =array          /* dirección array */
  119.     mov r2, r3
  120.     bl mergeSort            /* llamada recursiva */
  121.     pop {r0, r1, r2, r3}
  122.  
  123.     add r4, r3, #1          /* q + 1 */
  124.     push {r0, r1, r2, r3}
  125.     ldr r0, =array          /* dirección array */
  126.     mov r1, r4              /* mergeSort(a, q+1, r) */
  127.     bl mergeSort            /* llamada recursiva */
  128.     pop {r0, r1, r2, r3}
  129.  
  130.     ldr r0, =array          /* dirección array */
  131.     push {r0, r1, r2, r3}
  132.     mov r4, r2              /* R4 = r */
  133.     mov r5, r3              /* R5 = q */
  134.     mov r2, r5              /* R2 = q */
  135.     mov r3, r4              /* R3 = r */
  136.                             /* R1 = p, R2 = q * R3= r */
  137.     bl merge                /* merge(a, p, q, r) */
  138.     pop {r0, r1, r2, r3}
  139.  
  140. outMerge:
  141.     pop {lr}
  142.     bx lr                   /* Return de mergeSort */
  143.  
  144. /*
  145. -------------------------------------------------------------
  146. * Función merge
  147. * Ordena un array de enteros
  148. * Valores de entrada:
  149. *   r0 = dirección del array
  150. *   r1 = índice de inicio de los datos mitad izquierda p
  151. *   r2 = índice de inicio de los datos mitad derecha q
  152. *   r3 = longitud de los datos r
  153. * retorna: nada
  154. -------------------------------------------------------------
  155. */
  156. .data
  157. .balign 4
  158. i: .word 0
  159.  
  160. .balign 4
  161. j: .word 0
  162.  
  163. .balign 4
  164. k: .word 0
  165.  
  166. .balign 4
  167. p: .word 0
  168.  
  169. .balign 4
  170. q: .word 0
  171.  
  172. .balign 4
  173. r: .word 0
  174.  
  175. .text
  176.  
  177. merge:
  178.     push {lr}
  179.  
  180.     ldr r4, =p              /* *R4 variable p */
  181.     str r1, [r4]            /* variable p guardada */
  182.     ldr r4, =q              /* *R4 variable q */
  183.     str r2, [r4]            /* variable q guardada */
  184.     ldr r4, =r              /* *R4 variable r */
  185.     str r3, [r4]            /* variable r guardada */
  186.  
  187.     ldr r4, =i              /* *R4 variable i */
  188.     ldr r5, =j              /* *R5 variable j */
  189.     ldr r6, =k              /* *R6 variable k arrayAux[k-p]*/
  190.  
  191.     str r1, [r4]            /* i = p */
  192.     add r2, r2, #1          /* q = q + 1*/
  193.     str r2, [r5]            /* j = q + 1 */
  194.  
  195.     mov r1, #0
  196.     str r1, [r6]            /* k = 0 */
  197.  
  198. loopM1:
  199.     ldr r4, =q              /* *R4 variable q */
  200.     ldr r1, [r4]            /* carga q */
  201.     ldr r4, =i              /* *R4 variable i */
  202.     ldr r2, [r4]            /* carga i */
  203.     cmp r2, r1              /* compara i <= q */
  204.     bgt outloopM1           /* sale si i > q */
  205.  
  206.     ldr r4, =r              /* *R4 variable r */
  207.     ldr r1, [r4]            /* carga r */
  208.     ldr r4, =j              /* *R4 variable j */
  209.     ldr r2, [r4]            /* carga j */
  210.     cmp r2, r1              /* compara j <= r */
  211.     bgt outloopM1           /* sale si j > r */
  212.  
  213.     ldr r4, =i              /* *R4 variable i */
  214.     ldr r1, [r4]            /* carga i */
  215.  
  216.     ldr r0, =array          /* dirección array */
  217.     add r3, r0, r1, LSL #2  /* índice al array[i] en R3 */
  218.     ldr r1, [r3]            /* valor del array en [i] */
  219.     add r3, r0, r2, LSL #2  /* índice al array[j] en R3 */
  220.     ldr r2, [r3]            /* valor del array en [J] */
  221.  
  222.     cmp r1, r2              /* ¿array[i] < array[j]? */
  223.     blt maspeq              /* si, salta a mas pequeño */
  224.  
  225.     ldr r2, =k              /* *R2 variable k */
  226.     ldr r2, [r2]            /* R2 = k */
  227.     ldr r1, =j
  228.     ldr r1, [r1]
  229.     ldr r0, =array
  230.     add r3, r0, r1, LSL #2      /* índice al array[j] en R3 */
  231.     ldr r1, [r3]
  232.     ldr r0, =auxarr             /* dirección array auxiliar */
  233.     add r3, r0, r2, LSL #2      /* índice al arrayAux[k] en R3 */
  234.     str r1, [r3]                /* arrayAux[k] = array[j] */
  235.    
  236.     ldr r1, =j              /* *R1 variable j */
  237.     ldr r2, [r1]            /* cargamos variable j */
  238.     add r2, r2, #1          /* j = j + 1 */
  239.     str r2, [r1]            /* guardamos variable j */
  240.     b outIf1
  241.  
  242. maspeq:
  243.     ldr r2, =k              /* *R2 variable k */
  244.     ldr r2, [r2]            /* R2 = k */
  245.     ldr r1, =i
  246.     ldr r1, [r1]
  247.     ldr r0, =array
  248.     add r3, r0, r1, LSL #2      /* índice al array[i] en R3 */
  249.     ldr r1,[r3]
  250.  
  251.     ldr r0, =auxarr         /* dirección array auxiliar */
  252.     add r3, r0, r2, LSL #2  /* índice al arrayAux[k] en R3 */
  253.     str r1,[r3]
  254.  
  255.     ldr r1, =i              /* *R1 variable i */
  256.     ldr r2, [r1]            /* cargamos variable  */
  257.     add r2, r2, #1          /* i = i + 1 */
  258.     str r2, [r1]            /* guardamos variable i */
  259.  
  260. outIf1:
  261.     ldr r1, =k              /* *R1 variable k */
  262.     ldr r2, [r1]            /* cargamos variable k */
  263.     add r2, r2, #1          /* k = k + 1 */
  264.     str r2, [r1]            /* guardamos variable k */
  265.     b loopM1
  266.  
  267. outloopM1:
  268.     ldr r1, =q              /* *R1 variable q */
  269.     ldr r2, =i              /* *R2 variable i */
  270.     ldr r1, [r1]            /* R1 variable q */
  271.     ldr r2, [r2]            /* R2 variable i */
  272.  
  273.     cmp r2, r1
  274.     bgt outloopM2
  275.     ldr r1, =k              /* *R1 variable k */
  276.     ldr r1, [r1]            /* R1 variable k */
  277.     ldr r2, =i              /* *R2 variable i */
  278.     ldr r2, [r2]            /* R2 variable i */
  279.  
  280.     ldr r0, =array          /* dirección array */
  281.     add r3, r0, r2, LSL #2  /* índice al array[i] en R3 */
  282.     ldr r2, [r3]            /* cargamos valor en array[i] */
  283.  
  284.     ldr r0, =auxarr         /* dirección array auxiliar */
  285.     add r3, r0, r1, LSL #2  /* índice al arrayAux[k] en R3 */
  286.     str r2, [r3]            /* arrayAux[k] = array[i] */
  287.  
  288.     ldr r1, =i              /* *R1 variable i */
  289.     ldr r2, [r1]            /* cargamos vararrayAux[k-p]iable i */
  290.     add r2, r2, #1          /* i = i + 1 */
  291.     str r2, [r1]            /* guardamos variable i */
  292.  
  293.     ldr r1, =k              /* *R1 variable k */
  294.     ldr r2, [r1]            /* cargamos variable k */
  295.     add r2, r2, #1          /* k = k + 1 */
  296.     str r2, [r1]            /* guardamos variable k */
  297.     b outloopM1
  298.  
  299. outloopM2:
  300.     ldr r1, =r              /* *R1 variable r */
  301.     ldr r2, =j              /* *R2 variable j */
  302.     ldr r1, [r1]            /* R1 variable r */
  303.     ldr r2, [r2]            /* R2 variable j */
  304.     cmp r2, r1              /* compara j <= r */
  305.     bgt outloopM3
  306.  
  307.     ldr r1, =k              /* *R1 variable k */
  308.     ldr r1, [r1]            /* R1 variable k */
  309.     ldr r2, =j              /* *R2 variable j */
  310.     ldr r2, [r2]            /* R2 variable j */
  311.  
  312.     ldr r0, =array          /* dirección array */
  313.     add r3, r0, r2, LSL #2  /* índice al array[j] en R3 */
  314.     ldr r2, [r3]            /* cargamos valor en array[j] */
  315.  
  316.     ldr r0, =auxarr         /* dirección array auxiliar */
  317.     add r3, r0, r1, LSL #2  /* índice al arrayAux[k] en R3 */
  318.     str r2, [r3]            /* arrayAux[k] = array[j] */
  319.  
  320.     ldr r1, =j              /* *R1 variable j */
  321.     ldr r2, [r1]            /* cargamos variable j */
  322.     add r2, r2, #1          /* j = j + 1 */
  323.     str r2, [r1]            /* guardamos variable j */
  324.  
  325.     ldr r1, =k              /* *R1 variable k */
  326.     ldr r2, [r1]            /* cargamos variable k */
  327.     add r2, r2, #1          /* k = k + 1 */
  328.     str r2, [r1]            /* guardamos variable k */
  329.     b outloopM2
  330.  
  331. outloopM3:
  332.     ldr r1, =p              /* *R1 variable p */
  333.     ldr r1, [r1]            /* R1 variable p */
  334.     ldr r2, =k              /* *R2 variable k */
  335.     str r1, [r2]            /* k = p */
  336.  
  337. for1:
  338.     ldr r2, =k              /* *R2 variable k */
  339.     ldr r2, [r2]            /* R2 variable k */
  340.     ldr r1, =r              /* *R1 variable r */
  341.     ldr r1, [r1]            /* R1 variable r */
  342.  
  343.     cmp r2, r1              /* ¿ k<=r ? */
  344.     bgt outFor1             /* k > r, sale */
  345.  
  346.     ldr r1, =p              /* *R1 variable p */
  347.     ldr r1, [r1]            /* R1 variable p */
  348.     sub r1, r2, r1          /* R1 indice k - p */
  349.  
  350.     ldr r0, =auxarr         /* dirección array auxiliar */
  351.     add r3, r0, r1, LSL #2  /* índice al arrayAux[k-p] en R3 */
  352.     ldr r1, [r3]            /* carga valor arrayAux[k-p] en R1 */
  353.  
  354.     ldr r0, =array          /* dirección array */
  355.     add r3, r0, r2, LSL #2  /* índice al array[k] en R3 */
  356.     str r1, [r3]            /* array[k] = arrayAux[k-p] */
  357.  
  358.     add r2, r2, #1          /* k = k + 1 */
  359.     ldr r1, =k              /* *R2 variable k */
  360.     str r2, [r1]
  361.     b for1
  362.  
  363. outFor1:
  364.     pop {lr}
  365.     bx lr                   /* Return de merge */
  366.  
  367. /*
  368. -------------------------------------------------------------
  369.  *  Función printArray
  370.  *  Muestra por la terminal el array de enteros
  371.  -------------------------------------------------------------
  372. */
  373. printArray:
  374.     push   {r1, r2, r4, r5, r7, lr} /* Procedimiento de llamada estándar para la arquitectura ARM */
  375.  
  376.     ldr r4, =array          /* dirección del array */
  377.     mov r5, #0              /* R5 como contador */
  378.     mov r6, #0              /* R6 números por linea */
  379.  
  380. escribe:
  381.     cmp r5, #ARRAY_LEN      /* ¿tenemos los 1024 bytes? */
  382.     beq finprint            /* si, salimos del bucle */
  383.     add r3, r4, r5, LSL #2  /* actualizamos el índice, entonces R3 = R1 + (R2*4) */
  384.     ldr r1, [r3]            /* carga el valor del array en R1 apuntado por *R3 */
  385.     ldr r0, =mascara        /* r0 ← &mascara */
  386.     bl printf               /* llamada a printf, escribe el número*/
  387.     add r5, r5, #1          /* R5 = R5 + 1 */
  388.     add r6, r6, #1          /* R6 = R6 + 1 */
  389.     cmp r6, #16             /* ¿16 números escritos? */
  390.     bne sigue               /* no, seguimos */
  391.     mov r6, #0              /* si, ponemos el contador a 0 R&=0 */
  392.     mov r0, #0x0A           /* añadimos un retorno de carro */
  393.     bl putchar              /* con la función putchar */
  394.  
  395.  sigue:
  396.     b escribe
  397.  
  398.  finprint:
  399.     pop    {r1, r2, r4, r5, r7, lr} /* recupera la llamada estándard */
  400.     bx     lr                       /* retorno de subrutina */
  401.     b fincarga              /* borrar */
  402. /*
  403. -------------------------------------------------------------
  404.  *  Función rand
  405.  *  Lee un número aleatorio del archivo /dev/urandom
  406.  *  Devuelve el número en R0
  407.  -------------------------------------------------------------
  408. */
  409.  
  410. .data
  411.  
  412.     /* Modos de lectura / escritura para el archivo */
  413.  
  414.     .equ open,      5       /* Abrir archivo */
  415.     .equ RdWr,      02      /* Acceso lectura escrtura */
  416.     .equ Apnd,      02000   /* Abrir archivo */
  417.     .equ read,      3       /* Leer archivo */
  418.     .equ close,     6       /* Cerrar archivo */
  419.  
  420. .balign 4
  421. dir_file: .asciz "/dev/urandom"
  422.  
  423. .balign 4
  424. Open: .word dir_file, RdWr | Apnd, open
  425.  
  426. .balign 4
  427. Buf: .word 0
  428.  
  429. .balign 4
  430. Read: .word Buf, 1, read
  431.  
  432. /*
  433. *  Empieza área de código
  434. */
  435. .text
  436.  
  437. rand:
  438.     push   {r1, r2, r4, r5, r7, lr} /* Procedimiento de llamada estándar para la arquitectura ARM */
  439.  
  440.     ldr    r3, =Open                /* dirección de Open */
  441.     ldm    r3, {r0, r1, r7}         /* carga los registros */
  442.     svc    #0                       /* el SO abre el archivo */
  443.     mov    r4, r0                   /* el número de archivo se almacena en R4 (fd) */
  444.  
  445.     ldr    r3, =Read                /* dirección de Read */
  446.     ldm    r3, {r1, r2, r7}         /* carga los registros */
  447.     svc    #0                       /* el SO lee el archivo */
  448.  
  449.     mov    r0, r4                   /* carga el fd en R0 */
  450.     mov    r7, #close               /* núm. para cerrar */
  451.     svc    #0                       /* el SO cierra el archivo */
  452.  
  453.     ldr    r0, =Buf                 /* dirección del dato leído */
  454.     ldr    r0, [r0]                 /* carga el valor en R0 */
  455.  
  456.     pop    {r1, r2, r4, r5, r7, lr} /* recupera la llamada estándard */
  457.     bx     lr                       /* retorno de subrutina */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!