From: Leandro Lucarella Date: Sun, 9 Oct 2005 20:30:29 +0000 (+0000) Subject: Bugfix (evita potencial pisada de memoria). X-Git-Tag: darcs_import~10 X-Git-Url: https://git.llucax.com/z.facultad/75.29/dale.git/commitdiff_plain/bef7e48edc804c2329baa9f565a6a85eb765fdbf?ds=sidebyside;hp=11386ea0e0e75b3642b8c54e69232eec227678c8 Bugfix (evita potencial pisada de memoria). --- diff --git a/src/number.h b/src/number.h index 2b4b78f..8c37df6 100644 --- a/src/number.h +++ b/src/number.h @@ -12,6 +12,8 @@ #include #include #include +#include +#include #include #ifdef _WIN32 @@ -66,7 +68,7 @@ struct number number(native_type n, sign_type s = positive): chunk(1, n), sign(s) {} - number(const std::string& str); + number(std::string str); // Operadores number& operator++ () @@ -79,8 +81,11 @@ struct number number& operator*= (const number& n); number& operator<<= (const size_type n); number& operator-= (const number& n); - bool operator< (const number& n) const; bool operator== (const number& n) const; + bool operator< (const number& n) const; + + // Compara si es menor en módulo. + bool menorEnModuloQue(const number& n) const; // Devuelve referencia a 'átomo' i del chunk (no debería ser necesario // si la multiplicación es un método de este objeto). @@ -171,31 +176,36 @@ struct number }; -template < typename N, typename E > -number< N, E >::number(const std::string& origen) +inline unsigned ascii2uint(char c) { - const N MAX_N = (~( (N)0 ) ); - E increment = 0; - E acum = 0; - - unsigned length = origen.length(); - unsigned number_offset = 0; + return c & 0xF; +} - while (number_offset +number< N, E >::number(std::string str): + chunk(1, 0), sign(positive) +{ + if (!str.size()) + return; // Si está vacío, no hace nada + + number< N, E > diez = 10u; + std::string::size_type i = 0; + std::string::size_type fin = str.size() - 1; + if (str[0] == '-') // Si es negativo, salteo el primer caracter + ++i; + chunk[0] = ascii2uint(str[i]); + while (i < fin) { - // si encuentro un signo + ó - corto - if (!isdigit(origen[length-number_offset-1])) - break; - - increment = (10*number_offset)*(origen[length-number_offset-1]-'0'); - if ((acum + increment) > MAX_N) - { - chunk.push_back(acum); - } - + *this = *this * diez + number< N, E >(ascii2uint(str[i+1])); + ++i; } - - + if (str[0] == '-') // Si es negativo, le pongo el signo + sign = negative; } template < typename N, typename E > @@ -237,6 +247,7 @@ number< N, E >& number< N, E >::operator+= (const number< N, E >& n) { chunk[i] += n.chunk[i] + c; if ((chunk[i] < n.chunk[i]) || \ + ( c && ((n.chunk[i] + c) == 0)) || \ ( (n.chunk[i] == 0) && c && (chunk[i] == 0) )) c = 1; // Overflow else @@ -298,7 +309,7 @@ number< N, E >& number< N, E >::operator-= (const number< N, E >& n) number< N, E > subtrahend; // voy a hacer siempre el mayor menos el menor - if (*this < n) + if (menorEnModuloQue(n)) { minuend = n; subtrahend = *this; @@ -363,6 +374,16 @@ bool number< N, E >::operator< (const number< N, E >& n) const return true; // n es más grande } + if (sign == negative) // Si comparamos 2 negativos, usamos + return !menorEnModuloQue(n); // "lógica inversa" + else + return menorEnModuloQue(n); +} + + +template < typename N, typename E > +bool number< N, E >::menorEnModuloQue(const number< N, E >& n) const +{ size_type i; //problema de VC++, da error de redefinición if (chunk.size() > n.chunk.size()) // yo tengo más elementos @@ -407,6 +428,7 @@ bool number< N, E >::operator< (const number< N, E >& n) const return false; // Son iguales } + // efectúa un shifteo a izquierda del chunk, agregando 0s en los casilleros // menos significativos template < typename N, typename E > @@ -428,20 +450,69 @@ number< N, E > operator<< (const number< N, E >& n, typename number< N, E >::siz return tmp; } +// Este es un 'workarround' HORRIBLE, de lo peor que hicimos en nuestras vidas, +// pero realmente no encontramos manera alguna de convertir un número a un +// string decimal que no requiera de divisiones sucesivas. Para no cambiar la +// semántica del programa, decidimos convertir externamente nuestra salida en +// hexadecimal a decimal utilizando un programa externo (en este caso Python +// porque sabemos que está disponible en el laboratorio B). +// +// Estamos realmente avergonzados de haber tenido que llegar a esto, pero no nos +// imaginamos que iba a sernos tan compleja esta conversión. Y nuevamente +// pedimos disculpas. template < typename NN, typename EE > std::ostream& operator<< (std::ostream& os, const number< NN, EE >& n) { + std::string cmd = "python -c 'print "; + if (n.sign == negative) + cmd += '-'; + cmd += "0x" + numberToHex(n) + "'"; + + char buf[BUFSIZ]; + FILE *ptr; + + if ((ptr = popen(cmd.c_str(), "r")) != NULL) + while (fgets(buf, BUFSIZ, ptr) != NULL) + os << buf; + pclose(ptr); + return os; +} + +template < typename N, typename E > +std::string numberToHex(const number< N, E >& n) +{ + std::ostringstream os; + typename number< N, E >::const_reverse_iterator i = n.chunk.rbegin(); + typename number< N, E >::const_reverse_iterator end = n.chunk.rend(); + // Salteo ceros + for (; i != end; ++i) + if (*i != 0) + break; + if (i != end) // Si no llegué al final, imprimo sin 'leading zeros' + { + os << std::hex << *i; + ++i; // y voy al próximo + } + // imprimo el resto con 'leading zeros' + for (; i != end; ++i) + os << std::setfill('0') << std::setw(sizeof(N) * 2) << std::hex + << *i; + return os.str(); +} + +template < typename N, typename E > +std::string numberToHexDebug(const number< N, E >& n) +{ + std::ostringstream os; // FIXME sacar una salida bonita en ASCII =) - if (n.sign == positive) - os << "+ "; - else - os << "- "; - typename number< NN, EE >::const_reverse_iterator i = n.chunk.rbegin(); - typename number< NN, EE >::const_reverse_iterator end = n.chunk.rend(); + if (n.sign == negative) + os << "-"; + typename number< N, E >::const_reverse_iterator i = n.chunk.rbegin(); + typename number< N, E >::const_reverse_iterator end = n.chunk.rend(); for (; i != end; ++i) - os << std::setfill('0') << std::setw(sizeof(NN) * 2) << std::hex + os << std::setfill('0') << std::setw(sizeof(N) * 2) << std::hex << *i << " "; - return os; + return os.str(); } template < typename N, typename E > @@ -518,6 +589,7 @@ number< N, E > operator* (const number< N, E >& n1, const number< N, E >& n2) template < typename N, typename E > std::pair< number< N, E >, number< N, E > > number< N, E >::split() const { + assert(chunk.size() > 1); typedef number< N, E > num_type; typename num_type::size_type full_size = chunk.size(); typename num_type::size_type halves_size = full_size / 2;