Hlavní navigace

Počítání s přetečením v C

1. 10. 2014 23:42 (aktualizováno) Josef Pavlík

Čas od času je potřeba sčítat a odčítat s přetečením/podtečením. Například v případě, že potřebujeme počítat s větší šířkou registrů než máme k dispozici. V assembleru je tato záležitost jednoduchá. Máme k dispozici flag Carry. Ale v C tuhle možnost nemáme. Sice máme možnost napsat část kódu v assembleru, ale to bývá komplikované a nepřenosné.

Nedávno jsem potřeboval napsat 64 bitové sčítání a odčítání pro 32 bitový processor. Přesněji řečeno, celý program umocňuje 64bitové číslo dalším 64bitovým číslem a počítá zbytek po dělení výsledku dalším 64bitovým číslem. Tahle šílenost nakonec vede na sčítání a odčítání 64bitových čísel. Původně jsem to napsal pro i8051, pak pro PIC, nakonec to musím portovat na Atmel, tentokrát v C. A jsme u jádra problému. Jak detekovat přeteční v C.

Idea je celkem jednoduchá. Pokud sčítám dvě kladná čísla, výsledek musí být vyšší nebo roven kterémukoliv ze sčítanců. Pokud ovšem výsledek přeteče, bude menší, než kterýkoliv z nich. Tahle doměnka by se jistě dala dokázat matematicky, ale jednodušší bude ověřit, jestli to funguje pro jakoukoliv kombinaci sčítanců. Ale nebudeme to dělat pro 32bitová čísla, vyzkoušíme to hrubou silou na dvoubitových číslech:

A

B

C=A+B

podmínky

bit1

bit0

bit1

bit0

carry

bit1

bit0

C<A?

C<B?

0

0

0

0

0

0

0

NE

NE

0

0

0

1

0

0

1

NE

NE

0

0

1

0

0

1

0

NE

NE

0

0

1

1

0

1

1

NE

NE

0

1

0

0

0

0

1

NE

NE

0

1

0

1

0

1

0

NE

NE

0

1

1

0

0

1

1

NE

NE

0

1

1

1

1

0

0

ANO

ANO

1

0

0

0

0

1

0

NE

NE

1

0

0

1

0

1

1

NE

NE

1

0

1

0

1

0

0

ANO

ANO

1

0

1

1

1

0

1

ANO

ANO

1

1

0

0

0

1

1

NE

NE

1

1

0

1

1

0

0

ANO

ANO

1

1

1

0

1

0

1

ANO

ANO

1

1

1

1

1

1

0

ANO

ANO

V tabulce vidíme, že hypotéza skutečně funguje. Kdykoliv, kdy výsledek přeteče, bude C menší než kterýkoliv ze sčítanců. Takže program v C pro sčítání a detekci přetečení může vypadat takto:

unsigned add(unsigned A, unsigned B, bool *CY)
{
  unsigned C=A+B;
  *CY=C<A;
  return C;
}

Pokud potřebujeme přičíst i předchozí flag přetečení. musíme udělat dva testy.

unsigned addc(unsigned A, unsigned B, bool *CY)
{
  unsigned C=A+B;
  unsigned local_carry=C<A;
  if (*CY)
  {
    C++;
    if (C==0) local_carry=true;
  }
  *CY=local_carry;
  return C;
}

Já vím, nahradit jedinou instrukci addc programem v C na 12 řádků je perverzní, ale v nenáročných případech je to lepší, protože je to plně přenositelné.

Při odečítání máme situaci jednodušší. Pokud budeme počítat C=A-B a přitom A<B, víme dopředu, že to podteče. Tady nepotřebujeme důkazy.

unsigned sub(unsigned A, unsigned B, bool *Borrow)
{
  *Borrow=A<B;
  return A-B;
}

unsigned subb(unsigned A, unsigned B, bool *Borrow)
{
  bool local_borrow=A<B;
  unsigned C=A-B;
  if (*Borrow)
  {
    if (C==0) local_borrow=true;
    C--;
  }
  *Borrow=local_borrow;
  return C;
}

Sdílet