8-bit Bitwise for 64 bit integer

Question

I want to implement bitwise cyclic shift of a 64 bit integer.

ROT(a,b) will move bit at position i to position i+b. (a is the 64 bit integer)

However, my avr processor is an 8-bit processor. Thus, to express a, I have to use unit8_t x[8].

x[0] is the 8 most significant bits of a.
x[7] is the 8 least significant bits of a.

Can any one help to implement ROT(a,b) in term of array x?

Thank you

Is there a specific programming language you want an answer in? Also x[0] has the 8 most significant bits of a, right? — helb
Basically, you can either do this in pieces, or you can see if the compiler will do it for you. Just for laughs I asked avr-gcc to do some operations on a uint64_t and it did not complain - though I'll caution that I haven't actually tested the result. (I guess you would still have to synthesize rotation from shifts.) — Chris Stratton
Thank you all, I want to do it in C. Actually, it is a part of exercise which requires me to transform the code :D. I did give it a try but the result is not correct. — tako
What is i in "ROT(a,b) will move bit at position i to position i+b. (a is the 64 bit integer)"? Don't your need ROT(a,i,b)? — chux - Reinstate Monica

chux - Reinstate Monica chux - Reinstate Monica · Accepted Answer · 2014-04-03T22:32:19

It makes no functional difference if the underlying processor is 64-bit, 8-bit or 1-bit. If the compiler is compliant - you are good to go. Use uint64_t. Code does not "have to use unit8_t" because the processor is an 8-bit one.

uint64_t RPT(uint64_t a, unsigned b) {
  return (a << (b & 63))  |  (a >> ((64 - b) & 63));
}

Extra () added for explicitness.
& 63 (or %64 is you like that style) added to insure only 6 LSBits of b contribute to the shift. Any higher bits simply imply multiple "revolutions" of a circular shift.
((64 - b) & 63) could be simplified to (-b & 63).

--

But if OP still wants "implement ROT(a,b) in term of array unit8_t x[8]":

#include <stdint.h>

// circular left shift.  MSByte in a[0].
void ROT(uint8_t *a, unsigned b) {
  uint8_t dest[8];
  b &= 63;

  // byte shift
  unsigned byte_shift = b / 8;
  for (unsigned i = 0; i < 8; i++) {
    dest[i] = a[(i + byte_shift) & 7];
  }

  b &= 7; // b %= 8;  form bit shift;
  unsigned acc = dest[0] << b;
  for (unsigned i = 8; i-- > 0;) {
    acc >>= 8;
    acc |= (unsigned) dest[i] << b;
    a[i] = (uint8_t) acc;
  }
}

@vlad_tepesch Suggested a solution that emphasizes the AVR 8-bit nature. This is an untested attempt.

void ROT(uint8_t *a, uint8_t b) {
  uint8_t dest[8];
  b &= 63;  // Could be eliminated as following code only uses the 6 LSBits.

  // byte shift
  uint8_t byte_shift = b / 8u;
  for (uint8_t i = 0; i < 8u; i++) {
    dest[i] = a[(i + byte_shift) & 7u];
  }

  b &= 7u; // b %= 8u;  form bit shift;
  uint16_t acc = dest[0] << b;
  for (unsigned i = 8u; i-- > 0;) {
    acc >>= 8u;
    acc |= (uint8_t) dest[i] << b;
    a[i] = (uint8_t) acc;
  }
}

8-bit Bitwise for 64 bit integer

3 Answers