Cum ati implementa functia atoi()?

[Silviu Ardelean]

Mi se pare o cretinitate sa discuti de wchar_t cand e vorba de atoi() dar sunt convins ca exista specimene ce-si pun problema asta.

Offtopic: Ori suntem atoi ori nu mai suntem!

[Marius Bancila]

Mi se pare o cretinitate sa discuti de wchar_t cand e vorba de atoi() dar sunt convins ca exista specimene ce-si pun problema asta.

Hai sa nu exageram cu limbajul.

[0ptr]

Mi se pare o cretinitate sa discuti de wchar_t cand e vorba de atoi() dar sunt convins ca exista specimene ce-si pun problema asta.

Hai sa nu exageram cu limbajul.

Sorry!

[MrSmersh]

usor OT
Mie o implementare de atoi o asociez cu folosirea (relativ frecventa)a lui isdigit.
Scriu prea mult managed, sau e o asociere "sanatoasa" ?

[Ovidiu Cucu]

O implementare a unei functii care sa se comporte similar cu functia C standard atoi() ar fi aceasta:

Code: Select all

int my_atoi(const char* p)
{
   int result = 0;
   char sign;

   while(isspace(*p)) /* skip witespace */
   {
      p++;
   }

   sign = *p;         /* store sign */

   if((sign == '+') || (sign == '-'))
   {
      p++;            /* skip sign */
   }

   while(isdigit(*p))
   {
      result = 10 * result + *p - '0';
      p++;            /* next digit */
   }
   return (sign == '-') ? -result : result;
}

Nu neaparat la interviu... Char daca s-ar da problema unui lot de programatori care au folosit de jdemii de ori atoi(), formulata la modul

scrieti codul ce implementeaza functia C int atoi(const char* pChar).

...atat si-o dunga... cei mai multi ar "uita" partea cu "skip witespace". Pe langa acestia, multi s-ar apuca voiniceste de testat daca nu cumva argumentu-i NULL, daca nu cumva rezulta overflow si alte jmecherii pe care atoi-ul original (ca si alte functii C standard) nu le face.

De aceea spuneam mai devreme de "specifcatii" pentru cei care fac subiectele de interviu.
Un minim de informatii nu strica, pentru ca nu sta nimeni sa invete pe derost specificatiile exacte ale functiilor C standard, chiar a celor des folosite si aparent banale.

Din pacate, generalizand, in lumea software se asteapta de multe ori sa iasa "din cacat bici care sa pocneasca" sau se spune "lasa ca stie programatorul ce am eu in cap!".
Ce rezulta, stim cu totii:

requrements.jpg (21.11 KiB) Viewed 7933 times

Fara mishto!

[null]

Bucla:

Code: Select all

 while(isdigit(*p))
   {
      result = 10 * result + *p - '0';
      p++;            /* next digit */
   }

ar putea fi scrisa ca:

Code: Select all

unsigned int d;
 while(*p && (d = *p -'0') < 10)
   {
      result = 10 * result +d;
      p++;            /* next digit */
   }

reducand numarul de operatii in plus prin folosirea lui isdigit().

[xxscorp]

Fara misto nici din partea mea, sa presupunem ca se foloseste acel atoi intr-un aparat de radioterapie, sa citeasca user input-ul (adica de la tehnician) si sa calculeze doza. Sau ca sa fiu si mai rau, sa calculeze atenuarea aplicata cu un scut in calea radiatiilor. Ii dau programului lui 42 urmatorul input: 5000000042. Cred ca ar fi frumos sa dea acel INT_MAX (2147483647 deci), insa el imi da voiniceste 705032746. Fukushima frate!

Observati ca nu am zis nimic de whitespace, isdigit sau alte chichite si chichineturi (cam lame de altfel) care se pot specifica si verifica mai mult sau mai putin usor, am gasit insa un bug mult mai subtil si mai greu de depistat chiar si in acel cod "trivial". Daca era insa mai complex, nu prea as fi avut sanse sa-l pot gasi si... go figure!


P.S. Exemplul cu aparatul de radioterapie l-am dat pentru ca au fost in realitate cazuri de erori de programare (de fapt era combinatie de design al aparatului si de eroare de programare) care s-au soldat si cu decese parca.

[Ovidiu Cucu]

Bucla:

Code: Select all

 while(isdigit(*p))
   {
      result = 10 * result + *p - '0';
      p++;            /* next digit */
   }

ar putea fi scrisa ca:

Code: Select all

unsigned int d;
 while(*p && (d = *p -'0') < 10)
   {
      result = 10 * result +d;
      p++;            /* next digit */
   }

reducand numarul de operatii in plus prin folosirea lui isdigit().

Desigur, daca vrem, o putem "cripta" cat de tare vrem. Si poate ca pe unele compilatoare s-ar putea obtine ceva castig de performanta.
Desi ma indoiesc de faptul ca inlocuirea lui isdigit care e standard si e super-optimizat ar fi o idee prea stralucita. Doar daca, intr-un caz special, nu avem si nu avem CRT.

[Ovidiu Cucu]

Fara misto nici din partea mea, sa presupunem ca se foloseste acel atoi intr-un aparat de radioterapie, sa citeasca user input-ul (adica de la tehnician) si sa calculeze doza. Sau ca sa fiu si mai rau, sa calculeze atenuarea aplicata cu un scut in calea radiatiilor. Ii dau programului lui 42 urmatorul input: 5000000042. Cred ca ar fi frumos sa dea acel INT_MAX (2147483647 deci), insa el imi da voiniceste 705032746. Fukushima frate!

Observati ca nu am zis nimic de whitespace, isdigit sau alte chichite si chichineturi (cam lame de altfel) care se pot specifica si verifica mai mult sau mai putin usor, am gasit insa un bug mult mai subtil si mai greu de depistat chiar si in acel cod "trivial". Daca era insa mai complex, nu prea as fi avut sanse sa-l pot gasi si... go figure!


P.S. Exemplul cu aparatul de radioterapie l-am dat pentru ca au fost in realitate cazuri de erori de programare (de fapt era combinatie de design al aparatului si de eroare de programare) care s-au soldat si cu decese parca.

Fara misto, m-am racit gura (se pare, cel putin pana acum) aici spunand "specificatii".
Daca spui "implementeaza-mi o functie simlara cu atoi()" mi se pare normal sa-ti fac ceva similar cu atoi-ul standard, care asta e..., nu e safe si nici n-a fost proiectata sa fie safe.
Daca in schimb spui "implementeaza-mi o functie simlara cu atoi() care sa fie 'safer'" atunci it fac, mai frate , si validare de parametru, si sa nu se dea rezultatul peste cap, s.a.m.d.

BTW. Ca sa nu mai moara oameni nevinovati din cauza lui atoi(), puteti folosi in loc strtol() care FACE test de overflow.
Numai sa nu uitati sa testati valoarea returnata si errno.

[xxscorp]

Eu zic asa: daca nu faci ceva si spui asta - e ok. Daca faci insa, fa-o bine!
Problema e ca atoi42 face test de overflow, dar nu il face bine. Si problema mare e ca nu greseste decat uneori, si atunci cand greseste o face tacut si subtil (da rezultat gresit, nu crapa, nu tipa).
De asta m-am referit la varianta lui si nu am zis nimic de celelalte implementari (care nu fac testul deloc si despre care s-au spus deja destule).

[Ovidiu Cucu]

Eu zic asa: daca nu faci ceva si spui asta - e ok. Daca faci insa, fa-o bine!
Problema e ca atoi42 face test de overflow, dar nu il face bine. Si problema mare e ca nu greseste decat uneori, si atunci cand greseste o face tacut si subtil (da rezultat gresit, nu crapa, nu tipa).
De asta m-am referit la varianta lui si nu am zis nimic de celelalte implementari (care nu fac testul deloc si despre care s-au spus deja destule).

Am pornit de la "atoi" si-am ajuns la "atoi42". In care CRT e probleama? Care sunt cazurile cand da kix? Nu cumva vrei sa spui "_atoi64"?

Ok, sa incercam sa descalcim un pic.
In standardul ISO/IEC 9899-1999 (C99) scrie:

The functions atof, atoi, atol, and atoll need not affect the value of the integer
expression errno on an error. If the value of the result cannot be represented, the
behavior is undefined.

Daca inteleg eu bine, se da mana libera celui care le implementeaza sa faca sau sa nu faca verificari gen overflow. Sau mai degraba sugereaza sa nu faca.
Orcum, "undefined behavior" trebuie sa dea de gandit celor care folosesc aceste functii.
Multe implementari de CRT nu fac verificarile deci, cine cheama atoi() undeva unde se poate intampla un "dezastru" in caz de eroare, o face pe barba lui.
Acuma ce ne facem? Ne apucam repede sa implemetam my_atoi() dupa chipul, asemanarea si durerea noastra?
Nu zic nu, ar fi si asta o solutie.
Insa cum am mai zis, avem la dispozitie strtol() care musai verifica depasirea, fara sa trebuiasca sa reinventam noi roata.

BTW. In implementarea din VC2005 sau din versiunile mai noi, atoi() cheama intern strtol() deci putem face teste de eroare.
La fel si _atoi64 cheama intern _strtoi64.

Cel putin din testele pe care le-am facut, nu e nici o problema cu verificarea depasirii.
Exemplu:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <errno.h>

int main()
{
   // Note: under VS2005 this prints "Overflow", while under VS6.0 prints "Ok".
   const char* p = "9223372036854775808"; // _I64_MAX + 1
 
   __int64 res = _atoi64(p);

   if(ERANGE == errno)
   {
      if((_I64_MAX == res) || (_I64_MIN == res))
      {
         printf("Overflow");
      }
   }
   else
   {
      printf("Ok");
   }
   return 0;
}

[Marius Bancila]

Am impresia ca s-a plecat de la o intrebare de interviu si s-a ajuns la un requirement de functie de biblioteca.

[0ptr]

Am impresia ca s-a plecat de la o intrebare de interviu si s-a ajuns la un requirement de functie de biblioteca.

Mi-ai luat vorba de pe limba. Apreciez faptul ca intrebarea mea a strarnit atata interes si s-a ajuns la discutii tot mai detaliate. Sunt convins ca foarte multi interievatori ar fi multumiti cu toate implementarile propuse.
Daca mai sunt lucruri / variante de adaugat cred ca sunt bine-venite.