Systemnahe Programmierung in Chome Systemnahe Programmierung in C: Matrizen als Felder von Zeigern auf Felder Prof. Dr. Uwe Schmidt FH Wedel
Matrizen-Verarbeitung
Matrizen als eindimensionale FelderInhaltsverzeichnisMatrizen mit Deskriptoren und Feldern von Zeigern auf Felder

Matrizen als Felder von Zeigern auf Felder

weiter
weiter

Implementierung von Matrizen mit Feldern von Zeigern

Matrizen
werden in diesem Beispiel durch Felder von Zeigern realisiert. Diese Zeiger zeigen auf die einzelnen Zeilen. Die Zeilen selbst sind wieder Felder, in denen die Elemente stehen.
 
Der Platz für die Zeilen kann aber in einem Stück alloziert werden. Das Feld für die Zeiger auf die Zeilen wird in der Allokationsroutine initialisiert. Damit hat man die Adressen der Zeilen einmal berechnet und kann durch einen einfachen indizierten Zugriff auf den Anfang einer Zeile verweisen. Mit einem zweiten einfachen indizierten Zugriff kann man ein Element erreichen.
 
Durch ein wenig mehr Aufwand, Platz und Zeit bei der Alloaktion kann beim Zugriff Zeit gespart werden. Dies ist sichtbar in dem Code für die Schleifenrümpfe in den Routinen addMatrix und transposeMatrix. Indizierter Zugriff ist in dieser Implementierung einfach zu realisieren, allerdings ohne eine Möglichkeit der Indexüberprüfung.
weiter
weiter

Die Schnittstelle: Matrix2.h

   1#ifndef Matrix2__
   2#define Matrix2__ 1
   3
   4typedef double Element;
   5
   6typedef Element *Row;
   7typedef Row *Matrix;
   8
   9/* constructor functions */
  10
  11extern Matrix newMatrix( int h, int w );
  12extern Matrix zeroMatrix( int h, int w );
  13extern Matrix unitMatrix( int h, int w );
  14
  15/* destructor */
  16
  17extern void freeMatrix( Matrix m );
  18
  19/* matrix ops */
  20
  21extern Matrix addMatrix( Matrix m1, Matrix m2, int h, int w );
  22extern Matrix transposeMatrix( Matrix m, int h, int w );
  23
  24/* element access ops */
  25/* unsave, unsave, unsave, ... */
  26
  27#define at(m,i,j) ((m)[j][i])
  28#define setAt(m,i,j,v) ((m)[i][j] = (v), (m))
  29
  30#endif
weiter
weiter

Die Implementierung: Matrix2.c

   1#include "Matrix2.h"
   2
   3#include <stdlib.h>
   4
   5/*--------------------*/
   6
   7Matrix newMatrix( int h, int w )
   8{
   9    Matrix res = malloc( h * sizeof( Row ) );
  10
  11    if ( res ) {
  12        Row rows = malloc( h * w * sizeof( Element ) );
  13
  14        if ( rows ) {
  15            Matrix m = res;
  16            Row r = rows;
  17
  18            while ( h-- ) {
  19                *m++ = r;
  20                r += w;
  21            }
  22
  23            return res;
  24        }
  25    }
  26    /* heap overflow */
  27    exit( 1 );
  28}
  29
  30/*--------------------*/
  31
  32void freeMatrix( Matrix m )
  33{
  34    free( m[0] );
  35    free( m );
  36}
  37
  38/*--------------------*/
  39
  40Matrix zeroMatrix( int h, int w )
  41{
  42    Matrix res = newMatrix( h, w );
  43
  44    int len = w * h;
  45    Row p = res[0];
  46
  47    while ( len-- ) {
  48        *p++ = 0.0;
  49    }
  50
  51    return res;
  52}
  53
  54/*--------------------*/
  55
  56Matrix unitMatrix( int h, int w )
  57{
  58    Matrix res = zeroMatrix( h, w );
  59    int i;
  60
  61    for ( i = 0; i < w && i < h; ++i ) {
  62        res[i][i] = 1.0;
  63    }
  64
  65    return res;
  66}
  67
  68/*--------------------*/
  69
  70Matrix addMatrix( Matrix m1, Matrix m2, int h, int w )
  71{
  72
  73    Matrix res = newMatrix( h, w );
  74    int i, j;
  75
  76    for ( i = 0; i < h; ++i ) {
  77        for ( j = 0; j < w; ++j ) {
  78            res[i][j] = m1[i][j] + m2[i][j];
  79        }
  80    }
  81
  82    return res;
  83}
  84
  85/*--------------------*/
  86
  87Matrix transposeMatrix( Matrix m, int h, int w )
  88{
  89
  90    Matrix res = newMatrix( w, h );
  91    int i, j;
  92
  93    for ( i = 0; i < h; ++i ) {
  94        for ( j = 0; j < w; ++j ) {
  95            res[j][i] = m[i][j];
  96        }
  97    }
  98
  99    return res;
 100}
weiter
weiter

Der Assembler-Code: gcc -O -o Matrix2-O.s -S Matrix2.c
Matrix2-O.s

1 newMatrix:
2 pushq %r12
3 pushq %rbp
4 pushq %rbx
5 movl %edi, %ebx
6 movl %esi, %r12d
7 movslq %edi, %rdi
8 salq $3, %rdi
9 call malloc
10 movq %rax, %rbp
11 testq %rax, %rax
12 je .L2
13 movl %ebx, %edi
14 imull %r12d, %edi
15 movslq %edi, %rdi
16 salq $3, %rdi
17 call malloc
18 testq %rax, %rax
19 je .L2
20 testl %ebx, %ebx
21 je .L3
22 movslq %r12d, %r12
23 salq $3, %r12
24 subl $1, %ebx
25 leaq 8(%rbp,%rbx,8), %rcx
26 movq %rbp, %rdx
27 .L4:
28 movq %rax, (%rdx)
29 addq $8, %rdx
30 addq %r12, %rax
31 cmpq %rcx, %rdx
32 jne .L4
33 .L3:
34 movq %rbp, %rax
35 popq %rbx
36 popq %rbp
37 popq %r12
38 ret
39 .L2:
40 movl $1, %edi
41 call exit
42 freeMatrix:
43 pushq %rbx
44 movq %rdi, %rbx
45 movq (%rdi), %rdi
46 call free
47 movq %rbx, %rdi
48 call free
49 popq %rbx
50 ret
51 zeroMatrix:
52 pushq %rbp
53 pushq %rbx
54 subq $8, %rsp
55 movl %edi, %ebp
56 movl %esi, %ebx
57 call newMatrix
58 imull %ebp, %ebx
59 movq (%rax), %rdx
60 testl %ebx, %ebx
61 je .L8
62 subl $1, %ebx
63 leaq 8(%rdx,%rbx,8), %rsi
64 movl $0, %ecx
65 .L9:
66 movq %rcx, (%rdx)
67 addq $8, %rdx
68 cmpq %rsi, %rdx
69 jne .L9
70 .L8:
71 addq $8, %rsp
72 popq %rbx
73 popq %rbp
74 ret
75 unitMatrix:
76 pushq %rbp
77 pushq %rbx
78 subq $8, %rsp
79 movl %edi, %ebp
80 movl %esi, %ebx
81 call zeroMatrix
82 testl %ebx, %ebx
83 jle .L12
84 testl %ebp, %ebp
85 jle .L12
86 movl $0, %edx
87 movabsq $4607182418800017408, %rdi
88 .L13:
89 movslq %edx, %rcx
90 movq (%rax,%rcx,8), %rsi
91 movq %rdi, (%rsi,%rcx,8)
92 addl $1, %edx
93 cmpl %edx, %ebx
94 jle .L12
95 cmpl %edx, %ebp
96 jg .L13
97 .L12:
98 addq $8, %rsp
99 popq %rbx
100 popq %rbp
101 ret
102 addMatrix:
103 pushq %r13
104 pushq %r12
105 pushq %rbp
106 pushq %rbx
107 subq $8, %rsp
108 movq %rdi, %rbp
109 movq %rsi, %rbx
110 movl %edx, %r13d
111 movl %ecx, %r12d
112 movl %ecx, %esi
113 movl %edx, %edi
114 call newMatrix
115 movl $0, %ecx
116 testl %r13d, %r13d
117 jg .L17
118 jmp .L18
119 .L19:
120 movq (%rax,%rcx,8), %rsi
121 movq 0(%rbp,%rcx,8), %r8
122 movq (%rbx,%rcx,8), %rdi
123 movsd (%r8,%rdx), %xmm0
124 addsd (%rdi,%rdx), %xmm0
125 movsd %xmm0, (%rsi,%rdx)
126 addq $8, %rdx
127 cmpq %r9, %rdx
128 jne .L19
129 .L20:
130 addq $1, %rcx
131 cmpl %ecx, %r13d
132 jg .L23
133 jmp .L18
134 .L17:
135 leal -1(%r12), %edx
136 leaq 8(,%rdx,8), %r9
137 .L23:
138 movl $0, %edx
139 testl %r12d, %r12d
140 jg .L19
141 jmp .L20
142 .L18:
143 addq $8, %rsp
144 popq %rbx
145 popq %rbp
146 popq %r12
147 popq %r13
148 ret
149 transposeMatrix:
150 pushq %r12
151 pushq %rbp
152 pushq %rbx
153 movq %rdi, %rbp
154 movl %esi, %ebx
155 movl %edx, %r12d
156 movl %edx, %edi
157 call newMatrix
158 testl %ebx, %ebx
159 jle .L25
160 subl $1, %ebx
161 leaq 8(,%rbx,8), %r9
162 movl $0, %ecx
163 leal -1(%r12), %edx
164 leaq 8(,%rdx,8), %r8
165 jmp .L26
166 .L27:
167 movq 0(%rbp,%rcx), %rsi
168 movq (%rsi,%rdx), %rdi
169 movq (%rax,%rdx), %rsi
170 movq %rdi, (%rsi,%rcx)
171 addq $8, %rdx
172 cmpq %r8, %rdx
173 jne .L27
174 .L28:
175 addq $8, %rcx
176 cmpq %r9, %rcx
177 je .L25
178 .L26:
179 movl $0, %edx
180 testl %r12d, %r12d
181 jg .L27
182 jmp .L28
183 .L25:
184 popq %rbx
185 popq %rbp
186 popq %r12
187 ret
weiter
weiter

Download

Quellen
Matrix2.h
Matrix2.c
SeitenanfangMatrizen-Verarbeitung
Matrizen als eindimensionale FelderInhaltsverzeichnisMatrizen mit Deskriptoren und Feldern von Zeigern auf Felder
Letzte Änderung: 11.01.2007
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel