Permutations on binary strings

[ruben.de.visscher]

I am trying to write a program that encrypts 8-bit plaintext using a
10-bit key. To generate subkeys, and for other things, i will need to
be able to perform permutations on binary strings for example:

if k1k2k3k4k5k6k7k8k9k10 represents all ten digits of the key, the
outpur of the permutation should be like this:
k3k5k2k7k4k10k1k9k8k6 .

I am new to operations on binary strings and i don't really know how to
implement this as efficient as possible...

 

[Michael Mair]

I am trying to write a program that encrypts 8-bit plaintext using a
10-bit key. To generate subkeys, and for other things, i will need to
be able to perform permutations on binary strings for example:

if k1k2k3k4k5k6k7k8k9k10 represents all ten digits of the key, the
outpur of the permutation should be like this:
k3k5k2k7k4k10k1k9k8k6 .

I am new to operations on binary strings and i don't really know how to
implement this as efficient as possible...

Then don't.

Implement it in a way you can understand, even if _seems_ terribly
slow to you. If you are sure you want to replace the respective
portions of the code later on, wrap repeating tasks in functions
or macros.
Afterwards, have a look at whether this is really terribly slow or
maybe fast enough. Do not try to go for the "most clever" variant
first. If you keep it simple enough, the compiler may even optimise
it better than you ever can using "clever" constructs.

Notes on working with bits:
- typical macros to work bitwise:
#define IS_BIT_SET(src, bit) ((src) & (1UL<<(bit)))
#define SET_BIT(src,bit) ((src) |= (1UL<<(bit)))
#define UNSET_BIT(src,bit) ((src) &= ~(1UL<<(bit)))
- Work with unsigned types.
- Beware of integer promotions to signed types.
- Similarly: Make sure to have the left operand of << to be of
the desired "destination" type


Cheers
Michael

 

[Walter Roberson]

I am trying to write a program that encrypts 8-bit plaintext using a
10-bit key. To generate subkeys, and for other things, i will need to
be able to perform permutations on binary strings for example:

if k1k2k3k4k5k6k7k8k9k10 represents all ten digits of the key, the
outpur of the permutation should be like this:
k3k5k2k7k4k10k1k9k8k6 .

I am new to operations on binary strings and i don't really know how to
implement this as efficient as possible...

Really there are two distinct questions involved:
1) What is an efficient permutation algorithm; and
2) How do you work with individual bits

Efficient permutation algorithms are not generally considered
to be within the scope of this newsgroup -- but if I recall
correctly, then if you search the comp.lang.c newsgroup archives
(e.g., via google groups) then you will find some good permutation
algorithms (or references to such.)


With regards to working with bits:

You numbered the bits from MSB (Most Significant Bit) to LSB (Least
Significant Bit). Most often the bit order is numbered the other way
around and starts from 0, but people disagree about the "right" ordering --
and the ordering doesn't matter as long as you are consistant with
yourself and that if the ordering is visible to the users, that your
user interface makes it clear what the numbering system is.


The "key" that you are using, 10 bits long, is not a particularily
common size of byte, so you will need to embed the 10 bit key within a
wider integral type such as short (less space) or int (more natural for
arithmetic operations.) When you do that embedding, you need to decide
where the 10 bits are to be packed in the wider type -- left end (MSB
of the key at the MSB of the wider type), right end (LSB of the
key at the LSB of the wider type), or something else.

I would suggest to you that packing at the "right" end is
easier to deal with: that saves a lot of messiness about having
to know exactly how big the wider type is; and is
preserves interpretation of values if the word you are working with
happens to get promoted to a wider type yet.

If you pack at the "right" side of the wider type, and if you
use the numbering scheme you give (first bit is #1), then for
a W-bit wide quantity, you have the following:

#define SET_ON_BIT_N(x, W, N) (x | 1<<(W-N))
#define SET_OFF_BIT_N(x, W, N) (x & ~ 1<<(W-N))
#define GET_BIT_N(x, W, N) ((x & 1<<(W-N)) >> (W-N))
#define SET_BIT_N(x, W, N, s) (s ? SET_ON_BIT10_N(x, W, N) : \
SET_OFF_BIT10_N(x, W, N) )

If you want, you could define things like

#define SET_OFF_BIT10_N(x, N) SET_OFF_BIT_N(x, 10, N)

if you are going to always be using 10-bit wide keys.


You may notice that the code would simplify if you were numbering
the other way around, bit 9 as the first bit and bit 0 as the last.

 

[Michael Mair]

Really there are two distinct questions involved:
1) What is an efficient permutation algorithm; and
2) How do you work with individual bits

Efficient permutation algorithms are not generally considered
to be within the scope of this newsgroup -- but if I recall
correctly, then if you search the comp.lang.c newsgroup archives
(e.g., via google groups) then you will find some good permutation
algorithms (or references to such.)


With regards to working with bits:

You numbered the bits from MSB (Most Significant Bit) to LSB (Least
Significant Bit). Most often the bit order is numbered the other way
around and starts from 0, but people disagree about the "right" ordering --
and the ordering doesn't matter as long as you are consistant with
yourself and that if the ordering is visible to the users, that your
user interface makes it clear what the numbering system is.


The "key" that you are using, 10 bits long, is not a particularily
common size of byte, so you will need to embed the 10 bit key within a
wider integral type such as short (less space) or int (more natural for
arithmetic operations.) When you do that embedding, you need to decide
where the 10 bits are to be packed in the wider type -- left end (MSB
of the key at the MSB of the wider type), right end (LSB of the
key at the LSB of the wider type), or something else.

Note: Working with a signed type and bits requires extra care.
So I would rather suggest unsigned integer types.

I would suggest to you that packing at the "right" end is
easier to deal with: that saves a lot of messiness about having
to know exactly how big the wider type is; and is
preserves interpretation of values if the word you are working with
happens to get promoted to a wider type yet.

If you pack at the "right" side of the wider type, and if you
use the numbering scheme you give (first bit is #1), then for
a W-bit wide quantity, you have the following:

#define SET_ON_BIT_N(x, W, N) (x | 1<<(W-N))
#define SET_OFF_BIT_N(x, W, N) (x & ~ 1<<(W-N))
#define GET_BIT_N(x, W, N) ((x & 1<<(W-N)) >> (W-N))
#define SET_BIT_N(x, W, N, s) (s ? SET_ON_BIT10_N(x, W, N) : \
SET_OFF_BIT10_N(x, W, N) )

Caveat: This can easily break as you neglected putting
parentheses wherever appropriate/applicable.
Apart from that, I prefer 1UL/1L as left hand side argument to
<< to make sure that I am on the safe side. (Undefined behaviour
by shifting by 16 or more for 16-bit-ints is easily avoided by
this.)
If x is signed and we have arithmetical right shift, your
GET_BIT_N macro does not work as intended. First >> then mask.
In SET_BIT_N(x, W, N, s) you used SET_ON_BIT10_N/SET_OFF_BIT10_N
instead of SET_ON_BIT_N/SET_OFF_BIT_N as probably intended.

BTW: I would not really go about the above in that way;
W does not really introduce something new and useful, so I would
rather define two macros:

#define SET_ON_BIT_N(x, N) ((x) | 1<<(N))
#define SET_ON_BIT_W_N(x, W, N) SET_ON_BIT_N(x,(W)-(N))

If you want, you could define things like

#define SET_OFF_BIT10_N(x, N) SET_OFF_BIT_N(x, 10, N)

if you are going to always be using 10-bit wide keys.


You may notice that the code would simplify if you were numbering
the other way around, bit 9 as the first bit and bit 0 as the last.

Cheers
Michael