Su tarea es escribir un programa en lenguaje de máquina x86 (cualquier versión que desee) que ejecutará tantas instrucciones como sea posible y luego se detendrá, utilizando un máximo de 32 bytes de código y comenzando con registros cerados.
Puede asumir cualquier cosa sobre la memoria de acceso aleatorio que desee, siempre que esté en un formato utilizable para la máquina x86.
Respuestas:
2 524224 instrucciones
Mi programa:
(Nota técnica: esto está escrito para nasm. Esta
a32
es la sintaxis de nasm para el byte alternativo de prefijo de tamaño de dirección. Para masm, debe reemplazar ela32
condefb 0x67
.)Para mayor claridad, aquí está el resultado de la lista:
El programa asume que el procesador está en modo real y que el programa está ubicado en la parte inferior de un segmento de memoria de 64k que, de lo contrario, se inicializa en todos los bits cero. Su diseño es simple: trate la memoria como un único entero gigante sin signo, e increméntelo a través de todos los valores posibles, hasta que vuelva a cero. Repita esto 2 32 veces. Entonces detente.
El bucle más interno (líneas 4‒6) es responsable de incrementar el número entero enorme. Cada iteración agrega cero o uno a un solo byte, dependiendo de si hubo una ejecución del byte anterior. Tenga en cuenta que se accede a cada byte en el gran número entero, ya sea que haya cambiado o no, por lo que este ciclo siempre itera 2 16 - 14 veces.
Por cierto, en caso de que te lo estés preguntando, este código ilustra la razón por la cual las instrucciones x86
inc
/dec
no afectan el indicador de acarreo: solo para simplificar este tipo de patrón de acarreo de varios bytes. (Este patrón surgió con mayor frecuencia en los días de los microprocesadores de 8 bits, cuando se definió el conjunto de instrucciones 8080 original).La línea 7 hace que el proceso de incremento se repita hasta que se realiza uno desde el último byte, lo que indica que el entero enorme se ha restablecido a todos los bits cero. Esto lleva mucho tiempo.
Las líneas 8‒9 marcan el bucle más externo y hacen que este proceso se repita 2 32 veces, hasta que el
ecx
registro rueda a cero. Esto es efectivamente equivalente a agregar otros 32 bits al entero gigante.Sería posible agregar otro ciclo externo y hacer esto nuevamente usando (digamos) el
edx
registro, y luego quizás usandoesi
yedi
para aún más repeticiones. Sin embargo, no vale la pena hacerlo. Las instrucciones para incrementar y recorrer requieren cuatro bytes. Esos cuatro bytes son quitados del entero gigante. Entonces perdemos 32 bits en el contador de RAM, solo para agregar 32 bits a través de un registro: termina siendo un lavado. La única razónecx
es una excepción es que tiene unaloop
instrucción especializada que se ajusta a solo tres bytes. Así, el programa intercambia 24 bits por 32, una ganancia pequeña pero aún positiva de 8 bits.No es demasiado difícil calcular directamente la cantidad de instrucciones que ejecuta el programa antes de detenerse. Sin embargo, hay una forma mucho más simple de estimar este número. El programa modifica toda su memoria, menos los 14 bytes que contienen el programa y los registros
bx
yecx
. Esto suma hasta 2 16 - 14 + 2 + 4 = 65528 bytes, para un total de 524224 bits. El acceso directo implica darse cuenta de que, en el proceso de ejecución, cada patrón posible de 524224 bits aparece exactamente una vez. Para la RAM y elecx
registro esto es fácil de ver, ya que el programa aumenta a través de cada valor individual. porbx
Esto es un poco menos obvio, ya que se está cambiando al mismo tiempo que se actualiza el valor en la memoria. Sin embargo, se puede demostrar que, dada la estructura del programa, si un patrón de bits completo apareciera realmente dos veces, entonces el programa tendría que estar en un bucle infinito. Como este no es el caso, cada patrón de bits debe ser visitado una sola vez. (La prueba completa se deja como ejercicio para el lector, naturalmente).Dado que todos los patrones de bits posibles aparecen en el curso del programa, el programa debe ejecutar al menos 2 524224 instrucciones, que es aproximadamente igual a 1.4 × 10 157807 . (El número acutal es muy levemente mayor debido a las instrucciones de salto, pero la diferencia a esta magnitud es insignificante).
Obviamente, esto podría mejorarse significativamente utilizando más de 64k de RAM. Espero la próxima versión del código hasta que averigüe exactamente cuánta RAM se puede acceder.
fuente
~ 2 ^ (2 ^ 67) instrucciones
(sintaxis de at & t)
Desmontado, 26 bytes:
Similar a la solución de breadbox, pero no hay razón para detenerse en 16 bits de dirección. Mi código usa x86-64 y supone que tenemos 2 ^ 64 bytes de memoria y usamos todo menos la memoria que contiene el código como un contador gigante.
fuente