Interpolationsknas på Arduino

[superx]

Ok, om arkitekturen man kör på har instruktioner för 8x8 bitars-multiplikation med 16 bitars-resultat och en 16-bitars-ackumulator, och dessutom har en MAC-instruktion, hur ska man då skriva följande kod (V är 16 bitar, de andra 8 bitar):

Kod: Markera allt

V = (A*x + B*(M-x));

Om man castar alla 8-bitarsvariablerna till 16-bitar finns möjligheten att kompilatorn gör detta först, och implementerar multiplikationerna som 16x16 bitar, vilket inte är det man vill. Men om man bara castar slutresultatet så finns risken att det blir 8x8 bitar trunkerat till ett 8-bitarstal, så att additionerna körs med 8 bitar, vilket inte heller är bra.

Jag tror man blir tvungen att lära sig hur kompilatorn vill ha det, eller skriva inline-assembler om det är viktigt exakt hur detta görs.

[stekern]

Jo, det är ganska klart definierat i standarden vad som kommer ske, även om man inte explicit castar.
Läs under kapitel 6.3 (speciellt 6.3.1.8 ) här: http://www.open-std.org/jtc1/sc22/wg14/ ... /n1256.pdf

"If both operands have the same type, then no further conversion is needed.
Otherwise, if both operands have signed integer types or both have unsigned
integer types, the operand with the type of lesser integer conversion rank is
converted to the type of the operand with greater rank."

D.v.s:

Kod: Markera allt

uint8_t a;
uint16_t b;
a * b;

<=>

Kod: Markera allt

uint8_t a;
uint16_t b;
((uint16_t)a) * b;

[superx]

Ja, fast problemet uppstår ju vid multiplikation där operanderna och resultatet har olika antal bitar på många arkitekturer. Kan man då på något standardenligt sätt säga åt kompilatorn när casten ska ske?

Den delen av standarden som det refereras till löser, så vitt jag ser, inte problemet med:

Kod: Markera allt

V = (A*x + B*(M-x));

[stekern]

Om man castar alla 8-bitarsvariablerna till 16-bitar finns möjligheten att kompilatorn gör detta först, och implementerar multiplikationerna som 16x16 bitar, vilket inte är det man vill.

Jag vet inte om jag hänger med på vad du menar här, på vilket sätt skulle t.ex.
0x7f * 0x7f = 0x3F01
vara annorlunda än
0x007f * 0x007f = 0x3F01

[superx]

Resultatet är detsamma, men den undre varianten kräver 4 multiplikationer istället för 1 om man har en 8-bitars-multiplikator.

[Wedge]

Man kan ju skriva om...

W = (A*x + B*(M-x));
V = W / M;

(A*x + B(M-x)) / M
(A*x + B*M - B*x)/M
((A-B)*x + B*M)/M

B + (A-B)*X /M

Swech

Det där såg verkligen lovande ut. En multiplikation mindre, gånger 48 interpoleringar, det lär märkas på exekveringstiden.
Dessutom blir nog den kvarstående multiplikationen betydligt snabbare, 16*16 bitar istället för 32*32 bitar.
M och x är 16 bitar (unsigned), (A-B) blir också 16 bitar (signed). Produkten blir 32 bitar (signed). Efter divisionen räcker det med 16 bitar (signed), och resultatet av additionen klarar sig med 8 bitar (unsigned) men måste beräknas med 16.

I mitt första uttryck fick A och B typecastas upp till 32 bitar för att kompilatorn skulle lyckas räkna rätt. Känns som om de multiplikationerna blev onödigt dyra.

De konstiga värden jag fick berodde nog mest på lömskheter från interrupttimern, som kunde utlösas medan x och M behandlades... yay, slarv!! Med längre tid i interpoleringen så flyttades risken för fel därmed till andra ställen, märkte jag, haha!
Jag fick det att snurra riktigt fint (men kanske onödigt långsamt) igår, men ska prova din variant. Tack!

[stekern]

Resultatet är detsamma, men den undre varianten kräver 4 multiplikationer istället för 1 om man har en 8-bitars-multiplikator.

Ah, du tänker så, men det kommer inte hända (om inte kompilatorn är hjärndöd och
är den det kommer den inte kunna utnyttja 8x8=>16 multipliceraren ändå).
Den kommer identifera det som zext16(u8) * zext16(u8) => u16 och kunna lägga in en
u8*u8 => u16 instruktion.

Men det är klart att du har en poäng i det du säger, C är inte target-oberoende,
det har ingen någonsin påstått, och vill man ha fullkomlig kontroll vad som händer
är det knacka asm som gäller.

[superx]

Men det är klart att du har en poäng i det du säger, C är inte target-oberoende,
det har ingen någonsin påstått, och vill man ha fullkomlig kontroll vad som händer
är det knacka asm som gäller.

Nä, det är det ingen som påstått. Tror det här stickspåret började med att jag påstod att C är dåligt på att beskriva den här typen av beräkningar. Min erfarenhet är tyvärr att kompilatorerna är rätt korkade med sånt här. Läs här t.ex.
http://mekonik.wordpress.com/2009/03/18 ... plication/

Ibland tror jag kompilatorerna blir lite bakbundna av standarden också, så att de tvingas att göra en cast vid fel tillfälle för att uppfylla någon klausul i standarddokumentet.

Så fort man försöker göra lite mer avancerade DSP-grejer i fixed-point så blir detta ett problem, men ibland går det att komma runt det genom att lista ut i vilken ordning man ska casta saker för att få kompilatorn att fatta vad man vill.

[Wedge]

Liten observation... Arduinobibliotekets funktion map() kunde jag ju använt. Mappar ett värdeområde till ett annat... vilket ju faktiskt är vad interpolationen gör.

V = map (x, 0, M, A, B)

Och den räknar i princip som Swech visade, men är en funktion (med overhead) och räknar mer, samt använder long på alla argument, så den blir inte lika effektiv som att göra det själv:

Kod: Markera allt

long map(long x, long in_min, long in_max, long out_min, long out_max)
{
  return (x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min;
}

[stekern]

Ibland tror jag kompilatorerna blir lite bakbundna av standarden också, så att de tvingas att göra en cast vid fel tillfälle för att uppfylla någon klausul i standarddokumentet.

Jag tycker det är lite tvärtom, standarden hjälper till att ordna reda i vad som bör ske.
Har du koll på vad standarden säger, så har du nytta av det när du ska pressa ut rätt asm ur kompilatorn.

Sen att man stundoms tappar hakan av en del saker som är ett resultat av något som står
i standarden är en annan sak, det är i alla fall betryggande att ha det svart på vitt varför hakan är i knävecken

T.ex. så kan man se detta spännande fenomen då int = 32-bit:

Kod: Markera allt

uint32_t u32 = 0;
int32_t s32 = -1;
uint8_t u8 = 0;
int8_t s8 = -1;
 
(int64_t)(s32 - u32) => 0x00000000ffffffff
(int64_t)(s8 - u8)   => 0xffffffffffffffff

detta har att göra med att s8 och u8 kommer få plats i en int, och blir således "uppgraderade" till det.
u32 kan inte få plats i en int, så s32 kommer således bli "uppgraderad" till en unsigned int.

(Sorry Wedge för stickspåret i din tråd, hoppas du inte tar illa upp, det är i alla fall löst anknutet )

[Wedge]

Stickspåret är helt OK för min del.

[Swech]

Men man kan också se det som att om man inte analyserar det som skall göras
och genomskådar "genvägar" i beräkningar så kan det bli onödiga beräkningar.

Är man gammel och envis som jag och kör assembler så sliter man sitt hår för att hitta enklaste beräkningsvägen..

Swech

[Nerre]

Ja det var ju lite det jag försökte få fram, genom att vrida och vända på formlerna kan man se var man kan förenkla och rationalisera.

Ett typiskt exempel är ju när folk börjar labba med en temperaturgivare och börjar med att räkna om ett inläst 12-bitars värde till en temperatur (i form av fixed point eller i värsta fall flyttal) istället för att använda det där 12-bitars värdet i alla beräkningar och bara göra omräkningen vid presentationen.

[sodjan]

Man ska inte heller glömma table-lookup. Det kan vara väldigt
effektivt för t.ex interpoleringar.

[superx]

Spännande exempel! Gäller att se upp när man blandar signed och unsigned verkar det som.

Testade lite med avr-gcc här.

Kod: Markera allt

uint16_t interp1(const uint8_t x, const uint8_t A, const uint8_t B, const uint8_t M)
{
  uint8_t AB = A-B;
  uint16_t V = B + (AB)*x/M;

  return V;
}

Ger 1 multiplikation

Kod: Markera allt

uint16_t interp2(const uint8_t x, const uint8_t A, const uint8_t B, const uint8_t M)
{
  uint16_t V = B + (A-B)*x/M;

  return V;
}

Ger 3 multiplikationer. Jag antar att det beror på att man i det övre fallet själv tar ansvar för att A-B inte slår runt. Går detta att utläsa av standarden?

EDIT: Ändrade AB från signed till unsigned