Matematika v robotice 15. Nad dopisy diváků

29. září 2013 v 5:13 | Petr |  Roboti a Matematika
Klidně si užívám toho, jak jsem na dovolené a moje mladá manželka nehne v domácnosti ani prstem - a najednou se nad minulým dílem "Matematiky" rozhořela diskuse skoro jakobych se pokusil zabít nějaké zlaté tele. No asi ano, protože v diskusi dokonce padlo odvážné "zkuste uložit JPEG na SD kartu v Assembleru" - no ukládá snad žirafa, nebo brouk hrobařík JPEG na SD kartu ? A jak jim to funguje ?
Když už tak rýpu, tak si rýpnu ještě - ukládání JPEGů na SD kartu - to je typická "úloha moderní doby" - kdy je snadné zjistit kolik napršelo na Times Square v New Yorku, ale zjistit kolik mi napršelo na zahrádce je "technological challenge".

Takže vše se točí kolem Saturační aritmetiky a sčítání a odčítání v ní. V diskusi jsem dostal moře dotazů - typu kolik je -1+(-1) atd. Tyto otázky bych rozdělil celkem do 8 variant, které postupně proberu, a abych mé čtenáře nepletl 4, 8 a 16 bitovými čísly tak dneska se pohybujeme striktně v oblasti 8 bitů - tedy int8_t a uint8_t

1. Unsigned integer - uint8_t. - čísla se nám pohybují od 0 do 255 tedy 0b00000000 do 0b11111111
A. Je možné aby A+B < 0 - není - protože pro záporná čísla nemáme ani bitové vyjádření navíc nejnepříznivější případ je A+0 = A
B. Je možné aby A+B > 255 - snadno a proto procesor nastavuje Carry bit který je de-facto 9 bit sčítaných registrů. Ergo příklad saturačního sčítání uint8_t už jsem uvedl.
ADD R16, R17
BRCC Continue
LDI R16, 255
:Continue
C. Je možné aby A-B > 255 - pokud jsou A i B v rozsahu - není - pilným nedůvěřivcům doproučuju zkusit všech 65536 kombinací .
D. Je možné aby A-B < 0 - velmi snadno stačí aby B > A, ale zde nám začínají problémy s Carry bitem - protože některé architektury používají při odčítání Carry - pořád jako Carry - tedy 9 bit - tedy při regulérním odčítání typu 5-3 alias 5+(-3) je Carry nastaven, Zatímco oblíbené AVR a ostatní starší architektury používají Carry jako Borrow - tedy při operaci typu 5-3 není nastaven, zato je nastaven při operaci typu 3-5. takže berte jako fakt, že pro saturační odčítání uint8_t v AVR platí
SUB R16, R17
BRCC Continue
CLR R16
:Continue

2. Signed integer - int8_t - tedy čísla se nám pohybují od -128 do +127 to je od 0b10000000 do 0b01111111
A. je možne aby A+B < -128 - ano snadno -100 + (-100) = -200
B. Je možné aby A+B > 127 - ano snadno 100 + 100 = 200

Tím jsme v průseru neboť na rozdíl od Unsigned varianty - nám žádná možnost "automaticky nevypadává".
Tedy je jasné , že pomocí Overflow detekujeme přetečení - když nenastane budeme ve výpočtu pokračovat. Když nastane potřebujeme nějakou možnost, jak zjistit, jestli místo přetečeného výsledku dosazujeme +127 nebo -128.
Minule jsem psal, že Carry si nevšímáme jelikož ale všechny procesory sčítají stejně (unsigned jako signed) a nastavují vždy Overflow i Carry - můžeme toho "kreativně využít".

Nejprve je třeba si položit otázku jestli součtem kladného a záporného čísla se můžeme dostat mimo limit - a odpověď je nikoliv. To nám ohromně pomáhá, protože to znamená, že problémy dělají buď součty dvou kladných, nebo dvou záporných. Kladná čísla v Signed variantě jsou vždy 0B0XXXXXXX - tedy není cesta jak součtem dvou čísel s nulou v osmém bitu nechat výsledek přetéct do devátého (Carry) bitu - a tedy Carry není nastaven když jsme přetekli směrem ke 127, A naopak....

Takže příkládek saturačního sčítání int8_t je zde.
ADD R16, R17 ; Sčítáme
BRVC EndProc ; nepřetekli jsme takže končíme
BRCC PosOverflow ; přetekli jsme na kladnou stranu takže jdeme dosadit 127
LDI R16, -128 ; přetekli jsme na zápornou stranu - dosazujeme -128
RJMP EndProc ; a končíme
:PosOverflow
LDI R16, 127 ; při kladném přetečení dosazujeme 127
:EndProc

C. je možné aby A-B < -128 - Ano -100 - (+100) = -200
D. Je možné aby A-B > 127 Ano 100- (-100) = 200
E. Je možné aby 0-B > 127 Ano 0-(-128) =128
Doufám, že po minulém příkládku vás nebere migréna. Takže postup je jasný, nejprve podle Overflow rozhodneme jestli k něčemu vůbec došlo a pak pomocí Carry rozhodneme zda výsledek nahradíme +127 nebo -128. jedinou věc, kterou je třeba rozmyslet je která hodnota Carry znamená co takže vezměme příklad C.
To je 0b100110 - 0b0110100 - z hlediska carry bitu (unsigned čísel) odečítáme menší číslo od většího a Carry nebude nastaven - takže nebude - li carry nastaven dosazujeme -128.
Vezměme příklad D. 0b0110100 - 0b100110 - carry bit bude nastaven - a my dosazujeme +127, což (naštěstí) zahrnuje i příklad E. Tedy :
SUB R16, R17 ; Odečítáme
BRVC EndProc ; nepřetekli jsme takže končíme
BRCC NegOverflow ; přetekli jsme bez Carry takže jdeme dosadit -128
LDI R16, 127 ; přetekli jsme s Carry takže dosazujeme 127
RJMP EndProc ; a končíme
:NegOverflow
LDI R16, -128 ; dosazujeme -128 a končíme
:EndProc¨
Jasné ?

Všech 8 varinat i mně jsme vyčerpali. Takže jenom několik poznámek :
1. C prý s Overflow bitem vůbec neumí pracovat.
2. x86 architektura harwarově podporuje saturační aritmetiku od doby MMX instrukcí.
3. Skoky v saturačních počtech prý na moderních architekturách dělají úžasný bordel v Instrukční Pipeline, proto docenti dělají docentury a profesoři profesury na "Branchless satruration aritmetic" (saturační aritmetika bez větvení) - Schválně si to zadejte do BINGU a zejnéna na tom jak donutit C přeložit to tak"jak jsme to zamýšleli"
4. Přepsání příkládků z Assembleru do C opět nechávám na C-čkových guruech - já jsem jako žirafa, nebo brouk hrobařík - taky neumím uložit JPEG na SD kartu, a zatím jsem to k ničemu nepotřeboval....

Zbývá už jenom tradiční rada pro brunety : jestli si myslíte, že občas ukázat pipinu a občas ukázat slzičky - stačí k otevření všech dveří - šeredně se mýlíte.
 

Buď první, kdo ohodnotí tento článek.

Komentáře

1 Pablo2048 Pablo2048 | 30. září 2013 v 7:48

2 Dalik: Tak, a ted jsme to dostali oba ;-)

2 Dalik Dalik | 30. září 2013 v 9:22

Ano :-), přitom to bylo všechno skoro i nedorozumění. Žil jsem totiž v dojmu, že Overflow je nastavené při přetečení ze 7. do 8. bitu, podobně jako Carry je nastaven při přetečení z 8. do 9. bitu. To ovšem, jak by řekl Milouš Jakeš, neodpovídá skutečnosti.

Komentáře jsou uzavřeny.


Aktuální články

Reklama