La empresa VideoStream S.A. diseña un programa en ensamblador que procesa secuencias de bytes. Dichas secuencias almacenan una señal de vídeo, tienen una longitud variable y terminan siempre con un byte cuyo valor es 0 (los bytes de la secuencia son todos diferentes a cero).

La empresa quiere diseñar dos rutinas para detectar y reemplazar los lugares en una secuencia en los que aparecen cuatro bytes consecutivos con determinados valores numéricos. La siguiente figura muestra un ejemplo de una secuencia de bytes en la que se encuentra un patrón formado por los bytes consecutivos con valores v1, v2, v3 y v4.

Se pide escribir el código ensamblador para las siguientes rutinas:

• Rutina detectar: Recibe como parámetros la dirección de comienzo de la secuencia y los cuatro bytes del patrón a dectectar empaquetados en 32 bits depositados en ester orden en la pila y devuelve a través del registro %eax la dirección de memoria en la que se ha encontrado por primera vez el patrón dado. Si no se encuentra el patrón se devuelve el valor cero.

  Solución:

  La rutina avanza a través de la secuencia de byte en byte, pero puede realizar la comparación del patrón de una sola instrucción, puesto que se pueden comparar 4 bytes consecutivos con un valor en un registro. Se carga el en un registro el valor del patrón, y se avanza byte a byte comparando dicho registro con el contenido de memoria. Si la comparación tiene éxito se devuelve el %eax la dirección, y si se detecta el final de secuencia, se devuelve un cero.

  detectar:
  	push %ebp			# Terminar el bloque de activación 
  	mov %esp, %ebp
  
  	push %ebx			# Salvar Registros
  		
  	# 8(%ebp)  = patrón
  	# 12(%ebp) = dirección base de la secuencia
  
  	mov 12(%ebp), %eax		# %eax contiene la @ de los 4 bytes a procesar
  	mov 8(%ebp), %ebx		# %ebx contiene el patrón
  		
  dbucle:
          cmpb  $0, (%eax)               	# Comprobar si hay un cero en el primer byte
  	jz dfinal			# Si cero, final de secuencia. Terminar
  
  	cmp (%eax), %ebx		# Comparar 4 bytes con patrón
  	je drest			# Si son iguales terminar rutina
  
  	inc %eax			# Avanzar bucle
  	jmp dbucle
  			
  dfinal:	mov $0, %eax			# No se ha encontrado. Devolver cero
  	
  drest:	pop %ebx
  	pop %ebp			# Restaurar EBP 
  	ret
            

• Rutina reemplazar: Recibe como parámetros la dirección de comienzo de la secuencia y dos patrones de cuatro bytes deposidados por ese orden en la pila. La rutina debe recorrer la secuencia, detectar todas las ocurrencias del primer patrón depositado en la pila y reemplazarlo por el segundo. La rutina devuelve como resultado a través de la pila el número de veces que se ha reemplazado el patrón. Se debe utilizar la rutina del apartado anterior para detectar patrones.

  Solución:

  Esta rutina invoca sucesivamente la rutina detectar hasta que se obtiene la dirección de memoria igual a cero como resultado. Cada vez que se detecta un patrón, se reemplaza y se incrementa el resultado que a su vez se deposita en el espacio en la pila reservado para ello. La observación a tener en cuenta es que cuando se detecta un patrón, la siguiente búsqueda se puede realizar cuatro posiciones más que la búsqueda anterior, pues está garantizado que en el patrón no hay un byte de final de secuencia.

  reemplazar:
  	push %ebp			# Terminar el bloque de activación 
  	mov %esp, %ebp
  
  	push %eax			# Salvar registros
  	push %ebx
  	
  	# 8(%ebp)  = patrón a insertar
  	# 12(%ebp) = patrón a buscar
  	# 16(%ebp) = dirección base de la secuencia
  	# 20(%ebp) = resultado
  
  	mov 16(%ebp), %eax		# Dirección en la secuencia
  	mov 8(%ebp), %ebx		# Patrón a insertar
  	movl $0, 20(%ebp)		# Contador de apariciones
  	
  rbucle:
  	cmp $0, %eax			# Si %eax es cero se termina
  	je rrest
  
  	push %eax			# Llamar a detectar con dirección
  	push 12(%ebp)			# y patrón a detectar
  	call detectar
  	add $8, %esp			# Deshacer el bloque de activación
  
  	cmp $0, %eax			# Comparar resultado con cero
  	je rrest			# Si cero, final de secuencia. Terminar
  
  	mov %ebx, (%eax)		# Reemplazar patrón
  	incl 20(%ebp)			# Incrementar contador de aparaciones
  	add $4, %eax			# Avanzar 4 bytes en la secuencia
  	jmp rbucle			# Iterar de nuevo
  	
  rrest:	pop %ebx			# Restaurar Registros
  	pop %eax
  	
  	pop %ebp			# Restaurar EBP 
  	ret
            

Se require que el código esté perfectamente documentado. Una solución sin comentarios se considerará incorrecta. Se valorará la eficiencia en la ejecución de la solución propuesta.

En este ejercicio vamos a implementar una instrucción que haga lo siguiente: "Intercambia el contenido de la palabra de memoria cuya dirección es (CD), siendo CD un campo de la instrucción, con el contenido de la palabra de memoria cuya dirección es (CD) + 1". Al terminar de ejecutarse esta instrucción el contenido del acumulador debe de ser el mismo que el que había justo antes de empezar a ejecutarse la instrucción.

En este problema se considera que el formato de instrucciones es el mismo que en Símplez original y que la temporización de la Memoria Principal es idéntica a la de Símplez original.

Para implementar esta instrucción se propone utilizar 2 rutas de datos distintas, cuyo esquema se presenta en hojas adjuntas. A continuación se describen estas 2 rutas de datos.

La primera ruta de datos, que llamaremos SímplezSep04R1 se diferencia de la ruta de datos original de Símplez exclusivamente en lo siguiente:

• Aparecen 2 nuevos registros, ambos de 12 bits, llamados AUX1 y AUX2, sensibles al flanco de bajada. Estos registros no son registros de propósito general, sino que son registros de uso interno a la ruta de datos. Por lo tanto, podemos modificar libremente el dato guardado en ellos.

• La entrada de ambos registros se toma del bus D. El registro AUX1 dispone de una entrada de carga (microorden eaux1). Cuando esta microorden está activa, en el flanco de bajada del reloj se carga el dato a la entrada de AUX1 en el registro. Del mismo modo, el registro AUX2 dispone de una entrada de carga (microorden eaux2). Cuando esta microorden está activa, en el flanco de bajada del reloj se carga el dato a la entrada de AUX2 en el registro.

• La salida de ambos registros está conectada a un multiplexor, por medio del cual se selecciona de cual de los dos registros se toma la entrada 2 de la UAL. El multiplexor está controlado por la microorden rs. Cuando la microorden rs está activa, la salida del multiplexor se toma de AUX2, en caso contrario, la salida del multiplexor se toma de AUX1.

  Por lo tanto, no existe camino directo del bus de datos a la entrada 2 de la UAL.

• Aparece una nueva microorden, inra, que controla el registro RA. Cuando se activa esta microorden, en el flanco de subida del reloj, se incrementa el contenido de RA.

La segunda ruta de datos, que llamaremos SímplezSep04R2 se diferencia de la ruta de datos original de Símplez exclusivamente en lo siguiente:

• Aparecen 2 nuevos registros, ambos de 12 bits, llamados AUX1 y AUX2, sensibles al flanco de bajada. Estos registros no son registros de propósito general, sino que son registros de uso interno a la ruta de datos. Por lo tanto, podemos modificar libremente el dato guardado en ellos.

• La entrada del registro AUX1 se toma del bus D. El registro AUX1 dispone de una entrada de carga (microorden eaux1). Cuando esta microorden está activa, en el flanco de bajada del reloj se carga el dato a la entrada de AUX1 en el registro.

• La entrada del registro AUX2 se toma de la salida del registro AUX1. El registro AUX2 dispone de una entrada de carga (microorden eaux2). Cuando esta microorden está activa, en el flanco de bajada del reloj se carga el dato a la entrada de AUX2 en el registro.

• La salida del registro AUX2 está conectada a la entrada 2 de la UAL. Por lo tanto, no existe camino directo del bus de datos a la entrada 2 de la UAL.

• Aparece una nueva microorden, inra, que controla el registro RA. Cuando se activa esta microorden, en el flanco de subida del reloj, se incrementa el contenido de RA.

Se pide:

1. (8 puntos) Razone si en el caso de que la microorden inra incrementase el contenido de RA en el flanco de bajada del reloj, en vez de en el de subida, la instrucción pedida se podría ejecutar en el mismo número de ciclos de reloj, en menos o requeriría más ciclos de reloj (para ambas rutas de datos).

   Solución:

   Si la microorden inra incrementase el contenido de RA en el flanco de bajada, cuando se activase inra se incrementaría el contenido de RA al final del ciclo, por lo que en el siguiente ciclo de reloj no sería posible realizar un acceso a Memoria Principal, ya que la temporización de la Memoria Principal exige que la dirección a la que se va a acceder esté en RA un tiempo antes de realizar el acceso. Por lo tanto, en este supuesto se necesitaría un ciclo de reloj adicional.

2. (28 puntos) Para cada una de las rutas de datos propuestas escriba un cronograma que permita ejecutar la nueva instrucción que se ha descrito en este ejercicio. Para ello, escriba una tabla del estilo de la que se presenta a continuación, en la que se indica que microórdenes estarían activas en cada ciclo de reloj:

   Ciclo de reloj	Microórdenes
   1	lec, eri, incp
   2	...
   ...	...

   Nota: se penalizará, para cada ruta de datos, con 2 puntos cada acceso a Memoria Principal utilizado por encima del mínimo y con 1 punto cada ciclo de reloj por encima del mínimo.

   Solución:

   SímplezSep04R1

   Ciclo de reloj	Microórdenes
   1	lec, eri, incp
   2	sri, era, sac, eaux2
   3	lec, eaux1
   4	inra, tra2, eac
   5	lec, eaux1
   6	-
   7	sac, esc
   8	sac, sri, era, tra2, eac
   9	sac, esc
   10	sac, rs, tra2, eac, scp, era

   SímplezSep04R2

   Nota: Activar eaux1 y eaux2 simultáneamente en el mismo ciclo de reloj no lleva el dato disponible en ese momento en el bus de datos a AUX2 porque el retardo que se produce desde que se carga el dato en AUX1 hasta que ese dato está disponible a la salida de AUX1 más el retardo de propagación de la salida de AUX1 a la entrada de AUX2 es muy superior a la duración del flanco de bajada del reloj (teóricamente igual a 0, en la práctica de duración despreciable). Por el contrario, si se activan esas 2 microórdenes lo que ocurre es que el dato que había en AUX1 antes del flanco de bajada del reloj pasa a AUX2 y el dato en el bus de datos pasa a AUX1.

   Ciclo de reloj	Microórdenes
   1	lec, eri, incp
   2	sri, era
   3	lec, eaux1
   4	inra, eaux2
   5	lec, eaux1
   6	sac, eaux1, eaux2, tra2, eac
   7	sac, esc
   8	sac, sri, era, eaux2, tra2, eac
   9	sac, esc
   10	sac, tra2, eac, scp, era