bitweises kopieren -> triviales(?) problem eigentlich...

dettus

Bicycle User
aaaargh!

leute, helft mir.

ich hab mal wieder ein triviales problem, an dem ich schlicht am verzweifeln bin...
folgendes:

ich habe zwei arrays von charactern
Code:
unsigned char c[1024];
unsigned char d[1024];

und jetzt brauche ich eine funktion, die n bits von bit x aus c nach bit y aus d kopiert.

fuer x,y,n mod 8=0 ist das also

Code:
memcpy(d+y/8,c+x/8,n/8);

kein problem. irgendwie wollen aber die anderen faelle nicht in meine birne rein!
oh, ja, die bitreihenfolge ist big endian.

die naive loesung sieht so aus:
Code:
#include <stdio.h>
#include <stdlib.h>


int main(void)
{
        unsigned char z;
        unsigned char b;
        unsigned char c[10]={0x80,0x80,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00};
        unsigned char d[10]={0x80,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00};
        unsigned int x=3;
        unsigned int y=1;
        unsigned int n=9;
        unsigned int i;

        printf("in>  c:");
        for (i=0;i<10;i++) printf("%02x ",c[i]);
        printf("\n");
        printf("in>  d:");
        for (i=0;i<10;i++) printf("%02x ",d[i]);
        printf("\n");

        z=d[y/8]>>(8-(y%8));
        while (n)
        {
                b=(c[x/8]>>(7-x%8))&0x1;
                z=(z<<1)|b;
                x++;
                y++;
                if ((y%8)==0) {
                        d[y/8-1]=z;
                        z=0;
                }
                n--;
        }
        z<<=(8-(y%8));
        d[y/8]=z;
        printf("out> d:");
        for (i=0;i<10;i++) printf("%02x ",d[i]);
        printf("\n");
}



auf jeden fall muss das doch auch irgendwie schneller gehen!

kann mir irgendwer bei dem uebergang bit->byte helfen?
 
Last edited:
Du musst halt mit Bitmasken arbeiten. Das ist viel gefummel, aber es geht. Hier ist eine sehr einfache Lösung in Pseudo Code, die Bit für Bit vorgeht. Man könnte auch schnellere basteln, die sind aber deutlich aufwändiger.

Code:
byte[] moveBits(byte[] source, byte[] target, int from, int to, int length) {
    while (length > 0) {
        int sourceIndex = from / 8;
        int targetIndex = to / 8;
        int sourceBit = from mod 8;
        int targetBit = to mod 8;

        byte currentBit = ((source[sourceIndex] << sourceBit) AND 0x01) >> targetBit;
        byte currentBitMask = (2 ^ targetBit) XOR 0xFF;
        target[targetIndex] = target[targetIndex] AND currentBitMask OR currentBit;

        from++;
        to++;
        length--;
    }
    return target;
}
 
Last edited:
danke.

oehm...

das ist aber wieder das gleiche wie oben.
ich braeuchte da etwas, bei dem der length=length-8 rechnet.
er also die einzelnen bits en block als byte verpackt kopiert.
 
Das ist ziemlich aufwendig, vor allem wenn der Bit Offset sich in Source und Target unterscheiden, weil du dann jedes byte auf 2 andere verteilen musst. Du musst also mit 'ner Menge Bitmasken und rumgeshifte spielen.
Kurz gesagt es ist ein ziemliches Gefrickel, das ich nur auf mich nehmen würde, wenn die Funktion zum Flaschenhals wird.

Wenn du Variablen aussagekräftige Namen, statt x, y, z gibst, erhöht das für mich die Bereitschaft den Versuch zu unternehmen deinen Code zu verstehen.
 
[LoN]Kamikaze said:
Das ist ziemlich aufwendig, vor allem wenn der Bit Offset sich in Source und Target unterscheiden, weil du dann jedes byte auf 2 andere verteilen musst. Du musst also mit 'ner Menge Bitmasken und rumgeshifte spielen.
Kurz gesagt es ist ein ziemliches Gefrickel, das ich nur auf mich nehmen würde, wenn die Funktion zum Flaschenhals wird.
lol.
du hast mein problem erkannt ;-)

das ganze wird hinterher eine hardwareimplementierung, in einem takt schafft der ALLES, was in einer while-schleife ausgefuehrt wird. das darf also ruhig etwas komplexer werden.
was reduziert werden MUSS ist die anzahl, wie oft die schleife durchlaufen wird. weil das ding nachher nur auf 12mhz rennt.

Wenn du Variablen aussagekräftige Namen, statt x, y, z gibst, erhöht das für mich die Bereitschaft den Versuch zu unternehmen deinen Code zu verstehen.

goodie!

okay:

Code:
#include <stdio.h>
#include <stdlib.h>


int main(void)
{
        unsigned char z;
        unsigned char b;
        unsigned char source[10]={0x80,0x80,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00};
        unsigned char dest[10]={0x80,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00};
        unsigned int sourcebit=3;
        unsigned int destbitt=1;
        unsigned int bitstocopy=9;
        unsigned int i;

        printf("in>  sour:");
        for (i=0;i<10;i++) printf("%02x ",source[i]);
        printf("\n");
        printf("in>  dest:");
        for (i=0;i<10;i++) printf("%02x ",dest[i]);
        printf("\n");

        z=dest[destbit/8]>>(8-(destbit%8));
        while (bitstocopy)
        {
                b=(source[sourcebit/8]>>(7-sourcebit%8))&0x01; // hier holt er sich ein bit aus dem source
                z=(z<<1)|b;
                sourcebit++;
                destbit++;
                if ((destbit%8)==0) {
                        dest[destbit/8-1]=z;
                        z=0;
                }
                bitstocopy--;
        }
        z<<=(8-(destbit%8));
        dest[destbit/8]=z;
        printf("out> dest:");
        for (i=0;i<10;i++) printf("%02x ",dest[i]);
        printf("\n");
}

p.s.: keine angst, ich arbeite auch gerade dran, aber ich dachte dass vielleicht jemand schneller sein koennte als ich *ggg*
 
Last edited:
Hallo,

nur so ne fixe Idee:

Wenn Du das erste und letzte Byte, das manipuliert wird gesondert behandelst, kannst Du den Rest vielleicht über eine 2 Byte Variable verschieben;

1. die Offsetdifferenz (osd) der Startbits eines Byte bestimmen

2. die 2Byte (buf) Variable mit den ersten zu übertragenden Bytes des Quell-Puffers füllen

3. den Inhalt von buf um osd Bits verschieben

4. das untere Byte von buf in den Ziel-Puffer kopieren

5. Prüfen, ob noch mehr bytes übertragen werden müssen

6. den Inhalt von buf um (8-osd) verschieben und das nächste Byte aus dem Quell-Puffer in das höhere Byte von buf kopieren und zu 3. gehen



Ciao
PhysChemist
 
Hallo dettus,

wenn ich dich richtig verstanden habe, dann ist dein Problem, dass die while-Schleife möglichst wenig Durchläufe haben sollte. Damit man das erreichen kann, muss man ja von der bitweisen Verarbeitung weg. Der Vorschlag, das ganze charweise zu machen, wurde ja bereits genannt. Ich schätze mal, dass du auch nicht einfach auf eine andere Größe wechseln kannst, daher mal mein Vorschlag:

Code:
#include <stdio.h>
#include <stdlib.h>

int
max(int a, int b)
{
	if (a > b)
		return a;
	return b;
}

int
main(void)
{
	unsigned char source[] = {0x00, 0x00, 0x07, 0x80, 0x00};
	unsigned char dest[] = {0x00, 0x00, 0x00, 0x00, 0x00};

	int i;
	int diff, nbits, written;
	int dest_offset, source_offset;
	int dest_block_offset, source_block_offset;

	unsigned char dest_block, source_block;
	unsigned char mask;

	nbits = 4;
	dest_offset = 18;
	source_offset = 20;

	printf("in>  sour:");
	for (i = 0; i < 5; i++)
		printf("%02x ", source[i]);
	printf("\nin>  dest:");
	for (i = 0; i < 5; i++)
		printf("%02x ", dest[i]);
	puts("");

	while (nbits) {
		/* Variablen vorbereiten */
		source_block = source[source_offset / 8];
		source_block_offset = source_offset % 8;

		dest_block = dest[dest_offset / 8];
		dest_block_offset = dest_offset % 8;

		mask = 0xff;

		/*
	 	* Zuerst werden alle unnötigen Bits in source_block auf
	 	* 0 gesetzt, damit sie bei späteren Operationen nicht weiter
	 	* stören.
	 	*
	 	* Hierbei wird auch gleich die Maske für dest_block
	 	* vorbereitet.
	 	*/

		/* Alles auf der linken Seite vom Offset auf 0 */
		source_block <<= source_block_offset;
		source_block >>= source_block_offset;

		mask <<= source_block_offset;
		mask >>= source_block_offset;

		/* Falls auf der rechten Seite unnötige Bits sind, diese auch */
		if (nbits < 8 - source_block_offset) {
			source_block >>= (8 - source_block_offset - nbits);
			source_block <<= (8 - source_block_offset - nbits);

			mask >>= (8 - source_block_offset - nbits);
			mask <<= (8 - source_block_offset - nbits);
		}

		/*
	 	* Als nächstes werden die Bits nun an die richtige Position
	 	* geschoben, so dass sie in das Zielchar eingebunden werden
	 	* können.
	 	*/
		if (source_block_offset > dest_block_offset) {
			source_block <<= (source_block_offset - dest_block_offset);
			mask <<= (source_block_offset - dest_block_offset);
		}
		else {
			source_block >>= (dest_block_offset - source_block_offset);
			mask >>= (dest_block_offset - source_block_offset);
		}

		/* Die Maske muss noch invertiert werden */
		mask ^= 0xff;

		/*
	 	* Nun werden die Bits geschrieben. Die Maske sorgt dafür, dass
	 	* das logische ODER keine 1-Bits aus dem dest_block übernimmt,
	 	* wenn im Quellblock eine 0 vorgesehen ist.
	 	*/
		dest_block &= mask;
		dest_block |= source_block;
		dest[dest_offset / 8] = dest_block;

		/*
	 	* Nun muss noch überprüft werden, wie viele Bits geschrieben
	 	* wurden. Daraufhin noch die Offsets anpassen und das ganze
	 	* wiederholen.
	 	*/
		written = 8 - max(source_block_offset, dest_block_offset);
		if (nbits > written) {
			nbits -= written;
			source_offset += written;
			dest_offset += written;
		}
		else
			nbits = 0;
	}

	printf("in>  sour:");
	for (i = 0; i < 5; i++)
		printf("%02x ", source[i]);
	printf("\nin>  dest:");
	for (i = 0; i < 5; i++)
		printf("%02x ", dest[i]);
	puts("");

	return 0;
}

Das ganze baut darauf auf, dass man die Chars als Blöcke betrachtet. Diese werden dann noch "zurechtgeschnitten" und auf den anderen gelegt.

Ich hab das Programm jetzt nicht ausführlich getestet, ich hoffe aber, dass insbesondere die Kommentarblöcke dir 'ne Idee geben, wie ich mir das vorgestellt habe.
 
Last edited:
schade! da ist noch ein kleiner fehler drinne....
aber sonst schon ganz okay...

mit
Code:
        nbits = 5;
        dest_offset = 0;
        source_offset =20;

lautet das ergebnis
Code:
70 00 00 00
statt
Code:
78 00 00 00

p.s.: "die maske muss noch invertiert werden" geht auch mit einem
Code:
mask^=0xff;
;-)
 
Haha, danke für die Hilfe. :D

Das Problem ist noch mit dem letzten Schritt (gucken, wie viele Bits geschrieben wurden).

Code:
nbits -= 8 - source_block_offset + 1;
und
Code:
nbits -= 8 - dest_block_offset + 1;

Das "+ 1" muss da weg. Ich probier nochmal paar Werte aus, mal sehen, ob es sich irgendwo rächt ... ;)

(Quelltext geändert)
 
hilft dir fuers rausholen die funktion? ->
Code:
unsigned int bits( unsigned int x, int k, int j) {
    return ( x >> k ) & ~(~0 << j) ;
}
die holt die j Bits, die k bits von rechts in x angeordnet sind .. (quelle algorithmen in C, sedgewick)
und fuers shiften um y sollte ja dann der einfache shift genuegen?
oder hab ich was falsch verstanden?
 
hmm... das proggie sieht schonmal okay aus...
zwar laeuft der fuer ein byte immer noch zweimal durch die schleife, aber das ist auf jeden fall besser als acht mal...

mal gucken ob man das noch weiter optimieren kann ;-)

EDIT:
okay, ich hab noch einmal copy&paste gemacht, und den inhalt der schleife nochmal darunter eingebaut.
nochmal: was in der schleife steht kann ruhig kompliziert werden...
scheint zu tun!
danke!

so, nun muss ich nochmal ueber dem code brueten um den zu verstehen und umbauen zu koennen.

wobei ich jetzt noch ein paar probleme mit der adressierung habe...
optimal waere ein source_block_offset+=8 gewesen.
aber... das schaff ich auch noch.
 
Last edited:
Ja, man kann es dadurch weiter verbessern, indem man sich nicht auf die Quelle, sondern auf das Ziel beruft:

Bisher guckt man ja, wie viel man aus einem Quellchar auslesen kann und schreibt das dann (soweit möglich) in den Zielchar. Man könnte auch gucken, wie viel in den aktuellen Zielchar passt und dann möglicherweise noch auf den darauf folgenden Quellchar zugreifen, um mit einem Durchlauf den Zielchar vollschreiben zu können.
 
Bezüglich der angestrebten Optimierung:

Es ist nicht möglich, den Eingabe-Char als ... ich sag mal "long long" zu betrachten, so dass man den einfach so mal eben um paar Bits shiften könnte, oder? ;)

Die Hardwareimplementation ist vermutlich auch an 8-Bit-Variablen gebunden? Oder könnte man die durchaus größer gestalten?
 
leider nicht.

die bytes werden bei mir reingestreamt. ich kann mir zwar merken welcher wert das war, aber die muessen auch wieder als bytes rausgestreamt werden.
 
sooooooooooooooooooooooooooo.....

dank euch allen hab ichs am ende doch noch zufriedenstellend hingekriegt.
fuers protokoll: der trick ist, dass man drei faelle betrachten muss:
1. ein- und ausgangstring fangen beim gleichen bit an
2. das erste bit vom eingangsstring liegt vor dem letzten bit vom ausgangsstring
3. das erste bit vom eingangsstring liegt hinter dem letzten bit vom ausgangsstring
(bin ich durch paldium drauf gekommen ;-)
dank physchemist weiss ich jetzt auch dass man das erste und letzte byte gesondert betrachten sollte.


dann kann man das alles so coden: (ich hab mal naive und optimierten code zusammengepackt:)
Code:
#include <stdio.h>
#include <stdlib.h>


int main(void)
{
        unsigned char z;
        unsigned char b;
        unsigned char c[10]={0x80,0xff,0xff,0xff,0x00,0x00,0x00,0x00,0x00,0x00};
        unsigned char d[10]={0x80,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00};
        unsigned char e[10];

        unsigned int x1=0;
        unsigned int y1=0;
        unsigned int n1=24;
        unsigned int i;
        unsigned short s;

        unsigned char ilsb,omsb,typ;
        int x,y,n;


        int u;

// bitcopy, naive implementierung
        x=x1;
        y=y1;
        n=n1;
        for (i=0;i<10;i++) e[i]=d[i];
        printf("in>  c:");
        for (i=0;i<10;i++) printf("%02x ",c[i]);
        printf("\n");
        printf("in>  d:");
        for (i=0;i<10;i++) printf("%02x ",d[i]);
        printf("\n");

        z=d[y/8]>>(8-(y%8));
        while (n)
        {
                b=(c[x/8]>>(7-x%8))&0x1;
                z=(z<<1)|b;
                x++;
                y++;
                if ((y%8)==0) {
                        d[y/8-1]=z;
                        z=0;
                }
                n--;
        }
        z<<=(8-(y%8));
        d[y/8]=z;
        printf("out> d:");
        for (i=0;i<10;i++) printf("%02x ",d[i]);
        printf("\n");





// bitcopy bytewise
        n=n1;
        x=x1;
        y=y1;



        ilsb=x%8;
        omsb=y%8;
        u=omsb-ilsb;


        if (u>0) // -> das erste bit vom eingangsstring liegt hinter dem letzten bit vom ausgangsstring
        {
                typ=1;
        } else if(u==0) // -> ein- und ausgangstring fangen beim gleichen bit an
        {
                typ=2;
        } else //  -> das erste bit vom eingangsstring liegt vor dem letzten bit vom ausgangsstring
        {
                typ=0;
                u=-u;
        }

        n-=(8-omsb);
        z=0;
        b=0;


// erstes byte gesondert betrachten
        z=e[y/8]&0xff<<(8-omsb);
        b=(c[x/8]<<ilsb)&0xff;
        z|=(b>>omsb);
        if (typ==1) b=c[x/8];

        x+=8;

        while (n>0)
        {
                switch(typ)
                {
                        case 0:         // u<0  -> das erste bit vom eingangsstring liegt vor dem letzten bit vom ausgangsstring
                                b=c[x/8];
                                e[y/8]=z|(b>>(8-u));
                                z=(b<<u);
                                break;
                        case 1:         // u>0 -> das erste bit vom eingangsstring liegt hinter dem letzten bit vom ausgangsstring
                                e[y/8]=z;
                                z=(b<<(8-u))&0xff;
                                b=c[x/8];
                                z|=(b>>u);
                                break;
                        case 2:         // u==0 -> ein- und ausgangstring fangen beim gleichen bit an
                                e[y/8]=z;
                                z=c[x/8];
                                break;
                }
                n-=8;
                x+=8;
                y+=8;
        }

// letztes byte gesondert betrachten
        if (typ==0) z=z|((c[x/8]>>(8-u)));
        e[y/8]=z&(0xff<<(-n));

        printf("out> e:");
        for (i=0;i<10;i++) printf("%02x ",e[i]);
        printf("\n");

        n=0;
        for (i=0;i<10;i++) if (d[i]!=e[i]) n=1;
        if (n) printf("fail\n");
}
 
Das wird 'ne Monsterschaltung. Errinnert mich irgendwie daran, als wir in der UNI Cache strategien in Software (MIPS 2000) simulieren mussten.
 
Nur noch als Anmerkung:

Bei
Code:
b=(c[x/8]<<ilsb)&0xff;
und
Code:
z=(b<<(8-u))&0xff;

kann man das &0xff auch weglassen, da ein UND mit nur 1 keine Auswirkung auf das Ergebnis haben wird. Aber das hätte man wohl spätestens beim Entwurf der Hardware bemerkt. ;)

Zu der Lösung im Allgemeinen: Respekt!

Und Danke, dass du dein Endergebnis noch gepostet hat, ist immer interessant zu sehen, wie man sowas effektiver gestalten kann - und wo man am Ende gelandet ist.
 
@kamikaze: och, das geht eigentlich... platz hab ich.
ausserdem sind das nur ein paar multiplexer, dreistufige barrellshifter und knapp 40 bit register. du solltest mal meine fouriertransformation sehen! *g*

mein chip ist nur zu 70% voll, da passt noch mehr rein.... hauptsache der schafft das alles in moeglichst wenig zyklen.

das finde ich auch das schoene an so kleinen taktfrequenzen: du kannst dich beim basteln TOOOOOOTAL austoben, ohne dass du bauchschmerzen kriegst, weil unter umstaenden ein zu langer pfad auftreten koennte.

@paldium: danke fuer die blumen. ohne euch haette ich das GARANTIERT nicht hingekriegt.
 
Back
Top