CODEWITHSUNDEEP
c
Juan
Juan

Reputation: 2103

Fast Multiplication Code in C

I am studying multiplication source code and I don't understand this function for multiplying x*A. Please help me to understand this with any numeric example please?

#define BITS_PER_LONG (8 * sizeof (unsigned long))

typedef struct matrix{
int rown;//number of rows.
int coln;//number of columns.
int rwdcnt;//number of words in a row
int alloc_size;//number of allocated bytes
unsigned long *elem;//row index.
}*binmat_t;

void mat_vec_mul(unsigned long *cR, unsigned char *x, binmat_t A)
{
    int i,j;
    unsigned long *pt;

    memset(cR, 0, A->rwdcnt*sizeof(long));
    pt = A->elem;
    for(i=0; i<A->rown; i++)
    {
        if ((x[i/8] >> (i%8)) & 1)
            for (j = 0;  j < A->rwdcnt;  ++j)
                cR[j] ^= *pt++;
        else
            pt += A->rwdcnt;
    }
}

Upvotes: 1

Views: 1100

Answers (1)

Eric Postpischil
Eric Postpischil

Reputation: 222234

x is a vector of bits, which are stored in an array of char. The number of bits in x is A->rown. The expression (x[i/8] >> (i%8)) & 1 selects the ith bit of x.

A is a two-dimensional array of unsigned long, with A->rown rows and A->rwdcnt columns.

cR is a vector of unsigned long with A->rwdcnt elements. cR is cleared upon entering this routine.

The if statement determines whether the ith bit in x is on. If the bit is on, then the ith column of A is “added” to cR. If the bit is off, then the else clause skips this column of A. Since a bit can have only values of 1 or 0, this if-else is equivalent to multiplying the column of A by the bit and adding the product to cR.

The “addition” is done by XOR. The interpretation here is unclear. It may be that each cR is a single array of bits (and each column of A), or it may be that each unsigned long in cR (and in A) represents a polynomial over the integers modulo two. (This is a common type in cryptography.)

I suspect that cR is a single array of bits, and that A->rwdcnt = A->coln / BITS_PER_LONG.

Effectively, this is a standard array multiplication over the integers modulo two.

Upvotes: 2

Related Questions