How to add a value greater than 255 to a wide integer (encoded as an array of uint

I want to add a value (potentially larger than 255) to an array of uint8_t. Currently, my implementation does not allow to exceed 255 as the value is of type uint8_t. Ideally I would like to have this value of type int.

This code must be compilable with standard libraries and be exclusively in C99. I don't have access to uint32_t or uint_64t types either. How could I modify the following snippet to change value from uint8t to int ?

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

void addArray(uint8_t *dest, size_t sizeDest, uint8_t value){
    uint8_t remaining = value;
    uint8_t sum;
    for (size_t i = 0; i < sizeDest;   i){
        sum = dest[i]   remaining;
        if (dest[i] > sum){
            remaining -= UINT8_MAX - (dest[i] - sum);
            dest[i]=sum;
        }
        else{
            dest[i]=sum;
            return;
        }
    }
}

void printArray(uint8_t *t, size_t arrayLength){
    for (int i = 0; i < arrayLength;   i)
    {
        printf("%d ", t[i]);
    }
    printf("\n");
}

int main() {
    printf("Max value of uint8_t is %d\n",UINT8_MAX);
    int arrayLength = 16;
    uint8_t key[] = {
        252,255,255,255,255,255,255,255,
        255,255,255,255,255,255,255,2
    };
    uint8_t *testArray = (uint8_t *) malloc(sizeof(uint8_t) * arrayLength);
    memcpy(testArray, key, sizeof(uint8_t)*arrayLength);
    printf("Before addition\n");
    printArray(testArray, arrayLength);
    addArray(testArray,arrayLength,15);
    printf("After addition\n");
    printArray(testArray, arrayLength);
    return 0;
}

CodePudding user response：

How to add a value greater than 255 to an array of uint_8t?

" Ideally I would like to have this value of type int. " --> As the goal is "a value greater than 255", we can simplify and use unsigned.

Add the unsigned to the uint8_t indexed in the array. As overflow may occur, use wider than unsigned math.

// Return overflow amount
// void addArray(uint8_t *dest, size_t sizeDest, uint8_t value){
unsigned addArray(uint8_t *dest, size_t sizeDest, unsigned value){
  unsigned long long sum = value; // Use some type wider than unsigned
  for (size_t i = 0; i < sizeDest;   i) {
    sum  = dest[i];               
    dest[i] = (uint8_t) sum;      // Save 8 lower bits
    sum >>= 8;                    // Continue with the upper bits
  }
  return (unsigned) sum;
}

... or more like OP's code with no wider integer math used.

unsigned addArray(uint8_t *dest, size_t sizeDest, unsigned value){
    #define UINT_MAX_PLUS1_DIV256 ((UINT_MAX - UINT_MAX/2) >> 7)
    unsigned remaining = value;
    for (size_t i = 0; i < sizeDest;   i) {
        unsigned sum = remaining   dest[i];
        dest[i] = sum;   // Save lower bits
        if (sum < remaining) {  // Overflow occurred in remaining   dest[i]
            remaining = sum >> 8;
            remaining  = UINT_MAX_PLUS1_DIV256 // add back overflow bit / 256
        } else{
            remaining = sum >> 8; // Continue with the upper bits 
        } 
    }
    return remaining
}

CodePudding user response：

You say you're not allowed to use uint32_t or uint64_t, but you are allowed to use int. If so, this is simple enough. Just use int to pass in your new value and to keep track of the partial, running sum.

I did it like this; it's quite similar to the code @chux posted. I also simplified the logic: you don't actually need to keep separate sum and remaining values, so I boiled it down to just one variable, which I'm calling carry, of type int.

void addArray(uint8_t *dest, size_t sizeDest, int value){
    int carry = value;
    for (size_t i = 0; i < sizeDest;   i){
        carry = dest[i]   carry;
        dest[i] = carry & 0xff;
        carry >>= 8;
    }
}

During each trip through the loop, carry is either the value we're adding in, or the carry that's leftover from the previous "digit". We add the carry to the current digit, stash as much of it as will fit — the low-order 8 bits — back into the current digit, and keep what's leftover (that is, after using >>= to discard the low-order 8 bits, which are they ones we've just stored in dest[i]) in the carry variable for next time.

Why does this work? Well, it's the same thing you do when you add a column of numbers by hand, using the technique we all learned back in elementary school. Suppose you're adding

After you add up the one's column, you get 27, and you say, "okay, that's 7, carry the 2". (You do not say, "carry the 20".) Your partial sum was 27, and the "bottom half" of it (7, or 27 % 10) is the digit in the one's place of the final sum, and the "top half" (2, or 27 / 10) is the carry into the ten's column.

So if you're not familiar or not comfortable with those "bitwise" operators, you can perform the equivalent operations using % and /, except using factors of 256 instead of 10:

void addArray(uint8_t *dest, size_t sizeDest, int value){
    int carry = value;
    for (size_t i = 0; i < sizeDest;   i){
        carry = dest[i]   carry;
        dest[i] = carry % 256;
        carry /= 256;
    }
}

Basically you're performing addition here in base 256.

Depending on your needs and constraints, there might be some value in using types int16_t, unsigned int, or uint16_t for value and carry, instead of plain int.

I tested this by calling

addArray(testArray,arrayLength,300);

and it printed

Before addition
252 255 255 255 255 255 255 255 255 255 255 255 255 255 255   2 
After addition
 40   1   0   0   0   0   0   0   0   0   0   0   0   0   0   3

which looks right. As a second test,

addArray(testArray,arrayLength,123456789);

prints

After addition
 17 205  91   7   0   0   0   0   0   0   0   0   0   0   0   3

(More on these tests in the "addendum" below.)

As @chux points out in a comment, this code does have its limitations. If the value you tried to add in was close to the maximum an int can hold, the carry variable might overflow (that is, on the carry = dest[i] carry line). But as long as value is less than or equal to INT_MAX - 255 (and greater than or equal to zero!), you should be fine.

Of course, if the value you're trying to add in might be large, it might also be larger than a single int can hold, in which case you'd need to pass it in some other way, likely as a second array of uint8_t, just like dest — and then you'd find yourself writing a fully general multiprecision adder.

Addendum: To double-check these results, and to demonstrate what's actually going on, we can perform the same arithmetic in dc, the Unix/Linux arbitrary-precision calculator. I have determined that @Tifa's initial key value is 3987683987354747618711421180841033724. We'll use dc to print that number out in various bases, and as we add 15, 300, and 123456789 to it.

$ dc
3987683987354747618711421180841033724       # original key
p                                           # print it
3987683987354747618711421180841033724
16o p                                       # set output base to 16 and print
2FFFFFFFFFFFFFFFFFFFFFFFFFFFFFC
256o p                                      # set output base to 256 and print
 002 255 255 255 255 255 255 255 255 255 255 255 255 255 255 252
15   p                                      # add 15 and print (still base 256)
 003 000 000 000 000 000 000 000 000 000 000 000 000 000 000 011
3987683987354747618711421180841033724       # original key again
300   p                                     # add 300 and print
 003 000 000 000 000 000 000 000 000 000 000 000 000 000 001 040
3987683987354747618711421180841033724       # original key again
123456789   p                               # add and print
 003 000 000 000 000 000 000 000 000 000 000 000 007 091 205 017

dc's base-256 rendition corresponds to the output of Tifa's printArray function, albeit in a more conventional left-to-right order.