Encoding number through editing last bit of array elements

Question

I'm trying to write a simple encoding program in C and I definitely have something wrong with my bitwise operations so I tried to write a simplified version to fix that mistake - so far it's still not working. I have an encoding and decoding method where, given a "key" I encode one number by hiding bits of it in a large array of unsigned ints.

I hide it by using srand(key) (so that I can generate the same numbers afterword with the same key) choosing array elements and then taking one bit of number (iterating through all) and swapping the least significant bit of array element for the bit coming through the number.

In decode method I try to reverse the steps, get all the bits from array elements back and glue them together to get back the original number.

That's the code I have so far:

    unsigned int * encode(unsigned int * original_array, char * message, unsigned int mSize, unsigned int secret) {//disregard message, that's the later part, for now just encoding mSize - size of message

    int size = MAX; //amount of elementas in array, max defined at top
    int i, j, tmp;
    unsigned int *array;


    srand(secret); //seed rand with the given key

    array = (unsigned int *)malloc(MAX*sizeof(unsigned int));
    //copy to array from im
    for (i=0; i<MAX; i++){
        array[i] = original_array[i];
    }

    //encode message length first. it's a unsigned int therefore it's size is 4 bytes - 32 bits.

    for (i=0; i<32; i++){
        tmp = rand() % size;
        if (((mSize >> i) & 1)==1) //check if the bit is 1
            array[tmp] = (1 << 0) | array[tmp]; // then write 1 as last bit 
        else //else bit is 0
            array[tmp] = array[tmp] & (~(1 << 0)); //write 0 as last bit 

    }

    return array;
}

unsigned int decode(unsigned int * im, unsigned int secret) {
    char * message;
    int i, tmp;
    unsigned int result = 2;
    int size = MAX;


    srand(secret);
    for (i=0; i<32; i++){
        tmp = rand() % size;
        if (((im[tmp] << 0) & 1)==1)
            result = (1 >> i) | result;
        else
            result = result & (~(1 >> i));
        }//last 

    return result;
}

However running it and trying to print decoded result will give me 2, which is the dummy value I gave to result in decode() -therefore I know that at least my method of recovering the changed bits is clearly not working. Unfortunately since decoding is not working, I have no idea if encoding actually works and I can't seem to pinpoint the mistake.

I'm trying to understand how the hiding of such bits works since, ultimately, I want to hide entire message in a slightly more complicated structure then array, but first I wanted to get it working on a simpler level since I have troubles working with bitwise operators.

Edit: Through some debugging I think the encoding function works correctly - or at least does seem to change the array elements by one sometimes which would indicate flipping one bit if conditions are met. Decoding doesn't seem to affect result variable at all - it doesn't change thgoughour all the bitwise operations and I don't know why.

Answer 1

The main bit of the encode function is the following which is same as your original just tidied it up a little by removing the uncessary 0 shifts and brackets:

//encode message length first. it's a unsigned int therefore it's size is 4 bytes - 32 bits.
for (i=0; i<32; i++){
    tmp = rand() % size;
    if (((mSize >> i) & 1)==1) //check if the bit is 1
        array[tmp] |= 1; // then write 1 as last bit 
    else //else bit is 0
        array[tmp] &= ~1; //write 0 as last bit 
}

The problem you have is when you either set the last bit to 1 or 0 then you effectively lose information. There is no way of telling what the original last bit was. And so you will not be able to decode or reverse it.

In short the decode function will never work. As the encode function is not invertible.

EDIT

Following on from your comment. I would say the following about the decode function (again tidied up this should be the same as the original):

unsigned int decode(unsigned int * im, unsigned int secret) {
    char * message;
    int i, tmp;
    unsigned int result = 2;
    int size = MAX;


    srand(secret);
    for (i=0; i<32; i++){
        tmp = rand() % size;
        if ((im[tmp] & 1)==1)
            result |= 1 >> i;
        else
            result &= ~(1 >> i);
        }//last 

    return result;
}

The thing to note here is that for all values of i > 0 the following will apply:

1 >> i

is the same as

0

This means that for majority of your loop the code will be doing the following

if ((im[tmp] & 1)==1)
    result |= 0;
else
    result &= ~0;

And since 2 = 2 | 0 and 2 = 2 & ~0 then regardless of which branch of the if is executed the result will always be 2. This would be the same for any even number.

When i = 0 then the following is the case:

if ((im[tmp] & 1)==1)
    result |= 1;
else
    result &= ~1;

And so since 2 | 1 = 3 and 2 & ~1 = 2 your decode function will only ever return 2 or occasionally 3.