Cum ati implementa functia atoi()?

Intrebari despre limbajul C++, standardul C++, STL, OOP in C++ sau alte subiecte nelegate de VisualC++
User avatar
Silviu Ardelean
Senior
Senior
Posts: 1175
Joined: 12 Jul 2007, 09:22
Judet: Timiş
Location: Timisoara
Contact:

Re: Cum ati implementa functia atoi()?

Post by Silviu Ardelean » 21 Mar 2011, 14:53

0ptr wrote: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! ;)



User avatar
Marius Bancila
Fondator
Fondator
Posts: 2344
Joined: 11 Jul 2007, 11:45
Judet: Timiş
Location: Timisoara
Contact:

Re: Cum ati implementa functia atoi()?

Post by Marius Bancila » 21 Mar 2011, 17:11

:offtopic:
0ptr wrote: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.
Marius Bancila
Fondator Codexpert, Microsoft MVP VC++
Site personal | Blog

0ptr
Membru
Membru
Posts: 71
Joined: 01 Feb 2011, 23:27
Judet: Ilfov

Re: Cum ati implementa functia atoi()?

Post by 0ptr » 21 Mar 2011, 17:14

Marius Bancila wrote::offtopic:
0ptr wrote: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! :)

User avatar
MrSmersh
Microsoft MVP
Microsoft MVP
Posts: 289
Joined: 20 Jul 2007, 10:18
Location: Timisoara
Contact:

Re: Cum ati implementa functia atoi()?

Post by MrSmersh » 22 Mar 2011, 00:05

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" :biggrin:?

User avatar
Ovidiu Cucu
Fondator
Fondator
Posts: 3778
Joined: 11 Jul 2007, 16:10
Judet: Iaşi
Location: Iasi
Contact:

Re: Cum ati implementa functia atoi()?

Post by Ovidiu Cucu » 22 Mar 2011, 13:46

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
0ptr wrote: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
requrements.jpg (21.11 KiB) Viewed 6784 times
Fara mishto! :)

null
Junior
Junior
Posts: 1
Joined: 21 Mar 2011, 23:04

Re: Cum ati implementa functia atoi()?

Post by null » 22 Mar 2011, 14:12

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
Junior
Junior
Posts: 7
Joined: 31 Jan 2011, 15:01
Judet: Timiş

Re: Cum ati implementa functia atoi()?

Post by xxscorp » 22 Mar 2011, 14:22

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.

User avatar
Ovidiu Cucu
Fondator
Fondator
Posts: 3778
Joined: 11 Jul 2007, 16:10
Judet: Iaşi
Location: Iasi
Contact:

Re: Cum ati implementa functia atoi()?

Post by Ovidiu Cucu » 22 Mar 2011, 14:40

null wrote: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.

User avatar
Ovidiu Cucu
Fondator
Fondator
Posts: 3778
Joined: 11 Jul 2007, 16:10
Judet: Iaşi
Location: Iasi
Contact:

Re: Cum ati implementa functia atoi()?

Post by Ovidiu Cucu » 22 Mar 2011, 15:22

xxscorp wrote: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
Junior
Junior
Posts: 7
Joined: 31 Jan 2011, 15:01
Judet: Timiş

Re: Cum ati implementa functia atoi()?

Post by xxscorp » 22 Mar 2011, 16:19

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).

User avatar
Ovidiu Cucu
Fondator
Fondator
Posts: 3778
Joined: 11 Jul 2007, 16:10
Judet: Iaşi
Location: Iasi
Contact:

Re: Cum ati implementa functia atoi()?

Post by Ovidiu Cucu » 22 Mar 2011, 19:15

xxscorp wrote: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;
}

User avatar
Marius Bancila
Fondator
Fondator
Posts: 2344
Joined: 11 Jul 2007, 11:45
Judet: Timiş
Location: Timisoara
Contact:

Re: Cum ati implementa functia atoi()?

Post by Marius Bancila » 22 Mar 2011, 23:21

Am impresia ca s-a plecat de la o intrebare de interviu si s-a ajuns la un requirement de functie de biblioteca.
Marius Bancila
Fondator Codexpert, Microsoft MVP VC++
Site personal | Blog

0ptr
Membru
Membru
Posts: 71
Joined: 01 Feb 2011, 23:27
Judet: Ilfov

Re: Cum ati implementa functia atoi()?

Post by 0ptr » 22 Mar 2011, 23:51

Marius Bancila wrote: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.

Post Reply