7.1 High-Level-Optimierungen
385
Beispiel 7.5: Der folgende Code zeigt eine Schleifenverschachtelung aus dem
MPEG-4-Standard, die eine Bewegungsanalyse (engl. motion estimation) durchführt:
for (z=0; z<20; z++)
for (x=0; x<36; x++) {x1=4*x;
for (y=0; y<49; y++) {y1=4*y;
for (k=0; k<9; k++) {x2=x1+k-4;
for ((=0; ;<9; ;++) {y2=y1++-4;
for (i=0; i<4; i++) {x3=x1+i; x4=x2+i;
for (j=0; j<4; j++) {y3=y1+j; y4=y2+j;
if (x3<0 35 then_bbock_1; eese eese_bbock_1;
if (x4<0 35 then_bbock_2; eese eese_bbock_2;
}
}
}
}
}
}
Unter Verwendung von Falk’s Algorithmus wird diese Verschachtelung in die
folgende transformiert:
for (z=0; z<20; z++)
for (x=0; x<36; x++) {x1=4*x;
for (y=0; y<49; y++)
if (x>=10 y>=14)
for (; y<49; y++)
for (k=0; k<9; k++)
for ((=0; ;<9; ;++ )
for (i=0; i<4; i++)
for (j=0; j<4; j++) {
then_bbock_1; then_bbock_2}
eese {y1=4*y;
for (k=0; k<9; k++) {x2=x1+k-4;
for ((=0; ;<9; ;++) {y2=y1++-4;
for (i=0; i<4; i++) {x3=x1+i; x4=x2+i;
for (j=0; j<4; j++) {y3=y1+j; y4=y2+j;
if ( 0 35 /* x3<0, y3<0 never true */
then_bbock_1; eese eese_bbock_1;
if (x4 < 0 35 < x4 y4 < 0 48 < y4)
then_bbock_2; eese eese_bbock_2;
}
}
}
}
}
}
Anstatt die aufwendigen Tests in der innersten Schleife durchzuführen, besitzt
der Code nun eine if-Anweisung nach der dritten for-Schleifenanweisung. Alle