CODEWITHSUNDEEP
cbit-manipulationavr
tako
tako

Reputation: 11

8-bit Bitwise for 64 bit integer

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].

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

Thank you

Upvotes: 1

Views: 1517

Answers (3)

chux
chux

Reputation: 154322

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;
  }
}

Upvotes: 3

vlad_tepesch
vlad_tepesch

Reputation: 6925

why do not leave the work to the compiler and just implement a function

uint64_t rotL(uint64_t v, uint8_t r){
  return  (v>>(64-r)) | (v<<r)
}

Upvotes: 1

Mahmoud Tighiouart
Mahmoud Tighiouart

Reputation: 1

I take it the x(i) are 8 bits. To rotate left n times each bit from X(i,j) where i is the index array x(0) -> x(7) and j is the bit position within the element

then this bit will end up in Y((i+n)/8, ( i+n) & 7 ) This will handle rotations up to 63 any number > 63 , you just mod it.

Upvotes: 0

Related Questions