[C] Raar schuif probleem

[Gehakt]

Ik moest een programma schrijven om de IDCODE van een arm uit te lezen.
Waarschijnlijk weet niet iedereen hoe dat gaat.
IDCODE is een 32bits code die per clockpuls naar buiten word geschoven.
Hierbij komt als eerste het LSB en als laatste het MSB.
MSB ---[IDCODE]------LSB---->>>>>>

Deze 32bits code past uiteraard mooi in een interger.
Nou dacht ik om te beginnen met een interger die 0 is.
Deze vervolgens 1 plaats naar rechts te schuiven en iedere keer te ORen met het IDCODE bit wat ik inlees.

Na 32 maal schuiven zou het eerste bit wat ik binnen heb gekregen dus netjes op de LSB plaats terechtgekomen moeten zijn. Ik krijg de juiste bits binnen. Dit weet ik omdat ik iedere stap de bits print en de code heb gecontrolleerd. Echter gaat er iets mis bij het schuiven omdat ik uiteindelijk een interger overhou met de waarde 0xFF FF FF FF.

C:

//voorafgaande code
//temp is de 1 bits waarde die elke clockslag binnenkomt deze is 1 of 0.
//output is int output. Hierin komt de uiteindelijke IDCODE.
output = (output >> 1) | (temp<<31) ;
printf("%2X\t%4X\t%4X\n",temp,(temp<<31),output);
//hieronder volgt de output

 1      80000000        80000000
 1      80000000        C0000000
 1      80000000        E0000000
 1      80000000        F0000000
 0         0                 F8000000
 0         0                 FC000000
 0         0                 FE000000
 0         0                 FF000000
 1      80000000        FF800000
 1      80000000        FFC00000
 1      80000000        FFE00000
 1      80000000        FFF00000
 0         0                 FFF80000
 0         0                 FFFC0000
 0         0                 FFFE0000
 0         0                 FFFF0000
 1      80000000        FFFF8000
 1      80000000        FFFFC000
 1      80000000        FFFFE000
 1      80000000        FFFFF000
 1      80000000        FFFFF800
 0         0                 FFFFFC00
 0         0                 FFFFFE00
 0         0                 FFFFFF00
 1      80000000        FFFFFF80
 1      80000000        FFFFFFC0
 1      80000000        FFFFFFE0
 1      80000000        FFFFFFF0
 0         0                 FFFFFFF8
 0         0                 FFFFFFFC
 1      80000000        FFFFFFFE
 0         0                 FFFFFFFF
Output:FFFFFFFF

Wie o wie kan dit gedrag verklaren?
Mijn leraar kon het niet namelijk.

[Icelus]

Waarschijnlijk werk je met een signed integer. Hierbij is het hoogste bit het tekenbit.
De meeste compilers gebruiken een zgn. arithmetic shift (tekenbit blijft ‘behouden’) i.p.v. een logical shift bij het schuiven naar rechts.

Probeer de integers als ‘unsigned int’ te declareren.

[ Voor 19% gewijzigd door Icelus op 15-01-2008 10:35 ]

[Gehakt]

Ah dat was ook het enige wat ik kon bedenken maar heb het nog niet kunnen testen.
Nu weet ik tenminste ook hoe dat heet.
Zo even proberen of dat het probleem oplost.

[deadinspace]

Merk ook op dat een int niet noodzakelijk groot genoeg is om een 32-bits waarde op te slaan. Gebruik liever uint32_t (of uint_least32_t, of unsigned long).

[.oisyn]

Bovendien is het ook niet gezegd dat een shr op een uint altijd logic is - dat is aan de compiler. Als je het echt zeker wilt weten kun je nog ANDen met 0x7fffffff

[deadinspace]

.oisyn schreef op dinsdag 15 januari 2008 @ 13:50:
Bovendien is het ook niet gezegd dat een shr op een uint altijd logic is - dat is aan de compiler.

Jawel, unsigned right shifts zijn in C altijd zero-extended.

Uit mijn K&R second edition, sectie 2.9:

Right shifting an unsigned quantity always fills vacated bits with zero. Right shifting a signed quantity will fill with sign bits ("arithmic shift") on some machines and with 0-bits ("logical shift") on others.

[.oisyn]

Oh ja het was andersom, unsigned is altijd logic maar signed is implementation defined.

[Gehakt]

Ok ik heb het gecontrolleerd en dat was inderdaad het geval.
Als ik gebruik maakte van een unsigned int werden er wel netjes 0 en ingeschoven.

Het volgende is natuurlijk ook een oplossing:

code:

output = (output >> 1) & 0x7FFFFFFF;

Hierbij zet je na het schuiven het eerste bit weer handmatig op 0.
Iedereen bedankt.

[deadinspace]

Gehakt schreef op dinsdag 15 januari 2008 @ 15:30:
Het volgende is natuurlijk ook een oplossing:

code:

output = (output >> 1) & 0x7FFFFFFF;

Hierbij zet je na het schuiven het eerste bit weer handmatig op 0.
Iedereen bedankt.

Dat

• gaat mis als ints niet precies 32 bit zijn (zie ook mijn vorige opmerking).
• is een stuk minder leesbaar.
• is trager als je compiler het niet weg weet te optimaliseren (jaja, micro-optimalisatie, maar toch).

Dat eerste probleem kun je misschien nog omheen werken door met INT_MAX of UINT_MAX / 2 te werken ofzo, maar veel charmanter wordt dat er niet van.

[Gehakt]

Micro optimalisatie is wel belangrijk voor mij aangezien ik normaal werk met embedded systemen.
Het gaat hier echter om een kleine schoolopdracht van 100 regels code ofzo gecompileerd voor de pc dus de snelheid maakt in dit geval niet zoveel uit.
Dat een int niet altijd 32bits is zal ik in mijn achterhoofd houden.

[Icelus]

Dan kun je misschien beter zoiets doen:

C:

/* Initialisatie */
output = 0;
bitpos = 0;

[...]

output |= temp << bitpos;
bitpos++;

[ Voor 17% gewijzigd door Icelus op 15-01-2008 16:08 ]

[Gehakt]

Dat had ik in eerste instantie maar ik vond dit handiger voor me gevoel.
Weer 2 regels code minder.
Maar in theorie zou dit sneller zijn?

[.oisyn]

[quote]deadinspace schreef op dinsdag 15 januari 2008 @ 15:41:
[...]

Dat

• gaat mis als ints niet precies 32 bit zijn (zie ook mijn vorige opmerking).

Gaat helemaal niet mis. Hij stopt de nieuwe bit op positie 31 in de int. Dus zolang een int minstens 32 bits is gaat het gewoon goed.

[deadinspace]

.oisyn schreef op dinsdag 15 januari 2008 @ 16:33:
Gaat helemaal niet mis. Hij stopt de nieuwe bit op positie 31 in de int. Dus zolang een int minstens 32 bits is gaat het gewoon goed.

Ehm, ja, je hebt gelijk. Ik had even in mijn hoofd dat de data-bits erin gezet werden op de msb in plaats van op bit 31.

Maar mijn opmerking blijft wel staan voor als int minder dan 32 bits is

[farlane]

deadinspace schreef op dinsdag 15 januari 2008 @ 17:39:
Maar mijn opmerking blijft wel staan voor als int minder dan 32 bits is

Wat op een embedded systeem niet eens zo heel moeilijk voor te stellen is

Als je jezelf wilt aanleren om het goed te doen gebruik je het beste uint32_t, als je compiler die ondersteunt.

[ Voor 17% gewijzigd door farlane op 15-01-2008 20:55 ]

[Icelus]

Gehakt schreef op dinsdag 15 januari 2008 @ 16:16:
Dat had ik in eerste instantie maar ik vond dit handiger voor me gevoel.
Weer 2 regels code minder.
Maar in theorie zou dit sneller zijn?

‘Winst’ is hier extreem klein en hangt uiteraard van het systeem af.
Een ARM processor kan dit in één instructie (IIRC) maar een 8051/Z80 zal in een lus tot de juiste positie moeten schuiven.

[MSalters]

farlane schreef op dinsdag 15 januari 2008 @ 20:55:
[...]
Als je jezelf wilt aanleren om het goed te doen gebruik je het beste uint32_t, als je compiler die ondersteunt.

Je bedoelt unsigned long, wat (1) overal werkt, en (2) sneller kan zijn dan uint32_t.

Dat laatste is het gevolg van het feit dat uint32_t modulo 1<<32 moet rekenen, terwijl unsigned long modulo 1<<N moet rekenen met N>=32. Er zijn TI DSPs met snelle 40 bits operaties; die moeten een & 0x00FFFFFFFF doen na bijna elke operatie op een uint32_t

[farlane]

MSalters schreef op woensdag 16 januari 2008 @ 19:59:
Je bedoelt unsigned long, wat (1) overal werkt, en (2) sneller kan zijn dan uint32_t.

Dat laatste is het gevolg van het feit dat uint32_t modulo 1<<32 moet rekenen, terwijl unsigned long modulo 1<<N moet rekenen met N>=32. Er zijn TI DSPs met snelle 40 bits operaties; die moeten een & 0x00FFFFFFFF doen na bijna elke operatie op een uint32_t

Nee ik bedoelde een uint32_t, als ie ondersteund wordt. uint32_t zal op een platform met 32 bits longs hetzelfde zijn als een unsigned long lijkt me. ( Ben trouwens ook al eens een platform tegengekomen ( NeuronC dialect dat wel ) waar een long 16 bits is.

Ik vraag me af of die TI met zijn 40bits longs (?) niet kan zien dat als je met 0x7FFFFFFF AND dat hij niet zelf ook nog eens moet gaan maskeren.

Verder geldt het natuurlijk andersom ook, als sizeof( usigned long ) > 4 op een 8 bitter wordt gedraaid is het langzamer.

[.oisyn]

farlane schreef op donderdag 17 januari 2008 @ 18:43:
( Ben trouwens ook al eens een platform tegengekomen ( NeuronC dialect dat wel ) waar een long 16 bits is.

Mag niet, dus dat was geen echte C (wat je zelf ook al zegt)

[ Voor 6% gewijzigd door .oisyn op 17-01-2008 19:24 ]

[deadinspace]

MSalters schreef op woensdag 16 januari 2008 @ 19:59:
Je bedoelt unsigned long, wat (1) overal werkt, en (2) sneller kan zijn dan uint32_t.

uint_least32_t lijkt me dan nog steeds netter, omdat

• Je daarmee expliciet vastlegt minstens 32 bits nodig te hebben
• Je hiermee geen onnodig brede integer krijgt; longs zijn op 64-bit CPUs vaak 64 bits.

farlane schreef op donderdag 17 januari 2008 @ 18:43:
Ben trouwens ook al eens een platform tegengekomen ( NeuronC dialect dat wel ) waar een long 16 bits is.

Mja, maar goed dat dat een dialect was, want dat mag in C dus niet.

Ik vraag me af of die TI met zijn 40bits longs (?) niet kan zien dat als je met 0x7FFFFFFF AND dat hij niet zelf ook nog eens moet gaan maskeren.

Wat MSalters bedoelde is dat als een compiler 40 bits integers op zo'n DSP moet gebruiken voor uint32_t, dat hij dan na (bijna) elke operatie op die uint32_t die AND operatie moet doen om de resultaten correct te houden.

Als je dat toevallig zelf ook een keer doet dan zal de compiler (en niet de TI DSP!) dat waarschijnlijk wel weg optimaliseren, maar wat nou als je zelf die AND helemaal niet nodig hebt? Dan moet de compiler hem toch uitvoeren, om de illusie dat het om een 32-bits integer gaat hoog te houden. Dat probleem heb je bij uint_least32_t (of unsigned long) niet.