Nekorektní blog Petra Kubáče na Blog.cz

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.

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í

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

LDI R16, 127 ; při kladném přetečení dosazujeme 127

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

LDI R16, -128 ; dosazujeme -128 a končíme

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.