orga2-simd/machete/machete.tex

\documentclass{article}
\usepackage{lmodern}
\usepackage[T1]{fontenc}
\usepackage{geometry}
\usepackage{array}
\usepackage{listings} 		% Para insertar codigo
\usepackage[usenames,dvipsnames]{color} % Colores custom
\newcolumntype{@}{>{\global\let\currentrowstyle\relax}}
\newcolumntype{^}{>{\currentrowstyle}}
\newcommand{\rowstyle}[1]{\gdef\currentrowstyle{#1}%
  #1\ignorespaces
}


% Configuración de parrafos
\setlength{\parskip}{1em}

% Margenes
 \geometry{
 a4paper,
 total={210mm,297mm},
 left=15mm,
 right=10mm,
 top=15mm,
 bottom=10mm,
 includehead, includefoot
 }

\textwidth=6in
\textheight=9.0in

\renewcommand{\lstlistingname}{C\'odigo}
\definecolor{DarkGreen}{rgb}{0.0,0.4,0.0} % Comentarios
% Lenguajes soportados: ftp://ftp.tex.ac.uk/tex-archive/macros/latex/contrib/listings/listings.pdf
\lstloadlanguages{[x86masm]Assembler, C} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Me robe lo de abajo de otro ejemplo, estaba basado en Perl, ver si hay que cambiar algo
\lstdefinestyle{asmStyle}{language=[x86masm]Assembler,
        frame=single,
        breaklines=true, 					% Saltar de linea si supero el maximo
        basicstyle=\small\ttfamily,
        keywordstyle=[1]\color{Blue}\bf,	% Color de las funciones de assembler
        keywordstyle=[2]\color{Purple},		% Color de parámetros especiales (registros, etc)
        identifierstyle=,                               
        commentstyle=\usefont{T1}{pcr}{m}{sl}\color{DarkGreen}\small,
        stringstyle=\color{Purple}, 		% Strings purpuras
        showstringspaces=false,
        tabsize=4,
        %
        % Instrucciones no incluidas en el paquete Assembler
        morekeywords={global, define, section, .rodata, .text, jl, movd, movdqu, mulss, subss, addss, cmpss, pand, cvtss2si, cvttss2si, cvtsi2ss, pxor, pslldq, movq, pshufb, paddb, pmaxub, punpcklbw, punpckhbw},
        %
        % Registros y esas otras cosas especiales que no son instrucciones
        morekeywords=[2]{rax,al,rdx,rcx,rbx,rsi,rdi,rsp,rbp,r8,r9,r10,r11,r12,r13,r14,r15,xmm0,xmm1,xmm2,xmm3,xmm4,xmm5,xmm6,xmm7
        		xmm8,xmm9,xmm10,xmm11,xmm12,xmm13,xmm14,xmm15,r8b, r9b, r10b, r11b, r8d, r9d, r10d, r11d},
        morecomment=[l][\color{Blue}]{...}, % Line continuation (...) like blue comment
        numbers=left,						% Numeros de linea en la izquiera
        firstnumber=1, 						% Se arranca en la linea 1
        numberstyle=\tiny\color{Blue}, 		% Numeros de linea en azul y chicos
        stepnumber=5, 						% Los numerros de linea se muestran cada 5
        numbers=left	                    % where to put the line-numbers; possible values are (none, left, right)
}


\begin{document}

\section{Saltos}
\textbf {JA} = Above/not below or equal | (CF or ZF) = 0 \\
\textbf {JAE} = Above or equal/not below | CF = 0 \\
\textbf {JE} = Equal/zero | ZF = 1 \\
\textbf {JZ} = Equal/zero | ZF = 1 \\
\textbf {JGE} = Greater or equal/not less | (SF xor OF) = 0 \\
\textbf {JG} = Greater/not less or equal | ((SF xor OF) or ZF) = 0 \\
\textbf {JO} = Overflow | OF = 1 \\
\textbf {JECXZ} = Register ECX is zero | ECX = 0 \\

\section{Registros} 
\begin{itemize}
\setlength\itemsep{1em}
\item \textbf{8 bits}: AL, BL, CL, DL, DIL, SIL, BPL, SPL, R8L, R9L, R10L, R11L, R12L, R13L, R14L, R15L \item \textbf{16 bits}: AX, BX, CX, DX, DI, SI, BP, SP, R8W, R9W, R10W, R11W, R12W, R13W, R14W, R15W
\item \textbf{32 bits}: EAX, EBX, ECX, EDX, EDI, ESI, EBP, ESP, R8D, R9D, R10D, R11D, R12D, R13D, R14D, R15D
\item \textbf{64 bits}: RAX, RBX, RCX, RDX, RSI, RDI, RPB, RSP, R8, R9, R10, R11, R12, R13, R14, R15
\item \textbf{128 bits}: XMM0-XMM15 
\end{itemize}

\section{Secciones y Etiquetas}
\subsection*{Secciones}
\textbf{.data}: Variables \\
\textbf{.rodata}: Constantes \\
\textbf{.text}: C\'odigo \\

%\subsection*{Etiquetas}
%\textbf{global}: Define un s\'imbolo que va a ser visto externamente \\
%\textbf{\_start}: Punto de entrada de un programa en linux \\
%\textbf{extern}: Llamar funci\'on externa  

%\subsection*{Pseudoinstrucciones}
%Prefijo \textbf{TIMES}, para repetir una cantidad de veces la instrucci\'on que sigue


\section*{Instrucciones}
\begin{tabular}[l]{ |@l|>{\itshape}^l|^p{10cm}| }
\hline
\rowstyle{\bfseries}
Instruccion & Formato & Descripcion \\
\hline
DB, DW, DD, DQ & -- & Definir datos \\ \hline
SHR & reg, imm & Hace un shift right l\'ogico (sin signo) \\ \hline
SAR & reg, imm & Hace un shift right aritm\'etico (con signo) \\ \hline
LEA & reg1, [ reg * imm + imm/reg ] & Evalua lo que hay entre corchetes y lo almacena en reg1 \\ \hline
MOVZX & reg, reg/mem & Copia y extiene con cero. Solo vale para (b->w, d->dw, w->dw) \\ \hline
CBW & reg, reg & Extiende w->dw o b->w. Extiende signo \\ \hline
MOV & (tam), mem/imm & Para el caso de inmediato o mem, especificar tam \\ \hline
CMP & (tam), mem/imm & Para el caso de inmediato o mem, especificar tam \\ \hline
MOVQ & xmm, reg & Muevo de registro a registro XMM \\ \hline
REP & instruccion & Repito RCX veces la instrucci\'on siguiente \\ \hline
CLD/STD & -- & Limpio(DF=0)/Seteo(DF=1) flag de direcci\'on \\ \hline
MOVSB/W/D/DQ & -- & Mueve el contenido de donde apunta RSI y lo almacena a donde apunta RDI, despues si DF=0 incrementa, sino decrementa segun tam. \\
CMPSB/W/D/DQ & -- & Compara el contenido de donde apunta RSI y donde apunta RDI. Modifica flags. Despues si DF=0 incrementa, sino decrementa. \\
\hline
\end{tabular}


\section{Convenci\'on C}
%\begin{itemize}
%\setlength\itemsep{1em}
%\item RBX, R12, R13, R14 y R15 \\
%\item Retornar el resultado RAX o XMM0 \\
%\item No romper la pila \\
%\item Antes de llamar, alinear la pila a 16 bytes \\
%\end{itemize}

\subsection*{Stack Frame}
\textbf{PUSH RBP} \\
\textbf{MOV RBP, RSP} \\
... \\ 
\textbf{SUB RSP, 8}; para alinear, variables locales \\
\textbf{SUB RSP, 16}; Para almacenar registros XMM \\
;sub rsp, 16 ;por ejemplo \\
;mov [rsp], xmm0 ; esto es equiv a "push xmm0" \\
\textbf{POP RBP} \\
\textbf{RET} \\
\emph{El \textbf{RSP} apunta al \'ultimo elemento pusheado. Hacer push decrementa el RSP en 8 y mueve el dato.}


\subsection*{Pasaje de parametros}
\begin{itemize}
\setlength\itemsep{1em}
\item Si es entero o puntero se pasan respetando el orden usando:
     \begin{itemize}
     \setlength\itemsep{1em}
     \item [$*$] RDI, RSI, RDX, RCX, R8 y R9
     \end{itemize}
\item Si es de tipo flotante se pasan en los XMMs
\end{itemize}

Si no hay m\'as registros disponibles de usa la pila, pero deber\'an quedar ordenados desde la direcci\'on m\'as baja a la m\'as alta (se pushean de derecha a izquierda)



\subsection*{Vectores}
\textit {"Puntero al inicio del arreglo"} + \textit {"tama\~no del dato"} * \textit {" \'indice del elemento"}

\subsection*{Matrices}
\textit {"Puntero al inicio de la matriz"}
+ \textit {"cantidad elementos de la fila"} * \textit {"indice de la fila"} * \textit {"tama\~no dato"} 
+ \textit {"indice de columna"} * \textit {"tama\~no dato"}

\subsection*{El formato general para direccionar es}
\begin{center}[ \textit{\textbf{Base}} + \textit{\textbf{Indice}} * \textit{\textbf{scala}} +/- \textit{\textbf{Desplazamiento}} ]\\
         \textbf{Base} = alg\'un registro\\
         \textbf{Indice} = alg\'un registro\\
         \textbf{scala} = 1, 2, 4 u 8\\
         \textbf{Desplazamiento} = inmediato de 32 bits\\
\end{center}         
         
\section{Alineaci\'on}
\begin{itemize}
\item \textbf{Alineaci\'on en los campos del struct}:
Cada campo esta alineado a su tama\~no dentro del struct
\item \textbf{Alineaci\'on del struct}:
Se alinea al tama\~no del campo mas grande del struct
\item\textbf{\_\_atribute\_\_((packed)}:
Indica que el struct no va a ser alineado
\end{itemize}

------------------------------------------ \\
\section{SSE}

%Para enteros:  Comienzan con P, luego el nombre de la \textit {"operaci\'on"} y terminan con el \textit {"tamaño"} del dato
%
%\textit {\textbf {Ejemplo}}
%\begin{itemize}
%\setlength\itemsep{1em}
%   \item \textbf {PADDB}: suma de a \textbf{B}yte
%   \item \textbf {PADDW}: suma de a \textbf{W}ord
%   \item \textbf {PADDD}: suma de a \textbf{D}oubleword
%   \item \textbf {PADDQ}: duma de a \textbf{Q}uadword
%\end{itemize}
   
%Para punto flotante: nombre de la \textit {"operaci\'on"}, \textit {"modo"} de operaci\'on y \textit {"tama\~no"} del dato \\

%\textit {\textbf {Ejemplo}}
%   \begin{itemize}
%   \setlength\itemsep{1em}
%   \item \textbf {ADDPS}: suma de a \textbf{F}loat
%   \item \textbf {ADDPD}: suma de a \textbf{D}ouble
%   \end{itemize}
%   
%La P proviene de Packed, podria ser S de Scalar
%   
%\subsection*{Multiplicar}
%\begin{itemize}
%\setlength\itemsep{1em}
%\item \textbf {PMULLW}: multiplica de a word y se queda con la parte baja
%\item \textbf {PMULHW}: multiplica de a word y se queda con la parte alta
%\end{itemize}
%
%\subsection*{Saturacion}
%\begin{itemize}
%\setlength\itemsep{1em}
%\item \textbf {PADDUSB, PSUBUSB}: Suma y resta de enteros byte sin signo con saturaci\'on sin signo
%\item \textbf {PADDSB, PSUBSB}: Suma y resta de enteros byte con signo con saturaci\'on con signo
%\end{itemize}
%
%\subsection*{Empaquetado/Desempaquetado}
%\begin{itemize}
%\setlength\itemsep{1em}
%\item Desempaquetado: PUNPCK \{L,H\} \{BW,WD,DQ,QDQ\}
%\item Empaquetado: PACK{SS,US}{WB,DW}\\
%                   SS, US: \textbf{S}igned/\textbf{u}nsigned, con \textbf{s}aturación
%\end{itemize}
%\textit{\textbf{Ejemplo}}\\
%Estos de aca abajo quiero poner con item, pero si no se puede bueno \\
%\textbf{PXOR} XMM7, XMM7 (este fijate si terminan los dos en 7 que por ahi me confundi por si las moscas) \\
%\textbf{MOVDQU} XMM1, XMM0 \\
%\textbf{PUNPCKLBW} XMM0, XMM7 \\
%\textbf{PUNPCKHBW} XMM1, XMM7 \\
%
%\subsection*{Desempaquetar}
%\begin{itemize}
%\setlength\itemsep{1em}
%\item \textbf{PUNPCKLWD}: usa la parte baja de los registros para juntarlos
%\item \textbf{PUNPCKHWD}: usa la parte alta de los registros para juntarlos
%\end{itemize}


\subsection*{Shuffles}
Las intrucciones de Shuffles permiten reordenar datos en registros. Sus par\'ametros ser\'an el registro a reordenar y una mascara que indicar\'a como hacerlo
\begin{itemize}
\item \textbf{PSHUF\{B,W,D\}}: Shuffle Packed Bytes, Words, Doublewords
\item \textbf{PSHUF\{H,L\}W}: Shuffle High, low 16bit values
\item \textbf{SHUFP\{S,D\}}: Shuffle Packed single, Double FP Values
\end{itemize}
\textbf{PSHUFHW} xmm1, xmm2/m128, imm8


\subsection*{Insert/Extract}
\begin{tabular}[l]{ |@l|>{\itshape}^l|^p{10cm}| }
\hline
\rowstyle{\bfseries}
Instruccion & Formato & Descripcion \\
\hline
INSERTPS &  xmm1, xmm2/m32, imm8 & Scalar Double FP to Dword Integer. Donde imm8 = (S,D,Z) donde S y D son combinaci\'on de 2 bits para decir: Src y Dst. Z = Zmask: 4 bits para decir que singles de Dst quedan con 0. \\ \hline
EXTRACTPS & reg/m32, xmm2, imm & Extract Packed Single FP Value. imm8=2bits. DST[31:0] <- (SRC[127:0] >> (SRC\_OFFSET*32)) AND 0FFFFFFFFh \\ \hline
PINSR\{B,W,D,Q\} & xmm1, r/m32, imm8 & Insert Byte, Word, Dword, Qword integer value from r32,64/m8,32,64 into xmm1 at the destination element in xmm1 specified by imm8 \\ \hline
PEXTR\{B,W,D,Q\ & r/m32, xmm2, imm8 & Extract Byte, Word, Dword, Qword integer value from xmm2 at the source byte, dword, qword, offset specified by imm8 into reg. The upper bits of reg are zeroed. \\ \hline
\end{tabular}


\section{Ejercicios}
\subsection{filtrarLista}
\begin{lstlisting}[frame=single, style=asmStyle]
%define NODO_SIZE	16 
%define OFFSET_SIGUIENTE 0 
%define OFFSET_NOMBRE 8
%define FALSE 0
%define TRUE 1

;void filtrarBajaLista( nodo** n, bool(*f)(char*,char*), char* nombreCmp )
filtrarBajaLista:
	mov r15, rdi			; R15 = nodo** n
	mov r14, rsi			; R14 = *f
	mov r13, rdx			; R13 = char* nombreCmp
	cmp r15, NULL			; por si el ** en NULL
	je .fin
	
.ciclo:
	mov rbx, [r15 + OFFSET_SIGUIENTE]	; R15 = **n; RBX = *n
	cmp rbx, NULL
	je .fin

	mov rdi, [rbx + OFFSET_NOMBRE]		; RDI = char* nombre
	mov rsi, r13						; RSI = char* nombreCmp
	call r14							; f( nombre, nombreCmp )
	cmp al, TRUE						; if(f(n->nombre, nombreCmp))
	je .siguiente

tengoQueBorrrar:
	mov rdi, rbx						; NODO A BORRAR
	mov rbx, [rbx + OFFSET_SIGUIENTE]	; reenlazo punteros
	mov [r15], rbx						; reenlazo punteros
	call nodoBorrar						; nodoBorrar( nodo *n )
	jmp .ciclo
.siguiente:
	mov r15, [r15 + OFFSET_SIGUIENTE]	; avanzo a siguiente
	jmp .ciclo
\end{lstlisting}

\subsection{SSE Matriz Negativo}
Aca lo importante es que al desempaquetar un negativo perdes el bit de signo si lo extendes con ceros. Lo tenes que extender con unos (pero solo para los elementos que sean negativos!)
\begin{lstlisting}[frame=single, style=asmStyle]
.ciclo:
	movdqu xmm0, [rdi]			; XMM0 = 16 chars
	;(!) pude acceder a 16 elementos de M de una vez...
	movdqu xmm1, xmm0			; XMM1 = XMM0 = 16 chars
	movdqu xmm5, xmm0			; XMM5 = XMM0 = 16 chars
	pxor xmm2, xmm2				; XMM2 = | 0x00 | 0x00 | ... | 0x00 |
	pcmpeqb xmm7, xmm7			; XMM7 = | 0xFF | 0xFF | ... | 0xFF |
	
	; mascaras para positivos y para negativos
	pcmpgtb xmm1, xmm2			; XMM1 (bytes) = 0x00 si el char es NEGATIVO
								; 0xFF si es POSITIVO
	movdqu xmm6, xmm1
	pxor xmm6, xmm7				; XMM6 (bytes) = 0xFF si el char es NEGATIVO
								; 0x00 si es POSITIVO (XMM6 = NOT XMM1
								
	; separo positivos y negativos
	pand xmm0, xmm1				; XMM0 (bytes) = 0x00 si el char es NEGATIVO
								; el VALOR del char si es POSITIVO
	pand xmm5, xmm6				; XMM5 (bytes) = 0x00 si el char es POSITIVO
								; el VALOR del char si es NEGATIVO
    ;(!) pude separar positivos y negativos de a 16 elementos simultaneamente...
    ;--------------------------
    ; calculo sumPositiva
	; como son postitivos desempaqueto (extiendo signo) con XMM2 que tiene todos ceros
	mov xmm3, xmm0
	mov xmm4, xmm0
	punpcklbw xmm3, xmm2		; XMM3 (words) = | c7 | c6 | ... | c0 |
	punpcklbw xmm4, xmm2		; XMM4 (words) = | c15 | c14 | ... | c8 |
	paddw xmm3, xmm4			; XMM3 (words) = | c15 + c7 | ... | c8 + c0 |
	;(!) al tener que desempaquetar de byte a word, me quedan 8 por registro
	;(!) entonces, sumo los positivos de a 8 elementos simultaneamente...

	; calculo sumNegativa
	; como son negativos desempaqueto (extiendo signo)
	; con XMM6 que tiene todos 1s donde hay negativos y ceros donde no...
	mov xmm8, xmm5
	mov xmm9, xmm5
	punpcklbw xmm8, xmm6		; XMM8 (words) = | c7 | c6 | ... | c0 |
	punpcklbw xmm9, xmm6		; XMM9 (words) = | c15 | c14 | ... | c8 |
	paddw xmm8, xmm9			; XMM8 (words) = | c15 + c7 | ... | c8 + c0 |
	;(!) al tener que desempaquetar de byte a word, me quedan 8 por registro
	;(!) entonces, sumo los negativos de a 8 elementos simultaneamente...
	
	;-------------------------	
	paddw xmm10, xmm3			; acumulo positivos
	paddw xmm11, xmm8			; acumulo negativos
	add rdi, 16					; incremento puntero
	loop .ciclo
	;(!) pude procesar los 16 elementos de M en un ciclo...
\end{lstlisting}

\subsection{Pila Magica}
Algunas ideas:
\begin{itemize}
\item Recorro la lista hasta el iltimo elemento para poder leerlos de atras para adelante. Si los apilo en la pila de atras para quedan bien para que los tome como arrat "dameVector".
\item Pusheo primero en la pila el 0 (null) para indicar el fin del vector.
\item Los punteros a los short est\'an en "\&(numero->n)", eso lo tengo que meter en la pila.
\item El fin del ciclo puede ser: Comparando el primer puntero (me lo guarde al principio) o contando cantidad de elementos.
\item El tope de la pila es el primer elemento del vector y sirve como \emph{unsigned short* numeros[]} para par\'ametro.
\item Dejar la pila en estado consistente
\end{itemize}

\begin{lstlisting}[frame=single, style=asmStyle]
ahiVaElVector:
	push rbp
	mov rbp, rsp
	push r15

	mov rdx, [rdi + OFFSET_SIGUIENTE]	; asumo la lista no esta vacia
	mov r15, [rsp] ;guardo mi inicio de memoria

	xor rcx,rcx
.cicloAdelante:
	inc rcx ;dejo rcx aca porque hace un loop y
			;sino deberia hacer cmp por null en el prox ciclo
	cmp rdx, NULL
	je .cicloAtras
	mov rdi, rdx
	mov rdx, [rdx + OFFSET_SIGUIENTE]
	jmp .cicloAdelante

	push NULL							; pongo el NULL

.cicloAtras:
	lea rdx, [rdi + OFFSET_N]			; RDX = &(numero->n)
	push rdx
	mov rdi, [rdi + OFFSET_ANTERIOR]
	loop .cicloAtras
	
	mov rdi, rsp ;aca apunta mi "primer" elem.

	;alineo la pila con matemagicas
	and rsp, 0xffffffffffffffffff0 ;son 15 F's. 15x4=60 bits
	call dameVector
	
	mov rsp, r15 ;aca tenia mi rsp despues de los push 
	pop r15
	pop rbp
	ret
\end{lstlisting}
\end{document}