# Transposing a square matrix (n x n)

I wish to transpose a square matrix, permanently overwriting it.
This is not the same as creating a 2nd matrix with the transposed contents of the 1st matrix.

I call the procedure with 3 parameters: the address of the original matrix, its rank, and the address of a scratch buffer that is large enough.
First, all the elements are spread out over the scratch buffer. Later the scratch buffer is copied back to the original storage.

How can I optimize this code?

; TransposeSquareMatrix(Address, Rank, Scratch)
Q:  push    ebp
mov     ebp, esp
push    ecx edx esi edi
mov     esi, [ebp+8]    ; Address
mov     edx, [ebp+12]   ; Rank
mov     edi, [ebp+16]   ; Scratch buffer
lea     eax, [edx-1]    ; Additional address increment
.a: push    edi             ; (1)
mov     ecx, [ebp+12]   ; Rank
.b: movsb                   ; Spreading out the elements of one row
add     edi, eax
dec     ecx
jnz     .b
pop     edi             ; (1)
inc     edi
dec     edx
jnz     .a              ; Repeating it for every row
mov     edi, [ebp+8]    ; Address
mov     ecx, [ebp+12]   ; Rank
imul    ecx, ecx
mov     esi, [ebp+16]   ; Scratch buffer
rep movsb               ; Overwriting the original matrix
pop     edi esi edx ecx
pop     ebp
ret     12
; --------------------------

• Below is a self-answer. Please don't let that stop you from writing a review. Code improvements or perhaps suggesting an alternative approach? May 29, 2019 at 23:50

## 20+ percent faster using the stack for the extra buffer.

Matrix     Question     Answer(1)    Faster
-------------------------------------------
16 x 16    3.62 µsec    2.62 µsec    27.6 %
13 x 13    2.67 µsec    2.05 µsec    23.2 %
10 x 10    1.77 µsec    1.35 µsec    23.7 %
7 x  7    1.02 µsec    0.77 µsec    24.5 %
4 x  4    0.56 µsec    0.44 µsec    21.4 %


Setting up a temporary scratch buffer in the stack proved to be a winner. A decent speed increase, no need for the 3rd parameter, and with a single branch target, applying code alignment could be a bit easier.

This pushes the same 5 registers but delays assigning EBP so it can be used as an EndOfBuffer marker. A minor drawback is that the easy recognizable EBP-offsets for the parameters (+8, +12, ...) are gone. Requires some more attention to detail like in the ESP-offsets of today.

Nothing is pushed on the stack below the local stack buffer and so keeping ESP dword-aligned is not needed.

This is cleaner code. I think addressing the parameters several times over, looked a bit untidy.

; TransposeSquareMatrix(Address, Rank)
A1: push    ecx edx esi edi ebp
mov     ebp, esp
mov     esi, [ebp+24]   ; Address
mov     edx, [ebp+28]   ; Rank
mov     ecx, edx
imul    ecx, ecx        ; -> Size of matrix
sub     esp, ecx        ; Local buffer
mov     edi, esp
lea     eax, [edx-1]    ; (Rank - 1)
.a: movsb                   ; -> EDI += 1
add     edi, eax        ; -> EDI += (Rank - 1)
cmp     edi, ebp        ; Until end of local buffer
jb      .a
sub     edi, ecx        ; Back to start of current column
inc     edi             ; Go to start next column
dec     edx
jnz     .a              ; Repeat rank times
sub     esi, ecx        ; Copy to original storage
mov     edi, esi        ; -> EDI is Address
mov     esi, esp        ; -> ESI is local buffer
rep movsb
mov     esp, ebp
pop     ebp edi esi edx ecx
ret     8
; --------------------------


## 50+ percent faster without even using an extra buffer.

Matrix     Question     Answer(2)    Faster
-------------------------------------------
16 x 16    3.62 µsec    1.80 µsec    50.1 %
13 x 13    2.67 µsec    1.22 µsec    54.3 %
10 x 10    1.77 µsec    0.77 µsec    56.0 %
7 x  7    1.02 µsec    0.44 µsec    56.9 %
4 x  4    0.56 µsec    0.23 µsec    58.9 %


The elements on the main diagonal are never touched. All the other elements are flipped across the main diagonal.

; TransposeSquareMatrix(Address, Rank)
A2: push    ebx ecx edx esi edi ebp
mov     ebx, [esp+28]   ; Address
mov     ecx, [esp+32]   ; Rank
mov     ebp, ecx
dec     ecx
jz      .c              ; It's a (1 x 1) matrix
.a: push    ecx             ; (1)
mov     esi, ebx        ; Column address
mov     edi, ebx        ; Row address
.b: inc     esi             ; To next element in this row
add     edi, ebp        ; To next element in this column
mov     al, [esi]       ; Swap 2 elements
mov     dl, [edi]
mov     [edi], al
mov     [esi], dl
dec     ecx
jnz     .b
add     ebx, ebp        ; To next element on main diagonal
inc     ebx
pop     ecx             ; (1)
dec     ecx
jnz     .a              ; Continu until (1 x 1) matrix
.c: pop     ebp edi esi edx ecx ebx
ret     8
; --------------------------