[mittelbis schwer] Bits effizient rotieren

[CDW]

Eingereich von Shalec (samt Beispiel):


#####
Zunächst arbeiten wir mit unsigned integern und wollen einen beliebig langen Array diesen Datentyps um n-Bits Shiften bzw. rotieren.
Da das Shiften/Rotieren schnell und einfach programmiert werden kann, besteht folgende weitere Schwierigkeit: The most efficient way!

Gebt dazu die Hardwarearchitektur und ausgenutzte Operationen an (falls notwendig) und den Code.
Implementiert auch die Tiks/Cycle Analysemethode.

Ein kurzes Beispiel (Natürlich nicht most efficient) und ohne Cycleanalyse.

/*
der Code wurde von mir etwas umgestaltet und vereinfacht
CDW 
*/
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>


#define N 22

typedef uint32_t array[N];

void lshift(array A, uint8_t k){
    if (sizeof(A[0]) * CHAR_BIT <= k) {
	fpurge(stdout);
	fprintf(stderr, "Lshift not implemented for k >= %zu \n",
			sizeof(A[0]) * CHAR_BIT);
	exit(EXIT_FAILURE);
    }

    for(size_t i=0; i < N-1; ++i){
	A[i] = (uint32_t) ((A[i] << k) | (A[i+1] >> (32-k)) );
    }
    A[N-1] = (uint32_t) (A[N-1] << k);
}


void dump_array(array A, char* fmt) {
    for (size_t i = 0; i < N; ++i) {
	printf(fmt, A[i]);
    }
}


int main(){
    array A = {
	0xc22b4d0c, 0x4054bfb9, 0x1a0830ab, 0xb0a8771f, 0xd0d90c56, 0x58652c7f,
	0x60b79d15, 0x35dd1ddd, 0xea2b70bc, 0x52131a21, 0x1930f, 0xc22b4d0c,
	0x4054bfb9, 0x1a0830ab, 0xb0a8771f, 0xd0d90c56, 0x58652c7f, 0x60b79d15,
	0x35dd1ddd, 0xea2b70bc, 0x52131a21, 0x1930f
    };

    uint8_t bits_to_shift = 12;

    puts("Input:\n");
    dump_array(A, "%08X ");
    lshift(A, bits_to_shift);
    printf("\nafter lshift(%u):\n", bits_to_shift);
    dump_array(A, "%08X ");
    return EXIT_SUCCESS;
}

Ausgabe:

Input:

C22B4D0C 4054BFB9 1A0830AB B0A8771F D0D90C56 58652C7F 60B79D15 35DD1DDD EA2B70BC 52131A21 0001930F C22B4D0C 4054BFB9 1A0830AB B0A8771F D0D90C56 58652C7F 60B79D15 35DD1DDD EA2B70BC 52131A21 0001930F 
after lshift(12):
B4D0C405 4BFB91A0 830ABB0A 8771FD0D 90C56586 52C7F60B 79D1535D D1DDDEA2 B70BC521 31A21000 1930FC22 B4D0C405 4BFB91A0 830ABB0A 8771FD0D 90C56586 52C7F60B 79D1535D D1DDDEA2 B70BC521 31A21000 1930F000

 

[Shalec]

Dann mache ich mal den Anfang.

Plattform: ARM-Cortex M4.

Ausgenutzt habe ich nur die Register und den separaten Quarz, der mit 8 MHz schwingt, um die Cycles zu messen. Damit gemessen wird, muss ich den Compiler überlisten (t+=..) und (return t==..)
Wenn den Code jemand ausführen möchte: Dieser muss print_float entsprechend über USART definieren.

Ich komme damit auf 93 Cycles bei n=11. Darstellung: A[10] . A[9] ... A[0]. Leftshift.

Spoiler: Cortex M4, Code in C

#include <stdio.h>
#include <stdint.h>
#include <string.h>

/*****************
 *** Variables ***
 *****************/

#define n 11
#define shifts 12
#define TESTS 1000


/*************************
 *** Cycle Measurement ***
 *************************/
#define start_timer()    *((volatile uint32_t*)0xE0001000) = 0x40000001  
#define stop_timer()   *((volatile uint32_t*)0xE0001000) = 0x40000000  
#define get_timer()   *((volatile uint32_t*)0xE0001004)  
 
/*************************
 ****** The Function *****
 *************************/
 void leftshift(uint32_t* A, uint32_t bits_to_shift)
{	/* Leftshifting the whole array A by "glue_el" bits.
	*/
	int j = n;
	bits_to_shift &= 31;        // mod 32
	
	while(j-- >1)
	{
		A[j] = (uint32_t) ((A[j] << bits_to_shift) | (A[j-1] >> (-bits_to_shift & 31)));
	}
	A[0] <<= bits_to_shift;
}

/*************************
 ***** Main and Call *****
 *************************/

int check()
{
    uint32_t 	
        A[n] = {0xc1132657, 0x034d505e, 0x1fe97257, 0xa01702ae, 0xc20e847d, 0x3ec4cc5a,
                0xcce0a723, 0xec61ef0f, 0x3b3f2cba, 0x832e34e3, 0x00045de1},
        C[n] = {0x32657000, 0xD505EC11, 0x97257034, 0x702AE1FE, 0xE847DA01, 0x4CC5AC20,
                0x0A7233EC, 0x1EF0FCCE, 0xF2CBAEC6, 0xE34E33B3, 0x45DE1832};
    uint64_t c1, all1=0, all2=0, t=0;
	
	float c2;
	
	uint32_t j=TESTS;   
    
    start_timer();
    while(j-- > 1)
    {
    	c1 = get_timer();
    	leftshift(A, shifts);
    	all1 += get_timer() - c1;
    	
    	t += (memcmp(A,C,44)==0);
    }
    stop_timer();
	
	c2 = (float) all1/TESTS;
	print_float(c2);
	return (t==TESTS);
}

int main()
{
    return check();
}

EDIT: Ich bin aber der Meinung, dass diese Operationen signifikant günstiger gehen sollten. Auf dem Cortex kostet ein Shift (egal welche Richtung) 1 Cycle. Das logische verodern ebenfalls. Also kostet jede Zeile "shift, oder shift" drei Cycles. Das macht in der Summe 33. Jetzt kommen noch das Schreiben in den Speicher und andere Elemente hinzu, die ebene diese große Differenz ausmachen. Ich werde diesen Shift wohl auch mal in ASM schreiben.