How to multiply 2 uint8 modulo a big number without using integer type in C language

Question

If A and B are of type uint8_t and I want the result C=AxB % N where N is 2^16, how do i do this if I can't use integers (so I can't declare N as an integer, only uint8_t) in C language?

N.B: A, B and C are stored in uint8 arrays, so they are "expressed" as uint8 but their values can be bigger.

Why you can't perform calculation as `uint16_t` and then cast result back to `uint8_t`? Especially because `A*B` may be outside `uint8_t` range then... — Adriano Repetti, Jan 22 '16 at 14:26
Will the compiler promote `A` and `B`, or only if they're different types? — Fiddling Bits, Jan 22 '16 at 14:28
You **have to** use integers. *Usual arithmetic conversions* are performed on operands, which means that `uint8_t` types are converted to `int`, whether you want it or not. — user694733, Jan 22 '16 at 14:45
Is the number stored like this? A = 1389 -> `uint8_t A[6] = {0, 0, 1, 3, 8, 9};` ? Or is it like `uint8_t A[6] = {9, 8, 3, 1, 0, 0};` or some other way! If you want help, you need to clarify stuff like that. — Support Ukraine, Jan 22 '16 at 14:49
Please explain *"so they are "expressed" as uint8 but their values can be bigger."*. And also provide [mcve]. — user694733, Jan 22 '16 at 14:50
What I get from you question is `A` and `B` aren't `uint8_t` at all but instead `uint8_t *`. Right? Big difference! — Thomas M. DuBuisson, Jan 22 '16 at 17:38

score 3 · Answer 1 · edited May 23 '17 at 10:30

In general there is no easy way to do this.

Firstly you need to implement the multiply with carry between A and B for each uint8_t block. See the answer here.

Division with 2^16 really mean "disregard" the last 16 bits, "don't use" the last two uint8_t (as you use the array of int.). As you have the modulus operator, this means just the opposite, so you only need to get the last two uint8_ts.

Take the lowest two uint8 of A (say a0 and a1) and B (say b0 and b1):

split each uint8 in high and low part

a0h = a0 >> 4;    ## the same as a0h = a0/16;
a0l = a0 % 16;    ## the same as a0l = a0 & 0x0f;
a1h = a1 >> 4;
a1l = a1 % 16;

b0h = b0 >> 4;
b0l = b0 % 16;
b1h = b1 >> 4;
b1l = b1 % 16;

Multiply the lower parts first (x is a buffer var)

x = a0l * b0l;

The first part of the result is the last four bits of x, let's call it s0l

s0l = x % 16;

The top for bits of x are carry.

c = x>>4;

multiply the higher parts of first uint8 and add carry.

x = (a0h * b0h) + c;

The first part of the result is the last four bits of x, let's call it s0h. And we need to get carry again.

s0h = x % 16;
c = x>>4;

We can now combine the s0:

s0 = (s0h << 4) +  s0l;

Do exactly the same for the s1 (but don't forget to add the carry!):

x = (a1l * b1l) + c;
s1l = x % 16;
c = x>>4;
x = (a1h * b1h) + c;
s1h = x % 16;
c = x>>4;
s1 = (s1h << 4) +  s1l;

Your result at this point is c, s1 and s0 (you need carry for next multiplications eg. s2, s3, s4,). As your formula says %(2^16) you already have your result - s1 and s2. If you have to divide with something else, you should do something similar to the code above, but for division. In this case be careful to catch the dividing with zero, it will give you NAN or something!

You can put A, B, C and S in array and loop it through the indexes to make code cleaner.

Ian Abbott · Answer 2 · 2016-01-22T18:01:08.980

Here's my effort. I took the liberty of using larger integers and pointers for looping through the arrays. The numbers are represented by arrays of uint8_t in big-endian order. All the intermediate results are kept in uint8_t variables. The code could be made more efficient if intermediate results could be stored in wider integer variables!

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

static void add_c(uint8_t *r, size_t len_r, uint8_t x)
{
    uint8_t o;

    while (len_r--) {
        o = r[len_r];
        r[len_r] += x;
        if (o <= r[len_r])
            break;
        x = 1;
    }
}

void multiply(uint8_t *res, size_t len_res,
        const uint8_t *a, size_t len_a, const uint8_t *b, size_t len_b)
{
    size_t ia, ib, ir;

    for (ir = 0; ir < len_res; ir++)
        res[ir] = 0;

    for (ia = 0; ia < len_a && ia < len_res; ia++) {
        uint8_t ah, al, t;

        t = a[len_a - ia - 1];
        ah = t >> 4;
        al = t & 0xf;

        for (ib = 0; ib < len_b && ia + ib < len_res; ib++) {
            uint8_t bh, bl, x, o, c0, c1;

            t = b[len_b - ib - 1];
            bh = t >> 4;
            bl = t & 0xf;

            c0 = al * bl;
            c1 = ah * bh;

            o = c0;
            t = al * bh;
            x = (t & 0xf) << 4;
            c0 += x;
            x = (t >> 4);
            c1 += x;
            if (o > c0)
                c1++;

            o = c0;
            t = ah * bl;
            x = (t & 0xf) << 4;
            c0 += x;
            x = (t >> 4);
            c1 += x;
            if (o > c0)
                c1++;

            add_c(res, len_res - ia - ib, c0);
            add_c(res, len_res - ia - ib - 1, c1);
        }
    }
}

int main(void)
{
    uint8_t a[2] = { 0xee, 0xdd };
    uint8_t b[2] = { 0xcc, 0xbb };
    uint8_t r[4];

    multiply(r, sizeof(r), a, sizeof(a), b, sizeof(b));
    printf("0x%02X%02X * 0x%02X%02X = 0x%02X%02X%02X%02X\n",
            a[0], a[1], b[0], b[1], r[0], r[1], r[2], r[3]);
    return 0;
}

Output:

0xEEDD * 0xCCBB = 0xBF06976F

How to multiply 2 uint8 modulo a big number without using integer type in C language

2 Answers2