bit håndtering av et char buf[]

[opticus]

Hei,

 

jobber med en oppgave på skolen, jeg skal lage en crc.c til et program som sender filer over nettverket. Denne skal lage en crc av en char buf[], men jeg klarer ikke finne noe vettig info om bit håndtering, vet ikke hva jeg skal søke på på nettet heller, jeg har prøvde i flere timer å finne noe vettig om det her, men jeg klarer det rett og slett ikke. en annen ting jeg lurer på er dette polynomet man deler på når man lager crc, hvordan regner man ut hva som er best? min crc skal være forresten være på 6bit av en 53 byte char []

[søppel10]

http://www.faqs.org/faqs/compression-faq/p...section-26.html

[opticus]

ahhh... genialt!

 

hva er det som skjer her:

u_long crc32(u_char *buf, int len)
{
       u_char *p; //denne er grei
       u_long  crc; //denne er grei

       if (!crc32_table[1])    /* if not already done, */ //denne er grei
               init_crc32();   /* build table */ //denne er grei
       crc = 0xffffffff;       /* preload shift register, per CRC-32 spec */ //denne er grei
       for (p = buf; len > 0; ++p, --len) //begynner bli uklart, men den er også grei
               crc = (crc << 8) ^ crc32_table[(crc >> 24) ^ *p]; //wtf skjer her?
       return ~crc;            /* transmit complement, per CRC-32 spec */ //at det står ~crc er at den returnerer feks hvis det er 01001100 så er det 10110011 som blir returnert? sant?
}

[søppel10]

akkurat lekkert er det ikke nei .. hehe

 

se om du får noe ut av dette:

http://www.functionx.com/cpp/Level2/Lesson05.htm

 

..det kan være at det blir lettere å se hva som skjer om du bryter koden opp i deler (skritt for skritt) .. f.eks. den saken i for-loopen, noe slikt - hm, tror jeg:

 

 for (p = buf; len > 0; ++p, --len) {//begynner bli uklart, men den er også grei
   u_long tmp1 = (crc >> 24) ^ *p;
   u_long tmp2 = crc32_table[tmp1];
   u_long tmp3 = (crc << 8);
   crc = tmp3 ^ tmp2; //wtf skjer her?
 }

 

..setter du et breakpoint ved den siste linja i for-loopen kan du ta en titt på verdinene i tmp* .. (ved hjelp av gdb kan du skrive ut tall/ting i binær-format)

 

edit:

01001100 så er det 10110011 som blir returnert? sant?

ja

Endret 14. mars 2005 av søppel10

[opticus]

veldig mange tusen takker for hjelp så langt! har kommet mye lengre på 15 min nå enn de siste døgnene.

 

har et par kodeting jeg lurer på og det er:

hva betyr det ^ tegnet og hva er er << og >> ?

feks denne: (crc >> 24) ^ *p;

hva er det som skjer her? etter mye titting på kode her og der har jeg skjønt at denne ^ har noe med bit å gjøre, men jeg skjønner ikke hva, leser forresten på den siden nå, var endel å lese der det er bra!

 

EDIT:

 

tror jeg skal komme en del videre nå takk!!

denne har jo alt man trenger å vite mer eller mindre:

http://www.functionx.com/cpp/Level2/Lesson05.htm

Endret 14. mars 2005 av opticus

[søppel10]

jeg har forsøkt å sammle noe her:

http://nostdal.org/mediawiki/index.php/Bitwise_operators

 

feks denne: (crc >> 24) ^ *p;

 

(crc >> 24) er en isolert operasjon

^ er en isolert operasjon

..og *p er en isolert operasjon ....

 

*p vil si; "hent verdien av det p peker på"

^ vil si xor

(crc >> 24) vil si "returner verdien som blir når du "shifter" verdien i crc 24 ganger mot høyere"

 

edit:

du kan f.eks. bryte ting opp i deler som jeg forklarte over -- for å lettere se hva som skjer "skritt-for-skritt"

Endret 14. mars 2005 av søppel10

[opticus]

hvis det var et så tett skylag før denne tråden at jeg ikke kunne se noen ting, så er det lettere overskyet, med mulighet for sol nå

 

jeg skjønner ikke poenget med << og >>

 

*p er greit, dette skjønner jeg

^ xor eller hva det nå er skjønner jeg også.

 

har delt opp programmet endel nå

men oppdelingen slik du delte opp gir ikke lik crc verdi på tmp3 som crc

 

også skal jeg lage crc så jeg får en sjekksum som er 6-bit, ikke 32, men at crc er 32bit vil kanskje ikke si at sjekksum nødvendigvis blir det ?

 

og se bort fra signaturen min, føler at den er veldig feil akkurat nå

[JBlack]

jeg skjønner ikke poenget med << og >>

Du skjønner ikke...

A) at det er bitwise shift?

B) hva bitwise shift er?

C) hvorfor bruke bitwise shift her?

[opticus]

jeg skjønner ikke poenget med det, dvs hvorfor man flytter ting til høyre eller til venstre,

 

(crc << 8), dvs at man flytter det som er i p[n], til p[n+1] ? det er det jeg skjønner det som hvertfall.. den (crc >> 24) vil jo si at man flytter det på alt i crc fra feks crc[n] til crc[n-3]? hvorfor? what? i dont get it

[søppel10]

hvis du tenker deg:

int i1 = 1; // 00000001

..og du forskyver denne til venstre 2 ganger:

cout << (i1 << 2) << endl; // skriver ut 4, som er 00000100

er du med på hva som skjer? altså bittet 1 blir flyttet to ganger mot venstre (shifted)

 

det samme skjer her:

int i5 =  5; // 00000101
cout << (i5 << 2) << endl; // skriver ut 20, som er 00010100

..altså bittene i:

00000101

..blir forskjøvet 2 ganger mot venstre, og da ender man opp med:

00010100

..som binært representerer det desimale tallet 20

 

edit:

<< og >> jobber bare innenfor en byte, om jeg ikke tar helt feil (edit2: fannt noe greier jeg skrev tidligere her), - så forskyvningen vil ikke "forflytte" ting over i andre "array-elementer" .. ting faller bare utenfor, så om du gjør dette:

int i5 = 5; // 00000101
cout << (i5 >> 2) << endl; // skriver ut 1, som er 00000001

Endret 14. mars 2005 av søppel10

[opticus]

jada, jeg henger med på at det skyver bit'ene ene og andre veien, men hvorfor i alle dager gjør de det? det er det som er problemet mitt, jeg skjønner nå at 00000001 blir til 00000100 om jeg kjører "int noe = (1 << 2)", og at 00000001 = 1 og 00000100 = 4. Det er ok, dette skjønner jeg.

[søppel10]

men hvorfor i alle dager gjør de det?

 

jeg har ingen anelse - jeg har ikke satt meg inn i crc-algoritmen, men jeg anser shift-operatørene som operasjoner på lik linje med det å addere, subtrahere, multiplisere, dividere o.s.v. .. man putter noe inn - og får noe annet ut

[JBlack]

jeg skjønner ikke poenget med det, dvs hvorfor man flytter ting til høyre eller til venstre,

 

(crc << 8), dvs at man flytter det som er i p[n], til p[n+1] ? det er det jeg skjønner det som hvertfall.. den (crc >> 24) vil jo si at man flytter det på alt i crc fra feks crc[n] til crc[n-3]? hvorfor? what? i dont get it

Nei, det blir feil.

 

Bitwise shift shifter bare innen variabelen. Den flytter ingen data over til naboer i en array.

 

Ok, anta crc er 32 bit, eller fire byte.

 

Ta så en pointer til char, og la den peke på crc. Nå kan du sammenligne slik du mener, roterer 8 til en side er som å kopiere en byte til byten ved siden av.

 

Men dette er dumt av flere grunner.

1. Det er tungvindt og krever flere operasjoner når man skal forskyve alle bit'ene i 32 bit

2. Det er ikke plattformuavhengig, (big endian vs. little endian)

3. Det fungerer ikke om du skal skifte et antal bits som ikker går opp i åtte

 

En bitshift er en rask og enkel funksjon som gjør akkurat det den skal. Hvorfor komplisere?

 

Forståelse av algoritmen, hvorfor den bruker bitshift, det kan jeg ikke si uten å bruke tid på sette meg inn i den,

[maboi]

x << i ganger x med 2^i

 

så hvis i er 3 er det det samme som x * 8

 

x >> i deler x med 2^i

 

så hvis i er 3 er det det samme som x / 8

 

bare at det går bittelitt fortere med shift operatorene

[JBlack]

bare at det går bittelitt fortere med shift operatorene

En gang i tiden gikk det veldig mye fortere med shift, enn med gange og dele. I dag er vel prosessorene såpass optimaliserte at mulitplikasjon sikkert er gjort på en puls, og dividering sikker ikke mange fler.

 

Om jeg husker riktig, så kunne M68000 (fra de første Amiga'ene) bruke opptil 40 klokkepulser på en dividering. På den tiden optimaliserte man gjerne multiplikasjon i demoer, spill osv, ved å erstatte dem med bitshift og adderings operasjoner. Da sparte man noen klokkesykler.

[Feynman]

Verdien av en CRC er resten fra en deleoperasjon. Koden for å regne ut CRC-verdien er i prinsippet noe sånt som: buf % crc_divisor. Det er selvsagt ikke så enkelt, men det er ideen bak det hele.

 

Koden som er vist minner en del om multipliserings/divideringskretser, så dersom man ikke kjenner til digital elektronikk er det sikkert ikke noe lett å forstå hva man skal med alle disse bit-skiftene.

[opticus]

jeg har drevet svært lite med digitale kretser, litt har jeg vært borti det, ellers hadde jeg ikke skjønt ett kvekk av det her med and or xor not osv.. hjelper sikkert ikke på at jeg sitter her med feber og en forferdelig hoste. Men, jeg har kommet frem til at det er linjen

crc = (crc << 8) ^ crc32_table[(crc >> 24) ^ *p];

som er roten til alt ondt, evt roten av hele crc problematikken min.

- alt i crc blir flyttet 8 plasser til venste (crc << 8)

- alt i crc flyttet 24 plasser til høyre, kan ikke skjønne at det er noe poeng med dette, men ok, så xor'er det med *p, dvs binærverdien til en eller annen char?

- så tar man første operasjon og xor'er den med det som står på crc32_table[int verdien til andre operasjon]

 

dette er nemlig ikke helt uforståelig, men det er mer eller mindre helt totalt uforståelig, skjønner ikke hvordan jeg skal få dette gjort om så jeg får en 6bit crc verdi feks. Noen som har en anelse om hvordan de ville gjort den om til en 8bit rest?

[JBlack]

jeg har drevet svært lite med digitale kretser, litt har jeg vært borti det, ellers hadde jeg ikke skjønt ett kvekk av det her med and or xor not osv.. hjelper sikkert ikke på at jeg sitter her med feber og en forferdelig hoste. Men, jeg har kommet frem til at det er linjen

crc = (crc << 8) ^ crc32_table[(crc >> 24) ^ *p];

som er roten til alt ondt, evt roten av hele crc problematikken min.

- alt i crc blir flyttet 8 plasser til venste (crc << 8)

- alt i crc  flyttet 24 plasser til høyre, kan ikke skjønne at det er noe poeng med dette, men ok, så xor'er det med *p, dvs binærverdien til en eller annen char?

- så tar man første operasjon og xor'er den med det som står på crc32_table[int verdien til andre operasjon]

 

dette er nemlig ikke helt uforståelig, men det er mer eller mindre helt totalt uforståelig, skjønner ikke hvordan jeg skal få dette gjort om så jeg får en 6bit crc verdi feks. Noen som har en anelse om hvordan de ville gjort den om til en 8bit rest?

(crc << 8) endrer ikke crc. Resultat er det samme som (crc * 256), som heller ikke endrer den opprinnelige verdien. crc = crc << 8, ville endret verdien.

 

crc32_table[(crc >> 24) ^ *p] er altså et oppslag i en tabell, men uten at verken crc, p eller innholdet i tabellen blir endret.

Endret 15. mars 2005 av JBlack

[opticus]

dette er jo helt vanvittig!!!!!!

 

men jeg skjønner det nå..

hvis man tar å flytter alt << 6 (lage 6bit) og kjører xor og flytter den samtidig >> 1 i bufferet og gjør dette 6 ganger, så legger man sammen dette for hver karakter og kjører modulo et eller annet 6bit tall og får en remainder, så er alt fint!

[opticus]

heh...

 

er dette en crc sjekk som lager 6bit crc sjekksum?

int make_crc(char buf[])
{
     int i, crc = 0;
     for(i=0;i<strlen(buf);i++)
           crc += buf[i];
     crc = (crc%63);
     return crc;
}

Endret 15. mars 2005 av opticus