One function for addition/subtraction in "Clock arithmetic"/congruent math?

Question

Hi,

I want to "mix" char* data in this form:

source = (source + some_primary_number) % 256;

--the 256 line is because of I need to keep the range of char.

so I can do the "mix" and "un-mix" in 2 functions - the implementation above is for the mixing and this one is for the un-mixing:

source  = source  - some_primary_number;
if ( source  < 0)
{
    source  = 256 + source 
}

This works, of course. But is there any option to do the mixing and un-mixing with the same function?

I remember something fuzzy with congruent math...

Can you help me please? Thanks!

Answer 1

I'm not completely sure this is what you mean, but in general, in modular arithmetic, subtracting a particular x is the same operation as adding m - x, where m is the modulus (here, 256).

So for example if your 'mixing' is adding 47 (mod 256), then 'unmixing' is adding 209 (mod 256), because 209 = 256 - 47.

Answer 2

What kind of mixing are you looking for? What is your intended use of the mixing / un-mixing?

From a pure point of view, if the mixing and un-mixing can be done with the same function and the same primary number, then it means that each output number is paired with exactly one input number.

I can think of XOR with a constant as one example of being its own inverse function.

Linear congruent generator usually require a different un-mixing (inverse) function.

Answer 3

is there any option to do the mixing and un-mixing with the same function?

int foo(int source, int some_primary_number)
{
    return (source + some_primary_number) & 255;
}

To unmix, simply call it with a negative number. Is that what you were asking for?

Answer 4

I'm not sure what you're trying to get at, but I think this may be what you want:

x = ( ((a + b) % M) + M ) % M;

This will compute the common residue of a + b modulo M; it always result in a number [0..M).

It works by first computing (a + b) % M, then + M just in case it's negative, and then % M again.

Answer 5

You seem to want to do arithmetic modulo 256. C and C++ support that with unsigned arithmetic, so if you cast to unsigned char * you can simply do the obvious math.

Answer 6

If you declare source to have type unsigned char, everything should just work. (Or uint8_t if you want to be more explicit about the size, but uint8_t cannot exist on platforms where CHAR_BIT!=8 anyway.)

One possible pitfall is if you'll be using the value of source+blah in an expression without first writing it back into a variable of type unsigned char. In this case, it could very well be outside the range of 0-255 due to integer promotion. If you need to do that, either case the result of the addition back to unsigned char or mask it with &0xff (or equivalently &255).

By the way, don't listen to people who tell you to use % instead of &. Unless you're very careful to make sure the expressions you use with % are of type unsigned int or a larger unsigned type, % will incur an actual division/remainder operation as opposed to just bit masking. People mess that up all the time, thinking the compiler will optimize % by a power of 2 and not realizing that the optimization is impossible for signed types.