# modulo 2 modulus

• 03-16-2006
breik
modulo 2 modulus
I'm having trouble writing a modulo 2 modulus function. I need to divide a 260 byte unsigned integer by a 4 byte unsigned integer without carrying bits (modulo 2) and return the remainder. Currently I'm using loops to perform bitshift and logical operations and I'm thinking it might be cleaner if I wrote separate functions for performing binary operations on arbitrarily large amounts of data. The reason why I know my function isn't currently working is that if I divide a dividend by a divisor, then add the remainder to the dividend and divide again, the second remainder is not zero. I would appreciate some help getting this function working.

My current function is:
Code:

```char *divide(char *message, char *divisor, char *remainder) {         unsigned int *poly=divisor;         unsigned int *result=remainder;         int i, j;         for (i=0; i<260; i++)         {                 for (j=7; j>=0; j--)                 {                         int action=(*result>>31)&1;                         *result<<=1;                         *result|=(*(message+i)>>j)&1;                         *result^=action*i;                 }         }         for (i=0; i<32; i++)         {                 int action=(*result>>31)&1;                 *result<<=1;                 *result^=action*i;         }         unsigned int temp=(1<<31)-1;         return (*result & temp); }```
In case it helps, I uploaded my whole source to show some context.
• 03-16-2006
breik
I changed it to cpp so that I could use booleans and wrote this:
Code:

```char *divide(char *message, char *divisor, char *remainder) {         unsigned int result=*((unsigned int*)message);         const unsigned int div=*((unsigned int*)divisor);         bool *p=(bool*)(message+32);         int i=2048;         while (i--)         {                 if (result>div)                 {                         result^=div;                 }                 result<<1;                 result+=*(p++);         }         *((unsigned int*)remainder)=result;         return remainder; }```
but it still isn't comming out with a zero remainder.
• 03-17-2006
valis
Also is char *message the dividend?

If you want I could slap together some pseudo-code to work with numbers as strings and a basic algorithm some hardware uses to divide numbers.

Finally what do you mean by carry? Do you mean you can't save the msb of a string you are shifting left?
• 03-17-2006
dwks
Quote:

I changed it to cpp so that I could use booleans
You can do that in C (C99), too. Just use _Bool instead of bool or include <stdbool.h> and use bool as before.

In C89, you can use this code:
Code:

`typedef enum {false, true} bool;`
• 03-20-2006
breik
binary arithmatic
Thanks for the thing about stdbool.h, I hadn't heard of it before. I think my problem is that I'm not understanding how to properly do modulo 2 division. The idea is that since we are concerned about bits, we do not carry when we do arithmatic. So instead of addition or subtraction, we use XOR. I want to be able to check for errors in a message that I send so I want to divide the bits of the message (*message is the dividend), add the remainder and divide again. If the remainder is 0 then I know the message sent without errors. I am having trouble writing a function that can divide the message by a divisor using binary arithmatic (modulo 2). If anyone knows some sort of sudo-code for this type of function, to divide a message by a divisor, it would help a lot.

Currently running the program looks like this:
message: 61736466000000000000000000.....
divisor: 37000000
remainder: ffffff9a506566
message: 61736466000000000000000000.....ffffff9a506566
remainder: ffffffc14b6566

if this were working properly, the second remainder should have been 0.
• 03-24-2006
dwks
Code:

`*((unsigned int*)remainder)=result;`
Why not pass remainder as an unsigned int * instead of casting it? My compiler gives a warning about that, something like "use of casts in lvalues is deprecated".