# HG changeset patch # User arpi_esp # Date 1010983199 0 # Node ID ccf36af385f3ab16a94b88f67578d49bf04dd39c # Parent fceb435fae6b2c1aa3e1219a7a219eb728273447 (commit by michael) faster simple_idct in C diff -r fceb435fae6b -r ccf36af385f3 simple_idct.c --- a/simple_idct.c Mon Jan 14 04:34:52 2002 +0000 +++ b/simple_idct.c Mon Jan 14 04:39:59 2002 +0000 @@ -45,33 +45,50 @@ #define ROW_SHIFT 11 #define COL_SHIFT 20 // 6 #endif -#if 1 -static void inline idctRow (int16_t * row) + +/* 8x8 Matrix used to do a trivial (slow) 8 point IDCT */ +static int coeff[64]={ + W4, W4, W4, W4, W4, W4, W4, W4, + W1, W3, W5, W7,-W7,-W5,-W3,-W1, + W2, W6,-W6,-W2,-W2,-W6, W6, W2, + W3,-W7,-W1,-W5, W5, W1, W7,-W3, + W4,-W4,-W4, W4, W4,-W4,-W4, W4, + W5,-W1, W7, W3,-W3,-W7, W1,-W5, + W6,-W2, W2,-W6,-W6, W2,-W2, W6, + W7,-W5, W3,-W1, W1,-W3, W5,-W7 +}; + +static int inline idctRowCondZ (int16_t * row) { int a0, a1, a2, a3, b0, b1, b2, b3; - const int C1 =W1; - const int C2 =W2; - const int C3 =W3; - const int C4 =W4; - const int C5 =W5; - const int C6 =W6; - const int C7 =W7; - if( !(row[1] | row[2] |row[3] |row[4] |row[5] |row[6] | row[7])) { - row[0] = row[1] = row[2] = row[3] = row[4] = - row[5] = row[6] = row[7] = row[0]<<3; - return; + if( !( ((uint32_t*)row)[0]|((uint32_t*)row)[1] |((uint32_t*)row)[2] |((uint32_t*)row)[3])) { +/* row[0] = row[1] = row[2] = row[3] = row[4] = + row[5] = row[6] = row[7] = 0;*/ + return 0; } - a0 = C4*row[0] + C2*row[2] + C4*row[4] + C6*row[6] + (1<<(ROW_SHIFT-1)); - a1 = C4*row[0] + C6*row[2] - C4*row[4] - C2*row[6] + (1<<(ROW_SHIFT-1)); - a2 = C4*row[0] - C6*row[2] - C4*row[4] + C2*row[6] + (1<<(ROW_SHIFT-1)); - a3 = C4*row[0] - C2*row[2] + C4*row[4] - C6*row[6] + (1<<(ROW_SHIFT-1)); + if(!( ((uint32_t*)row)[2] |((uint32_t*)row)[3] )){ + a0 = W4*row[0] + W2*row[2] + (1<<(ROW_SHIFT-1)); + a1 = W4*row[0] + W6*row[2] + (1<<(ROW_SHIFT-1)); + a2 = W4*row[0] - W6*row[2] + (1<<(ROW_SHIFT-1)); + a3 = W4*row[0] - W2*row[2] + (1<<(ROW_SHIFT-1)); - b0 = C1*row[1] + C3*row[3] + C5*row[5] + C7*row[7]; - b1 = C3*row[1] - C7*row[3] - C1*row[5] - C5*row[7]; - b2 = C5*row[1] - C1*row[3] + C7*row[5] + C3*row[7]; - b3 = C7*row[1] - C5*row[3] + C3*row[5] - C1*row[7]; + b0 = W1*row[1] + W3*row[3]; + b1 = W3*row[1] - W7*row[3]; + b2 = W5*row[1] - W1*row[3]; + b3 = W7*row[1] - W5*row[3]; + }else{ + a0 = W4*row[0] + W2*row[2] + W4*row[4] + W6*row[6] + (1<<(ROW_SHIFT-1)); + a1 = W4*row[0] + W6*row[2] - W4*row[4] - W2*row[6] + (1<<(ROW_SHIFT-1)); + a2 = W4*row[0] - W6*row[2] - W4*row[4] + W2*row[6] + (1<<(ROW_SHIFT-1)); + a3 = W4*row[0] - W2*row[2] + W4*row[4] - W6*row[6] + (1<<(ROW_SHIFT-1)); + + b0 = W1*row[1] + W3*row[3] + W5*row[5] + W7*row[7]; + b1 = W3*row[1] - W7*row[3] - W1*row[5] - W5*row[7]; + b2 = W5*row[1] - W1*row[3] + W7*row[5] + W3*row[7]; + b3 = W7*row[1] - W5*row[3] + W3*row[5] - W1*row[7]; + } row[0] = (a0 + b0) >> ROW_SHIFT; row[1] = (a1 + b1) >> ROW_SHIFT; @@ -81,151 +98,324 @@ row[5] = (a2 - b2) >> ROW_SHIFT; row[6] = (a1 - b1) >> ROW_SHIFT; row[7] = (a0 - b0) >> ROW_SHIFT; + + return 1; +} + +static int inline idctRowCondDC (int16_t * row) +{ + int a0, a1, a2, a3, b0, b1, b2, b3; + + if( !( ((uint32_t*)row)[1] |((uint32_t*)row)[2] |((uint32_t*)row)[3]| row[1])) { +// row[0] = row[1] = row[2] = row[3] = row[4] = row[5] = row[6] = row[7] = row[0]<<3; + uint16_t temp= row[0]<<3; + ((uint32_t*)row)[0]=((uint32_t*)row)[1]= + ((uint32_t*)row)[2]=((uint32_t*)row)[3]= temp + (temp<<16); + return 0; + } + + if(!( ((uint32_t*)row)[2] |((uint32_t*)row)[3] )){ + a0 = W4*row[0] + W2*row[2] + (1<<(ROW_SHIFT-1)); + a1 = W4*row[0] + W6*row[2] + (1<<(ROW_SHIFT-1)); + a2 = W4*row[0] - W6*row[2] + (1<<(ROW_SHIFT-1)); + a3 = W4*row[0] - W2*row[2] + (1<<(ROW_SHIFT-1)); + + b0 = W1*row[1] + W3*row[3]; + b1 = W3*row[1] - W7*row[3]; + b2 = W5*row[1] - W1*row[3]; + b3 = W7*row[1] - W5*row[3]; + }else{ + a0 = W4*row[0] + W2*row[2] + W4*row[4] + W6*row[6] + (1<<(ROW_SHIFT-1)); + a1 = W4*row[0] + W6*row[2] - W4*row[4] - W2*row[6] + (1<<(ROW_SHIFT-1)); + a2 = W4*row[0] - W6*row[2] - W4*row[4] + W2*row[6] + (1<<(ROW_SHIFT-1)); + a3 = W4*row[0] - W2*row[2] + W4*row[4] - W6*row[6] + (1<<(ROW_SHIFT-1)); + + b0 = W1*row[1] + W3*row[3] + W5*row[5] + W7*row[7]; + b1 = W3*row[1] - W7*row[3] - W1*row[5] - W5*row[7]; + b2 = W5*row[1] - W1*row[3] + W7*row[5] + W3*row[7]; + b3 = W7*row[1] - W5*row[3] + W3*row[5] - W1*row[7]; + } + + row[0] = (a0 + b0) >> ROW_SHIFT; + row[7] = (a0 - b0) >> ROW_SHIFT; + row[1] = (a1 + b1) >> ROW_SHIFT; + row[6] = (a1 - b1) >> ROW_SHIFT; + row[2] = (a2 + b2) >> ROW_SHIFT; + row[5] = (a2 - b2) >> ROW_SHIFT; + row[3] = (a3 + b3) >> ROW_SHIFT; + row[4] = (a3 - b3) >> ROW_SHIFT; + + return 1; } static void inline idctCol (int16_t * col) { - int a0, a1, a2, a3, b0, b1, b2, b3; - const int C1 =W1; - const int C2 =W2; - const int C3 =W3; - const int C4 =W4; - const int C5 =W5; - const int C6 =W6; - const int C7 =W7; + /* if( !(col[8*1] | col[8*2] |col[8*3] |col[8*4] |col[8*5] |col[8*6] | col[8*7])) { col[8*0] = col[8*1] = col[8*2] = col[8*3] = col[8*4] = col[8*5] = col[8*6] = col[8*7] = col[8*0]<<3; return; }*/ + + int a0, a1, a2, a3, b0, b1, b2, b3; col[0] += (1<<(COL_SHIFT-1))/W4; - a0 = C4*col[8*0] + C2*col[8*2] + C4*col[8*4] + C6*col[8*6]; - a1 = C4*col[8*0] + C6*col[8*2] - C4*col[8*4] - C2*col[8*6]; - a2 = C4*col[8*0] - C6*col[8*2] - C4*col[8*4] + C2*col[8*6]; - a3 = C4*col[8*0] - C2*col[8*2] + C4*col[8*4] - C6*col[8*6]; + a0 = W4*col[8*0] + W2*col[8*2] + W4*col[8*4] + W6*col[8*6]; + a1 = W4*col[8*0] + W6*col[8*2] - W4*col[8*4] - W2*col[8*6]; + a2 = W4*col[8*0] - W6*col[8*2] - W4*col[8*4] + W2*col[8*6]; + a3 = W4*col[8*0] - W2*col[8*2] + W4*col[8*4] - W6*col[8*6]; - b0 = C1*col[8*1] + C3*col[8*3] + C5*col[8*5] + C7*col[8*7]; - b1 = C3*col[8*1] - C7*col[8*3] - C1*col[8*5] - C5*col[8*7]; - b2 = C5*col[8*1] - C1*col[8*3] + C7*col[8*5] + C3*col[8*7]; - b3 = C7*col[8*1] - C5*col[8*3] + C3*col[8*5] - C1*col[8*7]; + b0 = W1*col[8*1] + W3*col[8*3] + W5*col[8*5] + W7*col[8*7]; + b1 = W3*col[8*1] - W7*col[8*3] - W1*col[8*5] - W5*col[8*7]; + b2 = W5*col[8*1] - W1*col[8*3] + W7*col[8*5] + W3*col[8*7]; + b3 = W7*col[8*1] - W5*col[8*3] + W3*col[8*5] - W1*col[8*7]; col[8*0] = (a0 + b0) >> COL_SHIFT; + col[8*7] = (a0 - b0) >> COL_SHIFT; col[8*1] = (a1 + b1) >> COL_SHIFT; + col[8*6] = (a1 - b1) >> COL_SHIFT; col[8*2] = (a2 + b2) >> COL_SHIFT; + col[8*5] = (a2 - b2) >> COL_SHIFT; col[8*3] = (a3 + b3) >> COL_SHIFT; col[8*4] = (a3 - b3) >> COL_SHIFT; - col[8*5] = (a2 - b2) >> COL_SHIFT; +} + +static void inline idctSparseCol (int16_t * col) +{ + int a0, a1, a2, a3, b0, b1, b2, b3; + col[0] += (1<<(COL_SHIFT-1))/W4; + a0 = W4*col[8*0]; + a1 = W4*col[8*0]; + a2 = W4*col[8*0]; + a3 = W4*col[8*0]; + + if(col[8*2]){ + a0 += + W2*col[8*2]; + a1 += + W6*col[8*2]; + a2 += - W6*col[8*2]; + a3 += - W2*col[8*2]; + } + + if(col[8*4]){ + a0 += + W4*col[8*4]; + a1 += - W4*col[8*4]; + a2 += - W4*col[8*4]; + a3 += + W4*col[8*4]; + } + + if(col[8*6]){ + a0 += + W6*col[8*6]; + a1 += - W2*col[8*6]; + a2 += + W2*col[8*6]; + a3 += - W6*col[8*6]; + } + + if(col[8*1]){ + b0 = W1*col[8*1]; + b1 = W3*col[8*1]; + b2 = W5*col[8*1]; + b3 = W7*col[8*1]; + }else{ + b0 = + b1 = + b2 = + b3 = 0; + } + + if(col[8*3]){ + b0 += + W3*col[8*3]; + b1 += - W7*col[8*3]; + b2 += - W1*col[8*3]; + b3 += - W5*col[8*3]; + } + + if(col[8*5]){ + b0 += + W5*col[8*5]; + b1 += - W1*col[8*5]; + b2 += + W7*col[8*5]; + b3 += + W3*col[8*5]; + } + + if(col[8*7]){ + b0 += + W7*col[8*7]; + b1 += - W5*col[8*7]; + b2 += + W3*col[8*7]; + b3 += - W1*col[8*7]; + } + + if(!(b0|b1|b2|b3)){ + col[8*0] = (a0) >> COL_SHIFT; + col[8*7] = (a0) >> COL_SHIFT; + col[8*1] = (a1) >> COL_SHIFT; + col[8*6] = (a1) >> COL_SHIFT; + col[8*2] = (a2) >> COL_SHIFT; + col[8*5] = (a2) >> COL_SHIFT; + col[8*3] = (a3) >> COL_SHIFT; + col[8*4] = (a3) >> COL_SHIFT; + }else{ + col[8*0] = (a0 + b0) >> COL_SHIFT; + col[8*7] = (a0 - b0) >> COL_SHIFT; + col[8*1] = (a1 + b1) >> COL_SHIFT; + col[8*6] = (a1 - b1) >> COL_SHIFT; + col[8*2] = (a2 + b2) >> COL_SHIFT; + col[8*5] = (a2 - b2) >> COL_SHIFT; + col[8*3] = (a3 + b3) >> COL_SHIFT; + col[8*4] = (a3 - b3) >> COL_SHIFT; + } +} + +static void inline idctSparse2Col (int16_t * col) +{ + int a0, a1, a2, a3, b0, b1, b2, b3; + col[0] += (1<<(COL_SHIFT-1))/W4; + a0 = W4*col[8*0]; + a1 = W4*col[8*0]; + a2 = W4*col[8*0]; + a3 = W4*col[8*0]; + + if(col[8*2]){ + a0 += + W2*col[8*2]; + a1 += + W6*col[8*2]; + a2 += - W6*col[8*2]; + a3 += - W2*col[8*2]; + } + + if(col[8*4]){ + a0 += + W4*col[8*4]; + a1 += - W4*col[8*4]; + a2 += - W4*col[8*4]; + a3 += + W4*col[8*4]; + } + + if(col[8*6]){ + a0 += + W6*col[8*6]; + a1 += - W2*col[8*6]; + a2 += + W2*col[8*6]; + a3 += - W6*col[8*6]; + } + + if(col[8*1] || 1){ + b0 = W1*col[8*1]; + b1 = W3*col[8*1]; + b2 = W5*col[8*1]; + b3 = W7*col[8*1]; + }else{ + b0 = + b1 = + b2 = + b3 = 0; + } + + if(col[8*3]){ + b0 += + W3*col[8*3]; + b1 += - W7*col[8*3]; + b2 += - W1*col[8*3]; + b3 += - W5*col[8*3]; + } + + if(col[8*5]){ + b0 += + W5*col[8*5]; + b1 += - W1*col[8*5]; + b2 += + W7*col[8*5]; + b3 += + W3*col[8*5]; + } + + if(col[8*7]){ + b0 += + W7*col[8*7]; + b1 += - W5*col[8*7]; + b2 += + W3*col[8*7]; + b3 += - W1*col[8*7]; + } + + col[8*0] = (a0 + b0) >> COL_SHIFT; + col[8*7] = (a0 - b0) >> COL_SHIFT; + col[8*1] = (a1 + b1) >> COL_SHIFT; col[8*6] = (a1 - b1) >> COL_SHIFT; - col[8*7] = (a0 - b0) >> COL_SHIFT; + col[8*2] = (a2 + b2) >> COL_SHIFT; + col[8*5] = (a2 - b2) >> COL_SHIFT; + col[8*3] = (a3 + b3) >> COL_SHIFT; + col[8*4] = (a3 - b3) >> COL_SHIFT; } + void simple_idct (short *block) { + int i; - for(i=0; i<8; i++) - idctRow(block + 8*i); - - for(i=0; i<8; i++) - idctCol(block + i); - -} - -#else - -#define W1 22725 //cos(i*M_PI/16)*sqrt(2)*(1<<14) + 0.5 -#define W2 21407 //cos(i*M_PI/16)*sqrt(2)*(1<<14) + 0.5 -#define W3 19266 //cos(i*M_PI/16)*sqrt(2)*(1<<14) + 0.5 -#define W4 16384 //cos(i*M_PI/16)*sqrt(2)*(1<<14) + 0.5 -#define W5 12873 //cos(i*M_PI/16)*sqrt(2)*(1<<14) + 0.5 -#define W6 8867 //cos(i*M_PI/16)*sqrt(2)*(1<<14) + 0.5 -#define W7 4520 //cos(i*M_PI/16)*sqrt(2)*(1<<14) + 0.5 -#define COL_SHIFT 31 // 6 - -static void inline idctRow (int32_t *out, int16_t * row) -{ - int a0, a1, a2, a3, b0, b1, b2, b3; - const int C1 =W1; - const int C2 =W2; - const int C3 =W3; - const int C4 =W4; - const int C5 =W5; - const int C6 =W6; - const int C7 =W7; -/* - if( !(row[1] | row[2] |row[3] |row[4] |row[5] |row[6] | row[7])) { - row[0] = row[1] = row[2] = row[3] = row[4] = - row[5] = row[6] = row[7] = row[0]<<14; - return; + +#if 0 + int nonZero[8]; + int buffer[64]; + int nNonZero=0; + + idctRowCondDC(block); + + for(i=1; i<8; i++) + { + nonZero[nNonZero]=i; + nNonZero+= idctRowCondZ(block + i*8); + } + + if(nNonZero==0) + { + for(i=0; i<8; i++) + { + block[i ]= + block[i+8 ]= + block[i+16]= + block[i+24]= + block[i+32]= + block[i+40]= + block[i+48]= + block[i+56]= (W4*block[i] + (1<<(COL_SHIFT-1))) >> COL_SHIFT; + } } -*/ - a0 = C4*row[0] + C2*row[2] + C4*row[4] + C6*row[6]; - a1 = C4*row[0] + C6*row[2] - C4*row[4] - C2*row[6]; - a2 = C4*row[0] - C6*row[2] - C4*row[4] + C2*row[6]; - a3 = C4*row[0] - C2*row[2] + C4*row[4] - C6*row[6]; - - b0 = C1*row[1] + C3*row[3] + C5*row[5] + C7*row[7]; - b1 = C3*row[1] - C7*row[3] - C1*row[5] - C5*row[7]; - b2 = C5*row[1] - C1*row[3] + C7*row[5] + C3*row[7]; - b3 = C7*row[1] - C5*row[3] + C3*row[5] - C1*row[7]; - - out[0] = (a0 + b0); - out[1] = (a1 + b1); - out[2] = (a2 + b2); - out[3] = (a3 + b3); - out[4] = (a3 - b3); - out[5] = (a2 - b2); - out[6] = (a1 - b1); - out[7] = (a0 - b0); + else if(nNonZero==1) + { + int index= nonZero[0]*8; + for(i=0; i<8; i++) + { + int bias= W4*block[i] + (1<<(COL_SHIFT-1)); + int c= block[i + index]; + block[i ]= (c*coeff[index ] + bias) >> COL_SHIFT; + block[i+8 ]= (c*coeff[index+1] + bias) >> COL_SHIFT; + block[i+16]= (c*coeff[index+2] + bias) >> COL_SHIFT; + block[i+24]= (c*coeff[index+3] + bias) >> COL_SHIFT; + block[i+32]= (c*coeff[index+4] + bias) >> COL_SHIFT; + block[i+40]= (c*coeff[index+5] + bias) >> COL_SHIFT; + block[i+48]= (c*coeff[index+6] + bias) >> COL_SHIFT; + block[i+56]= (c*coeff[index+7] + bias) >> COL_SHIFT; + } + } +/* else if(nNonZero==2) + { + int index1= nonZero[0]*8; + int index2= nonZero[1]*8; + for(i=0; i<8; i++) + { + int bias= W4*block[i] + (1<<(COL_SHIFT-1)); + int c1= block[i + index1]; + int c2= block[i + index2]; + block[i ]= (c1*coeff[index1 ] + c2*coeff[index2 ] + bias) >> COL_SHIFT; + block[i+8 ]= (c1*coeff[index1+1] + c2*coeff[index2+1] + bias) >> COL_SHIFT; + block[i+16]= (c1*coeff[index1+2] + c2*coeff[index2+2] + bias) >> COL_SHIFT; + block[i+24]= (c1*coeff[index1+3] + c2*coeff[index2+3] + bias) >> COL_SHIFT; + block[i+32]= (c1*coeff[index1+4] + c2*coeff[index2+4] + bias) >> COL_SHIFT; + block[i+40]= (c1*coeff[index1+5] + c2*coeff[index2+5] + bias) >> COL_SHIFT; + block[i+48]= (c1*coeff[index1+6] + c2*coeff[index2+6] + bias) >> COL_SHIFT; + block[i+56]= (c1*coeff[index1+7] + c2*coeff[index2+7] + bias) >> COL_SHIFT; + } + }*/ + else + { + for(i=0; i<8; i++) + idctSparse2Col(block + i); + } +#else + for(i=0; i<8; i++) + idctRowCondDC(block + i*8); + + for(i=0; i<8; i++) + idctSparseCol(block + i); +#endif } - -static void inline idctCol (int32_t *in, int16_t * col) -{ - int64_t a0, a1, a2, a3, b0, b1, b2, b3; - const int64_t C1 =W1; - const int64_t C2 =W2; - const int64_t C3 =W3; - const int64_t C4 =W4; - const int64_t C5 =W5; - const int64_t C6 =W6; - const int64_t C7 =W7; -/* - if( !(col[8*1] | col[8*2] |col[8*3] |col[8*4] |col[8*5] |col[8*6] | col[8*7])) { - col[8*0] = col[8*1] = col[8*2] = col[8*3] = col[8*4] = - col[8*5] = col[8*6] = col[8*7] = col[8*0]<<3; - return; - }*/ - in[0] += (1<<(COL_SHIFT-1))/W4; - a0 = C4*in[8*0] + C2*in[8*2] + C4*in[8*4] + C6*in[8*6]; - a1 = C4*in[8*0] + C6*in[8*2] - C4*in[8*4] - C2*in[8*6]; - a2 = C4*in[8*0] - C6*in[8*2] - C4*in[8*4] + C2*in[8*6]; - a3 = C4*in[8*0] - C2*in[8*2] + C4*in[8*4] - C6*in[8*6]; - - b0 = C1*in[8*1] + C3*in[8*3] + C5*in[8*5] + C7*in[8*7]; - b1 = C3*in[8*1] - C7*in[8*3] - C1*in[8*5] - C5*in[8*7]; - b2 = C5*in[8*1] - C1*in[8*3] + C7*in[8*5] + C3*in[8*7]; - b3 = C7*in[8*1] - C5*in[8*3] + C3*in[8*5] - C1*in[8*7]; - - col[8*0] = (a0 + b0) >> COL_SHIFT; - col[8*1] = (a1 + b1) >> COL_SHIFT; - col[8*2] = (a2 + b2) >> COL_SHIFT; - col[8*3] = (a3 + b3) >> COL_SHIFT; - col[8*4] = (a3 - b3) >> COL_SHIFT; - col[8*5] = (a2 - b2) >> COL_SHIFT; - col[8*6] = (a1 - b1) >> COL_SHIFT; - col[8*7] = (a0 - b0) >> COL_SHIFT; -} - -void simple_idct (short *block) -{ - int i; - int32_t temp[64]; - for(i=0; i<8; i++) - idctRow(temp+8*i, block + 8*i); - - for(i=0; i<8; i++) - idctCol(temp+i, block + i); - -} - -#endif