---

Jeg har et langt chararray som indeholder data bitvist. Har i et forslag til
en effektiv måde at "spejlvende" hver byte i arrayt?

Det kræver hvis lige en lille illustration: hvert tal illustrere en bit. MSB
først LSB til sidst.


8 7 6 5 4 3 2 1|8 7 6 5 4 3 2 1|osv.


Hver byte skal nu spejlvendes (lang forklaering, men for at gøre et format
kompatibelt) så MSB og LSB bliver vendt.

altså:

1 2 3 4 5 6 7 8| 1 2 3 4 5 6 7 8| osv

Det er altså ikke arrayet der skal spejles men hver byte der i.

Håber nogen har et forlsag

Mvh
Anders

---

Flare wrote:
> Jeg har et langt chararray som indeholder data bitvist. Har i et forslag til
> en effektiv måde at "spejlvende" hver byte i arrayt?
>
> Det kræver hvis lige en lille illustration: hvert tal illustrere en bit. MSB
> først LSB til sidst.
>
>
> 8 7 6 5 4 3 2 1|8 7 6 5 4 3 2 1|osv.
>
>
> Hver byte skal nu spejlvendes (lang forklaering, men for at gøre et format
> kompatibelt) så MSB og LSB bliver vendt.
>
> altså:
>
> 1 2 3 4 5 6 7 8| 1 2 3 4 5 6 7 8| osv
>
> Det er altså ikke arrayet der skal spejles men hver byte der i.
>
> Håber nogen har et forlsag
>
> Mvh
> Anders
>
>
Noget i denne stil:

char * array = ....
int i, array_length = ...

for(i = 0; i < array_length; i++)
{
array[i] = ((array[i] >> 7) & 0x01) |
((array[i] >> 5) & 0x02) |
((array[i] >> 3) & 0x04) |
((array[i] >> 1) & 0x08) |
((array[i] << 1) & 0x10) |
((array[i] << 3) & 0x20) |
((array[i] << 5) & 0x40) |
((array[i] << 7) & 0x80);
}


Robert

---

On Thu, 29 May 2003 23:12:16 +0200, "Flare" <anders@pings.dk> wrote:

>en effektiv måde at "spejlvende" hver byte i arrayt?
>Håber nogen har et forlsag

Noget i retning af dette (ER IKKE TESTET!):

void reverse_bits_in_bytes( unsigned char * p, size_t n )
{
static unsigned char bytemirror_array[256];
static unsigned char * bytemirror = 0;

if ( !bytemirror )
{
/* Fyld data i tabellen */
unsigned char i = 0;
do {
bytemirror_array[i] =
(i >> 7) & 0x01) |
(i >> 5) & 0x02) |
(i >> 3) & 0x04) |
(i >> 1) & 0x08) |
(i << 1) & 0x10) |
(i << 3) & 0x20) |
(i << 5) & 0x40) |
(i << 7) & 0x80);

} while ( ++i & 0xFF );

/* Markér at tabellen nu er fuldtud initieret */
/* (bør være sidste punkt i initieringen) */
bytemirror = bytemirror_array;
}

if ( n )
do { *p = trans[*p]; ++p; } while ( --n );
}


Tabellen kan selvfølgelig også defineres fast - det er jo "kun" 16*16
værdier - 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, ... kan let laves
med et lille program.

/Peder Skyt

---

[ anders@pings.dk ]

> Jeg har et langt chararray som indeholder data bitvist. Har i et
> forslag til en effektiv måde at "spejlvende" hver byte i arrayt?


Vil du ha "effektiv" eller "portabel"?

I det første tilfellet kan det være aktuelt å se på instruksjonssettet
til den underliggende prosessoren. Noen har rotate instruksjoner, og
særlig mye raskere enn dette går det ikke. Kanskje finnes det "bytt om
disse bitene"-instruksjoner? Å skrive en liten funksjon i assembly som
koden din kaller for hver byte burde gå relativt greit.

Skal du ha en portabel løsning, så kunne problemet nesten ha blitt
løst med std::rotate, men dessverre (?) har man ikke iteratorer på
bitnivå (og jeg tror[tm] det vil koste mer enn det smaker å få det
til).

Det er flere mulige forslag til en portabel løsning:

* En tabell. Dette er spesielt gunstig dersom CHAR_BIT er relativt
liten (fx. 8). Da kan man regne ut alle (speilvendte) 2^CHAR_BIT
verdier på forhånd, og bruke den opprinnelige byten som en indeks i
denne tabellen.

* Bruke en byte som om det var en array, og bytte om verdier i to og
to posisjoner:

source = array[ index ];
result = 0U;
for ( position = 0U; position != CHAR_BIT / 2; ++position ) {
sh_amount_right = position;
sh_amount_left = CHAR_BIT - position - 1;

bit_right = source & ( 1 << sh_amount_right );
bit_left = source & ( 1 << sh_amount_left );

result = bit_right << ( sh_amount_left - sh_amount_right )
| bit_left >> ( sh_amount_left - sh_amount_right );
}
array[ index ] = result;

(evt. kan man gjøre:

result = ( bit_right >> sh_amount_right ) << sh_amount_left
| ( bit_left >> sh_amount_left ) << sh_amount_right;

... alt ettersom hva man mener selv er mest intuitivt (std::swap er
jo egentlig det som er mest beskrivende, men igjen, den virker ikke
på bitnivå)).

Begge løsningene over vil virke med CHAR_BIT != 8, noe forslagene til
Robert Larsen og Peder Skyt ikke gjør.





ivr
--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

---

Tak for hjæplen alle sammen!

Løsningen blev en kombination af jeres forslag

const int bits_reverse[256] = {
0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,
0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0,
0x08,0x88,0x48,0xC8,0x28,0xA8,0x68,0xE8,
0x18,0x98,0x58,0xD8,0x38,0xB8,0x78,0xF8,
0x04,0x84,0x44,0xC4,0x24,0xA4,0x64,0xE4,
Etc....... 0xFF};

Og så bare køre en for-løkke igennem der udskifter værdierne. Går rigtig
hurtigt. Så det er jo perfekt.

Mvh
Anders

---

"Flare" <anders@pings.dk> wrote in message
news:3ed7420d$0$24657$edfadb0f@dread14.news.tele.dk...
> Tak for hjæplen alle sammen!
>
> Løsningen blev en kombination af jeres forslag
>
> const int bits_reverse[256] = {
> 0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,
> 0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0,
> 0x08,0x88,0x48,0xC8,0x28,0xA8,0x68,0xE8,
> 0x18,0x98,0x58,0xD8,0x38,0xB8,0x78,0xF8,
> 0x04,0x84,0x44,0xC4,0x24,0xA4,0x64,0xE4,
> Etc....... 0xFF};
>
> Og så bare køre en for-løkke igennem der udskifter værdierne. Går rigtig
> hurtigt. Så det er jo perfekt.


Man kunne godt mistænke Robert og Peders løsninger for at være hurtigere, i
det de ikke kræver et (dyrt) opslag i hukommelsen pr. permutation. (Nåja, og
hvorfor er din permutations tabel const int når du kun bruger værdier i
intervallet [0;0xff[ ?)

---

> hvorfor er din permutations tabel const int når du kun bruger værdier i
> intervallet [0;0xff[ ?)

Fordi jeg har plads nok :) Nej. ehmm vil du da bruge char istedet?

Anders

---

> > hvorfor er din permutations tabel const int når du kun bruger værdier i
> > intervallet [0;0xff[ ?)
>
> Fordi jeg har plads nok :) Nej. ehmm vil du da bruge char istedet?

Det kommer an på så meget .. men rent logisk er det ikke snu at bruge const
int når man har data af type const unsigned char

---

> Det kommer an på så meget .. men rent logisk er det ikke snu at bruge
const
> int når man har data af type const unsigned char

Nej det har du / i ret i. Er også ændret.

Mvh
Anders

---

> Man kunne godt mistænke Robert og Peders løsninger for at være hurtigere, i
> det de ikke kræver et (dyrt) opslag i hukommelsen pr. permutation. (Nåja, og
> hvorfor er din permutations tabel const int når du kun bruger værdier i
> intervallet [0;0xff[ ?)
>
>

Mange tak

Man kunne endda gøre dem lidt hurtigere (og grimmere) ved at bruge Duffs
device:

#define ROTATE(x) ((x) = \
   ((x) >> 7) & 0x01 | \
   ((x) >> 5) & 0x02 | \
   ((x) >> 3) & 0x04 | \
   ((x) >> 1) & 0x08 | \
   ((x) << 1) & 0x10 | \
   ((x) << 3) & 0x20 | \
   ((x) << 5) & 0x40 | \
   ((x) << 7) & 0x80)

void rotate_bits(char * array, int array_length)
{
   int i = 0;
   int n = (array_length + 7) / 8;
   switch(array_length % 8)
   {
      case 0: do { ROTATE(array[i]); i++;
      case 7: ROTATE(array[i]); i++;
      case 6: ROTATE(array[i]); i++;
      case 5: ROTATE(array[i]); i++;
      case 4: ROTATE(array[i]); i++;
      case 3: ROTATE(array[i]); i++;
      case 2: ROTATE(array[i]); i++;
      case 1: ROTATE(array[i]); i++;
         } while (++i < array_length);
   }
}



Hehehe.....lidt at tænke over.
Jeg har ikke testet koden, men prøv selv ad.

Robert

---

"Igor V. Rafienko" <igorr@ifi.uio.no> wrote in message
news:xjvy90owxzh.fsf@riva.ifi.uio.no...
> [ anders@pings.dk ]
>
> > Jeg har et langt chararray som indeholder data bitvist. Har i et
> > forslag til en effektiv måde at "spejlvende" hver byte i arrayt?
>
> Begge løsningene over vil virke med CHAR_BIT != 8, noe forslagene til
> Robert Larsen og Peder Skyt ikke gjør.

For større værdier vil man nok foretrække en algoritme der er
logaritmisk i antal bit.

mvh. Anders

---

[ Anders J. Munch ]

[ ... ]

> For større værdier vil man nok foretrække en algoritme der er
> logaritmisk i antal bit.


First make it right, then make it fast.





ivr
--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

---

"Igor V. Rafienko" <igorr@ifi.uio.no> wrote:
> [ Anders J. Munch ]
>
> [ ... ]
>
> > For større værdier vil man nok foretrække en algoritme der er
> > logaritmisk i antal bit.
>
>
> First make it right, then make it fast.

Ja, okay, men 'make it right' kan også se sådan her ud:

assert(CHAR_BIT == 8);

- Anders