vector<char> mit beliebiger groesse um x bit's nach links rotieren

Hi, ich moechte einen byte vector 1 bit nachts links rotieren...die funktion hat noch einen bug...den ich nicht finde:

Ausgabe in Binary:

0000000000000001
0000000000000010
0000000000000100
0000000000001000
0000000000010000
0000000000100000
0000000001000000
0000000010000000
0100000000000000
1000000000000000
0000000000000001
0000000000000010
0000000000000100
0000000000001000
0000000000010000
0000000000100000
0000000001000000
0000000010000000
0100000000000000
1000000000000000

Code:

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <iomanip>
#include <algorithm>
using namespace std;

typedef char BYTE;

void rotate_1bit_left(vector<BYTE> &array) {
    if(array.size() == 0) {
		return;
	}

    BYTE shifted = 0x00;    
    BYTE overflow = (0x80 & array[0]) >> 7;

    for (int i = (array.size() - 1); i >= 0; i--) {	
        shifted = (array[i] << 1) | overflow;
        overflow = (0x80 & array[i]) >> 1;
        array[i] = shifted;
    }
}

void rotate_bits_left(vector<BYTE> &array, unsigned int number_of_bits) {
    for(int i = 0; i < number_of_bits; i++) { 
        rotate_1bit_left(array);
    }
}

string char_to_binary(unsigned char c) {
    string s;
    int x = (int)c;

    do
    {
        s.push_back('0' + (x & 1));
    } while (x >>= 1);

    while(s.size() < 8) { 
        s = s + '0';
    }

    std::reverse(s.begin(), s.end());

    return s;
}

string char_to_hex(unsigned char c) {
    stringstream stream;

	stream << setfill('0') << setw(2) << hex << (int)c;

	return stream.str();
}

string get_hex_string(const vector<BYTE> &vec) {
    string out;

    for(int i = 0; i < vec.size(); i++) {
        out += char_to_hex(vec[i]);
    }

    return out;
}

string get_binary_string(const vector<BYTE> &vec) {
    string out;

    for(int i = 0; i < vec.size(); i++) {
        out += char_to_binary(vec[i]);
    }

    return out;
}

int main() {
	// your code goes here

	vector<BYTE> key = {0x00, 0x01};
	const int number_of_bits = 20;

	for(int i = 0; i < number_of_bits; i++) {
		cout << get_binary_string(key) << endl;

		rotate_bits_left(key, 1); // koennen auch 20 bits sein...das muss dann umgemappt werden, wie gross der vector halt ist...
	}

	return 0;
}

std::rotate ist dein Freund.

rotate(vec.begin()+1, vec.begin(), vec.end()) ... rotiert mir aber 1 byte nach links

volkard

Mein erster Gedanke dazu:
In Zeile 21 shiftest Du um 1 statt um 7.

@volkard: danke...das war der fehler

wie kann ich das mit std::rotate implementieren....wird der code schneller?

algoman1 schrieb:

rotate(vec.begin()+1, vec.begin(), vec.end()) ... rotiert mir aber 1 byte nach links

Richtig wäre rotate(vec.begin(), vec.begin()+1, vec.end())

volkard

algoman1 schrieb:

@volkard: danke...das war der fehler
wie kann ich das mit std::rotate implementieren....wird der code schneller?

Ähm, eigentlich nicht.
std::rotate rotiert byteweise, wie Du schon gesagt hast.
Du willst aber bitweise rotieren.
Das ist, ähm, ja völlig was aderes.

Aber wenn Du Speed brauchst, kannst doch es benutzen!

Mit std::rotate tust Du byteweises Rotieren implementieren.

void rotate_1_bit_left(vector<BYTE> &array);//wie gehabt
void rotate_n_byte_left(vector<BYTE> &array);//mit std::rotate
void rotate_bits_left(vector<BYTE> &array, unsigned int number_of_bits) {
   unsigned int number_of_bytes=number_of_bits/8;
   unsigned int number_of_bits_left=number_of_bits%8;
   rotate_n_byte_left(array,number_of_bytes);
   for(...)
      void rotate_1_bit_left(...);      
}

Damit haste egal um wieviele Bits rotiert werden soll maximal einmal std::rotate und maximal 7-mal rotate_1byte_left, zusammen lineare Laufzeit.

Kannst dann noch, vermute ich, aber dazu gehört ein wenig Anstrengung, aber kriegste sicher hin, auch wenns einen Tag dauert,

void rotate_n_bit_left(array,n)//0<=n<=7

basteln, was nur einmal übers ganzte Array durchläuft. Musst ja nicht <<1 machen, <<n geht ja auch. Entsprechend die Maske anpassen, const unsingend int maske=0xff<<(8-n) oder so. Dann wärst Du mit zwei Durchläufen durchs Array immer bedient, kackegal wie groß oder krumm n ist.

kann man das eventuelle mit sse intrinsic's mit mehr speed implementieren?

volkard

algoman1 schrieb:

kann man das eventuelle mit sse intrinsic's mit mehr speed implementieren?

Auswendig weiß ich es leider nicht. Bei meinen Problemen tut der optimierende Compiler stets SSE so ungeheuer schlau einbauen, daß ich gar keine Chance habe, es per Hand besser zu machen, das Compilat achtet drauf, Register gerade so zu benutzen und zuz belegen, daß möglichst viel parallel passieren kann. Das ist weit jenseits und überlegen des einfachen Takte-Sparens.

Im vorliegenden Fall würde ich zuerst versuchen, den Datentyp größer zu wählen, sagen wie mal unsigned long long statt unsinged char. Und mal schauen, was passiert. Ok, ull ist nur 64-bittig. SSE-Register können mehr. Aber die Befehle drauf sind immer nur für kleine Einheiten. Um damit auf eine ganzes Shift zu kommen, müßte man bestimmt noch ein wenig bit twiddeling betreiben, das frißt die Performance auf, denke ich mal.

Also meine Empfehlung aus dem Bauch heraus: Mit ull kurz drüberhpsen und den Rest schnell kleiner machen.

vector&lt;char&gt; mit beliebiger groesse um x bit's nach links rotieren

vector<char> mit beliebiger groesse um x bit's nach links rotieren