In the last blog entry ive mentioned the hadamard transform, so its high time to dissuss it

the hadamard transform is a linear transform, and all linear transforms can be written as a vector-matrix multiplication, here the matrix is orthogonal, symmetric and all it elements are either a or -a. Actually this is commonly written as a matrix of 1 and -1 which is multiplied by a which is sqrt(size of the transform), you also might want to take a look at Wikipedia/Hadamard_transform.

The hadamard transform is also somewhat similar to the DCT but simpler, thats also why its used as part of a SATD motion estimation comparission function, the dct would be slightly better quality wise but significantly slower …

#### How to calculate it

Well there are many ways

a slow and simple one is:

for(i=0; i<n; i++){
dst[i]=0;
for(j=0; j<n; j++){
int sign= parity(i&j) ? -1 : 1;
dst[i] += src[j] * sign;
}
}

a faster one is:

void transform(int *data, int step, int n){
int i, j;
for(i=0; i<n; i+=2*step){
for(j=i; j<i+step; j++){
int a= data[j];
data[j] = a + data[j+step];
data[j+step] = a - data[j+step];
}
}
if(2*step<n)
transform(data, 2*step, n);
}

You should of course not implement this recursively, but instead remove recursion, unroll the loops where cleanly possible and replace step and n by constants if you can.

Ive just written it like above as its IMHO easier to understand that way then 2 pages of unrolled loops